Differential Privacy(8. Foundations of Local DP)

Published in

slcf

8 min readJul 24, 2021

본문은 James Honaker과 Salil Vadhan의 Computer Science 208: Applied Privacy for Data Science 강의의 Foundations of Local DP와 Adam Smith의 Local-ish Models for statistical Differential Privacy를 요약한 글입니다.

Local DP

𝜀-DP의 경우 신뢰할 수 있는 curator가 존재해 모든 참여자의 원본 데이터를 가지고 있고, 그 curator에 질의를 할 때 노이즈를 추가해 데이터를 보호했습니다.

𝜀-DP, 단 하나의 값이 달라지더라도 A(x)와 A(x’)의 값이 비슷해야 합니다.

하지만 공격자가 이 curator을 공격하는 경우 문제가 발생할 수 있습니다. 이러한 상황을 해결할 수 있는 방법으로 “Local-DP”가 있습니다.

Local DP의 경우 모든 참여자가 Q_i의 ‘local randomizer’로 자신의 데이터를 randomize 시킵니다. 그 후 이 값을 aggregator에게 전송합니다. aggregator은 이 각각의 원본 데이터를 알지 못하기 때문에 위 시나리오에서 정보가 유출되지 않습니다. 각 local randomizer Q_i가 𝜀-DP 메커니즘일 때, 모든 Q_i와 aggregator A를 합친 protocol을 𝜀-local DP라고 정의합니다.

𝜀-local DP는 trusted curator가 필요하지 않으며, 𝜀-DP처럼 한 값이 failure일 필요가 없으며 높은 활용도를 갖습니다. 하지만 𝜀-DP에 비해 낮은 accuracy를 갖는 단점이 있습니다.

Randomized Response

local 𝜀-DP의 한 예시로 Randomized Response가 있습니다. Randomized Response는 설문조사 등에서 사용되던 방식으로, 민감한 질문을 할 때 local한 노이즈를 추가해 개인의 프라이버시를 보호할 수 있습니다. 예를들어 ‘부정행위를 한 경험이 있는 학생의 비율’에 대해 조사를 하고 싶은 경우, 학생들은 “부정행위를 한 적이 있습니까?”라는 질문을 받으면 부정행위를 한 적이 있더라도 “네”라는 대답을 하기 어려울 것입니다.

이 문제를 해결하기 위해 1965년에 제안된 Randomized Response는 다음과 같습니다.

앞면이 나올 확률이 p인 동전을 던져 동전의 앞면이 나온다면 질문에 대한 답변이 무엇인가에 관계 없이 “네” 라는 대답을 합니다.
뒷면이 나온다면 정직하게 대답을 합니다.

이 상황에서는 질문을 하는 사람은 동전이 앞면이 나왔는지 뒷면이 나왔는지 알지 못하기 때문에 설문자가 “네”라는 답변을 한 것이 동전이 앞면이기 때문인지, 뒷면이 나왔는데 자신이 부정행위를 해서 “네”라는 대답을 했는지 알지 못합니다. 따라서 질문을 받은 사람은 개인정보에 대한 우려 없이 제대로 된 답변을 할 수 있게 됩니다. 이 상황을 그림으로 나타내면 다음과 같으며, 색이 칠해진 범위에 있는 학생들을 “네”라는 대답을 하게 됩니다.

조사자는 실제로 부정행위를 한 적이 있는 학생의 비율 q를 계산할 수 있습니다. 조사자가 수집한 “네”는 p의 확률로 동전이 앞면이 나온 답변과 (1-p)q의 확률로 뒷면이 나오고 부정행위를 한 답변을 얻을 수 있습니다. 따라서 수집한 “네”의 비율을 이용해 q값을 구할 수있습니다. (만약 수집한 ‘네’가 0.75, 동전의 앞면이 나올 확률이 0.5라면 0.75=0.5+0.5*q를 풀어 절반의 학생이 부정행위를 했음을 알 수 있습니다.)

이 상황을 발전시켜 local 𝜀-DP로 만들 수 있습니다. 이번에는 위와 같은 설문조사 상황에서 Randomization operator을 정의하겠습니다. 답변은 Y/N이기 때문에 +1, -1이라고 하고, 각 답변자 x_i가 y∈{-1,+1}로 답변한다면 Randomization operator Q는 다음과 같이 정의할 수 있습니다.

즉, 1/(e^ε+1)의 확률로 자신의 답변을 뒤집는 형태가 됩니다. 이를 그림으로 표현하면 다음과 같습니다. 아래 그림에서 +1이라고 답변한 사람은 빗금친 영역의 사람이 됩니다.

Randomized Response를 통해 count나 sum 함수에 노이즈를 추가한 경우 error bound는 ±O(√n/ε)가 되며, 평균 등 통계치를 구하는 쿼리에 대해서는 ±O(1/ε√n)수준의 error bound를 갖습니다. 이는 count나 sum에 대해서는 ±O(1/ε), 통계치에 대해서는 ±O(1/εn) 수준의 error bound를 갖는 일반적인 DP에 비해 좋지 않지만, 여전히 useful하다고 말할 수 있습니다.

Randomized Response를 이용하면 히스토그램에 대한 프라이버시를 보호할 수도 있습니다.

먼저 x가 {1,2,…,d} 중 하나의 값을 갖는다고 합니다. 히스토그램 h(x)는 (n_1, …, n_d)라고 정의할 수 있는데, n_j는 x=j인 x의 갯수를 의미합니다. 이번에는 e_(x_i)를 정의합시다. e_(x_i)는 길이가 d고 x_i번째 원소만 1인 one-hot 벡터입니다(즉, x_i만 1이고 나머지는 0인 벡터). 이렇게 정의하면 히스토그램 h(x)는 모든 e_(x_i)의 합이라고 생각할 수도 있습니다.

이러한 히스토그램에 앞서 정의한 randomized operator을 적용할 수 있습니다. 앞서 정의한 Q에서 {-1,+1}을 {0,1}로 바꾼 operator을 Q’이라고 한다면 e_(x_i)의 모든 원소 (0과 1)을 Q을 통해 1/(e^ε+1)의 확률로 답변을 뒤집을 수 있습니다. 이렇게 변환된 Q’(e_(x_i))를 모두 더하면 프라이버시가 보호된 히스토그램을 만들 수 있습니다.

이렇게 얻어진 히스토그램의 각 bin의 expected error bound는randomized response와 마찬가지로 ±O(√n/ε)가 됩니다. 또한, 모든 d 개의 bin에 대한 expected max error는 ±O(√(n logd)/ε)가 되며, Q’은 2𝜀-local DP가 됩니다.

Interactive mechanism

이번에는 interactive mechanism가 DP라는 것이 어떤 의미를 갖는지 살펴보겠습니다. Interactive mechanism은 여러개의 질의를 하는 상황에서 다음번에 하는 질의가 그 전 질의들과 상관관계를 갖는 메커니즘으로, 단순히 앞서 배웠던 composition theorem을 이용한 ‘여러개의 질의를 하는 상황’이라고 생각할 수 있습니다. 하지만 이보다 더 좋은 정의를 만들 수도 있습니다.

즉, C(D)와 상호작용을 한 경우나 C(D’)과 상호작용을 한 경우나 HIV에 걸렸나는 질문에 YES라고 대답할 확률이 ε수준에서 같다고 생각할 수 있습니다. 이러한 정의를 Local DP로 확장시킬수도 있습니다.

local DP의 일반적인 DP와는 다르게 dataset이 하나가 다를 필요가 없습니다. 다만 모든 i에 대해서 각각의 randomizor Q_i가 존재하고, Q_i에 들어가는 x_i값이 달라져도 ε수준에서 같아야 local (ε,δ)-DP를 만족할 수 있습니다.

다음으로는 Multiparty DP에 대해 설명하겠습니다. 지금까지 curator가 하나인 상황을 다뤘지만, k개의 curator가 존재하는 상황에서도 DP를 사용할 수 있습니다. 각 curator C_j가 dataset D^(j)를 갖는다고 하면 multiparty DP는 다음과 같이 정의할 수 있습니다.