Commitment scheme
|
|
In cryptography, a commitment scheme or a bit commitment scheme is a method by which Alice can "commit" to a bit to Bob without revealing to him what the bit is in such a way that the commitment can later be revealed, or "opened" by Alice and verified by Bob. Commitment is related to digital timestamping and zero knowledge proof and finds application in electronic cash, electronic voting and online games.
A useful way to visualize a commitment scheme is to think of Alice as putting the message in a box, securing the box with a lock to which only she has the key, and giving the box to Bob. The challenge, of course, is to find mathematical constructions that capture the behavior of the box, lock and key.
A simple commitment scheme is the following: if b is the commitment, Alice generates a large random number r and gives to Bob the 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.
A commitment scheme can either be perfectly binding (it is theoretically impossible for Alice to alter her commitment after she has made it) or perfectly concealing (it is theoretically impossible for Bob to find out the commitment without Alice revealing it) but not both.
A Perfectly binding scheme
Alice chooses a group of prime order p, and let x be a generator thereof.
Alice picks a value b from 0 to p-1 to commit to and calculates c=x^b and publishes c. To reveal the commitment she tells Bob b.
This method isn't perfectly concealing as someone could find the commitment by solving the discrete logarithm problem c=x^b.