JP6095057B2 - 検索システム、検索方法および検索プログラム - Google Patents

Description

本発明は、検索システム、検索方法、および、検索プログラムに関し、特に、キーワード検索におけるサーバの不正を検出可能なだけでなく、ファイルの更新（削除を含む）をも行える検索システム、検索方法、および、検索プログラムに関する。

この技術分野において周知のように、Yahoo!データボックスなどのデータストレージ（データ保管）サービスにおいては、ユーザ端末は、写真などの多くのファイルを（Yahoo!データボックスなどの）サーバに格納し、保管することができる。また、ユーザ端末は、ファイル名についてキーワード検索を行って、サーバから所望のファイルの集合を取得することもできる。尚、ユーザ端末は、クライアントとも呼ばれる。

これに対して、非特許文献１は、ファイルおよびキーワード検索の際、サーバに対し内容を秘匿する暗号化検索方式を開示している。この暗号化検索方式は、ファイルとキーワードとを暗号化する方式である。

一方、悪意のあるサーバ、あるいはウィルスに汚染されたサーバは、キーワード検索の際、対応する全てのファイルを正しく返すのではなく、ファイルの一部を削除、追加、改ざん、あるいはすり替えてしまう、といった不正を行うことが考えられる。

この問題に対し、上記非特許文献１では、ファイルの削除、追加、改ざんをユーザ端末が検出できる検索システムを開示している。以下では、この非特許文献１に開示された検索システムを「第１の先行検索システム」と呼ぶことにする。しかしながら、非特許文献１に開示された第１の先行検索システムでは、サーバの不正として、ファイルのすり替えを検出することができない。

そこで、本発明者らは、サーバの不正として、ファイルの削除、追加、改ざんのみならず、ファイルのすり替えをも検出できる、検索システムを既に提供した（非特許文献２）。以下では、この非特許文献２に開示された検索システムを「第２の先行検索システム」と呼ぶことにする。しかしながら、非特許文献２に開示された第２の先行検索システムでは、ファイルを更新（削除も含む）する場合、その更新（削除）すべきファイルに含まれる全てのキーワードについて索引中の検証情報を変更しなければならない。その結果、通信量が多く、非効率になるという問題がある。

一方、非特許文献３は、ファイルの更新を容易に行える検索システムを開示している。以下では、この非特許文献３に開示された検索システムを「第３の先行検索システム」と呼ぶことにする。しかしながら、非特許文献３に開示された第３の先行検索システムでは、サーバの不正を検出することができない。

Y. Chang and M. Mitzenmacher, "Privacy Preserving Keyword Searches on Remote Encrypted Data", ACNS 2005: pp. 442-455 (2005) Kaoru Kurosawa and Yasuhiro Ohtaki, "UC-Secure Searchable Symmetric Encryption", Financial Cryptography 2012: pp. 285-298 Seny Kamara, Charalampos Papamanthou, and Tom Roeder, "Dynamic Searchable Symmetric Encryption", ACM Conference on Computer and Communications Security 2012: pp. 965-976

上述したように、非特許文献１に開示された第１の先行検索システムでは、サーバの不正として、ファイルのすり替えを検出することができない。

一方、非特許文献２に開示された第２の先行検索システムでは、サーバの不正（ファイルの削除、追加、改ざん、すり替え）を検出できるが、ファイルの更新（削除）を効率的に行えない。

さらに、非特許文献３に開示された第３の先行検索システムでは、ファイルの更新を容易に行えるが、ファイルの不正を検出することができない。

したがって本発明の目的は、サーバの不正（ファイルの削除、追加、改ざん、すり替え）を検出でき、かつファイルの更新（削除）も効率的に行える、検索システム、検索方法、および検索プログラムを提供することにある。

本発明の他の目的は、リプレイ・アタックも検出できる、検索システム、検索方法、および検索プログラムを提供することにある。

本発明の第１の態様に係る検索システムは、ユーザ端末がサーバに複数のファイルを保管し、ユーザ端末がキーワード検索によってサーバから所望のファイルの集合を取得すると共に、ファイルの更新（削除を含む）をも行う検索システムであって、ユーザ端末は、複数のファイルをそれらのファイル番号と共にサーバに保管するファイル保管手段と；キーワードとそのキーワードに対応するファイルのファイル番号との対応表である索引を、サーバに保管する索引保管手段と；キーワードと当該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成し、この生成した索引検証情報をサーバに保管する索引検証情報生成部と；検索キーワードをサーバへ送って、サーバから検索キーワードを含むファイルおよび当該ファイルのファイル番号の集合と検索キーワードに対応する索引検証情報とを取得するファイル取得手段と；この取得した索引検証情報が、検索キーワードと取得したファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックし、チェックの結果が正しければ承認し、そうでなければ拒否する索引検証部と；更新（削除）すべきファイルをそのファイル番号と共にサーバへ送って更新する更新手段と；を備える。

本発明の第２の態様による検索システムは、ユーザ端末がサーバに複数の暗号ファイルを保管し、ユーザ端末がキーワード検索によってサーバから所望のファイルの集合を取得すると共に、暗号ファイルの更新（削除を含む）をも行う検索システムであって、ユーザ端末は、暗号化の秘密鍵を使って複数のファイルをそれぞれ暗号化し、複数の暗号ファイルをそれらの暗号ファイルのファイル番号と共にサーバに保管する暗号ファイル保管手段と；キーワードとそのキーワードに対応するファイルのファイル番号との対応表である索引を、所定の秘密鍵を使って暗号化し、キーワードの暗号文とそのキーワードを含むファイルのファイル番号の暗号文とから成る暗号化索引をサーバに保管する暗号化索引保管手段と；キーワードと当該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成し、その生成した索引検証情報をサーバに保管する索引検証情報生成部と；所定の秘密鍵を使って検索キーワードを暗号化して得られる暗号検索キーワードをサーバへ送って、サーバから暗号検索キーワードを含む暗号ファイルおよび当該暗号ファイルのファイル番号の集合と検索キーワードに対応する索引検証情報とを取得する暗号ファイル取得手段と；その取得した索引検証情報が、検索キーワードと取得した暗号ファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックし、チェックの結果が正しければ承認し、そうでなければ拒否する索引検証部と；更新（削除）すべきファイルを暗号化の秘密鍵を使って暗号化して得られる、更新（削除）すべき暗号ファイルをそのファイル番号と共にサーバに送って更新する更新手段と；を備える。

本発明では、キーワードと当該キーワードを含む全てのファイル（暗号ファイル）のファイル番号の集合との生成用組に対して所定のアルゴリズムに従って索引検証情報を生成し、その生成した索引検証情報をサーバに保管しているので、サーバの不正（ファイルの削除、追加、改ざん、すり替え）を検出するだけでなく、更新（削除）すべきファイル（暗号ファイル）をそのファイル番号と共にサーバに送出するだけで、ファイルの更新（削除）も効率的に行うことができる。

本発明の第１の実施例に係る検索システムの格納フェーズと検索フェーズの構成を示すブロック図である。 図１に示した検索システムに使用される索引の一具体例を示す図である。 図１に示した検索システムに使用される、クライアントの索引検証情報生成部の動作を説明するためのフローチャートである。 図３に示した索引検証情報生成部の動作の一具体例を示す図である。 図１に示した検索システムに使用される、クライアントのファイル蓄積値計算部の動作を説明するためのフローチャートである。 図５に示したファイル蓄積値計算部の動作の一具体例を示す図である。 図１に示した検索システムに使用される、クライアントの索引検証部の動作を説明するためのフローチャートである。 図７に示した索引検証部の動作の一具体例を示す図である。 図１に示した検索システムに使用される、サーバのファイル検証情報生成部の動作を説明するためのフローチャートである。 図９に示したファイル検証情報生成部の動作の一具体例を示す図である。 図１に示した検索システムに使用される、クライアントのファイル検証部の動作を説明するためのフローチャートである。 図１１に示したファイル検証部の動作の一具体例を示す図である。 本発明の第１の実施例に係る検索システムの更新フェーズの構成を示すブロック図である。 図１３に示した検索システムに使用される、クライアントのＡｃｃ更新部の動作を説明するためのフローチャートである。 本発明の第２の実施例に係る検索システムの格納フェーズと検索フェーズの構成を示すブロック図である。 図１５に示した検索システムに使用される、クライアントの索引暗号部の動作を説明するためのフローチャートである。 図１６に示した索引暗号部の動作の一具体例を示す図である。 図１５に示した検索システムに使用される、クライアントのファイル蓄積値計算部の動作を説明するためのフローチャートである。 図１８に示したファイル蓄積値計算部の動作の一具体例を示す図である。 図１５に示した検索システムに使用される、クライアントのキーワード暗号部の動作を説明するためのフローチャートである。 図２０に示したキーワード暗号部の動作の一具体例を示す図である。 図１５に示した検索システムに使用される、サーバの暗号検索部の動作を説明するためのフローチャートである。 図２２に示した暗号検索部の動作の一具体例を示す図である。 図１５に示した検索システムに使用される、サーバのファイル検証情報生成部の動作を説明するためのフローチャートである。 図２４に示したファイル検証情報生成部の動作の一具体例を示す図である。 図１５に示した検索システムに使用される、クライアントのファイル検証部の動作を説明するためのフローチャートである。 図２６に示したファイル検証部の動作の一具体例を示す図である。 本発明の第２の実施例に係る検索システムの更新フェーズの構成を示すブロック図である。 図２８に示した検索システムに使用される、クライアントのＡｃｃ更新部の動作を説明するためのフローチャートである。

［概要］
以下、本発明の実施形態の概要について説明する。

本発明の実施形態による検索システムは、キーワード検索におけるサーバの不正（ファイルの「削除」、「追加」、「改ざん」、「すり替え」）を検出するだけでなく、ファイルの更新（削除を含む）を効率的に行える検索システムである。

本実施形態に係る検索システムは、ファイルが暗号化されている場合と、ファイルが暗号化されていない場合との両者に適用できる。尚、この技術分野において周知のように、メッセージの認証機能には、デジタル署名を利用する場合と、メッセージ認証コード（Message Authentication code,ＭＡＣ）を利用して認証子を生成する場合とがある。なお、デジタル署名と認証子とは、総称して、検証情報と呼ばれる。

一般に、検証情報は、所定の生成アルゴリズムによって生成され、所定の検証アルゴリズムによって検証（チェック）される。検証情報がデジタル署名の場合、所定の生成アルゴリズムは署名生成アルゴリズムから成り、所定の検証アルゴリズムは署名検証アルゴリズムから成る。一方、検証情報が認証子の場合、所定の生成アルゴリズムはＭＡＣ生成アルゴリズムから成り、所定の検証アルゴリズムはＭＡＣ検証アルゴリズムから成る。

本実施形態に係る検索システムは、以下の第１および第２の実施形態に分けられる。

本発明の第１の実施形態に係る検索システムは、ユーザ端末がファイルを暗号化せずにサーバに保管すると共に、ファイルの更新（削除を含む）をも行う検索システムである。

第１の実施形態に係る検索システムでは、ユーザ端末が、キーワードと当該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定のアルゴリズムに従って索引検証情報を生成し、その生成した索引検証情報をサーバに保管する。これにより、サーバの不正（ファイルの削除、追加、改ざん、すり替え）を検出するだけでなく、更新（削除）すべきファイルをそのファイル番号と共にサーバに送出するだけで、ファイルの更新（削除）も効率的に行うことができる。

本発明の第２の実施形態に係る検索システムは、ユーザ端末がファイルおよびキーワードを暗号化してサーバに保管すると共に、暗号ファイルの更新（削除）をも行う検索システムである。

第２の実施形態に係る検索システムでは、ユーザ端末が、キーワードと当該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定のアルゴリズムに従って索引検証情報を生成し、その生成した索引検証情報をサーバに保管する。これにより、サーバの不正（ファイルの削除、追加、改ざん、すり替え）を検出するだけでなく、更新（削除）すべき暗号ファイルをそのファイル番号と共にサーバに送出するだけで、暗号ファイルの更新（削除）も効率的に行うことができる。

