Internet voting is a hard problem: there are many ways to fail, and the cost of failing is high. Furthermore, the security requirements appear to be self-contradicting at times. Verifiability requires that a voter, let’s say Alice, must have sufficient knowledge about her ballot to detect if it was tampered with, while Privacy requires that Alice’s vote remains secret, even if Alice herself is bribed or forced into revealing everything she knows.
Can we build a system that allows Alice to verify that her ballot remains unchanged, but also allows her to “forget” who she voted for?
In joint work with Véronique Cortier, Georg Fuchsbauer and David Galindo we present a solution to this problem, in the form of BeleniosRF. We use rerandomizable encryption to change how ballots are encrypted without changing their contents. Digital signatures and zero knowledge techniques ensure ballot integrity, and prevent any tampering during the rerandomization.
Verifiability and privacy
Verifiability means that there must be some way for voters to monitor the election such that they can detect foul play from other voters, or even officials. This is often split into two notions: individual verifiability, dealing with a voter monitoring the way her vote was processed (i.e. that it was not changed or simply thrown away), and universal verifiability, covering requirements for the entirety of the election (e.g. “every ballot must be valid”).
Privacy, in its simplest form, keeps the contents of a vote secret from malicious observers, or even authorities and other compromised voters. In plain terms, we don’t want hackers to decrypt votes, and we don’t allow authorities to decrypt votes when they’re not supposed to; current systems anonymize votes by shuffling or summing them before they are decrypted.
Unfortunately, the above discussion fails to cover one potential adversary: the voter herself. An adversarial voter might be fully corrupt, as in the case of a vote seller who does not value her vote apart from any potential financial gain, or simply be placed in a coercive environment where she is “encouraged” to vote the “right” way. A good voting system should aim to hinder vote sellers and protect coerced users. This might not be possible in all cases: if a voter is monitored 24/7 or simply prevented from voting, the problem may well be unsolvable.
For this reason we often choose to relax the requirements with regard to coercive attacks. One possible relaxation is called “Receipt Freeness”. Intuitively, Receipt Freeness allows Alice to claim she forgot everything to do with her vote, or simply lie about who she voted for, without Eve the coercer being able to tell. Any answer by Alice is equally credible. In turn, this implies that if Eve is attempting to coerce Alice, she will need to actively monitor her until she votes (thus making coercion harder, riskier and more expensive).
Receipts, and why you don’t want them
A receipt, in the context of Receipt Freeness, is any piece information that would enable a voter to prove to a coercer or vote buyer that she voted in a particular way. If Eve tries to bribe or threaten Alice but does not monitor her, it should be impossible for Eve to know if Alice complied or not. In particular, even if Alice complies, she will be unable to produce compelling evidence of that (i.e. a receipt).
In current practice, it is common for in-person voting systems to produce paper documents, called voting receipts for voters to take home. In many instances, the information on them is extremely limited, sometimes only certifying that one has in fact voted. When they do include more information, they are usually meant to be disposed of within the voting station. Needless to say, these are not the receipts that “Receipt Freeness” is about.
To avoid confusion, we will call the receipts we are interested in “full receipts” i.e receipts that include (at a minimum) the voter’s selections, as well as enough auxiliary information for a coercer or vote buyer to cross-check the receipt against the public record – otherwise a voter could simply lie to the coercer. In many internet voting systems, the public record often includes a Bulletin board containing the entirety of the encrypted ballots submitted to an election. So, in a vote selling situation, the receipt would enable the vote seller to convince the buyer about the contents of a ballot. Naturally, we consider this a privacy violation. Therefore an internet voting system should not allow voters to obtain full receipts.
Returning to the issue of verifiability, we want to enable the voter to check that her vote was not tampered with on the way from her computer to the bulletin board. This poses a dilemma: if we leave the ballot entirely unmodified, the voter might choose to keep a full receipt; the standard voting interface might not support this, but we assume a motivated party might tamper with the browser. But if we change the ballot in some way so as to make receipts useless, what is left for the user to check?
In BeleniosRF we use a cryptographic solution to this dichotomy. We use a construction called Extractable Signed Rerandomizable Ciphertexts (ESRC), to produce ballots than can be fully rerandomized while being verifiable, unforgeable and tamper-proof.
How you can verify your vote
BeleniosRF uses two components to provide verifiability for individual votes: a bulletin board, and a digital signature placed on every ballot by the voter. The security properties of the digital signature guarantee that only Alice can sign votes in her name. If Alice signs a ballot containing a vote supporting Bob, and posts it on the board, we are guaranteed that no third party will be able to produce a ballot for a different candidate with Alice’s signature on it. This means that a potentially malicious authority will not be able to take a ballot for Bob, and switch it to support Donald without invalidating Alice’s signature, which will then be detected.
This guarantees that Alice’s ballot will either be posted unadulterated or not at all. At the same time, since the bulletin board is public and updated in real-time, Alice will know almost immediately if the ballot was maliciously dropped.
How we foil reproduction
At the same time, we need to interpose an extra step between Alice and the bulletin board. Otherwise, if the bulletin board simply posted Alice’s ballot, completely unchanged, then Alice could keep a full receipt: she could simply save all the values she used to compute her ballot. Anyone could then check and see if the saved values did in fact produce the ballot posted on the bulletin board. In BeleniosRF we defend against this by adding an additional re-randomization server. This server re-randomizes the ballot submitted by Alice so that it looks like a new, freshly produced ballot, seemingly unrelated to the original, but without changing her vote. Informally, this is almost as if Alice forgets everything about her ballot: she simply does not know the corresponding encryption randomness. Because of our verifiability guarantees, the server cannot tamper with Alice’s choice without being detected.
Note here that the security guarantees of the attached signature only prevent us from producing new ballots for a different candidate. Thus, our intended use case (new ballot with the same vote) is explicitly allowed, while any foul play (e.g trying to change the candidate during randomization, or trying to replace the ballot with an invalid one) would be caught.
The end result is a system in which Alice knows that her vote is counted as it was cast, but she cannot be forced to reveal it: she has no way to reproduce the final encrypted ballot and any answer she gives is equally plausible.
Our paper, “BeleniosRF: A Non-Interactive Receipt-Free Electronic Voting Scheme” will be presented at ACM CCS 2016, in October. A preprint is available.