Wombat Voting: Open Audit Elections in Israel

My friend Alon Rosen is leading an effort with colleagues Amon Ta-Shma, Ben Riva, and Yoni Ben-Nun in Israel to implement and deploy in-person open-audit voting. The project is called Wombat Voting. It combines a number of existing cryptographic techniques in a very nice package. Oh, and they’ve implemented it and used it to run a 2000+ voter election, with apparently a few more elections in the pipeline. There’s a ton of press about them.

Here’s how it works:

Voters use an intuitive, touch-screen interface, receive a paper ballot they can physically cast in a transparent ballot box, and they get a physical encrypted receipt they can take home to make sure their vote actually counted. It’s awesome.

I’m extremely excited to see more truly verifiable voting systems implemented and deployed. Slowly but surely, we will get to a point where voting is truly auditable and democracy is actually verified. Israel, a high-tech democracy with engaged citizens, is a perfect place to get this kind of system going.

Online Voting is Terrifying and Inevitable

Voting online for public office is a terrifying proposition to most security experts. The paths to subversion or failure are many:

  1. the server could get overwhelmed by attackers, preventing voting altogether
  2. the server could get hacked and the votes changed surreptitiously
  3. the users’ machines could get compromised by a virus, which would then flip votes as it chooses with little or no trace
  4. even if somehow we secure the entire digital channel, there’s still the issue of your spouse looking over your shoulder, strongly suggesting you vote a certain way

So, terrifying. And yet, I’m now pretty sure it is inevitable.

What human activity isn’t on the Internet?

Today, we bank online, deposit checks and even pay vendors with our smart phones. We can change our mailing address with the postal service and pay parking tickets with our local governments online. We can shop online, socialize online, and debate with our Presidential candidates online. Newt Gingrich announced his Presidential campaign on Twitter.

Just about everyone now carries an Internet-connected personal device. The Internet is everywhere you want it, and just about everywhere you don’t. People are starting to experience the world through augmented reality, using online maps and satellite overlays matched with your current location. The Internet is only going to become more omnipresent, faster. Within a few years, it’s hard to imagine any human activity that doesn’t involve the Internet.

And yet, somehow, we expect people to still be voting in person, on paper? We can’t even get users to take SSL certificate warnings seriously, but we’re going to convince them that voting is so special it has to be done in person? I don’t think so.

Don’t grab your pitchfork yet

I’m not arguing that this is how it should be. I’m definitely not saying that we can secure online voting just like we can secure online banking. In fact I’ve made many of the original arguments, in my dissertation and on this blog, shooting down the bogus arguments that go something like “hey, we can secure online banking, surely we can secure online voting!” No, we don’t know how to do that.

What I’m saying is that, regardless of the state of online voting security, I think it’s a losing battle to expect voting to remain the only activity we still do in person and on paper. With the Oscars moving to online voting, the Federal Voting Assistance Program making $15M available in grants for activities related to online voting (even if it supposedly doesn’t involve online vote casting), parts of Canada moving to online voting, France considering online voting for its 2M+ expats (more than the margin of victory in the last Presidential election), what you’re hearing is the sound of inevitability.

Enforced Privacy is Dead

There’s another interesting issue, when you think about problem (4): even if we keep voting on paper in person, voting requires enforced privacy: we have to make sure it’s just you in the voting booth, not you plus a coercer. That’s great. Now, how many ballots do you think we’re going to see next year published on Instagram?

We have a deeper problem here due to the now omnipresent Internet. Voluntary privacy is not dead, since users can choose to isolate themselves. But enforced privacy, privacy imposed on the voter, the kind needed to prevent coercion, that’s quite dead. I’m very concerned about what that means for democracy. But again, this is inevitable.

Doing the Best We Can

So, if it’s inevitable, maybe the best we can do is make online voting as secure as possible. We’ll probably have a few disasters, maybe even a few thrown elections. So we’d better start now on the problems we have.

