Verifiable Oblivious Storage

Daniel Apon; Jonathan Katz; Elaine Shi; Aishwarya Thiruvengadam

Paper 2014/153

Verifiable Oblivious Storage

Daniel Apon, Jonathan Katz, 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 storage oblivious 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: CC BY

BibTeX

@misc{cryptoeprint:2014/153,
      author = {Daniel Apon and Jonathan Katz and Elaine Shi and Aishwarya Thiruvengadam},
      title = {Verifiable Oblivious Storage},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/153},
      year = {2014},
      url = {https://eprint.iacr.org/2014/153}
}