Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.


Sometimes You Can’t Distribute Random-Oracle-Based Proofs

September 27, 2023


Jack Doerner - Technion (Israel)


Abstract. In this talk, we discuss the conditions under which straight-line extractable non-interactive zero knowledge proofs (NIZKs) in the random oracle model (i.e. without a common reference string) permit threshold realizations that are black-box in the same random oracle. We show that even in the semi-honest setting, any secure 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 size of the NIZK grows 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.The paper on which this talk is based is available online at

[Slides] [Video]

Presented at

MPTS 2023: NIST Workshop (virtual) on Multi-Party Threshold Schemes 2023

Event Details



Related Topics

Security and Privacy: cryptography

Created September 21, 2023, Updated October 25, 2023