Engineering Encrypted Multi-Maps with Controlled Access and Volume Leakage for Multi-Dimensional Queries

Abstract

This work addresses the challenge of performing expressive, multi-dimensional range queries directly over encrypted data while balancing query efficiency against privacy leakage. Existing searchable encryption and encrypted multi-map (EMM) schemes either reveal access or volume patterns or incur substantial overhead by fully hiding all leakage (e.g. via ORAM) making them unpractical. Building on the static, multi-dimensional EMM framework of Falzon et al., we introduce a family of five EMM variants that provide tunable leakage profiles, spanning from full access- and volume-pattern exposure to near-complete concealment through adaptive padding and dummy-access techniques. The empirical evaluation of our
five EMM variants reveals a clear, quantifiable spectrum of privacy-performance trade-offs. On large-range workloads, the access-hiding schemes offer the best overall balance, with measured average latency slopes of ≈ 0.012 ms/label. For workloads dominated by small result sets, a volume hiding scheme excels, achieving an even lower slope of 0.0032 ms/label by tuning its padding to realistic occupancy bounds. In contrast, fully padded schemes like incur substantially higher overheads, up to two orders of magnitude greater, making them suitable only when maximal leakage resilience is required. These results allow cloud providers with quantitative guidance to deploy encrypted range search that meets both privacy requirements and performance expectations in real-world, multi-attribute database services.