  ConcurORAM is a parallel, multi-client oblivious RAM (ORAM) that eliminates
waiting for concurrent stateless clients and allows overall 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 oblivious 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 background 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.
