# Random Coin Flip

Quoting an old question:

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 her public key pk.
2. A chooses a random bit $b_A$, encrypts it using pk and announces the ciphertext $c_A$ to everyone.
3. 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$.
4. 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?

• When writing "the xor of two diff values will always be 1" you assume that $cB≠cA⟹b_B≠b_A$; that's not the intent in the problem. $c_B≠c_A$ is here to prevent $B$ from choosing $c_B=c_A$, which would make the outcome $0$. Your reasoning however correctly shows that even with the assumptions in a), the encryption must be randomized for the scheme to work at all. – fgrieu Dec 6 '15 at 16:53
• Hint for a): assume that with $B$ honest, the outcome could be predicted with some advantage; prove that $A$ can break the encryption scheme. $\;$ Hint for b): The problem is broken; no encryption algorithm can make the protocol secure against attacks using $T$ as a decryption oracle. For maximum points, explain that, and repair the problem by assuming $T$ only uses a given pk for two decryptions. Now, try to formalize what $B$ needs to cheat, or what property pk must have to make it impossible. That must in particular prevent attacks turning $c_A$ into $c'_A$ deciphering to $b_A$. – fgrieu Dec 6 '15 at 16:59

This sort of protocol is a bit more complicated than you may think. First, it's very unclear what the role of the trusted party is, relative to the encryption. Specifically, if $T$ is trusted, why not have it just flip a bit and send it to both $A$ and $B$. If $T$ is not trusted, then you need to have it prove that it behaved correctly (e.g., by proving that the decryption is correct). In the latter case, you would be better off just running a direct coin flipping protocol between $A$ and $B$. If you wish to use the result of the coin in a protocol (e.g., gambling) then you will need composition to hold as well. Therefore, just proving that it indistinguishable from random may not be enough.

Regarding the second part of the question, at the very minimum you must have non-malleability. Otherwise, given a ciphertext $c_A$ it may be possible to generate a random ciphertext that encrypts the same value, and then the result will always be 0. (Likewise, it may be possible to always generate a ciphertext that encrypts the opposite value and force the result to be 1.) However, this is also not so simple, since you need to determine whether you need CPA or CCA security, and this is related to the first part. If decryption is provided, then maybe CCA security is required (especially if there are many executions). Note that it is also necessary to include some sort of session ID in order to bind the encryptions to the same session.

Bottom line: you need a proper security model and definition of security. Then you need to take into account the issues above. Finally, you need to prove.

• thanks a lot. For part a) assuming that a trusted part is there and assuming A and B use it to generate a coin flip in the manner described what would your thoughts be on the claim that if A is dishonest but B is honest the coin is still uniformly distributed? I am still confused since no scheme is defined in the question wouldn't a deterministic scheme with the restriction cB ≠ cA always output 1 as xor of two different values is 1. does this imply that we assume a randomized encryption scheme is used? – izac Dec 6 '15 at 10:09
• If $B$ is honest, and the encryption by $B$ is sent after $A$ has already sent its encryption, then it's easy to argue that it's uniform. – Yehuda Lindell Dec 6 '15 at 16:31
• @YehudaLindell Can you provide the proof of part a? – Username Unknown Nov 28 '17 at 18:30

"the xor of two diff"erent bits "will always be 1" even though the scheme is randomized.
One won't get "a uniformly distributed coin flip in" the case of a deterministic scheme,
since no deterministic scheme can provide "a uniformly distributed coin flip".

Since there is a trusted third party, A's security against B is defined in the UC framework.
For that direction, one must assume that $\big[\hspace{-0.02 in}$[$\hspace{.02 in}$B never compromises T$\hspace{.03 in}$]
and $\: \big[\hspace{-0.02 in}$if the PKE scheme is not sender-non-committing, then B
never gets access to the randomness that A used to encrypt bA$\hspace{.02 in}\big]\big]$.

B's security against A will be information-theoretic UC, even if A [compromises T$\hspace{.03 in}$]
and [sees B's randomness as B generates it]. ​ ​ ​ However, that security might be
limited to twice the predictability of what cB would be without the restriction ​ cB ≠ cA .

• Thanks for your answer. It really helps. Just to confirm what do you mean exactly when you say this? "the xor of two different bits "will always be 1" even though the scheme is randomized. It's not, since a deterministic scheme can't provide "a uniformly distributed coin flip" – izac Dec 6 '15 at 9:50
• Also what exactly is a sender non committing scheme? The internet is not very clear on that! – izac Dec 6 '15 at 9:56
• (I think I fixed my answer's ambiguity.) ​ Sender-non-committing encryption is what you get by removing each of $\sigma_G$ and $\sigma_G^b$ from the ordered quadruple it's an entry of in [Definition 2](www.cs.columbia.edu/~dglasner/MyPapers/nce.pdf#page=9). ​ ​ ​ ​ – user991 Dec 6 '15 at 10:10
• Thanks. So you are saying that in such a protocol we MUST assume a randomized encryption scheme to have a chance of a uniformly distributed coin flip? – izac Dec 6 '15 at 10:20
• No; I'm saying we must assume a randomized not-necessarily-encryption scheme for that. ​ ​ – user991 Dec 6 '15 at 10:23