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 Salomon 001 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 27 | Feb 5 |
| Project 1: Signal | Feb 5 | Feb 14 |
| Project 2: Auth | Feb 17 | Feb 28 |
| Project 3: Vote | Mar 3 | Mar 21 |
| Project 4: PIR | Mar 31 | Apr 11 |
| Project 5: Yaos | Apr 14 | Apr 28 |
| Final Project | Mar 31 | May 9 |
| Homework | Release | Due |
|---|---|---|
| HW1 (template) | Feb 5 | Feb 12 |
| HW2 (template) | Feb 17 | Feb 24 |
| HW3 (template) | Mar 3 | Mar 10 |
| HW4 (template) | Mar 31 | Apr 7 |
| HW5 (template) | Apr 14 | Apr 21 |
Gearups will be held on Zoom; please see the course calendar for links.
| Gearup | Date | Recording | Slides |
|---|---|---|---|
| Cipher/Setup Gearup | Jan 27 | Recording | Slides |
| Signal Gearup | Feb 5 | Recording | Slides |
| Auth Gearup | Feb 19 | Recording | Slides |
| Vote Gearup | Mar 7 | Recording | Slides |
| PIR Gearup | April 3 | Recording | Slides |
| Yao's Gearup | April 15 | Recording | Slides |
Lectures
* indicates optional reading material.
| Date | Topics and Readings | Pre-Lec Notes |
Post-Lec Notes |
Scribe Notes |
Rec |
|---|---|---|---|---|---|
| Jan 22 | Topics: Introduction and overview. Readings: [MOV 1.1-1.2] Cryptography goals and primitives. Course Syllabus |
Pre01.pdf | Post01.pdf | Notes | Panopto01 Zoom01 |
| Jan 27 | Topics: Encryption scheme basics. One-time pad (OTP). Computational assumptions. Basic number theory. RSA assumption and RSA 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. |
Pre02.pdf | Post02.pdf | Notes | Panopto02 Zoom02 |
| Jan 29 | Topics: RSA assumption and RSA encryption (continued). Diffie-Hellman assumptions. ElGamal encryption. Diffie-Hellman key exchange. Message integrity. RSA signature scheme. Readings: *[KL 12.5.2] Padded RSA encryption. [MOV 3.7, KL 9.3.1-9.3.2] Diffie-Hellman assumptions. *[BS 15.1-15.3] Elliptic curve groups. [MOV 8.4] ElGamal encryption. [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. |
Pre03.pdf | Post03.pdf | Notes | Panopto03 Zoom03 |
| Feb 3 | Topics: Chosen-message attack (CMA) security. RSA signature scheme (continued). Authenticated encryption. Cryptographic hash functions. Readings: [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. [KL 5.1-5.3] Authenticated encryption. [R 11.1] Collision-resistant hash functions. |
Pre04.pdf | Post04.pdf | Notes | Panopto04 Zoom04 |
| Feb 5 | Topics: Cryptographic hash functions (continued). Birthday attacks. Random oracle model. 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. |
Pre05.pdf | Post05.pdf | Notes | Panopto05 Zoom05 |
| Feb 10 | Topics: Pseudorandom function/permutation (PRF/PRP, continued). Block cipher and modes of operation. 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. |
Pre06.pdf | Post06.pdf | Notes | Panopto06 Zoom06 |
| Feb 12 | Topics: CBC-MAC. Password-based authentication. Two-factor authentication. Readings: [R 10.3] CBC-MAC. [BS 18.3-18.4] Password-based authentication. |
Pre07.pdf | Post07.pdf | Notes | Panopto07 Zoom07 |
| Feb 17 | NO LECTURE (Long Weekend) | ||||
| Feb 19 | Topics: Two-factor authentication (continued). 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. Readings: [BS 13.8] Certificates and PKI. *[Paper] Security of group chats in Signal, Whatsapp, and Threema. |
Pre08.pdf | Post08.pdf | Notes | Panopto08 Zoom08 |
| Feb 24 | Topics: Case study: Single Sign-On (SSO) authentication. Definition of zero-knowledge proofs. Example: Schnorr's identification protocol. Example: Diffie-Hellman tuple. Readings: *[Paper Sec. 2] Kerberos overview. [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. |
Pre09.pdf | Post09.pdf | Notes | Panopto09 Zoom09 |
| Feb 26 | Topics: Anonymous online voting: an overview. Example: Diffie-Hellman tuple (continued). Non-interactive zero-knowledge (NIZK) proofs. Fiat-Shamir heuristic. Homomorphism of ElGamal encryption. Readings: [BS 19.5.2] Chaum-Pedersen protocol for Diffie-Hellman tuples. [BS 20.3] Fiat-Shamir heuristic. [BS 19.2] Schnorr signature. *[BS 19.3] ECDSA signature. |
Pre10.pdf | Post10.pdf | Notes | Panopto10 Zoom10 |
| Mar 3 | Topics: ZKP for OR statements (continued). Anonymous online voting (continued). ElGamal threshold encryption. RSA blind signature scheme. Readings: [BS 19.7] ZKP for OR statements. [KL 15.3.3] ElGamal threshold encryption. [BS Exercise 13.15] Blind signatures. |
Pre11.pdf | Post11.pdf | Notes | Panopto11 Zoom11 |
| Mar 5 | Topics: RSA blind signature (continued). 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. |
Pre12.pdf | Post12.pdf | Notes | Panopto12 Zoom12 |
| Mar 10 | Topics: Zero-knowledge proofs for all NP (continued). Succinct Non-Interactive Arguments (SNARGs). SNARGs from PCP. Readings: [Thaler's book Sec. 7] Compiling a PCP into a succinct argument. |
Pre13.pdf | Post13.pdf | Notes | Panopto13 Zoom13 |
| Mar 12 | Topics: SNARGs from PCP (continued). Cryptography in blockchain. Readings: *[Paper] Bitcoin. |
Pre14.pdf | Post14.pdf | Notes | Panopto14 Zoom14 |
| Mar 17 | 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. |
Pre15.pdf | Post15.pdf | Notes | Panopto15 Zoom15 |
| Mar 19 | Topics: LWE assumption (continued). Regev encryption. BFV: SWHE from RLWE. Readings: [KL 14.3] Regev encryption. *[Paper Sec. 3-4] BFV protocol for SWHE. |
Pre16.pdf | Post16.pdf | Notes | Panopto16 Zoom16 |
| Mar 24 | NO LECTURE (Spring Break) | ||||
| Mar 26 | NO LECTURE (Spring Break) | ||||
| Mar 31 | Topics: Putting it all together: private information retrieval. Bootstrapping SWHE to FHE. Secure hardware: secure enclaves (Intel SGX). Readings: *[Paper] PIR from SWHE (BFV). *[Paper] Intel SGX explained. |
Pre17.pdf | Post17.pdf | Notes | Panopto17 Zoom17 |
| Apr 2 | Topics: Secure hardware: hardware security module (HSM). 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. |
Pre18.pdf | Post18.pdf | Notes | Panopto18 Zoom18 |
| Apr 7 | 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. |
Pre19.pdf | Post19.pdf | Notes | Panopto19 Zoom19 |
| Apr 9 | Topics: Yao's garbled circuits. Construction of oblivious transfer. Readings: [Yakoubov's note Sec. 1.1] Yao's garbled circuits. [Paper Sec. 1] A simple OT protocol. |
Pre20.pdf | Post20.pdf | Notes | Panopto20 Zoom20 |
| Apr 14 | Topics: Putting it all together: semi-honest 2PC for any function. 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. |
Pre21.pdf | Post21.pdf | Notes | Panopto21 Zoom21 |
| Apr 16 | Topics: Private set intersection. Privacy-preserving machine learning. Readings: [Paper Sec. 3.1] DDH-based PSI-Cardinality. *[Paper] Privacy-preserving machine learning. |
Pre22.pdf | Post22.pdf | Notes | Panopto22 |
| Apr 21 | Topics: Federated learning. Differential privacy. Elliptic curve cryptography. Readings: *[Paper] Secure aggregation for federated learning. *[Paper] Vadhan's tutorial on differential privacy. *[Paper] Deep learning with differential privacy. |
Pre23.pdf | Post23.pdf | Notes | Panopto23 Zoom23 |
| Apr 23 | Topics: Elliptic curve cryptography (continued). Practical constructions of block cipher. Readings: *[BS 15.1-15.3] Elliptic curve cryptography. [KL 7.2] Practical constructions of block cipher. |
Pre24.pdf | Post24.pdf | Notes | Panopto24 Zoom24 |
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
John Wilkinson
HTA | jwilkin7
I'm a senior from Dedham, MA studying CS and Archaeology. In the summers I'm a sailing instructor, and in my free time I love windsurfing!
Robert Daly
UTA | rdaly5
Hi! I'm Robert. I like to study pure math, compete in CTFs, and chase rabbits on the main green.
Ian Hajra
UTA | ihajra
Hi there! I'm a junior from Michigan studying APMA/CS. I love to play jazz piano, go hiking, climb, and spend time with friends!
Nya Haseley-Ayende
UTA | nhaseley
Hi everyone! I’m a senior from Pelham, NY studying APMA/CS! You can also find me working at the IT Center at acapella performances for The Ursa Minors. I’m excited to meet you all!
Chris Jeong
UTA | cjeong6
Hey! I'm Chris, a junior concentrating in CS and Math from Oregon. In my free time I like to lift, review movies, and play clash of clans.
Karan Kashyap
UTA | kkashyap
Hi! I'm a senior studying CS. I enjoy playing tennis, swimming in the ocean, and listening to music. I'm also a big fan of formal methods, optimization, deep learning, and cryptography.
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