Paper 2022/941

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

Martin R. Albrecht, Royal Holloway University of London
Valerio Cini, AIT Austrian Institute of Technology
Russell W. F. Lai, Aalto University
Giulio Malavolta, Max Planck Institute for Security and Privacy
Sri AravindaKrishnan Thyagarajan, Carnegie Mellon University
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
Keywords
lattice-based cryptographysnarkvector commitmentfunctional commitment
Contact author(s)
valerio cini @ ait ac at
History
2023-02-08: last of 2 revisions
2022-07-20: received
See all versions
Short URL
https://ia.cr/2022/941
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2022/941,
      author = {Martin R. Albrecht and Valerio Cini and Russell W. F. Lai and Giulio Malavolta and Sri AravindaKrishnan Thyagarajan},
      title = {Lattice-Based {SNARKs}: Publicly Verifiable, Preprocessing, and Recursively Composable},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/941},
      year = {2022},
      url = {https://eprint.iacr.org/2022/941}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.