Welcome to the resource topic for 2025/2124
Title:
SALSAA – Sumcheck-Aided Lattice-based Succinct Arguments and Applications
Authors: Shuto Kuriyama, Russell W. F. Lai, Michał Osadnik, Lorenzo Tucci
Abstract:We present SALSAA, a more efficient and more versatile extension of the state-of-the-art lattice-based fully-succinct argument frameworks, RoK, paper, SISsors (RPS)'' and RoK and Roll (RnR)‘’ [Klooß, Lai, Nguyen, and Osadnik; ASIACRYPT’24, '25], integrating the sumcheck technique as a main component. This integration enables us to design an efficient norm-check protocol (controlling the norm during witness extraction) with a strictly linear-time prover while reducing proof sizes by 2-3$\times$ compared to the previous quasi-linear-time norm-check in RPS/RnR, eliminating a central performance bottleneck.
The sumcheck integration also allows us to natively support a wider class of relations, including rank-1 constraint systems (R1CS), which are widely used to express real-world computations.
To demonstrate the versatility and efficiency of our framework, we showcase three impactful applications achieved by different RoKs (Reductions of Knowledge) compositions:
(i) a lattice-based succinct argument of knowledge with a linear-time prover, achieving a verifier time of 41 ms, prover runtime of 10.61 s, and proof size of 979 KB for a witness of 2^{28} \mathbb{Z}_q elements;
(ii) a polynomial commitment scheme with matching performance; and
(iii) the first lattice-based folding scheme natively operating on \ell_2-norm-bounded witnesses, achieving highly efficient verification in 2.28 ms and producing a proof of just 73 KB for a witness of 2^{28} \mathbf{Z}_q elements, outperforming prior works for the family of linear relations.
We provide a modular, concretely efficient Rust implementation of our framework, benchmarked over cyclotomic rings with AVX-512-accelerated NTT-based arithmetic, demonstrating the practical efficiency of our approach.
ePrint: https://eprint.iacr.org/2025/2124
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .