Fair Computation of General Functions in Presence of Immoral Majority

Shafi Goldwasser^{∗} MIT

Leonid Levin^{†} Boston University^{‡}, MIT

Abstract

This paper describes a method for n players, a majority of which may be faulty, to compute correctly, privately, and fairly any computable function f(x_{1}, …, x_{n}) where x_{i} is the input of the i-th player. The method uses as a building block an oblivious transfer primitive.

Previous methods achieved these properties, only for boolean functions, which, in particular, precluded composition of such protocols.

We also propose a simpler definition of security for multi-player protocols which still implies previous definitions of privacy and correctness.

1 Introduction

The problem of performing a distributed computation in a fault-tolerant and private manner has been addressed by many researchers in the past few years.

In a sequence of papers [Goldreich Micali Wigderson 87, Ben-Or Goldwasser Wigderson 88, Chaum Crepeau Damgaard 88, Ben-Or Rabin 89] it has been shown that when both private channels between pairs of players and broadcast channels are available, any distributed computation (e.g. function or game) can be performed privately and correctly, in spite of worst case behavior of the faulty players, if they are in minority.

When in majority, faulty players can be shown to be able to prevent the completion of certain computations by quitting early. Moreover, they may quit while being “ahead”, i.e. having learned more about the output than non-faulty players.

A special computation problem where quitting early is especially harmful was addressed by [Luby Micali Rackoff 83]: the simultaneous exchange between two players of random secret bits. Each player must be protected against the case the other player quits early. The fairness notion they proposed (and achieved under the assumption the quadratic residue problem is hard) is that the probability that player A knows the secret bit of player B is within an ϵ of the probability that B knows the secret bit of A (the protocol is polynomial time in ϵ^{−1} ).

[Yao 86] proposed (and showed how to achieve under the assumption that integer factorization problem is hard) the following notion of fairness for arbitrary two party boolean protocols. Suppose two players A and B want to compute a boolean function f privately and correctly. Informally, a protocol is fair if given any strategy of a faulty A, the non-faulty B has a strategy such that the probability that B will learn f, given that A will learn f is at any time during the protocol is as high as it is in the beginning of the protocol. The solution is based on the existence of trapdoor functions. These results were extended in ([Galil Haber Yung 89, Brickell Chaum Damgaard VanDeGraaf 87]) to the multi-player case.

∗Supported by ARO grant DAAL 03-86-K-0171 and NSF PYI grant 8657527-CCR with IBM matching funds

†Supported by an NSF grant , and the MIT laboratory of computer science.

‡Computer Science dept., 111 Cummington St., Boston, MA 02215; e-mail: Lnd@cs.bu.edu

The drawback of the above fairness definition is its severe limitation on the power of the faulty players. Since the strategy of the non-faulty players depends on the strategy of the faulty players, the faulty players program strategy must be chosen first and can not change depending on the program of the non-faulty players.

[Beaver Goldwasser 89] proposes a different notion of fairness, free from this limitation. A protocol to compute function f is said to be fair: if there exists a strategy for player B such that for any strategy of faulty subset of players A the ratio of the odds of B and A to compute the outcome of f is (about) the same at any time during the protocol as it is in the beginning of the protocol. It is shown how to achieve such fairness for multi-player protocols for boolean functions (as well as different boolean functions for different participants). The solution in[1] is based on trapdoor functions, and in [2] on the existence of an oblivious transfer primitive.

New Results. In this paper we show how to define and achieve fairness of any (not only boolean) function from strings to strings. This allows iteration and composition of protocols preserving fairness. In fact, we can achieve fairness for any interactive probabilistic computation, (i.e. games – to be defined in the journal version of this paper). The solution is based on the existence of an oblivious transfer primitive between every pair of players and a broadcast channel. The failure probability of the the protocol we propose is exponential while previously known was a polynomial.

We also propose a simpler definition of security for multi-player protocols which still implies previous definitions of privacy and correctness. [Kilian Micali Rogaway 90] have proposed independently another set of definitions of security. The relationship between the set of definitions has not been fully analyzed yet.

2 Conventions

Definition 1 • A interactive Turing machine is one equipped with a work-tape, input tape, random tape, output tape and several read-only and write-only communication tapes. The random tape contains an infinite sequence of random bits. Flipping a coin means reading the next new bit from the random tape.

• A multi-player protocol P⃗ = (P_{1}, P_{2}, …, P_{n}) is a tuple of n interactive Turing machines where P_{i} starts up with x_{i} on its input tape and ends up with some output y_{i} on its output tape. We call x⃗ = (x_{1}, …, x_{n}) the input vector to P⃗.

Inputs. We assume that the number n of players and identity i of each player P_{i} are included in its input. Initially coin-flips and inputs are independent. They may become correlated if their joint distribution became conditional on the information (say their sum) released by the player. Such coin-flips we call relevant. Players may want to keep them secret, to protect the privacy of their inputs. Other irrelevant coins flips may be released after the end of the protocol. The third type are unused coin-flips. They are kept, so that modifications of the protocol may use them and run with no extra random sources. The protocol must separate the three types before any communication starts and the unused flips must have at least constant density on the tape. We will treat the relevant coin-flips as part of the complete input, unless we talk of the proper input.

Outputs. Also, each player’s output in non-faulty protocols consists of its input, relevant coin-flips, and only one more string P (x⃗), common to all players. This assumption does not limit generality, since we can always add one last step to any protocol P⃗ in which every player i uses a secret random string p_{i} and tells all other players the value of exclusive or: y_{i} ⊕ p_{i}. Then, the common output is the concatenation of all y_{i} ⊕ p_{i}. The new protocol is, clearly, equivalent to the old one and retains all its properties, like correctness, privacy, etc.

