论文标题
最短路径上的私人范围查询
Differentially Private Range Query on Shortest Paths
论文作者
论文摘要
我们在图表上考虑了私有范围的查询，其中查询范围被定义为图形最短路径上的一组边缘。图表中的边缘携带敏感属性，目标是在最短路径上报告这些属性的总和，以计数查询或瓶颈查询中的最小属性。我们使用差异隐私来确保这些查询答案的发布可以保护敏感边缘属性的隐私。我们的目标是开发具有给定隐私预算的报告答案的加性错误的机制。在本文中，我们报告了最短路径上私人范围查询的非平凡结果。对于计数范围查询，我们可以实现$ \ varepsilon $ -DP和$ \ tilde o（n^{1/4}）$ $（\ varepsilon，δ）$ - dp。我们提出了两种算法，在其中，我们通过仔细平衡添加到边缘属性的扰动而控制最终误差，直接将添加到范围查询答案子集（可用于其他范围查询）的子集中。瓶颈范围的查询更容易，可以使用标准技术通过Polyogarithmic添加性错误来回答。
We consider differentially private range queries on a graph where query ranges are defined as the set of edges on a shortest path of the graph. Edges in the graph carry sensitive attributes and the goal is to report the sum of these attributes on a shortest path for counting query or the minimum of the attributes in a bottleneck query. We use differential privacy to ensure that the release of these query answers provide protection of the privacy of the sensitive edge attributes. Our goal is to develop mechanisms that minimize the additive error of the reported answers with the given privacy budget. In this paper we report non-trivial results for private range queries on shortest paths. For counting range queries we can achieve an additive error of $\tilde O(n^{1/3})$ for $\varepsilon$-DP and $\tilde O(n^{1/4})$ for $(\varepsilon, δ)$-DP. We present two algorithms where we control the final error by carefully balancing perturbation added to the edge attributes directly versus perturbation added to a subset of range query answers (which can be used for other range queries). Bottleneck range queries are easier and can be answered with polylogarithmic additive errors using standard techniques.
