隐私的总结 第1篇
推进无监督学习下的隐私保护研究
权衡差分隐私保护的模型可用性与隐私性
探索多种技术结合的保护方法 （差分隐私、加密方法、区块链 各有优缺）
支持单点和全局隐私保护
开发机器学习隐私保护框架（目前是针对特定的攻击，需要通用的）
研究训练阶段基于密文的高效机器学习隐私保护方法
目前的方法多用于预测阶段，因为同态加密生成的密文大、复杂随着运算次数增多深度增加，一旦超过阈值将得不到正确结果。另一方面，深度学习本身运算量大，没有加密也需要高吞吐量的计算单元。
设计适用于机器学习各个阶段的通用隐私保护体系结构
提出针对半结构化、非结构化数据隐私的切实可行解决方案
现有的隐私保护几乎都是针对结构化 数据的，而大数据很多都是非结构化。
总结
机器学习不可分割，隐私泄露巨大威胁。
在数据隐私性、高效性、可用性的矛盾下，如何提供符合给定场景隐私保护方法，最小化隐私泄露风险，将是个长期挑战。
隐私的总结 第2篇
根据隐私感知得到的隐私数据及其标记，选用相应的隐私保护方法，包括密码学方法、信息隐藏方法和数据处理方法。
密码学方法：主要是研究构造适用于隐私保护、与传统数据加解密不同的密钥管理机制、同态密码方案以及混淆方法等；
信息隐藏/隐写的方法：则可以用来保护元数据，将元数据以变化的形态来传输，对应的还原控制参数应该与信息本身分割存储和传输；
数据处理方法：则是去除不同隐私数据间的关联性、添加数据扰动、通过数据匿名化实现隐私保护（如k-匿名，l-多样性，t-邻近性等），防止聚类分析、众包计算、深度学习等大数据分析。
1) 数据扰动
静态数据发布的匿名模型（如k-匿名）
动态数据发布的隐私模型（如差分隐私）
2) 基于密码学的隐私保护
数据加密：同态加密、安全多方计算
3) 数据隐藏
数字水印
4) 数据使用
身份认证、访问控制、安全审计等
1) 数据匿名化技术
在数据发布时根据某些限制不发布数据的某些域值，方法有泛化、隐匿、交换等，其中，泛化和隐匿最为常用。应用：数据脱敏，数据发布。
泛化：用更一般的值或者模糊的值取代原始属性值，但语义上与原始值保持一致
隐匿：用最一般化的值取代原始属性值，可视为是最高级别的泛化。
匿名化模型：k-匿名、l-多样性、 t-Closeness、个性化匿名、动态数据匿名化。
2) 差分隐私
保证任意一个体在数据集中或者不在数据集中时，对最终发布的查询结果几乎没有影响．具体地说，设有两个几乎完全相同的数据集（两者的区别仅在于一个记录不同），分别对这两个数据集进行查询访问，同一查询在两个数据集上产生同一结果的概率的比值接近于1．
差分隐私保护可以通过在查询函数的返回值中加入适量的干扰噪声来实现，常用的技术为xxx斯机制、指数机制。
3) 同态加密
同态加密，能够在不解密的情况下对密文数据进行计算，使得对该密文的明文执行了相应的计算。解决了密文域的安全计算问题。
根据密文计算能力的不同，可以分类为单同态加密、类同态加密、全同态加密。
4) 安全多方计算
解决一组互不信任的参与方之间保护隐私的协同计算问题，SMC要确保输入的独立性、计算的正确性、去中心化等特征，同时不泄露各输入值给参与计算的其他成员。
主要是针对无可信第三方的情况下，如何安全地计算一个约定函数的问题，同时要求每个参与主体除了计算结果外不能得到其他实体任何的输入信息。
5) 数字水印
将一些标识信息（即数字水印）直接嵌入数字载体（包括多媒体、文档、软件等）当中，但不影响原载体的使用价值，也不容易被人的知觉系统（如视觉或者听觉系统）觉察或注意到。包括图像水印、音频水印、视频水印、文本水印。
应用：版权保护、数字指纹、认证和完整性校验、内容标识和隐藏标识、内容保护、隐蔽通信。
6) 身份认证
分类：
1）根据客观的认证条件，分为双因子与单因子两种不同的认证方式；
2）借助于认证信息的分类，可以分为动态的和静态的认证；
3）从运用硬件还是软件角度，分为软件与硬件两种不同的认证。
身份认证方式：
1）生物特征认证，缺乏准确性和稳定性、成本高；
2）用户名和密码，静态密码、密码容易暴露；
3）USB Key认证，客户端的缺陷、冲击-响应认证不能进行双向认证；
4）动态口令/动态密码，单密钥、成本高。
隐私的总结 第3篇
信息缺损表示为，经过隐私保护技术处理后数据的信息丢失，是针对发布数据集质量的一种度量。最小信息缺损原则，通过比较原始数据和匿名数据的相似度来衡量隐私保护的效果。信息缺损越小，说明发布数据集的有效性越高。但是，这种度量原则需要考虑准标志符巾每个属性的每个取值的泛化和隐匿带来的信息缺损，计算代价较高，适用于对单个属性进行度量。
ILoss[7]度量标准，要求检查每条记录准标志xxx每个属性的取值泛化带来的信息缺损，进而计算出每条记录泛化后的信息缺损，再根据每条记录的信息缺损，计算整个发布数据集的信息缺损。
因此出现了如下几种数据隐私发布手段：
1、基于数据失真
据失真技术，那通过扰动原始数据来实现隐私保护。数据扰动的基本思想是隐藏真实的原始数据，只呈现出数据的统计学特征，具体地讲，经过扰动之后，攻击者通过发布的失真数据，不能重构出真实的原始数据，即不能发现真实的原始数据。并且．失真后的数据仍然保持某些性质不变，即利用失真数据得出的某些信息等同于从原始数据上得出的信息。
数据交换足一种基本的扰动技术，足在记录之间交换数据的值，保留某些统计学特征而不保留真实数值。另外一种技术是随机化，是对原始数据加入随机噪声从而隐藏真实数值。值得注意的是，任意对数据进行随机化，并不能保证数据和隐私的安全竭]，因为利用概率模型进行分析，可能揭露随机化过程中的众多性质。
2、基于数据加密
基于数据加密的隐私保护技术，多用于分布式应用中，是通过密码机制实现他方对原始数据的不可见性以及数据的无损失性，以实现隐私保护。
如安全多方计算
3、基于限制发布
所谓限制发布，是指不发布或者发布敏感度较低的数据，即有选择地发布原始数据，以实现隐私保护。限制发布在隐私披露风险与数据敏感度之间进行折中，即保证隐私披露风险在一定阚值范围之内，有选择地发布敏感数据。当前此类技术的研究热点，集中于数据匿名化。数据匿名化一般采用两种基本操作，一种是抑制，即不发布某些数据项；另一种是泛化，即对数据进行更概括、抽象的描述。数据匿名化的研究重点，主要是设计更好的匿名化原购，使发布数据既能很好地保护隐私，又具有较大的使用价值。同时，针对特定的匿名化原则，设计更为高效的匿名化算法。
如K-匿名技术
但是以上的几种隐私保护手段都具有相当大的局限性：
第一：对攻击者的能力具有限制
第二：没有严格的数学框架体系证明
第三：数据可用性和隐私保护程度关系难以平衡
因此2006年，提出了差分隐私。差分隐私保护采用添加噪声的技术使敏感数据失真，是基于数据失真的隐私保护技术。虽然其基于数据失真技术，但所需加入韵噪声量与数据集的大小无关。因此，即使对于大型数据集，也只需添加极少量的噪声，就可以达到高级别的隐私保护。此外，差分隐私保护定义了一个极为严格的攻击模型[2“，并对隐私披露风险给出了定量化的表示和证明。差分隐私保护可以保证，在数据集中删除或添加一条数据，不会影响到查询结果。因此，即使在最坏情况下，攻击者已知除某条记录之外的所有敏感数据，仍然可以保证不泄露这条记录的敏感信息。差分隐私保护极大地保证了数据的可用性，同时大大降低了隐私泄露的风险
差分隐私（Differential Privacy）的差分体现于何处呢？究竟何又为差分呢？
我们试想一下这样的一个例子：
我们有一个记录了某个社区的艾滋病病人的数据库，为了保证这些人的个人信息，我们对数据库的查询作出了限定，即每次的查询都必须要是统计查询且得到的信息的条目数量必须大于N，保证个人的信息不会被直接查询到。
但是在这种情况下我们可以通过差分攻击的手段来得到某一个人的具体信息：
由此通过这种差分攻击的手段我们可以查询到某个人的具体信息，造成了隐私泄露问题
所以差分隐私也就应运而生，这项技术要解决的也正是这类问题。在差分隐私的保护下，任何单条记录在数据库中的有无不影响算法的输出结果，所以也就能实现个人隐私的保护。
差分隐私依据数据收集分析发放中保护的对象不一样可以分为两种差分隐私类型：中心化差分隐私和本地化差分隐私。
一般的数据收集分析；流程如下：
数据收集：各个用户将自身的数据上传到第三方
数据分析：第三方利用所收集到的数据进行数据分析
结果发布：第三方将数据分析结果公开发布
即如图，依据隐私保护的目的和第三方是否可信可以将差分隐私分为中心化差分隐私和本地化差分隐私：
中心化差分隐私：认为第三方是可信的，因此主要保护的是数据收集分析后的结果发放过程，差分隐私保护机制运行在可信第三方上。
本地化差分隐私：认为第三方是不可信的，所以本地差分隐私保护的是用户上传数据到第三方的过程，差分隐私机制运行在各个用户的本地。
、中心化差分隐私：
首先我们要明白两个相邻数据集的概念，在这里 D D D和 D ’ D’ D’具有相同的属性结构，在有界的DP(Differential Privacy)中，相邻数据集是可以通过xxx一项数据得到的，而对于无界的DP，相邻数据集则是通过增加或者加减一项数据得到，即后者中的数据集大小有差别。由于减掉一项元素再加一项元素等价于替换一项元素，因此在这里我们只讨论无界的DP情况。
一个算法 A A A应用于数据集 D D D上会得到一个结果 t t t，即 A ( D ) = t A(D) = t A(D)=t，同样把该算法运用于D的邻近数据集 D ‘ D‘ D‘上得到 t ′ t' t′，即 A ( D ′ ) = t ′ A(D') =t' A(D′)=t′，倘若没有对这两项运算进行一定的处理，那么结果就可能出现由 t ′ − t t'-t t′−t透露出 D ′ − D D'-D D′−D的信息问题。因此我们差分隐私的主要思想就是对算法得到的结果进行混淆，使得对于临近数据集，我们得到相同结果即 t ′ − t = 0 t'-t=0 t′−t=0的概率保持在一定范围内，这样就可以在一定程度上抵御差分攻击。
ϵ − \epsilon- ϵ−差分隐私的数学定义如下：
这两个输出同样结果的概率的相差幅度不能太大，这样而这个幅度就由 ϵ \epsilon ϵ进行调控，其中 ϵ > 0 \epsilon>0 ϵ>0我们称为隐私预算，当 ϵ = 0 \epsilon = 0 ϵ=0的时候此时隐私保护能力最强，即 P r ( A ( D ) = t ) = P r ( A ( D ′ ) = t ) Pr(A(D)=t)= Pr(A(D')=t) Pr(A(D)=t)=Pr(A(D′)=t)，但是此时由于输出相同结果的概率一致，原来的数据分布被破坏，导致数据的可用性很差。所以一般在实际的情况中，我们会提高隐私预算 ϵ \epsilon ϵ使得既能保证数据的可用性又能达到差分隐私保护。
根据差分隐私的数学定义可以推导出以下的性质定理：
1、后加工不变性（Posting-processing）：
若 A 1 ( ∗ ) A_1(*) A1(∗)满足 ϵ − D P \epsilon-DP ϵ−DP，则对于任意复合函数 A 2 ( ∗ ) A_2(*) A2(∗)也有， A 2 ( A 1 ( ∗ ) ) A_2(A_1(*)) A2(A1(∗))也满足 ϵ − D P \epsilon-DP ϵ−DP
2、串行合成性（Sequential composition）：
对于 A 1 ( D ) A_1(D) A1(D)满足 ϵ 1 − D P \epsilon_1-DP ϵ1−DP， A 2 ( s , D ) A_2(s,D) A2(s,D)满足 ϵ 2 − D P \epsilon_2-DP ϵ2−DP则有， A 2 ( A 1 ( D ) ， D ) A_2(A_1(D)，D) A2(A1(D)，D)满足 ( ϵ 1 + ϵ 2 ) − D P (\epsilon_1+\epsilon_2)-DP (ϵ1+ϵ2)−DP
而该串行合成性可以扩展到多个算法复合，对一系列满足 ε 1 ε_1 ε1- differential privacy， ε 2 − ε_2- ε2− differential privacy， ……， ε k ε_k εk- differential privacy 的 k 个算法，若将这 k k k 个算法顺序施加到一个数据集 D D D 上， 则合成后的算法满足 ( ε 1 + ε 2 + … … + ε k ) (ε_1+ε_2+……+ε_k) (ε1+ε2+……+εk)- differential privacy
3、并行合成性（Parallel Composition）：
若将数据集 D D D 划分为 $k 个 不 相 交 的 xxx 集 个不相交的子集 个不相交的子集D_1,D_2,……,D_K$ 并对每个子集施加满足$ε_1,ε_2,……,ε_k $的差分隐私算法，则合成后的总数据集满足 m a x ( ε 1 , ε 2 , … … , ε k ) max(ε_1,ε_2,……,ε_k) max(ε1,ε2,……,εk)-differential privacy。
值得注意的是，并行合成原理仅对无界差分隐私(Unbounded DP)生效，对有界差分隐私(Bounded DP)无效。
平行合成定理和随机划分函数：
4、凸性(Convexity)
若将一个满足 ε- differential privacy 的算法以 p1 的概率施加到数据集 D 上，将另一个满足 ε- differential privacy 的算法以 p2 的概率施加到同一个数据集 D 上，如此类推直至将第 k 个同样满足 ε- differential privacy的算法以 pk 的概率施加到数据集 D 上，且 p1+p2+……+pk=1，则这个合成的算法满足 ε- differential privacy。
本地化差分隐私下的保护模型充分考虑了数据采集过程中数据收集者窃取或泄露用户隐私的可能性．该模型中，每个用户首先对数据进行隐私化处理，再将处理后的数据发送给数据收集者，数据收集者对采集到的数据进行统计，以得到有效的分析结果．即，在对数据进行统计分析的同时，保证个体的隐私信息不被泄露．本地化差分隐私的形式化定义如下：
从定义1中可以看出，本地化差分隐私技术通过控制任意两条记录的输出结果的相似性，从而确保算法M满足争本地化差分隐私．简言之，根据隐私算法M的某个输出结果，几乎无法推理出其输入数据为哪一条记录．在中心化差分隐私保护技术中，算法的隐私性通过近邻数据集来定义，因此其要求一个可信的第三方数据收集者来对数据分析结果进行隐私化处理．对于本地化差分隐私技术而言，每个用户能够独立地对个体数据进行处理，即，隐私化处理过程从数据收集方转移到单个用户端上，因此不再需要可信第三方的介入，同时也xxx不可信第三方数据收集者可能带来的隐私攻击。本地差分隐私的定义从理论的角度保证了算法满足}本地化差分隐私，而实现 ϵ − \epsilon- ϵ− 本地化差分隐私保护需要数据扰动机制的介入。
主要的扰动机制是随机响应技术，我们将在后面详细介绍。
1、组合性质
差分隐私技术具有序列组合性和并行组合性两种特性【271，序列组合性强调隐私预算诃以在方法的不同步骤进行分配，而并行组合性则是保证满足差分隐私的算法在其数据集的不相交子集上的隐私性．从定义上来看，中心化差分隐私定义在近邻数据集上，本地化差分隐私则是定义在其中的两条记录上，而隐私保证的形式并未发生变化，因此本地化差分隐私将上述两种组合特性继承下来。
2、噪声机制
在中心化差分隐私保护技术中，为保证所设计的算法满足争差分隐私，需要噪声机制的介入，xxx斯机制和指数机制是其最常用的两种噪声机制，其中，xxx斯机制面向连续型数据的查询，而指数机制面向离散型数据的查询．上述两种噪声机制均与查询函数的全局敏感性【28】密切相关，而全局敏感性则是定义在至多差一条记录的近邻数据集之上，使得攻击者无法根据统计结果推测个体记录，即将个体记录隐藏在统计结果之中．在本地化差分隐私中，每个用户将各自的数据进行扰动后，再上传至数据收集者处，而任意两个用户之间并不知晓对方的数据记录，亦即，本地化差分隐私中并不存在全局敏感性的概念，因此，xxx斯机制和指数机制并不适用．目前，本地化差分隐私主要采用第1．2节中所述的随机响应技术来确保隐私算法满足争本地化差分隐私。
3、应用场景
中心化差分隐私保护技术的研究主要集中在数据发布、数据分析[34,35]和查询处理等方面，近年来取得了突出的研究进展，然而，其数据的隐私化处理过程始终依靠一个可信的第三方数据收集者来完成．某种程度上来说，这一点也限制了差分隐私技术的发展，在隐私意识不断增强的背景下，如何保证数据收集者不会从中窃取用户的隐私信息将是一个重要的考量．基于此，本地化差分隐私技术应运而生，进一步细化了对个人隐私信息的保护，其摒弃了可信第三方数据收集者的假设，将数据的隐私化处理过程转移到每个用户上，这样不仅能够对敏感信息进行更加彻底的保护，而且隐私化处理过程更加简洁、明了．此外，由于每个用户能够掌握个人的敏感信息处理过程，这也使得用户可以根据自身需求，进行更加个性化的隐私设置．中心化差分隐私技术通过定义全局敏感性为查询结果添加响应噪声，再以统计的方式限制隐私信息泄露的量化边界，从而能将个体记录隐藏在统计结果中．因此，中心化差分隐私技术并不对统计数据量作特别要求．不同于此，本地化差分隐私技术对个体数据进行正向和负向的扰动，最终通过聚合大量的扰动结果来抵消添加在其中的正负向噪声，从而得到有效的统计结果．然而，由于噪声的随机性，要保证统计结果的无偏性，必然需要海量的数据集来实现满足数据可用性的统计精度。
Pure-DP 是一种严格的差分隐私定义如下：
但是考虑到低概率条件下的概率比值问题，所以研究者新定义了一种较为宽松的差分隐私，即 ( ϵ , δ ) − D P (\epsilon,\delta)-DP (ϵ,δ)−DP，其中纯粹差分隐私又可以看作是近似差分隐私的特例。
两者的主要区别如下：
在描述具体机制的实现方法之前，我们需要定义“敏感度(sensitivity)”的概念。敏感度是用来控制噪声大小的参数，敏感度越大，为了维持输出结果相似所需要添加的噪声量就越大。
最常使用的敏感度主要有三种，为全局敏感度、局部敏感度和平滑敏感度。
从全局敏感度的定义可以看出，全局敏感度是在整个 universeΧ 上所有可能的 D 和其相邻数据集 D’上找到的 f(D)与 f(D’)之间曼哈顿距离，因此全局敏感度只和查询函数 f 相关，反应的是一个查询函数在一对相邻数据集查询时最大的变化程度。像常见的 count 查询函数，其全局敏感度就是 1，因为无论怎样选择数据集，相差一个元素的相邻数据集对计数查询最大的变化量就是 1。但像mean(众数)， median(中位数)等函数，其全局敏感度可能会非常大，导致添加的噪声也非常大，此时我们就需要“局部敏感度”和“平滑敏感度”来代入计算。
局部敏感度的定义与全局敏感度非常相似，唯一的区别在于局部敏感度只在全部 D’中寻找最大值，这就是说局部敏感度是在确定了数据集 D 的前提下定义的，全局敏感度是全部局部敏感度的最大值。
因此也就是说局部敏感度是随着数据集D变化而变化的，因此应用范围受限并且由于局部敏感度的剧烈变化，因此会透露出数据集D的信息，所以研究人员定义了了平滑上界和平滑敏感度 ，试图加强局部敏感度的隐私保护能力。
为定义平滑敏感度，我们要先定义局部敏感度的“平滑上界”， 平滑上界是 一个通过超参数β定义的函数 S(x)：
在了解了查询函数 f 的平滑上界后，我们可以定义数据集 D 和查询函数 f f f 所对应的平滑敏感度：
平滑敏感度就是满足上述平滑上界定义的最小函数，平滑敏感度和局部敏感度相比可以更好地保护用户的隐私安全，但计算平滑敏感度有时是困难的，在一定条件下，平滑敏感度的计算会达到 NP-困难， Nissim 等人在他们提出平滑敏感度的论文_Smooth sensitivity and sampling in private data analysis._中给出了一个名为 Sample-Aggregate framework 的框架来解决这个问题。
这三者关系可以使用该图进行表示：
为了保证对于临近数据集我们的算法给出相同答案的概率一致，我们首先想到的是给我们的结果加一一个噪声来进行掩盖和混淆。即我们的输出 f ′ ( D ) = f ( D ) + X f'(D) = f(D)+X f′(D)=f(D)+X 其中 X X X是我们需要添加的噪音，下面我们通过分析来推导：
首先添加噪声后的结果应该满足： P r ( f ′ ( D ) = t ) P r ( f ′ ( D ′ ) = t ) = f ( D ) + X = t f ( D ′ ) + X = t = X = t − f ( D ) X = t − f ( D ′ ) < = e ϵ \dfrac{Pr(f'(D) =t)}{Pr(f'(D')=t)}=\dfrac{f(D)+X =t}{f(D')+X =t}=\dfrac{X= t-f(D)}{X=t-f(D')}<= e^{\epsilon} Pr(f′(D′)=t)Pr(f′(D)=t)=f(D′)+X=tf(D)+X=t=X=t−f(D′)X=t−f(D)<=eϵ 自然地，我们令 d = f ( D ) − f ( D ′ ) d = f(D)-f(D') d=f(D)−f(D′)，即要保证：
X = x P r ( X = x + d ) < = e ϵ \dfrac{X = x}{ Pr(X = x+d)}<= e^{\epsilon} Pr(X=x+d)X=x<=eϵ对任一 x x x 均要成立
因此我们可以看到我们要选择的噪声 X X X的分布应该需要和 d = f ( D ) − f ( D ′ ) d=f(D) -f(D') d=f(D)−f(D′)有关，因此首先我们要考虑 d d d。因此下面我们考虑全局敏感度和局部敏感度的定义。
全局敏感度$\Delta f = max |f(D) - f(D’)| $
这样我们就可以保证了d是必须满足 d < = Δ f d<=\Delta f d<=Δf的。
因此我们可以进一步分析，当我们取噪声的分布为 L a p l a c e ( Δ f ϵ ) Laplace(\dfrac{\Delta f}{\epsilon}) Laplace(ϵΔf)时，此时概率密度分布函数为 P r ( L a p ( β ) = x ) = 1 2 β e − ∣ x ∣ / β Pr(Lap(\beta)=x) = \dfrac{1}{2\beta}e^{-|x|/\beta} Pr(Lap(β)=x)=2β1e−∣x∣/β。因此有 β = Δ f / ϵ \beta = \Delta f/\epsilon β=Δf/ϵ P r [ L a p ( β ) = x ] P r [ L a p ( β ) = x + d ] < = e d / β < = e Δ f / β = e ϵ \dfrac{Pr[Lap(\beta)=x]}{Pr[Lap(\beta)=x+d]}<=e^{d/\beta}<=e^{\Delta f/\beta} = e^{{\epsilon}} Pr[Lap(β)=x+d]Pr[Lap(β)=x]<=ed/β<=eΔf/β=eϵ 因此我们得到了差分隐私的Laplace机制：
对于任一函数 f f f，xxx斯机制 A f ( D ) = f ( D ) + L a p ( Δ f / β ) A_f(D)=f(D)+Lap(\Delta f/\beta) Af(D)=f(D)+Lap(Δf/β)满足 ϵ − D P \epsilon-DP ϵ−DP
其中xxx斯分布为：
若 μ=0，则称 x 满足 Lap(b)，其具体图像为：
这种情况往往适合用于查询数值的例子，例如计数查询等。
对 Laplace 机制定义稍加变形，我们就能获得 Laplace 机制的一个特例——高 斯分布。xxx分布的敏感度采用 L2 间距(欧氏距离)， 添加的噪声为独立同分布的 随机xxx噪声。其具体定义为：
相比于上述机制中使用的第一范式敏感度，在这里我们使用第二范式敏感度： Δ 2 f = m a x D , D ′ ∣ ∣ f ( D ) − f ( D ′ ) ∣ ∣ 2 \Delta_2f = max_{D,D'}||f(D)-f(D')||_2 Δ2f=maxD,D′∣∣f(D)−f(D′)∣∣2 该机制使用的xxx函数 N ( 0 , σ 2 ) N(0,\sigma^2) N(0,σ2)是均值为0，其方差为 σ 2 \sigma^2 σ2，其中 σ = Δ 2 f 2 l n ( 2 / δ ) \sigma= \Delta_2f \sqrt{2ln(2/\delta)} σ=Δ2f2ln(2/δ)，则有该机制M：
M ( D ) = f ( D ) + N ( 0 , σ 2 ) M(D) = f(D)+N(0,\sigma^2) M(D)=f(D)+N(0,σ2)满足 ϵ , δ \epsilon,\delta ϵ,δ差分隐私
###、指数机制
对于数值型查询我们可以很好的利用xxx斯机制来进行差分隐私保护，但是对于非数值型，xxx斯机制的加数值噪声的机制便显得无能为力起来了。因此，我们考虑了指数机制，其一般适用于这种情况，我们要找出数据库中出现次数最多物品，这个时候由于查询结果不是数值，因此加噪声是不可以的。
但是同样可以考虑混淆查询的结果，假设数据库中出现次数最多的前几位为 T 1 , T 2 , T 3 . . . . T_1,T_2,T_3.... T1,T2,T3....，为了保证我们的查询具有差分隐私保护，我们可以考虑对于输出结果给予一定的概率分布，得到结果 T 1 ， T 2 ， T 3 . . . . . T_1，T_2，T_3..... T1，T2，T3.....的概率依次递减，从而使得查询并不会每次出现精确的结果，但是又保证了数据的可用性。
下面我们进行更加精确的数学推导和定义：
我们需要发布数据 f ( D ) f(D) f(D)， O O O是我们所有可能的输出的集合。为了要满足 ϵ − D P \epsilon-DP ϵ−DP，我们必须要按照一定的概率分布来发布 O O O中的值， q ( D , o ) q(D,o) q(D,o)定义为D中项目 o o o出现的次数。
指数机制：
首先定义全局敏感度： Δ q = m a x ∀ o , D ≃ D ′ ∣ q ( D , o ) − q ( D ′ , o ) ∣ \Delta q = max_{\forall o,D \simeq D'}|q(D,o)-q(D',o)| Δq=max∀o,D≃D′∣q(D,o)−q(D′,o)∣，和之前的xxx斯机制一样，有了全局敏感度之后我们就可以依此调整我们的隐私预算 ϵ \epsilon ϵ。
我们的差分隐私输出结果： P r [ M q ϵ ( D ) = o ] = e x p ( ϵ q ( D , o ) / 2 Δ q ) Σ o ′ ∈ O e x p ( ϵ q ( D , o ′ ) / 2 Δ q ) Pr[M^{\epsilon}_q(D)=o] = \dfrac{exp(\epsilon q(D,o)/2\Delta q)}{\Sigma_{o'\in O }exp(\epsilon q(D,o')/2\Delta q)} Pr[Mqϵ(D)=o]=Σo′∈Oexp(ϵq(D,o′)/2Δq)exp(ϵq(D,o)/2Δq)
同时有： e x p ( ϵ q ( D , o ) 2 Δ q ) e x p ( ϵ q ( D ′ , o ) 2 Δ q ) = e x p ( ϵ ( q ( D , o ) − q ( D ′ , o ) ) 2 Δ q ) < = e x p ( ϵ / 2 ) \dfrac{exp(\dfrac{\epsilon q(D,o)}{2\Delta q})}{exp(\dfrac{\epsilon q(D',o)}{2\Delta q})} = exp(\dfrac{\epsilon(q(D,o)-q(D',o))}{2\Delta q})<= exp(\epsilon/2) exp(2Δqϵq(D′,o))exp(2Δqϵq(D,o))=exp(2Δqϵ(q(D,o)−q(D′,o)))<=exp(ϵ/2)
所以下面我们证明该机制满足 ϵ − D P \epsilon- DP ϵ−DP： P r [ M q ϵ ( D ) = o ] P r [ M q ϵ ( D ′ ) = o ] = e x p ( ϵ q ( D , o ) / 2 Δ q Σ o ′ ∈ O e x p ( ϵ q ( D , o ′ ) / 2 Δ q ) e x p ( ϵ q ( D ′ , o ) / 2 Δ q ) Σ o ′ ∈ O e x p ( ϵ q ( D ′ , o ′ ) / 2 Δ q ) = . . . . < = e x p ( ϵ ) \dfrac{Pr[M^{\epsilon}_q(D)=o]}{Pr[M^{\epsilon}_q(D')=o]} =\dfrac{\dfrac{exp(\epsilon q(D,o)/2\Delta q}{\Sigma_{o'\in O }exp(\epsilon q(D,o')/2\Delta q)}}{\dfrac{exp(\epsilon q(D',o)/2\Delta q)}{\Sigma_{o'\in O }exp(\epsilon q(D',o')/2\Delta q)}} = ....<= exp(\epsilon) Pr[Mqϵ(D′)=o]Pr[Mqϵ(D)=o]=Σo′∈Oexp(ϵq(D′,o′)/2Δq)exp(ϵq(D′,o)/2Δq)Σo′∈Oexp(ϵq(D,o′)/2Δq)exp(ϵq(D,o)/2Δq=....<=exp(ϵ) 单调性的指数机制推导：
当 ∀ o ∈ O , q ( D , o ) > = q ( D ′ , o ) \forall o \in O, q(D,o)>=q(D',o) ∀o∈O,q(D,o)>=q(D′,o)或者 ∀ o ∈ O , q ( D , o ) < = q ( D ′ , o ) \forall o \in O, q(D,o)<=q(D',o) ∀o∈O,q(D,o)<=q(D′,o)成立时，此时概率函数可以取为 e x p ( ϵ q ( D , t ) Δ q ) exp(\dfrac{\epsilon q(D,t)}{\Delta q}) exp(Δqϵq(D,t))，此时仍然满足 ϵ − D P \epsilon-DP ϵ−DP，而且此时我们数据的可用性进一步加强，可以看到，选择精确的结果的概率要变得更高（如果之前选择的概率比为10:1，现在将变为100:1）
证明如下：假设单调性为 ∀ o ∈ O , q ( D , o ) < = q ( D ′ , o ) \forall o \in O, q(D,o)<=q(D',o) ∀o∈O,q(D,o)<=q(D′,o)，则有：
e x p ( ϵ q ( D , o ′ ) / Δ q ) < = e x p ( ϵ q ( D ′ , o ′ ) ) exp(\epsilon q(D,o')/\Delta q)<=exp(\epsilon q(D',o')) exp(ϵq(D,o′)/Δq)<=exp(ϵq(D′,o′))
同时依据前式有
e x p ( ϵ q ( D ′ , o ′ ) Δ q ) < = e x p ( ϵ ) e x p ( ϵ q ( D , o ′ ) Δ q ) exp(\dfrac{\epsilon q(D',o')}{\Delta q})<= exp(\epsilon)exp(\dfrac{\epsilon q(D,o')}{\Delta q}) exp(Δqϵq(D′,o′))<=exp(ϵ)exp(Δqϵq(D,o′))
因此：
。。。
综上有 e x p ( − ϵ ) < = P r [ M q ϵ ( D ) = o ] P r [ M q ϵ ( D ′ ) = o ] < = e x p ( ϵ ) exp(-\epsilon)<=\dfrac {Pr[M^{\epsilon}_q(D)= o]}{Pr[M^{\epsilon}_q(D')=o]}<= exp(\epsilon) exp(−ϵ)<=Pr[Mqϵ(D′)=o]Pr[Mqϵ(D)=o]<=exp(ϵ)