Resizable Oblivious RAM
摘要
Oblivious RAM (ORAM) is a cryptographic primitive that enables a trusted client to hide its memory access patterns from an untrusted memory. In this work, we explore the notion of resizability—a dimension that has been underexplored in ORAM literature. Resizability refers to a trusted client’s ability to dynamically expand or shrink the untrusted memory based on the number of elements it contains. This feature is crucial for high-level cryptographic primitives, particularly those related to outsourced storage, such as structured encryption and searchable symmetric encryption, where storage frequently fluctuates over time. The most common resizing approach in ORAM, often referenced in folklore, involves reinitializing the ORAM with a new capacity. While straightforward, this method has several limitations, including a superlinear resize cost, as the client must transfer all content from one ORAM instance to another. In this work, we first formalize the notion of resizable oblivious RAM. We model the reinitialization-based approach using a black-box construction, \(\textsf{RBB} \) , which transforms any ORAM into a resizable one. We then introduce our two primary constructions, \(\textsf{RPO} \) and \(\textsf{RRPO} \) , which build upon the non-recursive and recursive variants of Path ORAM, respectively. Both maintain the same asymptotic performance as their non-resizable counterparts while achieving \(O(\log {N})\) and \(O(\log ^2{N})\) resize communication complexity, where N represents the RAM size. These improvements significantly reduce the superlinear costs associated with folklore approaches in the vein of \(\textsf{RBB} \) .