차등 프라이버시 구성·새 질의와 결과 복사

보호 대상은 답변 하나가 아니라 전체 공개 기록이다

같은 사람에게 같은 질문을 여러 번 하면, 각각의 답변이 시끄러워도 여러 답을 모아 원래 값을 추정할 수 있습니다. 따라서 프라이버시 보장은 관찰자가 얻는 답변들의 결합 분포를 대상으로 해야 합니다. 각 답변을 따로 보았을 때의 분포만 확인하면, 답변 사이의 관계가 드러내는 정보를 놓칠 수 있습니다.

이 단원의 데이터는 한 사람의 비트 x∈{0,1}입니다. 인접 입력은 x=0을 x=1로 교체하는 것입니다. 여러 사람의 비트를 각각 한 번 무작위화하던 이전 단원과 달리, 같은 비트에 관해 여러 번 공개합니다. 보호할 변화가 무엇인지 먼저 고정해야 ε를 몇 번 더할지 결정할 수 있습니다.

공개 기록은 관찰자가 볼 수 있는 모든 출력입니다. 호출 횟수나 화면에 숫자가 추가된 횟수만 세면 충분하지 않습니다. 이미 공개한 숫자를 복사하는 것, 새 난수로 응답을 다시 생성하는 것, 난수 자체를 공개하는 것은 모두 다른 메커니즘입니다.

실습은 세 가지 방식을 제공합니다. 새 응답 모드는 같은 비트에 대해 독립 난수로 k개의 응답을 만듭니다. 복사 모드는 응답을 한 번만 만든 뒤 같은 응답을 k번 표시합니다. XOR 모드는 공정한 비트 R에 대해 (R,x XOR R)을 공개합니다. 마지막 모드는 잘못된 구성 논리를 보여 주는 반례이며 k와 p 입력은 사용하지 않습니다.

ε와 δ는 선택한 주장에 붙는 수치다

두 인접 입력의 전체 기록 분포를 P,Q라고 하면, 모든 출력 사건 S에 대해 양방향으로 다음 부등식이 성립해야 합니다.

$$P(S)\le e^\epsilon Q(S)+\delta.$$

α=e^ε라고 쓰겠습니다. 고정한 α에서 필요한 정확한 최소 δ는

$$\delta_*(\alpha)=\max\left\{\sum_z[P_z-\alpha Q_z]_+,\sum_z[Q_z-\alpha P_z]_+\right\}$$

입니다. 한 방향에서는 양의 차이를 만드는 출력만 모두 모으면 최대 사건을 얻습니다. 음의 차이를 더하면 사건의 차이가 줄어들므로 제외합니다. 다시 반대 방향과 비교하면 모든 사건과 두 방향을 다룹니다. 이는 그럴듯한 공격 몇 개를 표본으로 검사하는 방법이 아닙니다.

전체 주장 α와 δ는 메커니즘을 바꾸지 않고 검증할 주장을 바꿉니다. 별도의 단계별 예산 α₀는 구성 정리용 입력입니다. 같은 숫자를 입력해도 역할이 다르므로, 단계별 ε를 전체 ε로 그대로 사용하면서 계속 새 응답을 수집해서는 안 됩니다.

새 응답의 확률 분포를 직접 유도한다

각 응답은 확률 p로 실제 x를 보고하고 확률 1−p로 반전합니다. x=0일 때 1이 t번 나온 특정 길이 k 기록의 확률은 (1−p)ᵗpᵏ⁻ᵗ입니다. 같은 1 개수의 기록은 조합 수만큼 있으므로 공개된 1의 개수 T의 분포는

$$P(T=t\mid x=0)={k\choose t}(1-p)^t p^{k-t},\qquad P(T=t\mid x=1)={k\choose t}p^t(1-p)^{k-t}$$

가 됩니다. 독립성은 실제 데이터의 생성 과정이 아니라 메커니즘이 새로 만드는 난수에 관한 가정입니다.

왜 전체 비트 기록 대신 개수 분포를 그려도 될까요? 이 동일한 채널에서는 같은 개수의 기록들이 같은 우도비를 가집니다. 따라서 P−αQ의 부호도 한 개수 집합 안에서 같습니다. 그 기록들을 묶어도 양의 차이 합이 그대로입니다. p=1의 결정적 경우도 두 가능한 기록이 서로 다른 개수로 남으므로 같은 결론을 직접 확인할 수 있습니다. 임의의 출력 요약이 정확한 프라이버시 손실을 보존한다는 일반 주장은 아닙니다.

