Cryptographic protocols for electronic voting

Transfer

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

For cryptographic researchers, electronic voting is primarily not a matter of a voting machine or an online voting — it’s just a field for mathematical research . E-voting research involves creating 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 already real technologies used for real elections: in the city of Tacoma-Maryland State Park, voters trusted Scantegrity II, based on paper invisible ink bulletins, and the cryptographers themselves used Helios online voting systems to elect the leadership.

Electronic voting is a super-complex 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 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. It must be able to do this without disclosing his vote, and more generally, 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 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:

The voter receives a token in the form of a bulletin, which changes according to his choice. Different voters receive different ballots.
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.
The organizers publish encrypted bulletins on a bulletin board, a “public broadcast channel with memory,” in the jargon of cryptographers - to put it more simply, on something like Pastebin.
The organizers combine encrypted bulletins to calculate the encrypted total. Then they decipher it (but not the bulletins themselves!) And publish the results.
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, the 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:

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

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.

And how to find a homomorphic encryption scheme? Pretty easy - schemes such as RSA and ElGamal are homomorphic in their basic versions, since they satisfy the equation

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

But this is not exactly what we need - it is a multiplicative homomorphism, and 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 , encrypting 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 ^v1r1 ⁿ ) × (g ^v2 r2 ⁿ ) mod n ² = g ^{v1 + v2} (r1r2) ⁿ mod n ² = Enc (v1 + v2)

That is, the Peye 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 Enc (1) to add votes to a candidate. In the case of bad intentions, you can write Enc (very_ large_number) to cause the whole to overflow and the entire system to fail. How to guarantee the admissibility of a voice (0 or 1) without decoding?

The solution is 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:

Choose a random number r and send it to the verifier g ^r (a commitment).
You receive from the verifier a random number with (call).
Send to verifier s = r + cx.
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 will be able to 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 independently play this game and simulate the verifier so that the real verifier is convinced that we cannot come up with 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 on 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 can not 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 proof 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:

Tags: