(57)【要約】【課題】各利用者に暗号化データベースの検索範囲の権限を設定し、各利用者がその権限に応じた範囲で暗号化データベースの検索を行う仕組みを容易に実現する。【解決手段】検索対象情報の暗号文と、当該検索対象情報に対応するキーワード及び何れかの端末装置に対応するレベル識別子の組をＩＤとした階層型ＩＤベース暗号方式の暗号文である暗号化キーワードと、が対応付けられた暗号化データベースをデータベース装置に格納する。端末装置は、秘密鍵と検索用のキーワードとを用い、レベル識別子と当該キーワードとの組をＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を検索トークンとして出力する。データベース装置は、検索トークンを秘密鍵として用い、階層型ＩＤベース暗号方式の復号手順に従った復号処理を行い、前記暗号化データベースに格納された各暗号化キーワードの復号結果を検証する。【選択図】図１
2010160235.tif 000002
【特許請求の範囲】
【請求項１】
暗号化データベースを検索するための検索システムであって、
データベース装置とN個（N≧2）の端末装置TAn（n=1,...,N）とを有し、
各端末装置TAnには、それぞれ、暗号化データベースに対する検索権限を示す検索権限レベルが設定され、設定された検索権限レベルを示すレベル識別子LVIDnが対応付けられ、
最も高い検索権限レベルが設定された端末装置TA1は、
階層型ＩＤベース暗号方式の秘密鍵を生成するためのマスター秘密鍵と、端末装置TA1よりも低い検索権限レベルが設定された端末装置TAm（m=2,...,N）に対応するレベル識別子LVIDmと、が少なくとも格納された記憶部STR1と、
記憶部STR1から読み込んだマスター秘密鍵と何れかのレベル識別子LVIDmとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、当該レベル識別子LVIDmをＩＤとする階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を端末装置TAmの秘密鍵SKmとして出力する秘密鍵生成部SKG1と、を含み、
端末装置TA1よりも低い検索権限レベルが設定された端末装置TAk（k=2,...,N-1）は、
自らよりも高い検索権限レベルが設定された端末装置TA1,...,TAk-1の何れかがレベル識別子LVIDkを用いて生成した端末装置TAkの秘密鍵SKkと、自らよりも低い検索権限レベルが設定された端末装置TAu（u=k+1,...,N）に対応するレベル識別子LVIDuと、検索用のキーワードと、が少なくとも格納された記憶部STRkと、
記憶部STRkから読み込んだ端末装置TAkの秘密鍵SKkとレベル識別子LVIDuとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、レベル識別子LVIDuをＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を端末装置TAuの秘密鍵SKuとして出力する秘密鍵生成部SKGkと、
記憶部STRkから読み込んだ端末装置TAkの秘密鍵SKkと検索用のキーワードとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、レベル識別子LVIDkと当該キーワードとの組をＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を検索トークンとして出力する検索トークン生成部TKGkと、を含み、
データベース装置は、
検索対象情報の暗号文と、当該検索対象情報に対応するキーワード及び何れかの端末装置TAnに対応するレベル識別子LVIDnの組をＩＤとした階層型ＩＤベース暗号方式の暗号文である暗号化キーワードと、が対応付けられた暗号化データベースが格納された記憶部STRDBと、
入力された検索トークンを秘密鍵として用い、階層型ＩＤベース暗号方式の復号手順に従った復号処理を行い、前記暗号化データベースに格納された各暗号化キーワードの復号結果を検証する検索部と、を含む、
ことを特徴とする検索システム。
【請求項２】
請求項１の検索システムであって、
端末装置TAkの検索トークン生成部TKGkは、
さらに、検索用のキーワードと、秘密鍵生成部SKGkで生成されたレベル識別子LVIDuをＩＤとした階層型ＩＤベース暗号方式の秘密鍵である秘密鍵SKuとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、端末装置TAuのレベル識別子LVIDuと当該キーワードとの組をＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を検索トークンとして出力する、
ことを特徴とする検索システム。
【請求項３】
請求項１又は２の検索システムであって、
端末装置TA1の記憶部STR1には、検索用のキーワードが格納され、
端末装置TA1は、
記憶部STR1から読み込んだマスター秘密鍵と何れかの端末装置TAnに対応するレベル識別子LVIDnと検索用のキーワードとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、レベル識別子LVIDnと当該キーワードとの組をＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を検索トークンとして出力する検索トークン生成部TKG1を有する、
ことを特徴とする検索システム。
【請求項４】
請求項１から３の何れかの検索システムであって、
前記階層型ＩＤベース暗号方式が、当該階層型ＩＤベース暗号方式に従って生成された暗号文から当該暗号文に対応するＩＤを特定することが困難な匿名階層型ＩＤベース暗号方式である、
ことを特徴とする検索システム。
【請求項５】
検索権限レベルが設定された複数の端末装置によってデータベース装置に格納された暗号化データベースを検索するための検索システムの端末装置であって、
階層型ＩＤベース暗号方式の秘密鍵を生成するためのマスター秘密鍵と、自らよりも検索権限レベルが低い他の端末装置に対応するレベル識別子と、検索用のキーワードとが少なくとも格納された記憶部と、
記憶部から読み込んだマスター秘密鍵と、自らよりも検索権限レベルが低い何れか他の端末装置に対応するレベル識別子とを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、当該他の端末装置に対応するレベル識別子をＩＤとする階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を当該他の端末装置の秘密鍵として出力する秘密鍵生成部と、
記憶部から読み込んだマスター秘密鍵と、自らよりも検索権限レベルが低い何れか他の端末装置に対応するレベル識別子と、検索用のキーワードとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、当該他の端末装置に対応するレベル識別子と当該キーワードとの組をＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を検索トークンとして出力する検索トークン生成部と、
を有する端末装置。
【請求項６】
検索権限レベルが設定された複数の端末装置によってデータベース装置に格納された暗号化データベースを検索するための検索システムの端末装置であって、
階層型ＩＤベース暗号方式の鍵生成手順に従って自らよりも検索権限レベルが高い他の端末装置が生成した秘密鍵と、自らよりも検索権限レベルが低い他の端末装置に対応するレベル識別子と、検索用のキーワードと、が格納された記憶部と、
記憶部から読み込んだ秘密鍵と、自らよりも検索権限レベルが低い他の端末装置に対応するレベル識別子とを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、当該他の端末装置に対応するレベル識別子をＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を当該他の端末装置に対応する秘密鍵として出力する秘密鍵生成部と、
記憶部から読み込んだ秘密鍵と検索用のキーワードとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、自らのレベル識別子と当該キーワードとの組をＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を検索トークンとして出力する検索トークン生成部と、
を有する端末装置。
【請求項７】
検索対象情報の暗号文と、当該検索対象情報に対応するキーワード及び端末装置の検索権限レベルを示すレベル識別子の組をＩＤとした階層型ＩＤベース暗号方式の暗号文である暗号化キーワードと、が対応付けられた暗号化データベースが格納された記憶部と、
何れかの端末装置の検索権限レベルを示すレベル識別子及び検索用のキーワードの組をＩＤとした階層型ＩＤベース暗号方式の秘密鍵である検索トークンが入力される入力部と、
前記入力部に入力された検索トークンを秘密鍵として用い、階層型ＩＤベース暗号方式の復号手順に従った復号処理を行い、前記暗号化データベースに格納された各暗号化キーワードの復号結果を検証する検索部と、
を有するデータベース装置。
【請求項８】
請求項１の検索システムで実行される検索方法であって、
最も高い検索権限レベルが設定された端末装置TA1の秘密鍵生成部SKG1が、記憶部STR1から読み込んだマスター秘密鍵と何れかのレベル識別子LVIDmとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、当該レベル識別子LVIDmをＩＤとする階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を端末装置TAmの秘密鍵SKmとして出力するステップと、
端末装置TAkの秘密鍵生成部SKGkが、記憶部STRkから読み込んだ端末装置TAkの秘密鍵SKkとレベル識別子LVIDuとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、レベル識別子LVIDuをＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を端末装置TAuの秘密鍵SKuとして出力するステップと、
端末装置TAkの検索トークン生成部TKGkが、記憶部STRkから読み込んだ端末装置TAkの秘密鍵SKkと検索用のキーワードとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、レベル識別子LVIDkと当該キーワードとの組をＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を検索トークンとして出力するステップと、
データベース装置の検索部が、入力された検索トークンを秘密鍵として用い、階層型ＩＤベース暗号方式の復号手順に従った復号処理を行い、前記暗号化データベースに格納された各暗号化キーワードの復号結果を検証するステップと、
を有する検索方法。
【請求項９】
請求項５又は６の端末装置としてコンピュータを機能させるためのプログラム。
【請求項１０】
請求項７のデータベース装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースを検索するための技術分野に関し、特に、暗号化されたデータベースを検索するための技術分野に関する。
【背景技術】
【０００２】
データベースを格納するデータベース装置とそのデータベースを検索する端末装置とが別個に構成され、端末装置がデータベース装置にデータベースを検索するための情報を送信し、データベース装置がそれに対する検索結果を端末装置に返す検索システムが存在する。このような検索システムにおいてデータベースの情報を秘匿化するための技術として、暗号化データベースを用いた検索システムが提案されている（例えば、非特許文献１〜３等参照）。
【０００３】
従来の暗号化データベースを用いた検索システムは、例えば、ＲＳＡなどの公開鍵暗号方式と任意のＩＤベース暗号方式との組み合わせによって実現することができる。以下、従来の暗号化データベースを用いた検索システムを例示する。
【０００４】
また、検索システムの利用者は、公開鍵暗号方式の秘密鍵Sと公開鍵Pとを生成する。また、データベース装置には、以下のような暗号化データベースが格納される。
【０００５】
E(P,A), IBE(P,KW1,"1"), IBE(P,KW2,"0"), IBE(P,KW3,"0")
E(P,B), IBE(P,KW1,"0"), IBE(P,KW2,"1"), IBE(P,KW3,"0")
…
E(P,Z), IBE(P,KW1,"0"), IBE(P,KW2,"1"), IBE(P,KW3,"0")
この暗号化データベースでは、各E(P,A)〜E(P,Z)が、それぞれ「IBE(P,KW1,"1"), IBE(P,KW2,"0"), IBE(P,KW3,"0")」〜「IBE(P,KW1,"0"), IBE(P,KW2,"1"), IBE(P,KW3,"0")」に関連付けられている。ここで、A〜Zはテキストデータなどの検索対象情報であり、E(P,A)〜E(P,Z)はそれぞれ、公開鍵Ｐを用いて公開鍵暗号方式Ｅによって検索対象情報A〜Zを暗号化した暗号文である。また、KW1〜KW3は検索用のキーワードであり、IBE(P, KW1,"0")〜IBE(P, KW3,"0")は、それぞれ、Pを公開パラメータとしてKW1〜KW3をＩＤとしたＩＤベース暗号方式によってキーワードKW1〜KW3が検索対象情報A〜Zに対応するか否かを示すビット情報"1"や"0"（キーワードが対応する＝"1"、キーワードが対応しない＝"0"）を暗号化した暗号文である。例えば、検索対象情報AにはキーワードKW1が対応するがキーワードKW2及びKW3が対応しない場合、暗号文E(P,A)に暗号文IBE(P,KW1,"1"), IBE(P,KW2,"0"), IBE(P,KW3,"0")が対応付けられる。
【０００６】
上記の利用者が端末装置を用い、何れかのキーワードKWiを指定し、データベース装置に対して上記の暗号化データベースの検索を依頼する場合、当該端末装置は、秘密鍵Ｓをマスター秘密鍵とし、当該キーワードKWiをＩＤとしたＩＤベース暗号方式での秘密鍵を生成し、それを検索トークンST(KWi)としてデータベース装置に送信する。データベース装置は、この検索トークンST(KWi)を用い、暗号化データベースを構成するすべてのＩＤベース暗号方式の暗号文「IBE(P,KW1,"1"), IBE(P,KW2,"0"), IBE(P,KW3,"0")」〜「IBE(P,KW1,"0"), IBE(P,KW2,"1"), IBE(P,KW3,"0")」を復号する。
【０００７】
ここで、検索トークンST(KWi)に対応するキーワードKWiが、復号処理を行った暗号文IBE(P, KWi,"1")に対応するキーワードKWiと一致した場合には、暗号文IBE(P, KWi,"1")が正しく復号され、ビット情報"1"（キーワードが対応する）が復元される。この場合にのみ、データベース装置は、当該暗号文IBE(P, KWi,"1")に対応付けられている暗号文E(P,A)を検索結果として端末装置に返す。一方、検索トークンST(KWi)に対応するキーワードKWiが、復号処理を行った暗号文IBE(P, KWi,"0")に対応するキーワードKWiと一致した場合には、暗号文IBE(P, KWi,"0")が正しく復号され、ビット情報"0"（キーワードが対応しない）が復元されるが、この場合、データベース装置は、当該暗号文IBE(P, KWi,"0")に対応付けられている暗号文E(P,*)を端末装置に返さない。また、検索トークンST(KWi)に対応するキーワードKWiが、復号処理を行った暗号文IBE(P, KWj,"1")又はIBE(P, KWj,"0")に対応するキーワードKWjと一致しない場合には、復号結果がエラーとなり、この場合、データベース装置は、当該暗号文IBE(P, KWj,"1")又はIBE(P, KWj,"0")に対応付けられている暗号文E(P,*)を端末装置に返さない。
【０００８】
データベース装置から暗号文E(P,*)が返された端末装置は、秘密鍵Sを用いて暗号文E(P,*)を復号し、検索対象情報*を得る。以上より、暗号化データベースの検索が実現される。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano, "Public Key Encryption with keyword Serch," Eurocrypt 2004.
【非特許文献２】M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. Malone-Lee, G. Neven, P. Paillier, and H. Shi, "Searchable Encryption Revised: Consistency Properties, Relation to Anonymous IBE, and Extensions," CRYPTO 2005.
【非特許文献３】D. Boneh and B. Waters, "Conjunctive, Subset, and Range Queries on Encrypted Data," TCC2007.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、従来の暗号化データベースの検索システムの場合、データベース装置に対して正しく暗号化データベースの検索を依頼できるのは、秘密鍵Sを利用できる単一の端末装置、又は、秘密鍵Sを共有する複数の端末装置だけである。この場合、各利用者に暗号化データベースの検索範囲の権限を設定し、各利用者がその権限に応じた範囲で暗号化データベースの検索を行う仕組みを容易に実現することが困難であった。
【００１１】
例えば、端末装置ごとに別個な秘密鍵Sが設定され、端末装置ごとに別個な暗号化データベースを構成してデータベース装置に格納した場合、各端末装置が正しく暗号化データベースの検索を依頼できるのは、自らの秘密鍵Sに対応する暗号化データベースのみである。また、複数の端末装置が秘密鍵Sを共有した場合、それらの端末装置はその秘密鍵Sに対応する暗号化データベースのすべての検索範囲について正しく検索を依頼することができ、これらの利用者間で暗号化データベースの検索範囲の権限を制御することはできない。また、複数種類の秘密鍵Sごとに暗号化データベースを設定し、各利用者に検索権限に応じた種類の秘密鍵Sの利用を可能にする構成とすれば、各利用者間での暗号化データベースの検索権限を制御することはできる。しかし、この場合には秘密鍵Sの管理が煩雑となる。
【００１２】
本発明はこのような点に鑑みてなされたものであり、各利用者に暗号化データベースの検索範囲の権限を設定し、各利用者がその権限に応じた範囲で暗号化データベースの検索を行う仕組みを容易に実現することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明の暗号化データベースを検索するための検索システムは、データベース装置とN個（N≧2）の端末装置TAn（n=1,...,N）とを有する。各端末装置TAnには、それぞれ、暗号化データベースに対する検索権限を示す検索権限レベルが設定され、設定された検索権限レベルを示すレベル識別子LVIDnが対応付けられる。
【００１４】
最も高い検索権限レベルが設定された端末装置TA1は、階層型ＩＤベース暗号方式の秘密鍵を生成するためのマスター秘密鍵と、端末装置TA1よりも低い検索権限レベルが設定された端末装置TAm（m=2,...,N）に対応するレベル識別子LVIDmと、が少なくとも格納された記憶部STR1と、記憶部STR1から読み込んだマスター秘密鍵と何れかのレベル識別子LVIDmとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、当該レベル識別子LVIDmをＩＤとする階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を端末装置TAmの秘密鍵SKmとして出力する秘密鍵生成部SKG1とを含む。
【００１５】
端末装置TA1よりも低い検索権限レベルが設定された端末装置TAk（k=2,...,N-1）は、自らよりも高い検索権限レベルが設定された端末装置TA1,...,TAk-1の何れかがレベル識別子LVIDkを用いて生成した端末装置TAkの秘密鍵SKkと、自らよりも低い検索権限レベルが設定された端末装置TAu（u=k+1,...,N）に対応するレベル識別子LVIDuと、検索用のキーワードと、が少なくとも格納された記憶部STRkと、記憶部STRkから読み込んだ端末装置TAkの秘密鍵SKkとレベル識別子LVIDuとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、レベル識別子LVIDuをＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を端末装置TAuの秘密鍵SKuとして出力する秘密鍵生成部SKGkと、記憶部STRkから読み込んだ端末装置TAkの秘密鍵SKkと検索用のキーワードとを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、レベル識別子LVIDkと当該キーワードとの組をＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を検索トークンとして出力する検索トークン生成部TKGkとを含む。
【００１６】
データベース装置は、検索対象情報の暗号文と、当該検索対象情報に対応するキーワード及び何れかの端末装置TAnに対応するレベル識別子LVIDnの組をＩＤとした階層型ＩＤベース暗号方式の暗号文である暗号化キーワードと、が対応付けられた暗号化データベースが格納された記憶部STRDBと、入力された検索トークンを秘密鍵として用い、階層型ＩＤベース暗号方式の復号手順に従った復号処理を行い、暗号化データベースに格納された各暗号化キーワードの復号結果を検証する検索部とを含む。
【００１７】
以上の構成により、上位の検索権限レベルが設定された端末装置は、それよりも下位の検索権限レベルが設定された端末装置の秘密鍵や検索トークンを生成でき、自らの検索権限レベル以下の検索権限レベルが設定されたすべての端末装置が検索可能な範囲で暗号化データベースを検索できる。一方、下位の検索権限レベルが設定された端末装置は、それよりも上位の検索権限レベルが設定された端末装置の秘密鍵や検索トークンを生成できず、自らの検索権限レベルよりも高い検索権限レベルで暗号化データベースを検索することができない。また、本発明の場合、各端末装置は、マスター秘密鍵又は自らの秘密鍵を保持していれば、自らの検索権限レベル以下の検索権限レベルが設定されたすべての端末装置に対応する秘密鍵や検索トークンを作成できるため、煩雑な鍵の管理を必要としない。
【発明の効果】
【００１８】
以上のように本発明では、各利用者に暗号化データベースの検索範囲の権限を設定し、各利用者がその権限に応じた範囲で暗号化データベースの検索を行う仕組みを容易に実現することが可能となる。
【図面の簡単な説明】
【００１９】
【図１】本形態の検索システムの全体構成を説明するための構成図。
【図２】図１に例示したデータベース装置の詳細構成を説明するための機能ブロック図。
【図３】図１に例示した端末装置（TA1）の機能構成を説明するための機能ブロック図。
【図４】図３の秘密鍵生成部（SKG1）の詳細構成の一例を説明するための機能ブロック図。
【図５】図３の検索トークン生成部(TKG1)の詳細構成の一例を説明するための機能ブロック図。
【図６】図１に例示した端末装置（TAk）の機能構成を説明するための機能ブロック図。
【図７】図６の秘密鍵生成部(SKGk)の詳細構成の一例を説明するための機能ブロック図。
【図８】図６の検索トークン生成部(TKGk)の詳細構成の一例を説明するための機能ブロック図。
【図９】図１に例示した端末装置（TAN）の機能構成を説明するための機能ブロック図。
【図１０】各端末装置（TAn）がデータベース装置の暗号化データベースの検索を依頼し、その検索結果を受け取る検索処理を説明するためのフローチャート。
【図１１】端末装置（TA1）の秘密鍵生成部(SKG1)が行う秘密鍵の生成方法の一例を説明するためのフローチャート。
【図１２】端末装置（TA1）が何れかのレベル識別子LVIDnに対応する検索処理を依頼する場合のステップＳ２の具体例を説明するためのフローチャート。
【図１３】端末装置（TAk）の秘密鍵生成部(SKGk)が行う秘密鍵の生成方法の一例を説明するためのフローチャート。
【図１４】端末装置（TAk）の秘密鍵生成部(SKGk)が行う秘密鍵の生成方法の一例を説明するためのフローチャート。
【図１５】端末装置（TAk）がレベル識別子LVIDk又はそれよりも検索権限が低いレベル識別子LVIDuに対応する検索処理を依頼する場合のステップＳ２の具体例を説明するためのフローチャート。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施形態を説明する。
〔記号・用語の定義〕
まず、実施形態で使用する記号・用語を定義する。
【００２１】
E：位数Tの有限体ＦT上で定義された楕円曲線。アフィン（affine）座標版のWeierstrass方程式
y2+a1・x・y+a3・y=x3+a2・x2+a4・x+a6    …(1)
（ただし、a1,a2,a3,a4,a6∈FT）を満たす点(x,y)の集合に無限遠点と呼ばれる特別な点Ｏを付加したもので定義される。楕円曲線Ｅ上の任意の２点に対して楕円加算と呼ばれる二項演算及び楕円曲線Ｅ上の任意の１点に対して楕円逆元と呼ばれる単項演算がそれぞれ定義できる。また、この楕円加算に関して群をなすこと、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できることはよく知られている。また、それらの演算をコンピュータ上で効率的に実行する様々なアルゴリズムもよく知られている（例えば、参考文献１“イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0”等参照）。
【００２２】
＃E：楕円曲線E上の有理点からなる有限集合の要素数。有限体FT上で定義された楕円曲線Ｅの有理点の個数＃Eは有限である。
κ：＃Eを割り切る大きい素数。
G：位数κの巡回群。本形態では、楕円曲線Ｅのκ等分点からなる有限集合E[κ]を巡回群Gとして用いる。楕円曲線Ｅ上の点Ａのうち、楕円曲線Ｅ上での楕円スカラー倍算値κ・Aがκ・A=Ｏを満たす点Ａの有限集合として定義される。E[κ]は、Eの部分群である。
GT：有限体FTを基礎体とする拡大体である有限集合。その一例は、有限体FTの代数閉包における１のκ乗根からなる有限集合である。
e：非退化双線形ペアリング（pairing）関数（以下「ペアリング関数」と呼ぶ）であり、以下の式で定義される。
G×G=GT  …(2)
【００２３】
本形態で使用するペアリング関数eは次の性質を持つ。
［性質１］G上の任意の点A1に対して、e(A1,A1)=1が成り立つ。
［性質２］G上の任意の２点A1,A2に対して、e(A1,A2)=e(A2,A1)が成り立つ。
［性質３］G上の任意の３点A1,A2,A3に対して、e(A1+A2,A3)=e(A1,A3)e(A2,A3)であり、e(A1,A2+A3)=e(A1,A2)e(A1,A3)が成り立つ。
［性質４］G上の任意の点A1に対して、e(A1,O)=1が成り立つ。
［性質５］G上のある点A1がG上のすべての点Ａ２に対して、e(A1,A2)=1を満たすなら、A1=Oが成り立つ。
【００２４】
なお、このようなペアリング関数ｅの具体例としては、例えば、参考文献２「"IEEE P1636.3TM/D1 Draft Standard for Identity-based Public-key Cryptography Using Pairings", [URL: http://grouper.ieee.org/groups/1363/IBC/material/P1363.3-D1-200805.pdf], pp.24-25, April 2008」に開示された関数e(A1,φ(A2))を例示できる。参考文献２にあるように、この関数は、ＷｅｉｌペアリングやＴａｔｅペアリングなどの関数に写像φを組み合わせたもので実現できる。ここで、写像φは以下のようになる。
【００２５】
φ(x,y) = (v-1x,v-3/2y)（楕円曲線Eが２次のツイストを持つ場合）
φ(x,y) = (v-1/3x,v-1/2y)（楕円曲線Eが４又は６次のツイストを持つ場合）
ただし、vは有限体ＦTの平方非剰余な元v∈ＦTである。また、ＷｅｉｌペアリングやＴａｔｅペアリングについては、例えば、参考文献３「Alfred. J. Menezes，ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS， ISBN0-7923-9368-6，pp. 61-81」等に開示されている。また、ペアリング関数が効率的に計算可能な非超特異楕円曲線（non-supersingular curve）の生成方法については、参考文献４「A. Miyaji, M. Nakabayashi, S.Takano, "New explicit conditions of elliptic curve Traces for FR-Reduction," IEICE Trans. Fundamentals, vol. E84-A, no05, pp. 1234-1243, May 2001」、参考文献５「P.S.L.M. Barreto, B. Lynn, M. Scott, "Constructing elliptic curves with prescribed embedding degrees," Proc. SCN '2002, LNCS 2576, pp.257-267, Springer-Verlag. 2003」などに開示されている。また、ペアリング関数をコンピュータ上で計算するためのアルゴリズムとしては、周知のMiller のアルゴリズム（参考文献６「V. S. Miller, “Short Programs for functions on Curves,” 1986，インターネット＜http://crypto.stanford.edu/miller/miller.pdf＞」などが存在する。
【００２６】
階層型ＩＤベース暗号方式（Hierarchical Identity-Based Encryption）：ＩＤベース暗号方式のＩＤを階層化し、階層化された各ＩＤが階層化された各装置に対応させ、各装置の秘密鍵を階層的に生成できるＩＤベース暗号方式。この方式では、マスター秘密鍵を利用可能な装置が、マスター秘密鍵と各ＩＤとを用い、各ＩＤに対応する秘密鍵を生成でき、マスター秘密鍵を利用できない装置であっても、上位層のＩＤに対して生成された秘密鍵とその下位層のＩＤとを用い、当該下位層のＩＤに対応する秘密鍵を生成できる。また、この方式では、マスター秘密鍵を利用できない装置が、下位層のＩＤに対して生成された秘密鍵とその上位層のＩＤとを用い、当該上位層のＩＤに対応する秘密鍵を生成することはできない。階層型ＩＤベース暗号の具体的な構成は、様々な文献に開示されており、例えば、参考文献７「C. Gentry, A. Silverberg, "Hierarchical ID-based cryptography," Proceedings of ASIACRYPT 2002, Lecture Notes in Computer Science, Springer-Verlag, 2002.」、参考文献８「Dan Boneh, Xavier Boyen, and Eu-Jin Goh, "Hierarchical identity based encryption with constant size ciphertext," Proceedings of Eurocrypt 2005, volume 3494 of LNCS, pages 440-456.」、参考文献９「Xavier Boyen and Brent Waters, "Anonymous Hierarchical Identity-Based Encryption," Proceedings of CRYPTO 2006, volume 4117 of LNCS.」、参考文献１０「Le Trieu Phong, Wakaha Ogata, "Blind HIBE and its Application to Blind Decryption," SCIS 2008, Jan. 2008.」などに開示されている。なお、ＩＤベース暗号については、例えば、参考文献１１「D. Boneh and M. Franklin, "Identify-based encryption from the Weil pairing", Advances in Cryptology 0 CRYTPO '01, volume 2139 of LNCS, pages 213-229. Springer, 2001.」などに開示されている。
【００２７】
Z：整数集合。なお、ε∈Zは、εが整数集合Zの元であることを示す。
Zκ：κを法とする剰余類（=Z/κZ）。本実施形態では、その代表元をZκと表現する。また、代表元の一例は、0以上κ-1以下の整数である。なお、ε∈Zκは、εが集合Zκの元であることを示す。
p, q：p, qは互いに相違する素数であり、κ=p・qを満たす。
Gp,Gq：GpはGの部分群であり、その位数はpである。Gの生成元をΦ∈Gとすると、部分群Gpの生成元はΦp∈Gとなる。また、GqはGの部分群であり、その位数はqである。Gの生成元をΦ∈Gとすると、部分群Gqの生成元はΦｑ∈Gとなる。なお、ε・η∈Gは、Gの元εとηとに対し、Gで定義された演算を行うことを意味する。また、εν∈G（ν∈Z）は、Gの元εに対し、Gで定義された演算をν回行うこと（ε・ε...ε・ε∈G）を意味する。本形態のGは、楕円曲線E上の有理点からなる有限集合の部分群であるため、ε・η∈Gは楕円曲線Ｅ上での点εとηとの楕円加算に相当し、εν∈Gは楕円曲線Ｅ上での点εの楕円スカラー倍算（ν倍算）に相当する。
【００２８】
また、すべての任意の点hp∈Gp，hq∈Gqに対してe(hp,hq)=1が成り立つ（［性質６］）。なぜなら、整数a,b∈Zに対してe(hp,hq)=e(Φpa,Φqb)が成り立ち、［性質１］［性質３］からe(Φpa,Φqb)=e(Φ,Φ)pqab＝1pqab=1が成り立つからである。
【００２９】
〔構成〕
図１は、本形態の検索システム１の全体構成を説明するための構成図である。図２は、図１に例示したデータベース装置１０の詳細構成を説明するための機能ブロック図である。図３は、図１に例示した端末装置（TA1）２０−１の機能構成を説明するための機能ブロック図である。図４は、図３の秘密鍵生成部（SKG1）２８−１の詳細構成の一例を説明するための機能ブロック図であり、図５は、図３の検索トークン生成部(TKG1)２９−１ の詳細構成の一例を説明するための機能ブロック図である。また、図６は、図１に例示した端末装置（TAk）２０−ｋ（k=2,...,N）の機能構成を説明するための機能ブロック図である。なお、Ｎは総階層数を示す２以上の整数である。図７は、図６の秘密鍵生成部(SKGk)２８−ｋの詳細構成の一例を説明するための機能ブロック図であり、図８は、図６の検索トークン生成部(TKGk)２９−ｋの詳細構成の一例を説明するための機能ブロック図である。また、図９は、図１に例示した端末装置（TAN）２０−Ｎの機能構成を説明するための機能ブロック図である。
【００３０】
図１に示すように、本形態の検索システム１は、データベース装置１０と、N個（N≧2）の端末装置（TAn）２０−ｎ（n=1,...,N）とを有する。これらはネットワークを通じて通信可能に構成される。ここで、データベース装置１０は、例えば、ＣＰＵ（central processing unit）、ＲＡＭ（random-access memory）、磁気記録装置、光磁気記録媒体、通信装置等を備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される装置である。また、端末装置（TAn）２０−ｎは、例えば、ＣＰＵ、ＲＡＭ、磁気記録装置、光磁気記録媒体、通信装置、液晶ディスプレイ、キーボード等を備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される装置である。
【００３１】
図２に例示するように、本形態のデータベース装置１０は、制御部１１と、一時メモリ１２と、後述する暗号化データベースを格納した記憶部（STRDB）１３と、送信部１４と、受信部１５と、検索部１６とを有する。また、検索部１６は、復号部１６ａと判定部１６ｂと抽出部１６ｃとを有する。なお、制御部１１と検索部１６は、例えば、ＣＰＵに所定のプログラムが読み込まれて構成される処理部であり、一時メモリ１２と記憶部（STRDB）１３は、例えば、ＲＡＭ、磁気記録装置、光磁気記録媒体やそれらの少なくとも一部の結合によって構成される記憶領域である。また、送信部１４と受信部１５は、例えば、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動する通信装置である。なお、データベース装置１０は、制御部１１の制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ１２に格納され、その他の演算処理の際に読み出されて利用される。
【００３２】
図３に例示するように、本形態の端末装置（TA1）２０−１は、制御部２１−１と、一時メモリ２２−１と、記憶部（STR1）２３−１と、送信部２４−１と、受信部２５−１と、入力インタフェース部２６−１と、出力インタフェース部２７−１と、秘密鍵生成部（SKG1）２８−１と、検索トークン生成部（TKG1）２９−１とを有する。また、図４の例の秘密鍵生成部（SKG1）２８−１は、ランダム値生成部２８ａ−１と、鍵生成部２８ｂ−１と、引継ぎ情報生成部２８ｃ−１とを有する。ここで、鍵生成部２８ｂ−１は、演算部２８ｂａ−１〜２８ｂｄ−１を有し、引継ぎ情報生成部２８ｃ−１は、演算部２８ｃａ−１〜２８ｃｈ−１を有する。また、図５の例の検索トークン生成部（TKG1）２９−１は、ランダム値生成部２９ａ−１と、検索トークン演算部２９ｂ−１とを有する。ここで、検索トークン演算部２９ｂ−１は、演算部２９ｂａ−１〜２９ｂｃ−１を有する。なお、制御部２１−１と秘密鍵生成部（SKG1）２８−１と検索トークン生成部（TKG1）２９−１は、ＣＰＵに所定のプログラムが読み込まれて構成される処理部であり、一時メモリ２２−１と記憶部（STR1）２３−１とは、例えば、ＲＡＭ、磁気記録装置、光磁気記録媒体やそれらの少なくとも一部の結合によって構成される記憶領域である。また、送信部２４−１と受信部２５−１は、例えば、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動する通信装置である。また、入力インタフェース部２６−１や出力インタフェース部２７−１は、例えば、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するキーボードや液晶ディスプレイである。なお、端末装置（TA1）２０−１は、制御部２１−１の制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ２２−１に格納され、その他の演算処理の際に読み出されて利用される。
【００３３】
図６に例示するように、本形態の端末装置（TAk）２０−ｋは、制御部２１−ｋと、一時メモリ２２−ｋと、記憶部（STRk）２３−ｋと、送信部２４−ｋと、受信部２５−ｋと、入力インタフェース部２６−ｋと、出力インタフェース部２７−ｋと、秘密鍵生成部（SKGk）２８−ｋと、検索トークン生成部（TKGk）２９−ｋとを有する。また、図７の例の秘密鍵生成部（SKGk）２８−ｋは、ランダム値生成部２８ａ−ｋと、鍵生成部２８ｂ−ｋと、引継ぎ情報生成部２８ｃ−ｋと、演算制御部２８ｄ−ｋとを有する。ここで、鍵生成部２８ｂ−ｋは、演算部２８ｂａ−ｋ〜２８ｂｄ−ｋを有し、引継ぎ情報生成部２８ｃ−ｋは、演算部２８ｃａ−ｋ〜２８ｃｈ−ｋを有する。また、図８の例の検索トークン生成部（TKGk）２９−ｋは、ランダム値生成部２９ａ−ｋと、検索トークン演算部２９ｂ−ｋと、加算部２９ｄ−ｋとを有する。ここで、検索トークン演算部２９ｂ−ｋは、演算部２９ｂａ−ｋ〜２９ｂｃ−ｋを有する。なお、制御部２１−ｋと秘密鍵生成部（SKGk）２８−ｋと検索トークン生成部（TKGk）２９−ｋは、ＣＰＵに所定のプログラムが読み込まれて構成される処理部であり、一時メモリ２２−ｋと記憶部（STRk）２３−ｋとは、例えば、ＲＡＭ、磁気記録装置、光磁気記録媒体やそれらの少なくとも一部の結合によって構成される記憶領域である。また、送信部２４−ｋと受信部２５−ｋは、例えば、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動する通信装置である。また、入力インタフェース部２６−ｋや出力インタフェース部２７−ｋは、例えば、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するキーボードや液晶ディスプレイである。なお、端末装置（TAk）２０−ｋは、制御部２１−ｋの制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ２２−ｋに格納され、その他の演算処理の際に読み出されて利用される。
【００３４】
図９に例示するように、本形態の端末装置（TAN）２０−Ｎは、制御部２１−Ｎと、一時メモリ２２−Ｎと、記憶部（STRN）２３−Ｎと、送信部２４−Ｎと、受信部２５−Ｎと、入力インタフェース部２６−Ｎと、出力インタフェース部２７−Ｎと、秘密鍵生成部（SKGN）２８−Ｎとを有する。なお、制御部２１−Ｎと検索トークン生成部（TKGN）２９−Ｎは、ＣＰＵに所定のプログラムが読み込まれて構成される処理部であり、一時メモリ２２−Ｎと記憶部（STRN）２３−Ｎとは、例えば、ＲＡＭ、磁気記録装置、光磁気記録媒体やそれらの少なくとも一部の結合によって構成される記憶領域である。また、送信部２４−Ｎと受信部２５−Ｎは、例えば、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動する通信装置である。また、入力インタフェース部２６−Ｎや出力インタフェース部２７−Ｎは、例えば、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するキーボードや液晶ディスプレイである。なお、端末装置（TAN）２０−Ｎは、制御部２１−Ｎの制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ２２−Ｎに格納され、その他の演算処理の際に読み出されて利用される。
【００３５】
＜処理＞
次に、本形態の処理を説明する。以下に説明するように、本形態では階層型ＩＤベース暗号方式を利用して検索権限が設定された暗号化データベースの検索処理を実現する。これらの処理に利用する階層型ＩＤベース暗号方式は、前述した参考文献７〜１０などの公知の方式であってもよいが、以下では独自の階層型ＩＤベース暗号方式を利用する例を説明する。
【００３６】
［前処理］
各端末装置（TAn）２０−ｎには、それぞれ、データベース装置１０の記憶部１３に格納された暗号化データベースに対する検索権限を示す検索権限レベルが設定され、設定された検索権限レベルを示すレベル識別子LVIDnが対応付けられている。ここで、暗号化データベースに対する検索権限とは、暗号化データベースが具備するデータ集合のうち、キーワード検索を行うことが許可されたデータの範囲を意味する。また、検索権限を示す検索権限レベルLVIDnが高いとは、暗号化データベースに属するデータ集合のうち、検索可能なデータの数が多いことを意味する。すなわち、設定された検索権限レベルが高い端末装置ほど、暗号化データベース内の多くのデータを検索することができる。また、本形態では、レベル識別子LVID1が最も高い検索権限に対応し、ｎの値が大きいレベル識別子LVIDnほど低い検索権限に対応するものとする。また、各レベル識別子LVIDk（k=2,...,N）は、例えば、ｋ個の要素I1,...,Ikの集合LVIDk=[I1,...,Ik]であり、各レベル識別子LVIDk-1=[I1,...,Ik-1]は、レベル識別子LVIDk=[I1,...,Ik]の部分集合となっている。
【００３７】
図１，２に例示するように、本形態のデータベース装置１０の記憶部１３に格納された暗号化データベースでは、各検索対象情報A,...,Bの各暗号文ENC(A),...,ENC(Z)と、当該検索対象情報A,...,Bにそれぞれ対応し得るキーワードKW1,...,KW9及び何れかの端末装置（TAn）２０−ｎに対応するレベル識別子LVIDnの組をＩＤとし、階層型ＩＤベース暗号方式の暗号化手順に従って、各キーワードKW1,...,KW9が検索対象情報A,...,Bに対応するか否かを示すビット情報"1"や"0"（キーワードが対応する＝"1"、キーワードが対応しない＝"0"）を暗号化した階層型ＩＤベース暗号方式の各暗号文である暗号化キーワードHIBE(LVIDn,KW*,"*")と、が対応付けられている。このようなデータ構成により、本形態の暗号化データベースでは、検索対象情報の暗号文と、当該検索対象情報に対応するキーワード及び何れかの端末装置TAnに対応するレベル識別子LVIDnの組をＩＤとした階層型ＩＤベース暗号方式の暗号文である暗号化キーワードとが対応付けられている。
【００３８】
例えば、図１，２の例では、暗号文ENC(A)に暗号化キーワードHIBE(LVID1,KW1,"1"),...,HIBE(LVID1,KW9,"0")が対応付けられ、暗号文ENC(B)に暗号化キーワードHIBE(LVID2,KW1,"1"),...,HIBE(LVID2,KW9,"1")が対応付けられ、・・・暗号文ENC(Z)に暗号化キーワードHIBE(LVIDN,KW1,"1"),...,HIBE(LVIDN,KW9,"1")が対応付けられている。ここで、例えば、暗号文ENC(A)に暗号化キーワードHIBE(LVID1,KW1,"1")が対応付けられていることは、検索対象情報AがキーワードKW1に対応することを意味し、暗号文ENC(A)に暗号化キーワードHIBE(LVID1,KW9,"0")が対応付けられていることは、検索対象情報AがキーワードKW9に対応しないことを意味する。しかし、暗号化キーワードHIBE(LVID1,KW1,"1")やHIBE(LVID1,KW9,"0")を復号できないデータベース装置１０などは、暗号化キーワードHIBE(LVID1,KW1,"1")が"1"の暗号文であり、暗号化キーワードHIBE(LVID1,KW9,"0")が"0"の暗号文であることが分からないため、検索対象情報AがキーワードKW1やKW9に対応するか否かを知ることができない。
【００３９】
また、各暗号文ENC(A),...,ENC(Z)に対応付けられる暗号化キーワードは、その順序がランダム化されていることが望ましい。すなわち、各暗号化キーワードの格納位置からその暗号化キーワードがどのキーワードに対応するのかが分からないデータ構成であることが望ましい。より好ましくは、さらに、本形態で利用する階層型ＩＤベース暗号方式が、当該階層型ＩＤベース暗号方式に従って生成された暗号文から当該暗号文に対応するＩＤを特定することが困難な匿名階層型ＩＤベース暗号方式であることが望ましい。これにより、各暗号化キーワードに対応するキーワードが知られることを防止できる。このような匿名階層型ＩＤベース暗号方式の例は、参考文献９の方式や、本形態で具体的に処理を例示する方式である。
【００４０】
また、各検索対象情報A,...,Bの各暗号文ENC(A),...,ENC(Z)の暗号化は、公知の公開鍵暗号方式や共通鍵暗号方式やＩＤベース暗号方式を用い、各検索対象情報A,...,Bを利用する端末装置（TAn）２０−ｎなどの装置が復号できるように行われればよい。
【００４１】
また、最も高い検索権限レベルが設定された端末装置（TA1）２０−１の記憶部（STR1）２３−１には、階層型ＩＤベース暗号方式の秘密鍵を生成するためのマスター秘密鍵MKと、端末装置（TA1）２０−１に対応するレベル識別子LVID1と、端末装置（TA1）２０−１よりも低い検索権限レベルが設定された端末装置（TAm）２０−ｍ（m=2,...,N）に対応するレベル識別子LVIDmとが格納される（図３）。この格納は前処理の段階でなされていてもよいし、それ以降になされてもよい。
【００４２】
また、端末装置（TA1）２０−１よりも低い検索権限レベルが設定された端末装置（TAk）２０−ｋ（k=2,...,N）の記憶部（STRk）２３−ｋには、自らよりも高い検索権限レベルが設定された端末装置（TA1）２０−１,...,端末装置（TA k-1）２０−（ｋ−１）の何れかがレベル識別子LVIDkを用いて生成した端末装置（TAk）２０−ｋの秘密鍵SKkと、自らよりも低い検索権限レベルが設定された端末装置（TAu）２０−ｕ（u=k+1,...,N）に対応するレベル識別子LVIDuとが格納される（図６，図９）。この格納は前処理の段階でなされていてもよいし、後述の秘密鍵生成時点以降になされてもよい。この格納は前処理の段階でなされていてもよいし、それ以降になされてもよい。
【００４３】
また、最も高い検索権限レベルが設定された端末装置（TA1）２０−１（図３）は、自らよりも低い検索権限レベルが設定されたすべての端末装置（TAm）２０−ｍに対応する各秘密鍵SKmを生成できる。この場合、まず、端末装置（TA1）２０−１の秘密鍵生成部（SKG1）２８−１が、記憶部（STR1）２３−１から、マスター秘密鍵MKと、秘密鍵を生成する端末装置（TAm）２０−ｍに対応するレベル識別子LVIDmとを読み込む。次に、秘密鍵生成部（SKG1）２８−１は、階層型ＩＤベース暗号方式の鍵生成手順に従って、当該レベル識別子LVIDmをＩＤとする階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を端末装置（TAm）２０−ｍの秘密鍵SKmとして出力する。出力された端末装置（TAm）２０−ｍの秘密鍵SKmは送信部２４−１に送られ、そこから端末装置（TAm）２０−ｍに送信され、端末装置（TAm）２０−ｍの記憶部（STRm）２３−ｍに格納される。
【００４４】
端末装置（TA1）２０−１よりも低い検索権限レベルが設定された端末装置（TAk）２０−ｋ（図６）は、自らよりも高い検索権限レベルが設定された端末装置（TA1）２０−１,...,端末装置（TA k-1）２０−（ｋ−１）の何れかがレベル識別子LVIDkを用いて生成した端末装置（TAk）２０−ｋの秘密鍵SKkと、自らよりも低い検索権限レベルが設定された端末装置（TAu）２０−ｕ（u=k+1,...,N）に対応するレベル識別子LVIDuとを用い、端末装置（TAu）２０−ｕに対応する秘密鍵SKuを生成できる。この場合、まず、端末装置（TAk）２０−ｋの秘密鍵生成部（SKGk）２８−ｋが、記憶部（STRk）２３−ｋから、秘密鍵SKkと、秘密鍵を生成する端末装置（TAu）２０−ｕに対応するレベル識別子LVIDuとを読み込む。次に、秘密鍵生成部（SKGk）２８−ｋは、階層型ＩＤベース暗号方式の鍵生成手順に従って、レベル識別子LVIDuをＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を端末装置（TAu）２０−ｕの秘密鍵SKuとして出力する。出力された端末装置（TAu）２０−ｕの秘密鍵SKuは送信部２４−ｋに送られ、そこから端末装置（TAu）２０−ｕに送信され、端末装置（TAu）２０−ｕの記憶部（STRu）２３−ｕに格納される。
【００４５】
［前処理の具体例］
前処理の具体例を示す。なお、この具体例は本発明を限定するものではない。
《セッティング》
まず、以下のように元を設定する。
g,f,v,h1,...,hN+1,ω∈Gp     …(3)
Rg,Rf,Rv,R1,...,RN+1,gq∈Gq    …(4)
【００４６】
次に、以下のように公開パラメータPを設定する。公開パラメータPは公開され、データベース装置１０の暗号化データベースの作成時に利用される。
P=[gq,η=g・Rg∈G, F=f・Rf∈G, V=v・Rv∈G, H1=h1・R1∈G,...,HN+1=hN+1・RN+1∈G, ζ=e(g,ω)]   …(5)
次に、以下のようにマスター秘密鍵MKを設定する。マスター秘密鍵MKは、最も高い検索権限レベルが設定された端末装置（TA1）２０−１（図３）の記憶部（STR1）２３−１に格納される。
MK=[g,f,v,h1,...,hN+1,ω]   …(6)
【００４７】
《暗号化データベースの生成》
I1,...,In∈Zκからなるレベル識別子LVIDn=[I1,...,In]∈(Zκ)nと、検索用のキーワードKW*=In+1∈Zκと、Msg="1"or"0"とに対応する暗号化キーワードHIBE(LVIDn,In+1,Msg)は以下のように生成される。ただし、s,z1,z2,z3は、ランダム値s∈Zκ，z1,z2,z3∈Gpである。
【００４８】
【数１】
2010160235.tif 000003
このように生成された各暗号化キーワードHIBE(LVIDn,In+1,Msg)は、前述のように対応する暗号文ENC(*)に対応付けられ、これにより暗号化データベースが構成される。
【００４９】
《端末装置（TA1）２０−１の秘密鍵の生成》
図１１は、端末装置（TA1）２０−１の秘密鍵生成部(SKG1)２８−１（図４）が行う秘密鍵の生成方法の一例を説明するためのフローチャートである。以下、この図を用い、端末装置（TA1）２０−１が行う秘密鍵の生成方法を例示する。
【００５０】
まず、端末装置（TA1）２０−１の秘密鍵生成部（SKG1）２８−１が、記憶部（STR1）２３−１から、マスター秘密鍵MK=[g,f,v,h1,...,hN+1,ω]と、秘密鍵を生成する端末装置（TAm）２０−ｍに対応するレベル識別子LVIDm=[I1,...,Im]とを読み込む（ステップＳ１１）。次に、ランダム値生成部２８ａ−１が、ランダム値r1,r2,s1.s2,t1,t2∈Zκを生成して出力する（ステップＳ１２）。なお、この処理はs1・t2+s2・t1≡0 mod pとならないように行われる。すなわち、選択したランダム値がs1・t2+s2・t1≡0 mod pとなった場合には、ステップＳ１２の処理をやり直す。
【００５１】
次に、演算部２８ｂａ−１が、
【数２】
2010160235.tif 000004
の演算を行い（ステップＳ１３）、演算部２８ｂｂ−１，２８ｂｃ−１が、それぞれ、
【００５２】
【数３】
2010160235.tif 000005
の演算を行う（ステップＳ１５）。これらにより、鍵生成部２８ｂ−１は、
【００５３】
【数４】
2010160235.tif 000006
を生成する。
【００５４】
次に、演算部２８ｃａ−１が、
【数５】
2010160235.tif 000007
の演算を行い（ステップＳ１６）、演算部２８ｃｂ−１，２８ｃｃ−１が、それぞれ、
【００５５】
【数６】
2010160235.tif 000008
の演算を行い（ステップＳ１７）、演算部２８ｃｄ−１が、
【００５６】
【数７】
2010160235.tif 000009
の演算を行う（ステップＳ１８）。さらに、演算部２８ｃｅ−１が、
【００５７】
【数８】
2010160235.tif 000010
の演算を行い（ステップＳ１９）、演算部２８ｃｆ−１，２８ｃｇ−１が、それぞれ、
【００５８】
【数９】
2010160235.tif 000011
の演算を行い（ステップＳ２０）、演算部２８ｃｈ−１が、
【００５９】
【数１０】
2010160235.tif 000012
の演算を行う（ステップＳ２１）。これらにより、引継ぎ情報生成部２８ｃ−１は、
【００６０】
【数１１】
2010160235.tif 000013
を生成する。そして、秘密鍵生成部(SKG1)２８−１は、
秘密鍵SKm=[PvKd(LVIDm), PvKr(LVIDm)]     …(22)
を出力する（ステップＳ２２）。
【００６１】
《端末装置（TAk）２０−ｋ（k=2,...,N）の秘密鍵の生成》
図１３及び図１４は、端末装置（TAk）２０−ｋの秘密鍵生成部(SKGk) ２８−ｋ（図７）が行う秘密鍵の生成方法の一例を説明するためのフローチャートである。以下、この図を用い、端末装置（TAk）２０−ｋが行う秘密鍵の生成方法を例示する。
【００６２】
まず、端末装置（TAk）２０−ｋの秘密鍵生成部（SKGk）２８−ｋが、記憶部（STRk）２３−ｋから、秘密鍵SKk=[PvKd(LVIDk), PvKr(LVIDk)]と、秘密鍵を生成する端末装置（TAu）２０−ｕに対応するu及びレベル識別子LVIDu=[I1,...,Iu]を読み込む（ステップＳ４１）。なお、以下では、秘密鍵SKk=[PvKd(LVIDk), PvKr(LVIDk)]=[[a0,a1,a2,bk+1,...,bN],[[α0,α1,α2,βk+1,...,βN],[A0,A1,A2,Bk+1,...,BN]]]として各演算を表現する。
【００６３】
次に、演算制御部２８ｄ−ｋがw=k+1としてwを出力する（ステップＳ４２）。次に、ランダム値生成部２８ａ−ｋが、ランダム値γ1, γ2, γ3,δ1, δ2, δ3∈Zκを生成して出力する（ステップＳ４３）。なお、この処理はγ2・δ3+γ3・δ2≡0∈Zκとならないように行われる。すなわち、選択したランダム値がγ2・δ3+γ3・δ2≡0∈Zκとなった場合には、ステップＳ４２の処理をやり直す。
【００６４】
次に、演算部２８ｂａ−ｋが、
【数１２】
2010160235.tif 000014
の演算を行い（ステップＳ４４）、演算部２８ｂｂ−ｋが、
【００６５】
【数１３】
2010160235.tif 000015
の演算を行い（ステップＳ４５）、演算部２８ｂｃ−ｋが、
【００６６】
【数１４】
2010160235.tif 000016
の演算を行い（ステップＳ４６）、演算部２８ｂｄ−ｋが、
【００６７】
【数１５】
2010160235.tif 000017
の演算を行う（ステップＳ４７）。これらにより、鍵生成部２８ｂ−ｋは、
【００６８】
【数１６】
2010160235.tif 000018
を生成する。次に、演算部２８ｃａ−ｋが、
【００６９】
【数１７】
2010160235.tif 000019
の演算を行い（ステップＳ４８）、演算部２８ｃｂ−ｋ，２８ｃｃ−ｋが、それぞれ、
【００７０】
【数１８】
2010160235.tif 000020
の演算を行い（ステップＳ４９，Ｓ５０）、演算部２８ｃｄ−ｋが、
【００７１】
【数１９】
2010160235.tif 000021
の演算を行う（ステップＳ５１）。また、演算部２８ｃｅ−ｋが、
【００７２】
【数２０】
2010160235.tif 000022
の演算を行い（ステップＳ５２）、演算部２８ｃｆ−ｋ，２８ｃｇ−ｋが、それぞれ、
【００７３】
【数２１】
2010160235.tif 000023
の演算を行い（ステップＳ５３，Ｓ５４）、演算部２８ｃｈ−ｋが、
【００７４】
【数２２】
2010160235.tif 000024
の演算を行う（ステップＳ５５）。これらにより、引継ぎ情報生成部２８ｃ−ｋは、
【００７５】
【数２３】
2010160235.tif 000025
を生成する。
【００７６】
次に、演算制御部２８ｄ−ｋがw=uであるか否かを判定する（ステップＳ５６）。ここで、w=uでないと判定された場合、演算制御部２８ｄ−ｋがSKw=[PvKd(LVIDw), PvKr(LVIDw)]=[PvKd(LVIDk), PvKr(LVIDk)]=[[a0,a1,a2,bk+1,...,bN],[[α0,α1,α2,βk+1,...,βN],[A0,A1,A2,Bk+1,...,BN]]]と設定し（ステップＳ５７）、w+1を新たなwとして出力して（ステップＳ５８）、処理をステップＳ４３に戻す。一方、ステップＳ５６でw=uであると判定された場合、秘密鍵生成部２８−ｋは、端末装置（TAu）２０−ｕに対応する秘密鍵SKu=SKwを出力する（ステップＳ５９）。
【００７７】
［検索処理］
図１０は、各端末装置（TAn）２０−ｎがデータベース装置１０の暗号化データベースの検索を依頼し、その検索結果を受け取る検索処理を説明するためのフローチャートである。以下、この図を用いて本形態の検索処理を説明する。
【００７８】
各端末装置は、データベース装置１０の暗号化データベースを構成する暗号文ENC(A),...,ENC(Z)のうち、自らに設定されたレベル識別子に対応する暗号化キーワードに対応付けられた暗号文ENC(*)、及び自らのレベル識別子よりも低い検索レベルのレベル識別子に対応する暗号化キーワードに対応付けられた暗号文ENC(*)を検索できる。
【００７９】
《端末装置（TA1）２０−１が何れかのレベル識別子LVIDnに対応する検索処理を依頼する場合》
まず、端末装置（TA1）２０−１（図３）の入力インタフェース部２６−１に検索用のキーワードKW*が入力され、記憶部（STR1）２３−１に格納される（ステップＳ１）。次に、検索トークン生成部（TKG1）２９−１が、記憶部（STR1）２３−１から、マスター秘密鍵MKと、何れかの端末装置（TAn）２０−ｎに対応するレベル識別子LVIDnと、検索用のキーワードKW*とを読み込む。トークン生成部（TKG1）２９−１は、これらを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、レベル識別子LVIDnと当該キーワードKW*との組をＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を検索トークンST(LVIDn,KW*)として出力する（ステップＳ２）。出力された検索トークンST(LVIDn,KW*)は送信部２４−１に送られ、送信部２４−１は、この検索トークンST(LVIDn,KW*)をデータベース装置１０に送信する（ステップＳ３）。
【００８０】
送信された検索トークンST(LVIDn,KW*)は、データベース装置１０（図２）の受信部１５で受信され（ステップＳ４）、検索部１６に送られる。検索部１６は、検索トークンST(LVIDn,KW*)を秘密鍵として用い、階層型ＩＤベース暗号方式の復号手順に従った復号処理を行い、記憶部（STRDB）１３の暗号化データベースに格納された各暗号化キーワードHIBE (LVID*, KW*, “*”)
の復号結果を検証する（ステップＳ５）。例えば、検索部１６の復号部１６ａが、検索トークンST(LVIDn,KW*)を秘密鍵として用い、階層型ＩＤベース暗号方式の復号手順に従って、暗号化データベースに格納された各暗号化キーワードHIBE (LVID*, KW*, “*”)を復号し、判定部１６ｂが、各復号結果が"1"となったか否かを判定する。ここで、検索トークンST(LVIDn,KW*)に対応するレベル識別子LVIDnとキーワードKW*との両方が、各暗号化キーワードHIBE (LVID*, KW*, “*”)に対応するレベル識別子LVID*とキーワードKW*とに一致する場合には、各暗号化キーワードHIBE (LVID*, KW*, “*”)が正しく復号され、復号結果として"1"又は"0"が得られる。一方、検索トークンST(LVIDn,KW*)に対応するレベル識別子LVIDnとキーワードKW*との何れか一方が、各暗号化キーワードHIBE (LVID*, KW*, “*”)に対応するレベル識別子LVID*とキーワードKW*とに一致しない場合には、各暗号化キーワードHIBE (LVID*, KW*, “*”)が正しく復号されず、復号関数はエラーを返す。
【００８１】
抽出部１６ｃは、判定部１６ｂで復号結果が"1"と判定された暗号化キーワードHIBE (LVID*, KW*, “*”)に対応付けられた暗号文ENC(*)をそれぞれ抽出し、送信部１４に送る（ステップＳ６）。送信部１４は、抽出された各暗号文ENC(*)を端末装置（TA1）２０−１に送信し（ステップＳ７）、端末装置（TA1）２０−１の受信部２５−１で受信されて記憶部（STR1）２３−１に格納される（ステップＳ８）。その後、端末装置（TA1）２０−１は、必要に応じ、記憶部（STR1）２３−１に格納された各暗号文ENC(*)を復号し、検索対象情報を抽出する。
【００８２】
《端末装置（TAk）２０−ｋがレベル識別子LVIDk又はそれよりも検索権限が低いレベル識別子LVIDuに対応する検索処理を依頼する場合》
まず、端末装置（TAk）２０−ｋ（図６，図９）の入力インタフェース部２６−ｋに検索用のキーワードKW*と、検索を行う検索権限に対応するレベル識別子LVIDk又はLVIDu
に対応するk又はuが入力され、記憶部（STRk）２３−ｋに格納される（ステップＳ１）。次に、検索トークン生成部（TKGk）２９−ｋが、記憶部（STRk）２３−ｋから、検索用のキーワードKW*と、ステップＳ１で入力されたk又はuとを読み込み、ステップＳ１でkが入力された場合には、記憶部（STRk）２３−ｋからさらに秘密鍵SKkを読み込み、ステップＳ１でuが入力された場合には、秘密鍵生成部（SKGk）２８−ｋで生成された秘密鍵SKuが入力される。トークン生成部（TKGk）２９−ｋは、これらを用い、階層型ＩＤベース暗号方式の鍵生成手順に従って、レベル識別子LVIDkと当該キーワードKW*との組又はレベル識別子LVIDuと当該キーワードKW*との組をＩＤとした階層型ＩＤベース暗号方式の秘密鍵を生成し、当該秘密鍵を検索トークンST(LVIDk,KW*)又はST(LVIDu,KW*)として出力する（ステップＳ２）。出力された検索トークンST(LVIDk,KW*)又はST(LVIDu,KW*)は送信部２４−ｋに送られ、送信部２４−ｋは、この検索トークンST(LVIDk,KW*)又はST(LVIDu,KW*)をデータベース装置１０に送信する（ステップＳ３）。その後の処理は、上述した端末装置（TA1）２０−１が検索を依頼する場合と同様である。
【００８３】
《ステップＳ２の具体例》
図１２は、端末装置（TA1）２０−１（図３）が何れかのレベル識別子LVIDnに対応する検索処理を依頼する場合のステップＳ２の具体例を説明するためのフローチャートである。
【００８４】
この場合、まず、検索トークン生成部（TKG1）２９−１が、記憶部（STR1）２３−１から、マスター秘密鍵MK=[g,f,v,h1,...,hN+1,ω]と、何れかの端末装置（TAn）２０−ｎに対応するレベル識別子LVIDn=[I1,...,Im]と、検索用のキーワードKW*=In+1∈Zκとを読み込む（ステップＳ３１）。次に、ランダム値生成部２９ａ−１が、ランダム値r1,r2∈Zκを生成して出力する（ステップＳ３２）。次に、演算部２９ｂａ−１が、
【００８５】
【数２４】
2010160235.tif 000026
の演算を行い（ステップＳ３３）、演算部２９ｂｂ−１，２９ｂｃ−１が、それぞれ、
【００８６】
【数２５】
2010160235.tif 000027
の演算を行う（ステップＳ３４）。そして、検索トークン生成部（TKG1）２９−１は、検索トークン
【００８７】
【数２６】
2010160235.tif 000028
を出力する（ステップＳ３５）。
【００８８】
図１５は、端末装置（TAk）２０−ｋ（図６）がレベル識別子LVIDk又はそれよりも検索権限が低いレベル識別子LVIDuに対応する検索処理を依頼する場合のステップＳ２の具体例を説明するためのフローチャートである。
【００８９】
この場合、まず、検索トークン生成部（TKGk）２９−ｋ（図８）が、記憶部（STRk）２３−ｋから、検索用のキーワードKW*=Iwと、ステップＳ１で入力されたk又はuとを読み込み、ステップＳ１でkが入力された場合には、記憶部（STRk）２３−ｋからさらに秘密鍵SKkを読み込み、ステップＳ１でuが入力された場合には、秘密鍵生成部（SKGk）２８−ｋで生成された秘密鍵SKuが入力される（ステップＳ６１）。以下では、ステップＳ６１で検索トークン生成部（TKGk）２９−ｋに入力された秘密鍵SKk及び秘密鍵SKuを[[a0,a1,a2,bk+1,...,bN],[[α0,α1,α2,βk+1,...,βN],[A0,A1,A2,Bk+1,...,BN]]]と表現する。
【００９０】
次に、加算部２９ｄ−ｋが、ステップＳ１でkが入力された場合にはw=k+1として出力し、ステップＳ１でuが入力された場合にはw=u+1として出力する（ステップＳ６２）。次に、ランダム値生成部２９ａ−ｋがランダム値γ1, γ2, γ3∈Zκを生成して出力する（ステップＳ６３）。次に、演算部２９ｂａ−ｋが、
【００９１】
【数２７】
2010160235.tif 000029
の演算を行い（ステップＳ６４）、演算部２９ｂｂ−ｋ，２９ｂｃ−ｋが、それぞれ、
【００９２】
【数２８】
2010160235.tif 000030
の演算を行う（ステップＳ６５，Ｓ６６）。これらにより、検索トークン演算部２９ｂ−ｋは、ステップＳ１で入力されたk又はuに対応する検索トークン
【００９３】
【数２９】
2010160235.tif 000031
を生成して出力する（ステップＳ６８）。
【００９４】
《ステップＳ５の復号処理の具体例》
暗号化データベースに格納された各暗号化キーワードHIBE (LVID*, KW*, “*”)が、式(7)のように生成されたものである場合、ステップＳ５での各暗号化キーワードHIBE (LVID*, KW*, “*”)の復号処理は以下のようになる。ただし、式(7)に示す暗号化キーワードをHIBE (LVID*,KW*,“*”)=[C1,C2,C3,C4]と表現し、式(40)(44)に示す検索トークンをST(LVIDn,KW*)=[ν1,ν2,ν3]と表現する。
【００９５】
【数３０】
2010160235.tif 000032
ここで、検索トークンST(LVIDn,KW*)に対応するレベル識別子LVIDnとキーワードKW*との両方が、各暗号化キーワードHIBE (LVID*, KW*, “*”)に対応するレベル識別子LVID*とキーワードKW*とに一致する場合には、各暗号化キーワードHIBE(LVID*, KW*, “*”)が正しく復号され、復号結果としてMsg="1"or"0"が得られる。例えば、式(7)及び式(40)を式(45)の右辺に代入すると、
【００９６】
【数３１】
2010160235.tif 000033
となり、式(5)より、
【００９７】
【数３２】
2010160235.tif 000034
と変形でき、前述の［性質３］より、
【００９８】
【数３３】
2010160235.tif 000035
と変形でき、［性質６］より、
【００９９】
【数３４】
2010160235.tif 000036
となる。さらに、前述の［性質２］［性質３］より、式(47)の右辺は、
【０１００】
【数３５】
2010160235.tif 000037
となる。
【０１０１】
また、式(7)及び式(44)を式(45)の右辺に代入すると、式(46)のランダム数r1,r2,sを別のランダム数r1',r2',s'に更新した形に変形できるため、この場合も、正しい鍵を用いれば、式(45)によってMsgが復号できることができる。
【０１０２】
なお、本発明は上述の実施の形態に限定されるものではない。例えば、データベース装置１０の記憶部１３に格納された暗号化データベースが、各検索対象情報A,...,Bの各暗号文ENC(A),...,ENC(Z)と、当該検索対象情報A,...,Bにそれぞれ対応するキーワードKW1,...,KW9及び何れかの端末装置（TAn）２０−ｎに対応するレベル識別子LVIDnの組をＩＤとした階層型ＩＤベース暗号方式の各暗号文である暗号化キーワードHIBE(LVIDn,KW*)と、が対応付けられたものであってもよい。この場合には、検索トークンを秘密鍵として用いて復号できた暗号化キーワードHIBE(LVIDn,KW*)に対応する各暗号文ENC(*)が検索結果として返される構成となる。
【０１０３】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０４】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１０５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１０９】
本形態の利用分野としては、暗号化データベースの検索分野を例示できる。
【符号の説明】
【０１１０】
１  検索システム
【図１】
2010160235.tif 000038
【図２】
2010160235.tif 000039
【図３】
2010160235.tif 000040
【図４】
2010160235.tif 000041
【図５】
2010160235.tif 000042
【図６】
2010160235.tif 000043
【図７】
2010160235.tif 000044
【図８】
2010160235.tif 000045
【図９】
2010160235.tif 000046
【図１０】
2010160235.tif 000047
【図１１】
2010160235.tif 000048
【図１２】
2010160235.tif 000049
【図１３】
2010160235.tif 000050
【図１４】
2010160235.tif 000051
【図１５】
2010160235.tif 000052