CS-NC-813: Foundations of Cryptography, Session 2014-15, Term II
Course Information
Instructor: Ashish Choudhury,office: Room No 223, email: ashish DOT choudhury AT iiitb DOT ac DOT in

Timings: Monday: 9.30 am to 11 am (Room 132)
                Wednesday: 9.30 am to 11 am (Room 132) 

Attendance: There is no compulsion on attendance. If you want to learn the subject, then you are welcome to attend the lectures. 

Course Description: This is the first course in the series of three crypto courses that I am planning to offer as an elective in the next three semesters. The 
second course in the series will be Advanced Topics in Cryptography, where using the primitives and principles covered in this first introductory course, we will design cryptographic protocols for distributed applications and advanced encryption algorithms. The final course in the series will be Cryptographic Engineering (however this is tentative), which will have a more applied flavor and where we will discusses the design techniques and methods of cryptographic hardware and embedded software.

Note: The first course in the series, namely “Foundations of Cryptography” will be a pre-requisite for the remaining two courses in the series. Moreover, anyone who is interested to do a research project with me on any topic in cryptography has to compulsorily take this first course in the series (and has to get sufficiently good grade in this course) and preferably all the three courses in the series. The idea is that by taking all the three courses in the series, a student can get a complete picture of the entire domain of cryptography (both theory and applied) and then can select a suitable topic for his/her research project.

As the name suggests, the course “Foundations of Cryptography” provides the basic paradigm and principles of modern cryptography. The focus of this course will be on definitions and constructions of various cryptographic objects. We will try to understand what security properties are desirable in such objects, how to formally define these properties, and how to design objects that satisfy the definitions.  The aim is that at the end of this course, the students are able to understand a significant portion of current cryptography research papers and standards.

The topics covered in the course will be also useful for the students who are willing to take Network Security course in the future semester, as knowledge of principles of cryptography is necessary for a better understanding of network security course. In a nut-shell, this course will build the required foundation on top of which various complex and real-world cryptographic applications are built and which will be covered in the remaining two courses in the series, along with the Network Security course.

NoteThe students should note that this course will  neither teach them how to make their computer ``secure'', nor it will teach them hacking skills. These topics are beyond the scope of this course.

The course will be divided into following two major units, which will have several topics under them. The first unit deals with symmetric-key (a.k.a private-key) cryptography, while the second unit deals with asymmetric-key (a.k.a public-key) cryptography.
  1. Unit I: Classical cryptography, perfectly-secure encryption and limitations, computational-security, pseudo-randomness and private-key encryption, stream ciphers and block ciphers, message authentication, hash functions, theoretical constructions of pseudo-random objects, private-key manageent and public-key revolution.
  2. Unit II: Number theory and cryptographic-hardness assumptions, public-key encryption: overview and various schemes, digital signatures, random-oracle model.

Textbook:There are several good books on this subject, some of which are also available online. For bulk of the course we will be using the following text: 
Students interested in Cryptography/Security are strongly encouraged to have a personal copy of this book. It is an excellent book, very well written and students will find it very useful. Apart from the above book, the following books are also handy:
  • Cryptography: Theory and Practice by Douglas Stinson, Third edition, CRC Press. Amazon.in link for purchasing.
  • Modern Cryptography: Theory and Practice by Wenbo Mao, Pearson. Flipkart link for purchasing.
  • Handbook of Applied Cryptography by Alfred Menezes, Paul Oorschot and Scott Vanstone. Available online
  • Cryptography, An Introduction by Nigel Smart. Available online.
  • Foundations of Cryptography by Oded Goldreich. Available online. This is an advanced text and students may might it slightly difficult to understand it in the first read. So I recommend to give it a try once you attain the maturity to understand abstract ideas in cryptography. 
 There is an excellent online course on cryptography available here. There are several good courses on cryptography offered at various universities, where as part of the course, lecture notes are available online. You may find them to be useful. The links for some of these course home pages are listed below:
  • Various crypto courses offered at University of Maryland by Jonathan Katz
  • Various crypto courses offered at New York University by Yevgeniy Dodis
  • Various crypto courses offered at University of California San Diego by Mihir Bellare
  • Various crypto courses offered at Cornell University by Rafael Pass
Finally I would like to stress that the best resource for the student will be their own notes, which they can take during the lectures. So they are strongly encouraged to attend the lectures regularly.

