기술 요약: DP4SQL - 유연한 프라이버시 정책을 갖춘 차분 프라이버시 SQL

문제 정의

차분 프라이버시(Differential Privacy, DP)는 단일 테이블 데이터셋에는 잘 확립되어 있으나, 다중 관계형 데이터베이스에 적용하는 것은 여러 관계에 걸친 "그럴듯한 부인(plausible deniability)"의 정의가 복잡하기 때문에 여전히 도전적인 과제로 남아 있습니다. 기존의 차분 프라이버시 SQL 시스템들은 다음과 같은 한계를 가집니다.

기존 시스템의 핵심 제한 사항은 다음과 같습니다:

1. 비유연한 정책: 서로 다른 테이블이나 동일한 테이블 내의 서로 다른 컬럼이 각기 다른 보호 수준(예: 한 테이블에서는 레코드의 존재 여부를 보호하고, 다른 테이블에서는 속성 값만을 보호하는 경우)을 요구하는 시나리오를 처리할 수 없습니다.
2. 공개 지식 통합의 어려움: 공개된 정보(예: 알려진 테이블 크기, 교수 이름과 같은 공개된 컬럼 값)를 프라이버시 계산에 통합하는 데 어려움을 겪습니다. 이러한 공개 지식을 무시하면 데이터를 과잉 보호(과도한 노이즈 주입)하거나, 레코드의 존재 여부를 마스킹하는 데 실패하여 과소 보호(데이터 누출)하는 결과가 발생합니다.
3. 복잡한 엔티티 상호작용: 기존 모델은 외래 키(Foreign Keys)와 전이적 소유권(Transitive Ownership)을 올바르게 처리하지 못하는 경우가 많습니다, 특히 엔티티가 상호작용할 때(예: 교수가 학생에게 성적을 부여하는 경우) 그렇습니다. 이는 잘못된 민감도 계산으로 이어져, 불충분한 노이즈(프라이버시 침해) 또는 과도한 노이즈(유용성 상실)를 초래합니다.

방법론

본 논문은 고수준의 프라이비시 정책 명세와 저수준의 자동화된 추론을 분리하는 DP4SQL을 제안합니다. 이 방법론은 세 가지 주요 구성 요소로 이루어집니다.

1. 고수준 프라이버시 라벨링 프레임워크

데이터 관리자는 스키마의 각 관계(Relation)에 대해 간단한 고수준 라벨링 시스템을 사용하여 정책을 지정합니다. 구별되는 엔티티 관계 $R^\star$(예: 학생 또는 교수)에 대해, 각 관계 $R_i$에는 다음 세 가지 라벨 중 하나가 할당됩니다:

• DEL (Delete): 레코드의 존재 자체가 비공개입니다. 반사실적 세계(Counterfactual worlds)는 레코드를 삭제함으로써 생성됩니다. 이는 경계가 없는 이웃(Unbounded neighbors)에 해당합니다.
• REPA (Replace): 레코드의 존재는 공개되어 있으나, 특정 속성 $A$는 비공개입니다. 반사실적 세계는 $A$의 값을 교체함으로써 생성됩니다. 이는 경계가 있는 이웃(Bounded neighbors)에 해당합니다.
• PUB (Public): 관계 전체가 공개되어 있습니다.

이 프레임워크를 통해 학생의 존재는 보호(DEL)하면서 교수 이름은 공개(PUB)하고 교수의 급여는 보호(REPA)하는 것과 같은 혼합 정책을 구현할 수 있습니다.

2. 저수준 그럴듯한 부인 액션(Plausible Deniability Actions)

자동화된 추론을 위해, 시스템은 고수준 라벨을 인접한 데이터베이스 간의 쿼리 결과가 겪을 수 있는 최대 변화를 설명하는 그럴듯한 부인 액션 세트로 변환합니다. 액션은 다음과 같습니다:

• Add$_a$ / Del$_d$: $a$ 또는 $d$개의 행을 추가하거나 삭제함.
• Rep$^A_k$: $k$개의 행에서 속성 $A$의 값을 교체함.

시스템은 다음을 포함하는 복잡한 SQL 쿼리에 대해 액션을 도출하기 위해 프로덕션 규칙을 갖춘 추론 시스템을 사용합니다:

• 기본 관계(Base Relations): 규칙은 외래 키 제약 조건으로부터 도출된 최대 소유 관계($\hat{\otimes}$)를 고려하여 프라이버시 라벨을 초기 액션으로 매핑합니다.
• 단항 변환(Unary Transformations): 선택($\sigma$), 투영($\pi$), 그룹화($\gamma$)에 대한 규칙은 술어(Predicate)나 그룹화 키가 보호된 속성과 교차하는지 여부에 따라 액션을 전파합니다.
• 조인(Joins): 시스템은 키 조인(Key Joins)(기본 키-외래 키 쌍에 대한 조인)과 **일반 조인(General Joins)**을 구분합니다. 키 조인은 무결성 제약을 활용하여 레코드 변화에 대한 더 타이트한 경계를 도출하며, 일반 조인 규칙에서 흔히 발생하는 과대 근사(Over-approximation)를 피합니다.

