KZG Polynomial Commitment Scheme

KZG polynomial commitment scheme KZG10 plays an important role in making the polynomial constraints of PlonK's arithmetization become a zkSNARK GWC19.

In this section, we provide the syntax and security requirements of a polynomial commitment scheme (PCS) in Polynomial Commitment Scheme - Definition. Then, we show some instantiations of the scheme by discussing its technical overview in Technical Overview.

Author(s): khaihanhtang

Polynomial Commitment Scheme - Definition

In this section, we provide the definition of polynomial commitment scheme including syntax and security requirements. Syntax describes how the scheme works through algorithms while security requirements enforce the scheme to satisfy in order to make it secure.

Syntax is presented in Syntax and security requirements are presented in Security Requirements.

Syntax

A polynomial commitment scheme, for polynomials over a field $\mathbb{F}$, is a tuple of $5$ algorithms $(\mathsf{Setup}, \mathsf{Commit}, \mathsf{VerifyPoly}, \mathsf{CreateWitness}, \mathsf{VerifyEval})$ working as follows:

• $\mathsf{Setup}(1^\kappa, t):$ On inputs security parameter $1^\kappa$ and a degree bound $t$, this algorithm returns a commitment key $ck$. The key $ck$ allows to commit any polynomial in $\mathbb{F}[X]$ whose degree is at most $t$.

Above we use the notation $\mathbb{F}[X]$ to denote the field extension of $\mathbb{F}$. For intuition, this field extension contains every polynomial of the form $f(X) = \sum_{j = 0}^{\deg(f)} c_j \cdot X^j$ where $\deg(f)$ is the degree of $f(X)$ and $c_j \in \mathbb{F}$ for all $j \in \\{0, \dots, \deg(f)\\}$. Hence, with the algorithm $\mathsf{Setup}$ on input $t$, we can assume that it allows to commit to any polynomial $f$ satisfying $\deg(f) \leq t$.

We may have a question about what will happen if we try to use $ck$ to commit to a polynomial whose degree is larger than $t$. In this case, the execution and correctness of the algorithms below or the security of the scheme are not guaranteed.

• $\mathsf{Commit}\left(ck, f(X)\right):$ On inputs commitment key $ck$ and polynomial $f(X) \in \mathbb{F}[X]$, this algorithm returns a commitment $c$ and an opening (or decommitment) $d$. We note that $f(X)$ here is recommended to have degree at most $t$ with respect to $ck$ output by $\mathsf{Setup}(1^\kappa, t)$.

• $\mathsf{VerifyPoly}(ck, f(X), c, d):$ On inputs commitment key $ck$, polynomial $f(X) \in \mathbb{F}[X]$, commitment $c$ and opening $d$, this algorithm deterministically returns a bit $b \in \\{0, 1\\}$ to specify whether $c$ is a correct commitment to $f(X)$. If $c$ is such a correct commitment, then $b = 1$. Otherwise, $b = 0$.

At this moment, we may wonder why $\mathsf{Commit}$ does output both $c, d$ and $\mathsf{VerifyPoly}$ does use both $c, d$. In fact, when participating in an interactive protocol, one party may commit to some secret by exposing commitment $c$ to other parties. This commitment $c$ guarantees that the secret behind, namely, polynomial $f(X)$ in this case, is still secret, guaranteed the hiding property to be discussed later.

On the other hand, since we abuse the word commit, it means that the party publishing $c$ has only one opening, namely, $d$, to show that $c$ is a correct commitment to $f(X)$. It is extremely hard for this party to show that $c$ is correct commitment to some other polynomial $f'(X) \not= f(X)$. This is guaranteed by the binding property of the polynomial commitment scheme, to be discussed later.

• $\mathsf{CreateWitness}(ck, f(X), i, d):$ On inputs commitment key $ck$, polynomial $f(X)$, index $i$ and opening $d$, this algorithm returns a witness $w_i$ to ensure that $c$, related to opening $d$, is commitment to $f(X)$ whose evaluation at index $i$ is equal to $f(i)$.

Let us explain in detail the use of $\mathsf{CreateWitness}$. Assume that a party published $c$ which is a commitment to $f(X)$. It then publishes a point $(i, v)$ and claims that $f(i) = v$ without exposing $f(X)$. By using the algorithm $\mathsf{VerifyEval}$ defined below, this claim is assured if $f(i)$ is actually equal to $v$. Moreover, for all other indices $i'$ satisfying $i' \not= i$, if $f(i')$ has not been opened before, then $f(i')$ is unknown to any party who does not know $f(X)$.

