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: Josh Daniel Cohen Benaloh, Verifiable secret-ballot elections, 1987
• 2: Josh Benaloh , Dwight Tuinstra, Receipt-free secret-ballot elections (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.544-553, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195407]
• 3: Mike V. D. Burmester , Yvo Desmedt, All languages in NP have divertible zero-knowledge proofs and arguments under cryptographic assumptions (extended abstract), Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.1-10, February 1991, Aarhus, Denmark
• 4: Ran Canetti , Cynthia Dwork , Moni Naor , Rafail Ostrovsky, Deniable Encryption, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.90-104, August 17-21, 1997
• 5: R. Canetti , R. Gennaro, Incoercible multiparty computation, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.504, October 14-16, 1996
• 6: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 7: L. Chen. Witness Hiding Proofs and Applications. PhD thesis, Aarhns University, August 1994.
• 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: 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: 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: Ivan Damgård , Mats Jurik, A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.119-136, February 13-15, 2001
• 12: Ivan Damgård , Maciej Koprowski, Practical Threshold RSA Signatures without a Trusted Dealer, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.152-165, May 06-10, 2001
• 13: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 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: Pierre-Alain Fouque , Guillaume Poupard , Jacques Stern, Sharing Decryption in the Context of Voting or Lotteries, Proceedings of the 4th International Conference on Financial Cryptography, p.90-104, February 20-24, 2000
• 16: Marc Girault , Jacques Stern, On the Length of Cryptographic Hash-Values Used in Identification Schemes, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.202-215, August 21-25, 1994
• 17: S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Oomptter and System Sciences, 28:270-299, 1984.
• 18: L. C. Guillou , J.-J. Quisquater, A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory, Lecture Notes in Computer Science on Advances in Cryptology-EUROCRYPT'88, p.123-128, April 1988, Davos, Switzerland
• 19: M. Hirt and K. Sako. Efficient Receipt-Free Voting Based on Homomorphic Encryption. In Eurocrypt '00, LNCS 1807. Springer-Verlag, 2000.
• 20: Toshiya Itoh , Kouichi Sakurai , Hiroki Shizuya, Any Language in IP Has a Divertable ZKIP, Proceedings of the International Conference on the Theory and Applications of Cryptology: Advances in Cryptology, p.382-396, November 11-14, 1991
• 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: David Naccache , Jacques Stern, A new public key cryptosystem based on higher residues, Proceedings of the 5th ACM conference on Computer and communications security, p.59-66, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288106]
• 23: Tatsuaki Okamoto , Kazuo Ohta, Divertible zero knowledge interactive proofs and commutative random self-reducibility, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.134-149, November 1990, Houthalen, Belgium
• 24: Kazuo Ohta , Tatsuaki Okamoto, On Concrete Security Treatment of Signatures Derived from Identification, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.354-369, August 23-27, 1998
• 25: Tatsuaki Okamoto, Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.31-53, August 16-20, 1992
• 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: P. Paillier. Public-Key Cryptosystems Based on Discrete Logarithms Residues. In Eurocrlrpt '99, LNCS 1592. Springer-Verlag, 1999.
• 28: David Pointcheval, Self-Scrambling Anonymizers, Proceedings of the 4th International Conference on Financial Cryptography, p.259-275, February 20-24, 2000
• 29: David Pointcheval , Jacques Stern, Provably Secure Blind Signature Schemes, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.252-265, November 03-07, 1996
• 30: D. Pointcheval and J. Stern. Security Proofs for Signature Schemes. In Euroerypt '96, LNCS 1070, pages 387-398. Springer-Verlag, 1996.
• 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: C. P. Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3):161-174, 1991.
• 33: Berry Schoenmakers, A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.148-164, August 15-19, 1999
• 34: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 35: V. Shoup. Practical Threshold Signatures. In Eurocrypt '00, LNCS 1807. Springer-Verlag, 2000.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures

General Terms:
Design, Experimentation, Security