1. Introduction

Secure distributed computing (SDC) addresses the problem of distributed computing where some of the algorithms and data that are used in the computation must remain private. Usually, the problem is stated as follows, emphasizing privacy of data. Let f be a publicly known function taking n inputs, and suppose there are n parties (named p _i, i = 1 ... n), each holding one private input x _i. The n parties want to compute the value f( x _i, ..., x _n) without leaking any information about their private inputs (except of course the information about x _i that is implicitly present in the function result) to the other parties. An example is voting: the function f is addition, and the private inputs represent yes ( x _i = 1) or no ( x _i = 0) votes. In case you want to keep an algorithm private, instead of just data, you can make f an interpreter for some (simple) programming language, and you let one of the x _i be an encoding of a program.

In descriptions of solutions to the secure distributed computing problem, the function f is usually encoded as a boolean circuit, and therefore secure distributed computing is also often referred to as secure circuit evaluation.

It is...