Abstract
차등 프라이버시(differential privacy) 의 관점에서 개인 데이터 시장(private data markets) 에 대한 연구를 시작한다. 우리는 인구 통계를 추정하기 위해 민감한 정보를 구매하려는 데이터 분석가를 모델링한다.
이미 개인 데이터의 매매가 대규모로 이루어지고 있지만, 개인정보를 상품(commodity)으로 보는 이론적인 연구는 부족하다. 본 논문에서는 이러한 이론을 구축하는 것을 목표로 한다.
구체적으로, 우리는 데이터 분석가(data analyst) 가 특정 통계를 추정하기 위해 일반 대중으로부터 데이터를 구매하는 상황을 고려한다.
데이터 분석가는 정확한 통계를 가능한 한 저렴하게 얻기를 원하며, 반면 개인 데이터의 소유자들은 프라이버시 손실(privacy loss)로 인해 비용(cost)을 경험하게 되므로, 이에 대한 보상을 받아야 한다.
각 개인(에이전트)은 자신의 이익(profit)을 극대화하려는 이기적인 존재이므로, 본 논문의 목표는 진실성을 보장하는(truthful) 메커니즘을 설계하는 것이다.
– 조달 경매: 구매자가 여러 판매자로부터 특정 상품을 구매하려는 경매 방식
– 다중 단위 조달 경매: 구매자가 동일한 상품을 여러 개 구매해야 하는 경우를 다루는 경매 방식
본 논문의 주요 결과는 이러한 문제를 다중 단위 조달 경매(multi-unit procurement auctions)의 변형으로 자연스럽게 해석하고 최적화할 수 있다는 점이다.
이 결과를 바탕으로, 우리는 두 가지 자연스러운 상황에서 최적(상수 계수 내에서)인 경매 방식을 도출한다.
- 데이터 분석가가 고정된 정확도 목표(fixed accuracy goal) 를 가지고 있을 때, 전통적인 빅리(Vickrey) 경매를 적용하면 분석가의 정확도 목표를 달성하면서 총 지불 비용을 최소화할 수 있음을 증명한다.
- 데이터 분석가가 고정된 예산(fixed budget) 을 가지고 있을 때, 우리는 최종적으로 추정된 값의 정확도를 최대화하면서도, 총 지불 금액이 예산을 초과하지 않도록 보장하는 메커니즘을 제안한다.
이 두 가지 경우 모두에서, 우리는 비교 기준으로 질투 없음/시기심 없는(envy-free) 메커니즘을 사용하며, 이는 고정 가격(fixed-price) 메커니즘의 자연스러운 범주와 일치한다.
이 두 가지 결과에서, 우리는 개인의 프라이버시 가치(valuation for privacy)와 실제 데이터 사이의 상관관계로 인해 발생할 수 있는 프라이버시 비용(privacy cost)을 고려하지 않았다.
우리는 또한 개인이 보고한 프라이버시 가치로 인해 발생하는 프라이버시 손실(privacy loss)에 대해 개별적으로 합리적인(individually rational) 메커니즘이 보상을 제공할 수 없음을 일반적으로 증명한다.
그럼에도 불구하고, 이는 중요한 문제이며, 이를 정확하게 모델링하는 것은 향후 연구에서 다루어야 할 중요한 방향 중 하나이다.
1. Introduction
- 가장 중요한 문제는 ‘개인정보’라는 개념을 정의하고, 이를 정량적으로 측정하는 것이다.
이러한 측면에서 개인정보를 상품화하는 개념은 개인정보 보호의 이론적 기초의 발전과 자연스럽게 연결된다.
특히, 최근 연구에서 도입된 차등 프라이버시 연구 [DMNS06] (정의 2.1) 는 개인정보를 보호하는 강력한 개념을 제공할 뿐만 아니라, 이를 정량적으로 측정할 수 있는 체계를 제시한다.
더 중요한 점은, 차등 프라이버시가 보장하는 성질이 효용 이론(utility-theoretic) 관점에서 자연스럽게 해석될 수 있으며, 이를 사고팔 수 있는 양적 개념으로 정의할 수 있다. - 개인 데이터는 본질적으로 상호 보완성인 성질(intrinsic complementarities)을 갖는 상품이다.
데이터 분석가는 특정 개인의 개별적인 데이터 자체에는 관심이 없으며, 일반적으로 대규모 모집단에서 대표적인 샘플을 얻는 것에 관심이 있다. 하지만 분석가는 개별적인 개인들로부터 데이터를 구매해야 한다.
만약 각 개인들이 자신의 개인정보에 대한 가치(value for privacy)와 실제 데이터 사이에 알 수 없는 상관관계를 가지고 있다면, “가장 저렴한 판매자로부터 데이터를 구매하는” 일반적인 전략은 실패할 가능성이 크다.
그렇다면, 분석가가 전체 인구를 대표하는 값을 계산하려 할 때, 어떤 방식으로 경매를 설계해야 할까? - 개인이 개인정보 보호에 대해 지불해야 하는 비용 자체가 비공개 정보일 수 있다.
예를 들어, 앨리스가 종양학 전문의를 방문한 후, 개인정보 보호의 가치를 급격히 높게 평가하기 시작했다고 가정해 보자. 이 경우, 앨리스가 갑자기 프라이버시를 중요하게 생각하기 시작했다는 사실 자체가 이미 정보 유출이 될 수 있다.(
이러한 변화 자체가 그녀의 건강 상태에 대한 정보를 암시할 수 있다.) 그렇다면, 경매를 설계할 때 개별 응찰자들의 개인정보 보호 손실을 보상하는 방식으로 메커니즘을 구성할 수 있을까? 즉, 단순히 데이터를 제공하는 대가를 지불하는 것이 아니라, 응찰(bid) 자체가 경매의 작동 방식에 영향을 미치면서 발생하는 개인정보 보호 손실까지도 고려할 수 있을까?
1.1. Differential Privacy as a Commodity
차등 개인정보 보호(differential privacy)는 데이터베이스 개인정보 보호를 위한 기술적 정의로, Dwork 등 [DMNS06]에 의해 공식적으로 제안되었다(자세한 내용은 2장에서 정의함). 비공식적으로, 한 개인의 데이터가 변경되더라도 알고리즘의 출력 확률이 exp(ε) ≈ (1 + ε) 배 이상 변하지 않으면, 해당 알고리즘은 ε-차등 개인정보 보호를 만족한다고 한다.
차등 개인정보 보호는 또한 자연스러운 효용 이론적(utility-theoretic) 해석을 제공하므로, 개인정보를 구매하거나 판매할 때 이를 정량적으로 측정하는 유용한 척도로 활용할 수 있다.
ε-차등 개인정보 보호를 만족하는 알고리즘 A의 중요한 속성 중 하나는, 데이터베이스와 독립적인 임의의 함수 f와 조합되더라도 f(A) 역시 ε-차등 개인정보 보호를 유지한다는 점이다. 이 속성을 통해 알고리즘의 실제 출력과는 상당히 동떨어진 사건에 대해서도 논리적으로 추론할 수 있다.
예를 들어, ε-차등 개인정보 보호 보장은 “저녁 식사 중에 광고 전화를 받을 확률” 또는 “건강 보험 가입이 거부될 확률”이 exp(ε) 배 이상 증가하지 않는다는 것을 의미한다. 이러한 속성 덕분에 차등 개인정보 보호는 모든 개별 사용자에 대해, 임의의 (알려지지 않은) 효용 함수가 존재하더라도 적용될 수 있는 강력한 보장이 된다.
구체적으로, 어떤 개인이 미래 사건들에 대해 특정 효용 함수 u를 가지고 있다고 할 때, ε-차등 개인정보 보호를 만족하는 연산은 해당 개인의 미래 기대 효용을 exp(-ε) ≈ (1 – ε) 배 이상 감소시키지 않는다. 또는, 이를 동등하게 표현하면, 기대 효용 E[u(x)]의 ε배(εE[u(x)]) 이하의 가산적 감소를 초래한다.
따라서, 개인이 자신의 데이터를 ε-차등 개인정보 보호 방식으로 사용하도록 허용할 때 발생하는 비용을 정량적으로 평가하는 자연스러운 방법이 존재한다. 즉, 그 개인에게 있어 해당 데이터 사용의 가치는 그의 기대 효용의 ε-비율(ε-fraction)에 해당해야 한다. 이에 대한 보다 자세한 설명은 2.3장에서 다룬다.
1.2. Results
본 논문의 주요 기여는 차등 개인정보 보호를 보장하는 메커니즘이 일정 수준의 정확도를 제공하려면, 특정 수의 개인으로부터 최소한의 개인정보 보호(privacy)를 구매해야 한다는 점을 밝힌 것이다. 이는 정확한 응답을 개인정보 보호 방식으로 제공하는 문제를 조달 문제(procurement problem)의 형태로 단순화할 수 있음을 의미한다.
구체적으로, 우리는 다음과 같은 모델을 연구한다. 먼저,
- n명의 개인(n individuals)이 존재하며, 각 개인 i는 개인적인 비트 값 bᵢ를 가지고 있다.
- 이 정보는 병원과 같은 개인정보를 관리하는 데이터베이스 관리자(database administrator)에 의해 이미 알려져 있다.
- 각 개인은 또한 비용 함수(cost function) cᵢ(ε)를 가지고 있으며, 이는 bᵢ가 ε-차등 개인정보 보호 방식으로 사용될 경우 해당 개인이 부담해야 하는 비용을 나타낸다.
- 모든 유효한 메커니즘은 각 개인에게 그들의 개인정보 사용에 대한 보상을 제공해야 한다.
- 또한, 개인들은 자신의 비용 함수를 조작하여 지급받는 금액을 최대화하려는 전략적 행동을 할 수 있으므로, 개인들이 자신의 실제 개인정보 보호 비용을 정직하게 보고하도록 유도하는 메커니즘 설계가 필요하다.
한편, 데이터 분석가는 두 가지 목표 중 하나를 가지고 있다. 첫 번째는 고정된 정확도 목표를 설정하고, 해당 정확도를 얻는 데 필요한 비용을 최소화하는 것이며, 두 번째는 제한된 예산 내에서 가능한 한 높은 정확도를 달성하는 것이다.
이러한 문제를 해결하기 위해, 우리는 먼저 개인들이 자신의 비트 값 bᵢ의 사용으로 인한 개인정보 보호 손실에 대한 보상을 받지만, bᵢ와 비용 함수 cᵢ 사이의 암묵적인 상관관계로 인한 추가적인 개인정보 유출에 대한 보상은 받지 않는 간단한 모델을 고려한다. 즉, 특정 개인의 데이터 bᵢ가 전혀 사용되지 않는다면, 해당 개인은 개인정보 보호 손실을 입지 않으므로, 메커니즘이 보상을 제공할 필요가 없다.
데이터 분석가가 정확한 통계 값 s = ∑ bᵢ를 확보하는 경매를 설계하려 할 때, 직관적으로 여러 가지 복잡한 메커니즘이 고려될 수 있다. 예를 들어, 무작위로 개인을 샘플링한 후, 샘플 전체를 대상으로 데이터를 구매하는 방식이 가능하다. 그러나 이러한 방식에는 많은 변형이 존재하며, 처음에는 이러한 접근법을 탐색하는 방향으로 연구를 진행했다.
그러나 우리의 주요 결과는 이러한 복잡한 메커니즘을 고려할 필요가 없다는 것이다. 우리는 메커니즘의 내부 구조를 추상화할 수 있으며, 본질적으로 다중 단위 조달 경매로 문제를 단순화할 수 있음을 보인다.
이로 인해 몇 가지 중요한 결과가 도출된다. 첫째, 데이터 분석가가 특정 정확도 목표를 달성하는 데 필요한 비용을 최소화하려는 경우, 우리는 표준 VCG(Vickrey-Clarke-Groves) 메커니즘이 “시기심 없는(Envy-Free)” 메커니즘 중 최적임을 보인다. 둘째, 데이터 분석가가 고정된 예산 내에서 정확도를 극대화하려는 경우, 우리는 더 비정형적인 조달 경매 환경을 다룬다. 이 경우, 구매자는 가능한 한 많은 판매자로부터 데이터를 구매하려 하며, 판매자의 개인정보 보호 비용은 다른 판매자들이 데이터 판매에 참여하는지 여부에 따라 달라진다. 이러한 환경에서, 우리는 각 사례(instance)에 대해 최적의(fixed-price, envy-free) 진실성(truthful) 메커니즘을 제안한다.
우리가 제안하는 고정 가격(fixed-price) 메커니즘은 기존의 선행 연구에서 사전 정보 없이(prior-free) 메커니즘을 설계할 때 표준적으로 사용되는 방식이다. 그러나 우리의 연구에서는 기존의 경매 환경과 차이가 있다. 특히, 베이지안 최적(Bayesian-optimal) 메커니즘이 이미 존재하는 환경에서는 고정 가격 메커니즘이 적절한 기준이 될 수 있다. 하지만, 현재 연구되는 조달 경매 환경에서는 베이지안 최적 메커니즘이 알려져 있지 않으므로, 우리의 벤치마크 선택(고정 가격 메커니즘의 정당성 또는 개선 가능성)이 추가 연구를 통해 검증될 필요가 있다.
마지막으로, 우리는 일반적인 불가능성(impossibility) 결과를 제시한다. 어떤 직접 보고 메커니즘(direct revelation mechanism)도, 개인의 비공개 데이터 bᵢ와 비용 함수 cᵢ 사이의 알려지지 않은 상관관계로 인해 발생하는 개인정보 보호 손실을 보상할 수 없다. 즉, 만약 개인의 비용 함수 cᵢ가 사전에 정해진 특정 범위 내에 존재한다는 가정이 없다면, 개인들에게 비(非)사소한 개인정보 보호 보장을 제공하는 것이 불가능하다. 이러한 결과는 개인 데이터와 개인정보 보호 비용 간의 알려지지 않은 상관관계를 연구할 수 있는 올바른 모델을 찾는 것이 중요한 연구 방향이라는 점을 시사한다.
2. Preliminaries
우리는 n명의 개인 {1, …, n}의 데이터를 포함하는 데이터베이스를 고려하며, 이 집합을 [n]으로 표기한다. 각 개인 i는 개인적인 비트 값 \(b_i \in \{0,1\}\)와 개인의 개인정보 보호 비용을 나타내는 값 \(v_i\)를 가진다. 이때, \(v_i\)는 개인이 자신의 개인정보 보호 손실에 대해 부여하는 비용을 나타내는 비용 함수(cost function)를 매개변수화하는 값이다.
개인적인 비트 \(b_i\)는 임의의 예/아니오(yes/no) 질문에 대한 응답을 나타낸다고 가정할 수 있다. 예를 들어, 특정 개인이 민감한 의료 상태를 가지고 있는지 여부를 나타낼 수도 있다.
이 비트 값 \(b_i\)는 검증 가능하며, 개인은 자신의 비트 값을 거짓으로 보고할 수 없다. 예를 들어, 병원과 같은 신뢰할 수 있는 데이터베이스 관리자가 이미 이 정보를 알고 있거나, 혈액 또는 타액 샘플을 통해 경매 주최자가 직접 확인할 수 있는 경우가 이에 해당한다.
반면, 개인은 자신의 개인정보 보호 비용 \(v_i\)를 거짓으로 보고할 가능성이 있으며, 따라서 개인이 자신의 실제 개인정보 보호 비용을 정직하게 보고하도록 유도하는 인센티브 구조가 필요하다.
이 모델을 보다 구체적으로 공식화하는 내용을 다음 절에서 다룬다.
2.2. Mechanism Design
메커니즘 내에서 참가자의 효용 함수(utility function)를 구체적으로 정의하고, 이 함수가 개인정보 보호 보장과 어떻게 관련되는지를 설명한다.
각 개인 i는 메커니즘이 알지 못하는 단일 매개변수(single-parameter) 비용 함수 \(c(v_i, \cdot)\)를 가지고 있으며, 이는 \(v_i\)라는 매개변수로 표현된다. 여기서 \(c(v_i, \epsilon)\)는 개인 i가 자신의 데이터를 \(\epsilon\)-차등 개인정보 보호 방식으로 사용할 때 부담해야 하는 비용을 나타낸다.
비용 함수는 정규화(normalized)되어 있으며, 모든 \(v_i\)에 대해 \(c(v_i, 0) = 0\)을 만족한다. 또한, 이 함수는 연속 함수(continuous function)라고 가정한다.
우리는 두 가지 모델을 연구한다.
- 첫 번째 모델에서는 개인의 데이터가 단순히 개인적인 비트 \(b_i\) 하나로만 표현되는 경우를 다룬다.
- 두 번째 모델에서는 개인의 데이터가 \((v_i, b_i)\) 쌍으로 구성되어 있으며, 개인의 개인정보 보호 비용도 포함되는 경우를 다룬다.
각 개인의 비용 함수는 공개적으로 알려진 동일한 함수 계열(family)에 속하지만, 매개변수 \(v_i\) 값 자체는 개인만 알고 있으며, 이를 메커니즘에 보고해야 한다. 따라서 메커니즘은 개인이 자신의 \(v_i\) 값을 정직하게 보고하도록 유도하는 설계가 필요하다.
우리의 연구 결과가 유효하기 위해, 비용 함수 계열은 \(\epsilon\)에 대해 전체 순서(total ordering) 관계를 만족해야 한다. 즉, 임의의 개인 \(i \neq j\) 및 모든 \(\epsilon\)에 대해,
\(c(v_i, \epsilon) \leq c(v_j, \epsilon) \quad \text{if and only if} \quad v_i \leq v_j\)
→ \(v_i\)가 작을수록, 개인은 자신의 개인정보 보호를 상대적으로 덜 중요하게 여긴다.
따라서 동일한 \(\epsilon\)에서 보호 비용 \(c(v_i, \epsilon)\)도 낮아야 한다.
이 성질을 만족하는 자연스러운 비용 함수의 예시는 다음과 같다.
- 선형 비용 함수(linear cost function): \(c(v_i, \epsilon) = v_i \epsilon\)
- 지수형 비용 함수(exponential cost function): \(c(v_i, \epsilon) = \exp(\epsilon v_i)\)
- 이차 비용 함수(quadratic cost function): \(c(v_i, \epsilon) = v_i \epsilon^2\)
위와 같은 여러 형태의 비용 함수가 사용될 수 있다.
메커니즘 M은 입력값으로
- 비용 매개변수 벡터 \(v = (v_1, \dots, v_n)\) 와
- 개인적인 비트 값 벡터 \(b = (b_1, \dots, b_n)\)
를 받아서, 다음을 출력한다.
- 어떤 통계량 \(\hat{s}\)에 대한 추정값(estimate of some statistic \(\hat{s}\))
- 데이터 분석가로부터 수집한 총 지불 금액(payment), 이 금액은 참가자들에게 분배됨
우리는 다음의 두 가지 개인정보 보호 모델을 고려한다.
2.3. Valuing Differential Privacy
이 절에서는 개인이 자신의 데이터가 \(\epsilon\)-차등 개인정보 보호 방식으로 사용될 때 발생하는 비용을 정량화할 수 있어야 하는 이유를 설명한다.
Fact 2. 차등 개인정보 보호가 함수 합성(composition)과도 호환된다는 의미이다. 즉, 차등 개인정보 보호를 만족하는 메커니즘을 거친 데이터라면, 그 결과를 이용해 추가적인 처리를 하더라도 차등 개인정보 보호 보장이 유지된다는 것이다.
사람들은 보통 자신의 기대 효용(미래에 얻을 수 있는 이익)이 줄어드는 것을 원하지 않는다. 만약 데이터를 제공했을 때의 기대 효용이 줄어든다면, 당연히 그에 대한 보상을 받아야 한다. 차등 개인정보 보호가 제공된다면, 기대 효용의 변화는 최대 (exp(ε) – 1) 배만큼 변할 수 있다. 즉, 데이터 제공자가 잃을 수 있는 효용 손실을 보상하려면, 비용 함수를 다음과 같이 정의하는 것이 합리적이다.
\(c(v_i, \epsilon_i) = (e^{\epsilon_i} – 1) v_i\)
여기서, \(v_i\)는 데이터를 제공하지 않았을 때 개인이 기대하는 미래 효용, \(\epsilon_i\)는 메커니즘이 제공하는 차등 개인정보 보호 수준이다.
현실에서는 \(\epsilon\)이 아주 작은 경우가 많다. 지수 함수(exp(ε))는 작은 값에서는 거의 선형적(ε)으로 동작하기 때문에, 비용 함수를 더 단순하게 다음과 같이 근사할 수 있다.
\(c(v_i, \epsilon_i) \approx \epsilon_i v_i\)
3. Characterizing Accurate Mechanisms
이 절에서는 정확도를 보장하기 위해 각 개인으로부터 메커니즘이 구매해야 하는 개인정보 보호의 양에 대한 필요하고 충분한 조건을 제시한다. 특정 정확도 수준을 얻기 위해, 우리는 메커니즘이 최소한 ǫ 단위의 개인정보 보호를, 적어도 |H|명의 개인으로부터 구매해야 한다고 보여준다. 여기서 ǫ과 |H|의 값은 원하는 정확도에 따라 달라진다. 우리는 이러한 조건들이 메커니즘의 진실성 요구사항(truthfulness requirements)과는 무관하게, 정확도를 달성하기 위한 필요성에서만 발생한다고 강조한다. 이러한 조건들은 민감한 값 모델(sensitive value model)과 비민감한 값 모델(insensitive value model) 모두에 적용된다. 이는 개인 정보 경매 메커니즘 설계를 크게 단순화시킨다. 왜냐하면, 이를 통해 우리는 다중 단위 조달 경매(multi-unit procurement auction)에만 집중하면 되기 때문이다.
Theorem 3.1. (정확도에 대한 조건)
\(0 < \alpha < 1\)일 때, α·n/4-정확성(α·n/4-accuracy)을 만족하는 차등 개인정보 보호 메커니즘은 다음 조건을 만족해야 한다:
- 모든 \(i \in H\)에 대해 \(\epsilon_i \geq \frac{1}{\alpha n}\).
- \(|H| \geq (1 – \alpha)n\).
Proof. M을 α·n/4-정확성을 만족하는 메커니즘이라고 하자. 또한, \(H \subseteq [n]\)을 \(\epsilon_i \geq \frac{1}{\alpha n}\)을 만족하는 개인들의 집합으로 정의하자.
모순을 위한 가정: \(|H| < (1 – \alpha)n\)이라고 가정하자. 그러면, \(H = [n] \setminus H\)로 정의할 수 있다. 이 경우, \(|\bar{H}| > \alpha n\)이므로, 집합 \(S = \{x \in \mathbb{R} : |x – s| < \frac{\alpha n}{4} \}\), 여기서 \(s = \sum_{i=1}^{n} b_i\)라고 정의한다.
정확도에 따라 메커니즘 M(v, D)의 출력인 추정치 \(\hat{s}\)는 다음을 만족해야 한다:
\(Pr[\hat{s} \in S] \geq \frac{2}{3}\).
이제, \(H_1 = \{i \in H : b_i = 1\}\)과 \(H_0 = \{i \in H : b_i = 0\}\)으로 H를 두 집합으로 분할할 수 있다. 이때, \(H_0\)와 \(H_1\)은 H의 분할을 이루며, 다음이 성립한다:
\(\max(|H_0|, |H_1|) > \frac{\alpha n}{2}\).
손실 없이 일반성을 잃지 않기 위해 \(|H_0| > \frac{\alpha n}{2}\)라고 가정하자. 이제, \(T \subseteq H_0로서 |T| = \frac{\alpha n}{2}\)이고, 데이터셋 \(D{\prime}\)는 T에 포함된 각 \(b_i\) 값을 1로 변경한 데이터셋이라고 하자. 이때, \(D{\prime}\)와 D는 해밍 거리가 \(|T| = \frac{\alpha n}{2}\)이고, T의 인덱스에서만 서로 다르다.
이때, 메커니즘의 차등 개인정보 보호 특성을 사용하여, 사실 1을 적용하면 다음이 성립한다:
\(Pr[\hat{s}{\prime} \in S] \geq e^{-\frac{2}{\alpha n}} \cdot Pr[\hat{s} \in S]\)
이후, \(\hat{s}와 \hat{s}{\prime}\)의 차이를 고려하여 \(\hat{s}{\prime} \in S\)일 때 삼각 부등식(triangle inequality)을 이용하여 모순을 유도할 수 있다. 이 과정에서 \(\hat{s}{\prime}\)와 실제 값 \(s{\prime}\)의 차이가 \(\frac{\alpha n}{4}\)를 초과하는 확률이 1/3보다 클 수 없다는 모순을 도출하게 된다.
따라서, 메커니즘이 α·n/4-정확성을 만족하려면 적어도 \((1-\alpha)n\)명의 개인으로부터 \(\epsilon_i \geq \frac{1}{\alpha n}\)의 개인정보 보호를 구매해야 한다는 결론을 도출할 수 있다.
(각 개인에게 최소한 ε ≥ 1 / (αn) 정도의 개인정보 보호 수준을 보장해야 한다.)
→ 차등 개인정보 보호를 보장하면서도 원하는 수준의 정확도를 달성하기 위해 메커니즘이 최소한 어느 정도의 개인정보를 구매해야 하는지를 설명하는 것이다.
즉, 데이터 분석가가 정확한 통계값을 얻고 싶다면, 일정 수준 이상의 개인정보 보호(ε)를 특정 수의 개인들에게 제공해야 한다는 의미이다.
4. Deriving Truthful Mechanisms
개인 데이터 거래를 경매 문제로 변환하여 해결하는 접근법을 사용한다.
즉, 데이터 구매를 다중 단위 조달 경매(Multi-Unit Procurement Auction) 문제로 보고, 이를 통해 최적의 가격 책정 및 데이터 거래 방식을 도출한다.
4.1 Maximizing Accuracy Subject to a Budget Constraint
1) 첫번째 메커니즘: 정확도 목표(fixed accuracy goal) 를 가진 데이터 분석가가 총 지불 비용을 최소화하면서 목표 정확도를 달성하려는 경우, 우리는 표준 VCG (Vickrey-Clarke-Groves) 메커니즘이 envy-free(질투 없음) 메커니즘 중 최적임을 보인다.
* envy-free: 자신 i의 프라이버시 비용을 고려할 때, 다른 개인 j의 결과를 더 선호하지 않아야 한다.
데이터 분석가가 고정된 정확도 목표를 가지고 있어, 통계를 추정할 때 일정 수준 이상의 정확도를 유지해야 한다.
이 때 클래식 Vickrey Auction (2등 가격 경매, 빅리 경매)를 적용하여
• 참가자(데이터 제공자)들이 자신의 프라이버시 비용을 제안.
• 데이터 분석가는 가장 낮은 가격을 제시한 데이터 제공자로부터 구매.
• 낙찰자는 두 번째로 낮은 가격을 제시한 참가자의 가격으로 보상을 받음.
• 이를 통해 진실한 응답(truthful bidding)을 유도할 수 있음.
– 낙찰자는 데이터 분석가가 데이터를 구매하는 개인(데이터 제공자)을 의미한다.
– 낙찰자는 가장 낮은 가격을 제시한 참가자이다.
– 하지만 낙찰자는 자신이 제시한 가격이 아니라, 두 번째로 낮은 가격을 제시한 참가자의 가격을 받는다.
Vickrey 경매가 진실한 응답을 유도하는 이유
• 너무 높은 가격을 부르면 낙찰되지 않을 위험이 있음.
• 너무 낮은 가격을 부르면 실제 비용보다 적은 보상을 받을 위험이 있음.
• 하지만 자신의 실제 비용을 정직하게 보고하면,
• 낙찰될 가능성이 높아지면서도,
• 두 번째로 낮은 가격을 받을 수 있기 때문에 항상 보상을 받을 수 있는 안전한 전략이 됨.
Observation 4.3. 모든 i, j에 대해 \(\epsilon_i > 0, \epsilon_j > 0\) 이라면 반드시 \(p_i = p_j\)가 성립해야 한다.
이러한 메커니즘을 ‘고정 구매(fixed purchase) 메커니즘’이라고 부른다.
즉 envy free fixed purchase mechanisms은 모든 개인정보를 구매하는 개인들에게 동일한 가격을 지불해야 한다.
Proposition 4.4. FairQuery의 최적성 증명
FairQuery는 모든 진실성(truthful), 개별 합리성(individually rational), 시기심 없는(envy-free) 고정 구매 메커니즘 중에서, 주어진 예산 B 내에서 최적의 정확도를 달성한다.
Proof.
1. FairQuery가 시기심 없는 고정 구매 메커니즘인지
모든 선택된 개인에게 동일한 \(\epsilon_i = \frac{1}{n-k}\) 수준의 개인정보 보호를 구매한다.
2. FairQuery가 예산 내에서 최적의 정확도를 보장하는지
k명의 개인이 선택되었을 때, 다음 사람이 추가로 선택될 경우의 조건을 고려한다.
선택되지 않은 다음 개인 k+1의 비용 조건은
\(\frac{v_{k+1}}{(n-k-1)} > \frac{B}{k+1}\)
만약 k’ > k인 다른 메커니즘이 더 많은 개인을 선택하려면 \(p_{k+1} > B/(k+1)\)가 되어야 한다.
새로운 개인 k+1이 포함된다면, 모든 선택된 개인에게 지급되는 지불금 \(p_i\)는 다음 조건을 만족해야 한다.
\(p_{k+1} > \frac{B}{k+1}\)
4.2 Minimizing Payment Subject to an Accuracy Constraint
2) 두번째 메커니즘: 예산 제한(fixed budget) 내에서 정확도를 최대화하려는 경우, 이는 보다 특이한 형태의 조달 경매(procuring auction) 문제로 변환된다.
데이터 분석가는 제한된 예산 안에서 최대한 많은 개인의 데이터를 구매하여, 가능한 한 높은 정확도를 확보하려고 한다.
즉, 예산을 초과하지 않는 범위 내에서, 가장 많은 데이터를 얻는 것이 목표이다.
이 문제에서는 구매자가 가능한 한 많은 판매자로부터 데이터를 구매하려 하며, 각 판매자의 비용이 다른 판매자의 판매 여부에 따라 달라질 수 있는 구조를 갖는다.
예산 제한 기반, 데이터 분석가가 고정된 예산을 가지고 있어 예산 내에서 최대한 높은 정확도를 보여야 한다.
연구에서는 고정 가격(fixed-price) 메커니즘을 적용하여 최적의 데이터를 확보하는 방법을 제안한다.
이 메커니즘은 각 참가자에게 일정한 가격을 제시하고, 해당 가격에 동의하는 참가자들의 데이터를 구매하는 방식이다.
1. 데이터 분석가는 특정한 가격 p를 결정함.
• 이 가격은 참가자들에게 동일하게 적용되는 고정된 가격임.
• 가격을 너무 낮게 설정하면 많은 참가자들이 참여하지 않게 됨.
• 가격을 너무 높게 설정하면 적은 수의 참가자에게만 데이터를 구매할 수 있어 전체 정확도가 떨어질 수 있음.
2. 참가자들은 제안된 가격 p에 동의할지 결정함.
• 자신의 프라이버시 비용 \(c_i(\epsilon)\) 보다 높은 경우: 참가자는 데이터를 제공함.
• 자신의 프라이버시 비용 \(c_i(\epsilon)\) 보다 낮은 경우: 참가자는 데이터를 제공하지 않음.
3. 데이터 분석가는 예산 B 내에서 최대한 많은 참가자로부터 데이터를 구매함.
• 만약 제안된 가격으로 데이터를 제공하려는 참가자가 너무 많으면, 일부만 선택해야 함.
• 만약 제공자가 부족하면, 가격을 조정하여 더 많은 참가자를 확보해야 함.
왜 고정 가격을 사용하는가?
• 참가자는 자신의 비용을 숨기거나 조작할 유인이 줄어듦
• 모든 참가자가 같은 가격을 받기 때문에, 거짓으로 높은 가격을 제시해도 더 많은 돈을 받을 수 없음
• 복잡한 가격 조정 없이, 한 번의 가격 결정으로 참가자들의 데이터를 구매할 수 있음
이 문제에서는 구매자는 가능한 한 많은 판매자로부터 데이터를 구매하려 하며, 각 판매자의 비용이 다른 판매자가 데이터를 판매하는지 여부에 따라 결정되는 구조를 가진다.
• 이러한 설정에서 우리는 고정 가격(fixed-price) 메커니즘 중에서 개별 사례별(instance-by-instance)로 최적의 진실성(truthful) 메커니즘을 제안한다.
• 우리는 고정 가격 메커니즘을 비교 기준(benchmark)으로 사용하며,
이는 기존의 프라이어-프리 메커니즘 설계(prior-free mechanism design)에서 표준적인 접근 방식이다.
– 다만, 이 연구의 설정에서는 베이지안 최적(Bayesian-optimal) 메커니즘이 알려져 있지 않으므로, 고정 가격 접근법을 정당화하거나 개선하는 것이 향후 연구 과제.
–
고정된 정확도 제약 k 하에서 최소 비용으로 데이터를 구매하는 메커니즘을 고려한다.
정확도 k-정확성을 보장하면서, 지불해야 하는 비용을 최소화하려면 어떻게 해야 하는가?
이 문제를 해결하기 위해, 다중 단위 조달 경매(multi-unit procurement auction) 모델을 사용하며, VCG 메커니즘이 최적임을 보일 것이다.
정리 3.3에 의해, 정확도 목표 \(\alpha n\)을 달성하려면 \((1/2 + \ln 3) \cdot \alpha n\) 만큼의 개인정보 보호를 구매해야 한다. 그리고 이 보호를 총 \((1 – \frac{\alpha}{(1/2 + \ln 3)}) n\)명의 개인으로부터 구매해야 한다.
각 개인은 \((1/2 + \ln 3) \cdot \alpha n\) 단위의 개인정보 보호를 판매한다고 가정할 때, 각 개인의 비용 \(v_i\)은 해당 개인정보 보호량을 판매하는 총 비용으로 설정된다.
\(v_i = c_i((1/2 + \ln 3)an)\)
따라서, 이 문제는 \((1 – \frac{\alpha}{(1/2 + \ln 3)}) n\) 개의 개인정보 보호 단위를 구매하는 경매 문제로 변환된다.
MinCostAuction
입력: 비용 벡터 \(v_i\), 데이터베이스 D, 정확도 목표 \(\alpha\)
출력: 정확도 k를 만족하는 데이터 \(\hat{s}\) 및 비용 \(p_i\)
정확도 목표 기반으로 k 결정
개인 k명을 선택해야 하므로 k는 다음과 같이 설정된다.
\(k = [(1-\alpha^{\prime})n]\)
개인이 제공하는 개인정보 보호 비용 \(v_i = c_i \epsilon_i = c_i(1/(n-k))\)
데이터 추정값 \(\hat{s}\)는 \(\hat{s} = \sum_{i=1}^{k} b_i + \frac{n-k}{2} + \text{Lap}(\alpha{\prime} n)\)으로 설정된다.
선택되지 않은 개인(i > k)에게는 지불금 \(p_i = 0\), 선택된 개인(i \(\leq\) k)에게는 지불금 \(p_i = v_{k+1}\).
다음 낙찰자의 비용 \(v_{k+1}\)을 지불하도록 설계된다. (한 단계 낮은 가격을 기준으로 지불하는 원칙)
→ 추가로 낙찰될 수 있는 k+1 번째 개인의 가격을 기준으로 지불금을 결정한다.
1. 개별 합리성
모든 선택된 개인 i에게 지급되는 비용 \(p_i\)는 항상 자신의 실제 비용 \(v_i\)보다 크거나 같다.
왜냐하면, \(p_i = v_{k+1}\)이고, 정렬된 순서에서 \(v_i \leq v_{k+1}\)이므로 항상 \(p_i \geq v_i\)가 된다.
따라서 모든 개인이 손해를 보지 않고 참여할 동기가 있기 때문에 개별 합리성을 만족한다.
2. 진실성
VCG 방식은 개인이 자신이 비용을 조작하여 더 많은 이득을 얻을 수 없는 구조를 가진다.
왜냐하면, 지불금 \(p_i\)은 \(v_{k+1}\)로 고정되어 있다.
Proposition 4.5. MinCostAuction이 진실성, 개별 합리성 및 정확도를 만족한다.
1. MinCostAuction이 \(\alpha n\)-정확도를 만족한다.
정리 3.3에 따르면, 고정된 정확도 목표 \(\alpha n\)을 달성하기 위해 \((1/2 + \ln 3) \alpha n\) 단위의 개인정보 보호를 구매해야 한다.
MinCostAuction은 정확히 필요한 만큼의 개인정보 보호를 구매하도록 설계되었기 때문에 \(\alpha n\)-정확도를 만족한다.
2. 차등 개인정보 보호 수준 (\(\epsilon_i\)) 설정
정리 3.3에 따라, 선택된 개인 \(i \leq k\)에 대해 \(\epsilon_i = \frac{1}{\alpha^{\prime} n}\), 선택되지 않은 개인 \(i > k\)에 대해 \(\epsilon_i = 0\)이 성립한다. 즉, 정확히 필요한 개인정보 보호 수준만 구매함으로써 최적의 지불 구조를 유지한다.
3. 진실성과 개별 합리성 증명
MinCostAuction에서 각 개인 i의 비용은 다음과 같이 정의된다.
\(v_i = c_i(1/(\alpha^{\prime} n))\)
MinCostAuction은 전형적인 VCG(Vickrey-Clarke-Groves) 메커니즘의 한 변형(instantiation of the classical VCG mechanism)이므로,
- 각 개인이 자신의 비용을 거짓으로 보고할 유인이 없음 (진실성 보장)
- 각 개인이 자신의 실제 비용보다 낮은 보상을 받지 않음 (개별 합리성 보장)
MinCostAuction이 목표로 하는 효용(utiltiy)을 다음과 같은 총 비용으로 달성한다.
\(\sum_{i=1}^{n} p_i = k \cdot v_{k+1}\)
즉, 총 비용은 선택된 k명의 개인에게 지급된 총 금액이고, 이때 각 개인은 \(v_{k+1}\) 만큼의 비용을 지급받는다.
MinCostAuction에서 각 선택된 개인은 \(p_i = v_{k+1}\) 만큼을 받으므로 총 비용은 \(k \cdot v_{k+1}\)이다.
다른 시기심 없는 경매가 더 적은 비용을 지불할 수 없는 이유는, 만약 어떤 다른 시기심 없는 다중 단위 조달 경매가 k개의 개인정보 보호 단위를 구매하면서 더 적은 비용을 지불하려 한다면, 최소한 다음 조건을 만족해야 한다.
\(p_1 = p_2 = \dots = p_k \leq v_{k+1}\)
그러나, 시기심 없는(envy-free) 조건에 의해, 모든 선택된 개인들은 동일한 지불금을 받아야 하므로, 각 개인에게 \(v_{k+1}\) 미만을 지급할 경우, 최소 비용을 요구하는 개인이 거부할 수 있기에 이보다 더 낮은 비용을 지불하는 경매는 불가능하다.
즉, MinCostAuction은 같은 정확도를 보장하는 시기심 없는 메커니즘 중에서 최소 비용을 달성하는 최적의 경매이다.
5. Preserving the Privacy of the Bid
이전 섹션(Section 4)에서는 진실성(truthfulness)과 개별 합리성(individual rationality)을 만족하는 메커니즘을 고려했다.
이러한 메커니즘은 각 개인이 제공하는 데이터(즉, 개인의 비트 \(b_i\))를 사용하는 것에 대한 프라이버시 손실을 보상하는 구조였다.
그러나 이전까지는 각 개인의 개인정보 보호 비용(valuation for privacy, \(v_i\))을 별도의 프라이버시 보호 대상으로 고려하지 않았다.
즉, 메커니즘이 개인의 \(b_i\) 를 사용하는 것에 대해서는 보상하지만, 개인의 \(v_i\) 를 사용함으로 인해 발생하는 프라이버시 손실은 고려되지 않았다.
Q. 새로운 문제: \(v_i\) 도 프라이빗 데이터로 간주할 수 있는가?
우리는 각 개인의 개인정보 보호 비용( \(v_i\) ) 역시 프라이빗 데이터로 간주하고, 이를 보호하는 메커니즘을 설계할 수 있을까?
현실적으로, 개인의 개인정보 보호 비용 \(v_i\) 는 개인의 실제 데이터 \(b_i\) 와 상관관계를 가질 가능성이 높다.
예를 들어, 어떤 사람이 높은 개인정보 보호 비용을 요구한다면, 이는 그가 매우 민감한 정보를 가지고 있음을 의미할 가능성이 있다. 따라서, 메커니즘이 \(v_i\) 를 사용하면, 간접적으로 개인의 비트 \(b_i\) 에 대한 정보도 노출될 위험이 있다.
질문: 개인의 개인정보 보호 비용 \(v_i\) 도 보호하면서도, 이를 사용하여 적절한 보상을 제공하는 메커니즘을 설계할 수 있는가?
– 불가능하다.
메커니즘의 두 가지 출력
: 추정값 \(\hat{s}\) (estimate), 데이터 분석가가 지급해야 하는 총 지불금 P (payment)
만약 입찰 금액(bid) \(v_i\)도 비공개 데이터로 간주된다면, 메커니즘은 각 개인 i에 대해 차등 개인정보 보호를 만족해야 한다.
Theorem 5.1. 입찰자의 개인정보 보호 비용을 보호하는 것이 불가능함
만약 입찰자의 개인정보 보호 비용( \(v_i\) )이 임의로 클 수 있다면,
어떤 개별 합리적인(individually rational) 메커니즘도 입찰자의 개인정보 보호 비용을 보호하면서도, k < n/2 인 k-정확도를 보장할 수 없다.
즉, n/2 미만의 정확도를 달성하는 비(非)사소한(nontrivial) 메커니즘은 존재할 수 없다.
왜 프라이버시 평가 \(v_i\)를 보호하면서 보상하는 것이 불가능한가?
이 섹션에서는 만약 개인이 프라이버시 평가 \(v_i\)에 대해 임의로 높은 값을 설정할 수 있다면, 이러한 메커니즘을 설계하는 것은 본질적으로 불가능하다는 점을 보인다.
더 나아가, 개인의 프라이버시 평가 \(v_i\)에 사전적으로 상한선을 설정하려고 하면, 경매를 통해 해결하고자 했던 표본 추출 편향(sampling bias) 문제가 다시 발생하게 된다.
1) 높은 가격을 부를 수 있다.
– 경매에서는 참가자들이 자신이 생각하는 프라이버시 가치 \(v_i\)를 직접 입력한다.
– 하지만 만약 \(v_i\)가 프라이버시 보호를 받아야 한다면, 이를 제한할 방법이 없다.
– 즉, 어떤 사람이 ‘나는 내 데이터를 공개하는 대가로 1억 원을 받아야 해’라고 하면, 이를 막을 방법이 없다.
→ 모든 사람이 자신이 원하는 만큼 높은 \(v_i\)를 설정할 수 있다면, 경매는 성립하지 않는다.
2) 상한선을 설정하면 샘플링 편향(bias)이 생김
– \(v_i\) 값에 제한을 두면 되지 않을까? 예를 들어, ‘최대 100달러까지만 보상해준다’라고 하면 어떨까?
– 프라이버시를 중요하게 여기는 사람들(높은 \(v_i\)를 가진 사람들)은 경매에 참여하지 않을 가능성이 높다.
– 결국, 경매에서 확보한 데이터가 전체 모집단을 제대로 대표하지 못할 가능성이 커진다.
– 이것은 경매를 통해 해결하려 했던 대표성 문제(sampling bias)를 다시 불러오게 된다.
3) 수학적 조건: DP 보호의 한계
– 논문에서는 \(v_i\)를 DP로 보호해야 한다면, 특정한 확률 조건을 만족해야 한다고 설명한다.
– 만약 \(v_i\)가 보호된다면, 경매 결과(추정값과 보상)가 \(v_i\)의 변화에 따라 급격하게 변하면 안 된다.
– 하지만, 보상을 지급하려면 결국 \(v_i\)를 고려해야 하므로, 이 조건을 만족하면서 공정한 보상을 주는 것이 불가능하다.
– \(v_i\)를 보호하면서도 공정한 보상을 제공하는 것은 이론적으로 불가능하다.
결론 – Theorem 5.1
1) \(v_i\)를 무제한으로 허용할 경우, 참가자가 1억원 같은 비현실적인 가격을 요구할 수 있어 경매가 성립하지 않음
2) \(v_i\)에 상한선을 설정할 경우, 프라이버시를 보호하게 여기는 참가자가 빠지면서 샘플링 편향이 생김
3) \(v_i\)를 DP로 보호할 경우, 보상을 계산할 때 \(v_i\)를 고려해야 하므로, 프라이버시 보호와 보상을 동시에 할 수 없음
→ 프라이버시 평가 \(v_i\)를 보호하면서도 보상을 제공하는 것은 불가능하다. / k-정확도를 유지하는 개별 합리적인 메커니즘은 존재할 수 없다.
Remark 5.2
이 문제를 해결하는 방법은 입찰자의 프라이버시 평가 \(v_i\)가 특정한 범위 (e.g. [0, 1]) 내에 있도록 제한하는 것이지만, 이 방법은 만족스럽지 않다.
우리가 경매를 통해 해결하려고 했던 표본 추출 편향(sampling bias) 문제가 다시 발생하기 때문이다.
6. Future Directions
개인 데이터 경매(auction for private data) 개념을 형식화하고, 이러한 경매의 설계 공간이 다중 단위 조달 경매로 단순화할 수 있음을 보인 것이다.
향후 연구 질문
- 경매의 적절한 벤치마크란 무엇인가?
본 논문에서는 fixed-price 또는 envy-free 메커니즘을 벤치마크로 사용했다.
이러한 접근 방식은 사전 분포가 없는(prior-free) 메커니즘 설계에서 표준적으로 사용되는 방법이지만, 이는 베이지안 최적 메커니즘(Bayesian optimal mechanism)이 잘 알려져 있는 환경에서 더 적합한 방식이다.
그러나, 본 논문에서 다룬 예산 제한이 있는 경매(budget-constrained auctitons)에서는 베이지안 최적 메커니즘이 알려져 있지 않다. 따라서, 베이지안 최적 메커니즘을 연구함으로써, 보다 적절한 벤치마크를 정의하는 것이 중요하다. - 프라이버시 평가(privacy valuation)의 보호 및 보상 문제
개인의 프라이버시 평가 \(v_i\)가 개인의 데이터 \(b_i\)와 상관관계를 가질 수 있음을 보였다.
그러나, 이러한 상관관계는 실제로 존재하며, 이를 완전히 배제하는 것은 만족스럽지 않다.
프라이버시 평가를 제한된 범위 내에서 설정하는 방법도 제안될 수 있지만, 이는 다시 샘플링 편향 문제를 초래할 수 있다.
그렇다면, 특정한 조건 하에서 프라이버시 평가의 프라이버시를 보호하면서 보상할 수 있는 방법이 있을까? 이를 위해서는 새로운 모델이 필요할 것이다. - 데이터가 중앙 관리자에게 저장되지 않은 경우
사용자의 프라이빗 비트 \(b_i\)가 병원과 같은 중앙 데이터베이스 관리자에게 이미 알려져 있다고 가정했다.
그러나 모든 상황에서 이러한 가정이 성립하는 것은 아니다.
만약 개인이 직접 자신의 데이터를 보유하고 있으며, 이를 거짓으로 보고할 수도 있다면 어떻게 할 것인가?
개인이 자신의 데이터를 속일 가능성을 고려한 새로운 메커니즘이 필요할 것이다. - 다중 데이터 분석가(multi-sided market) 환경
본 논문에서는 단일 데이터 분석가가 하나의 연구 집단으로부터 데이터를 구매하는 단순한 시장을 가정했다.
그러나 현실에서는 여러 명의 데이터 분석가들이 다양한 연구 집단의 데이터를 구매하려 경쟁할 가능성이 있다.
이러한 환경에서, 프라이버시를 보호하면서 시장 균형 가격을 계산할 수 있을까?
다중 시장 모델을 연구하여, 데이터 분석가와 데이터 제공자 간의 상호작용을 보다 현실적으로 분석할 필요가 있다. - 반복적인 데이터 판매 환경에서의 문제
본 논문에서는 단발성 경매(one-shot auction)만 고려했다.
그러나 현실에서는 데이터베이스 관리자가 시간이 지남에 따라 여러 번 데이터 접근 요청을 받을 가능성이 높다.
그렇다면 데이터 분석가는 각 요청에 대한 응답을 어떻게 결정해야 하며, 추가적인 프라이버시 손실(marginal privacy loss)을 어떻게 평가해야 할까?
반복적인 경매와 온라인 학습을 고려한 메커니즘 설계가 필요할 것이다.
+) 한계
1) 프라이버시 비용과 데이터 제공 여부 사이의 상관관계
• 일부 참가자는 자신의 데이터가 민감할수록 더 높은 프라이버시 비용을 요구할 수 있음.
• 하지만 고정 가격 메커니즘은 이러한 차이를 반영하지 못할 수 있음.
2) 동적인 환경에서의 최적 가격 설정 문제
• 시장의 참가자 수가 변할 경우, 고정 가격을 어떻게 조정할 것인가?
• 최적의 가격을 실시간으로 동적으로 조정할 필요가 있을 수도 있음.
3) 반복적 거래(repeated auction) 환경에서의 문제
• 동일한 참가자가 여러 번 참여하는 경우, 가격 조정 전략이 필요함.
• 참가자들이 전략적으로 응답할 가능성이 커질 수 있음.
→ 참가자의 프라이버시 비용을 결정할 때, 데이터 민감도(sensitivity score)를 반영한 동적 가격 책정 모델을 도입.
• 예를 들어, 의료 데이터와 같이 고유하게 민감한 정보일수록 더 높은 보상을 지급하도록 메커니즘을 조정.
• 데이터의 민감도가 높을수록 프라이버시 비용을 더 높게 반영하여 공정성을 보장.
• 현실 세계의 데이터는 시간이 지남에 따라 변화한다. 예를 들어, 사용자의 행동 패턴, 시장 상황, 질병 발생률 등은 동적으로 변화하기 때문에, 기존 데이터를 반복적으로 업데이트해야 한다. 따라서 데이터 분석가는 지속적으로 데이터를 구매하여, 최신 정보를 반영해야 한다.
References
Ghosh, Arpita, and Aaron Roth. “Selling privacy at auction.” Proceedings of the 12th ACM conference on Electronic commerce. 2011.