Committed Oblivious Transfer and

Private Multi-Party Computation

Claude Crépeau  Jeroen van de Graaf  Alain Tapp

Université de Montréal Département d’informatique et de Recherche Opérationnelle email:{crepeau, jeroen, tappa}@iro.umontreal.ca

Abstract. In this paper we present an efficient protocol for “Committed Oblivious Transfer” to perform oblivious transfer on committed bits: suppose Alice is committed to bits a_{0} and a_{1} and Bob is committed to b, they both want Bob to learn and commit to a_{b} without Alice learning b nor Bob learning ab̄. Our protocol, based on the properties of error correcting codes, uses Bit Commitment (bc) and one-out-of-two Oblivious Transfer (ot) as black boxes. Consequently the protocol may be implemented with or without a computational assumption, depending on the kind of bc and ot used by the participants. Assuming a Broadcast Channel is also available, we exploit this result to obtain a protocol for Private Multi-Party Computation, without making assumptions about a specific number or fraction of participants being honest. We analyze the protocol’s efficiency in terms of bcs and ots performed. Our approach connects Zero Knowledge proofs on bcs, Oblivious Circuit Evaluation and Private Multi-Party Computations in a conceptually simple and efficient way.

1 Introduction

Committed Oblivious Transfer (cot) is the natural fusion of one-out-of-two Oblivious Transfer (ot) [13] and Bit Commitment (bc). At the start of the protocol Alice is committed to bits a_{0} , a_{1} and Bob to bit b . At the end Bob is committed to a_{b} and knows nothing about ab̄. Alice learns nothing about b.

The current paper presents an efficient cot protocol. This protocol makes no assumption on the type of bcs and ots that are used. For instance, with ot and bc based on the Quantum Channel [2, 3] we can perform cot without any computational assumption. Our protocol uses some elements of coding theory and simple Zero-Knowledge sub-protocols. It uses O(n) ots and O(n^{2}) bcs, where n denotes the security parameter, but uses only O(n) bcs if they have a special xor-property. The global running time is O(n^{2}) in the first case and O(n) in the second (excluding the time necessary to build the code).

cot is a very powerful tool that can be used to perform general cryptographic tasks such as Oblivious Circuit Evaluation (oce)[19] or Mental Games [16, 17], and Distributed Computation [18]. Such tasks have been achieved before [19] regardless of cot from generic bc and ot, but unfortunately the solution was not only complicated but very inefficient. At EUROCRYPT ’89, Crépeau [8] introduced cot under the label “Verifiable Oblivious Transfer” and used it in a simpler protocol for oce based on the work of Goldreich and Vanish [17]. Unfortunately this protocol for cot used Ω(n^{3}) ots, which is still rather inefficient.

An apparently more efficient protocol for cot (using only O(n) ots) was presented in [18] under the label “Preprocess-Oblivious-Transfer”. Unfortunately, it is very easy to misbehave in that protocol in a way that allows Bob to get both bits with non-negligible probability and for Alice to learn b with a non-negligible probability. These problems can be fixed easily by straightforward techniques, but then the resulting protocol becomes more or less equivalent to that of [8] using Ω(n^{3}) ots. The best that we were able to get from protocols in the spirit of [8] and [18] is a protocol using Ω(n^{2}) ots.

In the second part of this paper we use the cot protocol to obtain an efficient protocol for Private Multi-Party Computation (pmpc). The problem of computing a function when the participants want to keep their input private has been considered by many researchers under different models and various names (for an excellent overview see [15]). Distinguishing features of the several models are: the number of participants (P = 2 vs P ≥ 3), the presence or absence of some unproven intractability assumption, the communication model (private channels between each pair of participants, broadcast channels, oblivious transfers or a combination of these) and the capacity of dealing with malicious participants.

We assume that a Broadcast Channel and an Oblivious Transfer Channel are available between each pair of participants. A protocol is a correct Multi-Party Computation if the output of the protocol to each participant is the same as that of the function it is emulating. Furthermore we say that such a protocol is fair if the the fact that one participant learns the output implies that every participant does. It is honest if an honest participant knows when he does not learn the output of the function and it is private if no coalition of less than P participants can learn information about the private inputs of other participants, other than what the output of the function logically implies.

Our result can now be stated as follows. Suppose that P participants wish to evaluate a boolean circuit F consisting of m boolean gates. Then there exists a correct, private, honest and fair protocol to evaluate F using O(P^{2}n^{2}m) bc s and O(P^{2}nm) ot s. If instead of having bc and ot as basic primitives we only have the simpler Oblivious Transfer of Rabin [26], then the number of such primitives required is O(P^{2}n^{3}m).