I think we can solve Problem (2) with open-audit, end-to-end voting systems like Helios (but not only Helios, there are others.) I think we can minimize the risk of Problem (1) by moving to a longer voting period (1 week instead of 1 day). I suspect we have to eventually give up on some aspects of (4), whether or not we do online voting, though some technical tricks might make voter coercion a good bit more difficult (it’s never completely impossible). The hardest problem is (3): we have no way of ensuring that people are using trustworthy software that captures their intent properly.

Again, I’m not endorsing online voting for public office. I’m saying it’s inevitable, and it’s time to face that inevitability.

Importance of the User Agent and why I joined Mozilla

This issue of trustworthy user software is a much larger problem than voting. As human activity increasingly moves online, the central question is: what software is truly on the side of the user? How does the user know for sure that the software they’re using is their true agent? There’s only one piece of Internet architecture today that can be the user’s true agent, and that’s the Web browser (which technologists call the User Agent, unsurprisingly.) And, among the web browsers, there’s one that particularly stands out as the ultimate user agent, backed by a company whose mission is focused on the user and only the user.

That’s why I joined Mozilla. Because for voting and beyond, everything people do is online or soon to be online, and users better have an agent on their side. The best agent users can get today is Firefox, and I hope to contribute to making it an even better user agent in the next few years.

[It’s worth noting that Mozilla has no intention of getting into the voting business, that’s just my personal interest.]

OK, you may now get out your pitchfork.

everything I know about voting I learned from American Idol

Tonight, American Idol began online voting. Yes, I’m a fan of American Idol, but don’t let that fool you: I’m still a bitchin’ cryptographer. I suspect that American Idol online voting will give rise to many questions such as “wow, awesome, now when can I vote in US Elections with my Facebook account?” and “Why is online voting so hard anyways?” Perhaps I can be of assistance.

the voting process

So the process is much like other Facebook-connected sites: using Facebook Connect, you log in and grant the American Idol Voting site some permissions, including reading your profile info (ok), getting your email address (ok I guess), and accessing your Facebook data even if you’re offline (ummm, why?). Then you select your favorite contestant, solve a CAPTCHA, and click “vote”. You’re prompted to post the vote to your Facebook feed, and told you can vote up to 50 times.

My first question was “what’s the CAPTCHA defending against?” I have some thoughts on that, which I’ll get back to…

“a secure solution”

The news that American Idol would use online voting was reported with enthusiasm:

“We have been wanting to do online voting for several years, and now Facebook has offered us a secure solution and we are ready to go,” said Simon Fuller, Creator and Executive Producer, American Idol.

So what does that mean, exactly? What guarantees do American Idol producers have that the system is “secure?” Hard to say. But let’s explore a few possibilities.

ballot secrecy and coercion

American Idol voting is not secret: your vote is posted to your Facebook newsfeed! Of course, unless you’re a contestant’s mother, chances are no one’s going to be upset at you if you don’t vote “the right way.” In political elections, and in fact in many elections where the outcome impacts voters in a material way, ballot secrecy is important, and undue influence of voters is a concern. That’s what makes things particularly difficult in “real” online voting: you should receive some believable proof that your vote was counted properly, but somehow that information can’t be leaked to others who might try to influence you, waiting to see how you voted to decide whether to pay you or break your kneecaps.

one user = 50 votes?

The voting itself is happening on the American Idol site, not on Facebook, so what American Idol is getting from Facebook is mostly the identity layer: to vote, you must have a Facebook account. Between that and the CAPTCHA, it’s probably fairly difficult for an individual user to have disproportionate influence. I have a feeling that’s why they allow individual voters to vote up to 50 times and require a CAPTCHA. After all, if any user can vote 50 times, but the process is fairly time-intensive, how worthwhile is it to register more accounts so you can vote more than 50 times? If voters could legitimately vote only once, then it would be very enticing to create a few fake Facebook accounts to easily quintuple your impact. But to just double your impact with 50 legal votes each, you’re going to have to manually fill out 50 more CAPTCHAs. Eh. Not worth it, right?

