(57)【特許請求の範囲】
【請求項１】
データの暗号化処理と復号処理に関するプログラムを記憶部に格納する検索エージェントと、暗号化データの一致検索処理に関するプログラムを記憶部に格納する管理サーバが、ネットワーク経由で連携する検索処理システムであって、
検索エージェントは平文リファレンスから1次暗号化リファレンスと2次暗号化リファレンスを作成し、
検索エージェントは平文リードから1次暗号化リードと2次暗号化リードを作成し、
管理サーバは、1次暗号化リファレンスと1次暗号化リードの検索結果と、２次暗号化リファレンスと２次暗号化リードの検索結果と、により、平文リファレンスと平文リードの類似性を判定すること、
を特徴とする検索処理システム。
【請求項２】
請求項１記載の検索処理システムであって、
前記1次暗号化リファレンスとは、ブロック単位に分割された平文リファレンスを暗号化して作成されたものであって、
前記２次暗号化リファレンスとは、ブロック単位に分割された平文リファレンスとインデックスを連結したデータを暗号化して作成されたものであって、
前記1次暗号化リードとは、前記1次暗号化リファレンスと同じブロック単位に分割された平文リードを暗号化して作成されたものであって、
前記２次暗号化リードとは、前記2次暗号化リファレンスと同じブロック単位に分割された平文リードとインデックスを連結したデータを暗号化して作成されたものであること、
を特徴とする検索処理システム。
【請求項３】
請求項１記載の検索処理システムであって、
2次暗号化リファレンスと2次暗号化リードの前記検索結果とは、管理サーバが、2次暗号化リファレンスと2次暗号化リードの判定の是非により加点と減点を用いて得点化し、得点の高い場合に2次暗号化リファレンスが2次暗号化リードと類似していると判定する処理の結果であること、
を特徴とする検索処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サーバが格納する暗号化データを復号せずに、サーバに暗号化データの高速な類似検索を委託可能な検索処理システムに関する。
【背景技術】
【０００２】
近年、バイオインフォマティクス分野では、分析装置の普及などに伴い、ゲノム解析が飛躍的に進展している。その解析において、ある断片的なゲノム情報が、蓄積されたゲノムデータのどの部分に類似しているかを判定することが必要だが、そのための標準的なアルゴリズムがある。しかし、大容量のゲノムデータを保管し、判定処理を実行するには多大な計算リソースが必要なため、クラウド上での類似検索サービスが提供されることが望まれている。
【０００３】
一方、クラウドシステムにおいては、情報システムを管理する組織が、情報システムを利用する組織とは異なるため、情報漏えいの防止策や、事故発生後の原因究明、再発防止策等が自組織だけでは立てにくい。そのため、事前に、データの不正流出の予防策として、暗号技術を活用し、データの機密性を確保する必要がある。
【０００４】
そこで、クラウドシステムに暗号化したデータを預託し、クラウドシステムにデータを暗号化したまま検索させる、暗号技術が研究されている。例えば、非特許文献１や非特許文献２には、復号せずに暗号化データを検索する検索処理方式が記載されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】吉野 雅之, 長沼 健, 佐藤 尚宜. DB向け検索可能暗号の検討(2), Inproceedings of The 2011 Symposium on Cryptography and Information Security(2011).
【非特許文献２】Dan Boneh, Brent Waters: Conjunctive, Subset, and Range Queries on Encrypted Data. TCC, volume 4392 of Lecture Notes in Computer Science, pages 535-554(2007).
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１は、共通鍵暗号をベースとしており、高速であるが、完全一致検索のみが可能であり、類似検索ができない。例えば、データ「abcd」を検索する場合、その部分文字列である「ab」を検索リードでは、「abcd」を検索できない。一方、非特許文献２の技術は、部分一致検索が可能であるものの、演算処理の重い合成数位数の双線形群によるペアリングを用いるため、低速である。そのため、検索キーワードと被検索データを共に暗号化しながら、それらの類似性を高速に解析する処理方式が必要とされている。
【課題を解決するための手段】
【０００７】
前記課題を解決するために、本発明は、データの暗号化処理と復号処理に関するプログラムを記憶部に格納する検索エージェントと、暗号化データの一致検索処理に関するプログラムを記憶部に格納する管理サーバが、ネットワーク経由で連携する検索処理システムであって、検索エージェントは、非特許文献１や非特許文献２などのデータの暗号化と復号を実現するプログラムを記憶部に格納し、管理サーバは非特許文献１や非特許文献２などの暗号化データの一致検索を実現するプログラムを記憶部に格納し、検索エージェントは記憶部に格納された平文リファレンスを、ブロック単位に分割したデータを暗号化して１次暗号化リファレンスと２次暗号化リファレンスを作成し、また検索エージェントは記憶部に格納された検索エージェントは記憶部に格納された平文リードを、ブロック単位に分割したデータを暗号化して１次暗号化リードと２次暗号化リードを作成し、管理サーバによる１次暗号化リファレンスと1次暗号化リードの検索結果と、管理サーバによる２次暗号化リファレンスと２次暗号化リードの検索結果の是非による得点に従い、得点の高い２次暗号化リファレンスが２次暗号化リードと類似している、と判定する。
【発明の効果】
【０００８】
検索エージェントは、検索キーワードと被検索データを共に暗号化したまま、検索キーワードに類似した、被検索データを管理サーバに検知させる処理を高速に行うことができる。
【図面の簡単な説明】
【０００９】
【図１】第一実施形態において、検索処理委託システムの概略を例示する図である。
【図２】第一実施形態において、検索エージェントの機能の概略を例示する図である。
【図３】第一実施形態において、管理サーバの機能の概略を例示する図である。
【図４】コンピュータの概略構成を例示する図である。
【図５】第一実施形態において、検索エージェントと管理サーバがネットワーク100経由で実施する、1次暗号化リファレンスと2次暗号化リファレンスの登録処理の処理フローを例示する図である。
【図６（ａ）】第一実施形態において、検索エージェントのデータ記憶部に格納される、平文リファレンスを例示する図である。
【図６（ｂ）】第一実施形態において、管理サーバのデータ記憶部に格納される、1次暗号化リファレンスと2次暗号化リファレンスを例示する図である。
【図７】第一実施形態において、検索エージェントと管理サーバがネットワーク100経由で実施する、2次暗号化リファレンスの検索処理の処理フローを例示する図である。
【図８】第一実施形態において、登録エージェントが1次暗号化リファレンスを作成する処理フローを例示する図である。
【図９】第一実施形態において、登録エージェントが2次暗号化リファレンスを作成する処理フローを例示する図である。
【図１０】第一実施形態において、検索エージェントが1次暗号化リードに該当する2次暗号化リファレンスを検索する処理フローを例示する図である。
【図１１】第一実施形態において、登録エージェントが2次暗号化リードを作成する処理フローを例示する図である。
【図１２】第一実施形態において、管理サーバが2次暗号化リードに該当する2次暗号化リファレンスを検索する処理フローを例示する図である。
【図１３】検索エージェント200の全体処理部211が出力部に表示した検索結果を例示図である。
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態において、同一の部材には原則として同一の符号を付け、繰り返しの説明は省略する。
（実施の形態１）
図１は、本発明の第一の実施の形態である検索処理システムの概略図である。図示するように、検索処理システムは、検索エージェント200と、管理サーバ300と、を備え、検索エージェント200と管理サーバ300は、ネットワーク100を介して相互に情報を送受信できるように設計されている。
【００１１】
本実施形態における検索エージェント200は、データと検索用のリファレンス(以下、リファレンスと呼ぶ)を管理サーバ300に送信し、受信結果を管理サーバ300から受信する送受信装置として機能し、かつ検索処理委託用のリード（以下、リードと呼ぶ）を管理サーバ300に送信し、その検索結果を管理サーバ300から受信する送受信装置として機能し、管理サーバ300は、リファレンスを記憶し、また受信したリードを用いて、リファレンスを検索する送受信装置として機能する。
【００１２】
＜図２＞
図２は、検索エージェント200の機能概略図である。図示するように、登録エージェント200は、制御部210と、記憶部220と、入力部201と、出力部202と、通信部203と、を備える。
【００１３】
記憶部220は、データ記憶部230と、プログラム記憶部260と、一時情報記憶部280と、を備える。
【００１４】
データ記憶部230には、管理サーバ300に送信するデータである、暗号化前のリファレンス（以下、平文リファレンス231と呼ぶ）に関する情報が記憶される。本実施形態においては、入力部201を介して、受け付けた平文リファレンス231に関する情報と、検索処理に用いる暗号化前のリード（以下、平文リード233）に関する情報と、管理サーバ300に（暗号化後に）登録する、平文リファレンス231に関する情報と、公開パラメータ237に関する情報が記憶される。また、リファレンス暗号化部213が出力する1次暗号化リファレンスと2次暗号化リファレンスに関する情報と、リード暗号化部217が出力する1次暗号化リードと2次暗号化リードに関する情報も記憶される。また、安全性の観点から登録エージェント200が秘密に管理すべき、秘密鍵251に関する情報も記憶される。
【００１５】
プログラム記憶部260には、鍵生成、暗号化、復号などの暗号処理全般を含めた、1次暗号化リファレンスと2次暗号化リファレンスの登録処理に関するプログラムと、1次暗号化リードと2次暗号化リードによる検索処理に関するプログラムが記憶されている。1次暗号化リファレンスと2次暗号化リファレンスの登録処理については、図５を用い、後で詳しく報告する。また、1次暗号化リードによる2次暗号化リファレンスの検索処理については、図８を用い、後で詳しく報告する。2次暗号化リードによる2次暗号化リファレンスの検索処理については、図９を用い、後で詳しく報告する。
【００１６】
一時情報記憶部280には、制御部210などの処理に必要な情報が記憶される。
【００１７】
制御部210は、全体処理部211と、鍵生成部212と、リファレンス暗号化部213と、リファレンス復号部215と、リード暗号化部217と、を備える。
【００１８】
全体処理部211は、プログラム記憶部260から、1次暗号化リファレンスと2次暗号化リファレンスの登録処理に関するプログラムをロードし、検索エージェント200における各モジュール間の制御を行い、さらに簡単な演算処理を実施する。
【００１９】
例えば、全体処理部211は、入力部201を介して、入力を受け付けた情報を、データ記憶部230に、平文リファレンス231として、記憶する処理を行う。また、本実施形態において、全体処理部211は、平文リファレンス231を、出力部202に表示する処理を行う。
【００２０】
また、本実施形態において、全体処理部211は、データ記憶部230に記憶した平文リファレンス231を読み込み、リファレンス暗号化部213に入力し、出力されたデータを、データ記憶部230に、1次暗号化リファレンスまたは2次暗号化リファレンスとして、記憶する処理を行う。
【００２１】
また、本実施形態において、全体処理部211は、データ記憶部230に記憶した平文リード233を読み込み、リード暗号化部217に入力し、出力されたデータを、データ記憶部230に、1次暗号化リードまたは2次暗号化リードとして、記憶する処理を行う。
【００２２】
また、本実施形態において、全体処理部211は、1次暗号化リファレンス、2次暗号化リファレンス、1次暗号化リード、2次暗号化リードを、通信部203を介して、管理サーバ300に送信し、受信結果を管理サーバ300から受信する処理を行う。
【００２３】
また、本実施形態において、全体処理部211は、1次暗号化リードと2次暗号化リードを、通信部203を介して、管理サーバ300に送信し、2次暗号化リファレンスの検索結果を管理サーバ300から受信する処理を行う。
【００２４】
さらに、本実施形態において、全体処理部211は、管理サーバ300より、通信部203を介して受信した、2次暗号化リファレンスを一時情報記憶部280に記憶する処理と、出力部202に表示する処理を行う。
【００２５】
鍵生成部212は、秘密鍵251と公開パラメータ237を生成する処理を行う。例えば、本実施形態において、全体処理部211が公開パラメータ237を入力し、鍵生成部212が秘密鍵251を出力する処理を行う。なお、全体処理部211は公開パラメータ237の一部として記憶された公開パラメータ237をロードしてもよいし、入力部201を経由して鍵生成部212に入力してもよい。
【００２６】
秘密鍵251の実現方法については、各暗号方式の鍵生成アルゴリズム(ＡＥＳ暗号、ＤＥＳ暗号、検索可能暗号など)の実装により、実現可能であるため、その詳細な説明は省く。
【００２７】
リファレンス暗号化部213（と、検索エージェント200のリード暗号化部217）が用いる、秘密鍵251と公開パラメータ237の実現方法については、各暗号方式の鍵生成方法（検索可能暗号など）の実装により、実現可能であるため、その詳細な説明は省く。
【００２８】
リファレンス暗号化部213は、全体処理部211と連携し、平文リファレンス231を暗号化する処理を行う。平文リファレンス231とは、文字、数字、記号から構成されるディジタルデータである。図6(a)は、DNAの塩基配列を意味する文字（A：アデニン、G：グアニン、C：シトシン、T：チミン）から構成されるディジタルデータである、平文リファレンス231を例示したものである。
【００２９】
リード暗号化部217は、全体処理部211と連携し、平文リード233を暗号化する処理を行う。平文リード233は、平文リファレンス231と同様に、文字、数字、記号から構成されるディジタルデータである。
【００３０】
本実施形態においては、全体処理部211が平文リファレンス231と秘密鍵251をリファレンス暗号化部213に入力し、リファレンス暗号化部213は1次暗号化リファレンスと2次暗号化リファレンスを出力する処理を行う。1次暗号化リファレンスの作成方法については、図８を用い、後で詳しく説明する。2次暗号化リファレンスの作成方法については、図９を用い、後で詳しく説明する。
【００３１】
本実施形態において、全体処理部211が平文リード233と秘密鍵251をリード暗号化部217に入力し、リード暗号化部217は1次暗号化リードと2次暗号化リードを出力する処理を行う。1次暗号化リードの作成方法については、図１０を用い、後で詳しく説明する。2次暗号化リードの作成方法については、図１１を用い、後で詳しく説明する。
【００３２】
＜図３＞
図３は、管理サーバ300の機能概略図である。図示するように、管理サーバ300は、制御部310と、記憶部320と、入力部301と、出力部302と、通信部303と、を備える。
【００３３】
記憶部320は、プログラム記憶部360と、データ記憶部330と、一時情報記憶部380と、を備える。
【００３４】
データ記憶部330には、通信部303を介して、登録エージェント200から受信したデータに関する情報が、記憶される。本実施形態において、通信部303を介して、受信した1次暗号化リファレンス331と2次暗号化リファレンス332に関する情報が記憶される。また、公開パラメータ337に関する情報が記憶される。また、通信部303を介して、検索エージェント200から受信したデータに関する情報が、記憶される。本実施形態において、通信部303を介して、受信した1次暗号化リードと2次暗号化リードに関する情報が一時的に記憶される。
【００３５】
プログラム記憶部360には、2次暗号化リファレンス332の検索処理に関するプログラムが記憶されている。2次暗号化リファレンス332の検索処理については、図１０と図１２を用い、後で詳しく報告する。
【００３６】
一時情報記憶部380には、制御部310での処理で必要となる情報が記憶される。
【００３７】
制御部310は、全体処理部311と、検査部312と、を備える。  
【００３８】
全体処理部311は、プログラム記憶部360から、2次暗号化リファレンス332の検索処理に関するプログラムをロードし、管理サーバ300における各モジュール間の制御を行い、さらに簡単な演算処理を実施する。
【００３９】
例えば、全体処理部311は、通信部303を介して、1次暗号化リファレンス331、2次暗号化リファレンス332、1次暗号化リード、2次暗号化リードを、登録エージェント200から受信し、データ記憶部330に、記憶する処理を行う。1次暗号化リファレンス331と2次暗号化リファレンス332の保管方法については、図６(a)と図６(b)を用い、後で詳しく報告する。
【００４０】
また、本実施形態において、全体処理部311は、通信部303を介して、1次暗号化リードと2次暗号化リードを、検索エージェント200から受信し、データ記憶部330に、記憶する処理を行う。
【００４１】
また、本実施形態において、全体処理部311は、1次暗号化リードと1次暗号化リファレンス331を検査部312に入力し、または2次暗号化リードと2次暗号化リファレンス332を検査部312に入力し、検索部312が出力したデータを、受け取る処理を行う。
【００４２】
さらに、全体処理部311は、検索エージェント200または登録エージェント200より、通信部303を介して受信したデータに関する情報を、一時情報記憶部380に記憶する処理と、出力部302に表示する処理を行う。
【００４３】
＜図４＞
以上に示した検索エージェント200、管理サーバ300は、例えば、図４（コンピュータの概略図）に示すような、ＣＰＵ501と、メモリ502と、ＨＤＤ等の外部記憶装置503と、ＣＤやＤＶＤ等の可搬性を有する記憶媒体508に対して情報を読み書きする読書装置507と、キーボードやマウス等の入力装置506と、ディスプレイ等の出力装置505と、通信ネットワークに接続するためのＮＩＣ等の通信装置504と、これらを連結するシステムバス等の内部通信線(システムバスという)と、を備えた一般的なコンピュータで実現できる。
【００４４】
例えば、記憶部220、320は、ＣＰＵ501がメモリ502または外部記憶装置503を利用することにより実現可能であり、制御部210、310に含まれる各処理部は、外部記憶装置503に記憶されている所定のプログラムをメモリ502にロードしてＣＰＵ501で実行することで実現可能であり、入力部201、301は、ＣＰＵ501が入力装置506を利用することで実現可能であり、出力部202、302は、ＣＰＵ501が出力装置505を利用することで実現可能であり、通信部203、303は、ＣＰＵ501が通信装置504を利用することで実現可能である。
【００４５】
この所定のプログラムは、読書装置507を介して記憶媒体508から、あるいは、通信装置504を介してネットワーク100から、外部記憶装置503に記憶(ダウンロード)され、それから、メモリ502上にロードされて、ＣＰＵ501により実行されるようにしてもよい。また、読書装置507を介して、記憶媒体508から、あるいは通信装置504を介してネットワーク100から、メモリ502上に直接ロードされ、ＣＰＵ501により実行されるようにしてもよい。
【００４６】
＜図５：1次暗号化リファレンス331と2次暗号化リファレンス332の登録処理＞
図５は、本実施形態において、ネットワーク100を経由し、検索エージェント200が送信した1次暗号化リファレンスと2次暗号化リファレンスを、管理サーバ300が、記憶部320へ登録する処理を示すシーケンス図である。
【００４７】
検索エージェント200の全体処理部211は、平文リファレンス231をロードし、リファレンス暗号化部213へ入力する(S601)。
【００４８】
検索エージェント200のリファレンス暗号化部213は、記憶部220に格納された秘密鍵251と公開パラメータ237をロードし、平文リファレンス231を1次暗号化リファレンスと2次暗号化リファレンスに変換する。なお、変換方法については、図８と図９を用い、後で詳しく説明する(S602)。
【００４９】
検索エージェント200の通信部203は、リファレンス暗号化部213より出力された1次暗号化リファレンスと2次暗号化リファレンスを、ネットワーク100を経由し、管理サーバ300へ送信する処理を行う(S603)。
【００５０】
管理サーバ300の通信部303から、ネットワーク100を経由し、登録エージェント200が送信した1次暗号化リファレンスと2次暗号化リファレンスを受信する処理を行う(S604)。
【００５１】
管理サーバ300の全体処理部311は、1次暗号化リファレンス331と2次暗号化リファレンス332を記憶部320へ格納する(S605)。 
管理サーバ300は、1次暗号化リファレンス331と2次暗号化リファレンス332の記憶部320への格納処理を終えた場合、「登録成功」とし、通信部303から、ネットワーク100を経由し、「登録成功」を示すデータを検索エージェント200へ送信する処理を行う。また、記憶量の制限等を理由に、格納処理が終了できなかった場合、「登録失敗」とし、通信部303から、ネットワーク100を経由し、「登録失敗」を示すデータを検索エージェント200へ送信する処理を行う（S606）。
【００５２】
検索エージェント200の通信部203から、ネットワーク100を経由し、管理サーバ300が送信した「登録成功」または「登録失敗」を示すデータを受信する処理を行う(S607)。
【００５３】
上記の処理(S601からS607)により、検索エージェント200は、ネットワーク100経由で、管理サーバ300に平文リファレンス231を暗号化し、管理サーバ300のの記憶部320への格納を指示し、その処理結果を確認できる。
【００５４】
なお、上記の処理手順は、固定されたものではなく、処理手順を変更して実施してもかまわない。例えば、検索エージェント200は、1次暗号化リファレンスを作成、送信後に、2次暗号化リファレンス332を作成、送信するようにS602とS603を変更してもよい。また、管理サーバ300も、1次暗号化リファレンスと2次暗号化リファレンスの受信、記憶処理を個別に実施してもよい。同様に、他の処理内容を変更してもよい。
【００５５】
＜図６：平文リファレンス231と1次暗号化リファレンス331と2次暗号化リファレンス332＞
図６(a)は、検索エージェント200の記憶部220内のデータ記憶部230における平文リファレンス231を例示している。図６(a)の例では、平文リファレンス231は1文字毎に分割可能なアルファベットや記号（終端文字など）による、ｍ文字のデータ(バイトコードなどで表現)として表現されている。
【００５６】
図６(b)は、管理サーバ300の記憶部320内のデータ記憶部330における1次暗号化リファレンス331と2次暗号化リファレンス332を例示している。図６(b)の例では、1次暗号化リファレンス331は一定数の文字列毎（11文字毎など）に平文リファレンス231が暗号化されている。図６(a)の例を用いると、 B1ブロックはGCTATACTGCTの11文字の文字列からなり、これを暗号化したEs(B1)が1つの暗号文として保存されている。同様に、B2ブロックは、B1ブロックを1文字ずらしたCTATACTGCTAの文字列からなり、これを暗号化したEs(B2)がEs(B1)と同様に保存されている。また、2次暗号化リファレンス332はある暗号化されたインデックスと平文リファレンス231の一文字を連結し、これが暗号化して保存されている。同様に、他の文字列も暗号化され、（m-10）個の暗号文から、1次暗号化リファレンス331は構成される。図６(b)の例では、インデックス1が暗号化されたE(1)と平文リファレンス231の一文字目であるGが（G||E(1)）として連結され（ただし、||はデータの連結を意味する）、これを暗号化したEs（G||E(1)）が一つの暗号文として保存されている。同様に、インデックス２が暗号化されたE(2)と平文リファレンス231の一文字目であるCが（C||E(2)）として連結され、これを暗号化したEs（C||E(2)）が、Es（G||E(1)）と同様に保存されている。同様に、他の文字も暗号化され、m個の暗号文から、2次暗号化リファレンス332は構成される。
【００５７】
＜図７と図１３：1次暗号化リファレンスと2次暗号化リファレンスの検索処理＞
図７は、本実施形態において、ネットワーク100を経由し、検索エージェント200が送信した暗号化リードを用い、管理サーバ300が、記憶部320へ登録された1次暗号化リファレンス331と2次暗号化リファレンス332から、暗号化リードに関連する部分的な2次暗号化リファレンスを発見する処理を示すシーケンス図である。
【００５８】
検索エージェント200の全体処理部211は、平文リード233をロードし、リード暗号化部217へ入力する(S801)。
【００５９】
検索エージェント200のリード暗号化部217は、記憶部220に格納された秘密鍵251と公開パラメータ237をロードし、平文リード233を1次暗号化リード213に変換する。なお、変換方法については、S1101からS1108の各処理で詳しく説明する(S802)。
【００６０】
検索エージェント200の通信部203は、リード暗号化部217より出力された1次暗号化リードを、ネットワーク100を経由し、管理サーバ300へ送信する処理を行う(S803)。
【００６１】
管理サーバ300の通信部303から、ネットワーク100を経由し、登録エージェント200が送信した1次暗号化リードを受信する処理を行う(S804)。
【００６２】
管理サーバ300の全体処理部311は、記憶部320へ格納された2次暗号化リファレンス332から、1次暗号化リードに該当する、2次暗号化リファレンス332の部分データを抽出する。この抽出にあたっては、図１０を用い、後で詳しく報告する(S805)。
【００６３】
管理サーバ300は、通信部303から、ネットワーク100を経由し、抽出した2次暗号化リファレンス332の部分データを検索エージェント200へ送信する処理を行う（S806）。
【００６４】
検索エージェント200は、通信部203から、ネットワーク100を経由し、管理サーバ300が送信した2次暗号化リファレンスの部分データを受信する処理を行う(S807)。
【００６５】
検索エージェント200は、記憶部220に格納された秘密鍵251と公開パラメータ237をロードし、リファレンス復号部215を用い、2次暗号化リファレンスの部分データを、平文リファレンスの部分データに復号する(S808)。
【００６６】
検索エージェント200は、平文リファレンスの部分データを用い、リード暗号化部217は、2次暗号化リード213を作成する。なお、2次暗号化リードの作成方法については、図１１を用い、後で詳しく説明する(S809)。
【００６７】
検索エージェント200の通信部203は、リード暗号化部217より出力された2次暗号化リードを、ネットワーク100を経由し、管理サーバ300へ送信する処理を行う(S810)。
【００６８】
管理サーバ300の通信部303から、ネットワーク100を経由し、登録エージェント200が送信した2次暗号化リードを受信する処理を行う(S811)。
【００６９】
管理サーバ300の全体処理部311は、記憶部320へ格納された2次暗号化リファレンス332から、2次暗号化リードに該当する、2次暗号化リファレンス332の部分データを抽出する。この抽出にあたっては、図12を用い、後で詳しく報告する(S812) 
管理サーバ300は、通信部303から、ネットワーク100を経由し、抽出した2次暗号化リファレンスの部分データを検索エージェント200へ送信する処理を行う（S813）。
【００７０】
検索エージェント200は、通信部203から、ネットワーク100を経由し、管理サーバ300が送信した2次暗号化リファレンスの部分データを受信する処理を行う(S814)。
【００７１】
検索エージェント200の全体処理部211は、記憶部220に格納された秘密鍵251と公開パラメータ237をロードし、リファレンス復号部215を用い、2次暗号化リファレンスの部分データを、平文リファレンス231の部分データに復号する(S815)。
【００７２】
検索エージェント200の全体処理部211は、平文リファレンスの部分データと平文リード233のエディット距離が最も近くなるよう、平文リファレンスの部分データを変更する(S816)。
【００７３】
上記の処理(S801からS816)により、検索エージェント200は、ネットワーク100経由で、管理サーバ300の記憶部320へ登録された1次暗号化リファレンス331と2次暗号化リファレンスから、1次暗号化リードと2次暗号化リードに類似した2次暗号化リファレンスの部分データを発見できる。
【００７４】
図13に、検索エージェント200の全体処理部211が出力部に表示した検索結果を例示する。1行目の合致率とは、2次暗号化クエリと2次暗号化リファレンスの検索結果が同じである割合を指す。2行目の得点については、図14を用い、後で詳しく説明する。3行目以降に、類似する2次暗号化クエリと2次暗号化リファレンスを復号した結果を表示している。
【００７５】
なお、上記の処理手順は、固定されたものではなく、処理手順や処理内容を変更して実施してもかまわない。例えば、検索エージェント200は、1次暗号化リードと、2次暗号化リードを作成(S808)後、1次暗号化リードの送信(S804)、2次暗号化リードの送信(S808)を実行してもよい。同様に、他の処理内容を変更してもよい。
【００７６】
＜図８：1次暗号化リファレンスの作成処理＞
図８は、本実施形態の(S602)において、検索エージェント200が、平文リファレンスを1次暗号化リファレンスに変換する処理を示すシーケンス図である。
【００７７】
検索エージェント200の全体処理部211は、リファレンス暗号化部213に、ロードした秘密鍵251と公開パラメータ237と、平文リファレンスを入力する(S901)。
【００７８】
検索エージェント200の全体処理部211は、リファレンスの分割単位を意味するブロック長wを設定する(S902)。（図６(b)の例では、1次暗号化リファレンスのブロック長wは11文字である。）
検索エージェント200の全体処理部211は、インデックスiの値を初期値1に設定(i←1)し、また終了値を設定する(S903)。以降は、図６(b)の例に倣い、終了値は文字数mが設定されるものとする。
【００７９】
検索エージェント200の全体処理部211は、平文リファレンスにおけるi番目の文字からｗ＋(i-1)番目の文字を抜き出し、これをブロックBiとして、リファレンス暗号化部213へ入力する（従って、１ブロックはｗ個の文字列からなる）(S904)。
【００８０】
検索エージェント200のリファレンス暗号化部213は、ブロックBiを暗号化し、暗号文Es(Bi)を作成する(S905)。
【００８１】
検索エージェント200の全体処理部211は、インデックスiを1つインクリメントする(i←i+1)(S906)。
【００８２】
検索エージェント200の全体処理部211は、インデックスiが終了値を超えているかを判定する(i>m?)(S907)。越えていない場合は、S904へ戻る。越えている場合は、S908へ進む。
【００８３】
検索エージェント200の全体処理部211は、S905において、逐次的に作成したEs(B1)からEs(Bm)を、1次暗号化リファレンスとして、記憶部220へ格納する(S908)。
【００８４】
上記の処理(S901からS908)により、検索エージェント200は、平文リファレンスをワード長毎に分割し、これをリファレンス暗号化部により暗号化した、1次暗号化リファレンス331を作成できる。
【００８５】
なお、上記の処理手順は、固定されたものではなく、処理手順や処理内容を変更して実施してもかまわない。例えば、検索エージェント200は、複数のブロックを抜き出し(S904)、それらを暗号化し(S905)、インクリメントする数を増やしてもよい(S906)。同様に、他の処理内容を変更してもよい。
【００８６】
＜図９：2次暗号化リファレンスの作成処理＞
図９は、本実施形態の(S602)において、検索エージェント200が、平文リファレンスを2次暗号化リファレンスに変換する処理を示すシーケンス図である。
【００８７】
検索エージェント200のリファレンス暗号化部213に、全体処理部211によってロードされた秘密鍵251と公開パラメータ237と、平文リファレンスが入力される(S1001)。
【００８８】
検索エージェント200の全体処理部211は、リファレンスの分割単位を意味するブロック長wを設定する(S1002)。（図６(b)の例では、2次暗号化リファレンスのブロック長wは1文字である。）
検索エージェント200の全体処理部211は、インデックスiの値を初期値1に設定(i←1)し、また終了値を設定する(S1003)。以降は、図６(b)の例に倣い、終了値は文字数mが設定されるものとする。
【００８９】
検索エージェント200の全体処理部211は、インデックスiを暗号化し、暗号文E(i)を作成する(S1004)。
【００９０】
検索エージェント200の全体処理部211は、平文リファレンスにおけるi番目の文字からｗ＋(i-1)番目の文字を抜き出し、これをブロックCiとする（従って、１ブロックはｗ個の文字列からなる）(S1005)。
【００９１】
検索エージェント200の全体処理部211は、抽出したブロックCiと暗号化したインデックスE(i)を連結し、それをリファレンス暗号化部213に入力し、暗号文Es(Ci||E(i))を作成する(S1006)。ただし、||はデータの連結を意味する(S1006)。
【００９２】
検索エージェント200の全体処理部211は、インデックスiを1つインクリメントする(i←i+1)(S1007)。
【００９３】
検索エージェント200の全体処理部211は、インデックスiが終了値を超えているかを判定する(i>m?)(S1008)。越えていない場合は、S1005へ戻る。越えている場合は、S1009へ進む。
【００９４】
検索エージェント200の全体処理部211は、S1005において、逐次的に作成したEs(C1||E(1))からEs(Cm||E(m))を、2次暗号化リファレンスとして、記憶部220へ格納する(S1009)。
【００９５】
上記の処理(S1001からS1009)により、検索エージェント200は、平文リファレンスをワード長毎に分割し、インデックスを連結したデータをリファレンス暗号化部により暗号化した、2次暗号化リファレンス332を作成できる。
【００９６】
なお、上記の処理手順は、固定されたものではなく、処理手順や処理内容を変更して実施してもかまわない。例えば、検索エージェント200は、複数のブロックを抜き出し(S1005)、それらを暗号化し(S1006)、インデックスiのインクリメントする数を増やしてもよい(S1006)。同様に、他の処理内容を変更してもよい。
【００９７】
＜図なし：1次暗号化リードの作成処理＞
本実施形態の(S802)において、検索エージェント200が、平文リード233を1次暗号化リードに変換する処理を示す。
【００９８】
検索エージェント200のリード暗号化部217に、全体処理部211によってロードされた秘密鍵251と公開パラメータ237と、平文リード233が入力される(S1101)。
【００９９】
検索エージェント200の全体処理部211は、リファレンスの分割単位を意味するブロック長wを設定する(S1102)。（図６(b)の例では、1次暗号化リードのブロック長wは11文字である。）
検索エージェント200の全体処理部211は、インデックスiの値を初期値1に設定(i←1)し、また終了値を設定する(S1103)。以降は、リードの終了値はnを設定するものとする。
【０１００】
検索エージェント200の全体処理部211は、平文リード233におけるi番目の文字からｗ＋(i-1)番目の文字を抜き出し、これをブロックBiとして、リード暗号化部217へ入力する（従って、１ブロックはｗ個の文字列からなる）(S1104)。
【０１０１】
検索エージェント200のリード暗号化部217は、ブロックBiを暗号化し、暗号文E(Bi)を作成する(S1105)。
【０１０２】
検索エージェント200の全体処理部211は、インデックスiを1つインクリメントする(i←i+1)(S1106)。
【０１０３】
検索エージェント200の全体処理部211は、インデックスiが終了値を超えているかを判定する(i>n?)(S1107)。越えていない場合は、S1104へ戻る。越えている場合は、S1108へ進む。
【０１０４】
検索エージェント200の全体処理部211は、S1105において、逐次的に作成したE(B1)からE(Bn)を、1次暗号化リードとして、記憶部220へ格納する(S1108)。
【０１０５】
上記の処理(S901からS908)により、検索エージェント200は、平文リードをリード暗号化部により暗号化した、1次暗号化リードを作成できる。
【０１０６】
なお、上記の処理手順は、固定されたものではなく、処理手順や処理内容を変更して実施してもかまわない。例えば、検索エージェント200は、複数のブロックを抜き出し(S1105)、それらを暗号化し(S1106)、インクリメントする数を増やしてもよい(S1107)。同様に、他の処理内容を変更してもよい。
【０１０７】
＜図１０：2次暗号化リファレンスの抽出処理＞ 
図１０は、本実施形態の(S805)において、管理サーバ300が、2次暗号化リファレンス332を抽出する処理を示すシーケンス図である。  
【０１０８】
管理サーバ300の検査部312に、全体処理部311によってロードされた公開パラメータ337が入力される(S1201)。
【０１０９】
管理サーバ300の全体処理部311は、ブロック長wを設定する(S1202)。（図６(b)の例に倣い、1次暗号化リファレンス331のブロック長wは11とする。）
管理サーバ300の全体処理部311は、インデックスiの値を初期値に設定し、また終了値を設定する(S1203)。以降では、S908に倣い、一次暗号化リードとしてE(B1)からE(Bn)を受信したものとし、初期値を１(i←1)、終了値をnに設定するものとする。
【０１１０】
管理サーバ300の全体処理部311は、1次暗号化リードから暗号文E(Bi)を抽出する(S1204)。
【０１１１】
管理サーバ300の全体処理部311は、インデックスｊの値を初期値に設定し、また終了値を設定する(S1205)。以降では、図６(ｂ)に倣い、1次暗号化リファレンス331としてEs(B1)からEs(B(m-w+1))を記憶しているものとし、初期値を１(i←1)、終了値を(m-w+1)に設定するものとする。
【０１１２】
管理サーバ300の全体処理部311は、1次暗号化リファレンス331から暗号文Es(Bi)を抽出する(S1206)。
【０１１３】
管理サーバ300の全体処理部311は、S1204で抽出した暗号文E(Bi)と、S1206で抽出した暗号文Es(Bi)を検査部へ入力する。検査部312は、暗号文E(Bi)と暗号文Es(Bi)が暗号化前は同じ平文値を有するかを判定し、等しい場合は1を、等しくない場合は0を返す(S1207)。検索部が１を出力した場合はS1208へ進み、0を出力した場合はS1209へ進む。
【０１１４】
管理サーバ300の全体処理部311は、暗号文Es(Bi)と同じインデックスiを有する2次暗号化リファレンスEs(Ci)と、Es(Ci+1)、Es(Ci+2)、・・・、Es(Ci+w-1)を抽出し、記憶部220に格納する(S1208)。ただし、既に同じ暗号文が抽出されている場合は、その暗号文は抽出しない。
【０１１５】
管理サーバ300の全体処理部311は、インデックスjを1つインクリメントする(j←j+1)(S1209)。
【０１１６】
管理サーバ300の全体処理部311は、インデックスjが終了値を超えているかを判定する(ｊ>m-w+1?)(S1210)。越えていない場合は、S1206へ戻る。越えている場合は、S1211へ進む。
【０１１７】
管理サーバ300の全体処理部311は、インデックスiを1つインクリメントする(i←i+1)(S1211)。
【０１１８】
管理サーバ300の全体処理部311は、インデックスiが終了値を超えているかを判定する(i>n?)(S1212)。越えていない場合は、S1205へ戻る。越えている場合は、S1212へ進む。
なお、上記の処理手順は、固定されたものではなく、処理手順や処理内容を変更して実施してもかまわない。例えば、検索エージェント200は、複数のブロックを抜き出し(S1206)、それらを検索し(S1207)、インデックスjの更新する数を増やしてもよい(S1209)。同様に、他の処理内容を変更してもよい。
【０１１９】
＜図１０：2次暗号化リードの作成処理＞ 
図１０は、本実施形態の(S808)と(S809)において、検索エージェント200が、平文リード233を2次暗号化リードに変換する処理を示すシーケンス図である。  
【０１２０】
検索エージェント200は、通信部203を介し、2次暗号化リファレンスを受信する処理を行う(S1301)。
【０１２１】
検索エージェント200の全体処理部211は、リファレンス復号部215とリード暗号化部217に、ロードした秘密鍵251と公開パラメータ237と、2次暗号化リファレンスを入力する(S1302)。
【０１２２】
検索エージェント200の全体処理部211は、リファレンスの分割単位を意味するブロック長wを設定する(S1303)。以降では、2次暗号化リファレンスのブロック長wは1文字とする。
【０１２３】
検索エージェント200の全体処理部211は、インデックスiの値を初期値1に設定(i←1)し、また終了値を設定する(S1304)。以降は、図６(b)の例に倣い、終了値は文字数nが設定されるものとする。
【０１２４】
検索エージェント200の全体処理部211は、2次暗号化リファレンスにおけるi番目の文字を抜き出し、これをブロックE(Ci||E(i))とみなして、リファレンス復号部215へ入力する(S1305)。
【０１２５】
検索エージェント200の全体処理部211は、リファレンス復号部215が出力したCi||E(i)からE(i)を抽出し、再びリファレンス復号部215に入力する(S1306)。
【０１２６】
検索エージェント200の全体処理部211は、リファレンス復号部215が出力したiを取得する(S1307)。
【０１２７】
検索エージェント200の全体処理部211は、インデックスiを1つインクリメントする(i←i+1)(S1308)。
【０１２８】
検索エージェント200の全体処理部211は、インデックスiが終了値を超えているかを判定する(i>m?)(S1309)。越えていない場合は、S1305へ戻る。越えている場合は、S1310へ進む。
【０１２９】
上記S1301からS1309の処理により、2次暗号化リファレンスに埋め込まれていたインデックスi、i+1、…、i+n-1を取得した。
【０１３０】
検索エージェント200の全体処理部211は、ターゲットレンジ長ｖを設定する(S1310)。
【０１３１】
検索エージェント200の全体処理部211は、インデックスｊの値を初期値i-Vに設定し、また終了値としてi-1を設定する(S1311)。ただし、初期値であるi-Vが0以下(i-V<=0)である場合は、初期値を1とする。また、終了値であるi-1が0以下(i-1<=0)である場合は、S1311からS1315の処理を飛ばし、S1316へと進む。
【０１３２】
検索エージェント200のリード暗号化部217は、インデックスｊを暗号化し、暗号文E(ｊ)を作成する(S1312)。
【０１３３】
検索エージェント200の全体処理部211は、抽出したブロックCjと暗号化したインデックスE(j)を連結し、それを暗号化し、暗号文E(Ci||E(i))を作成する(S1313)。ただし、||はデータの連結を意味する。
【０１３４】
検索エージェント200の全体処理部211は、インデックスjを1つインクリメントする(j←j+1)(S1314)。
【０１３５】
検索エージェント200の全体処理部211は、インデックスiが終了値を超えているかを判定する(j>i-1?)(S1315)。越えていない場合は、S1312へ戻る。越えている場合は、S1316へ進む。
【０１３６】
検索エージェント200の全体処理部211は、ターゲットレンジ長ｖを再設定する(S1316)。
【０１３７】
検索エージェント200の全体処理部211は、インデックスｊの値を初期値i+nに設定し、また終了値としてi+n+v-1を設定する(S1317)。ただし、初期値であるi+nがm以上(i-V<0)である場合は、S1317からS1311の処理を飛ばし、S1312へと進む。また、終了値であるi+n+v-1がm以上(i-1<0)である場合は、終了値もmとする(S1317)。
【０１３８】
検索エージェント200のリード暗号化部217は、インデックスｊを暗号化し、暗号文E(ｊ)を作成する(S1318)。
【０１３９】
検索エージェント200の全体処理部211は、抽出したブロックCjと暗号化したインデックスE(j)を連結し、それを暗号化し、暗号文E(Ci||E(i))を作成する(S1319)。ただし、||はデータの連結を意味する。
【０１４０】
検索エージェント200の全体処理部211は、インデックスjを1つインクリメントする(j←j+1)(S1320)。
【０１４１】
検索エージェント200の全体処理部211は、インデックスiが終了値を超えているかを判定する(j>i-1?)(S1321)。越えていない場合は、S1318へ戻る。越えている場合は、S1322へ進む。
【０１４２】
検索エージェント200の全体処理部211は、S1313とS1319において、逐次的に作成した暗号文を、2次暗号化リードとして、記憶部220へ格納する(S1322)。
【０１４３】
上記のS1310からS1322の処理により、S1301からS1309の処理で抽出したインデックスi、i+1、・・・、i+n-1に対応する2次暗号化リードを作成できた。
なお、上記の処理手順は、固定されたものではなく、処理手順や処理内容を変更して実施してもかまわない。
【０１４４】
＜図１２：2次暗号化リファレンスの検索処理＞
図１２は、本実施形態の(S812)において、管理サーバ300が、2次暗号化リファレンス332を抽出する処理を示すシーケンス図である。
【０１４５】
管理サーバ300の全体処理部311は、合計点S、得点A、減点B、最大値M、しきい値T、インデックスL、インデックスR、ブール値ｂの初期値を設定する。例えば、S、A、B、M、T、L、R、ｂの初期値はそれぞれ0、５、４、0、-50、0、0、0とする(S1401)。以降では、ブール値ｂは2次暗号化リードの調査順序の設定（降順または昇順）に用いる。
【０１４６】
管理サーバ300の検査部312に、全体処理部311によってロードされた公開パラメータ237が入力される(S1402)。
【０１４７】
管理サーバ300の全体処理部311は、ブロック長wを設定する(S1403)。（図６(b)の例に倣い、2次暗号化リファレンス332のブロック長wは1とする。）
管理サーバ300の全体処理部311は、インデックスkの値を初期値に設定し、また終了値を設定する(S1404)。以降では、ｖ個の2次暗号化リードE(C(i-v))からE(C(i-1))を受信したものとし、インデックスkの初期値をi、終了値をi-v+1に設定するものとする。
【０１４８】
管理サーバ300の全体処理部311は、2次暗号化リードから暗号文E(Ck)を抽出する(S1405)。
【０１４９】
管理サーバ300の全体処理部311は、2次暗号化リファレンス332から暗号文Es(Ck)を抽出する(S1406)。
【０１５０】
管理サーバ300の全体処理部311は、S1404で抽出した暗号文E(Ck)と、S1406で抽出した暗号文Es(Ck)を検査部へ入力する。検査部312は、暗号文E(Ck)と暗号文Es(Ck)が暗号化前は同じ平文値を有するかを判定し、等しい場合は1を、等しくない場合は0を返す(S1407)。
【０１５１】
管理サーバ300の全体処理部311は、S1404で抽出した暗号文E(Ck)と、S1406で抽出した暗号文Es(Ck)を検査部へ入力する。検査部312は、暗号文E(Ck)と暗号文Es(Ck)が暗号化前は同じ平文値を有するかを判定し、等しい場合は1を、等しくない場合は0を返す(S1407)。
【０１５２】
管理サーバ300の全体処理部311は、得点Sと最大値を更新する(S1408)。S1407で検査部312が1を出力した場合は、Sを得点A分だけ加え（S←S＋A）、検査部312が0を出力した場合は、Sを減点B分だけ減らす（S←S―B）。
【０１５３】
管理サーバ300の全体処理部311は、得点Sとしきい値Tを比較し、得点Sがしきい値以下である(S <= T)場合は、S1414へ進み、そうでなければS1410へと進む。
【０１５４】
管理サーバ300の全体処理部311は、最大値Mが得点Sより低い場合、その差分(S-M)だけ、しきい値Tを増やす(T←T＋S-M)(S1410)。
【０１５５】
管理サーバ300の全体処理部311は、最大値Mが得点Sより低い(M<S)場合、得点Sの値を最大値Mの値にコピーする（M←S）。また、最大値を更新し、かつブール値ｂが0であった場合は、インデックスLにｋの値をコピーする（L←ｋif (b==0 && M<S)）。最大値を更新し、かつブール値ｂが1であった場合は、インデックスRにｋの値をコピーする（R←ｋif (b==1 && M<S)）。(S1411)
管理サーバ300の全体処理部311は、ブール値ｂが0である場合は、インデックスkを1つインクリメントし(k←k-1)、ブール値ｂが1である場合は、インデックスkを1つインクリメントし(k←k+1)、(S1412)。
【０１５６】
管理サーバ300の全体処理部311は、インデックスkが終了値を超えているかを判定する(k>i+v-1?)(S1413)。越えていない場合は、S1405へ戻る。越えている場合は、S1413へ進む。
【０１５７】
管理サーバ300の全体処理部311は、インデックスkがi+nを超えているかを判定する(k>i+n?)(S1414)。越えていない場合は、S1414へ進む。越えている場合は、S1415へ進む。
【０１５８】
管理サーバ300の全体処理部311は、インデックスkの値を初期値に設定し、また終了値を設定する(S1415)。以降では、2次暗号化リードとしてE(C(i+n))からE(C(i+n+v-1))を受信したものとし、インデックスkの初期値をi+n、終了値をi+n+v-1に設定するものとする。
【０１５９】
管理サーバ300の全体処理部311は、S1404で設定した初期値(i-1)からインデックスLまでの2次暗号化リファレンスにおける暗号文E(C(L))、・・・, E(C(i-1))を抽出する。ただし、インデックスLが0である場合は、この処理を省く。また同様に、S1415で設定した初期値(i+n)からインデックスRまでの2次暗号化リファレンスにおける暗号文E(C(i+n))、・・・, E(C(R))を抽出する。ただし、インデックスRが0である場合は、この処理を省く(S1416)。
【０１６０】
上記の処理により、一文字毎の暗号化データの完全一致検索を用い、暗号化リファレンスと暗号化リードの類似検索が実施できた。
なお、上記の処理手順は、固定されたものではなく、処理手順や処理内容を変更して実施してもかまわない。
【符号の説明】
【０１６１】
１００：ネットワーク、２００：検索エージェント、３００：管理サーバ、   
５００：コンピュータ、２０１、３０１：入力部、２０２、３０２：出力部、２０３、３０３：通信部、２１０、３１０：制御部、２１１、３１１：全体処理部、２１２：鍵生成部、２１３：リファレンス暗号化部、２１５：リファレンス復号部、２１７：リード暗号化部、３１２：検査部、２２０、３２０：記憶部、２３０、３３０：データ記憶部、２３１：平文リファレンス、２３３：平文リード、２３７、３３７：公開パラメータ、３３１：1次暗号化リファレンス、３３２：2次暗号化リファレンス、２５１：秘密鍵、２６０、３６０：プログラム記憶部、２８０、３８０：一時情報記憶部、５０１：ＣＰＵ(Central Processing Unit)、５０２：メモリ、５０３：外部記憶装置、５０８：記憶媒体、５０７：読書装置、５０６：入力装置、５０５：出力装置、５０４：通信装置、５０９：内部通信線
【図１】
0005948060.tif 000002
【図２】
0005948060.tif 000003
【図３】
0005948060.tif 000004
【図４】
0005948060.tif 000005
【図５】
0005948060.tif 000006
【図６（ａ）】
0005948060.tif 000007
【図６（ｂ）】
0005948060.tif 000008
【図７】
0005948060.tif 000009
【図８】
0005948060.tif 000010
【図９】
0005948060.tif 000011
【図１０】
0005948060.tif 000012
【図１１】
0005948060.tif 000013
【図１２】
0005948060.tif 000014
【図１３】
0005948060.tif 000015