Differentially Private Range Query on Shortest Paths
Differentially Private Range Query on Shortest Paths
复制标题
DOI：
10.1007/978-3-031-38906-1_23
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Chengyuan Deng;Jie Ying Gao;Jalaj Upadhyay;Chen Wang
中科院分区：
文献类型：
--
作者：
Chengyuan Deng;Jie Ying Gao;Jalaj Upadhyay;Chen Wang
我们考虑在不同隐私约束下的图上的范围查询，查询范围定义为图的最短路径上的边集。图中的边带有敏感属性，其目标是报告这些属性在最短路径上的总和，以用于计数查询或在跳跃查询中的最小属性。我们使用差异隐私来确保回答这些查询不会侵犯敏感边缘属性的隐私。我们的目标是设计在给定隐私预算的情况下最小化输出的加性误差的机制，为此，我们为最短路径上的私有范围查询开发了第一组非平凡结果。对于计数范围查询，我们可以获得FOR-DP和FOR-DP的相加误差。我们提出了两种算法，通过仔细平衡直接添加到边属性的扰动和添加到范围查询答案(子集)的扰动来控制最终误差。瓶颈范围查询更容易，并且可以用多对数相加误差来回答。
We consider range queries on a graph under the constraints of differential privacy and query ranges are defined as the set of edges on the shortest path of the graph. Edges in the graph carry sensitive attributes and the goal is to report the sum of these attributes on the shortest path forcounting queryor the minimum of the attributes in abottleneck query. We use differential privacy to ensure that answering these queries does not violate the privacy of the sensitive edge attributes. Our goal is to design mechanisms that minimize the additive error of the output with the given privacy budget.For this, we develop the first set of non-trivial results for private range queries on shortest paths. For counting range queries we can achieve an additive error offor-DP andfor-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. Bottleneck range queries are easier and can be answered with polylogarithmic additive errors.