Differential Privacy - Part 1

Differential Privacy - Definition

Adjacent Data

DP(Differential privacy)에서 말하는 인접합 데이터 \(D_1\), \(D_2\)라는 것은 두 데이터 사이에서 하나의 데이터 샘플만 차이가 날 때를 말한다. 예를 들어 철수는 10개의 연락처를 가지고 있는데, 영희는 철수의 연락처에서 ‘가희’의 연락처를 제외하고 9개의 연락처를 가지고 있다고 하자. 이 때, 영희는 철수의 adjacent data 혹은 영희는 철수의 adjacent data라고 할 수 있다. 이것은 data 단계의 인접함으로 정의된 것인데(example-level privacy), 때에 따라서는 고객(user, clients) 단계에서도 정의될 수 있다. 예컨대, S업체는 10명의 고객이 있고 각 고객들은 각기 다른 연락처를 지니고 있다. 그리고 K업체는 9명의 고객이 있는데, 이 9명의 고객은 동일하게 S업체에도 등록이 되어 있다. 따라서 S업체와 K업체는 오직 1명의 고객만 차이가 나므로, S업체와 A업체는 user-level privacy아래에 인접한 데이터를 가지고 있다고 말할 수 있겠다.

Differential privacy

어떤 무작위 함수(randomized algorithm) \(f\)는 \(\mathcal{D}\)에 속한 데이터 \(D_i\)를 입력값으로 받아 공간 \(\mathcal{S}\)으로 맵핑을 한다고 하자 \(\mathcal{f}: \mathcal{D} \rightarrow \mathcal{S}\). 이 때, 함수 \(f\)가 임의의 인접한 두 데이터(adjacent data) \(D_1, D_2 \in \mathcal{D}\)에 대해서 아래와 같은 조건을 만족한다면, \(\epsilon\)-differential privacy를 제공한다고 할 수 있다. (\(\epsilon \geq 0\) , \(s \subseteq \mathcal{S}\))

\[Pr[f(D_1)\in s] \leq \exp{(\epsilon)} \cdot Pr[f(D_2) \in s]\]

여기서 짚고 넘어갈 점은 \(\epsilon\)과 함수 \(f\)가 정해지는 순서이다. 우선, 어떤 함수 \(f\) 가 존재한다고 가정해보자. 이 때 우리는 \(f\)가 어느 정도의 \(\epsilon\)을 지니는지 모른다. 그러나 수식적으로 모든 \(D_i\)에 대해서 위의 부등호를 만족함을 증명했다고 하자. 이 때가 되어서야 함수 \(f\)는 얼마의 \(\epsilon\)을 지니는지 알 수 있다. 즉, \(f\)가 먼저 존재하고 이 \(f\)는 특정 \(\epsilon\)에서 DP의 조건을 만족시키는 함수임을 확인할 수 있다. 반면, 어떤 \(\epsilon\)과 데이터 \(D_i\)가 존재한다고 하자. 여기서 우리는 위의 조건을 만족시키는 \(f\)를 찾아야 하는 상황이 있을 수도 있다. 이때에는 앞선 순서와 반대로 \(\epsilon\)이 먼저 결정이 되고 \(\epsilon\)-DP를 만족하는 \(f\)가 나중에 결정이 된다.

그나저나 위의 식은 무엇을 의미하는 것일까?

식을 단순하게 풀어서 이해해보자면 다음과 같다. \(\epsilon\)-DP를 만족하는 함수 \(f\)에 의해 하나의 샘플만을 제외했을 경우(\(D_2\))가 여전히 공간 \(\mathcal{S}\) 안의 부분 공간 \(s\)에 존재할 가능성은 \(f(D_1)\)이 부분 공간 \(s\)에 존재할 부분 가능성에 비해 \(\exp{(\epsilon)}\) 에 반비례하거나 그것보다 커야 한다. 따라서 \(\epsilon\)이 0이라면 \(f(D_2)\)는 \(f(D_1)\)보다 같거나 더 높은 확률로 부분 공간 \(s\)에 존재해야만 한다. 그리고 \(\epsilon\)이 커지면 커질수록 \(f(D_2)\)가 부분 공간 \(s\)에 속할 확률은 급격히 감소하게 된다.

이것을 다르게 생각해보자면, \(\epsilon\)이 작으면 작을수록 (1개의 샘플만 다른) 서로 다른 두 데이터가 같은 부분 공간 상에 포함될 확률은 높아진다. 따라서 같은 부분 공간 상에 있는 서로 다른 두 데이터를 “다르다”라고 “분멸”하기 어렵다. 반면에 \(\epsilon\)이 커지면 커질수록 두 데이터가 같은 부분 공간 속에 속할 확률은 멀어지고 따라서 이 두 데이터를 “분별”해낼 수 있는 여지는 높아진다. 즉, 함수 \(f\)를 통해 후처리된 데이터의 정보가 “다르다” 라는 것을 결정하는 값은 \(\exp{(\epsilon)}\)이다.

