Quick Guide to E2E Verifiable Internet Voting

I’ve spent a lot of time recently on crypto and security stack exchange. Some of the comments I’ve left could make good blog posts, so I will be republishing them here occasionally. This one is cross-posted from here.

Internet voting introduces certain challenges that are not present (or as present) when voting is done in-person and in a private, isolated polling booth. Internet voting is difficult, but not impossible.

In general we want five properties:

1. Ballot Secrecy – That each voter’s choices remain secret.
2. Integrity – That each voter’s choice is included unmodified in the final tally.
3. Untrustworthy Platform – A voter’s ballot should be reliable and accurately transmitted from their personal computer.
4. Coercion Resistance – A voter should be able to cast the ballot of their choice even if they are voting in an unsupervised environment (and an adversary may be standing over their shoulder).
5. DOS-Prevention – The system should prevent small-scale and large-scale (D)DOS attacks.

For in-person voting, we concentrate on (1) and (2). For internet voting, we want (1) and (2) plus (3), (4), & (5).

Ballot Secrecy

Most current voting systems only achieve (1) ballot secrecy. For polling place voting, once you leave, you do not have (2) integrity and if you are using a computer (DRE) to cast your ballot, you do not have (2) even if you observe the entire day. It is possible that they even mess up (1): for example, if voters arrive and are timestamped when registered, and then ballots are timestamped when cast, you can correlate votes to voters.

Ballot Secrecy & Integrity

End-to-end verifiable (E2E) systems allow you to achieve (1) and (2). E2E systems have been used for in-person voting in governmental elections: Scantegrity in a municipal election in Maryland. For internet voting, E2E systems that achieve (1) and (2) only (not 3,4,5) include Helios, which has been used in student elections.

These systems work by throwing a bunch of cryptography at the problem. A voter essentially encrypts their vote (either explicitly if using a computer as in Helios, or through some human computable operation if using a paper ballot, like revealing a hidden code in Scantegrity). It is possible to use encryption functions that do not completely lock down the message: for example, you could take some encrypted messages and add them together under encryption and then just decrypt the sum (see homomorphic encryption), or you can take a list of encrypted ballots and shuffle them up under encryption so that you can’t determine which ballot corresponds to which voter (see mix networks). Each step of the tally can be proved to be done correctly with zero-knowledge proofs.

Since the votes are encrypted, they can be posted publicly without breaking ballot secrecy, and voters can check to see that their votes are included unmodified for the final tally.

Ballot Secrecy & Integrity & Untrustworthy Platform

Systems that solve these three problems have not been used in an election yet, however there are two elections on the horizon that will use them: Remotegrity in Maryland (alondside Scantegrity for in-person voting) and the system in Norway.

These systems use two tricks: two-channels with the assumption that either one is trustworthy, and a technique called code voting. Over one channel (e.g., mail), voters receive a list of candidates with a serial number and unique codes (3 alphanumeric characters) beside their names. Over another channel (e.g., internet via their computer) they vote by submitting the serial number and code for the candidate they want. Assuming the computer is compromised, it can see the code but does not know (a) which candidate is being voted for and (b) what the valid code is for the candidate it would like to switch the vote to (or any candidate for that matter). It can guess, which will likely lead to an invalid code or it could just not let the voter submit anything: both have the equivalent effect.

Each vote that is received is posted publicly. Since only the person with the card knows which code belongs to which candidate, no one else knows how anyone voted. Voters can check the list to make sure their vote made it (and then there is some additional steps they can use to lock in their ballots).

Instead of assuming the codes are delivered by mail (which the malicious computer can’t read), they could come through the computer but in the form of a CAPTCHA or something the computer can’t read. One way of doing this is SpeakUp.

In any case, if someone showed their card to an attacker or the attacker was physically present with the voter, they could be coerced. This leads to…

Ballot Secrecy & Integrity & Coercion-Resistance

There are two approaches to addressing the coercion-resistance problem. One is to let voters cast as many ballot as they want, so they can overwrite previous ballots. It is possible to use cryptography to have hidden tags that can link votes from the same voter together, so that only one is kept. The problem with this approach is that an attacker just needs to wait until the end of the voting period (5 min before the polls close) to coerce a voter.

