# 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.

# 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

# Lectures

Notes
Post-Lec
Notes
Scribe
Notes
Zoom
Rec
Jan 26 Topics:
Introduction and overview.

[MOV 1.1-1.2] Cryptography goals and primitives.
Jan 31 Topics:
Computational assumptions.
Symmetric-key/public-key encryption.
RSA encryption.

*[KL 2.4] Shannon's Theorem.
*[KL 3.1] Computational security.
[MOV 3.3] RSA problem.
[KL 10.4] RSA encryption.
Feb 2 Topics:
RSA encryption (continued).
ElGamal encryption.
Diffie-Hellman key exchange.
Message integrity.

[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.
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).

[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.
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.

[BS 8.7.2, 8.10.5] HMAC and HKDF.
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.
Feb 14 Topics:
Block cipher and modes of operation (continued).
CBC-MAC.
Case study: secure shell protocol (SSH).

[R 8.1] Block cipher modes of operation.
[R 5.1, 6.2] PRG from block cipher.
[R 10.3] CBC-MAC.
Feb 16 Topics:
Case study: SSH (continued).
Certificates and public key infrastructure (PKI).

[BS 13.8] Certificates and PKI.
Feb 21 NO LECTURE (Long Weekend)
Feb 23 Topics:
Two-factor authentication.
Putting it together: secure authentication.
Case study: security of group chats.

[Paper] Security of group chats in Signal, Whatsapp, and Threema.
Feb 28 Topics:
Case study: security of group chats (continued).
Single Sign-On (SSO) authentication.
Definition of zero-knowledge proof.
Example: Diffie-Hellman tuple.

[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.
Mar 2 Topics:
Proof of knowledge.
Schnorr's identification protocol.
Sigma protocol and examples.

[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.
Mar 7 Topics:
Proving arbitrary linear equations.
Proving AND/OR statements.
Non-interactive zero-knowledge (NIZK) proof.
Fiat-Shamir heuristic.

[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.
Mar 9 Topics:
ElGamal encryption: additive homomorphism and threshold decryption.
Putting it together: anonymous online voting.
Mar 14 Topics:
Zero-knowledge proofs for all NP.
Succinct Non-Interactive Arguments (SNARGs).

[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).

*[Nitulescu's survey Sec. 7] SNARKs from QAP.
[Lindell's note Sec. 1-2, 5] Motivation, definition, and practical use cases of MPC.
Mar 21 Topics:
Feasibility results of MPC.
Yao's garbled circuits and optimizations.

[Lindell's note Sec. 3] Feasibility results of MPC.
[Yakoubov's note Sec. 1] Yao's garbled circuits and optimizations.
Mar 23 Topics:
Oblivious transfer (OT).
Putting it together: 2PC for any function.
GMW: MPC for any function.

[Paper Sec. 1] A simple OT protocol.
*[Paper] OT extension.
[Evans-Kolesnikov-Rosulek's book Ch. 3.2] GMW protocol.
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.

[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.

[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.

[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.

[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.

*[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.

[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.

*[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.