COS 533 - Advanced Cryptography (Fall 2017)

Course Information

Instructor:	Mark Zhandry ()
	Office Hours: By appointment
TA:	Fermi Ma ()
	Office Hours: By appointment
Time:	MW 11:00am - 12:20pm
Location:	Friend Center 009
Grading:	Based on homeworks every 2 weeks, scribing some lectures
Piazza:	https://piazza.com/class/j7jaibu4qfjrd

Course Description

This course will cover a selection of advanced topics in cryptography, including some or all of the following:

• Lattice-based cryptography
• Elliptic curve-based cryptography
• Quantum Cryptography
• Cryptanalysis techniques
• 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 the database knowing which record
• Secret sharing - Splitting a secret into pieces so that only qualified sets of users can reconstruct the secret
• Multiparty computation - Several mutually distrusting users computing joint function over their private inputs

This course is intended to be a natural follow-up to COS 433. That said, I will try to make the course as self-contained as possible, and will try to cover any cryptographic background as needed (though topics covered in COS 433 will be given only basic treatment). If you are interested in taking this course, but have not previously taken COS 433 or equivalent, please contact me.

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). Familiarity with crypto concepts (one-way functions, encryption, digital signatures, public key vs secret key cryptography, etc) is recommended, though not strictly required.

Example Schedule (subject to change based on student interest)

Lecture	Topic	Scribe Notes
1 - W, 9/13	Course introduction, review of basic crypto concepts	[1]
2 - M, 9/18	Cryptography from one-way functions	[2]
3 - W, 9/20	Cryptography from one-way functions, cont.	[3]
4 - M, 9/25	Cryptography from one-way functions, cont.	[4]
5 - W, 9/27	Multiparty Computation	[5]
6 - M, 10/2	Multiparty Computation, cont.	[6]
7 - W, 10/4	Multiparty Computation, cont.	[7]
8 - M, 10/9	Zero Knowledge Proofs	[8]
9 - W, 10/11	Zero Knowledge Proofs, cont.	[9]
10 - M, 10/16	Elliptic curve cryptography	[10]
11 - W, 10/18	Elliptic curve cryptography, cont.	[11]
12 - M, 10/23	Elliptic curve cryptography, cont.	[12]
13 - W, 10/25	Bitcoin (Guest lecture by Arvind Narayanan)
M, 10/30	No Class - Fall recess
W, 11/1
14 - M, 11/6	Elliptic curve cryptography, cont.	[14]
15 - W, 11/8	Lattice-based cryptography	[15]
16 - M, 11/13	Lattice-based cryptography, cont.	[16]
17 - W, 11/15	Lattice-based cryptography, cont.	[17]
18 - M, 11/20	Lattice-based cryptography, cont.	[18]
W, 11/22	No Class - Thanksgiving
19 - M, 11/27	Cryptanalysis	[19]
20 - W, 11/29	Cryptanalysis	[20]
21 - M, 12/4	Quantum cryptography	[21]
22 - W, 12/6	Quantum cryptography, cont.	[22]
23 - M, 12/11	Quantum cryptography, cont.	[23]
24 - W, 12/13	Quantum cryptography, cont.	[24]

Homework Assignments

Homework 0. Due September 18
Homework 1. Due October 11
Homework 2. Due October 27
Homework 3. Due December 6
Homework 4. Due January 16

Instructions for Homeworks: Please type up your solutions (LaTeX preferred). Either email your solutions to (preferred) or print them out and hand them in during class by the due date.

Templates for Scribe Notes

ln.tex
template.tex

Latex source files for first two lectures
ln1.tex
ln2.tex