[Algorithmic Foundations] #2. Post-Processing proposition

Definition 2.4 (Differential Privacy)
Pr[M(x)∈S]≤exp(ε)Pr[M(y)∈S]+δ

– in detail: https://saraheee.com/2024/01/foundation-differential-privacy-definition/

Proposition 2.1 (Post-Processing). Let \(M: \mathbb{N}^{|X|} \to R\) be a randomized algorithm that is (ε,δ)-differentially private. Let f: R → R’ be an arbitrary randomized mapping. Then f ◦ M : \(\mathbb{N^{|X|}}\) → R’ is (ε, δ)-differentially private.

Proof. We prove the proposition for a deterministic function f : R → R′. The result then follows because any randomized mapping can be decomposed into a convex combination of deterministic functions, and a convex combination of differentially private mechanisms is differentially private.

Fix any pair of neighboring databases x, y with \(||x-y||_1 \leq 1\), and fix any event S ⊆ R’. Let T = {r ∈ R : f(r) ∈ S}. We then have:

Pr[f(M(x)) ∈ S] = Pr[M(x) ∈ T]
≤ exp(ε) Pr[M(y) ∈ T] + δ
= exp(ε)Pr[f(M(y)) ∈ S] + δ

which was what we wanted.

M: 데이터셋을 입력으로 받아 R 범위의 출력을 생성하는 무작위 알고리즘
f: M의 출력을 다른 범위 R’로 매핑하는 임의의 무작위 함수
f ◦ M: M의 출력에 함수 f를 적용한 값
(ε,δ)-differentially private: M과 f ◦ M 모두 같은 수준의 차등 프라이버시를 준수함

집합 T: f에 의해 S로 매핑되는 R의 모든 요소를 포함함
f(M(x))가 S에 속할 확률이 M(x)가 T에 속할 확률과 같음
하나의 데이터셋에 대한 메커니즘 출력의 확률이 이웃 데이터세트에 대한 확률보다 크게 크지 않다는 것

R’에서 가능한 모든 출력의 하위 집합, 알고리즘 출력을 분석할 때의 모든 (잠재적) 결과 집합

개인정보 보호 알고리즘의 출력은 사후 처리 후에도 차등 개인 정보 보호가 유지됨
차등 비공개 메커니즘의 출력에 어떤 추가 데이터 처리 또는 분석이 적용되더라도 개인 정보 보호 보장이 손상되지 않음을 의미
출력 데이터의 계산이나 조작에 대해 개인 정보 보호의 견고성을 보장함

Theorem 2.2. Any (ε, 0)-differentially private mechanism M is (kε, 0)-differential private for groups of size k. That is, for all \(||x-y||_1\) ≤ k and all S ⊆ Range(M)

Pr[M(x) ∈ S] ≤ exp(kε) Pr[M(y) ∈ S]

where the probability space is over the coin flips of the mechanism M.

(ε, 0)-differentially private를 만족한다면, 크기 k의 그룹에 대해 (kε, 0)-differentially private를 만족
두 데이터셋 x와 y가 최대 k개의 요소에서만 차이가 난다면, 즉 \(||x-y||_1\) ≤ k 이라면
그리고 M의 출력 범위의 임의의 부분집합 S에 대해, M이 x에서 S에 속하는 결과를 내는 확률은 y에서 동일한 결과를 내는 확률의 최대 exp(kε)배이다.

(kε, 0)-differentially private: k 크기의 그룹에 대해 확장된 차등 프라이버시
x와 y가 k개의 요소에서 차이가 날 때, 메커니즘 M이 exp(kε)배 이내의 확률로 결과를 생성하도록 보장함

\(||x-y||_1\) ≤ k: 데이터셋 x와 y가 최대 k개의 요소에서만 차이가 남

• 기본 차등 프라이버시에서 δ는 프라이버시가 완전히 보호되지 않을 수 있는 작은 가능성을 나타냄, 실질적인 한계
• 그룹에 대한 차등 프라이버시에서는 δ = 0. 엄격한 규칙, 기본 버전처럼 작은 오류 가능성을 허용하는 유연성이 없음

Reference

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