**Preliminary Analysis for Multiple Representations of Ballots in IV
Voting Systems**

**Draft Version March 2, 2005**

**13 November 2023**

**National Institute of Standards and Technology (NIST)**

Provided for consideration by the Technical Guidelines Development
Committee (TGDC) and the Election Assistance Commission under the
requirements of the Help America Vote Act (HAVA) of 2002.

Authority This document has been provided for consideration by the
Technical Guidelines Development Committee (TGDC) and the Election
Assistance Commission under the requirements of the Help America Vote
Act (HAVA) of 2002.

Disclaimer This document is a work in progress, provided solely as draft
input to the TGDC. Portions of this document may change substantially.

**1 Introduction**

Any time a voting system keeps multiple records of the same ballot,
there is an opportunity for these records to disagree. Voting systems
produce multiple representations of the same data for two reasons: to
allow recovery from disaster (such as failure of one memory device) and
to allow recovey from or detection of attempts to tamper with the voting
process. Another note describes the need for future voting systems to
produce multiple records; this note outlines the NIST voting team\'s
approach to writing standards for handling these multiple records.

This note is concerned with multiple representations of the voter\'s
choices which have some independent validity, such as might be found
from an electronic voting system in which the voter verification step
was done on a separate machine from a different manufacturer than the
vote capturing step, and records from each step were preserved. This
note is not concerned with purely derivative records, such as the
electronic records scanned from a sequence of paper ballots with no
voter interaction.

**1.1 Motivating Example**

A simple example can be used to illustrate the discussion in this note:
A voting system consisting of a DRE with a voter-verified paper audit
trail produces both electronic and paper records of the voters\' clearly
indicated choices. When both records arrive at a central counting
facility, they should agree with one another.

There are many ways the records might disagree. For example, mechanical
failure of a printer may cause some paper records to be unreadable, or
damage to a DRE may render its electronic records unreadable.
Alternatively, a disagreement may be introduced by an attacker in an
attempt to alter an election outcome: correct electronic records may
arrive with stuffed boxes full of paper records, or or correct paper
records may arrive with tampered electronic records.

Other voting system architectures have different ways in which the
representations may disagree (for example, in other architectures, all
the representations are electronic), but the underlying issues are the
same whenever multiple representations of the voters\' choices are
produced and counted. The two questions addressed by this note are:

a\. How shall disagreements be detected?

b\. How shall disagreements be resolved?

**1.2 Resolution 21-05:**

Resolution 21-05 says:

> Voting systems may create one or more electronic representations of
> ballots in addition to any paper record produced.. For example, three
> redundant electronic copies may be made, for reliability purposes. As
> another example, the scanning of an op-scan ballot may create another,
> electronic, representation of the ballot. A number of issues are
> related to the use of multiple representations (both electronic and
> paper) that are in some cases relatively new and not completely
> identified or understood, and in other cases need uniform terminology
> and procedures. These issues include: 1.Preventing, detecting, and
> handling disagreements between the representations, in the rare event
> that they should occur, 2.Converting between representations, and
> ensuring that ballots are not multiply converted and counted, 3.Use of
> multiple representations in fraud analysis, 4.Authenticity of the
> representations, 5.Marking of ballot representations with unique
> identifiers, (if and when possible to do so while preserving voter
> privacy), and 6.Conversion to/from standard formats. The TGDC has
> concluded that further research is advisable in identifying potential
> problems associated with voting systems that use multiple
> representations of ballots, and in identifying best approaches for
> handling such problems. The TGDC thus requests that NIST perform such
> research and draft standards documents that reflect NIST\'s
> determination of the best practices and best approaches for handling
> these problems.

**1.3 Summary of Current Thinking at NIST**

The analysis of the NIST voting team on these issues has lead to a
number of preliminary statements which are expected to appear in future
voting standards drafted by NIST:

a\. Disagreements between representations must not be a normal
occurence. Instead, a disagreement between multiple representations must
indicate either some major problem in the voting system (such as a
printer which has stopped working), or an attack.

b\. Normal election procedures must audit the different representations
against one another as part of the normal counting process, so that any
substantial difference between them is very likely to be discovered. The
best techniques for doing this depend on the specific voting
architecture, and the nature of the different representations.

c\. Voter-verifiable paper records which are electronically scanned
produce a distinct electronic representation, which must be audited for
agreement with the human-readable paper.

d\. Each representation used for counting, auditing, and recounting must
be in a fully-specified and public format, which can be exported from
the voting system, and checked and counted independently of any hardware
or software from the voting system vendor.

e\. Each representation must be written and stored in such a way that
accidental errors in writing and reading have a negligible chance of
failing to be detected.

f\. No a priori decision must be made about which representation is to
take precedence in case of disagreement between apparently undamaged
representations.

g\. Voting systems must include a full discussion of disagreements
between multiple representations in their documentation. This discussion
must describe any known or expected error conditions that may lead to
disagreements between representations, and recommended recovery
techniques. It should also discuss known or suspected attack scenarios
that might lead to disagreements.

