Cryptographic protocols for electronic voting

Democracy is not a vote, it is a vote count.
Tom Stoppard

For cryptographic researchers, electronic voting is not primarily related to a voting machine and not to online voting — it’s just a field for mathematical research . The study of electronic voting involves the creation of protocols, key mathematical components, protected and verifiable voting systems , or systems in which independent auditors and voters can safely verify the correctness of the vote count. These systems are not simple theoretical works, but real technologies that were used for real elections: in the city of Tacoma-Maryland State Park, voters trusted Scantegrity II , based on paper ballots with invisible ink, and the cryptographers themselves used Helios online voting systems. for election leadership.

Electronic voting is an extremely difficult topic, so in this article I will confine myself to key concepts: what does safe voice checking mean, how can votes be counted without addressing everyone individually, and what does not allow voters to cheat. I will not give you a complete description of the entire e-voting protocol with all its nuances, but those who wish can independently search for works on this topic, of which there are quite a lot .

Secure Confirmation

What should I expect from a safe voting system?

The first and the most obvious: you need to check that the ballots are counted correctly, that is, so that everyone can confirm that the final count was made in accordance with the number of ballots filled with voters. The check should not produce any additional information, except for the totals. In particular, the verifier should not be able to guess who voted how. This is equivalent to manually counting paper bulletins.

Secondly, it is necessary that any voter can make sure that his vote was counted and counted correctly. This needs to be able to be done without disclosing his vote, and in a more general case, the voter should not be able to prove who he voted for. This is done to exclude coercion, and to allow voters to freely choose a candidate, without fear of the consequences of their choice.

Finally, the voting system must be protected against fraud: the voter should not be able to vote more than once, and should not be able to change or copy the ballot. In addition, only registered voters should be able to vote.

So let's summarize: we need public verifiability, voter confidence, resistance to coercion, and integrity of the election. These principles were put forward in a fundamental study of the authorship of Chaum, Neff and others, published in the early 2000s.

Basic principles

Most classic e-voting protocols work as follows:

