Punchscan
Encyclopedia
Punchscan is an optical scan vote counting system
invented by cryptographer David Chaum
. Punchscan is designed to offer integrity, privacy, and transparency. The system is voter-verifiable, provides an end-to-end (E2E) audit
mechanism, and issues a ballot receipt
to each voter. The system won grand prize at the 2007 University Voting Systems Competition
.
The computer software
which Punchscan incorporates is open source
; the source code
was released on 2 November 2006 under a revised BSD licence. However, Punchscan is software independent; it draws its security from cryptographic functions instead of relying on software security like DRE voting machine
s. For this reason, Punchscan can be run on closed source operating system
s, like Microsoft Windows
, and still maintain unconditional integrity.
The Punchscan team, with additional contributors, has since developed Scantegrity
.
A Punchscan ballot
has two layers of paper. On the top layer, the candidates are listed with a symbol
or letter
beside their name. Below the candidate list, there are a series of round holes in the top layer of the ballot. Inside the holes on the bottom layer, the corresponding symbols are printed.
To cast a vote for a candidate, the voter must locate the hole with the symbol corresponding to the symbol beside the candidate's name. This hole is marked with a Bingo
-style ink dauber, which is purposely larger than the hole. The voter then separates the ballot, chooses either the top or the bottom layer to keep as a receipt
, and shreds
the other layer. The receipt is scanned
at the polling station for tabulation
.
The order of the symbols beside the candidate names is generated pseudo-randomly
for each ballot, and thus differs from ballot to ballot. Likewise for the order of the symbols in the holes. For this reason, the receipt does not contain enough information to determine which candidate the vote was cast for. If the top layer is kept, the order of the symbols through the holes is unknown. If the bottom layer is kept, the order of the symbols beside the candidates name is unknown. Therefore the voter cannot prove to someone else how they voted, which prevents vote buying
or voter intimidation.
and Pepsi
, as illustrated in the preceding diagram. The order of the letters beside the candidates' names could be A and then B, or B and then A. We will call this ordering
, and let 
=0 for the former ordering and 
=1 for the latter. Therefore,
: order of symbols beside candidate list,
.
Likewise we can generalize for other parts of a ballot:
: order of symbols through the holes,
.
: which hole is marked,
.
: result of the ballot,
.
Note that the order of the candidates' names are fixed across all ballots. The result of a ballot can be calculated directly as,
(Equation 1)
However when one layer of the ballot is shredded, either
or 
is destroyed. Therefore there is insufficient information to calculate 
from the receipt (which is scanned). In order to calculate the election results, an electronic database
is used.
Before the election, the database is created with a series of columns as such. Each row in the database represents a ballot, and the order that the ballots are stored in the database is shuffled
(using a cryptographic key that each candidate can contribute to
). The first column,
, has the shuffled order of the serial numbers. 
contains a pseudorandom bitstream
generated from the key, and it will act as a stream cipher
.
will store an intermediate result. 
contains a bit such that:
The result of each ballot will be stored in a separate column,
, where the order of the ballots will be reshuffled again. Thus 
contains the row number in the 
column where the result will be placed.
After the election is run and the
values have been scanned in, 
is calculated as:
And the result is calculated as,
This is equivalent to equation 1,
The result column is published and given the ballots have been shuffled (twice), the order of the results column does not indicate which result is from which ballot number. Thus the election authority cannot trace votes to serial numbers.
candidates, the above procedure is followed using modulo
-n equations.
Any voter or interested party can also inspect part of the database to ensure the results were calculated correctly. They cannot inspect the whole database, otherwise they could link votes to ballot serial numbers. However, half of the database can be safely inspected without breaking privacy. A random choice is made between opening
or 
(this choice can be derived from the secret key or from a true random source, such as dice
or the stock market
). This procedure allows the voter to be confident that the set of all ballots were counted as cast.
If all ballots are counted as cast and cast as intended, then all ballots are counted as intended. Therefore the integrity of the election can be proven to a very high probability.
, 
, and 
in the database are all generated pseudorandomly, multiple databases can be created with different random values for these columns. Each database is independent of the others, allowing the first half of some of the databases to be opened and inspected and the second half of others. Each database must produce the same final tally. Thus if an election authority were to tamper with the database to skew the final tally, they would have to tamper with each of the databases. The probability of the tampering being uncovered in the audit increases exponentially with the number of independent databases. With even a modest number of databases, the integrity of the election is probabilistically certain.
to the unique information contained on each ballot and in the databases. This is accomplished by applying a cryptographic one-way function
to the information. Though the result of this function, the commitment, is made public, the actual information being committed to remains sealed. Because the function is one-way, it is computationally infeasible to determine the information on the sealed ballot given only its publicly posted commitment.
Vote counting system
There exist various methods through which the ballots cast at an election may be counted, prior to applying a voting system to obtain one or more winners.-Manual counting:Manual counting requires a physical ballot that represents voter intent...
invented by cryptographer David Chaum
David Chaum
David Chaum is the inventor of many cryptographic protocols, including blind signature schemes, commitment schemes, and digital cash. In 1982, Chaum founded the International Association for Cryptologic Research , which currently organizes academic conferences in cryptography research...
. Punchscan is designed to offer integrity, privacy, and transparency. The system is voter-verifiable, provides an end-to-end (E2E) audit
End-to-end auditable voting systems
End-to-end auditable or end-to-end voter verifiable systems are voting systems with stringent integrity properties and strong tamper-resistance. E2E systems often employ cryptographic methods to craft receipts that allow voters to verify that their votes were not modified, without revealing which...
mechanism, and issues a ballot receipt
End-to-end auditable voting systems
End-to-end auditable or end-to-end voter verifiable systems are voting systems with stringent integrity properties and strong tamper-resistance. E2E systems often employ cryptographic methods to craft receipts that allow voters to verify that their votes were not modified, without revealing which...
to each voter. The system won grand prize at the 2007 University Voting Systems Competition
University Voting Systems Competition
The University Voting Systems Competition, or VoComp is an annual competition in which teams of students design, implement, and demonstrate open-source election systems. The systems are presented to a panel of security expert judges. The winners are awarded a cash prize provided by the sponsors...
.
The computer software
Computer software
Computer software, or just software, is a collection of computer programs and related data that provide the instructions for telling a computer what to do and how to do it....
which Punchscan incorporates is open source
Open source
The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
; the source code
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
was released on 2 November 2006 under a revised BSD licence. However, Punchscan is software independent; it draws its security from cryptographic functions instead of relying on software security like DRE voting machine
DRE voting machine
A direct-recording electronic voting machine records votes by means of a ballot display provided with mechanical or electro-optical components that can be activated by the voter ; that processes data by means of a computer program; and that records voting data and ballot images in memory components...
s. For this reason, Punchscan can be run on closed source operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
s, like Microsoft Windows
Microsoft Windows
Microsoft Windows is a series of operating systems produced by Microsoft.Microsoft introduced an operating environment named Windows on November 20, 1985 as an add-on to MS-DOS in response to the growing interest in graphical user interfaces . Microsoft Windows came to dominate the world's personal...
, and still maintain unconditional integrity.
The Punchscan team, with additional contributors, has since developed Scantegrity
Scantegrity
Scantegrity is a security enhancement for optical scan voting systems, providing such systems with end-to-end verifiability of election results. It uses confirmation codes to allow a voter to prove to themselves that their ballot is included unmodified in the final tally. The codes are...
.
Voting procedure
Ballot
A ballot is a device used to record choices made by voters. Each voter uses one ballot, and ballots are not shared. In the simplest elections, a ballot may be a simple scrap of paper on which each voter writes in the name of a candidate, but governmental elections use pre-printed to protect the...
has two layers of paper. On the top layer, the candidates are listed with a symbol
Symbol
A symbol is something which represents an idea, a physical entity or a process but is distinct from it. The purpose of a symbol is to communicate meaning. For example, a red octagon may be a symbol for "STOP". On a map, a picture of a tent might represent a campsite. Numerals are symbols for...
or letter
Letter (alphabet)
A letter is a grapheme in an alphabetic system of writing, such as the Greek alphabet and its descendants. Letters compose phonemes and each phoneme represents a phone in the spoken form of the language....
beside their name. Below the candidate list, there are a series of round holes in the top layer of the ballot. Inside the holes on the bottom layer, the corresponding symbols are printed.
To cast a vote for a candidate, the voter must locate the hole with the symbol corresponding to the symbol beside the candidate's name. This hole is marked with a Bingo
Bingo (US)
Bingo is a game of chance played with randomly drawn numbers which players match against numbers that have been pre-printed on 5x5 matrices. The matrices may be printed on paper, card stock or electronically represented and are referred to as cards. Many versions conclude the game when the first...
-style ink dauber, which is purposely larger than the hole. The voter then separates the ballot, chooses either the top or the bottom layer to keep as a receipt
End-to-end auditable voting systems
End-to-end auditable or end-to-end voter verifiable systems are voting systems with stringent integrity properties and strong tamper-resistance. E2E systems often employ cryptographic methods to craft receipts that allow voters to verify that their votes were not modified, without revealing which...
, and shreds
Paper shredder
A paper shredder is a mechanical device used to cut paper into chad, typically either strips or fine particles. Government organizations, businesses, and private individuals use shredders to destroy private, confidential, or otherwise sensitive documents...
the other layer. The receipt is scanned
Optical reader
An optical reader is a device found within most computer scanners that captures visual information and translates the image into digital information the computer is capable of understanding and displaying....
at the polling station for tabulation
Vote counting system
There exist various methods through which the ballots cast at an election may be counted, prior to applying a voting system to obtain one or more winners.-Manual counting:Manual counting requires a physical ballot that represents voter intent...
.
The order of the symbols beside the candidate names is generated pseudo-randomly
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
for each ballot, and thus differs from ballot to ballot. Likewise for the order of the symbols in the holes. For this reason, the receipt does not contain enough information to determine which candidate the vote was cast for. If the top layer is kept, the order of the symbols through the holes is unknown. If the bottom layer is kept, the order of the symbols beside the candidates name is unknown. Therefore the voter cannot prove to someone else how they voted, which prevents vote buying
Electoral fraud
Electoral fraud is illegal interference with the process of an election. Acts of fraud affect vote counts to bring about an election result, whether by increasing the vote share of the favored candidate, depressing the vote share of the rival candidates or both...
or voter intimidation.
Tabulation procedure
As an example, consider a two candidate election between CokeCoca-Cola
Coca-Cola is a carbonated soft drink sold in stores, restaurants, and vending machines in more than 200 countries. It is produced by The Coca-Cola Company of Atlanta, Georgia, and is often referred to simply as Coke...
and Pepsi
Pepsi
Pepsi is a carbonated soft drink that is produced and manufactured by PepsiCo...
, as illustrated in the preceding diagram. The order of the letters beside the candidates' names could be A and then B, or B and then A. We will call this ordering
, and let =0 for the former ordering and =1 for the latter. Therefore,: order of symbols beside candidate list,.Likewise we can generalize for other parts of a ballot:
: order of symbols through the holes,.: which hole is marked,.: result of the ballot,.Note that the order of the candidates' names are fixed across all ballots. The result of a ballot can be calculated directly as,
(Equation 1)However when one layer of the ballot is shredded, either
or is destroyed. Therefore there is insufficient information to calculate from the receipt (which is scanned). In order to calculate the election results, an electronic databaseDatabase
A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
is used.
Before the election, the database is created with a series of columns as such. Each row in the database represents a ballot, and the order that the ballots are stored in the database is shuffled
Random permutation
A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and simulation...
(using a cryptographic key that each candidate can contribute to
Key-agreement protocol
In cryptography, a key-agreement protocol is a protocol whereby two or more parties can agree on a key in such a way that both influence the outcome. If properly done, this precludes undesired third-parties from forcing a key choice on the agreeing parties...
). The first column,
, has the shuffled order of the serial numbers. contains a pseudorandom bitstreamBitstream
A bitstream or bit stream is a time series of bits.A bytestream is a series of bytes, typically of 8 bits each, and can be regarded as a special case of a bitstream....
generated from the key, and it will act as a stream cipher
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
.
will store an intermediate result. contains a bit such that:The result of each ballot will be stored in a separate column,
, where the order of the ballots will be reshuffled again. Thus contains the row number in the column where the result will be placed.After the election is run and the
values have been scanned in, is calculated as:And the result is calculated as,
This is equivalent to equation 1,
The result column is published and given the ballots have been shuffled (twice), the order of the results column does not indicate which result is from which ballot number. Thus the election authority cannot trace votes to serial numbers.
Generalized form
For an election with candidates, the above procedure is followed using moduloModulo operation
In computing, the modulo operation finds the remainder of division of one number by another.Given two positive numbers, and , a modulo n can be thought of as the remainder, on division of a by n...
-n equations.
Basic auditing procedures
The voter's ballot receipt does not indicate which candidate the voter cast their ballot for, and therefore it is not secret information. After an election, the election authority will post an image of each receipt online. The voter can look up her ballot by typing in the serial number and she can check that information held by the election authority matches her ballot. This way, the voter can be confident that her ballot was cast as intended.Any voter or interested party can also inspect part of the database to ensure the results were calculated correctly. They cannot inspect the whole database, otherwise they could link votes to ballot serial numbers. However, half of the database can be safely inspected without breaking privacy. A random choice is made between opening
or (this choice can be derived from the secret key or from a true random source, such as diceDice
A die is a small throwable object with multiple resting positions, used for generating random numbers...
or the stock market
Stock market
A stock market or equity market is a public entity for the trading of company stock and derivatives at an agreed price; these are securities listed on a stock exchange as well as those only traded privately.The size of the world stock market was estimated at about $36.6 trillion...
). This procedure allows the voter to be confident that the set of all ballots were counted as cast.
If all ballots are counted as cast and cast as intended, then all ballots are counted as intended. Therefore the integrity of the election can be proven to a very high probability.
Additional security
To further increase the integrity of a Punchscan election, several further steps can be taken to protect against a completely corrupt election authority.Multiple databases
Since, , and in the database are all generated pseudorandomly, multiple databases can be created with different random values for these columns. Each database is independent of the others, allowing the first half of some of the databases to be opened and inspected and the second half of others. Each database must produce the same final tally. Thus if an election authority were to tamper with the database to skew the final tally, they would have to tamper with each of the databases. The probability of the tampering being uncovered in the audit increases exponentially with the number of independent databases. With even a modest number of databases, the integrity of the election is probabilistically certain.Commitments
Prior to an election, the election authority prints the ballots and creates the database(s). Part of this creation process involves committingCommitment scheme
In cryptography, a commitment scheme allows one to commit to a value while keeping it hidden, with the ability to reveal the committed value later. Commitments are used to bind a party to a value so that they cannot adapt to other messages in order to gain some kind of inappropriate advantage...
to the unique information contained on each ballot and in the databases. This is accomplished by applying a cryptographic one-way function
One-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...
to the information. Though the result of this function, the commitment, is made public, the actual information being committed to remains sealed. Because the function is one-way, it is computationally infeasible to determine the information on the sealed ballot given only its publicly posted commitment.
Ballot inspection
Prior to an election, twice as many ballots are produced than the number intended to use in the election. Half of these ballots are selected randomly (or each candidate could choose a fraction of the ballots) and opened. The rows in the database corresponding to these selected ballots can be checked to ensure the calculations are correct and not tampered with. Since the election authority does not know a priori which ballots will be selected, passing this audit means the database is well formed with a very high probability. Furthermore, the ballots can be checked against their commitments to ensure with high probability that the ballot commitments are correct.External links
- Project home page
- Vocomp Submission — a comprehensive 80-page document explaining all aspects of the system
- Electronic Democracy — BBC WorldBBC WorldBBC World News is the BBC's international news and current affairs television channel. It has the largest audience of any BBC channel in the world...
's Digital PlanetDigital PlanetClick is a BBC radio programme broadcast on the BBC World Service and sister radio show to BBC News' Click TV....
audio interview with David ChaumDavid ChaumDavid Chaum is the inventor of many cryptographic protocols, including blind signature schemes, commitment schemes, and digital cash. In 1982, Chaum founded the International Association for Cryptologic Research , which currently organizes academic conferences in cryptography research...
. - Making Every E-vote Count — IEEE SpectrumIEEE SpectrumIEEE Spectrum is a magazine edited by the Institute of Electrical and Electronics Engineers. The IEEE's description of it is:IEEE Spectrum began publishing in January 1964 as a successor to Electrical Engineering...
. - Transparent and Open Voting with Punchscan: Part I and Part II
- Future Tense audio interview with David ChaumDavid ChaumDavid Chaum is the inventor of many cryptographic protocols, including blind signature schemes, commitment schemes, and digital cash. In 1982, Chaum founded the International Association for Cryptologic Research , which currently organizes academic conferences in cryptography research...
.