It is rather unfortunate that a single dishonest participant can make the pmpc protocol abort. Nevertheless, this is unavoidable, since to guarantee that no dishonest coalition can have any advantage over an honest participant, the protocol requires everybody’s cooperation. In section 5 of [18], Goldwasser and Levin describe a protocol (henceforth called GL) under the same assumptions as ours. Though we adopt many of their ideas (some of which are common knowledge), the protocol presented here is far more efficient. For instance, to implement an and gate for P participants GL uses computations on polynomials, and many conditions that have to be verified while the main protocol is in progress are verified through rather inefficient sub-protocols. In this paper we demonstrate a conceptually much simpler way to accomplish this same task using and extending techniques introduced in [21, 16].

This also allows us to give a proper analysis of the complexity (in terms of the underlying cryptographic primitives) of our protocol, which in GL is quite difficult. In other words, whereas GL shows that a protocol for pmpc exists under the current assumptions, we provide a much simpler and more efficient implementation.

The remainder of this paper starts with a section elaborating on the assumptions, and introducing some useful notations. Section 3 contains the protocol and proof for cot, whereas Section 4 extends the tolls of Section 2 and finally Section 5 outlines the protocol and proof for pmpc.

2 Preliminaries

2.1 One-out-of-two Oblivious Transfer and Bit Commitment

In this paper ot and bc are used as black boxes. Since these are well-known protocols, we only describe them briefly.

In a one-out-of-two Oblivious Transfer Bob has to choose between learning bit a_{0} or a_{1} prepared by Alice but she does not learn his choice b. Bob learns a_{b} and obtains no information about ab̄. Implementations of ot can only exist under some assumption. For instance, ot can be constructed if trapdoor functions exist [16], from a noisy channel [11, 12], or from a quantum channel [2, 10]. It is also a well-known fact that using O(n) of Rabin’s Oblivious Transfers [26] one can construct one-out-of-two Oblivious Transfer [7].

In a Bit Commitment Alice sends a committed bit a to Bob in such a way that she is able to reveal it later in a unique way (a) but Bob is not able to find its value by himself. Alice cannot change her mind and open a as ā.

Bc is impossible without making an assumption. It is easy to convert any version of Oblivious Transfer into a bc. Using error-correcting codes this is done at a cost of O(n) ots per bc [3]. Bc can also be implemented under the assumption of the existence of a one-way function (or equivalently a pseudo-random bit generator) by a result of Naor [25], from a noisy channel [12], or from a quantum channel [3].

2.2 Bit Commitments with XOR

In this subsection we show how to prove that some bcs satisfy an xor-relation without giving away their values. For this purpose we use special Bit Commitments (bcx) and proof techniques described by Kilian [21][22] (partly attributed to Rudich and Bennett). To commit to b using a bcx b , Alice uses 2n plain bcs, (b_{1L},b_{1R}, ...,b_{nL},b_{nR}) such that for each i ∈ {1...n} : b_{iL} ⊕ b_{iR} = b. To open b , Alice opens its 2n plain bcs. Bob accepts only if indeed all pairs of bcs xor to the same value b.

If Alice is committed to several bcxs b^{1} , b^{2} , ..., b^{k} she can prove to Bob that ⨁_{j=1}^{k} b^{j} = c for some public value c without disclosing the b^{j}’s as follows. First, Bob specifies to Alice k random permutations to shuffle the n pairs b_{iL}^{j}, b_{iR}^{j} of each bcx. Then, for each i ∈ {1...n} Alice announces c_{iL} = ⨁_{j=1}^{k} b_{iL}^{j} and c_{iR} = ⨁_{j=1}^{k} b_{iR}^{j}. Finally, for each i ∈ {1...n} Bob randomly asks Alice to open either all the b_{iL}^{j}’s or the b_{iR}^{j}’s, and verifies that the revealed values are consistent with c_{iL} or c_{iR}. If this is the case, Bob is convinced that the bcxs satisfy the linear relation announced by Alice, since her probability of convincing him of a bad relation without detection is exponentially small in n. Note that this technique can be used to prove that two bcxs a and b are equal (different) simply by proving a ⊕ b = 0 ( a ⊕ b = 1).

Since each such proof destroys the bcx involved, we must copy them first. Suppose Alice is committed to b and she wants two instances of this commitment, i.e. b^{1} and b^{2} such that b = b^{1} = b^{2}. Alice creates 3n pairs of bcs such that each pair xors to b. Then Bob randomly partitions these 3n pairs in three subsets of n pairs, thus obtaining b^{0} , b^{1} and b^{2} and asks Alice to prove that b^{0} = b as suggested above. This destroys b^{0} and b , but if Alice succeeds Bob is convinced that b^{1} and b^{2} are two bcxs with the same value as b .

Because of the complexity of these constructions, for the remaining of this paper we consider as a unitary bcx operation: creation of a bcx, opening of a bcx, or proof that a constant number of bcxs satisfy a given linear relation.

