[EL] Bush v. Gore ballots question

[Joseph Lorenzo Hall]

On Thu, Jun 2, 2011 at 5:20 PM, David Levine <davidalanlevine at gmail.com> wrote:
> On a somewhat related note I think Rick and Joe's references and remarks
> illustrate why it is important to to have a voting system that captures an
> actual graphic image of each individual ballot each time ballots are tallied
> ( in addition to recording voters and keeping running totals for each
> candidate). This redundant record of each ballot not only increases the
> likelihood of determining voter intent for any given ballot, since
> questionable ballots can be projected onto a screen allowing election judges
> to rule on voter intent, but substantially reduces the likelihood that
> problems with a voting system will result in different counts for a given
> set of ballots.

>From a technical perspective this is both very good and potentially
very bad.  (I've tried to word this in a way least likely to make all
your eyes glaze over!)

Very good, in that it is becoming increasingly essential to link
individual physical ballots to the digital "cast vote record" (a
machine-readable representation of how the system has interpreted
marks on the ballot as votes).  This is made somewhat easier using a
"ballot image scan", as David describes, where the image is an
intermediate link between the cast vote record and the physical
ballot. How are these used, ideally?  The field of post-election
auditing has changed remarkably over the past few years.  The state of
the art is in "risk-limiting audits" where a sample of ballots is
counted and if the amount of error (the number of ballots in which
voter intent was clearly not captured by the system) doesn't appear
large enough to change the election outcome, the audit stops and a
winner is comfortably certified.  If the error is not clearly small
and might affect the election outcome, a further sample is drawn and
counted (leading up to potentially a full hand count).  This ensures
that if error could change the outcome, all ballots are counted and
the subsequent result is by definition the correct outcome.
Naturally, if you know much about statistics, you'll realize that the
smaller one makes "batches" of ballots that are counted by hand and
compared to digital results, the fewer ballots one has to count and
the more precise the answer.  This can be taken to the extreme where
individual ballots are the sampling basis and instead of "counting"
the ballot, the entire contents of the ballot are compared to the
interpretation in the system's cast vote record.  Philip Stark
(Berkeley Statistics) and the California Secretary of State's Office
have been engaging in a number of "single-ballot risk-limiting audits"
under the auspices of AB 2023, a legislature-approved pilot program.
In many cases, these methods allow essentially performing "statistical
recounts" where a given contest can be confirmed to a high level of
confidence by counting only a few hundred ballots.

Now for the bad news.  In short, we need to be very careful who gets
access to full ballot image scans.  In my belief and the belief of a
number of academics in the voting technology realm, allowing access to
the general public is too much.  While it may seem like paranoid
security think, it's becoming increasingly obvious that full ballot
image scans capture a large amount of information.  Much of this
information can be used by adversaries to "deanonymize" ballots; that
is with some prior information, figure out which ballot corresponds to
a specific voter.  I'll give two examples, and I have another, much
more powerful example, that I can't speak about for a couple more
weeks until our researchers go public.

First, if ballot image scans are captured with enough resolution, it
starts to become easy to see the actual individual paper fibers on the
ballot (See Clarkson et al. and Calandrino et al.).  We can construct
a "fingerprint" of that ballot using the unique paper fiber structure
to later be able to pick it out of a shuffled pile of ballots (even if
they've been crumpled, etc.).  So, someone with access to, say, a
voter's blank absentee ballot before they fill it out can potentially
find the completed ballot if they later get access to completed
ballots such that they can read this fingerprint. (On the "good" side,
this will also lead to making counterfeiting money impossible if not
very difficult... e.g., soda machines, etc., can keep a database of
all "fingerprints" of every bill and compare any bill against this
database.)

Second, if a coercer or vote buyer wants to, they can use "pattern
voting attacks" to indicate a specific ballot belongs to a specific
voter (See Rescorla).  The coercer would tell a voter, "Vote for
Lincoln, but vote this unique pattern on the other contests on the
ballot."  It's not hard to do the math and realize that the number of
unique combinations on many of our rather-compliated US ballots could
be used easily to signal "hey, here's my ballot".  This is a very hard
attack to protect against, although there are some neat cryptographic
methods to do so. (Note that even releasing simply the cast vote
records in a jurisdiction could cause problems here.)

Finally, there is a much more powerful technique here that I cannot
talk about but will send a note when the Princeton researchers go
public.

In short, limited disclosure of ballot image scans and cast vote
records is a very important part of robust ballot secrecy.

best, Joe

References:

* Clarkson et al., "Fingerprinting Blank Paper Using Commodity
Scanners", http://citp.princeton.edu/pub/paper09oak.pdf
* Calandrino et al., "Some Consequences of Paper Fingerprinting for
Elections", http://www.usenix.org/event/evtwote09/tech/full_papers/calandrino.pdf
* Rescorla, "Understanding the Security Properties of Ballot-Based
Verification Techniques",
http://www.usenix.org/event/evtwote09/tech/full_papers/rescorla-ballot.pdf

--
Joseph Lorenzo Hall
ACCURATE Postdoctoral Research Associate
UC Berkeley School of Information
Princeton Center for Information Technology Policy
http://josephhall.org/



-- 
Joseph Lorenzo Hall
ACCURATE Postdoctoral Research Associate
UC Berkeley School of Information
Princeton Center for Information Technology Policy
http://josephhall.org/