【中文翻译】第1章-The Algorithmic Foundations of Differential Privacy

为方便阅读，故将《The Algorithmic Foundations of Differential Privacy》翻译项目内容搬运至此；

教材原文地址：https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf

中文翻译版 Github 项目地址1：https://github.com/guoJohnny/algorithmic-foundation-of-dp-zh-cn

中文翻译版 Github 项目地址2：https://github.com/doubleheiker/algorithmic-foundation-of-dp-zh-cn

感谢前辈的翻译工作！

前言

隐私保护数据分析的问题由来已久，涉及多个学科。随着有关个人的电子数据变得越来越详细，并且随着技术能够更强大地收集和管理这些数据，对隐私的鲁棒性、隐私的意义和隐私在数学上严格的定义需求不断增长，对满足隐私定义的算法需求也在不断增长。差分隐私就是这样的定义。

在讨论了差分隐私的含义之后，本书主要介绍了实现差分隐私的基本技术，并将这些技术应用于创造性的结合中（第3-7节），其中使用了’查询发布问题’作为示例。其中最重要的是：对比单纯用差分隐私计算替换非隐私的每个计算步骤这种实现方法，通过重新思考计算目标能有更好的结果。

尽管有一些惊人的强大的计算结果，但仍然存在根本的局限性——不仅局限于使用差分隐私可以实现什么目标，而且还局限于什么方法可以防止隐私被完全破坏（泄露）（第8节）。

实际上，本书中讨论的所有算法都针对不同计算能力的对手保持着不同的隐私。某些算法是计算密集型的，其他算法则为高效率的。攻击者和算法的计算复杂度均在第9节中讨论。

在第10节和第11节中，我们从基础知识转向查询发布以外的应用程序，讨论了用于机制设计和机器学习的差分私有方法。关于差分私有算法的绝大多数文献都考虑了要进行大量分析的单个静态数据库。在第12节中讨论了其他模型中的差分隐私，包括分布式数据库和数据流计算。

最后，这本书是对差分隐私问题和技术的全面介绍，但并不是要进行详尽的调查，因为到目前为止，在差分隐私方面有大量研究，我们可以只覆盖一小部分。

一、差分隐私的承诺

差分隐私 描述了数据持有者对数据主体的承诺：“无论您将数据用于任何研究或分析，都不会受到不利影响或其他影响。” 差分数据库机制可以使机密数据广泛用于准确的数据分析，而无需诉诸数据清洗，数据使用协议，数据保护计划，或其他受限方面。但是，保证隐私性的同时，将消耗数据实用性：《信息恢复基本法》指出，对太多问题的过于准确的回答将以一种惊人的方式破坏隐私。关于差分隐私的算法研究的目标是将这种不可避免性推迟尽可能长的时间。

差分隐私解决了一个问题，即分析人员通过数据集学习整体信息的同时（趋势、统计信息），无法获取个人的详细信息。

医学数据库可能会告诉我们，吸烟会导致癌症，影响保险公司对吸烟者长期医疗费用的看法。吸烟者受到分析的伤害了吗？如果保险公司知道他吸烟，他的保险费可能会上涨。他可能也会得到帮助。但保险公司学习他的健康风险，使他进入戒烟计划。吸烟者的隐私被侵犯了吗？当然，研究结束后对他的了解比以前更多，但他的信息是不是“泄露”了？差分隐私将认为它不是，理由是对吸烟者的影响是相同的独立于他是否在研究中。是这项研究得出的结论影响了吸烟者，而不是他在数据集中的存在与否影响了实验得出的结论。

差分隐私在满足隐私保护需求下，同时保证了分析数据集能得出相同的结论，例如，吸烟会导致癌症，这与是否有人的数据选是否在数据集中无关。具体地说，任何个体的存在或不存在这个数据集中，差分隐私能确保输出（对查询的响应）在“本质上”发生的概率是相同的。这里，概率被差分隐私机制（由数据持有者控制）所做的随机选择所取代，这里术语“本质上”被抽象为参数 $ϵ$。较小的 $ϵ$ 将产生更好的隐私（和更不准确的响应）。

差分隐私在满足隐私保护需求下，同时保证了分析数据集能得出相同的结论，例如，吸烟会导致癌症，这与是否有人的数据选是否在数据集中无关。具体地说，任何个体的存在或不存在这个数据集中，差分隐私能确保输出（对查询的响应）在“本质上”发生的概率是相同的。这里，概率被差分隐私机制（由数据持有者控制）所做的随机选择所取代，这里术语“本质上”被抽象为参数 $\epsilon$。较小的 $\epsilon$ 将产生更好的隐私（和更不准确的响应）。

