Externally Verifiable Oblivious RAM

Joshua Gancher; Adam Groce; Alex Ledger

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: 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},
      url = {https://eprint.iacr.org/2017/008}
}