1
$\begingroup$

I have $n$ persons, each holding a secret integer $x_i$ ($i$ from $1$ to $n$) and I'm looking for a way for them to jointly compute the sum of these secrets without revealing to each other their individual secrets.

Verification of the sum isn't important in this problem, as an error will cause an abort at a later point. The important issue is that they not get information about the numbers held by the other parties.

My other question is can this still be done / does it require a different solution if the addition is over a finite field?

$\endgroup$
2
  • $\begingroup$ There's an ambiguity about "integer": has it an upper bound? a lower-bound? Without such bound, there is no solution: knowing only the size of the messages exchanged, we can find an upper bound and a lower bound to the integers chosen by the parties. The problem becomes tractable if we restrict to e.g. $[0,2^{128})$ which is often fine. $\endgroup$ – fgrieu Mar 22 at 18:17
  • $\begingroup$ Yes sorry the problem can be restricted to $[0, 2^{128}]$ $\endgroup$ – Daz Mar 23 at 10:43
2
$\begingroup$

I have $n$ persons, each holding a secret integer $x_i$ ($i$ from $1$ to $n$) and I'm looking for a way for them to jointly compute the sum of these secrets without revealing to each other their individual secrets.

A simple application of arithmetic secret-sharing based secure multi-party computation ("arithmetic GMW") can do that.

The protocol for that goes as follows:

  1. (One-Time Setup) Pick a prime $p$ that is guaranteed to be larger than the sum of all input values (you can safely overshoot the sume by a large margin here, e.g. pick a prime larger than $2^{96}$ for 64-bit inputs). This prime will be used to define the finite field we will work in. If you already have a preferred one, use it here. All arithmetic that follows will be carried out in this field.
  2. Have every party $P_i$ choose $n-1$ random integers uniformly at random from the finite field. Call them $s_{i,j}$ and let $s_{i,n}=x_i-\sum_{j=1}^{n-1}s_{i,j}$. This creates an arithmetic $n$-out-of-$n$ sharing of $x_i$
  3. Have every party $P_i$ send $s_{i,j}$ to $P_{j}$.
  4. Have every party $P_i$ compute $r_i=\sum_{\ell=1}^{n}s_{\ell,i}$, that is, have them all sum up all the shares they receive.
  5. Have every party $P_i$ broadcast their result $r_i$ to all other parties (or only to the one needing to know the sum).
  6. Have every party with with all $r_j$ compute $\sigma=\sum_{j=1}^{n}r_j$. This value is the desired sum.
$\endgroup$
5
  • $\begingroup$ Thanks very much for your response. I don't quite get how $s_{i,n}$ is used. It doesn't seem like it's communicated to any other participant, so how is any information about $x_i$ conveyed? $\endgroup$ – Daz Mar 23 at 10:42
  • $\begingroup$ @Daz ahh, I see your issue. $s_{i,n}$ is just a normal $s_{i,j}$ with $j=n$ and I have used this notation to designate that the first $j=1,\ldots,n-1$ get chosen differently than $j=n$. During the protocol execution $s_{i,n}$ will then be sent to party $P_n$. $\endgroup$ – SEJPM Mar 23 at 11:09
  • $\begingroup$ So you mean each $s_{i,j}$ depends on $s_{i,1},...s_{i,j-1}$? Then what is $s_{i,1}$? $\endgroup$ – Daz Mar 23 at 11:42
  • $\begingroup$ @Daz Only the very last $s_{i,j}$ depends on the previous ones. All excpet the last are randomly, independently chosen from the finite field. That is all parties except $P_n$ will only get the random values but you need all of those random values to get a meaningful value out of $P_n$'s share. $\endgroup$ – SEJPM Mar 23 at 12:46
  • $\begingroup$ Okay, got it now! Thanks for your help! $\endgroup$ – Daz Mar 23 at 13:33
0
$\begingroup$

A very different answer might also be helpful (depending on your application):

The idea is to use distributed homomorphic encryption, like distributed El Gamal encryption. Say we are working in a group with generator $g$. Each of your persons $i$ chooses a secret key $y_i$ and shares the public key $Y_i=g^{y_i}$ with the other participants. They each compute the global public key $Y$ as the product of all the $Y_i$.

The idea now is that everyone will encrypt their $x_i$ with $Y$, and combine the ciphertexts to form the ciphertext corresponding to the combination of the $x_i$. Then they collaboratively decrypt that combination. However, doing it like this would produce the product of the $x_i$, whereas you want the sum, so we have to proceed slightly differently.

Each participant $i$ encrypts $g^{x_i}$ with $Y$ and shares it with everyone. Everyone then multiplies these ciphertexts together, producing a ciphertext whose plain text is $\prod_i g^{x_i}$, or equivalently, $g^{\sum x_i}$. Now they each use their secret keys $y_i$ to partially decrypt this combination. Each particpant can combine the partial decryptions to obtain the plaintext $g^{\sum x_i}$.

To extract ${\sum x_i}$ from this, we have to use brute-force search. I assume the values $x_i$ are not too large and therefore ${\sum x_i}$ is not too large, and can be efficiently found by trying all the values. This would work fine if ${\sum x_i}$ is less than, say, $2^{30}$.

$\endgroup$
1
  • $\begingroup$ If one wants to use homomorphic encryption for this (I see no reason when additive secret sharing suffices, but still), this problem is known as the "Multi-Key" variant of homomorphic encryption. See for example this paper, on multi-key FHE. I am not familiar with the particular paper, but I imagine decryption is much more efficient than brute forcing a discrete logarithm. $\endgroup$ – Mark Mar 24 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.