First, I can't find a copy of the RSA mental poker report, so I cannot say for sure what kind of "commutative encryption" they wanted to use, but one type is the Pohlig-Hellman cipher, where you encrypt a group element $x$ using a key $k$ by computing $x^k$. To decrypt $y$ using the key $k$, you compute $y^{k^{-1}}$, where the inverse is computed modulo the group order.

In this case, what is meant is to use it like in Shamir's three-pass protocol. Alice encrypts using $k_A$. Bob encrypts using $k_B$. Alice decrypts using $k_A$. Bob decrypts using $k_B$.

Second, ElGamal is a public key cryptosystem, so encrypting a ciphertext doesn't immediately make sense. However, as it turns out, it is possible to do something similar with ElGamal.

So Alice has a public key $y = g^a$ and Bob has a public key $z = g^b$.

1. Alice has encrypted a message $m$ as $(x,w)$ with $x = g^k$ and $w = y^k m$.
2. Bob reencrypts $(x,w)$ as $(x', w')$ with $x' = x g^u$, $w' = w y^u (x')^b$.
3. Alice "redecrypts" $(x',w')$ as $(x'',w'')$ with $x'' = x' g^v$, $w'' = w' z^v (x')^{-a}$.
4. Bob decrypts $(x'',w'')$ as $w'' (x'')^{-b}$.

Note that

• $x' = g^{k+u}$ and $w' = y^{k+u} m z^{k+u}; and

• $x'' = g^{k+u+v}$ and $w'' = y^{k+u} m z^{k+u+v} y^{-k-u} = m z^{k+u+v}$

so $w'' (x'')^{-b} = m$. Here, $(x,w)$ is an encryption of $m$ under $y$, $(x',w')$ is an encryption of $m$ under $yz$ and $(x'',w'')$ is an encryption of $m$ under $z$.

I suspect that these encryptions may be sufficiently independent to be useful in this context, but there is some proving to be done.

First, I can't find a copy of the RSA mental poker report, so I cannot say for sure what kind of "commutative encryption" they wanted to use, but one type is the Pohlig-Hellman cipher, where you encrypt a group element $x$ using a key $k$ by computing $x^k$. To decrypt $y$ using the key $k$, you compute $y^{k^{-1}}$, where the inverse is computed modulo the group order.

In this case, what is meant is to use it like in Shamir's three-pass protocol. Alice encrypts using $k_A$. Bob encrypts using $k_B$. Alice decrypts using $k_A$. Bob decrypts using $k_B$.

Second, ElGamal is a public key cryptosystem, so encrypting a ciphertext doesn't immediately make sense. However, as it turns out, it is possible to do something similar with ElGamal.

So Alice has a public key $y = g^a$ and Bob has a public key $z = g^b$.

1. Alice has encrypted a message $m$ as $(x,w)$ with $x = g^k$ and $w = y^k m$.
2. Bob reencrypts $(x,w)$ as $(x', w')$ with $x' = x g^u$, $w' = w y^u (x')^b$.
3. Alice "redecrypts" $(x',w')$ as $(x'',w'')$ with $x'' = x' g^v$, $w'' = w' z^v (x')^{-a}$.
4. Bob decrypts $(x'',w'')$ as $w'' (x'')^{-b}$.

Note that

• $x' = g^{k+u}$ and $w' = y^{k+u} \; m \; z^{k+u};$ and

• $x'' = g^{k+u+v}$ and $w'' = y^{k+u} \; m \; z^{k+u+v} y^{-k-u} = m z^{k+u+v}$

so $w'' (x'')^{-b} = m$. Here, $(x,w)$ is an encryption of $m$ under $y$, $(x',w')$ is an encryption of $m$ under $yz$ and $(x'',w'')$ is an encryption of $m$ under $z$.

I suspect that these encryptions may be sufficiently independent to be useful in this context, but there is some proving to be done.