Hardware enclaves are regions of processor memory that the cloud operator cannot read, such as Intel SGX. They let a cloud server run database queries over sensitive records at close to native speed, and they are 120x faster than homomorphic encryption on one genetic workload (PRESAGE). Enclaves still leak which memory locations are touched and how many results each step produces. Those signals are enough to rebuild a 100,000-row database with 0.11% average error (Database Reconstruction from Noisy Volumes). Defenses exist for flat tables: fully oblivious operators (ObliDB) and cheaper "differentially oblivious" operators that add calibrated noise to intermediate sizes (Adore). Much sensitive data is nested JSON or XML, such as clinical records, publication histories and auction logs, and no enclave system in the literature handles it. In nested data, the per-step result counts of a path query like /patient/visit/diagnosis reveal document shape directly: how many visits a patient had and how many diagnoses each visit carried.
This proposal does not build a new tree engine. It keeps the well-known trick of encoding a tree as a flat table and adds one ingredient: the document's public schema bounds how much a single record can change every intermediate result of a path query. That bound lets us pad intermediate results to noisy sizes with a privacy guarantee that composes across all steps of the query. Adore leaves composition open for general relational joins. We argue it becomes tractable for the restricted class of joins that tree navigation produces.
Core Claim
Pathfinder showed that XML path queries can be compiled to plain relational algebra. Each node is stored as a row (pre, size, level), and each navigation step becomes a range selection or a "staircase join," a join specialized to tree axes. This encoding is the obvious substrate for an enclave: it reuses flat-table oblivious machinery and needs no pointer chasing. Pointer chasing is exactly what makes native nested layouts (Han et al., CHESTNUT) hard to make oblivious. The encoding still leaves open how large to make each step's output. ObliDB-style full padding pads every step to the worst case, which for a descendant step is the whole document. Adore-style noise needs a sensitivity bound per operator, meaning how much one record can change the output size, and a general join has no such bound.
Our claim is that a structural join's change is confined to the subtree of the record that changed. Take two documents that are "neighbors": they differ by one top-level record, such as one patient. Suppose the schema caps the child fan-out along a path at $f_1, \dots, f_k$, where $f_j$ is the maximum number of step-$j$ children per step-$(j-1)$ node. Then the size of the $i$-th intermediate result changes by at most
$$\Delta_i = \prod_{j=1}^{i} f_j ,$$
and a $k$-step query releasing noisy sizes with per-step budget $\varepsilon_i$ is $(\sum_i \varepsilon_i)$-differentially oblivious by basic composition. The noise uses one-sided truncated noise so that padded sizes never fall below true sizes. JSON Schema, which Bourhis et al. show is equivalent to a modal logic over trees, supplies the $f_j$ through maxItems and through nesting. A DTD plays the same role for XML. Where the schema is unbounded, as with unbounded arrays or recursive types under the descendant axis, we cap fan-out at a publicly declared value. Records exceeding the cap fall back to full padding for that step and are never silently clipped. The query plan depends only on the query and the schema, so it can be public. ObliDB, by contrast, explicitly leaks its data-dependent plan choices.
Research Program
The work has three parts.
Measuring the leak. We first show that the leak matters for trees. We will adapt the volume-reconstruction pipeline of the SQLite attack to per-step result sizes of path queries over shredded documents. Its noisy volume measurements are clustered and stitched together to recover values. The question is whether an observer who sees only step sizes over repeated path queries can recover per-record shape statistics, for example publications per author in DBLP. This experiment motivates the work. If shape is not recoverable, the defense is unneeded and we would report that.
Building the engine. We will build an in-enclave executor on SGX. It stores the Pathfinder encoding in flat oblivious storage and implements child, descendant and attribute steps as oblivious range scans and staircase joins. The steps emit outputs padded to schema-bounded noisy sizes, using Adore's prefix-sum technique for the selection step and an oblivious sort plus filter for the join. Value predicates reuse Adore's operators unchanged.
Analysis. We will write the sensitivity proof for the structural-join pipeline and check where it breaks. Value joins between two independent paths, as in XMark Q11 and Q12, are the case Adore also cannot compose. We will report them as out of scope rather than claim them.
Baselines
The naive reference point is a non-oblivious in-enclave executor over the same Pathfinder encoding. It plays the role of SecuDB (SecuDB), which runs a full relational engine in a TDX enclave but excludes side channels from its threat model. It gives the speed ceiling and the full-leakage floor.
The strongest fully secure competitor is the same encoding executed with ObliDB-style operators, padding every step to document size. It is the right comparison because it gives the strongest guarantee using existing methods. ObliDB reports 1.1–19x gains over Opaque on the Big Data Benchmark, but no reported result found on Lacuna for ObliDB on hierarchical data.
The strongest efficiency competitor is Adore's operators applied step by step with sensitivity set to document size, since without our structural bound nothing smaller is justified. Adore reports up to a 7.4x speedup over ObliDB on the Big Data Benchmark, and 1.5–3.7x for selection with projection. Beating it means a large runtime and enclave-paging reduction at equal total privacy budget, on queries where its sensitivity must be set to document size.
Two ablations isolate the ingredient. The first is schema-bounded deterministic padding with no noise. The second is the full method with schema bounds replaced by measured data maxima, which is not private but shows the headroom. All systems will run on the same SGX machine, documents, queries and enclave memory limit, with equal total $\varepsilon$ for the noisy variants. Each system gets the same tuning budget over padding granularity.
Why not just…?
Why not just shred the documents and run SecuDB? This works for speed and is our naive baseline. It protects nothing against the volume attack, which SecuDB's threat model excludes. Part one of the program measures exactly how much shape it leaks.
Why not just pad every step to the schema maximum deterministically? This is the real threat. If schema bounds are tight, deterministic padding is fully oblivious and needs no privacy budget, so our noise would add nothing. It fails when schemas are loose, as with unbounded arrays, optional elements and the descendant axis, because the schema maximum then explodes. We will report the ratio of schema maximum to true size per step on XMark and DBLP. If the ratio is small for most queries, we will recommend deterministic padding there and confine noise to loose steps. The heterogeneous DBLP corpus (Forgotten DODBMSes benchmark) is where we expect loose bounds.
Why not just use homomorphic encryption or have the client navigate the tree? PRESAGE's 120x enclave advantage on its genetic workload already argues against homomorphic encryption. Client-side navigation forces the client to download and parse whole subtrees, which defeats outsourcing. We will not re-run either.
Proposed Experiments
The datasets are XMark documents scaled from 11 MB upward, using the path, descendant and aggregation queries and excluding the value-join queries Q11 and Q12, and the 6.15M-record DBLP corpus in both XML and JSON forms. Metrics are end-to-end latency, bytes moved across the enclave boundary, the ratio of padded to true intermediate size, and attack success under each defense. Attack success means reconstruction error of per-record shape statistics from observed step sizes, measured across a sweep of $\varepsilon$.
Two outcomes are decisive. First, at equal $\varepsilon$, schema-bounded noise must cut boundary traffic substantially below Adore-with-document-size-sensitivity on multi-step paths. Second, the reconstruction attack must drop from near-exact recovery against the non-oblivious baseline to near-chance against ours. A third check, the schema-maximum-to-true ratio, decides whether noise is needed at all beyond deterministic schema padding. We will also confirm that Pathfinder's 125–147% storage expansion fits within enclave memory at each scale, and report the point where it stops fitting.
References
- PRESAGE: PRivacy-preserving gEnetic testing via SoftwAre Guard Extension
- Database Reconstruction from Noisy Volumes: A Cache Side-Channel Attack on SQLite
- ObliDB: Oblivious Query Processing for Secure Databases
- Differentially Oblivious Relational Database Operators
- Pathfinder: XQuery - The Relational Way
- An XML Storage System for Object-Oriented/Object-Relational DBMSs
- Generating Application-specific Data Layouts for In-memory Databases
- JSON: Data model, Query languages and Schema specification
- SecuDB: An In-enclave Privacy-preserving and Tamper-resistant Relational Database
- The Forgotten Document-Oriented Database Management Systems: An Overview and Benchmark of Native XML DODBMSes in Comparison with JSON DODBMSes