기술 요약: 로컬 모델에서의 함수 프라이버시 보호 (Function Privatization)

문제 정의

본 논문은 함수 프라이버시 보호(function privatization) 문제를 다루며, 특히 궤적 데이터나 1차원 밀도 곡선과 같이 유한한 구간 위의 연속 함수의 이미지로서 자연스럽게 존재하는 데이터를 공개하는 데 초점을 맞춥니다. 설정은 각 사용자가 자신의 데이터를 신뢰할 수 없는 분석가에게 보내기 전에 스스로 프라이버시를 보호하는 **로컬 모델(local model)**의 차분 프라이버시(differential privacy)입니다.

식별된 핵심 과제는 표준 **로컬 차분 프라이버시(Local DP)**가 함수의 유사성과 관계없이 서로 다른 임의의 두 함수를 구별할 수 없도록 요구한다는 점입니다. 이러한 균등한 보장은 함수형 데이터에 대해 너무 강력하여 낮은 효용성을 초래합니다. 예를 들어, 거의 동일한 선형 함수($2t+3$와 $2.01t+2.99$)는 매우 상이한 함수($2t+3$와 $2000t-3000$)와 동일한 수준의 노이즈를 요구받게 됩니다.

이를 해결하기 위해 저자들은 일반화된 차분 프라이버시 개념인 **지오 프라이버시(Geo-Privacy, GP)**를 채택합니다. GP는 메트릭 공간(metric space) 내 두 인스턴스 사이의 거리에 비례하여 구별 불가능성 수준이 결정된다고 규정합니다. 함수에 대해 본 논문은 $L_2$ 메트릭(제곱 평균 제곱근 거리)을 활용하며, 이는 국소적인 미세 변동에 강건하고 물리적 에너지 개념과 일치합니다.

방법론

본 논문은 단순한 파라미터 형태에서 임의의 연속 곡선에 이르기까지, 입력 함수의 구조에 대한 다양한 가정에 맞춘 일련의 메커리즘을 제안합니다.

1. 파라미터 함수 (선형 및 기저 표현)

저자들은 먼저 고정된 수의 기저 함수(basis functions)의 선형 결합으로 표현될 수 있는 함수들을 고려합니다.

• 선형 함수: 함수 $f_a(t) = a_1 t + a_2$의 경우, 문제는 계수 벡터 $a \in \mathbb{R}^2$를 프라이버시 보호하는 문제로 축소됩니다. 계수 벡터 $a$에 구형 라플라스 노이즈(spherical Laplace noise)를 더하는 단순한 방식의 벡터 프라이버시 적용은 실패하는데, 그 이유는 계수 벡터 간의 유클리드 거리가 결과 함수 간의 $L_2$ 거리와 일치하지 않기 때문입니다.
• 해결책: 저자들은 특정 노이즈 분포를 도출합니다. 두 함수 사이의 $L_2$ 거리를 계수를 통해 표현함으로써, 이들은 공분산 행렬 $\Sigma$(기저 함수들의 내적으로 유도됨)를 식별합니다. 메커리즘은 계수 벡터 $a$에 $a + \frac{1}{\varepsilon}\Sigma^{1/2}Z$의 형태로 노이즈를 추가합니다 (여기서 $Z$는 표준 구형 라플라스 벡터임). 이는 출력이 $L_2$ 메트릭에 대해 $\varepsilon$-GP를 만족하도록 보장합니다.
• 일반화: 이 접근 방식은 $m$개의 기저 함수를 가진 함수(예: 다항식) 및 벡터 값 함수로 확장됩니다. 노이즈 크기는 $\sqrt{m}$에 비례하여(라플라스 노이즈의 경우 기대값으로 $m$) 조정되며, 이는 함수 공간의 차원과 프라이버시 손실 사이의 균형을 맞춥니다.

2. 임의 함수 (투영 및 프라이버시 보호)

특정한 파라미터 형태를 엄격히 따르지 않는 $L_2(I)$ 내의 함수들을 위해, 저자들은 투영 및 프라이버시 보호(Project-and-Privatize) 프레임워크를 제안합니다.

1. 투영(Projection): 입력 함수 $q$를 선택된 기저 함수 집합에 의해 생성된 유한 차원 부분 공간 $U_f$로 투영합니다.
2. 프라이버시 보호(Privatization): 위에서 설명한 파라미터 메커리즘을 투영된 계수에 적용합니다.
3. 오차 분석: 총 오차는 근사 오차(함수 $q$와 투영 사이의 거리)와 프라이버시 노이즈로 구성됩니다. 여기에는 트레이드오프가 존재합니다: 더 많은 기저 함수를 사용하면 근사 오차는 줄어들지만 프라이버시 노이즈는 증가합니다.

3. 자동 기저 선택 (PrivFuncSelect)

근사 오차와 프라이버시 노이즈 사이의 트레이드오프를 자동화하기 위해, 본 논문은 **알고리즘 3 (PrivFuncSelect)**을 도입합니다. 이 알고리즘은 **희소 벡터 기법(Sparse Vector Technique, SVT)**을 사용하여 다음을 수행합니다:

• 입력을 잘 근사하는 충분히 큰 기저 함수 집합을 식별합니다.
• 크기가 작은 계수(정확도에는 거의 기여하지 않으면서 상당한 노이즈를 더하는 계수)를 필터링하여 기저 함수의 부분 집합을 프라이빗하게 선택합니다.
• 이 알고리즘은 세심한 프라이버시 예산 구성을 통해 $\varepsilon$-GP를 유지하면서 두 가지 오차 원천 사이의 균형을 맞춥니다.

