Electronic VotingTalk OutlineA [Very] Brief History of VotingVoting: The ChallengeComparison of systemsThe Case for Cryptographic VotingVoting with Mix-NetsHow Private is Private?Privacy is not Enough!Flavors of Cryptographic PrivacyWho can you trust to encrypt?A New Breed of Voting ProtocolsAlice and Bob for Class PresidentCommitment with “Equivalence Proof”Additional RequirementsErnie Casts a BallotSlide 17Slide 18Slide 19Slide 20Slide 21Ernie Casts a Ballot: Full ProtocolSlide 23Implementing “Boxes and Scales”Slide 25A “Real” SystemSlide 27Slide 28Slide 29Slide 30Counting the VotesSlide 32Slide 33Slide 34Slide 35Slide 36Interim SummaryProtocol IngredientsProtocol OverviewCasting a BallotSlide 41Slide 42Slide 43Slide 44Slide 45Forced Destruction RequirementChecking the ReceiptCounting the BallotsSlide 49Oblivious Commitment ShuffleSlide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Summary and Open QuestionsSlide 59Electronic VotingBoaz Barak(many slides taken from Tal Moran)Talk Outline•Background on Voting•Voting with Mix-Nets•Voting and Privacy•A Human-Verifiable Voting Scheme•Splitting trust between multiple authoritiesA [Very] Brief History of Voting•Ancient Greece (5th century BCE)•Paper Ballots –Rome: 2nd century BCE(Papyrus)–USA: 17th century•Secret Ballots (19th century)–The Australian Ballot•Lever Machines•Optical Scan (20th century)•Direct Recording Electronic(DRE)•Requirements based on democratic principles:–Outcome should reflect the “people’s will”•Fairness - one person, one vote•Privacy – (required for fairness)Voting: The Challenge•Honest Intentions – no vote buying, coercion.•Cast as intended – no accidental, malicious miscasting of vote.•Count as cast – all votes cast are counted and no more. •Verifiable count – independent verification of counts.Comparison of systemsHonest IntentionsCast as intendedCount as castVerifiable countPaper ballot Public vote Touchscreen / DREYY??NYYYYY?Y?NThe Case for Cryptographic Voting•Elections don’t just name the winnermust convince the loser they lost!•Elections need to be verifiable•Counting in public:–Completely verifiable–But no vote privacy•Using cryptography , we can get both!Voting with Mix-Nets•Idea due to David Chaum (1981) •Multiple “Election Authorities”–Assume at least one is honest•Each voter creates “Onion Ballot”•Authorities decrypt and shuffle•No Authority knows all permutations–Authorities can publish “proof of shuffle”NoNoYesNoNoYesNoNoYesNoYesNoNoHow Private is Private?•Intuition: No one can tell how you voted•This is not always possible•Best we can hope for:–As good as the “ideal” vote counterv1v2vn…Tallyi1i2inPrivacy is not Enough!•Voter can sell vote by disclosing randomness•Example: Italian Village Elections–System allows listing candidatesin any order–Bosses gave a different permutation of“approved” candidates to each voter–They could check which permutationsdidn’t appear•Need “Receipt-Freeness”[Benaloh&Tuinstra 1994]Flavors of Cryptographic Privacy•Computational–Depends on a computational assumption–A powerful enough adversary can “break” the privacy guarantee–Example: Mix-Nets (public-key encryption)•Unconditional–Privacy holds even for infinitely powerful adversary–Example: Statistically-Hiding Commitment•Everlasting–After protocol ends, privacy is “safe” forever–Example: Unopened Statistically-Hiding CommitmentsWho can you trust to encrypt?•Public-key encryption requires computers•Voting at home–Coercer can sit next to you•Voting in a polling booth–Can you trust the polling computer?•Verification should be possible for a human!•Receipt-freeness and privacy are also affected.A New Breed of Voting Protocols•Chaum introduced first “human-verifiable” protocol in 2004•Two classes of protocols:1. Destroy part of the ballot in the booth [Chaum]2. Hide order of events in the booth [Neff]•Next: a “hidden-order” based protocol–Receipt-free–Universally verifiable–Everlasting PrivacyAlice and Bob for Class PresidentCory “the Coercer” wants to rig the electionHe can intimidate all the studentsOnly Mr. Drew is not afraid of CoryEverybody trusts Mr. Drew to keep secretsUnfortunately, Mr. Drew also wants to rig the election Luckily, he doesn't stoop to blackmailSadly, all the students suffer severe RSIThey can't use their hands at allMr. Drew will have to cast their ballots for themCommitment with “Equivalence Proof”We use a 20g weight for Alice......and a 10g weight for Bob Using a scale, we can tell if two votes are identicalEven if the weights are hidden in a box!The only actions we allow are:Open a boxCompare two boxesAdditional RequirementsAn “untappable channel”Students can whisper in Mr. Drew's earCommitments are secretMr. Drew can put weights in the boxes privatelyEverything else is publicEntire class can see all of Mr. Drew’s actionsThey can hear anything that isn’t whisperedThe whole show is recorded on video (external auditors)I’m whisperingErnie Casts a BallotErnie whispers his choice to Mr. DrewI like AliceErnieErnie Casts a BallotMr. Drew puts a box on the scaleMr. Drew needs to prove to Ernie that the box contains 20gIf he opens the box, everyone else will see what Ernie voted for!Mr. Drew uses a “Zero Knowledge Proof”Ernie Casts a BallotMr. Drew puts k (=3) “proof” boxes on the tableEach box should contain a 20g weightOnce the boxes are on the table, Mr. Drew is committed to their contentsErnieErnie Casts a BallotErnie “challenges” Mr. Drew; For each box, Ernie flips a coin and either:Asks Mr. Drew to put the box on the scale (“prove equivalence”)It should weigh the same as the “Ernie” boxAsks Mr. Drew to open the boxIt should contain a 20g weightErnieWeigh 1Open 2Open 3ErnieErnie Casts a BallotErnieOpen 1Weigh 2Open 3Ernie Casts a BallotIf the “Ernie” box doesn’t contain a 20g weight, every proof box:Either doesn’t contain a 20g weightOr doesn’t weight the same as theErnie boxMr. Drew can fool Ernie with probability at most 2-kErnie Casts a BallotWhy is this Zero Knowledge?When Ernie whispers to Mr. Drew,he can tell Mr. Drew what hischallenge will be.Mr. Drew can put 20g weights in the boxes he will open,
View Full Document