7
$\begingroup$

To convey how an adversary can bias the coin, most often a simple commitment-based two party coin-tossing protocol is given, as in [1]:

  1. Alice sends Bob the commitment $c = commit(x)$
  2. Bob sends Alice the bit $y$.
  3. Alice sends Bob $decommit(x)$, Bob verifies Alice actually chose $x$.
  4. Both compute result $r = x \oplus y$

It is said that Alice can place a bias of $1/4$ towards her choice after she receives Bob's bit $y$; if the result is what she wants, she plays along, if not, she aborts, forcing Bob to flip a coin on his own, which has $1/2$ chance of her choice coming up.

I understand the protocol and how a bias can be exerted. What eludes me is why such protocols are of interest:

  1. Why is either party allowed to abort at will? The only point abortion makes sense is when Bob fails to verify, but they can abort whenever they want. If only such an abortion is allowed, the bias-by-abort scheme fails since Alice cannot abort upon seeing the result after the second step.

  2. After Alice aborts, why does Bob flips a coin on his own? If the coin was flipped in case of a dispute, Bob can choose the way it suits him. If Bob could've just generated a random bit without having to prove anyone it is not biased, he would not have bothered with the protocol in the first place.

[1]: https://eprint.iacr.org/2012/643.pdf - Section 1, Example 1.1

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

1. You usually allow parties to abort at will at any stage of the protocol since a malicious adversary can always do that in a real protocol execution, and therefore this is not something we can enforce. A bit more formally, the best we can simulate (for a tutorial on simulation-based proofs see this) is an adversary that can abort, since that's unavoidable anyway.

2. I didn't read the details of the paper but I assume that in the description, Bob still throws a coin if Alice aborts. This is done precisely to break the bias imposed by Alice with the abort. This works because Bob is honest (since Alice is malicious as she aborted) so the output, that is, the coin tossed by Bob, will have a uniform distribution.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 1. In this case: Bob knows if Alice aborts after he sends his bit, she is trying to cheat. Why would an honest party continue the protocol when it is apparent he is being cheated? 2. I fail to see how flipping a coin alleviate an even more severe bias, could you elaborate further, please? Also, Bob flipping a coin at the end implies that if Alice aborts, she has to trust Bob about the coin flip, which ultimately defeats the purpose of using such a protocol in the first place. $\endgroup$
    – cngkaygusuz
    Jun 5, 2018 at 20:43
  • $\begingroup$ Also, don't worry about the paper, anything other than the example is irrelevant to the question at hand. $\endgroup$
    – cngkaygusuz
    Jun 5, 2018 at 20:45
  • $\begingroup$ 1. I do agree it sounds weird, but it's just for the matter of the proof if you want to provide the strongest robustness notion for a protocol: guaranteed output delivery (i.e. the adversary cannot prevent honest parties from getting output). You can always give up on this and say "if the adversary aborts then everybody aborts". However, this (as you said) introduces a bias. $\endgroup$
    – Daniel
    Jun 5, 2018 at 21:04
  • $\begingroup$ You can think of it in the following, perhaps more intuitive way: Imagine that Alice and Bob will run this protocol several times, say 100 times or so. If each time Alice aborts then Bob aborts we would have (possibly) a bias towards a particular bit. The way in which Bob can break this bias is saying "oh so you're cheating? Well, I don't care and I will choose our shared randomness myself then". The point is that the shared randomness is totally uniform now since Bob is honest (of course, Alice now can choose whether or not she uses that randomness as well, but this is a different matter) $\endgroup$
    – Daniel
    Jun 5, 2018 at 21:06
  • 1
    $\begingroup$ I appreciate your answers, but each answer spawns even more questions in my head, which I believe going through them in comments section won't do it any justice. $\endgroup$
    – cngkaygusuz
    Jun 12, 2018 at 17:13

Your Answer

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

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