Cryptology ePrint Archive: Report 2016/815

Secure Multiparty RAM Computation in Constant Rounds

Sanjam Garg and Divya Gupta and 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.

Category / Keywords: Secure computation, RAM computation, Garbled RAM

Original Publication (with minor differences): IACR-TCC-2016

Date: received 23 Aug 2016, last revised 26 Aug 2016

Contact author: sanjamg at berkeley edu, divyagupta iitd at gmail com, peihan at berkeley edu, omkant at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160826:191237 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]