International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Sometimes You Can't Distribute Random Oracle Based Proofs

Authors:
Jack Doerner , Brown University, Technion, Reichman University
Yashvanth Kondi , Silence Labs (Deel)
Leah Namisa Rosenbloom , Brown University
Download:
DOI: 10.1007/978-3-031-68388-6_12 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2024
Abstract: We investigate the conditions under which straight-line extractable NIZKs in the random oracle model (i.e. without a CRS) permit multiparty realizations that are black-box in the same random oracle. We show that even in the semi-honest setting, any MPC protocol to compute such a NIZK cannot make black-box use of the random oracle or a hash function instantiating it if security against all-but-one corruptions is desired, unless the number of queries made by the verifier to the oracle grows linearly with the number of parties. This presents a fundamental barrier to constructing efficient protocols to securely distribute the computation of NIZKs (and signatures) based on MPC-in-the-head, PCPs/IOPs, and sigma protocols compiled with transformations due to Fischlin, Pass, or Unruh. When the adversary is restricted to corrupt only a constant fraction of parties, we give a positive result by means of a tailored construction, which demonstrates that our impossibility does not extend to weaker corruption models in general.
BibTeX
@inproceedings{crypto-2024-34297,
  title={Sometimes You Can't Distribute Random Oracle Based Proofs},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-68388-6_12},
  author={Jack Doerner and Yashvanth Kondi and Leah Namisa Rosenbloom},
  year=2024
}