Grading: The overall grading will be done as per the following division:
  • Homework: 40 marks.
  • End-sem exam carrying 30 marks.
  • Scribe (see details below) carrying 10 marks.
  • Reading project (see details below) carrying 20 marks.
Assignments: Students will be given few homework (current estimation is 4 homework, each carrying around 10 questions) and the students need to submit their solution in hand-written form. Ideally the students should work on the problems on their own. However they can collaborate with at most two students for the problems; in that case they should clearly mention the name of the collaborators in their submission. The students are expected to try the problems on their own before searching for online solutions. I expect the students to follow perfect honesty and any failure to do so will lead an F grade. After the submission of all the homework, we will have a few brief "chalk-and-talk" sessions. Here for few selected problems, I will randomly select a student from the group of students who has solved the problem and the student has to come and explain the solution to the whole class. If the student fails to convince that he/she has indeed solved the problem then also it may affect his/her grade. So it is better to leave a particular problem if you are unable to solve it, instead of copying it from someone and then later get caught!

Students are discouraged to allow their solutions to be copied because it may happen that you work hard for the assignments but do not do well in the end-sem exam (see below) or some other components of the evaluation and end up getting a relatively lower grade compared to some one else who simply copied your assignment problems and some how managed to do better than you in the other components of the evaluation.

End Semester Exam: This will be an open notes exam where students are allowed to bring their notes. Note that students are allowed to bring only their hand-written notes and no xerox materials or book will be allowed. The problems in the exam will be based on the topics discussed in the class. Note that it is compulsory to pass in this exam in order that your assignments, scribe and project are evaluated. Failing to do so will by-default lead you to a C grade. So you need to carefully work on the assignment problems and try to avoid your solution being blindly copied by others.

Scribe: Each student will be asked to scribe for one of the lectures. The student scribing for a particular lecture will be announced at the beginning of the lecture (it will be randomly selected by me). The deadline for submitting the scribe for a lecture will be the midnight of the Sunday of the week during which the lecture was held. The idea behind the scribe is that the students become more active and interactive during the class and at the same time, we will have a record of all the lecture notes in electronic form at some place, so that any one can access it. This will also be a good learning experience for the students. Writing a scribe will definitely help the students to express their own views about the lecture. I will strongly encourage the students to consult various sources, apart from the discussion that we will have in the class, before writing a scribe. Imagine that you are writing a text-book chapter and so you would definitely want the audience to understand the topic as easily as possible. So try to add your explanation, examples, historical notes, additional references, etc.

The scribe need to be compulsorily prepared using Latex. There are numerous benefits of learning Latex on a long term basis. You may look at the sample scribe and the corresponding tex and style file below. All the scribes compulsorily need to be prepared using this style file to ensure uniformity. There are various online tutorials, like this to learn Latex. Note that after the initial submission, you can revise your scribe as many times as you want till the last lecture. You are encouraged to periodically look at the scribe of other students and if you believe that there is a scope of improving your scribe then you are allowed to do that. You are also encouraged to comment about the scribe of the other students through the group forum.

Reading Project: Earlier I though of giving short practical projects. But I think due to lack of time, I am scrapping this idea. Instead we will have reading projects. The idea is the following: in the class, I am unable to cover several interesting topics due to lack of time. Below I am giving a list of such topics. We will form groups of three and each group has to select a topic and give a combined presentation of 60 minutes before the entire class; this roughly includes 45 minutes of technical presentation (approx 15 mins per group member) plus additional 15 mins for queries from the audience. 

Your presentation will be judged on various factors (such as contents, your way of explaining things, the depth and breadth of the topic you are able to cover within the allotted time, the way you handle the questions from the audience, etc) and you should try to make it as crisp as possible. Simply do not try to put too many things in your slides, as a result of which the audience may not get anything. So you need to maintain a proper balance of what to put in the slides. Imagine what you will do if you are going to teach a class a particular assigned topic. Along with each topic, some references are also given. However it is not mandatory to base your presentation based on those references. Do not think that in your project I am asking you to cover a topic given in the corresponding references. Also do not have this impression that you need to put each and every thing about a given topic from the corresponding references in your presentation.  

The students who are doing SE projects with me should give a 40 min presentation on the topic they are working on (based on the above guidelines) and they need not have to select any topic from the following list.
The list of topics is given in the following table, along with the group details which is assigned a particular topic. The tentative schedule for the presentations is also mentioned. Since the three groups for SE project are working on somewhat related topics, there will be a 120 min combined slot for the three groups, to avoid repetition. I am hoping that we will be left with one day of regular lecture (after completing the syllabus and discussing the assignment questions) and so this combined presentation is likely to be scheduled during one of the regular lectures. Attendance is compulsory during the presentations, otherwise you will not be allowed to give your presentation.

