Verifiable Voting: A Primer
rcoh.me
rcoh.me
You need to allow each voter to cast multiple fake votes, otherwise the briber/coercer could simply demand receipts for a fake vote in addition to the real ones. Could get a bit unwieldy. But the big advantage is that there's no extra complexity for the average voter, since they don't need to cast any fake votes.
- Voter 1 votes for Harker
- Voter 2 votes for Harker, gets the same UUID. The machine casts a vote for Dracula instead
It could also cast any number of fake/counter votes without the voter knowing.
Some effort would be needed to create an actual proof that the coin flip protocol doesn’t allow the voter to generate any sort of proof that they participated in the coin flips. I think the usual schemes do have this property (at least, they do if the parties don’t collide), but I haven’t seen this specifically proven.
Then again, this is also a problem with existing methods isn't it?
What happens when some of the voters fail to produce the receipts? This seems inevitable even assuming good faith, but especially if it could be used to cast doubt on the legitimacy of the winning candidate (and it wouldn't even require voting against one's real preferences, given the existence of 'fake votes' in this system). Just deleting the unverified votes won't achieve much, if only a small subset are being tested.
- check in
- fill out a bubble sheet
- scan it
- declare vict'ry
Complex schemes are great intellectual exercises.
Just understand that perfection is unattainable.
We need enough automation for speedy reporting, without losing the secret ballot.
But the temptation to fetish technology past the point of diminishing returns, too, is a bugaboo.
KISS.
You fill in a bubble sheet, scan it, throw away half the ballot and take the other half as a receipt.
Later the user can prove their vote, but only to the election authority.
- a bad actor may lean on you about it
- recounts will be ridiculously costly
- a suitable ballot will be expensive to produce
When one considers all of the privacy/usability ramifications, just
- casting the ballot
- hearing a 'thunk' inside the DS200 machine
- having zero connecting information
. . .is more or less optimal.
> - a bad actor may lean on you about it
Except the scheme precludes it. Have you just not read this?
> - recounts will be ridiculously costly
This has some implications for recounts, but I don't think anything fatal or complicated.
> - a suitable ballot will be expensive to produce
The ballots I use currently have a perforated receipt, just not arranged in the way suggested. Yes, it may have slightly longer perforation, I guess...
Scheme or no scheme: if there is information, it will leak.
The stuff the voter keeps cannot be used to prove anything except that the voter's vote is in the count.
- This is a mathematically elegant approach, and the author is to be commended.
- The legal challenges impeding implementation would be staggering.
> "Each ballot has a randomized order – this means that a right-hand ballot alone can’t reveal who the vote was cast for."
This may be legally possible in some areas, but none with which I'm familiar. The ballot has to be known and printed weeks in advance of the election. The costs are already huge. Managing randomized hard-copy ballots is going to be a tough sell.
There's just a bit more afoot here than (admittedly splendid) abstract mathematical exercises.
Please understand: a large number of people want a printed, paper ballot. Excellent though the mathematical architecture may be, the fish don't want no bicycles.
And the same goes for the people helping conduct the election. The ones who have to help with counting. I would rather have anyone above the age of 18 be able to count the votes without trusting corporations or complex open source programs. Let the community leaders and volunteers in under privileged parts of the country be able to simply count the votes. Otherwise we shut them out.
Just my two cents. Well written post though.
I fail to see any form of discrimination here whatsoever. Voters don't have to understand anything about encryption, any more than today they understand how results get from their voting machine to the NYT home page in under an hour, which is just as much of a black box to most people.
And the trouble with people counting ballots, as always, is that it's error-prone (with recounts) and open to extreme manipulation to swing an election (as happens in many countries).
So a technological solution increases trust -- it doesn't decrease it.
And if you want to benefit voters from historically underprivileged backgrounds, well guess what -- election tampering is generally done to entrench a party or candidate in office for selfish gain, not the good of the country. And the poor and underprivileged are going to be the ones who suffer most from resulting police corruption, inflation, and economic mismanagement.
You can watch the box that the votes are put into, you can be present at the opening of the box, you can participate in the count. All the key parts of the process can (and in most countries do) happen in public view, and even someone with a low level of education can gain high confidence that the election is fair, trusting only other people like themselves - no need to trust the corporation that built the machine, or the politicians currently in power - you can watch it from empty box to published voting district results, and as long as you think there are people like you in each district doing similar checks, you can be confident the entire vote was done correctly.
I’m a reasonably intelligent software engineer and I would not trust myself to audit the described solution to know it does what it claims.
I can, however,
* review the receipt produced by the voting machine and ensure it matches * observe the random audits of submitted receipts to tabulated votes to be sure they match
I can also trust that a wide section of the public can do those things as well.
If you look up how elections get rigged, there are all sorts of opportunities for corrupting the election, which actually happen all over the world -- ballot boxes getting swapped out, literally stuffed with extra votes, being hidden and forgotten completely, getting "lost" or "accidentally destroyed" to prevent a recount along with forged results, the list goes on and on.
Yes the UN can send unbiased people to observe elections, but there just aren't enough to be present at every polling station and verify every step of the way. And the police tend to be happy to deny "unauthorized" people from observing... in the name of "security" to promote election integrity.
So considering that even official UN observers historically have been unable to verify the trustworthiness of many elections, I don't understand how you think "anyone who can count" could possibly do so.
You are right that ultimately it's based on trust, currently. But with technology we can have far greater certainty, and follow the phrase Reagan popularized: "trust, but verify". Elections deserve nothing less.
I'm describing elections where you can literally watch the box before it is sealed, to being opened, to having the votes counted and the count being published. If you're in a place where you are not able to do that, then yes, of course, you're running a high risk that the election is not fair.
You don't even need people to be unbiased, you just need a selection of people with different allegiances who will be able to cry foul if they see something happening that is not right because they think it will damage their side.
> But with technology we can have far greater certainty
I have yet to see any technological solution that gives greater certainty than the ballot box system. Most of them allow the voter to prove their vote or involve many more actors that must be trusted. They also provide new central points of attack, where a well run paper vote is very distributed.
I like Schneiers analysis of the papal election protocol: https://www.schneier.com/blog/archives/2005/04/hacking_the_p...
Except it's not, which is the whole point.
Half the country cries foul based on observational samples but without systemic proof, and the other half of the country says they're inventing stories and cherry-picking irregularities, and that there are just as many irregularities in the other direction to cancel them out.
And the average citizen, of course, has absolutely no idea what to think. Both sides sound entirely plausible. And even if there was manipulation, nobody has any idea if it changed the outcome by 0.1% (a few bad actors) or by 10% (the president directed it), if it was enough to tip an election or not.
By introducing foolproof technological verification, all this goes away. And I don't understand how you think this doesn't exist -- isn't this HN post just one example of multiple proposals?
Well, firstly, having some familiarity with software, it's rare to come across 'foolproof' used as an adjective, even with formally proved correct pieces of code.
But, I accept that it's possible that if implemented correctly, something like the most modern forms of things like Pret a Voter might be pretty secure. However, it's going to be harder for a normal human to check that Pret a Voter is implemented correctly than to check that a paper ballot system is implemented correctly.
For example, in Pret a Voter, the group of tellers and only the group of tellers have the ability to recover the original order. This would allow them to decrypt any of the posted receipts, if they shared that knowledge with someone nefarious, it provides perfect means for vote coercion. If the process is not run correctly and they are colluding, they could have the chance to choose a decryption that provides the right result.
If you implement Pret a Voter correctly, with a group of ideologically distinct tellers, and you involve them at the right points in the process, and not at other points, and you have a non-colluding auditor check they are doing their job correctly, then everything is fine, but in practice, how is a voter going to get that confidence?
This is ignoring very real usability concerns (that in some cases can be politically weaponized to disenfrancise particular segments of the population). https://www.usenix.org/system/files/conference/jets15/jets_0...
Ultimately, I find myself agreeing with Bruce Schneier. "The problem isn't the math, it's the human procedures around the math. I don't think a cryptographic voting system would be an improvement, because that's not the weakest link." https://www.schneier.com/blog/archives/2006/11/voting_techno...
That's good and all, but in the 4 states I've voted in, only one had a paper ballot. 3 were me showing up to the polling place and pressing buttons on a monitor. The 4th mails me a ballot, I fill things in, and send it back (so no receipt either).
Given my experience, and that several others tell me they do similar things, I don't understand your counter argument. We already do not have paper ballots to check. There is ZERO verification currently. If those ballots are printed out from the electronic machine that I voted on, well you still have to trust that a corporation did not mess with anything and printed out the wrong ballot, or just didn't print yours out. The way we are doing things and the way we used to do things don't enable the trust that you are suggesting.
But let's assume that the year is 2000 and we're voting on a paper ballot. We don't get to take a copy home. Once we leave we don't know what happens to that ballot in the box. Has our vote been counter? Did we fully punch out the paper chad? Did our ballot get lost when a country wide controversy started and my ballot got mailed around the state several times? Can I verify that the government's decision of how to count my vote reflected my actual intention?
The answer to these is that you can't do any verification of this. So I rather kinda like the idea of a website that I can go to and check that my vote was counted correctly and matches. The triviality of it from the voter side makes this process easy. Does it solve all verifiablity problems within the pipeline? No. Does it solve some? Yeah.
Personally I'd rather take a step forward, even if that step is small.
You are also able to volunteer to take part in the counting, or to observe the whole process. Sure, when you leave, you don't know that nothing bad happened, but you don't have to leave until the end of the process. In my jurisdiction, you can be part of the process that determines whether a vote is distinct (and should be voted) or not.
It sounds like you've already taken many steps backwards in your voting system, so this further step doesn't seem so bad, but it's still worse than a properly run paper system.
My voting system or the systems in the 4 states I've voted in? Which, I'll remind you, one uses paper ballots.
The year 2000 example I gave was literally what happened in Florida. Besides the chad part (which was a _MAJOR_ part of what I was suggesting as unverifiable), I'm also suggesting that given the close call there were many more opportunities for fowl play or accidents.
Really we don't care about verifiability in elections that went as expected. We care when they are close. Where mistakes make a difference. With thousands of ballots everywhere, it isn't hard for a few to get lost. Also, there were plenty of complaints about the ballot layout and how it confused people (Buchanan). You're also not going to be able to keep an eye on the ballots for 36 days (how long it took before the supreme court got involved).
Unless you have a receipt and a database you can easily access you can't really verify that your vote was counted. I'm not aware of any state that has this.
> it's still worse than a properly run paper system.
I also cannot think of a case where this is being done. I'll also note that according to this list[0], I voted with "Paper and DRE without paper trail", but I definitely did not vote on a piece of paper. I was put in front of a machine, so I'm not sure why this is called paper.
[0] https://ballotpedia.org/Voting_methods_and_equipment_by_stat...
The problem here is that many of these don't have the receipts (see link). And I'm guessing the other ones the receipts are upon request, so I don't know if it is obvious for users to print them out. And that still doesn't solve the problem of a lack of a easy to access database to check your ballot.
I strongly recommend people volunteer for their next election cycle to see this stuff firsthand. You'll definitely have better "this is how the election will be stolen" stories to tell than this mixnet verification stuff. At this point, I'm automatically skeptical of any story, positive or negative, about election security that doesn't include the word "pollbook".
With a paper ballot, you can.
1. in the morning, the ballot box is shown to be empty and is then locked.
2. during the day, voters leave their paper ballots in the box.
3. in the evening, the box is opened, and all the ballots inside it are counted.
The entire process is public, and the ballot box never leaves the public eye. So you can verify that your vote went into the box, and that all votes in the box were counted.
If you have strong opinions about how elections should be run, the best advice I've seen is Matt Blaze's: volunteer to be an election judge in your district, to get firsthand experience.
I don't understand this argument. From my understanding the computers (I'm not using algorithmic counting because that's not a distinct enough word. By hand you're still doing an algorithm) are already counting and the paper is a backup. If we can still count up all the ballots after and have a verifiable method, then I don't see anything lost.
You can watch the box that the votes are put into, you can be present at the opening of the box...
It's happened numerous times in the Bay Area that boxes of ballots have been "found" days after an election, with votes curiously inconsistent with others from nearby precincts.
I've updated the post in a few places to help clarify this.
Especially because most people can understand at a visceral level why all paper ballots are fair, why over complicate what isn't broken?
But let's say the Input->Output is reproducible all the time with no chain between the voter and the result. You /still/ have no way to ensure that the checkbox corresponded with the name, and that you cast the vote you think you did. Perhaps this is outside the scope of the article, but its a fairly glaring deficiency.
Perhaps I'm misunderstanding. But all you can tell with this system is that "your" ballot went into the magic box and a (presumably reproducible) result came out the other side.
You can't know which final ballot was your vote, but you can know that your ballot was in the mix coming in, and that the mix going out wasn't altered (within some probabilistic bounds).
I think this is the part I don't understand. Partly because I don't know anything about mixnets, and it feels like its paradoxical. But if that's how it is, then I can accept it.
Well the voter can verify if the voting machine is acting honestly by querying the salt used for encryption (refer to "How do you know your ballot was properly constructed?"). From an adversarial voting machine's perspective the chances of the voter validating the ballot is 0.5 and given the sensitivity of the elections, I'd imagine even one incident of foul play spreading like wildfire to raise alarms
This is not true. Scantegrity was an excellent voting system implemented in a real, binding US election. It is also (relatively) easy to use and requires little modification to a traditional ballot-based voting system.
https://www.chaum.com/publications/Scantegrity-II-Municipal-...
...and a good argument as to why paper ballots are still the best known voting system. Every other proposed solution is too complex.
This confuses me. Is it difficult to shuffle the paper ballots without changing votes? Are we concerned that the ink my be moved from one circle to another circle or something?
If we just directly decrypted them and published the results, they would allow someone to prove who they had voted for.
So instead, we shuffle them to anonymise them, then decrypt them to avoid being able to link an encrypted input vote to an output vote.
In a chad-based system though, the vote might actually change as the ballot was being physically handled.
A 3rd party could verify each person then sign each vote but then that 3rd party can mint valid votes. And if you have a trusted 3rd party then why do you need a complicated voting system?
At this point, paper ballots, and human processes are the best hope in America.
Doesn't account for the data leaks caused by ballot processing, which eliminate the secret ballot.
With paper ballots cast at poll sites, voters sign prior to being issued a ballot. This order is preserved (in the elections I'm familiar with). With the Australian Ballot, dropping the ballot into the box is the secure one-way hash which (mostly) anonymizes the ballots.
With postal ballots, even more care is required. Returned ballots arrive in bins. So its very likely that your ballot is the only one from your precinct in that bin. Making it trivial to tie that ballot back to you. The mitigation is to sort ballots by precinct prior to processing. Which is not easy or feasible, because ballots are generally processed as they arrive. This loss of secrecy is quite surprising to first time observers to how an election board works to certify elections.
--
Source: Burned out election integrity activist. I actually got some minor laws and procedures changed. Plus poll worker, judge, observer for about a decade. It took me forever to get up to speed on election administration and I'd say I know maybe 20% of what I'd need to know to do the job. There are so many nooks and crannies, and it's always changing, and every where has its own quirks. Meaning election administration is surprisingly difficult and arcane. So it's very hard to have casual constructive conversations about this stuff.
--
PS- Chewing on this article a bit more more. Two things.
#1
Huge shout out for this point:
"5) The salt is crucial for ballot secrecy – since there a finite number of permutations of the ballot, without it, an adversary could determine the contents of a vote simply by enumerating possible ballot permutations and matching the resulting cipher texts."
THANK YOU!
This is so hard to explain. Especially to crypto advocates.
Back when I studied the available crypto voting systems, manually simulating a real world election, I stumbled upon this realization.
Any one advocating a new voting system HAS to clearly state the operating parameters, assumptions. Number of voters, precincts, contests per ballot, etc. And be very clear for when their system NO LONGER WORKS.
#2
This article does mention shuffling. I'll admit that I haven't followed the advances this last decade. I'd want to verify that "shuffling" is one-way (irreversible) and not simply hashing (hash collisions).
No one will be happier if someone figured out how to preserve private voting, public counting (Australian Ballot).