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.

Post-Election Auditing

数字民主安全

与讲师见面