2016:CS-NC-716
CS-NC-716: Computing on Private Data, Session 2016-17, 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: A student is applicable to credit this course only if he/she has credited “Foundations of Cryptography course and obtained B or higher grade in the course. Students with a lower grade in the Foundations of Cryptography course should take my prior permission before registering for the course.
Students who have not taken the Foundations of Cryptography course but are quite comfortable in subjects in theoretical computer science (like Data structures, Algorithms, Discrete Maths and Theory of Computation) can also register for the course; however such students also need to take my prior approval before registering for the course. There if absolutely no restriction on auditing the course.
The course requires familiarity with some of the basic concepts covered in the first course in the cryptography series, apart from the basic knowledge of the concepts from discrete mathematics and algorithms. Having said that, it will be ensured 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. In the first course, we rigorously learnt 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 computation on distributed and sensitive data, also known as secure multi-party computation (MPC), which arguably is one of the most fundamental problems in cryptography as well as secure distributed computing.
The need for distributed computation on private data arises in several real-world applications that require computations involving 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 MPC models the above and several such applications that make simultaneous demands for the privacy and usability of sensitive data. Other examples 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.
Performing distributed computation on private data can also be used as a mechanism 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. The problem is as follows: we have a set of n mutually distrusting parties P1, …, Pn with private inputs x1, …, xn respectively. 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 cryptography. And this is a highly popular research topic both in the theoretical as well as in the applied cryptography community. This will be one of the first courses of its kind to be offered in India, covering the formal details of this topic and promises to unfold the evolution of this topic since 1982 to till date.
Note: This course has been previously offered with title Secure Computation.
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: The (tentative) evaluation will include the following components:
Scribe (20%): Each student has to scribe for at least one lecture. The scribe needs to be prepared in Latex. It needs to cover each and every topic covered in the lecture in full detail. Note: Unlike the previous course, no feedback will be provided to the students to revise their scribe. They are expected to prepare a quality level scribe on their own. The students can revise their scribe as many time as they want till the final presentation. The scribes need to be prepared using this style file.
Paper Presentation (50%): We will form groups of two students and each group will be assigned a theoretical and fundamental topic related to secure computation. The topic will be based on research paper(s), which the group members need to read and present towards the end of the semester. The list of papers is available in this zip file. The students have to email their group details and their preferences of the paper to Yashvanth Kondi (email: Yashvanth dot Kondi@iiitb.org) by 5th September. The students should give the preference for each paper in the list in the decreasing order. There is no guarantee that a group member will be assigned the paper for which they give the highest preference.
Research Assignments (30%): There will be some written assignments, consisting of research questions. The answers for these questions will be mostly available in research papers. The idea is to make the students re-invent these solutions with their own understanding that they develop during the course.
Course Schedule and Scribes
This section will be populated as the course progresses.