Differentially Private Learned Indexes

In this paper, we study the problem of efficiently answering predicate queries for encrypted databases—those powered by Trusted Execution Environments (TEEs), allowing untrusted providers to process encrypted user data all without revealing sensitive details. A common strategy in conventional databases to accelerate query processing is the use of indexes, which map attribute values to their corresponding record locations within a sorted data array. This allows for fast lookup and retrieval of data subsets that satisfy specific predicates. Unfortunately, these traditional indexing methods cannot be directly applied to encrypted databases due to strong data-dependent leakages. Recent approaches use differential privacy (DP) to construct noisy indexes that enable faster access to encrypted data while maintaining provable privacy guarantees. However, these methods often suffer from significant data loss and high overhead. To address these challenges, we propose to explore learned indexes---a trending technique that repurposes machine learning models as indexing structures---to build more efficient DP indexes. Our contributions are threefold: (i) We propose a flat learned index structure that seamlessly integrates with differentially private stochastic gradient descent (DPSGD) algorithms for efficient and private index training. (ii) We introduce a novel noisy-max based private index lookup technique that ensures lossless indexing while maintaining provable privacy. (iii) We benchmark our DP learned indexes against state-of-the-art (SOTA) DP indexing methods. Results show that our method outperform the existing DP indexes by up to 925.6$\times$ in performance.