7 ms·

Maybe this is a dumb idea, but what if for each election we issued a ballot containing a unique, random, sequential prime number to every registered voter? The

by pgt 6y ago

Maybe this is a dumb idea, but what if for each election we issued a ballot containing a unique, random, sequential prime number to every registered voter? Then, when counting the votes for each candidate we display the running product of all the primes counted for that candidate as a "checksum", or "check product". This retains privacy while allowing individual voters to easily verify that their vote was counted by simply dividing their party's checksum by their prime ballot number and confirming that it is a factor of the check product. By displaying a running product of votes, you can also verify that your vote was not counted before you voted. Additionally, this prevents double counting because the "checksum" for N primes must match exactly N votes and no two candidates can share a factor. By issuing sequences of primes to certain regions, you can get some metrics by state. Then you institute a rule that if some % of primes dispute that theirs was counted correctly, a recount is automatically triggered.

luckylion 6y ago
It allows for verification not only by the voter but also by third parties, doesn't it? That would make it possibly to sell votes (with proof!) or threaten people with repercussions unless they vote a certain way.
- compsciphd 6y ago
  what's a bigger threat. "selling votes" or unverifiable election. i.e. we generally say election fraud is not a huge problem because its too easy to get caught. if that's the case, one would think any vote buying scheme would be even easier to get caught.
  - Ekaros 6y ago
    Or coercion. If at any point your vote can be known, there is very high risk that someone forces you to vote like they want. Only way to prevent this is total anonymity of which vote was by which person.
    - compsciphd 6y ago
      is coercion really a threat on a large scale in the US (I'm sure in other countries it is). But if the onl way to know my vote is to have my random identifier, if I dispose of my random identifier, they can't know my vote. i.e. I feel we can both have total anonymity if a person desires, while also having verifiability. as an example: a random uuid is assigned to me and my votes are printed out on a slip of paper with the uuid (and with a cryptographic signature to verify that it was produced by a voting machine). I can choose to burn the paper and no one can know how I voted or I can keep the paper and anonymously verify that my vote was recorded correctly (i.e. download the whole set of uuid -> vote mappings). if the number of uuids submitted at each polling place is recorded reliably (i.e. observers from multiple sides having agreed upon counts), you have a good belief that no votes were added or removed. if every voter who chose to keep their slip is able to verify their vote is recorded correctly you have a good belief that the votes weren't manipulated (assuming enough people verify their votes). yes, there are issues, vote buying / coercion, but I'm just not convinced that those issues are severe enough or probable enough (at least in the USA) to want to avoid simple steps that will make people more comfortable with the election outcomes. i.e. make the punishments harsh enough for anyone caught coercing / paying others for their votes to make it unlikely to happen at a scale that will negatively impact things. but perhaps I'm naive about this.
      - pwg 6y ago
        > is coercion really a threat on a large scale in the US No, largely because of the secret vote and the fact that there is no way anyone can verify how "you" voted after the fact. So you can lie to the thug threatening you with a wrench that you voted for "candidate A" and the thug has no way to know otherwise. > But if the onl way to know my vote is to have my random identifier, if I dispose of my random identifier, they can't know my vote. If the thug with the wrench who has /suggested/ you vote for candidate A lest he break your kneecaps also knows you can verify your vote by using your random identifier, then if after the election you have disposed of your random identifier, the thug breaks your kneecaps because you disposed of your random identifier. Therefore you are still coerced to reveal your vote, because you are also coerced not to dispose of your random identifier until after the thug has verified you voted "the proper way". I.e. the thug changes tactics from "vote for A lest I break your kneecaps" to "vote for A and do not dispose of your identifier until I verify you voted my way lest I break your kneecaps". > I feel we can both have total anonymity if a person desires, while also having verifiability. If there is any form of ability to verify your actual individual vote, in any way, then there is no anonymity. Anonymity is only available if there is no ability to verify an individual voted a particular way after the fact. Any opening of verification destroys all anonymity.
- deleted 6y ago
  [deleted]
- pgt 6y ago
  This is only a risk if ballots are not issued privately.
  - lentil_soup 6y ago
    That is a great system, but there could still be coarcion to show your "prime number" token to someone, say your employer. Probably not common in the US or the EU, but in Venezuela for example there is a lot of pressure for employees of state owned companies to vote for the government and they use many tactics to make sure you do. I'd be worried about making it simpler for them. Maybe there's a way of addding an extra layer of security?
- sebmellen 6y ago
  If you see my above comment on a "Right to Vote" token system, which would abstract away the identity of any given vote, there is a solution for this: Because the Right to Vote tokens and the accounts that they are voted with by are anonymous, no third-party knows which vote belongs to which person (except for arbitrary public-key strings). However, if a voter wants to check that their vote was counted, they can easily see that the token sent from their account was used to vote for a certain party. Now, if a second layer of privacy and abstraction is needed, zero-knowledge proofs can offer that. This, however, is a completely different ball game.
Znafon 6y ago
What is a unique, random, sequential prime and how do you actually vote?
- pgt 6y ago
  Issue 1, 3, 5, 7, 11, 13, 17... up to N for N registered voters. Mix them up and hand out randomly. So let's say you get 5 and I get 7. To vote, you cast your prime for a candidate, thereby consuming it. No two candidates can share a prime, because their checksums will have a common factor, which is not allowed. If we both vote for candidate A, his checkproduct is now 35. If ballots 11, 13 and 17 vote for candidate B, his checkproduct is 2431. Because 2431/5 = 486.2 (non-integer), you can verify that your vote was not counted for B, but it was for A, because 35/5 = 7 (an integer). And because 2431 and 35 don't share any factors, no two votes were counted twice.
  - kevincox 6y ago
    Why do you need primes? You could just give everyone a number and publish which numbers voted for each candidate. That is effectively equivalent to what you are doing since each total product can be factored into the primes that voted for it anyways.
  - gspr 6y ago
    In this system you have to trust that the issuing authority never reuses primes. That seeems like a major downside, and something that is hard to overcome with transparency.
    - klyrs 6y ago
      People would definitely notice if the checkproduct for two candidates had a nontrivial gcd. Which is almost guaranteed to happen if primes are recycled to a significant degree.
  - Znafon 6y ago
    It doesn't work: let's take 4 people and they vote for two choices "1" or "2". I cheat when I give people their random numbers: A gets 5, B gets 5, C gets 7, D gets 11. Now they all cast their vote: A -> 1 B -> 1 C -> 2 D -> 2 Let's tally the votes, the result for choice 1 is 5 and the result for choice 2 is 77. A checks that its vote has been counted 5%5 == 0 so it's good. B checks that its vote has been counted 5%5 == 0 so it's good. C checks that its vote has been counted 77%7 == 0 so it's good. D checks that its vote has been counted 77%11 == 0 so it's good. For everybody the result appears to be one vote for choice 1, 2 votes for choice 2 and 1 abstention, your scheme does not detect any wrongdoing here.
sebmellen 6y ago
Not necessarily a dumb idea, but blockchains provide us an easier way to do something similar. Every voter would be provided 1 (one) "Right to Vote" token after verifying their identity or receiving it by mail (as is the proposed solution from the USPS). This is arguably just as secure as mail-in voting. Each voter would also have an "on-chain voter ID", which would just be an anonymous public-private keypair in possession of 1 "Right to Vote" token. This on-chain voter ID would never have to be "mapped" directly to a voter. All that's provisioned by the the election overseers is the right to vote with one account by using this token. Then, the vote is cast by redeeming this right to vote token, without the voting account ever being linked to a "real identity". Of course, there are problems here too. Mainly with UX, and then at a low level the hardware used (the general public is very easy to hack if you have nation-state power).
- Ekaros 6y ago
  Receive by mail? At that point I already know that the system is fundamentally broken...
- tudorhn 6y ago
  > This on-chain voter ID would never have to be "mapped" directly to a voter The government will generate these IDs and then mail them to people. Who’s stopping them from recording the mappings?
  - svrb 6y ago
    What's stopping them from not properly separating the outer and inner envelopes in mail-in voting? Or correlating poll booth entries with checkins? Nothing. The system fundamentally assumes the organization operating the poll is trustworthy.
    - lalaland1125 6y ago
      In case you are interested, the thing preventing those types of shenanigans from happening is volunteer observers from various parties. The inperson and physical nature of things makes it much more difficult to break.
lalaland1125 6y ago
This setup seems mostly pointless to me. Instead of publishing the product, why not just list the primes themselves? Both should be roughly equivalent and just publishing the list of primes would be simpler. And then once you do that, why even use prime numbers? Just assign unique tokens to voters. What exact security garantee are you trying to provide that wouldn't also be satisfied by just giving each voter a token and publishing the token lists?
- pgt 6y ago
  It can be verified with a pencil and piece of paper and a calculator, so anybody can do it. As long as you agree about the number of sequential primes issued, you can calculate how many votes are still outstanding and keep voting booths open until 99% has voted. By issuing ranges of primes to states, you know where you have to keep booths open.
  - mulmen 6y ago
    How do you know how many votes there should be? Don’t you just have to trust whoever gave you the ballot/prime? Why wouldn’t they just generate the checksums ahead of time, they already know your prime exists. They gave it to you.
  - ChrisLomont 6y ago
    > t can be verified with a pencil and piece of paper and a calculator, so anybody can do it. The size of the resulting number would be so incredibly large that no person with pencil and paper and calculator would have even the tiniest chance of being able to verify their number. The chance of even copying it down correctly once would be tiny. The number of pages to write it out is huge. The time for a person to check it by your method would require more than their lifetime. Thus nobody, not a single human, could check it by your method. This is a non-idea. For the math inclined, the nth prime is around n ln n. We need ~130,000,000 of them. Each side will multiply ~half of them. The resulting number is ~(10^9)^(10^9), which has 10^10 digits. Writing one step of the calculation at 5 digits per second would take 62 years.
jsilence 6y ago
Why not simply print a receipt after voting with the vote printed verbatim and a digital token that allows the voter to easily check whether the vote has actually been counted correctly. The token could be a hash of some relevant parameters that are easy to check and maybe digitally signed by the voting machine or whatever.
- dpflan 6y ago
  Indeed, a record of proof of the transaction instills more confidence in the system (i.e. votes aren't just in this "black box") and provides a redundancy in the case of issues with the electronic system.
  - Qwertious 6y ago
    If you vote from home, what sort of receipt do you get? A digital receipt for every candidate can't be recorded unless it's mailed in (and if people are all mailing in anyway then it sounds like you're just overcomplicating things), and people keeping a record of their vote at home where they can show others will let people systemically validate blackmail - "show me you voted <candidate> or I'll break your kneecaps". Although to be fair, if you seize someone's mail-in ballot you could force them to write it out under supervision. Other than possible cost savings, the only useful benefit of electronic voting is if it lets people vote from home/vote more conveniently. Requiring a paper backup nullifies that benefit, and making it optional damages the usefulness of having a paper backup in the first place and adds privacy problems.
    - mulmen 6y ago
      Blackmail doesn’t scale. In WA the ballot has a tab you peel off and can track through a webpage. It’s basically the system outlined above but we actually fill out a paper ballot then mail it in. The postage is prepaid. This solves basically all problems and works great. It’s independently verifiable. It’s anonymous. It’s accessible.
      - wtracy 6y ago
unabst 6y ago
And couldn't you just have one flat log file as an append-only ledger of all the votes? Maybe add a time stamp and location stamp to each prime recorded for context. Found this gem. https://primes.utm.edu/lists/small/millions/ https://primes.utm.edu/lists/small/millions/ 1 million primes is about 2mb zipped. Even with additional information, a national election result of 130 million votes could fit on a CD. The beauty of this is we have a completely transparent record that requires no unique software to view or test. No black boxes, and no magic beyond the magic of primes.
zeckalpha 6y ago
Private vote, guaranteed counting, no extra votes. Pick two. The system you’ve described only implements guaranteed counting.
ianhorn 6y ago
The number you're proposing has about 1.4 billion digits in it. It has more digits than just listing a number for everyone who votes and contains the same information.
RyJones 6y ago
VoteHere.net https://news.ycombinator.com/item?id=4771264 https://news.ycombinator.com/item?id=4771264
maxfan8 6y ago
There are a lot of comments here, but for anyone who’s looking for a well thought out implementation of publicly verifiable ballots, I suggest taking a look at Scantegrity [1]. Gotta love all the brilliant minds who worked (and implemented in the US!) it (David Chaum, Richard Carback, Jeremy Clark, Aleksander Essex, Stefan Popoveniuc, Ronald L. Rivest, Peter Y. A. Ryan, Emily Shen, and Alan T. Sherman) [1]: http://scantegrity.com/papers/ScantegrityII-EVT.pdf http://scantegrity.com/papers/ScantegrityII-EVT.pdf Note: They published several papers on the implementation and design of the Scantegrity system. I just linked to one of them (the most recent I believe).

by pgt 6y ago

luckylion 6y ago

It allows for verification not only by the voter but also by third parties, doesn't it? That would make it possibly to sell votes (with proof!) or threaten people with repercussions unless they vote a certain way.

compsciphd 6y ago
what's a bigger threat. "selling votes" or unverifiable election. i.e. we generally say election fraud is not a huge problem because its too easy to get caught. if that's the case, one would think any vote buying scheme would be even easier to get caught.
- Ekaros 6y ago
  Or coercion. If at any point your vote can be known, there is very high risk that someone forces you to vote like they want. Only way to prevent this is total anonymity of which vote was by which person.
  - compsciphd 6y ago
    is coercion really a threat on a large scale in the US (I'm sure in other countries it is). But if the onl way to know my vote is to have my random identifier, if I dispose of my random identifier, they can't know my vote. i.e. I feel we can both have total anonymity if a person desires, while also having verifiability. as an example: a random uuid is assigned to me and my votes are printed out on a slip of paper with the uuid (and with a cryptographic signature to verify that it was produced by a voting machine). I can choose to burn the paper and no one can know how I voted or I can keep the paper and anonymously verify that my vote was recorded correctly (i.e. download the whole set of uuid -> vote mappings). if the number of uuids submitted at each polling place is recorded reliably (i.e. observers from multiple sides having agreed upon counts), you have a good belief that no votes were added or removed. if every voter who chose to keep their slip is able to verify their vote is recorded correctly you have a good belief that the votes weren't manipulated (assuming enough people verify their votes). yes, there are issues, vote buying / coercion, but I'm just not convinced that those issues are severe enough or probable enough (at least in the USA) to want to avoid simple steps that will make people more comfortable with the election outcomes. i.e. make the punishments harsh enough for anyone caught coercing / paying others for their votes to make it unlikely to happen at a scale that will negatively impact things. but perhaps I'm naive about this.
    - pwg 6y ago
      > is coercion really a threat on a large scale in the US No, largely because of the secret vote and the fact that there is no way anyone can verify how "you" voted after the fact. So you can lie to the thug threatening you with a wrench that you voted for "candidate A" and the thug has no way to know otherwise. > But if the onl way to know my vote is to have my random identifier, if I dispose of my random identifier, they can't know my vote. If the thug with the wrench who has /suggested/ you vote for candidate A lest he break your kneecaps also knows you can verify your vote by using your random identifier, then if after the election you have disposed of your random identifier, the thug breaks your kneecaps because you disposed of your random identifier. Therefore you are still coerced to reveal your vote, because you are also coerced not to dispose of your random identifier until after the thug has verified you voted "the proper way". I.e. the thug changes tactics from "vote for A lest I break your kneecaps" to "vote for A and do not dispose of your identifier until I verify you voted my way lest I break your kneecaps". > I feel we can both have total anonymity if a person desires, while also having verifiability. If there is any form of ability to verify your actual individual vote, in any way, then there is no anonymity. Anonymity is only available if there is no ability to verify an individual voted a particular way after the fact. Any opening of verification destroys all anonymity.
deleted 6y ago
[deleted]
pgt 6y ago
This is only a risk if ballots are not issued privately.
- lentil_soup 6y ago
  That is a great system, but there could still be coarcion to show your "prime number" token to someone, say your employer. Probably not common in the US or the EU, but in Venezuela for example there is a lot of pressure for employees of state owned companies to vote for the government and they use many tactics to make sure you do. I'd be worried about making it simpler for them. Maybe there's a way of addding an extra layer of security?
sebmellen 6y ago
If you see my above comment on a "Right to Vote" token system, which would abstract away the identity of any given vote, there is a solution for this: Because the Right to Vote tokens and the accounts that they are voted with by are anonymous, no third-party knows which vote belongs to which person (except for arbitrary public-key strings). However, if a voter wants to check that their vote was counted, they can easily see that the token sent from their account was used to vote for a certain party. Now, if a second layer of privacy and abstraction is needed, zero-knowledge proofs can offer that. This, however, is a completely different ball game.

Znafon 6y ago

What is a unique, random, sequential prime and how do you actually vote?

pgt 6y ago
Issue 1, 3, 5, 7, 11, 13, 17... up to N for N registered voters. Mix them up and hand out randomly. So let's say you get 5 and I get 7. To vote, you cast your prime for a candidate, thereby consuming it. No two candidates can share a prime, because their checksums will have a common factor, which is not allowed. If we both vote for candidate A, his checkproduct is now 35. If ballots 11, 13 and 17 vote for candidate B, his checkproduct is 2431. Because 2431/5 = 486.2 (non-integer), you can verify that your vote was not counted for B, but it was for A, because 35/5 = 7 (an integer). And because 2431 and 35 don't share any factors, no two votes were counted twice.
- kevincox 6y ago
  Why do you need primes? You could just give everyone a number and publish which numbers voted for each candidate. That is effectively equivalent to what you are doing since each total product can be factored into the primes that voted for it anyways.
- gspr 6y ago
  In this system you have to trust that the issuing authority never reuses primes. That seeems like a major downside, and something that is hard to overcome with transparency.
  - klyrs 6y ago
    People would definitely notice if the checkproduct for two candidates had a nontrivial gcd. Which is almost guaranteed to happen if primes are recycled to a significant degree.
- Znafon 6y ago
  It doesn't work: let's take 4 people and they vote for two choices "1" or "2". I cheat when I give people their random numbers: A gets 5, B gets 5, C gets 7, D gets 11. Now they all cast their vote: A -> 1 B -> 1 C -> 2 D -> 2 Let's tally the votes, the result for choice 1 is 5 and the result for choice 2 is 77. A checks that its vote has been counted 5%5 == 0 so it's good. B checks that its vote has been counted 5%5 == 0 so it's good. C checks that its vote has been counted 77%7 == 0 so it's good. D checks that its vote has been counted 77%11 == 0 so it's good. For everybody the result appears to be one vote for choice 1, 2 votes for choice 2 and 1 abstention, your scheme does not detect any wrongdoing here.

sebmellen 6y ago

Not necessarily a dumb idea, but blockchains provide us an easier way to do something similar. Every voter would be provided 1 (one) "Right to Vote" token after verifying their identity or receiving it by mail (as is the proposed solution from the USPS). This is arguably just as secure as mail-in voting. Each voter would also have an "on-chain voter ID", which would just be an anonymous public-private keypair in possession of 1 "Right to Vote" token. This on-chain voter ID would never have to be "mapped" directly to a voter. All that's provisioned by the the election overseers is the right to vote with one account by using this token. Then, the vote is cast by redeeming this right to vote token, without the voting account ever being linked to a "real identity". Of course, there are problems here too. Mainly with UX, and then at a low level the hardware used (the general public is very easy to hack if you have nation-state power).

Ekaros 6y ago
Receive by mail? At that point I already know that the system is fundamentally broken...
tudorhn 6y ago
> This on-chain voter ID would never have to be "mapped" directly to a voter The government will generate these IDs and then mail them to people. Who’s stopping them from recording the mappings?
- svrb 6y ago
  What's stopping them from not properly separating the outer and inner envelopes in mail-in voting? Or correlating poll booth entries with checkins? Nothing. The system fundamentally assumes the organization operating the poll is trustworthy.
  - lalaland1125 6y ago
    In case you are interested, the thing preventing those types of shenanigans from happening is volunteer observers from various parties. The inperson and physical nature of things makes it much more difficult to break.

lalaland1125 6y ago

This setup seems mostly pointless to me. Instead of publishing the product, why not just list the primes themselves? Both should be roughly equivalent and just publishing the list of primes would be simpler. And then once you do that, why even use prime numbers? Just assign unique tokens to voters. What exact security garantee are you trying to provide that wouldn't also be satisfied by just giving each voter a token and publishing the token lists?

pgt 6y ago
It can be verified with a pencil and piece of paper and a calculator, so anybody can do it. As long as you agree about the number of sequential primes issued, you can calculate how many votes are still outstanding and keep voting booths open until 99% has voted. By issuing ranges of primes to states, you know where you have to keep booths open.
- mulmen 6y ago
  How do you know how many votes there should be? Don’t you just have to trust whoever gave you the ballot/prime? Why wouldn’t they just generate the checksums ahead of time, they already know your prime exists. They gave it to you.
- ChrisLomont 6y ago
  > t can be verified with a pencil and piece of paper and a calculator, so anybody can do it. The size of the resulting number would be so incredibly large that no person with pencil and paper and calculator would have even the tiniest chance of being able to verify their number. The chance of even copying it down correctly once would be tiny. The number of pages to write it out is huge. The time for a person to check it by your method would require more than their lifetime. Thus nobody, not a single human, could check it by your method. This is a non-idea. For the math inclined, the nth prime is around n ln n. We need ~130,000,000 of them. Each side will multiply ~half of them. The resulting number is ~(10^9)^(10^9), which has 10^10 digits. Writing one step of the calculation at 5 digits per second would take 62 years.

jsilence 6y ago

Why not simply print a receipt after voting with the vote printed verbatim and a digital token that allows the voter to easily check whether the vote has actually been counted correctly. The token could be a hash of some relevant parameters that are easy to check and maybe digitally signed by the voting machine or whatever.

dpflan 6y ago
Indeed, a record of proof of the transaction instills more confidence in the system (i.e. votes aren't just in this "black box") and provides a redundancy in the case of issues with the electronic system.
- Qwertious 6y ago
  If you vote from home, what sort of receipt do you get? A digital receipt for every candidate can't be recorded unless it's mailed in (and if people are all mailing in anyway then it sounds like you're just overcomplicating things), and people keeping a record of their vote at home where they can show others will let people systemically validate blackmail - "show me you voted <candidate> or I'll break your kneecaps". Although to be fair, if you seize someone's mail-in ballot you could force them to write it out under supervision. Other than possible cost savings, the only useful benefit of electronic voting is if it lets people vote from home/vote more conveniently. Requiring a paper backup nullifies that benefit, and making it optional damages the usefulness of having a paper backup in the first place and adds privacy problems.
  - mulmen 6y ago
    Blackmail doesn’t scale. In WA the ballot has a tab you peel off and can track through a webpage. It’s basically the system outlined above but we actually fill out a paper ballot then mail it in. The postage is prepaid. This solves basically all problems and works great. It’s independently verifiable. It’s anonymous. It’s accessible.
    - wtracy 6y ago

unabst 6y ago

And couldn't you just have one flat log file as an append-only ledger of all the votes? Maybe add a time stamp and location stamp to each prime recorded for context. Found this gem. https://primes.utm.edu/lists/small/millions/ https://primes.utm.edu/lists/small/millions/ 1 million primes is about 2mb zipped. Even with additional information, a national election result of 130 million votes could fit on a CD. The beauty of this is we have a completely transparent record that requires no unique software to view or test. No black boxes, and no magic beyond the magic of primes.

zeckalpha 6y ago

Private vote, guaranteed counting, no extra votes. Pick two. The system you’ve described only implements guaranteed counting.

ianhorn 6y ago

The number you're proposing has about 1.4 billion digits in it. It has more digits than just listing a number for everyone who votes and contains the same information.

RyJones 6y ago

VoteHere.net https://news.ycombinator.com/item?id=4771264 https://news.ycombinator.com/item?id=4771264

maxfan8 6y ago

There are a lot of comments here, but for anyone who’s looking for a well thought out implementation of publicly verifiable ballots, I suggest taking a look at Scantegrity [1]. Gotta love all the brilliant minds who worked (and implemented in the US!) it (David Chaum, Richard Carback, Jeremy Clark, Aleksander Essex, Stefan Popoveniuc, Ronald L. Rivest, Peter Y. A. Ryan, Emily Shen, and Alan T. Sherman) [1]: http://scantegrity.com/papers/ScantegrityII-EVT.pdf http://scantegrity.com/papers/ScantegrityII-EVT.pdf Note: They published several papers on the implementation and design of the Scantegrity system. I just linked to one of them (the most recent I believe).