In other words, I think the 50 votes per person + CAPTCHA produce the great equalizer: almost no one is going to bother trying to find ways to cast more votes, because the payoff isn’t worth the pain. Clever!

verifying the tally

In typical secret ballot elections, it’s quite hard to check that the tally was properly computed. After all, once the vote is submitted, via web, SMS, or phone, the tallying process is visible only to the organizers, and the voters must trust that process blindly. Now, physical in-person elections have admittedly only a little bit more auditability: you can kind of watch the ballot box and, if you’re really motivated, stick around to see the ballots counted. But in the online voting space, unless you’ve got some fancy solution, the process is totally opaque.

Except… voting for American Idol isn’t secret! So, technically, the tally could be recomputed from culling together all of the Facebook newsfeed posts…. And that’s actually a key insight into how the fancy truly auditable voting systems work: all of the votes are published for the world to see, in a special encrypted form that doesn’t reveal individual votes but can be intelligently combined and checked against the claimed tally. That’s what systems like Helios do.

was my vote captured correctly?

If you post your vote to your Facebook newsfeed, you can verify that it was recorded correctly. But what if something hijacks your browser, waits for you to log into Facebook, casts votes on your behalf (waiting for you to fill out the CAPTCHA or outsourcing it to some CAPTCHA solving farm), and opts not to post the results to Facebook? How can the American Idol producers ever detect this? They probably can’t.

The simplest way one might hijack your browser is via a technique called clickjacking: by wrapping the voting site in an HTML frame and layering a different user interface on top of it, a malicious site could trick you into voting for a different contestant than you intend. For example, the attacker might wait for you to cast your first vote freely, find out who you like by looking at your Facebook wall, and then switch the order of the candidates (by layering new photos on top of the underlying real site) to trick you into voting for a different candidate the other 49 times. Now, to American Idol’s credit, my quick-and-dirty attempt to frame their site and implement clickjacking failed: they’ve got some basic defense against clickjacking that I’m still investigating. Nice work! But of course, attacks that hijack the user’s browser can be much more intricate, including deploying and spreading a virus that takes full control of the browser and its display. There’s absolutely nothing a web site can do to defend against that.

And that, in fact, is the key issue we don’t know how to address when voting online in elections that have a high material impact. We don’t know how to make sure that your browser is really working on your behalf and hasn’t been hijacked by malware. It probably wouldn’t happen for American Idol (or would it?), but it surely would happen when voting for US President.

Crisis in the Java Community… could they have used a secret-ballot election?

There is a bit of a crisis in the Java community: the Apache Foundation just resigned its seat on the Java Executive Committee, as did two individual members, Doug Lea and Tim Peierls. From what I understand, the central issue appears to be that Oracle, the new Java “owner” since they acquired Sun Microsystems, is paying lip service to the Java Community while taking the language and, more importantly, its licensing, into the direction they prefer, which doesn’t appear to be very open-source friendly.

That said, I’m not a Java Community expert, so I won’t comment much more on this conflict, other than to say, wait a minute, what’s this from Tim Peierls’s resignation note?

Several of the other EC members expressed their own disappointment while voting Yes. I’m reasonably certain that the bulk of the Yes votes were due to contractual obligations rather than strongly-held principles.

Wait a minute, the Executive Committee votes by public ballot? They’re influenced by contractual obligations? That’s fascinating, and that’s hardly democratic! It means that, even where standards bodies are concerned, the secret ballot might be a very interesting tool.

There are arguments against the secret ballot in this case, of course: maybe the Executive Committee members are representative of the Java Community, and as such they should serve their constituents? Much like legislators, their votes should be public so the community can decide whether or not to reelect them? In that case, contractual obligations to vote a certain way should be strictly disallowed or required to be published along with the vote… To whom are these Executive Committee members accountable? To themselves as well-intentioned guides of the Java community? To the people who elected them? It’s difficult to have it both ways, since one requires a secret ballot, and the other a public ballot.

