[Resource Topic] 2022/941: Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable

Welcome to the resource topic for 2022/941

Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable

Authors: Martin R. Albrecht, Valerio Cini, Russell W. F. Lai, Giulio Malavolta, and Sri AravindaKrishnan Thyagarajan


A succinct non-interactive argument of knowledge (SNARK) allows a prover to produce a short proof that certifies the veracity of a certain NP-statement. In the last decade, a large body of work has studied candidate constructions that are secure against quantum attackers. Unfortunately, no known candidate matches the efficiency and desirable features of (pre-quantum) constructions based on bilinear pairings. In this work, we make progress on this question. We propose the first lattice-based SNARK that simultaneously satisfies many desirable properties: It (i) is tentatively post-quantum secure, (ii) is publicly-verifiable, (iii) has a logarithmic-time verifier and (iv) has a purely algebraic structure making it amenable to efficient recursive composition. Our construction stems from a general technical toolkit that we develop to translate pairing-based schemes to lattice-based ones. At the heart of our SNARK is a new lattice-based vector commitment (VC) scheme supporting openings to constant-degree multivariate polynomial maps, which is a candidate solution for the open problem of constructing VC schemes with openings to beyond linear functions. However, the security of our constructions is based on a new family of lattice-based computational assumptions which naturally generalises the standard Short Integer Solution (SIS) assumption.

ePrint: https://eprint.iacr.org/2022/941

Talk: https://www.youtube.com/watch?v=3y8jF07-f_A

Slides: https://iacr.org/submit/files/slides/2022/crypto/crypto2022/193/slides.pdf

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 .

Nice blog posts accompany the paper:
Martin’s blog post on the k-R-ISIS (of Knowledge) Assumption
Russel’s blog post on the SNARK construction
Aravind’s blog post on the applications of their SNARK

Russel’s presentation at the Vector Commitment Day of Protocol Labs here