Lattice-Based Succinct Arguments from Vanishing Polynomials

Valerio Cini*, Russell W.F. Lai, Giulio Malavolta

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

5 Sitaatiot (Scopus)

Abstrakti

Succinct arguments allow a prover to convince a verifier of the validity of any statement in a language, with minimal communication and verifier’s work. Among other approaches, lattice-based protocols offer solid theoretical foundations, post-quantum security, and a rich algebraic structure. In this work, we present some new approaches to constructing efficient lattice-based succinct arguments. Our main technical ingredient is a new commitment scheme based on vanishing polynomials, a notion borrowed from algebraic geometry. We analyse the security of such a commitment scheme, and show how to take advantage of the additional algebraic structure to build new lattice-based succinct arguments. A few highlights amongst our results are: (i)The first recursive folding (i.e. Bulletproofs-like) protocol for linear relations with polylogarithmic verifier runtime. Traditionally, the verifier runtime has been the efficiency bottleneck for such protocols (regardless of the underlying assumptions).(ii)The first verifiable delay function (VDF) based on lattices, building on a recently introduced sequential relation.(iii)The first lattice-based linear-time prover succinct argument for NP, in the preprocessing model. The soundness of the scheme is based on (knowledge)-k-R-ISIS assumption [Albrecht et al., CRYPTO’22].

AlkuperäiskieliEnglanti
OtsikkoAdvances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings, Part II
ToimittajatHelena Handschuh, Anna Lysyanskaya
KustantajaSpringer
Sivut72-105
Sivumäärä34
ISBN (painettu)978-3-031-38544-5
DOI - pysyväislinkit
TilaJulkaistu - 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaInternational Cryptology Conference - Santa Barbara, Yhdysvallat
Kesto: 20 elok. 202324 elok. 2023
Konferenssinumero: 43

Julkaisusarja

NimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
KustantajaSpringer
Vuosikerta14082 LNCS
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349

Conference

ConferenceInternational Cryptology Conference
LyhennettäCRYPTO
Maa/AlueYhdysvallat
KaupunkiSanta Barbara
Ajanjakso20/08/202324/08/2023

Sormenjälki

Sukella tutkimusaiheisiin 'Lattice-Based Succinct Arguments from Vanishing Polynomials'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä