CS499: Cryptography 
George Mason University, Computer Science, Fall 2018

Instructor: Prof. Foteini Baldimtsi (foteini@gmu.edu)
Office Hours: Mondays 2:00PM-4:00PM, Engineering 5333
Lectures: Tuesdays 4:30PM-7:10PM, Location: Blueridge Hall 129

Course Summary

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, we will also cover several recent topics in cryptography, such as the use of blockchains for crypto currencies (i.e. Bitcoin), zero-knowledge proofs of knowledge, 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.

Course Outcomes:  Students taking this class will be able to: (a) understand the security properties achieved by common cryptographic mechanisms such as encryption or digital signatures, (b) be familiar with a number of cryptographic protocols (toolbox) available to solve a variety of problems (message integrity, privacy, authentication, proof of knowledge etc), (c) gain some experience on how cryptographic tools are used to secure modern systems such as cryptocurrencies.  

Prerequisites: There is not hard prerequisite for this course but being familiar with material taught on CS 330, CS483 and MATH 125 is . Although we will learn about practical topics in cryptography, students will need some level of mathematical maturity, i.e. being familiar with concepts in probability theory (computation of expectation, conditional probability etc) and complexity theory (Turing machines, NP-completeness etc) would be helpful for an easier understanding of formal security definitions and proofs. This is not a course about computer hacking or computer security.

Required Materials

Text Book: Katz and Lindell. Introduction to modern cryptography, Second Edition. (Required). 

There will also be additional readings for each class (available online for free) listed below. 


Midterm: 25%
Assignments: 35% (5 assignments, bonus points offered in all of them) 
Final: 30% 
Quizzes: 10% (6 quizzes, lower grade dropped)

Assignment Submission and Late Policy: Homework questions will be posted on Blackboard and solutions have to be submitted through Blackboard (no credit will be given otherwise).  Assignments received within 24 hours after the deadline lose 20%, within 48 hours 40% and after that no credit will be given. To be fair with everyone in class no exception will be made to the rule above.

Grading Scale (before scaling):

A+ >97%   A   >92%   A-  >90%
B+ >87%   B   >82%   B-  >80%
C+ >77%   C   >72%   C-  >70%

Graduate Students (CS 595): Graduate students will be given an extra HW problem to solve in each of the five assignments. They will also have to solve an extra question in both midterm and final. 

Communications: We will use Piazza to communicate with you.  If you have a question about the course you should: (a) Come to office hours, OR (b) Post on Piazza. We have already set up different tags for HW problems and lectures. Please don't use private posts/emails to ask technical questions. The rest of the class is probably also interested in your question, so make it public! 

Honor code:  All students must adhere to the GMU Honor Code. You can discuss lecture material with other students in class but you have to work on the assignments alone. More specifically:  (1) You must work on the homework problems and write your solutions completely on your own, without looking at other people’s write-ups. (2) You are welcome to use any textbooks, online sources, blogs, research papers, Wikipedia, etc to better understand a notion covered in class or in a homework question. If you do so you have to properly cited it in any submitted work. Failure to do this is plagiarism and is serious violation of the GMU Honor Code and basic scientific ethics, and will not be tolerated. Note that it is not OK to search for solutions to HW problems online.

Class Schedule (Tentative):

 Lecture  Topics  Suggested Readings
([KL] stands for Katz & Lindell  - our main textbook)
 HWS/ Quizzes
08/28 Lec. 1
Introduction & Logistics

Semantic Security
One-time Pad
[KL]: Chapters 1.1, 1.2, 1.4 and 2.1 - 2.3. (2.1 contains a proof of why Def. 3 is equivalent to Def. 1&2 we saw in class, 2.3 contains a proof about the limitation of semantic security |KS|>|MS|). 

[Alternative readings]: Ch. 1 of Pass & shelat OR Ch. 1 of Rosulek

HW1 out
 09/04 Lec. 2 Encryption and Indistinguishability
(intro slides)
[KL]: Chapters 3.1, 3.2, 3.4 and 3.7.1 (for CCA definition). We started on 3.3 but not done.

[Alternative Readings]: Ch. 4 of Rosulek, Ch. 2.1, 3.1, 3.2 from Pass & shelat
Quiz 1
 09/11 Lec. 3 Pseudorandom Generators and CPA security [KL]: Chapter 3.3. Before class you have to read proof of Thm 3.18.

[Alternative readings]: Ch. 5 of Rosulek
Quiz 2
 09/18 Lec. 4 Pseudorandom Functions, Permutations
[KL]: Chapters  3.4, 3.5

[Alternative readings]: Ch. 6,7,8 of Rosulek, Ch. 3.8 from Pass & shelat
HW1 in 
HW2 out
 09/25 Lec. 5 Modes of Operation

Proving a scheme CPA secure
[KL]: Chapters 3.5, 3.6 (make sure you understand Proof of Construction 3.30)
Optionally, read Chapters 6.1,6.2 if you are curious about constructions of stream/block ciphers. 

[Alternative readings]: Ch. 9 of Rosulek

Quiz 3
 10/02 Lec. 6  Message Authentication Codes
[KL]: 4.1, 4.2, 4.3.1, 4.4 (we skipped proof in 4.4.2), 4.5 (we skipped proof of Thm 4.19)
HW2 in
HW3 out
 10/09      No class due to Fall Break
 10/16 Lec. 7   Review HW3 in
 10/23  Midterm  
 10/30 Lec. 8 Hash Functions
Public Key Encryption
[KL]: 5.1, 5.2, 5.3 (including proof of Thm 5.6), 5.65, 11.1, 11.2 (excluding Proof of Thm 11.6), 11.4
Optional: 5.5 (Random Oracle Model) 
 HW4 out
 11/6  Lec. 9 Public Key Encryption
Key Agreement  
[KL]: Chapter 8 for number theory background. Sec 10.1, 10.3, 10.4, 11.4, 11.5  Quiz 4
 11/13 Lec 10 Secret Sharing, Multiparty Computation & Yao,
Oblivious Transfer
Material on piazza +
Secret Sharing: Ch. 3 of Rosulek and Ch. 6.1 of Pass & shelat
MPC and Yao: Ch 6 of Pass & shelat
 HW4 in
HW5 out
 11/20 Lec 11 RSA Encryption, Signature Schemes  [KL]: 11.5, Ch. 12 Quiz 5
 11/27 Lec 12 Zero Knowledge Proofs,
Bitcoin and Cryptocurrencies
For the ZK proofs part we closely followed the lecture notes by Boaz Barak (can be found here).  HW5 in
 12/04 Lec 13Review   Quiz 6
12/11     Final