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.