Paper 2023/1646
Security Bounds for Proof-Carrying Data from Straightline Extractors
Abstract
Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Real-world deployments of PCD have sparked keen interest within the applied community and industry. Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, known security analyses incur expensive blowups, which practitioners have disregarded as the analyses would lead to setting parameters that are prohibitively expensive. In this work we study the concrete security of recursive composition, with the goal of better understanding how to reasonably set parameters for certain PCD constructions of practical interest. Our main result is that PCD obtained from SNARKs with \emph{straightline knowledge soundness} has essentially the same security as the underlying SNARK (i.e., recursive composition incurs essentially no security loss). We describe how straightline knowledge soundness is achieved by SNARKs in several oracle models, which results in a highly efficient security analysis of PCD that makes black-box use of the SNARK's oracle (there is no need to instantiated the oracle to carry out the security reduction). As a notable application, our work offers an idealized model that provides new, albeit heuristic, insights for the concrete security of \emph{recursive STARKs} used in blockchain systems. Our work could be viewed as partial evidence justifying the parameter choices for recursive STARKs made by practitioners.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in TCC 2024
- Keywords
- proof-carrying datasuccinct non-interactive argumentsrelativizationconcrete security
- Contact author(s)
-
alessandro chiesa @ epfl ch
ziyi guan @ epfl ch
shahars @ starkware co
eylon yogev @ biu ac il - History
- 2024-09-11: last of 2 revisions
- 2023-10-24: received
- See all versions
- Short URL
- https://ia.cr/2023/1646
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1646, author = {Alessandro Chiesa and Ziyi Guan and Shahar Samocha and Eylon Yogev}, title = {Security Bounds for Proof-Carrying Data from Straightline Extractors}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1646}, year = {2023}, url = {https://eprint.iacr.org/2023/1646} }