Electronic Voting, Spring 2020

Secret Ballot Receipts

There are two core ideas in Chaum's secret-ballot receipt idea:

• Visual Cryptography -- essentially an exclusive or operator done with two layers of transparency. Pixels in the image look grey if the two layers of that pixel are the same, and black if the two layers are different. Start with a random layer, duplicate all the pixels that should be grey in the image, flip all the pixels that should be black, an both layers will look entirely random until you align them, then the image will pop out. The voter keeps half, the election authorities get the other half.

• Mix Nets -- don't use true randomness, instead, the key to decrypting the visual cryptography is a pseudorandom number. A mix net allows the authorities to decode the ballots in multiple steps, shuffling after each step, so that by the time the ballots are decoded, the connection to the voter who cast the ballot is lost.

Scantegrity II

Chaum invented mix-nets as the basis of an e-cash scheme, so naturally, this is another mix-net scheme. This time, instead of visual cryptography, ballots are 2-layer optical-scan ballots, where one layer has candidate names printed next to holes in the ballot over each voting target. The bottom layer has voting targets where each target is pre-printed with pseudo-random codes using invisible ink. To vote, you daub the ballot with an invisible chemical that "develops" the invisible code for the cadidate. You can keep the top layer (with the names on it), while the bottom layers are scanned. Candidate names on each ballot are shuffled pseudorandomly, and mix-nets are used, as with the first scheme, to recover the votes.

Scantegrity II has been used on an experimental basis in a municipal election in Takoma Park, Maryland, a suburb of Washington DC. It worked, but in the paper on that election, survey results show that over 10% of survey respondents did not trust the system.

When Chaum proposed his scheme in 2004, I was impressed. Mix nets are really cool, so is visual cryptography. The problem is, how do you explain these schemes to your average voter. An election system that is provably secure against lots of attacks but can't be explained to someone who doesn't have a PhD is not going to end conspiracy theories about election rigging. I challenged Chaum to figure out how to explain his system to my grandmother. Since then, he and other proponents of end-to-end voting have come a long way, but it's not clear that they've passed my "grandmother test."