as b := bA ⊕ bB (where “⊕” denotes the x or function). Clearly if at least one of the bits bA and bB is uniformly random, then b is also uniformly random, and hence each party can be sure that the game is fair, as long as she behaves honestly (i.e., chooses her bit uniformly). When one tries to implement this protocol over the Internet, then of course, the main challenge is to ensure that Alice and Bob send their bits simultaneously. This is because if one party, say Alice, can choose her bit bA after she learns bB, then she can make b equal to any value b′ she wants by choosing bA := b′ ⊕ bB.

The solution proposed in Blum6 is to use a tool called a cryptographic commitment scheme. Informally, such a scheme is a two-party protocol executed between a committer and a receiver. At the beginning, the committer knows some value s that is secret to the receiver. The parties first perform the commitment phase (Commit). After this phase is executed, the receiver still does not know s (this property is called hiding). Later, the parties execute the opening phase (Open) during which the receiver learns s. The key property of a commitment scheme is that the committer cannot “change his mind” after the commitment phase. More precisely, after the first phase is executed, there exists precisely one value s that can be opened in the second phase. This property is called binding. In some sense, the commitment phase is analogous to sending a message s in a locked box, and the opening phase can be thought of as sending the key to the box. Clearly after the box is sent, the committer cannot change its contents, but before getting the key, the receiver does not know what is inside the box.

There exist several secure methods of constructing such commitments. In this paper, we use the ones that are based on the cryptographic hash functions (see Section 3).

It is now easy to see how a commitment scheme can be used to solve the coin-tossing problem: instead of sending her bit bA directly to Bob, Alice just commits to it (i.e., Alice and Bob execute the commitment scheme with Alice acting as the committer, Bob acting as the receiver, and bA being the secret). Symmetrically, Bob commits to his bit bB. After this commitment phase is over, the parties execute the opening phase and learn each other’s bits. Then the output is computed as b = bA ⊕ bB. The security of the commitment scheme guarantees that no party can choose her bit depending on the bit of the other party, and hence this procedure produces a uniformly random bit.

Boolean operations. The coin-tossing example above is a particularly simple case of a multiparty protocol since the parties that execute it do not take any inputs. To explain what we mean by a protocol where the parties do take inputs, consider the case when the function that Alice and Bob compute is the conjunction f ∧ (a, b) = a ∧ b, where a, b ∈ {0, 1} are Boolean variables denoting the inputs of Alice and Bob, respectively. This is sometimes called the marriage proposal problem since one can interpret the input of each party as a declaration if she/he wants to marry the other one. More precisely, suppose a = 1 if and only if Alice wants to marry Bob, and b = 1 if and only if Bob wants to marry Alice. In this case f ∧ (a, b) = 1 if and only if both parties want to marry each other, and hence, if for example, b = 0, then Bob after learning the output of the function has no information about Alice’s input. Therefore, the privacy of Alice is protected.

One can generalize this example and consider the
set-intersection problem. Here Alice and Bob have sets A and
B as their inputs and the output is equal to f ∩ (A, B) = A ∩ B. For
example, think of A and B as sets of e-mail addresses in Alice’s
and Bob’s contact lists—then the output f ∩(A, B) is the list
of the contacts that they have in common. The security here
means that: ( 1) the parties do not learn about each other’s
input more than they can deduce from their own input and
the output, and ( 2) a malicious party cannot cause the result
to be incorrect (e.g., a corrupt Alice cannot falsely make Bob
think that some e-mail address is in her contact list). For this
example, condition ( 1) means that for every a ∉ A, Alice should
obtain no information if a is in B (and symmetrically for Bob).
General results and the lack of “fairness.” The above exam-
ples can be generalized in several ways. First of all, one can
consider protocols executed among groups of parties of size
larger than two (hence the name MPCs, as opposed to the
two-party examples above). For example, a multiparty coin-
tossing protocol is specified exactly as the two-party one,
except that the number of the participants is larger than two.
Second, one can consider more complicated functions
than the ones described above. It was shown in Goldreich
et al. 14 that for any efficiently computable function f (includ-
ing “randomized” functions like the one in the coin-tossing
example), there exists an efficient protocol that securely
computes it, assuming the existence of trapdoor permu-
tations (which is a well-established assumption, widely
believed to hold). If a minority of the parties is malicious (i.e.,
does not follow the protocol), then the protocol always termi-
nates, and the output is known to each honest participant.
However, if more than half of the parties are malicious, then
the malicious parties can terminate the protocol after learn-
ing the output, preventing the honest parties from learn-
ing it. Note that in case of two-player protocols, it makes no
sense to assume that the majority of the players is honest, as
this would simply mean that none of the players is malicious.
This problem is visible in the coin-tossing example above,
as each party can refuse to open her commitment after she
learned what was the bit of the other party. In some cases,
this is not a problem since the parties can agree that refusing
to open the commitment is equivalent to losing the game.

However, it turns out9 that in general this problem, called the lack of fairness, is unavoidable. Hence, two-party protocols in general do not provide complete fairness.

Why are the MPC not widely used over the Internet? Since the introduction of MPCs there has been a significant effort to make these protocols efficient4, 10, 16 and sometimes even to use them in the real-life applications such as the online auctions. 7 On the other hand, perhaps surprisingly, the MPCs have not been used in many other areas where seemingly they would fit perfectly. One prominent example is Internet gambling: it may be intriguing that currently gambling over the Internet is done almost entirely with the help of websites that play the roles of “trusted parties,” instead of using a cryptographic coin-flip-ping protocol to eliminate the need for trust. This situation is clearly unsatisfactory from the security point of view, especially since in the past, there were cases when the operators of these sites abused their privileged position for their own financial gain. 18 Hence, it may look like the multiparty techniques that eliminate the need for a trusted party would be a perfect