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

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

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2023
lattice-based cryptographysnark
Contact author(s)
valerio cini @ ait ac at
russell lai @ aalto fi
giulio malavolta @ unibocconi it
2023-09-24: approved
2023-09-18: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.