Chapter status: ✅ in good shape ✅

Related puzzles: Puzzle 2 and Puzzle 4

TODO:

• cover Kohrita-Towa variant
• batch proofs for multiple polynomials [GWC19] [BDFG20]
• multivariate polynomials [PST13]
• degree-checks

Polynomial Commitment Schemes

Polynomial commitment schemes play a central role in the design of zk-SNARKs. In this section, we introduce them and present the two KZG schemes, DL-KZG and Ped-KZG.

Make sure to read the chapters about polynomials and standard commitments first.

We recall that given a field $\mathbb{F},$ we let ${\mathbb{F}}_{}^{(\le d)}[X]$ denote the set of all univariate polynomials over $\mathbb{F}$ of degree at most $d.$

Contents

• Generalities
  • Syntax
  • Security
• Informal Description of the KZG Schemes
• The DL-KZG Scheme
  • Description
  • Hiding Security
  • Binding Security
• The Ped-KZG Scheme
  • Description
  • Hiding Security
  • Binding Security
• Discussion
  • Efficiency
  • Trusted Setup
  • Summary of KZG Properties
• Multi-evaluation Proofs
  • Syntax and Security Definition
  • KZG with Multi-evaluation Proofs: Description
  • Security Proof
• A Practical Use Case
• Additional Resources

Generalities

As standard commitment schemes, a polynomial commitment scheme (PC scheme for short) involves two parties, a committer (or prover) and a verifier. It allows the committer to send to the verifier a commitment $C$ to some secret polynomial $p\in {\mathbb{F}}_{}^{(\le d)}[X]$ and later on prove that $p$ evaluates to some specific value $v\in \mathbb{F}$ at input $u\in \mathbb{F}$ (usually of the verifier's choosing), potentially for multiple inputs.

Recall that a polynomial of degree at most $d$ is specified by the tuple $\mathbf{a}=(a_0,\dots ,a_d)\in {\mathbb{F}}^{d+1}$ of coefficients such that $p(X)={\sum }_{i=0}^d{a}_i{X}^i.$ From a broader perspective, a PC scheme can be seen as the combination of a standard commitment scheme over ${\mathbb{F}}^{d+1}$ together with various proof systems for proving assertions about the committed vector $\mathbf{a}.$ In particular, proving that $p(u)=v$ is equivalent to proving that $$\sum _{i=0}^d{a}_i{u}^i=v$$ i.e., proving that the inner product of $\mathbf{a}$ with the vector $(1,u,u^2,\dots ,u^d)$ is equal to $v.$ Other assertions one may want to prove when designing SNARKs are, for example, that $p$ has degree at most $d^{\prime }<d,$ which is equivalent to $a_{d^{\prime }+1}=\cdots =a_d=0,$ or more complex relations about evaluations of $p$ such as ${\sum }_{u\in \mathcal{U}}p(u)=0$ for some subset $\mathcal{U}\subset \mathbb{F}.$

Syntax

More formally, a PC scheme is parameterized by a maximal degree $d\in \mathbb{N}$ (one can think of $d$ as being given as input to all algorithms) and consists of the five following algorithms (the exact syntax can vary slightly in the literature, here we adhere to the syntax of standard commitment schemes):

• a setup algorithm $\mathsf{Setup}$ which on input the security parameter $1^{\lambda }$ returns public parameters¹ $par;$ these parameters implicitly specify some finite field $\mathbb{F};$

• a commitment algorithm $\mathsf{Commit}$ which on input parameters $par$ and a polynomial $p\in {\mathbb{F}}_{}^{(\le d)}[X]$ returns a commitment $C$ and a decommitment $D;$

• a "polynomial" verification algorithm $\mathsf{PolyVerif}$ which on input parameters $par,$ a commitment $C,$ a polynomial $p\in {\mathbb{F}}_{}^{(\le d)}[X],$ and a decommitment $D,$ returns 1 if $D$ is a valid decommitment for $(par,C,p)$ and 0 otherwise;

• a proving algorithm $\mathsf{EvalProve}$ which on input parameters $par,$ a polynomial $p\in {\mathbb{F}}_{}^{(\le d)}[X],$ a decommitment $D,$ and a value $u\in \mathbb{F}$ returns an evaluation $v\in \mathbb{F}$ and a proof $\Pi ;$

• an "evaluation" verification algorithm $\mathsf{EvalVerif}$ which on input parameters $par,$ a commitment $C,$ a pair $(u,v)\in {\mathbb{F}}^2,$ and a proof $\Pi ,$ returns 1 if $\Pi$ is a valid proof that the polynomial committed to by $C$ evaluates to $v$ at input $u,$ and 0 otherwise.

In some cases (in particular for KZG), it might be possible to split the public parameters $par$ into a commitment key $ck$ and a verification key $vk,$ where typically only $ck$ is needed for algorithms $\mathsf{Commit},$ $\mathsf{PolyVerif},$ and $\mathsf{EvalProve}$ and only $vk$ is needed for $\mathsf{EvalVerif}.$

As already hinted, the three algorithms $\mathsf{Setup},$ $\mathsf{Commit},$ and $\mathsf{PolyVerif}$ can be regarded together as a standard commitment scheme with message space ${\mathbb{F}}_{}^{(\le d)}[X]\cong {\mathbb{F}}^{d+1}$ (with $p$ specified by the tuple $(a_0,\dots ,a_d)\in {\mathbb{F}}^{d+1}$ of its coefficients) while $\mathsf{EvalProve}$ and $\mathsf{EvalVerif}$ together form a proof system for statements of the form $p(u)=v.$

As for standard commitment schemes, what we just defined here is the syntax for a non-interactive PC scheme, where the $\mathsf{Setup}$ algorithm is run once and for all and then committing and proving an evaluation of the committed polynomial is non-interactive. More generally, committing and evaluation proving could be interactive.

As always, the scheme must be correct, meaning two things: first, $(\mathsf{Setup},\mathsf{Commit},\mathsf{PolyVerif})$ must be correct as defined for a standard commitment scheme with message space ${\mathbb{F}}^{d+1};$ second, for every security parameter $\lambda ,$ every $d\in \mathbb{N},$ every $p\in {\mathbb{F}}_{}^{(\le d)}[X],$ and every $u\in \mathbb{F},$ the following game capturing the nominal execution of algorithms for evaluation proving must return true with probability 1:

$$\boxed{\begin{array}{rl}& par\leftarrow \mathsf{Setup}(1^{\lambda })\\ & (C,D)\leftarrow \mathsf{Commit}(par,p)\\ & (v,\Pi )\leftarrow \mathsf{EvalProve}(par,p,D,u)\\ & b\leftarrow \mathsf{EvalVerif}(par,C,(u,v),\Pi )\\ & \mathbf{assert}(b=1)\end{array}}$$

Security

Defining security properties for PC schemes is rather subtle. Almost every paper about PC schemes define slightly different sets of security properties depending on the specific application being targeted. Here, we focus on the security properties proposed in the seminal paper about PC schemes [KZG10a], which are also the simplest ones.

First, a PC scheme should be hiding and binding in the standard sense when seen as a commitment to the tuple of coefficients $(a_0,\dots ,a_d)\in {\mathbb{F}}^{d+1}$ defining the polynomial $p.$ Let us the recall the corresponding games, that we call POLY-HIDING and POLY-BINDING for clarity:

$$\boxed{\begin{array}{cc}\begin{array}{l}\text{Game POLY-HIDING:}\\ b{\leftarrow }_{\$}\{0,1\}\\ par\leftarrow \mathsf{Setup}(1^{\lambda })\\ b^{\prime }\leftarrow {\mathsf{A}}^{\text{Commit}}(par)\\ \mathbf{assert}(b=b^{\prime })\end{array}& \begin{array}{l}\text{Oracle Commit(p0,p1):}\\ \mathbf{assert}(\mathrm{deg}(p_0)\le d)\\ \mathbf{assert}(\mathrm{deg}(p_1)\le d)\\ (C,D)\leftarrow \mathsf{Commit}(par,p_b)\\ \mathbf{return}C\end{array}\end{array}}$$

$$\boxed{\begin{array}{l}\text{Game POLY-BINDING:}\\ par\leftarrow \mathsf{Setup}(1^{\lambda })\\ (C,p,D,p^{\prime },D^{\prime })\leftarrow \mathsf{A}(par)\\ \mathbf{assert}(\mathrm{deg}(p)\le d)\wedge (\mathrm{deg}(p^{\prime })\le d)\\ b\leftarrow \mathsf{PolyVerif}(par,C,p,D)\\ b^{\prime }\leftarrow \mathsf{PolyVerif}(par,C,p^{\prime },D^{\prime })\\ \mathbf{assert}(p\ne p^{\prime })\\ \mathbf{assert}(b=1)\\ \mathbf{assert}(b^{\prime }=1)\end{array}}$$

It turns out that some PC schemes (such as the DL-KZG scheme) do not satisfy the poly-hiding notion (in general, when used to construct SNARKs, poly-hiding matters only if one cares about the SNARK being zero-knowledge). However, they satisfy what we call here evaluation hiding,² which informally means that for a random polynomial $p$ of degree at most $d,$ given a commitment to $p$ and at most $d$ evaluations of $p$ together with the corresponding proofs, no adversary should be able to guess the value of $p(u)$ for a new input $u.$ This is formalized by the following game:

$$\boxed{\begin{array}{cc}\begin{array}{l}\text{Game EVAL-HIDING:}\\ p(X){\leftarrow }_{\$}{\mathbb{F}}_{}^{(\le d)}[X]\\ ctr\leftarrow 0\\ \mathcal{Q}\leftarrow \varnothing \\ par\leftarrow \mathsf{Setup}(1^{\lambda })\\ (C,D)\leftarrow \mathsf{Commit}(par,p)\\ (u,v)\leftarrow {\mathsf{A}}^{\text{Prove}}(par,C)\\ \mathbf{assert}(ctr\le d)\\ \mathbf{assert}(u\notin \mathcal{Q})\\ \mathbf{assert}(p(u)=v)\end{array}& \begin{array}{l}\text{Oracle Prove(u):}\\ (v,\Pi )\leftarrow \mathsf{EvalProve}(par,p,D,u)\\ ctr\leftarrow ctr+1\\ \mathcal{Q}\leftarrow \mathcal{Q}\cup \{u\}\\ \mathbf{return}(v,\Pi )\\ \\ \\ \\ \\ \end{array}\end{array}}$$

To be completely explicit, the line $$p(X){\leftarrow }_{\$}{\mathbb{F}}_{}^{(\le d)}[X]$$ means $$\begin{array}{rl}& a_0,\dots ,a_d{\leftarrow }_{\$}\mathbb{F}\\ & p(X):=\sum _{i=0}^d{a}_i{X}^i.\end{array}$$

The condition that the adversary makes at most $d$ queries to the $\text{Prove}$ oracle is of course necessary: once the commitment has been opened at $d+1$ distinct points $u_0,$ $\dots ,$ $u_d,$ the committed polynomial has been completely revealed by virtue of Lagrange interpolation.

Regarding the binding property of evaluation proving, a PC scheme should be evaluation binding, meaning no efficient adversary can produce a commitment and two valid proofs that the committed polynomial evaluates to two different values $v\ne v^{\prime }$ at the same input $u.$ More formally, this is captured by the following game:

$$\boxed{\begin{array}{l}\text{Game EVAL-BINDING:}\\ par\leftarrow \mathsf{Setup}(1^{\lambda })\\ (C,u,(v,\Pi ),(v^{\prime },{\Pi }^{\prime }))\leftarrow \mathsf{A}(par)\\ b\leftarrow \mathsf{EvalVerif}(par,C,(u,v),\Pi )\\ b^{\prime }\leftarrow \mathsf{EvalVerif}(par,C,(u,v^{\prime }),{\Pi }^{\prime })\\ \mathbf{assert}(v\ne v^{\prime })\\ \mathbf{assert}(b=1)\\ \mathbf{assert}(b^{\prime }=1)\end{array}}$$

As for standard commitments, all these properties can hold statistically or computationally, but poly-hiding and poly-binding cannot hold both statistically for a PC scheme.

Informal Description of the KZG Schemes

Two closely related and very efficient PC schemes based on pairings were proposed by Kate, Zaverucha, and Goldberg in 2010 [KZG10a] (see also [KZG10b] for the full paper with security proofs). We will call them (for reasons that will become clear soon) DL-KZG and Ped-KZG. What is usually simply called KZG corresponds to the DL-KZG scheme.

Let us start with a high-level view of DL-KZG. For a maximal degree $d,$ the commitment and opening part is very similar to the (non-hiding version of the) generalized Pedersen commitment scheme. The public parameters consist of $d+1$ generators $(W_0,\dots ,W_d)$ of some group ${\mathbb{G}}_1$ of prime order $r.$ A polynomial $p(X)={\sum }_{i=0}^d{a}_i{X}^i$ is seen as a vector $(a_0,\dots ,a_d)\in ({\mathbb{F}}_r{)}^{d+1}$ and the corresponding commitment is $$C:=\sum _{i=0}^d{a}_i{W}_i.$$ There is a big difference though with generalized Pedersen commitments: the generators $W_0,\dots ,W_d$ are not independent. They are computed from a single generator $G_1\in {\mathbb{G}}_1$ and a secret random scalar $\tau \in {\mathbb{F}}_r$ as $$(W_0,W_1,\dots ,W_d)=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1).$$ These parameters have a precise structure. For this reason, they are also called a structured reference string (SRS). This also implies that they cannot be sampled obliviously of $\tau$ and require a trusted setup (more on this later).

