How is a re-encryption done with elGamal? For example, the "Mental poker" protocol asks for Bob to encrypt each card with his key, shuffle them, and then pass them to Alice.  Alice then encrypts each card with HER key, shuffles them, and then hands them back.  Bob removes his original key and .....

Looking at homomorphic cryptosystems, elGamal seems to work well, but the result of any encryption gives TWO numbers:

$a = G^k \mod P\\ 
b = y^k \ DATA \mod P$

This makes me ask: How is a re-encryption done with elGamal?
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$.


Alice has encrypted a message $m$ as $(x,w)$ with $x = g^k$ and $w = y^k m$.
Bob reencrypts $(x,w)$ as $(x', w')$ with $x' = x g^u$, $w' = w y^u (x')^b$.
Alice "redecrypts" $(x',w')$ as $(x'',w'')$ with $x'' = x' g^v$, $w'' = w' z^v (x')^{-a}$.
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.