(57)【特許請求の範囲】
【請求項１】
検索対象のデータを分類した複数のデータグループと、暗号化された前記データグループの識別子を復号する複数の復号鍵とを対応付けて記憶するデータ記憶部と、
復号鍵を判定する値である鍵判定情報を記憶する鍵判定情報記憶部と、
データを検索する条件である検索条件と、検索対象とするデータグループの識別子を暗号化した暗号化情報とを入力する検索条件入力部と、
前記検索条件入力部が入力した前記暗号化情報を前記データ記憶部に記憶された前記複数の復号鍵それぞれを用いて復号し、復号した結果が前記鍵判定情報と同じになる復号鍵を前記複数の復号鍵の中から選択し、前記データ記憶部に記憶された前記複数のデータグループのうち前記選択した復号鍵に対応付けられたデータグループを検索先グループとして選択するデータグループ選択部と、
前記データグループ選択部によって選択された前記検索先グループに含まれるデータから前記検索条件入力部が入力した前記検索条件を満たすデータを検索結果のデータとして取得するデータ検索部と、
前記データ検索部によって取得された前記検索結果のデータを出力する検索結果出力部と
を備えることを特徴とするデータ検索装置。
【請求項２】
前記データ検索装置は、さらに、
新規データと前記データグループの識別子を暗号化した暗号化タグとを入力する新規データ入力部と、
前記新規データ入力部が入力した前記新規データを前記複数のデータグループのうち前記データグループ選択部によって選択される登録先グループに追加する新規データ登録部と、を備え、
前記データグループ選択部は、
前記新規データ入力部が入力した前記暗号化タグを前記複数の復号鍵それぞれを用いて復号し、復号した結果が前記鍵判定情報と同じになる復号鍵を前記複数の復号鍵の中から選択し、前記複数のデータグループのうち前記選択した復号鍵に対応付けられたデータグループを前記登録先グループとして選択する
ことを特徴とする請求項１記載のデータ検索装置。
【請求項３】
前記データ記憶部は、さらに、複数のデータと前記データグループの識別子を暗号化した複数の暗号化タグとを対応付けて含んだデータグループとして未分類グループを記憶し、
前記データ検索装置は、さらに、
新たな復号鍵を追加復号鍵として入力する追加復号鍵入力部と、
前記未分類グループに含まれる前記複数の暗号化タグを前記追加復号鍵入力部が入力した前記追加復号鍵を用いて復号し、復号した結果が前記鍵判定情報と同じになる暗号化タグを前記複数の暗号化タグの中から選択し、前記未分類グループに含まれる前記複数のデータから前記選択した暗号化タグに対応付けられたデータを抽出し、前記複数のデータグループに加える新たなデータグループとして前記抽出したデータを含んだ追加グループを生成し、生成した前記追加グループと前記追加復号鍵とを対応付けて前記データ記憶部に記憶するデータグループ登録部と、を備える
ことを特徴とする請求項１または請求項２記載のデータ検索装置。
【請求項４】
検索対象のデータを分類した複数のデータグループと、暗号化された前記データグループの識別子を復号する複数の復号鍵とを対応付けて記憶するデータ記憶部と、復号鍵を判定する値である鍵判定情報を記憶する鍵判定情報記憶部と、検索条件入力部と、データグループ選択部と、データ検索部と、検索結果出力部と、を備えるデータ検索装置を用いて実行するデータ検索方法であって、
前記検索条件入力部が、データを検索する条件である検索条件と、検索対象とするデータグループの識別子を暗号化した暗号化情報とを入力し、
前記データグループ選択部が、前記検索条件入力部が入力した前記暗号化情報を前記データ記憶部に記憶される前記複数の復号鍵それぞれを用いて復号し、復号した結果が前記鍵判定情報と同じになる復号鍵を前記複数の復号鍵の中から選択し、前記データ記憶部に記憶される前記複数のデータグループのうち前記選択した復号鍵に対応付けられたデータグループを検索先グループとして選択し、
前記データ検索部が、前記データグループ選択部によって選択された前記検索先グループに含まれる１つ以上のデータから前記検索条件入力部が入力した前記検索条件を満たすデータを検索結果のデータとして取得し、
前記検索結果出力部が、前記データ検索部によって取得された前記検索結果のデータを出力する
ことを特徴とするデータ検索方法。
【請求項５】
データ記憶部と鍵判定情報記憶部とを用いるデータ検索プログラムであって、
前記データ記憶部は、検索対象のデータを分類した複数のデータグループと、暗号化された前記データグループの識別子を復号する複数の復号鍵とを対応付けて記憶する記憶部であり、
前記鍵判定情報記憶部は、復号鍵を判定する値である鍵判定情報を記憶する記憶部であり、
データを検索する条件である検索条件と、検索対象とするデータグループの識別子を暗号化した暗号化情報とを入力する検索条件入力処理と、
前記検索条件入力処理で入力した前記暗号化情報を前記データ記憶部に記憶された前記複数の復号鍵それぞれを用いて復号し、復号した結果が前記鍵判定情報と同じになる復号鍵を前記複数の復号鍵の中から選択し、前記データ記憶部に記憶された前記複数のデータグループのうち前記選択した復号鍵に対応付けられたデータグループを検索先グループとして選択するデータグループ選択処理と、
前記データグループ選択処理によって選択された前記検索先グループに含まれるデータから前記検索条件入力処理で入力した前記検索条件を満たすデータを検索結果のデータとして取得するデータ検索処理と、
前記データ検索処理によって取得された前記検索結果のデータを出力する検索結果出力処理と
をコンピュータに実行させるためのデータ検索プログラム。
【請求項６】
データを生成するデータ生成部と、
前記データ生成部によって生成されたデータの分類を示す分類情報を入力する分類情報入力部と、
前記分類情報入力部が入力した前記分類情報に基づいて前記分類情報が示す前記分類のデータグループを選択するための暗号化タグを生成する暗号化タグ生成部と、
前記データ生成部が生成した前記データと前記暗号化タグ生成部が生成した前記暗号化タグとをデータ検索装置へ送信することによって、前記分類情報が示す前記分類のデータグループに前記データを検索対象のデータとして追加する処理を前記データ検索装置に実行させるデータ登録要求部と
を備えることを特徴とするデータ登録装置。
【請求項７】
前記データ登録装置は、さらに、
複数の暗号化鍵と複数の分類情報とを対応付けて記憶する暗号化鍵記憶部を備え、
前記暗号化タグ生成部は、
前記暗号化鍵記憶部に記憶される前記複数の暗号化鍵のうち前記分類情報入力部が入力した前記分類情報と同じ分類情報に対応付けられた暗号化鍵を選択し、選択した暗号化鍵を用いて前記暗号化タグを生成する
ことを特徴とする請求項６記載のデータ登録装置。
【請求項８】
前記暗号化タグ生成部は、前記分類情報に基づくＩＤを用いてＩＤベース暗号方式によって前記暗号化タグを生成する
ことを特徴とする請求項６記載のデータ登録装置。
【請求項９】
前記暗号化タグ生成部は、前記分類情報を含んだベクトルを用いて関数型暗号方式によって前記暗号化タグを生成する
ことを特徴とする請求項６記載のデータ登録装置。
【請求項１０】
データ生成部と、分類情報入力部と、暗号化タグ生成部と、データ登録要求部と、を備えるデータ登録装置を用いて実行するデータ登録方法であって、
前記データ生成部が、データを生成し、
前記分類情報入力部が、前記データ生成部によって生成されたデータの分類を示す分類情報を入力し、
前記暗号化タグ生成部が、前記分類情報入力部が入力した前記分類情報に基づいて前記分類情報が示す前記分類のデータグループを選択するための暗号化タグを生成し、
前記データ登録要求部が、前記データ生成部が生成した前記データと前記暗号化タグ生成部が生成した前記暗号化タグとをデータ検索装置へ送信することによって、前記分類情報が示す前記分類のデータグループに前記データを検索対象のデータとして追加する処理を前記データ検索装置に実行させる
ことを特徴とするデータ登録方法。
【請求項１１】
データを生成するデータ生成処理と、
前記データ生成処理によって生成されたデータの分類を示す分類情報を入力する分類情報入力処理と、
前記分類情報入力処理で入力した前記分類情報に基づいて前記分類情報が示す前記分類のデータグループを選択するための暗号化タグを生成する暗号化タグ生成処理と、
前記データ生成処理で成した前記データと前記暗号化タグ生成処理で生成した前記暗号
化タグとをデータ検索装置へ送信することによって、前記分類情報が示す前記分類のデータグループに前記データを検索対象のデータとして追加する処理を前記データ検索装置に実行させるデータ登録要求処理と
をコンピュータに実行させるためのデータ登録プログラム。
【請求項１２】
データを検索するための検索条件とデータの分類を示す分類情報とを入力する検索条件入力部と、
前記検索条件入力部が入力した前記分類情報に基づいて前記分類情報が示す前記分類のデータグループを選択するための暗号化タグを生成する暗号化タグ生成部と、
前記検索条件入力部が入力した前記検索条件の情報と前記暗号化タグ生成部によって生成された前記暗号化タグとをデータ検索装置へ送信し、前記分類情報が示す前記分類のデータグループに含まれるデータのうち前記検索条件を満たすデータを検索結果のデータとして前記データ検索装置から受信するデータ検索要求部と
を備えることを特徴とする情報処理装置。
【請求項１３】
前記情報処理装置は、さらに、
複数の暗号化鍵と複数の分類情報とを対応付けて記憶する暗号化鍵記憶部を備え、
前記暗号化タグ生成部は、
前記暗号化鍵記憶部に記憶される前記複数の暗号化鍵のうち前記検索条件入力部が入力した前記分類情報と同じ分類情報に対応付けられた暗号化鍵を選択し、選択した暗号化鍵を用いて前記暗号化タグを生成する
ことを特徴とする請求項１２記載の情報処理装置。
【請求項１４】
前記暗号化タグ生成部は、前記分類情報に基づくＩＤを用いてＩＤベース暗号方式によって前記暗号化タグを生成する
ことを特徴とする請求項１２記載の情報処理装置。
【請求項１５】
前記暗号化タグ生成部は、前記分類情報を含んだベクトルを用いて関数型暗号方式によって前記暗号化タグを生成する
ことを特徴とする請求項１２記載の情報処理装置。
【請求項１６】
検索条件入力部と、暗号化タグ生成部と、データ検索要求部と、を備える情報処理装置を用いて実行するデータ検索方法であって、
前記検索条件入力部が、データを検索するための検索条件とデータの分類を示す分類情報とを入力し、
前記暗号化タグ生成部が、前記検索条件入力部が入力した前記分類情報に基づいて前記分類情報が示す前記分類のデータグループを選択するための暗号化タグを生成し、
前記データ検索要求部が、前記検索条件入力部が入力した前記検索条件の情報と前記暗号化タグ生成部によって生成された前記暗号化タグとをデータ検索装置へ送信し、前記分類情報が示す前記分類のデータグループに含まれるデータのうち前記検索条件を満たすデータを検索結果のデータとして前記データ検索装置から受信する
ことを特徴とするデータ検索方法。
【請求項１７】
データを検索するための検索条件とデータの分類を示す分類情報とを入力する検索条件入力処理と、
前記検索条件入力処理で入力した前記分類情報に基づいて前記分類情報が示す前記分類のデータグループを選択するための暗号化タグを生成する暗号化タグ生成処理と、
前記検索条件入力処理で入力した前記検索条件の情報と前記暗号化タグ生成処理によって生成された前記暗号化タグとをデータ検索装置へ送信し、前記分類情報が示す前記分類のデータグループに含まれるデータのうち前記検索条件を満たすデータを検索結果のデー
タとして前記データ検索装置から受信するデータ検索要求処理と
をコンピュータに実行させるためのデータ検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ検索装置、データ検索方法、データ検索プログラム、データ登録装置、データ登録方法、データ登録プログラムおよび情報処理装置に関するものである。
【背景技術】
【０００２】
公開鍵暗号（ＰＫＣ：Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ）の分野において、暗号化したデータを復号しないでキーワード検索を行うための技術として、検索可能公開鍵暗号（ＰＥＫＳ：Ｐｕｂｌｉｃ−ｋｅｙ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ｋｅｙｗｏｒｄ  Ｓｅａｒｃｈ）が知られている（非特許文献１参照）。【０００３】
この検索可能公開鍵暗号は、例えば、次のようなアプリケーションを実現する。
送信者が機密情報を含んだデータファイルを外部データベース（以下、「サーバ」という）経由で受信者に送る、という状況を考える。すなわち、送信者がサーバにデータファイルをアップロードしておき、受信者がキーワード検索により必要なデータファイルをサーバからダウンロードする、という状況を考える。
ここで、送信者と受信者は、データファイルとキーワードとの両方をサーバに知られずに共有したい。
受信者は、公開鍵暗号の公開鍵・秘密鍵ペア（データファイル本体の暗号化・復号に使用）と、検索可能公開鍵暗号の公開鍵・秘密鍵ペア（キーワードの暗号化、検索クエリの作成に使用）とを予め用意する。そして、受信者は、それぞれの公開鍵を公開しておく。
送信者は、受信者の公開鍵暗号の公開鍵を用いてデータファイルを暗号化してデータファイルの暗号文を生成する。これに加えて、送信者は、検索可能公開鍵暗号の公開鍵を用いてキーワードを暗号化してキーワードの暗号文を生成する。以下、検索可能公開鍵暗号の公開鍵を用いて生成したキーワードの暗号文を「暗号化タグ」という。送信者は、データファイルの暗号文と暗号化タグとを合わせてサーバにアップロードする。
受信者は、検索可能公開鍵暗号の秘密鍵を用いてキーワードを暗号化してキーワードの暗号文を生成する。以下、検索可能公開鍵暗号の秘密鍵を用いて生成したキーワードの暗号文を「トラップドア」という。受信者は、このトラップドアを検索クエリとしてサーバに送信する。
サーバは、受け取ったトラップドアを用いてデータベース内の全てのデータファイルの暗号文それぞれの暗号化タグに対して秘匿検索を行う。そして、サーバは、秘匿検索でヒットしたデータファイルの暗号文を受信者に送信する。【０００４】
検索可能公開鍵暗号には、全件検索をしなければならないため検索処理の時間がデータファイルの数に比例した大きさになってしまう、という課題があった。
これを解決するためにいくつかの方法が提案されている。【０００５】
特許文献１は、キーワードと文書名とを対応付けて記憶したインデックス記憶部と暗号化した文書を記憶した暗号化データベースとを用意し、インデックス記憶部内のキーワードを検索し、検索にヒットしなかった場合に暗号化データベース内の文書を全文検索する方法を開示している。インデックス記憶部は検索結果に応じて更新される。
但し、この方法には、インデックス記憶部が適切に更新されるまでは全文検索が必要なため、検索処理を高速化することができない、という課題がある。また、この方法には、様々な検索要求が大量に発生した場合にインデックス記憶部の効果が薄まり、検索処理を高速化することができない、という課題もある。さらに、この方法には、既存の検索可能公開鍵暗号方式のシステムを大きく変更する必要がある、という課題もある。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−１３４９９０号公報
【特許文献２】国際公開第２０１１／０８６６６８号パンフレット
【非特許文献】
【０００７】
【非特許文献１】Ｄａｎ  Ｂｏｎｅｈ，  Ｇｉｏｖａｎｎｉ  Ｄｉ  Ｃｒｅｓｃｅｎｚｏ，  Ｒａｆａｉｌ  Ｏｓｔｒｏｖｓｋｙ  ａｎｄ  Ｇｉｕｓｅｐｐｅ  Ｐｅｒｓｉａｎｏ，  ｀｀Ｐｕｂｌｉｃ  Ｋｅｙ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ｋｅｙｗｏｒｄ  Ｓｅａｒｃｈ，’’  Ｅｕｒｏｃｒｙｐｔ  ２００４，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ３０２７，  ｐｐ．  ５０６−５２２，  ２００４．
【非特許文献２】Ｍｉｈｉｒ  Ｂｅｌｌａｒｅ，  Ａｌｅｘａｎｄｒａ  Ｂｏｌｄｙｒｅｖａ，  Ａｎａｎｄ  Ｄｅｓａｉ  ａｎｄ  Ｄａｖｉｄ  Ｐｏｉｎｔｃｈｅｖａｌ，  ｀｀Ｋｅｙ−Ｐｒｉｖａｃｙ  ｉｎ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｅｎｃｒｙｐｔｉｏｎ，’’  Ａｓｉａｃｒｙｐｔ  ２００１，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ２２４８，  ｐｐ．  ５６６−５８２，  ２００１．
【非特許文献３】Ａｌｆｒｅｄ  Ｊ．  Ｍｅｎｅｚｅｓ，  Ｐａｕｌ  Ｃ．  Ｖａｎ  Ｏｏｒｓｃｈｏｔ，  ａｎｄ  Ｓｃｏｔｔ  Ａ．  Ｖａｎｓｔｏｎｅ，  Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ，  Ｃｈａｐｔｅｒ  ８  ｀｀Ｐｕｂｌｉｃ−Ｋｅｙ  Ｅｎｃｒｙｐｔｉｏｎ，’’  ＣＲＣ  Ｐｒｅｓｓ，  ２００６．
【非特許文献４】Ｄａｎ  Ｂｏｎｅｈ  ａｎｄ  Ｍａｔｔｈｅｗ  Ｆｒａｎｋｌｉｎ，  ｀｀Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  Ｐａｉｒｉｎｇ，’’  Ｃｒｙｐｔｏ  ２００１，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ２１３９，  ｐｐ．  ２１３−２２９，  ２００１．
【非特許文献５】Ｘａｖｉｅｒ  Ｂｏｙｅｎ  ａｎｄ  Ｂｒｅｎｔ  Ｗａｔｅｒｓ，  ｀｀Ａｎｏｎｙｍｏｕｓ  Ｈｉｅｒａｒｃｈｉｃａｌ  Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  （Ｗｉｔｈｏｕｔ  Ｒａｎｄｏｍ  Ｏｒａｃｌｅｓ），’’  Ｃｒｙｐｔｏ  ２００６，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ４１１７，  ｐｐ．  ２９０−３０７，  ２００６．
【非特許文献６】Ｍｉｃｈｅｌ  Ａｂｄａｌｌａ，  Ｍｉｈｉｒ  Ｂｅｌｌａｒｅ，  Ｄａｒｉｏ  Ｃａｔａｌａｎｏ，  Ｅｉｋｅ  Ｋｉｌｔｚ，  Ｔａｄａｙｏｓｈｉ  Ｋｏｈｎｏ，  Ｔａｎｊａ  Ｌａｎｇｅ，  Ｊｏｈｎ  Ｍａｌｏｎｅ−Ｌｅｅ，  Ｇｒｅｇｏｒｙ  Ｎｅｖｅｎ，  Ｐａｓｃａｌ  Ｐａｉｌｌｉｅｒ，  ａｎｄ  Ｈａｉｘｉａ  Ｓｈｉ，  ｀｀Ｓｅａｒｃｈａｂｌｅ  Ｅｎｃｒｙｐｔｉｏｎ  Ｒｅｖｉｓｉｔｅｄ：  Ｃｏｎｓｉｓｔｅｎｃｙ  Ｐｒｏｐｅｒｔｉｅｓ，  Ｒｅｌａｔｉｏｎ  ｔｏ  Ａｎｏｎｙｍｏｕｓ  ＩＢＥ，  ａｎｄ  Ｅｘｔｅｎｓｉｏｎｓ，’’  Ｃｒｙｐｔｏ  ２００５，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ３６２１，  ｐｐ．  ２０５−２２２，  ２００５．
【非特許文献７】Ｊｏｎａｔｈａｎ  Ｋａｔｚ，  Ａｍｉｔ  Ｓａｈａｉ，  ａｎｄ  Ｂｒｅｎｔ  Ｗａｔｅｒｓ，  ｀｀Ｐｒｅｄｉｃａｔｅ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｕｐｐｏｒｔｉｎｇ  Ｄｉｓｊｕｎｃｔｉｏｎｓ，  Ｐｏｌｙｎｏｍｉａｌ  Ｅｑｕａｔｉｏｎｓ，  ａｎｄ  Ｉｎｎｅｒ  Ｐｒｏｄｕｃｔｓ，’’  Ｅｕｒｏｃｒｙｐｔ  ２００８，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ４９６５，  ｐｐ．  １４６−１６２，  ２００８．
【非特許文献８】Ｔａｔｓｕａｋｉ  Ｏｋａｍｏｔｏ  ａｎｄ  Ｋａｔｓｕｙｕｋｉ  Ｔａｋａｓｈｉｍａ，  ｀｀Ａｄａｐｔｉｖｅｌｙ  Ａｔｔｒｉｂｕｔｅ−Ｈｉｄｉｎｇ  （Ｈｉｅｒａｒｃｈｉｃａｌ）  Ｉｎｎｅｒ  Ｐｒｏｄｕｃｔ  Ｅｎｃｒｙｐｔｉｏｎ，’’  Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ，  Ｒｅｐｏｒｔ  ２０１１／５４３，  ２０１１．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は、例えば、検索可能公開鍵暗号を用いた検索処理を高速化できるようにすることを目的とする。
【課題を解決するための手段】
【０００９】
本発明のデータ検索装置は、
１つ以上のデータを含んだ複数のデータグループと暗号化された情報を復号する複数の復号鍵とを対応付けて記憶するデータ記憶部と、
復号鍵を判定するための鍵判定情報を記憶する鍵判定情報記憶部と、
データを検索するための検索条件と、所定の情報を暗号化した暗号化情報とを入力する検索条件入力部と、
前記検索条件入力部が入力した前記暗号化情報を前記データ記憶部に記憶される前記複数の復号鍵それぞれを用いて復号し、前記複数の復号鍵のうち前記暗号化情報を前記鍵判定情報と同じ情報に復号した復号鍵を選択し、前記データ記憶部に記憶される前記複数のデータグループのうち前記選択した復号鍵に対応付けられたデータグループを検索先グループとして選択するデータグループ選択部と、
前記データグループ選択部によって選択された前記検索先グループに含まれる１つ以上のデータから前記検索条件入力部が入力した前記検索条件を満たすデータを検索結果のデータとして取得するデータ検索部と、
前記データ検索部によって取得された前記検索結果のデータを出力する検索結果出力部とを備える。
【発明の効果】
【００１０】
本発明によれば、例えば、検索可能公開鍵暗号を用いた検索処理を高速化することができる。
【図面の簡単な説明】
【００１１】
【図１】実施の形態１におけるデータ検索システム９００の構成図。
【図２】実施の形態１におけるデータ検索端末１００の機能構成図。
【図３】実施の形態１におけるシステム公開鍵１４０とシステム秘密鍵１５０とを示す図。
【図４】実施の形態１における公開鍵対応表１６０を示す図。
【図５】実施の形態１における検索クエリ１７０を示す図。
【図６】実施の形態１におけるデータ登録端末２００の機能構成図。
【図７】実施の形態１におけるシステム暗号文２３０を示す図。
【図８】実施の形態１におけるデータ検索サーバ３００の機能構成図。
【図９】実施の形態１における秘密鍵対応表３５０を示す図。
【図１０】実施の形態１におけるデータ検索端末１００のセットアップ処理を示すフローチャート。
【図１１】実施の形態１におけるデータ登録端末２００のデータ登録処理を示すフローチャート。
【図１２】実施の形態１におけるデータ検索サーバ３００のデータ登録処理を示すフローチャート。
【図１３】実施の形態１におけるデータ検索端末１００のデータ検索要求処理を示すフローチャート。
【図１４】実施の形態１におけるデータ検索サーバ３００のデータ検索処理を示すフローチャート。
【図１５】実施の形態１におけるデータ検索端末１００のカテゴリ登録要求処理を示すフローチャート。
【図１６】実施の形態１におけるデータ検索サーバ３００のカテゴリ登録処理を示すフローチャート。
【図１７】実施の形態１におけるデータ検索システム９００のハードウェア資源の一例を示す図。
【図１８】実施の形態１における鍵判定値対応表１９２を示す図。
【図１９】実施の形態１における公開鍵対応表１６０の別例を示す図。
【図２０】実施の形態２におけるシステム公開鍵１４０とシステム秘密鍵１５０とを示す図。
【図２１】実施の形態２におけるデータ検索端末１００のセットアップ処理を示すフローチャート。
【図２２】実施の形態２におけるデータ登録端末２００のデータ登録要求処理を示すフローチャート。
【図２３】実施の形態２におけるデータ検索サーバ３００のデータ登録処理を示すフローチャート。
【図２４】実施の形態２におけるデータ検索端末１００のデータ検索要求処理を示すフローチャート。
【図２５】実施の形態２におけるデータ検索サーバ３００のデータ検索処理を示すフローチャート。
【図２６】実施の形態２におけるデータ検索端末１００のカテゴリ登録要求処理を示すフローチャート。
【図２７】実施の形態２におけるデータ検索サーバ３００のカテゴリ登録処理を示すフローチャート。
【図２８】実施の形態２における公開鍵対応表１６０を示す図。
【図２９】実施の形態３におけるシステム公開鍵１４０とシステム秘密鍵１５０とを示す図。
【発明を実施するための形態】
【００１２】
実施の形態１．
検索可能公開鍵暗号（ＰＥＫＳ）を用いて高速に検索を行うシステムについて説明する。
検索可能公開鍵暗号とは、暗号化したデータを復号しないでキーワード検索を行うための技術である（非特許文献１参照）。
【００１３】
図１は、実施の形態１におけるデータ検索システム９００の構成図である。
実施の形態１におけるデータ検索システム９００の構成について、図１に基づいて説明する。
【００１４】
データ検索システム９００は検索可能公開鍵暗号を用いて検索を行うシステムの一例である。検索可能公開鍵暗号を用いることにより、検索対象のデータおよび検索用のキーワードを秘匿してキーワード検索を行うことができる。
【００１５】
データ検索システム９００は、一つのデータ検索端末１００と、複数のデータ登録端末２００と、一つのデータ検索サーバ３００とを備える。但し、データ検索端末１００やデータ検索サーバ３００が複数あっても構わないし、データ登録端末２００が一つであっても構わない。
データ検索端末１００とデータ登録端末２００とデータ検索サーバ３００とはネットワーク９０９（例えば、インターネット）を介して通信接続している。
【００１６】
データ登録端末２００（データ登録装置の一例）は、検索対象のデータを暗号化してデータ検索サーバ３００に登録するための装置（コンピュータ）である。
データ検索端末１００（情報処理端末装置の一例）は、データ検索サーバ３００に対して暗号化した検索キーワードを指定してキーワード検索を要求するための装置である。
データ検索サーバ３００（データ検索装置の一例）は、データ登録端末２００によって登録された暗号化データを対象にしてデータ検索端末１００によって指定された暗号化キーワードに従って検索可能公開鍵暗号のキーワード検索を行うための装置である。データ検索サーバ３００は検索結果をデータ検索端末１００に応答する。
【００１７】
例えば、検索対象のデータとして電子メールが挙げられる。この場合、データ検索サーバ３００はメールサーバとして機能し、データ登録端末２００は電子メールの送信者が使用するコンピュータとして機能し、データ検索端末１００は電子メールの受信者が使用するコンピュータとして機能する。そして、データ検索システム９００は以下のように利用される。但し、以下の利用方法は、データ検索システム９００の利用方法の一例である。
電子メールの送信者Ａ、Ｂ、Ｃはそれぞれ、データ登録端末２００を用いて暗号化した電子メールをデータ検索サーバ３００へ送信する。データ検索サーバ３００は送信者Ａ、Ｂ、Ｃそれぞれの暗号化された電子メールを記憶する。
電子メールの受信者は、送信者Ａの電子メールを見たい場合、データ検索端末１００に対して電子メールの検索キーワードとして送信者Ａの識別子（例えば、電子メールアドレス）を指定する。データ検索端末１００は、検索キーワード（送信者Ａの識別子）を暗号化してデータ検索サーバ３００へ送信する。
データ検索サーバ３００は、暗号化された検索キーワードに従って検索可能公開鍵暗号のキーワード検索を行い、送信者Ａの暗号化された電子メールをデータ検索端末１００へ送信する。
データ検索端末１００は送信者Ａの暗号化された電子メールを受信し、受信した電子メールを復号し、復号した電子メールを表示する。
これにより、電子メールの送信者Ａ、Ｂ、Ｃおよび受信者は電子メールを秘匿することができる。さらに、電子メールの受信者は電子メールの検索キーワードを秘匿することができる。
【００１８】
図２は、実施の形態１におけるデータ検索端末１００の機能構成図である。
実施の形態１におけるデータ検索端末１００の機能構成について、図２に基づいて説明する。
【００１９】
データ検索端末１００（情報処理装置の一例）は、セットアップ処理部１１０と、検索要求処理部１２０と、カテゴリ登録要求部１３０と、検索端末記憶部１９０とを備える。
【００２０】
セットアップ処理部１１０は、システム鍵生成部１１１と、公開鍵対応表生成部１１２と、鍵情報公開部１１３とを備える。
システム鍵生成部１１１は、後述する鍵判定値１９１とシステム公開鍵１４０とシステム秘密鍵１５０とを生成する。
公開鍵対応表生成部１１２は、後述する公開鍵対応表１６０を生成する。
鍵情報公開部１１３は、システム公開鍵１４０とシステム秘密鍵１５０と公開鍵対応表１６０とをデータ登録端末２００またはデータ検索サーバ３００に対して公開する。
システム鍵生成部１１１、公開鍵対応表生成部１１２および鍵情報公開部１１３の詳細については、後述するセットアップ処理のフローチャートに基づいて説明する。
【００２１】
図３は、実施の形態１におけるシステム公開鍵１４０とシステム秘密鍵１５０とを示す図である。
実施の形態１におけるシステム公開鍵１４０とシステム秘密鍵１５０とについて、図３に基づいて説明する。
【００２２】
システム公開鍵１４０およびシステム秘密鍵１５０は、データ検索システム９００で使用する公開鍵暗号（または検索可能公開鍵暗号）の鍵ペアを構成する。
【００２３】
システム公開鍵１４０は、一つのデータ用公開鍵１４１と、一つのキーワード用公開鍵１４２と、複数のカテゴリ判定用公開鍵１４３（複数の暗号化鍵の一例）とを含む。
データ用公開鍵１４１は、検索対象のデータを暗号化するための鍵データ（暗号化鍵）である。
キーワード用公開鍵１４２は、検索対象のデータに添付するキーワード（データキーワード）またはデータの検索時に指定するキーワード（検索キーワード）を暗号化するための鍵データ（暗号化鍵）である。
カテゴリ判定用公開鍵１４３は、検索対象のデータが属するカテゴリ（データカテゴリ）を判定するための情報（鍵判定値１９１）を暗号化するための鍵データ（暗号化鍵）である。カテゴリ判定用公開鍵１４３はデータのカテゴリ毎に異なる。
【００２４】
システム秘密鍵１５０は、一つのデータ用秘密鍵１５１と、一つのキーワード用秘密鍵１５２と、複数のカテゴリ判定用秘密鍵１５３（複数の復号鍵の一例）とを含む。
データ用秘密鍵１５１は、暗号化された検索対象のデータを復号するための鍵データ（復号鍵）である。
キーワード用秘密鍵１５２は、検索キーワードに対応する秘密鍵（後述する検索用トラップドア１７１）を生成するための鍵データ（マスタ秘密鍵）である。
カテゴリ判定用秘密鍵１５３は、暗号化された鍵判定値１９１（後述する索引用タグ１７２または索引用タグ２３３）を復号するための鍵データ（復号鍵）である。カテゴリ判定用秘密鍵１５３はデータのカテゴリ毎に異なる。
【００２５】
データ用公開鍵１４１およびデータ用秘密鍵１５１はデータ用の鍵ペア（公開鍵暗号の鍵ペア）を構成する。
キーワード用公開鍵１４２およびキーワード用秘密鍵１５２はデータのキーワード用の鍵ペア（検索可能公開鍵暗号の鍵ペア）を構成する。キーワード用公開鍵１４２とキーワード用秘密鍵１５２とをデータ用の鍵ペアとして兼用しても構わない。この場合、データ用公開鍵１４１およびデータ用秘密鍵１５１は不要である。
カテゴリ判定用公開鍵１４３およびカテゴリ判定用秘密鍵１５３はデータのカテゴリ判定用の複数の鍵ペア（公開鍵暗号の鍵ペア）を構成する。
【００２６】
図４は、実施の形態１における公開鍵対応表１６０を示す図である。
実施の形態１における公開鍵対応表１６０について、図４に基づいて説明する。
【００２７】
公開鍵対応表１６０は、カテゴリ判定用公開鍵１４３とデータのカテゴリとを対応付けるデータである。
図４に示す公開鍵対応表１６０は、「ＰＫ１」で識別されるカテゴリ判定用公開鍵１４３と「特許」カテゴリとを対応付け、「ＰＫ２」で識別されるカテゴリ判定用公開鍵１４３と「意匠」カテゴリとを対応付けている。
【００２８】
図２に戻り、データ検索端末１００の機能構成の説明を続ける。
【００２９】
検索要求処理部１２０は、検索キーワード入力部１２１と、検索クエリ生成部１２２と、検索要求部１２３と、検索結果出力部１２４とを備える。
検索キーワード入力部１２１（検索条件入力部の一例）は、利用者（データの検索者）に指定された検索キーワード（検索条件の一例）と検索対象のカテゴリとを入力装置または記憶装置から入力する。
検索クエリ生成部１２２（暗号化タグ生成部の一例）は、検索キーワードと検索対象のカテゴリとに基づいて検索クエリ１７０を生成する。検索クエリ１７０は検索キーワードを指定するためのデータである。
検索要求部１２３（データ検索要求部の一例）は、検索クエリ１７０をデータ検索サーバ３００へ送信し、検索キーワードに該当する暗号化データを含んだ検索結果１９９をデータ検索サーバ３００から受信する。
検索結果出力部１２４は、検索結果１９９に含まれる暗号化データをデータ用秘密鍵１５１を用いて復号し、復号して得られたデータを出力する。
検索キーワード入力部１２１、検索クエリ生成部１２２、検索要求部１２３および検索結果出力部１２４の詳細については、後述するデータ検索要求処理のフローチャートに基づいて説明する。
【００３０】
図５は、実施の形態１における検索クエリ１７０を示す図である。
実施の形態１における検索クエリ１７０について、図５に基づいて説明する。
【００３１】
検索クエリ１７０は、検索用トラップドア１７１（検索条件の情報の一例）と索引用タグ１７２（暗号化タグの一例）とを含んだデータである。
検索用トラップドア１７１は検索キーワードに対応する秘密鍵である。検索用トラップドア１７１はキーワード用秘密鍵１５２を用いて生成される。
索引用タグ１７２は、検索対象のカテゴリ用のカテゴリ判定用公開鍵１４３を用いて暗号化した鍵判定値１９１である。
【００３２】
図２に戻り、データ検索端末１００の機能構成について説明を続ける。
【００３３】
カテゴリ登録要求部１３０は、特定のカテゴリに属するデータ用のデータベースの生成をデータ検索サーバ３００に対して要求する。
カテゴリ登録要求部１３０の詳細については、後述するカテゴリ登録要求処理のフローチャートに基づいて説明する。
【００３４】
検索端末記憶部１９０（暗号化鍵記憶部の一例）は、データ検索端末１００で使用するデータを記憶する。
例えば、検索端末記憶部１９０は、鍵判定値１９１、システム公開鍵１４０、システム秘密鍵１５０、公開鍵対応表１６０、検索クエリ１７０および検索結果１９９を記憶する。
【００３５】
図６は、実施の形態１におけるデータ登録端末２００の機能構成図である。
実施の形態１におけるデータ登録端末２００の機能構成について、図６に基づいて説明する。
【００３６】
データ登録端末２００（データ登録装置の一例）は、公開情報取得部２１０と、データ登録要求処理部２２０と、登録端末記憶部２９０とを備える。
【００３７】
公開情報取得部２１０は、データ検索端末１００によって公開された鍵判定値１９１とシステム公開鍵１４０と公開鍵対応表１６０とを取得する。
公開情報取得部２１０の詳細については、後述するセットアップ処理のフローチャートに基づいて説明する。
【００３８】
データ登録要求処理部２２０は、登録情報入力部２２１と、データ暗号文生成部２２２と、キーワード暗号文生成部２２３と、索引用タグ生成部２２４と、データ登録要求部２２５とを備える。
登録情報入力部２２１（分類情報入力部の一例）は、利用者（データの登録者）に指定されたデータとデータのキーワードとデータのカテゴリとを入力装置または記憶装置から入力する。
データ暗号文生成部２２２（データ生成部の一例）は、データ用公開鍵１４１を用いてデータを暗号化する。
キーワード暗号文生成部２２３は、キーワード用公開鍵１４２を用いてデータのキーワードを暗号化する。
索引用タグ生成部２２４（暗号化タグ生成部の一例）は、データのカテゴリ用のカテゴリ判定用公開鍵１４３を用いて鍵判定値１９１を暗号化する。
データ登録要求部２２５（データ登録要求部の一例）は、暗号化したデータとキーワードと鍵判定値１９１とを含んだシステム暗号文２３０の登録をデータ検索サーバ３００に対して要求する。
登録情報入力部２２１、データ暗号文生成部２２２、キーワード暗号文生成部２２３、索引用タグ生成部２２４およびデータ登録要求部２２５の詳細については、後述するデータ登録要求処理のフローチャートに基づいて説明する。
【００３９】
図７は、実施の形態１におけるシステム暗号文２３０を示す図である。
実施の形態１におけるシステム暗号文２３０について、図７に基づいて説明する。
【００４０】
システム暗号文２３０は、データ暗号文２３１と、キーワード暗号文２３２と、索引用タグ２３３とを含んだデータである。
データ暗号文２３１（データの一例）は、データ用公開鍵１４１を用いてデータを暗号化したものである。
キーワード暗号文２３２は、キーワード用公開鍵１４２を用いてデータのキーワードを暗号化したものである。
索引用タグ２３３（暗号化タグの一例）は、データが属するカテゴリのカテゴリ判定用公開鍵１４３を用いて鍵判定値１９１を暗号化したものである。
【００４１】
図６に戻り、データ登録端末２００の機能構成の説明を続ける。
【００４２】
登録端末記憶部２９０は、データ登録端末２００で使用するデータを記憶する。
例えば、登録端末記憶部２９０は、鍵判定値１９１、システム公開鍵１４０、公開鍵対応表１６０およびシステム暗号文２３０を記憶する。
【００４３】
図８は、実施の形態１におけるデータ検索サーバ３００の機能構成図である。
実施の形態１におけるデータ検索サーバ３００の機能構成について、図８に基づいて説明する。
【００４４】
データ検索サーバ３００（データ検索装置の一例）は、カテゴリ用秘密鍵管理部３１０と、データ登録処理部３２０と、データ検索処理部３３０と、カテゴリ判定部３４０と、検索サーバ記憶部３９０とを備える。
さらに、データ検索サーバ３００は、データのカテゴリ別にデータベース（以下、「カテゴリ別ＤＢ部３９１」という）を備える。
また、データ検索サーバ３００は、いずれのカテゴリにも分類されていないデータ用のデータベース（以下、「未分類ＤＢ部３９２」という）を備える。
【００４５】
カテゴリ用秘密鍵管理部３１０（追加復号鍵入力部、データグループ登録部の一例）は、データ検索端末１００によって生成される鍵判定値１９１とカテゴリ判定用秘密鍵１５３とを管理する。
また、カテゴリ用秘密鍵管理部３１０は、カテゴリ判定用秘密鍵１５３に対応付けるカテゴリ別ＤＢ部３９１を生成する。
さらに、カテゴリ用秘密鍵管理部３１０は、カテゴリ判定用秘密鍵１５３とカテゴリ別ＤＢ部３９１とを対応付ける秘密鍵対応表３５０を生成する。
カテゴリ用秘密鍵管理部３１０の詳細については、後述するセットアップ処理のフローチャートおよびカテゴリ登録処理のフローチャートに基づいて説明する。
【００４６】
データ登録処理部３２０は、登録要求受信部３２１と、データ登録部３２２とを備える。
登録要求受信部３２１（新規データ入力部の一例）は、データ登録端末２００から送信されるデータ（図７に示したシステム暗号文２３０）の登録要求を受信する。
データ登録部３２２（新規データ登録部の一例）は、データの登録要求に従ってデータが属するカテゴリ用のカテゴリ別ＤＢ部３９１にデータを記憶する。
登録要求受信部３２１およびデータ登録部３２２の詳細については、後述するデータ登録処理のフローチャートに基づいて説明する。
【００４７】
データ検索処理部３３０は、検索要求受信部３３１と、データ検索部３３２と、検索結果送信部３３３とを備える。
検索要求受信部３３１（検索条件入力部の一例）は、データ検索端末１００から送信されるデータの検索要求（図５に示した検索クエリ）を受信する。
データ検索部３３２（データ検索部の一例）は、データの検索要求に従って検索対象のカテゴリ用のカテゴリ別ＤＢ部３９１を検索する。
検索結果送信部３３３（検索結果出力部の一例）は、検索条件を満たすデータ（図７に示したシステム暗号文２３０）を含んだ検索結果をデータ検索端末１００へ送信する。
検索要求受信部３３１、データ検索部３３２および検索結果送信部３３３の詳細については、後述するデータ検索処理のフローチャートに基づいて説明する。
【００４８】
カテゴリ判定部３４０（データグループ選択部の一例）は、データの登録要求に基づいてデータが属するカテゴリ用のカテゴリ別ＤＢ部３９１を判定し、データの検索要求に基づいて検索対象のカテゴリ用のカテゴリ別ＤＢ部３９１を判定する。
カテゴリ判定部３４０の詳細については、後述するデータ登録処理のフローチャートおよびデータ検索処理のフローチャートに基づいて説明する。
【００４９】
検索サーバ記憶部３９０は、データ検索サーバ３００で使用するデータを記憶する。
例えば、検索サーバ記憶部３９０は、鍵判定値１９１、カテゴリ判定用秘密鍵１５３および秘密鍵対応表３５０を記憶する。
【００５０】
図９は、実施の形態１における秘密鍵対応表３５０を示す図である。
実施の形態１における秘密鍵対応表３５０について、図９に基づいて説明する。
【００５１】
秘密鍵対応表３５０は、カテゴリ判定用秘密鍵１５３とカテゴリ別ＤＢ部３９１とを対応付けるデータである。
図９に示す秘密鍵対応表３５０は、「ＳＫ１」で識別されるカテゴリ判定用秘密鍵１５３と、「ＤＢ１」で識別されるカテゴリ別ＤＢ部３９１とを対応付け、「ＳＫ２」で識別されるカテゴリ判定用秘密鍵１５３と、「ＤＢ２」で識別されるカテゴリ別ＤＢ部３９１とを対応付けている。
【００５２】
図８に戻り、データ検索サーバ３００の機能構成の説明を続ける。
【００５３】
カテゴリ別ＤＢ部３９１（データ記憶部の一例）は、同じカテゴリに分類された１つ以上のシステム暗号文２３０（データグループの一例）を記憶する。
【００５４】
未分類ＤＢ部３９２（データ記憶部の一例）は、いずれのカテゴリにも分類されていない１つ以上のシステム暗号文２３０（未分類グループの一例）を記憶する。
【００５５】
図１０は、実施の形態１におけるデータ検索端末１００のセットアップ処理を示すフローチャートである。
実施の形態１におけるデータ検索端末１００のセットアップ処理について、図１０に基づいて説明する。
【００５６】
データ検索を行いたい利用者（以下、「検索者」という）はデータ検索端末１００のセットアップ処理部１１０を起動し、データ検索端末１００のセットアップ処理部１１０は以下のセットアップ処理（Ｓ１１０からＳ１３１）を実行する。
【００５７】
Ｓ１１０において、システム鍵生成部１１１は、システム公開鍵１４０とシステム秘密鍵１５０とを生成する（図３参照）。鍵生成方法については非特許文献３を参照のこと。
このとき、システム鍵生成部１１１は、データ用公開鍵１４１とデータ用秘密鍵１５１との鍵ペアを公開鍵暗号方式の鍵生成アルゴリズムによって生成する。ＲＳＡ暗号（ＲＳＡは登録商標）は公開鍵暗号方式の一例である。
また、システム鍵生成部１１１は、キーワード用公開鍵１４２とキーワード用秘密鍵１５２との鍵ペアを検索可能公開鍵暗号方式の鍵生成アルゴリズムによって生成する。
また、システム鍵生成部１１１は、カテゴリ判定用公開鍵１４３とカテゴリ判定用秘密鍵１５３との複数の鍵ペアを公開鍵暗号方式の鍵生成アルゴリズムによって生成する。例えば、システム鍵生成部１１１は、ＥｌＧａｍａｌ暗号やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号など、鍵匿名性（ｋｅｙ−ｐｒｉｖａｃｙ）を有する公開鍵暗号方式を使用する。鍵匿名性とは、暗号文を見てもどの公開鍵を用いたかわからない、という性質である。カテゴリ判定用公開鍵１４３とカテゴリ判定用秘密鍵１５３との鍵ペアの個数はデータを分類するカテゴリの個数であり、検索者がデータ検索端末１００のシステム鍵生成部１１１に対して指定（入力）する。
Ｓ１１０の後、Ｓ１２０に進む。
【００５８】
Ｓ１２０において、検索者は、Ｓ１１０で生成されたカテゴリ判定用公開鍵１４３に対応付けるデータのカテゴリを示すカテゴリ情報を入力装置（例えば、キーボードやマウス）を用いてデータ検索端末１００の公開鍵対応表生成部１１２に対して入力する。つまり、公開鍵対応表生成部１１２は、検索者によって指定されたカテゴリ情報を入力装置から入力する。
公開鍵対応表生成部１１２は、入力したカテゴリ情報に従って図４に示すような公開鍵対応表１６０を生成する。公開鍵対応表１６０は、カテゴリ判定用公開鍵１４３とデータのカテゴリとを対応付けるデータである。
例えば、「ＰＫ１」で識別されるカテゴリ判定用公開鍵１４３に対応付けるデータのカテゴリが「特許」である場合、公開鍵対応表生成部１１２は「ＰＫ１」と「特許」とを対応付けて公開鍵対応表１６０に設定する。
Ｓ１２０の後、Ｓ１３０に進む。
【００５９】
Ｓ１３０において、鍵情報公開部１１３は、所定の鍵判定値１９１とＳ１１０で生成したシステム公開鍵１４０とＳ１２０で生成した公開鍵対応表１６０とをデータ登録端末２００に対する公開情報として公開する。鍵判定値１９１は所定値（例えば「１」）である。
例えば、データ検索端末１００の鍵情報公開部１１３が公開情報を所定のサーバ（例えば、データ検索サーバ３００）に登録し、データ登録端末２００の公開情報取得部２１０が所定のサーバから公開情報を取得する。公開情報取得部２１０は取得した公開情報を登録端末記憶部２９０に記憶する。
また例えば、データ登録端末２００の公開情報取得部２１０が公開情報を要求する公開要求をデータ検索端末１００へ送信し、データ検索端末１００の鍵情報公開部１１３が公開要求を受信する。そして、データ検索端末１００の鍵情報公開部１１３が公開情報をデータ登録端末２００へ送信し、データ登録端末２００の公開情報取得部２１０が公開情報を受信する。公開情報取得部２１０は受信した公開情報を登録端末記憶部２９０に記憶する。
Ｓ１３０の後、Ｓ１３１に進む。
【００６０】
Ｓ１３１において、鍵情報公開部１１３は、所定の鍵判定値１９１とＳ１１０で生成した複数のカテゴリ判定用秘密鍵１５３とをデータ検索サーバ３００へ送信する。鍵判定値１９１はデータ登録端末２００に対して公開する値と同じである。
但し、鍵情報公開部１１３は、複数のカテゴリ判定用秘密鍵１５３のうち少なくともいずれかのカテゴリ判定用秘密鍵１５３だけをデータ検索サーバ３００へ送信してもよい。つまり、データ検索サーバ３００に対して送信しないカテゴリ判定用秘密鍵１５３があっても構わない。例えば、検索者がカテゴリ判定用秘密鍵１５３を指定する。そして、鍵情報公開部１１３は、複数のカテゴリ判定用秘密鍵１５３のうち検索者によって指定されたカテゴリ判定用秘密鍵１５３をデータ検索サーバ３００へ送信する。
【００６１】
このとき、データ検索サーバ３００のカテゴリ用秘密鍵管理部３１０は、データ検索端末１００の鍵情報公開部１１３によって送信された鍵判定値１９１とカテゴリ判定用秘密鍵１５３とを受信する。カテゴリ用秘密鍵管理部３１０は、受信した鍵判定値１９１とカテゴリ判定用秘密鍵１５３とを検索サーバ記憶部３９０に記憶する。
そして、カテゴリ用秘密鍵管理部３１０は、受信したカテゴリ判定用秘密鍵１５３別にカテゴリ別ＤＢ部３９１を生成する。カテゴリ別ＤＢ部３９１は、カテゴリ判定用秘密鍵１５３と鍵ペアを構成するカテゴリ判定用公開鍵１４３を用いて生成された索引用タグ２３３を含んだシステム暗号文２３０（図７参照）を記憶するためのデータベースである。
また、カテゴリ用秘密鍵管理部３１０は、図９に示すような秘密鍵対応表３５０を生成する。例えば、「ＳＫ１」で識別されるカテゴリ判定用秘密鍵１５３に対して「ＤＢ１」で識別されるカテゴリ別ＤＢ部３９１を生成した場合、カテゴリ用秘密鍵管理部３１０は「ＳＫ１」と「ＤＢ１」とを対応付けて秘密鍵対応表３５０に設定する。
Ｓ１３１により、セットアップ処理は終了する。
【００６２】
図１１は、実施の形態１におけるデータ登録端末２００のデータ登録処理を示すフローチャートである。
実施の形態１におけるデータ登録端末２００のデータ登録処理について、図１１に基づいて説明する。
【００６３】
検索対象のデータを登録したい利用者（以下、「登録者」という）はデータ登録端末２００のデータ登録要求処理部２２０を起動し、データ登録端末２００のデータ登録要求処理部２２０は以下のデータ登録処理（Ｓ２１０からＳ２５１）を実行する。
【００６４】
Ｓ２１０において、登録者は、検索対象として登録したいデータと、データに関連するキーワードと、データが属するカテゴリを示すカテゴリ情報とを入力装置を用いてデータ登録端末２００の登録情報入力部２２１に対して入力する。つまり、登録情報入力部２２１は、登録者によって指定されたデータとキーワードとカテゴリ情報とを入力装置から入力する。
Ｓ２１０の後、Ｓ２２０に進む。
【００６５】
Ｓ２２０において、データ暗号文生成部２２２は、登録端末記憶部２９０からデータ用公開鍵１４１を取得し、取得したデータ用公開鍵１４１を用いてＳ２１０で入力されたデータを暗号化する。以下、暗号化後のデータを「データ暗号文２３１」という。
Ｓ２２０の後、Ｓ２３０に進む。
【００６６】
Ｓ２３０において、キーワード暗号文生成部２２３は、登録端末記憶部２９０からキーワード用公開鍵１４２を取得し、取得したキーワード用公開鍵１４２を用いてＳ２１０で入力されたキーワードを暗号化する。以下、暗号化後のキーワードを「キーワード暗号文２３２」という。
Ｓ２３０の後、Ｓ２４０に進む。
【００６７】
Ｓ２４０において、索引用タグ生成部２２４は、登録端末記憶部２９０に記憶されている公開鍵対応表１６０を参照する。
そして、索引用タグ生成部２２４は、公開鍵対応表１６０に示されている複数のカテゴリ判定用公開鍵１４３のうちＳ２１０で入力されたカテゴリ情報が示すカテゴリに対応付けられているカテゴリ判定用公開鍵１４３を選択し、選択したカテゴリ判定用公開鍵１４３を登録端末記憶部２９０から取得する。
Ｓ２４０の後、Ｓ２４１に進む。
【００６８】
Ｓ２４１において、索引用タグ生成部２２４は、登録端末記憶部２９０から鍵判定値１９１を取得し、Ｓ２４０で取得したカテゴリ判定用公開鍵１４３を用いて鍵判定値１９１を暗号化する。以下、暗号化後の鍵判定値１９１を「索引用タグ２３３」という。
Ｓ２４１の後、Ｓ２５０に進む。
【００６９】
Ｓ２５０において、データ登録要求部２２５は、Ｓ２２０で生成したデータ暗号文２３１とＳ２３０で生成したキーワード暗号文２３２とＳ２４１で生成した索引用タグ２３３とを含んだシステム暗号文２３０（図７参照）を生成する。
Ｓ２５０の後、Ｓ２５１に進む。
【００７０】
Ｓ２５１において、データ登録要求部２２５は、Ｓ２５０で生成したシステム暗号文２３０の登録を要求する登録要求をデータ検索サーバ３００へ送信する。登録要求はシステム暗号文２３０を含んだデータである。
Ｓ２５１により、データ登録要求処理は終了する。
【００７１】
図１２は、実施の形態１におけるデータ検索サーバ３００のデータ登録処理を示すフローチャートである。
実施の形態１におけるデータ検索サーバ３００のデータ登録処理について、図１２に基づいて説明する。
【００７２】
Ｓ３１０において、登録要求受信部３２１は、データ登録端末２００から送信されるシステム暗号文２３０の登録要求を受信する。
Ｓ３１０の後、Ｓ３２０に進む。
【００７３】
Ｓ３２０において、カテゴリ判定部３４０は、後述するＳ３３０で選択していない未選択のカテゴリ判定用秘密鍵１５３が検索サーバ記憶部３９０に有るか否かを判定する。
未選択のカテゴリ判定用秘密鍵１５３が有る場合（ＹＥＳ）、Ｓ３３０に進む。
未選択のカテゴリ判定用秘密鍵１５３が無い場合（ＮＯ）、Ｓ３２１に進む。
【００７４】
Ｓ３３０において、カテゴリ判定部３４０は、検索サーバ記憶部３９０から未選択のカテゴリ判定用秘密鍵１５３を一つ選択し、選択したカテゴリ判定用秘密鍵１５３を検索サーバ記憶部３９０から取得する。
Ｓ３３０の後、Ｓ３３１に進む。
【００７５】
Ｓ３３１において、カテゴリ判定部３４０は、Ｓ３１０で受信されたシステム暗号文２３０から索引用タグ２３３を取得し、取得した索引用タグ２３３をＳ３３０で取得したカテゴリ判定用秘密鍵１５３を用いて復号する。以下、索引用タグ２３３を復号した値を索引用タグ２３３の復号値という。
Ｓ３３１の後、Ｓ３３２に進む。
【００７６】
Ｓ３３２において、カテゴリ判定部３４０は、Ｓ３３１で得られた索引用タグ２３３の復号値と検索サーバ記憶部３９０に記憶されている鍵判定値１９１とを比較する。
索引用タグ２３３の復号値と鍵判定値１９１とが同じ値である場合（ＹＥＳ）、Ｓ３４０に進む。
索引用タグ２３３の復号値と鍵判定値１９１とが異なる値である場合（ＮＯ）、Ｓ３２０に戻る。
【００７７】
Ｓ３４０において、データ登録部３２２は、検索サーバ記憶部３９０に記憶されている秘密鍵対応表３５０（図９参照）を参照し、秘密鍵対応表３５０に示されている複数のカテゴリ別ＤＢ部３９１のうちＳ３３０で選択したカテゴリ判定用秘密鍵１５３に対応付けられているカテゴリ別ＤＢ部３９１を選択する。
そして、データ登録部３２２は、選択したカテゴリ別ＤＢ部３９１にＳ３１０で受信されたシステム暗号文２３０を記憶する。
Ｓ３４０により、データ登録処理は終了する。
【００７８】
Ｓ３２１において、データ登録部３２２は、Ｓ３１０で受信されたシステム暗号文２３０を未分類ＤＢ部３９２に記憶する。つまり、システム暗号文２３０のデータ暗号文２３１がいずれのカテゴリ別ＤＢ部３９１のカテゴリにも分類されない場合、データ登録部３２２はシステム暗号文２３０を未分類ＤＢ部３９２に記憶する。未分類ＤＢ部３９２はデータ検索サーバ３００に予め生成しておく。
Ｓ３２１により、データ登録処理は終了する。
【００７９】
図１１に示したデータ登録要求処理と図１２に示したデータ登録処理とにより、システム暗号文２３０はデータ検索サーバ３００のいずれかのカテゴリ別ＤＢ部３９１または未分類ＤＢ部３９２に記憶される。
【００８０】
図１３は、実施の形態１におけるデータ検索端末１００のデータ検索要求処理を示すフローチャートである。
実施の形態１におけるデータ検索端末１００のデータ検索要求処理について、図１３に基づいて説明する。
【００８１】
検索者はデータ検索端末１００の検索要求処理部１２０を起動し、データ検索端末１００の検索要求処理部１２０は以下のデータ検索要求処理（Ｓ４１０からＳ４４１）を実行する。
【００８２】
Ｓ４１０において、検索者は、検索キーワードと検索対象のカテゴリを示すカテゴリ情報とを入力装置を用いてデータ検索端末１００の検索キーワード入力部１２１に対して入力する。つまり、検索キーワード入力部１２１は検索者によって指定された検索キーワードとカテゴリ情報とを入力装置から入力する。
Ｓ４１０の後、Ｓ４２０に進む。
【００８３】
Ｓ４２０において、検索クエリ生成部１２２は、検索端末記憶部１９０からキーワード用秘密鍵１５２を取得し、取得したキーワード用秘密鍵１５２を用いてＳ４１０で入力された検索キーワードを暗号化する。以下、暗号化後の検索キーワードを「検索用トラップドア１７１」という。
Ｓ４２０の後、Ｓ４２１に進む。
【００８４】
Ｓ４２１において、検索クエリ生成部１２２は、検索端末記憶部１９０に記憶されている公開鍵対応表１６０を参照し、公開鍵対応表１６０に示されている複数のカテゴリ判定用公開鍵１４３のうちＳ４１０で入力されたカテゴリ情報が示すカテゴリに対応付けられているカテゴリ判定用公開鍵１４３を選択する。
Ｓ４２１の後、Ｓ４２２に進む。
【００８５】
Ｓ４２２において、検索クエリ生成部１２２は、検索端末記憶部１９０から鍵判定値１９１を取得し、取得した鍵判定値１９１をＳ４２１で選択したカテゴリ判定用公開鍵１４３を用いて暗号化する。以下、暗号化後の鍵判定値１９１を「索引用タグ１７２」という。
Ｓ４２２の後、Ｓ４２３に進む。
【００８６】
Ｓ４２３において、検索クエリ生成部１２２は、Ｓ４２０で生成した検索用トラップドア１７１とＳ４２２で生成した索引用タグ１７２とを含んだ検索クエリ１７０（図５参照）を生成する。
Ｓ４２３の後、Ｓ４３０に進む。
【００８７】
Ｓ４３０において、検索要求部１２３は、Ｓ４２３で生成された検索クエリ１７０をデータ検索サーバ３００へ送信する。
Ｓ４３０の後、Ｓ４３１に進む。
【００８８】
Ｓ４３１において、検索要求部１２３は、データ検索サーバ３００から送信される検索結果を受信する。検索結果は、検索クエリ１７０に対応するデータ暗号文２３１（言い換えると「検索条件を満たすデータ暗号文２３１」または「検索処理でヒットしたデータ暗号文２３１」）を含んだデータである。
Ｓ４３１の後、Ｓ４４０に進む。
【００８９】
Ｓ４４０において、検索結果出力部１２４は、検索端末記憶部１９０からデータ用秘密鍵１５１を取得し、取得したデータ用秘密鍵１５１を用いてＳ４３１で受信された検索結果に含まれるデータ暗号文２３１を復号する。データ暗号文２３１を復号することにより、暗号化前のデータが得られる。
Ｓ４４０の後、Ｓ４４１に進む。
【００９０】
Ｓ４４１において、検索結果出力部１２４は、Ｓ４４０で得られたデータを含んだ検索結果を出力する。例えば、検索結果出力部１２４は、検索結果をディスプレイに表示する。
Ｓ４４１により、データ検索要求処理は終了する。
【００９１】
図１４は、実施の形態１におけるデータ検索サーバ３００のデータ検索処理を示すフローチャートである。
実施の形態１におけるデータ検索サーバ３００のデータ検索処理について、図１４に基づいて説明する。
【００９２】
Ｓ５１０において、検索要求受信部３３１は、データ検索端末１００から送信される検索クエリ１７０を受信する。検索クエリ１７０は、検索用トラップドア１７１と索引用タグ１７２とを含んだデータである（図５参照）。
Ｓ５１０の後、Ｓ５２０に進む。
【００９３】
Ｓ５２０において、カテゴリ判定部３４０は、後述するＳ５３０で選択していない未選択のカテゴリ判定用秘密鍵１５３が検索サーバ記憶部３９０に有るか否かを判定する。
未選択のカテゴリ判定用秘密鍵１５３が有る場合（ＹＥＳ）、Ｓ５３０に進む。
未選択のカテゴリ判定用秘密鍵１５３が無い場合（ＮＯ）、Ｓ５２１に進む。
【００９４】
Ｓ５３０において、カテゴリ判定部３４０は、検索サーバ記憶部３９０から未選択のカテゴリ判定用秘密鍵１５３を一つ選択し、選択したカテゴリ判定用秘密鍵１５３を検索サーバ記憶部３９０から取得する。
Ｓ５３０の後、Ｓ５３１に進む。
【００９５】
Ｓ５３１において、カテゴリ判定部３４０は、Ｓ５１０で受信された検索クエリ１７０から索引用タグ１７２を取得し、取得した索引用タグ１７２をＳ５３０で取得したカテゴリ判定用秘密鍵１５３を用いて復号する。以下、索引用タグ１７２を復号した値を索引用タグ１７２の復号値という。
Ｓ５３１の後、Ｓ５３２に進む。
【００９６】
Ｓ５３２において、カテゴリ判定部３４０は、Ｓ５３１で得られた索引用タグ１７２の復号値と検索サーバ記憶部３９０に記憶されている鍵判定値１９１とを比較する。
索引用タグ１７２の復号値と鍵判定値１９１とが同じ値である場合（ＹＥＳ）、Ｓ５４０に進む。
索引用タグ１７２の復号値と鍵判定値１９１とが異なる値である場合（ＮＯ）、Ｓ５２０に戻る。
【００９７】
Ｓ５４０において、データ検索部３３２は、検索サーバ記憶部３９０に記憶されている秘密鍵対応表３５０（図９参照）を参照し、秘密鍵対応表３５０に示されている複数のカテゴリ別ＤＢ部３９１のうちＳ５３０で選択したカテゴリ判定用秘密鍵１５３に対応付けられているカテゴリ別ＤＢ部３９１を検索対象として選択する。
そして、データ検索部３３２は、Ｓ５１０で受信された検索クエリ１７０から検索用トラップドア１７１を取得し、取得した検索用トラップドア１７１を用いて検索可能公開鍵暗号方式の検索アルゴリズムによって検索対象のカテゴリ別ＤＢ部３９１を検索する。
【００９８】
例えば、データ検索部３３２は以下のように検索する。
データ検索部３３２は、検索対象のカテゴリ別ＤＢ部３９１からシステム暗号文２３０を一つずつ選択し、選択したシステム暗号文２３０からキーワード暗号文２３２を取得する。
データ検索部３３２は、キーワード暗号文２３２と検索用トラップドア１７１とを入力データにして検索可能公開鍵暗号方式の検索アルゴリズム（検索プログラム）を実行する。
データ検索部３３２は、検索アルゴリズムの実行結果に基づいて、キーワード暗号文２３２へ暗号化する前のデータキーワードと検索用トラップドア１７１へ暗号化する前の検索キーワードとが一致するか否かを判定する。キーワード暗号文２３２のデータキーワードと検索用トラップドア１７１の検索キーワードとが一致する場合、そのキーワード暗号文２３２と共にシステム暗号文２３０に含まれているデータ暗号文２３１が検索処理でヒットしたデータ暗号文２３１である。
Ｓ５４０の後、Ｓ５５０に進む。
【００９９】
Ｓ５２１において、データ検索部３３２は、Ｓ５１０で受信された検索クエリ１７０から検索用トラップドア１７１を取得し、取得した検索用トラップドア１７１を用いて検索可能公開鍵暗号方式の検索アルゴリズムによって未分類ＤＢ部３９２を検索する。つまり、データ検索部３３２はカテゴリ別ＤＢ部３９１の代わりに未分類ＤＢ部３９２を検索対象にして検索処理を行う。検索方法はＳ５４０と同様である。
Ｓ５２１の後、Ｓ５５０に進む。
【０１００】
Ｓ５５０において、検索結果送信部３３３は、Ｓ５４０またはＳ５２１の検索処理でヒットしたデータ暗号文２３１を含んだ検索結果をデータ検索端末１００へ送信する。
Ｓ５５０により、データ検索処理は終了する。
【０１０１】
図１４に示したデータ検索処理により、データ検索サーバ３００は、検索者が指定したカテゴリ用のカテゴリ別ＤＢ部３９１（または未分類ＤＢ部３９２）を検索対象にして検索可能公開鍵暗号方式で検索を行うことができる。つまり、データ検索サーバ３００は、データと検索キーワードと検索対象のカテゴリとを秘匿にしたままキーワード検索を行うことができる。また、データ検索サーバ３００は、検索者が指定したカテゴリ用のカテゴリ別ＤＢ部３９１（または未分類ＤＢ部３９２）を検索対象にして検索を行うことにより、全てのデータ暗号文２３１を検索する場合に比べて検索時間を短縮させることができる。
【０１０２】
図１５は、実施の形態１におけるデータ検索端末１００のカテゴリ登録要求処理を示すフローチャートである。
実施の形態１におけるデータ検索端末１００のカテゴリ登録要求処理について、図１５に基づいて説明する。
【０１０３】
Ｓ６０１において、検索者は、未分類のシステム暗号文２３０を分類したいカテゴリを示すカテゴリ情報を入力装置を用いてデータ検索端末１００のカテゴリ登録要求部１３０に対して入力する。つまり、カテゴリ登録要求部１３０は検索者に指定されたカテゴリ情報を入力装置から入力する。
Ｓ６０１の後、Ｓ６０２に進む。
【０１０４】
Ｓ６０２において、カテゴリ登録要求部１３０は、検索端末記憶部１９０に記憶されている公開鍵対応表１６０（図４参照）を参照し、公開鍵対応表１６０に示されている複数のカテゴリ判定用秘密鍵１５３のうちＳ６０１で入力したカテゴリ情報が示すカテゴリに対応付けられているカテゴリ判定用秘密鍵１５３を選択する。
Ｓ６０２の後、Ｓ６０３に進む。
【０１０５】
Ｓ６０３において、カテゴリ登録要求部１３０は、Ｓ６０２で選択したカテゴリ判定用秘密鍵１５３を検索端末記憶部１９０から取得し、取得したカテゴリ判定用秘密鍵１５３を含んだカテゴリ登録要求をデータ検索サーバ３００へ送信する。
Ｓ６０３により、カテゴリ登録要求処理は終了する。
【０１０６】
図１６は、実施の形態１におけるデータ検索サーバ３００のカテゴリ登録処理を示すフローチャートである。
実施の形態１におけるデータ検索サーバ３００のカテゴリ登録処理について、図１６に基づいて説明する。
【０１０７】
Ｓ６１０において、カテゴリ用秘密鍵管理部３１０は、データ検索端末１００から送信されるカテゴリ登録要求を受信する。カテゴリ登録要求はカテゴリ判定用秘密鍵１５３を含んだデータである。
カテゴリ用秘密鍵管理部３１０は、受信したカテゴリ登録要求からカテゴリ判定用秘密鍵１５３を取得し、取得したカテゴリ判定用秘密鍵１５３を検索サーバ記憶部３９０に記憶する。
Ｓ６１０の後、Ｓ６２０に進む。
【０１０８】
Ｓ６２０において、カテゴリ用秘密鍵管理部３１０は、新たにカテゴリ別ＤＢ部３９１を生成する。
Ｓ６２０の後、Ｓ６３０に進む。
【０１０９】
Ｓ６３０において、カテゴリ用秘密鍵管理部３１０は、Ｓ６１０で取得したカテゴリ判定用秘密鍵１５３とＳ６２０で生成したカテゴリ別ＤＢ部３９１とを対応付けて秘密鍵対応表３５０（図９参照）に設定する。
Ｓ６３０の後、Ｓ６４０に進む。
【０１１０】
Ｓ６４０において、カテゴリ用秘密鍵管理部３１０は、後述するＳ６４１で選択していない未選択のシステム暗号文２３０が未分類ＤＢ部３９２にあるか否かを判定する。
未選択のシステム暗号文２３０が未分類ＤＢ部３９２にある場合（ＹＥＳ）、Ｓ６４１に進む。
未選択のシステム暗号文２３０が未分類ＤＢ部３９２に無い場合（ＮＯ）、カテゴリ登録処理は終了する。
【０１１１】
Ｓ６４１において、カテゴリ用秘密鍵管理部３１０は、未分類ＤＢ部３９２から未選択のシステム暗号文２３０を１つ選択し、選択したシステム暗号文２３０を未分類ＤＢ部３９２から取得する。
Ｓ６４１の後、Ｓ６４２に進む。
【０１１２】
Ｓ６４２において、カテゴリ用秘密鍵管理部３１０は、Ｓ６４１で選択したシステム暗号文２３０から索引用タグ２３３を取得し、取得した索引用タグ２３３をＳ６１０で取得したカテゴリ判定用秘密鍵１５３を用いて復号する。以下、索引用タグ２３３を復号した値を索引用タグ２３３の復号値という。
Ｓ６４２の後、Ｓ６４３に進む。
【０１１３】
Ｓ６４３において、カテゴリ用秘密鍵管理部３１０は、Ｓ６４２で得られた索引用タグ２３３の復号値と検索サーバ記憶部３９０に記憶されている鍵判定値１９１とを比較する。
索引用タグ２３３の復号値と鍵判定値１９１とが同じである場合（ＹＥＳ）、Ｓ６４４に進む。
索引用タグ２３３の復号値と鍵判定値１９１とが異なる場合（ＮＯ）、Ｓ６４０に戻る。
【０１１４】
Ｓ６４４において、カテゴリ用秘密鍵管理部３１０は、Ｓ６４１で選択したシステム暗号文２３０を未分類ＤＢ部３９２からＳ６２０で生成した新たなカテゴリ別ＤＢ部３９１へ移動する。
Ｓ６４４の後、Ｓ６４０に戻る。
【０１１５】
図１５に示したカテゴリ登録要求処理と図１６に示したカテゴリ登録処理とにより、新たなカテゴリ用のカテゴリ別ＤＢ部３９１が生成され、生成されたカテゴリ別ＤＢ部３９１には新たなカテゴリに分類されるシステム暗号文２３０が記憶される。
【０１１６】
図１７は、実施の形態１におけるデータ検索システム９００のハードウェア資源の一例を示す図である。
図１７において、データ検索端末１００、データ登録端末２００およびデータ検索サーバ３００（いずれもコンピュータの一例）は、ＣＰＵ９０１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を備えている。ＣＰＵ９０１は、バス９０２を介してＲＯＭ９０３、ＲＡＭ９０４、通信ボード９０５、ディスプレイ９１１（表示装置）、キーボード９１２、マウス９１３、ドライブ９１４、磁気ディスク装置９２０などのハードウェアデバイスと接続され、これらのハードウェアデバイスを制御する。ドライブ９１４は、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）などの記憶媒体を読み書きする装置である。
ＲＯＭ９０３、ＲＡＭ９０４、磁気ディスク装置９２０およびドライブ９１４は記憶装置の一例である。キーボード９１２、マウス９１３および通信ボード９０５は入力装置の一例である。ディスプレイ９１１および通信ボード９０５は出力装置の一例である。
【０１１７】
通信ボード９０５は、有線または無線で、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネット、電話回線などの通信網に接続している。
【０１１８】
磁気ディスク装置９２０には、ＯＳ９２１（オペレーティングシステム）、プログラム群９２２、ファイル群９２３が記憶されている。
【０１１９】
プログラム群９２２には、実施の形態において「〜部」として説明する機能を実行するプログラムが含まれる。プログラム（例えば、データ検索プログラム、データ登録プログラム、情報処理プログラム）は、ＣＰＵ９０１により読み出され実行される。すなわち、プログラムは、「〜部」としてコンピュータを機能させるものであり、また「〜部」の手順や方法をコンピュータに実行させるものである。
【０１２０】
ファイル群９２３には、実施の形態において説明する「〜部」で使用される各種データ（入力、出力、判定結果、計算結果、処理結果など）が含まれる。
【０１２１】
実施の形態において構成図およびフローチャートに含まれている矢印は主としてデータや信号の入出力を示す。
フローチャートなどに基づいて説明する実施の形態の処理はＣＰＵ９０１、記憶装置、入力装置、出力装置などのハードウェアを用いて実行される。
【０１２２】
実施の形態において「〜部」として説明するものは「〜回路」、「〜装置」、「〜機器」であってもよく、また「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明するものは、ファームウェア、ソフトウェア、ハードウェアまたはこれらの組み合わせのいずれで実装されても構わない。
【０１２３】
実施の形態１におけるデータ検索システム９００は、例えば、以下のような特徴を有する。
（１）暗号文（システム暗号文２３０）と検索クエリとの両方に索引用タグを付加する（図５、７参照）。
（２）データ検索サーバ３００に秘密鍵（カテゴリ判定用秘密鍵１５３）を開示することによって、秘密鍵に対応した特定のデータを全体から分離する。
（３）検索クエリ内の索引用タグを秘密鍵で復号し、その結果を見て検索対象を限定する（図１４参照）。
（４）上記の（１）から（３）を組み合わせることにより、全件検索を回避し、検索を高速化する。
【０１２４】
実施の形態１におけるデータ検索システム９００により、例えば、以下のような効果を奏することができる。
（１）検索可能公開鍵暗号において検索の高速化を実現できる、という効果がある。
（２）特定のデータ（例えば、あるカテゴリに該当するデータ）に狙いを定めて検索を高速化することができる、という効果がある。
（３）検索者が検索の高速化を行うカテゴリを適応的に増加させることができる、という効果がある（図１５、１６参照）。
（４）索引用タグの作成に使用する公開鍵暗号としてＥｌＧａｍａｌ暗号やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号などの鍵匿名性を有する公開鍵暗号方式を利用することにより、暗号文のカテゴリ情報をデータ検索サーバ３００に秘匿したままで検索を高速化できる、という効果がある。また、鍵匿名性を有さない公開鍵暗号方式を利用することにより、公開鍵暗号方式の選択肢を増やすことができる、という効果がある。
（５）既存の検索可能公開鍵暗号に対してカテゴリ判定用鍵ペア群（図３参照）や索引用タグ（図５、７参照）を増設する（アドオンする）構成をとっているため、既存の検索可能公開鍵暗号を大きく変更することなく実装することができる、という効果がある。これにより、実装コストを低減させることができる、という効果がある。
【０１２５】
実施の形態１におけるデータ検索システム９００は以下のような構成にしてもよい。
【０１２６】
（１）システム暗号文２３０に複数の索引用タグ２３３を含めてもよい。この場合、登録者は複数のカテゴリ情報をデータ登録端末２００に指定（入力）する。そして、データ登録端末２００は指定されたカテゴリ別に索引用タグ２３３を生成し、生成した複数の索引用タグ２３３をシステム暗号文２３０に設定する。また、データ検索サーバ３００は、システム暗号文２３０に含まれる複数の索引用タグ２３３に対応する複数のカテゴリ別ＤＢ部３９１にシステム暗号文２３０を記憶する。これにより、複数のカテゴリにまたがるデータに対応することができる。
【０１２７】
（２）実施の形態１では索引用タグの平文（鍵判定値１９１）として定数（例えば「１」）を用いる例を示したが、検索対象のデータやキーワードに依存した平文を用いてもよい。
例えば、キーワード暗号文２３２（図７参照）のハッシュ値を索引用タグの平文として用いてもよい。このようにすれば、キーワード暗号文２３２と索引用タグとの間に対応関係が生じるため、通信路上におけるデータの取り替え攻撃に耐性を持たせることができる。この場合、データ検索端末１００、データ登録端末２００およびデータ検索サーバ３００は鍵判定値１９１を使用する代わりにキーワード暗号文２３２のハッシュ値を算出して使用する。
【０１２８】
（３）複数の鍵判定値１９１を用いてカテゴリの分類を詳細化してもよい。カテゴリの分類を詳細化することにより、より高速な検索を実現することができる。
例えば、データ検索システム９００は以下のように動作する。
データ検索端末１００は図１８に示すような鍵判定値対応表１９２を生成し、生成した鍵判定値対応表１９２をデータ登録端末２００およびデータ検索サーバ３００に提供する。
データ検索端末１００およびデータ登録端末２００は利用者からカテゴリの大分類と小分類とを指定され、指定されたカテゴリの大分類と小分類とに対応付けられた鍵判定値１９１を使用する。
データ検索サーバ３００は、カテゴリの大分類毎（カテゴリ判定用秘密鍵１５３毎）にカテゴリ別ＤＢ部３９１を生成し、カテゴリ別ＤＢ部３９１内でカテゴリの小分類別にシステム暗号文２３０を記憶する。例えば、データ検索サーバ３００は、索引用タグ２３３の復号値が「１１」であるシステム暗号文２３０と索引用タグ２３３の復号値が「１２」であるシステム暗号文２３０とをカテゴリ別ＤＢ部３９１内で別々に管理する。
図１８は、実施の形態１における鍵判定値対応表１９２を示す図である。図１８に示すように、鍵判定値対応表１９２は大分類のカテゴリと小分類のカテゴリと鍵判定値１９１とを対応付けるデータである。カテゴリの分類は３階層以上（例えば、大分類、中分類、小分類）であっても構わない。
【０１２９】
（４）実施の形態１ではカテゴリを適応的に増加させる方法（図１５、１６参照）を示したが、カテゴリを適応的に減少させてもよい。
例えば、検索者はデータ検索端末１００を操作してカテゴリの削除要求をデータ検索サーバ３００へ送信する。カテゴリの削除要求は削除したいカテゴリのカテゴリ判定用秘密鍵１５３を指定するデータである。データ検索サーバ３００は削除要求に従ってカテゴリ判定用秘密鍵１５３を削除し、カテゴリ判定用秘密鍵１５３に対応付けられたカテゴリ別ＤＢ部３９１からシステム暗号文２３０を取り出して未分類ＤＢ部３９２へ移動し、カテゴリ別ＤＢ部３９１を削除する。
【０１３０】
（５）実施の形態１ではカテゴリ判定用公開鍵１４３とカテゴリ判定用秘密鍵１５３との鍵ペアを所定数だけ生成する例を示したが、カテゴリ判定用公開鍵１４３とカテゴリ判定用秘密鍵１５３との鍵ペアを必要に応じて追加してもよい。
例えば、検索者はカテゴリを追加したい場合に追加のカテゴリ情報をデータ検索端末１００に入力する。この場合、データ検索端末１００は追加のカテゴリ情報に基づいて新たにカテゴリ判定用公開鍵１４３とカテゴリ判定用秘密鍵１５３との鍵ペアを生成し、公開鍵対応表１６０を更新し、カテゴリ判定用公開鍵１４３とカテゴリ判定用秘密鍵１５３と公開鍵対応表１６０とをセットアップ処理と同様にデータ登録端末２００およびデータ検索サーバ３００に提供する。
【０１３１】
（６）実施の形態１ではデータ（データ暗号文２３１）やキーワード（キーワード暗号文２３２）の内容に関するカテゴリ（例えば「特許」「意匠」）によってシステム暗号文２３０を分類する例を示した。但し、データのその他の属性（作成日付、データサイズなど）によってシステム暗号文２３０を分類しても構わない。これにより、データの属性（種類）に応じてシステム暗号文２３０を管理し、検索を高速化することができる。
図１９は、実施の形態１における公開鍵対応表１６０の別例を示す図である。
例えば、データ検索端末１００は図１９に示すような公開鍵対応表１６０を生成し、生成した公開鍵対応表１６０をデータ登録端末２００に提供する。データ登録端末２００は、公開鍵対応表１６０に示される複数のカテゴリ判定用公開鍵１４３のうちシステム暗号文２３０の作成日に対応付けられているカテゴリ判定用公開鍵１４３を用いてシステム暗号文２３０の索引用タグ２３３を生成する。検索者は、取得したいデータの作成日をデータ検索端末１００に入力する。そして、データ検索端末１００は、公開鍵対応表１６０に示される複数のカテゴリ判定用公開鍵１４３のうち入力されたデータの作成日に対応付けられているカテゴリ判定用公開鍵１４３を用いて検索クエリ１７０の索引用タグ１７２を生成する。
【０１３２】
（７）公開鍵暗号方式（または検索可能公開鍵暗号）の代わりに他の暗号方式（例えば、共通鍵暗号方式）を用いても構わない。また、データやキーワードを必要に応じて暗号化せずに登録しても構わない。
【０１３３】
実施の形態１において、例えば、以下のようなデータ検索システム９００について説明した。
データ検索装置（データ検索サーバ３００）は、データ記憶部と、鍵判定情報記憶部と、検索条件入力部と、データグループ選択部と、データ検索部と、検索結果出力部とを備える。
データ記憶部（記憶装置）は、１つ以上のデータ（システム暗号文２３０）を含んだ複数のデータグループ（カテゴリ別ＤＢ部３９１）と暗号化された情報を復号する複数の復号鍵（カテゴリ判定用秘密鍵１５３）とを対応付けて記憶する。
鍵判定情報記憶部（検索サーバ記憶部３９０）は、復号鍵を判定するための鍵判定情報（鍵判定値１９１）を記憶する。
検索条件入力部（検索要求受信部３３１）は、データを検索するための検索条件（検索用トラップドア１７１）と、所定の情報（鍵判定値１９１）を暗号化した暗号化情報（索引用タグ１７２）とを入力する。
データグループ選択部（カテゴリ判定部３４０）は、検索条件入力部が入力した暗号化情報をデータ記憶部に記憶される複数の復号鍵それぞれを用いて復号する。データグループ選択部は、複数の復号鍵のうち暗号化情報を鍵判定情報と同じ情報に復号した復号鍵を選択する。データグループ選択部は、データ記憶部に記憶される複数のデータグループのうち選択した復号鍵に対応付けられたデータグループを検索先グループとして選択する。
データ検索部（データ検索部３３２）は、データグループ選択部によって選択された検索先グループに含まれる１つ以上のデータから検索条件入力部が入力した検索条件を満たすデータを検索結果のデータとして取得する。
検索結果出力部（検索結果送信部３３３）は、データ検索部によって取得された検索結果のデータを出力する。
【０１３４】
データ検索装置は、さらに、新規データ入力部と新規データ登録部とを備える。
新規データ入力部（登録要求受信部３２１）は、新規データ（データ暗号文２３１）と所定の情報（鍵判定値１９１）を暗号化した暗号化タグ（索引用タグ２３３）とを入力する。
新規データ登録部（データ登録部３２２）は、新規データ入力部が入力した新規データを複数のデータグループのうちデータグループ選択部によって選択される登録先グループに追加する。
データグループ選択部は、新規データ入力部が入力した暗号化タグを複数の復号鍵それぞれを用いて復号する。データグループ選択部は、複数の復号鍵のうち暗号化タグを鍵判定情報と同じ情報に復号した復号鍵を選択し、複数のデータグループのうち選択した復号鍵に対応付けられたデータグループを登録先グループとして選択する。
【０１３５】
データ記憶部（記憶装置）は、さらに、複数のデータと所定の情報を暗号化した複数の暗号化タグとを対応付けて含んだデータグループとして未分類グループ（未分類ＤＢ部３９２）を記憶する。
データ検索装置は、さらに、追加復号鍵入力部とデータグループ登録部とを備える。
追加復号鍵入力部（カテゴリ用秘密鍵管理部３１０）は、新たな復号鍵（カテゴリ判定用秘密鍵１５３）を追加復号鍵として入力する。
データグループ登録部（カテゴリ用秘密鍵管理部３１０）は、未分類グループに含まれる複数の暗号化タグを追加復号鍵入力部が入力した追加復号鍵を用いて復号する。データグループ登録部は、複数の暗号化タグのうち鍵判定情報と同じ情報に復号された暗号化タグを選択する。データグループ登録部は、未分類グループに含まれる複数のデータから、選択した暗号化タグに対応付けられたデータを抽出し、複数のデータグループに加える新たなデータグループとして、抽出したデータを含んだ追加グループを生成する。データグループ登録部は、生成した追加グループと追加復号鍵とを対応付けてデータ記憶部に記憶する。
【０１３６】
データ登録装置（データ登録端末２００）は、データ生成部と、分類情報入力部と、暗号化タグ生成部と、データ登録要求部とを備える。
データ生成部（データ暗号文生成部２２２）はデータ（データ暗号文２３１）を生成する。
分類情報入力部（登録情報入力部２２１）は、データ生成部によって生成されたデータの分類を示す分類情報を入力する。
暗号化タグ生成部（索引用タグ生成部２２４）は、分類情報入力部が入力した分類情報に基づいて所定の情報（鍵判定値１９１）を暗号化することによって暗号化タグ（索引用タグ２３３）を生成する。
データ登録要求部（データ登録要求部２２５）は、データ生成部が生成したデータと暗号化タグ生成部が生成した暗号化タグとをデータ検索装置（データ検索サーバ３００）へ送信する。これにより、データ登録要求部は、分類情報が示す分類のデータグループにデータを検索対象のデータとして追加する処理をデータ検索装置に実行させる。
【０１３７】
データ登録装置は、さらに、複数の暗号化鍵（カテゴリ判定用公開鍵１４３）と複数の分類情報（カテゴリ情報）とを対応付けて記憶する暗号化鍵記憶部（登録端末記憶部２９０）を備える。
暗号化タグ生成部は、暗号化鍵記憶部に記憶される複数の暗号化鍵のうち分類情報入力部が入力した分類情報と同じ分類情報に対応付けられた暗号化鍵を選択し、選択した暗号化鍵を用いて所定の情報を暗号化して暗号化タグを生成する。
【０１３８】
情報処理装置（データ検索端末１００）は、検索条件入力部と、暗号化タグ生成部と、データ検索要求部とを備える。
検索条件入力部（検索キーワード入力部１２１）は、データ（データ暗号文２３１）を検索するための検索条件（検索キーワード）とデータの分類を示す分類情報（カテゴリ情報）とを入力する。
暗号化タグ生成部（検索クエリ生成部１２２）は、検索条件入力部が入力した分類情報に基づいて所定の情報（鍵判定値１９１）を暗号化することによって暗号化タグ（索引用タグ１７２）を生成する。
データ検索要求部（検索要求部１２３）は、検索条件入力部が入力した検索条件の情報（検索用トラップドア１７１）と暗号化タグ生成部によって生成された暗号化タグとをデータ検索装置（データ検索サーバ３００）へ送信する。データ検索要求部は、分類情報が示す分類のデータグループに含まれるデータのうち検索条件を満たすデータを検索結果のデータとしてデータ検索装置から受信する。
【０１３９】
情報処理装置は、さらに、複数の暗号化鍵（カテゴリ判定用公開鍵１４３）と複数の分類情報とを対応付けて記憶する暗号化鍵記憶部（検索端末記憶部１９０）を備える。
暗号化タグ生成部は、暗号化鍵記憶部に記憶される複数の暗号化鍵のうち検索条件入力部が入力した分類情報と同じ分類情報に対応付けられた暗号化鍵を選択し、選択した暗号化鍵を用いて所定の情報を暗号化して暗号化タグを生成する。
【０１４０】
実施の形態２．
公開鍵暗号の代わりにＩＤベース暗号（ＩＢＥ：Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ）を用いる形態について説明する。
ＩＤベース暗号とは、ユーザ名、ＩＰアドレス、メールアドレスなどの識別子（ＩＤ）を公開鍵として用いる暗号方式である。
以下、実施の形態１と異なる事項について主に説明する。説明を省略する事項については実施の形態１と同様である。
【０１４１】
データ検索システム９００の構成、およびデータ検索端末１００とデータ登録端末２００とデータ検索サーバ３００との機能構成は、実施の形態１と同様である（図１、２、６、８参照）。
【０１４２】
但し、データ検索システム９００は、以下の点で実施の形態１と異なる。
【０１４３】
データ検索システム９００は、公開鍵暗号の代わりにＩＤベース暗号を用いるため、実施の形態１で説明した公開鍵対応表１６０（図４参照）が不要である。このため、データ検索端末１００の公開鍵対応表生成部１１２も不要である。処理の詳細については後述する。
【０１４４】
図２０は、実施の形態２におけるシステム公開鍵１４０とシステム秘密鍵１５０とを示す図である。
実施の形態２におけるシステム公開鍵１４０とシステム秘密鍵１５０とについて、図２０に基づいて説明する。
【０１４５】
システム公開鍵１４０は、実施の形態１（図３参照）で説明した複数のカテゴリ判定用公開鍵１４３の代わりに、一つのＩＢＥマスタ公開鍵１４４を有する。ＩＢＥマスタ公開鍵１４４はＩＤベース暗号のマスタ公開鍵である。
システム秘密鍵１５０は、実施の形態１（図３参照）で説明した複数のカテゴリ判定用秘密鍵１５３の代わりに、一つのＩＢＥマスタ秘密鍵１５４を有する。ＩＢＥマスタ秘密鍵１５４はＩＤベース暗号のマスタ秘密鍵である。
【０１４６】
図２１は、実施の形態２におけるデータ検索端末１００のセットアップ処理を示すフローチャートである。
実施の形態２におけるデータ検索端末１００のセットアップ処理について、図２１に基づいて説明する。
以下に説明するＳ１１０ＢからＳ１３１Ｂは、実施の形態１（図１０参照）で説明したＳ１１０からＳ１３１に対応する処理である。実施の形態１と一部が異なる処理には末尾に「Ｂ」を付記する。
【０１４７】
Ｓ１１０Ｂにおいて、システム鍵生成部１１１はシステム公開鍵１４０とシステム秘密鍵１５０とを生成する。
図２０に示したように、システム公開鍵１４０はＩＢＥマスタ公開鍵１４４を含み、システム秘密鍵１５０はＩＢＥマスタ秘密鍵１５４を含む。
システム鍵生成部１１１は、ＩＤベース暗号方式のマスタ鍵生成アルゴリズムを実行してＩＢＥマスタ公開鍵１４４とＩＢＥマスタ秘密鍵１５４との鍵ペアを生成する。
例えば、システム鍵生成部１１１は、Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎ  ＩＤベース暗号（ＢＦ−ＩＢＥ）（非特許文献４参照）やＢｏｙｅｎ−Ｗａｔｅｒｓ  ＩＤベース暗号（ＢＷ−ＩＢＥ）（非特許文献５参照）など、匿名性（ａｎｏｎｙｍｉｔｙ）を有するＩＤベース暗号方式を使用する。匿名性とは、暗号文を見てもどのＩＤを公開鍵として用いたかわからない、という性質である（非特許文献６参照）。
但し、システム鍵生成部１１１は、匿名性を有さないＩＤベース暗号方式（例えば、Ｂｏｎｅｈ−Ｂｏｙｅｎ  ＩＤベース暗号（ＢＢ−ＩＢＥ））を使用しても構わない。
Ｓ１１０Ｂの後、Ｓ１３０Ｂに進む。
【０１４８】
Ｓ１３０Ｂにおいて、鍵情報公開部１１３は、実施の形態１のＳ１３０と同様にシステム公開鍵１４０と鍵判定値１９１とＩＤベース暗号の公開パラメータとをデータ登録端末２００に対して公開する。但し、公開鍵対応表１６０は不要である。
Ｓ１３０Ｂの後、Ｓ１３１Ｂに進む。
【０１４９】
Ｓ１３１Ｂにおいて、鍵情報公開部１１３は、ＩＢＥマスタ秘密鍵１５４とカテゴリ情報とを用いてＩＤベース暗号のユーザ秘密鍵生成アルゴリズムを実行し、カテゴリ別にユーザ秘密鍵を生成する。カテゴリ情報は利用者がデータ検索端末１００に対して指定（入力）する。
鍵情報公開部１１３は、実施の形態１のＳ１３１と同様にカテゴリ別のユーザ秘密鍵（カテゴリ判定用秘密鍵１５３の代わり）と鍵判定値１９１とＩＤベース暗号の公開パラメータとをデータ検索サーバ３００に登録する。データ検索サーバ３００は、カテゴリ別のユーザ秘密鍵とカテゴリ別ＤＢ部３９１とを対応付ける秘密鍵対応表３５０を生成する。
Ｓ１３１Ｂにより、セットアップ処理は終了する。
【０１５０】
図２２は、実施の形態２におけるデータ登録端末２００のデータ登録要求処理を示すフローチャートである。
実施の形態２におけるデータ登録端末２００のデータ登録要求処理について、図２２に基づいて説明する。
以下に説明するＳ２１０からＳ２５１は、実施の形態１（図１１参照）で説明したＳ２１０からＳ２５１に対応する処理である。実施の形態１と一部が異なる処理には末尾に「Ｂ」を付記する。
【０１５１】
Ｓ２１０からＳ２３０は実施の形態１と同じである。Ｓ２３０の後、Ｓ２４１Ｂに進む。
【０１５２】
Ｓ２４１Ｂにおいて、索引用タグ生成部２２４は、ＩＢＥマスタ公開鍵１４４とカテゴリ情報とを用いてＩＤベース暗号の暗号化アルゴリズムを実行し、鍵判定値１９１を暗号化した索引用タグ２３３を生成する。つまり、索引用タグ生成部２２４はカテゴリ情報をパラメータとして、ＩＢＥマスタ公開鍵１４４を用いて鍵判定値１９１を暗号化する。
Ｓ２４１Ｂの後、Ｓ２５０に進む。
【０１５３】
Ｓ２５０およびＳ２５１は実施の形態１と同じである。Ｓ２５１により、データ登録要求処理は終了する。
【０１５４】
図２３は、実施の形態２におけるデータ検索サーバ３００のデータ登録処理を示すフローチャートである。
実施の形態２におけるデータ検索サーバ３００のデータ登録処理について、図２３に基づいて説明する。
以下に説明するＳ３１０からＳ３４０Ｂは、実施の形態１（図１２参照）で説明したＳ３１０からＳ３４０に対応する処理である。実施の形態１と一部が異なる処理には末尾に「Ｂ」を付記する。
【０１５５】
Ｓ３１０において、登録要求受信部３２１はデータ登録端末２００からシステム暗号文２３０の登録要求を受信する。
Ｓ３１０の後、Ｓ３２０Ｂに進む。
【０１５６】
Ｓ３２０Ｂにおいて、カテゴリ判定部３４０は、後述するＳ３３０Ｂで選択していない未選択のカテゴリ別のユーザ秘密鍵が検索サーバ記憶部３９０に有るか否かを判定する。
未選択のカテゴリ別のユーザ秘密鍵が有る場合（ＹＥＳ）、Ｓ３３０Ｂに進む。
未選択のカテゴリ別のユーザ秘密鍵が無い場合（ＮＯ）、Ｓ３２１に進む。Ｓ３２１において、データ登録部３２２はシステム暗号文２３０を未分類ＤＢ部３９２に記憶する。
【０１５７】
Ｓ３３０Ｂにおいて、カテゴリ判定部３４０は、検索サーバ記憶部３９０から未選択のカテゴリ別のユーザ秘密鍵を一つ選択する。
Ｓ３３０Ｂの後、Ｓ３３１Ｂに進む。
【０１５８】
Ｓ３３１Ｂにおいて、カテゴリ判定部３４０は、Ｓ３３０Ｂで選択したカテゴリ別のユーザ秘密鍵を用いてシステム暗号文２３０に含まれる索引用タグ２３３を復号する。
Ｓ３３１Ｂの後、Ｓ３３２に進む。
【０１５９】
Ｓ３３２において、カテゴリ判定部３４０は、鍵判定値１９１とＳ３３１Ｂで得られた索引用タグ２３３の復号値とを比較する。
鍵判定値１９１と索引用タグ２３３の復号値とが同じ値である場合（ＹＥＳ）、Ｓ３４０Ｂに進む。
鍵判定値１９１と索引用タグ２３３の復号値とが異なる値である場合（ＮＯ）、Ｓ３２０Ｂに戻る。
【０１６０】
Ｓ３４０Ｂにおいて、データ登録部３２２は、Ｓ３３０Ｂで選択したカテゴリ別のユーザ秘密鍵に対応するカテゴリ別ＤＢ部３９１にシステム暗号文２３０を記憶する。
Ｓ３４０Ｂにより、データ登録処理は終了する。
【０１６１】
図２４は、実施の形態２におけるデータ検索端末１００のデータ検索要求処理を示すフローチャートである。
実施の形態２におけるデータ検索端末１００のデータ検索要求処理について、図２４に基づいて説明する。
以下に説明するＳ４１０からＳ４４１は、実施の形態１（図１３参照）で説明したＳ４１０からＳ４４１に対応する処理である。実施の形態１と一部が異なる処理には末尾に「Ｂ」を付記する。
【０１６２】
Ｓ４１０およびＳ４２０は実施の形態１と同じである。Ｓ４２０の後、Ｓ４２２Ｂに進む。
【０１６３】
Ｓ４２２Ｂにおいて、検索クエリ生成部１２２は、ＩＢＥマスタ公開鍵１４４とカテゴリ情報とを用いてＩＤベース暗号の暗号化アルゴリズムを実行し、鍵判定値１９１を暗号化した索引用タグ１７２を生成する。つまり、検索クエリ生成部１２２はカテゴリ情報をパラメータとして、ＩＢＥマスタ公開鍵１４４を用いて鍵判定値１９１を暗号化する。
Ｓ４２２Ｂの後、Ｓ４２３に進む。
【０１６４】
Ｓ４２３からＳ４４１は実施の形態１と同じである。Ｓ４４１により、データ検索要求処理は終了する。
【０１６５】
図２５は、実施の形態２におけるデータ検索サーバ３００のデータ検索処理を示すフローチャートである。
実施の形態２におけるデータ検索サーバ３００のデータ検索処理について、図２５に基づいて説明する。
以下に説明するＳ５１０からＳ５５０は、実施の形態１（図１４参照）で説明したＳ５１０からＳ５５０に対応する処理である。実施の形態１と一部が異なる処理には末尾に「Ｂ」を付記する。
【０１６６】
Ｓ５１０において、検索要求受信部３３１は、検索用トラップドア１７１と索引用タグ１７２とを含んだ検索クエリ１７０をデータ検索端末１００から受信する。
Ｓ５１０の後、Ｓ５２０Ｂに進む。
【０１６７】
Ｓ５２０Ｂにおいて、カテゴリ判定部３４０は、後述するＳ５３０Ｂで選択していない未選択のカテゴリ別のユーザ秘密鍵が検索サーバ記憶部３９０にあるか否かを判定する。
未選択のカテゴリ別のユーザ秘密鍵が有る場合（ＹＥＳ）、Ｓ５３０Ｂに進む。
未選択のカテゴリ別のユーザ秘密鍵が無い場合（ＮＯ）、Ｓ５２１に進む。Ｓ５２１において、データ検索部３３２は、検索用トラップドア１７１を用いて検索可能公開鍵暗号方式の検索アルゴリズムにより未分類ＤＢ部３９２を検索する。
【０１６８】
Ｓ５３０Ｂにおいて、カテゴリ判定部３４０は、検索サーバ記憶部３９０から未選択のカテゴリ別のユーザ秘密鍵を一つ選択する。
Ｓ５３０Ｂの後、Ｓ５３１Ｂに進む。
【０１６９】
Ｓ５３１Ｂにおいて、カテゴリ判定部３４０は、Ｓ５３０Ｂで選択したカテゴリ別のユーザ秘密鍵を用いて索引用タグ１７２を復号する。
Ｓ５３１Ｂの後、Ｓ５３２に進む。
【０１７０】
Ｓ５３２において、カテゴリ判定部３４０は、鍵判定値１９１とＳ５３１Ｂで得られた索引用タグ１７２の復号値とを比較する。
鍵判定値１９１と索引用タグ１７２の復号値とが同じ値である場合（ＹＥＳ）、Ｓ５４０Ｂに進む。
鍵判定値１９１と索引用タグ１７２の復号値とが異なる値である場合（ＮＯ）、Ｓ５２０Ｂに戻る。
【０１７１】
Ｓ５４０Ｂにおいて、データ検索部３３２は、Ｓ５３０Ｂで選択したカテゴリ別のユーザ秘密鍵に対応するカテゴリ別ＤＢ部３９１を、検索用トラップドア１７１を用いて検索可能暗号方式の検索アルゴリズムにより検索する。
Ｓ５４０Ｂの後、Ｓ５５０に進む。
【０１７２】
Ｓ５５０において、検索結果送信部３３３は、Ｓ５４０ＢまたはＳ５２１の検索処理でヒットしたデータ暗号文２３１を含んだ検索結果をデータ検索端末１００へ送信する。
Ｓ５５０により、データ検索処理は終了する。
【０１７３】
図２６は、実施の形態２におけるデータ検索端末１００のカテゴリ登録要求処理を示すフローチャートである。
実施の形態２におけるデータ検索端末１００のカテゴリ登録要求処理について、図２６に基づいて説明する。
以下に説明するＳ６０１からＳ６０３Ｂは、実施の形態１（図１５参照）で説明したＳ６０１からＳ６０３に対応する処理である。実施の形態１と一部が異なる処理には末尾に「Ｂ」を付記する。
【０１７４】
Ｓ６０１において、カテゴリ登録要求部１３０は検索者が指定したカテゴリ情報を入力する。
Ｓ６０１の後、Ｓ６０２Ｂに進む。
【０１７５】
Ｓ６０２Ｂにおいて、カテゴリ登録要求部１３０は、ＩＢＥマスタ秘密鍵１５４とカテゴリ情報とを用いてＩＤベース暗号のユーザ秘密鍵生成アルゴリズムを実行し、カテゴリ別のユーザ秘密鍵を生成する。
Ｓ６０２Ｂの後、Ｓ６０３Ｂに進む。
【０１７６】
Ｓ６０３Ｂにおいて、カテゴリ登録要求部１３０は、Ｓ６０２Ｂで生成したカテゴリ別のユーザ秘密鍵を含んだカテゴリ登録要求をデータ検索サーバ３００へ送信する。
Ｓ６０３Ｂにより、カテゴリ登録要求処理は終了する。
【０１７７】
図２７は、実施の形態２におけるデータ検索サーバ３００のカテゴリ登録処理を示すフローチャートである。
実施の形態２におけるデータ検索サーバ３００のカテゴリ登録処理について、図２７に基づいて説明する。
以下に説明するＳ６１０ＢからＳ６４４は、実施の形態１（図１６参照）で説明したＳ６１０からＳ６４４に対応する処理である。実施の形態１と一部が異なる処理には末尾に「Ｂ」を付記する。
【０１７８】
Ｓ６１０Ｂにおいて、カテゴリ用秘密鍵管理部３１０は、カテゴリ別のユーザ秘密鍵を含んだカテゴリ登録要求をデータ検索端末１００から受信する。
Ｓ６１０Ｂの後、Ｓ６２０に進む。
【０１７９】
Ｓ６２０において、カテゴリ用秘密鍵管理部３１０は新たなカテゴリ別ＤＢ部３９１を生成する。
Ｓ６２０の後、Ｓ６３０Ｂに進む。
【０１８０】
Ｓ６３０Ｂにおいて、カテゴリ用秘密鍵管理部３１０は、秘密鍵対応表３５０にカテゴリ別のユーザ秘密鍵と新たなカテゴリ別ＤＢ部３９１との対応関係を設定する。
Ｓ６３０Ｂの後、Ｓ６４０に進む。
【０１８１】
Ｓ６４０において、カテゴリ用秘密鍵管理部３１０は、後述するＳ６４１で選択していない未選択のシステム暗号文２３０が有るか否かを判定する。
未選択のシステム暗号文２３０が有る場合（ＹＥＳ）、Ｓ６４１に進む。
未選択のシステム暗号文２３０が無い場合（ＮＯ）、カテゴリ登録処理は終了する。
【０１８２】
Ｓ６４１において、カテゴリ用秘密鍵管理部３１０は、登録端末記憶部２９０から未選択のシステム暗号文２３０を一つ選択する。
Ｓ６４１の後、Ｓ６４２Ｂに進む。
【０１８３】
Ｓ６４２Ｂにおいて、カテゴリ用秘密鍵管理部３１０は、カテゴリ別のユーザ秘密鍵を用いて索引用タグ２３３を復号する。
Ｓ６４２Ｂの後、Ｓ６４３に進む。
【０１８４】
Ｓ６４３において、カテゴリ用秘密鍵管理部３１０は、鍵判定値１９１とＳ６４２Ｂで得られた索引用タグ２３３の復号値とを比較する。
鍵判定値１９１と索引用タグ２３３の復号値とが同じ値である場合（ＹＥＳ）、Ｓ６４４に進む。
鍵判定値１９１と索引用タグ２３３の復号値とが異なる値である場合（ＮＯ）、Ｓ６４０に戻る。
【０１８５】
Ｓ６４４において、カテゴリ用秘密鍵管理部３１０は、Ｓ６４１で選択したシステム暗号文２３０を未分類ＤＢ部３９２から新たなカテゴリ別ＤＢ部３９１へ移動する。
Ｓ６４４の後、Ｓ６４０に戻る。
【０１８６】
実施の形態２において、実施の形態１と同様に公開鍵対応表１６０を用いても構わない。この場合、データ検索端末１００およびデータ登録端末２００は以下のように動作する。
図２８は、実施の形態２における公開鍵対応表１６０を示す図である。図２８に示すように、公開鍵対応表１６０は、カテゴリ判定用公開鍵として用いるＩＤとカテゴリとを対応付けるデータである。
データ検索端末１００およびデータ登録端末２００は、カテゴリ情報を用いてカテゴリ別のユーザ公開鍵を生成する代わりに、公開鍵対応表１６０に示される複数のＩＤのうちカテゴリ情報が示すカテゴリに対応するＩＤを用いてカテゴリ別のユーザ公開鍵を生成する。
【０１８７】
実施の形態２におけるデータ検索システム９００により、例えば、以下のような効果を奏することができる。
（１）実施の形態１と同様な効果を得ることができる。特に、検索可能公開鍵暗号において検索の高速化を実現することができる。また、匿名性を有するＩＤベース暗号を用いることにより暗号文のカテゴリ情報を秘匿することができる。
（２）公開鍵対応表が不要なため、データ登録端末２００は公開鍵対応表を参照することなく直ちに索引用タグ２３３を生成することができる。但し、公開鍵対応表を用いても構わない。
（３）ＩＢＥマスタ公開鍵１４４およびＩＢＥマスタ秘密鍵１５４を用いることにより、カテゴリ数の増加や減少に直ちに対応することができる。
【０１８８】
実施の形態３．
ＩＤベース暗号の代わりに関数型暗号（ＦＥ：Ｆｕｎｃｔｉｏｎａｌ  Ｅｎｃｒｙｐｔｉｏｎ）を用いる形態について説明する。
【０１８９】
関数型暗号とは、パラメータｘを公開鍵として用いて、ユーザ秘密鍵を生成する際にパラメータｙを用いる暗号方式である。パラメータｘとパラメータｙとが所定の関係Ｒ（ｘ、ｙ）を満たす場合に暗号文を復号することができる。
パラメータｘ、パラメータｙおよび関係Ｒ（ｘ，ｙ）には様々な種類がある。例えば、属性秘匿性を有する関数型暗号の場合、ｘおよびｙは数値ベクトルであり、関係Ｒはｘとｙとの内積値が０となる関係であることが一般的である。このようなｘ、ｙ、Ｒ（ｘ，ｙ）を内積述語と呼ぶ。例えば、ｘ＝（１，３４，５）、ｙ＝（−２９，  １，  −１）のとき、ｘとｙの内積値は０になるので、このｘおよびｙは関係Ｒ（ｘ，ｙ）を満たすことになる。
属性秘匿性とは、暗号文を見てもどの属性を用いて暗号化したかわからない、という性質である（非特許文献８参照）。Ｋａｔｚ−Ｓａｈａｉ−Ｗａｔｅｒｓ内積述語暗号（ＫＳＷ−ＩＰＥ）（非特許文献７参照）や岡本−高島内積述語暗号（ＯＴ−ＩＰＥ）（非特許文献８参照）は、属性秘匿性を有する関数型暗号方式の一例である。Ｓａｈａｉ−ＷａｔｅｒｓファジイＩＤベース暗号（ＳＷ−ＦＩＤＥ）は属性秘匿性を有さない関数型暗号の一例である。
【０１９０】
以下、実施の形態１、２と異なる事項について主に説明する。説明を省略する事項については実施の形態１、２と同様である。
【０１９１】
データ検索システム９００の構成、およびデータ検索端末１００とデータ登録端末２００とデータ検索サーバ３００との機能構成は、実施の形態１と同様である（図１、２、６、８参照）。
【０１９２】
但し、データ検索システム９００は、以下の点で実施の形態１、２と異なる。
【０１９３】
データ検索システム９００は、関数型暗号を用いるため、ＩＤベース暗号を用いる場合（実施の形態２参照）と同様に公開鍵対応表１６０が不要である。このため、データ検索端末１００の公開鍵対応表生成部１１２も不要である。但し、実施の形態２（図２８参照）と同様にパラメータｘ（ＩＤの代わり）とカテゴリとを対応付ける公開鍵対応表１６０を用いても構わない。
【０１９４】
図２９は、実施の形態３におけるシステム公開鍵１４０とシステム秘密鍵１５０とを示す図である。
実施の形態３におけるシステム公開鍵１４０とシステム秘密鍵１５０とについて、図２９に基づいて説明する。
【０１９５】
システム公開鍵１４０は、実施の形態１（図３参照）で説明した複数のカテゴリ判定用公開鍵１４３の代わりに、一つのＦＥマスタ公開鍵１４５を有する。ＦＥマスタ公開鍵１４５は関数型暗号のマスタ公開鍵である。
システム秘密鍵１５０は、実施の形態１（図３参照）で説明した複数のカテゴリ判定用秘密鍵１５３の代わりに、一つのＦＥマスタ秘密鍵１５５を有する。ＦＥマスタ秘密鍵１５５は関数型暗号のマスタ秘密鍵である。
【０１９６】
データ検索端末１００のセットアップ処理は実施の形態２と同様である（図２１参照）。
但し、システム鍵生成部１１１はＩＢＥマスタ公開鍵１４４の代わりに関数型暗号のマスタ公開鍵を含んだシステム公開鍵１４０を生成し、ＩＢＥマスタ秘密鍵１５４の代わりに関数型暗号のマスタ秘密鍵を含んだシステム秘密鍵１５０を生成する（Ｓ１１０Ｂ）。
【０１９７】
データ登録端末２００のデータ登録要求処理は実施の形態２と同様である（図２２参照）。
但し、索引用タグ生成部２２４は、ＩＢＥマスタ公開鍵１４４の代わりに関数型暗号のマスタ公開鍵を用いて鍵判定値１９１を暗号化して索引用タグ２３３を生成する（Ｓ２４１Ｂ）。
例えば、索引用タグ生成部２２４は、マスタ公開鍵「ベクトルｘ＝（ＣＮ、１）」の「ＣＮ」にカテゴリ情報（カテゴリ名）を設定してユーザ公開鍵を生成し、生成したユーザ公開鍵を用いて鍵判定値１９１を暗号化して索引用タグ２３３を生成する。つまり、索引用タグ生成部２２４はカテゴリ情報を含んだパラメータｘを公開鍵として用いて索引用タグ２３３を生成する。
登録者は、関数型暗号の特性を活かして複雑な条件でカテゴリを指定してもよい。例えば、内積述語暗号を用いればＡＮＤ条件またはＯＲ条件を指定できることが知られている。また、属性秘匿性を有さない関数型暗号を用いればＮＯＴ条件を指定できることが知られている。索引用タグ生成部２２４は検索条件に応じた形式のベクトルｘを公開鍵として用いる。
【０１９８】
データ検索サーバ３００のデータ登録処理は実施の形態２と同様である（図２３参照）。
但し、カテゴリ別のユーザ秘密鍵はＩＤベース暗号ではなく関数型暗号のユーザ秘密鍵である。
【０１９９】
データ検索端末１００のデータ検索要求処理は実施の形態２と同様である（図２４参照）。
但し、検索クエリ生成部１２２は、上記の索引用タグ生成部２２４と同様に、ＩＢＥマスタ公開鍵１４４の代わりに関数型暗号のマスタ公開鍵を用いて関数型暗号方式の暗号アルゴリズムを実行し、鍵判定値１９１を暗号化して索引用タグ１７２を生成する（Ｓ４２２Ｂ）。
【０２００】
データ検索サーバ３００のデータ検索処理は実施の形態２と同様である（図２５参照）。
但し、カテゴリ別のユーザ秘密鍵はＩＤベース暗号ではなく関数型暗号のユーザ秘密鍵である。
【０２０１】
データ検索端末１００のカテゴリ登録要求処理は実施の形態２と同様である（図２６参照）。
但し、カテゴリ登録要求部１３０は、ＩＢＥマスタ秘密鍵１５４の代わりに関数型暗号のマスタ秘密鍵を用いてカテゴリ別のユーザ秘密鍵を生成する（Ｓ６０２Ｂ）。
例えば、カテゴリ登録要求部１３０は、関数型暗号のマスタ秘密鍵とベクトルｙ＝（−１、ＣＮ）とを入力にして関数型暗号方式のユーザ秘密鍵生成アルゴリズムを実行し、カテゴリ別のユーザ秘密鍵を生成する。ＣＮはカテゴリ情報（カテゴリ名）である。つまり、索引用タグ生成部２２４はカテゴリ情報を含んだパラメータｙを用いてカテゴリ別のユーザ秘密鍵を生成する。
検索者は、関数型暗号の特性を活かして複雑な条件でカテゴリを指定してもよい。例えば、内積述語暗号を用いればＡＮＤ条件またはＯＲ条件を指定できることが知られている。また、属性秘匿性を有さない関数型暗号を用いればＮＯＴ条件を指定できることが知られている。この場合、カテゴリ登録要求部１３０は条件に応じた形式のベクトルｙを用いる。
【０２０２】
データ検索サーバ３００のカテゴリ登録処理は実施の形態２と同様である（図２７参照）。
但し、カテゴリ別のユーザ秘密鍵はＩＤベース暗号ではなく関数型暗号のユーザ秘密鍵である。
【０２０３】
実施の形態３におけるデータ検索システム９００により、例えば、以下のような効果を奏することができる。
（１）実施の形態１、２と同様な効果を得ることができる。特に、検索可能公開鍵暗号において検索の高速化を実現することができる。また、属性秘匿性を有する関数型暗号を用いることにより暗号文のカテゴリ情報を秘匿することができる。
（２）ＩＤベース暗号を用いた場合のカテゴリの条件（ＩＤの一致）よりも柔軟な条件（ＡＮＤ条件、ＯＲ条件、ＮＯＴ条件など）でカテゴリを指定することができる。
【符号の説明】
【０２０４】
１００  データ検索端末、１１０  セットアップ処理部、１１１  システム鍵生成部、１１２  公開鍵対応表生成部、１１３  鍵情報公開部、１２０  検索要求処理部、１２１  検索キーワード入力部、１２２  検索クエリ生成部、１２３  検索要求部、１２４  検索結果出力部、１３０  カテゴリ登録要求部、１４０  システム公開鍵、１４１  データ用公開鍵、１４２  キーワード用公開鍵、１４３  カテゴリ判定用公開鍵、１４４  ＩＢＥマスタ公開鍵、１５０  システム秘密鍵、１５１  データ用秘密鍵、１５２  キーワード用秘密鍵、１５３  カテゴリ判定用秘密鍵、１５４  ＩＢＥマスタ秘密鍵、１６０，１６１  公開鍵対応表、１７０  検索クエリ、１７１  検索用トラップドア、１７２  索引用タグ、１９０  検索端末記憶部、１９１  鍵判定値、１９２  鍵判定値対応表、１９９  検索結果、２００  データ登録端末、２１０  公開情報取得部、２２０  データ登録要求処理部、２２１  登録情報入力部、２２２  データ暗号文生成部、２２３  キーワード暗号文生成部、２２４  索引用タグ生成部、２２５  データ登録要求部、２３０  システム暗号文、２３１  データ暗号文、２３２  キーワード暗号文、２３３  索引用タグ、２９０  登録端末記憶部、３００  データ検索サーバ、３１０  カテゴリ用秘密鍵管理部、３２０  データ登録処理部、３２１  登録要求受信部、３２２  データ登録部、３３０  データ検索処理部、３３１  検索要求受信部、３３２  データ検索部、３３３  検索結果送信部、３４０  カテゴリ判定部、３５０  秘密鍵対応表、３９０  検索サーバ記憶部、３９１  カテゴリ別ＤＢ部、３９２  未分類ＤＢ部、９００  データ検索システム、９０１  ＣＰＵ、９０２  バス、９０３  ＲＯＭ、９０４  ＲＡＭ、９０５  通信ボード、９０９  ネットワーク、９１１  ディスプレイ、９１２  キーボード、９１３  マウス、９１４  ドライブ、９２０  磁気ディスク装置、９２１  ＯＳ、９２２  プログラム群、９２３  ファイル群。
【図１】
0005606642.tif 000002
【図２】
0005606642.tif 000003
【図３】
0005606642.tif 000004
【図４】
0005606642.tif 000005
【図５】
0005606642.tif 000006
【図６】
0005606642.tif 000007
【図７】
0005606642.tif 000008
【図８】
0005606642.tif 000009
【図９】
0005606642.tif 000010
【図１０】
0005606642.tif 000011
【図１１】
0005606642.tif 000012
【図１２】
0005606642.tif 000013
【図１３】
0005606642.tif 000014
【図１４】
0005606642.tif 000015
【図１５】
0005606642.tif 000016
【図１６】
0005606642.tif 000017
【図１７】
0005606642.tif 000018
【図１８】
0005606642.tif 000019
【図１９】
0005606642.tif 000020
【図２０】
0005606642.tif 000021
【図２１】
0005606642.tif 000022
【図２２】
0005606642.tif 000023
【図２３】
0005606642.tif 000024
【図２４】
0005606642.tif 000025
【図２５】
0005606642.tif 000026
【図２６】
0005606642.tif 000027
【図２７】
0005606642.tif 000028
【図２８】
0005606642.tif 000029
【図２９】
0005606642.tif 000030