RoK, Paper, SISsors Toolkit for Lattice-Based Succinct Arguments

Lattice-based succinct arguments allow to prove bounded-norm satisfiability of relations, such as f(s)=tmodq and ‖s‖≤β, over specific cyclotomic rings O_K, with proof size polylogarithmic in the witness size. However, state-of-the-art protocols require either 1) a super-polynomial size modulus q due to a soundness gap in the security argument, or 2) a verifier which runs in time linear in the witness size. Furthermore, construction techniques often rely on specific choices of K which are not mutually compatible. In this work, we exhibit a diverse toolkit for constructing efficient lattice-based succinct arguments: We identify new subtractive sets for general cyclotomic fields K and their maximal real subfields K⁺, which are useful as challenge sets, e.g. in arguments for exact norm bounds.We construct modular, verifier-succinct reductions of knowledge for the bounded-norm satisfiability of structured-linear/inner-product relations, without any soundness gap, under the vanishing SIS assumption, over any K which admits polynomial-size subtractive sets.We propose a framework to use twisted trace maps, i.e. maps of the form τ(z)=1N·Trace_K/Q(α·z), to embed Z-inner-products as R-inner-products for some structured subrings R⊆O_K whenever the conductor has a square-free odd part.We present a simple extension of our reductions of knowledge for proving the consistency between the coefficient embedding and the Chinese Remainder Transform (CRT) encoding of s over any cyclotomic field K with a smooth conductor, based on a succinct decomposition of the CRT map into automorphisms, and a new, simple succinct argument for proving automorphism relations. We identify new subtractive sets for general cyclotomic fields K and their maximal real subfields K⁺, which are useful as challenge sets, e.g. in arguments for exact norm bounds. We construct modular, verifier-succinct reductions of knowledge for the bounded-norm satisfiability of structured-linear/inner-product relations, without any soundness gap, under the vanishing SIS assumption, over any K which admits polynomial-size subtractive sets. We propose a framework to use twisted trace maps, i.e. maps of the form τ(z)=1N·Trace_K/Q(α·z), to embed Z-inner-products as R-inner-products for some structured subrings R⊆O_K whenever the conductor has a square-free odd part. We present a simple extension of our reductions of knowledge for proving the consistency between the coefficient embedding and the Chinese Remainder Transform (CRT) encoding of s over any cyclotomic field K with a smooth conductor, based on a succinct decomposition of the CRT map into automorphisms, and a new, simple succinct argument for proving automorphism relations. Combining all techniques, we obtain, for example, verifier-succinct arguments for proving that s satisfying f(s)=tmodq has binary coefficients, without soundness gap and with polynomial-size modulus q.