Foundations of Cryptography Lecture 5 Highlights
Explore key concepts covered in Foundations of Cryptography Lecture 5, including secret-key encryption, PRGs, PRFs, the Goldreich-Goldwasser-Micali construction, identification protocols, authentication, and more. Learn about challenges like adversary impersonation and unpredictability in cryptographic functions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
MIT 6.875 Foundations of Cryptography Lecture 5
TODAY 0. Finish up secret-key encryption. 1. Theorem: If there are PRGs, then there are PRFs. The Goldreich-Goldwasser-Micali (GGM) construction. 2. More Applications of PRFs: a. Identification Protocols b. Authentication c. Applications to Learning Theory
Friend-or-Foe Identification Adversary: person-in-the-middle. Can listen to / modify the communications. Wants to impersonate Tim.
A Simple Lemma about Unpredictability Let ??:{0,1} {0,1}? be a pseudorandom function. Consider an adversary who requests and obtains ???1, , ???? for a polynomial ? = ? ? . Can she predict ??? for some ? of her choosing where ? {?1, ,??}? How well can she do it? 1 2?+ 1/poly(?), then she broke PRF Lemma: If she succeeds with probability security. This is negligible in ? if ? is large enough, i.e. ?(log?).
A Simple Lemma about Unpredictability Let ??:{0,1} {0,1}? be a pseudorandom function. Consider an adversary who requests and obtains ???1, , ???? for a polynomial ? = ? ? . Can she predict ??? for some ? of her choosing where ? {?1, ,??}? How well can she do it? Unpredictability Indistinguishability for bits (lecture 3) Indistinguishability Unpredictability (but not vice versa).
Challenge-Response Protocol Random? (??,??? ) PRF Key ? (ID number ??, PRF Key ?) Proof : Adversary collects (??,????) for poly many ?? (potentially of her choosing). She eventually has to produce ??? for a fresh random ? when she is trying to impersonate. This is hard as long as the input and output lengths of the PRF are long enough, i.e. ?(log?).
TODAY 1. Theorem: If there are PRGs, then there are PRFs. The Goldreich-Goldwasser-Micali (GGM) construction. 2. More Applications of PRFs: a. Identification Protocols b. Authentication c. Applications to Learning Theory
Secure Communication m ? ? ? ? Bob Alice Key ? Can toggle between m and m Key ? One-time pad (and encryption schemes in general) are malleable.
Secure Communication m (?,??? ? ) (?,??(?) ?) Bob Alice Key ? Can toggle between m and m Key ? One-time pad (and encryption schemes in general) are malleable.
Message Authentication Codes m ????? = ??(?) Bob Alice Key ? Key ? MACs give us integrity, but not privacy.
Message Authentication Codes m (? = ?,??? ? ,tag = ?? (?)) Bob Alice Keys ?,? Keys ?,? MACs give us integrity, but not privacy. Solution: Encrypt, then MAC (more in pset 2)
TODAY 1. Theorem: If there are PRGs, then there are PRFs. The Goldreich-Goldwasser-Micali (GGM) construction. 2. More Applications of PRFs: a. Identification Protocols b. Authentication c. Applications to Learning Theory
Negative Results in Learning Theory Theorem [Kearns and Valiant 1994]: Assuming PRFs exist, there are hypothesis classes that cannot be learned by polynomial-time algorithms.
