0
$\begingroup$

Suppose there are three voters $P$, $Q$ and $R$, and each will vote only on one candidate out of $X$, $Y$ or $Z$, with a 6 bit vote vector corresponding to $X $, $Y$ and $Z$ respectively (with 2 bits each for a candidate. E.g., $( 01, 00, 00 )$ signifies a vote for $X$).

How can any voter find out the total number of votes cast for each candidate without disclosing their preferences by the use of secure multiparty computation?

Each 6 bit vote vector is encrypted and sent to the some third party who will then take the product of ciphertext votes and then decrypt the product to yield a bit vector which shows the total number of preferences received by each candidate (Paillier cryptosystem).

What homomorphic property must be held by the cryptosystem in the plaintext and in the ciphertext space to satisfy the objective?

Finally, I need some theoretical explanation finding secure sum using SMP (with and without random seed) and SMC to sort the numbers.

$\endgroup$
2
$\begingroup$

In general, there are many techniques for secure multiparty computation. However, the problem of voting is much broader than this, and if you are really interested I suggest looking into the voting literature in depth.

One of the big questions is the model: typically, you cannot run a regular MPC protocol since that requires interaction among all the parties. One solution (which is an old work, but one that I really like), separates between an election service provider and the actual election being held. Actually the work talks about auctions, but a similar idea can be used. See Privacy Preserving Auctions and Mechanism Design.

For more modern work on elections, see Helios (which is the scheme used by the IACR). I suggest looking at Wikipedia - end-to-end verifiable voting for some sources, but note that a lot of research is needed. In general, secure tallying is a tiny part of what is needed for a real election (and the easiest to solve).

$\endgroup$
  • $\begingroup$ Thank you references , really i need to learn SMC protocol (eg: sum ,multiplication ) , more deeply. i will follow ur references. $\endgroup$ – uma Oct 8 '18 at 9:41
0
$\begingroup$

How any voter can find out the total number of votes cast for each candidate without disclosing their preferences by the use of secure multiparty computation.?

The answer comes with the semantically secure Additive Homomorphic schemes; that allow addition on encrypted data, Assuming the tally honest.

  • The tally generates the $pub$ and $prv$ keys.
  • The tally publishes $pub$
  • each voter votes $< 01, 00, 00 >$
  • by using the $pub$ voters encrypt their votes. $< 0xfa, 0x14, 0xe3 >$. no on except the tally can extract information from the vote as long as the underlying scheme is secure.
  • cast the ballot.
  • the tally performs addition on the encrypted data.
  • When the voting finished, tally decrypts the results and publishes.

Each 6 bit vote vector is encrypted and sent to some third party who will then take the product of ciphertext votes and then decrypt the product to yield a bit vector which shows the total number of preferences received by each candidate (Paillier cryptosystem). What homomorphic property must be held by the cryptosystem in the plaintext and in the ciphertext space to satisfy the objective?

  • Must perform addition on encrypted data
  • Must be semantically secure.
  • To prevent the overflow, the number of possible votes must be taken into account to prevent the overflow.

Of course, the answer is not that simple;

  • If tally is not counting who voted or not, then there is a multiple vote cast.
  • An attacker to the system can change any casted vote by using the public key. So, integrity into the system must be applied.
$\endgroup$
  • $\begingroup$ 'the tally performs addition on the encrypted data.' that mean the calculation part done for encrypted data? $\endgroup$ – uma Oct 8 '18 at 8:54
  • 1
    $\begingroup$ This solution is completely insecure. If the "tally" receives the individual votes and then tallies them, then it can decrypt and learn all individual votes (since the key belongs to the tally). Thus, this is just a trusted third party, and each party can send their vote to the party (encrypted over TLS). $\endgroup$ – Yehuda Lindell Oct 8 '18 at 9:04
  • $\begingroup$ @YehudaLindell what if the voters add the votes the transfer to the tally? $\endgroup$ – kelalaka Oct 8 '18 at 9:08
  • $\begingroup$ You would need them all to communicate, and if there's a collusion between the tally and one/some of the voters then they can learn the votes of individual honest parties. So, this also isn't a good solution. $\endgroup$ – Yehuda Lindell Oct 8 '18 at 9:22
  • 1
    $\begingroup$ I want to give a simple but not perfect solution to the first part. The problem as you stated is required many parties to interact. thanks $\endgroup$ – kelalaka Oct 8 '18 at 10:09

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.