尚、検索システムの動作は、ユーザ端末がファイル（暗号ファイル）をサーバに格納する「格納フェーズ」と、ユーザ端末がサーバから所望のファイルを検索する「検索フェーズ」と、ユーザ端末がファイル（暗号ファイル）を更新（削除を含む）する「更新フェーズ」と、に分けられる。

また、ファイル更新固有の問題として、「リプレイ・アタック」が知られている。ここで、リプレイ・アタックとは、不正なサーバが、更新した新しいファイルの代わりに、古いファイルを返すことをいう。

後述する本発明の実施例においては、この「リプレイ・アタック」をＲＳＡ(Rivest-Shamir-Adleman) accumulatorを使用することによって解決している。

従って、本発明の実施例の理解を容易にするために、以下、ＲＳＡ accumulatorの概要について説明する。

ｐ＝２ｐ’＋１，ｑ＝２ｑ’＋１は素数である。ただし、ｐ’，ｑ’も素数で、ｐｑは３λビットである。Ｎ＝ｐｑとおく。

ｍｏｄ Ｎにおいて、位数がｐ’ｑ’となる要素をｇとする。すなわち、
ｇ^ｐ’ｑ’＝１ｍｏｄ Ｎ
である。

３λビットの正整数ａをランダムに選ぶ。
３λビットの正整数ｘに対し、ｈ_ａ（ｘ）を、
ｈ_ａ（ｘ）＝ａ×ｘ の下位λビットと定義する。なお、この乗算×は、有限体（あるいはガロア体）ＧＦ（２^３λ）上の乗算である。

このとき、λビットの任意のｙに対し、
ｈ_ａ（ｘ）＝ｙ
となる３λビットの素数ｘを効率よく求めることができる。
そのような素数ｘをｐｒｉｍｅ（ｙ）と書く。

λビットのｙ_ｉの集合をＥ＝｛ｙ_１，・・・，ｙ_ｎ｝とする（１≦ｉ≦ｎ）。

Ａｌｉｃｅは、Ｅの蓄積値
Ａｃｃ（Ｅ）＝ｇ^{ｐｒｉｍｅ（ｙ１）×・・・×ｐｒｉｍｅ（ｙｎ）}ｍｏｄ Ｎ
をＢｏｂに送る。

ｙ_ｉ∈Ｅを証明したいとき、Ａｌｉｃｅは、ｐｒｉｍｅ（ｙ_ｊ）と、
π＝ｇ^{Πｉ≠ｊ ｐｒｉｍｅ（ｙｉ）}ｍｏｄ Ｎ
と、をＢｏｂに送る。

Ｂｏｂは、
Ａｃｃ（Ｅ）＝（π）^{ｐｒｉｍｅ（ｙｊ）}ｍｏｄ Ｎ
が成り立つかどうかをチェックする。

強ＲＳＡ仮定が成り立つと仮定する。
公開情報Ｎ，ｇ，ｈ_ａおよびλビットのｙ_ｉの集合Ｅ＝｛ｙ_１，・・・，ｙ_ｎ｝が与えられたとき、
Ａｃｃ（Ｅ）＝（π）^{ｐｒｉｍｅ（ｙ）}ｍｏｄ Ｎ
を満たすＥに属さないｙとπを見つけることは困難である。

図１を参照して、本発明の第１の実施例に係る検索システム１００の格納フェーズおよび検索フェーズについて説明する。図１は、本発明の第１の実施例に係る検索システム１００の格納フェーズと検索フェーズのブロック図である。図示の検索システム１００は、上述した本発明の第１の実施形態に係る検索システムに相当する検証システムである。検索システム１００は、クライアント２００とサーバ３００とから構成される。クライアント２００は、ユーザ端末とも呼ばれる。

図示の検索システム１００は、クライアント（ユーザ端末）２００がサーバ３００に複数のファイルを保管し、クライアント（ユーザ端末）２００がキーワード検索によってサーバ３００から所望のファイルの集合を取得するシステムである。

尚、クライアント（ユーザ端末）２００がサーバ３００に格納されたファイルを更新（削除を含む）する更新フェーズのブロック図については、後で図１３を参照して説明する。

クライアント２００は、鍵生成部２０２と、鍵保持部２０４と、索引検証情報生成部２０６と、索引検証部２０８と、第１乃至第３の信号線（伝送線）２１０、２１２、２１４と、ファイル蓄積値計算部２１６と、Ａｃｃ保持部２１８と、ファイル検証部２２０と、から構成されている。

一方、サーバ３００は、記憶領域３０２と、検索部３０４と、鍵保持部３０６と、ファイル検証情報生成部３０８と、から構成されている。

鍵生成部２０２は、検証用の秘密鍵Ｋと秘密情報ｐ，ｑと公開情報Ｎ，ｇ，ｈ_ａとを生成する。クライアント２００の鍵保持部２０４は、これら生成された検証用の秘密鍵Ｋと秘密情報ｐ，ｑと公開情報Ｎ，ｇ，ｈ_ａとを保持する。また、鍵保持部２０４に保持された公開情報Ｎ，ｇ，ｈ_ａは、サーバ３００の鍵保持部３０６へ送られる。したがって、サーバ３００の鍵保持部３０６は、公開情報Ｎ，ｇ，ｈ_ａを保持する。

クライアント２００は、複数のファイルをそれらのファイル番号と共に第１の信号線（伝送線）２１０を介してサーバ３００へ送信する。サーバ３００は、その送られてきた複数のファイルをそれらのファイル番号と共に記憶領域３０２に保管する。したがって、第１の信号線（伝送線）２１０は、サーバ３００に複数のファイルをそれらのファイル番号と共に保管するファイル保管手段として働く。

また、クライアント２００は、索引（後述する）を生成し、生成した索引を第２の信号線（伝送線）２１２を介してサーバ３００へ送信する。サーバ３００は、その送られてきた索引を記憶領域３０２に記憶する。したがって、第２の信号線（伝送線）２１２は、生成した索引をサーバ３００に保管する索引保管手段として働く。

図２に索引の具体例を示す。索引は、キーワードと、それに対応するファイルの番号（ファイル番号）の対応表である。

図示の例では、索引の番号１には、キーワードとして「情報工学」が記憶され、そのキーワードに対応するファイル番号として、「１」、「６」、「８」、「１１」が記憶されている。また、索引の番号２には、キーワードとして「茨城大学」が記憶され、そのキーワードに対応するファイル番号として、「３」、「６」、「１０」が記憶されている。

図３を参照して、クライアント２００の索引検証情報生成部２０６の動作について説明する。

索引検証情報生成部２０６は、索引と検証用の秘密鍵Ｋとを読み込む（Ｓ１０２）。次に、索引検証情報生成部２０６は、各キーワードＷ_ｉについて以下の処理を実行する（Ｓ１０４）。ここでは、キーワードＷ_ｉを含むファイルの集合｛Ｄ_ｊ１，Ｄ_ｊ２，・・・｝に関し、その添字（すなわち、ファイル番号）の集合を｛ｊ１、ｊ２、…｝とする。この場合、索引検証情報生成部２０６は、検証用の秘密鍵Ｋを使い、生成用組（Ｗ_ｉ、ｊ１、ｊ２、…）に対応する索引検証情報ｔａｇ_ｉを下記の数式によって計算する。
ｔａｇ_ｉ＝ｆ_Ｋ（Ｗ_ｉ、ｊ１、ｊ２、…）
ここで、ｆはＭＡＣ生成アルゴリズムまたは署名生成アルゴリズムから成る所定の生成アルゴリズムである。

所定の生成アルゴリズムがＭＡＣ生成アルゴリズムから成るとする。この場合、索引検証情報生成部２０６は、検証用の秘密鍵ＫとしてＭＡＣの秘密鍵を使って、ＭＡＣ生成アルゴリズムに従って、索引検証情報ｔａｇ_ｉとして生成用組（Ｗ_ｉ、ｊ１、ｊ２、…）に対する認証子を生成する。

一方、所定のアルゴリズムが署名生成アルゴリズムから成るとする。この場合、索引検証情報生成部２０６は、検証用の秘密鍵Ｋとしてデジタル署名の秘密鍵を使って、署名生成アルゴリズムに従って、索引検証情報ｔａｇ_ｉとして生成用組（Ｗ_ｉ、ｊ１、ｊ２、…）に対するデジタル署名を生成する。

索引検証情報生成部２０６は、計算して得られた索引検証情報（ｔａｇ_１、ｔａｇ_２、…）を出力する（ステップＳ１０６）。これら索引検証情報は、サーバ３００に送られ、サーバ３００は、これら索引検証情報を記憶領域３０２に記憶する。

次に、図４を参照して、索引検証情報生成部２０６の動作について具体例を挙げて説明する。ここでは、キーワードが索引番号２の「茨城大学」である場合を例に挙げて説明する。

この場合、索引検証情報生成部２０６は、索引を参照して、キーワード「茨城大学」を含む、該当するファイルのファイル番号を選択する。この場合、索引番号２のファイル番号には、「３」、「６」、「１０」が記憶されているので、索引検証情報生成部２０６は、該当ファイル番号として、「３」、「６」、「１０」を選択する。

そして、索引検証情報生成部２０６は、検証用の秘密鍵Ｋを使い、生成用組（茨城大学、３、６、１０）に対する検証情報ｔａｇ_２を、所定の生成アルゴリズムｆに従って、下記数式で示されるように生成する。
ｔａｇ_２＝ｆ_Ｋ（茨城大学、３、６、１０）

索引検証情報生成部２０６は、このようにして、キーワードｉ毎の索引検証情報ｔａｇ_ｉを生成する。生成された索引検証情報ｔａｇ_ｉは、サーバ３００へ送られ、サーバ３００は、送られてきた索引検証情報ｔａｇ_ｉを記憶領域３０２に記憶する。

図５を参照して、クライアント２００のファイル蓄積値計算部２１６の動作について説明する。ここでは、ファイルの総数がｎであるとする。

先ず、ファイル蓄積値計算部２１６は、全ファイルの集合｛（１，Ｄ_１），（２，Ｄ_２），・・・｝および公開情報Ｎ，ｇ、ｈ_ａを読み込む（ステップＳ２０２）。次に、ファイル蓄積値計算部２１６は、各ファイルＤ_ｉ（１≦ｉ≦ｎ）について、素数ｐ_ｉを下記の数式によって求める（ステップＳ２０４）。
ｐ_ｉ＝ｐｒｉｍｅ（Ｈ（ｉ，Ｄ_ｉ））
ここで、Ｈはハッシュ関数である。

そして、ファイル蓄積値計算部２１６は、ファイルの蓄積値Ａｃｃを下記の数式によって計算する（ステップＳ２０６）。
Ａｃｃ＝ｇ^{ｐ１ｐ２ｐ３．．．ｐｎ}ｍｏｄ Ｎ

ファイル蓄積値計算部２１６は、この計算して得られたファイルの蓄積値Ａｃｃを出力する（ステップＳ２０８）。ファイルの蓄積値Ａｃｃは、Ａｃｃ保持部２１８で保持される。

図６に、ファイル蓄積値計算部２１６の動作の具体例を示す。

すなわち、ファイル蓄積値計算部２１６は、各ファイルＤ_１、Ｄ_２、・・・、Ｄ_ｎについて、それぞれ、素数ｐ_１＝ｐｒｉｍｅ（Ｈ（１，Ｄ_１））、ｐ_２＝ｐｒｉｍｅ（Ｈ（２，Ｄ_２））、・・・、ｐ_ｎ＝ｐｒｉｍｅ（Ｈ（ｎ，Ｄ_ｎ））を求め、ファイルの蓄積値Ａｃｃ＝ｇ^{ｐ１ｐ２ｐ３．．．ｐｎ}ｍｏｄ Ｎを計算し、ファイルの蓄積値Ａｃｃを出力する。

