Xiao Liang: PhD Thesis Defense: "Black-Box Secure Multi-Party Computation: New Possibilities and Limitations"

Dates: 
Tuesday, August 24, 2021 - 12:00pm to 2:00pm
Location: 
Zoom - contact events@cs.stonybrook.edu for Zoom info.
Event Description: 
Abstract: 
Secure multi-party computation (MPC) allows mutually distrustful parties to compute any functionality without compromising the privacy of their inputs. It has been an important theme in this area to obtain constructions that make only black-box use of their cryptographic building blocks. Such constructions are usually preferable since their efficiency is not affected by the implementation details of the underlying primitives.

Black-Box Composable MPC. We present new composable MPC protocols that make only black-box access to lower-level primitives. In particular: (1) We construct a constant-round black-box protocol that remains secure under bounded-concurrent composition. Prior to our work, such protocols required either non-black-box usage of cryptographic primitives or relaxed notions for security. (2) We present a \widetilde{O}(\log \lambda)-round black-box protocol achieving angel-based universal composability. Prior to our work, there only exist black-box constructions in  \widetilde{O}(\log^2 \lambda) rounds and non-black-box constructions in  \widetilde{O}(\log \lambda) rounds. Thus, we close the gap between these two types of protocols.

Black-Box Zero-Knowledge. Zero-Knowledge Proofs are of great importance both as a building block for MPC and a stand-alone primitive. General-purpose zero-knowledge proofs inherently require the code of the relation to be proven. As shown by Rosulek (Crypto'12), zero-knowledge proofs for even simple statements, such as membership in the range of a one-way function, require non-black-box access.

We propose an approach to bypass Rosulek's impossibility result. Instead of asking for a ZK proof directly for the given one-way function f, we seek to construct a new one-way function F making only black-box access to f, and an associated ZK protocol for proving non-trivial statements over its output. We say that F, along with its associated ZK protocol, is a proof-based one-way function. Similarly, we define and construct proof-based versions of pseudo-random generators and collision-resistant hash functions. We first show that even this relaxed proof-based black-box notion is impossible to achieve; we next present possibility results assuming a Goldreich-Levin-type restriction on input. Our results open up the possibility that general-purpose ZK proofs for relations that require black-box access to the primitives above may be possible in the future by instantiating them using proof-based primitives instead of ordinary ones.

Computed Event Type: 
Mis