3. 민감도 계산 및 노이즈 주입

추론된 액션은 전역 민감도(Global Sensitivity, $\hat{\Delta}$)의 상한값으로 매핑됩니다. 이 상한값은 라플라스 메커니즘(Laplace mechanism)을 통해 주입될 노이즈의 규모를 결정합니다. 시스템은 추론된 액션(추가, 삭제, 교체)이 출력 벡터에 어떻게 영향을 미치는지 분석하여 집계 함수(COUNT, SUM)에 대한 민감도를 계산합니다.

주요 기여

1. 유연한 정책 명세: 외래 키가 있는 관계형 스키마 전반에서 혼합된 프라이버시 요구사항(공개된 크기, 공개된 컬럼, 비공개 속성)을 지원하는 고수준 컬럼 라벨링 프레임워크를 제공합니다.
2. 자동화된 추론 엔진: 고수준 라벨을 저수준의 그럴듯한 부인 액션으로 변환하고, 관계 대수 쿼리(조인, 집계, 서브쿼리)의 안정성을 건전하게 추론하는 공식적인 추론 시스템을 제공합니다.
3. 더 타이트한 민감도 경계: 공개된 지식(예: 알려진 테이블 크기)을 명시적으로 모델링하고 키 조인 전용 규칙을 사용함으로써, DP4SQL은 최악의 시나리오를 가정하는 기존 시스템보다 더 타이트한 민감도 경계를 도출합니다.
4. 구현 및 검증: DP4SQL은 SQL 쿼리를 가로채서 필요한 노이즈를 계산하고 차분 프라이버시가 적용된 답변을 반환하는 데이터베이스 미들웨어로 구현되었습니다.

결과

논문은 대학 스키마 케이스 스터디와 TPC-H 벤치마크를 사용하여 DP4SQL을 평가하였으며, 이를 베이스라인 정책(순수 경계 없는 이웃 및 순수 경계 있는 이웃) 및 PrivateSQL 기반의 Tumult Analytics 시스템과 비교하였습니다.

• 프라이버시 정확성 (과소 보호): 테이블 크기가 공개된 시나리오(예: TPC-H의 주문 수)에서, 기존의 경계 없는 모델(예: Tumult)은 레코드의 존재 자체가 비공개라고 잘못 가정합니다. 이는 레코드를 삭제하는 대신 교체하는 것이 (크기가 알려진 경우) 유효한 반사실적 행동임을 고려하지 못하여 과소 보호(불충 sufficient 노이즈)를 초래합니다. DP4SQL은 이러한 사례를 정확히 식별하고 적절한 노이즈를 적용합니다.
• 유용성 개선 (과잉 보호): 베이스라인 모델은 종종 모든 속성을 비공개로 취급하여 과잉 보호(과도한 노이즈)를 유발합니다. 예를 들어, 대학 케이스 스터디에서 공개된 리뷰 점수나 교수 이름에 대한 쿼리는 DP4SQL의 유연한 정책 하에서 민감도가 0이었으나, 베이스라인은 상당한 노이즈를 주입했습니다. TPC-H에서 DP4SQL은 공개된 정보(예: 공급업체 수)를 반환하는 쿼리에 대해 0의 민감도를 달성한 반면, 베이스라인은 결과를 사용할 수 없게 만드는 노이즈(상대 오차 > 100%)를 추가했습니다.
• 정확도: 베이스라인이 과잉 보호를 수행한 경우, DP4SQL은 현저히 낮은 상대 오차를 보여주었습니다(특정 TPC-H 쿼리에 대해 DP4SQL은 19.6%의 오차를 보인 반면, 베이스라인은 훨씬 높은 오차를 기록함).

의의 및 주장

본 논문은 DP4SQL이 기존 DP SQL 시스템의 "원 사이즈 포 올(one-size-fits-all)" 한계점을 해결한다고 주장합니다. 데이터 큐레이터가 그럴듯한 부인 요구사항을 맞춤 설정할 수 있게 함으로써, 시스템은 프라이버시 침해(과소 보호로 인한)와 데이터 유용성 상실(과잉 보호로 인한) 사이의 트레이드오프를 피합니다.

저자들은 자신들의 접근 방식이 **건전(Sound)**함을 강조합니다. 즉, 추론 시스템이 전역 민감도의 상한을 정확하게 도출한다는 것을 형식적으로 증명하여, 결과적인 메커니즘이 $(PS, R^\star, \epsilon)$-차분 프라이버시를 만족함을 보장합니다. 이 연구는 올바른 프라이버시 모델링, 특히 공개된 테이블 크기, 공개된 컬럼, 그리고 세밀한 속성 보호를 추론하는 능력이 복잡한 다중 테이블 관계형 환경에 차분 프라이버시를 배포하는 데 필수적임을 강조합니다.