RDifferential Privacy (2. Reidentification and Reconstruction Attacks)
본문은 James Honaker과 Salil Vadhan의 Computer Science 208: Applied Privacy for Data Science 강의의 Reidentification and Reconstruction Attacks를 요약한 글입니다.
데이터 재식별화(Data Reidentification)란 익명화 등의 방법을 통한 개인 정보 보호가 이루어져 있는 데이터에서 개인에 대한 정보를 다시 알아내는 것을 의미합니다. 이러한 형식의 공격은 다른 데이터와의 결합(Linkage)을 통해 이루어질 수 있습니다. 아래 그림의 의료 데이터는 이름이 지워진 상태로 개인에 대한 식별이 그 자체만으로는 불가능합니다. 하지만 이 데이터가 투표권자 리스트 데이터와 결합이 된다면 두 데이터에서 동시에 나타나는 우편 번호, 생년월일, 성별 정보를 활용하여 상당히 많은 사람의 이름을 알아낼 수 있다는 점이 밝혀진 바 있습니다.
위와 같은 공격에 대응하기 위해 일반화(Generalization) 방법이 제안되었습니다. 이 방법은 데이터에 대한 정확한 정보 대신 조금 더 일반적으로 표현된 정보로 데이터를 표현하는 방법입니다. 예를 들어, 어떤 사람의 나이가 34세일 때, “34세”라는 정확한 나이 대신, “30대”와 같이 조금 더 포괄적인 개념으로 정보를 나타내게 됩니다.
이러한 일반화 방법을 활용해 재식별화 공격에 대응하는 방법 중 하나가 K-익명성(K-Anonymity)입니다. 이 방법은 앞서 설명한 일반화 방법을 사용해 데이터를 표현하는 데, 이 때 일반화되어 표현되는 속성값이 동일한 레코드가 최소 k개 나타나도록 하는 일반화 방법입니다.
위의 데이터는 나이(Age)에 대해 K-익명성이 적용되었습니다. 이 때, 나이와 같이 K-익명성이 적용될 수 있는 속성을 “Quasi-Identifier”라고 합니다. 이 속성들은 외부의 데이터셋과 결합될 때 사용되는 속성들이고 이 Quasi-Identifier에 대해서만 K-익명성 모델은 적용될 수 있습니다.
해당 데이터를 살펴보면, 40세 이상의 사람이 암, 심장병, 바이러스 감염 중 어떤 병을 가지고 있는지 식별이 불가능합니다. 그룹 안에서 특정 개인의 정보를 확신할 수 없게 만드는 것이 이 방어 방법의 목적이라 할 수 있습니다. 하지만 현재 데이터에서 30대 모두 암에 걸린 상태인데, K-익명성 모델을 적용했지만 해당 그룹의 모든 사람이 암에 걸려있는 상태라 암에 걸렸다는 민감한 정보가 그대로 드러나게 됩니다. 또한 이러한 익명 처리 방식으로 인해 기존 데이터로부터 왜곡된 정보를 전달한다는 단점 역시 존재합니다. 어떤 기준을 적용해서 K-익명성 모델을 만들 것인지 결정하는 단계에서 이미 개인의 프라이버시가 침해될 수 있다는 비판 역시 존재합니다.
2008년 Netflix Challenge를 통해 공개된 익명 데이터와 IMDB의 공개 데이터를 활용한 데이터 재식별화가 가능하다는 것이 Narayanan과 Shmatikov에 의해 밝혀진 바 있습니다.
해당 연구에서는 IMDB 평점이라는 외부 정보를 활용하여 아래와 같은 score function을 설계하였습니다. Netflix 데이터의 각 레코드들에 대해 score를 계산하고, 특정 레코드의 score가 일정 수준이상 다른 레코드에 비해 높은 경우 해당 레코드에 속하는 인물을 유추하는 방식으로 알고리즘을 구성하였습니다.
이런 방식을 통해 일부 사용자의 정보를 재식별화 하는 데에 성공하였으며, 재식별화된 정보를 통한 개인 정보 유출 가능성에 대해 문제가 제기되었습니다. 주목해야 할 점은 score function에 사용된 평점의 경우 개인을 식별할 수 있는 Quasi-identifier가 아니라는 점입니다. 이런 식별자가 없이도 개인 정보에 대한 공격이 일어날 수 있음을 알려준 사례라고 볼 수 있습니다.
개인 정보에 대한 공격은 통계량을 활용해서도 이루어질 수 있습니다. Bit 형식으로 표현된 민감 데이터(Sensitive bit)에 대해 Query를 활용하여 데이터 중 일부 집합에서의 민감 데이터 합에 대한 정보만 알 수 있는 경우에도 공격이 가능합니다. Ziv (2013)에 따르면 이스라엘의 인구조사 데이터에서 이러한 방식의 공격을 통한 개인 정보 유출이 가능했다고 합니다.
만약, 공격자가 데이터 중 일부 집합을 선택하는 방식이 아니라 임의로 선정된 부분 집합에 대해서 통계량을 얻는 경우는 어떨까요? 이 경우에서 역시 데이터의 개수(n)만큼 통계량(Sensitive bit의 합)을 알 수 있다면 1-𝑜(1)의 확률로 공격자는 전체 데이터를 재구성(Reconstruct)할 수 있습니다.
정확한 통계량이 주어지지 않고 약간의 노이즈가 섞인 경우에도 역시 데이터의 재구성은 가능하게 됩니다. Dinur-Nissim (2003)에 따르면 데이터의 개수만큼 임의의 부분 집합 S들에 대해 Query에 대한 답을 확인할 때 실제 결과(a)와의 차이로 나타나는 노이즈가 모두 아래의 조건을 만족할 경우, 높은 확률로 전체 데이터의 대부분을 재구성할 수 있습니다.
즉, 노이즈가 포함된 통계량이어도 어느 정도의 정확도를 가진 통계량을 어느 수준 이상으로 공개하게 되면 전체 데이터에 대한 재구성이 가능해지게 됩니다. 다만 여기서의 정확도, 그리고 공개되는 데이터의 양 등은 모두 결정해야 할 요소입니다. 따라서 어느 정도의 공개가 얼만큼 이루어져야 하는지 정량적으로 파악할 수 있는 방법에 대한 필요성이 대두되었습니다. 그에 대한 답을 줄 수 있는 방법 중 하나가 바로 차등 정보 보호 기법(Differential Privacy)입니다.
