Paper 2023/1405
Lattice-based Succinct Arguments from Vanishing Polynomials
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)
- 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
-
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} }