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

Jonathan Bootle; Alessandro Chiesa; Katerina Sotiraki

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in CRYPTO 2023
Keywords: succinct arguments lattices short-integer-solution problem
Contact author(s): jbt @ zurich ibm com
alessandro chiesa @ epfl ch
katesot @ berkeley edu
History: 2023-06-16: revised; 2023-06-14: received; See all versions
Short URL: https://ia.cr/2023/930
License: CC BY

BibTeX

@misc{cryptoeprint:2023/930,
      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{https://eprint.iacr.org/2023/930}},
      url = {https://eprint.iacr.org/2023/930}
}