Data Privacy

차분 프라이버시 (Differential Privacy) 는 데이터셋에 대한 수많은 질의에 대해 지나치게 정확한 답변을 공개하는 것이, 공격자가 민감한 데이터의 상당 부분을 재구성하도록 허용할 수 있다는 관찰에서 비롯된다.

1. 1.Reconstruction Attack

Reconstruction Attack은 공격자가 집계된 통계적 질의 응답으로써 실제 데이터셋의 개별 항목 대부분 또는 전부를 추론하는 공격 기법이다. 이를 통해 우리는 집계 통계만 공개했는데도 개별 개인의 민감한 정보가 복원될 수 있는가를 수학적으로 보일 수 있다.

ex) 회사 직원의 건강 정보

한 회사가 직원들에게 건강 보험을 제공하기 위해, 보험사에 주기적으로 다음과 같이 질의한다.

• “특정 날짜에 태어나고, 특정 우편번호에 거주하며, 특정하기 쉬운 특이 질환을 앓고 있는 직원은 몇 명인가?”

만약 답변이 1이고, 회사가 해당 생년월일과 우편번호에 해당하는 직원이 한 명뿐임을 알고 있다면, 회사는 즉시 해당 직원이 특이 질환을 앓고 있다는 민감한 건강 정보를 알게 된다.

작은 수치를 억제하여, 예를 들어 정확한 작은 숫자를 제공하는 대신 “5 미만”이라고 답변함으로써 이를 방지하려 할 수도 있다. 하지만 다음 두 가지 질의를 고려해보자.

1. 특정 날짜 이전에 입사했으며 해당 질환을 앓고 있는 직원은 몇 명입니까?
2. 특정 날짜의 다음 날 이전에 입사했으며 해당 질환을 앓고 있는 직원은 몇 명입니까?

만약 답변이 정확히 1만큼 차이가 난다면, 회사는 다시 민감한 정보를 얻을 수 있게 된다.

이 문제는 프라이버시의 출발점이 된다. 우리가 흔히 “합계나 평균만 공개하면 안전하지 않을까?”라고 생각하지만, Differential Privacy는 바로 그 믿음이 틀릴 수 있음을 느낌이 아닌, 수학적으로 엄밀히 알려줄 것이다.

1.1. 카운팅 쿼리

데이터셋 $D=(d_1,\dots ,d_n)\in \{0,1{\}}^n$ 에서, 각 $d_i$가 $i$번째 개인에 대한 민감 속성의 유무를 나타낸다고 가정하자. 이때, 임의의 쿼리에 속하는 개인을 나타내는 부분집합 $S\subseteq \{1,\dots ,n\}$ 에 대해 개수를 반환하는 카운팅 쿼리 $q_S$를 다음과 같이 정의할 수 있다.

$$q_S(D)=\sum _{i\in S}{d}_i$$

이는 $S$ 안에 1이 몇개 존재하는지를 알려주는 것으로, 공격자가 고르는 충분히 많은 쿼리 $S_j$에 대한 응답 $q_{S_j}$를 얻을 수 있다면, 역으로 $d_i$를 추론할 수 있을 것이다. 이는 충분히 많은 선형 제약식이 주어지면, 원래의 이진 벡터(여기서는, $D$)를 복원할 수 있음을 시사한다.

1.2. Reconstruction Attack & Error

만약 우리가 통계 질의에 대한 응답에 특정 오차 범위 내의 노이즈를 섞으면 Reconstruction Attack을 피할 수 있을까?

우리가 질의하는 쿼리 $S_j$에 대한 실제 카운팅 정답을 $q_{S_j}$, 노이즈가 섞인 응답을 $a_j$라 하자. 이때, 공격자는 충분히 많은 질의응답을 얻음으로써 최적화된 데이터셋 $\hat{D}$를 다음과 같이 얻으려 시도한다.

$$\hat{D}=\underset{\text{질의 오차의 최댓값을 가장 줄이는 D^}}{\underbrace{\underset{D\in {\left\{0,1\right\}}^n}{\arg \min }\stackrel{\text{가장 큰 질의 오차}}{\overbrace{\underset{1\le j\le m}{\max }\underset{\text{각 질의 Sj에 대한 오차}}{\underbrace{\left|q_{S_j}(D)-a_j\right|}}}}}}$$

만약 응답 $a_S$가 실제 정답 $q_S$와 너무 많이 다르다면, 이는 통계응답에 대한 의미를 잃어버리므로, 결국 질의에 대한 오차 비율에는 한계가 존재해야 한다. 따라서 이제 모든 쿼리의 응답이 “충분히” 정확하다는 가정을 더하려 한다.

어떤 $\alpha <1$이 존재하여, 모든 질의 $S$에 대해 $a_S$와 $q_S$ 사이에 다음의 오차 상한이 존재한다고 하자.

$$\left|a_S-q_S(D)\right|<\alpha n$$

이 제약이 성립한다면, 노이즈가 섞인 응답으로 부터 재구축되는 데이터셋 $\hat{D}$도 충분히 원본의 데이터셋 $D$와 가까워질 수 있지 않을까?

1.3. Dinur-Nissim Reconstruction Attack 1

Theorem 1. Dinur-Nissim Reconstruction Attack 1

모든 쿼리의 응답 오차가 $\alpha n(\alpha <1)$ 의 상한을 가질 때, Reconstruction Error는 최대 $4\alpha n$이다.

$$\sum _{i=1}^n|D_i-{\hat{D}}_i|\le 4\alpha n.$$

Proof of Theorem 1. Dinur-Nissim Reocnstruction Attack 1

데이터셋 $D$와 Reconstructed 데이터셋 $\hat{D}$의 오차 집합 $A_{01},A_{10}$을 다음과 같이 정의하자.

$$A_{01}=\left\{i:{\hat{D}}_i=0,D_i=1\right\}{A}_{10}=\left\{i:{\hat{D}}_i=1,D_i=0\right\}$$

이때 전체 오차는 다음과 같이 표현될 수 있다.

$$\sum _{i=1}^n\left|D_i-{\hat{D}}_i\right|=\left|A_{01}\right|+\left|A_{10}\right|$$

만약 오차 상한이 $\alpha n$일 때, 이 값이 $4\alpha n$보다 크다고 가정하자. 비둘기집의 원리에 의해 $\left|A_{01}\right|,\left|A_{10}\right|$ 둘 중 하나는 $2\alpha n$보다 커야하고, 이 둘 중 어느것을 예시로 잡아도 일반성을 잃지 않기에 여기서는 $\left|A_{10}\right|$이 $2\alpha n$보다 크다고 가정해보자.

$$\left|A_{10}\right|=\mid q_{A_{10}(D)}-q_{A_{01}(D)}>2\alpha n$$

그런데, 오차 상한 $\alpha n$으로 부터 다음의 식도 성립해야 한다.

$$\begin{array}{rl}\left|q_{A_{10}}(D)-q_{A_{10}}(\hat{D})\right|& \le \left|q_{A_{10}}(D)-a_{A_{10}}\right|+\mid a_{A_{10}}-q_{A_{10}}(\hat{D})\mid \\ & \le \alpha n+\alpha n=2\alpha n\end{array}$$

이 두가지 식은 동시에 성립할 수 없는 모순이다. 따라서 전체 Reconstruction Error가 $4\alpha n$보다 크다는 가정이 틀렸고, 따라서 전체 Reconstruction Error는 $4\alpha n$보다 작다.

이 증명이 중요한 이유는, 공격자가 $A_{10}$ 을 미리 알아야 하는 것이 아니라는 점이다.

“모든 쿼리에 답을 받았다”는 가정 아래에서는, 공격자는 모든 부분집합에 대한 답을 이미 들고 있으므로, 복원된 해 $\hat{D}$ 와 실제 $D$ 를 가르는 결정적인 집합도 결국 응답 목록 안에 포함된다. (만약 모든 응답 $q_S$가 $\pm 0.01n$의 노이즈를 가져도, 우리는 무려 $0.96n$명의 정보를 완벽하게 복구할 수 있다!)

다만, $n$이 1 증가함에 따라 가능한 쿼리 집합의 크기는 지수적으로 증가하기에 현실적인 방법은 아니다. 이제 두 번째 정리를 통해 다항 개수의 랜덤 쿼리 스케일로 Reconstruction Attack을 현실적인 범위로 들고와 보자.

1.4. Dinur-Nissim Reconstruction Attack 2

Theorem 2. Dinur-Nissim Reconstruction Attack 2

만약 $m=20n$개 쿼리 응답의 오차 상한이 $\alpha n$이면, 높은 확률로 Reconstruction Error의 상한은 $256{\alpha }^2{n}^2$이다. (이 상한은 $\alpha \ll \frac{1}{\sqrt{n}}$일 때 의미가 있다.)

Proof of Theorem 2. Dinur-Nissim Reconstruction Attack 2

원본 데이터셋 $D\in {\left\{0,1\right\}}^n$와 $\hat{D}$의 후보가 되려는, 적어도 $k\ge 256{\alpha }^2{n}^2$개의 좌표에서 다른 데이터셋 $D_0\in {\left\{0,1\right\}}^n$ 을 가정하자.

$$B=\left\{\hat{D}:\hat{D}\text{ and }D\text{ disagree on at least }256{\omega }^2{n}^2\text{ coordinates}\right\}$$

만약 어떠한 후보 $D_0$가 실제 $\hat{D}$가 되려면, 적어도 실제 데이터 $D$보다 정답 $q_S$에 대해 더 큰 오차를 가지면 안된다. 이미 $D$ 자신이 오차 상한 $\alpha n$을 만족하므로 최적해인 $\hat{D}$도 당연히 이 조건을 만족해야만 후보가 될 수 있고, 따라서 아래의 식으로 제약된다.

$$\underset{j}{\max }\left|q_{S_j}(D_0)-a_j\right|\le \alpha n$$

이제 어떤 쿼리 $S_j$에 대해, $\left|q_{S_j}(D_0)-q_{S_j}(D)\right|>4\alpha n$이라고 하자. 삼각부등식에 의해 다음이 성립해야 한다.

$$\begin{array}{rl}\left|q_{S_j}(D_0)-a_j\right|& \ge \left|q_{S_j}(D_0)-q_{S_j}(D)\right|-\left|q_{S_j}(D)-a_j\right|\\ & >4\alpha n-\left|q_{S_j}(D)-a_j\right|\\ & >4\alpha n-\alpha n=3\alpha n\end{array}$$

그러나 위의 두 식은 서로 모순 관계에 있다. 따라서 실제 데이터셋과 적어도 $k\ge 256{\alpha }^2{n}^2$개의 좌표에서 다른 데이터셋 $D_0$는 $\hat{D}$가 될 수 없다.

이제, 삼각부등식을 다시 써서 $\left|q_{S_j}(D_0)-q_{S_j}(D)\right|$의 상한을 구해보면 다음의 조건을 만족해야 처음의 제약식에 위배되지 않음을 알 수 있다.

$$\begin{array}{rl}\left|q_{S_j}(D_0)-a_j\right|& \ge \left|q_{S_j}(D_0)-q_{S_j}(D)\right|-\left|q_{S_j}(D)-a_j\right|\\ & >\left|q_{S_j}(D_0)-q_{S_j}(D)\right|-\alpha n\le \alpha n\\ \therefore \left|q_{S_j}(D_0)-q_{S_j}(D)\right|& \text{ must be }\le 2\alpha n\end{array}$$

하지만, 이 증명에서는 더 깔끔한 전개를 위해 이 상한을 더 넓혀 $4\alpha n$으로 잡고 나아가겠다.