As a result, the commitment $C$ is actually $p(\tau )$ in disguise: $$C=\sum _{i=0}^d{a}_i({\tau }^i{G}_1)=\left(\sum _{i=0}^d{a}_i{\tau }^i\right)G_1=p(\tau )G_1.$$

Evaluation proving relies on the polynomial remainder theorem: a polynomial $p\in \mathbb{F}[X]$ satisfies $p(u)=v$ if and only if $p(X)-v$ is divisible by $X-u,$ i.e., there exists a polynomial $q$ such that $$p(X)-v=(X-u)q(X).$$ The proving algorithm therefore consists in computing the polynomial $q(X)={\sum }_{i=0}^d{b}_i{X}^i$ explicitly and the proof $\Pi ,$ which consists in $q(\tau )$ in disguise, as $$\Pi :=\sum _{i=0}^d{b}_i({\tau }^i{G}_1)=q(\tau )G_1.$$

Evaluating this polynomial equality at $\tau ,$ we see that $$p(\tau )-v=(\tau -u)q(\tau ).$$ The verification algorithm consists in checking this equality "in the exponent" (or rather "in the scalar multiplication" here as we use additive notation). This is where pairings comes in: ${\mathbb{G}}_1$ is actually a pairing-friendly group coming with related groups ${\mathbb{G}}_2$ and ${\mathbb{G}}_t$ and a pairing $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_t.$ The public parameters include a generator $G_2$ of ${\mathbb{G}}_2$ and the group element $H_2=\tau G_2.$ The verifier can compute $(p(\tau )-v)G_1=C-v{G}_1$ and $(\tau -u)G_2=H_2-u{G}_2$ and also knows $\Pi =q(\tau )G_1.$ Then $p(\tau )-v=(\tau -u)q(\tau )$ holds iff the following pairing equality does: $$e(C-v{G}_1,G_2)=e(\Pi ,H_2-u{G}_2).$$

The DL-KZG commitment scheme is obviously not hiding because the commitment algorithm is deterministic. The Ped-KZG scheme remedies this problem by adding a commitment to a random polynomial $\hat{p}={\sum }_{i=0}^d{\hat{a}}_i{X}^i$ with respect to another tuple of points $(H_1,\tau H_1,\dots ,{\tau }^d{H}_1):$ $$C=\sum _{i=0}^d{a}_i({\tau }^i{G}_1)+\sum _{i=0}^d{\hat{a}}_i({\tau }^i{H}_1)=p(\tau )G_1+\hat{p}(\tau )H_1.$$ Evaluation proving is adapted accordingly. The form of the commitment $C$ is reminiscent of the (hiding version) of Pedersen commitments, explaining the naming convention.

We now give a detailed description and analysis of the properties of the DL-KZG and Ped-KZG schemes.

The DL-KZG Scheme

Description

Let $\mathsf{PairingSetup}$ be an asymmetric pairing group setup algorithm.³ The DL-KZG scheme for a maximal degree $d$ is defined as follows:

• The $\mathsf{Setup}$ algorithm, on input the security parameter $1^{\lambda },$ runs $$({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)\leftarrow \mathsf{PairingSetup}(1^{\lambda }),$$ draws random generators $G_1$ and $G_2$ of respectively ${\mathbb{G}}_1$ and ${\mathbb{G}}_2,$ draws $\tau {\leftarrow }_{\$}{\mathbb{F}}_r,$ and returns public parameters $$par:=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,G_2,\tau G_2)\in {\mathbb{G}}_1^{d+1}\times {\mathbb{G}}_2^2.$$ Here we assume that pairing parameters $({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)$ are implicitly specified in $par.$⁴ The field over which polynomials are defined is ${\mathbb{F}}_r.$ The public parameters can be split into a commitment key $$ck:=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1)\in {\mathbb{G}}_1^{d+1}$$ and a verification key $$vk:=(G_1,G_2,\tau G_2)\in {\mathbb{G}}_1\times {\mathbb{G}}_2^2.$$

• The $\mathsf{Commit}$ algorithm, on input a commitment key $ck=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1)$ and a polynomial $p\in {\mathbb{F}}_r^{(\le d)}[X]$ where $p(X)={\sum }_{i=0}^d{a}_i{X}^i,$ returns the commitment $$C:=\sum _{i=0}^d{a}_i({\tau }^i{G}_1)=p(\tau )G_1$$ and an empty decommitment $D=\perp .$

• The $\mathsf{PolyVerif}$ algorithm, on input a commitment key $ck=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1),$ a commitment $C\in {\mathbb{G}}_1,$ and a polynomial $p\in {\mathbb{F}}_r^{(\le d)}[X]$ where $p(X)={\sum }_{i=0}^d{a}_i{X}^i,$ returns 1 if $C={\sum }_{i=0}^d{a}_i({\tau }^i{G}_1)$ and 0 otherwise.

• The $\mathsf{EvalProve}$ algorithm, on input a commitment key $ck=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1),$ a polynomial $p\in {\mathbb{F}}_r^{(\le d)}[X],$ and $u\in {\mathbb{F}}_r,$ computes the polynomial⁵ $$q(X):=\frac{p(X)-p(u)}{X-u}=\sum _{i=0}^d{b}_i{X}^i,$$ the group element $$\Pi :=\sum _{i=0}^d{b}_i({\tau }^i{G}_1)=q(\tau )G_1,$$ and returns $p(u)$ and the proof $\Pi .$

• The $\mathsf{EvalVerif}$ algorithm, on input a verification key $vk=(G_1,G_2,\tau G_2),$ a commitment $C,$ a pair $(u,v)\in {\mathbb{F}}_r^2,$ and a proof $\Pi ,$ returns 1 if $$e(C-v{G}_1,G_2)=e(\Pi ,\tau G_2-u{G}_2)\text{\hspace{1em}(19.1)}$$ and 0 otherwise.