One obvious choice for the presentations is to use power-point. However handling math formulas is really challenging in ppt. There is an alternative called beamer for preparing presentations (pdf) involving mathematics. The problem with beamer is that getting good animations becomes really difficult compared to ppt; also the ppt presentations look more appealing (this is my personal opinion) and there are ways to get the same kind of animations and look in beamer as in ppt. In fact in the theoretical computer science community, the trend is to go for beamer presentation. However these are just recommendations and there will be no discrimination in the evaluation based on whether you are using beamer of ppt for the presentation.

 S. No
                                                Topic and Description
                         Group Details and Presentation
    1Differential Cryptanalysis: This is a powerful cryptanalysis method proposed in late 90s and now considered a standard test for judging any newly proposed block cipher design. You need to understand this method and how it is applied to DES.

Relevant sources:
  •  Eli Biham and Adi Shamir. Differential Cryptanalysis of  DES-like Cryptosystems. J. Cryptology 4(1): 3-72 (1991).
  • Howard M. Hey. A Tutorial on Linear and Differential Cryptanalysis
 Deepshree Ravindran, Sankalp Johri and Shashank Gupta.

Tentative schedule: 01/05/2015, 9 am
    2Attacks on RC4: Recently few attacks are reported in RC4 when deployed in TLS and WPA. This is very interesting, as RC4 till now was believed to be secure. Your goal will be to understand the attack.

Relevant paper:
  •  Nadhem J. AlFardan, Daniel J. Bernstein, Kenneth G. Paterson, Bertram Poettering and Jacob C. N. Schuldt. On the security of RC4 in TLS and WPA. Usenix Security, 2013.
 Harshad Gadkari, Rajendrakumar Premnarayan and Sabyasachi Mallick

Tentative schedule: 11/04/2015, 10 am
   3Finding Collisions in the MD5 Algorithm: MD5 is one of the important practically used hash function. However, in a breakthrough work, a collision was explicitly demonstrated in MD5. Your goal will be to understand the technique used to find the collision.

Relevant paper:
  •  Xiaoyun Wang and Hongbo Yu. How to Break MD5 and Other Hash Functions. Eurocrypt 2005.
 Anand Tirthgirikar, Abhishek Joshi and Suraj Munale

Tentative schedule: 11/04/2015, 11 am
   4Paillier Encryption Scheme: In the class, we will discuss only two public-key cryptosystems, namely RSA and El Gamal. However, there are several other well known public-key cryptosystems, based on variety of assumptions. And Paillier encryption scheme is one of them. You need to understand the cryptosystem and its properties.

The relevant source for this project is chapter 13 of the Katz-Lindell book (2nd edition).
 Arun K, Sarada S and Srijith V 

Tentative schedule: 11/04/2015, 12 pm
   5Rabin Encryption Scheme: The goal of this project is similar to the previous once, except that now you need to consider the Rabin cryptosystem.

The relevant source for this project is chapter 13 of the Katz-Lindell book (2nd edition).
 Theegala Harika Rao, Venkata Sushmitha Punati and Lukshya Madan

Tentative schedule: 01/05/2015, 2 pm
   6
Algorithms for factoring: Factoring assumption is one of the popular assumptions used in public-key cryptosystems. In the literature, several attempts have been made to solve this problem, but no polynomial time algorithm could be reported. However there are super-polynomial time algorithm for solving this problem. The goal of this project will be to look into these algorithms, such as Pollard's p-1 algorithm, Pollard's Rho algorithm and the Quadratic Sieve algorithm

The relevant source for this project is chapter 9 of the Katz-Lindell book (2nd edition).
 Rajan Padalia, Kaustav Sen and Apoorv Shrivastava 

Tentative schedule: 25/04/2015, 12 pm
   7Algorithms for computing Discrete Logarithms: The goal of this project will be similar to the previous one, except that now you need to study algorithms for solving the Discrete-log problem, such as Pohlig-Hellman algorithm, Baby-step/Giant-step algorithm and Index calculus algorithm.

The relevant source for this project is chapter 9 of the Katz-Lindell book (2nd edition).
 Sandesh Prabhu, T. Divyasree and Robert Fels

