Paper 2020/513

E-cclesia: Universally Composable Self-Tallying Elections

Myrto Arapinis and Nikolaos Lamprou and Lenka Mareková and Thomas Zacharias

Abstract

The concept of a self-tallying election (STE) scheme was first introduced by Kiayias and Yung [PKC 2002] and captures electronic voting schemes in which the tallying authorities are the voters of the election themselves. This type of electronic voting is particularly compatible with and suitable for (but not only) Blockchain governance, where governance is expected to be maintained in a fully distributed manner. In this work, we formalize the requirements for secure STE schemes in the Universal Composability (UC) framework. Our model captures the standard voting properties of eligibility, fairness, vote-privacy, and one voter-one vote. We present E-cclesia, a new family of STE schemes, and prove that it securely UC-realizes the STE functionality. We propose a first concrete instantiation of E-cclesia using RSA accumulators in combination with the time-lock puzzles by Rivest, Shamir, and Wagner [Technical report 1996]. To this end, we provide en passant the first UC treatment of dynamic accumulators in the public setting as well as time-lock encryption (TLE) schemes, and prove the equivalence of our UC definitions to the standard property-based definitions.