1/2≤p<1일 때 가장 큰 기록 우도비는

$$\left(\frac p{1-p}\right)^k$$

입니다. x=0에서 모두 0인 기록이 이 비율을 달성하고 반대 방향에서는 모두 1인 기록이 달성합니다. 따라서 최소 순수 ε는 k ln(p/(1−p))입니다. p=1/2에서는 두 분포가 같아 0이고, p=1에서는 지지집합이 분리되어 유한한 순수 ε가 없습니다.

두 번 새로 공개하는 예제를 손으로 계산한다

두 번째 안내 예제를 불러오세요. p=3/4, k=2이고 전체 주장은 α=3, δ=0입니다. 개수 0,1,2에 대한 두 분포는

$$P=(9,6,1)/16,\qquad Q=(1,6,9)/16$$

입니다. 사건 {0}에서 P−3Q는 9/16−3/16=6/16=3/8입니다. 다른 두 출력은 이 방향에서 양의 차이를 만들지 않습니다. 반대 방향에서는 사건 {2}가 같은 최댓값을 만듭니다. 그러므로 정확한 필요 δ는 3/8이고 현재의 δ=0 주장은 실패합니다.

한 번의 응답에는 최소 ε=ln3이 충분했지만, 두 번의 새 응답에는 ln9가 필요합니다. 전체 α를 9로 바꾸면 필요한 δ가 정확히 0이 됩니다. 같은 비트에 관한 독립 응답을 추가하면 관찰자가 그 비트에 대한 증거를 더 모을 수 있다는 사실이 수치에 반영됩니다.

k=3, α=3일 때는 P=(27,27,9,1)/64, Q는 그 반대 순서입니다. 출력 0의 차이는 24/64=3/8이고 출력 1의 차이는 정확히 0입니다. 따라서 필요 δ가 k=2와 같습니다. 새 기록에서 마지막 응답을 버리면 이전 기록을 얻으므로 프라이버시 프로필이 좋아지지는 않지만, 모든 예산에서 매번 엄격히 나빠져야 하는 것은 아닙니다.

이미 공개한 결과의 복사는 후처리다

k=2와 p=3/4를 유지하고 복사 모드로 바꾸세요. 비트 B를 한 번 생성하고 (B,B)를 공개합니다. 두 개수 분포는

$$P=(3/4,0,1/4),\qquad Q=(1/4,0,3/4)$$

입니다. 가능한 출력은 개수 0과 2뿐입니다. 최대 우도비는 여전히 3이고 최소 순수 ε는 ln3입니다. B로 복사 기록을 만들 수 있고 복사 기록에서 B를 되찾을 수도 있으므로 두 공개물의 프라이버시 프로필이 정확히 같습니다.

화면에는 두 비트가 있어도 보호 비트에 대한 실제 질의는 한 번입니다. 그러나 이 사실을 원래 데이터에 접근하면서 같은 난수를 임의로 재사용해도 된다는 뜻으로 확대하면 안 됩니다. 이미 공개한 값만의 함수가 후처리입니다. x에 다시 접근하는 두 번째 계산은 별개의 정보 공개일 수 있습니다.

모든 과거 기록에서 성립하는 조건부 보장을 합산한다

Dwork·Roth 교재의 3.5절과 부록 B의 기본 구성 정리는 단계별 메커니즘이 모든 고정된 과거 공개 기록에서 (εᵢ,δᵢ)-DP이면 전체 기록에 다음의 충분한 보장을 준다고 설명합니다.

$$\left(\sum_i\epsilon_i,\min\{1,\sum_i\delta_i\}\right).$$

일반적인 적응적 구성 정리에 난수의 독립성이 반드시 필요한 것은 아닙니다. 핵심은 과거 기록을 고정했을 때 다음 메커니즘이 유효한 DP 보장을 갖는다는 조건입니다. 이 실습의 새 응답 모드에서는 독립 난수를 사용하기 때문에 구체적인 곱 분포를 계산할 수 있습니다. 정리의 일반 조건과 특정 실습의 분포 가정을 구분하세요.

