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 to use these cryptographic techniques 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, this course also provides hands-on experience implementing them using tools from the existing crypto libraries such as CryptoPP and Microsoft SEAL. All the projects are written in C++ as it is the most widely used language in crypto libraries.
Lectures take place every Monday and Wednesday from 3:00 - 4:20 PM, in Friedman 108 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
- [EKR] A Pragmatic Introduction to Secure Multi-Party Computation by David Evans, Vladimir Kolesnikov, and Mike Rosulek
Guides
Contact
Assignments
| Project | Release | Due |
|---|---|---|
| Project 0: Cipher | Jan 28 | Feb 3 |
| Project 1: Signal | Feb 4 | Feb 13 |
| Project 2: Auth | Feb 18 | Feb 27 |
| Project 3: Vote | Mar 4 | Mar 20 |
| Project 4: Yaos | Mar 30 | Apr 10 |
| Project 5: PIR | Apr 15 | Apr 24 |
| Final Project | Mar 30 | May 8 |
| Homework | Release | Due |
|---|---|---|
| HW 1 | Feb 4 | Feb 9 |
| HW 2 | Feb 18 | Feb 23 |
| HW 3 | Mar 4 | Mar 11 |
| HW 4 | Mar 30 | Apr 6 |
| HW 5 | Apr 15 | Apr 20 |
| Code Review | Release | Due |
|---|---|---|
| CR 1: Signal and Auth | TBD | TBD |
| CR 2: Vote or Yaos | TBD | TBD |
Gearups will be recorded and posted here when projects come out.
| Gearup | Recording | Slides |
|---|---|---|
| Cipher/Setup Gearup | ||
| Signal Gearup | ||
| Auth Gearup | ||
| Vote Gearup | ||
| PIR Gearup | ||
| Yaos Gearup |
Lectures
* indicates optional reading material.
| Date | Topics and Readings | Pre-Lec Notes |
Post-Lec Notes |
Scribe Notes |
Rec |
|---|---|---|---|---|---|
| Jan 21 | Topics: Introduction and overview. Readings: [MOV 1.1-1.2] Cryptography goals and primitives. Course Syllabus |
Pre01.pdf | |||
| Jan 26 | Topics: One-time pad (OTP). Computational assumptions. Symmetric-/ public-key encryption. RSA assumption and RSA encryption. ElGamal encryption. Readings: *[KL 1.2] Kerckhoffs' Principle. [R 1.2] One-time pad. *[KL 2.4] Shannon's Theorem. *[KL 3.1] Computational security. [MOV 3.3] RSA problem. *[KL 9.2] Factoring and RSA assumptions. [KL 12.5.1] Plain RSA encryption. *[KL 12.5.2] Padded RSA encryption. [MOV 8.4] ElGamal encryption. |
||||
| Jan 28 | Topics: Diffie-Hellman assumptions. Diffie-Hellman key exchange. Message integrity. Message authentication codes. RSA and DSA signature schemes. Readings: [MOV 3.7, KL 9.3.1-9.3.2] Diffie-Hellman assumptions. *[BS 15.1-15.3] Elliptic curve groups. [MOV 12.6.1] Diffie-Hellman key exchange. *[KL 9.3.3] Prime-order subgroups of Z_p^*. *[BS 16.5] Quantum attacks on factoring and discrete log. [KL 4.1-4.2] Definition of message authentication codes (MACs). [KL 13.1-13.2] Definition of digital signatures. [KL 13.4] RSA signature. |
||||
| Feb 2 | Topics: Authenticated encryption. Collision-resistant hash functions. Birthday attacks. Readings: [KL 5.1-5.3] Authenticated encryption. [R 11.1] Collision-resistant hash functions. |
||||
| Feb 4 | Topics: Random oracle model. Secure Hash Algorithms (SHA). Applications of hash functions. Putting it all together: secure messaging. Signal Diffie-Hellman ratchet. Pseudorandom generator (PRG). Pseudorandom function (PRF). Pseudorandom permutation (PRP). Readings: *[KL 6.5] Random oracle model. *[BS 8.6] SHA256. [BS 8.7.2, 8.10.5] HMAC and HKDF. [KL 13.3] Hash-and-Sign paradigm. Signal double ratchet algorithm. [R 6.1] Definition of PRF. |
||||
| Feb 9 | Topics: Block cipher and modes of operation. CBC-MAC. Certificates and public key infrastructure (PKI). Readings: [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. [R 10.3] CBC-MAC. |
||||
| Feb 11 | Topics: Password-based authentication. Two-factor authentication. Readings: [BS 18.3-18.4] Password-based authentication. |
||||
| Feb 16 | NO LECTURE (Long Weekend) | ||||
| Feb 18 | Topics: Putting it all together: secure authentication. Certificates and public key infrastructure (PKI). Case study: secure shell protocol (SSH). Case study: secure messaging and group chats. Case study: Single Sign-On (SSO) authentication. Readings: [BS 13.8] Certificates and PKI. *[Paper] Security of group chats in Signal, Whatsapp, and Threema. *[Paper Sec. 2] Kerberos overview. |
||||
| Feb 23 | Topics: Definition of zero-knowledge proofs. Example: Schnorr's identification protocol. Example: Diffie-Hellman tuple. Readings: [Lindell's notes Sec. 6] Definition of zero-knowledge proof. [BS 19.1.1] Honest verifier zero knowledge (HVZK). [BS 19.1] Schnorr's identification protocol. [BS 19.4] Sigma protocols. [BS 19.5.2] Chaum-Pedersen protocol for Diffie-Hellman tuples. |
||||
| Feb 25 | Topics: Non-interactive zero-knowledge (NIZK) proofs. Fiat-Shamir heuristic. Homomorphism of ElGamal encryption. ZKP for OR statements. Readings: [BS 20.3] Fiat-Shamir heuristic. [BS 19.2] Schnorr signature. *[BS 19.3] ECDSA signature. [BS 19.7] ZKP for OR statements. |
||||
| Mar 2 | Topics: ElGamal threshold encryption. RSA blind signature scheme. Readings: [KL 15.3.3] ElGamal threshold encryption. [BS Exercise 13.15] Blind signatures. |
||||
| Mar 4 | Topics: Putting it all together: anonymous online voting. More examples of sigma protocols. Zero-knowledge proofs for all NP. Readings: [BS 19.5.1, 19.5.3] More examples of sigma protocols. [Lindell's notes Sec. 7] Zero-knowledge proofs for all NP. |
||||
| Mar 9 | Topics: Succinct Non-Interactive Arguments (SNARGs). SNARGs from PCP. Readings: [Thaler's book Sec. 7] Compiling a PCP into a succinct argument. |
||||
| Mar 11 | Topics: Cryptography in blockchain. Readings: *[Paper] Bitcoin. |
||||
| Mar 16 | Topics: Introduction to secure multi-party computation (MPC). Feasibility results of MPC. Oblivious transfer (OT). Readings: [Lindell's note Sec. 1-2, 5] Motivation, definition, and practical use cases of MPC. [Lindell's note Sec. 3] Feasibility results of MPC. |
||||
| Mar 18 | Topics: GMW: MPC for any function. GMW compiler: malicious MPC for any function. Readings: [EKR 3.2] GMW protocol. [EKR 6.5.1] GMW compiler. |
||||
| Mar 23 | NO LECTURE (Spring Break) | ||||
| Mar 25 | NO LECTURE (Spring Break) | ||||
| Mar 30 | Topics: Yao's garbled circuits. Construction of oblivious transfer. Putting it all together: semi-honest 2PC for any function. Readings: [Yakoubov's note Sec. 1.1] Yao's garbled circuits. [Paper Sec. 1] A simple OT protocol. |
||||
| Apr 1 | Topics: Optimizations of garbled circuits. Cut-and-choose for garbled circuits. Readings: [Yakoubov's note Sec. 1.2] Optimizations for garbled circuits. *[Paper] Three halves optimization for garbled circuits. *[Paper] Malicious 2PC via cut-and-choose for garbled circuits. |
||||
| Apr 6 | Topics: Private set intersection. Privacy-preserving machine learning. Federated learning. Readings: [Paper Sec. 3.1] DDH-based PSI-Cardinality. *[Paper] Privacy-preserving machine learning. *[Paper] Secure aggregation for federated learning. |
||||
| Apr 8 | Topics: Elliptic curve cryptography. Practical constructions of block cipher. Secure hardware: secure enclaves (Intel SGX); hardware security module (HSM). Readings: *[BS 15.1-15.3] Elliptic curve cryptography. [KL 7.2] Practical constructions of block cipher. *[Paper] PIR from SWHE (BFV). *[Paper] Intel SGX explained. |
||||
| Apr 13 | Topics: Introduction to fully homomorphic encryption. Somewhat homomorphic encryption over integers. Learning with errors (LWE) assumption. Readings: [Halevi's tutorial Sec. 1] Introduction to FHE. *[Paper] A conceptually simple construction of FHE over integers. *[Paper] Security of lattice-based cryptosystems. |
||||
| Apr 15 | Topics: Regev encryption. BFV: SWHE from RLWE. Putting it all together: private information retrieval. Bootstrapping SWHE to FHE. Readings: [KL 14.3] Regev encryption. *[Paper Sec. 3-4] BFV protocol for SWHE. |
||||
| Apr 20 | Topics: AI watermarking. Readings: *[Paper] SoK: Watermarking for AI-Generated Content. |
||||
| Apr 22 | Topics: Differential privacy. Readings: *[Paper] Vadhan's tutorial on differential privacy. *[Paper] Deep learning with differential privacy. |
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, both theoretical and applied.
How to pronounce my name.
Pronouns: she/her/hers
Ian Hajra
HTA | ihajra
Hi there! I'm a senior from Michigan studying APMA/CS. I love to play jazz piano, go hiking, climb, and spend time with friends!
Chloe Qiao
HTA | zyqiao
Hello! I'm a junior from California studying computer science. In my free time I enjoy bouldering, DDR, and playing Terraria.
Anand Advani
UTA | aaadvani
Hi everyone! I’m Anand, a senior from Virginia studying APMA-CS. I’m also interested in AI ethics and love to spin poi and play in the snow.
Manav Chakravarthy
UTA | mchakra3
Hi folks! I'm Manav, a 5th-year Masters student in CS. During my free time, I enjoy going surfing and watching Modern Family reruns!
Eric Cho
UTA | ekcho
Hi there! I’m a senior from Georgia studying APMA-CS. In my free time, I like to watch youtube videos and play Clash of Clans!
Sophia Ma
UTA | gma10
Hi! I’m a senior from Beijing studying Computer Science and Philosophy. Outside of class, you can usually find me hopping between Rock, Orwig, and Nelson, or happily grocery shopping.