"I love An intensive introduction to cryptography: index"

2022-05-14 12:43:12

An intensive introduction to cryptographyp Foreword and Syllabusp.1 Syllabusp.1.1 Prerequisitesp.2 Why is cryptography hard?0 Mathematical Background0.1 A quick overview of mathematical prerequisites0.2 Mathematical Proofs0.2.1 Example: The existence of infinitely many primes.0.3 Probability and Sample spaces0.3.1 Random variables0.3.2 Distributions over strings0.3.3 More general sample spaces.0.4 Correlations and independence0.4.1 Independent random variables0.4.2 Collections of independent random variables.0.5 Concentration and tail bounds0.5.1 Chebyshev’s Inequality0.5.2 The Chernoff bound0.6 Exercises0.7 Exercises1 Introduction1.1 Some history1.2 Defining encryptions1.3 Defining security of encryption1.3.1 Generating randomness in actual cryptographic systems1.4 Defining the secrecy requirement.1.5 Perfect Secrecy1.5.1 Achieving perfect secrecy1.6 Necessity of long keys1.6.1 Amplifying success probability1.7 Bibliographical notes2 Computational Security2.0.1 Proof by reduction2.1 The asymptotic approach2.1.1 Counting number of operations.2.2 Our first conjecture2.3 Why care about the cipher conjecture?2.4 Prelude: Computational Indistinguishability2.5 The Length Extension Theorem or Stream Ciphers2.5.1 Appendix: The computational model3 Pseudorandomness3.0.1 Unpredictability: an alternative approach for proving the length extension theorem3.1 Stream ciphers3.2 What do pseudorandom generators actually look like?3.2.1 Attempt 0: The counter generator3.2.2 Attempt 1: The linear checksum / linear feedback shift register (LFSR)3.2.3 From insecurity to security3.2.4 Attempt 2: Linear Congruential Generators with dropped bits3.3 Successful examples3.3.1 Case Study 1: Subset Sum Generator3.3.2 Case Study 2: RC43.3.3 Case Study 3: Blum, Blum and Shub3.4 Non-constructive existence of pseudorandom generators4 Pseudorandom functions4.1 One time passwords (e.g. Google Authenticator, RSA ID, etc.)4.1.1 How do pseudorandom functions help in the login problem?4.1.2 Modifying input and output lengths of PRFs4.2 Message Authentication Codes4.3 MACs from PRFs4.4 Arbitrary input length extension for MACs and PRFs4.5 Aside: natural proofs5 Pseudorandom functions from pseudorandom generators and CPA security5.1 Securely encrypting many messages - chosen plaintext security5.2 Pseudorandom permutations / block ciphers5.3 Encryption modes5.4 Optional, Aside: Broadcast Encryption5.5 Reading comprehension exercises6 Chosen Ciphertext Security6.1 Short recap6.2 Going beyond CPA6.2.1 Example: The Wired Equivalence Privacy (WEP)6.2.2 Chosen ciphertext security6.3 Constructing CCA secure encryption6.4 (Simplified) GCM encryption6.5 Padding, chopping, and their pitfalls: the "buffer overflow" of cryptography6.6 Chosen ciphertext attack as implementing metaphors6.7 Reading comprehension exercises7 Hash Functions, Random Oracles, and Bitcoin7.1 The "Bitcoin" Problem7.1.1 The Currency Problem7.1.2 Bitcoin Architecture7.2 The Bitcoin Ledger7.2.1 From Proof of Work to Consensus on Ledger7.3 Collision Resistance Hash Functions and Creating Short "Unique" Identifiers7.4 Practical Constructions of Cryptographic Hash Functions7.4.1 Practical Random-ish Functions7.4.2 Some History7.4.3 The NSA and Hash Functions7.4.4 Cryptographic vs Non-Cryptographic Hash Functions7.5 Reading comprehension exercises8 Key derivation, protecting passwords, slow hashes, Merkle trees8.1 Keys from passwords8.2 Merkle trees and verifying storage.8.3 Proofs of Retrievability8.4 Entropy extraction8.4.1 Forward and backward secrecy9 Public key cryptography9.1 Private key crypto recap9.2 Public Key Encryptions: Definition9.2.1 The obfuscation paradigm9.3 Some concrete candidates:9.3.1 Diffie-Hellman Encryption (aka El-Gamal)9.3.2 Sampling random primes9.3.3 A little bit of group theory.9.3.4 Digital Signatures9.3.5 The Digital Signature Algorithm (DSA)9.4 Putting everything together - security in practice.9.5 Appendix: An alternative proof of the density of primes9.6 Additional Group Theory Exercises and Proofs9.6.1 Solved exercises:10 Concrete candidates for public key crypto10.1 Some number theory.10.1.1 Primaliy testing10.1.2 Fields10.1.3 Chinese remainder theorem10.1.4 The RSA and Rabin functions10.1.5 Abstraction: trapdoor permutations10.1.6 Public key encryption from trapdoor permutations10.1.7 Digital signatures from trapdoor permutations10.2 Hardcore bits and security without random oracles10.2.1 Extending to more than one hardcore bit11 Lattice based cryptography11.0.1 Quick linear algebra recap11.1 A world without Gaussian elimination11.2 Security in the real world.11.3 Search to decision11.4 An LWE based encryption scheme11.5 But what are lattices?11.6 Ring based lattices12 Establishing secure connections over insecure channels12.1 Cryptography’s obsession with adjectives.12.2 Basic Key Exchange protocol12.3 Authenticated key exchange12.3.1 Bleichenbacher’s attack on RSA PKCS V1.5 and SSL V3.012.4 Chosen ciphertext attack security for public key cryptography12.5 CCA secure public key encryption in the Random Oracle Model12.5.1 Defining secure authenticated key exchange12.5.2 The compiler approach for authenticated key exchange12.6 Password authenticated key exchange.12.7 Client to client key exchange for secure text messaging - ZRTP, OTR, TextSecure12.8 Heartbleed and logjam attacks13 Zero knowledge proofs13.1 Applications for zero knowledge proofs.13.1.1 Nuclear disarmament13.1.2 Voting13.1.3 More applications13.2 Defining and constructing zero knowledge proofs13.3 Defining zero knowledge13.4 Zero knowledge proof for Hamiltonicity.13.4.1 Why is this interesting?13.5 Parallel repetition and turning zero knowledge proofs to signatures.13.5.1 "Bonus features" of zero knowledge14 Fully homomorphic encryption: Introduction and bootstrapping14.1 Defining fully homomorphic encryption14.1.1 Another application: fully homomorphic encryption for verifying computation14.2 Example: An XOR homomorphic encryption14.2.1 Abstraction: A trapdoor pseudorandom generator.14.3 From linear homomorphism to full homomorphism14.4 Bootstrapping: Fully Homomorphic "escape velocity"14.4.1 Radioactive legos analogy14.4.2 Proving the bootstrapping theorem15 Fully homomorphic encryption: Construction15.1 Prelude: from vectors to matrices15.2 Real world partially homomorphic encryption15.3 Noise management via encoding15.4 Putting it all together15.5 Analysis of our scheme15.5.1 Correctness15.5.2 CPA Security15.5.3 Homomorphism15.5.4 Shallow decryption circuit15.6 Advanced topics:15.6.1 Fully homomorphic encryption for approximate computation over the real numbers: CKKS15.6.2 Bandwidth efficient fully homomorphic encryption GH15.6.3 Using fully homomorphic encryption to achieve private information retrieval.16 Multiparty secure computation I: Definition and Honest-But-Curious to Malicious complier16.1 Ideal vs. Real Model Security.16.2 Formally defining secure multiparty computation16.2.1 First attempt: a slightly "too ideal" definition16.2.2 Allowing for aborts16.2.3 Some comments:16.3 Example: Second price auction using bitcoin16.3.1 Another example: distributed and threshold cryptography16.4 Proving the fundamental theorem:16.5 Malicious to honest but curious reduction16.5.1 Handling probabilistic strategies:17 Multiparty secure computation II: Construction using Fully Homomorphic Encryption17.1 Constructing 2 party honest but curious computation from fully homomorphic encryption17.2 Achieving circuit privacy in a fully homomorphic encryption17.2.1 Bottom line: A two party secure computation protocol17.3 Beyond two parties18 Quantum computing and cryptography I18.1 The double slit experiment18.2 Quantum amplitudes18.2.1 Quantum computing and computation - an executive summary.18.3 Quantum 10118.3.1 Physically realizing quantum computation18.3.2 Bra-ket notation18.4 Bell’s Inequality18.5 Analysis of Bell’s Inequality18.6 Grover’s Algorithm19 Quantum computing and cryptography II19.1 From order finding to factoring and discrete log19.2 Finding periods of a function: Simon’s Algorithm19.3 From Simon to Shor19.3.1 The Fourier transform over \Z_m19.3.1.1 Fast Fourier Transform.19.3.2 Quantum Fourier Transform over \Z_m19.4 Shor’s Order-Finding Algorithm.19.4.1 Analysis: the case that r|m19.4.1.1 The general case19.5 Rational approximation of real numbers19.5.1 Quantum cryptography20 Software Obfuscation20.1 Witness encryption20.2 Deniable encryption20.3 Functional encryption20.4 The software patch problem20.5 Software obfuscation20.6 Applications of obfuscation20.7 Impossibility of obfuscation20.7.1 Proof of impossibility of VBB obfuscation20.8 Indistinguishability obfuscation21 More obfuscation, exotic encryptions21.1 Slower, weaker, less securer21.2 How to get IBE from pairing based assumptions.21.3 Beyond pairing based cryptography22 Anonymous communication22.1 Steganography22.2 Anonymous routing22.3 Tor22.4 Telex22.5 Riposte23 Ethical, moral, and policy dimensions to cryptography23.1 Reading prior to lecture:23.2 Case studies.23.2.1 The Snowden revelations23.2.2 FBI vs Apple case23.2.3 Juniper backdoor case and the OPM break-in24 Course recap24.1 Some things we did not cover24.2 What I hope you learned index An Intensive Introduction to CryptographyBoaz BarakWork in progressThese are lecture notes for lecture notes for an introductory but fast-paced undergraduate/beginning graduate course on cryptography. I am using these notes for Harvard CS 127.You can also download all lecture notes in a single PDF file.If you have any comments, suggestions, typo fixes, etc.. I would be very grateful if you post them as an issue or pull request in the GitHub repository where I am maintaining the source files for these notes.Book chaptersChapter p: Foreword and Syllabus(PDF: best formatting ,Word: buggy)Chapter 0: Mathematical Background(PDF: best formatting ,Word: buggy)Chapter 1: Introduction(PDF: best formatting ,Word: buggy)Chapter 2: Computational Security(PDF: best formatting ,Word: buggy)Chapter 3: Pseudorandomness(PDF: best formatting ,Word: buggy)Chapter 4: Pseudorandom functions(PDF: best formatting ,Word: buggy)Chapter 5: Pseudorandom functions from pseudorandom generators and CPA security(PDF: best formatting ,Word: buggy)Chapter 6: Chosen Ciphertext Security(PDF: best formatting ,Word: buggy)Chapter 7: Hash Functions, Random Oracles, and Bitcoin(PDF: best formatting ,Word: buggy)Chapter 8: Key derivation, protecting passwords, slow hashes, Merkle trees(PDF: best formatting ,Word: buggy)Chapter 9: Public key cryptography(PDF: best formatting ,Word: buggy)Chapter 10: Concrete candidates for public key crypto(PDF: best formatting ,Word: buggy)Chapter 11: Lattice based cryptography(PDF: best formatting ,Word: buggy)Chapter 12: Establishing secure connections over insecure channels(PDF: best formatting ,Word: buggy)Chapter 13: Zero knowledge proofs(PDF: best formatting ,Word: buggy)Chapter 14: Fully homomorphic encryption: Introduction and bootstrapping(PDF: best formatting ,Word: buggy)Chapter 15: Fully homomorphic encryption: Construction(PDF: best formatting ,Word: buggy)Chapter 16: Multiparty secure computation I: Definition and Honest-But-Curious to Malicious complier(PDF: best formatting ,Word: buggy)Chapter 17: Multiparty secure computation II: Construction using Fully Homomorphic Encryption(PDF: best formatting ,Word: buggy)Chapter 18: Quantum computing and cryptography I(PDF: best formatting ,Word: buggy)Chapter 19: Quantum computing and cryptography II(PDF: best formatting ,Word: buggy)Chapter 20: Software Obfuscation(PDF: best formatting ,Word: buggy)Chapter 21: More obfuscation, exotic encryptions(PDF: best formatting ,Word: buggy)Chapter 22: Anonymous communication(PDF: best formatting ,Word: buggy)Chapter 23: Ethical, moral, and policy dimensions to cryptography(PDF: best formatting ,Word: buggy)Chapter 24: Course recap(PDF: best formatting ,Word: buggy)Compiled on 11/17/2021 22:36:41Copyright 2021, Boaz Barak.This work islicensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.Produced using pandoc and panflute with templates derived from gitbook and bookdown.