Differential Privacy: (ε, δ) 로 정량화하는 프라이버시 보장

differential privacy, 차분 프라이버시, DP, epsilon differential privacy, ε-DP, epsilon-delta DP, Laplace mechanism, Gaussian mechanism, exponential mechanism, DP-SGD, privacy budget, 프라이버시 예산, sensitivity, global sensitivity, local sensitivity, Local DP, LDP, Central DP, Renyi DP, moments accountant, RAPPOR, k-anonymity, l-diversity

정의

Differential Privacy (DP, 차분 프라이버시) 는 데이터셋에 대한 질의 (query) 결과에 calibrated noise 를 추가함으로써, 한 개인의 데이터가 포함되었는지 여부 를 결과만 보고서는 알 수 없게 만드는 수학적 프라이버시 프레임워크입니다. Cynthia Dwork 등이 2006 년에 정의했습니다.

핵심 아이디어: “당신이 데이터셋에 있든 없든, 통계 결과는 거의 같게 보이도록 만든다.”

왜 등장했는가

전통적 익명화 (identifier 제거, k-anonymity, l-diversity 등) 는 linkage attack 에 취약합니다.

• Netflix Prize (2007): 익명화된 시청 기록이 IMDb 공개 리뷰와 결합되어 사용자 재식별
• AOL 검색 로그 (2006): 사용자 ID 만 익명화했지만 검색 쿼리 자체가 지문 역할
• Massachusetts governor 재식별 (Sweeney, 1997): ZIP + 생년월일 + 성별 3 축만으로 87% 재식별 가능

문제의 본질: 관측 가능한 결과가 특정 개인의 데이터에 크게 의존 하면, 아무리 이름을 지워도 그 개인이 데이터에 있었다는 사실 자체가 새어 나갑니다. DP 는 이 의존성을 정량적 상한 으로 제어합니다.

형식 정의

인접 데이터셋 (Adjacent Datasets)

두 데이터셋 $D$ 와 $D^{\prime }$ 이 정확히 한 레코드만 다를 때 인접 (adjacent) 이라고 합니다.

• Add/Remove 인접: $D^{\prime }=D\cup \{x\}$ 또는 $D^{\prime }=D\setminus \{x\}$
• Replace 인접: $D^{\prime }$ 이 $D$ 의 한 레코드를 다른 값으로 바꾼 결과

정의에 따라 프라이버시 보장 강도가 조금씩 달라지지만, 실용적으로는 큰 차이 없습니다.

ε-Differential Privacy (pure DP)

무작위 알고리즘 $\{M\}$ 이 $ϵ$-DP 를 만족한다는 것은, 임의의 인접 데이터셋 $D,D^{\prime }$ 과 임의의 출력 집합 $S$ 에 대해:

$$\mathrm{Pr}[\{M\}(D)\in S]\le e^{\{}ϵ\}\cdot \mathrm{Pr}[\{M\}(D^{\prime })\in S]$$

• $ϵ$ (epsilon): 프라이버시 손실의 상한. 작을수록 강력한 보장.
• $e^{ϵ}\approx 1+ϵ$ (작은 $ϵ$ 일 때), 즉 두 확률 분포가 매우 유사.

(ε, δ)-Differential Privacy (approximate DP)

$$\mathrm{Pr}[\{M\}(D)\in S]\le e^{\{}ϵ\}\cdot \mathrm{Pr}[\{M\}(D^{\prime })\in S]+\delta$$

• $\delta$: 위 부등식이 실패할 확률의 상한. 보통 $\delta \ll 1/n$ (데이터 크기의 역수보다 작게)
• Gaussian mechanism 등은 pure DP 를 만족할 수 없어 approximate DP 를 씀

Rule of thumb:

• $ϵ\le 1$: 강한 보장
• $1\text{<}ϵ\le 3$: 중간
• $ϵ>10$: 실질적 보장 미미 (경고 신호)
• $\delta \text{<}1/n^2$ 정도 권장 (Dwork 의 조언)

왜 이 정의인가

DP 의 강력한 점:

