WAMPC, Day 2, Afternoon

A delegation of the Aarhus Crypto Group (Bernardo DavidTore FrederiksenClaudio OrlandiTomas Toft and Roberto Trifiletti) is attending the Workshop on Applied Multi-Party Computation and will attempt to cover this event on the MPCLounge.

We decided that timeliness is more important than perfection, and we therefore apologize for any mistake in these posts!

This is the last of a 4 post series.

First Session: Panel on the Business Case for MPC

Seny Kamara, Javier Salido, Vladimir Kolesnikov, Florian Kerschbaum

What are is the killer app for MPC?
The discussion starts by Florian considering the fact that companies do not want to trust cloud providers to outsource database storage or computations. This might be a setting where MPC could shine. The discussion is continued by Javier considering the privacy sensitive data a company holds. It turns out that companies in general only desires to obey the law in regards to storage of private data, which leads to the consideration that MPC might need to be forced upon the companies by legislation. However, legislations are made by lawyers, who do not know about MPC and thus it might be desirable to increase the amount of communication with lawyers.

The discussion continues by pointing out that companies might also need to use MPC in other settings, either as services directly to costumers or by the need to securely compute on data owned by other companies. Unfortunately when you start talking about MPC, ZK and commitments, IT folks at companies will start asking questions as they are only familiar with hashing, encryption, PKI, etc. and not protocols or advanced primitives. So it is very hard to convince them that MPC actually works and is secure. Furthermore, it is not trivial to use and implement crypto, and history teaches us that to avoid disasters one should not allow amateurs to implement crypto. Yehuda points out that real world projects and applications using MPC are on their way. Still, Florian points out that there are applications for existing companies which could be solved using MPC not being done because putting out new products is much harder than taking existing products and adding a layer of privacy and security.

Are there parts of the world that are better to get to adopt MPC?
The discussion starts by considering whether or not the Average Joe cares about the privacy of his personal data. It seems to depend on what the data is and how it is going to be used. Unfortunately it is not always clear what is being logged and how it is being used. Furthermore, it also depends on a cost/benefit analysis: what do I gain by giving away my private data versus what is the risk of giving away that data.  However, most people don’t think about that. Furthermore, it is hard to know what companies actually learn about you and what they use it for. So it will not be something that the average Joe is thinking about. Still, some places of Europe might be better at facilitating the usage of MPC compared to the US, due to a tradition of higher regulation of different fields (consider the Danish sugar beet auction).

What can we learn from other communities that desire security, e.g. databases.
It seems that other communities directly see the “money” and the products when they add security features. Javier points out that this was actually also the case for the crypto community in the 80’s where banks started to do electronic communications between each other. It seems that the conclusion is that we should consider direct products and features when considering the design of MPC.

What are the objections and roadblocks you (the panel) have met trying to promote MPC?
Javier experienced that people don’t seem to get the powers of MPC, and they only seem to be interested if they have an immediate problem that can be solved with MPC. So privacy and security is generally not something they desire to pay for. Vladimir experienced that the extra cost imposed by MPC is the main issue when discussing MPC with engineers. For them every cent matters. Florian claimed that you need a clear and concrete problem for people to actually desire to use MPC. Even if the company can actually save money by doing MPC it might not be enough if they already make money on an insecure system. You need to wait for companies to have a security problem and then quickly sell them MPC.

Second Session: Data-Oblivious Computation

How to Implement (ORAM in) MPC

Marcel Keller

Marcel’s talk was the first one to look at protocols based on secret sharing for arithmetic circuits, in a workshop otherwise dominated by Boolean circuits and garbled circuits. Marcel started by giving a brief overview of the celebrated SPDZ protocol. SPDZ is a offline/online protocol: in the offline phase many multiplications triples are generated in an efficient way  using (low) leveled FHE. As the preprocessing is independent of the the actual function/input (using the Beaver rerandomization trick) the preprocessing itself is very efficient and parallelizable. By turning this into an efficient protocol in practice is another story, and Marcel presented a number of issues that were addressed in his CCS 2013 paper such as how to compile a program into an arithmetic circuit with the lowest depth and highest amount of parallel operations, etc. 

Then Marcel went on to describe some recent results on implementing ORAM in MPC. Oblivious RAM is a very fascinating cryptographic primitive. Here is the scenario: a processor (with a small cache) wants to use an external, untrusted memory. Using “bread and butter” crypto it is possible to encrypt and authenticate the data stored on the RAM, so that the a corrupted memory cannot read/change the data read/wrote by the processor. But still the access pattern of the processor to the RAM might leak information about the flow of the program and its secret state! A trivial solution is to simply read the whole memory every time, and the goal of ORAM protocols is to do this with lower communication complexity. At least in theory, combining ORAM and MPC allows to securely evaluate RAM program, and that in many cases might be preferable to the standard “circuit” model of computation. Marcel went on showing how choosing the right ORAM (tree-based ORAM or path-ORAM by Shi et al.) and MPC protocol (SPDZ), this can actually be done efficiently, with applications to useful algorithms such as Dijkstra’s algorithm.

