G.O.S.S.I.P 阅读推荐 2022-12-22 PrivTrace

#USENIXSecurity2023 6 个 #每日阅读推荐 172 个 #安全学术论文每日推荐 465 个 #隐私保护 7 个

大家好，今天给大家推荐一篇来自浙江大学，德国CISPA中心，和美国弗吉尼亚大学联合投稿的关于隐私路径生成的文章 PrivTrace: Differentially Private Trajectory Synthesis by Adaptive Markov Models，目前该工作已被 USENIX Security 2023 录用。

路径数据在城市规划，智能交通中有着重要的应用。大量的路径数据需要从携带有定位设备的用户处获得。但作为一种隐私敏感数据，直接分享路径数据可能会暴露用户的敏感信息。传统的隐私保护方法如匿名化方法易受到去匿名化攻击和推断攻击，并不能有效保护路径数据。近年来，差分隐私 (Differential Privacy, DP) 日益成为一种隐私保护的公认标准。目前绝大多数利用差分隐私保护路径数据的工作集中于在一种特定的数据挖掘任务上保护隐私，如社团发现和基于位置的推荐。相对于在单一任务中保护隐私，满足差分隐私的路径数据生成可以产生一系列路径数据。这些数据可以用于多种下游任务；同时由于在数据生成过程中应用了差分隐私技术，根据差分隐私的后向处理 (Post-processing) 性质，在这些数据上得到的数据分析结果也是受到差分隐私保护的。在本工作中，作者提出了一种利用多个马尔可夫模型生成满足差分隐私的路径数据的算法: PrivTrace。

PrivTrace分为三个部分。首先，PrivTrace将路径所在的地理空间进行划分，并基于划分结果将路径数据从连续地理空间的序列转换为离散空间的序列。其次，作者利用路径的离散序列学习马尔可夫模型。最后，通过在马尔可夫模型上进行随机游走生成路径数据。

地理空间划分

作者对地理空间进行两次划分。首先，使用均匀的网格，将地理区域划分为许多大小一致的格子。之后统计每个格子中的路径密度用以二次划分。为了满足差分隐私的要求，作者改变路径密度的计算方式使得路径密度的隐私敏感度 (Sensitivity) 为1，之后向路径密度中加入满足拉普拉斯分布的噪声。根据加噪后的路径密度，作者将密度较大的格子进行二次划分。两次划分后得到的所有格子用作马尔可夫模型中的状态。根据通过不同格子的顺序，每条路径被转化为状态的序列。

马尔可夫模型学习

利用转化为状态序列的路径，作者学习了一阶和二阶两个马尔可夫模型。在模型学习中，作者同样改变马尔可夫模型中转移概率的计算方式使得马尔可夫模型中可以加入拉普拉斯噪声。具体地说，作者把每条路径对马尔可夫模型的贡献值用这条路径的长度正则化，这样得到的模型隐私敏感度为1。同时为了利用路径初始位置的信息，作者设计了基于优化的方法来减轻正则化对初始位置分布的影响。

路径生成

路径生成通过马尔可夫模型上的随机游走进行。随机游走的每一步需要决定使用一阶马尔可夫模型还是二阶马尔可夫模型。通过比较模型预测能力和噪声的影响，作者分析了不同模型的优劣：一阶模型预测能力较弱，受噪声影响较小；二阶模型预测能力强，但受噪声影响较大。基于这一分析，作者提出了两个标准来确定需要更强的预测能力 (选择二阶马尔可夫模型) 还是更小的噪声影响 (选择一阶马尔可夫模型)。通过在地图上的采样，随机游走生成的离散状态序列转换为连续的地理路径数据，即为最终得到的生成数据。