기술 요약: Earth Mover's Distance를 통한 사용자 수준의 메트릭 차분 프라이버시 (Metric Differential Privacy)

문제 정의

차분 프라이버시(Differential Privacy, DP)는 데이터 분석의 표준이 되었으나, 전통적으로 모든 입력 데이터셋 쌍을 동일하게 민감한 것으로 취급하는 균등한 프라이버시 보장을 제공합니다. 그러나 많은 실제 응용 분야에서 데이터는 이질성을 보입니다. 예를 들어, 사용자의 정확한 거주 도시를 드러내는 것은 국가를 드러내는 것보다 더 민감할 수 있습니다. **메트릭 차분 프라이버시(Metric DP)**는 입력 쌍 사이의 거리와 비례하여 프라이버시 보장 수준을 조절함으로써, 입력값이 유사할 때 더 나은 유틸리티를 얻을 수 있도록 합니다.

기존의 메트릭 DP 연구는 각 사용자가 단일 데이터 항목을 기여하는 아이템 수준(item-level) 설정에 집중해 왔으나, 실제 시나리오에서는 한 명의 사용자가 여러 아이템의 집합(예: 위치 기록 또는 단어 집합)을 제공하는 사용자 수준(user-level) 기여가 빈번합니다. 기존의 사용자 수준 DP 프레임워크는 변화의 크기나 성격에 관계없이 사용자의 전체 데이터셋에 대한 모든 변화를 동일하게 민감한 것으로 취급하는 표준 DP에 의존합니다. 본 논문은 **Earth Mover's Distance (dEM)**를 기반 메트릭으로 사용하는 사용자 수준의 메트릭 DP 연구를 개시합니다. 목표는 사용자의 기여도가 변경된 데이터의 비율과 그 변경의 거리 모두에 따라 민감도가 결정되는 프라이버시 개념을 정의하여, 표준 사용자 수준 DP보다 더 미세한 프라이버시 의미론을 포착하는 것입니다.

방법론

1. dEM-DP의 정의

저자들은 두 사용자 데이터셋 $K$와 $K'$ 사이의 거리를 Earth Mover's Distance(1-Wasserstein 거리로도 알려짐)를 사용하여 측정함으로써 dEM-DP를 정의합니다.

