The goal of this paper is to present a modified version of oblivious RAM that improves the performance of enforcing oblivion for write heavy workloads. One of the more poignant criticisms of ORAM, as mentioned in the previous paper, is the high-performance overhead that comes with it. With write-only oblivious RAM, the concept of stashing blocks in local state, which is particularly essential for when writes fail in a randomized context, is done away with and replaced with a deterministic, sequential writing pattern that is more efficient because entropy is no longer required. The goal of the paper is not so much to introduce new security mechanisms, but rather, to improve performance, which is evident in the author’s evaluation section that demonstrates both experimental and asymptotical improvements in runtime. Original ORAM, proposed in the late 80s, had a run time of N^2, and since then, there have been periodic improvements oriented around improving the algorithm or “cheating” by using more servers.

This paper builds on the original idea of Write Only ORAM. With the original version, the idea is that with writes, there is no need to shuffle for purposeful randomization. Writes can simply be pointed to random locations. Stale blocks can also be overwritten, but stashes are required when random locations are all non-stale (a.k.a. being used). The good thing is that each write takes O(1) but would be O(log N) stateless (only O(1) hidden storage required). The innovation that this paper introduces is splitting the storage into two parts. The Holding area is a circular buffer where new blocks are written sequentially while long term storage is a size-N array where blocks are placed in their “true” locations. The paper demonstrates that there is a tradeoff between overhead and storage. The writes in a low storage, balanced, and fast write context all evaluate to linear time. The main benefits are that it is asymptotically optimal, simplifies the security proof (only symmetric ciphers needed), obviates the need for state (only cipher key, counter needed), introduces a lot of both spatial and temporal locality (reducing read cache misses), and has a sequential write pattern that adapts nicely to existing storage devices like the SSD format.

I feel like the authors of this paper did their research and really understood the history and research on ORAM, leading to a well written paper with a simple concept, yet demonstrated its wide-ranging performance benefits while upholding a slightly weaker security policy. The benchmark results with fio with random reads and writes were quite promising, although in a hard disk setting, Write-Only ORAM performed 1.6x slower than the baseline. I found that surprising but felt like it wasn’t too well explained. I am also not sure whether the position map would require write-only ORAM, or if it could work for other forms of ORAM.

Write Only ORAM has a variety of applications. One of the more straightforward usages would be for encrypting hidden volumes, preventing attackers from learning whether a particular disk drive is actually being used. Secure computation with a remote attacker in mind allows for computing on trusted CPUs with untrusted RAM while ensuring an adversary can only see snapshots of memory. Encrypted backup and file synchronization creates a system where users store a local copy of their files, with only writes being sent to a server.