Cryptography and elections

Transparent and verifiable electronic elections are technically feasible, but for a variety of reasons, the techniques used are not actually viable for running most elections—and definitely not for remote voting. That was one of the main takeaways from a keynote at this year's linux.conf.au given by University of Melbourne Associate Professor Vanessa Teague. She is a cryptographer who, along with her colleagues, has investigated several kinds of e-voting software; as is probably not all that much of a surprise, what they found is buggy implementations. She described some of that work in a talk that was a mix of math with software-company and government missteps; the latter may directly impact many of the Australian locals who were in attendance.

She began by noting that the "cheerful title" of her talk, "Who cares about democracy?", was hopefully only a rhetorical question, which elicited some, perhaps slightly nervous, laughter. The cryptographic algorithms and protocols that can provide step-by-step proof that a voter's intent was correctly gathered and that the vote was counted do exist, but the assumptions that need to be made about user behavior make them too difficult to use for government elections. It is unreasonable to expect that voters will take the fairly onerous actions to actually verify those steps; "it's too easy to trick people". These kinds of systems do not "adequately defend against bugs and fraud for serious elections".

End-to-end verifiable elections

The details of these techniques are complicated, she said, but "the principle is really simple": the system should "provide evidence that it has done the right thing with the data at every stage of the process". (The YouTube video of the talk shows her slides, which have some pictures that give an overview of the scheme.) Voters should be able to check that it has done so by using their own code—or code provided by organizations they trust. When voters use a machine that they may not trust to vote, they should get some kind of receipt that can be used to verify that their vote has been recorded accurately. That receipt can then be checked on some other device to ensure that the vote stored in the encrypted receipt is, in fact, the choices they wanted to make.

The next stage is a public bulletin board that lists the encrypted votes that have been recorded for the election. It would need to have some "fancy features" to ensure that changes could not be made to the list once it has been posted, but it could effectively be just a web page with a list of encrypted votes recorded. If there was no concern for privacy, those votes could simply be decrypted and tallied. But since there is normally a need for secret ballots, the votes, which have identity information attached to them, cannot just be decrypted.

So a series of "mixing servers" would be used to shuffle the votes (without the identity information) and re-encrypt them, to break the link between who voted and for what. When you mix a bunch of paper ballots in a box, you don't know what shuffle was applied to the votes, but that is not true for electronic shuffling. So there should be multiple mixing servers, each using its own algorithm, and, ideally, each being run by a different organization; as long as those organizations are unlikely to all collude on the outcome (e.g. political parties) the mixing will break that link.

There is still a problem, however: whether those mixing servers also "fiddled the contents" while doing the shuffle. There is some "fancy crypto" for ensuring that the contents have not been altered, which would allow a mathematical proof of honest mixing to be published on the bulletin board.

The final step is for some kind of election authority to use the secret key to decrypt the votes and tally the results. That is, of course, another step where things can go awry. Once again, though, there are cryptographic methods that allow the authority to prove that it has not altered the votes while decrypting and counting them. That proof would also be posted to the board.

She reiterated that the algorithms are complicated, but that the technique provides a kind of openness, though one that is different from what the open-source community normally envisions. It is not necessary and, in fact, not sufficient for the different organizations to use open-source software to perform these steps—for one thing, it is impossible to be sure they have used the software that they claim to have used. But all of the steps are verifiable using open-source (or other) code that does not rely on the software used in the process. It relies on voters actually verifying all of those steps, however.

Analyzing an implementation

She and two colleagues looked at the Swiss Post e-voting system, which was provided by a company called "Scytl", last year. It does not provide end-to-end verifiability, but does provide shuffling and accurate-decryption proofs. As their report notes, it is meant to provide "complete verifiability", rather than "universal verifiability"; "complete" means that there is an assumption that at least one of the server-side systems is behaving correctly.

In an outcome that will probably only surprise politicians that push (and purchase) these kinds of systems, Teague and her colleagues, when looking at the code, found a bug in each part of what the system was meant to be able to prove. "There were only two things that they were supposed to prove and they were both buggy." In this context, "buggy" means that it can provide a proof that everything has been done correctly, "while actually fiddling the votes".

She went into some detail of the problem that they found in the accurate-decryption proof, which uses a Chaum-Pedersen proof of the equality of discrete logs. Scytl had "rolled its own" implementation that did not hash an important element of the calculation during the process, so that value could be calculated after the "proof" had been presented without altering its verifiability.

