Standard encryption protects the content of data, but it leaves the structure and access patterns of that data exposed. If an untrusted cloud server observes that a user frequently accesses the same encrypted block, or follows a specific path through an encrypted index, it can infer sensitive information—such as the frequency of keywords or the distribution of values in a database—without ever decrypting a single bit.
To solve this, researchers have developed oblivious hierarchical structures. These techniques transform traditional data structures like trees and tries into uniform, "shape-blind" versions where every operation looks identical to an observer.
The Leakage of Geometry
In a standard search index or database, the structure of the data is often a reflection of the data itself. For example, a B+ tree might be deeper in sections where data is dense, or a trie might have longer branches for longer words.
Jiangang Shu, Xingming Sun, and Jin Wang identified this in Efficient Keyword Search Scheme in Encrypted Cloud Computing Environment. They noted that the "shape" of a hierarchical index leaks keyword frequency and length. To counter this, they proposed inserting dummy nodes to transform the index into a full, uniform tree. By ensuring every path from root to leaf is the same length and every node has the same number of children, the physical layout of the index becomes independent of the underlying keywords.
This concept of structural uniformity is a recurring theme. Sepanta Zeighami and colleagues applied this to database queries in Dynamic Skyline Queries on Encrypted Data Using Result Materialization, using perfectly balanced trees to prevent storage providers from inferring data distributions through index depth.
Hiding the Path: Path ORAM
Even if a tree is perfectly balanced, the act of traversing it still leaks information. If a user reads node A then node B, an attacker knows those nodes are logically connected.
The breakthrough in hiding these movements came with Path ORAM, introduced by Emil Stefanov, Elaine Shi, and others in Path ORAM: An Extremely Simple Oblivious RAM Protocol. Path ORAM organizes server storage into a binary tree of buckets. The core intuition is simple: every time you want to access a single block of data, you must read and rewrite an entire path from the root to a leaf.
Because the data blocks are constantly shuffled and re-encrypted as they are written back, an observer sees a uniform "read-path, write-path" pattern. They cannot tell which specific block in that path was the actual target, effectively decoupling the logical access from the physical movement.
Optimizing for Databases and Enclaves
While Path ORAM provides strong security, its overhead can be prohibitive for high-performance databases. Saba Eskandarian addressed this in the development of ObliDB.
Standard B+ trees are "noisy" in memory; a single insertion can trigger a cascade of pointer updates (splits and merges) that are highly visible to an attacker. Eskandarian optimized the oblivious B+ tree by:
- Removing parent pointers: This prevents recursive update cycles that would otherwise require multiple expensive ORAM writes.
- Lazy write-backs: Modified nodes are kept in secure hardware enclaves as long as possible to minimize traffic to untrusted memory.
- Hybrid Storage: Using flat arrays for linear scans and ORAM-backed trees only for point lookups, allowing the system to choose the most efficient oblivious path for a given query.
Hardware-Accelerated Obliviousness
The shift toward oblivious structures has also moved into the realm of parallel computing. In GTree: GPU-Friendly Privacy-preserving Decision Tree Training and Inference, Qifan Wang and team demonstrated that representing decision trees as complete binary trees allows for "parallel scans."
Because the tree is structurally regular (a complete array), the GPU can process all possible paths simultaneously. This not only speeds up computation by 126× but also ensures that the memory access pattern is identical regardless of the input data, providing a side-channel-resistant way to perform machine learning inference.
Summary of Intuition
The power of these oblivious structures lies in indistinguishability. By forcing data into rigid, uniform geometries (like perfectly balanced trees) and accessing that data through fixed patterns (like full-path reads), researchers ensure that the "footprint" of a query is always the same. Whether you are searching for a common word or a rare one, the server sees the same number of nodes, the same path length, and the same memory addresses, leaving the attacker with no metadata to exploit.