Punchscan

Last updated
Punchscan
Punchscan logo.png
Developer(s) Richard Carback, David Chaum, Jeremy Clark, Aleks Essex, and Stefan Popoveniuc.
Stable release 1.0 (November 2, 2006) [±]
Preview release 1.5 (July 16, 2007) [±]
Written in Java
Operating system Cross-platform
Available inEnglish
Type vote counting system
License Revised BSD license
Website http://punchscan.org/

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.

Contents

The computer software which Punchscan incorporates is open-source; the source code was released on 2 November 2006 under a revised BSD licence. [1] However, Punchscan is software independent; it draws its security from cryptographic functions instead of relying on software security like DRE voting machines. For this reason, Punchscan can be run on closed source operating systems, like Microsoft Windows, and still maintain unconditional integrity.

The Punchscan team, with additional contributors, has since developed Scantegrity.

Voting procedure

A marked Punchscan ballot. Full ballot (top), separated ballot (bottom). Marked ballot.jpg
A marked Punchscan ballot. Full ballot (top), separated ballot (bottom).

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.

Tabulation procedure

As an example, consider a two candidate election between Coke 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.

Generalized form

For an election with candidates, the above procedure is followed using modulo-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 dice [2] or the stock market [3] ). 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 committing 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.

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

Related Research Articles

Quadratic reciprocity theorem

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:

Single transferable vote Proportional representation voting system

The single transferable vote (STV) is a proportional voting system designed to achieve or closely approach proportional representation through voters ranking candidates in multi-seat organizations or constituencies. There are various ways of counting votes under STV, as described below.

Atbash is a monoalphabetic substitution cipher originally used to encrypt the Hebrew alphabet. It can be modified for use with any known writing system with a standard collating order.

David Chaum cryptographer

David Lee Chaum is an American computer scientist and cryptographer. He is known as a pioneer in cryptography and privacy-preserving technologies, and widely recognized as the inventor of digital cash. His 1982 dissertation "Computer Systems Established, Maintained, and Trusted by Mutually Suspicious Groups" is the first known proposal for a blockchain protocol. Complete with the code to implement the protocol, Chaum's dissertation proposed all but one element of the blockchain later detailed in the Bitcoin whitepaper.

In social choice theory, the Gibbard–Satterthwaite theorem is a result published independently by philosopher Allan Gibbard in 1973 and economist Mark Satterthwaite in 1975. It deals with deterministic ordinal electoral systems that choose a single winner. It states that for every voting rule, one of the following three things must hold:

  1. The rule is dictatorial, i.e. there exists a distinguished voter who can choose the winner; or
  2. The rule limits the possible outcomes to two alternatives only; or
  3. The rule is susceptible to tactical voting: in certain conditions some voter's sincere ballot may not defend their opinion best.
Blind signature form of digital signature in which the content of a message is disguised (blinded) before it is signed

In cryptography a blind signature, as introduced by David Chaum, is a form of digital signature in which the content of a message is disguised (blinded) before it is signed. The resulting blind signature can be publicly verified against the original, unblinded message in the manner of a regular digital signature. Blind signatures are typically employed in privacy-related protocols where the signer and message author are different parties. Examples include cryptographic election systems and digital cash schemes.

In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic curve cryptography.

The affine is a type of monoalphabetic substitution cipher, where each letter in an alphabet is mapped to its numeric equivalent, encrypted using a simple mathematical function, and converted back to a letter. The formula used means that each letter encrypts to one other letter, and back again, meaning the cipher is essentially a standard substitution cipher with a rule governing which letter goes to which. As such, it has the weaknesses of all substitution ciphers. Each letter is enciphered with the function (ax + b) mod 26, where b is the magnitude of the shift.

The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of integer factorization. However the Rabin cryptosystem has the advantage that it has been mathematically proven to be computationally secure against a chosen-plaintext attack as long as the attacker cannot efficiently factor integers, while there is no such proof known for RSA. It has the disadvantage that each output of the Rabin function can be generated by any of four possible inputs; if each output is a ciphertext, extra complexity is required on decryption to identify which of the four possible inputs was the true plaintext.

