Paper 2023/953

Towards Generic MPC Compilers via Variable Instruction Set Architectures (VISAs)

Yibin Yang, Georgia Institute of Technology
Stanislav Peceny, Georgia Institute of Technology
David Heath, University of Illinois Urbana-Champaign
Vladimir Kolesnikov, Georgia Institute of Technology
Abstract

In MPC, we usually represent programs as circuits. This is a poor fit for programs that use complex control flow, as it is costly to compile control flow to circuits. This motivated prior work to emulate CPUs inside MPC. Emulated CPUs can run complex programs, but they introduce high overhead due to the need to evaluate not just the program, but also the machinery of the CPU, including fetching, decoding, and executing instructions, accessing RAM, etc. Thus, both circuits and CPU emulation seem a poor fit for general MPC. The former cannot scale to arbitrary programs; the latter incurs high per-operation overhead. We propose variable instruction set architectures (VISAs), an approach that inherits the best features of both circuits and CPU emulation. Unlike a CPU, a VISA machine repeatedly executes entire program fragments, not individual instructions. By considering larger building blocks, we avoid most of the machinery associated with CPU emulation: we directly handle each fragment as a circuit. We instantiated a VISA machine via garbled circuits (GC), yielding constant-round 2PC for arbitrary assembly programs. We use improved branching (Stacked Garbling, Heath and Kolesnikov, Crypto 2020) and recent Garbled RAM (GRAM) (Heath et al., Eurocrypt 2022). Composing these securely and efficiently is intricate, and is one of our main contributions. We implemented our approach and ran it on common programs, including Dijkstra's and Knuth-Morris-Pratt. Our 2PC VISA machine executes assembly instructions at $300$Hz to $4000$Hz, depending on the target program. We significantly outperform the state-of-the-art CPU-based approach (Wang et al., ESORICS 2016, whose tool we re-benchmarked on our setup). We run in constant rounds, use $6\times$ less bandwidth, and run more than $40\times$ faster on a low-latency network. With $50$ms (resp. $100$ms) latency, we are $898\times$ (resp. $1585\times$) faster on the same setup. While our focus is MPC, the VISA model also benefits CPU-emulation-based Zero-Knowledge proof compilers, such as ZEE and EZEE (Heath et al., Oakland'21 and Yang et al., EuroS&P'22).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. CCS 2023
DOI
10.1145/3576915.3616664
Keywords
MPCGeneral Purpose ProgramsGarbled Circuits
Contact author(s)
yyang811 @ gatech edu
stan peceny @ gatech edu
daheath @ illinois edu
kolesnikov @ gatech edu
History
2024-02-04: last of 2 revisions
2023-06-18: received
See all versions
Short URL
https://ia.cr/2023/953
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/953,
      author = {Yibin Yang and Stanislav Peceny and David Heath and Vladimir Kolesnikov},
      title = {Towards Generic {MPC} Compilers via Variable Instruction Set Architectures ({VISAs})},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/953},
      year = {2023},
      doi = {10.1145/3576915.3616664},
      url = {https://eprint.iacr.org/2023/953}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.