Paper 2022/691

QuORAM: A Quorum-Replicated Fault Tolerant ORAM Datastore

Sujaya Maiyya, University of California, Santa Barbara
Seif Ibrahim, University of California, Santa Barbara
Caitlin Scarberry, University of California, Santa Barbara
Divyakant Agrawal, University of California, Santa Barbara
Amr El Abbadi, University of California, Santa Barbara
Huijia Lin, University of Washington
Stefano Tessaro, University of Washington
Victor Zakhary, Oracle
Abstract

Privacy and security challenges due to the outsourcing of data storage and processing to third-party cloud providers are well known. With regard to data privacy, Oblivious RAM (ORAM) schemes provide strong privacy guarantees by not only hiding the contents of the data (by encryption) but also obfuscating the access patterns of the outsourced data. But most existing ORAM datastores are not fault tolerant in that if the external storage server (which stores encrypted data) or the trusted proxy (which stores the encryption key and other meta- data) crashes, an application loses all of its data. To achieve fault-tolerance, we propose QuORAM, the first ORAM datastore to replicate data with a quorum-based replication protocol. QuORAM’s contributions are three-fold: (i) it obfuscates access patterns to provide obliviousness guarantees, (ii) it replicates data using a novel lock-free and decentralized replication protocol to achieve fault-tolerance, and (iii) it guarantees linearizable semantics. Experimentally evaluating QuORAM highlights counter-intuitive results: QuORAM in- curs negligible cost to achieve obliviousness when compared to an insecure fault-tolerant replicated system; QuORAM’s peak throughput is 2.4x of its non-replicated baseline; and QuORAM performs 33.2x better in terms of throughput than an ORAM datastore that relies on CockroachDB, an open- source geo-replicated database, for fault tolerance.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. USENIX Security 2022
Keywords
Fault tolerant ORAM replicated ORAM quorum-based replication
Contact author(s)
sujaya_maiyya @ ucsb edu
seifibrahim @ ucsb edu
caitlinscarberry @ ucsb edu
agrawal @ cs ucsb edu
amr @ cs ucsb edu
rachel @ cs washington edu
tessaro @ cs washington edu
victorzakhary @ gmail com
History
2022-06-02: approved
2022-05-31: received
See all versions
Short URL
https://ia.cr/2022/691
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/691,
      author = {Sujaya Maiyya and Seif Ibrahim and Caitlin Scarberry and Divyakant Agrawal and Amr El Abbadi and Huijia Lin and Stefano Tessaro and Victor Zakhary},
      title = {{QuORAM}: A Quorum-Replicated Fault Tolerant {ORAM} Datastore},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/691},
      year = {2022},
      url = {https://eprint.iacr.org/2022/691}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.