Hacker News Reader

Comment by pgt | Hacker News Reader

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.

View on HN

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.

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?

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.

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.

> 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.

Since most voting is handled and tallied by county/sub-divisions of that county, and are published as such, wouldn't the number be much smaller? A few thousand per district since you only need to be unique to the place your vote is tallied.

At any scale this method is unusable by the vast majority of people, and it doesn’t prevent tons of other problems such as fake votes added.

Next, votes were once public, but it was too easy to prove who you voted for, making buying votes more valuable. These methods would bring that back, since a voter could prove who they voted for. The US did this for its first 50 years, and Kentucky even had it till ~1890. The modern private vote made it harder to determine who someone voted for, since if someone paid me for a vote I could still vote how I pleased and they couldn’t check me.

The above simplistic method would bring back vote buying.

> other problems such as fake votes added

First of all, everyone knows we can prove this never happens already, so no big deal.

Second, this is a feature, not a bug.

>everyone knows we can prove this never happens

You're claiming extra votes are never added? That everyone knows this? Citation?

In the 2018 North Carolina 9th Congressional District election had votes added illegally, changing the outcome. The subsequent investigation threw out the fraudulent votes, the illegally elected Mark Harris stepped down, and so far about a dozen people have been charged with felonies.

"At the center of the scandal was the Republican operative Harris had employed in Bladen County, Leslie McCrae Dowless, whose operation, according to investigators, included filling out at least a thousand mail-in-ballot requests, many without voters’ knowledge, and deploying a team of friends, family members, and other associates to pose as election officials and collect them." [1]

There's even a case where in Brussels where a bit flip (often the result of a cosmic ray or soft neutron decay) flipped an election, and it was only caught since suddenly there were 4096 more votes than eligible voters.

So ignoring the possibility of fake votes added is short sighted.

Your claim "everyone knows we can prove this never happens" is demonstrably false.

[1] https://www.newyorker.com/news/dispatch/the-tearful-drama-of...

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.

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.

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.

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.

> 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.

>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.

Sadly, the thug also knows this. But what the thug (=ruling party) does know is whether an entire voting district votes for the opposition.

Then they come down hard on the entire district. In all sorts of creative ways.

> Sadly, the thug also knows this. But what the thug (=ruling party) does know is whether an entire voting district votes for the opposition.

It's not so much about the ruling party - if they want to steal the vote, they can just just send an officer into the booth with you that makes sure you're not cheating.

It's more about those that don't have that ability, e.g. religious groups, families, social circles. That's why ballot selfies are sometimes outlawed and generally strongly discouraged: if it's illegal and punishable to prove to third parties how you voted, you have plausible deniability for why you can't produce proof.

and what would happen if you forced a random sampling of individuals to destroy their slips? so random group can verify but you have no idea who is in that random group?

edit: or perhaps better, a random sampling were permitted to print out a proof of vote slip, but didn't have to. But if not chosen, you didn't get a proof of vote slip.

Now, in thinking it through, it might not help much. if someone can manipulate the voting machines, they can know who printed out their slips and manipulate the other votes. With that said, if done correctly, with a paper trail, I think it be difficult.

i.e. users are giving 1 or 2 outputs. piece 1 is a paper print out with a uuid and their votes that gets deposited in big box and counted as deposited. piece 2 that not everyone even has an option to get, can be kept. there has to be no way to distinguish the different piece 1s of those who get a piece 2 or not. If so, if everyone who got a piece 2 sees that their vote was recorded per the record they have, they can be confident that their vote was recorded correctly.

if their vote is not recorded correctly, they should have an anonymous mechanism to deposit their slips to make known that their vote was not recorded correctly. (hand waving at that, as unsure how to do that).

This is only a risk if ballots are not issued privately.

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?

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.

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

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.

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.

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.

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.

> Blackmail doesn’t scale.

If elections in my district are historically won by a 10-20% margin, and my corporation directly employs 20% of the people in the district, then I think I could make blackmail scale just fine.

I’m not sure I follow. Are you threatening people’s jobs? Do you think you can reliably get away with that? This is the part where it doesn’t scale. You’re taking on an enormous risk to maybe swing a tight election by committing widespread extortion. It’s totally unrealistic and has nothing to do with voting in person, online or by mail. Your threat would apply to all of them.

> Are you threatening people’s jobs?

Yes.

> Do you think you can reliably get away with that?

Robber barons did reliably get away with it throughout the nineteenth century. That's the whole reason that you don't get to take a copy of your ballot home today.

> It’s totally unrealistic

Well, somebody forgot to tell reality.

> That's the whole reason that you don't get to take a copy of your ballot home today.

My ballot gets mailed to my house. I fill it out in my kitchen.

The point of the secret ballot is to make it very hard to sell votes, because you can’t prove how you voted. (Vote by mail is not a secret ballot.)

How is vote by mail not a secret ballot?

I live in CA where we have had mail-in voting for some time. As far as I know, I don't have anyway to prove to someone that I voted a particular way.

A scenario where a family or workplace or other organization has everyone fill in their ballot in front of each other and then drop it off in the mail together.

“For convenience,” “to make sure everyone gets their vote in.”

The difference is there is no designated, guaranteed-private voting booth for the act of voting.

This really doesn't help, because the average voter will have no understanding of what that "digital token" is or how it can be used to "check" anything. Are we imagining some kind of unique QR-code or similar, that I scan to get a confirmation my vote was recorded? That's pure black-box voodoo... why should I believe that there's any connection between that "check" and the official count?

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

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).

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/

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.

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

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.

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.

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.

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.

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.

Of course, you also have to check that your vote was not counted for any of the other candidates.

None of the voters had their vote counted to another candidate here but the result is wrong.

This voting scheme is just broken.

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).

Receive by mail? At that point I already know that the system is fundamentally broken...

> 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?

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.

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.

Yes, and volunteer observers could also ensure that the keypairs mailed out to people are never revealed.

1. An airgapped computer running a keypair generation program generates millions of keypairs.

2. This prints these millions of secure keypairs with the keypair facing "downward".

3. In a publicized setting with volunteer observers, the private keys are sealed into envelopes which don't yet have names or addresses on them, and secured with tamper-proof seals.

4. These ballots are sent through another printing system, which adds an address and name to each ballot, at random.

5. The ballots are mailed out.

How is that any different?

The level of complexity for auditing here is much, much higher than the paper system. How do you verify that the software wasn't backdoored? How do you verify that the computer actually ran that software? What if the hardware had a backdoor? What about the compiler? Even the printers could be compromised.

Normally, I would consider these types of issues simply paranoia, but in this case we are talking about very high stake elections that control the spending of trillions of dollars.

VoteHere.net

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

Reply on news.ycombinator.com