  We present efficient and practical algorithms for a large, distributed system
of processors to achieve reliable computations in a secure manner.
Specifically, we address the problem of computing a general function of several
private inputs distributed among the processors of a network, while ensuring
the correctness of the results and the privacy of the inputs, despite
accidental or malicious faults in the system. [...] Our algorithms maintain a
low cost in local processing time, are the first to achieve optimal levels of
fault-tolerance, and most importantly, have low communication complexity. In
contrast to the best known previous methods, which require large numbers of
rounds even for fairly simple computations, we devise protocols that use small
messages and a constant number of rounds regardless of the complexity of the
function to be computed. Through direct algebraic approaches, we separate the
communication complexity of secure computing from the computational complexity
of the function to be computed. We examine security under both the modern
approach of computational complexity-based cryptography and the classical
approach of unconditional, information-theoretic security. We [...] support
formal proofs of claims to security, addressing an important deficiency in the
literature. Our protocols are provably secure. In the realm of
information-theoretic security, we characterize those functions which two
parties can compute jointly with absolute privacy. We also characterize those
functions which a weak processor can compute using the aid of powerful
processors without having to reveal the instances of the problem it would like
to solve. Our methods include a promising new technique called a locally random
reduction, which has given rise not only to efficient solutions for many of the
problems considered in this work but to several powerful new results in
complexity theory.
