Differentially Private Learned Indexes
learned index;differential privacy;encrypted databases
We identified an issue with our method, particularly concerning the sensitivity used for generating Gaussian noise--- it should also scale with the batch sizes. Following discussions, we have decided to withdraw the submission to prepare a more rigorous and complete manuscript.
I have read and agree with the venue's withdrawal policy on behalf of myself and my co-authors.
This work proposes the first differentially-private learned indexes to accelerate predicate search on encrypted data.
@misc{
du2024differentially,
title={Differentially Private Learned Indexes},
author={Jianzhang Du and Tilak Mudgal and Rutvi Rahul Gadre and Yukui Luo and Chenghong Wang},
year={2024},
url={https://openreview.net/forum?id=8ZihaQpJ4L}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
~Jianzhang_Du1 ~Tilak_Mudgal1 ~Rutvi_Rahul_Gadre1 ~Yukui_Luo1 ~Chenghong_Wang1
Jianzhang Du Tilak Mudgal Rutvi Rahul Gadre Yukui Luo Chenghong Wang
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
learned index differential privacy encrypted databases
I certify that there is no acknowledgement section in this submission for double blind review.
du|differentially_private_learned_indexes
/pdf/b910cb963eed5333624e64374b27fab1041a18ef.pdf
alignment, fairness, safety, privacy, and societal considerations
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/973b49d253846c57060fbbac2c0315396f0a2f74.zip
Differentially Private Learned Indexes
ICLR 2025 Conference Withdrawn Submission
ICLR.cc/2025/Conference/Withdrawn_Submission