Commitment scheme: Difference between revisions

Revision as of 20:37, 10 November 2023

Revision as of 23:55, 15 November 2023

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 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,<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 | url=https://link.springer.com/article/10.1007/BF00196774 | 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]]. 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==