3 Committed Oblivious Transfer

Suppose that Alice is committed to bits a_{0} , a_{1} and Bob is committed to bit b . After running cot( a_{0} , a_{1} )( b ) Bob will be committed to a = a_{b}. Alice, whatever she does, cannot use the protocol to learn information on b and Bob, whatever he does, cannot use the protocol to learn information on ab̄.

3.1 Coding Theory

In our protocol for cot, a code is required. The code is not used to correct transmission errors (although it could if necessary) but in a more elaborate way for efficiency and security reasons.

Let σ and ϵ be some positive constants such that Bob can choose an [n, k, d] linear code for which k > (1/2 + 2σ)n and d > ϵn. The code must be efficiently decodable. The number of errors corrected by the decoding algorithm affects the efficiency of the protocol. It suffices that the algorithm corrects Ω(n) errors to guarantee the asymptotic security of the protocol.

Although Concatenated codes [14] are the most common codes with these properties, we recommend using the Superconcentrator Codes of Spielman [27] for their remarkable efficiency: they can be coded and decoded in linear time. In our protocol, we construct codewords, decode codewords and prove that some words are codewords. All these operations can be achieved in time O(n). In particular, to prove that a committed word is a codeword it is sufficient to prove a linear number of statements each involving only a constant number of committed bits xored together. For more details on coding theory in general we refer the reader to [24].

3.2 Informal Protocol

Intuitively cot( a_{0} , a_{1} )( b ) is performed by doing an imperfect “One-out-of-two Committed Oblivious String Transfer” of two random codewords c_{0} and c_{1}. This transfer is imperfect in the sense that even the honest Bob learns information about both words. He learns all the bits of c_{b} and some bits of cb̄. We use this trick because Bob is not only interested in getting a_{b} and committing to a = a_{b}, but he also wants to know that if he had ran the protocol with b̄ it would have worked as well. This is to prevent Alice from misbehaving on some part of her protocol so to learn b as a result of Bob aborting or not.

In the beginning Alice is committed to a_{0} and a_{1} and Bob to b . Bob chooses a code with suitable properties. Alice commits to c_{0} and c_{1} , two randomly chosen codewords, and proves that this is the case. She Obliviously Transfers c_{0} and c_{1} to Bob in such a way that for each pair of bits Bob can choose to learn one of c_{0} or c_{1}, but not both. Bob reads the bits to learn mostly c_{b} and a small part of cb̄. As suggested above he must gain a little bit of information on cb̄ to prevent Alice from learning which word he is interested in (and thus b). A cheating Alice could use very different words c_{0}, c_{1} in the ots and in the bcs. To prevent this, Alice is forced to open a small fraction of the committed bits on both sides, at Bob’s choosing, to let him check that the bits he received through the ot are the same. If Alice cheats a lot for one of the two words (or both) she will be caught without Bob revealing which one he was interest in. If Alice passes the test, only a small number of inconsistencies can remain between the bits Bob received and the bits Alice is committed to. Bob uses the fact that his word w should be a codeword to correct these.

Bob commits to w = c_{b} and proves to Alice that it is a codeword. It is now Bob’s turn to convince Alice that he is committed to what he actually received through the ot (he is not committed to an arbitrary codeword, but actually to c_{b}). Alice opens a random set of positions and Bob shows that the bits he is committed to are consistent with the bits Alice reveals and b . This is sufficient to convince Alice that Bob is committed to c_{b} without her learning b.

Although Bob is committed to w = c_{b}, he gets some information on cb̄ revealed by the fact that it is a codeword and by the bits opened by Alice in the checks. To get rid of that information, Alice chooses a random privacy amplification [1] function h such that a_{b} = h(c_{b}) and ab̄ = h(cb̄) and proves these two relations to Bob. Bob commits to a = h(w) and proves this to Alice.

3.3 Formal protocol

Before starting the protocol, Alice is committed to a_{0} , a_{1} and Bob to b . After the protocol Bob will be committed to a_{b} . Let σ, ϵ be two positive constants as defined in Section 3.1, and let n denote the security parameter. At any point in the protocol, a failure in a proof or check leads the participants to abort.

Protocol 3.1 ( cot ( a_{0} , a_{1} ) ( b ) )

1: Bob chooses and announces to Alice a decodable [n, k, d] linear code C

with k > (1/2+2σ)n and d > ϵn, efficiently decoding t ∈ Ω(n) errors. 2: Alice randomly picks c_{0}, c_{1} ∈ C, commits to c_{0}^{i} and c_{1}^{i} , for i ∈ {1 … n},

and proves that c_{0}^{1} c_{0}^{2} … c_{0}^{n} ∈ C and c_{1}^{1} c_{1}^{2} … c_{1}^{n} ∈ C.

