検索可能暗号 - 暗号理論教室

---

セキュア・インデックス

セキュア・インデックスの機能

セキュア・インデックスとは、文書Dに対して、検索キーwを隠したままでそれが文書Dに含まれるか否かを知ることができるインデックスI_Dを生成するスキーム。インデックスI_Dから文書Dの内容が知られてはならない。

インデックス・スキーム

I = (Keygen, Trapdoor, BuildIndex, SearchIndex)：

• K_priv ← Keygen()
• T_w ← Trapdoor(K_priv, w)
• I_D ← BuildIndex(D, K_priv)
• 1/0 ← SearchIndex(T_w, I_D)

文書Dと鍵K_privは私的に保持し、そのインデックスI_Dは第三者に預けておく。

ユーザはワードwについて検索したいときには、そのトラップドアT_wを計算し、第三者に渡して検索結果SearchIndex(T_w, I_D)を受け取る。

完全性 (completness)

∀K_priv ← Keygen(s), ∀w : ワード, ∀D : 文書,
∀T_w ← Trapdoor(K_priv, w), ∀I_D ← BuildIndex(D, K_priv)

• SearchIndex(T_w, I_D) = ( w∈^? D ).

セキュア・インデックスの安全性

どのような攻撃者も、いくつかのワードのトラップドアを入手したとしても、インデックスI_Dから文書Dの内容が全く分からないこと。

ゲーム

• q個のワードからなる集合Sを選択する。
• 攻撃者Aを起動し、集合Sを渡す。
• 攻撃者Aより、Sの部分集合の族S*を受け取り、
  • K_priv ← Keygen()
  • V ∈ S* 　: 　I_V ← BuildIndex(V, K_priv)
  • { (V, I_V) }_V∈S* をAに渡す。
• 以下をAが望むだけ複数回繰り返す： 　　　　※　トラップドアクエリ
  • 攻撃者Aがワードxについてトラップドアを要求したら、
  • T_x ← Trapdoor(K_priv, x) を計算し、返す。
• 攻撃者Aより２つの文書V₀, V₁ を受け取り、 　　　※　チャレンジクエリ
  • V₀∈S*、V₁∈S*、V₀ not⊆ V₁、V₁ not⊆ V₀ を確認する。
  • AはまだV₀とV₁の対称差に含まれるワードのトラップドアを要求していないことを確認する。
  • b ← {0,1}、　I_Vb ← BuildIndex(V_b, K_priv)
  • I_Vbを返す。
• 以下をAが望むだけ複数回繰り返す： 　　　　※　トラップドアクエリ
  • 攻撃者Aがワードxについてトラップドアを要求したら、
  • x が V₀とV₁の対称差に含まれないことを確認する。
  • T_x ← Trapdoor(K_priv, x) を計算し、返す。
• Aはb'を出力して停止する。

攻撃者Aのアドバンテージ：

• Adv_A =^def | Pr[b=b'] - 1/2 |

※ トラップドアT_xがワードxを隠すかどうかは考慮されていない。

定義 (IND-CKA)

インデックス・スキーム I = (Keygen, Trapdoor, BuildIndex, SearchIndex)が適応的選択キーワード攻撃に対し識別不可能（IND-CKA）であるとは、どのような効率的な攻撃者Aについても上記のゲームにおけるアドバンテージAdv_Aが無視可能であることを云う。

セキュア・インデックスの構成

ブルーム・フィルター

機能：

• 与えれたaが、集合S= {s₁, ・・・, s_n}に属するか否かを、o(n)の計算量で、判定する。

準備：

• パラメータ m, r
• mビットのアレイ α
• r個の独立なハッシュ関数 h₁, ・・・, h_r
  • h_i : {0,1}* → [1..m] 　　(i = 1,...,r)

動作：

• すべてのアレイビットを0に初期化：
  • h ∈ [1..m] : α[h] = 0.
• s ∈ S :
  • α[h₁(s)] = ・・・ = α[h_r(s)] = 1
• a ∈ S かどうかを判定するのに
  • αをビット位置 h₁(a), ・・・ , h_r(a)でチェック
  • それらがすべて１ならば、a ∈ Sと判定する。

※ フォース・ポジティブの確率あり。

インデックス・スキーム Z-IDX

部品

擬似ランダム関数 f : {0,1}^s x {0,1}ⁿ → {0,1}^s

Keygen (s) :

• return K_priv = (k₁, ... , k_r) ← {0,1}^sr

Trapdoor (K_priv, w) :

• return T_w = (f(k₁, w), ... , f(k_r, w))).

BuildIndex (D=(id_D, (w₁, ... , w_t))) :

• // 簡単のため、対象文書Dのワード数tは一定であるとする。
• ブルーム・フィルターBFを用意
• i∈[1..t] :
  • x₁ = f(k₁, w_i), ... , x_r = f(k_r, w_i)
  • y₁ = f(x₁, id_D), ... , y_r = f(x_r, id_D)
  • ブルーム・フィルターBFのアレイのビット位置y₁, ... , y_rを1にセット。
• return (id_D, BF)

SearchIndex ( T_w=(x₁, ... , x_r), I = (id_D, BF) ) :

• y₁ = f(x₁, id_D), ... , y_r = f(x_r, id_D)
• BFがビット位置y₁, ... , y_rですべて１であるか否かをチェック。
• そうならば1を、そうでないならば0を出力。

