保护位置隐私的效用优化本地差分隐私机制

冯立刚,朱友文,2

(1.南京航空航天大学计算机科学与技术学院,江苏 南京 211106;2.桂林电子科技大学广西密码学与信息安全重点实验室,广西 桂林 541010)

0 引 言

近年来移动智能设备已经成为城市居民的一种标准配置，手机、平板和智能手表成为人们现代化生活不可或缺的一部分。用户随身携带智能设备，依据智能设备的传感器获取的数据，用户能够实时确定自己的位置，然后使用它与基于位置的服务应用进行交互[1-2]。据此，用户可以随时随地访问各种服务，比如查询附近的餐厅[3]、打车[4]、推荐[5]等。无论这些服务的确切性质如何，这些服务都要求用户披露他们的位置[6]，以使应用程序可以按照预期方式进行工作。然而，这种地理位置公开会导致用户失去对其地理位置隐私的控制，因为有一些私密场所，比如家庭住址、礼拜场所等是人们不希望被泄露出去的。毫无疑问对于许多愿意了解更多用户信息的公司来说，用户的地理位置信息是一笔庞大的财富。许多应用程序和公司将收集到的数据用于商业分析[7]、营销、行为定位[8-11]，或者只是将这些信息出售给外部各方。此外，许多移动应用程序会在征得或未经用户同意的情况下跟踪和收集用户的位置，因此，地理位置隐私保护是一个与生活紧密相关的重要问题。

为此，国内外学者提出了许多地理位置隐私保护机制,如k匿名[12]、差分隐私[13]、哑元Dummy[14]和Mix-zone[15]等方法。他们的目标是保护用户的位置隐私，同时仍然允许他们使用地理定位服务。在所有隐私保护机制中，k匿名和差分隐私被广泛采用，并成为大多数后续研究工作的基础。学者们提出了通用的隐私保证，虽然这些保证最初并非用于地理位置隐私保护，但是后来被证明可以成功地应用于位置隐私。传统差分隐私技术通常假设数据收集者是可信任的，忽略了收集者泄露信息的潜在风险。为了克服这一缺点，Google[16]和Apple公司采用本地差分隐私技术(Local Differential Privacy， LDP)[17]。现有采用差分隐私的地理位置隐私保护机制大多数都是基于本地差分隐私。文献[18-19]在地图上构建网格，将每个用户的位置分配给网格中的单元格，然后根据随机响应方案发送网格中随机一个单元格的数据，由于这些方法以相同的方式扰动同一单元中的不同位置，它们很难为每个位置提供一个优化的方案。文献[20]提出了平面拉普拉斯机制，在不需要划分网格的情况下使用拉普拉斯噪声完成位置扰动，但是该机制会产生较大的误差。文献[21]提出的分段机制利用有界噪声分布扰动一个点，也可以在不使用网格的情况下收集地理位置数据。然而该机制将位置点在每个维度进行独立扰动，经常会产生在一个维度中的值与原始位置相似，但在另一个维度中的值却大不相同的扰动位置。因此，由该机制扰动获得的位置其误差往往很大。文献[22]提出平方机制(Square Mechanism， SM)，扰动位置在原始位置附近的矩形中概率较高，其他位置概率较低，其主要目的是在减少单个扰动位置的扰动误差。

然而现有的地理位置隐私保护机制并未考虑这样一个事实，即地理位置的敏感程度是不同的，比起商场、游乐园等公共场所，家庭住址、工作地点显然更加敏感，同时对于不同敏感度的地点，人们的保护意愿也是不同的，敏感地点需要有效保护，非敏感地点可能不需要加以保护，而现有的地理位置隐私保护机制对不同位置的隐私保护程度等同对待。效用优化本地差分隐私(Utility-optimized Local Differential Privacy, ULDP)机制[23]考虑了数据集中包含不同隐私保护级别数据这一情况下的差分隐私，但是仅适用于类别型数据的频率估计，在地理位置隐私保护方面没有应用。本文考虑ULDP机制下的地理位置隐私保护方案，对平方机制加以改造，提出效用优化的平方机制(Utility-optimized Square Mechanism, USM)，该机制使得敏感地点扰动到自身周边概率大，非敏感地点扰动到自身周边概率加大。理论分析证明该机制对于敏感数据满足本地差分隐私，同时在真实地理位置数据集上的实验表明该机制具有较高的效用。

