Paper 2013/177

A generic construction for voting correctness at minimum cost - Application to Helios

Veronique Cortier, David Galindo, Stephane Glondu, and Malika Izabachene

Abstract

Most voting schemes aim at providing verifiability: voters should be able to check that their ballots did contribute to the outcome (individual verifiability) and that the tallying authorities did their job properly (universal verifiability). Surprisingly, verifiability still does not answer a very simple and natural question: how can I be sure that the published result corresponds to the (sum of) intended votes of the voters? This property is called correctness by Juels, Catalano, and Jakobsson. Actually, even a prominent voting system like Helios does not achieve correctness in the case of a dishonest bulletin board, since it may add ballots. We generalize the aforementioned definition of correctness to account for a malicious bulletin board (full correctness) and we provide a generic construction that transforms a correct voting scheme into a fully correct voting scheme. This construction simply requires to send credentials to the voters, with no additional infrastructure. We further provide a simple and natural criteria that implies voting correctness, which can then be turned into full correctness due to our construction. As an application, we build a variant of Helios that is both fully correct, verifiable and private. Real-world elections often require threshold cryptosystems so that any t out of l trustees can proceed to tallying. We describe a fully distributed (with no dealer) threshold cryptosystem suitable for Helios (in particular, suitable to partial decryption). In doing so we happen to revisit the seminal multi-authority election system from Cramer, Gennaro and Schoenmakers. Altogether, we provide the first proof of privacy, verifiability and correctness for a fully distributed Helios voting scheme (and its enhanced version with credentials), together with its detailed description. This also implies, to our knowledge, the first formal proofs of privacy, verifiability and correctness for the scheme by Cramer et al. Last but not least, we provide an open source implementation of our variant of Helios.