Punch scan

Punch scan
Basic data
Maintainer	Richard Carback , David Chaum , Jeremy Clark , Aleks Essex , and Stefan Popoveniuc .
operating system	Cross-platform
programming language	Java
category	cryptographic voting method
License	Revised BSD license
http://punchscan.org/

Punchscan is a cryptographic method for electronically assisted execution of electoral processes using paper-based ballot while maintaining the secrecy of the ballot . The method presented has similarities to the implementation of voting processes by means of bingo voting .

The process is based on the counting of votes or data acquisition from ballot papers using an optical scanner and was first implemented by David Chaum , a US researcher in cryptography .

Punchscan is designed to provide integrity , confidentiality and transparency for the handling of elections . A special feature of the procedure is the possibility of subsequently checking, using a document - which every voter receives - whether their own votes were counted correctly. Punchscan enables a security audit for all phases of this process and especially for the phase of counting votes.

Open source software is used to implement Punchscan . The source code was released on November 2, 2006 under the revised open source license BSD . The Punchscan process is in principle software-independent and is therefore not like z. B. Voting computers rely on information security ; rather, it derives its special properties for the security of the voting process from cryptographic functions. This means that Punchscan can also be used on operating systems that are not open source (e.g. Windows and Mac OS ) and still retain their full security integrity.

Punchscan itself is no longer being developed or maintained, but will be used in the follow-up project Scantegrity .

Ballot papers and voting process

The two-part punchscan ballot. Complete note (above), both partial notes (below).

A punchscan ballot consists of two layers of paper . The top paper layer of the ballot shows the names of the possible election candidates marked with a symbol (here with the letters A and B). Below the list of candidates there are an equal number of punched-out open viewing windows . All symbols used for the upper paper layer are printed on the lower paper layer of the voting slip so that they appear exactly in the viewing windows of the upper paper layer.

A person entitled to vote casts their vote as follows:

1. He looks for the name of the candidate he would like to vote for in the top layer of paper on the ballot slip
2. Now he selects the viewing window whose contents contain the same symbol that can be found next to the name of the selected candidate
3. The selected viewing window is now stamped with a color stamp (similar to the bingo game ), which covers a little more area than the viewing window itself; thus a stamped window border also remains on the upper paper layer
4. The person entitled to vote now separates the upper paper layer of the voting slip from the lower one and freely chooses which paper layer he would like to keep as evidence of his election. The voter destroys the other remaining paper layer in a paper shredder
5. The person entitled to vote has his stored receipt electronically recorded by a scanner in the polling station so that his participation and his vote can be counted

Voting secrecy is ensured by a special procedure in the Punchscan process: pseudo-random . The assignment of the symbols to the names of the election candidates takes place pseudo-randomly and is therefore different from ballot to ballot. The same applies to the order in which the symbols are distributed over the open viewing windows.

The voting slip therefore does not contain any information as to which candidate the eligible voter has cast his vote for. If the voter keeps the top layer of paper on the ballot, it is not possible to tell which order the symbols had in the open viewing windows during the voting process. If the voter keeps the lower layer of paper, it is not possible to see what assignment the symbols had to the names of the candidates during the election process. The person entitled to vote cannot even prove to a third party who they have voted for, regardless of which paper they keep as evidence for themselves.

Vote counting

The counting is illustrated by an example: There is a choice between exactly two candidates, namely Coke and Pepsi , as can be seen in the illustration of the punchscan ballot. The order of the letters next to the names of the candidates can be A and then B, or B first and then A.

Special form for 2 election candidates

From now on we will name the sequence of letters next to the candidate names . ${\displaystyle P_{1}}$

The equation = 0 then corresponds to the first possible order and = 1 describes the remaining order. The following applies: ${\displaystyle P_{1}}$ ${\displaystyle P_{1}}$

${\displaystyle P_{1}}$: Order of the symbols next to the names of the candidates,

${\displaystyle P_{1}=\{0,1\}=\{{\mbox{AB}},{\mbox{BA}}\}\,}$.

This results in generalized for other parts of the ballot:

${\displaystyle P_{2}}$: Sequence of symbols in the open viewing windows,

${\displaystyle P_{2}=\{0,1\}=\{{\mbox{AB}},{\mbox{BA}}\}\,}$.

