Scantegrity

from Wikipedia, the free encyclopedia

Scantegrity deals with a principle that aims to make certain electronic voting systems more secure in terms of manipulation and voting secrecy . This system was developed by David Chaum and represents an essay on electronic systems that work on the basis of optical scanners.

purpose

Since counting votes is very time-consuming, electronic help is required. Even Hollerith realized this at the time. However, these electronic election workers are often easy to manipulate, or they often do little to protect election secrecy. Frequently used examples of this are the voting machines from Nedap and Diebold .

Most electronic voting systems provide complete hardware solutions. In contrast to these systems, the main focus of Scantegrity is more on the way the ballot papers and votes are managed. Attempts are made to eliminate the weak point in the hardware by making the process itself secure. Security should always be interpreted in relation to voting secrecy and manipulation.

principle

Scantegrity is a principle or system for the administration of votes in an election , which aims to save votes cast anonymously and verifiable. This verification (audit) should also be public and transparent for everyone . It is also evident that this system can expand any system based on optical scanners and therefore only requires little additional costs.

Scantegrity is divided into the following four phases:

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

Initially, only the simple case is considered in which exactly one election is carried out with one ballot paper in which exactly one vote can be cast for m (or 2) candidates. This is followed by a brief explanation of how the system can be expanded so that more than one vote can be cast or several elections can be carried out with one ballot paper.

(1) Pre-voting (preparation)

In the pre-voting phase, all the requirements for the Scantegrity system are prepared. This should be done before the ballot papers are printed, as they then carry information that is only calculated during this phase. The requirements mentioned include unique serial numbers for the ballot papers and the bulletin board, which is explained in detail in this chapter. The bulletin board is intended to disguise the connection between a ballot paper, which is assigned a unique serial number, and the candidate who is later chosen with this ballot paper . It is the core of Scantegrity.

The permutations is central to understanding. A permutation p is a mapping rule that swaps a specified number of letters. This is why it is sometimes called a substitution rule. A letter p (b) is assigned to each letter b . The simplest permutation is the identity that does not swap a letter. Another example is the permutation, which only swaps the first two letters. Example of a permutation - p ' Example 2 of a permutation - q '

These two figures show two permutations. Let them be denoted here by p 'and q'. In this example, p 'would replace an A with a B and vice versa. p '(C) would again result in C itself. This notation is interpreted by always replacing a letter with the letter below it.

If one has two permutations p and q , one can form their connection . If a letter b is replaced by p , one takes the new letter and proceeds analogously with the permutation q . The last letter obtained is the letter created by combining p and q from b . If one proceeds in this way with all possible letters, then the complete interchangeability rule for the connection (execution) of p and q arises . In the above example, a B would result in a C if executed one after the other, since p 'creates an A and q' turns A into a C. The reverse mapping of p describes the same mapping in the other direction. If b is replaced by p in a letter b2 , then b2 is replaced by the reverse mapping of p into the letter b . In the example above, the inverse mapping q 'would turn a B into a C.

As a prerequisite, n ballot papers are assumed, which, starting with 1, are numbered consecutively. These unique numbers are called serial numbers {i} . Assume that there are m candidates in the election. The first m letters of the alphabet on each ballot paper are then distributed to the candidates, the assignment being done arbitrarily for each ballot paper. A permutation p [i] of the permutation group S (m) is uniquely assigned to each ballot paper i . It should be mentioned here that it is sufficient to limit oneself to the cyclical subgroup generated by (2 3 ... m 1) as long as only one vote can be cast in the election. In this way one can speak of "shifts" and replace the permutations with numbers 1 to m.

The bulletin board is essentially a table with three columns and n rows, where n is the number of prepared ballots. The cells in the first two columns each consist of three components. The first component is a placeholder for one of the first m letters of the alphabet. It is only filled as soon as the voter casts his vote. The second component specifies a rule (permutation) for the first m letters. The permutations of the 1st column and i- th row will henceforth be denoted by q [i] and the permutations of the 2nd column and i- th row by r [i] . The third component is a number between 1 and n . Let the numbers in the 2nd column and i th row be denoted by f (i) and those in the 3rd column and i th row by g (i) . The last column consists of placeholders for letters. They resemble the structure of the first components of the cells in the first two columns. The following figure illustrates this again.

Illustration of the components of the bulletin board

The numbers f (i) and g (i) must not be determined completely arbitrarily, instead they have to meet exactly one condition. No number may appear twice in the second column. Likewise, no number may appear twice in the third column. The numbers f (i) are exactly the numbers from 1 to n . The n numbers g (i) also include exactly the numbers 1 to n .