The second approach is to have real ballots and fake ballots. Voters who are being coerced or selling votes can use/sell a fake ballot, and the attacker cannot tell them apart. The tricky bit is to make sure only real ballots are counted and fake ballots are discarded without revealing if a voter submitted a real or fake ballot. Like above, we can solve this by throwing lots of crypto at the problem.

Systems like this are research-level only. None has been used or even planned to be used.

One way of doing this is called Selections. In Selections, voters use a panic password system. To vote, they submit a password. If they use their real password, the crypto ensures the vote is cast. If they use one of a large set of panic passwords, the crypto ensures the vote is discarded. The casting/discarding can be verified to have been done correctly for the set of all votes (not for each individual vote as that would defeat the purpose).

Therefore voters can just make up a panic password (it is easy to do in your head) on the spot if someone coerces them or offers to buy their vote. Later (or maybe they have already) they can cast their real ballot with their real password. No one can link the two together.

Aside: (D)DOS

This is considered a problem that is not completely solvable. An infected computer can always deny a voter from casting their ballot: what the untrustworthy platform property allows is for you to detect this, not prevent it. The DOS attack could also happen at the network level, taking down the server(s) receiving the votes. The integrity property can detect if any ballots are deleted or modified, but cannot prevent this.

The only solution is to use standard approaches for any web-service.

Ballot Secrecy & Integrity & Untrustworthy Platform & Coercion-Resistance

If we set aside the (D)DOS issue, this is the best system that we can achieve. To my knowledge, designing such a system is an open problem. It is non-trivial to compose the solutions for the untrustworthy platform issue with the coercion-resistance issue.

Disclosure

Scantegrity, Remotegrity and Selections are all systems I have worked on.

Wedding Wrap-Up

Thank you to everyone for the best wishes for our wedding!

Pictures

• Preparing the Bride and Sangeet – Thursday, February 11 – Photos by Sandra Valente
• Indian Wedding – Friday, February 12 – Photos by Bliss Photography Boutique
• Wedding and Reception – Saturday, February 13 – Photos by Bliss Photography Boutique
• Reception – Sunday, February 14 – Photos by Sandra Valente

The pictures are full resolution and suitable for prints. Just use the download function to save a high quality version. We also had a sangeet on the 7th but the pictures are only on Facebook.

Blog Coverage

One of the exciting parts of having a wedding in the internet age are vendors blogging about it.

• Jennifer Images on our Engagement
• Classic Elegance on our Invitations
• Savillian on Nehru Suits
• Distinct Occasions on Saturday’s Wedding
• Savillian on our Suits
• The Caketress on our Cake
• Jennifer Images on Friday’s Wedding
• Classic Elegance on Saturday’s Wedding

Over at Punchscan…

Where people vote affects how they vote.

New Coke Usability

In software design, and in particular security applications (my field), the usability movement has been a breath of fresh air. Where it has had impact, it has successfully integrated issues of user psychology and HCI into the minds of software engineers, if not a general sense of aesthetics and design in addition. I think usability is still missing the greatest predictor of human behaviour, economics, but in time, incentive-centred design (ICD) should eventually find itself folded in.

Being at Waterloo, I feel obligated to have some sense of appreciation for Malcolm Gladwell; however, I can assure you that my fondness is legitimate and preceded my enrolment here. In his book Blink, Gladwell skillfully dissects what the Coca-Cola company was thinking in releasing the syrupy and foul New Coke. As it were, the original Coke was routinely getting beaten at Pepsi’s latest marketing juggernaut: the Pepsi Challenge. Pepsi invaded supermarkets, giving blind samples of Coke, with its subtle complexion, next to the more peppy, sugary Pepsi, and asked consumers which they preferred. Consumers started buying more Pepsi. Coca-Cola retaliated by engineering the ultimate blind taste-test cola: super sweet with a touch of citrus. New Coke performed well in taste-tests, inching ahead of both Classic Coke and Pepsi in focus groups. But when it hit the market, a consumer backlash emerged. Apparently what the executives failed to realize is that the excessive characteristics needed to favourably distinguish a very small, sipping portion of New Coke from the competition becomes sickening after consuming half of a can of it.

