Paper 2023/930

Lattice-Based Succinct Arguments for NP with Polylogarithmic-Time Verification

Jonathan Bootle, IBM Research Europe
Alessandro Chiesa, École Polytechnique Fédérale de Lausanne
Katerina Sotiraki, University of California, Berkeley

Succinct arguments that rely on the Merkle-tree paradigm introduced by Kilian (STOC 92) suffer from larger proof sizes in practice due to the use of generic cryptographic primitives. In contrast, succinct arguments with the smallest proof sizes in practice exploit homomorphic commitments. However these latter are quantum insecure, unlike succinct arguments based on the Merkle-tree paradigm. A recent line of works seeks to address this limitation, by constructing quantum-safe succinct arguments that exploit lattice-based commitments. The eventual goal is smaller proof sizes than those achieved via the Merkle-tree paradigm. Alas, known constructions lack succinct verification. In this paper, we construct the first interactive argument system for NP with succinct verification that, departing from the Merkle-tree paradigm, exploits the homomorphic properties of lattice-based commitments. For an arithmetic circuit with N gates, our construction achieves verification time polylog(N) 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 pre-quantum and from post-quantum cryptographic assumptions.

Note: Added full version.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2023
succinct argumentslatticesshort-integer-solution problem
Contact author(s)
jbt @ zurich ibm com
alessandro chiesa @ epfl ch
katesot @ berkeley edu
2023-06-16: revised
2023-06-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jonathan Bootle and Alessandro Chiesa and Katerina Sotiraki},
      title = {Lattice-Based Succinct Arguments for NP with Polylogarithmic-Time Verification},
      howpublished = {Cryptology ePrint Archive, Paper 2023/930},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.