Robin Vassantlal (LASIGE, Faculdade de Ciências, Universidade de Lisboa, Portugal), Hasan Heydari (LASIGE, Faculdade de Ciências, Universidade de Lisboa, Portugal), Bernardo Ferreira (LASIGE, Faculdade de Ciências, Universidade de Lisboa, Portugal), Alysson Bessani (LASIGE, Faculdade de Ciências, Universidade de Lisboa, Portugal)
It is well known that encryption alone is not enough to protect data privacy. Access patterns, revealed when operations are performed, can also be leveraged in inference attacks. Oblivious RAM (ORAM) hides access patterns by making client requests oblivious. However, existing protocols are still limited in supporting concurrent clients and Byzantine fault tolerance (BFT). We present MVP-ORAM, the emph{first wait-free ORAM protocol} that supports concurrent fail-prone clients. In contrast to previous works, MVP-ORAM avoids using trusted proxies, which necessitate additional security assumptions, and concurrency control mechanisms based on inter-client communication or distributed locks, which limit overall throughput and the capability to tolerate faulty clients. Instead, MVP-ORAM enables clients to perform concurrent requests and merge conflicting updates as they happen, satisfying wait-freedom, i.e., clients make progress emph{independently of the performance or failures of other clients}. Since wait and collision freedom are fundamentally contradictory goals that cannot be achieved simultaneously in an asynchronous concurrent ORAM service, we define a weaker notion of obliviousness that depends on the application workload and number of concurrent clients, and prove MVP-ORAM is emph{secure in practical scenarios where clients perform skewed block accesses}. By being wait-free, MVP-ORAM can be seamlessly integrated into existing confidential BFT data stores, creating the first BFT ORAM construction. We implement MVP-ORAM on top of a confidential BFT data store and show emph{our prototype can process hundreds of 4KB accesses per second} in modern clouds.