(2026-04) Improving LatticeFold+ with ℓ2-norm Checks
2026-04-13
Folding schemes enable incremental proving by compressing many relation instances into a small accumulator. Recent lattice-based constructions such as LatticeFold+ [CRYPTO '25] achieve post-quantum security, but prover performance is still dominated by expensive range checks used to control witness growth during folding and extraction. We present a final -norm-check design that combines random-projection constraints (in the spirit of Rok and Roll [ASIACRYPT '25]) with an exact shortening step (in the spirit of SALSAA [ePrint 2025/2124]) to recover the original witness -norm bound at extraction time. Integrated into the LatticeFold+ composition, this gives iterative folding with controlled norm growth, preserved binding and knowledge-soundness goals, and substantially lower prover cost on the dominant norm-check path, while maintaining a similar proof size and verification cost. Our approach is modular and can be applied to other lattice-based folding schemes, providing a practical path for efficient post-quantum folding constructions.