ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Efficient Receipt-Free Voting Based on Homomorphic Encryption

Martin Hirt and Kazue Sako

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$.

\smallskip\noindent{\bf Key words.} Receipt-free voting, Uncoercibility, Designated-verifier proofs.