As it turned out, one of her colleagues had made the same mistake and written a paper [PDF] describing the problem and its implications a few years earlier. That made it easy for them to see the problem when looking at the code; in fact, it took longer for them to get the code to compile and run than it did to find the problem. In practice, changing votes in this fashion would be obvious, because it would result in nonsense votes, though they would cancel out valid votes.

Fully end-to-end verifiable e-voting is possible, but when you start considering government elections using a system like that, "there are some serious concerns and limitations", Teague said. For one thing, voters need to do a lot of careful and complicated work to verify that their vote has been properly encrypted; if they do not, they could be tricked into recording a vote that does not accurately reflect their intentions. In addition, the system can allow voters to prove how they voted, if it was done on, say, a home computer, which may not be a desirable outcome; e-voting in a polling place largely eliminates that particular concern, however.

Beyond that, verifying the proofs of proper mixing and accurate decryption is quite complicated; it requires significant expertise, which may not be acceptable for a democracy. Subtle bugs can partly or completely undermine the security properties of the system as she had shown. This is different from traditional paper voting in that a subtle problem in a system like that does not hand over the ability for "total manipulation of all of the votes to one entity".

In summary, she said, there are reasonable solutions for doing e-voting in a polling place, but remote e-voting in a way that "really safeguards the election against manipulation and software bugs" is an unsolved problem. "That's the good news. That is the most optimistic part of my talk."

NSW iVote

She turned to the iVote system for remote e-voting that was put in place by the state government of New South Wales (NSW) in Australia. She asked, what does end-to-end verifiability have to do with iVote? "Really, not a lot."

For iVote, voters use JavaScript provided by Scytl to cast their vote. In order to verify it, however, they have to use a different application that the NSW Election Commission (NSWEC) and Scytl provided. That application was closed source up through the election, so you had to trust Scytl/NSWEC to tell the truth when you asked them if they had recorded your vote correctly. Four months after the election, some of the code was made available under a "reasonable" non-disclosure agreement (NDA) so that it could be inspected. But at election time, there was no proof that the vote was recorded correctly.

The public bulletin board from her idealized view of an end-to-end verifiable election was replaced with a secret bulletin board that listed which votes were recorded; it was available within NSWEC, but not to ordinary citizens. So there was no proof that a given vote had even been counted. Likewise, the series of independently administered mixing servers was replaced with a single mixer, so paths from voters to votes could potentially be traced. It is a far cry from even the idealized system that she had just argued could not be trusted for a government election.

She and her colleagues were already looking at the code from Scytl, in the context of the Swiss Post analysis, when the first iVote election was taking place. The Swiss had put the code out for review six months ahead of the first election so that any problems could be found and fixed before it was used. At the time the researchers found the first problem with the Swiss Post system (for the shuffle proof), NSWEC was already using iVote for early voting.

When the Swiss Post bug went public, NSWEC released a statement that said, in effect, "yes, we do have that critical Scytl crypto defect, but don't worry, we're going to use it anyway", she said to laughter. Scytl patched the software to fix that bug during the election, however.

The second bug that was found in the Swiss Post system (that she had detailed earlier in the talk) came to light a week or so after the first; given that the software came from the same company, was iVote susceptible to that bug as well? The day before the election using iVote, NSWEC put out a release [PDF] saying that it was confident that the second issue found for the Swiss Post system was not relevant to iVote. "This was highly implausible at the time." She could imagine a situation where neither of the bugs were relevant, but it simply was not reasonable to suggest that a second bug found in the same code base would not be present in the NSWEC version.

At the time of the election, anyone wanting to see the code had to sign an onerous NDA that said you could not release any of your findings for five years. She and her colleagues did not sign that agreement, so they could not see the code. Four months after the election (so, mid-2019), it was changed to have a "45-day quiet period", which was far more reasonable.

NSW is supposed to have laws mandating public access to source code, she said, but that does not apply to voting software. Part of what she wanted to convey in her talk is that "laws about election software really matter". Switzerland has good laws of that sort, she said, "New South Wales has very bad laws". She showed the laws for election software security, noting that they say nothing about actually securing that software; instead, they impose penalties of up to two years in jail for disclosing the source code or flaws in the security of the voting software without approval. It is not just some part of a larger body of law requiring safe election practices, "this is what substitutes for legislation mandating secure and transparent electoral processes".

Unsurprisingly, the bug found in the Swiss Post system was relevant to iVote as they discovered later. The obvious correct fix for that bug was to simply add the relevant parameter into the hash, but Scytl took a completely different approach. They chose a random value, raised the missing parameter to that power, and hashed that instead. But that does not fix the problem. The parameter needs to be hashed so that it cannot be calculated later; hashing it commits to a particular value. Raising it to a random power, without hashing (and thus committing to) that random value, still allows the important parameter to be post-calculated.

