Split-ballot voting: everlasting privacy with distributed trust

ABSTRACT

In this paper we propose a new voting protocol with desirable security properties. The voting stage of the protocol can be performed by humans without computers; it provides every voter with the means to verify that all the votes were counted correctly (universal verifiability) while preserving ballot secrecy. The protocol has "everlasting privacy": even a computationally unbounded adversary gains no information about specific votes from observing the protocol's output. Unlike previous protocols with these properties, this protocol distributes trust between two authorities: a single corrupt authority will not cause voter privacy to be breached. Finally, the protocol is receipt-free: a voter cannot prove how she voted even she wants to do so. We formally prove the security of the protocol in the Universal Composability framework, based on number-theoretic assumptions.

REFERENCES

• 1: Ben Adida , Ronald L. Rivest, Scratch & vote: self-contained paper-based cryptographic voting, Proceedings of the 5th ACM workshop on Privacy in electronic society, October 30-30, 2006, Alexandria, Virginia, USA [doi>10.1145/1179601.1179607]
• 2: Y. Aumann, Y. Z. Ding, and M. O. Rabin. Everlasting security in the bounded storage model. IEEE Trans. on Information Theory, 48(6):1668--1680, 2002.
• 3: 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]
• 4: J. W. Bryans and P. Y. A. Ryan. A simplified version of the Chaum voting scheme. Technical Report CS-TR 843, University of Newcastle, 2004.
• 5: R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. Cryptology ePrint Archive, Report 2000/067, 2000.
• 6: R. Canetti , R. Gennaro, Incoercible multiparty computation, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.504, October 14-16, 1996
• 7: 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]
• 8: D. Chaum. E-voting: Secret-ballot receipts: True voter-verifiable elections. IEEE Security & Privacy, 2(1):38--47, Jan./Feb. 2004.
• 9: D. Chaum, 2006. http://punchscan.org/.
• 10: J. D. Cohen (Benaloh) and M. J. Fischer. A robust and verifiable cryptographically secure election scheme. In FOCS '85, pages 372--382.
• 11: R. Cramer, M. Franklin, B. Schoenmakers, and M. Yung. Multi-authority secret-ballot elections with linear work. In Eurocrypt '96, pages 72--83.
• 12: R. Cramer, R. Gennaro, and B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. In Eurocrypt '97, pages 103--118.
• 13: Atsushi Fujioka , Tatsuaki Okamoto , Kazuo Ohta, A Practical Secret Voting Scheme for Large Scale Elections, Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.244-251, December 13-16, 1992
• 14: M. Hirt and K. Sako. Efficient receipt-free voting based on homomorphic encryption. In Eurocrypt '00, pages 539+.
• 15: T. Moran and M. Naor. Basing cryptographic protocols on tamper-evident seals. In ICALP '05, pages 285--297.
• 16: T. Moran and M. Naor. Receipt-free universally-verifiable voting with everlasting privacy. In CRYPTO, pages 373--392, 2006. http://www.wisdom.weizmann.ac.il/~talm/papers/MN06-voting.pdf.
• 17: M. Naor and A. Shamir. Visual cryptography. In Eurocrypt '94, volume 950 of LNCS, pages 1--12, 1995.
• 18: C. A. Neff. Practical high certainty intent verification for encrypted votes, October 2004. http://www.votehere.net/vhti/documentation/vsv-2.0.3638.pdf.
• 19: S. Popoveniuc and B. Hosp. An introduction to punchscan, 2006. http://punchscan.org/papers/popoveniuc_hosp_punchscan_introduction.pdf.
• 20: M. O. Rabin. Transaction protection by beacons. J.Computer and System Sciences, 27(2):256--267, 1983.
• 21: D. J. Reynolds. A method for electronic voting with coercion-free receipt. Presentation: http://www.win.tue.nl/~berry/fee2005/presentations/reynolds.ppt.
• 22: Peter Y. A. Ryan, A variant of the Chaum voter-verifiable scheme, Proceedings of the 2005 workshop on Issues in the theory of security, p.81-88, January 10-11, 2005, Long Beach, California [doi>10.1145/1045405.1045414]
• 23: A. Shamir. Cryptographers panel, RSA conference, 2006. Webcast: http://media.omediaweb.com/rsa2006/1_5/1_5_High.asx.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

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

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

General Terms:
Human Factors, Security, Theory