15 ms·

Verifiable Voting: A Primer

74 points by rusbus 7y ago

amflare 7y ago
I still don't get it. The ballot is effectively a pivot between the voter and the result. You can't just disconnect this without sacrificing the integrity of the system. If you scramble it so that the vote and the ballot are disconnected, there is no way to prove the results are valid. And if you disconnect the voter from the ballot, you can make up all the votes you want. 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.
- rusbus 7y ago
  I think you're saying that you don't understand how mixnets guarantee integrity -- if that's incorrect, I apologize. Mixnets allow you to verify that the data in is _identical_ to data out (modulo the salts) that serve an anonymize the data. It isn't just reproducible, but verifiable. The results coming out the other end are the final decrypted ballots which anyone can count and verify the totals. 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).
  - amflare 7y ago
    > Mixnets allow you to verify that the data in is _identical_ to data out (modulo the salts) to make it so that data an anonymized. 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.
  - hencq 7y ago
    Not OP, but that helped me at least, so thank you. The description of the mixnet seems a bit similar to the way Tor anonymizes where requests come. What I'm not clear on is how a voter can know that the mixnet is working correctly. I.e. I understand how the voter can verify that their second bubble from the top was recorded, but can they also verify that that was correctly counted as a vote for John Jackson?
- gnarula 7y ago
  > You /still/ have no way to ensure that the checkbox corresponded with the name, and that you cast the vote you think you did 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
vowelless 7y ago
This primer misses the point that elections should be easy to participate in. The voters should need the ability or knowledge about encryption to participate. Otherwise it discriminated against voters from many historically underprivileged backgrounds. 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.
- crazygringo 7y ago
  Huh? For the voter, this is literally the exact same as it is today -- fill in bubbles -- except that they also give you a copy of half your ballot, which you can simply toss if you're not personally interested in verifying election integrity. 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.
  - kybernetikos 7y ago
    With paper ballots it's easy for anyone to get involved in verifying the trustworthiness of part of an election. 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.
Buttons840 7y ago
> Next, we need to actually count the ballots in a way that can be verified. The key idea is that the ballots are shuffled in a way that we can be sure that no individual vote has been changed, but we don’t know which input vote corresponds to which output vote.... 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?
- rusbus 7y ago
  The encrypted ballots are all public and it isn't assumed they they're anonymous (eg. it's safe to post a picture of your RHS ballot on Facebook). 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.
- deleted 7y ago
  [deleted]
- singron 7y ago
  A more sensical analogy in paper ballots might be replacing a ballot. E.g. a counter scoops up some ballots into one sleeve and dumps some from the other while shuffling them around. In a chad-based system though, the vote might actually change as the ballot was being physically handled.
maxfan8 7y ago
> There several different verifiable voting systems that have been conceived of – I’ll be describing a system called Prêt à Voter (the only one, to my knowledge, that’s been used in a real election). 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-Election-at-Takoma-Park-the-first-E2E-Binding-Governmental-Election-with-Ballot-Privacy.pdf https://www.chaum.com/publications/Scantegrity-II-Municipal-...
- rusbus 7y ago
  Thanks! I've added a reference to Scantegrity to the post. Interestingly, Scantegrity is just a front-end -- you still need something like mixnets to actually count the votes.
honoredb 7y ago
This is a nice explanation and a cool solution. I amused myself a bit ago by trying to come up with a solution for these two constraints without reading about the crypto work, and ended up with something different. In my scheme, a voter casts a vote for a candidate and gets a receipt with the UUID of the vote, which is simply mapped to the candidate so that they can verify it online later. However, the voter can also cast any number of additional ballots, which are constrained by the system to be pairs of votes and anti-votes, each for the same candidate, and get receipts for each. For example, I support Harker, but I've been paid to vote for Dracula. I go into the voting booth and cast my vote for Harker, getting Receipt 1. Then I press an extra button to cast a fake vote for Dracula, and get Receipts 2 and 3, with 3 being a special negative ballot. I can show Receipt 2 to my briber, who can verify that it corresponds to a vote for Dracula. But secretly, I can use Receipt 1 to check that my vote for Harker was counted correctly, and Receipt 3 to see that a negative vote was also cast for Dracula, cancelling out my bribed vote. 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.
- IshKebab 7y ago
  That's pretty clever.
- fooyc 7y ago
  The machine could give the same UUID to different voters: - 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.
  - deegles 7y ago
    You make the ID be a hash of a UUID and the voter’s name.
    - amluto 7y ago
specialist 7y ago
Quickly scanned article. 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).
KerrickStaley 7y ago
How does this system protect against ballot stuffing? It seems to have a mechanism for voters to verify that their ballots were counted, but no mechanism for the public to verify that counted ballots correspond to real voters.
- Spivak 7y ago
  I don’t think any cryptographic system can actually accomplish this because the problem spills into meatspace. 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?
ryanobjc 7y ago
Election security should be transparently understandable to nearly everyone or else there'll be mistrust in the system. At this point, paper ballots, and human processes are the best hope in America.
nemetroid 7y ago
A nice article with a great sense of when to hand-wave (and to acknowledge that hand-waviness)... ...and a good argument as to why paper ballots are still the best known voting system. Every other proposed solution is too complex.
smitty1e 7y ago
Locally, where I serve as an election officer, we - 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.
- mlyle 7y ago
  I like this scheme because it's a similar complexity to existing voting protocols at the polling place. 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.
  - smitty1e 7y ago
    You may not want to leave the polling place with any physical evidence of how you voted. - 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.
    - mlyle 7y ago
      > You may not want to leave the polling place with any physical evidence of how you voted. > - 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...
      - smitty1e 7y ago
        > Except the scheme precludes it. Have you just not read this? Scheme or no scheme: if there is information, it will leak.

