This site is for a previous iteration of the course. The current site is here.

CSCI 1515

Applied Cryptography

[IMPORTANT] Room Change: Starting from Wednesday February 7th, lectures will take place in Smith-Buonanno 106!

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 Smith-Buonanno 106 (Bio Med Center 202) (Friedman Hall 208) and on Zoom.

Resources

Quick Links

Textbooks

Guides

Contact

Assignments

Project Release Due
Project 0: Cipher Jan 24 Feb 9
Project 1: Signal Feb 7 Feb 16
Project 2: Auth Feb 16 Mar 1
Project 3: Vote Mar 1 Mar 20
Project 4: Yaos Mar 20 Apr 12
Project 5: PIR Apr 12 Apr 26
Final Project Apr 12 May 10
Homework Release Due
HW1 Feb 7 Feb 14
HW2 Feb 16 Feb 23
HW3 Mar 1 Mar 8
HW4 Mar 20 Apr 3
HW5 Apr 12 Apr 19

Gearups will be held on Zoom; please see the course calendar for links.

Gearup Date Recording Slides
Cipher/Setup Gearup Jan 29 Link Link
Signal Gearup Feb 12 Link Link
Auth Gearup Feb 19 Link Link
Vote Gearup March 5 Link Link
Yaos Gearup April 4 Link Link
PIR Gearup April 16 Link Link

Lectures

* indicates optional reading material.

Date Topics and Readings Pre-Lec
Notes
Post-Lec
Notes
Scribe
Notes
Zoom
Rec
Jan 24 Topics:
Introduction and overview.

Readings:
Course Syllabus
[MOV 1.1-1.2] Cryptography goals and primitives.
Pre01.pdf Post01.pdf Link Rec01
Jan 29 Topics:
Encryption scheme basics.
One-time pad (OTP).
Computational assumptions.
Factoring assumption.

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 assumption.
*[BS 16.5] Quantum attacks on factoring.
Pre02.pdf Post02.pdf Link Rec02
Jan 31 Topics:
RSA assumption and RSA encryption.
Diffie-Hellman assumptions.
ElGamal encryption.
Diffie-Hellman key exchange.
Message integrity.
RSA signature scheme.

