Practical multi-candidate election system

ABSTRACT

The aim of electronic voting schemes is to provide a set of protocols that allow voters to cast ballots while a group of authorities collect the votes and output the final tally. In this paper we describe a practical multi-candidate election scheme that guarantees privacy of voters, public verifiability, and robustness against a coalition of malicious authorities. Furthermore, we address the problem of receipt-freeness and incoercibility of voters. Our new scheme is based on the Paillier cryptosystem and on some related zero-knowledge proof techniques. The voting schemes are very practical and can be efficiently implemented in a real system.

References

1. 1.J. Benaloh. Verifiable Secret-Ballot Elections. PhD thesis, Yale University, 1987.]]
2. 2.J. Benaloh and D. Tuinstra. Receipt-free secret-ballot elections. In Proc. 6th A CM Symposium on the Theory of Computing (STOC), pages 544-553. ACM, 1994.]]
3. 3.M. Burmester and Y. Desmedt. All Language in NP Have Divertible Zero-Knowledge Proofs and Arguments under Cryptographic Assumptions. In Eurecrypt '90, LNCS 473, pages 1-10. Springer-Verlag, 1991.]]
4. 4.R. Canetti, C. work, M. Naor, and R. Ostrovsky. Deniable Encryption. In Crypto '97, LNCS 1294, pages 90-104. Springer-Verlag, 1997.]]
5. 5.R. Canetti and R. Gennaro. Incoercible Multiparty Computation. In Proc. 37th IEEE Symposium on the Foundations of Computer Science (FOCS). IEEE, 1996.]]
6. 6.D. Chaum. Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms. Communications of the AGM, 24(2):84-88, February 1981.]]
7. 7.L. Chen. Witness Hiding Proofs and Applications. PhD thesis, Aarhns University, August 1994.]]
8. 8.L. Chen, I. B. Damgkrd, and T. P. Pedersen. Parallel Divertibility of Proofs of Knowledge. In Eurocrypt '9, LNCS 950, pages 140-155. Springer-Verlag, 1995.]]
9. 9.R. Cramer, Y. Frankel, B. Schoenmakers, and M. Yung. Multi-Authority Secret-Ballot Elections with Linear Work. In Eurocrlrpt '96, LNCS 1070, pages 72-83. Springer-Verlag, 1996.]]
10. 10.R. Cramer, tL Gennaro, and B. Schoenmakers. A Secure and Optimally Efficient Multi-Authority Election Scheme. In Eurecrypt '97, LNCS 1233, pages 113-118. Springer-Verlag, 1997.]]
11. 11.I. Damgkrd and M. Jurik. A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System. In PKC '01, LNCS 1992, pages 119-136. Springer-Verlag, 2001.]]
12. 12.I. Damgrd and M. Koprowski. Practical Threshold RSA Signatures Without a Trusted Dealer. In Eurocrypt '01, LNCS, pages -. Springer-Verlag, 2001.]]
13. 13.A. Fiat and A. Shamir. How to Prove Yourself: practical solutions of identification and signature problems. In Crypto '86, LNCS 263, pages 186-194. Springer-Verlag, 1987.]]
14. 14.P. Fouque and J. Stern. Fully Distributed Threshold RSA under Standard Assumptions. 2001. in Submission, available on the eprint server http://eprint, i a c r . org.]]
15. 15.P. A. Fouque, G. Poupard, and J. Stern. Sharing Decryption in the Context of Voting or Lotteries. In Financial Urypto '00, LNCS. Springer-Verlag, 2000.]]
16. 16.M. Giranlt and J. Stern. On the Length of Cryptographic Hash-Values used in Identification Schemes. In Urypto '9, LNCS 839, pages 202-215. Springer-Verlag, 1994.]]
17. 17.S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Oomptter and System Sciences, 28:270-299, 1984.]]
18. 18.L. C. Guiliou and J.-J. Quisquater. A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory. In Eurocrypt '88, LNCS 330, pages 123-128. Springer-Verlag, 1988.]]
19. 19.M. Hirt and K. Sako. Efficient Receipt-Free Voting Based on Homomorphic Encryption. In Eurocrypt '00, LNCS 1807. Springer-Verlag, 2000.]]
20. 20.T. Itoh, K. Sakural, and H. Shizuya. Any Language in IP Has a Divertible ZKIP. In Asiacrypt '91, LNCS 739, pages 382-397. Springer-Verlag, 1993.]]
21. 21.M. Jakobsson, K. Sako, and R. Impagliazzo. Designated Verifier Proofs and Their Applications. In Eurocrypt '96, LNCS 1070, pages 143-154. Springer-Verlag, Berlin, 1996.]]
22. 22.D. Ne and J. Stern. A New Cryptosystem based on Higher Residues. In Prec. of the 5th CCS, pages 59-66. ACM press, 1998.]]
23. 23.K. Ohta and T. Olmmoto. Divertible Zero-Knowledge Interactive Proofs and Commutative Random Serf-Reducibility. In Eurocrypt '89, LNCS 434, pages 134-149. Springer-Verlag, 1990.]]
24. 24.K. Ohta and T. Obamoto. On Concrete Security Treatment of Signatures Derived from Identification. In CrFpto '98, LNCS 1462, pages 354-369. Springer-Verlag, 1998.]]
25. 25.T. Okamoto. Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes. In Crypto '9, LNCS 740, pages 31-53. Springer-Verlag, 1992.]]
26. 26.T. Okamoto and S. Uchiyama. A New Public Key Cryptosystem as Secure as Factoring. In Eurocrypt '98, LNCS 1403, pages 308-318. Springer-Verlag, 1998.]]
27. 27.P. Paillier. Public-Key Cryptosystems Based on Discrete Logarithms Residues. In Eurocrlrpt '99, LNCS 1592. Springer-Verlag, 1999.]]
28. 28.D. Pointcheval. Self-Scrazabling Anonymizers. In Financial Grypto '00, LNCS. Springer-Verlag, 2000.]]
29. 29.D. Pointcheval and J. Stern. Provably Secure Blind Signature Schemes. In Asiacrlrpt '96, LNCS 1163, pages 252-265. Springer-Verlag, 1996.]]
30. 30.D. Pointcheval and J. Stern. Security Proofs for Signature Schemes. In Euroerypt '96, LNCS 1070, pages 387-398. Springer-Verlag, 1996.]]
31. 31.K. Sako and J. Kilian. Receipt-free mix-type voting scheme - A pratical solution to the implementation of a voting booth. In Eurocrypt '95, LNCS 921, pages 393-403. Springer-Verlag, 1995.]]
32. 32.C. P. Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3):161-174, 1991.]]
33. 33.B. Schoenmakers. Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic Voting. In Crypto '99, LNCS 1666, pages 148-164. Springer-Verlag, 1999.]]
34. 34.A. Shamir. How to Share a Secret. Communications of the ACM, 22:612-613, November 1979.]]
35. 35.V. Shoup. Practical Threshold Signatures. In Eurocrypt '00, LNCS 1807. Springer-Verlag, 2000.]]

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

  • Real-time systems

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques

      • Public key encryption

• Theory of computation

  • Computational complexity and cryptography

    • Interactive proof systems

    • Proof complexity

  • Logic

    • Proof theory