Lecture Notes on Cryptography - Computer Science

1 Lecture Notes on Cryptography Shafi Goldwasser1 Mihir Bellare2. July 2008. 1. MIT Computer Science and Artificial Intelligence Laboratory, The Stata Center, Building 32, 32 Vassar Street, Cambridge, MA 02139, USA. E-mail: ; Web page: shafi 2. Department of Computer Science and Engineering, Mail Code 0404, University of California at San Diego, 9500 Gilman Drive, La Jolla, CA 92093, USA. E-mail: ; Web page: Foreword This is a set of Lecture Notes on Cryptography compiled for , a one week long course on Cryptography taught at MIT by Shafi Goldwasser and Mihir Bellare in the summers of 1996 2002, 2004, 2005 and 2008.

2 Cryptography is of course a vast subject. The thread followed by these Notes is to develop and explain the notion of provable security and its usage for the design of secure protocols. Much of the material in Chapters 2, 3 and 7 is a result of scribe Notes , originally taken by MIT graduate students who attended Professor Goldwasser's Cryptography and Cryptanalysis course over the years, and later edited by Frank D'Ippolito who was a teaching assistant for the course in 1991. Frank also contributed much of the advanced number theoretic material in the Appendix.

3 Some of the material in Chapter 3 is from the chapter on Cryptography , by R. Rivest, in the Handbook of Theoretical Computer Science . Chapters 4, 5, 6, 8, 9 and 11, and Sections and , are from the Introduction to Modern Cryptography Notes by Bellare and Rogaway [23], and we thank Phillip Rogaway for permission to include this material. Rosario Gennaro (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 E.

4 All rights reserved. Shafi Goldwasser and Mihir Bellare Cambridge, Massachusetts, July 2008. 2. Table of Contents 1 Introduction to Modern Cryptography 11. Encryption: Historical Glance .. 11. Modern Encryption: A Computational Complexity Based Theory .. 12. A Short List of Candidate One Way Functions .. 13. Security Definitions .. 14. The Model of Adversary .. 15. Road map to Encryption .. 15. 2 One-way and trapdoor functions 16. One-Way Functions: Motivation .. 16. One-Way Functions: Definitions.

5 17. (Strong) One Way Functions .. 17. Weak One-Way Functions .. 18. Non-Uniform One-Way Functions .. 19. Collections Of One Way Functions .. 20. Trapdoor Functions and Collections .. 21. In Search of Examples .. 22. The Discrete Logarithm Function .. 23. The RSA function .. 26. Connection Between The Factorization Problem And Inverting RSA .. 28. The Squaring Trapdoor Function Candidate by Rabin .. 29. A Squaring Permutation as Hard to Invert as Factoring .. 32. Hard-core Predicate of a One Way Function.

6 33. Hard Core Predicates for General One-Way Functions .. 34. Bit Security Of The Discrete Logarithm Function .. 35. Bit Security of RSA and SQUARING functions .. 36. One-Way and Trapdoor Predicates .. 36. Examples of Sets of Trapdoor Predicates .. 37. 3 Pseudo-random bit generators 39. Generating Truly Random bit Sequences .. 39. Generating Pseudo-Random Bit or Number Sequences .. 40. 3. 4 Goldwasser and Bellare Provably Secure Pseudo-Random Generators: Brief overview .. 41. Definitions .. 41.

7 The Existence Of A Pseudo-Random Generator .. 42. Next Bit Tests .. 45. Examples of Pseudo-Random Generators .. 47. Blum/Blum/Shub Pseudo-Random Generator .. 47. 4 Block ciphers 48. What is a block cipher? .. 48. Data Encryption Standard (DES) .. 49. A brief history .. 49. Construction .. 49. Speed .. 51. Key recovery attacks on block ciphers .. 52. Iterated-DES and DESX .. 55. Double-DES .. 55. Triple-DES .. 56. DESX .. 57. Why a new cipher? .. 57. Advanced Encryption Standard (AES) .. 57. Limitations of key-recovery based security.

8 61. Problems .. 61. 5 Pseudo-random functions 63. Function families .. 63. Random functions and permutations .. 64. Random functions .. 64. Random permutations .. 66. Pseudorandom functions .. 68. Pseudorandom permutations .. 70. PRP under CPA .. 70. PRP under CCA .. 71. Relations between the notions .. 72. Modeling block ciphers .. 72. Example Attacks .. 73. Security against key recovery .. 75. The birthday attack .. 78. The PRP/PRF switching lemma .. 80. Sequences of families of PRFs and PRPs.

9 80. Some applications of PRFs .. 81. Cryptographically Strong Hashing .. 81. Prediction .. 81. Learning .. 82. Identify Friend or Foe .. 82. Private-Key Encryption .. 82. Historical Notes .. 82. Problems .. 83. Cryptography : Lecture Notes 5. 6 Private-key encryption 85. Symmetric encryption schemes .. 85. Some symmetric encryption schemes .. 86. The one-time-pad encryption scheme .. 87. Some modes of operation .. 87. Issues in privacy .. 90. Indistinguishability under chosen-plaintext attack.

10 92. Definition .. 92. Alternative interpretation .. 95. Why is this a good definition? .. 96. Example chosen-plaintext attacks .. 96. Attack on ECB .. 96. Any deterministic, stateless schemes is insecure .. 97. Attack on CBC encryption with counter IV .. 98. IND-CPA implies PR-CPA .. 99. Security of CTR modes .. 101. Proof of Theorem ?? .. 102. Proof of Theorem ?? .. 106. Security of CBC with a random IV .. 111. Indistinguishability under chosen-ciphertext attack .. 111. Example chosen-ciphertext attacks.