차등 프라이버시·모든 인접 입력과 사건

프라이버시는 출력 분포의 성질이다

한 사람당 이진 답 하나가 들어 있는 작은 고정 크기 설문을 생각해 봅시다. 근사 개수는 알고 싶지만 공개 결과가 어느 한 답에 지나치게 의존하지 않게 하고 싶습니다. 이름을 지웠다는 설명만으로는 그 의존성이 수학적으로 제한되지 않습니다. 보호할 변화·공개할 메커니즘·비교할 확률을 먼저 정해야 합니다.

이 실습의 n은 1부터 6까지이며 공개된 고정값입니다. 데이터는 n개 비트 벡터이고 인접 입력은 한 사람의 비트를 교체한 것입니다. 정해진 고정 크기 조건에서 비트 값을 보호하며 명단이나 공개 크기 n을 숨기는 모형은 아닙니다. 흔히 사용하는 추가·삭제 인접성과도 다릅니다. 비트 0을 1로 교체하면 벡터의 한 행이 바뀌지만 히스토그램에서는 두 항목이 변합니다.

데이터에 사전 확률분포를 가정하지 않습니다. 아래의 독립성은 개인들의 실제 데이터가 아니라 메커니즘이 사용하는 무작위 동전의 독립성입니다.

정의의 모든 정량자를 읽는다

ε≥0, δ≥0에 대해 선언한 인접성 아래 메커니즘 M이 (ε,δ)-차등 프라이버시를 만족하려면

$$\forall D\sim D',\quad\forall S\subseteq\mathrm{Range}(M),\qquad \Pr[M(D)\in S]\le e^\epsilon\Pr[M(D')\in S]+\delta$$

여야 합니다. 확률은 고정 입력에 대한 M의 무작위성에서 나옵니다. S에는 여러 출력이 함께 들어갈 수 있습니다. D와 D′를 뒤집은 방향도 별도 비교입니다. 같은 입력끼리의 비교는 이 비음수 매개변수에서 자동으로 성립합니다.

ε는 곱셈 계수 α=exp(ε)를 조절합니다. δ는 최악 사건 부등식의 덧셈 여유이며 문자 그대로 프라이버시를 잃는 사람의 비율이 아닙니다. δ=1이면 어떤 메커니즘도 부등식을 자명하게 통과하므로 그 통과만으로 유용한 보호를 주장하지 않습니다.

표준 배경은 Dwork·Roth의 The Algorithmic Foundations of Differential Privacy, 정의 2.4·3.2절을 참고하세요. 책의 기본 히스토그램 추가·삭제 인접성과 이 실습의 고정 크기 비트 교체 인접성은 구분해야 합니다. 아래의 개수 채널과 유한 인증은 후자를 명시적으로 사용합니다.

무작위 응답 개수 채널

각 개인은 확률 p로 자신의 비트를 보고하고 확률 1−p로 반전합니다. 공개하는 것은 보고된 1의 총개수 Y뿐입니다. 응답 벡터·개인 식별자·무작위 시드는 공개하지 않습니다. 참 개수가 c일 때

$$Y\ \overset{d}{=}\ \mathrm{Binomial}(c,p) +\mathrm{Binomial}(n-c,1-p)$$

이며 두 항은 독립입니다. 실제 비트 배치는 중요하지 않습니다. 기록을 순열로 바꾸어도 독립 인자들의 순서만 바뀌어서 총개수의 분포는 같습니다. 따라서 실제 인접 데이터 쌍은 참 개수 c와 c+1의 두 방향 중 하나로 표현됩니다. 2n개의 순서 있는 비자명한 개수 쌍이 이 모형의 모든 실제 인접 쌍을 다룹니다.

코드는 몬테카를로 표본 대신 모든 출력 확률을 계산합니다. pPercent가 정수이면 다음 생성 다항식을 곱합니다.

$$\bigl((1-p)+pz\bigr)^c\bigl(p+(1-p)z\bigr)^{n-c}.$$

