Cryptology ePrint Archive: Report 2017/008

Externally Verifiable Oblivious RAM

Joshua Gancher and 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.

Category / Keywords: cryptographic protocols / ORAM

Original Publication (with minor differences): PETS 2017

Date: received 6 Jan 2017

Contact author: agroce at reed edu

Available format(s): PDF | BibTeX Citation

Version: 20170111:131327 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]