How Encryption Can Secure Online Voting

Note: Some of the information presented here is intentionally oversimplified. Particular details depend on the actual implementation, as there are numerous ways and alternative cryptographic techniques that achieve the same goals.

"The biggest challenge of remote e-voting is to achieve high level of security under an uncontrolled environment and insecure platform. E-voting properties and many different classifications that set the minimum requirements are already established. Some of these classifications are just the same properties under different names such as: confidentiality, integrity, privacy, democracy, universality, verifiability, etc.. Regardless, the goal is always to conciliate two apparently mutually exclusive proprieties: verifiability and privacy."

The fundamental idea behind online voting is verifiability in the sense that votes are to be encrypted and made public, convincing the voters without a margin of doubt that the whole procedure was conducted regularly. Let’s delve into how this can be achieved, but before reading the rest of the article, we suggest watching Ron Rivest's presentation of this idea[1] up to 5:07.

Then, let’s consider:

And now here is the mathmagic...

The final tally is thus D( E(v1+v2+v3+v4) ) where D is the decryption function that can be computed by anyone once the poll ends without the need to access v individually: D(E(v1) ), D(E(v2) ) etc., which can only be decrypted by making use of the private keys...

Only voters themselves can decrypt v individually and actually check that their own vote is registered correctly! In conclusion, voters can verify both their votes and the final tally with privacy and accuracy!

Wow! I can verify that my vote is correct! But how can I be sure that votes cast by others are also legal without using their private keys?

Let’s say we attribute the value of 0 to mean a refusal for a given policy proposal that is being polled and 1 to be being in concordance, forming a set of possible answers {0,1}. A verifier, which could be anyone, may want to be sure that all the entries published on the append-only table correspond to a valid element in the set of possible answers and not anything else, such as what would be an entry with value 100. Zero-knowledge proofs allow precisely for this. To understand how, it may help first to understand what ZKPs really are. "In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information apart from the fact that the statement is indeed true."[2]

It may seem contradictory, but with ZKPs any voter may prove unequivocally the validity of their vote! Again, a vote is but a representation of an element from amongst a set of possible choices. To understand how ZKPs should be applied to voting, we suggest taking a look at the following articles[3], [4] as they address this question in more detail.

This technique can then be extended to include sets larger than {0,1} while preserving the mathematical properties of both homomorphic encryption and ZKPs, allowing for more complex polls than the simple yes, no / agree, disagree answers. This makes for interesting use cases such as multiple candidate elections, referendums that could have different solution proposals for a single given issue, questionnaires in market research...

We have just discussed how anyone can check the final tally, that their vote is the one intended, and how all the other votes were legal! All the while preserving voters’ privacy! The way these algorithms are put together, preserving the proprieties of both homomorphic encryption and ZKP is complex and requires a deep knowledge of cryptography, which can be mathematically proven to be true.[5]

There are other details and cryptographic techniques regarding cybersecure online voting, as with the use of stealth addresses[6], at least in blockchains that keep all transactions public such as Ethereum. These are used to avoid linking voters and their wallets. But we consider this a technical detail, of concern only to the software developers and not something that all users of online voting should be aware of, unlike homomorphic encryption and ZKPs whose knowledge helps build trust in the system.

How are these private keys generated and given to the voter without compromising security?

Ultimately, the private keys need to be tied to the true identity of the user in order to prevent double-spending. One approach is to use PKIs provided by trusted authorities such as state issued eID embedded in national identity smart cards... Because surely, the public institutions have thought of their own mechanisms to keep these keys secured, right?

In any case this is an issue more related to digital identity itself which we are to analyse in a future article in order to spare the reader of too many details and to keep information better organized. Suffice to say that while digital identity itself is a complex issue on its own right, there are ways to guarantee with relative confidence that each digital persona is unique by empowering multiple trusted entities with the task of attesting to the identity of a person. A quote often attributed to Abraham Lincoln and immortalized in a song by Bob Marley accurately describes what we will argue:

“You can fool some people some times but you can't fool all the people all the time”

What happens if a voter detects fraud or if is coerced physically to vote in a certain way?

The first measure to be taken is to provide a channel where people can report these situations so that these occurrences are taken into consideration. If they are marginal, representing 0,01% of the total votes, for example, this would not really be a problematic situation unless we are discussing a very sensitive referendum that requires democratic values to be upheld and where the final tally is close to the equivalent of a 50/50 situation. This can be mitigated by requiring the majority consensus to be higher, such as 55/45 in order for a poll to be considered valid.

In the scenario where someone sees that their vote was incorrectly registered, considering that the whole apparatus is supported by blockchain and thus not in control of a particular system administrator providing the service, the more reasonable approach is to assume that the voting machine itself is compromised and not the whole blockchain. The most direct protective measures to be taken then would be for the voter to change the machine and/or OS. This issue is more related to cybersecurity threats, the likes of social engineering and malware. Using open-source hardware and software is recommended, as well as using amnesic OS[7]. Amnesic software always returns to its initial configured state, so even if voters install malware by unintentionally clicking and running a virus, rebooting the machine rolls back the software to an unaltered configuration, effectively mitigating these occurrences.

