Welcome to the resource topic for 2025/199
Title:
Sublinear Proofs over Polynomial Rings
Authors: Mi-Ying Miryam Huang, Xinyu Mao, Jiapeng Zhang
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.
ePrint: https://eprint.iacr.org/2025/199
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .