CSNC813: Foundations of Cryptography, Session 201415, 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 prerequisite 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 nutshell, this course will build the required foundation on top of which various complex and realworld cryptographic applications are built and which will be covered in the remaining two courses in the series, along with the Network Security course.
Note: The 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 symmetrickey (a.k.a privatekey) cryptography, while the second unit deals with asymmetrickey (a.k.a publickey) cryptography.  Unit I: Classical cryptography, perfectlysecure encryption and limitations, computationalsecurity, pseudorandomness and privatekey encryption, stream ciphers and block ciphers, message authentication, hash functions, theoretical constructions of pseudorandom objects, privatekey manageent and publickey revolution.
 Unit II: Number theory and cryptographichardness assumptions, publickey encryption: overview and various schemes, digital signatures, randomoracle 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.
 Endsem 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 handwritten 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 "chalkandtalk" 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 endsem 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 handwritten 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 bydefault 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 textbook 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 powerpoint. 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
 1  Differential 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 DESlike Cryptosystems. J. Cryptology 4(1): 372 (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  2  Attacks 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  3  Finding 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  4  Paillier Encryption Scheme: In the class, we will discuss only two publickey cryptosystems, namely RSA and El Gamal. However, there are several other well known publickey 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 KatzLindell book (2nd edition).
 Arun K, Sarada S and Srijith V
Tentative schedule: 11/04/2015, 12 pm  5  Rabin 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 KatzLindell 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 publickey cryptosystems. In the literature, several attempts have been made to solve this problem, but no polynomial time algorithm could be reported. However there are superpolynomial time algorithm for solving this problem. The goal of this project will be to look into these algorithms, such as Pollard's p1 algorithm, Pollard's Rho algorithm and the Quadratic Sieve algorithm
The relevant source for this project is chapter 9 of the KatzLindell book (2nd edition).
 Rajan Padalia, Kaustav Sen and Apoorv Shrivastava
Tentative schedule: 25/04/2015, 12 pm  7  Algorithms 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 Discretelog problem, such as PohligHellman algorithm, Babystep/Giantstep algorithm and Index calculus algorithm.
The relevant source for this project is chapter 9 of the KatzLindell book (2nd edition).
 Sandesh Prabhu, T. Divyasree and Robert Fels
Tentative schedule: 25/04/2015, 2 pm  8  Provablysecure 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 nextbit 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 nextbit predictor based definition of PRG and also the famous BBS (BlumBlumShub) PRG, which is provablysecure 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  9  Elliptic Curves: Groups are important algebraic structures used in any publickey 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 publickey 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 KatzLindell book (2nd edition)
 Karthik S, Reijul Sachdev and Yashvanth Mohan Kondi
Tentative schedule: 25/04/2015, 10 am  10  Informationtheoretic MACs: messageauthentication 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 computationallysecure. However, we also have informationtheoretic (unconditionallysecure) MACs, which remains secure even against computationallyunbounded attackers. You need to understand such MACs.
Relevant source: Chapter 4 of the KatzLindell book (2nd edition)
 G.Keerthana, M.Deepa and N.Hanisha
Tentative schedule: 01/05/2015, 10 am  11  CramerShoup Cryptosystem: the only known CCAsecure publickey cryptosystem based on DiffieHellman 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 Longterm Projects: This section will be useful to you if you are interested to do a "longterm" 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/ndsssymposium 7. Real world cryptography workshop. Homepage for this year's event.
Category II: List of top venues for publishing results in hardware security and symmetrickey primitives: 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.
 Oblivious Datastructures for MPC: We 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.
 Privacypreserving Fingerprint Identification: In 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 privacypreserving 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 Privacypreserving Biometric Identification by Yan Huang, Lior Malka, David Evans and Jonathan Katz. Published in NDSS 2011.
 Privacypreserving Face Recognition: In 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 privacypreserving 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 Privacypreserving Face Recognition by AhmadReza Sadeghi, Thomas Schneide and Immo Wehrenberg. Published in ICISC 2009. Paper available here.
 Secure 2party AES: AES 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 TwoParty Computation Using Garbled Circuits by Yan Huang, David Evans, Jonathan Katz and Lior Malka. Published in Usenix 2011.
 Privacypreserving Applications on Smartphones: Smartphones are becoming popular day by day. Smartphones are slowly and slowly becoming essential platform for several privacypreserving applications. Unfortunately the standard privacypreserving 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 privacypreserving MPC protocols for smartphone. Reference: PrivacyPreserving 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  Date  Title 
Overview, slides and scribe 
1  5 January  Course Overview and Introduction  In this lecture, we will have a brief overview of the course. We will see that the two core/central problems in cryptography are (i) keyagreement 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 privatekey 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 Learnt  In
this lecture, we discussed some historical ciphers and how badly they were broken, even though considered to be secure. We discussed the nonrigorous 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
 Perfectlysecure Encryption
 In this lecture, we discussed perfectlysecure encryption, which is the strongest notion of security. We considered various equivalent formulation of the definition of perfectlysecure encryption. We also saw one candidate scheme achieving perfect security, namely onetime 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 January  Computational Security and Modern Cryptography  In this lecture we continued our discussion on perfectsecurity and saw the necessary conditions that any perfectlysecure 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 computationallybounded 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 perfectsecurity, we necessarily need to bring these two relaxations in any practical cryptographic scheme. We discussed how to mathematically formulate the notion of computationallybounded 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 January  Computational Indistinguishability and Pseudorandomness  In 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 ciphertextonly 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 January  Indistinguishable 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 perfectlysecure 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.
 7  28 January (backup lecture for 14 January)  Chosenplaintext Attack and Pseudorandom Function  In this lecture, we discussed a more powerful attack scenario than ciphertextonly attack. The attack scenario is called chosenplaintext 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 February  Block ciphers and their mode of operation  In this lecture, we discussed how to design efficient CPAsecure ciphers from PRFs for arbitrarylength 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 February  Security 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 February  Practical Constructions of Stream Ciphers and Block Ciphers  In 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 substitutionpermutation 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 DES  In 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 February  Theoretical Constructions of Symmetrickey Primitives  Part I  In this lecture, we started our discussion on provablysecure construction of symmetrickey primitives. For this we first defined the notion of oneway function (OWF), which is a fundamental concept in theoretical cryptography. We also defined the notion of hardcore predicate, which is another fundamental concept. Using these notions we saw a construction of a provablysecure PRG with minimal expansion factor; namely a PRG which expands an nbit seed to an n+1bit output. The slides for this lecture are available here. The scribe is available here.  13  18 February  Theoretical Constructions of Symmetrickey Primitives  Part II  In this lecture we continued our discussion on provablysecure construction of symmetrickey 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 provablysecure PRF from PRGs followed by provablysecure 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 Security  In 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 CCAsecurity, which is more powerful than CPAsecurity. We also discussed the notion of message integrity and authentication and saw the construction of fixedlength and arbitrarylength message authentication codes (MAC). The slides for this lecture are available here. The scribe is here.  15  16 March
 Authenticated Encryption and Hash Functions  In 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 symmetrickey encryption to be used in practice. We saw that authenticated encryption also generically implies CCAsecurity. We discussed how to get authenticated encryption by combining CPAsecure cipher with a secure MAC. We then started our discussion on hash functions, which is another important cryptographic primitive, used both the symmetrickey as well as asymmetrickey world.The slides for this lecture are available here. The scribe is here.  16  18 March  Birthday Attacks on Hash Functions, Applications of Hash Functions and Introduction to Number Theory  In 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 symmetrickey cryptography and started moving towards publickey cryptography. Since (algorithmic) number theory is very important for publickey cryptography, we started our discussion on number theory. The slides for this lecture are available here. The scribe is here.  17  23 March  Number Theory Part II  In this lecture, we continued our discussion of number theory. We discussed the notion of groups, subgroups, order of a group and cyclic groups, which play crucial role in the design of publickey encryption schemes. The slides are available here. The scribe is here.  18  25 March  Cryptographic Assumptions in Cyclic Groups and DiffieHellman Key Exchange Protocol  In this lecture, we discussed the notion of cyclic groups. We also discussed primeorder groups and their importance in cryptography. We saw one candidate primeorder group, namely the subgroup consisting of quadratics residues modulo a prime. We then discussed the various hard numbertheoretic problems in Cyclic groups, namely the Discrete Logarithm (DLog) problem and the two famous DiffieHellman problems, namely the Computational DiffieHellman (CDH) and Decisional DiifieHellman (DDH) problem and discussed the relationship among DLog, CDH and DDH problem. We then discussed the DiffieHellman keyexchange protocol and its security based on the DDH assumption. We also discussed the security requirements of any keyexchange protocol. We finally saw various active attacks against the DiffieHellman keyexchange protocol. The slides for this lecture are the same as for the previous lecture. The scribe is here.  19  30 March  Publickey Encryption: CPAsecurity and Constructions Based on DiffieHellman Problems  In this lecture started our discussion on publickey cryptography; we saw the advantages and disadvantages of publickey cryptography over privatekey cryptography. We discussed the CPAsecurity for publickey encryptions and observed that in the publickey world, EAVsecurity is equivalent to CPAsecurity; this is unlike the privatekey world. We then discussed one of the most popular publickey encryption scheme due to El Gamal based on DiffieHellman problems in the cyclic groups. The slides for this lecture are available here. The scribe is here.  20  1 April  Hybrid El Gamal Encryption and RSA Publickey Encryption  In this lecture, we discussed Hybrid El Gamal encryption scheme which combines DiffieiHellman keyexchange protocol and any EAVsecure symmetrickey encryption scheme. The resultant encryption scheme is highly efficient and its amortized cost is al most the same as that of the underlying symmetrickey encryption scheme. We proved the security of the scheme under Hash DiffieHellman (HDH) assumption. We then started our discussion on another publickey encryption scheme, namely the RSA encryption scheme. We saw that the basic RSA fails to provide CPAsecurity and so we discussed some of the methods to make RSA CPAsecure. The slides for this lecture are available here. The scribe is here.  21  6 April  CCAsecurity for Publickey Encryption and Generic Constructions in the Random Oracle Model (ROM)  In this lecture, we discussed CCA attacks on publickey encryption schemes and saw that both El Gamal as well as textbook RSA fail to provide CCAsecurity. We then discussed a general paradigm for constructing efficient CPA and CCAsecure hybrid publickey encryption schemes. Towards this, we introduced two important and fundamental notions, namely of oneway functions with trapdoor and randomoracle model. The slides for this lecture are from the previous lecture. The scribe is here.  22  8 April  Digital Signatures  I  In this lecture, we discussed digital signatures, which are the analogue of MAC in the publickey 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 April  Digital Signatures  II and Concluding Remarks  In this lecture, we discussed how to convert Scnorr's identification scheme into a digital signature scheme using the FiatShamir 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 April  Assignment 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 April  Assignment 2 Solution Discussion  We discussed the solutions for assignment 2. The assignment is here and the scribe discussing the sample solutions is here.
 26  27 April  Assignment 3 Solution Discussion  We discussed the solutions for assignment 3. The assignment is here. 
