Paper 2023/1381
Sometimes You Can’t Distribute Random-Oracle-Based Proofs
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published by the IACR in CRYPTO 2024
- Keywords
- Threshold CryptographyMultiparty ComputationStraight-line ExtractionNIZKZero-knowledgeSignatures
- Contact author(s)
-
j @ ckdoerner net
yash @ ykondi net
leah_rosenbloom @ brown edu - History
- 2024-06-01: revised
- 2023-09-14: received
- See all versions
- Short URL
- https://ia.cr/2023/1381
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1381,
author = {Jack Doerner and Yashvanth Kondi and Leah Namisa Rosenbloom},
title = {Sometimes You Can’t Distribute Random-Oracle-Based Proofs},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1381},
year = {2023},
url = {https://eprint.iacr.org/2023/1381}
}
