(57)【特許請求の範囲】
【請求項１】
検索情報生成装置と検索要求装置と検索実行装置を含み、検索情報保存装置に記憶された検索インデックスＣ２を用いて、文字列を含む平文Ｍを暗号化して暗号情報保存装置に記憶された暗号文Ｃ１に対してキーワード検索を行う暗号文検索システムであって、
前記検索情報生成装置は、
任意のビット列からなる情報Ｒ１を生成し、当該情報Ｒ１を、あらかじめ生成された公開鍵ｐｋと、前記平文Ｍと関連するキーワードである登録キーワードＷＴを用いて暗号化することで、情報Ｒ２を生成し、前記暗号文Ｃ１を一意に識別するための情報Ｒ３を生成し、当該情報Ｒ１と当該情報Ｒ２と当該情報Ｒ３を一組とした前記検索インデックスＣ２：＝（Ｒ１，Ｒ２，Ｒ３）を前記検索情報保存装置へ送信する検索インデックス生成部を備え、
前記検索要求装置は、
検索キーワードＷＱと、前記公開鍵ｐｋと対になるマスタ秘密鍵ｓｋを用いて、前記情報Ｒ２を復号するための秘密鍵である検索クエリｋ＊を生成し、前記検索実行装置へ送信する検索クエリ生成部と、
前記検索実行装置から受信した検索結果Ｃ３に含まれる前記情報Ｒ３により識別される前記暗号文Ｃ１を前記暗号情報保存装置から取得する暗号文取得部を備え、
前記検索実行装置は、
前記検索インデックスＣ２を前記検索情報保存装置から取得する検索インデックス取得部と、
前記検索インデックスＣ２に含まれる前記情報Ｒ２を前記検索クエリｋ＊を用いて復号することで復号結果Ｒを生成し、当該復号結果Ｒと当該検索インデックスＣ２に含まれる前記情報Ｒ１が一致するか否かを判定する検索結果判定部と、
前記検索結果判定部により一致すると判定された検索インデックスＣ２から、少なくとも前記情報Ｒ３を抽出して前記検索結果Ｃ３を生成し、当該検索結果Ｃ３を前記検索要求装置へ送信する検索結果送信部を備える
ことを特徴とする暗号文検索システム。
【請求項２】
請求項１に記載の暗号文検索システムであって、
前記検索情報保存装置と前記暗号情報保存装置は、前記検索情報生成装置と前記検索要求装置と前記検索実行装置それぞれと、インターネットを介して接続されるオンラインストレージサービスである
ことを特徴とする暗号文検索システム。
【請求項３】
請求項１または２に記載の暗号文検索システムであって、
ｒを前記登録キーワードＷＴの最大文字数、ｗｉを前記登録キーワードＷＴのｉ番目の文字、ｔを前記検索キーワードＷＱの最大文字数、ｓｉを前記検索キーワードＷＱのｉ番目の文字、ｒｄｉ，ｊ（１≦ｉ，ｊ≦ｒ）を乱数として、
前記検索インデックス生成部は、属性ベクトルｘ→と述語ベクトルｖ→の内積が０であることを条件として暗号文を復号する内積述語暗号方式により、前記登録キーワードＷＴから前記属性ベクトルｘ→を生成し、当該属性ベクトルｘ→と前記公開鍵ｐｋを用いて、前記情報Ｒ１を暗号化することで前記情報Ｒ２を生成し、
前記検索クエリ生成部は、前記内積述語暗号方式により、前記検索キーワードＷＱから前記述語ベクトルｖ→を生成し、当該述語ベクトルｖ→と前記マスタ秘密鍵ｓｋを用いて、前記検索クエリｋ＊を生成し、
前記検索結果判定部は、前記内積述語暗号方式により、前記検索クエリｋ＊を用いて、前記情報Ｒ２を復号することで前記復号結果Ｒを生成し、
前記属性ベクトルｘ→は、ｒ個の属性値変数Ｘ１，…，Ｘｒからなる次数ｒ次以下の単項式をすべて辞書式順序で並べた順に各成分とした変数ベクトルＸ→ｒ，ｒに、前記登録キーワードの各文字ｗｉを、
【数１０】
0005670365.tif 000011
と設定することで生成され、
前記述語ベクトルｖ→は、前記内積述語暗号方式の述語論理を表す述語多項式の係数を、前記変数ベクトルＸ→ｒ，ｒの成分に対応する順に設定することで生成され、
前記述語多項式は、検索方式が完全一致検索の場合には、
【数１１】
0005670365.tif 000012
で表され、
前記述語多項式は、検索方式が前方一致検索の場合には、
【数１２】
0005670365.tif 000013
で表され、
前記述語多項式は、検索方式が後方一致検索の場合には、
【数１３】
0005670365.tif 000014
で表され、
前記述語多項式は、検索方式が部分一致検索の場合には、
【数１４】
0005670365.tif 000015
で表される
ことを特徴とする暗号文検索システム。
【請求項４】
請求項１または２に記載の暗号文検索システムであって、
＾はべき乗を表し、Ｓを鍵シード空間、Ｗをキーワード空間、Ｇ１，Ｇ２を位数ｐの巡回群、ｇを巡回群Ｇ１の生成元、ｅをＧ１×Ｇ１→Ｇ２であるペアリング関数、ｈσをＳ×Ｗ→Ｇ１である鍵付きハッシュ関数、σを鍵付きハッシュ関数ｈσのランダムシード、ｘ，ζを元の数がｐである有限体Ｆｐ＊からあらかじめランダムに選択された整数であるとして、
前記検索実行装置は、
属性ベクトルｘ→と述語ベクトルｖ→の内積が０であることを条件として暗号文を復号する内積述語暗号方式により、ユーザ識別子Ｕと当該ユーザ識別子Ｕに対応する属性情報ＡＦＬＵから前記述語ベクトルｖ→を生成し、当該述語ベクトルｖ→と前記公開鍵ｐｋと前記マスタ秘密鍵ｓｋを用いて、検索秘密鍵ｓｋＵを生成し、乱数ｘＵを前記有限体Ｆｐ＊からランダムに選択して補完鍵ｃｋＵ＝ｇ＾ｘ／ｘＵを計算し、当該検索秘密鍵ｓｋＵと乱数ｘＵを前記検索情報生成装置と前記検索要求装置へ送信するユーザ登録部と、
前記検索情報生成装置から受信したハッシュ値Ｈを用いて、係数ｆ＝ｅ（Ｈ，ｃｋＵ）を計算し、当該係数ｆを当該検索情報生成装置へ送信する係数算出部と、
をさらに備え、
前記検索情報生成装置は、
前記登録キーワードＷＴと前記有限体Ｆｐ＊からランダムに選択した乱数ｒｗを用いて、前記ハッシュ値Ｈ＝（ｈσ（ＷＴ））＾ｒｗｘＵを計算し、当該ハッシュ値Ｈを前記検索実行装置へ送信するハッシュ値算出部と、
をさらに備え、
前記検索インデックス生成部は、前記検索実行装置から受信した係数ｆと前記巡回群Ｇ２からランダムに選択した乱数ｒを用いて係数ｒ’＝ｒｆを計算し、前記乱数ｒを前記情報Ｒ１として設定し、前記内積述語暗号方式により、前記登録キーワードＷＴと当該登録キーワードＷＴを利用した検索を可能とするユーザの情報を含む検索権限情報ＡＣから前記属性ベクトルｘ→を生成し、当該属性ベクトルｘ→と前記公開鍵ｐｋを用いて、前記情報Ｒ１を暗号化することで（Ｔ１，…，ＴＮ）を生成し、前記ｇと前記ζを用いてτ＝ｇζを計算し、当該（Ｔ１，…，ＴＮ）と当該τと前記ハッシュ値Ｈを一組として前記情報Ｒ２：＝（Ｔ１，…，ＴＮ，τ，Ｈ）を生成し、
前記検索クエリ生成部は、前記内積述語暗号方式により、前記検索キーワードＷＱから前記述語ベクトルｖ→を生成し、当該述語ベクトルｖ→と前記公開鍵ｐｋと前記検索秘密鍵ｓｋＵを用いて、前記検索クエリｋ＊：＝（Ｑ１，…，ＱＮ）を生成し、
前記検索結果判定部は、前記検索クエリｋ＊：＝（Ｑ１，…，ＱＮ）を用いて、すべての検索インデックスＣ２それぞれについて、当該検索インデックスＣ２に含まれる前記情報Ｒ２：＝（Ｔ１，…，ＴＮ，τ，Ｈ）が、
【数１５】
0005670365.tif 000016
を満たすか否かを判定する
ことを特徴とする暗号文検索システム。
【請求項５】
請求項４に記載の暗号文検索システムであって、
＾はべき乗を表し、ｔを検索インデックスＣ２の総数、ｊを検索インデックスＣ２の番号、Ｋ（＝ｌｏｇ２ｔ＋１）をバッチタグＢＴａｇの階層数、ｋ（０≦ｋ≦Ｋ−１）をバッチタグＢＴａｇの階層の番号、Ｍ（＝２＾（ｌｏｇ２ｔ−ｋ））をバッチタグＢＴａｇの各階層における要素数、ｍ（１≦ｍ≦Ｍ）をバッチタグＢＴａｇの各階層における要素の番号であるとして、
前記検索実行装置は、
前記検索インデックスＣ２（ｊ）：＝（Ｔ（ｊ，１），…，Ｔ（ｊ，Ｎ），τ（ｊ），Ｈ（ｊ），ｒ（ｊ））から、Ｋ階層の２分木構造であるバッチタグＢＴａｇ（ｋ，ｍ）：＝（ＢＴ（ｋ，ｍ，１），…，ＢＴ（ｋ，ｍ，Ｎ），Ｂτ（ｋ，ｍ），ＢＨ（ｋ，ｍ），Ｂｒ（ｋ，ｍ））を、
階層０のバッチタグＢＴａｇ（０，ｍ）であれば、
ＢＴ（０，ｍ，ｉ）＝Ｔ（ｊ，ｉ），
Ｂτ（０，ｍ）＝τ（ｊ），
ＢＨ（０，ｍ）＝Ｈ（ｊ），
Ｂｒ（０，ｍ）＝ｒ（ｊ）
（ただし、１≦ｉ≦Ｎ）
として生成し、
その他のバッチタグＢＴａｇ（ｋ，ｍ）であれば、
ＢＴ（ｋ，ｍ，ｉ）＝ＢＴ（ｋ−１，２ｍ−１，ｉ）＋ＢＴ（ｋ−１，２ｍ，ｉ），
Ｂτ（ｋ，ｍ）＝Ｂτ（ｋ−１，２ｍ−１）Ｂτ（ｋ−１，２ｍ），
ＢＨ（ｋ，ｍ）＝ＢＨ（ｋ−１，２ｍ−１）＋ＢＨ（ｋ−１，２ｍ），
Ｂｒ（ｋ，ｍ）＝Ｂｒ（ｋ−１，２ｍ−１）Ｂｒ（ｋ−１，２ｍ）
（ただし、１≦ｉ≦Ｎ）
として生成するバッチタグ生成部
をさらに備え、
前記検索クエリ生成部は、前記内積述語暗号方式により、前記キーワード空間Ｗから前記検索キーワードＷＱを除いた集合である否定キーワードＷＱ￣から前記述語ベクトルｖ→を生成し、当該述語ベクトルｖ→と前記公開鍵ｐｋと前記検索秘密鍵ｓｋＵを用いて、前記検索クエリｋ＊：＝（Ｑ１￣，…，ＱＮ￣）を生成し、
前記検索結果判定部は、前記検索クエリｋ＊：＝（Ｑ１￣，…，ＱＮ￣）を用いて、階層（Ｋ−１）から階層０までの階層ごとに、前記バッチタグＢＴａｇ（ｋ，ｍ）それぞれについて、
【数１６】
0005670365.tif 000017
を満たすか否かを判定する
ことを特徴とする暗号文検索システム。
【請求項６】
請求項４に記載の暗号文検索システムであって、
＾はべき乗を表し、ｔを検索インデックスＣ２の総数、ｊを検索インデックスＣ２の番号、Ｋ（＝ｌｏｇ２ｔ＋１）をバッチタグＢＴａｇの階層数、ｋ（０≦ｋ≦Ｋ−１）をバッチタグＢＴａｇの階層の番号、Ｍ（＝２＾（ｌｏｇ２ｔ−ｋ））をバッチタグＢＴａｇの各階層における要素数、ｍ（１≦ｍ≦Ｍ）をバッチタグＢＴａｇの各階層における要素の番号であるとして、
前記検索情報保存装置は、
前記検索インデックスＣ２（ｊ）：＝（Ｔ（ｊ，１），…，Ｔ（ｊ，Ｎ），τ（ｊ），Ｈ（ｊ），ｒ（ｊ））から生成したＫ階層の２分木構造であるバッチタグＢＴａｇ（ｋ，ｍ）：＝（ＢＴ（ｋ，ｍ，１），…，ＢＴ（ｋ，ｍ，Ｎ），Ｂτ（ｋ，ｍ），ＢＨ（ｋ，ｍ），Ｂｒ（ｋ，ｍ））を、さらに記憶しており、
前記バッチタグＢＴａｇ（ｋ，ｍ）：＝（ＢＴ（ｋ，ｍ，１），…，ＢＴ（ｋ，ｍ，Ｎ），Ｂτ（ｋ，ｍ），ＢＨ（ｋ，ｍ），Ｂｒ（ｋ，ｍ））は、
階層０のバッチタグＢＴａｇ（０，ｍ）であれば、
ＢＴ（０，ｍ，ｉ）＝Ｔ（ｊ，ｉ），
Ｂτ（０，ｍ）＝τ（ｊ），
ＢＨ（０，ｍ）＝Ｈ（ｊ），
Ｂｒ（０，ｍ）＝ｒ（ｊ）
（ただし、１≦ｉ≦Ｎ）
として生成され、
その他のバッチタグＢＴａｇ（ｋ，ｍ）であれば、
ＢＴ（ｋ，ｍ，ｉ）＝ＢＴ（ｋ−１，２ｍ−１，ｉ）＋ＢＴ（ｋ−１，２ｍ，ｉ），
Ｂτ（ｋ，ｍ）＝Ｂτ（ｋ−１，２ｍ−１）Ｂτ（ｋ−１，２ｍ），
ＢＨ（ｋ，ｍ）＝ＢＨ（ｋ−１，２ｍ−１）＋ＢＨ（ｋ−１，２ｍ），
Ｂｒ（ｋ，ｍ）＝Ｂｒ（ｋ−１，２ｍ−１）Ｂｒ（ｋ−１，２ｍ）
（ただし、１≦ｉ≦Ｎ）
として生成され、
前記検索インデックス取得部は、前記バッチタグＢＴａｇ（ｋ，ｍ）を前記検索情報保存装置から取得し、
前記検索クエリ生成部は、前記内積述語暗号方式により、前記キーワード空間Ｗから前記検索キーワードＷＱを除いた集合である否定キーワードＷＱ￣から前記述語ベクトルｖ→を生成し、当該述語ベクトルｖ→と前記公開鍵ｐｋと前記検索秘密鍵ｓｋＵを用いて、前記検索クエリｋ＊：＝（Ｑ１￣，…，ＱＮ￣）を生成し、
前記検索結果判定部は、前記検索クエリｋ＊：＝（Ｑ１￣，…，ＱＮ￣）を用いて、階層（Ｋ−１）から階層０までの階層ごとに、前記バッチタグＢＴａｇ（ｋ，ｍ）それぞれについて、
【数１７】
0005670365.tif 000018
を満たすか否かを判定する
ことを特徴とする暗号文検索システム。
【請求項７】
検索インデックスＣ２を記憶する検索情報保存装置と、文字列を含む平文Ｍを暗号化した暗号文Ｃ１を記憶する暗号情報保存装置と、ネットワークを介して接続された検索情報生成装置であって、
任意のビット列からなる情報Ｒ１を生成し、当該情報Ｒ１を、あらかじめ生成された公開鍵ｐｋと、前記平文Ｍと関連するキーワードである登録キーワードＷＴを用いて暗号化することで、情報Ｒ２を生成し、前記暗号文Ｃ１を一意に識別するための情報Ｒ３を生成し、当該情報Ｒ１と当該情報Ｒ２と当該情報Ｒ３を一組とした前記検索インデックスＣ２：＝（Ｒ１，Ｒ２，Ｒ３）を前記検索情報保存装置へ送信する検索インデックス生成部を備える
ことを特徴とする検索情報生成装置。
【請求項８】
検索要求装置と、検索インデックスＣ２を記憶する検索情報保存装置と、ネットワークを介して接続された検索実行装置であって、
前記検索インデックスＣ２を前記検索情報保存装置から取得する検索インデックス取得部と、
前記検索インデックスＣ２に含まれる情報Ｒ２を検索クエリｋ＊を用いて復号することで復号結果Ｒを生成し、当該復号結果Ｒと当該検索インデックスＣ２に含まれる情報Ｒ１が一致するか否かを判定する検索結果判定部と、
前記検索結果判定部により一致すると判定された検索インデックスＣ２から、少なくとも情報Ｒ３を抽出して検索結果Ｃ３を生成し、当該検索結果Ｃ３を前記検索要求装置へ送信する検索結果送信部と、
を備えることを特徴とする検索実行装置。
【請求項９】
検索実行装置と、検索インデックスＣ２を記憶する検索情報保存装置と、文字列を含む平文Ｍを暗号化した暗号文Ｃ１を記憶する暗号情報保存装置と、ネットワークを介して接続された検索要求装置であって、
検索キーワードＷＱと、あらかじめ生成されたマスタ秘密鍵ｓｋを用いて、前記検索インデックスＣ２に含まれる情報Ｒ２を復号するための秘密鍵である検索クエリｋ＊を生成し、前記検索実行装置へ送信する検索クエリ生成部と、
前記検索実行装置から受信した検索結果Ｃ３に含まれる情報Ｒ３により識別される前記暗号文Ｃ１を前記暗号情報保存装置から取得する暗号文取得部と、
を備えることを特徴とする検索要求装置。
【請求項１０】
検索インデックス生成部が、任意のビット列からなる情報Ｒ１を生成し、当該情報Ｒ１を、あらかじめ生成された公開鍵ｐｋと、文字列を含む平文Ｍと関連するキーワードである登録キーワードＷＴを用いて暗号化することで、情報Ｒ２を生成し、前記平文Ｍを暗号化した暗号文Ｃ１を一意に識別するための情報Ｒ３を生成し、当該情報Ｒ１と当該情報Ｒ２と当該情報Ｒ３を一組とした検索インデックスＣ２：＝（Ｒ１，Ｒ２，Ｒ３）を検索情報保存装置へ送信する検索インデックス生成ステップと、
検索クエリ生成部が、検索キーワードＷＱと、前記公開鍵ｐｋと対になるマスタ秘密鍵ｓｋを用いて、前記情報Ｒ２を復号するための秘密鍵である検索クエリｋ＊を生成する検索クエリ生成ステップと、
検索インデックス取得部が、前記検索インデックスＣ２を前記検索情報保存装置から取得する検索インデックス取得ステップと、
検索結果判定部が、前記検索インデックスＣ２に含まれる前記情報Ｒ２を前記検索クエリｋ＊を用いて復号することで復号結果Ｒを生成し、当該復号結果Ｒと当該検索インデックスＣ２に含まれる前記情報Ｒ１が一致するか否かを判定する検索結果判定ステップと、
検索結果送信部が、前記検索結果判定ステップにより一致すると判定された検索インデックスＣ２から、少なくとも前記情報Ｒ３を抽出して検索結果Ｃ３を生成する検索結果送信ステップと、
暗号文取得部が、前記検索結果Ｃ３に含まれる前記情報Ｒ３により識別される前記暗号文Ｃ１を前記暗号情報保存装置から取得する暗号文取得ステップと、
を含む暗号文検索方法。
【請求項１１】
検索インデックス生成部が、任意のビット列からなる情報Ｒ１を生成し、当該情報Ｒ１を、あらかじめ生成された公開鍵ｐｋと、文字列を含む平文Ｍと関連するキーワードである登録キーワードＷＴを用いて暗号化することで、情報Ｒ２を生成し、前記平文Ｍを暗号化した暗号文Ｃ１を一意に識別するための情報Ｒ３を生成し、当該情報Ｒ１と当該情報Ｒ２と当該情報Ｒ３を一組とした検索インデックスＣ２：＝（Ｒ１，Ｒ２，Ｒ３）を検索情報保存装置へ送信する検索インデックス生成ステップ
を含む検索情報生成方法。
【請求項１２】
検索インデックス取得部が、検索インデックスＣ２を検索情報保存装置から取得する検索インデックス取得ステップと、
検索結果判定部が、前記検索インデックスＣ２に含まれる情報Ｒ２を検索クエリｋ＊を用いて復号することで復号結果Ｒを生成し、当該復号結果Ｒと当該検索インデックスＣ２に含まれる情報Ｒ１が一致するか否かを判定する検索結果判定ステップと、
検索結果送信部が、前記検索結果判定ステップにより一致すると判定された検索インデックスＣ２から、少なくとも情報Ｒ３を抽出して検索結果Ｃ３を生成する検索結果送信ステップと、
を含む検索実行方法。
【請求項１３】
検索クエリ生成部が、検索キーワードＷＱと、あらかじめ生成されたマスタ秘密鍵ｓｋを用いて、検索インデックスＣ２に含まれる情報Ｒ２を復号するための秘密鍵である検索クエリｋ＊を生成する検索クエリ生成ステップと、
暗号文取得部が、検索結果Ｃ３に含まれる情報Ｒ３により識別される暗号文Ｃ１を暗号情報保存装置から取得する暗号文取得ステップと、
を含む検索要求方法。
【請求項１４】
請求項７に記載の検索情報生成装置、請求項８に記載の検索実行装置、または請求項９に記載の検索要求装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えばクラウドストレージなどに保存されている暗号化された情報に対し暗号学的に安全にキーワード検索を行うことができる暗号文検索システム、検索情報生成装置、検索実行装置、検索要求装置、暗号文検索方法、検索情報生成方法、検索実行方法、検索要求方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、コンピュータの資源や機能（例えばネットワーク／サーバー／ストレージ／アプリケーション／サービスなど）を、例えばインターネットなどのネットワークを介してサービスとして利用する、クラウドコンピューティング（以下、クラウド）と呼ばれるコンピュータの利用形態が拡大している。特にクラウド上のストレージ資源を外部記憶域として情報の保存に利用するサービス提供形態は、クラウドストレージサービスやオンラインストレージサービスと呼ばれている。
【０００３】
クラウド上のオンラインストレージサービスにおける情報保存を、暗号理論を適用することで安全に実現する暗号学的クラウドストレージが提案されている（非特許文献１参照）。非特許文献１に記載の暗号学的クラウドストレージは、クラウド上に保存されたメッセージからの情報漏洩を防ぐ技術、どの文書が検索されたかという情報を除いては漏洩することのない検索技術、文書が改ざんされることなく保存されていることを保証する技術から構成されている。
【０００４】
しかしながら、非特許文献１に記載の暗号学的クラウドストレージでは、共通鍵型の検索可能暗号を利用しているため、検索をするために文書作成者から直接検索クエリを入手しなければならない。したがって、文書作成者と通信することができなければ検索機能を利用することができなくなるという課題があった。
【０００５】
文書作成者と直接通信することなく同等の安全性を確保した検索を実現する方式として、内積述語暗号（非特許文献２参照）を変換した公開鍵型の検索可能暗号である内積述語検索可能暗号が提案されている（非特許文献３、非特許文献４、非特許文献５参照）。公開鍵型の検索可能暗号は、内積述語暗号において、暗号文を検索インデックス、秘密鍵を検索クエリとし、属性を登録キーワード、述語を検索キーワードとした暗号文検索方法である。公開鍵型の検索可能暗号を用いると、文書作成者と通信しなくとも、第三者に何のキーワードで検索しているのかという情報を漏洩することなく暗号文の検索を行うことができる。非特許文献３は、非特許文献２に記載の階層型内積述語暗号を利用して部分一致検索を可能とした内積述語検索可能暗号である。非特許文献４は、非特許文献２に記載の階層型内積述語暗号を利用して複数ユーザでの利用を可能とした内積述語検索可能暗号である。非特許文献５は、非特許文献２に記載の階層型内積述語暗号においてバッチ検索を可能とすることで効率的な検索処理を実現した内積述語検索可能暗号である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】S. Kamara and K. Lauter. “Cryptographic cloud storage.” In Financial Cryptography Workshops, pp. 136-149, 2010.
【非特許文献２】T. Okamoto and K. Takashima. “Hierarchical predicate encryption for inner-products.” In ASIACRYPT, pp. 214-231, 2009.
【非特許文献３】R. Yoshida, S. Oda, and T. Kobayashi. “Public-key encryption with partial matching keyword search.” In Symp. on Cryptography and Information Security, 2010.
【非特許文献４】R. Yoshida, A. Nagai, and T. Kobayashi. “Hierarchical predicate encryption with keyword search in multi-user setting.” In Computer Security Symposium, 2010.
【非特許文献５】R. Yoshida, A. Nagai, T. Kobayashi, and H. Fuji. “An algorithm for inner-product batch searchable encryption.” In Symp. on Cryptography and Information Security, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来の暗号文検索システムは、公開情報のみから検索インデックスの生成が可能であるため、検索クエリに指定した検索キーワードが辞書攻撃により推測可能であることが知られている（詳しくは、「J. W. Byun, H. S. Rhee, H. Park, and D. H. Lee. “Off-line keyword guessing attacks on recent keyword search schemes over encrypted data.” In Secure Data Management, pp. 75-83, 2006.」参照）。
【０００８】
また、従来の暗号文検索システムでは、検索インデックスと暗号文からなる暗号情報を保存する装置と、検索を実行する装置が同一の装置として構成されていた。このため、検索処理量の増大に対応するために検索代行装置を増設する際には、追加する検索代行装置それぞれにすべての暗号情報を記憶させる必要があり、システム全体として必要とするストレージの容量が増大するという課題があった。
【０００９】
この発明はこのような点に鑑みてなされたものであり、辞書攻撃による検索キーワードの推定を防止し、かつ検索処理量の増大に対して必要とするストレージ容量を抑制した暗号文検索システム、暗号文検索方法、検索情報生成装置、検索実行装置、検索要求装置、およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
この発明の暗号文検索システムは、検索情報生成装置と検索要求装置と検索実行装置を含む。この発明の暗号文検索システムは、検索情報保存装置に記憶された検索インデックスＣ２を用いて、文字列を含む平文Ｍを暗号化して暗号情報保存装置に記憶された暗号文Ｃ１に対してキーワード検索を行う。検索情報生成装置は、検索インデックス生成部を備える。検索インデックス生成部は、任意のビット列からなる情報Ｒ１を生成する。情報Ｒ１を、あらかじめ生成された公開鍵ｐｋと、平文Ｍと関連するキーワードである登録キーワードＷＴを用いて暗号化することで、情報Ｒ２を生成する。暗号文Ｃ１を一意に識別するための情報Ｒ３を生成する。情報Ｒ１と情報Ｒ２と情報Ｒ３を一組とした検索インデックスＣ２：＝（Ｒ１，Ｒ２，Ｒ３）を検索情報保存装置へ送信する。検索要求装置は、検索クエリ生成部と暗号文取得部を備える。検索クエリ生成部は、検索キーワードＷＱと、公開鍵ｐｋと対になるマスタ秘密鍵ｓｋを用いて、情報Ｒ２を復号するための秘密鍵である検索クエリｋ＊を生成する。検索クエリｋ＊を検索実行装置へ送信する。暗号文取得部は、検索実行装置から受信した検索結果Ｃ３に含まれる情報Ｒ３により識別される暗号文Ｃ１を暗号情報保存装置から取得する。検索実行装置は、検索インデックス取得部と検索結果判定部と検索結果送信部を備える。検索インデックス取得部は、検索インデックスＣ２を検索情報保存装置から取得する。検索結果判定部は、検索インデックスＣ２に含まれる情報Ｒ２を検索クエリｋ＊を用いて復号することで復号結果Ｒを生成する。復号結果Ｒと検索インデックスＣ２に含まれる情報Ｒ１が一致するか否かを判定する。検索結果送信部は、検索結果判定部により一致すると判定された検索インデックスＣ２から、少なくとも情報Ｒ３を抽出して検索結果Ｃ３を生成する。検索結果Ｃ３を検索要求装置へ送信する。
【発明の効果】
【００１１】
この発明の暗号文検索システムによれば、検索クエリが暗号情報を保存する装置に漏洩しないため、辞書攻撃による検索キーワードの推定を防止できる。したがって、従来の暗号文検索システムに対してセキュリティを向上することができる。また、暗号情報を保存する装置と検索を実行する装置を分けて構成するため、検索処理量の増大に対して追加するストレージ容量を抑制することができる。
【図面の簡単な説明】
【００１２】
【図１】従来の暗号文検索システムの構成例を示すブロック図。
【図２】従来の暗号文検索システムを構成する装置の構成例を示すブロック図。
【図３】従来の暗号文検索システムが暗号文を生成・保存する動作例を示す図。
【図４】従来の暗号文検索システムが暗号文を検索・復号する動作例を示す図。
【図５】実施例１の暗号文検索システムの構成例を示すブロック図。
【図６】実施例１の暗号文検索システムを構成する装置の構成例を示すブロック図。
【図７】実施例１の暗号文検索システムが暗号文を生成・保存する動作例を示す図。
【図８】実施例１の暗号文検索システムが暗号文を検索・復号する動作例を示す図。
【図９】実施例１変形例の暗号文検索システムの構成例を示すブロック図。
【図１０】実施例１変形例の暗号文検索システムを構成する装置の構成例を示すブロック図。
【図１１】実施例２の暗号文検索システムの構成例を示すブロック図。
【図１２】実施例２の暗号文検索システムを構成する装置の構成例を示すブロック図。
【図１３】実施例２の暗号文検索システムが暗号文を生成・保存する動作例を示す図。
【図１４】実施例２の暗号文検索システムが暗号文を検索・復号する動作例を示す図。
【図１５】実施例３の暗号文検索システムの構成例を示すブロック図。
【図１６】実施例３の暗号文検索システムを構成する装置の構成例を示すブロック図。
【図１７】実施例３の暗号文検索システムが暗号文を検索・復号する動作例を示す図。
【図１８】実施例３変形例の暗号文検索システムの構成例を示すブロック図。
【図１９】実施例３変形例の暗号文検索システムを構成する装置の構成例を示すブロック図。
【図２０】実施例３変形例の暗号文検索システムが暗号文を検索・復号する動作例を示す図。
【発明を実施するための形態】
【００１３】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１４】
［従来の暗号文検索システムの説明］
実施例の説明に先立ち、図１〜４を参照して、従来の内積述語検索可能暗号を利用した暗号文検索システム１０の動作を詳細に説明する。図１は、従来の暗号文検索システム１０の構成を示すブロック図である。図２は、従来の暗号文検索システム１０を構成する各装置の構成を示すブロック図である。図３は、従来の暗号文検索システム１０が暗号文を生成・保存する動作を示すフローチャートである。図４は、従来の暗号文検索システム１０が暗号文を検索・復号する動作を示すフローチャートである。
【００１５】
図１，２を参照して、従来の暗号文検索システム１０の構成を説明する。従来の暗号文検索システム１０は、インターネット１とネットワーク２と検索情報生成装置１００と検索要求装置２００と検索代行装置８００から構成される。検索代行装置８００はインターネット１に接続される。検索情報生成装置１００と検索要求装置２００はネットワーク２に接続される。インターネット１とネットワーク２はルータやファイアウォールなどの各種のネットワーク機器によって接続されており、検索情報生成装置１００と検索要求装置２００と検索代行装置８００が相互に通信可能なように構成される。検索情報生成装置１００は、暗号文生成部１１０と検索インデックス生成部１２０を備える。検索要求装置２００は、検索クエリ生成部２１０と復号部２９０を備える。検索代行装置８００は、検索結果判定部８１０と検索結果送信部８２０と記憶部８９０を備える。
【００１６】
図３を参照して、従来の暗号文検索システム１０が暗号文を生成・保存する動作を実際に行われる手続きの順に従って説明する。
【００１７】
検索情報生成装置１００の暗号文生成部１１０は、平文Ｍを暗号化して暗号文Ｃ１を生成する（Ｓ１１０）。検索情報生成装置１００の検索インデックス生成部１２０は、任意のビット列を情報Ｒ１として生成する（Ｓ１２１０）。続いて、検索情報生成装置１００の検索インデックス生成部１２０は、情報Ｒ１を、あらかじめ生成された公開鍵ｐｋと登録キーワードＷＴを用いて、内積述語暗号方式により暗号化することにより、情報Ｒ２を生成する（Ｓ１２２０）。続いて、検索情報生成装置１００の検索インデックス生成部１２０は、情報Ｒ１と情報Ｒ２を一組とした検索インデックスＣ２：＝（Ｒ１，Ｒ２）を生成し、検索インデックスＣ２と暗号文Ｃ１を一組とした暗号情報Ｃ０＝（Ｃ２，Ｃ１）を検索代行装置８００へ送信する。検索代行装置８００は、検索情報生成装置１００から受信した暗号情報Ｃ０を記憶部８９０へ記憶する（Ｓ８９０）。
【００１８】
図４を参照して、従来の暗号文検索システム１０が暗号文を検索・復号する動作を実際に行われる手続きの順に従って説明する。検索要求装置２００の検索クエリ生成部２１０は、検索キーワードＷＱと、公開鍵ｐｋと対になるマスタ秘密鍵ｓｋを用いて、内積述語暗号方式により情報Ｒ２を復号するための秘密鍵である検索クエリｋ＊を生成する（Ｓ２１０）。続いて、検索要求装置２００の検索クエリ生成部２１０は、検索クエリｋ＊を検索代行装置８００へ送信する。検索代行装置８００の検索結果判定部８１０は、検索要求装置２００から受信した検索クエリｋ＊を用いて、記憶部８９０へ記憶している暗号情報Ｃ０のそれぞれについて検索が当たりか否かを判定する（Ｓ８１０）。検索が当たりか否かの判定は、すべての暗号情報Ｃ０について、検索インデックスＣ２に含まれる情報Ｒ２を、検索クエリｋ＊を用いて、内積述語暗号方式により復号して復号結果Ｒを生成し、その検索インデックスＣ２に含まれる情報Ｒ１と復号結果Ｒが一致するか否かにより行われる。次に、検索代行装置８００の検索結果送信部８２０は、当たりと判定された暗号情報Ｃ０に含まれる暗号文Ｃ１をすべて抽出し、検索要求装置２００へ送信する（Ｓ８２０）。検索要求装置２００の復号部２９０は、検索代行装置８００から受信した暗号文Ｃ１を復号して平文Ｍを取得する（Ｓ２９０）。
【００１９】
［従来の暗号文検索システムの課題］
検索代行装置８００と検索要求装置２００は、インターネット１を介して接続される。したがって、検索要求装置２００で生成され検索代行装置８００へ送信される検索クエリｋ＊は、インターネットを経由して送受信されることになる。また、検索代行装置８００がクラウド上のオンラインストレージサービスとして構成される場合には、その検索代行装置８００は外部の第三者であるサービス提供事業者により提供される。これは、内積述語暗号方式の秘密鍵である検索クエリｋ＊が外部の第三者に漏洩することを意味する。同様に検索クエリｋ＊により当たりと判定された暗号文Ｃ１がいずれであるかという情報も外部の第三者に漏洩することを意味する。一方で、検索インデックスＣ２は公開鍵ｐｋと任意に指定する登録キーワードＷＴを用いて生成されるため、検索代行装置８００が任意のキーワードを指定して検索インデックスを生成することも可能である。したがって、検索代行装置８００は、任意のキーワードによって生成した検索インデックスを、入手した検索クエリｋ＊で復号することで、その検索クエリｋ＊に指定された検索キーワードＷＱを推定することが可能である。さらに、検索代行装置８００は、検索によって当たりと判定された暗号文Ｃ１の内容を推測することが可能となる。このように、従来の暗号文検索システムにおいては、辞書攻撃に対する脆弱性が存在していた。
【００２０】
また、検索代行装置８００は、検索を実行する検索結果判定部８１０と暗号情報Ｃ０を記憶する記憶部８９０を備えており、記憶部８９０には検索インデックスＣ２と暗号文Ｃ１の組である暗号情報Ｃ０がすべて記憶されている。したがって、システム全体として必要とするストレージの容量はすべての暗号情報Ｃ０を合わせた容量を検索代行装置８００の台数倍した容量となる。このため、検索処理量の増大に対応するために検索代行装置８００を増設する際には、追加する検索代行装置８００それぞれにすべての暗号情報Ｃ０を記憶させる必要があり、必要とするストレージ容量が増大するという課題があった。
【実施例１】
【００２１】
本実施例は、部分一致検索が可能な内積述語検索可能暗号に対してこの発明を適用した実施例である。部分一致検索が可能な内積述語検索可能暗号についての詳細は、非特許文献３を参照されたい。
【００２２】
図５〜８を参照して、この発明の実施例１の暗号文検索システム２０の動作を詳細に説明する。図５は、本実施例の暗号文検索システム２０の構成を示すブロック図である。図６は、本実施例の暗号文検索システム２０を構成する装置の構成を示すブロック図である。図７は、本実施例の暗号文検索システム２０が暗号文を生成・保存する動作を示すフローチャートである。図８は、本実施例の暗号文検索システム２０が暗号文を検索・復号する動作を示すフローチャートである。
【００２３】
図５，６を参照して、本実施例の暗号文検索システム２０の構成を説明する。本実施例の暗号文検索システム２０は、インターネット１とネットワーク２と検索情報生成装置１０１と検索要求装置２０１と検索実行装置３００と検索情報保存装置４００と暗号情報保存装置５００から構成される。検索情報保存装置４００と暗号情報保存装置５００はインターネット１に接続される。検索情報生成装置１０１と検索要求装置２０１と検索実行装置３００はネットワーク２に接続される。インターネット１とネットワーク２はルータやファイアウォールなどの各種のネットワーク機器によって接続されており、検索情報生成装置１０１と検索要求装置２０１と検索実行装置３００と検索情報保存装置４００と暗号情報保存装置５００が相互に通信可能なように構成される。検索情報生成装置１０１は、暗号文生成部１１０と検索インデックス生成部１２１を備える。検索要求装置２０１は、検索クエリ生成部２１０と暗号文取得部２２０と復号部２９０を備える。検索実行装置３００は、検索インデックス取得部３１０と検索結果判定部３２０と検索結果送信部３３０を備える。検索情報保存装置４００は、検索インデックス記憶部４９０を備える。暗号情報保存装置５００は、暗号文記憶部５９０を備える。
【００２４】
検索情報保存装置４００と暗号情報保存装置５００は、ファイルサーバやＮＡＳ（Network Attached Storage）、ＳＡＮ（Storage Area Network）などによるファイル共有サービスとして構成してもよいし、クラウド上のオンラインストレージサービスとして提供されてもよい。本実施例ではクラウド上のオンラインストレージサービスとして構成した場合の例を説明する。なお、検索情報保存装置４００と暗号情報保存装置５００がインターネット１に接続するものとしたのはクラウド上のオンラインストレージサービスとして構成したためであり、検索情報保存装置４００と暗号情報保存装置５００がファイル共有サービスとして構成した場合には、検索情報保存装置４００と暗号情報保存装置５００はネットワーク２に接続することができる。後述の実施例２，３についても同様である。
【００２５】
図７を参照して、本実施例の暗号文検索システム２０が暗号文を生成・保存する動作を実際に行われる手続きの順に従って説明する。
【００２６】
まず、管理者は、初期化処理として、セキュリティパラメータ１λを入力として、Ｓｅｔｕｐを実行し、公開鍵ｐｋとマスタ秘密鍵ｓｋを生成する。マスタ秘密鍵ｓｋは検索要求装置２０１へ送信される。
【００２７】
検索情報生成装置１０１の暗号文生成部１１０は、文字列を含む平文Ｍを暗号化して暗号文Ｃ１を生成する（Ｓ１１０）。ここでの暗号方式は限定されない。例えば、共通鍵暗号方式や公開鍵暗号方式が利用できる。共通鍵暗号方式の場合、平文Ｍは検索情報生成装置１０１と検索要求装置２０１の間で共有される共通鍵によって暗号化される。公開鍵暗号方式の場合、平文Ｍは、例えば公開鍵基盤（ＰＫＩ）によって公開されている検索要求装置２０１の公開鍵によって暗号化される。続いて、検索情報生成装置１０１の暗号文生成部１１０は、暗号文Ｃ１を暗号情報保存装置５００へ送信する。
【００２８】
暗号情報保存装置５００は、検索情報生成装置１０１から受信した暗号文Ｃ１を暗号文記憶部５９０へ記憶する（Ｓ５９０）。
【００２９】
検索情報生成装置１０１の検索インデックス生成部１２１は、任意のビット列を情報Ｒ１として生成する（Ｓ１２１０）。例えば、情報Ｒ１に数値としてゼロを設定する。続いて、検索情報生成装置１０１の検索インデックス生成部１２１は、情報Ｒ１を、あらかじめ生成された公開鍵ｐｋと登録キーワードＷＴを用いて、内積述語暗号方式により暗号化することにより、情報Ｒ２を生成する（Ｓ１２２０）。登録キーワードＷＴは検索対象となるキーワードであり、ユーザにより任意に設定される。例えば、平文Ｍに含まれる文字列や平文Ｍの内容を示す単語などを設定することができる。
【００３０】
内積述語暗号方式は、属性ベクトルと述語ベクトルの内積が０であることを条件として暗号文を正しく復号できるという、内積を用いた述語暗号である。内積述語暗号についての詳細は、例えば「J. Katz, A. Sahai, and B. Waters. “Predicate encryption supporting disjunctions, polynomial equations, and inner products.” In EUROCRYPT, pp. 146-162, 2008.」や「A. B. Lewko, T. Okamoto, A. Sahai, K. Takashima, and B. Waters. “Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption.” In EUROCRYPT, pp. 62-91, 2010.」、もしくは非特許文献２を参照されたい。
【００３１】
内積述語検索可能暗号は、上述の内積述語暗号において、暗号文を検索インデックス、秘密鍵を検索クエリとし、属性を登録キーワード、述語を検索キーワードとした暗号文検索方法である。内積述語検索可能暗号では、登録キーワードＷＴを用いて属性ベクトルｘ→を生成し、検索キーワードＷＱを用いて述語ベクトルｖ→を生成する。属性ベクトルｘ→と述語ベクトルｖ→の内積が０であること、すなわち＜ｘ→，ｖ→＞＝０が登録キーワードと検索キーワードのマッチングを意味する。
【００３２】
属性ベクトルｘ→は、具体的には以下のように生成する。ｒ個の属性値変数Ｘ１，…，Ｘｒに対してｄ回の論理和を扱うためには、Ｘ１，…，Ｘｒからなる次数ｄ次以下の単項式をすべて用意する。この単項式を、１を含めて辞書式順序で並べた順に各成分としたベクトルを、属性値変数Ｘ１，…，Ｘｒに対するｄ次の変数ベクトルと呼ぶ。ここでは、変数ベクトルをＸ→ｒ，ｄと記述する。
【００３３】
ｒ文字の登録キーワードＷＴのｉ番目の文字をｗｉ（１≦ｉ≦ｒ）とする。属性変数Ｘｉについて、Ｘｉ＝ｗｉとする。ｘ→が式（１）を満足する場合、属性ベクトルｘ→を変数ベクトルＸ→ｒ，ｄ上の属性ベクトルとも呼ぶ。
【００３４】
【数１】
0005670365.tif 000002
【００３５】
ｒは１≦ｒを満たす整数の固定値にシステム仕様として設定される。ｄは１≦ｄ≦ｒを満たす整数の固定値にシステム仕様として設定される。この実施例では、ｄ＝ｒとする。つまり、述語多項式において登録キーワードの文字数相当の論理和を許容する。
【００３６】
続いて、検索情報生成装置１０１の検索インデックス生成部１２１は、暗号文Ｃ１を一意に識別するための情報Ｒ３を生成する（Ｓ１２３０）。情報Ｒ３は暗号文Ｃ１を一意に特定できる情報であればどのような情報でもよく、例えば暗号文Ｃ１を入力としたハッシュ関数の出力とすることができる。そして、検索情報生成装置１０１の検索インデックス生成部１２１は、情報Ｒ１と情報Ｒ２と情報Ｒ３を一組とした検索インデックスＣ２：＝（Ｒ１，Ｒ２，Ｒ３）を生成し、検索情報保存装置４００へ送信する。
【００３７】
検索情報保存装置４００は、検索情報生成装置１０１から受信した検索インデックスＣ２を検索インデックス記憶部４９０へ記憶する（Ｓ４９０）。
【００３８】
図８を参照して、本実施例の暗号文検索システム２０が暗号文を検索・復号する動作を実際に行われる手続きの順に従って説明する。
【００３９】
検索要求装置２０１の検索クエリ生成部２１０は、検索キーワードＷＱから述語ベクトルｖ→を生成する。その述語ベクトルｖ→と公開鍵ｐｋと対になるマスタ秘密鍵ｓｋを用いて、内積述語暗号方式により情報Ｒ２を復号するための秘密鍵である検索クエリｋ＊を生成する（Ｓ２１０）。検索キーワードＷＱは検索条件として指定するキーワードであり、ユーザにより任意に指定される。続いて、検索要求装置２０１の検索クエリ生成部２１０は、検索クエリｋ＊を検索実行装置３００へ送信する。
【００４０】
述語ベクトルｖ→は、具体的には以下のように生成する。ｒ個の属性値変数Ｘ１，…，Ｘｒで最大ｄ回の論理和が許されているとき、述語論理を表す属性変数からなる多変数多項式ｐ（Ｘα，…，Ｘβ）（１≦α≦β≦ｒ）を、変数ベクトルＸ→ｒ，ｄ上の述語多項式と呼ぶ。変数ベクトルＸ→ｒ，ｄ上の述語多項式ｐ（Ｘα，…，Ｘβ）を、変数ベクトルＸ→ｒ，ｄと述語ベクトルｖ→の内積＜Ｘ→ｒ，ｄ，ｖ→＞と考えて、述語多項式ｐ（Ｘα，…，Ｘβ）の係数を、変数ベクトルＸ→ｒ，ｄの成分に対応する順に述語ベクトルｖ→の成分とする。これ以外の述語ベクトルｖ→の成分は０とする。述語ベクトルｖ→を変数ベクトルＸ→ｒ，ｄ上の述語ベクトルとも呼ぶ。
【００４１】
ｔ文字の検索キーワードＷＱのｉ番目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とする。変数ベクトルＸ→ｒ，ｄ上の述語多項式ｐ（Ｘα，…，Ｘβ）は、検索時に指定される検索方式に対応して決定される。指定できる検索方式には、完全一致検索・前方一致検索・後方一致検索・部分一致検索がある。なお、ｒｄｉ，ｊ（１≦ｉ，ｊ≦ｒ）は乱数である。
【００４２】
完全一致検索は、任意のｉ（１≦ｉ≦ｒ）に対してｗｉ＝ｓｉが成立する場合である。完全一致検索における述語多項式ｐ（Ｘα，…，Ｘβ）は、式（２）で与えられる。
【００４３】
【数２】
0005670365.tif 000003
【００４４】
前方一致検索は、任意のｉ（１≦ｉ≦ｔ）に対してｗｉ＝ｓｉが成立する場合である。前方一致検索における述語多項式ｐ（Ｘα，…，Ｘβ）は、式（３）で与えられる。
【００４５】
【数３】
0005670365.tif 000004
【００４６】
後方一致検索は、任意のｉ（ｒ−ｔ＋１≦ｉ≦ｒ）に対してｗｉ＝ｓｉが成立する場合である。後方一致検索における述語多項式ｐ（Ｘα，…，Ｘβ）は、式（４）で与えられる。
【００４７】
【数４】
0005670365.tif 000005
【００４８】
部分一致検索は、任意のｊに対してｊ≦ｉ≦ｔ＋ｊ−１≦ｒを満たすすべてのｉに対してｗｉ＝ｓｉが成立する場合である。部分一致検索における述語多項式ｐ（Ｘα，…，Ｘβ）は、式（５）で与えられる。
【００４９】
【数５】
0005670365.tif 000006
【００５０】
検索実行装置３００の検索インデックス取得部３１０は、検索情報保存装置４００の検索インデックス記憶部４９０に記憶されている検索インデックスＣ２をダウンロードする（Ｓ３１０）。常にすべての検索インデックスＣ２をダウンロードしてもよいし、使用するネットワーク帯域を抑えるために、前回実行時に利用した検索インデックスＣ２を保持しておき、差分のみをダウンロードしてもよい。
【００５１】
検索実行装置３００の検索結果判定部３２０は、検索要求装置２０１から受信した検索クエリｋ＊を用いて、検索インデックスＣ２それぞれについて検索が当たりか否かを判定する（Ｓ３２０）。検索が当たりか否かの判定は、すべての検索インデックスＣ２について、その検索インデックスＣ２に含まれる情報Ｒ２を、検索クエリｋ＊を用いて、内積述語暗号方式により復号して復号結果Ｒを生成し、その検索インデックスＣ２に含まれる情報Ｒ１と復号結果Ｒが一致するか否かにより行われる。
【００５２】
検索実行装置３００の検索結果送信部３３０は、検索結果判定部３２０により当たりと判定された検索インデックスＣ２から暗号文Ｃ１を一意に識別する情報Ｒ３を抽出して検索結果Ｃ３を生成し、検索要求装置２０１へ送信する（Ｓ３３０）。
【００５３】
検索要求装置２０１の暗号文取得部２２０は、受信した検索結果Ｃ３に含まれる情報Ｒ３を参照し、すべての情報Ｒ３について、その情報Ｒ３により一意に識別される暗号文Ｃ１を暗号情報保存装置５００からダウンロードする（Ｓ２２０）。
【００５４】
検索要求装置２０１の復号部２９０は、暗号情報保存装置５００からダウンロードした暗号文Ｃ１を復号して平文Ｍを取得する（Ｓ２９０）。平文Ｍを復号する情報処理は、Ｓ１１０において検索情報生成装置１００の暗号文生成部１１０が用いた暗号方式に対応する復号アルゴリズムである。例えば、共通鍵暗号方式で暗号化がされていた場合には、平文Ｍは検索情報生成装置１０１と検索要求装置２０１の間で共有される共通鍵によって復号される。公開鍵暗号方式で暗号化がされていた場合には、平文Ｍは、検索要求装置２０１の秘密鍵によって復号される。
【００５５】
本実施例はこのような構成とすることにより、部分一致検索が可能な内積述語検索可能暗号において、検索クエリｋ＊がクラウドを構成する装置に漏洩することを防止でき、辞書攻撃による検索キーワードの推定を防止できる。そのため、従来の暗号文検索システムに対してセキュリティを向上することができる。また、暗号情報を保存する暗号情報保存装置と検索を実行する検索実行装置が異なる装置として構成することができるため、システム全体としての検索処理量の増大に対応して検索実行装置を増設する場合に、追加するストレージ容量を抑制することができる。
【００５６】
［変形例］
図９，１０を参照して、実施例１の変形例の暗号文検索システム２０’の構成を説明する。図９は、本実施例の暗号文検索システム２０’の構成を示すブロック図である。図１０は、本実施例の暗号文検索システム２０’を構成する装置の構成を示すブロック図である。
【００５７】
本実施例の暗号文検索システム２０’は、インターネット１とネットワーク２と検索情報生成装置１０１と検索要求装置２０１’と検索情報保存装置４００と暗号情報保存装置５００から構成される。検索情報保存装置４００と暗号情報保存装置５００はインターネット１に接続される。検索情報生成装置１０１と検索要求装置２０１’はネットワーク２に接続される。インターネット１とネットワーク２はルータやファイアウォールなどの各種のネットワーク機器によって接続されており、検索情報生成装置１０１と検索要求装置２０１’と検索情報保存装置４００と暗号情報保存装置５００が相互に通信可能なように構成される。検索要求装置２０１’は、検索クエリ生成部２１０と暗号文取得部２２０と復号部２９０と検索インデックス取得部３１０と検索結果判定部３２０を備える。
【００５８】
したがって、本変形例の暗号文検索システム２０’は実施例１の暗号文検索システム２０と比較して、検索実行装置３００の備えていた検索インデックス取得部３１０と検索結果判定部３２０を検索要求装置２０１’が備えるようにし、検索実行装置３００を省略したことが相違点である。
【００５９】
暗号文検索システム全体として必要とされる検索処理量が多くなく、検索要求装置が少数である場合には、本変形例のように構成することでシステム全体の装置数を削減することができる。この変形例の考え方は、後述の実施例２，３にも適用することができる。
【実施例２】
【００６０】
本実施例は、複数ユーザで利用が可能な内積述語検索可能暗号に対してこの発明を適用した実施例である。複数ユーザで利用が可能な内積述語検索可能暗号についての詳細は、非特許文献４を参照されたい。
【００６１】
図１１〜１４を参照して、この発明の実施例２の暗号文検索システム３０の動作を詳細に説明する。図１１は、本実施例の暗号文検索システム３０の構成を示すブロック図である。図１２は、本実施例の暗号文検索システム３０を構成する装置の構成を示すブロック図である。図１３は、本実施例の暗号文検索システム３０が暗号文を生成・保存する動作を示すフローチャートである。図１４は、本実施例の暗号文検索システム３０が暗号文を検索・復号する動作を示すフローチャートである。
【００６２】
図１１，１２を参照して、本実施例の暗号文検索システム３０の構成を説明する。本実施例の暗号文検索システム３０は、インターネット１とネットワーク２と検索情報生成装置１０２と検索要求装置２０２と検索実行装置３０１と検索情報保存装置４００と暗号情報保存装置５００から構成される。検索情報保存装置４００と暗号情報保存装置５００はインターネット１に接続される。検索情報生成装置１０２と検索要求装置２０２と検索実行装置３０１はネットワーク２に接続される。インターネット１とネットワーク２はルータやファイアウォールなどの各種のネットワーク機器によって接続されており、検索情報生成装置１０２と検索要求装置２０２と検索実行装置３０１と検索情報保存装置４００と暗号情報保存装置５００が相互に通信可能なように構成される。検索情報生成装置１０２は、暗号文生成部１１１と検索インデックス生成部１２２とハッシュ値算出部１３０を備える。検索要求装置２０２は、検索クエリ生成部２１１と暗号文取得部２２０と復号部２９０を備える。検索実行装置３０１は、検索インデックス取得部３１０と検索結果判定部３２１と検索結果送信部３３０とユーザ登録部３４０と係数算出部３５０を備える。
【００６３】
したがって、本実施例の検索情報生成装置１０２と実施例１の検索情報生成装置１０１とは、ハッシュ値算出部１３０を備え、暗号文生成部と検索インデックス生成部の処理が異なることが相違点である。本実施例の検索要求装置２０２と実施例１の検索要求装置２０１とは、検索クエリ生成部の処理が異なることが相違点である。本実施例の検索実行装置３０１と実施例１の検索実行装置３００とは、ユーザ登録部３４０と係数算出部３５０を備え、検索結果判定部の処理が異なることが相違点である。
【００６４】
以下の説明において、＾はべき乗を表し、Ｓを鍵シード空間、Ｗをキーワード空間、Ｇ１，Ｇ２を位数ｐの巡回群、ｇを巡回群Ｇ１の生成元、ｅをＧ１×Ｇ１→Ｇ２であるペアリング関数、ｈσをＳ×Ｗ→Ｇ１である鍵付きハッシュ関数、σを鍵付きハッシュ関数ｈσのランダムシード、ｘ，ζを元の数がｐである有限体Ｆｐ＊からあらかじめランダムに選択された整数であるものとする。ペアリング関数は、例えばWeilペアリングやTateペアリングなどである。鍵付きハッシュ関数は、例えばSHA-1やMD5などである。
【００６５】
図１３を参照して、本実施例の暗号文検索システム３０が暗号文を生成・保存する動作を実際に行われる手続きの順に従って説明する。
【００６６】
まず、管理者は、初期化処理として、セキュリティパラメータ１λを入力として、Ｓｅｔｕｐを２回実行し、それぞれの出力を（公開鍵ｐｋ，マスタ秘密鍵ｓｋ）、（暗号公開鍵ｐｋｅ，暗号マスタ秘密鍵ｓｋｅ）とする。続いて、管理者は、ｘとζを有限体Ｆｐ＊からランダムに選択する。続いて、管理者は、鍵付きハッシュ関数ｈσのランダムシードσを鍵シード空間Ｓからランダムに選択する。そして、マスタ秘密鍵ｓｋとｘは検索実行装置３０１へ送信される。
【００６７】
検索実行装置３０１のユーザ登録部３４０は、内積述語暗号方式により、登録対象であるユーザを一意に識別するユーザ識別子Ｕと、そのユーザ識別子Ｕに対応する属性情報ＡＦＬＵから述語ベクトルｖ→を生成する。述語ベクトルｖ→とあらかじめ生成された公開鍵ｐｋとその公開鍵ｐｋと対になるマスタ秘密鍵ｓｋを用いて、検索秘密鍵ｓｋＵを生成する。また、述語ベクトルｖ→とあらかじめ生成された暗号公開鍵ｐｋｅとその暗号公開鍵ｐｋｅと対になるマスタ秘密鍵ｓｋｅを用いて、暗号秘密鍵ｓｋｅ，Ｕを生成する。続いて、乱数ｘＵを有限体Ｆｐ＊からランダムに選択して補完鍵ｃｋＵ＝ｇ＾ｘ／ｘＵを計算する。そして、検索秘密鍵ｓｋＵと暗号秘密鍵ｓｋｅ，Ｕと乱数ｘＵを検索情報生成装置１０２と検索要求装置２０２へ送信する（Ｓ３４０）。
【００６８】
検索情報生成装置１０２の暗号文生成部１１０は、文字列を含む平文Ｍを暗号化して暗号文Ｃ１を生成する（Ｓ１１０）。暗号文Ｃ１は、検索権限情報ＡＣから属性ベクトルｘ→を生成する。属性ベクトルｘ→と暗号公開鍵ｐｋｅを用いて、内積述語暗号方式により暗号化される。検索権限情報ＡＣは、その暗号文Ｃ１を復号可能とするユーザのユーザ識別子Ｕと、そのユーザ識別子Ｕに対応する属性情報ＡＦＬＵからなる。続いて、検索情報生成装置１０２の暗号文生成部１１０は、暗号文Ｃ１を暗号情報保存装置５００へ送信する。
【００６９】
暗号情報保存装置５００は、検索情報生成装置１０２から受信した暗号文Ｃ１を暗号文記憶部５９０へ記憶する（Ｓ５９０）。
【００７０】
検索情報生成装置１０２のハッシュ値算出部１３０は、乱数ｒｗを有限体Ｆｐ＊からランダムに選択し、登録キーワードＷＴを用いて、ハッシュ値Ｈ＝（ｈσ（ＷＴ））＾ｒｗｘＵを計算することでハッシュ値Ｈを生成する（Ｓ１３０）。続いて、検索情報生成装置１０２のハッシュ値算出部１３０は、ハッシュ値Ｈを検索実行装置３０１へ送信する。
【００７１】
検索実行装置３０１の係数算出部３５０は、検索情報生成装置１０２から受信したハッシュ値Ｈを用いて、係数ｆ＝ｅ（Ｈ，ｃｋＵ）を計算する（Ｓ３５０）。続いて、検索実行装置３０１の係数算出部３５０は、係数ｆを検索情報生成装置１０２へ送信する。
【００７２】
検索情報生成装置１０２の検索インデックス生成部１２２は、乱数ｒを巡回群Ｇ２からランダムに選択する。その乱数ｒと検索実行装置３０１から受信した係数ｆを用いて、係数ｒ’＝ｒｆを計算する。そして、乱数ｒを情報Ｒ１として生成する（Ｓ１２１０）。続いて、検索情報生成装置１０２の検索インデックス生成部１２２は、内積述語暗号方式により、登録キーワードＷＴと、その登録キーワードＷＴを利用した検索を可能とするユーザのユーザ識別子Ｕとそのユーザ識別子Ｕに対応する属性情報ＡＦＬＵを含む検索権限情報ＡＣから属性ベクトルｘ→を生成する。属性ベクトルｘ→と公開鍵ｐｋを用いて、情報Ｒ１を内積述語暗号方式により暗号化することにより（Ｔ１，…，ＴＮ）を生成する。続いて、巡回群Ｇ１の生成元ｇと有限体Ｆｐ＊からあらかじめランダムに選択されたζを用いてτ＝ｇζを計算する。そして、（Ｔ１，…，ＴＮ）とτとハッシュ値Ｈを一組として情報Ｒ２：＝（Ｔ１，…，ＴＮ，τ，Ｈ）を生成する（Ｓ１２２０）。
【００７３】
続いて、検索情報生成装置１０２の検索インデックス生成部１２２は、暗号文Ｃ１を一意に識別するための情報Ｒ３を生成する（Ｓ１２３０）。そして、検索情報生成装置１０２の検索インデックス生成部１２２は、情報Ｒ１と情報Ｒ２と情報Ｒ３を一組とした検索インデックスＣ２：＝（Ｒ１，Ｒ２，Ｒ３）を生成し、検索情報保存装置４００へ送信する。
【００７４】
検索情報保存装置４００は、検索情報生成装置１０１から受信した検索インデックスＣ２を検索インデックス記憶部４９０へ記憶する（Ｓ４９０）。
【００７５】
図１４を参照して、本実施例の暗号文検索システム３０が暗号文を検索・復号する動作を実際に行われる手続きの順に従って説明する。
【００７６】
検索要求装置２０２の検索クエリ生成部２１１は、内積述語暗号方式により、検索キーワードＷＱから述語ベクトルｖ→を生成する。生成した述語ベクトルｖ→と公開鍵ｐｋと検索秘密鍵ｓｋＵを用いて、内積述語暗号方式により情報Ｒ２を復号するための秘密鍵である検索クエリｋ＊：＝（Ｑ１，…，ＱＮ）を生成する（Ｓ２１１）。続いて、検索要求装置２０２の検索クエリ生成部２１１は、検索クエリｋ＊を検索実行装置３０１へ送信する。
【００７７】
検索実行装置３０１の検索インデックス取得部３１０は、検索情報保存装置４００の検索インデックス記憶部４９０に記憶されている検索インデックスＣ２をダウンロードする（Ｓ３１０）。
【００７８】
検索実行装置３０１の検索結果判定部３２１は、検索要求装置２０２から受信した検索クエリｋ＊：＝（Ｑ１，…，ＱＮ）を用いて、すべての検索インデックスＣ２について、その検索インデックスＣ２に含まれる情報Ｒ２が式（６）を満たすか否かを判定する。式（６）を満たす場合には、その検索インデックスＣ２は検索が当たりであると判定する（Ｓ３２１）。
【００７９】
【数６】
0005670365.tif 000007
【００８０】
検索実行装置３０１の検索結果送信部３３０は、当たりと判定された検索インデックスＣ２から暗号文Ｃ１を一意に識別する情報Ｒ３を抽出して検索結果Ｃ３を生成し、生成した検索結果Ｃ３を検索要求装置２０２へ送信する（Ｓ３３０）。
【００８１】
検索要求装置２０２の暗号文取得部２２０は、検索実行装置３０１から受信した検索結果Ｃ３に含まれる情報Ｒ３を参照し、すべての情報Ｒ３について、その情報Ｒ３により一意に識別される暗号文Ｃ１を暗号情報保存装置５００からダウンロードする（Ｓ２２０）。
【００８２】
検索要求装置２０２の復号部２９０は、暗号情報保存装置５００からダウンロードした暗号文Ｃ１を復号して平文Ｍを取得する（Ｓ２９０）。
【００８３】
本実施例はこのような構成とすることにより、複数ユーザで利用が可能な内積述語検索可能暗号において、検索クエリｋ＊がクラウドを構成する装置に漏洩することを防止でき、辞書攻撃による検索キーワードの推定を防止できる。そのため、従来の暗号文検索システムに対してセキュリティを向上することができる。また、暗号情報を保存する暗号情報保存装置と検索を実行する検索実行装置が異なる装置として構成することができるため、システム全体としての検索処理量の増大に対応して検索実行装置を増設する場合に、追加するストレージ容量を抑制することができる。
【実施例３】
【００８４】
本実施例は、バッチ検索が可能な内積述語検索可能暗号に対してこの発明を適用した実施例である。バッチ検索が可能な内積述語検索可能暗号についての詳細は、非特許文献５を参照されたい。
【００８５】
図１５〜１７を参照して、この発明の実施例３の暗号文検索システム４０の動作を詳細に説明する。図１５は、本実施例の暗号文検索システム４０の構成を示すブロック図である。図１６は、本実施例の暗号文検索システム４０を構成する装置の構成を示すブロック図である。図１７は、本実施例の暗号文検索システム４０が暗号文を検索・復号する動作を示すフローチャートである。
【００８６】
図１５，１６を参照して、本実施例の暗号文検索システム４０の構成を説明する。本実施例の暗号文検索システム４０は、インターネット１とネットワーク２と検索情報生成装置１０２と検索要求装置２０３と検索実行装置３０２と検索情報保存装置４００と暗号情報保存装置５００から構成される。検索情報保存装置４００と暗号情報保存装置５００はインターネット１に接続される。検索情報生成装置１０２と検索要求装置２０３と検索実行装置３０２はネットワーク２に接続される。インターネット１とネットワーク２はルータやファイアウォールなどの各種のネットワーク機器によって接続されており、検索情報生成装置１０２と検索要求装置２０３と検索実行装置３０２と検索情報保存装置４００と暗号情報保存装置５００が相互に通信可能なように構成される。検索要求装置２０３は、検索クエリ生成部２１２と暗号文取得部２２０と復号部２９０を備える。検索実行装置３０２は、検索インデックス取得部３１０と検索結果判定部３２２と検索結果送信部３３０とユーザ登録部３４０と係数算出部３５０とバッチタグ生成部３６０を備える。
【００８７】
したがって、本実施例の検索要求装置２０３と実施例２の検索要求装置２０２とは、検索クエリ生成部の処理が異なることが相違点である。本実施例の検索実行装置３０２と実施例２の検索実行装置３０１とは、バッチタグ生成部３６０を備え、検索結果判定部の処理が異なることが相違点である。
【００８８】
以下の説明において、＾はべき乗を表し、ｔを検索インデックスＣ２の総数、ｊを検索インデックスＣ２の番号、Ｋ（＝ｌｏｇ２ｔ＋１）をバッチタグＢＴａｇの階層数、ｋ（０≦ｋ≦Ｋ−１）をバッチタグＢＴａｇの階層の番号、Ｍ（＝２＾（ｌｏｇ２ｔ−ｋ））をバッチタグＢＴａｇの各階層における要素数、ｍ（１≦ｍ≦Ｍ）をバッチタグＢＴａｇの各階層における要素の番号であるものとする。
【００８９】
本実施例の暗号文検索システム４０が暗号文を生成・保存する動作は、実施例２の暗号検索システム３０が暗号文を生成・保存する動作と同様であるため、説明は省略する。
【００９０】
図１７を参照して、本実施例の暗号文検索システム４０が暗号文を検索・復号する動作を実際に行われる手続きの順に従って説明する。
【００９１】
検索要求装置２０３の検索クエリ生成部２１２は、内積述語暗号方式により、キーワード空間Ｗから検索キーワードＷＱを除いた集合である否定キーワードＷＱ￣から述語ベクトルｖ→を生成する。生成した述語ベクトルｖ→と公開鍵ｐｋと検索秘密鍵ｓｋＵを用いて、内積述語暗号方式により情報Ｒ２を復号するための秘密鍵である検索クエリｋ＊：＝（Ｑ１￣，…，ＱＮ￣）を生成する（Ｓ２１２）。続いて、検索要求装置２０２の検索クエリ生成部２１２は、検索クエリｋ＊を検索実行装置３００へ送信する。
【００９２】
検索キーワードＷＱの否定キーワードＷＱ￣から述語ベクトルｖ→を生成する方法は、例えば以下のように行うことができる。まず、登録キーワードＸ１が検索キーワードＹ１である、あるいは登録キーワードＸ２が検索キーワードＹ２である、…、あるいは登録キーワードＸｍが検索キーワードＹｍである、という条件は式（７）にように表すことができる。
【００９３】
【数７】
0005670365.tif 000008
【００９４】
式（７）の否定表現は、キーワード空間Ｗから検索キーワードＹｉを除いた集合Ｗ＼｛Ｙ１，…，Ｙｍ｝：＝｛Ｖｉ｝（１≦ｉ≦Ｋ，Ｋ＝｜Ｗ＼｛Ｙ１，…，Ｙｍ｝｜）と乱数ｒｊ（１≦ｊ≦ｍ）を用いて、式（８）のように表すことができる。
【００９５】
【数８】
0005670365.tif 000009
【００９６】
以上より、登録キーワードベクトルＷＴ→＝（Ｘ１Ｋ，Ｘ１Ｋ−１，…，Ｘ１，１，…，ＸｍＫ，１）を属性ベクトルとし、否定キーワードベクトルＷＱ￣→＝（ｒ１ｓＫ，ｒ１ｓＫ−１，…，ｒ１ｓ１，ｒ１ｓ０，…，ｒｍｓＫ，ｒｍｓ０）を述語ベクトルとすればよい。
【００９７】
検索実行装置３０２の検索インデックス取得部３１０は、検索情報保存装置４００の検索インデックス記憶部４９０に記憶されている検索インデックスＣ２をダウンロードする（Ｓ３１０）。
【００９８】
検索実行装置３０２のバッチタグ生成部３６０は、検索インデックスＣ２（ｊ）：＝（Ｔ（ｊ，１），…，Ｔ（ｊ，Ｎ），τ（ｊ），Ｈ（ｊ），ｒ（ｊ））（１≦ｊ≦ｔ）から、Ｋ階層の２分木構造であるバッチタグＢＴａｇ（ｋ，ｍ）：＝（ＢＴ（ｋ，ｍ，１），…，ＢＴ（ｋ，ｍ，Ｎ），Ｂτ（ｋ，ｍ），ＢＨ（ｋ，ｍ），Ｂｒ（ｋ，ｍ））を生成する（Ｓ３６０）。階層０のバッチタグＢＴａｇ（０，ｍ）は、各要素の成分を式（９）のように設定することで生成する。
【００９９】
ＢＴ（０，ｍ，ｉ）＝Ｔ（ｊ，ｉ），
Ｂτ（０，ｍ）＝τ（ｊ），
ＢＨ（０，ｍ）＝Ｈ（ｊ），
Ｂｒ（０，ｍ）＝ｒ（ｊ）                                        （９）
（ただし、１≦ｉ≦Ｎ）
その他のバッチタグＢＴａｇ（ｋ，ｍ）は、各要素の成分を式（１０）のように設定することで生成する。
【０１００】
ＢＴ（ｋ，ｍ，ｉ）＝ＢＴ（ｋ−１，２ｍ−１，ｉ）＋ＢＴ（ｋ−１，２ｍ，ｉ），
Ｂτ（ｋ，ｍ）＝Ｂτ（ｋ−１，２ｍ−１）Ｂτ（ｋ−１，２ｍ），
ＢＨ（ｋ，ｍ）＝ＢＨ（ｋ−１，２ｍ−１）＋ＢＨ（ｋ−１，２ｍ），
Ｂｒ（ｋ，ｍ）＝Ｂｒ（ｋ−１，２ｍ−１）Ｂｒ（ｋ−１，２ｍ）    （１０）
（ただし、１≦ｉ≦Ｎ）
【０１０１】
検索実行装置３０２の検索結果判定部３２２は、検索要求装置２０３から受信した検索クエリｋ＊：＝（Ｑ１￣，…，ＱＮ￣）を用いて、階層（Ｋ−１）から階層１までのバッチタグＢＴａｇ（ｋ，ｍ）それぞれについて、そのバッチタグＢＴａｇ（ｋ，ｍ）が式（１１）を満たすか否かを判定する。ただし、階層ｋのバッチタグＢＴａｇ（ｋ，ｍ）について式（１１）を満たす場合には、次の階層（ｋ−１）の検証において、バッチタグＢＴａｇ（ｋ−１，２ｍ−１）とバッチタグＢＴａｇ（ｋ−１，２ｍ）は判定を行わない。そして、階層０のバッチタグＢＴａｇ（０，ｍ）それぞれについて、式（１１）を満たすか否かを判定する。式（１１）を満たさない場合には、その階層０のバッチタグＢＴａｇ（０，ｍ）に対応する検索インデックスＣ２は検索が当たりであると判定する（Ｓ３２２）。
【０１０２】
【数９】
0005670365.tif 000010
【０１０３】
検索実行装置３０２の検索結果送信部３３０は、当たりと判定された検索インデックスＣ２から暗号文Ｃ１を一意に識別する情報Ｒ３を抽出して検索結果Ｃ３を生成し、生成した検索結果Ｃ３を検索要求装置２０３へ送信する（Ｓ３３０）。
【０１０４】
検索要求装置２０３の暗号文取得部２２０は、検索実行装置３０２から受信した検索結果Ｃ３に含まれる情報Ｒ３を参照し、すべての情報Ｒ３について、その情報Ｒ３により一意に識別される暗号文Ｃ１を暗号情報保存装置５００からダウンロードする（Ｓ２２０）。
【０１０５】
検索要求装置２０３の復号部２９０は、暗号情報保存装置５００からダウンロードした暗号文Ｃ１を復号して平文Ｍを取得する（Ｓ２９０）。
【０１０６】
本実施例はこのような構成とすることにより、バッチ検索が可能な内積述語検索可能暗号において、検索クエリｋ＊がクラウドを構成する装置に漏洩することを防止でき、辞書攻撃による検索キーワードの推定を防止できる。そのため、従来の暗号文検索システムに対してセキュリティを向上することができる。また、暗号情報を保存する暗号情報保存装置と検索を実行する検索実行装置が異なる装置として構成することができるため、システム全体としての検索処理量の増大に対応して検索実行装置を増設する場合に、追加するストレージ容量を抑制することができる。
【０１０７】
［変形例］
実施例３では、検索実行装置がバッチタグの生成を行うように構成したが、検索情報保存装置がバッチタグの生成を行うように構成してもよい。
【０１０８】
図１８〜２０を参照して、この変形例の暗号文検索システム４０’の動作を詳細に説明する。図１８は、本変形例の暗号文検索システム４０’の構成を示すブロック図である。図１９は、本変形例の暗号文検索システム４０’を構成する装置の構成を示すブロック図である。図２０は、本変形例の暗号文検索システム４０’が暗号文を検索・復号する動作を示すフローチャートである。
【０１０９】
図１８，１９を参照して、本変形例の暗号文検索システム４０’の構成を説明する。本変形例の暗号文検索システム４０’は、インターネット１とネットワーク２と検索情報生成装置１０２と検索要求装置２０３と検索実行装置３０２’と検索情報保存装置４００’と暗号情報保存装置５００から構成される。検索情報保存装置４００’と暗号情報保存装置５００はインターネット１に接続される。検索情報生成装置１０２と検索要求装置２０３と検索実行装置３０２’はネットワーク２に接続される。インターネット１とネットワーク２はルータやファイアウォールなどの各種のネットワーク機器によって接続されており、検索情報生成装置１０２と検索要求装置２０３と検索実行装置３０２’と検索情報保存装置４００’と暗号情報保存装置５００が相互に通信可能なように構成される。検索実行装置３０２’は、検索インデックス取得部３１０’と検索結果判定部３２２と検索結果送信部３３０とユーザ登録部３４０と係数算出部３５０を備える。検索情報保存装置４００’は、バッチタグ生成部３６０と検索インデックス記憶部４９５と検索インデックス記憶部４９０を備える。
【０１１０】
したがって、本変形例の暗号文検索システム４０’と実施例３の暗号文検索システム４０とは、バッチタグ生成部３６０を検索実行装置の替わりに検索情報保存装置が備えており、検索情報保存装置がバッチタグ記憶部４９５を備えており、検索実行装置の検索インデックス取得部の動作が異なることが相違点である。
【０１１１】
検索情報保存装置４００’のバッチタグ生成部３６０は、検索インデックス記憶部４９０に記憶されている検索インデックスＣ２を用いてバッチタグＢＴａｇ（ｋ，ｍ）を生成する（Ｓ３６０）。生成したバッチタグＢＴａｇ（ｋ，ｍ）は、バッチタグ記憶部４９５へ記憶する。バッチタグＢＴａｇ（ｋ，ｍ）の生成は、検索情報生成装置１０２から検索インデックスＣ２を受信するたびに実行してもよいし、定期的に実行されるようにしてもよい。また、バッチタグ生成の処理速度が十分であれば、検索実行装置３０２’がバッチタグＢＴａｇ（ｋ，ｍ）のダウンロードを要求するたびに実行するようにしてもよい。バッチタグＢＴａｇ（ｋ，ｍ）の生成方法は実施例３と同様であるため、説明は省略する。
【０１１２】
検索実行装置３０２’の検索インデックス取得部３１０’は、検索情報保存装置４００’のバッチタグ記憶部４９５に記憶されているバッチタグＢＴａｇ（ｋ，ｍ）をダウンロードする（Ｓ３１０’）。常にすべてのバッチタグＢＴａｇ（ｋ，ｍ）をダウンロードしてもよいし、使用するネットワーク帯域を抑えるために、前回実行時に利用したバッチタグＢＴａｇ（ｋ，ｍ）を保持しておき、差分のみをダウンロードしてもよい。
【０１１３】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１１４】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１１５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１１６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１１９】
この発明は、クラウドストレージに保存されている暗号化された情報に対し暗号学的に安全にキーワード検索を行う暗号文検索システムに利用することができる。
【符号の説明】
【０１２０】
１０−４０  暗号文検索システム
１  インターネット
２  ネットワーク
１００−１０２  検索情報生成装置
１１０，１１１  暗号文生成部
１２０−１２２  検索インデックス生成部
１３０  ハッシュ値算出部
２００−２０３  検索要求装置
２１０−２１２  検索クエリ生成部
２２０  暗号文取得部
２９０  復号部
３００−３０２  検索実行装置
３１０  検索インデックス取得部
３２０−３２２  検索結果判定部
３３０  検索結果送信部
３４０  ユーザ登録部
３５０  係数算出部
３６０  バッチタグ生成部
４００  検索情報保存装置
４９０  検索インデックス記憶部
４９５  バッチタグ記憶部
５００  暗号情報保存装置
５９０  暗号文記憶部
８００  検索代行装置
８１０  検索結果判定部
８２０  検索結果送信部
８９０  記憶部
【図１】
0005670365.tif 000019
【図２】
0005670365.tif 000020
【図３】
0005670365.tif 000021
【図４】
0005670365.tif 000022
【図５】
0005670365.tif 000023
【図６】
0005670365.tif 000024
【図７】
0005670365.tif 000025
【図８】
0005670365.tif 000026
【図９】
0005670365.tif 000027
【図１０】
0005670365.tif 000028
【図１１】
0005670365.tif 000029
【図１２】
0005670365.tif 000030
【図１３】
0005670365.tif 000031
【図１４】
0005670365.tif 000032
【図１５】
0005670365.tif 000033
【図１６】
0005670365.tif 000034
【図１７】
0005670365.tif 000035
【図１８】
0005670365.tif 000036
【図１９】
0005670365.tif 000037
【図２０】
0005670365.tif 000038