In my previous blog posts about Solon I have mostly focused on the high-level interaction between Solon and Liquid Feedback. Now it is time to dive into the good stuff: the cryptographic e-voting algorithms that scientists have been developing since the 80's. But first, we need to understand our requirements. What does it mean to develop a secure e-voting algorithm?

Most academic articles on e-voting algorithms will begin with a recital of requirements for a secure election or secure voting. The list is quite long, so sometimes an article may omit some of these, but there is a well established consensus that what I will write about in this post is what a secure election is about. I have taken this list from a really well written overview of different e-voting algorithms: "A framework and taxonomy for comparison of electronic voting schemes" by K Sampigethaya, R Poovendran, Computers & Security, Elsevier 2006. I recommend you read it if you want a deeper understanding on this topic.

Often when various e-voting products are discussed (for example, Finland trialed one in 2008 but it lost 3% of the votes cast so a court ordered new elections), any criticism is usually brushed aside with a comparison to online banking: If I can conduct my banking securely over the internet, surely we can do elections too! When you read the below list, you'll realize that this is a very ignorant comment. Online banking is a piece of cake compared to these requirements.

(And by the way, we don't really use "secure" online banking algorithms, such as DigiCash, because it turns out we actually trust our banks not to steal our money. For example, when you make an online payment, your browser will show a text that the payment was made, but in a cryptographical sense you have not really been provided a receipt. It's just a piece of text on your computer screen. You just trust that the bank will keep the correct amount of money in your account - but if it didn't, you don't really have any way of proving the bank wrong. Hence, the "secure" part in online banking only refers to the security from outsiders trying to access your bank account. For this you just use passwords and standard https, that's all. But I digress...)

Fundamentally the challenge with e-voting is that the voting protocol at the same time must 1) identify voters to prove that they are eligible to vote, 2) keep their content of their vote secret and 3) still be able to "read" the votes so they are counted and also provide some verification that all votes were counted correctly, but still not provide any traceability for who voted what. These requirements are contradictory with each other and that's why this is so much harder than, for example, online banking. The exciting thing is that cryptographers have taken on this challenge and come up with algorithms that are up to the task!

So let's start. To make the concepts a little more understandable, I will for each requirement also compare how this requirement is satisfied by traditional paper-based voting, using Finnish elections as a specific example.

Requirements of secure (e-)voting

Eligibility

Only eligible voters can cast a permitted number of votes.

In Finland, the authorities at the voting place have a list of the people who are eligible to vote at that voting place. (You have to be a citizen, 18 years, etc...) I have to provide a photo ID, and they then check that I'm on the list. To ensure that I can't vote twice, a line is drawn over my name.

Fun fact: Some e-voting algorithms actually permit to cast more votes than you are permitted to, instead they only count the correct amount of votes you have cast, such as the most recent one, and discard the others.

Privacy

Nobody can find out how I voted. This includes the person or computer who is counting the votes.

This is why you use an election booth, so nobody can see what you write on the ballot. The ballot is then folded and dropped into the a sealed box, the ballot box. At the end of election day the box is opened, but at this point the ballots don't contain any identifying information of who cast which ballot. (...except for fingerprints. You should wear gloves!)

Fun fact: The expectation for privacy is a fairly modern invention. In ancient Athens, people would stand in the city square and just raise their hand. I understand this is still the case in Switzerland?

Receipt-freeness

This is a complement to privacy: Even if I wanted to, I should not be able to reveal or prove to someone else how I voted. This is to prevent me from selling my vote or also from being coerced to reveal my vote to someone.

Well, in Finnish elections there is no receipt. I draw a number on the ballot and drop it in the ballot box and then I go home.

Fun fact: Apparently in Italy many people would use their phones to take a photo of their ballot. Who knows for what purpose... For this reason it is prohibited to take a camera with you or use a camera in the voting booth, both in Italy and in Finland.

Verifiability

Any participant should be able to verify that votes were counted correctly. This can be broken into different flavors:

Individual verifiability is when each voter can verify that his own vote is part of the tally and has been counted as part of the final result.

Universal verifiability is when anyone can verify that all valid votes have been correctly counted. This is of course much better.

In Finland and most paper-based elections there is something we might describe as distributed trust verifiability. An individual voter cannot actually participate or observe the vote counting process. However, each party that participates in the election can send their representatives. The ballot box is opened and votes are counted while all parties (and some independent observers) are present. This way nobody can cheat, because they all keep an eye on each other. This is a sufficient level of verfiability, because it doesn't make sense that all parties would collude to commit fraud.

Another reason why traditional elections are not universally verifiable is because there are multiple different voting places. So nobody is able to observe all the votes counted everywhere in Finland.

Fun fact: This comic explains the problem with many of the naive e-voting systems that are in widespread use today. How can we know the computer counted the votes correctly? We trust the banks to keep our money in our accounts without getting a receipt, but experiences from Russia to Florida suggest we should not blindly trust our politicians to count our votes...

Dispute-freeness

This is similar to verifiability, yet different. The idea here is that if someone claims that his vote has been tampered with, the voting algorithm has means to either prove or disprove such claims.