지금 중요한 것은, 만약 임의의 $D_0$에 대해 $\left|q_{S_j}(D_0)-q_{S_j}(D)\right|>4\alpha n$이면, 우리는 $D_0$를 $\hat{D}$의 후보에서 자신있게 기각시킬 수 있다는 것이다.

이제, 임의의 쿼리 $s_j$에 포함되는 좌표를 지시하는 지시벡터 $F=(f_1,\dots ,f_n),f_i=1\text{ where }i\in s_j$를 통해 다음의 확률변수 $X$를 정의해보자.

$$X=\mid q_{s_j}(D)-q_{s_j}(D_0)\mid =\left|F\cdot (D-D_0)\right|$$

이 $X$는 임의 쿼리 $s_j$에 대한 오차 크기의 분포를 표현한다. 또한, CLT에 의해 충분히 큰 $n$에 대해 $X$는 가우시안처럼 행동하며, 이때의 분산은 다음과 같이 표현된다.

$$\mathrm{Var}(F\cdot (D-D_0))=\sum _{i=1}^n\mathrm{Var}(f_i(d_i-d_{0,i}))=\sum _{d_i\ne d_{0,i}}\frac{1}{4}=\frac{k}{4}\ge 64{\alpha }^2{n}^2$$

이를 가우시안 분포에 적용하면 $X\approx Z\sim \mathcal{N}(0,(8\alpha n{)}^2)$에서 다음과 같다.

$$\begin{array}{rl}\mathrm{Pr}\left[\left|F\cdot (D-D_0)\right|\le 4\alpha n\right]& \le \mathrm{Pr}\left[\left|Z\right|\le 4\alpha n\right]\\ & =\mathrm{Pr}\left[\left|Z\right|<\sigma /2\right]\\ & \fallingdotseq 0.38\le \frac{9}{10}\end{array}$$

우리는 앞서 만약 임의의 $D_0$에 대해 $\left|q_{S_j}(D_0)-q_{S_j}(D)\right|>4\alpha n$이면, 우리는$D_0$를 $\hat{D}$의 후보에서 자신있게 기각됨을 보였다.

여기에 앞의 확률 부등식을 결합하면, 임의의 복원 데이터셋 후보 $D_0$가 $k\ge 256{\alpha }^2{n}^2$개의 복원 오차를 갖는 나쁜 후보라면, $D_0$가 랜덤 쿼리를 무사히 통과해서 살아남을 확률은 아무리 커도 0.9라는 의미가 된다.

이제 앞에서 말한 $m=20$개의 랜덤 쿼리 $s_1,\dots ,s_m$와 이에 대한 응답을 생각해보자.

$\hat{D}$의 후보 $D_0$는 하나의 쿼리가 아닌 $m$개의 쿼리 응답에 대해 모두 $\left|q_{S_j}(D_0)-q_{S_j}(D)\right|>4\alpha n$을 만족해야만 한다. 따라서 $m개$의 쿼리를 모두 통과할 확률의 상한은 다음과 같아진다.

$$(0.9{)}^m=(0.9{)}^{20n}=(0.9^{20}{)}^n\approx 2^{-3.04n}<2^{-2n}$$

문제는 가능한 쿼리 개수가 $n$에 대해 지수적으로 증가하는, 총 $2^n$개이며, 따라서 나쁜 후보도 최대 $2^n$개 존재할 수 있다. 우리는 이 중 단 하나의 운 좋은 나쁜 후보가 우연히 $m$개의 쿼리를 통과하는 경우를 막기 위해 다음의 union bound를 쓸 수 있다.

$$\sum ^{2^n}{2}^{-2n}=2^n\times 2^{-2n}=2^{-n}$$

위 결과는 집합 $B$에 속하는 어떤 $D_0$라도 재구성 공격의 결과가 될 수 있는 (즉, $m$개의 질의 모두에서 $D_0$가 $D$에 비해 $4\omega n$보다 작은 오차를 보이는) 확률이 $2^{-n}$으로 매우 낮다는 것을 의미한다.

다르게 말하면, “재구성 오차가 $256{\omega }^2{n}^2$보다 크게 발생하는($D_0\in B$) 경우”는 높은 확률($1-2^{-n}$)로 발생하지 않는다.

따라서, 재구성 공격이 성공적으로 이루어질 경우, 그 결과인 $\hat{D}$는 원본 데이터셋 $D$와 최대 $256{\omega }^2{n}^2$개 미만의 좌표에서만 불일치할 것임을 의미하며, 이것이 재구성 오차의 상한이 된다.

when $\alpha =0.0001,n=10,000$

이 경우, Reconstruction Attack의 결과 $\hat{D}$의 오차 상한은 $256\times 0.0001^2\times 10,000^2=256$개이다.

이는 오차의 수가 $256{\alpha }^2{n}^2$ 보다 크면, 그런 후보는 랜덤 쿼리들 중 적어도 하나와 크게 충돌한다”는 구조를 수학적으로 증명하는 한편, 이 bound가 의미 있으려면 $\omega \ll \frac{1}{\sqrt{n}}$ 정도의 정밀도가 필요하다는 한계도 드러낸다.

즉, 질의 수를 줄일 수는 있지만, 그만큼 더 정밀한 응답이 필요한 Trade-Off 관계를 잘 보여준다.

---

이렇듯, 재구성 공격은 “너무 정확한” 집계 통계를 공개하는 것의 근본적인 한계를 보여주며, Trade-Off 가능한 프라이버시와 정확도 간의 추상적 경계를 수학적으로 분석할 필요와 함께, 앞으로 배울 Differential Privacy와 같이 프라이버시 손실을 형식적으로 정량화하는 엄격한 프레임워크의 필요에 대한 동기를 부여한다.

Reconstruction Attack을 막기 위해서는 신중한 노이즈 보정이 필수적이며, 그렇지 않으면, 약간 부정확한 통계조차도 프라이버시를 극단적으로 무너트릴 수 있다.

그렇다면, 원래 정보의 통계는 대충 유지하면서도 개인 정보를 감추기 위해서, 응답에 어떻게 노이즈를 추가해야할까?

2. Randomized Response

민감한 비트 $D_i\in \left\{0,1\right\}$를 가지는 데이터셋 $D\in {\left\{0,1\right\}}^n$에 대해, 개별 비트가 프라이버시를 지키기 위해 통계 수집을 위한 질의에 다음의 확률적 랜덤 응답 $Y_i$를 내뱉는다고 가정하자.

