CryptoDB
Lattice-based Succinct Arguments from Vanishing Polynomials
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2023 |
| 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 \emph{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: \begin{enumerate} \item The first recursive folding (i.e. Bulletproofs-like) protocol for linear relations with \emph{polylogarithmic} verifier runtime. Traditionally, the verifier runtime has been the efficiency bottleneck for such protocols (regardless of the underlying assumptions). \item The first verifiable delay function (VDF) based on lattices, building on a recently introduced sequential relation. \item 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]. \end{enumerate} |
BibTeX
@inproceedings{crypto-2023-33162,
title={Lattice-based Succinct Arguments from Vanishing Polynomials},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-38545-2_3},
author={Valerio Cini and Russell W. F. Lai and Giulio Malavolta},
year=2023
}