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:

• \log_2 p > 250 (the prime is of cryptographic size),
• 2^n \,\vert\, p - 1 (the field has roots of unity \omega_n).
• n = 2^k < 2^{28} (we can realistically compute operations that ar O(n \log n), but not O(n ^2)).

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

• H(X) = X^n -1 or any other efficient polynomial.
• F(X) = X^n -1 or any polynomial.

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}