CS 127 / CSCI E-127: Cryptography

Boaz Barak

I will be teaching this course in the Spring of 2018. This website is for the Spring 2016 version. See www.boazbarak.org/cs127/ ) for the current version.

Instructor:Boaz Barak, office hours: Tuesdays 1pm-2:30pm (MD 329), see below for special shopping week hours.
Teaching Fellows:Tudor Giurgica-Tiron ( giurgicatiron (at) college (dot) harvard (dot) edu), Section schedule: TBD, office hours: TBD
Nathan Manohar (nmanohar (at) college (dot) harvard (dot) edu), Section schedule: TBD, office hours: TBD
Mark Yao - extension school TF (markyao (at) college (dot) harvard (dot) edu), Section schedule: TBD, office hours: TBD
Administrator:Kevin Doyle, 617-496-6257, Maxwell Dworkin 111A kdoyle (at) seas (dot) harvard (dot) edu
Grading Scheme: (tentative, see admin page for more details) Weekly problem sets:* 40%; Weekly online quizzes: 10%; Midterm: 15%; Take home final exam: 25%; Class participation: 10%
Canvas website: https://canvas.harvard.edu/courses/9393
(Used to submit all homeworks and quizzes.)
Piazza Website https://piazza.com/harvard/spring2016/cs127/home
(Discussion boards)
* Problem sets will contain bonus questions that can make up for missed points in the P-sets or quizzes or a missed problem set (as well as simply provide more challenging questions for students who enjoy them :) )

About this course

Cryptography is as old as human communication itself, but has undergone a revolution in the last few decades. It is now about much more than "secret writing" and includes seemingly paradoxical notions such as communicating securely without a shared secret, and computing on encrypted data. In this challenging but rewarding course we will start from the basics of private and public key cryptography and go all the way up to advanced notions such as fully homomorphic encryption and indistinguishability obfuscation. This is a proof-based course that will be best appreciated by mathematically mature students.

For more information about this course, please see the following document on Foreword, Syllabus and Prerequisites. The recommended textbook for this class is Introduction to Modern Cryptography (2nd ed) / Katz and Lindell though we will only be loosely following it (and teach many topics not covered by it).

For some of the mathematical background, see the notes for the "Lecture 0" on mathematical background. The exercises there will be part of the first problem set, so you can save yourself time by starting on them now.

Should I take this course? If you are interested in both the foundations of cryptography as well as some of its exciting recent applications, and are comfortable with mathematical proofs and abstract reasoning, this course might be for you. If you are a Harvard student wondering if you should take this course, send me an email and I'll be happy to set up a time to meet and talk about it in person.

During shopping week (Jan 24-30) I will have the following extended office hours if you want to talk to me: Monday (1/25) 2-3pm, Tuesday (1/26) 1pm-2:30pm, Thursday (1/28) 2pm-3pm, Friday (1/29) 2pm-3pm.

See this page for more administrative information about this course.


As mentioned above, the recommended textbook for this course is Katz and Lindell's Intrduction to Modern CRyptography (2nd ed). Another text we will refer to occasionally is Boneh and Shoup's Graduate Course on Applied Cryptography. A very comprhenesive text on the theory of cryptography is Goldreich's two volume "Foundations of Cryptography". There are several lecture notes on the web for cryptography courses; a fairly complete set of notes is Pass and Shelat's. A more applied cryptography text is Menezes et al's Handbook of Applied Cryptography. Finally, Dan Boneh has taught a MOOC on cryptography which is available on Coursera (Part I) and (Part II)

Tentative plan

(very much subject to change!)

Submit all homework and quizzes via the canvas website for the course.

Date Topic Notes Homework
pre term Syllabus, admin, mathematical background syllabus(pdf) (html)
mathematical background, homework 0 (pdf) (html)
Administrative policies
(See mathematical background handout)
Tue 1/26 Introduction, history, perfect secrecy pdf html
Handout 1 (syllabus+lec1+lec2+hw1)
Slides (powerpoint format)
Homework 1: pdf, html , md
Due Friday February 5, 5pm.
See also admin page for policies on assignments, collaborations, etc..
Thu 1/28 Computational secrecy pdf html
Tue 2/2 Pseudorandomness pdf html Homework 2: pdf, html , md
See Canvas for deadline
Thu 2/4 Pseudorandom functions, authentication pdf html
Tue 2/9 Pseudorandom functions from generators, multiple message security pdf html
Thu 2/11 The login problem and chosen ciphertext attacks pdf html Homework 3: pdf, html , md
See Canvas for deadline
Tue 2/16 Hashing, random oracle model, bitcoin pdf html
Thu 2/18 Key derivation, protecting passwords, slow hashes, entropy extraction pdf html Homework 4: pdf, html , md
See Canvas for deadline
Tue 2/23 Private key crypto recap pdf html
Thu 2/25 Public key crypto intro, the obfuscation paradigm, Diffie Hellman and DSA pdf html Homework 5: pdf, html , md
See Canvas for deadline
Tue 3/1 Concrete candidates: RSA and Rabin pdf html
Thu 3/3 Lattice based crypto pdf html Homework 6: pdf, html , md
See Canvas for deadline
Tue 3/8 The handshake - CCA for public key, SSL/TLS and friends Password-Authenticated Key Exchange, ZRTP, OTR etc.. pdf html
Thu 3/10 Zero knowledge proofs pdf html Homework 7: pdf, html , md
See Canvas for deadline
Tue 3/22 Fully homomorphic encryption 1: Introduction and bootstrapping pdf html
Thu 3/24 Fully homomorphic encryption 2: Construction pdf html Homework 8: pdf, html , md
See Canvas for deadline
Tue 3/29 Secure multiparty computation 1: Definitions, examples,honest-but-curious to malicious compiler pdf html
Thu 3/31 Secure multiparty computation 2: constructions pdf html Homework 9: pdf, html , md
See Canvas for deadline
Tue 4/5 Quantum computing and cryptography I pdf html
Thu 4/7 Quantum computing and cryptography II pdf html Homework 10: pdf, html , md
See Canvas for deadline
Tue 4/12 Obfuscation pdf html
Thu 4/14 Identity based encryption, witness encryption, functional encryption pdf html Homework 11: pdf, html , md
See Canvas for deadline
Tue 4/19 Anonynmous communication: onion routing, steganography Riposte paper
Telex paper
Thu 4/21 Moral, ethical, and policy dimensions of cryptography pdf html
Tue 4/26 Course recap and preparation for exam pdf html practice questions (pdf) practice questions (html)