It is straightforward to verify that $(\mathsf{Setup},\mathsf{Commit},\mathsf{PolyVerif})$ is correct as a standard commitment scheme. Let's check that the scheme is correct with respect to evaluation proving, i.e., if the commitment $C$ and the proof $\Pi$ have been honestly computed, then the verification passes. If $C=p(\tau )G_1$ and $\Pi =q(\tau )G_1$ where $p(X)$ and $q(X)$ are such that $$p(X)-v=(X-u)q(X),$$ then $$\begin{array}{rl}e(C-v{G}_1,G_2)& =e((p(\tau )-v)G_1,G_2)\\ & =e((\tau -u)q(\tau )G_1,G_2)\\ & =e(q(\tau )G_1,(\tau -u)G_2)\\ & =e(\Pi ,\tau G_2-u{G}_2),\end{array}$$ hence Eq. (19.1) is satisfied and $\mathsf{EvalVerif}$ returns 1.

Hiding Security

The DL-KZG scheme as described above is not poly-hiding: the commitment algorithm $\mathsf{Commit}$ is deterministic, hence, given two polynomials $p_0$ and $p_1$ and a commitment $C,$ it is trivial to distinguish whether $C$ commits to $p_0$ and $p_1$ by computing the corresponding commitments and comparing with $C.$

Regarding the eval-hiding property, note that DL-KZG cannot be statistically eval-hiding. Indeed, an unbounded adversary can compute $\tau$ from the parameters and $p(\tau )$ from the commitment and return $(\tau ,p(\tau ))$ to win the EVAL-HIDING game without making any query to the $\text{Prove}$ oracle. However, it is eval-hiding under the discrete logarithm assumption (in group ${\mathbb{G}}_1).$

Let us give the intuition before the full-fledged proof. As the committed polynomial is uniformly random in ${\mathbb{F}}_r^{(\le d)}[X],$ Lagrange interpolation ensures that given at most $d$ evaluations of $p$ at $u_1,\dots ,u_d,$ the value of $p$ on any other point $u\notin \{u_1,\dots ,u_d\}$ is uniformly random so that even an unbounded adversary can guess it with probability at most $1/\left|{\mathbb{F}}_r\right|.$ Hence, the only way an adversary can guess $p(u)$ with non-negligible probability is to compute $p(\tau )$ from $C=p(\tau )G_1.$ Together with $d$ queries to the $\text{Prove}$ oracle, this yields $d+1$ evaluations of $p,$ allowing to compute $p$ with Lagrange interpolation. But computing $p(\tau )$ requires to solve the discrete logarithm problem for challenge $C.$

Theorem 19.1. Assume that the DL problem is hard in ${\mathbb{G}}_1$ for $\mathsf{PairingSetup}.$ Then the DL-KZG scheme is (computationally) eval-hiding. More precisely, for every adversary $\mathsf{A}$ against the EVAL-HIDING game, there exists an adversary $\mathsf{B}$ for the DL problem running in time $t+O(\lambda d^2),$ where $t$ is the running time of $\mathsf{A},$ and such that $${\mathbf{Adv}}_{\mathsf{A}}^{\text{eval-hiding}}(\lambda )\le {\mathbf{Adv}}_{\mathsf{B}}^{\text{dl}}(\lambda )+\frac{1}{2^{2\lambda -1}}.$$

Proof

Let $\mathsf{A}$ be an adversary against the eval-hiding property of DL-KZG. Without loss of generality, we assume that $\mathsf{A}$ makes exactly $d$ queries to the $\text{Prove}$ oracle. We simply denote EH the EVAL-HIDING game. Let also $E$ denote the event that $\mathsf{A}$ queries the $\text{Prove}$ oracle on $\tau .$ By definition of the advantage, we have $$\begin{array}{rl}{\mathbf{Adv}}_{\mathsf{A}}^{\text{eval-hiding}}(\lambda )& =\mathrm{Pr}\left[\text{EH}\to \mathbf{true}\right]\\ & =\mathrm{Pr}\left[\text{EH}\to \mathbf{true}\mid E\right]\mathrm{Pr}\left[E\right]+\mathrm{Pr}\left[\text{EH}\to \mathbf{true}\mid \neg E\right]\mathrm{Pr}\left[\neg E\right]\\ & \le \mathrm{Pr}\left[\text{EH}\to \mathbf{true}\mid E\right]+\mathrm{Pr}\left[\text{EH}\to \mathbf{true}\mid \neg E\right]\mathrm{Pr}\left[\neg E\right].\end{array}$$ Let us first show that the first term is negligible. Just before $\mathsf{A}$ returns its answer, $p$ has been evaluated on at most $d+1$ points: $\tau$ (when computing the commitment) and the $d$ queries $\{u_1,\dots ,u_d\}$ of $\mathsf{A}$ to the $\text{Prove}$ oracle. Conditioned on $\mathsf{A}$ querying $\text{Prove}$ on $\tau$ (i.e., $\tau \in \{u_1,\dots ,u_d\}),$ $p$ has been in fact evaluated on $d$ points before $\mathsf{A}$ returns its output $(u,v).$ Since $p$ is a random polynomial of degree $d,$ the value of $p(u)$ conditioned on these at most $d$ evaluations (for any $u\ne u_1,\dots ,u_d)$ is uniformly random. Hence, even a computationally unbounded adversary can guess $p(u)$ with probability at most $1/\left|{\mathbb{F}}_r\right|,$ i.e., $$\mathrm{Pr}\left[\text{EH}\to \mathbf{true}\mid E\right]=\frac{1}{\left|{\mathbb{F}}_r\right|}\le \frac{1}{2^{2\lambda -1}}.$$ Let us now upper bound the second term with a reduction. We construct an adversary $\mathsf{B}$ that solves the DL problem by simulating game EH to $\mathsf{A}$ as follows. Let $C=c{G}_1\in {\mathbb{G}}_1$ be the DL instance that $\mathsf{B}$ must solve. $\mathsf{B}$ draws $\tau {\leftarrow }_{\$}{\mathbb{F}}_r,$ computes $$par:=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,G_2,\tau G_2),$$ and runs $\mathsf{A}$ on input $(par,C).$ Note that $C$ implicitly commits to a polynomial $p$ such that $p(\tau )=c.$ $\mathsf{B}$ simulates the $\text{Prove}$ oracle as follows: when $\mathsf{A}$ queries the oracle on some field element $u\in {\mathbb{F}}_r\setminus \{\tau \},$ $\mathsf{B}$ draws $v{\leftarrow }_{\$}{\mathbb{F}}_r,$ computes a proof $$\Pi :=\frac{1}{\tau -u}(C-v{G}_1)$$ and returns $(v,\Pi ).$ The proof is valid because $$\begin{array}{rl}e(\Pi ,\tau G_2-u{G}_2)& =e((\tau -u{)}^{-1}(C-v{G}_1),(\tau -u)G_2)\\ & =e(C-v{G}_1,G_2)\end{array}$$ and hence the verification equation (19.1) is satisfied. Note that $\mathsf{B}$ cannot answer this way if $\mathsf{A}$ queries $\tau$ to $\text{Prove}$ since $p(\tau )$ is exactly the solution to its DL challenge. In such a case (i.e., when $E$ happens), $\mathsf{B}$ simply aborts. Conditioned on $E$ not happening, $p$ is sampled through the commitment evaluation $p(\tau )=c$ and the $d$ evaluations $\{(u_1,v_1),\dots ,(u_d,v_d)\}$ corresponding to $\text{Prove}$ queries made by $\mathsf{A},$ with $c$ and $v_1,\dots ,v_d$ uniformly random and independent. By Lagrange interpolation, this is equivalent to drawing the $d+1$ coefficients of $p$ uniformly at random and hence the EVAL-HIDING game is perfectly simulated. If $\mathsf{A}$ successfully returns a pair $(u,v)$ such that $p(u)=v,$ then $\mathsf{B}$ can interpolate the $d$ evaluations corresponding to $\text{Prove}$ queries together with $(u,v)$ to recover polynomial $p$ and compute $p(\tau )=c,$ which yields the solution to the DL challenge.

Let DL be the discrete logarithm game played with $\mathsf{B}.$ Then $$\begin{array}{rl}{\mathbf{Adv}}_{\mathsf{B}}^{\text{dl}}(\lambda )& =\mathrm{Pr}\left[\text{DL}\to \mathbf{true}\right]\\ & =\mathrm{Pr}\left[\text{DL}\to \mathbf{true}\mid E\right]\mathrm{Pr}\left[E\right]+\mathrm{Pr}\left[\text{DL}\to \mathbf{true}\mid \neg E\right]\mathrm{Pr}\left[\neg E\right]\\ & =\mathrm{Pr}\left[\text{DL}\to \mathbf{true}\mid \neg E\right]\mathrm{Pr}\left[\neg E\right]\\ & =\mathrm{Pr}\left[\text{EH}\to \mathbf{true}\mid \neg E\right]\mathrm{Pr}\left[\neg E\right]\end{array}$$ where for the last equality we used that conditioned on $\neg E,$ games DL${}^{\mathsf{B}}(\lambda )$ and EH${}^{\mathsf{A}}(\lambda )$ are identical. Hence, $${\mathbf{Adv}}_{\mathsf{A}}^{\text{eval-hiding}}(\lambda )\le {\mathbf{Adv}}_{\mathsf{B}}^{\text{dl}}(\lambda )+\frac{1}{2^{2\lambda -1}}$$ $\mathsf{B}$ runs in time $t$ (where $t$ is the running time of $\mathsf{A})$ plus the time to interpolate $p,$ which requires at most $O(d^2{\log }_2(r))=O(\lambda d^2)$ operations.

Binding Security

