The Oblivious Machine or: How to Put the C into MPC

Abstract. We present an oblivious machine, a concrete notion for a multiparty random access machine (RAM) computation and a toolchain to allow the efficient execution of general programs written in a subset of C that allows RAM-model computation over the integers. The machine only leaks the list of possible instructions and the running time. Our work is based on the oblivious array for secret-sharing-based multiparty computation by Keller and Scholl (Asiacrypt ‘14). This means that we only incur a polylogarithmic overhead over the execution on a normal CPU. We describe an implementation of our construction using the Clang compiler from the LLVM project and the SPDZ protocol by Damg̊ard et al. (Crypto ‘12). The latter provides active security against a dishonest majority and works in the preprocessing model. The online phase clock rate of the resulting machine is 41 Hz for a memory size of 1024 64-bit integers and 2.2 Hz for a memory of 220 integers. Both timings have been taken for two parties in a local network. Similar work by other authors has only been the semi-honest setting. To further showcase our toolchain, we implemented and benchmarked private regular expression match-ing. Matching a string of length 1024 against a regular expression with 69270 transitions as a finite state machine takes seven hours online time, of which more than six hours are devoted to loading the reusable program