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

Martin R. Albrecht; Valerio Cini; Russell W. F. Lai; Giulio Malavolta; Sri AravindaKrishnan Thyagarajan

doi:10.1007/978-3-031-15979-4_4

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

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

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

22 Citations (Scopus)

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.

Original language	English
Title of host publication	Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings
Editors	Yevgeniy Dodis, Thomas Shrimpton
Publisher	Springer
Pages	102-132
ISBN (Electronic)	978-3-031-15979-4
ISBN (Print)	978-3-031-15978-7
DOIs	https://doi.org/10.1007/978-3-031-15979-4_4
Publication status	Published - 13 Oct 2022
MoE publication type	A4 Conference publication
Event	International Cryptology Conference - Santa Barbara, Santa Barbara, United States Duration: 13 Aug 2022 → 18 Aug 2022 https://crypto.iacr.org/2022/

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13508 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Cryptology Conference
Abbreviated title	CRYPTO
Country/Territory	United States
City	Santa Barbara
Period	13/08/2022 → 18/08/2022
Internet address	https://crypto.iacr.org/2022/

Access to Document

10.1007/978-3-031-15979-4_4

https://eprint.iacr.org/2022/941Licence: CC0

Cite this

Albrecht, M. R., Cini, V., Lai, R. W. F., Malavolta, G., & Thyagarajan, S. A. (2022). Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable. In Y. Dodis, & T. Shrimpton (Eds.), Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings (pp. 102-132). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13508 LNCS). Springer. https://doi.org/10.1007/978-3-031-15979-4_4

Albrecht, Martin R. ; Cini, Valerio ; Lai, Russell W. F. et al. / Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable. Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings. editor / Yevgeniy Dodis ; Thomas Shrimpton. Springer, 2022. pp. 102-132 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f08be66c95eb4596941ef3b3ecd121d4,

title = "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.",

author = "Albrecht, {Martin R.} and Valerio Cini and Lai, {Russell W. F.} and Giulio Malavolta and Thyagarajan, {Sri AravindaKrishnan}",

year = "2022",

month = oct,

day = "13",

doi = "10.1007/978-3-031-15979-4_4",

language = "English",

isbn = "978-3-031-15978-7",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "102--132",

editor = "Yevgeniy Dodis and Thomas Shrimpton",

booktitle = "Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings",

address = "Germany",

note = "International Cryptology Conference, CRYPTO ; Conference date: 13-08-2022 Through 18-08-2022",

url = "https://crypto.iacr.org/2022/",

}

Albrecht, MR, Cini, V, Lai, RWF, Malavolta, G & Thyagarajan, SA 2022, Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable. in Y Dodis & T Shrimpton (eds), Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13508 LNCS, Springer, pp. 102-132, International Cryptology Conference, Santa Barbara, California, United States, 13/08/2022. https://doi.org/10.1007/978-3-031-15979-4_4

Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable. / Albrecht, Martin R.; Cini, Valerio; Lai, Russell W. F. et al.
Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings. ed. / Yevgeniy Dodis; Thomas Shrimpton. Springer, 2022. p. 102-132 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13508 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

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

AU - Albrecht, Martin R.

AU - Cini, Valerio

AU - Lai, Russell W. F.

AU - Malavolta, Giulio

AU - Thyagarajan, Sri AravindaKrishnan

PY - 2022/10/13

Y1 - 2022/10/13

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

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

UR - http://www.scopus.com/inward/record.url?scp=85141692075&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-15979-4_4

DO - 10.1007/978-3-031-15979-4_4

M3 - Conference article in proceedings

SN - 978-3-031-15978-7

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 102

EP - 132

BT - Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings

A2 - Dodis, Yevgeniy

A2 - Shrimpton, Thomas

PB - Springer

T2 - International Cryptology Conference

Y2 - 13 August 2022 through 18 August 2022

ER -

Albrecht MR, Cini V, Lai RWF, Malavolta G, Thyagarajan SA. Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable. In Dodis Y, Shrimpton T, editors, Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings. Springer. 2022. p. 102-132. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-15979-4_4