Foundations of Secure Interactive Computing

The problem of secure multiparty computation is usually described as follows: each of n players in a network holds a private input x_i. Together they would like to compute a function F(x₁,...,x_n) without revealing the inputs, even though no particular player can be trusted. Attempts to contrive formal definitions for the problem have treated properties of the solution separately (correctness, privacy, etc.), giving an ad hoc collection of desirable properties and varied definitions that do not support clear or comparable proofs.We propose a clear, concise, and unified definition for security and reliability in interactive computations. We develop a reduction called relative resilience that captures all desired properties at a single blow. Relative resilience allows one to classify and compare arbitrary protocols in terms of security and reliability, in the same way that Turing reductions allow one to classify and compare algorithms in terms of complexity. Security and reliability reduce to a simple statement: a protocol for F is resilient if it is as resilient as an ideal protocol in which a trusted host is available to compute F. Relative resilience captures the notions of security and reliability for a wide variety of interactive computations, including zero-knowledge proof systems, Byzantine Agreement, oblivious transfer, two-party oblivious circuit evaluation, among others.Relative resilience provides modular proof techniques that other approaches lack: one may compare a sequence of protocols ranging from the real-world protocol to the ideal protocol, proving the relative resilience of each successive protocol with greater clarity and less complexity. Folk theorems about the “transitivity” of security and the security of concatenated protocols are now provable; and the proofs reveal that such folk theorems fail under subtle conditions that have previously gone unnoticed. The conciseness1 and modularity of our definitions and proof techniques provide great clarity in designing and reasoning about protocols and have already lead to provably secure protocols that are significantly more efficient than those appearing in the literature.