[table of contents]
Let us first look at a simple special case, namely where each is a natural number, and
. Secure computation of even such a simple function can have very meaningful applications. Consider the case where
want to vote on some yes/no decision. Then we can let
represent the vote of
where
means “no” and
means “yes”. If we can compute the sum of the
securely, this exactly means we get a way to vote with the properties we usually expect: the result
is indeed the result of the vote, namely the number of yes-votes. Moreover, if the computation is secure, no information is leaked other than
, in particular, no information is revealed on how a particular player voted.
We will now design a protocol for the voting application. To be consistent with the next example we give, we set . A simple mental exercise will allow the reader to extend to a voting solution for any
.
Secret Sharing
Before we can solve the problem, we need to look at an important tool known as secret sharing. The term may seem self-contradictory at first sight: how can anything be secret if you share it with others? Nevertheless, the name makes good sense: the point is that secret sharing provides a way for a party, say , to spread information on a secret number
across all the players, such that they together hold full information on
, yet no player has any information on
. First, we choose a prime
, and we define
as
In the following, we will think of the secret
as a number in
.
In order to share the secret ,
chooses numbers
uniformly at random in
, and sets
.
Put another way: he chooses randomly from
subject to the constraint that
. Recall that
means that you add
and
and then substract (or add) $p$ as many times as you need to end up in the interval
again. For instance
.
Note that this way of choosing means that each of the three numbers is uniformly chosen in
: for each of them, all values in
are possible and equally likely. Now
sends privately
to
,
to
, and keeps
himself. The
‘s are called the shares of the secret
.
The process we have described satisfies two basic properties: First, the secret is kept private in the sense that neither
nor
knows anything about that secret. As a result if some hacker breaks into the machine of
or
(but not both) he will learn nothing about
. Second,
can be reconstructed if shares from at least two players are available. Let us argue that this is true in a more precise way:
- Privacy: Even though
has distributed shares of the secret
to the other players, neither
nor
has any idea what
is. For
we can argue as follows: he knows
(but not
) and that
. Take any
. From
‘s point of view, could it be that
? The answer is yes, for if
it would have to be the case that
. This is certainly a possibility, recall that
is uniformly chosen in
, so all values are possible. However, any other choice, say
is also a possibility. If this was the answer we would have
, which is a value different from
, but just as likely. We conclude that what has been sent to
reveals nothing new about
. A similar argument shows that the same is true from
‘s point of view.
- Correctness: If two of the three parties pool their information, the secret can be reconstructed, since then all three shares will be known and one can simply add them modulo
.
Note that the privacy property is information theoretic: as long a party does not know all three summands, no amount of computing power can give him any new information on the corresponding secret. The secret sharing technique shown above is a special case of so-called replicated secret sharing. There are many ways to realise secret sharing with other desirable properties than the method we show here. If you are interested in learning other techniques are more precise definition of secret sharing, I have heard that this is a really in-depth book on the subject.
A Protocol for Secure Addition
The basic idea for secure addition is that all players and
will distribute shares of their private values
and
in exactly the way we saw before. It turns out that one can now compute the sum securely by locally adding shares and announcing the result. The complete protocol is shown below.
Secure Addition
Participants are , input for
is
, where
is a fixed prime agreed upon in advance.
- Each
computes and distributes shares of his secret
as described in the text: he chooses
uniformly at random in
, and sets
.
- Each
sends privately
to
,
to
, and
to
(note that this involves
sending “to himself”). So
, for instance, now holds
,
and
.
- Each
adds corresponding shares of the three secrets — more precisely, he computes, for
,
, and announces
to all parties. So each party will compute and announce two values.
- All parties compute the result
.
To analyse the secure addition protocol, let us first see why the result is indeed the correct result. This is straightforward:
.
This shows that the protocol computes the sum modulo of the inputs, no matter how the
‘s are chosen. However, if we let the parties choose
for yes and
for no, and make sure that
, then
, because all
are
or
and so their sum cannot be larger than
. So in this case,
is indeed the number of yes-votes.
Now, why is it the case that no new information other than the result is leaked to any player? Let us concentrate on
for concreteness. Now, in step 1,
and
are secret shared, and we have already argued above that this tells
nothing whatsoever about
. In the final step,
are announced. Note that
already knows
, so
is the only new piece of information. However, we can argue that seeing
will tell
what
is and nothing more. The reason for this is that, if one is given
and
, one can compute
. Put another way: given what
is supposed to know, namely
, we can already compute what he sees in the protocol, namely
, and therefore seeing the information from the protocol tells him nothing beyond
.
This type of reasoning is formalised later theoretical cryptography and is called a simulation argument: given what a player is supposed to know, we show how to efficiently compute (simulate) everything he sees in the protocol, and from this, we conclude that the protocol tells him nothing beyond what we wanted to tell him.
Note that given the result, is in fact able to compute some information about other people’s votes. In particular, he can compute
, i.e., the sum of the other players’ votes. It is easy to get confused and think that because of this, something must be wrong with the protocol, but in fact there is no problem: it is true that
can compute the sum of the votes of
and
, but this follows from information
is supposed to know, namely the result and his own input. There is nothing the protocol can do to deprive him of such information — in other words, the best a protocol can do is to make sure players only learn what they are supposed to learn, and this includes whatever can be derived from the player’s own input and the intended result.
That was easy! Let us take a look at multiplication…