What do I learn?

Algorithms are non-interactive tasks realizing a computational function. Typically, a single party, such as the program, executes an algorithm. Some tasks naturally involve multiple parties. Think of a set of millionaires who are interested in knowing who is richer. Smart as they are the millionaires suggest the following protocol. They write their asset on a piece of paper. After all of them have written down a number, they show the paper to the audience. Simply by looking at the papers, each millionaire can verify who is the richest. Unfortunately, some of the milliionaires raise their concern. Those who rather are unwealthy fear discrimination, as the protocol leaks all assets. What the millionaires ideally would like is a protocol with an additional security guarantee. It shall keep every millionaire's asset private and reveal the name of the richest millionaire only.

The course is devoted to explore one of the fundamental questions in cryptography. How do multiple parties securely compute a function. The course will gradually introduce cryptographic concepts to answer the question, including

  • Secret Sharing
  • Oblivious Transfer
  • Commitments
  • Interactive, non-interactive, and succinct proof systems
  • (Threshold) Fully homomorphic encryption
  • Secure function evaluation/Garbled circuits
  • Multi-party computation 

What can I do with this knowledge?

Multi-party computation (MPC) is in a period of time, where digital information are a crucial asset, a powerful security technology. With MPC, for example, multiple service providers may compute a function without disclosing their data - their most valuable asset - to a competetor. The function may serve a statistical analysis or be a clever machine learning algorithm. With the knowledge of the course you will understand how to apply concrete MPC protocols to emerging technologies.

Rules of the Game

The intention of the workshop is to expand and fledge out your theoretical cryptography skill set. Sometimes theoretic concepts are complex and not easy to grasp. They require time, patience and continuity. You are given weekly reading assignments that shall prepare you for the class. You get an oral grade for your active engagement. You also summarize the theoretic concepts after the lecture. For your weekly short paper you get a written grade. The final grade is derrived from the weighted oral and written average grades

final grade := 0.5 * (average oral grade) + 0.5 * (average written grade)

Recommended Books

   
Jonathan Katz and Yehuda Lindell: Introduction to Modern Cryptography (2nd Edition)   Oded Goldreich: Foundations of Cryptography I   Oded Goldreich: Foundations of Cryptography II

Online Courses

You may want to have a look at the sunday&monday lectures of the 5th Bar-Ilan University school on advances in multi party computation.

Research Papers

  • Adi Shamir: How to share a secret. Communications of the ACM, 1979
  • Moni Naor and Benny Pinkas: Oblivious Polynomial Evaluation. STOC, 1990
  • Shafi Goldwasser, Silvio Micali, and Charles Rackoff: The knowledge complexity of interactive proof-systems. STOC, 1985
  • C.P. Schnorr: Efficient identification and signatures for smart cards. CRYPTO, 1989
  • Mihir Bellare, Oded Goldreich: On Defining Proofs of Knowledge. CRYPTO, 1992
  • Oded Goldreich and Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM Journal on Computing
  • Amos Fiat and Adi Shamir: How to Prove Yourself: Practical Solutions to the Identification and Signature Problem. CRYPTO, 1986
  • Ronald Cramer, Ivan Damgard, and Berry Schoenmakers: Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. CRYPTO, 1994
  • Nir Bitansky and Ran Canetti and Alessandro Chiesa and Shafi Goldwasser and Huijia Lin and Aviad Rubinstein and Eran Tromer: The Hunting of the SNARK. ITCS, 2012
  • Rosario Gennaro and Craig Gentry and Bryan Parno and Mariana Raykova: Quadratic Span Programs and Succinct NIZKs without PCPs. EUROCRYPT, 2013
  • Yehuda Lindell and Benny Pinkas: A Proof of Yao's Protocol for Secure Two-Party Computation. IACR Journal of Cryptology, 2009
  • Yehuda Lindell and Benny Pinkas: Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer. ePrint Archive: Report 2010/284
  • Gilad Asharov and Yehuda Lindell: A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation. ePrint Archive: Report 2011/136
  • Yuval IshaiManoj Prabhakaran and Amit Sahai: Founding Cryptography on Oblivious Transfer – Efficiently. CRYPTO, 2008
  • Yehuda Lindell: How To Simulate It - A Tutorial on the Simulation Proof Technique. ePrint Archive Report 2016/046
  • Adriana Lopez-Alt and Eran Tromer and Vinod Vaikuntanathan: On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption. STOC, 2012