International Association
for Cryptologic Research

We present techniques to construct constant bandwidth, client storage and server storage blowup Oblivious RAM schemes in the (single-server) client-server setting.

Crucially, our constructions \\emph{do not rely on Fully Homomorphic Encryption (FHE) or Somewhat Homomorphic Encryption (SWHE)}

but instead rely only on an public-key additive homomorphic encryption scheme such as the Paillier or Damg\\r{a}rd-Jurik Cryptosystem cryptosystem.

The key mechanism that we use to get constant bandwidth overhead is \\emph{layered encryption}: to perform an ORAM eviction operation, the server performs an oblivious permutation operation on the eviction candidate blocks \\emph{without sending any data blocks back to the client}.

After each permutation, each block that was involved in the permutation gets an additional layer of encryption.

Importantly, the bandwidth needed for this operation is independent of the data block size.

If layered encryption is combined with previous ORAM schemes na\\\"{i}vely, the number of layers grows unbounded (with the number of accesses made to the ORAM).

This blows up server storage and bandwidth (due to ciphertext blowup) as well as client computation (as the client must ``peel\'\' off all layers to get the underlying plaintext).

To address this challenge, we propose \\emph{Onion ORAM}, a new ORAM scheme that is designed and optimized to bound the number of encryption layers on each block to $\\tilde{O}(\\log N)$, where $N$ is the number of blocks in the ORAM---\\emph{i.e., independent of the number of ORAM accesses}.

Putting it together, with sufficiently large block size $B=\\Omega(k \\log^2 N \\log^2 \\log N)$~bits for a security parameter $k$, Onion ORAM achieves $O(B)$ bandwidth, $O(B)$ client storage and $O(BN)$ server storage--only a constant factor blowup in all the three metrics.

Using the Damg\\r{a}rd-Jurik cryptosystem as our underlying primitive, Onion ORAM achieves the aforementioned asymptotics for block sizes $B=\\Omega(\\log^5 N \\log^2 \\log N)$~bits and security against known attacks with complexity $O\\left(N^{\\omega(1)}\\right)$, superpolynomial in the security parameter.