그러나 잊지 말아야 할 사실은 “\(\epsilon\)-DP를 만족하는 \(f\)“에서 이미 \(\epsilon\)의 값은 정해졌다. 함수 \(f\)에 다른 두 데이터를 입력하고, 각각 도출된 두 개의 결과값을 도출했다고 하자. 이 결과값을 본 사람이 “이 두 데이터는 원래 다른 값이 군요!”라고 할 여지는 이미 우리가 함수 \(f\)를 써야겠다 라고 마음먹은 그 시점에 \(\exp{(\epsilon)}\)만큼 결정된 사항이다. 따라서 우리는 함수 낮은 \(\epsilon\)을 가지는 “좋은” 함수 \(f\)를 잘 찾아서 서로 다른 데이터를 잘 구별하지 못하는 함수값으로 변환시키는 작업을 거쳐야 한다.

함수 \(f\)는 무엇을 의미하는가?

많은 튜토리얼에서 다루는 상황은 Counting에 관한 것들이다. 예를 들어, 우리가 가진 데이터는 A기업 이사회의 안건 투표 결과라고 생각하자. 이 때, 함수 \(f\)는 이사의 투표용지에서 각 안건들의 득표수로 맵핑을 하는 counting function이 될 수 있겠다. 만약 어떤 간부가 1명의 경쟁자가 어떤 결정을 내렸는지 알고싶어한다는 시나리오를 생각해보자. 이 간부는 경쟁자를 제외한 다른 이들의 모든 결정을 알고 있다. 이 때, 단순하게 득표수를 공개하는 것은 이 경쟁자가 어떤 선택을 내렸는지를 분명하게 보여줄 수 있다. 따라서, 우리는 단순한 counting function \(f\)가 아니라, 낮은 \(\epsilon\)-DP를 만족하는 counting function \(f\)를 사용해서 결과는 변함이 없지만 (같은 부분 공간에 속하고 있지만), 서로 다른 두 데이터에 대해서 구분을 하기 힘들게 만들어야만 한다.

Privacy Loss

DP 정의에서 \(\epsilon\)이 의미하는 것. 머신 러닝과 관련된 대부분의 텍스트에서 Loss는 Cost function을 의미한다. 그러나 여기서의 Loss는 말그대로(literally) 손실을 의미하기 때문에, ‘정보의 손실(leakage)’이라는 의미와 동일하다. 따라서 \(\epsilon\)이 작다라는 것은 정보의 노출이 적다 라고 받아들이면 되겠다. 반대로, \(\epsilon\)이 커질수록 privacy는 감소하여 ‘정보의 손실(leakage)’은 증가한다.

privacy loss라는 의미 아래 \(\epsilon\)-differential privacy는 무엇을 뜻할까?

처음에는 잘 와닿지 않았는데, 생각해보면 정보보호라는 차원에서 이해를 해볼 수 있을 것 같다. 우리가 가진 데이터를 ‘어떤 의미’ 아래에서 정보 보호를 하고 싶다. 그래서 우리는 함수 \(f\)를 잘 정의해서 데이터 보안이 가능한 공간 \(\mathcal{S}\)를 만들어 주고 싶다. 이때 데이터 보안이 가능하다는 것을 보장해주기 위해서는 \(f\)로 맵핑한 데이터가 공간 \(\mathcal{S}\)가 위에서 언급한 조건을 만족 시킬 수 있어야 한다. 위의 조건을 만족시키는 공간 \(\mathcal{S}\)는 \(\epsilon\)만큼의 손실(위험성, risk)를 가지고 있다. 물론 함수 \(f\)가 맵핑 시키는 \(\mathcal{S}\)는 ‘어떤 의미’를 잘 나타내는 특별한 공간을 만들 수 있어야 한다. 그러므로 우리가 고민을 해야하는 것은 “어떻게 작은 \(\epsilon\)을 가지는 확률 함수 \(f\)를 찾을 수 있을까?” 이다.

Privacy Budget/Cost

Privacy Loss의 최대값을 의미한다. 최대값이란 무엇을 의미하는가? 예를 들어, \(\epsilon\)-DP를 만족하는 함수 \(f\)에서 특정한 input값에 대한 output을 한 번 얻어냈다고 가정해보자 (query를 한 번 날렸다). 이 것으로는 \(\epsilon\)이 작을 경우에 내가 지닌 결과와 유의미한 차이점을 발견하기 힘들 것이다. 그러나 이 과정을 계속 하다보면 privacy가 점점 희석되고 (central limit theorem을 떠올려보자), 결국에는 어떠한 값으로 수렴하게 될 것이다. Differential Privacy는 이렇게 많은 query를 날렸을 경우 privacy를 보장해주지는 못 한다.

따라서 privacy loss는 축적된다고 볼 수 있다. \(k\) 번의 query를 날리면 \(k\epsilon\)-DP가 되어버린다. 여기서 \(k\epsilon\)이 지닐 수 있는 최대값을 privacy budget이라고 일컫는다. Privacy Budget이 크다는 말은 그만큼 많은 Query를 날려야 한다는 의미이고, (하나의 Query에서 발생되는) 정보의 노출이 굉장히 작음을 의미한다.

Reference