$$Y_i=\{\begin{array}{ll}{D}_i& \text{with probability}\frac{1}{2}+\gamma \\ 1-D_i& \text{with probability}\frac{1}{2}-\gamma \end{array}\text{where }0<\gamma \le \frac{1}{2}$$

$\gamma =\frac{1}{2}$일 때 $Y_i=D_i$로 프라이버시를 완전히 잃어버리고, $\gamma =0$일 때 $Y_i$는 완전 무작위 응답으로 바뀌어 프라이버시를 완전히 보호하는 대신 의미있는 정보를 전부 잃어버린다. 이러한 $Y_i$의 기댓값은 다음과 같이 계산된다.

$$\begin{array}{rl}\mathbb{E}[Y_i]& =D_i(\frac{1}{2}+\gamma )+(1-D_i)(\frac{1}{2}-\gamma )\\ & =2\gamma D_i-\gamma +\frac{1}{2}\end{array}$$

이때, 응답 $Y_i$로부터 개별 비트 추정량은 $\widehat{D_i}=\frac{Y_i+\gamma -\frac{1}{2}}{2\gamma }$이다.

이제 $D_i$에 대해 통계량$p=\frac{1}{n}{\sum }_{i=1}^n{D}_i$를 공개하고 싶다고 할 때, $Y_i$로부터 얻는 $\mathbb{E}[D_i]$로부터 얻게되는 통계 추정량 $\hat{p}$는 다음과 같다.

$$\hat{p}=\frac{1}{n}\sum _{i=1}^n\widehat{D_i}=\frac{1}{n}\sum _{i=1}^n\frac{Y_i+\gamma -\frac{1}{2}}{2\gamma }$$

이 추정량 $\hat{p}$는 다음의 전개에 따라 $p$에 대한 불편향 추정치임을 증명할 수 있다.

$$\begin{array}{rl}\mathbb{E}[\hat{p}]& =\mathbb{E}\left[\frac{1}{n}\sum _{i=1}^n\frac{Y_i-\gamma +\frac{1}{2}}{2\gamma }\right]\\ & =\frac{1}{n}\sum _{i=1}^n\frac{\mathbb{E}[Y_i]-\gamma +\frac{1}{2}}{2\gamma }\\ & =\frac{1}{n}\sum _{i=1}^n\frac{2\gamma D_i-\gamma +\frac{1}{2}+\gamma -\frac{1}{2}}{2\gamma }\\ & =\frac{1}{n}\sum _{i=1}^n{D}_i=p\end{array}$$

이제 우리는 개별 비트 $D_i$를 일정 확률로 뒤집는 $Y_i$로부터 통계 추정량을 얻어도, 이 기댓값이 원래 비트 $D_i$의 통계량과 일치함을 보았다. 그렇다면 $Y_i$로 부터 얻은 통계 추정량의 오차는 어느정도일까? 먼저 추정량 $\hat{p}$의 $p$로부터의 분산의 상한을 구할 수 있다.

$$\begin{array}{rl}\mathrm{Var}\left[\hat{p}\right]& =\mathrm{Var}\left[\frac{1}{n}\sum _{i=1}^n\frac{Y_i+\gamma -\frac{1}{2}}{2\gamma }\right]\\ & =\frac{1}{n^2}\sum _{i=1}^n\mathrm{Var}\left[\frac{Y_i+\gamma -\frac{1}{2}}{2\gamma }\right]\\ & =\frac{1}{n^2}\times \frac{1}{4{\gamma }^2}\sum _{i=1}^n\mathrm{Var}\left[Y_i\right]\end{array}$$ $$\begin{array}{rl}\mathbb{E}[Y_i]& =2\gamma D_i-\gamma +\frac{1}{2}\\ \mathbb{E}[Y_i^2]& =\mathbb{E}[Y_i]=2\gamma D_i-\gamma +\frac{1}{2}(\because \text{for each case }{Y}_i=0/1,Y_i^2=Y_i)\end{array}$$ $$\begin{array}{rl}\therefore \mathrm{Var}\left[\hat{p}\right]& =\frac{1}{4n^2{\gamma }^2}\sum _{i=1}^n\mathrm{Var}\left[Y_i\right]\\ & =\frac{1}{4n^2{\gamma }^2}\times n\gamma (1-\gamma )\\ & \le \frac{1}{16n{\gamma }^2}\end{array}$$

---

여기서 체비셰프 부등식 (Chebyshev’s Inequality)을 사용하자.

Lemma 1. Chebyshev's Inequality

확률 변수 $X$의 기댓값이 $\mathbb{E}[X]=\mu$이고, 분산이 $\mathrm{Var}\left[X\right]={\sigma }^2$일 때, 다음이 성립한다.

$$\mathrm{Pr}\left[\left|X-\mu \right|>k\sigma \right]\le \frac{1}{k^2}\text{for all }k>0$$

우리의 추정량 $\hat{p}$에 체비셰프 부등식을 적용하면 최대 분산 $\frac{1}{16n{\gamma }^2}$에 대해 다음의 확률 상한을 구할 수 있다.

$$\begin{array}{rl}\mathrm{Pr}\left[\mid \hat{p}-p\mid >k\sigma \right]& =\mathrm{Pr}\left[\left|\hat{p}-p\right|>\frac{k}{4\gamma \sqrt{n}}\right]\le \frac{1}{k^2}\\ \therefore \mathrm{Pr}\left[\left|\hat{p}-p\right|>\alpha \right]& \le \beta ,\alpha =\frac{k}{4\gamma \sqrt{n}},\beta =\frac{1}{k^2}\end{array}$$

이는 통계 추정량 $\hat{p}$가 높은 확률로 $p$로부터 $\alpha =\frac{k}{4\gamma \sqrt{n}}$ 안에 존재함을 알려준다. 또한, 범위 제약 $\alpha$와 확률 제약 $\beta$를 통해 데이터 크기 $n=\frac{1}{16{\gamma }^2\beta {\alpha }^2}$를 역산할 수 있게 되고 다음의 Trade-Off를 수학적으로 계산할 수 있다.

• 추정량 $\hat{p}$가 실제 $p$로부터 가까워지려면, 통계량은 더 많은 데이터를 포함해야 한다.
  • 작은 $\alpha$를 원한다면, $n$을 키워야 한다. ($n\propto \frac{1}{{\alpha }^2}$)
• 추정량 $\hat{p}$가 실제 $p$로부터 가까울 확률을 높이려면, 통계량은 더 많은 데이터를 포함해야 한다.
  • 작은 $\beta$를 원한다면, $n$을 키워야 한다. ($n\propto \frac{1}{\beta }$)
• 개별 데이터의 프라이버시 보존 강도를 높이려면, 통계량은 더 많은 데이터를 포함해야 한다.
  • 작은 $\gamma$를 원한다면, $n$을 키워야 한다. ($n\propto \frac{1}{{\gamma }^2}$)

---

이로써 우리는 개별 비트를 확률적으로 뒤집은 랜덤 비트를 사용해도, 전체 통계량을 unbiased하게 추정할 수 있음을 보였고, 이때의 추정량의 정확도 손실이 $n$에 어떻게 의존하는지를 분산 차원에서 정량화하여 이후 다룰 Differential Privacy의 대표적 예시 하나를 다루었다.

다만 지금까지 우리가 살펴본 예시는 특정한 이진 구조의 데이터셋과 평균 통계량 $p$에 한정되어 있다. 임의의 구조를 가진 데이터셋 $D$의 임의의 통계량 f(D)에 대해 어떻게 DP를 일반화할 수 있을까?

3. Differential Privacy

차분 프라이버시 (Differential Privacy)는 어떠한 데이터로부터의 계산 결과가 단 한 명의 개인 데이터 유무나 변경에 크게 영향을 받지 않도록 보장하는 공식적인 프라이버시 보장 프레임워크를 말한다.

다시 말해, 특정 개인의 데이터가 입력에 포함되든 안 포함되든, 알고리즘의 출력 분포는 거의 동일하게 유지되어 공격자가 특정 개인의 정보를 관찰해도 해당 개인에 대해 거의 정보를 얻지 못하게 한다.

3.1. 이웃 데이터셋 (Neighboring Datasets)

두 데이터셋 $D,D^{\prime }$이 단 한 개의 데이터에 대해서만 다를 때, 이 둘을 서로 이웃 데이터셋 (Neighboring Datasets)이라 한다. 데이터셋 $D^{\prime }$는 데이터셋 $D$에서 정확히 하나의 레코드만 변경하여 얻을 수 있는 모든 데이터셋에 대응되며, $D$와 $D^{\prime }$의 수학적 비교는 DP에서 한 개인의 데이터 레코드 변경이 계산량에 미치는 영향을 보여줄 수 있다.

3.2. $ϵ$-Differential Privacy

우리는 이전에 이진 비트 데이터셋에서 randomized response가 개별 비트 정보 복구를 어떻게 방해할 수 있는지 살펴보았다.

이를 더 General하게 표현하면, 한 개인의 데이터가 바뀌더라도 이 데이터셋에 대한 알고리즘의 출력 분포가 거의 안 바뀐다면, 그 개인의 정보는 보호된다고 볼 수 있다는 뜻이다. 이것이 단일 출력 값이 아닌, 출력 분포 전체의 안전성으로 프라이버시를 정의하는 Differential Privacy의 본질이다.

$ϵ$-Differential Privacy

무작위화된 메커니즘 $\mathcal{M}$의 가능한 모든 인접 데이터셋 $D,D^{\prime }$에 대해 가능한 모든 출력 부분집합 $O$에 대해 다음을 만족하면, $\mathcal{M}$은 $ϵ$-Differential Privacy를 만족한다고 정의한다.

$\mathrm{Pr}[\mathcal{M}(D)\in O]\le e^{ϵ}\mathrm{Pr}[\mathcal{M}(D^{\prime })\in O]$

• 무작위화된 메커니즘(Randomized mechanism) $\mathcal{M}$
  • 결정론적(deterministic) 메커니즘은 DP를 만족할 수 없으며, 반드시 무작위성을 도입해야 한다.
• $\mathcal{M}$의 출력 범위($\mathrm{Range}(\mathcal{M}))$의 가능한 모든 부분집합 $O$
• 프라이버시 예산 $\rho$
  • $p\to 0$일 때, $e^{\rho }\to 1$로 $\mathcal{M}(D)$와 $\mathcal{M}(D^{\prime })$의 출력 확률 분포가 유사해지며, $D,D^{\prime }$는 가능한 모든 이웃 데이터셋에 대해 양방향으로 성립하므로 다음이 자명하다.

$$e^{-ϵ}\le \frac{\mathrm{Pr}[\mathcal{M}(D)\in O]}{\mathrm{Pr}[\mathcal{M}(D^{\prime })\in O]}\le e^{ϵ}$$

$\mathcal{M}$이 결정론적 메커니즘 (Deterministic mechanism) 이라면?

$f(D)=\frac{1}{n}{\sum }_{i=1}^n{X}_i$에 대해, $\mathcal{M}(D)=f(D)$라면 ($\mathcal{M}$이 무작위화된 메커니즘이 아니라면),

$$\mathcal{M}(D^{\prime })=f(D^{\prime })=\frac{X_1+\cdots +X_i^{\prime }+\cdots +X_n}{n}=f(D)+\frac{X_i^{\prime }-X_i}{n}$$

위 상황에서 우리가 $f(D),f(D^{\prime })$을 모두 안다면, 개별 데이터 레코드 $X_i,X_i^{\prime }$에 대한 유의미한 추론이 가능하고, 심지어는 $f(D)$가 $D$로부터의 계산량인지, $D^{\prime }$으로부터의 계산량인지도 알 수 있다.

어떠한 결정론적 메커니즘 $\mathcal{M}$에 대해서도 위와 같은 문제가 발생하며, 이는 왜 $\mathcal{M}$이 무작위적 메커니즘이어야 하는지에 대한 확신을 제공한다.

이는 공격자가 $ϵ-$DP를 만족하는 $\mathcal{M}$의 출력으로부터 특정 개별 레코드가 사용되거나 혹은 사용되지 않았는지에 대한 확신의 정도를 $e^{ϵ}$으로 제한한다.

앞으로 위의 $ϵ-$DP의 정의로부터 나아갈 때, 아래의 사항을 기억하자.

• $ϵ$이 0에 가까워질수록 더 강도 높은 프라이버시를 제공하며, $ϵ=0$에서 완벽한 프라이버시를 얻는다.
• $ϵ-$DP는 그 정의상 모든 이웃 데이터셋 $D,D^{\prime }$에 대해 성립하므로 worst-case를 보장한다.
• 오차 계수가 $ϵ$이 아닌 $e^{ϵ}$이며, 이는 추후 계산 및 표기의 용이성을 위함이다. 또한, 0에 가까운 $ϵ$에서 $e^{ϵ}\approx 1+ϵ$으로의 치환이 가능하다.
• 우리가 정의한 DP는 단순히 $\mathcal{M}(D)$와 $\mathcal{M}(D^{\prime })$ 사이의 출력 분포의 유사성을 나타내는 개념으로, 다른 형태의 분포 간 거리를 사용한 대체 정의가 가능하다. (${\mathrm{D}}_{\mathrm{KL}}$ 등)
• 이웃 데이터에는 대체(Replacing), 삽입(Insertion), 삭제(Deletion)의 형태들이 존재하나, 이 중 대체가 삽입과 삭제의 조합으로 표현될 수 있으므로 다소 동등한 형태의 정의들로 간주할 수 있다. 따라서 여기서는 이 중 대표적으로 대체(Replacing) 연산을 통해 이웃 데이터셋을 정의한다.

---

가설 검정 측면에서 DP의 해석

어떠한 개별 레코드 $i$에 대해 다음의 귀무가설 $H_0$와 대립가설 $H_1$을 설정해보자.

• 귀무가설 $H_0$: 레코드 $i$가 데이터셋 $D$에 포함되어 있다.
• 대립가설 $H_1$: 레코드 $i$가 데이터셋 $D$에 포함되어 있지 않다.

$ϵ-$DP는 $\mathcal{M}$으로부터의 어떠한 테스트도 $H_0$와 $H_1$를 구별할 수 없게끔 보장하며, 그 로그 가능도비를 $ϵ$으로 제한됨을 보장한다.

코로나 환자의 체온 측정

코로나 환자의 체온 분포가 $\mathrm{Lap}(39,b)$이고, 비-코로나 환자의 체온 분포가 $\mathrm{Lap}(38,b)$라 하자. 우리는 환자의 체온 $T$가 주어졌을 때, 다음의 가설 중 하나를 채택해야 한다.

• 귀무가설 $H_0$: 환자가 코로나에 걸리지 않았음
• 대립가설 $H_1$: 환자가 코로나게 걸렸음

여기서 최적의 검사는 환자의 체온 $T$가 $T<38.5$인지 여부를 검사하는 것이지만, 여기에는 두가지 오판 가능성이 존재한다.

• 오탐지(False Positive, FP): 환자가 코로나에 걸리지 않았지만, $H_1$을 채택
• 미탐지(False Negative, FN): 환자가 코로나에 걸렸지만, $H_0$를 채택

따라서 “이상적인” 테스트는 $FP$와 $FN$의 확률을 동시에 줄이는 것이다. 그러나 이것이 가능할까?

---

이 상황을 이전까지 다루어온 데이터셋과 메커니즘 $\mathcal{M}$의 출력분포로 표현해보자.

이 환자가 코로나 환자가 아닐 때의 데이터셋을 $D_0$, 양성인 데이터셋을 $D_1$, 이로부터 체온을 측정하는 과정을 메커니즘 $\mathcal{M}$의 출력을 구하는 과정으로 대응시키고, 판단 기준 $O$를 기반으로 $\mathcal{M}$의 출력이 $O$에 속하면 $H_1$을 채택, 속하지 않으면 $H_0$를 채택하는 기준을 세울 수 있다.

이제 DP가 직접적으로 공격자가 관측값 $\mathcal{M}(D)$로부터 소스 데이터셋을 예측하기 힘들도록 한다는 점을 착안하여, 잘못된 예측인 FN와 FP의 확률을 각각 $p,q$로 정의하자. 만약 $p$ 또는 $q$의 값이 높다면, 이는 재구성 공격이 원본 데이터셋을 잘 복구하지 못함을 의미한다.

또한, 소스 데이터셋이 $D_0,D_1$인지의 여부에 관계없이 관측은 실제 데이터셋이 확정된 이후에 일어나므로, $p,q$의 여확률 $1-p,1-q$는 고정된 데이터셋 축을 따라 부여된다.

이를 진위표로 표현하면 다음과 같다.

$\begin{array}{cc}& \text{real}\\ \text{pred}& \end{array}$	P	N
P	TP $\mathrm{Pr}[\mathcal{M}(D_1)\in O]=1-p$	FP $\mathrm{Pr}[\mathcal{M}(D_0)\in O]=q$
N	FN $\mathrm{Pr}[\mathcal{M}(D_1)\notin O]=p$	TN $\mathrm{Pr}[\mathcal{M}(D_0)\notin O]=1-q$

만약 메커니즘 $\mathcal{M}$의 $ϵ-$DP가 보장된다면, 이는 곧 $\mathcal{M}$에 대해 가능한 모든 판별기준 $O$에 대해 다음이 성립함을 의미한다.

$$\begin{array}{r}{e}^{-ϵ}\le \frac{\mathrm{Pr}[\mathcal{M}(D_1)\notin O]}{\mathrm{Pr}[\mathcal{M}(D_0)\notin O]}=\frac{p}{1-q}\\ e^{-ϵ}\le \frac{\mathrm{Pr}[\mathcal{M}(D_0)\in O]}{\mathrm{Pr}[\mathcal{M}(D_1)\in O]}=\frac{q}{1-p}\end{array}$$

이 부등식은, $p$가 작아지려면 비율 $\frac{p}{1-q}$의 하한이 존재하기에, $1-q$ 또한 작아져야 하고, 따라서 $q$는 커져야 함을 시사한다. 또한, 그 반대의 경우도 동일하게 제약한다.

우리는 앞서 이상적인 테스트를 통해 FP의 확률 $q$와 FN의 확률 $p$를 동시에 줄여야 함을 전제했지만, 위 부등식은 그것이 불가능함을 보인다. 따라서 어떠한 테스트를 통해서도 $p,q$를 동시에 낮출 수 없고, 이로써 원본 데이터셋의 복구에 한계가 있음을 가설 검정을 통해 확인하였다.

Randomized Response

우리는 앞서 이진 데이터셋에서 확률 $\frac{1}{2}-\gamma$ 랜덤하게 뒤집힌 비트 응답을 통해 재구축 공격을 방어하는 과정을 공부하였다. 이를 $ϵ-$DP로 다시 증명해보자.

이 상황을 이제 원본 데이터셋 $D=(D_1,\dots ,D_n)$, 계산량 $f(D)=(D_1,\dots ,D_n)$, 개별 비트에 대해 $\frac{1}{2}-\gamma$의 확률로 뒤집는 메커니즘에 의한 응답 $\mathcal{M}(D)=(Y_1,\dots ,Y_n)$을 얻은 것으로 표현할 수 있다.

이제 이웃 데이터셋 $D^{\prime }=(D_1,\dots ,D_i^{\prime },\dots ,D_n)$에 대해

$$\frac{\mathrm{Pr}[\mathcal{M}(D)=(y_1,\dots ,y_n)]}{\mathrm{Pr}[\mathcal{M}(D^{\prime })=(y_1,\dots ,y_n)]}=\frac{\mathrm{Pr}[Y_i=y_i]}{\mathrm{Pr}[Y_i^{\prime }=y_i]}=\frac{\frac{1}{2}+\gamma }{\frac{1}{2}-\gamma }=\frac{1+2\gamma }{1-2\gamma }\approx \frac{e^{2\gamma }}{e^{-2\gamma }}=e^{4\gamma }$$

따라서, 이 메커니즘은 $4\gamma -$DP를 만족한다.

3.3. Laplace Mechanism (for numeric queries)

이제, 일반적인 numeric query ($f(D)\in {\mathbb{R}}^k$)에 대해 $ϵ-$DP를 가능케 하는 가장 중요한 메커니즘인 Laplace mechanism을 다루어보자.

이를 위해서는 먼저 함수의 함수 f의 출력이 인접한 두 이웃 데이터셋에 대하여 가질 수 있는 최대 변화량을 의미${\Delta }_1$ sensitivity를 정의해야 한다.

$${\Delta }_1=\underset{D,D^{\prime }neighbors}{\max }\Vert f(D)-f(D^{\prime }){\Vert }_1$$

Laplace 분포 $\mathrm{Lap}(\mu ,b)$의 확률 밀도 함수는 $p(x)=\frac{1}{2b}{e}^{-\frac{|x-\mu |}{b}}$이며, $\mu =0$일 때에 $p(x)=\frac{1}{2b}{e}^{-\frac{|x|}{b}}$로 정의된다. 이를 이용하여 정의되는 Laplace 메커니즘은 다음과 같다.

$$\mathcal{M}(D)=f(D)+(Y_1,\dots ,Y_k),\text{where }{Y}_i\stackrel{iid}{\sim }\mathrm{Lap}(0,\frac{{\Delta }_1}{ϵ}).$$

이 Laplace 메커니즘은 $ϵ-$DP를 만족한다. 추가되는 노이즈 $(Y_1,...,Y_k)$의 크기가 단일 개인 데이터의 변화로 인한 $f(D)$의 변화 ${\Delta }_1$보다 충분히 커서, 외부에서 출력 $\mathcal{M}(D)$를 관찰하더라도 어떤 개인의 데이터가 포함되었는지 또는 변경되었는지 확신하기 어렵게 만들기 때문이다.

이를 수식적으로 증명해보자. 먼저, 임의의 $z=(z_1,\dots ,z_k)\in {\mathbb{R}}^k$에 대해 $\mathcal{M}(D),\mathcal{M}(D^{\prime })$의 확률 밀도는 다음과 같다.

$$\begin{array}{rl}{p}_{\mathcal{M}(D)}(z)& =\prod _{i=1}^k\frac{1}{2b}\exp \left(-\frac{|z_i-f_i(D)|}{b}\right),b=\frac{{\Delta }_1}{ϵ}\\ p_{\mathcal{M}(D^{\prime })}(z)& =\prod _{i=1}^k\frac{1}{2b}\exp \left(-\frac{|z_i-f_i(D^{\prime })|}{b}\right),b=\frac{{\Delta }_1}{ϵ}.\end{array}$$

여기에서 $\mathcal{M}(D),\mathcal{M}(D^{\prime })$ 간에 비율을 취하고 삼각 부등식을 이용하면,

$$\begin{array}{rl}\frac{p_{\mathcal{M}(D)}(z)}{p_{\mathcal{M}(D^{\prime })}(z)}& =\prod _{i=1}^k\exp \left(-\frac{\left|z_i-f(C{)}_i\right|-\left|z_i-f(D^{\prime }{)}_i\right|}{b}\right)\\ & \le \prod _{i=1}^k\exp \left(\frac{\left|f(D_i)-f(D_i^{\prime })\right|}{b}\right)\\ & =\exp \left(\sum _{i=1}^k\frac{\left|f(D_i)-f(D_i^{\prime })\right|}{b}\right)\\ & =\exp \left(\frac{\Vert f(D{)}_i-f(D^{\prime }{)}_i{\Vert }_1}{b}\right)\\ & \le \exp \left(\frac{{\Delta }_1}{b}\right)=\exp \left(\frac{{\Delta }_1}{\frac{{\Delta }_1}{ϵ}}\right)=e^{ϵ}\end{array}$$

마지막으로 사건 ($T\subseteq {\mathbb{R}}^k$) 에 대해 적분하면 아래와 같이 $ϵ-$DP가 성립함을 확인할 수 있다.

$$\frac{\mathrm{Pr}[\mathcal{M}(D)\in T]}{\mathrm{Pr}[\mathcal{M}(D^{\prime })\in T]}=\frac{{\int }_{z_k\in T}^{}{f}_{\mathcal{M}(D)}(z_k)d{z}_k}{{\int }_{z_k\in T}^{}{f}_{\mathcal{M}(D^{\prime })}(z_k)d{z}_k}\le e^{ϵ}$$ $$\therefore {\int }_T{f}_{\mathcal{M}(D)}(\mathbf{z})d\mathbf{z}\le e^{ϵ}{\int }_T^{}{f}_{\mathcal{M}(D^{\prime })(\mathbf{z})}d\mathbf{z}$$

또한, 이때 Laplace 노이즈 $Y_i$의 분산은 다음의 사항을 시사한다.

$$\mathrm{Var}(Y_i)=2b^2=\frac{2{\Delta }_1^2}{{ϵ}^2}$$

• 함수 $f$의 최대 변동폭이 클수록 $f$는 더 많은 정보를 누출한다.
  • 큰 ${\Delta }_1$은 같은 $ϵ-$DP를 위해 더 큰 분산의 Laplace 노이즈를 요구한다.
• 프라이버시를 강건하게 만드려면, Laplace 노이즈의 분산은 더 커져야 한다.
  • 작은 $ϵ-$DP를 위해서는 더 큰 분산의 Laplace 노이즈를 요구한다.

---

여기서는 프라이버시를 분포적 안정성으로 정의하고, 이전에 살펴본 randomized response와 Laplace mechanism이 그 정의를 만족함을 보였으며, 그 과정에서 함수 $f$의 출력에 있어 한 개인의 영향의 최대 크기인 민감도 (sensitivity)가 왜 DP를 위한 핵심이 되는지 살펴보았다.

그렇다면 만약 여러 DP 알고리즘을 연속으로 실행하면 프라이버시가 어떻게 누적될까? 또한 DP의 출력에 후처리를 하면 프라이버시가 깨지는지, 수치적 출력이 아닌 선택 문제는 어떻게 다뤄야 할까?

4. Properties of Differential Privacy

지금까지는 DP의 수학적으로 엄밀한 정의를 다루어 보았다. 이제는 그 정의가 얼마나 유용하고 다루기 좋은지, 여러 메커니즘을 조합해도 제어 가능한지, 후처리에 안전한지, 샘플링이 어떤 이득을 주는지가 살펴볼 필요가 있다.

4.1. Composition Theorems

이전까지의 $ϵ-$DP는 데이터셋에 대한 하나의 메커니즘이 얼마나 프라이버시를 손실/보존하는지를 위주로 살펴보았다. 그렇다면 여러 ${ϵ}_i-$DP 메커니즘을 같은 데이터셋에 연속해서 적용하는 경우 프라이버시 손실은 어떻게 변할까?

DP는 이렇듯 하나의 데이터셋에 가해지는 여러 메커니즘의 조합 아래에서도, 어떻게 전체 프라이버시 손실이 누적되는지를 이론적으로 추적할 수 있게끔 한다.

---

Theorem 3.

메커니즘 ${\mathcal{M}}_1:{\mathcal{X}}^n\to {\mathcal{Y}}_1$과 ${\mathcal{M}}_2:{\mathcal{X}}^n\to \mathcal{Y}$가 각각 ${ϵ}_1-$DP, ${ϵ}_2-$DP를 만족한다고 하자. 이때 두 메커니즘 ${\mathcal{M}}_1,{\mathcal{M}}_2$를 동시에 공개하는 것은 최대 $({ϵ}_1+{ϵ}_2)-$DP를 만족한다.

Proof of Theorem 3.

직관적으로 각 메커니즘이 독립적으로 개별 데이터의 변경으로부터 함수의 출력을 각각 최대 $e^{{ϵ}_1},e^{{ϵ}_2}$배까지 변화시킬 수 있으므로, 두 메커니즘을 동시에 관찰하는 경우 이 둘의 곱인 $e^{{ϵ}_1+{ϵ}_2}$ 까지 변화할 수 있을 것으로 보인다.

실제로도 각 메커니즘의 결합확률분포는 독립적이므로 조건부 분포 형태 분해한 후 체이닝이 가능하여, 다음과 같이 계산된다.

$$\begin{array}{rl}\frac{\mathrm{Pr}[{\mathcal{M}}_1(D),{\mathcal{M}}_2(D,{\mathcal{M}}_1(D))=(a_1,a_2)]}{\mathrm{Pr}[{\mathcal{M}}_1(D^{\prime }),{\mathcal{M}}_2(D^{\prime },{\mathcal{M}}_1(D^{\prime })=(a_1,a_2)]}& =\frac{\mathrm{Pr}[{\mathcal{M}}_1(D)=a_1]\times \mathrm{Pr}[{\mathcal{M}}_2(D,{\mathcal{M}}_1)=a_2\mid {\mathcal{M}}_1(D)=a_1]}{\mathrm{Pr}[{\mathcal{M}}_1(D^{\prime })=a_1]\times \mathrm{Pr}[{\mathcal{M}}_2(D^{\prime },{\mathcal{M}}_1)=a_2\mid {\mathcal{M}}_1(D^{\prime })=a_1]}\\ & =\frac{\mathrm{Pr}[{\mathcal{M}}_1(D)=a_1]}{\mathrm{Pr}[{\mathcal{M}}_1(D^{\prime })=a_1]}\times \frac{\mathrm{Pr}[{\mathcal{M}}_2(D)=a_2]}{\mathrm{Pr}[{\mathcal{M}}_2(D^{\prime })=a_2]}\\ & \le e^{ϵ1}\times e^{{ϵ}_2}=e^{{ϵ}_1+{ϵ}_2}\end{array}$$

이를 더욱 일반화하면, $k$개의 메커니즘 ${\mathcal{M}}_1,{\mathcal{M}}_2,\dots ,{\mathcal{M}}_k$에 대해 각 메커니즘 ${\mathcal{M}}_i$가 ${ϵ}_i-$DP를 만족한다면, 이 출력들의 조합은 $\sum _i{ϵ}_i-$DP를 만족하며, 이는 worst-case의 프라이버시 손실 상한으로 작동한다.

특히 동일한 $ϵ-$DP를 만족하는 $k$개의 독립 메커니즘의 적용에서 DP는 $kϵ-$DP로 프라이버시 손실 $ϵ$은 $k$에 선형적으로 증가하는 것을 알 수 있다. 이처럼 로그 가능도비가 additive하게 누적되어 깔끔하게 정리된다는 점에서 $ϵ-$DP에서 확률 상한을 $e^{ϵ}$로 정하는 이유가 된다.

4.2. Post-processing Immunity

이제 $ϵ-$DP 메커니즘을 적용한 이후 후처리 (Post-Processing)를 적용했을 때, $ϵ-$DP가 어떻게 변하는지 살펴보자.

Theorem 4.

만약 메커니즘 $\mathcal{M}:D\to O$가 $ϵ-$DP를 만족하고, $f:O\to O^{\prime }$이 랜덤화 가능한 임의의 함수라면, 결합 메커니즘 $f(\mathcal{M}(D))$ 또한 $ϵ-$DP 이다.

Proof of Theorem 4.

직관적으로 $\mathcal{M}$의 출력이 이미 private하므로, 이후 어떠한 변형 $f$도 개별 데이터 레코드에 대한 새로운 종속성을 창출할 수 없다.

출력 사건 $S\subseteq O^{\prime }$에 대해 $f$를 통해 $S$로 보내지는 원래 출력들의 집합을 $f^{-1}(S)=\left\{o\in O:f(o)\in S\right\}$라 하면, 다음이 성립한다.

$$\begin{array}{rl}\mathrm{Pr}[f(\mathcal{M}(D))\in S]& =\mathrm{Pr}[\mathcal{M}(D)\in f^{-1}(S)]\\ & \le e^{ϵ}\mathrm{Pr}[\mathcal{M}(D^{\prime })\in f^{-1}(S)]\\ & =e^{ϵ}\mathrm{Pr}[f(\mathcal{M}(D^{\prime }))\in S]\end{array}$$

즉, DP 메커니즘의 적용 이후 후처리는 privacy loss를 늘리지 못한다. 이러한 후처리 면역성은 DP로 처리된 결과를 공개적으로 게시하고 추가적인 프라이버시 손실에 대한 걱정 없이 모든 후속 분석을 허용할 수 있음을 의미한다.

따라서 초기 결과가 $ϵ-$DP를 만족하는 한, 후속의 임의의 부가적인 계산이나 보조 데이터를 가진 공격자조차도 프라이버시를 악화시킬 수 없음을 명확히 한다는 점에서 매우 중요하다.

4.3. Group Privacy

우리는 지금까지 DP를 데이터셋에서 개별 데이터 레코드의 프라이버시를 보존하는 목적으로 정의하고 발전시켜왔다. 만약 개별 데이터 레코드가 아니라 크기 $t$의 개별 그룹을상정하면, 이에 대해 DP의 프라이버시 손실을 추가로 고려할 필요가 있다.

Theorem 5. Group Privacy

만약 메커니즘 $\mathcal{M}$이 $ϵ-$DP를 만족하면, 임의의 크기 $t$의 개별 그룹 내 모든 변화에 대해 $\mathcal{M}$은 $tϵ-$DP를 만족한다.

Proof of Theorem 5.

이는 상당히 직관적이다. $t$개의 레코드를 변경하는 것은 $t$번의 단일 레코드 변경을 순차적으로 보는 것으로 간주할 수 있으며, 합성(또는 직접적인 결합 논증)을 통해 가능성 비율에 대한 결합은 $e^{tϵ}$이 되고 덧셈 마진은 $t\delta$가 된다.

이러한 그룹 프라이버시는 만약 누군가가 5개의 레코드 그룹(동일한 사람이 데이터에 여러 번 나타나는 경우 등)에 대해 우려한다면, $ϵ-$DP의 프라이버시 보장이 그 5배만큼 저하됨을 의미한다. 그럼에도, 일반적으로 $ϵ$은 충분히 작게 유지기에, 너무 크지 않은 $t$에서는 수용 가능한 $tϵ-$DP 보장을 받을 수 있을 가능성이 크다.

4.4. Amplification by Subsampling

서브샘플링에 의한 프라이버시 증폭은 DP에서 매우 중요한 긍정적 속성으로 작용한다. SGD에서 미니 배치를 쓰는 등, 우리는 각 개별 데이터 레코드를 특정 확률로만 경우가 상당히 많고, 이러한 서브샘플링은 결과적으로 DP의 프라이버시를 더욱 증폭시킬 수 있다.

Theorem 6. Privacy Amplification by Subsampling

$(ϵ,\delta )-$DP을 보장하는 메커니즘 $\mathcal{M}:{\mathcal{X}}^m\to \mathcal{Y}$가 있다. 이때, $n>m$에 대해 입력 $X\in {\mathcal{X}}^n$로부터 랜덤 부분집합 $X^{\prime }\in {\mathcal{X}}^m$에 $\mathcal{M}(X^{\prime })$을 수행한 후 출력하는 메커니즘 ${\mathcal{M}}^{\prime }:{\mathcal{X}}^n\to \mathcal{Y}$를 고려하자.

개별 데이터 레코드의 서브샘플링 확률을 $q=\frac{m}{n}$이라 하면, ${\mathcal{M}}^{\prime }$는 ${ϵ}^{\prime }<ϵ$인 ${ϵ}^{\prime }-$DP를 만족한다.

$${ϵ}^{\prime }=\ln (1+q(e^{ϵ}-1))$$

Proof of Theorem 6. Privacy Amplification by Subsampling

이웃 데이터셋 $X,X^{\prime }\in {\mathcal{X}}^n$을 고려하자. 존재하는 모든 경우의 수를 일반화하여, 각 데이터셋을 $X=(x,x_2,x_{3,\dots ,x_n})$, $X^{\prime }=(x^{\prime },x_2,x_3,\dots ,x_n)$의 형태로 간주할 수 있다.

이제 각 원소가 $1,\dots ,n$으로부터 균일하게 샘플링되는 크기 $m$의 인덱스 지시 벡터 $I=(I_1,\dots ,I_m)$와 이 지시 벡터로부터 샘플링을 수행하는 함수 $s(X;I)=(X_{I_1},X_{I_2},\dots ,X_{I_m})$를 정의하자. $\mathrm{Pr}[1\in I]=\frac{m}{n}=q$로 정의하면, 임의의 출력 집합 $T$에 대해 다음이 성립한다.

$$\begin{array}{rl}\mathrm{Pr}[{\mathcal{M}}^{\prime }(X)\in T]=& q\cdot \mathrm{Pr}[\mathcal{M}(s(X;I))\in T\mid 1\in I]\\ & +(1-q)\cdot \mathrm{Pr}[\mathcal{M}(s(X;I))\in T\mid 1\notin I](0)\end{array}$$

$\mathrm{Pr}[1\in I]=\frac{m}{n}=q$이며, $ϵ-$DP에 의해 다음이 성립한다.

$$\begin{array}{rlr}\mathrm{Pr}[\mathcal{M}(s(X;I))\in T\mid 1\in I]& \le e^{ϵ}\mathrm{Pr}[\mathcal{M}(s(X^{\prime };I))\in T\mid 1\in I]& (1)\\ \mathrm{Pr}[\mathcal{M}(s(X;I))\in T\mid 1\in I]& \le e^{ϵ}\mathrm{Pr}[\mathcal{M}(s(X;I))\in T\mid 1\notin I]& (2)\\ \mathrm{Pr}[\mathcal{M}(s(X;I))\in T\mid 1\notin I]& =\mathrm{Pr}[\mathcal{M}(s(X^{\prime };I))\in T\mid 1\notin I]& (3)\end{array}$$

• (1)은 $ϵ-DP$의 정의에 의해 성립한다.
• (2)는 $1\in I$인 모든 부분 집합과 $1\notin I$인 부분 집합 사이에 대응 관계를 찾아 각 대응하는 부분 집합들이 서로 인접하게 만들 수 있다.
• (3)은 이웃 데이터셋이 $X=(x,x_2,\dots ,x_n),X^{\prime }=(x^{\prime },x_2,\dots ,x_n)$이므로 첫 번째 요소를 포함하지 않는 $1\notin I$경우에서 $s(X^{\prime };I)$에 대한 확률은 동일하다.

따라서 식 (0)은 다음과 같이 바뀐다. 두번째 항은 식 (3)에 의해 $e^{ϵ}$ 항이 없는 것에 유의하자.

$$\begin{array}{rl}Pr[{\mathcal{M}}^{\prime }(X)\in T]& \le q{e}^{ϵ}Pr[\mathcal{M}(s(X^{\prime };I))\in T\mid 1\in I]\\ & +(1-q)Pr[\mathcal{M}(s(X^{\prime };I))\in T\mid 1\notin I]\end{array}$$

우리는 $ϵ-$DP의 표현 형태를 만족하기 위해, $\mathrm{Pr}[{\mathcal{M}}^{\prime }(X)\in T]$를 상계하는 우변을 어떠한 상수 $C$로 표현되는 $C\cdot \mathrm{Pr}[{\mathcal{M}}^{\prime }(X)\in T]=C(qA+(1-q)B)$의 형태로 잡을 수 있어야 한다. 이를 위해 $\alpha =q+(1-q)e^{-ϵ}<1$을 정의해보자. 이 $\alpha$는 다음의 성질을 만족한다.

$$\begin{array}{rl}\alpha & =q+(1-q)e^{-ϵ}\\ \alpha e^{ϵ}& =q{e}^{ϵ}+(1-q)\\ (1-\alpha )e^{ϵ}& =(1-q-(1-q)e^{-ϵ})e^{ϵ}\\ & =e^{ϵ}-q{e}^{ϵ}-(1-q)\\ & =(1-q)(e^{ϵ}-1)\end{array}$$

따라서 다음과 같이 전개하여 정리할 수 있다.

$$\begin{array}{rl}& \\ Pr[{\mathcal{M}}^{\prime }(X)\in T]& =qPr[\mathcal{M}(s(X;I))\in T\mid 1\in I]\\ & +(1-q)Pr[\mathcal{M}(s(X;I))\in T\mid 1\notin I]\\ & \le q{e}^{ϵ}Pr[\mathcal{M}(s(X;I))\in T\mid 1\in I]\\ & +(1-q)Pr[\mathcal{M}(s(X^{\prime };I))\in T\mid 1\notin I]\\ & \le \{\\ & \alpha q{e}^{ϵ}\mathrm{Pr}[\mathcal{M}(s(X;I))\in T\mid 1\in I]\\ & +(1-\alpha )q{e}^{ϵ}\mathrm{Pr}[\mathcal{M}(s(X;I))\in T\mid 1\in I]\\ & \}+(1-q)\mathrm{Pr}[\mathcal{M}(s(X^{\prime };I))\in T\mid 1\notin I]\\ & \le \alpha q{e}^{ϵ}\mathrm{Pr}[\mathcal{M}(s(X^{\prime };I))\in T\mid 1\in I]\\ & +(1-\alpha )q{e}^{ϵ}\mathrm{Pr}[\mathcal{M}(s(X^{\prime };I))\in T\mid 1\notin I]\\ & +(1-q)\mathrm{Pr}[\mathcal{M}(s(X^{\prime };I))\in T\mid 1\notin I]\\ & =\alpha q{e}^{ϵ}\mathrm{Pr}[\mathcal{M}(s(X^{\prime };I))\in T\mid 1\in I]\\ & +\left\{1-q+(1-\alpha )q{e}^{ϵ}\right\}\mathrm{Pr}[\mathcal{M}(s(X^{\prime };I))\in T\mid 1\notin I]\\ & =\end{array}$$

이제 $A$에 붙어있는 $q{e}^e$ 계수 $\alpha <1$을 도입해

$$\begin{array}{rl}\mathrm{Pr}[{\mathcal{M}}^{\prime }(X)\in T]& \le q{e}^{ϵ}A+(1-q)B\\ & =e^{ϵ}(qA+(1-q)e^{-ϵ}B)\\ & =e^{ϵ}(\alpha qA+(1-\alpha )qA+(1-q)e^{-ϵ}B)\end{array}$$

4.5. Differentially private k-means

$k-$means 알고리즘은 $n$개의 데이터를 각 클래스별 분산을 가장 작게 만드는 $k$개의 클래스로 분할하는 고전적인 알고리즘이다. 여기에 DP를 적용하여, 개별 데이터 레코드 $X$가 바뀌어도 전체 k-means 결과가 심각하게 흔들리지 않도록 해보자.

이를 위해 다음의 “Private k-Means via Output Perturbation” 메소드를 사용한다.

Private k-Menas via Output Perturbation

데이터셋 $X=\left\{x_1,x_2,\dots ,x_n\right\}\subseteq {\mathcal{U}}^n$, 클러스터 개수 $k$에 대해 다음의 과정을 수행한다.

1. $k$개의 클러스터 중심 ${\mu }_1,\dots ,{\mu }_k$를 랜덤하게 초기화한다.
2. 각 클러스터 $C_j$를 다음과 같이 업데이트한다.

$$C_j\leftarrow \left\{x_i\in X:\Vert x_i-{\mu }_j{\Vert }^2\le \underset{m\in \left\{1,\dots ,k\right\}}{\min }\Vert x_i-{\mu }_m{\Vert }^2\right\}$$

3. 각 클러스터 $C_j$에 대해, $Y_j,Z_j\sim \mathrm{Lap}(0,\frac{2}{{ϵ}^{\prime }})$을 샘플링한다.
4. $n_j\leftarrow \left|C_j\right|+Y_j$를 정의한다.
5. $a_j\leftarrow {\sum }_{x_i\in C_j}^{}{x}_i+Z_d$ 를 정의한다.
6. 각 클러스터 중심 ${\mu }_j$를 다음과 같이 업데이트한다.

$${\mu }_j\leftarrow \{\begin{array}{ll}\frac{a_j}{n_j}& \text{If }{n}_j\ge 1\\ uniform\in \mathcal{U}& \text{If }{n}_j<1\end{array}$$

7. 위 과정을 $T$번 반복한다.

private k-means는 각 반복마다 두 가지를 privatize한다.

1. 각 클러스터의 원소 수 ($|C_j|$)
2. 각 클러스터의 벡터 합 (${\sum }_{x_i\in C_j}{x}_i$)

데이터가 $|x{|}_1\le 1$ 인 bounded domain $\mathcal{U}$에 있다고 가정하면, 한 점을 바꾸면 어떤 클러스터에서 빠지고 다른 클러스터에 들어갈 수 있으므로 전체 벡터 합의 ${\ell }_1$-sensitivity는 2가 된다. 또한, 클러스터 개수 벡터 역시 하나 빠지고 하나 들어가므로 sensitivity는 또다시 2이다.

따라서 각각에 Laplace noise scale $2/{\rho }^{\prime }$ 를 추가하면 각 단계가 (${\rho }^{\prime }$)-DP 가 되며, $t$ 반복마다 “개수 privatization + 합 privatization” 두 번이 있으므로 한 iteration당 ($2{ϵ}^{\prime }$), 총 ($T$) 번 반복이면 $2T{ϵ}^{\prime }=ϵ$ 가 되도록 ${\rho }^{\prime }=ϵ/(2T)$로 잡으면 전체 알고리즘은 $ϵ$-DP를 만족한다.

즉, 이 알고리즘의 핵심은 k-means 전체를 한 번에 증명하는 것이 아니라, 민감한 sufficient statistics를 DP로 만들고 composition으로 묶는다는 데에 있다.

4.6. Additive Differential Privacy $\delta -$DP

이웃 데이터셋 $D,D^{\prime }$에 대해 additive DP $\delta -$DP는 모든 출력 사건 $O$에 대해 다음 제약을 요구한다.

$$\left|\mathrm{Pr}[\mathcal{M}(D)\in O]-\mathrm{Pr}[\mathcal{M}(D^{\prime })\in O]\right|\le \delta$$

즉, 이웃 데이터셋에 대하여 어떤 사건의 확률 차이도 $\delta$를 넘지 않아야 한다. 이는 지금까지 살펴본 multiplicative DP인 $ϵ-$DP와 비슷하게 프라이버시를 잘 보존하는 것으로 보인다.

하지만 문제는, 이 조건이 “이웃 데이터셋에 대해 사건 발생의 확률 차이만 작으면 된다”는 식이라서, 아주 작은 확률로 엄청나게 큰 유출이 발생하는 상황을 막지 못한다는 데 있다. multiplicative DP는 희귀한 사건의 확률도 상대적으로 엄격하게 제어하는 반면, additive-only 조건은 안전한 프라이버시를 제공하지 못하는 메커니즘조차 “어차피 확률이 $\delta$ 이하니까 괜찮다”고 통과시켜 버릴 수 있는 것이다.

$\delta -$DP의 위험성

어떤 민감한 사건이 한 데이터셋에서는 확률 $p=10^{-9}$, 다른 데이터셋에서는 확률 $p=10^{-3}$으로 일어난다고 가정하자.

만약 $\delta -$DP에서 $\delta =10^{-3}$으로 설정한다면 additive DP는 이 기준에서 위의 상황을 허용한다. 하지만 이건 상대적으로는 $10^6$배 차이로, 관찰자가 이러한 사건을 관측하게 되면 매우 강하게 두 데이터셋을 구별할 수 있다. multiplicative $ϵ-$DP는 이웃 데이터셋 간의 사건 확률을 배율 $e^{ϵ}$로 제어하기 때문에, 이런 상대적 폭증을 엄격하게 막으려 하지만, additive-only 정의로는 막을 수 없다.

ex1. 데이터셋의 전체 유출

데이터셋 $X=(x_1,x_2,\dots ,x_n)$과 이웃 데이터셋 $X^{\prime }$, 다음과 같은 메커니즘을 생각해보자.

$$\mathcal{M}(X)=\{\begin{array}{ll}X& \text{w.p. }\delta \\ \perp & \text{w.p. }1-\delta \end{array}$$

위 메커니즘은 확률 $\delta$로 데이터셋을 그대로 공개해버리거나 확률 $1-\delta$로 아무것도 출력하지 않는다. 이는 당연히 아무리 낮은 확률이라도 전체 데이터셋을 그대로 공개해버리는 치명적인 정보 유출을 일으키기에 DP 보장을 통과하면 안될 것처럼 보이지만, $\delta -$DP에서는 통과 가능한 경우가 생긴다.

---

이 메커니즘이 $\delta -$DP를 만족한다는 것은 아래가 성립함을 의미한다.

$$\mathrm{Pr}[\mathcal{M}(X)\in O]\le \mathrm{Pr}[\mathcal{M}(X^{\prime })\in O]+\delta$$

여기서 가능한 $O$는 사실상 $O\subseteq \left\{X,X^{\prime },\perp \right\}$의 세가지이며, 이때 $\mathcal{M}(X),\mathcal{M}(X^{\prime })$의 확률식은 다음과 같이 정의된다.

$$\begin{array}{rl}\mathrm{Pr}[\mathcal{M}(X)\in O]& =\delta \cdot 1[X\in O]+(1-\delta )\cdot 1[\perp \in O]\\ \mathrm{Pr}[\mathcal{M}(X^{\prime })\in O]& =\delta \cdot 1[X^{\prime }\in O]+(1-\delta )\cdot 1[\perp \in O]\end{array}$$

이때 두 확률간 차이는 다음과 같이 정리되며, $\delta$-DP 제약을 통과함을 볼 수 있다.

$$\begin{array}{c}\mathrm{Pr}[\mathcal{M}(X)\in O]-\mathrm{Pr}[\mathcal{M}(X^{\prime })\in O]=\delta \cdot (1[X\in O]-1[X^{\prime }\in O])\\ \therefore \left|\mathrm{Pr}[\mathcal{M}(X)\in O]-\mathrm{Pr}[\mathcal{M}(X^{\prime })\in O]\right|\le \delta \end{array}$$

ex2. 데이터셋의 일부 유출

ex1과 동일하게 데이터셋 $X=(x_1,x_2,\dots ,x_n)$과 이웃 데이터셋 $X^{\prime }$, 다음과 같은 메커니즘을 생각해보자.

$$\mathcal{M}(X{)}_i=\{\begin{array}{ll}{X}_i& \text{w.p. }\delta \\ \perp & \text{w.p. }1-\delta \end{array}$$

위 메커니즘은 확률 $\delta$로 특정 요소 $X_i$만을 나타내거나 숨긴다. 이는 이전과 동일한 논리로 $\delta -$DP를 만족할 수 있으나, 전체적으로 보면 여전히 한 명의 데이터가 유출될 확률은 상당히 높다.

---

인접한 두 데이터셋 $X,X^{\prime }$가 오직 하나의 위치 $j$에서만 다르다고 가정하자. 이때 출력 $y=(y_1,\dots ,y_n)$이 가질 수 있는 각 좌표 값은 $X_i,\perp$이며, $X,X^{\prime }$은 $j$자리에서만 다르므로, 나머지 좌표는 모두 동일하다. 따라서 우리는 $y_i$의 경우의 수만 따지면 된다.

1. 만약 $y_j=\perp$인 경우

• 이 경우에는 $X,X^{\prime }$ 모두에 대해 $\mathrm{Pr}[\mathcal{M}(X)\in y]=\mathrm{Pr}[\mathcal{M}(X^{\prime })\in y]=1-\delta$이다.

2. 만약 $y_j=X_j$인 경우

• 이 경우 $y$는 $\mathcal{M}(X)$에서만 출력 가능하고, 그 확률은 $\mathrm{Pr}[\mathcal{M}(X)\in y]=\delta \cdot {\prod }_{i\ne j}^{}{p}_i(y_i)\le \delta$, $X^{\prime }$에서는 $y_j=X_j$가 불가능하므로 $\mathrm{Pr}[\mathcal{M}(X^{\prime })\in y]=0$이다.

3. 만약 $y_j=X_j^{\prime }$인 경우

• 2의 경우에서 반대이다.

결국 모든 단일 출력 $y$에 대해 두 분포의 차이는 $j$번째 좌표에서 생기는 확률차이 최대 $\delta$를 상한으로 가지며, 임의의 사건 $O$는 이런 출력들의 가능한 모든 집합이.

따라서 이중에서 가장 확률차이가 커지는 사건 집합은 “$j$번째 좌표가 $X_j$ 또는 $X_j^{\prime }$로 드러나는 모든 출력”을 모아놓은 사건이며, 이 사건의 확률차이는 정확히 $\delta$로, 다음 $\delta -$DP를 만족한다.

$$\left|\mathrm{Pr}[\mathcal{M}(X)\in O]-\mathrm{Pr}[\mathcal{M}(X^{\prime })\in O]\right|\le \delta$$

이처럼 $\delta -$DP는 어떤 사건의 확률 질량이 이웃 데이터셋 중 특정 한 쪽에만 몰리는 경우 (극단적으로, 위 예시의 경우 반대쪽 데이터셋에서 사건의 확률 질량이 0)를 핸들링하지 못한다.

만약 $ϵ-$DP 테스트의 경우, 한쪽 확률 질량이 0이 되거나 상대적으로 매우 희소해지는 순간, 확률비가 $e^{ϵ}$를 쉽게 넘어서며 DP 제약을 위반함을 드러낸다.

4.7. Selection Problem: Exponential Mechanism

이제 숫자 출력이 아닌 선택 문제에 $ϵ-$DP를 적용해보자. 특정 클래스 라벨을 선택하는 출력(샘플링 등) 메커니즘은 출력 자체에 노이즈를 걸면 의미없는 수치값이 나오기 때문에, 이를 위한 새로운 개념이 제시되어야 한다.

이를 위해 메커니즘이 데이터셋 $D$에서 후보군 $j$가 뽑히게끔 유도하는 스코어 함수를 특별히 Utility 함수라 부르고 $q(j;D)$로 표기한다.

Exponential Mechanism은 가능한 각 후보 $y\in \mathcal{Y}$에 대해, 이 후보가 얼마나 좋은가를 utility 함수 $q(j;D)$로 정의하고, 이 값의 대소에 따라 각 후보가 뽑힐 확률을 지수적으로 조정하는 메커니즘이다. 지수항이 1보다 커지면 $q(j;D)$의 작은 차이에 더 민감하게 확률을 조절하고, 지수항이 1보다 작아지면 $q(j;D)$의 차이에 점점 둔감해지게(즉, 평탄하게) 만든다.

$$\mathrm{Pr}[{\mathcal{M}}_{EM}(D)=y]=\frac{\exp \left(\frac{ϵq(y;D)}{2{\Delta }_q}\right)}{{\sum }_{y^{\prime }\in \mathcal{Y}}^{}\exp \left(\frac{ϵq(y^{\prime };D)}{2{\Delta }_q}\right)}$$

이떄, $ϵ-$DP를 위한 민감도 ${\Delta }_q$는 $q$에 의존하여 다음과 같이 정의되며, 이웃 데이터셋 간에 한 데이터 레코드만이 바뀌었을 때, 후보 $y$의 utility가 최대 얼마나 바뀔 수 있는지를 정의한다.

$$\Delta q=\underset{\begin{array}{c}D\sim D^{\prime }\\ y\in \mathcal{Y}\end{array}}{\max }|q(D,y)-q(D^{\prime },y)|$$

---

이제 $ϵ-$DP 정의를 위해 확률비를 계산해보자. ${\sum }_{y^{\prime }\in \mathcal{Y}}\exp \left(\frac{\epsilon q(y^{\prime };D)}{2{\Delta }_q}\right)$를 정규화 상수 $Z(D)$로 표기하면, 다음과 같다.

$$\frac{\mathrm{Pr}[\mathcal{M}(D)=y]}{\mathrm{Pr}[\mathcal{M}(D^{\prime })=y]}=\frac{\exp \left(\frac{\epsilon q(D,y)}{2\Delta q}\right)}{\exp \left(\frac{\epsilon q(D^{\prime },y)}{2\Delta q}\right)}\cdot \frac{Z(D^{\prime })}{Z(D)}$$

민감도 정의에 의해 다음이 성립한다.

$$\begin{array}{rl}q(y;D)& \le q(y;D^{\prime })+{\Delta }_q\\ \frac{ϵq(y;D)}{2{\Delta }_q}& \le \frac{ϵq(y;D^{\prime })}{2{\Delta }_q}+\frac{ϵ{\Delta }_q}{2{\Delta }_q}\\ \therefore \exp \left(\frac{\epsilon q(D,y)}{2\Delta q}\right)& \le e^{\epsilon /2}\exp \left(\frac{\epsilon q(D^{\prime },y)}{2\Delta q}\right)\end{array}$$

또한, 모든 $y^{\prime }\in \mathcal{Y}$에 대해 성립하므로 이들을 합한 정규화항 $Z$에 대해서도 아래 부등식이 성립한다.

$$\frac{Z(D^{\prime })}{Z(D)}\le e^{ϵ/2}$$

따라서 다음의 $ϵ-$DP를 만족한다.

$$\frac{\mathrm{Pr}[\mathcal{M}(D)=y]}{\mathrm{Pr}[\mathcal{M}(D^{\prime })=y]}\le e^{\epsilon /2}\cdot e^{\epsilon /2}=e^{\epsilon }$$

---

이제 privacy만 좋고 답은 엉망이면 쓸모가 없으니, “얼마나 좋은 답을 뽑는가”를 봐야 한다. 따라서, 최고 utility 값을 $q_{\max }={\max }_{y\in \mathcal{Y}}q(D,y)$라 하고, 실제 메커니즘이 출력하는 $Y$의 utility 가 $q_{max}$에 비해 얼마나 떨어지는지 확인해야 한다. 이 손실을 다음과 같이 정의하자.

$$q_{max}-q(y;D)$$

출력 공간의 크기를 $d=\left|\mathcal{Y}\right|$라 할 때, Exponential Mechanism은 $t>0$에 대해 원래의 최적 utility보다 $\frac{2{\Delta }_q}{ϵ}(\log d+t)$ 이상 나쁜 답을 고를 확률이 $e^{-t}$ 이하임을 보장한다. 이를 수식으로 표현하면 다음과 같다.

$$\mathrm{Pr}\left[q(Y;D)<q_{max}-\frac{2{\Delta }_q}{ϵ}(\log d+t)\right]\le e^{-t}$$

여기서 중요한 해석으로 다음의 세가지를 기억하자.

1. $ϵ$이 커질수록 손실 상한이 작아지므로 더 좋은 답을 고른다.
2. 민감도 ${\Delta }_q$가 클수록 손실 상한이 커진다.
3. 출력 후보 수 $d$가 늘어나도 손실은 $\log d$에만 비례한다. 즉, 후보가 많아져도 손실이 로그 스케일로 제한된다.

---

가장 높은 utility를 가지는 최적 출력을 $y^{\ast }$로 두고, 이때의 utility를 $q_{max}q(y^{\ast ;D})$라 하자.

이제, 선택 메커니즘에 의한 나쁜 출력들의 집합 $B_t$를 다음과 같이 정의하여 $\mathrm{Pr}[Y\in B_t]\le e^{-t}$임을 보이는 것이 목적이다.

$$B_t=\left\{y\in \mathcal{Y}:q(y;D)<q_{\max }-\frac{2{\Delta }_q}{\epsilon }(\log d+t)\right\}$$

우선, Exponential Mechanism의 정의에 의해 임의의 $y\in B_t$에 대해 다음이 성립한다.

$$\begin{array}{rl}\frac{\mathrm{Pr}[Y=y]}{\mathrm{Pr}[Y=y^{\ast }]}& =\frac{\exp \left(\frac{ϵq(y;D)}{2{\Delta }_q}\right)/Z}{\exp \left(\frac{ϵq_{max}}{2{\Delta }_q}\right)/Z}\\ & <\exp \left(\frac{ϵq_{max}-2{\Delta }_q(\log d+t)-ϵq_{max}}{2{\Delta }_q}\right)\\ & =\exp \left(-(\log d+t)\right)\end{array}$$

따라서 임의의 나쁜 사건 $y\in B_t$에 대해, 다음의 부등식이 성립한다.

$$\begin{array}{c}\mathrm{Pr}[Y=y]<e^{-(\log d+t)}\cdot \mathrm{Pr}[Y=y^{\ast }]\\ \therefore \mathrm{Pr}[Y\in B_t]=\sum _{y\in B_t}\mathrm{Pr}[Y=y]<\left|B_t\right|\cdot e^{-(\log d+t)}\mathrm{Pr}[Y=y^{\ast }]\end{array}$$

그런데, $\mathrm{Pr}[Y=y^{\ast }]<1$이고, $\left|B_t\right|<d$ 이므로 다음처럼 정리될 수 있다.

$$\mathrm{Pr}[Y\in B_t]<\left|B_t\right|\cdot e^{-(\log d+t)}\mathrm{Pr}[Y=y^{\ast }]<d\cdot e^{-(\log d+t)}=e^{-t}$$

이로써 나쁜 사건 전체의 확률 상한을 증명했다.

---

또한 추가적으로 Exponential Mechanism의 기댓값 $\mathbb{E}[q_{max}-q(y;D)]$에 대해서도 다음의 보장을 얻을 수 있다.

$Z=\frac{ϵ}{2{\Delta }_q}(q_{max}-q(y;D))$라 하면, $z=\log d+t$의 reparameterization trick에 의해 다음이 성립한다.

$$\begin{array}{rl}\mathbb{E}[Z]& ={\int }_0^{\infty }\mathrm{Pr}[Z>z]dz\\ & ={\int }_{-\log d}^{\infty }\mathrm{Pr}[Z>\log d+t]dt\\ & ={\int }_{-\log d}^0\mathrm{Pr}[Z>\log d+t]dt+{\int }_0^{\infty }\mathrm{Pr}[Z>\log d+t]dt\\ & \le \log d+{\int }_0^{\infty }\mathrm{Pr}[Z>\log d+t]dt\\ & \le \log d+{\int }_0^{\infty }{e}^{-t}dt\\ & =\log d+1\\ \therefore & \mathbb{E}[q_{max}-q(y;D)]\le \frac{2{\Delta }_q}{ϵ}(\log d+1)\end{array}$$

4.8. Selection Problem: Noisy Max

Exponential Mechnism이 각 후보 $y$의 유틸리티에 비례하는 exponential 확률로 각 후보를 샘플링한다면, Noisy Max는 각 score에 아예 독립적인 noise를 더한 뒤 argmax 단 하나만을 택하여 공개하는 선택 메커니즘이다.

언뜻 보면, 이전의 Exponential Mechanism과 그 의미는 비슷하다. 특히, 노이즈 샘플링 과정에서 특정 노이즈 분포(Gumbel, Laplace, Exponential 등)을 쓰면 Noisy max에서 argmax로 얻어지는 분포가 Exponential Mechanism과 동일하거나 또는 근사 가능하다는 점에서 두 메커니즘이 수학적으로 밀접한 관련이 있다.

Exponential Mechanism은 이론적인 유틸리티 함수와, 이에 따른 전체 확률 분포의 정규화 등 큰 계산비용을 소모하여 강한 DP 보장을 제공하는 반면, Noisy Max는 명시적인 유틸리티 함수와 정규화 과정 없이 단순히 각 후보에 독립적 노이즈를 추가하는 것만으로 Exponential Mechanism에 근사가 가능한 것이 장점이다. 대신 이렇게 계산 비용을 줄인 만큼 적절한 노이즈 분포 및 스케일을 선택하지 않았을 때에 최적의 프라이버시를 보장하지 못하는 단점을 가진다.

---

유한한 후보 집합 $Y$와 각 후보 $y\in Y$에 대한 점수함수 $q(y;D)$가 있다고 하자. 이 점수 함수의 민감도가 ${\Delta }_q$라는 것은, 모든 이웃 데이터셋 $D,D^{\prime }$과 모든 $y\in Y$에 대해 다음이 성립함을 의미한다.

$$|q(y;D)-q(y;D^{\prime })|\le {\Delta }_q$$

이때 Noisy Max는 각 후보에 독립적으로 $Z_y$를 샘플링하여 다음의 방식으로 후보를 선택한다.

$$\begin{array}{c}{s}_y=q(y;D)+Z_y{Z}_y\sim \mathrm{Exp}(\text{scale}=\frac{2{\Delta }_q}{ϵ})\\ \hat{y}=\underset{y\in Y}{\arg \max }{s}_y\end{array}$$

여기서 $\mathrm{Exp}(\mathrm{scale}=\mathrm{b})$는 범위가 $[0,\infty )$인 한쪽 방향의 exponential 노이즈를 의미하며, 따라서 확률밀도는 $f(z)=\frac{1}{b}\exp \left(-\frac{z}{b}\right)$, 여기서 $b=\frac{2{\Delta }_q}{ϵ}$이므로 확률밀도의 tail은 다음이 된다.

$$\mathrm{Pr}[Z\ge t]=\exp \left(-\frac{ϵt}{2{\Delta }_q}\right)(t\ge 0)$$

특히 점수함수 자체의 민감도는 ${\Delta }_q$인데 반해, 최종 전개에서는 $\mathrm{Exp}$분포의 스케일로 $2{\Delta }_q$가 선택되는 점에 유의하자.

Noisy Max에서 후보 $y$가 이기려면 모든 다른 후보 $j\ne y$에 대해 다음이 성립해야 한다.

$$\begin{array}{rl}q(y;X)+Z_y& \ge q(j;X)+Z_j\\ \therefore Z_y& \ge \underset{j\ne y}{\max }(q(j;X)+Z_j)-q(y;X)\end{array}$$

이때 $y$가 이기는 조건은 $y$에서 샘플링되는 $Z_y$가 어떤 threshold $T_X(z_{-y})$를 넘어야하는가에 대한 문제로 바뀐다.

$$T_X(z_{-y})=\underset{j\ne y}{\max }(q(j;X)+z_j)-q(y;X)$$

이웃 데이터셋 간에 모든 후보에서 생길 수 있는 점수함수의 변동성은 각각 ${\Delta }_q$로 상계된다. 따라서 최악의 경우 이웃데이터셋 간에는, 타겟 후보 $y$와 이와 경쟁하는 후보 $j$에 대해 다음의 변동이 가능하다.

$$\begin{array}{rl}y& \to y-{\Delta }_q\\ j& \to j+{\Delta }_q\end{array}$$

이웃 데이터셋 $X,X^{\prime }$에 대해 threshold를 각각 계산하면 아래와 같고

$$\begin{array}{rl}{T}_X(z_{-y})& =\underset{j\ne y}{\max }(q(j;X)+z_j)-q(y;X)\\ T_{X^{\prime }}(z_{-y})& =\underset{j\ne y}{\max }(q(j;X^{\prime })+z_j)-q(y;X^{\prime })\end{array}$$

첫 번째 $max$항에 대해서는 각 $j\ne y$에 대해 $q(j;X)\ge q(j;X^{\prime })-\Delta$를, 두 번째 $max$에 대해서는 $q(y;X)\le q(y;X^{\prime })+\Delta$를 적용하면 다음과 같다.

$$\begin{array}{cc}\begin{array}{rl}& (1)\\ q(j;X)& \ge q(j;X^{\prime })-{\Delta }_q\\ \underset{j\ne y}{\max }(q(j;X)+z_j)& \ge \underset{j\ne y}{\max }(q(j;X^{\prime })+z_j)-{\Delta }_q\end{array}& \begin{array}{rl}& (2)\\ q(y;X)& \le q(y;X^{\prime })+{\Delta }_q\\ -q(y;X)& \ge -q(y;X^{\prime })-{\Delta }_q\end{array}\end{array}$$ $$\begin{array}{rl}\therefore T_X(z_{-y})& =\underset{j\ne y}{\max }(q(j;X)+z_j)-q(y;X)\\ & \ge \underset{j\ne y}{\max }(q(j;X^{\prime })+z_j)-{\Delta }_q-q(y;X^{\prime })-{\Delta }_q\\ & =\underset{j\ne y}{\max }(q(j;X^{\prime })+z_j)-q(y;X^{\prime })-2{\Delta }_q\\ & =T_{X^{\prime }}(z_{-y})-2{\Delta }_q\end{array}$$

따라서 이웃데이터셋 간에 경합하는 두 후보의 점수 차이의 최대 변동성은 $2{\Delta }_q$가 되고, 이 최악의 변동에 대해서도 확률비 변동은 $e^{ϵ}$을 넘지 않도록 제한하게 된다.

---

이제 Noisy Max가 $ϵ-$DP를 만족함을 증명해보자. 임의의 출력 $y$ 에 대해 다음이 성립해야 한다.

$$\mathrm{Pr}[\mathcal{M}(X)=y]\le e^{ϵ}\mathrm{Pr}[\mathcal{M}(X^{\prime })=y]$$

후보 $y$가 선택될 확률을 다른 후보들의 노이즈 $Z_{-y}$에 대해 조건부로 쓰면 다음과 같다.

$$\mathrm{Pr}[\mathcal{M}(X)=y\mid Z_{-y}=z_{-y}]=\mathrm{Pr}[Z_y\ge T_X(z_{-y})]$$

이를 전체 $z_{-y}$에 대해 적분하면 다음의 전체 확률을 얻는다.

$$\mathrm{Pr}[\mathcal{M}(X)=y]=\int \mathrm{Pr}[Z_y\ge T_X(z_{-y})]f_{Z_{-y}}(z_{-y})d{z}_{-y}$$

이제 이전의 threshold 부등식 $T_X(z_{-y})\ge T_{X^{\prime }}(z_{-y})-2{\Delta }_q$에 의해 다음 부등식이 성립한다.

$$\begin{array}{rl}\mathrm{Pr}[Z_y\ge T_X(z_{-y})]& \le \exp \left(-\frac{ϵT_X(z_{-y})}{2{\Delta }_q}\right)\\ & \le \exp \left(-\frac{ϵ(T_{X^{\prime }}(z_{-y})-2{\Delta }_q)}{2{\Delta }_q}\right)\\ & =\exp \left(ϵ\right)\cdot \exp \left(-\frac{ϵT_{X^{\prime }}(z_{-y})}{2{\Delta }_q}\right)\\ & =e^{ϵ}\mathrm{Pr}[Z_y\ge T_{X^{\prime }}(z_{-y})]\end{array}$$

이제 이 부등식을 전체 확률식 안에 넣으면 다음의 과정으로 $ϵ-$DP가 증명된다.

$$\begin{array}{rl}\mathrm{Pr}[\mathcal{M}(X)=y]& =\int \mathrm{Pr}[Z_y\ge T_X(z_{-y})]f_{Z_{-y}}(z_{-y})d{z}_{-y}\\ & \le e^{ϵ}\int \mathrm{Pr}[Z_y\ge T_{X^{\prime }}(z_{-y})]f_{Z_{-y}}(z_{-y})d{z}_{-y}\\ & =e^{ϵ}\mathrm{Pr}[\mathcal{M}(X^{\prime })=y]\end{array}$$

결국 이 과정에서 키 포인트는 $Z_y\sim \mathrm{Exp}\left(\frac{2\Delta }{ϵ}\right)$와 임의의 $K$에 대해, $\mathrm{Pr}[Z\ge K]=e^{-\frac{ϵK}{2\Delta }}$에 의해 항상 다음이 성립하는 것이다.

$$\mathrm{Pr}[Z_y\ge K-2\Delta ]\le e^{ϵ}\mathrm{Pr}[Z_y\ge K]$$

---

이러한 선택 메커니즘은 단순히 프라이버시를 숨기는 것을 넘어, 결과를 엉뚱하지 않게 만들어야 한다. Utility Theorem은 선택된 후보 $\hat{y}$의 실제 점수 $q(\hat{y};D)$가 실제 최댓값 $q(y^{\ast };D)$보다 얼마나 떨어질 수 있는지를 확률적으로 보장한다.

진짜 최적 후보를 $y^{\ast }=\underset{y\in Y}{\arg \max }q(y;X)$라 하자. $q(Y;X)+Z_Y\ge \underset{j}{\arg \max }q(j;X)+Z_j$d이므로

$$\begin{array}{rl}\mathrm{Pr}\left[q_{max}-q(\hat{y};X)>\frac{2{\Delta }_q(\log d+t)}{ϵ}\right]& =\mathrm{Pr}\left[q_{max}>q(\hat{y};X)+Z_{\hat{y}}-Z_{\hat{y}}+\frac{2{\Delta }_q(\log d+t)}{ϵ}\right]\\ & \le \mathrm{Pr}\left[q_{max}>\max q(j;X)+Z_j-Z_y+\frac{2{\Delta }_q(\log d+t)}{ϵ}\right]\\ & \le \mathrm{Pr}\left[Z_y-Z_j>\frac{2{\Delta }_q(\log d+t)}{ϵ}\right]\\ & \le d\times \exp \left(-(\log d+t)\right)\\ & =e^{-t}\end{array}$$

따라서 다음의 확률 보장을 얻는다.

$$\therefore \mathrm{Pr}\left[q_{max}-q(\hat{y};X)>\frac{2{\Delta }_q(\log d+t)}{ϵ}\right]\le e^{-t}$$

---

이로써 우리는

1. composition으로 복잡한 DP 알고리즘을 설계할 수 있게 되었고,
2. post-processing 덕분에 DP 출력을 안전하게 재활용할 수 있으며,
3. group privacy와 subsampling amplification으로 보장의 스케일링이 어떻게 이루어지는지,
4. k-means, selection problem 같은 실제 문제에 적용하는 방법을 알았다.

다만, 모든 문제가 해결된 것은 아니다. 지금까지 다룬 pure DP만으로는 빈번하게 쓰이는 Gaussian noise 같은 자연스러운 메커니즘을 다루기 어렵다. 또한 이 과정에서 $ϵ-$DP의 composition bound가 너무 보수적이어서, “작은 확률의 예외”를 허용하는 유연한 메커니즘의 적용에 무리가 있다.

5. Approximate Differential Privacy