• 메트릭: $d_{EM}(\tilde{K}, \tilde{K}')$는 데이터셋 $K$의 확률 분포를 $K'$로 운송하는 데 드는 최소 비용을 나타내며, 여기서 비용은 이동하는 데이터의 양에 아이템 간의 거리 $d_X$를 곱한 값입니다.
• 프라이버시 보장: 메커리즘 $M$이 동일한 크기의 임의의 두 데이터셋 $K, K'$에 대해 다음을 만족하면 $(\alpha, \delta)$-bounded dEM-DP를 충족합니다:
  $$\Pr[M(K) \in O] \le e^{\alpha \cdot d_{EM}(\tilde{K}, \tilde{K}')} \Pr[M(K') \in O] + \delta$$
  여기서 프라이버시 파라미터는 거리에 따라 스케일링됩니다. 만약 $d_{EM}$이 작다면(유사한 데이터셋인 경우), 균등한 $\epsilon$을 적용하는 표준 DP에 비해 프라이버시 보장이 더 강력해집니다(더 낮은 유효 $\epsilon$).

2. 메커니즘 설계

본 논문은 로컬 모델(사용자가 데이터를 전송하기 전에 프라이버시 처리)과 중앙 모델(신뢰할 수 있는 집계자가 데이터를 보유) 모두에서 dEM-DP 하의 쿼리 릴리스를 위한 두 가지 새로운 메커리즘을 제안합니다.

A. 선형 쿼리 (PrivEMDLinear)

$F\tilde{K}$ 형태의 선형 쿼리에 대해, 저자들은 dEM 하에서의 민감도를 분석합니다.

• 민감도 분석: 쿼리 함수가 유계(bounded)여야 하는 표준 DP와 달리, dEM-DP 분석은 쿼리 함수 $f$가 **립시츠 연속(Lipschitz continuous)**일 것을 요구합니다.
• 결과: 저자들은 dEM 하에서의 선형 쿼리의 민감도가 쿼리 함수의 립시츠 상수(Lipschitz constant)에 의해 상한이 됨을 증명합니다. 이를 통해 최악의 경우의 글로벌 경계가 아닌 립시츠 상수에 비례하도록 보정된 노이즈(예: K-norm 메커니즘 또는 가우시안 메커니즘 사용)를 추가할 수 있어 유틸리티를 개선할 수 있습니다.

B. 순서가 없는 아이템별 쿼리 (PrivEMDItemWise)

사용자의 데이터셋 내 각 아이템에 대한 노이즈가 섞인 출력을 릴리스하기 위해(예: 히스토그램), 이 메커리즘은 각 아이템에 기본 아이템 수준 메트릭 DP 메커리즘 $A$를 적용한 후 결과를 **셔플링(shuffling)**합니다.

• 셔플링에 의한 프라이버시 증폭: 저자들은 "셔플링에 의한 프라이버시 증폭" 결과를 메트릭 DP 설정으로 일반화합니다. 출력은 순서가 없는 리스트이므로, 공격자는 특정 출력을 특정 입력 인덱스에 연결할 수 없습니다.
• 기술적 참신함: 그들은 $m$개의 아이템을 셔플링하는 것이 프라이버시 비용을 $O(m\alpha)$(합성을 통해)에서 $O(\alpha\sqrt{m})$로 줄여준다는 것을 증명합니다. 이 결과는 입력 벡터 간의 결합(coupling)을 분석하고 셔플 모델의 특성을 활용하여 도출되었습니다.

3. 무제한 데이터로의 확장

실제 데이터셋은 사용자당 데이터 크기가 다양하며(무제한 설정), 이는 데이터셋 크기 자체가 프라이버시 문제가 될 수 있기 때문에 dEM 분석을 복잡하게 만듭니다.

• 축소(Reduction): 저자들은 무제한(unbounded) dEM-DP에서 유계(bounded) dEM-DP로의 블랙박스 축소를 제안합니다.
• 메커니즘: **복원 추출(sampling with replacement)**을 사용하여 임의의 사용자 데이터셋을 고정된 크기 $s$로 투영합니다. 저자들은 이 투영이 "매끄럽다(smooth)"는 것, 즉 투영된 데이터셋 간의 dEM 거리가 원래 데이터셋 간의 dEM 거리와 (작은 가산 항까지 포함하여) 매우 유사하다는 것을 증명합니다.
• 이산 dEM-DP (Discrete dEM-DP): 샘플링으로 인한 가산 오차를 처리하기 위해, 거리가 $r$ 이하인 변화는 균등하게 보호되는 "이산적" dEM-DP 정의를 도입합니다. 충분히 큰 샘플 크기에 대해, 무제한 dEM-DP가 프라이버시 의미론의 손실을 거의 없이 유계 dEM-DP로 축소될 수 있음을 보여줍니다.

주요 기여

1. 사용자 수준 메트릭 DP의 정의: 본 논문은 Earth Mover's Distance를 사용하여 데이터 변화의 크기와 공간적 측면을 모두 포착하는 사용자 수준의 메트릭 DP에 대한 공식적인 정의를 확립했습니다.
2. 새로운 메커리즘:
   • PrivEMDLinear: 립시츠 연속성을 활용하여 민감도를 제한함으로써, 특정 유형의 쿼리에 대해 표준 사용자 수준 DP보다 더 나은 유틸리티를 제공하는 선형 쿼리용 메커리즘입니다.
   • PrivEMDItemWise: 셔플링을 활용하는 아이템별 쿼리용 일반 메커리즘입니다. 저자들은 표준 합성(composition) 경보다 $\sqrt{m}$ 개선된 프라이버시 증폭 분석을 제공합니다.
3. 무제한 축소: 샘플링을 통해 유계 dEM-DP 메커리즘을 무제한 메커리즘으로 변환하는 블랙박스 축소 기술을 제안하여, 가변적인 사용자 기여 크기를 가진 데이터셋에 이 메커니즘들을 적용할 수 있게 합니다.
4. 유틸리티 개선: 이론적 분석을 통해 dEM-DP 메커니즘이 다음과 같은 경우 표준 사용자 수준 DP 베이스라인보다 엄격히 더 나은 유틸리티(더 낮은 오차)를 달erm 수 있음을 입증했습니다:
   • 선형 임베딩 쿼리: 중앙 및 로컬 모델 모두에서, 특히 불일리한 입력에 대해 프라이버시 파라미터 $\alpha$가 표준 $\epsilon$보다 클 수 있을 때 유용합니다.
   • 빈도 추정 (Frequency Estimation): 로컬 모델에서, 데이터가 구조(예: 클러스터링된 메트릭)를 가지고 있을 때 도메인 크기와 프라이버시 파라미터가 특정 조건을 만족하면 오차가 개선됩니다.

결과 및 의의

본 논문은 dEM-DP가 실제 프라이버시 의미론과 더 잘 부합하는 더 세밀한 프라이버시 정의를 제공한다고 주장합니다.

• 프라이버시 의미론: 표준 DP에서는 사용자의 데이터를 한 달 치를 바꾸는 것이 단 하루 치를 바꾸는 것만큼이나 민감하게 취급됩니다. dEM-DP에서는 단 하루의 변화는 덜 민감하게(작은 $d_{EM}$) 간주되어 노이즈를 줄이고 유틸리티를 높이는 반이, 한 달간의 변화는 더 강력한 보장을 받습니다.
• 유틸리티 이득: 이론적 경계는 선형 임베딩 쿼리와 빈도 추정에서 dEM-DP 메커니즘이 표준 사용자 수준 DP보다 성능이 뛰어날 수 있음을 보여줍니다. 예를 들어, 빈도 추정에서 데이터가 구조를 가질 때(예: 클러스터링된 메트릭), dEM-DP 하에서 도메인 크기 $k$와 프라이버시 파라미터에 대한 오차 의존성이 개선됩니다.
• 일반화 가능성: 유계 설정으로의 축소와 일반적인 셔플링 분석은 이러한 기술들이 제공된 특정 예시(위치, 텍스트, 그래프)를 넘어 다양한 메트릭 공간과 쿼리 유형에 광범위하게 적용될 수 있음을 시사합니다.

저자들은 이 연구가 특정 텍스트 기반 응용 분야를 넘어 일반적인 메트릭 공간에 적용 가능한 프레임워크로서, 사용자 수준의 메트릭 DP를 dEM을 통해 제안한 첫 번째 일반적 정의라고 위치시킵니다. 그들은 dEM-DP가 표준 DP의 완화된 형태이지만, 데이터의 유사성이 민감도와 상관관계를 갖는 응용 분야에서 더 실용적인 트레이드오프를 제공한다는 점을 강조합니다.