International Association
for Cryptologic Research

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.

Grassroots organizers are people who work from within communities to effect economic, environmental, social, or political change. Engagement, communication, and trust between community members are vital to the success of grassroots movements. Grassroots organizers have therefore developed long-standing community-based trust and communication protocols that are grounded in physical community spaces such as schools, libraries, town halls, community centers, places of worship, parks, and streets. Digital networking tools afford organizers the ability to engage more people, quickly disseminate important information, and decentralize movements for change. However, they also increase the level of personal risk that communities face by organizing, since the visibility of personal information and communication on social media facilitates surveillance, disinformation, infiltration, and ultimately physical violence from law enforcement, hate groups, and foreign governments. In this talk, we will explore the question: How might we use cryptographic tools to adapt the existing trust and communication protocols of grassroots organizers from physical to digital spaces, without increasing the risk of surveillance, disinformation, and infiltration of grassroots movements?

Numerous cryptographic applications require efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoK) as a building block. Typically they rely on the Fiat-Shamir heuristic to do so, as security in the random-oracle model is considered good enough in practice. However, there is a troubling disconnect between the stand-alone security of such a protocol and its security as part of a larger, more complex system where several protocols may be running at the same time. Provable security in the general universal composition model (GUC model) of Canetti et al. is the best guarantee that nothing will go wrong when a system is part of a larger whole, even when all parties share a common random oracle. In this paper, we prove the minimal necessary properties of generally universally composable (GUC) NIZKPoK in any global random-oracle model, and show how to achieve efficient and GUC NIZKPoK in both the restricted programmable and restricted observable (non-programmable) global random-oracle models.