Tentative schedule: 25/04/2015, 2 pm
   8Provably-secure PRGs and Next bit predictors: in the class we have seen a definition of PRG based on indistinguishability game. Somewhat different definition is in terms of the next-bit predictor, which intuitively demands that even if you have seen the first "few" output bits of a number generator, you should not be able to able to predict the next output bit, except with probability negligibly better than 1/2. Your goal will be to understand the next-bit predictor based definition of PRG and also the famous BBS (Blum-Blum-Shub) PRG, which is provably-secure and satisfies the definition based on next bit predictor.

Relevant source: Chapter 8 of Douglas Stinson book on Cryptography (3rd edition)
 Nishant Goyal, Byomkesh Jha and Jyothi Prakash

Tentative schedule: 25/04/2015, 9 am
   9Elliptic Curves: Groups are important algebraic structures used in any public-key cryptosystem. In cryptography, two groups are very fundamental. The first group is the set of integers modulo N. Another important group is based on the set of points on elliptic curves. For practical deployment of public-key crypto algorithms, the latter group is the popular choice. You need to understand the properties of groups based on elliptic curves and their significance from the cryptographic perspective.

Relevant source: chapter 8 of the Katz-Lindell book (2nd edition)
 Karthik S, Reijul Sachdev and Yashvanth Mohan Kondi

Tentative schedule: 25/04/2015, 10 am
  10Information-theoretic MACs: message-authentication codes (MAC) are important crypto primitives used for message authentication and ensuring message integrity. In the class, we will discuss MACs based on PRFs, which are computationally-secure. However, we also have information-theoretic (unconditionally-secure) MACs, which remains secure even against computationally-unbounded attackers. You need to understand such MACs.

Relevant source: Chapter 4 of the Katz-Lindell book (2nd edition)
 G.Keerthana, M.Deepa and N.Hanisha

Tentative schedule: 01/05/2015, 10 am
  11Cramer-Shoup Cryptosystem: the only known CCA-secure public-key cryptosystem based on Diffie-Hellman problems and in the "standard" model (that is without random oracles) is due to Cramer and Shoup. The goal of this project will be to understand the scheme and its security properties.

Relevant source: the description of the scheme is available in various lecture notes for cryptography. For example:
  •  http://www.cs.princeton.edu/courses/archive/fall07/cos433/lec22.pdf
  •  http://www.cs.umd.edu/jkatz/gradcrypto2/NOTES/lecture10.pdf
  •  Slides on the same topic by Benny Applebaum
 Pawan Dhananjay, Neha Tarigopula and Rahul Ghosh 

Tentative schedule: 25/04/2015, 11 am


Facebook Page: I strongly believe that technology can be a great asset if used properly. Social network has changed our lives (both positively and negatively) in a tremendous way. I think that it is a very powerful medium to reach out to the audience. We have a Facebook page for this course and if you are interested you can join the group.

Source for Long-term ProjectsThis section will be useful to you if you are interested to do a "long-term" project with me. The first thing you should decide is whether you want to do a research project (which involves mostly solving some open problem in the literature) or some applied project (where there is already some known theory and you need to make it practical). Once you decide your flavor then you need to find out the source from where you can find out the latest trend in cryptography and security. The best source for this are the "top" conferences in the area of cryptography and security, where the best research results are published in these areas. Here I will provide a list of few top conferences in crypto and security (this may not be the exhaustive list); these conferences are held annually. So you can just browse through the various papers published in these conferences during various years and see if there is anything which excites you. It will be very difficult to understand the topics at the beginning, but slowly and slowly as we learn various topics in this course, you will find it relatively easy to understand the results in these paper. You need not have to go through the whole paper, just the abstract and introduction should be sufficient to have a grasp of what exactly the paper is all about. The whole idea behind this exercise is that instead of me forcing something on you, it will be best if you can come up with your own idea for some project. And the best source for it is to have a look at the papers published in these venues. You need not have to start the process right now, you can start it slowly, as we advance through our current course and it should be periodic.

Category I: List of top venues for publishing applied crypto results:
3. Privacy Enhancing Technologies Symposium. Homepage for this year's event.
6. NDSS Symposium. Website: http://www.internetsociety.org/events/ndss-symposium
7. Real world cryptography workshop. Homepage for this year's event.

Category II: List of top venues for publishing results in hardware security and symmetric-key primitives:
1. Fast Software Encryption. Website: http://www.iacr.org/meetings/fse/
2. Workshop on Cryptographic Hardware and Embedded Systems. Website: http://www.chesworkshop.org/
3. Smart card research and advanced application conference. Homepage for this year's event: http://cedric.cnam.fr/events/cardis/

