核心思想
差分隐私的核心思想是对于任意两个相差一条记录的数据集 $ D $ 和 $ D' $(相邻数据集)以及任意输出 $ O $,要求添加了随机扰动的查询机制 $ M $(一般是一些统计信息的查询如均值、方差等)都能满足 $ e^{-\epsilon} \leq frac{P[M(D)=O]}{P[M(D')=0]} \leq e^{\epsilon} $,其中 $ P $ 是通过查询机制 $ M $ 获得输出 $ O $ 的概率。这意味着在数据集 $ D $ 中一条数据发生变化后通过 $ M $ 得到 $ O $ 的概率的变化会非常小,概率 $ P $ 的变化范围由公式中的 $ \epsilon $ 决定,此时称查询机制 $ M $ 满足 $ \epsilon - $ 差分隐私。
在差分隐私应用中通常需要程序员来设置 $ \epsilon $ 的值,所以对其的理解至关重要。
当参数 $ \epsilon $ 接近 0 时, $ e^{\epsilon} $ 接近 1,这意味着保密程度高。在普通情况下, $ \epsilon $ 越小,数据可用性越低;$ \epsilon $ 越大,隐私保护越弱,但查询结果可以更精确。
此外,差分隐私还具有可组合性,如果用保护程度分别为 $ \epsilon 1 $ 和 $ \epsilon 2 $ 的差分隐私来回应两个查询,则这两个查询的差分隐私性等同于保护程度 $ \epsilon 1 + \epsilon 2 $,而 $ \epsilon $ 越高则保护程度越弱,也就是说查询次数越多,隐私保护越弱,攻击者可以通过多次查询来分析结果的分布情况并从中推算真实数据。为了防止这种情况发生,差分隐私系统必须有一个隐私预算,就是为多个查询中使用的 $ \epsilon $ 的综合指定一个上限。
分类
根据存储位置可分为中心化差分隐私(Centralized Differential Privacy, CDP)和本地化差分隐私(Local Differential Privacy, LDP)。
根据交互方式分类可分为交互式和非交互式两种。
经典算法
拉普拉斯机制
对于数值型的查询结果,通常使用的方法是在查询结果中加入服从拉普拉斯分布的噪声,这种方法被称为拉普拉斯机制。
拉普拉斯分布的概率密度函数为 $ pdf(x) = \frac{1}{2 \lambda}e^{- \frac{\lvert x \rvert}{\lambda}} $,其概率密度函数图如下
根据差分隐私的理论,噪声参数 $ \lambda $ 取决于修改一条记录时查询结果总共改变多少,总共的最大改变成为这组查询的敏感度,例如对于数据库查询 SELECT 3 * COUNT(*) from D
,当数据库有一条数据改变时,返回的结果会改变 3,我们称这组查询的敏感度为 3。取 $ \lambda =\frac{\operatorname{sensitivity}}{\epsilon} $ 即能满足 $ \epsilon - $ 差分隐私
随机化回答机制
如果要发布的数据不是数值型,那么需要使用其他方法来引入噪声。
例如对于一个是非问题,每个参与者有 $ \frac{1}{6} $ 的概率说真话,有 $ \frac{5}{6} $ 的概率随机回答一个答案,即真假各占一半。假设有 60000 人按上面的规则进行了回复,其中有 28000 个是,32000 个否,可以知道每个人有 $ \frac{5}{6} $ 的概率给出假答案,即有 50000 个人给出假回复,其中约 25000 个假的是,25000 个假的否,据此可以推算出剩下的真实回复中约有 3000 个是和 7000 个否,即约有 70% 的人答案为否。
应用场景
差分隐私已在较多场景中得到了应用,如差分隐私数据库、差分隐私数据合成、差分隐私数据采集和差分隐私机器学习等