Secure Computation

We define what it means for a network of communicating players to securely compute a function of privately held inputs. Intuitively, we wish to correctly compute its value in a manner which protects the privacy of each player’s contribution, even though a powerful adversary may endeavor to disrupt this enterprise.This highly general and desirable goal has been around a long time, inspiring a large body protocols, definitions, and ideas, starting with Yao [1982, 1986] and Goldreich, Micali and Wigderson [1987]. But all the while, it had resisted a full and satisfactory formulation.Our definition is built on several new ideas. Among them: •Closely mimicking an ideal evaluation. A secure protocol must mimic this abstraction in a run-by-run manner, our definition depending as much on individual executions as on global properties of ensembles.•Blending privacy and correctness in a novel way, using a special type of simulator designed for the purpose.•Requiring adversarial awareness—capturing the idea that the adversary should know, in a very strong sense, certain information associated to the execution of a protocol. Among the noteworthy and desirable properties of our definition is the reducibility of secure protocols, which we believe to be a cornerstone in a mature theory of secure computation.