Paper 2020/513

E-cclesia: Universally Composable Self-Tallying Elections

Myrto Arapinis, University of Edinburgh
Nikolaos Lamprou, GIRY
Lenka Mareková, Royal Holloway University of London
Thomas Zacharias, University of Edinburgh
Léo Ackermann, ENS Rennes
Pavlos Georgiou, University of Edinburgh

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).

Available format(s)
Cryptographic protocols
Publication info
e-voting anonymous broadcast universally composable security
Contact author(s)
marapini @ inf ed ac uk
nikolaoslabrou @ yahoo gr
lenka marekova 2018 @ rhul ac uk
tzachari @ inf ed ac uk
leo ackermann @ ens-rennes fr
pavlos1998 @ gmail com
2022-12-01: last of 4 revisions
2020-05-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Myrto Arapinis and Nikolaos Lamprou and Lenka Mareková and Thomas Zacharias and Léo Ackermann and Pavlos Georgiou},
      title = {E-cclesia: Universally Composable Self-Tallying Elections},
      howpublished = {Cryptology ePrint Archive, Paper 2020/513},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.