기술 요약: 내부고발자를 위한 그럴듯한 부인 가능성 보장 (Plausible Deniability Guarantees)

문제 정의

내부고발자는 조직의 부정행위에 대한 중요한 안전장치 역할을 하지만, 보복에 대한 두려움은 신고를 저해하는 주요 원인이 됩니다. EU 내부고발자 보호 지침과 같은 기존 법적 프레임워크는 비밀 유지 신고 채널을 의무화하고 있으나, 감사인의 후속 조치로부터 조직이 무엇을 추론할 수 있는지에 대한 공식적인 보장은 제공하지 못합니다.

핵심적인 프라이버시 문제는 조직이 보고서 자체는 보지 못하더라도, 감사 결정의 시퀀스(감사 트랜스크립트)를 관찰할 수 있는 "강한 적대자(strong adversary)"로 작로할 때 발생합니다. 만약 감사인이 보고가 접수된 직후 특정 조직을 조사하고, 해당 정보에 접근할 수 있는 직원이 소수뿐이었다면, 조직은 내부고발자의 신원을 추론할 수 있습니다. 본 논문은 **그럴듯한 부인 가능성(plausible deniability)**의 필요성을 공식화합니다. 즉, 관찰 가능한 감사 트랜스크립트가 특정 보고가 제출된 세계와 제출되지 않은 세계를 무시할 수 있는 수준의 미미한 이점 이상의 차이로 구분할 수 없도록 보장해야 합니다.

랜덤 응답(Randomized Response, Warner의 1965년 메커니즘을 내부고발에 적용)과 같은 기존 방식은 근본적인 유틸리티-프라이버시 트레이드오프 문제를 겪습니다. 이러한 방식은 프라이버시 제약을 충족하기 위해 감사인이 대상(target)을 거의 균등하게 무작위로 선택하도록 강제하며, 이는 실제 보고량에 반응하지 못하는 감사 프로세스를 만듭니다. 또한, 표준 차분 프라이버시(Differential Privacy, DP) 메커니즘은 감사 대상 자체가 전체 결정 시퀀스를 관찰하는 적대자인 특정 위협 모델을 직접적으로 겨냥하지 못하는 경우가 많습니다.

방법론

공식 프레임워크

저자들은 $T$의 호라이즌(horizon)과 $C$개의 감사 대상(audit targets)으로 정의된 감사 프레임워크를 제안합니다.

• 입력: 보고 카운트 스트림 $R_T = (r_1, \dots, r_T)$, 여기서 $r_{t,c}$는 시간 $t$에서의 대상 $c$에 대한 새로운 보고 수입니다.
• 출력: 감사 트랜스크립트 $a_T = (a_1, \dots, a_T)$, 여기서 $a_t \in [C]$는 시간 $t$에 선택된 감사 대상입니다.
• 프라이버시 정의: 본 논문은 **보고당 인접성(per-report adjacency)**에 대한 **$(0, \delta)$-차분 프라이버시(DP)**를 채택합니다. 두 보고 스트림은 특정 시간과 대상에서 정확히 하나의 보고로 차이가 날 때 인접한 것으로 간주됩니다.
• 위협 모델: 적대자는 내부 지식을 거의 완벽하게 보유하고 전체 트랜스크립트 $a_T$를 관찰하는 감사 대상 자체입니다. 목표는 특정 보고가 제출되었는지 여부를 구별하는 데 있어 적대자의 이점을 제한하는 것입니다.
• 유틸리티 지표: 에러(error)는 메커니즘이 가장 높은 활성 카운트(마지막 감사 이후 접수된 보고 수)를 가진 대상을 선택하지 못할 확률로 정의됩니다.

부정적 결과: 랜덤 응답 (Randomized Response)

본 논문은 선택 단계에서 랜덤 응답(RR)을 적용하는 것—즉, 감사인이 확률 $p_{rand}$로 보고를 무시하고 무작위 대상을 감사하거나, 그렇지 않으면 가장 높은 카운트를 가진 대상을 감사하는 방식—이 균등 무작위 감사(uniform random auditing)보다 $\delta$ 이상 나아질 수 없음을 증명합니다.

• 정리 2: 모든 호라이즌 $T$에 대하여, RR이 $(0, \delta)$-DP를 만족한다면, 잘못된 대상을 선택할 확률(유일한 최댓값이 존재할 때)은 $\frac{C-1}{C} - \delta$보다 낮게 제한됩니다.
• 시사점: RR은 "간격 불감증(gap-insensitive)"을 보입니다. 선두 그룹과 차순위 그룹 사이의 보고 격차가 아무리 크더라도, 프라이버시 요구사항이 메커니즘이 거의 항상 탐색(무작위 감사)하도록 강제하기 때문에 에러는 높게 유지됩니다.

제안된 솔루션: 프라이빗 지속적 카운팅(Private Continual Counting)으로의 환원

RR의 한계를 극복하기 위해, 저자들은 프라이빗한 감사를 **프라이빗한 지속적 카운팅(private continual counting)**으로 환원하는 **일반적 환원(generic reduction)**을 제안합니다.

1. 메커니즘 설계 (알고리즘 1):
   • 각 감사 대상 $c$에 대해 독립적인 $(0, \delta)$-DP 지속적 카운터 인스턴스를 유지합니다.
   • 매 타임스텝마다 각 대상에 대한 새로운 보고 카운트를 해당 카운터에 입력합니다.
   • 가장 높은 노이즈가 섞인(noisy) 카운트를 가진 대상을 선택합니다.
   • 리셋 조건: 대상을 감사하면, 해당 카운터 인스턴스를 재시작하고 활성 카운트를 0으로 리셋합니다. 이는 과거의 보고가 미래의 결정에 의해 프라이버시가 침해되지 않도록 보장합니다.
