Principles and Applications of Cryptographic Commitment

homepage

WeChat public number: password application technology practice
Blogland Home:/informatics/
GIT Address:/warm3snow

synopsis

Polynomial commitment is a more practical cryptographic commitment scheme that allows one party (the committer) to commit the value of a polynomial to another party (the verifier) without revealing the exact form of the polynomial. It has a wide range of applications in the fields of zero-knowledge proofs, verifiable password sharing, etc. Common polynomial commitments include Kate polynomial commitment, FRI polynomial commitment, IPA polynomial commitment, etc. In this paper, we will focus onKate's polynomial commitmentThe construction and application of the

Before reading the following, it is essential to understand the basic cryptographic promises principles and applications, and the reader can refer to the following articles:
Principles and Applications of the Promise of Cryptography - An Overview
Principles and Applications of Cryptographic Commitment - Sigma Commitment.
Principles and Applications of Cryptographic Commitments - Pedersen Commitments.

preamble

polynomial (math.)

Before going into detail about Kate's polynomial commitment, let's briefly introduce the basic concept of polynomials. Polynomials are generally represented as:

\[f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_dx^d = \sum_{i=0}^{d}a_ix^i \]

Of the above polynomials, the\(a_0, a_1, a_2, ..., a_d\)bea polynomial coefficient (math.)，\(x\)is a polynomial in variables.\(d\)is the number of polynomials (or the degree of a polynomial). The number of times of a polynomial is the exponent of the highest power of the polynomial, e.g. the number of times of the above polynomial is\(t\)Therefore, the above\(f(x)\)We also refer to it as dpolynomial of the second order (math.)The Polynomial coefficients\(a_0, a_1, a_2, ..., a_d\)are important components of polynomials, they determine the shape and nature of the polynomials and are important information to protect.

The value of the polynomialis the result of substituting the variable x into a polynomial, for example\(f(\beta)\)represent\(x=\beta\)Substituting into the polynomial, the result is calculated.

root of a polynomialis the point at which the value of the polynomial is zero, i.e.\(f(x) = 0\)The Point.

Polynomials have two important properties:

univariate nth degree polynomialThere are at most n roots, assuming that the root is\(\beta_1, \beta_2, ..., \beta_d\), then the polynomial can be expressed as:\(f(x) = (x-\beta_1)(x-\beta_2)...(x-\beta_d)\)
the quotient polynomial (math.), the polynomial subtracts the value of the polynomial at a point (e.g., the point: <.\(a, f(a)\)>), is divisible by another polynomial calledthe quotient polynomial (math.)The The quotient polynomial is expressed as\(h(x) = \frac{f(x)-f(a)}{x-a}\)

Note: In zero-knowledge proofs, the problem to be proved is usually transformed into a polynomial expression and proved by equating the polynomial with the quotient polynomial.

bilinear map (math.)

In polynomial commitment verification, the concept of bilinear mapping is used.bilinear map (math.)(Bilinear Map) is an important mapping in mathematics, especially in cryptography and number theory with a wide range of applications. It is a special kind of function with the following properties:

define

found\(G\)is a multiplicative cyclic group, the\(g\)is a generating element, the\(G_T\)is another cluster. A mapping\(e: G \times G \rightarrow G_T\)is called a bilinear mapping if the following conditions are satisfied:

bilinear: For any\(a, b \in Z_p\)cap (a poem)\(g, h \in G\)Yes\(e(g^a, h^b) = e(g, h)^{ab}\)
non-degenerative: For any\(g \in G\)，\(e(g, g) \neq 1\)
computability: For any\(g, h \in G\)，\(e(g, h)\)can be computed in polynomial time

Nature of importance：

Exchangeability: for any\(g, h \in G\)，\(e(g, h) = e(h, g)\)
Distributivity: for any\(g, h1, h2 \in G\)，\(e(g, h1 \cdot h2) = e(g, h1) \cdot e(g, h2)\)
\(e(g, g) for G_T\)A generating element of

