Lecture Notes on Cryptography - Brown University

1 Lecture Notes on CryptographyShafi Goldwasser1 Mihir Bellare2 August 20011 MIT Laboratory of Computer Science, 545 Technology Square, Cambridge, MA 02139, USA. Web page: shafi2 Department of Computer Science and Engineering,Mail Code 0114, University of Californiaat San Diego, 9500 Gilman Drive, La Jolla, CA 92093, USA. is a set of Lecture Notes on Cryptography compiled for , a one week long course on cryptographytaught at MIT by Shafi Goldwasser and Mihir Bellare in the summers of 1996 2001.

2 The Notes wereformed by merging Notes written for Shafi Goldwasser sCryptography and Cryptanalysiscourse at MIT withnotes written for Mihir Bellare sCryptography and network securitycourse at UCSD. In addition, RosarioGennaro (as Teaching Assistant for the course in 1996) contributed Section , Section , Section ,and Appendix D to the Notes , and also compiled, from various sources, some of the problems in Appendix is of course a vast subject. The thread followed by these Notes is to develop and explain thenotion of provable security and its usage for the design of secure of the material in Chapters 2, 3 and 7 is a result of scribe Notes , originally taken by MIT graduatestudents who attended Professor Goldwasser sCryptography and Cryptanalysiscourse over the years, andlater edited by Frank D Ippolito who was a teaching assistant for the course in 1991.

3 Frank also contributedmuch of the advanced number theoretic material in the Appendix. Some of the material in Chapter 3 isfrom the chapter on Cryptography , by R. Rivest, in the Handbook of Theoretical Computer 4, 5, 6, 8 and 10, and Sections and , were written by Professor Bellare for hisCryptographyand network securitycourse at rights Goldwasser and Mihir BellareCambridge, Massachusetts, August of Contents1 Introduction to Modern Encryption: Historical Glance .. Modern Encryption: A Computational Complexity Based Theory .. A Short List of Candidate One Way Functions.

4 Security Definitions .. The Model of Adversary.. Road map to Encryption ..152 One-way and trapdoor One-Way Functions: Motivation .. One-Way Functions: Definitions .. (Strong) One Way Functions .. One-Way Functions .. One-Way Functions .. Of One Way Functions .. Functions and Collections .. In Search of Examples .. Discrete Logarithm Function .. RSA function .. Between The Factorization Problem And Inverting RSA .. Squaring Trapdoor Function Candidate by Rabin .. Squaring Permutation as Hard to Invert as Factoring.

5 Hard-core Predicate of a One Way Function .. Core Predicates for General One-Way Functions .. Security Of The Discrete Logarithm Function .. Security of RSA and SQUARING functions .. One-Way and Trapdoor Predicates .. of Sets of Trapdoor Predicates ..393 Pseudo-random bit Truly Random bit Sequences ..4134 Goldwasser and Pseudo-Random Bit or Number Sequences .. Secure Pseudo-Random Generators: Brief overview .. Definitions .. The Existence Of A Pseudo-Random Generator .. Next Bit Tests .. Examples of Pseudo-Random Generators.

6 Pseudo-Random Generator ..494 Block ciphers and modes of What is a block cipher? .. Data Encryption Standard .. brief history .. Advanced Encryption Standard .. Some Modes of operation .. codebook mode .. chaining mode .. mode .. Key recovery attacks on block ciphers .. Limitations of key-recovery based security .. Exercises and Problems ..575 Pseudo-random Function families .. Random functions and permutations .. Pseudorandom functions .. Pseudorandom permutations .. under CPA.

7 Under CCA .. between the notions .. Sequences of families of PRFs and PRPs .. Usage of PRFs and PRPs .. shared random function model .. block ciphers .. Example Attacks .. Security against key-recovery .. The birthday attack .. PRFs versus PRPs .. Constructions of PRF families .. Extending the domain size .. Some applications of PRFs .. Cryptographically Strong Hashing .. Prediction .. Learning .. Identify Friend or Foe .. Private-Key Encryption ..80 Cryptography : Lecture Historical Notes .. Exercises and Problems.

8 806 Private-key Symmetric encryption schemes .. Some encryption schemes .. Issues in security .. Information-theoretic security .. Indistinguishability under chosen-plaintext attack .. interpretation of advantage .. Example chosen-plaintext attacks .. on ECB .. , stateless schemes are insecure .. Security against plaintext recovery .. Security of CTR against chosen-plaintext attack .. of Theorem .. of Theorem .. Security of CBC against chosen-plaintext attack .. Indistinguishability under chosen-ciphertext attack.

9 Example chosen-ciphertext attacks .. Attack on CTR .. Attack on CBC .. Other methods for symmetric encryption .. Generic encryption with pseudorandom functions .. Encryption with pseudorandom bit generators .. Encryption with one-way functions .. Historical Notes .. Exercises and Problems .. 1177 Public-key Definition of Public-Key Encryption .. Simple Examples of PKC: The Trapdoor Function Model .. with the Trapdoor Function Model .. with Deterministic Encryption in General .. RSA Cryptosystem.

10 S Public key Cryptosystem .. Defining Security.. of Security: Polynomial Indistinguishability .. Definition: Semantic Security .. Probabilistic Public Key Encryption .. Single Bits: Trapdoor Predicates .. Single Bits: Hard Core Predicates.. Probabilistic Encryption .. Probabilistic Encryption .. implementation of EPE with cost equal to the cost of RSA .. 1336 Goldwasser and RSA based encryption: OAEP .. Exploring Active Adversaries .. 1368 Message Introduction .. problem .. does not provide data integrity.