INNOVATE

Anonymous Elections (II)

Vote codes, blind signatures and anonymous channels

Note: Read part I of this article here.

Secrecy is important to all voters regardless of their choice or voting method. We all wish for our vote to remain secret, not only on election day but also for some long time after. Usually, by a “long time after the election,” we mean forever or, at least, long enough that revealing votes will not harm us. The damage that could be caused from breaching voters’ privacy is enormous and varies from potential punishment for “making a wrong choice” to algorithms predicting future electoral behavior. Even if there are no direct consequences, the mere possibility of deanonymization in the future might make voters vote more carefully, which will affect both results and participation, and thus harm democracy.

Hence, it should not be possible to link a vote to the voter who has cast it, neither today nor in the future. This means an online voting system must somehow remove this link, which was created in the first place to verify that a ballot was cast by an actual eligible voter. One way to meet both requirements is by encrypting the votes first (so that no one sees what is inside during transmission), digitally signing them, and anonymizing the ballot box before the counting (so no one can link decrypted results with voters’ identities). As we have already explained in previous posts, one way to do so would be to use a mix-net, which is a mathematical way to mimic shaking a bag full of identical objects to mix them. Another known method is a homomorphic tally, which permits obtaining election results without decrypting individual votes.

Recall that, for mix-nets and homomorphic tally, all encrypted votes arrive in the ballot box signed by the voters, and we only anonymize them before decryption. Also, the decryption key is distributed among several trustees (e.g., the members of an electoral board or commission), and we assume at least one trustee will not allow the decrypting of individual votes or obtaining provisional results before the election finishes. Assuming that at least one trustee is honest, and that the encryption cannot be broken implies that no one can decrypt ballots before their anonymization is complete and the link is broken. Yet, a quantum computer will change that.

Once it becomes powerful enough to break today’s public key encryption, anyone keeping old election records can easily break privacy. Even if the ballot box is kept private and not publicly available (so only election authorities can see all cast votes), someone could still collect all encrypted data sent by a voter to an online voting system. What is more concerning: the ballots we cast today and will cast tomorrow might not remain private in the foreseeable future since the quantum computing field advances rapidly. Also, even if privacy concerns in the post-quantum future seem too far-fetched, dishonest trustees might directly decrypt individual votes and pose problems for secrecy now.

Considering this, one might wonder: Can we do anything to protect privacy against future quantum computers or dishonest trustees? The first thing that comes to mind is to upgrade online voting systems to use post-quantum cryptography. It will not save us from dishonest trustees but will help against a quantum computer. However, it is not easy to do so without significant performance setbacks. Therefore, maybe we need to consider alternative methods for vote anonymization — something other than mix-nets and homomorphic tally.

One idea is to no longer send ciphertexts to the voting system and instead send codes, which the system would interpret as the selection. The codes must be unique per voter, or else it would be obvious who votes in the same way. This is known as a vote-code-based voting system. The expectation is that, without ciphertexts, there would be nothing for a quantum computer to decrypt. So how would it work?

Of course, voters must somehow know which vote code corresponds to which voting options — perhaps, receiving a paper-based voting card before the election. The issue with anonymity here is that someone has to generate, print, and securely deliver voting cards before the election begins. Such an entity, say an election authority, would have enormous power over the election result — a simple swap of voting codes during printing would change votes without anyone noticing.

Any attempt to reduce the power entrusted to the election authority would imply a combination of audits and distributing responsibilities to several entities exchanging some encrypted data. But, without switching to post-quantum encryption, records of these exchanges or auditable data would eventually be able to break privacy.

Even if we forget about these difficulties related to voting cards, the election authority (at some point) must publish the corresponding ciphertext next to each selected code. However, this means that anyone keeping records of which codes correspond to which voter can break privacy in the post-quantum future. The only way to avoid this is to make the process non-transparent and ask the election authority to output just the election result.

Another idea is to anonymize votes before casting them by using anonymous credentials. This is probably the most common approach for ensuring that dishonest trustees are not able to break individual privacy. How does it work? For example, we can use a primitive called blind signature to make the election authorities sign a voter’s ballot as eligible without seeing it. It is like a club membership card, which proves the holder can enter the club but gives no additional information such as name, age, etc.

Unfortunately, despite the name, anonymous credentials do not provide a 100% privacy guarantee. Consider that, realistically, registration (obtaining credentials) and voting (sending ballots) usually happen without a significant time delay. It might be easy to link voters with their votes if they cast them at odd hours. For example, if only one person registered at 6 am on Sunday and shortly after that one vote appeared on the ballot box — we can be reasonably sure that the vote belongs to that voter. Increasing the time between registration and voting would only result in problems with intermediate credentials safe-keeping and would prolong the opportunity for credential theft and coercion. Also, even though blind signatures do not reveal voters’ identities directly, voters can be deanonymized via metadata such as their IP address, cookies, etc.

Alternatively, a voter may send a vote via an anonymous channel, which hides the sender from the receiver. This is another method frequently used for ensuring malicious trustees cannot harm the votes’ secrecy. Unfortunately, it has drawbacks too. First, such channels are notoriously hard to implement in practice. Existing solutions like Tor are susceptible to side-channel attacks and not quantum-computer resistant. Therefore, anyone collecting the traffic can break vote privacy one day. Second, by design, anonymous channels do not allow for nullifying extra votes, which is required if a voter votes via multiple channels: in person, online, by postal, etc. Third, to prevent non-eligible participants or multiple vote-casting from one person, each ballot must arrive with proof of eligibility. Since such eligibility proof must not be linked to a voter’s identity, it can be easily given to anyone without detection, thus facilitating vote-selling and coercion.

All in all, alternatives to mix-nets and homomorphic tally — vote codes, blind signatures, and anonymous channels — do not solve all privacy concerns. Vote codes require sacrificing verifiability and putting a lot of trust in the voting system and election authorities. Blind signatures do not fully ensure vote secrecy. And anonymous channels are vulnerable to quantum computers.

This article was written by Tamara Finogina, Cryptography Researcher at Scytl.