1 背景知识

1.1 本地差分隐私

差分隐私(Differential Privacy, DP)由Dwork[13]定义了正式且可证明的隐私保证。该机制的思想是，无论数据集中是否存在单个元素，对数据集计算的聚合结果都应该几乎相同。换句话说，添加或删除单个元素不应显著改变聚合函数的任何结果的概率。传统差分隐私机制是将数据集中到1个数据中心之后再对数据进行处理，这种方法被称为中心化差分隐私。但是，实际生活中想要找到1个可信的第三方数据中心是十分困难的，因此，用户自己处理个人数据从而达到差分隐私效果的方法应运而生，该方法被称为本地差分隐私。其定义如下:

定义1 对于输入集合X，输出集合Y，任意x，x′∈X，y∈Y，机制M有：

Pr[M(x)=y]≤eε·Pr[M(x′)=y]

(1)

则称机制M满足ε-LDP。

1.2 效用优化本地差分隐私

效用优化本地差分隐私是由Takao等人[23]提出的一种差分隐私机制，该机制针对数据之间隐私保护程度不同这一普遍事实，在本地差分隐私基础上进行了改进，从而使隐私保护的效果得到优化。其定义如下:

定义2 对于输入集合X，输出集合Y，其中敏感输入为Xs，非敏感输入为Xn，敏感输出为Yp，非敏感输出为Yi，扰动机制M有：

1)对于任意输出y∈Yi，存在输入x∈Xn使得Pr[M(x)=y]>0并且任意x′≠x有Pr[M(x)=y]=0。

2)对于任意输出y∈Yp，任意输入x，x′∈X，有Pr[M(x)=y]≤eε·Pr[M(x′)=y]。

则称扰动机制M满足ε-ULDP。

1.3 平方机制

平方机制是Hong等人[22]提出的一种能够基于隐私预算和整体区域大小减少扰动位置误差的地理位置隐私保护方法。该机制着眼于满足本地差分隐私的个体用户位置收集问题,文献[22]中实验表明其在现有使用差分隐私的地理位置隐私保护机制中效果最好。其方案设计如下：

问题设置为在一个给定的二维矩阵平面D=[-d1,d1]×[-d2,d2]上，对某一点p进行扰动。

首先在平面D内找出一个矩阵C*(p)，其边长为w，中心点坐标为c。中心点c需要在保证矩阵整体都在D内的同时，尽可能贴合被扰动点p。对于靠近平面边缘的点，平方机制会将其设置为最靠近点p同时满足矩阵C*(p)整体处于D内的点，即对于维度i有:

(2)

对于经过平方机制S扰动后的点p′=S(p)有:

(3)

定义3 对于点p和扰动得到的点p′，定义MSE作为其效用指标，MSE越小效用越好。有：

(4)

则给定点p其扰动期望值为：

(5)

假设点p在D上是均匀分布的，则：

(6)

其具体计算过程见文献[22]。因为隐私预算ε，整体区域边长d1、d2都是预先给出的，所以ES[MSE(p,p′)]与w直接相关。那么选取w使得ES[MSE(p,p′)]尽可能小就变成了一个优化问题，即：

subject to 0

(7)

平方机制依据经典的COBYLA算法[24]选取最优情况下的边长，该算法使用线性逼近的约束优化进行求值，在此不再详述。

2 效用优化的平方机制

在现有使用差分隐私的地理位置隐私保护机制中，大多数方法都将地理位置的隐私保护程度等同对待。本文将地理位置分为2个部分，敏感区域和非敏感区域，希望能够对敏感区域加以更有效的保护，就像ULDP一样。为此，本文基于ULDP机制对平方机制加以改造，设计一种新的机制，称为效用优化的平方机制。该机制对于敏感区域中的点，其扰动后只可能存在于敏感区域，非敏感区域中的点扰动后可能为自身也可能为敏感区域中的点。这种扰动方式可以在保证敏感区域的安全性的同时降低MSE和提高效用，即任意敏感区域中的点满足LDP且扰动到自身周围概率较大，非敏感区域中的点扰动到自身概率加大，整体MSE更小，效用更好。

2.1 机制设计

在一个给定的二维矩阵平面D=[-d1,d1]×[-d2,d2]中，敏感区域为A={A1,A2,…,An}，其面积为SA，非敏感区域为B，在D上对某一点p进行扰动。机制设计步骤如下：

步骤1 预处理，根据平面边长d1、d2和隐私预算设置下限，由COBYLA算法求出最大最优边长w′，并对每个敏感区域Aj⊂A，1≤j≤n进行检查更新，确保其边长aj1、aj2满足2·min(aj1,aj2)≥w′进行修改调整，这是为保证机制满足ULDP进行的设置。

步骤2 与平方机制相同，根据平面边长d1、d2和隐私预算ε，由COBYLA算法求出矩阵C*(p)和边长w。

步骤3 若p∈B，不进行矩阵C*(p)求取;若p∈Aj，则令矩阵C*(p)的中心点c对于维度i有:

(8)

即对于靠近敏感区域边缘的点，USM会将其设置为最靠近点p同时满足矩阵C*(p)整体处于敏感区域A内的点，如图1所示。

(a) 点p位于敏感区域内部

(b) 点p位于敏感区域边缘图1 矩阵C*(p)位置示意图

步骤4 USM扰动概率为:

当p∈A:

(9)

当p∈B:

(10)

2.2 理论分析

2.2.1 安全性证明

首先证明该机制符合ULDP。

推论1 对于任意的p′∈A，x,x′∈D，有Pr[U(x)=p′]≤eε·Pr[U(x′)=p′]。

证明:

(11)

推论2 对于任意的p′∈B，存在点x∈B使得Pr[U(x)=p′]>0，且任意x′≠x有Pr[U(x′)=p′]=0。

证明:

对任意的p′∈B，当x∈A,Pr[U(x)=p′]=0;

当x∈B∩x≠p′，Pr[U(x)=p′]=0;

当且仅当x=p′，Pr[U(x)=p′]>0。

2.2.2 效用分析

下面证明USM效用好于平方机制，即同等条件下MSE更小。

首先给出USM的效用计算公式。同样使用定义3作为标准，当p为敏感点，有：

(12)

当p为非敏感点，有:

(13)

因为EU[MSE(p,p′)]与ES[MSE(p,p′)]中参数不同，本文无法直接比较，所以使用以下方法来证明：

推论3 同等条件EU[MSE(p,p′)]

证明:

对于EU[MSE(p,p′)]与ES[MSE(p,p′)]两者w相等且固定，因为根据公式(7)可知，w与平面边长d1、d2和隐私预算ε相关，与敏感区域面积SA无关。当敏感区域面积SA扩大，对于敏感点a∈A，其映射到周边矩阵C*(p)概率α·eε减小，MSE增大，效用变差;对于非敏感点b∈B，其映射到自身的概率β减小，MSE增大，效用变差。整体而言，SA与MSE成正相关，SA越大效用越差。当敏感区域A等于整个平面区域D，此时有α=αw，USM退化为平方机制，两者效用EU[MSE(p,p′)]与ES[MSE(p,p′)]相等。由此，可以证得USM效用好于平方机制。

3 实验结果与分析

本文实验环境设置如下：操作系统为Windows10，处理器为AMD Ryzen5 2600，内存为16 GB，显卡为RX580 8 GB。以下首先对机制中的预处理设置做简要说明，然后在2种不同的真实地理位置数据集上进行实验，一种采用南京地图作为数据，一种是Yelp数据集中Las Vegas数据，最后将USM与现有方案中效果最好的平方机制进行对比。

3.1 预处理设置

预处理步骤确保USM符合ULDP，为此可能需要对敏感区域的边长做一定修改。因为敏感区域可能为多个并且边长不等，USM通过EU[MSE(p,p′)]求取w比较复杂，所以本文直接采用平方机制方法对w进行求取。通过计算可以发现，在整体区域边长给定且ε>1的情况下，ε越小，最优边长w越大，ES[MSE(p,p′)]越大，实用性越差。本文在d1=1000,d2=1000,ε={1,2,…,20}的条件下运行COBYLA算法，其实验结果如图2所示。实际使用时可以权衡隐私保护和效用自行设置ε下限。

图2 ε-w关系图

3.2 对比试验

本文采用与平方机制相同的实验设置，隐私预算ε设置为5～20。为了方便进行对比，默认设置敏感区域只有一个且位于中心点，其边长为整体区域长度的1/2。将USM与平方机制进行对比，图3为使用南京地图数据集的实验结果，图4为使用Yelp Las Vegas数据集的实验结果。通过图3和图4的实验结果对比可以发现USM效果明显好于平方机制。

图3 南京地图数据集实验对比

图4 Yelp数据集实验对比

为了防止数据集带来的偏差，本文使用不同的敏感区域进行重复实验。图5为使用南京地图数据集中不同区域作为敏感区域，USM与平方机制的效用对比。可以看出USM效果确实比平方机制有显著提升。

(a) 敏感区域位于整体左下部分

(b) 敏感区域位于整体左上部分

(c) 敏感区域位于整体右下部分

(d) 敏感区域位于整体右上部分图5 不同敏感区域位置南京数据集实验对比

在现实地理位置平面中敏感区域通常为多个。为此，接下来针对二维平面区域内存在多个敏感区域的情况进行实验。本文分别设置敏感区域个数n为2/4/6，每个敏感区域边长为整体区域边长的1/8，敏感区域位置随机分布，重复计算10次取平均值，为了防止最优边长过大导致预处理时发生敏感区域的合并，设置隐私预算ε范围为10～20，在Yelp数据集上实验结果如图6所示，可见，在多敏感区域的情况下USM的效用仍然优于平方机制。

(a) n=2时的Yelp实验结果

(b) n=4时的Yelp实验结果

(c) n=6时的Yelp实验结果图6 多敏感区域下Yelp数据集实验对比

4 结束语

针对现有地理位置隐私保护机制忽略了地理位置敏感度不同这一问题，本文将效用优化的本地差分隐私与平方机制相结合，提出了效用优化的平方机制USM。理论和实验证明，本文的机制相较于现有的机制在效用上有显著的提高。

针对未来的工作，当前的方法将地理位置分为敏感和非敏感2个部分，但是现实生活中仍有将敏感程度进一步划分的需求，目前没有对不同数量的敏感地理位置等级进行处理的机制，也没有框架在不同数量的敏感等级下描述平方机制，因此可以沿着这个方向进行深入探索，这一点可以参考可区分输入的本地差分隐私机制(Min-ID LDP)[25]。同时，矩阵边长w的求取方法也存在进一步优化的可能。最后，在连续轨迹隐私保护场景中，使用差分隐私的地理位置保护机制面临隐私预算难以合理分配以及位置数据失真的挑战，同时也缺乏对不同数量的敏感等级的研究，本文机制可以与一些连续轨迹隐私保护研究[26-28]相结合，探究连续位置隐私保护情境下不同敏感等级的保护机制。