On Differentially Private String Distances

## Abstract

Given a database of bit strings A 1 , … , A m ∈ { 0 , 1 } n subscript 𝐴 1 … subscript 𝐴 𝑚 superscript 0 1 𝑛 A_{1},\ldots,A_{m}\in\{0,1\}^{n} italic_A start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , … , italic_A start_POSTSUBSCRIPT italic_m end_POSTSUBSCRIPT ∈ { 0 , 1 } start_POSTSUPERSCRIPT italic_n end_POSTSUPERSCRIPT , a fundamental data structure task is to estimate the distances between a given query B ∈ { 0 , 1 } n 𝐵 superscript 0 1 𝑛 B\in\{0,1\}^{n} italic_B ∈ { 0 , 1 } start_POSTSUPERSCRIPT italic_n end_POSTSUPERSCRIPT 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 ϵ italic-ϵ \epsilon italic_ϵ -DP against any sequence of queries of arbitrary length, and for any query B 𝐵 B italic_B such that the maximum distance to any string in the database is at most k 𝑘 k italic_k , we output m 𝑚 m italic_m distance estimates. Moreover, • For Hamming distance, our data structure answers any query in O ~ ⁢ ( m ⁢ k + n ) ~ 𝑂 𝑚 𝑘 𝑛 \widetilde{O}(mk+n) over~ start_ARG italic_O end_ARG ( italic_m italic_k + italic_n ) time and each estimate deviates from the true distance by at most O ~ ⁢ ( k / e ϵ / log ⁡ k ) ~ 𝑂 𝑘 superscript 𝑒 italic-ϵ 𝑘 \widetilde{O}(k/e^{\epsilon/\log k}) over~ start_ARG italic_O end_ARG ( italic_k / italic_e start_POSTSUPERSCRIPT italic_ϵ / roman_log italic_k end_POSTSUPERSCRIPT ) ; • For edit distance, our data structure answers any query in O ~ ⁢ ( m ⁢ k 2 + n ) ~ 𝑂 𝑚 superscript 𝑘 2 𝑛 \widetilde{O}(mk^{2}+n) over~ start_ARG italic_O end_ARG ( italic_m italic_k start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT + italic_n ) time and each estimate deviates from the true distance by at most O ~ ⁢ ( k / e ϵ / ( log ⁡ k ⁢ log ⁡ n ) ) ~ 𝑂 𝑘 superscript 𝑒 italic-ϵ 𝑘 𝑛 \widetilde{O}(k/e^{\epsilon/(\log k\log n)}) over~ start_ARG italic_O end_ARG ( italic_k / italic_e start_POSTSUPERSCRIPT italic_ϵ / ( roman_log italic_k roman_log italic_n ) end_POSTSUPERSCRIPT ) . For moderate k 𝑘 k italic_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.

## 1 Introduction

Estimating string distances is one of the most fundamental problems in computer science and information theory, with rich applications in high-dimensional geometry, computational biology and machine learning. The problem could be generically formulated as follows: given a collection of strings $A_{1},\ldots,A_{m}\in\Sigma^{n}$ where $\Sigma$ is the alphabet, the goal is to design a data structure to preprocess these strings such that when a query $B\in\Sigma^{n}$ is given, the data structure needs to quickly output estimates of $\|A_{i}-B\|$ for all $i\in[m]$, where $\|\cdot\|$ is the distance of interest. Assuming the symbols in $\Sigma$ can allow constant time access and operations, a naïve implementation would be to simply compute all the distances between $A_{i}$’s and $B$, which would require $O(mn)$ time. Designing data structures with $o(mn)$ query time has been the driving research direction in string distance estimations. To make the discussion concrete, in this work we will focus on binary alphabet ($\Sigma=\{0,1\}$) and for distance, we will study Hamming and edit distance. Hamming distance [] is one of the most natural distance measurements for binary strings, with its deep root in error detecting and correction for codes. It finds large array of applications in database similarity searches [, , ] and clustering algorithms [, ].

Compared to Hamming distance, edit distance or the Levenshtein distance [] could be viewed as a more robust distance measurement for strings: it counts the minimum number of operations (including insertion, deletion and substitution) to transform from $A_{i}$ to $B$. To see the robustness compared to Hamming distance, consider $A_{i}=(01)^{n}$ and $B=(10)^{n}$, the Hamming distance between these two strings is $n$, but $A_{i}$ could be easily transformed to $B$ by deleting the first bit and adding a 0 to the end, yielding an edit distance of 2. Due to its flexibility, edit distance is particularly useful for sequence alignment in computational biology [, , ], measuring text similarity [, ] and natural language processing, speech recognition [, ] and time series analysis [, ].

In addition to data structures with fast query times, another important consideration is to ensure the database is *secure*. Consider the scenario where the database consists of private medical data of $m$ patients, where each of the $A_{i}$ is the characteristic vector of $n$ different symptoms. A malicious adversary might attempt to count the number of symptoms each patient has by querying ${\bf 0}_{n}$, or detecting whether patient $i$ has symptom $j$ by querying $e_{j}$ and ${\bf 0}_{n}$ where $e_{j}$ is the $j$-th standard basis in $\mathbb{R}^{n}$. It is hence crucial to curate a private scheme so that the adversary cannot distinguish the case whether the patient has symptom $j$ or not. This notion of privacy has been precisely captured by *differential privacy* [, ], which states that for neighboring databases(^1^11In our case, we say two database ${\cal D}_{1}$ and ${\cal D}_{2}$ are neighboring if there exists one $i\in[n]$ such that ${\cal D}_{1}(A_{i})$ and ${\cal D}_{2}(A_{i})$ differs by one bit.), the output distribution of the data structure query should be close with high probability, hence any adversary cannot distinguishable between the two cases.

Motivated by both privacy and efficiency concerns, we ask the following natural question:

Is it possible to design a data structures to estimate Hamming and edit distance, that are both differentially private, and time/space-efficient?

We provide an affirmative answer to the above question, with the main results summarized in the following two theorems. We will use $D_{\operatorname{ham}}(A,B)$ to denote the Hamming distance between $A$ and $B$, and $D_{\operatorname{edit}}(A,B)$ to denote the edit distance between $A$ and $B$. We also say a data structure is $\epsilon$-DP if it provides $\epsilon$-DP outputs against any sequence of queries, of arbitrary length.

###### Theorem 1.1 .

Let $A_{1},\ldots,A_{m}\in\{0,1\}^{n}$ be a database, $k\in[n]$ and $\epsilon>0,\beta\in(0,1)$, then there exists a randomized algorithm with the following guarantees:

- •
The data structure is $\epsilon$-DP;
- •
It perprocesses $A_{1},\ldots,A_{m}$ in time $\widetilde{O}(mn)$ time(^2^22Throughout the paper, we will use $\widetilde{O}(\cdot)$ to suppress polylogarithmic factors in $m,n,k$ and $1/\beta$.);
- •
It consumes $\widetilde{O}(mk)$ space;
- •
Given any query $B\in\{0,1\}^{n}$ such that $\max_{i\in[m]}D_{\operatorname{ham}}(A_{i},B)\leq k$, it outputs $m$ estimates $z_{1},\ldots,z_{m}$ with $|z_{i}-D_{\operatorname{ham}}(A_{i},B)|\leq\widetilde{O}(k/e^{\epsilon/\log k})$ for all $i\in[m]$ in time $\widetilde{O}(mk+n)$, and it succeeds with probability at least $1-\beta$.

###### Theorem 1.2 .

Let $A_{1},\ldots,A_{m}\in\{0,1\}^{n}$ be a database, $k\in[n]$ and $\epsilon>0,\beta\in(0,1)$, then there exists a randomized algorithm with the following guarantees:

- •
The data structure is $\epsilon$-DP;
- •
It perprocesses $A_{1},\ldots,A_{m}$ in time $\widetilde{O}(mn)$ time;
- •
It consumes $\widetilde{O}(mn)$ space;
- •
Given any query $B\in\{0,1\}^{n}$ such that $\max_{i\in[m]}D_{\operatorname{edit}}(A_{i},B)\leq k$, it outputs $m$ estimates $z_{1},\ldots,z_{m}$ with $|z_{i}-D_{\operatorname{edit}}(A_{i},B)|\leq\widetilde{O}(k/e^{\epsilon/(\log k
\log n)})$ for all $i\in[m]$ in time $\widetilde{O}(mk^{2}+n)$, and it succeeds with probability at least $1-\beta$.

