基于极坐标的位置差分隐私保护方法

宋法根 刘佳

摘要：众包作为一种新的工作模式，在实际生活中已经得到广泛的应用。在基于位置的服务（location based service，LBS）应用中，众包同样取得了比较好应用效果。但是在LBS的应用中需要暴露用户的位置信息，这给用户的隐私带来了很大的威胁。差分隐私可以很好地保护用户的隐私，但是会影响众包任务的分配。这篇文章中，结合差分隐私与极坐标变换设计了一种适用于众包活动的位置隐私方法，一方面可以有效地保护用户位置隐私，另一方面又不影响众包任务的分配。

关键词： 众包;隐私保护;差分隐私;信息安全;网络空间安全

中图分类号：TP311.52    文献标识码：A

文章编号：1009-3044（2021）09-0054-02

开放科学（资源服务）标识码（OSID）：

位置信息是一种重要的信息，基于位置的服务（location based service，LBS）在日常生活中已经得到广泛的应用，如在打车、导航、环境监测等领域均取得比较好的应用效果，取得很大的社会效益和经济效益。随着智能手机的普及以及导航系统的进一步完善，LBS必将发挥更大作用，创造更多的价值。但是这也为用户的隐私安全带来了很大的威胁。Wang S ， Sinnott R 等人在[1]中指出，一条轨迹上只需要4个准确的位置记录，90%的轨迹能够确定其对应的用户。若没有有效的隐私保护方法，位置信息被恶意用户使用必然会给正常用户的隐私安全带来非常大的威胁。

差分隐私是一种有效的隐私保护方法，在隐私保护领域，差分隐私已成为隐私保护事实上标准之一。差分隐私对攻击者的所掌握的背景信息不做假设，故而具有较强的隐私保护能力。其主要思想是通过添加噪声，使得修改数据集中的任意一条记录对查询结果都不会有较大的影响，进而有效地保护用户的隐私安全。但是在原始数据上添加噪声，会对原始数据造成一定的破坏，进而影响数据的使用。本文提出一种在极坐标下进行添加噪声的方法，该方法适合用于保护众包活动中用户的位置隐私。

1 众包

众包指的是一个机构把由员工执行的工作任务，外包给非特定的大众志愿者的做法。目前已经广泛应用于现实生活，并取得了很好的效果，创造了很大的经济价值和社会价值。如滴滴打车每天有大量的用户通过众包打乘汽车出行，维基百科创建了通过众包收集信息的典范。

目前众包活动可以分成两类，一类是基于自愿的，即不对完成众包任务的用户提供奖励;如：导航软件中，热心的导航用户会自发的上报道路上交通情况或交通事故情况。另一种是基于激励机制的，如上文提到的滴滴打车，当用户完成对应任务时会得到一定奖励。一般奖励的多少需要根据众包用户完成任务的情况，以及为完成任务时所付出的代价进行计算。对于某一任务其本身的情况是不变的，故在计算应付给用户的报酬时，用户完成任务所付出的代价对起着非常重要的作用，用户付出的代价主要是用户赶往确定地点的过程中所付出的代价，如旅行花费的时间，支付燃料的费用等。可见用户与众包任务的距离在报酬的计算过程中有很大的作用。要精确计算出众包任务与用户的距离，需要知道它们的精确位置，而如果用户共享其精确的位置，势必会泄露用户的隐私。本文提出了一种基于极坐标的差分隐私变换方法，一方面可以保护用户的位置信息不被泄露，另一方面又能够相对精确地得到用户与众包任务的距离。

2 差分隐私

定义1 邻居数据集： 如果数据集[D1]可以通过[D2] 修改、添加或删除一个数据得到，则称[D1]与[D2]为邻居数据集。

定义2。差分隐私：  算法[A]满足差分隐私，对于[ε>0] ，当且仅当对于任意邻居数据集，均满足：

[?T?Rang（A）：Pr[A（D1）∈T]≤eεPr[A（D2∈T）]]       （1）

其中[Pr[A（D1）∈T]]表示算法[A]输出[A（D1）∈T]的概率。

目前实现差分隐私的方法主要有拉普拉斯机制。拉普拉斯机制，是指在查询结果上添加满足拉普拉斯分布的噪声。对于任意查询请求[f]，得到其真实返回值[f（x）]，产生拉普拉斯噪声[n]，最终返回[f（x）+n]，其实满足差分隐私的，其证明过程已在[2]中详细给出，这里不再赘述。

所采用的拉普拉斯噪声[n]，一般位置参数为0，尺度参数为[?（f）/ε]，[n]的概率密度函数为

[p（x）=ε2Δ（f）e-|x|ε/Δ（f）]                                 （2）

其中[Δ（f）] 为查询函数[f]的敏感度，其描述了查询在该数据集上的最大变化情况，其定义式为：[Δ（f）=maxD1，D2f（D1）-f（D2）1] ，其中[D1，D2]为邻接数据集。

公式1中，ε称为差分预算，ε值越小，隐私保护程度越高，需要加入噪声越多。[Δ（f）]描述了，数据集修改一个元素后，对查询结果的影响程度，其值越大，表明敏感度越高，要實现隐私保护，就需要添加更多的噪声。

3 众包位置保护方法

