Abstract
프라이버시를 보호하는 데이터 마이닝 영역에서 DP 메커니즘은, 개인의 정보가 유출될 위험이 적기 때문에 사람들이 데이터를 공유하도록 장려하는 역할을 한다고 직관적으로 해석될 수 있다.
그러나 저자는 이 해석이 불완전하다고 주장한다. 그 이유는 사람들이 데이터베이스에 참여하려면 외부 인센티브(external incentives)가 필요하며, 따라서 데이터 공개 메커니즘은 단순히 DP를 만족하는 것뿐만 아니라, 인센티브와도 호환되어야 한다.
그렇지 않으면, 수집된 데이터가 허위일 가능성이 있다.
저자는 게임 이론에서의 진실성(truthfulness) 개념을 적용하여 이 문제를 분석한다. 특정 환경에서는, 기존 DP 메커니즘이 참가자들이 정보를 진실하게 보고하도록 장려하지 못한다는 결과를 보인다.
On the positive side
긍정적인 측면에서, 저자는 ‘진실성을 유지하는 DP 보호 변환 방법’을 제시한다.
이 변환은 유형 공간이 작고, 사회적 복지(social welfare)와 같은 민감하지 않은 지표를 최적화하는 게임에 적용 가능하다.
또한, 이 변환 과정은 최적성(optimality)에서 작은 추가적 손실(small additive loss)만 발생하며, 계산적으로 효율적이다.
특히, VCG(Vickrey-Clarke-Groves) 메커니즘과 결합하면, 작은 유형 공간을 가진 모든 사회적 복지 게임에 대해, 차등 개인정보 보호를 만족하면서도 진실성을 유지하는 근사적으로 효율적인 메커니즘이 존재함을 보인다.
저자는 또한 메커니즘에 의해 유출되는 정보에 대해 명확한 수치적 비용(numerical cost)이 할당되는 모델을 연구한다.
이 경우, DP 개념조차도 사람들이 진실하게 참여하도록 유도하기에 충분히 강력하지 않을 수 있음을 보인다.
특히, 데이터베이스의 노이즈가 추가된 히스토그램(perturbed histogram)을 공개하는 메커니즘이 지나치게 많은 정보를 노출할 수 있음을 입증한다.
또한, Blum et al. (STOC ’08)의 메커니즘과 같이, 원본 데이터베이스와 유사한 개요(synopsis)를 출력하는 메커니즘도 지나치게 많은 정보를 노출할 수 있음을 보인다.
Keywords: differential privacy, mechanism design
1. Introduction
세상이 점점 더 디지털화되고 연결됨에 따라 개인 정보 보호에 대한 우려가 점점 더 커지고 있다. 다양한 조직들이 개인의 데이터를 수집, 접근, 저장하면서,
- 데이터를 최대한 활용하려는 욕구와,
- 의료 기록, 인구 통계 정보 등 다양한 개인정보를 보호하려는 욕구
이 두 가지가 강한 긴장 상태에 놓이게 되었다.
이러한 긴장을 이해하고 해결하려는 것은 통계(statistics) 및 데이터 분석(data analysis) 연구 분야에서 오랫동안 다루어 온 목표였다 [5, 16].
보다 최근에는 이론적 컴퓨터 과학 분야에서 이 문제를 다루기 위한 정의와 엄격한 접근법(rigorous treatment)을 제시했으며, 이 연구는 결국 DP 개념의 정의 및 연구로 이어졌다 [11, 8].
DP는 다음을 보장한다:
어떤 데이터베이스가 주어졌을 때, 특정 참여자 i의 존재 여부가 데이터 공개 메커니즘의 출력 s에 미치는 확률적 영향이 최대 \(e^{\epsilon}\)배를 초과하지 않도록 한다. (즉, 특정 개인의 데이터가 포함되었는지 여부가 결과에 미치는 영향이 제한된다.)
그러나, 개인정보 보호를 보장하면서도 데이터 유용성을 유지할 수 있는가? 라는 질문이 남는다.
극단적인 경우, 데이터를 전혀 보지 않고 일정한 값을 출력하는 메커니즘을 만들면 완벽한 개인정보 보호는 가능하지만,
이는 실용성이 전혀 없는(trivially private but not very useful) 메커니즘이 된다.
차등 개인정보 보호가 제공하는 엄격한 정의를 사용하면, 특정한 작업들이 개인정보 보호(privacy)와 유용성(utility)을 공식적으로 보장(formal guarantees)하는 방식으로 수행 가능함을 증명할 수 있다.
어떤 문제에서 유의미한 유용성(meaningful utility)과 차등 개인정보 보호(differential privacy)를 동시에 달성할 수 있는 경우, 차등 개인정보 보호의 보장은 다음과 같이 해석된다.
: 차등 개인정보 보호 메커니즘의 출력 분포(output distribution)는 특정 참여자 i의 존재 여부에 거의 영향을 받지 않는다.
따라서, 이 메커니즘은 참여자 i에 대한 개인정보를 거의 유출하지 않으며,
그 결과, 참여자 i는 자신의 데이터를 데이터베이스에 안전하게 제공할 수 있다고 느낄 것이다.
Differential privacy and incentives.
본 논문에서는 위에서 논의한 해석을 심층적으로 탐구한다.
개인의 데이터베이스 참여 동기: 왜 사람들이 데이터를 제공하는가?
만약 개인이 자신의 정보 보호에 대한 우려를 가지고 있다면, 데이터를 제공하는 대신 이를 상쇄할 수 있는 인센티브를 받아야만 한다.
아무런 인센티브도 제공하지 않는 조직에 개인이 기꺼이 자신의 데이터를 제공하는 것은 상상하기 어렵다.
개인들은 자신과 무관한 상품을 판매하는 마케팅 회사에 자발적으로 정보를 제공하지 않는다.
단, 금전적 보상 또는 경품 당첨 기회 등의 인센티브가 주어지면 참여할 수 있다.
반면, Facebook에서 친구들과 연결되거나, Google의 이메일 서비스를 이용하는 것과 같은 이득이 있다면, 개인들은 기꺼이 개인정보를 공개한다.
게임 이론적 관점에서의 접근
게임 이론(game theory) 관점에서 접근하면, 특정 데이터베이스가 민감한 정보(sensitive information)를 수집할 경우, 해당 데이터베이스에는 개인이 참여하도록 유도하는 게임(game)이 존재해야 한다. 즉, 데이터베이스 참여를 위한 인센티브 구조가 필요하다.
일반적인 인센티브 설정
본 연구에서는 가장 일반적인 인센티브 설정을 다음 두 가지 관점에서 연구한다.
- 개인의 인센티브는 서로 충돌할 수 있으며, 데이터베이스 관리자의 인센티브와도 일치하지 않을 수 있다.
- 개인은 자신의 이익을 위해 데이터를 거짓으로 보고할 수 있다.
이와 다른 가정을 사용하는 연구들에 대한 논의는 2.4.1절에서 다룬다.
2. Our results
이 논문의 주요 기여(contribution)는 개념적(conceptual)이다.
저자는 차등 개인정보 보호(differential privacy)와 게임 이론적 인센티브(game-theoretic incentives)를 결합한 자연스럽고 일관된 모델을 제안한다.
즉, 개인정보 보호와 인센티브 호환성(incentive compatibility)을 동시에 고려하는 모델을 연구해야 한다고 주장한다.
긍정적인 결과
저자는 제안한 모델에서 차등 개인정보 보호를 인센티브와 양립 가능하게(incentive-compatible way) 달성할 수 있음을 보이는 일반적인 긍정적인 결과(general positive results)를 증명한다.
즉, 적절한 메커니즘 설계를 통해 개인정보 보호를 유지하면서도 사람들이 진실하게 데이터를 제공하도록 유도할 수 있음을 보인다.
부정적인 결과
반면, 개인정보 보호에 명확한 비용(explicit costs)을 부여할 경우, 추가적인 주의가 필요함을 보이는 부정적인 결과(negative results)도 제시한다.
즉, 잘못된 비용 설계는 차등 개인정보 보호와 인센티브 호환성을 저해할 수 있다.
2.1. Our model
The differential privacy setting.
데이터베이스 관리자(database curator)는 개인들로부터 정보를 제공받아 데이터베이스를 구축한다.
데이터베이스의 각 행(row)은 한 개인의 정보를 포함한다.
관리자는 데이터베이스에 차등 개인정보 보호 메커니즘(release mechanism)을 적용하여 결과를 생성한 후 이를 공개(publish)한다.
데이터 공개 메커니즘에는 출력의 품질을 평가하는 품질 지표(quality metric)가 존재한다고 가정한다.
데이터베이스 관리자는 품질이 높은(high quality) 출력을 생성하는 메커니즘을 원한다.
반면, 개인들은 데이터가 차등 개인정보 보호를 만족하는 방식으로 처리되기를 원한다.
이 두 가지 목표는 서로 충돌(tension)할 수 있다.
The mechanism design setting.
본 논문에서는 메커니즘 설계(mechanism design)의 게임 이론적 설정(game-theoretic setting)을 비공식적으로 소개한 후, 이를 차등 개인정보 보호(differential privacy) 문제와 연결한다. (in Section 3)
보다 구체적인 이해를 돕기 위해, 논문에서는 각 개념을 단일 품목(single-item) 경매의 맥락에서 설명한다.
- 메커니즘 설계(mechanism design)에서는 n 명의 플레이어(players)가 존재하며, 각 플레이어는 개인적인 정보(private information)인 “유형(type)“을 가진다.
(예: 경매의 경우, 플레이어의 “유형”은 해당 품목에 대한 자신의 가치 평가(value of the item)이다. - 가능한 결과 공간(outcome space)이 존재한다.
(예: 경매의 경우, 결과는 낙찰자(winner)의 결정과 최종 가격(price)이다.) - 각 플레이어는 개인적인 효용 함수(utility function)를 가지며, 특정 결과에서 자신이 얻는 효용을 결정한다.
(예: 경매의 경우, 낙찰된 플레이어의 효용: 품목 가치 – 지불 가격. 낙찰되지 않은 플레이어의 효용: 0) - 각 플레이어의 목표는 자신의 개별 효용(individual utility)을 최적화하는 것이다.
- 글로벌 효용(global utility) 함수도 존재하며, 이는 전체 결과의 품질을 평가한다.
(예: 사회적 복지(social welfare) = 모든 플레이어의 효용 합)
메커니즘(mechanism)이란,
플레이어들의 유형(type) 설정을 특정 결과(outcome)로 매핑하는 (랜덤화 가능) 함수이다.
메커니즘 설계에서 연구하는 핵심 문제는 다음 두 가지 속성을 만족하는 메커니즘을 구축하는 것이다.
- 효율성 (Efficiency)
모든 플레이어 유형에 대해, 메커니즘이 생성하는 기대 글로벌 효용(expected global utility)이 최적 글로벌 효용(optimal global utility)에 가깝도록 해야 한다. - 진실성 (Truthfulness)
어떠한 플레이어 유형 설정에서도, 특정 플레이어 i가 거짓 유형(false type)을 보고했을 때 그가 진실하게 유형을 보고한 경우보다 더 큰 기대 효용을 얻을 수 없다.
즉, 각 플레이어가 자신의 유형을 정직하게 보고하는 것이 최선의 전략이 되도록(truthful, incentive-compatible) 메커니즘을 설계해야 한다.
개인 효용(individual utility)과 글로벌 효용(global utility)이 반드시 일치하지 않기 때문에, 위의 두 가지 기준(효율성 & 진실성)을 동시에 만족하는 메커니즘을 구현하는 것은 매우 어렵다.
예를 들어, 단일 품목 경매(single-item auction) 문제를 연구한 결과, “빅리(Vickrey) 2차 가격 경매(Vickrey 2nd-price auction)” 메커니즘이 도출되었다.
(이는 진실성을 만족하는 대표적인 경매 메커니즘 중 하나이다.)
The combined model.
이제 차등 개인정보 보호 환경을 게임 이론적 용어를 사용하여 자연스럽게 다시 서술할 수 있다.
개인은 플레이어이며, 각 개인의 개인 정보는 그의 유형이다.
데이터베이스는 모든 플레이어의 유형을 연결한 것이다.
데이터베이스 공개 메커니즘은 게임 이론적 의미에서의 메커니즘과 동일하다.
품질 지표는 게임의 글로벌 효용이며, 따라서 “정확한” 공개 메커니즘은 “효율적인” 게임 이론적 메커니즘에 해당한다.
위 내용 외에도, 개인 효용 함수는 이제 플레이어들의 행동에도 영향을 미칠 수 있다.
진실성은 단순히 게임 이론의 표준 개념이기 때문만이 아니라, 개인정보 보호 자체가 진실성이 없으면 의미가 없기 때문에 필수적이다.
수집된 데이터가 잘못 보고되었다면, 데이터베이스 관리자에게 거의 쓸모가 없다.
게다가, 잘못된 데이터를 보호하는 것은 불필요해 보인다.
또한 차등 개인정보 보호에서 주요한 우려는 개인정보 보호 수준이 너무 낮으면 개인들이 데이터베이스에 참여하지 않을 수도 있다는 점이다.
게임 이론적 환경에서는 진실성과 참여가 밀접하게 관련되어 있다. 게임을 확장하여 “⊥” 유형을 추가하면, 이는 비참여를 의미하며, 플레이어가 “⊥” 유형으로 이탈하는 것은 비참여를 나타낼 수 있다.
반대로, 자신의 실제 유형과 무관한 유형을 보고하는 플레이어는 어떤 의미에서는 참여하지 않는 것을 선택한 것이다.
이 논문의 나머지 부분에서는 진실성에 초점을 맞추되, 비참여가 진실성에서 벗어나는 특정한 형태라는 점을 이해하고 논의를 진행한다.
Roadmap.
개인정보 보호만을 독립적으로 연구할 때 만족스러워 보이는 메커니즘도, 진실성을 명시적으로 고려하면 반드시 만족스러운 것은 아니다.
차등 개인정보 보호와 진실성의 관계를 두 가지 프레임워크에서 살펴본다.
첫 번째 프레임워크에서는, 진실성을 만족하고 효율적이며 출력이 차등 개인정보 보호를 따르는 메커니즘을 구성한다.
이 모델에서는 개인정보 보호를 명확한 수치값으로 표현하지 않고, 단순히 메커니즘의 추가적인 속성으로 고려한다.
이러한 메커니즘을 PTE라고 부르며, 유형 공간이 작고 글로벌 효용이 특정 플레이어의 유형에 민감하지 않으며 각 유형을 가진 플레이어 수에만 의존하는 게임에 대해, 진실하고 효율적인 메커니즘을 PTE 메커니즘으로 변환하는 방법을 제시하여 최초의 PTE 메커니즘을 보인다.
두 번째 프레임워크에서는 개인정보 보호의 가치를 명시적으로 수량화한다.
메커니즘에 의해 유출되는 정보량에 대해 0이 아닌 비용을 부여하고, 정보 공개 비용이 플레이어가 게임에서 얻는 효용을 초과하는 경우를 분석한다.
개인정보 보호에 비용이 부여될 경우, 차등 개인정보 보호를 만족하는 메커니즘조차도 개인이 자신의 정보를 진실하게 공개하도록 동기부여하지 못할 수 있음을 보인다.
첫 번째 프레임워크는 개인정보 손실을 정량화하지 않기 때문에 다소 단순해 보일 수 있지만, 그곳에서 개발된 기법들이 두 번째 프레임워크에도 적용될 수 있음이 이후 연구에서 밝혀졌다.
2.2. Private, truthful, and efficient (PTE) mechanisms
The Exponential Mechanism is not necessarily truthful.
저자의 첫 번째 결과는 지수 메커니즘(Exponential Mechanism)이 진실성을 만족하는지 여부에 대한 질문을 다시 탐색한다. Nissim et al. [31]은 이미 지수 메커니즘이 진실성을 만족하지 않음을 보이는 반례(counter-example)를 제시한 바 있다. 그러나, 그들이 제시한 반례는 다소 인위적이다.
그 이유는 해당 게임에서는 개인정보 보호를 고려하지 않더라도 효율적이고 진실한 메커니즘이 존재하지 않기 때문이다.
저자는 다음 정리(Theorem 2.1)가 지수 메커니즘의 단점을 더 명확하게 보여준다고 생각한다.
그 이유는 우리가 고려하는 LINE-1-FAC 게임에서는 진실하고 효율적인 메커니즘이 존재하기 때문이다.
더 나아가, 저자는 LINE-1-FAC에 대해 PTE 메커니즘조차 존재함을 보인다.
저자는 잘 연구된 선형 공간에서 하나의 시설을 배치하는 게임(1-facility location on a line game, LINE-1-FAC)을 고려한다.
이 게임은 k-시설 문제(k-facility problem) [31, 26, 1]의 특수한 경우이며, 단일 봉우리 선호(single-peaked preference) 게임 [28, 33]의 사례이기도 하다.
LINE-1-FAC 게임에서, 각 플레이어는 구간 [0,1] 내에서 한 점을 갖는다.
메커니즘은 구간 [0,1] 내에서 하나의 위치 s를 출력해야 한다.
각 개인의 목표는 출력된 s까지의 거리를 최소화하는 것이며, 메커니즘의 목표는 모든 개인의 거리 합을 최소화하는 것이다.
이 게임에서는 금전적 보상이 없는(non-monetary) 진실하고 효율적인 메커니즘이 존재하는데, 이 게임에서는 금전적 보상이 없는(non-monetary) 진실하고 효율적인 메커니즘이 존재하는데, 저자는 다음을 증명한다.
정리 2.1. LINE-1-FAC 게임에서, 어떠한 개인정보 보호 수준 \(\epsilon > 0\) 에 대해서도 지수 메커니즘(Exponential Mechanism)은 진실성을 만족하지 않는다.
Transforming a truthful and efficient mechanism into a private, truthful, and efficient mechanism.
저자의 주요 긍정적인 기술적 결과는 진실하고 효율적인 메커니즘을 PTE 메커니즘으로 변환하는 방법이다.
보다 정확히 말하면, 저자는 \((\epsilon, \eta)\)-차등 개인정보 보호 개념을 사용한다 [10].
이 개념은 기존 \(\epsilon\)-차등 개인정보 보호에서 요구하는 \(e^{\epsilon}\) 배 확률 차이 조건 외에도, 데이터베이스의 출력 분포 차이에 대해 작은 추가적인 오차 \(\eta\) 를 허용하는 방식이다.
저자의 변환 기법은 어떤 진실하고 효율적인 메커니즘을 \((\epsilon, \eta)\)-차등 개인정보 보호를 만족하면서도 진실하고 \(\delta\)-효율적인 메커니즘으로 변환한다.
여기서 \(\delta는 \epsilon, \eta\)에 따라 결정되는 추가적인 근사 오차(additive approximation error) 이다.
정확한 정의는 3장에서 논의한다.
이 변환 기법을 통해, 비자명한(non-trivial) 게임에서 최초의 PTE 메커니즘을 제시한다.
또한, 변환 기법은 계산 효율성(computational efficiency)과 비금전성(moneylessness) 등의 속성을 보존하며, 유형 공간이 작은 모든 게임에 적용 가능하다.
따라서, 이 변환 기법을 VCG 메커니즘에 적용하면, 유형 공간이 작은 모든 사회적 복지 게임(social welfare games)에 대한 PTE 메커니즘을 얻을 수 있다.
이 논문 전반에서, 저자는 다음과 같은 가정을 사용한다.
- 각 사용자의 효용 함수(utility function)는 [-1,1] 범위 내에 존재한다.
- 글로벌 효용 함수(global utility function)는 [-n, n] 범위 내에 존재한다.
특히, \(\delta = o(n)\)을 만족하는 \(\delta\)-효율적인 메커니즘을 얻는 것이 중요하다.
The transformation.
변환 방법의 아이디어는 히스토그램 데이터를 비공개로 공개하는 기법 [11]에서 착안되었다.
게임의 유형 공간(type space)이 크기 q인 유한 집합이라고 가정하자.
플레이어 입력을 \(t = (t_1, …, t_n)\)이라 하고, 여기서 \(t_i\)는 i번째 플레이어의 유형이라고 하자.
이제 히스토그램 h를 정의하는데, 이는 q개의 항목을 가지며, \(h_j = |\{i | t_i = j\}|\)는 각 유형에 대해 해당 유형을 가진 플레이어의 수를 나타낸다.
각 플레이어의 효용 함수 v(t,s)를 가정하자. 여기서 t는 플레이어의 유형, s는 게임의 결과이다.
또한, 효용 함수 v는 [-1,1] 범위 내에 있다고 가정하자.
글로벌 효용 함수 w(t,s)가 익명적(anonymous) 이며, 즉 히스토그램 h에만 의존하고 개별 플레이어의 정체성에는 의존하지 않는다고 가정하자.
또한, w는 민감하지(insensitive) 않다고 가정한다.
즉, 두 히스토그램 \(h, h{\prime}\)이 \(\ell_1\) 거리에서 가깝다면, 모든 결과 s에 대해 \(|w(h,s) – w(h{\prime},s)|\)가 작다.
예를 들어, 사회적 복지 함수(social welfare function)는 모든 개별 플레이어의 효용 합으로 정의되며, 이러한 글로벌 효용 함수의 한 가지 예시가 된다.
일반성을 잃지 않고, 이러한 글로벌 효용 함수를 가지는 게임에 대한 모든 메커니즘은 개별 플레이어의 유형이 아닌 플레이어 유형의 히스토그램에만 의존하면 충분하다.
이 사실은 부록 A에서 증명된다.
상위 개념에서, 저자의 변환 방법은 진실하고 효율적인 메커니즘을 PTE 메커니즘으로 변환하는 방식으로 작동한다.
- 입력 데이터의 히스토그램을 구성한다.
- 각 히스토그램 항목에 대해 독립적으로, 양쪽 기하 분포(two-sided geometric distribution)를 따르는 노이즈를 추가한다.
- 변형된(perturbed) 히스토그램을 사용하여 원래의 진실하고 효율적인 메커니즘을 실행한다.
그러나, 노이즈 추가 과정에서 히스토그램의 값이 음수가 되지 않도록 주의해야 한다.
단순히 음수를 0으로 절단(truncate)하는 방식은 진실한 메커니즘을 보장하지 못한다.
이에 대한 해결 방법은 4장에서 논의된다. 저자의 절차를 통해 다음 정리를 얻는다.
정리 2.2 (비공식). \(\epsilon, \eta > 0\)라 하자.
게임 G 는 유형 공간의 크기가 q이며, 글로벌 효용 함수가 히스토그램에만 의존하고 개별 플레이어의 유형에 대해 민감하지 않다고 가정하자.
M 이 진실하고 \(\delta\)-근사적으로 효율적인 메커니즘이라 하자.
그러면, 게임 G 에 대해 \(\epsilon, \eta\)-차등 개인정보 보호를 만족하며, \(\delta^{\prime}\)-근사적으로 효율적인 진실한 메커니즘 \(M{\prime}\)이 존재한다. 여기서 \(\delta^{\prime} \approx \delta\)이다.
또한, M이 계산적으로 효율적(computationally efficient)이라면, \(M^{\prime}\)도 그렇다.
M 이 비금전적(moneyless)이라면, \(M^{\prime}\)도 비금전적이다.
PTE mechanism for all social welfare games with small type space.
VCG 메커니즘은 모든 사회적 복지 게임에서 진실성을 만족하며 완전히 효율적인(perfectly efficient) 메커니즘을 제공한다.
즉, 개별 플레이어의 효용 합을 최적화하는 게임에서 사용될 수 있다. 따라서, 저자의 주요 정리는 다음을 함의한다.
추론 2.4. \(\epsilon, \eta > 0\)를 고정하자. n 명의 플레이어를 가지며, 유형 공간의 크기가 q 이고, 목표가 사회적 복지를 최적화하는 게임 G 에 대해, 다음 조건을 만족하는 진실한 메커니즘이 존재한다.
\((\epsilon, \eta)\)-차등 개인정보 보호를 만족한다.
\(O(q \log(q/\eta) / \epsilon)\)-근사적으로 효율적이다.
2.3. The value of privacy
이전 연구는 개인정보 보호와 유용성(utility)을 독립적인 요소로 취급해왔다.
예를 들어, 앞에서 저자는 차등 개인정보 보호를 만족하면서도 진실성을 유지하는 효율적인 메커니즘이 가능함을 보였다.
그러나 참여자가 실제로 개인정보 보호를 가치 있게 여긴다고 가정한다면, 이러한 고려가 개인의 효용 함수(utility function)에 명시적으로 반영되어야 한다.
이러한 접근 방식은 두 가지 장점을 제공한다.
- 개인정보 보호에 대한 참여자의 가치 평가를 정량화할 수 있다.
- 유용성과 개인정보 보호 간의 상충 관계(trade-off)를 모델링할 수 있다.
즉, 참여자는 자신의 유형을 거짓으로 보고함으로써 일부 유용성을 포기하고 개인정보 보호를 강화할 수도 있다.
반대로, 개인정보 보호를 일부 희생하면 게임의 결과에서 더 큰 유용성을 얻을 수 있기 때문에 그렇게 선택할 수도 있다.
저자는 PTE 메커니즘조차도 진실성을 유지하기 위해 너무 많은 정보를 유출할 가능성이 있음을 보일 것이다.
2.3.1. Quantifying privacy
첫 번째 과제는 메커니즘이 얼마나 많은 정보를 유출하는지 측정하는 방법을 정의하는 것이다.
자연스러운 조건 중 하나는, 플레이어가 자신의 실제 유형과 독립적인 유형을 보고할 경우, 정보 비용(information cost)이 0이 되어야 한다는 것이다.
이유는, 출력된 메커니즘 결과가 플레이어의 유형에 대한 정보를 포함하지 않으면, 그의 개인정보 보호가 침해되지 않기 때문이다.
이 기준을 만족하려면, 정보 비용은 단순히 플레이어의 유형과 게임의 결과만을 기반으로 정의될 수 없다.
왜냐하면, “정직한 유형과 독립적”이라는 개념은 특정 유형에서의 행동이 아니라, 모든 가능한 유형에 대한 플레이어의 행동을 기반으로 정의되기 때문이다.
사고 실험(thought experiment)으로, 어떤 유형 t 가 고정되어 있다고 가정하고, 다음 두 가지 전략을 고려하자.
- 진실한 전략(truthful strategy): 플레이어가 자신의 실제 유형을 보고하는 경우.
- 상수 t 전략(constant t strategy): 플레이어가 자신의 실제 유형과 관계없이 항상 t 를 보고하는 경우.
만약 플레이어의 실제 유형이 t 인 경우, 두 전략은 동일한 출력을 생성하지만, 직관적으로 진실한 전략은 플레이어의 유형에 대한 정보를 노출할 가능성이 있는 반면, 상수 t 전략은 그렇지 않다.
따라서, 정보 비용을 전통적인 효용 함수의 변형 형태로 표현할 수 없다.
즉, 정보 비용은 단순히 플레이어의 유형과 게임의 결과만으로 결정되는 것이 아니라, 모든 가능한 유형에 대한 플레이어의 전략을 기반으로 해야 한다.
저자는 \(ICM(\sigma, t, i)\)를 정의하는데, 이는 메커니즘 M 이 주어진 상태에서, 플레이어 i 가 전략 \(\sigma\)를 사용했을 때 발생하는 정보 비용을 의미한다.
전략 \(\sigma\)는 유형에서 유형 분포로의 함수로 정의되며, 즉, 플레이어 i 의 실제 유형이 t 일 때, 그가 전략 \(\sigma\)를 사용하면, 일정한 확률에 따라 \(t{\prime} \sim \sigma(t)\)를 샘플링하고, 이를 메커니즘에 보고한다.
일반적으로 정보 비용은 특정한 응용(application)에 따라 달라질 수 있다.
따라서 저자는 특정한 정보 비용 함수를 고정하지 않고, 다음과 같은 가정을 만족하는 어떠한 정보 비용 함수에 대해서도 결과가 성립함을 보일 것이다.
플레이어는 자신의 데이터를 숨길 수 있어야 한다:
어떤 전략 \(\sigma\)가 입력과 독립적인 경우(즉, 모든 \(t, t{\prime}\)에 대해 \(\sigma(t) = \sigma(t{\prime}\)) 를 만족하는 경우),
모든 i, t 에 대해 정보 비용 \(ICM(\sigma,t,i)\)는 0이 되어야 한다.
즉, 플레이어가 자신의 실제 유형과 무관하게 동일한 유형을 보고하는 전략을 사용할 경우, 그의 유형이 정보 비용에 영향을 미쳐서는 안 된다.
정보 비용은 차등 개인정보 보호를 반영해야 한다:
대략적으로, 만약 메커니즘 M 이 \(\epsilon\)-차등 개인정보 보호를 만족하는 최소한의 값 \(\epsilon\)이 존재한다고 하면,
정보 비용은 \(\epsilon\)보다 크게 감소할 수 없어야 한다.
즉, 차등 개인정보 보호 수준 \(\epsilon\)이 높을수록, 정보 비용도 일정 수준 이상이어야 한다는 것을 의미한다. 이 조건은 차등 개인정보 보호가 정보 유출을 얼마나 제한하는지를 반영하는 역할을 한다.
References
Xiao, David. “Is privacy compatible with truthfulness?.” Proceedings of the 4th conference on Innovations in Theoretical Computer Science. 2013.