Paper 2026/359

Cyclo: Lightweight Lattice-based Folding via Partial Range Checks

Abstract

Folding is a powerful technique for constructing efficient succinct proof systems, especially for computations that are expressed in a streaming fashion. In this work, we present Cyclo, a new lattice-based folding protocol that improves upon LatticeFold+ [Boneh and Chen '25] in multiple dimensions and which incorporates, among others, the pay-per-bit techniques from Neo when folding constraints expressed over a field $\mathbb{F}_q$ [Nguyen and Setty '25]. Cyclo proposes a new framework for building lattice-based folding schemes that eliminates the need for norm checks \emph{on the accumulator} by adopting an amortized norm-refreshing design, ensuring that the witness norm grows additively per round within a (generously) bounded number of folds. This design simplifies the protocol and reduces prover overhead. In particular, Cyclo only performs range checks on the input \emph{non-accumulated} witness, and when applied to fold constraints over $\mathbb{F}_q$, it does not decompose any witnesses into low-norm chunks within the folding protocol itself. Cyclo, supporting a complete family of cyclotomic rings, combines two simple building blocks: an extension commitment that reduces the norm of the witness by decomposing it and recommitting, and an $\ell_\infty$ range test via a sum-check protocol. We demonstrate, by proving communication and runtime estimates, that the construction results in an efficient and proof-size-friendly folding scheme. We also establish an algebraic connection between $\mathcal{R}_q$ and $\mathbb{F}_q$ using the polynomial evaluation map, enabling efficient reduction from R1CS/CCS over $\mathbb{F}_q$ to a linear relation over $\mathcal{R}_q$, providing a new and simpler formulation of the techniques in [Nguyen and Setty '25]. In practical settings, Cyclo achieves succinct proof sizes on the order of $30$ KB, improving by an order of magnitude over LatticeFold+. Our efficiency benchmarks indicate that our protocol also outperforms LatticeFold+ in practice.