検索時、クライアント２００は、検索キーワードＷを第３の信号線（伝送線）２１４を介してサーバ３００に送る。サーバ３００においては、検索キーワードＷに応答して、検索部３０４は、その検索キーワードＷを含むファイルおよびファイル番号の集合（ｉ１，Ｄ_ｉ１），（ｉ２，Ｄ_ｉ２），・・・と、その索引検証情報ｔａｇとをクライアント２００へ返す。したがって、クライアント２００は、ファイルおよびファイル番号の集合（ｉ１，Ｄ_ｉ１），（ｉ２，Ｄ_ｉ２），・・・とその索引検証情報ｔａｇとを取得する。すなわち、第２の信号線（伝送線）２１４は、検索キーワードＷをサーバ３００へ送って、サーバ３００から、検索キーワードＷを含むファイルおよびファイル番号の集合（ｉ１，Ｄ_ｉ１），（ｉ２，Ｄ_ｉ２），・・・と、その索引検証情報ｔａｇとを取得するファイル取得手段として働く。

尚、以下の説明では、検索キーワードＷを含むファイルおよびファイル番号の集合（ｉ１，Ｄ_ｉ１），（ｉ２，Ｄ_ｉ２），・・・を、単に、検索キーワードＷを含むファイルの集合とも略称する。

次に、図７を参照して、クライアント２００の索引検証部２０８の動作について説明する。

索引検証部２０８は、先ず、検索キーワードＷと、鍵保持部２０４に保持された検証用の秘密鍵Ｋとを読み込む（Ｓ３０２）。次に、検索検証部２０８は、サーバ３００から、検索キーワードＷを含むファイルの集合（ｉ１，Ｄ_ｉ１），（ｉ２，Ｄ_ｉ２），・・・と、その索引検証情報ｔａｇとを受け取る（ステップＳ３０４）。

索引検証部２０８は、検証用の秘密鍵Ｋを使い、索引検証情報ｔａｇが検証用組（Ｗ、ｉ１、ｉ２、…）の索引検証情報であるか否かを、所定の検証アルゴリズムに従って、下記の数式に示されるように計算する（ステップＳ３０６）。
Verify_Ｋ（Ｗ、ｉ１、ｉ２、…、ｔａｇ）＝accept or reject
ここで、Verifyは、ＭＡＣ検証アルゴリズムまたは署名検証アルゴリズムから成る所定の検証アルゴリズムである。

所定の検証アルゴリズムがＭＡＣ検証アルゴリズムから成るとする。この場合、索引検証部２０８は、検証用の秘密鍵ＫとしてＭＡＣの秘密鍵を使って、ＭＡＣ検証アルゴリズムに従って、取得した認証子が検証用組（Ｗ、ｉ１、ｉ２、…）の認証子であるか否かをチェックする。

一方、所定の検証アルゴリズムが署名検証アルゴリズムから成るとする。この場合、索引検証部２０８は、デジタル署名の公開鍵を使って、署名検証アルゴリズムに従って、取得したデジタル署名が検証用組（Ｗ、ｉ１、ｉ２、…）のデジタル署名であるか否かをチェックする。

索引検証部２０８は、acceptなら、accept（承認）を出力し（ステップＳ３１０）、rejectなら、reject（拒否）を出力する（ステップＳ３１２）。

次に、図８を参照して、索引検証部２０８の動作について具体例を挙げて説明する。ここでは、検索キーワードＷが索引番号２の「茨城大学」である場合を例に挙げて説明する。

この場合、索引検証部２０８は、鍵保持部２０４から検証用の秘密鍵Ｋを読み込み、検索キーワードとして「茨城大学」を読み込み、サーバ３００から送られてきた、ファイルの集合（Ｄ_３、Ｄ_６、Ｄ_１０）に対応するファイル番号の集合（３、６、１０）と索引検証情報ｔａｇとを読み込む。

そして、索引検証部２０８は、検証用の秘密鍵Ｋを使い、索引検証情報ｔａｇが検証用組（茨城大学、３、６、１０）の索引検証情報であるか否かを、所定の検証アルゴリズムに従って、下記の数式に示されるように計算する。
Verify_Ｋ（茨城大学、３、６、１０、ｔａｇ）＝accept or reject

索引検証部２０８は、acceptなら、accept（承認）を出力し、rejectなら、reject（拒否）を出力する。

図９を参照して、サーバ３００のファイル検証情報生成部３０８の動作について説明する。

先ず、ファイル検証情報生成部３０８は、検索部３０４からファイルの集合Ｓ＝｛（ｊ１，Ｄ_ｊ１），（ｊ２，Ｄ_ｊ２），・・・｝を読み込む（ステップＳ４０２）。引き続いて、ファイル検証情報生成部３０８は、記憶領域３０２から全ファイル｛（１、Ｄ_１），（２，Ｄ_２），・・・｝を読み込む（ステップＳ４０４）。そして、ファイル検証情報生成部３０８は、鍵保持部３０６から公開情報Ｎ，ｇ，ｈ_ａを読み込む（ステップＳ４０６）。

次に、ファイル検証情報生成部３０８は、ファイルの集合Ｓに含まれない各添字（ｉ１，ｉ２，・・・）について下記の数式に従って素数ｐ_ｉ（ｉ＝ｉ１，ｉ２，・・・）を計算し、さらに、ファイル検証情報πを下記の数式に従って計算する（ステップＳ４０８）。
ｐ_ｉ＝ｐｒｉｍｅ（Ｈ（ｉ，Ｄ_ｉ））
π＝ｇ^{ｐｉ１ｐｉ２・・・}ｍｏｄ Ｎ

そして、ファイル検証情報生成部３０８は、ファイル検証情報πを出力する（ステップＳ４１０）。このファイル検証情報πは、クライアント２００へ送出される。

図１０に、ファイル検証情報生成部３０８の動作の具体例を示す。この例では、検索部３０４からファイルの集合Ｓ＝｛（２，Ｄ_２），（４，Ｄ_４）｝が出力される場合を示している。

この場合、ファイル検索情報生成部３０８は、ファイル番号が２，４以外のすべてのファイルについて、ｐ_１＝ｐｒｉｍｅ（Ｈ（１，Ｄ_１）），ｐ_３＝ｐｒｉｍｅ（Ｈ（３，Ｄ_３）），ｐ_５＝ｐｒｉｍｅ（Ｈ（５，Ｄ_５）），ｐ_６＝ｐｒｉｍｅ（Ｈ（６，Ｄ_６）），・・・を計算し、ファイル検証情報π＝ｇ^{ｐ１ｐ３ｐ５ｐ６・・・}ｍｏｄ Ｎを計算して出力する。

図１１を参照して、クライアント２００のファイル検証部２２０の動作について説明する。

ファイル検証部２２０は、先ず、索引検証部２０８の結果がaccept（承認）であるか否かを判断する（ステップＳ５０２）。accept（承認）なら、ファイル検証部２２０はステップＳ５０４に進み、reject（拒否）なら、ファイル検証部２２０はreject（拒否）を出力する（ステップＳ５１４）。

ステップＳ５０４において、ファイル検証部２２０は、サーバ３００からファイルの集合Ｓ＝｛（ｉ１，Ｄ_ｉ１），（ｉ２，Ｄ_ｉ２），・・・｝と、そのファイル検証情報πを読み込む。そして、ファイル検証部２２０は、鍵保持部２０４から公開情報Ｎ，ｇ，ｈ_ａを読み込む。

引き続いて、ファイル検証部２２０は、ファイルの集合Ｓに含まれる各ファイルＤ_ｉ（Ｄ_ｉ１，Ｄ_ｉ２，・・・）について、下記の数式に従って素数ｐ_ｉを計算する（ステップＳ５０６）。
ｐ_ｉ＝ｐｒｉｍｅ（Ｈ（ｉ，Ｄ_ｉ））

次に、ファイル検証部２２０は、下記の数式に従ってファイルの蓄積値Ａを計算する（ステップＳ５０８）。
Ａ＝π^{ｐｉ１ｐｉ２・・・}ｍｏｄ Ｎ

そして、ファイル検証部２２０は、この計算したファイルの蓄積値Ａが、Ａｃｃ保持部２１８に保持されている全ファイルの蓄積値Ａｃｃと等しいか否か判断する（ステップＳ５１０）。

Ａ＝Ａｃｃの場合（ステップＳ５１０のＹｅｓ）、ファイル検証部２２０は、サーバ３００から取得したファイルの集合Ｓ＝｛（ｉ１，Ｄ_ｉ１），（ｉ２，Ｄ_ｉ２），・・・｝を所望のファイルの集合として出力する（ステップＳ５１２）。Ａ≠Ａｃｃの場合（ステップＳ５１０のＮｏ）、ファイル検証部２２０は、reject（拒否）を出力する（ステップＳ５１４）。

図１２に、ファイル検証部２２０の動作の具体例を示す。この例では、サーバ３００からファイルの集合Ｓ＝｛（２，Ｄ_２），（４，Ｄ_４）｝を受け取った場合の例を示している。

この場合、ファイル検証部２２０は、素数ｐ_２＝ｐｒｉｍｅ（Ｈ（２，Ｄ_２））およびｐ_４＝ｐｒｉｍｅ（Ｈ（４，Ｄ_４））を計算した後、ファイルの蓄積値Ａ＝π^ｐ２ｐ４ｍｏｄ Ｎを計算し、計算したファイルの蓄積値Ａが保持している全ファイルの蓄積値Ａｃｃと等しいか否か判断し、等しければ、取得したファイルの集合Ｄ_２、Ｄ_４を所望のファイルの集合として得、等しくなければ、reject（拒否）する。

図１３を参照して、本発明の第１の実施例に係る検索システム１００の更新フェーズについて説明する。図１３は、本発明の第１の実施例に係る検索システム１００の更新フェーズのブロック図である。

図１３に示されるように、クライアント（ユーザ端末）２００は、第４及び第５の信号線（伝送線）２２２、２２４と、Ａｃｃ更新部２２６と、を更に有する。

本例では、ファイル番号ｊを持つ現ファイルＤ_ｊを、新ファイルＤ_ｊ’に更新するか又は削除する場合の例を示している。すなわち、本例では、ファイル番号ｊを持つファイルが、更新（又は削除）すべきファイルであり、現ファイルＤ_ｊが更新前のファイルである。

この場合、クライアント２００は、新ファイルＤ_ｊ’又は「削除」を示すデータを第４の信号線（伝送線）２２２を介してサーバ３００へ送信すると共に、ファイル番号ｊを第５の信号線（伝送線）２２４を介してサーバ３００へ送信する。サーバ３００は、その送られてきた新ファイルＤ_ｊ’又は「削除」を示すデータをそのファイル番号ｊと共に記憶領域３０２に保管する。

したがって、第４及び第５の信号線（伝送線）２２２、２２４の組み合わせは、更新（削除）すべきファイルをそのファイル番号ｊと共にサーバ３００へ送って更新（削除）する更新手段として働く。

サーバ３００において、第５の信号線（伝送線）２２４を介してファイル番号ｊが渡されると、検索部３０４は、記憶領域３０２に既に格納されている現ファイル（更新前のファイル）Ｄ_ｊを検索して、そのファイル番号ｊが付加された現ファイル（ｊ、Ｄ_ｊ）をクライアント２００へ返す。

図１４を参照して、クライアント２００のＡｃｃ更新部２２６の動作について説明する。

先ず、Ａｃｃ更新部２２６は、ファイル番号ｊ、現ファイルＤ_ｊ、新ファイルＤ_ｊ’（又は「削除」を示すデータ）を読み込み、Ａｃｃ保持部２１８から全ファイルの蓄積値Ａｃｃを読み込み、鍵保持部２０４から秘密情報ｐ，ｑと公開情報Ｎ，ｇ，ｈ_ａを読み込む（ステップＳ６０２）。

引き続いて、Ａｃｃ更新部２２６は、下記の数式に従って、ｘ、ｘ’、およびｄを計算する（ステップＳ６０４）。
ｘ＝ｐｒｉｍｅ（Ｈ（ｊ，Ｄ_ｊ））
ｘ’＝ｐｒｉｍｅ（Ｈ（ｊ，Ｄ_ｊ’））
ｄ＝ｘ’／ｘ ｍｏｄ （ｐ−１）（ｑ−１）

