提出隐私保护的字符串距离计算方法，支持高效查询与强隐私保障。
On Differentially Private String Distances
- 用随机响应改造位翻转技术处理压缩后字符串
- 哈密顿距离误差≤O~(k/e^{ε/log k})，编辑距离误差≤O~(k/e^{ε/(log k log n)})
- 适合需要隐私保护的数据库距离查询场景
给定一个由 m 个长度为 n 的二进制字符串组成的数据库 A₁,…,Aₘ∈{0,1}ⁿ，基本任务是估计给定查询串 B∈{0,1}ⁿ 与数据库中所有字符串的距离。此外，还需以安全方式发布这些距离统计信息以保证数据库完整性。本文提出针对汉明距离与编辑距离的差分隐私（DP）数据结构。该结构对任意长度的查询序列均满足 ε-差分隐私，且当任意字符串与查询串的最大距离不超过 k 时，可输出 m 个距离估计值。对于汉明距离，查询时间复杂度为 Õ(mk+n)，每项估计误差不超过 Õ(k/e^{ε/log k})；对于编辑距离，查询时间复杂度为 Õ(mk²+n)，误差不超过 Õ(k/e^{ε/(log k log n)})。在中等规模的 k 情况下，两种结构均支持亚线性查询。核心方法为将随机响应技术改造为位翻转过程，应用于压缩后的字符串上。
原文摘要 · Abstract (English)
Given a database of bit strings $A_1,\ldots,A_m\in \{0,1\}^n$, a fundamental data structure task is to estimate the distances between a given query $B\in \{0,1\}^n$ 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(mk^2+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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。