Commitment scheme: Difference between revisions

Revision as of 10:37, 1 October 2024

Latest revision as of 05:53, 19 August 2025

(7 intermediate revisions by 7 users not shown)

Line 1:

{{short description|Cryptographic scheme that allows commitment to a chosen value}}

{{more citations needed|date=October 2014}}

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]]. EarlierPrior 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==

Line 21:

===Coin flipping===

Suppose [[Alice and Bob]] want to resolve some dispute via '''[[coin flipping]]'''. If they are physically in the same place, a typical procedure might be:

# Alice "calls" the coin flip,

Line 88:

environment that, instead of corrupting ''C'', corrupts ''R'' instead. Additionally it runs a copy of ''S''. Messages received from ''C'' are fed into ''S'', and replies from ''S'' are forwarded to ''C''.

The environment initially tells ''C'' to commit to a message ''m''. At some point in the interaction, ''S'' will commit to a value ''m′''. This message is handed to ''R'', who outputs ''m′''. Note that by assumption we have ''m' = m'' [[with high probability]]. Now in the ideal process the simulator has to come up with ''m''. But this is impossible, because at this point the commitment has not been opened yet, so the only message ''R'' can have received in the ideal process is a "receipt" message. We thus have a contradiction.

==Construction==

Line 118:

Note that since we do not know how to construct a one-way permutation from any one-way function, this section reduces the strength of the cryptographic assumption necessary to construct a bit-commitment protocol.

In 1991 [[Moni Naor]] showed how to create a bit-commitment scheme from a [[cryptographically secure pseudorandom number generator]].<ref>{{cite web|url=http://citeseer.ist.psu.edu/context/22544/0 |title=Citations: Bit Commitment using Pseudorandom Generators - Naor (ResearchIndex) |publisher=Citeseer.ist.psu.edu |access-date=2014-06-07 |url-access=registration}}</ref> The construction is as follows. If ''G'' is a pseudo-random generator such that ''G'' takes ''n'' bits to 3''n'' bits, then if Alice wants to commit to a bit ''b'':

*Bob selects a random 3''n''-bit vector ''R'' and sends ''R'' to Alice.

Line 259:

It is an interesting question in [[quantum cryptography]] if ''unconditionally secure'' bit commitment protocols exist on the quantum level, that is, protocols which are (at least asymptotically) binding and concealing even if there are no restrictions on the computational resources. One could hope that there might be a way to exploit the intrinsic properties of [[quantum mechanics]], as in the protocols for [[Quantum key distribution|unconditionally secure key distribution]].

However, this is impossible, as Dominic Mayers showed in 1996 {{xref|(see this citation:<ref>Brassard, Crépeau, Mayers, Salvail: [https://arxiv.org/abs/quant-ph/9712023 A brief review on the impossibility of quantum bit commitment]</ref> for the original proof)}}. Any such protocol can be reduced to a protocol where the system is in one of two pure states after the commitment phase, depending on the bit Alice wants to commit. If the protocol is unconditionally concealing, then Alice can unitarily transform these states into each other using the properties of the [[Schmidt decomposition]], effectively defeating the binding property.

One subtle assumption of the proof is that the commit phase must be finished at some point in time. This leaves room for protocols that require a continuing information flow until the bit is unveiled or the protocol is cancelled, in which case it is not binding anymore.<ref>A. Kent: [https://arxiv.org/abs/quant-ph/9906103 Secure classical Bit Commitment using Fixed Capacity Communication Channels]</ref> More generally, Mayers' proof applies only to protocols that exploit [[quantum physics]] but not [[special relativity]]. Kent has shown that there exist unconditionally secure protocols for bit commitment that exploit the principle of [[special relativity]] stating that information cannot travel faster than light.<ref>{{Cite journal|last=Kent|first=A.|date= 1999|title=Unconditionally Secure Bit Commitment|journal=Phys. Rev. Lett.|language=en|volume=83|issue=7|pages=1447–1450|doi=10.1103/PhysRevLett.83.1447|arxiv=quant-ph/9810068|bibcode=1999PhRvL..83.1447K|s2cid=8823466}}</ref>