[Algorithmic Foundations] #1. Differential Privacy definition

Differential Privacy

통계값으로 데이터를 추론할 수 없도록 하는 것이 DP의 목표
익명화와 같은 기존 개인정보 보호 방법의 한계를 고려하여 대규모 데이터 세트에서 개인의 개인정보를 보호해야 하는 문제에 대응하기 위해 등장

Requirement: for all D, D’ differing on one row, and all q ∀ sets T,
Pr[M(D, q) ∈ T] ≲ (1+ε) ・ Pr[M(D’, q) ∈ T]

Definition 2.4 (Differential Privacy). A randomized algorithm M with domain \(\mathbb{N^{|\textrm{X}|}}\) is \((\varepsilon, \delta)\)-differentially private if for all \(\mathcal{S} \subseteq Range(\mathcal{M})\) and for all x, y \(\in \mathbb{N^{|\textrm{X}|}}\) such that \(\left| x-y \right|_1 \leq 1\):

\(Pr[\mathcal{M}(x) \in \mathcal{S}] \leq exp(\varepsilon) Pr[\mathcal{M}(y) \in \mathcal{S}] + \delta\)

the simpler case where \(\delta\) = 0

\(exp(-\epsilon) \leq \frac{Pr[M(x) = r]}{Pr[M(y) = r]} \leq exp(\epsilon)\)

DP는 데이터 집합을 분석할 때 강력한 개인정보 보호를 보장하기 위해 개발됨
한 개인의 데이터를 추가하거나 제거해도 분석 결과에 큰 영향을 미치지 않아야 데이터 세트에 포함된 개인의 개인정보를 보호할 수 있음

M: (Randomized algorithm) 프로세스에서 무작위화를 사용하는 알고리즘. 데이터 세트를 입력으로 받아 분석에 사용되는 출력을 생성함

X: 데이터 유형의 세계 또는 데이터 요소가 취할 수 있는 모든 가능한 값의 집합
(e.g., medical dataset, X could include 나이, 혈압, 콜레스테롤 수치)
the universe of data types or the sets of all possible values that a data element can take
|X|: set X의 크기, 다양한 데이터 유형 또는 속성의 수
N: 자연수 집합, dataset의 각 요소에 대해 가능한 개수 또는 수량의 범위
\(N^{|\textrm{X}|}\): (Domain) 알고리즘이 처리할 수 있는 모든 데이터 세트의 집합
S ⊆ Range(M): 알고리즘 M에서 가능한 모든 출력의 하위 집합, 알고리즘 출력을 분석할 때의 모든 (잠재적) 결과 집합
x, y \(\in \mathbb{N^{|\textrm{X}|}}\) such that \(\left| x-y \right|_1 \leq 1\): 도메인 내 두 데이터 세트 x, y, 두 데이터 세트의 차이 (measured in the \(L_1\) norm), 데이터 세트가 하나의 데이터를 제외하고는 동일
\(L_1\) norm: 맨해튼 거리(Manhattan distance) or 택시 규범(Taxicab geometry)이라 함, 해당 구성 요소의 절대 차이의 합

algorithm M이 dataset x에서 실행될 때, 집합 S에서 결과를 생성할 확률이 dataset y에서 실행될 때 M이 집합 S에서 결과를 생성할 확률과 크게 다르지 않아야 함

ε (epsilon): 프라이버시 손실을 측정하는 음수가 아닌 매개변수(parameter), 출력 확률이 얼마나 다를 수 있는지를 제어함
ε가 작을수록 → 두 datasets (differing by only one element)에 대한 알고리즘 출력 확률 분포가 유사함 → 프라이버시가 잘 보호됨

δ (delta): another non-negative parameter, usually very small

Example

dataset of individuals’ medical records, 특정 질병의 유병률을 분석
(ε, δ)-differential privacy 정의에 따르면, dataset 포함 여부에 관계없이 분석 결과(like the calculated prevalence)는 크게 다르지 않아야 함

Reference

  • Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, 2.3. Formalizing differential privacy

Leave a Comment