Paper 2017/008

Externally Verifiable Oblivious RAM

Joshua Gancher, Adam Groce, and Alex Ledger

Abstract

We present the idea of externally verifiable oblivious RAM (ORAM). Our goal is to allow a client and server carrying out an ORAM protocol to have disputes adjudicated by a third party, allowing for the enforcement of penalties against an unreliable or malicious server. We give a security definition that guarantees protection not only against a malicious server but also against a client making false accusations. We then give modifications of the Path ORAM and Ring ORAM protocols that meet this security definition. These protocols both have the same asymptotic runtimes as the semi-honest original versions and require the external verifier to be involved only when the client or server deviates from the protocol. Finally, we implement externally verified ORAM, along with an automated cryptocurrency contract to use as the external verifier.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. PETS 2017
Keywords
ORAM
Contact author(s)
agroce @ reed edu
History
2017-01-11: received
Short URL
https://ia.cr/2017/008
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/008,
      author = {Joshua Gancher and Adam Groce and Alex Ledger},
      title = {Externally Verifiable Oblivious RAM},
      howpublished = {Cryptology ePrint Archive, Paper 2017/008},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/008}},
      url = {https://eprint.iacr.org/2017/008}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.