Consider the following protocol for two parties A and B to flip a fair coin (more...

  

Transcribed Image Text:

Consider the following protocol for two parties A and B to flip a fair coin (more complicated versions of this might be used for internet gambling): (1.) a trusted party T publishes a public key pk (from a public-key encryption scheme); (2.) A chooses a uniform random bit b, encrypts it using pk, and announces the ciphertext CA; (3.) next, B (similarly) chooses a uniform random bit bB, encrypts it using pk, and announces the ciphertext CB; (4.) T decrypts both b and bB, and announces the results; the parties XOR the results to obtain the value of the coin. (a) Argue that even if A is dishonest (but B is honest), the final value of the "coin toss" is uniformly distributed. (b) Assume that the parties use El Gamal encryption (where the bit b is encoded as the group element gb before being encrypted-note that efficient decryption is still possible). Show how a dishonest B can bias the resulting coin to be any value she likes. (c) This is a little troubling. We proved that El Gamal encryption possesses a very strong notion of security; what went wrong? How could we adapt the protocol so that it achieves security? Consider the following protocol for two parties A and B to flip a fair coin (more complicated versions of this might be used for internet gambling): (1.) a trusted party T publishes a public key pk (from a public-key encryption scheme); (2.) A chooses a uniform random bit b, encrypts it using pk, and announces the ciphertext CA; (3.) next, B (similarly) chooses a uniform random bit bB, encrypts it using pk, and announces the ciphertext CB; (4.) T decrypts both b and bB, and announces the results; the parties XOR the results to obtain the value of the coin. (a) Argue that even if A is dishonest (but B is honest), the final value of the "coin toss" is uniformly distributed. (b) Assume that the parties use El Gamal encryption (where the bit b is encoded as the group element gb before being encrypted-note that efficient decryption is still possible). Show how a dishonest B can bias the resulting coin to be any value she likes. (c) This is a little troubling. We proved that El Gamal encryption possesses a very strong notion of security; what went wrong? How could we adapt the protocol so that it achieves security?