The only thing that a commitment $C$ commits to, information-theoretically speaking, is the value $p(\tau ).$ Hence, the DL-KZG scheme is certainly not statistically poly-binding: an adversary able to compute $\tau$ from the public parameters can very easily decommit any commitment $C=c{G}_1$ to any polynomial $p$ such that $p(\tau )=c.$ However, for an adversary unable to compute $\tau$ from the public parameters, which is an instance of what we call the $(d,1)$-co-DL problem, there is only a negligible chance that it can find two polynomials $p$ and $q$ such that $p(\tau )G_1=q(\tau )G_1=C.$ More formally, we have the following result.

Theorem 19.2. Assume that the $(d,1)$-co-DL problem is hard for $\mathsf{PairingSetup}.$ Then the DL-KZG scheme for maximal degree $d$ is poly-binding. More precisely, for any adversary $\mathsf{A}$ against the poly-binding security of DL-KZG for maximal degree $d,$ there exists an adversary $\mathsf{B}$ for the $(d,1)$-co-DL problem running in time $t+O(\lambda d^3),$ where $t$ is the running time of $\mathsf{A},$ and such that $${\mathbf{Adv}}_{\mathsf{A}}^{\text{poly-binding}}(\lambda )={\mathbf{Adv}}_{\mathsf{B}}^{\text{(d,1)-co-dl}}(\lambda ).$$

Proof

Let $\mathsf{A}$ be an adversary against the poly-binding security of DL-KZG for maximal degree $d.$ We construct an algorithm $\mathsf{B}$ for the $(d,1)$-co-DL problem as follows. $\mathsf{B}$ gets pairing group parameters $({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)$ and an instance $(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,G_2,\tau G_2)$ of the $(d,1)$-co-DL problem. The goal of $\mathsf{B}$ is to compute $\tau .$ It runs $\mathsf{A}$ on public parameters $$par=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,G_2,\tau G_2).$$ Assume that $\mathsf{A}$ is successful and returns a commitment $C$ and two distinct polynomials $p$ and $p^{\prime }$ of degree at most $d$ such that $$\mathsf{PolyVerif}(par,C,p)=\mathsf{PolyVerif}(par,C,p^{\prime })=1.$$ This implies that $C=p(\tau )G_1=p^{\prime }(\tau )G_1,$ hence $p(\tau )=p^{\prime }(\tau )$ and $\tau$ is a root of the non-zero polynomial $(p-p^{\prime })(X)\in {\mathbb{F}}_r^{(\le d)}[X].$ This polynomial can be factored in time $O(d^3\log (r))$ with the Cantor–Zassenhaus algorithm, which allows $\mathsf{B}$ to compute all its roots and find $\tau .$ The success probability of $\mathsf{B}$ is the same as the one of $\mathsf{A}$ and the running time of $\mathsf{B}$ is $t+O(\lambda d^3).$

Eval-binding security relies on a stronger assumption, namely that the so-called $(q_1,q_2)$-strong Diffie-Hellman ($(q_1,q_2)$-SDH) problem is hard. This problem is as follows: given $$(G_1,x{G}_1,\dots x^{q_1}{G}_1,G_2,x{G}_2,\dots ,x^{q_2}{G}_2)\in {\mathbb{G}}_1^{q_1+1}\times {\mathbb{G}}_2^{q_2+1},$$ compute a pair $(a,Y)\in {\mathbb{F}}_r\times {\mathbb{G}}_1$ such that $Y=\frac{1}{x+a}{G}_1.$ The $(q,1)$-SDH problem is usually simply called the $q$-SDH problem.

Theorem 19.3. Assume that the $d$-SDH problem is hard for $\mathsf{PairingSetup}.$ Then the DL-KZG scheme for maximal degree $d$ is eval-binding. More precisely, for any adversary $\mathsf{A}$ against the eval-binding security of DL-KZG for maximal degree $d,$ there exists an adversary $\mathsf{B}$ for the $d$-SDH problem running in time similar to the time of $\mathsf{A}$ and such that $${\mathbf{Adv}}_{\mathsf{A}}^{\text{eval-binding}}(\lambda )={\mathbf{Adv}}_{\mathsf{B}}^{\text{d-sdh}}(\lambda ).$$

Proof

Let $\mathsf{A}$ be an adversary against the eval-binding security of the DL-KZG scheme for maximal degree $d.$ We construct an adversary $\mathsf{B}$ for the $d$-SDH problem. $\mathsf{B}$ gets pairing group parameters $({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)$ and an instance $(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,G_2,\tau G_2)$ of the $d$-SDH problem. The goal of $\mathsf{B}$ is to return a pair $(a,Y)$ such that $Y=\frac{1}{\tau +a}{G}_1.$ It runs $\mathsf{A}$ on public parameters $$par=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,G_2,\tau G_2).$$ Assume that $\mathsf{A}$ is successful and returns a commitment $C,$ a field element $u\in {\mathbb{F}}_r,$ and two valid value/proof pairs $(v,\Pi )$ and $(v^{\prime },{\Pi }^{\prime })$ with $v\ne v^{\prime }.$ Then $\mathsf{B}$ proceeds as follows. First, it checks whether $u=\tau$ (e.g., by checking whether $u{G}_1$ is equal to the second group element of the parameters $par).$ If this is the case, then $\mathsf{B}$ simply picks an arbitrary element $a\in {\mathbb{F}}_r\setminus \{-\tau \}$ and returns $(a,\frac{1}{\tau +a}{G}_1).$ From now on, we assume $u\ne \tau .$ The validity of the two proofs imply that $$\begin{array}{rl}e(C-v{G}_1,G_2)& =e(\Pi ,\tau G_2-u{G}_2)\\ \text{and }e(C-v^{\prime }{G}_1,G_2)& =e({\Pi }^{\prime },\tau G_2-u{G}_2).\end{array}$$ Taking the inverse of the second equation and multiplying with the first equation, we get successively $$\begin{array}{rl}e(C-v{G}_1,G_2)e(C-v^{\prime }{G}_1,G_2{)}^{-1}& =e(\Pi ,(\tau -u)G_2)e({\Pi }^{\prime },(\tau -u)G_2{)}^{-1}\\ e(C-v{G}_1,G_2)e(-C+v^{\prime }{G}_1,G_2)& =e(\Pi ,(\tau -u)G_2)e(-{\Pi }^{\prime },(\tau -u)G_2)\\ e(C-v{G}_1-C+v^{\prime }{G}_1,G_2)& =e(\Pi -{\Pi }^{\prime },(\tau -u)G_2)\\ e((v^{\prime }-v)G_1,G_2)& =e(\Pi -{\Pi }^{\prime },(\tau -u)G_2)\\ e\left(\frac{1}{\tau -u}{G}_1,G_2\right)& =e\left(\frac{1}{v^{\prime }-v}(\Pi -{\Pi }^{\prime }),G_2\right),\end{array}$$ where for the last implication we used that $v^{\prime }-v\ne 0$ and $\tau -u\ne 0,$ which allows us to multiply by $(v^{\prime }-v{)}^{-1}(\tau -u{)}^{-1}\mathrm{mod}r.$ The last equation implies that $$Y:=\frac{1}{v^{\prime }-v}(\Pi -{\Pi }^{\prime })=\frac{1}{\tau -u}{G}_1.$$ Hence, $\mathsf{B}$ returns $(-u,Y)$ which is a valid solution of the SDH instance. The success probability of $\mathsf{B}$ is the same as the one of $\mathsf{A}$ and the running time of $\mathsf{B}$ is close to the one of $\mathsf{A}.$

The Ped-KZG Scheme

Description

As discussed in the previous section, the DL-KZG scheme is not poly-hiding because the $\mathsf{Commit}$ algorithm is deterministic. It is possible the make the scheme poly-hiding by randomizing the $\mathsf{Commit}$ algorithm. Below we present the Ped-KZG scheme. The idea is to add to the basic DL-KZG commitment $C=p(\tau )G_1$ a commitment to another random and independent polynomial $\hat{p}(X)$ with respect to another generator $H_1$ of ${\mathbb{G}}_1.$ The commitment becomes $p(\tau )G_1+\hat{p}(\tau )H_1,$ which is very similar to a Pedersen commitment, hence the name. This requires expanding the size of the public parameters and the evaluation proofs. The formal description follows.

• The $\mathsf{Setup}$ algorithm, on input the security parameter $1^{\lambda },$ runs $$({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)\leftarrow \mathsf{PairingSetup}(1^{\lambda }),$$ draws random generators $G_1$ and $H_1$ of ${\mathbb{G}}_1$ and $G_2$ of ${\mathbb{G}}_2,$ draws $\tau {\leftarrow }_{\$}{\mathbb{F}}_r,$ and returns public parameters $$par:=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,H_1,\tau H_1,\dots ,{\tau }^d{H}_1,G_2,\tau G_2)\in {\mathbb{G}}_1^{2d+2}\times {\mathbb{G}}_2^2.$$ Here we assume that pairing parameters $({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)$ are implicitly specified in $par.$ The field over which polynomials are defined is ${\mathbb{F}}_r.$ The public parameters can be split into a commitment key $$ck:=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,H_1,\tau H_1,\dots ,{\tau }^d{H}_1)\in {\mathbb{G}}_1^{2d+2}$$ and a verification key $$vk:=(G_1,H_1,G_2,\tau G_2)\in {\mathbb{G}}_1^2\times {\mathbb{G}}_2^2.$$

• The $\mathsf{Commit}$ algorithm, on input a commitment key $ck$ and a polynomial $p\in {\mathbb{F}}_r^{(\le d)}[X]$ where $p(X)={\sum }_{i=0}^d{a}_i{X}^i,$ draws a random polynomial $\hat{p}(X)={\sum }_{i=0}^d{\hat{a}}_i{X}^i$ with ${\hat{a}}_0,\dots ,{\hat{a}}_d{\leftarrow }_{\$}{\mathbb{F}}_r$ and returns the commitment $$C:=\sum _{i=0}^d{a}_i({\tau }^i{G}_1)+\sum _{i=0}^d{\hat{a}}_i({\tau }^i{H}_1)=p(\tau )G_1+\hat{p}(\tau )H_1$$ and the decommitment $D=\hat{p}(X).$

