(57)【特許請求の範囲】
【請求項１】
平文を秘匿化した秘匿文を生成する秘匿化装置であって、
前記平文を秘匿鍵により秘匿化した前記秘匿文を生成する秘匿化部と、
前記平文を検索するためのキーワードに対応付けられる対応情報を生成する対応情報生成部と、
前記キーワードと前記対応情報とに基づきタグを生成するタグ生成部と、
前記秘匿文および前記タグの組を出力する秘匿情報出力部と、
を備える秘匿化装置。
【請求項２】
前記対応情報生成部は、キーワード毎に異なる乱数を前記対応情報として生成する
請求項１に記載の秘匿化装置。
【請求項３】
前記キーワードおよび前記対応情報の組を出力するキーワード出力部をさらに備え、
前記キーワード出力部は、権限を有する特定の利用者がアクセス可能な内部記憶部に、前記キーワードおよび前記対応情報の組を記憶させる、
請求項１または２に記載の秘匿化装置。
【請求項４】
前記平文を識別する識別情報を生成する識別情報生成部と、
前記識別情報に基づき前記秘匿鍵を生成する秘匿鍵生成部と、
をさらに備え
前記秘匿情報出力部は、前記秘匿文、前記識別情報および前記タグの組を出力する
請求項１から３の何れか１項に記載の秘匿化装置。
【請求項５】
前記秘匿鍵生成部は、マスター鍵と前記識別情報とに基づき、前記秘匿鍵を生成する
請求項４に記載の秘匿化装置。
【請求項６】
前記タグ生成部は、タグ鍵と前記キーワードと前記対応情報とを予め定められた関数に入力して、前記タグを生成する
請求項１から５の何れか１項に記載の秘匿化装置。
【請求項７】
前記秘匿化部は、前記平文を前記秘匿鍵により暗号化して前記秘匿文を生成する
請求項１から６の何れか１項に記載の秘匿化装置。
【請求項８】
前記秘匿化部は、前記平文を前記秘匿鍵により秘密分散して複数のシェアを含む前記秘匿文を生成する
請求項１から６の何れか１項に記載の秘匿化装置。
【請求項９】
前記対応情報生成部は、１つの前記キーワードに対して複数の前記対応情報を生成し、
前記タグ生成部は、１つの前記キーワードに対する複数の前記対応情報に基づき、１つの前記キーワードに対して複数の前記タグを生成する
請求項１から８の何れか１項に記載の秘匿化装置。
【請求項１０】
前記タグ生成部は、それぞれが１つの前記キーワードに対応付けられる前記タグを生成する
請求項９に記載の秘匿化装置。
【請求項１１】
前記タグ生成部は、それぞれが複数の前記キーワードに対応付けられる可能性を有する前記タグを生成する
請求項９に記載の秘匿化装置。
【請求項１２】
乱数から前記マスター鍵を生成するマスター鍵生成部をさらに備え、
前記秘匿鍵生成部は、前記識別情報に対応する前記秘匿鍵を、前記マスター鍵から予め定められた鍵規則に基づいて生成し、
それぞれの前記秘匿鍵は、前記識別情報毎に異なり、一部が他の前記秘匿鍵と相関を有する
請求項５に記載の秘匿化装置。
【請求項１３】
前記秘匿化部は、ｎ（ｎは２以上の整数）個の前記平文をｎ個の前記秘匿鍵により暗号化してｎ個の前記秘匿文を生成し、
ｎ個の前記秘匿鍵は、全て同一のビット長であり、
前記平文のビット長と前記秘匿鍵のビット長は、｜ｍ｜で同一であり、
前記マスター鍵生成部は、
０以上１以下の値であり、攻撃者がｎ個の前記秘匿文とｙ（ｙは０以上ｎ−１以下の整数のそれぞれ）個の前記秘匿鍵を知ったそれぞれの場合における、１個の前記平文に対するユーザが設定する安全性を表すｎ個の導出パラメータρ１，ｙを入力し、
それぞれのｘ（ｘは０以上ｎ以下の整数）について、差分ｄ（ｘ）＝ρ１，ｘ−１−ρ１，ｘを算出し（ただし、ρ１，−１＝１，ρ１，ｎ＝０）、
それぞれのｘについて、下記の式に表される多項式の係数ａｔ，ｘを取得し、取得した係数ａｔ，ｘを第１鍵規則に従って組み合わせた系列を前記マスター鍵として出力する
【数１】
0006441160.tif 000005
請求項１２に記載の秘匿化装置。
【請求項１４】
前記秘匿鍵生成部は、
前記マスター鍵から式（１）に表される多項式の係数ａｔ，ｘを前記第１鍵規則に従って抽出し、
抽出した係数ａｔ，ｘのうち識別情報ｉにより特定される複数の係数ａｔ，ｘを複数の部分系列として取得し、
取得した複数の部分系列を第２鍵規則に従って組み合わせた系列を前記秘匿鍵として出力する
請求項１３に記載の秘匿化装置。
【請求項１５】
秘匿鍵により平文を秘匿化した秘匿文から、前記平文を復号する復号装置であって、
前記平文を検索するためのキーワードを入力するキーワード入力部と、
前記キーワードおよび対応情報の組を複数個記憶した内部記憶部から、入力した前記キーワードに対応する前記対応情報を取得する対応情報取得部と、
入力した前記キーワードと、入力した前記キーワードと対応付けられる前記対応情報とに基づきタグを生成するタグ生成部と、
前記秘匿文および前記タグの組を複数個記憶した外部記憶部から、生成した前記タグに対応する前記秘匿文を取得する秘匿情報取得部と、
前記秘匿鍵により前記秘匿文から前記平文を復号する復号部と、
を備える復号装置。
【請求項１６】
前記外部記憶部から、生成した前記タグを含む、前記秘匿文および前記タグの組を検索する検索部
をさらに備える請求項１５に記載の復号装置。
【請求項１７】
前記秘匿鍵は、前記平文を識別する識別情報に基づき生成され、
前記秘匿情報取得部は、前記秘匿文、前記識別情報および前記タグの組を複数個記憶した前記外部記憶部から、生成した前記タグに対応する前記秘匿文および前記識別情報を取得し、
当該復号装置は、取得した前記識別情報に基づき前記秘匿鍵を生成する秘匿鍵生成部をさらに備える
請求項１５または１６に記載の復号装置。
【請求項１８】
生成した前記タグに対応する前記識別情報の数に基づく統計情報を算出し、前記キーワードに対応する前記統計情報を出力する統計部
をさらに備える請求項１７に記載の復号装置。
【請求項１９】
論理式入力部をさらに備え、
前記キーワード入力部は、１または複数の前記キーワードを入力し、
前記論理式入力部は、入力した１または複数の前記キーワードを入力値とした論理式を入力し、
前記タグ生成部は、入力した複数の前記キーワードのそれぞれについて前記タグを生成し、
前記秘匿情報取得部は、前記外部記憶部から、複数の前記キーワードのそれぞれについて取得した複数の前記秘匿文および前記識別情報の組の集合を入力値として、前記論理式を演算し、演算結果として得られた前記秘匿文および前記識別情報の組の集合を取得する
請求項１７または１８に記載の復号装置。
【請求項２０】
平文を秘匿化した秘匿文を生成する秘匿化方法であって、
前記平文を秘匿鍵により秘匿化した前記秘匿文を生成し、
前記平文を検索するためのキーワードに対応付けられる対応情報を生成し、
前記キーワードと前記対応情報とに基づきタグを生成し、
前記秘匿文および前記タグの組を出力する
秘匿化方法。
【請求項２１】
秘匿鍵により平文を秘匿化した秘匿文から、前記平文を復号する復号方法であって、
前記平文を検索するためのキーワードを入力し、
前記キーワードおよび対応情報の組を複数個記憶した内部記憶部から、入力した前記キーワードに対応する前記対応情報を取得し、
入力した前記キーワードと、入力した前記キーワードと対応付けられる前記対応情報とに基づきタグを生成し、
前記秘匿文および前記タグの組を複数個記憶した外部記憶部から、生成した前記タグに対応する前記秘匿文を取得し、
秘匿鍵により前記秘匿文から前記平文を復号する
復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、秘匿化装置、復号装置、秘匿化方法および復号方法に関する。
【背景技術】
【０００２】
暗号化された情報群の中から目的の情報を検索する方法として、それぞれの暗号化情報に検索用の付加情報（タグ）を付ける方法が知られている。この方法では、検索時において、キーワードからタグを生成し、生成したタグと一致したタグが付けられた暗号化情報を取得すれば、暗号化情報を復号せずに目的の情報を取得することができる。
【０００３】
しかし、頻繁に検索をした場合、タグから平文の内容が推定されたり、平文の検索頻度等が漏えいしたりし、安全性が低下する可能性がある。従って、このような方法において安全性を向上するには、暗号鍵のサイズおよびタグのサイズを大きくしなければならない。しかし、暗号鍵のサイズおよびタグのサイズを大きくすると、検索者が検索のために保持すべき情報量が大きくなってしまう。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１２−７３６９３号公報
【特許文献２】特開２０１４−１９２６１２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明が解決しようとする課題は、検索のために保有しなければならない情報を小さくしつつ、秘匿文およびタグの安全性を向上することにある。
【課題を解決するための手段】
【０００６】
実施形態の秘匿化装置は、平文を秘匿化した秘匿文を生成する。前記秘匿化装置は、秘匿化部と、対応情報生成部と、タグ生成部と、秘匿情報出力部とを備える。前記秘匿化部は、前記平文を秘匿鍵により秘匿化した前記秘匿文を生成する。前記対応情報生成部は、前記平文を検索するためのキーワードに対応付けられる対応情報を生成する。前記タグ生成部は、前記キーワードと前記対応情報とに基づきタグを生成する。前記秘匿情報出力部は、前記秘匿文および前記タグの組を出力する。
【図面の簡単な説明】
【０００７】
【図１】第１実施形態に係る検索システムの構成を示す図。
【図２】秘匿化装置の構成を示す図。
【図３】復号装置の構成を示す図。
【図４】秘匿化時の処理手順を示すフローチャート。
【図５】キーワードと対応情報との対応関係の第１例を示す図。
【図６】キーワードと対応情報との対応関係の第２例を示す図。
【図７】復号時の処理手順を示すフローチャート。
【図８】キーワードとタグとの対応関係の第１例を示す図。
【図９】キーワードとタグとの対応関係の第２例を示す図。
【図１０】マスター鍵と秘匿鍵との関係を示す図。
【図１１】マスター鍵生成部の構成の一例を示す図。
【図１２】乱数からマスター鍵を生成する処理を示す図。
【図１３】第１の秘匿鍵生成部の構成の一例を示す図。
【図１４】マスター鍵から秘匿鍵を生成する処理を示す図。
【図１５】第２実施形態に係る検索システムの構成を示す図。
【図１６】第３実施形態に係る検索システム構成を示す図。
【図１７】第４実施形態に係る復号装置の構成を示す図。
【図１８】実施形態に係るコンピュータのハードウェア構成図。
【発明を実施するための形態】
【０００８】
以下、図面を参照しながら実施形態について詳細に説明する。本実施形態に係る検索システムは、検索のために保有しなければならない情報を小さくしつつ、秘匿文およびタグの安全性を向上することを目的とする。
【０００９】
（第１実施形態）
図１は、第１実施形態に係る検索システム１０の構成を示す図である。検索システム１０は、情報処理部２０と、記憶部３０とを備える。
【００１０】
情報処理部２０は、秘匿化装置２１と、復号装置２２と、マスター鍵生成部２３と、タグ鍵生成部２４と、内部記憶部２５とを有する。また、記憶部３０は、外部記憶部３１と、検索部３２とを有する。
【００１１】
秘匿化装置２１、復号装置２２、マスター鍵生成部２３、タグ鍵生成部２４および内部記憶部２５は、権限を有する特定の利用者がアクセス可能な内部ネットワーク上に接続されている。すなわち、秘匿化装置２１、復号装置２２、マスター鍵生成部２３、タグ鍵生成部２４および内部記憶部２５は、権限を有する特定の利用者がアクセス可能であるが、特定の利用者以外がアクセスできない。秘匿化装置２１、復号装置２２、マスター鍵生成部２３、タグ鍵生成部２４および内部記憶部２５は、１つのコンピュータにより実現されてもよいし、異なる複数のコンピュータにより実現されてもよい。
【００１２】
外部記憶部３１および検索部３２は、特定の利用者以外がアクセス可能な外部ネットワーク上に接続されている。すなわち、外部記憶部３１および検索部３２は、内部記憶部２５等をアクセス可能な特定の利用者以外がアクセスすることが可能である。記憶部３０は、例えば、コンピュータ、インターネット上のサーバまたはクラウドサービスシステム等により実現されてもよい。
【００１３】
秘匿化装置２１は、平文と、平文を検索するために用いる少なくとも１つのキーワードとを入力する。秘匿化装置２１は、入力した平文を秘匿鍵により秘匿化した秘匿文、および、入力した平文を識別する識別情報を生成する。また、秘匿化装置２１は、入力したそれぞれのキーワードに対応する対応情報を生成する。さらに、秘匿化装置２１は、入力したそれぞれのキーワード毎に、キーワードおよび対応する対応情報に基づきタグ（付加情報）を生成する。
【００１４】
そして、秘匿化装置２１は、生成した秘匿文、識別情報および少なくとも１つのタグの組を外部記憶部３１に出力する。外部記憶部３１は、秘匿文、識別情報および少なくとも１つのタグの組を秘匿化装置２１から入力して記憶する。外部記憶部３１は、秘匿文、識別情報および少なくとも１つのタグの組を複数個記憶する。
【００１５】
また、秘匿化装置２１は、それぞれのキーワードと対応する対応情報との組を内部記憶部２５に出力する。内部記憶部２５は、それぞれのキーワードと対応する対応情報との組を秘匿化装置２１から入力して記憶する。内部記憶部２５は、キーワードおよび対応情報の組を複数記憶する。
【００１６】
復号装置２２は、平文を検索するためのキーワードを入力する。復号装置２２は、入力したキーワードに対応して記憶された対応情報を内部記憶部２５から取得する。復号装置２２は、入力したキーワードおよび取得した対応情報に基づきタグを生成する。そして、復号装置２２は、生成したタグを検索部３２に出力する。検索部３２は、復号装置２２からタグを入力すると、外部記憶部３１にアクセスして、入力したタグを含む、秘匿文、識別情報およびタグの組の集合を検索する。検索部３２は、外部記憶部３１から、入力したタグを含む、秘匿文、識別情報およびタグの組の集合が抽出された場合、抽出した秘匿文および識別情報の組の集合を復号装置２２に出力する。
【００１７】
復号装置２２は、検索部３２から秘匿文および識別情報の組の集合を入力する。復号装置２２は、対応する秘匿鍵によりそれぞれの組に含まれる秘匿文から平文を復号する。そして、復号装置２２は、復号した平文の集合を出力する。
【００１８】
マスター鍵生成部２３は、例えば乱数に基づき、秘匿化装置２１に入力される複数の平文に対して共通なマスター鍵を生成する。マスター鍵生成部２３は、生成したマスター鍵を内部記憶部２５に記憶させる。内部記憶部２５に記憶されたマスター鍵は、秘匿鍵を生成するために用いられる。
【００１９】
タグ鍵生成部２４は、例えば乱数に基づき、秘匿化装置２１に入力される複数の平文に対して共通なタグ鍵を生成する。タグ鍵生成部２４は、生成したタグ鍵を内部記憶部２５に記憶させる。内部記憶部２５に記憶されたタグ鍵は、タグを生成するために用いられる。
【００２０】
図２は、秘匿化装置２１の構成を示す図である。秘匿化装置２１は、平文入力部４１と、第１のキーワード入力部４２と、第１のマスター鍵入力部４３と、識別情報生成部４４と、第１の秘匿鍵生成部４５と、秘匿化部４６と、第１のタグ鍵入力部４７と、対応情報生成部４８と、第１のタグ生成部４９と、秘匿情報出力部５０と、キーワード出力部５１とを備える。
【００２１】
平文入力部４１は、秘匿化対象の平文を入力する。第１のキーワード入力部４２は、秘匿化対象の平文を検索するために用いるキーワードを入力する。第１のキーワード入力部４２は、複数のキーワードを入力してもよい。
【００２２】
第１のマスター鍵入力部４３は、内部記憶部２５に記憶されたマスター鍵を入力する。識別情報生成部４４は、秘匿化対象の平文を入力する毎に、入力した平文を識別する識別情報を生成する。識別情報は、平文毎に固有の値である。
【００２３】
第１の秘匿鍵生成部４５は、第１のマスター鍵入力部４３が入力したマスター鍵、および、識別情報生成部４４が生成した識別情報を受け取る。そして、第１の秘匿鍵生成部４５は、マスター鍵と識別情報とに基づき、秘匿鍵を生成する。例えば、第１の秘匿鍵生成部４５は、下記の式（１）に示すように、マスター鍵と識別情報とを予め定められた鍵生成関数ＫｅｙＧｅｎ（）に入力して秘匿鍵を生成する。なお、式（１）において、Ｋｓはマスター鍵、ｉは識別情報、Ｋｉは識別情報ｉに対応する秘匿鍵を表す。
ＫｅｙＧｅｎ（Ｋｓ，ｉ）→Ｋｉ…（１）
【００２４】
秘匿化部４６は、平文入力部４１が入力した平文、および、第１の秘匿鍵生成部４５が生成した秘匿鍵を受け取る。そして、秘匿化部４６は、平文を秘匿鍵により秘匿化した秘匿文を生成する。秘匿化部４６は、一例として、平文を秘匿鍵により暗号化して秘匿文を生成する。また、秘匿化部４６は、一例として、平文を秘匿鍵により秘密分散して複数のシェアを含む秘匿文を生成する。
【００２５】
第１のタグ鍵入力部４７は、内部記憶部２５に記憶されたタグ鍵を入力する。対応情報生成部４８は、第１のキーワード入力部４２がキーワードを入力する毎に、入力したキーワードに対応付けられる対応情報を生成する。第１のキーワード入力部４２が複数のキーワードを入力した場合には、対応情報生成部４８は、それぞれのキーワード毎に対応情報を生成する。なお、対応情報は、それぞれのキーワードを識別する値である。ただし、同一の対応情報が複数のキーワードに対応付けられる場合があってもよい。
【００２６】
対応情報生成部４８は、一例として、キーワードが入力される毎に乱数を発生または入力して、発生または入力した乱数を対応情報とする。対応情報生成部４８は、キーワードが入力される毎に対応情報を生成し、同一のキーワードが入力された場合であっても異なる対応情報を生成してよい。また、対応情報生成部４８は、一例として、同一のキーワードが複数回入力される場合、最初のキーワードの入力時において乱数を対応情報として発生し、以後、同一のキーワードが入力される毎に最初に発生した乱数の値を所定値（例えば１）ずつインクリメントした値を対応情報として発生してもよい。
【００２７】
第１のタグ生成部４９は、第１のタグ鍵入力部４７が入力したタグ鍵、第１のキーワード入力部４２が入力したキーワード、および、対応情報生成部４８が生成した対応情報を受け取る。そして、第１のタグ生成部４９は、タグ鍵とキーワードと対応情報とに基づきタグを生成する。第１のタグ生成部４９は、複数のキーワードを入力した場合には、複数のキーワードのそれぞれについて、タグ鍵とキーワードと対応する対応情報に基づきタグを生成する。
【００２８】
例えば、第１のタグ生成部４９は、下記の式（２）に示すように、タグ鍵とキーワードと対応情報とを予め定められたタグ生成関数ＴａｇＧｅｎ（）に入力して、タグを生成する。なお、式（２）において、ｔｋはタグ鍵、ｗｊはキーワード、ｒは対応情報を表す。また、ｔｊ，ｒは、生成されたタグを表す。
ＴａｇＧｅｎ（ｔｋ，ｗｊ，ｒ）→ｔｊ，ｒ…（２）
【００２９】
秘匿情報出力部５０は、秘匿化部４６が生成した秘匿文、識別情報生成部４４が生成した識別情報、および、第１のタグ生成部４９が生成したタグを受け取る。そして、秘匿情報出力部５０は、秘匿文、識別情報およびタグの組を外部記憶部３１に出力して記憶させる。なお、秘匿情報出力部５０は、第１のタグ生成部４９から複数のタグを受け取った場合には、秘匿文、識別情報および複数のタグの組を外部記憶部３１に出力して記憶させる。
【００３０】
キーワード出力部５１は、第１のキーワード入力部４２が入力したキーワード、および、対応情報生成部４８が生成した対応情報を受け取る。そして、キーワード出力部５１は、キーワードおよび対応情報の組を内部記憶部２５に出力して記憶させる。なお、キーワード出力部５１は、第１のキーワード入力部４２から複数のキーワードを受け取った場合には、複数のキーワード毎に、キーワードおよび対応する対応情報の組を内部記憶部２５に出力して記憶させる。
【００３１】
なお、秘匿化部４６が、秘密分散をして複数個（例えばｑ個）のシェアを含む秘匿文を生成する場合、記憶部３０は、異なる複数個（例えばｑ個）の外部記憶部３１を有する。ｑ個の外部記憶部３１は、例えば、ネットワーク上における異なるサーバ等である。シェア秘匿情報出力部５０は、ｑ個のシェアのそれぞれを、対応するタグおよび識別情報と組にして、異なるｑ個の外部記憶部３１に分散して記憶させる。
【００３２】
図３は、復号装置２２の構成を示す図である。復号装置２２は、第２のキーワード入力部６１と、対応情報取得部６２と、第２のタグ鍵入力部６３と、第２のタグ生成部６４と、秘匿情報取得部６５と、第２のマスター鍵入力部６６と、第２の秘匿鍵生成部６７と、復号部６８と、平文出力部６９とを備える。
【００３３】
第２のキーワード入力部６１は、平文を検索するためのキーワードを入力する。対応情報取得部６２は、第２のキーワード入力部６１が入力したキーワードを受け取る。そして、対応情報取得部６２は、内部記憶部２５から、入力したキーワードに対応する対応情報を取得する。
【００３４】
なお、内部記憶部２５は、１つのキーワードに対応して複数の対応情報を記憶している場合もある。この場合、対応情報取得部６２は、入力した１つのキーワードに対応する複数の対応情報を取得する。また、対応情報取得部６２は、入力したキーワードに対応する対応情報が内部記憶部２５に記憶されていない場合、キーワードが存在しないことを示す通知を外部に出力する。
【００３５】
第２のタグ鍵入力部６３は、内部記憶部２５に記憶されたタグ鍵を入力する。第２のタグ生成部６４は、第２のタグ鍵入力部６３が入力したタグ鍵、第２のキーワード入力部６１が入力したキーワード、および、対応情報取得部６２が取得した対応情報を受け取る。そして、第２のタグ生成部６４は、タグ鍵とキーワードと対応情報とに基づきタグを生成する。第２のタグ生成部６４は、対応情報取得部６２が複数の対応情報を取得した場合には、複数の対応情報のそれぞれについてタグを生成する。
【００３６】
なお、第２のタグ生成部６４は、第１のタグ生成部４９と同一の方法でタグを生成する。例えば、上述した式（２）と同一のタグ生成関数ＴａｇＧｅｎ（）にタグ鍵とキーワードと対応情報とを入力してタグを生成する。これにより、第２のタグ生成部６４は、同一のキーワードおよび同一の対応情報を与えられた場合に、秘匿化時において生成したタグと同一のタグを生成することができる。
【００３７】
秘匿情報取得部６５は、第２のタグ生成部６４が生成したタグを検索部３２に出力する。第２のタグ生成部６４が複数のタグを生成した場合には、秘匿情報取得部６５は、複数のタグを検索部３２に出力する。検索部３２は、秘匿情報取得部６５からタグを受け取ると、外部記憶部３１に記憶された秘匿文、識別情報およびタグの組の中から、受け取ったそれぞれのタグを含む、秘匿文、識別情報およびタグの組を検索する。検索部３２は、受け取ったタグを含む、秘匿文、識別情報およびタグの組の集合が抽出された場合、抽出した秘匿文および識別情報の組の集合を秘匿情報取得部６５に出力する。そして、秘匿情報取得部６５は、検索部３２から、秘匿文および識別情報の組の集合を入力する。
【００３８】
第２のマスター鍵入力部６６は、内部記憶部２５に記憶されたマスター鍵を入力する。第２の秘匿鍵生成部６７は、第２のマスター鍵入力部６６が入力したマスター鍵、および、秘匿情報取得部６５が取得した識別情報を受け取る。そして、第２の秘匿鍵生成部６７は、マスター鍵と識別情報とに基づき、秘匿鍵を生成する。第２の秘匿鍵生成部６７は、秘匿情報取得部６５が複数の識別情報を取得した場合には、それぞれの識別情報について秘匿鍵を生成する。
【００３９】
なお、第２の秘匿鍵生成部６７は、第１の秘匿鍵生成部４５と同一の方法で秘匿鍵を生成する。例えば、上述した式（１）と同一の鍵生成関数ｋｅｙＧｅｎ（）に、マスター鍵と識別情報とを入力して秘匿鍵を生成する。これにより、第２の秘匿鍵生成部６７は、同一の識別情報を与えられた場合に、秘匿化時と同一の秘匿鍵を生成することができる。
【００４０】
復号部６８は、秘匿情報取得部６５が取得した秘匿文、および、第２の秘匿鍵生成部６７が生成した秘匿鍵を受け取る。そして、復号部６８は、秘匿鍵により秘匿文から平文を復号する。復号部６８は、秘匿情報取得部６５が複数の秘匿文を取得した場合には、複数の秘匿文から、対応する秘匿鍵により複数の平文を復号する。
【００４１】
復号部６８は、一例として、平文を秘匿鍵により暗号化した秘匿文から、平文を復号する。また、復号部６８は、一例として、平文を秘匿鍵により秘密分散して生成した複数のシェアを含む秘匿文から平文を復号する。なお、この場合において、復号部６８は、秘匿化部４６による秘匿化の方法と対応する方法で、秘匿文から平文を復号する。これにより、復号部６８は、秘匿化部４６により生成された秘匿文から平文を復号することができる。
【００４２】
平文出力部６９は、復号部６８により復号された平文を出力する。平文出力部６９は、秘匿情報取得部６５が複数の秘匿文を取得した場合には、複数の平文を出力する。
【００４３】
なお、秘匿化装置２１が、秘密分散をして複数個（例えばｑ個）のシェアを含む秘匿文を生成した場合、検索部３２は、異なるｑ個の外部記憶部３１に対してアクセスして、受けったタグに対応するシェアおよび識別情報の組を検索し、平文が復元可能な一定数のシェアと識別情報との組を取得する。なお、検索部３２は、例えばしきい値型秘密分散方式が利用されている場合には、ｑ個より少ない数のシェアと識別情報との組を取得すればよい。従って、検索部３２は、少なくとも一定数の外部記憶部３１にアクセスすれば、ｑ個の外部記憶部３１の全てにアクセスできなくてよい。そして、検索部３２は、一定数のシェアを含む秘匿文と、識別情報と、タグとの組を、秘匿情報取得部６５に出力する。
【００４４】
また、秘匿化装置２１が、秘密分散をして複数個のシェアを含む秘匿文を生成した場合、復号部６８は、秘密鍵を用いずに一定数のシェアから平文を復号する。従って、この場合、復号装置２２は、第２のマスター鍵入力部６６および第２の秘密鍵生成部６７を備えない構成となる。
【００４５】
図４は、秘匿化時の処理手順を示すフローチャートである。秘匿化装置２１は、秘匿化時において図４に示すフローに従って処理を実行する。
【００４６】
まず、平文入力部４１は、秘匿化対象の平文を入力する（Ｓ１１）。続いて、第１のキーワード入力部４２は、キーワードを入力する（Ｓ１２）。第１のキーワード入力部４２は、複数のキーワードを入力してもよい。続いて、第１のマスター鍵入力部４３は、内部記憶部２５に記憶されたマスター鍵を入力する（Ｓ１３）。続いて、識別情報生成部４４は、識別情報を生成する（Ｓ１４）。
【００４７】
続いて、第１の秘匿鍵生成部４５は、マスター鍵と識別情報とに基づき、秘匿鍵を生成する（Ｓ１５）。続いて、秘匿化部４６は、入力した平文を秘匿鍵により秘匿化した秘匿文を生成する（Ｓ１６）。続いて、第１のタグ鍵入力部４７は、内部記憶部２５に記憶されたタグ鍵を入力する（Ｓ１７）。
【００４８】
続いて、対応情報生成部４８および第１のタグ生成部４９は、キーワード毎に、ステップＳ１９およびステップＳ２０の処理を繰り返して実行する（Ｓ１８とＳ２１との間のループ処理）。ループ内において、対応情報生成部４８は、処理対象のキーワードに対応付けられる対応情報を生成する（Ｓ１９）。対応情報生成部４８は、一例として、新たな乱数を発生または入力して、対応情報とする。続いて、第１のタグ生成部４９は、タグ鍵と、対応するキーワードと、生成した対応情報とに基づきタグを生成する（Ｓ２０）。そして、第１のタグ生成部４９は、全てのキーワードについて処理を終えるとループを抜けてステップＳ２２に処理を進める（Ｓ２１）。
【００４９】
続いて、秘匿情報出力部５０は、生成した秘匿文、生成した識別情報、および、生成したタグの組を外部記憶部３１に出力して記憶させる（Ｓ２２）。なお、秘匿情報出力部５０は、複数のキーワードを入力した場合には、秘匿文、識別情報および複数のタグの組を外部記憶部３１に出力して記憶させる。
【００５０】
続いて、キーワード出力部５１は、キーワードおよび対応情報の組を内部記憶部２５に出力して記憶させる（Ｓ２３）。なお、キーワード出力部５１は、複数のキーワードを入力した場合には、複数のキーワード毎に、キーワードおよび対応する対応情報の組を内部記憶部２５に出力して記憶させる。また、秘匿化装置２１は、ステップＳ１３からステップＳ１６の前に、ステップＳ１７からステップＳ２１の処理を実行してもよい。また、秘匿化装置２１は、ステップＳ１３〜Ｓ１６の処理と、ステップＳ１７〜Ｓ２１の処理とを並列に実行してもよい。
【００５１】
図５は、内部記憶部２５に記憶されたキーワードと対応情報との対応関係の第１例を示す図である。図６は、内部記憶部２５に記憶されたキーワードと対応情報との対応関係の第２例を示す図である。
【００５２】
内部記憶部２５は、複数のキーワードについて、キーワードと対応情報との組を記憶する。複数の平文を秘匿化した結果、内部記憶部２５には、１つのキーワードに対して、複数の対応情報が対応付けられる状態となる可能性がある。このような場合、内部記憶部２５は、図５に示すように、キーワードと対応情報との組をそのまま追加して記憶してもよい。
【００５３】
また、内部記憶部２５は、図６に示すように、１つのキーワードに対して、複数の対応情報の組を記憶してもよい。この場合、内部記憶部２５は、秘匿化装置２１から１つのキーワードと対応情報の組を受け取ると、既に記憶されている同一のキーワードを検索し、同一のキーワードが検出されればそのキーワードに対応付けて受け取った対応情報を記憶する。同一のキーワードが検出されなければ、内部記憶部２５は、受けったキーワードと対応情報の組を追加して記憶する。
【００５４】
また、対応情報生成部４８は、同一のキーワードが複数回入力される場合、最初のキーワードの入力時において乱数を対応情報として発生し、以後、同一のキーワードが入力される毎に最初に発生した乱数の値を所定値（例えば１）ずつインクリメントした値を対応情報として発生してもよい。この場合、内部記憶部２５は、１つのキーワードに対して、最初に発生した乱数の値、および、そのキーワードについて対応情報を発生した回数を記憶してもよい。内部記憶部２５は、検索時において、最初に発生した乱数から、対応情報を発生した回数まで所定値ずつインクリメントしたそれぞれの値を、対応情報として出力する。
【００５５】
図７は、復号時の処理手順を示すフローチャートである。復号装置２２は、復号時において、図７に示すフローに従って処理を実行する。
【００５６】
まず、第２のキーワード入力部６１は、検索対象のキーワードを入力する（Ｓ３１）。続いて、対応情報取得部６２は、内部記憶部２５から、入力したキーワードに対応する対応情報を取得する（Ｓ３２）。入力したキーワードに対応して複数の対応情報が記憶されている場合、対応情報取得部６２は、複数の対応情報を取得する。続いて、第２のタグ鍵入力部６３は、内部記憶部２５に記憶されたタグ鍵を入力する（Ｓ３３）。
【００５７】
続いて、第２のタグ生成部６４は、取得した対応情報毎に、ステップＳ３５の処理を実行する（Ｓ３４とＳ３６との間のループ処理）。ループ内において、第２のタグ生成部６４は、タグ鍵と、キーワードと、対応する対応情報とに基づきタグを生成する。第２のタグ生成部６４は、全ての対応情報についてタグを生成すると処理をステップＳ３７に進める。
【００５８】
続いて、秘匿情報取得部６５は、生成した全てのタグを検索部３２に出力する（Ｓ３７）。続いて、検索部３２は、外部記憶部３１に記憶された秘匿文、識別情報およびタグの組の中から、受け取ったそれぞれのタグを含む、秘匿文、識別情報およびタグの組を検索する（Ｓ３８）。検索部３２は、入力したタグを含む、秘匿文、識別情報およびタグの組の集合が抽出された場合、抽出した秘匿文および識別情報の組の集合を秘匿情報取得部６５に出力する。
【００５９】
続いて、秘匿情報取得部６５は、検索部３２から、秘匿文および識別情報の組の集合を入力する（Ｓ３９）。続いて、第２のマスター鍵入力部６６は、内部記憶部２５に記憶されたマスター鍵を入力する（Ｓ４０）。
【００６０】
続いて、第２の秘匿鍵生成部６７および復号部６８は、秘匿情報取得部６５が取得した識別情報毎に、ステップＳ４２およびステップＳ４３の処理を実行する（Ｓ４１とＳ４４との間のループ処理）。ループ内において、第２の秘匿鍵生成部６７は、マスター鍵、および、秘匿情報取得部６５が取得した識別情報に基づき、処理対象の識別情報に対応する秘匿鍵を生成する（Ｓ４２）。続いて、ループ内において、復号部６８は、生成した秘匿鍵により、処理対象の識別情報と組となっている秘匿文から平文を復号する（Ｓ４３）。第２の秘匿鍵生成部６７および復号部６８は、全ての識別情報について平文を復号すると、処理をステップＳ４５に進める。
【００６１】
そして、平文出力部６９は、復号された全ての平文を出力する（Ｓ４５）。
【００６２】
図８は、キーワードとタグとの対応関係の第１例を示す図である。対応情報生成部４８は、同一のキーワードが入力された場合であっても、キーワードを入力する毎に異なる対応情報を生成する。従って、第１のタグ生成部４９は、同一のキーワードが入力された場合であっても、キーワードを入力する毎に異なるタグを生成する。なお、第１のタグ生成部４９は、同一のキーワードに対して常に異なるタグを生成するのではなく、同一のキーワードに対して同一のタグが重複する場合があっても構わない。
【００６３】
ここで、第１のタグ生成部４９は、一例として、１つのキーワードに対応付けられ、他のキーワードには対応付けられないタグを生成する。例えば、第１のタグ生成部４９は、図８に示すようなタグを生成する。図８においては、タグｔ１およびｔ２は、キーワードｗ１に対応付けられているが、他のキーワードには対応付けられていない。また、タグｔ３、ｔ４およびｔ５は、キーワードｗ２に対応付けられているが、他のキーワードには対応付けられていない。
【００６４】
例えば、第１のタグ生成部４９は、下記の式（３−１）、式（３−２）または式（３−３）に示されるタグ生成関数によりタグを生成する。
ｔ＝Ｆ（ｗ‖ｒ）  …（３−１）
ｔ＝Ｆ（Ｇ（ｗ‖ｒ））  …（３−２）
ｔ＝Ｆ（Ｇ（ｒ‖ｗ））  …（３−３）
【００６５】
‖は、左右のデータ列を結合する関数である。Ｇ（）は、入力データのビット配置を予め定められた規則で置き換える関数である。Ｆ（）は、入力データと出力データとが一対一となる関係の関数である。また、式（３−１）、式（３−２）および式（３−３）において、関数Ｇ（）および関数Ｆ（）がタグ鍵ｔｋに対応する。
【００６６】
このような関数を用いることにより、第１のタグ生成部４９は、それぞれが１つのキーワードに対応付けられる複数のタグを生成することができる。検索システム１０は、このようなタグを用いることにより、キーワードに対応しない秘匿文が抽出されないので、効率良く検索および復号をすることができる。
【００６７】
図９は、キーワードとタグとの対応関係の第２例を示す図である。第１のタグ生成部４９は、複数のキーワードに対応付けられる可能性を有するタグを生成してもよい。
【００６８】
例えば、第１のタグ生成部４９は、図９に示すようなタグを生成する。すなわち、図９においては、タグｔ１およびｔ２は、キーワードｗ１に対応付けられているが、他には対応付けられていない。また、タグｔ４およびｔ５は、キーワードｗ２に対応付けられているが、他には対応付けられていない。しかし、タグｔ３は、キーワードｗ１およびキーワードｗ２の２つに対応付けられている。
【００６９】
例えば、第１のタグ生成部４９は、下記の式（４）または式（５）に示されるタグ生成関数によりタグを生成する。
ｔ＝Ｈａｓｈ（ｔｋ‖ｗ‖ｒ）…（４）
ｔ＝Ｈａｓｈ（ｔｋ×ｗ×ｒ）…（５）
【００７０】
Ｈａｓｈ（）は、入力データのハッシュ値を算出するハッシュ関数である。×は、左右の値を乗算する関数である。なお、第１のタグ生成部４９は、式（４）または式（５）以外にも、ｔｋ，ｗ，ｋに基づく値が引数となるハッシュ関数によりタグを生成してもよい。
【００７１】
また、例えば、第１のタグ生成部４９は、下記の式（６−１）または式（６−２）に示されるようなタグ生成関数によりタグを生成してもよい。
ｔ＝Ｆ（Ｇ（ｗ×ｒ））…（６−１）
ｔ＝Ｆ（Ｇ（ｒ×ｗ））…（６−２）
【００７２】
式（６−１）および式（６−２）において、関数Ｇ（）および関数Ｆ（）がタグ鍵ｔｋに対応する。
【００７３】
第１のタグ生成部４９は、以上の式の他にも、引数をｔｋ，ｗ，ｒに基づいた値としたランダム化関数によりタグを生成してもよい。
【００７４】
このような関数を用いることにより、第１のタグ生成部４９は、それぞれが複数のキーワードに対応付けられる可能性を有する複数のタグを生成することができる。検索システム１０は、このようなタグを用いて検索することにより、盗聴者等が同一のキーワードに対応する秘匿文を検出しても誤りを含んだ秘匿文の集合が抽出されるので、安全性をより向上させることができる。
【００７５】
図１０は、マスター鍵と秘匿鍵との関係を示す図である。第１の秘匿鍵生成部４５は、マスター鍵および識別情報に基づき、識別情報に対応した秘匿鍵を生成する。
【００７６】
例えば、第１の秘匿鍵生成部４５は、特許文献２に記載されているような、サーバ鍵からクライアント鍵を生成する方法により、マスター鍵から秘匿鍵を生成する。すなわち、第１の秘匿鍵生成部４５は、予め定められた鍵規則と識別情報とに基づき、識別情報毎（平文毎）に異なる秘匿鍵を生成する。
【００７７】
この場合において、第１の秘匿鍵生成部４５は、識別情報毎に異なり、一部が他の秘匿鍵と相関を有する複数の秘匿鍵を生成する。つまり、それぞれの秘匿鍵は、一部に他の秘匿鍵と相関を有するビット系列を含んでいる。このような秘匿鍵を用いることにより、検索システム１０は、秘匿鍵を全て保持するよりも、秘匿して保持しておく情報量を少なくすることができる。
【００７８】
ここで、鍵規則は、マスター鍵Ｋｓの１つ以上の部分系列を抽出して秘匿鍵Ｋｉを生成するための規則である。すなわち、鍵規則は、秘匿鍵Ｋｉを定めるための規則である。秘匿鍵Ｋｉは、１つ以上の部分系列を要素とする部分系列集合に基づいて定められる。複数の秘匿鍵Ｋｉのうち、いずれか２つの秘匿鍵Ｋｉの第１部分系列集合の少なくとも１つの部分系列が相関を有する。部分系列とは、マスター鍵Ｋｓの部分情報である。なお、鍵規則は、公開された情報（すなわち、秘匿されていない情報）であってもよいし、秘匿して管理される秘密情報であってもよい。
【００７９】
図１１は、マスター鍵生成部２３の構成の一例を示す図である。図１２は、乱数からマスター鍵を生成する処理を示す図である。
【００８０】
秘匿化部４６は、一例として、ｎ（ｎは２以上の整数）個の平文Ｍｉ（＝Ｍ１，Ｍ２，…，Ｍｎ）を、ｎ個の対応する秘匿鍵Ｋｉ（＝Ｋ１，Ｋ２，…，Ｋｎ）で暗号化して、ｎ個の秘匿文Ｃｉ（＝Ｃ１，Ｃ２，…，Ｃｎ）を生成する。ｎ個の秘匿鍵は、全て同一のビット長である。また、平文のビット長と秘匿鍵のビット長は、｜ｍ｜で同一である。そして、秘匿化部４６は、平文Ｍｉと秘匿鍵Ｋｉとを排他的論理和演算して、秘匿文Ｃｉを生成する。なお、秘匿化部４６は、秘匿化したい平文の長さが平文ごとに異なる場合、平文を固定長で分割またはパディング等の処理で平文長を揃えることにより、本手法を用いることができる。また、秘匿化部４６は、ここではワンタイムパットにより秘匿文Ｃｉを生成しているが、他の暗号化方式で秘匿文Ｃｉを生成してもよい。
【００８１】
秘匿化部４６がこのような暗号化をする場合であって、一部が他の秘匿鍵と相関を有する複数の秘匿鍵を生成するためのマスター鍵Ｋｓを生成する場合、マスター鍵生成部２３は、例えば、図１１に示すような構成を有する。すなわち、マスター鍵生成部２３は、差分算出部８１と、部分系列長算出部８２と、係数算出部８３と、マスター鍵結合部８４とを有する。
【００８２】
差分算出部８１は、平文数ｎおよびｎ個の導出パラメータρ１，ｙを入力する。平文数ｎは、暗号化することができる最大の平文数、すなわち、生成する秘匿鍵の数である。ｎ個の導出パラメータρ１，ｙは、ユーザが任意に設定する値であって、０以上１以下の値である。ｎ個の導出パラメータρ１，ｙは、攻撃者がｎ個の秘匿文とｙ（ｙは０以上ｎ−１以下の整数のそれぞれ）個の秘匿鍵を知ったそれぞれの場合における、１個の平文に対する安全性を表す。ｎ個の導出パラメータρ１，ｙは、ρ１，０，ρ１，１，ρ１，２，…，ρ１，ｎ−１と表される。導出パラメータρ１，ｙは、値が大きい方が（つまり、１に近い方が）、安全性が高いことを意味する。
【００８３】
差分算出部８１は、それぞれのｘ（ｘは０以上ｎ以下の整数）について、差分ｄ（ｘ）＝（ρ１，ｘ−１−ρ１，ｘ）を算出する。つまり、ｄ（０）＝（ρ１，−１−ρ１，０），ｄ（１）＝（ρ１，０−ρ１，１），ｄ（２）＝（ρ１，１−ρ１，２），…，ｄ（ｎ）＝（ρ１，ｎ−１−ρ１，ｎ）を算出する。
【００８４】
ただし、ρ１，−１およびρ１，ｎは、ダミーの導出パラメータとして予め設定されている。ここでは、ρ１，−１＝１，ρ１，ｎ＝０と設定されている。
【００８５】
部分系列長算出部８２は、平文のビット長｜ｍ｜、および、差分算出部８１により算出された差分ｄ（ｘ）を入力する。部分系列長算出部８２は、下記の式（７）の演算をして、それぞれのｘについて、部分系列長｜ｓｉ，ｘ｜を算出する。部分系列長｜ｓｉ，ｘ｜が整数でない場合は、部分系列長算出部８２は、小数点以下を切り捨て、切り上げ、四捨五入等の処理を行い、ｘを整数にする。
｜ｓｉ，ｘ｜＝ｄ（ｘ）×｜ｍ｜…（７）
【００８６】
係数算出部８３は、部分系列長｜ｓｉ，ｘ｜および乱数ｒを入力する。係数算出部８３は、それぞれのｘについて、下記式（８）に表される多項式の係数ａｔ，ｘを取得する。
【数１】
0006441160.tif 000002
【００８７】
それぞれの係数ａｔ，ｘは、その値が互いに異なる乱数であり、ビット長が部分系列長｜ｓｉ，ｘ｜となる。例えば、係数算出部８３は、図１２のＳ１１１に示すように、入力した乱数ｒから部分系列長｜ｓｉ，ｘ｜のビット列を抽出して、それぞれの係数ａｔ，ｘを生成する。そして、係数算出部８３は、取得した係数の集合を出力する。
【００８８】
マスター鍵結合部８４は、係数算出部８３から出力された係数ａｔ，ｘの集合を入力する。マスター鍵結合部８４は、図１２のＳ１１２に示すように、取得した係数ａｔ，ｘを第１鍵規則に従って連結または置き換えをして配置することにより、マスター鍵Ｋｓを生成する。
【００８９】
そして、マスター鍵結合部８４は、第１鍵規則、第２鍵規則およびマスター鍵Ｋｓを出力する。なお、第１鍵規則は、係数ａｔ，ｘの集合から、マスター鍵Ｋｓを生成するための規則である。また、第２鍵規則は、係数ａｔ，ｘの集合の中から選択された識別情報ｉに対応する係数ａｔ，ｘから、秘匿鍵Ｋｉを生成するための規則である。
【００９０】
図１３は、第１の秘匿鍵生成部４５の構成の一例を示す図である。図１４は、マスター鍵から秘匿鍵を生成する処理を示す図である。
【００９１】
図１１に示すようなマスター鍵生成部２３により生成されたマスター鍵から秘匿鍵を生成する場合、第１の秘匿鍵生成部４５は、例えば図１３に示すような構成を有する。すなわち、第１の秘匿鍵生成部４５は、係数群抽出部９１と、部分系列群抽出部９２と、秘匿鍵結合部９３とを有する。
【００９２】
係数群抽出部９１は、マスター鍵Ｋｓおよび第１鍵規則を入力する。そして、係数群抽出部９１は、図１４のＳ１２１に示すように、マスター鍵Ｋｓから第１鍵規則に従って、それぞれの係数ａｔ，ｘの集合を抽出する。
【００９３】
部分系列群抽出部９２は、係数群抽出部９１により抽出された係数ａｔ，ｘの集合および識別情報ｉを入力する。そして、部分系列群抽出部９２は、図１４のＳ１２２に示すように、部分系列ｓｉ，ｘを生成するために、係数ａｔ，ｘの集合からｘがｓｉ，ｘのｘと一致する係数を選択し、多項式ｆｘ（ｉ）を生成する。部分系列ｓｉ，ｘは、多項式ｆｘ（ｉ）の出力である。なお、多項式ｆｘ（ｉ）は、下記の式（９）に示すように、式（８）に示した多項式である。
【数２】
0006441160.tif 000003
【００９４】
秘匿鍵結合部９３は、識別情報ｉに対応する部分系列ｓｉ，ｘおよび第２鍵規則を入力する。秘匿鍵結合部９３は、図１４のＳ１２３に示すように、取得した部分系列ｓｉ，ｘを第２鍵規則に従って連結または置き換えをして配置することにより、識別情報ｉに対応する秘匿鍵Ｋｉを生成する。
【００９５】
つぎに、平文の数ｎ（秘匿鍵の数ｎ）を４とした場合における具体的な秘匿鍵Ｋｉの生成例について説明する。例えば下記のような４個の導出パラメータρ１，ｙを入力したとする。
ρ１，０＝１
ρ１，１＝１
ρ１，２＝０．８
ρ１，３＝０
【００９６】
この場合、差分ｄ（ｘ）は以下のようになる。
ｄ（０）＝（ρ１，−１−ρ１，０）＝（１−１）＝０
ｄ（１）＝（ρ１，０−ρ１，１）＝（１−１）＝０
ｄ（２）＝（ρ１，１−ρ１，２）＝（１−０．８）＝０．２
ｄ（３）＝（ρ１，２−ρ１，３）＝（０．８−０）＝０．８
ｄ（４）＝（ρ１，３−ρ１，４）＝（０−０）＝０
【００９７】
それぞれのｘに対応する多項式は、下記の式（１０）および式（１１）のようになる。なお、ｓｉ，０，ｓｉ，１，ｓｉ，４は、ｄ（ｘ）×｜ｍ｜＝０となるので、生成する必要がない。
【数３】
0006441160.tif 000004
【００９８】
マスター鍵Ｋｓは、多項式ｆ２（ｉ）およびｆ３（ｉ）に含まれる係数ａｔ，ｘの集合の組み合わせである。従って、マスター鍵Ｋｓの要素は、下記の式（１２）に示すようになる。
Ｋｓ＝｛ａｔ，ｘ｜ｘ＝１，…，ｎ，ｔ＝０，…，ｘ−１｝＝｛ａ０，２，ａ１，２，ａ０，３，ａ１，３，ａ２，３｝…（１２）
【００９９】
マスター鍵Ｋｓは、例えば第１鍵規則が要素の連結だった場合、以下のようになる。
Ｋｓ＝ａ０，２‖ａ１，２‖ａ０，３‖ａ１，３‖ａ２，３
【０１００】
そして、識別情報ｉに対応する秘匿鍵Ｋｉは、マスター鍵（すなわち、ｓｉ，２およびｓｉ，３の多項式に含まれる係数ａｔ，ｘの集合）の中から選択された係数ａｔ，ｘから生成された多項式ｆｘ（ｉ）の出力の集合ｓｉ，ｘである。従って、秘匿鍵Ｋｉの要素は、下記の式（１３）のようになる。
Ｋｉ＝｛Ｓｉ，ｘ｜ｘ＝１，…，４｝…（１３）
【０１０１】
秘匿鍵Ｋｉは、例えば第２鍵規則が要素の連結だった場合、以下のようになる。
Ｋ1＝ｓ１，１‖ｓ１，２‖ｓ１，３‖ｓ１，４
Ｋ２＝ｓ２，１‖ｓ２，２‖ｓ２，３‖ｓ２，４
Ｋ３＝ｓ３，１‖ｓ３，２‖ｓ３，３‖ｓ３，４
Ｋ４＝ｓ４，１‖ｓ４，２‖ｓ４，３‖ｓ４，４
【０１０２】
以上のように本実施形態に係る検索システム１０は、キーワードと対応情報とに基づきタグを生成しているので、同一のキーワードであっても異なるタグを生成する。これにより、検索システム１０は、タグから秘匿文の内容や秘匿文の統計情報を推定することを困難として安全性を向上させることができる。さらに、検索システム１０は、キーワードと対応情報とを秘匿して記憶していればよいので、検索のために保有しなければならない情報を小さくすることができる。このように本実施形態に係る検索システム１０によれば、検索のために保有しなければならない情報を小さくしつつ、秘匿文およびタグの安全性を向上することができる。
【０１０３】
以上のような本実施形態は、例えば、多数のプライバシー情報等を収集し、収集したそれぞれの情報を秘匿化して管理するシステムに適用することができる。例えば、本実施形態は、患者の状態を検出するセンサ（体温計、血圧計、脈拍計）等から検出データを収集し、収集した検出データのそれぞれを暗号化して管理する医療システム等に適用することができる。
【０１０４】
（第２実施形態）
図１５は、第２実施形態に係る検索システム１１０の構成を示す図である。なお、第２の実施形態は、第１の実施形態と略同一の機能および構成を有するので、第１の実施形態と略同一の機能および構成を有する部材に同一の符号を付けて、相違点を除き詳細な説明を省略する。第３実施形態以降の実施形態も同様である。
【０１０５】
第２実施形態に係る検索システム１１０は、情報処理部２０と、記録メディア１１１とを備える。本実施形態に係る情報処理部２０は、検索部３２をさらに有する。記録メディア１１１は、外部記憶部３１を有する。
【０１０６】
記録メディア１１１は、例えば、ＣＤ（Compact  Disk），ＤＶＤ（Digital  Versatile  Disk），ＳＤメモリカード，ＵＳＢ（Universal  Serial  Bus）メモリまたは取り外し可能なＨＤＤ（Hard  Disk  Drive）等である。記録メディア１１１は、情報処理部２０が設けられた内部ネットワーク上のコンピュータ等により取り付けられる。検索部３２は、内部ネットワーク上のコンピュータ等により実現される。このように本実施形態に係る検索システム１１０は、秘匿文およびタグを記録メディア１１１に記憶させることができる。
【０１０７】
（第３実施形態）
図１６は、第３実施形態に係る検索システム１２０の構成を示す図である。第３実施形態に係る検索システム１２０の情報処理部２０は、統計部１２１をさらに有する。
【０１０８】
統計部１２１は、検索部３２から出力された秘匿文および識別情報の組のうち、識別情報の組の集合を入力する。そして、統計部１２１は、復号装置２２が生成したタグに対応する識別情報の数をカウントして、キーワードに対応する統計情報を出力する。例えば、統計情報は、秘匿文の数の情報や、キーワード毎の秘匿分の数に関する大小関係の情報であってよい。
【０１０９】
このような本実施形態に係る検索システム１２０は、秘匿文を復号せずに、キーワードに対応した統計情報を検出することができる。なお、本実施形態において、復号装置２２は、秘匿文を復号しない構成であってもよい。つまり、復号装置２２は、タグを生成して検索部３２に送信する処理をすれば、他の処理をしなくてもよい。また、この場合において、統計部１２１は、情報処理部２０に含まれなくてもよい。例えば、統計部１２１は、記憶部３０に含まれていてもよい。また、本実施形態を第２実施形態に適用してもよい。
【０１１０】
（第４実施形態）
図１７は、第４実施形態に係る復号装置２２の構成を示す図である。第４実施形態に係る復号装置２２は、論理式入力部１３１をさらに備える。
【０１１１】
本実施形態において、第２のキーワード入力部６１は、１または複数のキーワードを入力する。論理式入力部１３１は、第２のキーワード入力部６１が入力した１または複数のキーワードを入力値とした論理式を入力する。対応情報取得部６２は、入力した１または複数のキーワードのそれぞれについて、対応情報を取得する。そして、秘匿情報取得部６５は、入力した１または複数のキーワードのそれぞれについて、１または複数のタグを生成する。
【０１１２】
秘匿情報取得部６５は、キーワードを入力値とした論理式を、第２のタグ生成部６４が生成したタグを入力値とした論理式に置き換える。そして、秘匿情報取得部６５は、入力した１または複数のキーワードのそれぞれについてのタグとともに、論理式を検索部３２へと出力する。
【０１１３】
検索部３２は、外部記憶部３１を検索して、与えられたそれぞれのタグに対応する、秘匿文および識別情報の組の集合を抽出する。検索部３２は、それぞれのタグに対応する秘匿文および識別情報の組の集合を入力値として、与えられた論理式に従った演算をする。そして、検索部３２は、論理式の演算結果として得られた秘匿文および識別情報の組の集合を、復号装置２２へと出力する。そして、秘匿情報取得部６５は、検索部３２から出力された秘匿文および識別情報の組を取得する。
【０１１４】
このように本実施形態に係る復号装置２２は、秘匿文を復号せずに、１または複数のキーワードを入力値とした論理式を演算した結果を取得することができる。なお、本実施形態を第２または第３実施形態に適用してもよい。
【０１１５】
（ハードウェア構成）
実施形態に係るコンピュータのハードウェア構成を示す図である。本実施形態に係る秘匿化装置２１および復号装置２２は、例えば図１８に示すようなハードウェア構成のコンピュータ２００により実現される。このコンピュータ２００は、ＣＰＵ（Central  Processing  Unit）２０１と、ＲＡＭ（Random  Access  Memory）２０２と、ＲＯＭ（Read  Only  Memory）２０３と、操作入力装置２０４と、表示装置２０５と、記憶装置２０６と、通信装置２０７とを備える。そして、これらの各部は、バスにより接続される。
【０１１６】
ＣＰＵ２０１は、プログラムに従って演算処理および制御処理等を実行するプロセッサである。ＣＰＵ２０１は、ＲＡＭ２０２の所定領域を作業領域として、ＲＯＭ２０３および記憶装置２０６等に記憶されたプログラムとの協働により各種処理を実行する。
【０１１７】
ＲＡＭ２０２は、ＳＤＲＡＭ（Synchronous  Dynamic  Random  Access  Memory）等のメモリである。ＲＡＭ２０２は、ＣＰＵ２０１の作業領域として機能する。ＲＯＭ２０３は、プログラムおよび各種情報を書き換え不可能に記憶するメモリである。
【０１１８】
操作入力装置２０４は、マウスおよびキーボード等の入力デバイスである。操作入力装置２０４は、ユーザから操作入力された情報を指示信号として受け付け、指示信号をＣＰＵ２０１に出力する。
【０１１９】
表示装置２０５は、ＬＣＤ（Liquid  Crystal  Display）等の表示デバイスである。表示装置２０５は、ＣＰＵ２０１からの表示信号に基づいて、各種情報を表示する。
【０１２０】
記憶装置２０６は、フラッシュメモリ等の半導体による記憶媒体、または、磁気的若しくは光学的に記録可能な記憶媒体等にデータを書き込みおよび読み出しをする装置である。記憶装置２０６は、ＣＰＵ２０１からの制御に応じて、記憶媒体にデータの書き込みおよび読み出しをする。通信装置２０７は、ＣＰＵ２０１からの制御に応じて外部の機器とネットワークを介して通信する。
【０１２１】
本実施形態の秘匿化装置２１で実行されるプログラムは、平文入力モジュール、第１のキーワード入力モジュール、第１のマスター鍵入力モジュール、識別情報生成モジュール、第１の秘匿鍵生成モジュール、秘匿化モジュール、第１のタグ鍵入力モジュール、対応情報生成モジュール、第１のタグ生成モジュール、秘匿情報出力モジュールおよびキーワード出力モジュールを含むモジュール構成となっている。このプログラムは、ＣＰＵ２０１（プロセッサ）によりＲＡＭ２０２上に展開して実行されることにより、コンピュータ２００を、平文入力部４１と、第１のキーワード入力部４２と、第１のマスター鍵入力部４３と、識別情報生成部４４と、第１の秘匿鍵生成部４５と、秘匿化部４６と、第１のタグ鍵入力部４７と、対応情報生成部４８と、第１のタグ生成部４９と、秘匿情報出力部５０と、キーワード出力部５１として機能させる。
【０１２２】
なお、秘匿化装置２１は、このような構成に限らず、平文入力部４１、第１のキーワード入力部４２、第１のマスター鍵入力部４３、識別情報生成部４４、第１の秘匿鍵生成部４５、秘匿化部４６、第１のタグ鍵入力部４７、対応情報生成部４８、第１のタグ生成部４９、秘匿情報出力部５０およびキーワード出力部５１の少なくとも一部をハードウェア回路（例えば半導体集積回路）により実現した構成であってもよい。
【０１２３】
本実施形態の復号装置２２で実行されるプログラムは、第２のキーワード入力モジュール、対応情報取得モジュール、第２のタグ鍵入力モジュール、第２のタグ生成モジュール、秘匿情報取得モジュール、第２のマスター鍵入力モジュール、第２の秘匿鍵生成モジュール、復号モジュールおよび平文出力モジュールを含むモジュール構成となっている。このプログラムは、ＣＰＵ２０１（プロセッサ）によりＲＡＭ２０２上に展開して実行されることにより、コンピュータ２００を、第２のキーワード入力部６１と、対応情報取得部６２と、第２のタグ鍵入力部６３と、第２のタグ生成部６４と、秘匿情報取得部６５と、第２のマスター鍵入力部６６と、第２の秘匿鍵生成部６７と、復号部６８と、平文出力部６９として機能させる。
【０１２４】
なお、復号装置２２は、このような構成に限らず、第２のキーワード入力部６１、対応情報取得部６２、第２のタグ鍵入力部６３、第２のタグ生成部６４、秘匿情報取得部６５、第２のマスター鍵入力部６６、第２の秘匿鍵生成部６７、復号部６８および平文出力部６９の少なくとも一部をハードウェア回路（例えば半導体集積回路）により実現した構成であってもよい。
【０１２５】
また、本実施形態の秘匿化装置２１および復号装置２２で実行されるプログラムは、コンピュータにインストール可能な形式または実行可能な形式のファイルで、ＣＤ−ＲＯＭ、フレキシブルディスク、ＣＤ−Ｒ、ＤＶＤ（Digital  Versatile  Disk）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０１２６】
また、本実施形態の秘匿化装置２１および復号装置２２で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、本実施形態の秘匿化装置２１および復号装置２２で実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。また、秘匿化装置２１および復号装置２２で実行されるプログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０１２７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１２８】
１０  検索システム
２０  情報処理部
２１  秘匿化装置
２２  復号装置
２３  マスター鍵生成部
２４  タグ鍵生成部
２５  内部記憶部
３０  記憶部
３１  外部記憶部
３２  検索部
４１  平文入力部
４２  第１のキーワード入力部
４３  第１のマスター鍵入力部
４４  識別情報生成部
４５  第１の秘匿鍵生成部
４６  秘匿化部
４７  第１のタグ鍵入力部
４８  対応情報生成部
４９  第１のタグ生成部
５０  秘匿情報出力部
５１  キーワード出力部
６１  第２のキーワード入力部
６２  対応情報取得部
６３  第２のタグ鍵入力部
６４  第２のタグ生成部
６５  秘匿情報取得部
６６  第２のマスター鍵入力部
６７  第２の秘匿鍵生成部
６８  復号部
６９  平文出力部
８１  差分算出部
８２  部分系列長算出部
８３  係数算出部
８４  マスター鍵結合部
９１  係数群抽出部
９２  部分系列群抽出部
９３  秘匿鍵結合部
１１０  検索システム
１１１  記録メディア
１２０  検索システム
１２１  統計部
１３１  論理式入力部
【図１】
0006441160.tif 000006
【図２】
0006441160.tif 000007
【図３】
0006441160.tif 000008
【図４】
0006441160.tif 000009
【図５】
0006441160.tif 000010
【図６】
0006441160.tif 000011
【図７】
0006441160.tif 000012
【図８】
0006441160.tif 000013
【図９】
0006441160.tif 000014
【図１０】
0006441160.tif 000015
【図１１】
0006441160.tif 000016
【図１２】
0006441160.tif 000017
【図１３】
0006441160.tif 000018
【図１４】
0006441160.tif 000019
【図１５】
0006441160.tif 000020
【図１６】
0006441160.tif 000021
【図１７】
0006441160.tif 000022
【図１８】
0006441160.tif 000023