• ホーム
• 情報セキュリティ
• 暗号技術

暗号応用技術

検索可能暗号

検索可能暗号とは

暗号化されたデータベースをキーワードで検索する場合，一般的には暗号化データをその都度復号してキーワードを含むか否かを調べる必要がある．この場合，暗号化により保護された情報を復元する鍵をサーバ側 (の管理者) が保持することになり，管理者による不正閲覧が可能なことやコンピュータウイルスにも弱いことが懸念される．

これを解決する方法として，「検索可能暗号」という技術がある．これは， データを暗号化したまま検索する暗号技術のことである．検索対象のデータだけでなく，検索キーワードも暗号化したまま処理できるため，クラウド上のデータの安全な利活用に役立つ技術として注目が高まっているもので，近年研究されている技術である．種々の方式が提案されているが，検索用のインデックスやタグを用いて，データが一致するかどうかを判別する仕組みを採用していることが多い．

例えば，次のような方式がある．

• 対象データは従来の方式で暗号化してサーバに保管する．
• 各データに対する検索キーワードを選び，検索可能暗号の公開鍵で暗号化して検索タグを生成しデータとペアにしてサーバに保管する．
• 検索するときは，検索キーワードから検索可能暗号の秘密鍵を用いて検索鍵を生成し，サーバに送る．
• サーバは検索鍵を用いて暗号化された検索タグを調べ，検索鍵で復号できる検索タグを探す．復号できるものがあれば，それに対応した暗号化データが検索対象のデータになる．

検索可能暗号の実現方式には，

• IDベース暗号ないし関数型暗号を利用する方式 (検索可能公開鍵暗号)
  ペアリング(双線形写像)を利用した検索可能暗号方式である．文書を暗号化した状態で，落とし戸 (trapdoor) を持つユーザだけが暗号文の中に特定のキーワードが含まれているかどうか検索できる方式である．落とし戸を持たないユーザには暗号文からキーワードが一切漏れることはない．
• 共通鍵暗号技術を用いる方式
  データや検索キーワードを暗号化する際に，暗号文にそれぞれ検索用のタグを付ける．このタグは，暗号文の生成時に使われた乱数を加工したものである．検索時には，「データの暗号文」と「検索キーワードの暗号文」から乱数で生成された部分のデータを取り出して，検索用に付けたタグのデータと比較する．比較の結果，二つのデータが一致すれば検索成功となる．ここで，生成される暗号文が毎回異なるようにに．暗号文の生成時に乱数を使う．

などがある．

検索可能公開鍵暗号

検索可能公開鍵暗号 PEKS（Publickey Encryption with Keyword Serach）は，キーワード $W$ のトラップドアがあれば，暗号文 $C$ がキーワード $W$ を暗号化したものか否かがわかる公開鍵暗号である．

• アルゴリズム
  検索可能公開鍵暗号は， $\mathrm{Setup}$，$\mathrm{KeyGen}$，$\mathrm{PEKS}$，$\mathrm{Trapdoor}$，$\mathrm{Test}$ の 5 つの手順から構成される．
  • $\mathrm{SetUp} (k)$：
    セキュリティパラメータ $k$ に対して，ランダムな生成元 $g \in G_1$ を選択する．
    次の双線形写像 $e$ と 2 つのハッシュ関数 $\mathrm{H_1}$， $\mathrm{H_2}$ を選択する．
    

    双線形写像 $e : G_1 \times G_1 \rightarrow G_2,\qquad \#G_1 = \#G_2 =$ 素数 $p$

    ハッシュ関数 $\mathrm{H_1} : \{0, 1\}^* \rightarrow G_1$

    ハッシュ関数 $\mathrm{H_2} : G_2 \rightarrow \{0, 1\}^n,\quad n = \log_2 p$

  • $\mathrm{KeyGen} (g)$：
    ランダムな $α \in {Z_p}^*$ を選び，$h = g^α$ を計算する．
    秘密鍵 $A_{pri}$ と公開鍵を$A_{pub}$ を以下とする．

    $A_{pri} = α$

    $A_{pub} = (g, h = g^α)$

  • $\mathrm{PEKS} (A{pri}, W)$：
    キーワード $W \in \{0, 1\}^n$ の暗号文 $C$ を生成する． ここで，任意の乱数 $r \in {Z_p}^*$ を用いる．

    $C = < g^r, \mathrm{H_2}(e(\mathrm{H_1}(W), h^r)) >$

  • $\mathrm{Trapdoor} (A_{pri}, W)$：
    秘密鍵 $A_{pri}$ と検索キーワード $W$ から検索鍵 $T_W$ を求める．

    $T_W = \mathrm{H_1}(W)^α$

  • $\mathrm{Test} (A_{pub}, C = <A, B>, T_W)$：
    検索鍵 $T_W$ と暗号文 $C = <A, B>$ を用い，以下の式が成り立てば，検索鍵 $T_W$ による検索は成功とする．すなわち，暗号文 $C$ はキーワード $W$ を暗号化したものであることが分かる．

    $\mathrm{H_2}(e(T_W, A)) =?\ B$

• 検索可能公開鍵暗号の安全性
  どのような攻撃者もいくつかのキーワードのトラップドアを適応的に入手したとしても，その他のキーワードの暗号文については，どんなキーワードの暗号化か全く分からないことである．

／