鳥が類を慕うように集まる：集合バイアスが交集サイズの公開を通じてどのように匿名性を損なうか

安全な二-partyプロトコルは、交差点に関連する統計情報を計算するために産業界で広く注目されています。これらのプロトコルにより、2つの組織は関数（カウントやサムなど）を共に計算できますが、交差点を明示的に明らかにする必要はありません。しかし、ほとんどの場合、これらのプロトコルは最終的に2つの集合間の交差点のサイズを明らかにしてしまいます。本研究では、攻撃者が公開された交差点サイズを利用して、ある組織の集合内での要素の所属を推論できる程度に焦点を当てています。ある要素の所属情報を別の組織に開示することさえも、GDPRなどのプライバシー規制に違反する可能性があります。このような要素は、2つの組織間で個人を識別するために使用されることが多いためです。我々は、交差点サイズ公開プロトコルにおける集合所属漏洩を最初に調査した研究チームです。現実的なシナリオでこの漏洩を評価するために、ベースライン攻撃と特徴認識攻撃の2つの攻撃手法を提案します。特に、特徴認識攻撃は現実世界の集合バイアスを利用しており、特定の特性を持つ要素が組織集合のメンバーになる可能性が高いというものです。結果として、両方の攻撃手法は3つの現実的なシナリオで平均して2.0〜72.7個の集合メンバーを推論できます。集合バイアスが弱くない場合、特徴認識攻撃はベースライン攻撃より優れています。例えば、COVID-19接触追跡では、特徴認識攻撃が135回のプロトコル呼び出しで25.9個の感染患者マーカーを見つけることができ、これはベースライン攻撃より1.5倍多い結果です。

序論

2つの組織の集合交差点に関する安全な2者間計算は、産業界で広く注目されています。有名なプロトコルの1つはプライベート集合交差点基数（PSI-CA）であり、これはある組織に交差点のサイズを返すもので、他方にはその他の情報を伝えません。このプロトコルは、ソーシャルネットワークの追跡やアソシエーションルールマイニングなどの分野で広く利用されています。もう1つの人気のあるプロトコルは基数付きプライベート交差点サム（PSI-SUM）であり、これは交差点内のインデックスに関連付けられた値をある組織が保持していることを合算します。PSI-SUMは当初、Googleの研究で広告変換による収益を測定するために提案されました。最近では、FacebookはPrivate-IDを提案しており、これはオンライン広告でのプライバシー保護変換向上測定のためのプロトコルです。

これらの安全計算プロトコルは2つの組織の集合交差点をいずれにも明らかにしませんが、2つの集合の交差点サイズを明らかにします。このような交差点サイズを明らかにするプロトコルを2つの組織間で繰り返し呼び出す限り、攻撃者は明らかになった交差点サイズを利用して特定の要素が交差点にあるかどうかをテストできます。このような攻撃では、ある組織（攻撃者として機能）は、各回の別の組織（被害者として機能）とのプロトコル呼び出しで単一要素集合を入力し、結果の交差点サイズを観察できます。このサイズが1に等しければ、関連する要素は交差点内に存在し、そうでなければ存在しません。攻撃者は、プロトコル呼び出しで対象となる要素を使用できることを強調します。これらの要素の所属は、基本的には被害者の集合の所属を明らかにしてしまうのです。言い換えれば、この攻撃により、攻撃者は対象要素が被害者の集合に属していることを推論できます。被害者の集合が静的であれば、N回のプロトコル呼び出しはN個の要素の集合所属を漏洩します。

本研究はこの攻撃を超え、明らかにされた交差点サイズによる集合所属漏洩に関する初めての研究を開始しました。この漏洩は、交差点に関する情報を明らかにしないまま交差点関連の統計量を計算するすべてのプロトコルにとって一般的な問題です。多くの現実世界のシステムは、これらのプロトコルを使用して、攻撃者から被害者の集合に関する情報をできるだけ隠そうとしています。これらのシステムでは、被害者の集合内の任意の要素を明らかにすることは許可されていません。しかし、本研究は、このようなセキュリティ要件を持つシステムにおいて、交差点サイズを明らかにするプロトコルを使用することはリスクがある可能性を示しています。

