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 .
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.
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…