3: Bob randomly picks I_{0}, I_{1} ⊂ {1...n}, with |I_{0}| = |I_{1}| = σn, I_{1} ∩ I_{0} = ∅

and sets b^{i} ← b̄ for i ∈ I_{0} and b^{i} ← b for i ∉ I_{0}. 4: Alice runs ot(c_{0}^{i}, c_{1}^{i})(b^{i}) with Bob who gets w^{i}, for i ∈ {1, 2, ..., n}. 5: Bob tells I = I_{0} ∪ I_{1} to Alice who opens c_{0}^{i} and c_{1}^{i} , for each i ∈ I. 6: Bob checks that w^{i} = ci ; b̄, for i ∈ I_{0} and that w^{i} = c_{b}^{i}, for i ∈ I_{1},

sets w^{i} ← c_{b}^{i}, for i ∈ I_{0}, corrects w using C’s decoding algorithm, commits to w^{i} , for i ∈ {1 … n}, and proves that w^{1} w^{2} … w^{n} ∈ C.

7: Alice randomly picks and announces a subset I_{2} ⊂ {1...n}

with |I_{2}| = σn, I_{2} ∩ I = ϕ and opens c_{0}^{i} and c_{1}^{i} , for i ∈ I_{2}.

8: Bob proves that w^{i} = ci ; b , for i ∈ I_{2}.

9: Alice randomly picks and announces a privacy amplification function h : {0, 1}^{n} → {0, 1}, such that a_{0} = h(c_{0}) and a_{1} = h(c_{1})

and proves a_{0} = h ( c_{0}^{1} c_{0}^{2} … c_{0}^{n} ) and a_{1} = h ( c_{1}^{1} c_{1}^{2} … c_{1}^{n} ).

10: Bob sets a ← h(w), commits to a and proves a = h ( w^{1} w^{2} … w^{n} ).

3.4 Zero-Knowledge proofs

In the protocol, Alice and Bob make a number of zero-knowledge proofs. All these proofs are easily achieved if we are able to perform xor proofs on committed bits. This is why the protocol uses bcxs and not plain bcs.

In Step 2 and 6 a party must show to the other that a set of committed bits form a codeword. In any linear code, this operation can be achieved by showing that the syndrome of the word is the zero-vector. This takes O(n^{2}) bcx operations. In the case of Superconcentrator Codes, it is sufficient to prove that each bit is the xor of a constant number of (publicly known) other bits of the word. Therefore it takes only O(n) bcx operations.

In Step 8 Bob must prove to Alice that w^{i} = ci ; b, for i ∈ I_{2}. First, for each position in which c_{0}^{i} = c_{1}^{i}, Bob can simply open w^{i} because in this case w^{i} contains no information on b. For the other positions, where c_{0}^{i} ≠ c_{1}^{i}, one of c_{0} or c_{1} must be 0 and the other must be 1. When c_{0} = 0 and c_{1} = 1 we have c_{b}^{i} = b, therefore Bob proves w^{i} ⊕ b = 0. In the opposite situation c_{b}^{i} = b̄, therefore Bob proves w^{i} ⊕ b = 1. Both of these proofs give no information on b and take constant time. The total for all the positions in I_{2} is O(n) bcx operations.

In Step 9 and 10 a party must show to the other that z = h ( x^{1} x^{2} ⋯ x^{n} ) for some committed bit z and word x. If h is a random linear function specified by a public random subset H of the bits of x it defines a universal hash function [4]. In this case it suffices to show z⊕⨁_{i∈H}x^{i} = 0 which takes O(n) bcx operations.

3.5 Validity of the Protocol

There are several ways in which Alice and Bob may misbehave when they execute our protocol. At any point Alice or Bob can decide to stop cooperating and they can commit to values different from those used in the oblivious transfer. The main point is that Bob cannot claim to be committed to a_{b} if he is not, and that even if the protocol aborts no unintended information leaks.

Bob cannot commit to \overline{a_{b}}. First observe that we cannot force Bob to commit to a_{b} after he has learned this value in Step 9. However, this is equivalent to the situation in which Bob refuses to open a after the protocol since an unopened a is useless to Alice. So the only important fact is that if the protocol has completed without complaints and Bob is committed to a bit, this must be a_{b}.

We show informally why this is true. Suppose Bob commits to a = \overline{a_{b}}. This means that he has proved at Step 10 that \overline{a_{b}} = h(w). Since a_{b} = h(c_{b}) this implies that w ≠ c_{b}. Bob has proved at Step 6 that w is a codeword, so the Hamming distance between w and c_{b} is greater than ϵn or, equivalently, they differ in more than ϵn positions. But Alice has asked Bob to open σn positions chosen at random and for all these positions the bits were equal to their counterparts in c_{b}. This cannot happen except with a probability exponentially small in n.