• The $\mathsf{PolyVerif}$ algorithm, on input a commitment key $ck,$ a commitment $C\in {\mathbb{G}}_1,$ a polynomial $p\in {\mathbb{F}}_r^{(\le d)}[X]$ where $p(X)={\sum }_{i=0}^d{a}_i{X}^i,$ and a decommitment $\hat{p}\in {\mathbb{F}}_r^{(\le d)}[X]$ where $\hat{p}(X)={\sum }_{i=0}^d{\hat{a}}_i{X}^i,$ returns 1 if $C={\sum }_{i=0}^d{a}_i({\tau }^i{G}_1)+{\sum }_{i=0}^d{\hat{a}}_i({\tau }^i{H}_1)$ and 0 otherwise.

• The $\mathsf{EvalProve}$ algorithm, on input a commitment key $ck,$ a polynomial $p\in {\mathbb{F}}_r^{(\le d)}[X],$ a decommitment $\hat{p}\in {\mathbb{F}}_r^{(\le d)}[X],$ and $u\in {\mathbb{F}}_r,$ computes the polynomials $$\begin{array}{rl}q(X)& :=\frac{p(X)-p(u)}{X-u}=\sum _{i=0}^d{b}_i{X}^i,\\ \hat{q}(X)& :=\frac{\hat{p}(X)-\hat{p}(u)}{X-u}=\sum _{i=0}^d{\hat{b}}_i{X}^i,\end{array}$$ the group element $$\Pi :=\sum _{i=0}^d{b}_i({\tau }^i{G}_1)+\sum _{i=0}^d{\hat{b}}_i({\tau }^i{H}_1)=q(\tau )G_1+\hat{q}(\tau )H_1,$$ and returns $p(u)$ and the proof $(\hat{p}(u),\Pi ).$

• The $\mathsf{EvalVerif}$ algorithm, on input a verification key $vk=(G_1,H_1,G_2,\tau G_2),$ a commitment $C,$ a pair $(u,v)\in {\mathbb{F}}_r^2,$ and a proof $(\hat{v},\Pi ),$ returns 1 if $$e(C-v{G}_1-\hat{v}{H}_1,G_2)=e(\Pi ,\tau G_2-u{G}_2)\text{\hspace{1em}(19.2)}$$ and 0 otherwise.

Correctness can be verified in a similar way to DL-KZG.

Hiding Security

Thanks to the commitment randomization, poly-hiding and eval-hiding security both hold statistically for Ped-KZG.

Theorem 19.4. The Ped-KZG scheme is perfectly poly-hiding.

Proof

For any $\tau \in {\mathbb{F}}_r$ and any polynomial $p\in {\mathbb{F}}_r^{(\le d)}[X],$ the commitment $C$ returned by the $\mathsf{Commit}$ algorithm is uniformly random in ${\mathbb{G}}_1$ due to the addition of the term $\hat{p}(\tau ).$ Hence, the $\text{Commit}$ oracle in the POLY-HIDING game does not reveal any information about the hidden bit $b.$

Theorem 19.5. The Ped-KZG scheme is statistically eval-hiding. More precisely, for any adversary $\mathsf{A},$ one has $${\mathbf{Adv}}_{\mathsf{A}}^{\text{eval-hiding}}\le \frac{1}{2^{2\lambda -1}}.$$

Proof

Let $\mathsf{A}$ by a (computationally unbounded) adversary against the eval-hiding property of Ped-KZG. We can assume without loss of generality that $\mathsf{A}$ is given $\tau ,$ the discrete logarithm $h$ of $H_1$ in base $G_1,$ and the discrete logarithm $c=p(\tau )+h\hat{p}(\tau )$ of the challenge commitment $C.$ Let u_i_, $i\in \{1,\dots ,d\}$ be the queries of $\mathsf{A}$ to oracle $\text{Prove}$ and $(v_i,({\hat{v}}_i,{\Pi }_i))$ be the corresponding answers. Note that ${\Pi }_i$ does not bring any additional information to $\mathsf{A}$ as it can be computed from the other quantities, namely $${\Pi }_i=\frac{1}{\tau -u_i}(C-v_i{G}_1-{\hat{v}}_i{H}_1).$$ Hence, all in all the adversary is given $d$ evaluations of $p$ and $\hat{p}$ at the same points together with the value $c=p(\tau )+h\hat{p}(\tau ).$ Note that $h\ne 0$ since $H_1$ is a generator of ${\mathbb{G}}_1.$ Hence, conditioned on $(u_i,v_i,{\hat{v}}_i)$ for $i\in \{1,\dots ,d\}$ and $c,$ the value of $p(\tau )$ is uniformly random and $\mathsf{A}$ only has $d$ evaluations of $p.$ This implies that the probability that $\mathsf{A}$ guesses $p(u)$ correctly for $u\notin \{u_1,\dots ,u_d\}$ is $1/\left|{\mathbb{F}}_r\right|\le 1/2^{2\lambda -1}.$

Binding Security

The poly-binding and eval-binding security properties hold under the same assumptions as for DL-KZG. The proofs are slightly more complex and must account for the possibility that the adversary solves the discrete logarithm problem for $H_1$ in base $G_1.$

Theorem 19.6. Assume that the $(d,1)$-co-DL problem is hard for $\mathsf{PairingSetup}.$ Then the Ped-KZG scheme for maximal degree $d$ is poly-binding. More precisely, for any adversary $\mathsf{A}$ against the poly-binding security of Ped-KZG for maximal degree $d,$ there exists an adversary $\mathsf{B}$ for the $(d,1)$-co-DL problem running in time $t+O(\lambda d^3),$ where $t$ is the running time of $\mathsf{A},$ and such that $${\mathbf{Adv}}_{\mathsf{A}}^{\text{poly-binding}}(\lambda )=2\cdot {\mathbf{Adv}}_{\mathsf{B}}^{\text{(d,1)-co-dl}}(\lambda ).$$

Proof

Let $\mathsf{A}$ be an adversary against the poly-binding security of the Ped-KZG scheme for maximal degree $d.$ We construct an algorithm $\mathsf{B}$ for the $(d,1)$-co-DL problem as follows. $\mathsf{B}$ gets pairing group parameters $({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)$ and an instance $(G_1,x{G}_1,\dots ,x^d{G}_1,G_2,x{G}_2)$ of the $(d,1)$-co-DL problem. The goal of $\mathsf{B}$ is to compute $x.$

Adversary $\mathsf{B}$ randomly chooses between two indistinguishable ways to embed its instance into the parameters. Namely, it draws $b{\leftarrow }_{\$}\{0,1\}$ and proceeds as follows depending on $b:$

• If $b=0,$ then $\mathsf{B}$ draws $h{\leftarrow }_{\$}{\mathbb{F}}_r\setminus \{0\}$ and runs $\mathsf{A}$ on public parameters $$par=(G_1,x{G}_1,\dots ,x^d{G}_1,\alpha G_1,h(x{G}_1),\dots ,h(x^d{G}_1),G_2,x{G}_2).$$ This implicitly sets $\tau =x$ and $H_1=h{G}_1.$
• If $b=1,$ then $\mathsf{B}$ draws $\tau {\leftarrow }_{\$}{\mathbb{F}}_r$ and runs $\mathsf{A}$ on public parameters $$par=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,x{G}_1,\tau (x{G}_1),\dots ,{\tau }^d(x{G}_1),G_2,\tau G_2).$$ This implicitly sets $H_1=x{G}_1.$

Assume that $\mathsf{A}$ is successful and returns a commitment $C$ and two distinct polynomials $p$ and $p^{\prime }$ of degree at most $d$ together with corresponding decommitments $\hat{p}$ and ${\hat{p}}^{\prime }$ such that $$\mathsf{PolyVerif}(par,C,p,\hat{p})=\mathsf{PolyVerif}(par,C,p^{\prime },{\hat{p}}^{\prime })=1.$$ This implies that $$C=p(\tau )G_1+\hat{p}(\tau )H_1=p^{\prime }(\tau )G_1+{\hat{p}}^{\prime }(\tau )H_1$$ and hence $$(p(\tau )-p^{\prime }(\tau ))G_1+(\hat{p}(\tau )-{\hat{p}}^{\prime }(\tau ))H_1=0.$$ We can distinguish two cases:

• case $p(\tau )-p^{\prime }(\tau )=0:$ If $b=1$ then $\mathsf{B}$ aborts. Otherwise, since $b=0,$ we have $x=\tau .$ Hence, $x$ is a root of the non-zero polynomial $(p-p^{\prime })(X)\in {\mathbb{F}}_r^{(\le d)}[X].$ This polynomial can be factored in time $O(d^3\log (r))$ with the Cantor–Zassenhaus algorithm, which allows $\mathsf{B}$ to compute all its roots and find $x.$
• case $p(\tau )-p^{\prime }(\tau )\ne 0:$ If $b=0$ then $\mathsf{B}$ aborts. Otherwise, since $b=1$ then $H_1=x{G}_1.$ This implies that $$p(\tau )-p^{\prime }(\tau )+x(\hat{p}(\tau )-{\hat{p}}^{\prime }(\tau ))=0.$$ Then necessarily $\hat{p}(\tau )-{\hat{p}}^{\prime }(\tau )\ne 0$ as otherwise this would contradict $p(\tau )-p^{\prime }(\tau )\ne 0.$ Hence, $\mathsf{B}$ can compute $$x=\frac{p(\tau )-p^{\prime }(\tau )}{{\hat{p}}^{\prime }(\tau )-\hat{p}(\tau )}.$$

