Stanford Research Workshop

$$ \def\O{\mathcal O} \def\F{\mathbb F} $$

Context. We are given a prime field $\F_p$, a size parameter $n$ and the following:

Note. If it helps, you may assume additional restricions on the prime $p$, for example the existance of other roots of unity. (Depending on how common these primes are, the result may no longer be relevant in pairing cryptography, but it will still be relevant for FRI and DARK based constructions). You may even outright pick a prime.

We denote the set of polynomials of degree less than $k$ as $\F_{< k}[X]$.

As is common in Cryptography, we accept probabilistic results as long as the probability is larger than $1 - 2^{\lambda}$, where $\lambda$ is the number of bits of security. We typically require at least $\lambda > 80$, but higher is better.

Finally, we are working in interactive proofs where there is dialogue between a prover and a verifier. Given a polynomial $P \in \F_{< n}$ we have existing protocols that allow us to send an oracle for this polynomial to the verfier, and the verifier can then ask for evaluations of these polynomials. Note that this existing protocol only works for polynomials of degree less than $n$.

Lemma. (Polynomial identity test). Given two polynomials $P, Q \in \F_{< n}[X]$ we want to convice the verifier that they are equal. The prover sends oracles for $P$ and $Q$ to the verifier, the verifier responds by asking for evaluations on a random point $\alpha$ and checks that they are equal.

Proof. By the Schwartz-Sippel lemma.

Problem. (Efficient zeros). An efficiently evaluable polynomial of degree $n$ has an $\O(\log n)$ sized circuit of $+$ or $\times$ operations that evaluates it. We are looking for efficiently evaluable polynomials that have as roots a subbset of the roots of unity $\omega_n^i$.

For example $X^n -1$ is efficiently evaluable and has all the roots of unity as roots. $X^{n/2} -1$ is efficient and has a roots all even powers of $\omega_n^i$.

Problem. (Composition) Given $F,G,H \in \F_{< n}[X]$, we want to interactively proof that

$$ F(G(X)) \!\!\!\!\mod H(X) = 0 $$

We can send oracles to the verifier, but only for polynomials in $\F_{\le n}$.

The current proof protocols use

$$ F(G(X)) = H(X) Z(X) $$

and then writes

$$ Z(X) = Z_0(X^n) + X \cdot Z_1(X^n) + \cdots + X^n Z_n(X^n) $$

And sends oracles for $Z_0 \dots Z_n$ and uses identity testing. The problem is this uses $n$ operations, and we'd like a protocol that uses at most $\O(\log n)$ exchanges.

Restrictions. Feel free to assume any of

Generalizations. Same problem, but now with $F$ a multivariate over multiple $G$

$$ F(G_0(X), G_1(X), G_2(X), \dots, G_) = H(X) Z(X) $$

Solution by Reid Barton for $F$ an efficient polynomial.

$$ \begin{aligned} G_1(X) - G(X)^2 &= H(X) Z_1(X) \\ G_2(X) - G(X)^2 &= H(X) Z_2(X) \\ & \,\,\,\vdots \\ G_k(X) - G(X)^2 &= H(X) Z_k(X) \\ \end{aligned} $$

Remco Bloemen
Math & Engineering