In Semester 1, 2018-2019, I will be teaching CS 6111: Foundations of Cryptography.
Administrative Information.
When and Where.
Classes are held on Wednesday 3:25-4:40 pm and Friday 2:00 pm - 3:15 pm. Location: CSB 36.
Office Hours and Teaching Assistants.
The teaching assistants for the course are listed below.
Monday 2-4 pm are the office hours, held in the PACE lab. I do not hold fixed office hours but will be happy to meet you anytime, just drop me an email!
- Rachit Garg. Email:rachit0596@gmail.com
- Monosij Maitra. Email:monosij.maitra@gmail.com
Pre-requisites.
This course requires mathematical maturity, you should be comfortable with the language of proofs. Knowledge of algorithms, theory of computing (i.e. familiarity with reductions), some algebra and probability theory is required. The course will be self contained for the most part but you should be familiar with the tools and techniques used in theoretical computer science.
Requirements.
- Homeworks: 20%. There will be a homework assignment every two weeks.
- Midterm: 25%. To be held on 26th Sept from 3:30-5:30 pm.
- Major Exam: 35%
- Project: 20%
Policies and Grades.
Collaboration is encouraged but you must write up solutions on your own. You must also write the names of all the people you discussed the problem with. In case you find material that will help
you in solving some problems, you should mention the source in your writeup. Class participation will also be taken into account when assigning grades.
I expect all students to behave according to the highest ethical standards. Any cheating or dishonesty of any nature will result in failing the class.
Lecture Notes and Handouts.
Lecture Summaries.
The course will follow the outline of
this previous offering.
Introduction: Introduction to Cryptography. Motivation, hardness assumptions, discussion on provable security. Principles of Cryptographic design : formulating security model, distilling mathematical assumption, reducing hardness of cryptosystem to mathematical assumption. Case study of secure encryption. Slides were used and are available here. The material was from Katz-Lindell's book (see Reading material below).
Introduction continued: Definitions of Symmetric and Public Key encryption. Discussion on why the latter is better. Perfect secrecy, one time pad and limitations of one time pad. Computational secrecy: definition of PPT algorithms, negligible functions. Discussion about randomized algorithms and security parameter. We used the Katz-Lindell book for this material, which is available in the library. You can also read Lec 1 in these notes , by Yevgeniy Dodis.
Basic Primitives and Candidates: Definitions of OWF,OWP,TDP and number theoretic examples of these from integer factoring, discrete log, RSA. We also covered the requisite number theory background including Fermat's little theorem, chinese remainder theorem, Euler's theorem and so on. The material was from Lec 2 and 3 here, by Yevgeniy Dodis.
Pseudorandom Generators: Discussion about next bit unpredictability (NBU). Show a function satisying NBU. Definition of PRG. NBU=> PRG: first example of Hybrid argument. Equivalence of OWF and PRG. Good notes are here and here.
Pseudorandom Functions and Provably Secure Encryption: Definition and construction of pseudorandom functions (PRF). Definitions of security for symmetric and public key encryption, and constructions. Good notes are lectures 6,7 and 8 here. We used these notes for CPA secure symmetric key encryption.
Public Key Encryption: Definition and constructions. Good notes are here and here.
Midterm Sep 26, 3:30-5:30 pm. CSB 27.
Bitcoins and Blockchains. Introduction (not included in exam).
Message Authentication codes and Digital Signatures: Definitions and constructions. Good notes are Ch 5 of Pass-Shelat.
Interactive Proof Systems and Zero Knowledge Proof systems. Good notes are the Lectures 1 and 5 here and lectures 14 and 18 here. Please also see Ch 7 of Yehuda Lindell's notes here.
CCA1 Security: Naor Yung construction. We used these slides. Good notes are lectures 6 and 7 here and here.
Reading Material and References.
Background Reading:
This blog by Ryan O'Donnell and
this follow-up discussion contains a nice discussion of average case hardness, in particular Impagliazzo's worlds.
Here is a discussion on basing cryptography on NP-hard problems by Scott Aaronson.
This Wikipedia entry is also good to read.
Here is a formal discussion of Shannon's lower bound for perfect security, section 1.3 of
this contains another.
While we will not follow any particular text, the following are useful references.
Handouts.
Some useful handouts for probability, number theory and algebra are given below. Please refer to them on an "as needed" basis.
- Handout for basic probability by Luca Trevisan and another one by Boaz Barak.
- Handout for Algebra by Luca Trevisan.
- More technical introduction to number theory by D. Angluin.
- Very Basic and Basic number theory fact sheet by Dan Boneh.
- Computational Number Theory notes by Mihir Bellare.
Homeworks.
- Homework 1 is out. Due back 5th Sept at the BEGINNING of class.
- Homework 2 is out. Due back 21st Sept at the BEGINNING of class.
- Homework 3 is out. Due back 31st Oct at the BEGINNING of class.
- Homework 4 is out. Due back 9th Nov at the BEGINNING of class.
Policy:
You are encouraged to discuss problems but you are expected to fully understand and write down solutions on your own. Once the HW is returned, we will discuss solutions in class where I will randomly call upon students who got a homework problem correct to solve the problem on the board so that we all can understand and discuss the solution. So make sure you really know the solutions you write!
The TAs will be watching for copied answers. If any copying is detected then you will earn a zero in ALL homework assignments. I will not discuss or bend this rule. No late submissions will be accepted unless in extreme situations.