2
$\begingroup$

Is there a coin flipping protocol where:

  • Alice, Bob and Carol don't trust each other, and
  • The coin is flipped only by Alice and Bob, and
  • The result must be trusted by all three participants.
$\endgroup$
  • $\begingroup$ I'd recommend that you expand on your usage of the term "trust". In particular, Carol not trusting Alice and Bob implies that the latter two colluding is an adversarial model the protocol must consider. Alice and Bob may not trust each other, but from your present description Carol doesn't know that, and therefore could only accept a security argument that considered such an attack. My impression is that you did not have this situation in mind, and were intending to ask about the more limited problem in which Alice, Bob, and Carol are pairwise distrustful. $\endgroup$ – sju Nov 7 '15 at 3:34
  • $\begingroup$ Yes. The protocol should consider a collusion between Alice and Bob that may affect Carol. $\endgroup$ – Victor Nov 7 '15 at 13:14
  • 2
    $\begingroup$ This is unachievable. From Carol's point of view: She isn't involved in the protocol execution (except possibily some initial input). She doesn't trust Alice and Bob (they could in fact be just one party). And she has to trust the result of the coin toss somehow, while having no influence or ability to verify anything. Without further specification this is impossible. $\endgroup$ – tylo Nov 9 '15 at 14:10
5
+50
$\begingroup$

Your requirements are not terribly precise, so here is what I think you mean:

  • "The result must be trusted by all three participants" ==> Even if Alice & Bob are both malicious & colluding, the output of Carol should be uniform. Also, all 3 should get the same output.

  • "The coin is flipped only by Alice and Bob" ==> Alice & Bob do all the work. At the most Carol should just send some information to them beforehand, and get some information from them afterwards.

In that case, it's impossible. Alice & Bob can collude and do the following to force the coin toss to be whatever they want. Suppose they want it to come up heads:

  1. Receive the initial message from Carol.

  2. Run the protocol between the two of them until they are just about to send the final messages to Carol. By our assumption, Carol is not involved in this part.

  3. At this point Alice & Bob can compute what the output is going to be. They both get output eventually (by correctness, it must be the same output Carol will get). But they will receive no more messages from Carol so they must be able to compute their output without her.

  4. If the output is going to be tails, repeat part 2 fresh. Since Carol has no input to the protocol during step 2, correctness of the protocol requires that doing this is undetectable. This must result in a completely fresh outcome, otherwise there is an attack where Carol can fix the outcome of the coin.

  5. If the output is going to be heads, send the final message to Carol.

$\endgroup$
0
$\begingroup$

Your requirements are not particularly clear. What do you mean that "the coin is flipped by only Alice and Bob"? This doesn't have any particular meaning – a coin is a device generating a random value in the set {0, 1}. This value is ideally truly random; it does not depend on Alice or Bob's luck or skill.

As such, nobody really "flips" the coin. The coin is, instead, simply observed.

Having understood this, Alice, Bob, and Carol can simulate the generation of this random value by each generating a random bit, A, B, and C. After they commit to their bit, they all publish their commitments. Finally, they reveal their plaintext values and the result A xor B xor C is computed, which is the result of the coin flip.

While information is exchanged between all three and all three of them choose random values, in the end the coin flip is simply an experiment which is simply observed by all.

$\endgroup$
  • $\begingroup$ Alice, Bob, and Carol can simulate the generation of this random value by each generating a random bit, – The problem is, that the question clearly states … coin is flipped only by Alice and Bob… so the question assumes that Carol won’t be generating anything. Practically, she isn't involved in the protocol execution. This is somewhat clarified by the comment stating “The protocol should consider a collusion between Alice and Bob that may affect Carol.” $\endgroup$ – e-sushi Nov 10 '15 at 23:15
0
$\begingroup$

Alice choose a salt, Bob choose a salt and they create a string starting by the "head" or "tail" (chosen from random) word followed be the salt. Could be like this:

tail$jdfnj4jbfasbjnjnbks 

or

head$vgsjnljb8kbelkjrbvv

they calculate a hash (for instance sha256) of those strings and send them to each other, then they reveal the strings.

If you wanted them to make a consensus on a particular value (head or tail), you can xor them - if they've chosen same values, the result is tail otherwise head.

$\endgroup$
  • 1
    $\begingroup$ "The result must be trusted by all three participants", collusion may occur between Alice and Bob. $\endgroup$ – MH Samadani Nov 11 '15 at 10:44
  • $\begingroup$ you have Alice and Bob closed in the room, they should throw the coin each and they have to inform you what they are doing. The information which they have to publish should prevent them from cheating. Hmm seems to be a stupid question. What if they record the procedure before you close them in the room? $\endgroup$ – smrt28 Nov 11 '15 at 14:43

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.