# Are there transitive ciphers (either symmetric and asymmetric)

Say Alice has information that's already encrypted with Bob's key. She wants Bob to decrypt it without knowing what he just decrypted. So she encrypts it with her key and sends it to him, he decrypts with his key, and sends it back and she decrypts it with her key.

Is there a block cipher where this would work?

• Block ciphers by themselves can't do this. Stream ciphers however can. – SEJPM Jul 10 '15 at 18:40
• @SEJPM Xor is not secure as commutative encryption. – CodesInChaos Jul 10 '15 at 18:58
• @CodesInChaos, what do you mean with "not secure"? This can at most provide IND-CPA and I'm not aware of any else problems... – SEJPM Jul 10 '15 at 18:59
• Related: SRA, pohlig-hellman, three-pass protocol – CodesInChaos Jul 10 '15 at 19:12
• @CodesInChaos, is "SRA" a typo for RSA? – SEJPM Jul 10 '15 at 19:33

Actually, there's the Pohlig-Hellman cipher (dating back to the 70's) that can do precisely this; it works like this:

• There's a large public prime $p$ (for which the DLOG problem is hard)

• The secret key is an integer $x$ that is relatively prime to $p-1$

• To encrypt a message $M$ with key $x$, we compute $C = M^x \bmod p$

• To decrypt a message $C$ with key $x$, we compute $M = C^{x^{-1} \bmod p-1} \bmod p$

It should be clear that the encryption and decryption processes (for a fixed key) are inverses of each other, and that this allows Alice and Bob to do precisely what you asked for; if Alice has $M^b$, she can give Bob , $(M^b)^a = M^{ab}$; Bob computes $(M^{ab})^{b^{-1}} = M^a$, and send that back to Alice, who can then recover $M$

• interesting scheme. I've actually never heard of it. Does it have a fancy name? And why do you require an integer $y$? – SEJPM Jul 10 '15 at 18:53
• @SEJPM: it is formally named for its inventors, which I am totally blanking on right now - it dates back to the 70s. As for why $y$'s there, well, that's because I changed my explination midway through - I was originally going to talk about Alice's and Bob's secret keys together. – poncho Jul 10 '15 at 19:03
• – CodesInChaos Jul 10 '15 at 19:13
• @CodesInChaos: Bingo! – poncho Jul 10 '15 at 19:17

The term you're looking for is commutative encryption.

For instance, the following would work with any block cipher in counter mode, which uses a commutative operation (exclusive-or) for encryption: Alice, given a ciphertext $(\mathit{IV}_0,\mathit{cipher}_0)$ under Bob's key corresponding to some $\mathit{message}$, super-encrypts the ciphertext $\mathit{cipher}_0$ using a new initialization vector $\mathit{IV}_1$ as she would with any plaintext to obtain the new ciphertext $\mathit{cipher}_1$, and passes the ciphertext $(\mathit{IV}_0,\mathit{cipher}_1)$ to Bob. He proceeds to decrypt this using his key to obtain the result $\mathit{cipher}_2$, which is now the encryption of the original $\mathit{message}$ under Alice's key with initialization vector $\mathit{IV}_1$. Alice can use her key to recover $\mathit{message}$ from $(\mathit{IV}_1,\mathit{cipher}_2)$, but all that Bob sees is the encryption of his ciphertext $\mathit{cipher}_0$ as well as the encryption of the original message (both under Alice's key), which does not pose a security risk for good ciphers (that is, those resistant to chosen-plaintext attacks).

• You may want to extend your answer to also mention stream ciphers in general fullfilling the requirement. – SEJPM Jul 10 '15 at 18:54

Please note: Authentication can't trivially be provided.

Assume Alice is given the encrypted message $C=E_{K_B}(P)$, she wants to learn $P$ without revealing $P$ to Bob. Bob however is willing to serve as a decryption oracle for arbitrary messages.

If $E_K(P):=P_K\oplus P$ ($P_K$ being the pad generated by the cipher) then solving the above scenario is quite simple.
The message $C$ then becomes $C=E_{K_B}(P)=P_{K_B}\oplus P$. If Alice now performs $C'=E_{K_A}(C)=P_{K_A}\oplus E_{K_B}(P)=P_{K_A}\oplus P_{K_B}\oplus P$, she can send $C'$ to Bob, who will decrypt this resulting in $P'=P_{K_A}\oplus P$, which is trivially decryptable by Alice. Bob has no chance of learing $P$ at his decryption.

A specific instance of the above scheme is AES-CTR, other choices include Salsa20 and ChaCha20. Please note: The mentioned modes require an IV and usual convention is to prepend the IV to the ciphertext. This preprended IV must not be encrypted as part of the $E_K(P)$ operation. You must have two different IVs prepended to $C'$.

As a general rule:
You need commutative encryption, meaning schemes for which $E_{K_A}(E_{K_B}(P))=E_{K_B}(E_{K_A}(P))$ holds.

Using the above procedure is only secure against passive eavesdroppers, if the $E_{K_B}(P)$ isn't transmitted alone at any point, as this would enable an eavesdropper to compute $P=C\oplus C' \oplus P'=P_{K_B}\oplus P \oplus P_{K_A}\oplus P_{K_B}\oplus P \oplus P_{K_A}\oplus P$ with $P'$ being the response from Bob to Alice.
• By decrypting any messsage (e.g. $C'$) Bob gives away $P_{K_B}$: $C' \oplus E_{K_B}(C') = C' \oplus P_{K_B} \oplus C' = P_{K_B}$. So Bob can just send $K_B$ or $P_{K_B}$ instead... – Stefan Jul 6 '17 at 11:38
Take a look at blind signatures. There is one attack that does what you want. Blind signatures are applicable on most of public key crypto such as RSA. First, Alice blinds the message with a factor $r$ (by multiplying the enc message by $r$ power Bob's public exponent modulo $n$) and then sends it to Bob.
Bob decrypts the message and he gets $C=M\cdot r$. He learns nothing since he doesn't know $r$ and he can't unblind the message.