PowerPoint PresentationSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Secret Ballot ReceiptsTrue Voter-Verifiable ElectionsRichard CarbackKevin FisherSandi LwinCMSC 691vApril 3, 2005IntroductionSystem Features•Magic receipt•Vote visible in voting booth•Vote invisible, verifiable outside voting booth•Trusted voting machines unnecessary•Provisional ballots are ballots, too•Vote from anywhere•Adjudicate today, adjudicate tomorrow•Deeper, more restful sleep•Eliminates common indoor allergens•Even pet dander!•Boosts gas mileage up to 13%System from Voter’s Perspective•Input with touch screen or other input means•Register printer generates printout•List names of candidate•party affiliations•office sought•othersSystem from Voter’s Perspective•Print votes before the final inch•Printer prints simultaneously both layers•Review printout•Indicate layer to keep•Printer prints final inchSystem from Voter’s Perspective•Printer cuts both layers off, still laminated together and releases them•Neither layer readable on its own•Light passing through sandwiched layers without printings on either layers makes choices visibleExample of Ballot PrintoutFigure 1. An example part of a ballot printout listing a candidate selected. In addition to being able to include the candidate’s name, party affiliation, and office sought, the printout can also include other types of contests and various graphics options.Example of Final Inch TogetherFigure 2. Last inch of the printout before the two laminated layers are separated.Final Inch SeparatedFigure 3. Last inch of the printout after it’s separated: (a) the receipt (the layer the voter selects to keep) and (b) the layer that’s shredded before the voter leaves the polling place.Leaving the Polling Booth•Voter gives up the layer marked for surrender•Layer gets shredded by poll worker•Same layers get shredded “electronically”•Only physical layer voter kept and digital version of that same image remainsElection Web Site•Enter receipt’s serial # to check vote has been counted•Print image on website and check against the actual receiptResistance to Attack•Posted Receipt == Proper Tabulation (Most likely)•Votes are private (unless code is broken)•Malicious Software can only hope:–user will choose one layer–noone will check serial numbers–tally will not be auditedWeaknesses to Attack•Subliminal Channels•Selectively Malicious DRE•Discarded Receipts•Malicious Tally SoftwareVisual Cryptography 101Typography+=Newsprinte+=Ballot ReceiptVisual Cryptography 101PixelsNewsprint Ballot Receipt= 0= 10 1====001101010110====Visual Cryptography 101Message Encoding+=RandomWhite Sheet=+][+Visual Cryptography 101White Sheet VulnerabilitySingle encoded message yieldsmultiple plaintext images.Visual Cryptography 101Mixing Red and White Sheets+==+Tabulation•All receipts are posted•Each trustee decodes a batch•Batches randomized to protect privacyRussian Nesting Dolls•Voted Ballot == Set of dolls (or one big doll)•Each trustee opens one size of dolls•Smallest doll is plaintext ballotCoded Sheets•How you do this with computers•Big doll is the summation of the smaller permutations•Each trustee subtracts their permutation mod 2•Original permutation revealed at smallest dollTabulation Integrity•Need to maintain privacy•Each trustee is video-taped doing 2 batches•1 tape is released–chosen afterwards (auditor or political parties)Formal Receipt ProcessVoting Phase – Step 1Ballot image BPresident: LincolnSenator: KennedymilkeggsLINCOLNGeneral ElectionSenator:President:KENNEDYBallot Number 8675309Separate layers before leaving booth.Plaintext receiptFormal Receipt ProcessVoting Phase – Step 2< LZ , q , Dt , Db >Printed 4-tuplesBallot Number 8675309Separate layers before leaving booth.General Electionq: serial numberLZ: ballot layerDt: top dollDb: bottom dollBallot Number 8675309Separate layers before leaving booth.General ElectionFormal Receipt ProcessVoting Phase – Step 3< Lt , q , Dt , Db >Visual XOR functionLINCOLNGeneral ElectionSenator:President:KENNEDYBallot Number 8675309Separate layers before leaving booth.< Lb , q , Dt , Db >=< B , q , Dt , Db >Mathematical XOR functionFormal Receipt ProcessVoting Phase – Step 5Bottom layer: x=bBallot Number 8675309Separate layers before leaving booth.General ElectionBallot Number 8675309Separate layers before leaving booth.General ElectionTop layer: x=tFormal Receipt ProcessVoting Phase – Step 5Bottom layer: x=bSeed: sx(q)Ballot Number 8675309Separate layers before leaving booth.General ElectionOverall: ox(Lx,q,Dt,Db,sx(q))“Last Inch”Digital Signature< sx(q) , ox(Lx,q,Dt,Db,sx(q)) >Formal Receipt ProcessVoting Phase – Step 6Part 1sx(q)Ballot Number 8675309Separate layers before leaving booth.General ElectionConsistency Check(sx)-1hashqFormal Receipt ProcessVoting Phase – Step 6Part 2sx(q)Ballot Number 8675309Separate layers before leaving booth.General Electionox(Lx,q,Dt,Db,sx(q))Consistency Check(ox)-1hashqhashDbhashDthashLxFormal Receipt ProcessRed and White MatricesBallot Number 8675309Separate layers before leaving booth.General Electionmnn/2n/2WZRZFormal Receipt ProcessRed and White MatricesBallot Number 8675309Separate layers before leaving booth.General ElectionBallot Number 8675309Separate layers before leaving booth.General ElectionTop Layer Bottom LayerWt = Lti,[2j – ([i+1] mod 2)]Rt = Lti,[2j – (i mod 2)]Rb = Lbi,[2j – ([i+1] mod 2)]Wb = Lbi,[2j – (i mod 2)]WtRtRbWbFormal Receipt ProcessRed and White MatricesBallot Number 8675309Separate layers before leaving booth.General ElectionBallot Number 8675309Separate layers before leaving booth.General ElectionTop Layer Bottom LayerBx = Rx WyWtRtRbWbFormal Receipt ProcessCryptographic Pseudorandom Number GeneratorsBallot IDKey12345CiphertextAESAES123461010100..100100111..00N bitsFormal Receipt ProcessCalculating the Noise MatrixWZi,j = (dZk dZk-1 … dZ1)[mj–m]+1dZk = h’(d’Zk)d’Zk = h(sZ(q), k)sZ(q)Pseudorandom sequenceh’hdZk =
View Full Document
Unlocking...