"データを秘匿検索装置に送信する登録クライアントは、前記秘匿検索装置に送信するデータを暗号化して暗号化データを生成する暗号化手段、前記データから抽出したインデックスを秘匿化した秘匿化インデックスを生成する秘匿化インデックス生成手段、前記データから、データ間の類似度を計算するための特徴量を算出する特徴量算出手段、及び前記暗号化データ、前記秘匿化インデックス、及び前記特徴量の組を、前記秘匿検索装置に送信する登録手段を有する、ことを特徴とする登録クライアント。前記登録クライアントにおける前記秘匿化インデックス生成手段は、データから検索キーワードを抽出し、前記抽出したキーワードそれぞれについてハッシュ値を計算し、各ハッシュ値に対して乱数列を生成し、前記乱数列に対するメッセージダイジェストを求め、前記乱数列のビット長と前記メッセージダイジェストのビット長の和は前記ハッシュ値のビット長と等しくなるように、前記乱数列と前記メッセージダイジェストを連結したビット列と前記ハッシュ値との排他的論理和を、前記秘匿化インデックスとして出力する、ことを特徴とする請求項1記載の登録クライアント。前記登録クライアントにおいて、前記特徴量は、前記秘匿検索装置に送信するデータのデータ長で与えられ、2つのデータ間の類似度は、前記2つのデータにおけるそれぞれの特徴量s1,s2を含む、1/1|s1-s2|によって算出する、ことを特徴とする請求項1記載の登録クライアント。前記登録クライアントにおいて、前記特徴量は、前記秘匿検索装置に送信するデータから単語を抽出し、抽出した単語それぞれについてハッシュ値を計算し、前記ハッシュ値の論理和をビット列とみなすことで与えられ、2つのデータ間の類似度は、前記2つのデータの特徴量において、ともに1になるビットの個数によって算出される、ことを特徴とする請求項1記載の登録クライアント。前記登録クライアントにおいて、前記特徴量は、前記秘匿検索装置に送信するデータを、あらかじめ定めた特定のビットパターンが境界となるように分割し、前記分割したデータそれぞれについてハッシュ値を計算し、前記ハッシュ値を構成要素とする集合として与えられ、2つのデータ間の類似度は、前記2つのデータにおける特徴量の積集合に含まれる要素数と、前記特徴量の和集合に含まれる要素数の比によって算出される、ことを特徴とする請求項1記載の登録クライアント。秘匿検索装置に対して検索を行う検索クライアントは、前記秘匿検索装置に登録されたデータの検索を行うための検索クエリに含まれる検索キーワードを秘匿化したトラップドアを生成するトラップドア生成手段、を有することを特徴とする検索クライアント。前記検索クライアントにおいて、前記トラップドアは、前記データから抽出した検索キーワードから秘匿化インデックスを生成する際に、前記検索キーワードのハッシュ値を求めたハッシュ関数を用いて、検索クエリに対するハッシュ値を算出する、ことを請求項6記載の検索クライアント。データを登録クライアントから受信し、検索用の情報を検索クライアントから受信する秘匿検索装置は、前記登録クライアントから、前記データを暗号化した暗号化データと、前記データから抽出したインデックスを秘匿化した秘匿化インデックスと、データ間の類似度を計算するための特徴量との組を受信する受信手段と、前記登録クライアントから受信した前記特徴量をもとに、2つのデータの類似度を算出する類似度算出手段と、前記類似度算出手段が算出した類似度に基づいて、前記登録クライアントから受信した前記暗号化データをクラスタリングするクラスタリング手段と、前記秘匿検索装置に登録されたデータの検索を行うための検索クエリに含まれる検索キーワードを秘匿化したトラップドアを前記検索クライアントから受け取り、前記クラスタリング手段が生成したクラスタリングの結果をもとに、前記クラスタリングされた暗号化データと前記トラップドアとの照合処理の優先順位を算出する優先順位算出手段と、前記登録クライアントから受信した前記秘匿化インデックスと前記トラップドアとの照合処理を行う照合手段と、前記検索クライアントから前記トラップドアを受信したとき、前記優先順位算出手段が算出した優先順位に基づいて、あらかじめ定めた回数だけ、前記優先順位が高いクラスタの順に、前記照合手段によって、前記暗号化データと前記トラップドアとの照合を行ない、前記トラップドアにヒットした前記暗号化データを前記検索クライアントに返信する検索手段とを、有することを特徴とする秘匿検索装置。前記秘匿検索装置において、前記クラスタリング手段は、クラスタを1以上生成し、各クラスタについて中心をランダムに設定し、前記登録クライアントから受信した全てのデータについて、各データに含まれる特徴量に基づいて、前記類似度算出手段に、当該中心との類似度を計算させて、各データを最も類似する中心が属するクラスタに割り振り、前記登録クライアントから受信した全てのデータについて、クラスタへの割り振りが変化しなかった場合は処理を終了し、それ以外の場合は各クラスタの中心を、当該クラスタに属するデータの特徴量を用いて計算し直してから、当該中心を求める処理を繰り返すことを特徴とする請求項8記載の秘匿検索装置。前記秘匿検索装置において、前記クラスタリング手段は、前記登録クライアントから受信したデータを1つだけを含むクラスタを、前記データの総数分生成し、前記類似度算出手段に、各クラスタに属するデータの特徴量を用いてクラスタ間の距離を計算させ、最も距離の近い2つのクラスタを逐次的に併合し、前記併合を、全ての対象が1つのクラスタに併合されるまで繰り返す、ことを特徴とする請求項8記載の秘匿検索装置。前記秘匿検索装置において、前記優先順位算出手段は、各クラスタについて、前記クラスタに属する全てのデータのうち1つを代表データとして選択し、各クラスタについて、前記クラスタの代表データの秘匿化インデックスと前記トラップドアを前記照合手段に照合させて、前記トラップドアとの合致率が大きいほど優先度が高くなるように当該クラスタの優先度を算出し、前記優先度が高い順になるようにクラスタに含まれるデータの照合順序をソートする、ことを特徴とする請求項8記載の秘匿検索装置。前記秘匿検索装置において、前記照合手段は、前記秘匿化インデックスと前記トラップドアの排他的論理和を取り、前記秘匿化インデックス生成の際に生成した乱数列と同じ長さのビット列を前記排他的論理和の先頭から取って、前記ビット列のメッセージダイジェストを計算し、前記メッセージダイジェストが、前記排他的論理和の前記メッセージダイジェストを計算していないビット列と一致した場合、前記秘匿化インデックスは前記トラップドアに対応する検索クエリを含んでいると判断し、一致しない場合、前記秘匿化インデックスは前記トラップドアに対応する前記検索クエリを含んでいないと判断する、ことを特徴とする請求項8記載の秘匿検索装置。前記秘匿検索装置において、前記検索手段が行う照合処理の回数は、前記検索クライアントが設定する、ことを特徴とする請求項8記載の秘匿検索装置。前記秘匿検索装置において、前記検索手段が行う照合処理の回数は、前記秘匿検索装置が設定する、ことを特徴とする請求項8記載の秘匿検索装置。少なくとも1つの登録クライアント、秘匿検索装置、及び少なくとも1つの検索クライアントを互いにネットワークを介して接続した計算機システムであって、データを前記秘匿検索装置に送信する前記登録クライアントは、前記秘匿検索装置に送信するデータを暗号化して暗号化データを生成する暗号化手段、前記データから抽出したインデックスを秘匿化した秘匿化インデックスを生成する秘匿化インデックス生成手段、前記データから、データ間の類似度を計算するための特徴量を算出する特徴量算出手段、及び前記暗号化データ、前記秘匿化インデックス、及び前記特徴量の組を、前記秘匿検索装置に送信する登録手段を有し、前記秘匿検索装置に対して検索を行う前記検索クライアントは、前記秘匿検索装置に登録されたデータの検索を行うための検索クエリに含まれる検索キーワードを秘匿化したトラップドアを生成するトラップドア生成手段を有し、データを前記登録クライアントから受信し、検索用の情報を前記検索クライアントから受信する前記秘匿検索装置は、前記登録クライアントから、前記暗号化データと、前記秘匿化インデックスと、前記特徴量との組を受信する受信手段、前記登録クライアントから受信した前記特徴量をもとに、2つのデータの類似度を算出する類似度算出手段、前記類似度算出手段が算出した類似度に基づいて、前記登録クライアントから受信した前記暗号化データをクラスタリングするクラスタリング手段、前記トラップドアを前記検索クライアントから受け取り、前記クラスタリングの結果をもとに、前記クラスタリングされた暗号化データと前記トラップドアとの照合処理の優先順位を算出する優先順位算出手段、前記登録クライアントから受信した前記秘匿化インデックスと前記トラップドアとの照合処理を行う照合手段、及び前記検索クライアントから前記トラップドアを受信したとき、前記優先順位に基づいて、あらかじめ定めた回数だけ、前記優先順位が高いクラスタの順に、前記照合手段によって、前記暗号化データと前記トラップドアとの照合を行ない、前記トラップドアにヒットした前記暗号化データを前記検索クライアントに返信する検索手段とを有する、ことを特徴とする計算機システム。ネットワークを介して、秘匿検索装置に登録するデータを送信する登録クライアントと前記秘匿検索装置に対して検索を行う検索クライアントとに接続された秘匿検索装置における秘匿検索方法は、前記登録クライアントから、前記データを暗号化した暗号化データと、前記データから抽出したインデックスを秘匿化した秘匿化インデックスと、データ間の類似度を計算するための特徴量との組を受信し、前記登録クライアントから受信した前記特徴量をもとに、2つのデータの類似度を算出し、前記算出した類似度に基づいて、前記登録クライアントから受信した前記暗号化データをクラスタリングし、前記秘匿検索装置に登録されたデータの検索を行うための検索クエリに含まれる検索キーワードを秘匿化したトラップドアを前記検索クライアントから受け取り、前記生成したクラスタリングの結果をもとに、前記クラスタリングされた暗号化データと前記トラップドアとの照合処理の優先順位を算出し、前記検索クライアントから前記トラップドアを受信したとき、前記算出した優先順位に基づいて、あらかじめ定めた回数だけ、前記登録クライアントから受信した前記暗号化インデックスと前記トラップドアとを照合し、前記トラップドアにヒットした前記暗号化データを前記検索クライアントに返信する、ことを特徴とする秘匿検索方法。一般に、文字列検索においては、単語とその単語を含む文書の索引転置インデックスを備えることで、検索応答時間の短縮を図っている。このような索引がない場合、毎回検索クエリと預託データを総当りで照合する必要があり、検索応答が大幅に遅延することとなる。非特許文献1~非特許文献4や特許文献1記載の技術では、頻度分析などの攻撃に耐性を持たせるために、秘匿化インデックスがどの単語を含んでいるかを判定することが困難な仕組みとなっている。つまり、転置インデックスなどの索引を構成することが事実上不可能である。よってこれらの従来技術では、検索クエリと秘匿化インデックスを毎回総当りで照合する必要があり、検索応答が大幅に遅延してしまう。本発明の目的は、検索可能暗号を用いた秘匿検索システムにおいては、検索の高速化を達成することにある。上記の目的を達成するために本発明は、暗号化データや秘匿化インデックスだけではなく、預託データの特徴量もデータベースサーバに登録する手段を提供する。ここで特徴量とは、預託データの特徴をできるだけ損なわないようにデータ長を大幅に削減したもので、特徴量だけを用いて預託データの類似度を計算することができるが、特徴量から元のデータを推測することが困難なものとして定義される。特徴量として、例えば預託データ内の単語などから計算される特徴ベクトルや、預託データを分割してハッシュ値を求めて連結したファジィハッシュとよばれる量などが知られている。次に本発明は、暗号化データや秘匿化インデックスともに受信した特徴量を用いて、データベースサーバ側で特徴量に対応する預託データの類似度を計算し、類似した預託データが同じクラスタに含まれるように秘匿化インデックスなどをクラスタリングしておく手段を提供する。さらに本発明は、秘匿検索処理において、まず各クラスタにおいて秘匿化インデックスの代表以下ピボットと呼ぶを選択して、ピボットとトラップドア検索クエリに含まれる検索キーワードを秘匿化したものの照合を行い、ピボットがトラップドアにヒットした場合、当該ピボットが属するクラスタに含まれる全登録データについてトラップドアとの照合の優先順位を上げ、ピボットがトラップドアにヒットしなかった場合、当該ピボットが属するクラスタに含まれる全登録データについて照合の優先順位を下げる手段を提供する。照合対象の優先順位を定めた後全登録データについて照合を順次行い、一定回数で照合を打ち切ることで、安全性や検索精度の低下を抑えつつ秘匿検索処理の高速化を実現する。データベースサーバに預託された暗号化データを復号せずに検索する秘匿検索システムにおいて、元のデータを推測しにくい特徴量を用いて秘匿化インデックスをクラスタリングしておくことで、安全性や検索精度の低下を抑えつつ、秘匿検索を高速化することができる。以下、本発明の実施の形態を図面に基づいて詳細に説明する。システム構成図1は、本発明の実施の形態である秘匿検索処理システムの概略図である。図示するように検索処理システムは、n個の登録クライアント20-1~20-n、m個の検索クライアント30-1~30-mおよびデータベースサーバ40を備え、これらがネットワーク10を介して相互に情報を送受信できるよう設計されている。ここでn及びmは1以上の整数をとり、nとmは異なっていてもよい。登録クライアント20-1~20-nはすべて同じ構成をとる。以下、任意の一つを登録クライアント20と呼ぶ。同様に、検索クライアント30-1~30-mはすべて同じ構成をとる。以下、任意の一つを検索クライアント30と呼ぶ。本実施形態における登録クライアント20は、暗号化した預託データなどをデータベースサーバ40に送信するデータ登録用の送受信装置として機能する。検索クライアント30は、秘匿化した検索クエリをデータベースサーバ40に送信して検索結果を受信する、検索用の送受信装置として機能する。データベースサーバ40は、暗号化した預託データなどをデータベースに登録し、かつデータベース内のデータを検索する秘匿検索装置として機能する。登録クライアント図2は登録クライアント20の概略構成を例示する図である。図示するように登録クライアント20は、CPU212、メモリ214、記憶装置216、鍵生成部218、登録部220、ユーザインターフェース230および通信インターフェース232を備え、これらが内部バス200を介して相互に情報を送受信できるように設計されている。登録部220は、暗号化部222、秘匿化インデックス生成部224、特徴量算出部226および設定部228を備える。これらの装置はハブ200を介して、単体でCPU212などと相互に情報を送受信することができる。まず汎用的な構成要素について説明する。CPU212は、様々な数値計算や情報処理、機器制御などを行う中央処理装置である。メモリ214は、CPU212が直接読み書きできるRAMやROMなどの半導体記憶装置である。記憶装置216は、コンピュータ内でデータやプログラムを記憶するハードディスクや磁気テープ、フラッシュメモリなどといった装置である。当該装置はデータベースサーバ40に預託するデータなどを格納する。鍵生成部218は、データを暗号化もしくは復号化するための鍵などを生成し、さらに検索クライアント30と復号鍵を共有するための処理を行う装置である。復号鍵の共有については後で図7を用いて説明する。ユーザインターフェース230は、ユーザに処理結果を出力し、かつユーザの指示を受け付けて登録クライアント20の各構成要素に反映させる、ディスプレイやマウス、キーボードなどといった装置である。通信インターフェース232は、登録クライアント20の各構成要素と検索クライアント30やデータベースサーバ40などの外部装置とのデータの送受信を制御するための装置である。本発明特有の構成要素は、登録部220およびこれを構成する暗号化部222、秘匿化インデックス生成部224、特徴量算出部226、設定部228である。これらのうち、従来の検索可能暗号技術にはない最も特徴的な構成要素は、特徴量算出部226である。まず登録部220の構成要素から説明する。暗号化部222は、データベースサーバ40に預託するデータを記憶装置216から読み出して、鍵生成部218で生成した暗号鍵を用いて暗号化し、暗号化したデータを登録部220に通知し、またはメモリ214もしくは記憶装置216に一時的に出力する装置である。秘匿化インデックス生成部204は、データベースサーバ40に預託するデータを記憶装置216から読み出し、検索可能暗号特有のアルゴリズムで預託データの内容から秘匿化インデックスを生成し、生成した秘匿化インデックスを登録部220に通知し、またはメモリ214もしくは記憶装置216に一時的に出力する装置である。秘匿化インデックスの具体的な生成手順については、後で図5を用いて説明する。特徴量算出部206は、データベースサーバ40に預託するデータを記憶装置216から読み出し、所定のアルゴリズムで預託データの特徴量を算出し、算出した特徴量を登録部220に通知し、またはメモリ214もしくは記憶装置216に一時的に出力する装置である。特徴量の具体的な算出手順については後で図5を用いて説明する。設定部228は、暗号化、秘匿化インデックス生成、特徴量算出などの処理に必要なパラメータを設定するための装置である。当該パラメータはユーザインターフェース230を介してユーザによって設定され、登録部220、暗号化部222、秘匿化インデックス生成部224、特徴量算出部226に反映される。そして登録部220は、ユーザインターフェース230を介してデータベースサーバ40への登録指示をユーザから受け取り、指示された記憶装置216の格納データに対して、暗号化部222、秘匿化インデックス生成部224および特徴量算出部226を制御して、暗号化データ、秘匿化インデックスおよび特徴量の組に含まれるそれぞれを計算して、計算したそれぞれを含む組を、通信インターフェース232を介してデータベースサーバ40に送信する装置である。データ登録処理の詳細については後で図5を用いて説明する。なお、鍵生成部218、登録部220およびこれを構成する暗号化部222、秘匿化インデックス生成部224、特徴量算出部226、設定部228については、それぞれの装置が単体で処理を実行してもよいし、それぞれの装置はプログラムのみを具備し、CPU212が当該プログラムをメモリ214に読み込んで実行してもよい。検索クライアント図3は検索クライアント30の概略構成を例示する図である。図示するように検索クライアント30は、CPU312、メモリ314、記憶装置316、検索部320、ユーザインターフェース330および通信インターフェース332を備え、これらが内部バス300を介して相互に情報を送受信できるように設計されている。また、検索部320は、トラップドア生成部322、鍵共有部324、復号化部326および設定部328を備える。これらの装置は内部バス300を介して、単体でCPU312などと相互に情報を送受信することができる。トラップドアとは、検索用の情報であって、検索クエリに含まれる検索キーワードを秘匿化したものである。汎用的な構成要素であるCPU312、メモリ314、記憶装置316、ユーザインターフェース330および通信インターフェース332は、図2の説明と同様の機能を有する。本発明特有の構成要素は、検索部320およびこれを構成するトラップドア生成部322、鍵共有部324、復号化部326、設定部328となる。以下、CPU312など汎用的な構成要素の説明については割愛し、検索部320の構成要素から説明する。トラップドア生成部322は、検索クエリを、ユーザインターフェース330を介してユーザから受け取り、検索可能暗号特有のアルゴリズムで検索クエリに含まれるキーワードを秘匿化することによってトラップドアを生成し、生成したトラップドアを検索部320に通知し、またはメモリ314もしくは記憶装置316に出力する装置である。トラップドアの具体的な生成手順については、後で図7を用いて説明する。鍵共有部324は、データベースサーバ40から検索クエリにヒットした暗号化データを受信した際、当該暗号化データの復号鍵を登録クライアント20と共有するための装置である。共有した復号鍵は、検索部320内に、またはメモリ314もしくは記憶装置316に一時的に保存される。具体的な鍵共有処理については、後で図7を用いて説明する。復号化部326は、鍵共有部324が取得した復号鍵を用いてデータベースサーバ40から受信した暗号化データを復号して検索部320に通知し、またはメモリ314もしくは記憶装置316に一時的に出力する装置である。設定部328は、トラップドア生成、鍵共有、復号化などの処理に必要なパラメータを設定するための装置である。当該パラメータはユーザインターフェース330を介してユーザによって設定され、検索部320、トラップドア生成部322、鍵共有部324、復号化部326に反映される。パラメータ設定の一例について、後で図11を用いて説明する。そして検索部320は、ユーザインターフェース330を介してユーザから検索クエリを受けとり、トラップドア生成部322を制御して検索クエリからトラップドアを生成し、生成したトラップドアをデータベースサーバ40に送信し、データベースサーバ40から返信された暗号化データを鍵共有部324および復号化部326を制御して復号してメモリ314もしくは記憶装置316に出力し、またはユーザインターフェース330を介してユーザに提示する装置である。処理の詳細については後で図7を用いて説明する。なお、検索部320およびこれを構成するトラップドア生成部322、鍵共有部324、復号化部326、設定部328については、それぞれの装置が単体で処理を実行してもよいし、それぞれの装置はプログラムのみを具備し、CPU312が当該プログラムをメモリ314に読み込んで実行してもよい。データベースサーバ図4はデータベースサーバ40の概略構成を例示する図である。図示するようにデータベースサーバ40は、CPU412、メモリ414、記憶装置416、認証部418、登録部420、クラスタリング部430、検索部440、設定部450、ユーザインターフェース460および通信インターフェース462を備え、これらが内部バス400を介して相互に情報を送受信できるように設計されている。また、クラスタリング部430は類似度算出部432を備える。類似度算出部432は内部バス400を介して単体でCPU412などと相互に情報を送受信することができる。また、検索部440は優先順位算出部442および照合部444を備える。これらの装置も内部バス400を介して単体でCPU412などと相互に情報を送受信することができる。汎用的な構成要素であるCPU412、メモリ414、記憶装置416、ユーザインターフェース460および通信インターフェース462は、図2の説明と同様の機能を有するので説明を割愛する。認証部418は、データベースサーバ40へのデータ登録や検索を許可するユーザのIDやパスワードを管理する装置である。詳細については後で図5を用いて説明する。本発明特有の構成要素は、登録部420、クラスタリング部430、これを構成する類似度算出部432、検索部440およびこれを構成する優先順位算出部442、照合部444、ならびに設定部450である。登録部420は、登録クライアント20から暗号化データ、秘匿化インデックスおよび特徴量の組を受信したとき、この組を記憶装置416に登録する装置である。以下、この組のことを登録データと呼ぶ。具体的な登録内容については後で図6を用いて説明する。クラスタリング部430は、記憶装置416に登録されている登録データをクラスタリングし、クラスタリング結果をメモリ414もしくは記憶装置416に一時的に出力する装置である。クラスタリングを行うには登録データ間の類似度を計算する必要があるが、この計算は類似度算出部432が登録データ中の特徴量を用いてクラスタリングを行う。具体的なクラスタリング処理については後で図5を用いて説明する。また、クラスタリング結果の具体例を図6であげる。類似度算出部432は、クラスタリング部430からの要求に応じて2つの登録データの類似度を算出する装置である。類似度を算出する登録データは、クラスタリング部430が一時的にメモリ414もしくは記憶装置416に格納するか、類似度算出部432に直接通知する。算出した類似度は、メモリ414もしくは記憶装置416に一時的に出力されるか、クラスタリング部430に直接返される。具体的な類似度の計算手順については後で図5を用いて説明する。検索部440は、検索クライアント30から検索クエリのトラップドアを受信し、検索クエリにヒットした暗号化データを、通信インターフェース442を介して検索クライアント30に返信する装置である。トラップドアを受信したとき検索部440は、まず優先順位算出部442を起動する。優先順位算出部442は、クラスタリング部430の処理によるクラスタリング結果をもとに照合処理の優先順位を算出する装置である。各クラスタの秘匿インデックスを代表する秘匿インデックスであるピボットとトラップドアとを比較して、各クラスタの照合処理の優先順位を決める。算出した優先順位はメモリ414もしくは記憶装置416に一時的に出力されるか、検索部430に直接返される。具体的な優先順位算出手順については後で図8を用いて説明する。各クラスタのピボットは、クラスタリング部430又は優先順位算出部442で設定/決定される。次に検索部440は照合部444を呼び出し、メモリ414もしくは記憶装置416に、または検索部430に格納されている優先順位に基づいて、優先度が高い順にトラップドアと秘匿化インデックスとの照合を行う。照合すべきトラップドアおよび秘匿化インデックスは、検索部440が一時的にメモリ414もしくは記憶装置416に格納するか、直接照合部444に渡す。照合部444は検索可能暗号特有のアルゴリズムによりトラップドアと秘匿化インデックスとの照合を行い、照合の結果をメモリ414もしくは記憶装置416に一時的に出力するか、検索部440に直接返す。具体的な照合手順については後で図9を用いて説明する。従来技術では全登録データについて総当りでトラップドアと照合する必要があったが、優先順位算出部442が特徴量を用いて登録データの照合処理の優先順位を設定し、検索部440が優先度の高い順でトラップドアと秘匿化インデックスとの照合を行い、一定回数で照合を打ち切ることで、検索応答時間の大幅な短縮を実現する。さらに、特徴量からは元の預託データの中身を推測することが困難なので、安全性の低下を抑えることができる。具体的な検索手順については、後で図7ないし図10を用いて説明する。設定部450はクラスタリングや検索などの処理に必要なパラメータを設定するための装置である。当該パラメータはユーザインターフェース460を介してデータベースサーバ管理者によって設定され、登録部420、クラスタリング部430、類似度算出部432、検索部440、優先順位算出部442および照合部444に反映される。なお、認証部418、登録部420、クラスタリング部430、類似度算出部432、検索部440、優先順位算出部442、照合部444および設定部450については、それぞれの装置が単体で処理を実行してもよいし、それぞれの装置はプログラムのみを具備し、CPU412が当該プログラムをメモリ414に読み込んで実行してもよい。処理概要まず始めに、図12を用いて、本発明の秘匿検索方法の処理概要を説明する。1登録クライアントは、預託データを暗号化した暗号化データや、預託データから抽出したインデックスを秘匿化した秘匿化インデックスだけではなく、預託データの特徴量もデータベースサーバに登録する1201。ここで特徴量とは、預託データの特徴をできるだけ損なわないようにデータ長を大幅に削減したもので、例えば預託データ内の単語などから計算される特徴ベクトルや、預託データを分割してハッシュ値を求めて連結したファジィハッシュとよばれる量などがある。2データベースサーバは、受信した特徴量を用いて、特徴量に対応する預託データの類似度を計算し、類似した預託データが同じクラスタに含まれるように秘匿化インデックスなどをクラスタリングする1202。3データベースサーバは、秘匿検索処理において、まず、各クラスタにおいて秘匿化インデックスの代表ピボットを選択し、このピボットと、検索クライアントで検索クエリに含まれる検索キーワードを秘匿化したトラップドアとの照合を行なうことにより、登録データ照合時のクラスタの優先順位を決定する1203。4データベースサーバは、優先順位に基づいて、クラスタ単位に全登録データの照合を行い1204、検索結果を検索クライアントに出力する。なお、優先順位決定の際に、ピボットがトラップドアにヒットした場合、当該ピボットが属するクラスタに含まれる全登録データについてトラップドアとの照合の優先順位を上げ、ピボットがトラップドアにヒットしなかった場合、当該ピボットが属するクラスタに含まれる全登録データについて照合の優先順位を下げる。さらに、秘匿検索処理を高速化するために、照合対象の優先順位を定めた後全登録データについて照合を順次行なう際に、一定回数で照合処理を打ち切る。データ登録処理図5は、登録クライアント20とデータベースサーバ40のデータ登録処理を例示するシーケンス図である。図5に基づいて当該データ登録処理を説明するとともに、図2の説明で述べた秘匿化インデックス生成手順、特徴量算出手順や、図4の説明で述べたクラスタリング処理、類似度算出手順についても、具体的な処理内容を例示する。登録クライアント20によるデータベースサーバ40へのデータ登録は、大別すると、登録クライアント20が登録データを生成するデータ生成処理S50と、登録クライアント20とデータベースサーバ40との間でデータの授受を行うデータ送受信処理S52と、データベースサーバ40が登録データをクラスタリングするクラスタリング処理S54からなる。データ生成処理S50は以下の手順で進行する。S500登録クライアント20のユーザは、ユーザインターフェース230を介してデータベースサーバ40に登録するデータを指定する。当該指定を受けて登録部220は、まず鍵生成部218を起動する。鍵生成部218は暗号鍵と復号鍵のペアを生成し、メモリ214または記憶装置216に格納する。暗号化部222は登録指示を受けたデータ預託データに対して、鍵生成部218が生成した暗号鍵を用いて暗号化処理を施す。なお、生成した復号鍵は後で検索クライアント30からの要求により外部に送信される可能性があるため、記憶装置216または鍵生成部218自体が保持しておく。S502秘匿化インデックス生成部224は預託データの内容から秘匿化インデックスを生成する。非特許文献1に基づいて具体的な生成方法を例示すると以下のようになる。秘匿化インデックス生成の処理手順を図13に示す。S502-1預託データから照合対象となる単語w1,w2,...を抽出する。単語の抽出は、英語であれば空白で区切られた文字列を抽出することでなされる。日本語の場合は、預託データ内の文章を一定の長さの文字列に分解する方法N-gramや、形態素解析により単語の抽出を行うことができる。S502-2抽出した単語w1,w2,...それぞれについてハッシュ値h1,h2,...を計算する。各ハッシュ値のビット長をnとする。S502-3各ハッシュ値hiに対してcビットの乱数列riを生成するi=1,2,...。各乱数列riについて所定の演算を行ってn-cビットのメッセージダイジェストdiを求める。ダイジェスト算出のための所定の演算は、例えば、上記のような単語からハッシュ値を計算する場合とは異なる別のハッシュ関数である。S502-4乱数列riの末尾にメッセージダイジェストdiを連結して、長さnのビット列siを得るi=1,2,...。各ハッシュ値hiとビット列siとの排他的論理和が秘匿化インデックスHiとなる。ここで、図13を参照しながら、上記のステップS502-1~4によって得られる秘匿化インデックスHiの表現について説明する。排他的論理和をXOR、2つのビット列の結合を|とすると、秘匿化インデックスHiは、hi単語wiのハッシュ値とri|di乱数列riとメッセージダイジェストdiからなるビット列siを用いて、Hi=hiXORri|diと表される。但し、単語Wiのハッシュ値hi、乱数列ri、メッセージダイジェストdiは、それぞれ、ハッシュ関数hWi=hi、乱数生成Rhi=ri、所定演算fri=diによって生成される。単語そのものではなくハッシュ値を用いたり、乱数列との排他的論理和を取ったりしているため、秘匿化インデックスから預託データ内の単語を求めることは困難となる。詳細については非特許文献1参照のこと。こうして求めた秘匿化インデックスとトラップドアとの照合方法については、後の図8の説明で明らかにする。S504特徴量算出部226は預託データの内容から特徴量を算出する。特徴量として、例えば預託データの大きさなど、恣意的に変更することが難しく、かつ連続的な値を取るような属性情報を用いる方法がまずあげられる。預託データの大きさを特徴量とした場合、2つの預託データ間の類似度は、預託データの大きさをs1、s2とすると、1/1|s1-s2|で近似することができる。この類似度は0から1までの値をとり、預託データが類似するほど1に近づく。より洗練された特徴量として、預託データ内の単語からベクトル特徴ベクトルを生成する方法が知られている。特徴ベクトルは以下の手順で求められる。特徴ベクトル生成の処理手順を図15に示す。S504-1預託データから照合対象となる単語w1,w2,...を抽出する。S504-2抽出した単語列w1,w2,...それぞれについてハッシュ値h1,h2,...を計算する。各ハッシュ値のビット長をnとする。S504-3h1、h2、...の各ビットの論理和をとる。これをn次元のベクトルとみなして特徴ベクトルと呼ぶ。こうして算出した特徴ベクトルを用いれば、2つの預託データ間の類似度を特徴ベクトル内のともに1になるビットの個数で近似することができる。即ち、2つの預託データに対応するハッシュ値のそれぞれのビットに対して論理積ANDを求めた結果に含まれるビット1の個数が類似度となる。特徴ベクトルの詳細については非特許文献5を参照のこと。また、単語の抽出などを行なわずに、計算可能な特徴量としてファジィハッシュとよばれる量を用いて類似度を求めることができる。ファジィハッシュは以下の手順で算出される。S504-a預託データを分割する。固定長で分割するほか、特定のビット列が境界となるように分割する方法が知られている。S504-b各分割データd1,d2,...のハッシュ値h1,h2,...を計算する。S504-cハッシュ値の配列h1,h2,...をファジィハッシュとして出力する。当該預託データに対応するファジィハッシュH=h1,h2,...、他の預託データに対応するファジィハッシュF=f1,f2,...を用いると、2つの預託データ間の類似度を、h1,h2,...とf1,f2,...との積集合の要素数HとFの双方に含まれているハッシュ値の数nと、h1,h2,...とf1,f2,...の和集合の要素数HとFの双方における要素の数の和Nからnを引いた数との比n/N-nで近似することができる。なお、H及びFの要素の数をm1及びm2とすると、N=m1m2、0=<n=<minm1、m2<Nである。これまでさまざまなファジィハッシュ技術が提案されている。詳細については非特許文献6を参照のこと。次にデータ送受信処理S52は、以下の手順で進行する。S520登録クライアント20とデータベースサーバ40との間でデータ授受のための通信路を確立する。具体的には、まず認証部418が、通信インターフェース232,462やユーザインターフェース230を介して登録クライアント20のユーザのID、及びパスワードなどでユーザの認証を行う。あらかじめ登録された正規のユーザと判断した場合、認証部418は登録クライアント20の登録部220とデータベースサーバ40の登録部420との間で通信路を確立する。この際、認証部418は登録クライアント20のIPアドレスなどの識別情報も収集して、記憶装置416に格納する。この識別情報は検索クライアント30と登録クライアント20との間で鍵共有をする場合に必要になる。詳細については後で図6及び図7を用いて説明する。なお、正規のユーザでないと判断した場合は、通信路を確立せず処理を終了する。S522登録部220は通信インターフェース232を介して、登録データ暗号化データ、秘匿化インデックス、及び特徴量の組をデータベースサーバ40に送信する。S524登録部420は通信インターフェース462を介して送信された登録データを受信し、記憶装置416に格納する。具体的な登録内容については後で図6を用いて説明する。S526登録部420は通信インターフェース462を介して登録完了の旨を登録クライアント20の登録部220に通知する。S528認証部418は、登録クライアント20の登録部220とデータベースサーバ40の登録部420との間で確立した通信路を開放する。以上の手順により、登録クライアント20のユーザは、データベースサーバ40の管理者や通信路上の第三者に内容を事実上知られることなくデータベースサーバ40に自己のデータを預託できる。データの登録後データベースサーバ40は登録データのクラスタリング処理S54を行う。代表的なクラスタリング手法として、K平均法と階層的クラスタリングが知られている。まず、K平均法は以下の手順で行われる。特徴量の個数をNとする。S54-1K個のクラスタの中心をランダムに設定する。あるいは、各クラスタに含まれる複数の秘匿化インデックスを所定の順に並べた時に、順序の中心の位置するものを当該クラスタの中心に設定する。S54-2各特徴量xii=1,2,...,NについてK個の中心との類似度を計算して、最も類似する中心を求める。xiを当該中心が属するクラスタに割り振る。S54-3全ての特徴量についてクラスタへの割り振りが変化しなかった場合は処理を終了する。それ以外の場合は割り振った特徴量から各クラスタの中心を計算し直してから、ステップS54-2に戻る。結果は最初のクラスタのランダムな設定に依存するが、計算量はnKのオーダなので比較的高速に動作するというメリットがある。詳細については非特許文献7を参照のこと。なおK平均法では、同じクラスタに属している特徴量からクラスタの中心を求める必要がある。特徴量として預託データの大きさを用いた場合、あるクラスタには、そのクラスタに含まれるm個の預託データそれぞれの大きさである特徴量xkk=1,...,mが属しているとすると、その中心vはx1...xm/mで与えられる。特徴量として特徴ベクトルを用いた場合、中心ベクトルvのi番目の要素をvi、m個の預託データからなるクラスタに含まれる預託データkの、n個の特徴量からなる特徴ベクトルxkのi番目の要素をxkii=1,,nとかくと、xkiのkk=1,...,m個の預託データについての標準偏差uiと平均値<xi>との比ui/<xi>が、1/CCは2~10程度の定数よりも小さければui/<xi>=<1/C、即ち、<xi>/ui>=C、多くのxkiが平均値<xi>の近傍に集中しているので、n個の特徴量におけるi番目の特徴量がそのクラスタの特徴量として有効であることを意味しており、その場合はvi=1、それ以外の場合i番目の特徴量がそのクラスタの特徴量として有効でないはvi=0とし、1又は0であるviを要素とする中心ベクトルv=v1,,vnを求めることができる。即ち、中心ベクトルvは、n個の特徴量の中で、どの特徴量がそのクラスタの特徴量として有効であるかを示す特徴量ベクトルである。また、上記の<xi>が正であれば、上記の判定式によって得られる、中心ベクトルの要素vi1又は0は、ガウスの記号[]を用いてvi=[pi]-[|pi-1|]と表される。但し、pi=<xi>/uiCである。一方、特徴量としてファジィハッシュを用いた場合は、類似度の計算が特殊なので特徴量から中心を求めることは難しい。類似度さえ計算できればどのような特徴量でもクラスタリング可能な方法として階層的クラスタリングがある。これは以下の手順で行われる。S54-a1個の特徴量だけを含むN個のクラスタを生成する。S54-bクラスタiとjのそれぞれの特徴量xiとxjの距離非類似度からクラスタ間の距離を計算し、最も距離の近い2つのクラスタを逐次的に1つのクラスタに併合する。S54-cこの併合を全ての対象が1つのクラスタに併合されるまで繰り返す。階層的クラスタリングによる出力はデンドログラムdendrogram、樹状図、系統樹とよばれるツリー構造をとる。デンドログラムによりどのデータがどのクラスタに属するかということだけではなく、クラスタ内のデータ同士がどの程度離れているかということも求められる。なお、クラスタの併合を工夫することで、計算量のオーダをNの2乗にまで抑えられることが知られている。詳細については非特許文献8を参照のこと。以上まとめると、K平均法は高速に動作するが、特徴量から中心が定まる場合にのみ適用できる。階層的クラスタリングはK平均法より低速だが、類似度さえ計算できればどのようなデータでもクラスタリングできる。図6はデータベースサーバが作成する登録データ格納位置管理テーブル60とクラスタ管理テーブル62のデータ構成を例示する図である。データベースサーバ40の登録部420は、登録クライアント20から暗号化データ、秘匿化インデックス、特徴量の組登録データを受信すると、登録データ格納位置管理テーブル60を作成して記憶装置416に格納する。登録データ格納位置管理テーブル60は、登録データを一意に識別する登録データIDを格納する登録IDカラム600、受信した暗号化データの記憶装置416内の格納場所を記録する暗号化データカラム602、秘匿化インデックスの記憶装置416内の格納場所を記録する秘匿化インデックスカラム604、特徴量の記憶装置416内の格納場所を記録する特徴量カラム606、暗号化データ等を登録した登録クライアント20の識別情報を格納する登録クライアントカラム608およびその他必要な事項を格納するカラム608を備える。登録部420は、登録データが追加される度に値を1ずつ増やすなどして、登録データを一意に識別できるように登録データIDを発行する。暗号化データカラム602、秘匿化インデックスカラム604および特徴量カラム606に記録する情報として、暗号化データなどのファイル名や記憶装置416内のセクタアドレスなどがある。なお、特徴量は暗号化データなどと比較してデータ量が少ないため、直接特徴量カラム606に格納してもよい。登録クライアントカラム608に格納すべき情報として、暗号化データ等を登録した登録クライアント20のIPアドレスがある。この情報は認証部418が図5のステップS520で取得しており、検索クライアント30と登録クライアント20の間で鍵共有をする場合に必要になる。鍵共有処理の詳細については後で図7を用いて説明する。さらに、カラム608に格納すべき情報として、例えばデータの登録日時がある。クラスタリング部430は特徴量を用いてクラスタリングした結果をクラスタ管理テーブル62に記録し、記憶装置416に格納する。そのクラスタ管理テーブル62は、クラスタを一意に識別するクラスタIDを格納するクラスタIDカラム620、クラスタに属する登録データの登録データID600を格納する登録データIDカラム622およびその他必要な事項を格納するカラム624からなる。カラム624に格納すべき情報として、例えばK平均法におけるクラスタの中心に関する情報をなどがある。秘匿検索処理の詳細以上、特徴量算出方法やクラスタリング方法、およびこれらを実現するための装置について説明してきた。これらの方法および装置は、秘匿検索の高速化のために必要な、いわば事前準備に相当する。以下、データベースサーバが行う秘匿検索処理の詳細について説明する。検索クライアントとデータベースサーバの検索処理図7は検索クライアントとデータベースサーバの検索処理を例示するシーケンス図である。図7に基づいて当該データ登録処理を説明するとともに、図2、図3および図6の説明で述べた鍵共有手順や、図3の説明で述べたトラップドア生成手順についても具体的な処理を例示する。検索クライアント30とデータベースサーバ40で行われる秘匿検索処理は、大別すると、検索クライアント20が検索クエリからトラップドアを生成するトラップドア生成処理S70と、検索クライアント20とデータベースサーバ40との間で検索処理を行う秘匿検索処理S72と、登録クライアント20と検索クライアント30との間で復号鍵を共有し、暗号データを復号する復号化処理S74からなる。検索クライアント20の検索部320はトラップドア生成処理S70として、ユーザインターフェース330を介してユーザから検索クエリを受けとり、トラップドア生成部322を制御して検索クエリからトラップドアを生成する。非特許文献1に基づいて具体的なトラップドア生成処理S70を例示すると、以下のようになる。S70-1秘匿化インデックス生成処理S502-2で用いたハッシュ関数を準備する。S70-2当該ハッシュ関数を用いて検索クエリ検索キーワードのハッシュ値を計算する検索キーワードの秘匿化。これがトラップドアとなる。検索クエリのハッシュ値を用いるので、トラップドアから検索クエリを特定することは困難となる。こうして求めたトラップドアと秘匿化インデックスとの照合方法については、後の図9の説明で明らかにする。秘匿検索処理S72は以下の手順で進行する。S720検索クライアント30とデータベースサーバ40との間でデータ授受のための通信路を確立する。具体的には、まず認証部418が通信インターフェース332,462やユーザインターフェース330を介して検索クライアント30のユーザとのID、及びパスワードなどでユーザの認証を行う。あらかじめ登録された正規のユーザと判断した場合、認証部418は、検索クライアント30の検索部320とデータベースサーバ40の検索部440との間で通信路を確立する。正規のユーザでないと判断した場合は通信路を確立せず、処理を終了する。S722検索部320は通信インターフェース332を介してトラップドアをデータベースサーバ40に送信する。データベースサーバ40の検索部440は通信インターフェース462を介して当該トラップドアを受信する。S724検索部440の優先順位算出部442は、受信したトラップドアと記憶装置416に格納されている秘匿化インデックスの一部と照合を行うことで照合の優先順位を算出する。具体的な優先順位算出手順については次の図8を用いて説明する。S726検索部440はステップS724で求めた優先順位をもとに照合部444を制御して、優先度が高い順にトラップドアと秘匿化インデックスの照合処理を行う。具体的な照合手順については後で図9を用いて説明する。S728検索部440は、ヒットした暗号化データを検索部320に返信する。併せて、登録データ格納位置管理テーブル60の登録クライアントカラム608に格納されている登録クライアント20のIPアドレスも返信する。後の復号化処理S74で検索クライアント30が復号鍵を入手するために必要となるためである。S730認証部418は、検索部320と検索部440との間で確立した通信路を開放する。次に復号化処理S74について説明する。検索結果として入手した暗号化データを復号するためには、登録クライアント20から復号鍵を共有しなければならない。鍵共有の方法として、SSLで利用されている公開鍵暗号を用いる鍵共有法や、IPSecで利用されているDH鍵共有法が知られている。ここでは公開鍵暗号を用いる鍵共有法について具体的手順を説明する。S740鍵共有部324はデータベースサーバ40から受信した検索結果から、暗号化データ等を登録した登録クライアント20の、IPアドレスなどといった識別情報を取り出す。登録クライアント20は当該暗号化データの復号鍵を所有している。復号鍵を共有する前に、まずは検索クライアント30がなりすましなどをしていない正規のクライアントであることを証明しなければならない。鍵共有部324は以下の手順で登録クライアント20の認証を行う。S740-1鍵共有部324は登録クライアント20のIPアドレスをもとに通信インターフェース332を介して登録クライアント20に接続する。S740-2登録クライアント20の鍵生成部218は、通信インターフェース232を介して検索クライアント30の鍵共有部324に証明書を要求する。ここで証明書とは、信頼できる第三者CA:CertificateAuthority、認証局が検索クライアント30の公開鍵に電子署名を施したものである。S740-3鍵共有部324は当該証明書を登録クライアント20へ送付する。S740-4鍵生成部218は当該証明書の署名を検証し、検索クライアント30の公開鍵を取得する。署名の検証に失敗した場合は、証明書が不正であるとして通信路を切断して処理を終了する。S740-5鍵共有部324はメッセージを生成してメッセージダイジェストを付加し、鍵共有部324の持つ秘密鍵で暗号化して、鍵生成部218へ送信する。S740-6鍵生成部218は、鍵共有部324の公開鍵を使ってメッセージを解読する。解読したメッセージからメッセージダイジェストを作成し、鍵共有部324が付加したメッセージダイジェストと比較する。双方のメッセージダイジェストの一致が確認されれば正規の検索クライアント30から改ざんされていないメッセージを受信したと判定され、認証が完了する。そうでない場合は、検索クライアント30は正規のクライアントではないと判定され、通信路を切断し、処理を終了する。S704-1からS740-6で述べた認証手順では、登録クライアント20のユーザの意思にかかわらず、CAに正規の証明書を発行してもらった正規の検索クライアント30は全て、暗号化データを復号し得ることになる。復号鍵の送付先を限定するためには、ステップS704-1で検索クライアント30から接続された際や、ステップS740-4において証明書を検証した際に、鍵生成部218が接続元の情報や証明書などから検索クライアント30の識別情報も読み取り、所定の検索クライアント以外に復号鍵を送信しないように通信路を切断するといった方法をとればよい。復号鍵の送信先の指定は、ユーザがユーザインターフェース230を介して行うことができる。認証が完了した後、検索クライアント30は、以下の手順で登録クライアント20から復号鍵を入手する。S742登録クライアント20の鍵生成部218は、証明書から取得した公開鍵で自己の有する復号鍵を暗号化して、通信インターフェース232を介して検索クライアント30の鍵共有部324に送信する。鍵共有部324は当該暗号化された復号鍵を自己の秘密鍵で復号して、所望の復号鍵を得る。S744復号化部326がS742で入手した復号鍵を用いて暗号データを復号して、検索処理が完了する。以上の手順により検索クライアント30のユーザは、データベースサーバ40の管理者や通信路上の第三者に検索クエリや検索結果の内容を事実上知られることなく、所望の検索結果を入手することができる。優先順位決定図8はデータベースサーバ40が行う優先順位算出S724の処理手順を例示するフローチャートである。図8に基づいて検索クライアント30からトラップドアを受信してから行う優先順位算出処理について以下に説明する。図5で述べた秘匿化インデックスとトラップドアとの照合についても、具体的な処理を例示する。なお、以下の処理はすべてデータベースサーバ40の検索部440の優先順位算出部442が行う。S800クラスタをカウントするための変数pに1を設定する。S802クラスタIDがpとなるクラスタに属する全登録データから代表データを選択する。代表データは、当該クラスタに属する全登録データからランダムに選択してもいいし、K平均法を用いた場合には、当該クラスタの中心に最も近い登録データを代表データとしてもよい。例えば、所定の順序でクラスタ内の登録データを並べた時に、全体の順序の中心付近に位置するデータを代表データとする。S804変数pが全クラスタ数よりも小さい場合、pを1増やしてS806、ステップS802に戻り、次のクラスタについて同様の処理を行う。そうでない場合はステップS810へ進む。S810クラスタをカウントするための変数qに1を設定する。S812クラスタIDがqとなるクラスタの代表データの秘匿化インデックスとトラップドアとを照合する。非特許文献1に基づいて具体的な照合方法を例示すると以下のようになる。秘匿化インデックスとトラップドアの照合の処理手順を図14に示す。なお、図13のS502-1からS502-4で求められた秘匿化インデックスHiは、預託データ内の単語Wiから生成したハッシュ値hiと、乱数列riとそのメッセージダイジェストdiを連結したものとの排他的論理和で生成されたものとするi=1,2,...。また、S70-1からS70-2の手順で求めたトラップドアをh′とする。なお、添え字iは、預託データ内に含まれるそれぞれの単語に対する識別子である。S812-1各単語Wiについて、秘匿化インデックスHiとトラップドアh′との排他的論理和を取る。S812-2ステップS502-3と同様に、当該排他的論理和ビット列S′iの先頭cビットのビット列r′iから、図13のステップS502-3と同じ所定の演算を行なってメッセージダイジェストDiを計算し、このDiを、当該排他的論理和の後半n-cビットのビット列d′iと比較する。S812-3もしhi=h′、即ち、元の単語Wiと検索キーワードとが一致するならば、このダイジェストDiとビット列d′iとの排他的論理和を取ることで、乱数列riとそのメッセージダイジェストdiだけが残るはずである。よって、r′iのメッセージダイジェストDiがd′iに一致すれば、hiはh′に等しく、秘匿化インデックスに対応する預託データはトラップドアに対応する検索クエリ検索キーワードを含んでいると判断できる。以下この事象を単純に検索にヒットしたという。一致しない場合、秘匿化インデックスに対応する預託データはトラップドアに対応する検索クエリを含んでいないと判断する。ここで、図14を参照しながら、ステップS812-2、812-3における検索クエリとトラップドアとの一致判定のアルゴリズムを説明する。排他的論理和をXOR、集合Aの補集合否定を¬、論理和を、論理積を、2つのビット列の結合を|とすると、一般に、3つの集合の排他的論理和は、AXORBXORC=XB¬X¬B、かつ、X=¬AXORC、¬X=AXORCとなる。ここで、A=hi単語wiのハッシュ値、B=ri|di乱数列riとメッセージダイジェストdiからなるビット列Si、C=h′トラップドアとすると、X=hiXOR¬h′、¬X=hiXORh′となる。特に、hi=h′の場合、X=1、¬X=0となる。秘匿化インデックスHiとトラップドアh′との排他的論理和を、HiXORh′=r′i|d′i乱数列とメッセージダイジェストからなるビット列S′iとおいてS812-1、この左辺のHiに上記のHiの表現を代入すると、r′i=Xri¬X¬ri、及びd′i=Xdi¬X¬diとなる。もし、hi=h′ならば、X=1、¬X=0であるから、r′i=ri、及びd′i=diとなる。従って、トラップドアによるメッセージダイジェストDi=fr′i=fri=diS812-2、さらに、d′i=diであるから、Di=d′iとなるS812-3。以上のことから、hi=h′、即ち、単語Wi=検索キーワードであれば、Di=d′iとなるS812-3。乱数列と排他的論理和の性質を利用することで、平文と暗号文が1対1とならない場合でもトラップドアとの照合を行うことができる。詳細については非特許文献1参照のこと。なお、クラスタ内の代表データ登録データ、特に、登録データ内の秘匿化インデックスをピボットとも言う。S814秘匿化インデックスとトラップドアとの合致率が大きいほど優先度が高くなるよう、クラスタIDがqとなるクラスタの優先度を算出する。トラップドアが1つの場合、合致度は検索にヒットしたか否かの二値で与えられる。複数の検索キーワードを指定してこれらのand論理積検索やor論理和検索を行った場合、トラップドアは複数となるため、合致度は、検索にヒットしたトラップドアの個数と全トラップドアとの比で与えられる。S816変数qが全クラスタ数よりも小さい場合、qを1増やしてS818、ステップS812に戻り、次のクラスタについて同様の処理を行う。そうでない場合はステップS820へ進む。S820優先順位算出部442は、優先度が高い順になるようにクラスタIDをソートし、当該結果をメモリ414または記憶装置416に出力する。以上で優先順位算出処理を終了する。クラスタの優先順位に基づく登録データの照合図9は、データベースサーバ40が行う秘匿化インデックスとトラップドアの照合処理図8のステップS812の手順を例示するフローチャートである。本発明の実施の形態では、預託データの特徴量を用いて照合対象の優先順位を定めてから照合を順次行い、一定回数で照合を打ち切ることで、安全性や検索精度の低下を抑えつつ秘匿検索処理の高速化を実現することを特徴とする。以下、照合を行う回数を照合回数とよぶ。当該照合回数はあらかじめ登録クライアント20のユーザがユーザインターフェース230を介して設定しておく。照合回数の設定については後で図11を用いて説明する。秘匿化インデックスとトラップドアの照合処理は以下の手順で行われる。なお、以下の処理S904を除くはすべて検索部440が行う。S900照合回数をカウントする変数tを0に、クラスタをカウントする変数kを1に設定する。S902クラスタ内の登録データをカウントする変数nを1に設定する。メモリ414または記憶装置416からステップS820で優先順位算出部442が出力した優先順位を読み込み、k番目に優先順位が高いクラスタCkを特定する。S904照合部444は、クラスタCkに含まれるn番目の登録データの秘匿化インデックスとトラップドアとを照合する。ヒットした場合、秘匿化インデックスとトラップドアの合致率と併せて、対応する登録データIDをメモリ414または記憶装置416に一時的に出力する。ヒットしなかった場合は何も出力しない。S906照合回数の変数tを1増やす。S908もし変数tがあらかじめ定めた照合回数より小さい場合は、次のステップS910に進む。そうでない場合はステップS918に進み、処理を終了する。S910登録データをカウントする変数nがクラスタCkに含まれる全登録データ数よりも小さい場合、nを1増やしてS912、ステップS904に戻り、クラスタ内の次の登録データについて同様の処理を行う。そうでない場合はステップS914へ進む。S914優先順位を表す変数kが全クラスタ数よりも小さい場合、kを1増やしてS916、ステップS902に戻り、次に優先順位が高いクラスタについて同様の処理を行う。そうでない場合はステップS918へ進む。S918検索部440は、照合部444がメモリ414または記憶装置416に一時的に出力した登録データIDに対応する暗号化データを、メモリ414または記憶装置416に合致率とともに出力する。以上で秘匿化インデックスとトラップドアの照合処理を終了する。例えば、登録クライアント20が雲というキーワードを含む1000個の預託データと、雲を含まない9000個の預託データを、本実施形態によりデータベースサーバ40に登録したとする。データベースサーバ40では、クラスタリング処理により、雲を含むクラスタAと含まないクラスタBの2つに分解して登録データが管理されることになる。検索クライアント30が雲という検索クエリで検索した場合、検索クエリトラップドアとピボット秘匿化インデックスの代表との照合により、クラスタAの1000個の登録データが優先的に照合される。よって、仮に1000回で照合を打ち切ったとしても、雲を含む1000個の全預託データにヒットすることになる。一方、従来の検索可能暗号を用いた秘匿検索システムにおいては、10000個の全登録データに対して雲という検索クエリのトラップドアと照合して、初めて雲を含む全預託データにヒットする。従って、この例では、本発明は従来と比較して10倍検索速度を向上できたといえる。このように、図1から図9を用いて説明した本発明の実施の形態に従って、元のデータを推測しにくい特徴量を用いて秘匿化インデックスをクラスタリングしておくことで、安全性や検索精度の低下を抑えつつ、秘匿検索を高速化することができた。図10も、データベースサーバ40が行う秘匿化インデックスとトラップドアとの照合処理手順を例示するフローチャートである。図9の例では一定回数で照合を打ち切ることで秘匿検索処理の高速化を実現したが、照合回数ではなく検索にヒットした回数以下、ヒット回数とよぶで打ち切ることでも高速化を実現できる。具体的には、図9のステップS906およびS908が以下のステップS906-a,S906-b,S908′に置き換わる。以下の処理はすべて検索部440が行う。S906-a照合部444において検索がヒットしたかどうかを判断する。ヒットしたときS906-bへ進む。ヒットしなかったときステップS908′へ進む。S906-b照合回数の変数tを1増やす。S908′もし変数tがあらかじめ定めたヒット回数より小さい場合は、次のS910に進む。そうでない場合はS918に進み、処理を終了する。ヒット回数は、あらかじめ登録クライアント20のユーザがユーザインターフェース230を介して設定しておく。ヒット回数の設定については後で図11を用いて説明する。図10のフローチャートによる方法はあらかじめ設定したヒット回数に達するまで照合を繰り返すため、図9で説明した検索方法と比較して検索漏れが少なくなるという利点がある。その反面、検索にヒットしなければ検索が遅延するという欠点がある。一方、図9で説明した方法は、あらかじめ設定した照合回数しか照合を行わないため、図10の方法よりも検索漏れが生じやすいという欠点があるが、検索結果のいかんにかかわらず検索応答時間が一定に保たれるという利点がある。図11は、検索クライアント30またはデータベースサーバ40で行う設定画面を例示する図である。図3の説明で述べた検索クライアント30の設定部328が設定するパラメータとして、例えば照合回数がある。ダイアログ1100や1120は、設定部328が照合回数をユーザに設定させるためにユーザインターフェース330を介してユーザに提示する画面の例である。ダイアログ1100では、スライドバー1102を左に動かすほど照合回数が小さくなって検索速度が向上する一方で、検索にヒットする登録データに到達する可能性が下がり、検索精度が低下する。スライドバー1102を右に動かすほど照合回数が大きくなって、検索速度が低下する一方、検索精度が向上する。スライドバー1122の位置に応じて、照合回数は、設定部328が保持する所定の値に設定される。また、ダイアログボックス1120の入力ボックス1122で、ユーザが直接照合回数を設定することもできる。なお図10で説明した実施形態においては、上記説明における照合回数をヒット回数に読み替える。また、照合回数またはヒット回数の設定をデータベースサーバ40の管理者が行う実施形態もある。この場合、データベースサーバ40の設定部450がユーザインターフェース460を介してダイアログ1100や1120を提示する。データベースサーバ40の管理者が、登録データ数やクラスタリングの態様を定期的にチェックし、検索応答時間が遅延しないように照合回数を調整することで、秘匿検索サービスの質を保証することができる。"