背景

交差点サイズ公開プロトコル

多くの安全な2者間プロトコルが存在し、交差点に関する情報以外は明らかにせず、そのサイズのみを明らかにしながら2者の集合の交差関数を計算できます。

• PSI-CA：このプロトコルはブラックボックスであり、一方から集合Aを受け取り、もう一方から集合Bを受け取ります。内部で交差点サイズ｜A ∩ B｜を計算し、この値を2者のうち1方に送信します。
• PSI-SUM：このプロトコルはブラックボックスであり、一方から集合Aを受け取り、もう一方からインデックス-値ペアのテーブル(ai,wi)を受け取ります。内部で交差点A ∩ Bのインデックスに関連付けられた値を集約し、総和∑ai∈A∩B wiを得ます。その後、この総和と交差点サイズ｜A ∩ B｜をテーブルを入力した方に送信します。
• Private-ID：このプロトコルはブラックボックスであり、一方から集合Aを受け取り、もう一方から集合Bを受け取ります。内部で結合A ∪ Bのすべての要素にランダムラベルを割り当て、2者が交差点A ∩ Bの各要素に対して同じラベルを取得できるようにします。その後、これらのラベルと交差点サイズ｜A ∩ B｜を2者に送信します。これらのラベルは、後続の安全計算で交差点A ∩ Bの多くの統計情報を計算するために使用できます。

脅威モデル

攻撃者の能力：攻撃者は以下の能力を持ちます：

• 攻撃者は交差点サイズを明らかにするプロトコルの当事者です。各プロトコル呼び出しで、攻撃者は自分の入力を選択でき、その入力と他方の集合によって生じる交差点サイズを把握できます。ここで、他方は被害者であり、その集合は動的です。
• 攻撃者は同じ被害者に対してプロトコルを繰り返し使用することが許可されています。

集合所属推論攻撃

ベースライン攻撃

ベースライン攻撃者は二分探索に似た戦略を採用します。まず、以下の条件を満たすような二分木を構築します：（i）各ノードは空でない集合を格納し、（ii）ルートノードは対象要素の集合を格納し、（iii）非葉ノードに格納された集合は、それぞれの2つの子ノードに格納される2つの空でなく互いに素な部分集合に分割されます。

二分木Mのノードuについて、Mu∈Aはノードuに格納された集合を表し、leftNode(u)（rightNode(u)）はuの左（右）子ノードを示します。我々のベースライン攻撃はAlgorithm 1のブループリントに従い、Algorithm 2をサブルーチンとして使用して二分木を構築します。

Algorithm 2: ベースライン攻撃者のconstructTreeアルゴリズム

入力：集合A。パラメータBGは無視。
出力：二分木M。

1. Mを初期化し、集合Aを格納する単独ノードrootを含む。
2. 格納された集合を2つの空でなく互いに素な部分集合に再帰的に分割することで、バランスの取れた二分木Mを構築。
3. Mを返却。

対象要素の集合所属を推論するために、攻撃者はキューに入れられた部分木に対して深さ優先探索（DFS）を実行します（キューには最初に構築された二分木が含まれます）。各DFSで、攻撃者は（i）キューからポップされた部分木を走査し、（ii）被害者とのプロトコル呼び出しを行い、アクセスした各ノードに格納された集合の交差点サイズを取得し、（iii）格納された集合サイズが受け取った交差点サイズに等しいノードで終了します。この検索中にアクセスされなかった部分木は、将来のDFSのためにキューにプッシュされます（16行目と19行目）。最後に、攻撃者はキューを空にして、被害者も保持している対象要素を含むすべての部分集合を見つけます。同時に、攻撃者は他の対象要素が非メンバーであることも確認できます。

Algorithm 1: 集合所属推論のブループリント

入力: 対象要素の集合A、背景知識BG、constructTreeアルゴリズム

