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.
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).
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.