ブルームフィルタと確率的データ構造のセキュリティ応用

解きたい問題：巨大なブラックリストを安く速く照合する

「このパスワードは過去の漏洩に含まれるか」「このURLは既知の悪性サイトか」――セキュリティの現場には、数億件規模の集合に対する所属判定（membership query） が頻発します。素朴にはハッシュ集合（ハッシュテーブル）に全件を入れて引けばよいのですが、漏洩パスワードは Have I Been Pwned（HIBP）の Pwned Passwords だけでユニークなものが10億件規模、悪性URLも日々膨れ上がり、全件をメモリに載せるとギガバイト級になります。さらにクライアント側（ブラウザ・端末）で照合したい場合、巨大な辞書を配布するのは帯域・更新の両面で現実的ではありません。

ここで効くのが 確率的データ構造（probabilistic data structure） です。「絶対に正しい答え」を諦め、ごく低い確率で誤判定する代わりに、空間を桁違いに節約する。中でも所属判定の定番が ブルームフィルタ です。要素そのものを一切保存せず、ビット配列への「印」だけで「たぶん含まれる／確実に含まれない」を答えます。要素を保存しないという性質は、実はプライバシーの観点でも効いてきます。

ブルームフィルタの原理：k 個のハッシュでビットを立てる

ブルームフィルタは、m ビットの配列（初期値すべて0）と k 個の独立なハッシュ関数からなります。操作は2つだけです。

構造: bits[0..m-1]（最初は全0）、ハッシュ h1..hk（各々 0..m-1 を返す）

挿入 add(x):
  for i in 1..k:
    bits[ hi(x) ] = 1          # k 箇所のビットを立てる

照会 query(x):
  for i in 1..k:
    if bits[ hi(x) ] == 0:
      return "確実に含まれない"   # 1つでも0なら未挿入が確定
  return "たぶん含まれる"          # 全部1なら所属の可能性

ここに非対称性があります。挿入時に立てたビットは決して0に戻らないので、挿入した要素は照会で必ず全ビットが1になる――つまり 偽陰性（false negative）は原理的に起こりません。一方、別の要素たちが立てたビットがたまたま重なって、未挿入の要素の k 箇所がすべて1になることはあり得る。これが 偽陽性（false positive） です。「含まれないものを含むと誤答する」ことはあっても、「含まれるものを含まないと誤答する」ことはない――この一方向の誤りこそ、ブラックリスト照合に都合がよい性質です。悪性URLの判定なら、偽陽性は「安全なサイトを念のため精査する」コストで済み、見逃し（偽陰性）が起きないほうが重要だからです。

偽陽性率の数理と最適パラメータ

偽陽性率を見積もれることが、ブルームフィルタを「使える」道具にしています。n 個の要素を挿入した後、ある特定のビットが0のままである確率を考えます。1回のハッシュがそのビットを避ける確率は 1 − 1/m、k·n 回の印付けすべてが避ける確率は (1 − 1/m)^(kn)。m が大きいとき、これは e^(−kn/m) で近似できます。よって、あるビットが1になっている確率は 1 − e^(−kn/m) です。照会対象の k 箇所がすべて1（＝偽陽性）になる確率は、近似的に次になります。

偽陽性率  p ≒ (1 − e^(−kn/m))^k

最適なハッシュ個数（p を最小化する k）:
  k_opt = (m / n) · ln2          # m/n はビット数/要素数

このとき:
  p ≒ (1/2)^k_opt  =  2^( −(m/n)·ln2 )

必要ビット数（要素あたり）:
  m / n  =  − log2(p) / ln2  =  − ln(p) / (ln2)^2  ≒  −2.0813 · ln(p)

直感的には、k を増やすと「全ビット1」の条件が厳しくなり偽陽性は減りますが、増やしすぎると配列がすぐ埋まってかえって偽陽性が増える。両者が釣り合う最適点が k = (m/n)·ln2 で、そのとき配列はちょうど 約半分のビットが1になります。実用上の要点は 要素あたりのビット数 m/n で偽陽性率がほぼ決まることです。

注目すべきは、偽陽性率を10倍厳しくするのに必要な追加ビットが要素あたり一定（約4.8ビット）だという点です。要素の実サイズ（URLの長さなど）に一切依存しないのもブルームフィルタの強みで、長いURLでも短いパスワードでも要素あたりのコストは同じです。

削除できない弱点と Counting フィルタ

標準ブルームフィルタには本質的な制約があります。削除ができません。要素を消そうとして k 箇所のビットを0に戻すと、それらのビットを共有していた別の要素まで「含まれない」と誤答する偽陰性が生まれてしまう。失効した悪性URLをブラックリストから外したい、といった用途では致命的です。

これを解くのが Counting Bloom Filter です。各セルを1ビットではなく小さなカウンタ（例 4ビット）にし、挿入で +1、削除で −1 します。照会は「全カウンタが1以上か」を見ます。これで削除が可能になりますが、代償としてメモリが数倍（カウンタのビット幅倍）に増え、カウンタが上限に達して飽和する（オーバーフロー）リスクも抱えます。