4. 곡선 프라이버시 보호 (구간별 근사)

일반적인 곡선을 위해, 저자들은 **구간별 기저 함수(piecewise basis functions)**를 사용하는 알고리즘 4 (PrivFuncSeg) 및 **알고리즘 5 (ReduceSeg)**를 제안합니다.

• 세분화(Segmentation): 알고리즘은 근사와 노이즈 사이의 균형을 맞추기 위해 필요한 하위 구간의 수를 결정하기 위해 SVT를 사용합니다.
• 정제(Refinement): 곡선의 평탄한 영역에서 불필요한 하위 구간을 제거하여, 근사 오차를 크게 높이지 않으면서 노이즈 벡터의 차원을 줄이는 재귀적 감소 프로세스를 채택합니다.
• 연속성(Continuity): 사후 처리 단계는 가장 가까운 연속 곡선을 찾기 위해 제약 조건이 있는 이차 계획법(constrained quadratic program)을 풀어, 프라이버시가 적용된 곡선이 구간 경계에서 연속성을 유지하도록 합니다.
• 무한 구간: 프레임워크는 함수 에너지가 구간 외부에서 무시할 수 있는 수준이 되는 절단점 $\bar{T}$를 찾기 위해 SVT를 사용한 후, 유한 구간 알고리즘을 적용함으로써 무한 영역($\mathbb{R}$)으로 확장됩니다.

주요 기여

1. 함수를 위한 지오 프라이버시 프레임워크: 본 논문은 $L_2$ 메트릭을 사용하여 함수형 데이터에 지오 프라이버시를 적용하는 엄격한 프레임워크를 구축하였으며, 이 메트릭이 점별(point-wise) 메트릭보다 유사한 함수에 대해 더 강력한 보호를 제공함을 입증했습니다.
2. 최적의 노이즈 메커리즘: 저자들은 나이브한 등방성 노이즈 추가의 실패를 교정하여, 함수 공간의 기하학적 구조(행렬 $\Sigma$를 통해)를 고려한 특정 노이즈 메커니즘을 도출했습니다.
3. 적응형 알고리즘: PrivFuncSelect 및 PrivFuncSeg의 개발은 기저 함수 및 세분화 지점을 자동으로 선택할 수 있게 해줍니다. 이 알고리즘들은 함수의 복잡도에 대한 사전 지식 없이도 근사 오차와 프라이버시 노이즈 사이의 균형을 동적으로 맞춥니다.
4. 벡터 값 지원: 제안된 방법들은 벡터 값 함수 및 계수로 자연스럽게 확장되어, 다차원 궤적에도 적용 가능합니다.
5. 연속성 보존: 본 논문은 현실적인 곡선 재구성에 필수적인 요구 사항인, 프라이버시가 적용된 구간별 함수에서 연속성을 강제하는 방법을 제공합니다.

실험 결과 및 주장

본 논문은 제안된 방법의 실질적인 효용성을 입증하기 위해 여러 데이터셋(궤적 데이터 포함)에 대해 실험적 평가를 수행합니다.

• 효용성 개선: 결과에 따르면 제안된 방법은 이산적인 점들을 독립적으로 프라이버시 보호하는 나이브한 솔루션에 비해 훨씬 더 나은 효용성(낮은 $L_2$ 오차)을 달eric합니다.
• 적응성: 적응형 알고리즘은 다양한 유형의 곡선에 대해 최적의 기저 함수 수 또는 세그먼트 수를 성공적으로 식별하며, 함수가 매끄럽거나 평탄한 영역에서 노이즈를 효과적으로 줄입니다.
• Local DP와의 비교: 본 논문은 표준 Local DP 하에서는 데이터 유니버스를 매우 작은 공간으로 제한하지 않고는 일반적인 곡선에 대해 의미 있는 효용성을 얻는 것이 불가능하다고 주장합니다. 반면, GP 기반 접근 방식은 전형적인 실제 세계의 함수형 데이터에 대해 높은 효용성을 허용합니다.

의의

본 논문은 로컬 모델에서의 함수 프라이버시 보호가 단순히 함수를 이산화하고 점별 프라이버시를 적용하는 것으로는 해결할 수 없는, 구별되고 도전적인 문제라고 주장합니다. 지오 프라이버시 정의와 $L_2$ 메트릭을 활용함으로써, 저자들은 이론적으로 견고하고 실용적으로 효과적인 프레임워크를 제공합니다. 그 의의는 다음과 같습니다:

• 상관관계 포착: 방법론들은 함수형 데이터에 내재된 상관관계(예: 매끄러움, 주기성)를 자동으로 활용하여 노이즈를 줄입니다.
• 이론적 우아함: 솔루션은 단순히 이산적인 점들이 아닌 실수 위에서 정의된 함수를 출력하여 데이터의 연속성을 보존합니다.
• 실용적 적용 가능성: 알고즘은 벡터 값 궤적 및 임의의 연속 곡선을 포함한 실제 시나리오를 처리할 수 있도록 설계되었으며, 이는 교통 및 신호 처리와 같은 분야에서 프라이버시를 보호하는 데이터 분석을 위한 실행 가능한 경로를 제공합니다.

저자들은 초기 기저 컬렉션(예: 푸리에, 다항식, sinc 함수)의 선택은 애플리케이션에 따라 달라질 수 있다는 점을 언급하며 신중한 입장을 유지하지만, 그들의 프레임워크가 이러한 컬렉션을 최적으로 활용할 수 있는 메커니즘을 제공한다고 밝힙니다.