基于本地差分隐私的众包隐私保护方法

赵 龙,龙士工,2

(1.贵州大学计算机科学与技术学院,贵州 贵阳 550025; 2.贵州大学公共大数据国家重点实验室,贵州 贵阳 550025)

0 引 言

随着互联网的飞速发展，众包工作模式已经成为了一种广泛使用的任务执行模式，通过高效协同群智资源来汇聚群体智慧从而有效地解决问题，特别是针对那些单独使用计算机难以完成但是对于个人来说相对简单的任务。由于位置服务的普及，个人位置信息就很轻易地被获取从而进行位置数据挖掘分析。攻击者甚至可以推测出个人的喜好、生活习惯等更为敏感[1-3]的信息。

在目前的研究工作中，文献[4]和文献[5]提供了一种产生虚假位置的保护隐私的方法，用户是在发送个人真实位置的同时，发送产生的假位置进行混杂;文献[6]和文献[7]则是将目前流行的差分隐私技术应用到位置隐私保护领域之中，其工作内容为将可控噪声引入随机机制中，在数据发布环节中，已经证明是可用且有效的。现有的关于位置数据隐私保护的研究工作中，大部分是直接将差分隐私技术应用到位置数据信息发布环节上。文献[8]采用了差分隐私扰动方法在数据发布上进行保护,文献[9]是利用k-匿名技术来保护位置隐私。

在上述位置数据采集模式中，都是用户直接将个人真实的地理位置发送给数据采集者，由数据采集方来进行相关的扰动操作，这样有2个前提：1)数据采集方对于移动用户来说是可信的，并且采集方不会故意泄露甚至贩卖用户的数据信息；2)移动用户愿意将自己的真实位置提供给数据采集方。首先，由于大量的采集方是不可信的，社会上出现很多服务提供商贩卖移动用户的个人数据，导致隐私数据泄露问题普遍存在；其次，由于人们不愿意将自己的精确位置数据暴露在外，因此很难获取其真实数据。根据上述分析，本地化差分隐私技术是处理该情况最好的方法。在本地化差分隐私模型之中，用户的真实数据在流出客户端之前通过满足差分隐私机制进行扰动处理生成近似数据，将近似数据发送给数据收集方。文献[10]采用维诺图方式对路网空间进行划分，客户端对于用户位置数据信息进行差分隐私保护之后发送给服务器，这样便保护了移动用户的位置数据隐私。如果简单地将差分隐私运用到位置数据之中，会有这个问题[11-12]，对于位置数据集来说，由于其敏感度的测量与位置距离有关，如果简单将传统的差分隐私方法用来计算其敏感度，则会涉及位置数据集中最远距离，出现敏感度较大的问题，导致数据的可用性降低。

地理不可区分性[13-14]，是对差分隐私应用在几何空间中的扩展。地理不可区分性引入了距离这一概念，即在用户指定的范围之中，用户的真实位置和产生的近似位置是不能区分的。该机制是将可控的噪声添加到用户的精准位置数据上从而产生出虚假位置。在半径为r的圆形区域范围之中，虚假位置和真实位置之间相似度极高，导致攻击者无法区分两者区别。

本文的主要研究内容是：基于本地化差分隐私技术在众包中的位置数据上的理论与实现，具体来说，本文的主要工作如下：

提出一种地理不可区分性算法应用在众包位置数据保护方法。在不暴露用户的真实位置的情况下，服务器端可以在近似位置上进行空间范围查询，达到其相同的效应同时保护用户的位置数据信息。

提出一种对于网格划分上以工人计数为衡量标准的隐私预算自适应方法，通过各个子网格上的工人计数占比合理分配隐私预算，从而提高隐私预算的利用率。

提出一种二级区域网格划分方法，将差分隐私机制应用在网格划分的人数计数保护上，在数据发布环节中保护地理区域位置计数隐私。

通过实验对本文提出的方法进行验证，表明该方法在数据精确度上具有优势。

1 预备知识

1.1 系统结构

在某一时刻下，移动用户设备拥有一条由该移动设备所生成的位置数据信息，由于前文提到的隐私泄露的问题，用户往往不会发送自己的真实位置给数据采集方，而是先将自己的真实位置进行算法扰动得到近似位置，再将近似位置发送给服务器。服务器通过得到的数据以某种计算方法获取其统计结果。

