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: ia.cr/2016/074 Discussion forum: Show discussion | Start new discussion