COS 433: CryptographyPerfectly Secure EncryptionPseudorandom Functions (PRF)Security of PRF-based ConstructionsCPA Secure EncryptionPrinceton University • COS 433 • Cryptography • Fall 2007 • Boaz BarakCOS 433: Cryptography Princeton University Fall 2007Boaz BarakLectures 1-6: Short Recap2Perfectly Secure EncryptionEx0yx1I can’t guess if it was x0 or x1 with prob better than ½ One time pad achieves this for unbounded adversary with |key| ¸ |message|Pseudorandom GeneratorsGI can’t tell if I’m seeing G(s) or just lots of random coins!sy$$$$$$$$$$$$$$We conjecture that they exist. (PRG Axiom)If we’re right, can get encryption with |key| < |message length|3Pseudorandom Functions (PRF)fkxyI don’t know what’s inside this box!Theorem: PRG Axiom ) 9 PRF4Ideal scheme using random functionESecurity of PRF-based ConstructionsEfkEncryption scheme using PRF. Can adversary succeed? 1) Prove that ideal scheme is secure. 2) Show this implies security for real scheme:Otherwise all system is one big adversary for the PRF.5CPA Secure EncryptionEx0yx1EThey gave me encryption box to play with and I still can’t guess if it’s x0 or x1 w/ prob > ½ + ²Theorem: 9 PRF ) 9 CPA-secure encryptionConstruction: Ek(x) = choose r2R {0,1}n send (r,