本文研究的问题系统结构如图1所示。客户端生成扰动位置后发送给服务器端。服务器内包含了地图网格划分、网格人数扰动以及查询结果返回3个模块。

图1 差分隐私的众包位置数据保护系统结构

1.2 本地化差分隐私

本地化差分隐私[15-20](Local Differential Privacy, LDP)与传统差分隐私(Differential Privacy, DP)之间是有区别的，移动用户的位置数据在移动用户设备流出数据之前就已经被扰动过。

定义1 本地化差分隐私(LDP)[9]。随机算法F满足ε-LDP，当且仅当对于a，a1∈A，任意的B⊂Range(A)：

P[F(a)∈B]≤eε×P[F(a1)∈B]

(1)

其中，A、Range(A)分别为函数F的定义域与值域。

定义2 拉普拉斯机制。在点c周围生成噪音点c1的概率随着两者之间的距离为指数递减，其概率密度函数f为：

(2)

性质1 差分隐私的并行性。若2个A1、A2分别是满足ε1、ε2的差分隐私算法，并且应用在独立的数据集上，则组合算法是满足max{ε1，ε2}-差分隐私。

1.3 地理不可区分性

定义3 隐私级别。对任意半径r大于0的范围空间，若该机制满足ε-地理不可区分性[13]，其中ε为差分隐私中的隐私预算，则用户在半径为r的圆形区域内拥有εr-隐私，其中εr为该区域内位置点之间的隐私级别l。

定义4 地理不可区分性。当x，x1∈X，Y是X通过机制G的输出结果，若机制G满足ε-地理不可区分性,则对所有欧氏距离d(x,x1)≤r，其中r为上述机制保护的范围，报告位置点y∈Y，有：

G(x)(y)≤eεd(x,x1)G(x1)(y)

(3)

其中，G(x)(y)表示在该位置点x报告y的概率。式(3)中表示当输入为x与x1时，将得到相同的输出y的概率在eεd(x,x1)范围内。

由于差分隐私的Laplace机制是应用在一维数据之中，而位置坐标却是二维数据，所以首先需要定义一个连续的机制，满足连续平面的地理不可区分性。

定义5 平面拉普拉斯分布[13]。对指定ε∈R2,实际位置x∈R2,对于任意一个进行该机制生成的虚假位置y∈R2，该概率密度函数为：

(4)

公式(5)是以x为中心点的平面Laplace分布。在极坐标下，原点为x的概率密度函数为：

(5)

由于真实情况下，往往都是用离散坐标表示位置点。通过将其离散化，使地理不可区分性机制可以使用到离散的笛卡儿坐标系中。

移动用户真实位置x,向极坐标中的x添加可控噪声(r,θ)，根据离散化操作，获得其近似位置Y={y1,y2,y3,…,yn}，机制的查询函数G(x)(y)作为x点的概率累计函数。由于极坐标映射到笛卡儿坐标系上所产生的不规则性，为保持其数据可用性程度，通过调整隐私参数，满足其地理不可区分性。

令rmax

(6)

其中，u为笛卡儿坐标网格步长单元，σr、σθ为机器绘制坐标中半径和角度的精确度[21]。在直径为rmax的范围内，Gε′满足ε-地理不可区分性，即对d(x,y),d(x′,y)≤r时查询函数G有：

Gε′(x)(y)≤eεd(x,x′)Gε′(x′)(y)

(7)

其中G(x)(y)是在点x报告点y的概率。

2 本地化差分隐私的位置众包流程

满足本地化差分隐私的位置数据保护算法的流程如下：1)用户得到其移动设备所产生的真实位置x，然后通过满足地理不可区分性机制来产生近似位置y，并且发送给服务器；2)服务器收到位置y后对位置数据集进行二级区域划分，得到其每个子区域内的人数计数N；3)服务器将每个子区域内人数进行满足差分隐私的加噪扰动得到扰动数据N1并发布。

数据流向如图2所示。

图2 数据流向

2.1 满足地理不可区分性的位置数据扰动

移动用户获得真实位置数据信息后，由于ε1-地理不可区分性的隐私保护等级限制，需要调整参数ε1的方式保证其可用性。针对个人的真实位置，角度θ和半径r由扰动机制来决定，最后，在需要生成虚假位置的范围内，通过将噪声(r,θ)添加在真实位置上，得到虚假位置y[21]。

