Title: CAOS: Concurrent-Access Obfuscated Store,
Abstract: This paper proposes Concurrent-Access Obfuscated Store (CAOS), a construction
for remote data storage that provides access-pattern obfuscation in a
honest-but-curious adversarial model, while allowing for low bandwidth overhead
and client storage. Compared to the state of the art, the main advantage of
CAOS is that it supports concurrent access without a proxy, for multiple
read-only clients and a single read-write client. Concurrent access is achieved
by letting clients maintain independent maps that describe how the data is
stored. These maps might diverge from client to client, but it is guaranteed
that no client will ever lose track of current data. We achieve efficiency and
concurrency at the expense of perfect obfuscation: in CAOS the extent to which
access patterns are hidden is determined by the resources allocated to its
built-in obfuscation mechanism. To assess this trade-off we provide both a
security and a performance analysis of our protocol instance. We additionally
provide a proof-of-concept implementation.