Paper 2022/691
QuORAM: A Quorum-Replicated Fault Tolerant ORAM Datastore
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},
url = {https://eprint.iacr.org/2022/691}
}