Multinomial commitments

The main process for polynomial commitments is as follows:

[00] Setup initialization phase: Committers and verifiers share a common reference string CRS
- CRS: common reference string, a publicly available string, typically generated through a trusted third party, used in the construction of polynomial commitments
[01] Commitment phase: Committers calculate polynomial commitments\(C = Commit(CRS, f(α))\)and send\(C\)To the verifier.
- The computation of C depends on the polynomial\(f(x)\)and common reference string CRS
- Note that in polynomial commitment, the degree of the polynomial needs to satisfy\(d \leq t\)which\(t\)is the highest power in the common reference string
[02] Open open stage: Committers reveal polynomials\(f(x)\)
- f(x) is a concrete form of the polynomial, and the committer directly reveals that the polynomial\(f(x)\), such as polynomial parameters and coefficients
[03] VerifyPoly verification phase: the verifier recomputes the polynomial commitment\(C^{'} = Commit(CRS, f(α))\)
- The verifier recomputes the polynomial commitment\(C^{'}\)and validate\(C^{'}\)cap (a poem)\(C\)Are they equal?

The polynomial commitment opening phase of the above approach is explicitly revealed, i.e., the committer directly reveals the polynomial\(f(x)\), the verifier recomputes the polynomial commitment\(C^{'} = Commit(CRS, f(x))\)and validate\(C^{'}\)respond in singing\(C\)Are they equal.
Explicit revelation is simple and straightforward, but suffers from the following problems:

At higher polynomial orders, explicit revelation leads to a higher communication volume
Explicit revelation does not protect polynomials, they must be disclosed

Kate's polynomial commitment

In order to solve the problem ofexplicitly revealProblems with polynomial commitments, Kate polynomial commitments based on polynomialsturn on (light)The polynomial commitment and verification are realized in the manner of theturn on (light)way means that the committer does not directly reveal the polynomials\(f(x)\), but rather to reveal the value of the polynomial at a point\(f(β)\)and provide awitnessProof that the verifier verifies that the polynomial has the correct value at the β-point by a bilinear mapping. By point opening, the Kate polynomial commitment solves the problem of explicit revelation while preserving the privacy of the polynomial.

There are two general schemes for the construction of Kate polynomial commitments, and the two schemes differ in security:

Compute the hidden Kate polynomial commitment: The fact that the value of a promise is computationally hidden means that for any polynomial-time attacker, it is not possible to effectively distinguish between two different promises. In other words, the attacker is computationally incapable of inferring the contents of a promise from the promise.
Unconditionally hidden Kate polynomial commitments: The value of a promise is computationally unconditionally hidden, meaning that for any attacker, it is impossible to infer the content of the promise from the promise.

Definitionally abstract, this simply means that unconditional hiding makes promised values computationally uninferrable by introducing randomness, while computational hiding makes promised values computationally uninferrable by using only discrete logarithmic difficulty assumptions.

Compute the hidden Kate polynomial commitment

Computing the hidden Kate polynomial commitment is constructed as follows.

[00] Setup initialization phase

Kate polynomial commitment requires an initialization phase, mainly generating and exposing CRSs, and bilinear mappings\(e: G \times G \rightarrow G_T\). The CRS in the Kate polynomial commitment is as follows:

\[CRS = (G, g^α, g^{α^2}, ..., g^{α^t}) \]

Among them.\(G\)representing the multiplicative group.\(g\)be\(G\)A generating element of\(α\)is a random number.\(t\)is the highest power. Note: In the zero-knowledge proof, the\(α\)is a private value that is not made public and needs to be securely destroyed (often referred to as toxic waste).

Note: In Kate's paper, the CRS is called a PK, or public key.

[01] Commitment phase

Committers compute the commitment value of a polynomial\(C = Commit(CRS, f(x))\)and send\(C\)to the verifier. The commitment value of a polynomial is computed as follows:

\[C = g^{f(α)} = g^{\sum_{i=0}^{d}{a_iα^i}} = \prod_{i=0}^{d}g^{a_iα^i} = \prod_{i=0}^{d}{(g^{α^i})^{a_i}} \]

\(a_i\)are the coefficients of the polynomial, known to the committer.
The CRS is the common reference string, and the CRS contains the\(g^{α^i}\)value, so the promisor can be used without knowing the value of the\(α\)in the case of the calculation of the\(C\)

[02] CreateWitness point opening stage

Committers compute the value of a polynomial at a point\(f(β)\)and provide a certificate of Witness\(w\)which\(w\)is the commitment of the polynomial at the point β, computed as follows:

First compute the quotient polynomial

\[φ(x) = \frac{f(x) - f(β)}{x - β} = \sum_{i=0}^{d-1}b_ix^i \]

count\(f(x)\)The value at point β

\[f(β) = \sum_{i=0}^{d}a_iβ^i \]

Compute the commitment value of the quotient polynomial at point α

\[w = Commit(CRS, φ(x)) \newline = g^{φ(α)} = g^{\sum_{i=0}^{d-1}{b_iα^i}} \newline = \prod_{i=0}^{d-1}g^{b_iα^i} = \prod_{i=0}^{d-1}{(g^{α^i})^{b_i}} \]

Committers will\((β, f(β), w)\)sent to the verifier.

[03] VerifyEval point verification phase

The verifier uses a bilinear mapping to verify that the polynomial opens correctly at the β-point in the following way:

\[e(C, g) \stackrel{?}{=} e(w, g^{α}/g^{β}) \cdot e(g, g)^{f(β)} \]

Correctness verification:

\[e(w, g^{α}/g^{β}) \cdot e(g, g)^{f(β)} \newline = e(g^{φ(α)}, g^{α-β}) \cdot e(g, g)^{f(β)} \newline = e(g,g)^{φ(α) \cdot (α-β)+f(β)} \]

By the definition of a quotient polynomial, there are:\(f(α) - f(β) = φ(α) \cdot (α-β)\), as a result:

\[e(w, g^{α}/g^{β}) \cdot e(g, g)^{f(β)} \newline = e(g,g)^{f(α)-f(β)+f(β)} \newline = e(g,g)^{f(α)} \newline = e(g^{f(α)}, g) \newline = e(C, g) \]

Therefore.\(e(C, g) = e(w, g^{α}/g^{β}) \cdot e(g, g)^{f(β)}\), validation passes.

Unconditionally hidden Kate polynomial commitments

The unconditionally hidden Kate polynomial commitment construction is similar to the computationally hidden Kate polynomial commitment process, with the difference that:

CRS in the initialization phase is different
Commitment values are generated and validated differently (commitment value generation is based on Pedersen commitments)

initialization phase

The CRS is constructed as follows:

\[CRS = (G, g^α, g^{α^2}, ..., g^{α^t}, h, h^α, h^{α^2}, ..., h^{α^t}) \]

Among them.\(h\)be\(G\)of another generating element.

Commitment phase

Committers compute the commitment value of a polynomial\(C = Commit(CRS, f(x))\)The calculation is as follows:

\[C = g^{f(α)} \cdot h^{\hat{f(α)}} \newline f(α) = \sum_{i=0}^{d}{a_iα^i} \newline \hat{f(α)} = \sum_{i=0}^{d}{b_iα^i} \newline = \prod_{i=0}^{d}{(g^{α^i})^{a_i}} \cdot \prod_{i=0}^{d}{(h^{α^i})^{b_i}} \]

CreateWitness point opening stage

Committers compute the value of a polynomial at a point\(f(β)\)and provide a certificate of Witness\(w\)The calculation is as follows:

the quotient polynomial (math.)

\[φ(x) = \frac{f(x) - f(β)}{x - β} \newline \hat{φ(x)} = \frac{\hat{f(x)} - \hat{f(β)}}{x - β} \]

Calculate the point open value

\[w = Commit(CRS, φ(x)) \cdot Commit(CRS, \hat{φ(x)}) \newline = g^{φ(α)} \cdot h^{\hat{φ(α)}} \]

\(g^{φ(α)}\)cap (a poem)\(h^{\hat{φ(α)}}\)The calculation is based on the CRS (in the same way as above, omitted), and the commitment will be\((β, f(β), \hat{f(β)}, w)\)sent to the verifier.

VerifyEval point validation phase

The verifier uses a bilinear mapping to verify that the polynomial opens correctly at the β-point in the following way:

\[e(C, g) \stackrel{?}{=} e(w, g^{α}/g^{β}) \cdot e(g^{f(β)} \cdot h^{\hat{f(β)}}, g) \]

Correctness verification:

\(h\)be\(G\)is not a group element in the generalizable\(h = g^\lambda\)which\(\lambda\)is a random number. Therefore:

\[e(w, g^{α}/g^{β}) \cdot e(g^{f(β)} \cdot h^{\hat{f(β)}}, g) \newline = e(g^{φ(α)} \cdot h^{\hat{φ(α)}}, g^{α-β}) \cdot e(g^{f(β)} \cdot h^{\hat{f(β)}}, g) \newline = e(g^{φ(α)+\lambda\hat{φ(α)}}, g^{α-β}) \cdot e(g^{f(β)+\lambda\hat{f(β)}}, g) \newline = e(g,g)^{φ(α) \cdot (α-β)+\lambda\hat{φ(α)} \cdot (α-β) + f(β) + \lambda\hat{f(β)}} \newline = e(g,g)^{φ(α) \cdot (α-β)+ f(β) + \lambda \cdot(\hat{φ(α)} \cdot (α-β) + \hat{f(β)})} \]

By the definition of a quotient polynomial, there are:\(f(α) - f(β) = φ(α) \cdot (α-β)\)，\(\hat{f(α)} - \hat{f(β)} = \hat{φ(α)} \cdot (α-β)\), as a result:

\[e(w, g^{α}/g^{β}) \cdot e(g^{f(β)} \cdot h^{\hat{f(β)}}, g) \newline = e(g,g)^{φ(α) \cdot (α-β)+ f(β) + \lambda \cdot(\hat{φ(α)} \cdot (α-β) + \hat{f(β)})} \newline = e(g,g)^{f(α) - f(β)+ f(β) + \lambda \cdot(\hat{f(α)} - \hat{f(β)} + \hat{f(β)})} \newline = e(g,g)^{f(α) + \lambda \cdot \hat{f(α)}} \newline = e(g^{f(α)} \cdot g^{\lambda \cdot \hat{f(α)}}, g) \newline = e(g^{f(α)} \cdot h^{\hat{f(α)}}, g) \newline = e(C, g) \]

Therefore.\(e(C, g) = e(w, g^{α}/g^{β}) \cdot e(g^{f(β)} \cdot h^{\hat{f(β)}}, g)\), validation passes.

concluding remarks

Kate polynomial commitment is a more practical polynomial commitment scheme, which can effectively reduce the amount of communication while preserving polynomial privacy by means of point-opening.Kate polynomial commitment has a wide range of applications in the fields of zero-knowledge proofs, verifiable cryptographic sharing, and so on. Understanding the principle and construction of Kate polynomial commitment is very helpful for learning zero-knowledge proof protocols such as zk-snarks and zk-starks. Through the introduction of this paper, we hope that readers can have a preliminary understanding of Kate polynomial commitment and lay a foundation for further study of zero-knowledge proof protocols.

bibliography

【1】Polynomial Commitment
【2】Non-interactive zero-knowledge proof
【3】Commitment_scheme