Talk:Commitment scheme

From Wikipedia, the free encyclopedia

I think the explanation of a bit-commitment protocol from a hash function is incorrect:

A simple commitment scheme is the following: if b is the commitment, Alice generates a large random number r and gives to Bob a hash of b concatenated with r. To open her commitment, Alice reveals b and r thus letting Bob recalculate the hash and compare it with the hash given him earlier to make sure Alice didn't cheat.

If the output length of the hash function is specified (as it is in most cryptographic hash functions) concatenating h(b) and r allows Bob to completely recover h(b) and r.

There is a reasonable sounding bit-commitment protocol from a hash function explained at everything2, and unless someone can explain why the protocol explained here works, I'm going to change the one here.

--Beamishboy 00:00, 3 August 2006 (UTC)

The point is, that Alice hashes the random number r concatenated with b. Since Bob does not know r, and cannot invert the hash function, he has no information whatsoever about b (assuming the output of the hash function is statistically independent of b). So basically what Alice tells Bob in the commitment phase is "I know a number which hashes to the value y=h(b), and the last bit of that number is the one I want to commit to.". It is binding because in order to cheat, Alice needs to find a number with last bit -b and the hash value y that she announced before. If the hash function is really one-way, this is (virtually) impossible.

--Tagmrfen 11:21, 24 August 2006 (UTC)

Thanks for the clarification. I misunderstood the order of operations. If || denotes concatenation, I thought the scheme was h(b) || r instead of h(b||r). As you say though, the security of this bit commitment scheme still rests on the fact that the hash function is statistically independent of b. This fact is not captured by most definitions of hash function security. For example, for this application it is not enough to assume h is collision-resistant or preimage resistant. For that reason, I still would like to change it.

--Beamishboy 22:31, 25 August 2006 (UTC)

You are right, but a hash function that allows to guess one bit of its input with probability != 1/2 would certainly be a very bad hash function. The easy example I like most is the following: Take TWO one-way permutations (!) h_0 and h_1, known to Alice and Bob. Alice chooses a random input X and sends Y=h_b(X) to Bob (note that this is effectively the same as having a hash function which takes one bit more and whose output is statistically independent of b).

Alice effectively promises "I know a number which permuted by h_b is Y". Thus the protocol is perfectly (!) concealing. To reveal the bit, she gives b and X to Bob, who checks that h_b(X)=Y. To cheat, Alice must be able to invert the one-way permutations, which she cannot in reasonable time. So the protocol is binding in a computational sense.

I do not like the protocol at everything2 for two reasons:

• The XOR of two hash function is unneccessary, since it can be merged into one hash function that calculates h_Alice(X) XOR h_Bob(X). There is no point in constructing it from two different functions, since a honest participant must assume that his/her hash function is a "good" hash function anyway, so one could as well use just that one and fix it by the protocol specification.
• On second look, it is just a derivation of the simple protocol described in the article: appending the bit to r is effectively the same as choosing the first N bits of a N+1-bit string at random (->r) and then adjusting the last bit so the parity is even (b=0) or odd (b=1). So one still must assume that the output of the composite hash function is statistically uncorrelated with the parity of the input.

--Tagmrfen 00:03, 27 August 2006 (UTC)