We also remark that, from basic algebra, if we know evaluations at $\deg(f) + 1$ distinct indices, we can recover the polynomial $f(X)$. Therefore, the above claim assumes that other parties do not know up to $\deg(f) + 1$ distinct evaluations.

• $\mathsf{VerifyEval}(ck, c, i, v, w_i):$ On inputs commitment key $ck$, commitment $c$, index $i$, evaluation $v$ and witness $w_i$, this algorithm returns $\\{0, 1\\}$ deciding whether $c$ is a commitment key $f(X)$ satisfying $f(i) = v$.

Security Requirements

In this section, we briefly discuss the security requirement for polynomial commitment schemes.

A polynomial commitment scheme is said to be secure if it satisfies the following properties:

• Correctness. The correctness property says that if the scheme is executed honestly then the verification algorithms, namely, $\mathsf{VerifyPoly}$ and $\mathsf{VerifyEval}$, always returns $1$. In particular, assume that $ck \leftarrow \mathsf{Setup}(1^\kappa, t)$ and $(c, d) \leftarrow \mathsf{Commit}(ck, f(X))$. Then, $\mathsf{VerifyPoly}(ck, f(X), c, d)$ always returns $1$. And, for any $w_i$ output by $\mathsf{CreateWitness}(ck, f(i), i, d)$, algorithm $\mathsf{VerifyEval}(ck, c, i, f(i), w_i)$ always returns $1$.

• Polynomial Binding. For a given commitment key $ck$ output by $\mathsf{Setup}(1^\lambda, t)$, this property says that it is hard to output commitment $c$ and two tuples $(f(X), d)$ and $(f'(X), d')$ such that $f(X)$ and $f'(X)$ are distinct and have degrees at most $t$, and $c$ is commitment to both $f(X)$ and $f'(X)$ with respect to openings $d$ and $d'$, respectively. More precisely, it is hard to make $\mathsf{VerifyPoly}(ck, f(X), c, d) = 1$ and $\mathsf{VerifyPoly}(ck, f'(X), c, d') = 1$ if $f(X) \not= f'(X)$, $\deg(f) \leq t$ and $\deg(f') \leq t$.

• Evaluation Binding. The evaluation binding property says that a committed polynomial evaluating on an index $i$ cannot produce two different outcomes $v$ and $v'$. More precisely, an adversary cannot provide an index $i$ and $2$ tuples $(v, w_i)$ and $(v', w'_i)$ satisfying $v \not= v'$ such that $\mathsf{VerifyEval}(ck, c, i, v, w_i) = 1$ and $\mathsf{VerifyEval}(ck, c, i, v', w'_i) = 1$.

• Hiding. An adversary $\mathcal{A}$ who knows at most $\deg(f)$ evaluations of a committed polynomial $f(X)$ cannot determine any evaluation that it does not know before.

We remind that knowing $\deg(f) + 1$ different evaluations helps to determine polynomial, and hence all other evaluations. Therefore, we use the bound $\deg(f)$ here as a maxmimum number of evaluations that the adversary is allowed to know in order not to correctly obtain the evaluations of all other indices.

Technical Overview

From the syntax of polynomial commitment scheme presented in Polynomial Commitment Scheme - Syntax, a realization, or equivalently, a construction, can be separated into $2$ components:

• Commiting polynomial includes the algorithms $\mathsf{Commit}$ and $\mathsf{VerifyPoly}$.
• Evaluating polynomial includes the algorithms $\mathsf{CreateWitness}$ and $\mathsf{VerifyEval}$.

Based on those components, we present the high level idea of $2$ constructions, namely, conditional and unconditional, of polynomial commitment scheme separated into $3$ little parts. The first and second parts, to be presented in Commitment to Polynomial Without Hiding Property and Correct Evaluation from the Commitment, respectively, focus on constructing the realization of conditional version. And, in the third part, to be presented in Dealing with Hiding, regarding condition and unconditional hidings, we discuss the modification of conditional version to achieve the unconditional one.

Commitment to Polynomial Without Hiding Property

In the construction of KZG10, the main idea to commit a polynomial is to evaluate it on a secret index. For example, assume that $f(X) = a_0 + a_1 X + \dots + a_d X^d \in \mathbb{F}[X]$. The secret index can be thought of as some value $x$ that the committer does not know. So, how can committer evaluate $f(x)$ on that secret index without any knowledge about it? In fact, cryptography can magically help you do that. For instance, by putting $1, x, x^2, \dots, x^n$ into the form of powers to some base element $g$, e.g., $g^1, g^x, g^{x^2}, \dots, g^d$, it helps to hide those values $1, x, x^2, \dots, x^d$. Moreover, it alows you to evaluate $g^{f(x)}$ as desired by computing $(g^1)^{a_0} \cdot (g^x)^{a_1} \cdot (g^{x^2})^{a_2} \cdot \dots \cdot (g^{x^d})^{a_d} = g^{a_0 + a_1x + \dots a_d x^d} = g^{f(x)}.$ Thus, $g^{f(x)}$ is computed without any knowledge about $x$. Hence, that is whatever the committer needs to do in the commit step, namely, executing the algorithm $\textsf{Commit}$ to output the commitment $g^{f(x)}$. So the commitment key $ck$ for this algorithm is the hidden indices wrapped under powers of $g$, namely, the set sequence $(g^1, g^{x}, g^{x^2}, \dots, g^{x^d})$. And, therefore, $(g^1, g^{x}, g^{x^2}, \dots, g^{x^d})$ is also the output of the algorithm $\textsf{Setup}$. At this point, we might think about a few things:

1. How to verify the commitment $c = g^{f(x)}$ by executing $\textsf{VerifyPoly}$.
2. How to guarantee that the commitment satisfies the polynomial binding property.

For the first question, to verify $c$, the decommitment of the construction is $f(X)$ itself. Committer simply send the entire polynomial $f(X)$ to verifier, namely, by sending coefficients $a_0, \dots, a_d$. Having the polynomial and the commitment key $ck$, the verifier can check easily by repeating steps similar to the algorithm $\textsf{Commit}$.

For the second question, to show the satisfaction of binding property, we can assume that the committer is able to break the binding property by introducing another polynomial $f'(X) = a'_0 + a'_1X + \dots + a'_dX^d$ where $f'(X) \not= f(X)$. So we have $g^{f(x)} = c = g^{f'(x)}$.