Before the restriction on permutations can be mentioned, the meaning of these numbers must be explained. Due to the uniqueness of the numbers f (i) and g (i) , unambiguous chains are determined from the cells in the first column to the cells in the third column. A chain that starts in the i th row of the first column has its second element in the second column in the row with the number f (i) . For the sake of simplicity, let this number f (i) be briefly fixed and denoted by j . Now you can find 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 papers and in the first column may be chosen at will , i.e. randomly . In contrast, for every i between 1 and n, the permutation r [i] must correspond to the inverse mapping of the sequential execution of the permutations p [i] and q [i] . Simply put, this limitation is as follows. If one chooses one of the first m letters and replaces it according to the permutation p [i] of the ballot paper, a new letter is obtained. If you continue with the newly won letter according to the permutation q [i] of the first column and do the same with the latter letter and the permutation r [i] from the second column, the originally selected letter must be created again.

At this point it should be mentioned that the content of the second and third components of the cells in the first two columns should not be public. This is to ensure that the chains are not visible, which means that the connection between ballot papers and elected candidates remains secret.

(2) voting

The choice using Scantegrity can be viewed from three perspectives. First of all, the view of the voter should be considered. Then points are mentioned which concern the election organizer himself. Finally, this phase is considered from the perspective of the Scantegrity system.

From the voter's point of view, there are up to three phases to go through. The latter two phases are optional and serve to verify the vote cast.

  • In the first phase (A) the voter fills out the ballot paper. More precisely, this means that the voter places a cross in a given area next to any candidate. A letter belongs to this area that he can write down. He can also write down the serial number of the ballot paper. Only when he does this can he go through the following optional phases.
  • In the second phase (B) the voter checks online whether his vote was cast correctly. To do this, he enters the serial number of his ballot paper on a given website and receives the letter of the candidate who was ticked accordingly. If this letter does not match the one he wrote down during the election, there is a discrepancy and only then should the third phase be initiated. At this point it should be noted again that the serial number and the letter cannot be used to deduce which candidate has been elected, since the affiliation of the letters to the candidates was chosen randomly for each ballot paper.
  • In the third phase (C), the voter turns to the election organizer to clarify this disagreement. In this case, there may be election fraud, ie his vote was manipulated.

From the point of view of the election organizer, it must be clarified which technical requirements must be met and how the votes cast are managed. The ballot papers can, as usual, be scanned in the district or at a central location. A central scanner would increase the time required, but reduce the technical effort. There are two different types of optical scanning systems. These are, on the one hand, the pixel scanners and, on the other hand, the sense mark scanners.

The pixel scanners are the usual scanners that are also often found in private use. You scan the entire image in a two-dimensional grid with a certain resolution. The used ballot papers are scanned and the image can be transferred directly to the ready-made software. If a voting system is expanded with the Scantegrity method, such software will already exist and the images will be sent to it as well as to the software specially developed for Scantegrity. On the other hand, the software for Scantegrity already contains a complete voting system, so that the old one can be omitted in this case. Numbers and markings on the ballot paper, such as B. the serial number of the ballot paper can be calculated with ready-made algorithms.

Sensemark scanners scan certain predetermined areas for a mark. The result for a certain area can only be “marked” or “not marked”. Serial numbers etc. can, however, be coded in binary, so that they can be detected by SensemarkScanners during scanning. This can be done analogously to the representation of numbers in the computer. Another possibility would be to specify exactly ten marks per digit, of which exactly one is filled out. Each marking represents a digit between 0 and 9. If you want to represent a five-digit number with this method, you need 50 marks.

In some retrofits, the software is not adapted, but a second scan is carried out with a pixel scanner. The votes can accordingly be counted a second (redundant) time and the results (counting results) can be compared.

The view of the bulletin board should show what exactly happens when a ballot paper is submitted. Assuming there is a valid ballot paper with a cast vote, the serial number and the marked letter are taken from it after scanning. The scanned letter is now written in the placeholder in the first column in the line with the number of the serial number i . Then the placeholders of the chain starting from this cell are filled. For this purpose, the scanned letter is replaced according to the permutation q [i] of the first column of this chain and written in the placeholder of the second column of this chain. The associated line number is f (i) . Likewise, the letter just received is replaced by the permutation r [f (i)] of the second column of the chain and written in the third column of the chain. The associated line number of this cell is identified by g (f (i)) . The letter in the third column in the line corresponding to the chain uniquely corresponds to a candidate for election.

(3) Pre-audit

In the pre-audit phase, the bulletin board is checked for correctness through random checks. In this sense, correctness means that the restrictions described in chapter "(1) pre-voting" are fulfilled.

