Commitment scheme: Difference between revisions

Revision as of 03:26, 6 October 2024

Revision as of 21:18, 3 February 2025

Line 2:

{{more citations needed|date=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.<ref name="Goldreich">[[Oded Goldreich]] (2001). ''[https://web.archive.org/web/20230323175232/https://www.wisdom.weizmann.ac.il/~oded/foc-book.html Foundations of Cryptography]'': Volume 1, Basic Tools. Cambridge University Press. {{ISBN|0-521-79172-3}}.{{rp|224}}</ref> 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 protocol]]sprotocols including secure coin flipping, [[zero-knowledge proof]]sproofs, 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&mdash;merely revealed if the sender chooses to give them the key at some later time.

Line 15:

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 extracted from the message 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,<ref name="BCC">Gilles Brassard, David Chaum, and Claude Crépeau, ''[http://crypto.cs.mcgill.ca/~crepeau/PDF/BCC88-jcss.pdf Minimum Disclosure Proofs of Knowledge]'', Journal of Computer and System Sciences, vol. 37, pp. 156–189, 1988.</ref> as part of various zero-knowledge protocols for [[NP (complexity)|NP]], based on various types of commitment schemes.<ref>{{cite journal |last1=Goldreich |first1=Oded |last2=Micali |first2=Silvio |last3=Wigderson |first3=Avi |year=1991 |title=Proofs that yield nothing but their validity |journal=Journal of the ACM |volume=38 |issue=3 |pages=690–728 |citeseerx=10.1.1.420.1478 |doi=10.1145/116825.116852 |s2cid=2389804 |doi-access=free}}</ref><ref>Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51</ref> But the concept was used prior to that without being treated formally.<ref name="Naor">{{cite journal | doi=10.1007/BF00196774 | title=Bit commitment using pseudorandomness | date=1991 | last1=Naor | first1=Moni | journal=Journal of Cryptology | volume=4 | issue=2 | pages=151–158 | s2cid=15002247 | doi-access=free }}</ref><ref name="Crepeau">Claude Crépeau, ''[http://crypto.cs.mcgill.ca/~crepeau/PDF/Commit.pdf Commitment]'', Cryptography and Quantum Information Lab, [[McGill University School of Computer Science]], accessed April 11, 2008</ref> The notion of commitments appeared earliest in works by [[Manuel Blum]],<ref name="Blum">Manuel Blum, ''[https://www.cs.cmu.edu/~mblum/research/pdf/coin/in4.html 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]].</ref> [[Shimon Even]],<ref name="Even">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.</ref> and [[Adi Shamir]] et al.<ref name="SRA81">A. Shamir, [[R. L. Rivest]], and L. Adleman, "[[Mental Poker]]"''.'' In [[David A. Klarner]], ed., ''[https://books.google.com/books?id=DhgGCAAAQBAJ&pg=PA37 The Mathematical Gardner]'' ({{ISBN|978-1-4684-6686-7}}), pp. 37–43. Wadsworth, Belmont, California, 1981.</ref> The terminology seems to have been originated by Blum,<ref name="Crepeau" /> although commitment schemes can be interchangeably called '''bit commitment schemes'''—sometimes reserved for the special case where the committed value is a [[bit]]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.

==Applications==