検索可能暗号と暗号化データベースの原理

解きたい問題：預けたいが見せたくない

データベースをクラウドに預けると、運用は楽になりますが、サーバー管理者やクラウド事業者、あるいは侵入者が平文をそのまま読めてしまいます。素直な対策はディスク全体やカラムを暗号化することですが、ここで矛盾が生じます。普通の暗号(AES-GCM など)で暗号化すると、同じ平文でも毎回異なる暗号文になり安全な一方、サーバーは暗号文どうしを比較できず、等価検索も範囲検索もソートも一切できなくなります。検索するには結局すべてを復号してクライアントに送り返すしかなく、暗号化の意味が薄れます。

この「暗号化したまま、サーバー側で検索・絞り込みをしたい」という要求に応えるのが検索可能暗号(Searchable Encryption)と、それを使った暗号化データベースです。ただし結論を先に言えば、機能を増やすほど情報が漏れます。本稿は SSE・OPE/ORE・CryptDB の原理を追いながら、この機能性と漏洩のトレードオフがなぜ避けられないのかを示します。前提となる暗号モードの基礎は 暗号利用モードの内部 を参照してください。

SSE：暗号化インデックスで等価検索する

対称検索可能暗号(Symmetric Searchable Encryption, SSE) は、全文検索のように「このキーワードを含む文書を返せ」を暗号化したまま実現する技術です。素朴な発想は、各文書を暗号化したうえで暗号化された逆引きインデックスを別に作っておくことです。

鍵は擬似乱数関数(PRF)によるトークン化です。クライアントだけが持つ鍵 K と PRF F を使い、キーワード w を t = F(K, w) という決定論的なトークンに変換します。F は鍵がなければ出力から入力を逆算できず、しかも同じ w は必ず同じ t になります。この性質を使い、各キーワードのトークンをキー、それを含む文書 ID の(暗号化された)集合を値とする辞書を作ってサーバーに置きます。

インデックス構築（クライアント側、鍵 K は秘密）:
  各キーワード w について
    t = F(K, w)                      # 決定論的トークン
    index[t] = Enc(文書IDの集合)      # w を含む文書ID群を暗号化して格納
  index 全体をサーバーへ送る

検索（"database" を探す）:
  クライアント: t = F(K, "database") をサーバーへ送る
  サーバー    : index[t] を引き、該当エントリを返す（中身は読めない）
  クライアント: 受け取った文書IDを復号して結果を得る

ここが SSE の核心です。サーバーは t という不透明なトークンで辞書を引くだけで、t が何のキーワードかも、インデックスの中身も知りません。クライアントは検索語のトークンだけを渡せばよく、データベース全体をダウンロードする必要がありません。鍵が手元にある対称鍵方式だからこそ、PRF による決定論トークン化が成立します。

決定論的暗号と順序保存暗号：等価と範囲の代償

SSE は専用インデックスを前提としますが、既存のリレーショナル DB の WHERE col = ? や WHERE col BETWEEN ? AND ? をそのまま暗号文上で動かしたい場合、カラムの値そのものを特殊な暗号で置き換えるアプローチが使われます。ここで等価検索と範囲検索が別々の暗号方式に対応します。

決定論的暗号(Deterministic Encryption, DET) は、同じ平文を常に同じ暗号文に写します。普通の暗号と違いランダム性を排すため、サーバーは暗号文の一致だけで等価検索や GROUP BY、結合ができます。代償は明白で、同じ値は同じ暗号文になる=値の重複と頻度がそのまま見えることです。

順序保存暗号(Order-Preserving Encryption, OPE) は、平文の大小関係を暗号文の大小関係として保ちます。つまり a < b ならば必ず Enc(a) < Enc(b) が成り立つよう設計されており、サーバーは暗号文を数値比較するだけで範囲検索・ソート・MIN/MAX を実行できます。これは便利さと引き換えに、順序という情報を常時漏らすことを意味します。

決定論的暗号(DET):  Enc(100)=0x9a3f,  Enc(100)=0x9a3f   # 同値→同暗号文（等価検索可）
順序保存暗号(OPE):  a < b  ⇒  Enc(a) < Enc(b)          # 大小が保たれる（範囲検索可）

OPE をさらに洗練したのが順序明示暗号(Order-Revealing Encryption, ORE) です。OPE は暗号文自体が数直線上に並ぶため順序がそのまま読めますが、ORE は暗号文を直接比較するのではなく、専用の比較関数に二つの暗号文を渡したときだけ大小が判明する形にします。これにより「順序は分かるが、暗号文の数値的な間隔(平文の近さ)までは漏らさない」ように漏洩を絞れます。ただし順序関係そのものは依然として漏れる点は OPE と変わりません。

漏洩ベース攻撃：頻度とアクセスパターンから平文を当てる

DET や OPE/ORE が漏らす「頻度」や「順序」は一見すると無害に見えますが、外部知識(背景分布)と突き合わせると平文を高精度で復元できます。これが漏洩ベース攻撃(leakage-abuse attack) です。