${\displaystyle P_{3}}$: marked open viewing window,

${\displaystyle P_{3}=\{0,1\}=\{{\mbox{1st}},{\mbox{2nd}}\}\,}$.

${\displaystyle R}$: possible results of the voting slip,

${\displaystyle R=\{0,1\}=\{{\mbox{Coke}},{\mbox{Pepsi}}\}\,}$.

Important note: the order of the names of the candidates is exactly the same on all ballot papers. The result of counting exactly one ballot can be calculated as follows:

${\displaystyle R=P_{1}+P_{2}+P_{3}{\bmod {2}}\,}$		(Equation 1)

However, since either the top or bottom layer of paper on the voting slip is destroyed in a paper shredder as part of the voting process, either or no longer exists after the voting process. ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$

In order therefore to calculate missing information, the scanned document election alone is therefore not sufficient for a result determination. Further information is necessary in order to be able to count the votes; this is stored in a database. ${\displaystyle R}$

Before an election is made, a specific set of columns is created in a database - the data is organized in columns and rows. Each line of data then represents a voting slip. The order in which the ballot information is stored in the database is determined at random using a cryptographic key that each candidate can determine himself through the participation in a key exchange protocol . The first column contains the randomly distributed serial numbers. Contains a pseudo-random bit sequence that was generated with the help of the cryptographic key and is used for stream encryption . only saves the intermediate result. contains a bit for which the following relationship applies: ${\displaystyle D_{1}}$ ${\displaystyle D_{2}}$ ${\displaystyle D_{3}}$ ${\displaystyle D_{4}}$

${\displaystyle D_{2}+D_{4}=P_{1}+P_{2}{\bmod {2}}\,}$

The result of each ballot paper is in turn stored in a column in which the sequence of the ballot paper results is determined again at random. finally contains the line number in which the result was stored in. ${\displaystyle R}$ ${\displaystyle D_{5}}$ ${\displaystyle R}$

After the dialing processes have been completed and the values ​​for have been scanned, the following can be determined: ${\displaystyle P_{3}}$ ${\displaystyle D_{3}}$

${\displaystyle D_{3}=P_{3}+D_{2}{\bmod {2}}\,}$

The result is calculated as follows:

${\displaystyle R=D_{3}+D_{4}{\bmod {2}}\,}$

This is equivalent to equation 1:

${\displaystyle {\begin{aligned}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{aligned}}}$

The values ​​of the result column are published. If the order of the ballot papers (represented by the data lines) was swapped accidentally twice, the order of the results does not give any indication of which result is to be assigned to which ballot paper. Thus, even an implementing institution with sovereignty over the database could not associate the votes cast with the serial numbers of the ballot papers.

Generalized form for n election candidates

For an election with candidates, the above calculation takes place with modulo -n equations. ${\displaystyle n}$

Basic security audit

The paper layer chosen by the voter, which he kept as a receipt, does not contain any direct information about what he has chosen, but it does contain a serial number. The receipt does not contain any secret or confidential information about the selected candidates. After the voting has been completed, the election organizer can publish the content of the other paper layer - which was optically scanned - online. Each voter can then check by entering the serial number of his paper receipt whether the content of the scanned paper layer matches the actual vote, which is then based on the paper receipt retained by the voter z. B. can be checked at home on the computer. This is the first time to check. This does not guarantee whether the optical scanning process actually recorded the voice correctly or whether the recorded voice was also counted.

Every voter and every other interested party can check the contents of the database (security audit) and thus check whether the results have been calculated correctly. However, not all of the information in the database can be checked, as otherwise a connection between the serial number and the registered voter could be established. Election secrecy would then no longer be guaranteed.

This problem is countered with a random mechanism that randomly selects and checks half of all database contents. This would still ensure voting secrecy and manipulations would be detected if they were included in the random selection.

Specifically, the following happens: The inspection is randomly selected by or (the random selection can e.g. be derived from a secret key, or better still, a non-deterministic random number generator , such as a dice or the stock index ). This form of auditing excludes that the candidate selection is manipulated by individual ballot papers. ${\displaystyle \{D_{1},D_{2},D_{3}\}}$ ${\displaystyle \{D_{3},D_{4},D_{5}\}}$

