CSE208 (Winter 2011): Advanced Cryptography - Secure Multiparty Computation
Schedule: Lectures are on Tuesday and Thursday, at 11am-12:20pm, in room EBU3b 4217.
There will be no lecture on Thursday January 27, due to STOC PC meeting.
Course Description
This quarter, the Advanced Cryptography course will focus on Secure Multiparty Computation. Specific topics that will be covered include: definition of secure computation in the presence of passive and active adversaries, variants of the universal composability framework, general feasibility results for 2 party and multiparty computation, recent progress on efficient protocols and the overhead of cryptography, dedicated protocols for special problems (zero knowledge proofs, oblivious transfer, private information retrieval, etc.)
There is not textbook for this course, and relevant reading material (links to lecture notes, research papers, etc.) will be posted on this web page. However, as no textbook level reference material is available for this topic, students are expected to come to lecture and take their own notes during class. If you miss any class, you are responsible to obtain notes from some other student.
Coursework will include a small number of homework assignments, and individual presentations at the end of the course. The presentation can be either a survery of a small number of related papers, or, if appropriate, reporting on a research project carried out as part of this course.
Syllabus / Reading Assignments
Specific topics and relevant reading assignments will be posted here as they get covered during the course. For links to the reading material, see reference section below.
- Introduction to Secure Multiparty Computation (Reading: Chapter 1 from Multiparty Computation). In class we also gave a detailed security proof (with respect to passive adversaries) for a variant of the addition protocol described in this chapter. As an exercise, give a similar proof for the addition and the multiplication protocols described in the chapter.
- Secret sharing and general secure computation against passive attacks in the information theoretic setting (Reading: Chapter 4 from Multiparty Computation)
- Impossibility of perfectly secure computation against t >= n/2 passive corruptions. (Reading: Chapter 4 from Multiparty Computation)
- Computationally secure 2-party function evaluation (Yao's Garbled circuits). (Reading: A Proof of Security of Yao's Protocol for Two-Party Computation)
- Definition of (standalone) security for function evaluation protocols with respect to active attacks. Examples: Obliviuos Transfer and Zero Knowledge.
- Zero-Knowledge protocols for all NP problems
References
Recent papers on secure computation (TCC 2011, Eurocrypt 2011)
- Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer (Lindell & Pinkas; TCC 2011)
- Completeness Theorems with Constructive Proofs for Finite Deterministic 2-Party Functions (Kraschewski & Müller-Quade; TCC 2011)
- A Zero-One Law for Secure Multi-Party Computation with Ternary Outputs (Kreitz; TCC 2011)
- Limits on the Power of Zero-Knowledge Proofs in Cryptographic Constructions (Brakerski, Katz, Segev & Yerukhimovich; TCC 2011)
- Perfectly Secure Oblivious RAM Without Random Oracles (Damgård, Meldgaard & Nielsen; TCC 2011)
- Practical Adaptive Oblivious Transfer from Simple Assumptions (Green & Hohenberger; TCC 2011)
- Concurrent Non-Malleable Zero Knowledge with Adaptive Inputs (Lin & Pass; TCC 2011)
- On the Black-Box Complexity of Optimally-Fair Coin Tossing (Dachman-Soled, Lindell, Mahmoody & Malkin; TCC 2011)
- Exploring the Limits of Common Coins Using Frontier Analysis of Protocols (Maji, Ouppaphan, Prabhakaran & Rosulek; TCC 2011)
- Unconditional and Composable Security Using a Single Stateful Tamper-Proof Hardware Token (Döttling, Kraschewski & Müller-Quade; TCC 2011)
- Bringing People of Different Beliefs Together to do UC (Sanjam Garg; Vipul Goyal; Abhishek Jain; Amit Sahai; TCC 2011)
- Semi-Homomorphic Encryption and Multiparty Computation (Bendlin, Damgård, Orlandi & Zakarias, EUROCRYPT 2011)
- Two-output Secure Computation With Malicious Adversaries (shelat & Shen, EUROCRYPT 2011)
- Towards a Game Theoretic View of Secure Computation (Asharov, Canetti & Hazay; EUROCRYPT 2011)
- Efficient Non-Interactive Secure Computation (Ishai, Kushilevitz, Ostrovsky, Prabhakaran & Sahai; EUROCRYPT 2011)