There is a lesson in all of this for us usability people. Often we conduct user studies, where we sit a user down in our lab in front of a security application for the first time and see how getting them to do core tasks pans out. More often than not, its a total disaster and we draw lots of inferences about reducing complexity, simplifying the user interface, and automating as much as possible. Because usability is so hard, the typical problem is getting lab results implemented. But the argument needs to be made that there is a real danger in taking the results too seriously. The danger is that we create dumbed-down software that you love to sip, but once you take it home and start seriously using it, you yearn for a more subtle and complex software experience.

Pictures with the President

Does anyone else find it irritating that virtually every Wikipedia article of a G8 leader has to have the token picture of themselves with the President of the United States? Of all the notable pictures in the span of their career, often only 3 or 4 make it to their article, and almost without exception, at least one is with the President.

I’ll limit myself to G8 leaders in office during the Bush administration, although I’m sure the trend preserves in both time and set of nations. If I had a dollar for every time… a leader was pictured with the President, fifty cents if its a picture with the President but also some other leaders, and a quarter if its a senior official from the administration, this is how much my selection of leaders would net me:

Canada:

• $0.50 – Harper
• $1.00 – Martin
• $1.00 – Chrétien

 

France:

• $0.25 – Sarkozy
• $3.00 – Chirac

 

Germany:

• $0.00 – Merkel
• $2.00 – Schröder

 

Italy:

• $1.50 – Berlusconi
• $1.00 – Prodi

(Maybe in a few years, I can switch the order of these names again)

 

Japan

• $2.00 – Fukuda
• $0.50 – Abe
• $1.00 – Koizumi
• $2.00 – Mori

 

Russia:

• $4.25 – Putin

 

UK:

• $1.00 – Brown
• $1.00 – Blair

Benefit of Voting Receipts

Cross-posted from the Punchscan blog.

Rational people should not vote.

Or at least that the consensus among economists. Here is Levitt/Dubner, Harford, Landsburg. Okay, Okay, so maybe a consensus among economists who write great books.

The rational is that one vote will very rarely change an election’s outcome. In terms of costs and benefits, the costs of going out of your way to vote very rarely will outweigh the political benefit from casting that one vote.

Why do people vote then? Well in Canada, parties do get a small financial compensation for each vote they receive (under certain preconditions) but for the average voter, this is unlikely a conscious factor. There is also a sort of prisoner’s dilemma at play: its safe to not vote as long as everyone else does but if everyone acted rationally, then no one would vote (making everyone worst-off, and also making it rational to vote again).

However, empirical studies suggest that people vote because of a moral incentive to perform their civic duty, and not for any direct expected benefit. This is important because it means decreasing the costs of voting will not increase turnout. Levitt/Dubner summarize the finds of Patricia Funk on Swiss elections,

The Swiss love to vote – on parliamentary elections, on plebiscites, on whatever may arise. But voter participation had begun to slip over the years (maybe they stopped handing out live pigs there too), so a new option was introduced: the mail-in ballot. Whereas each voter in the U.S. must register, that isn’t the case in Switzerland. Every eligible Swiss citizen began to automatically receive a ballot in the mail, which could then be completed and returned by mail… Never again would any Swiss voter have to tromp to the polls during a rainstorm; the cost of casting a ballot had been lowered significantly.

So this will increase turnout, right? Amazingly, no.

In fact, voter turnout often decreased, especially in smaller cantons and in the smaller communities within cantons. This finding may have serious implications for advocates of Internet voting – which, it has long been argued, would make voting easier and therefore increase turnout. But the Swiss model indicates that the exact opposite might hold true.

Why?

