Towards ZKP

Note that although we have focused on a malicious prover so far, the verifier may deviate from the honest protocol to learn secret data from the verifier. For example, they can choose adaptive off-domain points or collude across multiple openings with the goal of extracting intermediate witness values or private inputs.

Blinding via vanishing-polynomial multiples

To defend against this, we mask each witness polynomial (f(x)) by adding a random multiple of the vanishing polynomial.

$$Z_H(x)=x^n-1.$$

Concretely, before committing we form

$$\tilde{f}(x)=f(x)+Z_H(x)\cdot p(x),$$

where $p(x)$ is drawn uniformly at random from all polynomials of degree $<k$ (for some security parameter $k$.

One fresh blinding factor per opening

Each time the verifier opens $\tilde{f}$ at a point $z\notin \{{\omega }^i\}$, they learn

$$\tilde{f}(z)=f(z)+Z_H(z)\cdot p(z)$$

which yields one linear equation in the coefficients of $p(x)$.

• If the same $p(x)$ were reused for multiple openings, a malicious verifier could gather enough of these equations to solve for $p(x)$, then subtract $Z_H(x)\cdot p(x)$ and recover the original $f(x)$.
• To preserve zero-knowledge, we therefore allocate one independent random polynomial $p(x)$ for each distinct off-domain opening query.

Example

Consider the following example for blinding the witness polynomial $a(x)$. We assume two openings on $a(x)$, as we will see later in the full protocol.

k = 2

p = R.random_element(degree=k-1)
print("p(x) =", p)
a_blind = a + p*ZH
show(a_blind)
print("Degree of a_blind:",a_blind.degree())

Exercise 18

Assuming $b(x),c(x)$ also have at most two openings, blind them similarly to $a(x)$. Afterwards, interpolate $z\mathrm{\_}poly,N\mathrm{\_}poly,D\mathrm{\_}poly$ using the given $\beta$ and $\gamma$. Finally blind $z\mathrm{\_}poly$ assuming also at most 2 openings.

beta = gamma = 42

b_blind = #?
c_blind = #?
z_poly = #?
N_poly = #?
D_poly = #?
z_poly_blind = #?

If computed correctly the following check should still pass on the blinded polynomials, because the roots of the polynomial do not change (points of the domain).

assert (ZH).divides( z_poly_blind*N_poly -D_poly*z_poly_blind(x*ω)) == True, "Something went wrong"