COMBINE: COMpilation and Backend-INdependent vEctorization for Multi-Party Computation

Benjamin Levy; Muhammad Ishaq; Ben Sherman; Lindsey Kennard; Ana Milanova; Vassilis Zikas

Paper 2023/089

COMBINE: COMpilation and Backend-INdependent vEctorization for Multi-Party Computation

Benjamin Levy

, Rensselaer Polytechnic Institute

Muhammad Ishaq

, Purdue University West Lafayette

Ben Sherman

, Rensselaer Polytechnic Institute

Lindsey Kennard

, STR

Ana Milanova

, Rensselaer Polytechnic Institute

Vassilis Zikas

, Purdue University West Lafayette

Abstract

Recent years have witnessed significant advances in programming technology for multi-party computation (MPC), bringing MPC closer to practice and wider applicability. Typical MPC programming frameworks focus on either front-end language design (e.g., Wysteria, Viaduct, SPDZ), or back-end protocol implementation (e.g., ABY, MOTION, SPDZ). We propose a methodology for an MPC compilation toolchain, which by mimicking the compilation methodology of classical compilers enables middle-end (i.e., machine-independent) optimizations, yielding significant improvements. We advance an intermediate language, which we call MPC-IR that can be viewed as the analogue of (enriched) Static Single Assignment (SSA) form. MPC-IR enables backend-independent optimizations in a close analogy to machine-independent optimizations in classical compilers. To demonstrate 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. To demonstrate backend independence and quality of our optimization, we evaluate our approach with two mainstream backend frameworks that support multiple types of MPC protocols, namely MOTION and MP-SPDZ, and show significant improvements across the board.

Note: minor typos fixed to improve readability

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. Major revision. ACM Conference on Computer and Communications Security (CCS) 2023
DOI: 10.1145/3576915.3623181
Keywords: applied cryptography program and binary analysis systems security multiparty computation compilers
Contact author(s): levb3 @ rpi edu
ishaqm @ purdue edu
shermb @ rpi edu
fireelemental ne @ gmail com
milanova @ cs rpi edu
vzikas @ purdue edu
History: 2023-12-20: last of 8 revisions; 2023-01-24: received; See all versions
Short URL: https://ia.cr/2023/089
License: CC BY

BibTeX

@misc{cryptoeprint:2023/089,
      author = {Benjamin Levy and Muhammad Ishaq and Ben Sherman and Lindsey Kennard and Ana Milanova and Vassilis Zikas},
      title = {{COMBINE}: {COMpilation} and Backend-{INdependent} {vEctorization} for Multi-Party Computation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/089},
      year = {2023},
      doi = {10.1145/3576915.3623181},
      url = {https://eprint.iacr.org/2023/089}
}