1. 개인 데이터의 존재/부재를 감출 수 있음: 공격자가 사전에 알고 있는 정보가 아무리 많아도 (어떤 auxiliary data 를 가지고 있어도) 새 정보를 얻기 어려움
2. Composition 가능: 여러 DP 쿼리를 합쳐도 여전히 DP 성질 유지 (예산 합산)
3. Post-processing immunity: DP 결과에 어떤 계산을 추가로 해도 여전히 DP 유지
4. 미래 공격에 대비: 특정 공격을 상정하지 않고 최악 케이스를 다룸

핵심 개념: Sensitivity

함수 $f:\text{{}Data\}\to \{R{\}}^d$ 의 global sensitivity 는 인접 데이터셋에 대한 함수 값 변화의 상한:

$$\Delta f=\underset{\{}{\max }D,D^{\prime }\text{ adjacent}\}\Vert f(D)-f(D^{\prime }){\Vert }_1$$

• 개수 세기 (count): $\Delta f=1$ (한 명 추가/제거하면 결과 1 변함)
• 평균 (mean) with bounded values in $[0,M]$: $\Delta f=M/n$
• 합 (sum) with bounded values in $[0,M]$: $\Delta f=M$

Sensitivity 가 클수록 더 많은 노이즈가 필요합니다. 값을 미리 clip 해서 sensitivity 를 제어 하는 게 실전에서 매우 흔한 패턴입니다.

핵심 메커니즘

Laplace Mechanism

$ϵ$-DP 를 만족하는 가장 단순한 방법. Laplace 분포에서 노이즈 샘플:

$$\{M\}(D)=f(D)+\text{{}Lap\}\left(\frac{\{}{\Delta }f\}\{ϵ\}\right)$$

Laplace 분포는 라플라스 확률 밀도 $\text{{}Lap\}(b):p(x)=\frac{1}{\{}2b\}{e}^{\{}-|x|/b\}$.

import numpy as np

def laplace_mechanism(true_value, sensitivity, epsilon):
    noise = np.random.laplace(loc=0, scale=sensitivity/epsilon)
    return true_value + noise

# 예: 데이터셋에서 특정 조건 만족하는 사용자 수 세기
true_count = 4321
noisy_count = laplace_mechanism(true_count, sensitivity=1, epsilon=0.5)

Gaussian Mechanism

$(ϵ,\delta )$-DP 를 만족. L2 sensitivity 사용:

$$\{M\}(D)=f(D)+\{N\}\left(0,{\left({\frac{\{}{\Delta }}_{2}f\cdot \sqrt{2\ln (1.25/\delta )}\}\{ϵ\}\right)}^2\right)$$

Gaussian 은 여러 차원의 합성에서 유리하며, DP-SGD 등에서 표준입니다.

Exponential Mechanism

범주형/불연속 출력 에 사용. Utility 함수 $u(D,r)$ 을 정의하고:

$$\mathrm{Pr}[\{M\}(D)=r]\propto \exp \left(\frac{\{}{ϵ}\cdot u(D,r)\}\{2\Delta u\}\right)$$

Utility 가 높은 후보를 확률적으로 우선 선택합니다. 경매, 후보 선택 문제에 씀.

Composition

여러 DP 쿼리를 순차적으로 하면 프라이버시가 누적됩니다.

Basic Composition

$k$ 개의 $({ϵ}_i,{\delta }_i)$-DP 메커니즘의 순차 합성은:

$$\left(\sum {ϵ}_i,\sum {\delta }_i\right)\text{{}-DP\}$$

간단하지만 상당히 loose 합니다.

Advanced Composition (Dwork et al., 2010)

$k$ 개의 $(ϵ,\delta )$-DP 메커니즘의 합성은 다음과 같이 tighter:

$$\left({ϵ}^{\prime }=ϵ\sqrt{\{}2k\ln (1/{\delta }^{\prime })\}+kϵ(e^{ϵ}-1),k\delta +{\delta }^{\prime }\right)\text{{}-DP\}$$

Basic 대비 $\sqrt{\{}k\}$ 배 정도로 개선됩니다.

Rényi DP 를 통한 tighter composition

Mironov (2017) 의 Rényi DP 는 Rényi divergence 로 프라이버시를 정의합니다. 합성이 매우 tight 하며 최종적으로 $(ϵ,\delta )$-DP 로 변환합니다. DP-SGD 의 privacy accounting 은 사실상 Rényi DP + Moments Accountant 방식입니다.

Privacy Budget

