0
$\begingroup$

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!

$\endgroup$
6
  • 2
    $\begingroup$ Paillier encryption solves a different, easier problem: $n$ people each encrypt their secret number using a public key given by a trusted party, the cryptograms are combined publicly, and then the trusted party deciphers the combination to get and publish the sum. However the trusted third party could decipher the individual numbers. If there is a practical solution for the harder problem in the question, I want to know it! $\endgroup$
    – fgrieu
    Jun 5, 2023 at 19:11
  • $\begingroup$ I wonder if this is similar to a trustless electronic voting problem, where each person can cast a vote 0/1 and it needs to be summed up without a trusted 3rd party? I found this article online ieeexplore.ieee.org/document/8887296 but I can't access it yet :( $\endgroup$ Jun 6, 2023 at 5:48
  • 2
    $\begingroup$ @fgrieu in your approach, the trusted dealer could also distribute shares of the Paillier decryption key, which allows for threshold decryption of the result by the parties. Justin Zhang: what is your collusion scenario? Do you want security against collusions of multiple parties? $\endgroup$ Jun 6, 2023 at 13:57
  • $\begingroup$ hi @GeoffroyCouteau I am trying to build a game with private information. If a player learns about any other player's secret then it defies the purpose of the game. Of course, if multiple players can collude and together decipher another player's secret, that's also bad. Wonder if that describe the collusion scenario? $\endgroup$ Jun 6, 2023 at 19:05
  • $\begingroup$ @GeoffroyCouteau thanks for suggesting that the trusted dealer can distribute the shares of the Paillier decryption key to the parties in fgrieu 's approach. I wonder if there is any fast algorithm to generate and distribute the Paillier decryption key shares? I found a few resources online, like this one eprint.iacr.org/2019/1136.pdf, but they are all very slow (more than 1 minute to set it up for 3 parties.) If the keys can be generated fast, then it seems to be a very good solution. I am not very familiar in this field, wonder if there could be any potential downside here? $\endgroup$ Jun 6, 2023 at 19:24

2 Answers 2

3
$\begingroup$

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)
$\endgroup$
2
  • $\begingroup$ hi @richard-thiessen, thanks for your detailed answer! I understand the first two sections but I am still confused about "Proving misbehavior to discourage DOS attacks". I am trying to understand what kind of attack it prevents. If someone submitted a bad x or u share, then C_tot = Gx+Hu won't hold and the algorithm correctly rejects the result. Is the goal of the 3rd section to detect exactly who submitted a bad share? From the Schnorr algorithms you mentioned, I'm not sure how it can detect who submitted bad shares. Thanks! $\endgroup$ Jun 6, 2023 at 22:35
  • 1
    $\begingroup$ Yes, it's to detect which person submitted the bad share result after shuffling. There's three possible error cases: (1)the public matrix column sum doesn't match the input Pedersen commitment (the Schnorr proof requires they do) (2) the row sum output scalar wasn't calculated correctly (anyone can check this against that row in the public matrix) (3) the public and private matrices don't match (whoever was sent that row can report this mismatch by revealing the share sent to them). $\endgroup$ Jun 7, 2023 at 10:46
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ hi @GeoffroyCouteau, thanks for the answer. I wonder if it is the same approach as the one in Richard Thiessen's reply? Wonder if one can use zero-knowledge proofs to make this also work with malicious adversaries? Also I forgot an important constraint in my original question that the final sum should not be made public, instead I hope to compare two such sums. (a modified question posted here tinyurl.com/newquestionx) I searched around and found "distributed garbled circuit" promising (dl.acm.org/doi/pdf/10.1145/100216.100287). Do you think I'm on the right track? Thx!! $\endgroup$ Jun 9, 2023 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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