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):
- A trusted party T publishes her public key pk.
- A chooses a random bit $b_A$, encrypts it using pk and announces the ciphertext $c_A$ to everyone.
- B chooses a random bit $b_B$, encrypts it using pk and announces the ciphertext $c_B$ to everyone, with the additional restriction $c_B \neq c_A$.
T decrypts both ciphertexts and announces both plaintexts. The value of the coin is deemed to be the XOR of the two values.
a) Argue that even if A is dishonest (but B is honest), the final value of the coin is uniformly distributed.
b) Suggest what type of encryption scheme would be appropriate to prevent B from cheating. Define an appropriate notion of security and prove that your suggestion achieves this definition.
For part a) I believe that if A is dishonest it has no advantage however following the rules of the protocol and honest B will always produce a different cipher text. However I am confused as it seems that in a deterministic scheme the xor of two diff values will always be 1. How is this a uniformly distributed coin flip in that case?
For part b) I am not sure how the notion of security can be defined?