Welcome to the resource topic for 2024/1972
Title:
RoK, Paper, SISsors – Toolkit for Lattice-based Succinct Arguments
Authors: Michael Klooß, Russell W. F. Lai, Ngoc Khanh Nguyen, Michał Osadnik
Abstract:Lattice-based succinct arguments allow to prove bounded-norm satisfiability of relations, such as f(\vec{s}) = \vec{t} \bmod q and \|\vec{s}\|\leq \beta, over specific cyclotomic rings \mathcal{O}_\mathcal{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 \mathcal{K} which are not mutually compatible. In this work, we exhibit a diverse toolkit for constructing efficient lattice-based succinct arguments:
(i) We identify new subtractive sets for general cyclotomic fields \mathcal{K} and their maximal real subfields \mathcal{K}^+, which are useful as challenge sets, e.g. in arguments for exact norm bounds.
(ii) 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 \mathcal{K} which admits polynomial-size subtractive sets.
(iii) We propose a framework to use twisted trace maps, i.e. maps of the form \tau(z) = \frac{1}{N} \cdot \mathsf{Trace}_{\mathcal{K}/\mathbb{Q}}( \alpha \cdot z ), to embed \mathbb{Z}-inner-products as \mathcal{R}-inner-products for some structured subrings \mathcal{R} \subseteq \mathcal{O}_\mathcal{K} whenever the conductor has a square-free odd part.
(iv) 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 \vec{s} over any cyclotomic field \mathcal{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 \vec{s} satisfying f(\vec{s}) = \vec{t} \bmod q has binary coefficients, without soundness gap and with polynomial-size modulus q.
ePrint: https://eprint.iacr.org/2024/1972
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 .