eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2020/997

Alibi: A Flaw in Cuckoo-Hashing based Hierarchical ORAM Schemes and a Solution

Brett Hemenway Falk, Daniel Noble, and Rafail Ostrovsky

Abstract

There once was a table of hashes That held extra items in stashes It all seemed like bliss But things went amiss When the stashes were stored in the caches The first Oblivious RAM protocols introduced the ``hierarchical solution,'' (STOC '90) where the servers store a series of hash tables of geometrically increasing capacities. Each ORAM query would read a small number of locations from each level of the hierarchy, and each level of the hierarchy would be reshuffled and rebuilt at geometrically increasing intervals to ensure that no single query was ever repeated twice at the same level. This yielded an ORAM protocol with polylogarithmic overhead. Future works extended and improved the hierarchical solution, replacing traditional hashing with cuckoo hashing (ICALP '11) and cuckoo hashing with a combined stash (Goodrich et al. SODA '12). In this work, we identify a subtle flaw in the protocol of Goodrich et al. (SODA '12) that uses cuckoo hashing with a stash in the hierarchical ORAM solution. We give a concrete distinguishing attack against this type of hierarchical ORAM that uses cuckoo hashing with a combined stash. This security flaw has propagated to at least 5 subsequent hierarchical ORAM protocols, including the recent optimal ORAM scheme, OptORAMa (Eurocrypt '20). In addition to our attack, we identify a simple fix that does not increase the asymptotic complexity. We note, however, that our attack only affects more recent hierarchical ORAMs, but does not affect the early protocols that predate the use of cuckoo hashing, or other types of ORAM solutions (e.g. Path ORAM or Circuit ORAM).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in EUROCRYPT 2021
Keywords
oblivious rammultiparty computation
Contact author(s)
dgnoble @ cis upenn edu
fbrett @ cis upenn edu
rafail @ cs ucla edu
History
2021-03-23: last of 6 revisions
2020-08-18: received
See all versions
Short URL
https://ia.cr/2020/997
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/997,
      author = {Brett Hemenway Falk and Daniel Noble and Rafail Ostrovsky},
      title = {Alibi: A Flaw in Cuckoo-Hashing based Hierarchical ORAM Schemes and a Solution},
      howpublished = {Cryptology ePrint Archive, Paper 2020/997},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/997}},
      url = {https://eprint.iacr.org/2020/997}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.