Abstract: 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 regarding the support for concurrent clients and Byzantine fault tolerance.
We present MVP-ORAM, the first ORAM protocol that can support multiple clients and servers, whereas the servers may be subject to Byzantine faults.
In contrast with previous works, MVP-ORAM avoids using trusted proxies, which require making additional security assumptions, and distributed locks for managing client concurrency, which limit overall throughput.
Instead, MVP-ORAM lets clients perform concurrent requests and merge conflicting updates as they happen. This, allied with an algorithm for confidential Byzantine fault-tolerant replication, allows MVP-ORAM to be the first truly concurrent Byzantine fault-tolerant ORAM protocol.
Experimental results demonstrate that MVP-ORAM processes 587 ops/s in modern networks, with only a 14% decrease in throughput as fault tolerance increases from one to three corrupted servers.