本地距离查询与差分隐私

差分隐私（DP）常用于保护图分析或发布。距离作为图分析的关键因素，通常通过管理者差分隐私（curator DP）处理，即由可信管理者持有所有顶点的完整邻居列表并私有化回答查询。然而，在许多实际场景中，可能不存在这样的管理者，这为在本地差分隐私（LDP）下实现差分私有距离查询带来了重大挑战。

本文提出了两种方法来解决这一挑战。第一种方法通过随机化响应生成合成图，并应用位操作来减少噪声干扰。然而，与其他合成图方法类似，此方法的效用较低。为克服这一限制，我们提出了第二种方法，这是首个专为距离查询设计的LDP方法，该方法通过持续聚合来自相邻顶点的局部距离向量来捕获全局图结构。这一过程能够准确更新全局距离。我们通过全面的理论分析和在真实数据集上的实验评估，证明了我们方法的有效性。

主题分类：
密码学与安全（cs.CR）

引用信息：
arXiv:2508.05518 [cs.CR]
(或此版本的 arXiv:2508.05518v1 [cs.CR])
DOI: https://doi.org/10.48550/arXiv.2508.05518

提交历史：
来自：Weihong Sheng [查看邮箱] [v1]
2025年8月7日星期四 15:48:35 UTC (287 KB)