Traditional elections are not strongly dispute free, this is more a property that is provided by constantly observing the election process from start to finish, and recording all events, such as "voting started at 8AM and Joe and Jane verified that the ballot box was empty before it was sealed".

Fun fact: Using a camera is a great way to record what happens too, I don't see much to dispute in that video from Russian presidential elections.

To really understand the point of dispute-freeness, we could use Liquid Feedback as an example. LQFB is publicly verifiable because they publish how everyone voted. So everyone can check that their vote is part of the tally, and anyone can check that the votes have been summed up correctly. However, because it lacks any cryptographic functionality, LQFB is not dispute free. If a voter would say "that's not really what I voted, somebody has tampered with my vote" we have no way of knowing if that is true or not. The PostgreSQL DBA could at any time change anyones vote in a LQFB database (just like the banks could take your money). So should we trust the random voter, or the DBA? Perhaps most people would trust the DBA...

Ok, but someone can make false accusations, that's not so bad? Turns out it is... You see, now if the PostgreSQL DBA wants to tamper with the voting process, he could change a few votes to his liking. Then, if someone notices this and protests, the DBA could just deny anything and say that the voter is just trying to make false accusations. In other words, dispute-freeness is actually a critical part of verifiability!

Again, we are at the heart of designing a secure voting process here. Like the Russian video above shows, we really want a voting algorithm that doesn't depend on blindly trusting the guy who is counting the votes. That's not the case for traditional elections either, so it shouldn't become worse when we use e-voting.

Accuracy

Kind of obvious, but in traditional paper-based elections this is actually a hard challenge. Is that a nine or a six? Is that a one or a seven? Who would've thought, all our election results are subjective judgements to some degree!

For computers this shouldn't be a big deal, but it might surprise you that the system trialed in Finland lost 3% of votes due to programming errors (a combination of performance and usability problems). The fact that the system was inherently insecure and the TietoEnator programmers could have simply made it produce any results they wanted was not the reason the election results were discarded.

Fun fact: In the infamous Florida re-count when Bush was elected, they must at some point have realized that actually the margin of error is bigger than the "true" distance between the candidates. Personally I'm convinced Jeb Bush, the governor, simply ordered to stop the recount at a convenient moment when his brother happened to be leading the re-count results.

Fairness

Fairness is a strong word but in academic papers on e-voting it means a very specific property. That nobody is aware of the tally while voting is still ongoing.

Think about it, it's the perfect crime. There are a few hours left to vote, and your candidate is a 100 votes behind. Now all you need to do is to find 3 buses and fill them with voters that you know will vote for your candidate. (E.g. blacks will vote for Obama, etc...) Then you just make sure to drive them to the voting place in time and you have 150 extra votes. Giving someone a lift to the voting place is not even illegal.

To continue with the LQFB comparison, this is the other property where a cryptographically secure e-voting algorithm will make a difference. Currently the PostgreSQL DBA of course is able to see the state of voting at any time, even if end users only see the results when voting is closed.

Robustness

Instead of tampering with the results, someone might simply try to sabotage the voting process. A robust voting algorithm will be resistant to such attacks.

To again use LQFB as an example, the DBA or sysadmin could simply pull the power from the server to stop people from voting. (Especially since because of the fairness issue, he can also see whether voting is going his way or not...) Cryptographical e-voting algorithms typically rely on some kind of threshold cryptography, where voting protocol is executed by a group of independent actors (such as each party has one server under their control) and if one actor tries to block the voting process, others can still continue without him.

Fun fact: distributed trust here is the same concept as using a shared PGP key where 5 guys have a share of the key and you need at least 3 of them to decrypt a secret email.

Incoercibility

Coercion means that an outsider tries to force you to vote a certain way. This could come in many forms: Unless you vote for Putin, you will lose your job. Unless you vote for your husband, he will beat you up. Unless you vote for this honorable Italian gentleman, bad things will happen... Privacy and receipt-freeness are the ingredients that together provide incoercibility.

It is worth pointing out that physical security also provides incoercibility. So when traditional elections use a voting booth, and nobody else is allowed to go with me into the booth, and I'm not allowed to use a camera, and so on... then traditional elections are pretty secure. If I'm allowed to vote from home over the internet, nobody can know whether someone is holding a gun to my head, or her abusive husband is looking over her shoulder. There is nothing a cryptographic algorithm can do to provide physical security like a voting booth - unless it includes secure mind reading.

***

So that's my list! Pretty exhausting, isn't it? Now, if we can find an algorithm that does all this, we also has to hope it is practical to implement (ie using standard computers connected over the internet) and that it scales to millions of citizens voting.

In addition, for the particular case of Solon, we want it to be able to handle:

• preferential voting, in particular Schulze rank
• delegated voting
• including the possibility to delegate your vote for all future issues for which voting is not yet open

These last 3 items are what worries me most. There's 30 years of research that has gone into cryptographic e-voting algorithms, but alas they have only focused on re-creating the traditional elections we are used to having. (Which is a bit silly, since at least in Finland they work perfectly fine with the paper-based method.) It turns out many of the proposed algorithms could not handle delegation of future votes, for instance. I'm hoping the Acquisti algorithm can be twisted to meet also these requirements though.