出力: 集合所属述語φ。各xi ∈ Aについて、xiが被害者の集合に含まれていればφ(xi) = 1、そうでなければφ(xi) = 0

1 Q ← ∅を初期化
2 プロトコルにAを入力し、交差点サイズnを取得
3 M ← constructTree(A,BG) // 攻撃者の背景知識に基づいて二分木を構築
4 forest ← {(n/|A|,(n,M.root))} // (優先度, 部分木情報)タプルの優先度キュー
5 forestが空でない間:
6     (mcurrent,current) ← forest.pop()
7     0 < mcurrent < |Mcurrent|の間:
8         L ← leftNode(current), R ← rightNode(current)
9         if MRがMLより多くの要素を含む:
10           プロトコルにMLを入力し、交差点サイズmLを取得
11           mR ← mcurrent − mL
12       else:
13           プロトコルにMRを入力し、交差点サイズmRを取得
14           mL ← mcurrent − mR
15       if mR/|MR| > mL/|ML|:
16           forest.push((mL/|ML|,(mL,L)))
17           current ← R, mcurrent ← mR // 右の子へ移動
18       else:
19           forest.push((mR/|MR|,(mR,R)))
20           current ← L, mcurrent ← mL // 左の子へ移動
21   if mcurrent > 0 then Q ← Q ∪ Mcurrent
22 φをφ(xi) = 1 iff xi ∈ A ∩ Qとなる述語とする
23 return φ

残る問題は、ベースライン攻撃者が非葉ノードに格納された集合をどのように分割するかです。ベースライン攻撃者にとって、各対象要素が集合メンバーになる確率は同じです。この攻撃者にとっては、集合をランダムに均等に分割し、最終的にバランスの取れた二分木を構築するのが最適です。この方法により、DFSパスの期待長が最小になり、つまり期待されるプロトコル呼び出し回数が最小になります。

我々のベースライン攻撃は、二分探索に似た戦略のおかげでトイ攻撃よりも効率的です。被害者の集合Bが静的であり、攻撃者が二分木Mを構築したと仮定します。最初の観察は、木Mの任意の非葉ノードuについて、以下の等式が成り立つことです： ｜Mu ∩ B｜ = ｜MleftNode(u) ∩ B｜ + ｜MrightNode(u) ∩ B｜ この等式により、攻撃者が親ノードのサイズ（例：｜Mu ∩ B｜）と他方の子ノードのサイズ（例：｜MleftNode(u) ∩ B｜）を既に知っている場合、攻撃者は片方の子ノードの交差点サイズ（例：｜MrightNode(u) ∩ B｜）をローカルに決定できます。したがって、攻撃者はローカルに決定可能な交差点サイズに対して無駄な呼び出しを避けることができます。

効率最適化：貪欲深さ優先探索

集合メンバーのマージは攻撃効率を高められるので、攻撃者は最も高いマージ確率を持つ部分木を最初に探索すべきです。この確率は、部分木のルートの交差点サイズとその部分木内の対象要素数の比率に比例します。攻撃者はこの比率を把握しており、これを優先度スコアとして使用し、キューにプッシュされる部分木の順序を決定できます。これにより、攻撃者は最も高いマージ確率を持つポップされた部分木上で最初にDFSを実行します。各DFSでは、攻撃者は最も高い優先度スコアを持つ子ノードを再帰的にアクセスします。

Algorithm 3: 特徴認識攻撃者のためのconstructTree

入力: 集合A, 背景知識BG
出力: 二分木M

1 BGをテーブルDAとして解析し、DA[xi]が対象要素xiに関連する特徴を示す
2 Mを単一ノードrootを含むように初期化
3 Mroot ← A, queue ← {root}
4 queueが空でない間:
5   node ← queue.pop()
6   特徴{xi ∈ Mnode : DA[xi]}を使用してk-meansを実行し、Mnodeを2つの部分集合SLとSRに分割
7   2つの子ノードLとRをnodeに追加
8   ML ← SL, MR ← SR
9 if |SL| > 1 then queue.push(L)
10 if |SR| > 1 then queue.push(R)
11 return M