Charles River Crypto Day: On the Power of Secure Two-Party Computation

Опубликовано 11 августа 2016, 7:46

Ishai, Kushilevitz, Ostrovsky and Sahai (STOC`07, 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 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`09, 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`90) to obtain black-box constructions of commit-and-prove protocols with the so called input-delayed property where the honest proverΓÇÖs algorithm does not require the actual statement until the last round. Using this, we obtain first constructions of a 4-round concurrent 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 primitive. We also show how these proofs can improve round complexity of secure computation protocols in the tamper-proof model.