Seminar on Secure Multi-Party Computation
Id: 0368-4182-01


Ran Cohen and Iftach Haitner

Tuesdays: 10:00-12:00, Room: Schriber 008


In Secure Multiparty Computation, two or more parties wish to jointly compute a function of their inputs in a secure manner: the outputs received by the parties are correctly distributed, and the privacy of each party’s input is preserved as much as possible, even in the presence of adversarial behavior. Formally defining secure multiparty computation and implementing the secure computation for many functions of interest, is arguably one of the great achievements of theoretical cryptography. The seminar will not follow any specific text, references to the relevant material for each lecture will be given in the seminar website.

In each meeting one student will cover a single topic as listed below.

Prerequisites

This is an advanced seminar, so background in the theory of computation (Algorithm, Computability, Complexity) is required. Students with particularly strong math background are also welcome. Cryptography course, like Foundation of Cryptography or Introduction to Modern Cryptography, is recommended but not required.

Undergrad students

Third year students who are willing to work hard, are welcome to join the seminar, but please consult me via email before registering.

Presentations

Power Point presentations are acceptable, but white boards ones are preferable.
To do a good job one needs to read background material, see the reading section.
In addition, the speakers of the week will have to give me a practice talk a week before (right after the talk of that week).

Topics and schedule

(see Additional reading for further reading on your lecture topic)

# When Who What
1 14/03 Ran Cohen
Introduction [slides]
2 21/03 Nathanel Ozeri
Definitions for two-party computation (semi-honest and malicious)
[HL10] sections 2.1-2.3
28/03 NO CLASS
3 04/04 Shlomi Shamir
Yao's Garbled Circuit (semi-honest two-party protocol)
[HL10] sections 3.1-3.4 (section 3.2 only at a high level)
4 05/04 (Wednesday!) Gal Arnon
Oblivious transfer
  • 1-out-of-k OT from 1-out-of-2 OT: [BCR86] section 2.2
  • Precomputing OT: [Bea95] sections 3.1 and 3.2
  • OT extension: [Bea96] section 3
  • OT is symmetric: [WW06] section 4
5 25/4 Noam Nissan
GMW protocol (semi-honest multi-party protocol)
[Gol04] sections 7.3.3, 7.3.4, and 7.5.2
6 09/05 Assaf Yifrach
BGW protocol (unconditionally secure MPC for honest majority)
[AL17] sections 3 and 4
7 16/05 Adam Alon
BMR protocol (constant-round MPC)
[BNP08] sections 3 and 4
8 23/05 Jhonatan Tavori
GMW compiler (enforcing semi-honest behavior)
[Gol04] sections 7.4.1, 7.4.3, and 7.4.4
9 06/06 Alon Resler
IKOS zero-knowledge proofs (two-party ZKP from MPC)
[IKOS09]
10 13/06 Lev Pachmanov
Cut and choose (Yao's protocol for malicious adversaries)
[LP12]
11 20/06 Doron Sobol and Rotem Tsabary
Sigma protocols
[HL10] section 6
12 27/06 David Tsiris
Secure computation of specific functionalities
  • Finding the median: [HL10] chapter 8
  • Private set intersection: [FNP04]


Additional Reading


References