Commitment scheme: Difference between revisions

Revision as of 04:34, 5 October 2023

Latest revision as of 05:53, 19 August 2025

(26 intermediate revisions by 24 users not shown)

Line 1:

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

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

Line 13:

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 knownextracted 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 | 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]]. 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,

# Bob flips the coin,

# If Alice's call is correct, she wins, otherwise Bob wins.

If Alice and Bob are not in the same place a problem arises. Once Alice has "called" the coin flip, Bob can stipulate the flip "results" to be whatever is most desirable for him. Similarly, if Alice doesn't announce her "call" to Bob, after Bob flips the coin and announces the result, Alice can report that she called whatever result is most desirable for her. Alice and Bob can use commitments in a procedure that will allow both to trust the outcome:

Line 33:

# Alice reveals what she committed to,

# Bob verifies that Alice's call matches her commitment,

# If Alice's revelation matches the coin result Bob reported, Alice wins.

For Bob to be able to skew the results to his favor, he must be able to understand the call hidden in Alice's commitment. If the commitment scheme is a good one, Bob cannot skew the results. Similarly, Alice cannot affect the result if she cannot change the value she commits to.

A real-life application of this problem exists, when people (often in media) commit to a decision or give an answer in a "sealed envelope", which is then opened later. "Let's find out if that's what the candidate answered", for example on a game show, can serve as a model of this system.

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==

A commitment scheme can either be perfectly binding (it is impossible for Alice to alter her commitment after she has made it, even if she has unbounded computational resources); or perfectly concealing (it is impossible for Bob to find out the commitment without Alice revealing it, even if he has unbounded computational resources); or formulated as an instance-dependent commitment scheme, which is either hiding or binding depending on the solution to another problem.<ref>Shien Hin Ong and Salil Vadhan (1990). Perfect zero knowledge in constant round, In Proc. STOC, p. 482-493482–493, cited in Shien Hin Ong and Salil Vadhan (2008). An Equivalence between Zero Knowledge and Commitments, Theory of Cryptography.</ref><ref>Toshiya Itoh, Yiji Ohta, Hiroki Shizuya (1997). A language dependent cryptographic primitive, In J. Cryptol., 10(1):37-49, cited in Shien Hin Ong and Salil Vadhan (2008). An Equivalence between Zero Knowledge and Commitments, Theory of Cryptography.</ref> A commitment scheme can notcannot be both perfectly hiding and perfectly binding at the same time.

===Bit-commitment in the random oracle model===

