Paper 2017/586

Deterministic, Stash-Free Write-Only ORAM

Daniel S. Roche, Adam J. Aviv, Seung Geol Choi, and Travis Mayberry

Abstract

Write-Only Oblivious RAM (WoORAM) protocols provide privacy by encrypting the contents of data and also hiding the pattern of write operations over that data. WoORAMs provide better privacy than plain encryption and better performance than more general ORAM schemes (which hide both writing and reading access patterns), and the write-oblivious setting has been applied to important applications of cloud storage synchronization and encrypted hidden volumes. In this paper, we introduce an entirely new technique for Write-Only ORAM, called DetWoORAM. Unlike previous solutions, DetWoORAM uses a deterministic, sequential writing pattern without the need for any "stashing" of blocks in local state when writes fail. Our protocol, while conceptually simple, provides substantial improvement over prior solutions, both asymptotically and experimentally. In particular, under typical settings the DetWoORAM writes only 2 blocks (sequentially) to backend memory for each block written to the device, which is optimal. We have implemented our solution using the BUSE (block device in user-space) module and tested DetWoORAM against both an encryption only baseline of dm-crypt and prior, randomized WoORAM solutions, measuring only a 3x-14x slowdown compared to an encryption-only baseline and around 6x-19x speedup compared to prior work.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Proc. ACM Conf. on Computer and Communications Security (CCS) 2017
DOI
10.1145/3133956.3134051
Keywords
cryptographic protocolsORAM
Contact author(s)
roche @ usna edu
History
2017-09-07: revised
2017-06-20: received
See all versions
Short URL
https://ia.cr/2017/586
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/586,
      author = {Daniel S.  Roche and Adam J.  Aviv and Seung Geol Choi and Travis Mayberry},
      title = {Deterministic, Stash-Free Write-Only ORAM},
      howpublished = {Cryptology ePrint Archive, Paper 2017/586},
      year = {2017},
      doi = {10.1145/3133956.3134051},
      note = {\url{https://eprint.iacr.org/2017/586}},
      url = {https://eprint.iacr.org/2017/586}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.