한 데이터셋에 대해 여러 분석을 하고 싶다면, 각 분석마다 ${ϵ}_i$ 를 배분해야 합니다.

$$\sum _i{ϵ}_i\le {ϵ}_{\{}\text{total}\}$$

• 총 예산 소진 후에는 더 이상 어떤 쿼리도 하면 안 됨
• 프로덕션에서는 accountant 로 남은 예산을 실시간 추적
• 예산이 부족하면: 데이터셋 refresh, 사용자 그룹 세분화, 더 세밀한 clipping 으로 sensitivity 감소

Central DP vs Local DP

Central DP (Trusted Curator)

• 신뢰할 수 있는 데이터 큐레이터 존재
• 큐레이터가 원본 데이터를 보고 노이즈 추가 후 결과 공개
• Utility 높음, 프라이버시 보장은 큐레이터를 신뢰한다는 전제
• 예: 미국 인구조사국, 대부분의 학술 통계

Local DP (LDP)

• 신뢰할 수 있는 큐레이터가 없음
• 각 개인이 자기 데이터에 노이즈를 추가하고 서버에 전송
• 서버는 노이즈가 낀 데이터만 받으므로 원본을 알 수 없음
• Utility 매우 낮음 (같은 $ϵ$ 이면 노이즈가 훨씬 커야 함)
• Apple, Google 이 자주 배포

RAPPOR (Google, 2014)

LDP 의 대표 배포. Chrome 사용자의 홈페이지 URL 통계를 수집할 때 각 사용자가 자기 URL 을 Bloom filter 로 인코딩한 뒤 각 비트를 randomized response 로 뒤집어 전송. 서버는 통계만 복원 가능, 개인 URL 은 알 수 없음.

비교

구분	Central DP	Local DP
신뢰 모델	큐레이터 신뢰 필요	Trustless
노이즈 위치	서버 (집계 후)	클라이언트 (개별 데이터)
같은 ε 에서 utility	높음	낮음
배포 사례	미국 인구조사, 학술	Apple 이모지, Google RAPPOR

DP-SGD, 딥러닝 학습의 DP

Abadi et al. (2016) 이 제안한 DP-SGD (Differentially Private SGD) 는 딥러닝 학습에 DP 를 적용하는 표준 방법입니다.

알고리즘:

1. Sample: 각 step 에서 mini-batch 를 Poisson sampling (각 샘플이 확률 $q=B/N$ 로 포함)
2. Compute per-sample gradients: 각 샘플에 대한 gradient 를 개별 계산
3. Clip: 각 gradient 를 L2 norm 상한 $C$ 로 클립 $${\bar{g}}_i=g_i/\max \left(1,\frac{\Vert g_i{\Vert }_2}{C}\right)$$
4. Aggregate + noise: 클립된 gradient 를 합산하고 Gaussian noise 추가 $$\tilde{g}=\frac{1}{B}\left(\sum _i{\bar{g}}_i+\mathcal{N}(0,{\sigma }^2{C}^{2}I)\right)$$
5. Update: $\theta \leftarrow \theta -\eta \widetilde{\{}g\}$

노이즈 배율 $\sigma$ 와 sampling 확률 $q$, 총 step 수 $T$ 로부터 최종 $(ϵ,\delta )$ 를 계산합니다 (Moments Accountant 또는 Rényi DP accountant).

Opacus (PyTorch)

Facebook Research 의 PyTorch DP 라이브러리:

from opacus import PrivacyEngine

model = MyModel()
optimizer = torch.optim.SGD(model.parameters(), lr=0.05)
data_loader = torch.utils.data.DataLoader(dataset, batch_size=256)

privacy_engine = PrivacyEngine()

model, optimizer, data_loader = privacy_engine.make_private(
    module=model,
    optimizer=optimizer,
    data_loader=data_loader,
    noise_multiplier=1.1,       # σ
    max_grad_norm=1.0,          # C
)

for epoch in range(N):
    for batch, labels in data_loader:
        optimizer.zero_grad()
        loss = criterion(model(batch), labels)
        loss.backward()
        optimizer.step()

    epsilon = privacy_engine.get_epsilon(delta=1e-5)
    print(f"epoch {epoch}: (ε={epsilon:.2f}, δ=1e-5)")

DP-SGD 의 utility 손실

