Cryptology ePrint Archive: Report 2014/153

Verifiable Oblivious Storage

Daniel Apon and Jonathan Katz and Elaine Shi and Aishwarya Thiruvengadam

Abstract: We formalize the notion of Verifiable Oblivious Storage (VOS), where a client outsources the storage of data to a server while ensuring data confidentiality, access pattern privacy, and integrity and freshness of data accesses. VOS generalizes the notion of Oblivious RAM (ORAM) in that it allows the server to perform computation, and also explicitly considers data integrity and freshness.

We show that allowing server-side computation enables us to construct asymptotically more efficient VOS schemes whose bandwidth overhead cannot be matched by any ORAM scheme, due to a known lower bound by Goldreich and Ostrovsky. Specifically, for large block sizes we can construct a VOS scheme with constant bandwidth per query; further, answering queries requires only poly-logarithmic server computation. We describe applications of VOS to Dynamic Proofs of Retrievability, and RAM-model secure multi-party computation.

Category / Keywords: cryptographic protocols / verifiable oblivious storage; oblivious ram

Original Publication (with minor differences): IACR-PKC-2014

Date: received 28 Feb 2014, last revised 2 Mar 2014

Contact author: dapon at cs umd edu

Available format(s): PDF | BibTeX Citation

Note: Added authors' contact information

Version: 20140302:230426 (All versions of this report)

Short URL: ia.cr/2014/153

Discussion forum: Show discussion | Start new discussion