Cryptology ePrint Archive: Report 2018/347

3PC ORAM with Low Latency, Low Bandwidth, and Fast Batch Retrieval

Stanislaw Jarecki and Boyang Wei

Abstract: Multi-Party Computation of Oblivious RAM (MPC ORAM) implements secret-shared random access memory in a way that protects access pattern privacy against a threshold of corruptions. MPC ORAM enables secure computation of any RAM program on large data held by different entities, e.g. MPC processing of database queries on a secret-shared database. MPC ORAM can be constructed by any (client-server) ORAM, but there is an efficiency gap between known MPC ORAM's and ORAM's. Current asymptotically best MPC ORAM is implied by an "MPC friendly" variant of Path-ORAM called Circuit-ORAM, due to Wang et al. However, using garbled circuit for Circuit-ORAM's client implies MPC ORAM which matches Path-ORAM in rounds but increases bandwidth by \Omega(kappa) factor, while using GMW or BGW protocols implies MPC ORAM which matches Path-ORAM in bandwidth, but increases round complexity by \Omega(log n loglog n) factor, for kappa the security parameter and n the memory size.

In this paper we bridge the gap between MPC ORAM and client-server ORAM by showing a specialized 3PC ORAM protocol, i.e. MPC ORAM for 3 parties tolerating 1 fault, which uses only symmetric ciphers and asymptotically matches client-server Path-ORAM in round complexity and for large records also in bandwidth.

Our 3PC ORAM also allows for fast pipelined processing: With post- poned clean-up it processes b=O(log n) accesses in O(b+log n) rounds with O(D+poly(log n)) bandwidth per item, where D is record size.

Category / Keywords: cryptographic protocols / secure computation, multi-party computation (MPC), oblivious RAM (ORAM)

Original Publication (with major differences): The 16th International Conference on Applied Cryptography and Network Security, ACNS 2018

Date: received 13 Apr 2018

Contact author: stanislawjarecki at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180416:212720 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]