Before diving into the details, we would like to make several remarks regarding our data structure results. Note that instead of solving the exact Hamming distance and edit distance problem, we impose the assumption that the query $B$ has the property that for any $i\in[m]$, $\|A_{i}-B\|\leq k$. Such an assumption might seem restrictive at its first glance, but under the standard complexity assumption Strong Exponential Time Hypothesis (SETH) [, ], it is known that there is no $O(n^{2-o(1)})$ time algorithm exists for exact or even approximate edit distance [, , , , , , , , , , , ]. It is therefore natural to impose assumptions that the query is “near” to the database in pursuit of faster algorithms [, , , , , ]. In fact, assuming SETH, $O(n+k^{2})$ runtime for edit distance when $m=1$ is optimal up to sub-polynomial factors []. Thus, in this paper, we consider the setting where $\max_{i\in[m]}\|A_{i}-B\|\leq k$ for both Hamming and edit distance and show how to craft private and efficient mechanisms for this class of distance problems.

Regarding privacy guarantees, one might consider the following simple augmentation to any fast data structure for Hamming distance: compute the distance estimate via the data structure, and add Laplace noise to it. Since changing one coordinate of the database would lead to the Hamming distance change by at most 1, Laplace mechanism would properly handle this case. However, our goal is to release a *differentially private data structure* that is robust against potentially infinitely many queries, and a simple output perturbation won’t be sufficient as an adversary could simply query with the same $B$, average them to reduce the variance and obtain a relatively accurate estimate of the de-noised output. To address this issue, we consider the *differentially private function release communication model* [], where the curator releases an $\epsilon$-DP description of a function $\widehat{e}(\cdot)$ that is $\epsilon$-DP without seeing any query in advance. The client can then use $\widehat{e}(\cdot)$ to compute $\widehat{e}(B)$ for any query $B$. This strong guarantee ensures that the client could feed infinitely many queries to $\widehat{e}(\cdot)$ without compromising the privacy of the database.

###### Theorem 1.1 .

###### Theorem 1.2 .

## 2 Related Work

#### Differential Privacy.

Differential privacy is a ubiquitous notion for protecting the privacy of database. [] first introduced this concept, which characterizes a class of algorithms such that when inputs are two neighboring datasets, with high probability the output distributions are similar. Differential privacy has a wide range of applications in general machine learning [, , , ], training deep neural networks [, ], computer vision [, , ], natural language processing [, ], large language models [, ], label protect [], multiple data release [], federated learning [, ] and peer review []. In recent years, differential privacy has been playing an important role for data structure design, both in making these data structures robust against adaptive adversary [, , , ] and in the function release communication model [, , , , , , , ].

#### Hamming Distance and Edit Distance.

Given bit strings $A$ and $B$, many distance measurements have been proposed that capture various characteristics of bit strings. Hamming distance was first studied by Hamming [] in the context of error correction for codes. From an algorithmic perspective, Hamming distance is mostly studied in the context of approximate nearest-neighbor search and locality-sensitive hashing [, ]. When it is known that the query $B$ has the property $D_{\operatorname{ham}}(A,B)\leq k$, [] shows how to construct a sketch of size $\widetilde{O}(k)$ in $\widetilde{O}(n)$ time, and with high probability, these sketches preserve Hamming distance. Edit distance, proposed by Levenshtein [], is a more robust notion of distance between bit strings. It has applications in computational biology [, , ], text similarity [, ] and speech recognition [, ]. From a computational perspective, it is known that under the Strong Exponential Time Hypothesis (SETH), no algorithm can solve edit distance in $O(n^{2-o(1)})$ time, even its approximate variants [, , , , , , , , , , , ]. Hence, various assumptions have been imposed to enable more efficient algorithm design. The most related assumption to us is that $D_{\operatorname{edit}}(A,B)\leq k$, and in this regime various algorithms have been proposed [, , , , , ]. Under SETH, it has been shown that the optimal dependence on $n$ and $k$ is $O(n+k^{2})$, up to sub-polynomial factors [].

## 3 Preliminary

Let $E$ be an event, we use ${\bf 1}[E]$ to denote the indicator variable if $E$ is true. Given two length-$n$ bit strings $A$ and $B$, we use $D_{\operatorname{ham}}(A,B)$ to denote $\sum_{i=1}^{n}{\bf 1}[A_{i}=B_{i}]$. We use $D_{\operatorname{edit}}(A,B)$ to denote the edit distance between $A$ and $B$, i.e., the minimum number of operations to transform $A$ to $B$ where the allowed operations are insertion, deletion and substitution. We use $\oplus$ to denote the XOR operation. For any positive integer $n$, we use $[n]$ to denote the set $\{1,2,\cdots,n\}$. We use $\Pr[\cdot]$, $\operatorname*{{\mathbb{E}}}[\cdot]$ and $\text{Var}[\cdot]$ to denote probability, expectation and variance respectively.

### 3.1 Concentration Bounds

We will mainly use two concentration inequalities in this paper.

###### Lemma 3.1 (Chebyshev’s Inequality) .

Let $X$ be a random variable with $0<\mathrm{Var}[X]<\infty$. For any real number $t>0$,

$$ $\displaystyle\Pr[|X-\operatorname*{{\mathbb{E}}}[X]|>t]\leq$ $\displaystyle~{}\frac{\mathrm{Var}[X]}{t^{2}}.$ $$

###### Lemma 3.2 (Hoeffding’s Inequality) .

Let $X_{1},\ldots,X_{n}$ with $a_{i}\leq X_{i}\leq b_{i}$ almost surely. Let $S_{n}=\sum_{i=1}^{n}X_{i}$, then for any real number $t>0$,

$$ $\displaystyle\Pr[|S_{n}-\operatorname*{{\mathbb{E}}}[S_{n}]|>t]\leq$ $\displaystyle~{}2\exp(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}).$ $$

###### Lemma 3.1 (Chebyshev’s Inequality) .

###### Lemma 3.2 (Hoeffding’s Inequality) .

### 3.2 Differential Privacy

Differential privacy (DP) is the key privacy measure we will be trying to craft our algorithm to possess it. In this paper, we will solely focus on pure DP ($\epsilon$-DP).

###### Definition 3.3 ( $\epsilon$ -Differential Privacy) .

We say an algorithm ${\cal A}$ is *$\epsilon$-differentially private ($\epsilon$-DP)* if for any two neighboring databases ${\cal D}_{1}$ and ${\cal D}_{2}$ and any subsets of possible outputs $S$, we have

$$ $\displaystyle\Pr[{\cal A}({\cal D}_{1})\in S]\leq$ $\displaystyle~{}e^{\epsilon}\cdot\Pr[{\cal A}({\cal D}_{2})\in S],$ $$

where the probability is taken over the randomness of ${\cal A}$.

Since we will be designing data structures, we will work with the *function release communication model* [] where the goal is to release a function that is $\epsilon$-DP against any sequence of queries of arbitrary length.

###### Definition 3.4 ( $\epsilon$ -DP Data Structure) .

We say a data structure ${\cal A}$ is $\epsilon$-DP, if ${\cal A}$ is $\epsilon$-DP against any sequence of queries of arbitrary length. In other words, the curator will release an $\epsilon$-DP description of a function $\widehat{e}(\cdot)$ without seeing any query in advance.

Finally, we will be utilizing the *post-processing* property of $\epsilon$-DP.

###### Lemma 3.5 (Post-Processing) .

Let ${\cal A}$ be $\epsilon$-DP, then for any deterministic or randomized function $g$ that only depends on the output of ${\cal A}$, $g\circ{\cal A}$ is also $\epsilon$-DP.

###### Definition 3.3 ( ϵ italic-ϵ \epsilon italic_ϵ -Differential Privacy) .

###### Definition 3.4 ( ϵ italic-ϵ \epsilon italic_ϵ -DP Data Structure) .

###### Lemma 3.5 (Post-Processing) .

## 4 Differentially Private Hamming Distance Data Structure

To start off, we introduce our data structure for differentially private Hamming distance. In particular, we will adapt a data structure due to []: this data structure computes a sketch of length $\widetilde{O}(k)$ bit string to both the database and query, then with high probability, one could retrieve the Hamming distance from these sketches. Since the resulting sketch is also a bit string, a natural idea is to inject Laplace noise on each coordinate of the sketch. Since for two neighboring databases, only one coordinate would change, we could add Laplace noise of scale $1/\epsilon$ to achieve $\epsilon$-DP. However, this approach has a critical issue: one could show that with high probability, the magnitude of each noise is roughly $O(\epsilon^{-1}\log k)$, aggregating the $k$ coordinates of the sketch, this leads to a total error of $O(\epsilon^{-1}k\log k)$. To decrease this error to $O(1)$, one would have to choose $\epsilon=k\log k$, which is too large for most applications.

