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

Date Topic Relevant Reading Homework
Aug. 30 The goal of modern cryptography; Perfect secrecy via the one-time pad; 1.1 - 1.4, A.3, 2.1, 2.2 Hw1 out
Sept. 6 limitations of perfect secrecy; definitions of computational security; Security reductions; Pseudorandom generators; proof of security for pseudo-OTP; Chosen plaintext attack security 2.3, 3.1, 3.2.1, 3.3, 3.4 Hw1 due (9/8 is fine).
Hw2 out.
Sept. 13 Pseudorandom functions; achieving CPA security; pseudorandom permutations and block ciphers 3.5  
Sept. 20 Modes of operation in block ciphers; Chosen Ciphertext Attack security; message authentication 3.6, 3.7, 4.1-4.3.1 Hw2 due. Hw3 out
Sept. 27 Message authentication for arbitrary length messages; CBC-MAC 4.3.2, 4.4.1  
Oct. 4 (To be rescheduled.) authenticated encryption; Hash functions, collision resistance, birthday attacks and HMAC 4.5, 5.1, 5.3, 5.4.1 HW 3 due.
Oct. 11 No Class    
Oct. 18 Midterm (in class)    
Oct. 25 Proof of work; blockchains; bitcoin TBD  
Nov. 1 Practical constructions of stream ciphers and block ciphers. Substitution-permutaton networks; attacks on reduced round SPNs; Feistel networks 6.1.1-6.1.3, 6.2.1 - 6.2.2  
Nov. 8 Searchable symmetric encryption and encrypted databases TBA  
Nov. 15 Basic number theory; Algorithmic number theory; Modular Arithmitic; Group theory 8.1.1 - 8.1.4, B.1, B.2.1 - B.2.3 Hw4 out.
Nov. 22 Factoring; RSA assumption; Discrete log assumption 8.1.5, 8.2.1, 8.2.3, 8.2.4, 8.3.1 - 8.3.3  
Nov. 29 Diffie Hellman; Hybrid Encryption; El Gamal encryption 10.1 - 10.4, 11.1, 11.2.1, 11.4.1, 11.3.1 Hw4 in. Hw5 out.
Dec. 6 RSA Encryption; Padded RSA; Digital Signatures; Hash and Sign 11.2.2, 11.5.1, 11.5.2, 11.5.4, 12.1-12.4 Hw5 in.
Dec. 13 ?? Final Exam (in class)