次に、Ａｃｃ更新部２２６は、下記の数式に従って、新しい全ファイルの蓄積値Ａｃｃ’を計算する（ステップＳ６０６）。
Ａｃｃ’＝Ａｃｃ^ｄｍｏｄ Ｎ

最後に、Ａｃｃ更新部２２６は、計算した新しい全ファイルの蓄積値Ａｃｃ’をＡｃｃ保持部２１８に保持することにより、古い全ファイルの蓄積値Ａｃｃを新しい全ファイルの蓄積値Ａｃｃ’に更新する（ステップＳ６０８）。

このように、ファイルを更新（又は削除）しようとする場合、クライアント２００は、更新すべきファイル（又は「削除」を示すデータ）をそのファイル番号と共にサーバ３００へ送出し、全ファイルの蓄積値を更新するだけで良いので、ファイルの更新を効率的に行なうことができる。

次に、本第１の実施例の効果について説明する。

第１の実施例の検索システム１００の第１の効果は、サーバ３００の不正（ファイルの削除、追加、改ざん、すり替え）を検出できるだけでなく、ファイルの更新（削除を含む）を効率的に行なうことができることである。その理由は、クライアント（ユーザ端末）２００が各キーワードＷ_ｉと当該キーワードＷ_ｉを含む全てのファイルのファイル番号の集合（ｊ１、ｊ２、…）とを一組（生成用組）として、それに対する索引検証情報ｔａｇ_ｉを生成し、生成した索引検証情報ｔａｇ_ｉをサーバ３００に保管しているからである。

第１の実施例の検索システム１００の第２の効果は、リプレイ・アタックを検出できることである。その理由は、ＲＳＡ accumulatorを利用してファイルの蓄積値Ａｃｃをチェックしているからである。

尚、リプレイ・アタックを検出しない場合には、クライアント２００から、ファイル蓄積値計算部２１６、Ａｃｃ保持部２１８、ファイル検証部２２０、およびＡｃｃ更新部２２６を省略し、サーバ３００から鍵保持部３０６およびファイル検証情報生成部３０８を省略することができる。

また、上記本発明の第１の実施例に係る検索システム１００は、検索方法として実現され得る。さらに、上記本発明の第１の実施例に係る検索システム１００のうちのクライアント（ユーザ端末）２００が実施する部分は、当該クライアント（ユーザ端末）２００に含まれるメモリ（ＲＯＭ等）に格納された検索プログラムによって実行されるようにしてもよい。

図１５を参照して、本発明の第２の実施例に係る検索システム１００Ａの格納フェーズと検索フェーズについて説明する。図１５は、本発明の第２の実施例に係る検索システム１００Ａの格納フェーズと検索フェーズのブロック図である。図示の検索システム１００Ａは、上述した本発明の第２の実施形態に係る検索システムに相当する検索システムである。検索システム１００Ａは、クライアント２００Ａとサーバ３００Ａとから構成される。クライアント２００Ａは、ユーザ端末とも呼ばれる。

検索システム１００Ａは、クライアント（ユーザ端末）２００Ａがサーバ３００Ａに複数の暗号ファイルを保管し、クライアント（ユーザ端末）２００Ａがキーワード検索によってサーバ３００Ａから所望のファイルの集合を取得するシステムである。

尚、クライアント（ユーザ端末）２００Ａがサーバ３００Ａに格納された暗号ファイルを更新する更新フェーズのブロック図については、後で図２８を参照して説明する。

クライアント２００Ａは、鍵生成部２０２Ａと、鍵保持部２０４Ａと、索引検証情報生成部２０６Ａと、索引検証部２０８Ａと、ファイル暗号化部２１０Ａと、索引暗号化部２１２Ａと、キーワード暗号化部２１４Ａと、ファイル蓄積値計算部２１６Ａと、Ａｃｃ保持部２１８Ａと、ファイル検証部２２０Ａと、から構成されている。

一方、サーバ３００Ａは、記憶領域３０２Ａと、暗号検索部３０４Ａと、鍵保持部３０６Ａと、ファイル検証情報生成部３０８Ａと、から構成されている。

鍵生成部２０２Ａは、暗号化の秘密鍵Ｋ_ｅと、検証用の秘密鍵Ｋと、所定の秘密鍵Ｋ０、Ｋ１と、秘密情報ｐ，ｑと、公開情報Ｎ，ｇ，ｈ_ａとを生成する。鍵保持部２０４Ａは、この生成された暗号化の秘密鍵Ｋ_ｅと、検証用の秘密鍵Ｋと、所定の秘密鍵Ｋ０、Ｋ１と、秘密情報ｐ，ｑと公開情報Ｎ，ｇ，ｈ_ａとを保持する。また、鍵保持部２０４Ａに保持された公開情報Ｎ，ｇ，ｈ_ａは、サーバ３００Ａの鍵保持部３０６Ａへ送られる。したがって、サーバ３００Ａの鍵保持部３０６Ａは、公開情報Ｎ，ｇ，ｈ_ａを保持する。

ファイル暗号化部２１０Ａは、暗号化の秘密鍵Ｋ_ｅを使い、複数のファイルの暗号文である暗号ファイル｛Ｅ（Ｄ_１）、Ｅ（Ｄ_２）、…｝を計算する。これら暗号ファイル｛Ｅ（Ｄ_１）、Ｅ（Ｄ_２）、…｝は、それらのファイル番号と共にサーバ３００Ａへ送られ、サーバ３００Ａは、その送られてきた暗号ファイル｛Ｅ（Ｄ_１）、Ｅ（Ｄ_２）、…｝をそれらのファイル番号と共に記憶領域３０２Ａに記憶する。したがって、ファイル暗号化部２１０Ａは、暗号化の秘密鍵Ｋ_ｅを使って複数のファイルをそれぞれ暗号化し、複数の暗号ファイルをそれらのファイル番号と共にサーバ３００Ａに保管する暗号ファイル保管手段として働く。

また、クライアント２００Ａは、索引を生成する。索引の具体例は、前述した図２と同一である。前述したように、索引は、キーワードと、それに対応するファイルの番号（ファイル番号）の対応表である。

図２に示されるように、図示の例では、索引の番号１には、キーワードとして「情報工学」が記憶され、そのキーワードに対応するファイル番号として、「１」、「６」、「８」、「１１」が記憶されている。また、索引の番号２には、キーワードとして「茨城大学」が記憶され、そのキーワードに対応するファイル番号として、「３」、「６」、「１０」が記憶されている。

索引暗号化部２１２Ａは、所定の秘密鍵Ｋ０、Ｋ１を使い、生成した索引を暗号化して、暗号化索引をサーバ３００Ａへ送信する。サーバ３００Ａは、その送られてきた暗号化索引を記憶領域３０２Ａに記憶する。したがって、索引暗号化部２１２Ａは、生成した索引を暗号化して、暗号化索引をサーバ３００Ａへ保管する暗号化索引保管手段として働く。

図１６を参照して、クライアント２００Ａの索引暗号化部２１２Ａの動作について説明する。

ここでは、索引暗号化部２１２Ａの動作について説明する前に、先ず、記法について説明する。

ＰＲＦ_ｋ（・）は擬似ランダム関数を表す。ただし、ｋは鍵である。
［ＰＲＦ_ｋ（Ｗ）］_ｕにより、ＰＲＦ_ｋ（Ｗ）の先頭のｕビットを表す。
文書（ファイル）の総数をｎとする。
キーワードＷ_ｉがファイルＤ_ｊに含まれるなら、ｅ_ｉ，ｊ＝１と表し、そうでなければ、ｅ_ｉ，ｊ＝０と表す。

先ず、索引暗号化部２１２Ａは、索引と所定の秘密鍵Ｋ０、Ｋ１とを読み込む（ステップＳ７０２）。

引き続いて、索引暗号化部２１２Ａは、各キーワードＷｉについて、下記の数式で表される、ｌａｂｅｌ_ｉ、ＰＡＤ_ｉ、およびＯＴＰ_ｉを計算する（ステップＳ７０４）。
ｌａｂｅｌ_ｉ＝［ＰＲＦ_Ｋ０（Ｗ_ｉ）］_１２８
ＰＡＤ_ｉ＝［ＰＲＦ_Ｋ１（Ｗ_ｉ）］_ｎ
ＯＴＰ_ｉ＝ＰＡＤ_ｉ＋（ｅ_ｉ，１，・・・、ｅ_ｉ，ｎ）ｍｏｄ ２
ここで、ｌａｂｅｌ_ｉは、キーワードＷ_ｉの暗号文を表し、ＯＴＰ_ｉは、キーワードＷ_ｉを含むファイルのファイル番号の暗号文を表す。

そして、索引暗号化部２１２Ａは、暗号化索引＝｛（ｌａｂｅｌ_１，ＯＴＰ_１），（ｌａｂｅｌ_２，ＯＴＰ_２），・・・｝を出力する（ステップＳ７０６）。

このように、索引暗号化部２１２Ａは、キーワードＷ_ｉとそのキーワードＷ_ｉに対応するファイルのファイル番号との対応表である索引を、所定の秘密鍵Ｋ０，Ｋ１を使って暗号化し、キーワードＷ_ｉの暗号文ｌａｂｅｌ_ｉとそのキーワードＷ_ｉを含むファイルのファイル番号の暗号文ＯＴＰ_ｉとから成る暗号化索引をサーバ３００Ａに保管する暗号化索引保管手段として働く。

次に、図１７を参照して、索引暗号化部２１２Ａの動作について具体例を挙げて説明する。ここでは、ファイル（文書）の総数ｎ＝１２で、キーワードが索引番号２の「茨城大学」である場合を例に挙げて説明する。したがって、この場合、索引番号２のファイル番号には、「３」、「６」、「１０」が記憶されている。

この場合、索引暗号化部２１２Ａは、キーワードＷ_２の暗号文ｌａｂｅｌ_２と、ファイル番号の暗号文ＯＴＰ_２とを計算する。

ただし、キーワードＷ_２の暗号文ｌａｂｅｌ_２は、下記の数式で表される。
ｌａｂｅｌ_２＝［ＰＲＦ_Ｋ０（茨城大学）］_１２８

また、（ｅ_２，１，・・・，ｅ_２，１２）は、（００１００１０００１００）に等しい。また、ＰＡＤ_２は下記の数式で表され、ここで（１１０１０１０１１１１０）であったとする。
ＰＡＤ_２＝［ＰＲＦ_Ｋ１（茨城大学）］_１２
＝（１１０１０１０１１１１０）

よって、ファイル番号の暗号文ＯＴＰ_２は、それらの排他的論理和（ｘｏｒ）であるので、本例では、下記の数式で表される。
ＯＴＰ_２＝（１１１１０００１１０１０）

クライアント２００Ａの索引検証情報生成部２０６Ａの動作は、図３および図４に示したものと同様であるので、重複を避けるためにその説明を省略する。

図１８を参照して、クライアント２００Ａのファイル蓄積値計算部２１６Ａの動作について説明する。

先ず、ファイル蓄積値計算部２１６Ａは、全暗号ファイルの集合｛（１、Ｅ（Ｄ_１）），（２，Ｅ（Ｄ_２）），・・・｝および公開情報Ｎ，ｇ、ｈ_ａを読み込む（ステップＳ２０２Ａ）。次に、ファイル蓄積値計算部２１６Ａは、各暗号ファイルＥ（Ｄ_ｉ）（１≦ｉ≦ｎ）について、素数ｐ_ｉを下記の数式によって求める（ステップＳ２０４Ａ）。
ｐ_ｉ＝ｐｒｉｍｅ（Ｈ（ｉ，Ｅ（Ｄ_ｉ）））
ここで、Ｈはハッシュ関数である。

そして、ファイル蓄積値計算部２１６Ａは、ファイルの蓄積値Ａｃｃを下記の数式によって計算する（ステップＳ２０６Ａ）。
Ａｃｃ＝ｇ^{ｐ１ｐ２ｐ３．．．ｐｎ}ｍｏｄ Ｎ

ファイル蓄積値計算部２１６Ａは、この計算して得られたファイルの蓄積値Ａｃｃを出力する（ステップＳ２０８Ａ）。ファイルの蓄積値Ａｃｃは、Ａｃｃ保持部２１８Ａで保持される。

