Differentially Private Approximate Pattern Matching

In this paper, we consider the $k$-approximate pattern matching problem under differential privacy, where the goal is to report or count all substrings of a given string $S$ which have a Hamming distance at most $k$ to a pattern $P$, or decide whether such a substring exists. In our definition of privacy, individual positions of the string $S$ are protected. To be able to answer queries under differential privacy, we allow some slack on $k$, i.e. we allow reporting or counting substrings of $S$ with a distance at most $(1+γ)k+α$ to $P$, for a multiplicative error $γ$ and an additive error $α$. We analyze which values of $α$ and $γ$ are necessary or sufficient to solve the $k$-approximate pattern matching problem while satisfying $ε$-differential privacy. Let $n$ denote the length of $S$. We give 1) an $ε$-differentially private algorithm with an additive error of $O(ε^{-1}\log n)$ and no multiplicative error for the existence variant; 2) an $ε$-differentially private algorithm with an additive error $O(ε^{-1}\max(k,\log n)\cdot\log n)$ for the counting variant; 3) an $ε$-differentially private algorithm with an additive error of $O(ε^{-1}\log n)$ and multiplicative error $O(1)$ for the reporting variant for a special class of patterns. The error bounds hold with high probability. All of these algorithms return a witness, that is, if there exists a substring of $S$ with distance at most $k$ to $P$, then the algorithm returns a substring of $S$ with distance at most $(1+γ)k+α$ to $P$. Further, we complement these results by a lower bound, showing that any algorithm for the existence variant which also returns a witness must have an additive error of $Ω(ε^{-1}\log n)$ with constant probability.