Usable and Efficient Secure Multiparty Computation

Several interviews describe the usage of SMC to perform statistical computation. Cybernetica AS (CYB) is experimenting with the implementation of this functionality on the Sharemind platform and is evaluating the performance of the system with relatively big datasets (thousands of observations).

In particular, we are now implementing privacy preserving versions of t-tests and other aggregate statistics. In order to provide a "general" and "reusable" framework, KTH (Kungliga Tekniska Högskolan) started to formalize a small set of statistical APIs (in the style of R) that fixes the minimal-functionality required.

A further class of interesting problems is graph algorithms (e.g. shortest path and maximum flow). These problems can be solved by exploiting  linear programming, thus they provide  interesting benchmarks for different SMC techniques.

Our current strategy is:

1. implement problem-specific algorithm (e.g. Bellman-Ford) on top of the Sharemind platform;
2. estimate the cost of a "general" solution (e.g. gate estimation in the case of garbled circuits);
3. exploit a linear programming SMC technique (e.g. CYB is experimenting techniques based on genetic programming);
4. develop new algorithms that take benefit of application dependent
   properties.

Our long term goal is to compare the result of the above approaches, according with application specific constraints, in order to suggest the best strategy.