If a given citizen doesn’t stand a chance of having her vote affect the outcome, why does she bother? In Switzerland, as in the U.S., “there exists a fairly strong social norm that a good citizen should go to the polls,” Funk writes. “As long as poll-voting was the only option, there was an incentive (or pressure) to go to the polls only to be seen handing in the vote. The motivation could be hope for social esteem, benefits from being perceived as a cooperator or just the avoidance of informal sanctions. Since in small communities, people know each other better and gossip about who fulfills civic duties and who doesn’t, the benefits of norm adherence were particularly high in this type of community.”

Conclusions: (1) Internet voting will probably not have the intending effect of increasing turnout. (2) Turnout can be increased by making the act of voting more visual to other people in society. (3) A great way to signal that you voted is a receipt. (4) Another argument for receipt-based election systems like Punchscan, Scantegrity, Pret a Voter, or ThreeBallot.

A Card Trick

An article by John Allen Paulos tipped me off to an interesting card trick. The trick is mathematical, and based on probability theory not sleight of hand. You get rid of the face cards in a deck (leaving the aces, which will be treated as 1′s), and give it a good shuffle. You then tell a cute woman (or man) you are trying to impress to pick a secret number between 1 and 10. Let’s say she picks 7—after all, we all know that prime numbers are more random. You then ask her to count (from 1… if she is geeky enough to count from 0, she’s probably not going to find the trick very impressive) the cards as you slowly turn them over. When the cards reach her number, the 7th card, she looks at the number on the card and this her new secret number. She then starts counting cards again from 1 to her new number, and repeats the process. Towards the end of the deck, you pause after overturning a card, tap it, and declare it to be the secret card she was counting towards.

The trick is to do the same thing you’ve ask her to do with the first card and go through the process in your head as you are performing the trick. The probability is in favor of your chain of numbers colliding at some point with hers, after which every number in the sequence will be the same (the chains have been “coupled”). As you near the end of the deck, you guess your own secret card with the confidence that it will be the same as hers.

To see it in action, here is a graph showing how such a game might progress. The numbers on the graph are not the series of secret numbers themselves, but rather the position of the secret cards in the deck.

Deck: 2, 6, 4, 6, 3, 9, 4, 8, 8, 5, 1, 8, 10, 5, 3, 5, 7, 6, 9, 7, 5, 6, 1, 3, 7, 10, 9, 2, 10, 4, 3, 2, 8, 4, 2, 7, 10, 1, 9, 1

In the above case, all numbers will lead to the 36th card. Sometimes, it doesn’t work out perfectly. For example, graphs like these are common:

Deck: 10, 8, 4, 6, 1, 5, 7, 7, 10, 5, 1, 10, 1, 3, 9, 9, 2, 4, 2, 5, 6, 3, 4, 2, 3, 7, 6, 2, 9, 1, 7, 9, 6, 8, 10, 8, 4, 3, 5, 8

Deck: 1, 9, 2, 2, 9, 9, 10, 3, 7, 1, 4, 10, 2, 8, 8, 5, 5, 5, 3, 4, 1, 6, 7, 4, 10, 3, 9, 5, 4, 7, 6, 8, 3, 6, 7, 2, 8, 6, 10, 1

So what is the probability that the trick will actually work? Working out the solution is more difficult than it sounds, but it has been found empirically to be about 83.7% for this variation (other variations leave the face cards in, and have them count as 5′s, raising the probability of succeeding a couple points).

A Puzzle over Contests

In my last post, I considered some of the complexities of contests. Now let’s ponder strategies for splitting the spoils should you find yourself on a winning team.

A fair split could attempt to correlate the winnings to the amount of work contributed to winning. But therein lays a problem. How do you determine what work contributed to winning, and what work was, well, worthless? The game theoretical analysis of contests suggests that teams should spend limitless amounts of utility in trying to outdo a competitor, if the competitor is trying to keep pace. But there are easy ways of sinking unlimited hours into things that ultimately won’t matter.

From our recent personal experience, we found the judges put a high value on things we would never have predicted and didn’t work particularly hard to achieve. For example, we won an award for printing some data on the bottom corner of ballots, which could be clipped off and retained as a paper-based backup. Its a good idea, don’t get me wrong. But we only did this, after much protest, to comply with a student association regulation we didn’t see much value in. We also were disheartened to find that what we felt was our strongest selling point, independent verification of election results, didn’t pass much muster.

