Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Topic Page
Marketing
Events
Start single access now
Access for companies
12th International Engine Congress 2025 | 25. + 26. February 2025

Meeting Place for the Powertrain and Sustainable Fuels Community

The congress will examine the future role of the internal combustion engine and its non-fossil fuels from a global perspective with leading experts. Be part of it! More information and booking options are available on our website.
EXTENDED SEARCH
Log in
Top
Published in:
Read chapter Read first chapter

2025 | OriginalPaper | Chapter

Security Bounds for Proof-Carrying Data from Straightline Extractors

Authors : Alessandro Chiesa, Ziyi Guan, Shahar Samocha, Eylon Yogev

Published in: Theory of Cryptography

Publisher: Springer Nature Switzerland

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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 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 recursive STARKs used in blockchain systems. Our work could be viewed as partial evidence justifying the parameter choices for recursive STARKs made by practitioners.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Batch Arguments to NIZKs from One-Way Functions
Footnotes
1
A separate line of work constructs IVC for deterministic computations from falsifiable cryptographic assumptions using different tools (see [39] and references therein). These elegant constructions are less relevant to the motivation of this paper as, typically, applications of PCD and IVC require supporting nondeterministic computations.
 
2
The statement that “there exists a valid proof” refers to the verifier of the underlying SNARK or accumulation scheme. As such, the resulting PCD scheme makes non-black-box use of the verifier for the underlying scheme.
 
3
There are other PCD constructions of practical interest that do not fit our setting (e.g., those based on knowledge-of-exponent assumptions). Achieving security reductions that yield useful concrete security bounds for these remains an open problem.
 
4
Such reductions are unlikely to exist in the standard model [29], as PCD can be used to construct a SNARK [8].
 
5
The random oracle methodology is widely used across cryptography to set the security parameters of protocols that rely on cryptographic hash functions (and possibly other cryptographic building blocks). The methodology must, nevertheless, be applied with caution because it does not work for every protocol [15].
 
6
Relativization is distinct from other limitations of SNARKs in the presence of oracles: [28] studies limitations of knowledge extraction for adversaries that access oracles exogenous to the SNARK scheme itself (e.g., the signing oracle of a signature scheme).
 
7
The extraction time is as before and, necessarily, depends on \(N\), as the extractor outputs a distributed computation of size \(N\).
 
8
In particular, the transcript size and transcript depth may or may not be bounded for a particular compliance predicate \(\phi \).
 
9
The dependence is on transcript depth rather than transcript size because the security reduction simultaneously extracts from all SNARK proofs at the same transcript depth (see, e.g., [20]).
 
10
Achieving straightline extraction in the ROM is straightforward; see prior work [6, 23‐25, 36].
 
11
A STARK (as deployed in that system) is the heuristic instantiation (via the random oracle methodology) of a SNARK in the ROM, with straightline knowledge soundness, that is based on a certain IOP.
 
