Workshop on Applied Multi-Party Computation (February 20-21, 2014, MSR Redmond)

Seny Kamara and Payman Mohassel are organizing a workshop on Applied MPC next February in Redmond.

Note that the workshop is conveniently scheduled right before TCC 2014.

Here is the announcement:

Dear Colleagues,

 This is to announce the upcoming Workshop on Applied Multi-Party Computation which will be held on February 20th and 21st, 2014 at Microsoft Research in Redmond.

 MPC has been an active area of research of cryptography for over 30 years. The last decade has witnessed significant interest and advances in the applied aspects of MPC. This workshop will bring together researchers in security and cryptography to discuss recent advances, challenges and research directions related to applied secure computation.

 The workshop will consist of invited keynote presentations, contributed presentations and round-table discussions on all aspects of applied secure computation. A detailed program describing the talks and discussion topics will be announced closer to the date of the workshop.

 Additional information

 Call for Contributions: The workshop will include contributed presentations. If interested in presenting your work, please send an abstract of your proposed talk to Seny Kamara and Payman Mohassel by November 15th, 2013. There will be no proceedings. 

 Registration: The workshop is open to all, however space is limited, and we need an accurate count of those attending. If you are interested in attending, please email the organizers. There will be no registration fee.

 Organizers: Seny Kamara ( and Payman Mohassel (

 Dates: February 20th and 21st, 2014

 Location: Microsoft Research, Redmond

Efficient Secure Computation at Eurocrypt 2013

There were multiple presentations about secure multi-party computation at Eurocrypt 2013. I’ll describe here only a few of these talks.

Tore Frederiksen presented work on “MiniLEGO: Efficient Secure Two-Party Computation From General Assumptions”, coauthored with Thomas P. Jakobsen, Jesper Buus Nielsen, Peter Sebastian Nordholt and Claudio Orlandi, all from Aarhus University, Denmark. This work builds on the LEGO paper of Nielsen and Orlandi from TCC 2009. That work presented a secure two-party protocol that applied the cut-and choose technique at the gate level, where one party generates many gates and the other party checks some of the gates and uses the others. A main technical challenge is how to connect together the gates that are chosen to be used. The original LEGO paper solved this problem by relying on a specific number-theoretic assumption and using public-key operations per gate. The new paper connects gates using a new XOR-homomorphic commitment scheme based on linear error correcting codes and oblivious transfer. The entire construction is therefore based on symmetric primitives, except for the few seed OTs needed to bootstrap the OT extension.

Saeed Sadeghian presented his work with Payman Mohassel on “How to Hide Circuits in MPC: An Efficient Framework for Private Function Evaluation”. The goal of this work is to obtain Private Function Evaluation (PFE), where privacy here means that the computation hides the function that is computed (in the sense that both the wiring of the circuit and the gates are kept hidden). Valiant have shown that every circuit with |C| gates can be computed by a universal circuit of size O(|C| log|C|). PFE can also be based on a fully homomorphic encryption scheme. Katz and Malka designed a two-party PFE protocol based on a singly homomorphic encryption, that uses O(|C|) public-key operations.
The new work presents a general framework in the semi-honest (passive) adversary setting. The results are for 2PC and MPC, and for both binary and arithmetic circuits. A major tool that is used is oblivious switching networks, that are based on the use of OT (which in turn can be extended and use mostly symmetric key operations). Private switching based on this tool is then applied to the Yao, GMW and CDN01 protocols.

Hoeteck Wee presented joint work with Dov Gordon, Tal Malkin and Mike Rosulek on “Multi-Party Computation of Polynomials and Branching Programs without Simultaneous Interaction”. The paper extends the results of  Halevi et al. on secure one-pass protocols, that introduced this type of protocols and showed how to implement them for computing  symmetric functions and choice functions (as well as presenting a generic but less practical protocol). The current work presents one-pass protocols for computing sparse multivariate polynomials, which can be used for computing statistic functions such as the variance, and for computing read-once branching programs, which can used for computing functions such as string matching, finite automata, and second price auctions. A major limiting factor of the new construction is that, unlike the previous work, the order of the participants needs to be known in advance, or computed on the fly.

Steve Lu presented his work with Rafi Ostrovsky titled “How to Garble RAM Programs”. This truly interesting work presents a secure two-party protocol where the two parties mimic a computation on a RAM machine, without converting the RAM programs into circuits. The protocol that is run is non-interactive. Each access to the RAM is implemented using oblivious RAM (ORAM), where the ORAM needs to access locations that depend on the index of the looked item and are unknown at “compilation” time. In order to achieve this property without interaction, the protocol implements at Step j a circuit that constructs the circuit for Step j+1 and encodes in it the locations that will be accessed.