2015-CS-NC-813

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.

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 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:

Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell, Second Edition, CRC Press.

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.

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 Projects: This 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:

1. IEEE Symposium on security and privacy and the associated workshops.

2. ACM conference on Computers and Communication Security and the associated workshops.

3. Privacy Enhancing Technologies Symposium. Homepage for this year's event.

4. European Symposium on Research in Computer Security.

5. USENIX security conference.

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 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.

2. Privacy-preserving 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 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 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 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 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 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 Smartphones: Smartphones 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.