Even if it were possible to design a provably correct, impossible to tamper with, anonymous electronic voting system (which seems unlikely to me) it still should NOT be used. Why?
Everyone understands paper in ballot boxes, and how they can be cheated, what to look for. Everyone can assess an argument as to whether this happened based on the evidence presented.
Basically nobody would understand what to even look for in cheating the electronic system. It would be totally my expert says your expert is wrong and so it is/isn't fraud. Having even the possibility of that argument for electoral fraud is completely insane.
It doesn't just have to be fair, it has to be seen to be fair. Really it does. We need to have reason to have faith in our democratic processes most especially when the people you want to win, don't and the result surprises you.
The sooner we get to "Any electronic voting must be used to mark a standard paper ballot which becomes the entire source of truth." The better. Everything else in electronic voting is dangerous, sinister and flat out evil. Oppose it. Loudly. At every opportunity. Especially if you're known as someone who understands computers on some level.
I work in public digitisation in Denmark where we do digital elections. We’ve digitised voter registration, not the actual voting part. That bit is still done with paper, and will continue to be that way for a long time.
Basically every adult Dane is mailed a vote-card that you can trade in for a ballot at your local voting place each election. Traditionally you took this paper and got crossed off in a big book, something which created hour long queues at prime times. So we added a bar code to your vote-card, and now we scan it when you arrive.
The interesting bit about this though, is that it’s way more expensive to do things this way because public IT-systems are just damn expensive. Which leads me to your point on “why would you do it”, and I agree, it just doesn’t make sense to digitise elections.
It doesn’t really make them easier to handle. We have to train people on how to setup and use the system, each time. We also have to set up the equipment and the backup equipment. Basically we spend a few thousand hours extra in preparation for each election, so not only is the software/hardware expensive, we actually use more man hours. You could reduce some of that by digitising the vote counting of course, but when we did the math it wouldn’t save us more than we spend.
So there is no financial reason to digitise elections.
We knew this when we decided to digitise part of our election btw, but because we’re the public sector and not a business, well, financial reasons aren’t the only reason we operate. Citizen satisfaction is a major one, and that’s exactly what we get by lowering the queues from a few hours to 10 minutes max.
But what is there to gain by digitising the counting? Getting results at 8pm instead of later during the night? Maybe if it was risk free, but since digital elections are the opposite, there is just no reason.
I guess if you let people vote online like Estonia, but we wouldn’t consider that to be a democratic process.
I dont understand quite why there are such long lines in Denmark. I know about America and why due to historical reasons they vote on Tuesdays, but this is the first I heard about queues in Denmark. Having been to Denmark quite a few times I always though Denmark to be better organized than Germany even. Maybe you could give some background as I am genuinely puzzled.
For some background. In Germany I voted in big cities, medium cities, tiny villages. Big elections and small. I never ever had to wait more than 5 minutes, I don't actually remember ever having had any experience that equated to 'waiting' as you would in a supermarket queue etc. I made some smalltalk with the election helpers sometimes but that's about it. I also never heard anybody ever mentioning waiting time when voting.
Basically voting happens on a Sunday. You get your morning breakfast. You decide to go on a walk with your family either in the morning or afternoon and stroll towards the voting place with your voter registration card and passport. You get the ballot. They strike your name from the list. You vote. You go home.
As for electronic voting. As a software developer I say it makes absolutely no sense whatsoever at all. It is already risky to tabulate the final data in software and forward this electronically. It would be better if it was phoned upwards and the written document then signed, sealed and sent afterwards for verification.
I had a similar experience. My first job was to study the deployment of electronic ballot box in a region in northern Italy.
It's such a problematic process on many levels, and it's incredible how many things can go wrong. Things you cannot even imagine: like finger traces on the touch screen. We just observed an increase of risks, without an increase in benefits. For extra safety, our machine produced a paper trace to every vote as well, but it's just not worth it...
Paper and pencils are still the best technology for elections.
And ofc voting at home, by mail or electronically, like in Switzerland or Estonia, is not democratic enough for me. To make it democratic, you have to be alone in a safe space with maximum privacy: a ballot box. You should not be pressured by family or anyone.
I know for sure that in Switzerland (I lived there), in many households, ballot box of the wife are often ticked by the man, and that's nonsense.
Some systems are simple enough and important enough that speeding them up with computers just ain't necessary. I can see how in a direct democracy, where many issues are voted on, it may seem reasonable to do it. However if an issue is important enough ought for it to be out directly to the people then it is important enough that we can wait for 24-48 hours for a result.
How about this?
1) you go to vote with your voting card
2) you get a paper printout of your vote
3) the voting machine then broadcasts your vote (only IDs) to N independent checkers; this makes your vote public but anonymous
4) later you check the printout against your favorite online checker to make sure it registered properly
To make all this work the paper and electronic trail is digitally signed with something that's only on your voting card.
This leads to the problem of letting _other people_ force you to show them how you voted.
This is a real problem! The secret vote isn't just about making sure that you can choose privately, but also about making sure that other people don't have ways of coercing you into certain choices.
Our current system allows others to know how you voted, postal votes are coercible and not secret. Your coercer could post your vote so electronic voting is only as vulenerable in this respect as our current system.
Only if the crypto is designed to be run in your head, so that you can lie to someone who wants proof. Good luck implementing that through education.
Consider the simplest case, a binary choice. The system tells you (and only you, and only once and without tangible record) that the public copy will either be inverted or not, a one bit one time pad. Kind of feasible, but already hard enough: will you really assume tampering when the bit that makes the public record match your vote does not match your memory? Then imagine scaling to something more meaningful than a binary vote, even just to more than one binary. I can't see that actually working out.
No there aren't. If you can check your vote, then your abusive spouse, your boss or somebody else who has power over you, can force you to show them your vote.
Not neccessarily, you can have a system where you can retrieve 'proof' of having voted in any way you want, and you can verify via some secret information used when voting, but making the UX of such a feature good enough that it's actually usable by someone in those circumstances is not at all easy.
They are given two random words. One for candidate A, one for candidate B.
They are told they should remember the code-word matching their choice if they later want to scan the printed out QR code (or enter their vote uuid) to one of the validator websites.
Voter makes their choice, completes the process. A thermal printout is printed with their vote uuid and a QR code meant to make it easy to input it.
Now anyone can get that printout with the uuid and scan it and see the code-word representing the voter's selection. However the association is only known to the voter and if asked, the voter can say that's what it was.
I've been thinking for a while that it would be nice to have paper ballots with the ability to cryptographically verify the inclusion of your vote in totals all the way up (ballot collection box, polling location, district, city, county, state, nation).
Such a solution is of the sort where you can't make up your own opinion if the two (hopefully) experts that looked at it disagree. And if they happen to agree you still have to trust them because you'd have to train for several years to be able to follow their argument.
Doing this permit someone to force you to disclose your vote and force you to vote what they want. The strength of traditional vote is that nobody can know your vote and this is the more important feature of the voting system.
I was arguing about this with someone when they pointed out that in Australian Senate elections, it's trivially easy to make your vote unique. There are many candidates and you can order them however you like, so you can vote a particular way among the candidates that are actually competitive, and then order the rest of the candidates in some improbable way to make your vote unique. Then when the database gets published later someone can verify that you voted how you said you would.
So the Australian Senate is currently vulnerable to vote buying, for what it's worth.
I like your thought, but if a voter can lookup their vote to confirm it got counted correctly with some form of receipt, then it opens the door for vote buying.
I’m not sure if there’s a way around that, but it would be awesome to be able to absolutely prove all votes were correctly counted.
that is why multiple people in the office of different political factions count the votes. And they are also present all the time. Otherwise you can simply do it the Russian way: https://www.youtube.com/watch?v=3oSeRyaFllY
I think what dnos means by vote buying, is not that somebody bribes the people who count the votes, but that somebody bribes the voters. If a politician now approaches me and promises me to pay me if I vote for him, he can't really be sure I actually did vote for him. Nobody but me knows what happens in the voting booth. He could ask me to take a picture, but I could still change my vote after the picture was taken.
sure .. that is possible. But all bribing is a matter of attenuation. One would want to spend as little money possible to change the outcome. Bribing voters is the most expensive version, one with the highest risk of being found out, and
least verifiable. Paying off the people counting in each district is once removed in these risks. Attacking the people up the chain (that sum up many districts) is the next level etc.
At every step of this way, if there is software involved it becomes instantly easier and less risky to influence. Whether it is online voting, voting machines, vote counting software, tabulation software, emailing results upwards etc.
That's a surprisingly luddite response on a technology forum. Paper ballots have all their own set of security challenges. The North Carolina event that literally happened this year being a great such example. The Battle of Athens is another - a literal gunfight over who would hold possession over the ballot box.
Or how about all the issues over running out of paper ballots, long lines, etc. With electronic voting you could have everyone pre-enter their vote electronically & just "drop" it off by scanning their phone & getting a printed receipt they can use to confirm their vote was recorded correctly cryptographically.
It is possible to actually design secure electoral systems that actually protect the integrity of the election better (better anonymity, better traceability, better auditing, less error, more accessibility, etc, etc, etc). Convenience is also important; there are even ways you can potentially design the system to run on semi-trusted hardware which means lower cost & more polling stations, easier access etc. This rhetorical argument of making fun of the idea as "we can wait a couple of days for the results" completely ignores the actual advantages of such a system. It also completely ignores that a paper trail isn't mutually exclusive from electronic voting.
The challenge is in making sure the process for creating these systems isn't corrupted, especially by technologically illiterate legislative leaders who don't seem to place any of the most basic protections that experts recommend. They also don't have the balls to hold the voting companies to task for designing secure systems; somehow it's a non-issue for the same companies to do the obviously right things when it comes to their other customers (banks).
I think it was just a misunderstanding on my part. It sounded like OP was advocating for a purely paper-driven system. That's why I said it's a Luddite position.
I think the misunderstanding on your part may have been similar meaning I'm advocating for entirely electronic.
To me electronic voting means a machine generating your ballot which avoids spoilage like hanging chads, incorrectly filled out ballots, etc (paper ballots should also be an option). Electronic voting means using counting machines to tabulate everything quickly while creating & retaining a paper trail for auditing. This is literally what Schneier is talking about: merging the advantages of both to mitigate the disadvantages of either.
Electronic voting is fundamentally incompatible elections. It's too easy to flip bits, and it always will be. "Hanging chads" etc are trivial issues (I would argue features) compared to the problems digital voting introduces.
But literally a paper trail is generated that can be used to audit any problems. How is that not better? Your "hanging chad" issue being a feature makes it sound like you're OK with disenfranchising people you look down upon.
"feature makes it sound like you're OK with disenfranchising people"
...if you assume the least useful interpretation of the comment. Could having a real physical object to examine be useful?
The paper as a "backup" is worse than backwards, it's an excuse to implement electronic voting, and since there is "no evidence" of problems, why would you need to examine the paper anyway?
You'd examine the paper to ensure integrity of the system. That's literally the point. Just like physical ballots are kept around.
Also, I think you're misunderstanding. The "no evidence" conclusion comes from auditing the paper ballot (as Schneier points out in that blog post above). You don't get to say "no evidence of problems" until the electronic & paper ballot agree. If there's disagreement you don't know which method is right & thus you have to hold a new election.
"You'd examine the paper to ensure integrity of the system."
Then just use paper.
Recounts (which is what your suggestion will get called in practice) require legal maneuvers which are fought by the winning side. Adding a electronic component to voting will never lower it's complexity.
> You might be surprised that that "Luddite" response is actually the consensus opinion among experts familiar with electronic voting technology.
I don't know if it is the consensus opinion among experts, but it certainly wasn't the opinion Schneier expressed in that article.
Granted, he had strong words to say about the voting machines used in the US. And justifiably so. They are just plain horrible, they've been known to be horrible for years if not decades now and I find it hard to understand why the most sophisticated and wealthy places on the planet continue to use them. Particularly as we have known how to do it right for almost as long as they have been in use.
To Schneier's credit he does explain how electronic voting can be done securely in the article. Which makes your comment all the more puzzling.
It is super convenient and I love being able to do research at my leisure with the ballot right in front of me--helps keep me from being lazy and voting a party line. The only downside is having weeks to procrastinate about it has caused me to miss a couple votes since we started doing it this way.
It preserves privacy by splitting the vote and the identification forms into two different envelopes. The vote (and only the vote) goes into a second envelope that is placed into the return envelope along with the identifying information. After the information is verified, the envelope with the vote is then added to a ballot box (and not opened right away). The whole process also happens in the open, so everyone interested in either the process or not trusting it to be properly done can stand by and watch. At least here postal votes are processed like this.
Sure. I'm still waiting for a description of how that preserves privacy? Until you seal the vote it's not privacy preserving. Literally the whole "privacy" aspect of the ballot is around making it impossible for anyone to observe your vote (& thus be able to punish you for not voting the "right" way). If you disagree, I'd like to bring North Carolina to your attention.
I don't know? I didn't make such a claim, but I'll speculate a little anyway. Vote by mail is accomplished by trusting the postal service which has a good track record of not losing or mangling my messages and, at least where I live, heavy legal deterrents against tampering. I imagine a digital solution could be as or more secure, but it may not be more trustworthy. Especially if the software running it is opaque or I don't understand the math involved.
Vote by mail is accomplished by accepting that a number of households/groups will cast a unanimous vote that would have been different votes if they happened in the enforced privacy of a voting booth.
That might be an understandable opinion if it is accepted as a conscious trade-off, but if you pretend that it will never happen you are just lying to yourself.
Here is a thread[1] from one of the researchers. She spells out what they have found. I think the most damning quote is.
“Do not let people minimize this issue. This isn't "some random hacker can steal an election" this is "SwissPost can prove they didn't steal an election, even if they did"
I really like the Minnesota system. You fill out a paper ballot. You load the paper ballot that gets scanned and recorded and the paper ballot gets rolled into a locked box that is attached to the machine.
Recounts and etc should be relatively easy to manage and leave a very good paper trail tied to various machines and etc.
I don't understand why you need a machine at all.
Counting ballots is trivial to parallelize.
You just have each polling place count its own ballots publicly, display the result in a permanent manner, reseal the box and communicate the count to a regional center. The regional center publicly sum the counts, display the sum and communicate it to a bigger center until you have the final count.
Where I am from, it takes less than two days to count a bit more than 30,000,000 ballots. You also get a very good result prediction two hours after the closing of polling places by using the official result of a set of selected small polling places known to be fairly representative of the voting population.
You still have to verify that the people counting the ballots aren't altering them somehow.
I remember hearing a story in France where it was found that people doing the count had bits of pencil lead tucked under their nails. They would open each ballot, and if it was for the "wrong" candidate, they would discretely mark another name and the ballot would be counted as invalid since it had two names circled. Not sure if it's a true story or not (can't be bothered to check) - but seems like a good illustrations of the problems that are faced.
> They would open each ballot, and if it was for the "wrong" candidate, they would discretely mark another name
That's impossible. You don't write on French ballot.
We use a card of a standardized format on which the name of the candidate (or the list of names) is printed which you directly put in the envelope. Cards are both sent to you by post and available at the polling station. Anything written on a ballot makes it void.
> They would open each ballot, and if it was for the "wrong" candidate, they would discretely mark another name
Ballots are open in public. The person in charge of opening the envelope does so in front of the room and with two assessors watching. They remove the ballot, read it aloud and display it to the room. It would be very difficult to read and alter a ballot without anyone noticing. A different person updates the tally on a board when the name is read.
The same on the other side of the Alps, plus local representatives of all parties use to roam between voting places and check that ballots are counted fairly.
As a software developer I trust the traditional method much more than any innovation involving machines and software.
This is one of the important parts. Every party wants itself to win, every ballot-counter also has a position, but if everyone can force a recount at any time, there's a much bigger motivation to count fairly. Multiple redundant counts is also part of that.
> Not sure if it's a true story or not (can't be bothered to check) - but seems like a good illustrations of the problems that are faced.
This exact sentiment -- that the truth of some tidbit of anecdata is not only unverified, but it's verification is irrelevent and should be treated as backing up a larger position regardless -- is one of the core problems with the current discourse.
As other commenters point out, not only is it not true, but such fraud is accounted for and mitigated in the existing procedure. So this is a bad illustration, it should seem like a bad illustration on the face of it because it hasn't been verified or contextualized, and in general we should all be suspicious of simple, pat little anecdotes that validate our assumptions about how the world is or ought to be.
Sorry for the rant, but I'm going to downvote this lazy thinking every time I see it. I hope we all aspire to better analytical thinking about the world, given that most of us here have to write software that interfaces with it.
I have participated in the operations of a voting station in France, and the method you describe would be incredibly risky, unless all the voting station is in (which you can not guarantee).
Also even then, one group never opens more than a few hundred ballots, so the corruption would be limited to a couple ballots or become super obvious.
I feel like this is nearly perfect if you automatically hand count statistically interesting number of boxes before certifying an election. If you hand count 1% randomly, you should feel pretty confident that nothing strange happened.
That's actually how large parts of Switzerland count their votes. (Some areas count/weigh ballots.)
This e-voting system is optional, can't be used for more than 1/3rd of voters in a given district, and is only being used by a small number of regions.
Given what's happened here, the moratorium on e-voting looks like it could well happen after all (funnily enough, that will also go to a vote).
Hand-counting is slow and inaccurate. As in, you regularly see swings of 1% or more from hand-counts, and they typically take weeks.
Electronic tabulation of paper ballots is the best of both worlds. You get results today, they're pretty accurate, and there's a paper trail if you want to go back and argue later.
Hand-counting is done in public in any respectable democracy. Each ballot is shown and you can constantly see the current tally. My parents used to take me to our polling places tally when I was a kid. For a mistake to happen, thirty persons supporting different candidates would have had to be wrong at the same time. It seems very unlikely to me.
Also, my country manages to hand count 30,000,000 ballots in less than two days and we get a very accurate result prediction on the day of the vote using a sample of official results from small polling places known to be representative.
Hand counting is not a problem at all when implemented properly.
At least in German we get the first hand count within hours. If that result is close and a recount is done, we will usually get that within a day. The final result may be weeks away, but that is because legal proceedings and additional scrutiny in a hand full of the 70000 voting locations take some time. Doing the vote with a sufficient number of locations and polling clerks is not cheap, about one euro per voter, but worth it to us.
Out of curiosity, what does a UK ballot look like? I found [1], is that typical?
Part of the problem might be one of ballot design. A US ballot is typically considerably more complicated than that. Here's one from New York [2]. There will be many races; in a presidential election there will be president, usually senator, representative, governor, state senator, local councilman, and assorted other offices. At least in New York State, the candidates will be presented by party, so a single candidate may be on the ballot multiple times.
Nobody is counting the US one by hand overnight; not without some pretty comprehensive redesigns of the ballot.
That's one of the simpler UK ballots. Some of our council elections allow us to elect more than one candidate, and our mayoral and police and crime commissioner elections uses the rather oddball supplementary vote system.
The Democrats ran in 4 "parties", and the Republicans in 3 "parties", for governor.
The Libertarian party nominated 2 separate sets of governor/deputy governor.
The non main parties nominated the same people (sometimes), but not for some categories, randomly. Some people are nominated on different parties that nominate different people for governor.
Ultimately, it's a 2-person race in most posts, and a single nomination for coroner.
Why not have 14 simple ballots with a straight choice?
Australia also counts all the votes by hand. In most cases the results for the lower house are known before the day is over, so like the UK we are pretty good at counting votes.
The same people also do the upper house count, which usually elects 1/4 the number of people in the lower house. Very roughly, the results are usually know in a month or so. https://www.aec.gov.au/voting/counting/senate_count.htm
If the results were recorded electronically I guess a computer would spit out the final outcome within a few minutes of the ballot box closing.
In the UK state-level interference would likely go unnoticed if it mugged only postal votes and didn't push too obviously-far in one direction or another. I've been on the receiving end of mail interference and since then I can only assume it's become a lot cheaper to do than it was.
Ballot stuffing is a thing, and ballot disposal is a thing.
Elections are one of the few games in town where the people that control things get to count up the vote and tell you who should control things in the future. If government was really ethical, you would expect independent auditors to be checking processes before and after.
Generally, there's an incumbent, and a likely winner. If you have enough popular support to win a fair election, you can probably figure out how to mobilize a few volunteers to oversee ballot counting.
I think the general assumption that you have is that all voters have equal access to financial gain, free time, and other things that in any society known are heavily deviated towards the rich. Add to that the fact that the most heavily monied campaigns normally turn out to be the winners, and it becomes very difficult to claim the idea of fair elections has any real merit except as a nice theory we want to believe is true.
You shouldn't presume the U.S. two-party system to be the normal case.
Also as a party you don't need to monitor every precinct. You monitor those where you suspect fraud might happen. Then every voter should be able to monitor the counting process if they desire. Why should they have to rely on parties to do it for them?
Hand counting is costly, time-consuming and error-prone. Paper ballots with supervised electronic tabulation puts forward the best of both worlds. (It's how we do it in New York, too.)
We're also required to have machines in the polling place for those with disabilities. These too produce paper records, that the voter can review. California went all-in on recording elections after the debacle in Florida in 2000.
Which is fine, if this were the only vector for votes. But then loads of "early voting" ballots turn up, and truckloads of "harvested" ballots with dubious provenance are delivered to be counted.
This process adheres to the paper trail rule, can be recounted with certainty, and yet is completely and utterly fraudulent.
Fair elections are the lynchpin of a democracy. Violate this trust, and the entire social contract is threatened.
Speaking as someone who is forced to vote on a proprietary touchscreen system with no paper trail, I wish researchers were finding cryptographic problems in my voting system.
I love those systems. In Texas my parents tried to press Betos name, and at the "review results" screen, Cruz was selected. This was a well documented, statewide problem.
The touchscreens in New Mexico 2004 simply didn't record the votes of Spanish language ballots. Kerry won the state but Bush received the electoral votes.
Fortunately, the NM courts agreed and prohibited the further use of the touchscreens.
What blows my mind is how invalidating (decertifying) the touchscreens has to be done in each state. I still can't fathom why the feds (eac.gov) can't just pull rank and ban them.
> I still can't fathom why the feds (eac.gov) can't just pull rank and ban them.
Article One, Section Four of the Constitution gives this power solely to the State and Federal legislatures. The Executive branch (and it'd probably the FEC, not the EAC) can't pull rank here unless Congress gives them the power to.
HAVA is an act of Congress. It does not, to my knowledge, allow the FEC to confiscate voting machines. Maybe it should've been clearer - "no shitty touchscreens!" - but it wasn't.
AZ tested some of the on-screen machines... I still prefer the Optical Scan-Tron option. Built in paper trail, super fast, need another booth, a few bucks of cardboard to isolate it from the rest not thousands for another slow touchscreen beast.
It uses a trapdoor commitment function. It does not have a “trapdoor” or “backdoor”.
The problem is not so much in the implementation of the function, but in the generation of parameters required by the function. The machines need to follow a particular scheme to generate the parameters of the function in order for the commitment to be secure. Think, e.g. of ZCash, where if the initial ceremony is not completed in a specific way and trusted, then the entire system after that has specific weaknesses.
In this case, if the parameter generation is not done correctly, or if randomness generated by clients is compromised, votes can be altered.
Now one of the issues is generating random group elements. Reading one of the linked notices [1] it talks about best practices of generating a random group element.
I don’t understand exactly all the terminology in the paper (even though it is quite trivial) but it looks to me like it is talking about generating effectively a public key in an EC system.
One way to do it is to generate a random integer r between 0..q-1, which is effectively the private key, and then generate the corresponding public key by doing g^r mod p.
The problem with this approach is that in the process the machine generating the public key knows the private key. It could be thus saved or leaked.
Instead you can generate a public key directly. This requires randomly selecting a value and checking it is valid (r/p=1), which is more expensive, or alternatively select a random r in Z and return r^2 mod p.
Finally, the generation process itself must be proveably fair and random (e.g. some sort of blockchain ceremony) to be trusted.
Fundamentally the Swiss system does not specify a ceremony for trusting the parameters used by its Pedersen commitment scheme, and therefore even if the implementation is perfect it still is not secure.
If all that's needed is a public key without known private key (i.e. some element Ga with a unknown) then a simple ceremony is possible.
Anyone who wants gets to submit a value H_i = G a_i.
With a proof that H lies in the correct subgroup.
Then the final value can bu the sum of all H_i s. The final private key would be the sum of all a_i s. If even one of those private keys is unkown, the final value is also unknown.
You don't need any such "ceremony" for this sort of protocol, no trusted setup is required at all: you can use a hash function to select random group elements.
All thats required is that that the dlog between the respective group elements is unknown, they don't need special properties other than that.
This makes it unlike the trusted setup of things like zcash (as mentioned in the grandparent post) which cannot be simply initialized randomly.
I don't know anything about how elliptic curve points are represented in memory, so I thought using a hash-function is difficult. If that's not the case, then there is no problem. Using hashes as 'nothing up your sleeve' numbers.
There are fairly straight forward options for this sort of thing... the simplest of which is you hash onto the field and check if the result is on the curve by applying the curve equation (which it will be with probability 1/2). If it is, you are done, if not increment the hash input and repeat until done.
There are fancier ways to hash onto curves that can give nearly uniform points in constant time, but they're curve specific... and for parameter generation you don't need constant time.
> How can there be a trapdoor when the system has been formally proven secure? Any formal proof of correctness for any system makes some assumptions that become axioms in the formal proof. Scytl’s formal proof of security [Scy18] simply models the mixnet as sound, based on an informal interpretation of Bayer and Groth’s security proof. It does not model the proper generation of commitment parameters. We do not see any reason to believe there is an error in Scytl’s proof, but when the axioms are mistaken the conclusions are not valid. This does not mean that formal proofs are not valuable—at an absolute minimum, they clarify assumptions and explain the reasons for trust—but it does mean that they are not a substitute for broad and open public scrutiny. It is quite possible that there are errors in the implementations of other cryptographic primitives, that their details may not be modelled in the formal proofs, and that they may affect either privacy or verifiability.
There wasn't a better path to translate the proof into an implementation? How was the algorithm translated into code (Java I think)?
The issue at hand, is people are REALLY sensitive to having their voting record(s) tracked. If you know someone's key, you can track all their votes on the blockchain.
If the blockchain isn't public, then it isn't trustable.
Sure, maybe you can design a provably correct e-voting system, but 99% of the people will just have to blindly trust the system. Then one day a politician will point out that his new election system is better, because it has nicer colors and some stuff, and maybe a lot of people will agree with him. A lot of people will be willing to move from from the provably correct system, which they blindly trust, to another system which they blindly trust. Except maybe the new system did away with all that blockchain mambo-jumbo and a few people on weird internet sites are complaining about it and saying that this isn't what we signed up originally with e-voting, but who listens to them?
In my crypto lecture we did automatic protocol verification using proverif. Since here the implementation is at fault, and not the protocol, the next thing seems to be a (proven) compiler from the (proven) protocol specification to an implementation?
Title makes it sound like a bug is discovered. The 'trapdoor' is in the protocol by design. A lot of zero knowledge proof protocols have an initial setup phase in which values are created that need to be forgotten for the system to be secure. These values are sometimes know as 'toxic waste'.
Only due to ignorance. It is well known that the bases of a Pedersen commitment can and should be sampled randomly; a trusted setup is only subverting the security of the primitive.
If you're interested in voting systems and the challenges of election administration, the National Academies of Science published a paper last year that is approachable, relatively comprehensive and free to read: https://www.nap.edu/read/25120/chapter/1
It is a much harder problem than a lot of technologist think. And "just add blockchain" is almost certainly the wrong move.
It seems there is a class of commitment schemes that's called "trapdoor commitment schemes" and deployed in SwissPost. I'm not aware of these, but they cite this PhD thesis on the topic:
I don't think it's a mistake. I think this is actually a trapdoor in the cryptographic sense of the term, and the security hole is the result of them using a zero-knowledge proof scheme based on these kind of trapdoor functions that relies on no-one having a copy of the trapdoor information, but incorrectly letting the untrusted party choose the trapdoor function.
Trapdoor is an older term that means the same thing as "backdoor". I think this author chose to use it in order to distinguish between the modern colloquial meaning of "backdoor" as "a method for an attack to eavesdrop on communication", and the more abstract meaning of a correctness vulnerability in an allegedly secure counting algorithm.
No, it's clear that the researchers are using the term trapdoor in a technical sense. Specifically, one of the key ideas in the swiss system is that it produce a proof that the votes produced as the result of the "shuffle" operation have the same meaning as the votes that are provided as inputs. The easiest "proof" of this would simply be to publish the input votes... but that would defeat the whole purpose of the shuffling. Instead, the Swiss system appears to involve a trapdoor commitment that produces a non-reversible token (hence "trapdoor") that could only be generated if this is a legitimate shuffling. As I read it, this is much like (for instance) a SHA-256 hash of an input message that can be generated to ensure that a document has not been tampered with.
TLDR: E-voting system uses pedersen commitments, but doesn't provide any evidence that the generators used are nothing-up-my-sleeve values.
To understand what a pedersen commitment is think "cryptographic hash" but constructed so that you can 'add' hashes to get the hash of the added values. Pedersen commitments require as system parameters multiple base points where, for soundness, no one knows the discrete log any of them with respect to each other. The normal way to accomplish this is to generate them all in a "nothing up my sleeve" way by hashing some data.
In my work on confidential transactions ( https://people.xiph.org/~greg/confidential_values.txt ) the base points I used were the standard secp256k1 generator, and a second point constructed by hashing the standard generator with sha256.
If implementations of the SwissVote system were initialized in the say way they could simply add the information about the hashed data to their audit logs, even after the fact. If, instead, they picked the base points "randomly" then they could not prove that past usage wasn't compromised.
I have often been frustrated by the lack of clarity in academic cryptographic papers about the exact trust implications about initialization -- e.g. it often takes a careful reading to tell if a paper requires a trusted setup, if the values can just be chosen in a provably random way (and if so, will a simple method suffice or is there a strong requirement on uniformity) ... but pedersen commitments (even the vector versions) are really bread and butter simple stuff. I would be worried that anyone who didn't know that choice of the base points resulted in a trapdoor would be unlikely to spot actually subtle implementation or algorithmic mistakes.
Everyone understands paper in ballot boxes, and how they can be cheated, what to look for. Everyone can assess an argument as to whether this happened based on the evidence presented.
Basically nobody would understand what to even look for in cheating the electronic system. It would be totally my expert says your expert is wrong and so it is/isn't fraud. Having even the possibility of that argument for electoral fraud is completely insane.
It doesn't just have to be fair, it has to be seen to be fair. Really it does. We need to have reason to have faith in our democratic processes most especially when the people you want to win, don't and the result surprises you.
The sooner we get to "Any electronic voting must be used to mark a standard paper ballot which becomes the entire source of truth." The better. Everything else in electronic voting is dangerous, sinister and flat out evil. Oppose it. Loudly. At every opportunity. Especially if you're known as someone who understands computers on some level.