### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# IntroModern Cryptography CSE 107

GPA 3.69

### View Full Document

## 17

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 133 page Class Notes was uploaded by Jacey Olson on Thursday October 22, 2015. The Class Notes belongs to CSE 107 at University of California - San Diego taught by Mihir Bellare in Fall. Since its upload, it has received 17 views. For similar materials see /class/226790/cse-107-university-of-california-san-diego in Computer Science and Engineering at University of California - San Diego.

## Reviews for IntroModern Cryptography

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15

PSEUDO RANDOM FUNCTIONS mt 155 Recall We studied security of a block cipher against key recovery But we saw that security against key recovery is not sufficient to ensure that natural usages of a block cipher are secure We want to answer the question What is a good block cipher where good means that natural uses of the block cipher are secure We could try to define good by a list of necessary conditions 0 Key recovery is hard 0 Recovery of M from C EKM is hard 0 But this is neither necessarily correct nor appealing 255 Turing Intelligence Test a human Q What does it mean for a program to be intelligent in the sense of u ago 355 Turing Intelligence Test Q What does it mean for a program to be intelligent in the sense of a human Possible answers 0 It can be happy 0 It recognizes pictures 0 It can multiply 0 But only small numbers n 5 39 E 6qu 355 Turing Intelligence Test Q What does it mean for a program to be intelligent in the sense of a human Possible answers o It can be happy o It recognizes pictures o It can multiply 0 But only small numbers 0 Clearly no such list is a satisfactory answer to the question 355 Turing Intelligence Test Q What does it mean for a program to be intelligent in the sense of a human Turing39s answer A program is intelligent if its inputoutput behavior is indistinguishable from that of a human 455 Turing Intelligence Test Room 0 Rom 1 Opaque wall Opaque wall Keyboard Keyboard Tester Tester Behind the wall 0 Room 1 The program P 0 Room 0 A human Turing Intelligence Test Room 0 Room 1 7 E Opaque wall Opaque wall Keyboard Keyboard Tester Tester Game 0 Put tester in room 0 and let it interact with object behind wall 0 Put tester in rooom 1 and let it interact with object behind wall 0 Now ask tester which room was which 665 Turing Intelligence Test Room 0 Room 1 7 E Opaque wall Opaque wall Keyboard Keyboard Tester Tester Game 0 Put tester in room 0 and let it interact with object behind wall 0 Put tester in rooom 1 and let it interact with object behind wall 0 Now ask tester which room was which The measure of intelligence of P is the extent to which the tester fails 665 Turing Intelligence Test Room 0 Room 1 7 E Opaque wall Opaque wall Keyboard Keyboard Tester Tester Game 0 Put tester in room 0 and let it interact with object behind wall 0 Put tester in rooom 1 and let it interact with object behind wall 0 Now ask tester which room was which Clarification Room numbers are in our head not written on door 755 Real versus Ideal Notion l Real object l Ideal object Intelligence Program Human Block cipher 7 Real versus Ideal Notion Real object Ideal object Intelligence Program Human Block cipher Random function Random functions A random function with L bit outputs is implemented by the following box Fn where T is initially L everywhere Fn X If TX L then 4 Return TX 955 Random function Game Randmlp procedure FnX if Tx L then Txlti01L return TX Adversary A 0 Make queries to Fn 0 Eventually halts with some output We denote by Pr Randfmy d the probability that A outputs d 1055 Random function Game Rand mp adversary A y e Fn01 return y 000 procedure Fnx if Tx L then Tx lti0713 return TX Pr Randfoyu3 trUe 7 Random function Game Rand mp adversary A y e Fn01 return y 000 procedure Fnx if Tx L then Tx lti0713 return TX Pr Randfoylp true 2 3 Random function Game Rando13 adversary A procedure Fnx y1 H Fquot00 if Tx L then Tx lt1 07 13 yz H Fn11 return TM return yl 010 Ayg 011 Pr Rand40713 true vqu 1255 Random function Game Rando13 adversary A procedure Fnx y1 H Fquot00 if Tx L then Tx lt1 07 13 yz H Fn11 return TM return yl 010 Ayg 011 Pr Rand40713 true 2 6 7 vqu 1255 Random function Game Rando13 adversary A procedure Fnx y1 e FnOQ if Tx L then Tx lt1 07 13 yz H Fn11 return TX return yl 69 yz 101 Pr Randfoyu3 true Random function Game Rando13 adversary A procedure Fnx y1 H Fquot00 if Tx L then Tx lt1 07 13 yz H Fn1139 return TX return VI 69 y 101 Pr Rand40713 true 2 3 Function families A family of functions F KeysF x DomF a RangeF is a two argument map For K E KeysF we let FK DomF a RangeF be defined by VX E DomF FKX FKX Examples 0 DES KeysF 0156 DomF RangeF 0164 0 Any block cipher DomF RangeF and each FK is a permutation 1455 Real versus Ideal Notion Real object l Ideal object PRF Family of functions eg a block cipher Random function F is a PRF if the input output behavior of FK looks to a tester like the input output behavior of a random function Tester does not get the key K 1555 PRF adversaries Let F KeysF x DomF a RangeF be a family of functions A prf adversary our tester has an oracle Fn for a function from DomF to RangeF It can 0 Make an oracle query X of its choice and get back Fnx 0 Do this many times 0 Eventually halt and output a bit d 1555 Repeat queries We said earlier that a random function must be consistent meaning once it has returned y in response to X it must return y again if queried again with the same X This is why we have the if in the following written as Game procedure Fnx RandRangeF if Tx 7e L then Tx i RangeF Return TX Henceforth we make a rule 0 A prf adversary is not allowed to repeat an oracle query Then our game is Game procedure Fnx RandRangeF TX lti Ra ngeF Return TX 1755 PRF adversaries Let F KeysF x DomF a RangeF be a family of functions Real world Ideal Random world X Fn A y y lt1 RangeF lntended meaning A39s output d I think I am in the 1 Real world 0 Ideal Random world The harder it is for A to guess world it is in the better F is as a PRF 1355 Let F KeysF x DomF a RangeF be a family of functions Game Real Game RandRangeF procedure Initialize procedure Fnx K i KeY5F TX lti RangeF procedure Fnx Return Tx Return FKX Associated to FA are the probabilities Pr Real ili Pr Rand angeF1 that A outputs 1 in each world The advantage of A is Advg M Pr Real il 7 PI Rand ang jli 1955 Let F 01quot x 01128 a 01128 be defined by FKX X Let prf adversary A be defined by adversary A if Fn0128 0128 then Ret 1 else Ret 0 Game Real procedure Initialize Real world Klti 07 1k A L Fn procedure Fnx y y H FKX Return FKX 2055 Let F 01quot x 01128 a 01128 be defined by FKX X Let prf adversary A be defined by adversary A if Fn0128 0128 then Ret 1 else Ret 0 Game Real procedure Initialize K i 0 1k procedure Fnx Return FKX Real world Then Pr Real ili 2055 Let F 01quot x 01128 a 01128 be defined by FKX X Let prf adversary A be defined by adversary A if Fn0128 0128 then Ret 1 else Ret 0 Game Real procedure Initialize Real world MW A procedure Fnx lt Return FKX Then Pr Real il 1 because the value returned by Fn will be Fn0128 FK0128 0128 so A will always return 1 2055 Let F 01quot x 01128 a 01128 be defined by FKX X Let prf adversary A be defined by adversary A if Fn0128 0128 then Ret 1 else Ret 0 Game RandRangeF procedure Fnx X Fn TX071L A y y lt1 0 1 8 Return TX 7 Then Ideal Random world Pr Rand angeF1 2155 Let F 01quot x 01128 a 01128 be defined by FKX X Let prf adversary A be defined by adversary A if Fn0128 0128 then Ret 1 else Ret 0 Game RandRangeF procedure Fnx X Fn TX071L A y y lt1 0 1 8 Return TX 7 Then Ideal Random world Pr Rand angeF1 pr Fn0128 0123 2123 because Fn0128 is a random 128 bit string 2155 Example Advantage computation Let F 01quot x 01128 a 01128 be defined by FKX X Let prf adversary A be defined by adversary A if Fn0128 0128 then Ret 1 else Ret 0 Then 1 2128 x A r AdvIEIfM Pr Real il 7 Pr Rand angeFl 17 27128 2255 The measure of success Let F KeysF x D0mainF a RangeF be a family of functions and A a prf adversary Then AdvIEIfM Pr Real il 7 Pr Rand angeFll is a number between 71 and 1 A large close to 1 advantage means 0 A is doing well 0 F is not secure A small close to O or g 0 advantage means 0 A is doing poorly o F resists the attack A is mounting 2355 PRF security Adversary advantage depends on its 0 strategy 0 resources Running time t and number q of oracle queries Security F is a secure PRF if AdvIEIfA is small for ALL A that use practical amounts of resources Example 80 bit security could mean that for all n 180 we have Advgrfm 2n for any A with time and number of oracle queries at most 280 Insecurity F is insecure not a PRF if there exists A using few resources that achieves high advantage 2455 Example 1 Define F 01k x 01128 a 01128 by FKX X for all kx s F a secure PRF Real Rand X Fn X Fn yi y e FKX yi y lt1 07 1128 Can we design A so that AdvIEIfM Pr Real il 7 Pr Rand angeFll is close to 1 2555 Example 1 Define F 01k x 01128 a 01128 by FKX X for all kx s F a secure PRF Real Rand X Fn X Fn yi y e FKX yi y lt1 07 1128 Can we design A so that AdvIEIfM Pr Real il 7 Pr Rand angeFll is close to 1 Exploitable weakness of F FK0128 0128 for all K We can determine which world we are in by testing whether Fn0128 0128 2555 Example 1 Real Rand X Fn X Fn L A New Now F is defined by FKX X adversary A if Fn0128 0128 then return 1 else return 0 2555 Example 1 Analysis F is defined by FKX X adversary A if Fn0128 0128 then return 1 else return 0 Real Rand A X Fn A X Fn L y e FKx L y lt1 0 112 We already analysed this and saw that Pr Real ill 1 Pr Rand angef ll 2 128 2755 Example 1 Conclusion F is defined by FKX X adversary A if Fn0128 0128 then return 1 else return 0 Then 1 2128 r quot AdvIEIfM Pr Real il 7 Pr Rand angeFl 1 7 27128 and A is efficient Conclusion F is not a secure PRF 2355 Example 2 Define F 01l x 01l a 01l by FKX K 63 X for all KX s F a secure PRF Real Rand X Fn X Fn A A MW Can we design A so that AdvIEIfM Pr Real il 7 Pr Rand angeFll is close to 1 2955 Example 2 Define F 01 x 01 a 01 by FKX K 63 X for all KX s F a secure PRF Real Rand X Fn X Fn A A MW Can we design A so that AdvIEIfM Pr Real il 7 Pr Rand angeFll is close to 1 Exploitable weakness of F FK0 ea FK1 K ea 0 ea K 691 1l for all K We can determine which world we are in by testing whether Fn0 ea Fn1 1l 2955 Example 2 The adversary F 01 X 01 a 01 is defined by FKX K 63 X adversary A if Fn0l 63 Fn1l 1 then return 1 else return 0 Example 2 Real world analysis F 01 x 01l a 01 is defined by FKX K 63 X adversary A if Fn0l 63 Fn1l 1 then return 1 else return 0 Game Real Real world procedure Initialize K H 07 1k A 4 procedure Fnx lt7 Return FKX 3155 Example 2 Real world analysis F 01 x 01l a 01 is defined by FKX K 63 X adversary A if Fn0l 63 Fn1l 1 then return 1 else return 0 Game Real procedure Initialize Real world procedure Fnx lt7 Return FKX quotlt T39I39I 7 Then Pr Real il 3155 Example 2 Real world analysis F 01 x 01l a 01 is defined by FKX K 63 X adversary A if Fn0l 63 Fn1l 1 then return 1 else return 0 Game Real procedure Initialize Real world procedure Fnx lt7 Return FKX quotlt T39I39I 7 Then Pr Realgel 1 because Fn0 Fn1 FK0 FK1 K0 Kea1 1 3155 Example 2 Ideal world analysis F 01l x 01l a 01l is defined by FKX K 63 X adversary A if Fn0l 63 Fn1l 1l then return 1 else return 0 Game RandRangeF Ideal random world procedure Fnx A X Fquot TXlti01l return TX y y H 071l 3255 Example 2 Ideal world analysis F 01l x 01l a 01l is defined by FKX K 63 X adversary A if Fn0l 63 Fn1l 1l then return 1 else return 0 Game RandRangeF Ideal random world procedure Fnx A X Fn TXlti01l return TX y y e 01l Then Pr Real il 3255 Example 2 Ideal world analysis F 01l x 01l a 01l is defined by FKX K 63 X adversary A if Fn0l 63 Fn1l 1l then return 1 else return 0 Game RandRangeF Ideal random world procedure Fnx A X Fn TXlti01l return TX y y e 01l Then Pr Real il Pr Fn1l 63 Fn0l 1l 3255 Example 2 Ideal world analysis F 01l x 01l a 01l is defined by FKX K 63 X adversary A if Fn0l 63 Fn1l 1l then return 1 else return 0 Game RandRangeF Ideal random world procedure Fnx A X Fn TXlti01l return TX y y e 01l Then Pr Real il Pr Fn1l 63 Fn0l 1l 2 l because Fn0l Fn1l are random 6 bit strings 3255 Example 2 Conclusion F 01 x 01l a 01 is defined by FKX K 63 X adversary A if Fn0l 63 Fn1l 1 then return 1 else return 0 Then 1 2 1 r quot AdvIEIfM 7 Pr Real il 7 Pr Rand angeFl 17 2quot and A is efficient Conclusion F is not a secure PRF 3355 Birthday Problem q people 17 7 q with birthdays y17yq E 17365 Assume each person39s birthday is a random day of the year Let C3657 q Pr 2 or more persons have same birthday Pr yl7 yq are not all different 0 What is the value of C3657 q o How large does q have to be before C3657 q is at least 12 3455 Birthday Problem q people 17 7 q with birthdays y17yq E 17365 Assume each person39s birthday is a random day of the year Let C3657 q Pr 2 or more persons have same birthday Pr yl7 yq are not all different 0 What is the value of C3657 q o How large does q have to be before C3657 q is at least 12 Naive intuition o C3657 q z q365 0 q has to be around 365 3455 Birthday Problem q people 17 7 q with birthdays y17yq E 17365 Assume each person39s birthday is a random day of the year Let C3657 q Pr 2 or more persons have same birthday Pr yl7 yq are not all different 0 What is the value of C3657 q o How large does q have to be before C3657 q is at least 12 Naive intuition C365 q z q365 0 q has to be around 365 The reality 0 3657 q z 72365 0 q has to be only around 23 M 3455 Birthday collision bounds C3657 q is the probability that some two people have the same birthday in a room of q people with random birthdays C 3555 Birthday Problem Pick y17 7Yqltil77N and let CN7qPry17 Birthday setting N 365 yq not all distinct Birthday Problem Pick y17 7Yqltil77N and let CN7 q Pry17 yq not all distinct Birthday setting N 365 Fact CN7 q z ZLN Birthday collisions formula LetY17yqilN Then 17 CN7q Pry1yq all distinct 1EEHMW N N N l l 11 so 171 CNq17i11 lt17Ngt u 5 39 Birthday bounds Let Cqu Pry17 Fact Then yq not all distinct WV 1 707 1 3 ltCN lt05 O N 7 7 7 7 N where the lower bound holds for 1 q 3 x2N C2 C1 PI C1 V C2 7 PI C1 PI C2 7 PI C1 A C2 S PI39C1 PI39C2 More generally PrC1C2Cq PrC1PrC2PrCq n 5 39 39 nu vqu 3955 Arithmetic sums 012 Aq71 nu RG 4055 Arithmetic sums 012H q71 qqf 1 2 nu RG 4055 Birthday bounds Let CN7 q Pry17 yq not all distinct Then CN7 q g 05 M N Proof of this upper bound Let C be the event that Yi E Y177ygt1 Then CN q PrC1 v c2 ch PrC1PrC2PrCq lt 9lmLl 7 N N N ail 2N 39 4155 Block ciphers as PRFs Let E 01quot x 01 a 01 be a block cipher Real Rand A X Fn A X Fn yi ye EKX yi yi01l Can we design A so that AdvgrfA Pr Real31 7 Pr Randfmml is close to 1 4255 Block ciphers as PRFs Defining property of a block cipher EK is a permutation for every K So if X17 Xq are distinct then 0 Fn EK Fnx17 Fnxq distinct o Fn random Fnx17 Fnxq not necessarily distinct Let us turn this into an attack 4355 Birthday attack on a block Cipher E 01quot x 01 a 071V a block cipher adversary A Let X17 7Xq 6 01 be distinct for 17 q do y e FnX if y1 yq are all distinct then return 1 else return 0 Real world analysis Let E 01k x 01l a 01l be a block cipher Game RealE adversary A l procedure Initialize Let 39X17 Xq 6 01 be distinct KR 1k for1qd0yanX 7 if y1 yq are all distinct Emcedlgelnlx then return 1 else return 0 eturn K X Then Pr Real il 4555 Real world analysis Let E 01k x 01l a 01l be a block cipher Game RealE adversary A l procedure Initialize Let 39X17 Xq 6 01 be distinct KR 1k for1qd0yanX 7 if y1 yq are all distinct Emcedlgelnlx then return 1 else return 0 eturn K X Then Pr Real31 1 because yl yq will be distinct because EK is a permutation 4555 Ideal world analysis Let E 01K x 01l a 01l be a block cipher adversary A Game Rand01 Let X1 Xq E 01l be distinct procedure Fnx for i 1 q do y e FnX TM 1 011 if y1 yq are all distinct Return TX then return 1 else return 0 Then Pr Rand0111 Pry1 yq all distinct 1 C2Z7 q because y1 yq are randomly chosen from 01 4555 Birthday attack on a block Cipher E 01quot x 071 a 01 a block cipher adversary A Let X17 Xq 6 01 be distinct for1qd0yanX if y1 yq are all distinct then return 1 else return 0 1 1C22q x A AdvIEfM Pr Real il 7 Pr Rand angeFl C2l7 q qq 71 gt 03 T so q x 202 Advgrfm z 1 4755 Birthday attack on a block cipher Conclusion If E 01quot x 01l a 01 is a block cipher there is an attack on it as a PRF that succeeds in about 2 2 queries Depends on block length not key length H 6 i2l2i Status DES2DES3DES3 64 i 232 i Insecure AES 128 i 264 i Secure 4355 KR security versus PRF security We have seen two possible metrics of security for a block cipher E 0 KR security It should be hard to get K from input output examples of EK o PRF security It should be hard to distinguish the input output behavior of EK from that of a random function Question Is it possible for E to be 0 PRF secure but 0 NOT KR secure 4955 KR security versus PRF security Question Is it possible for a block cipher E to be PRF secure but not KR secure Why do we care Because we 0 agreed that KR security is necessary 0 claim that PRF security is sufficient for secure use of E so a YES answer would render our claim false Luckily the answer to the above question is NO 5055 KR security versus PRF security Fact PRF security implies 0 KR security 0 Many other security attributes Why does PRF security imply KR security Claim KR insecurity PRF insecurity Real world Ideal Random world A 4X Fquot X Fn 4L yeFle A y yiRangeU U If you give me a method B to defeat KR security I can design a method A to defeat PRF security What A does 0 Use B to find key K 0 Test whether Fnx FKX for some new point X o If this is true decide it is in the Real world 5255 Why does PRF security imply KR security Issues To run B adversary A must give it input output examples under FK We have A give B input output examples under Fn This is correct in the real world but not in the random world Nonetheless we can show it works 5355 Course Information CSE 107 Introduction to Modern Cryptography Instructor Mihir Bellare Website http wwwcse ucsd eduusersmihiIcse107 Cryptography usage Did you use any cryptography 0 today Cryptography usage Did you use any cryptography 0 today 0 over the last week Cryptography usage Did you use any cryptography 0 today 0 over the last week 0 over the Christmas break rm ago 255 ryptograph usage Anlaznnculn checkmu Sign In F 0 Erie gen yiew gm Euukmarks tears ueip Jucimri Getting Started lteiesi sac Heedhnes iv we in Ordering fI39Dm Amazoncom is quick and easy Enter ynur emeii address 7 lam a new Customer vuu H create a password hater o https invokes the Secure Socket Layer SSL communication security protocol to securely transmit your credit card number to the s rver o SSL uses cryptography 7 V 355 Cryptography usage Other uses of cryptography 0 ATM machines 0 On Iine banking 0 Remote login and file transfer using SSH rm vocxov 455 What is cryptography abo t Public network Adversary clever person with powerful computer Goals a Data privacy a Data integrity and authenticity 555 Public network M N a Adversaw A The goal is to ensure that the adversary does not see or obtain the data message M Example M could be a credit card number being sent by shopper Alice to server Bob and we want to ensure attackers don t learn it 656 Integrity and authenticity Public network The goal is to ensure that a M really originates with Alice and not someone else a M has not been modified in transit 755 Integrity and authenticity example Bob Alice Bank Alice Pay 100 to Charlie Adversary Eve might 0 Modify Charlie to Eve 0 Modify 100 to 1000 Integrity prevents such attacks 355 Medical databases Doctor Reads FA Get Alice FA Modifies FA to FA Data base Alice FA Bob FB Put Alice FA Alice FA Bob FB Medical databases Doctor Database GetFAIIce Alice FA Reads FA A Bob FB Modifies FA to FA Put Alice FA Alice FA Bob FB 0 Privacy FA7 FA contain confidential information and we want to ensure the adversary does not obtain them 955 Medical databases Doctor Database GetFAIIce Alice FA Reads FA A Bob FB Modifies FA to FA Put Alice FA Alice FA Bob FB 0 Privacy FA7 FA contain confidential information and we want to ensure the adversary does not obtain them 0 Integrity and authenticity Need to ensure doctor is authorized to get Alice39s file FA7 FA are not modified in transit FA is really sent by database FA is really sent by authorized doctor 955 What is cryptography abo t Public network Adversary clever person with powerful computer Goals a Data privacy a Data integrity and authenticity 1u5a Ideal World Public network Crypmmum pipe Adversary A Cryptonium pipe Cannot see inside or alter content 1155 Ideal World Public network Crypmmum pipe Adversary A Cryptonium pipe Cannot see inside or alter content All our goals would be achieved 1155 Ideal World Public network Crypmmum pipe Adversary A Bb Cryptonium pipe Cannot see inside or alter content All our goals would be achieved But cryptonium is only available on planet Crypton and is in short supply 1155 Cryptographic schemes Alice Adversary A 5 encryption algorithm Ke encryption key D decryption algorithm Kd decryption key 12 5a Cryptographic schemes Alice Adversary A 5 encryption algorithm Ke encryption key D decryption algorithm Kd decryption key Algorithms standardized implemented publicl 12 5a Cryptographic schemes AdversaryA 5 encryption algorithm Ke encryption key D decryption algorithm Kd decryption key Settings 0 publicekey assymmetric Ke public Kd secret o privateekey symmetric Ke Kd secret 13 5a Cryptographic schemes Alice Adversary A 5 encryption algorithm Ke encryption key D decryption algorithm Kd decryption key How do keys get distributed7 Magic for now39 was Cryptographic schemes Mi Adversaw A Our concerns 0 How to define security goals7 0 How to design 5 D7 o How to gain confidence that 5 D achieve our goals7 1556 Cryptographic schemes Adversary A Computer Security How does the computersystem protect KeKd from breakein Viruses worms 08 holes 7 CSE 127227 Cryptography How do we use Ke Kd to ensure security of communication over an insecure network7 CSE 107207 16 5a Why is cryptography hard possibilities is infinite 0 One cannot anticipate an adversary strategy in advance number of 0 Testing is not possible in this setting Early history Substitution ciphersCaesar ciphers Ke Kd 7r X a La secret permutation eg X A7 B7 C7 and 7139 is as follows quotEn WCAB 7rC7rA7rB Z E A DHZEA 7r 1Z7r 1E7r 1A CAB 1355 Early history Substitution ciphersCaesar ciphers Ke Kd 7r X a La secret permutation eg X A7 B7 C7 and 7139 is as follows quotEn WCAB 7rC7rA7rB Z E A DAZEA 7r 1Z7r 1E7r 1A C A B Not very secure Common newspaper puzzle 1355 The age of machines Enigma German World War II machine Broken by British in an effort led by Turing 1956 Shannon and One Time Pad OTP Encryption Kede Ki01k K Chosen at random from 0 1k For any M E O1k 8KM Kaa M DKC KGB C 2056 Shannon and One Time Pad OTP Encryption Kede Ki01k K chosen at random from 0 1k For any M E O1k 8KM Ke M DKC KGB C Theorem Shannon OTP is perfectly secure as long as only one message encrypted Perfect secrecy a notion Shannon defines captures mathematical impossibility of breaking an encryption scheme Fact if lMl gt then no scheme is perfectly secure 2056 Modern Cryptography A Computational Science Security ofa quotpracticalquot system must rely not on the impossibility but on the computational dif culty of breaking the system Practical more message bits than key bits Modern Cryptography A Computational Science Rather than quotIt is impossible to break the schemequot We might be able to say quotNo attack using 2160 time succeeds With probability 2 2 20quot e Attacks can exist as long as cost to mount them is prohibitive where Cost computing timememory 2255 Modern Cryptography A Computational Science Security ofa quotpracticalquot system must rely not on the impossibility but on the computational dif culty of breaking the system Cryptography is now notjust mathematics it needs to draw on computer science 0 Computational complexity theory CSE 105200 0 Algorithm design CSE 101202 2355 Classical Approach Iterated design Scheme 11 nu C qu 2455 Classical Approach Iterated design Scheme 11 f bug nu C qu 2455 Classical Approach Iterated design Scheme 11 gt bug 1 Scheme 12 nu c qo 2455 Classical Approach Iterated design Scheme 11 gt bug 1 Scheme 12 a bug nu c qo 2455 Classical Approach Iterated design Scheme 11 a bug 1 Scheme 12 a bug Scheme 1n Classical Approach Iterated design Scheme 11 a bug 1 Scheme 12 a bug Scheme 1n a deploy Classical Approach Iterated design Scheme 11 a bug 1 Scheme 12 a bug Scheme 1n a deploy H bug Good cryptography oi security goals 0 Understanding the goals Formal adversarial models and definitions achieves its goal 0 Beyond iterated design Proof by reduction that a construction Defining security A great deal of design tries to produces schemes without first asking What exactly is the security goalquot This leads to schemes that are complex unclear and wrong Defining security Being able to precisely state what is the security goal of a design is challenging but important We will spend a lot of time developing and justifying strong precise notions of security Thinking in terms of these precise goals and understanding the need for them may be the most important thing you get from this course 2755 Defining Security What does it mean for an encryption scheme to provide privacy nu ego 2355 Defining Security What does it mean for an encryption scheme to provide privacy Does it mean that given C KeM adversary cannot 0 recover M 0 recover the first bit of M 0 recover the XOR of the First and the ast bits of M Defining Security What does it mean for an encryption scheme to provide privacy Does it mean that given C EKSM adversary cannot 0 recover M 0 recover the first bit of M 0 recover the XOR of the first and the last bits of M C We will provide a formal definition for privacy justify it and show it implies the above and more 2355 The factoring problem Input Composite ihteger N Desired output prim e factors of N Example Input 85 Output The factoring problem Input Composite ihteger N Desired output prim e factors of N Example Input 85 Output 17 5 The factoring problem Input Composite integer N Desired output prime factors of N Example Input 85 Output 17 5 Can we write a factoring program The factoring problem Input Composite integer N Desired output prime factors of N Example Input 85 Output 175 Can we write a factoring program Easy Alg FactorN N a product of 2 primes For23imi do If N mod 139 0 then return 139 2955 The factoring problem Input Composite integer N Desired output prime factors of N Example Input 85 Output 175 Can we write a factoring program Easy Alg FactorN N a product of 2 primes For23imi do If N mod 139 0 then return i QM But this is very slow Prohibitive if N is large eg 400 digits 2955 Can we factor fast 0 Gauss couldn t figure out how 0 Nor does anyone know now Nobody today knows how to factor a 400 digit number in a practical amount of time 3056 Provable Security Provide 0 A scheme 0 A proof of security The proof establishes something like The only way to break the scheme is to factor a large number or put another way If an adversary breaks the scheme it must have found a fast factoring algorithm 3155 Provable Security Bug in scheme implies o attacker has found a way to factor fast 0 attacker is smarter than Gauss o and smarter than all living mathematicians Atomic Primitives or Problems Examples 0 Factoring Given large N pq find p q 6 Block cipher primitives DES AES 0 Hash functions MDS SHAl Atomic Primitives or Problems Examples 0 Factoring Given large N pq find p7 q 0 Block cipher primitives DES AES 0 Hash functions MD5 SHAl Features 0 Fewrsuch primitives 0 Bugs rare 0 Design an art confidence by history Atomic Primitives or Problems Examples 0 Factoring Given large N pq find p7 q 0 Block cipher primitives DES AES 0 Hash functions MD5SHA1 Features 0 Few such primitives 0 Bugs rare 0 Design an art confidence by history Drawback Don39t directly solve any security problem 3355 Higher Level Primitives Goal Solve security problem of direct interest Examples encryption authentication digital signatures key distribution v1qu 3455

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.