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.