Maybe the right solution is to publish all comments, but keep the ballots secret? There’s always a chance that a truly hypocritical member would consistently vote differently than their publicly stated opinions, but I’m not sure that risk is worse than the problems the Java Community just faced with what appears to be anything but a democratic vote. In a tough spot like this one, it seems to me that Executive Committee members should be able to vote their conscience without fear of retribution.

(Oh, and if the Java community is looking for a secure voting system, I might have a suggestion.)

faulty logic, even for good, is still faulty

So Alex Halderman and team hacked the DC Internet Voting pilot. The voting system they attacked was not particularly well secured, and the type of attack used is a fairly simple web input corruption attack with little novelty. This hack, however, performs a very useful task: educating election officials and the public about what hacks against an Internet Voting System look like.

What happens next is going to be very interesting. The folks who have been fighting hard against Internet Voting should be careful not to use the same faulty logic they’ve been criticizing for years. When the discussion was about paper was electronic voting machines, some election officials said “well, *I*’ve never seen anything go wrong, show me an example!” And the answer we, computer security specialists, gave was some variation of “how do you know nothing went wrong?” or, in the words of Dijkstra, “Program testing can be used to show the presence of bugs, but never to show their absence.”

What reasoning applies, then, when we do find a bug? We are faced with an effective attack against a specific Internet Voting system. It’s easy to get carried away… Verified Voting just declared the Dangers of Internet Voting confirmed saying:

we have a visceral demonstration of just how serious the threats really are.

yes, so far I agree,…

But do legislators and election officials fully understand what Dr. Halderman’s team has taught us? We’ve been given a lesson on how easy it is for attackers to penetrate and control not just this system, but any Internet voting system.

Ummm, no. That’s incorrect reasoning. Remember the important question: how do you know? We know that this system in question is insecure. But we have no proof that all Internet Voting systems are insecure. This is the same faulty logic of inappropriate generalization we accused the election officials of only months ago!

Now, once again, I need to clarify: I agree that Internet Voting for high-stakes elections is deeply problematic, and I’m against it. Interestingly, I don’t think this server-penetration hack represents the inherent problem with Internet Voting, because, given sufficient work, we could probably secure a voting server. The core problem is that end-users’ computers can’t be secured, making it possible to defraud the election even if the server is very secure. But whatever I think, and whatever everyone else thinks, this particular hack does not prove anything about the security of all Internet Voting systems in general.

If we, as security professionals, attempt to leverage and over-generalize this one incident, we’re just as guilty of overlooking sound security reasoning to push a particular agenda, exactly what we saw some election officials doing in 2004-2006 with electronic voting machines. In the long run, this greatly undermines scientifically-based arguments against Internet Voting. The ends do not justify the means.

Fort Knox vs. the Barking Dog

Over the last few days, Alex Halderman and his team at the University of Michigan hacked an Internet Voting System being field-tested by the DC Board of Elections. First, we need to commend both Alex’s team for their dutiful analysis of this system, and, more importantly, the DC Board of Elections for running an open security evaluation of their system. I say “more importantly” because there is very little good press to gain from such a test: in fact the DC Board of Elections is already getting a lot of grief, the hah-hah-they-got-haxored articles just write themselves. I think they did exactly the right thing: they experimented with a technology, and they did so by running an open security evaluation. Kudos to them. I sincerely hope that this is the beginning of a trend, and even those who criticize Internet Voting should take a few moments to first commend the DC Board of Elections.

The Halderman DC Internet Voting Hack is not specific to voting: it’s a fairly standard input-corruption attack on a web application. With more work and more security testing, the voting system will probably get better and more difficult to attack. More consistent input validation, running the server chrooted to limit the effects of this kind of attack, etc. Much can be done to make the voting application more secure. But, as Halderman and team correctly point out, it will never be fully secure, because nothing ever is.

