Researchers find trapdoor in SwissVote election system
about.unimelb.edu.au
about.unimelb.edu.au
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.
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 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.
...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?
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.
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.
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.
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.
To make all this work the paper and electronic trail is digitally signed with something that's only on your voting card.
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.
never said it's easy, but it is possible.
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).
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.
So the Australian Senate is currently vulnerable to vote buying, for what it's worth.
https://www.zdnet.com/google-amp/article/us-voter-records-fr...
https://gizmodo.com/nearly-15-million-texas-voters-reportedl...
https://thestack.com/security/2016/04/25/93-4-million-mexica...
So much for such an important feature.
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.
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.
> [...] my expert says your expert is wrong and so it is/isn't fraud.
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.
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.
Also see https://www.newlyswissed.com/die-gottliche-ordnung-film-revi...
Advised as in stomped in hard with both boots if the canton didn't get its act together, pronto!
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.
“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"
[1]https://twitter.com/sarahjamielewis/status/11053782573171916...
Recounts and etc should be relatively easy to manage and leave a very good paper trail tied to various machines and etc.
We use essentially a Scantron sheet in Massachusetts.
Easy to fill out, computer countable, with a hand recount as an easy backup option.
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.)
Democracy doesn't work without trust. Sacrificing trust for some speed is dumb thing to do.
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.
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?
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.
More importantly, yes you can rig a paper ballot, but you can't do it large scale without everybody knowing it.
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.
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.
[1] https://www.gravesham.gov.uk/home/elections-and-voting/guide...
This is insane.
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?
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.
I’d prefer accurate >> speed when it comes down to something as important as an governmental election.
Accurate, triple-redundant hand counts can be done quickly - like in a day. Spot rechecks and audits may add another week.
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.
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).
I've never heard about burning ballots. Throwing packs of fraudulent ballots into voting boxes indeed has been caught on cameras multiple times.
What's more, statistical anomalies of voting results have been analyzed and they seem to indicate election fraud in favor of the Putin's party.
It is still better to have paper trail than not.
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.
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.
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.
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.
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.
It gives you another check against foolishness. If the computer says there are 5000 ballots missing, someone needs to figure out why.
I don't have a problem with computers being an ALSO. It's when computers are an ONLY that I have issues.
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.
Of course things should be good with that method. But they should also be good with some proper crypto.
Malice? User error? Ux idiocy? Who knows!
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.
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.
Which is it? Pick one.
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.
Your concern trolling isn't even wrong. Please. Continue.
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.
Still reading...
[1] - https://s68aa858fd10b80a7.jimcontent.com/download/version/15...
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.
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.
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.
[1] https://about.unimelb.edu.au/newsroom/news/2019/march/resear...
https://people.eng.unimelb.edu.au/vjteague/UniversalVerifiab...
> 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)?
E-voting is a bad idea, and government attempting to implement it is an even worse idea.
If the blockchain isn't public, then it isn't trustable.
You can't have non-tracked + blockchain + trust.
ZCash has a good write up on how this went in their zero-knowledge proof based system: https://z.cash/technology/paramgen
The main criticism by the researchers seems to be that the process around this setup was insufficient to demonstrate security.
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.
It is a much harder problem than a lot of technologist think. And "just add blockchain" is almost certainly the wrong move.
A backdoor is a hidden access, like this.
Just a mistake in the article.
https://people.eng.unimelb.edu.au/vjteague/UniversalVerifiab...
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:
https://www.math.uni-frankfurt.de/~dmst/research/phdtheses/m...
(Disclaimer: I have no idea how these work - maybe the authors mixed up their terminology ;-))
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.