There is also a tendency to overvalue the marginal cost of winning. That is to say, if you summed up the value of the winning team’s contributions against the second place team’s, the winning difference may be a small thing. In our case, it seems to have been finding a flaw in the competition’s code—but because this was the winning difference, it has a salience and availability that’s cognitively pleasing. Of course, if you were to subtract the value placed on the winning margin by removing some other contribution, you wouldn’t win. And so there is no one contribution that is the winning difference; there are only contributions which are equal in value to the winning difference.

Another interesting consideration is the difference between winning by a small and large margin: a difference that clearly amounts to nothing. If you win, you win. And so any added utility to secure your victory when you have already won is wastage. However during the competition, you are acting under incomplete information, making it difficult to establish when your contributions are inefficient. Ex post, its tricky to overcome hindsight bias.

Our choice was to split the prize evenly. If known in advance, this can be equally problematic as it lends itself to the free-rider problem.

Puzzle: what is the better solution? I don’t have an answer.

Hidden Costs and Benefits of Contests

I recently heard a well known public figure advocating state-sponsored contests to fuel scientific discoveries and achievements. Unfortunately, I forget who it was (someone with better recollection: feel free to comment). Contests are something I have some experience with, having just won one, and I concur with the individual that they are a very good way for the state to encourage innovation. But the economist in me cannot help pointing out that they are a little too good.

A much exploited method for economics professors wanting to make a little money off their naive undergrads is by hosting a dollar auction. A dollar auction is what sounds like — a loonie or dollar bill is auctioned off to the highest bidder — except it has one twist: the winning bid gets the dollar for the asking price but the second highest bidder must also pay her bid. Say Alice bids a nickel and Bob raises her bid to a dime (the bidding increment is irrelevant as long as it is fifty cents or less). Both will naturally continue, and at this rate, Bob will reach a dollar which you might think is the natural stopping point. However Alice is facing losing her last bid: 95 cents. If she raises Bob to $1.05, she is paying 5 cents more than the dollar is worth however losing 5 cents beats losing 95. Therefore, if she is rational, she’ll make the bid. Now Bob faces a similar dilemma: losing a dollar by sticking to his bid or losing 10 cents by raising. If he is rational, he will also raise. While this bidding war could continue forever, it will typically level-out at some point (especially if the bidders collude).

Now compare this to a contest, such as the one we participated in which offered a $10,000 prize. Each team that participates will spend, towards winning, a certain amount of utility — stressful days and straining nights, the forgoing of more pleasurable activities, money for equipment or promotional materials, and lots and lots of hard work. The ten grand is a juicy carrot encouraging each team to convert utility into an increased chance of winning (although this conversion has its own inefficiencies to be discussed in the next post). Of course, only the winner will receive something in exchange for their valuable efforts — the losers pay their bidding price.

This can be great for those who will benefit from the research — they get the sum total of everyone’s contribution, which usually adds up to more than the reward. But for the participants unwittingly caught in a bidding war, it can get downright nasty. Now of course, throwing more utility at the problem does not always increase your chances — especially in scientific contests that require a level of intelligence and insight not on the market. There are also two distinct contests: there is the kind we participated in where one team will win and therefore your goal is to simply outdo your opponent, and there is the kind like finding a cure for cancer or giving the FBI evidence of Osama’s whereabouts where it is possible that no participant will win.

I am no expert in appraising the monetary value of things like opportunity cost or added stress, but I would imagine that our team did not spend $10,000 worth of utility in our bid to win the prize. This is in part due to the non-zero sum nature of some our contributions — the utility can be spent in two places at once: on competing and also on completing a portion of a thesis or spotting a business venture, for example. However there was a constant incentive to spend more and more time on our submission, and that incentive would remain even if we outspent the prize we were vying for.

 The experience has left me a bit disillusioned with contests. The hardest part is not bidding when the dollar is going for 10 cents even if you know what you are in for. Once you get suckered in, its all downhill with no Nash equilibrium in sight.

A Hopefully Final Word on EV