Category III: List of top venue for publishing (theoretical) results in all areas of cryptology
1. CRYPTO, Eurocrypt and Asiacrypt (3 flagship events). Homepage for these conferences. 
2. TCC and PKC. Homepage for this year's event are here and here

Apart from this, here is the list of some other annual cryptology conferences. The IMTech students who want to do their final year thesis with me should periodically check the above list of conferences to find some interesting topics for their thesis. To do a good thesis, you need to plan in advance. 

Few Currently Available Applied Projects (Specially for M. Tech students registered in this course for their software engineering project): The proposed projects are really advanced and ideally I wanted to offer them during the second course of my proposed series, namely the Advanced Cryptography course. All the 5 proposed projects are based on some recent and advanced research topics and are highly practically motivated. For each of these projects, you need to read few advanced research papers. None of the topics in these research papers will be discussed in our current course and you have to work on your own to understand them. However I believe that once you have some basic understanding in crypto, you should not find it difficult to understand these advanced concepts, provided you work hard. If some MTech student opt to take any of the projects, then there might be a possibility to even present a "small" part of the project as the project component for the foundation course in cryptography. However this is optional and it completely depends upon whether we can identify a small subset of the deliverable of the SE project for the foundation course in cryptography.

  1. Oblivious Data-structures for MPCWe all know how to efficiently implement basic abstract data types (ADT) like arrays, dictionaries, priority queues. We often require these ADTs to implement various higher lever applications, such as graph algorithms. Now consider a scenario where you have to implement these ADTs in a distributed and secure fashion. Specifically consider a scenario where an array or a dictionary or a priority queue is not available at a single "source" but rather shared among multiple sources, say n sources such that only when the n sources combine their "part" of the ADT, they will have access to the full ADT. In such a scenario we have to implement various ADTs in a distributed and secure fashion, such that only the end result of the operations will be revealed and nothing else. Using these distributed and secure ADTs we can then design secure and distributed graph theoretic algorithms, such as Dijkstra's algorithm: consider a scenario where the structure of the graph is not public, but rather shared among n entities; we just know the number of vertices and number of edges in the graph. We would still like to run the Dijkstra's algorithm in a distributed and secure fashion. These kind of algorithms will be useful in sensitive applications where we would like to keep the underlying network topology to be hidden but still want to carry out normal graph theoretic algorithms.                                                                                                                                                                                                                                                                                                                                                                           Reference: Efficient, Oblivious Data Structures for MPC by Marcel Keller and Peter Scholl. Published in Asiacrypt 2014. Paper available  here. http://eprint.iacr.org/2014/137. 
  2. Privacy-preserving Fingerprint IdentificationIn a typical fingerprint identification system, we have a server maintaining a huge database of some fingerprint readings and a client who submits some candidate fingerprint reading to the server for identification. Can we run the same application in a privacy-preserving fashion in the sense that server does not learn anything about the candidates submitted by the client and at the same time client does not learn anything about the server database except the fact whether the submitted candidates belong to the database or not. The goal of this project will be to carry out the above task.                                                                                                                                                                                                                                                                                                                                                                                                           Reference: Efficient Privacy-preserving Biometric Identification by Yan Huang, Lior Malka, David Evans and Jonathan Katz. Published in NDSS 2011.
  3. Privacy-preserving Face RecognitionIn a typical face recognition system, we have a server maintaining a huge database of face images and a client who submits some candidate face image to the server for identification. Can we run the same application in a privacy-preserving fashion in the sense that server does not learn anything about the candidates submitted by the client and at the same time client does not learn anything about the server database except the fact whether the submitted candidates belong to the database or not. The goal of this project will be to carry out the above task. Reference: Efficient Privacy-preserving Face Recognition by Ahmad-Reza Sadeghi, Thomas Schneide and Immo Wehrenberg. Published in ICISC 2009. Paper available here.
  4. Secure 2-party AESAES is one of the most widely used block cipher. It takes a secret key as input and a message block to be encrypted and generates the ciphertext corresponding to the message, without disclosing anything about the key or the message. Typically the key and the message to be encrypted are available with a single entity. Now consider a scenario where we have two parties, one holding the secret key and the other holding the message to be encrypted. We want to design a protocol such that at the end of the protocol, the second party learns the encryption of the message (and no information about the key) while the first party learns nothing about the encrypted message. The goal of this project will be to implement such a protocol.                                                                                                                                                                                                                                                                                                                                                                                                                                                                     Reference: Faster Secure Two-Party Computation Using Garbled Circuits by Yan Huang, David Evans, Jonathan Katz and Lior Malka. Published in Usenix 2011.
  5. Privacy-preserving Applications on SmartphonesSmartphones are becoming popular day by day. Smartphones are slowly and slowly becoming essential platform for several privacy-preserving applications. Unfortunately the standard privacy-preserving protocols are highly computation expensive and cannot be executed on less powerful devices like a smart phone. The goal of this project will be to implement efficient privacy-preserving MPC protocols for smartphone.                                                                                                                                                                                                                                                                                                                                                                                                                                          Reference: Privacy-Preserving Applications on Smartphones by Yan Huang, Peter Chapman and David Evans. Published at Hotsec 2011.

