Punchscan

Punch Scan is a cryptographic method for electronically supported execution of electoral processes by means of paper-based ballots while preserving secrecy of the ballot. The presented method has similarities to the conduct of electoral processes by Bingo Voting.

The method is based on a vote-counting and data collection of ballots by optical scanner and was first implemented by David Chaum, a U.S. researcher in cryptography.

Punch scan was developed to provide integrity, confidentiality and transparency for the administration of elections. A special feature of the method is the possibility on the basis of a document - which every voter receives - to be able to also check afterwards whether its own electoral vote was counted correctly. Punch scanning thus allows a safety audit for all phases of this process and in particular for the phase of the counting of votes.

For the realization of Punch scan open source computer software is used. The source code was released on November 2, 2006 under the revised BSD open source license. However, the Punch scan method is in principle independent of any software, and is therefore not such as voting machines rely on information security; it derives its special properties for the security of the voting process rather from cryptographic functions. This means that Punch scanning and may get into operating systems are used, which are not open source (such as Windows and Mac OS) and still retains its full safety integrity.

Punch scan itself is no longer developed and maintained, but is used in the follow-up project Scantegrity.

• 4.1 Several databases
• 4.2 Commitments
• 4.3 Examination of the ballot

Ballots and election process

A Punch scan ballot consists of two layers of paper. The upper layer of the ballot paper shows the names of possible candidates for elections marked with an icon (indicated by the letters A and B). Below the list of candidates there are an equal number of round punched open view windows. On the lower paper layer of the ballot all used symbols of the upper layer of paper are printed so that they appear exactly in the viewing windows of the upper paper layer.

A voter casts his vote as follows:

The secrecy of the ballot is ensured by a special procedure for Punch scan method: the pseudo-random. The assignment of symbols to the names of candidates for election takes place here pseudo-randomly and is thus of ballot ballots differently. The same is true for the order of the distribution of the symbols to the open window.

The election document thus contains no information for which election candidates the voters his voice did. Retains the voters, the upper layer of the ballot paper, it is not clear what order were the symbols in the electoral process in the open view windows. Retains the voters, the lower layer of paper is not clear which assignment had the symbols to the names of candidates for election in the electoral process. So the voters can not even prove a third party for whom he voted, no matter what he paper sheet for yourself reserves as evidence.

Counting of votes

The counting is illustrated by an example: There is a choice place between exactly two election candidates, namely Coke and Pepsi, as seen in the figure of Punch scan ballot. The order of the letters next to the names of election candidates on the one hand and then be A A and B, or B first.

Special shape for two election candidates

The letter sequence in addition to the candidates' names we call from now.

The equation = 0 then corresponds to the first possible order and = 1 describes the remaining order. Thus, the following applies:

: Order of icons next to the names of election candidates,

It follows the case for the other parts of the ballot:

: Order of icons in the open view windows,

: Labeled open window,

: Possible results of the ballot,

Important Note: The order of the names of election candidates on all ballots exactly the same. The election results of counting exactly one ballot can thus be calculated as follows,

(Equation 1)

However, either the upper or the lower paper layer of the ballot will be destroyed in a paper shredder in the context of the electoral process, either exists or after the election process no longer.

So to calculate missing information, the scanned document selection alone is therefore not sufficient for a determination result. Another information is necessary in order to count out the voices, these can be stored in a database.

The data organized in columns and rows - - a specific amount of columns generated before an election is in a database. Each row of data then represents a ballot. The order in which the ballot information is stored in the database is randomly fedtgelegt, using a cryptographic key to each election candidate can determine through participation in a key exchange protocol itself. The first column contains the distributed randomly serial numbers. includes a pseudo-random bit sequence generated using the cryptographic key and is used for a stream cipher. only stores the intermediate result. contains a bit for the following relationship applies:

The result of each ballot in turn is stored in a column in which the order of the ballot results is determined again by chance. finally contains the line number in which the result was stored in.

After the elections will be terminated and the values ​​were scanned for, can be determined as follows:

The result is calculated as follows:

This is equivalent to Equation 1:

The values ​​of the result column is published. Were the ballot (represented by the rows of data ) exchanged twice selected at random in order, are the order of the results no indication what the result is assigned to which ballot. Thus, an implementing institution with authority over the database could not be reconciled with the serial numbers of the ballot in connection the votes cast.

Generalized form for n election candidates

