RE: Spoiled ballots, forged ballots, destroyed ballots

From: John Payson <jpayson_at_circad_dot_com>
Date: Fri Jun 11 2004 - 21:15:15 CDT

Put together a well-thought out, consistent, and complete description
of your ideas, and you'll get a better hearing. Some of us have been
working on this for years. Some ideas we've adopted when suggested,
like the bar code. Other ideas, we've rejected.

All right, here we go.

To start with, at the time ballots enter the ballot box, they should be
confirmably valid. This may be accomplished either via captive printer
assembly, or by having the ballot box scan ballots before accepting them.
Ballots should contain machine-readable voting information, coded in such a way
that the votes cannot be altered without rendering the ballot invalid (this may
or may not be intrinsic in all barcode formats; a code-39 "percent sign", for
example, could be altered into some other characters). The machine should also
confirm that the ballot is free of any marks other than those necessary to
legitimately represent votes (a captive printer assembly would probably not
need this check).

Upon acceptance, the ballot would then be marked with a unique-ID for each race
on it (for example, if the ballot contained votes for President/VP, Senator,
and Representative, there would be three uniqueID's generated, one for each
race). The unique ID's could identify the voting station where the ballot was
deposited, but indicate nothing about the order cast. Memory is sufficiently
cheap that the voting station could select ID's at random, using a checklist to
avoid duplication. The uniqueID's would not be visible or obtainable by the
voter; the machine would record the uniqueID's along with the ballots cast, but
in such a way as to not record the order in which they were cast. This would
be one spot where open-source verification of software would be useful [a
conspiracy between machine providers and election officials would make it
possible to illicitly record the order in which voters were cast regardless of
the election methodology used, so the fact that open-source doesn't provide
absolute assurance against that isn't an objection].

Following the election, a list would be published by election officials for
each race, in unique-ID order, listing for each ballot its uniqueID applicable
to that race and the vote cast in that race. Any interested party could run
this list through a simple program to confirm that reported election totals
correctly match the records in the list, and to confirm that all the
unqiqueID's in the list are distinct. The list would not provide any improper
information about voting patterns, since the uniqueID's on each race would be
assigned independently. Indeed, the list would impart no information at all to
anyone except as required in the following procedure.

Concurrent with the publication of the lists, all ballots would be fed through
a scanner which would verify that they had been recorded correctly 'the first
time'. Unlike the initial scanning (where the ballots were scanned in the
order cast, but stored in random order), the ballots would be scanned in random
order, but recorded in the order in which they were scanned.