74 points by rusbus 7y ago

I still don't get it. The ballot is effectively a pivot between the voter and the result. You can't just disconnect this without sacrificing the integrity of the system. If you scramble it so that the vote and the ballot are disconnected, there is no way to prove the results are valid. And if you disconnect the voter from the ballot, you can make up all the votes you want. 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.

rusbus 7y ago
I think you're saying that you don't understand how mixnets guarantee integrity -- if that's incorrect, I apologize. Mixnets allow you to verify that the data in is _identical_ to data out (modulo the salts) that serve an anonymize the data. It isn't just reproducible, but verifiable. The results coming out the other end are the final decrypted ballots which anyone can count and verify the totals. 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).
- amflare 7y ago
  > Mixnets allow you to verify that the data in is _identical_ to data out (modulo the salts) to make it so that data an anonymized. 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.
- hencq 7y ago
  Not OP, but that helped me at least, so thank you. The description of the mixnet seems a bit similar to the way Tor anonymizes where requests come. What I'm not clear on is how a voter can know that the mixnet is working correctly. I.e. I understand how the voter can verify that their second bubble from the top was recorded, but can they also verify that that was correctly counted as a vote for John Jackson?
gnarula 7y ago
> You /still/ have no way to ensure that the checkbox corresponded with the name, and that you cast the vote you think you did 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

vowelless 7y ago

This primer misses the point that elections should be easy to participate in. The voters should need the ability or knowledge about encryption to participate. Otherwise it discriminated against voters from many historically underprivileged backgrounds. 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.

crazygringo 7y ago
Huh? For the voter, this is literally the exact same as it is today -- fill in bubbles -- except that they also give you a copy of half your ballot, which you can simply toss if you're not personally interested in verifying election integrity. 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.
- kybernetikos 7y ago
  With paper ballots it's easy for anyone to get involved in verifying the trustworthiness of part of an election. 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.

Buttons840 7y ago

> Next, we need to actually count the ballots in a way that can be verified. The key idea is that the ballots are shuffled in a way that we can be sure that no individual vote has been changed, but we don’t know which input vote corresponds to which output vote.... 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?

rusbus 7y ago
The encrypted ballots are all public and it isn't assumed they they're anonymous (eg. it's safe to post a picture of your RHS ballot on Facebook). 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.
deleted 7y ago
[deleted]
singron 7y ago
A more sensical analogy in paper ballots might be replacing a ballot. E.g. a counter scoops up some ballots into one sleeve and dumps some from the other while shuffling them around. In a chad-based system though, the vote might actually change as the ballot was being physically handled.

maxfan8 7y ago

> There several different verifiable voting systems that have been conceived of – I’ll be describing a system called Prêt à Voter (the only one, to my knowledge, that’s been used in a real election). 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-Election-at-Takoma-Park-the-first-E2E-Binding-Governmental-Election-with-Ballot-Privacy.pdf https://www.chaum.com/publications/Scantegrity-II-Municipal-...

rusbus 7y ago
Thanks! I've added a reference to Scantegrity to the post. Interestingly, Scantegrity is just a front-end -- you still need something like mixnets to actually count the votes.

honoredb 7y ago

This is a nice explanation and a cool solution. I amused myself a bit ago by trying to come up with a solution for these two constraints without reading about the crypto work, and ended up with something different. In my scheme, a voter casts a vote for a candidate and gets a receipt with the UUID of the vote, which is simply mapped to the candidate so that they can verify it online later. However, the voter can also cast any number of additional ballots, which are constrained by the system to be pairs of votes and anti-votes, each for the same candidate, and get receipts for each. For example, I support Harker, but I've been paid to vote for Dracula. I go into the voting booth and cast my vote for Harker, getting Receipt 1. Then I press an extra button to cast a fake vote for Dracula, and get Receipts 2 and 3, with 3 being a special negative ballot. I can show Receipt 2 to my briber, who can verify that it corresponds to a vote for Dracula. But secretly, I can use Receipt 1 to check that my vote for Harker was counted correctly, and Receipt 3 to see that a negative vote was also cast for Dracula, cancelling out my bribed vote. 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.

IshKebab 7y ago
That's pretty clever.
fooyc 7y ago
The machine could give the same UUID to different voters: - 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.
- deegles 7y ago
  You make the ID be a hash of a UUID and the voter’s name.
  - amluto 7y ago

specialist 7y ago

Quickly scanned article. 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).

KerrickStaley 7y ago

How does this system protect against ballot stuffing? It seems to have a mechanism for voters to verify that their ballots were counted, but no mechanism for the public to verify that counted ballots correspond to real voters.

Spivak 7y ago
I don’t think any cryptographic system can actually accomplish this because the problem spills into meatspace. 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?

ryanobjc 7y ago

Election security should be transparently understandable to nearly everyone or else there'll be mistrust in the system. At this point, paper ballots, and human processes are the best hope in America.

nemetroid 7y ago

A nice article with a great sense of when to hand-wave (and to acknowledge that hand-waviness)... ...and a good argument as to why paper ballots are still the best known voting system. Every other proposed solution is too complex.

smitty1e 7y ago

Locally, where I serve as an election officer, we - 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.

mlyle 7y ago
I like this scheme because it's a similar complexity to existing voting protocols at the polling place. 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.
- smitty1e 7y ago
  You may not want to leave the polling place with any physical evidence of how you voted. - 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.
  - mlyle 7y ago
    > You may not want to leave the polling place with any physical evidence of how you voted. > - 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...
    - smitty1e 7y ago
      > Except the scheme precludes it. Have you just not read this? Scheme or no scheme: if there is information, it will leak.