COS 433: CryptographySemantically Secure EncryptionPseudorandom GeneratorsCPA Secure EncryptionPseudorandom Functions (PRF)Security of PRF-based ConstructionsPrinceton University • COS 433 • Cryptography • Fall 2005 • Boaz BarakCOS 433: Cryptography Princeton University Fall 2005Boaz BarakLecture 1-7: Short Recap2Semantically Secure EncryptionEI don’t know anything about x I couldn’t guess before! xyEquivalent notion: IndistinguishabilityEx1yx2I can’t guess if it was x1 or x2 with prob better than halfBoth satisfied with one-time pad if we allow |key| ¸ |message|3Pseudorandom GeneratorsGI can’t tell if I’m seeing G(s) or just lots of random coins!sy$$$$$$$$$$$$$$We conjecture that they exist. (Axiom 1)If we’re right, can get encryption with |key| < |message length|4CPA Secure EncryptionEThey gave me encryption box to play with and I still don’t know anything about x I couldn’t guess before! xyIndistinguishability is still equivalentEx1yx2EE5Pseudorandom Functions (PRF)fsxyI don’t know what’s inside this box!Axiom 1 (9 PRG) ) 9 PRF ) 9 CPA-secure encryption6Security of PRF-based ConstructionsEfsEncryption scheme using PRF. Can adversary succeed? Ideal scheme using random functionE1) Prove that ideal scheme is secure. 2) Show this implies security for real scheme:Otherwise all system is one big adversary for the