Encryption scheme with equivalent keys? I've long been looking for a symmetric encryption scheme (or algorithm) with equivalent keys. Let me define what I want:


Symmetric encryption algorithm with encryption function $E_k$ and inverse decryption function $D_k$.
Existence of equivalent keys. Keys $k_i \neq k_j$ will be called equivalent if $E_{k_i}(\cdot) \equiv E_{k_j}(\cdot)$ as functions and the same for the decryption operation $D_{k_i}(\cdot) \equiv D_{k_j}(\cdot)$.
Without knowledge of some master secret, it would be computationally infeasible to derive an equivalent key $k' \neq k$ from a key $k$.
With knowledge of some master secret, it would be straightforward to derive at least "many" equivalent keys (let's just say that the equivalent keys should not be scarce compared to the size of the entire keyspace, e.g. 4 equivalent keys in the entire keyspace are not enough).
No trivial intermediate value: of course it's trivial to come up with a scheme satisfying all of the above in which all equivalent keys map to one intermediate value (for example take 128 bit keys with an additional 16 bits at the end, then discard these as a first step before applying standard AES-128). This is perhaps the most important feature and the hardest to define. Let's say then that it requires knowledge of some master secret or some special trapdoor to reduce equivalent keys to an intermediate value. 


Does anyone know of existing schemes/algorithms satisfying at least most of the requirements above, or any interesting papers on the subject, or just have some bright idea to share with us?
I don't know of any scheme that provides this, and it sounds tricky to build one.

Here's the closest I can come up with.  Let $n=pq$ be a 2048-bit RSA modulus, $d$ be a random 2048-bit number that is relatively prime to $(p-1)(q-1)$, and $e = d^{-1} \bmod (p-1)(q-1)$.  The master secret is $d$; $n$ will be baked into the description of the encryption algorithm $E$.  Let $\text{truncate}(z)$ be the result of truncating $z$ to 128 bits: say, deleting the low 1920 bits and keeping the high 128 bits.  Then, define $$E_k(x) = AES(\text{truncate}(k^e \bmod n), x),$$
and similarly for $D_k(x)$.  In other words, the key $k$ is a 2048-bit string.  To encrypt under $k$, we raise the key $k$ to the power $e$ modulo $n$ (a textbook-RSA encryption of $k$), keep the first 128 bits, and use that as an AES key to encrypt the message $x$.

Given a key $k$ and knowledge of the master secret, it is easy to derive many other keys that will be equivalent (just tweak the low bits of $k^e \bmod n$ randomly, then raise that to the $d$th power modulo $n$, and you've got an equivalent key).

This satisfies your requirements 1-4, but not requirement 5.  Why do you need your requirement 5?  I wonder if we might be able to weaken the requirement somehow and still get something that is sufficient for your application.