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

Cloud based storage-as-a-service is quickly gaining popularity due to its many advantages such as scalability and pay-as-you-use cost model. However, storing data in the clear on third-party servers creates vulnerabilities, especially pertaining to data privacy. Applications typically encrypt their data before off-loading it to cloud storage to ensure data privacy. To serve a client’s read or write requests, an application either reads or updates the encrypted data on the cloud, revealing the type of client access to the untrusted cloud. An adversary however can exploit this information leak to compromise a user’s privacy by tracking read/write access patterns. Existing approaches (used in Oblivious RAM (ORAM) and frequency smoothing datastores) hide the type of client access by always reading the data followed by writing it, sequentially, irrespective of a read or write request, rendering one of these rounds redundant with respect to a client request. To mitigate this redundancy, we propose ORTOA- a One Round Trip Oblivious Access protocol that reads or writes data stored on remote storage in one round without revealing the type of access. To our knowledge, ORTOA is the first generalized protocol to obfuscate the type of access in a single round, reducing the communication overhead in half. ORTOA hides the type of individual access as well as the read/write workload distribution of an application, and due to its generalized design, it can be integrated with many existing obliviousness techniques that hide access patterns such as ORAM or frequency smoothing. Our experimental evaluations show that ORTOA’s throughput is 2.8x that of a baseline that requires two rounds to hide the type of access; and the baseline incurs 1.9x higher latency than ORTOA.

Available format(s)
Publication info
Encrypted datastores Oblivious access Hide type of access One round protocol
Contact author(s)
smaiyya @ uwaterloo ca
yuval @ ucsb edu
agrawal @ cs ucsb edu
prabhanjan @ ucsb edu
amr @ cs ucsb edu
2022-11-07: approved
2022-11-01: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.