You are looking at a specific version 20201006:093131 of this paper. See the latest version.

Paper 2020/1195

A Lower Bound for One-Round Oblivious RAM

David Cash and Andrew Drucker and Alexander Hoover

Abstract

We initiate a fine-grained study of the round complexity of Oblivious RAM (ORAM). We prove that any one-round balls-in bins ORAM that does not duplicate balls must have either \Omega(\sqrt{N}) bandwidth or \Omega(\sqrt{N}) client memory, where N is the number of memory slots being simulated. This shows that such schemes are strictly weaker than general (multi-round) ORAMs or those with server computation, and in particular implies that a one-round version of the original square-root ORAM of Goldreich and Ostrovksy (J. ACM 1996) is optimal. We prove this bound via new techniques that differ from those of Goldreich and Ostrovksy, and of Larsen and Nielsen (CRYPTO 2018), which achieved an \Omega(\log N) bound for balls-in-bins and general multi-round ORAMs respectively. Finally we give a weaker extension of our bound that allows for limited duplication of balls, and also show that our bound extends to multiple-round ORAMs of a restricted form that include the best known constructions.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2020
Keywords
oramlower boundround complexity
Contact author(s)
davidcash @ uchicago edu,alexhoover @ uchicago edu
History
2020-10-06: received
Short URL
https://ia.cr/2020/1195
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.