Takoma Park Election: the 7 steps of auditing

Posted on November 1, 2009 by ben

[This post is part of my Auditing the Takoma Park Municipal Election series.]

If you’ve been following, we know what the voter experience is going to be like on Tuesday, and we know what the auditing process is going to be like. So, can we audit this thing already?

Yes, we can. Here are the steps:

  1. Meeting 1: the election officials get together, agree on election parameters, and generate the commitments to the Ballot Table of 5000 ballots (called the P Table for historical reasons) and the 40 Shuffle Tables (called the D Tables). Why 40 shuffle tables? It’s a way of increasing the certainty of the election verification, but we’ll talk about the details in a later blog post. The only thing to verify here is that the Ballot and Shuffle tables contain exactly the number of rows they’re supposed to contain.

  2. Meeting 2: the election officials get together and use some public source of randomness (stock closing prices) to decide which rows in the P table (and corresponding rows in the D tables) to open up for auditing in the cut-and-choose process. They then reveal those rows accordingly. For the remaining rows, meaning the ballots that will get printed and used for ballot casting, the election officials generate commitments to the confirmation codes and publish them. The job of the auditor here is to ensure that this random selection was done properly, that the row reveals match up with the data seen in Meeting 1, and that the left-hand and right-hand permutations in the D tables match up with the P table. The confirmation code commitments are good to record, but they can’t be checked yet.

  3. After the election happens, Meeting 3: the election officials get together and fill in the P tables with the encoded votes that were cast and the D tables with the intermediate decryption of these encoded votes. They also reveal the confirmation codes that voters should be able to check only, and how these confirmation codes correspond to the commitments from Meeting 2. An auditor should ensure that the ballots used here were not those audited in Meeting 2, and that the codes are revealed correctly. An auditor should also make available the list of confirmation codes that he verified.

  4. the Tally: well yeah, that’s kind of important… based on the Results Table, called the R table, published in Meeting 3, it’s straight-forward to re-compute the tally from the individual ballots there. In the case of the Takoma Park election, this is a relatively standard single-seat single-transferable election.

  5. Meeting 4: using public randomness again, the election officials open up either the left or right hand of each D table. The auditor must ensure that the randomness was properly used to generate the left/right challenges, that the reveals match the earlier commitments from Meeting 1, and that the revealed permutation, left-hand or right-hand, was properly applied: in the case of the left-hand permutation that the P-table vote is properly transformed into the intermediate D-table vote, in the case of the right-hand permutation that the D-table intermediate vote was properly transformed into the result, fully decrypted vote.

  6. Contested Ballots: if voters complain about a confirmation-code mixup after Meeting 3, then the contested ballots are fully opened up by administrators so that all confirmation codes can be revealed. An auditor should check that these contested ballots are properly opened (we expect very few.)

  7. Spoiled Ballots: in-person auditing staff will be randomly selecting ballots to audit, and all unused ballots will be audited too in this “spoiled-ballot” final check, where the full P-table row and corresponding D-table rows are revealed by election officials. The auditor should check that all reveals are done correctly and that all permutations match between the D tables and P table.

Oh yeah, and one more thing: everything has to happen 6 times because there are 6 wards, each of them run independently.

So, the election is in a couple of short days… where are we now?

Meetings 1 and 2 have occurred. And I have just audited Meeting 1, go see the Meeting 1 audit data.

I haven’t yet done the audit for Meeting 2, but I have already signed the files generated by the Takoma Scantegrity team, so that I can be certain that that data is locked and loaded. I’ll be auditing it shortly, before the Tuesday election of course.

This entry was posted in crypto, Takoma Park 2009, voting. Bookmark the permalink.
  • Christopher Marshall

    How do you defend against the following attack?

    An election trustee reveals the seed used to generate the P and D tables to agents that then coerce voters to vote a certain way. The agents tell the voters whom to vote for and ask them for their ballot serial numbers after they vote. They use the seed to decode the reported ballot to verify if the voter chose the right candidate.

    I have read descriptions of the punchscan and scantegrity procedures that refer to a secure, diskless workstation the trustees use to print the ballots, generate the commitments, respond to the audit challenges, and tally the votes. None of the trustees is supposed to know the seed by themselves (they each have a separate share and the election seed is only known when a quorum of all the shares are combined).

    How could you know that a claimed ‘secure diskless workstation’ was in fact diskless and didn’t contain a secret flash device that it actually booted from while pretending to boot from the dvd-rom used at the ballot generation meeting?

    The only solution that occurs to me is that, before each meeting in which the ballot tables are generated from the election seed, the trustees randomly select a store within 10 miles from which to buy the diskless computer used.

    Are you aware of any other strategies?

    How was the election workstation handled in the takoma park election?

  • http://ben.adida.net Ben Adida

    Hi Christopher,

    Note that in you first paragraph “an election trustee reveals the seed…” that only works if the trustee has access to the full reconstituted seed.

    I agree with you that the diskless machine approach should be improved, because it is effectively a single point of trust in the system. It would be better to have true distributed P & D table generation, with true threshold crypto operations, rather than a diskless machine that must effectively be trusted not to leak the reconstituted seed. With the existing scheme, I don’t have a better idea than the one you describe. I would prefer a true threshold scheme, where the election trustees don’t actually need to meet in person and use the same system: they could each use their own.

  • Christopher Marshall

    Ben:

    Are you saying that distributed protocols, for generating the output of the challenges to the P and D tables, and for generating the R table tallies, exist? So the election trustees could exchange a series of emails with each other which could achieve that effect without any of the trustees being able to deduce the seed behind the table generation?

    That’s fascinating if true.

    I would still have to wonder about how to arrange for the printing of the ballots without relying on a ‘secure’ workstation to keep the seed secret.

    Did the Takoma Park election use a diskless workstation that was booted from a live DVD-rom?

  • http://ben.adida.net Ben Adida

    Yes, these protocols certainly exist, since we know how to do generic secure multi-party computation… the problem is, the generic protocols are quite inefficient. Maybe you’re already asking “does a very practical protocol for this exist?” and in that case I’m not sure. It would probably require a good bit of work, and by the time you’re done, it might end up looking a lot more like a classic verifiable mixnet.

    Where you’re absolutely right is the weakness regarding printing of ballots. There are some papers that attempt to fix this issue, notably by Peter Ryan regarding Pret-a-Voter and its derivatives, and I think there’s even been attempts to implement these more secure printing schemes. But they do require a lot more effort than Scantegrity.