RE: Barcode Redux

From: John Payson <jpayson_at_circad_dot_com>
Date: Mon Jun 07 2004 - 19:58:36 CDT

>>
This seems like a useful thought. How deep should such a "pre-casting"
inspection go? If there is both human-readible text and a bar code, should
both be inspected for gunk? I'm assuming this would be a inspection done by a
memory-less machine, otherwise there would be privacy issues.
<<

First of all, if the current plan is to do any sort of scanning of the ballots
as they are cast, I don't see any reason why having the ballot scanned more
thoroughly to ensure there are no stray marks would pose any additional privacy
risks.

As for the throughness of inspection, my own personal feeling is that there
should be no way for any invalid ballot to get into the ballot stream without
the complicity of at least one election official or else a concerted effort
which should draw the attention of an honest official [if 0.1% of machines are
broken in such a way as to have a 10% chance of accepting a spoiled ballot,
enough people trying to cast enough spoiled ballots would eventually get one
through, but such numbers of people trying to cast spoiled ballots should be in
and of itself suspicious.]

>From what I can see, there are four things that need to be assured to have a
proper election:

-1- The ballots in the ballot-stream are the ballots actually cast, and contain
the choices the voters actually marked.

-2- The votes are in fact tabulated accurately. This may be assured even with
black-box machines, provided that certain safeguards are included [described
below]. Because these safeguards will work even if the machines have been
tampered with, it would be worthwhile to include them even in an open-source
implementation.

-3- There is no way for anyone to prove how a particular person voted without
that person's consent, unless the election results are unanimous. This and the
last point are the hardest things to assure. Open-source software AND HARDWARE
are necessary for this, and even those are insufficient to provide absolute
assurance since there are many ways hardware could be tampered with.

-4- There is no way for anyone to prove how a particular person voted, even
with that person's consent, unless the election results are unanimous.

Point #2 is the one I find most interesting, because even if all the voting
machines are black boxes, it's possible to have a system where any interested
person can be assured that all the ballots are counted accurately, without
having to compromise anyone's anonymity, given only the requirements that (1)
the paper ballots themselves are proof against undetectable alteration or
substitution, and (2) no defective ballots will be accepted into the ballot
stream.

The protocol would be as follows:

-1- Each ballot, when cast, is marked with indelible ink in such a way that
adding any more ink would invalidate it. On a "selection-dot" style ballot,
this could be handled by having an explicit "No candidate selected" item in
each race (and, in "vote for two" races, a "Less than two candidates selected"
dot; in "vote for three" races, a "Less than three candidates selected" dot,
etc.).

-2- Ballots would be fed into a scanner which would only accept ballots all of
whose marked dots were solid and all of whose unmarked dots were blank. This
scanner would mark each ballot with a randomly-generated unique-ID for each
race on the ballot. The scanner would then scan to ensure the marking was
successful; if not, the ballot would be apologetically rejected.

-3- Following the election, a list would be published for each race, listing
all the ballots cast in that race. Each entry would contain the race-specific
uniqueID for the ballot and the vote associated with that uniqueID. Note that
the lists would not convey any information which could be used directly or
indirectly to identify voters, since the uniqueID's in different races would
not be correlated; the lists would provide no information about what
combinations of candidates were voted for, aside from such implications as
could be drawn by the counts themselves (e.g. if 80% of voters voted for Adam
in one race, and 60% for Bob in another, then at least 40% must have voted for
Adam and Bob).

-4- Over the next few hours or days, a participatory means would be used to
select from the lists some number of ballots for each race (say 200 if the race
was decided by a margin of over 1%, or 200/p for races decided by a margin of
p% for p<1). There are a number of means which would allow any and all
interested persons to ensure that the ballots were in fact chosen randomly.

-5- The selected ballots would be examined to confirm validity and to confirm
that they precisely matched their associated computer records.

If 1% of the ballots in a large election are mistabulated (whether by design or
accident), a sampling of 200 ballots will likely discover one. If ballot-box
scanners are designed to reject any ballots that are even remotely unclear,
there should be no reason for any mistabulated ballots to exist. If any are
discovered, QC methods should be used to determine whether they represent a
fluke or part of a larger pattern.

Although parts of the protocol may seem a little bit complicated, the
assignment of ID's to ballots, publication of lists, and participatory
generation of random numbers are all necessary to ensure that ballots are
indeed selected randomly. Other methods of selection would allow someone to
cheat undetectably.

For example, suppose the protocol were to randomly select a paper ballot and
then examine its computer record. In this case, corrupt officials could
program the voting machines to assign duplicated id's to some--even many--of
the ballots selecting a particular disliked candidate. If there are 1,000,000
ballots in an election, of which 100,000 are duplicates of another 100,000, one
could easily pull out 200 or even 20,000 ballots without any of those
duplicating each other. For every duplicated ballot-id, the election official
could create a fictitious ballot-id which voted for the official's preferred
candidate. Selecting paper ballots at random and checking them against
computer records would not show any irregularity unless one happened upon two
ballots with identical ID's; random sampling would be unlikely to discover such
duplication.

By contrast, if the ballot id's are selected from the published list, such
shenanigans are impossible, since any interested person can inspect the
published list of ballot id's and confirm that they are all unique.
==================================================================
= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
==================================================================
Received on Wed Jun 30 23:17:11 2004

This archive was generated by hypermail 2.1.8 : Wed Jun 30 2004 - 23:17:29 CDT