(57)【要約】  頻度分析への耐性を持つ秘匿検索を実現する。（１）変換規則管理装置４００は、検索キーワードと変換キーワード群とを対応付けた変換規則テーブルを生成する。（２）データ登録装置５００は、暗号化データと暗号化キーワードとを対応付けた登録データを変換規則テーブルに基づいて生成し、登録データをサーバ装置３００に登録する。（３）情報処理装置２００は、指定された検索キーワードに対応する変換キーワード群を変換規則テーブルから取得し、暗号化キーワード群を生成し、暗号化キーワード群を指定してデータ検索を要求する。（４）サーバ装置３００は、暗号化キーワード群に含まれる暗号化キーワードを検索キーとして検索キーに対応する暗号化データを検索し、検索した暗号化データを応答する。（５）情報処理装置２００は、検索された暗号化データを復号し、復号して得られた検索データを検索結果として出力する。
2012115031.tif 000002
【特許請求の範囲】
【請求項１】
情報処理装置と検索装置とを備える検索システムにおいて、
前記情報処理装置は、
検索キーワードと１以上の対応キーワードとを対応させた対応キーワード群を対応キーワードデータとして記憶する対応キーワード記憶部と、
検索キーワードを入力する検索キーワード入力部と、
前記検索キーワード入力部により入力された前記検索キーワードに対応する対応キーワード群を前記対応キーワード記憶部に記憶された対応キーワードデータから取得する対応キーワード群取得部と、
前記対応キーワード群取得部によって取得された対応キーワード群に含まれる対応キーワードを暗号化して暗号化キーワード群を生成する暗号化キーワード群生成部と、
前記暗号化キーワード群生成部によって生成された暗号化キーワード群を含む検索要求データを前記検索装置へ送信する検索要求データ送信部と、
前記検索装置から送信される検索応答データを受信する検索応答データ受信部と、
前記検索応答データ受信部によって受信された検索応答データに含まれる暗号化データを復号し、復号して得られる検索データを検索結果として出力する検索結果出力部とを備え、
前記検索装置は、
検索データを暗号化した暗号化データを記憶する暗号化データ記憶部であって、検索データ毎に当該検索データを暗号化した暗号化データと対応キーワードを暗号化した暗号化キーワードとを対応付けて記憶する暗号化データ記憶部と、
前記情報処理装置から送信される検索要求データを受信する検索要求データ受信部と、
前記検索要求データ受信部によって受信された検索要求データに基づいて、前記検索要求データ内の暗号化キーワード群に含まれる暗号化キーワードを検索キーとして検索キーに対応する暗号化データを前記暗号化データ記憶部から取得する暗号化データ検索部と、
前記暗号化データ検索部によって取得された暗号化データを含む検索応答データを送信する検索応答データ送信部と
を備えることを特徴とする検索システム。
【請求項２】
前記検索システムは、さらに、対応キーワード管理装置を備え、
前記対応キーワード管理装置は、
検索キーワードを定義すると共に特定の検索キーワードに対応付けられる検索データの割合を特定の検索キーワードの出現頻度として定義する出現頻度データを記憶する出現頻度記憶部と、
前記出現頻度記憶部に記憶される出現頻度データに定義された前記検索キーワードの出現頻度に応じて、前記検索キーワードに対応付ける対応キーワードの個数を対応キーワード数として算出する対応キーワード数算出部と、
前記対応キーワード数算出部によって算出された対応キーワード数と同じ個数の対応キーワードを対応キーワード群として生成する対応キーワード群生成部と、
前記出現頻度データに定義された検索キーワードと前記対応キーワード群生成部によって生成された対応キーワード群とを対応付けて前記対応キーワードデータを生成する対応キーワードデータ生成部とを備え、
前記情報処理装置の対応キーワード記憶部は、前記対応キーワード管理装置によって生成された対応キーワードデータを記憶する
ことを特徴とする請求項１記載の検索システム。
【請求項３】
前記対応キーワード管理装置の対応キーワード数算出部は、前記出現頻度データに定義された検索キーワードの出現頻度に基づいて、前記検索キーワードの対応キーワード毎に前記検索キーワードの対応キーワード群から当該対応キーワードを選択する割合を対応キーワード選択率として算出し、
前記対応キーワード管理装置の対応キーワードデータ生成部は、前記検索キーワードと前記対応キーワード群と前記対応キーワード選択率とを対応付けたデータを対応キーワード選択率データとして生成し、
前記検索システムは、さらに、暗号化データ生成装置を備え、
前記暗号化データ生成装置は、
検索データと検索キーワードとを対応付けて記憶する検索データ記憶部と、
前記対応キーワード管理装置によって生成された対応キーワード選択率データを記憶する対応キーワード選択率記憶部と、
前記対応キーワード選択率データから前記検索データ記憶部に記憶された検索キーワードに対応する対応キーワード群を取得し、取得した対応キーワード群に含まれる少なくともいずれかの対応キーワードを前記対応キーワード選択率データに含まれる対応キーワード選択率に応じて選択する対応キーワード選択部と、
前記検索データ記憶部に記憶された検索データを暗号化して暗号化データを生成し、前記対応キーワード選択部によって選択された対応キーワードを暗号化して暗号化キーワードを生成する暗号化データ生成部とを備え、
前記検索装置の前記暗号化データ記憶部は、前記暗号化データ生成装置によって生成された暗号化データと暗号化キーワードとを対応付けて記憶する
ことを特徴とする請求項２記載の検索システム。
【請求項４】
前記対応キーワード管理装置の対応キーワード数算出部は、各検索キーワードの対応キーワード数で分割した分割後の各検索キーワードの出現頻度が等しくなるように各検索キーワードの対応キーワード数を算出し、
前記対応キーワード数算出部は、検索キーワード毎に前記対応キーワード数の逆数を前記対応キーワード選択率として算出する
ことを特徴とする請求項３記載の検索システム。
【請求項５】
前記対応キーワード数算出部は、各検索キーワードの出現頻度の最大公約数を算出し、検索キーワード毎に検索キーワードの出現頻度を前記最大公約数で除算した値を検索キーワードの対応キーワード数として算出する
ことを特徴とする請求項４記載の検索システム。
【請求項６】
前記対応キーワード管理装置の対応キーワード数算出部は、所定の匿名数以上の検索キーワードが同じ出現頻度を持つように各検索キーワードの出現頻度を分割する分割数を各検索キーワードの対応キーワード数として算出し、各検索キーワードの出現頻度を分割する分割割合を各検索キーワードの対応キーワード選択率として算出する
ことを特徴とする請求項３記載の検索システム。
【請求項７】
前記対応キーワード数算出部は、各検索キーワードの出現頻度から所定の匿名数番目に大きい出現頻度を演算頻度として選択し、前記演算頻度以上の出現頻度から１つ以上の演算頻度を減算し、減算後の各検索キーワードの出現頻度から前記匿名数番目に大きい出現頻度を新たな演算頻度として選択し、新たな演算頻度以上の出現頻度から１つ以上の新たな演算頻度を減算し、検索キーワード毎に出現頻度から減算した各演算頻度の数を対応キーワード数として算出すると共に元の出現頻度に対する各演算頻度の割合を対応キーワード選択率として算出する
ことを特徴とする請求項３記載の検索システム。
【請求項８】
前記対応キーワード数算出部は、検索キーワード毎に検索キーワードの出現頻度を所定の基数のべき乗値を用いて複数の出現頻度に分割し、検索キーワード毎に出現頻度の分割数を対応キーワード数として算出すると共に分割前の出現頻度に対する分割後の出現頻度の割合を対応キーワード選択率として算出する
ことを特徴とする請求項３記載の検索システム。
【請求項９】
前記対応キーワード数算出部は、各検索キーワードの分割後の出現頻度のうち当該出現頻度を持つ検索キーワードの数が所定の匿名数未満である出現頻度を前記基数のべき乗値を用いて分割する
ことを特徴とする請求項８記載の検索システム。
【請求項１０】
前記対応キーワード数算出部は、特定数の対応キーワードを検索キーワード毎に設けた場合の対応確率値として検索キーワードと特定数の対応キーワードとを所定の組み合わせで対応付ける確率を各検索キーワードの出現頻度に基づいて算出し、算出した対応確率値に基づいて検索キーワードと特定数の対応キーワードとの組み合わせのエントロピーをエントロピー値として算出し、算出したエントロピー値に前記対応確率値を乗算してエントロピー指標値を算出し、算出したエントロピー指標値を所定のエントロピー閾値と比較し、前記エントロピー指標値が前記エントロピー閾値より大きい場合、前記対応キーワードの特定数を対応キーワード数として算出し、
前記対応キーワード数算出部は、前記対応キーワード数の逆数を前記対応キーワード選択率として算出する
ことを特徴とする請求項３記載の検索システム。
【請求項１１】
情報処理装置と検索装置とを備える検索システムの検索方法において、
前記情報処理装置は、検索キーワードと１以上の対応キーワードとを対応させた対応キーワード群を対応キーワードデータとして記憶する対応キーワード記憶部を備え、
前記情報処理装置は、
検索キーワードを入力する検索キーワード入力処理と、
前記検索キーワード入力部により入力された前記検索キーワードに対応する対応キーワード群を前記対応キーワード記憶部に記憶された対応キーワードデータから取得する対応キーワード群取得処理と、
前記対応キーワード群取得処理によって取得された対応キーワード群に含まれる対応キーワードを暗号化して暗号化キーワード群を生成する暗号化キーワード群生成処理と、
前記暗号化キーワード群生成処理によって生成された暗号化キーワード群を含む検索要求データを前記検索装置へ送信する検索要求データ送信処理とを実行し、
前記検索装置は、検索データを暗号化した暗号化データを記憶する暗号化データ記憶部であって、検索データ毎に当該検索データを暗号化した暗号化データと対応キーワードを暗号化した暗号化キーワードとを対応付けて記憶する暗号化データ記憶部を備え、
前記検索装置は、
前記情報処理装置から送信される検索要求データを受信する検索要求データ受信処理と、
前記検索要求データ受信処理によって受信された検索要求データに基づいて、前記検索要求データ内の暗号化キーワード群に含まれる暗号化キーワードを検索キーとして検索キーに対応する暗号化データを前記暗号化データ記憶部から取得する暗号化データ検索処理と、
前記暗号化データ検索処理によって取得された暗号化データを含む検索応答データを送信する検索応答データ送信処理とを実行し、
前記情報処理装置は、さらに、
前記検索装置から送信された検索応答データを受信する検索応答データ受信処理と、
前記検索応答データ受信処理によって受信された検索応答データに含まれる暗号化データを復号し、復号して得られる検索データを検索結果として出力する検索結果出力処理とを実行する
ことを特徴とする検索システムの検索方法。
【請求項１２】
検索キーワードと１以上の対応キーワードとを対応させた対応キーワード群を対応キーワードデータとして記憶する対応キーワード記憶部と、
検索キーワードを入力する検索キーワード入力部と、
前記検索キーワード入力部により入力された前記検索キーワードに対応する対応キーワード群を前記対応キーワード記憶部に記憶された対応キーワードデータから取得する対応キーワード群取得部と、
前記対応キーワード群取得部によって取得された対応キーワード群に基づいて、前記対応キーワード群に含まれる対応キーワードを暗号化して暗号化キーワード群を生成する暗号化キーワード群生成部と、
前記暗号化キーワード群生成部によって生成された暗号化キーワード群を含む検索要求データを所定の検索装置へ送信する検索要求データ送信部と、
前記検索装置から送信される検索応答データであって前記暗号化キーワードに対応する暗号化データを含んだ検索応答データを受信する検索応答データ受信部と、
前記検索応答データ受信部によって受信された検索応答データに含まれる暗号化データを復号し、復号して得られる検索データを検索結果として出力する検索結果出力部と
を備えることを特徴とする情報処理装置。
【請求項１３】
検索キーワードと１以上の対応キーワードとを対応させた対応キーワード群を対応キーワードデータとして記憶する対応キーワード記憶部を備える情報処理装置の検索プログラムにおいて、
検索キーワードを入力する検索キーワード入力処理と、
前記検索キーワード入力部により入力された前記検索キーワードに対応する対応キーワード群を前記対応キーワード記憶部に記憶された対応キーワードデータから取得する対応キーワード群取得処理と、
前記対応キーワード群取得処理によって取得された対応キーワード群に基づいて、前記対応キーワード群に含まれる対応キーワードを暗号化して暗号化キーワード群を生成する暗号化キーワード群生成処理と、
前記暗号化キーワード群生成処理によって生成された暗号化キーワード群を含む検索要求データを所定の検索装置へ送信する検索要求データ送信処理と、
前記検索装置から送信される検索応答データであって暗号化キーワード群に対応する暗号化データを含んだ検索要求データを受信する検索応答データ受信処理と、
前記検索応答データ受信処理によって受信された検索応答データに含まれる暗号化データを復号し、復号して得られる検索データを検索結果として出力する検索結果出力処理とを前記情報処理装置に実行させることを特徴とする検索プログラム。
【請求項１４】
検索キーワードを定義すると共に特定の検索キーワードに対応付けられる検索データの割合を特定の検索キーワードの出現頻度として定義する出現頻度データを記憶する出現頻度記憶部と、
前記出現頻度記憶部に記憶される出現頻度データに定義された前記検索キーワードの出現頻度に応じて前記検索キーワードに対応付ける対応キーワードの個数を対応キーワード数として算出し、前記検索キーワードの対応キーワード毎に当該対応キーワードを選択する割合を対応キーワード選択率として算出する対応キーワード数算出部と、
前記対応キーワード数算出部によって算出された対応キーワード数と同じ個数の対応キーワードを対応キーワード群として生成する対応キーワード群生成部と、
前記出現頻度データに定義された検索キーワードと前記対応キーワード群生成部によって生成された対応キーワード群と前記対応キーワード数算出部によって算出された対応キーワード選択率とを対応付けたデータを対応キーワードデータとして生成する対応キーワードデータ生成部と
を備えることを特徴とする対応キーワード管理装置。
【請求項１５】
前記対応キーワード数算出部は、所定の匿名数以上の検索キーワードが同じ出現頻度を持つように各検索キーワードの出現頻度を分割する分割数を各検索キーワードの対応キーワード数として算出し、各検索キーワードの出現頻度を分割する分割割合を各検索キーワードの対応キーワード選択率として算出する
ことを特徴とする請求項１４記載の対応キーワード管理装置。
【請求項１６】
前記対応キーワード数算出部は、各検索キーワードの出現頻度から所定の匿名数番目に大きい出現頻度を演算頻度として選択し、前記演算頻度以上の出現頻度から１つ以上の演算頻度を減算し、減算後の各検索キーワードの出現頻度から前記匿名数番目に大きい出現頻度を新たな演算頻度として選択し、新たな演算頻度以上の出現頻度から１つ以上の新たな演算頻度を減算し、検索キーワード毎に出現頻度から減算した各演算頻度の数を対応キーワード数として算出すると共に元の出現頻度に対する各演算頻度の割合を対応キーワード選択率として算出する
ことを特徴とする請求項１４記載の対応キーワード管理装置。
【請求項１７】
前記対応キーワード数算出部は、検索キーワード毎に検索キーワードの出現頻度を所定の基数のべき乗値を用いて複数の出現頻度に分割し、検索キーワード毎に出現頻度の分割数を対応キーワード数として算出すると共に分割前の出現頻度に対する分割後の出現頻度の割合を対応キーワード選択率として算出する
ことを特徴とする請求項１４記載の対応キーワード管理装置。
【請求項１８】
前記対応キーワード数算出部は、各検索キーワードの分割後の出現頻度のうち当該出現頻度を持つ検索キーワードの数が所定の匿名数未満である出現頻度を前記基数のべき乗値を用いて分割する
ことを特徴とする請求項１７記載の対応キーワード管理装置。
【請求項１９】
前記対応キーワード数算出部は、特定数の対応キーワードを検索キーワード毎に設けた場合の対応確率値として検索キーワードと特定数の対応キーワードとを所定の組み合わせで対応付ける確率を各検索キーワードの出現頻度に基づいて算出し、算出した対応確率値に基づいて検索キーワードと特定数の対応キーワードとの組み合わせのエントロピーをエントロピー値として算出し、算出したエントロピー値に前記対応確率値を乗算してエントロピー指標値を算出し、算出したエントロピー指標値を所定のエントロピー閾値と比較し、前記エントロピー指標値が前記エントロピー閾値より大きい場合、前記対応キーワードの特定数を対応キーワード数として算出し、
前記対応キーワード数算出部は、前記対応キーワード数の逆数を前記対応キーワード選択率として算出する
ことを特徴とする請求項１４記載の対応キーワード管理装置。
【請求項２０】
検索キーワードを定義すると共に特定の検索キーワードに対応付けられる検索データの割合を特定の検索キーワードの出現頻度として定義する出現頻度データを記憶する出現頻度記憶部を備える対応キーワード管理装置の対応キーワード管理プログラムにおいて、
前記出現頻度記憶部に記憶される出現頻度データに定義された前記検索キーワードの出現頻度に応じて前記検索キーワードに対応付ける対応キーワードの個数を対応キーワード数として算出し、前記検索キーワードの対応キーワード毎に当該対応キーワードを選択する割合を対応キーワード選択率として算出する対応キーワード数算出処理と、
前記対応キーワード数算出処理によって算出された対応キーワード数と同じ個数の対応キーワードを対応キーワード群として生成する対応キーワード群生成処理と、
前記出現頻度データに定義された検索キーワードと前記対応キーワード群生成処理によって生成された対応キーワード群と前記対応キーワード数算出部によって算出された対応キーワード選択率とを対応付けたデータを対応キーワードデータとして生成する対応キーワードデータ生成処理と
を前記対応キーワード管理装置に実行させることを特徴とする対応キーワード管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、秘匿検索を行う検索システム、検索システムの検索方法、情報処理装置、検索プログラム、対応キーワード管理装置および対応キーワード管理プログラムに関するものである。
【背景技術】
【０００２】
秘匿検索システムは、サーバに保存されたデータを検索者がキーワードを指定して検索でき、かつその際にデータ・キーワードをサーバに対して秘匿する。【０００３】
秘匿検索システムは、機密データ管理のアウトソーシングや、メールサーバにおける暗号化メールのフィルタリングへの応用が期待されている。
そのため、秘匿検索システムの技術として、種々の安全性要件を達成するための技術や、サーバや検索者のストレージ・通信オーバーヘッド・演算オーバーヘッドを削減するための技術が提案されている。【０００４】
特に、確定的暗号をベースにした秘匿検索技術では同じキーワードが同じ暗号化キーワードに対応するため、サーバは指定された暗号化キーワードに基づく一致検索を行うだけで良い。このため、既存の検索技術を用いた高速化が可能である。【０００５】
しかし、確定的暗号を用いてキーワードを暗号化した場合、キーワードの頻度情報がそのまま暗号化キーワードの頻度情報として現れてしまう。このため、暗号化キーワードの頻度を調べることによって対応するキーワードを推測することができる。つまり、「頻度分析」と呼ばれる攻撃が可能である。【０００６】
この頻度分析への対策として、頻度を撹乱するためのダミーデータを挿入する方法がある。
特許文献１には、句読点など、通常検索に使用されない文字列を利用してダミーデータを生成する方式が開示されている。この方式により、データベースのサイズを増加することなく頻度分析への耐性を持たせることができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００５−７２９１７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ダミーデータの挿入による頻度撹乱方式では、もとのキーワードの頻度に大きな偏りがある場合、頻度の差に相当する大量のダミーデータを用意する必要がある。
特許文献１では検索に使用されない文字列を利用してデータベースサイズの増加を防いでいるが、データベースの種類によっては「検索に使用されない文字列」が少ない、あるいは全く存在しないこともあり得る。この場合、効率的に頻度撹乱することができない。【０００９】
本発明は、例えば、キーワードの頻度分布がどのようなものであっても効率的な頻度撹乱を行うことにより、頻度分析への耐性を持つ高速な秘匿検索を実現できるようにすることを目的とする。
【課題を解決するための手段】
【００１０】
本発明の検索システムは、情報処理装置と検索装置とを備える。
前記情報処理装置は、
検索キーワードと１以上の対応キーワードとを対応させた対応キーワード群を対応キーワードデータとして記憶する対応キーワード記憶部と、
検索キーワードを入力する検索キーワード入力部と、
前記検索キーワード入力部により入力された前記検索キーワードに対応する対応キーワード群を前記対応キーワード記憶部に記憶された対応キーワードデータから取得する対応キーワード群取得部と、
前記対応キーワード群取得部によって取得された対応キーワード群に含まれる対応キーワードを暗号化して暗号化キーワード群を生成する暗号化キーワード群生成部と、
前記暗号化キーワード群生成部によって生成された暗号化キーワード群を含む検索要求データを前記検索装置へ送信する検索要求データ送信部と、
前記検索装置から送信される検索応答データを受信する検索応答データ受信部と、
前記検索応答データ受信部によって受信された検索応答データに含まれる暗号化データを復号し、復号して得られる検索データを検索結果として出力する検索結果出力部とを備え、
前記検索装置は、
検索データを暗号化した暗号化データを記憶する暗号化データ記憶部であって、検索データ毎に当該検索データを暗号化した暗号化データと対応キーワードを暗号化した暗号化キーワードとを対応付けて記憶する暗号化データ記憶部と、
前記情報処理装置から送信される検索要求データを受信する検索要求データ受信部と、
前記検索要求データ受信部によって受信された検索要求データに基づいて、前記検索要求データ内の暗号化キーワード群に含まれる暗号化キーワードを検索キーとして検索キーに対応する暗号化データを前記暗号化データ記憶部から取得する暗号化データ検索部と、
前記暗号化データ検索部によって取得された暗号化データを含む検索応答データを送信する検索応答データ送信部とを備える。
【発明の効果】
【００１１】
本発明によれば、例えば、検索データと複数の暗号化キーワードとを対応付けることにより、キーワードの頻度分布がどのようなものであっても効率的な頻度撹乱を行い、頻度分析への耐性を持つ高速な秘匿検索を実現することができる。
【図面の簡単な説明】
【００１２】
【図１】実施の形態１における秘匿検索システム１００の構成図。
【図２】実施の形態１における情報処理装置２００の機能構成図。
【図３】実施の形態１におけるサーバ装置３００の機能構成図。
【図４】実施の形態１における変換規則管理装置４００の機能構成図。
【図５】実施の形態１におけるデータ登録装置５００の機能構成図。
【図６】実施の形態１における変換規則管理装置４００の変換規則管理方法を示すフローチャート。
【図７】実施の形態１における検索キーワードテーブル４９１を示す図。
【図８】実施の形態１における変換規則算出処理（Ｓ１１０）の一例を示すフローチャート。
【図９】実施の形態１における変換規則テーブル２９１を示す図。
【図１０】実施の形態１におけるデータ登録装置５００のデータ登録方法を示すフローチャート。
【図１１】実施の形態１における登録データテーブル３９１を示す図。
【図１２】実施の形態１における暗号化キーワードの登録頻度を示す図。
【図１３】実施の形態１における情報処理装置２００の検索方法を示すフローチャート。
【図１４】実施の形態１におけるサーバ装置３００の検索方法を示すフローチャート。
【図１５】実施の形態１における秘匿検索システム１００のハードウェア資源の一例を示す図。
【図１６】実施の形態２における変換規則算出処理（Ｓ１１０）のフローチャート。
【図１７】実施の形態２における検索キーワードテーブル４９１と分割済み頻度テーブル４９２とを示す図。
【図１８】実施の形態２における変換規則算出処理（Ｓ１１０）の概要図。
【図１９】実施の形態２における変換規則算出処理（Ｓ１１０）の概要図。
【図２０】実施の形態２における変換規則算出処理（Ｓ１１０）の概要図。
【図２１】実施の形態２における変換規則算出処理（Ｓ１１０）の概要図。
【図２２】実施の形態２における変換規則テーブル２９１を示す図。
【図２３】実施の形態２における暗号化キーワードの登録頻度を示す図。
【図２４】実施の形態２における検索キーワードテーブル４９１と分割済み頻度テーブル４９２との別例を示す図。
【図２５】実施の形態２における変換規則算出処理（Ｓ１１０）の再分割処理（Ｓ１１６Ｂ）を示すフローチャート。
【図２６】実施の形態２における再分割処理（Ｓ１１６Ｂ）の概要図。
【図２７】実施の形態２における再分割処理（Ｓ１１６Ｂ）の概要図。
【図２８】実施の形態２における分割済み頻度の最適化を示す図。
【図２９】実施の形態２における分割済み頻度の最適化を示す図。
【図３０】実施の形態２における分割済み頻度の最適化を示す図。
【図３１】実施の形態３における変換規則算出処理（Ｓ１１０）のフローチャート。
【図３２】実施の形態３における変換規則算出処理（Ｓ１１０）の概要図。
【図３３】実施の形態３における変換規則算出処理（Ｓ１１０）の概要図。
【図３４】実施の形態３における変換規則テーブル２９１を示す図。
【図３５】実施の形態３における暗号化キーワードの登録頻度を示す図。
【図３６】実施の形態３における分割済み頻度テーブル４９２の最適化の具体例を示す図。
【図３７】実施の形態３における変換規則テーブル２９１の別例を示す図。
【図３８】実施の形態３における暗号化キーワードの登録頻度の別例を示す図。
【図３９】実施の形態４における変換規則算出処理（Ｓ１１０）を示すフローチャート。
【図４０】実施の形態４における検索キーワードテーブル４９１を示す図。
【図４１】実施の形態４における変換規則テーブル２９１の一例を示す図。
【図４２】実施の形態４における検索キーワードと変換キーワードとの組み合わせの一例を示す図。
【図４３】実施の形態４における検索キーワードと変換キーワードとの組み合わせの一例を示す図。
【発明を実施するための形態】
【００１３】
実施の形態１．
暗号化した検索キーワードを用いてデータ検索を行う秘匿検索システムの形態であって、暗号化した検索キーワードが頻度分析されてしまうことを防ぐ秘匿検索システムの形態ついて説明する。
【００１４】
図１は、実施の形態１における秘匿検索システム１００の構成図である。
実施の形態１における秘匿検索システム１００の概要について、図１に基づいて説明する。
【００１５】
秘匿検索システム１００（検索システムの一例）は情報処理装置２００、サーバ装置３００（検索装置の一例）、変換規則管理装置４００（対応キーワード管理装置の一例）およびデータ登録装置５００（暗号化データ生成装置の一例）を備え、各装置はネットワーク１０１を介して通信を行う。
【００１６】
（１）変換規則管理装置４００は、検索キーワードと変換キーワード群とを対応付けた変換規則テーブルを生成する（変換規則生成処理）。
（２）データ登録装置５００は、検索データを暗号化した暗号化データと変換キーワードを暗号化した暗号化キーワードとを対応付けた登録データを変換規則テーブルに基づいて生成する。そして、データ登録装置５００は、登録データをサーバ装置３００に登録する（データ登録処理）。
（３）情報処理装置２００は、利用者に指定された検索キーワードに対応する変換キーワード群を変換規則テーブルから取得し、取得した変換キーワード群を暗号化して暗号化キーワード群を生成する。そして、情報処理装置２００は、暗号化キーワード群を指定してサーバ装置３００にデータ検索を要求する（検索要求処理）。
（４）サーバ装置３００は、情報処理装置２００により指定された暗号化キーワード群に含まれる暗号化キーワードを検索キーとして検索キーに対応する暗号化データを検索する。そして、サーバ装置３００は、検索した暗号化データを情報処理装置２００へ応答する（検索処理）。
（５）情報処理装置２００は、サーバ装置３００により検索された暗号化データを復号し、復号して得られた検索データを検索結果として出力する（検索結果出力処理）。
【００１７】
以下に、秘匿検索システム１００の詳細について説明する。
【００１８】
図２は、実施の形態１における情報処理装置２００の機能構成図である。
実施の形態１における情報処理装置２００の機能構成について、図２に基づいて説明する。
【００１９】
情報処理装置２００は、検索キーワード入力部２１０、変換キーワード群取得部２２０、暗号化キーワード群生成部２３０、検索要求部２４０、検索結果出力部２５０、処理装置通信部２８０および処理装置記憶部２９０を備える。
【００２０】
処理装置記憶部２９０（対応キーワード記憶部の一例）は、情報処理装置２００で使用するデータを記憶する。
変換規則テーブル２９１、暗号鍵データ２９２または復号鍵データ２９３は、処理装置記憶部２９０に記憶されるデータの一例である。
変換規則テーブル２９１（対応キーワードデータの一例）は、検索キーワードと１以上の変換キーワード（対応キーワード）とを対応させた変換キーワード群を定義するデータである。例えば、変換規則テーブル２９１は、複数の検索キーワードを定義すると共に検索キーワード毎に１以上の変換キーワードを変換キーワード群として定義するデータである。
【００２１】
検索キーワード入力部２１０は、検索キーワードを入力する（検索キーワード入力処理）。
【００２２】
変換キーワード群取得部２２０（対応キーワード群取得部の一例）は、検索キーワード入力部２１０により入力された検索キーワードに対応する変換キーワード群を処理装置記憶部２９０に記憶された変換規則テーブル２９１から取得する（対応キーワード群取得処理）。
【００２３】
暗号化キーワード群生成部２３０は、変換キーワード群取得部２２０によって取得された変換キーワード群に含まれる変換キーワードを暗号鍵データ２９２を用いて暗号化して暗号化キーワード群を生成する（暗号化キーワード群生成処理）。
【００２４】
検索要求部２４０（検索要求データ送信部、検索応答データ受信部の一例）は、暗号化キーワード群生成部２３０によって生成された暗号化キーワード群を含む検索要求データを処理装置通信部２８０を介してサーバ装置３００へ送信する（検索要求データ送信処理）。
検索要求部２４０は、サーバ装置３００から送信される検索応答データを受信する（検索応答データ受信処理）。
【００２５】
検索結果出力部２５０は、検索要求部２４０によって受信された検索応答データに含まれる暗号化データを復号鍵データ２９３を用いて復号し、復号して得られる検索データを検索結果として出力する（検索結果出力処理）。
【００２６】
処理装置通信部２８０はデータ通信を行う。
例えば、処理装置通信部２８０は検索要求データをサーバ装置３００へ送信し、サーバ装置３００から検索応答データを受信する。
また、処理装置通信部２８０は変換規則管理装置４００から変換規則テーブル２９１を受信し、受信した変換規則テーブル２９１を処理装置記憶部２９０に記憶する。
【００２７】
図３は、実施の形態１におけるサーバ装置３００の機能構成図である。
実施の形態１におけるサーバ装置３００の機能構成について、図３に基づいて説明する。
【００２８】
サーバ装置３００は、サーバ装置通信部３１０、データ検索部３２０、データ登録部３３０およびサーバ装置記憶部３９０を備える。
【００２９】
サーバ装置記憶部３９０（暗号化データ記憶部の一例）は、サーバ装置３００で使用するデータを記憶する。
登録データテーブル３９１は、サーバ装置記憶部３９０に記憶されるデータの一例である。
登録データテーブル３９１は、検索データを暗号化した暗号化データと変換キーワードを暗号化した暗号化キーワードとを対応付けたデータである。例えば、登録データテーブル３９１は、検索データ毎に当該検索データを暗号化した暗号化データと特定の変換キーワードを暗号化した暗号化キーワードとを対応付けたデータである。
【００３０】
サーバ装置通信部３１０（検索要求データ受信部、検索応答データ送信部の一例）は、データ通信を行う。
例えば、サーバ装置通信部３１０は、情報処理装置２００から送信される検索要求データを受信する（検索要求データ受信処理）。
また、サーバ装置通信部３１０は、データ検索部３２０によって取得される暗号化データを含む検索応答データを送信する（検索応答データ送信処理）。
また、サーバ装置通信部３１０は、データ登録装置５００から送信される登録要求データを受信する（登録要求データ受信処理）。
【００３１】
データ検索部３２０は、サーバ装置通信部３１０によって受信された検索要求データに基づいて、検索要求データ内の暗号化キーワード群に含まれる暗号化キーワードを検索キーとして検索キーに対応する暗号化データを登録データテーブル３９１から取得する（データ検索処理）。
【００３２】
データ登録部３３０は、サーバ装置通信部３１０によって受信される登録要求データに含まれる登録データ（暗号化データ、暗号化キーワード）を登録データテーブル３９１に設定する（データ登録処理）。
【００３３】
図４は、実施の形態１における変換規則管理装置４００の機能構成図である。
実施の形態１における変換規則管理装置４００の機能構成について、図４に基づいて説明する。
【００３４】
変換規則管理装置４００（対応キーワード管理装置）は、変換規則算出部４１０、変換キーワード群生成部４２０、変換規則生成部４３０、管理装置通信部４４０および管理装置記憶部４９０を備える。
【００３５】
管理装置記憶部４９０は、変換規則管理装置４００で使用するデータを記憶する。
検索キーワードテーブル４９１は、管理装置記憶部４９０に記憶されるデータの一例である。
検索キーワードテーブル４９１（出現頻度データの一例）は、検索キーワードを定義すると共に特定の検索キーワードに対応付けられる検索データの割合を特定の検索キーワードの出現頻度として定義するデータである。
【００３６】
変換規則算出部４１０（対応キーワード数算出部の一例）は、検索キーワードテーブル４９１に定義された検索キーワードの出現頻度に応じて、検索キーワードに対応付ける変換キーワードの個数を変換キーワード数として算出する（対応キーワード数算出処理）。
変換規則算出部４１０は、検索キーワードテーブル４９１に定義された検索キーワードの出現頻度に基づいて、検索キーワードの対応キーワード毎に検索キーワードの対応キーワード群から当該対応キーワードを選択する割合を変換確率（対応キーワード選択率）として算出する（対応キーワード選択率算出処理）。
【００３７】
例えば、変換規則算出部４１０は、以下のように変換キーワード数と変換確率とを算出する。
【００３８】
変換規則算出部４１０は、各検索キーワードの変換キーワード数で分割した分割後の各検索キーワードの出現頻度が等しくなるように各検索キーワードの変換キーワード数を算出する。
【００３９】
変換規則算出部４１０は、各検索キーワードの出現頻度の最大公約数を算出し、検索キーワード毎に検索キーワードの出現頻度を最大公約数で除算した値を検索キーワードの変換キーワード数として算出する。
【００４０】
変換規則算出部４１０は、検索キーワード毎に変換キーワード数の逆数を変換確率として算出する。
【００４１】
変換キーワード群生成部４２０（対応キーワード群生成部の一例）は、変換規則算出部４１０によって算出された変換キーワード数と同じ個数の変換キーワードを変換キーワード群として生成する（対応キーワード群生成処理）。
【００４２】
変換規則生成部４３０（対応キーワードデータ生成部の一例）は、検索キーワードと変換キーワード群と変換確率とを対応付けて変換規則テーブル２９１（対応キーワードデータ、対応キーワード選択率データの一例）を生成する（対応キーワードデータ生成処理）。
【００４３】
管理装置通信部４４０はデータ通信を行う。
例えば、管理装置通信部４４０は、変換規則生成部４３０によって生成された変換規則テーブル２９１を情報処理装置２００およびデータ登録装置５００へ送信する。
【００４４】
図５は、実施の形態１におけるデータ登録装置５００の機能構成図である。
実施の形態１におけるデータ登録装置５００の機能構成について、図５に基づいて説明する。
【００４５】
データ登録装置５００（暗号化データ生成装置の一例）は、登録装置入力部５１０、キーワード変換部５２０、登録データ生成部５３０、登録要求部５４０、登録装置通信部５８０および登録装置記憶部５９０を備える。
【００４６】
登録装置記憶部５９０（検索データ記憶部、キーワード選択率記憶部の一例）は、データ登録装置５００で使用するデータを記憶する。
検索データテーブル５９１、変換規則テーブル２９１または暗号鍵データ２９２は、登録装置記憶部５９０に記憶されるデータの一例である。
検索データテーブル５９１は、検索データと検索キーワードとを対応付けたデータである。
【００４７】
キーワード変換部５２０（対応キーワード選択部の一例）は、検索データテーブル５９１に含まれる検索キーワード毎に検索キーワードに対応する変換キーワード群を変換規則テーブル２９１から取得する。
キーワード変換部５２０は、取得した変換キーワード群に含まれる少なくともいずれかの変換キーワードを変換規則テーブル２９１に含まれる変換確率に応じて選択する（対応キーワード選択処理）。
【００４８】
登録データ生成部５３０（暗号化データ生成部の一例）は、検索データテーブル５９１に含まれる検索データ毎に検索データを暗号鍵データ２９２を用いて暗号化して暗号化データを生成する（暗号化データ生成処理）。
登録データ生成部５３０は、キーワード変換部５２０によって選択された変換キーワードを暗号鍵データ２９２を用いて暗号化して暗号化キーワードを生成する（暗号化キーワード生成処理）。
【００４９】
登録要求部５４０は、登録データ生成部５３０によって生成された暗号化データと暗号化キーワードとを対応付けて設定した登録要求データを登録装置通信部５８０を介してサーバ装置３００へ送信する（登録要求処理）。
【００５０】
登録装置通信部５８０はデータ通信を行う。
例えば、登録装置通信部５８０は、登録要求データをサーバ装置３００へ送信する。
【００５１】
図６は、実施の形態１における変換規則管理装置４００の変換規則管理方法を示すフローチャートである。
実施の形態１における変換規則管理装置４００の変換規則管理方法について、図６に基づいて説明する。
【００５２】
まず、変換規則管理装置４００の変換規則管理方法の概要について説明する。
【００５３】
変換規則算出部４１０は、検索キーワードの出現頻度に基づいて変換キーワード数と各変換キーワードの変換確率を算出する（Ｓ１１０）。
変換キーワード群生成部４２０は、変換キーワード数と同じ数の変換キーワード（変換キーワード群）を生成する（Ｓ１２０）。
変換規則生成部４３０は、検索キーワードと変換キーワード群と各変換キーワードの変換確率とを対応付けて変換規則テーブル２９１を生成する（Ｓ１３０）。
管理装置通信部４４０は、変換規則テーブル２９１を情報処理装置２００およびデータ登録装置５００へ送信する（Ｓ１４０）。
【００５４】
次に、変換規則管理装置４００の変換規則管理方法の詳細について説明する。
【００５５】
Ｓ１１０において、変換規則算出部４１０は、管理装置記憶部４９０から検索キーワードテーブル４９１を取得する。検索キーワードテーブル４９１は管理装置記憶部４９０に予め記憶しておく。
【００５６】
図７は、実施の形態１における検索キーワードテーブル４９１を示す図である。
図７に示すように、検索キーワードテーブル４９１は検索キーワードと出現頻度とを対応付けたデータである。
出現頻度は、対応する検索キーワードを検索キーとして用いる検索データの割合を意味する。例えば、１００個の検索データのうち２５個の検索データで検索キーワード「Ａ社」が検索キーとして用いられる場合、検索キーワード「Ａ社」の出現頻度は「２５％（＝２５／１００）」である。
【００５７】
図６に戻り、Ｓ１１０の説明を続ける。
【００５８】
Ｓ１１０において、変換規則算出部４１０は、検索キーワードテーブル４９１に基づいて、各検索キーワードの分割後の出現頻度が均等になるような頻度分割数を「変換キーワード数」として算出する。
さらに、変換規則算出部４１０は、変換キーワード数の逆数を「変換確率」として算出する。
【００５９】
例えば、図７に示す検索キーワードテーブル４９１は検索キーワード「Ａ社」の出現頻度を「２５％」、検索キーワード「Ｂ社」の出現頻度を「１５％」、その他の検索キーワードの出現頻度を「５％」と定義している。
この場合、検索キーワード「Ａ社」の出現頻度「２５％」を５分割し、検索キーワード「Ｂ社」の出現頻度「１５％」を３分割すれば、分割後の全ての出現頻度は均等な値「５％」になる。
そこで、変換規則算出部４１０は、検索キーワード「Ａ社」の変換キーワード数として頻度分割数「５」、検索キーワード「Ｂ社」の変換キーワード数として頻度分割数「３」、その他の検索キーワードの変換キーワード数として頻度分割数「１」を算出する。
また、変換規則算出部４１０は、検索キーワード「Ａ社」の変換確率「１／５」、検索キーワード「Ｂ社」の変換確率「１／３」、その他の検索キーワードの変換確率「１／１」を算出する。
【００６０】
例えば、変換規則算出部４１０は、出現頻度の最大公約数を用いて変換キーワード数と変換確率とを算出する。
【００６１】
図８は、実施の形態１における変換規則算出処理（Ｓ１１０）の一例を示すフローチャートである。
出現頻度の最大公約数を用いて変換キーワード数と変換確率とを算出する変換規則算出処理（Ｓ１１０）について、図８に基づいて説明する。
【００６２】
Ｓ１１１において、変換規則算出部４１０は、検索キーワードテーブル４９１に設定されている各検索キーワードの出現頻度に基づいて、出現頻度の最大公約数を算出する。
例えば、図７に示した検索キーワードテーブル４９１の場合、出現頻度の最大公約数は「５％」である。
Ｓ１１１の後、Ｓ１１２に進む。
【００６３】
Ｓ１１２において、変換規則算出部４１０は、検索キーワード毎に出現頻度を最大公約数で除算する。そして、除算して得られる値が変換キーワード数である。
例えば、図７の場合、検索キーワード「Ａ社」の変換キーワード数は、出現頻度「２５％」を最大公約数「５％」で除算した値「５（＝２５％÷５％）」である。
Ｓ１１２の後、Ｓ１１３に進む。
【００６４】
Ｓ１１３において、変換規則算出部４１０は、検索キーワード数毎に変換キーワード数の逆数を変換確率として算出する。
例えば、図７の場合、検索キーワード「Ａ社」の変換確率は、変換キーワード数「５」の逆数「１／５」である。
Ｓ１１３により、変換規則算出処理（Ｓ１１０）は終了する。
【００６５】
図６に戻り、変換規則管理方法の説明を続ける。
【００６６】
Ｓ１１０の後、Ｓ１２０に進む。
【００６７】
Ｓ１２０において、変換キーワード群生成部４２０は、検索キーワード毎に変換キーワード数と同じ数の変換キーワードを生成する。以下、変換キーワード数と同じ数の変換キーワードを「変換キーワード群」という。
例えば、検索キーワード「Ａ社」の変換キーワード数が「５」である場合、変換キーワード群生成部４２０は、検索キーワード「Ａ社」の語尾に連番を付して変換キーワード群「Ａ社−１」「Ａ社−２」「Ａ社−３」「Ａ社−４」「Ａ社−５」を生成する。
但し、変換キーワードは検索キーワードを含んでいなくてもよい。例えば、ランダムに選択した文字、数値、記号などを組み合わせたキーワードを変換キーワードにしてもよい。また、変換キーワードを生成するために一方向性関数を用いても構わない。
Ｓ１２０の後、Ｓ１３０に進む。
【００６８】
Ｓ１３０において、変換規則生成部４３０は、検索キーワードテーブル４９１に設定されている検索キーワードと、Ｓ１１０で算出された変換確率と、Ｓ１２０で生成された変換キーワード群とを対応付けて変換規則テーブル２９１を生成する。
【００６９】
図９は、実施の形態１における変換規則テーブル２９１を示す図である。
図９に示すように、変換規則テーブル２９１は、検索キーワードと変換確率と変換キーワードとを対応付けたデータである。
図９に示す変換規則テーブル２９１は、図７に示した検索キーワードテーブル４９１に基づいて生成される変換規則テーブル２９１である。つまり、各変換キーワードの出現頻度は、図７で説明したように均等な値「５％」である。
【００７０】
図６に戻り、変換規則管理方法の説明を続ける。
【００７１】
Ｓ１３０の後、Ｓ１４０に進む。
【００７２】
Ｓ１４０において、管理装置通信部４４０は、Ｓ１３０で生成された変換規則テーブル２９１を情報処理装置２００およびデータ登録装置５００へ送信する。
情報処理装置２００の処理装置通信部２８０は変換規則テーブル２９１を受信し、受信した変換規則テーブル２９１を処理装置記憶部２９０に記憶する。
また、データ登録装置５００の登録装置通信部５８０は変換規則テーブル２９１を受信し、受信した変換規則テーブル２９１を登録装置記憶部５９０に記憶する。
Ｓ１４０により、変換規則管理方法の処理は終了する。
【００７３】
図１０は、実施の形態１におけるデータ登録装置５００のデータ登録方法を示すフローチャートである。
実施の形態１におけるデータ登録装置５００のデータ登録方法について、図１０に基づいて説明する。
【００７４】
まず、データ登録装置５００のデータ登録方法の概要について説明する。
【００７５】
登録装置入力部５１０は、検索データと検索キーワードとを入力する（Ｓ２１０）。
キーワード変換部５２０は、変換規則テーブル２９１から入力キーワードに対応する変換キーワードを選択する（Ｓ２２０）。
登録データ生成部５３０は、入力データと選択キーワードとを暗号化して登録データを生成する（Ｓ２３０）。
登録要求部５４０は、登録データを含んだ登録要求データをサーバ装置３００へ送信する（Ｓ２４０）。
【００７６】
次に、データ登録装置５００のデータ登録方法の詳細について説明する。
【００７７】
Ｓ２１０において、管理者は、キーボードやマウスなどの入力装置を用いて検索データと検索キーワードとの組み合わせをデータ登録装置５００に指定する。年齢などの数値、性別などの属性、氏名などの文字列、文書などのファイルは検索データの一例である。
登録装置入力部５１０は、管理者から指定された検索データと検索キーワードとの組み合わせを入力装置から入力する。
但し、検索データと検索キーワードとの複数の組み合わせを登録装置記憶部５９０に予め記憶しておき、登録装置入力部５１０が登録装置記憶部５９０から検索データと検索キーワードとの組み合わせを一つずつ入力してもよい。
以下、Ｓ２１０で入力した検索データと検索キーワードとをそれぞれ「入力データ」「入力キーワード」という。
Ｓ２１０の後、Ｓ２２０に進む。
【００７８】
Ｓ２２０において、キーワード変換部５２０は、登録装置記憶部５９０から変換規則テーブル２９１（図９参照）を取得する。
キーワード変換部５２０は、入力キーワードと同じ検索キーワードに対応する変換キーワード群を変換規則テーブル２９１から取得する。
キーワード変換部５２０は、取得した変換キーワード群からいずれかの変換キーワードをランダムに選択する。但し、各変換キーワードを選択する選択確率は、変換規則テーブル２９１に設定されている変換確率に従う。
以下、Ｓ２２０で選択した変換キーワードを「選択キーワード」という。
【００７９】
例えば、図９に示した変換規則テーブル２９１の場合、入力キーワード「Ａ社」に対して変換キーワード「Ａ社−１」「Ａ社−２」「Ａ社−３」「Ａ社−４」または「Ａ社−５」が選択される。各変換キーワードを選択する確率（変換確率）は「１／５」である。
つまり、１００個の入力キーワード「Ａ社」がある場合、「Ａ社−１」「Ａ社−２」「Ａ社−３」「Ａ社−４」および「Ａ社−５」はそれぞれ２０回程度ずつ選択される。
【００８０】
Ｓ２２０の後、Ｓ２３０に進む。
【００８１】
Ｓ２３０において、登録データ生成部５３０は、登録装置記憶部５９０から暗号鍵データ２９２を取得する。暗号鍵データ２９２は所定の鍵生成アルゴリズムによって生成し、登録装置記憶部５９０に予め記憶しておく。
登録データ生成部５３０は、入力データを暗号鍵データ２９２を用いて所定の暗号化アルゴリズムで暗号化する。以下、暗号化した入力データを「暗号化データ」という。
登録データ生成部５３０は、選択キーワードを暗号鍵データ２９２を用いて所定の暗号化アルゴリズム（確定的暗号）で暗号化する。以下、暗号化した選択キーワードを「暗号化キーワード」という。
但し、入力データの暗号化に用いる暗号鍵データと異なる暗号鍵データを選択キーワードの暗号化に用いても構わない。また、入力データの暗号化に用いる暗号化アルゴリズムと異なる暗号化アルゴリズムを選択キーワードの暗号化に用いても構わない。
以下、暗号化データと暗号化キーワードとの組み合わせを「登録データ」という。
Ｓ２３０の後、Ｓ２４０に進む。
【００８２】
Ｓ２４０において、登録要求部５４０は、Ｓ２３０で生成された登録データを含んだ登録要求データを生成し、生成した登録要求データを登録装置通信部５８０を介してサーバ装置３００へ送信する。但し、登録要求部５４０は、複数の登録データを含んだ登録要求データをサーバ装置３００へ送信しても構わない。
サーバ装置３００のサーバ装置通信部３１０は登録要求データを受信し、受信した登録要求データに含まれる登録データを登録データテーブル３９１に登録（設定）する。
Ｓ２４０により、データ登録方法の処理は終了する。
【００８３】
図１１は、実施の形態１における登録データテーブル３９１を示す図である。
図１１に示すように、登録データテーブル３９１（データベースともいう）は暗号化キーワードと暗号化データとの組み合わせ（登録データ）を複数含んだデータである。つまり、登録データテーブル３９１は暗号化キーワードと暗号化データとを対応付けたデータである。
「Ｅ（ｘ）」は、「ｘ」を暗号化したデータを表している。
【００８４】
前述の通り、各変換キーワードは変換規則テーブル２９１に定義された均等な変換確率で選択される（図１０、Ｓ２２０）。
このため、登録データテーブル３９１に登録された登録データの数が十分に多い場合、登録データテーブル３９１に含まれる各暗号化キーワードの数はほぼ均等である。
【００８５】
暗号化キーワードと暗号化データとを異なるテーブルまたは記憶装置に分けて記憶しても構わない。例えば、暗号化キーワードと暗号化データのデータＩＤとを対応付けたテーブルと、データＩＤと暗号化データとを対応付けたテーブルとを用意すればよい。
【００８６】
図１２は、実施の形態１における暗号化キーワードの登録頻度を示す図である。
例えば、図９に示した変換規則テーブル２９１に基づいて変換キーワードを選択し、選択した変換キーワードを暗号化した場合、登録データテーブル３９１に登録される各暗号化キーワードの割合（登録頻度）は「５％」で均等化される（図１２参照）。
【００８７】
したがって、サーバ装置３００に記憶される登録データテーブル３９１に基づいて暗号化キーワードを頻度分析しても、暗号化キーワードから検索キーワードを推測することはできない。暗号化キーワードに登録頻度の差がほとんど無いためである。
【００８８】
図１３は、実施の形態１における情報処理装置２００の検索方法を示すフローチャートである。
実施の形態１における情報処理装置２００の検索方法について、図１３に基づいて説明する。
【００８９】
まず、情報処理装置２００の検索方法の概要について説明する。
【００９０】
検索キーワード入力部２１０は、検索キーワードを入力する（Ｓ３１０）。
変換キーワード群取得部２２０は、入力キーワードに対応する変換キーワード群を変換規則テーブル２９１から取得する（Ｓ３２０）。
暗号化キーワード群生成部２３０は、変換キーワード群を暗号化して暗号化キーワード群を生成する（Ｓ３３０）。
検索要求部２４０は、暗号化キーワード群を含んだ検索要求データをサーバ装置３００へ送信する（Ｓ３４０）。
検索要求部２４０は、暗号化データを含んだ検索応答データをサーバ装置３００から受信する（Ｓ３５０）。
検索結果出力部２５０は、検索応答データに含まれる暗号化データを復号し、復号して得られた検索データを検索結果として出力する（Ｓ３６０）。
【００９１】
次に、情報処理装置２００の検索方法の詳細について説明する。
【００９２】
Ｓ３１０において、利用者は、キーボードやマウスなどの入力装置を用いて検索キーワードを情報処理装置２００に指定する。
検索キーワード入力部２１０は、利用者に指定された検索キーワードを入力装置から入力する。
以下、Ｓ３１０で入力した検索キーワードを「入力キーワード」という。
Ｓ３１０の後、Ｓ３２０に進む。
【００９３】
Ｓ３２０において、変換キーワード群取得部２２０は、処理装置記憶部２９０に記憶されている変換規則テーブル２９１から入力キーワードに対応する変換キーワード群を取得する。
例えば、変換キーワード群取得部２２０は、図９に示す変換規則テーブル２９１から入力キーワード「Ａ社」に対応する変換キーワード群「Ａ社−１」「Ａ社−２」「Ａ社−３」「Ａ社−４」「Ａ社−５」を取得する。
Ｓ３２０の後、Ｓ３３０に進む。
【００９４】
Ｓ３３０において、暗号化キーワード群生成部２３０は、処理装置記憶部２９０から暗号鍵データ２９２を取得する。
暗号化キーワード群生成部２３０は、Ｓ３２０で取得された変換キーワード群に含まれる各変換キーワードを暗号鍵データ２９２を用いて所定の暗号化アルゴリズム（確定的暗号）で暗号化する。
但し、Ｓ３３０で用いる暗号鍵データ２９２および暗号化アルゴリズムは、登録データ生成時（図１０のＳ２３０）に検索キーワードの暗号化で用いる暗号鍵データおよび暗号化アルゴリズムと同じである。
以下、暗号化した変換キーワードを「暗号化キーワード」といい、暗号化キーワードから成るデータを「暗号化キーワード群」という。
Ｓ３３０の後、Ｓ３４０に進む。
【００９５】
Ｓ３４０において、検索要求部２４０は、Ｓ３３０で生成された暗号化キーワード群を含んだ検索要求データを生成し、生成した検索要求データを処理装置通信部２８０を介してサーバ装置３００へ送信する。
例えば、図９に示した変換規則テーブル２９１の場合、入力キーワード「Ａ社」に対する検索要求データには、暗号化キーワード群「Ｅ（Ａ社−１）」「Ｅ（Ａ社−２）」「Ｅ（Ａ社−３）」「Ｅ（Ａ社−４）」「Ｅ（Ａ社−５）」が含まれる。
Ｓ３４０の後、Ｓ３５０に進む。
【００９６】
Ｓ３５０において、サーバ装置３００は、検索要求データに基づいて暗号化データを検索し、検索でヒットした１つまたは複数の暗号化データを含んだ検索応答データを情報処理装置２００へ送信する。
検索要求部２４０は、サーバ装置３００から送信された検索応答データを処理装置通信部２８０を介して受信する。
Ｓ３５０の後、Ｓ３６０に進む。
【００９７】
Ｓ３６０において、検索結果出力部２５０は、処理装置記憶部２９０から復号鍵データ２９３を取得する。
検索結果出力部２５０は、検索応答データに含まれる各暗号化データを復号鍵データ２９３を用いて所定の復号アルゴリズムで復号する。
検索結果出力部２５０は、復号して得られる各検索データを入力キーワードに対する検索結果として出力する。例えば、検索結果出力部２５０は、検索結果を表示装置に表示する。
但し、Ｓ３６０で用いる復号鍵データ２９３は検索データの暗号化時（図１０のＳ２３０）に用いる暗号鍵データと対になるデータであり、Ｓ３６０で用いる復号アルゴリズムは検索データの暗号化時に用いる暗号化アルゴリズムと対になるアルゴリズムである。
Ｓ３６０により、情報処理装置２００の検索方法の処理は終了する。
【００９８】
図１４は、実施の形態１におけるサーバ装置３００の検索方法を示すフローチャートである。
実施の形態１におけるサーバ装置３００の検索方法について、図１４に基づいて説明する。
【００９９】
まず、サーバ装置３００の検索方法の概要について説明する。
【０１００】
サーバ装置通信部３１０は、検索要求キーワード群を含んだ検索要求データを受信する（Ｓ４１０）。
データ検索部３２０は、検索要求キーワード群内の検索要求キーワードに対応付けられた暗号化データを登録データテーブル３９１から取得する（Ｓ４２０）。
サーバ装置通信部３１０は、暗号化データを含んだ検索応答データを情報処理装置２００へ送信する（Ｓ４３０）。
【０１０１】
次に、サーバ装置３００の検索方法の詳細について説明する。
【０１０２】
Ｓ４１０において、サーバ装置通信部３１０は、情報処理装置２００から送信される検索要求データを受信する。
以下、検索要求データに含まれる暗号化キーワード群（暗号化キーワード）を「検索要求キーワード群（検索要求キーワード）」という。
Ｓ４１０の後、Ｓ４２０に進む。
【０１０３】
Ｓ４２０において、データ検索部３２０は、検索要求キーワード群に含まれる各検索要求キーワードを検索キーとして登録データテーブル３９１（図１１参照）を検索する。つまり、データ検索部３２０は、登録データテーブル３９１を検索し、少なくともいずれかの検索要求キーワードと一致する暗号化キーワードを特定する（ＯＲ検索）。
ここで、検索キーと一致する暗号化キーワードを「対象キーワード」という。
【０１０４】
そして、データ検索部３２０は、各対象キーワードに対応付けられている暗号化データを登録データテーブル３９１から取得する。
【０１０５】
例えば、図１１に示した登録データテーブル３９１の場合、データ検索部３２０は、検索要求キーワード群「Ｅ（Ａ社−１）」「Ｅ（Ａ社−２）」「Ｅ（Ａ社−３）」「Ｅ（Ａ社−４）」「Ｅ（Ａ社−５）」に対して暗号化データ「Ｅ（データａ）」「Ｅ（データｂ）」および「Ｅ（データｄ）」を取得する。
【０１０６】
従来の検索技術（例えば、ハッシュテーブルを用いる技術）を用いて検索処理（Ｓ４２０）を高速化してもよい。
【０１０７】
Ｓ４２０の後、Ｓ４３０に進む。
【０１０８】
Ｓ４３０において、データ検索部３２０は、Ｓ４２０で取得した各暗号化データを含んだ検索応答データを生成する。
そして、サーバ装置通信部３１０は、データ検索部３２０によって生成された検索応答データを情報処理装置２００へ送信する。
Ｓ４３０により、サーバ装置３００の検索方法は終了する。
【０１０９】
図１５は、実施の形態１における秘匿検索システム１００のハードウェア資源の一例を示す図である。
図１５において、情報処理装置２００、サーバ装置３００、変換規則管理装置４００およびデータ登録装置５００は、ＣＰＵ９０１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を備えている。ＣＰＵ９０１は、バス９０２を介してＲＯＭ９０３、ＲＡＭ９０４、通信ボード９０５、ディスプレイ装置９１１、キーボード９１２、マウス９１３、ドライブ装置９１４、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。ドライブ装置９１４は、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）などの記憶媒体を読み書きする装置である。
【０１１０】
通信ボード９０５は、有線または無線で、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネット、電話回線などの通信網に接続している。
【０１１１】
磁気ディスク装置９２０には、ＯＳ９２１（オペレーティングシステム）、プログラム群９２２、ファイル群９２３が記憶されている。
【０１１２】
プログラム群９２２には、実施の形態において「〜部」として説明する機能を実行するプログラムが含まれる。プログラムは、ＣＰＵ９０１により読み出され実行される。すなわち、プログラムは、「〜部」としてコンピュータを機能させるものであり、また「〜部」の手順や方法をコンピュータに実行させるものである。
【０１１３】
ファイル群９２３には、実施の形態において説明する「〜部」で使用される各種データ（入力、出力、判定結果、計算結果、処理結果など）が含まれる。
【０１１４】
実施の形態において構成図およびフローチャートに含まれている矢印は主としてデータや信号の入出力を示す。
【０１１５】
実施の形態において「〜部」として説明するものは「〜回路」、「〜装置」、「〜機器」であってもよく、また「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明するものは、ファームウェア、ソフトウェア、ハードウェアまたはこれらの組み合わせのいずれで実装されても構わない。
【０１１６】
実施の形態１において、例えば、以下のような秘匿検索システム１００について説明した。
【０１１７】
情報処理装置２００は、データ・キーワードをサーバ装置３００に対して秘匿したまま検索を行う。
確率的暗号ではなく確定的暗号を利用するため、検索時にはバイナリデータの完全一致検索を行えば良い。これにより、既存の検索技術を利用した高速化が可能である。
確定的暗号とは、平文データと暗号化データとが一対一に対応する暗号方式である。つまり、暗号化データは平文データによって一意に定まる。
確率的暗号とは、平文データに対応する暗号化データが複数有る暗号方式である。暗号化データは平文データによって一意に定まらない。
【０１１８】
秘匿検索システム１００では特許文献１のようにダミーデータが不要である。したがって、記憶領域の面で効率的である。
【０１１９】
変換規則テーブル２９１は、与えられたキーワード（例えば、暗号化キーワード）の頻度情報（出現頻度、登録頻度）に対して、攻撃者による頻度分析への耐性を持たせることを目的として生成する。
変換規則テーブル２９１を暗号化して秘匿性を高めてもよい。
【０１２０】
情報処理装置２００、サーバ装置３００、変換規則管理装置４００またはデータ登録装置５００を統合または分割しても構わない。
例えば、情報処理装置２００が変換規則管理装置４００またはデータ登録装置５００の機能を備えてもよい。
【０１２１】
暗号化データに対応付ける暗号化キーワードの数は一つであっても複数であっても構わない。暗号化データに複数の暗号化キーワードを対応付ける場合、検索要求キーワード群に全ての暗号化キーワードが含まれる場合、または少なくてもいずれかの暗号化キーワードが含まれる場合に当該暗号化データを検索にヒットしたデータとして扱う。
また、一つの暗号化キーワードに複数の暗号化データを対応付けても構わない。この場合、検索要求キーワード群に当該暗号化キーワードが含まれる場合、全ての暗号化データまたは少なくともいずれかの暗号化データを検索にヒットしたデータとして扱う。
【０１２２】
暗号鍵データ２９２はＩＣカードなどから入力してもよいし、パスワードや生体情報などの利用者情報に基づいて自動生成してもよい。
【０１２３】
実施の形態２．
「ｋ−匿名性」を満たす秘匿検索システム１００の形態について説明する。
以下、実施の形態１と異なる事項について主に説明する。説明を省略する事項については実施の形態１と同様である。
【０１２４】
「ｋ−匿名性」とは、登録頻度が等しい暗号化キーワードの数を「ｋ」個以上にすることにより、暗号化キーワードの頻度分析を困難にする性質である。
【０１２５】
秘匿検索システム１００の装置構成および各装置の機能構成は実施の形態１（図１−５参照）と同じである。
【０１２６】
但し、変換規則管理装置４００の変換規則算出部４１０は、以下のように変換キーワード数と変換確率とを算出する。
変換規則算出部４１０は、所定の匿名数「ｋ」以上の検索キーワードが同じ出現頻度を持つように各検索キーワードの出現頻度を分割する分割数を各検索キーワードの変換キーワード数（対応キーワード数）として算出する。
変換規則算出部４１０は、各検索キーワードの出現頻度を分割する分割割合（後述する分割済み頻度）を各検索キーワードの変換確率（対応キーワード選択率）として算出する。
【０１２７】
例えば、変換規則算出部４１０は、以下のように変換キーワード数と変換確率とを算出する。
変換規則算出部４１０は、各検索キーワードの出現頻度から所定の匿名数「ｋ」番目に大きい出現頻度を演算頻度として選択する。
変換規則算出部４１０は、演算頻度以上の出現頻度から１つ以上の演算頻度を減算する。
変換規則算出部４１０は、減算後の各検索キーワードの出現頻度から匿名数「ｋ」番目に大きい出現頻度を新たな演算頻度として選択する。
変換規則算出部４１０は、新たな演算頻度以上の出現頻度から１つ以上の新たな演算頻度を減算する。
変換規則算出部４１０は、検索キーワード毎に出現頻度から減算した各演算頻度の数を変換キーワード数として算出する。
変換規則算出部４１０は、検索キーワード毎に元の出現頻度に対する各演算頻度の割合を変換確率として算出する。
【０１２８】
図１６は、実施の形態２における変換規則算出処理（Ｓ１１０）のフローチャートである。
実施の形態２における変換規則算出処理（Ｓ１１０）について、図１６に基づいて説明する。
【０１２９】
Ｓ１１１Ｂにおいて、変換規則算出部４１０は、検索キーワードテーブル４９１を含んだ分割済み頻度テーブル４９２を生成する。
【０１３０】
図１７は、実施の形態２における検索キーワードテーブル４９１と分割済み頻度テーブル４９２とを示す図である。
図１７に示すように、検索キーワードテーブル４９１は「検索キーワード」と「出現頻度」とを対応付けたデータである。但し、出現頻度は整数比で表している。
また、分割済み頻度テーブル４９２は、検索キーワードテーブル４９１を含んだデータであり、「検索キーワード」と「出現頻度」と「分割済み頻度」とを対応付けたデータである。
【０１３１】
図１６に戻り、変換規則算出処理（Ｓ１１０）の説明を続ける。
【０１３２】
Ｓ１１１Ｂの後、Ｓ１１２Ｂに進む。
【０１３３】
Ｓ１１２Ｂにおいて、変換規則算出部４１０は、分割済み頻度テーブル４９２からｋ番目に大きい出現頻度を選択する。
ここで、「ｋ」は、「ｋ−匿名性」のパラメータ値として定義された匿名数「ｋ」を意味するものとする。
例えば、「３−匿名性（ｋ＝３）」の場合、変換規則算出部４１０は図１７に示した分割済み頻度テーブル４９２から３番目に大きい出現頻度「２８」を選択する。
以下、Ｓ１１１Ｂで選択した出現頻度を「演算頻度」という。
Ｓ１１２Ｂの後、Ｓ１１３Ｂに進む。
【０１３４】
Ｓ１１３Ｂにおいて、変換規則算出部４１０は、分割済み頻度テーブル４９２から演算頻度以上の出現頻度を選択する。以下、Ｓ１１３Ｂで選択した出現頻度を「対象頻度」という。
変換規則算出部４１０は、対象頻度から演算頻度を減算して対象頻度を更新し、演算頻度を分割済み頻度として設定する。
【０１３５】
図１８は、実施の形態２における変換規則算出処理（Ｓ１１０）の概要図である。
図１８の（１）に示す分割済み頻度テーブル４９２において「３−匿名性（ｋ＝３）」の演算頻度は「２８」であり、対象頻度（２８以上の出現頻度）は「４０」「３５」「２８」である。
変換規則算出部４１０は、図１８の（２）に示すように、対象頻度「４０」から演算頻度「２８」を減算して対象頻度を「１２（＝４０−２８）」に更新する。
また、変換規則算出部４１０は、演算頻度「２８」を分割済み頻度として設定する。
これにより、対象頻度「４０」は、減算後の対象頻度「１２」と分割済み頻度「２８」とに分割される。
【０１３６】
同様に、変換規則算出部４１０は、対象頻度「３５」を減算後の対象頻度「７」と分割済み頻度「２８」とに分割し、対象頻度「２８」を減算後の対象頻度「０」と分割済み頻度「２８」とに分割する。
【０１３７】
但し、対象頻度が演算頻度のｎ倍以上の値である場合（ｎは１以上の整数値）、変換規則算出部４１０は、対象頻度からｎ個の演算頻度を減算して対象頻度を更新し、ｎ個の演算頻度を分割済み頻度として設定する。
例えば、対象頻度が「６０」である場合、変換規則算出部４１０は、対象頻度「６０」から２つの演算頻度「２８」を減算して対象頻度を「４（＝６０−２８−２８）」に更新し、２つの演算頻度「２８」を分割済み頻度として設定する。これにより、対象頻度「６０」は、減算後の対象頻度「４」と２つの分割済み頻度「２８」「２８」とに分割される。
【０１３８】
図１６に戻り、変換規則算出処理（Ｓ１１０）の説明を続ける。
【０１３９】
Ｓ１１３Ｂの後、Ｓ１１４Ｂに進む。
【０１４０】
Ｓ１１４Ｂにおいて、変換規則算出部４１０は、分割済み頻度テーブル４９２に「０」以外の出現頻度が残っているか否かを判定する。
「０」以外の出現頻度が残っている場合（ＹＥＳ）、Ｓ１１５Ｂに進む。
「０」以外の出現頻度が残っていない場合（ＮＯ）、Ｓ１１７Ｂに進む。
【０１４１】
Ｓ１１５Ｂにおいて、変換規則算出部４１０は、分割済み頻度テーブル４９２に「０」以外の出現頻度が「ｋ」個以上残っているか否かを判定する。
「０」以外の出現頻度が「ｋ」個以上残っている場合（ＹＥＳ）、Ｓ１１２Ｂに戻る。例えば、前記図１８の（２）に示す分割済み頻度テーブル４９２には「０」以外の出現頻度が７つ、つまり、３つ（＝ｋ）以上残っている。したがって、処理はＳ１１２Ｂに戻る。
「０」以外の出現頻度が「ｋ」個未満しか残っていない場合（ＮＯ）、Ｓ１１６Ｂに進む。
【０１４２】
Ｓ１１６Ｂにおいて、変換規則算出部４１０は、分割済み頻度テーブル４９２に設定した分割済み頻度をｋ−匿名性を満たすように再分割する。
Ｓ１１６Ｂの処理の詳細については別途説明する。
Ｓ１１６Ｂの後、Ｓ１１７Ｂに進む。
【０１４３】
Ｓ１１７Ｂにおいて、変換規則算出部４１０は、分割済み頻度テーブル４９２に設定された分割済み頻度の数を「変換キーワード数」として算出する。
また、変換規則算出部４１０は、各分割済み頻度の割合を「変換確率」として算出する。
変換キーワード数および変換確率の算出方法の具体例について別途説明する。
Ｓ１１７Ｂにより、変換規則算出処理（Ｓ１１０）は終了する。
【０１４４】
図１９から図２１は、実施の形態２における変換規則算出処理（Ｓ１１０）の概要図である。
図２２は、実施の形態２における変換規則テーブル２９１を示す図である。
Ｓ１１５Ｂにおいて「０」以外の出現頻度が「ｋ」個以上残っていた場合（ＹＥＳ）の処理の具体例について、図１９から図２２に基づいて説明する。
【０１４５】
図１９において、変換規則算出部４１０は、（２）分割済み頻度テーブル４９２から３（＝ｋ）番目に大きい出現頻度「２２」を演算頻度として選択する（Ｓ１１２Ｂ）。
次に、変換規則算出部４１０は、演算頻度「２２」以上の出現頻度「２７」「２３」「２２」「２２」を対象頻度として選択する。そして、変換規則算出部４１０は、対象頻度「２７」を「５」と「２２」とに分割し、対象頻度「２３」を「１」と「２２」とに分割し、対象頻度「２２」を「０」と「２２」とに分割する（Ｓ１１３Ｂ）。
これにより、図１９に示す（３）分割済み頻度テーブル４９２が生成される。
【０１４６】
（３）分割済み頻度テーブル４９２には「０」以外の出現頻度が３つ（＝ｋ）以上残っているため、処理はＳ１１２Ｂに戻る（Ｓ１１４Ｂ−Ｓ１１５Ｂ）。以下に説明を続ける。
【０１４７】
図２０において、変換規則算出部４１０は、（３）分割済み頻度テーブル４９２から３（＝ｋ）番目に大きい出現頻度「７」を演算頻度として選択する（Ｓ１１２Ｂ）。
次に、変換規則算出部４１０は、演算頻度「７」以上の出現頻度「２１」「１２」「７」を対象頻度として選択する。そして、変換規則算出部４１０は、対象頻度「２１」を「０」と３つの「７」とに分割し、対象頻度「１２」を「５」と「７」とに分割し、対象頻度「７」を「０」と「７」とに分割する（Ｓ１１３Ｂ）。
これにより、図２０に示す（４）分割済み頻度テーブル４９２が生成される。
【０１４８】
（４）分割済み頻度テーブル４９２には「０」以外の出現頻度が３つ（＝ｋ）以上残っているため、処理はＳ１１２Ｂに戻る（Ｓ１１４Ｂ−Ｓ１１５Ｂ）。以下に説明を続ける。
【０１４９】
図２１において、変換規則算出部４１０は、（４）分割済み頻度テーブル４９２から３（＝ｋ）番目に大きい出現頻度「１」を演算頻度として選択する（Ｓ１１２Ｂ）。
次に、変換規則算出部４１０は、演算頻度「１」以上の出現頻度「５」「５」「１」を対象頻度として選択する。そして、変換規則算出部４１０は、対象頻度「５」を「０」と５つの「１」とに分割し、対象頻度「１」を「０」と「１」とに分割する（Ｓ１１３Ｂ）。
これにより、図２１に示す（５）分割済み頻度テーブル４９２が生成される。
【０１５０】
（５）分割済み頻度テーブル４９２には「０」以上の出現頻度が存在しないため（Ｓ１１４Ｂ）、変換規則算出部４１０は各検索キーワードの変換キーワード数および変換確率を以下のように算出する（Ｓ１１７Ｂ）。
【０１５１】
（５）分割済み頻度テーブル４９２において、検索キーワード「佐藤」の分割済み頻度は「２８」、「７」および５つの「１」である。
【０１５２】
変換規則算出部４１０は、（５）分割済み頻度テーブル４９２を参照し、検索キーワード「佐藤」の分割済み頻度の個数「７」を検索キーワード「佐藤」の変換キーワード数として算出する。
さらに、変換規則算出部４１０は、検索キーワード「佐藤」の各分割済み頻度の割合「２８／４０」「７／４０」「１／４０」を検索キーワード「佐藤」の各変換キーワードの変換確率として算出する。
【０１５３】
変換規則算出部４１０は、他の検索キーワードの変換キーワード数および変換確率についても同様に求める。
【０１５４】
図２１に示した（５）分割済み頻度テーブル４９２に基づいて変換規則テーブル２９１が生成される。
例えば、変換規則テーブル２９１には検索キーワード「佐藤」に対応付けて変換キーワード数「７」と同じ個数の変換キーワード「佐藤−１〜７」が設定される。
また、変換規則テーブル２９１には、検索キーワード「佐藤」の各変換キーワードに対応付けて変換確率「２８／４０」「７／４０」「１／４０」が設定される。
【０１５５】
図２３は、実施の形態２における暗号化キーワードの登録頻度を示す図である。
例えば、図２２に示した変換規則テーブル２９１に基づいて変換キーワードを選択し、選択した変換キーワードを暗号化した場合、各暗号化キーワードは図２３に示すような登録割合で登録データテーブル３９１に登録される。
【０１５６】
例えば、登録頻度が「２８」である暗号化キーワードとして「Ｅ（佐藤−１）」「Ｅ（鈴木−１）」「Ｅ（高橋−１）」の３（＝ｋ）種類の暗号化キーワードが存在する。このため、これら３つの暗号化キーワードのいずれが検索キーワード「佐藤（または鈴木、高橋）」に対応するデータであるかを特定することはできない。
つまり、「３−匿名性」が保証されるため、暗号化キーワードの頻度分析が困難である。
【０１５７】
同様に、他の登録頻度「２２」「７」「１」についても３（＝ｋ）種類以上の暗号化キーワードに共通している。このため、「３−匿名性」が保証され、暗号化キーワードの頻度分析が困難である。
【０１５８】
図２４は、実施の形態２における検索キーワードテーブル４９１と分割済み頻度テーブル４９２との別例を示す図である。
図２５は、実施の形態２における変換規則算出処理（Ｓ１１０）の再分割処理（Ｓ１１６Ｂ）を示すフローチャートである。
図２６、図２７は、実施の形態２における再分割処理（Ｓ１１６Ｂ）の概要図である。
Ｓ１１５Ｂにおいて「０」以外の出現頻度が「ｋ」個未満しか残っていなかった場合（ＮＯ）の再分割処理（Ｓ１１６Ｂ）について、図２４−図２７に基づいて説明する。
【０１５９】
図２４に示す検索キーワードテーブル４９１に基づいて各検索キーワードの出現頻度をＳ１１２Ｂ−Ｓ１１５Ｂ（図１６参照）で分割した場合、図２４の（１）分割済み頻度テーブル４９２が得られる。
（１）分割済み頻度テーブル４９２に残っている「０」以外の出現頻度「５」の数は２つである。つまり、「０」以外の出現頻度が３つ（＝ｋ）未満しか残っていないため、図２５に示す再分割処理（Ｓ１１６Ｂ）が実行される。
【０１６０】
Ｓ１１６Ｂ−１（図２５参照）において、変換規則算出部４１０は、分割済み頻度テーブル４９２に基づいて同じ値の分割済み頻度から成る分割済み頻度グループ毎に分割済み頻度グループに含まれる分割済み頻度の数を算出する。以下、分割済み頻度グループに含まれる分割済み頻度の数を「グループ内頻度数」という。
図２４に示す（１）分割済み頻度テーブル４９２には、３つの分割済み頻度「２８」から成る「２８」分割済み頻度グループと、４つの分割済み頻度「２２」から成る「２２」分割済み頻度グループと、５つの分割済み頻度「７」から成る「７」分割済み頻度グループとの３つのグループが含まれる。この場合、「２８」分割済み頻度グループのグループ内頻度数は「３」であり、「２２」分割済み頻度グループのグループ内頻度数は「４」であり、「７」分割済み頻度グループのグループ内頻度数は「５」である。
【０１６１】
変換規則算出部４１０は、グループ内頻度数が匿名数「ｋ」より多い分割済み頻度グループを「分割候補グループ」として判定する。「ｋ−匿名性」を満たすためである。
図２４に示す（１）分割済み頻度テーブル４９２の場合、「２２」分割済み頻度グループと「７」分割済み頻度グループとが分割候補グループである。
【０１６２】
変換規則算出部４１０は、最も小さい分割済み頻度から成る分割候補グループを「再分割頻度グループ」として選択する。
図２４に示す（１）分割済み頻度テーブル４９２の場合、「７」分割済み頻度グループが再分割頻度グループである。
但し、変換規則算出部４１０は、最も大きい分割済み頻度から成る分割候補グループを再分割頻度グループとして選択してもよいし、グループ内頻度数が最も多い（または少ない）分割済み頻度グループを再分割頻度グループとして選択してもよいし、各分割候補グループからランダムに再分割頻度グループを選択してもよい。
【０１６３】
変換規則算出部４１０は、再分割頻度グループに含まれる複数の分割済み頻度から出現頻度に戻す分割済み頻度を「再分割頻度」として選択する。
例えば、変換規則算出部４１０は、再分割頻度グループ内の残りの分割済み頻度に対応する検索キーワードの数が匿名数「ｋ」以上になることを条件として再分割頻度を選択する。
図２４に示す（１）分割済み頻度テーブル４９２の場合、変換規則算出部４１０は、検索キーワード「中村」の分割済み頻度「７」を再分割頻度として選択する。
Ｓ１１６Ｂ−１の後、Ｓ１１６Ｂ−２に進む。
【０１６４】
Ｓ１１６Ｂ−２において、変換規則算出部４１０は、再分割頻度を分割元（減算元）の出現頻度に加算して分割元の出現頻度を更新し、再分割頻度を削除する。これにより、再分割頻度が「分割済み頻度」から分割元の「出現頻度」に戻る。
例えば、図２６に示す（１）分割済み頻度テーブル４９２において再分割頻度「７」を出現頻度に戻すと（２）分割済み頻度テーブル４９２が得られる。
Ｓ１１６Ｂ−２の後、Ｓ１１６Ｂ−３に進む。
【０１６５】
Ｓ１１６Ｂ−３において、変換規則算出部４１０は、分割済み頻度テーブル４９２に「０」以外の出現頻度が「ｋ」個以上残っているか否かを判定する。
「０」以外の出現頻度が「ｋ」個以上残っている場合（ＹＥＳ）、Ｓ１１６Ｂ−４に進む。
「０」以外の出現頻度が「ｋ」個未満しか残っていない場合（ＮＯ）、Ｓ１１６Ｂ−１に戻る。
【０１６６】
Ｓ１１６Ｂ−４において、変換規則算出部４１０は、分割済み頻度テーブル４９２に残っている各出現頻度（≠０）を分割するための分割済み頻度の組み合わせを決定し、決定した分割済み頻度の組み合わせで各出現頻度を分割する。
但し、変換規則算出部４１０は、分割済み頻度の組み合わせを構成する全ての分割済み頻度を用いて各出現頻度を分割するものとする。
つまり、各出現頻度は他の出現頻度と同じ分割済み頻度の組み合わせで分割される。これにより「ｋ−匿名性」を満たすことができる。
【０１６７】
図２７に示す（２）分割済み頻度テーブル４９２には出現頻度「５」「５」「７」が残っている。出現頻度「５」「５」「７」はそれぞれ「３」と「２」とを組み合わせて分割することができる。出現頻度「５」「５」「７」を分割済み頻度「３」「２」に分割した場合、（３）分割済み頻度テーブル４９２が得られる。
【０１６８】
例えば、変換規則算出部４１０は、各出現頻度を総当たりで分割（分割の全数探索）して複数の組み合わせ候補を生成し、生成した組み合わせ候補毎に当該組み合わせ候補に従って各出現頻度を分割した場合の分割済み頻度の総数を算出する。そして、変換規則算出部４１０は、分割済み頻度の総数が最も少ない組み合わせ候補を分割済み頻度の組み合わせとして選択し、選択した分割済み頻度の組み合わせで各出現頻度を分割する。この分割済み頻度の組み合わせは変換キーワード数の平均値を最も小さくする組み合わせである。これにより、検索要求データに含まれる検索要求キーワード（暗号化キーワード）の数の平均値を最も小さくすることができる。
例えば、出現頻度「５」「５」「７」は「４」と「１」との組み合わせ、「３」と「１」との組み合わせまたは「２」と「１」との組み合わせでも分割することができる。但し、「３」と「２」との組み合わせで各出現頻度を分割した場合に分割済み頻度の総数が最も少なくなる。したがって、変換規則算出部４１０は、出現頻度「５」「５」「７」を分割済み頻度「３」「２」に分割する。
【０１６９】
但し、変換規則算出部４１０は、組み合わせ候補毎に当該組み合わせ候補に従って各出現頻度を分割した場合の変換キーワード数の最大値を算出し、変換キーワード数の最大値が最も小さい組み合わせ候補を分割済み頻度の組み合わせとして選択してもよい。これにより、検索要求データに含まれる検索要求キーワードの数の最大値を小さくすることができる。
【０１７０】
Ｓ１１６Ｂ−４により、再分割処理（Ｓ１１６Ｂ）は終了する。
【０１７１】
ここで、図１６に示した変換規則算出処理（Ｓ１１０）の補足説明を行う。
Ｓ１１５Ｂ（図１６）において、「０」以外の出現頻度が「ｋ」個以上残っている場合（ＹＥＳ）、図２５で説明した再分割処理（Ｓ１１６Ｂ）と同様の処理を行うことにより分割済み頻度を最適化してもよい。
【０１７２】
図２８−図３０は、実施の形態２における分割済み頻度の最適化を示す図である。
分割済み頻度の具体例について、図２０、図２８−図３０に基づいて説明する。
【０１７３】
図２０において（４）分割済み頻度テーブル４９２に新たに設定した分割済み頻度「７」の数は３つ（＝ｋ）より多い。
このとき、「０」以外の出現頻度「５」「５」「１」が３つ（＝ｋ）以上残っているが、残りの出現頻度「５」「５」「１」の中で３（＝ｋ）番目に大きい出現頻度「１」（演算頻度）は所定の頻度閾値（例えば１）以下である。
そこで、変換規則算出部４１０は、５つの分割済み頻度「７」のうち「３−匿名性」を満たす検索キーワード「中村」の分割済み頻度「７」を出現頻度に戻す。これにより、図２８の（５）分割済み頻度テーブル４９２が得られる。
【０１７４】
変換規則算出部４１０は、残りの出現頻度「７」「５」「５」「１」を分割して分割済み頻度の組み合わせ候補を生成する。但し、各分割済み頻度の組み合わせ候補は「３−匿名性」を満たすものとする。つまり、分割済み頻度の組み合わせ候補を構成する各分割済み頻度が３つ（＝ｋ）以上の検索キーワードに対応付けて設定されるという条件を満たす。
そして、変換規則算出部４１０は、生成した分割済み頻度の組み合わせ候補から分割済み頻度の組み合わせを選択し、選択した分割済み頻度の組み合わせで各出現頻度「７」「５」「５」「１」を分割する。
【０１７５】
変換キーワード数の平均値（分割済み頻度の総数）を最も少なくした分割結果を図２９の（Ａ）分割済み頻度テーブル４９２に示し、変換キーワード数の最大値を最も小さくした分割結果を図２９の（Ｂ）分割済み頻度テーブル４９２に示す。
（Ａ）分割済み頻度テーブル４９２の変換キーワード数の平均値は「２．５」であり、図２１に示した（５）分割済み頻度テーブル４９２の変換キーワード数の平均値「２．８７５」より小さい値である。
（Ｂ）分割済み頻度テーブル４９２の変換キーワード数の最大値は「５」（検索キーワード：佐藤、中村）であり、図２１に示した（５）分割済み頻度テーブル４９２の変換キーワード数の最大値「７」（検索キーワード：佐藤）より小さい値である。
【０１７６】
さらに、変換規則算出部４１０は、複数の「ｋ−匿名性」について分割済み頻度テーブル４９２を生成してもよい。
この場合、変換規則算出部４１０は、生成した分割済み頻度テーブル４９２のうち所定の最適化条件を満たす分割済み頻度テーブル４９２を判定し、所定の最適化条件（例えば、検索キーワード数の平均値または最大値）を満たす分割済み頻度テーブル４９２のうち「ｋ」の値が最も大きい分割済み頻度テーブル４９２を選択する。
【０１７７】
例えば、変換規則算出部４１０は、「３−匿名性」「４−匿名性」「５−匿名性」の分割済み頻度テーブル４９２を生成する。
「３−匿名性」の分割済み頻度テーブル４９２および「４−匿名性」の分割済み頻度テーブル４９２を図３０に示す。「５−匿名性」の分割済み頻度テーブル４９２については図示省略する。
【０１７８】
変換規則算出部４１０は、「３−匿名性」「４−匿名性」「５−匿名性」の検索キーワード数の平均値を算出する。図３０の場合、「３−匿名性」の検索キーワード数の平均値は「２．５」であり、「４−匿名性」の検索キーワード数の平均値は「２．７５」である。また、「５−匿名性」の検索キーワード数の平均値が「３．５」であるものとする。
変換規則算出部４１０は、各検索キーワード数の平均値「２．５」「２．７５」「３．５」を所定の最適化条件値「３．０」と比較する。この場合、「３−匿名性」の検索キーワードの平均値「２．５」および「４−匿名性」の検索キーワードの平均値「２．７５」が最適化条件値「３．０」以下であり、最適化条件を満たす。
そこで、変換規則算出部４１０は、「３−匿名性」の分割済み頻度テーブル４９２と「４−匿名性」の分割済み頻度テーブル４９２とのうち「ｋ」の値が大きい「４−匿名性」の分割済み頻度テーブル４９２を選択する。
【０１７９】
上記したように、変換規則算出部４１０は分割済み頻度テーブル４９２を最適化してもよい。
【０１８０】
変換規則管理装置４００の変換規則管理方法の他の処理（Ｓ１２０−Ｓ１４０）は実施の形態１（図６参照）と同様である。
【０１８１】
また、データ登録装置５００のデータ登録方法、情報処理装置２００の検索方法およびサーバ装置３００の検索方法は、実施の形態１（図１０、１３、１４参照）と同様である。
【０１８２】
実施の形態２において、例えば、以下のような秘匿検索システム１００について説明した。
【０１８３】
秘匿検索システム１００において安全性の指標として「ｋ−匿名性」というものを定義し、この指標に基づいて変換規則管理装置４００が変換規則を生成する。
これにより、検索時に情報処理装置２００がサーバ装置３００に送信する検索要求のサイズを小さくすることができる。
ｋ−匿名性とは、攻撃者がキーワードの頻度分布、変換規則、暗号化キーワードの頻度分布の全ての情報を得たうえで暗号化キーワードからキーワードを推定する場合に、任意の暗号化キーワードに対し、対応し得るキーワードがｋ個以上存在することである。
【０１８４】
秘匿検索システム１００において、情報処理装置２００がデータ・キーワードをサーバ装置３００に対して秘匿したまま検索を行うことができる。
ｋ−匿名性という性質を満たすことで、サーバ装置３００によるキーワードの特定を防ぐことができ、さらに実施の形態１に比べ、検索要求のサイズを小さくすることができる。
例えば、図１７に示した検索キーワードテーブル４９１に基づいて変換規則テーブル２９１を生成した場合、実施の形態１では各変換キーワードの出現頻度を均一にするため検索キーワード「佐藤」に対して出現頻度が「１」である４０個の変換キーワードを設ける必要がある。一方、実施の形態２では図２２に示したように検索キーワード「佐藤」に対して７個の変換キーワードを設ければよい。つまり、実施の形態２の方が変換キーワード数が少ないため、実施の形態２の方が検索要求データのサイズが小さい。
【０１８５】
実施の形態３．
「ｋ−匿名性」を満たす秘匿検索システム１００の形態として実施の形態２と異なる形態について説明する。
以下、実施の形態１−２と異なる事項について主に説明する。説明を省略する事項については実施の形態１−２と同様である。
【０１８６】
秘匿検索システム１００の装置構成および各装置の機能構成は実施の形態１（図１−５参照）と同じである。
【０１８７】
但し、変換規則管理装置４００の変換規則算出部４１０は、以下のように変換キーワード数と変換確率とを算出する。
変換規則算出部４１０は、検索キーワード毎に検索キーワードの出現頻度を所定の基数のべき乗値を用いて複数の出現頻度に分割する。
変換規則算出部４１０は、検索キーワード毎に出現頻度の分割数を変換キーワード数（対応キーワード数）として算出する。
変換規則算出部４１０は、分割前の出現頻度に対する分割済み頻度（分割後の出現頻度）の割合を変換確率（対応キーワード選択率）として算出する。
【０１８８】
また、変換規則算出部４１０は、各検索キーワードの分割済み頻度のうち当該分割済み頻度を持つ検索キーワードの数が所定の匿名数「ｋ」未満である分割済み頻度を基数のべき乗値を用いて分割する。
【０１８９】
図３１は、実施の形態３における変換規則算出処理（Ｓ１１０）のフローチャートである。
図３２、図３３は、実施の形態３における変換規則算出処理（Ｓ１１０）の概要図である。
実施の形態３における変換規則算出処理（Ｓ１１０）について、図３１−３３に基づいて説明する。
【０１９０】
Ｓ１１１Ｃ（図３１参照）において、変換規則算出部４１０は、分割済み頻度テーブル４９２に設定された各出現頻度を所定の基数値「ｐ」を用いてｐ進展開し、各出現頻度を複数の分割済み頻度に分割する。
【０１９１】
図３２において、（１）分割済み頻度テーブル４９２に設定されている各出現頻度は、（２）分割済み頻度テーブル４９２に設定した分割済み頻度のように２進展開することができる。
例えば、検索キーワード「佐藤」の出現頻度「４０」は基数「２（＝ｐ）」を５乗した値「３２」と基数「２」を３乗した値「８」とに分割される。
但し、「２」以外の値（例えば、３や５）を基数とするべき乗値で各出現頻度を分割しても構わない。
【０１９２】
図３１に戻り、変換規則算出処理（Ｓ１１０）の説明を続ける。
【０１９３】
Ｓ１１１Ｃの後、Ｓ１１２Ｃに進む。
【０１９４】
Ｓ１１２Ｃにおいて、変換規則算出部４１０は、分割済み頻度テーブル４９２に基づいて分割済み頻度の値毎に分割済み頻度の個数を算出する。以下、分割済み頻度の個数を「頻度個数」という。
変換規則算出部４１０は、頻度個数が匿名数「ｋ」未満である分割済み頻度が有るか否かを判定する。
頻度個数が匿名数「ｋ」未満である分割済み頻度が有る場合（ＹＥＳ）、Ｓ１１３Ｃに進む。
頻度個数が匿名数「ｋ」未満である分割済み頻度が無い場合（ＮＯ）、Ｓ１１４Ｃに進む。
【０１９５】
図３２の（２）分割済み頻度テーブル４９２の場合、分割済み頻度「３２」の頻度個数は「２」であり、分割済み頻度「１６」の頻度個数は「６」であり、分割済み頻度「８」の頻度個数は「３」であり、分割済み頻度「４」の頻度個数は「５」であり、分割済み頻度「２」の頻度個数は「５」であり、分割済み頻度「１」の頻度個数は「４」である。
この場合、分割済み頻度「３２」の頻度個数「２」は「３（＝ｋ）」未満である。
したがって、処理はＳ１１３Ｃに進む。
【０１９６】
図３１に戻り、Ｓ１１３Ｃから説明を続ける。
【０１９７】
Ｓ１１３Ｃにおいて、変換規則算出部４１０は、頻度個数が匿名数「ｋ」未満である分割済み頻度（以下、「再分割頻度」という）をｐ進展開して分割する。
【０１９８】
図３３の（２）分割済み頻度テーブル４９２に設定されている再分割頻度「３２」は、２（＝ｐ）を４乗した値「１６」に分割することができる。これにより、（３）分割済み頻度テーブル４９２が得られる。
【０１９９】
図３１に戻り、変換規則算出処理（Ｓ１１０）の説明を続ける。
【０２００】
Ｓ１１３Ｃの後、Ｓ１１２Ｃに戻る。
【０２０１】
図３３に示した（３）分割済み頻度テーブル４９２では、全ての分割済み頻度の頻度個数が「３（＝ｋ）」以上である。
このため、Ｓ１１２Ｃの後、Ｓ１１４Ｃに進む（図３１参照）。
【０２０２】
Ｓ１１４Ｃにおいて、変換規則算出部４１０は、分割済み頻度テーブル４９２に基づいて変換キーワード毎に分割済み頻度の数を「変換キーワード数」として算出し、各分割済み頻度の割合を「変換確率」として算出する。
【０２０３】
図３３の（３）分割済み頻度テーブル４９２の場合、検索キーワード「佐藤」の分割済み頻度は「１６」「１６」「８」である。
したがって、変換規則算出部４１０は、検索キーワード「佐藤」の分割済み頻度の個数「３」を検索キーワード「佐藤」の変換キーワード数として算出する。
さらに、変換規則算出部４１０は、検索キーワード「佐藤」の各分割済み頻度の割合「１６／４０」「１６／４０」「８／４０」を検索キーワード「佐藤」の各変換キーワードの変換確率として算出する。
【０２０４】
変換規則算出部４１０は、他の検索キーワードの変換キーワード数および変換確率についても同様に求める。
【０２０５】
図３４は、実施の形態３における変換規則テーブル２９１を示す図である。
図３５は、実施の形態３における暗号化キーワードの登録頻度を示す図である。
図３３に示した（３）分割済み頻度テーブル４９２に基づいて図３４に示す変換規則テーブル２９１が生成される。
例えば、変換規則テーブル２９１には検索キーワード「佐藤」に対応付けて変換キーワード数「３」と同じ個数の変換キーワード「佐藤−１〜３」が設定される。
また、変換規則テーブル２９１には、検索キーワード「佐藤」の各変換キーワードに対応付けて変換確率「１６／４０」「１６／４０」「８／４０」が設定される。
図３４の変換規則テーブル２９１に基づいて変換キーワードを選択し、選択した変換キーワードを暗号化した場合、各暗号化キーワードは図３５に示すような登録割合で登録データテーブル３９１に登録される。
各登録頻度は３（＝ｋ）種類以上の暗号化キーワードに共通している。このため、「３−匿名性」が保証され、暗号化キーワードの頻度分析が困難である。
【０２０６】
変換規則算出部４１０は、分割済み頻度テーブル４９２を最適化してもよい。
【０２０７】
例えば、変換規則算出部４１０は、以下のように分割済み頻度テーブル４９２を最適化する。
変換規則算出部４１０は、分割済み頻度テーブル４９２を参照し、統合しても「ｋ−匿名性」を満たす分割済み頻度の組み合わせを「統合候補」として判定する。
変換規則算出部４１０は、統合候補毎に分割済み頻度を統合して分割済み頻度テーブル４９２を生成する。
変換規則算出部４１０は、分割済み頻度テーブル４９２毎に変換キーワード数の平均値（または変換キーワード数の最大値）を算出する。
変換規則算出部４１０は、最も変換キーワード数の平均値（または変換キーワード数の最大値）が小さい分割済み頻度テーブル４９２を選択する。
【０２０８】
図３６は、実施の形態３における分割済み頻度テーブル４９２の最適化の具体例を示す図である。
図３６に示す（３）分割済み頻度テーブル４９２の場合、「３−匿名性」を満たす統合候補として｛１６、８｝、｛１６、４｝、｛１６、２｝、｛１６、１｝が挙げられる。いずれの統合候補を選択して分割済み頻度を統合しても統合後の各分割済み頻度が３つ（＝ｋ）以上の検索キーワードで共通するためである。
例えば、統合候補｛１６、２｝を分割済み頻度「１８（＝１６＋２）」に統合した場合、図３６に示す（４）分割済み頻度テーブル４９２が得られる。（４）分割済み頻度テーブル４９２の変換キーワード数の平均値は「２．７５」である。
また、統合候補｛１６、８｝を統合した場合の変換キーワード数の平均値は「３．０」であり、統合候補｛１６、４｝を統合した場合の変換キーワード数の平均値は「２．７５」であり、統合候補｛１６、１｝を統合した場合の変換キーワード数の平均値は「２．８７５」である。
つまり、統合候補｛１６、２｝を統合した場合の変換キーワード数の平均値「２．７５」が最も小さいため、変換規則算出部４１０は統合候補｛１６、２｝を統合した（４）分割済み頻度テーブル４９２を選択する。但し、統合候補｛１６、４｝を統合した場合も変換キーワード数の平均値は「２．７５」であるため、変換規則算出部４１０は、統合候補｛１６、４｝を統合した分割済み頻度テーブル４９２を選択しても構わない。
【０２０９】
図３７、３８に統合候補｛１６、２｝を統合した（４）分割済み頻度テーブル４９２に基づく変換規則テーブル２９１と暗号化キーワードの登録頻度とを示す。
【０２１０】
また、変換規則算出部４１０は、複数の統合候補からいずれかの統合候補をランダムに選択し、選択した統合候補を採用して分割済み頻度テーブル４９２を生成しても構わない。
【０２１１】
上記では検索キーワードの出現頻度をｐ進法展開で分割しているが、ｐ進法以外の分割規則に従って検索キーワードの出現頻度を分割しても構わない。
例えば、複数の分割値「１、５、１０、５０、１００、５００、・・・」から成る分割規則を予め定義する。そして、変換規則算出部４１０は、この分割規則に従って検索キーワードの出現頻度を分割する。この場合、出現頻度「２８」は「１０」「１０」「５」「１」「１」「１」に分割される。
【０２１２】
変換規則管理装置４００の変換規則管理方法の他の処理（Ｓ１２０−Ｓ１４０）は実施の形態１（図６参照）と同様である。
【０２１３】
また、データ登録装置５００のデータ登録方法、情報処理装置２００の検索方法およびサーバ装置３００の検索方法は、実施の形態１（図１０、１３、１４参照）と同様である。
【０２１４】
実施の形態３により、実施の形態２と同様な効果を得ることができる。
【０２１５】
実施の形態４．
攻撃者がキーワードを推定する際の曖昧さ（エントロピー）を安全性指標とし変換キーワード数と変換確率とを算出する形態について説明する。
以下、実施の形態１−３と異なる事項について主に説明する。説明を省略する事項については実施の形態１−３と同様である。
【０２１６】
秘匿検索システム１００の装置構成および各装置の機能構成は実施の形態１（図１−５参照）と同じである。
【０２１７】
但し、変換規則管理装置４００の変換規則算出部４１０は、以下のように変換キーワード数と変換確率とを算出する。
変換規則算出部４１０は、特定数の変換キーワードを検索キーワード毎に設けた場合の発生確率値（対応確率値）として検索キーワードと特定数の変換キーワードとを所定の組み合わせで対応付ける確率を各検索キーワードの出現頻度に基づいて算出する。
変換規則算出部４１０は、算出した発生確率値に基づいて検索キーワードと特定数の変換キーワードとの組み合わせのエントロピーをエントロピー値として算出する。
変換規則算出部４１０は、算出したエントロピー値に発生確率値を乗算してエントロピー指標値を算出する。
変換規則算出部４１０は、算出したエントロピー指標値を所定のエントロピー閾値と比較する。
変換規則算出部４１０は、エントロピー指標値がエントロピー閾値より大きい場合、変換キーワードの特定数を変換キーワード数として算出する。
変換規則算出部４１０は、変換キーワード数の逆数を変換確率（変換キーワード選択率）として算出する。
【０２１８】
図３９は、実施の形態４における変換規則算出処理（Ｓ１１０）を示すフローチャートである。
実施の形態４における変換規則算出処理（Ｓ１１０）について、図３９に基づいて説明する。
【０２１９】
以下、安全性を表すパラメータ値として登録データ数「Ｎ」とエントロピー閾値「Ｈ」とが与えられているものとする。
【０２２０】
Ｓ１１１Ｄにおいて、変換規則算出部４１０は、変数「キーワード変換数ｗ」に初期値「１」を設定する。但し、初期値は２以上の整数であっても構わない。
Ｓ１１１Ｄの後、Ｓ１１２Ｄに進む。
【０２２１】
Ｓ１１２Ｄにおいて、変換規則算出部４１０は、キーワード変換数ｗの変換キーワードを検索キーワード毎に設けた場合の発生確率値を各検索キーワードの出現頻度に基づいて算出する。発生確率値とは、検索キーワードとキーワード変換数ｗの変換キーワードとを正しい組み合わせで対応付ける確率である。
【０２２２】
図４０は、実施の形態４における検索キーワードテーブル４９１を示す図である。
図４１は、実施の形態４における変換規則テーブル２９１の一例を示す図である。
図４２、図４３は、実施の形態４における検索キーワードと変換キーワードとの組み合わせの一例を示す図である。
図４０に示す検索キーワードテーブル４９１に基づいて検索キーワード「既婚」に対して１つ（＝ｗ）の変換キーワード「既婚−１」を設け、検索キーワード「未婚」に対して１つの変換キーワード「未婚−１」を設けた場合、図４１に示す（１）変換規則テーブル２９１が得られる。
変換キーワード「既婚−１」「未婚−１」を暗号化した暗号化キーワードを「Ｅ（既婚−１）」「Ｅ（未婚−１）」とした場合、検索キーワードと暗号化キーワードとの組み合わせは図４２の（１）（２）に示すように２通り存在する。図４２の（１）の組み合わせが正しい組み合わせである。
【０２２３】
また、キーワード変換数ｗが「２」である場合、図４０に示す検索キーワードテーブル４９１に基づいて図４１に示す（２）変換規則テーブル２９１が得られる。
この場合、検索キーワードと暗号化キーワードとの組み合わせは図４３の（１）〜（６）に示すように６通り存在する。
【０２２４】
図４０に示すように、検索キーワード「既婚」の出現頻度は「７５％（＝３／４）」であり、検索キーワード「未婚」の出現頻度は「２５％（＝１／４）」である。
したがって、暗号化キーワード「Ｅ（既婚−１）」の登録頻度は「７５％（＝３／４）」であり、暗号化キーワード「Ｅ（未婚−１）」の登録頻度は「２５％（＝１／４）」である。
【０２２５】
ここで、登録データ数「Ｎ＝１０」の場合、登録データテーブル３９１（図１１参照）には１個の暗号化キーワード「Ｅ（既婚−１）」と９個の暗号化キーワード「Ｅ（未婚−１）」とが登録される可能性がある。
また、２個、３個、・・・、１０個の暗号化キーワード「Ｅ（既婚−１）」が登録される可能性もある。さらに、暗号化キーワード「Ｅ（既婚−１）」が登録されない、つまり、暗号化キーワード「Ｅ（既婚−１）」が０個の可能性もある。
但し、変換キーワードが暗号化されているため、暗号化キーワードを見ても暗号化キーワードがどの変換キーワードを暗号化したデータであるか判別できない。したがって、検索キーワードと暗号化キーワードとの正しい組み合わせは不明である。
【０２２６】
例えば、登録データテーブル３９１に６個の暗号化キーワード「Ｅ（既婚−１）」と４個の暗号化キーワード「Ｅ（未婚−１）」とが登録されているとすると、図４２の（１）に示すように検索キーワードと暗号化キーワードとを正しく組み合わせた場合、６個の暗号化キーワード「Ｅ（既婚−１）」と４個の暗号化キーワード「Ｅ（未婚−１）」とが登録されている登録確率は３６／４１０（＝（３／４）６×（１／４）４）である。この値は、登録データ数「１０」、暗号化キーワードの登録数「６」「４」および暗号化キーワードの登録頻度「３／４」「１／４」に基づいた値である。
同様に、図４２の（２）に示すように検索キーワードと暗号化キーワードとを間違って組み合わせた場合の登録確率は３４／４１０（＝（３／４）４×（１／４）６）である。
【０２２７】
したがって、図４２の（１）の組み合わせが正しい組み合わせである尤度は０．９（＝（３６／４１０）／（３６／４１０＋３４／４１０））である。同様に、図４２の（１）の組み合わせが間違った組み合わせである尤度は０．１（＝（３４／４１０）／（３６／４１０＋３４／４１０））である。これらの値は、登録確率「３６／４１０」「３４／４１０」を用いてベイズの定理によって算出される値である。以下、算出した尤度を「発生確率値」という。
【０２２８】
変換規則算出部４１０は、暗号化キーワード「Ｅ（既婚−１）」の登録数毎に発生確率値を上記のように算出する。但し、モンテカルロ法に基づき、Ｎ個の登録データを持つ登録データテーブルをランダムに１つ以上選択し、選択した登録データテーブル毎に発生確率値を算出してもよい。
【０２２９】
Ｓ１１２Ｄ（図３９）の後、Ｓ１１３Ｄに進む。
【０２３０】
Ｓ１１３Ｄにおいて、変換規則算出部４１０は、Ｓ１１２Ｄで算出した発生確率値に基づいて検索キーワードと変換キーワードとの組み合わせのエントロピーをエントロピー値として算出する。但し、変換規則算出部４１０は、暗号化キーワード「Ｅ（既婚−１）」の登録数毎にエントロピー値を算出する。また、Ｓ１１２Ｄでランダムに選択した登録データテーブル毎に発生確率値を算出した場合、変換規則算出部４１０は発生確率値を算出した登録データテーブル毎にエントロピー値を算出する。
例えば、発生確率値が「０．９」「０．１」である場合、エントロピー値は０．４７（≒−（０．９ｌｏｇ２０．９＋０．１ｌｏｇ２０．１））である。
Ｓ１１３Ｄの後、Ｓ１１４Ｄに進む。
【０２３１】
Ｓ１１４Ｄにおいて、変換規則算出部４１０は、暗号化キーワード「Ｅ（既婚−１）」の登録数毎に、Ｓ１１３Ｄで算出したエントロピー値Ａに、前記登録数の暗号化キーワード「Ｅ（既婚−１）」が発生する確率Ｂを乗算して重み付けエントロピー値Ｃ（＝Ａ×Ｂ）を算出する。
以下、暗号化キーワード「Ｅ（既婚−１）」の登録数ｎ（ｎは０以上Ｎ以下の整数）に対応する重み付けエントロピー値を「Ｃｎ」と記す。
【０２３２】
変換規則算出部４１０は、重み付けエントロピー値Ｃｎの合計値をエントロピー指標値「ｈ」として算出する。
Ｓ１１４Ｄの後、Ｓ１１５Ｄに進む。
【０２３３】
Ｓ１１５Ｄにおいて、変換規則算出部４１０は、Ｓ１１４Ｄで算出したエントロピー指標値「ｈ」と予め与えられたエントロピー閾値「Ｈ」とを比較する。
エントロピー指標値「ｈ」がエントロピー閾値「Ｈ」以上である場合（ＹＥＳ）、Ｓ１１７Ｄに進む。
エントロピー指標値「ｈ」がエントロピー閾値「Ｈ」未満である場合（ＮＯ）、Ｓ１１６Ｄに進む。
【０２３４】
Ｓ１１６Ｄにおいて、変換規則算出部４１０は、キーワード変換数「ｗ」に加算値「１」を加える。但し、加算値は２以上の整数であっても構わない。また、キーワード変換数「ｗ」を整数倍しても構わない。
Ｓ１１６Ｄの後、Ｓ１１２Ｄに戻る。
【０２３５】
Ｓ１１７Ｄにおいて、変換規則算出部４１０は、キーワード変換数「ｗ」を変換キーワード数として出力する。
また、変換規則算出部４１０は、変換キーワード数の逆数「１／ｗ」を各変換キーワードの変換確率として算出する。
【０２３６】
変換規則管理装置４００の変換規則管理方法の他の処理（Ｓ１２０−Ｓ１４０）は実施の形態１（図６参照）と同様である。
但し、変換規則テーブル２９１には変換キーワード毎に変換確率を設定しなくても構わない。各変換キーワードの変換確率が同じであるので、一つの変換確率を別途記憶すればよいからである。
【０２３７】
また、データ登録装置５００のデータ登録方法、情報処理装置２００の検索方法およびサーバ装置３００の検索方法は、実施の形態１（図１０、１３、１４参照）と同様である。
【０２３８】
以下に、実施の形態４を補足説明する。
【０２３９】
頻度分析攻撃とは、検索キーワードの頻度分布と暗号化キーワードの頻度分布とを比べることによってこれらの対応付けを行い、暗号化キーワードの内容を推定する攻撃である。
攻撃者が暗号化キーワードを十分に得られる場合は、暗号化キーワードの頻度分布は検索キーワードの頻度分布に十分近づくと考えられる。
そこで、各実施の形態では同一頻度を持つ暗号化キーワードを複数作り、検索キーワードの特定を防いでいる。
【０２４０】
攻撃者が得られる暗号化キーワードの量が少ない場合、暗号化キーワードの頻度分布は検索キーワードの頻度分布と必ずしも一致しない。
この場合、頻度が一致する暗号化キーワードの内容を特定できないことに加え、頻度が近い暗号化キーワードの内容を推定することも困難になる。
【０２４１】
そこで、実施の形態４では、攻撃者が限られた量の暗号化キーワードを得ることを仮定して暗号化キーワードと検索キーワードとの対応付けの曖昧さ（エントロピー）を数値で表し、この数値を安全性指標として変換規則を生成する。
【０２４２】
実施の形態４において、例えば、以下のような秘匿検索システム１００について説明した。
【０２４３】
秘匿検索システム１００において、情報処理装置２００はデータ・キーワードをサーバ装置３００に対して秘匿したまま検索を行うことができる。
エントロピーに基づく安全性によってサーバ装置３００によるキーワードの推定にある程度の曖昧さを確保し、さらに実施の形態１に比べ、検索要求のサイズを小さくすることができる。
また、各変換キーワードの変換確率（検索キーワードの頻度分割数）を一定にすることで、変換規則テーブル２９１のデータサイズを小さくすることができる。変換キーワード毎に変換確率を設定しなくてもよいからである。
【０２４４】
但し、変換キーワード毎に変換確率が可変であっても構わない。例えば「関東地方の都県名は１０分割」「近畿地方の府県名は９分割」のように、検索キーワードをグループ化してグループごとに一定の変換確率を用いても良い。
【０２４５】
上記の説明では、エントロピーという安全性の下限を固定したうえで検索要求サイズの削減や変換規則の簡素化を行っているが、検索要求サイズや変換規則の複雑さを固定したうえで安全性を高めるようにしてもよい。
例えば、検索要求サイズの平均値（キーワード変換数ｗ、変換キーワード数の平均値）を２以下に限定してエントロピーが最大となる変換規則を利用してもよい。
また、検索キーワードのグループ化において、グループ数を３個に限定した分割の中でエントロピーが最大となる変換規則を利用してもよい。
【符号の説明】
【０２４６】
１００  秘匿検索システム、１０１  ネットワーク、２００  情報処理装置、２１０  検索キーワード入力部、２２０  変換キーワード群取得部、２３０  暗号化キーワード群生成部、２４０  検索要求部、２５０  検索結果出力部、２８０  処理装置通信部、２９０  処理装置記憶部、２９１  変換規則テーブル、２９２  暗号鍵データ、２９３  復号鍵データ、３００  サーバ装置、３１０  サーバ装置通信部、３２０  データ検索部、３３０  データ登録部、３９０  サーバ装置記憶部、３９１  登録データテーブル、４００  変換規則管理装置、４１０  変換規則算出部、４２０  変換キーワード群生成部、４３０  変換規則生成部、４４０  管理装置通信部、４９０  管理装置記憶部、４９１  検索キーワードテーブル、４９２  分割済み頻度テーブル、５００  データ登録装置、５１０  登録装置入力部、５２０  キーワード変換部、５３０  登録データ生成部、５４０  登録要求部、５８０  登録装置通信部、５９０  登録装置記憶部、５９１  検索データテーブル、９０１  ＣＰＵ、９０２  バス、９０３  ＲＯＭ、９０４  ＲＡＭ、９０５  通信ボード、９１１  ディスプレイ装置、９１２  キーボード、９１３  マウス、９１４  ドライブ装置、９２０  磁気ディスク装置、９２１  ＯＳ、９２２  プログラム群、９２３  ファイル群。
【図１】
2012115031.tif 000003
【図２】
2012115031.tif 000004
【図３】
2012115031.tif 000005
【図４】
2012115031.tif 000006
【図５】
2012115031.tif 000007
【図６】
2012115031.tif 000008
【図７】
2012115031.tif 000009
【図８】
2012115031.tif 000010
【図９】
2012115031.tif 000011
【図１０】
2012115031.tif 000012
【図１１】
2012115031.tif 000013
【図１２】
2012115031.tif 000014
【図１３】
2012115031.tif 000015
【図１４】
2012115031.tif 000016
【図１５】
2012115031.tif 000017
【図１６】
2012115031.tif 000018
【図１７】
2012115031.tif 000019
【図１８】
2012115031.tif 000020
【図１９】
2012115031.tif 000021
【図２０】
2012115031.tif 000022
【図２１】
2012115031.tif 000023
【図２２】
2012115031.tif 000024
【図２３】
2012115031.tif 000025
【図２４】
2012115031.tif 000026
【図２５】
2012115031.tif 000027
【図２６】
2012115031.tif 000028
【図２７】
2012115031.tif 000029
【図２８】
2012115031.tif 000030
【図２９】
2012115031.tif 000031
【図３０】
2012115031.tif 000032
【図３１】
2012115031.tif 000033
【図３２】
2012115031.tif 000034
【図３３】
2012115031.tif 000035
【図３４】
2012115031.tif 000036
【図３５】
2012115031.tif 000037
【図３６】
2012115031.tif 000038
【図３７】
2012115031.tif 000039
【図３８】
2012115031.tif 000040
【図３９】
2012115031.tif 000041
【図４０】
2012115031.tif 000042
【図４１】
2012115031.tif 000043
【図４２】
2012115031.tif 000044
【図４３】
2012115031.tif 000045
【手続補正書】
【提出日】平成25年7月4日(2013.7.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
情報処理装置と検索装置と対応キーワード管理装置とを備える検索システムにおいて、
前記情報処理装置は、
検索キーワードと１以上の対応キーワードとを対応させた対応キーワード群として前記対応キーワード管理装置によって生成される対応キーワードデータを記憶する対応キーワード記憶部と、
検索キーワードを入力する検索キーワード入力部と、
前記検索キーワード入力部により入力された前記検索キーワードに対応する対応キーワード群を前記対応キーワード記憶部に記憶された対応キーワードデータから取得する対応キーワード群取得部と、
前記対応キーワード群取得部によって取得された対応キーワード群に含まれる対応キーワードを暗号化して暗号化キーワード群を生成する暗号化キーワード群生成部と、
前記暗号化キーワード群生成部によって生成された暗号化キーワード群を含む検索要求データを前記検索装置へ送信する検索要求データ送信部と、
前記検索装置から送信される検索応答データを受信する検索応答データ受信部と、
前記検索応答データ受信部によって受信された検索応答データに含まれる暗号化データを復号し、復号して得られる検索データを検索結果として出力する検索結果出力部とを備え、
前記検索装置は、
検索データを暗号化した暗号化データを記憶する暗号化データ記憶部であって、検索データ毎に当該検索データを暗号化した暗号化データと対応キーワードを暗号化した暗号化キーワードとを対応付けて記憶する暗号化データ記憶部と、
前記情報処理装置から送信される検索要求データを受信する検索要求データ受信部と、
前記検索要求データ受信部によって受信された検索要求データに基づいて、前記検索要求データ内の暗号化キーワード群に含まれる暗号化キーワードを検索キーとして検索キーに対応する暗号化データを前記暗号化データ記憶部から取得する暗号化データ検索部と、
前記暗号化データ検索部によって取得された暗号化データを含む検索応答データを送信する検索応答データ送信部とを備え、
前記対応キーワード管理装置は、
検索キーワードを定義すると共に特定の検索キーワードに対応付けられる検索データの割合を特定の検索キーワードの出現頻度として定義する出現頻度データを記憶する出現頻度記憶部と、
前記出現頻度記憶部に記憶される出現頻度データに定義された前記検索キーワードの出現頻度に応じて、前記検索キーワードに対応付ける対応キーワードの個数を対応キーワード数として算出する対応キーワード数算出部と、
前記対応キーワード数算出部によって算出された対応キーワード数と同じ個数の対応キーワードを対応キーワード群として生成する対応キーワード群生成部と、
前記出現頻度データに定義された検索キーワードと前記対応キーワード群生成部によって生成された対応キーワード群とを対応付けて前記対応キーワードデータを生成する対応キーワードデータ生成部とを備える
ことを特徴とする検索システム。
【請求項２】
前記対応キーワード管理装置の対応キーワード数算出部は、前記出現頻度データに定義された検索キーワードの出現頻度に基づいて、前記検索キーワードの対応キーワード毎に前記検索キーワードの対応キーワード群から当該対応キーワードを選択する割合を対応キーワード選択率として算出し、
前記対応キーワード管理装置の対応キーワードデータ生成部は、前記検索キーワードと前記対応キーワード群と前記対応キーワード選択率とを対応付けたデータを対応キーワード選択率データとして生成し、
前記検索システムは、さらに、暗号化データ生成装置を備え、
前記暗号化データ生成装置は、
検索データと検索キーワードとを対応付けて記憶する検索データ記憶部と、
前記対応キーワード管理装置によって生成された対応キーワード選択率データを記憶する対応キーワード選択率記憶部と、
前記対応キーワード選択率データから前記検索データ記憶部に記憶された検索キーワードに対応する対応キーワード群を取得し、取得した対応キーワード群に含まれる少なくともいずれかの対応キーワードを前記対応キーワード選択率データに含まれる対応キーワード選択率に応じて選択する対応キーワード選択部と、
前記検索データ記憶部に記憶された検索データを暗号化して暗号化データを生成し、前記対応キーワード選択部によって選択された対応キーワードを暗号化して暗号化キーワードを生成する暗号化データ生成部とを備え、
前記検索装置の前記暗号化データ記憶部は、前記暗号化データ生成装置によって生成された暗号化データと暗号化キーワードとを対応付けて記憶する
ことを特徴とする請求項１記載の検索システム。
【請求項３】
前記対応キーワード管理装置の対応キーワード数算出部は、各検索キーワードの対応キーワード数で分割した分割後の各検索キーワードの出現頻度が等しくなるように各検索キーワードの対応キーワード数を算出し、
前記対応キーワード数算出部は、検索キーワード毎に前記対応キーワード数の逆数を前記対応キーワード選択率として算出する
ことを特徴とする請求項２記載の検索システム。
【請求項４】
前記対応キーワード数算出部は、各検索キーワードの出現頻度の最大公約数を算出し、検索キーワード毎に検索キーワードの出現頻度を前記最大公約数で除算した値を検索キーワードの対応キーワード数として算出する
ことを特徴とする請求項３記載の検索システム。
【請求項５】
前記対応キーワード管理装置の対応キーワード数算出部は、所定の匿名数以上の検索キーワードが同じ出現頻度を持つように各検索キーワードの出現頻度を分割する分割数を各検索キーワードの対応キーワード数として算出し、各検索キーワードの出現頻度を分割する分割割合を各検索キーワードの対応キーワード選択率として算出する
ことを特徴とする請求項２記載の検索システム。
【請求項６】
前記対応キーワード数算出部は、各検索キーワードの出現頻度から所定の匿名数番目に大きい出現頻度を演算頻度として選択し、前記演算頻度以上の出現頻度から１つ以上の演算頻度を減算し、減算後の各検索キーワードの出現頻度から前記匿名数番目に大きい出現頻度を新たな演算頻度として選択し、新たな演算頻度以上の出現頻度から１つ以上の新たな演算頻度を減算し、検索キーワード毎に出現頻度から減算した各演算頻度の数を対応キーワード数として算出すると共に元の出現頻度に対する各演算頻度の割合を対応キーワード選択率として算出する
ことを特徴とする請求項２記載の検索システム。
【請求項７】
前記対応キーワード数算出部は、検索キーワード毎に検索キーワードの出現頻度を所定の基数のべき乗値を用いて複数の出現頻度に分割し、検索キーワード毎に出現頻度の分割数を対応キーワード数として算出すると共に分割前の出現頻度に対する分割後の出現頻度の割合を対応キーワード選択率として算出する
ことを特徴とする請求項２記載の検索システム。
【請求項８】
前記対応キーワード数算出部は、各検索キーワードの分割後の出現頻度のうち当該出現頻度を持つ検索キーワードの数が所定の匿名数未満である出現頻度を前記基数のべき乗値を用いて分割する
ことを特徴とする請求項７記載の検索システム。
【請求項９】
前記対応キーワード数算出部は、特定数の対応キーワードを検索キーワード毎に設けた場合の対応確率値として検索キーワードと特定数の対応キーワードとを所定の組み合わせで対応付ける確率を各検索キーワードの出現頻度に基づいて算出し、算出した対応確率値に基づいて検索キーワードと特定数の対応キーワードとの組み合わせのエントロピーをエントロピー値として算出し、算出したエントロピー値に前記対応確率値を乗算してエントロピー指標値を算出し、算出したエントロピー指標値を所定のエントロピー閾値と比較し、前記エントロピー指標値が前記エントロピー閾値より大きい場合、前記対応キーワードの特定数を対応キーワード数として算出し、
前記対応キーワード数算出部は、前記対応キーワード数の逆数を前記対応キーワード選択率として算出する
ことを特徴とする請求項２記載の検索システム。
【請求項１０】
情報処理装置と検索装置と対応キーワード管理装置とを備える検索システムの検索方法において、
前記情報処理装置は、検索キーワードと１以上の対応キーワードとを対応させた対応キーワード群として前記対応キーワード管理装置によって生成される対応キーワードデータを記憶する対応キーワード記憶部を備え、
前記情報処理装置は、
検索キーワードを入力する検索キーワード入力処理と、
前記検索キーワード入力処理により入力された前記検索キーワードに対応する対応キーワード群を前記対応キーワード記憶部に記憶された対応キーワードデータから取得する対応キーワード群取得処理と、
前記対応キーワード群取得処理によって取得された対応キーワード群に含まれる対応キーワードを暗号化して暗号化キーワード群を生成する暗号化キーワード群生成処理と、
前記暗号化キーワード群生成処理によって生成された暗号化キーワード群を含む検索要求データを前記検索装置へ送信する検索要求データ送信処理とを実行し、
前記検索装置は、検索データを暗号化した暗号化データを記憶する暗号化データ記憶部であって、検索データ毎に当該検索データを暗号化した暗号化データと対応キーワードを暗号化した暗号化キーワードとを対応付けて記憶する暗号化データ記憶部を備え、
前記検索装置は、
前記情報処理装置から送信される検索要求データを受信する検索要求データ受信処理と、
前記検索要求データ受信処理によって受信された検索要求データに基づいて、前記検索要求データ内の暗号化キーワード群に含まれる暗号化キーワードを検索キーとして検索キーに対応する暗号化データを前記暗号化データ記憶部から取得する暗号化データ検索処理と、
前記暗号化データ検索処理によって取得された暗号化データを含む検索応答データを送信する検索応答データ送信処理とを実行し、
前記情報処理装置は、
前記検索装置から送信された検索応答データを受信する検索応答データ受信処理と、
前記検索応答データ受信処理によって受信された検索応答データに含まれる暗号化データを復号し、復号して得られる検索データを検索結果として出力する検索結果出力処理とを実行し、
前記対応キーワード管理装置は、検索キーワードを定義すると共に特定の検索キーワードに対応付けられる検索データの割合を特定の検索キーワードの出現頻度として定義する出現頻度データを記憶する出現頻度記憶部を備え、
前記出現頻度記憶部に記憶される出現頻度データに定義された前記検索キーワードの出現頻度に応じて、前記検索キーワードに対応付ける対応キーワードの個数を対応キーワード数として算出する対応キーワード数算出処理と、
前記対応キーワード数算出処理によって算出された対応キーワード数と同じ個数の対応キーワードを対応キーワード群として生成する対応キーワード群生成処理と、
前記出現頻度データに定義された検索キーワードと前記対応キーワード群生成処理によって生成された対応キーワード群とを対応付けて前記対応キーワードデータを生成する対応キーワードデータ生成処理とを実行する
ことを特徴とする検索システムの検索方法。
【請求項１１】
検索キーワードを定義すると共に特定の検索キーワードに対応付けられる検索データの割合を特定の検索キーワードの出現頻度として定義する出現頻度データを記憶する出現頻度記憶部と、
前記出現頻度記憶部に記憶される出現頻度データに定義された前記検索キーワードの出現頻度に応じて、前記検索キーワードに対応付ける対応キーワードの個数を対応キーワード数として算出する対応キーワード数算出部と、
前記対応キーワード数算出部によって算出された対応キーワード数と同じ個数の対応キーワードを対応キーワード群として生成する対応キーワード群生成部と、
前記出現頻度データに定義された検索キーワードと前記対応キーワード群生成部によって生成された対応キーワード群とを対応付けたデータを対応キーワードデータとして生成する対応キーワードデータ生成部と
を備えることを特徴とする対応キーワード管理装置。
【請求項１２】
前記対応キーワード数算出部は、前記出現頻度データに定義された検索キーワードの出現頻度に基づいて、前記検索キーワードの対応キーワード毎に前記検索キーワードの対応キーワード群から当該対応キーワードを選択する割合を対応キーワード選択率として算出し、
前記対応キーワードデータ生成部は、前記検索キーワードと前記対応キーワード群と前記対応キーワード選択率とを対応付けたデータを対応キーワード選択率データとして生成する
ことを特徴とする請求項１１記載の対応キーワード管理装置。
【請求項１３】
前記対応キーワード数算出部は、所定の匿名数以上の検索キーワードが同じ出現頻度を持つように各検索キーワードの出現頻度を分割する分割数を各検索キーワードの対応キーワード数として算出し、各検索キーワードの出現頻度を分割する分割割合を各検索キーワードの対応キーワード選択率として算出する
ことを特徴とする請求項１２記載の対応キーワード管理装置。
【請求項１４】
前記対応キーワード数算出部は、各検索キーワードの出現頻度から所定の匿名数番目に大きい出現頻度を演算頻度として選択し、前記演算頻度以上の出現頻度から１つ以上の演算頻度を減算し、減算後の各検索キーワードの出現頻度から前記匿名数番目に大きい出現頻度を新たな演算頻度として選択し、新たな演算頻度以上の出現頻度から１つ以上の新たな演算頻度を減算し、検索キーワード毎に出現頻度から減算した各演算頻度の数を対応キーワード数として算出すると共に元の出現頻度に対する各演算頻度の割合を対応キーワード選択率として算出する
ことを特徴とする請求項１２記載の対応キーワード管理装置。
【請求項１５】
前記対応キーワード数算出部は、検索キーワード毎に検索キーワードの出現頻度を所定の基数のべき乗値を用いて複数の出現頻度に分割し、検索キーワード毎に出現頻度の分割数を対応キーワード数として算出すると共に分割前の出現頻度に対する分割後の出現頻度の割合を対応キーワード選択率として算出する
ことを特徴とする請求項１２記載の対応キーワード管理装置。
【請求項１６】
前記対応キーワード数算出部は、各検索キーワードの分割後の出現頻度のうち当該出現頻度を持つ検索キーワードの数が所定の匿名数未満である出現頻度を前記基数のべき乗値を用いて分割する
ことを特徴とする請求項１５記載の対応キーワード管理装置。
【請求項１７】
前記対応キーワード数算出部は、特定数の対応キーワードを検索キーワード毎に設けた場合の対応確率値として検索キーワードと特定数の対応キーワードとを所定の組み合わせで対応付ける確率を各検索キーワードの出現頻度に基づいて算出し、算出した対応確率値に基づいて検索キーワードと特定数の対応キーワードとの組み合わせのエントロピーをエントロピー値として算出し、算出したエントロピー値に前記対応確率値を乗算してエントロピー指標値を算出し、算出したエントロピー指標値を所定のエントロピー閾値と比較し、前記エントロピー指標値が前記エントロピー閾値より大きい場合、前記対応キーワードの特定数を対応キーワード数として算出し、
前記対応キーワード数算出部は、前記対応キーワード数の逆数を前記対応キーワード選択率として算出する
ことを特徴とする請求項１２記載の対応キーワード管理装置。
【請求項１８】
請求項１１から請求項１７いずれかに記載の対応キーワード管理装置としてコンピュータを機能させるための対応キーワード管理プログラム。
【請求項１９】
請求項１１から請求項１７いずれかに記載の対応キーワード管理装置によって検索キーワードと１以上の対応キーワードとを対応させた対応キーワード群として生成される対応キーワードデータを記憶する対応キーワード記憶部と、
検索キーワードを入力する検索キーワード入力部と、
前記検索キーワード入力部により入力された前記検索キーワードに対応する対応キーワード群を前記対応キーワード記憶部に記憶された対応キーワードデータから取得する対応キーワード群取得部と、
前記対応キーワード群取得部によって取得された対応キーワード群に基づいて、前記対応キーワード群に含まれる対応キーワードを暗号化して暗号化キーワード群を生成する暗号化キーワード群生成部と、
前記暗号化キーワード群生成部によって生成された暗号化キーワード群を含む検索要求データを所定の検索装置へ送信する検索要求データ送信部と、
前記検索装置から送信される検索応答データを受信する検索応答データ受信部と、
前記検索応答データ受信部によって受信された検索応答データに含まれる暗号化データを復号し、復号して得られる検索データを検索結果として出力する検索結果出力部と
を備えることを特徴とする情報処理装置。
【請求項２０】
請求項１９記載の情報処理装置としてコンピュータを機能させるための検索プログラム。
【国際調査報告】
2012115031.tif 000046
2012115031.tif 000047
2012115031.tif 000048
2012115031.tif 000049