International Association
for Cryptologic Research

We present the oblivious machine, a concrete notion for 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 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 implemented our construction using the clang compiler from the LLVM

project and the SPDZ protocol by Damgård 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 2^20 integers. Both timings have been taken

for two parties in a local network.

To further showcase our toolchain, we implemented and benchmarked

private regular expression matching. 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.