If the code had been available for analysis before the election, rather than four months after, the problem could have been spotted in short order. Instead, NSWEC ran the election with flawed, manipulable software because they "did not make it openly available to scrutiny by people who knew what they were doing". She suggested that attendees look for themselves on the Scytl web site that allows one to apply for access to the iVote code. She only spent a short amount of time verifying the problems they had already found, and discovering that the fix was no fix, but there is "heaps and heaps of code there"; finding bugs in that code and getting them fixed will incrementally help secure the system before it gets used again.

Victoria

She asked the audience how many were from NSW (many) and if they had used iVote, but seemingly no one had (or would admit to it). She then asked how many were from the state of Victoria (as she is). She asked, "feeling smug?" That was met with groans, nos, and scattered laughter as attendees guessed that things there were probably not much better—or perhaps even worse.

At the end of 2019, a law passed the lower chamber of the legislative body for Victoria that would allow the Minister for Elections to choose a voting system that would be universally applied to all local elections (i.e. not for federal offices). It allows the Minister to choose postal voting, which has a body of laws already to govern election security and privacy, attendance voting, which has an even older set of laws surrounding it, or "anything else he feels like with no restrictions whatsoever".

It is clear what the agenda is, Teague said; there is no groundswell for voting with "bronze discs or pottery shards". It is meant to facilitate "large scale, totally unregulated electronic voting compulsorily for everyone" who is voting in local elections in Victoria. The legislation is coming up for a vote in the upper body in February; she suggested that attendees from Victoria figure out who their five representatives are and contact them to request the removal of that clause. "Once we lose the ability to have genuine democratic local elections in Victoria, we are never getting it back."

Risk-limiting audits

She then shifted gears to talk about a pilot project that she participated in to do a risk-limiting audit for a San Francisco district attorney election. Instead of talking about electronic voting, the second half of her keynote would be about electronic counting of paper votes, which is an easier problem in every way, Teague said. Assuming that the paper records have been properly secured along the way, there exists a full record of voters' intents that can be double-checked against the tallies provided by counting devices.

In jurisdictions that use paper ballots in the US, that kind of double-checking is often done; "serious statistical audits of those paper records" are performed to ensure that the electronic counting system is accurate. There are a number of sophisticated statistical analysis techniques that can be used to give a level of confidence that the outcome has not been subject to malware or bugs in the counting systems. In her opinion, the best technique is risk-limiting audits.

At the beginning of an election, the auditors will need to decide on the probability of being tricked they are "willing to live with"; if you are doing random sampling, there is always some possibility that the statistics do not reflect the results. Then there are calculations that can be made to determine how to do the sampling such that those constraints are met; if the sampling indicates that the reported outcome is not as it should be, then a full count by hand should be done.

These audits are used in several states, but the US has a "really weird primitive voting system" where a single candidate is chosen by each voter and the one with the most votes wins. The audit is just checking to ensure that the declared winner is actually the candidate with the most votes. But some US jurisdictions are starting to use instant-runoff voting, "which in Australia is called 'voting'", she said to laughter. It is a great voting system, she said, but it breaks the risk-limiting audit frameworks that are in place.

She got involved in a project to take the Australian understanding of preference voting and to combine it with the ideas of risk-limiting audits for the most recent election in San Francisco, which was held in November 2019. (LWN covered a talk about other aspects of San Francisco election handling back in August.) The district attorney election had four candidates and the results were quite close.

She and her colleagues in the project decided to test their risk-limiting audit techniques on that race. They only got access to the postal votes, which turned out to be about two-thirds of the votes cast. So the audit did not actually provide evidence that the outcome of the election was correctly decided, but it demonstrated how the audit could work in an election with preferential voting. It turns out that the outcome when considering just the postal votes is the opposite of the outcome when looking at all of the votes, because polling-place voters overwhelmingly chose the winning candidate. "That doesn't really affect the math, nor does it affect how this thing, in its ideal form, should work."

The idea behind the project is to provide a set of "completely open, publicly available verification and auditing tools". The actual counting machines are a kind of scanner and digitizer that comes from a proprietary company (Dominion) that she does not trust any more than she does Scytl. There is no opportunity to look at the code, but they did get the report from that system, which detailed the choices counted on each ballot; "the seventh ballot in bag 52 has this list of preferences".

