Masked B-Tree Data Structure

The challenge of creating efficient queries on encrypted data is a major obstacle in privacy-preserving data access. Existing approaches, such as Homomorphic Encryption (HE), Oblivious RAM (ORAM), and Private Information Retrieval (PIR), are theoretically ideal but practically inefficient due to the high demand for computational and memory resources. On the other hand, Searchable Symmetric Encryption (SSE) and Order-Revealing/Order-Preserving Encryption (ORE/OPE) achieve optimal query performance in build time; however, they are vulnerable to leakage exploitation, especially with dynamic and adaptive adversaries. The research proposes a Masked B-Tree data structure that rethinks the data structure layer to provide an ideal balance between efficiency and leakage resistance. The proposed data structure combines ORE for fast key comparisons with cache-oblivious B-tree packing for block locality, enhanced by dummy nodes and controlled dummy walks to conceal access traces. This results in a well-defined leakage profile, enabling a formal analysis of the type of information exposed to the attacker. To address stronger attackers, the model integrates HMAC-based authentication and versioning, enabling the detection of malicious events such as replay, reordering, selective failures, and bucket drops, which are not detected in traditional SSE settings. The prototype is benchmarked against realistic workloads with a minimum sample size of 1000 elements. The benchmarked results indicate that the proposed model exhibits logarithmic query performance and practical update support. Compared to existing solutions, the proposed model achieves practical query efficiency, formalized leakage control, and robustness against active attackers, positioning it as a promising solution for privacy-preserving data access.