Differential Privacy(9. Implementing Local DP-Google, Apple, Microsoft)

본문은 James Honaker과 Salil Vadhan의 Computer Science 208: Applied Privacy for Data Science 강의의 Implementing Local DP(Google, Apple, Microsoft)와 Apple의 Learning with Privacy at Scale, Google의 RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response를 요약한 글입니다.

telemetry란 접근이 불가능한 지점에서 원격으로 데이터를 수집해 모니터링을 위해 수신 장비로 전송하는 통신 프로세스를 의미합니다. Google, Apple, Microsoft에서는 telemetry data의 프라이버시를 보호하는 방식으로 각각 “RAPPOR”, “Learning with Privacy”, “Collecting Telemetry Data Privately”를 제시했습니다.

Handling Large Domains

서버는 랜덤한 해쉬 함수 h:{1, … ,D} → {1, … ,m}를 모든 사용자에게 보냅니다(m<<D). 그 다음 이 h(x_i)를 히스토그램으로 근사해 Randomized Response Protocol을 적용합니다. RR protocol을 적용한 히스토그램을 f^∈ℤ^m라고 하고, {1, … , D}에 속하는 모든 v에 대해 frequency를 구하면 다음과 같습니다.

이는 unbiased estimator입니다.

다음으로 variance를 줄이기 위해 사용자를 임의로 k개의 집단으로 나눕니다. 각각의 집단은 각기 다른 해쉬 함수 h_j를 갖게 되며, 이러한 기법은 구글과 애플에서 사용되고 있습니다.

해쉬 함수를 각 집단에 l개씩 적용할 수도 있습니다. 이는 구글에서 사용되고 있으며, RR을 2l-hot 벡터에 적용합니다. 실험적으로 각 집단에 2개의 해쉬함수를 적용하는 것이 좋다고 알려져있습니다.

inference on the reports(Google)

먼저, 간단하게 하나의 집단에 하나의 해쉬 함수가 할당된다고 가정합시다. 집단 j의 해쉬값의 히스토그램은 다음과 같이 나타낼 수 있습니다.

이 히스토그램에 노이즈를 추가하고, s개의 v에 대해 frequency를 구하기 위해 행렬을 만들 수 있습니다.

그 뒤 LASSO regression을 사용하면 다음 식을 만족하는 sparse한 F^을 찾을 수 있습니다.

다시 F^에 OLS regression을 사용해 coefficient와 standard error, p value를 구할 수 있습니다.

Discovering Unknown Values(APPLE)

지금까지 설명한 방법으로 서버가 frequency를 추정하기 위해서는 v_1, …, v_s를 결정해야 했습니다. 그렇다면 v가 알려지지 않은 경우에는 어떻게 해야 할까요? 아이디어는 v[j]를 각각 구성하는 것입니다.

먼저 모든 j=1, … , log D에 대해 h(x_i)||x_i[j]에 RR을 취합니다. 그 다음 𝜎_j∈{-1,+1}에 대해 𝑓̂^[𝑤||𝜎_𝑗]가 크다면 ℎ (𝑣)= 𝑤 이고, 𝑣_ 𝑗 = 𝜎에서 자주 발생하는 v를 찾을 수 있습니다. 만약 여러 𝜎_𝑗에서 모두 큰 값이 나온다면 v는 각 𝜎_𝑗를 곱한 값이 됩니다.

Controlling Privacy Loss over Time

구글에서는 v를 memoization하고 two-level RR을 사용합니다. RAPPOR은 bloom filter에서 영감을 받아 제작되었는데, 대략적인 그림은 다음과 같습니다.

RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response

1. Signal: 가장 먼저 실제값을 Bloom filter B에 표시합니다. 이 그림에서는 68이라는 숫자를 256개의 비트 크기를 가진 bloom filter에 hash function 4개로 표시했습니다.
2. Permanent RR(𝜀_1-DP): 다음으로 1에서 만든 bloom filter B의 각 값을 특정한 확률로 뒤집는 RR을 수행합니다. 이렇게 만들어진 fake bloom filter B’는 이 과정에서 변하지 않고 계속 사용됩니다.
3. Instantaneous RR(𝜀_2-DP): 2에서 만든 fake bloom filter B’에서 각 값이 0인지 1인지에 따라 다른 확률로 새로운 bit array S에 1을 표시합니다. S는 고정된 B’에 따라 즉각적으로 만들어지며, 이렇게 만들어진 S는 서버에 보내집니다.

마이크로소프트에서는 연속적인 값 v에 대해서 memoization을 합니다. 여기서는 반올림 사용하는데, v가 작은 값 변화하더라도 반올림한 값은 거의 변하지 않는다는 성질을 이용합니다.

애플에서는 익명화를 통해 개인정보를 보호합니다. 즉, 애플은 각각의 리포트가 어떤 사용자에게서 왔는지 알지 못합니다. 이러한 과정을 통해 개인정보 보호를 강화할 수 있습니다.

Utility, critiques

구글의 RAPPOR는 경험적으로 𝑝 ∈ [0,1]일 때, sample size 𝑛 ≳ 10/ p²가 필요하다고 알려져있습니다. 즉, p가 작아질수록 더 많은 샘플이 필요합니다.

마지막으로 지금까지 살펴본 기업들에서 사용하는 DP 방법들의 단점들을 살펴보겠습니다.

• 애플과 마이크로소프트는 코드나 privacy loss parameter을공개하고 있지 않습니다.
• 애플은 각 리포트의 privacy loss 𝜀를 1 또는 2로 하고 있습니다. 네가지 리포트에 대해 하루에 발생할 수 있는 최대 privacy loss 𝜀는 14이고, 더 많은하루가 아니라면 privacy loss가 unbounded가 됩니다. 즉, privacy loss가 매우 크다는 단점이 있습니다.
• 구글은 사용자의 데이터를 수집할 때 DP를 적용하지 않는 경우가 많습니다.
• 구글에서는 accuracy때문에 RAPPOR을 점차 사용하지 않는 추세입니다.