Paper 2026/823

TieredOMap: Skewness-Aware Oblivious Map

Abstract

Oblivious map (OMAP) is a fundamental primitive for encrypted databases, yet existing designs largely adhere to a uniform worst-case principle: every record incurs nearly the same time to retrieve, regardless of how often it is queried. Real-world workloads, however, are typically highly skewed, with a small hot set accounting for most requests. We argue that such skewness should be leveraged as a first-class design signal for oblivious retrieval, rather than treated solely as leakage to conceal. We present TieredOMap, the first skewness-aware framework for OMAP, opening up a new design space for improving OMAP efficiency. TieredOMap separates hot and cold records into separate and independent OMAPs to enable more efficient access to hot records without weakening the security guarantees of standard OMAPs. Moreover, its design naturally supports further performance gains under a small, explicit relaxation of security. To make TieredOMap more practical, we also develop a complete mechanism to support dynamic workloads with evolving hot sets. Overall, our results show that oblivious accesses to records need not be governed solely by uniform worst-case behavior, and that skewness-aware structure represents a promising new direction orthogonal to existing OMAP design principles.