E-cclesia: Universally Composable Self-Tallying Elections over Anonymous Broadcast

The technological advancements of the digital era have paved the way for the facilitation of electronic voting (e-voting) with promises of increased 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 designated talliers 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 designated talliers. 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 present 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 checks, 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 novel construction based on mix-nets that utilizes layered encryption, threshold secret sharing, and equivocation techniques. Additionally, we provide the first UC formalization of dynamic accumulators without a trusted setup, along with a UC realization based on existing constructions. Finally, we discuss the deployment and scalability of E-cclesia. We present preliminary benchmarks of the key operations of the voting client and demonstrate the feasibility of our proposal with readily available cryptographic tools for mid-sized elections.