CS 795 / ISA 797: Cryptography, Fall 2016

Course Overview

Course Description

The course will provide an introduction to modern cryptography. We will cover many practical topics, such as how to correctly use block ciphers and hash functions for the most common tasks: encryption and message authentication. In addition, with what time we remains, we will also cover several recent topics in cryptography, such as the use of block chains for crypto currencies, data sanitization through differential privacy, and searching encrypted databases.

The main objectives are to convey the importance of provable security, to teach students how to use cryptographic tools in a way that is provably secure, to provide students with the ability to decide whether a protocol is secure, and to demonstrate the range of what can be achieved with provable security.

There are no formal prerequisites for this course, and I intend for everything to be self-contained. However, students should have some level of mathematical maturity. Accordingly, a course such as CS600 would be a good course to take prior to this one. Students should be comfortable proving that one computational task reduces to another (in a formal way), and they should have comfort with basic probability theory.


Course Requirements


There will be 6 homework assignments, due every other week. Students are welcome to work in groups, but every student must write their solutions independently. Homework that appear overly similar will be considered to violate the honor code. Students may re-submit up to 3 homework assignments for re-grading. The intent is to encourage students to revisit material that they did not understand; students are discouraged from re-submitting homework to save a few points. Accordingly, the following rules apply:
a) Points earned on re-submissions will be earned at 80% value: if you lost 5 points on the first submission, you can earn back at most 4.
b) Before resubmitting a homework, you must attend office hours to discuss what you didn't understand.
c) Re-submissions are due two weeks after the graded homework was originally returned to the student.
d) Anything submitted for re-grading must be accompanied by the original submission.

I encourage students to type their answers, both because they will be easier to read, and also because I believe it helps you clarify your own thinking. You can use this LaTex template file, if it is helpful to you. There are also command definitions that might be helpful to you here. (If you're using the template file, you will need to remove the comment where the preamble file is included.) This is a great LaTex reference, with a list of useful symbols on page 75.


There will be one mid-term and one final exam. Each will cover roughly half of the semester. The final will not be cumulative. Both exams are closed book, and no notes will be allowed.


Homework: 50%
Midterm: 25%
Final: 25%


Course Policies


I prefer that students do not use laptops in class. I will go slowly enough that notes can be taken by hand. If you feel you need a laptop, please discuss it with me.


Tentative Schedule

The following schedule is tentative, and is likely to change. Please go here for a schedule that is updated weekly to reflect what we actually cover, and to find reading and homework assignments.

Date Topic
Aug. 30 The goal of modern cryptography; Perfect secrecy via the one-time pad; limitations of perfect secrecy; definitions of computational security;
Sept. 6 Security reductions; Pseudorandom generators; proof of security for pseudo-OTP; Chosen plaintext attack security
Sept. 13 Pseudorandom functions; achieving CPA security; pseudorandom permutations and block ciphers
Sept. 20 Modes of operation in block ciphers; Chosen Ciphertext Attack security; message authentication
Sept. 27 Message authentication for arbitrary length messages; CBC-MAC; authenticated encryption
Oct. 4 (To be rescheduled) Hash functions, collision resistance, birthday attacks and HMAC
Oct. 11 No class
Oct. 18 Midterm (in class)
Oct. 25 Proof of work; blockchains; bitcoin
Nov. 1 Practical constructions of stream ciphers and block ciphers. Substitution-permutaton networks; attacks on reduced round SPNs; Feistel networks
Nov. 8 Searchable symmetric encryption and encrypted databases
Nov. 15 Basic number theory; Algorithmic number theory; Modular Arithmitic; Group theory
Nov. 22 Factoring; RSA assumption; Discrete log assumption
Nov. 29 Diffie Hellman; Hybrid Encryption; El Gamal encryption
Dec. 6 RSA Encryption; Padded RSA; Digital Signatures; Hash and Sign
Dec. 13 ?? Final Exam (in class)