CryptoDB
Beyond MPC-in-the-Head: Black-Box Constructions of Short Zero-Knowledge Proofs
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2023 |
| Abstract: | In their seminal work, Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC`07) presented the MPC-in-the-Head paradigm, which shows how to design Zero-Knowledge Proofs (ZKPs) from secure Multi-Party Computation (MPC) protocols. This paradigm has since then revolutionized and modularized the design of efficient ZKP systems, with far-reaching applications beyond ZKPs. However, to the best of our knowledge, all previous instantiations relied on {\em fully-secure} 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 MPC-in-the-Head paradigm to {\em game-based} cryptographic primitives supporting homomorphic computations (e.g., fully-homomorphic 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 commit-and-prove protocols, and use it to devise tight black-box compilers from Interactive (Oracle) Proofs to ZKPs, assuming One-Way Functions (OWFs). We use our paradigm to obtain several new ZKP constructions: 1. The first constant-round ZKPs for $\NP$ relations computable in (non-uniform) $\NC^1$, with communication approaching witness length (specifically, $n\cdot\poly\left(\secp\right)$, where $n$ is the witness length, and $\secp$ is a security parameter) assuming DCR. 2. Constant-round ZKPs for \NP\ relations computable in bounded polynomial space, with $O\left(n\right)+o\left(m\right)\cdot\poly\left(\secp\right)$ communication assuming OWFs, where $m$ is the instance length. This gives a black-box alternative to a recent non-black-box construction of Nassar and Ron (CRYPTO`22). 3. ZKPs for \NP\ relations computable by a logspace-uniform family of depth-$d\left(m\right)$ circuits, with $n\cdot\poly\left(\secp,d\left(m\right)\right)$ communication assuming OWFs. This gives a black-box alternative to a result of Goldwasser, Kalai and Rothblum (JACM). |
BibTeX
@inproceedings{tcc-2023-33658,
title={Beyond MPC-in-the-Head: Black-Box Constructions of Short Zero-Knowledge Proofs},
publisher={Springer-Verlag},
author={Carmit Hazay and Muthuramakrishnan Venkitasubramaniam and Mor Weiss},
year=2023
}