Last week, I presented a paper at the Symposium on Usable Privacy and Security (SOUPS). During a panel discussion, the topic of EV certificates came up. I shared a short version of my position. Afterwards, I got into a discussion with several people whose disagreement with my position led me to clarify a few things. I thought I would share them.

I have already addressed the adverse selection of TRUSTe seals, and I don’t see it as a problem for my position. In fact, I embrace their failure as a fundamental reason why EV certificates could work better (if they were just a bit more expensive). The nature of privacy seals are different from certificates. Certificates are used for authentication (the site is who they say they are) whereas a seal is used to signal that the site follows their stated privacy policies. However, seals must undergo a verification process similar enough to EV that they could make a good comparision. Whether or not EV certificates lead to adverse selection is an empirical question that can easily be answered. I have not answered it myself, nor have a seen an data either way. However I am specifically addressing phishing sites; the illegitimate sites with TRUSTe seals are not phishing sites but rather sites that do not follow their stated practices; a problem of importance in its own right albeit a separate problem.

I think EV certificates are too cheap. They are marginally more expensive than a TRUSTe seal for sites with low revenue. Since I think the validation process itself is secondary, and the money spent is the primary mechanism that could allow them to work, my hypothesis is that EV certificates would reduce the adverse selection by an amount proportional to the price difference between them. Once again, this hypothesis is falsifiable. And if it can be prove, maybe it will be a compelling reason to jack up the price a bit.

I also only claim that EV certificates can solve the false-positive problem; that is illegitimate sites will not have one. It will not solve the false-negative problem; many legitimate sites will also not have one. And so encountering a certificate means the site is likely trustworthy, not encountering one means one should be agnostic about the state of the site. And so we may need a second solution to deal with the legitimate sites that can’t afford a certificate. However that leads to my next point.

Who cares about phishing? Costumers do a bit. But generally, customers will get their money back. The real people who care about phishing are the credit card companies. Now is it fair for a solution to solve the problem for some sites and not others? Moreover, is it fair that the richest sites can have the problem solved while leaving the online mom-and-pop shops left to fend for themselves? It doesn’t sound very altruistic. My answer is yes. Credit card companies, the real victim of phishing, loose more money from a small number of phished sites (the big ones–Paypal, Amazon, etc). I don’t have the data, but I strongly suspect that phishing has a long tail; that is the sites that get phished get phished a lot. If, for example, 5% of sites cause 95% of the revenue lost, you can solve a lot of the problem by solving it for a small number of sites. It doesn’t sound fair, but when power laws are in play, policy tends to have that characteristic.

So if we solve the problem for the big sites, won’t the simply phishers adapt and move to the long tail? Long tail economics makes a lot of sense if you are Amazon, but it wouldn’t work out so well for phishing. The first problem for the phishers is that you would need a new EV certificate for every URL. The phishing business model is to rapidly change between URLs, as their sites get taken down. I have gotten many phishing emails, but by the time I get around to clicking the link (I am always curious), its gone. Phishers have to build up quantity over time and over multiple URLs. EV certificates are not a one time cost, they are marginal for every URL. There isn’t a huge marginal cost for Amazon to sell one copy of a hundred books over selling a hundred copies of one book. But phishing a hundred people off of one site is much cheaper than phishing one person off a hundred sites if you need an EV certificate for each one (based on the economics alone; the actual validation process could prevent you from getting one as well). And so if EV certificates became prevalent, I think phishing would largely dry up (or shift to tricking the user through other social engineering methods instead of site impersonation). Remember that if you are resolved to making money illegally, there are a lot of competing methods.

Finally, its one thing to get a sound economic mechanism that is good at generating signals. The harder problem is getting users to understand the signals. A recent paper attacks the EV certificate cue of turning the taskbar green primarily through window-in-window attacks. I believe this is a browser problem, fundamentally. Browsers should not permit pop-ups; everything should open in a new tab. There is no reason why a website should be able to resize the browser window or pop-up without an address bar. The browser needs to take control of websites and contain them inside the sandbox of a tabbed window. But either way, the usability of EV certificates is a separate question and I am not convinced that the current cue is sufficient.