Notation 1 Let x⃗ = (x_{1}, …, x_{n}) be the input vector to protocol P⃗ = (P_{1}, …, P_{n}). Then, P⃗ (x⃗) will denote the random variable which maps the (uniformly distributed) contents of random tapes α_{i} of the P_{i}’s into the output vector y⃗ = (y_{1}, …, y_{n}) where y_{i} is the output of machine P_{i}.

Let F ⊆ {1, …, n} be the set of (colluding) faulty players. An upper bound t ≥ |F | on their number is included in the inputs of all players. The inputs and outputs of faulty and non-faulty players we denote x⃗_{F} , x⃗_{!F} , P⃗_{F} (x⃗), P⃗_{!F} (x⃗), respectively.

Let us choose an arbitrary monotone unbounded security threshold S(k) < k and call functions k^{−S(k)/O(1)} negligible. If a family Y of random variables runs in expected polynomial time E_{α}T_{Y_{k}(α)} = k^{O(1)}, we call it samplable.

Definition 2 A test is a probabilistic algorithm t(ω, y) which maps the tested string y into the result {±1, 0}, using its internal coin-flips ω. Tests must run in expected polynomial time E_{ω}T_{t(ω,y)} = |y|^{O(1)}. A test t accepts a family Y_{k}(α) ∈ {0, 1}^{k} if its expected value t_{Y} (k) = E_{ω,α}t(ω, Y_{k}(α)) is negligible. We call indistinguishable:

• two families of random variables, if every test accepts both or none of them.^{1}

• protocols P⃗ , P⃗′, if P⃗ (x⃗), P⃗′(x⃗) are indistinguishable when x⃗ is generated by any samplable family of random variables.

2.1 Faulty Versions of Protocols

Versions of a protocol capture deviations from it by the faulty players.

Definition 3 A version of protocol P is any protocol P′, with P_{!F} = P′_{!F}.

Note, that no restriction is put on P′_{F}. They may deviate from the P_{F} at any time and freely exchange messages among members of F. This raises two questions.

Question 1: How does a player become faulty and enter F?

Answer: We assume an adversary who points to a player and makes it faulty.

Question 2: How does such an adversary decide who to point to?

Answer: We consider two models for such adversary.

In the first model, the adversary, called the static adversary, chooses the set of faulty player before the beginning of the computation.

In the second model the adversary is called the dynamic adversary. In this model the adversary observes the broadcast messages and private inputs/communication of any (none at the start) players which already became faulty. Based on this information, the adversary may, at any time and repeatedly, choose new players to become faulty. Once a player is faulty it remains faulty and their number is limited by t.

2.2 Legal and Moral Faults

Some faults affect the input-output behavior of a protocol but, for trivial reasons, can never be prevented by the non-faulty players.

For example, players in F may choose to misrepresent their inputs x_{F} as x′_{F} and run P_{F} accordingly; also they may choose to replace their output y_{F} with entirely different strings y′_{F}. We refer to such faulty behavior as immoral but legal.

1For non-samplable Y, Y′ one should require negligibility of t_{Y} − t_{Y′}.

Definition 4 A legal version of a multi-player protocol P⃗ = (P_{1}, …, P_{n}) is a protocol P⃗′ = (P′_{1}, …, P′_{n}) where P′_{i} is identical to P_{i} except for

• Before any communication with non-faulty machines, the faulty players may pull together their inputs and random tapes and transform them arbitrarily.

• Upon termination of P⃗, all i ∈ F may pull together their inputs, outputs, and random tapes. Then the outputs of faulty players may be replaced by a function of this pool.

Note: The dynamic adversary in the legal version is active only during the input and output stages. In these stages he corrupts players choosing them on the basis of inputs (and at the end of outputs as well) of those players he previously corrupted.

When in majority, faulty players have other non-preventable ways to affect the protocol’s inputoutput behavior. Namely, if players quit early, they can prevent the good players from completing the computation.

Definition 5 A legal-minority version of a multi-player protocol P⃗ is a legal version P⃗′ of a protocol identical to P⃗ except that the players whose coin flips have 0^{k} prefix may broadcast an abort message before or during the protocol. Any such message preceding the protocol aborts it and players output error. During the protocol such messages from n−t players also cause an abort and non-faulty players append their output with the identity of the aborting players.

2.3 Robust and Fair Protocols

Definition 6 A protocol P⃗ = (P_{1}, …, P_{n}) is robust (respectively semi-robust), if for every version P⃗′ of P⃗, there exists a legal (respectively legal-minority) version P⃗′′, of P⃗, indistinguishable from P⃗′.

While robustness is a “complete” quality, semi-robustness requires additional feature: quitfairness. It insures that interrupting the protocol does not give an unfair advantage in knowledge to the perpetrating majority.

In addition to players 1, …, n, we will speak of player 0 to mean the coalition of faulty players whose joint input is x_{0} = x_{F}. (from here on i ranges from 0 to n).

For generality, we assume that not all output information has equal value. Some may be useless, as the players may somehow get it for free upon termination of the protocol P⃗. Suppose this free information for player i is V_{i}(x⃗). The function V⃗ may not even been known to i during the protocol, but could be known to the faulty players. (The reader may ignore this extra generality, assuming V⃗ = 0.)

Let μ̄_{y}(i) be the probability (over x⃗, α⃗) of output y = P (x⃗) given V_{i}(x⃗) and x_{i}, and δ(i, x⃗, α⃗) =

