CSCI 1515
Applied Cryptography
Introduction
Welcome to Applied Cryptography (CSCI 1515) at Brown!
This course teaches cryptography from a practical perspective and provides hands-on experience in building secure systems.
We first introduce foundational cryptographic algorithms including secret-key and public-key encryption schemes, message authentication codes, digital signatures, and hash functions, from which you will build secure communication and authentication systems.
More advanced topics that are covered include zero-knowledge proofs, secure multi-party computation, fully homomorphic encryption, post-quantum cryptography, and differential privacy. You will learn how these cryptographic techniques can be used to develop more advanced applications such as secure online anonymous voting, secure computation, and private information retrieval.
Besides the high-level design of these cryptosystems, you will also get hands-on experience implementing them using tools from the existing crypto libraries written in C++.
Lectures take place every Tuesday and Thursday from 9:00 - 10:20 AM, in CIT 368 and on Zoom.
Resources
Quick Links
Textbooks
- [MOV] Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone
- [BS] A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup
- [KL] Introduction to Cryptography by Jonathan Katz and Yehuda Lindell
- [R] The Joy of Cryptography by Mike Rosulek
Guides
Contact
Assignments
| Project | Release | Due |
|---|---|---|
| Project 0: Cipher | Jan 27 | Feb 9 |
| Project 1: Signal | Feb 8 | Feb 17 |
| Project 2: Auth | Feb 18 | Mar 7 |
| Project 3: Vote | Mar 8 | Mar 24 |
| Project 4: Yaos | Mar 25 | Apr 14 |
| Project 5: PIR | Apr 15 | Apr 25 |
| Final Project | Apr 15 | May 16 |
| Homework | Release | Due |
|---|---|---|
| HW1 (Solution) | Feb 8 | Feb 14 |
| HW2 (Solution) | Feb 18 | Feb 28 |
| HW3 (Solution) | Mar 8 | Mar 17 |
| HW4 (Solution) | Mar 25 | Apr 7 |
| HW5 (Solution) | Apr 15 | Apr 21 |
Gearups will be held on Zoom; please see the course calendar for links.
| Gearup | Date | Recording | Slides |
|---|---|---|---|
| Cipher/Setup Gearup | Jan 30 | Link | Link |
| Signal Gearup | Feb 10 | Link | Link |
| Auth Gearup | Feb 24 | Link | Link |
| Vote Gearup | Mar 10 | Link | Link |
| Yaos Gearup | Apr 3 | Link | Link |
| PIR Gearup | Apr 17 | Link | Link |
Lectures
* indicates optional reading material.
| Date | Topics and Readings | Pre-Lec Notes |
Post-Lec Notes |
Scribe Notes |
Zoom Rec |
|---|---|---|---|---|---|
| Jan 26 | Topics: Introduction and overview. Readings: [MOV 1.1-1.2] Cryptography goals and primitives. |
Pre01.pdf | Post01.pdf | Link | Rec01 |
| Jan 31 | Topics: One-time pad. Computational assumptions. Symmetric-key/public-key encryption. RSA encryption. Readings: [R 1.2] One-time pad. *[KL 2.4] Shannon's Theorem. *[KL 3.1] Computational security. [MOV 3.3] RSA problem. [KL 10.4] RSA encryption. |
Pre02.pdf | Post02.pdf | Link | Rec02 |
| Feb 2 | Topics: RSA encryption (continued). ElGamal encryption. Diffie-Hellman key exchange. Message integrity. Readings: [KL 10.4] RSA encryption. [MOV 3.7] [BS 10.5] Diffie-Hellman assumptions. [MOV 8.4] ElGamal encryption. [MOV 12.6.1] Diffie-Hellman key exchange. *[BS 16.5] Quantum attacks on factoring and discrete log. |
Pre03.pdf | Post03.pdf | Link | Rec03 |
| Feb 7 | Topics: Message authentication codes. RSA and DSA signature schemes. Authenticated encryption. Collision-resistant hash functions. Birthday attacks. Random oracle model. Secure Hash Algorithms (SHA). Readings: [KL 12.3] RSA signature. [MOV 11.5.1] DSA signature. [BS 9.1, 9.4] Authenticated encryption. [R 11.1] Collision-resistant hash functions. *[KL 13.1] Random oracle model. *[BS 8.6] SHA256. |
Pre04.pdf | Post04.pdf | Link | Rec04 |
| Feb 9 | Topics: Applications of hash functions. Putting it together: secure communication. Signal double ratchet algorithm. Pseudorandom generator (PRG). Pseudorandom function/permutation (PRF/PRP). Block cipher and modes of operation. Readings: [BS 8.7.2, 8.10.5] HMAC and HKDF. [KL 12.4] Hash-and-Sign paradigm. Signal double ratchet algorithm. [R 6.1, 6.3, 6.5] PRF/PRP and block cipher. [R 8.1] Block cipher modes of operation. [R 5.1, 6.2] PRG from block cipher. |
Pre05.pdf | Post05.pdf | Link | Rec05 |
| Feb 14 | Topics: Block cipher and modes of operation (continued). CBC-MAC. Case study: secure shell protocol (SSH). Readings: [R 8.1] Block cipher modes of operation. [R 5.1, 6.2] PRG from block cipher. [R 10.3] CBC-MAC. |
Pre06.pdf | Post06.pdf | Link | Rec06 |
| Feb 16 | Topics: Case study: SSH (continued). Certificates and public key infrastructure (PKI). Password-based authentication. Readings: [BS 13.8] Certificates and PKI. [BS 18.3-18.4] Password-based authentication. |
Pre07.pdf | Post07.pdf | Link | Rec07 |
| Feb 21 | NO LECTURE (Long Weekend) | ||||
| Feb 23 | Topics: Password-based authentication (continued). Two-factor authentication. Putting it together: secure authentication. Case study: security of group chats. Readings: [BS 18.3-18.4] Password-based authentication. [Paper] Security of group chats in Signal, Whatsapp, and Threema. |
Pre08.pdf | Post08.pdf | Link | Rec08 |
| Feb 28 | Topics: Case study: security of group chats (continued). Single Sign-On (SSO) authentication. Definition of zero-knowledge proof. Example: Diffie-Hellman tuple. Readings: [Paper] Security of group chats in Signal, Whatsapp, and Threema. *[Paper Sec. 2] Kerberos overview. [Lindell's notes Sec. 6] Definition of zero-knowledge proof; Diffie-Hellman tuple. |
Pre09.pdf | Post09.pdf | Link | Rec09 |
| Mar 2 | Topics: Proof of knowledge. Schnorr's identification protocol. Sigma protocol and examples. Readings: [BS 19.1] Schnorr's identification protocol. [BS 19.4] Definitions of sigma protocol. [BS 19.5.1-19.5.2] Two examples of sigma protocols. |
Pre10.pdf | Post10.pdf | Link | Rec10 |
| Mar 7 | Topics: Proving arbitrary linear equations. Proving AND/OR statements. Non-interactive zero-knowledge (NIZK) proof. Fiat-Shamir heuristic. Readings: [BS 19.5.3] Sigma protocol for arbitrary linear equations. [BS 19.7] Proving AND/OR statements. [BS 20.3] Fiat-Shamir heuristic. [BS 19.2] Signatures from identification protocols. |
Pre11.pdf | Post11.pdf | Link | Rec11 |
| Mar 9 | Topics: ElGamal encryption: additive homomorphism and threshold decryption. Putting it together: anonymous online voting. |
Pre12.pdf | Post12.pdf | Link | Rec12 |
| Mar 14 | Topics: Zero-knowledge proofs for all NP. Succinct Non-Interactive Arguments (SNARGs). Readings: [Lindell's notes Sec. 7] Zero-knowledge proof for all NP. [Thaler's book Sec. 7] Compiling a PCP into a succinct argument. |
Pre13.pdf | Post13.pdf | Rec13 | |
| Mar 16 | Topics: SNARGs from PCP (continued). SNARGs from linear PCP. Introduction to secure multi-party computation (MPC). Readings: *[Nitulescu's survey Sec. 7] SNARKs from QAP. [Lindell's note Sec. 1-2, 5] Motivation, definition, and practical use cases of MPC. |
Pre14.pdf | Post14.pdf | Link | Rec14 |
| Mar 21 | Topics: Feasibility results of MPC. Yao's garbled circuits and optimizations. Readings: [Lindell's note Sec. 3] Feasibility results of MPC. [Yakoubov's note Sec. 1] Yao's garbled circuits and optimizations. |
Pre15.pdf | Post15.pdf | Link | Rec15 |
| Mar 23 | Topics: Oblivious transfer (OT). Putting it together: 2PC for any function. GMW: MPC for any function. Readings: [Paper Sec. 1] A simple OT protocol. *[Paper] OT extension. [Evans-Kolesnikov-Rosulek's book Ch. 3.2] GMW protocol. |
Pre16.pdf | Post16.pdf | Link | Rec16 |
| Mar 28 | NO LECTURE (Spring Break) | ||||
| Mar 30 | NO LECTURE (Spring Break) | ||||
| Apr 4 | Topics: Malicious security: GMW compiler. Cut-and-choose for garbled circuits. Private set intersection. Readings: [Evans-Kolesnikov-Rosulek's book Ch. 6.5.1] GMW compiler. *[Paper] Malicious 2PC via cut-and-choose for garbled circuits. [Paper Sec. 3.1] DDH-based PSI-sum with cardinality. |
Pre17.pdf | Post17.pdf | Rec17 | |
| Apr 6 | Topics: DDH-based PSI-Sum (continued). Information-theoretic MPC. Introduction to fully homomorphic encryption. Somewhat homomorphic encryption over integers. Readings: [Evans-Kolesnikov-Rosulek's book Ch. 3.3] BGW protocol. [Halevi's tutorial Sec. 1] Introduction to FHE. *[Paper] A conceptually simple construction of FHE over integers. |
Pre18.pdf | Post18.pdf | Rec18 | |
| Apr 11 | Topics: SWHE over integers (continued). GSW: SWHE from LWE. Readings: [Halevi's tutorial Sec. 3] GSW protocol for SWHE. *[Paper] Security of lattice-based cryptosystems. |
Pre19.pdf | Post19.pdf | Rec19 | |
| Apr 13 | Topics: GSW: SWHE from LWE (continued). BFV: SWHE from RLWE. Putting it together: private information retrieval. Readings: [Paper Sec. 3-4] BFV protocol for SWHE. *[Paper] PIR from SWHE (BFV). *[Paper] PIR from (R)GSW. |
Pre20.pdf | Post20.pdf | Rec20 | |
| Apr 18 | Topics: Private information retrieval (continued). Bootstrapping SWHE to FHE. Practical constructions of block cipher. Readings: *[Paper] PIR from additively homomorphic (Regev) encryption. [KL 6.2.1] Substitution-permutation network (SPN). |
Pre21.pdf | Post21.pdf | Rec21 | |
| Apr 20 | Topics: Block cipher (continued). Secure hardware: secure enclaves (Intel SGX); hardware security module (HSM). Cryptography in blockchain. Readings: [KL 6.2.2-6.2.3] Feistel network and DES. *[Paper] Intel SGX explained. *[Paper] Bitcoin. |
Pre22.pdf | Post22.pdf | Rec22 | |
| Apr 25 | Guest Lecture: Karn Seth from Google. Topics: Practical deployment of MPC applications. Challenges, constraints, and lessons learned from deploying cryptography at scale: MPC and Tink. |
Slides | Rec23 | ||
| Apr 27 | Topics: Blockchain (continued). Differential privacy. Privacy in machine learning. Readings: *[Paper] Vadhan's tutorial on differential privacy. *[Paper] Deep learning with differential privacy. *[Paper] Secure aggregation for federated learning. |
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
Jack Cheng 🐣
HTA | jcheng46
hi! I'm a junior and I enjoy exploring. Pronouns: he/him/his
Nick Young 🐝
HTA | nyoung10
Hi! I'm from Vancouver and I enjoy climbing, mixology, and keyboards! Pronouns: he/him/his
Anna Wei 🍃
UTA | qwei3
CS, math, dance, creative writing, nature, poetry, music, photography!
Jiahua Chen 🐫
UTA | jchen345
heya! I'm a junior studying math+computer science.
Ocean Pak 🌊
UTA | cpak4
halo! I'm Ocean, a senior from Hong Kong studying comp sci. You'll probably find me snacking, sleeping, climbing, listening to cantopop and playing board and card games.
Sudatta Hor 😈
UTA | shor1
Hi! I'm Sudatta, a third-year concentrating in Mathematics-Computer Science and Physics. I'm interested in ML, cryptography, and quantum computing research. Outside of class, I enjoy boxing and eating ramen.