You are looking at a specific version 20160314:051731 of this paper. See the latest version.

Paper 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.

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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
adaptive zero-knowledge proofssecure two-party computationrandomized encodinginteractive hashinginstance-dependent commitmentsnon-malleable commitments
Contact author(s)
muthuv @ cs rochester edu
History
2019-01-27: last of 3 revisions
2016-01-27: received
See all versions
Short URL
https://ia.cr/2016/074
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.