Correct Evaluation from the Commitment

Warning. This part explains by the use of algebra. You may skip if you feel it is complicated.

For an index $i$ given to the committer, since committer knows $f(X)$, he can compute $f(i)$ definitely. The $\mathsf{CreateWitness}$ algorithm is constructed based on the fact that $X - i$ divides $f(X) - f(i)$. At this point, there is something difficult to realize here since it regards to the use of algebra. However, we know that $f(i)$ is the output of $f(X)$ on input $i$. Therefore, we see that $i$ is among the roots of $g(X) = f(X) - f(i)$, i.e., $g(i) = 0$ which says that $i$ is a root of $g(X)$. Therefore, $X - i$ divides $f(X) - f(i)$. Hence, to guarantee the evaluation binding property, committer needs to show that $f(X) - f(i)$ is divisible by $X - i$.

Example. Consider polynomial $f(X) = 6X^3 + 25X^2 + 16X + 19$ in $\mathbb{Z}_{31}$. Let $i = 28$. Then, $f(28) = 151779 = 3$ in $\mathbb{Z} _{31}$. Hence, $X - 28 = X + 3$ divides $f(X) - 3$. In fact, $f(X) - 3 = 6X^3 + 25X^2 + 16X + 16 = (3X + 5)(2X + 30)(X + 3)\text{ in } \mathbb{Z} _{31}.$ It is obvious that $X + 3$ is a factor of $f(X) - 3$.

Equivalently, we can say that $v = f(i)$ if and only if $X - i$ divides $f(X) - f(i)$.

To show such divisibility holds, we can compute $\psi(X) = \frac{f(X) - v_i}{X - i}$, where $v_i$ is assumed to be $f(i)$, and define witness $w_i = g^{\psi(x)}$ by using $g^1, g^x, \dots, g^{x^d}$ output by the algorithm $\textsf{Setup}$.

At this point, for the verifier to verify, committer needs to show that $\psi(x) \cdot (x - i) + v_i = f(x)$. Let's closely take a look at this formula. We observe the followings:

1. No one knows $x$. Hence, $\psi(x)$ is not known to anyone.
2. Committer and verifier know $g^{\psi(x)}$ which is equal to the commitment $c$. Moreover, they also know $g^x, g^i, g^{v_i}$ since $g^x$ belongs to commitment key $ck$, $i$ is public and $v_i$ is publicly claimed by committer.
3. Verifier can easily compute $g^{x - i} = g^x / g^i$.

