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:

1. Symmetric encryption algorithm with encryption function $E_k$ and inverse decryption function $D_k$.

2. 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)$.

3. Without knowledge of some master secret, it would be computationally infeasible to derive an equivalent key $k' \neq k$ from a key $k$.

4. 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).

5. 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?

-
Much like D.W. I doubt there is something matching the question as worded, and suggest you state the practical issue to be solved. –  fgrieu Sep 17 '12 at 11:49
You say that without knowledge of the master secret, deriving equivalent keys should be infeasible. It is a requirement that the fact that there are equivalent keys be kept hidden? In other words, an attacker with access to your source code might be able to look at it and say "hey, if only I knew how to factor this large number (for example), then I could find multiple keys that all resulted in the same encryption." Does the system need to be able to defend against this or can an attacker know that equivalent keys exist but just not be able to find them? –  mikeazo Sep 17 '12 at 12:20
The very existence of equivalent keys is not a secret in this envisioned scheme. It's deriving new additional keys or "merging" equivalent keys to produce new ones that should be difficult/impossible to an attacker. The problem to be solved, basically, and without dragging you all into too much detail, is within the realm of Conditional Access or DRM systems, where different users need to decrypt the same content (encrypted once for all of them), but using keys that are traceable back to them. As noted above, broadcast encryption schemes can handle this in some settings. –  Harel Sep 17 '12 at 12:23

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.

-
Thanks - I'll have to think deeper about your answer, but for now, this is why I want requirement 5: if this were some scheme where equivalent keys were handed out, one to each user/customer, and these were leaked, then they could be traced. But if there's such an intermediate value, this kind of traitor tracing property is lost. In your example, if such a traitor leaked the 128 bits used as the AES key, it wouldn't be traceable to him. –  Harel Sep 15 '12 at 20:10
If that's what you want, you should look at the literature on traitor tracing, watermarking, and such topics. There's been a great deal of research on solving that problem -- though it doesn't necessarily take the form you have described. For instance, Bluray's AACS scheme is a good example of a state-of-the-art approach to this problem. There is a lot written about AACS on the Internet. –  D.W. Sep 15 '12 at 20:52
Thanks, but schemes based on broadcast encryption key distribution are another matter, and have their own practical considerations. I was still wondering if schemes/algorithms based "simply" on equivalent keys, as I defined, are possibles. Maybe the answer is negative. –  Harel Sep 16 '12 at 8:01
@D.W. : You meant $e=d^{-1}\bmod \mathtt{LCM}(p-1,q-1)$ where there is $e = d^{-1} \bmod n$. –  fgrieu Sep 16 '12 at 12:38
Yes, thank you @fgrieu! I've edited my answer to fix this. Thanks for pointing it out! –  D.W. Sep 16 '12 at 23:38

I think your problem might be solved by the Derived Unique Key Per Transaction (DUKPT) key generation algorithm. It doesn't work exactly the way you describe, but the keys might have the properties you're looking for.

DUKPT is used in banking terminals to generate a unique key per message. It starts with a Base Derivation Key, which is the super secret master key for the whole system. When a PIN pad terminal is to have a new key injected, the BDK is transformed using the terminal number and the encryption algorithm (generally 3DES) in a non-reversible fashion. This generates a new key called the Initial PIN Encryption Key (IPEK). The IPEK is injected into the PIN pad (along with the key's ID), which immediately runs the transformation algorithm again, creating a set of (up to) 21 keys called Future Keys (FKs), and the injected IPEK is then discarded by both the terminal and the injection machine. Each FK is used only once to encrypt a single message (containing the customer's account number and PIN), and a transaction counter is increased. That FK is then discarded by the terminal. Once the set of 21 FKs is depleted, the algorithm is run again to generate a new set of FKs.

The message sent to the host contains the key ID, the terminal number, the transaction counter, and the 3DES encrypted data. At the decrypting end, the key generation process is run however many times are indicated by the transaction counter, and the resultant FK is then used to decrypt the message.

The strength comes from the non-reversible translation step. A successful attack on the encryption algorithm is required to recover the previous set of keys. As each older set of FKs is discarded, a terminal progressively drifts farther and farther from the BDK.

Because the IPEKs are individually created for each terminal, no terminal's keys bear any relationship to any other terminal's keys. The compromise of one terminal will not yield a secret that can be used to break any other terminal's message. The compromise of one message will not yield information about any prior keys generated by that terminal. Because IPEKs are destroyed when they are turned into FKs during the initialization of the terminal, no terminal leaves the initialization facility without being at least twice removed from the BDK.

The drawback is decryption effort. The decrypting host must run through the algorithm for every set of FKs generated in the lifetime of the machine. The HSMs used in the financial industry are purpose built to run the DUKPT protocol, and will handle thousands of transactions per second.

-
I was curious about how the DUKPT key derivation process actually worked, and found this presentation from AsiaCrypt 2010 on Google. (It's actually about an optimized variant, but they describe the standard version too.) The interesting feature, not really mentioned in this answer, is that the derived keys effectively form a tree hierarchy, so that the $n$-th transaction key can be derived from the BDK using only $O(\log n)$ derivation steps. –  Ilmari Karonen Sep 17 '12 at 15:09