Paper 2026/448

Interactive Proofs for Batch Polynomial Evaluation

Abstract

Polynomials are a fundamental mathematical object underlying virtually all of theoretical computer science. In proof systems, a common task for the verifier is to evaluate a polynomial of degree $d$ at $m$ distinct points. The best known algorithm for this problem performs $O((m + d) \cdot \log^2(m + d))$ field operations. We present a concretely efficient $\mathsf{MA}$ protocol for this problem in which the verifier runs in \emph{linear time}: the prover sends a single message consisting of $d - 1$ field elements, and the verifier performs only $O(m + d)$ field operations. We further extend our protocol to handle the more general setting of evaluating multiple polynomials at multiple points, and for this problem, we construct an $\mathsf{AMA}$ protocol. Our protocols improve the verifier time in several interactive proofs. Most notably are the sumcheck protocol over a large summation domain and protocols that rely on polynomial quotienting. In particular, by a straightforward application of our results, we reduce the verifier's runtime in the STIR protocol (CRYPTO 2024) to match that of WHIR (EUROCRYPT 2025), despite WHIR being highly optimized for verification time. As an additional application, we show that any univariate polynomial commitment schemes (PCS) can be transformed, in a black-box manner, into a new scheme that efficiently supports batch openings at multiple points. In particular, opening $m$ points incurs only a constant overhead compared to opening a single point.