Using that list, a random selection of ballots is chosen to be audited; those will be examined and compared with what the counting system reported. A tally of discrepancies is then maintained. Then there are two different sets of math analysis that need to be done.

The first is to carefully determine which parts of the preferences are important in terms of the outcome. The order in which the losing candidates are eliminated can sometimes make a big difference in the overall outcome (because the next level of voter preference is then boosted from ballots that preferred the eliminated candidate). Switching the order can cascade into a completely different winner, though usually that is not the case; normally, the low vote-getters can be eliminated in any order and it does not affect the outcome. The tool that they developed looked at the election and determined which of the comparisons were critical and then ignored the rest (for auditing purposes).

The second piece is "to do the careful statistics for eliminating the possibility that the comparison was made wrongly". Both pieces are available as open-source software: Risk-limiting Audits for Instant Runoff vote Elections (RAIRE) and Sets of Half-Average Nulls Generate Risk-Limiting Audits (SHANGRLA). Citizens in San Francisco were able to observe the auditing process, see which ballots were chosen to be sampled, compare them to the reported preferences, and then run the calculations themselves if they wished. The code can be used by others to reproduce the results or to add different types of statistical measures, for example.

Back to Oz

So, like the mechanisms to verify every step of an e-voting election, an electronically counted election can also be verified using an open process, even though the software running on the devices may not be available for scrutiny. But, she asked, what does this have to do with the Australian senate count? "You probably have already guessed—not a lot."

She went over some testimony by the electoral commissioner about the integrity of the senate count. Pointed questions were asked about whether any manual auditing of the ballots had been done and whether the error rate for data entry had been estimated, but the commissioner said that he would need to look into both of those questions. But when asked about whether the commission had followed the recommendations of the last inquiry by the Australian Parliament about the senate elections, which were to appoint expert scrutineers to observe the ballot-counting process, his memory suddenly returned. Parliament had only recommended that action, not required it by law.

There is an important element to his answer, Teague said: actual legislation is needed to ensure that voting is secure. The Swiss e-voting laws are detailed and well thought-out, with an orientation toward transparency of the process, privacy for the voters, and the ability to verify the results; they are not perfect, but they are quite good. Switzerland found out about its problems as soon as it forced the source code to be open, she said to applause.

In contrast, New South Wales found out about its problems 12 days before the election. California has "pretty decent laws about election auditing". But the Australian senate scrutineering rules have not been updated since the days of hand-counted paper ballots, which was a long time ago. In effect, those rules say that scrutineers must be allowed to stand in the room while "they do their thing on their computers". It does not say anything about providing meaningful evidence that those computers are doing the right thing.

What she believes is needed for the senate count is a mandate for a statistical audit of the paper ballots that can be meaningfully observed by scrutineers. There is no need for "the perfect law", just for something that requires auditing and allows public oversight. It seems rather obvious that the electoral commission is not going to do so unless they are forced, so a legislative mandate for that is needed, she said.

The senate count is a place where "there is a risk for undetectable electoral fraud", she said, particularly in the last few seats where "lots and lots of preference shifting" has been needed to decide them. It would be pretty difficult to fiddle with the tallies for the top vote-getters from the major parties, she said, but the preferences further down the list could be more easily manipulated. Unlike some e-voting systems, such as iVote, the senate count is in a much better position to be audited because the paper records exist.

A new project?

She finished "on a slightly upbeat note"; rather than spending 2020 by picking holes in bad software, she thought it might be better to work on a new project. "Democracy is about more than just elections." She spent some time working to defeat—or even just amend—the "shocking train wreck that was our anti-encryption laws" that were passed at the end of 2018. Working to try to convince legislators is not something she ever wants to be involved in again, but it did get her thinking.

The legislative process in Australia is fairly open; the text of the proposed bills is available online under a Creative Commons license. What if there were an online amendment and voting site that would allow cryptographically verified voting on the bills, amendments, and the like. It would allow people to more actively participate in the process and to provide input in ways other than "writing 50,000 submissions" to various committees that "ignore what we write".

She thinks a version could also be rolled out for teenagers so that they could practice debating various issues of the day. The e-voting verification techniques could be used to give users some level of assurance that the votes are being tallied correctly, while familiarizing people with the approach. The lack of an Australian digital ID will make it difficult to trust the aggregation, since the identities of the participants cannot be verified, however. In any case, she would like to pursue something down this path and solicited attendees to tell her that it is a bad idea or to give suggestions for better ones.

[I would like to thank LWN's travel sponsor, the Linux Foundation, for travel assistance to Gold Coast for linux.conf.au.]