Scantegrity

Scantegrity treated a principle, which is to make certain electronic voting systems with respect to manipulation and secrecy of the ballot safer. This system was developed by David Chaum and provides an essay on electronic component systems which operate on the basis of optical scanners.

Purpose

Since the counting of votes is very extensive, you need electronic help. Already Hollerith realized this at the time. However, these electronic election officials are often easily manipulated, and they are often poorly protected secrecy of the ballot. Frequently used examples are the voting machines from Nedap and Diebold.

Most electronic voting systems provide complete solutions with hardware. In contrast to these systems, the focus of Scantegrity lies rather in the manner of administration of the ballots and the votes. The vulnerability of the hardware is therefore tries to eliminate by the method itself is to be made ​​safe. In this case, safety should always be interpreted in relation to the election secrecy and manipulation.

Principle

Scantegrity is a principle or system for the management of votes in an election that sets itself the goal of votes cast to store anonymous and verifiable. This verification (audit) should also be transparent and publicly for everyone. It also follows that this system is arbitrary, based on optical scanner that can expand systems and therefore requires only small additional cost.

Scantegrity is divided into the following four phases:

• (1 ) pre -voting
• ( 2) voting
• (3 ) pre -audit
• ( 4) audit

Only the simple case is first considered that with a ballot accurately an election takes place, can be delivered in exactly one vote for m (or 2) candidates. Following is a brief guide on how to expand the system so that more than one vote may be cast, or more elections can be carried out with a ballot paper.

( 1) Pre- voting ( preparation)

In the pre -voting phase, all necessities for Scantegrity system are prepared. This should be done even before the ballots are printed, as they contribute information that will only be calculated during this phase. Among the mentioned needs, among other things include unique serial numbers for the ballot and the bulletin board, which is explained in this chapter in detail. The bulletin board is to obscure the connection between a ballot paper to which a unique serial number is assigned, and the later elected with this ballot candidates. It represents the core of Scantegrity

The permutations for an understanding of central importance. A permutation P is a mapping rule, which exchanged a predetermined number of characters. Man you therefore also sometimes called interchange specification. It is therefore assigned to each letter b is a point p (b). The simplest is the identity permutation that swaps no letters. Another example is the permutation that swaps only the first two characters.

These two figures show two permutations. You are here denoted by p 'and q'. p ' would, in this example an A replaced with a B and vice versa. p '( C) would again result in C itself. They interpreted this spelling by one letter is always replaced by the under him letters.

If you have two permutations p and q, then one can form the link. If p by a letter b replaced, so you take the new letter and the procedure is analogous to the permutation q. The letter recently received the letter, which results from the combination of p and q from b. By doing so with all sorts of letters, the result is the complete interchange specification of link ( sequential execution ) of p and q. A B would result in a C in the above example, in the sequential execution as ' creates an A and Q' by P from C. A makes a. The inverse mapping of p describes the same image in the other direction. If b is replaced by p in a letter b2, then b2 by the inverse mapping of p replaced in the letter b. In the example above, the inverse map q ' turn a B, a C.

As a prerequisite n ballots were accepted, are numbered consecutively starting with 1. This unambiguous numbers are called serial numbers { i}. It is assumed that there are m candidate in the selection. Then the first m letters of the alphabet are distributed to the candidates on each ballot, the assignment is done randomly for each ballot. Each ballot i is thus unambiguously assigned a permutation p [ i] of the permutation group S (m). It should be mentioned that it is sufficient to restrict oneself to the cyclic subgroup generated by ( 1 2 3 ... m ), while in the choice of only one vote may be cast. In this way, one can speak of shifts and replacing the permutations by numbers from 1 to m.

The bulletin board is essentially a table with three columns and n rows, where n is the number of prepared ballots represents. The cells of the first two columns consist of three components, respectively. The first component is a placeholder for one of the first m letters of the alphabet. You will only be filled once the voter to vote. The second component specifies an interchange specification ( permutation ) of the first m letters. The permutations of the first column and i- th row are henceforth denoted by q [ i] and the Permutaionen the 2nd column and i- th row and r [ i]. The third component is a number between 1 and n are the numbers of the second column and the ith row here with f (i) and designated the third column and the ith row of g ( i). The last column consists of placeholders for letters. They are similar to the structure of the first components of the cells of the first two columns. The following figure illustrates this again.

The numbers f (i ) and g ( i) may not be assigned completely arbitrarily, instead they are to exactly satisfy a condition. In the second column, no number can appear twice. Similarly, no number can appear twice in the third column. The numbers f (i) are exactly the numbers from 1 to n also include the N numbers g (i) the exact number of 1 to N.

