Enabling Scalable Resizing in Tree-Based ORAM: A Dynamic Transformation Framework

Oblivious RAM (ORAM) is a fundamental cryptographic primitive that enables secure access to encrypted data while hiding access patterns. It has been widely adopted in privacy-preserving storage and secure computation applications. Among various ORAM constructions, tree-based ORAM schemes have gained prominence due to their practical efficiency. However, most existing tree-based ORAM designs are static, making them unsuitable for applications requiring frequent data updates. In this work, we address this limitation by introducing a generic transformation framework that enables dynamic expansion and contraction of tree-based ORAMs. Our approach integrates a reverse lexicographic order scheduling forterminal nodeinsertion and pruning, along with a deepestvirtual level mappingmechanism to efficiently manage the position map. This design ensures scalability while avoiding frequent update of the position map. We implement our framework for state-of-the-art Path ORAM, Circuit ORAM, and Ring ORAM, and conduct extensive evaluations. The results demonstrate that compared to their original static counterparts and the scheme of Moataz et al., our schemes significantly reduce bandwidth overhead by up to 7×, making tree-based ORAMs more practical for real-world applications, such as oblivious priority queue and dynamic searchable encryption.