/images/img/definition.png

差分隐私(DP,Differential Privacy)最早由微软科学家Cynthia Dwork提出。差分隐私通过添加随机噪声对原始数据进行扰动,在扰动过程中保证数据的统计不变性。差分隐私作为一种严谨而有效的隐私保护机制,使攻击者即使攻击者拥有最大背景知识也无法识别单条记录是否在原数据表中。差分隐私研究的核心问题是如何高效地兼顾安全性(Privacy-Preserve)和结果可用性(utility)。

/images/DP2006.png

本地差分隐私(LDP,Local Differential Privacy)是一种新兴的差分隐私保护模型,它将数据扰动过程从服务器端转移到用户端。用户将扰动过后的数据发送至数据收集者(Aggregator),之后数据收集者进行聚合查询。LDP 不仅保护了用户的隐私,也避免了数据收集者意外泄露用户真实数据的情况,即 LDP同时保护了数据收集者.LDP被互联网公司广泛采用,比如谷歌的chrome浏览器,苹果的safari浏览器,微软的windows操作系统和小米的MIUI等。

CDP和LDP对比
CDP LDP
是否必须有可信第三方
查询的数据 相邻数据集 其中两条记录

传统的差分隐私技术将原始数据集中到一个数据中心, 然后发布满足差分隐私的相关统计信息, 我们称其为中心化差分隐私(CDP,Centralized Differential Privacy)技术.因此, 中心化差分隐私对于敏感信息的保护始终基于一个前提假设:可信的第三方数据收集者, 即保证第三方数据收集者不会窃取或泄露用户的敏感信息.而在 LDP 中,数据管理员是不可信的,数据收集过程是关注的重点。

差分隐私技术具有序列组合性和并行组合性两种特性,CDP都具有这两种特性,LDP只有线性组合性。

/images/img/20220302003000.png

/images/laplace.png
  • 拉普拉斯分布
  • 分布函数: $\Pr(\eta =x)=\frac{1}{2\lambda } e^{\frac{{-\left \vert x \right \vert } }{\lambda }} =Lap(\eta )$
  • 期望:一般为0
  • 方差:$2\eta^{2}$

全局敏感度: $$ S(F)=\max_{D,D’} \Vert F(D)-F(D^\prime)\Vert_{1} $$

证明:

$$ \begin{align} \frac{\Pr[A({\color{Blue} D} ) = O]}{\Pr[A({\color{Red}{D^{\prime}}}) = O]} & = \frac{\Pr[q({\color{Blue} D} )+\eta = O]}{\Pr[q({\color{Red} D^{\prime}} )+\eta = O]} \\ & = \frac{\frac{e^{\left | O-q(D) \right | }}{\lambda } }{\frac{e^{\left | O-q(D^{\prime}) \right | }}{\lambda } } \\ & \leq e^{\frac{{\left | q(D)-q(D^{\prime}) \right | } }{\lambda } } \leq e^{\frac{S(q)}{\lambda } }=e^{\epsilon } \end{align} $$

定理: 令函数$𝐹$的敏感度$𝑆(𝐹)$, 算法$A(D) = F(D) + Lap(∆𝑓/ε)$ 保证ε-差分隐私

  • $𝐹$的值域为$\omega$
  • $𝐷$为查询数据集
  • 随机采样某一个输出结果:$\omega \in \Omega $
  • 用户自定义一个评分函数:$u(D,\omega )$,用于评价$\omega$的效用,$𝑢$越大,$\omega$效用越大
  • 随机输出$\omega$的概率$\propto e^{(\frac{u(D,\omega )}{2\Delta{u}})}$

敏感度定义: $$S_{u}=\max_{\begin{array}{c}\omega \in \Omega \\D,D^{\prime }:\Vert D-D^{\prime }\Vert_{1} \leq 1 \end{array}}\left \vert u({\color{Blue} D} ,\omega)-u({\color{Red} D^{\prime}} ,\omega) \right \vert $$

定理: 指数机制满足${\epsilon}$-差分隐私,要求评分函数$u(D,\omega )$的敏感度满足条件:$\Delta{u}\geq \frac{S(u)}{\epsilon}$

[1] 本地化差分隐私综述-叶青青等 [LDP] [pdf]

[2] 差分隐私保护及其应用

[1] FengHZ’s Blog

[1] 差分隐私之Composition Theorem(一)

[2] 差分隐私概念介绍

[3] 差分隐私:原理、应用与展望 [video]

[4] 20200817差分隐私叶青青孙林 [video]

[5] 20200817差分隐私张啸剑 [video]