차등 정보보호(Differential Privacy)는 데이터셋에 포함된 특정 개인의 정보 유무가 분석 결과에 미치는 영향을 제한하여 개인의 프라이버시를 수학적으로 보장하는 강력한 기술입니다. 이는 질의 결과에 의도적인 '노이즈'를 추가함으로써 달성됩니다. 이때 추가되는 노이즈의 양을 결정하는 핵심 개념이 바로 전역 민감도(Global Sensitivity)입니다.
차등 정보보호와 전역 민감도의 정의
차등 정보보호(ε-Differential Privacy)는 알고리즘 $M$이 비슷한 두 데이터베이스(단 한 명의 개인 정보만 차이 나는)에 대해 거의 동일한 결과를 출력하도록 보장하는 개념입니다. 수학적으로는 다음과 같이 정의됩니다.
Pr[M(D) \in S] \le e^\epsilon \cdot Pr[M(D') \in S]
$$
여기서 $D$와 $D'$는 이웃 데이터베이스, $S$는 가능한 출력 결과의 집합, 그리고 ε(엡실론)은 프라이버시 손실(privacy loss)을 나타내는 매개변수입니다. ε 값이 0에 가까울수록 프라이버시 보호 수준이 높아집니다.
전역 민감도($\Delta f$)는 질의 함수 $f$가 이웃 데이터베이스에 적용될 때 나타날 수 있는 결과값의 최대 변화량을 의미합니다. 이는 데이터셋 자체와는 무관하게 오직 질의 함수에 의해서만 결정됩니다.
\Delta f = \max_{D, D'} \|f(D) - f(D')\|_1
$$
전역 민감도는 차등 정보보호를 구현하기 위해 추가해야 할 노이즈의 크기를 결정하는 데 핵심적인 역할을 합니다.
전역 민감도 적용 사례: 질병 보유자 수 계산
특정 질병(예: 당뇨병)을 앓고 있는 환자 수를 계산하는 간단한 시나리오를 통해 전역 민감도를 구체적으로 살펴보겠습니다.
- 데이터베이스 ($D$): 병원의 환자 기록 목록
- 질의 함수 ($f$): 데이터베이스에서 '당뇨병' 진단을 받은 환자의 수를 계산하는 함수 (COUNT 질의)
이 질의 함수의 전역 민감도를 계산해 보겠습니다. 데이터베이스 $D$와 여기서 한 명의 환자 기록이 추가되거나 삭제된 이웃 데이터베이스 $D'$를 가정합니다.
- 환자 추가:
- 만약 새로 추가된 환자가 당뇨병 환자라면, 질의 결과는 1 증가합니다.
- $f(D')=f(D)+1$
- 당뇨병 환자가 아니라면 결과는 변하지 않습니다.
- $f(D')=f(D)$
- 환자 제거:
- 만약 제거된 환자가 당뇨병 환자였다면, 질의 결과는 1 감소합니다.
- $f(D')=f(D)−1$
- 당뇨병 환자가 아니었다면 결과는 그대로입니다.
- $f(D')=f(D)$
두 경우 모두 질의 결과값의 최대 변화량은 1입니다. 따라서 이 COUNT 질의의 전역 민감도($\Delta f$)는 1이 됩니다.
프라이버시 손실 관계 수식 유도
이제 위 사례에 라플라스 메커니즘(Laplace Mechanism)을 적용하여 프라이버시 손실 관계를 도출해 보겠습니다. 라플라스 메커니즘은 질의 결과값에 라플라스 분포를 따르는 노이즈를 추가하여 차등 정보보호를 만족시키는 가장 일반적인 방법입니다.
알고리즘 $M$은 실제 질의 결과 $f(D)$에 스케일 $b$를 가지는 라플라스 노이즈를 추가하여 최종 결과를 반환합니다.
M(D)=f(D)+Laplace(b)
$$
이때, 라플라스 노이즈의 확률 밀도 함수(PDF)는 다음과 같습니다.
pdf(x|b) = \frac{1}{2b} exp\left(− \frac{|x|}{b}\right)
$$
알고리즘 $M$이 특정 결과 $k$를 출력할 확률의 비율을 계산하여 프라이버시 손실 관계를 유도할 수 있습니다.
\frac{Pr[M(D)=k]}{Pr[M(D')=k]}
= \frac{\frac{1}{2b} exp\left(−\frac{|k-f(D)|}{b}\right)}{\frac{1}{2b} exp\left(−\frac{|k-f(D')|}{b}\right)}
= exp\left(\frac{|k-f(D')|-|k-f(D)|}{b}\right)
$$
삼각 부등식($|x|−|y| \le |x−y|$)에 따라 위 식의 지수 부분은 다음과 같이 제한됩니다.
|k-f(D')|-|k-f(D)| \le |(k-f(D')) - (k-f(D))| = |f(D) - f(D')|
$$
전역 민감도의 정의($|f(D)−f(D')| \le \Delta f$)를 적용하면, 확률의 비율은 다음과 같은 상한을 가집니다.
\frac{Pr[M(D)=k]}{Pr[M(D')=k]} \le exp\left(\frac{\Delta f}{b}\right)
$$
ε-차등 정보보호를 만족시키기 위해 상한을 ε 값으로 정합니다.
\frac{\Delta f}{b} = \epsilon
$$
이로부터 라플라스 노이즈의 확률 밀도 함수에서 스케일 $b$와 프라이버시 손실을 나타내는 매개변수 ε 간의 관계식을 얻을 수 있습니다.
b = \frac{\Delta f}{\epsilon}
$$
결론적으로, 전역 민감도가 1인 COUNT 질의에 스케일 $b$가
b = \frac{1}{\epsilon}
$$
인 라플라스 노이즈를 추가하면, 특정 개인의 데이터 포함 여부가 최종 결과에 미치는 영향이 $e^{\epsilon}$ 배를 넘지 않도록 보장하여 개인의 프라이버시를 효과적으로 보호할 수 있습니다.
댓글
댓글 쓰기