(57)【特許請求の範囲】
【請求項１】
１つ以上のクエリ暗号化検索要求用キーワードを有するエントリ用検索クエリと前記エントリ用検索クエリが有する属性と１つ以上の暗号化代表元用キーワードを有するエントリ用代表元タグとを対応させて記憶するインデックス記憶部と、
登録暗号化情報と前記登録暗号化情報に対応する１つ以上の暗号化登録キーワードを有する登録キーワードタグとを受信する登録データ受信部と、
前記インデックス記憶部に記憶された前記エントリ用検索クエリと前記登録データ受信部が受信した前記登録キーワードタグとを照合し、前記エントリ用検索クエリと前記登録キーワードタグとが対応する場合に、前記登録データ受信部が受信した前記登録暗号化情報が前記インデックス記憶部に記憶された前記エントリ用検索クエリに対応する前記登録暗号化情報であると判定して、前記インデックス記憶部において前記登録暗号化情報を前記エントリ用検索クエリに関連付けるインデックス更新管理部と、
１つ以上のクエリ暗号化検索要求用キーワードを有する検索要求用クエリを受信する検索要求受信部と、
前記検索要求受信部が受信した検索要求用クエリから前記検索要求用クエリが有する属性を検出するインデックス分類部と、
前記インデックス記憶部に記憶された前記エントリ用代表元タグと前記検索要求受信部が受信した前記検索要求用クエリとを照合し、前記エントリ用代表元タグと前記検索要求用クエリとが対応する場合で、かつ前記インデックス記憶部に記憶された前記エントリ用検索クエリが有する属性と前記インデックス分類部が検出した検索要求用クエリが有する属性とを照合し、前記エントリ用検索クエリが有する属性と前記検索要求用クエリが有する属性とが対応する場合に、前記エントリ用代表元タグに関連付けられた登録用情報を出力する検索処理部と
を備えたことを特徴とする情報検索装置。
【請求項２】
前記インデックス更新管理部は、前記エントリ用検索クエリと前記登録キーワードタグとが対応する場合に、前記登録データ受信部が受信した前記登録暗号化情報を前記インデックス記憶部に記憶することを特徴とした請求項１記載の情報検索装置。
【請求項３】
前記情報検索装置は、さらに
登録暗号化情報を記憶するデータ保管部
を備え、
前記登録データ受信部は、受信した登録暗号化情報を前記データ保管部に記憶し、
前記インデックス更新管理部は、前記エントリ用検索クエリと前記登録キーワードタグとが対応する場合に、前記登録キーワードタグとともに受信した登録暗号化情報であって前記データ保管部に記憶された登録暗号化情報の識別子を前記インデックス記憶部に記憶することを特徴とした請求項１又は２記載の情報検索装置。
【請求項４】
前記データ保管部は、さらに前記登録暗号化情報に対応する登録キーワードタグを記憶し、
前記検索処理部は、前記データ保管部が記憶した登録キーワードタグと前記検索要求受信部が受信した前記検索要求用クエリとを照合し、前記データ保管部が記憶した登録キーワードタグと前記検索要求用クエリとが対応する場合に前記データ保管部が記憶した登録キーワードタグに対応する登録暗号化情報もしくは前記データ保管部が記憶した登録暗号化情報の識別子を前記インデックス記憶部に記憶することを特徴とした請求項３記載の情報検索装置。
【請求項５】
前記インデックス記憶部は、クエリ暗号化検索要求用キーワードの数を属性として、クエリ暗号化検索要求用キーワードの数毎にキーワード数別インデックスを記憶し、前記キーワード数別インデックスの各々は、クエリ暗号化検索要求用キーワードと暗号化代表元用キーワードの数が同じ数のエントリ用検索クエリとエントリ用代表元タグとの組を一つ以上記憶し、
前記インデックス分類部は、前記検索要求用クエリが有する属性として前記検索要求用クエリが有するクエリ暗号化検索要求用キーワードの数を検出し、
前記インデックス更新管理部は、前記インデックス分類部が検出したクエリ暗号化検索要求用キーワードの数に応じて、該当するキーワード数別インデックスに、前記登録暗号化情報と前記エントリ用代表元タグとの関連付けを記憶することを特徴とする請求項１〜４のいずれか一項に記載の情報検索装置。
【請求項６】
前記インデックス記憶部は、前記暗号化登録キーワードの登録フィールド番号を属性として、前記暗号化登録キーワードの登録フィールド番号とクエリ暗号化検索要求用キーワードとの対応関係を記述したエントリを記憶し、前記エントリの各々は、検索要求用フィールド番号とクエリ暗号化検索要求用キーワードとの対応関係とともに、エントリ用代表元タグを記憶し、
前記検索要求受信部は、クエリ暗号化検索要求用キーワードと前記クエリ暗号化検索要求用キーワードの検索要求用フィールド番号を有する検索要求用クエリを受信し、
前記インデックス分類部は、前記検索要求用クエリが有する属性として前記検索要求用クエリが有するクエリ暗号化検索要求用キーワードの検索要求用フィールド番号を一つ以上検出し、
前記インデックス更新管理部は、前記インデックス分類部が検出した一つ以上のクエリ暗号化検索要求用キーワードの検索要求用フィールド番号に対応するエントリに、前記登録暗号化情報と前記エントリ用代表元タグとの関連付けを記憶することを特徴とする請求項１〜４のいずれか一項に記載の情報検索装置。
【請求項７】
前記検索処理部は、前記エントリ用検索クエリが有する属性と前記検索要求用クエリが有する属性とを照合し、前記エントリ用検索クエリが有する属性と前記検索要求用クエリが有する属性とが一致する場合に、前記エントリ用検索クエリが有する属性と前記検索要求用クエリが有する属性とが対応すると判断することを特徴とする請求項１〜６のいずれか一項に記載の情報検索装置。
【請求項８】
前記登録データ受信部は、平文の登録キーワードＸと公開鍵とで暗号化された暗号化登録キーワードＣＸを一つ以上含む登録キーワードタグを受信し、
前記インデックス記憶部は、平文の検索要求用キーワードＹがユーザ秘密鍵で暗号化されたクエリ暗号化検索要求用キーワードＣＹを含む前記エントリ用検索クエリを記憶し、
前記インデックス更新管理部は、前記暗号化登録キーワードＣＸに対応した任意の平文Ｚが、前記登録キーワードタグの各暗号化登録キーワードＣＸを前記エントリ用検索クエリの各クエリ暗号化検索要求用キーワードＣＹで復号処理して前記任意の平文Ｚが復号されるか否かにより前記登録キーワードタグと前記エントリ用検索クエリとを照合し、前記エントリ用検索クエリが含む全てのクエリ暗号化検索要求用キーワードＣＹで前記任意の平文Ｚが復号出来る場合に、前記登録キーワードタグと前記エントリ用検索クエリとが対応すると判断することを特徴とする請求項５記載の情報検索装置。
【請求項９】
前記登録データ受信部は、平文の登録キーワードＸと公開鍵とで暗号化された暗号化登録キーワードＣＸと前記暗号化登録キーワードＣＸに対応した登録フィールド番号とをそれぞれ一つ以上含む登録キーワードタグを受信し、
前記インデックス記憶部は、平文の検索要求用キーワードＹがユーザ秘密鍵で暗号化されたクエリ暗号化検索要求用キーワードＣＹと前記クエリ暗号化検索要求用キーワードＣＹに対応した検索要求用フィールド番号とを含む前記エントリ用検索クエリを記憶し、
前記インデックス更新管理部は、前記暗号化登録キーワードＣＸに対応した任意の平文Ｚが、前記登録キーワードタグの各暗号化登録キーワードＣＸを前記エントリ用検索クエリの各クエリ暗号化検索要求用キーワードＣＹで復号処理して前記任意の平文Ｚが復号されるか否かにより前記登録キーワードタグと前記エントリ用検索クエリとを照合し、かつ、
前記インデックス分類部は、前記暗号化登録キーワードＣＸに対応する登録フィールド番号と前記クエリ暗号化検索要求用キーワードＣＹに対応する検索要求用フィールド番号とを比較し、
前記インデックス更新管理部は、前記エントリ用検索クエリが含む全てのクエリ暗号化検索要求用キーワードＣＹで前記任意の平文Ｚが復号出来て、かつ、前記暗号化登録キーワードＣＸに対応する登録フィールド番号と前記クエリ暗号化検索要求用キーワードＣＹに対応する検索要求用フィールド番号とが一致する場合に、前記登録キーワードタグと前記エントリ用検索クエリとが対応すると判断することを特徴とする請求項５記載の情報検索装置。
【請求項１０】
前記登録データ受信部は、平文の検索要求用キーワードＹがユーザ秘密鍵で暗号化されたクエリ暗号化検索要求用キーワードＣＹを一つ以上含む前記検索要求用クエリを受信し、
前記インデックス記憶部は、平文の代表元用キーワードＷと公開鍵とで暗号化された暗号化代表元用キーワードＣＷを一つ以上含むエントリ代表元タグを前記暗号化代表元用キーワードＣＷの数毎に関連付けられたキーワード数別インデックス毎に記憶し、
前記検索処理部は、前記暗号化代表元用キーワードＣＷに対応した任意の平文Ｚが、前記エントリ代表元タグの各暗号化代表元用キーワードＣＷを前記検索要求用クエリの各クエリ暗号化検索要求用キーワードＣＹで復号処理して前記任意の平文Ｚが復号されるか否かにより前記エントリ代表元タグと前記検索要求用クエリとを照合し、前記検索要求用クエリが含む全てのクエリ暗号化検索要求用キーワードＣＹで前記任意の平文Ｚが復号出来る場合に、前記登録キーワードタグと前記エントリ用検索クエリとが対応すると判断することを特徴とする請求項６記載の情報検索装置。
【請求項１１】
前記登録データ受信部は、平文の検索要求用キーワードＹがユーザ秘密鍵で暗号化されたクエリ暗号化検索要求用キーワードＣＹと前記クエリ暗号化検索要求用キーワードＣＹに対応した検索要求用フィールド番号とをそれぞれ一つ以上含む前記検索要求用クエリを受信し、
前記インデックス記憶部は、平文の代表元用キーワードＷと公開鍵とで暗号化された暗号化代表元用キーワードＣＷと前記暗号化代表元用キーワードＣＷに対応したエントリ用フィールド番号とをそれぞれ一つ以上含むエントリ代表元タグを前記暗号化代表元用キーワードＣＷの数毎に関連付けられたキーワード数別インデックス毎に記憶し、
前記検索処理部は、前記暗号化代表元用キーワードＣＷに対応した任意の平文Ｚが、前記エントリ代表元タグの各暗号化代表元用キーワードＣＷを前記検索要求用クエリの各クエリ暗号化検索要求用キーワードＣＹで復号処理して前記任意の平文Ｚが復号されるか否かにより前記エントリ代表元タグと前記検索要求用クエリとを照合し、かつ、
前記インデックス分類部は、前記クエリ暗号化検索要求用キーワードＣＹに対応する検索要求用フィールド番号と前記暗号化代表元用キーワードＣＷに対応するエントリ用フィールド番号とを比較し、
前記検索処理部は、前記検索要求用クエリが含む全てのクエリ暗号化検索要求用キーワードＣＹで前記任意の平文Ｚが復号出来て、かつ、前記クエリ暗号化検索要求用キーワードＣＹに対応する検索要求用フィールド番号と前記暗号化代表元用キーワードＣＷに対応するエントリ用フィールド番号とが一致する場合に、前記登録キーワードタグと前記エントリ用検索クエリとが対応すると判断することを特徴とする請求項６記載の情報検索装置。
【請求項１２】
前記インデックス記憶部は、複数のユーザにそれぞれ対応する複数の記憶領域を有することを特徴とする請求項１〜１１のいずれか一項に記載の情報検索装置。
【請求項１３】
コンピュータに、
１つ以上のクエリ暗号化検索要求用キーワードを有するエントリ用検索クエリと前記エントリ用検索クエリが有する属性と１つ以上の暗号化代表元用キーワードを有するエントリ用代表元タグとを対応させて記憶するインデックス記憶ステップと、
登録暗号化情報と前記登録暗号化情報に対応する１つ以上の暗号化登録キーワードを有する登録キーワードタグとを受信する登録データ受信ステップと、
前記インデックス記憶ステップで記憶された前記エントリ用検索クエリと前記登録データ受信ステップで受信した前記登録キーワードタグとを照合し、前記エントリ用検索クエリと前記登録キーワードタグとが対応する場合に、前記登録データ受信ステップで受信した前記登録暗号化情報が前記インデックス記憶ステップで記憶された前記エントリ用検索クエリに対応する前記登録暗号化情報であると判定して、前記登録暗号化情報を前記エントリ用検索クエリに関連付けるインデックス更新管理ステップと、
１つ以上のクエリ暗号化検索要求用キーワードを有する検索要求用クエリを受信する検索要求受信ステップと、
前記検索要求受信ステップで受信した検索要求用クエリから前記検索要求用クエリが有する属性を検出するインデックス分類ステップと、
前記インデックス記憶ステップで記憶された前記エントリ用代表元タグと前記検索要求受信ステップで受信した前記検索要求用クエリとを照合し、前記エントリ用代表元タグと前記検索要求用クエリとが対応する場合で、かつ前記インデックス記憶ステップで記憶された前記エントリ用検索クエリが有する属性と前記インデックス分類ステップで検出した検索要求用クエリが有する属性とを照合し、前記エントリ用検索クエリが有する属性と前記検索要求用クエリが有する属性とが対応する場合に、前記エントリ用代表元タグに関連付けられた登録用情報を出力する検索処理ステップと
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号化された情報を暗号化された検索要求用キーワードにより秘匿検索する情報検索装置および情報検索方法に関する。
【背景技術】
【０００２】
秘匿検索とは、検索者（以下ユーザと称する）の要求に応じて、情報検索システム（情報検索装置）が必要な情報を検索する場合に、情報検索システム（情報検索装置）は、暗号化された情報（以下暗号化情報と称する）を復号することなく、暗号化された状態で検索をすることである。（以下、秘匿検索に用いる情報検索システム（情報検索装置）を秘匿検索システムと称する）。
秘匿検索システムが暗号化情報そのものを検索することは出来ないので、秘匿検索システムは、検索可能な情報キーワードを暗号化したもの（以下タグと称する）を暗号化情報に付加してデータセンターに登録（記録もしくは保存）する。
【０００３】
ここでデータセンターとは、例えばデータサーバなどの大容量の記憶装置である。データセンターが登録した情報もしくはデータを、データセンターの管理者（データセンターの管理部門もしくは管理会社の人間）は閲覧することが可能である。
データセンターはユーザが用いる端末（以下ユーザ端末と称する）が入力した情報を保存し、保存した情報を管理し、ユーザ端末の要求に応じて検索し、ユーザ端末の要求に応じて検索した情報をユーザ端末に出力する等の機能を有する。
【０００４】
また、秘匿検索システムにおいて、ユーザは、タグの検索に用いる検索要求用キーワードも暗号化されたものを用いる（以下、暗号化された検索要求用キーワードを暗号化検索要求用キーワードと称する。また、暗号化検索要求用キーワードには以下に説明のタグ暗号化検索要求用キーワードとクエリ暗号化検索要求用キーワードとが有るが、特に区別の必要が無い場合は、暗号化検索要求用キーワードと称する）。もしくは、ユーザは、タグの検索に検索要求用クエリを用いる（ここで、検索要求用クエリとは、１つ以上の暗号化検索要求用キーワードで構成されたユーザ端末からの検索要求のことである。）。
すなわち、秘匿検索システムがデータセンターに保存した暗号化情報および、秘匿検索システムがデータセンターに保存した暗号化情報を検索する際に使用するクエリ暗号化検索要求用キーワード（もしくは検索要求用クエリ）とタグは全て暗号化されている。従って、解読可能な情報は、第３者（以下、第３者とは、例えばデータセンターの管理会社の人間などを示す）に漏れることが無い。
【０００５】
その為に、ユーザは第３者が管理するデータセンターに暗号化情報の保存、管理を委託することが可能である。
すなわち、ユーザはユーザ端末から暗号化情報をデータセンターに登録し、必要に応じてクエリ暗号化検索要求用キーワード（もしくは検索要求用クエリ）を用いて、データセンターに登録された暗号化情報に対応するタグを検索する。そして、ユーザは検索されたタグに対応する暗号化情報をユーザ端末に保存し、ユーザ端末で暗号化情報の復号処理を行い、暗号化情報の内容を閲覧する。
近年、例えばクラウドサービスなどのインターネット上にユーザが情報を保存する際、秘匿検索は、情報盗難などの脅威から守るためのセキュリティ技術として注目されている。
【０００６】
一方、秘匿検索は、保存されている暗号化情報、クエリ暗号化検索要求用キーワード（もしくは検索要求用クエリ）やタグから一切の情報を得られない。そこで、データセンターは暗号化情報の内容に応じて分類分け等の管理が出来ず、データセンターは分類毎の検索が出来ない。その為、一般的にはユーザから検索要求が有った際に、データセンターは保存されているすべてのタグを検索対象とする必要があり、保存された暗号化情報の増加による検索時間の増加が問題となる。
【０００７】
そこで、検索履歴（以下インデックス）を利用した秘匿検索の高速化手法が存在する。（例えば、特許文献１、非特許文献１参照）。
また、更に秘匿検索の検索効率改善手法として、複数の暗号化検索要求用キーワードを用いて秘匿検索を行う手法（例えば、非特許文献２参照）や、複数のユーザがタグを共有する手法（例えば、非特許文献３参照）が存在する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００５−１３４９９０
【非特許文献】
【０００９】
【非特許文献１】Ｄ．Ｂｏｎｅｈ、Ｇ．Ｄ．Ｃｒｅｓｃｅｎｚｏ、Ｒ．Ｏｓｔｒｏｖｓｋｙ、Ｐｅｒｓｉａｎｏ．Ｇ、  “Ｐｕｂｌｉｃ  Ｋｅｙ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ｋｅｙｗｏｒｄ  Ｓｅａｒｃｈ”、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＥＵＲＯＣＲＹＰＴ  ‘０４、ｖｏｌ．３０２７  ＬＮＣＳ、ｐｐ５０６−５２２（２００４）
【非特許文献２】Ｙ．Ｈ．Ｈｗａｎｇ、Ｐ．Ｊ．Ｌｅｅ、  “Ｐｕｂｌｉｃ  Ｋｅｙ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ｃｏｎｊｕｎｃｔｉｖｅ  Ｋｅｙｗｏｒｄ  Ｓｅａｒｃｈ  ａｎｄ  Ｉｔｓ  Ｅｘｔｅｎｓｉｏｎ  ｔｏ  ａ  Ｍｕｌｔｉ−ｕｓｅｒ  Ｓｙｓｔｅｍ”、Ｐａｉｒｉｎｇ  ２００７、ＬＮＣＳ  ４５７５、ｐｐ２−２２．
【非特許文献３】Ｍ．Ｈａｔｔｏｒｉ、Ｔ．Ｍｏｒｉ、Ｔ．Ｉｔｏ、Ｎ．Ｍａｔｓｕｄａ、Ｔ．Ｙｏｎｅｄａ、Ｋ．Ｏｈｔａ、  “Ａｎｏｎｙｍｏｕｓ  ＨＩＢＥ  ｗｉｔｈ  ｗｉｌｄｃａｒｄｓ  ａｎｄ  ｉｔｓ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｓｅｃｕｒｅ  ｋｅｙｗｏｒｄ  ｓｅａｒｃｈ  ｆｏｒ  ｇｒｏｕｐ−ｏｒｉｅｎｔｅｄ  ｍｕｌｔｉ−ｕｓｅｒ  ｓｙｓｔｅｍ，”、ＳＣＩＳ  ２０１０、３Ａ４−２、２０１０．
【発明の概要】
【発明が解決しようとする課題】
【００１０】
この発明の実施の形態は、例えば、複数の暗号化検索要求用キーワードを用いて高速な秘匿検索を行う情報検索装置を実現することを目的とする。
【課題を解決するための手段】
【００１１】
この発明に係る情報検索装置は、
１つ以上のクエリ暗号化検索要求用キーワードを有するエントリ用検索クエリと前記エントリ用検索クエリが有する属性と１つ以上の暗号化代表元用キーワードを有するエントリ用代表元タグとを対応させて記憶するインデックス記憶部と、
登録暗号化情報と前記登録暗号化情報に対応する１つ以上の暗号化登録キーワードを有する登録キーワードタグとを受信する登録データ受信部と、
前記インデックス記憶部に記憶された前記エントリ用検索クエリと前記登録データ受信部が受信した前記登録キーワードタグとを照合し、前記エントリ用検索クエリと前記登録キーワードタグとが対応する場合に、前記登録データ受信部が受信した前記登録暗号化情報が前記インデックス記憶部に記憶された前記エントリ用検索クエリに対応する前記登録暗号化情報であると判定して、前記インデックス記憶部において前記登録暗号化情報を前記エントリ用検索クエリに関連付けるインデックス更新管理部と、
１つ以上のクエリ暗号化検索要求用キーワードを有する検索要求用クエリを受信する検索要求受信部と、
前記検索要求受信部が受信した検索要求用クエリから前記検索要求用クエリが有する属性を検出するインデックス分類部と、
前記インデックス記憶部に記憶された前記エントリ用代表元タグと前記検索要求受信部が受信した前記検索要求用クエリとを照合し、前記エントリ用代表元タグと前記検索要求用クエリとが対応する場合で、かつ前記インデックス記憶部に記憶された前記エントリ用検索クエリが有する属性と前記インデックス分類部が検出した検索要求用クエリが有する属性とを照合し、前記エントリ用検索クエリが有する属性と前記検索要求用クエリが有する属性とが対応する場合に、前記エントリ用代表元タグに関連付けられた前記登録用情報を出力する検索処理部と
を備えたことを特徴とする。
【発明の効果】
【００１２】
この発明に係る情報検索装置は、複数の暗号化検索要求用キーワードを用いて高速な秘匿検索を行うことが可能となる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態１を示す図で、秘匿検索システムの外観の一例を示す図。
【図２】実施の形態１を示す図で、秘匿検索システム１００のハードウェア資源の一例を示す図。
【図３】実施の形態１を示す図で、秘匿検索システム１００の構成例を示す図。
【図４】実施の形態１を示す図で、ユーザ端末２０１の構成を示すブロック図。
【図５】実施の形態１を示す図で、タグ生成部２０６におけるタグ生成の動作を示す図（（ａ）はキーワードが１つの場合、（ｂ）はキーワードが３つの場合）。
【図６】実施の形態１を示す図で、登録データ２３０１の構成の例を示す図。
【図７】実施の形態１を示す図で、検索要求用クエリ生成部２０５における検索要求用クエリ２００２生成の動作を示す図（（ａ）はキーワードが１つの場合、（ｂ）はキーワードが３つの場合）。
【図８】実施の形態１を示す図で、検索要求２００１の構成の例を示す図。
【図９】実施の形態１を示す図で、データセンター３０１の構成を示すブロック図。
【図１０】実施の形態１を示す図で、検索要求用クエリ２００２で保管キーワードタグ４００３を復号する動作の第１の例を示す図。
【図１１】実施の形態１を示す図で、検索要求用クエリ２００２で保管キーワードタグ４００３を復号する動作の第２の例を示す図。
【図１２】実施の形態１を示す図で、検索要求用クエリ２００２で保管キーワードタグ４００３を復号する動作の第３の例を示す図。
【図１３】実施の形態１を示す図で、インデックス記憶部３０４に記憶される検索結果のデータ構造の一例を示す図。
【図１４】実施の形態１を示す図で、データセンター３０１で実施される処理の概要を示したフローチャート。
【図１５】実施の形態１を示す図で、検索処理部３０３におけるインデックス検査Ｓ４０３の動作を示すフローチャート。
【図１６】実施の形態１を示す図で、インデックス更新管理部３０６におけるインデックス登録Ｓ４０６の動作を示すフローチャート。
【図１７】実施の形態１を示す図で、ユーザが新規にデータをデータセンター３０１に登録する際の動作を示したフローチャート。
【図１８】実施の形態１を示す図で、登録データ２３０１と保管データ４００１との具体例を示す図（（ａ）は登録データ２３０１ａ、（ｂ）は登録データ２３０１ｂ、（ｃ）は登録データ２３０１ｃ、（ｄ）は保管データ４００１ａ、（ｅ）は保管データ４００１ｂ、（ｆ）は保管データ４００１ｃ）。
【図１９】実施の形態１を示す図で、検索要求２００１の具体例を示す図（（ａ）は検索要求２００１ａ、（ｂ）は検索要求２００１ｂ、（ｃ）は検索要求２００１ｃ）。
【図２０】実施の形態１を示す図で、ステップＳ４０５の保管データ全探索の動作を示す図。
【図２１】実施の形態１を示す図で、第１の検索要求２００１ａに基づくインデックス登録の例を示す図。
【図２２】実施の形態１を示す図で、検索要求２００１ａ〜ｃに基づくインデックス登録の例を示す図。
【図２３】実施の形態１を示す図で、検索要求２００１ａ〜ｃに基づくエントリ登録の例を示す図（（ａ）はエントリ３００３ａ、（ｂ）はエントリ３００３ｂ、（ｃ）はエントリ３００３ｃ）。
【図２４】実施の形態１を示す図で、登録データ２３０１ｄを示す図。
【図２５】実施の形態１を示す図で、登録データ２３０１ｄに含まれる登録暗号化情報がエントリに追加された例を示す図。
【図２６】実施の形態１を示す図で、検索要求２００１の更なる具体例を示す図（（ａ）は検索要求２００１ｄ、（ｂ）は検索要求２００１ｅ）。
【図２７】実施の形態２を示す図で、フィールド番号を含んだ登録データ２３０１の構成の例を示す図。
【図２８】実施の形態２を示す図で、フィールド番号を含んだ検索要求２００１の構成の例を示す図。
【図２９】実施の形態２を示す図で、フィールド番号を含んだインデックス記憶部３０４に記憶される検索結果のデータ構造の一例を示す図。
【図３０】実施の形態２を示す図で、インデックス検査Ｓ４０３の手順を示したフローチャート。
【図３１】実施の形態２を示す図で、インデックス登録Ｓ４０６の手順を示したフローチャート。
【図３２】実施の形態２を示す図で、インデックス検査Ｓ４０３における一致検査の具体例を示す図（（ａ）はエントリ３００３の具体例、（ｂ）は、検索要求２００１ａ、（ｃ）は、検索要求２００１ｂ、（ｄ）は、検索要求２００１ｃ）。
【図３３】実施の形態３を示す図で、データ保管部３０５の構造の一例を示す図。
【図３４】実施の形態３を示す図で、インデックス記憶部３０４に保存されるインデックス３００１の構造の一例を示す図。
【図３５】実施の形態３を示す図で、グループ共有を行わない場合のインデックス検査Ｓ４０３の手順を示したフローチャート。
【図３６】実施の形態３を示す図で、グループ共有を行う場合のインデックス検査Ｓ４０３の手順を示したフローチャート。
【発明を実施するための形態】
【００１４】
実施の形態１．
本実施の形態では、ユーザ（検索者、登録者）とデータセンター（データ管理者）の間で、複数のキーワードに対応した検索履歴を利用した秘匿検索を実施する際の、誤検索や検索漏れを防止する手法の例を説明する。
【００１５】
最初に、図１、図２、図３を用いて秘匿検索システムの概要を説明する。
【００１６】
図１は、秘匿検索システムの外観の一例を示す図である。
図１において、秘匿検索システム１００は、システムユニット９１０、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）やＬＣＤ（液晶）の表示画面を有する表示装置９０１、キーボード９０２（Ｋｅｙ・Ｂｏａｒｄ：Ｋ／Ｂ）、マウス９０３、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・  Ｄｒｉｖｅ）、コンパクトディスク装置９０５（ＣＤＤ）、プリンタ装置９０６、スキャナ装置９０７などのハードウェア資源を備え、これらはケーブルや信号線で接続されている。
また、これらのハードウェア資源をユーザ端末２０１と称している。
システムユニット９１０は、コンピュータであり、ファクシミリ機９３２、電話器９３１とケーブルで接続され、また、ローカルエリアネットワーク９４２（ＬＡＮ）、ゲートウェイ９４１を介してネットワーク１０１に接続されている。ネットワーク１０１の代表的な例はインターネットがある。
【００１７】
図２は、秘匿検索システム１００のハードウェア資源の一例を示す図である。
図２において、秘匿検索システム１００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５、プリンタ装置９０６、スキャナ装置９０７、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部の一例である。
通信ボード９１５、キーボード９０２、スキャナ装置９０７、ＦＤＤ９０４などは、入力部、入力装置の一例である。
また、通信ボード９１５、表示装置９０１、プリンタ装置９０６などは、出力部、出力装置の一例である。
【００１８】
通信ボード９１５は、ファクシミリ機９３２、電話器９３１、ＬＡＮ９４２等に接続されている。通信ボード９１５は、ＬＡＮ９４２に限らず、ネットワーク１０１、ＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）などに接続されていても構わない。ネットワーク１０１或いはＩＳＤＮ等のＷＡＮに接続されている場合、ゲートウェイ９４１は不用となる。
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。
【００１９】
上記プログラム群９２３には、以下に述べる実施の形態の説明において「〜部」として説明する機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
ファイル群９２４には、以下に述べる実施の形態の説明において、「〜の判定結果」、「〜の計算結果」、「〜の処理結果」として説明する情報やデータや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵの動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
また、以下に述べる実施の形態の説明において説明するフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、ＦＤＤ９０４のフレキシブルディスク、ＣＤＤ９０５のコンパクトディスク、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｋ）等の記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【００２０】
また、以下に述べる実施の形態の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「手段」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、以下に述べる「〜部」としてコンピュータを機能させるものである。あるいは、以下に述べる「〜部」の手順や方法をコンピュータに実行させるものである。
【００２１】
図３は、秘匿検索システム１００の構成例を示す図である。図３は、図１に示した秘匿検索システム１００の外観の一例を簡略化して図示している。
秘匿検索システム１００は、ユーザ端末２０１、データセンター３０１を備える。ユーザ端末２０１はローカルエリアネットワーク９４２に接続されている。ローカルエリアネットワーク９４２はネットワーク１０１を介してデータセンター３０１と接続されている。
ユーザ端末２０１は、例えば企業のユーザが利用するＰＣ（パーソナルコンピュータ）である。
ネットワーク１０１は、ローカルエリアネットワーク９４２とデータセンター３０１を接続する通信路である。
ローカルエリアネットワーク９４２は、企業内に施設された通信路であり、企業内で利用される様々なサーバやＰＣが接続される。なお、通信路は専用線や無線、ルータなどで構成される複雑な通信路となる。
ここで、図１はローカルエリアネットワーク９４２を使用した例を示している。しかし、例えば個人が家庭でユーザ端末２０１を使用する場合などは、ユーザ端末２０１は、ローカルエリアネットワーク９４２を介せず、直接ネットワーク１０１に接続することも可能である。
【００２２】
ここで、秘匿検索システム１００の大まかな動作を説明する。
秘匿検索システム１００に用いる暗号方式は、基本的にはＩＤベース暗号（以下  ＩＢＥ：Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ）を用いた秘匿検索方式である。この方式によりユーザはデータセンター３０１に登録する情報も、検索時のキーワードも全て暗号化したまま、情報検索が可能である。以下に詳細を説明する。
まず、ユーザはユーザ端末２０１を用いて、ユーザが保存したい暗号化情報と暗号化情報に対応したタグ（以下、登録キーワードタグと称する）を組にしてデータセンター３０１に保存する。（なお、本実施の形態の説明においては、データ保管部３０５に保存された登録キーワードタグを保管キーワードタグと称しているが、実質的に同一のものであり、特に区別の必要が無い場合は、登録キーワードタグの表現を用いる）。
また、暗号化登録キーワードは暗号化情報を検索するための登録キーワード（暗号化情報の保存時にユーザが設定したキーワード）を暗号化したものである。そして、登録キーワードタグは１つ以上の暗号化登録キーワードから構成される。更に詳細に説明すると、暗号化登録キーワード（登録キーワードタグ）はユーザが入力した任意の平文を登録キーワードと公開鍵とで暗号化したものである。なお、任意の平文は、無意味な平文であり、以下無意味な平文と称する。ここで、暗号化情報と暗号化登録キーワード（登録キーワードタグ）は暗号化されていて、第３者は、情報を閲覧することが出来ない。
検索時には、ユーザは検索要求用キーワードをユーザ秘密鍵で暗号化したクエリ暗号化検索要求用キーワード（もしくは検索要求用クエリ）をデータセンター３０１に送信する。ここで、クエリ暗号化検索要求用キーワード（もしくは検索要求用クエリ）も暗号化されていて第３者は、情報を閲覧することが出来ない。
データセンター３０１は、検索要求用クエリを用いて、保存している登録キーワードタグと一致検査を行う。検索要求用クエリと登録キーワードタグとが一致すれば、データセンター３０１は、組で保存されている暗号化情報をユーザに返却する。ここで、検索要求用クエリと登録キーワードタグとが一致とは、検索要求用クエリで登録キーワードタグを復号して、元の無意味な平文が得られることをいう。復号された無意味な平文からも第３者は情報を閲覧することが出来ず、第３者は、検索要求用クエリと登録キーワードタグとが一致したという状態が分かるのみとなる。その為にユーザは第３者に対する秘匿検索が可能である。
また、データセンター３０１は、企業内で作成された暗号化情報および登録キーワードタグを保存する大容量の記憶装置を持つサーバである。またデータセンター３０１は、一度検索された暗号化検索要求用キーワードの検索結果をインデックスとして保存し、次回以降に同一のキーワードが検索された場合に、そのインデックスを利用して高速に応答する機能を備える。
【００２３】
次に、図４を用いて本実施の形態にて構成されているユーザ端末２０１について、更に詳しく説明する。
【００２４】
図４は、ユーザ端末２０１の構成を示すブロック図である。
ユーザ端末２０１は、情報・鍵格納領域２０２、暗号化情報管理部２０３、ユーザインターフェース２０４、検索要求用クエリ生成部２０５、タグ生成部２０６、通信モジュール２０７を備える。
【００２５】
情報・鍵格納領域２０２は、暗号化情報の基であるオリジナルの情報を保存する。ここでオリジナルの情報とは、例えば数値データや図面や文章などの平文の情報そのものでも良いし、既に暗号化された情報でも良い。またオリジナルの情報は、情報名やファイル名、情報を保存しているデータベースの位置情報などで有っても良いし、これらの組み合わせ（例えば前記の平文の情報そのものとファイル名の組み合わせなど）でも良い。
また、情報・鍵格納領域２０２は、情報を暗号化して暗号化情報を生成する為の鍵（暗号化情報生成鍵）と、検索要求用キーワードを暗号化して検索要求用クエリを生成する為のユーザ秘密鍵と、タグを生成するための公開鍵を保存する。
【００２６】
暗号化情報管理部２０３は、情報・鍵格納領域２０２に保存されている情報を暗号化し、暗号化情報を生成する。暗号化情報からは、第３者は、情報を閲覧することはできない。暗号化の方法としては、検索要求用クエリ生成部２０５やタグ生成部２０６で用いられる暗号化の方法とは別の方法が用いられる。
ユーザインターフェース２０４は、秘匿検索システム１００をユーザが操作するためのインタフェースである。ユーザインターフェース２０４は、検索要求用クエリ生成部２０５や、タグ生成部２０６で用いるキーワードと無意味な平文をユーザが入力する機能を備える。なお、ユーザは、１つ以上のキーワード入力が可能である。
【００２７】
通信モジュール２０７は、検索要求用クエリ生成部２０５、タグ生成部２０６、暗号化情報管理部２０３が生成した検索要求（検索要求用クエリや検索要求用代表元タグ）や登録データ（受信暗号化情報や受信キーワードタグや無意味な平文）を、データセンター３０１に送信するために、ローカルエリアネットワーク９４２もしくはネットワーク１０１に接続するものである。
【００２８】
ここで、検索要求と登録データの説明を行う。
【００２９】
まず、図５、図６を用いてタグ生成部２０６における暗号化の動作および登録データの構造を説明する。
【００３０】
図５は、タグ生成部２０６におけるタグ生成の動作を示す図である。（（ａ）はキーワードが１つの場合、（ｂ）はキーワードが３つの場合）。
ユーザは、ユーザインターフェース２０４を介して無意味な平文２３０５と登録キーワード２３００とを入力する。
タグ生成部２０６は、ユーザが入力した無意味な平文２３０５に登録キーワード２３００と情報・鍵格納領域２０２に保存された公開鍵とから暗号化登録キーワード２３０４と登録キーワードタグ２３０３とを生成する。また、タグ生成部２０６は、ユーザがユーザインターフェース２０４を介して入力した検索要求用キーワード２０００と情報・鍵格納領域２０２に保存された公開鍵とからタグ暗号化検索要求用キーワード２００５と検索要求用代表元タグ２００４とを生成する。
【００３１】
具体的には、図５（ａ）を用いて登録データの生成を説明する。
例えば、ユーザがデータセンター３０１に保存する情報が「自動車」に関する情報とする。そして、データセンター３０１に保存する情報に「エンジン」に関係する記述が有る為にユーザは、登録キーワード２３００として「エンジン」をユーザインターフェース２０４を介してタグ生成部２０６に入力する。
そして、タグ生成部２０６は、ユーザがユーザインターフェース２０４を介して入力した無意味な平文２３０５（例えば、ｐｅｎｃｉｌ）を登録キーワード２３００の「エンジン」と情報・鍵格納領域２０２に保存された公開鍵とで暗号化し、暗号化登録キーワード２３０４（登録キーワードタグ２３０３）を生成する。
同様に、図５（ｂ）のようにユーザがデータセンター３０１に保存する情報に「エンジン」「タイヤ」「ハンドル」に関係する記述が有る為、登録キーワード２３００として「エンジン」「タイヤ」「ハンドル」の３つのキーワードを設定したとする。その場合は、タグ生成部２０６は、無意味な平文２３０５（例えば、ｐｅｎｃｉｌ、ｒａｉｎ、ｃａｎｄｙ）を登録キーワード２３００の「エンジン」「タイヤ」「ハンドル」と情報・鍵格納領域２０２に保存された公開鍵とで暗号化し、暗号化登録キーワード２３０４（登録キーワードタグ２３０３）を生成する。
【００３２】
図６は、登録データ２３０１の構成の例を示す図である。
登録データ２３０１は、登録暗号化情報２３０２と登録キーワードタグ２３０３と無意味な平文２３０５とから構成される。
ここでは、図５（ｂ）に説明した例を用いる。ユーザがデータセンター３０１に保存する情報が情報・鍵格納領域２０２に保存されている例えば「自動車情報１」であったとする。そして、暗号化情報管理部２０３は、「自動車情報１」を暗号化し、登録暗号化情報２３０２を生成する。登録暗号化情報の暗号化の方法としては、検索要求用クエリ生成部２０５やタグ生成部２０６で用いられる暗号化の方法とは別の方法が用いられる。（例えば、登録暗号化情報２３０２を生成の為の独自のユーザ秘密鍵など）。また、ここでは保存する情報を平文のテキスト文書のようなものと想定しているが、数値データや画像データでも良い。また、保存する情報は、情報名やファイル名、情報を保存しているデータベースの位置情報などで有っても良いし、これらの組み合わせ（例えば前記の平文の情報そのものとファイル名の組み合わせなど）でも良い。また保存する情報そのものが元々暗号化されていても良い。
そして、登録キーワードタグ２３０３は、図５（ｂ）で説明の通り、登録暗号化情報２３０２に対応した（関連した）３つのキーワードが設定されている。
なお、無意味な平文２３０５は平文のまま登録キーワードタグ２３０３の暗号化登録キーワード２３０４と対応して登録データ２３０１に含まれる。
また、暗号化登録キーワード２３０４（登録キーワードタグ２３０３）は暗号化されており、暗号化登録キーワード２３０４（登録キーワードタグ２３０３）を生成する為に用いた登録キーワード２３００を第３者は知ることが出来ない。しかし、第３者（もしくはデータセンター３０１）は、登録キーワードタグ２３０３の属性として、登録キーワードタグ２３０３に含まれる暗号化登録キーワード２３０４の数は知ることが出来る。
【００３３】
そして、図７、図８を用いて検索要求用クエリ生成部２０５における暗号化の動作および検索要求の構造を説明する。
図７は、検索要求用クエリ生成部２０５における検索要求用クエリ２００２生成の動作を示す図である。（（ａ）はキーワードが１つの場合、（ｂ）はキーワードが３つの場合）。
検索要求用クエリ生成部２０５は、ユーザがユーザインターフェース２０４を介して入力したユーザが検索したいキーワード（以下、検索要求用キーワード２０００と称す）と情報・鍵格納領域２０２に保存されたユーザ秘密鍵とからクエリ暗号化検索要求用キーワード２００３と検索要求用クエリ２００２を生成する。
【００３４】
具体的には、図７（ａ）を用いて検索要求の生成を説明する。
例えば、ユーザが「エンジン」に関係する情報を検索したいとする。そして、ユーザは、検索要求用キーワード２０００として「エンジン」をユーザインターフェース２０４を介して検索要求用クエリ生成部２０５に入力する。
そして、検索要求用クエリ生成部２０５は、検索要求用キーワード２０００の「エンジン」を情報・鍵格納領域２０２にユーザ秘密鍵で暗号化し、クエリ暗号化検索要求用キーワード２００３と検索要求用クエリ２００２を生成する。
また、ユーザが検索要求用キーワード２０００として「エンジン」「タイヤ」「ハンドル」の３つのキーワードを設定したとする。その場合は、検索要求用クエリ生成部２０５は、検索要求用キーワード２０００の「エンジン」「タイヤ」「ハンドル」を情報・鍵格納領域２０２に保存されたユーザ秘密鍵で暗号化し、検索要求用クエリ２００２を生成する。
【００３５】
図８は、検索要求２００１の構成の例を示す図である。ここでは、図５（ｂ）と図７（ｂ）に説明した例（３つのキーワードが設定された場合）を図示している。
検索要求２００１は、検索要求用クエリ２００２と検索要求用代表元タグ２００４と無意味な平文２３０５から構成される。
検索要求２００１の生成において、ユーザが入力した検索要求用キーワード２０００は、図４に示すように検索要求用クエリ生成部２０５とタグ生成部２０６の両方に入力される。そして、検索要求用クエリ生成部２０５は、検索要求用クエリ２００２を生成し、タグ生成部２０６は、検索要求用代表元タグ２００４を生成する。そして、ユーザ端末２０１は、両者を組み合わせて検索要求２００１を生成する。
なお、無意味な平文２３０５は平文のまま検索要求用代表元タグ２００４のタグ暗号化検索要求用キーワード２００５に対応して検索要求用クエリ２００２に含まれる。（以下の説明においては、検索要求用クエリ２００２に含まれる無意味な平文２３０５の図示は省略する）。
また、検索要求用クエリ２００２は暗号化されており、検索要求用クエリ２００２を生成する為に用いた検索要求用キーワード２０００を第３者は知ることが出来ない。しかし、第３者（もしくはデータセンター３０１）は、検索要求用クエリ２００２の属性として、検索要求用クエリ２００２に含まれるクエリ暗号化検索要求用キーワード２００３の数は知ることが出来る。
同様に、検索要求用代表元タグ２００４は暗号化されており、検索要求用代表元タグ２００４を生成する為に用いた検索要求用キーワード２０００を第３者は知ることが出来ない。しかし、第３者（もしくはデータセンター３０１）は、検索要求用代表元タグ２００４の属性として、検索要求用代表元タグ２００４に含まれるタグ暗号化検索要求用キーワード２００５の数は知ることが出来る。
【００３６】
次に、図９を用いてデータセンター３０１の説明を行う。
【００３７】
図９は、データセンター３０１の構成を示すブロック図である。
データセンター３０１は、検索要求受信部３０２、検索処理部３０３、インデックス記憶部３０４、データ保管部３０５、インデックス更新管理部３０６、検索要求回答部３０７、登録データ受信部３０８、インデックス分類部３０９を備える。
なお、インデックス分類部３０９は、検索処理部３０３もしくはインデックス更新管理部３０６に含まれていても構わない。
【００３８】
まず各構成要素の概要を説明する。
【００３９】
検索要求受信部３０２は、ユーザ端末２０１から送信された検索要求２００１を受信し、検索処理部３０３へ入力する。
登録データ受信部３０８は、ユーザ端末２０１から登録データ２３０１を受信すると、インデックス更新管理部３０６とデータ保管部３０５に登録データ２３０１を入力する。
データ保管部３０５は、登録データ受信部３０８から受信した登録データ２３０１を保管データ４００１として保存する。その際にデータ保管部３０５は、登録暗号化情報２３０２を保管暗号化情報４００２として、登録キーワードタグ２３０３を保管キーワードタグ４００３として保存する。（登録データ２３０１と保管データ４００１は実質的に同一のものであり、特に区別の必要が無い場合は、登録データ２３０１の表現を用いている。登録暗号化情報２３０２と保管暗号化情報４００２、登録キーワードタグ２３０３と保管キーワードタグ４００３についても同様である。）また、データ保管部３０５は、無意味な平文２３０５も保管データ４００１の一部として保存する。
保管キーワードタグ４００３は、登録キーワードタグ２３０３と同一構造であり、保管キーワードタグ４００３を生成する為に用いた登録キーワード２３００を第３者は知ることが出来ない。しかし、第３者（もしくはデータセンター３０１）は、保管キーワードタグ４００３の属性として保管キーワードタグ４００３に含まれる暗号化登録キーワード２３０４の数は知ることが出来る。
【００４０】
検索処理部３０３は、検索要求受信部３０２から検索要求２００１を受信し、検索要求２００１に応じて、インデックス記憶部３０４もしくはデータ保管部３０５の検索を行う。
インデックス記憶部３０４は、過去に検索処理部３０３が検索した検索結果を保存する。
インデックス分類部３０９は、クエリ暗号化検索要求用キーワード２００３の数に応じてインデックス記憶部３０４の検索対象領域を決定する。
インデックス更新管理部３０６は、インデックス記憶部３０４に保存された内容を更新する。
検索要求回答部３０７は、検索処理部３０３によって検索された登録暗号化情報２３０２をユーザ端末２０１に送信する。
【００４１】
前記のデータセンター３０１の各構成要素の内、まずは検索処理部３０３がデータ保管部３０５の検索を行う例を詳細説明する。
【００４２】
検索処理部３０３は、検索要求受信部３０２から入力された検索要求２００１に応じて、データ保管部３０５に保存された保管データ４００１を検索する。その際に、検索処理部３０３は、検索要求２００１に含まれる検索要求用クエリ２００２で保管データ４００１に含まれる保管キーワードタグ４００３を照合（復号処理）する。そして、検索要求用クエリ２００２で保管キーワードタグ４００３が復号出来た場合に、検索要求用クエリ２００２に含まれるクエリ暗号化検索要求用キーワード２００３と保管キーワードタグ４００３に含まれる暗号化登録キーワード２３０４とが一致したと判断する。
【００４３】
ここで、図１０、図１１、図１２を用いて検索要求用クエリ２００２で保管キーワードタグ４００３を復号する動作を説明する。
【００４４】
図１０は、検索要求用クエリ２００２で保管キーワードタグ４００３を復号する動作の第１の例を示す図である。
図１１は、検索要求用クエリ２００２で保管キーワードタグ４００３を復号する動作の第２の例を示す図である。
図１２は、検索要求用クエリ２００２で保管キーワードタグ４００３を復号する動作の第３の例を示す図である。
なお、図１０〜図１２における検索要求用クエリ２００２の無意味な平文２３０５の図示は省略している。
【００４５】
まず図１０に示す例は、登録データ２３０１における登録キーワードタグ２３０３の暗号化登録キーワード２３０４が３つ有る場合（図５（ｂ）の例と同じ）である。この登録データ２３０１がデータ保管部３０５に保管データ４００１として保存されることで、同じく保管キーワードタグ４００３は、暗号化登録キーワード２３０４が３つ有る状態となっている。そして、検索要求用クエリ２００２は、クエリ暗号化検索要求用キーワード２００３が１つの場合（図７（ａ）の例と同じ）である。
【００４６】
検索処理部３０３は、図１０に示す検索要求２００１に含まれる検索要求用クエリ２００２で、保管データ４００１に含まれる保管キーワードタグ４００３を復号する。そして、無意味な平文２３０５（例えばｐｅｎｃｉｌ）が正しく再現出来れば、検索処理部３０３は、検索要求用クエリ２００２と保管キーワードタグ４００３が一致すると判断する。ここで、無意味な平文２３０５は、ユーザ端末２０１のタグ生成部２０６において暗号化された登録キーワードタグ２３０３を生成する際に用いられたものである。（以下、復号処理により正しい無意味な平文が再現することを、「一致する」もしくは「復号出来る」と表現する）。
そして、検索処理部３０３は、検索要求用クエリ２００２に一致した保管キーワードタグ４００３に対応する保管暗号化情報４００２が検索要求用キーワード２０００に対応する保管暗号化情報であると判断する。
なお、無意味な平文２３０５は、登録キーワードタグ２３０３と一緒に登録データ２３０１の一部としてデータ保管部３０５に保存されている。そこで、検索処理部３０３は、データ保管部３０５に保存された無意味な平文２３０５を参照することで、復号において無意味な平文２３０５を正しく再現したかを判断する。
【００４７】
次に図１１に示す例は、検索要求用クエリ２００２のクエリ暗号化検索要求用キーワード２００３が２つの場合で、２つのクエリ暗号化検索要求用キーワード２００３が両方とも保管キーワードタグ４００３の暗号化登録キーワード２３０４に一致する場合である。この場合は、検索要求用キーワード「エンジン」と「ハンドル」それぞれに対応した無意味な平文２３０５（例えばＰｅｎｃｉｌとＣａｎｄｙ）は、正しく再現される。そして、検索処理部３０３は、検索要求用クエリ２００２と保管キーワードタグ４００３とが一致すると判断する。
【００４８】
一方、図１２に示す例は、検索要求用クエリ２００２のクエリ暗号化検索要求用キーワード２００３が２つの場合である。そして、２つのクエリ暗号化検索要求用キーワード２００３のうち１つしか保管キーワードタグ４００３の暗号化登録キーワード２３０４に一致しない場合である。この場合は、検索要求用キーワード「エンジン」に対応した無意味な平文２３０５（例えばＰｅｎｃｉｌ）が正しく再現されるが、検索要求用キーワード「アクセル」に対応した無意味な平文２３０５は誤って再現される。（例えば％６ｈ＋￥）。
そこで、検索処理部３０３は、検索要求用クエリ２００２と保管キーワードタグ４００３とが一致しないと判断する。
【００４９】
次に、図１３を用いて前記データセンター３０１の各構成要素の内、インデックス記憶部３０４の詳細を説明する。
図１３は、インデックス記憶部３０４に記憶される検索結果のデータ構造の一例を示す図である。インデックス３００１は、複数（例えばｎ個）のキーワード数別インデックス３００２で構成される。キーワード数別インデックス３００２は、検索要求用クエリ２００２に含まれるｎ個（ｎ≧１）のキーワード数に対応する。（図中に３００２−１〜３００２−ｎで表記）。さらに、キーワード数別インデックス３００２は、１つ以上のエントリ３００３から構成され、ユーザの検索要求により、必要に応じて生成される。
そして、エントリ３００３は、エントリ用代表元タグ３００４、エントリ用検索クエリ３００６、エントリ用暗号化情報３００７、無意味な平文２３０５から構成される。
エントリ用代表元タグ３００４は、１つ以上の暗号化代表元用キーワードで構成される。実施の形態１においては、エントリ用代表元タグ３００４は、検索要求２００１に含まれる検索要求用代表元タグ２００４が保存されたものである。その為、暗号化代表元用キーワードは、タグ暗号化検索要求用キーワード２００５となる。また、暗号化代表元用キーワードは、無意味な平文２３０５が代表元用キーワードと公開鍵とで暗号化されたものである。その為、代表元用キーワードは検索要求用キーワード２０００となる。エントリ用検索クエリ３００６は、検索要求２００１に含まれる検索要求用クエリ２００２が保存されたものである。エントリ用暗号化情報３００７は、複数の登録暗号化情報２３０２もしくは保管暗号化情報４００２がエントリ３００３に保存されたものである。もしくは、エントリ用暗号化情報３００７は、データ保管部３０５における保管暗号化情報４００２の識別子であっても良い。ここで、識別子とは、データの保管場所を示すアドレス情報であっても良いし、データの保管場所を示すリンクやポインタであっても良いし、データを特定可能なファイル名で有っても良い。
また、無意味な平文２３０５は、エントリ用代表元タグ３００４が正しく復号されたかを検索処理部３０３が判断するのに用いられる。
【００５０】
次いで、秘匿検索システム１００のデータ検索処理の概要説明を行う。
図１４は、データセンター３０１で実施される処理の概要を示したフローチャートである。
【００５１】
まず、ステップＳ４０１において、データセンター３０１は、ユーザ端末２０１からネットワーク１０１を経由して送信される検索要求２００１を、検索要求受信部３０２で受信する。
次に、ステップＳ４０２において、検索要求受信部３０２は、検索要求２００１を検索処理部３０３に転送する。
次に、ステップＳ４０３において、検索処理部３０３は、インデックス分類部３０９により指定されたインデックス記憶部３０４のキーワード数別インデックス３００２を参照する。そして、検索処理部３０３は、検索要求受信部３０２から転送された検索要求用クエリ２００２に含まれるキーワードが、インデックス記憶部３０４に保存されているか検査する。
次に、ステップＳ４０４において、検索処理部３０３は、受信した検索要求２００１のタグ暗号化検索要求用キーワード２００５がインデックス記憶部３０４に存在した場合（該当あり）は、エントリ３００３のエントリ用暗号化情報３００７から該当する暗号化情報を読み出し、検索要求回答部３０７を介して、検索要求のあったユーザ端末２０１へ回答する。
また、ステップＳ４０５において、Ｓ４０３の検査で検索要求２００１のタグ暗号化検索要求用キーワード２００５がインデックス記憶部３０４に存在しなかった場合（該当なし）、検索処理部３０３は、データ保管部３０５を検索する。その際、検索処理部３０３は、インデックス検査Ｓ４０３で判定したエントリ用代表元タグ３００４と同じ保管キーワードタグ４００３を持つ保管データ４００１を検索対象から除外する。
次に、ステップＳ４０６において、インデックス更新管理部３０６は、Ｓ４０５の検索の結果、検索要求２００１に一致する登録データ２３０１がある場合（該当暗号化情報あり）、インデックス登録を行う。そして、Ｓ４０４において、検索処理部３０３は、該当する暗号化情報を読み出し、検索要求回答部３０７を介して、検索要求のあったユーザ端末２０１へ回答する。
Ｓ４０５において、データ保管部３０５にも、検索要求に該当するデータが存在しない場合（該当暗号化情報なし）、検索処理部３０３は、検索要求回答部３０７を介して、検索要求のあったユーザ端末２０１へ該当データが存在しない旨を回答する。
【００５２】
そして、秘匿検索システム１００のデータ検索処理の詳細説明を行う。
【００５３】
まず図１５を参照し、本実施の形態におけるインデックス検査Ｓ４０３を詳しく説明する。
図１５は、検索処理部３０３におけるインデックス検査Ｓ４０３の動作を示すフローチャートである。
まず、ステップＳ５０１において、検索処理部３０３は、受信した検索要求２００１をインデックス分類部３０９に入力する。インデックス分類部３０９は、検索要求２００１の検索要求用クエリ２００２に含まれるクエリ暗号化検索要求用キーワード２００３の数に応じてキーワード数別インデックス３００２の内、どのキーワード数別インデックスを検索するかを選択する。
次に、ステップＳ５０２において、検索処理部３０３は、インデックス分類部３０９が選択したキーワード数別インデックスから、未検査のエントリ３００３があるかを検査する。
次に、ステップＳ５０３において、検索処理部３０３は、未検査のエントリが無い場合は、検索要求２００１に該当するデータが存在しないため「該当なし」とし、保管データ全探索Ｓ４０５に進むため、インデックス検査Ｓ４０３を終了する。未検査のエントリがある場合、そこに保存されているエントリ用代表元タグ３００４と検索要求２００１における検索要求用クエリ２００２とが一致するかを検査する。エントリ用代表元タグ３００４と検索要求２００１における検索要求用クエリ２００２とが一致しなかった場合（不一致）、検索処理部３０３は、他の未検査のエントリ３００３を検査するため、Ｓ５０２に戻る。
次に、ステップＳ５０４において、検索処理部３０３は、エントリ用代表元タグ３００４と検索要求用クエリ２００２とが一致した場合（一致）、エントリ用代表元タグ３００４が対応するエントリ用暗号化情報３００７を読み取る。そして、検索処理部３０３は、読み取ったエントリ用暗号化情報３００７を検索要求回答部３０７に出力する。
なお、エントリ用暗号化情報３００７に記憶されている情報が、保管暗号化情報４００２の識別子である場合、検索処理部３０３は、識別子が示す保管暗号化情報４００２をデータ保管部３０５から取り出す。そして、検索処理部３０３は、その保管暗号化情報４００２を検索要求回答部３０７に出力する。（以下、エントリ用暗号化情報３００７に記憶されている情報が、保管暗号化情報４００２の識別子である場合の検索処理部３０３からの出力処理は同様である。そのため、以下、エントリ用暗号化情報３００７に記憶されている情報が、保管暗号化情報４００２の識別子である場合の説明を省略する）。
【００５４】
次に図１６を参照し、本実施の形態におけるインデックス登録Ｓ４０６を詳しく説明する。
図１６は、インデックス更新管理部３０６におけるインデックス登録Ｓ４０６の動作を示すフローチャートである。
保管データ全探索Ｓ４０５において、データ保管部３０５から、検索要求２００１に合致する検索結果（すなわち検索要求２００１に合致する保管データ４００１）が得られた場合に、検索処理部３０３は、保管データ４００１に含まれる保管暗号化情報４００２もしくは保管暗号化情報４００２の識別子をエントリ用暗号化情報３００７として、インデックス更新管理部３０６に転送する。また、検索処理部３０３は、登録データ２３０１に合致した検索要求２００１もインデックス更新管理部３０６に転送する。
そして、ステップＳ６０１において、インデックス更新管理部３０６は検索処理部３０３から転送されたエントリ用暗号化情報３００７と検索要求２００１をインデックス分類部３０９に入力する。そして、インデックス分類部３０９は、検索要求２００１に含まれる検索要求用クエリ２００２のクエリ暗号化検索要求用キーワード２００３の数に応じて、インデックス３００１のキーワード数別インデックス３００２のどこにエントリ用暗号化情報３００７を登録するか決定する。
次に、ステップＳ６０２において、インデックス更新管理部３０６は、検索結果に対応した新規のエントリ３００３を作成する。
次に、ステップＳ６０３において、インデックス更新管理部３０６は、作成したエントリのエントリ用代表元タグ３００４には検索要求２００１の検索要求用代表元タグ２００４を設定する。
次に、ステップＳ６０４において、インデックス更新管理部３０６は、作成したエントリのエントリ用検索クエリ３００６に検索要求２００１の検索要求用クエリ２００２を設定する。
次に、ステップＳ６０５において、インデックス更新管理部３０６は、作成したエントリのエントリ用暗号化情報３００７を設定する。
なお、Ｓ６０３からＳ６０５までの処理は順不同である。
【００５５】
次に図１７を参照して、秘匿検索システム１００のデータ新規登録処理の説明を行う。
図１７は、ユーザが新規にデータをデータセンター３０１に登録する際の動作を示したフローチャートである。
まず、ステップＳ７０１において、登録データ受信部３０８が、ユーザ端末２０１から登録データ２３０１を受信すると、登録データ受信部３０８は、データ保管部３０５とインデックス更新管理部３０６とに登録データ２３０１を転送する。
次に、ステップＳ７０２において、インデックス更新管理部３０６は、登録データ２３０１の登録キーワードタグ２３０３と全てのキーワード数別インデックスに保存されたエントリ３００３のエントリ用検索クエリ３００６との一致判定を行う。（ここで、インデックス分類部３０９は、全てのキーワード数別インデックスとの照合を指定する）。
次に、ステップＳ７０３において、インデックス更新管理部３０６は、登録データ２３０１における登録キーワードタグ２３０３に一致するエントリ用検索クエリ３００６を保存したエントリがある場合（一致）、該当する全てのエントリに登録暗号化情報２３０２をエントリ用暗号化情報３００７として追加する。登録キーワードタグ２３０３とエントリ用検索クエリ３００６とが一致しない場合（不一致）、インデックス更新管理部３０６は、インデックス３００１の更新を行わない。
次に、ステップＳ７０４において、登録キーワードタグ２３０３とエントリ用検索クエリ３００６とが一致／不一致に関わらず、データ保管部３０５は、登録データ受信部３０８から転送された登録データ２３０１を保管データ４００１として保存する。保管データ４００１は、保管キーワードタグ４００３として保存された登録キーワードタグ２３０３と、保管暗号化情報４００２として保存された登録暗号化情報２３０２とで構成される。
すなわち、登録キーワードタグ２３０３とエントリ用検索クエリ３００６とが一致する場合は、登録暗号化情報２３０２は、インデックス記憶部３０４のエントリ３００３とデータ保管部３０５との両方に保存される。
あるいは、図１７のフローチャートには図示しないが、例えば、ユーザが登録暗号化情報２３０２をインデックス記憶部３０４とデータ保管部３０５との両方に保存する必要が無いと判断する場合が想定される。その場合には、インデックス更新管理部３０６は、ステップＳ７０４において登録データ受信部３０８が保存した保管暗号化情報４００２の識別子をデータ保管部３０５から取得する。そして、インデックス更新管理部３０６は、登録暗号化情報２３０２の代わりに保管暗号化情報４００２の識別子をエントリ用暗号化情報３００７としてエントリ３００３に保存することも出来る。
ユーザは例えば登録暗号化情報２３０２の容量が大きい場合は、保管暗号化情報４００２の識別子をエントリ用暗号化情報３００７として保存することが可能である。またユーザは例えば登録暗号化情報２３０２の容量が小さい場合は登録暗号化情報２３０２を保存するなどの選択が可能である。そして、ユーザは登録暗号化情報２３０２に応じて、保管暗号化情報４００２の識別子と登録暗号化情報２３０２を混在してエントリ用暗号化情報３００７として保存することが可能である。
【００５６】
ここで、秘匿検索システム１００のデータ新規登録処理及びデータ検索処理の具体例を示す。
図１８は、登録データ２３０１と保管データ４００１との具体例を示す図である。（（ａ）は登録データ２３０１ａ、（ｂ）は登録データ２３０１ｂ、（ｃ）は登録データ２３０１ｃ、（ｄ）は保管データ４００１ａ、（ｅ）は保管データ４００１ｂ、（ｆ）は保管データ４００１ｃ）。ここで、登録データと保管データとに含まれる無意味な平文２３０５は図示を省略している。
図１９は、検索要求２００１の具体例を示す図である。（（ａ）は検索要求２００１ａ、（ｂ）は検索要求２００１ｂ、（ｃ）は検索要求２００１ｃ）。
図２０は、ステップＳ４０５の保管データ全探索の動作を示す図である。
図２１は、検索要求２００１ａに基づくインデックス登録の例を示す図である。
図２２は、検索要求２００１ａ〜ｃに基づくインデックス登録の例を示す図である。
図２３は、検索要求２００１ａ〜ｃに基づくエントリ登録の例を示す図である。（（ａ）はエントリ３００３ａ、（ｂ）はエントリ３００３ｂ、（ｃ）はエントリ３００３ｃ）。
図２４は、登録データ２３０１ｄを示す図である。
図２５は、登録データ２３０１ｄに含まれる登録暗号化情報がエントリに追加された例を示す図である。
図２６は、検索要求２００１の更なる具体例を示す図である。（（ａ）は検索要求２００１ｄ、（ｂ）は検索要求２００１ｅ）。
【００５７】
まず、登録データの新規登録処理を説明する。
ここで、初期状態としては、秘匿検索システム１００に保管データ４００１が何も無い状態を想定する。
そして、登録データ受信部３０８は、図１８に示す登録データ２３０１ａ〜ｃを受信したとする。そして、図１７に示すステップＳ７０２においてエントリ用検索クエリ３００６が何も無い状態なので、登録データ２３０１ａ〜ｃは、保管データ４００１ａ〜ｃとしてデータ保管部３０５に保存される。
【００５８】
そして、次に検索要求による検索処理を説明する。
検索要求受信部３０２は、図１９（ａ）に示す検索要求２００１ａを受信したとする。図１４のステップＳ４０３において、インデックス３００１に何もデータが無い状態なので、検索処理部３０３は、図１４のステップＳ４０５の保管データ全探索を行う。
図２０に示すように、クエリ暗号化検索要求用キーワード２００３ａ「エンジン」とクエリ暗号化検索要求用キーワード２００３ｂ「タイヤ」との両方に一致する保管キーワードタグ４００３は、第１の保管データ４００１ａと第２の保管データ４００１ｂとに存在する。
そこで、図１６に示すステップＳ４０６内のステップＳ６０１において、インデックス分類部３０９は、検索要求２００１ａのクエリ暗号化検索要求用キーワード２００３がクエリ暗号化検索要求用キーワード２００３ａ「エンジン」とクエリ暗号化検索要求用キーワード２００３ｂ「タイヤ」の２つで有ることを認識する。
従って、図２１に示すようにインデックス更新管理部３０６は、キーワード数別インデックス３００２の内、２キーワードインデックスの箇所（例えば３００２−２）に検索要求２００１ａに基づくエントリ３００３ｂを登録する。すなわち、インデックス更新管理部３０６は、検索要求２００１ａの検索要求用代表元タグ２００４をエントリ用代表元タグ３００４としてエントリ３００３ｂに保存する。さらに、インデックス更新管理部３０６は、検索要求２００１ａの検索要求用クエリ２００２をエントリ用検索クエリ３００６としてエントリ３００３ｂに保存する。また、インデックス更新管理部３０６は、保管データ４００１ａの保管暗号化情報４００２ａもしくは保管暗号化情報４００２ａの識別子と、保管データ４００１ｂの保管暗号化情報４００２ａもしくは保管暗号化情報４００２ａの識別子とをエントリ用暗号化情報３００７ｂとして保存する。
【００５９】
さらに検索要求受信部３０２は図１９（ｂ）に示す検索要求２００１ｂと図１９（ｃ）に示す検索要求２００１ｃとを受信したとする。その場合、インデックス更新管理部３０６は、同様の手順で図２２に示すインデックス３００１を形成する。そして、各エントリは、図２３に示すエントリ３００３ａ〜３００３ｃの通りとなる。
【００６０】
さらに追加登録データの登録処理について説明する。
図２４に示す登録データ２３０１ｄを検索要求受信部３０２が受信したとする。そして、インデックス更新管理部３０６は、エントリ３００３ａ〜３００３ｃのエントリ用検索クエリ３００６ａ〜３００６ｃと登録データ２３０１ｄの登録キーワードタグ２３０３ｄが一致するかを検査する。そして、インデックス更新管理部３０６は、エントリ３００３ａのエントリ用検索クエリ３００６ａとエントリ３００３ｂのエントリ用検索クエリ３００６ｂとが登録データ２３０１ｄの登録キーワードタグ２３０３と一致すると判断する。インデックス更新管理部３０６は、登録データ２３０１ｄの登録暗号化情報２３０２ｄ「自動車情報４」をエントリ３００３ａのエントリ用暗号化情報３００７ａとエントリ３００３ｂのエントリ用暗号化情報３００７ｂに追加する。（図２５参照）。
【００６１】
さらに追加検索要求による検索処理について説明する。
検索要求受信部３０２は、図２６（ａ）に示す検索要求２００１ｄを受信したとする。検索要求２００１ｄのクエリ暗号化検索要求用キーワード２００３の数は、２つである。その為に、図１４のステップＳ４０３において、インデックス分類部３０９は、インデックス３００１における２キーワード用インデックス（例えば３００２ｂ）の参照を決定する。そして、検索処理部３０３は、図２５に示すエントリ３００３ｂのエントリ用代表元タグ３００４ｂと検索要求２００１ｄの検索要求用クエリ２００２ｄとが一致すると判断する。そして、検索処理部３０３は、検索結果として、図２５に示すエントリ用暗号化情報３００７ｄに記憶されている「自動車情報１」「自動車情報２」「自動車情報４」を検索要求回答部３０７に出力する。
【００６２】
そして、検索要求受信部３０２は、図２６（ｂ）に示す検索要求２００１ｅを受信したとする。
検索要求２００１ｅのクエリ暗号化検索要求用キーワード２００３の数は、１つである。その為に、図１４のステップＳ４０３において、インデックス分類部３０９は、インデックス３００１における１キーワード用インデックス（例えば３００２ａ）の参照を決定する。そして、検索処理部３０３は、検索要求２００１ｅの検索要求用クエリ２００２ｅに一致するエントリが無いと判断する（図２５参照）。その為、検索処理部３０３は、図１４に示すステップＳ４０５の処理に移り、データ保管部３０５の検索を実施する。そして、検索処理部３０３は、データ保管部３０５に図１８に示す保管データ４００１ｃを見つけることが出来る。
ここで、仮にキーワード数別インデックス３００２が存在しない場合を想定する。その場合、図２５に示すエントリは混在することになる。そして、検索要求受信部３０２は、図２６（ｂ）に示す検索要求２００１ｅを受信したとする。そして、図２５に示すエントリ３００３ｂのエントリ用代表元タグ３００４ｂの暗号化登録キーワード２３０４は「タイヤ」が含まれている。すると、検索処理部３０３は、検索要求２００１ｅの検索要求用クエリ２００２ｅとエントリ３００３ｂのエントリ用代表元タグ３００４ｂとが一致すると判断する。そして、検索処理部３０３は、データ保管部３０５の保管データ４００１ｃを検出出来ない。
【００６３】
本実施の形態の秘匿検索システムは、ユーザが複数のキーワードを利用した検索を行うことが可能であり、ユーザの検索要求をより柔軟に表現できる。また、本実施の形態の秘匿検索システムは、複数のキーワード対応の検索履歴を用いた秘匿検索を誤一致や検索漏れなく実施することが出来、効率的な検索を実施出来る。
更に、本実施の形態の秘匿検索システムは、過去に検索した１つ以上のキーワードに対する検索結果をインデックスから必ず一意に特定できるため、誤った検索結果を出力することを防止する。
また、ユーザがデータを登録する際に、そのデータをインデックスに反映させることにより、秘匿検索システムがインデックスを利用して検索を高速化する際に、本実施の形態の秘匿検索システムは、検索漏れが発生しない。
また、１つのキーワードにつき１つのタグおよび検索クエリを生成する方式と比較し、本実施の形態の秘匿検索システムは、キーワードの増加による、タグおよび検索クエリの数の増加を低減し、かつ、キーワードの一致判定の回数を低減する。
【００６４】
実施の形態２．
実施の形態１では、インデックス分類部３０９は、検索結果を保存するインデックスを暗号化検索要求用キーワード数ごとに分類していた。また、インデックスのエントリの検索要求用代表元タグ２００４はユーザが指定していた。（ユーザは、検索要求２００１を送信する際に検索要求用クエリ２００２以外に検索要求用代表元タグ２００４を送信していた）。
実施の形態２では、複数のキーワードを用いた検索要求において、ユーザが検索対象の登録キーワードの特定が可能な場合に、インデックスの暗号化検索要求用キーワード数ごとの分類や、ユーザによる検索要求用代表元タグの設定を不要とする秘匿検索システム１００を示す。
【００６５】
まず、図２７を用いてフィールド番号を含んだ登録データ２３０１の構造を説明する。
図２７は、フィールド番号を含んだ登録データ２３０１の構成の例を示す図である。
登録データ２３０１は、登録暗号化情報２３０２と登録キーワードタグ２３０３と無意味な平文２３０５と登録フィールド番号２４０４とから構成される。
登録暗号化情報２３０２と登録キーワードタグ２３０３は実施の形態１と同様であり、説明を省略する。
登録フィールド番号２４０４は平文であり、暗号化登録キーワード２３０４に対応している。すなわち、登録フィールド番号２４０４は登録キーワードタグ２３０３の属性を示すものである。図２７に示す例では、暗号化登録キーワード「エンジン」は登録フィールド番号「１」、暗号化登録キーワード「タイヤ」は登録フィールド番号「２」、暗号化登録キーワード「ハンドル」は登録フィールド番号「３」と例えばユーザが定義している。
【００６６】
次に図２８を用いてフィールド番号を含んだ検索要求２００１の構造を説明する。
図２８は、フィールド番号を含んだ検索要求２００１の構成の例を示す図である。
検索要求２００１は、検索要求用クエリ２００２と検索要求用フィールド番号２１０４から構成される。
検索要求用クエリ２００２は実施の形態１と同様であり、説明を省略する。
検索要求用フィールド番号２１０４は、平文であり、検索要求用クエリ２００２のクエリ暗号化検索要求用キーワード２００３に対応している。すなわち、検索要求用フィールド番号２１０４は、検索要求用クエリ２００２の属性を示すものである。また、検索要求用フィールド番号２１０４は、クエリ暗号化検索要求用キーワード２００３がどの登録フィールド番号２４０４の暗号化登録キーワード２３０４を照合するかを示している。
すなわち、登録データとして図２７の例が存在する場合では、図２８に示すクエリ暗号化検索要求用キーワード「エンジン」は検索要求用フィールド番号が「１」であり、図２７の登録フィールド番号「１」の暗号化登録キーワード「エンジン」を照合する。
【００６７】
そして、図２９を用いてフィールド番号を含んだインデックス記憶部３０４におけるインデックス３００１の構造を説明する。
図２９は、フィールド番号を含んだインデックス記憶部３０４に記憶される検索結果のデータ構造の一例を示す図である。
インデックス３００１は、複数のエントリ３００３で構成される。
そして、エントリ３００３は、エントリ用代表元タグ３００４、エントリ用検索クエリ３００６、エントリ用暗号化情報３００７、無意味な平文２３０５、エントリ用フィールド番号３１０５から構成される。
エントリ用代表元タグ３００４は、１つ以上の暗号化代表元用キーワードで構成される。実施の形態２においては、エントリ用代表元タグ３００４は、登録データ２３０１に含まれる登録キーワードタグ２３０３が保存されたものである。その為、暗号化代表元用キーワードは、暗号化登録キーワード２３０４となる。また、暗号化代表元用キーワードは、無意味な平文２３０５が代表元用キーワードと公開鍵とで暗号化されたものである。その為、代表元用キーワードは登録キーワード２３００となる。
エントリ用検索クエリ３００６、エントリ用暗号化情報３００７、無意味な平文２３０５は、実施の形態１と同様である為説明を省略する。
エントリ用フィールド番号３１０５は、平文であり、エントリ用検索クエリ３００６とエントリ用代表元タグ３００４とに対応している。すなわち、エントリ用フィールド番号３１０５は、エントリ用検索クエリ３００６とエントリ用代表元タグ３００４との属性を示すものである。
【００６８】
次いで、実施の形態２におけるフィールド番号を含んだ秘匿検索システム１００のデータ検索処理の説明を行う。
実施の形態２におけるデータ検索処理の手順は、実施の形態１で説明した図１４と同様である。
ここで、実施の形態１では、インデックス分類部３０９は、クエリ暗号化検索要求用キーワード２００３の数に応じて、照合するキーワード数別インデックス３００２を決定している。しかし、実施の形態２では、インデックス分類部３０９は、検索要求２００１の検索要求用フィールド番号２１０４とエントリ３００３のエントリ用フィールド番号３１０５とを照合する役割を担う。
そこで、図１４において実施の形態１との相違点があるインデックス検査Ｓ４０３とインデックス登録Ｓ４０６の説明を行う。
【００６９】
まず、図３０を用いて実施の形態２におけるインデックス検査Ｓ４０３の説明を行う。
図３０は、インデックス検査Ｓ４０３の手順を示したフローチャートである。
実施の形態１と同様に、ユーザから検索要求２００１を受信したデータセンター３０１は、インデックス記憶部３０４から、検索要求２００１に一致するエントリ３００３を検索する。
まず、ステップＳ５１１において、検索処理部３０３は、インデックス３００１に未検査のエントリ３００３があるかを検査する。未検査のエントリが無い場合、検索要求に該当するデータが存在しないため検索処理部３０３は、「該当なし」と判断し、保管データ全探索Ｓ４０５に進むため、インデックス検査を終了する。
次に、ステップＳ５１２において、検索処理部３０３は、Ｓ５１１で未検査のエントリがある場合、検索要求用クエリ２００２とエントリ用代表元タグ３００４との一致検査を行う。
さらにインデックス分類部３０９は、検索要求用フィールド番号２１０４とエントリ用フィールド番号３１０５との一致検査を行う。
次に、ステップＳ５１３において、検索処理部３０３は、Ｓ５１３の一致検査の結果、一致する場合（一致）に該当エントリのエントリ用暗号化情報３００７を検索要求回答部３０７に出力する。一致しない場合（不一致）は、他の未検査のエントリについて同様の検査を行う。
【００７０】
次に図３１を用いて実施の形態２におけるインデックス登録Ｓ４０６の説明を行う。
図３１は、インデックス登録Ｓ４０６の手順を示したフローチャートである。
検索処理時、検索処理部３０３は、実施の形態１と同様にインデックス参照を実施した結果、検索要求に該当するエントリが見つからなかった場合、データ保管部３０５を検索する。
その結果、検索要求に該当する保管データ４００１が存在する場合に、インデックス登録処理Ｓ４０６を行う。
まず、ステップＳ６１１において、インデックス更新管理部３０６は、インデックス記憶部３０４に保存するための新規エントリを作成する。
次に、ステップＳ６１２において、インデックス更新管理部３０６は、作成した新規エントリのエントリ用代表元タグ３００４検索結果の保管キーワードタグ４００３から選択し、設定する。
次に、ステップＳ６１３において、インデックス更新管理部３０６は、作成した新規エントリのエントリ用フィールド番号３１０５として、保管データ４００１に含まれる登録フィールド番号２４０４を設定する。（実施の形態２における保管データ４００１の例は、図示を省略しているが、実施の形態１と同じく、保管データ４００１と登録データ２３０１は実質的に同一であり、登録フィールド番号２４０４が保管データ４００１に含まれている）。
次に、ステップＳ６１４において、インデックス更新管理部３０６は、作成した新規エントリのエントリ用検索クエリ３００６として検索要求用クエリ２００２を保存する。この時に、インデックス更新管理部３０６は、エントリ用フィールド番号３１０５をエントリ用検索クエリ３００６のクエリ暗号化検索要求用キーワード２００３にも関連付けする。
次に、ステップＳ６１５において、インデックス更新管理部３０６は、作成した新規エントリのエントリ用暗号化情報３００７に、検索結果の保管暗号化情報４００２もしくは保管暗号化情報４００２の識別子を保存する。
なお、Ｓ６１２からＳ６１５は順不同である。
【００７１】
ユーザが新規にデータを登録する場合は、実施の形態１と同様に図１７の手順で行う。保管データ４００１は、実施の形態１と同様に登録データ２３０１と同じ構造のものである。従って、実施の形態２における保管データ４００１は、図２７に示すように、登録フィールド番号２４０４も含んでいる。
実施の形態２で説明しなかった部分については、実施の形態１と同様であるので省略する。
【００７２】
ここで、図３２を用いて、インデックス検査Ｓ４０３における一致検査の具体例を示す。
（前記の通り、インデックス登録Ｓ４０６における一致検査（保管データ４００１と検索要求２００１との一致検査）は、実施の形態１と同様の処理なので、説明を省略する）。
図３２は、インデックス検査Ｓ４０３における一致検査の具体例を示す図である。（（ａ）はエントリ３００３の具体例、（ｂ）は、検索要求２００１ａ、（ｃ）は、検索要求２００１ｂ、（ｄ）は、検索要求２００１ｃ）。
まず、エントリ３００３と検索要求２００１ａとを照合した場合、インデックス分類部３０９は、エントリ用フィールド番号３１０５と検索要求用フィールド番号２１０４ａとが一致する為、エントリ３００３と第１の検索要求２００１ａは一致と判断する。そして、検索処理部３０３は、エントリ用代表元タグ３００４と検索要求用クエリ２００２とが一致する為、最終的にエントリ３００３と検索要求２００１ａは一致と判断する。
次に、エントリ３００３と検索要求２００１ｂとを照合した場合、インデックス分類部３０９は、エントリ用フィールド番号３１０５と検索要求用フィールド番号２１０４ｂとが一致しない為、エントリ３００３と検索要求２００１ａは不一致と判断する。
そして、エントリ３００３と検索要求２００１ｃとを照合した場合、インデックス分類部３０９は、エントリ用フィールド番号３１０５と検索要求用フィールド番号２１０４ｃとが一致しない為、エントリ３００３と検索要求２００１ｃは不一致と判断する。
【００７３】
実施の形態２によれば、実施の形態１の効果を奏するのに加えて、インデックスのエントリ用代表元タグは、検索結果の登録キーワードタグ２３０３を設定可能となる。従って、ユーザは、エントリ用代表元タグ３００４用の検索要求用代表元タグ２００４としてデータセンターに送らずに済む。そのため、ユーザ端末２０１とデータセンター３０１間の通信データ量を低減できるという効果がある。
また、データセンター３０１は、インデックス内を暗号化検索要求用キーワード数毎に分類しなくても良く、実施の形態１と比較してインデックスの管理の手間を削減できるという効果がある。
【００７４】
実施の形態３．
実施の形態１、２では、複数のキーワードを利用した秘匿検索システムにおいて、データセンター３０１は、検索履歴から正確な検索結果を取得し、高速にユーザへ出力する。すなわち、実施の形態１、２は、インデックスの設定法に関する実施の形態である。実施の形態３は、複数のユーザが秘匿検索システムを利用する場合の、ユーザ毎のデータ保管とインデックス構築を行う実施形態を示す。
ここで複数のユーザとは、例えば企業における課、部などを指し、それぞれの範囲内でデータ登録およびデータ検索を行う。また、特定のユーザ間で共通のデータを検索する場合もあり、その場合を「グループ共有」と呼ぶ。
以下では、ユーザ１〜ユーザｎのｎユーザ（ｎ≧１）が秘匿検索システムを利用しているものとする。また、ここでは、あるユーザの集合をユーザグループと呼ぶ。以下では、インデックス記憶部３０４とデータ保管部３０５をユーザ毎に管理する高速化手法を説明する。
【００７５】
図３３を用いて実施の形態３におけるデータ保管部３０５の構造を説明する。
図３３は、データ保管部３０５の構造の一例を示す図である。
データ保管部３０５はデータ領域３０５１から構成される。（図中に３０５１−１〜３０５１−ｎで表記）。データ領域３０５１は複数のユーザ（ユーザ１〜ユーザｎ）用に割り当てられる。またグループ共有を行う場合は、データ保管部３０５はグループ用にデータ領域を割り当て、そこにデータを保管する。
データ登録時、データセンター３０１はデータ登録要求のあったユーザに対応するデータ領域に登録データを保管する。これを「ユーザデータ領域」と呼ぶ。グループ共有する場合は、データセンター３０１は「共通データ領域」としてデータ領域３０５１を割り当て、該当するデータを「共通データ領域」にデータを保存する。なお、共通データ領域は複数あってもよいので、ユーザは、グループ毎に共通データ領域を作成してもよい。
データ検索時、データセンター３０１は検索要求を送信したユーザのユーザデータ領域と、共通データ領域のみ参照する。このように、データセンター３０１は、データ保管部３０５の全探索時に、検索要求に関連のないユーザのデータを検索対象から除外することが可能となり、全探索にかかる時間を削減することができる。
【００７６】
次に図３４を用いて、実施の形態３におけるインデックス記憶部３０４に保存されるインデックスの構造を説明する。
図３４は、インデックス記憶部３０４に保存されるインデックス３００１の構造の一例を示す図である。
インデックス３００１は、複数のサブインデックス３２０２から構成される。（図中に３２０２−１〜３２０２−ｎで表記）。サブインデックス３２０２内の構成は、例えば、実施の形態１、２のインデックス３００１のようになる。つまり、インデックス３００１はインデックス３００１内に複数のインデックスを構築する構成である。
サブインデックスは、ユーザ毎に割り当てられ、ここでは「ユーザサブインデックス」と呼ぶ。また、グループ共有データのインデックス化のため、グループに対してサブインデックスを割り当てても良い。ここでは、グループに対するサブインデックスを「共通サブインデックス」と呼ぶ。
【００７７】
ここで、実施の形態３における検索処理の説明を行う。
実施の形態３における検索処理の手順は実施の形態１で説明した図１４と同様である。実施の形態１と同様に、ユーザから検索要求を受信したデータセンター３０１は、インデックス記憶部３０４から、検索要求に一致するエントリを検索する。
実施の形態１との相違点はインデックス検査Ｓ４０３の手順である。図３５、図３６を用いて、グループ共有の有無に応じた動作例を説明する。
図３５は、グループ共有を行わない場合のインデックス検査Ｓ４０３の手順を示したフローチャートである。
図３６は、グループ共有を行う場合のインデックス検査Ｓ４０３の手順を示したフローチャートである。
【００７８】
まず、グループ共有しない場合を説明する。
グループ共有を行わない場合は、検索要求を送信したユーザに関連するユーザサブインデックスを検索対象として、検索処理部３０３は、インデックス検索を行う（図３５参照）。
まず、ステップＳ８０１において、検索処理部３０３は、検索要求を送信したユーザのユーザサブインデックスを検索の対象として、検索要求に該当するエントリを検索する。
次に、ステップＳ８０２において、検索処理部３０３は、エントリの検索処理を行う。エントリの検索処理は実施の形態１の方法で有っても良いし、実施の形態２の方法で有っても良い。検索処理部３０３は、検索要求に該当するエントリが存在した場合（該当あり）、Ｓ８０３に進む。該当するエントリが存在しない場合（該当なし）、保管データ全探索Ｓ４０５に進むため、インデックス検査を終了する。
次に、ステップＳ８０３において、検索処理部３０３は、検索要求に該当するエントリに保存されているエントリ用暗号化情報３００７を出力する。
【００７９】
次に、グループ共有する場合を説明する。
グループ共有を行う場合は、共通サブインデックスと、検索要求を送信したユーザに関連するユーザサブインデックスを検索対象として、検索処理部３０３は、インデックス検索を行う（図３６参照）。
まず、ステップＳ９０１において、検索処理部３０３は、検索要求を送信したユーザに関連する共通サブインデックスを検索対象として、検索要求に該当するエントリを検索する。
次に、ステップＳ９０２において、検索処理部３０３は、検索要求を送信したユーザのユーザサブインデックスを検索の対象として、検索要求に該当するエントリを検索する。
なお、Ｓ９０１、Ｓ９０２の検索の順序は逆でも良い。
次に、ステップＳ９０３において、検索処理部３０３は、Ｓ９０１とＳ９０２のエントリ探索の結果、該当するエントリが存在しない場合（該当なし）、保管データ全探索Ｓ４０５に進むため、インデックス検査を終了する。
次に、ステップＳ９０４において、検索処理部３０３は、Ｓ９０１とＳ９０２のエントリ探索の結果、検索要求に該当するエントリが存在した場合（該当あり）、該当エントリに保存されているエントリ用暗号化情報３００７を出力する。
【００８０】
以上のようにインデックス検査Ｓ４０３を実施した結果、検索要求に該当するエントリが見つからなかった場合、検索処理部３０３は、データ保管部３０５を検索する。その結果、検索要求に該当する保管データ４００１が存在する場合に、検索処理部３０３は、インデックス登録処理Ｓ４０６を行う。
【００８１】
次に、インデックス登録処理Ｓ４０６の説明を行う。インデックス登録処理Ｓ４０６は、グループ共有の有無により動作が異なる。以下、それぞれの場合について説明する。
【００８２】
まず、グループ共有しない場合を説明する。
この場合、検索処理部３０３は、検索要求を送信したユーザのユーザサブインデックスに、検索結果を保存する。
【００８３】
次に、グループ共有する場合を説明する。
グループ共有データ領域から検索された検索結果を、検索処理部３０３は、共通サブインデックスに保存する。そして、ユーザ用データ領域から検索された検索結果を、検索処理部３０３は、そのユーザに対応したユーザサブインデックスに保存する。
【００８４】
さらに、実施の形態３におけるデータ登録処理の説明を行う。
【００８５】
まず、グループ共有しない場合を説明する。
この場合、データ保管部３０５は、登録データをユーザ用データ領域に保存する。
【００８６】
次に、グループ共有する場合を説明する。
この場合、ユーザ端末２０１は、登録データ２３０１と共に登録データ２３０１が、グループ共有データなのかユーザ専用データなのかをデータセンター３０１に通知する。
データセンター３０１は、登録データ２３０１がグループ共有データの場合は共通データ領域に保存し、登録データ２３０１がユーザ専用データの場合はユーザデータ領域に保存する。
【００８７】
実施の形態３で説明しなかった部分については、実施の形態１、２と同様であるので省略する。
【００８８】
実施の形態３によれば、実施の形態１、２の効果を奏するのに加えて、複数ユーザ対応の秘匿検索システムは、インデックスの検索範囲を限定出来る。その為、秘匿検索システムは、インデックス検索に要する時間を低減するという効果がある。
また、秘匿検索システムは、データ保管部３０５の全探索の際に、検索者に関連のあるデータのみを検索対象とするため、全探索に要する時間を低減する、という効果がある。
【００８９】
以上、実施の形態１から実施の形態３にわたり、複数キーワード対応の検索履歴を用いた秘匿検索システムを開示したが、これは、暗号化情報のキーワード検索に限らない。任意のデータに対応した検索のためのキーデータ（検索キー）であれば、本実施の形態１〜３は、応用可能なことは明らかである。すなわち、本実施の形態１〜３によれば、データを暗号化したままで複数の検索キーを用いた検索を高速に実施することができる。したがって、本実施の形態１〜３は、画像検索、動画検索、音声検索などへの応用が可能である。
【００９０】
既に、説明したように、本実施の形態１〜３に示す秘匿検索システム１００は、処理装置たるＣＰＵ、記憶装置たるメモリ、磁気ディスク等、入力装置たるキーボード、マウス、通信ボード等、出力装置たる表示装置、通信ボード等を備えるコンピュータである。
そして、上記したように「〜部」として示された機能をこれら処理装置、記憶装置、入力装置、出力装置を用いて実現するものである。
【符号の説明】
【００９１】
１００  秘匿検索システム、１０１  ネットワーク、２０１  ユーザ端末、２０２  情報・鍵格納領域、２０３  暗号化情報管理部、２０４  ユーザインターフェース、２０５  検索要求用クエリ生成部、２０６  タグ生成部、２０７  通信モジュール、３０１  データセンター、３０２  検索要求受信部、３０５  データ保管部、３０６  インデックス更新管理部、３０８  登録データ受信部、９０１  表示装置、９０２  キーボード、９０３  マウス、９０４  ＦＤＤ、９０５  コンパクトディスク装置、９０６  プリンタ装置、９０７  スキャナ装置、９１０  システムユニット、９１１  ＣＰＵ、９１２  バス、９１３  ＲＯＭ、９１４  ＲＡＭ、９１５  通信ボード、９２０  磁気ディスク装置、９２１  オペレーティングシステム、９２２  ウィンドウシステム、９２３  プログラム群、９２４  ファイル群、９３１  電話器、９３２  ファクシミリ機、９４１  ゲートウェイ、９４２  ローカルエリアネットワーク、２０００  検索要求用キーワード、２００１  検索要求、２００２  検索要求用クエリ、２００３  クエリ暗号化検索要求用キーワード、２００４  検索要求用代表元タグ、２００５  タグ暗号化検索要求用キーワード、２１０４  検索要求用フィールド番号、２３００  登録キーワード、２３０１  登録データ、２３０２  登録暗号化情報、２３０３  登録キーワードタグ、２３０４  暗号化登録キーワード、２３０５  無意味な平文、２４０４  登録フィールド番号、３００１  インデックス、３００２  キーワード数別インデックス、３００３  エントリ、３００４  エントリ用代表元タグ、３００６  エントリ用検索クエリ、３００７  エントリ用暗号化情報、３１０５  エントリ用フィールド番号、３０５１  データ領域、３２０２  サブインデックス、４００１  保管データ、４００２  保管暗号化情報、４００３  保管キーワードタグ。
【図１】
0005557683.tif 000002
【図２】
0005557683.tif 000003
【図３】
0005557683.tif 000004
【図４】
0005557683.tif 000005
【図５】
0005557683.tif 000006
【図６】
0005557683.tif 000007
【図７】
0005557683.tif 000008
【図８】
0005557683.tif 000009
【図９】
0005557683.tif 000010
【図１０】
0005557683.tif 000011
【図１１】
0005557683.tif 000012
【図１２】
0005557683.tif 000013
【図１３】
0005557683.tif 000014
【図１４】
0005557683.tif 000015
【図１５】
0005557683.tif 000016
【図１６】
0005557683.tif 000017
【図１７】
0005557683.tif 000018
【図１８】
0005557683.tif 000019
【図１９】
0005557683.tif 000020
【図２０】
0005557683.tif 000021
【図２１】
0005557683.tif 000022
【図２２】
0005557683.tif 000023
【図２３】
0005557683.tif 000024
【図２４】
0005557683.tif 000025
【図２５】
0005557683.tif 000026
【図２６】
0005557683.tif 000027
【図２７】
0005557683.tif 000028
【図２８】
0005557683.tif 000029
【図２９】
0005557683.tif 000030
【図３０】
0005557683.tif 000031
【図３１】
0005557683.tif 000032
【図３２】
0005557683.tif 000033
【図３３】
0005557683.tif 000034
【図３４】
0005557683.tif 000035
【図３５】
0005557683.tif 000036
【図３６】
0005557683.tif 000037