Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Proof-Carrying Data from Arithmetized Random Oracles
 
conference paper

Proof-Carrying Data from Arithmetized Random Oracles

Chen, Megan
•
Chiesa, Alessandro  
•
Gur, Tom
Show more
April 15, 2023
Advances in Cryptology – EUROCRYPT 2023 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II
42nd Annual International Conference on Theory and Applications of Cryptographic Techniques

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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-031-30617-4_13
Web of Science ID

WOS:001276439600013

Author(s)
Chen, Megan

Boston University

Chiesa, Alessandro  

École Polytechnique Fédérale de Lausanne

Gur, Tom

University of Warwick

O'Connor, Jack

University of Warwick

Spooner, Nicholas

University of Warwick

Date Issued

2023-04-15

Publisher

Springer

Published in
Advances in Cryptology – EUROCRYPT 2023 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II
ISBN of the book

978-3-031-30616-7

Series title/Series vol.

Lecture Notes in Computer Science; 14005

ISSN (of the series)

0302-9743

Subjects

proof-carrying data

•

random oracle model

•

arithmetization

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
COMPSEC  
Event nameEvent acronymEvent placeEvent date
42nd Annual International Conference on Theory and Applications of Cryptographic Techniques

Eurocrypt 2023

Lyon, France

2023-04-23 - 2023-04-27

FunderFunding(s)Grant NumberGrant URL

UK Research & Innovation (UKRI)

MR/S031545/1

EPRSC New Horizons

EP/X018180/1

Engineering and Physical Sciences Research Council through the Mathematics of Systems Centre for Doctoral Training at the University of Warwick

EP/S022244/1

Show more
Available on Infoscience
March 7, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/247627
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés