Welcome to the resource topic for 2023/089
Title:
Compilation and Backend-Independent Vectorization for Multi-Party Computation
Authors: Benjamin Levy, Ben Sherman, Muhammad Ishaq, Lindsey Kennard, Ana Milanova, Vassilis Zikas
Abstract:Recent years have witnessed a push to bring multi-party computation (MPC) to practice and make it accessible to the end user/programmer. Despite novel ideas, on frontend language design (e.g., Wysteria, Viaduct), backend protocol design and implementation (e.g., ABY, MOTION), or both (e.g., SPDZ), classical compiler optimizations remain largely under-utilized (if not completely unused) in MPC programming. A likely reason is that such optimizations are often applied on a middle-end intermediate representation such as SSA.
We put forth a methodology for an MPC programming compilation toolchain, which by mimicking the compilation methodology of standard imperative languages enables middle-end optimizations on MPC, yielding significant improvements. To this direction we devise an MPC circuit compiler that allows MPC programming in what is essentially Python, and inherits the structure (and therefore optimization opportunities) of the classical compilation pipeline. Our key conceptual contribution is advancing an intermediate language, which we call MPC-IR, that can be viewed as the analogue, in an MPC program’s compilation, of (enriched) SSA form. MPC-IR is a particularly appealing intermediate language as it allows backend-independent optimizations, a close analogy to machine independent optimizations in classical compilers. Demonstrating the power of our approach, we focus on a specific
backend-independent optimization, SIMD-vectorization: We devise a novel classical-compiler-inspired automatic SIMD-vectorization on MPC-IR, which we show leads to significant speedup in circuit generation time and running time, as well as significant reduction in communication size and number of gates over the corresponding iterative schedule.
We implement and benchmark our compiler from a Python-like program to an optimized circuit that can be fed into an MPC backend (for our benchmarks we make use of the MOTION backend for MPC). We view our exhaustive benchmarks as both a way to validate our optimization and end-to-end compiler, and as a contribution, by itself, to a more complete benchmarks suite for MPC programming—such benchmarks suites are common in classical compilers.
ePrint: https://eprint.iacr.org/2023/089
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .