差分隱私 -- Laplace mechanism、Gaussian mechanism、Composition theorem

作者：由天下客發表于攝影時間：2021-10-26

1。 Differential Privacy （DP）

定義演算法

$\mathcal{M}:\mathcal{D\rightarrow R}$

，其中

$\mathcal{D}$

為資料取值域，

$\mathcal{R}$

為因變數範圍域，如果想要該機制想要滿足

$(\epsilon,\delta)$

-差分隱私，則需要對任意兩個相鄰輸入

$d,d^{$

，對於輸出

$S\subseteq \mathcal{R}$

的任意子集都滿足：

$Pr[\mathcal{M}(d)\in S] \le e^{\epsilon}Pr[\mathcal{M}(d^{$

DP的目的

：希望

$Pr[\mathcal{M}(d)\in S] = Pr[\mathcal{M}(d^{$

，演算法從隱私保護角度是完美的（理想情況下），因為實現了對

$d,d^{$

的完美遮蔽。攻擊者無法從輸出的公共資料

回推真實資料

$d,d^{$

。

#FormatImgID_12# -差分隱私

：在一定程度上放鬆了 DP 的嚴格定義（鬆弛的差分隱私），其允許 DP 演算法以機率

$\delta$

（最好小於

）的機率被打破。

2。 Gaussian/Laplace mechanism

2。1 Laplace mechanism

Laplace 分佈

是統計學中的概念，是一種連續的機率分佈。如果隨機變數的機率密度函式分佈為：

$f(x|\mu,b)=\frac{1}{2b}\exp (-\frac{|x-\mu|}{b})=\frac{1}{2b}\begin{cases} \exp(- \frac{\mu-x}{b}) & x < \mu \\ \exp(- \frac{x-\mu}{b}) & x \ge \mu \end{cases}\\$

那麼它就是拉普拉斯分佈。其中，

$\mu$

是位置引數，

是尺度引數。

由於資料集中少一條記錄就會對資料查詢

的結果結果造成一定的影響，因此需要定義一個新的概念來確定影響程度的大小，在這裡使用敏感度（sensitivity）：

-sensitivity： The

-sensitivity of a function

$f:\mathbb{N}^{|\mathcal{X}|}\rightarrow\mathbb{R}^k$

is：

$\triangle f = \max \limits_{x,y\in\mathbb{N}^{|\mathcal{X}|}, ||x-y||_1=1} ||f(x)-f(y)||_1\\$

有了

$\triangle f$

之後，自然想

$\triangle f$

越大，噪聲應該越大，

$\triangle f$

越小，噪聲應該越小。

拉普拉斯機制：給定查詢函式

$f:\mathbb{N}^{|\mathcal{X}|}\rightarrow\mathbb{R}^k$

，滿足隱私預算為

$\epsilon$

且查詢因變數為

的拉普拉斯機制可以表示為：

$\mathcal{M}_L(x, f(\cdot),\epsilon) = f(x) + (Y_1, Y_2, ..., Y_k)\\$

其中，

是獨立同分布的變數，為

$Lap(0,\frac{\Delta f}{\epsilon})$

，表示對查詢結果注入的噪聲。

定義- 噪聲

$Y \sim L(0,\frac{\Delta f}{\epsilon})$

滿足

$(\epsilon,0)-differential\;privacy$

。

$\Delta f$

表示敏感度，

$\epsilon$

表示隱私預算。可以看到，隱私預算越小，噪聲越大，結果可用性越小，隱私保護越好。

假設

表示

$\mathcal{M}_L(x,f,\epsilon)$

的 pdf，

表示

$\mathcal{M}_L(y,f,\epsilon)$

的pdf；

對於某個輸出

，只要約束

${MaxDivergence}\leq\epsilon$

：

首先根據

$Lap(0,\frac{\Delta f}{\epsilon})$

可得 Laplace 分佈為：

$f(x|\mu,b)=\frac{\epsilon}{2\Delta f}\exp (-\frac{|x|\epsilon}{\Delta f})$

。

基於此：

$\begin{align} \frac{p_x(z)}{p_y(z)} &= \prod_{i=1}^{k} \frac{\exp(-\frac{\epsilon |f(x)_i-z_i|}{\triangle f})}{\exp(-\frac{\epsilon |f(y)_i-z_i|}{\triangle f})}\\ &= \prod_{i=1}^{k} \exp{\frac{\epsilon(|f(y)_i-z_i|-|f(x)_i-z_i|)}{\triangle f}}\\ &\le \prod_{i=1}^{k}\exp(\frac{\epsilon(|f(x)_i-f(y)_i|)}{\triangle f})\\ &=\exp(\frac{\epsilon \cdot ||f(x)-f(y)||_1}{\triangle f})\\ &\le \exp(\epsilon) \end{align}\\$

Line 1：根據

$\mathcal{M}_L(x, f(\cdot),\epsilon) = f(x) + (Y_1, Y_2, ..., Y_k)$

化簡為

，使其可以寫成拉普拉斯分佈的形式進行後續的化簡

Line 2：簡單化簡

Line 3：應用絕對值三角不等式

Line 4：1 範數

Line 5：應用敏感度概念進行化簡得到結果，證明滿足

$(\epsilon,0)$

-DP。

2。2 Gaussian mechanism

Laplace 機制提供的是嚴格的

$(\epsilon,0)$

-DP，高斯機制則提供的是鬆弛的

$(\epsilon,\delta)$

-DP。

${\displaystyle f(x)={\frac {1}{\sigma {\sqrt {2\pi }}}}\;e^{-{\frac {\left(x-\mu \right)^{2}}{2\sigma ^{2}}}}\!}\\$

正態分佈的期望值等於位置引數，決定了分佈的位置；其方差

$\sigma ^{2}$

的開平方或標準差

$\sigma$

等於尺度引數，決定了分佈的幅度。

對於任意的

$\epsilon\in(0,1),\delta\ge\frac{e^{-(\sigma\epsilon)^2/2}}{1.25}$

，有噪聲

$Y \sim \mathcal{N}(0,{\Delta f}^2\sigma^2)$

滿足

$(\epsilon,\delta)$

-DP：

$Pr[\mathcal{M}(d)\in S] \le e^{\epsilon}Pr[\mathcal{M}(d^{$

其中，

$\mathcal{M} \mathop{=}^{\triangle}\mathcal{M}_G(x, f(\cdot),\epsilon) = f(x) + (Y_1, Y_2, ..., Y_k)$

，這裡形式與 Laplace 機制相似不過注入的噪聲為高斯噪聲。高斯機制的定義明顯比 Laplace 複雜，主要有三個引數：

高斯分佈的標準差

$\sigma$

，決定噪聲的尺度；

$\epsilon$

表示隱私預算，和噪聲成負相關；

$\delta$

表示鬆弛項，比如設定為

$10^{-5}$

，就表示只能容忍

$10^{-5}$

的機率違反嚴格差分隱私。

$Y \sim \mathcal{N}(0,{\Delta f}^2\sigma^2)$

，

$f(x)={\frac {1}{\sigma {\sqrt {2\pi }}}}\;e^{-{\frac {\left(x-\mu \right)^{2}}{2\sigma ^{2}}}}\!$

高斯機制部分證明如下，

表示準守嚴格 DP 的部分，

表示違反嚴格 DP 的部分

在鬆弛差分隱私中，輸出分為兩部分，一部分是嚴格遵守 DP，另一部分是違反 DP 的。

因此需要將輸出集合分隔成兩部分，證明第一部分是被

$\epsilon$

約束住，而第二部分小於

$\delta$

。

$\begin{align*} \mathop{Pr}_{x\sim \mathcal{N}(0,\sigma^2)}[f(x)+x\in S] = \mathop{Pr}_{x\sim \mathcal{N}(0,\sigma^2)}[f(x)+x \in S_1]\\+\mathop{Pr}_{x \sim \mathcal{N}(0,\sigma^2)}[f(x)+x \in S_2]\\ \le \mathop{Pr}_{x \sim \mathcal{N}(0,\sigma^2)}[f(x)+x \in S_1] + \delta \\ \le e^{\epsilon}(\mathop{Pr}_{x \sim \mathcal{N}(0,\sigma^2)}[f(y)+x \in S_1] + \delta) \end{align*}\\$

3。 Composition Theorem

Composition Theorem 直接翻譯的話就是組成原理，目的就是將一系列滿足差分隱私的模組（查詢）組合在一起，並且保證整體仍然滿足差分隱私。

例如，對一個簡單的神經網路，如果將每個神經元計算梯度看成一個查詢

$\nabla f : D\rightarrow g$

，輸入是資料集

，輸出是梯度

。Composition Theorem（組成原理）研究整個神經網路滿足怎樣的差分隱私。主要包括兩個部分的內容：

Basic Composition Theorem（基本組成原理），不考慮查詢函式之間的關聯性（查詢相互獨立）

並行組成

不相交資料集，不同查詢

序列組成

同一資料集，不同查詢

Advanced Composition（高階組成原理），就是考慮查詢函式之間的關聯性。

Naive Composition Theorem

Strong Composition Theorem

Moment Account

3。1 Basic Composition Theorem

3。1。1 Sequential Composition 序列組合

序列組合簡單講就是同一資料集，不同查詢函式，在［PINQ］

［1］

中的定義是：：

其中

表示一個滿足

$\epsilon_i$

的差分隱私演算法，而

表示所有的演算法作用於同一個資料集

，那麼這些演算法構成的集合滿足

$\sum_i\epsilon_i$

-DP。證明可參考［PINQ］

［1］

。

3。1。2 Parallel Composition 並行組合

並行組合簡單講就是不同資料集，不同查詢函式，在［PINQ］

［1］

中的定義是：：

其中

表示一個滿足

$\epsilon$

的差分隱私演算法，

表示互不相交的資料集，

$M_i(X\cap D_i)$

表示各個差分隱私演算法之間作用的資料集互不相交，那麼整體滿足

$\epsilon$

-DP。如果

滿足

$\epsilon_i$

的差分隱私演算法，那麼整體滿足

$\max \{{\epsilon_i}\}$

-DP。證明可參考［PINQ］

［1］

。

3。2 Advanced Composition 高階組成

考慮攻擊者可以自適應地影響資料庫以及對應的查詢機制，換句話說，

查詢與查詢之間存在關聯

，如下圖所示：

其中，

$\mathcal{M}$

表示一系列滿足差分隱私的查詢機制，數量為

；

$\mathcal{M}_i$

表示第

個查詢機制；

$\mathcal{A}$

表示攻擊者；

$D^{i,0},D^{i,1}$

表示兩個鄰接資料庫；

表示的是實驗的下標；

表示第

個查詢機制得到的結果。

最終的輸出結果可以用

（包含了所有的一系列滿足 DP 的查詢機制）進行表示：

其中

代表的是攻擊者

$\mathcal{A}$

隨機扔出的一個骰子，值可以是 0 或者 1，代表兩個實驗；其餘的

$Y_{1\sim k}$

表示的是

次查詢的結果。

這個輸出是一個多維的隨機變數，它有對應的分佈；目標是讓基於任意兩個鄰接資料集（只相差一個樣本）得到的兩個輸出變數之後，他們對應的分佈的差異應該儘可能接近，以至於攻擊者不知道用了哪個資料集。兩個分佈的差異稱為 Privacy Loss ，如果嚴格約束 Privacy Loss ，那麼就是

$\epsilon$

-DP；如果允許一定程度違背，就是

$(\epsilon,\delta)$

-DP。

3。2。1 Navie Composition Theorem

對於輸出

，只要約束

${MaxDivergence}\leq\epsilon$

：對於組合定理而言就是每一次查詢都要滿足隱私預算

$\epsilon$

（每次查詢彼此獨立）：

這是最簡單的組合機制，可以看到組合之後的

$\epsilon$

。證明內容可以參考［lecture］

［2］

，一個簡單的例子如下［DLDP］

［3］

。

$\sigma = \frac{\sqrt{2 \times \ln(1/10^{-5})}}{1.2}，\ln(1/10^{-5}) \approx 11.52\\$

3。2。2 Strong Composition Theorem

強組合原理的基本思想就是用很小的一點

$\delta$

換取很多的

$\epsilon$

。這裡的證明可以參考［Privacy Book］

［4］

中的

[Theorem 3.20]

。

這裡咋一看組合之後的

$\epsilon$

比 Navie Composition 的還多，但實際上當

$\epsilon=10^{-5}$

的時候，後面一項

$k\epsilon(e^{\epsilon}-1)$

近似等於0，這樣整體的

$\epsilon$

，相當於

$O(\sqrt{k})$

，相對於原來的

節省了更多的隱私預算。一個簡單的例子如下［DLDP］

［3］

：

3。2。3 Moments Accountant

這是在

Deep Learning with differential privacy

中提出來的方法，細節的證明可以參考

［5］

。它提出的方法就是在計算的梯度

$\nabla \mathcal{L}$

中加入噪聲，而重要的就是噪聲的大小，整篇文章的重點就是研究如何在滿足差分隱私的前提下加入噪聲。

差分隱私等價於約束兩個分佈的差異

兩個分佈的差異可以用

來衡量

$c(o) = \log\frac{\Pr[\mathcal{M}(aux,d) = o]}{\Pr[\mathcal{M}(aux,d^{$

這個差異

是一個滿足亞高斯分佈的隨機變數

考慮這個隨機變數的

$\log$

矩母函式 MGF

$\alpha_\mathcal{M}(\lambda;aux,d,d^{$

結合 Markov 不等式，推出矩母函式：

$\begin{align*}\mathop{\Pr}_{o \sim \mathcal{M}(d)}&[c(o)\ge \epsilon] \\&=\mathop{\Pr}_{o \sim \mathcal{M}(d)}[exp(\lambda c(o))\ge exp(\lambda \epsilon)] \\&\le \frac{\mathbb{E}_{o \sim \mathcal{M}(d)}[exp(\lambda c(o))]}{exp(\lambda\epsilon)} \\&\le exp(\alpha -\lambda\epsilon) \end{align*}\\$