display | more...

A cryptographic protocol where Alice puts a secret binary value (a bit), into an "envelope", so that Bob cannot guess the value of the bit, and Alice cannot change the value of the bit after she has committed to its value.

One example of such a protocol involves the use of a one-way hash function such as MD5 or SHA. Both Alice and Bob construct or choose a hash function, and each lets the other know of this choice. Alice then selects a random number of bits whose parity she chooses, and runs these bits through both her and Bob's hash functions, and XOR's the result. This parity Alice chose gets put into the "envelope" provided by the security of the hash functions. Bob then attempts to guess the parity of her input. If he guesses wrongly, Alice must prove that he's wrong by revealing her input, which Bob can then verify by passing it through both of their hash functions and XORing the results.

Note that the security of this protocol requires that the hash functions have properties that make it impossible for (1) Bob to invert them and recover Alice's input (preimage resistance) and (2) Alice to find two different inputs that have opposite parity that lead to the same input (collision resistance).

Bit commitment protocols are widely used as building blocks for more complicated protocols like zero knowledge proofs of knowledge and oblivious transfer. One can also use protocols of this kind to play mental poker.