Paper 2026/2581

Post-Quantum Sublinear Lookup Arguments from Polynomial Preprocessing

Abstract

Lookup arguments with sublinear prover time typically rely on bilinear pairings. The only exception is the recent work of Campanelli, Carrillo, Cascudo, Fiore, Francati, and Gennaro (ePrint 2025/238); however, they rely on general-purpose SNARKs to certify expensive preprocessing, which requires non-black-box usage of cryptographic primitives. Thus practical realizations of sublinear lookups with post-quantum security remain challenging. We develop the first plausibly post-quantum sublinear lookup arguments that avoid general-purpose SNARKs via polynomial preprocessing and a novel adaptation of proximity testing for Reed-Muller codes into the Interactive Oracle Proof (IOP) framework. Our starting point is a knowledge-sound polynomial commitment scheme (PCS) with prover-side preprocessing based on the Kedlaya-Umans framework. Rather than proving the expensive preprocessing computation inside a general-purpose SNARK, we directly certify its output using Reed-Muller proximity testing and an associated evaluation protocol. For polynomials of size $N$, our approach yields multivariate and univariate PCS with $N^{1+\epsilon}\mathsf{polylog}(N)$ preprocessing and only $\mathsf{polylog}(N)$ online prover time, while retaining $\mathsf{polylog}(N)$ proof size and verification. We leverage this PCS to obtain a lookup argument for \textit{static} tables of size $N$ and $k\ll N$ lookups with $k\cdot\mathsf{polylog}(N)$ online prover time and $\mathsf{polylog}(N)$ verification and proof size. We further extend the approach to \textit{updatable} tables, obtaining $O(k(N^\epsilon+\mathsf{polylog}(N)))$ amortized prover time for a $k$-sized batch of reads and writes, where $\epsilon \in (0,1)$. We retain $\mathsf{polylog}(N)$ proof size and verification. The IOPs underlying our lookup arguments satisfy round-by-round (knowledge) soundness, which can be compiled into plausibly post-quantum arguments in the (quantum) random oracle model with transparent setup.