Security with Low Communication Overhead

We consider the communication complexity of secure multiparty computations by networks of processors each with unlimited computing power. Say that an n-party protocol for a function of m bits is efficient if it uses a constant number of rounds of communication and a total number of message bits that is polynomial in max(m, n). We show that any function has an efficient protocol that achieves (n log n)/m resilience, Ours is the first secure multiparty protocol in which the communication complexity is independent of the computational complexity of the function being computed.We also consider the communication complexity of zero-knowledge proofs of properties of committed bits. We show that every function f of m bits has an efficient notarized envelope scheme; that is, there is a protocol in which a computationally unlimited prover commits a sequence of bits x to a computationally unlimited verifier and then proves in perfect zero-knowledge (without decommitting x) that f(x) = 1, using a constant number of rounds and poly(m) message bits. Ours is the first notarized envelope scheme in which the communication complexity is independent of the computational complexity of f.Finally, we establish a new upper bound on the number of oracles needed in instance-hiding schemes for arbitrary functions. These schemes allow a computationally limited querier to capitalize on the superior power of one or more computationally unlimited oracles in order to obtain f(x) without revealing its private input x to any one of the oracles. We show that every function of m bits has an (m/log m)-oracle instance-hiding scheme.The central technique used in all of these results is locally random reducibility, which was used for the first time in [7] and is formally defined for the first time here. In addition to the applications that we present, locally random reducibility has been applied to interactive proof systems, program checking, and program testing.