The view of $\mathsf{A}$ is independent from $b$ and hence $\mathsf{B}$ aborts with probability $1/2,$ so that $${\mathbf{Adv}}_{\mathsf{B}}^{\text{(d,1)-co-dl}}(\lambda )=\frac{1}{2}{\mathbf{Adv}}_{\mathsf{A}}^{\text{poly-binding}}(\lambda ).$$ The running time of $\mathsf{B}$ is at most $t+O(\lambda d^3),$ which concludes the proof.

Theorem 19.7. Assume that the $d$-SDH problem is hard for $\mathsf{PairingSetup}.$ Then the Ped-KZG scheme for maximal degree $d$ is eval-binding. More precisely, for any adversary $\mathsf{A}$ against the eval-binding security of Ped-KZG for maximal degree $d,$ there exists an adversary $\mathsf{B}$ for the $d$-SDH problem running in time similar to the time of $\mathsf{A}$ and such that $${\mathbf{Adv}}_{\mathsf{A}}^{\text{eval-binding}}(\lambda )=2\cdot {\mathbf{Adv}}_{\mathsf{B}}^{\text{d-sdh}}(\lambda ).$$

Proof

Let $\mathsf{A}$ be an adversary against the eval-binding security of the Ped-KZG scheme for maximal degree $d.$ We construct an adversary $\mathsf{B}$ for the $d$-SDH problem. $\mathsf{B}$ gets pairing group parameters $({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)$ and an instance $(G_1,x{G}_1,\dots ,x^d{G}_1,G_2,x{G}_2)$ of the $d$-SDH problem. The goal of $\mathsf{B}$ is to return a pair $(a,Y)$ such that $Y=\frac{1}{x+a}{G}_1.$

Adversary $\mathsf{B}$ randomly chooses between two indistinguishable ways to embed its instance into the parameters. Namely, it draws $b{\leftarrow }_{\$}\{0,1\}$ and proceeds as follows depending on $b:$

• If $b=0,$ then $\mathsf{B}$ draws $h{\leftarrow }_{\$}{\mathbb{F}}_r\setminus \{0\}$ and runs $\mathsf{A}$ on public parameters $$par=(G_1,x{G}_1,\dots ,x^d{G}_1,\alpha G_1,h(x{G}_1),\dots ,h(x^d{G}_1),G_2,x{G}_2).$$ This implicitly sets $\tau =x$ and $H_1=h{G}_1.$
• If $b=1,$ then $\mathsf{B}$ draws $\tau {\leftarrow }_{\$}{\mathbb{F}}_r$ and runs $\mathsf{A}$ on public parameters $$par=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,x{G}_1,\tau (x{G}_1),\dots ,{\tau }^d(x{G}_1),G_2,\tau G_2).$$ This implicitly sets $H_1=x{G}_1.$

Assume that $\mathsf{A}$ is successful and returns a commitment $C,$ a field element $u\in {\mathbb{F}}_r,$ and two valid value/proof pairs $(v,(w,\Pi ))$ and $(v^{\prime },(w^{\prime },{\Pi }^{\prime }))$ with $v\ne v^{\prime }.$ Then $\mathsf{B}$ proceeds as follows. First, it checks whether $u=\tau$ (e.g., by checking whether $u{G}_1$ is equal to the second group element of the parameters $par).$ If this is the case, then $\mathsf{B}$ simply picks an arbitrary element $a\in {\mathbb{F}}_r\setminus \{-\tau \}$ and returns $(a,\frac{1}{\tau +a}{G}_1).$ From now on, we assume $u\ne \tau .$ The validity of the two proofs imply that $$\begin{array}{rl}e(C-v{G}_1-w{H}_1,G_2)& =e(\Pi ,\tau G_2-u{G}_2)\\ \text{and }e(C-v^{\prime }{G}_1-w^{\prime }{H}_1,G_2)& =e({\Pi }^{\prime },\tau G_2-u{G}_2).\end{array}$$ Combining these two equations, we get $$\begin{array}{rl}e((v^{\prime }-v)G_1+(w^{\prime }-w)H_1,G_2)& =e(\Pi -{\Pi }^{\prime },(\tau -u)G_2)\\ e\left(\frac{v^{\prime }-v}{\tau -u}{G}_1+\frac{w^{\prime }-w}{\tau -u}{H}_1,G_2\right)& =e(\Pi -{\Pi }^{\prime },G_2),\end{array}$$ where we used that $u\ne \tau .$

We can now distinguish two cases:

• case $\Pi \ne {\Pi }^{\prime }:$ If $b=1$ then $\mathsf{B}$ aborts. Otherwise, since $b=0,$ we have $\tau =x$ and $\mathsf{B}$ knows the value $h$ such that $H_1=h{G}_1.$ The equation above yields $$e\left(\frac{v^{\prime }-v+h(w^{\prime }-w)}{x-u}{G}_1,G_2\right)=e(\Pi -{\Pi }^{\prime },G_2),$$ This implies in particular that $v^{\prime }-v+h(w^{\prime }-w)\ne 0$ as otherwise this would imply $\Pi ={\Pi }^{\prime }.$ Hence, $$e\left(\frac{1}{x-u}{G}_1,G_2\right)=e\left(\frac{1}{v^{\prime }-v+h(w^{\prime }-w)}(\Pi -{\Pi }^{\prime }),G_2\right)$$ which implies that $$Y:=\frac{1}{v^{\prime }-v+h(w^{\prime }-w)}(\Pi -{\Pi }^{\prime })=\frac{1}{(x-u)}{G}_1$$ Thus, $\mathsf{B}$ can return $(-u,Y)$ as solution to the $d$-SDH instance.
• case $\Pi ={\Pi }^{\prime }:$ If $b=0$ then $\mathsf{B}$ aborts. Otherwise, since $b=1;$ we have $H_1=x{G}_1$ and the equation above yields $$e\left(\frac{v^{\prime }-v+x(w^{\prime }-w)}{\tau -u}{G}_1,G_2\right)=e(0,G_2),$$ which implies $(v^{\prime }-v)+x(w^{\prime }-w)=0.$ We cannot have $w=w^{\prime }$ as this would imply $v=v^{\prime }$ whereas $v\ne v^{\prime }$ when $\mathsf{A}$ is successful. Hence, $\mathsf{B}$ can compute $x=(v^{\prime }-v)(w^{\prime }-w{)}^{-1},$ choose an arbitrary $a\in {\mathbb{F}}_r\setminus \{-x\},$ and return $(a,\frac{1}{x+a}{G}_1)$ as solution to the SDH instance.

The view of $\mathsf{A}$ is independent from $b$ and hence $\mathsf{B}$ aborts with probability $1/2,$ so that $${\mathbf{Adv}}_{\mathsf{B}}^{\text{d-sdh}}(\lambda )=\frac{1}{2}{\mathbf{Adv}}_{\mathsf{A}}^{\text{eval-binding}}(\lambda ).$$ The running time of $\mathsf{B}$ is similar to the running time of $\mathsf{A},$ which concludes the proof.

Discussion

Efficiency

DL-KZG commitments are extremely succinct and rather cheap to verify: a commitment and a proof take one elliptic curve point each (e.g., 48 bytes when using BLS12-381) and verifying an opening essentially takes two pairings. In case one has to verify many openings for the same commitment, the verification equation (19.1) can be equivalently written $$e(C,G_2)=e(G_1,G_2{)}^{v}e(\Pi ,\tau G_2-u{G}_2),$$ where $e(C,G_2)$ and $e(G_1,G_2)$ can be computed once and stored for verifying multiple openings, allowing to trade one pairing for one exponentiation in ${\mathbb{G}}_t.$ On the other hand, the size of the commitment key and the complexity of algorithms $\mathsf{Commit}$ and $\mathsf{EvalProve}$ are linear in $d,$ the maximal degree of committed polynomials (which when building SNARKs can be quite large).

Trusted Setup

The secret value $\tau$ drawn by the $\mathsf{Setup}$ algorithm must be securely deleted once the commitment key has been set up as it allows to break the evaluation binding property of the scheme. Indeed, knowing $\tau ,$ given an arbitrary commitment $C\in {\mathbb{G}}_1,$ one can open this commitment at any point $u\ne \tau$ to any value $v$ by computing the proof as $\Pi =(\tau -u{)}^{-1}(C-v{G}_1).$ Then the verification equation (19.1) is satisfied as $$\begin{array}{rl}e(\Pi ,\tau G_2-u{G}_2)& =e((\tau -u{)}^{-1}(C-v{G}_1),(\tau -u)G_2)\\ & =e(C-v{G}_1,G_2).\end{array}$$

This is quite different from the $\mathsf{Setup}$ procedure of the Pedersen commitment scheme, for which it is possible to proceed without ever generating any trapdoor explicitly. There is no (efficient) way known to implement the $\mathsf{Setup}$ procedure for KZG without explicitly sampling $\tau .$ To the best of my knowledge, there is also no proof that this is impossible. The assumption that this is impossible looks quite similar to many "knowledge of exponent" assumptions, hence the claim that running the KZG setup obliviously of $\tau$ is impossible is presumably true but not provable with known techniques. It is, however, possible to run the setup in a decentralized fashion, ensuring that the process is secure as long as a single party behaves honestly (see for example [NRBB22]).

