Bingo voting

Bingo voting is an electronic voting process that was developed at the European Institute for System Security (EISS) of the Karlsruhe Institute of Technology and is intended to remedy the lack of traceability of many electronic voting processes using cryptographic methods. The correctness of the choice is guaranteed under the assumption that trustworthy random number generators are used. The name "Bingo Voting" comes from the idea of using a mechanical device as a random number generator, similar to bingo or the lottery .

In the process, voting computers are used to cast and count the votes, but the voter receives a paper receipt when voting, with the help of which he can understand the correct counting of his vote. The receipt is not simply a copy of the completed ballot paper. Rather, the distribution of votes is only visible to the voter himself from the receipt. The receipt is neither intended nor suitable for recounting the election results and is given to the voter to take home.

concept

The declared aim of the bingo voting process is to remedy the disadvantages of conventional voting machines, in particular the lack of verifiability, and to make electronic procedures for voting verifiable and thus usable.

The basic idea of the procedure is to give the voter a document from which he can see his vote and to publish copies of all documents after the election. This ensures:

Any voter can verify that their voucher has been published and that their vote has been counted.
Anyone can verify the result of the count against the published evidence.

A trivial procedure would be to simply give the voter a copy of their (with an identification number) ballot slip in the hand. After the election, all ballot papers will be published and everyone can check that their ballot paper is among them, as well as the counting and thus the election result. With this naive procedure, however, blackmail and buying votes would be possible through the receipt , so voting secrecy would not be adequately protected.

However, cryptographic procedures enable evidence from which only the voter himself can see his vote and no one else. As a result, the voter cannot use his receipt to prove to any other person what he has voted.

In addition to the actual vote of the voter, the receipt contains so-called filler votes (or dummy votes). These votes were determined before the election and distributed evenly to the candidates. The real voice is generated in the voting booth in front of the voter's eyes so that he knows it, but cannot be distinguished from a filling voice by anyone else.

Election process

Election preparation

In preparation for the election, random numbers are generated for each candidate. These random numbers serve as filler votes. Commitments are published on the random numbers, along with zero-knowledge evidence that each candidate received the same number of filler votes. A commitment procedure offers the possibility of publishing a value in such a way that one is committed to it without revealing it, that is, one does not publish the value itself but an "encrypted version" of it. The developers propose Pedersen commitments for this, as they have advantageous properties for the necessary evidence.

For practical reasons, each voting machine receives its own pool of filler votes. In the following, the method is described for illustration with only one voting machine and a pool of filling votes.

choice

The voting machine required for the method consists of a voting computer with a screen, an input device (for example a touchscreen ), a printer and a trustworthy random number generator.

A voter casts his vote on a voting machine. There are no restrictions due to the procedure itself, the presentation and voting as well as any help can be adapted to the election.

After the voter has cast his or her vote, the random number generator generates a random number for each vote that has been cast and shows this on its own display. The voter now receives a printed receipt and can check directly in the voting booth whether the receipt is correct. To do this, he compares the random numbers that represent his votes, i.e. are in the appropriate places, with the random numbers that are displayed by the random number generator. If they match, he can be sure that the voting machine has saved his vote correctly.

The random numbers on the receipt, which represent votes that were not cast, come from the lists previously established. The voting computer removes these random numbers from its list as soon as they have been used for a receipt so that they are not used a second time.

Counting

The counting is based on the unused filler votes. The candidate who has retained the most filler votes on his list wins the election. Because if a voter casts his vote for a candidate, all other candidates lose a filler vote from their list. The exact distribution of votes can be calculated from the number of unused filler votes and the number of voters.

After the election, further information will be published in addition to the election results:

All unused random numbers (filler votes) from the lists of candidates are published.
All documents are published.
A zero-knowledge proof is published for each receipt, which proves that there is exactly one fresh random number on the receipt and that the remaining random numbers come from the lists of candidates.

With the help of this published data can

every voter check whether his receipt has been published and thus his vote has been taken into account in the count,
everybody understand that for every document (and thus for every voter) from every list with filler votes except one (that of the candidate for whom the vote was cast), a random number was deleted, and
everyone understand that the number of receipts corresponds to the number of voters and the election result.

The last two points can be checked by anyone regardless of whether they participate in the election or the count.

example

In the voting booth: The voter has chosen candidate B using a voting computer (left) and receives a receipt (right) in which the random number belonging to candidate B corresponds to the display of the random number generator (center).

