Paper 2026/2011

CauchyFold: Residue-Optimal High-Arity Lattice Folding via Scaled Cauchy Challenges

Abstract

Folding schemes combine a batch of relation instances into one accumulator. For quadratic relations, applying the fold directly creates a mixed term for every pair of inputs. We present CauchyFold, a lattice protocol that folds one accumulator with \(k\) fresh quadratic instances without enumerating these pairwise terms. The companion work [WX26] uses Cauchy folding coefficients to represent the mixed contribution through a vector-valued polynomial of degree below \(k\). We give two algorithms that compute its coefficients with quasi-linear arithmetic in \(k\) for fixed relation dimensions. The protocol commits this polynomial before the folding challenge. Since the folding coefficients need not be short integers, it computes the fold over an extension field and canonically re-encodes the result as bits. This preserves the accumulator’s commitment layout and honest opening bound. For classical resettable provers, we give explicit extraction-error and expected-time bounds for a folding node with a fixed-depth reduction chain. It recovers valid source openings or a short nonzero vector in the kernel of a commitment matrix. A compiled profile at \(k=1024\) uses 162.67 KiB of no-retry interactive communication, excluding incoming commitments and the CRS.