In Semester 2, 2013-2014, I will be teaching CSL 759: Cryptography and Network Security.
Administrative Information.
When and Where.
Classes are held on Tuesday, Wednesday and Friday between 6 pm - 7 pm. Location: Bharti building, Room 201.
Note: we are now holding classes on Tuesday and Wednesday 6-7:30 pm. No class on Friday!
Teaching Assistants.
The teaching assistants for the course are listed below. Please email them for setting up meeting times.
- Chandrika Bharadwaj. Email: chandrika.bhardwaj@gmail.com
- Abhay Gupta. Email: abhay3390@gmail.com
- Nikhil Kumar. Email: nikhilkumar4@gmail.com
- Utkarsh Ohm. Email: utkarshohm@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: There will be a homework assignment every two weeks. Each student will also be expected to scribe one lecture. Total weight of homeworks and scribe will be 20%.
- Minor exam 1 (20%) and 2 (20%)
- Major Exam: 40%
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.
Below are summaries of the lectures already conducted.
- Lecture 1 (Jan 3, 2014): Motivation for Crypto, Principles of Cryptographic design : formulating security model, distilling mathematical assumption, reducing hardness of cryptosystem to mathematical assumption. Case study of secure encryption. Slides for Lec 1 are available (also in pdf).
- Lecture 2 (Jan 7, 2014): Definition of PPT, negligible functions, One way Functions, One way Permutations, Trapdoor Permutations. Example of weak and strong OWF from factoring and application to Password Authentication. Scribes are available edited and unedited.
- Lecture 3 (Jan 8, 2014): Hardness Amplification: conversion of weak OWF to strong OWF. Useful reference for this is Rafael Pass' notes Section 2.3 or Oded Goldreich's book Section 2.3. Scribes are available unedited.
- Lecture 4 (Jan 10, 2014): Recap of Hardness Amplification. Example of OWP from Discrete Log and some relevant number theory. Scribes are available unedited.
- Jan 14, 2014: Holiday. Happy Makar-sakranti!
- Lecture 5 (Jan 15, 2014): LSB of Discrete log OWP is efficiently computable via Legendre symbol. Construction of TDP from RSA and application of TDP to weakly secure one time encryption. Chinese remainder theorem and Jacobi Symbols. Reference: Lecture 3 of Yevgeniy's notes. Scribes are available unedited.
- Lecture 6 (Jan 17, 2014): Examples of CRT. Rabin's OWP from squaring and reduction to factoring. Hardcore bits. Proof that MSB is hardcore for DL OWP. Reference: Lectures 3 and 4 of Yevgeniy's notes. Scribes are available unedited.
- Lecture 7 (Jan 21, 2014): Goldreich Levin hardcore bit. References : Barak's notes , Yevgeniy's notes and Theorem 9.12 in Barak-Arora's book chapter . Scribes are available unedited-1. and unedited-2.
- Lecture 8 (Jan 22, 2014): Using hardcore bit for coin tossing on the telephone and for one bit encryption. Definition of computational indistinguishability and pseudorandom generator. Construction of PRG with single bit stretch from hardcore bit. Scribes are available unedited-1 . 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.
- Lecture 9 (Jan 28, 2014): Stretching the output length of PRG. Construction using OWP and hardcore bits. Definition of next bit unpredictability. Proof that construction satisfies NBU. Barak's Notes and Yevgeniy's notes are a good reference. Scribes are available unedited-1. and unedited-2. .
- Lecture 10 (Jan 29, 2014): Proof that NBU implies PRG. Explicit examples of PRG: Blum-Micali and Blum-Blum-Shub. Definition of PRF. Barak's Notes and Yevgeniy's notes are a good reference. Scribes are available unedited.
- Lecture 12 (Feb 4, 2014): Problem solving session in preparation for the minor.
- Feb 5, 2014: No class since minor exam on Feb 6.
- Lecture 13 and 14 (Feb 11 and 12, 2014): Guest lectures by Dr. Somitra Sanadhya on block ciphers. His slides are here. Additional references on AES are here.
- Lecture 15 (Feb 18, 2014): Definition of PRFs. Construction from PRG. Definition of symmetric key encryption and eavesdropping attack. Here are some references. Scribes are available unedited-1 and unedited-2.
- Lecture 16 (Feb 19, 2014): Construction of symmetric key encryption from PRGs one-time secure against eavesdropping attack. Discussion on multiple message security and problems with deterministic encryption. Using PRGs in synchronized mode to achieve multiple message security. Definition of CPA security. A good reference is Yevgeniy's notes . Scribes are available unedited-1 and unedited-2. .
- Lecture 17 (Feb 25, 2014): Construction of CPA secure symmetric key encryption from PRFs. A good reference is Yevgeniy's notes. Discussion on perfect security and Shannon's bound (see this for a discussion). Scribes are available unedited-1. and unedited-2.
- Lecture 18 (Feb 26, 2014): Public key encryption. Definition of CPA security. DDH assumption and El Gamal encryption. Useful properties of ElGamal encryption. A good reference is Yevgeniy's notes and Debdeep's notes. The latter even contains a discussion of stronger notions of security than IND based security. Scribes are available unedited-1 and unedited-2.
- Lecture 19 (Mar 12, 2014): Padded RSA PKE (see this ), Goldwasser-Micali PKE based on QR (see this ), Regev's LWE based PKE (see this ) and proofs. Discussion on semantic security for PKE and its equivalence to IND based security. Scribes are available unedited.
- Lecture 20 (Mar 14, 2014): Proof that semantic security is equivalent to IND. A good reference is here. Scribes are available unedited-1 and unedited-2.
- Lecture 21 (Mar 18, 2014): 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. A good reference is here. Collision resistant hash functions. Scribes are available unedited-1 and unedited-2.
- Lecture 22 (Mar 19, 2014): Merkle Damgard transform for converting fixed length CRHFs to handle arbitrary length. MACs for arbitrary lengths using block ciphers (CBC mode) and CRHFs. Construction of HMAC and NMAC. Slides for the class are available here. There are no scribes for this class.
- March 25, 2014: No class due to Minor 2 exam.
- Lecture 23 (March 26, 2014): Introduction to Obfuscation : Impossibility of virtual black box obfuscation for general programs. Slides are available here. Digital Signatures: Definition, Lamport's one time signatures, Domain extension of OTS, converting one time to many time, Diffie Hellman heuristic, efficient signatures in ROM based on trapdoor OWP. Slides for the class are available here. Scribes are available unedited-1 and unedited-2. A good reference for the material is Yevgeniy's notes .
- Lecture 24 (April 2, 2014): Introduction to lattice based cryptography : SIS and LWE problems, Lattice trapdoors, Regev's PKE. Slides from the class are available here.
- April 2, 2014: No class: instructor not well. Makeup class will be held on April 11.
- April 8, 2014: No class: Ram-Navmi Holiday
- Lecture 25 (April 9, 2014): Identity based encryption from Learning With Errors. Scribes are available unedited.
- Lecture 26 (April 11, 2014): Makeup class for April 2. Interactive Proof Systems and Zero Knowledge. Examples of graph isomorphism (GI), graph non isomorphism (GNI), 3-colorability. Introduction to commitment schemes. Slides for the class are available here. A useful reference is MIT open course notes. See the first 5 lectures (its a bit more advanced than what we will cover). See the SUDOKU demo on Moni Naor's page.
- Lecture 27 (April 15, 2014): More on zero knowledge. Definitions of perfect, statistical and computaional ZK (see Chris's notes for a reference on various kinds of indistinguishability). ZK simulation strategies for GI, GNI. Protocol for QR. A good reference is Rafael's notes. Scribes are available unedited.
- Lecture 28 (April 16, 2014): Simulation strategy for graph 3 colorability. Definition of Non interactive zero knowledge (NIZKs) and its impossibility in the plain model. Discussion of the CRS model. Mention (but not prove) application to CCA security. Scribes are available unedited-1. and 2.
- Lecture 29 (April 22, 2014): NIZKs: Hidden bits model. Transforming a NIZK in the hidden bits model to one in CRS model using TDPs. We use the reference Jon Katz's notes . Another good reference is MIT open course notes. Some good slides are here. There will be no scribes for this class, but you can refer to Katz's notes, which I followed closely.
- Lecture 30 (April 23, 2014): NIZK for NP in the Hidden bits model (Graph Hamiltonicity). We use the references Jon Katz's notes-1 and 2. There will be no scribes for this class, but you can refer to Katz's notes, which I followed closely.
- Lecture 31 (April 29, 2014): CCA security using NIZKs (the Naor Yung construction). We will use the references Katz's notes -1 and 2 . Another good reference is Shoup's notes-1 and 2. There will be no scribes for this class, but you can refer to Katz's notes, which I followed closely.
Reading Material and References.
While we will not follow any particular text, the following are useful references.
Handouts.
Below are some useful handouts for the class.
Scribing: It is compulsary to scribe one lecture in the course. This involves taking down notes carefully for one lecture and carefully converting it to
LaTex. The template for scribe is
here and a good reference for Tex is
here. The scribe carries weight equal to a homework assignment.
Background:
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.