You are looking at a specific version 20140302:230426 of this paper. See the latest version.

Paper 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.

Note: Added authors' contact information

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2014
Keywords
verifiable oblivious storageoblivious ram
Contact author(s)
dapon @ cs umd edu
History
2014-03-02: last of 2 revisions
2014-03-01: received
See all versions
Short URL
https://ia.cr/2014/153
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.