CS 261 Week 12 Notes - E-VotingEric KimNovember 14, 20111 Why do Electronic Voting?We want to do Electronic Voting (E-Voting) because it gives us operational efficiency. It’s mucheasier to do an electronic election (say, using a DRE system) than a paper-based ballot, since apaper-based election has a lot of overhead (such as printing the ballots, making sure there areenough paper ballots, transporting the paper ballots, etc). In addition, E-Voting allows voting tobe more accessible to those with special needs (say, vision-impairment).In the past, those with impairments (motor, visual, etc) would have another person (friend,spouse, etc.) perform the vote for him or her. This isn’t desirable, since the system is deprivingthat impaired voter of anonymity and independence. With an E-Voting system however, there canbe special machines that are geared towards allowing those with impairments to still successfullycast a vote.2 Why is E-Voting hard? (the ’voting’ problem)2.1 Problem 1: The Secret Ballot problemAll votes should be anonymous and untraceable - in addition, there shouldn’t be a way to provethat a voter voted in a certain way. We want this in order to avoid vote coercion or blackmailing -consider a scenario where Bob is trying to force Alice to vote for Chuck. If Bob is unable to verifythat Alice voted for Chuck, then it is impossible for Bob to force Alice to vote for Chuck, sinceBob will be unable to verify Alice’s vote.So, we just can’t maintain voting logs.2.2 Problem 2: ConfidenceWe must be confident in the election results - more importantly, ’ordinary’ people (i.e. non Ph.Dpeople) should be able to hold confidence in the voting system. For instance, a voting system thatuses a crazy amount of complicated cryptography would seem questionable to an ordinary memberof the public. A voting system that requires experts to understand/verify the system isn’t ideal.Another problem with election confidence is that the election officials in charge are typicallyappointed by the party in power - thus, there is a potential conflict of interest there.3 The (Initial) Rise of E-VotingDuring the Florida 2000 election, the punch-card voting systems used caused a lot of highly-publicized problems. As a result, Congress allocated $4 billion in order to upgrade voting systems.1Since the money was only to be used within a certain time frame, DRE’s (Direct Recording Elec-tronic) systems were widely deployed. However, they were deployed before many computer scientistsgot involved with the systems.4 The Paper Arrives (2006)Just after many jurisdictions bought the DRE systems (with the Congress money), the Princetonpaper was published in 2006. The people behind the paper managed to get their hands on one ofthe Diebold DRE systems (via a pretty shady means), and exposed many serious vulnerabilitieswith the system. Such vulnerabilities included the ability to rewrite the bootloader, steal/modifyvotes, and spread the malicious software via a DRE virus. Further follow-up surveys on othersystems discovered vulnerabilities.5 The Fall of E-VotingThe shift towards E-Voting systems have since reversed. Before Congress allocated $4 billion, E-Voting usage was about 33% . After the Congress allocation, the usage jumped to 66% - however,now it’s back down to 33% . In addition, there has been a significant uptick in vote-by-mailvotes. For instance, Oregon and Washington only has vote-by-mail. They claim that vote-by-mailelections are cheaper to perform.6 ThreeBallot Voting SystemRon Rivest developed a ”cryptographic end-to-end voter verifiable” voting system called the Three-Ballot Voting System. It was an attempt to allow the voter to verify that his/her vote was tal-lied correctly, while providing verifiability and anonymity. However, it had some privacy issues(whoops).7 CryptographyWe’d like to prevent undetectable large-scale vote stealing. Assume that we have a trusted votingofficial with a public key K0.Say that each DRE machine publishes the encrypted votes (encrypted with public key K0)EK0(vi) in a random order. How can we verify that the votes were correctly tallied?7.1 Random Sampling7.1.1 Analogy: Drug-LordSay you’re a drug lord, and you’re about to do a big, $100K deal. At the meeting place, the otherparty comes with 5000 stacks of $20 bills. You don’t have enough time to check each $20 bill (thecops might come!), so instead you randomly select a small subset of the bills, and verify those.With a certain confidence interval, you can be sure that the bills are good.7.1.2 In the voting systemWhen the user votes, the machine spits out a mag-strip card that contains EK0(v). The user canthen either accept it, or ask for the vote to be verified. In other words, can the system prove to me2that the encryption was done correctly?The hope is, if small fraction of the voting population asks to verify the vote (say, 10%), thenwith high probability any false encryptions (i.e. vote tampering) can be detected.Note that, in order to preserve anonymity, if the voter asks for proof, then the vote is canceled,so the voter has to re-vote.7.2 How to prove that the encryption was done correctly?Any cryptographic encryption function Epublickeyis a deterministic function of the form: Epublickey(v) =f(publickey, v, r) , where r is the source of randomness. So, if the machine gives us r, then we cancompute our own f (p, v, r) to verify the machine’s output Epublickey(v).7.3 How to tabulate {EK0(v1), ..., EK0(vn)}?The trick is being able to decrypt in a verifiable way, in addition to preserving anonymity. The ideais: given the ciphertexts of the votes {c1, ..., cn}, first randomly permute the array of ciphertexts(to preserve anonymity). Then, the election official decrypts the ciphertext to an array of votes:{v1, ..., vn}. Then, the election official creates a (private) mapping from each cito its correspondingvi. The voting official then randomly selects 1/2 of the edges (i.e. mappings from cito vi), andprovides proofs that each ci= vi(same proof as from earlier).While this system offers great integrity (provided you completely trust the voting official), itmeans that only 1/2 of the votes get anonymity. Bummer!The solution is to ”chain” the above scheme:37.4 A chain of indirectionHave the election official encrypt each cito get an array {d1, ..., dn} . Then, choose 1/2 of theseedges such that there doesn’t exist a path from a dito a vi(in order to provide anonymity).To choose