Paper 2022/1506

ORTOA: One Round Trip Oblivious Access

Abstract

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.