Alice learns nothing about b. It is not hard to see that if Alice performs cot honestly she learns nothing about b. Furthermore, regardless of how Alice cheats, she gains no information about b. A straightforward analysis of each step of the protocol shows that only in Step 1, 5, 6, 8 and 10 Bob sends actual information to Alice. In Step 1 and 5 the information is independent of b. For Step 6,8 and 10 the definition of bc and the fact that the proofs are Zero-knowledge guarantee that Alice learns nothing about b. The only other way Alice could learn information would be to misbehave in such a way that Bob has to abort if b = 0 (or b = 1) in Steps 7 or 9. This way she could learn b and Bob would catch her only if b = 1 (or b = 0).

In Step 10 Bob will always succeed since he calculates a himself. If Bob fails the proofs at Step 6 or 8, this implies that w^{1} w^{2} … w^{n} ≠ c_{b}^{1} c_{b}^{2} … c_{b}^{n} . But since c_{b} is a codeword (as proved in Step 2) this means that their Hamming distance is at least t because otherwise the decoding algorithm would have led to c_{b}. Since t ∈ Ω(n) the check of Step 6 has only an exponentially small probability of success. Thus, if the check of Step 6 succeeds, the proofs of Step 6 and 8 will fail with exponentially small probability whatever b is. And since |I_{0}| = |I_{1}| the check of Step 6 has the same probability of success whatever b is.

Bob learns nothing about a\overline{b}. Alice does not want a dishonest Bob to learn ab̄. In fact it is not sufficient that Bob learns no information about ab̄. We want that for all dishonest Bob′ the amount of information he has about ab̄ after interacting with Alice will be the same as before, even if he knew a_{b} to start with. This is to ensure that Bob does not learn any correlation between a_{0} and a_{1} through our protocol, for instance a_{b} ⊕ ab̄.

Note that the information on a_{0} and a_{1} is completely uncorrelated. Because Alice picks c_{0} and c_{1} at random, no information about ab̄ is sent before she reveals h. For Bob to learn h he must pass Alice’s test of Step 8 and convince her that he is committed to w = c_{b}. If Bob wishes to have no more than 2^{σn/2} candidates for a_{b} by the time he commits at Step 6, he must have acquired on side b at least n/2 + 3σn/2 of the n + 2σn bits available to him through Step 4 and 5. This is the case because there are 2^{n/2+2σn} codewords, and thus after learning n/2 + 3σn/2 extra bits, 2^{σn/2} of them remain equally possible. If Bob gets n/2 + 3σn/2 bits on side b, it leaves him with no more than n/2 + σn/2 bits on side b̄ of the n + 2σn bits available. In this case there are also 2^{σn/2} candidates for cb̄ even after learning σn extra bits at Step 7.

In conclusion, if Bob gains as few as n/2 + 3σn/2 bits on side b, he has probability no more than 2^{−σn/2} of committing to the right codeword at Step 6, and any wrong codeword will have at least ϵn differences with the correct one. In this case the test of Step 8 would have an exponentially small probability in n of succeeding. On the other hand, if Bob gains as few as n/2 + σn/2 bits on side b̄ then, by a theorem of Bennett, Brassard and Robert [1], his probability of obtaining any information whatsoever about h(cb̄) is less than 2^{−σn/2} provided h is chosen at random.

3.6 Complexity of the protocol

The exact complexity of the protocol depends on the kind of bcs and ots used by the participants. We thus make our analysis based on the number of bcs and ots that are required to perform the protocol. If the ot and bc being used require a constant number of communication rounds, then all the ots and proofs can be done in parallel and the cot protocol also requires a constant number of rounds.

The protocol uses O(n) ots which are performed in Step 2, when c_{0} and c_{1} are transferred. It also requires O(n) bcxs for both Alice and Bob to commit to c_{0},c_{1} resp. w. All the proofs on the bcxs can be done with only O(n) bcx operations.

If the bcxs are not available one can use the trick described in Section 2.2. To perform cot, O(n^{2}) bcs are used to perform the O(n) necessary bcx operations. In this case, the overall complexity is O(n) ots and O(n^{2}) bc operations.

4 Extension of the primitives to multiple participants

The second goal of this paper is to describe a protocol for Multi-Party Computation. To reach this goal, we enhance bcx and cot (prefixed with g for “global”), allowing other participants (who do not provide an input) to act as “verifier” to check that the active participant(s) behave honestly. Secondly we show how cot can be used to obtain a protocol for evaluating a partial and gate between two participants, a mandatory step for pmpc.

4.1 Global Bit Commitment with XOR proof (GBCX)

A Global Bit Commitment with xor (gbcx) is a bit commitment to a group of participants. A gbcx is conceptually equivalent to P − 1 bcxs, one to each participant, all with the same value. gbcxs are constructed such that a dishonest participant A cannot open it as a different value to two honest participants B_{j}, B_{k}. An obvious, but very inefficient way to achieve this is that A proves to each pair of participants that the two bcxs they hold are equal.

