データ利活用のためのプライバシー保護技術
統計数理研究所
南 和宏
2024年5月24日
統計数理研究所オープンハウス2024公開講演会

本日の内容• データ利活用における出力プライバシー• 統計開示抑制と安全性ルール• 統計表の表セル秘匿処理とマッチング攻撃• 今後の方向性2

秘密計算による入力プライバシー保護• 入力データの機密性を保証しつつ関数𝑓(𝑥)を計算
入力データ

公開されるのは関数の出力値のみ

x1
x2

Sum関数

x! + x" + ⋯ + 𝑥#

STOP

入力
プライバシー保護x10

入力の推 デー
測 タ

計算プロセスの観察

3

もしデータ提供者が二人だったら。。
出力データから入力データの推定を防ぐ「出力プライバシー」の保証が別途必要

x1

Sum関数

x1 + x2x2x2の導出
4

統計開示制御 (Statistical Disclosure Control)
による出力プライバシー保護• 統計量の開示から入力データが推定されるリスクを抑制する方法論• 公開するデータを修正、削除することで、統計開示のリスクを減少させる• しかし公開するデータをあまり劣化させると、データが活用できない– 一般には機密情報の保護を拘束条件として、情報の有用性の最大化を目指す最適化問題として定式化される
5

９人の共謀が必要

客体１０の原則• 10個以上入力値があれば共謀は困難

x1x2

Sum関数

x9x10

推をX 10

た
し定

x! + x" + ⋯ + 𝑥!$る
すいと6占有性の原則• 入力データが多数あっても、一つの入力値が突出しておおきくてはいけない（例：70％以上）
x1

S = x! + x" + ⋯ + 𝑥!#xx2

Sum関数

x10x2を合計値𝑆で近似できてしまう

２7

統計表の統計開示抑制• 統計表は最も基本的な記述統計• 国が行う公的調査から多くの統計表が一般に公開されている• 表の各セル値にØ最小度数ルール
Ø占有性ルールを適用し、安全性を確認

外部者による攻撃度数分布表集計表

地域

職種
P1P2P3P4P5

合計

M1201530201095

M2722013010133

M3383815402133

合計

13073

469022361

P1P2P3P4P5

合計

M1360

450

720

400

360

2290

M21440

540

22570

320

2892

M3722

1178

375

800

363

3438

合計

2522

2168

1117

1770

1043

8620

収入の合計

9

内部者（調査対象者）による攻撃

度数分布表

地域

職種
P1P2P3P4

M120153020

1095

M2722013010133

M3

38

38

15402133

合計

13073

4690

22361

P5

合計

自分の収入を引けばもう一人の収入が分かる
P1P2P3P4

集計表

自分の属性
合計
P5は知っている

M1360

450

720

400

3602290

M21440

540

22570

320

2892

M3722

1178

375

800

363

3438

合計

2522

2168

1117

1770

1043

8620

収入の合計

10

行計、列計の関係式から値が復元されてしまうのを防ぐためには２次秘匿が必要
集計表

NA (Not Available)
P1

P2P3

合計

M120242872M23838NA116

121

M3403942121309

合計

98101110309

P1P2P3

合計

M1202428

72

M2383840116

M3403942

合計

98101110１次
秘匿

表の各セルに最小度数ルール、占有性ルールを適用

占有性ルール
を侵害

２次秘匿
P1P2P3

合計

M1NA24NA72

M2NA38NA116

M3403942121合計9810111030911この秘匿処理は安全か？
B1B2B3B4

計

A1

7

1060

1390

A211601260

143A360

1160

12143

A414601360147

計

92

141

145

145

523

B1B2B3B4計

A1

x1x2

60x390A2x460x560

143

A360x660x7

143

A4x860x960147

計

92

141

145

145

523
12

x1は特定される+x1 + x2 + x3x2x3= 30+ x6
= 21+ x7 = 25x1

- x6 – x7 = -16-x6 + x7 = 23

x1 = 713

the bipartite network of Figure 6. This al行計、列計の関係式から
k optimization algorithms, such as those for
秘匿セルの値が復元される
st-paths [1]. This
fact was originally noticed
in other works [4, 5, 6, 9, 14, 23, 29].

• r行c列の表には (r+c)個の線形制約条件が存在

a11. . . a1ca1(c+1)...
... ...
...
ar1. . . arc
ar(c+1)a(r+1)1 . . . a(r+1)c a(r+1)(c+1)
cX

aij = a(r+1)jc
X

aij = ai(c+1)

i = 1, . . . , rj=1

j = 1, . . . , ci=1

安全性の検証には線形計画法の問題を解く必要がある

14

table with only one primary cell in boldface; removing this cell is not enough, since
its value can be retrieved from marginals, thus forcing the suppression of three additional complementary cells.

•

