統計数理研究所オープンハウス 公開講演会「プライバシー保護とデータサイエンス」（2024/5/24）

差分プライバシーと統計解析への応用
村上 隆夫（統計数理研究所

学際統計数理研究系）

本講演の内容
 差分プライバシー（Differential Privacy）

個人のプライバシーを保護しながら統計解析を行う際の安全性指標のデファクト標準
 Google、Apple、Microsoftなどが導入。2020年に米国国勢調査においても導入
 強固な安全性を保証すると言われているが、安全性の概念が分かりづらいとよく言われる。。。


 本講演

1) 差分プライバシーとはどのようなものか？
 2) どのような安全性を保証するのか？
 3) 差分プライバシーを満たす技術としてどのようなものがあるか？
 といった差分プライバシーの概要について、なるべく分かりやすく説明

その後、具体的な統計解析への応用例をご紹介

本講演の内容
背景（プライバシー問題、具体例、プライバシー保護研究の歴史）

差分プライバシー（差分プライバシーとは、どのような安全性を保証するか、差分プライバシーを満たす技術）

統計解析への応用例（Yes/Noの分布推定、Googleの事例、グラフ統計解析）

背景 プライバシー問題

IoT、人工知能の普及に伴い、パーソナルデータの利活用への期待が高まっている 一方、プライバシーの問題が懸念されている
スマートフォン・ウォッチセンサ
スマートメータ

音声，位置情報,身体活動, etc.

画像・動画
電力量
パーソナル
データ

統計情報

パーソナルデータ
機械学習モデル漏洩背景 例1: 統計情報からのデータの漏洩

時間帯ごとの人口分布から、各個人の位置情報が復元される恐れがある[1]位置情報DB
ユーザ 移動履歴
u 1 x2 x3 x3 x4

位置情報 xi

u2x1x2x4x4

u3x1x3x5x4

時刻1 (7AM)

時刻2 (8AM)

104

104

102

10200106

復元[1] A. Pyrgelis et al., “What Does The Crowd Say About You? Evaluating Aggregation-based Location Privacy,” PoPETs, 2017.

106背景 例2: 機械学習モデルからのデータの漏洩

深層学習モデルから、どのユーザが学習に用いられたかが推定される恐れがある [2]

学習が学習に用いられている

メンバーシップ推定[2] R. Shokri et al., “Membership Inference Attacks Against Machine Learning Models,” S&P’17.

背景 例3：2010年米国国勢調査に対する再構築攻撃[3]

2010年米国国勢調査の集計表から、元のデータベースを部分的に復元できることが示された

集計表1

集計表2

集計表3

元DB

復元

 2020年米国国勢調査では、差分プライバシーが導入[4][3] J. Abowd, Declaration of John Abowd, State of Alabama v. United States Department of Commerce. Case No. 3:21-CV-211-RAH-ECM-KCN, 2021.
[4] 寺田，“2020年米国国勢調査への差分プライバシーの導入に関する考察”，月刊統計（特集：プライバシー保護技術の新展開），2022.8背景 プライバシー保護研究の歴史

20年ほど前は攻撃と防御のいたちごっこの世界 homogeneity attack background knowledge attack[Machanavajjhala+, ICDE06]
 skewness attack
 similarity attack[Li+, ICDE07]
安全性指標：

k-匿名性

l-多様性

1998

2006

2007

このような中、どのような攻撃に対しても安全性を理論的に保証する「差分プライバシー」が登場

本講演の内容
背景（プライバシー問題、具体例、プライバシー保護研究の歴史）

差分プライバシー（差分プライバシーとは、どのような安全性を保証するか、差分プライバシーを満たす技術）

統計解析への応用例（Yes/Noの分布推定、Googleの事例、グラフ統計解析）

差分プライバシーとは？
 差分プライバシー（DP: Differential Privacy）[5]「あるユーザのデータがDBにいてもいなくても、データ解析結果がほぼ同じ」になることを理論的に保証する安全性指標のデファクト・スタンダード
データベース𝐷𝐷

データベース𝐷𝐷𝐷or

データ解析結果𝑦𝑦
加工メカニズムℛ

𝐷𝐷 or 𝐷𝐷′？

攻撃者

定義（𝜺𝜺-DP）
任意の隣接する（あるユーザが一方にのみ含まれる）データベース𝐷𝐷, 𝐷𝐷𝐷と任意の出力データ𝑦𝑦に対してPr(𝑦𝑦|𝐷𝐷) ≤ 𝑒𝑒 𝜀𝜀 Pr(𝑦𝑦|𝐷𝐷𝐷)が成立するとき、加工メカニズムℛは𝜺𝜺-DPを満たすという（𝜀𝜀: privacy budget）
𝜀𝜀が小さいとき（例：0～1）、Pr(𝑦𝑦|𝐷𝐷)とPr(𝑦𝑦|𝐷𝐷𝐷)が近い値となる [5] C. Dwork, A. Roth, “The Algorithmic Foundations of Differential Privacy,” Now Publishers Inc., 2014.

がいるのか判別しづらいどのような安全性を保証するか？
 仮説検定としての解釈[6]