Clearly, having $g^{\psi(x)},g^{x - i}, g^{v_i}$ and $g^{f(x)}$, we do not know any efficient way to compute $g^{\psi(x)\cdot (x - i) + v_i}$ since computing $g^{\psi(x)\cdot (x-i)}$ is hard due to Diffie-Hellman assumption.

Using Bilinear Pairing to Handle Correct Multiplications

Recall the bilinear pairing $e : \mathbb{G}\times \mathbb{G} \to \mathbb{G}_T$ where $\mathbb{G}$ and $\mathbb{G}_T$ are some groups of the same cardinality. This bilinear pairing has $2$ properties: bilinearity and non-degeneracy. However, to avoid confusion, we only care about the bilinearity and temporarily skip the notice to non-degeneracy.

• Bilinearity. For $g \in \mathbb{G}$ and $g_T \in \mathbb{G}_T$, $e(g^a, g^b) = e(g, g)^{ab}$ for any $a, b \in \mathbb{Z}_p$ where $p=|\mathbb{G}|$.

The validity of the witness can be check easily by using pairing, namely, $e(w_i, g^x / g^i)\cdot e(g,g)^{v_i} \stackrel{?}{=}e(c, g),$ where $c$ is the commitment to $f(X)$. If the above identity holds, with non-negligible probability, it says that $v_i = f(i)$.

To show identity implies $v_i = f(i)$ with non-negligible probability, we consider $w_i = g^{\psi(x)} = g^{\frac{f(x) - v_i}{x - i}}$. Hence,

$$\begin{align} e(w_i, g^x / g^i)\cdot e(g, g)^{v_i} &= e\left(g^{\frac{f(x) - v_i}{x - i}}, g^x / g^i\right)\cdot e(g, g)^{v_i}\\\\ &= e(g, g)^{f(x) - v_i}\cdot e(g, g)^{v_i} = e(g^{f(x)}, g) = e(c, g). \end{align}$$

Notice that, if the person providing $w_i$ and $v_i$ does not know $f(X)$, then we have the following possibilities:

• This person correctly guesses $w_i$ and $v_i$. This happens with negligible probability if we assumes that field cardinality, namely, number of elements in field $\mathbb{F}$, is large.
• The person incorrectly provides $w_i$ and $v_i$. Specificially, either $v_i$ is not equal to $f(i)$ or $w_i$ is incorrect. Assume that $w_i = g^{h_i}$. This case happens when $x$ is the root of $h_i\cdot (X - i) \cdot v_i = f(X)$. By Schwartz–Zippel lemma, this case also happens with negligible probability if the field cardinality is large and that person does not know $x$, as $x$ at the beginning was assumed to be hidden index.

Dealing with Hiding

In the previous sections, namely, Commitment to Polynomial Without Hiding Property and Correct Evaluation from the Commitment, we discussed the high level idea of the construction of algorithms as well as the polynomial and evaluation binding properties. One remaining thing is the hiding property. In KZG10, the authors proposed $2$ constructions from discrete logarithm assumption, for conditional hiding, and Pedersen commitment, for unconditional hiding.

Remark. We now make clear the $2$ notions here, namely, conditional hiding and unconditional hiding.

Conditional hiding of a commitment $c$ to a polynomial $f(X)$ is the property protecting the polynomial $f(X)$ from being compromised with a condition that some assumption employed is assumed to be hard. Usually, the hardness of the assumption is against probabilistic polynomial-time adversaries. Here, probabilistic polynomial-time adversaries stand for the machines that attack the scheme with limited amount of time, and this amount of time is upper-bounded by a polynomial on input the security parameter given to the scheme. Probabilistic polynomial time is a notion in the theory of computation. If you would like to know more about the detail, we prefer to check some textbooks. For example, we prefer Sipser2012-introduction-to-theory-of-computation in this blog.

On the other hand, unconditional hiding means that we cannot extract any information about the polynomial behind. For example, if $f(X) = a_0 + a_1X + \dots + a_dX^d$ and $r(X) = r_0 + r_1X + \dots + r_dX^d$, given that $r_0, \dots, r_d$ are independently and uniformly sampled from $\mathbb{F}$, then $f(X) + r(X) = (a_0 + r_0) + (a_1 + r_1)X + \dots + (a_d + r_d)X^d$ completely hides $f(X)$ since $a_0 + r_0, a_1 + r_1, \dots, a_d + r_d$ are uniform in $\mathbb{F}$.

