지역 차등 정보보호를 구현하는 대표적인 기술 중 하나가 바로 k-Randomized Response(k-RR), 우리말로는 'k-무작위화 응답'입니다.
k-Randomized Response의 작동 과정
k-Randomized Response는 사용자가 자신의 실제 값을 일정 확률로 보내거나, 또는 완전히 다른 임의의 값으로 바꿔서 보내는 방식으로 작동합니다. 여기서 'k'는 사용자가 응답할 수 있는 가능한 값의 총 개수(카디널리티)를 의미합니다.
과정은 다음과 같이 간단하게 두 단계로 나눌 수 있습니다.
1단계: 사용자의 응답 무작위화 (클라이언트 측)
사용자는 자신의 실제 값을 서버에 보내기 전, 동전 던지기와 같은 확률적 과정을 거칩니다.
- 참 값을 보낼 확률 (p): 미리 정해진 확률 $p$에 따라 자신의 실제 값을 그대로 보냅니다.
- 거짓 값을 보낼 확률 (q): 반대로, 확률 $q$에 따라 자신의 실제 값을 제외한 나머지 (k-1)개의 값 중 하나를 무작위로 선택하여 보냅니다.
여기서 두 확률의 관계는 다음과 같이 정의됩니다.
$$p + (k-1)q = 1$$
프라이버시 보장 수준은 $p$의 값에 따라 달라집니다. $p$가 클수록 원본 데이터의 유용성은 높아지지만 프라이버시 보호 수준은 낮아집니다. 반대로 $p$가 작아지면 프라이버시 보호는 강화되지만, 수집된 데이터의 통계적 정확성은 떨어지게 됩니다.
예시: '예' 또는 '아니오' (k=2)로 답하는 설문조사를 생각해 보겠습니다.
> 질문: "어제 운동을 하셨나요?"
한 사용자의 실제 답변이 '예'라고 가정해 봅시다.
- 확률 p (예: 75%) 로는 자신의 실제 값인 '예'를 그대로 서버에 전송합니다.
- 확률 q (예: 25%) 로는 다른 값인 '아니오'를 서버에 전송합니다.
만약 가능한 답변이 'A', 'B', 'C' (k=3) 세 가지이고, 사용자의 실제 값이 'A'라면 과정은 다음과 같습니다.
- 확률 p로는 'A'를 전송합니다.
- 확률 q로는 'B' 또는 'C' 중 하나를 무작위로 선택하여 전송합니다.
2단계: 데이터 집계 및 통계 복원 (서버 측)
서버는 이렇게 무작위화된 응답들을 수집합니다. 개별 응답은 실제 값인지 거짓 값인지 알 수 없지만, 수많은 데이터를 모으면 통계적으로 원래 값의 분포를 추정할 수 있습니다.
서버는 수집된 응답 값들의 개수를 센 뒤, 미리 알고 있는 확률 $p$와 $q$를 이용해 통계적 보정을 거쳐 원래 응답의 분포를 복원합니다.
예를 들어, $N$명의 사용자로부터 특정 값 $v$가 $N_v$번 관측되었다면, 원래 값 $v$를 가진 사용자의 수($n_v$)는 다음 공식을 통해 추정할 수 있습니다.
$$n_v \approx \frac{N_v - Nq}{p-q}$$
이처럼 k-Randomized Response는 개별 사용자의 프라이버시를 강력하게 보호하면서도 전체 데이터 집단의 통계적 특성은 유지할 수 있게 해주는 효과적인 지역 차등 정보보호 기술입니다. Google이나 Apple과 같은 기업에서 사용자의 민감한 정보(예: 키보드 사용 패턴, 앱 사용 통계 등)를 수집하면서도 프라이버시를 보호하기 위해 널리 활용되고 있습니다.
프라이버시 손실 관계식 유도
인접 데이터셋:
- $D_1$: 개인의 실제 답변이 v인 경우
- $D_2$: 개인의 실제 답변이 w인 경우 ($w \neq v$)
차등 정보보호 정의:
$$\frac{P(M(D_1)=O)}{P(M(D_2)=O)} = \frac{P(\text{보고된 답변}=v|\text{실제 답변}=v)}{P(\text{보고된 답변}=v|\text{실제 답변}=w)} \leq e^{\epsilon}
$$
보고된 답변이 v일 확률 계산:
- $P(\text{보고된 답변}=v|\text{실제 답변}=v) = p$
- $P(\text{보고된 답변}=v|\text{실제 답변}=w) = q$
프라이버시 손실 수준이 $\epsilon$으로 주어졌을 때 $\epsilon$-차등 정보보호를 만족하기 위한 최대 $p$ 값 유도:
$$\frac{p}{q} = e^{\epsilon}
$$
여기서
$$q = \frac{1-p}{k-1}
$$
를 대입하고 p에 대해 풀면
$$p = \frac{e^{\epsilon}}{e^{\epsilon} + k - 1}
$$
이 됩니다.
원래 값 추정 공식 유도
실제 답변이 v인 사용자가 v로 보고할 확률은 p이고 실제 답변이 v가 아닌 사용자가 v로 보고할 확률은 q이므로 v로 보고한 사용자 수는 아래와 같은 관계를 가지게 됩니다.
$$N_v = pn_v + q(N-n_v)
$$
여기서
- $N$: 총 답변자 수
- $N_v$: 보고된 답변이 v인 사용자 수
- $n_v$: 실제 답변이 v인 사용자 수 (추정 값)
위 수식을 $n_v$에 대해 풀면
$$n_v = \frac{N_v - qN}{p - q}
$$
가 됩니다.
댓글
댓글 쓰기