Abstract
Voting schemes that provide receipt-freeness prevent voters from proving their cast vote, and hence thwart vote-buying and coercion. We analyze the security of the multi-authority voting protocol of Benaloh and Tuinstra and demonstrate that this protocol is not receipt-free, opposed to what was claimed in the paper and was believed before. Furthermore, we propose the first practicable receipt-free voting scheme. Its only physical assumption is the existence of secret one-way communication channels from the authorities to the voters, and due to the public verifiability of the tally, voters only join a single stage of the protocol, realizing the “vote-and-go” concept. The protocol combines the advantages of the receipt-free protocol of Sako and Kilian and of the very efficient protocol of Cramer, Gennaro, and Schoenmakers, with help of designated-verifier proofs of Jakobsson, Sako, and Impagliazzo. Compared to the receipt-free protocol of Sako and Kilian for security parameter ℓ (the number of repetitions in the non-interactive cut-and-choose proofs), the protocol described in this paper realizes an improvement of the total bit complexity by a factor ℓ.
Supported by the Swiss National Science Foundation, project no. SPP 5003-045293.
Chapter PDF
Similar content being viewed by others
References
Masayuki Abe. Mix-networks on permutation networks In Advances in Cryptology — ASIACRYPT’ 99, vol. 1716 of LNCS, pp. 258–273. Springer-Verlag, 1999.
Josh Cohen Benaloh: Verifiable Secret-Ballot Elections. Yale University PhD thesis, YALEU/DCS/TR-561, 1987.
Josh Cohen Benaloh and Dwight Tuinstra. Receipt-free secret-ballot elections (extended abstract). In Proc. 26th ACM Symposium on the Theory of Computing (STOC), pp. 544–553. ACM, 1994.
Ran Canetti, Cynthia Dwork, Moni Naor, and Rafail Ostrovsky. Deniable encryption. In Advances in Cryptology — CRYPTO’ 97, vol. 1294 of LNCS, pp. 90–104. Springer-Verlag, 1997.
Ran Canetti and Rosario Gennaro. Incoercible multiparty computation. In Proc. 37th IEEE Symposium on the Foundations of Computer Science (FOCS), 1996.
David Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM, 24(2):84–88, 1981.
Ronald Cramer, Ivan Damgård, and Berry Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Advances in Cryptology — CRYPTO’ 94, vol. 839 of LNCS. Springer-Verlag, 1994.
Josh D. Cohen (Benaloh) and Michael J. Fischer. A robust and verifiable cryptographically secure election scheme. In Proc. 26th IEEE Symposium on the Foundations of Computer Science (FOCS), pp. 372–382. IEEE, 1985.
Josh Cohen (Benaloh) and Moti Yung: Distributing the Power of a Government to Enhance the Privacy of Voters. In Proc. 5th ACM Symposium on Principles of Distributed Computing (PODC), pp. 52–62. ACM, 1986.
Ronald Cramer, Matthew K. Franklin, Berry Schoenmakers, and Moti Yung. Multi-authority secret-ballot elections with linear work. In Advances in Cryptology — EUROCRYPT’ 96, vol. 1070 of LNCS, pp. 72–83. Springer-Verlag, May 1996.
Ronald Cramer, Rosario Gennaro, and Berry Schoenmakers. A secure and optimally efficient multi-authority election scheme. European Transactions on Telecommunications, 8:481–489, 1997. Preliminary version in Advances in Cryptology — EUROCRYPT’ 97.
Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In Advances in Cryptology — CRYPTO’ 84, vol. 196 of LNCS, pp. 10–18. Springer-Verlag, 1984.
Paul Feldman. A practical scheme for non-interactive verifiable secret sharing. In Proc. 28th IEEE Symposium on the Foundations of Computer Science (FOCS), pp. 427–437, 1987.
Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology — CRYPTO’ 86, vol. 263 of LNCS, pp. 186–194. Springer-Verlag, 1986.
Atsushi Fujioka, Tatsuaki Okamoto, and Kazuo Ohta. A practical secret voting scheme for large scale elections. In Advances in Cryptology — AUSCRYPT’ 92, pp. 244–251, 1992.
Markus Jakobsson, Kazue Sako, and Russell Impagliazzo. Designated-verifier proofs and their applications. In Advances in Cryptology — EU-ROCRYPT’ 96, vol. 1070 of LNCS, pp. 143–154. Springer-Verlag, 1996.
Markus Jakobsson. A Practical Mix. In Advances in Cryptology — EU-ROCRYPT’ 98, vol. 1403 of LNCS, pp. 448–461, Springer-Verlag, 1998.
Markus Michels and Patrick Horster. Some remarks on a receipt-free and universally verifiable mix-type voting scheme. In Advances in Cryptology — ASIACRYPT’ 96, vol. 1163 of LNCS, pp. 125–132. Springer-Verlag, 1996.
Tatsuaki Okamoto. Receipt-free electronic voting schemes for large scale elections. In Proc. of Workshop on Security Protocols’ 97, vol. 1361 of LNCS, pp. 25–35. Springer-Verlag, 1997.
Wakaha Ogata, Kaoru Kurosawa, Kazue Sako and Kazunori Takatani Fault Tolerant Anonymous Channel In Information and Communications Security ICICS’ 97, vol. 1334 of LNCS, pp. 440–444. Springer-Verlag, 1997.
Choonsik Park, Kazutomo Itoh, and Kaoru Kurosawa. Efficient anonymous channel and all/nothing election scheme. In Advances in Cryptology — EUROCRYPT’ 93, vol. 765 of LNCS, pp. 248–259. Springer-Verlag, 1993.
Torben P. Pedersen. A threshold cryptosystem without a trusted party (extended abstract). In Advances in Cryptology — EUROCRYPT’ 91, vol. 547 of LNCS, pp. 522–526. Springer-Verlag, 1991.
Kazue Sako. Electronic voting schemes allowing open objection to the tally. In Transactions of IEICE, vol. E77-A No.1, Jan. 1994.
Kazue Sako and Joe Kilian. Secure voting using partially compatible homomorphisms. In Advances in Cryptology — CRYPTO’ 94, vol. 839 of LNCS, pp. 411–424. Springer-Verlag, 1994.
Kazue Sako and Joe Kilian. Receipt-free mix-type voting scheme — A practical solution to the implementation of a voting booth. In Advances in Cryptology — EUROCRYPT’ 95, vol. 921 of LNCS, pp. 393–403. Springer-Verlag, 1995.
Adi Shamir. How to share a secret. Communications of the ACM, 22:612–613, 1979.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hirt, M., Sako, K. (2000). Efficient Receipt-Free Voting Based on Homomorphic Encryption. In: Preneel, B. (eds) Advances in Cryptology — EUROCRYPT 2000. EUROCRYPT 2000. Lecture Notes in Computer Science, vol 1807. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45539-6_38
Download citation
DOI: https://doi.org/10.1007/3-540-45539-6_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67517-4
Online ISBN: 978-3-540-45539-4
eBook Packages: Springer Book Archive
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.