• 이미지 분류에서 clean 대비 5~15%p accuracy 손실이 흔함
• LLM 파인튜닝에서는 더 심각할 수 있음
• 완화: PEFT 와 결합 (파라미터 수가 적으면 노이즈 영향 감소), 사전 학습 모델 재사용, 더 큰 batch

실배포 사례

Apple (2016~)

iOS 10 부터 emoji 추천, QuickType 같은 기능에 LDP. Randomized response 계열, ε 는 일당 수 단위. WWDC 2016 발표.

Google

• RAPPOR (Chrome, 2014)
• Federated Learning + DP (Gboard 다음 단어 예측)
• Google Health 데이터 집계

US Census (2020)

2020 년 미국 인구조사가 DP 를 공식 채택. 발표된 통계에 Gaussian noise 를 추가한 것이 정치적 논란도 있었지만 역사적 이정표입니다. Epsilon 은 여러 통계별로 배분 (총 예산 약 $ϵ=19.6$).

Microsoft

• Windows telemetry 에 LDP 적용
• SmartNoise 오픈소스 릴리스

학술 데이터셋

• OpenDP 프로젝트 (Harvard) 가 공공 데이터셋 릴리스에 DP 도구 제공

프레임워크

도구	특징
Opacus	PyTorch, DP-SGD, Facebook
TensorFlow Privacy	TF, DP-SGD, Google
OpenDP	Harvard, rigorous verification, Rust core + Python binding
Diffprivlib	IBM, sklearn-호환 인터페이스
SmartNoise	Microsoft + OpenDP, 통계 쿼리 지향
PyDP	OpenMined, Google DP C++ 라이브러리 wrapper

한계와 유의점

Utility-Privacy Trade-off

강력한 프라이버시 ($ϵ$ 작게) 는 노이즈 증가 → 정확도 하락. “공짜 프라이버시” 는 없습니다.

ε 해석의 어려움

• 실무자에게 ε=1 이 “얼마나 안전한지” 직관 어려움
• $e^{ϵ}$ 배 정도의 확률 차이라고 설명해도 감이 안 오는 경우 많음
• 최근에는 Bayesian re-interpretation 이나 membership inference attack 성공률로 환산해 설명하려는 시도

데이터 카탈로그 문제

DP 는 각 쿼리 에 대해 보장하는 것이지, 데이터셋 자체를 “완전히 익명” 만드는 것이 아닙니다. 여러 릴리스가 쌓이면 예산이 소진됩니다.

결측치와 outlier

극단값이 sensitivity 를 크게 만들어 노이즈가 급증합니다. Clipping 을 잘 설계해야 함.

Group Privacy 는 다름

DP 는 “한 개인” 을 보호합니다. 가족처럼 상관관계 있는 그룹은 별도 분석 필요.

정확한 구현이 어려움

• Floating-point 구현이 이론과 미묘하게 어긋나 실제로 DP 를 위반하는 사례 보고 (Mironov, 2012)
• Random number generator 품질 중요
• 이 때문에 검증된 라이브러리 (Opacus, OpenDP) 사용 강력 권장

관련 개념 비교

방법	보장 강도	특징
Identifier 제거	매우 약함	Netflix, AOL 사건으로 실패 증명
k-anonymity	약함	Quasi-identifier 지정 필요, 조합 attack 취약
l-diversity, t-closeness	약함~중간	k-anonymity 개선판, 실전 여전히 어려움
Differential Privacy	강함, 정량	Composition 성질, 미래 공격에 대비
Secure Multi-Party Computation (MPC)	강함	계산 자체는 정확, 프로토콜 비용 큼
Homomorphic Encryption (HE)	강함	암호화 상태 계산, 매우 느림
Federated Learning	자체 보장 없음	Gradient inversion 취약, DP 와 결합 필요

DP + FL + Secure Aggregation 조합이 실무의 표준 강화 스택입니다.

참고

• 관련 Federated Learning 에 DP 를 결합한 학습
• 관련 Transfer Learning 파인튜닝 시 DP-SGD 로 개인정보 보호
• 관련 분류 모델 지표 DP 학습 모델도 동일 지표로 평가
• 정본 교과서: Dwork & Roth 2014, The Algorithmic Foundations of Differential Privacy
• Wikipedia: Differential privacy
• 강의 자료: Boston University CS 591, Harvard OpenDP