# 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?

• @DrLecter - It looks like Maarten Bodewes removed his comments, so I do not understand what you mean about using an "homomorphic property using an encryption of 11. And the operation is componentwise" - can you clarify? Thank you!
– Rich
Jan 30 '17 at 20:44
• @Rich: Hope that helps: crypto.stackexchange.com/questions/18948/… Jan 30 '17 at 20:53
• @DrLecter - rerandomization only gives another ciphertext with same message and same public key. In this case it is not what we want because Alice and Bob have different keys. Jan 30 '17 at 21:09
• @Florian Bourse Sure, this is just a reply to the comment which asks about a previous deleted comment of mine :) Jan 30 '17 at 21:11

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.

• Thank you for the answers. I will look as Shamir's secret sharing. However, I am confused about your answer for elGamel - wouldn't step 2 produce FOUR numbers? The message is one number, then first encryption produces two, and then the re-encryption (of each number from the previous step) make four total numbers.
– Rich
Jan 30 '17 at 20:38
• You aren't encrypting the ciphertext components. You are reencrypting the ciphertexts, which means you turn one ciphertext into a single new ciphertext (with two components). If you encrypted each component separately, this trick would not work.
– K.G.
Jan 30 '17 at 20:57
• Also, this is Shamir's three pass protocol, not Shamir's secret sharing, which is something else. He's been quite productive, you see.
– K.G.
Jan 30 '17 at 20:59
• How do I turn the two components into one?
– Rich
Jan 30 '17 at 22:39
• Why do you want to turn them into one? Decryption does that, of course.
– K.G.
Jan 31 '17 at 17:56

In this case, Alice can use a ciphertext $(c_1,c_2)=(g^r,h_B^r m)$ encrypting m under Bob's public key $h_B=g^{s_B}$ together with her secret key $s_A$ to create a ciphertext for m under the secret key $s_A+s_B$ : $(d_1,d_2)=(c_1,c_2 * c_1^{s_A})$. Then Bob can use this ciphertext and his secret key $s_B$ to create a ciphertext for m under Alice's key : $(d_1,d_2 / d_1^{s_B})$. Which Alice may later decrypt.

It is also possible to rerandomize ciphertexts at each step if you're worried about them all having same first component.

• Yes, randomizing ciphertexts while keeping the first part intact could make shuffling to miss the target. So Alice would update Bob's random $r$ first: $(e_1, e_2) = (c_1 g^{r'}, c_2 h_B^{r'})$ and then encrypt shuffled ciphertexts $(d_1, d_2) = (e_1, e_2 e_1^{s_A})$ to her key, as suggested. Jan 30 '17 at 22:14