Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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