図１９に、ファイル蓄積値計算部２１６Ａの動作の具体例を示す。

すなわち、ファイル蓄積値計算部２１６は、各暗号ファイルＥ（Ｄ_１）、Ｅ（Ｄ_２）、・・・、Ｅ（Ｄ_ｎ）について、それぞれ、素数ｐ_１＝ｐｒｉｍｅ（Ｈ（１，Ｅ（Ｄ_１）））、ｐ_２＝ｐｒｉｍｅ（Ｈ（２，Ｅ（Ｄ_２）））、・・・、ｐ_ｎ＝ｐｒｉｍｅ（Ｈ（ｎ，Ｅ（Ｄ_ｎ）））を求め、ファイルの蓄積値Ａｃｃ＝ｇ^{ｐ１ｐ２ｐ３．．．ｐｎ}ｍｏｄ Ｎを計算し、ファイルの蓄積値Ａｃｃを出力する。

検索時、クライアント２００Ａでは、キーワード暗号化部２１４Ａが、所定の秘密鍵Ｋ０、Ｋ１を使って検索キーワードＷを暗号化し、暗号検索キーワード（ｌａｂｅｌ^＊，ＰＡＤ^＊）をサーバ３００Ａに送る。

図２０を参照して、クライアント２００Ａのキーワード暗号化部２１４Ａの動作について説明する。

キーワード暗号化部２１４Ａは、先ず、検索キーワードＷと所定の秘密鍵Ｋ０，Ｋ１とを読み込む（ステップＳ８０２）。引き続いて、キーワード暗号化部２１４Ａは、下記の数式に従って、暗号検索キーワード（ｌａｂｅｌ^＊，ＰＡＤ^＊）を計算する（ステップＳ８０４）。
ｌａｂｅｌ^＊＝［ＰＲＦ_Ｋ０（Ｗ）］_１２８
ＰＡＤ^＊＝［ＰＲＦ_Ｋ１（Ｗ）］_ｎ

そして、キーワード暗号化部２１４Ａは、計算により得られた暗号検索キーワード（ｌａｂｅｌ^＊，ＰＡＤ^＊）をサーバ３００Ａへ送信する（ステップＳ８０６）。

図２１に、キーワード暗号化部２１４Ａの動作の具体例を示す。本例では、検索キーワードＷが「茨城大学」であって、ファイルの総数ｎが１２に等しい場合の例を示している。

この場合、キーワード暗号化部２１４Ａは、下記の数式に従って、暗号検索キーワード（ｌａｂｅｌ^＊，ＰＡＤ^＊）を計算する。
ｌａｂｅｌ^＊＝［ＰＲＦ_Ｋ０（茨城大学）］_１２８
ＰＡＤ^＊＝［ＰＲＦ_Ｋ１（茨城大学）］_１２
（＝１１０１０１０１１１１０）

キーワード暗号化部２１４Ａは、計算により得られた暗号検索キーワード（ｌａｂｅｌ^＊，ＰＡＤ^＊）をサーバ３００Ａへ送信する。

サーバ３００Ａにおいては、暗号検索キーワード（ｌａｂｅｌ^＊，ＰＡＤ^＊）に応答して、暗号検索部３０４Ａは、その検索キーワードＷを含む暗号ファイルの集合｛（ｊ１，Ｅ（Ｄ_ｊ１）），（ｊ２，Ｅ（Ｄ_ｊ２）），・・・｝とその索引検証情報ｔａｇ_ｊとをクライアント２００Ａへ返す。

図２２を参照して、サーバ３００Ａの暗号検索部３０４Ａの動作について説明する。

先ず、暗号検索部３０４Ａは、クライアント２００Ａから送出されてきた暗号検索キーワード（ｌａｂｅｌ^＊，ＰＡＤ^＊）を検索用データとして読み込む（ステップＳ９０２）。

引き続いて、暗号検索部３０４Ａは、記憶領域３０２Ａに格納されている暗号化索引の中からｌａｂｅｌ^＊＝ｌａｂｅｌ_ｊとなるｊを見つけて、（ｌａｂｅｌ_ｊ，ＯＴＰ_ｊ，ｔａｇ_ｊ）を見つける（ステップＳ９０４）。

次に、暗号検索部３０４Ａは、下記の数式を計算する（ステップＳ９０６）。
（ｅ_１，・・・，ｅ_ｎ）＝ＯＴＰ_ｊ＋ＰＡＤ^＊ｍｏｄ ２

そして、暗号検索部３０４Ａは、ｅ_ｊ＝１となるｊの集合｛ｊ１，ｊ２，・・・｝を求める（ステップＳ９０８）。

次に、暗号検索部３０４Ａは、検索キーワードＷを含む暗号ファイルの集合｛（ｊ１，Ｅ（Ｄ_ｊ１）），（ｊ２，Ｅ（Ｄ_ｊ２）），・・・｝とその索引検証情報ｔａｇ_ｊとを出力する（ステップＳ９１０）。

したがって、クライアント２００Ａは、暗号ファイルの集合｛（ｊ１，Ｅ（Ｄ_ｊ１）），（ｊ２，Ｅ（Ｄ_ｊ２）），・・・｝とその索引検証情報ｔａｇ_ｊとを取得する。

図２３に暗号検索部３０４Ａの動作の具体例を示す。本例では、ｊが２に等しく、ｎが１２に等しい場合の例を示している。

ｊ＝２であるので、暗号検索部３０４Ａは、暗号化索引の中から（ｌａｂｅｌ_２，ＯＴＰ_２，ｔａｇ_２）を見つける。そして、暗号検索部３０４Ａは、下記の数式を計算する。
（ｅ_１，・・・，ｅ_１２）＝ＯＴＰ_２＋ＰＡＤ^＊ｍｏｄ ２

本例では、ＰＡＤ^＊およびＯＴＰ_２は、それぞれ、下記の数式に等しいとする。
ＰＡＤ^＊＝（１１０１０１０１１１１０）
ＯＴＰ_２＝（１１１１０００１１０１０）

この場合、（ｅ_１，・・・，ｅ_１２）は、それらの排他的論理和ｘｏｒであるので、下記の数式で表される。
（ｅ_１，・・・，ｅ_１２）＝（００１００１０００１００）

よって、ｅ_３＝１、ｅ_６＝１、ｅ_１０＝１であるので、該当する文書番号（ファイル番号は、（３，６，１０）となる。

したがって、暗号検索部３０４Ａは、検索キーワードＷを含む暗号ファイルの集合｛（３，Ｅ（Ｄ_３）），（６，Ｅ（Ｄ_６）），（１０，Ｅ（Ｄ_１０））｝とその索引検証情報ｔａｇ_２とを出力する。

上述したように、キーワード暗号化部２１４Ａは、所定の秘密鍵Ｋ０、Ｋ１を使って検索キーワードＷを暗号化して得られる暗号検索キーワード（ｌａｂｅｌ^＊，ＰＡＤ^＊）をサーバ３００Ａへ送って、サーバ３００Ａから、暗号ファイルの集合｛（ｊ１，Ｅ（Ｄ_ｊ１）），（ｊ２，Ｅ（Ｄ_ｊ２）），・・・｝と検索キーワードＷに対応する索引検証情報ｔａｇ_ｊとを取得する暗号ファイル取得手段として働く。

クライアント２００Ａの索引検証部２０８Ａの動作は、図７および図８と実質的に同様なので、その詳細な動作説明については省略する。相違点は、図７のステップＳ３０４における「ファイルの集合」が、「暗号ファイルの集合」に変更されていることだけである。

図２４を参照して、サーバ３００Ａのファイル検証情報生成部３０８Ａの動作について説明する。

先ず、ファイル検証情報生成部３０８Ａは、暗号検索部３０４Ａから暗号ファイルの集合Ｓ＝｛（ｊ１，Ｅ（Ｄ_ｊ１）），（ｊ２，Ｅ（Ｄ_ｊ２）），・・・｝を読み込む（ステップＳ４０２Ａ）。引き続いて、ファイル検証情報生成部３０８Ａは、記憶領域３０２Ａから全暗号ファイル｛（１、Ｅ（Ｄ_１）），（２，Ｅ（Ｄ_２）），・・・｝を読み込む（ステップＳ４０４Ａ）。そして、ファイル検証情報生成部３０８Ａは、鍵保持部３０６Ａから公開情報Ｎ，ｇ，ｈ_ａを読み込む（ステップＳ４０６Ａ）。

次に、ファイル検証情報生成部３０８Ａは、暗号ファイルの集合Ｓに含まれない各添字（すなわち、ファイル番号）（ｉ１，ｉ２，・・・）について下記の数式に従って素数ｐ_ｉ（ｉ＝ｉ１，ｉ２，・・・）を計算し、さらに、ファイル検証情報πを下記の数式に従って計算する（ステップＳ４０８Ａ）。
ｐ_ｉ＝ｐｒｉｍｅ（Ｈ（ｉ，Ｅ（Ｄ_ｉ）））
π＝ｇ^{ｐｉ１ｐｉ２・・・}ｍｏｄ Ｎ

そして、ファイル検証情報生成部３０８Ａは、ファイル検証情報πを出力する（ステップＳ４１０Ａ）。このファイル検証情報πは、クライアント２００Ａへ送出される。

図２５に、ファイル検証情報生成部３０８Ａの動作の具体例を示す。この例では、暗号検索部３０４Ａから暗号ファイルの集合Ｓ＝｛（２，Ｅ（Ｄ_２）），（４，Ｅ（Ｄ_４））｝が出力された場合の例を示している。

この場合、ファイル検索情報生成部３０８Ａは、ファイル番号が２，４以外のすべての暗号ファイルについて、ｐ_１＝ｐｒｉｍｅ（Ｈ（１，Ｅ（Ｄ_１））），ｐ_３＝ｐｒｉｍｅ（Ｈ（３，Ｅ（Ｄ_３））），ｐ_５＝ｐｒｉｍｅ（Ｈ（５，Ｅ（Ｄ_５））），ｐ_６＝ｐｒｉｍｅ（Ｈ（６，Ｅ（Ｄ_６））），・・・を計算し、ファイル検証情報π＝ｇ^{ｐ１ｐ３ｐ５ｐ６・・・}ｍｏｄ Ｎを計算して出力する。

図２６を参照して、クライアント２００Ａのファイル検証部２２０Ａの動作について説明する。

ファイル検証部２２０Ａは、先ず、索引検証部２０８Ａの結果がaccept（承認）であるか否かを判断する（ステップＳ５０２Ａ）。accept（承認）なら、ファイル検証部２２０ＡはステップＳ５０４Ａに進み、reject（拒否）なら、ファイル検証部２２０Ａはreject（拒否）を出力する（ステップＳ５１４Ａ）。

ステップＳ５０４Ａにおいて、ファイル検証部２２０Ａは、サーバ３００Ａから暗号ファイルの集合Ｓ＝｛（ｉ１，Ｅ（Ｄ_ｉ１）），（ｉ２，Ｅ（Ｄ_ｉ２）），・・・｝と、そのファイル検証情報πを読み込む。そして、ファイル検証部２２０Ａは、鍵保持部２０４Ａから公開情報Ｎ，ｇ，ｈ_ａを読み込む。

引き続いて、ファイル検証部２２０Ａは、暗号ファイルの集合Ｓに含まれる各暗号ファイルＥ（Ｄ_ｉ）（Ｅ（Ｄ_ｉ１），Ｅ（Ｄ_ｉ２），・・・）について、下記の数式に従って素数ｐ_ｉを計算する（ステップＳ５０６Ａ）。
ｐ_ｉ＝ｐｒｉｍｅ（Ｈ（ｉ，Ｅ（Ｄ_ｉ）））

次に、ファイル検証部２２０Ａは、下記の数式に従ってファイルの蓄積値Ａを計算する（ステップＳ５０８Ａ）。
Ａ＝π^{ｐｉ１ｐｉ２・・・}ｍｏｄ Ｎ