An election with three candidates could run roughly as follows: The election commission, together with the three candidates, publishes three encrypted lists of random numbers (actually commitments on the random numbers). This also proves that all three lists are of the same length, i.e. contain the same number of random numbers.

In the voting booth, the voter selects one of the three candidates, for example with a touchscreen. Once confirmed, a random number generator, a small device with a display that is connected to the computer, starts up. The voting computer now generates a receipt by taking a random number from the two lists of candidates who have not been elected, as well as the random number from the random number generator. The two random numbers from the lists are written to the respective candidates, the candidate who was chosen receives the random number that was just generated by the random number generator.

The voter now receives a receipt with a number behind each candidate. He can check that the voucher reflects his vote correctly. To do this, the number next to the candidate he has chosen must match the number displayed by the random number generator. If this is the case, he can leave the voting booth and take the receipt home with him. Nobody who was not there when the random number was generated and displayed by the random number generator can see on the receipt who the voter voted for.

After the election, voters can see whether their receipt has been published. With this he can be sure that his vote has been counted. For each receipt there is also a proof that two of the three random numbers come from the lists specified in advance. This means that the voter can be sure that a random number has been deleted from the candidates he has not chosen, because these appear on his receipt. The random number of the candidate chosen by the voter cannot come from the list because it was generated in the voting booth in front of his eyes.

Security and traceability

The security of the procedure is based on the basic idea that every voter can check the correct counting of his own vote. To do this, the voter in the voting booth must compare the receipt with the display of the random number generator and after the election check that his receipt has been published. The evidence, which is also necessary for security, can be reproduced independently, even by people or groups who were not involved in the election itself.

The verifiable correctness of the procedure is based on the random number generator. If this is corrupted, the correctness of the procedure cannot be guaranteed. The authors argue that it is easier to comprehensibly build and certify a random number generator than a complete voting machine.

The security of voting secrecy is based on the voting machine and the trust in the election management, which generates the random numbers before the election. If the voting machine saves which vote was cast when or if the list of random numbers is completely known, voting secrecy is no longer guaranteed.

Contesting the election

There are several problems that can arise during or after a rigged election:

A voter determines that the receipt does not contain the fresh random number from the random number generator or has it in the wrong place.
A voter notes that his receipt has not been published.
One of the zero knowledge pieces of evidence is flawed.

The bingo voting process makes no statement about the evidence on which an election can be contested. It only serves to uncover election manipulation.

Bingo voting in practice

Use in complex elections

One of the advantages of voting processes that use voting computers is the support that the computer can provide in complex, high-number, cumulative and multi-vote elections. Above a certain size, bingo voting comes up against a limit, as the size of the receipt and the number of random numbers increase with the number of votes. In the case of an election with three candidates and one vote, the voter has to look for a number on a receipt with three random numbers and compare it with the display of the random number generator. In an election with 50 candidates and nine votes, the receipt already bears 450 random numbers, nine of which the voter has to compare with the random number generator. This task can be made easier with the help of the computer and appropriate formatting of the receipt, but it is time-consuming in any case.

Real elections carried out using bingo voting

Bingo voting was used for the first time in the student parliament election of the University of Karlsruhe in 2008 in a real election. About 2.5% of the votes cast there were cast by bingo voting, the remaining votes were conventional paper slips. After the election, however, the election committee reported problems with the prototype system, including the possibility that EISS employees could have broken the secrecy of the election.

Awards

On October 24th, 2008 the project “Bingo Voting - Verifiable Elections with Voting Machines” was awarded the German IT Security Prize.

Similar procedures

There are other cryptographic voting methods with a purpose similar to bingo voting. One of them is Punchscan , which was developed by David Chaum .

swell

Web links

[1] Jens-Matthias Bohli, Jörn Müller-Quade, Stefan Röhrich: Bingo Voting: Secure and coercion-free voting using a trusted random number generator

[2] Press release in the archive of the Karlsruhe Institute of Technology (KIT)

[3] Homepage of the election committee of the independent model (University of Karlsruhe)

[4] Overview of the urns and votes cast in the StuPa election 2008 in Karlsruhe

[5] Minutes of the 6th session of the student parliament of the University of Karlsruhe, annex comments from the election committee WS07 / 08 (PDF; 61 kB)

[6] heise Security on the award of the German IT Security Award 2008