5
$\begingroup$

It's well known that two parties, Alice and Bob, can flip a fair coin using commitments.

  1. Alice picks a random number $a \in \mathbb{Z}_q$ and computes $c_a = Com(a, r_a)$ where $r_a \xleftarrow{R} \mathbb{Z}_q$. She then sends to Bob $c_a$.
  2. Bob does the same, pick a number $b \in \mathbb{Z}_q$, and compute $c_b$ and send it to Alice.
  3. Then, as Bob went second, he's required to open $c_b$ first, revealing $(b, r_b)$. Alice checks the opening.
  4. Then Alice does the same, and Bob checks the opening.
  5. Each of them just computes $a + b \mod q$ and outputs 1 if the answer is less than $\frac{q}{2}$ and 0 otherwise

Commitments require that Alice and Bob be PPT as commitments cannot be statistically binding and hiding. Is there an impossibility result that says one cannot flip a fair coin without commitment or assuming some form of public key cryptography? Can two unbounded algorithms flip a fair bit?

$\endgroup$
2
  • $\begingroup$ Is PPT "probabilistic polynomial time"? $\endgroup$
    – kodlu
    Commented Jan 13, 2023 at 18:00
  • $\begingroup$ Yes PPT = Probabilistic Polynomial Time $\endgroup$
    – Ari
    Commented Jan 14, 2023 at 23:28

2 Answers 2

3
$\begingroup$

Coin flipping with any number of rounds and constant bias is known to imply one-way function, which itself is known to imply commitments.

See here for the first part of the statement (this is the last work in a sequence of papers on cryptographic implications of coin flipping, see the introduction for further references). The second part of the result is implied by this seminal paper, together with the existence of PRGs from one-way functions.

Hence, commitments (or one-way functions) are necessary and sufficient for coin flipping with any nontrivial bias (and can achieve negligible bias against adversaries that do not abort). Coin flipping is therefore impossible with unbounded parties (though it could be possible in other models of computation, e.g. space-bounded cryptography or cryptography over noisy channels).

$\endgroup$
0
1
$\begingroup$

From https://dl.acm.org/doi/pdf/10.1145/12130.12168, it seems impossible to get an unbiased coin in the two-party protocol when one of the parties is corrupt (and unbounded).

The argument is as follows, let $n$ be the security parameter:

Let $\Pi$ be a protocol between Alice and Bob, such that at the end of the protocol, Alice outputs $a$, and Bob outputs $b$. Without loss of generality, assume that Bob is a rushing adversary (Alice sends the first message in each round).

It's safe to assume after $\Pi$ concludes and both parties have output $a$ and $b$, P[a=b] > 1/2. If P[a=b] = 1/2, then Bob just outputs a random bit regardless of what Alice does. If this is the case, Alice can output $a \oplus b$ as the final answer, and she has an unbiased coin. Bob's entire goal is to prevent this from happening.

So we assume that $\Pi$ is $\epsilon$ consistent i.e. P[a=b] = 1/2 + $\epsilon$ for $\epsilon > 0$. This a very weak assumption that states that B will not output an unbiased random bit. In this case Theorem 2.2 of the cited paper shows that for all polynomial functions $f$ : $Pr[f(a,b) = 1 ] \geq 1/2 + \frac{\epsilon}{4r + 1}$ where $r$ is the number of rounds of messaging in $\Pi$.

As $r$ is a polynomial function of the security parameter $n$ the final output is non-negligibly biased away from 1/2.

$\endgroup$
3
  • 1
    $\begingroup$ Is this an answer, or should it have been an edit to the question ? $\endgroup$ Commented Jan 15, 2023 at 0:36
  • $\begingroup$ The new edited paragraph is what I believe the answer. $\endgroup$
    – Ari
    Commented Jan 15, 2023 at 1:39
  • 1
    $\begingroup$ Note that this does not address your question: this is an impossibility of tossing a fair coin when assuming that the adversary can abort. Here, the adversary biases the result by aborting when they're not happy with the outcome. In contrast, commitments imply fair coin flipping in a setting where the parties do not abort. $\endgroup$ Commented Jan 16, 2023 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.