7
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ @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! $\endgroup$
    – Rich
    Commented Jan 30, 2017 at 20:44
  • $\begingroup$ @Rich: Hope that helps: crypto.stackexchange.com/questions/18948/… $\endgroup$
    – DrLecter
    Commented Jan 30, 2017 at 20:53
  • $\begingroup$ @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. $\endgroup$
    – Florian Bourse
    Commented Jan 30, 2017 at 21:09
  • $\begingroup$ @Florian Bourse Sure, this is just a reply to the comment which asks about a previous deleted comment of mine :) $\endgroup$
    – DrLecter
    Commented Jan 30, 2017 at 21:11

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Rich
    Commented Jan 30, 2017 at 20:38
  • $\begingroup$ 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. $\endgroup$
    – K.G.
    Commented Jan 30, 2017 at 20:57
  • $\begingroup$ Also, this is Shamir's three pass protocol, not Shamir's secret sharing, which is something else. He's been quite productive, you see. $\endgroup$
    – K.G.
    Commented Jan 30, 2017 at 20:59
  • $\begingroup$ How do I turn the two components into one? $\endgroup$
    – Rich
    Commented Jan 30, 2017 at 22:39
  • $\begingroup$ Why do you want to turn them into one? Decryption does that, of course. $\endgroup$
    – K.G.
    Commented Jan 31, 2017 at 17:56
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Vadym Fedyukovych
    Commented Jan 30, 2017 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.