It is unclear how many of these issues can be addressed in a voting
standard directly. Some may appear as requirements on voting system
documentation. Others may need to be addressed in some other way, such
as proposed guidance on election procedures.

**2 The Problem with \"Ballots of Record\"**

There\'s is a common notion of \"ballots of record\" intended to capture
the idea that there is one true representation of the voters\' choices
to which the voting system can return during a recount. This idea makes
sense when discussing paper ballots which are counted after the voting
is done, because there is really only one original representation of the
voters\' choices, in the paper ballots. Electronic counting of those
ballots results in the creation of a derivative electronic record, and
since the scanning of paper ballots is an error-prone process, each new
attempt to count the ballots electronically leads to a slightly
different electronic representation. However, that electronic record has
no validity independent of the validity of the paper record. The paper
record is the only original evidence of the voters\' choices in this
case, and so it must take precedence over these derived records.

This notion does not make sense for voting systems which create multiple
representations of the voters\' choices which have independent validity
during the voting process, however. A DRE that creates multiple
electronic copies, a DRE with voter-verified paper, a frog voting system
such as that recommended in the MIT/Caltech report, all create multiple
representations of the voters\' clearly expressed choices at the time of
the vote. Any of these representations might be correct.

Return to the motivational example of a DRE with voter-verified paper
trail. Securing the electronic memory of the DRE is a difficult task,
and it\'s hard to be sure it\'s been done well, especially in the face
of corrupt insiders at the voting system vendor. Securing the paper
records is also a difficult task, especially in the face of corrupt
local election officials. The thing that makes a DRE with VVPAT
potentially much more secure than a straight DRE or a straight paper
system is that the attackers have to compromise two independent records,
and the insiders most likely to be able to compromise one probably
can\'t compromise the other. If both records are checked against each
other in the normal process of counting votes, an attacker who can
compromise only one set of records knows that he is overwhelmingly
likely to get caught, if he tries to alter the outcome of the election.

**3 Garbled and Destroyed Records: Distinguishing Error from Fraud**

There are two broad ways a disagreement between records can show up:
Either there are some obviously-wrong records (missing, garbled, or
otherwise nonsensical), or there aren\'t. If one representation is
obviously damaged, this requires some investigation into the causes, but
makes it pretty easy to guess which records are more reliable. For
example, if the printer runs out of ink during the middle of an
election, there may be a few printed ballots which aren\'t readable,
before some voter calls it to the attention of an election official.
There\'s no confusion about whether the paper records in this case have
been tampered with to make them cast a different vote than intended;
they\'ve simply been lost.

When there are records which are garbled, the question to ask from a
security perspective is whether this could be part of an attack. The
part of this question that is easy to address in a standard (and without
doing some kind of forensics on the other record) is to ask:

a\. How many records are garbled? Is it enough to have a significant
impact on the final count? If not, then the garbled records are probably
not an issue in security terms.

b\. Are the damaged or missing records plausibly the result of an error,
or are they evidence of some kind of tampering or attack?

If the damage is consistent with random errors or known equipment
failures, and the missing records aren\'t widespread enough to
substantially change the election results, then the lost records may be
ignored. The important point, though, is that when there are substantial
records missing or damaged from one representation, this cannot just be
handled automatically. Election officials must be informed of the
disagreement between records, and must decide how to proceed. The voting
system, in turn, must give some guidance about how to proceed in its
documentation, particularly by noting the known sources of innocent
disagreements between records, such as occasional printer failures.

**3.1 Requirements from this Analysis**

Distinguishing between accidental garbling of records, intentional
garbling of records, and more subtle tampering with records is an
important part of securing a voting system. The following requirements
come out of the above discussion and analysis:

a\. Errors in records shall be as rare as possible, given the normal
constraints on component reliability. Printed records should employ
whatever redundancy is sensible (error-correcting codes, high-density
two-dimensional barcodes) to achieve high reliability.

b\. Accidental garbling of records in any representation must be
virtually certain to be detected. This imposes requirements on both the
encoding of the records (e.g., using error-correcting codes to make
undetected accidental errors astronomically unlikely) and the normal
counting and auditing procedures, which must detect garbled and missing
records in any representation as part of detecting disagreements between
records.

**4 Disagreement Among Plausible Records**

Disagreement between plausible records occurs when two or more
representations disagree, but neither shows obvious signs of damage or
failure. This must not occur in the normal course of events, and it must
be detected with high probability in the normal procedures of counting
and auditing. A disagreement between plausible records does not leave a
clear answer to the question of what the election results should be, and
can\'t leave a clear answer.

Again, return to the example of a DRE with voter verifiable paper. The
paper ballots indicate that John Smith won the election with 55% of the
vote, but the electronic records indicate that Mary Jones won with 55%.
How can election officials resolve this situation?

