# 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

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