\frac{1}{μ̄_{P (x⃗)}} E_{y≠P (x⃗)}(μ̄_{y}) = \frac{1}{μ̄_{P (x⃗)}} ∑_{y≠P (x⃗)} \frac{μ̄_{y}^{2}}{1−μ̄_{P (x⃗)}} be the ratio of the average (over y) probability of a wrong answer to the probability of a correct answer (from the point of view of player i).

Let h_{x⃗,i,t,α⃗} be the history seen by player i up to step t on input x⃗, and coin tosses α⃗.

Let μ_{t}(i, x⃗, α⃗) denote the probability of the correct output P (x⃗) (taken over x⃗, α⃗) given V_{i}(x⃗) and h_{x⃗,i,t,α⃗} (from the point of view of player i).

Let r_{t}(i, x⃗, α⃗) = \frac{(1−μ)}{μ} be the ratio of the odds of wrong and correct values for P (x⃗) (from the point of view of player i)

Let R_{t}(i, x⃗) be the expectation (over α⃗) of r_{t} and D_{t}(i, x⃗) be its standard deviation.

Definition 7 A protocol is quit-fair if

• for all i, t, x⃗, α⃗ either log \frac{r_{t+1}(i,x⃗,α⃗)}{r_{t}(i,x⃗,α⃗)} < \frac{1}{|x⃗|}^{2} or h_{x⃗,i,t,α⃗} ∈ H_{x⃗,i,t} where H_{x⃗,i,t} is a set of histories of exponentially small probability over α.

2This can be made arbitrarily small by padding the input x⃗.

• \frac{R_{t+1}(i,x⃗)}{R_{t}(i,x⃗)} does not depend on i.

• D_{t}(i, x⃗) is O(\sqrt{δ(i, x⃗, α⃗)R_{t}(i, x⃗)}).

A protocol is robust for minority if it is semi-robust and quit-fair.

2.4 Stable Functions and Commitment Protocols

Definition 8 A function f is stable if f(x⃗′) is either nil or f(x⃗), for all x⃗ in its domain and x⃗′, s.t. x′_{!F} = x_{!F}.

Note 1 Faulty players can not affect the value of stable functions by misrepresenting their inputs.

By running a commitment protocol on inputs x⃗ we will transform any function f into a stable function f′ (on possible outcomes y⃗ of the commitment protocol), such that f′(y⃗) = f(x⃗′) for some x⃗′, x′_{!F} = x_{!F}.

3 The Merits of the Definitions

Traditionally, several properties are required of a protocol such as privacy, correctness, independent choice of the inputs by faulty players, when a minority is faulty. And, additionally, quit-fairness, when majority is faulty.

All versions of robust protocol satisfy all these properties:

Proposition 1 Any version of a robust protocol P⃗ satisfies the following properties:

• Correctness: In a legal version, by definition, the non-faulty players output P_{!F} (x⃗′), and x′_{!F} = x_{!F}. Now, since there exists a legal version which is indistinguishable from an illegal one and in that the good guys outputs are correct, we are practically guaranteed correctness for illegal version of P⃗.

• Privacy: Several definitions of privacy exist. We recall one of them and demonstrate it for a robust protocol. Let V IEW_{F} be the random variable which takes on as value the entire history of communication and coin tosses as seen by the players in F. Call a protocol private if there is a polynomial time algorithm M, s.t. (M(x_{F} , α_{F} , y_{F}), x⃗, y⃗) is indistinguishable from (V IEW_{F} , x⃗, y⃗).

Now, any version P⃗′ of protocol P⃗, can be modified by making its faulty players to output the V IEW_{F}. There exists a legal version P⃗′′ of P⃗, with an output distribution indistinguishable from P⃗′. In a legal version, the faulty players compute their output based only on their inputs/outputs for P⃗. It follows that V IEW_{F} can be generated given only the inputs x_{F} and outputs y_{F} for P⃗ of a faulty coalition.

• independent commitment to inputs: By definition, in a legal version of the protocol the faulty players decide on which value x′_{i} to use independently of the values of non-faulty players. Since for every illegal version of the protocol, there exists a legal version with the same output distribution, the values that faulty players choose in the illegal version would have been chosen by faulty players in a legal version independently of non-faulty inputs.

Proposition 2 Any version of a robust for minority protocol P⃗ satisfies privacy, correctness, independent commitment to inputs, and quit-fairness.

Proof: Privacy and independent commitment to values are shown as above. The definition of correctness for a faulty majority is an extension of correctness in the faulty minority case. Namely, we allow non-faulty players to output the special “error” output when faulty players quit in the middle of the protocol. For this extended definition, the same argument used for correctness in above theorem will work. Fairness is guaranteed as part of the definition of robust for minority protocols.

Now previous theorems in the literature can be cast in this terminology:

Theorem 1 ([Ben-Or Goldwasser Wigderson 88, Ben-Or Rabin 89]) If |F | < n/2, any protocol can be modified into a robust one with same outputs.

Especially interesting is the case of P⃗ computing stable functions, since in all versions of robust protocols for a stable function, non-faulty outputs are the same.

4 Main Result: Robust for Minority Protocols

Theorem 2 (Main) If an oblivious transfer primitive exists and a broadcast channel exists, any protocol can be modified into one robust for minority, with same outputs.

Note 2 No restriction is made on the number of faults in the theorem. The oblivious transfer condition has previously been shown necessary for a general protocol transformation preserving privacy for a majority of faults.

In addition to players 1, …, n, we will speak of player 0 to mean the coalition of faulty players whose joint input is x_{0} = x_{F}. (from here on i ranges from 0 to n).

