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

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.