In Semester 1, 2015-2016, I will be teaching CSL 759: Cryptography and Network Security.
Administrative Information.
When and Where.
Classes are held on Monday and Thursday between 3:30 pm - 5 pm. Location: Bharti building, Room 201.
Office Hours and Teaching Assistants.
The teaching assistants for the course are listed below. Please email them for setting up meeting times. I do not hold fixed office hours but will be happy to meet you anytime, just drop me an email!
- Ishaan Preet Singh. Email:cs5110280@cse.iitd.ac.in
- Sai Praneeth Reddy. Email:cs5110294@cse.iitd.ac.in
- Divyanshu Bagga. Email:csz138107@cse.iitd.ac.in
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%
- 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.
- Lec 1 (23rd July) : Introduction to Cryptography. Motivation, hardness assumptions, discussion on provable security. 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.
- Lec 2 (27th July): 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).
- Lec 3 (30th July): Formalizing easy and hard: Definition of probabilistic polynomial time (PPT) algorithms, negligible functions. Definition of One way Functions, One way Permutations. Examples based on integer factoring and discrete log. Basic number theory review: groups, definition of Z_n^*, Fermat's little theorem.
- Lec 4 (3rd Aug): Proof of Fermat's little theorem, efficient algorithm for modular exponentiation. Definition of Euler's phi function and Euler's theorem. Definition of trapdoor permutation and the example of RSA. Discussion of how to use OWFs for storing passwords and the many real world problems with this approach. Lectures 3 and 4 are based on this lecture by Yevgeniy Dodis.
- Lec 5 (6th Aug): Quadratic residues, Legendre symbols, ease of computing LSB of discrete log. Here is one good reference, here is another.
- Lec 6 (10th Aug): Jacobi symbol, QR assumption, Rabin's OWF based on factoring. References listed for Lec 5 are applicable.
- Lec 7 (13th Aug): Goldreich Levin hardcore bit. References : Barak's notes , Yevgeniy's notes and Theorem 9.12 in Barak-Arora's book chapter .
- Lec 8 (17th Aug) and Lec 9 (20th Aug): Using hardcore bit for coin tossing on the telephone and for symmetric key encryption. Definition of computational indistinguishability and pseudorandom generator. Construction of PRG with single bit stretch from hardcore bit. Barak's notes are a good reference for single bit stretch PRG and Arora's notes are a good reference for poker playing and a general introduction.
- Lec 10 (24th Aug) and Lec 11 (27th Aug): Stretching the output length of PRG. Construction using OWP and hardcore bits. Definition of next bit unpredictability and its connection with PRG. Proof that construction satisfies NBU. References: Barak's Notes and Yevgeniy's notes . Discussion on whether there can exist a one way function in which no bit is hardcore. A good reference (thanks to Raghuvansh!) is this homework assignment by Jon Katz.
- No lectures on 31st Aug and 3rd Sept due to Minor Test 1.
- Lec 12 (7th Sept): Proof that NBU implies PRG. Explicit examples of PRG: Blum-Micali and Blum-Blum-Shub. Definition of PRF. Barak's Notes, Yevgeniy's notes , Leo's notes are a good reference.
- Lec 13 (10th Sept): Symmetric Key encryption from PRG and limitations. Definition and discussion of CPA security for symmetric key encryption. Motivation for PRFs. Yevgeniy's notes are a good reference.
- Lec 14 and 15 (14th and 16th Sept): Construction of Symmetric key encryption from PRFs. Proof that it satisfies CPA security. Started construction of PRFs from PRGs. Here are some references.
- Lec 16 (21st Sept): Construction of PRF from PRG (GGM). Discussion about hybrid argument. Good references are here and here.
- Lec 17 24th Sept): Problem solving in preparation of midterm.
- (28th Sept): No class due to midterm exam. .
- Lec 18 (1st Oct): Definition of Public Key encryption, constuction from TDPs and DDH (El Gamal Encryption). Good notes are here and here.
- Lec 19 (5th Oct) and 20 (8th Oct): Introduction to the problem of message authentication. Difference between authentication and encryption, a.k.a trust versus privacy. Definition of MAC and construction from PRFs. Good notes are here and here.
- Lec 21 (12th Oct): Discussed solutions for Mid Term Exam.
- Lec 22 (15th Oct): Lecture about Bitcoins. Slides are here.
- 19th and 22nd Oct: No class due to Mid Semester Break.
- Lec 23 (26th Oct): Digital Signatures. Definition. One time signatures from One Way Functions. Construction from TDPs in ROM. Discussion of Random Oracle Model. Good references are Chris's notes and Yevgeniy's notes .
- Lec 24 (29th Oct): One time to many time signatures using CRHFs and chaining. Proof of TDP based signatures (full domain hash) in Random Oracle Model. References from previous lecture apply, in addition to this.
- Lec 25 (2nd Nov) and Lec 26 (4th Nov, rescheduled from 5th Nov): Introduction to Zero Knowledge. Slides by Yevgeniy Dodis are available here. Good notes by Rafael Pass are 1, 2 and 3. Here is the SUDOKO demonstration I showed in class.
- Lec 27 (16th Nov): Introduction to lattice based cryptography. Discussion on fully homomorphic encryption.
Reading Material and References.
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! Here are the solutions (on IIT privateweb).
- Homework 2 is out! Here are the solutions (on IIT privateweb).
- Homework 3 is out. Here are the solutions (on IIT privateweb).
- Homework 4 is out! Here are the solutions (on IIT privateweb).
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.