ConcurORAM: High-Throughput Stateless Parallel Multi-Client ORAM

ConcurORAM is a parallel, multi-client oblivious RAM (ORAM) that
eliminates waiting for concurrent stateless clients and allows over-
all throughput to scale gracefully, without requiring trusted third
party components (proxies) or direct inter-client coordination.
A key insight behind ConcurORAM is the fact that, during
multi-client data access, only a subset of the concurrently-
accessed server-hosted data structures require access privacy
guarantees. Everything else can be safely implemented as oblivi-
ous data structures that are later synced securely and efficiently
during an ORAM “eviction”.
Further, since a major contributor to latency is the eviction
– in which client-resident data is reshuffled and reinserted back
encrypted into the main server database – ConcurORAM also
enables multiple concurrent clients to evict asynchronously, in
parallel (without compromising consistency), and in the back-
ground without having to block ongoing queries.
As a result, throughput scales well with increasing number of
concurrent clients and is not significantly impacted by evictions.
For example, about 65 queries per second can be executed in
parallel by 30 concurrent clients, a 2x speedup over the state-of-
the-art. The query access time for individual clients increases
by only 2x when compared to a single-client deployment.