Global InformationCommitment scheme information
 | This article needs additional citations for verification. (October 2014) |
A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later.[1] Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding. Commitment schemes have important applications in a number of cryptographic protocols including secure coin flipping, zero-knowledge proofs, and secure computation.
A way to visualize a commitment scheme is to think of a sender as putting a message in a locked box, and giving the box to a receiver. The message in the box is hidden from the receiver, who cannot open the lock themselves. Since the receiver has the box, the message inside cannot be changed—merely revealed if the sender chooses to give them the key at some later time.
Interactions in a commitment scheme take place in two phases:
- the commit phase during which a value is chosen and committed to
- the reveal phase during which the value is revealed by the sender, then the receiver verifies its authenticity
In the above metaphor, the commit phase is the sender putting the message in the box, and locking it. The reveal phase is the sender giving the key to the receiver, who uses it to open the box and verify its contents. The locked box is the commitment, and the key is the proof.
In simple protocols, the commit phase consists of a single message from the sender to the receiver. This message is called the commitment. It is essential that the specific value chosen cannot be known by the receiver at that time (this is called the hiding property). A simple reveal phase would consist of a single message, the opening, from the sender to the receiver, followed by a check performed by the receiver. The value chosen during the commit phase must be the only one that the sender can compute and that validates during the reveal phase (this is called the binding property).
The concept of commitment schemes was perhaps first formalized by Gilles Brassard, David Chaum, and Claude Crépeau in 1988,[2] as part of various zero-knowledge protocols for NP, based on various types of commitment schemes.[3][4] But the concept was used prior to that without being treated formally.[5][6] The notion of commitments appeared earliest in works by Manuel Blum,[7] Shimon Even,[8] and Adi Shamir et al.[9] The terminology seems to have been originated by Blum,[6] although commitment schemes can be interchangeably called bit commitment schemes—sometimes reserved for the special case where the committed value is a bit. Earlier to that, commitment via one-way hash functions was considered, e.g., as part of, say, Lamport signature, the original one-time one-bit signature scheme.
- ^ Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3.: 224
- ^ Gilles Brassard, David Chaum, and Claude Crépeau, Minimum Disclosure Proofs of Knowledge, Journal of Computer and System Sciences, vol. 37, pp. 156–189, 1988.
- ^ Goldreich, Oded; Micali, Silvio; Wigderson, Avi (1991). "Proofs that yield nothing but their validity". Journal of the ACM. 38 (3): 690–728. CiteSeerX 10.1.1.420.1478. doi:10.1145/116825.116852. S2CID 2389804.
- ^ Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51
- ^ Naor, Moni (1991). "Bit commitment using pseudorandomness". Journal of Cryptology. 4 (2): 151–158. doi:10.1007/BF00196774. S2CID 15002247.
- ^ a b Claude Crépeau, Commitment, Cryptography and Quantum Information Lab, McGill University School of Computer Science, accessed April 11, 2008
- ^ Manuel Blum, Coin Flipping by Telephone, Proceedings of CRYPTO 1981, pp. 11–15, 1981, reprinted in SIGACT News vol. 15, pp. 23–27, 1983, Carnegie Mellon School of Computer Science.
- ^ Shimon Even. Protocol for signing contracts. In Allen Gersho, ed., Advances in Cryptography (proceedings of CRYPTO '82), pp. 148–153, Santa Barbara, CA, US, 1982.
- ^ A. Shamir, R. L. Rivest, and L. Adleman, "Mental Poker". In David A. Klarner, ed., The Mathematical Gardner (ISBN 978-1-4684-6686-7), pp. 37–43. Wadsworth, Belmont, California, 1981.