kni020's profile image

kni020

November 26, 2022 00:00

Local Differential Privacy

security

들어가며

지난번에는 어느 한 데이터셋에서 하나의 데이터가 가지는 영향력에 대해서 공부해 보았습니다. 어떤 데이터셋에서 한 데이터를 제외한 나머지 정보를 다 알고 있을 때, 나머지 한 개의 데이터를 유출할 수 있는지에 대한 것이었습니다. Differential Privacy는 이를 수식을 활용해 표현한 것으로, ϵ의 값으로 데이터의 안정성을 확인할 수 있었습니다.

이번에는 Differential Privacy와는 조금 다르지만 개인의 프라이버시를 보호할 수 있는 개념을 소개하려고 합니다. 개인이 신뢰하지 않는 서버에 데이터를 제공했을 때의 프라이버시를 보호하기 위한 개념인 Local Differential Privacy에 대해 소개하려고 합니다.

Local Differential Privacy (LDP)

등장 배경

기존의 DP는 데이터 셋 안에서 어느 한 데이터의 영향력을 판단하여, 노이즈를 이용해 영향력을 줄이고 그 영향력을 측정하는 것이 목적이었습니다.

이 전제 조건에는, 서버는 신뢰할 수 있는 존재라는 점입니다. 데이터를 갖고있는 주체가 신뢰할 수 있는 상태에서, 노이즈를 가해 사용하는 것이었습니다.

하지만 데이터의 소유자를 신뢰할 수 없다고 할 경우, 데이터를 하나 제공하는 것 조차 문제가 될 수 있습니다.

Local Differential Privacy라고 부르는 LDP는 기존의 DP보다 한층 더 프라이버시를 신경쓰는 이론입니다.

예를 들어서, A랑 B라는 두 의견으로 나누는 경우가 있다고 생각해봅시다. A를 좋아하는 사람들이 모인 집단에서 설문조사를 했을 경우, 실제로 B를 좋아한다 하더라도 B를 좋아한다고 말할 수 없을 것입니다. 하지만 그렇다고 거짓말을 할 수 없습니다. 이 경우에, DP를 적용한다면 우리는 B를 좋아하는 사람이 있다는 사실을 알 수 있습니다.

하지만 이러한 것은 설문조사를 하는 사람을 신뢰하지 못하는 순간부터 개인의 프라이버시를 존중하지 못하는 것이라고 볼 수 있습니다. 하지만 이런 특징을 숨기지 못한다면, 프라이버시를 보장한다고 할 수 없을 것입니다.

이를 위해서, 원래의 데이터가 가지는 특성을 최대한 지키며, 원래의 데이터를 숨기는 것이 Local Differential Privacy라고 할 수 있습니다.

이러한 식으로 데이터의 privacy를 지키는 방법으로는 randomized response가 있습니다. input perturbation라고도 하는데, 이는 원래 민감한 정보의 질문을 할 때 활용한 방법이었습니다. 설문조사의 결과를 통계적 특성은 유지한 채 랜덤하게 보이는 값으로 바꿔서 전달한다면, 정보를 수집하는 입장에서는 개인의 민감한 결과를 알 수 없게 됩니다.

예를 들어, B를 선택한 하나의 데이터를 A를 선택한 데이터 2개, B를 선택한 데이터 4개로 확장한다면 B가 더 많다는 것은 변함이 없지만, A를 좋아하는 그룹에서 “B를 선택한 사람이 한명은 존재한다!”라는 결과는 도출할 수 없게 됩니다.

이것과 같이, 데이터들의 특성들을 유지하면서도 데이터셋에서 그 데이터셋의 특성을 얻을 수 없도록 하는 것을 Local Differential Privacy 라고 합니다.

ϵDP, 그리고 (ϵ,δ)DP

지난번에 적었던 내용이지만, Database의 프라이버시 정도를 측정하기 위한 방법으로 (ϵ,δ)DP 가 제안되었습니다. 그래서 (ϵ,δ)-Differential Privacy 의 내용을 간단하게 다시 적어보려 합니다.

데이터셋 D1이 있습니다. 그리고 D1과 하나의 데이터를 제외한 나머지 데이터가 전부 같은 데이터셋 D2가 있습니다.

그리고 데이터셋을 입력으로 가지는 알고리즘 A라고 가정합니다.

해당 조건하에서, 다음 식을 만족하는 만족하는 경우, D1ϵ-differential privacy라고 합니다.

Pr[A(D1)S]eϵ×Pr[A(D2)S]

이 식에서, δ항을 추가한다면 (ϵ,δ)-differential privacy 라고 합니다.

Pr[A(D1)S]eϵ×Pr[A(D2)S]+δ

제안된 이 방법에서 얻는 ϵ,δ 값을 통해 프라이버시의 정도를 측정하고, 판단할 수 있게 되었습니다.

ϵ-Local Differential Privacy

(ϵ,δ)-Differential Privacy 의 정의를 한번 다시 돌아보았습니다. 하지만 Local Differential Privacy는 Differential Privacy와 다른 방법을 사용하여 비교합니다.

Local Differential Privacy는 Differential Privacy와 다르게 어떤 데이터를 특정지을 수 없게 하는 것이기 때문에, 일반적인 두 데이터를 통해 비교합니다. ϵ-Local Differential Privacy의 정의를 보면 다음과 같습니다.

어떤 두 데이터 x,x과 랜덤한 알고리즘 A가 있다고 생각합시다.

다음의 식을 만족하면 알고리즘 A가 ϵ-Local Differential Privacy 를 만족한다고 합니다.

Pr[A(x)S]eϵ×Pr[A(x)S]