Course Schedule, Scribes and Slides 
This section will be populated as the course progresses. 

 Lecture No      DateTitle  Overview, slides and scribe
15 JanuaryCourse Overview and IntroductionIn this lecture, we will have a brief overview of the course. We will see that the two core/central problems in cryptography are (i) key-agreement and (ii) secure and authentic communication. We will also see that apart from these two basic problems, the world of cryptography includes several fascinating applications, which we will discuss in the second course in the series. We will begin our technical discussion on the syntax of private-key encryption, Kerckhoff's principle and various kind of attack scenarios against cryptographic algorithms.

The slides for this lecture are available here. The scribe for this lecture is available here. The tex and style files are here and here. Students are expected to prepare scribes along the same line.
         2
 7 January
Historical Ciphers, their Cryptanalysis and Lessons LearntIn this lecture, we discussed some historical ciphers and how badly they were broken, even though considered to be secure. We discussed the non-rigorous approach to security followed in classical cryptography and the rigorous approach used in modern cryptography, based on precise security definitions, assumptions and rigorous security proofs.The slides for this lecture are available here. The scribe for this lecture is available here.
         3 12 January
 Perfectly-secure Encryption
In this lecture, we discussed perfectly-secure encryption, which is the strongest notion of security. We considered various equivalent formulation of the definition of perfectly-secure encryption. We also saw one candidate scheme achieving perfect security, namely one-time pad (OTP). However OTP suffers from two drawbacks, namely the secret key should be of the same size as the message size and secondly key cannot be reused.The slides for this lecture are available here. The scribe for this lecture is available here.
         4 19 JanuaryComputational Security and Modern CryptographyIn this lecture we continued our discussion on perfect-security and saw the necessary conditions that any perfectly-secure scheme should satisfy. These conditions are infeasible to achieve and so modern cryptographic schemes has to take a different approach, namely that of computational security, where security is guaranteed only against a computationally-bounded attacker and where the attacker is allowed to break the scheme with a "very small" probability. We discussed that in order to get rid of the limitations imposed by perfect-security, we necessarily need to bring these two relaxations in any practical cryptographic scheme. We discussed how to mathematically formulate the notion of computationally-bounded attacker and very small probability. Some of the slides were used from the previous lectures while the remaining slides for this lecture are available here. The scribe for the lecture is available here.
         5 21 JanuaryComputational Indistinguishability and PseudorandomnessIn this lecture, we continued our discussion on computational security and formulated the first basic definition of computational security, which ensures security against a PPT  eavesdropper carrying a ciphertext-only attack. We then discussed the notion of pseudorandomness, which is a central concept for achieving computational security. Some of the slides for this lecture were from the previous lecture's slides while the remaining slides for this lecture are available here. The scribe for this lecture is available here.
         6 28 JanuaryIndistinguishable Encryptions using Pseudorandom Generators In In this  lecture we discussed that how using PRGs, one can design a symmetric cipher which provides indistinguishable encryptions. The advantage of this approach is that we can use a very short "true randomness" to encrypt a large message, which is not possible via a perfectly-secure encryption scheme. We then saw that even though indistinguishable encryption is a reasonable security notion, in reality, we require a more stronger notion of security, where multiple messages are encrypted using the same short key. Such a stronger security notion is difficult to achieve via PRGs and so we require a even more stronger primitive. The slides for this lecture are from the previous lecture's slides. The scribe for this lecture is available here.
         728 January (back-up lecture for 14 January)Chosen-plaintext Attack and Pseudorandom FunctionIn this lecture, we discussed a more powerful attack scenario than ciphertext-only attack. The attack scenario is called chosen-plaintext attack, where a PPT eavesdropper has access to encryptions of messages of its choice and still we would like to obtain indistinguishable encryptions. We discussed how to mathematically formulate the security against such an attack. We then saw pseudorandom function (PRF), which is a more powerful primitive  than a PRG and which helps us to achieve indistinguishable encryption against CPA attack. The slides for this lecture are available here. The scribe for this lecture is available here.
         8 2 FebruaryBlock ciphers and their mode of operationIn this lecture, we discussed how to design efficient CPA-secure ciphers from PRFs for arbitrary-length messages, by using a PRF in varieties of ways; these varieties of ways define what are known as modes of operations of block ciphers. Block ciphers are practical instantiation of PRF. The slides for this lecture are available here. The scribe is available here.
        9 4 FebruarySecurity of CTR Mode of Operation of Block Cipher, Modes of Operations for Stream Ciphers and Practical Constructions of Stream Ciphers
