Externally Verifiable Oblivious RAM

Joshua Gancher; Adam Groce; Alex Ledger

Paper 2017/008 Original: eprint.iacr.org/2017/008 ↗

Externally Verifiable Oblivious RAM

Joshua Gancher

Adam Groce

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: Preprint.
History: 2017-01-11: last updated; 2017-01-11: published
Short URL: https://ia.cr/2017/008
License: https://creativecommons.org/licenses/by/4.0/

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}
}