Secure Computation with Random Access Machines

Mariana Raykova

Mariana started again by saying how the RAM model of computation is more natural then the circuit based one, and it is in fact the model we use when we write code in our favourite programming language.

Moreover, if we wants to perform the same computation over and over again on the same input, using ORAM one can achieve sublinear secure computation (that is otherwise impossible using circuit evaluations). Think of a search in a sorted list: this can be done with only log n access to the ram, while if one uses a circuit the whole input must be read every time.

Mariana went on explaning a result that I found extremely fascinating: it is possible to perform an oblivious search in a sorted list using only 1 ORAM access! This is a really cool result and it would seem impossible (binary search requires log n in the plain!). But ORAM access already include a polylog factor, so by a clever organization of the memory and because the ORAM already has a tree-structure it is actually possible to do binary search with only one access.

The take home message is to try to integrate computation in the ORAM in RAM-based-MPC, and don’t discard low degree FHE, it can be useful and practical.

Obliv-C: A Lightweight Compiler for Data-Oblivious Computation

Samee Zahur

It should be easy for researchers to implement MPC, they should not have to reimplement their own compiler. Samee promises he is not going to just add a new standard to the mess, but he will actually solve some problem.

From xkcd.com

If you already have a C program it should be easy to wrap it into his language. Programmer have type system, you can define which variable will be hidden. Obliv-C should help benchmarking different protocols for the same problem, and easy prototyping. Performances are competitive, but the project still has some rough edges and missing features (floating point, logical operators, error reporting).

The project lives here: Obliv-C.

Third Session: Asynchronous & Broadcast-Efficient MPC

Broadcast (and Round) Efficient Secure Multiparty Computation

Juan Garay

This work deal with information theoretic MPC and how to achieve it efficiently. The talk introduced the share-compute-reveal paradigm of BGW and CCD and explains that multiplication of shares is the major bottleneck of these protocols and this requires communication, in particular broadcasts. Next the well know trick by using Beaver multiplication triples was explained which reduces the cost of mult. gate reduced to one reconstruction of a Verifiable Secret Sharing Scheme.

The goal of the work is to reduce the number of broadcast rounds for MPC for n > 2t, while minimizing overall no. rounds. The results they achieved is a VSS scheme with two broadcast rounds and constant overall rounds, which is the first VSS with these features. Their construction uses as building blocks a weak secret sharing scheme and information checking (an information theoretic signature like functionality). This enables them to get a 3 broadcast round VSS and they reach the 2 broadcast round scheme by using modercast to remove one of the broadcasts.

Due to time constraints the last part of the talk was quickly covered, but as a second result constant round pseudosignatures were achieved and together with the above VSS this can be combined in a general efficient MPC protocol.

Asynchronous MPC with t < n/2 Using Non-equivocation

Aniket Kate

The presentation considers how to achieve actively secure MPC where at most half of the parties are corrupted under the assumption that corrupted parties use non-equivocation. Non-equivocation is the case where a corrupt party supposed to do a broadcast, does not send the broadcast message to all the other parties. In particular he does not send anything for some of the parties. The specific contribution of the talk is an actively secure asynchronous MPC protocol with at most t<n/2 corrupted parties with O(n^3k) communication complexity assuming access to threshold signatures and non-equivocation. This improves on the result of [BHN10] which has communication complexity O(n^4k) and needs the additional assumptions of threshold homomorphic encryption.
The overall idea is first to construct transferability of non-equivocation using signatures. Specifically we add a signature to the messages that needs broadcast, so the party getting a broadcast message can then send it to the parties who did not get the message, which can verify the message using the signature. Using this a MPC protocol is constructed based on “supervised” Beaver triplets. These triplets reduces to “supervised” sharing, which is almost the same as verifiable secret sharing. These can then be constructed “relatively” easily.

Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation

Mahnush Movahedi

In the last talk of the workshop more Manush presented an asynchronous algorithm fro MPC in the setting of honest majority. On day one a different protocol based on quorums (also coauthored by Manush) was presented. The main difference seems to be that while in the first talk the authors were willing to settle with computational security, in today’s talk we are looking at an unconditional protocol. The setting is n players, and security should hold for any static and malicious adversary that corrupts up to 1/8 of the players. Using this protocol, it is possible to evaluate any function f over a field that can be computed by a circuit with m gates with communication and computational complexity O (m/n + sqrt n).

Some of the challenges in constructing protocols for asynchronous MPC is that one cannot wait for all inputs (or the adversary could stall the computation), so one needs to proceed after the threshold is reached. Manush presented a new data structure to efficiently count the number of inputs, called t-counter, which is roughly a binary tree, where messages are received in leafs and propagated up the tree. Every node only sends logarithmic number of messages

The MPC protocol proceeds by generating quorums of parties, and assigning each gate of the circuit to a specific quorum.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s