Paper 2025/199

Sublinear Proofs over Polynomial Rings

Abstract

Designing non-interactive proof systems, such as NIZK or SNARKs, for lattice-based protocols is a well-motivated problem with numerous applications including aggregate signatures, verifiable random functions, group signatures, verifiable homomorphic encryption schemes, and others. Although many works have made efforts toward efficient lattice-based protocols, several challenges remain. In particular, a major challenge, as highlighted by Ganesh et al. (Journal of Cryptology 2023) and Zhang et al. (CCS 2025), is the algebraic gap between polynomial rings, which are typically used in lattice-based constructions, and fields, which are commonly used in the constructions of non-interactive proofs. In this paper, we introduce a novel technique called ring switching, which bridges this gap by transforming proofs over polynomial-ring arithmetic into proofs over finite fields or Galois rings with prime power modulus. Using ring switching, we construct an efficient non-interactive argument of knowledge for Ring-R1CS over $\mathbb{Z}_Q[X]/(X^N+1)$ for arbitrary prime-power moduli $Q$. Our construction achieves sublinear proof size and enables significantly faster verification by eliminating costly ring multiplications. The ring switching framework is compatible with parameter regimes used in practical lattice-based cryptosystems, including NTT-friendly and power-of-two moduli. Subsequent works building on this technique further demonstrate its efficiency, achieving substantial verification time improvements in lattice-based polynomial commitments and verifiable homomorphic encryption schemes.

Note: Add a comparison paragraph