What is the appropriate public key encryption for secure coin flipping?

Question

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?

Answer 1

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.

Answer 2

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.