Making Elections Safe
A new proof that MAJORITY is not in 
|
| [ Rich DeMillo ] |
Rich DeMillo is a strong leader, a famous researcher, and a long-time best friend. Proof: He was the first CTO at HP and was the Dean of Computing at Georgia Tech; He helped created mutation a powerful software testing method and did seminal work in complexity theory. The last is clear.
Today I want to talk about his recent work on voting systems.
The 2020 election is over a year away, yet it is on our collective minds. People voice concerns everyday on social media, on TV, on cable, in print, everywhere. Their concerns are that our next national election will be compromised. Rich has turned his concern into activism: he is working hard to make elections trusted in general and the 2020 election in particular.
Rich is scheduled to give a talk this coming Monday, May 13, at Georgia Tech. I wish I could be there, but cannot. I do plan to watch the video of his presentation—see here. The talk is based on his recent paper joint with Andrew Appel and Philip Stark titled, “Ballot-Marking devices (BMDs) cannot assure the will of the voters.” As an aside, their paper (ADS) has already generated measurable interest—it’s been downloaded over 
What Makes A Good Election?
There are several criterion that a “good” election should have.
- During the voting: Only eligible voters can vote.
- During the tabulation: Each voter gets exactly one vote.
- After the election: Each vote remains secret.
Rich says in his talk abstract:
Many people believe that, in an Internet-enabled world, secure, safe voting should be easy to achieve. For example, using known cryptographically secure protocols (maybe even blockchains), a secure website might be developed to relieve voters of the burden of driving to a polling place on election day.
This belief is wrong. Elections are hard—impossible?—to safeguard. A U.S. national election is the union of about ten thousand local elections. Each has different rules and protocols, which makes safeguarding the national election difficult.
- During the voting: Who votes is subject to human decisions? People must prove they are eligible voters. Even computer identification is subject to bias.
- During the tabulation: Counting is usually a combination of human and computer systems. The former make errors and as do the latter. Computers can have bugs or can be hacked by adversaries.
- After the election: Since records are usually kept of the voting, they must be safeguarded to avoid disclosing how someone voted.
The last point is central. There must be a record of the votes to allow audits after the election is over. We must be able to audit and check that the tabulation was correct. This is the central question that Rich and his co-authors discuss. We will turn to this issue in a moment.
Before that I note that keeping a vote secret is impossible in an absolute sense. Suppose that you vote “yes” in some district. After the election suppose that the count in that district is made public, as it usually is. Say 
How Are Votes Recorded?
There are two main ways to record votes. One method is to have voters hand-mark their ballots, in the old-fashioned way. It is simple, cheap, and not 21st century. Hand-marked ballots can be read by automatic scanners, at least in principle. A difficulty is voters are human and may mark their ballots incorrectly. They may miss a box, or mark two boxes, or make some other mistake. What if the voter is instructed to:
Select two of the following six choices.
There can be other difficulties: Some voters may have special needs and may require instructions to be in a large type font, for example.
Another recoding method is to have voters use a device to print their paper ballots. These are cleverly called Ballot Marking Devices (BMDs). The name sounds slightly strange to me; there is an alternative name, electronic ballot markers (EBMs).
The authors, ADS, argue that BMDs are dangerous. Such devices can fail, they argue, and not protect the election. The BMDs rely on software, complex special purpose software, and thus are subject to bugs, errors, mistakes, and to active attacks by adversaries.
A BMD device takes input from a voter and then prints out a paper ballot. Often the ballot will contain a machine-readable bar code. This is so scanners can more easily read the paper ballots, later. The problem, the danger, is that most voters cannot tell if a bar code is correct or not. An attacker need only have the BMD confirm that you voted say “yes” and print a ballot that says “yes”. Then the attacker has the BMD cheat you by printing a bar code that says “no”. This is a nasty attack, which is hard to stop. The ADS team discusses this and related problems with BDMs.
Mathematics and Voting
Can complexity theory help us design better elections? Unclear. Can election theory help us understand complexity theory? Perhaps.
Elections Inform Complexity Theory
Theorem 1 The Election Hardness Axiom implies that the MAJORITY function cannot be computed by a polynomial size constant depth Boolean circuit of NOT, AND, and OR gates.
That is, the MAJORITY function is not in 
Okay we are kidding. But not completely. Suppose that MAJORITY function were in
The tabulators have looked at the following ballots
and we agree that there is a “yes” vote in ballot
.
Complexity Informs Elections
Rich, in his talk abstract, states that it is unlikely that crypto theory could be used to create trusted elections. His reason is voters will not trust elections that rely on crypto results. I agree. But I wonder if ideas from theory could be useful. Here are two high-level thoughts.
Open Problems
Can we elections be trusted? Can we formalize the connection between election and
In my country we have electronic voting: https://en.wikipedia.org/wiki/Electronic_voting_in_Brazil
Dear Alexandre:
Thanks for this pointer. My understanding is that there are some critics of the system. The machines used, I believe, do not have a paper trail as in BMDs. But the voting system may indeed have much to recommend itself. Perhaps the key is that no voting system is perfect and all systems have some issues.
Best
There are sound cryptographic voting protocols, like Helios or Belenios:
http://www.belenios.org/documentation.html
The idea is: the votes are encrypted using an homographic encryption (typically based on DLP), then they are tallied (with a Zero-Knowledge proof of correctness) supplied, and then the tally is decrypted (with a ZK proof too). So the result is garanteed to be correct (if the underlying crypto tools are not broken of course).
Privacy is provided by the fact that the decryption key is shared (typically via Shamir’s secret sharing). So if only one of the trustee is honest, and only accept to decrypt the tally but not the individual votes, then privacy is assured. But this part require the honesty of at least one of the trustee, it cannot be assured just from the protocol.
Of course using thus a protocol for important national elections is another question: personal computers are too easy to tamper with… But this is useful for local elections, we use it at our university.
Dear Damien Robert:
Thanks for this comment. The point of the ADS paper is that computers cannot be trusted. It is a basic assumption in crypto that we can make implementations correct. It is reasonable in many settings, but not so clear for elections. The whole open problem is can we avoid trusting computers?
Best
In cryptographic elections the zero-knowledge proofs are required to be publicly verifiable, which in particular means that anyone can write their own verifier on their preferred platform.
There is no need to put any trust in the prover, just in the existence of one properly implemented verifier, and these verifiers are typically very simple programs.
Is it too much to assume that at least one of them will be properly implemented?
Dear Alan Rosen:
Yes it is too much to assume for many. The verifiers can be assumed to be correct programs. But they cannot assume to not be attacked by adversaries. So when the elections is being tabulated the verifiers could be infected. This is the core issue. This is why people are nervous about such methods. This is what the authors ADS and others are worried about.
Best
The whole point of zero-knowledge proofs, and what seems to confuse many people that are used to the “traditional” viewpoint of security, is that you do not care whether the tabulation process was “infected”. What you care about (and verify) is that the input/output relation of the computation is proper.
In this context it is not clear what “verifiers could be infected” even means. The tabulation is not performed by them anyway, and they can run at any time after the tabulation is done. In principle there could be as many verifiers as you wish, and it is not like a verifier is an entity that can be so easily attacked/”infected” (in particular, it can be offline).
Note that each party could implement a verifier of their own on any platform they choose to trust, just like any of us can choose our own doctor to which we entrust our health.
That being said, I would be the first to agree that paper trail is necessary for elections. It is just that the argument that the authors make (as described by you) does not strike me as very strong.
A downside to the conclusion of their abstract is that it makes the ballots of people with disabilities easier to identify.
Dear Tomboktu:
Thanks for your comment. The basic point, I feel, is that there is no perfect way to protect all information in elections.
Perhaps the best we can do is try and make the elections fair.
Best
There is a different way you can look at a good election, which I think is roughly what is intended in Australia. Instead of trying to prevent people from voting fraudulently, you have systems in place to be able to detect that fraud. If there is enough voter fraud that the result of the election could be incorrect, then you just redo the election (or the part of the election that needs redoing).
We have something roughly like this:
1) Mandatory voter attendance (all people over 18 must register to vote, and on voting day they need to have their name marked off or face a fine)
2) To vote, you say your name and address, and your name is marked off the roll, you are then given voting paper (at this point you are also asked if you have already voted elsewhere, if you say yes then you are sent away)
3) You do your voting (or leave the paper blank) and put it in the box
4) Votes are counted in the open with representatives of parties typically supervising
After the election, if the number of people voting multiple times is so large that it could change the result, then this is a sufficient condition to just redo the election.
I’m not familiar with the measures needed for preventing people from enrolling fake people on the register, but it seems like it would be tricky to do, since they need to have an address (which coupled with the fact that every adult is required to be registered means there aren’t many good hiding spots).
No one needs to provide ID. The system is simple enough that anyone can observe it and see it working (even if you had fancy maths to solve it, I’m not sure it would convince most people that their vote was actually counted), and you can’t be identified.
Dear Andy:
Thanks for the thoughtful comment. I am not sure this method would work here in the U.S. It is an interesting type of election process, however. The idea that a “redo” is used to handle problems in the voting seems fine for some places. I do not see it working everywhere.
Best
I guess it is marginally interesting from an algorithmic perspective because I think it means that the algorithm isn’t guaranteed to terminate (unless your “algorithm” also involves some means for preventing the same type of fraud between redos).
In practice, I don’t think we have ever (?) needed to do such a redo – presumably because anyone wanting to try such fraud would realise that the probability of success is minor, but the risk of getting caught is large.
I think the election process in the US is too political, which makes any changes to it very difficult, because any change will either be expected to make no difference to the outcome (in which case, no one cares) or expected to give one party an advantage (in which case, the other party will fight). I don’t have any great ideas on how to set this up (how do you convince the population that an independent/non-partisan group is truly independent and non-partisan?) but to me that seems like the most obvious first step required (and still suffers from the same problem that whichever group feels like they will be disadvantaged by “fairer” elections will fight it).
Dear Andy:
Thanks again. The idea of an independent and trusted group is like in crypto assuming a trusted party. The usual assumption is that we would prefer to avoid trusted groups. Not sure how to do that here.
Best
The assumption based on with EHA (Election Hardness Assumption) is based on is flawed. Proof Clinton lost with majority of vote.
Dear L:
Not sure what you mean here? The fact that one can lose in U.S. with majority is based on the fact that we have a more complex rule than majority. The rule uses majority for each state and then takes a weighted threshold.
Please help explain what you mean.
Best
“Suppose that MAJORITY function were in {\mathsf{AC}^{0}}. Then a series of decisions of the form:
The tabulators have looked at the following ballots {B_{1},\dots,B_{m}} and we agree that there is a “yes” vote in ballot {B_{i}}.”
I don’t follow what you mean by this. It feels like it’s missing a sentence… although I haven’t yet learned the proof that majority is not in $AC^0$, so maybe I’m missing some knowledge that would make your meaning clear.