Another situation that one may want to account for is a situation where the voter is coerced to vote in a certain way, either physically or by blackmail. The only approach to defend against coercion other than living in a decent society is to allow revoting to occur on the same poll. There is research[8] in this area, although ways to merge this technique with all the others mentioned above remain, to our knowledge, to be implemented. Surely there is a way. In any case, reopening the polling phase is always a possibility. It should be noted also that preventing coercion would also prevent vote selling, for obvious reasons.

We do not argue for a complete abandonment of paper voting because, at the very least in presence, paper voting is an excellent opportunity to put identity to the test (real or digital), but nevertheless, we feel strongly in favor of its adoption in politics as a complementary tool able to generate consensus faster while also being a secondary source confirming the results of paper voting.

Are we there yet?

As computer scientist Jeffrey Dean eloquently put:

“The driving force behind modern computer ciphers isn’t security, but efficiency. The question is not can you create a secure cipher. You can. The question is whether you can create one that will work efficiently on huge data sets, or on very limited hardware”

The challenge of blockchain tech is precisely its ability to scale as the user base and demand for computation grows. Current implementations of cryptographic algorithms in online voting backed by blockchain estimate the costs to be around $10 per vote as implemented in Ethereum.[14] Researchers believe that improvements can be made in order to lower this value to under $1 by making use of a faster blockchain as well as tweaking the underlying mathematical algorithms.

Throughout history, cryptography has played a major role in changing the course of events. The Caesar cipher, one of the most simple cryptographies, is famous for having been used by the Roman emperor two millennia ago. The Allies’ ability to intercept and decrypt messages encrypted by the Japanese cipher machine Purple and the German Enigma was crucial to providing the key advantage necessary to end WWII.

For those who know how to program and are interested in learning more, we suggest reading this research paper.[15] You can also play with CryptoBallot to get acquainted with this type of software.[16]

In conclusion, cybersecure online polling is not only possible but highly needed. Its adoption in the political space has the potential to be one of the most disruptive events in our lifetimes... All you need to do is trust the algorithms running on your computer and the blockchain and if you don't, you can always do the maths with a pen and paper yourself.

References:

[1] "Was YOUR vote counted? (feat. homomorphic encryption)" by professor Ron Rivest, Numberphile, on YouTube, 2016. https://www.youtube.com/watch?v=BYRTvoZ3Rho

[2] Zero-knowledge proof entry on Wikipedia, https://en.wikipedia.org/wiki/Zero-knowledge_proof

[3] "How to use ZKP to prove set membership without exposing the set or the member" by Anders Borch, author's blog, 2019. https://blog.cyborch.com/how-to-use-cryptographic-accumulators-to-prove-set-membership-without-exposing-the-set-or-the-member/

[4] "Zero-Knowledge Proofs for Set Membership" by Dario Fiore, on ZKProof Standards, 2020. https://zkproof.org/2020/02/27/zkp-set-membership/

[5] "Non-interactive Zero-Knowledge from Homomorphic Encryption" by Ivan Damg ̊ard et al., Theory of Cryptography Conference, 2006. https://cs.nyu.edu/\~nicolosi/papers/NonIntSi.pdf

[6] "Stealth Address (Cryptocurrency)" by Jake Frankenfield, Investopedia, 2022. https://www.investopedia.com/terms/s/stealth-address-cryptocurrency.asp

[7] Tails (operating system) entry on Wikipedia, https://en.wikipedia.org/wiki/Tails_(operating_system)

[8] "VoteAgain: A scalable coercion-resistant voting system" by Wouter Lueks et al., Spring Labs, Universidad Carlos III de Madrid, 2020. https://arxiv.org/pdf/2005.11189.pdf

[9] The Heritage Foundation, https://www.heritage.org/

[10] "Ainda mais indícios de fraude nas Legislativas 2022?" entry on YouTube, in portuguese, 2022. https://www.youtube.com/watch?v=L8fA9aOuR9k

[11] "AnaKarina denuncia "FRAUDE ELEITORAL" por parte da CNE" entry on YouTube, in portuguese, Angola, 2022. https://www.youtube.com/watch?v=hLm8ocLgXCU

[12] "Frequently Asked Questions - Voter Fraud", https://www.voteaustralia.org.au/faq_voter_fraud

[13] "Democracy Index 2020: In sickness and in health?" report by The Economist Intelligence Unit, 2020. https://www.eiu.com/n/campaigns/democracy-index-2020/

[14] "ethVote: Towards secure voting with distributed ledgers" by Johannes Mols et Emmanouil Vasilomanolakis, Aalborg University, Denmark, 2020. https://www.researchgate.net/publication/341000573_ethVote_Towards_secure_voting_with_distributed_ledgers

[15] "Remote e-voting overview" by NERV, a paper submission to the 14th ICEGOV Conference in 2021, https://ia601401.us.archive.org/33/items/remote-e-voting-overview/Remote e-voting overview.pdf

[16] CryptoBallot, https://github.com/cryptoballot/cryptoballot