2
$\begingroup$

I was reading Richard Cleve's 1984 paper on coin flipping protocols, and he says that in the case where parties may abort prematurely and the honest party is forced to output a bit, then the honest party can be forced to be biased by at least 1/r where r is the number of rounds.

Recently Moran, Naor, Segev showed that this bound is asympotically tight.

Although I roughly understand Cleve's proof, I don't understand the premise that the chosen bit that a party outputs when the other party aborts is deterministic. Since they are PPTs, and they are notified when the other party abort, can't the honest party just flip a random coin and output that?

| improve this question | |
$\endgroup$
3
$\begingroup$

In a multi-party protocol, if every honest party just outputs a random bit, it's likely they won't all output the same bit and the protocol would be incorrect.

With two parties, the corrupt party can still bias the output. Suppose the corrupt party aborts in the last round whenever the actual protocol output would be 1. If an abort occurs, the honest party outputs a random bit. Then we have two cases, which each occur with $1/2$ probability:

  • Abort, output random $b \leftarrow \{0,1\}$

  • No abort, output $b=0$

Clearly the probability of outputting 0 is $3/4$, so there is still bias.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Actually, this is the 2-party case, and it's okay if the honest party disagrees with the dishonest party. $\endgroup$ – quantumtremor Nov 18 '16 at 20:09
  • $\begingroup$ OK, that's right in the two-party case. The problem is, the honest party can output a random coin in case of abort, but the output might still be biased when the protocol does not abort. E.g. the corrupt party might abort iff the output is 0, and then the honest party's output will be biased towards 1. $\endgroup$ – pscholl Nov 18 '16 at 21:58
  • $\begingroup$ So this is the part where the corrupt party needs to simulate the honest party, right (since the output value is secret initially). But the corrupt party will guess the bit that the honest party outputs with only 50% accuracy, so how can there be bias? $\endgroup$ – quantumtremor Nov 18 '16 at 22:03
  • $\begingroup$ In the final round, the corrupt party can always predict the honest party's output before choosing whether to send the final message, otherwise the protocol wouldn't be correct. $\endgroup$ – pscholl Nov 18 '16 at 22:42
  • $\begingroup$ Sorry, I'm still confused. In the final round, honest party precomputes a random bit b in case corrupt party halts. If it does halt (send all 0s), then it outputs the random bit b. If it doesn't halt and outputs what it's supposed to, then honest party outputs the bit as dictated by the protocol. So the corrupt party can predict, but if it tries to halt, honest party reverts to outputting a random bit. $\endgroup$ – quantumtremor Nov 19 '16 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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