Conditional hiding from discrete logarithm assumption

The former, namely, discrete logarithm assumption, guarantees the hiding by its own hardness assumption. In particular, given $g$ and $g^v$ for some secret integer $v$, there is no way to extract any piece of information about $v$ from $g$ and $g^v$ due to hardness of discrete logarithm problem. Therefore, the hiding here is conditional, i.e., discrete logarithm assumption is hard.

Unconditional hiding from Pedersen commitment

The latter, namely, using Pedersen commitment, exploits the use of an additional part to achieve unconditional hiding property, which is secure against powerful adversaries and not limited to PPT ones. Roughly speaking, the external part can be informally thought of as a commitment to a random polynomial with conditional hiding. To perform this, we extend the commitment key $ck$ to contain additional elements $h^1, h^x, \dots, h^{x^d}$ where $h$ is another generator of $\mathbb{G}$ different from $g$. Hence, the commitment key $ck$ now is the tuple $(g^1, \dots, g^{x^d}, h^1, \dots, h^{x^d})$. Therefore, whenever committing to a polynomial $f(X) = a_0 + a_1X + \dots + a_dX^d$, we additionally sample a polynomial $r(X) = r_0 + r_1X + \dots + r_dX^d\in \mathbb{F}[X]$. The sampling process can be conducted easily by sampling each $r_i$ uniformly and independently from $\mathbb{Z}_{|F|} = \\{0, \dots, |F| - 1\\}$.

The algorithm $\textsf{Commit}$ now can be evaluated by computing

$$c = \prod_{i = 0}^d (g^{x^i})^{a_i} \cdot \prod_{i = 0}^d (h^{x^i})^{r_i} = g^{f(x)}\cdot h^{r(x)},$$

namely, the original conditional-hiding commitment to $f(X)$ multiplying with the condition-hiding commitment to random polynomial $r(X)$ becomes an unconditional commitment $c$ where auxiliary information $\textsf{aux}$ can be set to be the tuple $(f(X), r(X))$. Hence, now, the adversary knows nothing about the evaluations of any index in $\mathbb{F}$. We can see clearly that the commitment $c$ hides $f(X)$ unconditionally since $r_0$ is chosen uniformly from $\mathbb{Z}_{|\mathbb{F}|}$ and, hence, $(h^{x^0})^{r_0}$ is uniform in $\mathbb{F}$. It also implies that $c$ is uniform in $\mathbb{F}$.

Since $c = g^{f(x)}\cdot h^{r(x)}$, we can say that $c$ is the multiplication of two parts, namely, the message part $g^{f(x)}$ and the randomness part $h^{r(x)}$.

We now discuss how algorithms $\textsf{CreateWitness}$ and $\textsf{VerifyEval}$ work with respect to introductory of the additional part, namely, $h^{r(x)}$.

Creating witness in unconditional hiding mode

For a given index $i$, the witness output by algorithm $\textsf{CreateWitness}$ is also a multiplication of $2$ parts. We simply call the message evaluation and randomness evaluation parts.

The message evaluation part is computed identically to the conditional version of the commitment scheme. That is, we compute the formula $g^{\psi(x)}$ where $\psi(X) = \frac{f(X) - f(i)}{X - i}$.

The randomness evaluation part is also conducted similarly. Notice that, since we employ $r(X)$ as a polynomial of degree $d$, we can compute witness for the correct evaluation on the same index $i$, namely, $r(i)$. This randomness evaluation part is equal to $h^{\varphi(x)}$ where $\varphi(X) = \frac{r(X) - r(i)}{X - i}$.

Remark. As previously said, $x$ is unknown to committer. Therefore, the computation of $g^{\psi(x)}$ and $h^{\varphi(x)}$ must depend on the commitment key $ck$ by employing the elements $g^1, \dots, g^{x^{d - 1}}, h^1, \dots, h^{x^{d - 1}}$. Notice that we do not you $g^{x^d}$ and $h^{x^d}$ since $\psi(X)$ and $\varphi(X)$ are polynomials of degrees at most $d - 1$.

