Paper 2019/651

Efficient MPC via Program Analysis: A Framework for Efficient Optimal Mixing

Muhammad Ishaq, Ana Milanova, and Vassilis Zikas


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.ACM CCS 2019
protocol mixinglinear programmingmultiparty computationprogram analysiscryptography
Contact author(s)
ishaq @ ishaq pk
2019-07-12: last of 5 revisions
2019-06-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Muhammad Ishaq and Ana Milanova and Vassilis Zikas},
      title = {Efficient MPC via Program Analysis: A Framework for Efficient Optimal Mixing},
      howpublished = {Cryptology ePrint Archive, Paper 2019/651},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.