そして、ファイル検証部２２０Ａは、この計算したファイルの蓄積値Ａが、Ａｃｃ保持部２１８Ａに保持されている全ファイルの蓄積値Ａｃｃと等しいか否か判断する（ステップＳ５１０Ａ）。

Ａ＝Ａｃｃの場合（ステップＳ５１０ＡのＹｅｓ）、ファイル検証部２２０Ａは、サーバ３００Ａから取得した暗号ファイルの集合Ｓ＝｛（ｉ１，Ｅ（Ｄ_ｉ１）），（ｉ２，Ｅ（Ｄ_ｉ２）），・・・｝を復号して、所望のファイルの集合｛（ｉ１，Ｄ_ｉ１），（ｉ２，Ｄ_ｉ２），・・・｝として出力する（ステップＳ５１２Ａ）。Ａ≠Ａｃｃの場合（ステップＳ５１０ＡのＮｏ）、ファイル検証部２２０Ａは、reject（拒否）を出力する（ステップＳ５１４Ａ）。

図２７に、ファイル検証部２２０Ａの動作の具体例を示す。この例では、サーバ３００Ａから暗号ファイルの集合Ｓ＝｛（２，Ｅ（Ｄ_２）），（４，Ｅ（Ｄ_４））｝を受け取った場合を示している。

この場合、ファイル検証部２２０Ａは、素数ｐ_２＝ｐｒｉｍｅ（Ｈ（２，Ｅ（Ｄ_２）））およびｐ_４＝ｐｒｉｍｅ（Ｈ（４，Ｅ（Ｄ_４）））を計算した後、ファイルの蓄積値Ａ＝π^ｐ２ｐ４ｍｏｄ Ｎを計算し、計算したファイルの蓄積値Ａが保持している全ファイルの蓄積値Ａｃｃと等しいか否か判断し、等しければ、取得した暗号ファイルの集合Ｅ（Ｄ_２）、Ｅ（Ｄ_４）を復号して、所望のファイルの集合Ｄ_２、Ｄ_４を得、等しくなければ、reject（拒否）する。

図２８を参照して、本発明の第２の実施例に係る検索システム１００Ａの更新フェーズについて説明する。図２８は、本発明の第２の実施例に係る検索システム１００Ａの更新フェーズのブロック図である。

図２８に示されるように、クライアント（ユーザ端末）２００Ａは、第１及び第２の信号線（伝送線）２２２Ａ、２２４Ａと、Ａｃｃ更新部２２６Ａと、を更に有する。

本例では、ファイル番号ｊを持つ現暗号ファイルＥ（Ｄ_ｊ）を、新暗号ファイルＥ（Ｄ_ｊ’）に更新するか又は削除する場合を示している。すなわち、本例では、ファイル番号ｊを持つ暗号ファイルが、更新（又は削除）すべき暗号ファイルであり、現暗号ファイルＥ（Ｄ_ｊ）が更新前の暗号ファイルである。

この場合、クライアント２００Ａは、新暗号ファイルＥ（Ｄ_ｊ’）又は「削除」を示すデータを第１の信号線（伝送線）２２２Ａを介してサーバ３００Ａへ送信すると共に、ファイル番号ｊを第２の信号線（伝送線）２２４Ａを介してサーバ３００Ａへ送信する。サーバ３００Ａは、その送られてきた新暗号ファイルＥ（Ｄ_ｊ’）又は「削除」を示すデータをそのファイル番号ｊと共に記憶領域３０２Ａに保管する。

したがって、第１及び第２の信号線（伝送線）２２２Ａ、２２４Ａの組み合わせは、更新（削除）すべき暗号ファイルをそのファイル番号ｊと共にサーバ３００Ａへ送って更新（削除）する更新手段として働く。

尚、新暗号ファイルＥ（Ｄ_ｊ’）は、図１５に示すファイル暗号化部２１０Ａを使用して、新ファイルＤ_ｊ’を暗号化することによって生成してよい。

サーバ３００Ａにおいて、第２の信号線（伝送線）２２４Ａを介してファイル番号ｊが渡されると、暗号検索部３０４Ａは、記憶領域３０２Ａに既に格納されている現暗号ファイル（更新前の暗号ファイル）Ｅ（Ｄ_ｊ）を検索して、そのファイル番号ｊが付加された現暗号ファイル（ｊ、Ｅ（Ｄ_ｊ））をクライアント２００Ａへ返す。

図２９を参照して、クライアント２００ＡのＡｃｃ更新部２２６Ａの動作について説明する。

先ず、Ａｃｃ更新部２２６Ａは、ファイル番号ｊ、現暗号ファイルＥ（Ｄ_ｊ）、新暗号ファイルＥ（Ｄ_ｊ’）（又は「削除」を示すデータ）を読み込み、Ａｃｃ保持部２１８Ａから全暗号ファイルの蓄積値Ａｃｃを読み込み、鍵保持部２０４Ａから秘密情報ｐ，ｑと公開情報Ｎ，ｇ，ｈ_ａを読み込む（ステップＳ６０２Ａ）。

引き続いて、Ａｃｃ更新部２２６Ａは、下記の数式に従って、ｘ、ｘ’、およびｄを計算する（ステップＳ６０４Ａ）。
ｘ＝ｐｒｉｍｅ（Ｈ（ｊ，Ｅ（Ｄ_ｊ）））
ｘ’＝ｐｒｉｍｅ（Ｈ（ｊ，Ｅ（Ｄ_ｊ’）））
ｄ＝ｘ’／ｘ ｍｏｄ （ｐ−１）（ｑ−１）

次に、Ａｃｃ更新部２２６Ａは、下記の数式に従って、新しい全暗号ファイルの蓄積値Ａｃｃ’を計算する（ステップＳ６０６Ａ）。
Ａｃｃ’＝Ａｃｃ^ｄｍｏｄ Ｎ

最後に、Ａｃｃ更新部２２６Ａは、計算した新しい全暗号ファイルの蓄積値Ａｃｃ’をＡｃｃ保持部２１８Ａに保持することにより、古い全暗号ファイルの蓄積値Ａｃｃを新しい全暗号ファイルの蓄積値Ａｃｃ’に更新する（ステップＳ６０８Ａ）。

このように、暗号ファイルを更新（又は削除）しようとする場合、クライアント２００Ａは、更新すべき暗号ファイル（又は「削除」を示すデータ）をそのファイル番号と共にサーバ３００Ａへ送出し、全暗号ファイルの蓄積値を更新するだけで良いので、暗号ファイルの更新（削除）を効率的に行なうことができる。

次に、本第２の実施例の効果について説明する。

第２の実施例の検索システム１００Ａの第１の効果は、サーバの不正（ファイルの削除、追加、改ざん、すり替え）を検出ことができるだけでなく、ファイルの更新（削除を含む）を効率的に行うことができることである。その理由は、クライアント（ユーザ端末）２００Ａが各キーワードＷ_ｉと当該キーワードＷ_ｉを含む全てのファイルの集合を暗号化して得られる暗号ファイル｛Ｅ（Ｄ_j1）、Ｅ（Ｄ_j２）、…｝のファイル番号の集合（ｊ１、ｊ２、…）とを一組（生成用組）として、それに対する索引検証情報ｔａｇ_ｉを生成し、生成した索引検証情報ｔａｇ_ｉをサーバ３００Ａに保管しているからである。

第２の実施例の検索システム１００Ａの第２の効果は、リプレイ・アタックを検出できることである。その理由は、ＲＳＡ accumulatorを利用してファイルの蓄積値Ａｃｃをチェックしているからである。

尚、リプレイ・アタックを検出しない場合には、クライアント２００Ａから、ファイル蓄積値計算部２１６Ａ、Ａｃｃ保持部２１８Ａ、ファイル検証部２２０Ａ、およびＡｃｃ更新部２２６Ａを省略し、サーバ３００Ａから鍵保持部３０６Ａおよびファイル検証情報生成部３０８Ａを省略することができる。

また、上記本発明の第２の実施例に係る検索システム１００Ａは、検索方法として実現され得る。さらに、上記本発明の第２の実施例に係る検索システム１００Ａのうちのクライアント（ユーザ端末）２００Ａが実施する部分は、当該クライアント（ユーザ端末）２００Ａに含まれるメモリ（ＲＯＭ等）に格納された検索プログラムによって実行されるようにしてもよい。

以上、実施形態（実施例）を参照して本発明を説明したが、本発明は上記実施形態（実施例）に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。

上記の実施形態（実施例）の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。

（付記１） ユーザ端末がサーバに複数のファイルを保管し、前記ユーザ端末がキーワード検索によって前記サーバから所望のファイルの集合を取得すると共に、ファイルの更新をも行う検索システムであって、前記ユーザ端末は、
前記複数のファイルをそれらのファイル番号と共に前記サーバに保管するファイル保管手段と、
キーワードと該キーワードに対応するファイルのファイル番号との対応表である索引を、前記サーバに保管する索引保管手段と、
前記キーワードと該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成し、該生成した索引検証情報を前記サーバに保管する索引検証情報生成部と、
検索キーワードを前記サーバへ送って、前記サーバから前記検索キーワードを含むファイルおよび当該ファイルのファイル番号の集合と前記検索キーワードに対応する索引検証情報とを取得するファイル取得手段と、
該取得した索引検証情報が、前記検索キーワードと前記取得したファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックし、チェックの結果が正しければ承認し、そうでなければ拒否する索引検証部と、
更新すべきファイルをそのファイル番号と共に前記サーバへ送って更新する更新手段と、
を有する検索システム。

(付記２) 前記更新すべきファイルが削除を示すデータから成る、付記１に記載の検索システム。

(付記３) 前記ユーザ端末は、
秘密鍵と所定の公開情報とを保持するユーザ鍵保持部と、
前記所定の公開情報と前記複数のファイルとから全ファイルの蓄積値を計算するファイル蓄積値計算部と、
前記全ファイルの蓄積値を保持する蓄積値保持部と、
を更に備え、
前記サーバは、
前記所定の公開情報を保持するサーバ鍵保持部と、
前記所定の公開情報に基づいて、当該サーバに保管された全ファイルの内、前記検索キーワードを含むファイルの集合以外のファイルを使用して、ファイル検証情報を生成して前記ユーザ端末へ送出するファイル検証情報生成部と、
を備え、
前記ユーザ端末は、
前記索引検証部で承認された場合、前記所定の公開情報に基づいて、前記取得したファイルの集合と前記ファイル検証情報とを使用して、ファイルの蓄積値を計算し、該計算したファイルの蓄積値と前記保持した全ファイルの蓄積値とが等しければ、前記取得したファイルの集合を前記所望のファイルの集合として得、そうでなければ拒否するファイル検証部を更に有する、
付記１又は２に記載の検索システム。

（付記４） 前記ユーザ端末は、
前記所定の公開情報に基づいて、前記更新すべきファイル、更新前のファイル、そのファイル番号、および前記蓄積値保持部に保持された全ファイルの蓄積値を使用して、新しい全ファイルの蓄積値を計算し、該計算した新しい全ファイルの蓄積値を前記蓄積値保持部に保持する蓄積値更新部を更に有する、
付記３に記載の検索システム。

（付記５） 前記所定の生成アルゴリズムが署名生成アルゴリズムから成り、
前記所定の検証アルゴリズムが署名検証アルゴリズムから成り、
前記索引検証情報生成部は、デジタル署名の秘密鍵を使って、前記署名生成アルゴリズムに従って、前記索引検証情報として前記生成用組に対するデジタル署名を生成し、
前記索引検証部は、デジタル署名の公開鍵を使って、前記署名検証アルゴリズムに従って、取得したデジタル署名が前記検証用組のデジタル署名であるか否かをチェックする、
付記１乃至４のいずれか１つに記載の検索システム。

（付記６） 前記所定の生成アルゴリズムがＭＡＣ（Message Authentication Code）生成アルゴリズムから成り、
前記所定の検証アルゴリズムがＭＡＣ検証アルゴリズムから成り、
前記索引検証情報生成部は、ＭＡＣの秘密鍵を使って、前記ＭＡＣ生成アルゴリズムに従って、前記索引検証情報として前記生成用組に対する認証子を生成し、
前記索引検証部は、前記ＭＡＣの秘密鍵を使って、前記ＭＡＣ検証アルゴリズムに従って、取得した認証子が前記検証用組の認証子であるか否かをチェックする、
付記１乃至４のいずれか１つに記載の検索システム。

