Differential Privacy (4. Definition, basic mechanisms)
본문은 James Honaker과 Salil Vadhan의 Computer Science 208: Applied Privacy for Data Science 강의의 Definition, basic mechanisms와 Dwork의 The Algorithmic Foundations of Differential Privacy를 요약한 글입니다.
앞서 Membership Attack과 Reconstruction Attack에 대해 배웠습니다. 각 시나리오에서 ‘data set에 들어가는지’를 Alice의 민감 정보로 생각해 들어가면 1, 들어가지 않으면 0인 sensitive bit를 만들 수 있습니다. 즉, Membership attack과 Reconstruction attack간의 관계가 있음을 알 수 있습니다.
Differential Privacy
DP는 Utility와 Privacy, 두가지 목적을 가지고 있습니다. Utility는 dataset을 이용해 통계적인 해석이 가능한가로 정의가 되며, Privacy는 individual-level의 데이터를 보호할 수 있는지에 대해서 정의가 됩니다.
Differential Privacy의 시나리오는 다음과 같습니다:
(신뢰할 수 있는 서버에) 데이터 베이스가 있고, data analyst는 데이터베이스에 접근할 수 없습니다. 다만 서버에 질의를 하면 메커니즘을 통해 통계값만 얻을 수 있습니다. 여기서 data analyst가 공격자로 변경되었을 때, 메커니즘을 통한 통계값으로 데이터를 추론할 수 없도록 하는 것이 DP의 목표입니다.
데이터베이스에 존재하는 임의의 개별 데이터를 추론할 수 없게 하기 위해서는 임의의 한 데이터가 변경되거나 제거되어도 통계값에 차이가 없어야 합니다. 이렇게 만들기 위해서는 공격자의 질의에 대한 답변에 ‘random noise’를 추가할 수 있습니다. 즉, 메커니즘은 ‘randomized mechanism’이라고 쓸 수 있으며, 단 하나의 row만 다른 두 데이터베이스 D와 D’이 있다고 할 때 임의의 쿼리(질의, q)에 대해 두 메커니즘 M(D,q)와 M(D’,q)의 분포는 𝜀 수준으로 동일해야 합니다(여기서는 질의를 단 한번 하는 상황을 가정하고 있습니다). 이를 수식으로 나타내면 다음과 같습니다.
1+𝜀는 𝜀이 작을 때 e^𝜀로 근사할 수 있으며, 0보다 클 때는 항상 1+𝜀<e^𝜀가 성립합니다. 이 성질을 이용해 𝜀-DP를 다음과 같이 정의할 수 있습니다.
다음으로 randomized mechanism에 추가하는 random noise는 어느정도 수준이어야 할까요? 결과값의 변화를 숨기기 위해서는 하나의 데이터가 바뀌었을 때 가장 많이 변화하는 정도(∆)의 노이즈를 추가해야 합니다. 이 ∆를 global sensitivity라고 하며, 다음과 같이 정의합니다.
데이터를 𝜀수준으로 보호하기 위해서는 노이즈는 𝜀에 대한 함수로 나타나게 될 것입니다. 즉, 질의에 대한 답에 추가하는 노이즈는 𝜀와 sensitivity에 관한 함수로 나타나게 될 것입니다.
Laplace Mechanism
마지막으로, 추가하는 노이즈의 분포는 어떻게 될까요? 다양한 분포가 존재할 수 있겠지만 가장 흔하게 사용되는 분포는 라플라스 분포입니다.
라플라스 분포 Lap(μ,b)의 그래프는 다음과 같습니다.
여기서 μ는 평균, b는 scale parameter로, 노이즈를 추가할 때 μ는 0이어야 합니다. 따라서 Lap(μ,b)대신 Lap(b)으로 사용합니다.
Lap(b)의 density function은 다음과 같습니다.
표준편차는 다음과 같습니다.
질의의 결과값에 라플라스 분포를 따르는 노이즈를 더하는 매커니즘을 라플라스 매커니즘이라고 합니다. 잘 알려진 정리로, 질의 q에 대한 Laplace Mechanism
는 𝜀-DP가 성립합니다.
이에 대한 증명은 다음과 같습니다.
