Paper 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.The 16th International Conference on Applied Cryptography and Network Security, ACNS 2018
Keywords
secure computationmulti-party computation (MPC)oblivious RAM (ORAM)
Contact author(s)
stanislawjarecki @ gmail com
History
2018-04-16: received
Short URL
https://ia.cr/2018/347
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/347,
      author = {Stanislaw Jarecki and Boyang Wei},
      title = {3PC ORAM with Low Latency, Low Bandwidth, and Fast Batch Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2018/347},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/347}},
      url = {https://eprint.iacr.org/2018/347}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.