秘匿セルの取りうる値の範囲が十分広いことが安全性の要件
Fig. 10 Original
table with
Original tableProtected tableprimary cell in boldface, andP1 P2 P3 TOTALP1 P2 P3 TOTAL
秘匿セル変数の可能範囲（）の幅wの長さがprotected table after suppresM1 20 24 2872
M1
2472
sion of three secondary cells.
M2 38 38以上であること
40 116
M238116
しきい値 tM3 40 39 42 121
M3 40 39 42 121
P1 TOTAL
P2 98 101P3110 合計309 TOTAL 98 101 110 309

秘匿インターバル（度数分布表では１０）
M1x11

24x1372

From the protectedMtable
ofxFigure10,
may deduce a lower and upper
38 any attacker
116
x23
221
bound for the primary cell. Indeed, considering variables x11 , x13 , x21 , x23 for theM340
3942
121
primary and secondary
cells, a lower bound a23 and an upper bound a23 for the合計
101110309
primary cell can beobtained98by solving

1. 最小値問題
a23 = min x23
subjectto x11 + x13 = 72 − 24
拘束条件:x21 + x23 = 116 − 38
x11 + x21 = 98 − 40
x13 + x23 = 110 − 42(x11 , x13 , x21 , x23 ) ≥ 0

2. 最大値問題
a23 = max x23
subjectto x11 + x13 = 72 − 24
拘束条件:
x21 + x23 = 116 − 38
and(8)
x11 + x21 = 98 − 40
x13 + x23 = 110 − 42(x11 , x13 , x21 , x23 ) ≥ 0.

