(57)【特許請求の範囲】
【請求項１】
確率的暗号化方式により暗号化された登録データを記憶するＤＢサーバと、
検索クライアントとを含み、
前記検索クライアントから受信した、前記ＤＢサーバが記憶するデータの検索を要求する検索クエリに従い、前記ＤＢサーバが記憶する前記データの暗号化を解除せずに、検索する検索可能暗号処理システムであって、
前記確率的暗号化方式は、同一のデータ値の平文から異なるデータ値の暗号文を生成するデータの暗号化方式であり、
前記検索クライアントは、前記検索クエリを記憶する記憶部と、前記検索クエリを暗号化する制御部と、暗号化した前記検索クエリを送信する通信部とを備え、
前記検索クライアントにおける前記制御部は、第1の乱数を生成する乱数生成部と、前記第1の乱数により前記検索クエリを前記確率的暗号化方式で暗号化する基本演算部と、前記第1の乱数を入力値とする準同型関数の関数値を出力値とする準同型関数部とを備え、
前記検索クライアントにおける前記制御部は、前記準同型関数部が出力した前記関数値を変換し、ハッシュ値を出力する圧縮関数部を備え、
前記ＤＢサーバは、前記検索クエリを受信する通信部と、暗号化された前記検索クエリと暗号化された前記登録データを記憶する記憶部と、記憶する前記登録データが前記検索クエリに該当するかを決定する制御部とを備え、
前記ＤＢサーバにおける前記制御部は、暗号化された前記登録データと暗号化された前記検索クエリとの乱数の相関を導出する全体処理部と、前記相関を入力値とする準同型関数の関数値を出力値とする準同型関数部とを備え、
前記検索クライアントが送信する暗号化された前記検索クエリは、前記基本演算部により、前記確率的暗号化方式で暗号化された暗号文と、前記圧縮関数部が出力する前記ハッシュ値から構成されるデータが暗号化されていることを特徴とする検索可能暗号処理システム。
【請求項２】
確率的暗号化方式により、暗号化された登録データを記憶するＤＢサーバと、
検索クライアントとを含み、
前記検索クライアントから受信した、前記ＤＢサーバが記憶するデータの検索を要求する検索クエリに従い、前記ＤＢサーバが記憶する前記データの暗号化を解除せずに、検索する検索可能暗号処理システムであって、
前記確率的暗号化方式は、同一のデータ値の平文から異なるデータ値の暗号文を生成するデータの暗号化方式であり、
前記検索クライアントは、前記検索クエリを記憶する記憶部と、前記検索クエリを暗号化する制御部と、暗号化した前記検索クエリを送信する通信部とを備え、
前記検索クライアントにおける前記制御部は、乱数を生成する乱数生成部と、前記乱数により前記検索クエリを前記確率的暗号化方式で暗号化する基本演算部と、前記乱数を入力値とする準同型関数の関数値を出力値とする準同型関数部とを備え、
前記ＤＢサーバは、前記検索クエリを受信する通信部と、暗号化された前記検索クエリと暗号化された前記登録データを記憶する記憶部と、記憶する前記登録データが前記検索クエリに該当するかを決定する制御部とを備え、
前記ＤＢサーバにおける前記制御部は、暗号化された前記登録データと、暗号化された前記検索クエリとの乱数の相関を導出する全体処理部と、前記相関を入力値とする準同型関数の関数値を出力値とする準同型関数部とを備え、
前記検索クライアントが送信する暗号化された前記検索クエリは、前記基本演算部により、前記確率的暗号化方式で暗号化された前記データと、前記準同型関数部が出力した前記関数値から構成されるデータが暗号化されることを特徴とする検索可能暗号処理システム。
【請求項３】
請求項１記載の検索可能暗号処理システムであって、
前記確率的暗号化方式により、前記登録データを暗号化する登録クライアントを有し、
前記ＤＢサーバの前記通信部は、暗号化した前記登録データを受信し、前記ＤＢサーバの前記記憶部は前記登録データを記憶し、
前記登録クライアントは、前記登録データを記憶する記憶部と、前記登録データを暗号化する制御部と、暗号化した前記登録データを送信する通信部とを備え、
前記登録クライアントにおける前記制御部は、第２の乱数を生成する乱数生成部と、前記第２の乱数により前記登録データを前記確率的暗号化方式で暗号化する基本演算部と、前記第２の乱数を入力値とする準同型関数の関数値を出力値とする準同型関数部と、を備えることを特徴とする検索可能暗号処理システム。
【請求項４】
請求項３記載の検索可能暗号処理システムであって、
前記登録クライアントが送信する暗号化された前記登録データは、前記乱数部が出力した前記第２の乱数と、前記基本演算部により前記確率的暗号化方式で暗号化された暗号文と、前記準同型関数部が出力する前記関数値から構成されることを特徴とする検索可能暗号処理システム。
【請求項５】
請求項４記載の検索可能暗号処理システムであって、
前記ＤＢサーバの前記通信部は、前記検索クエリに該当する、暗号化された前記登録データを送信し、
前記検索クライアントの前記通信部は、暗号化された前記登録データを受信し、前記検索クライアントの前記制御部は、前記登録データを復号化し、
前記検索クライアントの前記制御部は、暗号化された前記登録データを暗号化した第３の乱数を出力する圧縮関数部を備え、前記検索クライアントの前記基本演算部は、前記登録データの暗号化を解除することを特徴とする検索可能暗号処理システム。
【請求項６】
請求項５記載の検索可能暗号処理システムであって、
前記ＤＢサーバの前記基本演算部は、前記登録データから任意のデータを抽出し、前記圧縮関数部が出力した前記第３の乱数から、指定されたデータ長分を検査することを特徴とする検索可能暗号処理システム。
【請求項７】
請求項６記載の検索可能暗号処理システムであって、
前記登録クライアントの前記記憶部は、前記登録クライアントの前記準同型関数部に入力可能な関数パラメータを記憶し、
前記検索クライアントの前記記憶部は、前記検索クライアントの前記準同型関数部に入力可能な関数パラメータを記憶し、
前記ＤＢサーバの前記記憶部は、前記ＤＢサーバの前記準同型関数部に入力可能な関数パラメータを記憶することを特徴とする検索可能暗号処理システム。
【請求項８】
請求項７記載の検索可能暗号処理システムであって、
前記検索クライアントの前記記憶部は、暗号化を解除した前記登録データの検査用のパラメータを記憶し、
前記検索クライアントは、暗号化を解除した前記登録データから検査用のデータを抽出し、前記検査用のパラメータとの関係を検査する全体処理部を備えることを特徴とする検索可能暗号処理システム。
【請求項９】
請求項８記載の検索可能暗号処理システムであって、
前記登録クライアントは、前記登録データを決定的暗号化方式で暗号化する暗号化部を備え、
前記決定的暗号化方式は、同一のデータ値の平文からデータ値が等しい暗号文を生成するデータの暗号化方式であることを特徴とする検索可能暗号処理システム。
【請求項１０】
請求項９記載の検索可能暗号処理システムであって、
前記登録クライアントの前記記憶部は、暗号化されていない、登録用のデータを記憶し、前記登録クライアントの前記記憶部に記憶した検査用のパラメータから、誤り検査用のデータを抽出し、前記登録用のデータと結合させる全体制御部を備えることを特徴とする検索可能暗号処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サーバ／クライアントモデルにおいて、サーバが、クライアントの要求に従って、暗号化データを復号せずに、預託された暗号化データを検索する、検索処理システムに関する。
【背景技術】
【０００２】
情報システムの開発・運用管理費の効率化を目的に、近年、情報システムを自組織が維持するのではなく、他組織が提供する情報システムを利用する、クラウドと呼ばれる運用管理形態が脚光を浴びている。一方、クラウドにおいては、情報システムを管理する組織が、情報システムを利用する組織とは異なるため、情報漏えい等を防止する策や、事故発生後の原因究明、再発防止策等が自組織だけでは立てにくい。そのため、事前に、データの不正流出の予防策として、暗号技術を活用し、データの機密性を確保する必要がある。
【０００３】
サーバ／クライアントモデルにおいて、クライアントが、サーバにデータを預託しながら、サーバに対し、預託したデータの情報漏洩を防ぐ技術として、暗号技術を利用した方式が知られている。例えば、非特許文献１や非特許文献２には、クライアントの要求に従って、暗号化データを復号せずに、預託された暗号化データを検索する、検索処理方式が記載されている。この検索処理方式は、平文と暗号文が一対一の単純な対応関係を有する決定的暗号化方式よりも安全な、平文と暗号文が一対ｍの複雑な対応関係を有する確率的暗号化方式を採用しており、サーバ管理者への情報漏洩を防ぎながら、かつサーバに預託したデータを安全に検索するための技術が開示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Dawn  Xiaodong Song, David Wagner, Arian Perrig. “Practical Techniques for Searches on Encrypted Data”. In Proceedings of the 2000 IEEE Symposium on Security and Privacy, pages 44-55(2000).
【非特許文献２】Zhiqiang Yang, Sheng Zhong, Rebecca N. Wright. “Privacy-Preserving Queries on Encrypted Data”. In Proceedings of the 11th European Symposium on Research in Computer Security (Esorics), Volume 4189 of Lecture Notes in Computer Science, pages 476-495(2006).
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１、非特許文献２に記載された技術では、サーバに預託する確率的暗号化で暗号化したデータを復号化するために必要な、運用管理が複雑、クライアント・サーバ共に複雑である。更に、擬似乱数による確率的暗号化は、クライアントが検索をするまでは有効であるが、検索後は、検索に該当した暗号文の擬似乱数のマスクが解除されてしまい、暗号文の安全性が、確率的暗号化から、決定的暗号化に低下してしまう。しかも、クライアントは、検索時の要求(検索クエリ)の暗号化には、安全性の低い決定的暗号化方式を用いているため、頻度分析等の不正攻撃に対しても、脆弱である。
【課題を解決するための手段】
【０００６】
前記課題を解決するために、検索可能暗号処理システムは、データを預かるＤＢサーバと、ＤＢサーバにデータを預託する登録クライアントと、ＤＢサーバにデータを検索させる検索クライアントがネットワーク経由で連携し、登録クライアントは、ハッシュ値と準同型関数の出力値によるマスクを用いた確率的暗号化方式により、暗号化したデータを、安全にサーバに預託し、検索クライアントは、検索クエリの暗号化に、複数の異なる入力値から同一の値を出力する準同型関数を用いたマスクによる確率的暗号化を用い、ＤＢサーバにマスクを解除させずに、かつ、ＤＢサーバに検索に該当するデータの出現頻度が漏洩しないよう、検索クエリと該当しないデータを検索結果として出力させ、検索クライアントは、検索結果を入手後、再暗号化を行い、ＤＢサーバにデータを再預託する。
【発明の効果】
【０００７】
クライアントがＤＢサーバを利用した検索後も、検索に該当したデータが確率的暗号で暗号化されており、安全性が高い。また、複雑な運用管理をクライアントに強いることなく、暗号化されたデータを効率的に復号化できる。
【図面の簡単な説明】
【０００８】
【図１】検索可能暗号処理システムの概略を例示する図である。
【図２】登録クライアントの機能の概略を例示する図である。
【図３】検索クライアントの機能の概略を例示する図である。
【図４】ＤＢサーバの機能の概略を例示する図である。
【図５】コンピュータの概略構成を例示する図である。
【図６】登録クライアントの出力部の表示内容を例示する図である。
【図７Ａ】登録クライアントが作成する連結データのデータ構成を例示するブロック図である。
【図７Ｂ】登録クライアントが作成する連結データのデータ構成を例示するブロック図である。
【図７Ｃ】登録クライアントが作成する秘匿登録データのデータ構成を例示するブロック図である。
【図８】登録クライアントが秘匿登録データをＤＢサーバへ登録する処理を例示するシーケンス図である。
【図９Ａ】ＤＢサーバのデータベース記憶部に記憶される、データベースの管理状態を例示する図である。
【図９Ｂ】ＤＢサーバのデータベース記憶部に記憶される、データベースの検索手順を例示する図である。
【図１０】検索クライアントの出力部の表示内容を例示する図である。
【図１１Ａ】検索クライアントが作成する連結データのデータ構成を例示するブロック図である。
【図１１Ｂ】検索クライアントが作成する連結データのデータ構成を例示するブロック図である。
【図１１Ｃ】検索クライアントが作成する連結データのデータ構成を例示するブロック図である。
【図１２】検索クライアントが、秘匿検索クエリを用い、ＤＢサーバ内のデータベースを検索する処理を例示するシーケンス図である。
【図１３Ａ】ＤＢサーバが通信部から受信した秘匿検索クエリを復号化した、連結データのデータ構成を例示するブロック図である。
【図１３Ｂ】ＤＢサーバが、データベース記憶部に記憶した、秘匿登録データのデータ構成を例示するブロック図である。
【図１３Ｃ】ＤＢサーバが作成する連結データのデータ構成を例示するブロック図である。
【図１３Ｄ】ＤＢサーバが作成する連結データのデータ構成を例示するブロック図である。
【図１４Ａ】検索クライアントが通信部から受信した秘匿登録データのデータ構成を例示するブロック図である。
【図１４Ｂ】検索クライアントが作成するデータＣＲのデータ構成を例示するブロック図である。
【図１４Ｃ】ＤＢサーバが作成する連結データのデータ構成を例示するブロック図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。
【００１０】
図１は、本実施形態の検索処理システムの概略図である。図示するように、検索処理システムは、登録クライアント100（Registration Client）と、検索クライアント200（Search Client）と、ＤＢサーバ300（Data Base Server）とを備え、登録クライアント100とＤＢサーバ300、検索クライアント200とＤＢサーバ300は、ネットワーク400を介して相互に情報を送受信できるように構成されている。
【００１１】
ここで、本実施形態における登録クライアント100は、秘匿化したデータをＤＢサーバ300に送信するデータ登録用の送受信装置として機能し、検索クライアント200は、秘匿化した検索クエリをＤＢサーバ300に送信し、検索結果を受信する、検索用の送受信装置として機能し、ＤＢサーバ300は、秘匿化したデータをデータベースに保管し、またデータベース内のデータを検索するＤＢ管理用の送受信装置として機能する。
【００１２】
図２は、登録クライアント100の機能概略図である。図示するように、登録クライアント100は、制御部110と、記憶部120と、入力部101と、出力部102と、通信部103とを備える。
【００１３】
記憶部120は、登録データ記憶部130と、秘密鍵記憶部150と、パラメータ記憶部160と、一時情報記憶部180とを備える。
【００１４】
登録データ記憶部130には、ＤＢサーバ300に送信するデータである、送信文を特定する情報が記憶される。ここで、本実施形態においては、入力部101を介して、受け付けた平文登録データ131を特定する情報と、ＤＢサーバ300に登録する、秘匿登録データ132を特定する情報と、平文登録データ131と秘匿登録データ132の属性133を特定する情報とが記憶される。
【００１５】
秘密鍵記憶部150には、安全性の観点から登録クライアント100が秘密に管理すべき、秘密鍵151を特定する情報が記憶される。ここで、本実施形態においては、暗号化部112に入力する秘密鍵151と、擬似乱数生成部114に入力する秘密鍵151と、圧縮関数部115に入力する秘密鍵151とを特定する情報が記憶される。
【００１６】
パラメータ記憶部160には、データの秘匿化に用いる、パラメータを特定する情報が記憶される。ここで、本実施形態においては、準同型関数部116に入力する関数パラメータ161と、基本演算部117に入力する検査パラメータ162とを特定する情報が記憶される。また、安全性の観点から、関数パラメータ161は、登録クライアント100が秘密に管理すべき情報である。
【００１７】
一時情報記憶部180には、制御部110での処理で必要となる情報が記憶される。
【００１８】
制御部110は、全体処理部111と、暗号化部112と、擬似乱数生成部114と、圧縮関数部115と、準同型関数部116と、基本演算部117とを備える。
【００１９】
全体処理部111は、登録クライアント100における全ての処理を制御する。
【００２０】
例えば、本実施形態において、全体処理部111は、入力部101を介して入力を受け付けた情報を、登録データ記憶部130に平文登録データ131として記憶する処理を行う。
【００２１】
また、本実施形態において、全体処理部111は、平文登録データ131を出力部102に表示する処理を行う。
【００２２】
また、本実施形態において、全体処理部111は、登録データ記憶部130に記憶した平文登録データ131を読み込み、それぞれ、暗号化部112と、擬似乱数生成部114と、圧縮関数部115と、準同型関数部116と、基本演算部117とに入力し、出力されたデータを、登録データ記憶部130に秘匿登録データ132として記憶する処理を行う。
【００２３】
また、本実施形態において、全体処理部111は、属性133と秘匿登録データ132を、通信部103を介してＤＢサーバ300に送信する処理を行う。
【００２４】
さらに、本実施形態において、全体処理部111は、ＤＢサーバ300より通信部103を介して受信した属性133と秘匿登録データ132を、一時情報記憶部180に記憶する処理と出力部102に表示する処理を行う。
【００２５】
暗号化部112は、入力されたデータを暗号化したデータを出力する処理を行う。
【００２６】
例えば、本実施形態においては、全体処理部111からデータと秘密鍵151が入力され、秘密鍵151を用い、暗号化したデータを出力する処理を行う。
【００２７】
例えば、標準的な暗号化アルゴリズムの実装により、暗号化部112は実現される。
【００２８】
擬似乱数生成部114は、擬似乱数を出力する処理を行う。
【００２９】
例えば、擬似乱数生成部114は、温度、時間、電力量、等の物理現象から、乱数を出力する。
【００３０】
本実施形態においては、擬似乱数生成部114は、全体処理部111から入力された秘密鍵151を用い、擬似乱数を出力する。また、秘密鍵151のデータ値は新しいデータ値に更新され、再び、全体処理部111により秘密鍵記憶部150に記憶される。
【００３１】
例えば、標準的な擬似乱数生成アルゴリズムの実装により、擬似乱数生成部114は実現される。
【００３２】
圧縮関数部115は、入力されたデータを圧縮したデータを出力する処理を行う。
【００３３】
例えば、本実施形態においては、全体処理部111から入力されたデータを固定長（ｈビット）の別のデータに変換し、出力する処理を行う。
【００３４】
例えば、標準的な暗号ハッシュ関数アルゴリズムの実装により、任意長の入力データを固定長のデータへ変換する圧縮関数部115が実現できる。
【００３５】
準同型関数部116は、入力されたデータに対し、関数計算の出力結果をデータとして出力する処理を行う。
【００３６】
例えば、本実施形態においては、全体処理部111から入力されたデータを、準同型の性質を有する関数の入力値とみなし、全体処理部111から入力された関数パラメータ161を用いて、関数計算の出力値をバイナリ列で表現した固定長（ｆビット）のデータに変換する処理を行う。
【００３７】
ただし、準同型関数とは、関数Ｆと、入力変数ｘ、入力変数ｙに対し、
Ｆ（ｘ・ｙ）＝Ｆ（ｘ）？Ｆ（ｙ）      （1）
が成り立つ関数を指す。ただし、・と？は、演算記号を表わし、加算用の演算記号+、乗算用の演算記号*、ビット毎の排他的論理和であるＸＯＲ(eXclusive OR)演算用の演算記号xor等が入る。
【００３８】
本実施形態では、・と？にＸＯＲ演算記号xorが入る場合、即ち式（2）が成り立つ場合を示す。
Ｆ（ｘ xor ｙ）＝Ｆ（ｘ）xor Ｆ（ｙ）      （2）
ただし、準同型関数が式（2）以外の演算記号で成り立つ時でも、本実施形態は同様に実施できる。
【００３９】
なお、準同型関数を実現するアルゴリズムの実装により、準同型関数部116は実現される。
【００４０】
基本演算部117は、加算、減算、比較算等の基本的な算術演算に関する処理を行う。
【００４１】
例えば、本実施形態においては、基本演算部117は、全体処理部111から入力された２つのデータのビット毎の排他的論理和であるＸＯＲ演算や、比較演算の等号成立または不成立の検証結果を、データとして出力する処理を行う。
【００４２】
以上に示した登録クライアント100は、例えば、図５（コンピュータの概略図）に示すような、ＣＰＵ(Central Processing Unit)501と、メモリ502と、ＨＤＤ(Hard Disk Drive)等の外部記憶装置503と、ＣＤ(Compact Disk)やＤＶＤ(Digital Versatile Disk)等の可搬性を有する記憶媒体508に対して情報を読み書きする読書装置507と、キーボードやマウス等の入力装置506と、ディスプレイ等の出力装置505と、通信ネットワークに接続するためのＮＩＣ(Network Interface Card)等の通信装置504と、これらを連結するシステムバス等の内部通信線(システムバスという)509と、を備えた一般的なコンピュータ500で実現できる。
【００４３】
例えば、記憶部120は、ＣＰＵ501がメモリ502または外部記憶装置503を利用することにより実現可能であり、制御部110と制御部110に含まれる各処理部は、外部記憶装置503に記憶されている所定のプログラムをメモリ502にロードしてＣＰＵ501で実行することで実現可能であり、入力部101は、ＣＰＵ501が入力装置506を利用することで実現可能であり、出力部102は、ＣＰＵ501が出力装置505を利用することで実現可能であり、通信部103は、ＣＰＵ501が通信装置504を利用することで実現可能である。
【００４４】
この所定のプログラムは、読書装置507を介して記憶媒体508から、あるいは、通信装置504を介してネットワークから、外部記憶装置503に記憶(ダウンロード)され、それから、メモリ502上にロードされて、ＣＰＵ501により実行されるようにしてもよい。また、読書装置507を介して、記憶媒体508から、あるいは通信装置504を介してネットワークから、メモリ502上に直接ロードされ、ＣＰＵ501により実行されるようにしてもよい。
【００４５】
図３は、検索クライアント200の機能概略図である。図示するように、検索クライアント200は、制御部210と、記憶部220と、入力部201と、出力部202と、通信部203とを備える。
【００４６】
記憶部220は、検索クエリ記憶部230と、秘密鍵記憶部250と、パラメータ記憶部260と、受信データ記憶部270と、一時情報記憶部280とを備える。
【００４７】
検索クエリ記憶部230には、ＤＢサーバ300に送信するデータである、送信文を特定する情報が記憶される。ここで、本実施形態においては、検索クライアント200が、入力部201を介して受け付けた平文検索クエリ231を特定する情報と、ＤＢサーバ300に送信する秘匿検索クエリ232と、平文検索クエリ231と秘匿検索クエリ232の属性233を特定する情報とが記憶される。
【００４８】
秘密鍵記憶部250には、安全性の観点から検索クライアント200が秘密に管理すべき、秘密鍵251を特定する情報が記憶される。ここで、本実施形態においては、暗号化部212に入力する秘密鍵251と、復号化部213に入力する秘密鍵251と、擬似乱数生成部214に入力する秘密鍵251と、圧縮関数部215に入力する秘密鍵251とを特定する情報が記憶される。
【００４９】
パラメータ記憶部260には、データの秘匿化と秘匿化解除とに用いるパラメータを特定する情報が記憶される。ここで、本実施形態においては、準同型関数部216に入力する関数パラメータ261を特定する情報と、基本演算部217に入力する検査パラメータ262を特定する情報とが記憶される。また、安全性の観点から、関数パラメータ261は、検索クライアント200が秘密に管理すべき情報である。
【００５０】
受信データ記憶部270には、通信部203を介して受信したデータを特定する情報が記憶される。ここで、本実施形態においては、受信データ記憶部270には、通信部203を介してＤＢサーバ300から受信したデータを特定する情報が、秘匿登録データ271として記憶される。また、秘匿登録データ271から、秘匿化を解除したデータを、平文登録データ272として受信データ記憶部270に記憶する処理を行う。
【００５１】
一時情報記憶部280には、制御部210での処理で必要となる情報が記憶される。
【００５２】
制御部210は、全体処理部211と、暗号化部212と、復号化部213と、擬似乱数生成部214と、圧縮関数部215と、準同型関数部216と、基本演算部217とを備える。
【００５３】
全体処理部211は、検索クライアント200における全ての処理を制御する。
【００５４】
例えば、本実施形態において、全体処理部211は、入力部201を介して入力を受け付けた情報を、検索クエリ記憶部230に平文検索クエリ231として記憶する処理を行う。
【００５５】
また、本実施形態において、全体処理部211は、平文検索クエリ231を出力部202に表示する処理を行う。
【００５６】
また、本実施形態において、全体処理部211は、検索クエリ記憶部230に記憶した平文検索クエリ231を読み込み、それぞれ、暗号化部212と、擬似乱数生成部214と、圧縮関数部215と、準同型関数部216と、基本演算部217とに入力し、出力されたデータを秘匿検索クエリ232として検索クエリ記憶部230に記憶する処理を行う。
【００５７】
また、本実施形態において、全体処理部211は、通信部203を介して、属性233と秘匿検索クエリ232をＤＢサーバ300に送信する処理を行う。
【００５８】
また、本実施形態において、全体処理部211は、通信部203を介して、秘匿登録データ271をＤＢサーバ300から受信する処理を行う。
【００５９】
また、本実施形態において、全体処理部211は、通信部203を介して、受信した秘匿登録データ271を受信データ記憶部270に秘匿登録データ271として記憶する処理を行う。
【００６０】
また、本実施形態において、全体処理部211は、受信データ記憶部270に記憶した秘匿登録データ271を読み込み、それぞれ、復号化部213と、圧縮関数部215と、準同型関数部216と、基本演算部217とに入力し、出力されたデータを平文登録データ272として受信データ記憶部270に記憶する処理を行う。
【００６１】
また、本実施形態において、全体処理部211は、平文登録データ272を出力部202に表示する処理を行う。
【００６２】
さらに、全体処理部211は、ＤＢサーバ300より、通信部203を介して受信したデータを、一時情報記憶部280に記憶する処理と、出力部202に表示する処理を行う。
【００６３】
暗号化部212は、入力されたデータを暗号化したデータを出力する処理を行う。
【００６４】
例えば、本実施形態においては、全体処理部211からデータと秘密鍵251が入力され、秘密鍵251を用い、暗号化したデータを出力する処理を行う。
【００６５】
復号化部213は、入力されたデータを復号化したデータを出力する処理を行う。
【００６６】
例えば、本実施形態においては、全体処理部211からデータと秘密鍵251が入力され、秘密鍵251を用い、復号化したデータを出力する処理を行う。
【００６７】
擬似乱数生成部114は、擬似乱数を出力する処理を行う。
【００６８】
例えば、擬似乱数生成部214は、温度、時間、電力量、等の物理現象から、乱数を出力する。
【００６９】
本実施形態においては、擬似乱数生成部214は、全体処理部211から入力された秘密鍵251を用い、擬似乱数を出力する。また、秘密鍵251のデータ値は新しいデータ値に更新され、再び、全体処理部211により秘密鍵記憶部250に記憶される。
【００７０】
例えば、本実施形態においては、全体処理部211から入力された秘密鍵251を用い、擬似乱数を出力する処理を行う。
【００７１】
圧縮関数部215は、入力されたデータを圧縮したデータを出力する処理を行う。
【００７２】
例えば、本実施形態においては、全体処理部211から入力されたデータを固定長（ｈビット）の別のデータに変換し、出力する処理を行う。
【００７３】
準同型関数部216は、入力されたデータに対し、関数計算の出力結果をデータとして出力する処理を行う。
【００７４】
例えば、本実施形態においては、全体処理部211から入力されたデータを準同型の性質を有する関数の入力値とみなし、全体処理部211から入力された関数パラメータ261を用いて、関数計算の出力値をバイナリ列で表現した固定長（ｆビット）のデータに変換する処理を行う。
【００７５】
ただし、準同型関数は、関数Ｆと、入力変数ｘ、入力変数ｙに対し、式（2）が成り立つ場合を示すが、ビット毎の排他的論理和であるＸＯＲ演算以外の演算記号で準同型性が成り立つ時も、本実施形態は同様に実施できる。
【００７６】
基本演算部217は、加算、減算、比較算等の基本的な算術演算に関する処理を行う。
【００７７】
例えば、本実施形態においては、基本演算部217は、全体処理部211から入力された２つのデータのバイナリ値（２進数）の減算結果を、データとして出力する処理を行う。
【００７８】
以上に示した検索クライアント200は、例えば、図５（コンピュータの概略図）に示すような、ＣＰＵ501と、メモリ502と、ＨＤＤ等の外部記憶装置503と、ＣＤやＤＶＤ等の可搬性を有する記憶媒体508に対して情報を読み書きする読書装置507と、キーボードやマウス等の入力装置506と、ディスプレイ等の出力装置505と、通信ネットワークに接続するためのＮＩＣ等の通信装置504と、これらを連結するシステムバス等の内部通信線(システムバスという)と、を備えた一般的なコンピュータで実現できる。
【００７９】
例えば、記憶部220は、ＣＰＵ501がメモリ502または外部記憶装置503を利用することにより実現可能であり、制御部210と制御部210に含まれる各処理部は、外部記憶装置503に記憶されている所定のプログラムをメモリ502にロードしてＣＰＵ501で実行することで実現可能であり、入力部201は、ＣＰＵ501が入力装置506を利用することで実現可能であり、出力部202は、ＣＰＵ501が出力装置505を利用することで実現可能であり、通信部203は、ＣＰＵ501が通信装置504を利用することで実現可能である。
【００８０】
この所定のプログラムは、読書装置507を介して記憶媒体508から、あるいは、通信装置504を介してネットワークから、外部記憶装置503に記憶(ダウンロード)され、それから、メモリ502上にロードされて、ＣＰＵ501により実行されるようにしてもよい。また、読書装置507を介して、記憶媒体508から、あるいは通信装置504を介してネットワークから、メモリ502上に直接ロードされ、ＣＰＵ501により実行されるようにしてもよい。
【００８１】
図４は、ＤＢサーバ300の機能概略図である。図示するように、ＤＢサーバ300は、制御部310と、記憶部320と、入力部301と、出力部302と、通信部303と、を備える。
【００８２】
記憶部320は、パラメータ記憶部360と、秘密鍵記憶部350と、データベース記憶部340と、検索クエリ記憶部330と、一時情報記憶部380とを備える。
【００８３】
パラメータ記憶部360には、秘匿検索クエリ332とデータベース341の関係の検査に用いる、パラメータを特定する情報が記憶される。ここで、本実施形態においては、準同型関数部316に入力する関数パラメータ361を特定する情報が記憶される。また、安全性の観点から、関数パラメータ361はＤＢサーバ300が秘密に管理すべき情報である。
【００８４】
秘密鍵記憶部350には、安全性の観点からＤＢサーバ300が秘密に管理すべき、秘密鍵351を特定する情報が記憶される。ここで、本実施形態においては、復号化部313に入力する秘密鍵351とを特定する情報が記憶される。
【００８５】
データベース記憶部340には、通信部303を介して受信した登録データを特定する情報が記憶される。ここで、本実施形態においては、通信部303を介して登録クライアント100から受信した情報を、データベース記憶部340にデータベース341の構成情報として記憶する処理を行う。
【００８６】
検索クエリ記憶部330には、通信部303を介して受信した検索クエリを特定する情報が記憶される。ここで、本実施形態においては、通信部303を介して検索クライアント200から受信した情報を、検索クエリ記憶部330に秘匿検索クエリ332として記憶する処理を行う。
【００８７】
一時情報記憶部380には、制御部310での処理で必要となる情報が記憶される。
【００８８】
制御部310は、全体処理部311と、復号化部313と、圧縮関数部315と、準同型関数部316と、基本演算部317と、を備える。
【００８９】
全体処理部311は、ＤＢサーバ300における全ての処理を制御する。
【００９０】
例えば、本実施形態において、全体処理部311は、通信部303を介して秘匿登録データ131を、登録クライアント100から受信する処理を行う。
【００９１】
また、本実施形態において、全体処理部311は、通信部303を介して受信した秘匿登録データ131を、データベース記憶部340にデータベース341の構成情報として記憶する処理を行う。
【００９２】
また、本実施形態において、全体処理部311は、通信部303を介して秘匿検索クエリ332を、検索クライアント200から受信する処理を行う。
【００９３】
また、本実施形態において、全体処理部311は、通信部303を介して受信した秘匿検索クエリ332を、検索クエリ記憶部330に記憶する処理を行う。
【００９４】
また、本実施形態において、全体処理部311は、検索クエリ記憶部330に記憶した秘匿検索クエリ332を読み込み、それぞれ、復号化部313と、圧縮関数部315と、準同型関数部316と、基本演算部317とに入力し、出力されたデータを、通信部303を介して、検索クライアント200に送信する処理を行う。
【００９５】
さらに、全体処理部311は、検索クライアント200または登録クライアント100より、通信部303を介して受信したデータに関する情報を、一時情報記憶部380に記憶する処理と、出力部302に表示する処理を行う。
【００９６】
復号化部313は、入力されたデータを復号化したデータを出力する処理を行う。
【００９７】
例えば、本実施形態においては、全体処理部311からデータと秘密鍵351が入力され、秘密鍵351を用い、復号化したデータを出力する処理を行う。
【００９８】
圧縮関数部315は、入力されたデータを圧縮したデータを出力する処理を行う。
【００９９】
例えば、本実施形態においては、全体処理部311から入力されたデータを固定長（ｈビット）の別のデータに変換し、出力する処理を行う。
【０１００】
準同型関数部316は、入力されたデータに対し、関数計算の出力結果をデータとして出力する処理を行う。
【０１０１】
例えば、本実施形態においては、全体処理部311から入力されたデータを、準同型の性質を有する関数の入力値とみなし、全体処理部311から入力された関数パラメータ361を用いて、関数計算の出力値をバイナリ列で表現したデータを固定長（ｆビット）のデータに変換する処理を行う。
【０１０２】
ただし、準同型関数は、関数Ｆと、入力変数ｘ、入力変数ｙに対し、式（2）が成り立つ場合を示すが、ビット毎の排他的論理和であるＸＯＲ演算以外の演算記号で準同型性が成り立つ時も、本実施形態は同様に実施できる。
【０１０３】
基本演算部317は、加算、減算、比較算等の基本的な算術演算に関する処理を行う。
【０１０４】
例えば、本実施形態においては、基本演算部317は、全体処理部311から入力された２つのデータのバイナリ値（２進数）の減算結果をデータとして出力する処理を行う。
【０１０５】
また、本実施形態においては、基本演算部317は、全体処理部311から入力された２つのデータのバイナリ値（２進数）の比較結果をデータとして出力する処理を行う。
【０１０６】
以上に示したＤＢサーバ300は、例えば、図５（コンピュータの概略図）に示すような、ＣＰＵ501と、メモリ502と、ＨＤＤ等の外部記憶装置503と、ＣＤやＤＶＤ等の可搬性を有する記憶媒体508に対して情報を読み書きする読書装置507と、キーボードやマウス等の入力装置506と、ディスプレイ等の出力装置505と、通信ネットワークに接続するためのＮＩＣ等の通信装置504と、これらを連結するシステムバス等の内部通信線(システムバスという)とを備えた一般的なコンピュータで実現できる。
【０１０７】
例えば、記憶部120、220、320は、ＣＰＵ501がメモリ502または外部記憶装置503を利用することにより実現可能であり、制御部110、210、310と制御部110、210、310に含まれる各処理部は、外部記憶装置503に記憶されている所定のプログラムをメモリ502にロードしてＣＰＵ501で実行することで実現可能であり、入力部101、201、301は、ＣＰＵ501が入力装置506を利用することで実現可能であり、出力部102、202、302は、ＣＰＵ501が出力装置505を利用することで実現可能であり、通信部103、203、303は、ＣＰＵ501が通信装置504を利用することで実現可能である。
【０１０８】
この所定のプログラムは、読書装置507を介して記憶媒体508から、あるいは、通信装置504を介してネットワークから、外部記憶装置503に記憶(ダウンロード)され、それから、メモリ502上にロードされて、ＣＰＵ501により実行されるようにしてもよい。また、読書装置507を介して記憶媒体508から、あるいは通信装置504を介してネットワークから、メモリ502上に直接ロードされ、ＣＰＵ501により実行されるようにしてもよい。
【０１０９】
図６は、登録クライアント100の出力部102の表示内容600を例示した図である。図示するように、登録クライアント100は、管理方法の選択部610と、管理フォーム部620と、実行と表示されたボタンを指す実行ボタン650と、クリアと表示されたボタンを指すクリアボタン660とを備える。
【０１１０】
管理方法の選択部610は、データの登録と、データの更新と、データの削除となどの、データの管理に関する項目から構成される。例えば、本実施形態では、データ追加と、データ更新と、データ削除とを特定するラジオボタンを備える。また、入力部101を介し、各項目が選択可能である。
【０１１１】
管理フォーム部620は、管理方法の選択部610で特定された項目である、データの登録と、データの更新と、またはデータの削除とに応じて扱う、データの種類を示す属性621と、データの詳細内容を入力する入力フォーム622から構成される。例えば、本実施形態では、番号と、氏名と、Ｅメールと、所属部署とを指す属性621と、番号の入力用と、氏名の入力用と、Ｅメールの入力用と、所属部署の入力用とに設計された入力フォーム622を備える。各入力フォーム622に入力された情報は、記憶部120の一時情報記憶部180に記憶される。
【０１１２】
クリアボタン660は、入力部101を介し、選択可能である。例えば、本実施形態では、クリアボタン660が選択されると、各入力フォーム622に入力された情報を消去する。
【０１１３】
実行ボタン650は、入力部101を介し、選択可能である。例えば、本実施形態では、実行ボタン650が選択されると、管理方法の選択部610で特定された項目と各フォームに入力された情報を基に、秘匿登録データ131を作成し、ＤＢサーバ300へ送信する処理を行う。以下では、管理方法の選択部610で、特定された項目がデータ登録である場合を説明するが、データ更新と、データ削除とが特定された場合も、同様の処理を行う。
【０１１４】
管理方法の選択部610で、特定された項目がデータ登録である場合に、実行ボタン650が選択された場合に、実施する秘匿登録データ131の処理手順をＳ701からＳ715に示す。
【０１１５】
図７Ａは、本実施形態において、登録クライアント100が、出力部102に出力した入力フォーム622に入力された情報を基に作成する、連結データ703のデータ構成を示すブロック図の例である。
【０１１６】
また、図７Ｂは、本実施形態において、登録クライアント100が、秘匿登録データ712を作成する過程において作成する、連結データ704のデータ構成を示すブロック図の例である。
【０１１７】
また、図７Ｃは、本実施形態において、登録クライアント100が作成する、秘匿登録データ712のデータ構成を示すブロック図である。
【０１１８】
以下では、図７Ａと、図７Ｂと、図７Ｃとを用い、入力フォーム622に入力されたデータ値によらず、登録クライアント100が、毎回、データ値の異なる秘匿登録データ712を作成する処理手順を説明する。
【０１１９】
登録クライアント100の全体処理部111は、入力フォーム622に入力された情報を平文登録データ701として、記憶部120の登録データ記憶部130に記憶する処理を行う。このとき、平文登録データ701は、登録クライアント100の一時情報記憶部180にｍビットのバイナリ表現で構成されたデータとして記憶される。
【０１２０】
登録クライアント100の全体処理部111は、パラメータ記憶部160に記憶された検査パラメータ162を読み込み、誤り検査データ702として出力する処理を行う。このとき、出力された誤り検査データ702は、登録クライアント100の一時情報記憶部180に、ｅビットのデータとして記憶される。
【０１２１】
登録クライアント100の全体処理部111は、平文登録データ701と誤り検査データ702を連結する処理を行う (S701) 。
【０１２２】
連結処理では、平文登録データ701の各所に、分割した誤り検査データ702を挿入してもよい。例えば、平文登録データ701の初め（ヘッダ）と終わり（フッタ）に、誤り検査データ702を挿入してもよい。また、誤り検査データ702に平文登録データ701を乗算で掛け合わせるなど、混合させてもよい。
【０１２３】
以下では、図７Ａに示すように、登録クライアント100において、全体処理部111が入力した平文登録データ701の末尾に、誤り検査データ702を連結し、連結データ703を一つのデータとみなした場合を扱う。このとき、登録クライアント100の一時情報記憶部180には、連結データ703は（ｍ＋ｅ）ビットのデータとして記憶される。ただし、連結処理は、この場合に限定されるわけではなく、他の連結処理でも、同様に実施できる。
【０１２４】
次に、図７Ｂに示すように、登録クライアント100が作成する連結データ704のデータ構成を説明する。
【０１２５】
登録クライアント100の全体処理部111は、平文登録データ701と誤り検査データ702を連結したデータである連結データ703と、秘密鍵記憶部150に記憶された秘密鍵151とを暗号化部112へ入力する処理を行う(S702)。
【０１２６】
登録クライアント100の暗号化部112は、入力されたデータを暗号化し、データＣR705を出力する処理を行う(S703)。
【０１２７】
登録クライアント100において、全体処理部111が入力した連結データ703を暗号化部112が暗号化し、出力したデータをデータＣR705とみなす。このとき、データＣR705は、登録クライアント100の一時情報記憶部180には、ｃビットのデータとして記憶される(S704)。
【０１２８】
なお、データＣR705は、連結データ703に依存、即ち、入力フォーム622の入力情報に依存して構わない。例えば、同一のデータ値を持つ連結データ703からは、同一のデータＣR705を出力してもよい。
【０１２９】
登録クライアント100の全体処理部111は、秘密鍵記憶部150から秘密鍵151を読み出し、秘密鍵151を、擬似乱数生成部114に入力する処理を行う(S705)。
【０１３０】
登録クライアント100の擬似乱数生成部114は、入力された秘密鍵151を用い、擬似乱数を出力する処理を行う。このとき、擬似乱数は、登録クライアント100の一時情報記憶部180には、ｒビットのデータＰＲ706として記憶される(S706)。
【０１３１】
擬似乱数生成部114が出力する擬似乱数は、連結データ703、データＣR705に依存しない。従って、入力フォーム622の入力情報に依存せず、毎回、データ値の異なるデータＰＲ706を作成できる。
【０１３２】
登録クライアント100の全体処理部111は、秘密鍵記憶部150から秘密鍵151を読み出し、秘密鍵151と乱数生成部から出力されたデータＰＲ706を連結したデータを、圧縮関数部115に入力する処理を行う(S707)。
【０１３３】
登録クライアント100の圧縮関数部115は、入力されたデータを変換し、ハッシュ値を出力する処理を行う。このとき、ハッシュ値は、登録クライアント100の一時情報記憶部180には、ｈビットのデータＨＲ707として記憶される(S708)。
【０１３４】
データＨＲ707は、圧縮関数の性質から、乱数とみなせる。データＨＲ707は、連結データ703、データＣR705に依存しない。従って、データＰＲ706同様、入力フォーム622の入力情報に依存せず、毎回、データ値の異なるデータＨＲ707を作成できる。
【０１３５】
登録クライアント100の全体処理部111は、データＨＲ707と、パラメータ記憶部160に記憶された関数パラメータ161とを準同型関数部116に入力する(S709)。
【０１３６】
登録クライアント100の準同型関数部116は、入力されたデータを準同型の性質を有する関数の入力値とみなし、関数パラメータ161を用いて、関数計算の出力値をバイナリ列で表現した準同型関数値を出力する処理を行う。このとき、準同型関数値は、登録クライアント100の一時情報記憶部180には、ｆビットのデータＦＲ708として記憶される(S710)。
【０１３７】
なお、準同型関数をfuncとした場合、その入力値であるデータＨＲ707、出力値であるデータＦＲ708には、式（3）が成り立つ（ただし、関数パラメータ161の記述は省略）。
ＦＲ ＝ func（ＨＲ）      （3）
データＦＲ708は、準同型関数部116が処理する準同型関数の性質から、入力されたデータ値が乱数の場合、出力も乱数とみなせる。また、データＦＲ708は、連結データ703と、データＣR705に依存しない。従って、データＨＲ707同様、入力フォーム622の入力情報に依存せず、毎回、データ値の異なるデータＦＲ707を作成できる。
【０１３８】
登録クライアント100の全体処理部111は、準同型関数部116から出力されたデータＦＲ708を、圧縮関数部115へ入力する処理を行う(S711)。
【０１３９】
登録クライアント100の圧縮関数部115は、入力されたデータを変換し、ハッシュ値を出力する処理を行う。このとき、ハッシュ値は、登録クライアント100の一時情報記憶部180には、ｇビットのデータＧＲ709として記憶される(S712)。
【０１４０】
データＧＲ709は、圧縮関数の性質から、乱数である。従って、データＦＲ707と、データＨＲ707同様、入力フォーム622の入力情報に依存せず、毎回、データ値の異なるデータＧＲ709を作成できる。また、圧縮関数の性質から、逆像は計算困難であるため、データＧＲ709をＤＢサーバ300に登録しても、データの安全性に影響を与えない。
【０１４１】
図７Ｃは、本実施形態において、登録クライアント100が作成する秘匿登録データ712のデータ構成を示すブロック図である。
【０１４２】
登録クライアント100の全体処理部111は、データＨＲ707とデータＣR705とを基本演算部117へ入力する処理を行う(S713)。
【０１４３】
登録クライアント100の基本演算部117は、入力されたデータＨＲ707とデータＣR705とのビット毎の排他的論理和であるＸＯＲ算を計算し、その計算結果を、データＤR711として出力する処理を行う(S714)。
【０１４４】
S714のxor算により、データＨＲ707とデータＣＲ705とデータＤＲ711とは式（4）を満たす。
ＤR ＝ＨＲ xor ＣR      （4）
Ｓ714の計算は、連結データ703やデータＣR705に依存しない、乱数であるデータＨＲ707を用いている。従って、連結データ703とデータＣR705の関係が一意に定まる場合でも、毎回、データ値が異なる、データＨＲ707を用いれば、異なるデータ値のデータＤR711が得られる。
【０１４５】
登録クライアント100の全体処理部111は、データＰＲ706とデータＤＲ711とデータＧＲ709とを連結し、作成したデータを、秘匿登録データ712として登録データ記憶部130へ記憶する処理を行う(S715)。
【０１４６】
秘匿登録データ712は、連結データ703やデータＣR705に依存しない乱数であるデータＰＲ706、データＤＲ711、データＧＲ709を用いており、毎回、異なるデータ値が得られる。その結果、データＰＲ706とデータＤＲ711とデータＧＲ709とを連結した秘匿登録データ712は、連結データ703とデータＣR705とは独立している。即ち、入力フォーム622の入力情報に依存せず、毎回、データ値の異なる秘匿登録データ712を作成できる。
【０１４７】
なお、上記の処理手順は、固定されたものではなく、処理手順を変更してもよい。例えば、S713とS714の処理手順を変更し、S713でデータＰＲ706とデータＨＲ707とデータＧＲ709を連結してから、S714でデータＨＲ707とデータCR705とのXOR算を計算してもよい。同様に、他の処理手順を変更してもよい。
【０１４８】
また、上記の各処理を担当する制御部110は固定されたものではなく、担当する制御部110を変更してもよい。例えば、S711でデータＦＲ708を、圧縮関数部115ではなく、暗号化部112にデータＦＲ708を入力してもよく、S712では、暗号化部112から出力されたデータを、データＧＲ709として一時情報記憶部180に記憶してもよい。
【０１４９】
また、秘匿登録データ712のデータ構成を変更し、それに併せて処理を変更してもよい。例えば、データＰＲ706に関する情報は、記憶部120に記憶し、秘匿登録データ712に含まないように構成しても構わない。この時、S706が出力するデータをデータＨＲ706とみなし、S707とS708に係る処理は削除可能である。また、この時、S715で登録クライアント100の全体処理部111は、秘匿登録データ712として、データＤＲ711とデータＧＲ709とを連結すればよい。
【０１５０】
図８は、本実施形態において、ネットワーク400を経由し、登録クライアント100が、秘匿登録データ132をＤＢサーバ300へ登録する処理を示すシーケンス図である。
【０１５１】
登録クライアント100は、入力部101を経由し、ユーザからフォームへ入力された情報を一時情報記憶部180に記憶する処理を行う（Ｓ８０１）。
【０１５２】
登録クライアント100は、入力部101を経由し、ユーザにより実行ボタン650が選択されたことを検知し、フォームに入力された情報を、平文登録データ131として記憶部120へ記憶する処理を行う（Ｓ８０２）。
【０１５３】
登録クライアント100は、制御部110により秘匿登録データ132を作成し、記憶部120へ記憶する処理を行う（Ｓ８０３）。
【０１５４】
登録クライアント100は、通信部103からネットワーク400を経由し、属性133と秘匿登録データ132を、ＤＢサーバ300へ送信する処理を行う（Ｓ８０４）。
【０１５５】
ＤＢサーバ300は、通信部303からネットワーク400を経由し、登録クライアント100が送信した属性133と秘匿登録データ132を受信する処理を行う（Ｓ８０５）。
【０１５６】
ＤＢサーバ300は、制御部310により受信した属性133を用い、秘匿登録データ132を、データベース341の構成情報として記憶部320へ記憶する処理を行う（Ｓ８０６）。
【０１５７】
ＤＢサーバ300は、秘匿登録データ132の登録処理の成否を、通信部303からネットワーク400を経由し、登録サーバへ送信する処理を行う（Ｓ８０７）。
【０１５８】
登録クライアント100は、通信部103からネットワーク400を経由し、ＤＢサーバ300が送信した秘匿登録データ132の登録処理の成否を受信する処理を行う（Ｓ８０８）。
【０１５９】
登録クライアント100は、出力部102を経由し、ユーザに、登録処理の成否を含む登録情報について表示する処理を行う（Ｓ８０９）。
【０１６０】
図９Ａは、ＤＢサーバ300における、記憶部320のデータベース記憶部340に記憶されるデータベース341の管理状態を例示した構成図である。
【０１６１】
例えば、本実施形態において、ＤＢサーバ300における、データベース341は、番号と、氏名と、Eメールとなどを示す属性901と、属性901に関連付けられた秘匿登録データ902(d0、d1、d2、・・・)とから構成されている。
【０１６２】
図１０は、検索クライアント200の出力部202の表示内容1000を例示した図である。図示するように、検索クライアント200は、検索項目部1010と、検索フォーム部1020と、検索と表示されたボタンを指す検索ボタン1050と、クリアと表示されたボタンを指すクリアボタン1060とを備える。
【０１６３】
検索方法の選択部は、検索対象のデータの種類に関する項目から構成される。例えば、本実施形態では、番号と、氏名と、Ｅメールと、所属部署とを特定するラジオボタンを備える。また、入力部201を介し、各項目が複数選択可能である。
【０１６４】
検索フォーム部1020は、検索方法の選択部で特定された属性1011である、番号と、氏名と、Ｅメールと、所属部署との詳細内容を入力する入力フォーム1022から構成される。例えば、本実施形態では、番号の入力用と、氏名の入力用と、Ｅメールの入力用と、所属部署の入力用とに設計された入力フォーム1022を複数備える。各入力フォーム1022に入力された情報は、記憶部220の一時情報記憶部280に記憶される。
【０１６５】
クリアボタン1060は、入力部201を介し、選択可能である。例えば、本実施形態では、クリアボタン1060が選択されると、各入力フォーム1022の入力情報を消去する。
【０１６６】
検索ボタン1050は、入力部201を介し、選択可能である。例えば、本実施形態では、検索ボタン1050が選択されると、検索方法の選択部で特定された属性1011と入力フォーム1022に入力された情報を基に、秘匿検索クエリ232を作成し、ＤＢサーバ300へ送信する処理を行う。以下では、検索方法の選択部で、ただ一つの属性1011（例えば氏名）が選択された場合を示すが、複数の入力フォーム1022に情報が入力された場合と、複数の属性1011が選択された場合も、同様の処理で実施できる。
【０１６７】
検索方法の選択部で、特定された属性1011が、ただ一つである場合に、検索ボタン1050が選択された場合の処理手順は、Ｓ1101〜Ｓ1112に従う。
【０１６８】
図１１Ａは、本実施形態において、検索クライアント200が、出力部202に出力した入力フォーム1022に入力された情報を基に作成する連結データ1103のデータ構成を示すブロック図の例である。
【０１６９】
また、図１１Ｂは、本実施形態において、検索クライアント200が、秘匿検索クエリ1111を作成する過程において作成する連結データ1104のデータ構成を示すブロック図の例である。
【０１７０】
また、図１１Ｃは、本実施形態において、検索クライアント200が作成する連結データ1108のデータ構成を示すブロック図である。
以下では、図１１Ａと、図１１Ｂと、図１１Ｃとを用い、入力フォーム1022に入力されたデータ値によらず、検索クライアント200が、毎回、データ値の異なる秘匿検索クエリ1111を作成する処理手順を説明する。
【０１７１】
検索クライアント200の全体処理部211は、入力フォーム1022に入力された情報を、平文検索クエリ1101として記憶部220の検索クエリ記憶部230に記憶する処理を行う。このとき、平文検索クエリ1101は、検索クライアント200の一時情報記憶部280にｍビットのバイナリ表現で構成されたデータとして記憶される。
【０１７２】
検索クライアント200の全体処理部211は、パラメータ記憶部260に記憶された検査パラメータ262を読み込み、誤り検査データ1102として出力する処理を行う。このとき、出力された誤り検査データ1102は、検索クライアント200の一時情報記憶部280に、ｅビットのデータとして記憶される。
【０１７３】
検索クライアント200の全体処理部211は、平文検索クエリ1101と誤り検査データ1102を連結する処理を行う(S1101)。
【０１７４】
連結処理では、平文検索クエリ1101の各所に、分割した誤り検査データ1102を挿入してもよい。例えば、平文検索クエリ1101の初め（ヘッダ）と終わり（フッタ）に、誤り検査データ1102を挿入してもよい。また、誤り検査データ1102に平文検索クエリ1101を乗算で掛け合わせるなど、混合させてもよい。
【０１７５】
以下では、図１１Ａに示すように、検索クライアント200において、全体処理部211が入力した平文検索クエリの末尾に誤り検査データ1102を連結し、連結データ1103を一つのデータとみなした場合を扱う。このとき、検索クライアント200の一時情報記憶部280には、連結データ1103は（ｍ＋ｅ）ビットのデータとして記憶される。ただし、連結処理は、この場合に限定されるわけではなく、他の連結処理でも、同様に実施できる。
【０１７６】
次に、図11Ｂに示すように、検索クライアント200が作成する連結データ1104のデータ構成を説明する。
【０１７７】
検索クライアント200の全体処理部211は、平文検索クエリ1101と誤り検査データ1102を連結したデータである連結データ1103と、秘密鍵記憶部250に記憶された秘密鍵251とを暗号化部212へ入力する処理を行う（S1102）。
【０１７８】
検索クライアント200の暗号化部212は、入力されたデータを暗号化し、データＣS1105を出力する処理を行う(S1103)。
【０１７９】
検索クライアント200において、全体処理部211が入力した連結データ1103を暗号化部212が暗号化し、出力したデータをデータＣS1105とみなして扱えばよい。このとき、データＣS1105は、検索クライアント200の一時情報記憶部280に、ｃビットのデータとして記憶される(S1104)。
【０１８０】
なお、データＣS1105は、連結データ1103に依存、即ち、入力フォーム1022の入力情報に依存してもよい。例えば、同一のデータ値を持つ連結データ1103からは、同一のデータＣS1105を出力してもよい。
【０１８１】
検索クライアント200の全体処理部211は、秘密鍵記憶部250から秘密鍵251を読み出し、秘密鍵251を擬似乱数生成部214に入力する処理を行う(S1105)。
【０１８２】
検索クライアント200の擬似乱数生成部214は、入力された秘密鍵251を用い、擬似乱数を出力する処理を行う。このとき、擬似乱数は、検索クライアント200の一時情報記憶部280に、ｒビットのデータＰＳ1106として記憶される(S1106)。
【０１８３】
擬似乱数生成部214が出力する擬似乱数は、連結データ1103、データＣS1105に依存しない。従って、入力フォーム1022の入力情報に依存せず、毎回、データ値の異なる、データＰS1106を作成できる。
【０１８４】
データＰS1106は、擬似乱数生成関数の性質から、乱数を出力する。また、データＰS1106は、連結データ703、データＣS705に依存しない。従って、データＰS1106は、入力フォーム1022の入力情報に依存せず、毎回、データ値の異なるデータＦＳ1107を作成できる。
【０１８５】
検索クライアント200の全体処理部211は、データＰＳ1106と、パラメータ記憶部260に記憶された関数パラメータ261とを準同型関数部216に入力する(S1107)。
【０１８６】
検索クライアント200の準同型関数部216は、入力されたデータを、準同型の性質を有する関数の入力値とみなし、関数パラメータ261を用いて、関数計算の出力値をバイナリ列で表現した準同型関数値を出力する処理を行う。このとき、準同型関数値は、検索クライアント200の一時情報記憶部280に、fビットのデータＦＳ1107として記憶される(S1108)。
【０１８７】
なお、準同型関数をfuncとした場合、その入力値であるデータＰＳ、出力値であるデータＦＳには、式（5）が成り立つ（ただし、関数パラメータ261の記述は省略）。
ＦＳ ＝ func（ＰＳ）      （5）
データＦＳ1107は、準同型関数部216が処理する準同型関数の性質から、入力されたデータ値が一様に分布する乱数の場合、出力も同様に一様分布する。また、データＦＳ1107は、連結データ1103とデータＣS1104に依存しない。従って、データＰＳ1106同様、入力フォーム1022の入力情報に依存せず、毎回、データ値の異なるデータＦＳ1107を作成できる。
【０１８８】
図11Ｃは、本実施形態において、検索クライアント200が作成する連結データ1108のデータ構成を示すブロック図である。
【０１８９】
検索クライアント200の全体処理部211は、データＰＳ1106とデータＦＳ1107とを連結し、作成した連結データ1104と、データＣS1105とを基本演算部217へ入力する処理を行う(S1109)。
【０１９０】
検索クライアント200の基本演算部217は、入力された連結データ1104と、データＣS1105とのビット毎の排他的論理和であるＸＯＲ算を計算し、その計算結果をデータＤＳ1110として出力する処理を行う(S1110)。
【０１９１】
Ｓ1110の計算は、連結データ1103やデータＣS1105に依存しない、乱数であるデータＰＳ1106を用いている。従って、連結データ1103とデータＣS1105の関係が一意に定まる場合でも、毎回、データ値が異なる、データＰＳ1106を用いれば、異なるデータ値のデータＤＳ1110が得られる。
【０１９２】
検索クライアント200の全体処理部211は、データＤＳ1110とデータＦＳ1107とを連結したデータである連結データ1108と、秘密鍵記憶部250に記憶された秘密鍵251とを暗号化部212へ入力する処理を行う(S1111)。
【０１９３】
検索クライアント200の暗号化部212は、入力されたデータを暗号化し、暗号化したデータを、全体処理部211は、秘匿検索クエリ1111として検索クエリ記憶部230へ記憶する処理を行う(S1112)。
【０１９４】
秘匿検索クエリ1111は、暗号化部に入力された連結データが乱数とみなせるため、出力された秘匿検索クエリ1111も、同様に乱数とみなせる。そのため、検索クライアント200が、例え不正傍受可能なネットワーク400経由で、ＤＢサーバ300に送信しても、秘匿検索クエリ1111は安全である。
【０１９５】
秘匿検索クエリ1111は、連結データ1103やデータＣＳ1105に依存しない、乱数であるデータＰＳ1106とデータＦＳ1107とを用いており、毎回、異なるデータ値が得られる。その結果、データＤＳ1106とデータＦＳ1107とを連結した秘匿検索クエリ1111は、連結データ1103とデータＣR1105とは独立している。即ち、入力フォーム1022の入力情報に依存せず、毎回、データ値の異なる秘匿検索クエリ1111を作成できる。
【０１９６】
なお、上記の処理手順は、固定されたものではなく、処理手順を変更してもよい。例えば、S1109とS1110の処理手順を変更し、S1109でデータＣＳ1105と、データＰＳ1106と、のXOR算を計算してから、S1110でデータＦＳ1107とデータＤＳ1110とを連結してもよい。同様に、他の処理手順を変更してもよい。
【０１９７】
また、上記の各処理を担当する制御部210は固定されたものではなく、担当する制御部210を変更してもよい。例えば、S1105で、擬似乱数生成部214ではなく、圧縮関数部215に秘密鍵251を入力してもよい。
【０１９８】
また、秘匿検索クエリ1111のデータ構成を変更し、それに併せて処理を変更してもよい。例えば、全体処理部211がデータＦＳ1107と、秘密鍵記憶部250に記憶された秘密鍵251とを暗号化部212へ入力する処理を行い(S1111)、暗号化部が出力したデータと、データＤＳ1106とを、連結したデータを、秘匿検索クエリ1111とみなしてもよい (S1112)。
【０１９９】
図１２は、本実施形態において、ネットワーク400を経由し、検索クライアント200が送信した秘匿検索クエリ232を用い、ＤＢサーバ300がデータベース341を検索する処理を示すシーケンス図である。
【０２００】
検索クライアント200は、入力部201を経由し、ユーザから、フォームへ入力された情報を一時情報記憶部280に記憶する処理を行う（Ｓ１２０１）。
【０２０１】
検索クライアント200は、入力部201を経由し、ユーザにより、検索ボタン1050が選択されたことを検知し、フォームに入力された情報を平文検索クエリ231として記憶部220へ記憶する処理を行う（Ｓ１２０２）。
【０２０２】
検索クライアント200は、制御部210により、秘匿検索クエリ232を作成し、記憶部220へ記憶する処理を行う（Ｓ１２０３）。
【０２０３】
検索クライアント200は、通信部203からネットワーク400を経由し、属性233と秘匿検索クエリ232を、ＤＢサーバ300へ送信する処理を行う（Ｓ１２０４）。
【０２０４】
ＤＢサーバ300は、通信部303からネットワーク400を経由し、検索クライアント200が送信した属性233と秘匿検索クエリ232を受信する処理を行う（Ｓ１２０５）。
【０２０５】
ＤＢサーバ300は、制御部310により、属性233を用い、データベース341から、秘匿検索クエリ332に関係する秘匿登録データ902を検索する処理を行う（Ｓ１２０６）。
【０２０６】
ＤＢサーバ300は、秘匿検索クエリ332に該当する検索結果（属性901と秘匿登録データ902の一部を抜粋）を、通信部303からネットワーク400を経由し、検索サーバへ送信する処理を行う（Ｓ１２０７）。
【０２０７】
検索クライアント200は、通信部203からネットワーク400を経由し、ＤＢサーバ300が送信した秘匿検索クエリ232に該当する検索結果を受信する処理を行う（Ｓ１２０８）。
【０２０８】
検索クライアント200は、制御部210により、秘匿検索クエリ232に該当する検索結果から、平文登録データ272を復元する（S1209）。
【０２０９】
検索クライアント200は、出力部202を経由し、抽出した平文登録データ272を記憶部220に記憶する。また、抽出した平文登録データ272を、出力部202に表示する処理を行ってもよい（Ｓ１２１０）。
【０２１０】
本実施形態において、Ｓ１２０６で示した、ＤＢサーバ300の制御部310が秘匿登録データ902を検索する処理手順は、以下、S1301からS1318に従う。
【０２１１】
なお、ＤＢサーバ300の全体処理部311は、受信した属性233に関係する、データベース341の属性901に関連付けられた秘匿登録データ902を検索対象とする。
【０２１２】
図９Ｂは、図９Ａに示した、構成図を用い、ＤＢサーバ300の記憶部320のデータベース記憶部340に記憶された、データベース341における、検索対象を例示した構成図である。
【０２１３】
例えば、受信した属性233が、氏名に関する情報である場合、図９Ｂの太線の実線枠が囲んだ部分が示すように、ＤＢサーバ300の全体処理部311は、データベース341の氏名に関係する属性901を、検索対象の秘匿登録データ902として扱う。
【０２１４】
なお、以下、秘匿登録データ902を検索するS1301からS1318の処理手順は、検索対象である秘匿登録データ902の全て、または検索対象である秘匿登録データ902から任意に抽出した秘匿登録データ902、または一定数の秘匿登録データ902に対して、実施する。
【０２１５】
図１３Ａは、本実施形態において、ＤＢサーバ300が、通信部303から受信した秘匿検索クエリを復号化した、連結データ1301のデータ構成を示すブロック図の例である。
【０２１６】
また、図１３Ｂは、本実施形態において、ＤＢサーバ300が、データベース記憶部340に記憶した、データベース341における、秘匿登録データ1304のデータ構成を示すブロック図の例である。
【０２１７】
また、図１３Ｃは、本実施形態において、ＤＢサーバ300が、連結データ1301を用い、秘匿登録データ1304を検索する過程において作成する連結データ1308のデータ構成を示すブロック図の例である。
【０２１８】
また、図１３Ｄは、本実施形態において、ＤＢサーバ300が、連結データ1301を用い、秘匿登録データ1304を検索する過程において作成する連結データ1311のデータ構成を示すブロック図の例である。
【０２１９】
以下では、図１３Ａと、図１３Ｂと、図１３Ｃと、図１３Ｄとを用い、ＤＢサーバ300が、毎回、データ値の異なる連結データ1301を用いても、正しく秘匿登録データ1304を検索する処理手順を説明する。
【０２２０】
ＤＢサーバ300の全体処理部311は、通信部303を用い、秘匿検索クエリ1300を受信する処理を行う。このとき、ＤＢサーバ300の全体処理部311は、秘匿検索クエリ1300を、検索クエリ記憶部330に記憶する。
【０２２１】
ＤＢサーバ300の全体処理部311は、秘匿検索クエリ1300と、秘密鍵記憶部350に記憶された秘密鍵351とを復号化部313へ入力する処理を行う(S1301)。
【０２２２】
ＤＢサーバ300の復号化部は、入力された秘匿検索クエリ1300を復号化し、連結データ1301を出力する処理を行う(S1302)。このとき、図１３Ａに示すように、連結データ1301は、ＤＢサーバ300の一時情報記憶部280に、（ｈ＋ｆ）ビットのバイナリ表現で構成されたデータとして記憶される。
【０２２３】
ＤＢサーバ300の全体処理部311は、連結データ1301からデータＤＳ1302を取り出す処理を行う（S1303）。
【０２２４】
S1303は、例えば、図１３Ａに示すように、ＤＢサーバ300が、全体処理部311が、連結データ1301から、データＤＳ1302に該当する最初のhビットを、抽出すればよい。
【０２２５】
ＤＢサーバ300の全体処理部311は、データベース記憶部340に記憶されている、データベース341にある秘匿登録データ1304を読み出し、秘匿登録データ1304から、データＤR1306を取り出す処理を行う（S1304）。
【０２２６】
S1304は、例えば、図１３Ｂに示すように、ＤＢサーバ300が、全体処理部311が、秘匿登録データ1304から、データＰＲ1305に該当する最初のｒビットと、データＧＲ1307に該当する最後のｇビットとを取り除いたデータを、データＤR1306とみなして扱えばよい。
【０２２７】
図１３Ｃは、本実施形態において、ＤＢサーバ300が作成する連結データ1308のデータ構成を示すブロック図である。
【０２２８】
登録クライアント100がデータＣＲ705の確率的暗号化に利用したデータＨＲ707と、検索クライアント200がデータＣＳ1105の確率的暗号化に利用したデータＰＳ1106と、の相関関係が取れるかを、準同型関数部316を利用して検査する。
【０２２９】
ＤＢサーバ300の全体処理部311は、データＤＲ711とデータＤＳ1302とを基本演算部317へ入力する処理を行う(S1305)。
【０２３０】
登録クライアント100の基本演算部117は、入力されたデータＤＲ1309とデータＤS1310とのビット毎の排他的論理和であるＸＯＲ算を計算し、その計算結果を連結データ1308として出力する処理を行う(S1306)。
【０２３１】
S1305とS1306では、登録クライアント100の入力フォーム622に入力された情報を隠すためのデータＨＲ707と、検索クライアント200が入力フォーム1022に入力された情報を隠すためのデータＰＳ1106との関係式を導く。
【０２３２】
実際、S1306のxor算により、登録クライアント100と検索クライアント200の入力情報が等しい、即ち、データＣｓ705とデータＣＲ1105のデータ値が等しい場合、以下の式（6）が導ける。
Ｄｓ xor ＤＲ = ＰＳ xor ＨＲ （ただし、Ｃｓ＝ＣＲのとき）      (6)
図１３Ｄは、本実施形態において、ＤＢサーバ300が作成する連結データ1311のデータ構成を示すブロック図の例である。
【０２３３】
ＤＢサーバ300の全体処理部311は、連結データ1308と、パラメータ記憶部360に記憶された関数パラメータ361とを準同型関数部316に入力する(S1307)。
【０２３４】
ＤＢサーバ300の準同型関数部316は、入力されたデータを準同型の性質を有する関数の入力値とみなし、関数パラメータ361を用いて、関数計算の出力値をバイナリ列で表現した準同型関数値を出力する処理を行う。このとき、準同型関数値は、ＤＢサーバ300の一時情報記憶部380には、hビットのデータＦＤ1312として記憶される(S1308)。
ＦＤ = Ｆ(ＰＳ xor ＨＲ) =ＦＳ xor ＦR      (7)
なお、式(7)は、式(3)と、式（5）と、式（6）とより導ける。
【０２３５】
ＤＢサーバ300の全体処理部311は、連結データ1301からデータＦＳ1303を取り出す処理を行う（S1309）。
【０２３６】
S1309は、例えば、図１３Ａに示すように、ＤＢサーバ300が、全体処理部311が入力した連結データ1301から、データＦＳ1303に該当する最後のfビットを抽出すればよい。
【０２３７】
ＤＢサーバ300の全体処理部311は、データＦＤ1312とデータＦS1303を、基本演算部317に入力する処理を行う(S1310)。
【０２３８】
ＤＢサーバ300の基本演算部317は、入力されたデータＦＤ1312とデータＦＳ1303とのビット毎の排他的論理和であるＸＯＲ算を計算し、その計算結果をデータＤＤ1313として出力する処理を行う(S1311)。
【０２３９】
データＣｓ705とデータＣＲ1105のデータ値が同じ、即ち、式（7）が成り立つ場合、S1311の処理は、式(8)に基づく。
ＤR = ＦＤ xor ＦS= ＦR       （8）
従って、データＣｓ705とデータＣＲ1105のデータ値が等しい場合、データＤR1313のデータ値はデータＦR708と等しい。
【０２４０】
ＤＢサーバ300の全体処理部311は、データＤＲ1313を、圧縮関数部315へ入力する処理を行う(S1312)。
【０２４１】
ＤＢサーバ300の圧縮関数部315は、入力されたデータを変換し、ハッシュ値を出力する処理を行う。このとき、ハッシュ値は、登録クライアント100の一時情報記憶部180には、ｇビットのデータＧＤ1314として記憶される(S1313)。
【０２４２】
ＤＢサーバ300の全体処理部311は、データＧＤ1314とデータＧR1307を基本演算部317に入力する処理を行う(S1314)。
【０２４３】
ＤＢサーバ300の基本演算部317は、入力されたデータＧＤ1314と、データＧR1307とのビット毎の排他的論理和であるＸＯＲ算を計算し、その計算結果をデータＥＤ1315として出力する(S1315)。
【０２４４】
式(5)が成り立つ場合、データＧＤ1314のデータ値はデータＧR1307と等しく、式(9)より、データＥＤ1315のデータ値は0になる。
ＧＤ xor ＧS= 0      （9）
ＤＢサーバ300の全体処理部311は、任意の数だけ、データＥＤ1315のビット値が0であるかを判定する(S1316)。
【０２４５】
S1316で調査したデータＥＤ1315のデータ値が0でない場合、ＤＢサーバ300の全体処理部311は、秘匿検索クエリ1300と秘匿登録データ1304の関係がないと判断する。このとき、検索対象である秘匿登録データ1304の全て、または検索対象である秘匿登録データ1304から任意に抽出した秘匿登録データ1304の全て、または検索した秘匿登録データ1304が一定数に達するまで、ＤＢサーバ300の制御部310は、S1304に戻り、秘匿登録データ1304を検索する処理を続ける(S1317)。
【０２４６】
S1316で調査したデータＥＤ1315のデータ値が0である場合、ＤＢサーバ300の全体処理部311は、秘匿検索クエリ1300と秘匿登録データ1304の関係があると判断する。このとき、判断された秘匿登録データ1304と、関連する属性901に対応する秘匿登録データ1304とを、秘匿検索クエリ1300に該当する検索結果とみなす(S1318)。
【０２４７】
例えば、図９Ｂに示すように、検索結果は、検索した属性901が氏名に関する情報であり、秘匿検索クエリ1300に関係がある秘匿登録データ1304がdk+1であるとＤＢサーバ300の全体処理部311が判断した場合、判断された秘匿登録データ1304であるdk+1と、属性901が対応する図９Ｂの太枠の点線で囲まれた秘匿登録データ1304（dk、dk+2、dk+3、・・・）を、秘匿検索クエリ1300に該当する検索結果とみなす。
【０２４８】
以上に示したように、登録クライアント100が、毎回、異なるデータ値を有する秘匿登録データ712を作成し、検索クライアント200が、毎回、異なるデータ値を有する秘匿検索クエリ1111を作成した場合にも、受信した秘匿検索クエリ1300に該当する秘匿登録データ1304を正しく検索できる。
【０２４９】
また、式（6）に示したように、検索過程において、データＣｓ705とデータＣＲ1105のデータ値を互いに相殺しており、ＤＢサーバ300には、データＣｓ705とデータＣＲ1105のデータ値が漏洩しない。
【０２５０】
なお、上記の処理手順は固定されたものではなく、処理手順を変更してもよい。例えば、S1303とS1305、S1304とS1306の処理手順をそれぞれ変更し、S1304でデータＤR1306を取り出し、S1306でデータＤS1302を取り出してもよい。同様に、他の処理手順を変更してもよい。
【０２５１】
また、上記の各処理を担当する制御部310は固定されたものではなく、担当する制御部310を変更してもよい。例えば、ＤＢサーバ300が暗号化部312を備える場合、S1312でデータＤＲ1313を、圧縮関数部315ではなく、暗号化部312に入力してもよく、S1314では、暗号化部312から出力されたデータを、データＧD1314として一時情報記憶部380に記憶してもよい。
【０２５２】
また、検索処理に該当する判定基準を変更してもよい。例えば、S1316において、データＥＤ1315の任意のビットが0と等しいのを判定するのではなく、変更可能な特定の値と、データＥＤ1315のデータ値との大小関係等の判定式を用いて判定するようにしてもよい。
【０２５３】
また、秘匿検索クエリ1301に該当する、秘匿登録データ1304のデータ構成を変更し、検索結果を構成してもよい。例えば、データＧＲ1307に関する情報は、検索結果に含まないように構成しても構わない。
【０２５４】
また、ＤＢサーバ300が擬似乱数生成部314を備えるならば、全体処理部311が擬似乱数生成部314に秘密鍵351を入力し、擬似乱数生成部314が出力した擬似乱数を、データＧＲ1307の代わりに連結したデータを、秘匿検索クエリ1301に該当する秘匿登録データ1304として、検索結果に含めてもよい。また、データＧＲ1307と擬似乱数を、共に秘匿検索クエリ1301に該当する秘匿登録データ1304として、検索結果に含めてもよく、擬似乱数の代わりに、一般的なインデックスを用いてもよい。
【０２５５】
また、ＤＢサーバ300が暗号化部313を備えるならば、全体処理部311が、秘匿検索クエリ1301に該当する秘匿登録データ1304と、秘密鍵351を暗号化部313に入力し、出力したデータを、検索結果とみなしてもよい。秘匿検索クエリ1301に該当する秘匿登録データ1304が擬似乱数または一般的なインデックスと連結されている場合、暗号化部313への入力値が随時異なるため、暗号化部313が出力するデータは、乱数とみなせる。従って、ＤＢサーバ300が、例え不正傍受可能なネットワーク400経由で、検索クライアント200に送信しても、検索結果は安全である。
【０２５６】
本実施形態において、S1209で示した、検索クライアント200の制御部210が、受信した秘匿登録データ1304の全てまたは一部に対する秘匿登録データ1304を復号し、平文登録データ272を抽出する処理手順は、以下、Ｓ1401からＳ1411の処理手順に従う。
【０２５７】
図１４Ａは、本実施形態において、検索クライアント200が、通信部203から受信した秘匿登録データ1401のデータ構成を示すブロック図の例である。
【０２５８】
また、図１４Ｂは、本実施形態において、ＤＢサーバ300が、秘匿登録データ1401を復号化する過程において作成するデータＣＲ1405のデータ構成を示すブロック図の例である。
【０２５９】
また、図１４Ｃは、本実施形態において、ＤＢサーバ300が、秘匿登録データ1401を復号化する過程において作成する連結データ1409のデータ構成を示すブロック図の例である。
【０２６０】
以下では、図１４Ａと、図１４Ｂと、図１４Ｃと、図１４Dとを用い、検索クライアント200が、秘匿登録データ1401から平文登録データ1410を復号化する処理手順を説明する。
【０２６１】
検索クライアント200の全体処理部211は、通信部203を用い、秘匿登録データ1401を受信する処理を行う。このとき、検索クライアント200は、登録データ1401を、検索クエリ記憶部230に、(r+h+g)ビットのバイナリ表現で構成されたデータとして記憶する。
【０２６２】
検索クライアント200の全体処理部211は、秘匿登録データ1401からデータＰＲ1402を取り出す処理を行う(S1401)。
【０２６３】
S1401は、例えば、図１４に示すように、検索クライアント200が、全体処理部211が入力した秘匿登録データ1401から、データＰＲ1402に該当する最初のｒビットを抽出すればよい。
【０２６４】
検索クライアント200の全体処理部211は、秘密鍵記憶部250から秘密鍵251を読み出し、秘密鍵251とデータＰＲ1402を圧縮関数部215に入力する処理を行う(S1402)。
【０２６５】
検索クライアント200の圧縮関数部215は、入力されたデータを変換し、ハッシュ値を出力する処理を行う(S1403)。このとき、ハッシュ値は、検索クライアント200の一時情報記憶部280には、ｈビットのデータＨＳ1407として記憶される。
【０２６６】
図１４Ｂは、本実施形態において、ＤＢサーバ300が作成するデータＣＲ1405のデータ構成を示すブロック図である。
【０２６７】
検索クライアント200の全体処理部211は、データＤＲ1403とデータＨＳ1407とを基本演算部217へ入力する処理を行う(S1404)。
【０２６８】
検索クライアント200の基本演算部217は、入力されたデータＤＲ1403とデータＨＳ1407とのビット毎の排他的論理和であるＸＯＲ算を計算し、その計算結果をデータＣＲ1405として出力する処理を行う(S1405)。
【０２６９】
S1407のxor算では、データＨＲ1407とデータＤＲ1403とデータＣＲ1405とは式（10）を満たす。
ＣR ＝ＨＲ xor ＤR      （10）
なお、式(10)は、式(4)を変形した数式である。
【０２７０】
検索クライアント200の全体処理部211は、基本演算部217が出力したデータと、秘密鍵記憶部250に記憶された秘密鍵251とを復号化部213へ入力する処理を行う(S1406)。
【０２７１】
検索クライアント200の復号化部は、入力されたデータＣＲ1405を復号化し、連結データ1409を出力する処理を行う(S1407)。このとき、図１４Ｃに示すように、連結データ1409は、検索クライアント200の一時情報記憶部280に、（ｍ＋ｅ）ビットのデータとして記憶される。
【０２７２】
検索クライアント200の全体処理部211は、連結データ1409から誤り検査データ1411を取り出す処理を行う(S1408)。
【０２７３】
例えば、図１４Ｃに示すように、検索クライアント200が、全体処理部211が入力した連結データ1403から、データ終わりのｅビットを誤り検査データ1411とみなし抽出すればよい。
【０２７４】
検索クライアント200の全体処理部211は、パラメータ記憶部260に記憶された検査パラメータ262を読み込み、検査用のデータに変換したデータと、誤り検査データ1411とを基本演算部217へ入力する処理を行う(S1409)。
【０２７５】
検索クライアント200の基本演算部217は、入力された、検査用に変換されたデータと、誤り検査データ1411を比較し、その比較結果を出力する処理を行う(S1410)。
【０２７６】
例えば、バイナリ列で表わされた検査用のデータと誤り検査データが等しければ、等号を表わすビット（１）を出力し、等しくない場合は、不等号を表わすビット（０）を出力する処理を行う。
【０２７７】
例えば、基本演算部217が、等号を表わすビット（１）を出力した場合は、検索クライアント200の全体処理部211は、正しい検索結果であると判断する処理を行う。また、基本演算部217が、不等号を表わすビット（０）を出力した場合は、ＤＢサーバ300の全体処理部311は、誤った検索結果であると判断する処理を行う。
【０２７８】
検索クライアント200の全体処理部211は、基本演算部217が出力した結果に応じ、連結データ1402から抽出した平文登録データ1410を検索結果とする処理を行い、平文登録データ1410を復元する処理（S1209）を終了する(S1411）。例えば、図１４Ｃに示すように、検索クライアント200が、全体処理部211が入力した連結データ1409から、データ初めのｍビットを平文登録データ1410とみなす。
【０２７９】
なお、ＤＢサーバ300の不正対策に万全を期したい場合、検索に該当した検索結果はＤＢサーバ300から削除し、復号化した平文登録データ1410の順番をランダムにシャッフルした後、検索クライアント200または登録クライアント100から、ＤＢサーバ300に秘匿登録データを再登録するように処理してもよい。
【符号の説明】
【０２８０】
１００：登録クライアント、２００：検索クライアント、３００：ＤＢサーバ、４００：ネットワーク、５００：コンピュータ、１０１、２０１、３０１：入力部、１０２、２０２、３０２：出力部、１０３、２０３、３０３：通信部、１１０、２１０、３１０：制御部、１１１、２１１、３１１：全体処理部、１１２、２１２：暗号化部、２１３、３１３：復号化部、１１４、２１４：擬似乱数生成部、１１５、２１５、３１５：圧縮関数部、１１６、２１６、３１６：準同型関数部、１１７、２１７、３１７：基本演算部、１２０、２２０、３２０：記憶部、１３０：登録データ記憶部、１３１、２７２、７０１、１４１０：平文登録データ、１３２、２７１、７１２、１３０４、１４０１：秘匿登録データ、１３３、２３３：属性、２３０、３３０：検索クエリ記憶部、２３１、１１０１：平文検索クエリ、２３２、３３２、１１１１、１３００：秘匿検索クエリ、３４０：データベース記憶部、３４１：データベース、１５０、２５０、３５０：秘密鍵記憶部、１５１、２５１、３５１：秘密鍵、１６０、２６０、３６０：パラメータ記憶部、１６１、２６１、３６１：関数パラメータ、１６２、２６２：検査パラメータ、２７０：受信データ記憶部、１８０、２８０、３８０：一時情報記憶部、５０１：ＣＰＵ(Central Processing Unit)、５０２：メモリ、５０３：外部記憶装置、５０８：記憶媒体、５０７：読書装置、５０６：入力装置、５０５：出力装置、５０４：通信装置、５０９：内部通信線、６００：出力部１０１の表示内容、６１０：管理方法の選択部、６２０：管理フォーム部、６２１、１０１１：属性、６２２、１０２２：入力フォーム、６５０：実行ボタン、６６０、１０６０：クリアボタン、１０００：出力部１０２の表示内容、１０１０：検索項目部、１０２０：検索フォーム部、１０５０：検索ボタン、７０２、１４１１：誤り検査データ、７０３、７０４、１１０３、１１０４、１１０８、１３０１、１３０８、１３１１、１４０９：連結データ、７０５：データＣＲ、７０６：データＰＲ、７０７：データＨＲ、７０８：データＦＲ、７０９：データＧＲ、７１１：データＤＲ、１１０２：誤り検査データ、１１０５：データＣＳ、１１０６：データＰＳ、１１０７：データＦＳ、１１１０：データＤＳ、１３０２：データＤＳ、１３０３：データＦＳ、１３０５：データＰＲ、１３０６：データＤＲ、１３０７：データＧＲ、１３０９：データＤＲ、１３１０：データＤＳ、１３１２：データＦＤ、１３１３：データＤＤ、１３１４：データＧＤ、１３１５：データＥＤ、１４０２：データＰＲ、１４０３：データＤＲ、１４０４：データＧＲ、１４０５：データＣＲ、１４０７：データＨＳ。
【図１】
0005412414.tif 000002
【図２】
0005412414.tif 000003
【図３】
0005412414.tif 000004
【図４】
0005412414.tif 000005
【図５】
0005412414.tif 000006
【図６】
0005412414.tif 000007
【図７Ａ】
0005412414.tif 000008
【図７Ｂ】
0005412414.tif 000009
【図７Ｃ】
0005412414.tif 000010
【図８】
0005412414.tif 000011
【図９Ａ】
0005412414.tif 000012
【図９Ｂ】
0005412414.tif 000013
【図１０】
0005412414.tif 000014
【図１１Ａ】
0005412414.tif 000015
【図１１Ｂ】
0005412414.tif 000016
【図１１Ｃ】
0005412414.tif 000017
【図１２】
0005412414.tif 000018
【図１３Ａ】
0005412414.tif 000019
【図１３Ｂ】
0005412414.tif 000020
【図１３Ｃ】
0005412414.tif 000021
【図１３Ｄ】
0005412414.tif 000022
【図１４Ａ】
0005412414.tif 000023
【図１４Ｂ】
0005412414.tif 000024
【図１４Ｃ】
0005412414.tif 000025