# Are any public key algos commutative?

Are there any public key encryption algorithms that allows for arbitrary ordering of crypto operations (commutative). That is, given a plaintext $$\text{message}_1$$, the following operations work to doubly encrypt it:

$$\text{message}_2 = \operatorname{encrypt}(\text{message}_1, \text{pub}\_\text{key}_1)$$ $$\text{message}_3 = \operatorname{encrypt}(\text{message}_2, \text{pub}\_\text{key}_2)$$

Then to decrypt one would need to remove the encryption in LIFO order:

$$\text{message}_2 = \operatorname{decrypt}(\text{message}_3, \text{priv_key}_2)$$ $$\text{message}_1 = \operatorname{decrypt}(\text{message}_2, \text{priv_key}_1)$$

Is there a crypto method that allows me to also (implying commutativity) reverse the order in which the keys are applied in the decrypt operations to recover the original plaintext $$\text{message}_1$$? That is, I would need the following to work as well:

$$\text{message}_4 = decrypt(\text{message}_3, \text{priv_key}_1)$$ $$\text{message}_1 = decrypt(\text{message}_4, \text{priv_key}_2)$$

• Did you see this answer? – mikeazo Feb 15 '16 at 20:41
• The answer to that question does not really do encryption (stated explicitly in the answer). It only needs a trapdoor function. – Mike Janzen Feb 16 '16 at 23:39
• But the answer mentions some options that appear to fit your needs. – mikeazo Feb 16 '16 at 23:57

## 1 Answer

The classical ElGamal cryptosystem satisfies your requirements. Indeed, let us consider a group $\mathbb{G}$ of prime order $p$ and a generator $g \in \mathbb{G}$. Let $(h_1,h_2) = (g^{s_1},g^{s_2})$ be two public keys for two random secret keys $(s_1,s_2)$. To encrypt a message $m \in \mathbb{G}$ with the public key $h_1$, pick a random coin $r_1 \in \mathbb{Z}_p$ and send $C_1 = (g^{r_1}, mh_1^{r_1}) = (c,c')$. To re-encrypt it, it is sufficient to encrypt the second component $c'$ of the ciphertext $C_1$. So, pick a random coin $r_2$ and compute $C_2 = (c, g^{r_2}, c'h_2^{r_2}) = (\alpha,\beta,\gamma)$, which is a re-encryption of $C_1$ with the second public key $h_2$. Now, you can decrypt in reverse order: decrypt $C_2$ by computing $\gamma / \alpha^{s_1} = \delta = mh_2^{r_2}$, and decrypt the resulting ciphertext $(\beta, \delta)$ with $s_2$: $\beta/ \delta^{s_2} = m$.

However, re-encryption of a ciphertext is not compact: encrypting $n$ times a plaintext results in a ciphertext of size $O(n)$.

There are probably many other examples of commutative cryptosystems, and there has been some work on constructing various interesting cryptosystems with this property, but unless what you want is more complicated than just "commutative public key cryptosystem", the above examples are sufficient.

• to be able to create two keypairs, which are commutative in RSA, shouldn't both parties know the prime factors to be able generate their own key pairs? I think this will undermine the security of the cryptosystem... Unless you had some other construct in mind. – zetaprime Sep 27 '18 at 13:43
• You're perfectly right, you cannot have "independent key pairs over the same plaintext space" for RSA. I'll remove that from the answer when I get access to a computer. – Geoffroy Couteau Sep 27 '18 at 14:45
• Is there any library that supports the commutative public key encryption? – ady Sep 11 '20 at 16:41
• Many libraries support ElGamal; whether any of them explicitly implement the commutative encryption "mode" is something I have no idea about, though doing that on top of any library implementing ElGamal should not be too hard (with the usual disclaimers about not using the crypto you implement yourself as part of something sensitive unless you are a specialist). – Geoffroy Couteau Sep 11 '20 at 17:36