The x_{i}’s for player i are chosen at random with some (not necessarily easy computable) distribution. Recall that we assume the original protocol to compute one common output P (x⃗) (in addition to x_{i} and relevant coin flips). This is so since at the end of the original protocol each player can choose a random string p_{i}, and send all other players y_{i} ⊕ p_{i}. The common output will the concatenation of all p_{i} ⊕ y_{i}. Clearly, the same privacy properties hold. Thus, from here on we speak of a protocol to compute a single output.

The protocol consists of four stages: preprocessing, commitment, computation, and revelation. Preprocessing

If the number of potential faults is in minority the preprocessing stage is skipped. If the number of potential faults is in majority, then first the entire network engages in a preprocessing phase, independent of the inputs. The outcome of the preprocessing phase is either error or the protocol proceeds to stages of commitment, computation and revelation. An error implies that the protocol is aborted. A majority of faulty players can always force an early abort, but their decision to cause an early abort is independent of the non-faulty players inputs. Commitment

The commitment stage reduces the problem to computing a stable function P (x⃗). It also creates a sequence of (committed to but hidden) coin-flips α (each the sum mod2 of coin-flips of all users). Computation

The computation stage reveals the sum (taken over Z_{2}^{|P (x⃗)|}) of P (x⃗) with random password w (chosen based on α). Fairness is not an issue at this stage, because any player can (were the protocol interrupted) make this sum totally random by erasing her coin-flips. Revelation

At the revelation stage w is revealed. Privacy is not an issue at this stage, since w has no information about the inputs (beyond what the function value reveals).

Let ε = 1/|x⃗|. The revelation protocol consists of T < 2|w| macrosteps in which the protocol reveals next unused portion of α and interprets it as a vector v_{T} ∈ Z_{2}^{|w|}. It then reveals a sequence of ε^{−3} independent bits (one per micro step) b_{t}(α) chosen such that b_{t} = (v_{T} · w) (the inner product of v_{T} and w) with probability 1/2 + ε. At the end of the macro-step the actual value of (v_{T} · w) is revealed.^{3}

Clearly the logarithm of r_{t}(i, x⃗, α⃗) (see Definition 7) cannot change by more than O(ε) per microstep. After going through ϵ^{−3} micro steps with an exponentially small probability the majority of the coin flips differs from v_{T} · w. Thus, at the last step of the macro step when v_{T} · w is revealed, r_{t+1} − r_{t} is changed negligibly unless this exponentially rare failure of majority has happened. This takes care of the first requirement of quit-fairness.

Assume for generality sake that at termination of the protocol player i may even be given an extra information V_{i}(x⃗). (The function V⃗ to be later handed out may not necessarily be known to the non-faulty players during the protocol but could be known to the faulty players).

One can easily show that R_{t} decreases with almost the same speed for all x⃗, i, V⃗. Indeed, let the computation stage output y = P (x⃗) ⊕ w. At the outset of a macro-step T, let S_{T} (y, α) be the set of w′ with (v_{T′} · w′) = (v_{T′} · w) for all T′ < T. Let p(Y) be the probability at the outset (over x⃗ with given x_{i} and V_{i}(x⃗)) of y ⊕ P (x⃗) ∈ Y. Then at the end of macrostep T, r_{t} = \frac{1−μ_{t}}{μ_{t}} = \frac{(p(S_{T})−p(w))}{p(w)}.

Each w′ has a 2^{−T} chance to satisfy all T of the above randomly chosen v_{T} · w boolean linear equations and so fall in S_{T}. Moreover, each u falls in or out of S_{T} pairwise independently of any u′ ∉ {u, u⊕w}. Thus, the expectation at the end of a macro step of p(S_{T}) − p(w) (over α) is (1−p(w))/2^{T}, and therefore the expected value of \frac{1−μ_{t}}{μ_{t}} is \frac{(1−p(w))}{p(w)·2^{T}}. No change in the expected value occurs at a micro step. Thus R_{t} is independent of i and the second requirement of quit-fairness is satisfied.

The standard deviation of p(S_{T}) − p(w) is smaller than the square root of the mean of p({a}) by a factor of 2^{−T/2}/O(1), and therefore D_{T} ≤ O(\sqrt{δR_{T}}). (Recall that δ (in the definition of quit-fairness) is the ratio of the average probability of wrong answer to correct answer.)^{4}

5 How to Use the Oblivious Transfer Primitive

5.1 The Oblivious Transfer Assumption

We assume that every two players can perform an oblivious transfer.

An oblivious transfer [Rabin, Blum, Fischer Micali Rackoff, Even Goldreich Lempel 82] between two players A and B denoted by \frac{1}{2} − OT^{AB}(b_{0}, b_{1}, c) is a process by which player A who has bits b_{0},b_{1} transfers bit b_{c} to player B, where c is chosen by B. The transfer is done obliviously: player A can not distinguish between the case player B received b_{0} and the case B received b_{1}; player B can not distinguish between bc̄ = 0 and bc̄ = 1.^{5} An oblivious transfer of one bit, means that the other bit is 0 and the (random) order of bits is revealed after the transfer is performed.

An oblivious transfer can be implemented if trapdoor functions exist and A and B are computationally bounded [Even Goldreich Lempel 82]; or can be derived from the existence of noisy channel and other physical means even in the presence of infinitely powerful A and B [Crepeau Kilian 88].

3The purpose of not revealing (v_{T} · w) immediately is to assure that by quitting early the faulty players can only receive one coin flip more than non-faulty ones toward the value of (v_{T} · w). After 2|w| macrosteps, w itself can be revealed.

Sometimes the faulty coalition can be restricted to a polynomial number of possible combinations (known to all parties). Also the parties may be confident at the start that their inputs are random and completely secret. Then a more sophisticated procedure could be used to discriminate against possible coalitions, which “know too much”. We ignore this issue for now.

