Securely computing the addition of n numbers owned by n people

Question

Assume that we have n people each owning a secret number. Now we want to collaboratively compute the addition of all these numbers without anyone revealing their numbers. Then the result will be made public to all. Wonder what algorithm shall I use?

(I have looked into multi-party computation, specifically secret sharing. But that, according to my basic understanding, is for a trusted dealer to divide a secret into many shares and distribute them, such that multiple parties can collaboratively use the secret without any of them knowing the whole secret. It solves a different problem than the one I need to solve.

I also looked into homomorphic encryption. But I'm not sure how different people can each encrypt their numbers using different keys and collaboratively compute and decrypt.)

Thanks!

Answer 1

If you're okay with n^2 communication costs here's a protocol based on Pedersen commitments. Range proofs to enforce bounds on the initial commited numbers via Bulletproofs are quite small (this could prevent participants from using "negative" numbers for example).

The basic protocol works as follows. Each participant (i=0...n)

• starts with their number x[i] and picks a blinding factor u[i]
• computes a Pedersen commitment of their value C[i]=G*x[i]+H*u[i] and publishes it

Anyone can now compute C_tot=sum(C[i],i=0...n)

To check the resulting commitment we need to compute the final value x=sum(x[i],i=0...n) and u=sum(u[i],i=0...n) then check that C_tot=G*x+H*u. An alternative to publishing u is to compute the point H*u in the commitment equation directly along with a proof of knowledge of u or u shares adding up to u.

Split into n*n shares, shuffle and reassemble

Have everyone split their u[i] and x[i] into a bunch of shares (u[i]=sum(u_share[i][j],j=0...n)),(x[i]=sum(x_share[i][j],j=0...n)).

This creates an n*n matrix of u_share[i][j] and x_share[i][j] values. Each participant generates a column u_share[participant][0...n] and then gathers a row u_share[0...n][participant]. This is the n^2 communication part since each participant has to send n-1 messages. Crucially this makes the protocol maximally robust. Participant values are only revealed if all other peers are dishonestly collaborating.

Each participant then computes and publishes

• u_shuffled[i]=sum(u_share[i][j],i=0...n))
• x_shuffled[i]=sum(u_share[i][j],i=0...n))

These can be summed to find the final u and x values by some chosen node that then broadcasts the results. Anyone can now verify the commitment opening C_tot=G*x+H*u.

Proving misbehavior to discourage DOS attacks

If a participant chooses to publish a bad u_shuffled[i] or x_shuffled[i] value, the protocol fails. One simple solution is to have a public n*n matrix of G*u_share[i][j] and H*x_share[i][j] points. Notice that I swapped around the generators H and G since H*u_share[i][j] column sums can un-blind the original pedersen commitments. Everyone commits to their column and if there's an issue, the matrix can be reassembled. The row sums can checked against each party's published row sum and column sums against the Pedersen commitments without having to reveal any of the scalar share values.

Row sums can be checked easily since those are scalar values. Column sums have to be checked against the original Pedersen commitments but without un-blinding them which is more challenging.

So let's assume we have(note:I've omitted the [i]'s):

• C=G*x+H*u
• Col_sum=G*u

We want to prove that the same u was used for both. There's a simple Schnorr-signature-like proof of this:

• set up two Schnorr like equations:
  • R1= C*e+S*H+T*G
  • R2=Col_sum*e+S*G
  • e=Hash(R1,R2,C,Col_sum)
• To generate the proof:
  • pick two secret scalars k and j
  • R1=H*k+G*j
  • R2=G*k
  • e=Hash(R1,R2,C,Col_sum)
  • S=k-u*e
  • T=j-x*e
  • output (e,S,T)
• To verify check the equations hold:
  • R1= C*e+S*H+T*G
  • R2=Col_sum*e+S*G
  • check that e = Hash(R1,R2,C,Col_sum)

Swapping around the generators and the x and u values yields a similar proof the x value in the Pedersen commitment matches the appropriate column sum:

• R1= C*e+S*G+T*H
• R2=Col_sum*e+S*H
• e=Hash(R1,R2,C,Col_sum)

Answer 2

How about the following straightforward solution? I'm assuming that each party $P_i$ holds an input $x_i$ belonging to some abelian group $\mathbb{G}$, and that the parties are connected through private channels (which can be implemented with key exchange and symmetric encryption).

• Each party $P_i$ secretly shares their input $x_i$ into $n$ random parts $(x_i^1, \cdots, x_i^n)$ (i.e., the $x_i^j$ are random elements of $\mathbb{G}$ that sum to $x_i$), and sends each $x_i^j$ to $P_j$.
• Each party $P_i$ sums all the shares it received: $y^i \gets \sum_{j=1}^n x_j^i$.
• All parties broadcast the $y^i$'s to everyone. The output is reconstructed as $\sum_{i=1}^n y^i = \sum_{i=1}^n x_i$.

It's not too hard to show that this is an information-theoretically secure protocol (in the model of secure computation with authenticated private channels) in the honest-but-curious model (where parties follow the protocol) for up to $n-1$ corruptions (i.e. even if everyone colludes against you - though in this particular case there's nothing left to hide of course).