1
$\begingroup$

Suppose there is a large number of participants each with a secret value. The secret values are very large (e.g. 256-bit integers). Each participant has published a public commitment to their secret value.

Is it possible for them to determine what their values sum up to in a single round of communication but without revealing their private values?

This can also be thought of as a voting scheme: each participant holds a value with which they can vote. Knowing public commitments for the votes that have been cast, we'd like to figure out the total number of votes that was cast without the need for voters to collaborate with each other (beyond casting of the original vote).

$\endgroup$
  • $\begingroup$ You need more of a statement of the intended security of the system. Is it required to keep each individual's vote private? Are voters allowed to abstain? Can each voter compute the sum independently, or do we want a trusted third party for that? Must each voter be able to verify that his/her vote is reflected in the final sum? $\endgroup$ – Russ Sep 28 '18 at 11:49
1
$\begingroup$

If all the participants have a random secret key which sums to 0. They can each post the sum of their key with their number. Anyone can then some the values posted, the key will cancel out and we what will remain is the sum.

This only works if everybody posts their value and we have an appropriate key distributed.

$\endgroup$
  • $\begingroup$ What about abstinence votes (deliberate choice to not vote)? Can you figure out who didn't vote, and doesn't that break privacy? $\endgroup$ – Russ Sep 28 '18 at 11:46
  • $\begingroup$ If even one person doesn't vote We dob't learn their part of the secret key, and nothing is revealed(including the sum we wish to calculate. A different system where anyone can not votr and everyone can calculate the sum from posted values necessarily does not keep votes private as we could sum a single value or many different aub groups. $\endgroup$ – Meir Maor Sep 28 '18 at 13:31
0
$\begingroup$

It seems that you are trusting everybody. Now use any semantically secure fully or just additive homeomorphic.

  1. Each party uses the public key of a master to encrypt their secret value.
  2. Send the encrypted values to a server with the public key.
  3. The server performs addition on the encrypt data.
  4. Now, the private key owner downloads the encrypted sum and decrypts to get the result.
$\endgroup$
0
$\begingroup$

First, there is a body of work on cryptographic voting, so I urge the asker to review that first before designing his/her own system. As an intellectual exercise, I designed the following simple tally system to meet what I perceive are the requirements.

  1. A trusted third-party manager creates a Paillier keypair S and P, creates a secret prime number $p_m$, and initializes a vote buffer $C_{prod}, C_{sum}$ where $C_{prod} = C_{sum} = E_P(p_m)$, with $E_P(x)$ denoting Paillier encryption by P. Each voter $v_i$ creates a secret prime number $p_i$, creates a randomized encryption $C_{p_i}$ - which is what Paillier does - and enrolls this with the manager. (The manager is trusted to keep each voter's commitment a secret, by not disclosing the mapping between $v_i$ and $C_{p_i}$.) To start the vote, the manager selects a voter at random and sends the buffer.
  2. Voter $i$ receives the buffer, and must decide whether to vote or to abstain. If voting, she updates $C_{prod} = C_{prod}^{p_i}$, and $C_{sum} = C_{sum}\cdot E_P(p_i)$. If abstaining, she rerandomizes each of $C_{prod}, C_{sum}$ by multiplying by $E_P(0)$. Paillier is additive, so exponentiation creates a product of primes, and multiplication creates a sum of primes. She passes the buffer along to another voter. The last voter sends it back to the manager.
  3. The manager reveals S, thereby revealing $prod$ and $sum$ to everyone. Each voter decrypts $C_{prod}$, and verifies that her vote is included in the tally by checking that her own secret number $p_i$ divides $prod$. Each voter verifies the tally by first determining which primes are included in $prod$ (divisibility), then ensuring the tally consists of the sum of those primes.

This ensures no removal of votes, no overvoting, but trusts the manager with the voter privacy. There may also be problems with false challenges and with vote stuffing - how can every voter know that posted commitments come from unique, registered voters?

$\endgroup$

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.