Lecture Notes on Cryptography

1 Introduction to Modern Cryptography 11 1.1 Encryption: Historical Glance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 Modern Encryption: A Computational Complexity Based Theory . . . ...

1 Introduction to Modern Cryptography 11 1.1 Encryption: Historical Glance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 Modern Encryption: A Computational Complexity Based Theory . . . . . . . . . . . . . . . . 12 1.3 A Short List of Candidate One Way Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Security Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.5 The Model of Adversary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.6 Road map to Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 One-way and trapdoor functions 17 2.1 One-Way Functions: Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 One-Way Functions: Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.1 (Strong) One Way Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2 Weak One-Way Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.3 Non-Uniform One-Way Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.4 Collections Of One Way Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.5 Trapdoor Functions and Collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 In Search of Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3.1 The Discrete Logarithm Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.2 The RSA function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3.3 Connection Between The Factorization Problem And Inverting RSA . . . . . . . . . . 30 2.3.4 The Squaring Trapdoor Function Candidate by Rabin . . . . . . . . . . . . . . . . . . 30 2.3.5 A Squaring Permutation as Hard to Invert as Factoring . . . . . . . . . . . . . . . . . 34 2.4 Hard-core Predicate of a One Way Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.4.1 Hard Core Predicates for General One-Way Functions . . . . . . . . . . . . . . . . . . 35 2.4.2 Bit Security Of The Discrete Logarithm Function . . . . . . . . . . . . . . . . . . . . . 36 2.4.3 Bit Security of RSA and SQUARING functions . . . . . . . . . . . . . . . . . . . . . . 38 2.5 One-Way and Trapdoor Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5.1 Examples of Sets of Trapdoor Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3 Pseudo-random bit generators 41 3.0.2 Generating Truly Random bit Sequences . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.0.3 Generating Pseudo-Random Bit or Number Sequences . . . . . . . . . . . . . . . . . . 42 3.0.4 Provably Secure Pseudo-Random Generators: Brief overview . . . . . . . . . . . . . . 43 3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.2 The Existence Of A Pseudo-Random Generator . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.3 Next Bit Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.4 Examples of Pseudo-Random Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4.1 Blum/Blum/Shub Pseudo-Random Generator . . . . . . . . . . . . . . . . . . . . . . . 49 4 Block ciphers and modes of operation 51 4.1 What is a block cipher? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2 Data Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.2.1 A brief history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.2.2 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.2.3 Speed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.3 Advanced Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.4 Some Modes of operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.4.1 Electronic codebook mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.4.2 Cipher-block chaining mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.4.3 Counter mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.5 Key recovery attacks on block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.6 Limitations of key-recovery based security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.7 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5 Pseudo-random functions 58 5.1 Function families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.2 Random functions and permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.3 Pseudorandom functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5.4 Pseudorandom permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.4.1 PRP under CPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.4.2 PRP under CCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.4.3 Relations between the notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.5 Sequences of families of PRFs and PRPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.6 Usage of PRFs and PRPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.6.1 The shared random function model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.6.2 Modeling block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.7 Example Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.8 Security against key-recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.9 The birthday attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.10 PRFs versus PRPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.11 Constructions of PRF families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.11.1 Extending the domain size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.12 Some applications of PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.12.1 Cryptographically Strong Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.12.2 Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.12.3 Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.12.4 Identify Friend or Foe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.12.5 Private-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80