KZG

KZG (Kate, Zaverucha, Goldberg) is a pairing-based polynomial commitment scheme with trusted setup.

Intuition

Bilinear maps effectively convey the power of multiplicative-homomorphism, but only for one multiplication operation. To be more concrete, let us think of a group element $g^{m_i} ∈ G$ as a commitment to $m_i$ (if $m_i$ is chosen at random, the commitment is computationally hiding if the discrete logarithm problem is hard in $G$, meaning it is hard to determine $m_i$ from $g^{m_i}$). Then bilinear maps allow any party, given commitments $c_1, c_2, c_3$ to check whether the values $m_1, m_2, m_3$ inside the commitments satisfy $m_3 = m_1 · m_2$. This is because by bilinearity of the map $e : G × G → G_t$, $e(g^{m_1} , g^{m_2} ) = e(g^{m_3} , g)$ if and only if $m_3 = m_1 · m_2$.

It turns out that the power to perform a single “multiplication check” of committed values is enough to obtain a polynomial commitment scheme. This is because for any $\text{degree-}D$ univariate polynomial $p$, the assertion $p(z) = v$ is equivalent to the assertion that there exists a polynomial $w$ of degree at most $D − 1$ such that

$$p(X) − v = w(X) · (X − z).$$

This equation can be probabilistically verified by evaluating the two polynomials on the left hand side and right hand side at a randomly chosen point $τ$. This entire approach assumes that the committer does not know $τ$, since if it did, it could choose the polynomial $w$ so that the equation does not hold as an equality of polynomials, but does hold at $τ$.

Protocol Description

Setup

Let $e$ be a bilinear map pairing groups $G$, $G_t$ of prime order $p$, and $g ∈ G$ be a generator, and $D$ be an upper bound on the degree of the polynomials we would like to support commitments to. Let $\tau, \alpha \in F_p$ be two random nonzero field elements. Then SRS (structured reference string) consists of the pairs:

$$\{(g, g^α ), (g^τ , g^{ατ} ), (g^{τ^2}, g^{ατ^2}), . . . , (g^{τ^D}, g^{ατ^D})\}.$$

Note that neither $τ$ nor $α$ are included in the SRS — they are “toxic waste” that must be discarded after the SRS is generated, as any party that knows these quantities can break extractability or binding of the polynomial commitment scheme.

Commit

To commit to a polynomial $q$ over $F_p$, the committer sends a value

$$c = (U, V) = (g^{q(τ)}, g^{\alpha q(τ)}).$$

Note that while the committer does not know $τ$, it is still able to compute $g^{q(τ)}$ using the first elements in pairs in the SRS and additive homomorphism:

$$\text{if } q(Z) = \sum_{i=0}^{D}c_iZ^i \text{, then } g^{q(τ)} = \prod_{i=0}^{D}(g^{\tau^i})^{c_i},$$

which can be computed given the values $g^{τ^i}$ for all $i = 0, . . . , D$ even without knowing $τ$. The commiter can compute $g^{\alpha q(τ)}$ in a similar manner, using second elements in pairs in the SRS, without knowing the value of $\alpha$.

Evaluatuion

To open a commitment $c = (U, V)$ at $z ∈ F_p$ to some value $v$, the committer computes the $\text{degree-}(D − 1)$ polynomial $w(X) := (q(X) − v)/(X − z)$ and sends a value $y$ claimed to equal $w(τ)$. The verifier checks:

$$e(U · g^{−v}, g) = e(y, g^τ · g^{−z}) \\ e(U, g^α ) = e(V, g)$$

This scheme is binding and extractable. You can find security analysis in the subsection 15.2 of "Proofs, Arguments, and Zero-Knowledge". If we omit the "alpha part" (second elements in the SRS, second element of commitment, second verification check), this scheme will be binding to some function but it doesn’t establish that the function the prover is bound to is a $\text{degree-}D$ polynomial.

Complexity

• Setup time: $O(D)$

• Commit time: $O(D)$

• Commit size: $O(1)$

• Evaluation proof time: $O(D\log{D})$

• Evaluation proof size: $O(1)$

• Verify time: $O(1)$

Extension of KZG to Multilinear Polynomials

TBD

Original Paper

https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf