Secure Protocol Transformations

Abstract

In the rich literature of secure multi-party computation MPC, several important results rely on whereby protocols from one model of MPC are transformed to protocols from another model. Motivated by the goal of simplifying and unifying results in the area of MPC, we formalize a general notion of black-box protocol transformations that captures previous transformations from the literature as special cases, and present several new transformations. We motivate our study of protocol transformations by presenting the following applications. Simplifying feasibility results:Easily rederive a result in Goldreich's book 2004, on MPC with full in the presence of an honest majority, from an earlier result in the book, on MPC that offers security with abort.Rederive the classical result of Rabin and Ben-Or 1989 by applying a transformation to the simpler protocols of Ben-Or et al. or Chaum et al. 1988.Efficiency improvements:The first constant-rate MPC protocol for a constant number of parties that offers full information-theoretic with an optimal threshold, improving over the protocol of Rabin and Ben-Or;A fully secure MPC protocol with optimal threshold that improves over a previous protocol of Ben-Sasson et al. 2012 in the case of deep and narrow computations;A fully secure MPC protocol with near-optimal threshold that improves over a previous protocol of Damgard et al. 2010 by improving the dependence on the parameter from linear to polylogarithmic;An efficient new transformation from passive-secure two-party computation in the OT-hybrid and OLE-hybrid model to zero-knowledge proofs, improving over a recent similar transformation of Hazay and Venkitasubramaniam 2016 for the case of static zero-knowledge, which is restricted to the OT-hybrid model and requires a large number of commitments. Finally, we prove the impossibility of two simple types of black-box protocol transformations, including an unconditional variant of a previous negative result of Rosulek 2012 that relied on the existence of one-way functions.