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

Use of cloud based storage-as-a-service has surged 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 request, an application either reads or updates the encrypted data on the cloud, revealing the type of client access to the untrusted cloud. An adversary how- ever can exploit this information leak to compromise a user’s privacy by tracking read/write access patterns. Existing ap- proaches (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, irrespec- tive of a read or write request, rendering one of these rounds redundant with respect to a client request. To mitigate this re- dundancy, 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 distribu- tion 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 smooth- ing. Our experimental evaluations show that for objects of 160B size ORTOA’s throughput is 1.4-1.7x that of a baseline that requires two rounds to hide the type of access; and the baseline incurs 1.5-1.9x higher latency than ORTOA.

Note: Added additional experiments and found new results that are reported in the updated version.

Available format(s)
Publication info
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
2023-02-07: revised
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.