김종욱
(Jong Wook Kim)
†iD
Copyright © The Korea Institute for Structural Maintenance and Inspection
Key words
Data Privacy, Differential Privacy, Data Utility, Computation Overhead, Data Collection
1. 서 론
오늘날 대부분의 사람들이 스마트폰과 같은 모바일 기기를 일상적으로 사용함에 따라, 다양한 데이터가 실시간으로 수집되고 있다. 이러한 기술 발전은
교통, 헬스케어, 스마트 시티와 같은 여러 분야에서 사용자 기반 의사 결정 시스템을 가능하게 하고 있다[1,2,3]. 예를 들어, 전자지도 서비스는 사용자로부터 수집한 도로 혼잡도와 같은 실시간 데이터를 바탕으로 교통 상황을 분석하고 최적의 경로를 제시하는 의사
결정을 내린다. 헬스케어 분야에서도 웨어러블 기기를 통해 사용자의 건강 상태를 모니터링하고, 이를 바탕으로 개인 맞춤형 건강 관리 서비스를 제공하는
시스템이 있다. 이처럼 다양한 응용 프로그램은 실시간으로 수집된 데이터를 분석하여 사용자에게 보다 효과적인 서비스를 제공하고 있다.
응용 프로그램에 따라 수집된 데이터의 유용성 요구 사항은 각기 다르다. 일부 응용 프로그램은 데이터가 완전하지 않더라도 여전히 중요한 통찰력을 제공할
수 있는 데이터를 필요로 한다. 예를 들어, PoI(Point of Interest) 방문 데이터를 활용하는 경우, 특정 관심 지점에 대한 방문 데이터가
일부 누락되더라도 다른 여러 위치에서 충분한 방문 데이터가 수집되면, 이를 통해 전체적인 트렌드와 패턴을 분석하는 것이 가능하다. 이러한 유연성은
특히 실시간 분석이 필요한 응용 프로그램에서 변화하는 상황을 빠르게 인식하고 적절히 대응할 수 있도록 하는 핵심 요소이다.
사용자로부터의 데이터 수집이 확산됨에 따라 개인 정보 보호에 대한 우려가 제기되고 있다. 특히, 수집된 데이터에 민감한 정보가 포함된 경우, 적절한
보호 조치가 이루어지지 않으면 사용자의 프라이버시가 침해될 가능성이 크다. 이러한 문제를 해결하기 위한 대표적인 방법으로 차분 프라이버시(DP, Differential
Privacy)[4]가 널리 사용되고 있다. DP는 데이터 변조를 통해 원본 데이터를 보호하는 프라이버시 기법으로, 현재 다양한 분야에서 활용되고 있다.
DP를 이용한 데이터 수집 기법 중 대표적인 방법으로 지역 차분프라이버시(Local Differential Privacy, LDP)[5]와 분산 차분프라이버시(Distributed Differential Privacy, DDP)[6]가 있다. 두 기법 모두 사용자가 데이터를 중앙 서버(central server)에 전송하기 전에 로컬 환경에서 노이즈를 추가하여 프라이버시를 보호하는
방식이다. LDP는 상대적으로 낮은 계산 부하를 가지는 장점이 있지만, 데이터 변조가 심하게 발생하며, 이로인해 수집된 데이터의 유용성이 저하되는
문제가 있다. 그러므로 LDP는 높은 분석 정확도를 요구하는 분야보다는 개인의 민감한 정보를 보호하면서도 대규모 데이터의 전반적인 경향을 파악하는
데 중점을 두는 분야에 적합하다. 반면, DDP는 수집된 데이터의 유용성은 높으나, 계산 부하가 크게 증가하는 단점이 있다.
그림 1. 제안 기법인 ($\theta$,$\lambda$)-데이터 수집 개요
Fig. 1. Overview of the proposed ($\theta$,$\lambda$) data collection
그림 1은 본 연구의 동기를 설명하는 예시를 보여준다. LDP와 DDP를 사용하면 전체 항목에 대한 데이터를 수집할 수 있다. 그러나 LDP는 수집된 데이터의
유용성이 낮아 효과적인 분석이 어려울 수 있다. 반면, DDP는 계산 부하가 커서 실시간 분석이 어려워지는 문제가 발생한다. 이를 해결하기 위해,
본 논문에서는 DP를 만족하는 ($\theta$,$\lambda$)-데이터 수집 기법을 제안한다. 본 논문의 제안 기법인 ($\theta$,$\lambda$)-데이터
수집 기법은 전체 데이터 중 적어도 $\theta$ 비율의 항목을 수집하고, 각 항목에 대해 전체 사용자 중 최소 $\lambda$ 비율의 사용자로부터
데이터를 확보하도록 설계되었다. 제안기법은 LDP에 비해 데이터 유용성을 높이고 DDP에 비해 계산 부하를 줄일 수 있는 기법이다. 이를 통해 수집한
데이터의 유용성과 계산 효율성 간의 균형을 달성할 수 있다.
본 논문은 다음과 같이 구성되어 있다. 2장에서는 본 논문과 관련된 선행 연구에 대해서 설명한다. 3장에서는 배경 지식에 대하여 설명한다. 4장에서는
제안기법에 대하여 설명한다. 5장에서는 제안기법의 성능 평가를 수행한 후, 6장에서 결론을 맺는다.
2. 관련연구
DP는 다양한 분야에서 민감한 데이터의 프라이버시를 보존하기 위한 방법으로 사용되고 있다. LDPTrace[5]는 LDP를 이용해 사용자들의 경로 정보를 보호하면서 합성 경로를 생성하는 방법을 제안하였다. LDPTrace는 합성 경로 생성을 위해 사용자 경로의
시작 및 종료 위치, 그리고 이동 패턴을 LDP를 통해 수집한다. Chen et al.은 DP를 사용하여 프라이버시를 보존하면서 민감한 사용자 경로
데이터를 안전하게 배포하는 방안을 제시하였다[7]. 또한, Kim et al.은 DP를 이용해 웨어러블 기기에서 사용자의 건강 정보를 수집하는 방법을 제안하였다[3]. 제안 기법은 건강 데이터로부터 특이점을 추출한 후, 전체 데이터를 전송하는 대신 특이점 데이터를 LDP를 이용하여 수집하고 이를 서버에서 복원하는
방식을 사용한다. Shaham et al.은 DP를 활용하여 출발-도착 행렬(origin-destination matrix)을 프라이버시를 보장하면서
배포하는 기법을 제안하였다[8]. 배포된 출발-도착 행렬은 빈번한 이동 패턴을 분석하는 데 활용된다. Chen et al.은 DP를 활용하여, COVID-19 환자의 위치 정보를
보호하면서 COVID-19 발병 지도를 생성하였다[9]. Wang et al.은 모바일 크라우드소싱 환경에서 작업자의 위치 프라이버시를 보호하기 위한 방법을 제안하였다[10]. 제안 기법은 DP를 적용해 작업자의 위치 정보를 안전하게 수집하고, 이를 바탕으로 모바일 크라우드소싱에서 작업자 분포를 추정하는 데 활용하였다.
Q. Geng et al.은 DP의 데이터 변조 과정에서 발생하는 노이즈를 줄이기 위한 방법을 제안하였다[11]. 이 기법은 노이즈를 여러 구간으로 나눈 계단 모양의 확률 분포를 따르며, 구간 내에서 특정 값들이 더 높은 확률로 선택되는 방식이다. DP를 위치
데이터에 적용하기 위한 기술도 활발히 연구되어 왔다. 가장 대표적인 기법인 geo-indistinguishability는 노이즈를 추가해 사용자의
위치를 모호하게 변조함으로써 위치 정보의 프라이버시를 보호하는 기법이다[12,13]. 최근 들어 DP의 변형인 셔플 모델(shuffled model)에 대한 연구가 활발히 진행되고 있다[14,15]. 셔플 모델에서는 각 사용자가 로컬 환경에서 데이터를 처리한 후, 이를 무작위로 셔플하여 서버에 전송함으로써, 중앙 서버가 개별 사용자의 데이터를
식별할 수 없도록 설계되었다. Rényi DP는 기존 DP의 확장된 개념으로, Rényi 다이버전스를 사용해 프라이버시 손실을 더 세밀하게 측정하며,
특히 반복적인 프라이버시 메커니즘에서 유용하게 적용되는 기법이다[16].
3. 배경지식
DP는 데이터 수집 및 처리 과정에서 개인의 민감한 정보를 보호하기 위한 수학적 프레임워크이다.
정의 1. (($\epsilon$,$\delta$)-DP) 임의의 두 인접한 데이터셋 $D_{1}$과 $D_{2}$에 대해, 임의의 결과 집합 $S$에
대해 임의의 함수 $M$이 다음 조건을 만족하면 $M$은 ($\epsilon$,$\delta$)-DP를 만족한다.
여기서, $\epsilon$는 프라이버시 예산(privacy budget)을 나타내며, $\epsilon$ 값이 작을수록 더 강한 프라이버시 보호를
의미한다. $\delta$는 프라이버시 보장
이 실패할 확률을 나타내며, 보통 매우 작은 값으로 설정한다. 또한, 두 인접한 데이터셋 $D_{1}$와 $D_{2}$는 단 하나의 데이터 항목만
다른 데이터셋을 의미한다. DP는 이러한 두 데이터셋에 대해 분석 결과가 거의 동일하도록 보장하여, 개별 항목이 데이터셋에 포함되었는지 여부를 추론하기
어렵게 한다.
($\epsilon$,$\delta$)-DP를 달성하기 위한 대표적인 방법으로 가우시안 기법(Gaussian Mechanism)이 있다.
정의 2. (가우시안 기법) 임의의 함수 $M$에 대해 가우시안 기법 $A$는 ($\epsilon$,$\delta$)-DP를 만족하는 다음 결과를
생성한다.
여기서, $N(0,\: \sigma^{2})$는 평균이 0이고 표준 편차가 $\sigma =\dfrac{\triangle M\bullet\sqrt{2\ln(1.25/\delta)})}{\epsilon}$인
가우시안 분포에서 추출한 노이즈를 의미한다. 또한 $\triangle M$은 함수 $M$의 민감도를 나타내며, 두 인접한 데이터셋 $D_{1}$과
$D_{2}$에서 질의 결과 $M(D_{1})$과 $M(D_{2})$의 최대 차이를 의미한다.
4. 제안기법
4.1 문제 정의 및 기본 기법
본 절에서는 본 연구에서 다루는 문제를 정의한다. 사용자 집합을 $U$ = {$u_{1},\: u_{2},\: ....,\: u_{n}$}로,
항목(Item)의 집합을
$I$ = {$i_{1},\: i_{2},\: ....,\: i_{m}$}로 가정하자. 또한 $D_{t}$ = {$(i_{k},\: f_{t,\:
k})｜ k=1,\: 2,\: ...,\: m$}를 사용자 $u_{t}$의 데이터 집합이라 가정하자. 이때, $f_{t,\: k}$는 아이템 $i_{k}$의
값(value)을 나타낸다. 예를 들어, 항목 $I$가 PoI의 집합인 경우, $i_{k}$는 특정 PoI를, $f_{t,\: k}$는 해당 PoI의
방문 횟수를 의미한다. 일반적으로 항목의 수가 많으므로, 데이터 집합에서 많은 경우 값은 0에 해당한다.
서비스 제공자(즉, 중앙 서버)는 사용자들로부터 항목과 값을 수집한다. 본 연구에서는 항목의 값이 사용자의 민감한 데이터(sensitive data)에
해당한다고 가정한다. 그러므로 중앙 서버는 다음과 같은 집계 결과를 DP를 적용하여 사용자 프라이버시를 보호하면서 수집한다.
3장에서 설명한 DP는 중앙 모형(centralized model)에 해당한다. 이 기법은 중앙 서버를 신뢰할 수 있다는 가정하에 적용되며, 주로
데이터 배포 시 활용된다. 그러나 일반적으로 데이터 수집은 중앙 서버를 신뢰할 수 없는 상황에 해당한다. 그러므로, 사용자는 DP 조건을 만족하도록
자신의 데이터를 변조한 후, 원본 데이터 대신 변조된 데이터를 중앙 서버에 전송한다. 이때 사용되는 대표적인 기법이 LDP와 DDP이다.
그림 2. LDP 기반 방식의 의사코드
Fig. 2. Pseudocode for LDP-based Approach
그림 3. DDP 기반 방식의 의사코드
Fig. 3. Pseudocode for DDP-based Approach
그림 2와 3은 각각 LDP와 DDP 기법을 이용한 집계 결과 계산을 위한 사용자 처리 과정을 나타낸다. LDP 기법과 DDP 기법의 가장 큰 차이점은 LDP는
개별 데이터(즉, $f_{t,\: k}$)에 ($\epsilon$,$\delta$)-DP를 만족하도록 노이즈를 추가하지만, DDP는 집계 결과(즉,
$\sum_{i=1}^{n}f_{i,\: k}$)에 ($\epsilon$,$\delta$)-DP를 만족하도록 노이즈를 추가한다는 점이다. 최악의 경우,
LDP에서는 집계 결과가 $\sum_{i=1}^{n}(f_{i,\: k}+N(0,\: \sigma^{2}))=\sum_{i=1}^{n}f_{i,\:
k}+n N(0,\: \sigma^{2})$가 되지만, DDP의 경우 집계 결과는 $\sum_{i=1}^{n}(f_{i,\: k}+N(0,\: \sigma^{2}/n))=\sum_{i=1}^{n}f_{i,\:
k}+N(0,\: \sigma^{2})$가 된다. 그러므로 데이터 유용성 측면에서는 DDP가 LDP보다 우수하다.
그러나 DDP의 경우, 사용자가 개별적으로 추가하는 노이즈는 개별 데이터 $f_{t,\: k}$에 대해 ($\epsilon$,$\delta$)-DP를
만족하지 못 하므로, 중앙 서버는 개별 데이터가 아닌 집계 결과에만 접근할 수 있어야 한다. 이를 구현하기 위해 DDP는 SMC(secure multiparty
computation)를 필수적으로 요구한다. 하지만 SMC는 일반적으로 계산 부하가 높아, 수집하는 데이터 항목이 많을 경우 비효율적일 수 있다.
LDP와 달리 DDP에서는 개별 사용자가 더하는 노이즈의 합이 ($\epsilon$,$\delta$)-DP를 만족해야 하므로, 모든 사용자가 각 데이터
항목마다 노이즈를 추가해야 한다. 이로 인해 중앙 서버로 전송되는 항목 수가 증가하고, 결과적으로 SMC의 계산 부하가 커지는 단점이 있다.
4.2 ($\theta$,$\lambda$)-데이터 수집 기법
본 연구에서는 서비스 제공자는 데이터 수집을 통해 전체적인 트렌드와 패턴 분석을 목적으로 한다고 가정한다. 이를 위해, 두 개의 변수 $\theta$와
$\lambda$를 통해 데이터 수집의 정확성과 계산 부하를 제어한다.
정의 3. (($\theta$,$\lambda$)-데이터 수집)
$\theta$는 전체 $m$개의 항목으로 구성된 항목 집합 $I$ = {$i_{1},\: ....,\: i_{m}$} 중에서 적어도 $\theta
m$개의 항목을 수집해야 한다는 것을 의미한다. $\lambda$는 각 항목에 대해 $n$명의 사용자로 구성된 사용자 집합 $U$ = {$u_{1},\:
....,\: u_{n}$} 중에서 적어도 $\lambda n$명의 사용자로부터 데이터를 수집해야 하는 최소 사용자 수를 의미한다.
즉, 본 연구의 목표는 전체 항목 중 적어도 $\theta m$개의 항목을 수집하는 동시에, 수집된 각 항목에 대해 적어도 $\lambda n$명의
사용자로부터 데이터를 확보하는 것이다. 이를 본 논문에서는 ($\theta$,$\lambda$)-데이터 수집이라 정의한다. 여기서 $\theta$와
$\lambda$는 0과 1 사이의 값이다.
($\theta$,$\lambda$)-데이터 수집은 4.1절에서 설명한 LDP와 DDP 기법과 달리, 데이터 수집 목적에 맞춰 데이터 유용성과 계산
부하를 조절할 수 있는 방식이다. 먼저, $\lambda n$명의 사용자로부터 데이터를 수집하는 조건을 통해, 각 사용자는 $N(0,\: \dfrac{\sigma^{2}}{\lambda
n})$에서 추출한 노이즈를 추가하여 집계 결과에 대해 ($\epsilon$,$\delta$)-DP를 만족시킬 수 있다. 이는 LDP 기법에서 각
사용자가 추가하는 노이즈(즉, $N(0,\: \sigma^{2})$에 추출한 노이즈)보다 작으며, 변수 $\lambda$를 통해 각 사용자가 추가하는
노이즈의 양을 조절할 수 있다. $\lambda$가 1인 경우 DDP와 같은 데이터 유용성을 유지할 수 있다.
또한, DDP 기법에서는 각 사용자가 $m$개의 항목 데이터를 SMC를 적용한 후 서버에 전송해야 한다. 반면, ($\theta$,$\lambda$)-데이터
수집 기법은 변수 $\theta$와 $\lambda$를 통해 서버에 전송해야 하는 데이터 양을 조절할 수 있어, SMC 사용으로 인한 계산 부하를
줄일 수 있다.
4.2.1 항목 수에 대한 최소 한계 계산
그림 2의 LDP 기법에서처럼 단순히 값이 0보다 큰 항목들만을 서버에 전송할 경우, $\lambda n$명의 사용자로부터 데이터를 수집한다는 조건을 충족하지
못해 집계 데이터에 대한 ($\epsilon$,$\delta$)-DP를 만족할 수 없으며, SMC를 통해 집계 결과에 접근할 수 없게 된다. 따라서,
본 절에서는 ($\theta$,$\lambda$)-데이터 수집을 만족하기 위해 각 사용자가 서버에 전송해야 하는 항목 수에 대한 최소 한계 $\alpha$를
구하는 방법을 제안한다.
각 사용자가 총 $m$개의 항목 중에서 무작위로 $\alpha$개의 항목을 선택한다고 가정하면, 사용자가 특정 항목 $i_{t}$를 선택할 확률 $p_{t}$는
다음과 같다.
$X$를 항목 $i_{t}$를 선택하는 사용자 수를 나타내는 확률 변수라고 하자. 각 사용자의 선택은 독립적이므로, $X$는 이항 분포 $X\sim$Binomial($m$,$p_{t}$)를
따른다. 이때, 적어도 $\lambda n$명의 사용자가 항목 $i_{t}$를 선택할 확률은 $Pr(X\ge\lambda n)$으로 표현된다. 또한,
전체 항목 중 적어도 $\theta m$개의 항목을 수집해야 하므로, $\theta$를 신뢰도(confidence)로 간주하면, 다음을 만족하는 최소
$\alpha$를 찾아야 한다.
식 (5)를 이항 분포의 누적 분포 함수(cumulative distribution function)로 표현하면 다음과 같다.
그러므로 식 (6)에 의해 $(\lambda n-1)$명 이하의 사용자가 항목 $i_{t}$를 선택할 확률은 다음과 같이 누적 확률로 표현된다.
따라서, 식 (7)을 만족하는 $\alpha$의 최소값이 각 사용자가 서버에 전송해야 하는 항목 수에 대한 최소 한계를 의미한다. 식 (7)은 이항 분포를 포함하고 있어 닫힌식(closed-form expression)을 구하는 것이 복잡하므로, 그림 4와 같이 반복 기법을 통해 구할 수 있다. 특히, 그림 4에서는 효율적인 계산을 위해 이진 탐색 알고리즘을 사용하여 식 (7)을 만족하는 $\alpha$의 최소값을 구한다.
그림 4. $\alpha$를 구하는 의사코드
Fig. 4. Pseudocode for computing $\alpha$
그림 4의 알고리즘을 통해 구한 $\alpha$는 모든 사용자에게 배포되어, 각 사용자가 선택할 항목의 수를 결정하는 데 사용된다. 이를 통해 ($\theta$,$\lambda$)-데이터
수집 조건을 충족하면서, 각 사용자가 전송해야 하는 항목 수를 최소화할 수 있다.
4.2.2 ($\theta$,$\lambda$)-데이터 수집 알고리즘
그림 5는 중앙 서버로부터 받은 $\alpha$ 값을 이용한 ($\theta$,$\lambda$)-데이터 수집을 위한 사용자 처리 과정의 의사코드이다. 먼저,
값이 0보다 큰 항목에 대해 $N(0,\: \dfrac{\sigma^{2}}{\lambda n})$에서 추출한 노이즈를 추가하여 결과 집합 $R_{t}$에
저장한다 (3-7줄). 그런 다음, 선택한 항목의 수가 $\alpha$보다 작을 경우, 값이 0인 항목을 임의로 추출하여 노이즈를 추가한 후 $R_{t}$에
추가한다 (8-11줄). 마지막으로, 12~13줄에서는 $R_{t}$를 SMC를 이용해 암호화한 후 중앙 서버에 전송한다. 특히, 5줄과 10줄에서
확인할 수 있듯이, $\lambda$가 증가할수록 가우시안 기법에 의해 원본 데이터에 추가되는 노이즈의 크기가 감소한다. 따라서, $\lambda$를
조정함으로써 수집된 데이터의 유용성을 효과적으로 제어할 수 있다.
중앙 서버는 모든 사용자와 협력하여 복호화를 진행한다. 이때, $\lambda n$ 이상의 사용자로부터 수집된 항목은 복호화가 가능하다. 하지만,
$\lambda n$ 미만의 사용자로부터 수집된 항목은 복호화가 불가능하며, 해당 항목은 데이터 수집에서 누락된다.
그림 5. 제안 기법인 ($\theta$,$\lambda$)-데이터 수집 의사코드
Fig. 5. Pseudocode for the proposed ($\theta$,$\lambda$)-data collection
4.2.3 변수 와 의 영향 분석
변수 $\theta$와 $\lambda$는 수집한 데이터의 유용성과 데이터 수집 과정에서 발생하는 계산 부하에 영향을 미친다. 먼저, 데이터 유용성과
관련하여 그림 5의 알고리즘에서 각각의 사용자는 원본 값에 $N(0,\: \dfrac{\sigma^{2}}{\lambda n})$에서 추출한 노이즈를 추가한다. 따라서,
$\lambda$가 증가할수록 추가되는 노이즈의 크기가 작아져 데이터 유용성이 향상될 수 있다. 반면, $\theta$는 데이터 수집에서 누락되는
항목의 수를 조절하는 역할을 한다. $\theta$가 증가하면 누락된 항목의 수가 줄어들어 더 정확한 데이터 분석이 가능해진다.
그러나 $\theta$와 $\lambda$가 증가하면, 식 (7)에 의해 각 사용자가 서버에 전송해야 하는 항목 수가 증가하게 된다. 최근 SMC 분야에서 많은 발전이 이루어지고 있다. [17]은 최초로 확장 가능한 SMC 기법을 제안하였으며, 이 기법의 통신 비용과 계산 부하는 각각 $O(n+\alpha)$와 $O(n^{2}+\alpha\bullet
n)$로 표현된다. 또한, [18]에서는 통신 비용과 계산 부하가 각각 $O(\log^{2}n+\alpha)$와 $O(\log^{2}n+\alpha\bullet\log n)$에 해당하는
효율적인 SMC 기법을 제안하였다. 이러한 최신 SMC 기법에서는 사용자 수가 고정된 경우, $\alpha$에 비례하여 계산 부하가 선형적으로 증가하므로,
전송할 항목 수가 많아질수록 통신과 계산 부하가 증가한다. 따라서, $\theta$와 $\lambda$는 데이터 분석의 목적에 맞게 조정되어야 하며,
과부하와 데이터 유용성 사이의 균형을 유지해야 한다.
특히, 제안 기법을 실시간 시스템에 적용하기 위해서는 최신 SMC 기법을 활용하여 SMC 사용으로 인한 통신 및 계산 부하를 줄이는 것이 필수적이다.
그러나 앞서 설명한 바와 같이, SMC 사용으로 인한 과부하는 $n$과 $\alpha$에 비례하여 증가한다. 따라서, 모든 사용자에 대해 제안 기법을
일괄적으로 적용하기보다는, 사용자 그룹을 나누거나 데이터의 중요도에 따라 우선순위를 설정하여 선택적으로 기법을 적용하는 방안을 고려해야 한다.
5. 성능 평가
5.1 실험 환경
본 연구에서는 실데이터를 이용하여 제안 기법의 성능을 평가하였다. 실험에 사용한 데이터는 T-Drive 데이터셋[19]으로, 베이징 시내에서 10,357대의 택시 주행 기록을 포함하고 있다. 실험을 위해 전체 지역을 10,000개의 구역으로 나누고, 각 택시의 위치를
해당 구역에 매핑하였다. 이후 방문 빈도가 높은 상위 1,000개의 구역을 추출하여 이를 PoI 항목으로 설정하고, 각 구역의 방문 횟수를 값으로
사용하였다. 실험에서 전체 사용자 수는 1,000명에서 3,000명까지 변화시켰으며, 이를 위해 전체 데이터를 균등하게 사용자 수($n$)로 나누어
각 사용자의 데이터 셋을 생성하였다.
실험에서는 비교 평가를 위해 평균 절대 오차(Mean Absolute Error, MAE)와 Jensen–Shannon 발산(Jensen–Shannon
Divergence, JSD)를 사용하였다. MAE는 다음과 같이 정의된다.
이때, $af_{k}$는 식 (3)을 기반으로 계산한 실제 집계 결과를, $af'_{k}$는 DP를 적용하여 도출된 집계 결과를 의미한다. 또한, JDS는 다음과 같이 정의된다.
여기서, $D_{KL}$은 Kullback–Leibler 발산을 나타낸다. 또한, $D(P)$는 실제 집계 항목 값의 확률 분포를 의미하며, $D(P')$는
DP를 적용하여 구한 집계 항목 값을 나타낸다.
5.2 실험 결과
그림 6은 $\lambda$ 값을 0.05에서 0.3으로 변화시켰을 때의 MAE와 JSD 결과를 보여준다. 실험에서는 프라이버시 예산($\epsilon$)을
0.25에서 1.0까지 변화시켰고, $\theta$ 값은 0.9로 고정하였다. 또한, 사용자 수($n$)는 1,000명으로 설정하였다. 그림에서 알
수 있듯이, $\epsilon$ 값이 감소할수록 MAE와 JSD 값도 함께 감소하는 경향을 보인다. 이는 $\epsilon$ 값이 감소할수록 데이터에
추가되는 노이즈의 양이 증가하여 프라이버시 보호 수준이 높아지기 때문이다. 이러한 현상은 DP 기반 알고리즘에서 공통적으로 나타나는 특성이다.
그림 6에서 제안 기법(Prop)은 $\lambda$ 값이 증가할수록 MAE와 JSD 값이 감소하는 것을 확인할 수 있다. 특히, $\epsilon$ 값이
0.25인 경우, $\lambda$ 값이 0.05에서 0.3으로 증가함에 따라 MAE는 215에서 124로 감소하였으며, JSD는 0.121에서 0.067로
줄어드는 양상을 보였다. 이는 제안 기법이 $N(0,\: \dfrac{\sigma^{2}}{\lambda n})$에서 추출한 노이즈를 원본 데이터에
추가하는 방식이므로, $\lambda$ 값이 증가함에 따라 추가되는 노이즈가 줄어들기 때문이다. 또한, LDP와 비교했을 때, 제안 기법은 데이터
유용성이 현저히 높다는 점을 확인할 수 있다.
그림 6. $\lambda$값의 변화에 따른 MAE와 JSD의 비교
Fig. 6. Comparison of MAE and JSD when varying $\lambda$
그림 7은 $\theta$ 값을 0.6에서 0.99로 변화시켰을 때의 MAE와 JSD 결과를 보여준다. 실험에서는 $\epsilon$ 값을 0.25에서 1.0까지
변화시켰고, $\lambda$ 값은 0.2로 고정하였다. 또한, 사용자 수($n$)는 1,000명으로 설정하였다. 그림에서 확인할 수 있듯이, 본
논문의 제안 기법이 LDP 기법에 비해 MAE와 JSD 측면에서 더 우수한 성능을 보인다.
그림 7. $\theta$값의 변화에 따른 MAE와 JSD의 비교
Fig. 7. Comparison of MAE and JSD when varying $\theta$
그림 7의 실험 결과를 통해 $\theta$ 값의 변화가 MAE와 JSD 값에 큰 영향을 미치지 않는다는 것을 알 수 있다. 이는 수집된 데이터 항목만을
사용하여 MAE와 JSD를 계산하였기 때문이다. 또한, 원본 데이터에 추가되는 노이즈는 $\theta$ 값에 영향을 받지 않기 때문이다. 그러나 $\theta$
값은 수집된 데이터 항목의 수에 영향을 미친다. 이는 표 1에서 확인할 수 있다. 표 1은 그림 7의 실험 결과에서 실제로 수집된 항목의 개수를 보여준다. 표 1에서 괄호 안의 숫자는 $\theta$ 값 설정에 따라 요구되는 실제 수집해야 하는 항목의 개수를 나타낸다. 표에서 알 수 있듯이, 제안 기법은 요구된
최소 항목 수 이상을 효과적으로 수집할 수 있음을 보여준다. 이는 4.2.1절의 제안 기법이 항목 수에 대한 최소 한계를 효과적으로 계산함을 입증한다.
또한, $\theta$ 값이 증가할수록 수집한 항목 수도 증가함을 알 수 있다.
표 1 $\theta$ 값의 변화에 따른 수집된 항목의 수
Table 1 The number of collected items for varying $\theta$
|
$\theta$
|
0.6
|
0.7
|
0.8
|
0.9
|
0.99
|
|
Num. of Collected Items
|
607
(600)
|
713
(700)
|
809
(800)
|
905
(900)
|
992
(990)
|
표 2는 $\theta$, $\lambda$, $n$ 값의 변화에 따른 항목 수에 대한 최소 한계($\alpha$)의 변화를 보여준다. 표 2에서 확인할 수 있듯이, 4.2.3절에서 논의한 바와 같이 $\theta$와 $\lambda$가 증가할수록 $\alpha$ 값도 함께 증가하는 경향을
보인다. 예를 들어, $n$이 1000이고 $\lambda$가 0.1로 고정된 경우, $\theta$가 0.6에서 0.99로 증가함에 따라 $\alpha$는
103에서 124로 증가하였다. 또한, $n$이 1000이고 $\theta$가 0.6으로 고정된 경우, $\lambda$가 0.1에서 0.3으로 증가하면
$\alpha$는 103에서 304로 증가하는 것을 확인할 수 있다.
DDP를 적용했을 때 서버로 전송해야 하는 항목 수와 비교해 보면, 본 논문의 제안 기법이 서버로 전송해야 하는 항목 수를 크게 줄일 수 있음을 알
수 있다. 특히 사용자 수($n$)가 증가할수록, DDP 기법과 비교하여 제안 기법은 서버로 전송해야 하는 항목 수를 크게 감소시킬 수 있으며, 이를
통해 SMC 사용으로 발생하는 과부하를 크게 줄일 수 있다.
표 2 $\theta$, $\lambda$, $\theta$ 값의 변화에 따른 $\alpha$ 값의 변화
Table 2 The values $\alpha$ for varying $\theta$, $\lambda$, and $n$
|
|
$\theta$
$\lambda$
|
0.6
|
0.7
|
0.8
|
0.9
|
0.99
|
DDP
|
|
n=
1000
|
0.1
|
103
|
105
|
108
|
113
|
124
|
1000
|
|
0.2
|
203
|
207
|
211
|
217
|
231
|
|
0.3
|
304
|
308
|
312
|
319
|
334
|
|
n=
2000
|
0.1
|
102
|
104
|
106
|
109
|
117
|
2000
|
|
0.2
|
203
|
205
|
208
|
212
|
222
|
|
0.3
|
303
|
306
|
309
|
314
|
324
|
|
n=
3000
|
0.1
|
102
|
103
|
105
|
108
|
114
|
3000
|
|
0.2
|
202
|
204
|
207
|
210
|
218
|
|
0.3
|
302
|
305
|
307
|
311
|
320
|
본 장의 실험 결과를 통해 제안 기법인 ($\theta$,$\lambda$)-데이터 수집은 LDP보다 데이터 유용성을 높이면서도, DDP보다 계산
부하를 효과적으로 줄일 수 있음을 입증하였다. 특히, 변수 $\theta$와 $\lambda$를 통해 계산 부하와 데이터 유용성을 유연하게 조절할
수 있어, 실제 데이터 수집 및 분석 목적에 맞게 기법을 효과적으로 적용할 수 있다. 이를 통해 다양한 응용 분야에서 요구되는 프라이버시 보호와 데이터
유용성 및 계산 부하 간의 균형을 보다 효율적으로 달성할 수 있다.
6. 결 론
본 연구에서는 실시간으로 수집되는 데이터를 효과적으로 분석하기 위해 DP를 적용한 새로운 데이터 수집 기법을 제안하였다. 기존 LDP와 DDP의 단점을
보완한 제안 기법인 ($\theta$,$\lambda$)-데이터 수집은 데이터 유용성을 유지하면서도 계산 부하를 효과적으로 줄일 수 있는 방법이다.
특히, $\theta$와 $\lambda$ 값을 조정하여 데이터 수집 과정에서 계산 부하와 데이터 유용성을 유연하게 조절할 수 있음을 실험을 통해
확인하였다. 이를 통해 본 연구는 실시간 데이터 분석과 프라이버시 보호가 요구되는 다양한 응용 분야에서 활용 가능할 것으로 기대된다.
향후 연구에서는 제안 기법의 실시간 시스템 적용을 위한 구체적인 방안을 연구할 계획이다. 특히, 실시간 응용프로그램 환경에서 변수 $\theta$와
$\lambda$의 최적 값을 동적으로 조정할 수 있는 적응형 알고리즘을 개발하여, 실시간 응답 속도와 데이터 유용성 간의 균형을 최적화하는 방안을
모색할 것이다. 또한, 향후 연구에서는 다양한 데이터셋을 활용하여 제안 기법의 성능과 효율성을 종합적으로 검증할 예정이다. 특히, 여러 도메인에서
제안 기법의 성능을 평가함으로써, 실제 응용 분야에서의 적용 가능성과 일반화 가능성을 확인할 계획이다.
Acknowledgements
This research was funded by a 2023 Research Grant from Sangmyung University. (2023-A000-0120)
References
K. N. S. Behara et al., “A DBSCAN-based framework to mine travel patterns from origin-destination
matrices: Proof-of-concept on proxy static OD from Brisbane,” Transportation Research
Part C: Emerging Technologies, vol. 131, 2021.
J. S. Jia et al., “Population flow drives spatio-temporal distribution of COVID-19
in China,” Nature, vol. 582, pp. 389–394, 2020.
J. W. Kim et al., “Collecting health lifelog data from smartwatch users in a privacy-preserving
manner,” IEEE Transactions on Consumer Electronics, vol. 65, pp. 369–378, 2019.
C. Dwork, “Differential privacy,” Proceedings of International Colloquium on Automata,
Languages, and Programming, pp. 1–12, 2006.
Y. Du et al., “LDPTrace: Locally differentially private trajectory synthesis,” Proceedings
of the VLDB Endowment, pp. 1897-1909, 2023.
S. Goryczka, and L. Xiong, “A comprehensive comparison of multiparty secure additions
with differential privacy,” IEEE Transactions on Dependable and Secure Computing,
vol. 14, pp. 463-477, 2015.
S. Chen et al., “RNNDP: A new differential privacy scheme based on recurrent neural
network for dynamic trajectory privacy protection,” Journal of Network and Computer
Applications, vol. 168, 2020.
S. Shaham et al., “Differentially-private publication of origin-destination matrices
with intermediate stops,” Proceedings of International Conference on Extending Database
Technology, pp. 131–142, 2022.
R. Chen et al., “Constructing mobile crowdsourced COVID-19 vulnerability map with
geo-indistinguishability,” IEEE Internet of Things Journal, vol. 9, pp. 17403-17416,
2022.
J. Wang et al., “Location protection method for mobile rowd sensing based on local
differential privacy reference,” Peer-to-Peer Networking and Applications, vol. 12,
2019.
Q. Geng et al., “The staircase mechanism in differential privacy,” IEEE Journal of
Selected Topics in Signal Processing, vol. 9, pp. 1176–1184, 2015.
N. E. Bordenabe et al., “Optimal geo-indistinguishable mechanisms for location privacy,”
Proceedings of the ACM SIGSAC Conference on Computer and Communications Security,
pp. 251-262, 2014.
R. Ahuja et al., “A utility-preserving and scalable technique for protecting location
data with geoindistinguishability,” Proceedings of the International Conference on
Extending Database Technology, 2019.
Y. Wei et al., “Distributed differential privacy via shuffling versus aggregation:
A curious study,” IEEE Transactions on Information Forensics and Security, vol. 19,
pp. 2501–2516, 2024.
A. Girgis et al., “Shuffled model of differential privacy in federated learning,”
Proceedings of Machine Learning Research, vol 130, 2021.
A. M. Girgis et al., “On the Rényi differential privacy of the shuffle model,” Proceedings
of the ACM SIGSAC Conference on Computer and Communications Security, pp. 2321-2341,
2021.
K. Bonawitz et al., “Practical secure aggregation for privacy-preserving machine
learning,” Proceedings of the ACM SIGSAC Conference on Computer and Communications
Security, pp. 1175–1191, 2017.
J. H. Bell et al., “Secure single-server aggregation with (poly)logarithmic overhead,”
Proceedings of the ACM SIGSAC Conference on Computer and Communications Security,
pp. 1253–1269, 2020.
T-Drive trajectory data sample, https://www.microsoft.com/en-us/research/publication/t-drive-trajectory-data-sample,
2018.
저자소개
Jong Wook Kim received his Ph.D. in Computer Science from Arizona State University
in 2009. He is currently a professor in the Department of Computer Science at Sangmyung
University. His primary research interests include data privacy, distributed databases,
and query optimization.