and ax23 =68. If, for instance, lower and upperThesolutions to (8) are a23w==20max
秘匿インターバル
23 – min x23 = 68 – 20 = 48 > 1015
protection levels of l pl = upl = 10 were imposed (i.e., the protection pattern must
guarantee that no attacker can deduce a value of the sensitive cell within the range

表セル秘匿問題• 秘匿パターンyi 2 {0, 1} i = 1, . . . , n10NA580(0,1,0,0)• 目的関数: 秘匿セル数nX

yi

最小化を目指す

i=1• 拘束条件：各１次秘匿セル値の機密性保護
16

秘匿インターバルの要件
秘匿インターバルの幅 w = xij

xij >秘匿インターバル幅のしきい値 δ

秘匿インターバル

xij

aij

xij

下限値

セル値

上限値

行計、列計の線形式を満足する値の範囲

17Benders分割アルゴリズムによる効率的な実装• 主問題と部分問題に分割– 主問題：秘匿パターンの最適化– 部分問題：各秘匿セルの拘束条件のチェック• 最適化問題はNP困難であるが、大部分の表データを効率的に実行• アルゴリズムが終了した場合は、最適解を保証

主問題

秘匿パターン部分問題充足しない拘束条件の追加

拘束条件を全て満たすか？

最適秘匿パターン

Yes

No
18

ただし、秘匿アルゴリズムが攻撃者の手に渡るとマッチング攻撃が可能
秘匿セルの値を補完秘匿された元テーブル

元テーブル

セル秘匿アルゴリズム

候補テーブル

決定的：
同じ入力には同じ結果を出力

マッチング
秘匿された
候補テーブル19
秘匿パターンが再現できた候補テーブルの値のみが真の候補値！

秘匿セルの候補値の列挙• 秘匿セルの候補値ベクトルｘ は行計、列計に関する線形の拘束条件を満たす
Ax = b• 行列Aの零空間N(A)は
N (A) = {y 2 Z n | Ay = 0}

• Ax = b の解の集合S は
S = {v + y | Av = b ^ y 2 N (A)}20

Sum5146

62
M2 3319 192
x1 13 x255
M3 are8four 8 11 14 41
2 Suppose that we have a suppressed table in Table 1. Therethearelinearof the form Ax = b 9in (14)x3 are26 represented
x444 ascells whose cellThen,variables
v1 , vequations
2 , v3 , and v4 , respectively.M423 2 Sum
3 251 3 46 62 33 192
1 1 0 0 x1
23n example of a suppressed table. Each suppressed
i is6represented
by60 0 1cell17
767x
97 6 2 7 =of6the7form Ax = b in (14) are repre
ble vi .
Then,6thelinearequations(17454545
1010x23P1 P2 P3 P4 Sum
2332 3 2 3x41 1 09. 0 x123M1 15 15 12 10 052 1 0 1
6 0 0 1 17 6 x2 7 6 9 7
M2 19 x1 13 x255
676 7 = 6 7TA vectorv=[14,9,9,0]
isasolution
toequation(17)
41 0 1 05 4andM3
88 11 14 41x3 5 the4null
235 space N (A)represented
M4
9 asx3 26 x4
440 1 0 1 x4
9.
Sum 51 46 62 33 192⇢⇥⇤TTANvectorv=[14,9,9,0]
isasolution
toZequation (17) and the (18nu1111(A)=k|k2Ax = b秘匿テーブル
he linear equations of theformrepresentedAx = b in (14)as are represented as
232 3 2 3⇢1
100x1 takes23⇥ represent the⇤T set S of all possib
Since each variablea non-negative value, we
11 1 | k2Z
N (A) = k 1
6 0 0 1 17 6 x2 7 6 9 7
combinations
ofcellvalues
as6767
67(17)
解集合
41 0 ⇢1 05 4x3 5 = 4235
⇤T9. variable⇥⇤T0 1 0⇥ 1xSince
eachtakes
anon-negative
represent
411 1 | k 2 Zvalue,
S = 14 9 9 0 + k 1^ we0k  9 the set(19combinations of cell values as= [14, 9, 9, 0]T is a solution to equation ⇢(17) and the null space N (A) is⇥⇤T space⇥ is 1, but, in⇤general,asT
In this example, the dimensionof the null
the null spa
14
9
90
1
1
1
1
S=+k|k2
Z ^ 0
⇢（この例では１次元）
Ax=bの特定の解零空間N(A)is represented
as a linear⇥⇤T combination of multiple column vectors.

例：秘匿セル候補値の列挙

N (A) =k 1

11 1| k2Z(18)21
In this example, the dimension of the null space is 1, but,in genera
9
is represented
as athelinear
variable takes a non-negative value,
we represent
set S combinationof all possibleof multiple column vectors.

秘匿インターバルの絞り込み
秘匿
インターバル

マッチング攻撃による絞り込み
実効秘匿
インターバル
線形式を満たす候補値
秘匿パターンが一致した候補値

22

評価実験
Q:マッチング攻撃で秘匿インターバルの条件が侵害される一次秘匿セルの割合はどの程度か？
• セル数: 16, 25, 36, 49の２次元の度数分布表をランダムに各50個生成– セル値は平均15, 標準偏差10の正規分布から抽出• セル秘匿アルゴリズムで２次秘匿テーブルを作成– 度数しきい値: 5– 秘匿インターバルのしきい値：8• 同じセル秘匿アルゴリズムによるマッチング攻撃を実施

23

マッチング攻撃で安全要件（秘匿インターバルの最小幅）が破られた１次秘匿セル数
表セル数

16

一次秘匿セ 安全でないル数
一次秘匿セル数

安全でない
一次秘匿セルの割合

1044846%170

11769%

230

19083%

271

22683%(4✕4)

25(5✕5)36(6✕6)49(7✕7)24

mine how the ratio of unsafe cells depends on the dimension of thmatrix A of a suppressed table in Section 3.2. Table 3 shows the ra
零空間の次元別のwith the dimensions of the null spaces and the number of cells i
安全でない１次秘匿セルの割合
the lower thedimension of the null space is, the higher the risk of• 零空間の次元が小さいほど、候補となるテー
ブルが少なく、秘匿インターバルの絞り込み
The ratio of unsafe cells by crossing the dimension of the null space andが大きい#Cells in a table
16253649Total

Dimension of the null space1234
0.83 0.42 0.17
1.00 0.71 0.57
0.83
1.00 0.87 0.78
0.82
0.81 0.89
0.73
0.88 0.73 0.75
0.77
25

ws the number of candidate tables in dependence to the dimensio

19 submitted to Journal Not Specified

15 of 18

絞り込まれた秘匿インターバルの分布

sks of revealing the exact values of sensitive cells under the presence of the matching

distribution of unsafe cells with respect to their widths of the effective feasibility intervals.

he attacks

36490123456
Width of an effective feasibility interval

716 of 18#Primary suppressed cells
0 10 20 30 40 50

Version August 4, 2019 submitted to Journal Not Specified

0123456
Width of an effective feasibility interval(a) Tables with 16 cells

07(b) Tables with 25 cells

12345
Width of an effective feasibility interval

6#Primary suppressed cells
0 20 40 60 80 100

25#Unsafecells
66720
104416222341
635175334531501092
33
2857
4453

#Primary suppressed cells
0510152016

Width ofan effectivefeasibility interval
01234567012345670123456701234567#Primary suppressed cells
020406080#Cellsin a table

0123456
Width of an effective feasibility interval(c) Tables with 36 cells

7(d) Tables with 49 cells

Figure 8. Distribution of the widths of effective feasibility intervals of primary suppressed cells.
Table 5. Latency of performing matching attacks. We take the average latency of 50 matching attacksfor each table size.
#Cells in a table

Latency (Second)161.41226

まとめ• 統計開示抑制は出力プライバシー保護を目的とする• 統計量が特定の入力に依存しないことを目指す安全性ルールに経験的に定めている– 最小度数ルール、占有性ルール• 「決定論的」なセル秘匿処理には秘匿パターンの再現性確認によるマッチング攻撃が存在– 実証実験では現実的な脅威であることを確認• 今後の方向性
Ø 秘匿処理への確率的なランダム性の導入• ノイズ付加、ランダムサンプリング等

Ø 攻撃者に関する仮定の緩和• 例：９人の共謀は不可能

自分以外のデータ提供者が全員共謀している場合に入力データの機密性を保証する安全性指標は？
x1
x! + x" + ⋯ + 𝑥!$x2

Sum関数

x9ーシバ
イラプ
差分x10