Secure Multi-Party Computation with Identifiable Abort

Result by Yuval Ishai, Rafail Ostrovsky and Vassilis Zikas
Blog written by Roberto Trifiletti

First talk of the first Secure Computation session was by Vassilis Zikas who was presenting the paper “Secure Multi-Party Computation with Identifiable Abort” with coauthors Yuval Ishai and Rafail Ostrovsky.
As the title says the topic was MPC with identifiable abort (ID-MPC). Vassilis started out explaining the goals of general MPC, namely computing a function on joint input, while guaranteeing that only the output is revealed to each party. The following history of MPC was mapped out:
– In the 1980s the foundations of MPC was explored and established.
– In the 1990s major asymptotic advances was made.
– And in the 21st century implementations and practical MPC saw the light of day.

However Vassilis stressed that most of the research in the area of MPC has ignored the problem of abort. It is folklore that for general MPC it is impossible to withstand active premature abort. This has had the effect that most work on practical MPC only deliver security with abort, meaning the adversary can abort the protocol at any time, in particular when he learns the output and before the honest parties do (no fairness). Many MPC protocols do not even have mechanisms to identify which party caused the abort. Since the honest parties in this case have no way of knowing which party to either exclude or repair the only strategy is to start over from scratch. However the same party can cause an abort repeatedly in each execution which effectively imposes a DoS attack on the computation.

This work aims to address the above scenario by providing MPC protocols with identifiable abort, meaning if a party causes the protocol to abort the rest of the parties learns his identity and can take appropriate action. Clearly this eliminates the DoS attack sketched above.

An earlier result from [IOS12] shows that Information Theoretic (IT) ID-MPC cannot be achieved assuming OT alone. In fact it was shown that any type of pairwise correlated randomness is insufficient. In the computational setting, the GMW protocol (with a twist) [CDN01] is known to deliver ID-MPC. However this protocol is inherently non-black box and uses public key primitives for each gate of the circuit, so it is not suitable for implementation.
The work has two major contributions:
– Construct first IT ID-MPC assuming n-wise correlated randomness. In particular presents a compiler taking a semi-honest IT MPC protocol the in correlate randomness (CR) model as input and outputting a IT secure ID-MPC protocol in the CR model.
– Computationally secure ID-MPC using an OT protocol in a black-box manner. In particular a compiler taking an IT ID-MPC in the CR model as input and outputting a computational ID-MPC scheme.

The first IT compiler can be thought of as the ID-MPC equivalent of the GMW compiler. It makes use of a one-to-many commitment scheme instantiated using IT signatures with distributed verification keys [SHZI02, SS11] and IT ZK proofs which in turn are constructed using the IPS paradigm.

The second compiler makes BB use of the OT protocol to implement the sampling procedure (setup) step of the input IT ID-MPC protocol. Thus it is the input IT ID-MPC protocol that is being run, but the initial setup phase is instantiated using the (computational) BB OT protocol. Thus the resulting protocol is computationally secure.

As final remarks it was highlighted that this work presents the first IT ID-MPC protocol from n-wise correlated randomness, where before it was only known that it was impossible from 2-wise. Open problems include looking for more efficient solutions, implement the current ones and compare, and investigating if indeed n-wise correlation is required, or perhaps n-1-wise correlation could be sufficient.


Leave a Reply

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

You are commenting using your 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