The Library
Proof-carrying data from arithmetized random oracles
Tools
Chen, Megan, Chiesa, Alessandro, Gur, Tom, O’Connor, Jack and Spooner, Nicholas (2023) Proof-carrying data from arithmetized random oracles. In: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 23–27 Apr 2023. Published in: Advances in Cryptology – EUROCRYPT 2023, 14005 pp. 379-404. ISBN 9783031306167. doi:10.1007/978-3-031-30617-4_13 ISSN 0302-9743.
|
PDF
WRAP-proof-carrying-data-arithmetized-random-oracles-Spooner-2023.pdf - Accepted Version - Requires a PDF viewer. Download (1826Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-031-30617-4_13
Abstract
Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. SNARKs with desirable properties such as transparent setup are constructed in the random oracle model. However, using such SNARKs to construct PCD requires heuristically instantiating the oracle and using it in a non-black-box way. [CCS22] constructed SNARKs in the low-degree random oracle model, circumventing this issue, but instantiating their model in the real world appears difficult.
In this paper, we introduce a new model: the arithmetized random oracle model (AROM). We provide a plausible standard-model (software-only) instantiation of the AROM, and we construct PCD in the AROM, given only a standard-model collision-resistant hash function. Furthermore, our PCD construction is for arbitrary-depth compliance predicates. We obtain our PCD construction by showing how to construct SNARKs in the AROM for computations that query the oracle, given an accumulation scheme for oracle queries in the AROM. We then construct such an accumulation scheme for the AROM.
We give an efficient “lazy sampling” algorithm (an emulator) for the ARO up to some error. Our emulator enables us to prove the security of cryptographic constructs in the AROM and that zkSNARKs in the ROM also satisfy zero-knowledge in the AROM. The algorithm is non-trivial, and relies on results in algebraic query complexity and the combinatorial nullstellensatz.
Item Type: | Conference Item (Paper) | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Combinatorial analysis, Computational complexity, Data encryption (Computer science), Cryptography -- Mathematics, Proof theory | |||||||||||||||
Series Name: | Lecture Notes in Computer Science | |||||||||||||||
Journal or Publication Title: | Advances in Cryptology – EUROCRYPT 2023 | |||||||||||||||
Publisher: | Springer | |||||||||||||||
ISBN: | 9783031306167 | |||||||||||||||
ISSN: | 0302-9743 | |||||||||||||||
Book Title: | Advances in Cryptology – EUROCRYPT 2023 | |||||||||||||||
Official Date: | 15 April 2023 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 14005 | |||||||||||||||
Page Range: | pp. 379-404 | |||||||||||||||
DOI: | 10.1007/978-3-031-30617-4_13 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
Date of first compliant deposit: | 14 June 2023 | |||||||||||||||
Date of first compliant Open Access: | 15 April 2024 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Conference Paper Type: | Paper | |||||||||||||||
Title of Event: | 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques | |||||||||||||||
Type of Event: | Conference | |||||||||||||||
Location of Event: | Lyon, France | |||||||||||||||
Date(s) of Event: | 23–27 Apr 2023 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year