지역 차등 정보보호(Local Differential Privacy, LDP)는 사용자의 실제 데이터를 서버로 전송하기 전에 각 사용자의 기기에서 데이터를 무작위화(randomize)하여 개인정보를 보호하는 기술입니다. 이로 인해 서버는 개별 사용자의 실제 값을 알 수 없지만, 전체 사용자의 데이터 분포나 통계적 특성은 유의미하게 추정할 수 있습니다.
단항 인코딩
단항 인코딩(Unary Encoding) 또는 원-핫 인코딩(One-Hot Encoding)은 LDP에서 가장 기본적으로 사용되는 데이터 변환 방식입니다. 가능한 값의 종류가 d개일 때, 특정 값 v를 d차원의 벡터로 표현하는 기법입니다. 이 벡터는 v번째 위치의 값만 1이고 나머지 모든 값은 0으로 설정됩니다.
예를 들어, 사용자가 선호하는 과일이 {사과, 바나나, 오렌지} 중 하나라고 할 때 (d=3), 각 값은 다음과 같이 인코딩됩니다.
- 사과 (v=1): [1, 0, 0]
- 바나나 (v=2): [0, 1, 0]
- 오렌지 (v=3): [0, 0, 1]
Symmetric Unary Encoding(SUE)와 Optimized Unary Encoding(OUE)는 이 단항 인코딩된 벡터를 특정 확률에 따라 교란(perturb)하여 서버로 전송하는 기법입니다.
인코딩 방식
- Encode(v) = [0, · · · , 0, 1, 0, · · · , 0], 길이가 d인 이진 벡터이고 v번째 위치만 1
교란 규칙
벡터 B를 교란하여 B'을 얻을 때 다음 규칙을 적용합니다.
\text{Pr}[B'[i]=1] =
\begin{cases}
p, & \text{if}\ B[i] = 1 \\
q, & \text{if}\ B[i] = 0
\end{cases}
$$
즉,
- 비트 값이 1일 때
- p의 확률로 1을 유지
- 1-p의 확률로 0으로 뒤집기
- 비트 값이 0일 때
- q의 확률로 1로 뒤집기
- 1-q의 확률로 0을 유지
프라이버시 손실 관계식 유도
인접 데이터셋 정의:
- $D_1$: v번째 위치의 비트만 1, 나머지 비트는 0
- $D_2$: w번째 위치의 비트만 1, 나머지 비트는 0 (여기서 w $\neq$ v)
예시)
- $D_1$: [1, 0, 0] (사용자가 선호하는 과일: 사과)
- $D_2$: [0, 1, 0] (사용자가 선호하는 과일: 바나나)
차등 정보보호 정의:
예를 들어 보고된 답변이 사과일 때 사용자의 실제 답변이 사과일 수도 있고 바나나일 수도 있습니다. 따라서 차등 정보보호를 정의하는 수식에서 확률의 비율을 나타내는 분모, 분자는 다음과 같습니다.
- 분자: Pr[보고된 답변=사과 | 실제 답변=사과]
- Pr[(사과 위치의 1을 1로 유지하기) AND (바나나 위치의 0을 0으로 유지하기) AND (그 외 모든 위치의 0을 0으로 유지하기)]
- 분모: Pr[보고된 답변=사과 | 실제 답변=바나나]
- Pr[(사과 위치의 0을 1로 뒤집기) AND (바나나 위치의 1을 0으로 뒤집기) AND (그 외 모든 위치의 0을 0으로 유지하기)]
사과의 위치를 v, 바나나의 위치를 w로 하고 위 예시의 분자, 분모를 차등 정보보호 수식에 대입하면 아래와 같아집니다.
$$\frac{Pr[D_1[v]=1] \cdot Pr[D_1[w]=0]}{Pr[D_2[v]=1] \cdot Pr[D_2[w]=0]} = \frac{p(1-q)}{q(1-p)} \leq e^{\epsilon}
$$
이로부터 프라이버시 손실과 p, q 사이의 관계식을 얻을 수 있습니다.
$$\epsilon = \ln \left(\frac{p(1-q)}{(1-p)q}\right)
$$
집계된 값들의 분산
$$\text{Var}^*(c_{UE}[i]) = \frac{nq(1-q)}{(p-q)^2} = n \cdot \frac{((e^\epsilon - 1)q+1)^2}{(e^\epsilon-1)^2(1-q)q}
$$
대칭 단항 인코딩 (Symmetric Unary Encoding, SUE)
p와 q가 아래의 관계를 만족하도록 정합니다.
$$
p + q = 1
$$
이 때 프라이버시 손실 관계식으로부터 얻는 p, q는 다음과 같습니다.
$$\begin{align}
p & = \frac{e^{\epsilon / 2}}{e^{\epsilon / 2} + 1} \\
q & = \frac{1}{e^{\epsilon / 2}+1}
\end{align}
$$
최적화된 단항 인코딩 (Optimized Unary Encoding, OUE)
위에서 구한 분산을 q에 대하여 편미분하고 0이 되는 q를 구합니다.
$$\frac{\partial \text{Var}}{\partial q} = \frac{1}{(e^\epsilon - 1)^2} (\frac{e^{2\epsilon}}{(1-q)^2} - \frac{1}{q^2}) = 0
$$
위 수식으로부터 q를 얻습니다.
$$q = \frac{1}{e^\epsilon + 1}
$$
단항 인코딩의 프라이버시 손실 관계식에 q를 대입하여 p를 구합니다.
$$p = \frac{1}{2}
$$
따라서 단항 인코딩에서 분산을 최소화하는 p와 q는 다음과 같습니다.
$$\begin{align}
p & = \frac{1}{2} \\
q & = \frac{1}{e^{\epsilon}+1}
\end{align}
$$
댓글
댓글 쓰기