CS 499 / CS 587: Cryptography, Spring 2022

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 blockchains 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
CS 330, CS 310, and STAT 344. More generally, students should have some level of mathematical maturity. Students should be comfortable writing proofs, and should have comfort with basic probability theory.

Logistics

Office Hours
I will hold office hours in-person, in my office, on Tuesdays after class, and Wedn. at 3pm. Occasionally, by announcement, I will instead hold my Wednesday office hours virtually on Zoom. My office hours should be viewed as study sessions: homework is almost always due on Thursday at class time, and I will help you with the homework in my office hours. All are welcome at the same time! I'll take questions and we'll work through problems together. For students that expect to struggle with the material, I strongly encourage you to attend at least one, and preferably both hours each week. If you lose points on a homework, you should see this as an indication that you need help, and you should try to attend office hours. The TA will also hold hours, and he is able to help you in the same manner. To speak to me privately, please email me ahead of time, and I'll reserve some time for a private discussion, likely at end of office hours.

Piazza
All class announcements will be made on Piazza. I will answer all questions on Piazza. My email inbox is typically swamped, and anything sent there has a good chance of being missed. If you do email me, put 487/587 in the subject line. But better is to message me on piazza. Students are encouraged to post homework questions on piazza! I realize that some posts need to be private, but when in doubt, I encourage you to make your posts public! Everyone will benefit from your questions, and I prefer that we all learn from them. Generally, I'm not that worried about questions that give hints. (Within reason.)

Gradescope
Quizzes, homeworks and exams will all be submitted through Gradescope. You can find gradescope through Blackboard: click on Tools, then gradescope. You should also be able to access it directly from the gradescope website, if you use your GMU login. When submitting an assignment, please mark each question with the appropriate question number, as this makes grading much easier.

Overleaf
I will release the assignments on overleaf. This is a web-based platform for writing latex documents. You do not need special software, and I will not insist that you use latex to write your answers. You can simply view the PDF from the webpage, and submit answers to Gradescope in whatever format you like. However, I encourage you to use latex - it is fairly easy, and produces nice PDFs. To do that, just copy the project that I've shared, and edit. You still submit the resulting PDF through Gradescope.

Lecture Videos
Students are expected to watch videos each week, prior to the class meeting time. In the meeting, I will review questions about those videos, and we will work through related problems. Links to the videos can be found below, under the class schedule.

 

Course Requirements

Homework

There will be roughly 10 homework assignments. Homework will be due at class time 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 copy the overleaf project as a template. Please post on piazza if you have trouble.

Exams

There will be one midterm and one final exam. The better score will count more heavily towards your final grade. The final mostly covers the 2nd half. However, I may include some material from the first half if I feel students did not understand it sufficiently well. I will inform you ahead of time if I choose to do this.

Quizzes

Quizzes are short: 1-2 questions, multiple choice or fill-in-the-blank. They will be administered through Gradescope. Each single quiz is worth < 1% of your grade. They will be released on Friday, and due by the start of class on Tuesday. Each will cover the videos that were intended to be watched at home, in preperation for the week of lectures to come. They mainly serve to help me gauge what the students have understood from the videos, 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%. The lowest two quiz grades will be dropped.
Homeworks -- 30%. The lowest two homework grades will be dropped.
Midterm Exam -- 25% or 35%.
Final Exam -- 35% or 25%.
(The better exam score will count for 35%)

Do I curve? The short answer is yes. The more accurate answer is more subtle. I do not force the final grades to fit any kind of curve. Doing this would require a certain number of A's and a certain number of F's. I do not believe that there must be some minimum number of failures, or that there should be some maximum number of A's. (Before you get too excited, the symmetric argument is valid as well.)

When the final exam is graded, I will re-weight everyone's score according the weights described above, and I will sort them. I will then look to draw lines where there are clear gaps in the scores. For example, it is possible that an 83 will get an A, and an 81 will not. To help give you a sense of where you stand, after the midterm, I will give a histogram of score projections, and a spreadsheet that allows you to see how you will compare to those projected scores based on how you perform on the remaining assignments.

Intended Schedule and Material

The schedule below is not modified throughout the semester. For a live schedule, including homework links, see the Course Webpage.

Security Games

JPG PRG PRF EAV CPA CCA MAC CRHF RSA DLog (C|D)DH unforgeability
MP4 PRG PRF EAV CPA CCA MAC CRHF RSA DLog (C|D)DH


Date Topics and Videos Slides Relevant Reading Homework
1/25, 1/27 Classic Ciphers; Perfect secrecy via the one-time pad 1, 2 1.1 - 1.4, A.3, 2.1, 2.2
2/1, 2/3 Definitions of computational security; The goal of modern cryptography; Pseudorandom generators; Attacking a broken encryption scheme 1, 2 2.3, 3.1, 3.2.1, 3.3.1
2/8, 2/10 Pseudo-OTP; proof of security for pseudo-OTP; Multiple message security; Chosen plaintext attack security; Pseudorandom functions 1, 2, 3 3.3.2, 3.3.3, 3.4
2/15, 2/17 Achieving CPA security; Variable length enc; Pseudorandom permutations;
modes of operation: ECB, CBC, OFB, CTR
1, 2, ECB, CBC, OFB, CTR 3.5, 3.6.2
2/22, 2/24 (async.) Chained CBC; Chosen Ciphertext Attack security; Padding oracle attacks; Padding oracle attack example 1, 2, 3, 4 3.7
3/1, 3/3 Message authentication; A secure MAC scheme; Variable length MACs; Authenticated encryption 1,2, 3, 4, 5 4.1-4.3, 4.4.1, 4.5.1-4.5.2
3/8, 3/10 Midterm Review and exam      
3/15, 3/17 Spring Break      
3/22, 3/24 Hash functions, collision resistance, birthday attacks, Hash-and-MAC, HMAC, Applications of hash functions 1, 2, 3 5.1, 5.3, 5.4.1, 5.5, 5.6
3/29, 3/31 Practical constructions of block ciphers: SPNs and Feistel Networks; Double and Triple Encryption. Meet in the middle attack. 1, 2 6.2 (excluding 6.2.6)
4/5, 4/7 Modular Arithmitic; Group theory 1, 2 8.1.1 - 8.1.4, B.1, B.2.1 - B.2.3
4/12, 4/14 RSA assumption; Discrete log assumption; Diffie Hellman 1, 2, 3 8.2.1, 8.2.3, 8.2.4, 8.3.1, 8.3.2, 8.3.3
4/19, 4/21 Prime order groups; Concrete parameters; CRHF from Dlog; 1, 2 10.1 - 10.4
4/26, 4/28 Key Exchange; Public Key Encryption; El Gamal encryption; RSA Encryption; Hybrid Encryption 1 pdf,2 pdf,3 pdf,4 pdf,5 pdf 11.1, 11.2.1, 11.4.1, 11.3.1, 11.2.2, 11.5.1, 11.5.2, 11.5.4
5/3, 5/5 Random oracles; (587: One way functions) Digital Signatures (defs, constructions); PKI; TLS 1,23 pdf, 4 pdf,
5 pdf, 6 pdf
5.5, 5.6, 7, 12.1-12.4, 12.7-12.8
5/12 Final exam: 10:30 - 1:15 Final exam: 10:30 - 1:15 Final exam: 10:30 - 1:15