Transparent cipher

Question

I'm trying to implement this protocol:

1. Alice has her permanent key $K_1$. She computes $E(K_1, P)$.

2. She wants to share $P$ with Bob, Carol and Dave. For each of them she:

   2.1. Generates $K_2$.

   2.2. Computes $E_k(K_2, K_1)$ as $C_k$ and sends it via a secure channel.

   2.3. Computes $E(K_2, E(K_1, P))$ as $C$ and sends it via a secure channel.

3. Everyone decrypts $P$ using $D(C_k, C)$

Looks like I need something like this property:

$$D(K_1 + K_2, E(K_2, E(K_1, P))) = P,$$

with $E_k: (K_2, K_1)\mapsto E_k(K_2, K_1) = K_1+K_2$, where $+$ doesn't necessarily mean 'concatenation'. I don't know the proper term for this, although I'm pretty sure it exists.

Edit: "secure channel" in 2.2 and 2.3; $K_2$ in 2.3.

The original problem has Frank as a relay host. He has $E(K_1, P)$ and he executes 2.1, 2.2 and 2.3. I don't want anyone to have to know $K_1$ to decrypt the original message, that's why I'm trying to come up with something complicated. I can't alter step 1 - if I could, assymetric cipher whould solve my problem.

Answer 1

The one-time pad has this property. Specifically, letting $\oplus$ denote the bitwise XOR operation, the binary OTP is defined as:

$$E(K,M) = D(K,M) = K \oplus M.$$

From the commutativity and cancellation properties of $\oplus$, it then follows that

$$\begin{aligned} D(K_1 \oplus K_2, E(K_1, E(K_2, M))) &= (K_1 \oplus K_2) \oplus (K_1 \oplus (K_2 \oplus M)) \\ &= (K_1 \oplus K_2) \oplus (K_1 \oplus K_2) \oplus M \\ &= M \end{aligned}$$

More generally, any synchronous stream cipher also has essentially the same property. Letting $S(K)$ be the keystream generated by the key $K$, a binary additive stream cipher is defined as:

$$E(K,M) = D(K,M) = S(K) \oplus M.$$

Thus, if we define $S(K_1 + K_2)$ as $S(K_1) \oplus S(K_2)$ (where $K_1 + K_2$ denotes any encoded value from which we can unambiguously decode $K_1$ and $K_2$), then the stream cipher has the property you seek.

Even more generally, various other commutative encryption schemes, such as (textbook) RSA, could be used to achieve a similar property. However, as others have noted in the comments, it's not at all clear that this actually accomplishes any useful security goal. I'd suggest that you may want to rethink your protocol, and preferably provide a more explicit description of what you want to accomplish with it.

I do have a hunch that what you may be looking for might be something like the three-pass protocol, which allows one party to send a secret message to another using commutative encryption (specifically, exponentiation in a finite field) even if the two parties don't possess any shared keys. On a general level, the three-pass protocol works like this:

1. Alice → Bob: $C_A = E(K_A, M)$
2. Bob → Alice: $C_{AB} = E(K_B, C_A) = E(K_B, E(K_A, M))$
3. Alice → Bob: $C_B = D(K_A, C_{AB}) = D(K_A, E(K_B, E(K_A, M))) = E(K_B, M)$

Here, $K_A$ and $K_B$ are random keys chosen by Alice and Bob respectively. Bob then computes $M = D(K_B, C_B)$.

Step 3 above works because we're using commutative encryption — specifically, $E(K, M) = M^K$ and $D(K, M) = M^{K^{-1}}$, where the exponentiation is done in a finite field ($GF(p)$ for Shamir's three-pass protocol, $GF(2^n)$ for the Massey–Omura version). See the Wikipedia article for more details.