[Algorithmic Foundations] #5. randomized response & laplace mechanism

3.2 Randomized response

Let XYZ be such an activity.
Faced with the query, “Have you engaged in XYZ in the past week?” the respondent is instructed to perform the following steps:

1. Flip a coin
2. If tails, then respond truthfully
3. If heads, then flip a second coin and respond “Yes” if heads and “No” if tails.

Claim 3.5. The version of randomized response described above is (ln3, 0)-differentially private.

Proof. Fix a respondent.
Pr[Response = Yes|Truth = Yes] = 3/4. (first coin comes up tails 1/2, first and second come up heads 1/4)
Pr[Response = Yes|Truth = No] = 1/4.

\(\frac{Pr[Response=Yes|Truth=Yes]}{Pr[Response=Yes|Truth=No]} = \frac{3/4}{1/4} = \frac{Pr[Response=No|Truth=No]}{Pr[Response=No|Truth=Yes]} = 3\)

3.3 The laplace mechanism

functions \(f: \mathbb{N}^{|X|} \to \mathbb{R}^k\)는 데이터베이스 쿼리의 가장 기본적인 유형
X개 데이터베이스를 k개의 실수에 매핑

Definition 3.1 (\(l_1\)-sensitivity).

함수의 출력이 입력 데이터에 얼마나 민감하게 반응하는지 측정하는 지표
– \(l_1\) 민감도: 프라이버시를 보호하기 위해 출력을 얼마나 교란시켜야 하는지에 대한 상한
데이터베이스에서 단일 항목이 추가되거나 제거될 때 함수의 출력 값이 얼마나 변할 수 있는지 나타낸다.

Definition 3.2 (The Laplace Distribution).

0을 중심으로 스케일 b를 가지는 확률 밀도 함수를 가진 분포
지수 분포의 대칭적인 형태를 가진다.

x: 확률 변수, 분포 값
b: 분포의 스케일을 결정하는 매개변수(이 분포의 분산은 \(2b^2\)) – 형태 조절
exp(-|x|/b): x가 0에서 멀어질수록 확률 밀도가 어떻게 감소하는지 설명, b는 감소율 조정
1/2b: 정규화 상수(Normalization constant), 확률 밀도 함수의 총 면적이 1이 되도록 보장한다.
(모든 가능한 x 값에 대해 확률 밀도를 적분하면 1이 됨)

– 확률 밀도 함수는 0을 중심으로 대칭적, x의 절대값이 커질수록 확률 밀도가 지수적으로 감소

\(Lap(x|b) = \frac{1}{2b}exp(-\frac{|x-\mu|}{b})\) (분포의 중심이 μ인 경우)

\(\int_{-\infty}^{\infty}f(x|\mu, b)dx = \int_{-\infty}^{\infty}\frac{1}{2b}exp(-\frac{|x-\mu|}{b})dx\)

Definition 3.3 (The Laplace Mechanism).

\(M_L\): 함수 f의 계산 결과에 노이즈를 추가하여 결과를 변형한다.
\(Y_i\): 독립 동일 분포 랜덤 변수, Lap(∆f/ε)에서 추출된다.
∆f: \(l_1\)의 감도, 최대 출력 차이
ε: 프라이버시 예산 (ε↓ → 데이터 유용성이 낮아짐(노이즈↑), ε↑ → 프라이버시 보호 수준이 낮아짐)
\(f: \mathbb{N}^{|X|} \to \mathbb{R}^k\): 데이터베이스 X에서 k차원 실수 벡터로 매핑하는 함수

Theorem 3.6.

(ε,0)-differential privacy 만족
\(f: \mathbb{N}^{|X|} \to \mathbb{R}^k\) 결과에 독립적으로 분포된 라플라스 노이즈 \(Y_i\)를 추가하여 f(x) + (\(Y_1, \cdots, Y_k\))의 형태로 결과를 출력

비율이 \(exp(\epsilon \cdot \left| f(x)-f(y) \right|_1/\Delta f)\) 이하
\(\left| f(x)-f(y) \right|_1 \leq \Delta f\)이므로 이 비율은 exp(ε)을 초과할 수 없다.

1) 설정
인접한 두 데이터베이스 \(x, y \in \mathbb{N}^{|X|}\), \(\left| x-y \right|_1 \leq 1\)을 만족한다.
f(・): 주어진 함수
함수 f에 대해 \(M_L\)(x, f, ε)의 확률 밀도 함수를 \(p_x\), \(M_L\)(y, f, ε)의 확률 밀도 함수를 \(p_y\)로 표현한다.
(각 데이터베이스 x, y에 대해 라플라스 메커니즘을 적용했을 때의 확률 밀도 함수)

2) 비교
임의의 점 \(z \in \mathbb{R}^k\)에서 두 확률 밀도 함수의 비율을 비교한다.
함수 f의 각 출력 i에 대해, x와 y에 대한 함수 값의 차이
b = ∆f/ε

3) 분석
각 차원 i에 대해, x와 y로 계산된 함수 값의 차이는 \(\left| f(x)_i – f(y)_i \right|\)
f의 민감도와 ε에 의해 결정된 노이즈의 양을 고려할 때, \(p_x(z)/p_y(z)\)의 비율은 exp(ε)을 넘지 않는다.

* 삼각 부등식(Triangle Inequality)에 의해,
∣a+b∣ ≤ ∣a∣+∣b∣, ∣a∣−∣b∣ ≤ ∣a−b∣ 이다.
따라서 |f(y)-z| – |f(x)-z| ≤ |(f(y)-z) – (f(x)-z)| = |f(y) – f(x)| = |f(x) – f(x)|

4) 결론
라플라스 메커니즘이 (ϵ,0)-차등 프라이버시를 보장한다.

이론적 배경 및 실제 적용 가능성을 제시한다.

Reference

  • Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, 3. Basic Techniques and Composition Theorems

3 thoughts on “[Algorithmic Foundations] #5. randomized response & laplace mechanism”

  1. Hi i think that i saw you visited my web site thus i came to Return the favore Im attempting to find things to enhance my siteI suppose its ok to use a few of your ideas

    Reply

Leave a Comment