Cryptology ePrint Archive: Report 2016/074

On the Power of Secure Two-Party Computation

Carmit Hazay and Muthuramakrishnan Venkitasubramaniam

Abstract: Ishai, Kushilevitz, Ostrovsky and Sahai (STOC 2007, SIAM JoC 2009) introduced the powerful ``MPC-in-the-head'' technique that provided a general transformation of information-theoretic MPC protocols secure against passive adversaries to a ZK proof in a ``black-box'' way. In this work, we extend this technique and provide a generic transformation of any semi-honest secure two-party computation (2PC) protocol (with mild adaptive security guarantees) in the so called \emph{oblivious-transfer} hybrid model to an \emph{adaptive} ZK proof for any NP-language, in a ``black-box'' way assuming only one-way functions. Our basic construction based on Goldreich-Micali-Wigderson's 2PC protocol yields an adaptive ZK proof with communication complexity proportional to quadratic in the size of the circuit implementing the NP relation. Previously such proofs relied on an expensive Karp reduction of the NP language to Graph Hamiltonicity (Lindell and Zarosim (TCC 2009, Journal of Cryptology 2011)). We also improve our basic construction to obtain the first linear-rate adaptive ZK proofs by relying on efficient maliciously secure 2PC protocols. Core to this construction is a new way of transforming 2PC protocols to efficient (adaptively secure) instance-dependent commitment schemes.

As our second contribution, we provide a general transformation to construct a randomized encoding of a function $f$ from any 2PC protocol that securely computes a related functionality (in a black-box way). We show that if the 2PC protocol has mild adaptive security guarantees then the resulting randomized encoding (RE) can be decomposed to an offline/online encoding.

As an application of our techniques, we show how to improve the construction of Lapidot and Shamir (Crypto 1990) to obtain ``input-delayed'' ZK proofs which are proofs where the honest prover's algorithm does not require the actual statement until the last round. An interesting corollary we obtain using these proofs are first constructions of a 4-round non-malleable commitments scheme based on one-way permutations where the underlying one-way permutation is used in a black-box way. Previous constructions either required more number of rounds or made non-black-box usage of the underlying primitives.

Category / Keywords: adaptive zero-knowledge proofs, secure two-party computation, randomized encoding, interactive hashing, instance-dependent commitments, non-malleable commitments

Date: received 26 Jan 2016, last revised 13 Mar 2016

Contact author: muthuv at cs rochester edu

Available format(s): PDF | BibTeX Citation

Note: Added an application of our techniques, namely, obtaining black-box 4-round commit-and-prove protocols where the prover needs the statement only in the last round. As a corollary we also obtain the first 4-round black-box construction of a concurrent non-malleable commitment scheme.

Version: 20160314:051731 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]