数学保护隐私：一种新的数据安全方法

1997年，马萨诸塞州的医学研究人员开始提供对官员医疗记录的访问权限时，政府从名单中删除了患者姓名，地址和社会安全号码。时任州长的威廉·威尔德（William Weld）向公众保证，通过任命恢复身份是不可能的。

几天后，来自麻省理工学院的一名学生寄了一封信到Weld的办公室。州长医疗卡的摘录被封装在信封中。

尽管删除了明显的标识符，但官员们决定留下出生日期，性别和邮政编码（邮政编码）。在将这些数据与语音记录进行交叉比较之后，Latanya Sweeney能够计算出Weld的病历。

Sweeney在过去15年中的工作以及其他在隐私方面的突破引起了据称匿名数据的安全问题。

“我们发现人们对于将哪些数据视为私有的直觉效果不佳，”微软研究院硅谷的Frank McSherry说。“计算机正在不断提高从外行认为安全的信息中提取单个数据的能力。”

研究您的病史可以帮助您找到导致阿尔茨海默氏病风险的基因，减少医院错误的数量，或者找到治疗疾病的最佳药物。唯一的问题是如何在不泄露个人信息的情况下获取所有这些数据？关于该主题的十年研究已经在寻求一种通用的解决方案。

这种方法称为“差异隐私”，可让您在保护个人信息的同时发布数据。数据区分算法使研究人员可以对包含敏感信息的数据库提出任何查询，并以不透露任何个人数据（甚至是该数据库中特定人的数据的存在）的方式接收“模糊”答案。

微软研究院硅谷的辛西娅·德沃克（Cynthia Dvork）说：“我们的想法是，您可以无风险地使用您的数据。” Dvork在McSherry，Cobby Nissim和Adam Smith的帮助下于2005年引入了差异隐私（RP）的概念。

卡内基梅隆大学的Avrim Blum说，该方法保留“合理拒绝”的权利。 “如果我要假装我的个人信息与实际拥有的信息不同，我可以做到。实际上，RP机制的输出不会有太大差别，无论它是真实的还是假的我-因此我都可以否认我想要的一切。”

如此高的隐私级别似乎无法实现。实际上，当您提供真实或虚拟数据时，没有有用的RP算法会产生完全相同的结果。但是您可以允许算法产生几乎相同的数据。差异程度经过校准，代表隐私权的量化。人们或社区可以决定此参数的哪个值对应于可接受的隐私丧失程度，然后选择适当的算法。

隐私专家已经开发了各种RP算法，用于处理不同的数据并回答有关它们的不同问题。对于不是该领域专家的人们来说，大多数工作都很难理解，因此，科学家们正在开发标准化的计算机语言，这些语言不仅允许专家通过编写简单的程序以RP方式发布敏感数据。宾夕法尼亚大学计算机科学专家Aaron Roth说：“ RP是一种很有前途且非常有趣的技术。”


OnTheMap人口普查委员会通过发布数据但不披露个人信息来使用不同的隐私

大海捞针

似乎要解决隐私问题，您只需要发布与大批人员相关的通用数据即可。但是，即使这种方法也充满了对个人数据完整性的侵犯。

假设您需要确定作者是否患有糖尿病，并且您知道我的数据在数据库中。一个人可以减去两个查询的结果：“数据库中有多少人患有糖尿病”和“数据库中除了Eric Clarreich以外的名字中有多少人患有糖尿病。”

这两个查询的组合侵犯了我的隐私。但是，并不总是清楚哪些特定的问题组合会侵犯隐私权。找到这样的组合是一项完成NP的任务，也就是说，不存在有效的计算机算法来跟踪此类“攻击”。

2008年，研究人员显示了公开发表从一般遗传研究中获得的综合信息的危险-这是发现糖尿病对基因的依赖性的主要工具之一。这些研究涉及对100到1000名患有相同疾病的患者的测试组的基因进行解码，然后计算100,000个突变之一发生的平均频率。如果突变之一在该组中发生的频率更高，则表明它可能与疾病相关。

由当时是加利福尼亚大学研究生的尼尔斯·霍默（Niels Homer）领导的一组研究人员表明，在许多情况下，了解患者的基因组，就可以知道他是否属于基因组测试小组。此后，医学研究所协会撤销了有关发表遗传学研究数据的法令。

研究人员在2011年得出了一个更加令人惊讶的结论-在亚马逊的推荐系统的指导下，有可能提取有关购买的个人信息，从而得出诸如“谁同时购买了B和C”的结果。通过观察建议中的更改并将其与人们对购买的商品的评论进行比较，研究人员可以说，某个购买者在特定的一天购买了特定的商品，甚至在他发布商品评论之前。

在所有情况下，隐私措施似乎都是足够的，只要它们还不够。但是，此时已经在准备一种保护隐私的新方法，该方法是通过寻找以下主要问题的答案而获得的：保护隐私意味着什么？

