Please note that this talk will be held over Zoom - Join the talk here: https://aarhusuniversity.zoom.us/j/63761669660

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

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.

Paper URL: https://eprint.iacr.org/2019/651

About the speaker: Muhammad Ishaq is a PhD student at University of Edinburgh: https://www.inf.ed.ac.uk/people/students/Muhammad_Ishaq.html  

About the seminar: The seminar is hosted by the Cryptography and Security Research Group at Aarhus University. The Aarhus Crypto Seminars are weekly seminar open to everyone with an interest in recent research in cryptology and information security. Further details about the research group and the weekly seminars can be found here: https://cs.au.dk/da/forskningsomraader/kryptografi-og-datasikkerhed/seminar/