Note that it is possible to check that the trusted setup yielded public parameters having the correct form, namely that there indeed exists $\tau \in {\mathbb{F}}_r$ such that $par=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,G_2,\tau G_2).$ Say we are given $par=(P_0,P_1,\dots ,P_d,G_2,H_2).$ Let $\tau$ be defined as the discrete log of $H_2$ in base $G_2,$ i.e., $H_2=\tau G_2,$ and set $G_1=P_0.$ Then $ck$ has the correct form if and only if for every $i\in \{0,\dots ,d-1\},$ $e(P_i,H_2)=e(P_{i+1},G_2).$ Indeed, one has the following equivalences: $$\begin{array}{rl}e(P_i,H_2)=e(P_{i+1},G_2)& ⟺e(P_i,\tau G_2)=e(P_{i+1},G_2)\\ & ⟺e(\tau P_i,G_2)=e(P_{i+1},G_2)\\ & ⟺P_{i+1}=\tau P_i.\end{array}$$

Summary of KZG Properties

Multi-evaluation Proofs

We will see that the DL-KZG scheme can be generalized to allow proving multiple evaluations with one single proof consisting of a single ${\mathbb{G}}_1$ element. This technique can also be applied to Ped-KZG but it is much less interesting since the size of the proof for $n$ evaluations is one ${\mathbb{G}}_1$ element plus $n$ field elements, hence it grows linearly with $n.$

Recall that for a polynomial $p\in {\mathbb{F}}_{}^{(\le d)}[X],$ $p(u)=v$ is equivalent to $p(X)-v$ being divisible by $X-u.$ How does this generalize to multiple evaluations?

First, let us recall some vocabulary from the section about Lagrange interpolation. An evaluation domain (or simply domain) of size $n$ is a subset $\mathcal{U}\subset \mathbb{F}$ of size $n.$ The vanishing polynomial over $\mathcal{U}$ is the polynomial $z(X)$ defined as $$z_{\mathcal{U}}(X):=\prod _{i=1}^n(X-u_i).$$ A multi-evaluation of size $n$ is a subset $\mathcal{E}=\{(u_1,v_1),\dots ,(u_n,v_n)\}\subset {\mathbb{F}}^2$ such that $u_i\ne u_j$ for $i\ne j.$ The evaluation domain associated with $\mathcal{E}=\{(u_1,v_1),\dots ,(u_n,v_n)\}$ is $\mathcal{U}:=\{u_1,\dots ,u_n\}.$ We say that a polynomial $p\in \mathbb{F}[X]$ satisfies a multi-evaluation $\mathcal{E}=\{(u_1,v_1),\dots ,(u_n,v_n)\}$ if $p(u_i)=v_i$ for every $i\in \{1,\dots ,n\}.$

The idea of multi-evaluation proofs relies on the generalized polynomial remainder theorem that we restate here. Let $p\in \mathbb{F}[X],$ $\mathcal{E}=\{(u_1,v_1),\dots ,(u_n,v_n)\}$ be a multi-evaluation of size $n\le \mathrm{deg}(p),$ and $\mathcal{U}:=\{u_1,\dots ,u_n\}.$ Let $z(X)$ be the vanishing polynomial for domain $\mathcal{U}$ and $\ell (X)$ be the Lagrange interpolation polynomial for $\mathcal{E},$ i.e., the unique polynomial of degree at most $n-1$ such that $\ell (u_i)=v_i$ for every $i\in \{1,\dots ,n\}.$ Then $p$ satisfies $\mathcal{E}$ if and only if $z(X)$ divides $p(X)-\ell (X).$

For $n=1,$ one recovers the standard polynomial remainder theorem since for a single point $(u,v)$ the vanishing polynomial is $X-u$ and the Lagrange interpolation polynomial is the constant polynomial $\ell (X)=v,$ hence $p$ satisfies $p(u)=v$ if and only if $X-u$ divides $p(X)-v.$

Syntax and Security Definition

Let us now see how to adapt the syntax of a PC scheme to accommodate multi-evaluation proofs. Concretely, a PC scheme with multi-evaluation proofs consists of five algorithms: $\mathsf{Setup},$ $\mathsf{Commit},$ and $\mathsf{PolyVerif}$ have the same syntax as for a standard PC scheme, while $\mathsf{EvalProve}$ and $\mathsf{EvalVerif}$ are replaced respectively by the following two algorithms:

• a $\mathsf{MultiProve}$ algorithm which on input parameters $par,$ a polynomial $p\in {\mathbb{F}}_{}^{(\le d)}[X],$ a decommitment $D,$ and a tuple $(u_1,\dots ,u_n)\in {\mathbb{F}}^n$ of $n$ distinct field elements, $n\le d,$ returns a tuple $(v_1,\dots ,v_n)\in {\mathbb{F}}^n$ and a proof $\Pi ;$

• a $\mathsf{MultiVerif}$ algorithm which on input parameters $par,$ a commitment $C,$ a multi-evaluation $\mathcal{E},$ and a proof $\Pi ,$ returns 1 if $\Pi$ is a valid proof that the polynomial committed to by $C$ satisfies $\mathcal{E}$ and 0 otherwise.

The correctness property can be straightforwardly adapted: for every security parameter $\lambda ,$ every $d\in \mathbb{N},$ every $p\in {\mathbb{F}}_{}^{(\le d)}[X],$ every $n\in \{1,\dots ,d\},$ and every subset $\{u_1,\dots ,u_n\}\subset \mathbb{F},$ the following game capturing the nominal execution of algorithms for multi-evaluation proving must return true with probability 1:

$$\boxed{\begin{array}{rl}& par\leftarrow \mathsf{Setup}(1^{\lambda })\\ & (C,D)\leftarrow \mathsf{Commit}(par,p)\\ & ((v_1,\dots ,v_n),\Pi )\leftarrow \mathsf{MultiProve}(par,p,D,(u_1,\dots ,u_n))\\ & \mathcal{E}:=\{(u_1,v_1),\dots ,(u_n,v_n)\}\\ & b\leftarrow \mathsf{MultiVerif}(par,C,\mathcal{E},\Pi )\\ & \mathbf{assert}(b=1)\end{array}}$$

We must modify the security definitions accordingly. The poly-hiding and poly-binding notion are identical to the ones defined for a standard PC scheme. The eval-hiding notion is very similar: one only needs to adapt the $\text{Prove}$ oracle so that it may be queried on domains of size larger than 1.

The eval-binding notion requires more care: we still want that no adversary can prove that a polynomial evaluates to two different values $v$ and $v^{\prime }$ at the same input point $u;$ however, now the adversary has the freedom to prove this for two different multi-evaluations $\mathcal{E}$ and ${\mathcal{E}}^{\prime }$ with the constraint that $(u,v)\in \mathcal{E}$ and $(u,v^{\prime })\in {\mathcal{E}}^{\prime }.$ To emphasize the difference, we call this adapted security notion multi-binding. It is defined via the following game.

$$\boxed{\begin{array}{l}\text{Game MULTI-BINDING:}\\ par\leftarrow \mathsf{Setup}(1^{\lambda })\\ (C,(u,v,v^{\prime }),(\mathcal{E},\Pi ),({\mathcal{E}}^{\prime },{\Pi }^{\prime }))\leftarrow \mathsf{A}(par)\\ b\leftarrow \mathsf{EvalVerif}(par,C,\mathcal{E},\Pi )\\ b^{\prime }\leftarrow \mathsf{EvalVerif}(par,C,{\mathcal{E}}^{\prime },{\Pi }^{\prime })\\ \mathbf{assert}(u,v)\in \mathcal{E}\\ \mathbf{assert}(u,v^{\prime })\in {\mathcal{E}}^{\prime }\\ \mathbf{assert}(v\ne v^{\prime })\\ \mathbf{assert}(b=1)\\ \mathbf{assert}(b^{\prime }=1)\end{array}}$$

KZG with Multi-evaluation Proofs: Description

The DL-KZG multi-evaluation PC scheme works as follows:

• The $\mathsf{Setup}$ algorithm, on input the security parameter $1^{\lambda },$ runs $$({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)\leftarrow \mathsf{PairingSetup}(1^{\lambda }),$$ draws random generators $G_1$ and $G_2$ of respectively ${\mathbb{G}}_1$ and ${\mathbb{G}}_2,$ draws $\tau {\leftarrow }_{\$}{\mathbb{F}}_r,$ and returns public parameters $$par:=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,G_2,\tau G_2,\dots ,{\tau }^d{G}_2)\in {\mathbb{G}}_1^{d+1}\times {\mathbb{G}}_2^{d+1}.$$

• The $\mathsf{Commit}$ and $\mathsf{PolyVerif}$ algorithms are defined exactly as for DL-KZG.

• The $\mathsf{MultiProve}$ algorithm, on input a commitment key $ck=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1),$ a polynomial $p\in {\mathbb{F}}_r^{(\le d)}[X],$ and a subset $\mathcal{U}=\{u_1,\dots ,u_n\}\subset {\mathbb{F}}_r$ of size $n\in \{1,\dots ,d\},$ computes the polynomials $$\begin{array}{rl}z(X)& :=\prod _{i=1}^n(X-u_i),\\ \ell (X)& :=\sum _{i=1}^{n}p(u_i)\prod _{\begin{array}{c}1\le j\le n\\ j\ne i\end{array}}\frac{X-u_j}{u_i-u_j},\\ q(X)& :=\frac{p(X)-\ell (X)}{z(X)}=\sum _{i=0}^d{b}_i{X}^i,\end{array}$$ and the group element $\Pi :={\sum }_{i=0}^d{b}_i({\tau }^i{G}_1)=q(\tau )G_1$ and returns $(p(u_1),\dots ,p(u_n))$ and the proof $\Pi .$

• The $\mathsf{MultiVerif}$ algorithm, on input a verification key $vk=(G_2,\tau G_2,\dots ,{\tau }^d{G}_2),$ a commitment $C,$ a multi-evaluation $\mathcal{E}=\{(u_1,v_1),\dots ,(u_n,v_n)\}$ of size $n\in \{1,\dots ,d\},$ and a proof $\Pi ,$ computes the polynomials $$\begin{array}{rl}z(X)& :=\prod _{i=1}^n(X-u_i),\\ \ell (X)& :=\sum _{i=1}^n{v}_i\prod _{\begin{array}{c}1\le j\le n\\ j\ne i\end{array}}\frac{X-u_j}{u_i-u_j},\end{array}$$ and returns 1 if $$e(C-\ell (\tau )G_1,G_2)=e(\Pi ,z(\tau )G_2)$$ and 0 otherwise.

