随着移动互联网、云计算等技术飞速发展,大数据思维模式促进着各行各业数据不断地积累[1]。无论是互联网巨头还是各种社会组织,都越来越多地收集和分析用户数据,使得以位置信息为代表的隐私保护问题受到关注[2-3]。2018年5月25日,欧盟实行了史上最严隐私法规《通用数据保护条例》[4],其条文严格限制所有收集、处理、存储、管理欧盟公民个人数据的企业权限,旨在将个人信息的最终控制权还给用户。
在现实场景中,大量移动应用频繁弹出位置访问授权框,若不同意其政策则无法使用软件程序,这不断侵犯用户说“不”的权利;或者未经许可地利用用户位置数据训练相关推荐、预测、分类等机器学习模型,进而获得用户轨迹、行为模式[5]。第三方直接采集用户位置信息不利于保护用户隐私,会增加个人隐私泄露风险,然而不准确采集用户位置信息,相应的位置服务质量就难以保证,这样也不利于公共利益。因此,在位置数据采集阶段引入隐私保护机制来降低并控制隐私泄露风险、平衡隐私保护与位置数据可用性之间的关系、解决不牺牲用户个人隐私的位置数据分析问题,具有理论意义和实际价值。
大量研究表明,如哑位置[6]、匿名[7]、扰乱[8]、安全多方计算[9]、差分隐私[10-12]等技术,采用修改、隐藏、加密、加噪等可以对位置信息进行保护。尤其,差分隐私保证任意个体数据的存在或缺失不会显著影响隐私保护结果,但现行差分隐私位置数据保护方法多基于可信第三方,引入的噪声会消耗大量隐私预算。本文方案避免可信第三方假设,利用满足本地差分隐私的多级随机应答机制扰动原始位置数据,将噪声位置数据传至采集端,然后分别给出两种场景下直接统计法和期望最大法的区域密度估计,在严格保证用户隐私的同时,提高位置隐私保护方案的可用性,降低了传统方案中将精确位置信息全部汇聚于可信服务器带来的隐私泄露风险。
1 位置隐私保护与本地差分隐私 1.1 位置隐私保护位置服务的主要模式包括位置兴趣点(point of interest, POI)检索、精确导航、位置社交网络、位置运动检测、位置广告推送等。位置服务体系框架通常包含4个实体:移动设备、定位系统(北斗、WiFi定位、基站定位等)、通信网络、服务提供商。
位置隐私保护以用户标识符(如姓名、号码)、位置信息、时间信息、POI信息为保护目标,主要有两种隐私保护系统框架:1)在基于可信第三方的框架中,可信匿名服务器位于用户移动设备和位置服务提供商之间。用户把位置信息传递给集中式可信匿名服务器,把满足隐私要求的扰动数据发送到位置服务提供商。然而,当精确的位置信息全部汇聚于可信匿名服务器时,攻击者很可能窃取到用户设备传送到可信匿名服务器的精确位置数据,潜在的隐私泄露风险巨大。2)在基于不可信第三方的框架中,移动终端用户在本地进行数据隐私保护处理,这种部署方案简易,隐私保护粒度与强度可控性强。虽然位置服务提供商无法获得用户精确信息,但仍能保证位置服务可用。本文基于不可信第三方隐私保护系统框架,提出满足本地差分隐私的位置数据采集方案,并实现不同场景的区域位置密度估计。
1.2 本地差分隐私2006年Dwork等提出严格不依赖背景知识的隐私定义——差分隐私[10]。针对不同应用场景,差分隐私可划分为集中式模型(又称可信管理者模型)和本地模型。目前,差分隐私已经是隐私保护的重要标准,相关定义如下:
定义1 (兄弟数据集)[11]同域
定义2 (差分隐私)[12]给定随机函数A及其输出域O,对于兄弟数据集D和D′,函数A满足ε-差分隐私当且仅当
$ \frac{{\Pr \left[ {A\left( D \right) = O} \right]}}{{\Pr \left[ {A\left( {D'} \right) = O} \right]}} \le {{\rm{e}}^\varepsilon }. $ | (1) |
其中Pr为概率。隐私预算ε控制着攻击者不能确定性地区分随机函数A的任意输出来自D或D′。较小ε提供较强隐私保护,但噪声扰动随之增加。
定义3 (全局敏感度)[13]给定兄弟数据集D、D′,函数A的敏感度ΔA为
$ \Delta A = \mathop {\max }\limits_{D,D'} \left| {A\left( D \right) - A\left( {D'} \right)} \right|. $ | (2) |
定义4 (Laplace机制)[14]给定数值型函数A,当且仅当添加服从参数为ΔA/ε的Laplace分布噪声扰动N后,函数A满足Laplace机制下的ε-差分隐私。
$ N \sim {\rm{Lap}}\left( {0,\Delta A/\varepsilon } \right). $ | (3) |
传统差分隐私主要针对数据发布场景,而本地差分隐私适用于严格保护用户端数据信息场景,用户端通过随机噪声将本地数据扰动后报送给采集端即可实现隐私保护。
定义5 (本地差分隐私)[15]给定随机算法A及其输出域O,对于用户端所有数据对vi和vj,随机算法A满足ε-本地差分隐私当且仅当
$ \frac{{\Pr \left[ {A\left( {{v_i}} \right) = O} \right]}}{{\Pr \left[ {A\left( {{v_j}} \right) = O} \right]}} \le {{\rm{e}}^\varepsilon }. $ | (4) |
可以看出,本地差分隐私保证不论数据采集端接收到何种数据,都不能确定地推断出用户端发送的是vi还是vj。
作为本地差分隐私的典型技术,随机应答[16]采用依概率作答方式来保护用户隐私,已在Google Chrome的隐私保护工具[17]和Apple系统中应用。例如,给定敏感问题答案为“是”或“否”,回答者以掷硬币方式隐蔽作答。若出现正面,则真实作答;若出现反面,则再掷一次硬币,出现正面,则回答“是”,出现反面,则回答“否”。随机应答保证敏感问题作答具有很强的可否认性,即具有隐私保护性。
2 本地差分隐私位置数据采集 2.1 隐私保护位置数据采集基于不可信第三方隐私保护系统框架,满足本地差分隐私的位置数据采集方案具体步骤如下:
步骤1 位置编码。预先布置n个信息采集点(相当于用户端)C={c1, c2, …, cn},以最强信号i标记用户位置(1≤i≤n),n位数组A编码用户当前位置的方式为
$ {A_k} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 1,\\ 0, \end{array}&\begin{array}{l} k = i;\\ 其他. \end{array} \end{array}} \right. $ | (5) |
Ak代表位置数组A的第k位,最强信号对应位置编码1,其他位置为0。
步骤2 第一阶段随机应答。用随机应答机制编码数组A,
$ {R_k} = \left\{ \begin{array}{l} 1,\;\;\;\;\;\;\Pr = \frac{1}{2}f;\\ 0,\;\;\;\;\;\;\Pr = \frac{1}{2}f;\\ {A_k},\;\;\;\;\Pr = 1 - f. \end{array} \right. $ | (6) |
与文[17]的永久随机应答一致,参数f用来调节隐私保护强度,f值越接近1,则隐私保护强度越大。
步骤3 第二阶段随机应答。再次使用随机应答机制编码数组R,
$ \Pr \left( {{U_k} = 1} \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} q,\\ p, \end{array}&\begin{array}{l} {R_k} = 1;\\ {R_k} = 0. \end{array} \end{array}} \right. $ | (7) |
与文[17]的即时随机应答一致,数组U中第k位为1的概率由参数q、p和Rk决定。容易证明步骤2和3的编码方式满足差分隐私(具体证明过程参见文[17])。
步骤4 数据传送。将多阶段随机应答U传送到数据采集端。
步骤1—4在用户端完成,位置数据最终将多阶段随机应答U(可视情况增加随机应答阶段数以增强隐私保护性能)周期性地传输到采集端。
2.2 区域位置密度估计本节给出两个场景下的区域位置密度估计方法。区域位置密度估计问题可定义为在给定时间间隔内,根据采集到的位置数据估计与信息采集点关联的区域位置密度。在信息采集点较少场景下,期望最大法(expectation maximization, EM)效果较好,在信息采集点较多场景下,直接统计法也具有一定优势。
2.2.1 直接统计法设set(U)为数据采集端在给定时间间隔内接收到的第二阶段随机应答数组,set(R)和set(A)分别为第一阶段随机应答数组和原始位置数组。3个数据集大小set(U)、set(R)、set(A)相等。
首先,第二阶段随机应答U中第i位(标记为1)的估计量为
$ \begin{array}{*{20}{c}} {\widehat {{\rm{num}}\left( {{U_i}} \right)} = q \cdot {\rm{num}}\left( {{R_i}} \right) + }\\ {p \cdot \left( {\left| {{\rm{set}}\left( R \right)} \right| - {\rm{num}}\left( {{R_i}} \right)} \right).} \end{array} $ | (8) |
num(Ri)是第一阶段随机应答set(R)中第i位为1的真实数量。同理,num(Ri)的估计量为
$ \widehat {{\rm{num}}\left( {{R_i}} \right)} = \left( {1 - f} \right) \cdot {\rm{num}}\left( {{A_i}} \right) + \frac{1}{2}f \cdot \left| {{\rm{set}}\left( A \right)} \right|. $ | (9) |
可以得到
$ \begin{array}{*{20}{c}} {{\rm{num}}\left( {{A_i}} \right) = \frac{1}{{1 - f}} \cdot }\\ {\left( {\frac{{\widehat {{\rm{num}}\left( {{U_i}} \right)} - p \cdot \left| {{\rm{set}}\left( U \right)} \right|}}{{q - p}} - \frac{{f \cdot \left| {{\rm{set}}\left( U \right)} \right|}}{2}} \right).} \end{array} $ | (10) |
则num(Ai)的估计量为
$ \widehat {{\rm{num}}\left( {{A_i}} \right)} = \frac{1}{{1 - f}} \cdot \left( {\frac{{{N_i} - p \cdot N}}{{q - p}} - \frac{{f \cdot N}}{2}} \right). $ | (11) |
其中:N为给定时间间隔内采集到的第二阶段随机应答U的总数,Ni为给定时间间隔内第二阶段随机应答U中第i位为1的应答个数。
最终,与信息采集点ci关联的位置密度估计量为
$ {\rm{Density}}\left( {{c_i}} \right) = \frac{{\widehat {{\rm{num}}\left( {{A_i}} \right)}}}{{\sum\limits_{y = 1}^n {\widehat {{\rm{num}}\left( {{A_y}} \right)}} }}. $ | (12) |
期望最大法(EM)适用于部分数据缺失的参数估计。在本文给定问题中,第i个信息采集点关联的位置xi由n位数组表示(n为信息采集点个数),其第i位为1,其他位为0。在给定时间内的记录有N条,L={l1, l2, …, lN}是相应的位置记录。当给定第r个位置观测值时,A=xi(1≤i≤n)的生成概率为
$ \Pr \left( {A = {x_i}\left| {{L_r}} \right.} \right) = \frac{{\Pr \left( {A = {x_i}} \right) \cdot \Pr \left( {{l_r}\left| {A = {x_i}} \right.} \right)}}{{\sum\limits_{y = 1}^n {\Pr \left( {A = {x_i}} \right) \cdot \Pr \left( {{l_r}\left| {A = {x_y}} \right.} \right)} }}. $ | (13) |
其中Pr(lr|A=xi)的具体计算方法如下。
给定位置数组A,第一阶段随机应答R的第k位为1和0的概率为
$ \left\{ \begin{array}{l} \Pr \left( {{R_k} = 1\left| {{A_k} = 1} \right.} \right) = 1 - \frac{1}{2}f,\\ \Pr \left( {{R_k} = 1\left| {{A_k} = 0} \right.} \right) = \frac{1}{2}f,\\ \Pr \left( {{R_k} = 0\left| {{A_k} = 1} \right.} \right) = \frac{1}{2}f,\\ \Pr \left( {{R_k} = 0\left| {{A_k} = 0} \right.} \right) = 1 - \frac{1}{2}f. \end{array} \right. $ | (14) |
当Ak=1时,第二轮随机应答U第k位为1和0的概率为:
$ \Pr \left( {{U_k} = 1\left| {{A_k} = 1} \right.} \right) = \left( {1 - \frac{1}{2}f} \right) \cdot q + \frac{1}{2}f \cdot p, $ | (15) |
$ \begin{array}{*{20}{c}} {\Pr \left( {{U_k} = 0\left| {{A_k} = 1} \right.} \right) = }\\ {\left( {1 - \frac{1}{2}f} \right) \cdot \left( {1 - q} \right) + \frac{1}{2}f \cdot \left( {1 - p} \right).} \end{array} $ | (16) |
同理,当Ak=0时,第二轮随机应答U的第k位为1和0的概率为:
$ \Pr \left( {{U_k} = 1\left| {{A_k} = 0} \right.} \right) = \frac{1}{2}f \cdot q + \left( {1 - \frac{1}{2}f} \right) \cdot p, $ | (17) |
$ \begin{array}{*{20}{c}} {\Pr \left( {{U_k} = 0\left| {{A_k} = 0} \right.} \right) = }\\ {\frac{1}{2}f \cdot \left( {1 - q} \right) + \left( {1 - \frac{1}{2}f} \right) \cdot \left( {1 - p} \right).} \end{array} $ | (18) |
给定第r个观测数值lr,记lr, u是lr的第u位(lr, u取值为0或1)。然后,给定xi,其第i位为1,其他位为0。
$ \begin{array}{*{20}{c}} {\Pr \left( {{l_r}\left| {A = {x_i}} \right.} \right) = \left( {\Pr {{\left( {{U_1} = 1\left| {{A_1} = 0} \right.} \right)}^{{l_{r,1}}}} \cdot } \right.}\\ {\left. {\Pr {{\left( {{U_1} = 0\left| {{A_1} = 0} \right.} \right)}^{\left( {1 - {l_{r,1}}} \right)}}} \right) \cdot \cdots \cdot }\\ {\left( {\Pr {{\left( {{U_i} = 1\left| {{A_i} = 1} \right.} \right)}^{{l_{r,i}}}} \cdot } \right.}\\ {\left. {\Pr {{\left( {{U_i} = 0\left| {{A_i} = 1} \right.} \right)}^{\left( {1 - {l_{r,i}}} \right)}}} \right) \cdot \cdots \cdot }\\ {\left( {\Pr {{\left( {{U_n} = 1\left| {{A_n} = 0} \right.} \right)}^{{l_{r,n}}}} \cdot } \right.}\\ {\left. {\Pr {{\left( {{U_n} = 0\left| {{A_n} = 0} \right.} \right)}^{\left( {1 - {l_{r,n}}} \right)}}} \right).} \end{array} $ | (19) |
下面给出用EM法计算Pr(A=xi)的步骤。
1) 初始化。按如下方式指定初始参数:
$ \theta _i^{\left( 0 \right)} = \Pr {\left( {A = {x_i}} \right)^{\left( 0 \right)}} = \frac{1}{n},1 \le i \le n. $ | (20) |
2) E-步。基于当前参数计算后验概率,
$ \begin{array}{*{20}{c}} {\Pr \left( {A = {x_i}\left| {{l_r}} \right.:\theta _i^{\left( t \right)}} \right) = }\\ {\frac{{\theta _i^{\left( t \right)} \cdot \Pr \left( {{l_r}\left| {A = {x_i}} \right.} \right)}}{{\sum\limits_{y = 1}^n {\theta _y^{\left( t \right)} \cdot \Pr \left( {{l_r}\left| {A = {x_y}} \right.} \right)} }}.} \end{array} $ | (21) |
3) M-步。更新θi,
$ \theta _i^{\left( {t + 1} \right)} = \frac{1}{N} \cdot \sum\limits_{r = 1}^N {\left( {\Pr \left( {A = {x_i}\left| {{l_r}:\theta _i^{\left( t \right)}} \right.} \right)} \right)} . $ | (22) |
4) 迭代。迭代终止条件为
$ {\max_i}\left| {\theta _i^{\left( {t + 1} \right)} - \theta _i^{\left( t \right)}} \right| < \gamma . $ | (23) |
最终,与信息采集点ci关联的特定区域位置密度估计为
$ {\rm{Density}}\left( {{c_i}} \right) = \theta _i^{\left( {t + 1} \right)}. $ | (24) |
本文采用错误率来评价算法的有效性。Δ(ci)为与信息采集点ci关联区域的真实位置密度与估计密度的差值。
$ E = \frac{1}{n} \cdot \sum\limits_{i = 1}^n {\left| {\Delta \left( {{c_i}} \right)} \right|} . $ | (25) |
为模拟位置数据不足和位置数据量充足这两种采集场景,信息采集点数量分别设置为4、40、400个,均匀覆盖边长为100的正方形区域,位置数据由均匀分布模拟产生(其他分布数据实验效果一致),数据量大小分别为0.4万个、4万个、40万个。多阶段随机应答机制参数设置为:f=0,q=0.75,p=0.25(与RAPPOR[17]一致)。易得此时隐私预算为ε=ln 9。
3.2 实验结果分析图 1为数据量大小为40万个时,信息采集点数量对算法性能的影响。因为信息采集点数量与位置数据编码长度相关,在均匀分布情况下,随着信息采集点数量增加,EM法和直接统计法的位置密度估计错误率均降低。当信息采集点数量较少时,EM算法性能较好,当信息采集点数量增加时,两种算法性能趋于接近。
图 2为信息采集点数量为40个时,数据量大小对算法性能的影响。两种算法性能随着数据量增大而提高,当数据量较小时,EM法在区域位置密度估计方面性能优于直接统计法,但随着数据量增大,二者性能相近,这也表明了本文方案具有可用性。
为验证第一阶段随机应答中参数f对算法性能的影响,设置信息采集点数量为400个、数据量为40万个,第二阶段随机应答参数p=0.25、q=0.75。如图 3所示,参数f越大,算法错误率越高,因为参数f的大小与添加噪声的大小成正比,但随着噪声增加,隐私保护性能提升。可以看到,随着参数f增大,相比于直接统计法,EM法错误率较低,在保证较高可用性的同时,具有良好的位置数据的隐私保护性能。
与参数f实验结果一致,在第二阶段随机应答参数p、q实验中,随着p增大、q减小,隐私保护强度增大,两种算法错误率也随之升高;但相比于直接统计法,EM法具有较低的错误率。总之,模拟位置数据实验验证了运用本文方案采集的位置数据估计相应的区域位置密度统计量的可行性。
4 总结本文给出了基于本地差分隐私的位置数据采集方案,采用多阶段随机应答实现了满足本地差分隐私的位置数据采集,并通过模拟实验对比了直接统计法和EM法进行区域位置密度估计的效果。结果发现:在小样本数据量场景下,EM法估计性能较优;采集的位置数据样本量较大时,两种方法性能相近。本文方案保证了数据贡献者在本地对位置数据进行隐私处理情况下,位置数据采集者仍可以进行基于非原始数据的区域位置密度估计。下一步工作会将本文方案拓展到其他位置隐私保护应用问题,并在现实场景中部署应用。
[1] |
GAO Z Q, SUN Y X, CUI X L, et al. Privacy-preserving hybrid K-means[J]. International Journal of Data Warehousing and Mining (IJDWM), 2018, 14(2): 17. |
[2] |
JIANG H B, ZHAO P, WANG C. RobLoP:Towards robust privacy preserving against location dependent attacks in continuous LBS queries[J]. IEEE/ACM Transactions on Networking, 2018, 26(2): 1018-1032. DOI:10.1109/TNET.2018.2812851 |
[3] |
高志强, 崔翛龙, 周沙, 等. 本地差分隐私保护及其应用[J]. 计算机工程与科学, 2018, 40(6): 1029-1036. GAO Z Q, CUI X L, ZHOU S, et al. Local differential privacy protection and its applications[J]. Computer Engineering and Science, 2018, 40(6): 1029-1036. DOI:10.3969/j.issn.1007-130X.2018.06.010 (in Chinese) |
[4] |
PHILIP R K. General data protection regulation (GDPR) and paediatric medical practice in Ireland: A personal reflection[J/OL]. Irish Journal of Medical Science, 2018. (2018-06-29). https://doi.org/10.1007/s11845-018-1857-3.
|
[5] |
WANG Y J, CAI Z P, TONG X R, et al. Truthful incentive mechanism with location privacy-preserving for mobile crowdsourcing systems[J]. Computer Networks, 2018, 135: 32-43. DOI:10.1016/j.comnet.2018.02.008 |
[6] |
GHINITA G. Privacy for location-based services[J]. Synthesis Lectures on Information Security Privacy & Trust, 2013, 4(1): 1-85. |
[7] |
SUN X X, WANG H, LI J Y, et al. Enhanced P-sensitive K-anonymity models for privacy preserving data publishing[J]. Transactions on Data Privacy, 2008, 1(2): 53-66. |
[8] |
ARDAGNA C A, CREMONINI M, DE CAPITANI DI VIMERCATI S, et al. An obfuscation-based approach for protecting location privacy[J]. IEEE Transactions on Dependable and Secure Computing, 2011, 8(1): 13-27. DOI:10.1109/TDSC.2009.25 |
[9] |
GONG L M, LI S D, WU C Y, et al. Secure "ratio" computation and efficient protocol for general secure two-party comparison[J]. IEEE Access, 2018, 6: 25532-25542. DOI:10.1109/ACCESS.2018.2827025 |
[10] |
DWORK C, ROTHBLUM G N, VADHAN S. Boosting and differential privacy[C]//2010 IEEE 51st Annual Symposium on Foundations of Computer Science. Las Vegas, USA, 2010: 51-60.
|
[11] |
DWORK C, POTTENGER R. Toward practicing privacy[J]. Journal of the American Medical Informatics Association, 2013, 20(1): 102-108. DOI:10.1136/amiajnl-2012-001047 |
[12] |
DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis[M]//HALEVI S, RABIN T. Theory of cryptography. Berlin, Germany: Springer, 2012, 3876: 265-284.
|
[13] |
GAO Z Q, WANG Y T, DUAN Y Y, et al. Multi-level privacy preserving data publishing[J]. International Journal of Innovative Computing and Applications, 2018, 9(2): 66-76. |
[14] |
LI Y, YANG J, JI W. Local learning-based feature weighting with privacy preservation[J]. Neurocomputing, 2016, 174: 1107-1115. DOI:10.1016/j.neucom.2015.10.038 |
[15] |
FANTI G, PIHUR V, ERLINGSSON Ú. Building a RAPPOR with the unknown:Privacy-preserving learning of associations and data dictionaries[J]. Proceedings on Privacy Enhancing Technologies, 2016, 2016(3): 41-61. DOI:10.1515/popets-2016-0015 |
[16] |
TIAN X Y, TAYLOR J. Selective inference with a randomized response[J]. The Annals of Statistics, 2018, 46(2): 679-710. DOI:10.1214/17-AOS1564 |
[17] |
ERLINGSSON Ú, PIHUR V, KOROLOVA A. RAPPOR: Randomized aggregatable privacy-preserving ordinal response[C]//Proceedings of 2014 ACM SIGSAC Conference on Computer and Communications Security. Scottsdale, USA: ACM, 2014: 1054-1067.
|