# On Differentially Private String Distances

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 71 references that are in the map.
- First posted on arXiv 8 Nov 2024.

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

- [Differentially Private Label Protection in Split Learning](https://mlsanity.com/paper/2203.02073/) (2022)
- [Differentially Private Attention Computation](https://mlsanity.com/paper/2305.04701/) (2023)
- [Differentially Private Kernel Density Estimation](https://mlsanity.com/paper/2409.01688/) (2024)
- [Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees](https://mlsanity.com/paper/1607.03718/) (2016)

## Abstract (arXiv)

Given a database of bit strings A1,ldots,Am∈ 0,1n, a fundamental data structure task is to estimate the distances between a given query B∈ 0,1n with all the strings in the database. In addition, one might further want to ensure the integrity of the database by releasing these distance statistics in a secure manner. In this work, we propose differentially private (DP) data structures for this type of tasks, with a focus on Hamming and edit distance. On top of the strong privacy guarantees, our data structures are also time- and space-efficient. In particular, our data structure is ε-DP against any sequence of queries of arbitrary length, and for any query B such that the maximum distance to any string in the database is at most k, we output m distance estimates. Moreover, - For Hamming distance, our data structure answers any query in widetilde O(mk+n) time and each estimate deviates from the true distance by at most widetilde O(k/eε/log k); - For edit distance, our data structure answers any query in widetilde O(mk2+n) time and each estimate deviates from the true distance by at most widetilde O(k/eε/(log k log n)). For moderate k, both data structures support sublinear query operations. We obtain these results via a novel adaptation of the randomized response technique as a bit flipping procedure, applied to the sketched strings.