COS 533 - Advanced Cryptography (Spring 2021)

Course Information

Instructor:	Mark Zhandry ()
	Office Hours: By appointment
TAs:	Ben Kuykendall and Jiaxin Guan
Time:	TuTh 1:30pm - 2:50pm (EST)
Location:	Zoom
Grading:	Based on homeworks every ~2 weeks, scribing some lectures

Course Description

This course will cover a selection of advanced topics in cryptography. Examples of potential topics include:

• Foundations
  • Cryptography from minimal assumptions
  • Black box separations - arguing that something might be impossible
• Mathematical tools
  • Lattices
  • Elliptic curves
  • Pairings
  • Isogenies
  • Multivariate equations
• Quantum
  • Post-Quantum Cryptography - Securing cryptography from quantum attacks
  • Quantum cryptography - Using quantum computing to achieve never-before-possible applications
• Cryptanalysis techniques
  • Index calculus
  • Pollard Rho
  • Lattice cryptanalysis
• Applications
  • Fully homomorphic encryption - Computing on encrypted data
  • Zero knowledge proofs - Proving a theorem without revealing the proof
  • Traitor tracing - Finding the source of leaked keys
  • Identity-based encryption - Encryption where your public key is simply your email address
  • Private information retrieval - Retrieving a database record without revealing which record
  • Secret sharing - Only qualified sets of users can reconstruct a secret
  • Multiparty computation - Mutually distrusting users computing joint function over their private inputs
  • Obfuscation - Hiding secrets in software code.
• Other topics
  • Non-black-box techniques - Overcoming black box separations
  • Time/Space trade-offs

COS 533 is intended to complement the topics covered in COS 433, covering some of the more recent advances in cryptography and with a greater emphasis on theory.

Prerequisites: Familiarity with computability and complexity theory, such as that covered in COS 340 (Turing Machines, P vs NP, NP-completeness, etc). Basic number theory (arithmetic modulo primes, composites). COS 433 is not required, though some familiarity with crypto concepts (one-way functions, encryption, digital signatures, public key vs secret key cryptography, etc) is recommended.

Example Schedule (subject to change based on student interest)

Lecture	Topic	Scribe Notes
1 - Tu, 2/2	Course introduction, review of basic crypto concepts	[1]
2 - Th, 2/4	Cryptography from minimal assumptions	[2]
3 - Tu, 2/9	Cryptography from minimal assumptions, cont.	[3]
4 - Th, 2/11	Cryptography from minimal assumptions, cont.	[4]
5 - Tu, 2/16	Class Cancelled
6 - Th, 2/18	Algebraic tools for Cryptography	[5]
7 - Tu, 2/23	Algebraic tools for Cryptography, cont.	[6]
8 - Th, 2/25	Algebraic tools for Cryptography, cont.	[7]
9 - Tu, 3/2	Algebraic tools for Cryptography, cont.	[8]
10 - Th, 3/4	Zero Knowledge	[9]
11 - Tu, 3/9	Zero Knowledge	[10]
12 - Th, 3/11	Identity-based encryption	[11]
Tu, 3/16	No Class - Spring recess
13 - Th, 3/18	Identity-based encryption	[12]
14 - Tu, 3/23	Traitor Tracing	[13]
15 - Th, 3/25	Fully Homomorphic Encryption	[14]
16 - Tu, 3/30	Fully Homomorphic Encryption	[15]
17 - Th, 4/1	Functional Encryption	[16]
18 - Tu, 4/6	Obfuscation	[17]
19 - Th, 4/8	Obfuscation	[18]
20 - Tu, 4/13	Obfuscation	[19]
21 - Th, 4/15	Post-quantum cryptography	[20]
22 - Tu, 4/20	Post-quantum cryptography	[21]
23 - Th, 4/22	Quantum Cryptography	[22]
24 - Tu, 4/27	Quantum Cryptography

Homework Assignments

Homework 0. Due 2/3
Homework 1. Due 2/25
Homework 2. Due 3/12
Homework 3. Due 4/15
Homework 4. Due 5/5

Instructions for Homeworks: Please type up your solutions (LaTeX preferred). Submit your solutions to Canvas by the due date.

Templates for Scribe Notes

ln.tex
template.tex

Latex source files for first lecture
ln1.tex