Electronic voting machines were supposed to make elections cheaper, faster, and more secure, but so far they have failed. In the last decade there has been something of a rush to adopt e-voting, followed by suspicion and controversy over the black-box, “just trust us” nature of the first generation of commercial systems, followed by a return to paper ballots in many jurisdictions. However, if we wish to improve election processes, cheap and fast is probably the wrong goal. It may be possible to use cryptographic techniques to implement end-to-end auditable elections, new in human history.
The e-voting fiasco has illustrated that paper ballots are a better system than they might at first seem. Paper preserves voter secrecy, it is auditable after the fact, and it is even reasonably transparent, if one also allows election observers. But paper ballots must be closely guarded and cannot be directly counted by members of the general public, who in the end have no choice but to trust election officials, observers, counting equipment, and the entire chain of custody. Rather than simply duplicating paper ballots electronically, we should strive to improve upon them.
This seems to be possible. Modern cryptography suggests the possibility of a new kind of incredibly transparent and fair election, where ordinary citizens can verify the soundness of the election for themselves, without ever needing to trust blindly that a huge array of machines and people have acted correctly. This represents a fundamentally new ability: for the first time, it may be possible to hold truly “open” elections.
What are we trying to accomplish?
Ideally, a democratic voting system would satisfy the following criteria:
- Secrecy: to prevent coercion or vote-buying, each person’s vote must be secret in perpetuity.
- Transparency: all voting procedures must be public and understandable by everyone.
- Verifiability: it must be possible to independently audit or validate the election results.
- Usability: it must be easy to vote, and cheap to deploy the system for hundreds of millions of voters.
In this way, each person would vote freely, while the entire society could have confidence in the outcome. The difficultly with these criteria is that they conflict: it is hard to preserve both secrecy and verifiability in a simple, transparent way.
Paper ballots fall short of the these ideals in many ways. They are nicely secret, and the process is reasonably transparent as there are public laws describing exactly how the votes are to be tallied, regulations providing for election observers, etc. However, independent audits are not really possible, because they require access to a large quantity of fragile and politically sensitive paper. In principle, we would like it to be possible for any regular citizen with sufficient time on their hands to perform a complete audit of the election results.
Elections results could be openly verified by publishing copies of every ballot cast, but only if there was some way to ensure that these copies were accurate. This could be done by issuing to each citizen to some sort of receipt of their vote which could be checked against the public list, but then votes would not be secret: they could be coerced or bought by offering a clandestine cash reward for receipts.
While paper ballots leave much to be desired, current electronic voting systems are worse. All e-voting machines are essentially “black boxes” that transform the voter’s choice into a final tally by some complex and unknown process. This makes them completely non-transparent. In the worst case, paperless direct recording electronic (DRE) voting machines are not at all verifiable, which makes them subject to both invisible malfunction and deliberate hacking (either in the voting booth or at the tally station.) There has never been a convincingly documented case of miscount or fraud with DRE machines, but that may only be because such machines leave absolutely no record of the election process!
Because of this, many American states now require a paper record even for otherwise electronic machines, but even paper audit trails are problematic: when is an audit performed? Will all ballots be routinely audited or just a sample? What is the right sample size for confidence in the results? What happens if a discrepancy is discovered? Meanwhile, other states have gone back to paper ballots entirely and a number of electronic voting machines have been de-certified.
Cryptographic Hope
Enter cryptography, the discipline that has brought us such miracles as secure communication between two parties who have never exchanged any information in secret (public-key cryptography), tamper-proof electronic documents (digital signatures), and the ability to prove that one knows a secret without giving it away (zero-knowledge proofs.) In the wake of these achievements, there has been some hope that proper cryptographic protocols will simultaneously solve the secrecy, transparency, and verifiability issues.
Voting might still be electronic in a cryptographic system, but the security of an election would rest on open cryptographic protocols rather than on trusted system implementations, the physical security of ballot boxes, or the honesty of certain people. Even better, the election results would be auditable at any time from public information, and each voter could verify that their own ballot was correctly recorded yet their personal vote would remain secret and unprovable.
Such a system is said to be end-to-end auditable, and represents a fundamental shift: for the first time, it may be possible to hold completely “open” elections in the sense that governments and election officials would have no more authority or power than ordinary citizens. This is unprecedented in human history, and it is exciting.
It is also quite a trick, and has never been demonstrated in practice. Aside from secrecy, transparency, and verifiability, any proposed cryptographic voting system must guard against many different kinds of attacks. These include tampering and “denial of service” attacks against the election, such as the ability to spoil the election through some sort of interference (as might suit an opposition group) or to arbitrarily declare that it was spoiled in some non-disprovable way (as a dictator might wish to do.)
A Toy Example: ThreeBallot
Like much of modern cryptography, the simultaneous provision of both secrecy and verifiability seems counter-intuitive. To aid in the study and conceptualization of such systems, professor Ron Rivest of MIT (the “R” of RSA fame) invented a “toy” voting system in 2006 called ThreeBallot.
It works like this: each voter is given three identical ballots in the voting booth. To vote for a candidate, the voter writes a mark on two randomly chosen ballots; to vote against a candidate, only one randomly chosen ballot is marked.
A valid vote is one in which each candidate is marked on either one (against) or two (for) randomly selected ballots. This could be checked e.g. by an optical scanning machine, much as paper ballots are currently validated at polling stations.
Then the voter secretly chooses one of the ballots and makes a copy of it as a receipt; the others are dropped into the ballot box. Each of the three ballots has a unique serial number.
After the election, all ballots are published publicly, and anyone can tally the election results from these copies. Additionally, each voter can verify that their ballot was published accurately by looking up their receipt in the published list. Yet there is no way to use a receipt to determine who someone voted for, because the voter can arrange to have any particular set of markings on the receipt that they keep. The receipt also prevents tampering, because a would-be tamperer does not know which of the three ballots the voter has retained. Thus there is a 2-in-3 chance of getting away with tampering with (or deleting) any one vote, but only a (2/3)^N chance of getting away with tampering N votes — like tossing N heads in a row, these are very rapidly shrinking odds.
ThreeBallot was never meant to be a real election system, and in fact in a University class voting experiment ThreeBallot was found to have significant security and usability problems: a third of voters couldn’t produce a correct set of ballots the first time, and a student “attacker” was able to manipulate about 20% of the votes cast, enough to change the election result. He did this in part by clandestinely reading other people’s receipts, such as those left in voting booths or on desks. This reminds us once again that security is always about much, much more than good cryptography.
However, the basic ideas of ThreeBallot — randomness in the vote-casting process, voter receipts, published ballots, and probabilistic tampering detection — are found in virtually all cryptographic voting schemes.
Realistic Proposals
Serious proposals are somewhat more complex. Some are designed to be entirely electronic while others are additions to paper ballot systems. Major proposals include Punchscan (2006) by cryptographer David Chaum, Scantegrity (2007) by David Chaum and Ron Rivest, and Bingo Voting (2008) by a trio of German researchers. All of these systems are very cryptographically clever, but as always, security in the real world is about much more than cryptography. A 2005 paper considered how a real election system employing end-to-end auditable protocols might work, and proposed various non-cryptographic attacks including collection of receipts, social engineering of election workers, and denial-of-service attacks which could invalidate the entire election (such as hacking the voting machines to record spoiled ballots.)
Also, many problems just cannot be solved cryptographically. One major reason why we don’t have internet voting is that it is impossible to prevent coercion and vote buying if voters can mark their ballots at home. A physical polling booth can at least be secured against witnesses — though not against, say, someone who will pay for cell-phone camera pictures of a suitably marked ballot. A completely secure voting system is probably completely impossible.
Nonetheless, there is hope for electronic voting systems, not because they would allow us to vote cheaper or faster or more conveniently, but because they hold the promise of more transparent elections. Would-be designers and implementers of voting systems must realize that the purpose of a voting system is not just to count votes, but to ensure that everyone believes that the process was fair, and to ensure that this fairness can be proved as easily and as widely as possible.
This is a nice overview of a well vetted issue: to what extent cryptography can resolve the integrity and trust issues with the vote. One thing at the OSDV Foundation’s TrustTheVote Project we know for sure: so-called end-to-end (E2E) auditable (sic) systems is but a small part of any solution addressing the whole of ballot casting and counting and the ballot ecosystem.
For one simple example, gaining agreement on what the issues are and how they are to be addressed remains elusive. Consider that most E2E system designs assert 3 characteristics (2 integrity & 1 privacy): namely that
[1] a voter can verify that their unmodified ballot is included in a batch of ballots;
[2] any independent 3rd party (or the voter themselves) can verify (with high probability) that the collection of ballots in question produces the correct final tally; and
[3] no voter can prove how they cast their ballot to any 3rd party. Herein lies the rub.
Although the Elections Assistance Commission claims this 3rd criteria within their voluntary voting systems guidelines, some academicians argue that this 3rd ability (or lack thereof) is not inherently part of an E2E definition.
While certainly security is a high priority in the work at TrustTheVote, there is an entire ballot ecosystem of issues to be considered. And we think its worth reminding people that cryptography, as a means of integrity proofing, is but one aspect of (as Stray points out) a thorny multifaceted problem.
Cheers
GAM
http://www.osdv.org
For several reasons, I believe that crypto voting systems will not provide end-to-end security in actual elections.
First, as you note, these systems are just as susceptible to DoS attacks as ordinary e-voting systems. These can take many forms, from the ham-handed (locking up; repeatedly rebooting) to the subtle (lengthening the time required to initialize the system for the next voter; attempting to frustrate the voter by making the GUI slow; producing invalid ballots).
Second, crypto systems’ security guarantees depend upon the voter correctly executing an unfamiliar and unintuitive protocol with the system. An attacker can program the system to execute an incorrect protocol, thus voiding the guarantees [1]. Since the protocol is unfamiliar and unintuitive, very few voters will realize that anything has gone wrong. And if a voter does notice, and report the problem, officials probably will do what they too-often do today: say it’s “voter error” or “a glitch”, and leave it at that. Or, at best, they’ll shut down the system the voter used, leaving other compromised systems in operation. Of course, realistically, there is little they *can* do, other than to shut down all the systems and continue the election using hand-filled paper ballots.
Third, crypto systems are susceptible to the same presentation and selection attacks as ordinary e-voting systems. These can include omitting candidates from the ballot, reordering it, modifying headings to de-emphasize races [2], or modulating the ease of selecting certain candidates. [3]
While hand-filled paper ballot systems are far from perfect, computational presentation, selection, and recording systems create whole new categories of attacks, many of which elections officials (and the public) will never be technically-adept enough to detect.
—————–
[1] Some systems, e.g., VHTI, commit a result to a paper trail before asking the voter to select a “challenge” number. If the result isn’t printed before the voter selects her challenge number, the protocol’s security guarantees are void.
[2] In 2006, the U.S. House race in district 13 (Sarasota) experienced a massive (13%) undervote, which quite possibly flipped the result. Officials attributed the undervote to incorrect race headings. http://www.heraldtribune.com/apps/pbcs.dll/article?AID=/20061115/NEWS/611150751 . A presentation attack on race headings could produce a similar effect.
[3] See http://www.youtube.com/watch?v=V3jHENhdi0w for an over-the-top video on this theme.
>>It is also quite a trick, and has never been demonstrated in practice
Not clear what your criteria is here, but Punchscan, Bingo Voting and Pret-a-Voter have all be used in small-scale binding elections.
With respect to end-to-end verification, some of the comments seem to be confusing physical security and robustness aspects with the notion of verifiability. Clearly cryptography does not prevent shoulder surfing and DoS, nor does it claim to.
Just as digital signatures are not “tamper proof” (they are merely tamper evident), let us not over state the purpose of e2e: as a weather vein of integrity, not a breakwater. It is not offered as a substitute to policy–merely a tool thereof.
Quote:
——
With respect to end-to-end verification, some of the comments seem to be confusing physical security and robustness aspects with the notion of verifiability. Clearly cryptography does not prevent shoulder surfing and DoS, nor does it claim to.
——
There is no confusion. The issue is what crypto systems do for overall security in actual general-public elections for governmental offices, not how crypto systems implement a protocol that is theoretically secure under a highly-restricted set of conditions. Unfortunately, there is a common perception — particularly among the general public — that cryptographic voting systems are “secure”, full stop. [1] My post aimed to dispel this perception by describing some of the ways an attacker might sidestep a crypto system’s security guarantees — and, not coincidentally — avoid bumping the weather-vane while she does so.
[1] It doesn’t help matters that some crypto-voting practitioners, e.g., http://www.votehere.net/old/default.php , use rhetoric that promotes this kind of thinking (“VoteHere has developed election technology that let’s [sic] you prove that your vote was counted as you intended, while allowing anyone to audit the election results. This unique, groundbreaking technology meets the same audit standards of banking, express shipping, e-commerce, and other transactions people trust every day.”)
Thanks everyone for the lively discussion so far. So here’s a question for all of you: what would you say is the weakest link in security and confidence of current voting systems? (Pick your favorite jurisdiction if it helps to narrow the question.) Will cryptographic methods help this? Should e.g. the Obama administration consider them in its review of election reform?
Thank you for the questions. I believe that computational ballot presentation, selection, and recording are the weakest links in voting system security and transparency. This is primarily because computational devices are inherently mutable, and their internal states are basically invisible, and thus beyond effective supervision by pretty much anyone. How do you know that the “Xyzzytel Model E470” CPU in your computer doesn’t contain an opcode permitting a user program to execute the next-called function in kernel mode? Indeed, how do you even know that it was made by Xyzzytel? How do you know that your system’s chipset doesn’t contain a hidden loader and an associated radio receiver that permits an attacker to invisibly load code into it? Really you don’t know, and can’t know, particularly when “you” are an ordinary citizen and “your system” is the collection of e-voting machines used in a jurisdiction that has power of law over you.
Voter confidence is another matter altogether, and too often is perceived as a goal in itself (or even the primary goal of elections), rather than as an effect arising from the use of the most secure and transparent election systems and procedures. Voters too easily become confident in bad systems (e.g., the initial reactions to touchscreens), and too easily lose confidence in basically good systems (e.g., the reactions to Florida’s punchcard ballots), depending upon the prevailing rhetoric.
I do not believe that cryptographic methods can rescue computational vote presentation, selection, and recording systems; I think, instead, that they open up new avenues of attack (e.g., social engineering of the voter-machine protocol) while giving the false impression that crypto-assisted computational systems are “secure” (full stop).
Cryptographic methods might be able to practically enhance the security of hand-filled paper ballot systems (e.g., Punchscan). Though, as with computational systems, crypto methods open hand-filled paper to social-engineering attacks, such attacks probably will be less effective than those against computational systems, because the paper can’t interactively mislead the voter, and it can (maybe) effectively be audited before use.
I think the incoming administration should focus on improving election security and transparency by developing proper oversight procedures for administering hand-filled paper ballot systems. This oversight should include, at a minimum, precinct counts, general-public supervision of ballot handling, and statistically-supported hand audits. The administration should actively discourage the use of computational ballot presentation, selection, and recording systems except when needed to permit disabled voters to vote independently. Even then, the administration should prefer non-computational alternatives, e.g., the Vote-PAD, http://www.vote-pad.us .
Ronald:
“There is a common perception — particularly among the general public — that cryptographic voting systems are “secure”, full stop”
I’d love to meet these people! 🙂 As someone working on said systems, my personal experience has been staunchly the reverse!
Jon:
Hard to talk about a weakest link. There are many aspects, and certainly I don’t favor basic electronic systems either. I like paper ballots… I’ve been a returning officer in these kinds of elections. They’re pretty good.
However the weak link that I’ve taken an interest in is the notion that somehow the development of the democratic process climaxed in the 1870’s and that there’s really no new directions to explore, no new properties that could be desirable, and no solutions solutions can be found, thank ye very much.
I’m not referencing present company of course, but rather the other side of coin to the folks Ronald was mentioning—that paper ballot systems are “secure”, full stop.
Ronald,
You mention non-computational alternatives. I just want to take the opportunity to point out that the notion of end-to-end verification is something that is bigger than the technology that implements it.
ThreeBallot for example—e2e, no computers (well mostly). At little cumbersome for the voter. I wrote a paper recently that gives another example:
http://www.site.uottawa.ca/~aesse083/papers/aperio-WOTE.pdf
Again, E2E, no computers. Are there more procedures to follow? Yes. I just wanted to make the point that e2e is an integrity standard, and “crypto voting” is just one way to realize it.
Another issue I’d like to expand upon is “transparency”. A good definition is “a property of a system that permits members of the general public, having ordinary intelligence and education, to effectively supervise that system’s use and operation”. “Effectively supervise”, in turn, means, “determine whether the system is being operated properly, determine whether it is doing what it is advertised to do, and be able reasonably to fix it or to work around problems”.
Transparency of election systems natural analogous to the concepts of self-government. As we elect representatives to conduct our business, and hold them accountable via elections (and by writing letters, and engaging in protests, and acting as jurors, and…), we also implicitly “elect” voting systems. Or, rather, our representatives (or people appointed by our representatives, or people who lobby our representatives…) choose them. But, unless those systems are transparent, we have no analogous way to hold them accountable; yet those systems control the outcomes of elections — the most important means of holding our representatives accountable; you see the Gordian Knot.
At present, we push around (instead of cut) this knot largely by delegating supervision of our elections systems to public officials and, especially with electronic systems, to vendors, “test labs” and other experts. But that’s effectively delegating to a small group of experts the ability to determine our elections’ outcomes. Human nature being what it is, I think that this is certain eventually to cause (big) problems, if indeed it hasn’t already. We need some real checks and balances on our elections systems, and I believe the only way we can get them is to use transparent systems, and to encourage the general public assiduously to supervise them.
One of the problems with computational systems is that only a tiny sliver of the general public can effectively supervise them. Some crypto techniques attempt to improve this situation by providing a receipt that a voter can use to determine whether her votes were recorded as cast [1], and other data that a observer can use independently to collate the election. But, as I noted earlier, these techniques do not prevent an attacker from using a variety of other methods to corrupt an election, some of which are created by the crypto techniques themselves. Crypto thus gives the appearance of transparency, but only a modest portion of its substance; there’s still plenty of hidden machinery whose proper operation is required for elections’ integrity, but which ordinary citizens can’t possibly supervise.
Backing up a little, we should think long and hard before doing things that encourage the public to delegate the conduct of elections to experts. As with the jury, but even more so, I think Liberty rests upon the general public’s effective supervision of elections.
[1] (But that she can’t use to prove how she voted to a third party).
[Admin: The sentence beginning “Transparency of election systems natural analogous to the concepts of self-government” is, obviously, broken. I mean to say, “Transparency of election systems is analogous to the concepts of self-government”. Please fix the post. Thanks. -R]
Aleks: Thank you for the note on “E2E” vs. “crypto”; good point. But I have some problems with the term “E2E”, because, at least when used with computational ballot presentation and selection, its protections end well shy of the “input end” of the voting process.
Thank you also for the cite to your paper. I’ll read it soon.
Hi Ronald:
Well the term e2e has a bit of a sordid history. We (parts of the research community) picked it up after the EAC introduced it in the 2005 Draft VVSG. We were glad to have a proposal for a common term to encapsulate the notion, though EAC’s definition was a sort of an information system design framework.
The academic literature distilled out the three integrity properties (the ones you list) later. So in that sense, the term has evolved into something more general.
Then in the 2007 draft VVSG, the term was completely removed, which I found frustrating. I understand they just couldn’t arrive at solid enough definition. Now I hear that in light of the various research successes, they’re taking an interest in the term once again, so they may resurrect it.
We’ve pondered many replacement terms, but have sort of just stuck with it partly due to precedent.