Paper 2023/1737
Concrete Security for Succinct Arguments from Vector Commitments
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
-
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} }