CRYPTO 2014 rump session

from The MPC Lounge

Aug 20, 2014, 9:29:30 PM

The rump session at CRYPTO had plenty of talks in many subfields of cryptology, and secure computation was no exception. The part of the rump session concerned with MPC was started by Xiao Shaun Wang discussing “Circuit ORAM and on the Tightness of the Goldreich-Ostrovsky ORAM Lower Bound”. In particular he discussed an implementation (co-authored with T-H. Hubert Chan and Elaine Shi) of circuit ORAM, based on the JustGarble framework. This approach yields great improvements (up to a factor 48x on 1 GB data) over implementations based on path ORAM.
Xiao’s talk was followed by Kartik Nayak discussing “Oblivious data structures”. Kartik considers the problem of data access overhead using an ORAM. Specifically the overhead is data transferred in the oblivious case divided by data transferred in non-oblivious case. The best known result is O(log^2 (N)/ log log (N)) overhead [KLO’12]. Kartik and his co-authors (Xiao Shaun Wang, Chang Liu, T-H. Hubert Chan, Elaine Shi, Emil Stefanov, Yan Huang) manages to improve on this result for restricted access patterns. Such patterns include proximity and bounded degree trees. Such patterns reflect how data is generally accessed in most computer programs and algorithms. An open source implementation using garbled circuits as a backend is currently being implemented by the authors.
Xiao Shaun Wang returns to the stage to continue the talk on ORAM by presenting “SCVM: An Efficient, Automated RAM Model Secure Computation Framework”. The goal of SCVM is to make it possible for non-expert programmers to program secure computation tasks in a matter of hours. The SCVM system ensures security through a type system and is supposed to offer competitive efficiency to customized circuits for a large class of functions. More specifically, the system is as follows: the programmer makes a program in a source language which is then passed to a frontend compiler. The output of the compiler is then a SCVM intermediate representation which is then passed to a backend compiler. The compilers implement several compile time optimizations and the whole system is going to yield support for rich library functions such as data structures, machine learning and graph algorithms. Like in the previous presentations, the SCVM is based on ORAM using garbled circuits as a backend.
Next up was Wutichai Chongchitmate describing how to do “Optimally Resilient and Adaptively Secure MPC with Low Communication Locality”. The project (joint work with Nishanth Chandran, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, Vassilis Zikas) considers how to do MPC with many, many parties while retaining low communication complexity. Chongchitmate explains that this is possible to achieve, even in the case of a dishonest majority, controlled by an adaptive adversary. The core idea is to encode communication patterns into a symmetric key infrastructure, in particular having every party use his symmetric keys to decide on his set of neighbors. Then expander graphs are used to show that it is infeasible for an adaptive adversary to discover these patterns and disconnect two honest parties.
Afterwards Tore Frederiksen and Roberto Trifiletti discussed their work in progress (co-authored with Thomas Jakobsen and Jesper Nielsen) on practical optimizations of the LEGO paradigm for secure computation. The idea of Lego is to use garbled gates to get maliciously secure two-party computation, but instead of doing cut-and-choose on entire garbled circuits, cut-and-choose is done on individual gates. Non-checked gates are then combined to construct a single fault-tolerant garbled circuit. However, putting individual gates together is expensive so Tore and Roberto highlighted some new approaches for doing this, yielding much smaller constants than given in the previous Lego works.
The next speaker was Mike Rosulek who described a new webpage project for summaries of papers in MPC. In particular the summaries are short and easily readable and in particular aimed for first year Ph.D. students and other people with basic knowledge about crypto and an interest in MPC. Currently the site contains 30 paper and a glossary, but the hope is to keep the site community driven. If you want a look or submit a summery then navigate your browser to
The summaries above include the most MPC relevant talks, however, the rump session contained many other interesting talks with applications to MPC. If you wish to have a look at the titles and slides then navigate to