An Intensive Introduction to Cryptography: Lecture Notes

Contents 5 Contents (detailed) 7 Foreword and Syllabus 15 Syllabus 16 Prerequisites 18 Why is cryptography hard? 18 I Preliminaries 21 Mathematical Background 23 A quick overview of mathematical prerequisites 23 Mathematical Proofs 25 Example: The existence of infinitely many primes. 26 Probability and Sample spaces 27 Random variables 30 Distributions over strings 32 More general sample spaces. 33 Correlations and independence 33 Independent random variables 35 Collections of independent random variables. 36 Concentration and tail bounds 37 Chebyshev's Inequality 38 The Chernoff bound 39 Exercises 40 Exercises 41 Introduction 45 Some history 45 Defining encryptions 47 Defining security of encryption 49 Generating randomness in actual cryptographic systems 50 Defining the secrecy requirement. 52 Perfect Secrecy 55 Achieving perfect secrecy 58 Necessity of long keys 60 Amplifying success probability 63 Bibliographical notes 64 II Private key cryptography 67 Computational Security 69 Proof by reduction 73 The asymptotic approach 74 Counting number of operations. 76 Our first conjecture 78 Why care about the cipher conjecture? 79 Prelude: Computational Indistinguishability 79 The Length Extension Theorem or Stream Ciphers 84 Appendix: The computational model 88 Pseudorandomness 91 Unpredictability: an alternative approach for proving the length extension theorem 96 Stream ciphers 98 What do pseudorandom generators actually look like? 100 Attempt 0: The counter generator 100 Attempt 1: The linear checksum / linear feedback shift register (LFSR) 100 From insecurity to security 102 Attempt 2: Linear Congruential Generators with dropped bits 103 Successful examples 103 Case Study 1: Subset Sum Generator 104 Case Study 2: RC4 105 Case Study 3: Blum, Blum and Shub 106 Non-constructive existence of pseudorandom generators 107 Pseudorandom functions 111 One time passwords (e.g. Google Authenticator, RSA ID, etc.) 114 How do pseudorandom functions help in the login problem? 116 Modifying input and output lengths of PRFs 119 Message Authentication Codes 120 MACs from PRFs 122 Arbitrary input length extension for MACs and PRFs 123 Aside: natural proofs 123 Pseudorandom functions from pseudorandom generators and CPA security 125 Securely encrypting many messages - chosen plaintext security 130 Pseudorandom permutations / block ciphers 133 Encryption modes 137 Optional, Aside: Broadcast Encryption 139 Reading comprehension exercises 142 Chosen Ciphertext Security 145 Short recap 145 Going beyond CPA 146 Example: The Wired Equivalence Privacy (WEP) 146 Chosen ciphertext security 148 Constructing CCA secure encryption 151 (Simplified) GCM encryption 156 Padding, chopping, and their pitfalls: the ``buffer overflow'' of cryptography 157 Chosen ciphertext attack as implementing metaphors 158 Reading comprehension exercises 158 Hash Functions, Random Oracles, and Bitcoin 161 The ``Bitcoin'' Problem 161 The Currency Problem 161 Bitcoin Architecture 162 The Bitcoin Ledger 163 From Proof of Work to Consensus on Ledger 166 Collision Resistance Hash Functions and Creating Short ``Unique'' Identifiers 168 Practical Constructions of Cryptographic Hash Functions 169 Practical Random-ish Functions 171 Some History 171 The NSA and Hash Functions 172 Cryptographic vs Non-Cryptographic Hash Functions 173 Reading comprehension exercises 173 Key derivation, protecting passwords, slow hashes, Merkle trees 175 Keys from passwords 175 Merkle trees and verifying storage. 178 Proofs of Retrievability 179 Entropy extraction 179 Forward and backward secrecy 183 III Public key cryptography 185 Public key cryptography 187 Private key crypto recap 189 Public Key Encryptions: Definition 192 The obfuscation paradigm 193 Some concrete candidates: 195 Diffie-Hellman Encryption (aka El-Gamal) 195 Sampling random primes 200 A little bit of group theory. 201 Digital Signatures 203 The Digital Signature Algorithm (DSA) 204 Putting everything together - security in practice. 208 Appendix: An alternative proof of the density of primes 212 Additional Group Theory Exercises and Proofs 212 Solved exercises: 214 Concrete candidates for public key crypto 219 Some number theory. 219 Primaliy testing 220 Fields 221 Chinese remainder theorem 222 The RSA and Rabin functions 223 Abstraction: trapdoor permutations 224 Public key encryption from trapdoor permutations 225 Digital signatures from trapdoor permutations 228 Hardcore bits and security without random oracles 230 Extending to more than one hardcore bit 234 Lattice based cryptography 237 Quick linear algebra recap 239 A world without Gaussian elimination 241 Security in the real world. 243 Search to decision 245 An LWE based encryption scheme 246 But what are lattices? 251 Ring based lattices 253 Establishing secure connections over insecure channels 255 Cryptography's obsession with adjectives. 255 Basic Key Exchange protocol 257 Authenticated key exchange 258 Bleichenbacher's attack on RSA PKCS V1.5 and SSL V3.0 258 Chosen ciphertext attack security for public key cryptography 259 CCA secure public key encryption in the Random Oracle Model 261 Defining secure authenticated key exchange 264 The compiler approach for authenticated key exchange 266 Password authenticated key exchange. 267 Client to client key exchange for secure text messaging - ZRTP, OTR, TextSecure 267 Heartbleed and logjam attacks 267 IV Advanced topics 269 Zero knowledge proofs 271 Applications for zero knowledge proofs. 272 Nuclear disarmament 272 Voting 273 More applications 273 Defining and constructing zero knowledge proofs 273 Defining zero knowledge 277 Zero knowledge proof for Hamiltonicity. 281 Why is this interesting? 283 Parallel repetition and turning zero knowledge proofs to signatures. 285 ``Bonus features'' of zero knowledge 286 Fully homomorphic encryption: Introduction and bootstrapping 287 Defining fully homomorphic encryption 290 Another application: fully homomorphic encryption for verifying computation 291 Example: An XOR homomorphic encryption 292 Abstraction: A trapdoor pseudorandom generator. 294 From linear homomorphism to full homomorphism 297 Bootstrapping: Fully Homomorphic ``escape velocity'' 297 Radioactive legos analogy 298 Proving the bootstrapping theorem 299 Fully homomorphic encryption: Construction 301 Prelude: from vectors to matrices 303 Real world partially homomorphic encryption 305 Noise management via encoding 306 Putting it all together 308 Analysis of our scheme 309 Correctness 310 CPA Security 311 Homomorphism 311 Shallow decryption circuit 311 Advanced topics: 314 Fully homomorphic encryption for approximate computation over the real numbers: CKKS 314 Bandwidth efficient fully homomorphic encryption GH 315 Using fully homomorphic encryption to achieve private information retrieval. 316 Multiparty secure computation I: Definition and Honest-But-Curious to Malicious complier 319 Ideal vs. Real Model Security. 320 Formally defining secure multiparty computation 321 First attempt: a slightly ``too ideal'' definition 321 Allowing for aborts 322 Some comments: 324 Example: Second price auction using bitcoin 326 Another example: distributed and threshold cryptography 327 Proving the fundamental theorem: 328 Malicious to honest but curious reduction 329 Handling probabilistic strategies: 333 Multiparty secure computation II: Construction using Fully Homomorphic Encryption 335 Constructing 2 party honest but curious computation from fully homomorphic encryption 336 Achieving circuit privacy in a fully homomorphic encryption 339 Bottom line: A two party secure computation protocol 341 Beyond two parties 342 Quantum computing and cryptography I 345 The double slit experiment 345 Quantum amplitudes 346 Quantum computing and computation - an executive summary. 349 Quantum 101 351 Physically realizing quantum computation 354 Bra-ket notation 355 Bell's Inequality 356 Analysis of Bell's Inequality 357 Grover's Algorithm 360 Quantum computing and cryptography II 363 From order finding to factoring and discrete log 363 Finding periods of a function: Simon's Algorithm 364 From Simon to Shor 366 The Fourier transform over Zm 366 Fast Fourier Transform. 367 Quantum Fourier Transform over Zm 368 Shor's Order-Finding Algorithm. 369 Analysis: the case that r|m 370 The general case 370 Rational approximation of real numbers 371 Quantum cryptography 372 Software Obfuscation 373 Witness encryption 374 Deniable encryption 375 Functional encryption 375 The software patch problem 376 Software obfuscation 377 Applications of obfuscation 377 Impossibility of obfuscation 378 Proof of impossibility of VBB obfuscation 378 Indistinguishability obfuscation 381 More obfuscation, exotic encryptions 383 Slower, weaker, less securer 383 How to get IBE from pairing based assumptions. 384 Beyond pairing based cryptography 387 Anonymous communication 389 Steganography 389 Anonymous routing 390 Tor 390 Telex 390 Riposte 390 V Conclusions 391 Ethical, moral, and policy dimensions to cryptography 393 Reading prior to lecture: 395 Case studies. 395 The Snowden revelations 395 FBI vs Apple case 396 Juniper backdoor case and the OPM break-in 397 Course recap 399 Some things we did not cover 401 What I hope you learned 402