CSCI 1510
Introduction to Cryptography and Computer Security (Fall 2024)
Introduction
Welcome to Cryptography and Computer Security (CSCI 1510) at Brown!
Cryptography is about communication and computation in the presence of an adversary. In this course, we will address questions such as:
- Can a secret message be sent over an unsecured channel? How can Alice send a message to Bob such that Bob will understand it but no eavesdropper will? Can we guarantee authenticity of data?
- How can Bob be sure that the message he received is indeed from Alice? How can he convince someone else of this fact?
- Can we guarantee that it is impossible to cheat in an online game? Can Alice and Bob play cards over the Internet?
To answer these questions, we will first decide what security properties are desirable for the situation at hand. We will then formally define the objects that we wish to derive: encryption schemes, signature schemes, and hash functions. Finally, we will give suitable constructions and prove that they satisfy the definitions we have given.
Besides these foundational cryptographic notions, we will also cover more advanced topics including fully homomorphic encryption, post-quantum cryptography, zero-knowledge proofs, secure multi-party computation, and program obfuscation. We will see what security guarantees are desirable, how to properly define these security guarantees, and how to design cryptographic algorithms and protocols that satisfy them.
Lectures take place every Tuesday and Thursday from 10:30 - 11:50 AM, in CIT 477 and on Zoom.
Resources
Quick Links
- Syllabus
- EdStem
- Gradescope
- Lecture Capture Recordings
- Class Participation Template
- Homework Template (Overleaf)
- Homework Template (Static)
Textbooks
- [KL] Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell
- [BS] A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup
- [R] The Joy of Cryptography by Mike Rosulek
- [G] Foundations of Cryptography by Goldreich (Vol. 1 and Vol. 2)
- Lecture notes by Pass-Shelat, Bellare-Goldwasser, Bellare-Rogway, and Ostrovsky
Contact
Homeworks & Take-Home Exams
| Homework / Exam | Release | Due |
|---|---|---|
| Homework 0 | Sep 6 | Sep 13 |
| Homework 1 | Sep 13 | Sep 20 |
| Homework 2 | Sep 20 | Sep 27 |
| Homework 3 | Sep 27 | Oct 4 |
| Homework 4 | Oct 4 | Oct 11 |
| Homework 5 | Oct 11 | Oct 18 |
| Take-Home Midterm | Oct 18 | Oct 25 |
| Homework 6 | Oct 25 | Nov 1 |
| Homework 7 | Nov 1 | Nov 8 |
| Homework 8 | Nov 8 | Nov 15 |
| Homework 9 | Nov 15 | Nov 22 |
| Homework 10 | Dec 2 | Dec 9 |
| Take-Home Final | Dec 11 | Dec 18 |
Lectures
This schedule is tentative and subject to updates throughout the semester.
* indicates optional reading material.
| Date | Topics and Readings | Pre-Lec Notes |
Post-Lec Notes |
Rec |
|---|---|---|---|---|
| Sep 5 | Topics: Introduction and overview. Readings: Syllabus [KL 1.1] Cryptography and modern cryptography. *[KL 1.3] Historical ciphers and cryptanalysis. |
Pre01.pdf | Post01.pdf | Rec01 |
| Sep 10 | Topics: Syntax of symmetric-key encryption scheme. Kerckhoff's principle. Definitions of perfect security. One-time pad. Limitations of perfect security. Readings: [KL 1.2, R 1.1] Encryption syntax and Kerckhoff's principle. [KL 1.4.1] Formal definitions. [KL 2.1-2.3] Perfectly secure encryption. *[KL 2.4] Shannon's theorem. |
Pre02.pdf | Post02.pdf | Rec02 Zoom02 |
| Sep 12 | Topics: Computational security. Concrete vs asymptotic security. Definition of semantically secure encryption. Readings: [KL 3.1] Computational security (concrete vs asymptotic). [KL 3.2, BS 2.2.2] Semantic security. |
Pre03.pdf | Post03.pdf | Rec03 Zoom03 |
| Sep 17 | Topics: Definition of semantically secure encryption (continued). Definition of pseudorandom generators (PRGs). Semantically secure encryption scheme from PRG. Proof by reduction. Readings: [KL 3.3.1, BS 3.1.1] Definition of PRG. [KL 3.3.2-3.3.3, BS 3.2] Encryption scheme from PRG and proof. |
Pre04.pdf | Post04.pdf | Rec04 Zoom04 |
| Sep 19 | Topics: Security against chosen-plaintext attacks. Pseudorandom functions (PRFs). CPA-secure encryption scheme from PRF. Readings: [KL 3.4.2, BS 5.3] Definition of CPA security. [KL 3.5.1, BS 4.4.1] Definition of PRF. [BS 4.6] Construction of PRF from PRG (GGM tree). [KL 3.5.1, BS 5.4.1] CPA-secure encryption from PRF and proof. |
Pre05.pdf | Post05.pdf | Rec05 Zoom05 |
| Sep 24 | Topics: CPA-secure encryption scheme from PRF (continued). Hybrid argument. Message authentication codes (MACs). Readings: [KL 3.5.1, BS 5.4.1] CPA-secure encryption from PRF and proof. [KL 4.1-4.2, BS 6.1] Definition of MACs. |
Pre06.pdf | Post06.pdf | Rec06 |
| Sep 26 | Topics: Fixed-length MAC. CBC-MAC. Readings: [KL 4.3.1, BS 6.3] Fixed-length MAC. [KL 4.4] CBC-MAC. |
Pre07.pdf | Post07.pdf | Rec07 |
| Oct 1 | Topics: Security against chosen-ciphertext attacks. Definition of authenticated encryption. Generic constructions. Readings: [KL 5.1.2, BS 9.2.2] Definition of CCA security. [KL 5.2, BS 9.1] Definition of authenticated encryption. [KL 5.3.1, BS 9.4] Generic constructions of authenticated encryption. |
Pre08.pdf | Post08.pdf | Rec08 |
| Oct 3 | Topics: Proof of authenticated encryption. Collision resistant hash function (CRHF). Birthday attacks on CRHF. Readings: [KL 5.3.1, BS 9.4] Generic constructions of authenticated encryption. *[KL 5.4] Secure communication sessions. [KL 6.1.1, BS 8.1] Definition of CRHF. [KL 6.4.1, BS 8.3] Birthday attacks on CRHF. |
Pre09.pdf | Post09.pdf | Rec09 |
| Oct 8 | Topics: Merkle–Damgård transform. Hash-and-MAC. Applications of CRHF. Readings: [KL 6.2, BS 8.4] Merkle–Damgård transform. [KL 6.3.1, BS 8.2] Hash-and-MAC. [KL 6.6] Applications of CRHF. *[BS 8.7, 8.9, 8.10, 8.12] Additional applications of CRHF. |
Pre10.pdf | Post10.pdf | Rec10 |
| Oct 10 | Topics: Merkle trees (contintued). Practical constructions of block ciphers. Substitution-permutation networks. Feistel networks. Readings: [KL 6.6.2] Merkle trees. [KL 7.2.1-7.2.2] SPN and Feistel networks. |
Pre11.pdf | Post11.pdf | Rec11 |
| Oct 15 | Topics: Data encryption standard (DES). Block cipher modes of operation. Readings: [KL 7.2.3, 7.2.5] DES and AES. [KL 3.6.3, R 8.1] Block cipher modes of operation. |
Pre12.pdf | Post12.pdf | Rec12 |
| Oct 17 | Topics: Block cipher modes of operation (continued). Practical constructions of hash functions. Midterm review. Selected questions from HW 1-4. Readings: [R 5.1, 6.2] PRG from block cipher. [KL 7.3] Practical constructions of hash functions. |
Pre13.pdf | Post13.pdf | Rec13 |
| Oct 22 | Topics: One-way functions. Hard-core predicates. Theoretical constructions of symmetric-key primitives. Readings: [KL 8.1.1-8.1.2] Definition and candidates of one-way functions. [KL 8.1.3, 8.3] Hard-core predicates. [KL 8.2, 8.4] Construction of PRG from OWP. *[KL 8.5] Construction of PRF from PRG (GGM tree). *[KL 8.7] Assumptions for symmetric-key cryptography. |
Pre14.pdf | Post14.pdf | Rec14 |
| Oct 24 | Topics: Basic group theory. Factoring and RSA assumptions. Discrete-Log assumption. Readings: [KL 9.1.1-9.1.4, 9.3.1] Basic group theory. *[KL 9.2.1-9.2.2] Generating random primes. [KL 9.2.3-9.2.4, BS 10.3] Factoring and RSA assumptions. *[KL 9.2.5] Relating factoring and RSA assumptions. [KL 9.3.2, BS 10.5] Discrete-Log assumption. [KL 9.4, BS 10.6] Cryptographic applications. |
Pre15.pdf | Post15.pdf | Rec15 |
| Oct 29 | Topics: Diffie-Hellman assumptions. Key exchange and Diffie-Hellman protocol. Public-key encryption definitions. ElGamal encryption. RSA-based encryption. Public-key encryption from trapdoor permutations. Readings: [KL 9.3.2, BS 10.5] Diffie-Helmman assumptions. [KL 11.3, BS 10.4] Key exchange and Diffie-Hellman protocol. [KL 12.2, BS 11.2-11.3] Public-key encryption definitions. [KL 12.4.1, BS 11.5] ElGamal encryption. [KL 12.5.1-12.5.3] RSA-based encryption. [KL 15.1.1, BS 10.3, Pass-Shelat 2.11] Trapdoor permutations. [KL 15.1.2, BS 11.4] Public-key encryption from trapdoor permutations. |
Pre16.pdf | Post16.pdf | Rec16 |
| Oct 31 | Topics: Public-key encryption from trapdoor permutations (continued). Post-quantum PKE from learning with errors (LWE) assumption. Homomorphic property of encryption schemes. Digital signatures. Hash-and-sign paradigm. RSA-based signatures. Readings: *[KL 14.1-14.2] Quantum algorithms and their impact on cryptography. [KL 14.3] Learning with errors (LWE) assumption and Regev encryption. [KL 13.1-13.2] Definition of digital signatures. [KL 13.3] Hash-and-sign paradigm. [KL 13.4] RSA-based signatures. |
Pre17.pdf | Post17.pdf | Rec17 |
| Nov 5 | NO LECTURE (Election Day) |
|||
| Nov 7 | Topics: RSA signatures (contintued). Random oracle model. Identification schemes. Fiat-Shamir transform. Schnorr's identification/signature schemes. Readings: [KL 13.4] RSA-based signatures. [KL 6.5] Random oracle model. [KL 13.5] Signatures from DLOG. |
Pre18.pdf | Post18.pdf | Rec18 |
| Nov 12 | Topics: Schnorr's identification/signature schemes (continued). Definition of zero-knowledge proofs (ZKPs). Perfect ZKP for Diffie-Hellman tuples. Readings: [Lindell's notes Sec. 5.3, 6.1] Definition of ZKPs. [Lindell's notes Sec. 6.2] Perfect ZKP for Diffie-Hellman tuples. |
Pre19.pdf | Post19.pdf | Rec19 |
| Nov 14 | Topics: Perfect ZKP for Diffie-Hellman tuples (continued). Commitment schemes. ZKP for all NP. Readings: [Lindell's notes Sec. 7] ZKP for all NP. |
Pre20.pdf | Post20.pdf | Rec20 |
| Nov 19 | Topics: ZKP for all NP (continued). Non-interactive zero-knowledge proofs (NIZKs). Definitions of secure multi-party computation. Readings: [Lindell's note Sec. 1-2, 5] Motivation, definition, and practical use cases of MPC. [Lindell's tutorial Sec. 4.2, 6.2] Formal definitions for semi-honest and malicious MPC. |
Pre21.pdf | Post21.pdf | Rec21 |
| Nov 21 | Topics: Definitions of secure multi-party computation (continued). Private set intersection. Oblivious transfer. Readings: [Paper by Ion et al.] DDH-based PSI-sum with cardinality. [Lindell's note Sec. 3] Feasibility results of MPC. [Chou-Orlandi's paper] A simple OT protocol. |
Pre22.pdf | Post22.pdf | Rec22 |
| Nov 26 | Ask Me Anything |
|||
| Nov 28 | NO LECTURE (Thanksgiving) |
|||
| Dec 3 | Topics: Oblivious transfer (contintued). Semi-honest MPC for any function (GMW protocol). Malicious MPC (GMW compiler). Introduction to fully homomorphic encryption (FHE). Readings: [Evans-Kolesnikov-Rosulek's book Ch. 3.2] GMW protocol. [Evans-Kolesnikov-Rosulek's book Ch. 6.5.1] GMW compiler. [Halevi's tutorial Sec. 1] Introduction to FHE. |
Pre23.pdf | Post23.pdf | Rec23 |
| Dec 5 | Topics: SWHE from LWE (GSW). Bootstrapping SWHE to FHE. Program obfuscation. Readings: [Halevi's tutorial Sec. 3] GSW protocol. *[Jain-Lin-Sahai's paper] Indistinguishability obfuscation from well-founded assumptions. |
Pre24.pdf | Post24.pdf | Rec24 |
Calendar
Zoom links are included in the Google Calendar event, as well as in the Hours queue.
Staff
Peihan Miao
Professor | pmiao
Hello! I work on cryptography, theory, and security. I'm excited about bridging the gap between theory and practice in cryptography. Pronouns: she/her/hers
Colin Baker
HTA | cbaker20
My interest in cryptography stems from the need for secure methods to jointly compute on biological data. My research interests are electronic structure prediction, single-cell data integration, and protein modeling. Pronouns: he/him/his
Dagar Rehan
UTA | drehan
I'm currently a Master's student in Computer Science. I love cryptography and novels (especially horror genre)! Pronouns: he/him/his
Xinyi Shi
Grad TA | xshi40
I'm studying secure multi-party computation with Peihan. I love learning and creating interesting cryptographic protocols. Pronouns: she/her/hers