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

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.

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

[table of contents]

Secret Sharing

A Protocol for Secure Addition

Share this:

Synes godt om dette: