I want to randomly choose a game in the 50 games I have, in order to play with o

Question

I want to randomly choose a game in the 50 games I have, in order to play with one of my friend. But this friend doesn't trust me, and neither do I: every time one of us pick up a game, the other complains that the choice was not really random.

A first solution could be to put all the names in a hat and after pick up one name; but we're both paranoiac: the hat could contain only one name repeated 50 times, so we have to check that all the names are present only once to ensure an random choice. This is to long.

Second solution: we both randomly choose an integer in [1,50], write it on a paper, and then sum the result modulo 50. This is a good solution when we face each other.

But what if we want to choose an online game, me playing at Paris and my friend playing at NY ? I've trued to emulate the above protocol: each player choose randomly a number in huge interval like [1,1e30] and in a first time send a hash of its number (simulating the fact of hide the number on a piece of paper). When each player have received the hash of the other, the two players publish their numbers and add them modulo 50.

Is this protocol correct? Is there a better (maybe faster) protocol for this purpose?

Explanation / Answer

What you want is a variant of a coin-flipping scheme. The standard way to do this is, as you've identified, to have both people come up with a value and then combine those values such that neither side has any control over the outcome by themselves. You've decided to use modular addition; this is indeed a standard way. You've also identified the issue with that, which is that whoever decided second could control the outcome (as they know what the first person picked), so you need people to commit to their values before they know the other person's value.

This sort of thing is called a commitment scheme. In these systems, Alice has some value she wants to commit to. Specifically, she should send something to Bob which encodes her value, but from which Bob cannot recover the value. Alice can then send Bob a piece of information when it's time to reveal her secret; the idea is that she can only reveal the value she originally committed to.

To get more concrete, assume Alice wants to commit to one bit. She wants to produce a "blob" to send to Bob; this blob encodes either 1 or 0. Then, when it's time to reveal the bit, Alice and Bob can open this blob, using some additional information Alice provides. The two key properties of the blob are that Bob can't discover which bit it encodes, and they can only open the blob to one of the two bits (Alice can't produce a blob encoding 1 and then cheat by opening it to 0).

With bit commitment, you can use a collision-resistant hash, compute the blob as H(s||b) with long random s (you hash s concatenated with b), and reveal s to open it (well, s and b, but revealing s makes it easy to get b). This is equivalent to having a long number and taking it modulo 2 to get the committed bit. Your scheme has similar effect, and should work provided you can't find collisions.

Unfortunately, just doing that means that someone who does find a collision can use it repeatedly. It's better to have Bob provide some random bitstring b to Alice, and have Alice compute a second (secret) random bitstring a, have Alice encode a number from 0 to 50 as 6 bits n (fixed-length, so she can't claim the dividing line is somewhere different than what it actually is), and compute the blob as H(b||a||n). This means that even if Alice finds a collision in H, it doesn't help; she needs a colliding pair that starts with b.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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