Paper 2023/1737

On the Security of Succinct Interactive 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

We study the security of a fundamental family of succinct interactive arguments in the standard model, 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, or assume 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 the first security bounds for the IBCS protocol. Prior works rely upon this protocol without proving its security; our result closes this gap. 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 \emph{Finale protocol}, is secure when realized with any \emph{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.

Available format(s)
Publication info
succinct interactive argumentsvector commitment schemes
Contact author(s)
alessandro chiesa @ epfl ch
dallagnol @ princeton edu
ziyi guan @ epfl ch
nicholas spooner @ warwick ac uk
2024-02-14: revised
2023-11-09: received
See all versions
Short URL
Creative Commons Attribution


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