An Intensive Introduction to Cryptography: Lecture Notes

✍ Scribed by Boaz Barak

• Year: 2021
• Tongue: English
• Leaves: 404
• Category: Library

✦ Table of Contents

Contents
Contents (detailed)
Foreword and Syllabus
Syllabus
Prerequisites
Why is cryptography hard?
I Preliminaries
Mathematical Background
A quick overview of mathematical prerequisites
Mathematical Proofs
Example: The existence of infinitely many primes.
Probability and Sample spaces
Random variables
Distributions over strings
More general sample spaces.
Correlations and independence
Independent random variables
Collections of independent random variables.
Concentration and tail bounds
Chebyshev's Inequality
The Chernoff bound
Exercises
Exercises
Introduction
Some history
Defining encryptions
Defining security of encryption
Generating randomness in actual cryptographic systems
Defining the secrecy requirement.
Perfect Secrecy
Achieving perfect secrecy
Necessity of long keys
Amplifying success probability
Bibliographical notes
II Private key cryptography
Computational Security
Proof by reduction
The asymptotic approach
Counting number of operations.
Our first conjecture
Why care about the cipher conjecture?
Prelude: Computational Indistinguishability
The Length Extension Theorem or Stream Ciphers
Appendix: The computational model
Pseudorandomness
Unpredictability: an alternative approach for proving the length extension theorem
Stream ciphers
What do pseudorandom generators actually look like?
Attempt 0: The counter generator
Attempt 1: The linear checksum / linear feedback shift register (LFSR)
From insecurity to security
Attempt 2: Linear Congruential Generators with dropped bits
Successful examples
Case Study 1: Subset Sum Generator
Case Study 2: RC4
Case Study 3: Blum, Blum and Shub
Non-constructive existence of pseudorandom generators
Pseudorandom functions
One time passwords (e.g. Google Authenticator, RSA ID, etc.)
How do pseudorandom functions help in the login problem?
Modifying input and output lengths of PRFs
Message Authentication Codes
MACs from PRFs
Arbitrary input length extension for MACs and PRFs
Aside: natural proofs
Pseudorandom functions from pseudorandom generators and CPA security
Securely encrypting many messages - chosen plaintext security
Pseudorandom permutations / block ciphers
Encryption modes
Optional, Aside: Broadcast Encryption
Reading comprehension exercises
Chosen Ciphertext Security
Short recap
Going beyond CPA
Example: The Wired Equivalence Privacy (WEP)
Chosen ciphertext security
Constructing CCA secure encryption
(Simplified) GCM encryption
Padding, chopping, and their pitfalls: the buffer overflow'' of cryptography Chosen ciphertext attack as implementing metaphors Reading comprehension exercises Hash Functions, Random Oracles, and Bitcoin TheBitcoin'' Problem
The Currency Problem
Bitcoin Architecture
The Bitcoin Ledger
From Proof of Work to Consensus on Ledger
Collision Resistance Hash Functions and Creating Short Unique'' Identifiers Practical Constructions of Cryptographic Hash Functions Practical Random-ish Functions Some History The NSA and Hash Functions Cryptographic vs Non-Cryptographic Hash Functions Reading comprehension exercises Key derivation, protecting passwords, slow hashes, Merkle trees Keys from passwords Merkle trees and verifying storage. Proofs of Retrievability Entropy extraction Forward and backward secrecy III Public key cryptography Public key cryptography Private key crypto recap Public Key Encryptions: Definition The obfuscation paradigm Some concrete candidates: Diffie-Hellman Encryption (aka El-Gamal) Sampling random primes A little bit of group theory. Digital Signatures The Digital Signature Algorithm (DSA) Putting everything together - security in practice. Appendix: An alternative proof of the density of primes Additional Group Theory Exercises and Proofs Solved exercises: Concrete candidates for public key crypto Some number theory. Primaliy testing Fields Chinese remainder theorem The RSA and Rabin functions Abstraction: trapdoor permutations Public key encryption from trapdoor permutations Digital signatures from trapdoor permutations Hardcore bits and security without random oracles Extending to more than one hardcore bit Lattice based cryptography Quick linear algebra recap A world without Gaussian elimination Security in the real world. Search to decision An LWE based encryption scheme But what are lattices? Ring based lattices Establishing secure connections over insecure channels Cryptography's obsession with adjectives. Basic Key Exchange protocol Authenticated key exchange Bleichenbacher's attack on RSA PKCS V1.5 and SSL V3.0 Chosen ciphertext attack security for public key cryptography CCA secure public key encryption in the Random Oracle Model Defining secure authenticated key exchange The compiler approach for authenticated key exchange Password authenticated key exchange. Client to client key exchange for secure text messaging - ZRTP, OTR, TextSecure Heartbleed and logjam attacks IV Advanced topics Zero knowledge proofs Applications for zero knowledge proofs. Nuclear disarmament Voting More applications Defining and constructing zero knowledge proofs Defining zero knowledge Zero knowledge proof for Hamiltonicity. Why is this interesting? Parallel repetition and turning zero knowledge proofs to signatures.Bonus features'' of zero knowledge
Fully homomorphic encryption: Introduction and bootstrapping
Defining fully homomorphic encryption
Another application: fully homomorphic encryption for verifying computation
Example: An XOR homomorphic encryption
Abstraction: A trapdoor pseudorandom generator.
From linear homomorphism to full homomorphism
Bootstrapping: Fully Homomorphic escape velocity'' Radioactive legos analogy Proving the bootstrapping theorem Fully homomorphic encryption: Construction Prelude: from vectors to matrices Real world partially homomorphic encryption Noise management via encoding Putting it all together Analysis of our scheme Correctness CPA Security Homomorphism Shallow decryption circuit Advanced topics: Fully homomorphic encryption for approximate computation over the real numbers: CKKS Bandwidth efficient fully homomorphic encryption GH Using fully homomorphic encryption to achieve private information retrieval. Multiparty secure computation I: Definition and Honest-But-Curious to Malicious complier Ideal vs. Real Model Security. Formally defining secure multiparty computation First attempt: a slightlytoo ideal'' definition
Allowing for aborts
Some comments:
Example: Second price auction using bitcoin
Another example: distributed and threshold cryptography
Proving the fundamental theorem:
Malicious to honest but curious reduction
Handling probabilistic strategies:
Multiparty secure computation II: Construction using Fully Homomorphic Encryption
Constructing 2 party honest but curious computation from fully homomorphic encryption
Achieving circuit privacy in a fully homomorphic encryption
Bottom line: A two party secure computation protocol
Beyond two parties
Quantum computing and cryptography I
The double slit experiment
Quantum amplitudes
Quantum computing and computation - an executive summary.
Quantum 101
Physically realizing quantum computation
Bra-ket notation
Bell's Inequality
Analysis of Bell's Inequality
Grover's Algorithm
Quantum computing and cryptography II
From order finding to factoring and discrete log
Finding periods of a function: Simon's Algorithm
From Simon to Shor
The Fourier transform over Zm
Fast Fourier Transform.
Quantum Fourier Transform over Zm
Shor's Order-Finding Algorithm.
Analysis: the case that r|m
The general case
Rational approximation of real numbers
Quantum cryptography
Software Obfuscation
Witness encryption
Deniable encryption
Functional encryption
The software patch problem
Software obfuscation
Applications of obfuscation
Impossibility of obfuscation
Proof of impossibility of VBB obfuscation
Indistinguishability obfuscation
More obfuscation, exotic encryptions
Slower, weaker, less securer
How to get IBE from pairing based assumptions.
Beyond pairing based cryptography
Anonymous communication
Steganography
Anonymous routing
Tor
Telex
Riposte
V Conclusions
Ethical, moral, and policy dimensions to cryptography
Reading prior to lecture:
Case studies.
The Snowden revelations
FBI vs Apple case
Juniper backdoor case and the OPM break-in
Course recap
Some things we did not cover
What I hope you learned