- Arpita Patra (Email: arpita AT csa )
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
The space below will be populated as and when the course progresses.
Lecture # and Date
Lecture contents (The slides are copyrighted. Please take permission before using.)
Slides / Reading material
|Guest Lecture 1 (05.08.15)||Guest Lecture by Prof. Pandu Rangan.|
|Lecture 1 (10.08.15)||Introduction to Secure Computation Part I: Motivation, Definition, Secret sharing, Secure Addition, OT, Secure bit multiplication.||[ppt-1] / (some) Examples taken from 1st Chapter of CDN||
|Lecture 2 - 4 (12.08.15; 9:30 -10 am; 21.08.15 (Fri); 8 - 9:30 am; 2:30 - 5:30 pm)||Introduction to Secure Computation Part II: Various Facets/Models of MPC (models of computation; networks; modelling distrust; adversarial features); Various Models/parameters/questions/primitives used in MPC, Real world / Ideal Word Security Definition||[ppt-2]/ (Some) examples taken from 1st Chapter of CDN; Also see [Orl11].||[pdf](edited)|
|Lecture 5 (26.08.15 (Wed); 8 - 9:30 am)||Real world / Ideal Word Security Definition, Computational/Statistical/Perfect Indistinguishability, (n,t)-secret sharing, Shamir Sharing, Security, Lagranges Interpolation.||[ppt-5] / Have a look at the 3rd Chapter of CDN.||[pdf](edited).|
|Lecture 6 (26.08.15 (Wed); 2 - 3:30 pm)||i.t. MPC with honest majority (BGW)||[ppt-6] / [AL11]||[pdf] (edited).|
|Lecture 7 & 8 (04.09.15 (Fri); 8 - 10 am and 2 - 4 pm)||Offline-Online Paradigm and Beaver's Trick; Reduction of online phase to Reconstruction of Secret; Various offline phase protocols; Randomness extractors; Linear overhead i.t. MPC.||[ppt-7_8]||[pdf](unedited)|
|Lecture 9 & 10 (09.09.15 (Wed); 8 - 9:30 am; 2:00 - 3:30 pm)||Impossibility of i.t MPC with n<= 2t. Impossibility of OT with i.t. security. OT from CPA secure encryption with public key Samplability. Security Proof. Two party computation from OT (GMW construction), Security Proof, Extension to Multiparty Computation.||[ppt-9_10] / Impossibility proof from 13 page of [this]. OT (based on PKE) and proof from [this]; GMW from [this] and [this]||[pdf](unedited)|
|Lecture 11 & 12 (18.09.15 (Fri); 8 - 9:30 am; 2:30 - 4 pm)||Online/offline OT, Domain Extension of OT, OT Extension - IKNP03, 1-out-of-4 OT from 1-out-of-2 OT, Constant Round Two party Computation - Yao's Protocol- Part I||[ppt-11_12] / [IKNP03]||[ pdf]|
|Lecture 13 & 14 (23.09.15 (Wed); 8 - 9:30 am and 2 - 3:30 pm)||Yao's 2PC, Optimization: Point-and-Permute, Security Proof.||[ppt-13_14] / Chapter 3 of HL or [LP09]||[ pdf]|
|Guest Lecture 2-3 (14.10.15; 8 - 9:30 am, 2 - 3:30 pm)||Zero Knowledge Proofs||[ pdf]|
|Lecture 15-16 (15.10.15 (Thu); 8 - 9:30 am, 2 - 3:30 pm)||Challenges in malicious BGW, Verifiable Secret Sharing(VSS), 4-round VSS with n>=3t+1||[ppt-15_16] / For the 4-round VSS, refer to [GIKR01]||[ pdf]|
|Guest Lecture 4 (30.10.15 (Fri); 8 - 9:30 am)||Zero-knowledge proofs||[ pdf]|
|Lecture 17-18 (09.11.15 (Mon); 2:00 - 5:00 pm)||RS codes and Error Correction. Reconstruction for n >=3t+1 in the presence of malicious adversary, Perfectly secure Multiplication protocol, Maliciously secure BGW||[ppt-17_18] / [AL11]||Lecture 17:[ pdf], Lecture 18:[ pdf]|
|Lecture 19-20 (09.11.15 (Mon); 8 - 9:30 am, 2:30 - 4 pm)||Maliciously secure Yao (LP11)- Cut-and-choose Technique, DDH based Pseudo-random synthesizer, ZK Proof of Knowledge (PoK) for DDH, ZK PoK for OR statements, ZK PoK for proving knowledge for a subset of a given set of statements, Batch Single-choice Cut-and-Choose OT. LP11 Construction.||[ppt-19_20] / [LP11]|
Date and Time
|Divya||16.09.15; 8-9 am||How to Create Raw Data for Honest Majority MPC||[CHP13]||[Here] by Suvradip|
|Dheeraj||24.09.15; 2-3:30 pm||A Framework for Efficient and Composable Oblivious Transfer||[PVW08]||[Here] by Marylin|
|Ajith||28.09.15; 2:00-3:30 pm||The Round Complexity of Secure Protocols.||[BMR90]; search for a better reference||[Here] by Dheeraj|
|Pratik||30.09.15; 9:00-10:00 am||Improved OT extension for transferring short secrets.||[KK13]||[Here] by Ajith|
|Bharath||01.09.15; 9:00-11:30 pm||Software Protection and Simulations on Oblivious RAMs||[GO96]||[Here] by Nithin & [Here] By Divya|
|Nithin||02.10.15; 02:00-3:00 pm||Fast Garbling of Circuits from Standard Assumptions||[GLNP15 ]||[Here] by Bharath|
|Cressida||03.10.15; 10:00-11:00 pm||Secure and Efficient Protocols for Iris and Fingerprint Identification||[ BG10]||[Here] by Pratik|
Date and Time
|Pratik||11.11.15; 9-10 am||The Round Complexity of Verifiable Secret Sharing Revisited||[PCRR09]||[ ] [Here] by Dheeraj|
|Marylin||11.11.15; 10:30-11:30 am||Perfectly secure MPC with Linear Communication Complexity.||[BH08]||[ here] by Cressida|
|Divya||18.11.15; 4:30-5:00 pm||Near-Linear Unconditionally-Secure Multiparty Computation with a Dishonest Minority.||[BFO12]|
|Bharath||19.11.15; 1:30-3:00 pm||Software Protection and Simulations on Oblivious RAMs||[GO96]||[ Here ] by Pratik|
|Dheeraj||..||Efficient Constant Round Multi-party Computation Combining BMR and SPDZ.||[LPSY15 ]||[Here ] by Ajith|
|Ajith||20.11.15; 9:00 - 10:30 am||Blazing Fast 2PC in the Offline/Online Setting with Security for Malicious Adversaries.||[LR15];||[Here ] by Divya and [ here] by Nithin|
|Cressida||20.11.15; 2:00 - 3:30 PM||Multi-Valued Byzantine Broadcast: the t < n Case||[ HR14]||[Here ] by Cressida|
|Nithin||20.11.15; 3:30-5:00 pm||Non-Interactive Secure Computation Based on Cut-and-Choose.||[AMPR15]||[Here ] by Marilyn|