Instead of Laplace noises, we present a novel scheme that flips each bit of the sketch with certain probability. Our main contribution is to show that this simple scheme, while produces a biased estimator, the error is only $O(e^{-\epsilon/\log k}k)$. Let $t=\log k/\epsilon$, we see that the Laplace mechanism has an error of $O(t^{-1}k)$ and our error is only $O(e^{-t}k)$, which is exponentially small! In what follows, we will describe a data structure when the database is only one string $A$ and with constant success probability, and we will discuss how to extend it to $m$ bit strings, and how to boost the success probability to $1-\beta$ for any $\beta>0$. We summarize the main result below.

###### Theorem 4.1 .

Given a string $A$ of length $n$. There exists an $\epsilon$-DP data structure DPHammingDistance (Algorithm 1), with the following operations

- •
Init$(A\in\{0,1\}^{n})$: It takes a string $A$ as input. This procedure takes $O(n\log k+k\log^{3}k)$ time.
- •
Query$(B\in\{0,1\}^{n})$: for any $B$ with $z:=D_{\operatorname{ham}}(A,B)\leq k$, Query$(B)$ outputs a value $\widetilde{z}$ such that $|\widetilde{z}-z|=\widetilde{O}(k/e^{\epsilon/\log k})$ with probability $0.99$, and the result is $\epsilon$-DP. This procedure takes $O(n\log k+k\log^{3}k)$ time.

Figure: Algorithm 1 Differential Private Hamming Distance Query

To achieve the results above, we set parameters $M_{1}=O(\log k),M_{2}=O(k),M_{3}=O(\log^{2}k)$ in Algorithm 1.

We divide the proof of Theorem 4.1 into the following subsections:

###### Theorem 4.1 .

### 4.1 Time Complexity

Note that both the initializing and query run Encode
(Algorithm 1) exactly once, we show that the running time of Encode is $O(n\log k)$.

###### Lemma 4.2 .

Given $M_{1}=O(\log k)$, the running time of Encode (Algorithm 1) is $O(n\log k)$.

###### Proof.

In Encode, for each character in the input string, the algorithm iterate $M_{1}$ times. Therefore the total time complexity is $O(n\cdot M_{1})=O(n\log k)$.
∎

###### Lemma 4.2 .

###### Proof.

### 4.2 Privacy Guarantee

Next we prove our data structure is $\epsilon$-DP.

###### Lemma 4.3 .

Let $A$ and $A^{\prime}$ be two strings that differ on only one position. Let ${\cal A}(A)$ and ${\cal A}(A^{\prime})$ be the output of Init (Algorithm 1) given $A$ and $A^{\prime}$. For any output $S$, we have:

$$ $\displaystyle\Pr[{\cal A}(A)=S]\leq e^{\epsilon}\cdot\Pr[{\cal A}(A^{\prime})= S].$ $$

We defer the proof to Appendix A.

###### Lemma 4.3 .

### 4.3 Utility Guarantee

The utility analysis is much more involved than privacy and runtime analysis. We defer the proofs to the appendix, while stating key lemmas.

We first consider the distance between sketches of $A$ and $B$ without the random flipping process. Let $E(A),E(B)$ be Encode$(A)$ and Encode$(B)$. We prove with probability $0.99$, $D_{\text{ham}}(A,B)=0.5\cdot\sum_{j=1}^{M_{2}}\max_{i\in[M_{1}]}(\sum_{c=1}^{M
_{3}}|E(A)_{i,j,c}-E(B)_{i,j,c}|)$. Before we present the error guarantee, we will first introduce two technical lemmas. If we let $T=\{p\subseteq[n]\mid A_{p}\neq B_{p}\}$ denote the set of “bad” coordinates, then for each coordinate in the sketch, it only contains a few bad coordinates.

###### Lemma 4.4 .

Define set $T:=\{p\in[n]~{}|~{}A_{p}\neq B_{p}\}$.
Define set $T_{j}:=\{p\subseteq T~{}|~{}h(p)=j\}$.
When $M_{2}=2k$, with probability $0.99$, for all $j\in[M_{2}]$, we have $|T_{j}|\leq 10\log k$, i.e.,

$$ $\displaystyle\Pr[\forall j\in[M_{2}],~{}|~{}|T_{j}|\leq 10\log k]\geq 0.99.$ $$

The next lemma shows that with high probability, the second level hashing $g$ will hash bad coordinates to distinct buckets.

###### Lemma 4.5 .

When $M_{1}=10\log k,M_{2}=2k,M_{3}=400\log^{2}k$, with probability $0.98$, for all $j\in[M_{2}]$, there is at least one $i\in[M_{1}]$, such that all values in $\{g(2(p-1)+A_{p},i)~{}|~{}p\in T_{j}\}\bigcup\{g(2(p-1)+B_{p},i)~{}|~{}p\in T_
{j}\}$ are distinct.

With these two lemmas in hand, we are in the position to prove the error bound before the random bit flipping process.

###### Lemma 4.6 .

Let $E(A),E(B)$ be the output of Encode$(A)$ and Encode$(B)$. With probability $0.98$, $D_{\operatorname{ham}}(A,B)=0.5\cdot\sum_{j=1}^{M_{2}}\max_{i\in[M_{1}]}(\sum_
{c=1}^{M_{3}}|E(A)_{i,j,c}-E(B)_{i,j,c}|)$.

Our final result provides utility guarantees for Algorithm 1.

###### Lemma 4.7 .

Let $z$ be $D_{\text{ham}}(A,B)$, ${\widetilde{z}}$ be the output of Query$(B)$(Algorithm 1). With probability $0.98$, $|z-{\widetilde{z}}|\leq O(k\log^{3}k/e^{\epsilon/\log k})$.

###### Proof.

From Lemma 4.6, we know
with probability $0.98$, when $\epsilon\rightarrow\infty$ (i.e. without the random flip process), the output of Query$(B)$ (Algorithm 1) equals the exact hamming distance.

We view the random flip process as random variables. Let random variables $R_{i,j,c}$ be $1$ with probability $1/(1+e^{\epsilon/M_{1}})$, or 0 0 with probability $1-1/(1+e^{\epsilon/M_{1}})$. So we have

$$ $\displaystyle|{\widetilde{z}}-z|=$ $\displaystyle~{}\sum_{j=1}^{M_{2}}\max_{i\in[M_{1}]}(\sum_{c=1}^{M_{3}}R_{i,j, c})$ $\displaystyle\leq$ $\displaystyle~{}\sum_{j=1}^{M_{2}}\sum_{i=1}^{M_{1}}(\sum_{c=1}^{M_{3}}R_{i,j, c}),$ $$

where the second step follows from $\max_{i}\leq\sum_{i}$ when all the summands are non-negative.

Therefore, the expectation of ${\widetilde{z}}-z$ is:

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[|{\widetilde{z}}-z|]$ $\displaystyle=M_{1}M_{2}M_{3}\cdot\operatorname*{{\mathbb{E}}}[R_{i,j,c}]$ $\displaystyle=~{}k\log^{3}k\cdot\frac{1}{(1+e^{\epsilon/\log k})}$ $\displaystyle\leq~{}O(\frac{k\log^{3}k}{e^{\epsilon/\log k}}),$ $$

where the last step follows from simple algebra.
The variance of ${\widetilde{z}}-z$ is:

$$ $\displaystyle\text{Var}[|{\widetilde{z}}-z|]$ $\displaystyle=M_{1}M_{2}M_{3}\cdot\text{Var}[R_{i,j,c}]$ $\displaystyle=~{}k\log^{3}k\cdot\frac{1}{(1+e^{\epsilon/\log k})}\cdot(1-\frac {1}{(1+e^{\epsilon/\log k})}).$ $$

Using Chebyshev’s inequality (Lemma 3.1), we have

$$ $\displaystyle\Pr[|{\widetilde{z}}-z|\geq O(\frac{k\log^{3}k}{e^{\epsilon/\log k }})]\leq 0.01.$ $$

Thus we complete the proof.
∎

###### Remark 4.8 .