攻撃者が、𝑦𝑦を基に𝐻𝐻0 と𝐻𝐻1 に関する仮説検定を行うことを考える
 DPとtype I error（𝐻𝐻0 を誤って𝐻𝐻1 と判定）とtype II error（𝐻𝐻1 を誤って𝐻𝐻0 と判定）の関係は？
データベース𝐷𝐷

データベース𝐷𝐷𝐷

or
帰無仮説𝐻𝐻0 （ がいない）

データ解析結果𝑦𝑦

加工メカニズムℛ

対立仮説𝐻𝐻1 （ がいる）

定理（[6] Theorem 2.4）

加工メカニズムℛが𝜺𝜺-DPを満たすならば、以下が成立する．

例：𝜀𝜀 = 0.1

1 − (type II error) ≤ 𝑒𝑒 𝜀𝜀 (type I error)

type II error = 𝟎𝟎. 𝟒𝟒𝟒𝟒のとき、type I error ≥ 𝟎𝟎. 𝟒𝟒𝟒𝟒
（ほぼrandom guessの精度しか出ないので安全）[6] L. Wasserman and S. Zhou, “A Statistical Framework for Differential Privacy,” Journal of the American Statistical Association, 2010.

攻撃者差分プライバシーを満たすメカニズム
 元々の差分プライバシーが仮定するモデル ＝ 中央集権型モデル（Central Model）

サービス事業者がユーザからデータを集める データ解析結果𝑦𝑦（例：ヒストグラム）にランダムなノイズを付与し、第三者提供 or 公開

データベース𝐷𝐷
データ x1 x2 x3 x4 x5

x1 x2 x3 x4 x5

データ解析結果𝑦𝑦
加工
メカニズムℛ

サービス事業者

例：ラプラスメカニズム
ヒストグラムの各binにラプラス分布に従ったランダムなノイズを付与する  𝜺𝜺-DP

攻撃者

差分プライバシーを満たすメカニズム 中央集権型モデルの課題

不正アクセスなどにより、全ユーザの元データが漏洩する恐れあり
データベース𝐷𝐷

不正アクセスx1 x2 x3 x4 x5

漏洩

元データ x1 x2 x3 x4 x5

サービス事業者
 局所型モデル（Local Model）

ユーザがサービス事業者を信用せず、自身のデータにノイズを加える
 出力データyiは差分プライバシーを満たし、元データxiに関する情報がほとんど漏洩しない


x1

加工
メカニズムℛ

y1x5

加工
メカニズムℛy5

サービス事業者

差分プライバシーを満たすメカニズム
 局所型差分プライバシー（LDP: Local Differential Privacy）

定義（𝜺𝜺-LDP）
任意の元データ𝑥𝑥, 𝑥𝑥𝑥 ∈ 𝒳𝒳（𝒳𝒳：定義域）と出力データ𝑦𝑦 ∈ 𝒴𝒴（𝒴𝒴：値域）に対して𝑥𝑥𝑥Pr(𝑦𝑦|𝑥𝑥) ≤ 𝑒𝑒 𝜀𝜀 Pr(𝑦𝑦|𝑥𝑥′)が成立するとき、加工メカニズムℛは𝜺𝜺-LDPを満たすという𝜀𝜀が小さいとき（例：0～1）、出力データ𝑦𝑦を見ても入力データ𝑥𝑥の値が分からない
入力データ𝑥𝑥

出力データ𝑦𝑦
加工メカニズムℛ𝑥𝑥

𝑦𝑦𝑥𝑥 or 𝑥𝑥𝑥？

例：RR (Randomized Response)

𝑥𝑥

10𝑝𝑝

1 − 𝑝𝑝𝑝𝑝

𝑦𝑦

10𝑒𝑒 𝜀𝜀𝑝𝑝 = 𝜀𝜀𝑒𝑒 + 1

本講演の内容
背景（プライバシー問題、具体例、プライバシー保護研究の歴史）

差分プライバシー（差分プライバシーとは、どのような安全性を保証するか、差分プライバシーを満たす技術）

統計解析への応用例（Yes/Noの分布推定、Googleの事例、グラフ統計解析）

LDPを満たす分布推定 例1： Yes/Noの分布推定「今までにテストでカンニングをしたことがありますか？」（1: yes, 0: no）[7] 加工メカニズム ⇒ RR（Randomized Response）を使用
 入力分布𝐩𝐩の推定法 ⇒ 逆行列法[8]を使用
入力分布𝐩𝐩

RR 𝐑𝐑

0.7𝐩𝐩(1) = 0.2 10.3𝐩𝐩(0) = 0.8 00.7

出力分布𝐪𝐪1 𝐪𝐪(1) = 0.380 𝐪𝐪(0) = 0.62

0.7 0.3
0.38 0.62 = 0.2 0.80.3 0.7𝐩𝐩
𝐪𝐪
𝐑𝐑

RRはε-LDPを満たす（ε = 0.85）

推定値�
𝐩𝐩

�(1) = 0.25 1𝐩𝐩

