2015-CS-NC-857
CS-NC-857: Secure Computation, Session 2015-16, Term I
Course Information
Instructor: Ashish Choudhury,office: Room No 223, email: ashish DOT choudhury AT iiitb DOT ac DOT in
Timings and Venue: Tuesdays and Thursdays 11.15 am - 12.45 pm, Room no 103.
Attendance: There is no compulsion on attendance. If you want to learn the subject, then you are welcome to attend the lectures. However, I do expect some descent amount of "participation" from the students if they register for the course. You are welcome to audit the course.
Eligibility and Pre-requisites: The course is offered as a special topic elective for the 4th year IMTech students and 2nd year M.Tech students enrolled for the CS/NC stream. The students from the other streams can register for the course as an open elective.
A student is applicable to credit this course only if he/she has credited the CS-NC-813: Foundations of Cryptography course and obtained a B- or a higher grade in that subject. Students with any other grade in the CS-NC-813 course who are interested to credit the course should meet me and take my consent before registering for the course. The course requires familiarity with some of the basic concepts covered in the CS-NC-813 course, apart from the basic knowledge of the concepts from discrete mathematics and algorithms. Having said that, I will ensure that a significant effort is made from my side to simplify the overall presentation of the course and make it easily accessible.
Important: Students who are planning to do their final year project with me (both M.Tech as well as IMTech) have to compulsorily take this course. This course will cover everything about the research/practical projects in which I am interested to work.
Course Description: This will be the second course in the series of crypto courses, which started with the CS-NC-813 course on foundations of cryptography in the previous semester. Note that currently I am not planning to offer the third proposed course in the series, namely applied cryptography (or cryptographic engineering).
In the previous course, we studied rigorously about various cryptographic objects, like encryption schemes, signature schemes, message authentication codes, hash functions, etc. This course will discuss about how using these cryptographic primitives, one can do secure computation, which arguably is one of the most fundamental problems in cryptography as well as distributed computing. We will also develop several additional tools and proof techniques and learn various new definitional paradigm for advanced cryptographic tasks. In summary, if you believe that the previous course taught you something new and exciting with a non-negligible probability then this course is definitely meant for you, where the excitement and challenges will be much more. There will be ample scope to challenge your theoretical maturity and programming skills (see the assessment criteria below).
The need for secure computation arises in several real-world applications which require computations that involve sensitive data from two or more mutually distrusting entities. Consider the following example, which is one of the latest applications of secure computation investigated by DARPA: The Earth is orbited by thousands of man-made satellites and several thousands of orbital debris. The growing number of satellites and space debris orbiting the planet increases the danger of collisions. And this is not a hypothetical scenario, as several such “high-profile” collisions have been reported in the recent past. Given the expensive cost of satellites, the host countries would like to avoid collision. A collision can only be predicted if the detailed orbit information of the individual satellites is known. However, such information can be highly sensitive and in fact, it can even be a national secret. So what is needed here is a way to determine whether two satellites are about to clash with each other based on the detailed locations of the satellites, but without the need of disclosing the locations of the satellites to other host countries.
Secure computation models the above and several such applications that make simultaneous demands for the privacy and usability of sensitive data; if you are really wondering whether the above is doable (at least in theory), then you can read the paper [KH14] (however you will be able to make a good sense of it only at the end of the course). Other examples of secure computation include secure e-voting, secure e-auction, secure signal-processing, secure bioinformatics, secure biometrics, secure machine-learning, secure outsourcing, privacy-preserving data-mining, to name a few (see below the list of practical projects for some of the applications of MPC).
Secure computation can also be used as a tool to foil server security breach; in fact this technique is recently deployed by Dyadic security (https://www.dyadicsec.com/). The idea is the following: to counter ubiquitous data security breaches and identity thefts, the sensitive cryptographic keys/secret credentials is split into “shares” and stored in multiple servers so that the secret is protected from an attacker attacking a quorum of servers. The computation on the shared secret data without compromising its privacy is a serious challenge, which is tamed via secure computation protocols. The problem of secure computation abstracts out the afore-mentioned applications and alike and goes beyond the capabilities of conventional cryptography to offer the dual demands of privacy and computation on secret data as required.
The problem of secure computation was first formulated by the Turing award winner Andrew Yao in his seminal work published in Foundations of Computer Science (FOCS) 1982 (see [Yao82]). The problem is as follows: we have a set of n mutually distrusting parties P1, ..., Pn, with private inputs x1, ..., xn. Together they want to compute some publicly known function, say f, on their inputs, by keeping their inputs “as private as possible”. Due to its powerful abstraction, secure computation problem is also considered as the “holy-grail” of secure distributed computing; if you have a solution for this problem then you have a solution for thousands of other real-world problems. And this is a highly popular research topic both in the theoretical as well as the applied cryptography community; over the last three decades, this is arguably one of the largest studied topic in cryptography and distributed computing (see this annotated bibilography on MPC).This will be one of the first courses of its kind to be offered in India (a similar course is going to be offered by my research colleague Dr. Arpita Patra at Indian Institute of Science next semester and the course description given here is borrowed from her), covering the formal details of this topic and promises to unfold the evolution of this topic since 1982 to till date.
Tentative Topics: The following is the tentative list of topics to be covered in this course.
Why Secure Computation?: Introduction, Motivation and History.
Models for Secure Computation: Honest vs dishonest- majority setting, Semi-honest vs active(malicious) adversary, Static vs adaptive corruption, Computational vs information-theoretic security, Synchronous vs asynchronous network
Defining Secure Computation: Computational/statistical/perfect indistinguishability, Real-world/Ideal-world paradigm,Simulation based security notion.
Secure Computation with Semi-honest Security
Honest-majority Setting: Secret sharing, BenOr-Goldwasser-Wigderson (BGW) construction, Optimizations using Beaver's trick (secure computation in the preprocessing mode and circuit randomization), Secure computation from threshold-homomorphic encryption
Dishonest-majority Setting: Impossibility of the information-theoretic secure computation in the dis-honest majority setting,Oblivious transfer (OT), Two-party Goldreich-Micali-Wigderson (GMW) construction, Optimizations of GMW (Random input OT and OT extension), Yao’s 2-party protocol, Optimizations of Yao’s protocol (free XOR technique, point and permute technique), Beaver-MIcali-Rogaway (BMR) construction and multi-party GMW construction
5. Secure Computation with Active Security
Honest-majority Setting: Verifiable secret-sharing (VSS), BGW construction with active security, Hyper-invertible matrices and Beerliova-Hirt (BH) construction, Information-checking protocol
Dishonest-majority Setting: Commitment schemes, Zero-knowledge, GMW compiler for active corruption, Cut-and-Choose OT and Lindell-Pinkas construction
6. Broadcast and Byzantine Agreement (BA): Impossibility results, Dolev-Strong (DS) broadcast protocol, Exponential Information Gathering (EIG) construction for BA, Berman-Garay-Perry (BGP) construction for BA, Multi-valued broadcast and BA
7. Other Topics (if time permits): Verifiable computation, Fully-homomorphic encryption (FHE) and MPC
Textbook: As this is mostly a research-topic based course, there is no specific textbook which is available for this course. And most of the syllabus will be based on research papers published in top level cryptography and security conferences/journals (see below for a list of top cryptography and security conferences/journals); the students will be provided with all the relevant research papers. For some of the topics, the following texts can be used for the reference purpose:
Book: Efficient Two-party Protocols- Techniques and Constructions; by Carmit Hazay and Yehuda Lindell. Springer-Verlag, 2010.
Book: Engineering Secure Two-party Computation Protocols, by Thomas Schneider. Springer Verlag, 2010
Book: Secure Multiparty Computation and Secret Sharing, by Ronald Cramer, Ivan Damgard and Jesper Buus Nielsen. Cambridge University Press, 2015.
Book: Cryptography: Theory and Practice, by Douglas Stinson (3rd Edition), CRC Press.
The students will find the following video lectures (delivered by the top experts in this area) extremely useful, to understand both the theory and the applied side of secure computation:
Video lectures from the Bar-Ilan winter school on secure computation and efficiency
Video lectures from the Bar-Ilan winter school on advances in practical multi-party computation
A similar (and advanced) course on secure computation is offered at University of Maryland by Prof. Jonathan Katz and the students may find the lecture notes for that course useful for this course. My colleague Dr. Arpita Patra at IISc Bangalore is also offering a similar course this semester; students might find the references and slides used by her useful. These are available here.
Grading: There will be no exams and no assignments!! The (tentative) evaluation will include the following components:
Scribe (20%): Each student has to scribe one lecture; depending upon the number of students, we may form group of two students for scribe. Note that unlike the previous course, there will be no slides used and everything will be done on the board; so there will be no matinee show this time.
Paper Presentation and Practical Project (30% + 50%): We will form groups of two students at the beginning of the course and each group will be assigned a practical project related to secure computation. The project will be based on research paper(s), which the group members need to read and present. The group also need to implement the proposed protocol(s).Towards the end of the semester we will have a project demo and detailed viva for each group. During the course, we will develop the theory and tools for doing general MPC (ex: OT, homomorphic encryption, garbling, secret-sharing, etc); the assigned project will require to apply those tools and methodologies for specific problems given below. It is advisable that the students select the topics carefully and start devoting time for the same from the beginning, instead of pending everything towards the end. If given sufficient time, the projects are doable. All the projects are interesting and challenging; do not judge a project by the number of papers associated with it as you may need to read not only the mentioned paper but also some other papers referred by it to get a good grasp of the topic. The amount of effort (number of papers to read and implement it) required will be more or less same for each project. The list of projects and the related papers are as follows
Private Set Intersection (PSI): probably one of the most widely studied practical application of MPC. The problem is as follows: we have a set of n mutually distrusting parties, each with a private set. Together they want to find the intersection of the sets, without revealing any additional information about the individual sets. This problem has numerous applications (see the corresponding papers below for a list of such applications). The problem becomes more practically relevant for the 2-party case. There are several practical protocols for this problem proposed over a period of time, which can be categorized into following four categories (see [PSZ14] for a good survey of the PSI protocols). You have to select a protocol from one of these four categories and implement it.
PSI using oblivious transfer (OT): read [PSZ14] and its references
PSI using additive homomorphic encryption: read [HFH99], [CT10], [FHNP]
PSI for multiparty setting (more than 2 parties): read [KS05]
PSI for big-data using bloom filters: read [DCW13], [PSZ14]
Oblivious Sorting: assume we have an array, where the contents of the array is not available with a single party, but rather shared among n parties in a secret-shared/encrypted fashion. Now can the parties sort the array without learning anything about the array elements? This is the problem of oblivious sorting. Oblivious sorting have applications in higher level secure protocols. We have efficient oblivious sorting protocols for quick sort and radix sort; you have to select one of them and implement it.
Oblivious quick sort [HKI+13]
Oblivious radix sort [HICT14]
Secure Graph Algorithms: consider a scenario where a graph is shared among n parties in a secret-shared/encrypted fashion, such that the graph topology is completely hidden. Now can we solve the standard graph-theoretic problems like single-source shortest path, all-pair shortest path, max-flow, breadth-first search, etc without revealing the graph topology to any party? Such secure algorithms will be definitely useful in military applications and secure GPS services. We can also imagine about securely running the conventional computational geometry algorithms, like convex-hull, closest-pair, point-inclusion, etc. You have to select one of the following categories of problems and implement the corresponding algorithms.
Secure computational-geometry algorithms [AD01]
All-pair shortest path, single-source shortest path based on Yao's protocol [BS05]
Shortest-path, max-flow based on secret-sharing [ACMPV13]
BFS, Single-source shortest path, MSP, max-flow [BSA13]
Secure Genetic Algorithms: genetic algorithms are important class of heuristic algorithms, which are extremely useful to find approximate solutions when finding the exact solution is difficult. An interesting question will be to see whether we can apply the genetic algorithms even on the data which is not available in clear, but rather available in either encrypted or secret-shared form. You have to select one of the following two categories of secure genetic algorithms and implement it.
Secure genetic algorithm for the subset cover problem [BEJKMW14]
Secure genetic algorithm for the travelling-salesman problem [SK07]
Secure Biometric: another interesting and futuristic application of MPC. In a typical bio-metric application, there exists a bio-metric sample and an existing database of bio-metric samples and the goal is to find out whether the given sample belongs to the database or not. Now can we do the same in a secure way, where the database is with the server and the sample to be verified is with a client, such that they are not ready to reveal anything to each other, beyond the answer that whether the given sample is present in the database or not (this may look like a special case of PSI, but we have specific solutions tailor made for secure biometric applications). Typical biometric algorithms use various metrics like Hamming distance, Euclidean distance, Mahalanobis distance, scalar product, etc. If we can implement them securely then we can securely implement biometric algorithms. You have to understand the following paper and implement the algorithms in it.
GSHADE [BCFPSZ14]
Privacy-preserving GNOME Sequencing: Whole Genome Sequencing (WGS) evolved from a futuristic-sounding research project to an increasingly affordable technology for determining complete genome sequences of complex organisms, including humans. This prompts a wide range of revolutionary applications, as WGS promises to improve modern healthcare and provide a better understanding of the human genome - in particular, its relation to diseases and response to treatments. However, this progress raises worrisome privacy and ethical issues, since, besides uniquely identifying its owner, the genome contains a treasure trove of highly personal and sensitive information. Privacy-preserving GNOME sequencing has grabbed the attention of researchers over the past few years and several interesting solutions have been proposed (see this excellent survey). The main problem addressed in these protocols is that of private DNA matching, where one party has a DNA sample and the other party has another DNA sample or a database and the goal is to find the intersection. Again this looks like a special case of 2-party PSI, but more efficient tailor-made solutions have been proposed. The proposed solutions can be categorized into three groups; you have to select one such group and investigate.
Solutions based on oblivious finite state machine evaluation [TKC07], [Fri09]
Solution based on string matching based on oblivious PRF [KM10]
Solution based on PSI [BBCGT11], [CFGT12]
Secure Bit-decomposition and Applications: in several MPC protocols, we come across the following scenario: there exists a secret-shared value among a set of n parties. The shared value belongs to some finite field (the exact value is unknown). Somehow the parties want to have the bit representation of the secret field element in a shared fashion. The solution to this problem known as the secure bi-decomposition problem has several interesting applications, such as secure comparison (which is the solution for Yao's millionaire problem) and secure modular arithmetic (where a secret-shared number is reduced modulo a secret-shared modulus), etc. You have to read the following relevant paper and implement it.
Secure bit-decomposition [DFKNT06]
Distributed Discrete-log Based Encryption and Signature: in a threshold encryption scheme the encryption key is publicly available (so anyone can encrypt a message with the knowledge of public key), but the decryption key is not available with a single entity but rather shared among several parties. Decrypting a cipher-text in such a setting requires the participation of a certain threshold number of participants. The idea behind such a system is to prevent single point of failure. The goal of this project will be to implement such a set-up. The relevant paper is the following:
Threshold Discrete-log based cryptosystem [GJKR07-I]
Distributed RSA: The goal here is the same as the previous project except that here we deal with the RSA function. The following is the relevant paper:
Threshold RSA [GJKR07-II]
Verifiable Secret Sharing (VSS): VSS is a very fundamental primitive for distributed cryptography. On a high level, it allows a special party called dealer to verifiably share a secret among a set of share-holders, such that the privacy of the shared value is preserved even if a certain threshold number of participants combine their shares. The verifiability ensures that even if the dealer is corrupted, there exists some value which will be "properly" shared among the participants. VSS is heavily used in MPC. We can categorize VSS into following three groups. You have to select one group of protocols and investigate the same.
Perfectly-secure VSS [KKK08]
Statistically-secure VSS [PCR09], [Agr12]
Computationally-secure VSS [BKP11]
Multi-valued Byzantine Agreement (BA) and Broadcast: BA and broadcast are two fundamental problems in distributed computing. A BA protocol allows a set of n parties, each having a private bit, to agree upon a common bit, even if t out of the n parties try to prevent the agreement. A broadcast protocol allows a sender to send a message identically to all the n parties, even if the sender is corrupted and try to send different messages to different parties. In MPC protocols, a common scenario is when the parties need to broadcast large messages or need to agree on large messages, instead of single bit. One way of doing this is to run several instances of BA/broadcast protocol dealing with one bit, but this will be highly inefficient. A different approach would be to "work" on the large messages and use a small number of instances of BA/broadcast protocol dealing with one bit; the idea is to keep the number of such instances independent of the large message size. This is exactly the problem of multi-valued BA and broadcast. You have to investigate the following relevant paper.
Efficient multi-valued BA and broadcast [Pat11]
Bonus Evaluation: For students who are research oriented, there is ample scope of doing research and solving some good open problems in this course. Each of the papers listed above has some good open problems. Apart from this, I will also discuss some other open problems during the course. If you can solve one of those open research problems (you are allowed to make groups for such an attempt), then you need not have to go through any evaluation process and you will get an A grade in the subject. However I would like to caution that the open problems will be really challenging (they are open for quite some time now) and just by working for few days on them, they cannot be solved. So before you attempt any such problem, you should think carefully. Of course for your final year project (if you are doing it under me), you are strongly encouraged to work on such problems.
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.
Course Schedule, Scribes and Slides
This section will be populated as the course progresses.