Create Presentation
Download Presentation

Download Presentation
## Privacy, Democracy and the Secret Ballot

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Privacy, Democracy and the Secret Ballot**An Informal Introduction to Cryptographic Voting ?**Talk Outline**• Background on Voting • Voting with Mix-Nets • Voting and Privacy • A Human-Verifiable Voting Scheme • Splitting trust between multiple authorities**A [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)**Voting: The Challenge**• Requirements based on democratic principles: • Outcome should reflect the “people’s will” • Fairness • One person, one vote • Privacy • Not a principle in itself;required for fairness • Cast-as-intended • Counted-as-cast Additional requirements: Authorization, Availability**The 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” No No Yes No Yes Yes No Yes No No No No No**How 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 counter i1 i2 in … v1 v2 vn Tally**Privacy 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 Commitments**Who 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: • Destroy part of the ballot in the booth [Chaum] • Hide order of events in the booth [Neff] • Next: a “hidden-order” based protocol • Receipt-free • Universally verifiable • Everlasting Privacy**Alice 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 them**Commitment 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 boxes**Additional 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 whispering**Ernie Casts a Ballot**• Ernie whispers his choice to Mr. Drew I like Alice**Ernie 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**Ernie Casts a Ballot**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 contents Ernie**Ernie**Ernie Ernie Casts a Ballot Weigh 1Open 2Open 3 • 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 weight**Ernie Casts a Ballot**Open 1Weigh 2Open 3 • If the “Ernie” box doesn’tcontain 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-k Ernie**Ernie 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, and 10g weights in the boxes he weighs I like Alice Open 1Weigh 2Weigh 3**Ernie**Ernie Casts a Ballot: Full Protocol • Ernie whispers his choice and a fake challenge to Mr. Drew • Mr. Drew puts a box on the scale • it should contain a 20g weight • Mr. Drew puts k “Alice” proof boxesand k “Bob” proof boxes on the table • Bob boxes contain 10g or 20g weights according to the fake challenge I like Alice Open 1Weigh 2Weigh 3**Ernie**Ernie Ernie Casts a Ballot: Full Protocol Open 1Open 2Weigh 3 • Ernie shouts the “Alice” (real) challenge and the “Bob” (fake) challenge • Drew responds to the challenges • No matter who Ernie voted for,The protocol looks exactly the same! Open 1Weigh 2Weigh 3**r**Implementing “Boxes and Scales” • We can use Pedersen commitment • G: a cyclic (abelian) group of prime order p • g,h: generators of G • No one should know loggh • To commit to m2Zp: • Choose random r2Zp • Send x=gmhr • Statistically Hiding: • For any m, x is uniformly distributed in G • Computationally Binding: • If we can find m’m and r’ such that gm’hr’=x then: • gm-m’=hr-r’1, so we can compute loggh=(r-r’)/(m-m’)**r**s Implementing “Boxes and Scales” • To prove equivalence of x=gmhr and y=gmhs • Prover sends t=r-s • Verifier checks that yht=x h g h g t=r-s**A “Real” System**Hello Ernie, Welcome to VoteMaster Please choose your candidate: Alice Bob 1 Receipt for Ernie 2 o63ZJVxC91rN0uRv/DtgXxhl+UY= 3 - Challenges - 4 Alice: 5 Sn0w 619- ziggy p3 6 Bob: 7 l4st phone et spla 8 - Response - 9 9NKWoDpGQMWvUrJ5SKH8Q2CtwAQ= 0 === Certified ===**A “Real” System**Hello Ernie, You are voting for Alice Please enter a fake challenge for Bob Alice: l4st phone et spla Bob : Continue 1 Receipt for Ernie 2 o63ZJVxC91rN0uRv/DtgXxhl+UY= 3 - Challenges - 4 Alice: 5 Sn0w 619- ziggy p3 6 Bob: 7 l4st phone et spla 8 - Response - 9 9NKWoDpGQMWvUrJ5SKH8Q2CtwAQ= 0 === Certified ===**A “Real” System**Hello Ernie, You are voting for Alice Make sure the printer has output twolines (the second line will be covered)Now enter the real challenge for Alice Alice: Sn0w 619- ziggy p3 l4st phone et spla Bob : Continue 1 Receipt for Ernie 2 o63ZJVxC91rN0uRv/DtgXxhl+UY= 3 - Challenges - 4 Alice: 5 Sn0w 619- ziggy p3 6 Bob: 7 l4st phone et spla 8 - Response - 9 9NKWoDpGQMWvUrJ5SKH8Q2CtwAQ= 0 === Certified ===**A “Real” System**Hello Ernie, You are voting for Alice Please verify that the printed challengesmatch those you entered. Alice: Sn0w 619- ziggy p3 l4st phone et spla Bob : Finalize Vote 1 Receipt for Ernie 2 o63ZJVxC91rN0uRv/DtgXxhl+UY= 3 - Challenges - 4 Alice: 5 Sn0w 619- ziggy p3 6 Bob: 7 l4st phone et spla 8 - Response - 9 9NKWoDpGQMWvUrJ5SKH8Q2CtwAQ= 0 === Certified ===**A “Real” System**Hello Ernie, Thank you for voting Please take your receipt 1 Receipt for Ernie 2 o63ZJVxC91rN0uRv/DtgXxhl+UY= 3 - Challenges - 4 Alice: 5 Sn0w 619- ziggy p3 6 Bob: 7 l4st phone et spla 8 - Response - 9 9NKWoDpGQMWvUrJ5SKH8Q2CtwAQ= 0 === Certified ===12**Ernie**Fay Guy Heidi Counting the Votes • Mr. Drew announces the final tally • Mr. Drew must prove the tally correct • Without revealing who voted for what! • Recall: Mr. Drew is committed toeveryone’s votes Alice: 3Bob: 1**Ernie**Fay Guy Heidi Counting the Votes Weigh WeighOpen • Mr. Drew puts k rows ofnew boxes on the table • Each row should contain the same votes in a random order • A “random beacon” gives k challenges • Everyone trusts that Mr. Drewcannot anticipate thechallenges Alice: 3Bob: 1**Ernie**Fay Guy Heidi Ernie Fay Guy Heidi Counting the Votes Weigh WeighOpen • For each challenge: • Mr. Drew proves that the row contains a permutation of the real votes Alice: 3Bob: 1**Ernie**Fay Guy Heidi Counting the Votes Weigh WeighOpen • For each challenge: • Mr. Drew proves that the row contains a permutation of the real votes Or • Mr. Drew opens the boxes andshows they match the tally Alice: 3Bob: 1**Ernie**Fay Guy Heidi Counting the Votes Weigh WeighOpen • If Mr. Drew’s tally is bad • The new boxes don’t matchthe tally Or • They are not a permutationof the committed votes • Drew succeeds with prob.at most 2-k Alice: 3Bob: 1**Ernie**Fay Guy Heidi Counting the Votes Weigh WeighOpen • This prototocol does notreveal information aboutspecific votes: • No box is both opened andweighed • The opened boxes are ina random order Alice: 3Bob: 1**Interim Summary**• Background on Voting • Voting with Mix-Nets • Voting and Privacy • A Human-Verifiable Voting Scheme • Universally-Verifiable • Receipt-Free • Based on commitment with equivalence testing • Next • Splitting trust between multiple authorities**Protocol Ingredients**• Two independent voting authorities • Public bulletin board • “Append Only” • Private voting booth • Private channel between authorities**Protocol Overview**#1 Left #1 Right • Voters receive separateparts of the ballot from the authorities • They combine the parts to vote • Some of the ballot is destroyed to maintain privacy • No authority knows all of the destroyed parts • Both authorities cooperate to tally votes • Public proof of correctness (with everlasting privacy) • Even if both authorities cooperate cheating will be detected • Private information exchange to produce the proof • Still maintains computational privacy**Casting a Ballot**#1 Left #1 Right • Choose a pair of ballots to audit #2 Left #2 Right #1 Left #1 Right**Casting a Ballot**• Choose a pair of ballots to audit • Open and scan audit ballot pair #2 Left #2 Right #1 Left #1 Right**Private Booth**Casting a Ballot • Choose a pair of ballots to audit • Open and scan audit ballot pair • Enter private voting booth • Open voting ballot pair #2 Left #2 Right #2 Left #2 Right**Private Booth**Casting a Ballot • Choose a pair of ballots to audit • Open and scan audit ballot pair • Enter private voting booth • Open voting ballot pair • Stack ballot parts • Mark ballot D,G A,F B,E C,H**Private Booth**Casting a Ballot • Choose a pair of ballots to audit • Open and scan audit ballot pair • Enter private voting booth • Open voting ballot pair • Stack ballot parts • Mark ballot • Separate pages**Private Booth**Casting a Ballot • Choose a pair of ballots to audit • Open and scan audit ballot pair • Enter private voting booth • Open voting ballot pair • Stack ballot parts • Mark ballot • Separate pages • Destroy top (red) pages • Leave booth. Scan bottom pages Commitment to letter order Random letter order: different on each ballot**Forced Destruction Requirement**• Voters must be forced to destroy top sheets • Marking a revealed ballot as spoiled is not enough! • Coercer can force voter to spoil certain ballots • Coerced voters vote “correctly” 50% of the time • Attack works against other cryptographic voting systems too**Checking the Receipt**• Receipt consists of: • Filled-out bottom (green) pages of voted ballot • All pages of empty audit ballot • Verify receipt copy on bulletin board is accurate Audited Unvoted Ballots Audit checks that commitment matches ballot**Counting the Ballots**• Bulletin board contains commitments to votes • Each authority publishes “half” a commitment • Doesn’t know the other half • We can publicly “add” both halves • “Homomorphic Commitment” • Now neither authority can open! • We need to shuffle commitments before opening • Encryption equivalent is mix-net • Won’t work for everlasting privacy: not enough information**Counting the Ballots**• We need an oblivious commitment shuffle • Idea: Use homomorphic commitment and encryption over the same group • Publicly “add” commitments • Publicly shuffle commitments • Privately perform the same operations using encryptions • Just enough information to open, still have privacy**Oblivious Commitment Shuffle**• Show a semi-honest version of the protocol • Real protocol works in the malicious model • We’ll use a clock analogy for homomorphic commitment and encryption**Modular addition with clocks**Oblivious Commitment Shuffle x+y ← z