| Comments (1) | Voting
I spent the first half of this week at at the 2010 Electronic Voting Technology/Workshop on Trustworthy Elections (EVT/WOTE) workshop. I only had one paper this time, a collaboration with Kai Wang, Hovav Shacham, and Serge Belongie called OpenScan. The basic idea behind OpenScan is really simple: in conventional optical scan systems the ballots are read by a single scanner operated by the election officials and there's no direct way for a third party to verify that the scanner is reading the ballots accurately. For all you know, the scanner (which after all is a computer) has been totally reprogrammed by some attacker.

There have been two major lines of development designed to provide some third-party verifiability for opscan systems. The first is a hand-counted audit, in which you randomly draw a sample of ballots, hand count them, and use statistical techniques to determine whether the results provide convincing evidence that the original count was correct. Audits require considerable statistical sophistication and have some other logistical drawbacks, so uptake has been a bit slow. The second approach, exemplified by the Humboldt Election Transparency Project, involved rescanning all the ballots and publishing images so that anyone can verify the count themselves. The problem with ETP-style approaches is that it's not practical to have everyone scan independently, so you're still at the mercy of the scanner. In principle, you now have two independent scans but of course the people who are allowed to do their own scan necessarily have a special relationship with election officials, so this doesn't create as high a level of assurance as you might like. (You can find my discussion of this issue here).

OpenScan takes the ETP to its logical conclusion by allowing an arbitrary number of independent scans. The basic idea is that instead of using a scanner, you have a mechanical paper transport and then use video cameras to record the ballots as they go by. You can then use computer vision techniques to isolate the individual frames corresponding to each ballot, rectify them so they're square, and then merge them into a singel image suitable for processing with standard optical scan processing software. Because the system works even when the camera doesn't have a head-on view, you can support multiple cameras, which means that a large number of independent observers can bring their own cameras, thus verifying the election without needing to trust the scanner (aside from that it will feed the ballots correctly). The nice thing about this design is that in principle you can build your own ballot processing framework completely independently out of commodity components (though this is a lot of work), so you don't really need to trust anything but that your generic camera and generic PC are behaving correctly. This means that election officials can allow third-party verifiability just be staging a single event where they run all the ballots through the sheet feeding apparatus and letting people video them. Note that like ETP this has privacy implications, so we would need to do some cost/benefit analysis before deploying such a system.

It turns out that this idea isn't original to us, as we unfortunately learned right after the camera-ready deadline. Anwar Adi suggested the same concept in 2006 and built a prototype, but it's quite a bit less capable than ours: it requires you to manually identify a single video frame for each ballot, doesn't produce ballot images (it uses simple edge detection algorithms to process the ballots itself) and won't work with the standard kind of opscan ballots in widespread use.

We (by which I mean Kai) have built a prototype of the system and it works pretty well. With the limited number of ballots we're processing, we get extremely good quality output; our test set of 50 ballots (600 opscan targets) produced no errors. The major drawback is performance: it takes about 10 seconds to process a single frame, so the system operates quite a bit slower than real-time with respect to the video camera. This can of course be dealt with by throwing hardware at the problem (we estimate that you would need something like 3-5 8-core machines to process at 30 ballots/minute, which is already pretty reasonable), but we've been working on faster algorithms and hope to be able to at least lower the required amount of hardware. Once we get this figured out, we're hoping to release an open source version of the software.


Dude, that is freaking sweet! Nice work. Kai must be a wizard.

Leave a comment