A moment\'s reflection shows that there is not enough information in
this example to decide how to resolve it. The paper trail may have been
tampered with, or the electronic records may have been tampered with, or
the electronic records may have been altered by some kind of error. (A
good voting system design must make this last kind of error extremely
rare.) Some kind of investigation into the cause of the disagreement is
necessary to determine what has happened, and thus, what records may be
trusted. It may be that no investigation can determine which
representation is correct.

If one representation of the voters\' choices is not counted or audited
against the other unless there is a recount, then there is a substantial
chance that the disagreement will never be detected. This takes away
much of the security advantage of having multiple representations, and
NIST intends to draft standards which will not allow such an approach in
future voting systems.

If one representation always dominates in disagreements, then an
attacker need only tamper with that one representation to change the
outcome of the election.

**4.1 Lessons from this Analysis**

A few high-level requirements can be drawn from this analysis:

a\. Disagreements between plausibly-correct representations must be
detected in the normal course of counting and auditing votes.

b\. Substantial disagreements between plausibly-correct representations
must not be a normal occurrence in a voting system; in all cases, such
disagreements must demonstrate either an attempt to change the outcome
of an election illegally, or a critical error in the voting system.

c\. There is no a priori way to decide which representation is accurate.
Any attempt to decide this ahead of time makes an attack on the voting
system much easier, since the attacker knows which one representation he
must compromise.

**5 Detecting Disagreements**

Detecting disagreements between representations can be done in three
ways: By counting both representations, direct comparison of records,
and statistical sampling. A combination of these methods allows for
meaningful audit of one representation of voter choices by another.

The counting and auditing procedures of the voting system must be open
to public scrutiny. For this reason, the records must be exportable from
the voting system in a public and open format which can be read and
processed by other programs and hardware.

**5.1 Counting Both Representations**

If the representations are all electronic, they can be expected to have
extremely low error rates\--so low that in the course of a normal
election, no errors of reading, writing, or counting records are
expected. In this case, it is natural to simply count the results of
both representations.

If no errors are expected (this should be easy to achieve in
all-electronic representations), then the counts must match exactly or
they cannot be assumed to agree. If some error rate is accepted for the
records, then the counts must match to within a margin of error based on
that error rate. Note that the acceptable margin of error between the
two representations is also the acceptable margin of fraud between the
two\--an attacker tampering with one representation can escape detection
up to about half the margin of error on average.

For paper records which are scanned into an electronic format,
error-correcting codes and related techniques can eliminate errors based
on misreading a paper record (i.e., the paper record says \"John Smith\"
but the electronic one says \"Mary Jones\", but cannot eliminate errors
in which the paper record simply could not be read. Thus, the error rate
in the case of properly written paper records will be the rate of
missing records.

**5.2 Direct Comparison**

If the records carry unique identifiers (note that this can be done
without compromising voter privacy), then lists of the records from two
or more representations can be compared. Any discrepancy is noted.

When paper records are scanned into an electronic format and subjected
to direct comparison, missing records are noted instantly. Further, any
changed record is noted. An attacker tampering with the paper records
cannot affect the electronic version of those records without a
discrepancy being detected, except within the bounds of acceptable lost
records from the scanning process.

**5.3 Statistical Sampling**

Agreement between representations can be checked by statistical
sampling. This makes sense mainly for paper ballots. However, this has
to be done in a sensible way. As the paper by Neff shows, simply
statistically sampling records and recounting them is not especially
effective at detecting fraud. To use statistical sampling in an
effective way, unique identifiers must appear linking the records in
different representations.

One valuable application of statistical sampling is to verify that the
human-readable version of paper records corresponds to the electronic
version that is scanned in. A few hundred samples which are hand-checked
by humans can verify this to within a very small percentage of altered
or incorrect ballots. (By contrast, recounts of small samples of ballots
tend to provide very little assurance that votes haven\'t been changed
between the records.)

Statistical sampling can detect altered and inserted records, as well as
records that have been replaced by copies of other legitimate records,
but cannot easily detect deleted records. Other techniques must be used
to detect deleted records, based on counting or direct comparison.

**5.4 Requirements from the Analysis**

a\. Voting systems which use any representation with a non-negligible
error rate shallput an unambiguous ID string on each ballot record, so
that a given record has the same ID string in all representations. This
facilitates comparisons between the records.

b\. Human-readable paper records which are scanned electronically
produce a new representation, which shall be checked against the
original. Statistical sampling of paper ballots, and human verification
that the machine-readable parts correspond to the electronic records, is
a workable solution.

c\. The right auditing and counting procedures change depending on error
rates and the types of errors expected in a given representation.

**6 Conclusions**

This note has described the NIST voting team\'s current thinking on the
handling of multiple representations in voting systems. More specific
details of handling these issues for voter-verified paper audit trail
systems is described in the VVPAT draft. More specific details of
creating multiple representations of the kind discussed in this note
appear in the DV/IV note