两个世界的私密性

如果研究人员检查患者数据库并发现吸烟与某种形式的癌症之间存在联系，那么差异性隐私将无法保护在公共场所吸烟的人免受患病风险增加的人的标签的影响。但是，如果吸烟是一个人的秘密，隐藏在基地中，RP将保护他。

“差异”是指考虑两个世界的差异：在其中一个世界中，您允许您将个人数据包括在数据库中，而在另一个世界中，您不允许。这两个世界不是绝对相同的，但是可以使它们尽可能相似，并且几乎不可能区分它们。这就是RP的目的。

RP专注于发布数据，接收对数据库的查询并发布答案的算法-不精确，而是随机修改的。如果您基于两个依据（仅针对一个人的数据有所不同）提出相同的问题，您将得到基本相同的答案。


RP表示用户在搜索引擎中搜索“板球”一词的位置

更准确地说，对于任何可能的答案，两个数据库收到它的可能性都应该相同；这两个概率之比应限制在接近于整数的数R中。 R越接近1，攻击者就越难发现他是从基地A还是从基地B接收信息，而受保护的人X则越受保护，因为如果攻击者无法知道他接收的信息是否包括有关X的信息，他将无法了解

RP的研究人员通常谈论R的对数，并用note表示。该参数量化了个人数据的泄漏。 Ɛ越接近零，算法就越能更好地保护隐私。

为了了解如何构造RP算法，让我们看一下这种算法的最简单的例子。他使用的情况下，发问者只能进行定量查询。例如：“数据库中有多少人拥有属性C？”

假设对一个问题的真实答案是157。RP算法将向其中添加“噪声”-在发出答案之前，添加或减去一个随机数。结果，我们得到153、159或292。发问者知道算法使用的概率分布，因此他知道实际结果有多失真（否则，返回将完全无用）。但是他不知道将什么样的随机数添加到答案中。

必须仔细选择分配公式。为了了解哪种分发可以保证隐私，让我们想象一个持久性询问者试图找出我是否在数据库中。他问：“数据库中有多少人叫Eric Clarreich？”假设他收到100的答案。由于这个名字很少见，因此他意识到答案实际上是0或1。他有两种可能：

A）答案是0，算法加了100作为噪声；
B）答案是1，并且算法增加了99。

选择100和99的概率应该相同。然后，提问者无法区分这两种情况。更准确地说，这两个概率之比不应超过预定的R。并且不仅对于对100和99，而且对于任何两个连续的数，都应保留这种条件。

该属性具有拉普拉斯分布。它的尖峰降为零，然后图形在两个方向上逐渐减小。为此，满足存在数字R（分布宽度）的条件，以使得对于任何两个连续的数字，其概率之比为R。

对于每个宽度，都有一个可能的拉普拉斯分布。因此，您可以使用宽度来获得一个分布，该分布恰好提供了我们所需的隐私度。为了获得高度的隐私，分布范围将相对较宽且平坦。远离0的数字将以与接近零的数字几乎相同的概率掉出来。数据将模糊很多。

自然，隐私和实用性之间存在对抗。您需要的隐私越多，必须添加的噪音就越大，答案将越无用。当使用拉普拉斯分布时，增加的噪声量为反。如果privacy参数为0.01，则该算法将使定量指标模糊约100。

数据集越大，给定的模糊对实用性的影响就越小。在具有数百条记录的数据库中，模糊100会比在具有数百万条记录的数据库中造成更大的干扰。根据Dvork的说法，对于Internet规模的数据（即数亿），该算法已经为实际使用提供了足够的保密性。

拉普拉斯（Laplace）所说的“噪音”只是实施RP的第一步。研究人员已经提出了大量复杂得多的算法，在某些情况下，其中许多实用程序和隐私的比率都超过了拉普拉斯算法。

德沃克说：“人们总是在寻找改进的方法，但仍有改进的空间。”她说，关于比互联网更普通的数据集，“有很多算法可以执行许多任务。”

使用RP算法，无需仔细分析隐私侵犯问题-该保护已内置在算法中。由于干扰自己事务的问题通常归结为与特定人群有关的少数问题，而性质不同的问题研究的是大型群体的行为，因此抵消个人特征的额外噪音的数量对合法问题的答案影响很小。

有了RP，数据研究人员的问题（例如与外部资源的交叉比较）就消失了。数学方法并不期望攻击者拥有有限的外部信息源。

“ RP方法意味着攻击者是万能的，” McSherry说。-即使攻击者在100年后回来，并一直积累着思想和计算机技术，他们仍将无法找出您是否在数据库中。RP受未来保护。”

基本原语