간단하게 하면 데이터를 input으로 받아 결과물을 내는 알고리즘 A가 있다고 했을 떄, 두 데이터가 같은 결과물 안에 속할 확률이 eϵ 인 경우, ϵ-LDP 를 만족한다고 합니다.

해당 Local Differntial Privacy를 위한 알고리즘으로, RAPPOR에 대해 소개하려 합니다.

RAPPOR - Randomized Aggregatable Privacy-Preserving Ordinal Response

개요

이 논문은 Local Differential Privacy를 소개하면서, 이 개념이 적용된 예시를 위해 소개합니다. 이 논문은 Google이 Chrome 홈페이지에 대한 정보나 다른 프로세스에 대한 정보들을 수집할 때 사용된 Local Differential Privacy의 적용 방법입니다.

RAPPOR은 데이터를 수집하는 과정에서 numeric value 하나에 어떠한 방식으로 Local Differential Privacy를 적용하는지 제안하고 설명하고 있습니다.

RAPPOR이란?

RAPPOR이란 Randomized Aggregatable Privacy-Preserving Ordinal Response의 줄임말로, 구글에서 사람들의 정보들을 수집하기 위해서 구글에서 제안한 randomized response입니다. 이 방법은 randomzied response 중에서도 여러 데이터 중에 하나를 고르는 정답에 대해서 Local Differential Privacy를 제공합니다.

RAPPOR 알고리즘

RAPPOR의 과정을 알아보겠습니다. 먼저, 알고리즘을 보면 다음과 같은 과정입니다.

RAPPOR은 먼저 어느 한 값의 데이터를 받으면, 해쉬함수 h와 정해진 사이즈 k를 통해 Bloom Filter B를 제작합니다.

제작된 Bloom Filter B의 각 비트 Bi를 활용하여 Fake Bloom Filter를 제작합니다. Fake Bloom Filter를 제작하기 위해 특정 확률 f를 사용합니다. Bi1f의 확률로 각 Bloom Filter의 Bi들을 그대로 보존합니다. 그리고 나머지 f/2, f/2의 확률로 0과 1을 무작위로 정해서 Fake Bloom filter B을 제작합니다.

마지막으로 Fake Bloom Filter를 통해 제작된 데이터에서 Bi이 0일때랑 1일때, 각각 p와 q의 확률로 서버에 제출할 마지막 데이터 Si의 값을 1로 정합니다. 이렇게 만든 S를 서버에 제출합니다.

예시를 들면, 다음의 사진과 같습니다.

실제로 Local Differential Privacy를 위한 과정은 이게 전부입니다. 각 과정별로 큰 알고리즘도 없기 때문에 연산량도 적고, Client의 기기에서 빠르게 수행이 가능합니다. Local Differential Privacy가 적용되어 있으면서 정해진 확률 f,p,q를 통해 randomize하고있기 때문에 2중으로 보호하고 있습니다.

Differential Privacy of RAPPOR

이번에는 처음에 다루었던 ϵ-Local Differential Privacy을 통해 RAPPOR의 privacy를 측정하려고 합니다.

실제로 어떤 input v를 넣었을 때 S 라는 결과가 나오는 경우를 생각해보겠습니다. 이 경우가 일어날 확률을 각 단계별로 식으로 세워보면 다음과 같습니다.

P(S=s|V=v)=P(S=s|B,B,v)P(B|B,v)P(B|v)=P(S=s|B)P(B|B)P(B|v)=P(S=s|B)P(B|B)

그리고 이 과정에서, P(B|B) 는 실제 bi,bi의 값과 f를 통해서 예측할 수 있습니다. 이를 식으로 써보면, 다음과 같습니다.

P(bi=1|bi=1)=12f+1f=112fP(bi=1|bi=0)=12f

이를 이용해서, P(B=b|B=b) 일 확률을 계산해보면 다음과 같습니다. 편한 계산을 위해, 일관성을 잃지 않고 B에서 b1 ~ bh이 1이고, 나머지는 0이라고 가정하겠습니다.

P(B=b|B=b)=hi=0(12f)bi(112f)1bi×ki=h+1(112f)bi(12f)1bi

이러한 값을 얻고, 두 input에 대해 다음 식으로 ϵ의 계산이 가능합니다.

lnPr[A(x)S]Pr[A(x)S]ϵ

위 식에 그대로 대입하고 난 뒤 최댓값을 구한다면, bi들이 같은 값일수록 큰 값이 나옴을 알 수 있습니다. 즉, 제일 작게 계산이 될 경우는 ϵ값이 다음과 같이 유도됩니다.

ϵln(112f12f)

비슷하게 Server에 Report하기 마지막 전 단계에 대한 ϵ도 동일한 방법으로 계산이 가능하며, 계산시 다음과 같은 ϵ1을 얻을 수 있습니다.

ϵ1=hlog(q(1p)p(1q))

이와 같이 Local Differential Privacy를 적용할 수 있고, RAPPOR에서 정의한 확률에 따라 ϵ값이 달라짐을 알 수 있습니다.

결론

이번에는 Local Differential Privacy의 개념과, 현재 어떠한 방식으로 사용되는지 Google이 제안한 RAPPOR를 통해 확인해볼 수 있었습니다. Local Differential Privacy가 적용되는 것은 굉장히 특정한 상황일 수 있으나, 실제로 Differential Privacy를 활용하는 것보다는 조금 더 높은 프라이버시를 보장할 수 있을 것입니다. 이는 분산학습을 하는 경우에, 각 Client들의 데이터를 모으는 과정에서 사용되는 등, 여러 확장 가능성이 있음을 알 수 있었습니다.

참고 자료

  1. What Can We Learn Privately?
  2. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response