Paper 2023/1405

Lattice-based Succinct Arguments from Vanishing Polynomials

Valerio Cini, Austrian Institute of Technology
Russell W. F. Lai, Aalto University
Giulio Malavolta, Bocconi University & Max Planck Institute for Security and Privacy
Abstract

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: - 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). - The first verifiable delay function (VDF) based on lattices, building on a recently introduced sequential relation. - The first lattice-based \emph{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].

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2023
Keywords
lattice-based cryptographysnark
Contact author(s)
valerio cini @ ait ac at
russell lai @ aalto fi
giulio malavolta @ unibocconi it
History
2023-09-24: approved
2023-09-18: received
See all versions
Short URL
https://ia.cr/2023/1405
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1405,
      author = {Valerio Cini and Russell W. F. Lai and Giulio Malavolta},
      title = {Lattice-based Succinct Arguments from Vanishing Polynomials},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1405},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1405}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.