差分隐私是一个定义，而不是一个算法。对于给定的计算任务 $T$ 和给定的 $\epsilon$ 值，将有许多不同的私有算法以 $\epsilon$-差分隐私 方式实现 $T$。有些算法会比其他算法更准确。当 $\epsilon$ 很小时，很难为任务 $T$ 找到一个高精度的$\epsilon$-差分隐私算法，就像为一个特定的计算任务找到一个数值稳定的算法一样。

1.1 隐私保护的数据分析

差分隐私是针对隐私保护数据分析问题而提出的一种隐私定义。我们简要地讨论了解决隐私保护的其他方式的一些问题（个人认为：此处的其他方式应该是：属性隐藏、匿名、少量数据等隐私保护方式）。

数据不能完全匿名并且仍然有用

一般来说，数据越丰富，就越有趣和有用。这就产生了“匿名化”和“删除可识别个人信息”的概念，这些概念希望部分数据记录可以被掩盖，其余部分可以发布并用于分析。

然而，由于数据的丰富性使得“个人”数据属性可能与其他领域的数据属性相重合，比如邮政编码、出生日期和性别的组合，甚至三个电影的名字和一个独立的人观看这些电影的大致日期。这种“命名”功能可用于联动攻击，以将不同数据集中的“匿名”记录与非匿名记录进行匹配。有如下两个事例：

• 1.通过将匿名医疗遭遇数据与（公开提供的）选民登记记录相匹配，确定了马萨丘塞特政府的医疗记录。

• 2.通过与互联网电影数据库（IMDB）的链接，确定了 Netflix 用户，其观看历史记录包含在 Netflix 发布的匿名电影记录集合中，作为推荐竞赛的训练数据。

差分隐私能中和联动攻击：因为差分隐私是数据访问机制的一个属性，并且与对手可用的辅助信息（背景知识）的存在或不存在无关，访问 IMDb 用户数据将不能对存在 Netflix 训练集中的用户数据进行联动攻击,换言之，攻击在数据集中的用户成功的可能性不会超过不在数据集中的用户。

重标识“匿名”记录并非唯一风险

“匿名”数据记录的重新标识显然是不可取的，这不仅是因为重新标识本身（这肯定揭示了数据集中的成员身份），而且还因为记录可能包含损害信息，如果它与个人相关联，则可能会造成损害。在给定日期从特定紧急护理中心收集的医疗遭遇记录可能只列出少量不同的投诉或诊断。邻居在相关日期访问设施的附加信息给出了邻居病情的一系列可能诊断结果。可能无法将特定记录与邻居匹配这一事实为邻居提供了最低限度的隐私保护。

个人理解：此处的重标识“匿名”记录应该指的是上一小节中通过其他数据集共有属性对匿名数据进行标识。个人认为此处的邻居诊断例子是指，通过关联特定信息，虽然无法确切知道这个人患了什么病，但却缩小了其患病的种类，排除了多余信息，这样是否是种变相的隐私泄露？因为这样只能提供很小的隐私保护。

不具有保护性的大数据集查询

对于特定个体的查询无法准确地得到安全的回答，事实上，人们可能希望直接拒绝他们（如果在计算上无法识别他们）。但如下面的差分攻击所示，强迫查询超过大型集并不是万能的。假设攻击者已知X先生在某个医学数据库中。综上所述，这两个大问题的答案是 ：

• 1.“数据库中有多少人具有镰状细胞特征？”

• 2.“数据库中除了X外，还有多少人有镰状细胞的特征？”

通过这两个数据查询得出数据，交出X先生是否有镰状细胞特征。

个人理解：如果某种查询是不允许针对特定个人（这里指的是X）进行查询，只能针对大规模数据统计类查询，这种数据发布的方式也是不具有保护性的，能通过差分攻击攻击得到隐私数据，如标题所示，对大数据集的查询不具有保护性。

查询审查存在的问题

查询审核有问题。如果根据历史记录，回答当前的查询会损害隐私，那么人们可能会倾向于审查查询和响应的序列，以阻止任何响应。例如，审核员可能在寻找可能构成差分攻击的成对查询。这种方法有两个困难。首先，拒绝回答一个问题本身就有可能被披露。第二，查询审计在计算上是不可行的；事实上，如果查询语言足够丰富，则甚至不存在算法过程来判断一对查询是否构成差分攻击。（审核、防止差分攻击语句是不现实的）

“不安全”的摘要统计

在某种意义上，将摘要统计作为隐私解决方案是失败的，是直接来自上述差分攻击。摘要统计的其他问题包括针对数据库的各种重建攻击，数据库中每个人都有一个要保护的“秘密位”。有用性目标可以是允许，例如，形式的问题“满足属性 p 的多少人具有秘密比特值 1 ？”。另一方面，对手的目标是增加猜测个人秘密的机会。第 8.1 节中描述的重建攻击显示了即使是这种类型的线性查询数也难以保护：除非引入足够的不精确性，否则几乎所有的秘密比特都可以重建。

