## Going Beyond Dual Execution: MPC for Functions with Efficient Verification

```
@inproceedings{hsv20,
title = {Going Beyond Dual Execution: MPC for Functions with Efficient Verification},
author = {Carmit Hazay and abhi shelat and Muthu Venkitasubramaniam},
howpublished = {PKC'20},
year = {2020},
}
```

The *dual execution* paradigm of Mohassel and Franklin (PKC'06) and Huang, Katz and Evans (IEEE ‘12) shows how
to achieve the notion of *1-bit leakage* security at roughly twice the cost of semi-honest security for the special case of *two-party secure computation*. To date, there are no multi-party computation (MPC) protocols that offer such a strong trade-off between security and semi-honest performance.

Our main result is to address this shortcoming by designing 1-bit leakage protocols for the multi-party setting, albeit for a special class of functions. We say that function $f(x,y)$ is *efficiently verifiable by* $g$ if the running time of $g$ is always smaller than $f$ and $g(x,y,z)=1$ if and only if $f(x,y)=z$.

In the two-party setting, we first improve *dual execution* by observing that the second execution can be an evaluation of $g$ instead of $f$, and that by definition, the evaluation of $g$ is asymptotically more efficient. Our techniques apply to problems as varied as matrix multiplication, optimization problems such as max-flow, and minimum spanning tree.

Our main MPC result is to construct a 1-bit leakage protocol for such functions from any passive protocol for $f$ that is *secure up to additive errors* and any active protocol for $g$. An important result by Genkin et al. (STOC ‘14) shows how the classic protocols by Goldreich et al. (STOC ‘87) and Ben-Or et al. (STOC ‘88) naturally support this property, which allows to instantiate our compiler with two-party and multi-party protocols.

A key technical result we prove is that the passive protocol for distributed garbling due to Beaver et al. (STOC ‘90) is in fact *secure up to additive errors* against malicious adversaries, thereby, yielding another powerful instantiation of our paradigm in the constant-round multi-party setting.

As another concrete example of instantiating our approach, we present a novel protocol for computing *perfect matching* that is secure in the 1-bit leakage model and whose communication complexity is less than the honest-but-curious implementations of textbook algorithms for perfect matching.