Structural Obfuscation for Tree Data Structures

20 concepts14 papers1 proposal

Tree data structures—such as decision trees, tries, and hierarchical indexes—are highly effective because their shape directly mirrors the logical distribution of the data they organize. However, this structural efficiency creates a severe privacy vulnerability. If an untrusted server or an external observer can see the depth of a branch, the number of children a node has, or the specific path taken during a query, they can easily infer sensitive underlying data distributions or proprietary model logic.

To prevent this structural side-channel leakage, researchers have developed structural obfuscation. The core intuition is simple: decouple the logical execution of the tree from its physical footprint, making all operations look uniform to an observer while preserving the tree's underlying utility.


Uniformity Through Padding and Fixed Depths

The most direct way to prevent an observer from learning a tree's shape is to eliminate the shape variation altogether. If every tree is forced into a rigid, identical geometry, the tree's topology leaks exactly zero information.

   Logical Tree (Leaks Shape)             Obfuscated Tree (Uniform Shape)
             [ A ]                                     [ A ]
            /     \                                   /     \
        [ B ]     [ C ]                           [ B ]     [ C ]
       /                                         /   \     /     \
   [ D ]                                       [D]   [#]  [#]    [#]
                                              (Note: [#] represents a dummy node)

To achieve this, algorithms transform sparse or irregularly shaped trees into complete binary trees of a fixed, pre-defined depth. Branches that do not naturally reach the maximum depth are filled out using dummy nodes.

This strategy is widely used across different execution environments to ensure uniform memory and computational footprints:

The Trade-Off: Privacy vs. Efficiency

While padding guarantees structural privacy, it introduces a steep performance penalty. As Jian Liu et al. observe in SoK: Modular and Efficient Private Decision Tree Evaluation, padding sparse models to make all execution paths identical can lead to an exponential increase in the total number of nodes.

Furthermore, enforcing a rigid architecture impacts the training phase. As noted by Daniel Escudero et al. in Secure training of decision trees with continuous attributes, training a tree to a fixed, complete depth prevents shape-based leaks but forces a difficult trade-off between structural privacy, computational overhead, and the risk of overfitting.


Oblivious Permutations and Shuffling

When full padding is too computationally expensive, researchers turn to cryptographic shuffling. Instead of making the tree perfectly uniform, this approach dynamically randomizes the tree's layout so that an observer cannot track which logical nodes are being evaluated.

In Privately Evaluating Decision Trees and Random Forests, Tony Feng et al. propose structure-hiding tree permutations. By randomly reordering nodes and edges, the protocol ensures that a traversal path looks like a sequence of completely random bits to an evaluator, masking the specific decision logic.

To optimize this process for multi-party computation, Aikaterini Mitrokotsa et al. introduce an "Oblivious Tree Shuffle" in Constant-Round Private Decision Tree Evaluation for Secret Shared Data. This technique swaps sub-trees and node values in a way that preserves the underlying evaluation logic but allows the final classification path to be revealed safely in constant communication rounds, without leaking the specific traversal history.

      Logical Path: Node 1 -> Node 3 -> Leaf 6

      Physical Traversal (After Oblivious Shuffle):
      Step 1: Access Index 42  (Randomized Mapping)
      Step 2: Access Index 107 (Randomized Mapping)
      Step 3: Access Index 14  (Randomized Mapping)

This permutation strategy can also be applied locally within nodes to preserve specific capabilities like prefix-matching. In Pistis: A Decentralized Knowledge Graph Platform Enabling Ownership-Preserving SPARQL Querying, Enyuan Zhou et al. restrict random permutations to individual node levels within a trie structure. This shuffles and pads child nodes to obscure character frequencies and child counts, successfully preventing structural data deduction while maintaining fully functional search capabilities.


Obscuring Relationships and Frequencies

A third facet of structural obfuscation focuses on hiding the exact positional relationships and value frequencies within the tree nodes themselves, without necessarily modifying the global tree depth.

Randomized Traversal Numbers

In standard tree verification schemes (like Merkle trees), nodes are assigned sequential numbers based on standard traversals (pre-order, in-order, or post-order). These sequential numbers inadvertently leak the exact position and structural context of the data.

To solve this, Ashish Kundu et al. introduce "structural signatures" in Structural signatures for tree data structures. Instead of sequential identifiers, the authors use randomized traversal numbers. These randomized identifiers preserve the relative inequality and ordering properties required to cryptographically verify data integrity, but they obscure the exact positional relationships between nodes, preventing unauthorized parties from inferring the tree's broader organization.

Node Aggregation and State Tracking

Other approaches obscure data density by changing how data points map to nodes, or how the traversal state is maintained:

  • Node Aggregation: Traditional order-preserving encryption schemes leak data frequency through node distribution. In On the Gini-impurity Preservation For Privacy Random Forests, XinRan Xie et al. mitigate this by grouping multiple samples that share the same label into single nodes within a modified binary search tree, successfully obscuring value frequencies.
  • Commitment Blending: In A Distributed Implementation of the Certified Information Access Service, Carlo Blundo et al. combine indistinguishable hard and soft cryptographic commitments inside a tree structure. This prevents external processors from analyzing the statistical density or distribution of the underlying database.
  • Oblivious State Tracking: When navigating search trees during complex evaluations, the tracking mechanism itself can leak depth information. In ppSAT: Towards Two-Party Private SAT Solving, Ning Luo 0002 et al. utilize an oblivious stack structure to track variable assignments and backtracking points. This allows a private solver to traverse a search tree while keeping both the current search depth and the specific path entirely hidden from the participating parties.
  • Structural Transformation Rules: Finally, structural obfuscation can be enforced programmatically via access control. Ernesto Damiani et al. demonstrate in Securing XML-based Multimedia Content that structured documents can be treated as tree models where transformation rules prune or encrypt unauthorized branches before delivery, ensuring data redaction is enforced directly at the topology level.

Key Foundational Work

Structural signatures for tree data structures (2008) — contributed 3 concept elements to this direction.
A Distributed Implementation of the Certified Information Access Service (2008) — contributed 1 concept elements to this direction.
Securing XML-based Multimedia Content (2003) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_randomized_traversal_numbers_6ceb311a,
  title = {randomized traversal numbers},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-traversal-numbers/rdr_6ceb311a3ffe4f2493a97642e77ff1ef},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_randomized_traversal_numbers_6ceb311a_v1,
  title = {randomized traversal numbers},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-traversal-numbers/rdr_6ceb311a3ffe4f2493a97642e77ff1ef/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake