COS 433 - Cryptography (Spring 2018)

Course Information

Instructor: Mark Zhandry ()
     Office Hours: Mondays, 3pm-4pm, COS 314
TAs: Udaya Ghai ()
     Office Hours: Tuesdays, 1pm-2pm, Tea Room
Qipeng Liu ()
     Office Hours: Wednesdays, 4pm-5pm, Location TBA
Lecture: MW 1:30pm - 2:50pm, Room Friend Center 008
Grading: 40% for roughly weekly homeworks, 30% Projects, 30% take-home final
Piazza: https://piazza.com/class/jb0zp9b0blf3o0
Textbook: There is no official text for this course, however Introduction to Modern Cryptography by Katz and Lindell (KL) is a good resource. Each lecture will have pointers to the appropriate sections of KL for those following along with the book.

Course Description

Cryptography is an ancient practice dating back almost 4000 years. For most of its history, cryptography was largely confined to military applications and was synonymous with encryption: translating data into secret codes. The classical practice of cryptography was considered an art, characterized by a perpetual tug of war between code makers and code breakers.

In the last few decades, however, cryptography has been fundamentally transformed. Modern cryptography extends far beyond basic codes to encompass a wide variety of concepts such as authentication and integrity. Modern cryptography is also now more of a science, grounded on rigorous theoretical foundations thus ending the tug of war in favor of the code makers. These features of modern cryptography have been fundamental in transforming cryptography from a military tool into one of the fundamental pilliars of our modern digital lives.

This course is an introduction to modern cryptography, emphasizing the theoretical foundations. We will cover a variety of topics, including secret key and public key encryption, authentication, commitments, pseudorandom generators, and some advanced topics

Prerequisites: Basic probability theory. Basic complexity theory (as in COS340) recommended. New this year, there will be projects that involve programming. However, no specific programming language will be required.

Tentative Schedule (subject to change)

Lecture Topic KL Section Notes
1 - M, 2/5 Course introduction, A Brief History of Cryptography 1.3 [1]
2 - W, 2/7 Definitions in Cryptography, the One-time Pad 1.4-2.2 [2]
3 - M, 2/12 Multiple Message Security, Issues, Randomized Encryption [3]
4 - W, 2/14 Limitations of Information-Theoretic Security, Stream Ciphers, PRGs, and Computational Assumptions 2.3-3.3 [4]
5 - M, 2/19 Constructing PRGs 6.1 [5]
6 - W, 2/21 CPA security and PRFs 3.4-3.5 [6]
7 - M, 2/26 PRPs, Block Ciphers, Modes of Operation 3.6, 6.2 [7]
8 - W, 2/28 Constructing Block Ciphers 6.2 [8]
9 - M, 3/5 Attacks on Block Ciphers 6.2 [9]
10 - W, 3/7 Class Cancelled due to storm
11 - M, 3/12 Message Integrity, MACs 4.1-4, 4.6 [10]
12 - M, 3/14 Authenticated Encryption, CCA Security 4.5 [11]
M, 3/19 No Class - Spring Break
W, 3/21
13 - M, 3/26 Collision Resistant Hashing, Random Oracle Model 5.1-4, 6.3 [12]
14 - W, 3/28 Commitment Schemes [13]
15 - M, 4/2 Number-theoretic constructions of symmetric primitives 8.3-8.4 [14]
16 - M, 4/4 One-way functions, hardcore bits 7.1 [15]
17 - M, 4/9 Relationships between Symmetric Primitives 7.2 [16]
18 - M, 4/11 Key Exchange, Trapdoor Permutations 10.3 [17]
19 - M, 4/16 Public Key Encryption 11.1-11.5, 13.1 [18]
20 - W, 4/18 Digital Signatures 12.1-12.4 [19]
21 - M, 4/23 Digital Signatures from One-way Functions 12.6 [20]
22 - W, 4/25 Identification Protocols 12.5 [21]
23 - M, 4/30 Zero Knowledge [22]
24 - W, 5/2 Misc [23]

Handouts

Basic Number Theory

Homework Assignments

Homework 8: [HW8]. Due Tuesday May 8, 11:59pm

Homework 7: [HW7]. Due Tuesday May 1, 11:59pm

Homework 6: [HW6]. Due Wednesday April 25, 11:59pm

Homework 5: [HW5]. Due Tuesday April 10, 11:59pm

Homework 4: [HW4]. Due Tuesday April 3, 11:59pm

Homework 3: [HW3]. Due Thursday March 15, 11:59pm

Homework 2: [HW2]. Due Thursday March 1, 11:59pm

Homework 1: [HW1]. Due Tuesday February 13, 11:59pm

Homework 0: Due Friday February 9, 11:59pm. Please fill out the following Doodle poll to indicate your availability for office hours. Ignore the exact date, and just fill out your general availability for days of the week/times during the Spring semester. Once everyone has filled out the poll, the teaching staff will decide on office hours.

https://doodle.com/poll/8cpyuxwue8bnw9nr

Homework Instructions

Homeworks will be assigned roughly every week. Homework assignments will be posted here on the course webpage by Tuesday, and will be due the following Tuesday. Expect there to be a homework assignment due every week except the first week of class and during weeks in which a project is due (for a total of about 8 assignments).

Format: Please type up your solutions. Please let the teaching staff know if this will be a problem. LaTeX is strongly preferred. Learning LaTex will require a learning curve, but will pay off in the long run. Once you are accustomed to LaTex, you will be able to typeset technical material such as equations very quickly.

Submission: Assignments will be due at 11:59pm on the due date of the assignment. Submission details TBD

Collaboration Policy: You are encouraged to discuss homework assignments with other students in the class. However, students must write up solutions individually, and must not share their written solutions with classmates. Please identify your collaborators on your homework submissions.

Formalism: You must always show all of your work. Unless otherwise stated, any cryptosystem derived in the homework assignment must analyzed for both correctness and security. That is, you must prove both the correctness and security of the scheme. When asked to prove a statement (correctness/security or otherwise), the proof needs to be well written and rigorous. Your proofs do not need to be overly formal, but should not contain any logical gaps or errors. Any statements proved in lecture can be used in the solutions without proof, but any other statement should be proved as a part of the solution.

Flexibility: If you do not turn in an assignment, or turn in an assignment late, you will receive a zero for that assignment. There will be no dropped homeworks. However, each homework assignment will have 60 available points, but will be graded out of 50 points. Therefore, it is possible to achieve up to 120% on each assignment. If you are not able to turn in an assignment, you may make up for it getting above 100% on the other homeworks.

Latex source files for first homework:
hw1.tex
template.tex


Final Exam

Instructions forthcoming

Old exam: Spring 2017 Final Exam

Projects

Project 3: Instructions: [PR3]. Files: RIAserver.pyc, call_server.py, ctxts.txt. Due date: May 15th

Project 2: Instructions: [PR2]. Due date: April 19th

Project 1: Instructions: [PR1]. Ciphertexts: [ctxts]. Due Dates:

Grading

h = min(total homework points, 400)
p = total project points (out of 300)
f = final points (out of 300)

Numerical grade = (h+p+f)/10

There is no set curve or grading scale for the course (so for example a 90% may or may not end up being an A). However, expect the grade distribution to be roughly consistent with upper-level COS courses.