Externally Verifiable Oblivious RAM
Authors: Joshua Gancher (Cornell University, work done partly while at Reed College), Adam Groce (Reed College), Alex Ledger (MIT Lincoln Laboratory, work done while at Reed College)
Volume: 2017
Issue: 2
Pages: 149–171
DOI: https://doi.org/10.1515/popets-2017-0021
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 [15] and Ring ORAM [9] 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.
Keywords: Oblivious RAM, cryptocurrency
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
