DP-05. 차등 정보보호의 핵심 개념: 인접 데이터셋

차등 정보보호(Differential Privacy)는 "어떤 한 개인이 데이터셋에 포함되거나 포함되지 않더라도, 분석 결과는 거의 바뀌지 않아야 한다"는 강력한 개인정보보호 모델입니다. 여기서 '거의 바뀌지 않음'을 수학적으로 엄밀하게 정의하기 위해 사용되는 핵심 도구가 바로 인접 데이터셋(Adjacent Datasets)입니다.

간단히 말해, 인접 데이터셋이란 단 한 사람의 데이터만 다른 두 개의 데이터셋을 의미합니다.

인접 데이터셋의 두 가지 주요 정의

인접 데이터셋을 정의하는 방식은 크게 두 가지로 나뉩니다. 어떤 시나리오에서 개인정보를 보호하고 싶은지에 따라 적절한 정의를 사용합니다.

1. 레코드 추가/삭제 (비제한적 인접성, Unbounded Adjacency)

가장 일반적인 정의입니다. 두 데이터셋 D1과 D2는 한 개의 레코드(데이터 행)를 추가하거나 삭제해서 서로를 만들 수 있을 때 '인접'하다고 말합니다.

• 수학적 표현: $|D1ΔD2|=1$
  
  • 여기서 Δ는 대칭차(Symmetric Difference)를 의미합니다. 즉, 한쪽에만 있고 다른 쪽에는 없는 원소의 개수가 1개라는 뜻입니다.
• 예시: 100명의 환자 데이터가 담긴 데이터셋 D1이 있다고 가정해 봅시다.
  
  • D2: D1에서 특정 환자 A의 데이터를 삭제한 99명의 데이터셋
  • D3: D1에 새로운 환자 B의 데이터를 추가한 101명의 데이터셋
  • 이때, (D1, D2)는 인접 데이터셋이고, (D1, D3)도 인접 데이터셋입니다.

이 정의는 데이터셋의 전체 크기가 변할 수 있는 상황에 쓰이며, 전역 민감도(Global Sensitivity)를 계산하는 기준이 됩니다.

2. 레코드 대체 (제한적 인접성, Bounded Adjacency)

두 데이터셋의 크기(레코드 수)는 동일하지만, 단 하나의 레코드 내용만 다를 때 '인접'하다고 말합니다.

• 수학적 표현: 데이터셋 D1과 D2는 크기가 같고, 단 하나의 인덱스 i에서만 D1[i] ≠ D2[i]를 만족합니다.
• 예시: 100명의 설문조사 응답 데이터셋 D1이 있습니다.
  
  • D2: D1에서 다른 모든 정보는 동일하지만, 오직 3번 참가자의 응답만 '예'에서 '아니요'로 바꾼 데이터셋
  • 이때, D1과 D2는 인접 데이터셋입니다.

이 정의는 개인의 각 응답을 독립적으로 보호하는 지역 민감도(Local Sensitivity) 모델, 특히 임의화 응답(Randomized Response) 같은 시나리오에 직접적으로 적용됩니다. 스피너 모델의 경우가 바로 여기에 해당합니다.

• D1: 당신의 실제 답변이 '예'인 상태
• D2: 당신의 실제 답변이 '아니요'인 상태

이 두 "데이터셋"은 당신이라는 한 사람의 정보만 다르므로, 제한적 인접성의 정의를 만족합니다.

인접 데이터셋이 차등 정보보호의 핵심인 이유

인접 데이터셋 개념은 최악의 시나리오(worst-case)를 가정하여 프라이버시를 보장하는 열쇠입니다.

공격자의 입장에서 생각해봅시다. 공격자는 특정 개인 'A'의 정보(예: 'A'가 암 환자인지 여부)를 알아내고 싶어 합니다. 공격자가 알고 싶은 정보는 정확히 두 인접 데이터셋의 차이입니다.

• D1: 'A'의 정보가 포함된 데이터셋
• D2: 'A'의 정보가 포함되지 않은 데이터셋

만약 우리가 만든 분석 알고리즘 M이 차등 정보보호를 만족한다면, 이 두 인접 데이터셋에 대한 결과가 거의 동일하게 보여야 합니다. 수학적으로는 다음과 같이 표현됩니다.

$$P[M(D1)=O]≤e^ϵ×P[M(D2)=O]$$

 

이 수식의 의미는 다음과 같습니다.

"알고리즘 M이 D1을 입력받아 특정 결과 O를 출력할 확률은, D2를 입력받아 동일한 결과 O를 출력할 확률과 아주 약간의 차이($e^ϵ$)만 난다."

결과가 거의 구별 불가능하므로, 공격자는 분석 결과를 보아도 이 결과가 'A'가 포함된 D1에서 나온 것인지, 포함되지 않은 D2에서 나온 것인지 확신할 수 없습니다. 바로 이 지점에서 'A'의 정보가 무엇인지 추론할 수 없게 되고, 개인의 프라이버시가 수학적으로 강력하게 보장되는 것입니다.