4
$\begingroup$

I quote Bobby's question here since I encountered the same one...

Random Coin Flip using ElGamal and a Trusted Party

Consider the following protocol for two parties to flip a fair coin.

  1. Trusted party $T$ publishes her public key $K_{pub}$

  2. $A$ chooses a random bit $b_A$, encrypts it under $K_{pub}$, and announces the ciphertext $c_A$ to $B$ and $T$

  3. $B$ does the same and announces a ciphertext $c_B$ (where $c_B \neq c_A$)

  4. $T$ decrypts $c_A$ and $c_B$, and announces the results. Both parties $XOR$ the results to obtain the random value $b_A\oplus b_B$.

It was shown that ElGamal was not appropriate for the encryption scheme. RSA seems to fail to work also. Since $c_A=m^e \mod N$. Then if $m=1$, $c=1$. If $B$ receives $A$'s cipher he will know the exact value of $m$.

So what should the appropriate encryption scheme be?

Improve this question
$\endgroup$
2
  • $\begingroup$ This topic appears to have already been covered in How to fairly select a random number for a game without trusting a third party? and Verify product without revealing multipliers. $\endgroup$ – D.W. Sep 7 '12 at 8:29
  • $\begingroup$ With the protocol as described, active attacks, and if $T$ accepts to play the protocol several times with the same private key, all kinds of horrors can happen, regardless of the qualities of the encryption scheme. E.g. $B$ plays the protocol normally to learn $b_A$, except $B$ captures the communication from $A$ to $T$ at step 2, and blocks communication from $T$ to $A$ at step 4; $B$ then replay the former step 2 to $T$ pretending to be $A$, makes another step 3 where $B$ choses $b_B=b_A\oplus1$, and leaves step 4 proceed normally. The outcome is always $1$, and $B$ knows that. $\endgroup$ – fgrieu♦ Dec 14 '15 at 18:20
5
$\begingroup$

With the added restriction that $c_a \neq c_b$, any CCA-secure cryptosystem will work. For example, Cramer-Shoup instead of Elgamal or RSA+OAEP instead of textbook RSA.

Improve this answer
$\endgroup$
6
$\begingroup$

There is no asymmetric encryption scheme which would work here. Whatever algorithm is used, $B$ can always send the exact same message than $A$ (i.e. set $c_B = c_A$); when $T$ decrypts both messages, he gets the same value both times, and $b_A \oplus b_B$ ends up being zero.

ElGamal encryption just makes it a bit easier for $B$ to game the protocol inconspicuously: $B$ can send the same encrypted bit than $A$ (without knowing it) under a random guise, making it indistinguishable from an honestly encrypted bit. But the core issue is still there: this coin flipping protocol is inherently broken.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I forget to add that $c_A \neq c_B$. Any improvement if we add the above constraint? Thanks. $\endgroup$ – Jake Dec 1 '11 at 0:13
1
$\begingroup$

Note: I originally posted this as an answer to another question before realizing that it was a duplicate, so I'm reposting it here.

As already noted, any scheme that lets $B$ choose $c_B = c_A$ will allow $B$ to cheat by doing so. More generally, so will any scheme that lets $B$, given $c_A$, choose a valid ciphertext $c_B = f(c_A)$ such that $c_B$ still encrypts the same (or the opposite) bit as $c_A$.

Even more generally, $B$ will have an unfair advantage if (and only if!) there exists any function $f$ such that, given $c_A$ and $c_B = f(c_A)$, $B$ can predict $b_A \oplus b_B$ with better than 50% chance. In fact, this is effectively just a restatement of the problem: $B$ can cheat if and only if they can, given $c_A$, choose $c_B$ so as to have an advantage in predicting $b_A \oplus b_B$.

So, what does it take to prevent this? I will argue below that any IND-CCA2 secure encryption scheme will, by definition, suffice to prevent $B$ from cheating (by showing that, if $B$ could cheat, they could also break the IND-CCA2 security), provided that $B$ is prevented from choosing $c_B = c_A$. (Since the ciphertexts are public, this additional restriction can be easily enforced; without it, the problem has no solution, as $B$ can always cheat.)

Proof: Assume that, given a ciphertext $c_A$ encoding a random bit $b_A \in \{0,1\}$, $B$ can choose a valid ciphertext $c_B \ne c_A$, also encoding a single bit, such that they have a non-negligible advantage in guessing whether $c_B$ encodes the same bit as $c_A$. Then $B$ can also break the IND-CCA2 resistance of the encryption scheme as follows:

  1. Submit $M_0 = 0$ and $M_1 = 1$ to the challenger as the two challenge plaintexts.
  2. Treat the received challenge ciphertext as $c_A$, and compute the corresponding $c_B$.
  3. Submit $c_B$ to the decryption oracle to learn which bit it encodes; this is allowed under the rules of the CCA2 game, since $c_B \ne c_A$.
  4. Since $B$ now knows which bit $c_B$ encodes, and (by assumption) has a non-negligible advantage in guessing the XOR of this bit and the challenge bit, they have the same advantage in guessing the challenge bit. $\square$
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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