Paper 2025/199

Sublinear Proofs over Polynomial Rings

Abstract

We propose a sublinear-sized proof system for rank-one constraint satisfaction over polynomial rings (Ring-R1CS), particularly for rings of the form $Z_{Q}[X]/(X^N+1)$. These rings are widely used in lattice-based constructions, which underlie many modern post-quantum cryptographic schemes. Constructing efficient proof systems for arithmetic over these rings is challenged by two key obstacles: (1) Under practical popular choices of $Q$ and $N$, the ring $Z_{Q}[X]/(X^N+1)$ is not field-like, and thus tools like Schwartz–Zippel lemma cannot apply; (2) when $N$ is large, which is common in implementations of lattice-based cryptosystems, the ring is large, causing the proof size suboptimal. In this paper, we address these two obstacles, enabling more efficient proofs for arithmetics over $Z_{Q}[X]/(X^N+1)$ when $Q$ is a `lattice-friendly' modulus, including moduli that support fast NTT computation or power-of-two moduli. Our primary tool is a novel \emph{ring switching} technique. The core idea of ring switching is to convert the R1CS over $Z_{Q}[X]/(X^N+1)$ into another R1CS instance over Galois rings, which is field-like and small (with size independent with $N$). As (zero-knowledge) proofs have many applications in cryptography, we expect that efficient proof systems for polynomial ring arithmetic could lead to more efficient constructions of advanced primitives from lattice assumptions, such as aggregate signatures, group signatures, verifiable random function, or verifiable fully holomorphic encryption.