Paper 2022/1506

ORTOA: One Round Trip Oblivious Access

Sujaya Maiyya, University of Waterloo
Yuval Steinhart, University of California, Santa Barbara
Divyakant Agrawal, University of California, Santa Barbara
Prabhanjan Ananth, University of California, Santa Barbara
Amr El Abbadi, University of California, Santa Barbara
Abstract

Many applications relying on cloud storage services typically encrypt their data to ensure data privacy. However, reading or writing the encrypted data to serve client requests reveals the type of client operation to a potentially untrusted cloud. An adversary can exploit this information leak to compromise a user’s privacy by tracking read/write access patterns. Existing approaches such as Oblivious RAM (ORAM) schemes hide the type of client access by always reading and then writing the data sequentially for both reads and writes, rendering one of these rounds redundant with respect to a client request. To mitigate this redundancy, we propose ORTOA- a family of protocols enabling single-round data access on remote storage without revealing the operation type. Specifically, we propose three protocols, two using existing cryptographic primitives of fully homomorphic encryption and trusted execution environments (TEEs), and a new primitive inspired by garbled circuits. Each of these protocols has different trust assumptions, allowing an application to choose the option best suited for its needs. To our knowledge, ORTOA is the first to propose generalized protocols to obfuscate the type of access in a single round, reducing the communication overhead in half. The proposed techniques can pave the way for novel ORAM schemes that hide both the type of access and the access pattern in a single round. Our experimental results show ORTOA achieving throughput gains of 1.7x-3.2x compared to a baseline requiring two rounds for access type concealment, with the baseline incurring latency 1.5-1.9x that of ORTOA for 160B-sized objects.

Note: Added a new TEE-based version for one round trip protocol.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. EDBT 2024
Keywords
Encrypted datastoresOblivious accessApplied cryptographyHiding the type of accessOne round protocol
Contact author(s)
smaiyya @ uwaterloo ca
yuval @ ucsb edu
agrawal @ cs ucsb edu
prabhanjan @ ucsb edu
amr @ cs ucsb edu
History
2024-02-26: last of 2 revisions
2022-11-01: received
See all versions
Short URL
https://ia.cr/2022/1506
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1506,
      author = {Sujaya Maiyya and Yuval Steinhart and Divyakant Agrawal and Prabhanjan Ananth and Amr El Abbadi},
      title = {ORTOA: One Round Trip Oblivious Access},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1506},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1506}},
      url = {https://eprint.iacr.org/2022/1506}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.