Paper 2019/091

Efficient Zero-Knowledge for NP from Secure Two-Party Computation

Li Hongda, Pan Dongxue, and Ni Peifang

Abstract

Ishai et al. [28, 29] introduced a powerful technique that provided a general transformation from secure multiparty computation (MPC) protocols to zero-knowledge (ZK) proofs in a black-box way, called “MPC-in-the-head”. A recent work [27] extends this technique and shows two ZK proof protocols from a secure two-party computation (2PC) protocol. The works [28, 27] both show a basic three-round ZK proof protocol which can be made negligibly sound by standard sequential repetition [19]. Under general black-box zero knowledge notion, neither ZK proofs nor arguments with negligible soundness error can be achieved in less than four rounds without additional assumptions [15]. In this paper, we address this problem under the notion of augmented black-box zero knowledge [26], which is defined with a new simulation method, called augmented black-box simulation. It is presented by permitting the simulator to have access to the verifier’s current private state (i.e. “random coins” used to compute the current message) in a special manner. We first show a three-round augmented black-box ZK proof for the language graph 3-colorability, denoted G3C. And then we generalize the construction to a three-round augmented black-box ZK proof for any NP relation R(x, w) without relying on expensive Karp reductions. The two constructions are based on a family of claw-free permutations and the general construction is additionally based on a black-box use of a secure 2PC for a related two-party functionality. Besides, we show our protocols can be made negligibly sound by directly parallel repetition.