Abstract
기계적 설계(Mechanism Design)는 자기 이익을 추구하는 행위자들이 실행하는 분산 알고리즘을 다루는 학문이다. 메커니즘 설계자의 목표는 행위자의 개인적인 유형과 관련된 어떤 함수를 최적화하는 것이다. 이를 위해서는 행위자들의 인센티브를 고려한 계산을 설계해야 하며, 이는 반드시 메커니즘의 목표와 일치하는 것은 아니다. 전통적으로 메커니즘은 행위자들이 메커니즘 결과로부터 얻는 효용만을 고려하여 설계되었으며, 이 과정에서 행위자의 개인적인 정보를 완전히 또는 부분적으로 공개하는 것이 일반적이었다. 그러나 행위자가 프라이버시를 중요하게 생각하는 경우, 즉 프라이버시 손실이 자신의 효용에 부정적인 영향을 미치는 경우, 이러한 전통적인 메커니즘은 적절하지 않을 수 있다. 이런 경우, 메커니즘 설계 과정에서 프라이버시 인식을 고려하지 않으면, 해당 메커니즘은 인센티브 호환적이지 않을 수 있으며, 따라서 비효율적일 수 있다. 흥미롭게도, 다소 직관에 반하는 연구 결과로 Xiao(2011)는 강한 프라이버시 개념을 보장하는 메커니즘에서도 이러한 문제가 발생할 수 있음을 보였다.
우리는 프라이버시를 고려하는 행위자를 위한 메커니즘을 구축하기 위해, 프라이버시를 고려한 메커니즘 설계 모델을 제안하고 그 타당성을 설명한다. 이후, 프라이버시를 고려한 메커니즘이 실현 가능함을 보인다.
주요 기여
1. 프라이버시를 고려한 행위자 모델링 (Modeling privacy-aware agents)
우리는 프라이버시를 고려하는 행위자를 위한 새로운 모델을 제안한다. 이 모델에서는 행위자가 자신의 프라이버시 손실이 효용에 미치는 영향을 완전히 파악할 필요 없이, 보수적인 상한선만 가지면 충분하다. 이러한 접근법은 기존 모델들과 차별되며, 기존 연구에서는 프라이버시 손실이 미치는 영향을 완전히 규명해야만 진실성을 보장할 수 있었다.
2. 프라이버시 가치의 프라이버시 보호 (Privacy of the Privacy Loss Valuations)
행위자의 프라이버시 가치는 그 자체로도 민감한 정보일 수 있다. 우리가 제안하는 프라이버시를 고려한 메커니즘은 이러한 프라이버시 가치가 유출됨으로 인해 발생하는 효용 손실까지 고려한다.
3. 높은 프라이버시 가치를 가진 행위자에 대한 보장 (Guarantees for Agents with High Privacy Valuations)
행위자가 임의적으로 높은 프라이버시 가치를 가질 수 있다면, 인센티브 호환성(incentive compatible)을 보장하는 것은 불가능하다. 따라서, 우리는 메커니즘이 특정 임계값을 설정하여, 이 값을 넘지 않는 행위자에 대해서만 인센티브 호환성을 보장하고, 나머지 행위자들에 대해서는 ε-차등 프라이버시를 보장하는 방식을 채택한다.
4. 프라이버시를 고려한 메커니즘 구축 (Constructing privacy-aware mechanisms)
우리는 먼저 간단한 투표 문제를 해결하는 프라이버시를 고려한 메커니즘을 구축한 후, 이를 확장하여 보다 일반적인 메커니즘을 설계한다. 이 과정에서, Nissim, Smorodinsky, Tennenholtz(2012)의 근사적 덧셈 메커니즘 결과를 기반으로 하여, 프라이버시를 고려하는 행위자들을 포함한 모델을 설계한다. 또한, 프라이버시 가치 분포에 대한 가벼운 가정(즉, 대부분의 인구가 유한한 범위 내에서 프라이버시 가치를 가진다는 가정) 하에서, 우리가 제안하는 메커니즘은 거의 모든 행위자에게 인센티브 호환성을 제공하며 최적의 결과에 가까운 성능을 보장한다. 마지막으로, 우리는 이 일반적인 메커니즘을 디지털 상품의 프라이버시를 고려한 판매 문제에 적용하는 방법을 제시한다.
Key Words and Phrases: Privacy, Mechanism Design, Differential Privacy
1. Introduction
기계적 설계(Mechanism Design)는 자기 이익을 추구하는 행위자들이 실행하는 분산 알고리즘을 다루며, 메커니즘 설계자는 행위자의 개인적인 입력(유형)을 기반으로 특정 함수를 계산하려 한다. 전통적으로 행위자들은 메커니즘의 결과로 얻는 효용만을 고려하고 프라이버시는 신경 쓰지 않는다고 가정되었으나, 프라이버시 손실이 효용에 부정적인 영향을 미치는 경우 이러한 접근 방식은 적절하지 않을 수 있다.
기존 연구들은 차등 프라이버시를 활용해 진실성을 보장하는 메커니즘을 구축했으나, 행위자의 프라이버시 가치 자체를 보호하지 않는 한계를 가졌다. Xiao(2011)는 차등 프라이버시와 진실성이 결합되었음에도, 프라이버시를 고려하는 행위자들에게는 진실성이 항상 보장되지 않을 수 있음을 보였고, Ghosh와 Roth(2011)는 프라이버시 손실을 보상하는 메커니즘을 제안했지만, 행위자의 프라이버시 가치 자체를 보호하지 못하는 문제가 있었다.
Ghosh and Roth (2011)의 연구 결과에 따르면, 참여자의 프라이버시 평가 정보가 공개됨으로 인해 발생하는 정보 손실(disutility)을 보상하는 것을 불가능하다. 즉, 프라이버시 평가 \(v_i\) 자체가 노출될 가능성이 있는 경우, 이를 보상하는 개별 합리적(individually rational) 메커니즘은 존재할 수 없다.
다만, 프라이버시 평가 \(v_i\)가 상한선을 가지는 경우에는 보상이 가능할 수 있다.
본 연구는 기존 메커니즘이 다루지 않았던 프라이버시 가치 자체까지 보호하는 메커니즘을 구축하는 것을 목표로 한다. 그러나 개별적으로 합리적인 수준에서 프라이버시 가치의 유출로 인한 정보 손실을 완전히 보상하는 것은 불가능하기 때문에, 우리는 대규모 행위자 집단(large populations of agents)을 대상으로 하는 메커니즘을 고려한다. 즉, 프라이버시 손실을 보상하는 대상을 한정하여 프라이버시 가치가 일정 임계값 이하로 제한된 행위자들에게만 보상을 제공하고, 프라이버시 가치가 너무 높아 메커니즘이 보상할 수 없는 임계값을 초과하는 행위자들에 대해서는 ε-차등 프라이버시를 적용하여 보호하는 방식을 제안한다.
이때 행위자 집단의 크기가 증가할수록 임계값도 증가하며, 차등 프라이버시 매개변수 ε 값은 감소하여 강한 프라이버시 보호를 제공할 수 있도록 설계된다. 즉, 충분히 큰 집단에서는 대부분의 참여자가 보상을 받을 수 있게 된다.
1.1. Our Contributions
1. 프라이버시를 고려한 메커니즘 모델링
본 연구의 주요 기여 중 하나는 기존 모델의 한계를 보완한 새로운 프라이버시를 고려한 메커니즘 설계 모델을 제안하는 것이다. 우리의 모델에서 행위자는 기존의 게임 이론적 유형(game type)과 프라이버시 유형(privacy type)을 함께 가지며, 프라이버시 유형에 대해서는 프라이버시 손실이 효용에 미치는 영향을 보수적인 상한선으로만 평가할 수 있다.
이 모델에서는 참여자가 두 가지 유형의 정보를 가지고 있다고 가정한다:
- 전통적인 게임 이론적 타입(traditional game type)
- 프라이버시 타입(privacy type)
행위자는 자신의 게임 유형과 프라이버시 유형이 유출되는 것 모두에 대해 효용 감소를 경험할 수 있으며, 이는 기존 연구(Ghosh and Roth, 2011)에서 정보 효용(information utilty)을 완전히 규명해야만 진실성을 보장할 수 있었던 접근 방식과 차별된다.
기존 메커니즘들은 프라이버시 타입에 대한 정보 비용(information cost)을 고려하지 않았다.
이에 반해, 본 논문에서는 참여자의 프라이버시 손실이 효용에 미치는 영향을 보수적인 상한선(conservative upper bound)으로 설정하는 방식을 제안한다. 즉, 참여자는 프라이버시 손실이 자신의 효용을 얼마나 감소시키는지 정확히 알 필요 없이, 어느 정도 상한선만 설정하면 된다.
행위자가 임의적으로 높은 프라이버시 가치를 가질 수 있다면, 계산 결과에 따라 유출되는 정보 효용을 사전에 제한하는 것이 불가능하다. 이를 해결하기 위해, 우리는 프라이버시 가치의 임계값 \(v_{\max}\)과 프라이버시 보호 매개변수 ε을 설정하여, \(v_{\max}\) 이하의 행위자들에게는 인센티브 호환성을 보장하고, 모든 행위자들에게는 ε-차등 프라이버시를 보장하는 방식을 채택한다.
2. 프라이버시를 고려한 메커니즘 구축
이후, 우리는 프라이버시를 고려한 메커니즘이 실제로 실현 가능함을 보인다. 첫 번째 결과로, 2개 이상의 대안 중 하나를 선택하는 단순한 투표(polling) 문제에서 프라이버시를 고려한 메커니즘을 구축한다. 여기서 핵심 아이디어는 정보 유출에 대한 효용 손실보다 잘못된 응답으로 인한 효용 손실이 더 크게 만들어 진실성을 유지하도록 설계하는 것이다.
- 프라이버시 가치가 \(v_{\max}\) 이하인 행위자: 프라이버시 손실에 대해 적절한 보상을 제공한다.
- 프라이버시 가치가 \(v_{\max}\)을 초과하는 행위자: 프라이버시 가치를 보호하기 위해 ε-차등 프라이버시를 적용한다.
이 접근 방식은 프라이버시 손실을 완전히 보상하는 것이 불가능하기 때문에 달성할 수 있는 최선의 해결책이라고 할 수 있다. 이후, 우리는 대규모 인구 집단(large population)으로 확장하여, 프라이버시 가치 분포가 특정한 조건(예: 유한한 모멘트(finiteness of moments)를 가진 경우)을 만족할 때, 보다 일반적인 메커니즘을 구축할 수 있음을 보인다.
3. 일반적인 프라이버시를 고려한 메커니즘의 구축
5장에서는 프라이버시를 고려한 메커니즘의 일반적인 구축 방법을 제시한다. 이 과정에서, Nissim et al. (2012)의 일반적인 메커니즘 설계 기법을 기반으로, 프라이버시를 고려하는 행위자들을 포함하도록 메커니즘을 수정 및 분석한다. 이 메커니즘은 대부분의 행위자들에게 진실성을 보장하며, 정확도 또한 일정 수준 이상 유지할 수 있도록 설계되었다.
이후, 5.2절에서는 우리의 프레임워크에 적합한 프라이버시를 고려한 디지털 상품 판매 문제를 사례로 제시한다.
4. 프라이버시를 고려한 메커니즘이 진실성을 보장할 수 있는 조건
우리는 일반적인 진실한(truthful) 메커니즘이 개별 입력값에 민감하지 않은 경우(즉, 대규모 인구 집단에서 개별 행위자의 기여도가 낮은 경우), 대부분의 프라이버시를 고려하는 행위자들이 진실하게 보고하는 것이 합리적임을 보인다. 이는 잘못된 응답으로 인해 감소하는 효용이 정보 유출로 인한 효용 손실보다 크기 때문이다.
즉, 개별 행위자의 정보 유출이 미치는 영향이 작을수록, 프라이버시를 고려하는 행위자들도 진실하게 응답할 가능성이 높아진다.
프라이버시 평가가 임의로 높을 경우의 문제
만약 참여자의 프라이버시 평가가 임의로 높을 수 있다면, 메커니즘의 결과가 참여자의 개인 입력 또는 참여 여부에 따라 결정되는 경우, 정보 효용을 사전에 제한하는 것이 불가능하다.
이러한 문제는 특히 개인 정보 판매를 위한 진실한(truthful) 메커니즘 설계에서 중요한 이슈이며, Ghosh and Roth(2011)에서도 이에 대한 자세한 논의가 이루어졌다.
해결책: 프라이버시 임계값 및 DP 적용
이러한 근본적인 문제를 해결하기 위해, 본 논문에서는 보다 완화된 조건(lesser requirement)을 제시한다.
1. 메커니즘이 프라이버시 평가의 최대 임계값 \(v_{max}\)를 설정해야 한다.
즉, 프라이버시 평가가 \(v_{max}\) 이하인 경우에만 유인 호환성을 보장한다.
2. \(v_{max}\)를 초과하는 참여자에 대해서는 \(\epsilon\)-DP를 제공한다.
즉, 그들의 프라이버시 평가가 \(v_{max}\)를 초과하는지 여부 자체가 노출되지 않도록 보호한다.
이를 통해, 대부분의 참여자들에 대해서는 유인 호환성을 유지하면서도, 특정 참여자의 프라이버시가 너무 민감할 경우에는 DP를 활용하여 보호하는 전략을 적용할 수 있다.
Other Related Work
암호학 분야에서도 “프라이버시를 보호하는 메커니즘 설계(privacy-preserving mechanism design)“에 대한 연구가 진행되어 왔으며, 대표적인 예로 Naor et al.(1999)이 있다. 그러나 우리의 연구 목표는 이러한 암호학적 접근과는 다르다. 본 연구에서 행위자들은 메커니즘의 공개 결과가 자신의 유형(type)과 프라이버시 가치(privacy valuation)에 대해 어떤 정보를 유출할지 걱정하는 반면, 암호학적 메커니즘 설계는 메커니즘의 결과를 제외한 모든 정보를 숨기는 것을 목표로 한다.
Miltersen et al.(2009)의 연구는 인터넷과 같은 네트워크 환경에서 암호학을 활용해 메커니즘을 구현하는 것이 단순하지 않은 작업이며, 이를 구현할 때에도 메커니즘의 본래 속성(예: 진실성)이 보존되는지 확인해야 한다는 점을 지적하고 있다.
한편, Chen et al.(2011)은 본 연구와 독립적으로, 프라이버시를 고려하는 행위자가 존재하는 환경에서 진실한 메커니즘을 연구했다. Chen et al.(2011)과 우리의 연구는 모두 프라이버시 손실을 계량화하는 방식이 행위자의 입력이 메커니즘 결과에 미치는 영향으로 정의된다는 점에서 유사한 동기를 가진다. 그러나 Chen et al.(2011)의 모델에서는 행위자가 결과별로 프라이버시에 가치를 부여하는 반면, 우리의 모델에서는 행위자의 프라이버시 가치가 메커니즘의 전체적인(즉, 최악의) 결과에 의해 결정된다고 가정한다.
두 접근법 모두 타당한 동기를 가지며, 우리의 접근법은 약한 가정을 기반으로 더 강건한 메커니즘을 도출할 가능성이 있고, 결과별 접근 방식은 더 다양한 프라이버시 보호 메커니즘을 개발하는 데 유리할 수 있다.
Preliminaries
유형 집합(type set) T 와 사회적 대안 집합(social alternatives set) S 을 정의한다. 즉, T 는 행위자(agent)의 유형(type)들이 속하는 이산적인 집합이며, S 는 메커니즘의 결과로 선택될 수 있는 대안들의 집합이다.
두 개의 벡터 \(t, t^{\prime} \in T^n\) 에 대해, 해밍 거리(Hamming distance) 는 두 벡터가 서로 다른 위치의 개수로 정의된다. 즉, \(| \{ i : t_i \neq t^{\prime}_i \} |\)를 해밍 거리라고 한다. 해밍 거리가 1인 벡터 쌍을 “이웃(neighboring)”이라고 한다.
메커니즘 \(M : T^n \to \Delta(S)\) 은 입력 벡터 \(t \in T^n\) 에 대해, 사회적 대안 집합 S 에 대한 확률 분포를 반환하는 함수이다. 여기서 \(\Delta(S)\) 는 집합 S 위의 확률 분포의 집합을 의미한다. 즉, 메커니즘 M 은 특정 입력 벡터 t 가 주어졌을 때, 확률적으로 S 내의 어떤 요소를 결과로 선택한다. 또한, \(M(t)(S^{\prime})\) 는 메커니즘 M 이 입력 t 에 대해, 특정 부분집합 \(S^{\prime} \subseteq S\) 를 출력할 확률을 의미한다.
차등 프라이버시는 주어진 행위자의 유형을 포함한 입력이 변경되었을 때, 메커니즘의 결과 분포가 얼마나 영향을 받는지를 측정하는 매우 보수적인 기준이다. 이는 다른 행위자의 모든 유형이 알려져 있더라도, 개별 행위자의 정보가 유출되는 위험을 제한하는 강력한 보호 메커니즘이다.
정의 2.1 (차등 프라이버시, Differential Privacy [Dwork et al., 2006])
메커니즘 \(M : T^n \to \Delta(S)\) 이 ε-차등 프라이버시를 만족한다는 것은, 모든 이웃 관계인 \(t, t^{\prime} \in T^n\) 와 모든 측정 가능한 부분집합 \(S^{\prime} \subseteq S\) 에 대해 다음이 성립하는 것을 의미한다.
\(M(t)(S{\prime}) \leq e^{\epsilon} \cdot M(t{\prime})(S{\prime})\)
즉, 메커니즘이 특정 입력 벡터 t 를 받았을 때 특정 결과 \(S^{\prime}\) 가 선택될 확률과, 이웃하는 입력 \(t^{\prime}\) 에 대해 같은 결과가 선택될 확률이 \(e^{\epsilon}\) 배 이내로 유지됨을 보장한다.
레마 2.2 (차등 프라이버시가 기대값에 미치는 영향)
차등 프라이버시 정의로부터 직접적으로 유도할 수 있는 결과는 다음과 같다.
메커니즘 \(M : T^n \to \Delta(S)\) 이 ε-차등 프라이버시를 만족한다고 가정하자. 함수 \(g: S \to \mathbb{R}_{\geq 0}\) 에 대해, 모든 이웃 관계인 \(t, t^{\prime} \in T^n\) 에 대해 다음이 성립한다.
\(E_{s \sim M(t)} [g(s)] \leq e^{\epsilon} \cdot E_{s \sim M(t^{\prime})} [g(s)]\)
특히, 만약 \(\epsilon \leq 1\) 이고 \(g: S \to [0,1]\) 인 경우,
\(E_{s \sim M(t)} [g(s)] – E_{s \sim M(t^{\prime})} [g(s)] < 2\epsilon\)
이 성립한다.
즉, 차등 프라이버시를 만족하는 메커니즘에서는, 입력이 바뀌더라도 기대값의 변화가 제한됨을 보장한다.
3. Quantifying Information Utility
우리의 모델은 기존의 기계적 설계(Mechanism Design) 모델과 유사하지만, 메커니즘에 참여하는 행위자들이 프라이버시에 대한 효용을 고려한다는 점에서 차이가 있다.
일반적인 기계적 설계 모델에서는,
- 행위자의 유형 \(t_i\) 는 상품의 가치(valuation), 위치(location) 등의 정보를 포함한다.
- 메커니즘은 대안 s 를 선택하며,
- 행위자의 효용(utility) 함수는 \(t_i\) 와 s 의 함수로 정의된다(경우에 따라 금전적 보상 포함).
프라이버시를 고려하는 행위자(privacy-aware agents)의 경우, 기존 효용 함수에 정보 유출로 인한 비효용(dis-utility), 즉 정보 효용(information utility) 을 추가해야 한다. 이때, 정보 유출을 어떻게 정량화할 것인가? 가 첫 번째 문제로 등장한다.
- 각 행위자는 프라이버시에 대한 선호도가 다를 수 있기 때문에, 정보 유출을 정량화할 때 행위자의 프라이버시 선호도를 반영해야 한다.
- 각 행위자의 프라이버시 선호도를 \(v_i\) 로 정의하며, 따라서 행위자의 유형(type)은 기존 유형 \(t_i\) 와 프라이버시 선호도 \(v_i\) 를 포함하는 확장된 형태가 된다.
- 메커니즘이 선택하는 대안 s 는 \(t_i\) 뿐만 아니라 \(v_i\) 에 대한 정보도 유출할 수 있으므로, \(v_i\) 에 대한 정보 유출 또한 고려해야 한다.
기존 연구에서 정보 효용을 정량화하는 방법
1. McGrew et al.(2003)의 모델
비협력적 컴퓨팅(Non-Cooperative Computing, NCC) 맥락에서 프라이버시를 효용 함수에 포함한 초기 연구이다. 행위자들은 다른 행위자가 자신의 개인 유형을 100% 확실하게 아는 경우에만 정보 유출을 걱정한다. 즉, 프라이버시는 완전히 보호되거나(정보 유출 없음), 완전히 노출되거나(정보 유출 존재) 두 가지 상태만 존재한다. 따라서, 정보 유출 효용은 다음과 같이 이진적으로 정량화된다.
- 정보 유출 없음 → 효용 손실 없음 (0)
- 정보 유출 발생 → 효용 손실 (\(v_i\) > 0)
- 하지만 현실에서는 정보가 부분적으로 유출될 가능성이 높기 때문에, 이진적 모델은 적절하지 않다.
2. Ghosh와 Roth(2011)의 모델
데이터 분석가가 ε-차등 프라이버시를 보장하는 통계를 계산할 때, 데이터 제공자에게 프라이버시 손실을 보상하는 환경을 고려하였다.
이 연구에서는, 행위자의 정보 유출로 인한 비효용이 차등 프라이버시 매개변수 ε 에 비례한다고 가정한다.
\(u_i^{\text{inf}} = v_i \cdot \epsilon\)
여기서 \(v_i\) 는 행위자의 프라이버시 가치이며, \(\epsilon\) 값이 클수록(즉, 프라이버시 보호가 약해질수록) 정보 유출로 인한 비효용이 커진다.
그러나 이 접근 방식에는 몇 가지 문제점이 있다.
\(\epsilon\) 은 최악의 경우(worst-case) 프라이버시 손실을 측정하는 값이므로, 실제 평균적인 프라이버시 손실은 훨씬 작을 수 있다(Dwork et al., 2010).
또한, 행위자 i 의 정보 유출은 다른 행위자들의 입력 값에도 의존할 수 있다.
이 모델은 행위자의 프라이버시 선호도 \(v_i\) 자체가 유출될 수 있는 문제를 고려하지 않는다.
→ 정보 유출 비효용이 차등 프라이버시 매개변수 \(\epsilon\) 에 비례한다고 가정하지만, 실제 프라이버시 손실은 평균적으로 더 작을 수 있으며, 행위자의 프라이버시 가치 \(v_i\) 자체가 유출될 위험을 고려하지 않는다.
3. Xiao(2011)의 모델
본 연구와 유사하게, 프라이버시를 고려한 기계적 설계 모델을 연구하였다.
정보 유출 비효용을 다음과 같이 정량화하였다.
\(u_i^{\text{inf}} = v_i \cdot I(t_i; M(t_{-i}, \sigma(t_i)))\)
여기서 \(I(t_i; M(t_{-i}, \sigma(t_i)))\) 는 행위자 i 의 유형 \(t_i\) 가 메커니즘 M 의 결과를 통해 얼마나 많은 정보가 유출되는지를 나타내는 상호 정보(mutual information) 를 의미한다.
즉, \(v_i\) 가 클수록 정보 유출에 대한 비효용이 커지고, 행위자의 전략 \(\sigma\) 도 영향을 미친다.
하지만 이 접근 방식에도 한계가 있다.
행위자의 정보 유출 비효용이 행위자의 전략 \(\sigma\) 에 의해 결정되는 것은 분석적으로 다루기 어려운 문제를 초래할 수 있다. 특정한 전략을 선택할 경우, 정보 유출의 영향을 완전히 제거하는 것이 불가능할 수 있다.
→ 행위자의 전략 \(\sigma\)에 의해 정보 유출의 정도가 달라질 수 있기 때문에, 분석적 어려움이 있다.
예제 3.1 (“호밀빵 또는 통밀빵” 게임, The “Rye or Wholewheat” game)
Alice는 Bob을 위해 샌드위치를 준비하면서, Bob이 호밀빵(R)과 통밀빵(W) 중 어떤 것을 선호하는지 묻는다.
Bob은 자신이 가장 좋아하는 샌드위치를 먹고 싶지만, Alice가 자신의 선호도를 알게 되는 것은 원하지 않는다.
이제 Bob의 유형(type)이 \(\{ R, W \}\)에서 균등하게 선택된다고 가정하고, Bob이 취할 수 있는 두 가지 전략을 살펴보자.
1. Bob이 자신의 실제 선호도를 제공하는 경우
이 경우, Bob은 좋아하는 샌드위치를 먹을 수 있다.
하지만, Alice는 Bob의 선호도를 정확히 알게 되므로 정보 유출 비효용이 최대화된다.
상호 정보량(mutual information)은 다음과 같다.
\(I(t_{\text{Bob}}; M(\sigma_{\text{truthful}}(t_{\text{Bob}}))) = 1\)
2. Bob이 무작위로 대답하는 경우
Bob은 50% 확률로 원하는 샌드위치를 받을 수 있다.
하지만, Bob의 응답이 실제 선호도와 무관하므로 프라이버시 손실이 전혀 발생하지 않는다.
즉, Alice는 Bob의 선호도를 전혀 유추할 수 없다.
상호 정보량은 다음과 같다.
\(I(t_{\text{Bob}}; M(\sigma_{\text{random}}(t_{\text{Bob}}))) = 0\)
중요한 점은 Bob의 유형(호밀 또는 통밀)이 균등 확률로 선택되므로, Alice의 관점에서 Bob의 행동 분포는 두 전략(진실한 응답 \(\sigma_{\text{truthful}}\) vs 무작위 응답 \(\sigma_{\text{random}}\))이 동일하게 보인다는 것이다.
즉, Bob이 어떤 전략을 사용하든 Alice가 결과를 보고 이를 구별할 수 없다.
하지만 정보 이론적 관점에서 보면, 두 전략 간 상호 정보량은 극명하게 차이가 나며, 이는 Alice가 Bob의 유형을 어느 정도 학습하는지 여부를 나타낸다.
이 문제의 핵심 원인
이 예제는 \(I(t_{\text{Bob}}; M(\sigma(t_{\text{Bob}})))\) 가 프라이버시를 측정하는 기준으로서 문제가 있을 수 있음을 보여준다.
다만, 이는 Bob이 무작위 전략 \(\sigma_{\text{random}}\) 을 사용했기 때문이 아니라, Alice가 Bob의 전략을 알지 못하기 때문이다.
즉, Alice가 Bob의 전략을 관찰할 수 없는 상황에서는, 무작위 전략 \(\sigma_{\text{random}}\) 을 사용할 필요 없이 단순한 진실 응답 \(\sigma_{\text{truthful}}\) 도 같은 결과를 만들 수 있다.
따라서, 정보 비용(information cost) 개념은 Alice가 Bob의 전략을 알고 있는지 여부와 무관하게 정의되어야 한다.
3.1. Our Approach
우리는 기존 연구들과 달리 새로운 정보 효용(information utility) 측정 방법을 제안하는 것이 아니라, 기존 방법보다 훨씬 약한 개념을 사용한다.
이를 설명하기 위해, 기존 연구에서 논의된 정보 효용 측정 방식을 다시 살펴보자.
1. 기존 연구에서의 정보 효용 한계점 분석
(1) Ghosh와 Roth(2011)의 모델: \(v_i \cdot \epsilon\)
차등 프라이버시(ε-differential privacy)를 보장하는 메커니즘에서는,
\(\frac{\Pr[M(t) = s]}{\Pr[M(t{\prime}) = s]} \leq e^\epsilon\)
가 모든 인접한 입력 \(t, t^{\prime}\) 및 출력 s 에 대해 성립한다.
하지만, 이 최악의 경우(worst-case)가 실제로 발생할 확률은 매우 낮을 가능성이 높다.
따라서, \(v_i \cdot \epsilon\) 이 정보 효용을 정확히 측정하는 값은 아닐 수 있지만, 정보 효용의 상한(upper bound)으로는 적절할 수 있다.
(2) Xiao(2011)의 모델: \(v_i \cdot I(t_i; M(t))\)
예제 3.1에서 논의된 문제를 피하려면, \(I(t_i; M(t)) \geq I(t_i; M(t_{-i}, \sigma(t_i)))\) 가 모든 전략 \(\sigma\) 에 대해 성립한다는 점을 활용해야 한다.
따라서, \(v_i \cdot I(t_i; M(t))\) 도 정보 효용의 상한으로 사용할 수 있다.
(3) 정보 유출의 최댓값이 차등 프라이버시와 연결됨
Observation 2에 따르면, \(I(t_i; M(t)) \leq \epsilon \log e\) 이므로, 결국 \(v_i \cdot \epsilon\) 이 가장 약한(느슨한) 상한 값이 된다.
따라서, 우리는 정보 효용의 상한을 \(v_i \cdot \epsilon\) 으로 사용하기로 한다.
2. 우리의 정보 효용 개념의 차별점
(1) Ghosh와 Roth(2011)과의 차이점
우리가 \(v_i \cdot \epsilon\) 을 정보 효용의 상한으로 사용하는 방식은 Ghosh와 Roth(2011)와 개념적으로 다르다.
- Ghosh와 Roth(2011): 정보 유출 비용을 이용하여 비진실(truthful)이 아닌 응답을 억제하는 데 사용한다.
- 우리의 접근법: 정보 유출을 진실성을 보장하는 논리적 근거로 사용하지 않는다.
(2) 레마 2.2와의 관계
레마 2.2에 따르면, 행위자가 자신의 정보 유출로 인해 미래의 효용이 감소할 가능성이 존재한다.
따라서, 정보 효용의 상한은 이러한 미래의 효용 손실을 반영해야 한다.
레마 2.2를 적용하면, 정보 유출은 다음과 같이 상한을 가질 수 있다.
\(\max_{t \in T^n} (e^\epsilon – 1) \cdot E_{s \sim M(t)} |G_i(s)| \approx \epsilon \cdot \max_{t \in T^n} E_{s \sim M(t)} |G_i(s)|\)
여기서 \(G_i(s)\) 는 행위자 i 의 미래 효용이 메커니즘 M 의 결과에 따라 어떻게 달라지는지를 나타내는 함수이다.
즉, \(v_i \cdot \epsilon\) 은 정보 유출로 인해 미래 효용이 감소하는 정도의 상한을 제공한다.
3. 프라이버시 보호 및 진실성 보장
(1) 기존 연구에서 \(v_i\) 의 프라이버시 보호 부족
Ghosh와 Roth(2011)의 연구에서 행위자의 프라이버시 가치 \(v_i\) 는 보호되지 않는다.
즉, 어떤 행위자가 프라이버시를 높게 평가하는지를 공개적으로 알 수 있으며, 이는 추가적인 정보 유출 문제를 초래할 수 있다.
또한, \(v_i\) 가 무한대로 설정될 수 있다면, 프라이버시 손실에 대한 보상을 제공하면서도 충분한 데이터를 구매하는 것이 불가능해진다.
(2) 우리의 메커니즘이 제공하는 해결책
우리는 \((t_i, v_i)\) 전체 유형에 대해 \(\epsilon\)-차등 프라이버시를 제공한다.
행위자 수 n 이 증가할수록 \(\epsilon\) 은 감소하여, 더 강력한 프라이버시 보호를 제공할 수 있다.
(3) 진실성을 유지하는 방법
모든 \(v_i \leq v_{\max}\) 를 만족하는 행위자에 대해, 진실성이 지배 전략(dominant strategy)이 되도록 보장한다.
여기서, \(v_{\max}\) 는 매우 약한 가정하에서도 n 이 증가할수록 함께 증가하도록 설정된다.
또한, n 이 증가할수록 \(v_i > v_{\max}\) 를 만족하는 행위자의 비율은 점점 감소한다.
4. The Model
1. 메커니즘 (The Mechanism)
사회적 대안(social alternatives) 집합 S 와 유형(Type) 집합 T 가 존재하며, n명의 행위자가 참여한다고 가정한다.
직접 선언 메커니즘(Direct revelation mechanisms) 을 고려하며, 이는 행위자들이 자신의 유형을 메커니즘에 직접 보고한 후, 메커니즘이 사회적 대안 \(s \in S\) 를 선택하고 공개하는 방식이다.
프라이버시 손실을 정확히 평가하기 위해, 행위자의 개별 유형 정보 및 금전적 보상 여부는 암호학적 기법 등을 활용하여 완전히 숨긴다고 가정한다.
2. 목적 함수 (The Objective Function)
설계자의 목표는 주어진 행위자의 실제 유형 t 에 대해 사회적 대안 s 를 선택하여 목적 함수 f(t, s) 를 최적화하는 것이다.
\(f : T^n \times S \to \mathbb{R}_{\geq 0}\)
여기서 f(t, s) 는 주어진 행위자 유형 t 에 대한 선택된 대안 s 의 효용을 나타내는 비음수(Non-negative) 함수이다.
함수 f 의 민감도(Sensitivity) \(\Delta f\) 는 다음과 같이 정의된다.
\(\Delta f = \max | f(\hat{t}, s) – f(\hat{t}^{\prime}, s) |\)
여기서 최대값은 모든 이웃하는 유형 벡터(neighboring type vectors) \(\hat{t}, \hat{t}^{\prime} \in T^n\) 및 \(s \in S\) 에 대해 계산된다.
또한, 모든 s 에 대해 최소값이 0이라고 가정하며, 이에 따라 f(t, s) 값의 범위는 다음과 같이 제한된다.
\(f(t, s) \in [0, n \Delta f]\)
3. 프라이버시를 고려하는 행위자 (Privacy-Aware Agents)
기존 자기 이익을 추구하는 행위자(selfish agents) 모델을 확장하여, 행위자가 메커니즘의 결과에서 얻는 효용 \(u_i^{\text{out}}\) 뿐만 아니라, 정보 유출로 인해 발생하는 비효용(dis-utility) \(u_i^{\text{inf}}\) 도 고려하는 설정을 제시한다.
즉, 행위자의 총 효용은 다음과 같이 두 가지 요소의 합으로 정의된다.
\(u_i = u_i^{\text{out}} – u_i^{\text{inf}}\)
행위자의 유형 \(\tau_i\) 는 기존 유형 \(t_i\) 와 프라이버시 선호도 \(v_i\) 로 구성된 벡터 \(\tau_i = (t_i, v_i)\) 로 정의된다.
여기서 T 는 기존 유형 공간(traditional game type)이고, \(v_i\) 는 행위자가 자신의 프라이버시를 얼마나 중요하게 생각하는지를 나타내는 값이다.
행위자는 자신의 전체 유형 \((t_i, v_i)\) 에 대한 프라이버시를 걱정하며, 정보 유출은 \(t_i\) 와 \(v_i\) 두 가지 모두에 대해 발생할 수 있다.
따라서, 단순히 \(v_i\) 를 공개하는 것은 불가능하다.
모든 행위자들의 유형 벡터는 \(t = (t_1, \dots, t_n), v = (v_1, \dots, v_n)\) 로 나타낼 수 있다.
행위자는 자신의 효용을 극대화하기 위해 유형을 전략적으로 선언할 수 있으며, 이는 다음과 같이 표현된다.
\(\tau^{\prime}_i = \sigma_i(\tau_i) = (t^{\prime}_i, v^{\prime}_i)\)
4. 행위자의 효용 함수 정의
전통적인 게임 이론적 효용(Traditional Game Utility) \(u_i^{\text{out}}\) 는 다음과 같이 정의된다.
\(u_i^{\text{out}} : T \times S \to [-1,1]\)
정보 유출로 인한 비효용(Information Disutility) \(u_i^{\text{inf}}\) 는 다음과 같이 정의된다.
\(u_i^{\text{inf}} : \mathbb{R}{\geq 0} \to \mathbb{R}{\geq 0}\)
단, 다음과 같은 가정을 따른다.
\(u_i^{\text{inf}}(v_i) \leq v_i \cdot \epsilon\)
여기서 \(\epsilon\) 은 실행되는 차등 프라이버시 메커니즘의 매개변수로 정의되며,
\(e^\epsilon = \max \frac{M(t)(S)}{M(t^{\prime})(S)}\)
이 최대값은 모든 이웃하는 \(t, t^{\prime} \in T^n\) 및 \(S^{\prime} \subseteq S\) 에 대해 계산된다.
중요한 차이점은 \(u_i^{\text{out}}\) 는 단순히 메커니즘의 결과(선택된 s) 에만 의존하는 반면, \(u_i^{\text{inf}}\) 는 메커니즘 자체에도 의존한다는 점이다.
5. 참여하는 행위자(Participating Agents)와 근사 최적화
우리는 참여하는 행위자(participating agents)라는 개념을 정의하며, 이는 “진실한 응답(truthtelling)이 절대적으로 우월한 전략(strictly dominant strategy)“이 되는 행위자들의 부분집합이다.
메커니즘은 다음 조건을 만족할 때 f 를 근사적으로(approximately) 구현한다고 한다.
참여하는 행위자들이 진실하게 응답한다고 가정하고, 나머지 행위자들이 임의의 행동을 할 때, 메커니즘의 결과 s 가 f 를 근사적으로 최적화하는 경우.
5. A Generic Construction of Privacy-Aware Mechanisms
본 논문에서는 프라이버시를 고려한 메커니즘이 실제로 구현 가능함을 입증한다.
이를 위해, 먼저 간단한 투표 문제(pooling problem)를 통해 핵심 기법을 설명한 후, 보다 일반적인 프라이버시 보호 메커니즘을 구축하는 방법을 제시한다.
1. 간단한 프라이버시 보호 투표 메커니즘
여러 대안 중에서 선택하는 간단한 투표 문제를 고려한다.
1) 잘못된 응답(mis-reporting)으로 인해 발생하는 전통적인 비효용이 정보 효용을 압도하도록 설계한다.
즉, 참여자가 자신의 정보를 속여서 얻는 이득보다, 정직하게 응답하지 않았을 때 발생하는 손실이 더 크도록 조정한다.
이를 통해, 참여자가 자신의 정보를 속여서 얻는 이득보다, 정직하게 응답하지 않았을 때 발생하는 손실이 더 크도록 조정한다.
2) 프라이버시 평가에 따라 두 그룹으로 나눈다.
프라이버시 평가가 임계값 \(v_{max}\) 이하인 경우: 해당 참여자는 자신의 프라이버시 손실에 대해 공정한 보상을 받도록 메커니즘을 설계한다.
프라이버시 평가가 \(v_{max}\)를 초과하는 경우: 해당 참여자는 보상을 받을 수 없지만, 대신 그들의 프라이버시 평가 정보 자체를 \(\epsilon\)-DP 방식으로 보호한다.
이는 본 논문이 달성할 수 있는 최선의 해결책(best we can hope to achieve)이라고 할 수 있다.
2. 대규모 인구 집단을 위한 프라이버시 보호 메커니즘
참여자의 프라이버시 평가 분포가 특정한 통계적 특성을 만족한다고 가정한다.
이 가정하에서, 대부분의 참여자는 유인 호환성을 유지하면서도 정직하게 응답하는 것이 합리적인 선택이 된다.
이러한 접근 방식은 대규모 인구 집단에서는 개별 참여자의 데이터가 결과에 미치는 영향이 미미하기 때문이다.
즉, 개별 참여자의 입력이 결과에 미치는 영향이 작으면, 정보 유출에 따른 효용 감소보다, 정직한 응답을 했을 때 얻는 이득이 더 커질 가능성이 높다.
3.
References
Nissim, Kobbi, Claudio Orlandi, and Rann Smorodinsky. “Privacy-aware mechanism design.” Proceedings of the 13th ACM conference on electronic commerce. 2012.