We show how to do this more efficiently. To commit to a bit a using a gbcx, A makes 2n(P − 1) pairs of (plain) bcs, 2n to each of the other participants B_{1}...B_{P −1}, such that for i ∈ {1...2n} and j ∈ {1...(P − 1)}, a_{iL}^{j} ⊕ a_{iR}^{j} = a. Then each B_{j} chooses and broadcasts a random permutation of size 2n and renames his 2n pairs accordingly. For i ∈ {1...n} A announces V_{i}^{0} ← {j : (a_{iL}^{j}, a_{iR}^{j}) = (0, a)} and V_{i}^{1} ← {j : (a_{iL}^{j}, a_{iR}^{j}) = (1, ā)} in a random order. Then all participants flip n fair coins together (requiring O(nP) bcs) to construct a random tuple

(S_{1}...S_{n}) ∈ {L, R}^{n}. For i ∈ {1...n}, j ∈ {1...P − 1} A opens a_{iS_{i}}^{j}. Finally, each B_{j} verifies that the values of the a_{iS_{i}}^{j} opened to him correspond with those broadcasted, and that W_{i} ← {j : a_{iS_{i}}^{j} = 0} equals either V_{i}^{0} or V_{i}^{1}.

After this protocol A has n pairs of untouched bcs with each B_{j} (those with i ∈ {(n + 1)...2n}), which constitute the new gbcx. It is easy to verify that if A tries to commit to two different bits with two honest participants, or if he tries to construct inconsistent commitments, he will be caught by each pair of honest participants except with exponentially small probability.

Although the role of A (the “active” participant) is different from the role of the B_{j}s (the “passive” participants) in the protocol, the cost of creating a gbcx is the same for everybody, O(P n) bcs. Once created, operations on gbcxs, such as proving linear relations and copying, are reduced to P operations between A and B_{j} using bcxs. For A the cost of one such operation is O(P n), but for the B_{j} it is only O(n) (since after the creation they do not need to interact with other users).

4.2 Global Committed Oblivious Transfer (GCOT)

Global Committed Oblivious Transfer (gcot) is the extension of cot to a group. For Alice and Bob gcot achieves exactly the same functionality as cot but it allows the passive participants to be convinced that Alice and Bob do not conspire, i.e. that indeed after gcot( a_{0} , a_{1} )( b ) Bob is committed to a_{b} .

Some modifications are necessary to change cot to gcot: (1) The errorcorrecting code C of Step 1 must be chosen by all participants; (2) bcxs are replaced by gbcxs and all commitment openings and proofs are done to each participant; (3) the subset I_{2} in Step 7 must be chosen by all participants.

In order to choose I_{2}, only O(n log(n)) random coins have to be flipped, at the expense of O(P n log(n)) plain bcs for each participant. When many gcots on different inputs are performed in parallel, as will be the case in the evaluation of and gates in the final protocol, the same I_{2} may be used. Therefore we do not take this cost into account in the next paragraph, but deal with it later.

For one gcot Alice and Bob have to perform O(n) active gbcx operations (resulting in a total of O(P n^{2}) bcs) and O(n) ots. The others have to perform O(n) passive gbcx operations (resulting in O(n^{2}) bcs).

4.3 PAND and GPAND

As a step towards pmpc we introduce a two-party protocol, called pand, that takes the bcxs a from Alice and b from Bob as inputs. After the execution of pand Alice is committed to a′ and Bob to b′ such that a ∧ b = a′ ⊕ b′, and neither participant learns the other’s input value. Since the output is composed of the pair a′ and b′, we call this protocol pand for Pair-AND.

We implement pand using cot. Alice randomly chooses a bit a′, commits to a′′ = a′ ⊕ a and proves it. Then Alice performs cot( a′ , a′′)( b ) with Bob who gets b′ . (Notice that b = 0 ⇒ b′ = a′ ⇒ a′ ⊕ b′ = 0 and that b = 1 ⇒ b′ = a′ ⊕ a ⇒ a′ ⊕ b′ = a, so a ∧ b = a′ ⊕ b′.)

gpand is a generalization of the pand to a group: two active participants want to make a pand, while the passive participants want to be sure that indeed a ∧ b = a′ ⊕ b′ . The gpand is done as a pand, with cot replaced by gcot. The cost of one gpand is of the same order as the cost of one gcot, both for the active and the verifying participants.

5 Private Multi-Party Computation (PMPC)

In this section we show how, given ot and bc between each pair of participants and a reliable Broadcast Channel, P participants can perform a correct, honest, fair and private Multi-Party Computation, where we make no assumptions about the number of honest participants. The protocol consists of three steps: initialization, computation and revelation. At each step we make extensive use of the primitives previously defined.

