Abstract
개인정보 보호에 대한 우려가 이기적인 효용 극대화 에이전트의 행동에 미치는 영향을 분석하는 문제는 최근 많은 관심을 받아왔다. 일부 경우에서 개인정보 보호를 고려하는 에이전트의 행동은 DP 보호를 보장하는 잘 알려진 메커니즘인 무작위 알고리즘의 틀을 따른다.
우리의 연구는 개인정보 보호 우려가 명시적으로 주어진 환경에서 에이전트의 행동을 보다 잘 이해하는 것을 목표로 한다.
장난감 모델을 고려하는데, 여기서 에이전트 A는 에이전트 B의 비밀 유형을 알아내려는 시도로 B에게 선물을 제공한다.
B가 자신의 유형을 비밀로 유지하려는 인센티브는 B의 효용 함수에 개인정보 보호를 고려하도록 ‘내재적으로 설정(hardwriting)’하는 방식이 아니라, B와 A 사이의 지불 형태로 나뉜다.
이에 세 가지 유형의 지불 함수를 조사하고, 각각의 게임에서 B의 행동을 분석한다.
분석 결과, 일부 지불 방식에서는 B의 행동이 내재적으로 개인정보 보호를 고려하는 에이전트와 매우 다르게 나타나며, 심지어 결정론적(deterministic)일 수도 있음을 보인다.
반면, 다른 지불 방식에서는 B의 균형 전략(Bayesian Nash Equilibrium, BNE)이 무작위 응답(Randomized Response) 체계에 속함을 증명한다.
1. Introduction
최근 개인정보 보호가 점점 더 중요한 문제로 부각됨에 따라, 경제적 효용을 극대화하는 에이전트(utility-maximizing agents)의 잠재적 개인정보 보호 우려에 대한 많은 연구가 이루어졌다.
당연히, 효용을 극대화하는 에이전트는 현재 게임에서 개인 정보를 공개하는 것이 미래 거래에 미치는 영향을 우려하며, 미래의 잠재적 손실을 최소화하려고 한다.
또한, 일부 에이전트는 현재 게임에 참여하지 않는 외부 관찰자의 신념이 자신에 대해 어떻게 형성되는지를 신경 쓸 수도 있다.
이러한 에이전트는 현재 게임에서의 행동이 외부 관찰자의 신념에 미치는 영향을 최적화하고자 한다.
그러나, 개인정보가 미래의 지불 또는 외부 관찰자의 신념에 미치는 정확한 영향을 명확히 규정하는 것은 복잡하고 정교한 작업이다.
차등 개인정보 보호(Differential Privacy, DP)는 통계 데이터 분석을 위해 개발된 수학적 개인정보 보호 모델로서 [8][9],
이러한 복잡한 모델링을 회피하고, 에이전트의 개인정보 노출을 최악의 경우에도 보장할 수 있는 상한(worst-case bound)을 제공한다.
구체적으로, \(\epsilon\) -차등 개인정보 보호 메커니즘을 사용하면, 어떤 관찰자라도 이 메커니즘의 결과를 본 이후 해당 에이전트에 대한 신념이 최대 \(e^{\epsilon} \approx 1 + \epsilon\) 배까지만 변화하도록 보장할 수 있다.
더 나아가, [14, 20]의 연구에 따르면, \(\epsilon\)-차등 개인정보 보호 메커니즘을 사용하면, 기대값 관점에서 미래 손실이 최대 \(e^{\epsilon} -1 \approx \epsilon\) 배까지만 증가함을 보장할 수 있다.
최근 연구들 [4, 14, 20, 28]에서는 차등 개인정보 보호 개념을 이용하여 게임 이론적 환경에서 개인정보 보호 인식(privacy awareness) 에이전트의 행동을 모델링하고 분석하고 있다.
차등 개인정보 보호의 이러한 특성 덕분에, 연구자들은 미래 거래의 영향을 직접 모델링할 필요 없이, 에이전트의 효용 함수를 “내재적으로(hardwired)” 두 가지 요소 간의 균형을 맞추도록 설정하는 방식으로 개인정보 보호 인식을 모델링하였다.
- 양의 보상(positive reward): 메커니즘의 결과에서 얻는 보상
- 음의 개인정보 노출 손실(negative loss): 비공개 정보가 노출됨으로 인해 발생하는 손실
이 손실은 차등 개인정보 보호를 활용하여 상한을 설정할 수 있으며, 따라서 일부 경우에는 신중하게 설계된 메커니즘을 통해 보상이 손실을 압도하도록 설계할 수 있다.
이러한 결과는 개인정보 보호 우려가 특정 환경에서 에이전트의 행동에 영향을 미치지 않을 수도 있음을 시사한다.
그러나, 일부 경우에서 개인정보 보호를 고려하는 에이전트의 행동은 전통적인(개인정보 보호를 고려하지 않는) 에이전트의 행동과 크게 다를 수 있다.
예를 들어, B가 A가 제공하는 두 개의 무료 선물(이후 설명할 이유로 ‘쿠폰’이라고 부름) 중 어떤 것을 받고 싶은지 A에게 말하는 장난감 게임(toy game)을 고려하자.
B는 0 또는 1 중 하나의 유형(type)으로 구분되며, 유형 0은 첫 번째 선물을 선호하고, 유형 1은 두 번째 선물을 선호한다.
이는 [20]에서 논의된 “호밀빵(Rye) 또는 통밀빵(Wholewheat)” 게임을 재구성한 것이다.
따라서, 개인정보 보호를 고려하지 않는 에이전트는 항상(결정론적으로) 자신의 유형에 맞는 선물을 요구한다는 점을 쉽게 알 수 있다. 반면, Ghosh와 Roth [14]의 연구에서처럼 DP를 사용하여 개인정보 손실을 모델링하고, 쿠폰의 가치가 충분히 크다면, 개인정보 보호를 고려하는 에이전트는 무작위화된 전략(randomized strategy)을 사용한다.
구체적으로, 해당 에이전트는 표준 차등 개인정보 보호 메커니즘인 “무작위 응답(Randomized Response)“을 수행하며, 이 메커니즘은 에이전트가 선호하는 행동을 약간 더 높은 확률로 선택하도록 하는 방식이다.
구체적으로, 해당 에이전트는 표준 차등 개인정보 보호 메커니즘인 “무작위 응답(Randomized Response)“을 수행하며, 이 메커니즘은 에이전트가 선호하는 행동을 약간 더 높은 확률로 선택하도록 하는 방식이다.
그러나, 연구 [4, 20]에서는 DP의 최악의 경우(worst-case) 모델을 사용하여 에이전트의 개인정보 손실을 정량화하고 행동을 예측하는 것은 현실적이지 않다고 주장하였다.
차등 개인정보 보호는 개인정보 손실의 상한(upper bound)만을 제공하는 것이지, 에이전트의 기대 개인정보 손실(expected privacy loss)은 실제로 훨씬 더 작을 수 있으며, 작아야 한다.
이는 다음과 같은 요소들에 따라 달라질 수 있다.
- 에이전트가 미래 사건을 어떻게 예측하는지
- 공격자의 사전 신념
- 다른 에이전트의 유형 및 전략
- 메커니즘과 다른 에이전트의 무작위 선택
에이전트의 미래 거래를 공식화할 수 있으면 어떻게 될까?
만약 우리가 특정한 공격자의 신념에 대해 우려하고 있으며, 해당 신념의 변화가 미치는 영향을 정량화할 수 있다면?
이 경우, 전통적인 이기적(selfish) 에이전트의 행동을 “DP를 내재적으로 적용한(DP-hardwired)” 개인정보 보호 인식 에이전트의 행동으로 잘 모델링할 수 있을까?
또한, 이러한 환경에서 에이전트는 실제로 무작위 전략(randomized strategy)을 사용할까? 즉,
명확한 개인정보 보호 비용이 존재하는 환경에서, 이기적인 효용 극대화 에이전트의 행동은 어떻게 나타나는가?
보다 구체적으로, 장난감 게임에 A와 B 간의 지불을 도입하여, 이 장난감 게임에서 개인정보 보호를 고려하는 에이전트의 행동이 전통적인(개인정보 보호를 고려하지 않는) 에이전트의 행동과 일치하도록 만들 수 있는지 연구한다.
특히 만약 B가 무작위 전략을 선택한다면, 그의 행동이 \(\epsilon\)-DP를 유지하는지, 그리고 어떤 \(\epsilon\) 값에 대해 유지되는지를 분석한다.
이 연구는 전통적인 게임 이론뿐만 아니라, 게임 이론적 맥락을 넘어선 차등 개인정보 보호의 응용에도 의미 있는 통찰(insight)을 제공할 수 있다. 이를 통해, 개인정보 보호 매개변수 \(\epsilon\) 을 설정하는 방법 또는 최악의 경우가 아닌 대안적인 차등 개인정보 보호 모델(such as [1])을 활용하는 방법에 대한 방향성을 제시할 수 있다.
Our Model
비밀 유형(secret type)을 가진 에이전트와 이 유형을 발견하려는 공격자(adversary) 간의 상호작용을 모델링하는 여러 가지 게임을 고려한다.
각 게임에서 에이전트들의 행동이 다소 다를 수 있지만, 모두 위에서 언급한 장난감 게임(toy game)과 유사한 공통적인 구조를 따른다.
에이전트 A는 B에게 무료 쿠폰을 제공한다. 이 쿠폰은 두 가지 유형 {0, 1} 중 하나를 가진다.
에이전트 B는 비밀 유형 \(t \in \{0, 1\}\)을 가지고 있으며, 이는 사전 확률 분포 \((D_0, D_1)\)에 따라 선택된다.
유형 t인 B는 t 쿠폰에 대해 양의 효용 \(\rho_t\)를 가지나, 유형 (1-t) 쿠폰에 대한 효용은 0이다.
게임이 시작되면, B는 A에게 요청하는 쿠폰 유형을 나타내는 신호 \(\hat{t}\)를 보낸다.
A는 B가 보낸 신호 \(\hat{t}\)를 관찰한 후, B에게 도전한다. A는 행동 \(\tilde{t}\)를 선택하고, B는 A에게 지불 함수 \(P(\tilde, t)\)에 따라 지불한다.
A와 B의 확장형 베이지안 게임을 모델링한다. B는 발신자이고 A는 수신자이다.
B의 type에 대한 A의 belief: \(D_0, D_1\)
type spaces: \((\Gamma_A, \Gamma_B)\)
BNE strategy profile: \((\sigma_A, \sigma_B)\)
B의 가능한 동작 집합: \(C_B = \{\) send \(\hat{t} = 0,\) send \(\hat{t} = 1\}\)
A의 가능한 동작 집합은 B의 동작에 따라 달라지므로 A의 가능한 동작 집합은 2개의 tuple로 구성된다.
\(C_A\)의 각 요소는 \(<\tilde{t}_0, \tilde{t}_1>\)의 형태: B의 신호가 \(\hat{t} = 0\)일 때 \(\tilde{t}_0\), B의 신호가 \(\hat{t} = 1\)일 때 \(\tilde{t}_1\)
\(p^* = Pr[\sigma_B^*(0) = 0]\): type t = 0인 agent가 신호 \(\hat{t}=0\)을 보낼 확률이 p*, \(\hat{t}=1\)을 보낼 확률이 1-p*
\(q^* = Pr[\sigma_B^*(1) = 1]\): type t = 1인 agent가 신호 \(\hat{t}=0\)을 보낼 확률이 1-q*, \(\hat{t}=1\)을 보낼 확률이 q*
dynamic/sequential games에서 중요한 하위 클래스인 signaling games에서 BNE의 일반적으로 사용되는 개선은 Perfect Bayesian Equilibrium이라는 평형 개념이다.
A의 BNE 전략은 B가 \(\hat{t}\)를 보낸 후 사후 분포에 대해 최상의 반응을 보여야 한다.
\(\hat{t}=0\)일 때, \(\left(\frac{D_0 p^*}{D_0 p^*+D_1(1-q*)}, \frac{D_1(1-q^*)}{D_0 p^*+D_1(1-q^*)} \right)\)
\(\hat{t}=1\)일 때, \(\left(\frac{D_0(1-p^*)}{D_0(1-p^*)+D_1 q*}, \frac{D_1 q^*}{D_0(1-p^*)+D_1 q^*} \right)\)
separating equilibrium: 수신자가 발신자의 개인 유형을 결정적으로 추론할 수 있다.
pooling equilibrium: 여러 유형의 발신자가 동일한 조치를 취할 수 있으므로 수신자가 자신의 유형에 대한 정보를 얻는 것을 방지할 수 있다.
B가 type \(\hat{t}\)인 쿠폰을 요청하는 가장 간단한 장난감 게임
3. The coupon game
적절한 점수 규칙(proper scoring rule)을 사용하여 A와 B 간의 결제를 모델링한다.
1) 자신의 신념의 정확성에 이익을 A에게 할당하므로 A는 B 유형에 대해 이전 신념을 개선할 인센티브가 있다.
2) 이 모델에서는 신념의 \(\epsilon\)-change와 B가 A에게 지불하는 비용 사이에서 B의 트레이드 오프를 정량화할 수 있다.
{0, 1} 값의 무작위 변수 X의 경우, 전문가는 X = 1일 확률에 대해 예측 \(x \in [0, 1]\)을 보고하도록 요청 받는다.
무작위 변수 X가 1일 확률로 X를 보고하는 전문가에게 지급하는 금액은 무작위 변수 (1-X)가 1일 확률로 보고하는 전문가에게 지급하는 금액과 동일하다. 적절한 채점 규칙에 대한 추가 배경은 부록 A
A는 B의 유형을 발견하는 것을 목표로 한다. A의 지불은 두 가지 함수 \((f_0, f_1)\)로 구성된 적절한 점수 규칙에 의해 주어지므로 유형의 B 에이전트는 x의 믿음을 보고한 후 A에게 \(f_t(x)\)를 지불한다.
1) benchmark game: A는 적절한 점수 규칙에 따라 지급되고, A는 기대에 따라 지급받는다.
2) full game: 참여도가 높은 게임, A는 B의 유형에 대한 보다 정확한 사후 믿음을 목표로, type t 에이전트가 type t 쿠폰을 선호한다는 것을 알고 B에게 두 가지 가능한 쿠폰 중 하나를 제공한다. 따라서 B는 어떤 유형을 보고할지 선택하고, A는 이후 B의 유형 1일 확률을 예측한다.
(0) B의 유형 t는 \(Pr[t=0] = D_0\)와 \(Pr[t=1] = D_1\)로 무작위로 그려진다.
(1) B는 A에게 type \(\hat{t} = \sigma_B(t)\)을 보고하고, 실제로 \(\hat{t}=t\)일 때 \(\rho_t\)의 유틸리티를 받는다. 이 섹션에서 우리는 \(\rho_0 = \rho_1 = \rho\)라고 가정한다.
(2) A는 \(Pr[t=1 | \sigma_B(t)=\hat{t}\)를 나타내는 예측 x를 보고하고, \(f_t(x)\)로부터 B를 받는다.
6. Conclusions and Future Directions
세 가지 가능한 유형 중 하나의 에이전트 B로 확장하는 것 (현재는 차등적으로 비공개인 단일 메커니즘만 있음)
Appendix
Proper Scoring Rule: 전문가나 의사결정자에게 확률적 예측을 솔직히 보고하도록 유도하기 위한 수학적인 방법, 보고된 확률이 실제 확률과 일치할 때 최대 보상을 받도록 설계되어, 참가자가 자신의 실제 믿음을 보고하도록 장려한다.
전문가가 x를 보고하고 실제로 X = 1라면 \(f_1(x)\)를 지불하고, 그렇지 않으면 \(f_0(x)\)를 지불한다.
랜덤 변수: X: 결과가 불확실한 변수, 주로 이진 변수 \(X \in \{0, 1\}\)로 설정된다.
예측: x: X = 1일 확률에 대한 전문가의 예측
전문가가 실제 확률을 보고할 때 예상 점수가 최대화된다.
\(f_0(x) = g(x) – xg'(x)\), \(f_1(x) = g(x) + (1-x)g^{\prime}(x)\)
\(\mu = Pr[X = 1]\)일 때, 전문가가 x를 보고했을 때의 예상 보상은
$$F_\mu(x)=(1-\mu) f_0(x)+\mu f_1(x)=g(x)-(x-\mu) g^{\prime}(x)$$
스코어링 룰을 적용하는 이유:
1) 정직한 보고를 유도 (Truthful Reporting)
2) 확률적 예측의 정확성을 평가하여 불확실성을 정량화
행위자 A가 B의 유형을 정확히 추론하려는 동기를 제공하기 위해 사용한다. A의 유틸리티는 B의 신호를 기반으로 한 정확한 확률적 예측에 따라 결정되며, 이는 스코어링 룰을 통해 최적화된다. 이 과정에서 A와 B 모두 전략적 의사결정을 하게 된다.
–
소셜 거리 기반의 개인화된 차별적 프라이버시 보호 모델을 제안합니다. 프라이버시 수준을 개인화하여 균일한 프라이버시 보호 문제를 해결하였으며, 이를 통해 전체 프라이버시 예산을 줄이고 데이터 유용성을 높였습니다.
2. 사용자의 프라이버시와 공격자의 효과를 모두 고려하는 정적 베이즈 게임을 구축하였습니다. 차별적 프라이버시의 관점에서 모든 파라미터를 공식화하여 공격과 사용자 행위를 정량적으로 측정하였습니다. 이를 통해 데이터 유용성 측정의 불확실성을 제거하고 베이즈 내쉬 균형을 통해 향상된 데이터 유용성을 확보하였습니다.
3. 수정된 Q-학습 알고리즘을 사용하여 베이즈 내쉬 균형을 신속하게 도출했습니다. 데이터의 규모를 줄여 업데이트 규칙을 단순화함으로써 빠른 수렴을 달성하였고, 정적 베이즈 게임을 기반으로 사용자가 최대 데이터 유용성을 달성하기 위한 최적의 전략을 도출했습니다.
4. 실제 데이터셋을 사용한 광범위한 실험을 통해 제안된 모델의 효과성과 실현 가능성을 평가했습니다.
논문은 관련 연구와 배경을 2장에서 제시하며, 3장에서 제안된 모델의 프레임워크를 설명합니다. 4장은 정적 베이즈 게임을 묘사하고, 5장은 강화 학습을 통해 내쉬 균형 도출을 시연합니다. 6장은 시스템 분석, 7장은 성능 평가를 다루며, 마지막으로 8장에서 논문을 결론짓습니다.
• 소셜 네트워크에서 개인화된 차별적 프라이버시를 활용하여 데이터 유용성을 최대화할 수 있는 최적의 보호 전략은 무엇인가?
• 사용자와 공격자 간의 상호작용을 효과적으로 모델링하고, 프라이버시 보호와 데이터 유용성 간의 트레이드오프를 최적화할 수 있는 방법은 무엇인가?
References
Chen, Yiling, Or Sheffet, and Salil Vadhan. “Privacy games.” ACM Transactions on Economics and Computation (TEAC) 8.2 (2020): 1-37.