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

  • Trusted party $T$ publishes her public key $p_k$
  • A chooses a random bit $b_A$, encrypts it under $p_k$, and announces the ciphertext $c_A$ to $B$ and $T$
  • $B$ does the same and announces a ciphertext $c_B$
  • $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$.

Suggest what type of encryption scheme would be appropriate to prevent $B$ from cheating.

I would say that an appropriate scheme to use here would be Cramer-Shoup or RSA+OAEP. How can we define an appropriate notion of security and prove that it achieves this definition?

  • $\begingroup$ Why not just use an established method like Diffie-Hellman? $\endgroup$ – r3mainer Dec 4 '15 at 1:44
  • $\begingroup$ Hint: the protocol as stated is insecure if we use a pure encryption scheme. $B$ can cheat by submitting $c_B=c_A$ when its turn comes, making the outcome $0$. Another way: when its turn comes, $B$ submits some dummy $c_B$ to $T$ but not to $A$, obtains $b_A$ from $T$, impersonates $A$ to $T$ and re-submits (in a new instance of the protocol from the standpoint of $T$) the same $c_A$ that $A$ had previously sent, computes another $c_B$ containing the encryption of $b_B={b_A}\oplus1$, then acts per its normal role in the protocol; that makes the outcome $1$. $\endgroup$ – fgrieu Dec 4 '15 at 7:45
  • $\begingroup$ I understand that we cannot use an pure encryption scheme. I am trying to build a hybrid encryption. $\endgroup$ – Tina26 Dec 5 '15 at 12:53
  • $\begingroup$ @fgrieu Thanks but your answer is not related with my question. $\endgroup$ – Tina26 Dec 12 '15 at 18:22