Observe that the $\mathsf{MultiVerif}$ algorithm must compute $\ell (\tau )G_1$ and $z(\tau )G_2.$ For a multi-evaluation of size $n,$ $\ell$ has degree at most $n-1$ and $z$ has degree $n.$ Hence, if proofs for multi-evaluations of size at most $N$ are to be supported, one can restrict the public parameters to $$par=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,G_2,\tau G_2,\dots ,{\tau }^N{G}_2)\in {\mathbb{G}}_1^{d+1}\times {\mathbb{G}}_2^{N+1}$$ and derive a commitment key $$ck=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1)\in {\mathbb{G}}_1^{d+1}$$ and a verification key $$vk=(G_1,\tau G_1,\dots ,{\tau }^{N-1}{G}_1,G_2,\tau G_2,\dots ,{\tau }^N{G}_2)\in {\mathbb{G}}_1^N\times {\mathbb{G}}_2^{N+1}.$$

Security Proof

The proof of Theorem 19.3 can be adapted to show that DL-KZG is multi-binding under a slightly different assumption called $(q_1,q_2)$-bilinear strong Diffie-Hellman ($(q_1,q_2)$-BSDH). This problem is as follows: given $$(G_1,x{G}_1,\dots x^{q_1}{G}_1,G_2,x{G}_2,\dots ,x^{q_2}{G}_2)\in {\mathbb{G}}_1^{q_1+1}\times {\mathbb{G}}_2^{q_2+1},$$ compute a pair $(a,Y)\in {\mathbb{F}}_r\times {\mathbb{G}}_t$ such that $Y=e(G_1,G_2{)}^{\frac{1}{x+a}}.$ Note that $$(q_1,q_2)\text{-BSDH}\leqq (q_1,q_2)\text{-SDH}.$$ Indeed, given a solution $(a,\frac{1}{x+a}{G}_1)$ for some SDH instance, one can compute a solution $(a,e(\frac{1}{x+a}{G}_1,G_2))$ for the corresponding BSDH instance. The converse, though, is not known to hold, so that BSDH is presumably a stronger assumption than SDH.

Theorem 19.8. Assume that the $(d,N)$-BSDH problem is hard for $\mathsf{PairingSetup}.$ Then the DL-KZG multi-evaluation scheme for maximal degree $d$ and multi-evaluations of size at most $N$ is multi-binding. More precisely, for any adversary $\mathsf{A}$ against the multi-binding security of DL-KZG, there exists an adversary $\mathsf{B}$ for the $(d,N)$-BSDH problem running in time similar to the time of $\mathsf{A}$ and such that $${\mathbf{Adv}}_{\mathsf{A}}^{\text{multi-binding}}(\lambda )={\mathbf{Adv}}_{\mathsf{B}}^{\text{(d,N)-bsdh}}(\lambda ).$$

Proof

Let $\mathsf{A}$ be an adversary against the multi-binding security of the DL-KZG scheme for maximal degree $d.$ We construct an adversary $\mathsf{B}$ for the $(d,N)$-BSDH problem. $\mathsf{B}$ gets pairing group parameters $({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)$ and an instance $$(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,G_2,\tau G_2,\dots ,{\tau }^N{G}_2)$$ of the $(d,N)$-BSDH problem. The goal of $\mathsf{B}$ is to return a pair $(a,Y)$ such that $Y=e(G_1,G_2{)}^{\frac{1}{\tau +a}}.$ Adversary $\mathsf{B}$ runs $\mathsf{A}$ on input parameters $$par=(G_1,\tau G_1,\dots ,{\tau }^d{G}_1,G_2,\tau G_2,\dots ,{\tau }^N{G}_2).$$ Assume that $\mathsf{A}$ returns a commitment $C,$ a tuple $(u,v,v^{\prime })\in {\mathbb{F}}_r^3,$ and two valid multi-evaluations/proof pairs $(\mathcal{E},\Pi )$ and $({\mathcal{E}}^{\prime },{\Pi }^{\prime })$ such that $v\ne v^{\prime },$ $(u,v)\in \mathcal{E},$ and $(u,v^{\prime })\in {\mathcal{E}}^{\prime }.$ If $u=\tau$ (which $\mathsf{B}$ can verify by checking whether $u{G}_1$ is equal to the second group element of the parameters $par),$ then $\mathsf{B}$ simply picks an arbitrary element $a\in {\mathbb{F}}_r\setminus \{-\tau \}$ and returns $(a,e(G_1,G_2{)}^{\frac{1}{\tau +a}})$ as solution to the $d$-BSDH instance. From now on, we assume that $u\ne \tau .$

Let $\mathcal{U},$ resp. ${\mathcal{U}}^{\prime }$ be the evaluation domain corresponding to $\mathcal{E},$ resp. ${\mathcal{E}}^{\prime }.$ Let also $z,$ resp. $z^{\prime }$ be the vanishing polynomial for $\mathcal{U},$ resp. ${\mathcal{U}}^{\prime }$ and $\ell ,$ resp. ${\ell }^{\prime }$ be the Lagrange interpolation polynomial for $\mathcal{E},$ resp. ${\mathcal{E}}^{\prime }.$ Validity of the two proofs imply that $$\begin{array}{rl}e(C-\ell (\tau )G_1,G_2)& =e(\Pi ,z(\tau )G_2)\\ \text{and }e(C-{\ell }^{\prime }(\tau )G_1,G_2)& =e({\Pi }^{\prime },z^{\prime }(\tau )G_2).\end{array}$$ Combining these two equations, we obtain $$\begin{array}{r}e(({\ell }^{\prime }-\ell )(\tau )G_1,G_2)=e(\Pi ,z(\tau )G_2)e({\Pi }^{\prime },z^{\prime }(\tau )G_2{)}^{-1}.\end{array}$$ We know that $u$ is a root of both $z(X)$ and $z^{\prime }(X).$ Hence, there are polynomials $q$ and $q^{\prime }$ such that $z(X)=(X-u)q(X)$ and $z^{\prime }(X)=(X-u)q^{\prime }(X).$ We also know that polynomial $({\ell }^{\prime }-\ell )(X)$ evaluates to $v^{\prime }-v$ at $u.$ Hence, by the polynomial remainder theorem, there is a polynomial $q^{\prime \prime }$ such that $$({\ell }^{\prime }-\ell )(X)=v^{\prime }-v+(X-u)q^{\prime \prime }(X).$$ Note that $\mathsf{B}$ can explicitly compute $q,$ $q^{\prime },$ and $q^{\prime \prime }.$ Injecting this in the previous equation, we get $$\begin{array}{rl}& e((v^{\prime }-v)G_1,G_2)e((\tau -u)q^{\prime \prime }(\tau )G_1,G_2)=e(\Pi ,(\tau -u)q(\tau )G_2)e({\Pi }^{\prime },(\tau -u)q^{\prime }(\tau )G_2{)}^{-1}\\ & e((v^{\prime }-v)G_1,G_2)=e(\Pi ,(\tau -u)q(\tau )G_2)e({\Pi }^{\prime },(\tau -u)q^{\prime }(\tau )G_2{)}^{-1}e((\tau -u)q^{\prime \prime }(\tau )G_1,G_2{)}^{-1}\\ & e(G_1,G_2{)}^{1/(\tau -u)}=(e(\Pi ,q(\tau )G_2)e(-{\Pi }^{\prime },q^{\prime }(\tau )G_2)e(-q^{\prime \prime }(\tau )G_1,G_2){)}^{1/(v^{\prime }-v)},\end{array}$$ where for the last equality we used that $\tau -u\ne 0$ and $v^{\prime }-v\ne 0.$ Hence, $\mathsf{B}$ can return $(-u,Y),$ where $Y$ is the right-hand side of the last equation, as solution to the $(d,N)$-BSDH instance.

As a sanity check, observe that for a single evaluation ($n=1),$ one has $q(X)=q^{\prime }(X)=1$ and $q^{\prime \prime }(X)=0,$ in which case the last equation simplifies to $$e\left(\frac{1}{\tau -u}{G}_1,G_2\right)=e\left(\frac{1}{v^{\prime }-v}(\Pi -{\Pi }^{\prime }),G_2\right)$$ which allows to solve the $d$-SDH problem and recover Theorem 19.3.

A Practical Use Case

Ethereum is planning to use the KZG polynomial commitment scheme for proto-danksharding. Its properties make it a convenient solution to the data availability problem. A distributed trusted setup is being run at the time of writing.

Additional Resources

There are many resources explaining KZG out there, here are a few:

• Section 15.2 of PAZK
• this post by Andy Arditi
• this other one by Dankrad Feist
• yet another one by Alin Tomescu
• or this video by Dan Boneh.

---

1: As for standard commitment schemes, the name can vary and this is sometimes called a common reference string (crs) or structured reference string (srs) when it does not consist of random bits and has a specific "shape", as it is the case for KZG.

2: In the seminal paper introducing polynomial commitment schemes [KZG10a], evaluation hiding is simply called hiding.

3: KZG polynomial commitments are often described with a symmetric pairing (i.e., ${\mathbb{G}}_1={\mathbb{G}}_2),$ but we define them for an asymmetric pairing as this is the preferred option in practice.

4: Quite often, generators $G_1$ and $G_2$ are standard and specified in public parameters alongside ${\mathbb{G}}_1$ and ${\mathbb{G}}_2.$

5: The polynomial $q(X)$ is well-defined by the polynomial remainder theorem.