摘要：基本思想上图给出了差分隐私的一般性方法。定义一给出了差分隐私的数学表达。从定义可以看出差分隐私技术限制了任意一条记录对算法输出结果的影响。而基于不同噪音机制且满足差分隐私的算法所需噪音大小与全局敏感性密切相关。
1. 苹果、微软、谷歌与差分隐私的爱恨纠葛
在2016 年6 月份的苹果 WWDC 大会上苹果公司负责软件工程的高级副总裁克雷格•费德里希(Craig Federighi)在WWDC上满脸傲骄地说「We believe you should havegreat features and great privacy」，那个瞬间特别像一个小孩子，自信满满地向世界宣告「我们就是能站着把钱赚了」。就这样，差分隐私从研究论文一跃成为科技新闻头条。其实 Google 也有尝试过类似的事情，在 GitHub 上开源了一个名为RAPPOR(Randomized Aggregatable Privacy-Preserving Ordinal Response)的项目，从原理上来说，也是向数据中注入可控的噪音元素的方式来保护用户隐私，早在2014 年Google就以这项技术来收集用户使用Chrome浏览器时的资料。不过DP主要是由微软研究院的C. Dwork提出及发展，微软也已经在这个领域申请了不少的专利。遗憾的是，一如苹果宣称的，苹果是唯一一家将Differential Privacy作为标准大规模部署的公司。
2. 重大用户隐私泄露事件过去几十年，互联网的发展彻底改变了我们的生活。网络逐渐成为人们生活的中心——网购、聊天、看新闻、查股票⋯⋯，无不通过网络进行。日常生活的网络化塑造了一个网络时代和一大批与我们息息相关的互联网公司。这些公司往往提供优质而免费的服务，并拥有巨量用户。不过，为了提供更好的服务，或者出于其他商业目的，几乎所有的互联网公司都在尽可能地记录用户的行为。这些用户数据对互联网公司来说是珍贵的资源，因为他们可以通过机器学习和数据挖掘从中获得大量有用的信息。与此同时，用户数据亦是危险的“潘多拉之盒”：数据一旦泄漏，用户的隐私将被侵犯，同时对公司的信誉也带来莫大的伤害。近年来，我们已经目睹了多起用户隐私泄漏事件，几家大公司深陷其中；而这些事件全都是由于数据拥有者分享数据不当引起的。
20 世纪最著名的用户隐私泄漏事件发生在美国马萨诸塞州。90 年代中叶，该州团体保险委员会(Group Insurance Commis-sion)决定发布州政府雇员的“经过匿名化处理的”医疗数据，以助公共医学研究。在数据发布之前，委员会对潜在的隐私问题已有所认识，因此删除了数据中所有的敏感信息，例如姓名、住址和社会安全号码(social security number)。然而 1997 年，麻省理工学院博士生拉坦娅•斯威尼(Latanya Sweeney)(现任哈佛大学教授)成功破解了这份匿名数据，并找到了时任马萨诸塞州州长威廉•威尔德(William Weld)的医疗记录，还将该记录直接寄给了州长本人。
2006 年8月4日，美国在线公司的研究部门在互联网上发布了超过65万用户在过去三个月的搜索关键字，以供公众对搜索技术进行研究。该公司对发布的数据进行了匿名化处理，但仅仅是把用户的账号用一个随机号码代替，并没有对用户所提交的搜索关键字进行任何处理。随后，《纽约时报》成功将部分数据去匿名化，并在经过当事人同意后，公开了其中一位搜索用户的真实身份。这起隐私泄漏事件引起了人们的广泛关注，并导致美国在线公司首席技术官辞职。随后，美国在线公司因为此事件在北加州地方法院被起诉。
网飞公司 (Netflix) 也曾深陷数据隐私泄漏的丑闻中。2006 年，网飞公司投资100万美元举办了一个为期三年的推荐系统算法竞赛，并发布了一些用户的影评数据供参赛者测试。出于隐私保护，网飞公司在发布数据前将所有用户的个人信息移除，仅保留了每个用户对各个电影的评分以及评分的时间戳。然而，来自德州大学奥斯汀分校的两位研究人员利用网飞用户影评数据与公开的互联网电影数据库(IMDB)用户影评数据之间的相关性，将网飞公司的一部分匿名用户与公开的IMDB用户进行了一一对应，由此获得了IMDB用户在网飞公司网站上的全部电影浏览信息（包括涉及敏感题材的电影）。为此，2009年，网飞公司遭到了4 位用户的起诉，也不得不取消了原定于2010年举行的第二届算法竞赛。
3. 隐私保护研究的目的隐私保护研究的目标在于提出用以修改隐私数据的技术，使得修改后的数据可以安全发布(以供第三方进行研究)，而不会遭受去匿名化等隐私攻击。同时，修改后的数据要在保护隐私的前提下最大限度地保留原数据的整体信息，否则被发布的数据将毫无研究价值。具体来说，当前的研究热点主要集中在两个方面：
(1)隐私保护技术能提供何种强度的保护，或者说能够抵御何种强度的攻击；
(2)如何在保护隐私的同时，最大限度地保留原数据中的有用信息。
针对层出不穷的隐私攻击方式和现有隐私保护机制的缺陷，来自微软研究院的德沃柯(Dwork) 等人于2006年提出了差分隐私模型。差分隐私具有两个最重要的优点：(1)差分隐私严格定义了攻击者的背景知识：除了某一条记录，攻击者知晓原数据中的所有信息——这样的攻击者几乎是最强大的，而差分隐私在这种情况下依然能有效保护隐私信息；(2)差分隐私拥有严谨的统计学模型，极大地方便了数学工具的使用以及定量分析和证明。正是由于差分隐私的诸多优势，使其一出现便迅速取代了之前的隐私模型，成为隐私研究的核心，并引起理论计算机科学、数据库与数据挖掘、机器学习等多个领域的关注。
上图给出了差分隐私的一般性方法。当用户(也可能是潜藏的攻击者)向数据提供者提交一个查询请求时，如果数据提供者直接发布准确的查询结果，则可能导致隐私泄漏，因为用户可能会通过查询结果来反推出隐私信息。为了避免这一问题，差分隐私系统要求从数据库中提炼出一个中间件，用特别设计的随机算法对中间件注入适量的噪音，得到一个带噪中间件；再由带噪中间件推导出一个带噪的查询结果，并返回给用户。这样，即使攻击者能够从带噪的结果反推得到带噪中间件，他也不可能准确推断出无噪中间件，更不可能对原数据库进行推理，从而达到了保护隐私的目的。
差分隐私的定义是建立在对随机算法的约束之上的。约束的根本目的在于限制攻击者在得到带噪中间件后，对原数据库的推导能力。定义一给出了差分隐私的数学表达。
隐私是指个人、组织机构等实体不愿意被外部知晓的信息。例如，个人的薪资、医疗记录等。虽然出现了多种基于 -匿名和划分隐私保护框架的保护方法，而差分隐私保护技术被公认为比较严格和强健的保护模型。该保护模型的基本思想是对原始数据、对原始数据的转换或者是对统计结果添加噪音来达到隐私保护效果。 该保护方法可以确保在某一数据集中插入或者删除一条记录的操作不会影响任何计算的输出结果。另外，该保护模型不关心攻击者所具有的背景知识，即使攻击者已经掌握除某一条记录之外的所有记录的信息，该记录的隐私也无法被披露。差分隐私的形式化定义如下。
定义1:
给定数据集和，二者互相之间至多相差一条记录，即。给定一个隐私算法，为的取值范围，若算法在数据集和上任意输出结果满足下列不等式，则 满足-差分隐私。
其中，概率由算法的随机性控制，也表示隐私被披露的风险；隐私预算参数表示隐私保护程度， 越小隐私保护程度越高。从定义1可以看出差分隐私技术限制了任意一条记录对算法输出结果的影响。该定义是从理论角度确保算法满足-差分隐私，而要实现差分隐私保护需要噪音机制的介入。
噪音机制是实现差分隐私保护的主要技术，常用的噪音添加机制分别为拉普拉斯机制与指数机制。而基于不同噪音机制且满足差分隐私的算法所需噪音大小与全局敏感性(Global Sensitive)密切相关。
定义2:
对于任意一个函数，函数的全局敏感性为。其中，和至多相差一条记录，表示所映射的实数空间，表示函数的查询维度，表示度量使用的距离，通常使用来度量 。
该机制过拉普拉斯分布产生的噪音扰动真实输出值来实现差分隐私保护。
定理1：
对于任一个函数，若算法的输出结果满足下列等式，则满足-差分隐私。
其中，是相互独立的拉普拉斯变量，噪音量大小与成正比，与成反比。算法的全局敏感性越大，所需噪音越大 。从上式可知，中第个元素由拉普拉斯噪音引起的标准绝对误差与方差分别为
该机制主要是处理一些输出结果为非数值型的算法，例如，分类操作中分裂属性的选择问题。该机制的关键技术是如何设计打分函数，其中表示从输出域中所选择的输出项。
定理2：
给定一个打分函数，若算法
满足下列等式，则满足-差分隐私。
其中，为打分函数的全局敏感性。由上式可知，打分越高，被选择输出的概率越大。
差分隐私保护技术本身蕴含着序列组合性与并行组合性两种重要的组合性质。
性质1.
给定数据库与个随机算法，且满足-隐私，则在上的序列组合满足-差分隐私，。
性质2.
设为一个隐私数据库，被划分成个不相交的子集，,设为任一个随机算法满足-差分隐私。则算法在上的系列操作满足-差分隐私。
这两种性质在证明算法是否满足差分隐私以及在隐私预算分配过程中起着重要作用。
满足差分隐私的保护算法需要在保护隐私的同时，又要兼顾保护后数据的可用性以及隐私预算的分配策略是否合理。通常包括3个方面对隐私保护算法进行度量。
(1)算法误差。
常用的应用型误差度量方法包括相对误差、绝对误差、误差的方差以及欧式距离等。此外，数据依赖情况下的操作，必须考虑信息缺损带来的误差。
(2)算法性能。
一般利用时间复杂度与渐近噪音误差边界对算法的性能进行评估。
(3)的合理分配。
隐私预算代表着数据隐私保护程度。 一旦耗尽，将破坏差分隐私，算法本身也就失去了意义。因此，合理的预算分配策略要尽可能使的生命周期持续长一些。常用的分配策略包括线性分配、均匀分配、指数分配、自适用性分配以及混合策略分配等。
参考文献
张啸剑, 孟小峰. 面向数据发布和分析的差分隐私保护[J]. 计算机学报, 2014(4):927-949.
数据分享中的差分隐私保护 张俊
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/11299.html
摘要：摘要隐私数据与机器学习看似矛盾，其实不然。在每个分区上训练机器学习模型，将其称为教师模型。差分隐私能够很好地与机器学习的任务相一致，比如在学习过程中，记住像病例这样的特殊训练实例是侵犯隐私的行为，也是一种过拟合现象，降低了模型泛化能力。 摘要： 隐私数据与机器学习看似矛盾，其实不然。如何有效保护机器学习训练中的隐私数据？谷歌专家给出了答案——PATE框架，就算你不太懂隐私保护的知识，也...
摘要：作者天琼，数据游戏优胜队伍成员介绍本文整理记录了参与的一次小型数据分析竞赛数据游戏，竞赛目标是预测年月日股闭市时招商银行的股价。日发现的数据有错误，需要手工矫正日该数据恢复正常。而函数，是对样本外的数据进行预测。 作者：天琼，「数据游戏」优胜队伍成员 介绍 本文整理记录了参与的一次小型数据分析竞赛「数据游戏」，竞赛目标是预测2019年5月15日A股闭市时招商银行600036的股价。 主...
摘要：作者天琼，数据游戏优胜队伍成员介绍本文整理记录了参与的一次小型数据分析竞赛数据游戏，竞赛目标是预测年月日股闭市时招商银行的股价。日发现的数据有错误，需要手工矫正日该数据恢复正常。而函数，是对样本外的数据进行预测。 作者：天琼，「数据游戏」优胜队伍成员 介绍 本文整理记录了参与的一次小型数据分析竞赛「数据游戏」，竞赛目标是预测2019年5月15日A股闭市时招商银行600036的股价。 主...
摘要：是世界上最重要的研究者之一，他在谷歌大脑的竞争对手，由和创立工作过不长的一段时间，今年月重返，建立了一个探索生成模型的新研究团队。机器学习系统可以在这些假的而非真实的医疗记录进行训练。今年月在推特上表示是的，我在月底离开，并回到谷歌大脑。 理查德·费曼去世后，他教室的黑板上留下这样一句话：我不能创造的东西，我就不理解。（What I cannot create, I do not under...
摘要：以此来实现硬件不换，功能迭代升级的目的。这样如何使用最低成本高效的升级则成了物联网设备的一个重要课题。 1、背景 随着网络环境日益便利，物联网速成长期，物联网设备跟随产品定位不同导致的碎片化特别严重，但他们都有一个共同点就是都需要迭代更新，产品多样且复杂，那么必然导致升级类型和样式多，不是...
阅读 1420·2023-04-25 19:00
阅读 4103·2021-11-17 17:00
阅读 1732·2021-11-11 16:55
阅读 1493·2021-10-14 09:43
阅读 3084·2021-09-30 09:58
阅读 824·2021-09-02 15:11
阅读 2092·2019-08-30 12:56
阅读 1372·2019-08-30 11:12
