CSE 526: Cryptography (Spring 2019)
Instructor: Huijia (Rachel) Lin, rachel(at)cs
TA: Ji Luo (luoji(at)cs), Ashrujit Ghoshal (ashrujit(at)cs)
Time and location:
- Class: Monday/Wednesday 1:30pm-2:50pm, CSE2 371
- Rachel Lin: Monday 5:00pm-6:00pm, CSE 652 or by appointment
Discussion: We are going to use Google Discussion Board.
Notes: Notes and reading material will be posted at here (UWnetid protected).
Cryptography provides important tools for ensuring the confidentiality and integrity of sensitive digital data. Core cryptographic tools, such as encryption and digital signature, are used daily behind millions of online transactions. More advanced cryptographic objects, such as zero-knowledge proofs, secure multi-party computation, and fully homomorphic encryption, have emerged recently and are finding their ways into new applications.
This course gives an introduction to the theoretical foundation of cryptography, by focusing on the design and application of selected important cryptographic objects. For each cryptographic object, we formalize its functionality and security requirements (also known as security definitions), develop schemes that achieve the desired functionality, and establish their security via mathematical proofs, based on the hardness of well-studied computational hardness assumptions (e.g., the hardness of factoring integers).
In this course, we aim to gain an overview of the cryptography landscape, the proper usage and application of important cryptographic tools, and the mathematical frameworks and methodologies that modern cryptography has developed over the past decades for formalizing elusive security goals and designing provably secure solutions.
Required background: Students are expected to be ready to understand and write mathematical definitions and proofs. Exposure to basic probability / algebra / number theory, and theory of computing is also expected.
ResourcesThere is no mandatory textbook. Notes and reading material will be posted at here. Following is a list of great resources to reference to.
- R. Pass and a. shelat. A Course in Cryptography (fun and intuitive lecture notes for an undergrad crypto class, focusing on theory)
- O. Goldreich. The Foundations of Cryptography (a thorough and formal textbook on foundations.)
- J. Katz and Y. Lindell. Introduction to Modern Cryptography (a textbook, relatively easy entry)
- D. Boneh and V. Shoup A Graduate Course in Applied Cryptography (a textbook on applied cryptography)
- D. Stinson Cryptography, Theory and Practice (a textbook on different concrete crypto systems, more math oriented.)
- M. Bellare and P. Rogaway's lecture notes. Introduction to Modern Cryptography (lecture notes for a grad class, a blend of theory and practice)
Grading:There will be four homework, and one take-home final exam. Each student is responsible for scribing the note for one class, which will be posted online. Each homework accounts for 15% of points, the final accounts for 40% of points. Your final grade will be based on the weighted total points.
The following is a rough list of topics to be covered in the class. This list will be changed and refined during the course depending on the pace of the class.
- Information theoretic security: Shannon's perfect security and one-time pad.
- Encryption schemes with perfect security is inherently impractical.
- The use of assumptions and provable security.
- Computational Hardness
- One-way functions.
- Number theory and candidate one-way functions and permutations.
- Hardness amplification: Weak OWF implies strong OWF.
- Trapdoor permutations and RSA.
- The notion of computational Indistinguishability.
- Pseudo-Random Generator (PRG) and Hard-core predicates.
- Pseudo-Random Functions and the GGM PRF construction.
- Hard-core bits from any one-way functions. Goldreich-Levin Theorem.
- PRG and derandomization of BPP.
- Modern block-cipher. Pseudo-Random Permutation and the switching lemma.
- Private-key Encryption. IND-CPA security. Construction.
- Public-key Encryption. IND-CCA security. Construction.
- Authentication and Integrity
- Digital Signature. Definition. Construction from OWF.
- Hash functions. Domain Extension. Efficient digital signature construction in Random Oracle Model.
- Message authentication code.
- Simulation, Secure Computation
- Semantic security and equivalence to IND-based security.
- Zero-knowledge. Definition. Protocols for graph 3-coloring.
- Multi-party Computation. Semi-honest and malicious security.
- Yao's garbled circuits. 2-party computation.
- Secret sharing. General multiparty computation.
- Fully Homomorphic Encryption (FHE).
- Basics of lattice-based cryptography. Construction of FHE from Learning with Errors.