頻度分析攻撃は DET を直撃します。例えば病院 DB の「病名」カラムが DET で暗号化されていれば、各暗号文の出現回数が分かります。攻撃者が一般的な病名の分布(公開統計)を知っていれば、最頻の暗号文を最頻の病名に対応づけるだけで多くの値を当てられます。これは古典的な単一換字式暗号の頻度分析と同じ原理で、決定論性が頻度を保存してしまうことに起因します。

OPE/ORE はさらに弱く、頻度に加えて順序も漏らします。攻撃者は暗号文をソートして平文の順位を知り、平文の取りうる範囲(例えば年齢は 0〜120、給与帯は既知の分布)を背景知識として持てば、ソート順位と既知分布を対応づけるソート攻撃で値を絞り込めます。実データに対する研究で、OPE/ORE 列の多くが復元可能であることが繰り返し示されてきました。

CryptDB：レイヤ暗号化で機能ごとに暗号を選ぶ

これらの方式を実際の SQL データベースに統合した代表が CryptDB です(MIT、2011)。核心はオニオン暗号化(onion encryption) と呼ばれるレイヤ構造です。各値を、強い暗号で外側を、弱い(=機能のある)暗号で内側を包む入れ子にして格納します。

オニオン（等値・順序用の例、外側ほど安全）:
  RND(  DET(  平文  ) )     # 等値オニオン：外RND→内DET
  RND(  OPE(  平文  ) )     # 順序オニオン：外RND→内OPE

通常時      : 最外層 RND のまま（確率的＝何も漏れない）
等値検索が来た: その列のオニオンを RND だけ剥がし DET 層を露出
範囲検索が来た: 順序オニオンを OPE 層まで剥がす

ポイントは、最初はすべて最も安全な確率的暗号(RND)で包んでおき、そのカラムに実際に等値検索や範囲検索が来たときだけ、必要な層まで暗号を剥がすことです。剥がす操作はサーバー上でユーザー定義関数として行われ、一度剥がした層は元に戻りません。つまり実際に使った機能の分だけ、そのカラムの漏洩レベルが上がるという設計です。検索されないカラムは RND のまま守られ、頻度も順序も漏れません。

CryptDB はアプリと DB の間にプロキシを置き、SQL を書き換えて暗号化列に対するクエリへ変換し、結果を復号してアプリに返します。アプリ側の改修をほぼ不要にしたのが実用上の貢献でした。

機能性と漏洩のトレードオフ

ここまでの全体像を、機能の強さと安全性は反比例するという一本の軸でまとめられます。

• 確率的暗号(RND)：最も安全だが、サーバー側では復号以外何もできない。検索しないカラム向け。
• SSE：キーワード検索ができるが、アクセスパターン・検索パターンが漏れる。
• 決定論的暗号(DET)：等価検索ができるが、頻度分布が漏れる。
• 順序保存/明示暗号(OPE/ORE)：範囲検索・ソートができるが、全順序(OPE は間隔も)が漏れる。

つまり、サーバーに許す操作の集合と、サーバーに漏れる情報の集合は連動しており、片方だけを増やすことはできません。漏洩を限りなくゼロに近づける手段(完全準同型暗号や ORAM)は存在しますが、桁違いのオーバーヘッドのため大規模 DB では非現実的です。同じ「見せずに使う」を別アプローチで追う技術は 準同型暗号と秘密計算(MPC) や 差分プライバシー を参照すると、漏洩との付き合い方の違いがよく分かります。

まとめ

検索可能暗号と暗号化データベースは、「データを暗号化したまま、サーバー側で検索・絞り込みをしたい」という要求に応える技術群です。SSE は擬似乱数関数による決定論トークン化で暗号化インデックスを構築し、検索語のトークンだけをサーバーに渡して等価・全文検索を実現しますが、アクセスパターンと検索パターンの漏洩を許容します。リレーショナル DB では、等値検索を決定論的暗号(DET)、範囲検索を順序保存暗号(OPE)・順序明示暗号(ORE) で実現し、それぞれ頻度・順序という情報を必ず漏らします。

これらの漏洩は無害ではなく、背景分布と突き合わせる漏洩ベース攻撃(頻度分析・ソート攻撃・既知文書攻撃)で平文を高精度に復元しうることが繰り返し示されてきました。CryptDB はオニオン暗号化で各値を確率的暗号から弱い暗号まで入れ子にし、実際に使う機能の層まで剥がすことで「使わない機能の分は守る」設計を実現しましたが、使う機能の漏洩そのものは原理上ゼロにできません。結局、サーバーに許す機能の集合と漏れる情報の集合は連動するという機能性と漏洩のトレードオフが本質です。漏洩を極小化する 準同型暗号と秘密計算(MPC)、統計利用に特化した 差分プライバシー、暗号モードの土台である 暗号利用モードの内部 と併せて押さえると、暗号化データ処理の全体像がつかめます。