Yesterday, I testified before a hearing of Colorado’s Election Reform Commission. I made a small plug, at the end of my testimony, for a future generation of electronic voting machines that would use crypto machinery for end-to-end / software independent verification. Normally, the politicos tend to ignore this and focus on the immediately actionable stuff (e.g., current-generation DREs are unacceptably insecure; optical-scan is the best thing presently on the market). Not this time. I got a bunch of questions asking me to explain how a crypto voting system can be verifiable, how you can prove that the machine is behaving properly, and so forth. Pretty amazing. What I realized, however, is that it’s really hard to explain crypto machinery to non-CS people. I did my best, but it was clear from conversations afterward that a few minutes of Q&A did little to give them any confidence that crypto voting machinery really works.
Another of the speakers, Neil McBurnett, was talking about doing variable sampling-rate audits (as a function of how close the tally is). Afterward, he lamented to me, privately, how hard it is to explain basic concepts like what it means for something to be “statistically significant.”
There’s a clear common theme here. How do we explain to the public the basic scientific theories that underly the problems that voting systems face? My written testimony (reused from an earlier hearing in Texas) includes links to papers, and some people will follow up. Others won’t. My big question is whether we have a research challenge to invent progressively simpler systems that still have the right security properties, or whether we have an education challenge to explain that a certain amount of complexity is worthwhile for the good properties that can be achieved. (Uglier question: is it a desirable goal to weaken the security properties in return for greater simplicity? What security properties would you sacrifice?)
Certainly, with our own VoteBox system, which uses a variation on Benaloh‘s voter-initiated ballot challenge mechanism, one of the big open questions is whether real voters, who just want to cast their votes and don’t care about the security mechanisms, will be tripped up by the extra question at the end that’s fundamental to the mechanism. We’re going to need to run human subject tests against these aspects of the machine design, and if they fail in practice, it’s going to be a trip back to the drawing board.
[Sidebar: I’m co-teaching a class on elections with Bob Stein (a political scientist) and Mike Byrne (a psychologist). The students are a mix of Rice undergrads, most of whom aren’t computer scientists. I experimentally built a lecture that began by teaching just enough number theory to explain how El Gamal cryptography works and how it allows for homomorphic vote tallying. Then I described how VoteBox uses this mechanism, and wrapped up with an explanation of how to do Benaloh-style challenges. I left out a lot of details, like how you generate large prime numbers, or how you construct NIZK proofs, but I seemed to have the class along with me for the lecture. If I can sell the idea of end-to-end cryptographic mechanisms to undergraduate non-science students, then there may yet be some hope.]
While I would love to embrace advances in voting technology, I have to admit that I think this is the wrong path. Taking the technology route ultimately means that we’ll have to engage in the techno/security arms race just to protect the integrity of the vote. And as arms races go, we’ll never really win — and in this case, we’ll never even really be sure that we’re winning on a vote-by-vote basis.
Take the issue of compromised silicon, for example. This scenario is probably less than a decade away, and it’s not clear how we’ll combat this (or even detect it). Why inject this type of uncertainty/doubt into our voting process? Let’s address the actual flaws in the cases where they exist and leave normal cases (the majority) alone — and on paper. Let’s continue to improve voting access for those with physical disabilities, and let’s continue to improve voting processes for overseas voters. Most importantly, let’s continue to improve the auditing process for vote counting, perhaps by providing webcasts of the hand-counting and tabulation process.
And even if you disagree with all of my points above, I think it’s important to provide voters with the option to vote Luddite-style. It’s simply not fair to force voters to submit to a process with known vulnerabilities. This isn’t an all-or-nothing proposition, is it? Let each voter decide!
Dan, thanks for this post. I LOVE being wrong in this fashion! I have historically been very skeptical of electronic voting systems, because of the coercion/vote selling possibilities, identity and privacy issues, etc. I was unaware of these newer protocols such as Benaloh’s and the VoteBox variation, however.
VERY impressive, after reading Benaloh’s paper, it does indeed appear allow the benefits of electronic voting while minimizing risks to incredibly low levels. In fact, the VoteBox vote broadcast tweak seems to me to be vastly superior to any other automated process, such as the optical-scan that people seem to be so fond of. Anyone who’s critical of VoteBox but trusts unauditable optical scan totals simply isn’t thinking through the process, IMO. As the VoteBox faq puts so well (I actually laughed out loud): “Q: I still don’t trust computers. I want hand-counted paper ballots. A: We’re not asking you to trust computers. We’re asking you to trust mathematics. It’s a significant difference.”
I suggest that people read the Benaloh paper (it’s only 8 pages, everyone), and the VoteBox FAQ. More than one of the criticisms I’ve read here simply aren’t valid; it appears people are arguing against some voting scheme idea in their head, rather than the actual protocols being suggested.
Barring some attack that hasn’t been presented yet, I’m thrilled to be able to flip my allegiance and become an advocate of (the right types of) electronic voting systems. You seriously made my night.
“Q: I still don’t trust computers. I want hand-counted paper ballots. A: We’re not asking you to trust computers. We’re asking you to trust mathematics. It’s a significant difference.”
Yes it’s a significant difference that almost all the readers of this site will understand. However the danger is that the general public and (more important) non-technical officialdom don’t really understand this difference.
OK so you sell them a good secure maths based system. However they don’t really understand why your system is good – you just persuaded them. Once they have got used to the idea that a system they don’t understand can be secure then someone else who is technically less competent but a better salesman than you will sell them an bad system off the back of your arguments.
For this reason we have to stick to systems that everyone understands – such as paper ballots.
I always thought it odd that in America – where there is really no hurry over the election – because the president doesn’t take office for a couple of months- you have pushed forward with mechanising the system whereas in the UK where the new government takes over immediately (usually the day after the election) we have stuck with paper and hand counting – mind you in the 2000 US election it looked like a case of more haste less speed…
There are no generic methods of proving the correctness of non-trivial software. Even a program that contains as few as 30 decision steps can contain more possible states than there are teaspoons of water in the Pacific Ocean. Combined with the potentials for not controlling physical machine access, OS failures, software modifications and switches, additional running daemons, hardware modifications, and untold new areas for chicanery by malefactors, these issues demonstrate that there is no possible means for assuring vote integrity.
Voting security is ever so more important than mundane financial controls. Yet no one has ever come up with a method for absolutely securing monetary transactions. And financial security is much easier to test than voting integrity for a number of reasons. Financial systems generally have complete control of the physical means of computing, and if not point of sales terminals, there is at least physical control of the critical junctures. Unlike voting systems, there are defined inputs to a financial system. Finally, much fraud in financial systems can be uncovered because there are usually any number of individuals who are affected by such theft. But in voting, no one really knows what the result should be, and the systems are only run once or twice a year.
One stirling example of fraud was the Chamblis-Cleland election where Cleland was way ahead of Chamblis in the polls up until the election, but Chamblis resoundingly beat Cleland. Was this electronic voting machine fraud, or merely polling error?
No one has demonstrated a viable argument that shows that an electronic system is more capable, useful or secure than the hand counted ballots in Canada that yield a result in four hours after the polls close, and has maximum integrity.
When the little light lights up green to say the system has worked all we actually KNOW is that the little light has lit up….
We may know that the little green light has lit up, but we don’t know that it actually means that the system has worked.
I remeber one of the staff (Ian Halliday) at Imperial College London – where I did my PhD used to say:
“If you can’t explain it to your grandmother then you don’t understand it”
So maybe we should avoid systems we can’t explain – because that means we don’t *really* understand them – and there may be vulnerabilities we haven’t noticed
In order to have third-party verifiability, then each (encrypted) ballot would need to have a unique identifier, and at any stage that accumulates ballots you’d have to have some system that could be queried (or monitored) by third parties to say “exactly which ballot ids have you included?”
End-to-end tracking from polling location to the central accumulation point would then be able to verify that all votes that had been cast were accumulated at the central registry (assuming that if a fake ballot with a given id is generated then *every* node — including third party nodes — would be able to detect that it’s a forgery). Then you could be reasonably confident that the network as a whole is secure. But you still have to implicitly trust the security of the central point (where the ballots are decrypted), since that process cannot be observed securely (if you make available the information that specific ballot ids have been processed together in realtime with the current totals, or if you provide the totals in realtime and the ballots are known to be processed in a certain order, then that totally kills privacy). You could have an aggregate at the end (all of these ids were accumulated), but you still have to trust the decryptor/accumulator to be adding them up properly. Still, I guess since it’s a smaller target it’s easier to protect.
Of course there also needs to be no way to link a particular ballot id with a particular voter (or small set of voters), which also gets tricky if the ballot ids can be monitored in realtime, and you have someone observing the polling place to see when particular people place their votes.
Dan Simon asks about whether crypto voting systems can address auditability. By themselves, no. But the crypto enables one very important property: it’s safe to broadcast encrypted ballots far and wide. Hook the precinct (one-way) to the Internet. Let the League of Women Voters and/or the political parties jack their own sniffers into the polling place networks. Make lots of copies. You can’t do that without ballots being safe to be observed, in order, in real time. That property would seem to require crypto.
Once you’ve got more people observing the real-time stream of ballots, the idealized “bulletin board” of ballots becomes realizable in the real world. It’s much easier for third-party auditors to say “hey, you forgot the ballots from precinct 207” because they collected their own copies.
Of course, each ballot can be conventionally signed, using standard public key crypto, making it somewhat harder for somebody to introduce fraudulent ballots, but doing this in the real world would probably require TPM chips or something else embedded into the voting machine motherboards which could do the signing operation without being easy for an attacker to use as a signing oracle.
For sure, ballots “discovered” weeks after the election will always be suspicious. Our research theory is that widespread, real-time, ballot replication can reduce the need for such late discovery. For most of the U.S. (with the possible exception of distant polls in Alaska), it’s safe to assume that you’ve got some amount of net connectivity, allowing for real-time ballot transmission back to election headquarters. Of course, if that connectivity goes down, everybody will see it, and the ballots could be delivered via courier.
1) I don’t think the issue is explaining crypto to ordinary voters. Even if they understood it, they wouldn’t understand the screens that display their votes, the sensors that record their votes, the chips that translate and transmit their votes in digital form, and so on. What matters to ordinary voters is not understanding the technology, but rather day-to-day familiarity and experience with its use. If similar technology ever gets adopted–perhaps after multiple less ambitious iterations–in less sensitive contexts such as payment or surveys, that will do much more to allay voter suspicion of the system than all the “crypto for dummies” tutorials in the world.
2) I haven’t looked into the auditability property you mention as a key feature, but I’m skeptical as to whether it solves the “missing Minnesota ballot” problem. Suppose something goes wrong, and a voter’s vote doesn’t show up in the public tally. (Perhaps the voter notices this right away, perhaps some time later.) How is the problem debugged? What if three hundred, or three thousand, voters notice at the same time? Who’s at fault? Would they have some kind of (perhaps digitally signed) receipt? What if they don’t receive one, or if it’s actually invalid, and they didn’t check–or they claim their validator didn’t work properly, and indicated that it was valid? Suppose they all do have valid receipts–wouldn’t we be right back in the Minnesota situation, with hundreds of votes suddenly “materializing” suspiciously long after the election? Isn’t the problem simply that “voting irregularities” are inevitably going to look suspicious, regardless of what technological (or legal or procedural) means is used to resolve them?
3) All the rest of your justifications for electronic voting look to me more like minor corner cases–reason for perhaps offering electronic voting as an alternative mechanism when a voter specifically requests it (perhaps with elaborate extra procedural precautions to ensure its correct functioning), but not for converting the whole system to electronic voting.
I have successfully (I think) explained the Mental Poker protocol to some fairly nontechnical people (my family), using the padlocks-and-boxes analogy (see the bottom of the first page and top of the second page of http://www.demillo.com/PDF/Protocols_for_Data_Security.pdf for this analogy).
Of course, the physical analogies are not perfect; for the padlocks-and-boxes version of Mental Poker, you have to assume the existence of boxes that can’t be subtly marked by one participant without the other participant noticing.
With respect to the question of whether this is a research challenge or an education challenge, I think that at the very least it is a research challenge. It may _also_ be an education challenge, but if there is a way to simplify the security system without sacrificing its security properties, that is a wholly beneficial goal. Simpler systems are better for other reasons, even if they don’t address the user-confidence question.
As far as educating users goes, I think that the field absolutely could make improvements in the practitioners’ ability to explain the concepts to the general public. But then, this is a statement that can be made about nearly every technical field. I guess with crypto/security this is perhaps a more important goal, because there’s this question of public policy that’s hard to address without popular support.
Perhaps one approach to the latter is to somehow turn the question into one of economics. That is, create an environment where systems that are good from a public policy perspective are also the ones that can generate the most income, cost the least, etc. Many other industries implicitly address these technical questions in that way; the consumers don’t really understand the technicalities, but they do comprehend the end results well enough to make winners and losers out of the competing technologies.
That solution is as non-trivial as any other effective one, but it may be the most efficient. And it seems to me that a person smart enough to have expert work knowledge of crypto is likely smart enough to figure out the economic side of things too. 🙂
All that said, I reject any notion one might have that crypto is simply unexplainable. IMHO, one of the surest signs of a true master of a topic is their ability to describe and explain the topic in a way that is understandable to lay persons. Not to say that the lay person could then know enough to work in the field, but that they would at least be able to make informed statements and reasonable decisions related to the field.
Mitch Golden asks the perfectly reasonable question: why do we need anything other than optical-scanned paper ballots? A couple answers:
– Accessibility. Computer systems have the potential to be more accessible to a broader spectrum of the population. Present-day DRE systems fail in a number of ways to live up to this promise, but the promise is still there.
– Overseas / remote voting. Fancier crypto voting systems make it safe to transmit ballots home from remote voting precincts (foreign embassies, military bases, etc.). Note that this is a world apart from “Internet voting”. Present-day fax-based systems effectively surrender anonymity for the remote voter. A crypto voting system would let all the world see that Joe the Soldier cast this specific (encrypted) ballot and that it was included in the tally, all without being able to learn who Joe actually voted for.
– Independent / transparent tallying. In Minnesota, we just learned of some ballots that were “lost.” When tabulated, they pushed the tally 50 votes closer to Franken from Coleman. In an end-to-end crypto voting system, all of the encrypted votes are posted for all the world to see. (In VoteBox, they’re posted in real-time, and election observers can even sniff the local network inside the polling place.) That gives outside observers far more power to audit that all of the proper ballots are included in the final tally. You would have fewer lost ballots. You would have zero chance of ballots being double-tabulated. You would have less chance of “test ballots” being included in the final tally.
Of course, while outsiders can accumulate the ballots, it takes the election administrator to decrypt the totals, but then anybody can validate that the plaintext and the ciphertext correspond to one another.
In short, there are plenty of valuable properties that we can legitimately argue would be valuable in real elections. Achieving those properties requires cryptographic mechanisms.
But we still have this: a box full of paper ballots is so bone-headedly simple that all the ways to cheat are obvious and can be guarded against. The more complex systems you describe sound good in theory – but if it were so simple to get such things to work I think that the record companies would have made a functioning DRM system by now!
As to the particulars:
*) Accessible: I don’t see why it would be difficult to make optical scan paper ballots accessible. For blind people who can’t see the paper ballot we have the obvious point that they also can’t see any display that is validating how they vote. It seems to me the accessibility problem is identical in the two situations.
*) Overseas: Are you suggesting that the crypto systems can be used at the voters’ homes? If not, if the voter has to go to a polling place, then I guess I am missing something. The paper ballot is still at the overseas voting precinct and can be recounted if need be.
*) Tallying: Can’t the issue of lost ballots be solved with a properly designed box? Isn’t that much simpler?
A question for you: as I understand it, all such systems will depend on there being a private key somewhere that is kept private. If it leaks, it will be possible to forge ballots. How can we guarantee (and know that it is guaranteed) that the private key hasn’t leaked?
“But we still have this: a box full of paper ballots is so bone-headedly simple that all the ways to cheat are obvious and can be guarded against. The more complex systems you describe sound good in theory – but…”
But the more they overthink the plumbing, the easier it is to stop up the drain.
I think that you are underestimating another requirement: that the system must not only be trustworthy, it must appear to be trustworthy to a non-technical user. I doubt that the crypotgraphic systems will ever be able to achieve this.
I have to say that I persist in being unpersuaded by the need for any of this. The original technology – paper ballots in a box – had many advantages over anything that has been used or proposed since. The optical scan, voter verified paper ballot systems solve the few outstanding problems of paper ballots in a box. Why do we need anything else?
One of the things you’re up against, of course, is decades of ostensible experts dispensing utter baloney in the guise of technical proofs that something is secure, or verifiable, or otherwise of acceptable quality. It’s probably best to view actual expert testimony as the beginning of a discussion rather a conclusion.