For an election with candidates the above computation with modulo n equations takes place.

Basic safety audit

Chosen by election participants layer of paper, which he has kept as evidence, contains no direct information about what he has chosen, but this includes a serial number. However, the document contains any secret or to be kept secret information about the selected candidates. After the completion of the ballot submission of election authority can display the contents of the other layer of paper - published online - which was optically scanned. Each voter can check whether the contents of the scanned paper layer coincides with the actual voting, which can then be checked against the paper receipt retained by the voters, for example, at home on the computer then by entering the serial number of his paper document. In this way is possible to investigate first whether the optical scanning has captured the voice actually correct if the detected voice was also counted is thus not protected.

Each participant choice and each other interested party can check the contents of the database ( security audit) and examine whether the results were calculated correctly. However, it may not be the entire information of the database are checked, otherwise the connection between the serial number and the registered participant choice could be made. The secrecy of the ballot would then no longer ensured.

This problem is addressed with a random mechanism, which selects half of all database contents and randomly checked by the secrecy of the ballot would still be ensured and manipulations would if they are included in the random selection notice.

Specifically, the following occurs: A random selection of the inspection or will be made ( The random choice can be derived, for example, of a secret key, or better yet a non- deterministic random number generator, such as a dice or the stock index). This form of auditing preclude the candidates choice of individual ballots is manipulated.

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

• All ballots cast were included in the count.
• It was on every ballot actually elected members evaluated.
• When all the papers were counted and the actually selected candidate was counted, then was counted correctly.

In this case, an undisturbed integrity carried out with a very high probability of choice is provided.

Additional security

To restore the security of an election with punch scan ballots, various other measures can be taken to prevent possible manipulation attempt by the organizers of the election.

Several databases

Given that information, and in the ballot database all be generated together with pseudo-randomly can several databases exist in parallel, again with different pseudo-random information in these columns of data.

Each database is independent of the other, allowing for example the open inspection of some arbitrarily selected databases. Each database must be fully analyzed but ultimately yield the exact same result votes. Thus there is ultimately the same end result, just vote it lies in each database completely different structures before, so you would have to manipulate any database on a different way to even manipulate a cast votes. The probability of detection of tampering thus increases exponentially with the number of databases used, independent. Even the use of less independent databases thus increases the security of the stored data manipulation.

Commitments

As part of the preparations for an election, an institution must be familiar with these preparations, print the ballot papers and create the database (s). An essential step in the preparation of the ballot is that the institution shall adopt, by a cryptographic commitment to the unique information contained in each ballot and in / the database / s will. This determination takes place by a one-way function is applied to this unique information. Although the image of this function ( the Commitment ) is published on the ballot, the actual information is computationally sealed was included in the one-way function. Because of the irreversibility of the one-way function, it is computationally impossible to determine the input information again.

Examination of the ballot

In advance of an election so many paper-based ballots are made ​​that ultimately double the amount of voice labels is available, as is supposed to be employed. From the prepared ballot papers, the actually required ballots are randomly selected (it could, for example, each of the parties a choice proportion of ballots - to be used for the choice - choose yourself ). During the production process of these ballots have already been created as rows of data in the database. The selected ballot could even be re-examined so before the actual use, whether they are correctly registered in the database and still no election results were registered for it.

Since the election officials do not know in advance which half of the ballots actually becomes operational, it means the successful security audit in the form of checks, if the ballot is registered in the database, that the database has not been tampered with very high probability. As soon as the ballot document has been scanned and shredded, it can be checked on the basis of its determination again against the database in order to avoid a high probability of incorrect setting.

Criticism

The implementation of an electoral process by Punch scan appears much more security to offer than methods that rely on so-called voting machines. However, the devil is in the details or in the duly complied cryptographic operations. These are not readily understood by people who are not trained cryptography experts. However, this means that this technology is not comprehensible to administer the electoral process, at least for large parts of the population, so that is not verifiable and therefore not transparent.

However, transparency about what exactly happened is an important criterion for the acceptance of procedures for the settlement of electoral processes. Punch scan can be viewed as a successful attempt to produce an increased security for paper- based dialing, for example, by the verifiability of the voters that their votes were actually counted. However, the Punch scan fails method is to be easy to understand for all voters. It takes a lot of cryptographic sub-steps to apply the method. However, the obtained security and verifiability are exactly dependent on these de facto non-transparent steps and therefore only partly be seen as an improvement of electoral processes.