Welcome to the resource topic for 2023/1819
Title:
Beyond MPCintheHead: BlackBox Constructions of Short ZeroKnowledge Proofs
Authors: Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss
Abstract:In their seminal work, Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC`07) presented the MPCintheHead paradigm, which shows how to design ZeroKnowledge Proofs (ZKPs) from secure MultiParty Computation (MPC) protocols. This paradigm has since then revolutionized and modularized the design of efficient ZKP systems, with farreaching applications beyond ZKPs. However, to the best of our knowledge, all previous instantiations relied on fullysecure MPC protocols, and have not been able to leverage the fact that the paradigm only imposes relatively weak privacy and correctness requirements on the underlying MPC.
In this work, we extend the MPCintheHead paradigm to gamebased cryptographic primitives supporting homomorphic computations (e.g., fullyhomomorphic encryption, functional encryption, randomized encodings, homomorphic secret sharing, and more). Specifically, we present a simple yet generic compiler from these primitives to ZKPs which use the underlying primitive as a black box. We also generalize our paradigm to capture commitandprove protocols, and use it to devise tight blackbox compilers from Interactive (Oracle) Proofs to ZKPs, assuming OneWay Functions (OWFs).
We use our paradigm to obtain several new ZKP constructions:

The first ZKPs for NP relations \mathcal{R} computable in (polynomialtime uniform) NC^1, whose round complexity is bounded by a fixed constant (independent of the depth of \mathcal{R}'s verification circuit), with communication approaching witness length (specifically, n\cdot poly\left(\kappa\right), where n is the witness length, and \kappa is a security parameter), assuming DCR. Alternatively, if we allow the round complexity to scale with the depth of the verification circuit, our ZKPs can make blackbox use of OWFs.

Constantround ZKPs for NP relations computable in bounded polynomial space, with O\left(n\right)+o\left(m\right)\cdot poly\left(\kappa\right) communication assuming OWFs, where m is the instance length. This gives a blackbox alternative to a recent nonblackbox construction of Nassar and Rothblum (CRYPTO`22).

ZKPs for NP relations computable by a logspaceuniform family of depthd\left(m\right) circuits, with n\cdot poly\left(\kappa,d\left(m\right)\right) communication assuming OWFs. This gives a blackbox alternative to a result of Goldwasser, Kalai and Rothblum (JACM).
ePrint: https://eprint.iacr.org/2023/1819
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .