Punchscan
   HOME

TheInfoList



OR:

Punchscan is an optical scan
vote counting system Vote counting is the process of counting votes in an election. It can be done manually or by machines. In the United States, the compilation of election returns and validation of the outcome that forms the basis of the official results is call ...
invented by
cryptographer Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
David Chaum David Lee Chaum (born 1955) is an American computer scientist, cryptographer, and inventor. He is known as a pioneer in cryptography and privacy-preserving technologies, and widely recognized as the inventor of digital cash. His 1982 dissertatio ...
. 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 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 ar ...
. The
computer software Software is a set of computer programs and associated documentation and data. This is in contrast to hardware, from which the system is built and which actually performs the work. At the lowest programming level, executable code consists ...
which Punchscan incorporates is
open-source Open source is source code that is made freely available for possible modification and redistribution. Products include permission to use the source code, design documents, or content of the product. The open-source model is a decentralized sof ...
; the
source code In computing, source code, or simply code, is any collection of code, with or without comments, written using a human-readable programming language, usually as plain text. The source code of a program is specially designed to facilitate the wo ...
was released on 2 November 2006 under a revised
BSD licence BSD licenses are a family of permissive free software licenses, imposing minimal restrictions on the use and distribution of covered software. This is in contrast to copyleft licenses, which have share-alike requirements. The original BSD lic ...
. However, Punchscan is software independent; it draws its security from
cryptographic Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
functions instead of relying on
software security Application security (short AppSec) includes all tasks that introduce a secure software development life cycle to development teams. Its final goal is to improve security practices and, through that, to find, fix and preferably prevent security i ...
like
DRE voting machine A DRE voting machine, or 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. These are typically buttons or a touchscr ...
s. For this reason, Punchscan can be run on
closed source Proprietary software is software that is deemed within the free and open-source software to be non-free because its creator, publisher, or other rightsholder or rightsholder partner exercises a legal monopoly afforded by modern copyright and inte ...
operating system An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs. Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...
s, like
Microsoft Windows Windows is a group of several proprietary graphical operating system families developed and marketed by Microsoft. Each family caters to a certain sector of the computing industry. For example, Windows NT for consumers, Windows Server for serv ...
, and still maintain unconditional integrity. The Punchscan team, with additional contributors, has since developed
Scantegrity Scantegrity is a security enhancement for optical scan voting systems, providing such systems with end-to-end (E2E) verifiability of election results. It uses confirmation codes to allow a voter to prove to themselves that their ballot is included ...
.


Voting procedure

A Punchscan
ballot A ballot is a device used to cast votes in an election and may be found as a piece of paper or a small ball used in secret voting. It was originally a small ball (see blackballing) used to record decisions made by voters in Italy around the 16t ...
has two layers of paper. On the top layer, the
candidates A candidate, or nominee, is the prospective recipient of an award or honor, or a person seeking or being considered for some kind of position; for example: * to be election, elected to an official, office — in this case a Preselection, candida ...
are listed with a
symbol A symbol is a mark, sign, or word that indicates, signifies, or is understood as representing an idea, object, or relationship. Symbols allow people to go beyond what is known or seen by creating linkages between otherwise very different conc ...
or
letter Letter, letters, or literature may refer to: Characters typeface * Letter (alphabet), a character representing one or more of the sounds used in speech; any of the symbols of an alphabet. * Letterform, the graphic form of a letter of the alphabe ...
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 or B-I-N-G-O may refer to: Arts and entertainment Gaming * Bingo, a game using a printed card of numbers ** Bingo (British version), a game using a printed card of 15 numbers on three lines; most commonly played in the UK and Ireland ** Bi ...
-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 A receipt (also known as a packing list, packing slip, packaging slip, (delivery) docket, shipping list, delivery list, bill of the parcel, manifest, or customer receipt) is a document acknowledging that a person has received money or propert ...
, and shreds the other layer. The receipt is scanned at the polling station for
tabulation A table is an arrangement of information or data, typically in rows and columns, or possibly in a more complex structure. Tables are widely used in communication, research, and data analysis. Tables appear in print media, handwritten notes, comp ...
. The order of the symbols beside the candidate names is generated
randomly In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no :wikt:order, order and does not follow an intelligible pattern or combination. Ind ...
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 Vote buying (also referred to as electoral clientelism and patronage politics) occurs when a political party or candidate distributes money or resources to a voter in an upcoming election with the expectation that the voter votes for the actor handi ...
or voter intimidation.


Tabulation procedure

As an example, consider a two candidate election between Coke and
Pepsi Pepsi is a carbonated soft drink manufactured by PepsiCo. Originally created and developed in 1893 by Caleb Bradham and introduced as Brad's Drink, it was renamed as Pepsi-Cola in 1898, and then shortened to Pepsi in 1961. History Pepsi was ...
, 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 P_1, and let P_1=0 for the former ordering and P_1=1 for the latter. Therefore, P_1: order of symbols beside candidate list, :P_1\in\=\\,. Likewise we can generalize for other parts of a ballot: P_2: order of symbols through the holes, :P_2\in\=\\,. P_3: which hole is marked, :P_3\in\=\\,. R: result of the ballot, :R\in\=\\,. Note that the order of the candidates' names are fixed across all ballots. The result of a ballot can be calculated directly as, :R = P_1 + P_2 + P_3\bmod 2\, (Equation 1) However, when one layer of the ballot is shredded, either P_1 or P_2 is destroyed. Therefore, there is insufficient information to calculate R from the receipt (which is scanned). In order to calculate the election results, an electronic
database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
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 Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome. __TOC__ Techniques Overha ...
(using a
cryptographic key A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key c ...
that each candidate can contribute to). The first column, D_1, has the shuffled order of the serial numbers. D_2 contains a pseudorandom
bitstream A bitstream (or bit stream), also known as binary sequence, is a sequence of bits. A bytestream is a sequence of bytes. Typically, each byte is an 8-bit quantity, and so the term octet stream is sometimes used interchangeably. An octet may ...
generated from the key, and it will act as a
stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...
. D_3 will store an intermediate result. D_4 contains a bit such that: :D_2 + D_4 = P_1 + P_2 \bmod 2\, The result of each ballot will be stored in a separate column, R, where the order of the ballots will be reshuffled again. Thus D_5 contains the row number in the R column where the result will be placed. After the election is run and the P_3 values have been scanned in, D_3 is calculated as: :D_3 = P_3 + D_2 \bmod 2\, And the result is calculated as, :R = D_3 + D_4 \bmod 2\, This is equivalent to equation 1, :\begin R &= (D_3) + D_4 \bmod 2\\ &= (P_3 + D_2) + D_4 \bmod 2\\ &= P_3 + (D_2 + D_4) \bmod 2\\ &= P_3 + (P_1 + P_2) \bmod 2 \end 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 n candidates, the above procedure is followed using
modulo In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is t ...
-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 their ballot by typing in the serial number and they can check that information held by the election authority matches their ballot. This way, the voter can be confident that their 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
dice Dice (singular die or dice) are small, throwable objects with marked sides that can rest in multiple positions. They are used for generating random values, commonly as part of tabletop games, including dice games, board games, role-playing g ...
or the
stock market A stock market, equity market, or share market is the aggregation of buyers and sellers of stocks (also called shares), which represent ownership claims on businesses; these may include ''securities'' listed on a public stock exchange, as ...
Jeremy Clark, Aleks Essex, Carlisle Adams
Secure and Observable Auditing of Electronic Voting Systems using Stock Indices
). 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 D_1, D_2, and D_5 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 with the number of independent databases.


Commitments

Prior to an election, the election authority prints the ballots and creates the database(s). Part of this creation process involves committing to the unique information contained on each ballot and in the databases. This is accomplished by applying a cryptographic
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, spe ...
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 as 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.


See also

*
Stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...
*
Commitment scheme A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later.Oded Goldreich (2001). Foundations of Crypt ...
*
Zero-knowledge proof In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information a ...


References

{{reflist, 2


External links


Project home page

Vocomp Submission
— a comprehensive 80-page document explaining all aspects of the system
Electronic Democracy
BBC World BBC World News is an international English-language pay television network, operated under the ''BBC Global News Limited'' division of the BBC, which is a public corporation of the UK government's Department for Digital, Culture, Media and S ...
's
Digital Planet ''Digital Planet'' (previously known as ''Click'' and originally ''Go Digital'') is a radio programme broadcast on the BBC World Service presented by Gareth Mitchell. Alternating as contributors are Bill Thompson, Ghislaine Boddington and Angel ...
audio interview with
David Chaum David Lee Chaum (born 1955) is an American computer scientist, cryptographer, and inventor. He is known as a pioneer in cryptography and privacy-preserving technologies, and widely recognized as the inventor of digital cash. His 1982 dissertatio ...
.
Making Every E-vote Count
IEEE Spectrum ''IEEE Spectrum'' is a magazine edited by the Institute of Electrical and Electronics Engineers. The first issue of ''IEEE Spectrum'' was published in January 1964 as a successor to ''Electrical Engineering''. The magazine contains peer-revie ...
. * Transparent and Open Voting with Punchscan
Part I
an
Part II

Future Tense
audio interview with
David Chaum David Lee Chaum (born 1955) is an American computer scientist, cryptographer, and inventor. He is known as a pioneer in cryptography and privacy-preserving technologies, and widely recognized as the inventor of digital cash. His 1982 dissertatio ...
. Electronic voting methods Applications of cryptography