Differential Privacy (7. Programming Interfaces for DP)
본문은 James Honaker과 Salil Vadhan의 Computer Science 208: Applied Privacy for Data Science 강의의 Implementing Differential Privacy Programming Interfaces for DP를 요약한 글입니다.
앞서 배운 DP의 여러 메커니즘을 바탕으로 DP 인터페이스를 프로그래밍하는 방법에 대하여 소개하고자 합니다.
Matrix Mechanism
2020년 인구 조사 프로젝트에서는 개인의 프라이버시를 보호하면서도 메커니즘의 정확도를 최적화하기 위하여 “matrix mechanism”을 사용했습니다.
이 메커니즘은 쿼리집합 Q가 주어져 있을 때, (논문에서 Q는 workload query라 정의) 새로운 쿼리집합 Q’(strategy query)와 transformation matrix B를 정확도를 높이는 방향으로 조정해 나가는 메커니즘입니다.
Matrix mechanism은 크게 두 단계 과정으로 이루어져 있습니다. Workload query가 주어지면 메커니즘은 strategy query라는 다른 쿼리집합을 만들어냅니다. Strategy query는 DB에 접근하여 라플라스 메커니즘과 같은 DP 메커니즘에 의해 노이즈 섞인 답을 얻게 되고, 이 답에 행렬 B를 곱해주는 과정에 의해 workload query에 노이즈가 섞인 답을 도출해냅니다. 즉, 메커니즘의 최종 아웃풋은 DB에 접근해서 얻어지는 것이 아닌 strategy query로부터 도출되는 값인데, Li’14 논문에서는 라플라스나 가우시안 메커니즘으로 MSE를 최소화하는 Q’과 B를 찾는 것은 랭크 제약이 있는 semidefinite 문제와 동치임을 증명하였습니다. 이는 곧 optimizing 문제이므로, matrix mechanism을 통해 optimizing accuracy이 가능함을 알 수 있습니다.
Range Query
Matrix mechanism에서의 workload 쿼리로는 종종 range query가 사용됩니다. Range query는 특정 범위 내 있는 데이터 수를 아웃풋으로 갖는 쿼리입니다. Workload 쿼리가 range query인 상황에서 strategy query Q’을 어떻게 정하는지에 따라 메커니즘의 노이즈와 효율이 달라질 수 있습니다. 한편, Range query는 binary tree 형태로도 표현할 수 있는데, 이 경우 쿼리의 sensitivity는 트리의 깊이에 비례함이 증명되어 있습니다. (Hay-Rastogi’10)
Programming DP Interfaces
1. PinQ
DP 알고리즘은 데이터 분석가들이 알고리즘을 쉽게 사용할 수 있도록 하고, DP라는 신뢰를 줄 수 있도록 설계되어야 합니다. PinQ는 프라이버시를 보호하면서도 데이터를 분석할 수 있는 플랫폼인데, PinQ에서는 립시츠 데이터 변환 방식을 사용하여 사용자의 민감 데이터를 보호합니다.
두 데이터셋 x와 x’간의 distance를 서로 다른 row의 수라 정의를 하고, 이를 d(x, x’)라 표기하면 위와 같이 c-립시츠 변환이 정의됩니다. 정의 아래에는 립시츠 변환의 렘마들이 소개되어 있습니다. 이를 통해 립시츠 변환 연산이 반복되면 epsilon과 관련된 식들이 계속 유도됨을 알 수 있는데, 프라이버시 보호를 위해 소요되는 예산을 재귀적으로 추적할 수 있다는 것이 립시츠 변환의 장점입니다.
립시츠 변환은 PinQ 인터페이스의 기초가 되는 데이터 보호 방식이며, Ebadi는 그의 논문 Featherweight PinQ에서 PinQ 플랫폼과 상호작용하는 프로그램들은 DP 성질을 만족한다는 사실을 증명하였습니다.
2. Ektelo
또 다른 DP 인터페이스로 Ektelo를 소개하고자 합니다. 엑텔로는 비전문가들도 DP 알고리즘 개발을 쉽게 할 수 있도록 하기 위한 툴입니다. 사전에 검증된 operator 라이브러리가 제공되는데, 이러한 operator 집합을 plan이라고 합니다. plan들을 조합하여 DP 성질을 만족하는 알고리즘을 설계하는 방식이며, 라플라스 메커니즘(LM)과 같이 특정 operator들만 잘 구현되어있다면 비전문가들도 알고리즘을 쉽게 개발할 수 있다는 것이 엑텔로의 장점입니다.
Actors of DP Interfaces
아래 그림은 오픈 데이터 보관 방식에 연관된 행위자들과 DP 인터페이스와의 관계를 한 눈에 정리한 그림입니다. DP 방식을 통해 신뢰할 수 있는 수준으로 데이터를 보호할 수 있음을 알 수 있습니다.
지금까지 DP를 프로그래밍하기 위해 고려되어야 할 요소들에 대하여 알아보았습니다. 이외에도, DP 인터페이스 설계에는 다양한 이슈들이 연관되어 있습니다. DB가 multi relational인 경우에는 어떻게 할 것인지, side channel attack에 어떻게 대비할 것인지, privacy budgeting 관련 가이드는 어떻게 설정해야 하는지에 대한 문제가 대표적입니다. Privacy budgeting에 대해서는 추후에 다루고자합니다.