Counting Bloom Filter:
  add(x):    for i in 1..k: counter[ hi(x) ] += 1
  remove(x): for i in 1..k: counter[ hi(x) ] -= 1   # 標準版にはない操作
  query(x):  全ての counter[ hi(x) ] >= 1 なら "たぶん含まれる"

Cuckoo フィルタと XOR フィルタ

Counting フィルタの非効率を解消する新しい系統が Cuckoo フィルタ です。これはビット配列ではなく、要素ごとに短い フィンガープリント（指紋、数ビットのハッシュ断片） をハッシュテーブル状の「バケット」に格納します。Cuckoo ハッシュの発想で、各フィンガープリントは2つの候補バケットを持ち、片方が満杯ならもう片方へ追い出す（kick out）ことで高い占有率を実現します。

Cuckoo フィルタの利点は、フィンガープリントを直接消せるので削除が自然にでき、しかも同じ偽陽性率を Counting フィルタより少ないビットで達成できる点です。さらに照会が最大2バケットへのアクセスで済むため、k 箇所にランダムアクセスするブルームフィルタよりキャッシュ効率（メモリ局所性）が良く、実機では高速です。偽陽性率はフィンガープリントのビット幅 f とバケットサイズ b で決まり、おおむね 2b / 2^f に比例します。

近年は XOR フィルタ／Binary Fuse フィルタ がさらに省メモリです。これは静的な集合（あとから追加しない）専用で、3つのハッシュ位置の XOR が各要素のフィンガープリントに一致するよう構築時に解を求めます。同じ1%の偽陽性率を、ブルームフィルタの約9.6ビットに対し要素あたり約8ビット強で達成でき、照会も3アクセス固定です。漏洩パスワード辞書のように「一括構築して読み取り専用で配る」用途に向きます。

セキュリティ応用1：悪性URL判定とブラックリスト

ブラウザの セーフブラウジング 系機能は、確率的構造の代表的な実戦投入例です。全悪性URLのリストを端末に配ると巨大すぎ、URLを毎回サーバーへ問い合わせると閲覧履歴が筒抜けになる。そこで、URLのハッシュ接頭辞を使ったローカルフィルタで大半を「シロ（確実に含まれない）」と即断し、フィルタが「クロかもしれない（たぶん含まれる）」と言ったURLについてだけサーバーへ確認に行く、という二段構えを取ります。偽陰性が出ないため、フィルタが「シロ」と言えば確実に未登録で、危険サイトを取りこぼしません。サーバー問い合わせは偽陽性ぶんに絞られ、通信量とプライバシー漏れを最小化できます。

セキュリティ応用2：HIBP と k-匿名性によるプライバシー保全

漏洩パスワード照合は、確率的構造だけでなく k-匿名性（k-anonymity） という別のプライバシー技法と組み合わさる好例です。素朴に「このパスワードは漏洩していますか」とサーバーに問い合わせれば、サーバーに利用者の生パスワード（やそのハッシュ）が渡ってしまう。HIBP の Pwned Passwords API はこれを巧妙に回避します。

HIBP Range API（k-匿名モデル）の手順:

  1. クライアントが SHA-1(password) を計算   例: 21BD1...（40桁の16進）
  2. 先頭 5 桁だけをサーバーへ送る           例: "21BD1"
  3. サーバーは先頭が一致する全ハッシュの
     「残り 35 桁 + 漏洩回数」のリストを返す   （平均 約800 件）
  4. クライアントは手元で 35 桁を突き合わせ、
     一致があればそのパスワードは漏洩済み

肝は、サーバーが受け取るのが 5桁の接頭辞だけ だという点です。5桁（16進）の接頭辞は 16^5 ＝ 約105万通りあり、SHA-1 の出力は一様に近いので、同じ接頭辞を共有するハッシュは10億件規模のデータベース中に平均で数百件存在します。サーバーから見れば、どの利用者も「同じ接頭辞を持つ数百件の集団」の中に紛れ、どの具体的パスワードを照合したのかを区別できない――これが「集団サイズ k 以上の中に隠れる」k-匿名性です。残り35桁の最終判定は完全にクライアント側で行われ、生パスワードもその完全なハッシュもサーバーに渡りません。確率的構造が「要素を保存しない」のと同様、ここでも「サーバーに最小限しか渡さない」設計が効いています。

なお照合に SHA-1 を使うのは、あくまで既知漏洩との突き合わせ用の識別子としてであり、新規パスワードの保存には使ってはいけません。保存には専用の遅いハッシュ（ソルト＋ストレッチング）が必須で、その理由と設計は パスワードハッシュの内部 と オフラインパスワードクラッキング で扱う、辞書攻撃・レインボーテーブルへの耐性の話に直結します。

確率的データ構造を「ちょっと間違える代わりに省メモリな集合」で止めず、偽陽性率の数理・偽陰性ゼロという非対称性・削除を巡る構造選択・k-匿名性との組み合わせまで分解できると、なぜブラウザが履歴を漏らさず危険サイトを弾けるのか、なぜ HIBP が生パスワードを受け取らずに照合できるのかが、一本の設計思想としてつながって見えてきます。