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.

  • $\begingroup$ Are you sure it is a good idea to send the key for the next encryption in plain? (I.e. your two 2.2 steps seem not good fitting together.) $\endgroup$ – Paŭlo Ebermann Jun 10 '12 at 12:10
  • $\begingroup$ I agree with Paŭlo; it sounds like everyone who gets both messages will be able to recover the plaintext. What's the motivation behind this protocol? What security properties is it supposed to have? If it is privacy, how is Bob supposed to decrypt, but Eve cannot? What distinguishes Bob from Eve? $\endgroup$ – poncho Jun 10 '12 at 16:44
  • $\begingroup$ Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to software development (the topic of Stack Overflow), and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. $\endgroup$ – Paŭlo Ebermann Jun 10 '12 at 19:10
  • $\begingroup$ There was a mistake in 2.3, fixed it and added some details $\endgroup$ – Kirill Morarenko Jun 11 '12 at 21:51
  • $\begingroup$ Ah, that's now consistent. By secure channel you likely mean it is safe from alteration. Is D in (3) bound to be the reverse of E in (1)? Is E in (2.3) bound to be exactly the same as E in (1)? If E is unchangeable, what can we assume about it? $\endgroup$ – fgrieu Jun 12 '12 at 5:58

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.

| improve this answer | |
  • $\begingroup$ Yes the OTP has the property $D(K_1\oplus K_2, E(K_2, E(K_1, P))) = P$, but not the property $E(C_k, E(K_1, P))=C$ required by (2.3) when one defines $C_k=K_1\oplus K_2$ wich is how we read (2.2) and the introduction of $+$ in the question. The question appears to have a bug. $\endgroup$ – fgrieu Jun 11 '12 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.