ECStore: Achieving Efficient and Compressible Indexing on Outsourced Encrypted Databases

Abstract

Encrypted Databases (EDBs) are essential for protecting sensitive data outsourced to public clouds, enabling diverse index-based queries over encrypted data. However, existing EDB indexes often incur high storage overhead and performance degradation, primarily due to the poor compressibility of pseudorandom encrypted values, which leads to frequent accesses to slower persistent storage as indexes outgrow main memory. We introduce ECSTORE, the first EDB that supports compressible and efficient indexing. Observing that EDB indexes are used solely for lookups and never decrypted, we design ECTREE, a cryptographic hash-based index structure in which each node is a compressible bit-string identifier that conceals plaintext keys. ECTREE enables logarithmic-time encrypted search via a novel membership testing mechanism. To address false positives arising in dynamic workloads, we introduce Directed View Check (DVC), which detects inaccuracies and avoids redundant traversals. Additionally, ECTREE’s Merkle-tree-like structure supports encrypted query authentication, resisting server compromise. Extensive evaluations show that ECSTORE can achieve up to 94.7% lower latency and 10.5x higher throughput on popular benchmarks compared to notable EDBs.