CS 6111 : Foundations of Cryptography

In Semester 1, 2017-2018, 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. Office hours to be decided. I do not hold fixed office hours but will be happy to meet you anytime, just drop me an email!

• Suvradip Chakraborty. Email:suvradip1111@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 22nd Sept.
• 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, definitions, equivalence of definitions, one time pad and limitations of one time pad. Computational setting: 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 and Quadratic Residuosity. 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.

Hardcore bits and Pseudorandomness: Definition of hardcore bit. References : Barak's notes and Theorem 9.12 in Barak-Arora's book chapter. Discussion on whether there can exist a one way function in which no bit is hardcore. A good reference is this homework assignment by Jon Katz. The Goldreich Levin construction along with the general proof can be seen here.

Pseudorandom Generators: Construction of a PKE using hardcore bits. Discussion about security and 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.

MIDTERM (22nd Sept, in class, 2-3:15 pm)

Public Key Encryption: Definition and constructions. Good notes are here and here.

Message Authentication codes and Digital Signatures: Definitions and constructions. We used Ch 5 of Pass-Shelat.

Identity Based Encryption. This will not be included in the exam.

Interactive Proof Systems and Zero Knowledge Proof systems. Good notes are the first 3 lectures 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.

• Stanford's Coursera Cryptography class 1 and 2 by Dan Boneh.
• A course in Cryptography by Pass and Shelat.
• Introduction to Modern Cryptography by Katz and Lindell.
• Foundations of Cryptography by Oded Goldreich. Some chapters available free!
• Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Available free!
• Lecture Notes by Goldwasser and Bellare.
• Lecture Notes by Yevgeniy Dodis.
• Lecture notes by Chris Peikert.

Handouts.

Some useful handouts for probability, number theory and algebra are given below. Please refer to them on an "as needed" basis.

1. Handout for basic probability by Luca Trevisan and another one by Boaz Barak.
2. Handout for Algebra by Luca Trevisan.
3. More technical introduction to number theory by D. Angluin.
4. Very Basic and Basic number theory fact sheet by Dan Boneh.
5. Computational Number Theory notes by Mihir Bellare.

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.