Literature
1.
2.
Bartusek, J., Bronfman, L., Holmgren, J., Ma, F., Rothblum, R.D.: On the (in)security of Kilian-based SNARGs. In: Proceedings of the 17th Theory of Cryptography Conference, pp. 522–551. TCC 2019 (2019)
3.
4.
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, pp. 62–73. CCS 1993 (1993)
5.
Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable zero knowledge with no trusted setup. In: Proceedings of the 39th Annual International Cryptology Conference, pp. 733–764. CRYPTO 2019 (2019)
6.
Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Proceedings of the 14th Theory of Cryptography Conference, pp. 31–60. TCC 2016-B (2016)
7.
8.
Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKs and proof-carrying data. In: Proceedings of the 45th ACM Symposium on the Theory of Computing, pp. 111–120. STOC 2013 (2013)
9.
Boneh, D., Drake, J., Fisch, B., Gabizon, A.: Halo infinite: proof-carrying data from additive polynomial commitments. In: Proceedings of the 41st Annual International Cryptology Conference, pp. 649–680. CRYPTO 2021 (2021)
10.
Bonneau, J., Meckler, I., Rao, V., Shapiro, E.: Coda: Decentralized cryptocurrency at scale. IACR Cryptology ePrint Archive, Report 2020/352 (2020)
11.
Bowe, S., Grigg, J., Hopwood, D.: Halo: Recursive proof composition without a trusted setup. Cryptology ePrint Archive, Report 2019/1021 (2019)
12.
Bünz, B., Chen, B.: ProtoStar: generic efficient accumulation/folding for special-soundprotocols. In: Proceedings of the 29th International Conference on the Theory and Application of Cryptology and Information Security, pp. 77–110. ASIACRYPT 2023 (2023)
13.
Bünz, B., Chiesa, A., Lin, W., Mishra, P., Spooner, N.: Proof-carrying data without succinct arguments. In: Proceedings of the 41st Annual International Cryptology Conference, pp. 681–710. CRYPTO 2021 (2021)
14.
Bünz, B., Chiesa, A., Mishra, P., Spooner, N.: Proof-carrying data from accumulation schemes. In: Proceedings of the 18th Theory of Cryptography Conference, pp. 1–18. TCC 2020 (2020)
15.
16.
Chen, M., Chiesa, A., Gur, T., O’Connor, J., Spooner, N.: Proof-carrying data from arithmetized random oracles. In: Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 379–404. EUROCRYPT 2023 (2023)
17.
Chen, M., Chiesa, A., Spooner, N.: On succinct non-interactive arguments in relativized worlds. In: Proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT 2022 (2022)
18.
Chen, W., Chiesa, A., Dauterman, E., Ward, N.P.: Reducing participation costs via incremental verification for ledger systems. Cryptology ePrint Archive, Report 2020/1522 (2020)
19.
Chiesa, A., Liu, S.: On the impossibility of probabilistic proofs in relativized worlds. In: Proceedings of the 11th Innovations in Theoretical Computer Science Conference. ITCS 2020 (2020)
20.
Chiesa, A., Ojha, D., Spooner, N.: Fractal: Post-quantum and transparent recursive proofs from holography. In: Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 769–793. EUROCRYPT 2020 (2020)
21.
Chiesa, A., Tromer, E.: Proof-carrying data and hearsay arguments from signature cards. In: Proceedings of the 1st Symposium on Innovations in Computer Science, pp. 310–331. ICS 2010 (2010)
22.
Chiesa, A., Tromer, E., Virza, M.: Cluster computing in zero knowledge. In: Proceedings of the 34th Annual International Conference on Theory and Application of Cryptographic Techniques, pp. 371–403. EUROCRYPT 2015 (2015)
23.
Chiesa, A., Yogev, E.: Subquadratic SNARGs in the random oracle model. In: Proceedings of the 41st Annual International Cryptology Conference, pp. 711–741. CRYPTO 2021 (2021)
24.
Chiesa, A., Yogev, E.: Tight security bounds for Micali’s SNARGs. In: Proceedings of the 19th Theory of Cryptography Conference, pp. 401–434. TCC 2021 (2021)
25.
26.
Chong, S., Tromer, E., Vaughan, J.A.: Enforcing language semantics using proof-carrying data. Cryptology ePrint Archive, Report 2013/513 (2013)
27.
28.
Fiore, D., Nitulescu, A.: On the (in)security of SNARKs in the presence of oracles. In: Proceedings of the 14th Theory of Cryptography Conference, pp. 108–138. TCC 2016-B (2016)
29.
Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 99–108. STOC 2011 (2011)
30.
Goldberg, L., Papini, S., Riabzev, M.: Cairo: a turing-complete STARK-friendly CPU architecture. IACR Cryptology ePrint Archive, Report 2021/1063 (2021)
31.
Hall-Andersen, M., Nielsen, J.B.: On valiant’s conjecture: impossibility of incrementally verifiable computation from random oracles. In: Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT 2023 (2023)
32.
Kattis, A., Bonneau, J.: Proof of necessary work: Succinct state verification with fairness guarantees. In: Proceedings of the 27th Financial Cryptography and Data Security. FC 2023 (2023)
33.
Kothapalli, A., Setty, S.: SuperNova: proving universal machine executions without universal circuits. Cryptology ePrint Archive, Paper 2022/1758 (2022)
34.
Kothapalli, A., Setty, S., Tzialla, I.: Nova: recursive zero-knowledge arguments from folding schemes. In: Proceedings of the 42nd Annual International Cryptology Conference, pp. 359–388. CRYPTO 2022 (2022)
35.
36.
Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253–1298 (2000). preliminary version appeared in FOCS 1994
37.
Naveh, A., Tromer, E.: PhotoProof: cryptographic image authentication for any set of permissible transformations. In: Proceedings of the 37th IEEE Symposium on Security and Privacy, pp. 255–271. S &P 2016 (2016)
38.
39.
Paneth, O., Pass, R.: Incrementally verifiable computation via rate-1 batch arguments. In: Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science, pp. 1045–1056. FOCS 2022 (2022)
40.
41.
42.
43.
44.
Tyagi, N., Fisch, B., Zitek, A., Bonneau, J., Tessaro, S.: VeRSA: Verifiable registries with efficient client audits from RSA authenticated dictionaries. In: Proceedings of the 29th ACM Conference on Computer and Communications Security. pp. 2793–2807. CCS ’22 (2022)
45.
Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In: Proceedings of the 5th Theory of Cryptography Conference, pp. 1–18. TCC 2008 (2008)
Metadata
Title
Security Bounds for Proof-Carrying Data from Straightline Extractors
Authors
Alessandro Chiesa
Ziyi Guan
Shahar Samocha
Eylon Yogev
Copyright Year
2025
Book
Theory of Cryptography

Print ISBN: 978-3-031-78016-5

Electronic ISBN: 978-3-031-78017-2

Copyright Year: 2025

DOI
https://doi.org/10.1007/978-3-031-78017-2_16

Premium Partner

    Image Credits