순수 프라이버시는 기록 확률을 단계별 조건부 확률의 곱으로 분해하면 이해하기 쉽습니다. 각 단계의 우도비 상계 e^εᵢ를 곱하면 e^(Σεᵢ)가 됩니다. 이를 사건 전체에 합하면 사건 부등식을 얻습니다. 0으로 나누어야 하는 출력에서는 우도비 대신 원래 확률 부등식을 직접 사용합니다.

근사 프라이버시의 δ를 잘못 증폭하지 않는 유도

두 단계의 출력 사건 S에 대해 첫 출력 s를 고정한 두 번째 출력 단면을 S_s라고 합시다. 다음의 0과 1 사이 함수를 정의합니다.

$$h(s)=\min\{1,e^{\epsilon_2}Q_2(S_s\mid s)\}.$$

두 번째 단계의 조건부 보장은 P₂(S_s|s)≤h(s)+δ₂를 줍니다. 첫 단계의 사건 부등식은 임의의 0≤h≤1 함수의 기대값에도 적용됩니다. h를 높이 u에서 잘라 얻은 사건 {h>u}에 부등식을 적용하고 u=0부터 1까지 적분하면 확인할 수 있습니다. 따라서

$$\begin{aligned} P(S)&\le \mathbb E_{P_1}h+\delta_2\\ &\le e^{\epsilon_1}\mathbb E_{Q_1}h+\delta_1+\delta_2\\ &\le e^{\epsilon_1+\epsilon_2}Q(S)+\delta_1+\delta_2. \end{aligned}$$

반대 방향도 같고 단계 수에 대해 반복하면 합산 결과를 얻습니다. h≤1이라는 제한이 첫 단계의 δ₁을 불필요하게 e^ε₂배 하지 않게 해 줍니다. δ를 독립적으로 표시된 개인정보 노출 사건의 확률이라고 가정하지 않고도 유도됩니다.

충분한 구성 상계와 채널의 정확한 최솟값을 비교한다

별도 입력 α₀에서 ε₀=lnα₀를 정하고, 한 응답의 정확한 필요 δ₀를 구합니다. 새 응답은 q=k, 복사는 q=1로 두어 구성 정리의 충분한 보장 (qε₀,min(1,qδ₀))를 표시합니다. 같은 합산 ε에서 실제 메커니즘의 정확한 필요 δ도 따로 계산합니다. 이 패널의 예산과 아래 곡선의 선택한 전체 주장은 별개의 조회입니다.

예를 들어 p=0.9, k=2, α₀=3이면 한 응답의 필요 δ₀는 0.9−3×0.1=0.6입니다. 정리의 합산 ε는 ln9이고 δ 상계는 min(1,1.2)=1입니다. 직접 계산한 두 분포는 (0.81,0.18,0.01)과 그 반대 순서이므로 α=9에서 정확한 필요 δ는 0.81−9×0.01=0.72입니다. 구성 정리가 틀린 것이 아니라, 특정 메커니즘에서 충분한 상계보다 더 날카로운 결과를 계산한 것입니다.

δ=1은 어떤 두 확률 분포에도 성립하는 자명한 보장입니다. 유용한 프라이버시의 증거로 해석하면 안 됩니다. 또한 원하는 수치가 더 좋아 보인다는 이유로 정확한 필요 δ보다 작은 값을 주장해서도 안 됩니다.

주변 분포만 보면 놓치는 공유 마스크 반례

XOR 모드에서 R은 공정 비트입니다. x=0이면 출력 (R,x XOR R)은 00 또는 11이고 각각의 확률은 1/2입니다. x=1이면 01 또는 10이 각각 1/2입니다. 각 좌표만 보면 x와 무관한 공정 비트이므로 각각의 주변 분포는 ε=0입니다. 그러나 두 좌표를 XOR하면 바로 x가 드러납니다.

첫 출력 R=r을 이미 알 때 두 번째 출력은 x XOR r로 결정됩니다. 이 조건부 분포는 x에 의존하며 유한한 순수 ε가 없습니다. 따라서 0과 0을 더할 수 있다는 주장에 필요한 조건부 가정이 성립하지 않습니다. 실습은 이 모드의 구성 정리 예산을 ‘—’로 표시하고, 전체 기록의 정확한 필요 δ가 모든 유한 α에서 1임을 보여 줍니다.

