CS 499 / CS 587: Cryptography, Spring 2020

Course Overview

Course Description

Content
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, the differences between public key cryptography and symmetric key cryptography, and a few ways to build public key encryption and signatures. We will learn about how to properly define security, and how to prove that our constructions are secure. In addition, with what time we remains, we will cover several recent topics in cryptography, such as the use of block chains for crypto currencies, and securely computing on private data.

Objectives
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.

Course Outcomes
Students taking this class will: (a) be able to understand the security properties achieved by common cryptographic mechanisms such as encryption or digital signatures, (b) be familiar with a number of cryptographic primitives available to solve a variety of problems, (c) gain some experience with how these cryptographic tools can be used to secure modern systems.

Prerequisites
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 CS330 would be a good course to take prior to this one. Students should be comfortable writing proofs, and should have comfort with basic probability theory.

 

Course Requirements

Homework

There will be 10 homework assignments. Homework will be due on Thursdays. 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.

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. Please post on piazza if you have trouble.

Exams

There will be one mid-term and one final exam. The final exam is scheduled by the University: Tuesday, May 12, 1:30-4:15. Each will cover roughly half of the semester. The final will NOT be cumulative. Both exams are closed book, and notes will NOT be allowed. The exams are weighted such that the better score counts for more points (see below).

Quizzes

Quizzes are short: 1-2 questions, multiple choice or fill-in-the-blank. You will need a web browser, and a google login to answer the questions, as the results will be tallied immediately using google forms. If either of these requirements creates a problem, please email me, or come discuss it with me. Each single quiz is worth < 1% of your grade. They will be given at the start of class (don't be late!), on Tuesdays. They will cover the previous 1 or 2 lectures, and mainly serve to help me gauge what the students have understood, and what needs further explanation.

CS 587

Students in CS 587 will be be given extra homework problems on most homeworks, and an extra problem on each of the exams. They will also have to read Chapter 7 independently.

Grading

Quizzes -- 10%
Homeworks -- 30%. The lowest two homework grades will be dropped.
Exams -- 60%. Of the two exams, the higher score will be weighted to count for 35%, and the lower for 25%.

Tentative Schedule

Date Topic Relevant Reading Homework
Jan. 21 / 23 The goal of modern cryptography; Perfect secrecy via the one-time pad; 1.1 - 1.4, A.3, 2.1, 2.2 Hw1 due January 30
Jan. 28 / 30 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 Hw2 due Feb. 6
Feb. 4 / 6 Pseudorandom functions; achieving CPA security; pseudorandom permutations and block ciphers 3.5 Hw3 due Feb. 13
Feb. 11 / 13 Modes of operation in block ciphers; Chosen Ciphertext Attack security; message authentication 3.6, 3.7, 4.1-4.3.1 Hw4 due Feb. 20
Feb. 18 / 20 Message authentication for arbitrary length messages; CBC-MAC 4.3.2, 4.4.1 Hw5 due Feb. 27
Feb. 25 / 27 authenticated encryption; Hash functions, collision resistance, birthday attacks and HMAC 4.5, 5.1, 5.3, 5.4.1  
March 3 / 5 Midterm review (3/3), and midterm exam (3/5)    
March 10 / 12 Spring Break    
March 17 / 19 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  
March 24 / 26 Basic number theory; Algorithmic number theory; Modular Arithmitic; Group theory 8.1.1 - 8.1.4, B.1, B.2.1 - B.2.3  
March 31 / April 2 Factoring; RSA assumption; Discrete log assumption 8.1.5, 8.2.1, 8.2.3, 8.2.4, 8.3.1 - 8.3.3  
April 7 / 9 Diffie Hellman; Hybrid Encryption; El Gamal encryption 10.1 - 10.4, 11.1, 11.2.1, 11.4.1, 11.3.1
April 14 / 16 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  
April 21 / 23 Proof of work; agreement protocols; blockchains; zero knowledge
April 28 / 30 Secure computation
May 12 Final Exam (in class)