z^y의 계수가 P_c(Y=y)입니다. 공통 분모는 100ⁿ이며 n≤6에서 정수 가중치는 안전한 정수 범위 안에 있습니다. 추가 분모 때문에 곱셈이 안전 범위를 넘는 주장 비교에는 BigInt 교차곱을 사용합니다.

사건 하나는 조회이며 전체 보장이 아니다

첫 그림은 선택한 두 분포를 비교합니다. 파랑은 P_D(Y=y), 주황은 P_{D′}(Y=y)이고 윤곽선이 사건 S입니다. 사건 마스크는 선택한 출력들의 2ʸ 합입니다. 3은 {0,1}, 16은 {4}입니다. n보다 큰 불가능 출력의 비트는 무시하며 요청·유효 마스크를 함께 표시합니다.

작은 참 개수 조회는 n−1로 제한하고 방향 입력으로 c→c+1 또는 반대를 고릅니다. 이 입력들은 메커니즘을 관찰할 뿐입니다. 주장 α·δ, 사건, 조회 쌍을 바꿔도 채널 분포는 바뀌지 않습니다.

선택한 S에서 P_D(S)와 αP_{D′}(S)+δ를 비교합니다. 통과는 그 쌍과 그 사건에 대한 결과입니다. 정의에는 여전히 모든 쌍과 모든 사건이라는 정량자가 남아 있습니다.

모든 사건에 대한 최대화를 정확히 푼다

순서 있는 한 쌍에서 P_y=P_D(Y=y), Q_y=P_{D′}(Y=y)라고 합시다. 임의의 사건 S에 대해

$$P(S)-\alpha Q(S)=\sum_{y\in S}(P_y-\alpha Q_y)$$

입니다. 음수 항을 넣으면 합이 커지지 않고 양수 항을 빼면 이득을 잃습니다. 따라서

$$\max_S[P(S)-\alpha Q(S)] =\sum_y[P_y-\alpha Q_y]_+, \qquad[t]_+=\max(0,t)$$

입니다. 최대 사건은 엄격히 양수인 원자를 전부 포함합니다. 최댓값이 0이면 공집합도 최대 사건이며 프라이버시 위반을 뜻하지 않습니다. 이 값을 모든 순서 있는 인접 개수 쌍에서 다시 최대화하면 δ_min(α)를 얻습니다. 주장 δ가 이 값 이상일 때 정확히 전체 부등식을 만족합니다.

이 항등식은 공격을 추측하지 않고 모든 부분집합을 다룹니다. 검사에서는 별도로 모든 유한 부분집합을 열거해 최대값을 대조합니다. 인증 그림에는 현재 조회한 분포뿐 아니라 전체를 최대화하는 쌍과 사건이 표시됩니다.

α=1에서는 그 차이가 인접 분포의 총변동 거리입니다.

$$\sum_y[P_y-Q_y]_+=\frac12\sum_y|P_y-Q_y|.$$

δ=0이면 각 원자의 곱셈 부등식을 더해 모든 사건을 보장할 수 있습니다. δ>0에서는 각 단일 원자마다 δ를 붙여 검사하는 것으로 충분하지 않습니다. δ는 사건 전체에 한 번 허용되는 여유이며 원자마다 따로 쓰는 예산이 아닙니다.

모든 사건을 만족하는 순수 프라이버시 예제

n=4, p=3/4, α=3, δ=0을 불러오세요. 바뀐 개인의 응답 확률 비는 최대 3입니다. 전체 응답 벡터에서는 변하지 않은 독립 인자들이 두 입력 사이에서 약분됩니다. 개수 출력 사건에 속하는 응답 벡터 확률을 더해도 같은 상계를 보존합니다.

상계는 빡빡합니다. 적절한 방향으로 한 비트를 바꾸면 모두 1로 보고되는 출력의 확률 비가 p/(1−p)에 도달합니다. 따라서 p<1에서