The entire security audit indicates the correctness of the choice if:

• All voting papers submitted were included in the count.
• The candidate chosen was actually evaluated for each ballot.
• If all the slips of paper have been counted and the candidate actually chosen has been counted, then it has been counted correctly.

In this case, the integrity of the choice made is very likely to be unimpaired.

Extra security

In order to ensure the security of an election with Punchscan ballot papers, various other measures can be taken to prevent a possible manipulation attempt by the organizers of the election.

Multiple databases

As the information , and in the ballot database are all generated, including pseudo-randomly, multiple databases may exist in parallel, with again different pseudo-random information in said data columns. ${\displaystyle D_{1}}$ ${\displaystyle D_{2}}$ ${\displaystyle D_{5}}$

Each database is independent of the others and allows, for example, the open inspection of some randomly selected databases. However, every fully evaluated database must ultimately produce exactly the same vote result. So there is ultimately the same final voting result, only it is available in a completely different structure in each database, so that each database would have to be manipulated in a different way in order to manipulate even one voting slip. The probability of a manipulation being discovered increases exponentially with the number of independent databases used. Even the use of less independent databases increases the security against manipulation of the stored data.

Commitments

As part of the preparation of an election, an institution familiar with this preparation must print the ballot papers and create the database (s). An essential step in the creation of the ballot paper is that the institution uses a cryptographic commitment to commit itself to the unique information that will be contained on each ballot paper and in the database (s). This definition takes place by applying a one-way function to this unique information . Although the picture of this function (the commitment) is published on the ballot, the actual information that was included in the one-way function is computationally sealed. Because of the irreversibility of the one-way function, it is computationally impossible to determine the input information again.

Examination of the voting slip

In the run-up to an election, so many paper-based ballot papers are produced that in the end twice the number of ballot papers is available than should actually be used. The ballot papers actually required are selected at random from the ballot papers produced (e.g. each of the voting parties could choose a proportion of ballot papers - which are to be used for the election - themselves). During the production process of the ballot papers, these were already created as data lines in the database. The selected ballot papers could therefore even be checked again before the actual use, whether they are correctly registered in the database and whether no election results have yet been entered for them.

Since the election workers do not know in advance which half of the ballot paper will actually be used, a successful security audit in the form of a check whether the ballot paper is registered in the database means that there is a very high probability that the database has not been manipulated. As soon as the ballot slip has been scanned and shredded, it can be checked again against the database based on its definition in order to rule out an incorrect definition with a high degree of probability.

criticism

Carrying out a voting process using Punchscan appears to offer significantly more security than processes that rely on so-called voting computers . The devil, however, is in the details and in the cryptographic processes that must be followed properly. These are not readily understood by people who are not trained cryptography experts. This means, however, that this technology for processing an election process is not comprehensible, at least for large parts of the population, and therefore cannot be checked and is therefore not transparent.

Transparency about what exactly is happening, however, is an important criterion for the acceptance of procedures for handling elections. Punchscan can be seen as a successful attempt to create increased security for paper-based voting, for example by making it possible for the voter to verify whether his or her vote was actually counted. However, the punch scan method fails in being easily comprehensible for all voters. A lot of cryptographic substeps are needed to apply the method. The security and verifiability gained, however, depend precisely on these de facto non-transparent steps and can therefore only be viewed to a limited extent as an improvement in electoral processes.

Web links

• Homepage of the Punchscan project
• Vocomp Submission - clearly written 80-page document that describes all aspects of the system (PDF; 2.26 MB) - English
• Electronic Democracy (MP3; 7.2 MB) - BBC World ’s Digital Planet audio interview with David Chaum .
• Making Every E-vote Count - IEEE Spectrum .
• Transparent and Open Voting with Punchscan: Part 1 and Part 2 , 2006
• Future Tense ( Memento from October 14, 2007 in the Internet Archive ) Audio interview with David Chaum .

Individual evidence

1. ↑ Arel Cordero, David Wagner, David Dill: The Role of Dice in Election Audits - Extended Abstract (PDF; 1.0 MB).
2. ↑ Jeremy Clark, Aleks Essex, Carlisle Adams. Secure and Observable Auditing of Electronic Voting Systems using Stock Indices (PDF; 135 kB).