In this lecture we formally proved the security of CTR mode of operation of block ciphers. We then discuss stream ciphers and their modes of operations. Stream ciphers are practical instantiations of PRGs. We also started looking at some practical constructions of stream ciphers. The slides for this lecture are available here and here. The scribe for this lecture is available here.
       10 9 FebruaryPractical Constructions of Stream Ciphers and Block CiphersIn this lecture we continued our discussion on the practical construction of the stream ciphers. We then saw the practical construction of block ciphers. In that context, we discussed the substitution-permutation networks (SPN), a key ingredients used in the design of modern block ciphers. ciphers. The slides for this lecture are available here. The scribe is here.
       11 11 February AES and DESIn In this lecture, we discussed Fiestel networks, which is another important component used in the design of modern block ciphers. We then looked into the details of DES (and its variants), followed by a brief overview of AES; these are the two most popular practical block ciphers. The slides for this lecture are available here. The scribe is here.
      12 16 FebruaryTheoretical Constructions of Symmetric-key Primitives - Part IIn this lecture, we started our discussion on provably-secure construction of symmetric-key primitives. For this we first defined the notion of one-way function (OWF), which is a fundamental concept in theoretical cryptography. We also defined the notion of hard-core predicate, which is another fundamental concept. Using these notions we saw a construction of a provably-secure PRG with minimal expansion factor; namely a PRG which expands an n-bit seed to an n+1-bit output. The slides for this lecture are available here. The scribe is available here.
      13 18 FebruaryTheoretical Constructions of Symmetric-key Primitives - Part IIIn this lecture we continued our discussion on provably-secure construction of symmetric-key primitives. We first discussed how to increase the expansion factor of the PRG discussed in the previous lecture by a polynomial factor. We then saw how to construct provably-secure PRF from PRGs followed by provably-secure construction of PRP and SPRP. The proof for these constructions are given via hybrid arguments, which is a very important and fundamental proof strategy for proving security of advanced and complex cryptographic primitives. The slides for this lecture are available here. The scribe is available here.
       14 11 March CCA SecurityIn this lecture we introduced a new attack scenario where apart from the encryption oracle service, an attacker also gets access to decryption oracle service. This models a malicious attacker, who apart from eavesdropping can also maliciously change the ciphertext contents or can inject its own packets. To deal with such an attack scenario, we introduce a new security notion called CCA-security, which is more powerful than CPA-security. We also discussed the notion of message integrity and authentication and saw the construction of fixed-length and arbitrary-length message authentication codes (MAC). The slides for this lecture are available here. The scribe is here.
        15  16 March