The output of algorithm $\textsf{CreateWitness}$ is then equal to $w_i = (w^\star_i, s_i)$ where $w^\star_i = g^{\psi(x)} \cdot h^{\varphi(x)}$ is the multiplication of message evaluation and randomness evaluation parts and $s_i = r(i)$. Notice that $r(i)$ is attached to witness in order to help the evaluation verification algorithm, to be described below, work.

Verifying correct evaluation in unconditional mode

The evaluation verification algorithm $\textsf{VerifyEval}$ receives as inputs the commitment key $ck = (g^1, \dots, g^{x^d}, h^1, \dots, h^{x^d})$, commitment $c$ to $f(X)$, index $i$, value $v_i \in \mathbb{F}$ assumed to be equal to $f(i)$ and $w_i = (w^\star_i, s_i)$. This algorithm is expected to return $1$ is $v_i$ is equal to $f(i)$ with the use of associated witness $w_i$.

To verify whether $v_i = f(i)$, it is worth to verify both correct computations of $f(i)$ and $r(i)$. More precisely, verifier needs to confirm that $v_i = f(i)$ and $s_i = r(i)$. To this end, again, we imitate the verification process of the conditional hiding case. Hence, we employ again bilinear pairing $e : \mathbb{G}\times \mathbb{G} \to \mathbb{G}_T$ which maps $(g^a, g^b)$ to $e(g, g)^{ab}$. However, there is an obstacle here. Observe that, in this pairing, we use only $1$ generator $g$ while our commitment employs $2$ different generators $g$ and $h$ both generating $G$. In order to enable the bilinear pairing, we enforce $h = g^\gamma$ for some hidden $\gamma$. This enforcement works because $g$ is the generator of $\mathbb{G}$ and $h$ belongs to $\mathbb{G}$. Hence, our commitment $c$ can be alternatively written as

$$c = g^{f(x)}\cdot h^{r(x)} = g^{f(x)}\cdot g^{\gamma \cdot r(x)} = g^{f(x) + \gamma\cdot r(x)}$$

which is a conditional commitment to $f(X) + \gamma\cdot r(X)$ with $\gamma$ unknown to both committer and verifier.

Moreover, the witness $w^\star_i = g^{\psi(x)}\cdot h^{\varphi(x)}$ can also be interpreted as

$$w^\star_i = g^{\psi(x)}\cdot h^{\varphi(x)}=g^{\psi(x)} \cdot g^{\gamma\cdot \varphi(x)} = g^{\psi(x) + \gamma\cdot \varphi(x)}$$

which is also a witness for correct evaluation at index $i$ with respect to polynomial $f(X) + \gamma\cdot r(X)$ whose $\gamma$ is not known to both parties, namely, committer and verifier.

We now observe that $\psi(X) + \gamma\cdot \varphi(X) = \frac{f(X) - f(i)}{X - i} + \gamma\cdot \frac{r(X) - r(i)}{X - i}$. Hence, it is worth to guarantee the following equation holds:

$$\left(\frac{f(X) - f(i)}{X - i} + \gamma\cdot \frac{r(X) - r(i)}{X - i}\right)\cdot\left(X - i\right) - (f(i) + \gamma\cdot r(i)) = f(X) + \gamma \cdot r(X).$$

We now describe the process for verifying the above equation by employing the bilinear pairing function $g : \mathbb{G}\times \mathbb{G} \to \mathbb{G}_T$. Since the above equation has a multiplication, we apply the bilinear pairing by checking

$$e\left(g^{\frac{f(x) - v_i}{x - i} + \gamma\cdot \frac{r(x) - s_i}{x - i}}, g^{x - i}\right)\cdot e\left(g^{-\left(v_i + \gamma\cdot s_i\right)}, g\right) = e\left(g^{f(x) + \gamma\cdot r(x)},g\right)$$

where $x$ and $\gamma$ are unknown to both parties. Since $x$ and $\gamma$ are not known to both parties, it is inconvenient to evaluate the bilinear pairing function. However, since $ck = (g^1, \dots, g^{x^d}, h^1, \dots, h^{x^d})$ and $h = g^\gamma$ are public inputs, we can replace the appearances of $x$ and $\gamma$ in the above equation by those of $ck$ and $h$. The above computation of bilinear pairing hence becomes

$$e\left(w^\star, g^x / g^i\right)\cdot e\left(g^{-v_i}\cdot h^{-s_i}, g\right) = e(c, g)$$

since $c = g^{f(x)}\cdot h^{r(x)} = g^{f(x) + \gamma\cdot r(x)}$.