Paper 2023/953
Towards Generic MPC Compilers via Variable Instruction Set Architectures (VISAs)
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
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
-
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} }