Bit commitment

Bit commitment is a protocol between two mistrusting parties, Alice and Bob, which is supposed to provide the following functionality: In a commit phase, Alice gives as input a value X (e.g., a bit) and Bob gets a confirmation that Alice has commited to a value (without learning the actual value of X). Later, in an opening phase, Alice can decide to reveal the value X to Bob.

The functionality of a bit commitment protocol can be compared with that of a safe as follows: To commit to a value X, Alice writes X on a sheet of paper, locks the paper in the safe, and sends the safe to Bob while keeping the key. To open the commitment, Alice simply sends the key to Bob who opens the safe and reads the value of X.

Bit commitment is an important cryptographic primitive as it can be used as a building block for other tasks such as secure coin flipping.

Bit commitment can be realized classically in an computationally secure sense. More precisely, the protocols are either computationally hiding (in which case it is only computationally secure from Alice's point of view) or computationally binding (computationally secure from Bob's point of view). Moreover, it is not hard to prove that information-theoretically secure bit commitment protocols cannot exist classically. Interestingly, it could be shown that the same is true if we allow Alice and Bob to use quantum mechanics.

Bit commitment can be realized generically if one has access to an oblivious transfer (OT) primitive. Note that, for that reason, the impossiblity proofs mentioned above immediately carry over to OT.

Category:Quantum Cryptography

Last modified: 
Monday, October 26, 2015 - 17:56