A public sample for a particular ballot will invalidate it. The associated chain in the bulletin board is revealed. The voter can now check whether the combination of the permutations p [i] , q [i] and r [f (i)] result in the identical mapping. In simple terms, this means that he can check whether the letter at the end of the chain results from the substitutions that he entered at the beginning.

At this point, however, the problem can be recognized that the chain can be decrypted or disclosed if desired. It must be ensured here that this does not happen by unauthorized persons.

If x% of the ballot papers are revealed in the pre-audit phase, the probability of uncovering election fraud is also at least x% . The number x depends heavily on which scenario is implemented in order to give the voters the opportunity to carry out spot checks. Here are z. B. the following scenarios are conceivable:

One possibility is to give each voter exactly two ballot papers. The voter can then decide which of the two ballot papers to reveal for verification and which to use for voting. The probability of discovering electoral fraud is then at least 50%. Another option is to randomly decide for each ballot paper whether or not to reveal it. The random algorithm can then be designed in such a way that the number x can be chosen itself, apart from a certain inaccuracy. All undisclosed ballot papers are then distributed to voters. Of course, it must be ensured here that enough ballot papers are not revealed so that every voter can cast his or her vote. It is also conceivable that voters have the right to reveal and thus examine any ballot papers that have not yet been distributed. Here, however, the greatest problem is to correctly estimate the number of ballot papers so that in the end every voter could cast one vote.

(4) audit

The last phase also serves to verify the bulletin board. However, this verification takes place in public to a much greater extent than was the case in the previous phase.

For each ballot paper, the associated chain in the bulletin board consists of exactly three elements. The first two elements of each chain carry the information that must not be disclosed. This restriction is partly lifted here. In this phase, either the secret part of the first or the second element of each chain is revealed. The choice of which part is revealed is purely random. Since both parts are never revealed here at the same time, the voting secrecy is still preserved. The letter of the placeholder of the revealed element is replaced by means of the associated permutation and compared with the letter of the placeholder of the following element of the chain. If these two letters deviate from each other, this is a manipulation.

The chance of fraud is now vanishingly small. Any manipulation of a voice is detected with a probability of 50%. The probability of not being discovered for a fraudster is halved with every additionally manipulated vote. Since it takes a large number of votes to influence an election, the chance of detecting the fraud is almost 100%. The exact formula for the probability that the fraudster will not be discovered is attached for k manipulated votes . With 10 votes, this value is already less than 0.001.

Extensions to common electoral principles

So far it has been assumed for an election that exactly one cross may be placed under m candidates. However, it should be possible to cast multiple votes in one election. Furthermore, it often happens that two different elections are carried out with one ballot paper. This chapter shows how this can be solved.

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

If z elections are voted on with a ballot paper , it is sufficient to prepare z bulletin boards that are independent of one another. Although the elections are then all made with a ballot paper, they are handled like different elections.

Evaluation of target achievement

Obviously, the process appears to have achieved its two main objectives. On closer inspection, however, you can see that there are still gaps in securing voting secrecy and decisive disadvantages.

If the election organizer is already using a system based on optical scanners, the effort for setting up Scantegrity is very low. If you opted for the system, this speaks in favor of a quick changeover.

The voter has the option of subsequently verifying his cast vote, which also speaks for the system. Furthermore, the voter can invalidate a ballot paper and use it to carry out a random check to determine whether the bulletin board has been manipulated. The voter cannot do this in the usual procedures. Since the process is not easy for everyone to understand, it can still be difficult to build confidence in the process. The bulletin board can not only be checked for manipulation through random checks, but also through the final audit. It turns out that an effective undetected manipulation is almost impossible.

As this electoral system is complex, it will be difficult to gain the trust of the entire population in this system. Even with several candidates in an election, permutations must be expected, which means that the probability is high that the voter either does not gain understanding or loses the desire to carry out a random sample, as this does not require a small amount of effort. Furthermore, the system is very well protected against undetected manipulation, but at the price of the security of the election secrecy. The decisive phase, namely, to discover a manipulation in the bulletin board with a high degree of certainty, is the audit. This is based on being able to reveal the secret parts of the bulletin board on request. Since the voter has to be able to access the bulletin board from the outside via an online system to verify his vote, there is also the opportunity to attack the system from outside. Once the intrusion into the system has been granted, the attacker has access to all votes cast. If the attacker also knows the serial number of the target person's ballot paper, he now knows which candidate he has chosen, and voting secrecy is violated. The person who belongs to a ballot paper is relatively easy to determine as soon as one is in possession of the ballot paper, since in the future everyone's fingerprints will be recorded.

Overall, the result is that the system is very well armed against manipulation. Violating voting secrecy has become much more costly. On the other hand, there are complexity and the effort for the voters.

swell