로컬 차분 프라이버시(Local Differential Privacy) 하에서의 크로스-사일로 비익명화: 위협 모델, 상전이, 그리고 협력의

한 개인의 기록이 각각 (epsilon, delta)-차분 프라이버시 (differential privacy)로 보호되는 k개의 독립적인 데이터 사일로 (data silos)에 나타날 때, 표준 합성 (standard composition)은 결합된 출력에 대해 유효한 (kepsilon, kdelta)-DP 보장을 제공합니다. 그러나 이러한 최악의 경우에 대한 경계 (worst-case bound)는 구체적인 추론 질문, 즉 공격자가 실제로 타겟 개인을 식별할 수 있는 k는 얼마인가에 대한 답을 주지 못합니다. 본 논문은 이 질문에 답하는 데 필요한 정보 이론적 프레임워크 (information-theoretic framework)를 개발합니다. 우리는 모든 사일로에 걸쳐 한 개인의 모든 기록을 동시에 포착하는 인접 관계 (adjacency relation)를 갖는 Pufferfish 스타일의 프라이버시 개념인 크로스-사일로 개인 수준 DP (XSP-DP)를 도입하며, 표준 기본 합성 경계가 이 인접 모델로 전이됨을 검증합니다. 이 프레임워크 내에서 우리는 비익명화 (de-anonymization)가 k* = Theta(log n / epsilon^2) (인구 규모 n, 사일로당 RR 파라미터 epsilon)에서 상전이 (phase transition)를 겪음을 증명합니다 (Fano 하한 (Fano lower bound)은 k << k일 때 모든 추정기가 실패함을 보여주는 반면, 일치하는 최대 우도 상한 (maximum-likelihood upper bound)은 k >> k일 때 공격이 성공함을 보여줍니다). 명시적인 XOR + 무작위 응답 (randomized-response) 구성은 정보 시너지 (information synergy)를 입증합니다: 각 사일로의 출력은 개별적으로 타겟에 대해 정보를 제공하지 않지만, 결합 상호 정보량 (joint mutual information)은 엄격하게 양수입니다. 비협력적 이진 무작위 응답 메커니즘 (non-coordinated binary randomized-response mechanisms)의 경우, k가 임계값을 초과하면 비익명화가 불가피함을 증명하여 크로스-사일로 협력 (cross-silo coordination)이 필수적임을 확립합니다. 이러한 결과는 로컬 DP (local DP) 하에서의 크로스-사일로 추론 공격에 대한 기준 위협 모델과 Theta 수준의 임계값을 제공합니다.