5.1 Initialization

In the initialization step all participants agree on the circuit F to be evaluated and on a security parameter n. They also agree on a parameter σ and a code C for the gcot sub-protocol.

In the pmpc protocol each bit involved is represented by a Distributed Bit Commitment (dbc) consisting of P shares, each share being a gbcx created by a different participant. The value of a dbc is the xor of the value of its shares, therefore even P − 1 participants are not able to reconstruct the value of the dbc if one participant refuses to cooperate.

As a second part of the initialization step each participant uses dbcs to commit to his input bits. To create a dbc of value a, A asks each participant to commit to a random bit using a gbcx, and to open it to A only. Then A creates a gbcx such that the xor of all the gbcxs equals a.

5.2 Computation

In the computation step the participants evaluate the circuit consisting of and and not gates, one gate after the other, where the input and output bits of each gate are dbcs.

Since the output bit of a gate can be an input bit to several other gates we must be able to copy dbcs. To make r copies of a dbc each participant makes r copies of his share (a gbcx). The not operation on a dbc is equivalent to a copy, except that one designated participant inverts the value of his gbcx.

To evaluate an and gate on two dbcs of value a and b we observe that (⨁_{i=1}^{n} a_{i}) ∧ (⨁_{j=1}^{n} b_{j}) = ⨁_{i,j=1}^{n} a_{i} ∧ b_{j}. In other words, one Distributed and can be reduced to P^{2} gpands, one between each pair of participants. After all the gpands have been done each participant chooses a gbcx that equals the xor of all his shares and he proves this. This gbcx is his share of the dbc whose value equals a ∧ b.

To evaluate one and gate O(P^{2}) gpands and so O(P^{2}) gcots are executed. Each participant will be actively involved in P gcots, each requiring O(n) ots and O(n) active gbcxs operations. Each participant also verifies O(P^{2}) gcots between other participants. For one such gcot verification he is involved in O(n) passive gbcx operations. Therefore each participant is involved in O(P n) active gbcxs and O(P^{2}n) passive gbcxs. This results in O(P^{2}n^{2}) bcs and in O(P n) ots.

We must also take into account the cost for creating the subset I_{2} used in every gcot. Only one random I_{2} suffices for many parallel gcots, and since the creation of a single I_{2} requires O(n log(n)) coin flips, it requires a total of O(P n log(n)) bcs per participant. This does not change the previously stated complexity.

5.3 Revelation

At the end of the computation step each output bit of the circuit is hidden in a dbc. In order for each honest participant to learn an output bit of F, every participant could open his share of the dbc representing the answer, but obviously a dishonest participant could quit when he has more information than others. Better solutions, which achieve fairness, appear in the literature [6][18]. They can easily be incorporated into our protocol.

5.4 The validity of the PMPC protocol

We do not claim to provide a full proof that the protocol presented here is secure. The security of the final protocol relies on the security of all the subprotocols that constitute it. Due to space restrictions, we only give a brief and sketchy proof that pmpc satisfies the four desired properties mentioned in the introduction.

Correctness: If all participants are honest the output of our protocol should equal the output of the function to be emulated. This is verified because each sub-protocol outputs the value it is designed for.

Privacy: Observe that from a participant’s point of view the gbcx is the smallest “unit” to which he can commit and that no coalition can open it if the owner does not cooperate. Because of the way each dbc is constructed each participant holds a share of each bit of the computation, so for all sub-protocols no information about the values of the dbcs is revealed as long as at least one participant is honest. Therefore, before the revelation of the output bits no coalition of less than P participants can obtain any information whatsoever on the input bits, intermediate bits or output bits of the computation, except for what can be deduced from the information already known by the coalition. A more formal analysis along these lines could benefit from the definition of privacy given in [23].

Fairness: This is an issue in the revelation step only. We want to prevent one or several parties from learning more information on the output bits before the others. For the fairness of our protocol we totally rely on the model and definitions given by Goldwasser and Levin [18]. Though the implementation of their protocol differs from ours their model still applies, in particular their notion of fairness.

Honesty: Note that no coalition of participants can cheat on the resulting output dbcs of any sub-protocol. For the full protocol this means that, once the input bits have been committed to, no coalition of less than P players can change the values of an output dbc without being caught (except with exponentially small probability). In other words, even though any coalition can disrupt the protocol by preventing it from completing, no coalition can make an honest participant accept the output of F when any of the output dbcs has been tampered with.

5.5 Complexity of the PMPC protocol

It is easy to see that to evaluate a circuit F composed of m gates O(m) dbc operations are needed. The most expensive operation on dbcs is the evaluation of an and gate, so the overall complexity of the pmpc protocol is O(P^{2}n^{2}m) bcs and O(P nm) ots. Since bc and ot can be implemented using O(n) of Rabin’s Oblivious Transfers, pmpc can be performed using O(P^{2}n^{3}m) of them.

