lnotes_book.pdf下载

Part I: Introduction 1. How do we define security for encryption? Arguably the most important step in breaking out of the “build-break-tweak” cycle that Poe’s quote described has been the idea that we can have a mathematically precise definition of security, rather than relying on fuzzy notions, that allow us only to determine with certainty that a system is broken but never have a chance of proving that a system is secure . 2. Perfect security and its limitations: Showing the possibility (and the limitations) of encryptions that are perfectly secure regardless of the attacker’s computational resources. 3. Computational security: Bypassing the above limitations by restricting to computationally efficient attackers. Proofs of19 security by reductions. Part II: Private Key Cryptography • 1. Pseudorandom generators: The basic building block of cryptography, which also provided a new twist on the age-old philosophical and scientific question of the nature of randomness. 2. Pseudorandom functions, permutations, block ciphers: Block ciphers are the working horse of crypto. 3. Authentication and active attacks: Authentication turns out to be as crucial, if not more, to security than secrecy and often a precondition to the latter. We’ll talk about notions such as Message Authentication Codes and Chosen-Ciphertext-Attack secure encryption, as well as real-world examples why these notions are necessary. 4. Hash functions and the “Random Oracle Model”: Hash functions are used all over in crypto, including for verifying integrity, entropy distillation, and many other cases. 5. Building pseudorandom generators from one-way permutations (optional): Justifying our “axiom” of pseudo-random generators by deriving it from a weaker assumption. • Part III: Pubic key encryption 1. Public key cryptography and the obfuscation paradigm: How did Diffie, Hellman, Merkle, Ellis even dare to imagine the possiblity of public key encryption? 2. Constructing public key encryption: Factoring, discrete log, and lattice based systems: We’ll discuss several variants for constructing public key systems, including those that are widely deployed such as RSA, Diffie-Hellman, and the ellyptic curve variants, as well as some variants of lattice based cryptosystems that have the advantage of not being broken by quantum computers, as well as being more versatile. The former is the reason why the NSA has advised people to transition to lattice-based cryptosystems in the not too far future. 3. Signature schemes: These are the public key versions of authentication though interestingly are easier to construct in some sense than the latter. 4. Active attacks for encryption: Chosen ciphertext attacks for public key encryption.20 Part IV: Advanced notions • 1. Fully homomorphic encryption: Computing on encrypted data. 2. Multiparty secure computation: An amazing construction that enables applications such as playing poker over the net without trusting the server, privacy preserving data mining, electronic auctions without a trusted auctioneer, electronic elections without a trusted central authority. 3. Zero knowledge proofs: Prove a statement without revealing the reason to why its true. 4. Quantum computing and cryptography: Shor’s algorithm to break RSA and friends. Quantum key distribution. On “quantum resistant” cryptography. 5. Indistinguishability obfuscation: Construction of indistinguishability obfuscators, the potential “master tool” for crypto. 6. Practical protocols: Techniques for constructing practical protocols for particular tasks as opposed to general (and often inefficient) feasibility proofs. 7. Cryptocurrencies: Hash chains and Merkle trees, proofs of work, achieving consensus on a ledger via “majority of cycles”, smart contracts, achieving anonymity via zero knowledge proofs.