존슨-린덴스트라우스 변환을 통한 프라이버시

A 당사자가 사용자에 대한 개인 정보를 수집하고, 각 사용자의 데이터가 비트 벡터로 표현된다고 가정합시다. B 당사자는 사용자 간의 거리를 추정하는 데 필요한 독점 데이터 마이닝 알고리즘을 가지고 있으며, 클러스터링 또는 최근접 이웃을 포함합니다. 우리는 A 당사자가 B가 사용자 간의 거리를 추정할 수 있도록 각 사용자에 대한 일부 정보를 게시할 수 있는지 여부를 묻습니다. 하지만 B는 사용자에 대한 어떤 개인적인 비트도 유추할 수 없도록 해야 합니다. 우리의 방법은 각 사용자의 표현을 드문 존슨-린덴스트라우스 변환을 통해 무작위의 저차원 공간으로 투사하고, 저차원 표현의 각 항목에 가우시안 노이즈를 추가하는 것입니다. 우리는 이 방법이 차별적 프라이버시를 보존함을 보여줍니다. 즉, 프라이버시가 더 많이 요구될수록 가우시안 노이즈의 분산이 커집니다. 또한, 우리는 오직 저차원, 섭동된 데이터만으로 사용자 간의 실제 거리들을 어떻게 근사할 수 있는지도 보여줍니다. 마지막으로, 무작위 응답과 같은 다른 섭동 방법을 고려하고, 스케치 기반 방법과 비교합니다. 제3자에게 사용자별 데이터를 공개하려는 목표는 거리 보존보다 더 넓지만, 이 연구는 프라이버시를 유지하면서 거리 계산이 달성 가능한 목표임을 보여줍니다.