Secure Addition and Voting

[table of contents]

Let us first look at a simple special case, namely where each x_i is a natural number, and f(x_1,\ldots,x_n) = \sum_{i=1}^n x_i. Secure computation of even such a simple function can have very meaningful applications. Consider the case where \mathsf{P}_1, \ldots,\mathsf{P}_n want to vote on some yes/no decision. Then we can let x_i represent the vote of \mathsf{P}_i where x_i=0 means “no” and x_i=1 means “yes”. If we can compute the sum of the x_i securely, this exactly means we get a way to vote with the properties we usually expect: the result \sum_{i=1}^n x_i 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 \sum_{i=1}^n x_i, 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 n=3. A simple mental exercise will allow the reader to extend to a voting solution for any n.

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 \mathsf{P}_1, to spread information on a secret number x across all the players, such that they together hold full information on x, yet no player has any information on x. First, we choose a prime p, and we define \mathbb{Z}_p as \mathbb{Z}_p= \{ 0,1,..., p-1\} In the following, we will think of the secret x as a number in \mathbb{Z}_p.

In order to share the secret s, \mathsf{P}_1 chooses numbers r_{1}, r_{2} uniformly at random in \mathbb{Z}_p, and sets

r_{3}= x- r_{1} - r_{2} \bmod p .

Put another way: he chooses r_{1},r_{2},r_{3} randomly from \mathbb{Z}_p subject to the constraint that x= r_{1}+r_{2}+r_{3}\bmod p. Recall that a+b \bmod p means that you add a and b and then substract (or add) $p$ as many times as you need to end up in the interval 0, \ldots, p-1 again. For instance 7 + 5 \bmod 10 = 12 \bmod 10 = 2.

Note that this way of choosing r_1, r_2, r_3 means that each of the three numbers is uniformly chosen in \mathbb{Z}_p: for each of them, all values in \mathbb{Z}_p are possible and equally likely. Now \mathsf{P}_1 sends privately r_{1}, r_{3} to \mathsf{P}_2, r_{1}, r_{2} to \mathsf{P}_3, and keeps r_{2}, r_{3} himself. The r_{j}‘s are called the shares of the secret x.

replicatedsecretsharing.png

The process we have described satisfies two basic properties: First, the secret x is kept private in the sense that neither \mathsf{P}_2 nor \mathsf{P}_3 knows anything about that secret. As a result if some hacker breaks into the machine of \mathsf{P}_2 or \mathsf{P}_3 (but not both) he will learn nothing about x. Second, x 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 \mathsf{P}_1 has distributed shares of the secret x to the other players, neither \mathsf{P}_2 nor \mathsf{P}_3 has any idea what x is. For \mathsf{P}_2 we can argue as follows: he knows r_{1}, r_{3} (but not r_{2}) and that x= r_{1}+r_{2}+r_{3}\bmod p. Take any x_0\in \mathbb{Z}_p. From \mathsf{P}_2‘s point of view, could it be that x=x_0? The answer is yes, for if x=x_0 it would have to be the case that r_{2} = x_0 -r_{1} - r_{3}\bmod p. This is certainly a possibility, recall that r_2 is uniformly chosen in \mathbb{Z}_p, so all values are possible. However, any other choice, say x= x'_0\neq x_0 is also a possibility. If this was the answer we would have r_{2} = x'_0 -r_{1} - r_{3}\bmod p, which is a value different from x_0 -r_{1} - r_{3}\bmod p, but just as likely. We conclude that what has been sent to \mathsf{P}_2 reveals nothing new about x. A similar argument shows that the same is true from \mathsf{P}_3‘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 p.

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 \mathsf{P}_1, \mathsf{P}_2 and \mathsf{P}_3 will distribute shares of their private values x_1, x_2 and x_3 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 \mathsf{P}_1, \mathsf{P}_2, \mathsf{P}_3, input for \mathsf{P}_i is x_i\in \mathbb{Z}_p, where p is a fixed prime agreed upon in advance.

  1. Each \mathsf{P}_i computes and distributes shares of his secret x_i as described in the text: he chooses r_{i,1}, r_{i,2} uniformly at random in \mathbb{Z}_p, and sets r_{i,3}= x_i- r_{i,1} - r_{i,2}\bmod p.
  2. Each \mathsf{P}_i sends privately r_{i,2}, r_{i,3} to \mathsf{P}_1, r_{i,1}, r_{i,3} to \mathsf{P}_2, and r_{i,1}, r_{i,2} to \mathsf{P}_3 (note that this involves \mathsf{P}_i sending “to himself”). So \mathsf{P}_1, for instance, now holds r_{1,2}, r_{1,3}, r_{2,2}, r_{2,3} and r_{3,2}, r_{3,3}.
  3. Each \mathsf{P}_j adds corresponding shares of the three secrets — more precisely, he computes, for \ell\neq j, s_\ell= r_{1,\ell} + r_{2,\ell} + r_{3,\ell}\bmod p, and announces s_{\ell} to all parties. So each party will compute and announce two values.
  4. All parties compute the result v= s_1+s_2+s_3 \bmod p.

To analyse the secure addition protocol, let us first see why the result v is indeed the correct result. This is straightforward:

v= \sum_j s_j \bmod p = \sum_j\sum_i r_{i,j} \bmod p= \sum_i\sum_j r_{i,j}\bmod p=\sum_i x_i \bmod p.

This shows that the protocol computes the sum modulo p of the inputs, no matter how the x_i‘s are chosen. However, if we let the parties choose x_i=1 for yes and x_i=0 for no, and make sure that p>3, then \sum_i x_i \bmod p = \sum_i x_i, because all x_i are 0 or 1 and so their sum cannot be larger than p. So in this case, v is indeed the number of yes-votes.

Now, why is it the case that no new information other than the result v is leaked to any player? Let us concentrate on \mathsf{P}_1 for concreteness. Now, in step 1, x_1,x_2 and x_3 are secret shared, and we have already argued above that this tells \mathsf{P}_1 nothing whatsoever about x_2, x_3. In the final step, s_1, s_2, s_3 are announced. Note that \mathsf{P}_1 already knows s_2, s_3, so s_1 is the only new piece of information. However, we can argue that seeing s_1 will tell \mathsf{P}_1 what v is and nothing more. The reason for this is that, if one is given s_2, s_3 and v, one can compute s_1= v - s_2- s_3\bmod p. Put another way: given what \mathsf{P}_1 is supposed to know, namely v, we can already compute what he sees in the protocol, namely s_1, and therefore seeing the information from the protocol tells him nothing beyond v.

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, \mathsf{P}_1 is in fact able to compute some information about other people’s votes. In particular, he can compute v- x_1 = x_2+x_3, 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 \mathsf{P}_1 can compute the sum of the votes of \mathsf{P}_2 and \mathsf{P}_3, but this follows from information \mathsf{P}_1 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…

%d bloggers like this:
search previous next tag category expand menu location phone mail time cart zoom edit close