$$\epsilon_{\rm pure}=\ln\frac{p}{1-p}$$

입니다. p=3/4이면 ln3이고 δ_min(3)=0입니다. 전체 패널은 조회 사건 {0,1}, c=1→2뿐 아니라 모든 순서 있는 개수 쌍과 사건을 인증합니다.

n명이 무작위화한다고 비용을 n·ln3으로 더하지 않습니다. 이 비교에서 바뀌는 기록은 한 사람뿐이어서 나머지 인자들이 약분됩니다. 같은 사람에게 여러 번 새 무작위 응답을 받아 공개하는 문제는 다음 단원의 구성 문제입니다.

통과한 사건이 구체적 위반을 놓칠 수 있다

두 번째 예제는 n=4, p=0.9, α=3, 주장 δ=0.05입니다. c=2→3, 사건 {4}에서는

$$P(S)=0.0081,\qquad Q(S)=0.0729,\qquad \alpha Q(S)+\delta=0.2687$$

여서 쉽게 통과합니다. 하지만 같은 쌍의 사건 {0,1,2}에서는 차이가 0.1042로 이미 0.05를 넘습니다. 전체 쌍을 최대화하면 더 큽니다.

$$D:c0,\quad D':c1,\quad S=\{0\},\qquad 0.6561-3(0.0729)=0.4374=\frac{2187}{5000}.$$

전체 주장은 실패합니다. δ=0.437은 여전히 기준보다 작고 0.438은 큽니다. 이 판정에는 반올림한 글자가 아니라 유리수 부등식을 사용합니다.

이 채널의 최소 순수 ε는 ln9입니다. 양의 δ를 허용할 때도 그보다 작은 ε가 모두 불가능하다는 뜻은 아닙니다. 덧셈 항을 허용하면 다른 프라이버시 프로필의 점이 가능하지만, 유리한 사건 하나를 보고 가정하지 말고 정확히 계산해 명시해야 합니다.

여기서 δ가 측정하는 양

Q_y>0이면 쌍별 프라이버시 손실을 L(y)=ln(P_y/Q_y)로 정의합니다. 위의 최대 사건은 L(y)>ε인 출력들을 포함합니다. 하지만

$$\delta_{\rm pair}(\epsilon) =\sum_{y:L(y)>\epsilon}P_y\bigl(1-e^{\epsilon-L(y)}\bigr)$$

이지 단순히 그 집합의 확률은 아닙니다. δ를 한 개인이 노출될 확률로 바로 바꾸면 안 되는 이유입니다. Q_y=0<P_y인 원자는 P_y만큼 기여합니다. 둘 다 0이면 우도비는 정의되지 않지만 사건 차이에는 0을 더합니다. 임의의 0이나 작은 평활화 확률을 넣는다고 문제가 해결되지는 않습니다.

프라이버시와 추정 오차는 별도 계산이다

보고 총개수의 평균은 다음과 같습니다.

$$\mathbb E[Y\mid c]=n(1-p)+(2p-1)c.$$

p>1/2에서 불편 개수 추정식은

$$\widehat c=\frac{Y-n(1-p)}{2p-1},\qquad \mathbb E[(\widehat c-c)^2\mid c] =\frac{np(1-p)}{(2p-1)^2}$$

입니다. 실제 비트와 관계없이 각 무작위 응답 비트의 분산은 p(1−p)이고 동전들은 독립입니다. 합의 분산을 추정식의 계수로 나누면 위 평균제곱오차가 나옵니다. 임의의 고정 데이터에 조건부인 식이며 데이터 사전분포가 필요하지 않습니다.

n=4, p=3/4에서 추정값은 −2,0,2,4,6이며 MSE는 3입니다. [0,n] 밖의 값도 자르지 않습니다. 자르면 편향과 위험이 바뀌어 별도 분석이 필요합니다. p=0.9에서는 MSE가 0.5625로 줄지만 순수 프라이버시 매개변수는 더 약해집니다. 특정 추정식·채널의 관계이며 모든 문제의 보편적인 프라이버시–정확도 곡선은 아닙니다.

