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

Véronique Cortier 1 David Galindo 1 Stephane Glondu 1, 2 Malika Izabachène 1
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies, Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
2 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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.
Type de document :
Autre publication
Report 2013/177. Cryptology ePrint Archive, Report 2013/177. 2013
Liste complète des métadonnées

Contributeur : Véronique Cortier <>
Soumis le : jeudi 7 novembre 2013 - 14:25:18
Dernière modification le : jeudi 22 septembre 2016 - 14:31:08


  • HAL Id : hal-00881079, version 1


Véronique Cortier, David Galindo, Stephane Glondu, Malika Izabachène. A generic construction for voting correctness at minimum cost - Application to Helios. Report 2013/177. Cryptology ePrint Archive, Report 2013/177. 2013. <hal-00881079>



Consultations de la notice