Paper 2020/139

Going Beyond Dual Execution: MPC for Functions with Efficient Verification

Carmit Hazay, abhi shelat, and Muthuramakrishnan Venkitasubramaniam


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 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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2020
Secure ComputationSemi-honest SecurityDual ExecutionGreedy Algorithms
Contact author(s)
carmit hazay @ biu ac il
abhi @ neu edu
muthuv @ cs rochester edu
2020-02-10: received
Short URL
Creative Commons Attribution


      author = {Carmit Hazay and abhi shelat and Muthuramakrishnan Venkitasubramaniam},
      title = {Going Beyond Dual Execution: MPC for Functions with Efficient Verification},
      howpublished = {Cryptology ePrint Archive, Paper 2020/139},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.