逆行列𝐑𝐑−𝟏𝟏1.75

�(0) = 0.75 0𝐩𝐩

0.25 0.75 = 0.4 0.6
�𝐩𝐩

�𝐪𝐪

経験分布�𝐪𝐪

�(1) = 0.41 𝐪𝐪-0.75
�(0) = 0.60 𝐪𝐪
1.75

1.75 -0.75-0.75 1.75
𝐑𝐑−𝟏𝟏

プライバシーを保護したまま、入力分布𝐩𝐩が推定できる[7] B. Bullek et al., “Towards Understanding Differential Privacy: When Do People Trust Randomized Response Technique?,” CHI’17.
[8] R. Agrawal et al., “Privacy Preserving OLAP,” SIGMOD’05.

LDPを満たす分布推定 例2： Googleの事例[9]

Google独自のLDPメカニズムRAPPORを用いて、Chromeの起動ページの分布を推定

x1

RAPPOR（ε-LDP）

xn

RAPPOR（ε-LDP）

y1

yn

起動ページの分布

Google[9] U. Erlingsson et al., “RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response,” CCS’14.

LDPを満たすグラフ統計解析[10] グラフ統計（部分グラフ数）#triangles = 三角形の数、#𝑘𝑘-stars = 𝑘𝑘個のnodeが繋がっている星の数
ShapeNameCountTriangle

22-star153-star6

 何に使えるか？
「友達の友達が友達である確率」 = 3 ×友達？

#triangles
 友達推薦の有効性が分かる#2−stars[10] J. Imola, T. Murakami, K. Chaudhuri, “Locally Differentially Private Analysis of Graph Statistics,” USENIX Security’21.

LDPを満たすグラフ統計解析[10] プライバシー問題#triangles/#𝑘𝑘-starsから、秘密にしたい友達情報（edge）が漏洩する可能性がある
 例：𝑣𝑣2 が攻撃者の場合
𝑣𝑣3
Shape

𝑣𝑣1
𝑣𝑣6

𝑣𝑣4

𝑣𝑣2
𝑣𝑣7

Name

Count2-star20Triangle

5𝑣𝑣5

𝑣𝑣3 , … , 𝑣𝑣7 同士の友達情報は全部知っている。
𝑣𝑣1 は誰と友達なのだろう？

漏洩

𝑣𝑣1 の友達は𝑣𝑣3 , 𝑣𝑣4 , 𝑣𝑣6

プライバシーを強固に保護するには、部分グラフ数（#triangles/#𝒌𝒌-stars）にノイズを加える必要があり[10] J. Imola, T. Murakami, K. Chaudhuri, “Locally Differentially Private Analysis of Graph Statistics,” USENIX Security’21.

LDPを満たすグラフ統計解析[10] LDP

各ユーザが友達リスト（誰と繋がっているかの情報）に対してLDPを満たすノイズを加える
 攻撃者は、隣接グラフ（あるedgeが一方にのみ含まれる2つのグラフ）𝐺𝐺, 𝐺𝐺′のどちらから来たのか区別できない  友達関係を秘匿
友達リスト

友達リスト

加工メカニズムℛ（ε-LDP）

Shape

加工メカニズムℛ（ε−LDP）

𝐺𝐺

or[10] J. Imola, T. Murakami, K. Chaudhuri, “Locally Differentially Private Analysis of Graph Statistics,” USENIX Security’21.

𝐺𝐺′

Name

Count2-star

22Triangle

4
𝐺𝐺 or 𝐺𝐺𝐺？

LDPを満たすグラフ統計解析[10] LDPを満たす𝑘𝑘-starsの数え上げ[10]

各ユーザは自身の#𝑘𝑘-starsを知っている  1ラウンドで高精度に推定できる（Lap: ラプラスノイズ）
1ラウンド目#2-stars = 3#𝑘𝑘-stars + Lap.
 LDPを満たすtrianglesの数え上げ[10]各ユーザは友達同士が繋がっているか分からないため、自身の#trianglesを知らない  2ラウンド導入すれば、1辺だけnoisyなtriangleが数えられるようになり、高精度に推定できる


1ラウンド目
noisy graph

2ラウンド目=1

友達リスト（RR）[10] J. Imola, T. Murakami, K. Chaudhuri, “Locally Differentially Private Analysis of Graph Statistics,” USENIX Security’21.

noisy graph#triangles + Lap.

今後の展望 LDPの課題

各ユーザがノイズを加える分、ノイズ量が大きい  ユースケースによっては精度が全然でない 例：ユーザ数が少ないと推定誤差が大きい
 今後の展望：MPC-DP

秘密計算（MPC: Multi-Party Computation）を用いて、データが秘匿された状態でノイズを付与
 Local modelのように自身のデータは誰にも見られず、Central modelと同じ精度を達成できるCentral model

MPC-DP model
MPC
𝑥𝑥1𝑥𝑥5server

データ解析結果𝑦𝑦

データベース𝐷𝐷x1 x2 x3 x4 x5

serverserver

サービス事業者

データ解析結果𝑦𝑦ご清聴ありがとうございました