KZG

Paper

Constant-Size Commitments to Polynomials and Their Applications
Authors: Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg
Date: 2010

0. Paper vs Practice

Symmetric & Asymmetric Pairing Types

• In the paper, it uses symmetric pairing (Type 1)
  • In practice, asymmetric pairing is used for more efficiency
  • KZG supports both symmetric and asymmetric pairing

Pairing & Bilinear Group

• The most popular family of elliptic curves for pairings is BLS (e.g. BLS12-381)
• Pairing operates over prime order subgroups of composite order curve groups
• Although a bilinear group doesn’t specify an elliptic curve, an elliptic curve is the only method we know of constructing a bilinear group

Additive Notation vs Multiplicative Notation

• KZG commitment actually uses an Elliptic Curve Group, so in reality, it actually uses an additive group, which implies additive notation might be more suitable
• However, the KZG paper uses multiplication notation
• Regardless of the notation, the calculations are actually done by additive rules**

References

• elliptic curves - In the Kate/KZG Polynomial Commitment Scheme, in which Polynomial Ring should the polynomial to be committed be? - Cryptography Stack Exchange
• zero knowledge proofs - What is the difference between those two KZG Polynomial Commitment Schemes? - Cryptography Stack Exchange

---

1. Overview

• Homomorphic CS have a commitment size linear in the degree of the committed polynomial
• KZG is a PCS where
  • Commitments are of constant size (single elements**): $O(1)$ size
  • Opening a commitment is constant time**: $O(1)$ time
  • Opening multiple commitments is also constant time**: $O(1)$ time
• PCS can apply to 4 problems in cryptography:
  1. Verifiable secret sharing
  2. Zero-knowledge sets
  3. Credentials
  4. Content extraction signatures.
• Hiding property based on the DL assumption
• Binding property is proven under the SDH assumption

	Hash	Pedersen	$PolyCommi{t}_{DL}$	$PolyCommi{t}_{DL}$(Batch)	$PolyCommi{t}_{Ped}$	$PolyCommi{t}_{Ped}$ (Batch)
Commitment size	$t$	$t$	$1$	$1$	$1$	$1$
$k$-opening overhead	$0$	$k$ random values	$k$ witnesses	$1\mathbf{witness}$	$k$ random + $k$ witnesses	$k$ random + $1$ witness
Total overhead	$t$	$t+k$	$k+1$	$2$	$k+2$	$k+2$
Total overhead when $k\approx t$	$\approx t$	$\approx 2t$	$\approx t+1$	$2$	$t+2$	$t+2$

Table 1: Comparison of commitment scheme communication overhead. A commitment to $t$ messages is created, then later $k<t$ messages must be revealed.

Commitment Schemes

”Naive” Commitment Scheme

• let $g$ be a random generator of a group $G$ of prime order $p$
• A committer can commit a message $m{\in }_R{\mathbb{Z}}_p$ simply as $C_g(m)=g^m$
• Unconditionally binding
• Computationally hiding under the assumption that the discrete logarithm (DL) problem is hard in $G$

Pedersen Commitment

• Let $g$ and $h$ be two random generators of a group $G$ of prime order $p$
• $C〈g,h〉(m,r)=g^m{h}^r$, where $r{\in }_R{\mathbb{Z}}_p$
• Unconditionally hiding
• Computationally hiding under the assumption that the discrete logarithm (DL) problem is hard in $G$

Collision-Resistant Hash (CRH)

• The committer may publish $H(m)$ or $H(m||r)$ for any one-way function $H$

Hiding - Drawback of the Existing Scheme