到目前为止，我们一直在考虑有人用数字作为答案查询数据库的情况。但是现实更加复杂。研究人员想问数据库很多问题。随着时间的流逝，您的个人信息的一部分将进入各种数据库，每个数据库都将提供数据，而不会询问其余部分。

当研究人员询问所有存在您的数据的数据库时，RP提供了一种准确而简便的方法来评估总体的隐私威胁。假设您的数据在两个数据库中，并且这些数据是根据提供隐私参数Ɛ1和Ɛ2的算法给出的，则泄露的个人信息总量将不超过Ɛ1+Ɛ2。相同的公式适用于具有多个查询的单个数据库。对于m个查询，泄漏将限制在m * above之上。

从理论上讲，数据库管理员可以允许研究人员提出任意数量的问题，并在每个答案中添加必要的拉普拉斯噪声，以使泄漏的个人数据总量不超过特定限制。

事实证明，对数字答案的限制不是那么关键。可以更改许多其他查询，以使它们变得定量。例如，如果您需要为2012年出生的婴儿创建数百个最受欢迎的名字的列表，则可以提出一系列问题，例如“给多少个孩子以A开头的名字？”并处理结果。

“学习机器学习的早期结果之一是，可以使用数值查询来学习原则上可以学到的任何东西，” Aaron Roth说。 “这样的请求本身并不是玩具，而是一个基本的原语”，即砖头，可以在此基础上构建更复杂的算法。

但是有一个陷阱。我们可以问的问题越多，每个答案的噪音就越大。让我们看一个带有名称的示例。如果我们决定将最大隐私费用limit限制为0.01，并且名称将为10,000，则每期的隐私限制将为Ɛ/ 10,000，即0.000001。噪声级别将为10,000 /Ɛ或1,000,000-并且此级别完全消除了实际结果。

换句话说，向每个答案添加拉普拉斯噪声的“正面”方法受到可能问题数量的限制。为了解决这种情况，程序员必须开发出更合适的原语-算法“砖”，借助它们，给定特定库和任务的结构，他们可以更准确地回答更多问题。

例如，在2005年，史密斯（Smith）发现带有名称的任务具有特殊的结构：从数据库中删除有关一个人的信息只会改变10,000个名称中只有一个的答案。因此，我们可以对每个答案添加不超过1 /Ɛ的噪声，而不是10,000 /Ɛ，并且答案的隐私将保持在我们的限制内。这样的原语可以应用于任何“直方图”查询，即有关有多少人属于几种互斥类别（例如姓名）之一的查询。

当史密斯告诉德沃克这件事时，德沃克说：“我内心有些高兴。” “我意识到我们可以使用请求或计算的结构，并获得更高的响应准确性。”

从那时起，计算机科学家就开发了一个大型的此类基元库。并且由于附加规则解释了组合算法时隐私会发生什么，程序员可以将这些“砖块”组装成复杂的结构，同时监视对隐私泄漏的限制。

为了简化非专业人士对RP系统的访问，几个小组正在努力创建一种编程语言，该语言将使我们能够从算法的数学基础中抽象出来。


PINQ-RP PL的示例之一

用于处理差异性隐私的编程语言（例如PINQ）为敏感数据提供了接口，并允许您提出有关它们的问题，调整答案以保护隐私。创建PINQ语言的McSherry表示：“如果您负责数据集，则不必担心人们在使用此PL发出请求时会如何处理它。” “该程序保证了查询的安全性。”

不可再生资源

当包含您的数据的不同数据库提供查询答案时，由于the的简单加法则规则确定了隐私丢失的确切上限，因此，根据McSherry的说法，该规则将隐私变成一种货币。

例如，如果您决定一生对您个人隐私丢失的限制是可以接受的，则可以决定“花费”这种隐私-换钱或支持良好的研究项目。每次您允许在新的信息发布中使用数据时，您都会知道隐私“预算”的余量是多少。

数据集的负责人可以决定如何使用他决定发布的隐私量-例如，考虑研究项目中的提案，这些提案不仅描述了可用的请求，还描述了项目中使用的隐私量。然后，策展人将能够选择哪些项目将最好地利用这套信息的现有“预算”。支出预算后，将关闭数据集。

“隐私是不可再生的资源，” McSherry说。 “一旦花费，它就会消失。”

当被问及what的值代表可接受的隐私丧失限制时，社会应该回答，而不是程序员。每个人都可以有自己的答案。虽然为诸如隐私之类的无形事物分配价格标签的前景看起来令人望而生畏，但与此类似的事物已经存在。

“还有另一种具有相同属性的资源-您的生活时钟，” McSherry说。“他们的人数有限，花掉之后，它们就会消失。” 但是，由于我们拥有货币和劳动力市场，因此我们的社会提出了如何为人类时间分配价格标签。人们可以想象隐私会发生同样的事情。”

Source: https://habr.com/ru/post/zh-CN398011/