Following the publication of the lists, election officials would solicit all
interested parties to perform the following six-step process (the process could
be started at any time, but step 5 must occur after the publication of the

 -1- Generate a list of 10,000 nine-digit numbers by any desired means.

 -2- Generate a digital signature for the list using some agreed-upon
     open-source program.

 -3- Submit the list to election officials by a certain deadline.

 -4- Receive from election officials a file containing all submitted
     digital signatures.

 -5- Submit to election officials, before a second deadline, the list
     of numbers from which the signature was generated.

 -6- Receive from election officials a list of the signatures for which
     a valid follow-up list file was received, and have the option to
     request any portion of any list file.

After this, all lists for which valid signatures had been received would be
summed row-wise into a new list (the first number in the new list would be the
sum of the first numbers of all lists; likewise the second number, third
number, etc.) A single number generated by some agreeably
random event (e.g. lottery drawing) would determine the starting index within
the list.

If the margin of the election was e.g. 1%, the procedure to verify a particular
race would then be to take 200 items from the summed list starting at the
randomly-generated index, take them modulo the number of voters in that race,
and use those numbers as indices into the original vote records. For example,
if there were 2,399,191 voters in a particular race and the sum of all the
submitted numbers was 492,199,491,395 then (because 492,199,491,395 mod
2,399,191 is 659,363) the 659,364th voting record would be taken from the list.
It might indicate that unique-ID 592-391-5992 voted for Fred Quimby. To
confirm that, the ballot would be physically pulled and inspected (using the
list generated by the first 'rescan' to locate the physical ballot quickly).

Even in a California statewide race, inspecting 200 ballots would be sufficient
to show that the total number of miscounted ballots (or fraudulent ballots that
wouldn't withstand inspection) amounts to less than 1% of the total; inspecting
2,000 ballots would shoe that it amounts to less than 0.1% of the total.

In the event that discrepancies are found, then protocols become a little more
complicated and following reconciliation there may be a need for more random
sampling, preferably starting over with step -1- of the random number
generation procedure (to avoid giving any corrupt officials too much advance
knowledge of which ballots will be inspected).

One of the key features of this proposal is that there is no way that any
collusion of corrupt officials and corrupt machinery can alter election results
by more than a certain percentage without running a high risk of detection,
other than by physically altering ballots. There is no need for anyone to
trust any software other than what he runs on his own machine (for signature
generation or verification). Any interested person can ensure that the "random
sampling" of ballots is indeed random. And because only a small number of
ballots will need to be inspected, it becomes practical to actually perform a
careful inspection.

A few points which may not be obvious:

-1- The publication of the list of ballot-id's prior to the selection of
    random numbers is necessary to ensure that all ballots are in fact
    eligible for the random sampling. If the list were not published
    before the numbers were generated, a corrupt official who knew some
    ballots were misrecorded could adjust the list so as to ensure that
    all of the selected uniqueID's corresponded to valid ballots, even
    if none of the others did.

-2- The assignment of a separate uniqueID for each race is necessary to
    ensure that "interesting" combinations of votes on ballots are not
    available to the general public [e.g. to ensure that someone isn't
    told that there had better be a ballot listing Quimby as mayor, Fred
    Jones as Dog Catcher, Bob Smith as First Assistant Dog Catcher, etc.
    as a means of ensuring that person voted for Quimby].

-3- It is necessary that ballots be chosen by selecting a uniqueID and
    pulling the paper ballot rather than by choosing a random paper
    ballot and checking it against the computer because while it is
    possible (and easy) for all interested persons to ensure that the
    uniqueID's in the computer list are all unique, such people cannot
    ensure that is true of the ballots themselves.

    If the checking was done by selecting paper ballots and comparing
    them against computer records, it would be possible for crooked
    election equipment to steal every other vote for the non-preferred
    candidate by printing on its ballot the same uniqueID as the last
    (recorded) vote for that candidate and then generating a new fake
    voting record with a uniqueID somehow derived from the real one and
    with a vote for the preferred candidate. If the equipment maker
    included the same cheat in the "recount" scanner, this cheat would
    go undetected unless two paper ballots, pulled at random, happened
    to have the same uniqueID. Although this would--if it happened--
    prove that the election was rigged, the odds of pulling two ballots
    with matching uniqueID's when each uniqueID is only used twice are
    extremely remote.

-4- The protocol of having people submit lists of numbers is one of many
    means of allowing all interested parties to a supposedly-random event
    to ensure its randomness. Other means may be better, but a key
    aspect of this method is that if anyone generates his list of numbers
    randomly and keeps it confidential until all the signatures have been
    submitted, no amount of collusion by other people can cause the final
    list to be non-random. Any alternate means of choosing random ballots
    should have this feature.

The only significant additional expenses of using this approach would be (1) It
would likely be necessary for all ballots to get scanned twice; with automated
scanning equipment this should not be difficult and may be a good idea in any
case [if the initial scanner did not record what it scanned, the ballots would
only be scanned once]. (2) It would be necessary to host some data on the web
or in some otherwise-accessible format, and to do a little bit of data
processing. The amount of data is not terribly big by most standards though,
so this cost should not be significant. (3) It would be necessary to manually
pull and inspect 200 ballots for an election with a 1% or greater margin, or
2,000 ballots if the margin was 0.1%. Given that the 200/2,000 requirement
would apply even in a California statewide race, the cost of such inspection
seemes like it should be pretty reasonable.

Thus, for a relatively small incremental cost compared with other voting
schemes, computer-assisted vote tabulation can be performed in such a way as to
allow all interested parties to confirm that votes were tabulated correctly
even if they trust no equipment other than their own, and no election -related
personnel other than those inspecting the 200 or 2000 randomly-selected
= 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:13 2004

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