Commitment scheme: Difference between revisions

Revision as of 14:25, 8 November 2023

Revision as of 20:37, 10 November 2023

Line 23:

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 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 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 248 ⟶ 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]], 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 260 ⟶ 261:

However, this is impossible, as Dominic Mayers showed in 1996 (see<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==