Differential Privacy (5. Properties, more mechanisms)

본문은 James Honaker과 Salil Vadhan의 Computer Science 208: Applied Privacy for Data Science 강의의 Properties, more mechanisms와 Dwork의 The Algorithmic Foundations of Differential Privacy를 요약한 글입니다.

𝜀-DP 정의와 성질

지금까지 하나의 질의(쿼리)에 대한 DP와 라플라스 매커니즘에 대해 배웠습니다. 전 강의에서는 𝜀-DP를 다음과 같이 정의했습니다.

위의 M(D,q)∈T와 M(D’,q)∈T를 각각 M(D,q)=t, M(D’,q)=t로 변경하면 𝜀-DP를 point-wise하게 정의할 수 있으며, 위의 정의와 if and only if 관계가 성립합니다.

또한, 만약 메커니즘 M이 𝜀-DP이고, 임의의 함수 f에 대해 M’(x,q) = f(M(x,q))라고 하면 M’도 𝜀-DP입니다. 이 성질은 𝜀-DP가 post-processing에 닫혀있다고 표현합니다.

마지막으로, (basic) composition theory에 따르면 다음과 같은 식이 성립합니다.

이는 k개의 쿼리의 independent randomness를 이용한 것입니다.

𝜀-DP 확장

1. composition

이는 한명의 공격자가 k개의 질의를 할 때도 성립하는데, 이를 이용하면 M이 하나의 쿼리에 대해 𝜀-DP일 때, k개의 쿼리에 대해서는 k𝜀-DP임을 알 수 있습니다. 즉, global privacy loss를 𝜀_g로 설정한다면 𝜀는 𝜀_g/k로 줄어들게 됩니다. 따라서 𝜀가 작아지기 때문에 하나의 쿼리에 대해서는 감소하게 됩니다.

composition theorem과 post-processing을 통해 간단한 𝜀-DP 메커니즘으로부터 복잡한 알고리즘을 만들어낼 수 있습니다. 예를 들어서 stochastic gradient descent와 같은 많은 머신러닝 알고리즘은 low-sensitivity 쿼리(예: 평균 등)의 순열로 생각할 수 있습니다. 따라서 각 쿼리에 라플라스노이즈를 더해 모델을 DP하도록 만들어 결과값을 안전하게 보호할 수 있습니다.

𝜀-DP의 정의를 다시 해석하면 다음과 같습니다.

• 공격자가 나에 대해 무엇을 배운다면 그것은 나를 제외한 다른 모두의 데이터로부터도 배울 수 있는 것이다.
• 메커니즘은 ‘individual-specific’한 정보를 누출할 수 없다.
• 위 해석들은 공격자의 추가적인 정보나 계산 능력과는 관계 없이 보호된다.

하지만 주의할 점은 다음과 같습니다.

• 공격자가 민감 성질들을 추론할 수 없다는 것을 보장하지 않음.
• 데이터 분석 결과로부터 정보 제공자가 피해를 받지 않을 것임을 보장하지 않음.
• 몇개의 row로 localized되지 않은 정보에 대해서는 보호하지 않음.

2. Group privacy

𝜀-DP는 하나의 데이터가 변화했을 때 결과값이 변하지 않음을 보장합니다. 정의를 이용하면 k개의 데이터가 변화했을 때도 결과값이 변화하지 않도록 할 수 있습니다. 이를 수식으로 나타내면 다음과 같습니다.

여기서 group size k는 O(1/𝜀)수준이어야 합니다.

이를 이용하면 사용가능한 수준의 utility를 위해서 dataset의 크기 𝑛은 1 /𝜀 이상임을 도출할 수 있습니다. 통상적으로 프라이버시 보호를 위한 𝜀는 0. 01 ≤ 𝜀 ≤ 1로 설정합니다.

3. Bayesian interpretation

다음으로, 베이지안 관점에서 DP를 해석해보겠습니다. 먼저

가 공격자가 dataset에 대해 사전에 알고 있는 random variable distribution을 따른다고 하고, i번째 사람의 데이터가 지워지거나 다른 값으로 대체된

