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