Better Privacy Guarantees for Larger Groups

기술 요약: 더 큰 그룹을 위한 개선된 프라이버시 보장

문제 정의
본 논문은 고정된 서로소 그룹(disjoint groups)을 위한 프라이리한 히스토그램 설계와 관련하여 Pujol과 Desfontaines [2023]가 제기한 미해결 문제를 다룹니다. 표준 차분 프라이버시 메커니즘은 일반적으로 모든 카운트에 고정된 크기의 노이즈를 추가하여 균등한 절대적 프라이버시를 제공하지만, 이로 인해 작은 그룹에 비해 큰 그룹의 상대적 오차가 현저히 작아지는 결과를 초래합니다. 핵심 질문은 이 여분의 정확도를 어떻게 다르게 "사용"할 수 있는가 하는 것입니다. 즉, 그룹의 오차가 해당 카운트($x_i$)에 비례하여 커지도록 허용함으로써, 더 큰 그룹의 구성원들에게 더 강력한 프라이버시 보장(더 작은 프라이버시 예산)을 제공할 수 있는지에 대한 것입니다.

본 논문은 add-or-remove-one(하나를 더하거나 빼는) 인접성 모델 하에서 이를 조사합니다. 목표는 프라이버시 예산 $v(n)$이 그룹의 크기 $n$에만 의존하고, 비증가(non-increasing)하며, **카운트 종속적 그룹별 zero-concentrated differential privacy (zCDP)**를 만족하는 메커니즘을 찾는 것입니다. 이를 위해서는 인접한 데이터셋 사이의 모든 차수 $\alpha > 1$에 대해 렐리 디버전스(Rényi divergence)를 양방향으로 제한해야 합니다.

중요한 기술적 난제로 **제로 경계 조건(boundary condition at zero)**이 식별되었습니다. 기존의 정식화는 기대 절대 오차가 엄격하게 $r x_i$보다 작아야 함을 요구했습니다. $x_i = 0$일 때, 이는 $E|\hat{x}_i| < 0$을 의미하며, 이는 불가능합니다. 또한, $0 \leftrightarrow 1$ 엣지에서 유한한 양방향 렐리 디버전스를 유지하면서 부등식을 $\leq$로 완화하더라도 모순이 발생합니다(출력값이 1일 때 결정론적(deterministic)이어야 하여 오차 범위를 위반하게 됨).

방법론 및 수정된 정식화
이 경계 문제를 해결하기 위해, 저자들은 다음과 같은 "수정된" 효용 요구사항을 제안합니다:
$$E|\hat{x}_i - x_i| < r \max\{x_i, 1\}$$
이는 모든 양수 카운트에 대해 상대적 오차 목표를 유지하면서, 0일 때 고정된 절대 허용 오차를 도입하여 문제를 실행 가능하게 만듭니다.

본 논문은 두 가지 주요 방법론적 접근 방식을 채택합니다:

1. 실행 가능성 (상한선): 저자들은 기존의 "shifted-transformation" 프레임워크(Finley et al. [2026])를 특수화합니다. 카운트 공간을 이동(shift) $c$를 포함한 로그 함수로 변환하고($\log(x_i + c)$), 고정 분산 가우시안 노이즈를 더한 뒤, 지수 함수를 취하고 클리핑(clipping)하기 전에 결정론적 드리프트(drift)를 적용합니다.

   • 핵심 혁신: 평균 미편향성(mean-unbiasedness)을 보장하기 위해 $-\sigma^2/2$의 드리프트를 사용하는 표준 로그-노멀 메커니즘과 달리, 이 메커니즘은 $-\sigma^2$의 드리프트를 사용합니다. 이 특정 드리프트는 본 논문의 효용 지표와 일치하도록 '기대 절대 곱셈 오차(expected absolute multiplicative error)'를 최소화하기 위해 선택되었습니다.
   • 프라이버시 메커니즘: 동일한 분산을 가진 로그 공간에서 작업함으로써, 이 메커니즘은 인접한 카운트 사이의 렐리 디버전스가 모든 차수 $\alpha$에 대해 유한함을 보장하여, 불균등한 분산이 한쪽 방향의 무한한 디버전스를 유발하는 "꼬리 장애(tail obstruction)"를 방지합니다.