Authenticated Encryption and Hash FunctionsIn this lecture we considered authenticated encryption, which is an encryption mechanism providing privacy as well as integrity/authenticity simultaneously. Hence it is the right form of symmetric-key encryption to be used in practice. We saw that authenticated encryption also generically implies CCA-security. We  discussed  how to get authenticated encryption by combining CPA-secure cipher with a secure MAC. We then started our discussion on hash functions, which is another important cryptographic primitive, used both the symmetric-key as well as asymmetric-key world.The slides for this lecture are available here. The scribe is here.
        16  18 MarchBirthday Attacks on Hash Functions, Applications of Hash Functions and Introduction to Number TheoryIn this lecture, we discussed birthday attacks, which is a class of generic attacks against any hash function design. We also looked into some of the cryptographic applications of hash functions. With this we ended our discussion on symmetric-key cryptography and started moving towards public-key cryptography. Since (algorithmic) number theory is very important for public-key cryptography, we started our discussion on number theory. The slides for this lecture are available here. The scribe is here.
       17 23 MarchNumber Theory Part IIIn this lecture, we continued our discussion of number theory. We discussed the notion of groups, sub-groups, order of a group and cyclic groups, which play crucial role in the design of public-key encryption schemes. The slides are available here. The scribe is here.
      18  25 MarchCryptographic Assumptions in Cyclic Groups and Diffie-Hellman Key Exchange ProtocolIn this lecture, we discussed the notion of cyclic groups. We also discussed prime-order groups and their importance in cryptography. We saw one candidate prime-order group, namely the sub-group consisting of quadratics residues modulo a prime. We then discussed the various hard number-theoretic problems in Cyclic groups, namely the Discrete Logarithm (DLog) problem and the two famous Diffie-Hellman problems, namely the Computational Diffie-Hellman (CDH) and Decisional Diifie-Hellman (DDH) problem and discussed the relationship among DLog, CDH and DDH problem. We then discussed the Diffie-Hellman key-exchange protocol and its security based on the DDH assumption. We also discussed the security requirements of any key-exchange protocol. We finally saw various active attacks against the Diffie-Hellman key-exchange protocol. The slides for this lecture are the same as for the previous lecture. The scribe is here.
      19 30 MarchPublic-key Encryption: CPA-security and Constructions Based on Diffie-Hellman ProblemsIn this lecture started our discussion on public-key cryptography; we saw the advantages and disadvantages of public-key cryptography over private-key cryptography. We discussed the CPA-security for public-key encryptions and observed that in the public-key world, EAV-security is equivalent to CPA-security; this is unlike the private-key world. We then discussed one of the most popular public-key encryption scheme  due to El Gamal based on Diffie-Hellman problems in the cyclic groups. The slides for this lecture are available here. The scribe is here.
      20 1 AprilHybrid El Gamal Encryption and RSA Public-key EncryptionIn this lecture, we discussed Hybrid El Gamal encryption scheme which combines Diffiei-Hellman key-exchange protocol and any EAV-secure symmetric-key encryption scheme. The resultant encryption scheme is highly efficient and its amortized cost is al most the same as that of the underlying symmetric-key encryption scheme. We proved the security of the scheme under Hash Diffie-Hellman (HDH) assumption. We then started our discussion on another public-key encryption scheme, namely the RSA encryption scheme. We saw that the basic RSA fails to provide CPA-security and so we discussed some of the methods to make RSA CPA-secure. The slides for this lecture are available here. The scribe is here.
      21 6 AprilCCA-security for Public-key Encryption and Generic Constructions in the Random Oracle Model (ROM)In this lecture, we discussed CCA attacks on public-key encryption schemes and saw that both El Gamal as well as text-book RSA fail to provide CCA-security. We then discussed a general paradigm for constructing efficient CPA and CCA-secure hybrid public-key encryption schemes. Towards this, we introduced two important and fundamental notions, namely of one-way functions with trapdoor and random-oracle model. The slides for this lecture are from the previous lecture. The scribe is here.
      22 8 AprilDigital Signatures - IIn this lecture, we discussed digital signatures, which are the analogue of MAC in the public-key setting and provides authentication and integrity. We discussed the properties of MAC and signatures. We also discussed the security notion for digital signatures. We then saw the textbook RSA signature, which is highly insecure. This was followed by the discussion on full domain RSA hash signatures, which is secure in ROM. We also discussed about Schnorr identification scheme based on DLog problem. The slides for this lecture are available here. The scribe is here.
      23 15 AprilDigital Signatures - II and Concluding RemarksIn this lecture, we discussed how to convert Scnorr's identification scheme into a digital signature scheme using the Fiat-Shamir heuristic. We then discussed the practical applications of digital signatures. We finally concluded by briefly discussing the SSL/TLS protocol and the various cryptographic primitives used in the protocol. The slides for this lecture are from the previous lecture. The scribe is here.
      24 20 AprilAssignment I Solution Discussion
We discussed the solutions for assignment 1. The assignment is here and the scribe discussing the sample solutions is here.
      25 22 AprilAssignment 2 Solution DiscussionWe discussed the solutions for assignment 2. The assignment is here and the scribe discussing the sample solutions is here.
      26 27 AprilAssignment 3 Solution DiscussionWe discussed the solutions for assignment 3. The assignment is here.