QuORAM: A Quorum-Replicated Fault Tolerant ORAM Datastore

Sujaya Maiyya; Seif Ibrahim; Caitlin Scarberry; Divyakant Agrawal; Amr El Abbadi; Huijia Lin; Stefano Tessaro; Victor Zakhary

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: 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},
      note = {\url{https://eprint.iacr.org/2022/691}},
      url = {https://eprint.iacr.org/2022/691}
}