1
$\begingroup$

I decided to ask the question here, because although the problem is mathematical, I'm interested in its application here. In the version i read in wikipedia, they suggested the following method for Alice and Bob to agree on a coin flip result from afar:

1)Alice gives Bob a commitment(a box), which contains her 'call', but Bob dosent know what it is.

2)Bob performs the flip and reports the result to Alice.

3)Alice tells the 'key' to Bob who now learns her 'call'. If the call matches the report, Alice wins, else Bob does.

First of all, I want to know how this 'box' is actually implemented, in a relevant crypto system. Based on how the 'box' is actually defined, Alice can always win as follows: (We assume a 'box' to be a secure file, whose contents are absolutely unknown to Bob. Name this file F)

1)Alice gives Bob the 'box' which contains both possible calls 'tail' and 'heads' of the coin flip(but obviously Bob dosent know anything about the contents by the definition used above).

2)Bob performs the flip and reports the result to Alice(let it be heads).

3)Alice supplies the corresponding key $k_h$ to Bob, such that: $k_h(F) = 'heads'$, and alice inevitably wins.(if Bob reported tails, she would supply $k_t$ such that $k_t(F) = 'tails'$)

Basically the file here is a 2-key container, which returns a different result based on the key used. Is the definition of 'box' i gave wrong? What is the correct definition?

$\endgroup$
4
$\begingroup$

Is the definition of 'box' i gave wrong? What is the correct definition?

It is incorrect.

The analogous description of a commitment scheme would be that it is a box that contains only one choice (for example, "heads" or "tails"), Alice can place either, and Bob can't tell (by looking at the box) which is in it.

Later, Alice can open the box; Bob can then tell what's in it and (here's the key point) Alice can't change her mind what's in the box.

With this definition, this is a secure coin flip protocol (except that when Alice learns Bob's choice, she can walk away without opening the box; that needs to be handled somehow).

The easiest way to implement a commitment scheme is with a cryptographical hash function; Alice picks the secret value she's putting into the commitment and a long random nonce, she hashes them both together:

$$Commitment = Hash( Secret || Nonce )$$

She then sends the hash to Bob. Bob, by looking at the hash, can't recover the commitment (because of the random nonce). Then, Alice opens the commitment by revealing the secret and the nonce; Bob verifies the secret by hashing the revealed secret and nonce together to recompute the original commitment. If the Hash used is collision resistant (that is, we can't find two distinct values that hash to the same value), then Alice can't have a single commitment that can open to two different value (because that would imply two different $Secret || Nonce$ values that hash to the same thing, and we assume Alice can't find such a pair).

|improve this answer|||||
$\endgroup$

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.