Verifiable tally-hiding E-voting with fully homomorphic encryption

Abstract

An E-voting system is end-to-end verifiable if arbitrary external parties can check whether the result of the election is correct or not. It is tally-hiding if it does not disclose the full election result but rather only the relevant information, such as e.g. the winner of the election. In this thesis we pursue the goal of constructing an end-to-end verifiable tally-hiding E-voting system using fully homomorphic encryption. First we construct an alteration of the GSW levelled fully homomorphic encryption scheme based on the learning with errors over rings assumption. We utilize a key homomorphic property of this scheme in order to augment the scheme by a distributed key generation and distributed decryption. This leads to a passively secure 4-round multi-party computation protocol in the common random string model that can evaluate arithmetic circuits of arbitrary size. The complexity of this protocol is quasi-linear in the number of parties, polynomial in the security parameter and polynomial in the size of the circuit. By using Fiat-Shamir-transformed discrete-log-based zero-knowledge proofs we achieve security against active adversaries in the random oracle model while preserving the number of 4 rounds. Based on this actively secure protocol we construct an end-to-end verifiable tally-hiding E-voting system that has quasi-linear time complexity in the number of voters.