In this course, you'll learn what every citizen should know about the security risks--and future potential — of electronic voting and Internet voting. We'll take a look at the past, present, and future of election technologies and explore the various spaces intersected by voting, including computer security, human factors, public policy, and more.
Post-Election Auditing
Loading...
来自 University of Michigan 的课程
数字民主安全
92 个评分
从本节课中
New Technology and Policy
Lessons learned
与讲师见面
J. Alex HaldermanAssociate Professor
Electrical Engineering and Computer Science
When there's a close election, something we often see afterwards is a scene like
this, a manual recount of the ballots cast in the election.
And recounts like this are both an important security feature and a potential
opportunity to employ technology to make the process better.
A recount is an important security feature, because in any kind of counting
process we're likely to see some fraction of votes be counted in error.
This is true no matter what the voting technology.
It's just in a complex process involving thousands of locations.
Some votes are going to be misplaced. Some are going to be misinterpreted.
Some are going to be lost. And a manual recount is an opportunity to
check up on the whole process. Some voting systems like DREs provide very
limited opportunities for a recount. If there's a recount in a place involving
DRE's, what election officials are actually doing is just pressing the print
button again. Maybe they're going to check their
arithmetic, adding up the totals from the different machines, but there's no
opportunity to actually go into the machine and evaluate each ballot
individually, since the, the software in the machine, if it was dishonest, will
have changed all of the records. The most time-consuming audits, but also,
recounts rather, but also the most thorough, are ones that are involving paper
ballots. Recounts of paper ballots can be time
consuming and costly, and so there are rules in place about when they occur.
Most states have a law that invokes a mandatory recount of, of all the ballots
in the election. If the margin of victory is smaller than a
certain predetermined threshold. Also in most jurisdictions, candidates, or
sometime voters can request a recount if they're willing to pay for it.
Usually the State will refund the cost of the recount in the event that the election
outcome changes. But it's still a big gamble for whoever's
making the request. That cost can be very high when it comes
to recounting paper ballots. Figures from different sources vary and it
depends a bit on what you are taking into account.
But the quest to manually recount a paper ballot can be any where from 10's of cents
to more than a dollar, and in a large election, that can very quickly add up.
So the cost, the cost can be prohibitive to manual recounts in large jurisdictions.
Now a related topic to recounting is the idea of post-election auditing, which
involves very much the same process of going back and having people review
physical records of some of the votes. Now let me explain why post-election
audits are an extremely valuable security feature.
So in a, a system that provides auditability, like a precinct count
optical scan voting system, we end the election with two sets of records.
We have a set of paper ballots, which are slow and expensive to recount manually,
but are verified by the voter. So in some ways these are the strongest
evidence we have of the voter's intent. On the other hand, we also have a computer
record, an electronic record in a, in a memory card, say.
This is fast and easy to count, because it's a computer record.
But it's not verified by the voter. This kind of redundancy between different
records, which, as I explained earlier in the course also have very different
security properties and failure modes, offers us a chance to get much greater
security for the whole system. However this redundancy is only useful if
we check both records to make sure they agree, and checking these records for
consistency is the role of a manual audit. So, a manual audit is a process that can
be conducted after the election, but before the final results are declared, and
it involves spot checking the ballots to make sure that the computer records and
the paper records agree. Unlike a, a recount which usually takes
place, throughout the entire jurisdiction, and involves all the ballots, a
post-election audit usually involves selecting a random subset of all of the
precincts, and then just counting the pieces of paper in those precincts to
check whether they agree or disagree with the computer records in those places.
If there's a disagreement, we can elevate to a recount of all the ballots across the
entire jurisdiction. One important criteria for this, though,
is that the places that we're going to audit have to be picked randomly.
We can't announce in advance where the audits are going to be held, or anyone
who's going to commit fraud would just make sure the fraud was committed in
places that weren't going to be audited. Furthermore, there have been documented
cases where election officials, in order to avoid a wider recount, went and checked
the ballots in certain jurisdictions beforehand in secret.
And then announced that those were the places that were going to be audited,
after they knew that they weren't any discrepancies that were going to be
revealed. So those kinds of shenanigans can be
avoided if we carefully come up with procedures for randomly selecting where
the audit locations will be. One way to do this, that's frequently
talked about is to, to use stock market closing prices on the day, on the day, the
day before the audit is going to be held. That way its going to be very hard to
predict or manipulate which set of, of places is going to be a subject to the
audit. Another question is how much do we need to
audit? How many precincts, for instance?
And the standard practice is to use a fixed fraction of the precincts, say, ten
percent of them, selected at random. This has some problems, though.
A better alternative would be to fix the level of statistical confidence we're
shooting for. Say we want to, audit enough that we'll be
99 percent confident that the outcome is correct.
If we just audit a fixed fraction of precincts, we're either going to be
counting too many votes or not enough votes to reach a given target level of
confidence. Because the level of confidence we get
from auditing, say, ten percent of precincts, depends on the size of those
precincts, the number of votes, the margin of victory, and other factors like that.
So, the recommended practice is to fix a level of confidence and then audit until
you get to it. This idea of picking a level of confidence
leads to the idea of a statistical risk- limiting audit.
That is, you audit until you can establish with your given level of confidence that
hand counting all of the paper records would yield the same winner as the
electronic tally. A couple of states have implemented pilot
programs with statistical risk-limiting audits, and I'm hoping that the majority
of states follow suit in the near future. So let me give you an example of an audit
that we can use to see how statistical risk-limiting audits might work and ways
that technology can make them much more efficient.
So in our example, we have candidates Alice and Bob.
And Alice has gotten 55 percent of the votes, and Bob has gotten 45.
What we want to do in this audit is reject the hypothesis that more than five percent
of ballots differ between the paper and electronic records.
So we're going to pick some precincts. In order to get 95 percent confidence,
let's say we're going to have to pick 60 precincts and hand-count the ballots in
those places. The problem with this is going to be the
cost. If those precincts are large, auditing 60
precincts might cost, say, $100,000. We'll see an example than can reduce these
figures in a few minutes. So there's an alternative approach that
can make these costs much lower. So rather than picking whole precincts and
auditing there, which is the standard practice today, we could try to pick
individual ballots and just make sure that those individual ballots agree between the
paper and electronic records. Let me give you some intuition for why
this is much more efficient. On the left here, you see 100 marbles,
let's say those are standing in for precincts.
Ten percent of the marbles are blue, which are precincts where error or fraud
occurred. On the right you see 6300 beads, again
with ten percent of them blue. These represent individual ballots and
ballots with error or fraud. So if we sample ten percent from each of
these sets of things, in which case are we going to have a greater likelihood of
finding a blue unit? In which case is our ten percent audit
more likely to turn up fraud? So the question is how large a sample do
we need to draw from each of them to reach our given statistical, confidence level?
And the sample you're going to have to draw from the marbles is going to be a
much higher percentage than the sample you have to draw from the beads.
So if we apply this intuition to, to auditing, and come back to our example, we
can see that if we move from auditing precincts to auditing ballots, we can
drastically reduce the cost. Because using ballot based audit, we might
only have to look at 60 ballots from in, across the entire jurisdiction.
This would reduce the cost from $100,000 to way less than $1,000.
So, what's the problem though with the idea of a ballot based audit of sampling
individual ballots to get to a statistical level of confidence?
The problem is that we need some way, to match records from the computers from the
electronic count to individual ballots. You have to have two things that allegedly
agree according to the computers, to check that they actually do.
One way to get this would be to have serial numbers printed on all of the
ballots and to record those along with the votes that the machine thinks are on each
ballot. But this creates a privacy problem.
It's difficult to establish this correspondence in a way that doesn't
compromise the secret ballot. So now I'm going to show you a new idea
that came out of some of my earlier research, that is one way we can perform
an audit with a more efficient ballot-based way without compromising the
secret ballot. And this is very interesting because it
involves a way that we can use machines in the process without having to trust them.
So what we begin with is the results from the election.
Let's say we have a set of paper ballots and a set of computer totals.
So, this is our starting point for the audit.
And what we want to do is establish that the paper ballots and the computer totals
are in agreement. So the first thing we're going to do is
check that the electronic records match the paper records and we'll do this using
something I call a recount machine. This could be an off the shelf commercial
scanner hooked up to a PC running special software.
And its job is to scan in all the ballots and produce two set of records as a
result. First it's going to produce a computer
file that has the votes from each ballot individually together with a new number,
the ballot number. Second, it's going to print on each of the
ballots as it's being scanned that same ballot number.
So it's going to number the ballots, and produce a computer record that has, for
each ballot number, the votes that were recorded there.
Now, we're doing this as a separate process after original voting.
Because that way the ballots have already been shuffled, the order has been lost.
Privacy has been protected. But if we scan them the second time, after
the real count, now we have an opportunity to enumerate them, and to produce this
kind of record. So we'll take that electronic record from
the recount machine and we'll compare it to the records from the initial count.
If there's any mismatch, we need to do a manual recount.
But if the records agree, we're good, right? Well, actually we have one problem which
is that we need a way to know that the recount machine wasn't lying to us, that
it was more honest. Why should we blindly trust that machine
if we weren't going to trust the optical scanners or whatever machines produced the
initial count? But using ballot based auditing measures,
we can verify that it's behaving correctly.
So the second step is that we're going to audit the recount machine by selecting
random ballots from the pile for human inspection.
So we actually select records then pull the corresponding ballots out of the pile,
and make sure that they agree with the records that the recount machine produced
for those same ballots. So looking at this whole process, we can
see that there's really two steps. We're going to do a machine recount,
coupled with a ballot-based manual audit. So this is really neat to me because this is
a way we can use a machine in the election process without having to trust it at all
since we can manually verify that it was behaving honestly.
This kind of technology can significantly reduce the amount of work we have to do to
perform a post election audit. Let's take, as an example, the 2006
Virginia US Senate race. There was a .3 percent margin of victory.
So this is a very close election, and if we want to establish with 99 percent
confidence that the result is correct with a traditional precinct-based audit, we'd
have to have people look at more than 1,000,000 ballots.
With a machine-assisted audit, we can reduce that number to just a bit more than
2,000 ballots. So, this is an incredible savings in terms
of the amount of time, and, and, and money and human effort that has to go into the
process. And it comes without having to trust the
technology at all. Other researchers have spent a lot of time
trying to think of efficient rules for figuring out how many ballots have to be
audited. Using, ballot based audits like this.
And have come up with heuristics that are, are really smart.
It, it turns out that if you look at the contents of the ballot, for instance, you
can reduce the, the number even further. These kinds of reductions are being
coupled with very easy to use heuristics for, for determining that, that number of
ballots you have to look at. So all of this work is going into trying
to make sure that the, the procedures are easy for election officials to follow.
And simple to write into, into election system procedures.
So I hope that ballot based audits like this, and routine post-election auditing.
Will become a much bigger part of election practice in the future.
This is especially important because it's, it's part of what's probably the gold
standard in election technology today. Precinct count optical scan ballots, paper
ballots scanned at the polling place, coupled with a mandatory risk limiting
post election audit that occurs before the election results are declared.
This is about as good as we know how to do in terms of all of the properties we want
from elections based on available technology today.
