2. 基本术语
这一部分正式开始，给出了差分隐私的正式定义，并且列举了一些它的关键性质。
2.1 计算模型
我们假设存在一个可信的监管者，它持有包含个体信息的数据库D，通常数据库由n行数据组成。直观上来说，每一行包含一个个体的数据。隐私保护的目标是保护每一行个体数据隐私的同时，允许整个数据库用于统计学分析。
在非交互式或离线模型中，监管者产生一些目标，例如一个概况统计的“合成数据库”，或是“清洗过的数据库”等等。在这些信息发布后，监管者不再有用，原始的数据也可能会被销毁。
查询是一个应用于数据库的一种功能。在交互式或在线模型中允许数据分析者适应性地查询，数据分析者决定基于之前查询的响应提出下一个查询。
运行于个体集中的一种协议将取代可信的监管者，这种协议使用了密码学相关的技术，以此来保证多方协议的安全性，但是很大程度上，我们不会涉及密码学的假设。12章会描述这些，也可以在其他文献中学习。
当事先知道所有的查询时，非交互式模型应该会提供更好的精度，因为它能使噪声与知晓的查询框架所关联。与此相反，当事先不知道任何有关查询的信息时，非交互式模型面临严峻的挑战，因为它必须提供给查询者所有可能的查询。正如我们将要看到的，为了确保隐私，或甚是阻止隐私泄漏灾难，对于许多问题的查询结果，精确性将会下降。为查询者提供各种可能的查询将是不可行的。
一种隐私机制，或是一种简单的机制，它是一种算法，将一个数据库，一个数据类型的全集$\chi$（所有可能的数据库中行的集合），随机二进制数，以及，可选的一系列查询作为输入，而产生一个输出字符串。如果一系列的查询输入存在，所希望的是输出字符串能够被解码为查询相关的精确回答。如果没有查询存在，则是非交互式模型的情况，所希望的是输出字符串能够被翻译为所期待的回答。
在一些情况下，我们可能会要求输出的字符串是一个合成的数据库。它是一种多重集，是由可能的数据库中行的全集$\chi$所得出的。这种情况下，解码方式实现对于合成数据库的查询，然后运用一些简单的转化，例如乘以一个缩放因子，目的是获得真实的查询结果的一个近似值。
2.2 定义私有数据分析
在数据分析的背景下，定义隐私的一种通用方法是分析者在完成分析后，比起分析开始之前，并不会知道更多的有关任何个人的信息。它对一个目标通常也形式化了，即要求攻击者在攻击前后有关个人信息的观点不能“太不相同”，或者是访问数据库不能改变攻击者关于个人信息相关的观点。然而，如果数据库可以提供任何数据，那么隐私的这一定义将是不可实现的。例如，假设攻击者（不正确）之前的观点是每一个人都有两个左脚。访问数据库后，知道了几乎所有的人有一个左脚和一个右脚。现在，攻击者对于是否任意给定的应答者都有两个脚的观点有了不同的看法。
之前/之后的吸引人的部分，或者是“没有任何信息被学习到”，这种定义隐私的方法直觉上，如果没有任何有关个人的信息被学习到，那么个体又不会因为数据被分析而受到伤害。然而，“吸烟导致癌症”的例子表明这种直觉是有缺陷的；而罪魁祸首是背景信息（X先生吸烟）。
用“没有任何信息被学习到”来定义隐私是对于一个秘密学的语义安全的模仿。通俗的说，语义安全意识是对于密文，不能学习到任何有关明文（未加密的信息）的信息。即，在看到密文之后，任何有关明文的信息是在看到明文之前所知道的信息。所以如果有背景的信息表明密文是对“狗”或“猫”的一种加密，那么密文不能泄漏到底是对“狗”还是“猫”加密相关的进一步的信息。形式上，通过比较对于窃听者猜测是“狗”还是“猫”被加密的能力与拥有背景信息但并不知道密文的攻击者模拟器的猜测能力来建模。如果对于每一个窃听的攻击者与所有的背景信息（队友攻击者和模拟器是私密的），攻击者模拟器与窃听者猜测出结果的概率是相同的，那么系统是语义上安全的。当然，对于系统的有用性，合法接收者必须能够正确的解码信息；否则语义上的安全很容易实现。
我们都知道，在标准计算的假设下，语义上安全的密码系统存在，因此为什么我们不能建立语义上安全的私有数据库机制，这种机制在保证个体行信息的隐私的同时来对查询做出响应？
首先，类比是不完美的：在一个语义上安全的密码系统中有三个部分：消息发送者（他是明文消息加密者），消息接收者（他是解密者），和窃听者（在发送之前，她并不知道任何有关明文的信息，她对于她没法学习到任何有关明文信息感到失望）。与此相对，在隐私数据分析的环境中，只有两个部分：数据收集者，他使用了隐私机制（类比于发送者），数据分析者，他接收查询的响应（像是消息接收者）并且尝试计算出有关个体隐私保证的信息（像是窃听者）。因为合法的接收者与攻击者处于相同的部分，类比于加密系统是有缺陷的：拒绝所有攻击者的信息意味着拒绝所有数据分析者的信息。
其次，作为一种加密方案，我们要求隐私机制是有用的，意思是他让分析者知道了分析者之前并不知道的信息。对于一个攻击者模拟器，这种学习方式是无效的；即，没有模拟器可以“预测”数据分析者可以从中学习到什么。因此我们可以将数据库视为一种弱化的随机（不可预测）比特 的源，从中我们可以提取一些高质量的随机性作为随机填充。这可以用在一种加密技术中，这种加密技术是通过在私密消息中添加随机值（随机填充）来产生一串理论上隐藏了消息的私密性的字符串。只有那些知道填充的随机值的人才能获取到私密消息；而其他不知道所填充的随机值的人，无论他或她有多强大的计算能力，都不能获取到有关私密消息的任何信息。给定的访问某一数据库，数据分析这可以学习到随机填充，但是模拟器，若不能访问该数据库，就不能学习到任何有关的填充。因此，给定的一个私密的使用随机填充的加密技术作为附加信息，分析者能够解密私密信息，但是攻击者不能够学习到任何有关的信息。在攻击者和分析者对于学习私密信息的能力与攻击者模拟器做相同事情的能力之间将产生很大的不同，这消除了所有与语义安全性有任何相似之处的希望
吸烟导致癌症的例子与希望实现语义上的安全共同的障碍是背景信息。显然，为了有意义，隐私甚至必须在“合理的”背景信息的条件下得到保证，但是不合理的任意背景信息是有问题的。例如，使用政府数据库的分析者可能是主要从事搜索引擎的公司中的一员。对于此人，关于背景信息的“合理的”假设是什么？
2.3 形式化差分隐私
我们将开始差分隐私的技术定义，然后进一步阐释它。差分隐私通过处理来提供隐私保护；尤其是它将引入随机性。借用随机化处理的一个早期的隐私保护的例子随机响应，这种技术是在社会科学中发展的，通过获取是否具有性质P，来收集一些敏感的或是不合法行为的统计信息。让研究对象以一下规则回答他们是否具有性质P：
- 1.抛一枚硬币
- 2.如果是反面，然后如实回答问题。
- 3.如果是正面，则再抛一次硬币，若是正面回答“是”，反面回答“否”。
“隐私性”来自于任何结果都可以合理的否认；尤其是，如果性质P是不合法的行为，即使是回答“是”也并不是有罪的，因为这一答案有至少1/4的概率是由无论否具有性质P的人回答的。它的精确性来自于对于一个噪声生成过程的理解（随机化引入伪造的“是”和“否”的回答）：回答“是”的期望是那些并没有性质P的研究对象数量的1/4与具有性质P的研究对象数量的3/4的总和。因此，如果p是研究对象中具有性质P的真实数量，则回答“是”的期望为(1/4)(1-p)+(3/4)p=(1/4)+p/2。于是，我们可以通过回答“是”的数量的二倍减去1/2来估计p,即2((1/4)+p/2)-1/2。
随机化是重要的；更精确的说，任何重要的隐私的保障都需要随机化，无论是已经存在或是未来的背景信息源，包括其它的数据库，网站，在线社区，传闻，报纸，政府的统计数据，等等。这来自于一个简单的混合观点，我们现在简单概述。假设，基于不一致方面的原因，我们有一个特殊的确定性算法。特殊的意思是存在一种查询，两个数据库会产生不同的该查询的结果。在一次中，改变其中一行数据，我们将得到一对只有一行数据不同的数据库，相同的查询将产生不同的输出结果。一个攻击者在知道数据库是两个中的某一个时，可以获取到在未知行中的数据。
因此我们将需要讨论随机算法的输入输出空间。本书通篇都会谈论有关离散概率空间。有时，我们会描述来自连续分布采样的算法，但是这些应该都会以适当的方式离散化为有限的精度（可以查看下面的注解2.1）。通常，一个随机化的算法定义域为$A$，$B$是一个与从$A$到基于$B$的概率$\Delta(B)$单纯型相关映射的（离散）值域。
定义 2.1（概率单纯型）给定一个离散的集合$B$，基于$B$的概率单纯型用$\Delta(B)$来表示，它的定义如下：
$$\Delta(B)= \{ x\in \mathbb{R}^{|B|}: x_{i}\ge 0，对于所有的i， \sum_{i=1}^{|B|} x_{i}=1 \}$$
定义 2.2（随机化的算法）一个随机化的算法$M$，定义域为$A$。离散集$B$与$M$的映射为：$A \longrightarrow \Delta(B)$。输入$a \in A$,算法M输出$M(a)=b$的概率为$(M(a))_{b}$，其中对于每一个$b \in B$。概率空间是基于算法$M$的随机化。
我们认为数据库$x$是来自于全集$\chi$的一些记录集合。通常通过柱状图方便用来表示数据库：$x \in \mathbb N^{|\chi|}$，其中每一个记录$x_{i}$代表数据库$x$中元素$i$的数量，$i \in \chi$;（我们略微滥用符号，用符号$\mathbb N$表示所有非负整数的集合，其中包含零）。在这种表示中，两个数据库$x$和$y$的距离通常用它们的ℓ1距离表示。
定义 2.3（数据库的距离）数据库$x$的ℓ1范数用$||x||_{1}$来表示，定义如下：
$$||x||_{1}= \sum_{i=1}^{|\chi|} |x_{i}|$$
两个数据库$x$和$y$的ℓ1距离为$||x-y||_{1}$
注意这里的$||x||_{1}$是计算数据库$x$的大小（即包含数据元素的个数），而$||x-y||_{1}$是计算$x$和$y$之间有多少个不同的记录。
数据库可以由行（$\chi$中的元素）的多重集表示，甚至可以用行的有序列表来表示，这是一种特殊集合的情况，它的行号为每个元素名称的一部分。这种情况下，数据库之间的距离可以用汉明距离来计算，即，数据库中行号不同的数量。
然而，除非另外注明，我们将使用柱状图的方式表示上述所描述的。（注意，不论怎样，即使柱状图记法在计算上便利，而在实际运用中，多重集表示法更加的简明。）
我们现在已经为正式定义差分隐私做好了准备。差分隐私从直观上保证了随机化算法对于相似的输入数据库，有相似的输出。
定义 2.4（差分隐私）一个随机化的算法为$M$，定义域为$\mathbb N ^ {|\chi|}$,它是$(\epsilon,\delta)$-差分隐私。如果对于所有的$S \subseteq Range(M)$，以及$x,y \in \mathbb N ^ {|\chi|}$，并且满足$||x-y||_{1} \le 1$：
$$Pr[M(x)\in S]\le exp(\epsilon) \ Pr[M(y)\in S] + \delta$$
这里概率空间是基于机制$M$的随机化。如果$\delta=0$，我们就说$M$满足$\epsilon$-差分隐私。
特别地，我们对于$\delta$值感兴趣，它小于数据库大小的多项式的倒数。尤其是，$1/||x||_{1}$大小的$\delta$是非常危险的：它们允许通过公布数据库一小部分数量的完整记录来“保证隐私”——明确的有关“仅仅一部分”哲学的讨论是在第一部分。
然而，即使当$\delta$被是可以忽略时，$(\epsilon , 0)$-与$(\epsilon , \delta)$-差分隐私在理论上也是有区别的。其中主要的是量化顺序的转变。$(\epsilon , 0)$-差分隐私保证了，对于所有运行的$M(x)$机制，观察到的输出结果（几乎）等同于观察到的每一个相邻数据库的输出结果。与此相对应$(\epsilon , \delta)$-差分隐私则是对于所有相邻的数据库$x$和$y$，它是完全不同的，观察到的$M(x)$的输出，$x$和$y$数据库是非常相似或几乎不同。然而，给定一个输出$\xi \sim M(x)$
等式
$$ {\cal L}_{M(x)||M(y)}^{(\xi)}=ln\{ \frac{Pr[M(x)=\xi] }{Pr[M(y)=\xi]}\}$$
对我们来说很重要；我们提及它是因为隐私损失是由观察的$\xi$导致的。这种损失可能是积极的也可能是消极的。正如我们在引理3.17看到的，$(\epsilon , \delta)$-差分隐私保证了对于所有相邻的$x$和$y$，隐私损失的绝对值的边界将以至少$1-\delta$概率限制在$\epsilon$。通常，概率空间是基于机制$M$的随机化。
差分隐私不受后处理的影响：一个数据分析者，如果没有有关隐私数据库的额外信息，他将不能计算出隐私算法$M$输出的结果并且让差分隐私性降低。即，如果一个算法保护个体的隐私，那么数据分析者——既在正式的定义下也甚至在直觉上——仅仅站在一旁思考算法的输出，不能增加隐私损耗。具有$(\epsilon , \delta)$-差分隐私的算法$M$与一个数据独立的映射$f$的复合也满足$(\epsilon , \delta)-$差分隐私
命题 2.1（后处理） $M ：\mathbb N \longrightarrow R$ 为一个随机化的算法，满足$(\epsilon , \delta)$-差分隐私。$f ：R \longrightarrow R'$ 是任意一个随机化映射。则$f \circ M : \mathbb N \longrightarrow R'$ 满足$(\epsilon , \delta)$-差分隐私。
证明，对于一个确定性的函数$f ：R \longrightarrow R'$，我们证明此命题。以上的结果是因为任意随机化的映射可以被分解为一些确定性函数组合的凸问题，一些差分隐私机制组合的凸问题也满足差分隐私。
设任意相邻的数据库$x,y$ 且 $ ||x-y|| _{1} \leq 1$，任意事件$S \subseteq R'$。令$T = \{ r \in R : f(r) \in S \}$。然后有，
$$Pr[f(M(x)) \in S] = Pr[M(x) \in T]$$ $$\qquad\qquad\qquad\qquad\qquad\qquad \le exp(\epsilon)Pr[M(y) \in T]+ \delta$$ $$\qquad\qquad\qquad\qquad\qquad\qquad\quad\le exp(\epsilon)Pr[f(M(y)) \in T]+ \delta$$
这就是我们想要的。
它遵循了定义3.4，$(\epsilon , \delta)$-差分隐私包含了一种明确的方式：两个$(\epsilon , 0)$-差分隐私的机制的复合满足$(2\epsilon , \delta)$-差分隐私。更加一般地（定理 3.16），“$\epsilon$和$\delta累加$”：$k$个差分隐私机制的组合满足$(\sum _{i} \epsilon _{i} ,\sum _{i} \delta _{i})$-差分隐私，其中对于$1 \leq i \leq k$,第$i$个差分隐私机制满足$(\epsilon _{i} , \delta_{i})$-差分隐私，
对于$(\epsilon , 0)$-差分隐私的机制的组隐私也遵循定义2.4，它随着组规模的增大，隐私保护的强度线性减小。
定义 2.2 任意$(\epsilon , 0)$-差分隐私机制$M$，组大小为k的组满足任意$(k\epsilon , 0)$-差分隐私。即，对于所有的$||x - y||_{1} \leq k$且$S \subseteq Range(M)$
$$Pr[M(x)\in S]\le exp(k\epsilon) \ Pr[M(y)\in S] $$
例如，处理调查中包含多个家庭成员的相关隐私的问题。
一般地，复合和组隐私是不相同的，一种改进的复合在3.5.2中定义（定理 3.20），它从本质上改善了因子$k$，即使当$\delta = 0$，对于组隐私，它也不会产生相同的结果。
2.3.1 差分隐私所承诺的
一个经济学的观点。 差分隐私所承诺的是保护个体不受任何因为个体的数据存在于私有数据库而面临的伤害，而当个体的数据不存在于数据库中就不会不存在的额外伤害。虽然一旦差分隐私机制$M$的结果$M(x)$被发布，个体可能会受到伤害，但差分隐私保证受到伤害的可能性不会因为个体数据的加入而显著增加。这是一种非常实用的隐私定义，因为当一个个体正在决定是否要将个人数据添加到一个将会使用差分隐私保护的方式的数据库中，她所考虑的恰恰是这种差异：她参与后受到伤害的可能性与她不参与受到伤害的可能性。她不能控制数据库中所保留的内容。而给定差分隐私的承诺，她将确信：以未来是否会受到伤害来看，是否自己的数据参与其中几乎没有差别。给任意的激励——从利他主义到金钱的奖励——对于允许她的数据被使用，差分隐私可能会为她提供一些便利。这种直觉能够用一种实用理论的概念来形式化，我们将在此简单概括。
考虑一个个体$i$,它具有基于所有可能的未来事件的任意预设值，所有可能的未来事件用$A$来表示。这些预设值可以用一个功能函数$u_{i}$来表示：$A \longrightarrow \mathbb R_{\ge 0}$，我们说在事件$a \in A$中，个体i经历了$u_{i}(a)$。假设$x \in \mathbb N _{|\chi|}$是一个包含$i$的隐私数据的数据库，$M$是一个满足$\epsilon$-差分隐私的算法。$y$为一个不包含$i$且与$x$相邻的数据库（$||x-y||_{1} = 1$）,$f：Range(M) \longrightarrow \Delta(A)$为任意一个未来事件$A$的分布函数，其中机制M的输出为条件。通过差分隐私的保证，以及命题2.1中的任意后处理的保证，我们有：
$$\mathbb E_{a \sim f(M(x))}[u_{i}(a)] = \sum _{a \in A} u_{i}(a) Pr _{f(M(x))} [a] $$
$$\qquad\qquad\qquad\qquad\qquad \le \sum _{a \in A} u_{i}(a) exp(\epsilon) Pr _{f(M(y))} [a]$$
$$\qquad\qquad\qquad\qquad = exp(\epsilon)\mathbb E_{a \sim f(M(y))}[u_{i}(a)]$$
类似地，
$$\mathbb E_{a \sim f(M(x))}[u_{i}(a)] \ge exp(- \epsilon)\mathbb E_{a \sim f(M(y))}[u_{i}(a)]$$
因此，通过承诺$\epsilon$-差分隐私，一个数据分析者可以承诺一个个体未来所受到的损害不会超过$exp(\epsilon) \approx (1 + \epsilon )$ 。注意，这种承诺是独立于个体$i$的功能函数$u_{i}$,同时适用于具有多个功能函数的个体。
2.3.2 差分隐私所不能保证的
正如我们在抽烟导致癌症的例子中所看到的，虽然差分隐私是一种非常强的隐私保护，但是它并不能说是绝对的因此而不受到伤害。它也不会创造之前并不存在的隐私。更一般地，差分隐私不能保证人们认为自己的秘密一直保密。它仅仅能够确保在一项调查中个人的参与不会被公开，参与也不会导致任何由某个个体对于调查结果的影响的公开。来自调查结果的结论很有可能反映的是有关个体的统计信息。一项旨在发现一种特殊疾病早期指标的健康类调查可能会产生很强的，甚至是具有结论性的结果；这些适用于给定个体的结论并不是差分隐私违例的证据；个体可能甚至没有参加该项调查（差分隐私确保的是对于个体是否参加某项调查的可能性类似的结论不会产生）。特别地，如果调查告诉了我们特定的私有属性与公开的可以观察到的属性具有很强的相关性，这也不是差分隐私违例，因为这种相同的相关性可以以几乎相同的概率观测到，它与任意应答者存在或不存在是相互独立的。
__差分隐私的性质上的属性__已经引入并且定义了差分隐私，我们概况它的一些重要的性质。
1. 抵御任意风险的保护，而不仅仅是抵御重识别的保护。
2. 自动的链接攻击的中和，包括所有使用过去、现在和未来数据库以及其它背景信息形式和信息源的尝试。
3. 隐私损失的量化。差分隐私并不是一个二元的概念，它有衡量隐私损失的方式。这允许在不同的技术中进行比较：设定差分隐私损失的边界，哪一种方式会有更好的准确性？设定准确性，哪一种方式会提供更好的隐私性？
4. 复合。或许最关键地，损失的量化运行基于并行计算进行分析和隐私损失累积控制。理解复合下的差分隐私机制的行为能够使从简单的差分隐私的构建中设计和分析复杂的差分隐私算法。
5. 组隐私。差分隐私允许有关组（如家族）的分析和隐私损失累积。
6. 阻止后处理。后处理对于差分隐私是无效的：如果没有附加的有关私有数据库的相关信息，一个数据分析者就不能计算出差分隐私算法$M$输出的结果，他也不能让数据库降低差分隐私性。也就是说，一个数据分析者，无论拥有什么样的附加信息，仅仅是坐在角落思考算法的输出，在定义上或直觉上都不能增加隐私损失，
这些是差分隐私标志性的属性。我们能够逆向证明？也就是说，这些属性或它们的子集暗指差分隐私？差分隐私在这些方面被削弱并且仍有意义？这些是开放性的问题。
2.3.3 关于定义最后的注解
隐私的粒度。
所有小的$\epsilon$是类似的。
一些额外的形式。
注解 2.1。 当处理实数值时，必须格外小心，如拉普拉斯机制，那是由于浮点数实现的微妙。否则，差分隐私将被摧毁，这是因为在数据库$x$以非零概率输出，而在相邻数据库$y$由于舍入以零概率输出。在差分隐私的环境中，这仅仅是浮点数实现要求仔细检查的一种情况，并且不是唯一的一种。
2.4 相关文献说明
差分隐私的定义是由Dwork等人提出[23]；在本文所使用的准确的公式是在[20]中出现，是由Dwork和McSherry提出。术语“差分隐私”是由Michael Schroeder所创造。语义上的安全性的不可实现是由Dwork和Naor提出[25]。对于$(\epsilon , 0)$-差分隐私机制的组合和组隐私性质在[23]首次提出。对于$(\epsilon , \delta)$-差分隐私机制的组合性质是在[21]中首次提出（但我们所看到的附录B中的相关证明，是由Dwork和Lei给出[22]）。对于浮点数的不恰当实现，差分隐私所表现出的不足是由Mironov发现，他在[63]中提出了一种优化方案。
声明：本文是对“The Algorithmic Foundations of Differential Privacy”相关章节的翻译，原书可在相关的网站中获取。本文由我独立翻译完成，只用于学习和交流，因此翻译的所有内容，禁止用于任何商业用途。由于本人的英文水平以及差分隐私相关知识有限，难免有翻译不恰当的地方，欢迎各位指正。个人邮箱：alants56@163.com