## Cryptology ePrint Archive: Report 2015/467

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

Marcel Keller

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 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. Similar work by other authors has only been in the semi-honest setting.

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.

Category / Keywords: cryptographic protocols / Multiparty computation, random-access machine, oblivious RAM, compilers, regular expression matching

Date: received 17 May 2015, last revised 13 Nov 2015

Contact author: m keller at bristol ac uk

Available format(s): PDF | BibTeX Citation

Note: Minor revisions.

Short URL: ia.cr/2015/467

[ Cryptology ePrint archive ]