(57)【要約】【課題】  検索可能暗号方式では、暗号文の安全性や、暗号文のサイズの最適化とネットワーク通信量の最適化などが十分に検討されていない。【解決手段】  登録クライアントは、ハッシュ値と準同型関数の出力値によるマスクを用いた確率的暗号化方式により、検索用に作成する検索タグのサイズを圧縮した暗号化データをサーバに預託し、検索クライアントは、検索用のキーワードを同様に確率的暗号化し、暗号化データの一部のみを暗号化した検索キーワードとして管理サーバに送信し、管理サーバに暗号化データと暗号化キーワードの乱数のマスクを解除させずに、管理サーバに検索に該当するデータを検索し、検索結果の誤検索を検知し、検索結果を復号する。【選択図】  図１
2015035072.tif 000002
【特許請求の範囲】
【請求項１】
登録クライアントと検索クライアントと管理サーバがネットワークで接続された検索可能暗号処理システムであって、
前記登録クライアントは、登録用の平文データを暗号化した秘匿データを作成する手段を有し、
前記管理サーバは、検索に用いる検索タグを含む秘匿データを格納する手段を有し、
前記登録クライアントは、更に、データ記憶部に格納されたタグ長に従って、秘匿データの検索タグの長さを決定し、秘匿データの検索タグを作成する手段を有する、ことを特徴とする検索可能暗号処理システム。
【請求項２】
前記検索可能暗号処理システムにおいて、
前記検索クライアントが検索用の平文キーワードを暗号化した秘匿キーワードを作成して、前記ネットワーク経由で前記管理サーバに送信し、
前記管理サーバがネットワーク経由で前記秘匿キーワードを受信し、秘匿データと秘匿キーワードの検索を行うこと、
を特徴とする請求項１記載の検索可能暗号処理システム。
【請求項３】
前記検索可能暗号処理システムにおいて、
前記検索クライアントが検索用の平文キーワードを暗号化した暗号化キーワードを作成し、前記暗号化キーワードの一部を乱数でマスクしたデータを秘匿キーワードに含めること、
を特徴とする請求項２記載の検索可能暗号処理システム。
【請求項４】
前記検索可能暗号処理システムにおいて、
前記管理サーバが秘匿データと秘匿キーワードの検索を行い、検索結果の一部に秘匿データを含め、ネットワーク経由で、前記検索クライアントに送信し、
前記検索クライアントがネットワーク経由で送信された前記検索結果を受信すること、
を特徴とする請求項２記載の検索可能暗号処理システム。
【請求項５】
前記検索可能暗号処理システムにおいて、
前記登録クライアントが初期ベクトルを用いて乱数を生成し、
秘匿データが前記初期ベクトル含むこと、
を特徴とする請求項４記載の検索可能暗号処理システム。
【請求項６】
前記検索可能暗号処理システムにおいて、
前記登録クライアントが平文データを暗号化した中間暗号化データを作成し、
前記乱数を用いて中間暗号化データをマスクした暗号文本体を作成し、
前記秘匿データが前記暗号文本体を含むこと、
を特徴とする請求項５記載の検索可能暗号処理システム。
【請求項７】
前記検索可能暗号処理システムにおいて、
前記検索クライアントが前記秘匿データに埋め込まれた前記初期ベクトルを用いて、前記登録クライアントが生成した前記乱数と同一の乱数を生成すること、
を特徴とする請求項６記載の検索可能暗号処理システム。
【請求項８】
前記検索可能暗号処理システムにおいて、
前記検索クライアントが前記秘匿データに埋め込まれた前記初期ベクトルを用いて、前記登録クライアントが生成した前記乱数を生成し、
前記暗号文本体をマスクした前記乱数のマスクを解除すること、
を特徴とする請求項７記載の検索可能暗号処理システム。
【請求項９】
前記検索可能暗号処理システムにおいて、
前記検索クライアントが前記乱数のマスクを解除した前記暗号文本体と、前記暗号化キーワードを比較すること、
を特徴とする請求項７記載の検索可能暗号処理システム。
【請求項１０】
前記登録クライアントが、データ記憶部に格納されたタグ長と異なる長さをもつ、秘匿データの検索タグを作成すること、
を特徴とする請求項１記載の検索可能暗号処理システム。
【請求項１１】
登録クライアントと検索クライアントと管理サーバがネットワークで接続されたシステムにおける検索可能暗号処理方法であって、
前記登録クライアントは、登録用の平文データを暗号化した秘匿データを作成し、
前記管理サーバは、検索に用いる検索タグを含む秘匿データを格納し、
前記登録クライアントは、更に、データ記憶部に格納されたタグ長に従って、秘匿データの検索タグの長さを決定し、秘匿データの検索タグを作成する、ことを特徴とする検索可能暗号処理方法。
【請求項１２】
前記検索可能暗号処理方法において、
前記登録クライアントが平文データを暗号化した中間暗号化データを作成し、
前記乱数を用いて中間暗号化データをマスクした暗号文本体を作成し、
前記秘匿データが前記暗号文本体を含むこと、
を特徴とする請求項１１記載の検索可能暗号処理方法。
【請求項１３】
前記検索可能暗号処理方法において、
前記検索クライアントが前記秘匿データに埋め込まれた前記初期ベクトルを用いて、前記登録クライアントが生成した前記乱数と同一の乱数を生成すること、
を特徴とする請求項１２記載の検索可能暗号処理方法。
【請求項１４】
前記検索可能暗号処理方法において、
前記検索クライアントが前記乱数のマスクを解除した前記暗号文本体と、前記暗号化キーワードを比較すること、
を特徴とする請求項１３記載の検索可能暗号処理方法。
【請求項１５】
ネットワークを介して検索クライアントと管理サーバに接続された登録クライアントが検索可能暗号処理方法を実行するためのプログラムを格納した、計算機で読み取り可能な記憶媒体であって、前記方法は、
登録用の平文データを暗号化した秘匿データを作成し、
前記管理サーバに、検索に用いる検索タグを含む秘匿データを格納し、
更に、データ記憶部に格納されたタグ長に従って、秘匿データの検索タグの長さを決定し、秘匿データの検索タグを作成する、ことを特徴とする記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サーバ／クライアントモデルにおいて、サーバが、クライアントの要求に従って、暗号化データを復号せずに、預託された暗号化データを検索する、検索処理システム及び方法に関する。
【背景技術】
【０００２】
情報システムの開発・運用管理費の効率化を目的に、近年、情報システムを自組織が維持するのではなく、他組織が提供する情報システムを利用する、クラウドと呼ばれる運用管理形態が脚光を浴びている。一方、クラウドにおいては、情報システムを管理する組織が、情報システムを利用する組織とは異なるため、情報漏えい等を防止する策や、事故発生後の原因究明、再発防止策等が自組織だけでは立てにくい。そのため、事前に、データの不正流出の予防策として、暗号技術を活用し、データの機密性を確保する必要がある。
【０００３】
サーバ／クライアントモデルにおいて、クライアントが、サーバにデータを預託しながら、サーバに対し、預託したデータの情報漏洩を防ぐ技術として、暗号技術を利用した方式が知られている。例えば、非特許文献１や特許文献１には、クライアントの要求に従って、暗号化データを復号せずに、預託された暗号化データを検索する、検索処理方式が記載されている。この検索処理方式は、平文と暗号文が一対一の単純な対応関係を有する決定的暗号化方式よりも安全な、平文と暗号文が一対ｍの複雑な対応関係を有する確率的暗号化方式を採用しており、サーバ管理者への情報漏洩を防ぎながら、かつサーバに預託したデータを安全に検索するための技術が開示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】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).
【特許文献】
【０００５】
【特許文献１】特開２０１２−１２３６１４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１に記載された技術では、クライアントからの検索キーワードの暗号化には、安全性の低い決定的暗号化方式を用いているため、頻度分析等の不正攻撃に対して脆弱である。一方、特許文献１に記載された技術では、預託する平文データと検索キーワードの双方を確率的に暗号化しており、安全性が高い。ただし、暗号文のデータサイズの縮小に関して、十分な検討がされていない。例えば、標準的な暗号化方式であるＡＥＳ暗号（Advanced Encryption Standard，出力長１２８ビット）と標準的な暗号化ハッシュ関数であるＳＨＡ２５６（Secure HashAlgorithm 256bit,出力長２５６ビット）を用いて、１２８ビットの平文を暗号化した場合、サーバに預託する暗号化データのサイズはＡＥＳ暗号とＳＨＡ２５６ハッシュ関数のそれぞれの出力長を合計した３８４ビット（１２８ビット＋２５６ビット）以上になる。即ち、暗号化前（１２８ビット）に比べ、３倍にデータサイズが膨れ上がってしまう。検索キーワードの暗号化に関しても、同様にデータサイズの縮小に十分な検討がされていない。具体的には、検索キーワードを暗号化すると、同程度の長さの暗号文が作成される。この暗号文はネットワーク経由で送受信される。従って、検索キーワードのサイズが大きい場合、クライアントとサーバ間のネットワークに負荷がかかってしまう。
【課題を解決するための手段】
【０００７】
前記課題を解決するために、検索可能暗号処理システムは、データを預かる管理サーバと、管理サーバにデータを預託する登録クライアントと、管理サーバにデータを検索させる検索クライアントがネットワーク経由で連携し、登録クライアントは、ハッシュ値と準同型関数の出力値によるマスクを用いた確率的暗号化方式を用いつつ、検索用に作成する検索タグのサイズを圧縮した暗号化データをサーバに預託し、検索クライアントは、検索用のキーワードの暗号化に、同様に確率的暗号化を用いつつ、効率的に圧縮して暗号化した検索キーワードを管理サーバに送信し、管理サーバに暗号化データと暗号化キーワードの乱数のマスクを解除させずに、管理サーバに検索に該当するデータを検索結果として出力させ、検索クライアントは、検索結果の誤検索を検知し、検索結果を復号する。
【発明の効果】
【０００８】
クライアントが管理サーバに預託する暗号化データのサイズが小さいため、管理サーバのストレージを効率的に利用できる。検索用に暗号化した検索キーワードのサイズも小さくできるため、ネットワークにおける通信量を抑えることができる。さらに、クライアントは管理サーバが誤検索をした場合も、検索結果から誤りを検知できる。
【図面の簡単な説明】
【０００９】
【図１】検索可能暗号処理システムの概略を例示する図である。
【図２】登録クライアントの機能の概略を例示する図である。
【図３】検索クライアントの機能の概略を例示する図である。
【図４】管理サーバの機能の概略を例示する図である。
【図５】コンピュータの概略構成を例示する図である。
【図６】乱数の生成方法及び暗号化方法を例示する図である。
【図７】登録クライアントにおける秘匿データの作成手順を例示するブロック図である。
【図８】検索クライアントにおける秘匿キーワードの作成手順を例示するブロック図である。
【図９】管理サーバにおける秘匿データの検索手順を例示するブロック図である。
【図１０】検索クライアントにおける秘匿データの誤検索の検知手順を例示するブロック図である。
【図１１】検索クライアントにおける秘匿データの復号手順を例示するブロック図である。
【図１２】管理サーバと登録クライアントにおける秘匿データの登録手順を例示するフローチャートを示す図である。
【図１３】管理サーバと検索クライアントにおける秘匿データの検索手順を例示するフローチャートを示す図である。
【図１４】暗号文のフォーマットを示す図である。
【図１５】検索誤りの検知処理を示す図である。
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。  
図１は、本実施形態の検索処理システムの概略図である。図示するように、検索処理システムは、登録クライアント１００（Registration Client）と、検索クライアント２００（Search Client）と、管理サーバ３００（Management Server）とを備え、登録クライアント１００と管理サーバ３００、検索クライアント２００と管理サーバ３００は、ネットワーク４００を介して相互に情報を送受信できるように構成されている。
【００１１】
ここで、本実施形態における登録クライアント１００は、秘匿化したデータを管理サーバ３００に送信するデータ登録用の送受信装置として機能し、検索クライアント２００は、秘匿化したキーワードを管理サーバ３００に送信し、検索結果を受信する、検索用の送受信装置として機能し、管理サーバ３００は、秘匿化したデータをデータベース３４１に保管し、またデータベース３４１内のデータを検索する送受信装置として機能する。
【００１２】
図２は、登録クライアント１００の機能概略図である。図示するように、登録クライアント１００は、制御部１１０と、記憶部１２０と、入力部１０１と、出力部１０２と、通信部１０３とを備える。  
記憶部１２０は、データ記憶部１３０と、鍵記憶部１５０と、一時記憶部１８０とを備える。
【００１３】
データ記憶部１３０には、管理サーバ３００に送信するデータである平文が記憶される。ここで、本実施形態においては、入力部１０１を介して、受け付けた平文データ１３１と、管理サーバ３００に登録する秘匿データ１３２とが記憶される。また、秘匿データ１３２の一部分のデータ長を意味する、タグ長１３５を記憶する。また、秘匿データ１３２の作成時に用いる初期ベクトル１３６を記憶する。鍵記憶部１５０には、安全性の観点から登録クライアント１００が秘密に管理すべき、乱数用秘密鍵１５１とデータ暗号化鍵１５２が記憶される。一時記憶部１８０には、制御部１１０での処理で必要となる情報が記憶される。
【００１４】
制御部１１０は、全体処理部１１１と、暗号化部１１２と、擬似乱数生成部１１４と、不可逆変換部１１５と、準同型関数部１１６と、基本演算部１１７とを備える。
【００１５】
全体処理部１１１は、登録クライアント１００における全ての処理を制御する。例えば、本実施形態において、全体処理部１１１は、入力部１０１を介して入力を受け付けた情報を、データ記憶部１３０に平文データ１３１として記憶する処理を行う。また、本実施形態において、全体処理部１１１は、平文データ１３１を出力部１０２に表示する処理を行う。
【００１６】
また、本実施形態において、全体処理部１１１は、データ記憶部１３０に記憶した平文データ１３１を読み込み、それぞれ、暗号化部１１２と、擬似乱数生成部１１４と、不可逆変換部１１５と、準同型関数部１１６と、基本演算部１１７とに入力し、出力されたデータを、データ記憶部１３０に秘匿データ１３２として記憶する処理を行う。
【００１７】
また、本実施形態において、全体処理部１１１は、秘匿データ１３２を、通信部１０３を介して管理サーバ３００に送信する処理を行う。さらに、本実施形態において、全体処理部１１１は、管理サーバ３００より通信部１０３を介して受信した秘匿データ１３２を、一時記憶部１８０に記憶する処理と出力部１０２に表示する処理を行う。
【００１８】
暗号化部１１２は、入力されたデータを暗号化したデータを出力する処理を行う。例えば、本実施形態においては、全体処理部１１１からデータとデータ暗号化鍵１５２が入力され、暗号化したデータを出力する処理を行う。例えば、標準的な暗号化アルゴリズムの実装により、暗号化部１１２は実現される。
【００１９】
擬似乱数生成部１１４は、擬似乱数を出力する処理を行う。例えば、擬似乱数生成部１１４は、温度、時間、電力量、等の物理現象から、乱数を出力する。本実施形態においては、擬似乱数生成部１１４は、全体処理部１１１から入力された乱数用秘密鍵１５１を用い、擬似乱数を出力する。また、乱数用秘密鍵１５１のデータ値は新しいデータ値に更新され、再び、全体処理部１１１により鍵記憶部１５０に記憶される。例えば、標準的な擬似乱数生成アルゴリズムの実装により、擬似乱数生成部１１４は実現される。
【００２０】
不可逆変換部１１５は、入力されたデータを圧縮したデータを出力する処理を行う。例えば、本実施形態においては、全体処理部１１１から入力されたデータを固定長（ｈビット）の別のデータに変換し、出力する処理を行う。例えば、標準的な暗号ハッシュ関数アルゴリズムであるＳＨＡ−２５６関数の実装により、任意長の入力データを２５６ビットのデータへ変換する不可逆変換部１１５が実現できる。
【００２１】
準同型関数部１１６は、入力データに対し、準同型性を有する関数の出力結果をデータとして出力する処理を行う。ただし、準同型を有する関数（以降、準同型関数と呼ぶ）とは、関数Ｆと、入力変数ｘ、入力変数ｙに対し、以下の数１が成り立つ関数を指す。
（数１）              Ｆ（ｘ・ｙ）＝Ｆ（ｘ）？Ｆ（ｙ）
【００２２】
ただし、「・」と「？」は、演算記号を表わし、加算用の演算記号＋、乗算用の演算記号＊、ビット毎の排他的論理和であるＸＯＲ（ｅＸｃｌｕｓｉｖｅ  ＯＲ）演算用の演算記号ｘｏｒ等が入る。このとき、数１において、「・」と「？」にＸＯＲ演算記号ｘｏｒが入る場合、以下の数２が成り立つ。
（数２）              Ｆ（ｘ  ｘｏｒ  ｙ）＝Ｆ（ｘ）ｘｏｒ  Ｆ（ｙ）
【００２３】
基本演算部１１７は、加算、減算、比較算や、ＡＮＤ、ＯＲ、ＸＯＲ等の基本的な算術演算に関する処理を行う。例えば、本実施形態においては、基本演算部１１７は、全体処理部１１１から入力された２つのデータのビット毎の排他的論理和であるＸＯＲ演算や、比較演算の等号成立または不成立の検証結果を、データとして出力する処理を行う。
【００２４】
以上に示した登録クライアント１００は、例えば、図５（コンピュータの概略図）に示すような、ＣＰＵ（Central Processing Unit）５０１と、メモリ５０２と、ＨＤＤ（Hard Disk Drive）等の外部記憶装置５０３と、ＣＤ（Compact Disk）やＤＶＤ（Digital Versatile Disk）等の可搬性を有する記憶媒体５０８に対して情報を読み書きする読書装置５０７と、キーボードやマウス等の入力装置５０６と、ディスプレイ等の出力装置５０５と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置５０４と、これらを連結するシステムバス等の内部通信線（システムバスという）５０９と、を備えた一般的なコンピュータ５００で実現できる。
【００２５】
例えば、記憶部１２０は、ＣＰＵ５０１がメモリ５０２または外部記憶装置５０３を利用することにより実現可能であり、制御部１１０と制御部１１０に含まれる各処理部は、外部記憶装置５０３に記憶されている所定のプログラムをメモリ５０２にロードしてＣＰＵ５０１で実行することで実現可能であり、入力部１０１は、ＣＰＵ５０１が入力装置５０６を利用することで実現可能であり、出力部１０２は、ＣＰＵ５０１が出力装置５０５を利用することで実現可能であり、通信部１０３は、ＣＰＵ５０１が通信装置５０４を利用することで実現可能である。
【００２６】
この所定のプログラムは、読書装置５０７を介して記憶媒体５０８から、あるいは、通信装置５０４を介してネットワークから、外部記憶装置５０３に記憶（ダウンロード）され、それから、メモリ５０２上にロードされて、ＣＰＵ５０１により実行されるようにしてもよい。また、読書装置５０７を介して、記憶媒体５０８から、あるいは通信装置５０４を介してネットワークから、メモリ５０２上に直接ロードされ、ＣＰＵ５０１により実行されるようにしてもよい。
【００２７】
図３は、検索クライアント２００の機能概略図である。図示するように、検索クライアント２００は、制御部２１０と、記憶部２２０と、入力部２０１と、出力部２０２と、通信部２０３とを備える。  
記憶部２２０は、データ記憶部２３０と、鍵記憶部２５０と、一時記憶部２８０とを備える。
【００２８】
データ記憶部２３０には、管理サーバ３００に送信するデータである、送信文を特定する情報と通信部２０３を介して受信したデータを特定する情報が記憶される。本実施形態においては、検索クライアント２００が、入力部２０１を介して受け付けた平文キーワード２４１を特定する情報と、管理サーバ３００に送信する秘匿キーワード２４２と、平文キーワード２４１が記憶される。また、通信部２０３を介して管理サーバ３００から受信したデータを特定する情報が、秘匿データ２３２として記憶され、秘匿データ２３２から、秘匿化を解除したデータを、平文データ２３１としてデータ記憶部２３０に記憶する。また、秘匿データ２３２の作成時に用いる初期ベクトル２３６を記憶する。
【００２９】
鍵記憶部２５０には、安全性の観点から検索クライアント２００が秘密に管理すべき、乱数用秘密鍵２５１（Ｋ２）、データ暗号化鍵２５２（Ｋ１）、データ復号化鍵２５３（Ｋ１）、関数値暗号化鍵２５４（Ｋ３）を特定する情報が記憶される。なお、データ復号化鍵２５３は、上記のようにデータ暗号化鍵２５２と同じであってもよいし、異なっていてもよい。
【００３０】
一時記憶部２８０には、制御部２１０での処理で必要となる情報が記憶される。
【００３１】
制御部２１０は、全体処理部２１１と、暗号化部２１２と、復号化部２１３と、擬似乱数生成部２１４と、不可逆変換部２１５と、準同型関数部２１６と、基本演算部２１７とを備える。
【００３２】
全体処理部２１１は、検索クライアント２００における全ての処理を制御する。例えば、本実施形態において、全体処理部２１１は、入力部２０１を介して入力を受け付けた情報を、データ記憶部２３０に平文キーワード２４１として記憶する処理を行う。
【００３３】
また、本実施形態において、全体処理部２１１は、平文キーワード２４１を出力部２０２に表示する処理を行う。
【００３４】
また、本実施形態において、全体処理部２１１は、データ記憶部２３０に記憶した平文キーワード２４１を読み込み、それぞれ、暗号化部２１２と、擬似乱数生成部２１４と、不可逆変換部２１５と、準同型関数部２１６と、基本演算部２１７とに入力し、出力されたデータを秘匿キーワード２４２としてデータ記憶部２３０に記憶する処理を行う。
【００３５】
また、本実施形態において、全体処理部２１１は、通信部２０３を介して、秘匿キーワード２４２を管理サーバ３００に送信する処理を行う。また、本実施形態において、全体処理部２１１は、通信部２０３を介して、秘匿データ２３２を管理サーバ３００から受信する処理を行う。
【００３６】
また、本実施形態において、全体処理部２１１は、通信部２０３を介して、受信した秘匿データ２３２をデータ記憶部２３０に秘匿データ２３２として記憶する処理を行う。また、本実施形態において、全体処理部２１１は、データ記憶部２３０に記憶した秘匿データ２３２を読み込み、それぞれ、復号化部２１３と、不可逆変換部２１５と、準同型関数部２１６と、基本演算部２１７とに入力し、出力されたデータを平文データ２３１としてデータ記憶部２３０に記憶する処理を行う。
【００３７】
また、本実施形態において、全体処理部２１１は、平文データ２３１を出力部２０２に表示する処理を行う。さらに、全体処理部２１１は、管理サーバ３００より、通信部２０３を介して受信したデータを、一時記憶部２８０に記憶する処理と、出力部２０２に表示する処理を行う。
【００３８】
暗号化部２１２は、入力されたデータを暗号化したデータを出力する処理を行う。例えば、本実施形態においては、全体処理部２１１からデータとデータ暗号化鍵２５２が入力され、暗号化したデータを出力する処理を行う。
【００３９】
復号化部２１３は、入力されたデータを復号化したデータを出力する処理を行う。例えば、本実施形態においては、全体処理部２１１から暗号化したデータとデータ復号化鍵２５３が入力され、データを復号する処理を行う。
【００４０】
擬似乱数生成部２１４は、擬似乱数を出力する処理を行う。例えば、擬似乱数生成部２１４は、温度、時間、電力量、等の物理現象から、乱数を出力する。本実施形態においては、擬似乱数生成部２１４は、全体処理部２１１から入力された乱数用秘密鍵２５１を用い、擬似乱数を出力する。
【００４１】
また、乱数用秘密鍵２５１のデータ値は新しいデータ値に更新され、再び、全体処理部２１１により鍵記憶部２５０に記憶される。例えば、本実施形態においては、全体処理部２１１から入力された乱数用秘密鍵２５１を用い、擬似乱数を出力する処理を行う。
【００４２】
不可逆変換部２１５は、入力されたデータを不可逆変換したデータを出力する処理を行う。例えば、本実施形態においては、全体処理部２１１から入力されたデータを固定長（ｈビット）の別のデータに変換し、出力する処理を行う。例えば、標準的な暗号ハッシュ関数アルゴリズムであるＳＨＡ−２５６の実装により、任意長の入力データを２５６ビットのデータへ変換する不可逆変換部２１５が実現できる。
【００４３】
準同型関数部２１６は、入力されたデータに対し、準同型性関数の出力結果をデータとして出力する処理を行う。ただし、準同型関数とは、関数Ｆと、入力変数ｘ、入力変数ｙに対し、数２が成り立つ場合を示す。なお、ビット毎の排他的論理和であるＸＯＲ演算以外の演算記号で準同型性が成り立つ時も、本実施形態は同様に実施できる。
【００４４】
基本演算部２１７は、加算、減算、比較算や、ＡＮＤ、ＯＲ、ＸＯＲ等の基本的な算術演算に関する処理を行う。
【００４５】
以上に示した検索クライアント２００は、例えば、図５（コンピュータの概略図）に示すような、ＣＰＵ５０１と、メモリ５０２と、ＨＤＤ等の外部記憶装置５０３と、ＣＤやＤＶＤ等の可搬性を有する記憶媒体５０８に対して情報を読み書きする読書装置５０７と、キーボードやマウス等の入力装置５０６と、ディスプレイ等の出力装置５０５と、通信ネットワークに接続するためのＮＩＣ等の通信装置５０４と、これらを連結するシステムバス等の内部通信線（システムバスという）と、を備えた一般的なコンピュータで実現できる。
【００４６】
例えば、記憶部２２０は、ＣＰＵ５０１がメモリ５０２または外部記憶装置５０３を利用することにより実現可能であり、制御部２１０と制御部２１０に含まれる各処理部は、外部記憶装置５０３に記憶されている所定のプログラムをメモリ５０２にロードしてＣＰＵ５０１で実行することで実現可能であり、入力部２０１は、ＣＰＵ５０１が入力装置５０６を利用することで実現可能であり、出力部２０２は、ＣＰＵ５０１が出力装置５０５を利用することで実現可能であり、通信部２０３は、ＣＰＵ５０１が通信装置５０４を利用することで実現可能である。
【００４７】
この所定のプログラムは、読書装置５０７を介して記憶媒体５０８から、あるいは、通信装置５０４を介してネットワークから、外部記憶装置５０３に記憶（ダウンロード）され、それから、メモリ５０２上にロードされて、ＣＰＵ５０１により実行されるようにしてもよい。また、読書装置５０７を介して、記憶媒体５０８から、あるいは通信装置５０４を介してネットワークから、メモリ５０２上に直接ロードされ、ＣＰＵ５０１により実行されるようにしてもよい。
【００４８】
図４は、管理サーバ３００の機能概略図である。図示するように、管理サーバ３００は、制御部３１０と、記憶部３２０と、入力部３０１と、出力部３０２と、通信部３０３と、を備える。
【００４９】
記憶部３２０は、データ記憶部３３０と、一時記憶部３８０とを備える。  
データ記憶部３３０には、通信部３０３を介して受信したデータを特定する情報が記憶される。ここで、本実施形態においては、通信部３０３を介して登録クライアント１００から受信した情報を、データ記憶部３３０にデータベース３４１の構成情報として記憶する処理を行う。また、データ記憶部３３０には、通信部３０３を介して受信したキーワードを特定する情報が記憶される。ここで、本実施形態においては、通信部３０３を介して検索クライアント２００から受信した情報を、データ記憶部３３０に秘匿キーワード３４２として記憶する処理を行う。また、秘匿データの一部分のデータ長を意味する、タグ長３３５を記憶する。
【００５０】
一時記憶部３８０には、制御部３１０での処理で必要となる情報が記憶される。
【００５１】
制御部３１０は、全体処理部３１１と、復号化部３１３と、不可逆変換部３１５と、準同型関数部３１６と、基本演算部３１７と、を備える。
【００５２】
全体処理部３１１は、管理サーバ３００における全ての処理を制御する。例えば、本実施形態において、全体処理部３１１は、通信部３０３を介して秘匿データ１３２を、登録クライアント１００から受信する処理を行う。
【００５３】
また、本実施形態において、全体処理部３１１は、通信部３０３を介して受信した秘匿データ１３２を、データ記憶部３３０、データベース３４１の構成情報として記憶する処理を行う。また、本実施形態において、全体処理部３１１は、通信部３０３を介して秘匿キーワード３４２を、検索クライアント２００から受信する処理を行う。また、本実施形態において、全体処理部３１１は、通信部３０３を介して受信した秘匿キーワード３４２を、データ記憶部３３０に秘匿キーワード３４２として記憶する処理を行う。
【００５４】
また、本実施形態において、全体処理部３１１は、データ記憶部３３０に記憶した秘匿キーワード３４２を読み込み、それぞれ、不可逆変換部３１５と、準同型関数部３１６と、基本演算部３１７とに入力し、出力されたデータを、通信部３０３を介して、検索クライアント２００に送信する処理を行う。
【００５５】
さらに、全体処理部３１１は、検索クライアント２００または登録クライアント１００より、通信部３０３を介して受信したデータに関する情報を、一時記憶部３８０に記憶する処理と、出力部３０２に表示する処理を行う。
【００５６】
復号化部３１３は、入力されたデータを復号化したデータを出力する処理を行う。例えば、本実施形態においては、全体処理部３１１から暗号化した関数値を有するデータと関数値復号化鍵３５１が入力され、関数値を有するデータを復号する処理を行う。
【００５７】
不可逆変換部３１５は、入力されたデータを不可逆変換したデータを出力する処理を行う。例えば、本実施形態においては、全体処理部３１１から入力されたデータを固定長（ｈビット）の別のデータに変換し、出力する処理を行う。例えば、標準的な暗号ハッシュ関数アルゴリズムであるＳＨＡ−２５６関数の実装により、任意長の入力データを２５６ビットのデータへ変換する不可逆変換部１１５が実現できる。
【００５８】
準同型関数部３１６は、入力されたデータに対し、準同型関数の出力結果をデータとして出力する処理を行う。ただし、準同型関数とは、関数Ｆと、入力変数ｘ、入力変数ｙに対し、数２が成り立つ場合を示す。なお、ビット毎の排他的論理和であるＸＯＲ演算以外の演算記号で準同型性が成り立つ時も、本実施形態は同様に実施できる。
【００５９】
基本演算部２１７は、加算、減算、比較算や、ＡＮＤ、ＯＲ、ＸＯＲ等の基本的な算術演算に関する処理を行う。
【００６０】
以上に示した登録クライアント１００、検索クライアント２００、及び管理サーバ３００は、例えば、図５（コンピュータの概略図）に示すような、ＣＰＵ５０１と、メモリ５０２と、ＨＤＤ等の外部記憶装置５０３と、ＣＤやＤＶＤ等の可搬性を有する記憶媒体５０８に対して情報を読み書きする読書装置５０７と、キーボードやマウス等の入力装置５０６と、ディスプレイ等の出力装置５０５と、通信ネットワークに接続するためのＮＩＣ等の通信装置５０４と、これらを連結するシステムバス等の内部通信線（システムバスという）とを備えた一般的なコンピュータで実現できる。
【００６１】
例えば、記憶部１２０、２２０、３２０は、ＣＰＵ５０１がメモリ５０２または外部記憶装置５０３を利用することにより実現可能であり、制御部１１０、２１０、３１０と制御部１１０、２１０、３１０に含まれる各処理部は、外部記憶装置５０３に記憶されている所定のプログラムをメモリ５０２にロードしてＣＰＵ５０１で実行することで実現可能であり、入力部１０１、２０１、３０１は、ＣＰＵ５０１が入力装置５０６を利用することで実現可能であり、出力部１０２、２０２、３０２は、ＣＰＵ５０１が出力装置５０５を利用することで実現可能であり、通信部１０３、２０３、３０３は、ＣＰＵ５０１が通信装置５０４を利用することで実現可能である。
【００６２】
この所定のプログラムは、読書装置５０７を介して記憶媒体５０８から、あるいは、通信装置５０４を介してネットワークから、外部記憶装置５０３に記憶（ダウンロード）され、それから、メモリ５０２上にロードされて、ＣＰＵ５０１により実行されるようにしてもよい。また、読書装置５０７を介して記憶媒体５０８から、あるいは通信装置５０４を介してネットワークから、メモリ５０２上に直接ロードされ、ＣＰＵ５０１により実行されるようにしてもよい。
【００６３】
＜秘匿データの登録フロー＞
図１２は、本実施形態において、ネットワーク４００を経由し、登録クライアント１００が、秘匿データ１３２を、管理サーバ３００へ登録する処理を示すシーケンス図である。シーケンス１は登録クライアント１００が実行する処理であり、シーケンス２はシーケンス１と同期して管理サーバ３００が実行する処理である。
【００６４】
登録クライアント１００は、入力部１０１を経由し、ユーザから入力された情報を平文データ１３１として、記憶部１２０へ記憶する処理を行う（Ｓ１２０２）。登録クライアント１００は、制御部１１０により、秘匿データ１３２を作成し、記憶部１２０へ記憶する処理を行う（Ｓ１２０３）。登録クライアント１００は、通信部１０３から、ネットワーク４００を経由し、秘匿データ１３２を、管理サーバ３００へ、送信する処理を行う（Ｓ１２０４）。
【００６５】
管理サーバ３００は、通信部３０３から、ネットワーク４００を経由し、登録クライアント１００が送信した秘匿データ１３２を受信する処理を行う（Ｓ１２０５）。管理サーバ３００は、制御部３１０により、受信した秘匿データ１３２を、データベース３４１の構成情報として、記憶部３２０へ記憶する処理を行う（Ｓ１２０６）。管理サーバ３００は、秘匿データ１３２の登録処理の成否を、通信部３０３から、ネットワーク４００を経由し、登録サーバへ送信する処理を行う（Ｓ１２０７）。
【００６６】
登録クライアント１００は、通信部１０３から、ネットワーク４００を経由し、管理サーバ３００が送信した秘匿データ１３２の登録処理の成否を受信する処理を行う（Ｓ１２０８）。登録クライアント１００は、出力部１０２を経由し、ユーザに、登録処理の成否を含む登録情報について、表示する処理を行う（Ｓ１２０９）。
【００６７】
なお、必ずしも上記に記述された手順を全て処理する必要はない。例えば、Ｓ１２０３の処理手順を省いてもよい。
【００６８】
＜秘匿データの検索フロー＞
図１３は、本実施形態において、ネットワーク４００を経由し、検索クライアント２００が送信した秘匿キーワード２４２を用い、管理サーバ３００が、データベース３４１を検索する処理を示すシーケンス図である。シーケンス１は検索クライアント２００が実行する処理であり、シーケンス２はシーケンス１と同期して管理サーバ３００が実行する処理である。
【００６９】
検索クライアント２００は、入力部２０１を経由し、ユーザから入力された情報を平文キーワード２４１として、記憶部２２０へ記憶する処理を行う（Ｓ１３０２）。検索クライアント２００は、制御部２１０により、秘匿キーワード２４２を作成し、記憶部２２０へ記憶する処理を行う（Ｓ１３０３）。検索クライアント２００は、通信部２０３から、ネットワーク４００を経由し、秘匿キーワード２４２を、管理サーバ３００へ送信する処理を行う（Ｓ１３０４）。
【００７０】
管理サーバ３００は、通信部３０３から、ネットワーク４００を経由し、検索クライアント２００が送信した秘匿キーワード２４２を受信する処理を行う（Ｓ１３０５）。管理サーバ３００は、制御部３１０により、データベース３４１から、秘匿キーワード３４２に関係する秘匿データを検索する処理を行う（Ｓ１３０６）。管理サーバ３００は、秘匿キーワード３４２に該当する検索結果（秘匿データを含む場合と含まない場合がある）を、通信部３０３から、ネットワーク４００を経由し、検索サーバへ送信する処理を行う（Ｓ１３０７）。
【００７１】
検索クライアント２００は、通信部２０３から、ネットワーク４００を経由し、管理サーバ３００が送信した、秘匿キーワード２４２に該当する検索結果を受信する処理を行う（Ｓ１３０８）。
【００７２】
秘匿データが検索結果に含まれる場合、検索クライアント２００は、制御部２１０により、検索結果に誤検索が含まれていないか、誤検索の検知処理を行う（Ｓ１３０９）。検索結果から、誤検索と判断された秘匿データとそれに関連するデータを除く（Ｓ１３１０）。
【００７３】
秘匿データが検索結果に含まれる場合、検索クライアント２００は、制御部２１０により、秘匿キーワード２４２に該当する検索結果から、平文データ２３１を復元する（Ｓ１３１１）。検索クライアント２００は、出力部２０２を経由し、抽出した平文データ２３１を記憶部２２０に記憶する。また、抽出した平文データ２３１を、出力部２０２に表示する処理を行ってもよい（Ｓ１３１２）。
【００７４】
なお、必ずしも上記に記述された手順を全て処理する必要はない。例えば、Ｓ１３０９とＳ１３１０の処理手順を省いてもよい。
【００７５】
＜秘匿データの生成方法＞
登録クライアント１００における秘匿データ１３２の生成方法の処理手順を図６と図７を用いて示す。
【００７６】
登録クライアント１００の全体処理部１１１は、鍵記憶部１５０から乱数用秘密鍵１５１とデータ暗号化鍵１５２、データ記憶部１３０から初期ベクトル１３６、タグ長１３５を取得する。登録クライアント１００の全体処理部１１１は、秘匿データ１３２の生成に必要な作業領域を一時記憶部１８０に確保する。
【００７７】
登録クライアント１００の全体処理部１１１は、平文データ１３１を取得し、暗号化部１１２が処理可能なサイズに分割する。例えば、暗号化部１１２が共通鍵暗号ＡＥＳを実装している場合、図６（ｂ）に示すように、平文データＭをＭ１、Ｍ２、……Ｍｎの１２８ビット毎のブロックに分割する。
【００７８】
登録クライアント１００の全体処理部１１１は、初期ベクトル１３６、データ暗号化鍵１５１、分割されたｎ個の平文データ１３１を暗号化部１１２に入力し、出力されたｎ個の中間暗号化データＣ１、Ｃ２、……Ｃｎを取得する。平文データ１３１の暗号化では、先に作成した中間暗号化データを利用し、次の中間暗号化データを作成する。例えば、図６（ｂ）に示すように以前の中間暗号化データと平文データ１３１の排他的論理和（ｘｏｒ算）を計算したデータを暗号化し、次の中間暗号化データを作成する。従って、ブロックＭｎに対応する中間暗号化データＣｎには、平文における他のブロックＭ１、Ｍ２、……Ｍｎ−１の内容が反映されている。
【００７９】
登録クライアント１００の全体処理部１１１は、擬似乱数生成部１１４に初期ベクトル１３６と乱数用秘密鍵を入力し、ｎ個分の中間暗号化データに用いる乱数を生成する。例えば、図６上側の図６（ａ）に示すように、初期ベクトル１３６と定数を連結したデータを、乱数用秘密鍵Ｋ２とともに擬似乱数生成部（ＲＮＧ）１１４に入力し、１２８ビット毎のｎ個分の乱数Ｒ１、Ｒ２、……Ｒｎを生成する。
【００８０】
登録クライアント１００の全体処理部１１１は、準同型関数部１１６にｎ個目の乱数Ｒｎを入力し、出力されたデータを関数値Ｘとして取得する。例えば、図７に示すように、１２８ビットの乱数を準同型関数部１１６に入力し、９６ビットの関数値を得る。
【００８１】
登録クライアント１００の全体処理部１１１は、不可逆変換部１１５に関数値Ｘを入力し、出力されたデータを不可逆変換値Ｈとして取得する。例えば、不可逆変換部１１５がハッシュ関数ＳＨＡ２５６を実装している場合、９６ビットの関数値を２５６ビットのハッシュ値（不可逆変換値）に変換する。例えば、図７に示すように、２５６ビットのハッシュ値のうち、最下位３２ビットを全体処理部１１１は抽出し、秘匿データ用の検索タグＤｎ＋１を得る。その結果、元のデータよりもデータサイズが小さい検索用のデータが得られる。
【００８２】
上記の処理によって生成された暗号文のフォーマットを図１４に示す。暗号文は、ヘッダ部分である８ビットのＮｏｎｃｅ、平文を構成する各ブロックを乱数によって暗号化した暗号文本体、及び乱数の準同型関数値のハッシュ値である検索タグから構成される。
【００８３】
登録クライアント１００の全体処理部１１１は、不可逆変換値Ｈから、タグ長１３５に記録されたビット長を秘匿データ用の検索タグＤｎ＋１として取得する。例えば、図７に示すように、２５６ビットのハッシュ値のうち、最下位３２ビットを全体処理部が抽出し、照合データＤ'ｎ＋１を得る。なお、不可逆変換値Ｈから、抽出するビットは最下位ビットからに限らず、最上位ビットから抽出してもよく、既定のビットを抽出、あるいはランダムに各ビットを抽出してもよい。また、選択するビット長も任意である。
【００８４】
登録クライアント１００の全体処理部１１１は、基本演算部１１７にｎ個分の中間暗号化データと乱数を入力し、基本演算部１１７は、以下の数３に示すように、それぞれの排他的論理和（ＸＯＲ算）を計算し、出力結果Ｄ１、Ｄ２、……Ｄｎを暗号文本体として取得する。
（数３）          Ｄｉ＝Ｃｉ  ｘｏｒ  Ｒｉ（ｉ＝１、・・・ｎ）
【００８５】
登録クライアント１００の全体処理部１１１は、初期ベクトル１３６と暗号文本体Ｄ１、Ｄ２、……Ｄｎと、検察タグＤｎ＋１を連結し、これを秘匿データ１３２としてデータ記憶部１３０に格納する。
【００８６】
このように、秘匿データの生成において、秘匿データ用の検索タグＤｎ＋１を不可逆変換値Ｈから抽出して作成することにより、秘匿データのサイズを小さく抑えることができる。例えば、図７に従って、１２８ビットの平文から秘匿データを作成した場合、初期ベクトルのサイズ（仮に３２ビットとする）に、暗号文本体の１２８ビットと秘匿データの３２ビットを合計し、１９２ビット程度ですむ。
【００８７】
一方で、秘匿データ用の検索タグのサイズを小さくすると、検索タグにおける情報量が十分に足りず、管理サーバにおける誤検索の発生確率が高まるという副作用も生じる。この副作用を抑えるための、本実施例では、誤検索の検知手段について図１０を用いて後述する。
【００８８】
なお、上記の秘匿データを作成する手順は、必ずしも上記に記述された通りの順序で処理する必要はなく、異なる順序で実施してもよい。
【００８９】
＜秘匿キーワードの生成方法＞
検索クライアント２００における秘匿キーワード２４２の生成方法の処理手順を、図８を用いて示す。
【００９０】
検索クライアント２００の全体処理部２１１は、鍵記憶部２５０から乱数用秘密鍵２５１、データ暗号化鍵２５２と関数値暗号化鍵２５４を取得し、データ記憶部２３０から初期ベクトル２３６を取得する。検索クライアント２００の全体処理部２１１は、秘匿キーワード２４２の生成に必要な作業領域を一時記憶部２８０に確保する。
【００９１】
検索クライアント２００の全体処理部２１１は、平文キーワード２４１を取得し、暗号化部２１２が処理可能なサイズに分割する。例えば、図６（ｂ）における平文データ１３１の暗号化同様、１２８ビット毎に平文キーワードＭをＭ１、Ｍ２、……Ｍｎに分割する。
【００９２】
検索クライアント２００の全体処理部２１１は、初期ベクトル２３６、データ暗号化鍵２５２、分割された平文キーワード２４１を暗号化部２１２に入力し、出力されたｎ個の中間暗号化キーワードＣ１、Ｃ２、……Ｃｎを取得する。
【００９３】
平文キーワード２４１の暗号化は、平文データ１３１の暗号化と同様、先に作成した中間暗号化キーワードを利用し、次の中間暗号化キーワードを作成する。例えば、図６下側の図６（ｂ）に示すように、以前の中間暗号化キーワードと平文キーワード２４１をｘｏｒしたデータを暗号化し、次の中間暗号化キーワードを作成する。
【００９４】
検索クライアント２００の全体処理部２１１は、擬似乱数生成部２１４に初期ベクトル（Ｗ０）２３６と乱数用秘密鍵（Ｋ２）２５１を入力し、ｎ番目の中間暗号化キーワードＣｎとのｘｏｒに用いる１個分の乱数Ｒ'ｎを生成する。
【００９５】
検索クライアント２００の全体処理部２１１は、準同型関数部２１６に乱数Ｒ'ｎを入力し、出力されたデータを関数値Ｘとして取得する。例えば、図８に示すように、１２８ビットの乱数Ｒ'ｎを準同型関数部２１６に入力し、９６ビットの関数値Ｘを得る。
【００９６】
検索クライアント２００の全体処理部２１１は、関数値暗号化鍵（Ｋ３）２５４と関数値Ｘを暗号化部２１２に入力し、出力されたデータを秘匿キーワード用の検索タグＷｎ＋１として取得する。例えば、図８に示すように、暗号化部２１２が９６ビットの関数値Ｘをデータ暗号化鍵（Ｋ１）２５２と初期ベクトル（Ｗ０）２３６を用い、１２８ビットの暗号文を出力し、それを秘匿キーワード用の検索タグＷｎ＋１とする。
【００９７】
検索クライアント２００の全体処理部２１１は、基本演算部２１７にｎ個目の中間暗号化キーワードＣｎと乱数Ｒ'ｎを入力し、基本演算部２１７はその排他的論理和（ＸＯＲ算）を計算し、出力結果Ｗｎを暗号化キーワード本体として取得する。
【００９８】
検索クライアント２００の全体処理部２１１は、初期ベクトルＷ０、暗号化キーワード本体Ｗｎと秘匿キーワード用の検察タグＷｎ＋１を連結し、これを秘匿キーワード２４２としてデータ記憶部２３０に格納する。
【００９９】
全体処理部は、以下の数４に示すように、ｎ番目の中間暗号化キーワードＣｎと乱数Ｒ'ｎの排他的論理和（ＸＯＲ算）をとったデータを暗号化キーワード本体Ｗｎとする。
（数４）    Ｗｎ＝Ｃｎ  ｘｏｒ  Ｒ'ｎ
【０１００】
これら秘匿キーワード用の検索タグＷｎ＋１と暗号化キーワード本体Ｗｎに、秘匿キーワード用の索タグを連結したデータを秘匿キーワード２４２とする。
【０１０１】
このように、秘匿キーワードの生成において、暗号化キーワードのブロック数がｎ個ある場合でも、秘匿キーワードは２ブロック分の暗号文のサイズに抑えることができる。例えば、図７に従って、１２８００（ｎ＝１００）ビットの平文から秘匿キーワードを作成した場合に、秘匿キーワードは２５６ビット（１２８ビット２個分）程度ですむ。
【０１０２】
なお、上記の秘匿キーワードを作成する手順は、必ずしも上記に記述された通りの順序で処理する必要はなく、異なる順序で実施してもよい。
【０１０３】
＜秘匿データの検索方法＞
管理サーバ３００における秘匿データの検索方法の処理手順を、図９を用いて示す。具体的には、管理サーバ３００は、秘匿データと秘匿キーワード３４２を用い、平文データと平文キーワード２４１が同一であるかを検知する処理手順を示す。
【０１０４】
管理サーバ３００の全体処理部３１１は、鍵記憶部３５０から関数値復号鍵３５４、データ記憶部３３０から秘匿キーワード３４２、タグ長３３５、データベース３４１内に格納されている秘匿データを取得する。管理サーバ３００の全体処理部３１１は、秘匿データの検索に必要な作業領域を一時記憶部３８０に確保する。
【０１０５】
管理サーバ３００の全体処理部３１１は、秘匿データにおける暗号文本体を取得し、暗号化部１１２が処理したサイズに分割されたブロックのうち、ｎ番目のブロックを取り出す。例えば、秘匿データＤをＤ０、Ｄ１、Ｄ２、……Ｄｎ、Ｄｎ＋１と分割されたブロックの集合とみなし、データＤｎを取り出す。
【０１０６】
管理サーバ３００の全体処理部３１１は、秘匿キーワード３４２における暗号化キーワード本体を取得する。例えば、秘匿キーワードＷをＷ０、Ｗｎ、Ｗｎ＋１と３分割されたブロックの集合とみなし、２番目のデータＷｎを取り出す。
【０１０７】
管理サーバ３００の全体処理部３１１は、基本演算部３１７に暗号文本体Ｄｎと暗号化キーワードＷｎを入力し、基本演算部３１７はその排他的論理和（ＸＯＲ算）を計算し、数５に沿って、出力結果を取得する。
（数５）  Ｄｎ  ｘｏｒ  Ｗｎ＝（Ｃｎ  ｘｏｒ  Ｒｎ）ｘｏｒ（Ｃｎ  ｘｏｒ  Ｒ'ｎ）
【０１０８】
ここで、平文データと平文キーワードの値が同じである場合、それらを暗号化した中間暗号化データと中間暗号文の値が等しいため、以下の数６が導ける。
（¬（Ａ  ｘｏｒ  Ｂ）＝Ａ・Ｂ＋¬Ａ・¬Ｂより、但し¬は否定又は補集合）
（数６）      Ｄｎ  ｘｏｒ  Ｗｎ  ＝  Ｒｎ  ｘｏｒ  Ｒ'ｎ
即ち、乱数（ＲｎとＲ'ｎ）の情報のみが数６に残される。
【０１０９】
管理サーバ３００の全体処理部３１１は、基本演算部３１７の出力結果を準同型関数部３１６に入力し、準同型関数部３１６の出力結果である関数値Ｙを取得する。例えば、図９に示すように、暗号化データ本体におけるｎ番目の１２８ビットのブロックＤｎと１２８ビットの秘匿キーワード本体との排他的論理和（ＸＯＲ）をとり、その値を準同型関数部３１６に入力し、以下の数７に示すように、例えば９６ビットの関数値Ｙを得る。
（数７）    Ｙ＝Ｆ（Ｄｎ  ｘｏｒ  Ｗｎ）
数６が成り立つ場合、数７から以下の数８が導ける。
（数８）    Ｙ＝Ｆ（Ｒｎ  ｘｏｒ  Ｒ'ｎ）
【０１１０】
管理サーバ３００の全体処理部３１１は、秘匿キーワード３４２における秘匿キーワードの検索タグを取得する。例えば、秘匿キーワードＷをＷ０、Ｗｎ、Ｗｎ＋１と３分割されたブロックの集合とみなし、３番目のデータＷｎ＋１を取り出す。
【０１１１】
管理サーバ３００の全体処理部３１１は、関数値復号化鍵（Ｋ３）３５４、秘匿キーワードの検索タグＷｎ＋１を復号化部３１３に入力し、復号された関数値Ｘを取得する。関数値Ｘは、乱数Ｒｎと数２における準同型関数Ｆを用い、以下の数９で表わされる。
（数９）      Ｘ＝Ｆ（Ｒｎ）
【０１１２】
管理サーバ３００の全体処理部３１１は、基本演算部３１７に関数値Ｘと関数値Ｙを入力し、基本演算部３１７はその排他的論理和（ＸＯＲ算）を計算し、出力された関数値Ｚを取得する。関数値Ｚに対しては以下に示す数１０が成り立つ。
（Ａ  ｘｏｒ  （Ａ  ｘｏｒ  Ｂ）＝Ａ・¬（Ａ  ｘｏｒ  Ｂ）＋¬Ａ・（Ａ  ｘｏｒ  Ｂ）＝Ａ・Ｂ＋¬Ａ・Ｂ＝Ｂより、データ（Ｂ）に他のデータ（Ａ）による排他的論理和の演算を２度施すと元のデータ（Ｂ）が得られる）
（数１０）
Ｚ＝  Ｘ  ｘｏｒ  Ｙ
＝  Ｆ（Ｒｎ）ｘｏｒ（Ｆ（Ｒｎ  ｘｏｒ  Ｒ'ｎ））
＝  Ｆ（Ｒｎ）ｘｏｒ（Ｆ（Ｒｎ）ｘｏｒ  Ｆ（Ｒ'ｎ））  （数２より）
＝  Ｆ（Ｒ'ｎ）
【０１１３】
管理サーバ３００の全体処理部３１１は、不可逆変換部３１５に関数値Ｚを入力し、出力されたデータを不可逆変換値Ｈとして取得する。例えば、図９に示すように、不可逆変換部３１５がハッシュ関数ＳＨＡ２５６を実装している場合、９６ビットの関数値Ｘと関数値Ｙの排他的論理和の値を２５６ビットのハッシュ値（不可逆変換値）に変換する。
【０１１４】
管理サーバ３００の全体処理部３１１は、不可逆変換値Ｈから、タグ長３３５に記録されたビット長を照合データＳとして取得する。例えば、図９に示すように、２５６ビットのハッシュ値のうち、最下位３２ビットを全体処理部が抽出し、照合データＤ'ｎ＋１を得る。なお、不可逆変換値Ｈから、抽出するビットは最下位ビットからに限らず、最上位ビットから抽出してもよく、既定のビットを抽出、あるいはランダムに各ビットを抽出してもよい。また、選択するビット長も任意である。
【０１１５】
管理サーバ３００の全体処理部３１１は、秘匿データにおける秘匿データの検索タグを取得する。例えば、秘匿データＤにおけるデータＤｎ＋１を取り出す。
【０１１６】
管理サーバ３００の全体処理部３１１は、基本演算部３１７に照合データＤと秘匿データの検索タグを入力し、基本演算部３１７はその比較をし、同一であればＴＲＵＥ（＝１）を、同一でなければＦＡＬＳＥ（＝０）を出力する。
【０１１７】
最後に、秘匿データの検索タグＤｎ＋１と照合データＤ'ｎ＋１を比較し、同一であるならば検索に該当、異なれば検索に非該当と判断する。
【０１１８】
なお、上記の秘匿データを検索する手順は、必ずしも上記に記述された通りの順序で処理する必要はなく、異なる順序で実施してもよい。
【０１１９】
＜秘匿データの誤検索の検知方法＞
検索タグの大きさによっては、検索結果に誤りが含まれる可能性がある。例えば、不可逆変換部１１５の出力するデータが一様に分布するとしたとき、秘匿データの検索タグを８ビットにした場合、１／２５６の確率で不可逆変換値の値が衝突してしまうため、平文データと平文キーワードの値が異なる場合にも、同一であると誤判断してしまう。即ち、正しい（平文キーワードと等しい平文データに相当する）検索結果に加え、誤った検索結果（平文データと平文キーワードの値が異なる）が含まれてしまう。同様に、検索タグを８ビットから１６ビットに変更した場合、誤検索の確率は１／６５５３６に低下する。不可逆変換値そのもの（例えば、２５６ビット）を秘匿データの検索タグとして利用した場合は、誤検索が発生する確率は漸近的にはほぼ０（真に０ではない）であるが、秘匿データが肥大化し、管理サーバのストレージを圧迫してしまう。そこで、検索クライアントにおいて、この誤検索を検知する手順を以下に説明する。
【０１２０】
検索クライアント２００における秘匿データ２３２の誤検知の処理手順を、図１０を用いて示す。具体的には、検索クライアント２００は、秘匿データ２３２と秘匿キーワード２４２を用い、平文データと平文キーワード２４１が同一であるかを検知する処理手順を示す。
【０１２１】
検索クライアント２００の全体処理部２１１は、鍵記憶部２５０から乱数用秘密鍵（Ｋ２）２５４、データ記憶部２３０から初期ベクトル（Ｄ０）２３６、一時記憶部２８０から中間暗号化キーワード（Ｃ１〜Ｃｎ）を取得する。
【０１２２】
検索クライアント２００の全体処理部２１１は、秘匿データ２３２の誤検知に必要な作業領域を一時記憶部２８０に確保する。
【０１２３】
検索クライアント２００の全体処理部２１１は、秘匿データ２３２における初期ベクトル２３６を取得する。例えば、秘匿データＤをＤ０、Ｄ１、Ｄ２、……Ｄｎ、Ｄｎ＋１と分割されたブロックの集合とみなし、初期ベクトルＤ０を取り出す。
【０１２４】
検索クライアント２００の全体処理部２１１は、擬似乱数生成部２１４に初期ベクトル２３６と乱数用秘密鍵２５４を入力し、暗号文本体に用いる乱数を生成する。例えば、図６上側の図６（ａ）に示すように、初期ベクトル２３６と定数を連結したデータを、乱数用秘密鍵（Ｋ２）２５４と共に擬似乱数生成部２１４に入力し、１２８ビット毎のｎ個分の乱数Ｒ１、Ｒ２、……Ｒｎを生成する。
【０１２５】
図１５に、以下に述べる検索誤りの検知処理の概要を示す。
【０１２６】
検索クライアント２００の全体処理部２１１は、基本演算部２１７に暗号文本体と乱数を入力し、基本演算部２１７はそれぞれの排他的論理和（ＸＯＲ算）を計算し、出力結果Ｃ'１、Ｃ'２、……Ｃ'ｎを中間暗号化データとして取得する。Ｃ'ｉと、Ｄｉ及びＲｉとの間には以下の数１１に示す関係が成り立つ。
（数１１）    Ｃ'ｉ  ＝  Ｄｉ  ｘｏｒ  Ｒｉ  （ｉ＝１、・・・ｎ）
平文データと平文キーワードの値が等しい場合は、それらの中間暗号文と中間暗号化キーワードの値が等しい。
【０１２７】
そこで、数３と数１１より、Ｄｉ＝Ｃｉ  ｘｏｒ  Ｒｉ、Ｃ'ｉ  ＝Ｄｉ  ｘｏｒ  Ｒｉ＝（Ｃｉ  ｘｏｒ  Ｒｉ）  ｘｏｒ  Ｒｉ＝Ｃｉであるので、Ｃ'ｉ  ＝Ｃｉであれば、平文データと平文キーワードの値が等しいとみなせる。検索クライアント２００は、これを確認する。
【０１２８】
検索クライアント２００の全体処理部２１１は、基本演算部２１７に中間暗号化データと中間暗号化キーワードを入力し、基本演算部２１７はそれらが等しいかを判定する。基本演算部２１７は、同一（Ｃ'ｉ  ＝Ｃｉ）であればＴＲＵＥ（＝１）を、異なればＦＡＬＳＥ（＝０）を出力する。全体処理部は、ＦＡＬＳＥが返ってきた場合、誤検索が発生したと判断する。
【０１２９】
なお、上記の誤検索を検知する手順は、必ずしも上記に記述された通りの順序で処理する必要はなく、異なる順序で実施してもよい。
【０１３０】
以上に述べたように、本実施例の検索処理では、平文に対応する暗号文が一致するかどうかは、暗号化に用いた乱数から生成される検索タグが一致するかどうかを判定している。平文を暗号化して中間暗号を生成するときに用いた乱数は、暗号化したまま行われる本実施例の検索処理における平文の一致を特徴づける量である。即ち、この乱数から生成される検索タグは、平文を直接反映したものではないが、平文に対応する量となっている。
【０１３１】
また、以上に述べたように、本実施例における検索タグを用いた検索処理は、ｎビットの検索タグを用いて１／２ｎの精度で、１次検索がサーバ側で行われ（Precision（検索結果の適合率）＜１）、データを復号して比較（中間暗号レベルで比較可能）する２次検索がクライアント側で行われる（最終的にPrecisionを１にする）。
【０１３２】
＜秘匿データの復号方法＞
検索クライアント２００における秘匿データ２３２の復号方法の処理手順を、図１１を用いて示す。
【０１３３】
検索クライアント２００の全体処理部２１１は、鍵記憶部２５０から乱数用秘密鍵２５１とデータ復号化鍵２５３、データ記憶部２３０から初期ベクトル２３６を取得する。
検索クライアント２００の全体処理部２１１は、秘匿データ２３２の復号に必要な作業領域を一時記憶部２８０に確保する。
【０１３４】
検索クライアント２００の全体処理部２１１は、秘匿データ２３２における初期ベクトル２３６を取得する。例えば、秘匿データＤをＤ０、Ｄ１、Ｄ２、……Ｄｎ、Ｄｎ＋１と分割されたブロックの集合とみなし、初期ベクトルＤ０を取り出す。
【０１３５】
検索クライアント２００の全体処理部２１１は、擬似乱数生成部２１４に初期ベクトル２３６と乱数用秘密鍵２５１を入力し、暗号文本体に用いるｎ個分の乱数を生成する。例えば、図６上側の図６（ａ）に示すように、初期ベクトル２３６と定数を連結したデータを、乱数用秘密鍵２５１と共に擬似乱数生成部２１４に入力し、１２８ビット毎のｎ個分の乱数Ｒ１、Ｒ２、……Ｒｎを生成する。
【０１３６】
検索クライアント２００の全体処理部２１１は、基本演算部２１７に暗号文本体と乱数を入力し、基本演算部２１７はそれぞれの排他的論理和（ＸＯＲ算）を計算し、出力結果Ｃ'１、Ｃ'２、……Ｃ'ｎを中間暗号化データとして取得する。
【０１３７】
検索クライアント２００の全体処理部２１１は、初期ベクトル２３６、データ復号化鍵２５３、ｎ個の中間暗号化データを復号化部に入力し、出力されたｎ個の平文データＭ１、Ｍ２、……Ｍｎを取得する。中間暗号化データの復号は、例えば、図１１に示すように以前の中間暗号化データと平文データをｘｏｒしたデータを平文データ２３１としてデータ記憶部２３０に格納する。
【０１３８】
なお、秘匿データの復号手順は、必ずしも上記に記述された通りの順序で処理する必要はなく、異なる順序で実施してもよい。
【符号の説明】
【０１３９】
１００：登録クライアント、２００：検索クライアント、３００：管理サーバ、４００：ネットワーク、５００：コンピュータ、１０１、２０１、３０１：入力部、１０２、２０２、３０２：出力部、１０３、２０３、３０３：通信部、１１０、２１０、３１０：制御部、１１１、２１１、３１１：全体処理部、１１２、２１２：暗号化部、２１３、３１３：復号化部、１１４、２１４：擬似乱数生成部、１１５、２１５、３１５：不可逆変換部、１１６、２１６、３１６：準同型関数部、１１７、２１７、３１７：基本演算部、１２０、２２０、３２０：記憶部、１３０、２３０、３３０：データ記憶部、１３１、２３１：平文データ、１３２、２３２：秘匿データ、２４１：平文キーワード、２４２、３４２：秘匿キーワード、３４１：データベース、１５０、２５０、３５０：鍵記憶部、１５１、２５１：乱数用秘密鍵、１５２、２５２：データ暗号化鍵、２５３：データ復号化鍵、２５４、３５４：関数値暗号化鍵、１３５、３３５：タグ長、１３６，２３６：初期ベクトル、１８０、２８０、３８０：一時記憶部、５０１：ＣＰＵ（Central Processing Unit）、５０２：メモリ、５０３：外部記憶装置、５０８：記憶媒体、５０７：読書装置、５０６：入力装置、５０５：出力装置、５０４：通信装置、５０９：内部通信線
【図１】
2015035072.tif 000003
【図２】
2015035072.tif 000004
【図３】
2015035072.tif 000005
【図４】
2015035072.tif 000006
【図５】
2015035072.tif 000007
【図６】
2015035072.tif 000008
【図７】
2015035072.tif 000009
【図８】
2015035072.tif 000010
【図９】
2015035072.tif 000011
【図１０】
2015035072.tif 000012
【図１１】
2015035072.tif 000013
【図１２】
2015035072.tif 000014
【図１３】
2015035072.tif 000015
【図１４】
2015035072.tif 000016
【図１５】
2015035072.tif 000017