（付記７） ユーザ端末がサーバに複数のファイルを保管し、前記ユーザ端末がキーワード検索によって前記サーバから所望のファイルの集合を取得すると共に、ファイルの更新をも行う検索方法であって、
前記ユーザ端末が、前記複数のファイルをそれらのファイル番号と共に前記サーバに保管するステップと、
前記ユーザ端末が、キーワードと該キーワードに対応するファイルのファイル番号との対応表である索引を、前記サーバに保管するステップと、
前記ユーザ端末が、前記キーワードと該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成するステップと、
前記ユーザ端末が、前記生成した索引検証情報を前記サーバに保管するステップと、
前記ユーザ端末が、検索キーワードを前記サーバへ送って、前記サーバから前記検索キーワードを含むファイルおよび当該ファイルのファイル番号の集合と前記検索キーワードに対応する索引検証情報とを取得するステップと、
前記ユーザ端末が、前記取得した索引検証情報が、前記検索キーワードと前記取得したファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックするステップと、
前記ユーザ端末が、チェックの結果が正しければ承認し、そうでなければ拒否するステップと、
前記ユーザ端末が、更新すべきファイルをそのファイル番号と共に前記サーバへ送って更新するステップと、
を含む検索方法。

（付記８） 前記更新すべきファイルが削除を示すデータから成る、付記７に記載の検索方法。

（付記９） サーバに複数のファイルを保管し、キーワード検索によって前記サーバから所望のファイルの集合を取得すると共に、ファイルの更新をも行う処理を、コンピュータであるユーザ端末に実行させる検索プログラムであって、前記コンピュータに、
前記複数のファイルをそれらのファイル番号と共に前記サーバに保管する手順と、
キーワードと該キーワードに対応するファイルのファイル番号との対応表である索引を、前記サーバに保管する手順と、
前記キーワードと該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成する手順と、
前記生成した索引検証情報を前記サーバに保管する手順と、
検索キーワードを前記サーバへ送って、前記サーバから前記検索キーワードを含むファイルおよび当該ファイルのファイル番号の集合と前記検索キーワードに対応する索引検証情報とを取得する手順と、
前記取得した索引検証情報が、前記検索キーワードと前記取得したファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックする手順と、
チェックの結果が正しければ承認し、そうでなければ拒否する手順と、
更新すべきファイルをそのファイル番号と共に前記サーバへ送って更新する手順と、
を実行させるための検索プログラム。

（付記１０） 前記更新すべきファイルが削除を示すデータから成る、付記９に記載の検索プログラム。

（付記１１） ユーザ端末がサーバに複数の暗号ファイルを保管し、前記ユーザ端末がキーワード検索によって前記サーバから所望のファイルの集合を取得すると共に、暗号ファイルの更新をも行う検索システムであって、前記ユーザ端末は、
暗号化の秘密鍵を使って複数のファイルをそれぞれ暗号化し、前記複数の暗号ファイルをそれらの暗号ファイルのファイル番号と共に前記サーバに保管する暗号ファイル保管手段と、
キーワードと該キーワードに対応するファイルのファイル番号との対応表である索引を、所定の秘密鍵を使って暗号化し、前記キーワードの暗号文と該キーワードを含むファイルのファイル番号の暗号文とから成る暗号化索引を前記サーバに保管する暗号化索引保管手段と、
前記キーワードと該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成し、該生成した索引検証情報を前記サーバに保管する索引検証情報生成部と、
前記所定の秘密鍵を使って検索キーワードを暗号化して得られる暗号検索キーワードを前記サーバへ送って、前記サーバから前記暗号検索キーワードを含む暗号ファイルおよび当該暗号ファイルのファイル番号の集合と前記検索キーワードに対応する索引検証情報とを取得する暗号ファイル取得手段と、
該取得した索引検証情報が、前記検索キーワードと前記取得した暗号ファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックし、チェックの結果が正しければ承認し、そうでなければ拒否する索引検証部と、
更新すべきファイルを前記暗号化の秘密鍵を使って暗号化して得られる、更新すべき暗号ファイルをそのファイル番号と共に前記サーバに送って更新する更新手段と、
を有する検索システム。

（付記１２） 前記更新すべき暗号ファイルが削除を示すデータから成る、付記１１に記載の検索システム。

（付記１３） 前記ユーザ端末は、
前記暗号化の秘密鍵と前記所定の秘密鍵と所定の公開情報とを保持するユーザ鍵保持部と、
前記所定の公開情報と前記複数の暗号ファイルとから全暗号ファイルの蓄積値を計算するファイル蓄積値計算部と、
前記全暗号ファイルの蓄積値を保持する蓄積値保持部と、
を更に備え、
前記サーバは、
前記所定の公開情報を保持するサーバ鍵保持部と、
前記所定の公開情報に基づいて、当該サーバに保管された全暗号ファイルの内、前記暗号検索キーワードを含む暗号ファイルの集合以外の暗号ファイルを使用して、ファイル検証情報を生成して前記ユーザ端末へ送出するファイル検証情報生成部と、
を備え、
前記ユーザ端末は、
前記索引検証部で承認された場合、前記所定の公開情報に基づいて、前記取得した暗号ファイルの集合と前記ファイル検証情報とを使用して、暗号ファイルの蓄積値を計算し、該計算した暗号ファイルの蓄積値と前記保持した全暗号ファイルの蓄積値とが等しければ、前記取得した暗号ファイルの集合を復号して前記所望のファイルの集合を得、そうでなければ拒否するファイル検証部を更に有する、
付記１１又は１２に記載の検索システム。

（付記１４） 前記ユーザ端末は、
前記所定の公開情報に基づいて、前記更新すべき暗号ファイル、更新前の暗号ファイル、そのファイル番号、および前記蓄積値保持部に保持された全暗号ファイルの蓄積値を使用して、新しい全暗号ファイルの蓄積値を計算し、該計算した新しい全暗号ファイルの蓄積値を前記蓄積値保持部に保持する蓄積値更新部を更に有する、
付記１３に記載の検索システム。

（付記１５） 前記所定の生成アルゴリズムが署名生成アルゴリズムから成り、
前記所定の検証アルゴリズムが署名検証アルゴリズムから成り、
前記索引検証情報生成部は、デジタル署名の秘密鍵を使って、前記署名生成アルゴリズムに従って、前記索引検証情報として前記生成用組に対するデジタル署名を生成し、
前記索引検証部は、デジタル署名の公開鍵を使って、前記署名検証アルゴリズムに従って、取得したデジタル署名が前記検証用組のデジタル署名であるか否かをチェックする、
付記１１乃至１４のいずれか１つに記載の検索システム。

（付記１６） 前記所定の生成アルゴリズムがＭＡＣ（Message Authentication Code）生成アルゴリズムから成り、
前記所定の検証アルゴリズムがＭＡＣ検証アルゴリズムから成り、
前記索引検証情報生成部は、ＭＡＣの秘密鍵を使って、前記ＭＡＣ生成アルゴリズムに従って、前記索引検証情報として前記生成用組に対する認証子を生成し、
前記索引検証部は、前記ＭＡＣの秘密鍵を使って、前記ＭＡＣ検証アルゴリズムに従って、取得した認証子が前記検証用組の認証子であるか否かをチェックする、
付記１１乃至１４のいずれか１つに記載の検索システム。

（付記１７） ユーザ端末がサーバに複数の暗号ファイルを保管し、前記ユーザ端末がキーワード検索によって前記サーバから所望のファイルの集合を取得すると共に、暗号ファイルの更新をも行う検索方法であって、
前記ユーザ端末が、暗号化の秘密鍵を使って複数のファイルをそれぞれ暗号化し、前記複数の暗号ファイルをそれらの暗号ファイルのファイル番号と共に前記サーバに保管するステップと、
前記ユーザ端末が、キーワードと該キーワードに対応するファイルのファイル番号との対応表である索引を、所定の秘密鍵を使って暗号化し、前記キーワードの暗号文と該キーワードを含むファイルのファイル番号の暗号文とから成る暗号化索引を前記サーバに保管するステップと、
前記ユーザ端末が、前記キーワードと該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成するステップと、
前記ユーザ端末が、前記生成した索引検証情報を前記サーバに保管するステップと、
前記ユーザ端末が、前記所定の秘密鍵を使って検索キーワードを暗号化して得られる暗号検索キーワードを前記サーバへ送って、前記サーバから前記暗号検索キーワードを含む暗号ファイルおよび当該暗号ファイルのファイル番号の集合と前記検索キーワードに対応する索引検証情報とを取得するステップと、
前記ユーザ端末が、前記取得した索引検証情報が、前記検索キーワードと前記取得した暗号ファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックするステップと、
前記ユーザ端末が、チェックの結果が正しければ承認し、そうでなければ拒否するステップと、
前記ユーザ端末が、更新すべきファイルを前記暗号化の秘密鍵を使って暗号化して得られる、更新すべき暗号ファイルをそのファイル番号と共に前記サーバに送って更新するステップと、
を含む検索方法。

（付記１８） 前記更新すべき暗号ファイルが削除を示すデータから成る、付記１７に記載の検索方法。

（付記１９） サーバに複数の暗号ファイルを保管し、キーワード検索によって前記サーバから所望のファイルの集合を取得すると共に、暗号ファイルの更新をも行う処理を、コンピュータであるユーザ端末に実行させる検索プログラムであって、前記コンピュータに、
暗号化の秘密鍵を使って複数のファイルをそれぞれ暗号化し、前記複数の暗号ファイルをそれらの暗号ファイルのファイル番号と共に前記サーバに保管する手順と、
キーワードと該キーワードに対応するファイルのファイル番号との対応表である索引を、所定の秘密鍵を使って暗号化し、前記キーワードの暗号文と該キーワードを含むファイルのファイル番号の暗号文とから成る暗号化索引を前記サーバに保管する手順と、
前記キーワードと該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成する手順と、
前記生成した索引検証情報を前記サーバに保管する手順と、
前記所定の秘密鍵を使って検索キーワードを暗号化して得られる暗号検索キーワードを前記サーバへ送って、前記サーバから前記暗号検索キーワードを含む暗号ファイルおよび該暗号ファイルのファイル番号の集合と前記検索キーワードに対応する索引検証情報とを取得する手順と、
前記取得した索引検証情報が、前記検索キーワードと前記取得した暗号ファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックする手順と、
チェックの結果が正しければ承認し、そうでなければ拒否する手順と、
更新すべきファイルを前記暗号化の秘密鍵を使って暗号化して得られる、更新すべき暗号ファイルをそのファイル番号と共に前記サーバに送って更新する手順と、
を実行させるための検索プログラム。

（付記２０） 前記更新すべき暗号ファイルが削除を示すデータから成る、付記１９に記載の検索プログラム。

本発明は、キーワード検索におけるサーバの不正を検出し、ファイルを更新（削除を含む）する方式に利用可能である。

１００、１００Ａ 検索システム
２００、２００Ａ クライアント（ユーザ端末）
２０２、２０２Ａ 鍵生成部
２０４、２０４Ａ 鍵保持部
２０６、２０６Ａ 索引検証情報生成部
２０８、２０８Ａ 索引検証部
２１０ 第１の信号線（ファイル保管手段）
２１０Ａ ファイル暗号化部（暗号ファイル保管手段）
２１２ 第２の信号線（索引保管手段）
２１２Ａ 索引暗号化部（暗号索引保管手段）
２１４ 第３の信号線（ファイル取得手段）
２１４Ａ キーワード暗号化部（暗号ファイル取得手段）
２１６、２１６Ａ ファイル蓄積値計算部
２１８、２１８Ａ Ａｃｃ保持部
２２０、２２０Ａ ファイル検証部
２２２、２２２Ａ 信号線
２２４、２２４Ａ 信号線
２２６、２２６Ａ Ａｃｃ更新部
３００、３００Ａ サーバ
３０２、３０２Ａ 記憶領域
３０４ 検索部
３０４Ａ 暗号検索部
３０６、３０６Ａ 鍵保持部
３０８、３０８Ａ ファイル検証情報生成部

