New version page

Princeton COS 433 - Electronic Voting

Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

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 PresidentCory “the Coercer” wants to rig the electionHe can intimidate all the studentsOnly Mr. Drew is not afraid of CoryEverybody trusts Mr. Drew to keep secretsUnfortunately, Mr. Drew also wants to rig the election Luckily, he doesn't stoop to blackmailSadly, all the students suffer severe RSIThey can't use their hands at allMr. 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 identicalEven if the weights are hidden in a box!The only actions we allow are:Open a boxCompare two boxesAdditional RequirementsAn “untappable channel”Students can whisper in Mr. Drew's earCommitments are secretMr. Drew can put weights in the boxes privatelyEverything else is publicEntire class can see all of Mr. Drew’s actionsThey can hear anything that isn’t whisperedThe whole show is recorded on video (external auditors)I’m whisperingErnie Casts a BallotErnie whispers his choice to Mr. DrewI like AliceErnieErnie Casts a BallotMr. Drew puts a box on the scaleMr. Drew needs to prove to Ernie that the box contains 20gIf he opens the box, everyone else will see what Ernie voted for!Mr. Drew uses a “Zero Knowledge Proof”Ernie Casts a BallotMr. Drew puts k (=3) “proof” boxes on the tableEach box should contain a 20g weightOnce the boxes are on the table, Mr. Drew is committed to their contentsErnieErnie Casts a BallotErnie “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” boxAsks Mr. Drew to open the boxIt should contain a 20g weightErnieWeigh 1Open 2Open 3ErnieErnie Casts a BallotErnieOpen 1Weigh 2Open 3Ernie Casts a BallotIf the “Ernie” box doesn’t contain a 20g weight, every proof box:Either doesn’t contain a 20g weightOr doesn’t weight the same as theErnie boxMr. Drew can fool Ernie with probability at most 2-kErnie Casts a BallotWhy 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
Download Electronic Voting
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Electronic Voting and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Electronic Voting 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?