Before restricting the permutations can be called, the significance of these figures must be explained. The uniqueness of the number F ( i) and g (i) -one chains are determined by the cells of the first column to the cells of the third column. A chain that starts in the i- th row of the first column, has her second element in the second column in the row with the number f ( i). For simplicity, this number is f (i) and j indicates a short fixed. Now one finds the third element of the chain in the third column in the row with the number g ( j ) = g (f ( i)).

The permutations of the letters for the candidates on the ballot and in the first column may be arbitrary, ie randomly selected. In contrast, must, for each i between 1 and n is the permutation r [ i] is the inverse mapping of the sequential execution of permutations p [ i] and q [ i] correspond. Simply put, this restriction amounts to the following. If you take one of the first m letters, exchanges of these according to the permutation p [i ] of the ballot, we obtain a new letter. If you drive with the newly won letters according to the permutation q [ i] is the first column continues and makes selbiges with the latter letters and the permutation r [i ] from the second column, the originally selected letter must arise again.

At this point it should be mentioned that the contents of the second and third components of the cells of the first two columns are not intended to be public. This is intended to ensure that the chains are not seen to produce the compound of ballot remains secret to the selected candidates.

(2) voting

The choice of using Scantegrity can be viewed from three different viewpoints. First, the point of view of the voter should be considered. Then points are mentioned, relating to the election authority itself. Finally, this phase is considered from the perspective of Scantegrity system.

From the perspective of the voter up to three phases to be completed. The latter two phases are optional and serve to verify the vote cast.

• In the first phase (A) the voter fills the ballot. Specifically, this means that the voter is a cross within a predetermined range next to any candidate. This area includes a letter that he can write. He also can write down the serial number of the ballot. Only if he does this, he can commit the following optional phases.
• In the second phase (B ) of the voters checked online whether his vote was cast correctly. He enters on a given website, type the serial number of his ballot and receives the letter of the candidate who was ticked accordingly. Is this letter is not with the match, he has recorded during the election, so there is a discrepancy and then the third phase should be initiated. It should again be noted that one can not derive from the serial number and the letter which candidate was chosen as the membership of the letters was elected to the candidate for each ballot paper at random.
• In the third phase (C ), the voter applies the election authority for this discrepancy to be resolved. Possibly in this case before an election fraud, that his voice has been manipulated.

From the perspective of the election organizer is to clarify the technical requirements must be met and how the votes are managed. The ballots may be, as usual, scanned in the district, or at a central location. A central scanner would increase the cost, but they reduce the complexity. There are two different types of optical scanning systems. These are on the one hand, the pixel scanner and on the other hand, the Sense Mark scanner.

The pixel scanner are the usual scanners, which are also commonly found in private use. Scan with a certain resolution, the entire image into a two-dimensional grid. The unused ballots are scanned and the image can be transferred to the pre-written software directly. If a voting system is extended with the Scantegrity process, such software is already there and the pictures go to both these, as well as to the specially developed software for Scantegrity. On the other hand, the software for Scantegrity already contains a complete selection system, so that the old can be omitted in this case. Numbers and markings on the ballot, such as the serial number of the ballot can be eliminated with pre- algorithms.

Mark Sense Scanner scan certain predetermined areas off to a label. The result for a specific region can only be "marked" or " unmarked ". However, serial numbers, etc. can be encoded in binary, so they can be detected by Sense Mark scanner while scanning. This can be done analogously to the representation of numbers in the computer. Another option would be, per digit to specify exactly ten marks, one of which is exactly filled. Each mark this represents a digit between 0 and 9 If you want to represent with this method, a 5 -digit number, so this will require just 50 marks.

In some retrofit not the software is adapted to a second scan, but carried out with a pixel scanner. The voices can, accordingly, a second (redundant ) times are counted and the results ( counts ) can be compared.

The view of the bulletin -boards, will show what exactly happens when a ballot is issued. Suppose you have a valid ballots with a cast vote, then it is after scanning the serial number and the marked point taken. The scanned letter is now written into the placeholder in the first column in the row with the number of the serial number i. Subsequently, the placeholder of the outgoing from this cell chain are filled. For this, the scanned letter is replaced the first column of this chain according to the permutation q [ i] and written in the placeholder of the second column of this chain. The associated line number is f ( i). Similarly, the letter just received will be replaced the second column of the chain through the permutation r [f ( i)] and written in the third column of the chain. The corresponding number of this cell line is characterized by g ( f ( i)). The in the third column standing in the row corresponding to the chain letter corresponds uniquely to a candidates standing for election.

( 3) Pre -audit

In the pre -audit phase, the bulletin board is checked by sampling for accuracy. Correctness means in this sense that the restrictions described in the chapter " (1 ) pre- voting", are met.

A public sample for a particular ballot makes this invalid. The corresponding chain in the bulletin -board is revealed here. The voter can now check whether the link of permutations p [ i], q [i ] and r [f ( i)] yield the identity map. Expressed in simple terms, this means that it can check whether the end of the chain, the letter is created by the replacements, he has to enter at the beginning.