2.2 地图划分网格

本文将得到的位置数据集做成一个大型区域网格图[22]，然后均分为4份一级子区域，得到其每个一级子区域内的网格人数统计M，根据每个一级子区域内的网格人数排序，按照人数多少依次划分为3×3、2×3、2×2、2×1的二级子区域网格。分割步骤如图3所示，实际效果如图4和图5所示。

图3 区域网格图划分

图4 一级网格划分

图5 二级网格划分

结合上述内容，满足本地化差分隐私的数据保护算法如算法1所示。

算法1ε-Geo算法

输入：实际位置x，隐私预算ε1、ε2,参数u、q、σr、σθ；

输出：近似位置y，网路图W(Nj,Y)

Step1//位置扰动

For each 用户ui

生成真实位置数据x;

生成虚假位置y;

将虚假位置报告给服务器;

End for

Step2//计数加噪

服务器得到用户报告位置;

将位置数据进行区域二级划分得到W(Ni,Y);

计算每个二级子区域占比Pi;

将每个区域内计数Ni添加对应Laplace噪声生成Nj;

将区域信息W(Nj,Y)发布;

End

3 实验分析

为了验证本文所采用的算法的可行性，本实验采用真实的公共位置数据集Gowalla。共有10163名用户合计456967条用户位置签到数据。为了直观地表现出ε-Geo算法对于位置点的影响，实验采用文献[23]提出的相对误差来判定其算法精确度，用A(f)表示在真实数据集上执行查询f的结果，B(f)表示在扰动后数据集上执行查询f的结果。

(8)

其中，s是一个常数，本实验中，s=0.001×|D|,|D|表示数据集中的位置数据数目。

在位置数据集中随机选取一个用户位置点，对该位置点分别进行以保护范围为200 m、700 m的程度进行算法加噪后以得到的近似位置为中心点0.5 km、1 km、1.5 km范围内的位置点的查询，每次查询执行10次，取其平均相对误差。如图6所示。

ε=0.2

ε=0.5

ε=1

从图6可以看出，随着查询范围的增加，真实位置与近似位置的相对误差会越来越小，在近似位置上查询的结果会更加接近真实结果。当查询范围减小时，误差率会有提升。

本文将ε-DP算法与ε-Geo算法以保护范围为200 m加噪后产生的位置点以1 km为范围作查询的相对误差进行对比，如表1所示。

表1 2种算法相对误差对比

从表1和图7可以看出，对于同范围检索查询的情况下，ε-Geo算法误差率更小，查询精确度提高了至少2.7%。

图7 以1 km为范围查询误差对比

本文将ε-Geo算法对于区域计数加噪的精确度与equal分配隐私预算后计数加噪进行对比，选择区域为一个子区域内拥有过大计数C5和2个二级子区域拥有计数较少C19、C20的区域。从表2和图8可以看出，对于计数区域较小的情况下，ε-Geo算法误差率更小，精确度提高了至少4.62个百分点，对于计数区域较大的情况，ε-Geo算法也同样提高了精确度。

表2 隐私保护强度对比

图8 3个区域的计数精确率对比

4 结束语

根据现在大量的位置数据信息的使用，人们对于自己的个人位置隐私越来越重视，在数据流出移动设备之前就进行差分隐私保护这一方式更加安全。本文提出了一种基于本地化差分隐私的众包隐私保护方法。在用户的真实位置上进行满足差分隐私机制的地理不可区分性加噪方式得到近似位置，发送给服务器方，服务器根据获得的近似位置生成二级网格区域图，并将每个子区域内的人数计数添加满足拉普拉斯机制的噪声得到近似人数，最后进行发布。通过实验可以看出，传统的差分隐私对于地理位置的加噪方式，该算法所使用的地理不可区分性的方式能够降低其查询结果的误差度，并且在近似位置对于与真实位置较远距离的查询和在真实位置上进行查询结果较为接近。研究如何保护众包地理位置隐私的技术具有广阔的研究意义和实际作用，目前将地理不可区分性运用在此方面上的有关研究还比较少，今后笔者将继续研究该方向，提出更佳的算法。