를 정의합니다. 그 다음 메커니즘

이 𝜀-DP, y는 가능한 output값이라고 하면 모든 x_i에 대해 다음이 성립합니다.

이 식은 메커니즘 M의 output이 y라는 정보를 가지고 있을 때 i번째 데이터가 x_i라고 판단할 확률은 X에 i번째 데이터가 있든 다른값으로 대체되거나 없어지든 𝜀 수준으로 같음을 의미하며, 각 확률은 posterior belief라고 할 수있습니다.

4. Variants of Definition

이번에는 지금까지 배운 데이터와 조금 다른 경우에 대해 설명드리겠습니다.

• histogram

dataset D는 다음과 같이 정의합니다.

먼저, X를 전체 데이터 집합이라고 하고, D를 X의 원소를 원소로 갖는 multiset이라고 합니다. D는 히스토그램 D∈N^X로 간단히 나타낼 수 있는데, 여기서 D_x는 x의 갯수입니다.

예를 들어 X={a,b,c}가 있다면 multiset D={a,a,b,b,b,c}를 간단하게 (2,3,1)∈N³으로 나타낼 수 있습니다.

neighbor는 다음과 같이 정의합니다.

먼저, D와 D’이 neighboring한다는 것은 |D∆D’|=1이라고 할 수 있습니다. 여기서 |D∆D’|=1이라는 것은 하나의 원소를 더하거나 뺐다는 것으로, 다음과 같이 l_1 norm으로 정의할 수 있습니다.

• Social network data

소셜 데이터에서 dataset은 node와 edge로 이루어진 그래프 G로 정의합니다. 소셜 데이터의 경우 dataset이 node와 edge로 이루어져있기 때문에 neighbor가 두가지로 정의될 수 있습니다.

neighbor v1

두 dataset이 하나의 edge만 다를 경우 neighboring한다고 정의합니다.

neighbor v2

두 dataset이 하나의 node가 다른 경우 neighboring한다고 정의합니다. 여기서 하나의 node가 변경될 때 변경된 node에 속한 edge가 모두 변하기 때문에 v1보다 더 많은 데이터가 변경되는 것을 알 수 있습니다. 즉, neighboring dataset의 차이가 크기 때문에 두 dataset에게 질의를 했을 때 두 값이 크게 달라지고, 공격자가 두 dataset을 구분하지 못하게 하기 위해서는 더 큰 노이즈를 추가해야 합니다.

5. Approximate Differential Privacy

지금까지 𝜀-DP에 대해서 정의했습니다. 𝜀-DP의 경우 모든 경우에서 확률의 차이가 𝜀수준이어야 하지만, 이 조건을 조금 완화해 1 − 𝛿의 확률로 성립하도록 만들 수 있습니다. 이렇게 𝜀-DP의 조건을 완화한 것을 (𝜀, 𝛿)-DP라고 하며, 다음과 같이 정의합니다.

여기서 주의할 점은 dataset에 n명의 사람이 있을 때, 한 사람이 달라지면 확률은 최대 1/n가 달라지기 때문에 항상 (0,1/n)-DP라는 점입니다. 따라서, 𝛿<<1/n여야 의미가 있으며, 보통 𝛿를 2^(-50)와 같이 매우 작게 설정합니다.

(𝜀, 𝛿)-DP도 𝜀-DP와 마찬가지로 composition theorem이 성립하며, group size가 O(1/𝜀)보다 작은 범위에서 group privacy도 보호됩니다. 다만, pointwise에 대해서는 성립하지 않습니다.

Approximate DP를 사용하면 더 다양한 메커니즘을 사용할 수 있습니다. (𝜀, 𝛿)-DP에서 가장 대표적인 메커니즘은 Gaussian Mechanism이며, 다음과 같이 정의됩니다.

또한, (𝜀, 𝛿)-DP에서는 advanced composition theorem을 사용할 수 있으며, 다음과 같습니다.