公布汇总统计数据的风险的一个显著例证是，应用统计技术，最初是为了确认或驳斥个人 DNA 在法医学混合物中的存在，以裁定个人是否参与全基因组关联研究。根据人类基因组计划的一个网站，“单核苷酸多态性”（SNPs，发音为“snips”）是当基因组序列中的单核苷酸（A、T、C或G）改变时发生的 DNA 序列变异。例如，一个 SNP 可能会改变 AAGGCTAA 到 ATGGCTAA 的 DNA 序列。“在这种情况下，我们说有两个等位基因：A 和 T。对于这样一个 SNP，我们可以问，给定一个特定的参考群体，这两个可能等位基因的频率是多少？考虑到参考群体中 SNP 的等位基因频率，我们可以研究这些频率对于有特定疾病的亚群（即“病例”组）可能有什么不同，寻找与疾病相关的等位基因。因此，全基因组关联研究可能包含大量snp病例组的等位基因频率。根据定义，这些等位基因频率只是聚合的统计数据，而（错误的）假设是，通过这种聚合，它们保留了隐私。然而，考虑到个体的基因组数据，理论上有可能确定个体是否属于病例组（并且，因此，有疾病）。作为回应，国家卫生研究院和 Wellcome信托基金终止了公众从他们资助的研究中获取总频率数据的途径。

（受制于相关知识缺失，未能理解此段重建攻击和 DNA 事例，需要对第 8.1 节进行了解）

这是一个具有挑战性的问题，即使是对于差分隐私，因为涉及到大量的——数十万甚至一百万——测量，这些测量包含和关联了大群体中的小数量的个体。

长期的事实并不“好”

如果一个数据主体随着时间的推移而被跟踪，那么揭露数据个体长期的行为（例如购买面包）可能会有问题。举个例子，假设某人，他年复一年地定期买面包，直到突然转向很少买面包。一位分析师可能会得出结论，某人很可能被诊断为2型糖尿病。分析员可能是正确的，也可能是不正确的；不管怎样，某人的隐私都会受到伤害。

（此处原文为Ordinary Fact，根据下文内容来看，更应该表示为一种长期的普遍性结果，故将其翻译为“长期”）

“少数人”原则

在某些情况下，一种特定的技术实际上可以为数据集的“典型”成员提供隐私保护，或者更普遍地说，为“大多数”成员提供隐私保护。在这种情况下，人们经常听到这样的说法，即这种技术是足够的，因为它损害了“少数”参与者的隐私。撇开那些对隐私最重要的人来说可能是离群者这一担忧不谈，“少数人”原则在本质上并不是没有价值的：需要做出社会判断，权衡成本和收益。一个清晰的隐私定义与“少数人”的理念相一致，但还没有发展出来；但是，对于单个数据集，“只有少数”的隐私可以通过随机选择行的子集并将其全部释放来实现（引理4.3，第4节）。抽样界限描述了统计分析的质量，可以在随机子样本上执行，它控制要释放的行数。当“少数人”的原则被拒绝时，差分隐私提供了另一种选择。

（个人理解为离群点更容易遭受差分攻击，需要在之后深入理解）

1.2 参考文献

Sweeney [81] linked voter registration records to “anonymized” medical encounter data; Narayanan and Shmatikov carried out a linkage attack against anonymized ranking data published by Netflix [65]. The work on presence in a forensic mix is due to Homer et al. [46]. The first reconstruction attacks were due to Dinur and Nissim [18].

目录导航

第1章：https://blog.csdn.net/AdamCY888/article/details/146454841
第2章:https://blog.csdn.net/AdamCY888/article/details/146455093
第3章(1/3):https://blog.csdn.net/AdamCY888/article/details/146455756
第3章(2/3):https://blog.csdn.net/AdamCY888/article/details/146455796
第3章(3/3):https://blog.csdn.net/AdamCY888/article/details/146455328
第4章:https://blog.csdn.net/AdamCY888/article/details/146455882
第5章:https://blog.csdn.net/AdamCY888/article/details/146456100
第6章(1/2):https://blog.csdn.net/AdamCY888/article/details/146456712
第6章(2/2):https://blog.csdn.net/AdamCY888/article/details/146456972
第7章:https://blog.csdn.net/AdamCY888/article/details/146457037
第8章:https://blog.csdn.net/AdamCY888/article/details/146457172
第9章:https://blog.csdn.net/AdamCY888/article/details/146457257
第10章:https://blog.csdn.net/AdamCY888/article/details/146457331
第11章:https://blog.csdn.net/AdamCY888/article/details/146457418
第12章:https://blog.csdn.net/AdamCY888/article/details/146457489
第13章(含附录):https://blog.csdn.net/AdamCY888/article/details/146457601