The Paillier cryptosystem, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n-th residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.

Doomsday rule Way of calculating the day of the week of a given date

The Doomsday rule is an algorithm of determination of the day of the week for a given date. It provides a perpetual calendar because the Gregorian calendar moves in cycles of 400 years. The algorithm for mental calculation was devised by John Conway in 1973, drawing inspiration from Lewis Carroll's perpetual calendar algorithm. It takes advantage of each year having a certain day of the week, called the doomsday, upon which certain easy-to-remember dates fall; for example, 4/4, 6/6, 8/8, 10/10, 12/12, and the last day of February all occur on the same day of the week in any year. Applying the Doomsday algorithm involves three steps: Determination of the anchor day for the century, calculation of the doomsday for the year from the anchor day, and selection of the closest date out of those that always fall on the doomsday, e.g., 4/4 and 6/6, and count of the number of days between that date and the date in question to arrive at the day of the week. The technique applies to both the Gregorian calendar and the Julian calendar, although their doomsdays are usually different days of the week.

The Schulze method is an electoral system developed in 1997 by Markus Schulze that selects a single winner using votes that express preferences. The method can also be used to create a sorted list of winners. The Schulze method is also known as Schwartz Sequential dropping (SSD), cloneproof Schwartz sequential dropping (CSSD), the beatpath method, beatpath winner, path voting, and path winner.

In number theory, the Kronecker symbol, written as or , is a generalization of the Jacobi symbol to all integers . It was introduced by Leopold Kronecker.

The Tonelli–Shanks algorithm is used in modular arithmetic to solve for r in a congruence of the form r2n, where p is a prime: that is, to find a square root of n modulo p.

The digital root of a natural number in a given number base is the value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached.

End-to-end auditable or end-to-end voter verifiable (E2E) 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 counted as cast, without revealing which candidates were voted for. As such, these systems are sometimes referred to as receipt-based systems.

Prêt à Voter is an E2E voting system devised by Peter Ryan of the University of Luxembourg. It aims to provide guarantees of accuracy of the count and ballot privacy that are independent of software, hardware etc. Assurance of accuracy flows from maximal transparency of the process, consistent with maintaining ballot privacy. In particular, Prêt à Voter enables voters to confirm that their vote is accurately included in the count whilst avoiding dangers of coercion or vote buying.

Schulze STV is a draft ranked voting system designed to achieve proportional representation. It is a single transferable vote (STV) voting system. It was invented by Markus Schulze who developed the Schulze method for resolving ties under the Condorcet method. It is similar to CPO-STV in that it compares possible winning sets of candidate outcomes pairwise and selects the Condorcet winner. However, unlike CPO-STV, it only compares outcomes that differ by a single candidate. Comparing outcomes that differ by more than one candidate is accomplished by finding the strongest path.

Bingo voting is an electronic voting scheme for transparent, secure, end-to-end auditable elections. It was introduced in 2007 by Jens-Matthias Bohli, Jörn Müller-Quade, and Stefan Röhrich at the Institute of Cryptography and Security (IKS) of the Karlsruhe Institute of Technology (KIT).

Hare–Clark electoral system voting system used in Tasmania and the Australian Capital Territory

Hare-Clark is a type of single transferable vote electoral system of proportional representation used for elections in Tasmania and the Australian Capital Territory. The method for the distribution of preferences is similar to other voting systems in Australia, such as for the Australian Senate.

References

  1. Punchscan School Election System Goes Open Source Archived 2007-09-28 at the Wayback Machine . IT Business Edge
  2. Arel Cordero, David Wagner, and David Dill. The Role of Dice in Election Audits -- Extended Abstract.
  3. Jeremy Clark, Aleks Essex, Carlisle Adams. Secure and Observable Auditing of Electronic Voting Systems using Stock Indices [ permanent dead link ].