Paper 2016/815

Secure Multiparty RAM Computation in Constant Rounds

Sanjam Garg, Divya Gupta, Peihan Miao, and Omkant Pandey

Abstract

Securing computation of a random access machine (RAM) program typically entails that it be first converted into a circuit. This conversion is unimaginable in the context of big-data applications where the size of the circuit can be exponential in the running time of the original RAM program. Realizing these constructions, without relinquishing the efficiency of RAM programs, often poses considerable technical hurdles. Our understanding of these techniques in the multi-party setting is largely limited. Specifically, the round complexity of all known protocols grows linearly in the running time of the program being computed. In this work, we consider the multi-party case and obtain the following results: 1. Semi-honest model: We present a constant-round black-box secure computation protocol for RAM programs. This protocol is obtained by building on the new black-box garbled RAM construction by Garg, Lu, and Ostrovsky [FOCS 2015], and constant-round secure computation protocol for circuits of Beaver, Micali, and Rogaway [STOC 1990]. This construction allows execution of multiple programs on the same persistent database. 2. Malicious model: Next, we show how to extend our semi-honest results to the malicious setting, while ensuring that the new protocol is still constant-round and black-box in nature.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in TCC 2016
Keywords
Secure computationRAM computationGarbled RAM
Contact author(s)
sanjamg @ berkeley edu
divyagupta iitd @ gmail com
peihan @ berkeley edu
omkant @ gmail com
History
2016-08-26: last of 2 revisions
2016-08-26: received
See all versions
Short URL
https://ia.cr/2016/815
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/815,
      author = {Sanjam Garg and Divya Gupta and Peihan Miao and Omkant Pandey},
      title = {Secure Multiparty RAM Computation in Constant Rounds},
      howpublished = {Cryptology ePrint Archive, Paper 2016/815},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/815}},
      url = {https://eprint.iacr.org/2016/815}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.