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
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
Your blog has helped me through some tough times and I am so grateful for your wise words and positive outlook
Hello, Jack speaking. I’ve bookmarked your site and make it a habit to check in daily. The information is top-notch, and I appreciate your efforts.