• If we commit the string representation of a polynomial, then opening it requires revealing the entire polynomial
• This is not ideal, especially for secret sharing, which requires opening (i.e. calculating $\varphi (i)$ for $i\in {\mathbb{Z}}_p$) to different parties at different points in the protocol
• One solution is to commit the coefficients (e.g. $C=(g^{{\varphi }_0},...,g^{{\varphi }_t}$), but the size of the commitment is now $t+1$ elements of $G$

2. Hardness Assumption

Additional Reference

• KZG Polynomial Commitments | ZKDocs

Discrete logarithm (DL) Assumption

• Hiding property requires this assumption
• Discrete Logarithm Problem (DLP)

t-Diffie-Hellman inversion assumption (t-DHI) assumption

• introduced as a weak Diffie-Hellman assumption by Mitsunari, Sakai and Kasahara but renamed to t-DHI by Boneh and Boyen as it is actually stronger than Diffie-Hellman assumption for large values of $t$

t-polynomial Diffie-Hellman (t-polyDH) Assumption

• a generalization of t-DHI

t-Strong Diffie-Hellman (t-SDH) Assumption

• Binding property requires this assumption
• t-SDH implies computational Diffie-Hellman and DL Assumption
• related to t-DHI but stronger
• has exponentially many non-trivial, acceptable, different solutions

t-Bilinear Strong Diffie-Hellman (t-BSDH) Assumption

• Bilinear version of the t-SDH assumption
• KZG batch opening extension relies on this assumption

3.1. Algorithms

• PCS is composed of the following six algorithms:

Setup$(1^{\kappa },t)$

• generates an appropriate algebraic structure $G$ and a commitment to a public-private key pair $<PK,SK>$ to commit to a polynomial of degree ≤ $t$
• For simplicity, we add $G$ to the public key $PK$
• Setup is run by a trusted or distributed authority
• $SK$ is not required in the rest of the scheme for the given $t$

Commit$(PK,\varphi (x))$

• Outputs a commitment $C$ to a polynomial $\varphi (x)$ for the public key $PK$, and some associated decommitment information d. (In some constructions, d is null.)

Open$(PK,C,\varphi (x),d)$

• Outputs the polynomial $\varphi (x)$ used while creating the commitment, with decommitment information $d$

VerifyPoly$(PK,C,\varphi (x),d)$

• Verify that C is a commitment to $\varphi (x)$, created with decommitment information $d$
• If so, it outputs 1; otherwise, it outputs 0.

CreateWitness$(PK,\varphi (x),i,d)$

• Outputs 〈i, \phi(i), wi〉, where wi is a witness for the evaluation \phi(i) of \phi(x) at the index i and d is the decommitment information.

CreateWitnessBatch$(PK,\varphi (x),B)$

• batched version of **CreateWitness$(PK,\varphi (x),i,d\ast \ast )$

VerifyEval$(PK,C,i,\varphi (i),wi)$

• verifies that $\varphi (i)$ is indeed the evaluation at the index $i$ of the polynomial committed in $C$
• If so, it outputs 1, otherwise, it outputs 0

VerifyEvalBatch$(PK,C,B,r(x),wB)$

• batched version of **VerifyEval$(PK,C,i,\varphi (i),wi\ast \ast )$

3.2. $PolyCommi{t}_{DL}$

• PCS based on the Discrete Log problem
• Key idea:

$$\begin{array}{rl}& \frac{\varphi (x)-\varphi (i)fori\in Zp}{\varphi (x)\in Zp[x]:(x-i)}\\ & \\ & =\frac{\varphi (x)-\varphi (i)}{x-i}\end{array}$$

Setup$(1^K,t)$

Output: PK

1. Computer 2 groups $G$ and $G_T$ of prime order $p$
   • There is a symmetric bilinear pairing $e:G\times G\to G_T$
   • Define bilinear pairing group as $\mathcal{G}=<e,G,G_T>$
2. Choose a generator $g{\in }_{R}G$
3. $SK=\alpha {\in }_R{Z}_p^{\ast }$
4. Generate a $(t+1)$-tuple $<g,g^{\alpha },g^{{\alpha }^2},...,g^{{\alpha }^t}>\in G^{t+1}$
5. $PK=$
   • $<g,g^{\alpha },g^{{\alpha }^2},...,g^{{\alpha }^t}>$ (multiplication notation)
   • $<g,g\alpha ,g{\alpha }^2,...,g{\alpha }^t>$ (addition notation)

Commit$(PK,\varphi (x))$ - Prover

Input: PK, $\varphi (x)$ Output: C

1. $\varphi (\alpha )=\sum _{j=0}^{deg(\varphi )}{\varphi }_j{x}^j\in Z_p[X]$ is a polynomial of degree $\le t$
2. Calculate the commitment $C$:

$$\begin{array}{rl}C& =g^{\varphi (\alpha )}\\ & =\prod _{j=0}^{deg(\varphi )}(g^{{\alpha }^j}{)}^{{\varphi }_j}\\ & =g^{\varphi (0)}\cdot (g^{\alpha }{)}^{\varphi (1)}\cdot (g^{{\alpha }^2}{)}^{\varphi (2)}\cdot ...\cdot (g^{{\alpha }^t}{)}^{\varphi (t)}(multiplicationnotation)\\ & =\varphi (0)(g)+\varphi (1)(g\cdot \alpha )+\varphi (2)(g\cdot {\alpha }^2)+...+\varphi (t)(g\cdot {\alpha }^t)(additionnotation)\end{array}$$

Ensure Degree of Polynomial < Length of PK

• PK has a length of $t+1$
• A polynomial has a maximum degree $t$

Open$(PK,C,\varphi (x))$

Output: $\varphi (x)$

• outputs the committed polynomial $\varphi (x)$

CreateWitness$(PK,\varphi (x),i)$ - Prover

Input: $PK,\varphi (x),i$ Output: proof $w_i$

• compute ${\psi }_i(x)=\frac{\varphi (x)-\varphi (i)}{x-i}$
• compute witness (proof) $w_i$:

$$\begin{array}{rl}{w}_i& =g^{{\psi }_i(\alpha )}\\ & =g^{{\psi }_i(0)}\cdot (g^{\alpha }{)}^{{\psi }_i(1)}\cdot (g^{{\alpha }^2}{)}^{{\psi }_i(2)}\cdot ...\cdot (g^{{\alpha }^t}{)}^{{\psi }_i(t)}(multiplicationnotation)\\ & ={\psi }_i(0)(g)+{\psi }_i(1)(g\cdot \alpha )+{\psi }_i(2)(g\cdot {\alpha }^2)+...+{\psi }_i(t)(g\cdot {\alpha }^t)(additionnotation)\end{array}$$

VerifyPoly$(PK,C,\varphi (x))$ - Verifier

Input: $PK,C,\varphi (x)$ Output: True / False

• Verify the committed polynomial $C\stackrel{?}{=}{g}^{\varphi (\alpha )}$

VerifyEval$(PK,C,i,\varphi (i),wi)$ - Verifier

Input: $PK,C,i,\varphi (i)$, Output: True / False

3.3. $PolyCommi{t}_{Ped}$

• PCS uses a technique similar to Pedersen Commitments

3.4. Features

Homomorphism

• both KZG ($PolyCommi{t}_{DL}$) and $PolyCommi{t}_{Ped}$ are homomorphic

Unconditional Hiding for $PolyCommi{t}_{DL}$

• if $t<deg(\varphi )$ evaluations have been revealed, $PolyCommi{t}_{DL}$ unconditionally hides any unrevealed evaluations

Indistinguishability of Commitments (Randomized)

$PolyCommi{t}_{DL}$

• Given that one wants to commit $(<k_1,m_1>,...,<k_{t+1},m_{t+1}>)$
• When a PCS is randomized, an adversary cannot distinguish commitments to chosen sets of key-value pairs
• for $PolyCommi{t}_{DL}$ to be randomized, set one message $m_i$ to a random value

$PolyCommi{t}_{Ped}$

• is inherently randomized and can be used directly

Trapdoor Commitment

• VerifyEval$(PK,C,i,\varphi (i),wi)$ can be run easily

Batch Opening

• Open multiple evaluations by batching them to reduce computation and communication between the committer and verifier
• KZG - Batch Proofs

Strong Correctness

• It should not be possible to commit to a polynomial of degree greater than $t$
• used for a verifiable secret sharing application