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

##### 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.

Available format(s)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
Keywords
lattice-based cryptography snark vector commitment functional commitment
Contact author(s)
valerio cini @ ait ac at
History
2022-07-20: approved
See all versions
Short URL
https://ia.cr/2022/941

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},
note = {\url{https://eprint.iacr.org/2022/941}},
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.