DP-17. 가우시안 노이즈에서 프라이버시 손실 관계식 유도

프라이버시 손실 관계 수식 유도

차등 정보보호에서 가우시안 메커니즘이 (ε, δ)-DP를 만족할 때, 다음 파라미터들 간의 관계는 어떻게 될까요?

• $ε$: 프라이버시 손실 예산
• $δ$: ε-DP가 깨질 수 있는 확률 (프라이버시 손실 예산 초과 확률)
• $S$: L2-민감도 (인접한 두 데이터셋 $D_1$, $D_2$에 대한 질의 함수 $f$의 결과값 차이를 L2-놈으로 정의할 때 이들 사이의 최댓값)

$$S=\max_{D_1,D_2}||f(D_1)-f(D_2)||_2$$

• $σ$: 노이즈 표준편차

프라이버시 손실은 데이터셋 $D_1$와 $D_2$(하나의 레코드만 차이나는 인접 데이터셋)에 대한 질의 함수 $f$의 결과 $o$가 나올 확률의 비율로 정의됩니다. 여기에 로그 함수를 적용하여 확률 변수 $L$을 다음과 같이 정의합니다.

$$L(o)=\ln\left(\frac{P(M(D_1)=o)}{P(M(D_2)=o)}\right)$$

가우시안 메커니즘에서 $M(D) = f(D) + \mathcal{N}(0, \sigma^2)$이고, 쿼리 결과는 스칼라 값이라고 가정하겠습니다.

$$f(D_1​)=q_1​, \ f(D_2​)=q_2​$$

이때, 프라이버시 손실 $L$은 다음과 같이 계산됩니다.

$$
\begin{align*}
L(o) &= \ln\left(\frac{\exp(-\frac{(o-q_1)^2}{2\sigma^2})}{\exp(-\frac{(o-q_2)^2}{2\sigma^2})}\right) \\
       &=\frac{(o−q_2​)^2−(o−q_1​)^2}{2σ^2} \\
       ​&=\frac{2o(q_1​−q_2​)−(q_1^2​−q_2^2​)}{2σ^2}
\end{align*}
$$​

$o$는 $q_1$​에 노이즈 $z \sim \mathcal{N}(0, \sigma^2)$가 더해진 값이므로 $o=q_1​+z$로 치환하고, $s=q_1​−q_2$​ (이때 $|s|≤S$, $S$는 L2-민감도)라고 하면,

$$L=\frac{s^2+2sz}{2σ^2}​=\frac{s^2}{2σ^2}​+\frac{s}{σ^2}​z$$

가 됩니다. 여기서 $z$가 정규분포를 따르므로, $L$ 또한 정규분포를 따르는 확률 변수입니다.

• 평균: $E[L]=μ_L​=\frac{s^2}{2σ^2}$​
• 분산: $Var[L]={σ_L}^2​=(\frac{s}{σ^2}​)^2Var(z)=\frac{s^2​}{σ^4}σ^2=\frac{s^2}{σ^2}​$

즉, $L∼N(\frac{s^2}{2σ^2}​, \frac{s^2}{σ^2}​)$ 입니다.

(ε, δ)-DP의 정의는 프라이버시 손실이 ϵ을 초과할 확률이 δ보다 작거나 같아야 함을 의미합니다. 즉, $P(L>ϵ)≤δ$가 성립해야 합니다. 가장 엄격한 경계를 찾기 위해 $P(L>ϵ)=δ$로 설정하고, L을 표준화하여 표준정규분포 확률 변수 $Z \sim \mathcal{N}(0, 1)$로 변환합니다.

$$P(L>ϵ)=P\left(\frac{L-μ_L}{σ_L}>\frac{ϵ-μ_L}{σ_L}\right)=P\left(Z>\frac{ϵ-\frac{s^2}{2σ^2}}{\frac{|s|}{σ}}\right)=\delta$$

표준정규분포의 누적분포함수(CDF) $Φ$의 성질($P(Z>x)=1−Φ(x)$)을 이용하면,

$$1-Φ\left(\frac{ϵσ}{|s|}​−\frac{|s|}{2σ}\right)=δ$$

또 다른 성질($1−Φ(x)=Φ(−x)$)을 적용하면,

$$Φ\left(-\left(\frac{ϵσ}{|s|}​−\frac{|s|}{2σ}\right)\right)=Φ\left(\frac{|s|}{2σ}-\frac{ϵσ}{|s|}​\right)=δ$$

프라이버시 손실이 발생할 확률은 질의 결과값의 차이가 최대일 때, 즉 $|s|=S$일 때 가장 커지므로(worst-case), $|s|$를 $S$로 대체합니다.

이 관계를 정리하면 다음과 같은 최종 수식을 얻습니다.

$$δ=Φ\left(\frac{S}{2σ}​−\frac{ϵσ}{S}\right)$$

여기서 $Φ(x)=\frac{​1}{\sqrt{2π}}\int​_{−∞}^x​e^{−t^2/2}\,dt$ 입니다.

 

이 수식은 주어진 L2-민감도 $S$와 프라이버시 파라미터 $(\epsilon, \delta)$를 만족시키기 위해 필요한 노이즈의 크기 $σ$를 결정하는 핵심적인 관계를 나타냅니다.