Information Security and Cryptography Research Group

Efficient Receipt-Free Voting Based on Homomorphic Encryption

Martin Hirt and Kazue Sako

Advances in Cryptology — EUROCRYPT 2000, Lecture Notes in Computer Science, Springer-Verlag, vol. 1807, pp. 539–556, May 2000.

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 $\ell$ (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 $\ell$.

Key words. Receipt-free voting, Uncoercibility, Designated-verifier proofs.

BibTeX Citation

    author       = {Martin Hirt and Kazue Sako},
    title        = {Efficient Receipt-Free Voting Based on Homomorphic Encryption},
    editor       = {Bart Preneel},
    booktitle    = {Advances in Cryptology --- EUROCRYPT 2000},
    pages        = 539--556,
    series       = {Lecture Notes in Computer Science},
    volume       = 1807,
    year         = 2000,
    month        = 5,
    publisher    = {Springer-Verlag},

Files and Links