1. The voter receives a token in the form of a bulletin, which changes according to his choice. Different voters receive different ballots.
2. The voter encrypts the ballot (using a special type of encryption that allows e-voting magic to work and sends it so that the organizers of the voting receive an encrypted ballot.
3. The organizers publish encrypted bulletins on a bulletin board, a “public broadcast channel with memory,” in the jargon of cryptographers - to put it simply, on something like Pastebin.
4. The organizers combine encrypted bulletins to calculate the encrypted total. Then they decipher it (but not the bulletins themselves!) And publish the results.
5. Having received the result and the encrypted voices, anyone can verify its correctness.

Secure Counting: Homomorphic Encryption

At step 4, the organizers combine the cryptograms to create a new cryptogram, encrypting the sum of the individual votes. For this electronic voting scheme, Enc () encryption scheme is used, in which Enc (v1 + v2) can be calculated, having only Enc (v1) and Enc (v2) in hand, and not knowing the encryption key. Such encryption schemes are called homomorphic .

For example, if you simplify a lot, US voters do the following on November 8:

1. The Clinton newsletter and the Trump newsletter are received from the organizers (for simplicity, we consider only two candidates).
2. They write Enc (1) on one bulletin and Enc (0) on the other, using the public key issued by the organizers as the key.

The encrypted ballots are then published on the bulletin board along with the voter ID. Everyone knows who voted, but it is impossible to understand for whom exactly, since each Enc (0) and Enc (1) are unique, and we use strong and randomized encryption. If encryption were deterministic, the voter could be forced to reveal his voice by calculating Enc (0) again and comparing it with the value on the board.

Finally, the organizers combine all the ballots for Clinton and get the result of Enc (the number of votes for Clinton), and then do the same for the ballots for Trump and get the Enc (the number of votes for Trump). Then they take the decryption key and decipher these two values, announcing the winner.

How to find a homomorphic encryption scheme? Pretty easy - schemes such as RSA and ElGamal are homomorphic in their base case because they satisfy the equation

Enc (v1) × Enc (v2) = Enc (v1 × v2)

But this is not exactly what we need - it is a multiplicative homomorphism, but we need an additive one. There are tricks that turn the RSA and ElGamal schemes into additively homomorphic, but instead I will show a less well-known scheme that is immediately additively homomorphic: the Paye cryptosystem , which encrypts message v1 to

Enc (v1) = g ^v1 r1 ⁿ mod n ²

Where n = pq and g are fixed, and r1 is a random integer from] 1; n ² [. Therefore, we have:

Enc (v1) × Enc (v2) = (g ^v1 r1 ⁿ ) × (g ^v2 r2 ⁿ ) mod n ² = g ^{v1 + v2} (r1r2) ⁿ mod n ² = Enc (v1 + v2)

That is, the Paye scheme can be used to count the encrypted votes.

Prevent fraud: zero disclosure proof

To cheat, a voter may want to write in an Enc (10,000) bulletin instead of an Enc (1) to add votes to the candidate. In the case of bad intentions, you can write Enc (very_ large_number), so that this would lead to the overflow of the whole and to the failure of the entire system. How to guarantee the admissibility of a voice (0 or 1) without decoding?

The solution will be non-interactive zero disclosure (NINR) [ non-interactive zero-knowledge , NIZK]. NINR evidence is a very complex and extremely powerful cryptographic object: in our case it will allow the voter to prove that their cryptogram contains 0 or 1, but without showing the encrypted message itself. In general, NINR-proofs allow the prover to convince the verifier of the truth of the statement by sending him only a set of data without any other types of interaction.

Perhaps the simplest system with zero disclosure is the Schnorr scheme : let's say you know the solution to the discrete logarithm problem (the difficult task behind DSA and encryption on elliptic curves), and you want to prove that you know its solution without disclosing the solution itself. That is, you know x such that g ^x = y mod p, and the verifier knows only g, y, and p. To convince the verifier, you play the following game:

1. Choose a random number r and send it to the verifier g ^r (a commitment).
2. You get a random number from the verifier (call).
3. Send to verifier s = r + cx.
4. The verifier computes g ^s = g ^{r + cx} and checks that it is equal to g ^r × y ^c = g ^r × (g ^x ) ^c .

In this interactive protocol, the prover does not reveal the value of x, since it sends only random numbers. However, only a prover who knows x can send s passing the last check.

To make such an interactive protocol non-interactive (one that can be sent in one set of data), NINR-proofs are built. We play this game on our own and simulate the verifier so that the real tester is convinced that we cannot come up with a NINR-proof without knowing the proven assertion.

Conclusion

Key ideas discussed in the article:

• The main problem of a secure electronic voting system is public verifiability. This is achieved by posting encrypted newsletters in a publicly accessible forum. Voting organizers should also describe the mechanism that conducts the confirmation itself.
• The correctness of the vote is confirmed by authorizing each voter with a unique ID and giving voters access that allows them to verify that their ballot is 1) counted and 2) not changed.
• Voters cannot be punished for voting for "wrong" candidates due to resistance to coercion, which, in particular, is achieved through unpredictable and probabilistic encryption.
• The privacy of the ballots is guaranteed by the fact that the encrypted voices are not decrypted, but only the result created using homomorphic encryption is decrypted.
• A scam does not pass if we force voters to publish cryptographic evidence of the validity of their ballot with the help of NINR.

The concepts and technologies described here may seem deep and complex, but in reality this is only the tip of the iceberg. You cannot create a securely functioning e-voting system just by following the description. For example, I omitted such details as a way for voters to check their ballots in practice, the reason for using the NINR server, and so on. The bottom line is that any secure e-voting protocol is a very complex and full of nuances, and the actual implementation adds additional complexity due to human and organizational factors.

To learn more about cryptography related to the subject of electronic voting, you can study these high-quality materials:

• David Chaum's 2004 article in IEEE S & P
• Report The Future of Voting sponsored by the US Vote Foundation
• Ben Adida's GoogleTech Talk
• How human and operational factors can compromise e-voting schemes
• Lecture notes on zero-knowledge proofs