2. 프라이버시 보장: 감사 트랜스크립트는 카운터 출력의 후처리(post-processing)입니다. 카운터가 $(0, \delta)$-DP를 만족하고 리셋 메커니즘이 단일 보고가 오직 하나의 활성 카운터 인스턴스에만 영향을 미치도록 보장하므로, 전체 트랜스크립트는 $(0, \delta)$-DP 보장을 상속받습니다.
3. 구체적 구현: 저자들은 이 프레임워크를 Toeplitz-factorization 카운터(Fichtenberger et al., 2023; Dvijotham et al., 2024)를 사용하여 구현합니다. 이 메커니즘은 $O(\sqrt{\log T})$의 노이즈 스케일링을 달성하며, 이는 지속적 카운팅에서 최적에 가깝습니다.

유틸리티 분석

본 논문은 선택 에러가 실제 선두 그룹과 도전자 사이의 **유효 격차(effective gap)**가 커짐에 따라 감소함을 보여주는 유틸리티 정리(정리 6)를 도출합니다.

• 유효 격차에는 실제 보고 카운트 차이와 누적된 노이즈 차이가 포함됩니다.
• RR과 달리, 제안된 메커니즘의 에러는 보고 격차가 $\sqrt{\log T}$보다 빠르게 성장할 때 사라집니다. 이를 통해 메커니즘은 엄격한 프라이버시를 유지하면서도 보고량에 매우 민감하게 반응할 수 있습니다.

주요 기여

1. 공식화: 본 논문은 내부 정보를 가진 적대자가 대상인 강력한 적대자 모델 하에서, 내부고발자를 위한 보고당 $(0, \delta)$-DP 기반의 감사 트랜스크립트를 공식화했습니다.
2. RR에 대한 부정적 결과: 랜덤 응답(RR)이 호라이즌이나 보고 격차와 관계없이 근사 균등 감사에 고착되는 근본적인 한계가 있음을 증명했습니다.
3. 일반적 환원: 프라이빗한 감사를 프라이빗한 지속적 카운팅으로 환원하는 것을 확립하여, 어떤 $(0, \delta)$-DP 카운터라도 플러그인 구성 요소로 사용할 수 있게 했습니다.
4. 구체적 메커니즘 (TCA): Toeplitz factorization을 사용하여 환원을 구현함으로써, $O(\sqrt{\log T})$의 노이즈 스케일링을 달성하는 Toeplitz Continual Auditing (TCA)을 구축했습니다.
5. 유틸리티 정리: 선택 에러가 보고 격차가 증가함에 따라 감소함을 보여주는 유틸리티 정리를 제공하여, RR의 상수 에러 대비 상당한 개선을 이루었습니다.

결과

• 이론적 결과: 유틸리티 정리는 선두 조직과 경쟁자 사이의 격차가 커질수록 제안된 메커리즘의 에러가 0에 수렴함을 보여주는 반면, RR의 에러는 일정하게 높게 유지됨을 입증합니다.
• 실험적 결과: 정적(격차 스윕) 및 동적(온라인 감사) 설정 모두에서의 시뮬레이션을 통해 이론적 발견을 확인했습니다:
  • 정적 설정: TCA의 오선택률(mis-selection rate)은 보고 격차가 증가함에 따라 급격히 떨어지는 반면, RR은 격차에 무감각합니다.
  • 동적 설정: 보고 리셋이 있는 온라인 환경에서, TCA는 RR 및 균등 무작위 감사에 비해 현저히 낮은 "활성 카운트 결손(active-count deficit, regret)"을 유지하며, 비프라이빗 그리디(non-private greedy) 베이스라인의 성능에 근접합니다.

의의 및 주장

본 논문은 유틸리티를 희생하지 않으면서 긴 호라이즌 동안 효과적으로 작동하는, 최초의 정량화 가능한 내부고발자용 그럴듯한 부인 보장을 제공한다고 주장합니다.

• 신뢰성: 감사 결정이 특정 보고와 결정론적으로 연결될 수 없도록 보장함으로써, 보복을 두려워하는 잠재적 내부고발자들에게 보고 채널의 신뢰도를 높여줍니다.
• AI 거버넌스: 이 연구는 내부 정보가 안전 감사에 핵심적인 신호가 되는 AI 거버넌스 내의 신뢰할 수 있는 내부 보고의 필요성에 의해 특히 동기 부여되었습니다. 이 메커니즘은 개발자가 모델 평가의 타이밍이나 대상을 근거로 특정 직원이 보고했음을 추론할 수 없도록 보장합니다.
• 한계: 저자들은 개별 내부고발자에 대한 보장이 보고 수($k\delta$)에 따라 선형적으로 저하될 수 있다는 점과, 프라이빗한 카운트를 유출하지 않는 신뢰할 수 있는 감사인을 가정한다는 점을 겸허히 언급했습니다. 또한, 액세스 로그 유출과 같은 실제 운영상의 실패는 본 알고리즘적/암호학적 보장의 범위를 벗어남을 명시했습니다.

요약하자면, 본 논문은 랜덤 응답이 유틸리티가 매우 중요한 고위험 감사 상황에서는 불충분한 캔로니컬(canonical) 프라이버시 프리미티브임을 주장합니다. 지속적 카운팅의 발전을 활용함으로써, 보호하고자 하는 데이터에 매우 민-감하게 반응하면서도 강력하고 공식적인 그럴듯한 부인 가능성을 제공하는 감사 정책을 구축할 수 있습니다.