Paper 2017/981

Efficient Maliciously Secure Multiparty Computation for RAM

Marcel Keller and Avishay Yanai

Abstract

A crucial issue, that mostly affects the performance of actively secure computation of RAM programs, is the task of reading/writing from/to memory in a private and authenticated manner. Previous works in the active security and multiparty settings are based purely on the SPDZ (reactive) protocol, hence, memory accesses are treated just like any input to the computation. However, a garbled-circuit-based construction (such as BMR), which benefits from a lower round complexity, must resolve the issue of converting memory data bits to their corresponding wire keys and vice versa. In this work we propose three techniques to construct a secure memory access, each appropriates to a different level of abstraction of the underlying garbling functionality. We provide a comparison between the techniques by several metrics. To the best of our knowledge, we are the first to construct, prove and implement a concretely efficient garbled-circuit-based actively secure RAM computation with dishonest majority. Our construction is based on our third (most efficient) technique, cleverly utilizing the underlying SPDZ authenticated shares (Damgård et al., Crypto 2012), yields lean circuits and a constant number of communication rounds per physical memory access. Specifically, it requires no additional circuitry on top of the ORAM's, incurs only two rounds of broadcasts between every two memory accesses and has a multiplicative overhead of 2 on top of the ORAM's storage size. Our protocol outperforms the state of the art in this settings when deployed over WAN. Even when simulating a very conservative RTT of 100ms our protocol is at least one order of magnitude faster than the current state of the art protocol of Keller and Scholl (Asiacrypt 2015).

Note: Updated acknowledgments and moved to the front

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Multiparty computationoblivious RAMgarbled circuits
Contact author(s)
ay yanay @ gmail com
History
2017-12-26: last of 2 revisions
2017-10-09: received
See all versions
Short URL
https://ia.cr/2017/981
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/981,
      author = {Marcel Keller and Avishay Yanai},
      title = {Efficient Maliciously Secure Multiparty Computation for {RAM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/981},
      year = {2017},
      url = {https://eprint.iacr.org/2017/981}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.