The first and obvious conclusion is that Internet Voting for high-stakes public-office election is a very risky proposition, because suddenly your world of eligible attackers includes anyone with an Internet connection. But there’s a deeper conclusion, and I find it surprising that many voting security pros don’t see this more clearly: when we say “every system is vulnerable to attack”, that includes paper-based voting systems! Without an internet connection, it’s harder to attack a paper-based voting system, but it’s still doable. And the key problem is that, when a paper-based voting system gets attacked, the recovery story is not much better than that of an Internet Voting system.

The best example of this sad state of voting security is one I learned from Alex’s previous work hacking the Indian voting machines: in remote precincts in India, with their paper-ballot voting system (prior to the recent Electronic Voting Machines that have resulted in so much controversy), there’s long a type of attack called “precinct capture,” where attackers literally hijack a precinct and take the staff hostage while they stuff the ballot box with extra votes. Then they leave. Oh sure, you know who did it. But what can you possibly do to recover? Which votes do you discard?

My friend and voting technology veteran Jim Adler likes to talk about “Fort Knox vs. Barking Dog.” If you think about security like Fort Knox, where you focus on preventing someone from penetrating your defenses, you’ve got to invest incredible amounts of money and build incredibly sophisticated fences. If your defenses fail, and someone penetrates Fort Knox, gets the gold, and leaves, you are screwed. Because it’s gold, it’s not traceable, and once it’s stolen, it’s gone for good and there’s no way to recover.

The Barking Dog model is different. You still build fences. Maybe even a fancy lock. But more importantly, you get a well-trained dog, maybe even two or three for redundancy. And you assume that some of your fences will fail, because that’s what fences do when faced with smart intruders. When they do fail, and someone comes in, that’s where the barking dog comes in. Your defenses may fail, but your detectors will sound the alarm, allow you to respond and, hopefully, recover from the intrusion.

So back to voting with our new-found Knox v. Dog wisdom. Can we get a “barking dog” model of voting? The main reason it’s not so easy is because of the secret ballot: we want to ensure that, other than you, no one knows how you really voted. Because of this simple requirement, it’s very, very difficult to detect a problem. Even with paper-based systems, the answer is “sort of” at best. There’s a bunch of fascinating research into optimal auditing techniques, but the problem with all of these techniques is that the dog barks only under certain conditions, and even then only way too late. By the time you find out that something bad happened, there’s no way to recover. Consider again the Indian precinct capture attack. What can you possibly do to recover from that?

The Barking Dog is only useful if it barks in time for you to do something about it. That’s why I am increasingly convinced that, now that we have the technology to build systems that can be truly audited by the public thanks to individual tracking numbers and cryptographic auditing techniques, all while preserving the secret ballot, it’s simply sound engineering to do so. With these open-audit systems, any voter can be a barking dog.

So, we should clearly rethink our attempts at Internet Voting in high-stakes public-office elections. But, by the same token, we should rethink all election processes that do not provide recovery from error or attack. Paper-ballot systems may be noticeably less vulnerable to attack than Internet voting systems, but once they are attacked, they are hardly more recoverable. Now that we know how to do better, we should not rely on a Fort Knox, impenetrable-fence model of voting security, even with paper ballots.

UPDATE: Jim dug up the archeological trail of the Barking Dog in voting technology: a VoteHere blog post referencing an MSNBC report on their technology. Also, typo fix and clarification regarding the Indian precinct capture attack.

Usenix Security, voting and health security

I’m at Usenix Security 2010 in DC, starting with the EVT/WOTE Workshop on voting where I’ll be presenting an update on Helios, then the HealthSec workshop where I’ll be on a panel discussing my paper with Zak Kohane and Ken Mandl on using a Personally Controlled Health Record for health-information exchange [PDF].

The voting crowd is emerging from a 2-day workshop with election officials on remote voting for military and overseas voters. I’m trying to get a sense of attendees’ impressions from that workshop, but suffice it to say that it seems to have been “exciting.” Ron Rivest compared online voting for public-office elections to drunk driving, as in “there’s no good way to do it,” and that apparently didn’t go over very well with some folks. I agree with the metaphor, however harsh it may seem.