4The fairness requirement does not prevent erratic behavior at the end of the protocol, thus in special cases when it is detectable that the players doubts are concentrated on a logarithmic number of outputs we can do better by tossing a cube of all possible answers slightly biases toward the correct one.

5This form of oblivious transfer was shown equivalent to the original one proposed by Rabin.

We show how to use an \frac{1}{2} − OT^{AB}(b_{0}, b_{1}, c) protocol between every pair of players A and B to implement the preprocessing, commitment, and computation stages specified in section 4. Thus, we start with a legal protocol and transform it to one which is robust.

Many of the ideas in the transformation which lead to semi-robustness property (not quit-fairness) are similar to ones used in previous results of [Goldreich Micali Wigderson 87, Galil Haber Yung 87, Ben Or Goldwasser Wigderson 88, Kilian 88, Beaver Goldwasser 89].

In [Beaver Goldwasser 89a] a version of a protocol achieving semi-robustness for boolean functions based on the existence of trapdoor functions, is described. Here, we describe a protocol based on the existence of oblivious transfer, in which the error probability is improved from the previously known 1/polynomial [Beaver Goldwasser 89b] to 1/exponential.

We let t be the number of potential adversaries, k denote the security parameter.

5.2 Preprocessing Stage

5.2.1 Global Commitment and Decommitment

Each player globally commits to a library of 0’s and 1’s. A global commit has properties similar to a commit between two players. In fact, many of the the ideas are similar to the two party bit-commitment of [Kilian 88 ].

In particular, preprocess-global-commit(A,v,J) is a protocol for player A to globally commit to a bit v such that if the preprocessing stage is completed successfully, then there exists a unique value v̂ associated with J such that

• v̂ = v if A is non-faulty.

• At any time player A can decommit v̂ (or v̂_{1} ⊕ v̂_{2} where v̂_{1}, v̂_{2} are two previously committed bits) to a subset S of players such that either all non-faulty players in S will receive the correct value, or all non-faulty players will broadcast that A is faulty, or an exponentially rare event will happen. In the case of decommitting v̂_{1} ⊕ v̂_{2}, the privacy of v̂_{1} remains intact for the entire network.

• If non-faulty A committed a v randomly chosen in {0, 1} then the probability that the faulty players guess the value of v before it is decommitted to one of them is negligible.

This is achieved as follows. Notation: We let rep(v) be a set of k boolean vectors \{\overline{v}_{i}\}, 1 ≤ i ≤ k such that for each \overline{v}_{i} = (v_{i1}, ..., v_{ik}) the ⊕_{j}v_{ij} = v. We say that rep(v) = (v⃗_{1}, ..., v⃗_{k}) is invalid if for some s, t the ⊕_{j}v_{sj} ≠ ⊕_{j}v_{tj}. To choose a rep(v) at random means to pick the v_{ij} ∈ {0, 1} as above at random. To broadcast or obliviously transfer rep(v) means to broadcast or run oblivious transfer each of the v_{ij}’s. We let the function all({b_{i}}) = b_{1} if for all i, j, b_{i} = b_{j}, otherwise it assumes an error value.

Preprocess Global Commit(A,v,J):

Step 1. For 1 ≤ i ≤ k^{a} : A chooses v_{i}^{L}, v_{i}^{R} ∈ {0, 1} at random and sets v_{i} = v_{i}^{L} ⊕v_{i}^{R}. A chooses a rep(v_{i}^{L}) = (\overline{v}_{1}^{iL}, ..., \overline{v}_{k}^{iL}) and rep(v_{i}^{r}) = (\overline{v}_{1}^{iR}, ..., \overline{v}_{k}^{iR}) at random; For every player B, A oblivious transfers to B rep(v_{i}^{L}) and rep(v_{i}^{R}).^{6}

Step 2. The network chooses at random^{7}a set I containing half of the i’s. For all i ∉ I, A broadcasts rep(v_{i}^{L}) and rep(v_{i}^{R}). If for some i, d player B gets an invalid rep(v_{i}^{d}) or inconsistent with information B received then B broadcasts a complaint and the protocol is aborted.^{8} Otherwise, A broadcasts a set {c_{i} = v_{i}^{R} ⊕ v_{i}^{L} ⊕ v|i ∈ I}.

Step 3.^{9} Repeat for every player B k times: B broadcasts indexes i, j chosen at random in I; A broadcasts b = v_{i}^{L} ⊕ v_{j}^{L}; B chooses d ∈ {L, R} at random; A broadcasts rep(v_{i}^{d}) and rep(v_{j}^{d}); if b ≠ v_{i}^{d} ⊕ c_{i} ⊕ v_{j}^{d} ⊕ c_{j}, then B broadcasts a complaint and the protocol is aborted, otherwise I = I − {i, j}.

6each bits v_{i} is represented by a pair v_{i}^{R}, v_{i}^{L} such that v_{i} = v_{i}^{R} ⊕ v_{i}^{L}.

7It suffices that players alternate in choosing elements in I

8if the protocol is aborted during an execution of preprocess-global-commit, then all non-faulty players output error.

9In this step A proves to each player B in turn that for all remaining i, j ∈ I v_{i} ⊕ c_{i} = v_{j} ⊕ c_{j}.

Step 4. Each player stores I, {c_{i}, i ∈ I} and the information he received during the global commit of player A to v_{i}^{L}, v_{i}^{R}, i ∈ I in BIT − COMMIT (A, J)^{10} and the Jth bit is declared committed. (The value of this bit is all(v_{i}^{R} ⊕ c_{i} ⊕ v_{i}^{l}), i ∈ I)).

