Paper 2020/513

E-cclesia: Universally Composable Self-Tallying Elections

Abstract

The technological advancements of the digital era paved the way for the facilitation of electronic voting (e-voting) in the promise of efficiency and enhanced security. In standard e-voting designs, the tally process is assigned to a committee of designated entities called talliers. Naturally, the security analysis of any e-voting system with tallier designation hinges on the assumption that a subset of the talliers follows the execution guidelines and does not attempt to breach privacy. As an alternative approach, Kiayias and Yung [PKC ’02] pioneered the self-tallying elections (STE) paradigm, where the post-ballot-casting (tally) phase can be performed by any interested party, removing the need for tallier designation. In this work, we explore the prospect of decentralized e-voting where security is preserved under concurrent protocol executions. In particular, we provide the first comprehensive formalization of STE in the universal composability (UC) framework introduced by Canetti [FOCS ’01] via an ideal functionality that captures required security properties such as voter privacy, eligibility, fairness, one-voter one-vote, and verifiability. We provide a concrete instantiation, called E-cclesia , that UC realizes our functionality. The design of E-cclesia integrates several cryptographic primitives such as signatures of knowledge for anonymous eligibility check, dynamic accumulators for scalability, time-lock encryption for fairness and anonymous broadcast channels for voter privacy. For the latter primitive, we provide the first UC formalization along with a construction based on mix-nets that utilises layered encryption, threshold secret sharing and equivocation techniques. Finally, we discuss deployment and scalability considerations for E-cclesia . We present preliminary benchmarks of the key operations (in terms of computational cost) of the voting client and demonstrate the feasibility of our proposal with readily available cryptographic tools for mid-sized elections (∼100,000 voters).