Acknowledgments

We thank Joe Kilian and Matt Franklin for providing references. We give special thanks to Mélanie and Marie-France for their patience and understanding.

References

1. C.H. Bennett, G. Brassard, J.-M. Robert, Privacy Amplification by Public Discussion, SIAM Journal on Computing, Vol. 17, No.2, 1988, pp. 210–229.

2. C.H. Bennett, G. Brassard, C. Crépeau, M.-H. Skubiszewska, Practical Quantum Oblivious Transfer, Advances in Cryptology - CRYPTO’91, Springer-Verlag, 1992, pp. 351–366.

3. G. Brassard, C. Crépeau, R. Jozsa, D. Langlois, A Quantum Bit Commitment Scheme Provably Unbreakable by both Parties, 34th IEEE Symposium on Foundation of Computer Science, 1993, pp. 362–371.

4. J. L. Carter and M. N. Wegman, Universal Classes of hash function, Journal of Computer and System Sciences, Vol. 18, 1979, pp. 143-154.

5. D. Chaum, I. Damgård and J. van de Graaf, Multiparty computations ensuring privacy of each party’s input and correctness of the result, Advances in Cryptology - CRYPTO’87, Springer-Verlag, 1988, pp. 87–119.

6. R. Cleve, Controlled Gradual Disclosure Schemes for Random Bits and Their Applications, Advances in Cryptology - CRYPTO’89, Springer-Verlag, 1991, pp. 573– 590.

7. C. Crépeau, Equivalence Between Two Flavours of Oblivious Transfer, Advances in Cryptology - CRYPTO’87, Springer-Verlag, 1988, pp. 350-354.

8. Crépeau, C., Verifiable Disclosure of Secrets and Applications, Advances in Cryptology - Eurocrypt’89, Springer-Verlag, 1990, pp. 181–191.

9. C. Crépeau, Correct and Private Reductions Among Oblivious Transfers, Ph.D. thesis, MIT, 1990.

10. C. Crépeau, Quantum Oblivious Transfer, Journal of Modern Optics, vol. 41, No. 12, 1994.

11. C. Crépeau, J. Kilian, Achieving Oblivious Transfer Using Weakened Security Assumptions, 29th IEEE Symposium on Foundation of Computer Science, 1988, pp. 42–52.

12. C. Crépeau, Cryptographic protocol based on noisy channel, in preparation, 1995.

13. S. Even, O. Goldreich and A. Lempel, A Randomized Protocol for Signing Contracts, Communications of the ACM, Vol 28, 1985, pp. 637-647.

14. Forney, G. D., Concatenated Codes, The M.I.T. Press, 1966.

15. M. Franklin, Complexity and security of distributed protocols, Ph. D. thesis, Computer Science Department of Columbia University, New York, 1993.

16. O. Goldreich, S. Micali, and A. Wigderson, How to play any mental game, or: A completeness theorem for protocols with honest majority, 19th ACM Symposium on Theory of Computing, 1987, pp. 218–229.

17. O. Goldreich, R. Vainish, How to solve any protocol problem — an efficiency improvement, Advances in Cryptology - CRYPTO’87, Springer-Verlag, 1988, pp. 73– 86.

18. S. Goldwasser, L. Levin, Fair computation of general functions in presence of moral majority, Advances in Cryptology - CRYPTO’90, Springer-Verlag, 1991, pp. 77–93.

19. J. Kilian, Founding cryptography on Oblivious transfer, 20th ACM Symposium on Theory of Computation, 1988, pp. 20–31.

20. J. Kilian, Uses of Randomness in Algorithms and Protocols, MIT Press, 1990.

21. J. Kilian, A note on efficient zero-knowledge proofs and arguments, 24th ACM Symposium on Theory of Computation, 1992, pp. 723–732.

22. J. Kilian, On the complexity of bounded-interaction and noninteractive zeroknowledge proofs, 35th IEEE Symposium on Foundations of Computer Science, 1994, pp. 466-477.

23. E. Kushilevitz, S. Micali, R. Ostrovski, Reducibility and completeness in multiparty private computations, 35th IEEE Symposium on Foundations of Computer Science, 1994, pp. 478-489.

24. F. J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.

25. M. Naor, Bit Commitment using Pseudo-Randomness, Advances in Cryptology - CRYPTO’89, Springer-Verlag, 1989, pp. 128–136.

26. M. Rabin, How to exchange secrets by oblivious transfer, Tech. Memo TR–81, Aiken Computation Laboratory, Harvard University, 1981.

27. D. Spielman, Linear-Time Encodable and Decodable Error-Correcting Codes, 27th ACM Symposium on Theory of Computing, 1995, pp. 388–397.

This article was processed using the LaTEX macro package with LLNCS style