スキームの観察

• ブルーム・フィルターで用いるハッシュ関数を鍵付きのハッシュ関数とし、その鍵をマスターシークレットとした。
• 鍵付きのハッシュ関数を擬似ランダム関数で実現すれば、インデックスはランダム値となるので、文書の内容を隠す。
• ただし、トラップドアを実現するために、擬似ランダム関数の使い方に無理が生じている。
  • 後半の使い方（y_i = f(x_i, id_D)）に注意を要する。論文の証明は不十分と思われる。
    • シードが既知の乱数のときの、擬似ランダム関数の値の分布が問題となりそう。
    • 統計的な安全性の議論が必要となるのでは？

定理 (セキュアインデックス)

関数fが擬似ランダム関数ならば、インデックス・スキーム Z-IDXは、選択キーワード攻撃に対し識別不可能である。

証明について

上に見たように、論文の証明にはギャップがある。関数fについてもっと強い仮定が必要だろうと思われる。

検索可能公開鍵暗号

ワードWのトラップドアがあれば、暗号文SがワードWを暗号化したものか否かがわかる公開鍵暗号。

検索可能公開鍵暗号スキーム

PEKS = (KeyGen, PEKS, Trapdoor, Test)：

• (A_pub, A_priv) ← KeyGen(s)
• S ← PEKS(A_pub, W)
• T_W ← Trapdoor(A_priv, W)
• 1/0 ← Test(A_pub, S, T_W)

完全性 (completness)

(A_pub, A_priv) ← KeyGen(s),
∀W, S ← PEKS(A_pub, W), T_W ← Trapdoor(K_priv, W)

• Test(A_pub, S, T_W) = ( SはWの暗号文? ).

検索可能公開鍵暗号の安全性

どのような攻撃者も、いくつかのワードのトラップドアを適応的に入手したとしても、そのほかのワードの暗号文については、どんなワードの暗号化か全く分からないこと。

ゲーム

• (A_pub, A_priv) ← KeyGen(s)
• A_pubを入力として攻撃者Aを起動する。
• Aが望むだけ以下を複数回繰り返す： 　　　　※　トラップドアクエリ
  • 攻撃者AがワードWについてトラップドアを要求したら、
  • T_W ← Trapdoor(A_priv, W) を計算して返す。
• 攻撃者Aより２つのワードW₀, W₁ を受け取り、 　　　※　チャレンジクエリ
  • b ← {0,1}、　S ← PEKS(A_pub, W_b)
  • Sを返す。
• Aが望むだけ以下を複数回繰り返す： 　　　　※　トラップドアクエリ
  • 攻撃者AがワードWについてトラップドアを要求したら、
  • W が W₀やW₁とは異なることを確認する。
  • T_W ← Trapdoor(A_priv, W) を計算して返す。
• Aはb'を出力して停止する。

攻撃者Aのアドバンテージ：

• Adv_A(s) =^def | Pr[b=b'] - 1/2 |

定義 (IND-CKA)

検索可能公開鍵暗号 PEKS = (KeyGen, PEKS, Trapdoor, Test)が適応的選択キーワード攻撃に対し識別不可能（IND-CKA）であるとは、どのような効率的な攻撃者Aについても上記のゲームにおけるアドバンテージAdv_A(s)が無視可能であることを云う。

検索可能公開鍵暗号の構成

双線形写像を用いた構成

PEKS = (KeyGen, PEKS, Trapdoor, Test)

部品

• 双線形写像 e : G₁ x G₁ → G₂, 　 #G₁ = #G₂ = 素数p
• ハッシュ関数 H₁ : {0,1}* → G₁
• ハッシュ関数 H₂ : G₂ → {0,1}^{log p}

KeyGen

• α ← Z_p*,　g ← G₁の生成元
• return A_pub = (g, h = g^α), A_priv = α.

PEKS (A_pub, W) :

• r ← Z_p*
• return (g^r, H₂( e(H₁(W), h^r) )).

Trapdoor(A_priv = α, W) :

• return T_W = H₁(W)^α.

Test(A_pub, S=(A,B), T_W) :

• return H₂(e(T_W, A)) =^? B.

スキームの観察

• Wの暗号文は、(g^r, H₂(e(H₁(W), g^αr)))
• よって、H₁(W) = g^β とするとき、e(g, g)^αβrが問題。
• 一方、トラップドアオラクルは、H₁(W) = g^βとするとき、g^αβを返す。

定理 (PEKS)

双線形ディフィー・ヘルマン仮定が成り立つならば、ランダムオラクルモデルのもとで、PEKSは適応的選択キーワード攻撃に対し識別不可能（IND-CKA）である。

双線形ディフィー・ヘルマン仮定

g, g^a, g^b, g^cを与えらて、e(g,g)^a,b,cを計算することは困難。

証明について

• 上でみたようにH₁オラクルのシミュレーションがポイント。
• 適切な確率で、
  • 問題文g^bを返答に埋め込む 　　→　チャレンジクエリへの応答
  • 自ら生成した乱数aを用いて、g^aを返答する。 　→ トラップドアクエリへの応答

文献

• [Goh 03]
• [BCOP 04]
• [ABCKKLMNPS 05]
• [CGKO 06]

上へ

---