Fair elections. Word cryptographers
Many attempts (see, for example, Open electronic voting (proof by contradiction) , About electronic secret voting ) “on the knee” to come up with effective voting schemes that are protected from the main types of fraud, are based on one or another method of rejecting the secrecy of voting, ignoring this the danger of facilitating the purchase of votes or forcing the voter to vote. These dangers, it would seem, inevitably arise from the need to combine the “incompatible” requirements of fair elections - to enable the voter to check how his vote is taken into account and to exclude the possibility of selling his vote - that is, to prove to the buyer exactly how he voted. Accounting for the first requirement leads to the rejection of the secrecy of the vote (at least for the voter himself), and, automatically, gives this voter the opportunity to sell his vote to anyone who wants to buy it. The possibility of selling a vote automatically means the possibility of forcing the voter to vote at the request of the attacker under threat of persecution or discrimination. The actual purchase of votes or coercion may not be - the threat itself and the possibility of such a purchase are enough to create the danger of discrediting the voting results.
Can modern cryptography, which solved equally dizzying problems that seemed intractable at first glance (the discovery of an asymmetric encryption system), offer a solution to ensure that the two requirements of fair elections are met?
')
Back in the mid-2000s, Ronald Rivest, the developer of the well-known RSA asymmetric encryption algorithm, suggested “The Three Ballot Voting System” and “Three voting polls: Three Ballot , VTV and Twin” in his works “The Three Ballot Voting System ” (“Voting systems: Three bulletins, Voice-Antigolos-Golos and Gemini”) are several voting systems that can solve the problem of the implementation of both principles of fair elections.
The principle of the ThreeBallot system (sample bulletin - see Figure 1), is to use the bulletin, divided into 3 parts, each of which has a unique and random number (in order to be impossible to remember, it consists of numeric and non-numeric characters - while, of course, it is necessary to exclude the possibility of photographing the entire newsletter). The bulletin is filled in as a whole, in rows, while to vote “FOR” the candidate indicated in the line, you need to put 2 marks for him in any 2 (and only two) parts of the ballot. To vote “AGAINST”, you need to leave only one mark in one of the parts of the ballot in the line where the candidate is listed. A ballot that does not contain at least one mark for each candidate is considered invalid. After the voting is completed, the voter inserts the ballot into the checking machine (checking the correctness of filling in the ballot - having at least one mark and no more than two marks in the line for each candidate) and chooses which copy of which part of the ballot to return to him as a receipt to check the correctness of his vote. Further, the checking machine divides the ballot into 3 parts, makes a copy with the part chosen by the voter, returns it to the voter. All parts of the ballots are published in a public database (PBB, Public Bulletin Board), along with a list of voters who have voted, and the number of ballots should be multiplied by 3 the number of voters who participated in the vote and correctly filled out the ballots. The winning candidate is calculated by the number of marks given for each candidate, from which the number of correctly filled ballots is subtracted, divided by 3. For example, if 3 voters took part in the elections, correctly filled out the ballots as indicated in Figure 1, then the database will get 9 ballots, the number of votes for candidate Jo will be equal to 6- (9/3) = 3 votes, for a candidate Horror - 3- (9/3) = 0 votes. Failure to comply with this rule will indicate a throw-in, withdrawal or distortion of part of the ballots. A voter can check whether his vote is correctly taken into account by comparing a copy of the part of the ballot in his hands with that in PBB, but cannot sell his vote, since he cannot prove which candidate he voted for (for proof it is necessary to know which parts of the split bulletin were one bulletin).
Fig.1. Bulletin of the system “ThreeBallot” . The voter voted for presidential candidate Jo and for candidate for Senate Wu, and against Horror and Yuk. (Figure taken from the article “Three voting protocols: Three Ballot, VAV and Twin”)
A further development of the “ThreeBallot” system , in order to simplify for the voter, was the “Vote-AntiVote-Vote” system (VAV, “Voice-Antigolos-Voice”) (see Figure 2). In it, the bulletin is also divided into 3 parts, but it is allowed not to mark certain candidates, and the voter’s vote is given to the candidate for whom the voter did not tick the AntiVote bulletin, but ticked the ballot.
Figure 2. The ballot system of “Vote-AntiVote-Vote” , the voter voted for the candidate Xerxes. (Figure taken from the article “Three voting protocols: Three Ballot, VAV and Twin”)
Unfortunately, the systems of ThreeBallot and VAV are vulnerable to the possibility of selling votes, based on the buyer's access to the data on which parts the original ballots were made of. Although the PBB does not contain this data, it can be stolen.
Somewhat simpler is the one invented by D. Chaum, the author of the concept of “digital cash”, and described in 2006 by S. Popovenius (S. Popoveniuc) and B. Hoss (B.Hosp) from George Washington University in an article “ An Introduction to Punchscan ” , the Punchscan voting system (see fig.3).
Fig.3. Punchscan sample bulletin for referendum question (answer Yes or No is required). The voter chose the answer “Yes” (b). For traditional elections, instead of “Yes” and “No” the names of candidates may be indicated, the number of candidates may be more than two. (Figure taken from the article “An Introduction to Punchscan”)
The Punchscan bulletin consists of two sheets marked with the same unique number and superimposed one upon the other. The first (upper) sheet contains the names of candidates and their identifiers (for example, letters of the alphabet) in random order, and in the lower part of the sheet there are holes through which the second sheet of the newsletter is visible. On the second sheet, under the holes, the identifiers of the candidates are printed, also in a random order. The voter, having chosen which candidate he gives his vote to, uses a special felt-tip pen to paint over the opening of the first sheet, in which he sees the candidate's identifier printed on the first sheet, so that the marker's mark will remain on both sheets of the ballot. Next, the ballot is divided into sheets, one of the parts is destroyed in the shredder in front of the voter, the second is scanned and placed in the PBB along with the list of voters who have voted, and the original is given to the voter by hand to control the counting of his vote.
By comparing the number of ballots in the PBB with the voter list and their copy of the bulletin with the PBB, the voters monitor the correctness of their vote count.
Nevertheless, there remains the danger of the sale of votes by voters, since, although the voter himself cannot prove for whom he voted for the part of the ballot he has, the redeemer can do it if he gets access to information on the correspondence of identifiers and candidates in the ballots.
The main drawback in the “Scantegrity” system , which develops the advantages of Punchscan , remains unchanged - there is no protection against the possibility of selling a voter’s vote if the buyer has access to information on the correspondence of the random selection numbers specified for each candidate in the ballot issued to the voter.
After some work on testing and improving the ThreeBallot system, R. Raivist proposed a much simpler voting system, radically simplifying the process for the voter, but retaining the advantages of the ThreeBallot and VAV systems and eliminating the danger of buying votes based on access to information on pre-printed ballots. This system, named by the author Twin (Gemini), is described in the article “Three voting protocols: Three Ballot, VTV and Twin” .
The basic principle of the Twin system is extremely simple, called “floating receipt” (Floating Receiption) and provides that a voter, having voted, receives a copy of the ballot paper to control the correctness of the vote count, but not his own, but anyone who voted before .
The voting process in the Twin system can be built as follows:
1. A filled-in ballot is transmitted by the voter to an employee of the electoral commission who checks it for any special marks that could identify him for the purpose of selling a vote, complying with the approved form and transmitting a scanned copy of the bulletin to the PBB where the bulletin receives a random number that is not communicated to the employee election committee, no voter.
2. A polled voter whose ballot has already been submitted to PBB may (if desired) receive a printed copy of a different ballot filled in by another voter with a PBB number, for subsequent control whether the vote of the voter who filled the ballot was taken into account. The voter will not be able to sell the received copy of the ballot, since it was not he who filled it out.
That's all. It is easy to see that the Twin voting scheme ensures the implementation of both principles of fair elections. A voter cannot sell his vote, because he does not know under what number his ballot is counted, and a copy of a ballot without a number, even if he takes a photo of him, will say little. Many voters and independent observers are able to verify the correctness of the counting of votes, but not of their own, but of others, according to published scanned copies of ballots with numbers. No ballot stuffing is determined by matching the number of registered ballots in the PBB and the number of voters in the voter list. The voter list is published to monitor the presence of "dead" souls and persons who obviously did not vote.
The main disadvantage of the Twin system is that it requires the printing and scanning of paper newsletters. They are needed so that there is documentary evidence of how this or that voter actually cast his votes, as well as for the involvement of poorly technical voters in the process. But the disadvantage turns into dignity, as it allows to significantly speed up the voting process and simplify it. In the Twin system, ballots can be printed by the voter or volunteer assistants and distributed at rallies, meetings, or simply on pickets, along with brief instructions on how to fill in and the address to appear for registering voters and handing over the already filled ballot on election day . In the case of online voter registration, the ballot can even be sent by e-mail. In addition, no one forces to limit the voting process to one day - it can go through the entire period of voter registration and only end with the last voting day.
Can modern cryptography, which solved equally dizzying problems that seemed intractable at first glance (the discovery of an asymmetric encryption system), offer a solution to ensure that the two requirements of fair elections are met?
')
Back in the mid-2000s, Ronald Rivest, the developer of the well-known RSA asymmetric encryption algorithm, suggested “The Three Ballot Voting System” and “Three voting polls: Three Ballot , VTV and Twin” in his works “The Three Ballot Voting System ” (“Voting systems: Three bulletins, Voice-Antigolos-Golos and Gemini”) are several voting systems that can solve the problem of the implementation of both principles of fair elections.
The principle of the ThreeBallot system (sample bulletin - see Figure 1), is to use the bulletin, divided into 3 parts, each of which has a unique and random number (in order to be impossible to remember, it consists of numeric and non-numeric characters - while, of course, it is necessary to exclude the possibility of photographing the entire newsletter). The bulletin is filled in as a whole, in rows, while to vote “FOR” the candidate indicated in the line, you need to put 2 marks for him in any 2 (and only two) parts of the ballot. To vote “AGAINST”, you need to leave only one mark in one of the parts of the ballot in the line where the candidate is listed. A ballot that does not contain at least one mark for each candidate is considered invalid. After the voting is completed, the voter inserts the ballot into the checking machine (checking the correctness of filling in the ballot - having at least one mark and no more than two marks in the line for each candidate) and chooses which copy of which part of the ballot to return to him as a receipt to check the correctness of his vote. Further, the checking machine divides the ballot into 3 parts, makes a copy with the part chosen by the voter, returns it to the voter. All parts of the ballots are published in a public database (PBB, Public Bulletin Board), along with a list of voters who have voted, and the number of ballots should be multiplied by 3 the number of voters who participated in the vote and correctly filled out the ballots. The winning candidate is calculated by the number of marks given for each candidate, from which the number of correctly filled ballots is subtracted, divided by 3. For example, if 3 voters took part in the elections, correctly filled out the ballots as indicated in Figure 1, then the database will get 9 ballots, the number of votes for candidate Jo will be equal to 6- (9/3) = 3 votes, for a candidate Horror - 3- (9/3) = 0 votes. Failure to comply with this rule will indicate a throw-in, withdrawal or distortion of part of the ballots. A voter can check whether his vote is correctly taken into account by comparing a copy of the part of the ballot in his hands with that in PBB, but cannot sell his vote, since he cannot prove which candidate he voted for (for proof it is necessary to know which parts of the split bulletin were one bulletin).
Fig.1. Bulletin of the system “ThreeBallot” . The voter voted for presidential candidate Jo and for candidate for Senate Wu, and against Horror and Yuk. (Figure taken from the article “Three voting protocols: Three Ballot, VAV and Twin”)
A further development of the “ThreeBallot” system , in order to simplify for the voter, was the “Vote-AntiVote-Vote” system (VAV, “Voice-Antigolos-Voice”) (see Figure 2). In it, the bulletin is also divided into 3 parts, but it is allowed not to mark certain candidates, and the voter’s vote is given to the candidate for whom the voter did not tick the AntiVote bulletin, but ticked the ballot.
Figure 2. The ballot system of “Vote-AntiVote-Vote” , the voter voted for the candidate Xerxes. (Figure taken from the article “Three voting protocols: Three Ballot, VAV and Twin”)
Unfortunately, the systems of ThreeBallot and VAV are vulnerable to the possibility of selling votes, based on the buyer's access to the data on which parts the original ballots were made of. Although the PBB does not contain this data, it can be stolen.
Somewhat simpler is the one invented by D. Chaum, the author of the concept of “digital cash”, and described in 2006 by S. Popovenius (S. Popoveniuc) and B. Hoss (B.Hosp) from George Washington University in an article “ An Introduction to Punchscan ” , the Punchscan voting system (see fig.3).
Fig.3. Punchscan sample bulletin for referendum question (answer Yes or No is required). The voter chose the answer “Yes” (b). For traditional elections, instead of “Yes” and “No” the names of candidates may be indicated, the number of candidates may be more than two. (Figure taken from the article “An Introduction to Punchscan”)
The Punchscan bulletin consists of two sheets marked with the same unique number and superimposed one upon the other. The first (upper) sheet contains the names of candidates and their identifiers (for example, letters of the alphabet) in random order, and in the lower part of the sheet there are holes through which the second sheet of the newsletter is visible. On the second sheet, under the holes, the identifiers of the candidates are printed, also in a random order. The voter, having chosen which candidate he gives his vote to, uses a special felt-tip pen to paint over the opening of the first sheet, in which he sees the candidate's identifier printed on the first sheet, so that the marker's mark will remain on both sheets of the ballot. Next, the ballot is divided into sheets, one of the parts is destroyed in the shredder in front of the voter, the second is scanned and placed in the PBB along with the list of voters who have voted, and the original is given to the voter by hand to control the counting of his vote.
By comparing the number of ballots in the PBB with the voter list and their copy of the bulletin with the PBB, the voters monitor the correctness of their vote count.
Nevertheless, there remains the danger of the sale of votes by voters, since, although the voter himself cannot prove for whom he voted for the part of the ballot he has, the redeemer can do it if he gets access to information on the correspondence of identifiers and candidates in the ballots.
The main drawback in the “Scantegrity” system , which develops the advantages of Punchscan , remains unchanged - there is no protection against the possibility of selling a voter’s vote if the buyer has access to information on the correspondence of the random selection numbers specified for each candidate in the ballot issued to the voter.
After some work on testing and improving the ThreeBallot system, R. Raivist proposed a much simpler voting system, radically simplifying the process for the voter, but retaining the advantages of the ThreeBallot and VAV systems and eliminating the danger of buying votes based on access to information on pre-printed ballots. This system, named by the author Twin (Gemini), is described in the article “Three voting protocols: Three Ballot, VTV and Twin” .
The basic principle of the Twin system is extremely simple, called “floating receipt” (Floating Receiption) and provides that a voter, having voted, receives a copy of the ballot paper to control the correctness of the vote count, but not his own, but anyone who voted before .
The voting process in the Twin system can be built as follows:
1. A filled-in ballot is transmitted by the voter to an employee of the electoral commission who checks it for any special marks that could identify him for the purpose of selling a vote, complying with the approved form and transmitting a scanned copy of the bulletin to the PBB where the bulletin receives a random number that is not communicated to the employee election committee, no voter.
2. A polled voter whose ballot has already been submitted to PBB may (if desired) receive a printed copy of a different ballot filled in by another voter with a PBB number, for subsequent control whether the vote of the voter who filled the ballot was taken into account. The voter will not be able to sell the received copy of the ballot, since it was not he who filled it out.
That's all. It is easy to see that the Twin voting scheme ensures the implementation of both principles of fair elections. A voter cannot sell his vote, because he does not know under what number his ballot is counted, and a copy of a ballot without a number, even if he takes a photo of him, will say little. Many voters and independent observers are able to verify the correctness of the counting of votes, but not of their own, but of others, according to published scanned copies of ballots with numbers. No ballot stuffing is determined by matching the number of registered ballots in the PBB and the number of voters in the voter list. The voter list is published to monitor the presence of "dead" souls and persons who obviously did not vote.
The main disadvantage of the Twin system is that it requires the printing and scanning of paper newsletters. They are needed so that there is documentary evidence of how this or that voter actually cast his votes, as well as for the involvement of poorly technical voters in the process. But the disadvantage turns into dignity, as it allows to significantly speed up the voting process and simplify it. In the Twin system, ballots can be printed by the voter or volunteer assistants and distributed at rallies, meetings, or simply on pickets, along with brief instructions on how to fill in and the address to appear for registering voters and handing over the already filled ballot on election day . In the case of online voter registration, the ballot can even be sent by e-mail. In addition, no one forces to limit the voting process to one day - it can go through the entire period of voter registration and only end with the last voting day.
Source: https://habr.com/ru/post/156825/
All Articles