(57)【特許請求の範囲】
【請求項１】
複数のユーザに利用される複数の情報処理装置と、
ユーザの要求に基づいて暗号化データを記憶し、ユーザの要求に基づいて記憶している暗号化データの検索を行うサーバ装置と、
前記サーバ装置に対して秘密にしている鍵を更新イベントの発生時に新たな世代値を設けて更新し、更新イベント発生時を含む所定の鍵発行タイミングにおいてユーザに鍵を発行する管理装置を有し、
前記管理装置は、
利用が許可される世代範囲が許可世代範囲として設定される鍵を生成し、
ユーザごとに鍵の利用が許可される最も前の世代を利用開始世代として指定し、
鍵発行タイミングにおいて、ユーザごとに、最新世代の鍵であって、ユーザに指定されている利用開始世代から当該最新世代までが許可世代範囲として設定されている鍵を発行し、
各情報処理装置は、
最新世代の鍵を受領する度に、受領した最新世代の鍵を記憶し、
ユーザから暗号化データの格納指示があった際に、暗号化データの検索に用いられるインデックス情報と、前記ユーザの格納指示時点での最新世代の鍵の世代値と、暗号化データとを対応付けて格納するよう前記サーバ装置に要求し、
ユーザから暗号化データの検索指示があった際に、前記ユーザの検索指示時点での最新世代の鍵を用いて、許可世代範囲である利用開始世代から当該最新世代までのｎ（ｎ≧１）世代の各世代値が暗号化されているｎ個の暗号化世代情報が集約されている集約情報を生成し、生成した集約情報を含む検索要求を前記サーバ装置に送信し、
前記サーバ装置は、
情報処理装置からの格納要求を受領した場合に、インデックス情報と、鍵の世代値と、暗号化データとを対応付けて記憶し、
情報処理装置からの検索要求を受信した場合に、受信した検索要求に含まれる前記集約情報に対して所定の演算を行い、前記集約情報からｎ個の暗号化世代情報を抽出し、暗号化世代情報ごとに、暗号化世代情報が対象としている世代値と共通する世代値を対象としているインデックス情報に対応付けられている暗号化データであって所定の条件を満たす暗号化データを抽出することを特徴とする情報処理システム。
【請求項２】
各情報処理装置は、
ユーザから暗号化データの格納指示があった際に、前記ユーザが指定する検索条件を入力するとともに、前記ユーザの格納指示時点での最新世代の鍵を用いて前記検索条件を暗号化し、暗号化により得られた値をインデックス情報とし、インデックス情報と、前記ユーザの格納指示時点での最新世代の鍵の世代値と、暗号化データとを対応付けて格納するよう前記サーバ装置に要求し、
ユーザから暗号化データの検索指示があった際に、前記ユーザが指定する検索条件を入力するとともに、前記ユーザの検索指示時点での最新世代の鍵と前記検索条件を用いて、許可世代範囲である利用開始世代から当該最新世代までのｎ世代の各世代値と前記検索条件が暗号化されているｎ個の暗号化世代情報が集約されている集約情報を生成し、生成した集約情報を含む検索要求を前記サーバ装置に送信し、
前記サーバ装置は、
情報処理装置からの検索要求を受信した場合に、受信した検索要求に含まれる前記集約情報に対して所定の演算を行い、前記集約情報からｎ個の暗号化世代情報を抽出し、暗号化世代情報ごとに、暗号化世代情報が対象としている世代値と共通し、暗号化世代情報と共通する値のインデックス情報を選択し、選択したインデックス情報に対応付けられている暗号化データを抽出することを特徴とする請求項１に記載の情報処理システム。
【請求項３】
各情報処理装置は、
ユーザから暗号化データの格納指示があった際に、前記ユーザが指定する検索条件と格納対象の暗号化データの識別子を入力し、前記ユーザの格納指示時点での最新世代の鍵を用いて前記検索条件を暗号化するとともに、暗号化された検索条件を前記暗号化データの識別子を用いて再暗号化し、再暗号化により得られた値をインデックス情報とし、インデックス情報と、前記ユーザの格納指示時点での最新世代の鍵の世代値と、暗号化データと、前記暗号化データの識別子とを対応付けて格納するよう前記サーバ装置に要求し、
ユーザから暗号化データの検索指示があった際に、前記ユーザが指定する検索条件を入力するとともに、前記ユーザの検索指示時点での最新世代の鍵と前記検索条件を用いて、許可世代範囲である利用開始世代から当該最新世代までのｎ世代の各世代値と前記検索条件が暗号化されているｎ個の暗号化世代情報が集約されている集約情報を生成し、生成した集約情報を含む検索要求を前記サーバ装置に送信し、
前記サーバ装置は、
情報処理装置からの格納要求を受領した場合に、インデックス情報と、鍵の世代値と、暗号化データと、前記暗号化データの識別子とを対応付けて記憶し、
情報処理装置からの検索要求を受信した場合に、受信した検索要求に含まれる前記集約情報に対して所定の演算を行い、前記集約情報からｎ個の暗号化世代情報を抽出し、暗号化世代情報ごとに、各インデックス情報に対応付けられている識別子を用いて所定の演算を行い、暗号化世代情報が対象としている世代値と共通し、演算により得られた値と共通する値のインデックス情報を選択し、選択したインデックス情報に対応付けられている暗号化データを抽出することを特徴とする請求項１に記載の情報処理システム。
【請求項４】
前記管理装置は、
生成済みの鍵に対して第１の関数及び第２の関数のいずれかを適用して、各鍵間に連続性を持たせながら、前記生成済みの鍵とは別の許可世代範囲が設定されている鍵を生成し、
前記サーバ装置は、
情報処理装置からの検索要求を受信した場合に、受信した検索要求に含まれる前記集約情報に対して前記第１の関数と前記第２の関数を適用した所定の演算を行い、前記集約情報からｎ個の暗号化世代情報を抽出することを特徴とする請求項１〜３のいずれかに記載の情報処理システム。
【請求項５】
前記管理装置は、
最終世代の世代値を決定し、第１世代から最終世代までを許可世代範囲とする鍵を初期鍵として生成し、
前記初期鍵に前記第１の関数を適用して、許可世代範囲の開始世代が前記初期鍵の開始世代と共通し終了世代が前記初期鍵の終了世代の１つ前の世代となる新たな鍵を生成し、生成した鍵に前記第１の関数を適用して、許可世代範囲の開始世代が当該生成済みの鍵の開始世代と共通し終了世代が当該生成済みの鍵の終了世代の１つ前の世代となる新たな鍵を生成し、
前記初期鍵に前記第２の関数を適用して、許可世代範囲の終了世代が前記初期鍵の終了世代と共通し開始世代が前記初期鍵の開始世代の１つ後の世代となる新たな鍵を生成し、生成した鍵に前記第２の関数を適用して、許可世代範囲の終了世代が当該生成済みの鍵の終了世代と共通し開始世代が当該生成済みの鍵の開始世代の１つ後の世代となる新たな鍵を生成し、
生成した鍵に前記第１の関数及び前記第２の関数のいずれかを適用して新たな鍵を生成する動作を繰り返して、許容世代範囲の全パターンに対応する複数の鍵を生成し、生成した複数の鍵を記憶し、
鍵発行時に、ユーザごとに、利用開始世代から鍵発行時における最新世代までの世代範囲に対応する鍵を、記憶している前記複数の鍵の中から抽出し、抽出した鍵を発行することを特徴とする請求項４に記載の情報処理システム。
【請求項６】
前記管理装置は、
予め、第１世代のみを許可世代範囲とする鍵を初期鍵として生成し、
鍵発行時に、ユーザごとに、利用開始世代から鍵発行時における最新世代までの世代範囲に対応させて、初期鍵又は前記初期鍵から派生する鍵を生成元鍵とし、前記生成元鍵に前記第１の関数を適用して許可世代範囲の開始世代が前記生成元鍵の開始世代と共通し終了世代が前記生成元鍵の終了世代の１つ後の世代となる新たな鍵を生成し、または、前記生成元鍵に前記第２の関数を適用して許可世代範囲の終了世代が前記生成元鍵の終了世代と共通し開始世代が前記生成元鍵の開始世代の１つ後の世代となる新たな鍵を生成し、生成した鍵をユーザに発行することを特徴とする請求項４に記載の情報処理システム。
【請求項７】
前記管理装置は、
十分大きな素数であるｐ１及びｐ２を選び、Ｎ＝ｐ１×ｐ２とし、ｅ１及びｅ２としてＺＮ＊から（ｐ１−１）（ｐ２−１）と互いに素な数をランダムに選択した場合に、
前記第１の関数を、Ｆ１（ｘ）＝ｘｅ１  ｍｏｄ  Ｎ  とし、
前記第２の関数を、Ｆ２（ｘ）＝ｘｅ２  ｍｏｄ  Ｎ  とし、
（ｍｏｄはモジュロ演算子を表し、ＺＮ＊は０からＮ−１の整数の中でＮと互いに素である整数の集合を表す）（Ｆ１（ｘ）とＦ２（ｘ）は、互いに可換である）
最終世代の世代値をｑとし、第１世代から最終世代までを許可世代範囲とする初期鍵をｋ１，ｑとし、初期鍵ｋ１，ｑをＺＮ＊からランダムに選択し、許可世代範囲の開始世代がｉ世代であり終了世代がｊ世代である鍵をｋｉ，ｊとした場合に、
ｋｉ，ｊ−１＝Ｆ１（ｋｉ，ｊ）
ｋｉ＋１，ｊ＝Ｆ２（ｋｉ，ｊ）
による演算を繰り返して、許容世代範囲の全パターンに対応する複数の鍵ｋ１，１からｋｑ，ｑを生成することを特徴とする請求項５に記載の情報処理システム。
【請求項８】
前記管理装置は、
各情報処理装置において利用される関数を、
Ｇ（ｘ，ｙ）＝ｘｙ  ｍｏｄ  Ｎ  とし、
（Ｇ（ｘ，ｙ）は、Ｆ１（ｘ）及びＦ２（ｘ）と互いに可換である）
各情報処理装置は、
ユーザから暗号化データの格納指示があった際に、前記ユーザが指定する検索条件を入力し、
入力した検索条件をｗとし、格納指示時点での最新世代の鍵であって利用開始世代がｓ世代であり当該最新世代がｔ世代である鍵をｋｓ，ｔとし、当該最新世代のみを許可世代範囲とする鍵をｋｔ，ｔとし、当該最新世代の鍵の世代値と前記検索条件の暗号値をｔｄとした場合に、
ｋｔ，ｔ＝Ｆ２ｔ−ｓ（ｋｓ，ｔ）
ｔｄ＝Ｇ（ｋｔ，ｔ，ｗ）
（Ｆ２ｔ−ｓはＦ２をｔ−ｓ回適用することを表す。以下においても同様）
により、暗号値ｔｄを生成し、
ユーザから暗号化データの検索指示があった際に、前記ユーザが指定する検索条件を入力し、
入力した検索条件をｗとし、検索指示時点での最新世代の鍵であって利用開始世代がｓ世代であり当該最新世代がｔ世代である鍵をｋｓ，ｔとし、ｓ世代からｔ世代に対応する暗号化世代情報を集約する集約情報をｔｄｓ，ｔとした場合に、
ｔｄｓ，ｔ＝Ｇ（ｋｓ，ｔ，ｗ）
により、集約情報ｔｄｓ，ｔを生成し、
前記サーバ装置は、
ｔｄｉ，ｉ＝Ｆ１ｔ−ｉ（Ｆ２ｉ−ｓ（ｔｄｓ，ｔ））  （ｓ≦ｉ≦ｔ）
により、集約情報ｔｄｓ，ｔから、ｓ世代からｔ世代までの暗号化世代情報ｔｄｓ，ｓからｔｄｔ，ｔを抽出することを特徴とする請求項７に記載の情報処理システム。
【請求項９】
各情報処理装置は、
ユーザから暗号化データの格納指示があった際に、前記ユーザが指定する検索条件とともに格納対象の暗号化データの識別子を入力し、
入力した識別子をｉｄとし、Ｈ（ｘ，ｙ）を一方向性関数とし、ｃを暗号化値ｔｄの再暗号化値とした場合に、
ｃ＝Ｈ（ｉｄ，ｔｄ）
により、再暗号化値ｃを生成し、生成した再暗号化値ｃをインデックス情報とし、インデックス情報と、前記ユーザの格納指示時点での最新世代の鍵の世代値と、前記暗号化データと、前記暗号化データの識別子を対応付けて格納するよう前記サーバ装置に要求し、
前記サーバ装置は、
情報処理装置からの格納要求を受領した場合に、インデックス情報と、鍵の世代値と、暗号化データと、前記暗号化データの識別子とを対応付けて記憶し、
情報処理装置からの検索要求を受信した際に、集約情報ｔｄｓ，ｔからｓ世代からｔ世代に対応する暗号化世代情報ｔｄｓ，ｓからｔｄｔ，ｔを抽出し、
各インデックス情報に対応付けられている識別子をｉｄとし、各暗号化世代情報をｔｄｊ，ｊとした場合に、暗号化世代情報ｔｄｊ，ｊごとに、
ｃ＝Ｈ（ｉｄ，ｔｄｊ，ｊ）
を計算し、
演算により得られた値ｃと共通する値のインデックス情報を選択し、選択したインデックス情報に対応付けられている暗号化データを抽出することを特徴とする請求項８に記載の情報処理システム。
【請求項１０】
各情報処理装置は、
所定のグループに属するユーザに利用され、
前記管理装置は、
前記グループからのユーザの脱退及び所定の条件に合致する新たなユーザの前記グループへの加入を更新イベントとし、
ユーザの脱退又はユーザの加入により更新イベントが発生した場合に、前記グループに所属しているユーザごとに、現在利用されている鍵の次の世代の鍵であって、許可世代範囲を利用開始世代から当該次の世代までの範囲とする鍵を発行することを特徴とする請求項１〜９のいずれかに記載の情報処理システム。
【請求項１１】
前記管理装置は、
前記グループに新たに加入するユーザの利用開始世代が当該ユーザ加入後の最新世代である場合に、当該ユーザの加入を更新イベントとし、
当該ユーザの加入により、前記グループに所属しているユーザごとに、現在利用されている鍵の次の世代の鍵であって、許可世代範囲を利用開始世代から当該次の世代までの範囲とする鍵を発行し、前記グループに新たに加入するユーザには、当該次の世代のみを許可世代範囲とする鍵を発行し、
前記グループに新たに加入するユーザの利用開始世代が当該ユーザ加入後の最新世代よりも前の世代である場合は、当該ユーザの加入を更新イベントとせず、
前記グループに所属しているユーザには新たな鍵の発行を行わず、前記グループに新たに加入するユーザに、当該ユーザに指定される利用開始世代から現在の最新世代までを許可世代範囲とする鍵を発行することを特徴とする請求項１０に記載の情報処理システム。
【請求項１２】
複数のユーザに利用される複数の情報処理装置と、
ユーザの要求に基づいて暗号化データを記憶し、ユーザの要求に基づいて記憶している暗号化データの検索を行うサーバ装置と、
前記サーバ装置に対して秘密にしている鍵を更新イベントの発生時に新たな世代値を設けて更新し、更新イベント発生時を含む所定の鍵発行タイミングにおいてユーザに鍵を発行する管理装置とを有し、
前記管理装置は、
いずれのユーザ及び情報処理装置に対しても秘密にしている秘密パラメータを前記サーバ装置にのみ通知し、
各世代の鍵を、前記秘密パラメータを用いて生成し、
ユーザごとに鍵の利用が許可される最も前の世代を利用開始世代として指定し、
ユーザごとに、
初回の鍵発行時に、鍵発行時における最新世代の鍵と、利用開始世代から当該最新世代までの鍵を合成して生成した合成鍵を発行し、
２回目以降の鍵発行時は、各回時点での最新世代の鍵を発行し、
各情報処理装置は、
ユーザに対する初回の鍵発行時に、最新世代の鍵と合成鍵を受領し、受領した最新世代の鍵と合成鍵を記憶し、
ユーザに対する２回以降の鍵発行では、鍵発行の度に、最新世代の鍵を受領し、受領した最新世代の鍵と記憶している合成鍵を合成して新たな合成鍵を生成し、受領した最新世代の鍵と生成した新たな合成鍵を記憶し、
ユーザから暗号化データの格納指示があった際に、暗号化データの検索に用いられるインデックス情報と、前記ユーザの格納指示時点での最新世代の鍵の世代値と、暗号化データとを対応付けて格納するよう前記サーバ装置に要求し、
ユーザから暗号化データの検索指示があった際に、前記ユーザの検索指示時点での最新世代の鍵を用いて、当該最新世代の世代値が暗号化されている暗号化最新世代情報を生成し、検索指示時点での合成鍵を用いて、前記ユーザに指定されている利用開始世代から検索指示時点での最新世代までのｎ（ｎ≧１）世代の各世代値が暗号化されているｎ個の暗号化世代情報が集約されている集約情報を生成し、生成した暗号化最新世代情報と集約情報を含む検索要求を前記サーバ装置に送信し、
前記サーバ装置は、
前記管理装置から通知された前記秘密パラメータを記憶し、
情報処理装置からの格納要求を受領した場合に、インデックス情報と、鍵の世代値と、暗号化データとを対応付けて記憶し、
情報処理装置から検索要求を受信した場合に、受信した検索要求に含まれる暗号化最新世代情報と前記秘密パラメータを用いて、１つ前の世代の世代値が暗号化されている暗号化世代情報を算出し、以降、算出された暗号化世代情報と前記秘密パラメータを用いて１つ前の世代値が暗号化されている暗号化世代情報を算出する処理を繰り返し、検索要求元ユーザの利用開始世代の世代値が暗号化されている暗号化世代情報を算出し、算出した利用開始世代から最新世代の１つ前の世代までの暗号化世代情報と前記暗号化最新世代情報と、前記集約情報において集約されているｎ個の暗号化世代情報が一致するか否かを判定し、暗号化世代情報が一致する場合に、暗号化世代情報ごとに、暗号化世代情報が対象としている世代値と共通する世代値を対象としているインデックス情報に対応付けられている暗号化データであって所定の条件を満たす暗号化データを抽出することを特徴とする情報処理システム。
【請求項１３】
各情報処理装置は、
ユーザから暗号化データの格納指示があった際に、前記ユーザが指定する検索条件を入力するとともに、前記ユーザの格納指示時点での最新世代の鍵を用いて前記検索条件を暗号化し、暗号化により得られた値をインデックス情報とし、インデックス情報と、前記ユーザの格納指示時点での最新世代の鍵と、暗号化データとを対応付けて格納するよう前記サーバ装置に要求し、
ユーザから暗号化データの検索指示があった際に、前記ユーザが指定する検索条件を入力するとともに、前記ユーザの検索指示時点での最新世代の鍵と前記検索条件を用いて、当該最新世代の世代値と前記検索条件が暗号化されている暗号化最新世代情報を生成し、検索指示時点での合成鍵と前記検索条件を用いて、前記ユーザに指定されている利用開始世代から検索指示時点での最新世代までのｎ世代の各世代値と前記検索条件が暗号化されているｎ個の暗号化世代情報が集約されている集約情報を生成し、生成した暗号化最新世代情報と集約情報を含む検索要求を前記サーバ装置に送信し、
前記サーバ装置は、
暗号化世代情報が一致する場合に、暗号化世代情報ごとに、暗号化世代情報が対象としている世代値と共通する世代値を対象とし、暗号化世代情報と共通する値のインデックス情報を選択し、選択したインデックス情報に対応付けられている暗号化データを抽出することを特徴とする請求項１２に記載の情報処理システム。
【請求項１４】
各情報処理装置は、
ユーザから暗号化データの格納指示があった際に、前記ユーザが指定する検索条件と格納対象の暗号化データの識別子を入力し、前記ユーザの格納指示時点での最新世代の鍵を用いて前記検索条件を暗号化するとともに、暗号化された検索条件を前記暗号化データの識別子を用いて再暗号化し、再暗号化により得られた値をインデックス情報とし、インデックス情報と、前記ユーザの格納指示時点での最新世代の鍵と、暗号化データと、前記暗号化データの識別子を対応付けて格納するよう前記サーバ装置に要求し、
ユーザから暗号化データの検索指示があった際に、前記ユーザが指定する検索条件を入力するとともに、前記ユーザの検索指示時点での最新世代の鍵と前記検索条件を用いて、当該最新世代の世代値と前記検索条件が暗号化されている暗号化最新世代情報を生成し、検索指示時点での合成鍵と前記検索条件を用いて、前記ユーザに指定されている利用開始世代から検索指示時点での最新世代までのｎ世代の各世代値と前記検索条件が暗号化されているｎ個の暗号化世代情報が集約されている集約情報を生成し、生成した暗号化最新世代情報と集約情報を含む検索要求を前記サーバ装置に送信し、
前記サーバ装置は、
情報処理装置からの格納要求を受領した場合に、インデックス情報と、鍵の世代値と、暗号化データと、前記暗号化データの識別子を対応付けて記憶し、
暗号化世代情報が一致する場合に、暗号化世代情報ごとに、各インデックス情報に対応付けられている識別子を用いて所定の演算を行い、暗号化世代情報が対象としている世代値と共通する世代値を対象とし、演算により得られた値と共通する値のインデックス情報を選択し、選択したインデックス情報に対応付けられている暗号化データを抽出することを特徴とする請求項１２に記載の情報処理システム。
【請求項１５】
前記管理装置は、
ユーザに対する初回の鍵発行時に、利用開始世代から当該最新世代までの鍵の積を計算し、計算した鍵の積を合成鍵として発行し、
各情報処理装置は、
ユーザに対する２回以降の鍵発行では、鍵発行の度に、最新世代の鍵を受領し、受領した最新世代の鍵と記憶している合成鍵との積を計算し、計算した鍵の積を新たな合成鍵とすることを特徴とする請求項１２〜１４のいずれかに記載の情報処理システム。
【請求項１６】
前記管理装置は、
生成済みの鍵に対して所定の鍵生成関数を適用して、各鍵間に連続性を持たせながら、前記生成済みの鍵とは別の世代の鍵を生成し、
前記サーバ装置は、
情報処理装置からの検索要求を受信した場合に、前記暗号化最新世代情報と前記秘密パラメータに対して前記鍵生成関数を適用して、１つ前の世代の世代値が暗号化されている暗号化世代情報を算出し、以降、算出された暗号化世代情報と前記秘密パラメータに対して前記鍵生成関数を適用して１つ前の世代値が暗号化されている暗号化世代情報を算出する処理を繰り返すことを特徴とする請求項１２〜１５のいずれかに記載の情報処理システム。
【請求項１７】
前記管理装置は、
最終世代の世代値を決定し、最終世代の鍵を初期鍵として生成し、最終世代の鍵と前記秘密パラメータに対して前記鍵生成関数を適用して、最終世代の１つ前の世代の新たな鍵を生成し、生成した鍵と前記秘密パラメータに対して前記鍵生成関数を適用して更に１つ前の世代の鍵を生成し、以降、新たに生成した鍵と前記秘密パラメータに対して前記鍵生成関数を適用する動作を繰り返して、第１世代から最終世代の鍵を生成し、生成した第１世代から最終世代の鍵を記憶し、
鍵発行時に、最新世代に該当する鍵を、記憶している鍵の中から抽出し、抽出した鍵を発行することを特徴とする請求項１６に記載の情報処理システム。
【請求項１８】
前記管理装置は、
予め、第１世代の鍵を生成し、
鍵発行時に、鍵発行時点での最新世代に対応させて、前記第１世代の鍵又は前記第１世代の鍵から派生する鍵を生成元鍵とし、前記生成元鍵と前記秘密パラメータに対して前記鍵生成関数を適用して、前記生成元鍵の１つ後の世代の新たな鍵を最新世代の鍵として生成し、生成した最新世代の鍵をユーザに発行することを特徴とする請求項１６に記載の情報処理システム
【請求項１９】
前記管理装置は、
十分大きな素数であるｐを選んだ場合に、
自装置及び前記サーバ装置が用いる関数を、Ｆ（ｘ，ｙ）＝ｘｙ  ｍｏｄ  ｐ  とし、
各情報処理装置が用いる関数を、Ｇ（ｘ，ｙ）＝ｘｙ  ｍｏｄ  ｐ  とし、
（ｍｏｄはモジュロ演算子を表す）（Ｆ１（ｘ，ｙ）とＧ（ｘ，ｙ）は、互いに可換である）
このとき、Ｇは以下の準同型性を持ち、
Ｇ（ｘ１ｘ２，ｙ）＝Ｇ（ｘ１，ｙ）Ｇ（ｘ２，ｙ）という関係を持ち、
秘密パラメータをαとし、秘密パラメータαを巡回群Ｚｐ＊から、（ｐ−１）と互いに素となるようランダムに選択し、
最終世代の世代値をｑとし、最終世代の鍵である初期鍵をｋｑとし、初期鍵ｋｑをＺｐ＊の生成元からランダムに選択し、ｉ世代目の鍵をｋｉとした場合に、
ｋｉ−１＝Ｆ（ｋｉ，α）  （１≦ｉ＜ｑ）
による演算を繰り返して、第１世代から最終世代までの鍵ｋ１からｋｑを生成し、
各情報処理装置は、
ユーザから暗号化データの格納指示があった際に、前記ユーザが指定する検索条件を入力し、
入力した検索条件をｗとし、格納指示時点での最新世代の鍵をｋｔとし、当該最新世代の鍵の世代値と前記検索条件の暗号値をｔｄとした場合に、
ｔｄ＝Ｇ（ｋｔ，ｗ）
により、暗号値ｔｄを生成し、
ユーザから暗号化データの検索指示があった際に、前記ユーザが指定する検索条件を入力し、
入力した検索条件をｗとし、検索指示時点での最新世代の鍵をｋｔとし、ｓ世代目の鍵からｔ世代目の鍵までを合成した検索指示時点での合成鍵をｋｓ，ｔとし、暗号化最新世代情報をｔｄｔとし、集約情報をｔｄｓ，ｔとした場合に、
ｔｄｔ＝Ｇ（ｋｔ，ｗ）
ｔｄｓ，ｔ＝Ｇ（ｋｓ，ｔ，ｗ）
により、暗号化最新世代情報をｔｄｔと集約情報ｔｄｓ，ｔを生成し、
前記サーバ装置は、
ｔｄｉ−１＝Ｆ（ｔｄｉ，α）
により、暗号化最新世代情報ｔｄｔから、ｓ世代からｔ−１世代までを対象とする暗号化世代情報ｔｄｓからｔｄｔ−１を算出することを特徴とする請求項１７に記載の情報処理システム。
【請求項２０】
各情報処理装置は、
ユーザから暗号化データの格納指示があった際に、前記ユーザが指定する検索条件とともに格納対象の暗号化データの識別子を入力し、
入力した識別子をｉｄとし、Ｈ（ｘ，ｙ）を一方向性関数とし、ｃを暗号化値ｔｄの再暗号化値とした場合に、
ｃ＝Ｈ（ｉｄ，ｔｄ）
により、再暗号化値ｃを生成し、生成した再暗号化値ｃをインデックス情報とし、インデックス情報と、前記ユーザの格納指示時点での最新世代の鍵の世代値と、前記暗号化データと、前記暗号化データの識別子とを対応付けて格納するよう前記サーバ装置に要求し、
前記サーバ装置は、
情報処理装置からの格納要求を受領した場合に、インデックス情報と、鍵の世代値と、暗号化データと、前記暗号化データの識別子とを対応付けて記憶し、
情報処理装置からの検索要求を受信した際に、暗号化世代情報が一致する場合に、
各インデックス情報に対応付けられている識別子をｉｄとし、各暗号化世代情報をｔｄｊとした場合に、暗号化世代情報ｔｄｊごとに、
ｃ＝Ｈ（ｉｄ，ｔｄｊ）
を計算し、
演算により得られた値ｃと共通する値のインデックス情報を選択し、選択したインデックス情報に対応付けられている暗号化データを抽出することを特徴とする請求項１９に記載の情報処理システム。
【請求項２１】
各情報処理装置は、
所定のグループに属するユーザに利用され、
前記管理装置は、
前記グループからのユーザの脱退及び所定の条件に合致する新たなユーザの前記グループへの加入を更新イベントとし、
ユーザの脱退又はユーザの加入により更新イベントが発生した場合に、前記グループに所属しているユーザに、現在利用されている鍵の次の世代の鍵を最新世代の鍵として発行することを特徴とする請求項１２〜２０のいずれかに記載の情報処理システム。
【請求項２２】
前記管理装置は、
前記グループに新たに加入するユーザの利用開始世代が当該ユーザ加入後の最新世代である場合に、当該ユーザの加入を更新イベントとし、
当該ユーザの加入により、前記グループに所属しているユーザに、現在利用されている鍵の次の世代の鍵を最新世代の鍵として発行し、前記グループに新たに加入するユーザには、当該次の世代の鍵を最新世代の鍵及び合成鍵として発行し、
前記グループに新たに加入するユーザの利用開始世代が当該ユーザ加入後の最新世代よりも前の世代である場合は、当該ユーザの加入を更新イベントとせず、
前記グループに所属しているユーザには新たな鍵の発行を行わず、前記グループに新たに加入するユーザに、現在の最新世代の鍵を発行するとともに、当該ユーザに指定される利用開始世代の鍵から現在の最新世代の鍵までを合成した合成鍵を発行することを特徴とする請求項２１に記載の情報処理システム。
【請求項２３】
複数のユーザに利用される複数の情報処理装置と通信可能であり、ユーザの要求に基づいて暗号化データを記憶し、ユーザの要求に基づいて記憶している暗号化データの検索を行うサーバ装置と、
前記サーバ装置に対して秘密にしている鍵を更新イベントの発生時に新たな世代値を設けて更新し、更新イベント発生時を含む所定の鍵発行タイミングにおいてユーザに鍵を発行する管理装置とを有し、
前記管理装置は、
ユーザのカテゴリーとして、所定のグループに所属し前記サーバ装置の暗号化データに対する検索が許容される所属ユーザと、前記グループから脱退し前記サーバ装置の暗号化データに対する検索が禁止される禁止ユーザと、前記グループから脱退したが脱退前に前記サーバ装置に格納された暗号化データに対しては検索が許容される限定ユーザが設けられ、
前記グループからのユーザの脱退を前記更新イベントの一つとし、
鍵の世代値は、前記禁止ユーザが発生した際に値が更新される禁止ユーザ対応値と前記限定ユーザが発生した際に値が更新される限定ユーザ対応値を構成要素とし、
いずれかのユーザが前記グループから脱退し、脱退したユーザが前記禁止ユーザに該当する場合に、前記所属ユーザに対しては所属ユーザ向けの最新世代の鍵を発行し、前記脱退ユーザに対しては脱退ユーザ向けの最新世代の鍵を発行し、前記所属ユーザ向けの最新世代の鍵は、前記禁止ユーザ対応値が更新された値となり前記限定ユーザ対応値が当該脱退前の値のままである世代値が設定されている鍵であり、前記限定ユーザ向けの最新世代の鍵は、前記禁止ユーザ対応値が更新された値となり前記限定ユーザ対応値が当該限定ユーザの脱退時点の値のままである世代値が設定されている鍵であり、
いずれかのユーザが前記グループから脱退し、脱退したユーザが前記限定ユーザに該当する場合に、前記所属ユーザに対して、前記限定ユーザ対応値が更新された値となり前記禁止ユーザ対応値が当該脱退前の値のままである世代値が設定されている最新世代の鍵を発行し、
前記サーバ装置は、
情報処理装置から、暗号化データの検索に用いられるインデックス情報と、前記情報処理装置のユーザの格納要求時点での最新世代の鍵に設定されている禁止ユーザ対応値及び限定ユーザ対応値と、暗号化データとが含まれる格納要求を受領した場合に、前記インデックス情報と、前記禁止ユーザ対応値及び限定ユーザ対応値と、前記暗号化データとを対応付けて記憶し、
情報処理装置から、前記情報処理装置のユーザの検索要求時点での最新世代の鍵に設定されている禁止ユーザ対応値及び限定ユーザ対応値が暗号化されている暗号化世代情報を含む暗号化データの検索要求を受信した場合に、
前記暗号化世代情報より抽出される禁止ユーザ対応値が実際の最新世代の禁止ユーザ対応値と一致しない場合は暗号化データの検索が行われず、前記暗号化世代情報より抽出される禁止ユーザ対応値が実際の最新世代の禁止ユーザ対応値と一致する場合は、前記暗号化世代情報から抽出される限定ユーザ対応値以前の限定ユーザ対応値のインデックス情報が対応付けられている暗号化データに限定した検索が行われることを特徴とする情報処理システム。
【請求項２４】
前記管理装置は、
所属ユーザごとに、鍵の利用が許可される最も前の禁止ユーザ対応値と最も前の限定ユーザ対応値の組み合わせを利用開始世代として指定し、
鍵発行タイミングにおいて、所属ユーザ又は限定ユーザごとに、最新世代の鍵であって、ユーザに指定されている利用開始世代から当該最新世代までが許可世代範囲として設定されている鍵を発行し、
前記サーバ装置は、
情報処理装置から、前記情報処理装置のユーザの検索要求時点での最新世代の鍵を用いて生成され、前記ユーザの許可世代範囲である利用開始世代から当該最新世代までのｎ（ｎ≧１）世代の各世代における禁止ユーザ対応値及び限定ユーザ対応値が暗号化されているｎ個の暗号化世代情報が集約されている集約情報が含まれる検索要求を受信した場合に、
前記集約情報に対して所定の演算を行い、前記集約情報からｎ個の暗号化世代情報を抽出し、
抽出した暗号化世代情報ごとにインデックス情報との照合を行って暗号化データの検索を行うことを特徴とする請求項２３に記載の情報処理システム。
【請求項２５】
前記サーバ装置は、
情報処理装置から、前記ユーザにより指定された検索条件が暗号化されているインデックス情報が含まれる格納要求を受領した場合に、前記インデックス情報と、前記禁止ユーザ対応値及び限定ユーザ対応値と、前記暗号化データとを対応付けて記憶し、
情報処理装置から、前記ｎ世代の各世代における禁止ユーザ対応値及び限定ユーザ対応値と前記ユーザにより指定された検索条件が暗号化されているｎ個の暗号化世代情報が集約されている集約情報が含まれる検索要求を受信した場合に、
前記集約情報に対して所定の演算を行い、前記集約情報からｎ個の暗号化世代情報を抽出し、
抽出した暗号化世代情報ごとにインデックス情報との照合を行い、暗号化世代情報と共通する値のインデックス情報を選択し、選択したインデックス情報に対応付けられている暗号化データを抽出することを特徴とする請求項２４に記載の情報処理システム。
【請求項２６】
前記サーバ装置は、
情報処理装置から、前記ユーザにより指定された検索条件と格納対象の暗号化データの識別子が暗号化されているインデックス情報と前記識別子が含まれる格納要求を受領した場合に、前記インデックス情報と、前記禁止ユーザ対応値及び限定ユーザ対応値と、前記暗号化データと、前記識別子とを対応付けて記憶し、
情報処理装置から、前記ｎ世代の各世代における禁止ユーザ対応値及び限定ユーザ対応値と前記ユーザにより指定された検索条件が暗号化されているｎ個の暗号化世代情報が集約されている集約情報が含まれる検索要求を受信した場合に、
前記集約情報に対して所定の演算を行い、前記集約情報からｎ個の暗号化世代情報を抽出し、
抽出した暗号化世代情報ごとに、各インデックス情報に対応付けられている識別子を用いて所定の演算を行い、演算により得られた値と共通する値のインデックス情報を選択し、選択したインデックス情報に対応付けられている暗号化データを抽出することを特徴とする請求項２４に記載の情報処理システム。
【請求項２７】
前記管理装置は、
生成済みの鍵に対して第１の関数及び第２の関数のいずれかを適用して、各鍵間に連続性を持たせながら、前記生成済みの鍵とは別の禁止ユーザ対応値又は限定ユーザ対応値が設定されている鍵を生成し、
前記サーバ装置は、
情報処理装置からの検索要求を受信した場合に、受信した検索要求に含まれる前記集約情報に対して前記第１の関数と前記第２の関数を適用した所定の演算を行い、前記集約情報からｎ個の暗号化世代情報を抽出することを特徴とする請求項２４〜２６のいずれかに記載の情報処理システム。
【請求項２８】
前記管理装置は、
禁止ユーザ対応値及び限定ユーザ対応値のいずれもが先頭値となっている先頭世代の鍵と各世代の鍵との間に連続性を持たせるようにして第１の関数及び第２の関数を用いて各世代の鍵を生成し、
前記先頭世代の鍵と、いずれのユーザ及び情報処理装置に対しても公開されている公開値とを用いて、先頭世代暗号値を生成し、生成した先頭世代暗号値を前記サーバ装置に通知し、
前記サーバ装置は、
情報処理装置から、前記先頭世代暗号値との照合に用いられる照合用情報が含まれる検索要求を受信した場合に、前記照合用情報に対して前記第１の関数と前記第２の関数を適用して、前記照合用情報から前記先頭世代暗号値に一致する値が検出できるか否かを判定し、前記照合用情報から前記先頭世代暗号値に一致する値が検出できない場合には暗号化データの検索を行わないことを特徴とする請求項２３〜２７のいずれかに記載の情報処理システム。
【請求項２９】
前記管理装置は、
限定ユーザ対応値の最終値及び禁止ユーザ対応値の最終値を決定し、限定ユーザ対応値が最終値となり禁止ユーザ対応値が最終値となる最終世代の鍵を初期鍵として生成し、
前記初期鍵に第１の関数を適用して、禁止ユーザ対応値が前記初期鍵の禁止ユーザ対応値と共通し限定ユーザ対応値が前記初期鍵の限定ユーザ対応値の１つ前の世代の値となる新たな鍵を生成し、生成した鍵に前記第１の関数を適用して、禁止ユーザ対応値が当該生成済みの鍵の禁止ユーザ対応値と共通し限定ユーザ対応値が当該生成済みの鍵の限定ユーザ対応値の１つ前の世代の値となる新たな鍵を生成し、
前記初期鍵に第２の関数を適用して、限定ユーザ対応値が前記初期鍵の限定ユーザ対応値と共通し禁止ユーザ対応値が前記初期鍵の禁止ユーザ対応値の１つ前の世代の値となる新たな鍵を生成し、生成した鍵に前記第２の関数を適用して、限定ユーザ対応値が当該生成済みの鍵の限定ユーザ対応値と共通し禁止ユーザ対応値が当該生成済みの鍵の禁止ユーザ対応値の１つ前の世代の値となる新たな鍵を生成し、
生成した鍵に第１の関数及び第２の関数のいずれかを適用して新たな鍵を生成する動作を繰り返して、限定ユーザ対応値及び禁止ユーザ対応値の組み合わせの全パターンに対応する複数の鍵を生成し、生成した複数の鍵を記憶し、
鍵発行時に、所属ユーザ又は限定ユーザごとに、対応する限定ユーザ対応値及び禁止ユーザ対応値の組み合わせの鍵を、記憶している前記複数の鍵の中から抽出し、抽出した鍵を発行することを特徴とする請求項２７に記載の情報処理システム。
【請求項３０】
前記管理装置は、
予め、限定ユーザ対応値及び禁止ユーザ対応値のいずれもが先頭値となっている先頭世代の鍵を初期鍵として生成し、
鍵発行時に、所属ユーザ又は限定ユーザごとに、対応する限定ユーザ対応値及び禁止ユーザ対応値の組み合わせに基づき、初期鍵又は前記初期鍵から派生する鍵を生成元鍵とし、前記生成元鍵に前記第１の関数を適用して禁止ユーザ対応値が前記生成元鍵の禁止ユーザ対応値と共通し限定ユーザ対応値が前記生成元鍵の限定ユーザ対応値の１つ後の世代の値となる新たな鍵を生成し、または、前記生成元鍵に前記第２の関数を適用して限定ユーザ対応値が前記生成元鍵の限定ユーザ対応値と共通し禁止ユーザ対応値が前記生成元鍵の禁止ユーザ対応値の１つ後の世代の値となる新たな鍵を生成し、生成した鍵を所属ユーザ又は限定ユーザに発行することを特徴とする請求項２７に記載の情報処理システム。
【請求項３１】
前記管理装置は、
十分大きな素数であるｐ１及びｐ２を選び、Ｎ＝ｐ１×ｐ２とし、ｅ１及びｅ２としてＺＮ＊から（ｐ１−１）（ｐ２−１）と互いに素な数をランダムに選択した場合に、
前記第１の関数を、Ｆ１（ｘ）＝ｘｅ１  ｍｏｄ  Ｎ  とし、
前記第２の関数を、Ｆ２（ｘ）＝ｘｅ２  ｍｏｄ  Ｎ  とし、
（ｍｏｄはモジュロ演算子を表し、ＺＮ＊は０からＮ−１の整数の中でＮと互いに素である整数の集合を表す）（Ｆ１（ｘ）とＦ２（ｘ）は、互いに可換である）
前記禁止ユーザ対応値の最終値をｑ１とし、前記限定ユーザ対応値の最終値をｑ２とし、前記禁止ユーザ対応値が最終値となり前記限定ユーザ対応値が最終値となる最終世代の鍵である初期鍵をｋｑ１，ｑ２とし、初期鍵ｋｑ１，ｑ２をＺＮ＊からランダムに選択し、前記禁止ユーザ対応値がｉ世代であり前記限定ユーザ対応値がｊ世代である鍵をｋｉ，ｊとした場合に、
ｋｉ，ｊ−１＝Ｆ１（ｋｉ，ｊ）
ｋｉ−１，ｊ＝Ｆ２（ｋｉ，ｊ）
による演算を繰り返して、前記禁止ユーザ対応値及び前記限定ユーザ対応値の組み合わせの全パターンに対応する複数の鍵ｋ１，１からｋｑ１，ｑ２を生成することを特徴とする請求項２９に記載の情報処理システム。
【請求項３２】
前記管理装置は、
各情報処理装置において利用される関数を、
Ｇ（ｘ，ｙ）＝ｘｙ  ｍｏｄ  Ｎ  とし、
（Ｇ（ｘ，ｙ）は、Ｆ１（ｘ）及びＦ２（ｘ）と互いに可換である）、
前記サーバ装置は、
情報処理装置から、前記情報処理装置のユーザの検索要求時点での最新世代の鍵に基づいて生成された、前記ｎ世代の各世代における禁止ユーザ対応値及び限定ユーザ対応値と前記情報処理装置のユーザにより指定された検索条件が暗号化されているｎ個の暗号化世代情報が集約されている集約情報であって、
前記ユーザの検索要求時点での最新世代の鍵が、禁止ユーザ対応値がｓ世代であり限定ユーザ対応値がｔ世代である鍵ｋｓ，ｔであり、前記検索条件がｗであり、
ｔｄｓ，ｔ＝Ｇ（ｋｓ，ｔ，ｗ）
により生成された集約情報ｔｄｓ，ｔが含まれる検索要求を受信した場合に、
ｔｄｉ，ｊ−１＝Ｆ１（ｔｄｉ，ｊ）
ｔｄｉ−１，ｊ＝Ｆ２（ｔｄｉ，ｊ）
により、集約情報ｔｄｓ，ｔから、ｊ≦ｔを満たす範囲で暗号化世代情報ｔｄｉ，ｊを抽出することを特徴とする請求項３１に記載の情報処理システム。
【請求項３３】
前記サーバ装置は、
情報処理装置から、前記検索条件と格納対象の暗号化データの識別子が暗号化されているインデックス情報であって、
前記ユーザの格納要求時点での最新世代の鍵が、禁止ユーザ対応値がｓ世代であり限定ユーザ対応値がｔ世代である鍵ｋｓ，ｔであり、前記検索条件がｗであり、前記識別子がｉｄであり、Ｈ（ｘ，ｙ）を一方向性関数であり、
ｔｄ＝Ｇ（ｋｓ，ｔ，ｗ）
ｃ＝Ｈ（ｉｄ，ｔｄ）
により生成された暗号値ｃであるインデックス情報と、前記情報処理装置のユーザの格納要求時点での最新世代の鍵に設定されている禁止ユーザ対応値及び限定ユーザ対応値と、格納対象の暗号化データと、前記識別子とを受領した場合に、
前記インデックス情報と、前記禁止ユーザ対応値及び限定ユーザ対応値と、前記暗号化データと、前記識別子とを対応付けて記憶し、
情報処理装置からの検索要求を受信した際に、集約情報ｔｄｓ，ｔから暗号化世代情報ｔｄｉ，ｊを抽出し、
各インデックス情報に対応付けられている識別子をｉｄとした場合に、暗号化世代情報ｔｄｉ，ｊごとに、
ｃ＝Ｈ（ｉｄ，ｔｄｉ，ｊ）
を計算し、
演算により得られた値ｃと共通する値のインデックス情報を選択し、選択したインデックス情報に対応付けられている暗号化データを抽出することを特徴とする請求項３２に記載の情報処理システム。
【請求項３４】
請求項１〜３３のいずれかに記載の管理装置。
【請求項３５】
請求項１〜３３のいずれかに記載のサーバ装置。
【請求項３６】
請求項１〜２２のいずれかに記載の情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の情報処理装置とサーバ装置とが含まれる情報処理システムに関し、特に、情報処理装置が、検索のためのキーワードをサーバ装置に秘匿した状態でサーバ装置に蓄積されているデータを検索する秘匿検索システムに関する。
【背景技術】
【０００２】
サーバ装置（以下、単にサーバともいう）に保存されたデータを、検索者がキーワードを指定して検索でき、かつその際にデータ・キーワードをサーバに対して秘匿する秘匿検索システムがある。
このような秘匿検索システムは、機密データ管理のアウトソーシングや、メールサーバにおける暗号化メールのフィルタリングへの応用が期待されており、種々の安全性要件を達成するための技術や、サーバや検索者のストレージ・通信オーバーヘッド・演算オーバーヘッドを削減するための様々な技術が提案されている。
【０００３】
さらに、複数のユーザによる検索を可能とする場合には、ユーザの加入・脱退に柔軟に対処するための技術が必要とされる。
非特許文献１では、ユーザが保持する秘密情報をハッシュチェーンで管理し、ユーザの加入・脱退に伴って世代が更新されるたびに新しい秘密情報を正当ユーザに配布し、正当ユーザは最新の秘密情報から過去の秘密情報を導出できるようにし、ユーザに必要なストレージを抑えつつ、世代更新に対応した秘匿検索を達成する方式が開示されている。
また、特許文献１では、時刻と役職に基づいた、二次元的な鍵管理を行う方式が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−２４４４７４号公報
【非特許文献】
【０００５】
【非特許文献１】Ｈ．Ｐａｒｋ，  Ｊ．Ｗ．Ｂｙｕｎ，  ａｎｄ  Ｄ．Ｈ．Ｌｅｅ，  “Ｓｅｃｕｒｅ  Ｉｎｄｅｘ  Ｓｅａｒｃｈ  ｆｏｒ  Ｇｒｏｕｐｓ，”  ＴｒｕｓｔＢｕｓ  ２００５，  ＬＮＣＳ  ３５９２，  ｐｐ．１２８−１４０，  ２００５．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
世代更新を伴う秘匿検索システムでは、正当ユーザが、過去の世代で登録された情報を検索できるようにしたいという要求がある。
これを実現するために、非特許文献１にて開示されている方式では、検索者が最新の秘密情報から過去全ての世代の秘密情報を導出し、これらとキーワードからトラップドア（検索用の情報）を世代数分計算し、全てのトラップドアをサーバに送信し、トラップドアを受け取ったサーバが検索処理を行っている。
このため、検索者にとって計算量・通信量が世代数に比例して増大するという課題がある。
また、非特許文献１の方式では、加入ユーザが加入前の情報を全て検索することができ、これを防ぐことができないという課題がある。
【０００７】
一方、脱退ユーザに関しては、脱退後の情報を検索できないことは当然として、脱退前の情報を検索できるか否かについては実際のシステムに依存する。
例えば、ある会社に属していたユーザが退職した場合、退職前にはアクセスできた情報にもアクセスできなくするというケースが考えられる。
これに対し、ある部署に属していたユーザが異動した場合、業務の関係上、異動前にアクセスできた情報には引き続きアクセスしたいというケースを考えることができる。
脱退ユーザを上記のような「退職ユーザ」「異動ユーザ」に分けた場合、これらの一方のみに対応することは、非特許文献１の方式を始めとする、既存の方式で可能である。
しかし、脱退ユーザとして「退職ユーザ」「異動ユーザ」の両方が混在するシステムの場合、既存方式ではこれに対応できないという課題がある。
【０００８】
本発明は上記の課題を解決することを主な目的の一つとしており、検索者が送信すべきトラップドアの数を削減して、結果として検索者の計算量・通信量を削減することを主な目的とする。
また、ユーザごとに検索が許可されるデータの範囲を設定し、ユーザからの検索要求に対して当該ユーザに許可された範囲内でデータの検索を行うことを主な目的とする。
【課題を解決するための手段】
【０００９】
本発明に係る情報処理システムは、
複数のユーザに利用される複数の情報処理装置と、
ユーザの要求に基づいて暗号化データを記憶し、ユーザの要求に基づいて記憶している暗号化データの検索を行うサーバ装置と、
前記サーバ装置に対して秘密にしている鍵を更新イベントの発生時に新たな世代値を設けて更新し、更新イベント発生時を含む所定の鍵発行タイミングにおいてユーザに鍵を発行する管理装置を有し、
前記管理装置は、
利用が許可される世代範囲が許可世代範囲として設定される鍵を生成し、
ユーザごとに鍵の利用が許可される最も前の世代を利用開始世代として指定し、
鍵発行タイミングにおいて、ユーザごとに、最新世代の鍵であって、ユーザに指定されている利用開始世代から当該最新世代までが許可世代範囲として設定されている鍵を発行し、
各情報処理装置は、
最新世代の鍵を受領する度に、受領した最新世代の鍵を記憶し、
ユーザから暗号化データの格納指示があった際に、暗号化データの検索に用いられるインデックス情報と、前記ユーザの格納指示時点での最新世代の鍵の世代値と、暗号化データとを対応付けて格納するよう前記サーバ装置に要求し、
ユーザから暗号化データの検索指示があった際に、前記ユーザの検索指示時点での最新世代の鍵を用いて、許可世代範囲である利用開始世代から当該最新世代までのｎ（ｎ≧１）世代の各世代値が暗号化されているｎ個の暗号化世代情報が集約されている集約情報を生成し、生成した集約情報を含む検索要求を前記サーバ装置に送信し、
前記サーバ装置は、
情報処理装置からの格納要求を受領した場合に、インデックス情報と、鍵の世代値と、暗号化データとを対応付けて記憶し、
情報処理装置からの検索要求を受信した場合に、受信した検索要求に含まれる前記集約情報に対して所定の演算を行い、前記集約情報からｎ個の暗号化世代情報を抽出し、暗号化世代情報ごとに、暗号化世代情報が対象としている世代値と共通する世代値を対象としているインデックス情報に対応付けられている暗号化データであって所定の条件を満たす暗号化データを抽出することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、情報処理装置はｎ個の暗号化世代情報を集約した集約情報を送信するので、情報処理装置とサーバ装置との間の通信量を削減することができる。
また、管理装置において、ユーザごとに許可世代範囲が設定されている鍵を発行し、検索要求元のユーザの鍵を用いて生成された当該ユーザの許可世代範囲が反映される暗号化世代情報をサーバ装置で解析し、暗号化データの検索範囲をユーザの許可世代範囲に限定することができる。
【図面の簡単な説明】
【００１１】
【図１】実施の形態１に係るシステム構成例を示す図。
【図２】実施の形態１に係るサーバ装置の構成例を示す図。
【図３】実施の形態１に係る情報処理装置の構成例を示す図。
【図４】実施の形態１に係るグループ管理装置の構成例を示す図。
【図５】実施の形態１に係る暗号化キーワード記憶領域における記憶内容の例を示す図。
【図６】実施の形態１に係る暗号化データ記憶領域における記憶内容の例を示す図。
【図７】実施の形態１に係る暗号鍵記憶領域における記憶内容の例を示す図。
【図８】実施の形態１に係る暗号鍵記憶領域における記憶内容の例を示す図。
【図９】実施の形態２に係るサーバ装置の構成例を示す図。
【図１０】実施の形態２に係る情報処理装置の構成例を示す図。
【図１１】実施の形態２に係る暗号鍵記憶領域における記憶内容の例を示す図。
【図１２】実施の形態２に係る暗号鍵記憶領域における記憶内容の例を示す図。
【図１３】実施の形態２に係る暗号鍵記憶領域における記憶内容の例を示す図。
【図１４】実施の形態３に係るサーバ装置の構成例を示す図。
【図１５】実施の形態３に係る暗号化キーワード記憶領域における記憶内容の例を示す図。
【図１６】実施の形態３に係る世代遷移記憶領域における記憶内容の例を示す図。
【図１７】実施の形態３に係る暗号鍵記憶領域における記憶内容の例を示す図。
【図１８】実施の形態３に係る暗号鍵記憶領域における記憶内容の例を示す図。
【図１９】実施の形態３に係る暗号化キーワード記憶領域における記憶内容の例を示す図。
【図２０】実施の形態３に係る世代遷移記憶領域における記憶内容の例を示す図。
【図２１】実施の形態１に係る鍵生成手順を説明する図。
【図２２】実施の形態２に係る鍵生成手順を説明する図。
【図２３】実施の形態２に係るデータ検索手順を説明する図。
【図２４】実施の形態３に係る鍵生成手順を説明する図。
【図２５】実施の形態３に係る鍵更新手順を説明する図。
【図２６】実施の形態１に係るグループ管理装置の鍵生成動作の概要を示すフローチャート図。
【図２７】実施の形態１に係るグループ管理装置の鍵発行動作の概要を示すフローチャート図。
【図２８】実施の形態１に係るグループ管理装置の鍵更新動作の概要を示すフローチャート図。
【図２９】実施の形態１に係る情報処理装置の暗号化データの格納要求時における動作の概要を示すフローチャート図。
【図３０】実施の形態１に係るサーバ装置の暗号化データの格納動作の概要を示すフローチャート図。
【図３１】実施の形態１に係る情報処理装置の暗号化データの検索要求時における動作の概要を示すフローチャート図。
【図３２】実施の形態１に係るサーバ装置の暗号化データの検索動作の概要を示すフローチャート図。
【図３３】実施の形態２に係るグループ管理装置の鍵生成動作の概要を示すフローチャート図。
【図３４】実施の形態２に係るグループ管理装置の鍵発行動作の概要を示すフローチャート図。
【図３５】実施の形態２に係るグループ管理装置の鍵更新動作の概要を示すフローチャート図。
【図３６】実施の形態２に係る情報処理装置の暗号化データの検索要求時における動作の概要を示すフローチャート図。
【図３７】実施の形態２に係るサーバ装置の暗号化データの検索動作の概要を示すフローチャート図。
【図３８】実施の形態３に係るグループ管理装置の鍵生成動作の概要を示すフローチャート図。
【図３９】実施の形態３に係るグループ管理装置の異動ユーザ発生時の動作の概要を示すフローチャート図。
【図４０】実施の形態３に係るグループ管理装置の退職ユーザ発生時の動作の概要を示すフローチャート図。
【図４１】実施の形態３に係るサーバ装置の暗号化データの検索動作の概要を示すフローチャート図。
【図４２】実施の形態１〜３に係るサーバ装置等のハードウェア構成例を示す図。
【発明を実施するための形態】
【００１２】
以下の実施の形態１〜３では、秘密情報やトラップドアの導出方法を工夫することで、サーバが最新のトラップドアから過去のトラップドアを導出できるようにし、検索者が送信すべきトラップドアの数を削減して、結果として検索者の計算量・通信量を削減することができる秘匿検索システム（情報処理システム）を説明する。
また、新たにグループに加入した加入ユーザに加入前の情報を検索させない、脱退ユーザとして退職・異動ユーザの混在を許すなど、ユーザの加入・脱退に柔軟に対応することができる秘匿検索システム（情報処理システム）を説明する。
【００１３】
実施の形態１．
図１は、サーバ装置に保存されたデータを、複数のユーザがキーワードを指定して検索でき、かつその際にデータ・キーワードをサーバ装置に対して秘匿する秘匿検索システムの構成例である。
図１に示すように、複数の情報処理装置３０１が、ネットワーク１０１を介してサーバ装置２０１とグループ管理装置４０１に接続している。
なお、グループ管理装置４０１は管理装置の例である。
各装置の詳細は後述するが、ここで、各装置の概要を説明する。
【００１４】
各情報処理装置３０１を利用するユーザは企業における部署等の所定のグループに属しており、グループ内でデータを共用することができる。例えば、情報処理装置３０１を利用するユーザの属性（帰属組織、職務等）により、情報処理装置３０１のグループの分類が行われる。
同じグループの情報処理装置３０１は、暗号鍵（以下、単に鍵ともいう）を共有するとともに、例えば、新規ユーザの追加、既存ユーザの脱退といった更新イベントの発生に伴って暗号鍵が更新されていく。
なお、グループに所属しているユーザを所属ユーザともいう。また、グループに新規に加入する者を加入ユーザともいう。また、グループから脱退した者を脱退ユーザともいう。
暗号鍵は、サーバ装置２０１に対しては秘密にされている。
暗号鍵は、グループ管理装置４０１により更新イベントの発生の度に更新され、また、更新イベント発生時を含む鍵発行タイミングにおいて同じグループに属するユーザの情報処理装置３０１に暗号鍵が配布される。
各情報処理装置３０１では、グループ管理装置４０１から新たな暗号鍵が配布される度に過去の暗号鍵に上書きして保存する。
なお、暗号鍵は世代数により管理される（更新により世代数の値が１つ増える）。
【００１５】
本実施の形態では、暗号化データを各情報処理装置３０１からサーバ装置２０１に格納し、また、各情報処理装置３０１はサーバ装置２０１に暗号化データの検索を要求する。
各ユーザには、グループへの加入時期や、グループに引き続き所属しているか脱退しているか等により、検索が許可される暗号化データの範囲が決められている。
この検索が許可される暗号化データの範囲は、暗号鍵の世代によって定義される。
より具体的には、グループ管理装置４０１は、ユーザごとに鍵の利用が許可される最も前の世代を利用開始世代として指定する。
そして、鍵発行タイミングにおいて、ユーザごとに（情報処理装置３０１ごとに）、最新世代の鍵であって、ユーザに指定されている利用開始世代から当該最新世代までが許可世代範囲として設定されている鍵を発行する。
許可世代範囲とは、鍵の利用が許可される世代範囲であり、ユーザごとに異なっている。
鍵が更新される度に最新世代が改められるので、許可世代範囲は鍵の更新とともに拡大していく。
ユーザに検索が許可される暗号化データの範囲は、当該ユーザに発行された鍵に設定されている許可世代範囲に一致する。
後述するように、ユーザが暗号化データをサーバ装置２０１に格納する際に当該ユーザのその時点での最新世代の鍵の世代値と暗号化データが対応付けられて登録される。
また、暗号化データの検索の際に、ユーザは、その時点での当該ユーザの許可世代範囲が反映される情報（トラップドア）をその時点での最新世代の鍵を用いて生成し、情報処理装置３０１からサーバ装置２０１に送信する。
サーバ装置２０１では、検索要求に含まれる情報（トラップドア）を解析して、検索要求元ユーザの許可世代範囲に合致する世代値と対応付けられている暗号化データのみを検索の対象とする。
【００１６】
暗号化データの登録段階では、各情報処理装置３０１は、ユーザから暗号化データの格納を指示する格納指示を入力した際に、データ格納指示時点の最新世代の鍵を用いて、暗号化データとともに登録するキーワード（平文）（検索条件）に対して暗号化を行ってトラップドアを生成し、更に、暗号化データのＩＤ（識別子）を用いてトラップドアを再暗号化して暗号化キーワードを生成する。暗号化キーワードは、サーバ装置２０１に対してキーワードの内容を秘匿化できる。
暗号化キーワードは、暗号化データとともにサーバ装置２０１で登録され、暗号化データの検索に用いられる。暗号化キーワードは、インデックス情報の例である。
なお、後述するように、暗号化キーワードではなく、トラップドア自体を暗号化データに対応付けて登録することも可能である。この場合は、トラップドアがインデックス情報の例となる。
【００１７】
トラップドアは、データ検索段階で、データ検索要求元のユーザの許可世代範囲をサーバ装置２０１において導出可能にする情報であり、また、検索対象のキーワードの内容を秘匿化したままサーバ装置２０１において検索対象のキーワードを特定可能にするためのデータである。
【００１８】
情報処理装置３０１は、登録対象の暗号化データと、当該暗号化データのデータＩＤ（Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）、暗号化キーワード、当該暗号化キーワードの生成に用いた鍵の世代値をサーバ装置２０１に送信し、サーバ装置２０１では、これらを関連付けて記憶する。
【００１９】
そして、情報処理装置３０１では、ユーザから暗号化データの検索指示を入力した際に、データ検索指示の入力時点で最新世代の暗号鍵を用いて当該ユーザの許可世代範囲と検索キーワードが暗号化されたトラップドアを生成する。
より具体的には、情報処理装置３０１は、集約トラップドア（集約情報）を生成し、集約トラップドアをサーバ装置２０１に送信する。
集約トラップドアは、ユーザの許可世代範囲である利用開始世代から当該最新世代までのｎ（ｎ≧１）世代の各世代値と検索キーワードが暗号化されているｎ個のトラップドア（暗号化世代情報）が集約されている情報である。
【００２０】
サーバ装置２０１では、集約トラップドアを受信し、集約トラップドアからｎ個のトラップドアを導出する。
また、導出したトラップドアごとに、トラップドアが対象としている世代値と共通する世代値を対象とする暗号化キーワードであってトラップドアにおいて暗号化されている検索キーワードに合致する暗号化キーワードを検索する。
そして、検索した暗号化キーワードに対応付けられている暗号化データを抽出する。
【００２１】
以上が、各装置の概要である。
次に、図２〜図４を用いて、サーバ装置２０１、情報処理装置３０１及びグループ管理装置４０１の構成例を説明する。
【００２２】
図２は、本秘匿検索システム（図１）において、データ・キーワードを保持し、検索を行うサーバ装置２０１の構成例を表すブロック図である。
【００２３】
図２において、暗号化キーワード記憶領域２１１は、暗号化されたキーワードを、対応するデータＩＤ、および世代値と関連付けて記憶するデータ記憶手段である。
図５は暗号化キーワード記憶領域２１１が記憶するデータの一例を表す。
前述のように、暗号化キーワードは、インデックス情報の例である。
【００２４】
暗号化データ記憶領域２１２は、暗号化されたデータを、対応するデータＩＤと関連付けて記憶するデータ記憶手段である。
図６は暗号化データ記憶領域２１２が記憶するデータの一例を表す。
【００２５】
トラップドア生成部２２１は、情報処理装置３０１から受信したトラップドア（集約トラップドア）から、ｎ世代分のトラップドアを順次生成する手段である。
【００２６】
比較部２２２は、トラップドア生成部２２１が生成したｎ世代分のトラップドアと、暗号化キーワード記憶領域２１１に記憶されているデータを比較し、情報処理装置３０１の指定したキーワードに合致するデータを暗号化キーワード記憶領域２１１から検索する手段である。
【００２７】
通信部２３１は、情報処理装置３０１やグループ管理装置４０１と通信を行う手段である。
【００２８】
図３は、本秘匿検索システム（図１）において、サーバ装置２０１への暗号化データの登録・サーバ装置２０１からの暗号化データの検索を行う情報処理装置３０１の構成例を表すブロック図である。
【００２９】
図３において、暗号鍵記憶領域３１１は、データの暗号化・検索に用いる秘密情報を記憶するデータ記憶手段である。
図７は暗号鍵記憶領域３１１が記憶するデータの一例を表す。
図７の例において、暗号鍵ｋ１，３は、１世代目から３世代目までの秘密情報を検索可能であることを意味する。
換言すれば、暗号鍵ｋ１，３は、ユーザの利用開始世代が第１代目であり、また、許可世代範囲が第１世代目から第３世代目までであることを意味する。
【００３０】
トラップドア生成部３２１は、暗号鍵とキーワードから、対応するトラップドアを生成する手段である。
前述したように、トラップドア生成部３２１は、ｎ（ｎ≧１）世代分のトラップドアが集約されている集約トラップドアを生成する。
図７の暗号鍵ｋ１，３を用いる場合は、第１世代から第３世代までの３世代分の３つのトラップドアが１つのトラップドアに集約されている集約トラップドアを生成する。
【００３１】
暗号化キーワード生成部３２２は、あるキーワードに対応したトラップドアとデータＩＤから、暗号化キーワードを生成する手段である。
【００３２】
通信部３３１は、サーバ装置２０１やグループ管理装置４０１と通信を行う手段である。
【００３３】
図４は、本秘匿検索システム（図１）において、初期設定や、情報処理装置３０１が保持する暗号鍵の生成・管理などを行うグループ管理装置４０１の構成例を表すブロック図である。
【００３４】
図４において、暗号鍵記憶領域４１１は、情報処理装置３０１が利用する暗号鍵を記憶するデータ記憶手段である。
図８は暗号鍵記憶領域４１１が記憶するデータの一例を表す。
図８の例において、暗号鍵ｋｉ，ｊは、ｉ世代目からｊ世代目までの秘密情報を検索可能であることを意味する。
【００３５】
暗号鍵生成部４２１は、情報処理装置３０１が利用する暗号鍵を生成する手段である。
【００３６】
通信部４３１は、サーバ装置２０１や情報処理装置３０１と通信を行う手段である。
【００３７】
世代範囲記憶領域４４１は、ユーザごとに許可開始世代を記憶するデータ記憶手段である。
【００３８】
暗号鍵配布処理部４５１は、ユーザに配布する暗号鍵を暗号鍵記憶領域４１１から抽出する。
【００３９】
本秘匿検索システムにおける手続きは、（１）グループ管理装置４０１が初期設定を行う部分、（２）グループ管理装置４０１が、加入した情報処理装置３０１に暗号鍵を配布する部分、（３）グループ管理装置４０１が情報処理装置３０１が保持する暗号鍵の世代更新を行う部分、（４）情報処理装置３０１が暗号化データをサーバ装置２０１に送信・格納する部分、（５）情報処理装置３０１が暗号化データをサーバ装置２０１から検索・取得する部分に大別される。
以下、それぞれの手続きについて説明する。
【００４０】
（１）グループ管理装置の初期設定
グループ管理装置４０１は、パラメータｑ、および互いに可換な三つの関数Ｆ１（ｘ），Ｆ２（ｘ），Ｇ（ｘ、ｙ）を決定し、公開情報とする。
ここで、Ｆ１およびＦ２としては一方向性関数を選び、またＧとしては、関数の出力から実際の入力を推定することが困難である関数を選ぶ。
また、ＦとＧの可換性とは、例えばＦ１（Ｇ（ｘ，ｙ））＝Ｇ（Ｆ１（ｘ），ｙ）を意味するものとする。
ｑは世代数の最大値（最終世代）であり、世代の更新頻度やシステムの運用期間から適切に設定する。
さらに、適当な一方向性関数Ｈを選択し、公開情報とする。
本実施の形態では、Ｆ１，Ｆ２，Ｇの具体例として、以下に基づき決定したものを利用する。
ｐ１，ｐ２として十分大きな素数を選び、Ｎ＝ｐ１×ｐ２とする。
ｅ１，ｅ２としてＺＮ＊から、（ｐ１−１）（ｐ２−１）と互いに素な数をランダムに選択する。
Ｆ１，Ｆ２，Ｇを以下で定める。
Ｆ１（ｘ）＝ｘｅ１  ｍｏｄ  Ｎ
Ｆ２（ｘ）＝ｘｅ２  ｍｏｄ  Ｎ
Ｇ（ｘ，ｙ）＝ｘｙ  ｍｏｄ  Ｎ
なお、ｍｏｄはモジュロ演算子を表し、ＺＮ＊は０からＮ−１の整数の中でＮと互いに素である整数の集合を表す。
また、Ｆ１（ｘ）は第１の関数の例であり、Ｆ２（ｘ）は第２の関数の例である。
【００４１】
次に、暗号鍵生成部４２１による鍵生成動作の詳細を図２６のフローチャートを参照しながら説明する。
暗号鍵生成部４２１は、情報処理装置３０１が利用する暗号鍵ｋｉ，ｊ（１≦ｉ≦ｊ≦ｑ）を生成する。
ここで、ｋｉ，ｊは、ｉ世代目からｊ世代目までの秘密情報を検索可能な暗号鍵である。
【００４２】
まず、暗号鍵生成部４２１は、暗号鍵ｋ１，ｑ（第１世代から最終世代までを許可世代範囲とする暗号鍵）を、ＺＮ＊からランダムに選択する（Ｓ２６０１）。
そして、初期鍵である暗号鍵ｋ１，ｑに対してＦ１及びＦ２を適用して新たな暗号鍵を生成し、以降、生成済みの鍵に対してＦ１及びＦ２を適用して新たな鍵を生成する動作を繰り返し、各鍵間に連続性を持たせながら、生成済みの鍵とは別の許可世代範囲が設定されている暗号鍵を生成する。
具体的には、暗号鍵ｋ１，ｑ以外の暗号鍵ｋｉ，ｊ（１≦ｉ≦ｊ≦ｑ）を、以下の式に従って順次計算する（暗号鍵の無矛盾性はＦ１，Ｆ２の可換性によって保証される）（Ｓ２６０２）。
ｋｉ，ｊ−１＝Ｆ１（ｋｉ，ｊ）
ｋｉ＋１，ｊ＝Ｆ２（ｋｉ，ｊ）
【００４３】
このように、暗号鍵生成部４２１は、初期鍵である暗号鍵ｋ１，ｑに第１の関数（Ｆ１）を適用して、許可世代範囲の開始世代が暗号鍵ｋ１，ｑの開始世代と共通し終了世代が暗号鍵ｋ１，ｑの終了世代の１つ前の世代となる新たな暗号鍵ｋ１，ｑ−１を生成し、生成した暗号鍵ｋ１，ｑ−１に第１の関数を適用して、許可世代範囲の開始世代が当該生成済みの暗号鍵ｋ１，ｑ−１の開始世代と共通し終了世代が当該生成済みのｋ１，ｑ−１の終了世代の１つ前の世代となる新たな暗号鍵ｋ１，ｑ−２を生成する。
また、同様に、暗号鍵生成部４２１は、初期鍵である暗号鍵ｋ１，ｑに第２の関数（Ｆ２）を適用して、許可世代範囲の終了世代が暗号鍵ｋ１，ｑの終了世代と共通し開始世代が暗号鍵ｋ１，ｑの開始世代の１つ後の世代となる新たな暗号鍵ｋ２，ｑを生成し、生成した暗号鍵ｋ２，ｑに第２の関数を適用して、許可世代範囲の終了世代が当該生成済みの暗号鍵ｋ２，ｑの終了世代と共通し開始世代が当該生成済みの暗号鍵ｋ２，ｑの開始世代の１つ後の世代となる新たな暗号鍵ｋ３，ｑを生成する。
更に、暗号鍵生成部４２１は、生成した鍵に第１の関数及び第２の関数のいずれかを適用して新たな鍵を生成する動作を繰り返して、許容世代範囲の全パターンに対応する複数の暗号鍵を生成する。
【００４４】
こうして得られた全ての暗号鍵ｋ１，１〜ｋｑ，ｑを、暗号鍵生成部４２１は、暗号鍵記憶領域４１１に格納する（Ｓ２６０３）。
最後に、暗号鍵配布処理部４５１が１世代目の暗号鍵ｋ１，１を暗号鍵記憶領域４１１から取得し、通信部４３１が全ての正当な情報処理装置３０１（グループに所属しているユーザが利用している情報処理装置３０１）に、１世代目の暗号鍵ｋ１，１を送信する（Ｓ２６０４）。
これは、暗号鍵の安全性が保たれる方式であれば、オフラインで行っても良いし、既存の鍵配送技術を用いてオンラインで行っても良い。
暗号鍵ｋ１，１を受信した情報処理装置３０１は、この暗号鍵ｋ１，１を、世代情報とともに暗号鍵記憶領域３１１に格納する。
【００４５】
（２）加入ユーザへの暗号鍵配布
ｔ世代目においてユーザの加入があった際、グループ管理装置４０１は、加入した情報処理装置３０１に対して暗号鍵を配布する。
加入ユーザに対して、ｔ世代目を含めた、ｓ世代目からｔ世代目まで（ｓ≦ｔ）の秘密情報の検索を許す場合、グループ管理装置４０１の通信部４３１が、加入した情報処理装置３０１に、暗号鍵ｋｓ，ｔを送信する。
これは、暗号鍵の安全性が保たれる方式であれば、オフラインで行っても良いし、既存の鍵配送技術を用いてオンラインで行っても良い。
暗号鍵ｋｓ，ｔを受信した情報処理装置３０１は、受信した暗号鍵ｋｓ，ｔを、世代情報とともに暗号鍵記憶領域３１１に格納する。
この場合、次で述べる「（３）暗号鍵の世代更新」の処理は不要である（行っても良い）。
一方、加入ユーザに対して、ｔ世代目の秘密情報の検索を許さない場合、グループ管理装置４０１の通信部４３１が、加入した情報処理装置３０１に、暗号鍵ｋｔ＋１，ｔ＋１を送信する。
これは、暗号鍵の安全性が保たれる方式であれば、オフラインで行っても良いし、既存の鍵配送技術を用いてオンラインで行っても良い。
暗号鍵ｋｔ＋１，ｔ＋１を受信した情報処理装置３０１は、受信した暗号鍵ｋｔ＋１，ｔ＋１を、世代情報とともに暗号鍵記憶領域３１１に格納する。
その後、ｔ世代目からｔ＋１世代目に更新するために、次で述べる「（３）暗号鍵の世代更新」の処理が実行される。
【００４６】
図２７は、以上の（２）加入ユーザへの暗号鍵配布における動作を示すフローチャートである。
暗号鍵配布処理部４５１は、例えば、グループ管理装置４０１のオペレータからの入力に基づき、新たに加入する加入ユーザに許容される世代範囲を判断する（Ｓ２７０１）。
加入ユーザにｓ世代〜ｔ世代が認められる場合は、暗号鍵配布処理部４５１は、暗号鍵ｋｓ，ｔを暗号鍵記憶領域４１１から取得し、通信部４３１が当該ユーザの情報処理装置３０１に暗号鍵ｋｓ，ｔを送信する（Ｓ２７０２）。
また、世代範囲記憶領域４４１が、当該加入ユーザの許可世代範囲（ｓ世代からｔ世代）を記憶する（Ｓ２７０３）。
一方、Ｓ２７０１の判断において、新規に加入するユーザにｔ世代が許可されない場合は、暗号鍵配布処理部４５１は、暗号鍵ｋｔ＋１，ｔ＋１を暗号鍵記憶領域４１１から取得し、通信部４３１が当該ユーザの情報処理装置３０１に暗号鍵ｋｔ＋１，ｔ＋１を送信する（Ｓ２７０４）。
また、世代範囲記憶領域４４１が、当該加入ユーザの許可世代範囲（ｔ＋１世代）を記憶する（Ｓ２７０５）。
また、この後、図２８に示す世代更新処理が行われる（Ｓ２７０６）。
【００４７】
（３）暗号鍵の世代更新
正当な情報処理装置３０１のグループに対し、ユーザの加入・脱退があった際に、暗号鍵の世代更新が必要となる場合がある。
このようなユーザの加入（上記のｔ世代目の秘密情報の検索を認めないユーザの加入）及びユーザの脱退が更新イベントとなる。
更新イベントが発生した場合には、以下のように世代更新を実施する。
【００４８】
ｔ世代目からｔ＋１世代目に更新する場合（ただしｔ＋１≦ｑ）、グループ管理装置４０１の通信部４３１が、（加入ユーザを除く）全ての正当な情報処理装置３０１（所属ユーザが利用している情報処理装置３０１）と通信を行い、各情報処理装置３０１が保持する暗号鍵ｋｓ，ｔを、ｔ＋１世代目の検索も可能である暗号鍵ｋｓ，ｔ＋１に更新する。
これは、暗号鍵の安全性が保たれる方式であれば、オフラインで行っても良いし、既存の鍵配送技術を用いてオンラインで行っても良い。
暗号鍵ｋｓ，ｔ＋１を受信した情報処理装置３０１は、暗号鍵記憶領域３１１の内容を、新しい世代情報（検索開始世代ｓ，検索終了世代ｔ＋１）と暗号鍵ｋｓ，ｔ＋１で置き換える。
【００４９】
なお、グループを脱退した者がいる場合には、当該脱退者には、更新後の最新世代の鍵が配布されない。
このため、脱退者は、脱退前にサーバ装置２０１に登録されている暗号化データには、保持している暗号鍵を用いてアクセスすることができるが、脱退後にサーバ装置２０１に登録された暗号化データには、更新後の暗号鍵を保有していないのでアクセスできない。
なお、以前の暗号化データを含め一切の暗号化データに脱退者がアクセスできないようにすることもできる。
【００５０】
図２８は、以上の（３）暗号鍵の世代更新における動作を説明するフローチャートである。
更新イベントが発生した場合、つまり、ユーザの脱退又は世代更新が必要なユーザの加入があった場合（Ｓ２８０１でＹＥＳ）、暗号鍵配布処理部４５１は、世代範囲記憶領域４４１から各所属ユーザの許可世代範囲を読み出す（Ｓ２８０２）。
そして、暗号鍵配布処理部４５１は、所属ユーザごとに、ｓ世代〜ｔ＋１世代に対応する暗号鍵ｋｓ，ｔ＋１を暗号鍵記憶領域４１１から取得する（Ｓ２８０３）。
そして、通信部４３１が各所属ユーザの情報処理装置３０１に暗号鍵ｋｓ，ｔ＋１を送信する（Ｓ２８０４）。
なお、Ｓ２８０２で、所属ユーザごとに許可世代範囲を読み出すのは、所属ユーザごとに利用開始世代が異なるからである。
つまり、例えば、あるユーザは、グループ初期から所属しているので１世代目が利用開始世代になっているが、別のユーザは途中からグループに加入したため、３世代目が利用開始世代となっているような場合が生じるからである。
【００５１】
（４）暗号化データの送信・格納
正当な情報処理装置３０１がデータをサーバ装置２０１に送信する場合、後に秘匿検索が行えるよう、キーワードとデータを別々に暗号化したものを送信する。
ｔ世代目における具体的な手順を図２９及び図３０を参照しながら以下に述べる。
【００５２】
まず、情報処理装置３０１は、データに対し、ユニークなデータＩＤを割り当てる（ｉｄｘとする）。
さらに、情報処理装置３０１は、データの暗号化を行う（Ｓ２９０１）。
ここでは、正当な情報処理装置３０１だけが復号できるような、既存の暗号技術（グループ暗号技術）を利用する（暗号化データをｄｘとする）。
暗号化データｄｘに関連付けられる複数のキーワード（ｗｘｊとする）をユーザから入力する（Ｓ２９０２）。
次に、トラップドア生成部３２１が、データに関連付けられた複数のキーワード（ｗｘｊ）に対し、それぞれトラップドアを生成する（Ｓ２９０３）。
具体的には、暗号鍵記憶領域３１１に格納されている暗号鍵ｋｓ，ｔを利用して、各キーワードｗｘｊに対し、トラップドアｔｄｘｊを以下のように計算する（Ｆ２ｔ−ｓはＦ２をｔ−ｓ回適用することを表す。以下においても同様）。
ｋｔ，ｔ＝Ｆ２ｔ−ｓ（ｋｓ，ｔ）
ｔｄｘｊ＝Ｇ（ｋｔ，ｔ，ｗｘｊ）
その後、暗号化キーワード生成部３２２が、各トラップドアｔｄｘｊに対し、暗号化キーワードｃｘｊを以下のように計算する（Ｓ２９０４）。
ｃｘｊ＝Ｈ（ｉｄｘ，ｔｄｘｊ）
最後に、通信部３３１が、世代、データＩＤ、暗号化データ、暗号化キーワードの組（ｔ，ｉｄｘ，ｄｘ，ｃｘ１，ｃｘ２，．．．）を格納要求としてサーバ装置２０１に送信する（Ｓ２９０５）。
【００５３】
サーバ装置２０１では、通信部２３１が格納要求を受信し（Ｓ３００１）、暗号化データｄｘをデータＩＤと関連付けて暗号化データ記憶領域２１２に格納し、各暗号化キーワードｃｘｊを世代、データＩＤと関連付けて暗号化キーワード記憶領域２１１に格納する（Ｓ３００２）。
【００５４】
（５）暗号化データの検索・取得
正当な情報処理装置３０１は、現在もしくは過去の世代にサーバ装置２０１に格納されたデータに対し、キーワードを指定して秘匿検索を行うことができる。
暗号鍵ｋｓ，ｔを持つ正当な情報処理装置３０１が、ｓ世代目からｔ世代目までの検索を行う具体的な手順を図３１及び図３２を参照しながら以下に述べる。
【００５５】
まず、情報処理装置３０１は、暗号化データの検索指示として、ユーザから検索対象のキーワードｗを入力する（Ｓ３１０１）。
次に、トラップドア生成部３２１が、検索したいキーワードｗに対応するトラップドアを生成する（Ｓ３１０２）。
具体的には、キーワードｗに対し、集約トラップドアｔｄｓ，ｔ（ｓ世代目からｔ世代目までが検索可能なトラップドア）を以下のように計算する。なお、ｋｓ，ｔは、ユーザの検索指示時点での最新世代の暗号鍵である。
ｔｄｓ，ｔ＝Ｇ（ｋｓ，ｔ，ｗ）
集約トラップドアｔｄｓ，ｔ（集約情報）は、世代値ｓとキーワードｗが暗号化されているトラップドアｔｄｓ，ｓから世代値ｔとキーワードｗが暗号化されているトラップドアｔｄｔ，ｔまでのｎ個のトラップドアを集約している。また、各トラップドアｔｄｓ，ｓ〜ｔｄｔ，ｔは、暗号化世代情報に相当する。
次に、通信部３３１が、検索開始世代、検索終了世代、トラップドアの組（ｓ，ｔ，ｔｄｓ，ｔ）を検索要求としてサーバ装置２０１に送信する（Ｓ３１０３）。
【００５６】
サーバ装置２０１では、通信部２３１が検索要求を受信し（Ｓ３２０１）、トラップドア生成部２２１が、ｓ世代目からｔ世代目までのそれぞれに対応するトラップドアｔｄｓ，ｓ〜ｔｄｔ，ｔを以下のように順次計算する（Ｓ３２０２）。
ｔｄｉ，ｉ＝Ｆ１ｔ−ｉ（Ｆ２ｉ−ｓ（ｔｄｓ，ｔ））  （ｓ≦ｉ≦ｔ）
【００５７】
その後、比較部２２２が、暗号化キーワード記憶領域２１１を参照し、トラップドアに対応する暗号化キーワードが存在するかを確認する（Ｓ３２０３）。
具体的には、暗号化キーワード記憶領域２１１の各行の世代、データＩＤ、暗号化キーワードの組（ｊ，ｉｄ，ｃ）に対し、以下の等式が成立するかを確認する。
ｃ＝Ｈ（ｉｄ，ｔｄｊ，ｊ）
つまり、比較部２２２は、前述のＳ３２０２で生成されたトラップドアごとに、暗号化キーワード記憶領域２１１のデータＩＤのうち対応付けられている世代値ｊが当該トラップドアの世代値ｊと一致しているデータＩＤを抽出し、抽出したデータＩＤとトラップドアに一方向性関数Ｈを適用して暗号化キーワード候補（Ｈ（ｉｄ，ｔｄｊ，ｊ））を算出し、算出した暗号化キーワード候補（Ｈ（ｉｄ，ｔｄｊ，ｊ））が、暗号化キーワード記憶領域２１１の対応する行の暗号化キーワードｃに一致するか否かの照合を行う。
【００５８】
上記の等式が成立した場合はｃが指定されたキーワードｗに対応する暗号化キーワードとなるため、比較部２２２は、暗号化キーワード記憶領域２１１から対応するデータＩＤ（ｉｄ）を抽出し（Ｓ３２０４）、抽出したデータＩＤ（ｉｄ）をキーに暗号化データ記憶領域２１２を検索して暗号化データｄを取得する（Ｓ３２０５）。
最後に、通信部２３１が情報処理装置３０１に、キーワードｗに対応する暗号化データｄを送信する。
なお、上記の等式が複数成立した場合は全て送信するようにしても、一部を送信するようにしても良い。
上記の等式が暗号化キーワード記憶領域２１１のどの行においても不成立であった場合は、情報処理装置３０１にその旨を送信する。
なお、存在しないキーワードを指定した場合の他、データ検索の要求元が正当なアクセス権限を有しない場合（正しい暗号鍵を有しないので、適切なトラップドアを作成できない）に、上記の等式が暗号化キーワード記憶領域２１１のどの行においても不成立となると考えられる。
【００５９】
暗号化データｄを受信した情報処理装置３０１では、暗号化データｄの復号を行う。
ここでは、正当な情報処理装置３０１だけが復号できるような、既存の暗号技術（グループ暗号技術）を利用する。
【００６０】
ここで、図２１を参照して、具体例を用いて鍵生成手順及び各鍵とトラップドアの関係を説明する。
【００６１】
図２１の例では、０世代目が先頭世代であり、５世代目が最新世代である。
また、実線の矢印が関数Ｆ１を示し、破線がＦ２を示し、鎖線が関数Ｇを示している。
【００６２】
グループの初期からグループに所属している所属ユーザには、最新世代が５世代目であるときには、最新世代の暗号鍵として暗号鍵ｋ０，５が配布されている。
暗号鍵ｋ０，５からは、関数Ｆ１及び関数Ｆ２の実行により全世代の暗号鍵ｋ０，０〜ｋ５，５が導出可能であり、また、暗号鍵ｋ０，０〜ｋ５，５の各々から関数Ｇよりトラップドアｔｄ０，０〜ｔｄ５，５が導出可能である。
このため、グループの初期からグループに所属している所属ユーザの情報処理装置３０１では、暗号鍵ｋ０，５からトラップドアｔｄ０，０〜ｔｄ５，５が集約されている集約トラップドアｔｄ０，５を生成することができる。
また、サーバ装置２０１では、集約トラップドアｔｄ０，５からトラップドアｔｄ０，０〜ｔｄ５，５の各々を導出することができ、検索要求元のユーザが暗号鍵ｋ０，５を所持していることを検証することができる。
この結果、サーバ装置２０１では、暗号鍵に設定されている許可世代範囲である０世代目〜５世代目の範囲内で暗号化データを検索する。
【００６３】
一方、暗号鍵が２度更新された後にグループに加入したユーザ（加入時に配布される暗号鍵が暗号鍵ｋ２，２）には、最新世代が５世代目であるときには、最新世代の暗号鍵として暗号鍵ｋ２，５が配布されている。
暗号鍵ｋ２，５からは、関数Ｆ１及び関数Ｆ２の実行により暗号鍵ｋ２，２〜ｋ５，５のみ導出可能であり、また、暗号鍵ｋ２，２〜ｋ５，５の各々から関数Ｇよりトラップドア暗号鍵ｔｄ２，２〜ｔｄ５，５が導出可能である。
このため、途中からグループに加入した所属ユーザの情報処理装置３０１では、暗号鍵ｋ２，５からトラップドアｔｄ２，２〜ｔｄ５，５が集約されている集約トラップドアｔｄ２，５のみが生成可能である。
また、サーバ装置２０１では、集約トラップドアｔｄ２，５からトラップドアｔｄ２，２〜ｔｄ５，５の各々を導出することができ、検索要求元のユーザが暗号鍵ｋ２，５を所持していることを検証することができる。
この結果、サーバ装置２０１では、暗号鍵に設定されている許可世代範囲である２世代目〜５世代目の範囲内で暗号化データを検索する。
【００６４】
なお、サーバ装置２０１が受信したトラップドアｔｄｓ，ｔから生成したｉ世代目のトラップドアｔｄｉ，ｉと、情報処理装置３０１が暗号化データ送信の際に、暗号鍵ｋｉ，ｉから生成したトラップドアが一致し、本秘匿検索システムが正常に機能することは、例えば以下のように確認される。
サーバ装置２０１がトラップドアｔｄｓ，ｔから生成したｉ世代目のトラップドアｔｄｉ，ｉは、
ｔｄｉ，ｉ＝Ｆ１ｔ−ｉ（Ｆ２ｉ−ｓ（ｔｄｓ，ｔ））
＝Ｆ１ｔ−ｉ（Ｆ２ｉ−ｓ（Ｇ（ｋｓ，ｔ，ｗ）））
＝Ｆ１ｔ−ｉ（Ｇ（Ｆ２ｉ−ｓ（ｋｓ，ｔ），ｗ））
＝Ｇ（Ｆ１ｔ−ｉ（Ｆ２ｉ−ｓ（ｋｓ，ｔ）），ｗ）
＝Ｇ（ｋｉ，ｉ，ｗ）
となり、これは情報処理装置３０１がｉ世代目に生成するトラップドアと一致する。
【００６５】
また、システムの安全性、すなわちサーバ装置２０１がトラップドアや暗号化キーワードからキーワードを類推できないことや、ある期間の暗号鍵を持つ情報処理装置３０１が期間外の暗号鍵を類推できず、検索も行えないことは、Ｆ１，Ｆ２，Ｈの一方向性、Ｇの入力推定困難性に基づいている。
特に、本実施の形態にて示した具体例においては、ＲＳＡ（登録商標）暗号の安全性に基づいている。
【００６６】
以上によって、情報処理装置３０１がデータ・キーワードをサーバ装置２０１に対して秘匿したまま検索できる秘匿検索システムが実現できる。
サーバ装置２０１が、受信したトラップドアから検索期間に対応する全てのトラップドアを生成できるため、検索時に情報処理装置３０１が送信すべきトラップドアが削減でき、情報処理装置３０１の計算量や通信量の削減を達成できる。
また、加入ユーザに対して検索可能期間を設定するという、柔軟性も達成している。
【００６７】
なお、本実施の形態では、キーワードｗをそのまま関数Ｇへの入力としているが、一方向性関数を適用するなどして、適当に変換したものを関数Ｇへの入力としても良い。
【００６８】
また、本実施の形態では、検索結果として暗号化データを返すために暗号化データ記憶領域２１２を利用しているが、暗号化データを返す必要がない場合、サーバ装置２０１が暗号化データ記憶領域２１２を持たなくても良い。
例えば、暗号化データは別の装置が保持し、そこへのアクセスを可能とするためにデータＩＤだけを返すようにしても良い。
【００６９】
また、本実施の形態では、異なるデータに関連付けられた同一のキーワードが別の暗号化キーワードとなるようにするため、暗号化キーワードをｃ＝Ｈ（ｉｄ，ｔｄ）のように生成しているが、この区別をつける必要がない場合、本処理を省略し、トラップドアを暗号化キーワードとして使うことも可能である。
この場合、検索時にサーバ装置２０１がｉｄごとにＨを適用する必要がなくなり、検索を高速化することができる。
【００７０】
また、本実施の形態では、グループ管理装置４０１が初期設定の際に、全ての暗号鍵ｋ１，１〜ｋｑ，ｑを生成し、暗号鍵記憶領域４１１に格納しているが、ｋ１，ｑのみを格納し、その他の暗号鍵は必要なときに随時導出するようにしても良い。
【００７１】
また、本実施の形態では、グループ管理装置４０１が初期設定の際に、全ての暗号鍵ｋ１，１〜ｋｑ，ｑを生成し、暗号鍵記憶領域４１１に格納しているが、Ｎの素因数分解ｐ１×ｐ２を知るグループ管理装置４０１はＦ１およびＦ２の逆関数を計算できるため、暗号鍵記憶領域４１１には最新の暗号鍵（例えばｔ世代目ではｋ１，ｔ）のみを格納し、世代更新のたびに次の暗号鍵（例えばｋ１，ｔ＋１）を導出するようにしても良い。
この場合、世代数の最大値（ｑ）という制限を設けることなく秘匿検索システムを運用することが可能となる。
つまり、グループ管理装置４０１は、予め、第１世代のみを許可世代範囲とする鍵ｋ１，１を初期鍵として生成し、鍵発行時に、ユーザごとに、利用開始世代から鍵発行時における最新世代までの世代範囲に対応させて暗号鍵を生成するようにしてもよい。
この場合は、初期鍵又は初期鍵から派生する鍵を生成元鍵とし、生成元鍵に関数Ｆ１（第１の関数）を適用して許可世代範囲の開始世代が生成元鍵の開始世代と共通し終了世代が生成元鍵の終了世代の１つ後の世代となる新たな鍵を生成する。この場合は、生成元鍵は、終了世代が生成対象の鍵の１世代前の鍵である。
または、生成元鍵にＦ２（第２の関数）を適用して許可世代範囲の終了世代が生成元鍵の終了世代と共通し開始世代が前記生成元鍵の開始世代の１つ後の世代となる新たな鍵を生成するようにしてもよい。この場合は、生成元鍵は、開始世代が生成対象の鍵の１世代前の鍵である。
【００７２】
また、本実施の形態では、情報処理装置３０１が暗号化データを送信する際に、トラップドアｔｄｘｊを計算するためにｋｔ，ｔを導出しているが、暗号鍵記憶領域３１１にｋｓ，ｔだけでなくｋｔ，ｔも格納しておくことで、暗号化ごとの計算量を削減することも可能である。
【００７３】
また、本実施の形態では、情報処理装置３０１が暗号化データを検索する際に、暗号鍵記憶領域３１１に格納されている暗号鍵ｋｓ，ｔを利用してトラップドアを作成することで、ｓ世代目からｔ世代目までの検索を行っているが、情報処理装置３０１が検索期間の短い別の暗号鍵ｋｉ，ｊ（ｓ≦ｉ≦ｊ≦ｔ）を導出してトラップドアを作成することで、ｉ世代目からｊ世代目までに限定した検索を行うことも可能である。
【００７４】
また、本実施の形態では、データに複数のキーワードが関連付けられている場合、各キーワードに対し暗号化キーワードを送信し、これらを暗号化キーワード記憶領域２１１の複数行に格納しているが、複数キーワードを効率的に処理するＢｌｏｏｍ  Ｆｉｌｔｅｒなどの既存技術と組み合わせて、複数キーワードを１行でまとめて処理できるようにしても良い。
【００７５】
以上、本実施の形態では、
（１）サーバに保存されたデータを、ユーザがキーワードを指定して検索でき、かつその際にデータ・キーワードをサーバに対して秘匿する秘匿検索システムで、検索の際に利用する秘密情報を世代ごとに更新するシステムにおいて、データ保存・検索時にユーザがサーバに送信するトラップドアを、サーバが最新のトラップドアから過去のトラップドアを導出できるようなものにすることで、検索時にユーザが送信すべきトラップドアの数を削減し、結果として計算量や通信量を削減する方式を説明した。
【００７６】
また、本実施の形態では、
（２）上記（１）において、関数Ｆ１，Ｆ２，Ｇを利用することで、加入ユーザの検索権限を柔軟に設定できる方式を説明した。
【００７７】
また、本実施の形態では、
（３）上記（２）において、ＲＳＡ（登録商標）暗号の安全性をベースとする方式を説明した。
【００７８】
実施の形態２．
本実施の形態では、加入ユーザに加入前の情報を検索させないという目的を、実施の形態１で述べたものと異なる手段で達成する方式について述べる。
【００７９】
まず、本実施の形態に係る装置構成等の詳細を説明する前に、本実施の形態の動作概要を説明する。
図２２及び図２３は、本実施の形態の動作概要を説明する図である。
【００８０】
まず、図２２を用いて鍵の生成手順、更新手順及び暗号化データの格納手順を概説する。
図２２において、αはいずれのユーザ及び情報処理装置１００１（本実施の形態では、情報処理装置１００１と表記する）に対しても秘密にしている秘密パラメータである。
秘密パラメータαは、グループ管理装置４０１からサーバ装置９０１（本実施の形態では、サーバ装置９０１と表記する）に通知される。
ｗは、ユーザが指定するキーワードである。
関数Ｆは、ある世代の暗号鍵から１つ前の世代の暗号鍵又はある世代のトラップドアから１つ前の世代のトラップドアを生成するための関数である。
関数Ｇは、暗号鍵からトラップドアを生成するための関数である。
【００８１】
グループ管理装置４０１では、最終世代の鍵ｋＭを生成するとともに、当該鍵ｋＭに関数Ｆを適用して１世代前の鍵ｋＭ−１を生成し、以降、新たに生成された鍵に関数Ｆを適用し、先頭世代の鍵である鍵ｋ０を生成する。なお、関数Ｆには、αべき乗の演算が含まれる。
グループ管理装置４０１は、まず、鍵ｋ０をグループの初期からグループに所属している所属ユーザの情報処理装置１００１に送信する。
更新イベントが発生し、鍵ｋｉから鍵の世代を更新する場合は、グループ管理装置４０１は、次の世代の鍵ｋｉ＋１を送信する。
情報処理装置１００１では、鍵の更新がある度に、それまで保持している鍵に、新たな鍵を合成して合成鍵を生成する。具体的には、鍵の積算を行う。
例えば、新たな鍵として鍵ｋ３が配布された場合は、情報処理装置１００１は、その時点での最新世代の鍵としてｋ２を保持し、また、ｋ０、ｋ１、ｋ２の積であるｋ０ｋ１ｋ２を保持している。
このため、情報処理装置１００１は、最新世代の鍵をｋ３に置換するとともに、保持している鍵の積に新たな鍵ｋ３を加えて、鍵ｋ０ｋ１ｋ２ｋ３に更新する。
また、各世代の鍵ｋｉに対して関数Ｇを適用すると、トラップドアｔｄｉが生成できる。
なお、関数Ｇには、ｗべき乗の演算が含まれている。
【００８２】
暗号化データの格納の際には、情報処理装置１００１において、ユーザから格納指示があった時点での最新世代の鍵とキーワードｗに対して関数Ｇを適用してトラップドアを生成する。
更に、トラップドアと暗号化データのデータＩＤに対して一方向性演算を行って暗号化キーワードを生成する。
そして、情報処理装置１００１は、暗号化データ、暗号化キーワード、最新世代の鍵の世代値、データＩＤをサーバ装置９０１に送信し、サーバ装置９０１はこれらを対応付けて格納する。
【００８３】
次に、図２３を用いて、暗号化データの検索手順を説明する。
ここでは、最新世代の鍵ｋ３を保有し、鍵の積ｋ０ｋ１ｋ２ｋ３を保有しているユーザが暗号化データを検索する場合を例にして説明する。
情報処理装置では、最新世代の鍵ｋ３とキーワードｗに対して関数Ｇを適用してトラップドアｔｄ３を生成する。
また、情報処理装置１００１は、鍵の積ｋ０ｋ１ｋ２ｋ３とキーワードｗに関数Ｇを適用して鍵の積に対応するトラップドアを生成する。ここでは、鍵ｋ０〜ｋ３に対応するトラップドアなのでｔｄ０，３と表記する。
情報処理装置１００１は、２つのトラップドアｔｄ３とｔｄ０，３をサーバ装置９０１に送信する。
なお、トラップドアｔｄ３は暗号化最新世代情報に相当し、トラップドアｔｄ０，３は、トラップドアｔｄ０〜ｔｄ３を集約した情報であるため、集約情報に相当する。
また、トラップドアｔｄ０，３は、サーバ装置９０１において、情報処理装置１００１が鍵ｋ０〜ｋ３の保持実績があるか否か、すなわち、第０世代〜第３世代に対応する暗号化データにアクセスする権限があるか否かを検証するためのトラップドアであり、検証用トラップドアという。
【００８４】
サーバ装置９０１では、トラップドアｔｄ３に、秘密パラメータαが含まれる関数Ｆを用いて、トラップドアｔｄ２を導出し、更に、トラップドアｔｄ２に関数Ｆを適用してトラップドアｔｄ１を導出し、最終的にトラップドアｔｄ０〜ｔｄ２を導出する。
更に、サーバ装置９０１は、導出したトラップドアｔｄ０〜ｔｄ２と情報処理装置１００１から受信したトラップドアｔｄ３の積が、トラップドアｔｄ０，３と一致するか否かを検証する。
一致する場合は、サーバ装置９０１は、情報処理装置１００１が鍵ｋ０〜ｋ３の保持実績がある、すなわち、第０世代〜第３世代に対応する暗号化データにアクセスする権限があると判断し、第０世代〜第３世代の範囲で暗号化データの検索を行う。
【００８５】
本実施の形態に係る方式の概要は以上であり、以下では、本実施の形態に係る方式を詳細に説明する。
【００８６】
秘匿検索システムの構成例は実施の形態１で述べたものと同様である。
【００８７】
図９は、本秘匿検索システム（図１）において、データ・キーワードを保持し、検索を行うサーバ装置９０１の構成例を表すブロック図である。
図９において、暗号化キーワード記憶領域２１１、暗号化データ記憶領域２１２、トラップドア生成部２２１、比較部２２２、通信部２３１に関しては、実施の形態１にて記述したものと同様であるため、説明は省略する。
関数パラメータ記憶領域９１３は、過去のトラップドア導出に必要な秘密パラメータを記憶するデータ記憶手段である。
ここには、グループ管理装置４０１から受信した単一の値が格納される。
トラップドア検証部９２３は、情報処理装置１００１から受信したトラップドアが、正当な検索権限を持った情報処理装置１００１が生成したものであるかを検証する手段である。
【００８８】
図１０は、本秘匿検索システム（図１）において、サーバ装置９０１への暗号化データの登録・サーバ装置９０１からの暗号化データの検索を行う情報処理装置１００１の構成例を表すブロック図である。
図１０において、トラップドア生成部３２１、暗号化キーワード生成部３２２、通信部３３１に関しては、実施の形態１にて記述したものと同様であるため、説明は省略する。
暗号鍵記憶領域３１１は、データの暗号化・検索に用いる秘密情報を記憶するデータ記憶手段である。
図１１は暗号鍵記憶領域３１１が記憶するデータの一例を表す。
図１１の例において、検証用暗号鍵ｋ１，３は、１世代目から３世代目までの秘密情報を検索する権限があることを、サーバ装置９０１に対して証明するための秘密情報である。
検証用トラップドア生成部１０２３は、情報処理装置１００１が、ある期間についての秘密情報を検索する権限があることを、サーバ装置９０１に対して証明するための検証用トラップドアを生成する手段である。
【００８９】
また、本実施の形態に係るグループ管理装置４０１の構成例は、実施の形態１で述べた図４から世代範囲記憶領域４４１を除いたものに相当する。
なお、本実施の形態に係るグループ管理装置４０１の構成例の図示は省略している。
【００９０】
図４において、暗号鍵生成部４２１、通信部４３１及び暗号鍵配布処理部４５１に関しては、実施の形態１にて記述したものと同様であるため、説明は省略する。
暗号鍵記憶領域４１１は、情報処理装置１００１が利用する暗号鍵を記憶するデータ記憶手段である。
図１３は暗号鍵記憶領域４１１が記憶するデータの一例を表す。
【００９１】
本実施の形態においても、本秘匿検索システムにおける手続きは、実施の形態１にて記述した五つの手続きに大別される。
以下、それぞれの手続きについて説明する。
【００９２】
（１）グループ管理装置の初期設定
グループ管理装置４０１は、パラメータｑ、および可換な二つの関数Ｆ（ｘ，ｙ），Ｇ（ｘ，ｙ）を決定し、公開情報とする。
ここで、ＦとしてはｘとＦ（ｘ，ｙ）からｙを推定することが困難な関数を選び、またＧとしては、関数の出力から実際の入力を推定することが困難であり、かつｘに関して準同型性を持つ関数を選ぶ。
また、ＦとＧの可換性とは、Ｆ（Ｇ（ｘ，ｙ），ｚ）＝Ｇ（Ｆ（ｘ，ｚ），ｙ）を意味するものとする。
ｑは世代数の最大値（最終世代）であり、世代の更新頻度やシステムの運用期間から適切に設定する。
また、関数Ｆのパラメータとなる秘密パラメータαを決定する。
さらに、適当な一方向性関数Ｈを選択し、公開情報とする。
本実施の形態では、Ｆ，Ｇの具体例として、以下に基づき決定したものを利用する。
ｐとして十分大きな素数を選び、Ｆ，Ｇを以下で定める。
Ｆ（ｘ，ｙ）＝ｘｙ  ｍｏｄ  ｐ
Ｇ（ｘ，ｙ）＝ｘｙ  ｍｏｄ  ｐ
このとき、Ｇは以下の準同型性を持つ。
Ｇ（ｘ１ｘ２，ｙ）＝Ｇ（ｘ１，ｙ）Ｇ（ｘ２，ｙ）
また、αを巡回群Ｚｐ＊から、ｐ−１と互いに素となるようランダムに選択する。
【００９３】
次に、暗号鍵生成部４２１による鍵生成動作の詳細を図３３のフローチャートを参照しながら説明する。
暗号鍵生成部４２１は、情報処理装置１００１が利用する暗号鍵ｋｉ（１≦ｉ≦ｑ）を生成する。
【００９４】
まず、暗号鍵生成部４２１は、暗号鍵ｋｑ（最終世代の鍵）を、巡回群Ｚｐ＊の生成元からランダムに選択する（Ｓ３３０１）。
そして、初期鍵である暗号鍵ｋｑに対して所定の鍵生成関数を適用して、新たな暗号鍵を生成し、以降、生成済みの鍵に鍵生成関数を適用して、各鍵間に連続性を持たせながら、生成済みの鍵とは別の世代の鍵を生成する。
具体的には、暗号鍵ｋｑ以外の暗号鍵ｋｉ（１≦ｉ＜ｑ）を、以下の式に従って順次計算する（Ｓ３３０２）。
ｋｉ−１＝Ｆ（ｋｉ，α）
【００９５】
このように、暗号鍵生成部４２１は、初期鍵である暗号鍵ｋｑと秘密パラメータαに対して鍵生成関数Ｆを適用して、最終世代の１つ前の世代の新たな暗号鍵ｋｑ−１を生成し、生成した暗号鍵ｋｑ−１と秘密パラメータαに対して鍵生成関数Ｆを適用して更に１つ前の世代の暗号鍵ｋｑ−２を生成し、以降、新たに生成した鍵と秘密パラメータαに対して鍵生成関数Ｆを適用する動作を繰り返して、第１世代から最終世代の暗号鍵ｋ１〜ｋｑを生成する。
【００９６】
こうして得られた全ての暗号鍵ｋ１〜ｋｑを、暗号鍵生成部４２１は、暗号鍵記憶領域４１１に格納する（Ｓ３３０３）。
そして、暗号鍵配布処理部４５１が１世代目の暗号鍵ｋ１を暗号鍵記憶領域４１１から取得し、通信部４３１が、全ての正当な情報処理装置１００１に、１世代目の暗号鍵ｋ１を送信する（Ｓ３３０４）。
これは、暗号鍵の安全性が保たれる方式であれば、オフラインで行っても良いし、既存の鍵配送技術を用いてオンラインで行っても良い。
暗号鍵ｋ１を受信した情報処理装置１００１は、この暗号鍵ｋ１を、世代とともに暗号鍵記憶領域３１１に格納する。
また、検索開始世代（利用開始世代）として１を、検証用暗号鍵ｋ１，１として暗号鍵ｋ１と同じ値を格納する（図１２）。
最後に、通信部４３１が、サーバ装置９０１に、秘密パラメータαを送信する（Ｓ３３０５）。
これは、安全性が保たれる方式であれば、オフラインで行っても良いし、既存技術を用いてオンラインで行っても良い。
秘密パラメータαを受信したサーバ装置９０１は、この秘密パラメータαを、関数パラメータ記憶領域９１３に格納する。
【００９７】
（２）加入ユーザへの暗号鍵配布
ｔ世代目においてユーザの加入があった際、加入した情報処理装置１００１に対して暗号鍵を配布する。
加入ユーザに対して、ｔ世代目を含めた、ｓ世代目からｔ世代目まで（ｓ≦ｔ）の秘密情報の検索を許す場合、グループ管理装置４０１の通信部４３１が、加入した情報処理装置１００１に、暗号鍵ｋｔ、以下で導出される検証用暗号鍵ｋｓ，ｔ、および世代情報ｓ，ｔを送信する。なお、以下の式は、鍵の（巡回群における）積を表している。
ｋｓ，ｔ＝ｋｓｋｓ＋１…ｋｔ
これは、暗号鍵の安全性が保たれる方式であれば、オフラインで行っても良いし、既存の鍵配送技術を用いてオンラインで行っても良い。
これらを受信した情報処理装置１００１は、暗号鍵記憶領域３１１に、世代としてｔを、暗号鍵としてｋｔを、検索開始世代としてｓを、検証用暗号鍵としてｋｓ，ｔを格納する。
この場合、次で述べる「（３）暗号鍵の世代更新」の処理は不要である（行っても良い）。
一方、加入ユーザに対して、ｔ世代目の秘密情報の検索を許さない場合、グループ管理装置４０１の通信部４３１が、加入した情報処理装置１００１に、暗号鍵および検証用暗号鍵としてｋｔ＋１を、世代および検索開始世代としてｔ＋１を送信する。
これは、暗号鍵の安全性が保たれる方式であれば、オフラインで行っても良いし、既存の鍵配送技術を用いてオンラインで行っても良い。
これらを受信した情報処理装置１００１は、暗号鍵記憶領域３１１に、世代としてｔ＋１を、暗号鍵としてｋｔ＋１を、検索開始世代としてｔ＋１を、検証用暗号鍵ｋｔ＋１，ｔ＋１としてｋｔ＋１を格納する。
その後、ｔ世代目からｔ＋１世代目に更新するために、次で述べる「（３）暗号鍵の世代更新」の処理が実行される。
【００９８】
図３４は、以上の（２）加入ユーザへの暗号鍵配布における動作を示すフローチャートである。
暗号鍵配布処理部４５１は、例えば、グループ管理装置４０１のオペレータからの入力に基づき、新たに加入する加入ユーザに許容される世代範囲を判断する（Ｓ３４０１）。
加入ユーザにｓ世代〜ｔ世代が認められる場合は、暗号鍵配布処理部４５１は、暗号鍵ｋｓ〜暗号鍵ｋｔを暗号鍵記憶領域４１１から取得し、取得した暗号鍵ｋｓ〜暗号鍵ｋｔを積算して検証用暗号鍵ｋｓ，ｔを生成し、暗号鍵ｋｔ、検証用暗号鍵ｋｓ，ｔ、世代情報（ｓ、ｔ）を通信部４３１が当該ユーザの情報処理装置３０１に送信する（Ｓ３４０２）。
一方、Ｓ３４０１の判断において、新規に加入するユーザにｔ世代が許可されない場合は、暗号鍵配布処理部４５１は、暗号鍵ｋｔ＋１を暗号鍵記憶領域４１１から取得し、通信部４３１が当該ユーザの情報処理装置３０１に暗号鍵ｋｔ＋１と世代情報（ｔ＋１）を送信する（Ｓ３４０３）。
また、この後、図３５に示す世代更新処理が行われる（Ｓ３４０４）。
【００９９】
（３）暗号鍵の世代更新
正当な情報処理装置１００１のグループに対し、ユーザの加入・脱退があった際に、暗号鍵の世代更新が必要となる場合がある。
このようなユーザの加入（上記のｔ世代目の秘密情報の検索を認めないユーザの加入）及びユーザの脱退が更新イベントとなる。
更新イベントが発生した場合には、以下のように世代更新を実施する。
【０１００】
ｔ世代目からｔ＋１世代目に更新する場合（ただしｔ＋１≦ｑ）、グループ管理装置４０１の通信部４３１が、（加入ユーザを除く）全ての正当な情報処理装置１００１（所属ユーザが利用している情報処理装置１００１）に、ｔ＋１世代目の暗号鍵ｋｔ＋１を送信する。
これは、暗号鍵の安全性が保たれる方式であれば、オフラインで行っても良いし、既存の鍵配送技術を用いてオンラインで行っても良い。
暗号鍵ｋｔ＋１を受信した情報処理装置１００１は、暗号鍵記憶領域３１１の内容のうち、世代をｔ＋１に、暗号鍵をｋｔ＋１に、検証用暗号鍵ｋｓ，ｔを以下で導出されるｋｓ，ｔ＋１に置き換える。
ｋｓ，ｔ＋１＝ｋｓ，ｔｋｔ＋１（＝ｋｓｋｓ＋１…ｋｔｋｔ＋１）
【０１０１】
なお、グループを脱退した者がいる場合には、当該脱退者には、更新後の最新世代の鍵が配布されない。
このため、脱退者は、脱退前にサーバ装置９０１に登録されている暗号化データには、保持している暗号鍵を用いてアクセスすることができるが、脱退後にサーバ装置９０１に登録された暗号化データには、更新後の暗号鍵を保有していないのでアクセスできない。
なお、以前の暗号化データを含め一切の暗号化データに脱退者がアクセスできないようにすることもできる。
【０１０２】
図３５は、以上の（３）暗号鍵の世代更新における動作を説明するフローチャートである。
更新イベントが発生した場合、つまり、ユーザの脱退又は世代更新が必要なユーザの加入があった場合（Ｓ３５０１でＹＥＳ）、暗号鍵配布処理部４５１は、ｔ＋１世代に対応する暗号鍵ｋｔ＋１を暗号鍵記憶領域４１１から取得する（Ｓ３５０２）。
そして、通信部４３１が各所属ユーザの情報処理装置３０１に暗号鍵ｋｔ＋１を送信する（Ｓ３５０３）。
【０１０３】
（４）暗号化データの送信・格納
正当な情報処理装置１００１がデータをサーバ装置９０１に送信する場合、後に秘匿検索が行えるよう、キーワードとデータを別々に暗号化したものを送信する。
ｔ世代目における具体的な手順を以下に述べる。
なお、動作のフローチャートは、図２９及び図３０と同様である。
【０１０４】
まず、情報処理装置１００１は、データに対し、ユニークなデータＩＤを割り当てる（ｉｄｘとする）。
さらに、情報処理装置１００１は、データの暗号化を行う。
ここでは、正当な情報処理装置１００１だけが復号できるような、既存の暗号技術（グループ暗号技術）を利用する（暗号化データをｄｘとする）。
次に、トラップドア生成部３２１が、データに関連付けられた複数のキーワード（ｗｘｊとする）に対し、それぞれトラップドアを生成する。
具体的には、暗号鍵記憶領域３１１に格納されている暗号鍵ｋｔを利用して、各キーワードｗｘｊに対し、トラップドアｔｄｘｊを以下のように計算する。
ｔｄｘｊ＝Ｇ（ｋｔ，ｗｘｊ）
その後、暗号化キーワード生成部３２２が、各トラップドアｔｄｘｊに対し、暗号化キーワードｃｘｊを以下のように計算する。
ｃｘｊ＝Ｈ（ｉｄｘ，ｔｄｘｊ）
最後に、通信部３３１が、世代、データＩＤ、暗号化データ、暗号化キーワードの組（ｔ，ｉｄｘ，ｄｘ，ｃｘ１，ｃｘ２，．．．）をサーバ装置９０１に送信する。
【０１０５】
これらを受信したサーバ装置９０１は、暗号化データｄｘをデータＩＤと関連付けて暗号化データ記憶領域２１２に格納し、各暗号化キーワードｃｘｊを世代、データＩＤと関連付けて暗号化キーワード記憶領域２１１に格納する。
【０１０６】
（５）暗号化データの検索・取得
正当な情報処理装置１００１は、現在もしくは過去の世代にサーバ装置９０１に格納されたデータに対し、キーワードを指定して秘匿検索を行うことができる。
暗号鍵ｋｔ、検証用暗号鍵ｋｓ，ｔを持つ正当な情報処理装置１００１が、ｓ世代目からｔ世代目までの検索を行う具体的な手順を図３６及び図３７を参照しながら以下に述べる。
【０１０７】
まず、情報処理装置１００１は、暗号化データの検索指示として、ユーザから検索対象のキーワードｗを入力する（Ｓ３６０１）。
次に、トラップドア生成部３２１が、検索したいキーワードｗに対応するトラップドアを生成する（Ｓ３６０２）。
具体的には、キーワードｗに対し、トラップドアｔｄｔを以下のように計算する。
なお、ｋｔは、ユーザの検索指示時点での最新世代の暗号鍵である。
ｔｄｔ＝Ｇ（ｋｔ，ｗ）
このトラップドアｔｄｔは、暗号化最新世代情報に相当する。
さらに、情報処理装置１００１の検証用トラップドア生成部１０２３が、ｓ世代目からｔ世代目までを検索する権限があることをサーバ装置９０１に対して証明するための検証用トラップドアｔｄｓ，ｔを以下のように計算する（Ｓ３６０３）。
なお、ｋｓ，ｔは、鍵ｋｓ〜鍵ｋｔの積である。
ｔｄｓ，ｔ＝Ｇ（ｋｓ，ｔ，ｗ）
次に、通信部３３１が、検索開始世代（ｓ）、検索終了世代（ｔ）、トラップドア、検証用トラップドアの組（ｓ，ｔ，ｔｄｔ，ｔｄｓ，ｔ）をサーバ装置９０１に送信する（Ｓ３６０４）。
【０１０８】
サーバ装置９０１では、通信部２３１が検索要求を受信し（Ｓ３７０１）、トラップドア生成部２２１が、ｓ世代目からｔ−１世代目までのそれぞれに対応するトラップドアｔｄｓ〜ｔｄｔ−１を以下のように順次計算する（Ｓ３７０２）。
ｔｄｉ−１＝Ｆ（ｔｄｉ，α）  （ｓ＜ｉ≦ｔ）
そして、トラップドア検証部９２３が、導出したトラップドアｔｄｓ〜ｔｄｔと、受信した検証用トラップドアｔｄｓ，ｔの整合性を確認する（Ｓ３７０３）。
具体的には、以下の等式が成立するか否かを確認する。
ｔｄｓｔｄｓ＋１…ｔｄｔ＝ｔｄｓ，ｔ
【０１０９】
この等式が成立しなかった場合（Ｓ３７０４でＮＯ）、情報処理装置１００１に正当な検索権限がないとみなし、処理を終了する。
等式が成立した場合（Ｓ３７０４でＹＥＳ）、実際の検索処理を実行する（Ｓ３７０５、Ｓ３７０６）。
すなわち、比較部２２２が、暗号化キーワード記憶領域２１１を参照し、トラップドアに対応する暗号化キーワードが存在するかを確認する。
具体的には、暗号化キーワード記憶領域２１１の各行の世代、データＩＤ、暗号化キーワードの組（ｊ，ｉｄ，ｃ）に対し、以下の等式が成立するかを確認する。
ｃ＝Ｈ（ｉｄ，ｔｄｊ）
成立した場合はｃが指定されたキーワードｗに対応する暗号化キーワードとなるため、暗号化データ記憶領域２１２を参照してｉｄから暗号化データｄを取得する（Ｓ３７０７）。
そして、通信部２３１が情報処理装置１００１に、キーワードｗに対応する暗号化データｄを送信する（Ｓ３７０８）。
等式が複数成立した場合は全て送信するようにしても、一部を送信するようにしても良い。
上記の等式が暗号化キーワード記憶領域２１１のどの行においても不成立であった場合は、その旨を送信する。
【０１１０】
暗号化データｄを受信した情報処理装置１００１は、ｄの復号を行う。
ここでは、正当な情報処理装置１００１だけが復号できるような、既存の暗号技術（グループ暗号技術）を利用する。
【０１１１】
なお、サーバ装置９０１が受信したトラップドアｔｄｔから生成したｉ世代目のトラップドアｔｄｉと、情報処理装置１００１が暗号化データ送信の際に、暗号鍵ｋｉから生成したトラップドアが一致し、本秘匿検索システムが正常に機能することは、例えば以下のように確認される。
サーバ装置９０１がトラップドアｔｄｔから生成したｉ世代目のトラップドアｔｄｉは、
ｔｄｉ＝Ｆｔ−ｉ（ｔｄｔ，α）
＝Ｆｔ−ｉ（Ｇ（ｋｔ，ｗ），α）
＝Ｇ（Ｆｔ−ｉ（ｋｔ，α），ｗ）
＝Ｇ（ｋｉ，ｗ）
となり、これは情報処理装置１００１がｉ世代目に生成するトラップドアと一致する
（ここで、例えばＦ２（ｘ，ｙ）はＦ（Ｆ（ｘ，ｙ），ｙ）を表す。以下においても同様）。
【０１１２】
さらに、サーバ装置９０１が受信したトラップドアｔｄｔから導出したトラップドアｔｄｓ〜ｔｄｔと、受信した検証用トラップドアｔｄｓ，ｔの間に整合性があり、検索権限の確認が正常に機能することは、例えば以下のように確認される。
ｔｄｉ＝Ｇ（ｋｉ，ｗ）
ｔｄｓｔｄｓ＋１…ｔｄｔ＝Ｇ（ｋｓ，ｗ）Ｇ（ｋｓ＋１，ｗ）…Ｇ（ｋｔ，ｗ）
＝Ｇ（ｋｓｋｓ＋１…ｋｔ，ｗ）
＝Ｇ（ｋｓ，ｔ，ｗ）
＝ｔｄｓ，ｔ
【０１１３】
また、システムの安全性、すなわちサーバ装置９０１がトラップドアや暗号化キーワードからキーワードを類推できないことや、ある期間の暗号鍵を持つ情報処理装置１００１が期間外の暗号鍵を類推できず、検索も行えないことは、Ｆ，Ｇの入力推定困難性、Ｈの一方向性に基づいている。
特に、本実施の形態にて示した具体例においては、離散対数問題の安全性に基づいている。
【０１１４】
以上によって、情報処理装置１００１がデータ・キーワードをサーバ装置９０１に対して秘匿したまま検索できる秘匿検索システムが実現できる。
サーバ装置９０１が、受信したトラップドアから検索期間に対応する全てのトラップドアを生成できるため、検索時に情報処理装置１００１が送信すべきトラップドアが削減でき、情報処理装置１００１の計算量や通信量の削減を達成できる。また、加入ユーザに対して検索可能期間を設定するという、柔軟性も達成している。
【０１１５】
なお、実施の形態１にて記述したバリエーションは、本実施の形態においても同様に適用可能である。
例えば、本実施の形態では、グループ管理装置４０１は、最終世代から第１世代の鍵に遡って全世代の鍵を生成し、全世代の鍵を記憶し、鍵更新タイミングにおいて、記憶している鍵の中から該当する鍵を抽出して、情報処理装置１００１に送信することとしている。
これに代えて、グループ管理装置４０１は、予め、第１世代の鍵を生成し、鍵発行時に、鍵発行時点での最新世代に対応させて、第１世代の鍵又は第１世代の鍵から派生する鍵を生成元鍵とし、生成元鍵と秘密パラメータαに対して鍵生成関数Ｆを適用して、生成元鍵の１つ後の世代の新たな鍵を最新世代の鍵として生成し、生成した最新世代の鍵をユーザに発行するようにしてもよい。
【０１１６】
また、本実施の形態では、情報処理装置１００１の暗号鍵記憶領域３１１に記憶する秘密情報を削減するために、秘密情報としては最新世代の暗号鍵と検証用暗号鍵のみを格納しているが、全ての世代の暗号鍵を格納するようにしても良い。
この場合、情報処理装置１００１が検索期間の短い別の検証用暗号鍵ｋｉ，ｊ（ｓ≦ｉ≦ｊ≦ｔ）を導出してトラップドアを作成することで、ｉ世代目からｊ世代目までに限定した検索を行うことも可能である。
【０１１７】
以上、本実施の形態では、関数Ｆ，Ｇを利用することで、加入ユーザの検索権限を柔軟に設定できる方式を説明した。
更に、本実施の形態では、巡回群における離散対数問題の安全性をベースとする方式を説明した。
【０１１８】
実施の形態３．
本実施の形態では、脱退ユーザとして「異動ユーザ」「退職ユーザ」の、検索権限の異なるユーザが混在する場合に、秘匿検索を実現するという目的を達成する方式について述べる。
なお、本実施の形態において、「異動ユーザ」「退職ユーザ」の用語は以下の意味で用いる。
異動ユーザ：
グループからは脱退し、脱退以降の情報は検索できなくなるが、脱退以前の情報に関しては脱退以前と同じように検索できるユーザ。
つまり、グループから脱退したが脱退前にサーバ装置１４０１（本実施の形態では、サーバ装置１４０１と表記する）に格納された暗号化データに対しては検索が許容されるユーザである。
異動ユーザは、限定ユーザの例である。
退職ユーザ：
グループから脱退し、脱退以前に検索できた情報も含めた全ての情報が検索できなくなる者。
つまり、グループから脱退しサーバ装置１４０１の暗号化データに対する検索が禁止される者である。
退職ユーザは、禁止ユーザの例である。
【０１１９】
また、グループに所属しているユーザ（異動ユーザでも、退職ユーザでもないユーザ）は、所属ユーザという。
所属ユーザは、サーバ装置１４０１の暗号化データに対する検索が許容される。
このため、本実施の形態に係るグループ管理装置４０１では、所属ユーザ、異動ユーザ、退職ユーザの３つのユーザカテゴリーが設けられている。
なお、本実施の形態では、説明の簡明化のため、グループに途中から加入する者がない形態（更新イベントはグループからの脱退のみ）を前提に説明を行う。
【０１２０】
まず、本実施の形態に係る装置構成等の詳細を説明する前に、本実施の形態の動作概要を説明する。
図２４及び図２５は、本実施の形態の動作概要を説明する図である。
【０１２１】
まず、図２４を用いて鍵の生成手順を概説する。
本実施の形態では、暗号鍵はｋｉ，ｊという表記を用いる。値ｉ及びｊは、鍵の世代値を示す。ｉは、退職ユーザが発生した際に値が更新される退職ユーザ対応値（禁止ユーザ対応値）であり、ｊは、異動ユーザが発生した際に値が更新される異動ユーザ対応値（限定ユーザ対応値）である。
例えば、鍵ｋ２，２は、退職ユーザ対応値が第２世代であり、異動ユーザ対応値が第２世代であり、退職及び異動がそれぞれ２回ずつ発生したことを意味している。
各暗号鍵ｋｉ，ｊには、サーバ装置１４０１においてトラップドアから退職ユーザ対応値ｉ及び異動ユーザ対応値ｊが導出可能なように、退職ユーザ対応値ｉ及び異動ユーザ対応値ｊが設定されている。
関数Ｆ１は、ある世代の異動ユーザ対応値が設定されている暗号鍵から１つ前の世代の異動ユーザ対応値の暗号鍵又はある世代の異動ユーザ対応値が設定されているトラップドアからの１つ前の世代の異動ユーザ対応値のトラップドアを生成するための関数である。
関数Ｆ２は、ある世代の退職ユーザ対応値が設定されている暗号鍵から１つ前の世代の退職ユーザ対応値の暗号鍵又はある世代の退職ユーザ対応値が設定されているトラップドアからの１つ前の世代の退職ユーザ対応値のトラップドアを生成するための関数である。
関数Ｆ１は第１の関数に相当し、関数Ｆ２は第２の関数に相当する。
【０１２２】
グループ管理装置４０１では、最終世代の鍵ｋｑ１、ｑ２を生成するとともに、当該鍵ｋｑ１、ｑ２に関数Ｆ１を適用して異動ユーザ対応値が１世代前の鍵ｋｑ１、ｑ２−１を生成する。
また、最終世代の鍵ｋｑ１、ｑ２に関数Ｆ２を適用して退職ユーザ対応値が１世代前の鍵ｋｑ１−１、ｑ２を生成する。
関数Ｆ１及びＦ２の適用を繰り返して、各鍵間に連続性を持たせながら、退職ユーザ対応値の全世代及び異動ユーザ対応値の全世代が含まれる全ての組み合わせパターンに対応する鍵ｋ０、０〜ｋｑ１、ｑ２を生成し、生成した鍵ｋ０、０〜ｋｑ１、ｑ２を記憶する。
また、グループに所属している所属ユーザの情報処理装置１００１に初回の鍵として鍵ｋ０、０を送信する。
なお、この時点では、グループからの脱退は発生していない。
【０１２３】
また、グループ管理装置４０１は、先頭世代の鍵である鍵ｋ０、０と、いずれのユーザ及び情報処理装置１００１にも公開されている公開値である特別なキーワードｗ０を用いて特別な暗号化キーワードｃ０を生成し、サーバ装置１４０１に特別な暗号化キーワードｃ０を送信する。サーバ装置１４０１では、特別な暗号化キーワードｃ０を記憶する。
特別な暗号化キーワードｃ０は、公開値である特別なキーワードｗ０と鍵ｋ０、０を用いているため、鍵ｋ０、０を保有する正当な情報処理装置１００１であれば、特別な暗号化キーワードｃ０を導出可能なトラップドアを生成することができる。
なお、特別な暗号化キーワードｃ０は、先頭世代暗号値に相当する。
【０１２４】
次に、図２５を用いて鍵の更新手順及び暗号化データの検索手順を概説する。
最新世代の鍵が鍵ｋ０、０であるときに、異動１が発生すると、所属ユーザには、異動ユーザ対応値が更新された新たな鍵ｋ０、１が配布される。一方、異動１で異動した異動ユーザ１には、新たな鍵は配布されない。
次に、最新世代の鍵が鍵ｋ０、１であるときに、退職１が発生すると、所属ユーザには、所属ユーザ向け鍵ｋ１、１が配布される。所属ユーザ向け鍵ｋ１、１は、退職ユーザ対応値が更新された値となっている。
また、異動１で異動した異動ユーザ１には、異動ユーザ向け鍵ｋ１、０が配布される。異動ユーザ向け鍵ｋ１、０は、退職ユーザ対応値が更新された値（１）となり異動ユーザ対応値は当該異動ユーザの異動前の値（０）のままである。
同様に、最新世代の鍵が鍵ｋ１、１であるときに、異動２が発生すると、所属ユーザには、異動ユーザ対応値が更新された新たな鍵ｋ１、２が配布される。
異動２で異動した異動ユーザ２には、新たな鍵は配布されない（鍵ｋ１、１のまま）。
また、異動１で異動した異動ユーザ１にも新たな鍵は配布されない（鍵ｋ１、０のまま）。
最新世代の鍵が鍵ｋ１、２であるときに、退職２が発生すると、所属ユーザには、所属ユーザ向け鍵ｋ２、２が配布される。
鍵ｋ１、０を保持している異動ユーザ１には異動ユーザ鍵ｋ２、０が配布され、鍵ｋ１、１を保持している異動ユーザ２には異動ユーザ鍵ｋ２、１が配布される。
【０１２５】
なお、鍵の更新がある度に、グループ管理装置４０１からサーバ装置１４０１に最新世代の鍵の世代値が通知される。
この例では、異動１の際に、最新世代の世代値として（０，１）が通知され、退職１の際に（１，１）が通知され、異動２の際に（２，１）が通知され、退職２の際に（２，２）が通知される。
サーバ装置１４０１は、都度、通知された世代値を記憶する。
【０１２６】
また、暗号化データの格納手順は、実施の形態１と同様であり、情報処理装置１００１は、保持している最新世代の鍵とキーワードに所定の関数Ｇを適用してトラップドアを生成し、また、トラップドアとデータＩＤに所定の関数Ｈを適用して、暗号化キーワードを生成する。
また、情報処理装置１００１は、暗号化データ、データＩＤ、暗号化キーワード、鍵の世代値をサーバ装置１４０１に送信し、サーバ装置１４０１では、これらを対応付けて記憶する。
なお、本実施の形態では、鍵の世代値は、（ｉ，ｊ）のようになる。
ｉは退職ユーザ対応値であり、ｊは異動ユーザ対応値である。
【０１２７】
ここで、所属ユーザが鍵ｋ２、２を保持し、異動ユーザ１が鍵ｋ２、０を保持し、異動ユーザ２が鍵ｋ２、１を保持している状況での暗号化データの検索手順を説明する。
所属ユーザが利用している情報処理装置１００１は、最新世代の鍵ｋ２、２とキーワードｗに対して所定の関数Ｇを適用してトラップドアを生成する。
このトラップドアは、実施の形態１と同様に、鍵ｋ０、０〜鍵ｋ２、２に含まれる鍵ｋ０、０、ｋ０、１、ｋ０、２、ｋ１、０、ｋ１、１、ｋ１、２、ｋ２、０、ｋ２、１、ｋ２、２に対応するトラップドアｔｄ０、０、ｔｄ０、１、ｔｄ０、２、ｔｄ１、０、ｔｄ１、１、ｔｄ１、２、ｔｄ２、０、ｔｄ２、１、ｔｄ２、２が集約されている集約トラップドアである。ここでは、集約トラップドアｔｄ（２、２）と表記する。
また、所属ユーザが利用している情報処理装置１００１は、最新世代の鍵ｋ２、２と特別なキーワードｗ０に対して所定の関数Ｇを適用して検証用トラップドアｔｄｖを生成する。
検証用トラップドアｔｄｖは、照合用情報に相当する。
また、所属ユーザが利用している情報処理装置１００１は、集約トラップドアｔｄ（２、２）と検証用トラップドアｔｄｖをサーバ装置１４０１に送信する。
サーバ装置１４０１では、検証用トラップドアｔｄｖに対して関数Ｆ１及びＦ２を適用して、鍵ｋ０、０に対応するトラップドアｔｄ０、０を導出し、導出したトラップドアｔｄ０、０に対して特別なＩＤであるｉｄ０を適用し、暗号化キーワードｃ０が得られるか否かを検証し、検証に成功した場合に、集約トラップドアｔｄ（２、２）を用いた暗号化データの検索を行う。
具体的には、実施の形態１と同様に、集約トラップドアｔｄ（２、２）に関数Ｆ１及びＦ２を適用して、トラップドアｔｄ０、０、ｔｄ０、１、ｔｄ０、２、ｔｄ１、０、ｔｄ１、１、ｔｄ１、２、ｔｄ２、０、ｔｄ２、１、ｔｄ２、２を導出し、各トラップドアとインデックス情報との照合により当該ユーザに許可されている（０，０）〜（２，２）の世代範囲内で暗号化データを検索する。
【０１２８】
異動ユーザ１が利用している情報処理装置１００１は、保持している鍵ｋ２、０とキーワードｗに対して所定の関数Ｇを適用してトラップドアを生成する。
このトラップドアは、実施の形態１と同様に、鍵ｋ０、０〜鍵ｋ２、０に含まれる鍵ｋ０、０、ｋ１、０、ｋ２、０に対応するトラップドアｔｄ０、０、ｔｄ１、０、ｔｄ２、０が集約されている集約トラップドアである。ここでは、集約トラップドアｔｄ（２、０）と表記する。
また、異動ユーザ１が利用している情報処理装置１００１は、最新世代の鍵ｋ２、０と特別なキーワードｗ０に対して所定の関数Ｇを適用して検証用トラップドアｔｄｖを生成する。
また、異動ユーザ１が利用している情報処理装置１００１は、集約トラップドア（２、０）と検証用トラップドアｔｄｖをサーバ装置１４０１に送信する。
サーバ装置１４０１では、検証用トラップドアｔｄｖに対して関数Ｆ１及びＦ２を適用して、鍵ｋ０、０に対応するトラップドアｔｄ０、０を導出し、導出したトラップドアｔｄ０、０に対して特別なＩＤであるｉｄ０を適用し、暗号化キーワードｃ０が得られるか否かを検証し、検証に成功した場合に、集約トラップドアｔｄ（２、０）を用いた暗号化データの検索を行う。
具体的には、実施の形態１と同様に、集約トラップドアｔｄ（２、０）に関数Ｆ１及びＦ２を適用して、トラップドアｔｄ０、０、ｔｄ１、０、ｔｄ２、０を導出し、各トラップドアとインデックス情報との照合により当該ユーザに許可されている（０，０）、（１，０）、（２，０）の世代範囲内で暗号化データを検索する。
また、異動ユーザ２の場合も、使用する鍵の世代、トラップドアの種類・個数が異なるのみであり、異動ユーザ１の場合と同様である。
異動ユーザ２の場合は、（０，０）、（１，０）、（２，０）、（０，１）、（１，１）、（２，１）の世代範囲内で暗号化データが検索される。
【０１２９】
このように、本実施の形態では、鍵ｋｉ，ｊに関して、最新の鍵ｋ２，ｊを持つユーザのみが、ｊの範囲内でｉ＝０〜２の世代範囲に合致する暗号化データの検索が可能である。
【０１３０】
本実施の形態に係る方式の概要は以上であり、以下では、本実施の形態に係る方式を詳細に説明する。
【０１３１】
秘匿検索システムの構成例は実施の形態１で述べたものと同様である。
【０１３２】
図１４は、本秘匿検索システム（図１）において、データ・キーワードを保持し、検索を行うサーバ装置１４０１の構成例を表すブロック図である。
図１４において、暗号化データ記憶領域２１２、トラップドア生成部２２１、比較部２２２、トラップドア検証部９２３、通信部２３１に関しては、実施の形態１および２にて記述したものと同様であるため、説明は省略する。
暗号化キーワード記憶領域２１１は、暗号化されたキーワードを、対応するデータＩＤ、および世代と関連付けて記憶するデータ記憶手段である。
図１５は暗号化キーワード記憶領域２１１が記憶するデータの一例を表す。
図１５において、データＩＤ、および暗号化キーワードｉｄ０，ｃ０は、情報処理装置１００１の検索権限を検証するための特別な情報である。
世代遷移記憶領域１４１３は、二次元で管理された世代情報の遷移を記憶するデータ記憶手段である。
図１６は世代遷移記憶領域１４１３が記憶するデータの一例を表す。
【０１３３】
情報処理装置の構成例は実施の形態２で述べたものと同様（図１０）である。
図１０において、トラップドア生成部３２１、暗号化キーワード生成部３２２、検証用トラップドア生成部１０２３、通信部３３１に関しては、実施の形態２にて記述したものと同様であるため、説明は省略する。
暗号鍵記憶領域３１１は、データの暗号化・検索に用いる秘密情報を記憶するデータ記憶手段である。
図１７は暗号鍵記憶領域３１１が記憶するデータの一例を表す。
【０１３４】
グループ管理装置の構成例は実施の形態１で述べたものと同様（図４）である。
図４において、暗号鍵生成部４２１、通信部４３１に関しては、実施の形態１にて記述したものと同様であるため、説明は省略する。
暗号鍵記憶領域４１１は、情報処理装置１００１が利用する暗号鍵を記憶するデータ記憶手段である。
図１８は暗号鍵記憶領域４１１が記憶するデータの一例を表す。
【０１３５】
本実施の形態においては、本秘匿検索システムにおける手続きは、（１）グループ管理装置４０１が初期設定を行う部分、（２）異動ユーザの発生に伴い、グループ管理装置４０１が、情報処理装置１００１が保持する暗号鍵の世代更新を行う部分、（３）退職ユーザの発生に伴い、グループ管理装置４０１が、情報処理装置１００１が保持する暗号鍵の世代更新を行う部分、（４）情報処理装置１００１が暗号化データをサーバ装置１４０１に送信・格納する部分、（５）情報処理装置１００１が暗号化データをサーバ装置１４０１から検索・取得する部分に大別される。
以下、それぞれの手続きについて説明する。
【０１３６】
（１）グループ管理装置の初期設定
グループ管理装置４０１は、パラメータｑ１，ｑ２、および互いに可換な三つの関数Ｆ１（ｘ），Ｆ２（ｘ），Ｇ（ｘ、ｙ）を決定し、公開情報とする。
ここで、Ｆ１およびＦ２としては一方向性関数を選び、またＧとしては、関数の出力から実際の入力を推定することが困難である関数を選ぶ。
また、ＦとＧの可換性とは、例えばＦ１（Ｇ（ｘ，ｙ））＝Ｇ（Ｆ１（ｘ），ｙ）を意味するものとする。
ｑ１，ｑ２は世代数の最大値（最終世代）であり、それぞれ退職ユーザ、異動ユーザの発生に伴う鍵更新の上限を表す。
これらは世代の更新頻度やシステムの運用期間から適切に設定する。
さらに、検索権限を検証するための特別なキーワードｗ０、および適当な一方向性関数Ｈを選択し、公開情報とする。
本実施の形態では、Ｆ１，Ｆ２，Ｇの具体例として、以下に基づき決定したものを利用する。
ｐ１，ｐ２として十分大きな素数を選び、Ｎ＝ｐ１×ｐ２とする。
ｅ１，ｅ２としてＺＮ＊から、（ｐ１−１）（ｐ２−１）と互いに素な数をランダムに選択する。Ｆ１，Ｆ２，Ｇを以下で定める。
Ｆ１（ｘ）＝ｘｅ１  ｍｏｄ  Ｎ
Ｆ２（ｘ）＝ｘｅ２  ｍｏｄ  Ｎ
Ｇ（ｘ，ｙ）＝ｘｙ  ｍｏｄ  Ｎ
なお、ｍｏｄはモジュロ演算子を表し、ＺＮ＊は０からＮ−１の整数の中でＮと互いに素である整数の集合を表す。
また、Ｆ１（ｘ）は第１の関数の例であり、Ｆ２（ｘ）は第２の関数の例である。
【０１３７】
次に、暗号鍵生成部４２１による鍵生成動作の詳細を図３８のフローチャートを参照しながら説明する。
暗号鍵生成部４２１は、情報処理装置１００１が利用する暗号鍵ｋｉ，ｊ（１≦ｉ≦ｑ１，１≦ｊ≦ｑ２）を生成する。
ここで、ｋｉ，ｊは、（ｉ，ｊ）世代目で利用する暗号鍵であり、退職ユーザ発生に伴う鍵更新がｉ−１回、異動ユーザ発生に伴う鍵更新がｊ−１回行われたものを意味する。
【０１３８】
まず、暗号鍵生成部４２１は、暗号鍵ｋｑ１，ｑ２（退職ユーザ対応値及び異動ユーザ対応値のいずれもが最終値である暗号鍵）を、ＺＮ＊からランダムに選択する（Ｓ３８０１）。
そして、初期鍵である暗号鍵ｋｑ１，ｑ２に対してＦ１（ｘ）及びＦ２（ｘ）を適用して新たな暗号鍵を生成し、以降、生成済みの鍵に対してＦ１（ｘ）及びＦ２（ｘ）を適用して新たな鍵を生成する動作を繰り返し、各鍵間に連続性を持たせながら、生成済みの鍵とは別の退職ユーザ対応値又は異動ユーザ対応値が設定されている暗号鍵を生成する。
具体的には、暗号鍵ｋｑ１，ｑ２以外の暗号鍵ｋｉ，ｊ（１≦ｉ≦ｑ１，１≦ｊ≦ｑ２）を、以下の式に従って順次計算する（暗号鍵の無矛盾性はＦ１，Ｆ２の可換性によって保証される）（Ｓ３８０２）。
ｋｉ，ｊ−１＝Ｆ１（ｋｉ，ｊ）
ｋｉ−１，ｊ＝Ｆ２（ｋｉ，ｊ）
【０１３９】
このように、暗号鍵生成部４２１は、初期鍵である暗号鍵ｋｑ１，ｑ２に第１の関数（Ｆ１）を適用して、退職ユーザ対応値が暗号鍵ｋｑ１，ｑ２の退職ユーザ対応値と共通し異動ユーザ対応値が暗号鍵ｋｑ１，ｑ２の異動ユーザ対応値の１つ前の世代の値となる新たな暗号鍵ｋｑ１，ｑ２−１を生成する。また、生成した暗号鍵ｋｑ１，ｑ２−１に第１の関数を適用して、退職ユーザ対応値が暗号鍵ｋｑ１，ｑ２−１の退職ユーザ対応値と共通し異動ユーザ対応値が暗号鍵ｋｑ１，ｑ２−１の異動ユーザ対応値の１つ前の世代の値となる暗号鍵ｋｑ１，ｑ２−２を生成する。
また、暗号鍵生成部４２１は、初期鍵である暗号鍵ｋｑ１，ｑ２に第２の関数（Ｆ２）を適用して、異動ユーザ対応値が暗号鍵ｋｑ１，ｑ２の異動ユーザ対応値と共通し退職ユーザ対応値が暗号鍵ｋｑ１，ｑ２の退職ユーザ対応値の１つ前の世代の値となる新たな暗号鍵ｋｑ１−１，ｑ２を生成する。また、生成した暗号鍵ｋｑ１−１，ｑ２に第２の関数を適用して、異動ユーザ対応値が暗号鍵ｋｑ１−１，ｑ２の異動ユーザ対応値と共通し退職ユーザ対応値が暗号鍵ｋｑ１−１，ｑ２の退職ユーザ対応値の１つ前の世代の値となる新たな暗号鍵ｋｑ１−２，ｑ２を生成する。
このように、暗号鍵生成部４２１は、生成した鍵に第１の関数及び第２の関数のいずれかを適用して新たな鍵を生成する動作を繰り返して、異動ユーザ対応値及び退職ユーザ対応値の組み合わせの全パターンに対応する複数の鍵を生成する。
【０１４０】
こうして得られた全ての暗号鍵ｋ１，１〜ｋｑ１，ｑ２を、暗号鍵生成部４２１は、暗号鍵記憶領域４１１に格納する（Ｓ３８０３）。
そして、暗号鍵配布処理部４５１が（１，１）世代目の暗号鍵ｋ１，１を暗号鍵記憶領域４１１から取得し、通信部４３１が、全ての正当な情報処理装置１００１に、（１，１）世代目の暗号鍵ｋ１，１を送信する（Ｓ３８０４）。
これは、暗号鍵の安全性が保たれる方式であれば、オフラインで行っても良いし、既存の鍵配送技術を用いてオンラインで行っても良い。
暗号鍵ｋ１，１を受信した情報処理装置１００１は、この暗号鍵ｋ１，１を、世代情報とともに暗号鍵記憶領域３１１に格納する。
【０１４１】
その後、グループ管理装置４０１は、特別なＩＤとしてｉｄ０を適当に選択し、特別な暗号化キーワードｃ０を以下のように計算する（Ｓ３８０５）。
ｃ０＝Ｈ（ｉｄ０，Ｇ（ｋ１，１，ｗ０））
通信部４３１は、データＩＤ、暗号化キーワードの組（ｉｄ０，ｃ０）をサーバ装置１４０１に送信する（Ｓ３８０６）。
これらを受信したサーバ装置１４０１は、暗号化キーワード記憶領域２１１に、世代、データＩＤ、暗号化キーワードをそれぞれ（１，１），ｉｄ０，ｃ０としたデータを格納する（図１９）。
また、世代遷移記憶領域１４１３に、世代情報（１，１）を格納する（図２０）。
【０１４２】
（２）異動ユーザの発生に伴う暗号鍵の世代更新
正当な情報処理装置１００１のグループに対し、異動ユーザが発生した場合、以下のように世代更新を実施する。
以下、図３９のフローチャートを参照して、説明する。
【０１４３】
異動ユーザが発生した場合（Ｓ３９０１でＹＥＳ）、世代は（ｓ，ｔ）から（ｓ，ｔ＋１）に更新される（ただしｔ＋１≦ｑ２）。
具体的には、グループ管理装置４０１の暗号鍵配布処理部４５１が、所属ユーザ用に（ｓ，ｔ＋１）世代目の暗号鍵ｋｓ，ｔ＋１を暗号鍵記憶領域４１１から取得する（Ｓ３９０２）。
また、通信部４３１が、全ての正当な情報処理装置１００１（所属ユーザが利用している情報処理装置１００１）に、（ｓ，ｔ＋１）世代目の暗号鍵ｋｓ，ｔ＋１を送信する（Ｓ３９０３）。
これは、暗号鍵の安全性が保たれる方式であれば、オフラインで行っても良いし、既存の鍵配送技術を用いてオンラインで行っても良い。
暗号鍵ｋｓ，ｔ＋１を受信した情報処理装置１００１は、暗号鍵記憶領域３１１の内容のうち、世代を（ｓ，ｔ＋１）に、暗号鍵をｋｓ，ｔ＋１に置き換える。
また、グループ管理装置４０１の暗号鍵配布処理部４５１は、鍵更新の原因となった異動ユーザの許容世代範囲の情報を世代範囲記憶領域４４１に書き込む。具体的には、異動ユーザのユーザＩＤに対して、許容世代範囲として（ｓ、ｔ）世代と書き込む。
【０１４４】
更に、グループ管理装置４０１の通信部４３１は、最新の世代情報（ｓ，ｔ＋１）をサーバ装置１４０１に送信する（Ｓ３９０４）。
これを受信したサーバ装置１４０１は、世代遷移記憶領域１４１３に、最新の世代情報（ｓ，ｔ＋１）を追記する。
【０１４５】
（３）退職ユーザの発生に伴う暗号鍵の世代更新
正当な情報処理装置１００１のグループに対し、退職ユーザが発生した場合、以下のように世代更新を実施する。
以下、図４０のフローチャートを参照して、説明する。
【０１４６】
退職ユーザが発生した場合（Ｓ４００１でＹＥＳ）、世代は（ｓ，ｔ）から（ｓ＋１，ｔ）に更新される（ただしｓ＋１≦ｑ１）。
具体的には、グループ管理装置４０１の暗号鍵配布処理部４５１が、所属ユーザ用に（ｓ＋１，ｔ）世代目の暗号鍵ｋｓ＋１，ｔを暗号鍵記憶領域４１１から取得する（Ｓ４００２）。
また、通信部４３１が、全ての正当な情報処理装置１００１（所属ユーザが利用している情報処理装置１００１）に、（ｓ＋１，ｔ）世代目の暗号鍵ｋｓ＋１，ｔを送信する（Ｓ４００３）。
さらに、暗号鍵配布処理部４５１は、全ての（退職ユーザでない）異動ユーザの各々について、世代範囲記憶領域４４１から世代範囲情報を読み出す（Ｓ４００４）。
次に、暗号鍵配布処理部４５１は、現在の暗号鍵ｋｓ，ｊ（ｊ＜ｔ）を有している異動ユーザに対して、（ｓ＋１，ｊ）世代目の検索が可能である暗号鍵ｋｓ＋１，ｊを取得する（Ｓ４００５）。Ｓ４００５の処理は、異動ユーザごとに行われる。
そして、通信部４３１が、異動ユーザが利用している情報処理装置１００１に、対応する暗号鍵ｋｓ＋１，ｊを送信する（Ｓ４００６）。
通信部４３１による暗号鍵の送信は、暗号鍵の安全性が保たれる方式であれば、オフラインで行っても良いし、既存の鍵配送技術を用いてオンラインで行っても良い。
暗号鍵を受信した情報処理装置１００１は、暗号鍵記憶領域３１１の世代および暗号鍵を、受信した内容で置き換える。
また、グループ管理装置４０１の暗号鍵配布処理部４５１は、Ｓ４００６で新たな暗号鍵を送信した異動ユーザの新たな許容世代範囲の情報を世代範囲記憶領域４４１に書き込む。具体的には、異動ユーザのユーザＩＤに対して、許容世代範囲として（ｓ＋１、ｊ）世代と書き込む。
【０１４７】
更に、グループ管理装置４０１の通信部４３１は、最新の世代情報（ｓ＋１，ｔ）をサーバ装置１４０１に送信する（Ｓ４００７）。
これを受信したサーバ装置１４０１は、世代遷移記憶領域１４１３に、最新の世代情報（ｓ＋１，ｔ）を追記する。
【０１４８】
（４）暗号化データの送信・格納
正当な情報処理装置１００１がデータをサーバ装置１４０１に送信する場合、後に秘匿検索が行えるよう、キーワードとデータを別々に暗号化したものを送信する。
（ｓ，ｔ）世代目における具体的な手順を以下に述べる。
なお、動作のフローチャートは、図２９及び図３０と同様である。
【０１４９】
まず、情報処理装置１００１は、データに対し、ユニークなデータＩＤを割り当てる（ｉｄｘとする）。
さらに、情報処理装置１００１は、データの暗号化を行う。
ここでは、正当な情報処理装置１００１だけが復号できるような、既存の暗号技術（グループ暗号技術）を利用する（暗号化データをｄｘとする）。
次に、トラップドア生成部３２１が、データに関連付けられた複数のキーワード（ｗｘｊとする）に対し、それぞれトラップドアを生成する。
具体的には、暗号鍵記憶領域３１１に格納されている暗号鍵ｋｓ，ｔを利用して、各キーワードｗｘｊに対し、トラップドアｔｄｘｊを以下のように計算する。
ｔｄｘｊ＝Ｇ（ｋｓ，ｔ，ｗｘｊ）
その後、暗号化キーワード生成部３２２が、各トラップドアｔｄｘｊに対し、暗号化キーワードｃｘｊを以下のように計算する。
ｃｘｊ＝Ｈ（ｉｄｘ，ｔｄｘｊ）
最後に、通信部３３１が、世代、データＩＤ、暗号化データ、暗号化キーワードの組（ｓ，ｔ，ｉｄｘ，ｄｘ，ｃｘ１，ｃｘ２，．．．）をサーバ装置１４０１に送信する。
【０１５０】
これらを受信したサーバ装置１４０１は、暗号化データｄｘをデータＩＤと関連付けて暗号化データ記憶領域２１２に格納し、各暗号化キーワードｃｘｊを世代、データＩＤと関連付けて暗号化キーワード記憶領域２１１に格納する。
【０１５１】
（５）暗号化データの検索・取得
正当な情報処理装置１００１、もしくは（退職ユーザでない）異動ユーザに対応する情報処理装置１００１は、現在もしくは過去の世代にサーバ装置１４０１に格納されたデータに対し、キーワードを指定して秘匿検索を行うことができる。
暗号鍵ｋｓ，ｔを持つ情報処理装置１００１が、（ｓ，ｔ）世代目までの検索を行う具体的な手順を以下に述べる。
なお、情報処理装置１００１の動作のフローチャートは図３６と同様である。
サーバ装置１４０１の動作のフローチャートは図４１に示す通りである。
【０１５２】
まず、情報処理装置１００１のトラップドア生成部３２１が、検索したいキーワードに対応するトラップドアを生成する。具体的には、キーワードｗに対し、トラップドアｔｄｓ，ｔを以下のように計算する。
ｔｄｓ，ｔ＝Ｇ（ｋｓ，ｔ，ｗ）
さらに、情報処理装置１００１の検証用トラップドア生成部１０２３が、検索する権限があることをサーバ装置１４０１に対して証明するための検証用トラップドアｔｄｖを以下のように計算する。
ｔｄｖ＝Ｇ（ｋｓ，ｔ，ｗ０）
次に、通信部３３１が、世代情報（退職ユーザ対応値（ｓ）、異動ユーザ対応値（ｔ））、トラップドア、検証用トラップドアの組（ｓ，ｔ，ｔｄｓ，ｔ，ｔｄｖ）を検索要求としてサーバ装置１４０１に送信する。
【０１５３】
サーバ装置１４０１では、通信部２３１が検索要求を受信する（Ｓ４１０１）。
そして、比較部２２２が、まず、検索要求中の世代（ｓ，ｔ）と、世代遷移記憶領域１４１３に格納されている最新の世代について、第一要素（退職ユーザ対応値）が一致していることを確認する（Ｓ４１０２）。
一致しない場合、情報処理装置１００１に正当な検索権限がないとみなし、処理を終了する。
次に、トラップドア検証部９２３が、受信した検証用トラップドアｔｄｖと、暗号化キーワード記憶領域２１１に格納されている一行目の要素（１，１），ｉｄ０，ｃ０について、キーワードが一致すると判定されること、つまり、検証用トラップドアｔｄｖから特別な暗号化キーワードｃ０が抽出できることを確認する（Ｓ４１０３）。
なお、特別なキーワードｗ０は公開値であり、検証用トラップドアｔｄｖの生成は、ユーザが指定する検索キーワードｗの代わりに、特別なキーワードｗ０を用いて通常のトラップドアを生成することに相当する。換言すれば、検証用トラップドアｔｄｖにおいて特別なキーワードｗ０と対応付けられているレコードの検索を要求していることと同視できる。このため、確認方法は後述する検索処理と同様なので省略する。
Ｓ４１０３においてキーワードが一致しない場合、情報処理装置１００１に正当な検索権限がないとみなし、処理を終了する。
Ｓ４１０３においてキーワードが一致した場合、実際の検索処理を実行する。
【０１５４】
サーバ装置１４０１のトラップドア生成部２２１は、受信したトラップドアｔｄｓ，ｔを用い、世代遷移記憶領域１４１３に格納されている世代（ｉ，ｊ）のうちｊ≦ｔを満たすもの全てについて、対応するトラップドアｔｄｉ，ｊを以下のように順次計算する（Ｓ４１０４）。
ｔｄｉ，ｊ−１＝Ｆ１（ｔｄｉ，ｊ）
ｔｄｉ−１，ｊ＝Ｆ２（ｔｄｉ，ｊ）
その後、比較部２２２が、暗号化キーワード記憶領域２１１を参照し、トラップドアに対応する暗号化キーワードが存在するかを確認する（Ｓ４１０５、４１０６）。
具体的には、暗号化キーワード記憶領域２１１の各行の世代、データＩＤ、暗号化キーワードの組（ｉ，ｊ，ｉｄ，ｃ）に対し、以下の等式が成立するかを確認する。
ｃ＝Ｈ（ｉｄ，ｔｄｉ，ｊ）
成立した場合はｃが指定されたキーワードｗに対応する暗号化キーワードとなるため、暗号化データ記憶領域２１２を参照してｉｄから暗号化データｄを取得する（Ｓ４１０７）。
そして、通信部２３１が情報処理装置１００１に、キーワードｗに対応する暗号化データｄを送信する（Ｓ４１０８）。
等式が複数成立した場合は全て送信するようにしても、一部を送信するようにしても良い。
上記の等式が暗号化キーワード記憶領域２１１のどの行においても不成立であった場合は、その旨を送信する。
【０１５５】
暗号化データｄを受信した情報処理装置１００１は、ｄの復号を行う。
ここでは、正当な情報処理装置１００１だけが復号できるような、既存の暗号技術（グループ暗号技術）を利用する。
【０１５６】
なお、サーバ装置１４０１が受信したトラップドアｔｄｓ，ｔから生成した（ｉ，ｊ）世代目のトラップドアｔｄｉ，ｊと、情報処理装置１００１が暗号化データ送信の際に、暗号鍵ｋｉ，ｊから生成したトラップドアが一致し、本秘匿検索システムが正常に機能することは、例えば以下のように確認される。
サーバ装置１４０１がトラップドアｔｄｓ，ｔから生成した（ｉ，ｊ）世代目のトラップドアｔｄｉ，ｊは、
ｔｄｉ，ｊ＝Ｆ１ｔ−ｊ（Ｆ２ｓ−ｉ（ｔｄｓ，ｔ））
＝Ｆ１ｔ−ｊ（Ｆ２ｓ−ｉ（Ｇ（ｋｓ，ｔ，ｗ）））
＝Ｆ１ｔ−ｊ（Ｇ（Ｆ２ｓ−ｉ（ｋｓ，ｔ），ｗ））
＝Ｇ（Ｆ１ｔ−ｊ（Ｆ２ｓ−ｉ（ｋｓ，ｔ）），ｗ）
＝Ｇ（ｋｉ，ｊ，ｗ）
となり、これは情報処理装置１００１が（ｉ，ｊ）世代目に生成するトラップドアと一致する。
【０１５７】
また、システムの安全性、すなわちサーバ装置１４０１がトラップドアや暗号化キーワードからキーワードを類推できないことや、ある期間の暗号鍵を持つ情報処理装置１００１が期間外の暗号鍵を類推できず、検索も行えないことは、Ｆ１，Ｆ２，Ｈの一方向性、Ｇの入力推定困難性に基づいている。
特に、本実施の形態にて示した具体例においては、ＲＳＡ（登録商標）暗号の安全性に基づいている。
【０１５８】
以上によって、情報処理装置１００１がデータ・キーワードをサーバ装置１４０１に対して秘匿したまま検索できる秘匿検索システムが実現できる。
サーバ装置１４０１が、受信したトラップドアから検索期間に対応する全てのトラップドアを生成できるため、検索時に情報処理装置１００１が送信すべきトラップドアが削減でき、情報処理装置１００１の計算量や通信量の削減を達成できる。また、脱退ユーザとして、異動ユーザ、退職ユーザが混在できるという、柔軟性も達成している。
【０１５９】
なお、実施の形態１にて記述したバリエーションは、本実施の形態においても同様に適用可能である。
例えば、以下のようなバリエーションも可能である。
グループ管理装置４０１は、予め、異動ユーザ対応値及び退職ユーザ対応値のいずれもが先頭値となっている先頭世代の鍵ｋ０，０を初期鍵として生成する。
そして、鍵発行時に、所属ユーザ又は異動ユーザごとに、対応する異動ユーザ対応値及び退職ユーザ対応値の組み合わせに基づき、初期鍵又は初期鍵から派生する鍵を生成元鍵とし、生成元鍵に第１の関数（Ｆ１）を適用して退職ユーザ対応値が生成元鍵の退職ユーザ対応値と共通し異動ユーザ対応値が生成元鍵の異動ユーザ対応値の１つ後の世代の値となる新たな鍵を生成する。
または、生成元鍵に第２の関数（Ｆ２）を適用して異動ユーザ対応値が生成元鍵の異動ユーザ対応値と共通し退職ユーザ対応値が生成元鍵の退職ユーザ対応値の１つ後の世代の値となる新たな鍵を生成する。
そして、生成した鍵を所属ユーザ又は異動ユーザに発行する。
【０１６０】
また、本実施の形態に記述した内容と、実施の形態１、２にて記述した内容を組み合わせることで、加入ユーザの検索権限を柔軟に設定することも可能である。
【０１６１】
また、本実施の形態では、特別なキーワードｗ０に対する暗号化キーワードｃ０を利用して検索権限の検証を行っているが、トラップドアＧ（ｋ１，１，ｗ０）を利用して検証を行っても良い。
この場合、サーバ装置１４０１は、ｃ０のかわりに別途Ｇ（ｋ１，１，ｗ０）を検証用情報として記憶することになる。
また、退職ユーザの発生に伴う鍵更新が進むにつれて、サーバ装置１４０１はＧ（ｋｉ，１，ｗ０）の値を得ることができるので、この値をキャッシュすることで、以降の検証を効率化することも可能である。
つまり、上記の説明では、検証用トラップドアｔｄｖからトラップドアｔｄ１，１（＝Ｇ（ｋ１，１，ｗ０））まで遡って、特別な暗号化キーワードｃｏとの整合性を確認しているが、キャッシュしている値で代用することで検証作業を短縮することができる。
【０１６２】
例えば、図２５に示す鍵ｋ２，２に基づく検証用トラップドアｔｄｖ（２，２）に対する検証処理において、鍵ｋ０，０に対応するトラップドアｔｄ０，０（＝Ｇ（ｋ０，０，ｗ０））（上記のｔｄ１，１（＝Ｇ（ｋ１，１，ｗ０））に相当）を導出するためには、鍵ｋ２，１に対応するトラップドアｔｄ２，１（＝Ｇ（ｋ２，１，ｗ０））を導出する必要がある。
このため、このトラップドアｔｄ２，１（＝Ｇ（ｋ２，１，ｗ０））をキャッシュすることにより、次回の検証用トラップドアｔｄｖに対する検証処理では、キャッシュ値まで遡って検証を行うのみで済む。
【０１６３】
以上、本実施の形態では、関数Ｆ１，Ｆ２，Ｇを利用することで、脱退ユーザの検索権限を柔軟に設定できる方式を説明した。
また、本実施の形態では、ＲＳＡ（登録商標）暗号の安全性をベースとする方式を説明した。
【０１６４】
最後に、実施の形態１〜３に示したサーバ装置２０１、情報処理装置３０１及びグループ管理装置４０１（以下、三者をまとめてサーバ装置２０１等と表記する）のハードウェア構成例について説明する。
図４２は、実施の形態１〜３に示すサーバ装置２０１等のハードウェア資源の一例を示す図である。
なお、図４２の構成は、あくまでもサーバ装置２０１等のハードウェア構成の一例を示すものであり、サーバ装置２０１等のハードウェア構成は図４２に記載の構成に限らず、他の構成であってもよい。
【０１６５】
図４２において、サーバ装置２０１等は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。
ＣＰＵ９１１は、バス９１２を介して、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）９１３、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）９１４、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。
更に、ＣＰＵ９１１は、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、コンパクトディスク装置９０５（ＣＤＤ）、プリンタ装置９０６、スキャナ装置９０７と接続していてもよい。また、磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカード（登録商標）読み書き装置などの記憶装置でもよい。
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置の一例である。
実施の形態１〜３で説明した「〜記憶領域」は、ＲＡＭ９１４、磁気ディスク装置９２０等により実現される。
通信ボード９１５、キーボード９０２、マウス９０３、スキャナ装置９０７、ＦＤＤ９０４などは、入力装置の一例である。
また、通信ボード９１５、表示装置９０１、プリンタ装置９０６などは、出力装置の一例である。
【０１６６】
通信ボード９１５は、図１に示すように、ネットワークに接続されている。例えば、通信ボード９１５は、ＬＡＮ（ローカルエリアネットワーク）、インターネット、ＷＡＮ（ワイドエリアネットワーク）、ＳＡＮ（ストレージエリアネットワーク）などに接続されていても構わない。
【０１６７】
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。
プログラム群９２３のプログラムは、ＣＰＵ９１１がオペレーティングシステム９２１、ウィンドウシステム９２２を利用しながら実行する。
【０１６８】
また、ＲＡＭ９１４には、ＣＰＵ９１１に実行させるオペレーティングシステム９２１のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。
また、ＲＡＭ９１４には、ＣＰＵ９１１による処理に必要な各種データが格納される。
【０１６９】
また、ＲＯＭ９１３には、ＢＩＯＳ（Ｂａｓｉｃ  Ｉｎｐｕｔ  Ｏｕｔｐｕｔ  Ｓｙｓｔｅｍ）プログラムが格納され、磁気ディスク装置９２０にはブートプログラムが格納されている。
サーバ装置２０１等の起動時には、ＲＯＭ９１３のＢＩＯＳプログラム及び磁気ディスク装置９２０のブートプログラムが実行され、ＢＩＯＳプログラム及びブートプログラムによりオペレーティングシステム９２１が起動される。
【０１７０】
上記プログラム群９２３には、実施の形態１〜３の説明において「〜部」として説明している機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
【０１７１】
ファイル群９２４には、実施の形態１〜３の説明において、「〜の判断」、「〜の判定」、「〜の計算」、「〜の演算」、「〜の生成」、「〜の比較」、「〜の照合」、「〜の更新」、「〜の設定」、「〜の登録」、「〜の選択」、「〜の格納」、「〜の検索」、「〜の検証」等として説明している処理の結果を示す情報やデータや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。
「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示などのＣＰＵの動作に用いられる。
抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリ、レジスタ、キャッシュメモリ、バッファメモリ等に一時的に記憶される。
また、実施の形態１〜３で説明しているフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、ＦＤＤ９０４のフレキシブルディスク、ＣＤＤ９０５のコンパクトディスク、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ等の記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【０１７２】
また、実施の形態１〜３の説明において「〜部」として説明しているものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」、として説明しているものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、実施の形態１〜３の「〜部」としてコンピュータを機能させるものである。あるいは、実施の形態１〜３の「〜部」の手順や方法をコンピュータに実行させるものである。
【０１７３】
このように、実施の形態１〜３に示すサーバ装置２０１等は、処理装置たるＣＰＵ、記憶装置たるメモリ、磁気ディスク等、入力装置たるキーボード、マウス、通信ボード等、出力装置たる表示装置、通信ボード等を備えるコンピュータであり、上記したように「〜部」として示された機能をこれら処理装置、記憶装置、入力装置、出力装置を用いて実現するものである。
【符号の説明】
【０１７４】
１０１  ネットワーク、２０１  サーバ装置、２１１  暗号化キーワード記憶領域、２１２  暗号化データ記憶領域、２２１  トラップドア生成部、２２２  比較部、２３１  通信部、３０１  情報処理装置、３１１  暗号鍵記憶領域、３２１  トラップドア生成部、３２２  暗号化キーワード生成部、３３１  通信部、４０１  グループ管理装置、４１１  暗号鍵記憶領域、４２１  暗号鍵生成部、４３１  通信部、４４１  世代範囲記憶領域、４５１  暗号鍵配布処理部、９１３  関数パラメータ記憶領域、９２３  トラップドア検証部、１０２３  検証用トラップドア生成部、１４１３  世代遷移記憶領域。
【図１】
0005441726.tif 000002
【図２】
0005441726.tif 000003
【図３】
0005441726.tif 000004
【図４】
0005441726.tif 000005
【図５】
0005441726.tif 000006
【図６】
0005441726.tif 000007
【図７】
0005441726.tif 000008
【図８】
0005441726.tif 000009
【図９】
0005441726.tif 000010
【図１０】
0005441726.tif 000011
【図１１】
0005441726.tif 000012
【図１２】
0005441726.tif 000013
【図１３】
0005441726.tif 000014
【図１４】
0005441726.tif 000015
【図１５】
0005441726.tif 000016
【図１６】
0005441726.tif 000017
【図１７】
0005441726.tif 000018
【図１８】
0005441726.tif 000019
【図１９】
0005441726.tif 000020
【図２０】
0005441726.tif 000021
【図２１】
0005441726.tif 000022
【図２２】
0005441726.tif 000023
【図２３】
0005441726.tif 000024
【図２４】
0005441726.tif 000025
【図２５】
0005441726.tif 000026
【図２６】
0005441726.tif 000027
【図２７】
0005441726.tif 000028
【図２８】
0005441726.tif 000029
【図２９】
0005441726.tif 000030
【図３０】
0005441726.tif 000031
【図３１】
0005441726.tif 000032
【図３２】
0005441726.tif 000033
【図３３】
0005441726.tif 000034
【図３４】
0005441726.tif 000035
【図３５】
0005441726.tif 000036
【図３６】
0005441726.tif 000037
【図３７】
0005441726.tif 000038
【図３８】
0005441726.tif 000039
【図３９】
0005441726.tif 000040
【図４０】
0005441726.tif 000041
【図４１】
0005441726.tif 000042
【図４２】
0005441726.tif 000043