2. 불가능성 (하한선): 저자들은 수정된 효용 및 카운트 종속적 zCDP 요구사항을 만족하는 어떤 메커니즘도 카운트의 역제곱보다 빠른 속도로 프라이버시 예산이 감소할 수 없음을 증명합니다.

   • 두-카운트 논증 (Two-Count Argument): 두 특정 카운트 사이의 테스트를 통해 $n^{-2}$ 지수를 확립합니다.
   • 다수-카운트 논증 (Many-Count Argument): "숨겨진 오프셋(hidden offset)" 확률 변수를 활용하고 정보 이론적 논증(기대 절대 오차와 상호 정보량의 관계)을 사용하여, 프라이버시 예산의 선행 계수에 대한 더 타이트한 하한선을 도출합니다.

주요 결과

• 최적 점근적 비율: 임의의 고정된 $0 < r < 1$에 대해, 최적의 프라이버시 예산 $v(n)$은 $\Theta_r(n^{-2})$로 감소합니다.

  • 상한선: shifted-log Gaussian 메커니즘은 $v(n) = O_r(n^{-2})$를 달성합니다. 구체적으로, $n \to \infty$일 때, $v(n) \approx \frac{1}{2\sigma^2 n^2}$입니다.
  • 하한선: 요구사항을 만족하는 모든 메커니즘은 $\liminf_{n \to \infty} n^2 v(n) \geq \frac{(1-r)^6}{128r^2(1+r)^2}$를 만족해야 합니다. 이는 역제곱 비율이 인위적인 구조물이 아니라 본질적인 것임을 확인해 줍니다.

• 선행 계수: 본 논문은 작은 $r$과 큰 $n$의 극한에서 선행 계수 $C^*$에 대한 최적의 상한과 하한 사이의 간극을 좁힙니다:
  $$\frac{\pi}{4e^2} \leq C^* \leq \frac{1}{\pi}$$
  두 경계 사이의 비율은 약 2.995로, 두 경계가 3배 이내의 차이 안에 있음을 나타냅니다.

• 부적절한 불균등 분산 가우시안 (Failure of Unequal-Variance Gaussian): 본 논문은 $N(n, r^2 n^2)$(카운트의 제곱에 비례하는 분산을 가진 가우시안 노이즈)를 방출하는 단순한 메커니즘이 zCDP 정의를 충족하지 못함을 보여줍니다. 이는 올바른 오차 규모를 갖지만, 인접한 카운트 사이의 불균등한 분산으로 인해 충분히 높은 차수 $\alpha$에서 한쪽 방향의 렐리 디버전스가 무한대가 되어 zCDP의 "모든 차수" 요구사항을 위반하게 됩니다.

• 자명한 사례 (Trivial Case): $r=1$일 때, 데이터 독립적 릴리스(예: 항상 0.5를 출력)는 수정된 기준을 프라이버시 손실 없이($v \equiv 0$) 만족합니다.

의의 및 주장
본 논문은 이 특정 형식의 그룹별 프라이버시에 대해 역제곱 비율이 최적임을 입증하는 최초의 메커니즘 독립적 증명을 제공한다고 주장합니다.

• 실행 가능성: "수정된" 정식화가 해결 가능하다는 것을 입증하고, 최적의 비율을 달성하는 구체적이고 결합 가능한(composable) 메커니즘(shifted-log Gaussian)을 제시합니다.
• 최적성: 어떤 메커니즘도, 아무리 복잡하거나 상관 구조를 갖더라도, $n^{-2}$ 감소율을 개선할 수 없음을 증명합니다.
• 정밀도: 다수-카운트 정보 논증을 사용함으로써, 이전의 두-카운트 분석에 비해 선행 계수에 대한 경계를 크게 좁혀 불확실성을 3배 미만의 인자로 줄였습니다.

저자들은 최적의 계수 $C^*$의 정확한 값을 결정하는 것이 여전히 미해결 과제로 남아 있다고 명시했습니다. 또한, 본 결과가 고정된 서로소 그룹에 적용되며, 중첩되거나 데이터 의존적인 그룹은 별도의 민감도 분석이 필요함을 언급했습니다. 이 메커니즘은 편향되어 있지만( $-\sigma^2$ 드리프트 때문), 기대 절대 오차를 최소화하도록 특별히 조정되었습니다.