Paper 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 CPU. We describe an implementation of 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. 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.

Note: Update to full version of publication

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. Latincrypt 2017
DOI
10.1007/978-3-030-25283-0_15
Keywords
Multiparty computationrandom-access machineoblivious RAMcompilersregular expression matching
Contact author(s)
mks keller @ gmail com
History
2019-07-23: last of 2 revisions
2015-05-18: received
See all versions
Short URL
https://ia.cr/2015/467
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/467,
      author = {Marcel Keller},
      title = {The Oblivious Machine - or: How to Put the C into MPC},
      howpublished = {Cryptology ePrint Archive, Paper 2015/467},
      year = {2015},
      doi = {10.1007/978-3-030-25283-0_15},
      note = {\url{https://eprint.iacr.org/2015/467}},
      url = {https://eprint.iacr.org/2015/467}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.