Paper 2023/1737

Concrete Security for Succinct Arguments from Vector Commitments

Alessandro Chiesa, École Polytechnique Fédérale de Lausanne
Marcel Dall'Agnol, Princeton University
Ziyi Guan, École Polytechnique Fédérale de Lausanne
Nicholas Spooner, University of Warwick, New York University
Abstract

We study the concrete security of a fundamental family of succinct interactive arguments, stemming from the works of Kilian (1992) and Ben-Sasson, Chiesa, and Spooner ("BCS", 2016). These constructions achieve succinctness by combining probabilistic proofs and vector commitments. Our first result concerns the succinct interactive argument of Kilian, realized with any probabilistically-checkable proof (PCP) and any vector commitment. We establish the tightest known bounds on the security of this protocol. Prior analyses incur large overheads unsuitable for concrete security, or assume special (and restrictive) properties of the underlying PCP. Our second result concerns an interactive variant of the BCS succinct non-interactive argument, which here we call IBCS, realized with any public-coin interactive oracle proof (IOP) and any vector commitment. We establish tight bounds on the security of this protocol. While this variant has been informally discussed in the literature, no prior security analysis, even asymptotic, existed before this work. Finally, we study the capabilities and limitations of succinct arguments based on vector commitments. We show that a generalization of the IBCS protocol, which we call the Finale protocol, is secure when realized with any public-query IOP (a notion that we introduce) that satisfies a natural "random continuation sampling" (RCS) property. We also show a partial converse: if the Finale protocol satisfies the RCS property (which in particular implies its security), then so does the underlying public-query IOP.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
succinct interactive argumentsconcrete securityvector commitment schemes
Contact author(s)
alessandro chiesa @ epfl ch
dallagnol @ cs princeton edu
ziyi guan @ epfl ch
nicholas spooner @ warwick ac uk
History
2023-11-13: approved
2023-11-09: received
See all versions
Short URL
https://ia.cr/2023/1737
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1737,
      author = {Alessandro Chiesa and Marcel Dall'Agnol and Ziyi Guan and Nicholas Spooner},
      title = {Concrete Security for Succinct Arguments from Vector Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1737},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1737}},
      url = {https://eprint.iacr.org/2023/1737}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.