Efficient MPC via program analysis: A framework for efficient optimal mixing

Muhammad Ishaq, Ana L. Milanova, Vassilis Zikas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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 languageEnglish
Title of host publicationCCS 2019: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security
PublisherACM Association for Computing Machinery
Number of pages18
ISBN (Electronic)9781450367479
Publication statusPublished - 6 Nov 2019
Event26th ACM SIGSAC Conference on Computer and Communications Security - London, United Kingdom
Duration: 11 Nov 201915 Nov 2019


Conference26th ACM SIGSAC Conference on Computer and Communications Security
Abbreviated titleCCS 2019
Country/TerritoryUnited Kingdom
Internet address

Keywords / Materials (for Non-textual outputs)

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


Dive into the research topics of 'Efficient MPC via program analysis: A framework for efficient optimal mixing'. Together they form a unique fingerprint.

Cite this