이 모드의 출력 숫자는 2R+(x XOR R)이라는 두 비트 인코딩입니다. 1의 개수가 아닙니다. 인코딩은 두 비트를 모두 보존합니다. 분석 도중 이를 임의로 개수로 바꾸면 공개 대상이 다른 메커니즘이 되어 버립니다. k와 p를 바꾸어도 이 반례의 분포와 보장은 변하지 않습니다.

정수 계산과 경계 조건을 확인한다

p는 정수 백분율로 입력합니다. 새 응답 개수 확률의 공통 분모는 100ᵏ이므로 k가 커지면 JavaScript의 안전한 정수 범위를 넘습니다. 이항계수, 확률 가중치, 양의 차이 합과 주장 비교를 BigInt로 수행합니다. 반환하는 정확한 정수와 분수는 문자열이고 그림의 좌표만 일반 숫자로 변환합니다. 직렬화 경계에 BigInt를 노출하지 않습니다.

p=1/2에서는 새 응답과 복사의 분포가 입력과 무관해 최소 ε=0입니다. 하지만 XOR은 다른 메커니즘이며 p를 사용하지 않으므로 여전히 x를 공개합니다. p=1에서는 새 응답과 복사 모두 실제 비트를 결정적으로 공개하여 모든 유한 α에서 필요 δ=1입니다. k=1에서는 새 응답과 복사의 모든 프라이버시 프로필이 같습니다. 복사 모드의 불가능한 중간 개수는 확률 0 그대로 두며 임의의 작은 확률을 추가하지 않습니다.

곡선의 파란 값은 정수 α=1부터 100까지에서 정확하게 계산합니다. 사이 선분은 시각적 안내입니다. 선택점은 입력한 0.1 간격 α에서 다시 정확히 계산하므로 선분 보간으로 주장 통과를 판정하지 않습니다.

연습 문제와 해설

1. p=3/4, k=2, 새 응답에서 α=1의 최소 δ는 얼마인가요? 차이 벡터는 (8,0,−8)/16이고 두 방향의 최대 차이는 각각 1/2입니다. 따라서 (0,1/2)-DP입니다.
2. 같은 설정에서 α=3, δ=0.374는 통과하나요? 필요 δ=3/8=0.375보다 작아서 실패합니다. δ=0.375는 정확히 통과합니다. 반올림된 표시 대신 유리수 교차곱으로 판단합니다.
3. 한 응답을 열두 번 복사하면 왜 ε가 열두 배 되지 않나요? 새 비밀 접근이 없고 이미 공개한 하나의 응답만으로 전체 복사 기록을 만들 수 있습니다. 복사 기록과 원래 응답은 서로 복원 가능합니다.
4. p=0.9, k=2, α₀=3의 단계별 δ, 합산 δ 상계, 합산 ε에서의 정확한 δ를 계산하세요. 각각 0.6, 1, 0.72입니다. 각 수치의 역할이 다릅니다.
5. XOR 반례에서 어떤 가정이 깨지나요? 첫 출력을 조건으로 한 두 번째 단계의 DP 보장입니다. 각 좌표의 주변 보장만으로 이 조건을 대신할 수 없습니다.
6. 출력 폐기를 이용한 후처리 원리로 새 질의를 무시해도 되나요? 아닙니다. 새 질의는 비밀 입력에 다시 접근합니다. 이미 공개한 답만의 함수와 다른 계산입니다.

AI 학습에 연결할 때 필요한 다음 단계

반복 학습에서는 잡음을 넣은 갱신들이 순서대로 공개될 수 있습니다. 올바른 분석은 인접성, 민감도, 표본 추출, clipping, 잡음 분포와 단계별 공개 대상을 함께 정해야 합니다. 이 단원은 정확히 열거 가능한 작은 채널로 구성의 논리만 분리합니다. 화면의 수치를 더하는 것만으로 임의의 학습 파이프라인을 인증하지 않습니다.

데이터에 의존한 종료 규칙이나 예산 선택을 추가한다면 그 규칙을 포함한 전체 기록에 유효한 accountant가 필요합니다. 고급 구성과 더 날카로운 계산법에도 별도의 가정과 증명이 필요합니다. 다음 단원은 구성 전에 유효한 한 단계 보장을 만드는 민감도와 잡음 메커니즘을 다룹니다.