CryptoDB
Lattice-Based Succinct Arguments for NP with Polylogarithmic-Time Verification
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2023 |
| Abstract: | The ideal argument system should offer small proof sizes in practice, succinct verification, and post-quantum security based on standard assumptions. However, so far, all known constructions fall short. Succinct argument systems which rely on the Merkle-hashing paradigm introduced by Kilian (STOC 92) suffer from large proof sizes in practice due to the use of generic cryptographic primitives. Popular alternatives, which obtain smaller proof sizes by exploiting the structure of homomorphic commitment schemes, either rely on quantum-insecure assumptions, or fail to provide succinct verification. In this paper, we construct the first lattice-based succinct interactive argument system for NP statements with succinct verification that departs from the Merkle-hashing paradigm, and exploits the homomorphic properties of lattice-based commitments. For an arithmetic circuit with N gates, our construction achieves polylog(N) communication and polylog(N) verification time based on the hardness of the Ring Short- Integer-Solution (RSIS) problem. The core technique in our construction is a delegation protocol built from commitment schemes based on leveled bilinear modules, a new notion that we deem of independent interest. We show that leveled bilinear modules can be realized from both pre-quantum and post-quantum cryptographic assumptions. |
BibTeX
@inproceedings{crypto-2023-33221,
title={Lattice-Based Succinct Arguments for NP with Polylogarithmic-Time Verification},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-38545-2_8},
author={Jonathan Bootle and Alessandro Chiesa and Katerina Sotiraki},
year=2023
}