Paper 2019/091

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

Li Hongda, Pan Dongxue, and Ni Peifang


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Zero-knowledgeclaw-free permutationtwo-party computationparallel repetition.
Contact author(s)
lihongda @ iie ac cn
pandongxue @ iie ac cn
2019-01-30: last of 4 revisions
2019-01-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Li Hongda and Pan Dongxue and Ni Peifang},
      title = {Efficient Zero-Knowledge for NP from Secure Two-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2019/091},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.