Readings:
*[KL 9.2] RSA assumption.
[KL 12.5.1] Plain RSA encryption.
*[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.
*[BS 16.5] Quantum attacks on discrete log.
Pre03.pdf Post03.pdf Link Rec03
Feb 5 Topics:
Chosen-message attack (CMA) security.
RSA signature scheme.
Authenticated encryption.
Cryptographic hash functions.
Birthday attacks.
Random oracle model.

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.
*[KL 6.5] Random oracle model.
Pre04.pdf Post04.pdf Link Rec04
Feb 7 Topics:
Cryptographic hash functions (continued).
Applications of hash functions.
Putting it all together: secure messaging.
Signal Diffie-Hellman ratchet.
Pseudorandom generator (PRG).
Pseudorandom function (PRF).

Readings:
*[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 Link Rec05
Feb 12 Topics:
Pseudorandom function/permutation (PRF/PRP).
Block cipher and modes of operation.
CBC-MAC.

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.
Pre06.pdf Post06.pdf Link Rec06
Feb 14 Topics:
Password-based authentication.
Two-factor authentication.
Putting it all together: secure authentication.

Readings:
[BS 18.3-18.4] Password-based authentication.
Pre07.pdf Post07.pdf Link Rec07
Feb 19 NO LECTURE (Long Weekend)
Feb 21 Topics:
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.
Pre08.pdf Post08.pdf Link Rec08
Feb 26 Topics:
Definition of zero-knowledge proofs.
Proof of knowledge.
Example: Schnorr's identification protocol.
Example: Diffie-Hellman tuple.
Sigma protocols.

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.
Pre09.pdf Post09.pdf Link Rec09
Feb 28 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 Link Rec10
Mar 4 Topics:
ElGamal threshold encryption.
ZKP for AND/OR statements.
Anonymous online voting.

Readings:
[KL 15.3.3] ElGamal threshold encryption.
[BS 19.7] ZKP for AND/OR statements.
Pre11.pdf Post11.pdf Link Rec11
Mar 6 Topics:
ZKP for OR statements (continued).
RSA blind signature scheme.
Putting it all together: anonymous online voting.
Prime-order groups.

Readings:
[BS Exercise 13.15] Blind signatures.
*[KL 9.3.3] Working in subgroups of Z_p^*.
Pre12.pdf Post12.pdf Link Rec12
Mar 11 Topics:
More examples of sigma protocols.
Commitment schemes.
Zero-knowledge proofs for all NP.
Succinct Non-Interactive Arguments (SNARGs).

Readings:
[BS 19.5.1, 19.5.3] More examples of sigma protocols.
[Lindell's notes Sec. 7] Zero-knowledge proof for all NP.
Pre13.pdf Post13.pdf Link Rec13
Mar 13 Topics:
Succinct Non-Interactive Arguments (SNARGs) from PCP.
Introduction to secure multi-party computation (MPC).

Readings:
[Thaler's book Sec. 7] Compiling a PCP into a succinct argument.
[Lindell's note Sec. 1-2, 5] Motivation, definition, and practical use cases of MPC.
Pre14.pdf Post14.pdf Link Rec14
Mar 18 Topics:
Feasibility results of MPC.
Yao's garbled circuits.
Oblivious transfer (OT).

Readings:
[Lindell's note Sec. 3] Feasibility results of MPC.
[Yakoubov's note Sec. 1.1] Yao's garbled circuits.
Pre15.pdf Post15.pdf Link Rec15
Mar 20 Topics:
Optimizations of garbled circuits.
Construction of oblivious transfer.
Putting it all together: semi-honest 2PC for any function.
Cut-and-choose for garbled circuits.

Readings:
[Yakoubov's note Sec. 1.2] Optimizations for garbled circuits.
*[Paper] Slicing-and-dicing optimization for garbled circuits.
[Paper Sec. 1] A simple OT protocol.
*[Paper] OT extension.
*[Paper] Malicious 2PC via cut-and-choose for garbled circuits.
Pre16.pdf Post16.pdf Link Rec16
Mar 25 NO LECTURE (Spring Break)
Mar 27 NO LECTURE (Spring Break)
Apr 1 Topics:
Mid-semester feedback.
Cut-and-choose for garbled circuits (continued).
GMW: MPC for any function.

Readings:
[EKR 3.2] GMW protocol.
Pre17.pdf Post17.pdf Link Rec17 Panopto
Apr 3 Topics:
GMW protocol (continued).
GMW compiler: malicious MPC for any function.
Private set intersection.

Readings:
[EKR 6.5.1] GMW compiler.
[Paper Sec. 3.1] DDH-based PSI-Cardinality.
Pre18.pdf Post18.pdf Link Rec18
Panopto
Apr 8 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.
Pre19.pdf Post19.pdf Link Rec19
Ponopto
Apr 10 Topics:
LWE assumption and post-quantum cryptography (continued).
Regev encryption.
BFV: SWHE from RLWE.
Putting it all together: private information retrieval.

Readings:
*[Paper] Security of lattice-based cryptosystems.
[KL 14.3] Regev encryption.
*[Paper Sec. 3-4] BFV protocol for SWHE.
*[Paper] PIR from SWHE (BFV).
Pre20.pdf Post20.pdf Link Rec20
Panopto
Apr 15 Topics:
Private information retrieval (continued).
Bootstrapping SWHE to FHE.
Practical constructions of block cipher.

Readings:
[KL 7.2.1-7.2.3] Practical constructions of block cipher.
Pre21.pdf Post21.pdf Link Rec21
Panopto
Apr 17 Topics:
Secure hardware: secure enclaves (Intel SGX); hardware security module (HSM).
Cryptography in blockchain.

Readings:
*[Paper] Intel SGX explained.
*[Paper] Bitcoin.
Pre22.pdf Post22.pdf Link Rec22
Panopto
Apr 22 Topics:
Differential privacy.
Elliptic curve cryptography.

Readings:
*[Paper] Vadhan's tutorial on differential privacy.
*[BS 15.1-15.3] Elliptic curve cryptography.
Pre23.pdf Post23.pdf Link Rec23
Panopto
Apr 24 Topics:
Privacy-preserving machine learning.
Federated learning.

Readings:
*[Paper] Privacy-preserving machine learning.
*[Paper] Secure aggregation for federated learning.
*[Paper] Deep learning with differential privacy.
Pre24.pdf Post24.pdf Link Rec24
Panopto

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 senior and I enjoy exploring. Pronouns: he/him/his

Colby Anderson 🤙

UTA | cander23

I'm a senior. I'm a Product Manager, CS concentrator, and lover of all athletics.

Harys Dalvi 🐊

UTA | hdalvi

Hello! I'm a junior studying computer science and physics. I enjoy cryptography, ML, thermodynamics, language learning, and long walks in nature.

Sudatta Hor 💪

UTA | shor1

I like boxing and Shaq O'Neal.

Chenxin Liu 🍧

UTA | cliu248

I am currently a second-year master's student. Feel free to reach out for any course-related queries or to share your favorite food spots! Pronouns: she/her/hers

Nishchay Parashar 👾

UTA | nparasha

Hey! I'm Nishchay, a final-year master's student from New Delhi, India. Always excited to talk about classic rock music, an absolute need for every being to love Roger Federer and the latest YouTube rabbit hole you are into! :)

Michael Youssef 🤔

UTA | myousse2

Hey! I'm a junior and I'm a fan of cryptography.

Camille Zhang 🙃

UTA | czhan152

Hi! I'm Camille, a senior concentrating in CS from NorCal. I pretty much spend most of my time dancing, so come watch my last spring show April 5th and 6th! <- this plug was mandatory as Co-Director of DAEBAK