LatORAM: ORAMs from Lateral Stashes and Delayed Shuffling

We study the design of oblivious RAMs (ORAMs) that allow a client to access memory outsourced to a remote, untrusted server without revealing the client's data access pattern. We are interested in concretely efficient constructions and prior works have yielded different ORAM frameworks with various trade-offs. Tree-based constructions such as Ring ORAM [Ren et al., USENIX'15] obtain low communication overhead, but require client storage of linear position maps and two roundtrip queries. Hierarchical schemes such as FutORAMa [Asharov et al., CCS'23] further reduce communication at the cost of more roundtrips during queries. Finally, SQRT-ORAM [Zahur et al., S&P'16] enables fast queries of one roundtrip and one block of communication at the cost of larger amortized communication costs. We present two new constructions, LatORAM and LAT2ORAM, that simultaneously obtains the positive traits of all three types of ORAM constructions. Online queries are blazing fast with one roundtrip and a single block of communication like SQRT-ORAM. Fixing the client memory sizes for comparison, the online communication cost of our constructions are 5-8x smaller than Ring ORAM and 5-10x smaller than FutORAMa even though both Ring ORAM and FutORAMa require multiple roundtrips per online query. Furthermore, our total amortized communication is also up to 50% smaller. To obtain our constructions, we present a new lazy approach of lateral stash growth that delays large shuffles. Of independent interest, we present improved oblivious merging schemes for specific settings important for our ORAMs. Our constructions solely rely on symmetric Cryptography.