# Differentially Private Learned Indexes

arXiv: https://arxiv.org/abs/2410.21164 · HTML: https://mlsanity.com/paper/2410.21164/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 22 references that are in the map.
- First posted on arXiv 28 Oct 2024.

## Builds on (most cited first, 6 of 6)

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Spectre Attacks: Exploiting Speculative Execution](https://mlsanity.com/paper/1801.01203/) (2018)
- [IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential Privacy](https://mlsanity.com/paper/2203.05084/) (2022)
- [DP-Sync: Hiding Update Patterns in Secure Outsourced Databases with Differential Privacy](https://mlsanity.com/paper/2103.15942/) (2021)
- [SPECIAL: Synopsis Assisted Secure Collaborative Analytics](https://mlsanity.com/paper/2404.18388/) (2024)

## Built on by (most cited first, 1 of 1)

- [CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplaces](https://mlsanity.com/paper/2605.23887/) (2026)

## Abstract (arXiv)

In this paper, we address the problem of efficiently answering predicate queries on encrypted databases, those secured by Trusted Execution Environments (TEEs), which enable untrusted providers to process encrypted user data without revealing its contents. A common strategy in modern databases to accelerate predicate queries is the use of indexes, which map attribute values (keys) to their corresponding positions in a sorted data array. This allows for fast lookup and retrieval of data subsets that satisfy specific predicates. Unfortunately, indexes cannot be directly applied to encrypted databases due to strong data dependent leakages. Recent approaches apply 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 large storage costs, with index sizes typically scaling linearly with the key space. To address this challenge, we propose leveraging learned indexes, a trending technique that repurposes machine learning models as indexing structures, to build more compact DP indexes.