精华内容
下载资源
问答
  • 随着大数据时代的到来,人们在便利和隐私之间的矛盾在不断放大。本文介绍了差分隐私的基本概念,让大家能理解差分隐私的思想,并且带大家理解如何使用拉普拉斯分布来实现差分隐私

    差分隐私

    差分隐私通过在统计结果中加入了适量噪音以确保修改数据集中一条个体记录不会对统计结果造成显著影响,从而满足了隐私保护的要求。即便攻击者掌握了除一条数据外的全部其他的数据记录,差分隐私仍然能够防止攻击者分析出他不掌握的那条数据信息,有效避免了数据发布导致隐私泄露的问题。
    差分隐私是有严格的、可量化的隐私保护模型。假设D和D’为相邻数据集,S为在随机函数A所有可能的输出,Pr为A(D1)获得某个值的概率。那么只要算法满足下面的公式则可以说此算法满足ε -差分隐私的标准。
    dp

    图1 DP标准

    为更好的理解差分隐私,下面对相关名词进行说明

    相邻数据集

    两个数据集只相差一条记录。

    灵敏度

    差分隐私保护可以通过在查询函数的返回值中加入噪声来实现,但是噪声的大小同样会影响数据的安全性和可用性。通常使用敏感性作为噪声量大小的参数,表示删除数据集中某一记录对查询结果造成的影响。敏感度分为全局敏感度和局部敏感度,通常情况下采用全局敏感度会加入过大的噪音,使数据失真,但若使用局部敏感度,在一定程度上就会泄露数据分布信息,这个时候就有了平滑敏感度

    对于一个查询函数:,d为正整数,D为一个数据集的集合,代表的函数的灵敏度由下面公式定义:
    D,D’是相邻数据集,敏感度是查询函数作用在相邻数据集中差值最大的那一个,当数据集针对全局时,Δf就是全局敏感度。当数据针对部分数据集时,Δf就是局部敏感度。
    为了更好的理解差分隐私的作用,下面用一个例子来说明

    例子

    假设我们有一个医疗记录数据库 D1 在那里每条记录是一对 (名字, x), 其中 X 是一个布尔值表示一个人是否患有心脏病。例如:

    姓名有心脏病
    Rose
    Eric
    Joey
    Phoebe
    Chandler
    图2 医疗记录

    假设一个恶意用户 (通常被称为攻击者) 想知道Chandler是否有心脏病。假设他知道Chandler在数据库的哪一行。攻击者只能使用特定形式的查询Qi返回数据库中前i行中第一列 X 的部分总和。攻击者为了获取Chandler是否有心脏病的信息。只需要执行两个查询 Q5(D1)和Q4(D1),分别计算前五行和前四行的总和,然后计算两个查询的差别。在本例中Q5(D1)=3,Q4(D1)=2,差是1。攻击者在知道Chandler在第5行的情况下,就会知道他的心脏病状况是1(有心脏病)。这个例子显示了即使在没有明确查询特定个人信息的情况下, 个人信息如何被泄露。
    如果我们用(Chandler,0)代替(Chandler,1)构造D2,那么这个恶意攻击者将能够通过计算每个数据集的Q5-Q4来区分D2和D1。 如果攻击者被要求通过ε -差分隐私算法接收Qi值,对于足够小的ε,则他将不能区分这两个数据集。
    在上面医学数据库的例子中,如果我们认为f是函数Qi,那么,因为任意两个相邻数据集的差值是0或者1,所以函数的灵敏度就是1。

    差分隐私拉普拉斯实现

    Laplace 分布

    Laplace分布是统计学中的概念,是一种连续的概率分布。如果随机变量的概率密度函数分布为:

    那么它就是拉普拉斯分布。其中, μ 是位置参数, b 是尺度参数。画出来就是长这样:
    Laplace

    图 3 拉普拉斯分布

    我们之前提到过,保护数据隐私的方法就是将原有的单一查询结果概率化。Laplace噪声就给我们提供了一个很好的概率化的方法。继续上面的例子,假如查询为“查询数据集中患有心脏病的人数”,并且查询结果为“2”:在传统模式下,输出就是2;在差分隐私模式下,会以比较大概率输出2左右的结果,也会以比较小的概率输出和2差别比较大的结果。但是,我们需要保证输出的期望为2(保证数据有效性)。

    拉普拉斯实现DP

    那么这个概率怎么用Laplace分布来实现呢?我们可以直接在输出结果2上加均值为0的噪声。直观上来说,我们通过Laplace将查询结果概率化了。然后拉普拉斯噪声就正好能满足差分隐私的要求。那么Laplace噪声是如何产生符合差分隐私的噪声的呢?我们想一下差分隐私的设计目标:当相邻数据集求结果时,两者的结果不会相差太大。那么相邻数据集在真实情况下会相差多少呢?研究这个问题是因为我们不限定用户对数据集做出什么样的查询,直观上来说,如果查询的是人数,那么相邻数据集相差不大(只会相差1),只需要加一个小一点的噪声即可造成两个结果的混淆;那如果我们查询的是人的工资呢,加一个很小的噪声显然是无法满足应用需求的(因为数据相差太大,稍微对数据的改变依然可以看出数据差别很大)。由此可见,如何设计DP机制是和查询紧密相关的。所以我们需要对查询有一个简单的了解:
    因此,我们用到了上面提到的敏感度这一个概念。由于数据集中少一条记录就会对数据查询f的结果结果造成一定的影响,我们自然想知道,这个影响最大是多少呢?也就是上述定义中给出的敏感度的值Δf了。
    有了 Δf 之后,我们自然想: Δf 越大,噪声应该越大, Δf 越小,噪声应该越小。这就给我们设计接下来的机制给了一定的启发。
    拉普拉斯机制:给定查询函数 ,拉普拉斯机制可以表示为:
    查询机制

    图 4 拉普拉斯查询机制

    其中, Yi是独立同分布的变量,为 Lap(Δf /ε)
    接下来我们将说明,上面的Laplace机制就能满足ε-DP。证明过程如下:
    令b=Δf /ε
    假设px表示ML(x,f,ε)的pdf(probability density function),py表示ML(x,f,ε)的pdf,则对于某个输出z,我们有:
    推导

    图 5 拉普拉斯符合DP推导

    推导过程中进行了二次缩放,第一次缩放用到了绝对值不等式进行缩放,第二个缩放用到了上面我们的定义,由此我们就可以证明拉普拉斯分布可以用来实现差分隐私。
    然后我们要求拉普拉斯的概率累计函数,因为期望等于μ,而差分隐私要求期望等于0,所以直接令μ=0进行就算。
    求得概率累计函数在x<μ时等于1/2exp(x/b),当x>=μ时,等于1-1/2exp(-x/b)。然后可以通过每次随机数的大小算出x的值。
    当p<0.5时候,x=log(2); 当x>=0.5时,-blog(2-2p)(以此为例子,前一个同理可得);
    噪声大小

    图 6 拉普拉斯噪音大小

    有了上面的公式,代码的实现就简单了。
    噪音大小和累加和的值大小无关,只和敏感度与ε有关,因为我们只需要假如一定的噪音,让攻击者无法识别出相邻集的差值究竟是多少就行了。
    假设一个医院的心脏病患者相邻集的数值分别是5000和5001,然后外界接口进行查询时,我们加入拉普拉斯噪音在返回,在分别调用接口1000次返回数据集如下。当攻击者获得某次数据的值根本不可能推导出相邻集的数据差值,也就保护了相邻集的那一条数据的隐私。
    数据集可视化

    图 7 拉普拉斯算法返回数据集

    一些缺点

    当攻击者能够查询足够次数接口时,攻击者能够根据查询出来的接口的频次大概反推出原始数据的值大小,因为噪声的返回是符合拉普拉斯分布的,此时攻击者也能够拿到相邻集的差值。这应该算拉普拉斯实现的一点缺点吧,但我们可以限制查询次数,或者通过加入多组ε-差分隐私来进行对抗。
    差分隐私的拉普拉斯实现只能对数值型的数据发布起到保护作用,对于非数值型数据的话,拉普拉斯机制就不好处理了,此时就需要其他的实现机制来保护了,比如指数机制等。

    结语

    在大数据的时代中,各公司都在利用数据提供更好的服务的同时,用户隐私的保护问题也日益凸显。对用户隐私的保护既是法律的要求,也是安全行业的追求。我们相信隐私保护技术会越来越受到重视,并从学术理论迅速投入工业界实战应用。

    展开全文
  • 拉普拉斯机制向隐私数据统计信息添加噪声实现差分隐私保护时,给定ε怎么通过噪声所服从的概率密度函数![图片说明](https://img-ask.csdn.net/upload/201604/21/1461219802_834301.png)得到具体的噪声值?
  • 基于拉普拉斯机制的差分隐私保护k-means 聚类算法研究.pdf
  • 差分隐私入门——拉普拉斯分布

    千次阅读 2019-03-22 23:11:39
    np.random.laplace可以获得拉普拉斯分布的随机值,参数主要如下: n p . r a n d o m . l a p l a c e 可 以 获 得 拉 普 拉 斯 布 的 随 机 值 , 参 数 主 要 如 下 : l o c : 就 是 上 面 的 μ , 控 制 ...

    L a p l a c e 分 布 的 概 率 密 度 函 数 : Laplace分布的概率密度函数: Laplace:
    p ( x ) = 1 2 λ e − ∣ x − μ ∣ λ , 一 般 取 μ = 0 , 函 数 形 式 如 : p(x)=\frac{1}{2\lambda}e^{-\frac{|x-\mu|}{\lambda}},一般取\mu=0,函数形式如: p(x)=2λ1eλxμμ=0
    p ( x ) = 1 2 λ e − ∣ x ∣ λ , 又 称 为 双 指 数 函 数 分 布 。 p(x)=\frac{1}{2\lambda}e^{-\frac{|x|}{\lambda}},又称为双指数函数分布。 p(x)=2λ1eλx
    标 准 L a p l a c e 分 布 的 均 值 为 0 , 方 差 为 2 λ 2 , 几 种 λ 下 其 概 率 分 布 图 如 下 : 标准Laplace分布的均值为0,方差为{2\lambda^2},几种\lambda下其概率分布图如下: Laplace02λ2λ
    在这里插入图片描述

    import matplotlib.pyplot as plt
    import numpy as np
    def laplace_function(x, lambda_):
        return (1/(2*lambda_)) * np.e**(-1*(np.abs(x)/lambda_))
    x = np.linspace(-5,5,10000)
    y1 = [laplace_function(x_,1) for x_ in x]
    y2 = [laplace_function(x_,2) for x_ in x]
    y3 = [laplace_function(x_,0.5) for x_ in x]
    
    plt.plot(x, y1, color='r', label="lambda:1")
    plt.plot(x, y2, color='g', label="lambda:2")
    plt.plot(x, y3, color='b', label="lambda:0.5")
    
    plt.title("Laplace distributions")
    plt.legend()
    plt.show()
    

    n p . r a n d o m . l a p l a c e 可 以 获 得 拉 普 拉 斯 分 布 的 随 机 值 , 参 数 主 要 如 下 : np.random.laplace可以获得拉普拉斯分布的随机值,参数主要如下: np.random.laplace
    l o c : 就 是 上 面 的 μ , 控 制 偏 移 。 loc:就是上面的\mu,控制偏移。 locμ
    s c a l e : 就 是 上 面 的 λ , 控 制 缩 放 。 scale: 就是上面的\lambda,控制缩放。 scaleλ
    s i z e : 是 产 生 数 据 的 个 数 。 size: 是产生数据的个数。 size
    p y t h o n 生 成 l a p l a c e 分 布 直 方 图 : python生成laplace分布直方图: pythonlaplace
    在这里插入图片描述

    import numpy as np
    #print(np.random.laplace(0,1,10)) 生成10个样本
    laplace1 = np.random.laplace(0, 1, 10000)
    laplace2 = np.random.laplace(0, 2, 10000)
    
    import matplotlib.pyplot as plt
    fig, (ax1, ax2) = plt.subplots(1,2, sharex=True, sharey=True)
    ax1.hist(laplace1,bins=1000, label="lambda:1")
    ax1.legend()
    
    ax2.hist(laplace2, bins=1000, label="lambda:2")
    ax2.legend()
    plt.show()
    
    展开全文
  • 差分隐私的定义如下: 给定一个兄弟数据集D和D’,他们两者之间至多相差一条数据。然后给定一个映射函数f:D→Rdf:D\rightarrow R^df:D→Rd。它表示的是数据集D到一个d维空间的映射关系。接着,我们在所得到的的函数f...

    差分隐私的定义如下:
    给定一个兄弟数据集DD’,他们两者之间至多相差一条数据。然后给定一个映射函数 f : D → R d f:D\rightarrow R^d f:DRd。它表示的是数据集D到一个d维空间的映射关系。接着,我们在所得到的的函数 f ( D ) = ( x 1 , x 2 , . . . , x d ) T f(D)=(x_1,x_2,...,x_d)^T f(D)=(x1,x2,...,xd)T上添加拉普拉斯噪声,得到一个输出函数A(D)
    那么有式1:
    A ( D ) = f ( D ) + ⟮ L a p 1 ( Δ f ε ) , L a p 1 ( Δ f ε ) , . . . , L a p d ( Δ f ε ) ⟯ T A(D)=f(D)+\lgroup Lap_1(\frac {\Delta f} \varepsilon ), Lap_1(\frac {\Delta f} \varepsilon ),...,Lap_d(\frac {\Delta f} \varepsilon )\rgroup ^T A(D)=f(D)+Lap1(εΔf),Lap1(εΔf),...,Lapd(εΔf)T
    其中 Δ f = D , D ′ m a x ∣ ∣ f ( D ) − f ( D ′ ) ∣ ∣ p {\Delta f}=\stackrel {max}{_D, _{D&#x27;}} ||f(D)-f(D&#x27;)||_p Δf=D,Dmaxf(D)f(D)p,其中p一般取1,为1-范数。

    1-范数: ∣ ∣ x ∣ ∣ 1 = ∑ i = 1 n ∣ x i ∣ ||x||_1=\sum_{i=1}^{n}|x_i| x1=i=1nxi ,即向量元素绝对值之和,matlab调用函数norm(x, 1) 。

    而算法A满足差分隐私定义的条件是(式2):
    P r [ A ( D ) = O ] ≤ e ε ∗ P r [ A ( D ′ ) = O ] P_r[A(D)=O]\leq e^{\varepsilon} * P_r[A(D&#x27;)=O] Pr[A(D)=O]eεPr[A(D)=O]
    式1中的 A(D) 满足式2
    证明见一位大佬的证明

    展开全文
  • java、python--差分隐私拉普拉斯分布(Laplace)实现

    万次阅读 热门讨论 2017-08-22 11:15:18
    最近在研究差分隐私,先用java实现了拉普拉斯分布,做了个Hive交互式接口。后来又用python画图,准备做个非交互式数据发布。 差分隐私的原理我先简单介绍一下,Apple 用它来实现信息安全。这里举一个例子来帮助理解...

    最近在研究差分隐私,先用java实现了拉普拉斯分布,做了个Hive交互式接口。后来又用python画图,准备做个非交互式数据发布。

    差分隐私的原理我先简单介绍一下,Apple 用它来实现信息安全。这里举一个例子来帮助理解,考虑一个医疗数据场景:


           上图显示了一个医疗数据集D,其中每条记录表示一个患者是否患有癌症,当数据集作为科研数据或者社会调研被发布出来时,他对用户提供前行的统计查询服务,这里选取计数查询,用count (n) 表示前行里有多少个人患有癌症。

           这里攻击者知道Jack 排在第3行(医疗数据记录一般按一定顺序排列,例如身份证号等),由于不能直接访问D(注意 D 仅提供 count (n) 查询服务), 一开始并不知道Jack 的第二列属性值是否为1,但是可以通过如下攻击获取Jack 的个人隐私信息(是否患有癌症):count (3) - count (2)

           那么差分隐私技术在该案例中是如何保证信息安全的呢?我们可以把删除掉Jack 一行的数据集(或修改)看成D',要求A 根据D 获取的count 值,与根据D' 获取的count 值的概率分布差不多,假设count (3) 的输出可能来自{1.5, 2},那么count (2) 以近似的概率输出{1.5, 2} 中的任意值,Laplace 机制便能实现此功能,具体证明这里就不说了都是复杂的数学公式。 ϵ-DP的 ϵ 值就是用来控制概率分布的相似性,当 ϵ 越小时,exp( ϵ ) 越接近于1。

           拉普拉斯分布图:

       


           废话不说上代码,java代码:

    import org.apache.commons.math3.distribution.LaplaceDistribution;
    double laplaceMechanismCount(long realCountResult, double epsilon) {
    LaplaceDistribution ld = new LaplaceDistribution(0, 1 / epsilon);
    double noise = ld.sample();
    return realCountResult + noise;
    }
    
          python代码:

    import numpy as np
    loc, scale = 0., 1.
    s = np.random.laplace(loc, scale, 1)
    ss=s[0]
    print ss
    其中epsilon和scale调节保护性的大小。


    展开全文
  • 差分隐私

    千次阅读 2019-02-08 21:51:09
    上一篇介绍了数据脱敏的三种基本方法,这里介绍另一种方法——差分隐私差分隐私的优点在于其不需要特殊的攻击假设,不关心攻击者拥有的背景知识,量化分析隐私泄露风险。 核心研究问题:在满足差分隐私的前提下...
  • 启动Reduce分任务合并满足更新要求的分目标更新模型,并加入拉普拉斯随机噪声实现差分隐私保护。根据差分隐私保护原理,证明了算法满足ε-差分隐私保护要求。实验表明该算法具有明显的效率优势并有较好的数据可用性...
  • 针对现有轨迹差分隐私保护发布方法面临的独立噪声容易被滤除的问题,提出一种轨迹差分隐私发布方法——CLM。CLM 提出一种相关性拉普拉斯机制,利用高斯噪声通过特定的滤波器,产生与原始轨迹序列自相关函数一致的...
  • 中心化差分隐私与本地化差分隐私

    千次阅读 2018-12-26 22:01:22
    中心化差分隐私和本地差分隐私 定义区别:在中心化差分隐私保护技术中,算法膨的隐私性通过近邻数据集来定义,因此其要求一个可信的第三方数据收 集者来对数据分析结果进行隐私化处理.对于本地化差分隐私技术而...
  • 已有的基于差分隐私的直方图发布技术在利用直方图反映数据的真实分布特征时可能会出现“重拖尾”和“零桶”现象,并且在数据量较多处“过于平缓”;另外,已有技术对原始直方图进行差分隐私保护时未考虑每个分组所...
  • 在所提出的满足差分隐私的数据分级发布机制中,数据发布方利用隐私预算参数不同的拉普拉斯机制对数据查询结果进行隐私保护处理,实现了输出隐私保护程度不同的查询结果。在依据付费或权限对查询用户分级后,数据发布...
  • 根据发布数据集安全性和可用性的个性化需求, 个性化设置差分隐私预算分配比值常数$q$值, 实现对按敏感性排序的低维属性集合个性化分配拉普拉斯噪音. 理论分析和实验结果表明, PPBA算法相比较于同类算法能够满足高维...
  • 差分隐私(Differential privacy)浅析

    万次阅读 多人点赞 2019-09-05 08:56:23
    通过几天对差分隐私的左思右想,总算是摸到了点门道,顺着学习思路,就一些比较关键性概念说一下自己的看法: 一、关键性概念 1、查询 对数据集的各种映射函数被定义为查询(Query),用 ={, , ......}来表示一...
  • 本地化差分隐私(Local Differential Privacy)浅析

    万次阅读 多人点赞 2019-09-12 08:06:50
    传统的差分隐私是将原始数据集中到一个数据中心,然后在此对数据施加差分隐私算法,并对外发布,称之为中心化差分隐私(Centralized Differential Privacy)。因此,中心化差分隐私有一个前提:可信的第三方数据...
  • 首先构建多级查询树(位置搜索树),然后遍历查询树,使用差分隐私的指数机制来选取访问频率高的k项,最后通过拉普拉斯机制给选取的k项进行加噪。实验表明,相比于其他保护策略,基于差分隐私机制的位置数据隐私保护...
  • MindArmour差分隐私

    2021-01-23 09:10:05
    MindArmour差分隐私 总体设计 MindArmour的Differential-Privacy模块,实现了差分隐私训练的...图1是差分隐私训练的总体设计,主要由差分隐私噪声机制(DP Mechanisms)、差分隐私优化器(DP Optimizer)、差分隐私监控器
  • 今天小编就为大家分享一篇python实现差分隐私Laplace机制详解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 提出一种基于随机森林的差分隐私保护算法DiffPRFs,在每一棵决策树的构建过程中采用指数机制选择分裂点和分裂属性,并根据拉普拉斯机制添加噪声。在整个算法过程中满足差分隐私保护需求,相对于已有算法,该方法无需...
  • 差分隐私简介

    千次阅读 2018-01-03 18:48:02
    差分隐私可以通过向聚合查询结果添加随机化"噪声"来实现,以保护个人的条目,而不会显著改变查询结果。 差分隐私算法保证攻击者能获取的个人数据几乎和他们从没有这个人记录的数据集中能获取的相差无几。 最简单的...
  • 为提高隐私保护程度,对匿名化划分的数据添加拉普拉斯噪声,扰动个体数据真实值,以实现差分隐私保护模型的要求。通过聚类,分化查询函数敏感性,提高数据可用性。对算法隐私性进行证明,并实验说明发布数据的可用性...
  • 该算法首先将数据完全泛化,然后在给定的隐私保护预算下采用指数机制将数据逐步精确化,最后根据拉普拉斯机制向数据中加入噪声,保证整个算法过程满足差分隐私保护要求;对指数机制中方案选择的方法进行了有效的改进...
  • 差分隐私保护

    千次阅读 2020-03-26 16:17:27
    差分隐私(Differential Privacy)是密码学中的一种手段,旨在提供一种当从统计数据库查询时,最大化数据查询的准确性,同时最大限度减少识别其记录的机会。简单地说,就是在保留统计学特征的前提下去除个体特征以...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 198
精华内容 79
关键字:

拉普拉斯差分隐私