• Arpita Patra (Email: arpita AT csa )

• Class timing: Monday (8:00 - 9:30 am and 2:00 - 3:30 pm) OR Wednesday (8:00 - 9:30 am and 2:00 - 3:30 pm) OR Friday (8:00 - 9:30 am and 3:00 - 4:30 pm); Check the lecture schedule for up to date Information
• Venue: CSA 252

The fantabulous journey of Secure Computation had originated with the seminal work of Andew Chi Chih Yao published in Foundation of Computer Science (FOCS'82). The idea of secure computation is so groundbreaking that Yao was bestowed with the prestigious Turing Award in 2000. I feels wonderful to offer a course that is first of its kind in India. For more details, follow this link

Models of Secure Computation: Honest vs. Dishonest majority settings, semi-honest vs active(malicious) adversary, static vs. adaptive computation, computational vs. information theoretic security, synchronous vs. asynchronous network...

Defining Secure Computation: Computational/statistical Indistinguishability, Real-Ideal World or Simulation-based Security notions.

Secure computation with semi-honest security: Honest-majority Setting: Secret Sharing, BenOr-Goldwasser-Wigderson (BGW) Construction, Optimizations (MPC in preprocessing mode and circuit randomization), Cramer-Damgaard-Neilsen (CDN) Construction. Dishonest majority Setting: Oblivious Transfers (OT), two-party Goldreich-Micali-Wigderson (GMW) construction, Optimizations of GMW (Random input OT and OT extension), Yao construction, BMR construction and multi-party GMW construction.

Secure computation with Active security: Honest Majority Setting. Verifiable Secret Sharing, 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.

Broadcast & Byzantine Agreement (BA): Impossibility results. Dolev-Strong (DS) Broadcast, Exponential Information Gathering (EIG) construction for BA, Berman-Garay-Perry (BGP) construction for BA. Multi-valued Broadcast and BA.

Practical Secure Computation: Secure Set Intersection, Privacy Preserving Biometrics & Genomics, Secure Cloud Computing

• Scribe (8*3 = 24% ): Every student must scribe at least three lectures. The scribe submission deadline is one week after the class; e.g. a scribe for a lecture on 10th must be submitted by the midnight of 17th.The template tex file for a scribe can be downloaded from here. As you have guessed, the submission must be in Latex. To get first-hand ideas about how to scribe, please have a look at some examples from here.
• "Chalk & Talk" Seminar (10*2 + 3*2=26%): The goal of this session is to cover breadth of the course. Topics will be suggested as and when the course proceeds. The seminar series will run throughout the semster. Each student has to make two presentations and write two blogs overall. Every week we will have one presentation of one and half hour on Friday between 8:30 am and 9:30 am. Attendance is mandatory. For every presentation, a student (not the speaker) will be randomly picked and assigned to write a blog for the presentation. The blog will be a brief overview of the presentation and should make sense even to non-experts. To get first-hand idea on how to blog, take a look at the blogs here. We will create a similar blog page.
• Projects (10+40 = 50%): The course requires every student to carry out one project. The project will be either theoretical or practical in nature. The theoretical projects will involve answering deep and exiciting theoretical questions in the secure computation literature. On the other hand, the practical projects will involve implementing and improving challenging practical secure computation tasks. A list of theoretical & practical projects are posted below. The students are free to choose a project that catches their fancy. Students are also encouraged to propose their projects that fits under this course.
List of Theoretical Project Topics (under each topic there are several open problems which will be dispensed upon request)
• T1: OT & OT Extension
• T2: Commitments & Verfiable Secret Sharing
• T3: Garbled Circuits
• T4: Secure Computation with Dishonest Majority
• T5: Asynchronous or Partial Synchronous Secure Computation
• T6: Constant Round Secure Computation
• T7: Adaptive Secure Computation
• T8: Secure Computation of RAM Programs
• T9: Covert Secure Computation
• T10: Broadcast with dishonest Majority
List of Practical Project Topics (under each topic there are several open problems which will be dispensed upon request)
• P1: OT, OT Extension & Optimizations
• P2: Yao Garbled Circuits & Optimizations
• P3: Non-interactive Secure Computation
• P4: Efficient Two-party Computation
• P5: Secure Set Intersection
• P6: Privacy Preserving Genome Computation
• P7: Broadcast and Byzantine Agreement Protocols

Reference Books:

• Efficient Two-party Protocols- Techniques and Constructions by Carmit Hazay and Yehuda Lindell. Springer.
• Secure Multiparty Computation and Secret Sharing - An Information Theoretic Appoach by Ronald Cramer, Ivan Damgaard and Jesper Buus Nielsen. Cambridge Press.

Some useful links on Secure Computation:

• An ongoing course on Secure Computation by Benny Pinkas offerred at Bar-Ilan.
• A course on Intro to Secure Computation Course by Jonathan Katz at Maryland.
• A course on Secure Multi-party Computation by Daniele Micciancio
• Winter School on MPC organized by Yehuda Lindell in Bar-Ilan University.
• Summer School on Securing Computation at Simon's Institute