Bit-commitment schemes are trivial to construct in the [[random oracle]] model. Given a [[cryptographic hash function|hash function]] H with a 3''k'' bit output, to commit the ''k''-bit message ''m'', Alice generates a random ''k'' bit string ''R'' and sends Bob H(''R'' || ''m''). The probability that any ''R′'', ''m′'' exist where ''m′'' ≠ ''m'' such that H(''R′'' || ''m′'') = H(''R'' || ''m'') is ≈ 2^−''k'', but to test any guess at the message ''m'' Bob will need to make 2^''k'' (for an incorrect guess) or 2^''k''-1 (on average, for a correct guess) queries to the random oracle.<ref>{{Citation

| last = Wagner

| first = David

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 154:

These constructions are tightly related to and based on the algebraic properties of the underlying groups, and the notion originally seemed to be very much related to the algebra. However, it was shown that basing statistically binding commitment schemes on general unstructured assumption is possible, via the notion of interactive hashing

for commitments from general complexity assumptions (specifically and originally, based on any one way permutation) as in.<ref>Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung:

Perfect Zero-Knowledge Arguments for NP Using Any One-Way Permutation. J. Cryptology 11(2): 87-10887–108 (1998)[https://link.springer.com/article/10.1007%2Fs001459900037]</ref>

===A perfectly hiding commitment scheme based on RSA===

Line 176:

}}</ref>

===Additive and Multiplicativemultiplicative Homomorphichomomorphic properties of commitments===

The Pedersen commitment scheme introduces an interesting homomorphic property that allows performing addition between two commitments. More specifically, given two messages <math>m_1</math> and <math>m_2</math> and randomness <math>r_1</math> and <math>r_2</math>, respectively, the it is possible to generate a new commitment such that: <math>C(m_1, r_1) \cdot C(m_2, r_2) = C(m_1 + m_2, r_1 + r_2)</math>. Formally:

<math>C(m_1, r_1) \cdot C(m_2, r_2) = g^{m_1} h^{r_1} \cdot g^{m_2} h^{r_2} = g^{m_1+m_2} h^{r_1+r_2} = C(m_1 + m_2, r_1 + r_2)</math>

Line 195:

===Vector hashing===

Vector hashing is a naive vector commitment partial reveal scheme based on bit-commitment. Values <math>m_1, m_2, ... m_n</math> are chosen randomly. Individual commitments are created by hashing <math>y_1=H(x_1||m_1), y_2=H(x_2||m_2), ...</math>. The overall commitment is computed as

:<math>C=H(y_1||y_2||...||y_n)</math>

In order to prove one element of the vector <math>X</math>, the prover reveals the values

:<math>(i, y_1, y_2, ..., y_{i-1}, x_i, m_i, y_{i+1}, ..., y_n)</math>

The verifier is able to compute <math>y_i</math> from <math>x_i</math> and <math>m_i</math>, and then is able to verify that the hash of all <math>y</math> values is the commitment <math>C</math>.

Unfortunately the proof is <math>O(n)</math> in size and verification time. Alternately, if <math>C</math> is the set of all <math>y</math> values, then the commitment is <math>O(n)</math> in size, and the proof is <math>O(1)</math> in size and verification time. Either way, the commitment or the proof scales with <math>O(n)</math> which is not optimal.

===Merkle tree===

A common example of a practical partial reveal scheme is a [[Merkle tree]], in which a binary hash tree is created of the elements of <math>X</math>. This scheme creates commitments that are <math>O(1)</math> in size, and proofs that are <math>O(\log_2{n})</math> in size and verification time. The root hash of the tree is the commitment <math>C</math>. To prove that a revealed <math>x_i</math> is part of the original tree, only <math>\log_2{n}</math> hash values from the tree, one from each level, must be revealed as the proof. The verifier is able to follow the path from the claimed leaf node all the way up to the root, hashing in the sibling nodes at each level, and eventually arriving at a root node value that must equal <math>C</math>.<ref>{{Cite web |url=http://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf |title=Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis |last=Becker |first=Georg |date=2008-07-18 |publisher=Ruhr-Universität Bochum |page=16 |access-date=2013-11-20 |archive-date=2014-12-22 |archive-url=https://web.archive.org/web/20141222120036/http://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf |url-status=dead }}</ref>

===KZG commitment===

Line 214 ⟶ 221:

====Reveal====

A KZG proof must demonstrate that the revealed data is the authentic value of <math>x_i</math> when <math>C</math> was computed. Let <math>y=x_i</math>, the revealed value we must prove. Since the vector of <math>x_i</math> was reformulated into a polynomial, we really need to prove that the polynomial <math>p</math>, when evaluated at <math>i</math>, takes on the value <math>y</math>. Simply, we just need to prove that <math>p(i)=y</math>. We will do this by demonstrating that subtracting <math>y</math> from <math>p</math> yields a root at <math>i</math>. Define the polynomial <math>q</math> as

:<math>q(x)=\frac{p(x)-y}{x-i}</math>

This polynomial is itself the proof that <math>p(i)=y</math>, because if <math>q</math> exists, then <math>p(x)-y</math> is divisible by <math>x-i</math>, meaning it has a root at <math>i</math>, so <math>p(i)-y=0</math> (or, in other words, <math>p(i)=y</math>). The KZG proof will demonstrate that <math>q</math> exists and has this property.

Line 230 ⟶ 237:

where <math>e</math> is the bilinear map function as above. <math>H \cdot t</math> is a precomputed constant, <math>H \cdot i</math> is computed based on <math>i</math>.

By rewriting the computation in the pairing group <math>\mathbb{G}_T</math>, substituting in <math>\pi=q(t) \cdot G</math> and <math>C=p(t) \cdot G</math>, and letting <math>\tau(x)=e(G,H)^x</math> be a helper function for lifting into the pairing group, the proof verification is more clear.

:<math>e(\pi, H \cdot t - H \cdot i) = e(C - G \cdot y, H)</math>

:<math>e(G \cdot q(t), H \cdot t - H \cdot i) = e(G \cdot p(t) - G \cdot y, H)</math>

Line 241 ⟶ 249:

{{hidden

| Why the bilinear map pairing is used |

The utility of the bilinear map pairing is to allow the multiplication of <math>q(x)</math> by <math>x-i</math> to happen securely. These values truly lie in <math>\mathbb{G}_1</math>, where division is assumed to be computationally hard. For example, <math>\mathbb{G}_1</math> might be an [[elliptic curve]] over a finite field, as is common in [[elliptic-curve cryptography]]. Then, the division assumption is called the [[Elliptic-curve cryptography#Rationale|elliptic curve discrete logarithm problem]]{{Broken anchor|date=2024-07-20|bot=User:Cewbot/log/20201008/configuration|target_link=Elliptic-curve cryptography#Rationale|reason= The anchor (Rationale) [[Special:Diff/1148439344|has been deleted]].}}, and this assumption is also what guards the trapdoor value from being computed, making it also a foundation of KZG commitments. In that case, we want to check if <math>q(x)(x-i) = p(x)-y</math>. This cannot be done without a pairing, because with values on the curve of <math>G \cdot q(x)</math> and <math>G \cdot (x-i)</math>, we cannot compute <math>G \cdot (q(x)(x-i))</math>. That would violate the [[computational Diffie–Hellman assumption]], a foundational assumption in [[elliptic-curve cryptography]]. We instead use a [[pairing]] to sidestep this problem. <math>q(x)</math> is still multiplied by <math>G</math> to get <math>G \cdot q(x)</math>, but the other side of the multiplication is done in the paired group <math>\mathbb{G}_2</math>, so, <math>H \cdot (t-i)</math>. We compute <math>e(G \cdot q(t), H \cdot (t-i))</math>, which, due to the [[bilinear map|bilinearity]] of the map, is equal to <math>e(G, H)^{q(t)\cdot(t-i)}</math>. In this output group <math>\mathbb{G}_T</math> we still have the [[Discrete logarithm#Cryptography|discrete logarithm problem]], so even though we know that value and <math>e(G, H)</math>, we cannot extract the exponent <math>q(t)\cdot(t-i)</math>, preventing any contradiction with discrete logarithm earlier. This value can be compared to <math>e(G \cdot (p(t) - y), H)=e(G, H)^{p(t) - y}</math> though, and if <math>e(G, H)^{q(t)\cdot(t-i)} = e(G, H)^{p(t) - y}</math> we are able to conclude that <math>q(t) \cdot (t-i) = p(t)-y</math>, without ever knowing what the actual value of <math>t</math> is, let alone <math>q(t)(t-i)</math>.

|style = border: 1px solid lightgray; <!-- copied from the Navier–Stokes equations page -->

|headerstyle = text-align:left

Line 251 ⟶ 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>

==Commitments based on physical unclonable functions==