利用差分隐私保护用户的位置隐私，如果直接在用户所在位置的经纬度上添加噪声，必然对用户的位置造成比较大的扰动，进而影响众包中任务与用户之间距离的计算。本文首先以众包任务为原点，建立极坐标系，然后在众包用户的极坐标上添加噪声来实现差分隐私。极坐标中用户与众包任务之间的距离即为极径。为了使得报酬计算的更加合理，在极径上添加较少的噪声，而在辐角上添加较多的噪声，从而保护用户的位置隐私。因为计算报酬时，只关心用户为完成任务所旅行的距离，而不关心用户是从哪个方向来的，所以本方法更适合于众包活动中保护用户的位置隐私。

对于一个众包任务tl的坐标为（tlx，tly），某一worker（w）的坐标为（x，y） 。以点tl为原点，建立极坐标后，w的极坐标为[（ρ，α）]。

[r=（tlx-x）2+（tly-y）2]                                           （3）

[α=arctan（tly-ytlx-x）]                                                 （4）

对于每个众包任务，进行差分隐私变换后，需要重新转换为经常用的经纬度，具体转换方法如公式（4）（5）所示。

[x=tlx+r·cosα]                                                   （5）

[y=tly+r·sinα]                                                   （6）

为减少对众包任务与用户距离的扰动，在r上添加较少的噪声，在辐角上添加较多的噪声，从而保护用户的隐私。具体过程如算法1所示：

算法1众包位置隐私保护方法

输入：众包任务位置记录[TL={tl′1，tl′2…tl′k}]，用户位置记录[WL={wl1，wl2…wln}]

输出：对每个众包任务得到其周围噪声处理后的用户位置记录[WL={WLtl′1，WLtl′2…WLtl′k}] 其中[WLtl′i]表示可以参与众包任务[tli]的所有用户的位置集合。

（1） 对于区域进行均匀划分，计算各个网格中用户的数量;

（2） For each [tl′i∈TL];

（3） 寻找[tl′i]所在单元格，根据单元格用户的密度，估算可以参与总包活动的区域，及圆形区域的半径;

（4） 根据公式（2，3）得到圆形区域内所有用户的极坐标;

（5） 对区域内所有用户的极坐标添加噪声;

（6） 运用公式（4）（5）把添加噪声后的极坐标还原经纬度，把[WLtl′i]加入[WL]

（7） Endfor

（8） Return [WL']

算分1中，首先对众包区域进行网格划分，主要是为了解在整个区域中，众包用户的分布情况。整个区域往往很大，并非所有的用户都有参与该众包任务的意愿，文献[3]中研究发现，如果众包任务和用户的距离大于40km的话，那么用户参与该众包任务的意愿就非常低。故而没有必要对整个区域中所有的用户的位置进行变换。在第3行，根据任务所在网格的用户的分布情况，以及完成任务所需要的用户数，确定可能参与该众包任务的用户所在的区域。若任务tl周围用户的数量较少，显然需要增大[r]，在更大的区域中对更多用户的位置数据进行差分变换，并把变换后的数据发送给众包服务器，以保证更高的任务分配成功率。在第5行，根据众包任务的位置，把其周围区域中用户的坐标转换为极坐标，分别极径和辐角上添加噪声。为了减少噪声对计算众包任务与用户之间距离的影响，在极径上添加相对较少的噪声，而在辐角上添加较多的噪声。第6行，把噪声化的用户的位置信息添加到[WLtl′i]，每一个众包任务，返回一个用户位置集合，最后对所有任务的用户位置集合一起提交给众包服务器，众包服务器根据噪声化后的数据进行任务分配。由于添加噪声时，未对任务与用户之间的距离造成较大的扰动，故而众包服务器在根据用户旅行距离确定报酬时更精确，更合理。

4 结论

本文基于差分隐私与极坐标变换提出了一种保护位置隐私的方法，本方法对众包任务与用户之间的距离扰动较少，故而众包服务器可以更准确地计算出众包任务与众包用户之间的距离，故而支付的报酬更合理。本文对于同一众包任务需要多人协作完成的情况没有考虑，对于需要多个用户同时完成的众包任务，可以当成几个众包任务同时进行分发。

参考文献：

[1] Dwork C.Differential privacy：A survey of results[M]//Lecture Notes in Computer Science.Berlin，Heidelberg：Springer Berlin Heidelberg，：1-19.

[2] To H，Ghinita G，Fan L Y，et al.Differentially private location protection for worker datasets in spatial crowdsourcing[J].IEEE Transactions on Mobile Computing，2017，16（4）：934-949.

[3] 郑袁平，贺嘉，陈珍文，等.关于大数据安全与隐私保护的研究[J].数字通信世界，2019（3）：166，241.

[4] 疏令.基于局部差分隐私的PCMS算法实现[J].电脑知识与技术，2019，15（22）：59-60.

[5] 王家波.基于位置服務的轨迹隐私保护技术研究[D].杭州：杭州电子科技大学，2014.

[6] 魏立斐，陈聪聪，张蕾，等.机器学习的安全问题及隐私保护[J].计算机研究与发展，2020，57（10）：2066-2085.

[7] 冯登国，张敏，叶宇桐.基于差分隐私模型的位置轨迹发布技术研究[J].电子与信息学报，2020，42（1）：74-88.

[8] 郑袁平，贺嘉，陈珍文，等.关于大数据安全与隐私保护的研究[J].数字通信世界，2019（3）：166，241.

[9] 余智欣，黄天戍，杨乃扩，等.一种新型的分布式隐私保护计算模型及其应用[J].西安交通大学学报，2007，41（8）：954-958.

【通联编辑：朱宝贵】