The non-profit organisation Electis is supporting academic research on e-voting. One such protocol that we’re supporting is “E-cclesia,” an innovative self-tallying e-voting protocol developed by a team of academics of the University of Edinburgh (UoE).
Today, we’re releasing an interview with Nikolaos Lamprou (UoE), who is working on the provable security part of E-cclesia, in particular the mathematical proof of concept of time-lock-encryption. In the interview, Electis’s community manager Lena Melcher talks to Nikolaos about the mathematical problems behind e-voting and how to solve it.
LENA: Can you tell me about your academic background, and how you happened to begin working on e-voting?
NIKOLAOS: Initially, it was my supervisor, Myrto Arapinis, whose research expertise lies in the field of e-voting, who introduced me to this subject. After the discussions we had at the beginning of my PhD regarding e-voting, I was fascinated by how simple the problem of e-voting can be formulated and how hard it is to be solved. Specifically, in paper ballot elections there are properties such as verifiability (everyone knows that the election result is based on the ballots that the talliers have received) and privacy (the vote of a voter remains private even after the end of the election procedure). These properties are required for every e-voting protocol.
By that time, the most naive e-voting protocols that came to my mind was an open vote system where all voters plainly announce their preference publicly (verifiable elections) and another one where the voters secretly handle their ballot to a trusted party (private elections). In the first example, the voters are pretty much confident that their vote is part of the election outcome, but everyone knows how they voted. Contrarily, in the second example, the vote of the voter remains confidential from the other voters, but with the uncertainty that the trusted party will include it in the election results. I was very curious how these initially mutually exclusive properties can be satisfied at once. Since then, I have devoted my research to e-voting to understand the problem better; by reviewing the state-of-the-art mathematics behind e-voting and trying to improve the current limitations of the most prominent proposals.
LENA: How are mathematics related to computer security and specifically to e-voting?
NIKOLAOS: To answer this question, let me tell you a story. When I was doing my master in theoretical computer science back in Athens, I attended a cryptography class. I recall the professor explaining the Diffie-Hellman protocol, which is a method of securely exchanging cryptographic keys over a public channel. My professor explained it by saying: “Alice, Bob and Eve met for the first time at a social event. Alice wants to communicate with Bob in a public way, that means under the presence of Eve. On the other hand, Alice doesn’t want Eve to listen to her discussion with Bob. So Alice speaks for the first time to Bob, and Bob responds to Alice. At this initial stage of their discussion, Eve curiously observes them and understands everything about what they are saying. After this initial conversation, Alice and Bob can communicate without Eve being able to follow them.”
At first, I found this impossible; it was like magic. When the professor pointed out the mathematics behind this example, I was impressed by how people can solve problems of trust merely based on mathematics. This was uncharted territory in my mind from my bachelor in pure mathematics until back then.
So answering your question, security assumptions in cryptography and specifically in e-voting rely on the difficulty of mathematical problems (e.g. the discrete logarithm problem). Security formulation, adversarial modelling, protocol design to name just a few are essential aspects of cryptography and computer security that require mathematical expertise and as my professors were saying “mathematical reasoning and maturity”.
(Cipher, 1803, source: https://www.lewis-clark.org/article/2222)
LENA: What added value does E-cclesia bring to the e-voting solution Electeez?
NIKOLAOS: E-cclesia is a self-tallying e-voting protocol, so the only participating parties are the voters and an election authority is needed only to provide the list of the eligible voters. E-cclesia is named after the assembly of citizens in the democratic city-states of ancient Greece that had the authority to decide on a wide range of political issues. The voting solutions they used at that time were restricted to raising hands or counting stones or broken pieces of pottery.
In E-cclesia the voters are responsible for the production of the election result. This decentralized solution, which is a merit of all self-tallying protocols, leads to strengthened security models as we don’t have to trust even a single tally for the integrity of the election result. Moreover, it makes the protocol useful for a variety of other applications where the existence of a tally is not applicable (e.g. Bitcoin governance).
In comparison with the other self-tallying protocols in the literature and practice, we managed to solve many of the previous limitations. One of these was the problem with the abort. Specifically, a voter could make the protocol abort by deviating from the actual protocol. Another issue was the fairness problem, where a voter sees intermediate results and changes her initial vote (or does not open it at all). In E-cclesia, we managed to fix these limitations. Moreover, we provide our security claims in the highest standard security framework in the literature, the universal composable framework (UC). In the UC framework, we have an ideal execution of our protocol, where the adversarial influence is very limited, and the real protocol execution, where the adversarial influence is as in the real world. If a protocol is proven, UC secure means that the real world adversary is as “strong” as the adversary in the ideal world, which is very limited. Moreover, if a protocol is proven UC secure, it means that the security claims still hold even if many instances of our protocol run in parallel.
One more thing that makes E-cclesia so unique is our modular approach. As a result, future updates to E-cclesia can be done smoothly without re-proving the security of the whole protocol; rendering it easily accessible for further development.
LENA: What could this further development of E-cclesia look like?
NIKOLAOS: For example, at the current implementation, a trusted party is responsible for the generation of the parameters (e.g. in our case the RSA numbers). So if we require our protocol to be fully decentralized, we have to find a method to generate the parameters in a distributed manner. Ideally, the distribution centres will be all the voters; but for efficiency reasons, we might use only some of them. It is a trade-off between security and efficiency. For the time being, one entity generates these parameters, something that will change in future updates.
At the moment, a voter is subject to coercion, so a coercer can influence the way a voter votes. The coercion is correlated with another security issue which is vote-buying, a voter can sell their vote to someone else. We will address it in future updates.
In terms of efficiency, we can substitute our Rivest et al. time-lock encryption with another time-lock crypto primitive that is based on the Bitcoin ledger and witness encryption. The advantages are noticeable in terms of efficiency as the computational burden for solving the puzzles is transferred to the miners of the bitcoin ledger instead of the voters making E-cclesia more client-friendly. We excluded this solution from the current versions of E-cclesia because the state-of-the-art of witness encryption libraries are not at the level that we desire, and further development is needed.
As you can see, many improvements can be made. It is a demanding project; however, we should be ambitious because, at the end of the day, we are the ones who set the limits of what is achievable and what it is not. I am very confident in saying that E-cclesia still has many things to accomplish before it can be considered a stepping stone in e-voting. But as they say, Rome wasn’t built in a day; we are on the right track.