At the outset of the preprocessing stage, every player runs the protocol preprocess-global-commit for a sufficient number of values v = 0 and v = 1 as will be necessary for A to commit bits during the life time of the protocol.

During the protocol player A globally commits to bit v by broadcasting index J, such that the bit committed during the preprocessing global commit stored in BIT −COMMIT (A, J) is m. Once an index J is broadcast it is never reused.

To decommit to a subset S of the players, a committed bit stored in BIT − COMMIT (A, J), A runs the following protocol.

Global Decommit(A,S,J):

Let v be the bit committed in BIT − COMMIT (A, J) and S the subset to which it should be decommitted.

Step 1: A sends in private to each player in S, for all i ∈ I, rep(v_{i}^{R}) and rep(v_{i}^{L}). Players in S set v = c_{i} ⊕ v_{i}^{R} ⊕ v_{i}^{L} for the smallest i ∈ I.

Step 2: If any player B ∈ S gets for some i, d an invalid rep(v_{i}^{d}) or inconsistent with information B received during the oblivious transfer stage, then B broadcasts a request that player A should broadcast rep(v_{i}^{R}), rep(v_{i}^{L}) for all i ∈ I.

Step 3: If any player C detects that the information A broadcasts in step 2 is ”inconsistent” or invalid, then C broadcasts that A is faulty, otherwise the value of v is taken to be the bit c_{i} ⊕v_{i}^{L} ⊕v_{i}^{R} where v_{i}^{L}, v_{i}^{R} are defined by the information which A has broadcast at step 2.^{11}

5.2.2 Decommitting Sums of Globally Committed Bits

During the protocol player A will need to prove that various bits globally committed are the same. Let v and u be two previously globally committed bits stored in BIT − COMMIT (A, v, J_{v}) and BIT − COMMIT (A, u, J_{u}). Recall: Bit v has associated with it I_{v}, {c_{vi}|i ∈ I_{v}}, rep(v_{i}^{L}), rep(v_{i}^{R}) for all i ∈ I_{v}, and bit u has associated with it I_{u}, {c_{ui}|i ∈ I_{u}}, rep(u_{i}^{L}), rep(u_{i}^{R}) for all i ∈ I_{u}.

Protocol Prove-Equality(A,u, v)

Repeat for every player B k times: B broadcasts indexes i ∈ I_{v} and j ∈ I_{u} chosen at random; A broadcasts b = v_{i}^{L} ⊕ u_{j}^{L}; B chooses d ∈ {L, R} at random; A broadcasts rep(v_{i}^{d}) and rep(u_{i}^{d}) (if any C finds these invalid, then C broadcasts that A is faulty); if b ≠ v_{i}^{d} ⊕c_{vi} ⊕u_{j}^{d} ⊕c_{uj}, then every player broadcasts that A is faulty, otherwise every player updates I_{v} to be I_{v} − {i} and I_{u} to be I_{u} − {j}.

In fact, general properties of data globally committed can be proven in zero-knowledge using the protocols of [Kilian 89, Ben-Or et al [4]]. We chose the parameter a in the preprocess-global-commit protocol so to allow repeated zero-knowledge proofs about globally committed bits.

10Clearly each player may have received different bits during the oblivious transfer and thus has different information.

11By the properties of our global commit protocol all non-faulty players will either declare A faulty or agree that a bit of the same value has been decommitted.

5.2.3 Private Communication Lines

During the protocol players A and B will need to privately communicate and yet be able to prove to other players that the messages they send privately were computed correctly with respect to their committed inputs and previously received messages.

If encryption functions were available this would present no problem, however we only have the ability to perform oblivious transfers between every two players.

Thus, in the preprocessing stage every pair of players prepare and globally commit to a supply of 0’s and 1’s known to A and B alone which both can globally decommit. These bits will be used later for private communication.

This is done by running the following protocol.

Protocol Preprocess-Private-Communication(A,B,J)

A randomly chooses b ∈ {0, 1} and runs an identical protocol to P reprocess−Global−Commit(A, b, J) with the exception that the information stored normally in BIT − COMMIT (A, J) is stored in P RIV AT E − COMMIT (A, B, J). Next A decommits b to player B by running Global − Decommit(A, {B}, J); (Note now that both A and B can decommit the bit store in P RIV AT E − COMM(A, B, J).)

During the protocol A sends private message m = m_{1}, ..., m_{k} to player B by broadcasting indexes J_{i} such that for every i = 1, ..., k the value of the bit committed in P RIV AT E − COMM(A, B, J_{i}) is m_{i}. (Once an index J is broadcast it is never reused.)

5.2.4 Global Oblivious Transfers

During the protocol every pair of players (A,B) will need to engage in an oblivious transfer in such a way that A and B can prove to to the rest of the network that indeed they have fed the correct inputs to the oblivious transfer process, and have received claimed outputs.

This is achieved by having every pair of players (A, B) prepare a supply of oblivious transfers in which the inputs and the outputs have been globally committed.

Let i ∈ {0, 1}^{3}. Say that an oblivious transfer is of type i = i_{0}i_{1}i_{2} if b_{0} = i_{0}, b_{1} = i_{1} and c = i_{2}. To prepare at least L oblivious transfers of each type i ∈ {0, 1}^{3}, every pair of players (A, B) execute the following protocol O(L + k) times.

Protocol Preprocess-Oblivious-Transfer(A,B, J)