However, already at this point is to recognize the problem that the chain decrypted on request, or can be revealed. It must be ensured here that this does not happen by unauthorized persons.

If x % of the ballots will be revealed in the pre -audit phase, the probability is a fraud also reveal at least at x%. The number x depends strongly upon which scenario is implemented in order to give the voters the opportunity to carry out the audit. In this case, for example, the following scenarios are possible. One way is to give each voter exactly two ballots. The voters can then decide which of the two ballots he reveals for the verification and which he used for election. The chance to uncover the fraudulent elections is then at least 50%. Another possibility is random for each ballot to decide whether he is revealed. The random algorithm can be designed so that the number can be selected x up to a certain inaccuracy itself. All undisclosed ballots are then distributed to the voters. Of course there has to be ensured that sufficient ballots not be revealed, so that each voter can make his voice heard. It is also conceivable that voters have the right to disclose any, not yet distributed ballots and to examine it. Here, however, the problem is greatest, estimate the number of ballots correctly, so that at the end of each voter could cast a ballot.

( 4) Audit

The last phase is also used for verification of the bulletin boards. However, this verification is essentially greater extent from the public, as it was the case in the previous phase.

For each ballot the corresponding chain in the bulletin -board consists of exactly three elements. The first two elements of each chain wear is the information that must not be revealed. This restriction will be lifted here to the part again. In this phase of each chain either the secret part of the first or disclose the second element. The choice of which part is revealed is purely coincidental. Since there never both parts are revealed simultaneously, the secrecy of the ballot remains preserved. From the revealed element, the letter of the placeholder is replaced by the corresponding permutation and compared with the letter of the placeholder of the next element of the chain. If these two letters are different, so there is a manipulation here.

The chance of fraud is now negligible. Any manipulation of a voice is detected with a probability of 50%. So as not to be discovered, the probability of a scam is halved with each additional manipulated voice. Since a large number of votes is necessary to influence an election, the opportunity lies uncover the fraud that is almost 100 %. The exact formula for the probability that the scammer is not discovered, is for k manipulated votes in favor. Even with 10 votes, this value is already smaller than 0.001.

Extensions to usual choice principles

It was believed for a choice among m candidates that exactly one cross may be set. However, it should be possible to give more than one vote in an election. Furthermore, it often happens that with a ballot paper, two different elections are carried out. In this chapter it is shown how this can be solved.

Multiple votes on a ballot paper will be accommodated in the bulletin board by the placeholders from a y -tuple, where y represents the number of elections. This means that y is different letters are written. The first letter represents represents the first vote

If z elections matched with a ballot paper, it is sufficient z bulletin boards to prepare, each independently. Although then the elections are all made ​​with a ballot paper, but they are handled as different choices.

Evaluation of the target fulfillment

The obvious method seems to have fulfilled its two main objectives. On closer inspection, however, one realizes that there are still gaps in the area of ​​securing the secrecy of voting and crucial disadvantages.

If the election authority is already using a system based on optical scanner system, so the cost of the article by Scantegrity is very low. This argues in a decision for the system for a quick conversion.

The voter has the opportunity to subsequently verify its voter, which also speaks for the system. Furthermore, the voter can make a ballot invalid and perform with this one sample, whether the bulletin board has been manipulated. In the usual procedure, this is not possible for the voters. Since the process is not easy to understand for everyone, it can still be difficult to build trust in the process. The bulletin board can be tested not only by sampling on manipulating it back, but also by the final audit. It follows that a large impact undetected manipulation is almost impossible.

Because of this electoral system brings a certain complexity, it will be difficult to win the trust of the entire population in this system. Already with several candidates of an election to be reckoned with permutations, thereby reducing the likelihood is high that the voters either understanding not obtained or lose the desire to carry out a sample because this no small degree of effort is sufficient. Furthermore, the system is very well protected from undetected tampering, but this is based on the price of the security of the ballot secrecy. The decisive phase namely, to discover tampering with high certainty in the bulletin board is the audit. This is based on being able to reveal the secret parts of the bulletin boards on request. Since the voters can access an online system from the outside on the bulletin board for the verification of his voice has that chance is also given to attack the system from the outside. Is hacking into the system grants only once, so the attacker all votes cast are available. The attacker knows also the serial number of the ballot of its target person, he now knows what he has chosen candidates and ballot secrecy is violated. The person who belongs to a ballot is relatively easy to determine, as soon as one is in possession of the ballot, because in the future the fingerprints of all people are recognized.

Overall, the system is very well armed against manipulation. To violate the secrecy of the ballot has become far more complex. Contrast, however, is the complexity and the expense of the voters.

Swell

• Http://www.chaum.com ( 12 December 2007)