## Abstract

Multi-party computation (MPC) protocols have been extensively optimized in an effort to bring this technology to practice, which has already started bearing fruits. The choice of which MPC protocol to use depends on the computation we are trying to perform. Protocol mixing is an effective black-box -with respect to the MPC protocols-approach to optimize performance. Despite, however, considerable progress in the recent years existing works are heuristic and either give no guarantee or require an exponential (brute-force) search to find the optimal assignment, a problem which was conjectured to be NP hard. We provide a theoretically founded approach to optimal (MPC) protocol assignment, i.e., optimal mixing, and prove that under mild and natural assumptions, the problem is tractable both in theory and in practice for computing best two-out-of-three combinations. Concretely, for the case of two protocols, we utilize program analysis techniques-which we tailor to MPC-to define a new integer program, which we term the Optimal Protocol Assignment (in short, OPA) problem whose solution is the optimal (mixed) protocol assignment for these two protocols. Most importantly, we prove that the solution to the linear program corresponding to the relaxation of OPA is integral, and hence is also a solution to OPA. Since linear programming can be efficiently solved, this yields the first efficient protocol mixer. We showcase the quality of our OPA solver by applying it to standard benchmarks from the mixing literature. Our OPA solver can be applied on any two-out-of-three protocol combinations to obtain a best two-out-of-three protocol assignment.

Original language | English |
---|---|

Title of host publication | CCS 2019: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security |

Publisher | ACM Association for Computing Machinery |

Pages | 1539-1556 |

Number of pages | 18 |

ISBN (Electronic) | 9781450367479 |

DOIs | |

Publication status | Published - 6 Nov 2019 |

Event | 26th ACM SIGSAC Conference on Computer and Communications Security - London, United Kingdom Duration: 11 Nov 2019 → 15 Nov 2019 https://ccs19.swenjacobs.com/ |

### Conference

Conference | 26th ACM SIGSAC Conference on Computer and Communications Security |
---|---|

Abbreviated title | CCS 2019 |

Country/Territory | United Kingdom |

City | London |

Period | 11/11/19 → 15/11/19 |

Internet address |

## Keywords

- Cryptography
- Linear programming
- Multiparty computation
- Program analysis
- Protocol mixing