Meanwhile, there is plenty of room for online voting in the numerous elections people hold that are not for public office: corporate boards, clubs, student government, etc. That’s why I’m excited that last night, we released Helios v3. Try it out right now by voting in our super geeky sample election and in a current-events election (Wyclef for Haiti?).

More than 25,000 votes have been cast using Helios technology. We’ve learned some very interesting lessons already, and there are many more to come. I’m hoping that, as we add more social aspects to Helios, we’ll see more usage, more data, and a unique chance to improve the technology based on real-world experience.

What the Oscars teach us about voting

This year, the voting process for the Oscars has changed. Rather than indicating a single choice as they have done since 1946, members of the Academy will provide a first choice, a second choice, etc.. potentially ranking all 10 nominees for Best Picture if so desired. Some are speculating that this will affect the results. Some are writing really confusing articles about this change, with very misleading lines like “Getting the most votes is no longer enough.” Here’s the short version of this post: (1) of course ranked-voting is going to affect the Oscar results! and (2) this year, the result will actually reflect the will of the Academy far better than previous years.

Debating voting methodology can usually get very heated. In fact, if I say anything negative about ranked-voting, more formally called instant-runoff voting (IRV), a legion of IRV fans will descend upon this blog with tremendous fury. Thankfully, in this case, there’s little room for disagreement: it’s pretty obvious that IRV will much more adequately represent the opinion of the Academy. In fact, it’s surprising that the Academy has been using plurality single voting, which can easily yield wildly inaccurate results. It makes one question the validity of past Oscar winners, and not only because the election is completely un-auditable by anyone other than the designated auditor firm.

Say, for example, that 30% like Avatar best, 25% Hurt Locker, 20% Inglorious Bastards, 15% Up in the Air, and 10% District 9. (Apologies to the other Oscar nominees, but I need a simple example.) Using last year’s voting method, Avatar wins. With 30% of the vote. But wait, what if the fans of District 9 hated Avatar, and really prefer Hurt Locker second best? Since their first choice was District 9, a less popular movie, it seems they effectively don’t have an impact on the result of the election… unless we take their second choice into account. Ok, so we give those 10% to Hurt Locker, and now Hurt Locker wins. But wait, what if the fans of Up in the Air mostly prefer Avatar to Hurt Locker, so we eliminate “Up in the Air” for not having received enough votes, then give those to Avatar, then Avatar wins, but wait… you get the picture. It’s not that complicated. Basically, it means that if the movie you really want to see win has no chance of winning, then we’ll look at your second choice instead. The really crazy thing is that, with last year’s method, it’s conceivable that, even if all the fans of Inglorious Bastards, Up in the Air, and District 9 prefer Hurt Locker to Avatar, meaning that in a 2-way-only election, Hurt Locker would win 70-30, Avatar STILL wins under the system used for the last 64 years.

Because of this oddity, the fans of District 9 might realize that their favorite has no chance and be tempted to select only between the two favorites, Avatar and Hurt Locker. In other words, the dark horses are inherently handicapped. With IRV, there’s no reason to resort to such silliness: vote for the dark horse first if that’s really your preference, and if not enough others agree, your second choice will be “activated,” and you won’t have lost your chance to influence the result. So, this year, a dark horse movie has a better chance of winning. But not because the voting system gave the dark horse an unfair advantage! Rather, because IRV better represents the will of the Academy. Even if one of the favorites does win, it will be a much more legitimate win than every year prior.

And here’s the funny thing. That crazy plurality single vote system I just described… that’s how we vote for President in the United States.

Wait a minute…

Did I just imply that IRV is awesome? I should be more careful. Everything I just explained assumes that voters are well informed and rational. I’m willing to believe that voters are mostly rational, but I don’t think they’re well informed. Specifically, a voter might easily believe that voting first for District 9, then for Avatar yields a “weaker” vote for Avatar if District 9 is knocked out of the running. Or, they might think that voting only for District 9 will yield a stronger vote than if they add a second or third choice because, in some sense, District 9 is then the only acceptable winner for those single-movie voters. In other words, I suspect voters will still vote strategically with IRV, only this time with an incorrect, ill-informed strategy. This is speculation, I don’t have hard numbers to back it up, only (significant) anecdotal experience with voters who find IRV deeply confusing.