Step 1. For j = 1, ..., k^{a}: Player B globally commits to c^{j} randomly chosen in {0, 1}; Player A globally commits to b_{0}^{j}, b_{1}^{j}, r^{j} randomly chosen in {0, 1}. Players A and B run an OT^{AB}(b_{0}^{j} ⊕ r^{j}, b_{1}^{j} ⊕ r^{j}, c^{j}); Player B globally commits to r̂^{j} which he received as a result of the oblivious transfer. (Clearly, if A and B are non-faulty, r̂^{j} should equal b_{c^{j}}^{j} ⊕ r^{j}).

Step 2. The network chooses at random ^{12} a set I of half of the j’s. For all j ∉ I, A globally decommits b_{0}^{j}, b_{1}^{j}, r^{j} to the entire network; B globally decommits c^{j} and r̂^{j} to the network. If any player complains during these global commits or r^{j} ⊕ b_{c^{j}}^{j} ≠ r̂^{j}, the protocol is aborted. Otherwise, player B globally commits to randomly chosen c ∈ {0, 1}, broadcasts set I_{1} ⊂ I such that I_{1} = {j|c^{j} = c}, and proves that c^{j} = c iff j ∈ I_{1} (using the Prove-Equality procedure defined above.) Player A globally commits to randomly chosen b_{0}, b_{1}, r ∈ {0, 1}, broadcasts set I_{2} ⊂ I_{1} such that I_{2} = {j|b_{0}^{j} = b_{0}, b_{1}^{j} = b_{1}, r^{j} = r}, and proves that b_{0}^{j} = b_{0}, b_{1}^{j} = b_{1}, r^{j} = r iff j ∈ I_{2} (using the Prove-Equality procedure). If for some i, j ∈ I_{2} r̂^{j} ≠ r̂^{i} A broadcasts a complaint and the protocol is aborted, otherwise A globally commits to r̂ such that r̂ = r̂^{j}, for all j ∈ I_{2} and proves this fact (using the Prove-Equality procedure). Each player stores I_{2} and the information obtained during the global commits of b_{0}^{j}, b_{1}^{j}, c^{j}, r^{j}, r̂^{j}, for j ∈ I_{2} in its copy of OT − COMMIT (A, B, J).

12It suffices that players alternate in choosing elements in I

During the computation stage when A and B need to engage in an oblivious transfer with parameters B_{0}, B_{1} known to A and parameter C known to B they run the following protocol.

Protocol Global-Oblivious-Transfer(A, B, B_{0}, B_{1}, C)

B selects a J such that the set {b_{0}^{j}, b_{1}^{j}, c^{j}, r^{j}, r̂^{j}, j ∈ I_{2}} stored in OT − COMMIT (A, B, J) is such that c^{j} = C for all j ∈ I_{2} (a fact B proves to the network), and broadcasts J to the network. If B_{0} = b_{0}^{j} and B_{1} = b_{1}^{j} for all j ∈ I_{2} (a fact A proves to the network), A decommits r^{j}, j ∈ I_{2} to B, else J is cast out and the step is repeated. B sets B_{C} = all({r^{s} ⊕ r̂^{s}, s ∈ I_{2}}).

5.3 Input Commitment and Computation Stages

At this stage every player A needs to globally commit to its input x_{A} and a sequence of coin flips α_{A}.

Let x_{A}α_{A} = y_{A}^{1}...y_{A}^{m} (in binary). Player A broadcasts^{13} indexes J_{1}, ..., J_{k} such that the bit committed in GLOBAL − COMMIT (A, J_{i}) is y_{A}^{i}.

Set α = ∑_{player A} α_{A} mod 2.

5.3.1 Computation

Let C_{P} be the arithmetic circuit over field of elements F computing the legal protocol P (assuming that P has already been modified to output single output to all players). Let γ_{B} ∈ F be a unique element associated with player B.

In order to allow the network to compute with inputs x_{A} (and α_{a}), player A secret shares x_{A} (and α_{a}) as follows. A selects a random polynomial p_{x_{A}} of degree t such that p_{x_{A}}(0) = x_{A}. For every player B, A globally commits to p_{x_{A}}(γ_{B}) and privately communicates p_{x_{A}}(γ_{B}) to B.

Note now that because of the properties of PRIVATE-COMM every player B now knows p_{x_{A}}(γ_{B}), and every other player has received a global commitment to the value of p_{x_{A}}(γ_{B}) which can be decommitted either by A and or B.

A now proves in zero-knowledge to the network that the values privately sent {p_{x_{A}}(γ_{B})}_{B} interpolate to a unique t degree polynomial whose free term is x_{A}.

The arithmetic circuit C_{P} has two types of gates: addition (+), and multiplication (×) over the finite field F (scalar multiplication is a trivial extension of + gate).

The circuit is evaluated in a gate by gate fashion. The invariant during the computation stage is that each player holds a share of all inputs to the next gate to be computed, which is globally committed.

Suppose the inputs to a + gate are u and v. Every player A holds P_{u}(γ_{A}) and P_{v}(γ_{A}) (where P_{u} and P_{v} are random polynomials of degree t with free term u and v respectively). To compute a share of the output u + v, player A computes P_{u+v}(γ_{A}) = P_{u}(γ_{A}) + P_{v}(γ_{A}). A globally commits to P_{u+v}(γ_{A}).

Suppose the inputs to a × gate are u and v. Computing P_{u×v}(γ_{A}) (where P_{u×v} is a random polynomial of degree t whose free term is u × v.) can be reduced to the problem of every pair of players (A,B) computing semi-robustly a two-player function on the shares they hold P_{u}(γ_{A}) and P_{v}(γ_{B}), (see [Galil Haber Yung 87, Van Dem Graaph etal. 87, Beaver Goldwasser 88]). To compute a two-player function semi-robustly has been reduced to two-player oblivious transfer in [Kilian 88]. Instead of the two-player oblivious transfer called for in [Kilian 88]’s construction, the Commit − Oblivious − T ransfer(A, B, ...) protocol which was set up in the preprocessing stage is used.

