Paper 2026/347

Relaxed Modular PCS from Arbitrary PCS and Applications to SNARKs for Integers

Sriram Sridhar, University of California, Berkeley

Dimitrios Papadopoulos, Hong Kong University of Science and Technology

Charalampos Papamanthou, Yale University, Lagrange Labs

Abstract

\emph{Modular Polynomial Commitment Schemes (Mod-PCS)} extend standard PCSs by enabling provable evaluation of integer polynomials modulo a random modulus, providing a natural foundation for SNARKs that operate directly over large integers without emulating arithmetic in finite fields. Only two Mod-PCS constructions are known. The first (Campanelli and Hall-Andersen, IACR ePrint 2024) serves primarily as a feasibility result and is impractical and not post-quantum secure due to its reliance on groups of unknown order. The second (Garetta et al., CRYPTO 2025) introduces the weaker notion of \emph{relaxed} Mod-PCS, but is not fully succinct: committing to a multilinear polynomial with $N$ terms and $B$-bit coefficients requires $O(\sqrt{N}B)$ proof size and verification time. We present a black-box transformation that builds relaxed Mod-PCS from any standard PCS, enabling new constructions. Instantiating our transformation with a tensor-code PCS yields the first relaxed Mod-PCS with $O(\log (N+B))$ proof size and verifier time, which is transparent and plausibly post-quantum secure. Using this scheme within the framework of Garetta et al., we obtain the first fully succinct SNARK for the Customizable Constraint System over $\mathbb{Z}_B$, achieving $O(B\log N + N\log N \log B)$ prover time and $O(\log (N+B))$ verifier time and proof size. Our approach relies on a commitment-switching technique for integer polynomials and a new batched integer commitment scheme from any PCS. We further introduce improved arguments for integer addition and multiplication, correctness of the number-theoretic transform, and general Diophantine relations over committed integers.

Note: Bibliography Problem Fixed Author affiliation changed

@misc{cryptoeprint:2026/347,
      author = {Alireza Shirzad and Sriram Sridhar and Dimitrios Papadopoulos and Charalampos Papamanthou},
      title = {Relaxed Modular {PCS} from Arbitrary {PCS} and Applications to {SNARKs} for Integers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/347},
      year = {2026},
      url = {https://eprint.iacr.org/2026/347}
}