Secure Computation Boaz Barak Slides stolen from Joe Kilian Vitali Shmatikov Cryptology The First Few Millennia Well Done Thank you Sir Cryptographer 0100101010101000111010100 Curses I cannot read the message Goal of cryptology protect messages from prying eyes Lockboxes for data data safe as long as it is locked up The Last Twenty Years Then data protected but not used Now Use data but still protect it as much as possible Secure Computation Can we combine information while protecting it as much as possible The Love Game AKA the AND game He loves me he loves me not She loves me she loves me not Want to know if both parties are interested in each other But Do not want to reveal unrequited love Input 1 I love you Input 0 I love you as a friend Must compute F X Y X Y giving F X Y to both players Can we reveal the answer without revealing the inputs The Spoiled Children Problem AKA The Millionaires Problem Yao Who has more toys Who Cares Pearl wants to know whether she has more toys than Gersh Doesn t want to tell Gersh anything Gersh is willing for Pearl to find out who has more toys Doesn t want Pearl to know how many toys he has Can we give Pearl the information she wants and nothing else without giving Gersh any information at all Distributed Cryptographic Entities S1 Public Key P S2 S3 Secret Key S Trusted public servant cheerfully encrypts decrypts signs messages when appropriate Blakley Shamir Desmedt Frankel Can break secret key up among several entities Can still encrypt decrypt sign Remains secure even if a few parties are corrupted Auctions with Private Bids 2 7 3 5 4 Auction with private bids Bids are made to the system but kept private Normal auction Players reveal bids high bid is identified along with high Only thebidders winning bid bidders are revealed Drawback thewhere losingno bids gives strategic Can we haveRevealing private bids one not away even the auctioneer information that bids bidders and auctioneers might exploit in later knows the losing auctions Electronic Voting War Final Tally Peace War 2 Peace 2 Nader 1 The winner is War War Peace Nader Secure Computation Yao Goldreich Micali Wigderson 1 2 3 4 5 X1 X2 X3 X4 X5 F1 X1 X5 F2 X1 X5 F3 X1 X5 F4 X1 X5 F5 X1 X5 Players 1 N Inputs X1 XN Outputs F1 X1 XN FN X1 XN Players should learn correct outputs and nothing else An A snuff Ideal Protocol Protocol Don t I ll Help worry I ll The carry answer for a reayour is consonable secrets to sulting fee the grave X1 F1 X1 X2 16 Tons X2 F2 X1 X2 Goal Implement something that looks like ideal protocol That 80 s CIA training sure came in handy The Nature of the Enemy 5 0 1 1 0 9 1 0 7 1 4 1 Corrupting a player lets adversary Learn its input output See everything it knew saw later sees Control its behavior e g messages sent 2 0 4 0 7 1 input output changed What can go wrong War Final Tally War War War Red Blooded American Patriots 4 1 1 4 The winner is stillWar is War Privacy Inputs should not be revealed Correctness Answer should correspond to inputs Guantanamo Terrorist Sympathizing Liberals Peace What We Can Can t Hope For Outputs may reveal inputs If candidate received 100 of the votes we know how you voted Cannot complain about adversary learning what it can by independently selecting its inputs and looking at its outputs Cannot complain about adversary altering outcome solely by independently altering its inputs Goal is to not allow the adversary to do anything else Definitions very subtle Beaver Micali Rogaway Canetti Formal definition Def Let f 0 1 n 0 1 n 0 1 n 0 1 n A 2 party protocol P is an SFE for f if Correctness Alice Bob honest with inputs x y resp then Alice learns f1 x y and Bob learns f2 x y Security for Alice If Alice honest with input x then for every cheating Bob there is a simulator S s t y Alice x Bob Security for Bob symmetric S Ideal f2 x y Can We Do It Yao GMW GV K Yes Cryptographic solutions require reasonable assumptions e g hardness of factoring Slight issues about both players getting answer at same time Goldreich Micali Wigderson BGW CCD RB Bea Yes if number of parties corrupted is less than some constant fraction of the total number of players e g n 2 n 3 No hardness assumptions necessary As long as functions are computable in polynomial time solutions require polynomial computation communication Yao s Protocol Compute any function securely First convert the function into a boolean circuit AND AND Alice s inputs NOT AND OR OR z z AND x Bob s inputs y Truth table x y z x y z 0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 1 OR x y Truth table 0 1 0 1 0 1 1 1 AND AND Alice s inputs NOT AND OR Bob s inputs OR Overview 1 Alice prepares garbled version C of C 2 Sends encrypted form x of her input x 3 Allows bob to obtain encrypted form y of his input y 4 Bob can compute from C x y the encryption z of z C x y 5 Bob sends z to Alice and she decrypts and reveals to him z Crucial properties 1 Bob never sees Alice s input x in unencrypted form 2 Bob can obtain encryption of y without Alice learning y 3 Neither party learns intermediate values 4 Remains secure even if parties try to cheat Intuition c AND a b Intuition a a b b c a b AND a b a a b b 1 Pick Random Keys For Each Wire Next evaluate one gate securely Later generalize to the entire circuit Alice picks two random keys for each wire One key corresponds to 0 the other to z 1 k0z k1z 6 keys in totalANDfor a gate with 2 input y x wires Alice Bob k0x k1x k0y k1y 2 Encrypt Truth Table Alice encrypts each row of the truth table by encrypting the output wire key with the corresponding pair of input wire keys z k0z k1z AND x Alice k0x k1x k0y k1y x y z Original truth table 0 0 1 1 0 1 0 1 0 0 0 1 y Bob Ek0x Ek0y k0z E E k Encrypted truth table k0x k1y 0z Ek1x Ek0y k0z Ek1x Ek1y k1z 3 Send Garbled Truth Table Alice randomly permutes garbles encrypted truth table and sends it to Bob z k0z k1z x Alice k0x k1x k0y k1y Ek0x Ek0y k0z Ek0x Ek1y k0z Ek1x Ek0y k0z Ek1x Ek1y k1z AND y Does not know which row of garbled table corresponds to which row of original table Bob Ek1x Ek0y k0z Ek0x Ek1y k0z Garbled truth table Ek1x Ek1y k1z Ek0x …