두 경계가 차이를 분명하게 보여 준다

p=1/2이면 각 기록의 응답은 공정한 동전입니다. 모든 참 개수에서 같은 Binomial(n,1/2) 분포가 나옵니다. 최소 ε=0, 최소 δ=0입니다. 역산식은 2p−1=0으로 나누므로 사용할 수 없고 Y에는 개수 정보가 없습니다. 추정식이 미정이라는 사실과 프라이버시 손실 무한대는 다릅니다.

p=1이면 공개 개수가 참 개수와 같습니다. 추정 오차는 0입니다. 인접 개수의 지지는 겹치지 않아서 한 개수만 포함한 사건에서 P=1,Q=0입니다. 유한 순수 ε는 존재하지 않고 모든 유한 α에서 δ≥1이 필요합니다. 패널은 무한 순수 ε를 0이나 잘못된 숫자로 숨기지 않고 명시적으로 표시합니다.

관측 가능한 출력과 무작위성 가정은 중요합니다. 원래 기록·무작위 시드·추가 메타데이터까지 공개하면 다른 메커니즘이며 다시 분석해야 합니다. 이 유한 인증이 그런 프로그램까지 조용히 포함하지는 않습니다.

프라이버시 프로필을 읽는다

아래 그림의 가로축은 ε 자체가 아니라 α=exp(ε)입니다. 파란 값은 허용된 α 격자 1.0,1.1,…,10.0의 정확한 전체 필요 δ이며 연결선은 읽기 안내입니다. 주황은 주장 δ입니다. 선택한 파란 점이 주황 점 이하에 있어야 통과합니다.

n이나 p는 채널을 바꿉니다. α는 프라이버시 주장과 프로필 조회를 바꾸고 δ는 수평 예산선을 바꿉니다. 인접 쌍·사건 입력은 관찰만 바꿉니다. 배지는 정확한 정수 분자 비교로 결정하고 로그와 소수 표시는 표시용 수치입니다.

연습 문제와 해설

1. n=1,p=3/4,α=1에서 필요한 δ는 얼마인가요? 두 분포는 (3/4,1/4)와 (1/4,3/4)이므로 최대 차이는 1/2입니다. 이 인접성에서 (0,1/2)-DP이고 순수 보장은 (ln3,0)입니다.
2. 단일 출력 사건은 모두 통과해도 합친 사건은 실패할 수 있나요? P=(.4,.4,.1,.1), Q=(.1,.1,.4,.4), α=1,δ=.3으로 두세요. 모든 단일 사건은 양방향 모두 통과하지만 {0,1}의 차이는 .6으로 실패합니다. δ를 원자별로 따로 쓸 수 없습니다.
3. n=4,p=.9에서 주장 δ를 .437에서 .438로 올리면 메커니즘도 바뀌나요? 아닙니다. 모든 분포·순수 매개변수·추정 위험은 같습니다. 정확한 필요량 .4374를 주장이 덮는지만 바뀝니다.
4. 결정적 개수에서도 전체 출력 사건은 왜 통과하나요? 두 사건 확률이 모두 1이어서 1≤α+δ입니다. 언제나 맞는 사건 하나로 정의 전체를 만족시키지는 못합니다. 해당 개수 하나의 사건이 결정적 채널의 위반을 보여 줍니다.

결과의 범위

이 인증은 유한 채널·교체 인접성·선언한 개수 출력에 대한 수학적 결과입니다. 임의의 배포 시스템이나 법적 준수 판단이 아닙니다. 다른 메커니즘에는 자신의 전체 정의역·무작위성·출력 형식·구성을 다루는 증명이나 검증이 필요합니다.

다음 단원에서는 ε·δ의 구성을 다루며, 한 번 정제한 출력을 복사하는 것과 새 독립 공개를 여러 번 수행하는 것을 구분합니다.