Every message of the player sent while computing the × gate must be accompanied by a zeroknowledge proof that it has been computed and sent correctly with respect to the inputs globally committed and the messages previously received from other players both in private and by broadcast. This is possible as all private messages sent during the commitment and computation stage have been globally committed (as all these messages were sent using the private communication lines set up in preprocess-private-communication.)

13once an index is broadcast it will never be reused.

5.4 Acknowledgements

We are grateful to Mihir Bellare, Joe Kilian, and Silvio Micali for very useful discussion.

References

[1] D. Beaver, S. Goldwasser. Multi Party Fault Tolerant Computation with Faulty Majority, proceedings of Crypto89, Santa Barbara, CA, August 1989.

[2] D. Beaver, S. Goldwasser. Multi Party Fault Tolerant Computation with Faulty Majority Based on Oblivious Transfer, proceedings of FOCS89, Duke, NC, October 1989, pp. 468-473.

[3] M. Ben-Or, S. Goldwasser, A. Wigderson. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation. Proc. of 20^{th} STOC 1988, pp. 1-10.

[4] Ben-Or, Michael, Oded Goldreich, Shafi Goldwasser, Johan Hastad, Joe Kilian, Silvio Micali, Philip Rogaway, “IP is in Zero-Knowledge,” Proceedings, Advances in Cryptology, Crypto 1988.

[5] Rabin, T. and M. Ben-Or. “Verifiable Secret Sharing and Multiparty Protocols with Honest Majority.” Proc. of 21^{st} STOC, ACM, 1989.

[6] Blakely,T.. Security Proofs for Information Protection Systems. Proceedings of the 1980 Symposium on Security and Privacy, IEEE Computer Society Press, NY, pp. 79-88, 1981.

[7] Brassard, Gilles, Claude Crépeau, and David Chaum, “Minimum Disclosure Proofs of Knowledge,” manuscript.

[8] Brassard, Gilles, Claude Crépeau, and Jean-Marc Robert. “Information Theoritic Reductions Among Disclosure Problems,” Proceedings of the 27^{th} FOCS, IEEE, 1986, 168–173.

[9] E. Brickell, D. Chaum, I. Damgaard, J. van de Graaf. Gradual and Verifiable Release of A Secret. CRYPTO 1987.

[10] D. Chaum, C. Crepeau, I. Damgaard. Multiparty Unconditionally Secure Protocols. Proc. of 20^{th} STOC 1988, pp. 11-19.

[11] Chaum, David, Ivan Damgard, and Jeroen van de Graaf. “Multiparty Computations Ensuring Secrecy of Each Party’s Input and Correctness of the Output,” Proceedings of CRYPTO ’85, Springer-Verlag, 1986, 477–488.

[12] R. Cleve. Limits on the Security of Coin Flips When Half the Processors are Faulty. STOC 1986.

[13] Cohen, Fischer. A Robust and Verifiable Cryptographically Secure Election. FOCS 1985.

[14] C. Crepeau and J. Kilian. Achieving Oblivious Transfer Using Weakened Security Assumptions. FOCS 1988.

[15] Crépeau Claude, “On the Equivalence of Two Types of Oblivious Transfer”, Crypto87.

[16] B.Chor, S. Goldwasser, S. Micali, B. Awerbuch. Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults. FOCS 1985.

[17] B. Chor, M. Rabin. Achieving Independence in Logarithmic Number of Rounds. PODC 1986.

[18] Even S., Goldreich O., and A. Lempel, A Randomized Protocol for Signing Contracts, CACM, vol. 28, no. 6, 1985, pp. 637-647.

[19] Fischer M., Micali S., and Rackoff C. Oblivious Transfer Based in Quadratic Residuosity, Unpublished.

[20] Z.Galil, S.Haber, M.Yung. Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public Key Model. Proc. CRYPTO 1987.

[21] O. Goldreich, S. Micali, A. Wigderson. How to Play Any Mental Game, or A Completeness Theorem for Protocols with Honest Majority. Proc. of 19^{th} STOC 1987, pp. 218-229.

[22] Goldreich, O., Vainish, R. “How to Solve any Protocol Problem: An Efficiency Improvement”, Crypto 87.

[23] Goldwasser, Micali, Rackoff. The Knowledge Complexity of Interactive Proof Systems. SIAM J. of Comp 1989.

[24] S.Haber. Multi-Party Cryptographic Computation: Techniques and Applications. Ph.D. Thesis, Columbia University, 1988.

[25] Impagliazzo, Russell and Moti Yung, “Direct Minimum Knowledge Computations,” Proceedings, Advances in Cryptology, Crypto 1987.

[26] Kilian, Joe, “On The Power of Oblivious Transfer,” Proceedings of the 20^{th} STOC, ACM, 1988, pp. 20-29. Also appeared in Uses of Randomness In Algorithms and Protocols, An ACM Distinguished Dissertation 1989.

[27] J. Kilian. S. Micali. P. Rogaway Security Definitions for Multi Party Protocols. In Preparation.

[28] Micali Luby Rackoff 83. The Miraculous Exchange of a Secret bit, Proc. of FOCS 1983.

[29] A. Shamir. How to Share a Secret. CACM 22, 612-613, 1979.

[30] Yao, Andrew C. “Protocols for Secure Computations,” Proceedings of the 23^{rd} FOCS, IEEE, 1982, 160–164.

[31] Yao, Andrew C. “How to Generate and Exchange Secrets,” Proceedings of the 27^{th} FOCS, IEEE, 1986, 162–167.