Claims (10)

1. ユーザ端末がサーバに複数のファイルを保管し、前記ユーザ端末がキーワード検索によって前記サーバから所望のファイルの集合を取得すると共に、ファイルの更新をも行う検索システムであって、前記ユーザ端末は、
   前記複数のファイルをそれらのファイル番号と共に前記サーバに保管するファイル保管手段と、
   キーワードと該キーワードに対応するファイルのファイル番号との対応表である索引を、前記サーバに保管する索引保管手段と、
   前記キーワードと該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成し、該生成した索引検証情報を前記サーバに保管する索引検証情報生成部と、
   検索キーワードを前記サーバへ送って、前記サーバから前記検索キーワードを含むファイルおよび当該ファイルのファイル番号の集合と前記検索キーワードに対応する索引検証情報とを取得するファイル取得手段と、
   該取得した索引検証情報が、前記検索キーワードと前記取得したファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックし、チェックの結果が正しければ承認し、そうでなければ拒否する索引検証部と、
   更新すべきファイルをそのファイル番号と共に前記サーバへ送って更新する更新手段と、
   を有する検索システム。
2. 前記ユーザ端末は、
   秘密鍵と所定の公開情報とを保持するユーザ鍵保持部と、
   前記所定の公開情報と前記複数のファイルとから全ファイルの蓄積値を計算するファイル蓄積値計算部と、
   前記全ファイルの蓄積値を保持する蓄積値保持部と、
   を更に備え、
   前記サーバは、
   前記所定の公開情報を保持するサーバ鍵保持部と、
   前記所定の公開情報に基づいて、当該サーバに保管された全ファイルの内、前記検索キーワードを含むファイルの集合以外のファイルを使用して、ファイル検証情報を生成して前記ユーザ端末へ送出するファイル検証情報生成部と、
   を備え、
   前記ユーザ端末は、
   前記索引検証部で承認された場合、前記所定の公開情報に基づいて、前記取得したファイルの集合と前記ファイル検証情報とを使用して、ファイルの蓄積値を計算し、該計算したファイルの蓄積値と前記保持した全ファイルの蓄積値とが等しければ、前記取得したファイルの集合を前記所望のファイルの集合として得、そうでなければ拒否するファイル検証部を更に有する、
   請求項１に記載の検索システム。
3. 前記ユーザ端末は、
   前記所定の公開情報に基づいて、前記更新すべきファイル、更新前のファイル、そのファイル番号、および前記蓄積値保持部に保持された全ファイルの蓄積値を使用して、新しい全ファイルの蓄積値を計算し、該計算した新しい全ファイルの蓄積値を前記蓄積値保持部に保持する蓄積値更新部を更に有する、
   請求項２に記載の検索システム。
4. ユーザ端末がサーバに複数のファイルを保管し、前記ユーザ端末がキーワード検索によって前記サーバから所望のファイルの集合を取得すると共に、ファイルの更新をも行う検索方法であって、
   前記ユーザ端末が、前記複数のファイルをそれらのファイル番号と共に前記サーバに保管するステップと、
   前記ユーザ端末が、キーワードと該キーワードに対応するファイルのファイル番号との対応表である索引を、前記サーバに保管するステップと、
   前記ユーザ端末が、前記キーワードと該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成するステップと、
   前記ユーザ端末が、前記生成した索引検証情報を前記サーバに保管するステップと、
   前記ユーザ端末が、検索キーワードを前記サーバへ送って、前記サーバから前記検索キーワードを含むファイルおよび当該ファイルのファイル番号の集合と前記検索キーワードに対応する索引検証情報とを取得するステップと、
   前記ユーザ端末が、前記取得した索引検証情報が、前記検索キーワードと前記取得したファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックするステップと、
   前記ユーザ端末が、チェックの結果が正しければ承認し、そうでなければ拒否するステップと、
   前記ユーザ端末が、更新すべきファイルをそのファイル番号と共に前記サーバへ送って更新するステップと、
   を含む検索方法。
5. サーバに複数のファイルを保管し、キーワード検索によって前記サーバから所望のファイルの集合を取得すると共に、ファイルの更新をも行う処理を、コンピュータであるユーザ端末に実行させる検索プログラムであって、前記コンピュータに、
   前記複数のファイルをそれらのファイル番号と共に前記サーバに保管する手順と、
   キーワードと該キーワードに対応するファイルのファイル番号との対応表である索引を、前記サーバに保管する手順と、
   前記キーワードと該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成する手順と、
   前記生成した索引検証情報を前記サーバに保管する手順と、
   検索キーワードを前記サーバへ送って、前記サーバから前記検索キーワードを含むファイルおよび当該ファイルのファイル番号の集合と前記検索キーワードに対応する索引検証情報とを取得する手順と、
   前記取得した索引検証情報が、前記検索キーワードと前記取得したファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックする手順と、
   チェックの結果が正しければ承認し、そうでなければ拒否する手順と、
   更新すべきファイルをそのファイル番号と共に前記サーバへ送って更新する手順と、
   を実行させるための検索プログラム。
6. ユーザ端末がサーバに複数の暗号ファイルを保管し、前記ユーザ端末がキーワード検索によって前記サーバから所望のファイルの集合を取得すると共に、暗号ファイルの更新をも行う検索システムであって、前記ユーザ端末は、
   暗号化の秘密鍵を使って複数のファイルをそれぞれ暗号化し、前記複数の暗号ファイルをそれらの暗号ファイルのファイル番号と共に前記サーバに保管する暗号ファイル保管手段と、
   キーワードと該キーワードに対応するファイルのファイル番号との対応表である索引を、所定の秘密鍵を使って暗号化し、前記キーワードの暗号文と該キーワードを含むファイルのファイル番号の暗号文とから成る暗号化索引を前記サーバに保管する暗号化索引保管手段と、
   前記キーワードと該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成し、該生成した索引検証情報を前記サーバに保管する索引検証情報生成部と、
   前記所定の秘密鍵を使って検索キーワードを暗号化して得られる暗号検索キーワードを前記サーバへ送って、前記サーバから前記暗号検索キーワードを含む暗号ファイルおよび当該暗号ファイルのファイル番号の集合と前記検索キーワードに対応する索引検証情報とを取得する暗号ファイル取得手段と、
   該取得した索引検証情報が、前記検索キーワードと前記取得した暗号ファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックし、チェックの結果が正しければ承認し、そうでなければ拒否する索引検証部と、
   更新すべきファイルを前記暗号化の秘密鍵を使って暗号化して得られる、更新すべき暗号ファイルをそのファイル番号と共に前記サーバに送って更新する更新手段と、
   を有する検索システム。
7. 前記ユーザ端末は、
   前記暗号化の秘密鍵と前記所定の秘密鍵と所定の公開情報とを保持するユーザ鍵保持部と、
   前記所定の公開情報と前記複数の暗号ファイルとから全暗号ファイルの蓄積値を計算するファイル蓄積値計算部と、
   前記全暗号ファイルの蓄積値を保持する蓄積値保持部と、
   を更に備え、
   前記サーバは、
   前記所定の公開情報を保持するサーバ鍵保持部と、
   前記所定の公開情報に基づいて、当該サーバに保管された全暗号ファイルの内、前記暗号検索キーワードを含む暗号ファイルの集合以外の暗号ファイルを使用して、ファイル検証情報を生成して前記ユーザ端末へ送出するファイル検証情報生成部と、
   を備え、
   前記ユーザ端末は、
   前記索引検証部で承認された場合、前記所定の公開情報に基づいて、前記取得した暗号ファイルの集合と前記ファイル検証情報とを使用して、暗号ファイルの蓄積値を計算し、該計算した暗号ファイルの蓄積値と前記保持した全暗号ファイルの蓄積値とが等しければ、前記取得した暗号ファイルの集合を復号して前記所望のファイルの集合を得、そうでなければ拒否するファイル検証部を更に有する、
   請求項６に記載の検索システム。
8. 前記ユーザ端末は、
   前記所定の公開情報に基づいて、前記更新すべき暗号ファイル、更新前の暗号ファイル、そのファイル番号、および前記蓄積値保持部に保持された全暗号ファイルの蓄積値を使用して、新しい全暗号ファイルの蓄積値を計算し、該計算した新しい全暗号ファイルの蓄積値を前記蓄積値保持部に保持する蓄積値更新部を更に有する、
   請求項７に記載の検索システム。
9. ユーザ端末がサーバに複数の暗号ファイルを保管し、前記ユーザ端末がキーワード検索によって前記サーバから所望のファイルの集合を取得すると共に、暗号ファイルの更新をも行う検索方法であって、
   前記ユーザ端末が、暗号化の秘密鍵を使って複数のファイルをそれぞれ暗号化し、前記複数の暗号ファイルをそれらの暗号ファイルのファイル番号と共に前記サーバに保管するステップと、
   前記ユーザ端末が、キーワードと該キーワードに対応するファイルのファイル番号との対応表である索引を、所定の秘密鍵を使って暗号化し、前記キーワードの暗号文と該キーワードを含むファイルのファイル番号の暗号文とから成る暗号化索引を前記サーバに保管するステップと、
   前記ユーザ端末が、前記キーワードと該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成するステップと、
   前記ユーザ端末が、前記生成した索引検証情報を前記サーバに保管するステップと、
   前記ユーザ端末が、前記所定の秘密鍵を使って検索キーワードを暗号化して得られる暗号検索キーワードを前記サーバへ送って、前記サーバから前記暗号検索キーワードを含む暗号ファイルおよび当該暗号ファイルのファイル番号の集合と前記検索キーワードに対応する索引検証情報とを取得するステップと、
   前記ユーザ端末が、前記取得した索引検証情報が、前記検索キーワードと前記取得した暗号ファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックするステップと、
   前記ユーザ端末が、チェックの結果が正しければ承認し、そうでなければ拒否するステップと、
   前記ユーザ端末が、更新すべきファイルを前記暗号化の秘密鍵を使って暗号化して得られる、更新すべき暗号ファイルをそのファイル番号と共に前記サーバに送って更新するステップと、
   を含む検索方法。
10. サーバに複数の暗号ファイルを保管し、キーワード検索によって前記サーバから所望のファイルの集合を取得すると共に、暗号ファイルの更新をも行う処理を、コンピュータであるユーザ端末に実行させる検索プログラムであって、前記コンピュータに、
    暗号化の秘密鍵を使って複数のファイルをそれぞれ暗号化し、前記複数の暗号ファイルをそれらの暗号ファイルのファイル番号と共に前記サーバに保管する手順と、
    キーワードと該キーワードに対応するファイルのファイル番号との対応表である索引を、所定の秘密鍵を使って暗号化し、前記キーワードの暗号文と該キーワードを含むファイルのファイル番号の暗号文とから成る暗号化索引を前記サーバに保管する手順と、
    前記キーワードと該キーワードを含む全てのファイルのファイル番号の集合との生成用組に対して所定の生成アルゴリズムに従って索引検証情報を生成する手順と、
    前記生成した索引検証情報を前記サーバに保管する手順と、
    前記所定の秘密鍵を使って検索キーワードを暗号化して得られる暗号検索キーワードを前記サーバへ送って、前記サーバから前記暗号検索キーワードを含む暗号ファイルおよび該暗号ファイルのファイル番号の集合と前記検索キーワードに対応する索引検証情報とを取得する手順と、
    前記取得した索引検証情報が、前記検索キーワードと前記取得した暗号ファイルのファイル番号の集合との検証用組の索引検証情報であるか否かを所定の検証アルゴリズムによってチェックする手順と、
    チェックの結果が正しければ承認し、そうでなければ拒否する手順と、
    更新すべきファイルを前記暗号化の秘密鍵を使って暗号化して得られる、更新すべき暗号ファイルをそのファイル番号と共に前記サーバに送って更新する手順と、
    を実行させるための検索プログラム。

Images