Alice and Bob want to agree on a bit 0 or 1. Both know it would be fair to pick

Question

Alice and Bob want to agree on a bit 0 or 1. Both know it would be fair to pick that at random, but there's no way they could meet to throw a dice and no third party they could trust. Are there known protocols that allow either side to prove that they did not manipulate the outcome?

My idea is: Both randomly (or not - but that would be in their best interest) pick 0 or 1, write it down, put it in an envelope and send it to the other person. Then the XOR of both bits could not have been manipulated unfairly by either party.

The problem I see with that: How can Alice prove to Bob that she did not open his envolope before making her choice?

Explanation / Answer

You're close with the idea of using an envelope; the standard answer is to use a commitment scheme; this is a scheme where someone can publish a 'commitment' to a value, and then later revealing what that value was. The two essential properties of commitments are:

+ Someone just looking at the commitment cannot tell what the secret was

+ Someone with the commitment cannot reveal a value other than the value that was committed to.

How this works in this scenario is exactly analogous to your envelope method; Alice selects a random bit, and publishes a commitment to that bit. Bob then selects a bit (there's no need for a commitment there) and publishes it; Alice then reveals the bit she committed to; the exclusive-or of Alice and Bob's bit is the output.

Now, there are a number of practical commitment schemes known. The easiest is to use a cryptographically secure hash function; Alice selects a large random value A and publishes the hash value hash(A). Bob then selects his bit and publishes it; Alice then publishes A (and they use, say, the lsbit of A is Alice's bit).

Looking at hash(A), Bob gets no information on what the lsbit of A was (assuming Alice selected a sufficiently large bit string). This is not a formal requirement of cryptographically secure hash functions, but is a reasonable assumption with real hashes (especially if Alice chooses an A which is longer than the hash function output).

And, assuming that we're using a cryptographically secure hash function, Alice cannot decide to reveal a different value A?; if she could, that would mean that Alice found a hash collision hash(A)=hash(A?), and we assume Alice can't do that.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.