We will show how to generalize Theorem 4.1 to $m$ bit strings, and how to boost the success probability to $1-\beta$. To boost the success probability, we note that individual data structure succeeds with probability 0.99, we could take $\log(1/\beta)$ independent copies of the data structure, and query all of them. By a standard Chernoff bound argument, with probability at least $1-\beta$, at least $3/4$ fraction of these data structures would output the correct answer, hence what we could do is to take the median of these answers. These operations blow up both Init and Query by a factor of $\log(1/\beta)$ in its runtime. Generalizing for a database of $m$ strings is relatively straightforward: we will run the Init procedure to $A_{1},\ldots,A_{m}$, this would take $O(mn\log k+mk\log^{3}k)$ time. For each query, note we only need to Encode the query once, and we can subsequently compute the Hamming distance from the sketch for $m$ sketched database strings, therefore the total time for query is $O(n\log k+mk\log^{3}k)$. It is important to note that as long as $k\log^{3}k<n$, the query time is sublinear. Finally, we could use the success probability boosting technique described before, that uses $\log(m/\beta)$ data structures to account for a union bound over the success of all distance estimates.

###### Lemma 4.4 .

###### Lemma 4.5 .

###### Lemma 4.6 .

###### Lemma 4.7 .

###### Proof.

###### Remark 4.8 .

## 5 Differentially Private Edit Distance Data Structure

Our algorithm for edit distance follows from the dynamic programming method introduced by [, , , ]. We note that a key procedure in these algorithms is a subroutine to estimate *longest common prefix* (LCP) between two strings $A$ and $B$ and their substrings. We design an $\epsilon$-DP data structure for LCP based on our $\epsilon$-DP Hamming distance data structure. Due to space limitation, we defer the details of the DP-LCP data structure to Appendix B. In the following discussion, we will assume access to a DP-LCP data structure with the following guarantees:

###### Theorem 5.1 .

Given a string $A$ of length $n$. There exists an $\epsilon$-DP data structure DPLCP (Algorithm 3 and Algorithm 4) supporting the following operations

- •
Init$(A\in\{0,1\}^{n})$: It preprocesses an input string $A$. This procedure takes $O(n(\log k+\log\log n))$ time.
- •
InitQuery$(B\in\{0,1\}^{n})$: It preprocesses an input query string $B$. This procedure take $O(n(\log k+\log\log n))$ time.
- •
Query$(i,j)$: Let $w$ be the longest common prefix of $A[i:n]$ and $B[j:n]$ and ${\widetilde{w}}$ be the output of Query$(i,j)$, With probability $1-1/(300k^{2})$, we have: 1). ${\widetilde{w}}\geq w$; 2). $\operatorname*{{\mathbb{E}}}[D_{\operatorname{ham}}(A[i:i+{\widetilde{w}}],B[j
:j+{\widetilde{w}}])]\leq O((\log k+\log\log n)/e^{\epsilon/(\log k\log n)})$. This procedure takes $O(\log^{2}n(\log k+\log\log n))$ time.

We will be basing our edit distance data structure on the following result, which achieves the optimal dependence on $n$ and $k$ assuming SETH:

###### Lemma 5.2 ( [ 43 ] ) .

Given two strings $A$ and $B$ of length $n$. If the edit distance between $A$ and $B$ is no more than $k$, there is an algorithm which computes the edit distance between $A$ and $B$ in time $O(k^{2}+n)$.

We start from a naïve dynamic programming approach. Define $D(i,j)$ to be the edit distance between string $A[1:i]$ and $B[1:j]$. We could try to match $A[i]$ and $B[j]$ by inserting, deleting and substituting, which yields the following recurrence:

$$ $\displaystyle D(i,j)=\min\left\{\begin{array}[]{lll}D(i-1,j)+1&\text{if }i>0; \\ D(i-1,j-1)+1&\text{if }j>0;\\ D(i-1,j-1)+{\bf 1}[A[i]\neq B[j]]&\text{if }i,j>0.\end{array}\right.$ $$

The edit distance between $A$ and $B$ is then captured by $D(n,n)$. When $k<n$, for all $D(i,j)$ such that $|i-j|>k$, because the length difference between $A[1:i]$ and $B[1:j]$ is greater than $k$, $D(i,j)>k$. Since the final answer $D(n,n)\leq k$, those positions with $|i-j|>k$ won’t affect $D(n,n)$. Therefore, we only need to consider the set $\{D(i,j):|i-j|\leq k\}$.

For $d\in[-k,k],r\in[0,k]$, we define $F(r,d)=\max_{i}\{i~{}:~{}D(i,i+d)=r\}$ and let $\textsc{LCP}(i,j)$ denote the length of the longest common prefix of $A[i:n]$ and $B[j:n]$. The algorithm of [] defines $\textsc{Extend}(r,d):=F(r,d)+\textsc{LCP}(F(r,d),F(r,d)+d)$. We have

$$ $\displaystyle F(r,d)=\max\left\{\begin{array}[]{lll}\textsc{Extend}(r-1,d)+1& \text{if }r-1\geq 0;\\ \textsc{Extend}(r-1,d-1)&\text{if }d-1\geq-k,r-1\geq 0;\\ \textsc{Extend}(r-1,d+1)+1&\text{if }d+1,r+1\leq k.\end{array}\right.$ $$

The edit distance between $A$ and $B$ equals $\min_{r}\{r:F(r,0)=n\}$.

To implement LCP, [] uses a suffix tree data structure with initialization time $O(n)$ and query time $O(1)$, thus the total time complexity is $O(k^{2}+n)$. In place of their suffix tree data structure, we use our DP-LCP data structure (Theorem 5.1). This leads to Algorithm 2.

###### Theorem 5.3 .

Given a string $A$ of length $n$. There exists an $\epsilon$-DP data structure DPEditDistance (Algorithm 2) supporting the following operations:

- •
Init$(A\in\{0,1\}^{n})$: It preprocesses an input string $A$. This procedure takes $O(n(\log k+\log\log n))$ time.
- •
Query$(B\in\{0,1\}^{n})$: For any query string $B$ with $w:=D_{\operatorname{edit}}(A,B)\leq k$, Query outputs a value ${\widetilde{w}}$ such that $|w-{\widetilde{w}}|\leq{\widetilde{O}}(k/e^{\epsilon/(\log k\log n)})$ with probability $0.99$. This procedure takes $O(n(\log k+\log\log n)+k^{2}\log^{2}n(\log k+\log\log n))={\widetilde{O}}(k^{2
}+n)$ time.

Figure: Algorithm 2 Differential Private Edit Distance

Again, we divide the proof into runtime, privacy and utility.

###### Theorem 5.1 .

###### Lemma 5.2 ( [ 43 ] ) .

###### Theorem 5.3 .

### 5.1 Time Complexity

We prove the time complexity of Init and Query respectively.

###### Lemma 5.4 .

The running time of Init (Algorithm 2) is $O(n(\log k+\log\log n))$.

###### Proof.

The Init runs DPLCP.Init.
From Theorem 5.1, the init time is $O(n(\log k+\log\log n))$.
∎

###### Lemma 5.5 .

Query (Algorithm 2) runs in time $O((n+k^{2}\log n)(\log k+\log\log n))$.

###### Proof.

The Query runs DPLCP.QueryInit once and DPLCP.Query $k^{2}$ times.
From Theorem 5.1, the query time is $O(n(\log k+\log\log n)+k^{2}\log^{2}n(\log k+\log\log n))$.
∎

###### Lemma 5.4 .

###### Proof.

###### Lemma 5.5 .

###### Proof.

### 5.2 Privacy Guarantee

###### Lemma 5.6 .

The data structure DPEditDistance (Algorithm 2) is $\epsilon$-DP.

###### Proof.

The data structure only stores a DPLCP(Algorithm 3, 4).
From Theorem 5.1 and the post-processing property (Lemma 3.5), it is $\epsilon$-DP.
∎

###### Lemma 5.6 .

###### Proof.

### 5.3 Utility Guarantee

Before analyzing the error of the output of Query (Algorithm 2), we first introduce a lemma:

###### Lemma 5.7 .

Let $A,B$ be two strings. Let $\textsc{LCP}(i,d)$ be the length of the true longest common prefix of $A[i:n]$ and $B[i+d:n]$. For $i_{1}\leq i_{2},d\in[-k,k]$, we have $i_{1}+\textsc{LCP}(i_{1},d)\leq i_{2}+\textsc{LCP}(i_{2},d)$.

###### Proof.

Let $w_{1}=\textsc{LCP}(i_{1},d),w_{2}=\textsc{LCP}(i_{2},d)$. Then for $j\in[i_{1},i_{1}+w_{1}-1]$, $A[j]=B[j+d]$. On the other side, $w_{2}$ is the length of the longest common prefix for $A[i_{2}:n]$ and $B[i_{2}+d:n]$. So $A[i_{2}+w_{2}]\neq B[i_{2}+w_{2}+d]$. Therefore, $(i_{2}+w_{2})\notin[i_{1},i_{1}+w_{1}-1]$. Since $i_{2}+w_{2}\geq i_{2}\geq i_{1}$, we have $i_{2}+w_{2}\geq i_{1}+w_{1}$.
∎

###### Lemma 5.8 .

Let ${\widetilde{r}}$ be the output of Query (Algorithm 2), $r$ be the true edit distance $D_{\operatorname{edit}}(A,B)$. With probability $0.99$, we have $|r-{\widetilde{r}}|\leq O(k(\log k+\log\log n)/(1+e^{\epsilon/(\log k\log n)}))$.

###### Proof.

We divide the proof into two parts.
In part one, we prove that with probability $0.99$, ${\widetilde{r}}\leq r$.
In part two, we prove that with probability $0.99$, ${\widetilde{r}}\geq r-O(k(\log k+\log\log n)/(1+e^{\epsilon/(\log k\log n)}))$.
In Theorem 5.1, with probability $1-1/(300k^{2})$, DPLCP.Query satisfies two conditions. Our following discussion supposes all DPLCP.Query satisfies the two conditions. There are $3k^{2}$ LCP queries, by union bound, the probability is at least $0.99$.

###### Lemma 5.7 .

###### Proof.

###### Lemma 5.8 .

###### Proof.

#### Part I.

Suppose without differential privacy guarantee(using original LCP function instead of our DPLCP data structure), the dynamic programming method outputs the true edit distance.
We define $F^{\prime}_{i,j}$ as the dynamic programming array $F$ without privacy guarantee, $\textsc{Extend'}(i,j)$ be the result of $\textsc{Extend}(i,j)$ without privacy guarantee. Then we prove that for all $i\in[0,k],j\in[-k,k]$, $F_{i,j}\geq F^{\prime}_{i,j}$ holds true.

We prove the statement above by math induction on $i$. For $i=0$, $F(0,0)=F^{\prime}(0,0)=0$.
Suppose for $i-1$, $F(i-1,j)\geq F^{\prime}(i-1,j)$, then for $i$,

$$ $\displaystyle F(i,j)=\max\left\{\begin{array}[]{lll}\textsc{Extend}(i-1,j)+1& \text{if }i-1\geq 0;\\ \textsc{Extend}(i-1,j-1)&\text{if }j-1\geq-k,i-1\geq 0;\\ \textsc{Extend}(i-1,j+1)+1&\text{if }j+1,i+1\leq k,i-1\geq 0.\end{array}\right.$ $$

For $\textsc{Extend}(i-1,j)$, we have

$$ $\displaystyle\textsc{Extend}(i-1,j)=$ $\displaystyle F(i-1,j)+\textsc{DPLCP.Query}(F(i-1,j),F(i-1,j)+j)$ $\displaystyle\geq$ $\displaystyle~{}F(i-1,j)+\textsc{LCP}(F(i-1,j),F(i-1,j)+j)$ $\displaystyle\geq$ $\displaystyle~{}F^{\prime}(i-1,j)+\textsc{LCP}(F^{\prime}(i-1,j),F^{\prime}(i- 1,j)+j)$ $\displaystyle=$ $\displaystyle~{}\textsc{Extend'}(i-1,j)$ $$

The second step is because in Query (Theorem 5.1), ${\widetilde{w}}\geq w$. The third step follows from $F(i-1,j)\geq F^{\prime}(i-1,j)$ and Lemma 5.7. Thus, $F(i,j)=\max_{j_{2}\in[j,j-1,j+1]}\{\textsc{Extend}(i,j_{2})\}\geq\max_{j_{2}
\in[j,j-1,j+1]}\{\textsc{Extend'}(i,j_{2})\}=F^{\prime}(i,j)$. Since ${\widetilde{r}}=\min\{{\widetilde{r}}:F({\widetilde{r}},0)=n\},r=\min\{r:F^{
\prime}(r,0)=n\}$, we have $F(r,0)\geq F^{\prime}(r,0)=n$. Therefore ${\widetilde{r}}\leq r$.

#### Part II.

Let $G(L,R,j):=D_{\operatorname{edit}}(A[L:R],B[L+j,R+j])$. In this part, we prove that the edit distance $G(1,F_{i,j},j)\leq i\cdot(1+O((\log k+\log\log n)/(1+e^{\epsilon/(\log k\log n
)})))$ by induction on $i$.

For $i=0$, $F_{0,0}=0$. The statement holds true. Suppose for $i-1$, $G(1,F_{i-1,j},j)\leq(i-1)\cdot(1+O((\log k+\log\log n)/(1+e^{\epsilon/(\log k
\log n)})))$, then we prove this holds for $i$.

Because $F(i,j)=\max_{j_{2}\in[j,j-1,j+1]}\{\textsc{Extend}(i,j_{2})\}$, there is some $j_{2}\in\{j,j-1,j+1\}$ such that $F_{i,j}=F_{i-1,j_{2}}+\textsc{DPLCP.Query}(F_{i-1,j_{2}},F_{i-1,j_{2}}+j_{2})$. Let $Q:=\textsc{DPLCP.Query}(F_{i-1,j_{2}},F_{i-1,j_{2}}+j_{2})$. Therefore

$$ $\displaystyle G(1,F_{i,j},j)\leq$ $\displaystyle G(1,F_{i-1,j_{2}}+Q,j_{2})+1$ $\displaystyle\leq$ $\displaystyle~{}G(1,F_{i-1,j_{2}},j_{2})+G(F_{i-1,j_{2}},F_{i-1,j_{2}}+Q,j_{2} )+1$ $\displaystyle\leq$ $\displaystyle~{}G(1,F_{i-1,j_{2}},j_{2})+1+O((\log k+\log\log n)/(1+e^{ \epsilon/(\log k\log n)}))$ $\displaystyle\leq$ $\displaystyle~{}i\cdot(1+O((\log k+\log\log n)/(1+e^{\epsilon/(\log k\log n)})))$ $$

The third step follows from Theorem 5.1, and the fourth step follows from the induction hypothesis. Therefore, $r=G(1,F_{{\widetilde{r}},0},0)\leq{\widetilde{r}}\cdot(1+O((\log k+\log\log n)
/(1+e^{\epsilon/(\log k\log n)})))$ and the proof is completed.
∎

###### Remark 5.9 .

To the best of our knowledge, this is the first edit distance algorithm, based on *noisy* LCP implementations. In particular, we prove a structural result: if the LCP has query (additive) error $\delta$, then we could implement an edit distance data structure with (additive) error $O(k\delta)$. Compared to standard relative error approximation, additive error approximation for edit distance is relatively less explored (see e.g., [] for using additive approximation to solve gap edit distance problem). We hope this structural result sheds light on additive error edit distance algorithms.

###### Remark 5.9 .

## 6 Conclusion

We study the differentially private Hamming distance and edit distance data structure problem in the function release communication model. This type of data structures are $\epsilon$-DP against any sequence of queries of arbitrary length. For Hamming distance, our data structure has query time $\widetilde{O}(mk+n)$ and error $\widetilde{O}(k/e^{\epsilon/\log k})$. For edit distance, our data structure has query time $\widetilde{O}(mk^{2}+n)$ and error $\widetilde{O}(k/e^{\epsilon/(\log k\log n)})$. While the runtime of our data structures (especially edit distance) is nearly-optimal, it is interesting to design data structures with better utility in this model.

## Appendix A Proofs for Hamming Distance Data Structure

In this section, we include all proof details in Section 4.

### A.1 Proof of Lemma 4.3

###### Proof of Lemma 4.3 .

Let $E(A),E(A^{\prime})$ be $\textsc{Encode}(A)$ and $\textsc{Encode}(A^{\prime})$. Let $\#(E(A)=S)$ be the number of the same bits between $E(A)$ and $S$, $\#(E(A)\neq S)$ be the number of the different bits between $E(A)$ and $S$. Then the probability that the random flip process transforms $E(A)$ into $S$ is:

$$ $\displaystyle\Pr[{\cal A}(A)=S]$ $\displaystyle=(\frac{1}{1+e^{\epsilon/(2M_{1})}})^{\#(E(A)\neq S)}(\frac{e^{ \epsilon/(2M_{1})}}{1+e^{\epsilon/(2M_{1})}})^{\#(E(A)=S)}$ $\displaystyle=~{}\frac{(e^{\epsilon/(2M_{1})})^{\#(E(A)=S)}}{(1+e^{\epsilon/(2 M_{1})})^{n}}$ $$

Since for each position, Encode changes at most $M_{1}$ bits, and $A$ and $A^{\prime}$ only have one different position. Therefore there are at most $2M_{1}$ different bits between $E(A)$ and $E(A^{\prime})$. So we have

$$ $\displaystyle\frac{\Pr[{\cal A}(A)=S]}{\Pr[{\cal A}(A^{\prime})=S]}$ $\displaystyle\leq(e^{\epsilon/(2M_{1})})^{|\#(E(A)=S)-\#(E(A^{\prime})=S)|}$ $\displaystyle\leq(e^{\epsilon/(2M_{1})})^{2M_{1}}$ $\displaystyle=e^{\epsilon}$ $$

Thus we complete the proof.
∎

###### Proof of Lemma 4.3 .

### A.2 Proof of Lemma 4.4

###### Proof of Lemma 4.4 .

$h$ is a hash function randomly drawn from all functions $[2n]\rightarrow[M_{2}]$. For certain $j$, $h(p)=j$ for all $p$ are independent random variables, each of them equals $1$ with probability $1/M_{2}$, or 0 0 with probability $1-1/M_{2}$. So we have

$$ $\displaystyle\Pr[|T_{j}|\geq 10\log k]$ $\displaystyle=\Pr[\sum_{p\in T}[h(p)=j]\geq 10\log k]$ $\displaystyle=~{}\sum_{d=10\log k}^{|T|}{|T|\choose d}(\frac{1}{M_{2}})^{d}(1- \frac{1}{M_{2}})^{|T|-d}$ $\displaystyle\leq~{}\sum_{d=10\log k}^{|T|}\frac{|T|!}{d!(|T|-d)!}(\frac{1}{M_ {2}})^{d}$ $\displaystyle\leq~{}\sum_{d=10\log k}^{|T|}\frac{|T|^{d}}{d!}(\frac{1}{M_{2}}) ^{d}$ $\displaystyle\leq~{}\sum_{d=10\log k}^{|T|}\frac{1}{d!}(\frac{1}{2})^{d}$ $\displaystyle\leq~{}\frac{1}{(10\log k)!}\sum_{d=10\log k}^{|T|}(\frac{1}{2})^ {d}$ $\displaystyle\leq~{}\frac{1}{200k}$ $$

The fifth step follows from that fact that $|T|\leq k,M_{2}=2k$.

Therefore, by union bound over all $j\in[M_{2}]$, we can show

$$ $\displaystyle\Pr[\forall j\in[M_{2}],|T_{j}|<10\log k]\geq$ $\displaystyle~{}1-2k\cdot(\frac{1}{200k})$ $\displaystyle=$ $\displaystyle~{}0.99.$ $$

Thus, we complete the proof.
∎

###### Proof of Lemma 4.4 .

### A.3 Proof of Lemma 4.5

###### Proof of Lemma 4.5 .

$g$ is a hash function randomly drawn from all functions $[2n]\times[M_{1}]\rightarrow[M_{3}]$. For every single $i\in[M_{1}]$, define event $E_{i}$ as the event that the $2|T_{j}|$ values in $\{g(2(p-1)+A_{p},i)~{}|~{}p\in T_{j}\}\bigcup\{g(2(p-1)+B_{p},i)~{}|~{}p\in T_
{j}\}$ are mapped into distinct positions.

$$ $\displaystyle\Pr[E_{i}]$ $\displaystyle=\prod_{c=1}^{2|T_{j}|}(1-\frac{c}{M_{3}})$ $\displaystyle\geq~{}1-\sum_{c=1}^{2|T_{j}|}\frac{c}{M_{3}}$ $\displaystyle=~{}1-\frac{2|T_{j}|(|T_{j}+1|)}{M_{3}}$ $\displaystyle>~{}1-\frac{2(10\log^{2}k)}{400\log^{k}}$ $\displaystyle=0.5$ $$

The fourth step follows from Lemma 4.4. It holds true with probability $0.99$.

For different $i\in[M_{1}]$, $E_{i}$ are independent.
Therefore, the probability that all $E_{i}$ are false is $(0.5)^{M_{1}}<1/(1000k)$.
By union bound, the probability that for every $j\in[M_{2}]$ there exists at least one $i$ such that $E_{i}$ is true is at least

$$ $\displaystyle 1-M_{2}\cdot 0.5^{M_{1}}\geq$ $\displaystyle~{}1-M_{2}/(1000k)\geq 0.98.\qed$ $$

###### Proof of Lemma 4.5 .

### A.4 Proof of Lemma 4.6

###### Proof of Lemma 4.6 .

From Lemma 4.5, for all $j$, there is at least one $i$, such that the set $\{g(2(p-1)+A_{p},i)|p\in T_{j}\}\bigcup\{g(2(p-1)+B_{p},i)|p\in T_{j}\}$ contains $2|T_{j}|$ distinct values.
Therefore, for that $i$, $E(A)_{i,j,1\sim M_{3}}$ and $E(B)_{i,j,1\sim M_{3}}$ have exactly $2|T_{j}|$ different bits.
For the rest of $i$, the different bits of $E(A)_{i,j,1\sim M_{3}}$ and $E(B)_{i,j,1\sim M_{3}}$ is no more than $2|T_{j}|$.
So we have $0.5\cdot\sum_{j=1}^{M_{2}}\max_{i\in[M_{1}]}(\sum_{c=1}^{M_{3}}|E(A)_{i,j,c}-E
(B)_{i,j,c}|)=0.5\cdot\sum_{j=1}^{M_{2}}2|T_{j}|=|T|=D_{\text{ham}}(A,B)$.
∎

###### Proof of Lemma 4.6 .

## Appendix B Differentiall Private Longest Common Prefix

We design an efficient, $\epsilon$-DP longest common prefix (LCP) data structure in this section. Specifically, for two positions $i$ and $j$ in $A$ and $B$ respectively, we need to calculate the maximum $l$, so that $A[i:i+l]=B[j:j+l]$.
For this problem, we build a differentially private data structure (Algorithm 3 and Algorithm 4). The main contribution is a novel utility analysis that accounts for the error incurred by differentially private bit flipping.

Figure: Algorithm 3 Differential Private Longest Common Prefix, Part 1

Figure: Algorithm 4 Differential Private Longest Common Prefix, Part 2

### B.1 Time Complexity

We prove the running time of the three operations above.

###### Lemma B.1 .

The running time of Init and InitQuery (Algorithm 3) are $O(n\log n(\log k+\log\log n))$

###### Proof.

From Lemma 4.2, the running time of building node $T_{i,j}$ is $O((n/2^{i})M_{1})$.
Therefore the total building time of all nodes is

$$ $\displaystyle\sum_{i=0}^{\log n}\sum_{j=0}^{2^{i}-1}(n/2^{i})M_{1}=\sum_{i=0}^ {\log n}2^{i}\cdot(n/2^{i})M_{1}=O(n\log n(\log k+\log\log n)).$ $$

Thus, we complete the proof.
∎

###### Lemma B.2 .

The running time of Query (Algorithm 4) is $O(\log^{2}n(\log k+\log\log n))$.

###### Proof.

In Query (Algorithm 4), we use binary search. There are totally $\log n$ checks. In each check, we need to divide the interval into $\log n$ intervals and merge their sketches of size $M_{1}M_{2}M_{3}$. So the time complexity is $O(\log^{2}n(\log k+\log\log n))$.
∎

###### Lemma B.1 .

###### Proof.

###### Lemma B.2 .

###### Proof.

### B.2 Privacy Guarantee

###### Lemma B.3 .

The data structure DPLCP (Algorithm 3 and Algorithm 4) is $\epsilon$-DP.

###### Proof.

On each node, we build a hamming distance data structure DPHammingDistance that is $(\epsilon/\log n)$-DP. For two strings $A$ and $A^{\prime}$ that differ on only one bit, since every position is in at most $\log n$ nodes on the tree, for any output $S$, the probability

$$ $\displaystyle\frac{\Pr[\textsc{BuildTree}(A)=S]}{\Pr[\textsc{BuildTree}(A^{ \prime})=S]}\leq(e^{\epsilon/\log n})^{\log n}=e^{\epsilon}$ $$

Thus we complete the proof.
∎

###### Lemma B.3 .

###### Proof.

### B.3 Utility Guarantee

Before analyzing the error of the query, we first bound the error of SketchHammingDistance (Algorithm 3).

###### Lemma B.4 .

We select $M_{1}=\log k+\log\log n+10,M_{2}=1,M_{3}=10$ for DPHammingDistance data structure in BuildTree(Algorithm 3).
Let $z$ be the true hamming distance of the two strings $A[i:i+\mathrm{mid}]$ and $B[i:i+\mathrm{mid}]$.
Let ${\widetilde{z}}$ be the output of SketchHammingDistance(Algorithm 3). When $\epsilon=+\infty$(without the random flip process), then we have

- •
if $z=0$, then with probability $1$, ${\widetilde{z}}=0$.
- •
if $z\neq 0$, then with probability $1-1/(300k^{2}\log n)$, ${\widetilde{z}}\neq 0$.

###### Proof.

Our proof follows from the proof of Lemma 4.6. We prove the case of $z=0$ and $z\neq 0$ respectively.

When $z=0$, it means the string $A[i:i+\mathrm{mid}]$ and $B[i:i+\mathrm{mid}]$ are identical. Therefore, the output of the hash function is also the same. Therefore, the output $S^{A}$ and $S^{B}$ from IntervalSketch(Algorithm 3) are identical. Then ${\widetilde{z}}=0$.

When $z\neq 0$, define set $Q:=\{p\in[\mathrm{mid}]~{}|~{}A[i+p-1]\neq B[j+p-1]\}$ as the positions where string $A$ and $B$ are different. $|Q|=z$.
Note that $M_{1}=\log k+\log\log n+10,M_{2}=1,M_{3}=10$, $S^{A},S^{B}\in\{0,1\}^{M_{1}\times M_{2}\times M_{3}}$.
For every $i^{\prime}\in[M_{1}]$, the probability that $S^{A}_{i^{\prime}}$ and $S^{B}_{i^{\prime}}$ are identical is the probability that all $c\in[M_{3}]$ is mapped exactly even times from the position set $Q$.
Formally, define event $E$ as $[\forall j^{\prime},|\{p\in Q~{}|~{}g(p)=j^{\prime}\}|\bmod 2=0]$. Define another event $E^{\prime}$ as there is only one position mapped odd times from set $Q_{1\sim z-1}$. Then the probability equals

$$ $\displaystyle\Pr[E]=$ $\displaystyle\Pr[E^{\prime}]\cdot\Pr[E|E^{\prime}]$ $\displaystyle\leq$ $\displaystyle~{}\Pr[E|E^{\prime}]$ $\displaystyle=$ $\displaystyle~{}1/M_{3}$ $$

The last step is because $\Pr[E|E^{\prime}]$ is the probability that $g(Q_{z})$ equals the only position that mapped odd times.
There are totally $M_{3}$ positions and the hash function $g$ is uniformly distributed, so the probability is $1/M_{3}$.

For different $i^{\prime}\in[M_{1}]$, the event $E$ are independent. So the total probability that $z^{\prime}\neq 0$ is the probability that for at least one $i^{\prime}$, event $E$ holds true. So the probability is $1-(1/M_{3})^{M_{1}}=1-(1/10)^{\log k+\log\log n+10}>1-1/(300k^{2}\log n)$.
∎

###### Lemma B.5 .

Let $M_{1}=\log k+\log\log n+10,M_{2}=1,M_{3}=10$.
Let $z$ be the true hamming distance of the two strings $A[i:i+\mathrm{mid}]$ and $B[i:i+\mathrm{mid}]$.
Let ${\widetilde{z}}$ be the output of SketchHammingDistance(Algorithm 3).
With the random flip process with DP parameter $\epsilon$, we have:

- •
When $z=0$, with probability $1-1/(300k^{2}\log n)$, ${\widetilde{z}}<(1+o(1))M_{1}M_{3}/(1+e^{\epsilon/(\log k\log n)})$.
- •
When $z>3M_{1}M_{3}/(1+e^{\epsilon/(\log k\log n)})$, with probability $1-1/(300k^{2}\log n)$, ${\widetilde{z}}>(2-o(1))M_{1}M_{3}/(1+e^{\epsilon/(\log k\log n)})$.

###### Proof.

In the random flip process in DPHammingDistance (Algorithm 1,3), the privacy parameter $\epsilon^{\prime}=\epsilon/\log n$. We flip each bit of the sketch with independent probability $1/(1+e^{\epsilon/\log n\log k})$. Then we prove the case of $z=0$ and $z>3M_{1}M_{3}/(1+e^{\epsilon/(\log k\log n)})$ respectively.

When $z=0$, similar to the proof of Lemma 4.7, we view the flipping operation as random variables. Let random variable $R_{i,j,c}$ be $1$ if the sketch $S^{A}_{i,j,c}$ is flipped, otherwise 0 0. From Lemma B.4, $S^{A}$ and $S^{B}$ are identical. Then we have

$$ $\displaystyle|z-{\widetilde{z}}|=$ $\displaystyle\max_{i\in[M_{1}]}\sum_{c=1}^{M_{3}}R_{i,j,c}$ $\displaystyle\leq$ $\displaystyle~{}\sum_{i=1}^{M_{1}}\sum_{c=1}^{M_{3}}R_{i,j,c}$ $$

Since $R_{i,j,c}$ are independent Bernoulli random variables, using Hoeffding’s inequality (Lemma 3.2), we have

$$ $\displaystyle\Pr[|\sum_{i=1}^{M_{1}\times M_{3}}R_{i,j,c}-M_{1}M_{3} \operatorname*{{\mathbb{E}}}[R_{i,j,c}]|>L]\leq e^{-2L^{2}/(M_{1}\times M_{3})}$ $$

When $L=M_{1}\sqrt{M_{3}}$,

$$ $\displaystyle\Pr[|\sum_{i=1}^{M_{1}\times M_{3}}R_{i,j,c}-M_{1}M_{3} \operatorname*{{\mathbb{E}}}[R_{i,j,c}]|>L]\leq$ $\displaystyle e^{-2M_{1}^{2}M_{3}/(M_{1}M_{3})}$ $\displaystyle\leq$ $\displaystyle~{}e^{-2(\log k+\log\log n)}$ $\displaystyle\leq$ $\displaystyle~{}1/(300k^{2}\log n)$ $$

Thus we complete the $z=0$ case.

When $z>3M_{1}M_{3}/(1+e^{\epsilon/(\log k\log n)})$, the proof is similar to $z=0$. With probability $1-1/(300k^{2}\log n)$, we have $|z-{\widetilde{z}}|<(1+o(1))M_{1}M_{3}/(1+e^{\epsilon/(\log k\log n)})$. Thus ${\widetilde{z}}>(2-o(1))M_{1}M_{3}/(1+e^{\epsilon/(\log k\log n)})$.
∎

###### Lemma B.6 .

Let ${\widetilde{w}}$ be the output of Query$(i,j)$ (Algorithm 4), $w$ be the longest common prefix of $A[i:n]$ and $B[j:n]$. With probability $1-1/(300k^{2})$, we have: 1.${\widetilde{w}}\geq w$. 2. $D_{\operatorname{ham}}(A[i:i+{\widetilde{w}}],B[j:j+{\widetilde{w}}])\leq 3M_{
1}M_{3}/(1+e^{\epsilon/(\log k\log n)})$.

###### Proof.

In Query$(i,j)$ (Algorithm 4), we use a binary search to find the optimal $w$. In binary search, there are totally $\log n$ calculations of SketchHammingDistance. Define $\mathrm{threshold}:=1.5M_{1}M_{3}/(1+e^{\epsilon/(\log k\log n)})$. Define a return value of SketchHammingDistance is good if: 1). when $z=0$, ${\widetilde{z}}<\mathrm{threshold}$. 2). when $z>2\cdot\mathrm{threshold}$, ${\widetilde{z}}<\mathrm{threshold}$. $z$ and ${\widetilde{z}}$ are defined in Lemma B.5.

Therefore, by Lemma B.5, each SketchHammingDistance is good with probability at least $1-1/(k^{2}\log n)$. There are $\log n$ SketchHammingDistance in the binary search, by union bound, the probability that all of them are good is at least $1-1/(300k^{2})$.

When all answers for SketchHammingDistance are good, from the definition of binary search, for any two positions $L,R$ such that $D_{\operatorname{ham}}(A[i:i+L],B[j,j+L])=0$, $D_{\operatorname{ham}}(A[i:i+R],B[j,j+R])\geq 2\cdot\mathrm{threshold}$, we have $L\leq{\widetilde{w}}\leq R$. Next, we prove $w\leq{\widetilde{w}}$ and $D_{\operatorname{ham}}(A[i:i+{\widetilde{w}}],B[j:j+{\widetilde{w}}])\leq 3M_{
1}M_{3}/(1+e^{\epsilon/(\log k\log n)})$ respectively.

$w$ is the true longest common prefix of $A[i:n]$ and $B[j:n]$, so we have $D_{\operatorname{ham}}(A[i:i+L],B[j,j+L])=0$. Let $L=w$, we have $w=L\leq{\widetilde{w}}$.

Let $R$ be the minimum value that $D_{\operatorname{ham}}(A[i:i+R],B[j:j+R])\geq 2\cdot\mathrm{threshold}$. Because $D_{\operatorname{ham}}(A[i:i+R],B[j,j+R])$ is monotone for $R$, and ${\widetilde{w}}\leq R$, we have $D_{\operatorname{ham}}(A[i:i+{\widetilde{w}}],B[j:j+{\widetilde{w}}])\leq D_{
\operatorname{ham}}(A[i:i+R],B[j:j+R])=2\cdot\mathrm{threshold}=3M_{1}M_{3}/(1
+e^{\epsilon/(\log k\log n)})$.

Thus we complete the proof.
∎

###### Lemma B.4 .

###### Proof.

###### Lemma B.5 .

###### Proof.

###### Lemma B.6 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. What real world motivation for the privacy definition considered in this paper?

2. What are the novel part of the paper? Is it mainly randomized response which we know is optimal for pure-DP.
soundness: 2
strengths: The bound in the error scales exponentially with $\epsilon$. It is the first paper that studies data structure which provides non-trivial accuracy for measuring string distances, both with respect to the edit distance as well as the hamming distance. 

The query time of the data structure is also sublinear.
summary: The paper studies the problem of estimating distances between a given set of strings and the query string. The distance metric used in this paper is hamming distance and edit distance. For both of these metrics, they give a low-space algorithm that has an error that scales with $O(k/e^{\epsilon/\log(k)})$ and $O(k/e^{\epsilon/\log(k)\log(n)})$, respectively.
weaknesses: To me, it felt like the paper is computing the sketch using known techniques and using randomized response. The rest of the analysis seems more like an analysis of the error due to the randomized response. So, I do not see much of novelty in the paper. I do think the question studied is somewhat interesting, but again I felt that the motivation to study the question and the privacy definition needs a bit more clarification. The motivation for the neighboring relation studied in the paper is a little weak.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: What are some real-world examples where the adjacency notion makes sense?

The max distance of k assumption seems more motivated for edit distance, in applications like DNA. Can you provide more motivation for this assumption on the Hamming distance?

In my opinion, the main contribution of the paper is the edit distance algorithm, of which the LCP is a major subroutine (yet is put in the appendix). Consider shortening sections 3 and 4, and presenting the Hamming distance and LCP algorithms in their own section as “building blocks” towards the main section describing the edit distance algorithm.

The relaxation from a max to a sum in line 323 seems wasteful. Is it possible to do a tighter analysis and shave off a log factor?
soundness: 4
strengths: The algorithms are a novel improvement to string algorithms under differential privacy, for which little was known before. The algorithms are rather simple, have efficient running times, and are analyzed elegantly and tightly.
summary: The paper proposes data structures for computing the Hamming or edit distance of a query string to a given string, assuming the distances are promised to be at most k. The data structures satisfy differential privacy when a single character of the given string is changed. The Hamming distance algorithm adds a random flip step once a standard sketching technique is used. The more involved edit distance algorithm uses the fact that edit distance may be computed using a least common prefix data structure, which may be approximated with a set of private Hamming distance data structures for range queries.
weaknesses: The notion of adjacency used in the privacy guarantee is a bit weak; it applies when a single character of the input set of strings is changed. If each string corresponds to a user (e.g. DNA or utterances), this seems like an inadequate level of privacy for each user.

A second weakness is that the paper requires epsilon to be at least log k (resp. log k log n) in order to obtain non trivial utility guarantees for the Hamming distance (resp. edit distance). These values of epsilon are much better than naive approaches, but are still super-constant; and log n in particular may be too large.

---

confidence: 3
contribution: 1
initial_rating: 3
presentation: 2
questions: I have no questions.
soundness: 3
strengths: 1. The non-private version of this problem is one of the fundamental tasks in data structure.
2. Most theorems and lemmas are clearly stated.
summary: This paper studies differentially privately approximating the bit strings in a database, which is a fundamental problem in data structure. In particular, given datasets $A_1, A_2, \cdots, A_m\in \lbrace 0,1\rbrace^n$, the task is to output a sketch $\hat{e}(\cdot)$ with privacy, which could be used to answer any string query $B\in  \lbrace 0,1\rbrace^n$. Answering each query is private due to the robustness of differential privacy for post-processing.

The authors consider two different natural error metric: Hamming and edit distance. Under the assumption that $||A_i - B||_1 \leq k$ for any $i\in [m]$, for Hamming distance, they provide an algorithm that outputs a private synthetic sketch in $O(mn)$ time, and processes each query in time only $O(mk+n)$. The error inccurs for each query is $O(k\log k /e^{\epsilon/\log k})$. To achieve this, they privatize the algorithm in Porat & Lipsky (2007) by filpping each coordinate according to a carefully chosen probability in the sketch. The results and techniques for edit distance metric is similar.
weaknesses: I would suggest rejecting this paper due to its weakness in both results and techniques.

- For the results, this paper show that when $||A_i - B||_1 \leq k$, the error on approximating Hanmming distance between each $A_i$ and $B$ is $O(k\log k)$ for any constant $\epsilon$, if I understand it correctly. This looks trivial to me. I understand that the error can be reduced by amplifying $\epsilon$, but it is still pretty weak, as it offers little advantage within the most common range of $\epsilon$ over applying the Laplace mechanism to add noise to each coordinate.
- The authors claim that they present a "novel scheme" that flip each bit with certain probability. But to me it is just randomized response, so I am not sure if I agree this is "novel". Besides, it appears to me that Algorithm 1 closely follows the sketching algorithm in Porat & Lipsky (2007).

However, it is possible that I misunderstand the importance of the results or techniques, so I am open to discuss.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: (See Weaknesses section.)
soundness: 2
strengths: Private string edit distance is a natural problem, and the paper provides a thorough treatment of its algorithms, in the sense of analyzing privacy, time, space, and utility. I'm not aware of relevant work in differential privacy (https://arxiv.org/abs/2311.07415 might be closest, but I don't think it directly applies here).
summary: This paper studies the problem of privately computing data structures for answering binary string distance queries: given a collection of $m$ length-$n$ binary vectors, compute a data structure that is $\varepsilon$-DP with respect to the vectors and also approximates string distance between each vector and any arbitrary query vector. The paper provides solutions for both Hamming and edit distance that use time and space (roughly) linear in $m$ and $n$, with accompanying utility guarantees.
weaknesses: 1. I'm confused by the utility guarantees for these algorithms. As stated in Theorem 1.1, for any query string within Hamming distance k of the database strings, it estimates these distances to additive error $\tilde O(k / e^{\varepsilon / \log(k)})$. For the typical setting of small $\varepsilon$, isn't this essentially $\tilde O(k)$ error, which would also be achieved by the trivial algorithm that estimates each distance as 0? How large an $\varepsilon$ is necessary to beat the trivial algorithm? The same question applies for edit distance. I think I must be misunderstanding something here, because it makes the utility guarantees for these algorithms look trivial.

2. The algorithmic novelty for the Hamming distance data structure is unclear. It is described as an adaptation of a non-private approach from the Porat and Lipsky paper -- is it just that algorithm + randomized response, or are other modifications necessary? I understand that the paper positions the main "work" here as the utility analysis, but if there's more algorithmic novelty, it would be good to highlight it. 

3. For boosting, we'd need to pay a privacy cost for each data structure copy. Is there any reason to believe this would actually improve accuracy (for a fixed privacy budget)? That is, if $\varepsilon$ is fixed, is there any reason to use boosting (and divide $\varepsilon$ among the copies)?

4. The paper doesn't attempt to explain the core privatization algorithm for the edit distance problem in the main body, instead spending several pages analyzing algorithms that rely on it. Since the overall privacy guarantee relies on this algorithm, omitting it from the main paper seems odd. More generally, I think the paper is missing sketches of how the algorithms work (maybe because the ideas are simple/familiar to people who work on string distances -- but not to me). Dumping blocks of pseudocode and moving on technically compiles, but it doesn't make for a readable paper.

5. The paper should be clarify its neighboring relation in something more prominent than a footnote, especially since the neighboring relation is more restrictive (change one position in one string) than I expected from the introduction's example (change one string).

Overall, the problems are natural, but I'm not sure what the primary contribution here is supposed to be.