What we really want is a voting system that assumes realistic behavior from voters who are typically not fully informed experts. In a way, we need to reduce flexibility for voters so that the average voter will be less likely to choose an ill-informed strategy. That method is probably approval voting, where a voter marks every candidate they find acceptable. No ranking, just a checkmark next to each candidate. Instructions are then very straight-forward: mark every candidate you would be happy to see win. Not perfect in terms of ill-informed-strategy-resistance, but a heck of a lot better than all the misconceptions that come with IRV.

Oscar voting is actually even weirder

Of course, as if the insanity of the Oscars’ voting system over the last few years weren’t enough, there’s more weirdness.

To select the nominees, the Oscars effectively run a multi-seat Single Transferable Vote, which is like IRV where you rank the options, but this time you’re filling multiple spots. This is the way that Cambridge, Massachusetts elects its City Council, and it’s the way Australia elects its Parliament, and it’s incredibly confusing because of how votes are redistributed when a candidate is knocked out of the running or, more importantly, how to redistribute extra votes for a candidate that already has passed the victory bar. How confusing? Well, in Cambridge, the result of the election may depend on the order in which you count the ballots. Yep, you read that right, in a close election, the order of the ballots matters.

I’m not sure how it works exactly for the Oscar nomination process, but apparently the Oscars add a second complication: a nominee must be selected as a first choice by at least one person. Even if the movie is everyone’s second choice, it cannot be a nominee.

So, what this now means is that the Oscars are using a weirdly modified version of multi-seat Single Transferable Vote to select the nominees, and then a plurality single-vote to choose among those nominees, except this year where they’re re-running an IRV vote for Best Picture.

And to top it all off, you have to fully trust PriceWaterhouseCoopers, the auditors, who don’t even provide tallies, only the name of the winners.

Whoever said elections are simple?

For deniability, faking data even the owner can’t prove is fake

I was speaking with a colleague yesterday about Loopt, the location-based social network, the rise of location-based services and the incredible privacy challenges they present. I heard the Loopt folks give a talk a few months ago, and I was generally impressed with the measures they’re taking to protect their users’ data.

I particularly enjoyed the problem Loopt faced with respect to abusive spouses: if your spouse is spying on you, it’s not enough to turn off your location services, because then your abusive spouse will know that you’re hiding something. You have to actually be able to lie about your location, in other words Loopt has to let you fake your location data. And they do. And that’s awesome.

It’s just like voting: to be free to vote the way you want to vote, you have to be able to claim that you voted a certain way, even if you voted another way, and that claim has to be believable. In fact, when you think about it, because Loopt offers this “fake my data” feature, there’s no way for you to prove to someone else that you really are where you claim to be, at least not via Loopt. Because, if there were a way to say “okay, really, I’m here, no faking this time,” then there would be no deniability since abusive spouses could simply ask for the extra-no-faking version of the location.

In other words, to truly achieve deniability, you have to take away the user’s ability to certify their own data. That’s not obvious, and it’s interesting that location-based services and voting have this point in common.

Takoma Park 2009: the conclusion

Well, it’s been a few weeks of craziness at home and catching up on other work, but I’ve finally wrapped up the Takoma Park 2009 audit. The final step: letting you, dear reader, run the audit all on your own.

You’ll find the complete instructions here on the auditing site.

I haven’t tested this on Windows, just Mac OS X, and it should work on Linux/Unix, too. You need Python 2.5 or above, PyCrypto, git, and subversion. You need about 30 minutes of download time, and 1 hour of processing. And then you can check the results you’ve computed against the results I’ve computed, against the official election results (which have some small variations since the results were certified, I’m not entirely sure why), and against the list of verification codes.