欢迎来到 黑吧安全网 聚焦网络安全前沿资讯,精华内容,交流技术心得!

差分隐私保护:从入门到脱坑

来源:本站整理 作者:佚名 时间:2018-09-10 TAG: 我要投稿
对于拉普拉斯机制,我们进行以下定义:给定数据集D,设有函数f:D->Rd,其敏感度为Δf,那么随机算法M(D)=f(D)+Y提供ε-差分隐私保护,其中Y~Lap(Δf/ε)为随机噪声,服从尺度参数为Δf/ε的拉普拉斯分布。
指数机制
由于拉普拉斯机制仅适用于数值型结果,在一些特定场景中,往往需要返回离散型结果,例如某一方案或某一实体等。对此,McSherry等人提出了指数机制。
设查询函数的输出域为Range,域中的每个值r∈Range为一实体对象。在指数机制下,函数q(D,r)->R成为输出值r的可用性函数,用来评估输出值r的优劣程度。
对于指数机制,我们进行以下定义:设随机算法M输入为数据集D,输出为一实体对象r∈Range,q(D,r)->R为可用性函数,Δq为函数q(D,r)->R的敏感度。若算法M以正比于exp(εq(D,r)/2Δq)的概率从Range中选择并输出r,那么算法M提供ε-差分隐私保护。
组合性质
性质1
假设有n个随机算法K,其中Ki满足εi-差分隐私,则{Ki}(1
性质2
设有n个随机算法K,其中Ki满足εi-差分隐私,且任意两个算法的操作数没有交集,则{Ki}(1
0×02 实例
拉普拉斯机制
ID
hasCancer
01
Yes
02
No
03
Yes
04
No
···
···
我们设上述数据集为D,用于统计个体是否患有癌症。以计数函数为例,即count(D)函数,用于表示数据集D中共有n条hasCancer属性值为Yes的数据,即该数据集中共有n人患有癌症,该函数的敏感度为1,具体计算方法可参考相关论文。
为了方便计算,我们假设此时的隐私预算ε为1,则Δf/ε=1,即返回结果为count(D)+Lap(0,1)。
import numpy as np
loc, scale = 0., 1.
s = np.random.laplace(loc, scale, 1)
result= realResult + s[0]
print result
import numpt as np
import matplotlib.pyplot as plt
loc, scale = 0., 1.
s = np.random.laplace(loc, scale, 1000)
result_list = list(map(lambda x : x+50,s))
plt.hist(result_list, 30, density=True)
plt.show()
假设在上述数据集中,count(D)的真实结果为50,图4展示了重复1000次后的结果分布,基本符合拉普拉斯分布。

图4
指数机制
ID
disease
01
Cancer
02
HIV
03
HIV
04
HPV
···
···
我们设上述数据集为D,用于统计个体所患疾病的种类,为了方便计算,我们假定上述数据集中disease属性仅有三种类型,即Cancer、HIV和HPV。现在希望能够获得患者最多的疾病类型。在该场景下,可用性函数q(D, r)为数据集D中疾病r的患者数目,显然该函数Δq=1。
disease
可用性
Cancer
50
HIV
20
HPV
30
  为了方便计算,我们假设此时的隐私预算ε为1。
disease
exp(εq(D,r)/2Δq)
概率
Cancer
exp(25)
0.9999
HIV
exp(10)
3*10^-7
HPV
exp(15)
0.00004
为了比较不同隐私预算ε的影响,我们进一步比较隐私预算ε分别取值为0,0.1和0.5时的情况。
disease
ε=0
ε=0.1
ε=0.5
Cancer
0.333
0.628
0.993
HIV
0.333
0.124
0.006
HPV
0.333
0.231
0.001
上述结果也验证了我们的结论,即隐私预算ε越大,数据可用性越高,安全性越低,当隐私预算ε=0时,数据失去意义。
0×03 总结
上面只是差分隐私保护的简单应用,要想应用在生产环境中,还需要针对具体场景对算法进一步改造,但差分隐私保护的思想是不变的。差分隐私提供针对隐私保护的方法提供了形式化的定义,让信息安全人员和数据管理员对当前环境中的隐私保护情况有一个可量化的指标。另外,差分隐私提供了一种无关攻击者背景知识的数据保护方案,相比k-anonymity、l-diversity和t-closeness等方法更具优势。
在早期,人们很难证明我的方法保护了隐私,更无法证明究竟保护了多少隐私。现在差分隐私用严格的数学证明告诉人们,只要你按照我的做,我就保证你的隐私不会泄露。[6]
在这个意义上,差分隐私的出现可以说是具有重大意义的,它将隐私保护这一工程问题进行抽象,变为数学问题,
本文介绍了中心化的差分隐私方法,引出了主流的拉普拉斯机制和指数机制,关于机制实现ε-差分隐私保护的数学证明,可以在文章差分隐私若干基本知识点介绍(一)和差分隐私若干基本知识点介绍(二)中获得,其中的数学知识基本在高中范围。
而背景介绍中Google、苹果等公司采用的本地化差分隐私方法,是差分隐私保护的另一分支,在本地化差分隐私中,由于没有全局敏感度的概念,因此本文介绍的拉普拉斯机制和指数机制不再适用,大多数方案采用随机响应机制,如果可能将在后期的文章中介绍。
参考文献
[1] Narayanan, Arvind, and Vitaly Shmatikov. “Robust de-anonymization of large sparse datasets.” Security and Privacy, 2008. SP 2008. IEEE Symposium on. IEEE, 2008.
[2] De Montjoye, Yves-Alexandre, et al. “Unique in the crowd: The privacy bounds of human mobility.” Scientific reports 3 (2013): 1376.
[3] Dwork, Cynthia. “Differential privacy: A survey of results.” International Conference on Theory and Applications of Models of Computation. Springer, Berlin, Heidelberg, 2008.
[4] 熊平, 朱天清, and 王晓峰. “差分隐私保护及其应用.” 计算机学报 37.1 (2014): 101-122.
[5] Erlingsson, Úlfar, Vasyl Pihur, and Aleksandra Korolova. “Rappor: Randomized aggregatable privacy-preserving ordinal response.” Proceedings of the 2014 ACM SIGSAC conference on computer and communications security. ACM, 2014.
 

上一页  [1] [2] 

【声明】:黑吧安全网(http://www.myhack58.com)登载此文出于传递更多信息之目的,并不代表本站赞同其观点和对其真实性负责,仅适于网络安全技术爱好者学习研究使用,学习中请遵循国家相关法律法规。如有问题请联系我们,联系邮箱admin@myhack58.com,我们会在最短的时间内进行处理。
  • 最新更新
    • 相关阅读
      • 本类热门
        • 最近下载