(57)【特許請求の範囲】
【請求項１】
属性ベクトル生成装置と、述語ベクトル生成装置と、判定装置と、からなる検索システムであって、
Ｆｑを位数ｑの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Ｆｑの元で表現されるｔｒとし、添え字ｔｒはｔｒを意味し、ｒｄ１，…，ｒｄｔｒを乱数とし、検索対象情報に対応する登録用情報の要素をＸ１，…，Ｘｔｒとし、検索用情報の要素をｓ１，…，ｓｔｒとし、
【数５０】
0005486519.tif 000053
とし、ｆｐ（Ｘ１，…，Ｘｔｒ）を変数ｓ１，…，ｓｔｒを含まないＸ１，…，Ｘｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とし、ｆｐ（ｓ１，…，ｓｔｒ）を変数Ｘ１，…，Ｘｔｒを含まないｓ１，…，ｓｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とし、Ｐを１以上の整数とし、前記式（Ａ）は
【数５１】
0005486519.tif 000054
と表現されるものとし、
前記属性ベクトル生成装置は検索対象情報に対応する登録用情報の要素の集合Ｘ１，…，Ｘｔｒを用いて、前記式（Ｂ）のｆｐ（Ｘ１，…，Ｘｔｒ）の値を要素とする属性ベクトルを生成し、
前記述語ベクトル生成装置は検索用情報の要素の集合ｓ１，…，ｓｔｒを用いて、前記式（Ｂ）のｆｐ（ｓ１，…，ｓｔｒ）の値を要素とする述語ベクトルを生成し、
前記判定装置は前記属性ベクトルと前記述語ベクトルとの内積が０のとき、前記検索対象情報に対応する登録用情報中に前記検索用情報が含まれると判定する、
検索システム。
【請求項２】
請求項１記載の検索システムであって、
Ｙ０＝１とし、前記属性ベクトル生成装置は−Ｘ１，−Ｘ２，…，−Ｘｔｒのｋ次基本対称式Ｙｋを用いて、ｋ次基本対称式Ｙｋの値を要素とする属性ベクトルｗ→＝｛Ｙ０，Ｙ１，…，Ｙｋ，…，Ｙｔｒ｝を生成し、
前記述語ベクトル生成装置は
【数５２】
0005486519.tif 000055
の値を要素とする述語ベクトルｖ→＝｛Ｖ０，Ｖ１，…，Ｖｋ，…，Ｖｔｒ｝を生成する、
検索システム。
【請求項３】
請求項１または２記載の検索システムであって、
前記属性ベクトル生成装置は、検索対象情報に対応する登録用情報の要素の集合から重複する要素を削除して属性ベクトルを生成し、
前記述語ベクトル生成装置は、検索用情報の要素の集合から重複する要素を削除して述語ベクトルを生成する、
検索システム。
【請求項４】
請求項１から３の何れかに記載の検索システムにおいて用いられる判定装置。
【請求項５】
少なくとも属性ベクトルまたは述語ベクトルを生成するベクトル構成装置であって、
Ｆｑを位数ｑの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Ｆｑの元で表現されるｔｒとし、添え字ｔｒはｔｒを意味し、ｒｄ１，…，ｒｄｔｒを乱数とし、検索対象情報に対応する登録用情報の要素をＸ１，…，Ｘｔｒとし、検索用情報の要素をｓ１，…，ｓｔｒとし、
【数５３】
0005486519.tif 000056
とし、ｆｐ（Ｘ１，…，Ｘｔｒ）を変数ｓ１，…，ｓｔｒを含まないＸ１，…，Ｘｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とし、ｆｐ（ｓ１，…，ｓｔｒ）を変数Ｘ１，…，Ｘｔｒを含まないｓ１，…，ｓｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とし、Ｐを１以上の整数とし、前記式（Ａ）は
【数５４】
0005486519.tif 000057
と表現されるものとし、
少なくとも検索対象情報に対応する登録用情報の要素の集合Ｘ１，…，Ｘｔｒを用いて、前記式（Ｂ）のｆｐ（Ｘ１，…，Ｘｔｒ）の値を要素とする属性ベクトルを生成するか、
前記述語ベクトル生成装置は検索用情報の要素の集合ｓ１，…，ｓｔｒを用いて、前記式（Ｂ）のｆｐ（ｓ１，…，ｓｔｒ）の値を要素とする述語ベクトルを生成する、
ベクトル構成装置。
【請求項６】
請求項５記載のベクトル構成装置であって、
Ｙ０＝１とし、少なくとも−Ｘ１，−Ｘ２，…，−Ｘｔｒのｋ次の基本対称式Ｙｋを用いて、ｋ次基本対称式Ｙｋの値を要素とする属性ベクトルｗ→＝｛Ｙ０，Ｙ１，…，Ｙｋ，…，Ｙｔｒ｝として生成するか、
【数５５】
0005486519.tif 000058
の値を要素とする述語ベクトルｖ→＝｛Ｖ０，Ｖ１，…，Ｖｋ，…，Ｖｔｒ｝を生成する、
ベクトル構成装置。
【請求項７】
請求項５または６記載のベクトル構成装置であって、
少なくとも、検索対象情報に対応する登録用情報の要素の集合から重複する要素を削除して属性ベクトルを生成するか、または、検索用情報の要素の集合から重複する要素を削除して述語ベクトルを生成する、
ベクトル構成装置。
【請求項８】
属性ベクトル生成ステップと、述語ベクトル生成ステップと、判定ステップと、からなる検索方法であって、
Ｆｑを位数ｑの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Ｆｑの元で表現されるｔｒとし、添え字ｔｒはｔｒを意味し、ｒｄ１，…，ｒｄｔｒを乱数とし、検索対象情報に対応する登録用情報の要素をＸ１，…，Ｘｔｒとし、検索用情報の要素をｓ１，…，ｓｔｒとし、
【数５６】
0005486519.tif 000059
とし、ｆｐ（Ｘ１，…，Ｘｔｒ）を変数ｓ１，…，ｓｔｒを含まないＸ１，…，Ｘｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とし、ｆｐ（ｓ１，…，ｓｔｒ）を変数Ｘ１，…，Ｘｔｒを含まないｓ１，…，ｓｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とし、Ｐを１以上の整数とし、前記式（Ａ）は
【数５７】
0005486519.tif 000060
と表現されるものとし、
前記属性ベクトル生成ステップにおいて、検索対象情報に対応する登録用情報の要素の集合Ｘ１，…，Ｘｔｒを用いて、前記式（Ｂ）のｆｐ（Ｘ１，…，Ｘｔｒ）の値を要素とする属性ベクトルを生成し、
前記述語ベクトル生成ステップにおいて、検索用情報の要素の集合ｓ１，…，ｓｔｒを用いて、前記式（Ｂ）のｆｐ（ｓ１，…，ｓｔｒ）の値を要素とする述語ベクトルを生成し、
前記判定ステップにおいて、前記属性ベクトルと前記述語ベクトルとの内積が０のとき、前記検索対象情報に対応する登録用情報中に前記検索用情報が含まれると判定する、
検索方法。
【請求項９】
少なくとも属性ベクトルまたは述語ベクトルを生成するベクトル構成方法であって、
Ｆｑを位数ｑの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Ｆｑの元で表現されるｔｒとし、添え字ｔｒはｔｒを意味し、ｒｄ１，…，ｒｄｔｒを乱数とし、検索対象情報に対応する登録用情報の要素をＸ１，…，Ｘｔｒとし、検索用情報の要素をｓ１，…，ｓｔｒとし、
【数５８】
0005486519.tif 000061
とし、ｆｐ（Ｘ１，…，Ｘｔｒ）を変数ｓ１，…，ｓｔｒを含まないＸ１，…，Ｘｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とし、ｆｐ（ｓ１，…，ｓｔｒ）を変数Ｘ１，…，Ｘｔｒを含まないｓ１，…，ｓｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とし、Ｐを１以上の整数とし、前記式（Ａ）は
【数５９】
0005486519.tif 000062
と表現されるものとし、
少なくとも検索対象情報に対応する登録用情報の要素の集合Ｘ１，…，Ｘｔｒを用いて、前記式（Ｂ）のｆｐ（Ｘ１，…，Ｘｔｒ）の値を要素とする属性ベクトルを生成するか、
前記述語ベクトル生成方法は検索用情報の要素の集合ｓ１，…，ｓｔｒを用いて、前記式（Ｂ）のｆｐ（ｓ１，…，ｓｔｒ）の値を要素とする述語ベクトルを生成する、
ベクトル構成方法。
【請求項１０】
請求項４から７の何れかに記載の判定装置またはベクトル構成装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はキーワード検索や文書照合のための技術に関し、特に述語論理をベクトル表現し２つのベクトルの内積が０になるか否かを判定することにより、キーワード検索や文書照合を行う検索システム、判定装置、ベクトル構成装置、その方法及びプログラムに関する。
【背景技術】
【０００２】
述語論理を表現し２つのベクトルの内積が０になるか否かを判定することにより、キーワードや文書が一致するか否かを判定する従来技術として、非特許文献１及び２が知られている。これらの技術を用いることで、暗号情報に対して内積述語用いて検索タグと検索問い合わせ文（以下、「検索クエリ」という）を生成し、例えば内積該当暗号情報を復号することなくキーワードや文書を検索することができる。この検索技術を利用したものとして内積述語検索可能暗号がある（非特許文献１〜３参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】R. Yoshida, S. Oda, and T. Kobayashi. "Public-key encryption with partial matching keyword search", In Symp. on Cryptography and Information Security, 2010.
【非特許文献２】N. Matsuda, M. Hattori, T. Ito, and T. Yoneda. "Secure datacenter systems with hierarchical predicate encryption", In Symp. on Cryptography and Information Security, 2010.
【非特許文献３】R. Yoshida, A. Nagai, and T. Kobayashi. "Hierarchical predicate encryption with keyword search in multi-user setting", In Computer Security Symposium, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来技術では、ある長さｎの属性ベクトルから検索タグを作成し、そして同じ長さｎの述語ベクトルから検索クエリを生成し、それぞれの属性ベクトルと述語ベクトルの内積が０となるか否かを判定することで、暗号情報に対してキーワード検索や文書照合を行う。従来の属性ベクトル及び述語ベクトルの構成方法では、検索しようとする情報（以下、「検索用情報」という、例えば検索しようとするキーワードや照合しようとする文書等）が複数の要素（例えば文字や単語等）からなる場合、検索対象情報に対応する登録用情報の要素の中に、検索用情報の要素が全て登場するか否かを一回の検証（内積）で判定することが難しい。
【０００５】
本発明は、述語多項式を用いて集合部分一致検索を行い、検索用情報の要素の集合が検索対象情報に対応する登録用情報の要素の集合内に含まれるか否かを判定する検索システム、判定装置、ベクトル構成装置、その方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記の課題を解決するために、本発明の第一の態様に係る検索システムは、属性ベクトル生成装置と、述語ベクトル生成装置と、判定装置と、からなる。Ｆｑを位数ｑの有限体とする。検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Ｆｑの元で表現されるｔｒとする。添え字ｔｒはｔｒを意味する。ｒｄ１，…，ｒｄｔｒを乱数とする。検索対象情報に対応する登録用情報の要素をＸ１，…，Ｘｔｒとし、検索用情報の要素をｓ１，…，ｓｔｒとする。
【０００７】
【数１】
0005486519.tif 000002
【０００８】
とする。ｆｐ（Ｘ１，…，Ｘｔｒ）を変数ｓ１，…，ｓｔｒを含まないＸ１，…，Ｘｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とする。ｆｐ（ｓ１，…，ｓｔｒ）を変数Ｘ１，…，Ｘｔｒを含まないｓ１，…，ｓｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とする。Ｐを１以上の整数とする。式（Ａ）は
【０００９】
【数２】
0005486519.tif 000003
【００１０】
と表現されるものとする。属性ベクトル生成装置は検索対象情報に対応する登録用情報の要素の集合Ｘ１，…，Ｘｔｒを用いて、式（Ｂ）のｆｐ（Ｘ１，…，Ｘｔｒ）の値を要素とする属性ベクトルを生成する。述語ベクトル生成装置は検索用情報の要素の集合ｓ１，…，ｓｔｒを用いて、式（Ｂ）のｆｐ（ｓ１，…，ｓｔｒ）の値を要素とする述語ベクトルを生成し、判定装置は属性ベクトルと述語ベクトルとの内積が０のとき、検索対象情報に対応する登録用情報中に検索用情報が含まれると判定する。
【００１１】
上記の課題を解決するために、本発明の第二の態様に係るベクトル構成装置によれば、少なくとも属性ベクトルまたは述語ベクトルを生成する。Ｆｑを位数ｑの有限体とする。検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Ｆｑの元で表現されるｔｒとする。添え字ｔｒはｔｒを意味する。ｒｄ１，…，ｒｄｔｒを乱数とする。検索対象情報に対応する登録用情報の要素をＸ１，…，Ｘｔｒとする。検索用情報の要素をｓ１，…，ｓｔｒとする。
【００１２】
【数３】
0005486519.tif 000004
【００１３】
とする。ｆｐ（Ｘ１，…，Ｘｔｒ）を変数ｓ１，…，ｓｔｒを含まないＸ１，…，Ｘｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とする。ｆｐ（ｓ１，…，ｓｔｒ）を変数Ｘ１，…，Ｘｔｒを含まないｓ１，…，ｓｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とする。Ｐを１以上の整数とする。式（Ａ）は
【００１４】
【数４】
0005486519.tif 000005
【００１５】
と表現されるものとする。少なくとも検索対象情報に対応する登録用情報の要素の集合Ｘ１，…，Ｘｔｒを用いて、式（Ｂ）のｆｐ（Ｘ１，…，Ｘｔｒ）の値を要素とする属性ベクトルを生成するか、または、述語ベクトル生成装置は検索用情報の要素の集合ｓ１，…，ｓｔｒを用いて、式（Ｂ）のｆｐ（ｓ１，…，ｓｔｒ）の値を要素とする述語ベクトルを生成する。
【００１６】
上記の課題を解決するために、本発明の第三の態様に係る検索方法は、属性ベクトル生成ステップと、述語ベクトル生成ステップと、判定ステップと、からなる。Ｆｑを位数ｑの有限体とする。検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Ｆｑの元で表現されるｔｒとする。添え字ｔｒはｔｒを意味する。ｒｄ１，…，ｒｄｔｒを乱数とする。検索対象情報に対応する登録用情報の要素をＸ１，…，Ｘｔｒとする。検索用情報の要素をｓ１，…，ｓｔｒとする。
【００１７】
【数５】
0005486519.tif 000006
【００１８】
とする。ｆｐ（Ｘ１，…，Ｘｔｒ）を変数ｓ１，…，ｓｔｒを含まないＸ１，…，Ｘｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とする。ｆｐ（ｓ１，…，ｓｔｒ）を変数Ｘ１，…，Ｘｔｒを含まないｓ１，…，ｓｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とする。Ｐを１以上の整数とする。式（Ａ）は
【００１９】
【数６】
0005486519.tif 000007
【００２０】
と表現されるものとする。属性ベクトル生成ステップにおいて、検索対象情報に対応する登録用情報の要素の集合Ｘ１，…，Ｘｔｒを用いて、式（Ｂ）のｆｐ（Ｘ１，…，Ｘｔｒ）の値を要素とする属性ベクトルを生成する。述語ベクトル生成ステップにおいて、検索用情報の要素の集合ｓ１，…，ｓｔｒを用いて、式（Ｂ）のｆｐ（ｓ１，…，ｓｔｒ）の値を要素とする述語ベクトルを生成する。判定ステップにおいて、属性ベクトルと述語ベクトルとの内積が０のとき、検索対象情報に対応する登録用情報中に検索用情報が含まれると判定する。
【００２１】
上記の課題を解決するために、本発明の第四の態様に係るベクトル構成方法によれば、少なくとも属性ベクトルまたは述語ベクトルを生成する。Ｆｑを位数ｑの有限体とする。検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Ｆｑの元で表現されるｔｒとする。添え字ｔｒはｔｒを意味し、ｒｄ１，…，ｒｄｔｒを乱数とする。検索対象情報に対応する登録用情報の要素をＸ１，…，Ｘｔｒとする。検索用情報の要素をｓ１，…，ｓｔｒとする。
【００２２】
【数７】
0005486519.tif 000008
【００２３】
とする。ｆｐ（Ｘ１，…，Ｘｔｒ）を変数ｓ１，…，ｓｔｒを含まないＸ１，…，Ｘｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とする。ｆｐ（ｓ１，…，ｓｔｒ）を変数Ｘ１，…，Ｘｔｒを含まないｓ１，…，ｓｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とする。Ｐを１以上の整数とする。式（Ａ）は
【００２４】
【数８】
0005486519.tif 000009
【００２５】
と表現されるものとする。少なくとも検索対象情報に対応する登録用情報の要素の集合Ｘ１，…，Ｘｔｒを用いて、式（Ｂ）のｆｐ（Ｘ１，…，Ｘｔｒ）の値を要素とする属性ベクトルを生成するか、述語ベクトル生成方法は検索用情報の要素の集合ｓ１，…，ｓｔｒを用いて、式（Ｂ）のｆｐ（ｓ１，…，ｓｔｒ）の値を要素とする述語ベクトルを生成する。
【発明の効果】
【００２６】
本発明は、
【００２７】
【数９】
0005486519.tif 000010
【００２８】
を満たす属性ベクトルと述語ベクトルを用いて、登録用情報中に検索用情報が含まれるか否かを判定するため、検索用情報が複数の要素からなる場合であっても１回の検証により判定することができるという効果を奏する。
【図面の簡単な説明】
【００２９】
【図１】検索システム１の構成例を示すブロック図。
【図２】検索システム１の処理フローを示す図。
【図３】検索システム１の各装置の機能ブロック図。
【図４】検索システム２の構成例を示すブロック図。
【図５】図５Ａは管理装置２７−１の機能ブロック図、図５Ｂは管理装置２７−（ｍ’＋１）の機能ブロック図。
【図６】属性ベクトル生成装置２１−ｕの機能ブロック図。
【図７】判定装置２６の機能ブロック図。
【図８】図８Ａは保管装置２３の機能ブロック図、図５Ｂは暗号化データベース２３３内に記憶されるデータ例を示す図。
【図９】述語ベクトル生成装置２５−ｕの機能ブロック図。
【発明を実施するための形態】
【００３０】
以下、本発明の実施形態について、説明する。
【００３１】
〔定義〕
まず、各実施形態で使用される用語や記号を定義する。
【００３２】
行列：「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
【００３３】
（・）Ｔ：（・）Ｔは・の転置行列を表す。
（・）−１：（・）−１は・の逆行列を表す。
∧：∧は論理積を表す。
∨：∨は論理和を表す。
Ｚ：Ｚは整数集合を表す。
ｓｅｃ：ｓｅｃはセキュリティパラメータ（ｓｅｃ∈Ｚ，ｓｅｃ＞０）を表す。
【００３４】
Ｆｑ：Ｆｑは位数ｑの有限体を表す。位数ｑは１以上の整数であり、例えば、素数や素数のべき乗値を位数ｑとする。すなわち、有限体Ｆｑの例は素体やそれを基礎体とした拡大体である。
０Ｆ：０Ｆは有限体Ｆｑの加法単位元（零元）を表す。一般化した加法単位元を０と表す。
１Ｆ：１Ｆは有限体Ｆｑの乗法単位元を表す。一般化した乗法単位元を１と表す。
δ（ｉ，ｊ）：δ（ｉ，ｊ）はクロネッカーのデルタ関数を表す。ｉ＝ｊの場合にδ（ｉ，ｊ）＝１Ｆを満たし、ｉ≠ｊの場合にδ（ｉ，ｊ）＝０Ｆを満たす。
Ｅ：Ｅは有限体Ｆｑ上で定義された楕円曲線を表す。
Ｇ１，Ｇ２，ＧＴ：Ｇ１，Ｇ２，ＧＴは位数ｑの巡回群を表す。巡回群Ｇ１，Ｇ２の具体例は、楕円曲線Ｅのｐ等分点からなる有限集合Ｅ［ｐ］やその部分群である。Ｇ１＝Ｇ２であってもよいしＧ１≠Ｇ２であってもよい。また、巡回群ＧＴの具体例は、有限体Ｆｑを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Ｆｑの代数閉包における１のｐ乗根からなる有限集合である。
【００３５】
なお、本形態では、巡回群Ｇ１，Ｇ２上で定義された演算を加法的に表現し、巡回群ＧＴ上で定義された演算を乗法的に表現する。すなわち、χ∈Ｆｑ及びΩ∈Ｇ１に対するχ・Ω∈Ｇ１は、Ω∈Ｇ１に対して巡回群Ｇ１で定義された演算をχ回施すことを意味し、Ω１，Ω２∈Ｇ１に対するΩ１＋Ω２∈Ｇ１は、Ω１∈Ｇ１とΩ２∈Ｇ１とを被演算子として巡回群Ｇ１で定義された演算を行うことを意味する。同様に、χ∈Ｆｑ及びΩ∈Ｇ２に対するχ・Ω∈Ｇ２は、Ω∈Ｇ２に対して巡回群Ｇ２で定義された演算をχ回施すことを意味し、Ω１，Ω２∈Ｇ２に対するΩ１＋Ω２∈Ｇ２は、Ω１∈Ｇ２とΩ２∈Ｇ２とを被演算子として巡回群Ｇ２で定義された演算を行うことを意味する。一方、χ∈Ｆｑ及びΩ∈ＧＴに対するΩχ∈ＧＴは、Ω∈ＧＴに対して巡回群ＧＴで定義された演算をχ回施すことを意味し、Ω１，Ω２∈ＧＴに対するΩ１・Ω２∈ＧＴは、Ω１∈ＧＴとΩ２∈ＧＴとを被演算子として巡回群ＧＴで定義された演算を行うことを意味する。
【００３６】
ｎ：ｎは１以上の整数を表す。
ζ：ζは１以上の整数を表す。ζの一例は２または３である。
Ｇ１ｎ＋ζ：Ｇ１ｎ＋ζはｎ＋ζ個の巡回群Ｇ１の直積を表す。
Ｇ２ｎ＋ζ：Ｇ２ｎ＋ζはｎ＋ζ個の巡回群Ｇ２の直積を表す。
ｇ１，ｇ２，ｇＴ：ｇ１，ｇ２，ｇＴは巡回群Ｇ，Ｇ１，Ｇ２，ＧＴの生成元を表す。
Ｖ：Ｖはｎ＋ζ個の巡回群Ｇ１の直積からなるｎ＋ζ次元のベクトル空間を表す。
Ｖ＊：Ｖ＊はｎ＋ζ個の巡回群Ｇ２の直積からなるｎ＋ζ次元のベクトル空間を表す。
ｅ：ｅは直積Ｇ１ｎ＋ζと直積Ｇ２ｎ＋ζとの直積Ｇ１ｎ＋ζ×Ｇ２ｎ＋ζを巡回群ＧＴに写す非退化な双線形写像（ｂｉｌｉｎｅａｒｍａｐ）を表す。双線形写像ｅは、巡回群Ｇ１のｎ＋ζ個の元γβ（β＝１，…，ｎ＋ζ）と巡回群Ｇ２のｎ＋ζ個の元γβ＊（β＝１，…，ｎ＋ζ）とを入力とし、巡回群ＧＴの１個の元を出力する。
【００３７】
e:G1n+ζ×G2n+ζ→GT     (1)
双線形写像ｅは以下の性質を満たす。
【００３８】
［双線形性］全てのΓ１∈Ｇ１ｎ＋ζ，Γ２∈Ｇ２ｎ＋ζ及びν，κ∈Ｆｑについて以下の関係を満たす。
e(ν・Γ1,κ・Γ2)=e(Γ1,Γ2)ν・κ     (2)
【００３９】
［非退化性］全てのΓ１∈Ｇ１ｎ＋ζ，Γ２∈Ｇ２ｎ＋ζを巡回群ＧＴの単位元に写すものではない。
【００４０】
［計算可能性］あらゆる
Γ1∈G1n+ζ,Γ2∈G2n+ζ     (3)
についてｅ（Γ１，Γ２）を効率的に計算するアルゴリズムが存在する。
【００４１】
本形態では、巡回群Ｇ１と巡回群Ｇ２との直積Ｇ１×Ｇ２を巡回群ＧＴに写す非退化な双線形写像を計算するための関数
Pair:G1×G2→GT     (4)
を用いて双線形写像ｅを構成する。本形態の双線形写像ｅは、巡回群Ｇ１のｎ＋ζ個の元γβ（β＝１，…，ｎ＋ζ）からなるｎ＋ζ次元ベクトル（γ１，…，γｎ＋ζ）と、巡回群Ｇ２のｎ＋ζ個の元γβ＊（β＝１，…，ｎ＋ζ）からなるｎ＋ζ次元ベクトル（γ１＊，…，γｎ＋ζ＊）との入力に対し、巡回群ＧＴの１個の元
e=Πβ=1n+ζPair(γβ,γβ*)     (5)
を出力する。
【００４２】
なお、双線形写像Ｐａｉｒは、巡回群Ｇ１の１個の元と巡回群Ｇ２の１個の元との組を入力とし、巡回群ＧＴの１個の元を出力するものであり、以下の性質を満たす。
【００４３】
［双線形性］全てのΩ１∈Ｇ１，Ω２∈Ｇ２及びν，κ∈Ｆｑについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω1,Ω2)ν・κ     (6)
【００４４】
［非退化性］全ての
Ω1∈G1,Ω2∈G2     (7)
を巡回群ＧＴの単位元に写すものではない。
【００４５】
［計算可能性］あらゆるΩ１∈Ｇ１，Ω２∈Ｇ２についてＰａｉｒ（Ω１，Ω２）を効率的に計算するアルゴリズムが存在する。
【００４６】
なお、双線形写像Ｐａｉｒの具体例は、ＷｅｉｌペアリングやＴａｔｅペアリングなどのペアリングである（例えば、参考文献１及び２等参照）。
（参考文献１）Alfred. J. Menezes，"ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS"，ISBN0-7923-9368-6，pp. 61-81
（参考文献２）"RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems"
ａｉ（ｉ＝１，…，ｎ＋ζ）：ａｉは巡回群Ｇ１のｎ＋ζ個の元を要素とするｎ＋ζ次元の基底ベクトルを表す。基底ベクトルａｉの一例は、κ１・ｇ１∈Ｇ１をｉ次元目の要素とし、残りのｎ個の要素を巡回群Ｇ１の単位元（加法的に「０」と表現）とするｎ＋ζ次元の基底ベクトルである。この場合、ｎ＋ζ次元の基底ベクトルａｉ（ｉ＝１，…，ｎ＋ζ）の各要素をそれぞれ列挙して表現すると、以下のようになる。
【００４７】
a1=(κ1・g1,0,0,…,0)
a2=(0,κ1・g1,0,…,0)     (8)
…
an+ζ=(0,0,0,…,κ1・g1)
【００４８】
ここで、κ１は加法単位元０Ｆ以外の有限体Ｆｑの元からなる定数であり、κ１∈Ｆｑの具体例はκ１＝１Ｆである。基底ベクトルａｉは直交基底であり、巡回群Ｇ１のｎ＋ζ個の元を要素とする全てのｎ＋ζ次元ベクトルは、ｎ＋ζ次元の基底ベクトルａｉ（ｉ＝１，…，ｎ＋ζ）の線形和によって表される。すなわち、ｎ＋ζ次元の基底ベクトルａｉはベクトル空間Ｖを張る。
【００４９】
ａｉ＊（ｉ＝１，…，ｎ＋ζ）：巡回群Ｇ２のｎ＋ζ個の元を要素とするｎ＋ζ次元の基底ベクトルを表す。基底ベクトルａｉ＊の一例は、κ２・ｇ２∈Ｇ２をｉ次元目の要素とし、残りのｎ個の要素を巡回群Ｇ２の単位元（加法的に「０」と表現）とするｎ＋ζ次元の基底ベクトルである。この場合、基底ベクトルａｉ＊（ｉ＝１，…，ｎ＋ζ）の各要素をそれぞれ列挙して表現すると、以下のようになる。
【００５０】
a1*=(κ2・g2,0,0,…,0)
a2*=(0,κ2・g2,0,…,0)     (9)
…
an+ζ*=(0,0,0,…,κ2・g2)
【００５１】
ここで、κ２は加法単位元０Ｆ以外の有限体Ｆｑの元からなる定数であり、κ２∈Ｆｑの具体例はκ２＝１Ｆである。基底ベクトルａｉ＊は直交基底であり、巡回群Ｇ２のｎ＋ζ個の元を要素とする全てのｎ＋ζ次元ベクトルは、ｎ＋ζ次元の基底ベクトルａｉ＊（ｉ＝１，…，ｎ＋ζ）の線形和によって表される。すなわち、ｎ＋ζ次元の基底ベクトルａｉ＊はベクトル空間Ｖ＊を張る。
【００５２】
なお、基底ベクトルａｉと基底ベクトルａｉ＊とは、０Ｆを除く有限体Ｆｑの元τ＝κ１・κ２について
e(ai,aj*)=gTτ・δ(i,j)     (10)
を満たす。すなわち、ｉ＝ｊの場合には、式（５）（６）の関係から、
e(ai,aj*)=Pair(κ1・g1,κ2・g2)・Pair(0,0)・…・Pair(0,0)
=Pair(g1,g2)κ1・κ2・Pair(g1,g2)0・0・…・Pair(g1,g2)0・0
=Pair(g1,g2)κ1・κ2=gTτ
を満たす。一方、ｉ≠ｊの場合には、ｅ（ａｉ，ａｊ＊）＝Πｉ＝１ｎ＋ζＰａｉｒ（ａｉ，ａｊ＊）の右辺は、Ｐａｉｒ（κ１・ｇ１，κ２・ｇ２）を含まず、Ｐａｉｒ（κ１・ｇ１，０）とＰａｉｒ（０，κ２・ｇ２）とＰａｉｒ（０，０）との積になる。さらに、式（６）の関係からＰａｉｒ（ｇ１，０）＝Ｐａｉｒ（０，ｇ２）＝Ｐａｉｒ（ｇ１，ｇ２）０を満たす。そのため、ｉ≠ｊの場合には、
e(ai,aj*)=e(g1,g2)0=gT0
を満たす。
【００５３】
特に、τ＝κ１・κ２＝１Ｆである場合（例えば、κ１＝κ２＝１Ｆの場合）、
e(ai,aj*)=gTδ(i,j)     (11)
を満たす。ここで、ｇＴ０＝１は巡回群ＧＴの単位元であり、ｇＴ１＝ｇＴは巡回群ＧＴの生成元である。この場合、基底ベクトルａｉと基底ベクトルａｉ＊とは双対正規直交基底であり、ベクトル空間Ｖとベクトル空間Ｖ＊とは、双線形写像を構成可能な双対ベクトル空間〔双対ペアリングベクトル空間（ＤＰＶＳ：Dual Paring Vectorspace）〕である。
【００５４】
Ａ：基底ベクトルａｉ（ｉ＝１，…，ｎ＋ζ）を要素とするｎ＋ζ行ｎ＋ζ列の行列を表す。例えば、基底ベクトルａｉ（ｉ＝１，…，ｎ＋ζ）が式（８）によって表現される場合、行列Ａは、
【００５５】
【数１０】
0005486519.tif 000011
となる。
【００５６】
Ａ＊：基底ベクトルａｉ＊（ｉ＝１，…，ｎ＋ζ）を要素とするｎ＋ζ行ｎ＋ζ列の行列を表す。例えば、基底ベクトルａｉ＊（ｉ＝１，…，ｎ＋ζ）が式（９）によって表現される場合、行列Ａ＊は、
【００５７】
【数１１】
0005486519.tif 000012
となる。
【００５８】
Ｘ：有限体Ｆｑの元を要素とするｎ＋ζ行ｎ＋ζ列の行列を表す。基底ベクトルａｉの座標変換に用いられる。行列Ｘのｉ行ｊ列（ｉ＝１，…，ｎ＋ζ，ｊ＝１，…，ｎ＋ζ）の要素をχｉ，ｊ∈Ｆｑとすると、行列Ｘは、
【００５９】
【数１２】
0005486519.tif 000013
となる。なお、行列Ｘの各要素χｉ，ｊを変換係数と呼ぶ。
【００６０】
Ｘ＊：Ｘ＊は行列Ｘの逆行列の転置行列Ｘ＊＝（Ｘ−１）Ｔを表す。基底ベクトルａｉ＊の座標変換に用いられる。行列Ｘ＊のｉ行ｊ列の要素をχｉ，ｊ＊∈Ｆｑとすると、行列Ｘ＊は、
【００６１】
【数１３】
0005486519.tif 000014
となる。なお、行列Ｘ＊の各要素χｉ，ｊ＊を変換係数と呼ぶ。
【００６２】
この場合、ｎ＋ζ行ｎ＋ζ列の単位行列をＩとするとＸ・（Ｘ＊）Ｔ＝Ｉを満たす。すなわち、単位行列
【００６３】
【数１４】
0005486519.tif 000015
に対し、
【００６４】
【数１５】
0005486519.tif 000016
を満たす。ここで、ｎ＋ζ次元ベクトル
χi→=(χi,1,…,χi,n+ζ)      (18)
χj→*=(χj,1*,…,χj,n+ζ*)     (19)
を定義する。すると、式（１７）の関係から、ｎ＋ζ次元ベクトルχｉ→とχｊ→＊との内積は、
χi→・χj→*=δ(i,j)     (20)
となる。
【００６５】
ｂｉ：ｂｉは巡回群Ｇ１のｎ＋ζ個の元を要素とするｎ＋ζ次元の基底ベクトルを表す。行列Ｘを用いて基底ベクトルａｉ（ｉ＝１，…，ｎ＋ζ）を座標変換することで得られる。具体的には、基底ベクトルｂｉは、
bi=Σj=1n+ζχi,j・aj     (21)
の演算によって得られる。例えば、基底ベクトルａｊ（ｊ＝１，…，ｎ＋ζ）が式（８）によって表現される場合、基底ベクトルｂｉの各要素をそれぞれ列挙して表現すると、以下のようになる。
【００６６】
bi=(χi,1・κ1・g1,χi,2・κ1・g1,…,χi,n+ζ・κ1・g1)     (22)
巡回群Ｇ１のｎ＋ζ個の元を要素とする全てのｎ＋ζ次元ベクトルは、ｎ＋ζ次元の基底ベクトルｂｉ（ｉ＝１，…，ｎ＋ζ）の線形和によって表される。すなわち、ｎ＋ζ次元の基底ベクトルｂｉは前述のベクトル空間Ｖを張る。
【００６７】
ｂｉ＊：ｂｉ＊は巡回群Ｇ２のｎ＋ζ個の元を要素とするｎ＋ζ次元の基底ベクトルを表す。行列Ｘ＊を用いて基底ベクトルａｉ＊（ｉ＝１，…，ｎ＋ζ）を座標変換することで得られる。具体的には、基底ベクトルｂｉ＊は、
bi*=Σj=1n+ζχi,j*・aj*     (23)
の演算によって得られる。例えば、基底ベクトルａｊ＊（ｊ＝１，…，ｎ＋ζ）が式（９）によって表現される場合、基底ベクトルｂｉ＊の各要素をそれぞれ列挙して表現すると、以下のようになる。
【００６８】
bi*=(χi,1*・κ2・g2,χi,2*・κ2・g2,…,χi,n+ζ*・κ2・g2)     (24)
となる。巡回群Ｇ２のｎ＋ζ個の元を要素とする全てのｎ＋ζ次元ベクトルは、ｎ＋ζ次元の基底ベクトルｂｉ＊（ｉ＝１，…，ｎ＋ζ）の線形和によって表される。すなわち、ｎ＋ζ次元の基底ベクトルｂｉ＊は前述のベクトル空間Ｖ＊を張る。
【００６９】
なお、基底ベクトルｂｉと基底ベクトルｂｉ＊とは、０Ｆを除く有限体Ｆｑの元τ＝κ１・κ２について
e(bi,bj*)=gTτ・δ(i,j)     (25)
を満たす。すなわち、式（５）（２０）（２２）（２４）の関係から、
【００７０】
【数１６】
0005486519.tif 000017
【００７１】
を満たす。特に、τ＝κ１・κ２＝１Ｆである場合（例えば、κ１＝κ２＝１Ｆの場合）、
e(bi,bj*)=gTδ(i,j)     (26)
を満たす。この場合、基底ベクトルｂｉと基底ベクトルｂｉ＊とは、双対ペアリングベクトル空間（ベクトル空間Ｖとベクトル空間Ｖ＊）の双対正規直交基底である。
【００７２】
なお、式（２５）の関係を満たすのであれば、式（８）（９）で例示したもの以外の基底ベクトルａｉ及びａｉ＊や、式（２１）（２３）で例示したもの以外の基底ベクトルｂｉ及びｂｉ＊を用いてもよい。
【００７３】
Ｂ：Ｂは基底ベクトルｂｉ（ｉ＝１，…，ｎ＋ζ）を要素とするｎ＋ζ行ｎ＋ζ列の行列。Ｂ＝Ｘ・Ａを満たす。例えば、基底ベクトルｂｉが式（２２）によって表現される場合、行列Ｂは、
【００７４】
【数１７】
0005486519.tif 000018
となる。
【００７５】
Ｂ＊：Ｂ＊は基底ベクトルｂｉ＊（ｉ＝１，…，ｎ＋ζ）を要素とするｎ＋ζ行ｎ＋ζ列の行列を表す。Ｂ＊＝Ｘ＊・Ａ＊を満たす。例えば、基底ベクトルｂｉ＊（ｉ＝１，…，ｎ＋ζ）が式（２４）によって表現される場合、行列Ｂ＊は、
【００７６】
【数１８】
0005486519.tif 000019
となる。
【００７７】
〔内積述語暗号方式〕
次に、内積述語暗号方式について説明する。内積述語暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が０となるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。内積述語暗号方式では、内積が０となることと論理式の真理値が真となることとが等価である。
【００７８】
［内積と論理式の真理値との関係］
内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。
【００７９】
まず、「ｘ１がη１である」という命題１と「ｘ２がη２である」という命題２との論理和（ｘ１＝η１）∨（ｘ２＝η２）を
(x1-η1)・(x2-η2)     (29)
という多項式で表現する。すると、各真理値と式（２９）の関数値との関係は以下のようになる。
【００８０】
【表１】
0005486519.tif 000020
【００８１】
［表１］から分かるように、論理和（ｘ１＝η１）∨（ｘ２＝η２）が真である場合、式（２９）の関数値は０になり、論理和（ｘ１＝η１）∨（ｘ２＝η２）が偽である場合、式（２９）の関数値は０以外の値となる。すなわち、論理和（ｘ１＝η１）∨（ｘ２＝η２）が真であることと、式（２９）の関数値が０となることとは等価である。よって、論理和は式（２９）で表現できる。
【００８２】
また、「ｘ１がη１である」という命題１と「ｘ２がη２である」という命題２との論理積（ｘ１＝η１）∧（ｘ２＝η２）を
ι1・(x1-η1)+ι2・(x2-η2)     (30)
という多項式で表現する。但し、ι１及びι２は乱数である。すると、真理値と式（３０）の関数値とは以下の関係となる。
【００８３】
【表２】
0005486519.tif 000021
【００８４】
［表２］から分かるように、論理積（ｘ１＝η１）∧（ｘ２＝η２）が真である場合、式（３０）の関数値は０になり、論理積（ｘ１＝η１）∧（ｘ２＝η２）が偽である場合、式（３０）の関数値は０以外の値となる。すなわち、論理積（ｘ１＝η１）∧（ｘ２＝η２）が真であることと、式（３０）の関数値が０となることとは等価である。よって、論理積は式（３０）で表現できる。
【００８５】
以上から、論理和や論理積からなる任意の論理式を多項式で表現できることが分かる。例えば、論理式｛（ｘ１＝η１）∨（ｘ２＝η２）｝∧（ｘ３＝η３）∧（ｘ４＝η４）は、多項式
ι1・{(x1-η1)・(x2-η2)}+ι2・(x3-η3)+ι3・(x4-η4)  (31)
で表現できる。以下、このように論理式を表現する多項式のことを述語多項式と呼ぶ。
【００８６】
述語多項式は２つのベクトルの内積で表現できる。すなわち、述語多項式は、各項の不定元成分と１とを各要素とするベクトルと、各項の係数成分を各要素とするベクトルとの内積に等しい。例えば、式（３１）の述語多項式は、各項の不定元成分と１を各要素とするベクトル（ｘ１・ｘ２，ｘ１，ｘ２，ｘ３，ｘ４，１）と、各項の係数成分を各要素とするベクトル（ι１，−ι１・η２，−ι１・η１，ι２，−ι２・η３＋ι３，ι１・η１・η２−ι３・η４）との内積に等しい。
【００８７】
そのため、述語多項式の値が０であるか否かと、述語多項式の各項の不定元成分と１とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が０であるか否かとは等価である。言い換えると、論理式の真理値が真であるか否かと、当該論理式を示す述語多項式の各項の不定元成分と１とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が０であるか否かとは等価である。
【００８８】
内積述語暗号方式では、上述の各項の不定元成分と１を各要素とするベクトル（以下、「属性ベクトル」という）及び各項の係数成分を各要素とするベクトル（以下、「述語ベクトル」という）の何れか一方のベクトルが暗号文に埋め込まれ、他方のベクトルが復号鍵に埋め込まれる。以下では、暗号文に埋め込まれるベクトルをｗ→＝（ｗ１，…，ｗｎ）とし、復号鍵に埋め込まれるベクトルをｖ→＝（ｖ１，…，ｖｎ）とする。
【００８９】
［内積述語暗号方式の基本構成］
内積述語暗号方式で鍵カプセル化メカニズムＫＥＭ（Key Encapsulation Mechanisms）を構成する例を示す。この構成はＳｅｔｕｐ，ＧｅｎＫｅｙ，Ｅｎｃ，Ｄｅｃを含む。
【００９０】
《Ｓｅｔｕｐ：セットアップ》
−入力：セキュリティパラメータｓｅｃ
−出力：マスタ鍵情報ＭＳＫ，公開パラメータＰＫ
Ｓｅｔｕｐの一例では、まず、セキュリティパラメータｓｅｃをｎとして、ｎ＋ζ次元の基底ベクトルａｉ（ｉ＝１，…，ｎ＋ζ）を要素とするｎ＋ζ行ｎ＋ζ列の行列Ａと、基底ベクトルａｉ＊（ｉ＝１，…，ｎ＋ζ）を要素とするｎ＋ζ行ｎ＋ζ列の行列Ａ＊と、座標変換のためのｎ＋ζ行ｎ＋ζ列の行列Ｘ，Ｘ＊とが選択される。次に、式（２１）に従って座標変換されたｎ＋ζ次元の基底ベクトルｂｉ（ｉ＝１，…，ｎ＋ζ）が算出され、式（２３）に従って座標変換されたｎ＋ζ次元の基底ベクトルｂｉ＊（ｉ＝１，…，ｎ＋ζ）が算出される。そして、基底ベクトルｂｉ＊（ｉ＝１，…，ｎ＋ζ）を要素とするｎ＋ζ行ｎ＋ζ列の行列Ｂ＊がマスタ鍵情報ＭＳＫとして出力され、ベクトル空間Ｖ，Ｖ＊、基底ベクトルｂｉ（ｉ＝１，…，ｎ＋ζ）を要素とするｎ＋ζ行ｎ＋ζ列の行列Ｂ、セキュリティパラメータｓｅｃ、有限体Ｆｑ、楕円曲線Ｅ、巡回群Ｇ１，Ｇ２，ＧＴ、生成元ｇ１，ｇ２，ｇＴ、双線形写像ｅなどが公開パラメータＰＫとして出力される。
【００９１】
《ＧｅｎＫｅｙ：復号鍵生成》
−入力：マスタ鍵情報ＭＳＫ，ベクトルｖ→
−出力：ベクトルｖ→に対応する復号鍵Ｄ＊
ＧｅｎＫｅｙの一例では、まず、有限体Ｆｑから元σ，σι−ｎ∈Ｆｑが選択される。そして、マスタ鍵情報ＭＳＫである行列Ｂ＊を用い、ベクトルｖ→に対応する復号鍵
D*=σ・(Σμ=1nvμ・bμ*)+Σι=n+1n+ζ’σι-n・bι*∈G2n+ζ’     (32)
が生成され、出力される。但し、σ，σι−ｎは乱数などの変数や定数などであり、ζ’≦ζである（例えばζ＝３，ζ’＝２）。またΣι＝ｎ＋１ｎ＋ζ’σι−ｎはシステムで共有される定数値とされる。以下では
Σι=n+1n+ζ’σι-n=1F     (33)
とされた例を説明する。これは本発明を限定しない。
【００９２】
《Ｅｎｃ：暗号化》
−入力：公開パラメータＰＫ，ベクトルｗ→，平文ｍｅｓ
−出力：暗号文（Ｃ１，Ｃ２）
Ｅｎｃの一例では、行列Ｂなどの公開パラメータＰＫと、有限体Ｆｑの元である乱数υ０，υ１，…，υζと、ベクトルｗ→とを用い、暗号文
C1=υ0・(Σμ=1nwμ・bμ)+Σμ=n+1n+ζυμ-n・bμ∈G1n+ζ     (34)
が生成される。但し、
υ1=…=υζ’     (35)
を満たす（例えばζ’＝２のときにはυ１＝υ２）。また、ｇＴτ・υ１を共通鍵Ｋとし、所定の共通鍵暗号方式（第２暗号方式）に則って平文ｍｅｓの暗号文Ｃ２が生成される。暗号文Ｃ２の一例は、
C2=gTτ・υ1・mes(36)
である。添え字のυ１はυ１を意味する。前述のように定数τの一例はτ＝１Ｆである。生成された暗号文（Ｃ１，Ｃ２）は出力される。
【００９３】
《Ｄｅｃ：復号》
−入力：ベクトルｖ→に対応する復号鍵Ｄ＊，暗号文（Ｃ１，Ｃ２）
−出力：復号値ｍｅｓ’
Ｄｅｃの一例では、まず、暗号文Ｃ１と復号鍵Ｄ＊とが式（１）の双線形写像ｅに入力され、その演算結果を共通鍵Ｋ＝ｅ（Ｃ１，Ｄ＊）とし、以下のように復号値ｍｅｓ’が求められる。
【００９４】
mes’=C2/e(C1,D*)∈GT     (37)
ここで、式（２）（２５）（３３）（３５）の性質から、
【００９５】
【数１９】
0005486519.tif 000022
を満たす。
【００９６】
内積ｗ→・ｖ→＝０であれば、式（３８）は、
【００９７】
【数２０】
0005486519.tif 000023
を満たす。式（３６）（３７）（３９）から、内積ｗ→・ｖ→＝０であればｍｅｓ’＝ｍｅｓとなり、正しく復号されることが分かる。
【００９８】
［階層的内積述語暗号方式の基本構成］
階層的内積述語暗号方式は内積述語暗号方式の一種であり、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が０となるときに当該暗号文が当該復号鍵で復号可能となる。さらに階層的内積述語暗号方式では階層的な処理によって復号鍵を生成できる。すなわち、階層的内積述語暗号方式では属性が階層化され、各階層までの属性に対応する鍵情報が存在するとともに、上位の階層に対応する鍵情報を用いて下位の階層に対応する鍵情報を生成できる。そして、このような階層的な処理によって生成された最終的な鍵情報が復号鍵となる。以下に階層的内積述語暗号方式の基本構成を例示する。以下では、階層的内積述語暗号方式を用いて鍵カプセル化メカニズムＫＥＭを構成する場合の基本構成を例示する。但し、これは本発明を限定するものではない。
【００９９】
《前提》
深さｄの属性空間の階層フォーマットを以下の式によって定義する。但し、ｄは１以上ｎ以下の整数である。
【０１００】
ξ→=(n,d;ξ1,…,ξd)(0=ξ0<ξ1<…<ξd=n)     (40)
有限体Ｆｑの元を要素とするξω−ξω−１（ω＝１，…，ｄ）次元のベクトル（零ベクトルを除く）を階層ωに対応するベクトル
【０１０１】
【数２１】
0005486519.tif 000024
【０１０２】
とし、階層１から階層ｍ（ｍ≦ｄ）までに対応するベクトルを（ｗ１→，…，ｗｍ→）とする。有限体Ｆｑの元を要素とするξω−ξω−１次元（ω＝１，…，ｄ）のベクトル（零ベクトルを除く）を階層ωに対応するベクトル
【０１０３】
【数２２】
0005486519.tif 000025
とし、階層１から階層ｍまでに対応するベクトルを（ｖ１→，…，ｖｍ→）とする。
【０１０４】
《Ｓｅｔｕｐ：セットアップ》
−入力：セキュリティパラメータｓｅｃ
−出力：階層フォーマットξ→，マスタ鍵情報ＭＳＫ，公開パラメータｍｐｋ
Ｓｅｔｕｐの一例では、セキュリティパラメータｓｅｃの単調増加関数値をｎとし、階層フォーマットξ→＝（ｎ，ｄ；ξ１，…，ξｄ）が定められる。また、この例ではζ＝３とし、ｎ＋３次元の基底ベクトルａｉ（ｉ＝１，…，ｎ＋３）を要素とするｎ＋３行ｎ＋３列の行列Ａと、基底ベクトルａｉ＊（ｉ＝１，…，ｎ＋３）を要素とするｎ＋３行ｎ＋３列の行列Ａ＊と、座標変換のためのｎ＋３行ｎ＋３列の行列Ｘ，Ｘ＊とが選択される。次に、式（２１）に従って座標変換されたｎ＋３次元の基底ベクトルｂｉ（ｉ＝１，…，ｎ＋３）が算出され、式（２３）に従って座標変換されたｎ＋３次元の基底ベクトルｂｉ＊（ｉ＝１，…，ｎ＋３）が算出される。
【０１０５】
この例では、基底ベクトル（ｂ１＊，…，ｂｎ＊，ｂｎ＋１＊，ｂｎ＋２＊，ｂｎ＋３＊）と行列Ｘとがマスタ鍵情報ＭＳＫとして出力され、基底ベクトル（ｂ１，…，ｂｎ，ｂｎ＋１＋ｂｎ＋２，ｂｎ＋３）、ベクトル空間Ｖ，Ｖ＊、セキュリティパラメータｓｅｃ、有限体Ｆｑ、楕円曲線Ｅ、巡回群Ｇ１，Ｇ２，ＧＴ、生成元ｇ１，ｇ２，ｇＴ、双線形写像ｅなどが公開パラメータｍｐｋとして出力される。
【０１０６】
《ＧｅｎＫｅｙ：鍵情報生成》
−入力：マスタ鍵情報ＭＳＫ，公開パラメータｍｐｋ，ベクトル（ｖ１→，…，ｖｍ→）
−出力：ベクトル（ｖ１→，…，ｖｍ→）に対応する鍵情報ｋｍ＊
ＧｅｎＫｅｙの一例では、まず、有限体Ｆｑから元σα，ω，Ψ，Φα∈Ｆｑ（α＝０，…，ｍ＋１，ξｍ＋１，…，ｎ；ω＝１，…，ｍ）が任意に選択される。この例では、これらとマスタ鍵情報ＭＳＫである基底ベクトル（ｂ１＊，…，ｂｎ＊，ｂｎ＋１＊，ｂｎ＋２＊，ｂｎ＋３＊）とベクトル（ｖ１→，…，ｖｍ→）とを用い、ベクトル（ｖ１→，…，ｖｍ→）に対応する鍵情報
【０１０７】
【数２３】
0005486519.tif 000026
が生成されて出力される。但し、
【０１０８】
【数２４】
0005486519.tif 000027
である。
【０１０９】
《Ｄｅｌｅｇａｔｅ（ｍ’）：鍵情報生成委譲》
−入力：公開パラメータｍｐｋ，鍵情報ｋｍ’＊，ベクトルｖｍ’＋１→
−出力：ベクトル（ｖ１→，…，ｖｍ’＋１→）に対応する鍵情報ｋｍ’＋１＊
階層的内積述語暗号方式では、マスタ鍵情報ＭＳＫを用いることなく、公開パラメータｍｐｋ，鍵情報ｋｍ’＊，ベクトルｖｍ’＋１→からベクトル（ｖ１→，…，ｖｍ’＋１→）に対応する鍵情報ｋｍ’＋１＊を生成できる。但し、ｍ’＝１，…，ｄ−１である。
【０１１０】
Ｄｅｌｅｇａｔｅ（ｍ’）の一例では、有限体Ｆｑから元σ’α，ω，Ψ’，Φ’α∈Ｆｑ（α＝０，…，ｍ’＋２，ξｍ’＋１＋１，…，ｎ；ω＝１，…，ｍ’＋１）が任意に選択される。この例では、これらと鍵情報ｋｍ’＊とベクトルｖｍ’＋１→と用い、ベクトル（ｖ１→，…，ｖｍ’＋１→）に対応する鍵情報
【０１１１】
【数２５】
0005486519.tif 000028
が生成されて出力される。但し、
【０１１２】
【数２６】
0005486519.tif 000029
である。
【０１１３】
《Ｅｎｃ：暗号化》
−入力：公開パラメータｍｐｋ，ベクトル（ｗ１→，…，ｗｍ→），平文ｍｅｓ
−出力：暗号文（Ｃ１，Ｃ２）
Ｅｎｃの一例では、まず、有限体Ｆｑから任意の元υ１，…，υｄ，υｎ＋３，υが選択される。そして、これらと公開パラメータｍｐｋとベクトル（ｗ１→，…，ｗｍ→）とを用い、暗号文
【０１１４】
【数２７】
0005486519.tif 000030
が生成される。また、ｇＴτ・υを共通鍵Ｋとし、所定の共通鍵暗号方式（第２暗号方式）に則って平文ｍｅｓの暗号文Ｃ２が生成される。暗号文Ｃ２の一例は、
C2=gTτ・υ・mes(52)
である。なお、前述のように定数τの一例はτ＝１Ｆである。その後、以上のように生成された暗号文（Ｃ１，Ｃ２）が出力される。
【０１１５】
《Ｄｅｃ：復号》
−入力：公開パラメータｍｐｋ，ベクトル（ｖ１→，…，ｖｍ→）に対応する鍵情報ｋｍ＊，暗号文（Ｃ１，Ｃ２）
−出力：復号値ｍｅｓ’
Ｄｅｃの一例では、
mes’=C2/e(C1,km,0*)     (53)
によって復号値ｍｅｓ’を計算する。
【０１１６】
暗号文Ｃ１と鍵情報ｋｍ＊のｋｍ，０＊とが式（１）の双線形写像ｅ（この例ではζ＝３）に入力されると、式（２）（２５）の性質から、
【０１１７】
【数２８】
0005486519.tif 000031
【０１１８】
を満たす。なお、σω及びσは有限体Ｆｑの元である。Ｄｅｌｅｇａｔｅ（ｍ’）がなされることなく鍵情報ｋｍ＊が生成された場合にはσω＝σ０，ωである。Ｄｅｌｅｇａｔｅ（ｍ’）が１回以上なされた場合には、ＧｅｎＫｅｙに使用された有限体Ｆｑの元σα，ωやＤｅｌｅｇａｔｅ（ｍ’）時に使用された有限体Ｆｑの元σ’α，ωやΦ’αに応じてσωの値が定まる。ここで、全てのω＝１，…，ｍについて内積ｖω→・ｗω→＝０Ｆであれば、式（５４）は、
e(C1,km,0*)=gTτ・υ     (55)
と変形できる。式（５２）（５３）（５５）より、全てのω＝１，…，ｍについて内積ｖω→・ｗω→＝０Ｆである場合にｍｅｓ’＝ｍｅｓとなり、正しく復号がなされることが分かる。
【０１１９】
＜第一実施形態＞
以下に説明する情報処理では、文字列を含む情報が暗号化の対象となるが、暗号処理の実際では、人間が意味内容を認識可能なテキスト情報である文字そのものが暗号化されるのではなく、例えば当該文字に割り当てられている文字コード情報（EUC-JP、Shift_JIS、UTF-8などのバイト表現）が暗号化の対象となる。従って、後述の説明において例えば変数Ｘに文字ｗを代入ないし設定する（Ｘ＝ｗ）とは、テキスト情報としての文字ｗを変数Ｘに代入ないし設定することではなく、文字コード情報としての文字ｗを変数Ｘに代入ないし設定することと理解するべきである。このことは暗号処理の常套手段であるから、その詳細な説明を省略する。また、この明細書では、ベクトルの表記として慣用的にベクトルであることを示す記号“→”を省略している場合がある。従って、或る記号がベクトルであるか否かは明細書全体の記載から合理的に理解されたい。
【０１２０】
＜ポイント＞
式（３２）等で用いる述語ベクトルｖ→及び式（３４）等で用いる属性ベクトルｗ→の構成方法が従来の方法と異なる。まず、従来技術の述語ベクトル及び属性ベクトルの構成方法について説明する。
【０１２１】
従来の内積述語検索可能暗号（非特許文献１及び２参照）は、属性ベクトルや述語ベクトルをキーワードに見立てて、属性ベクトルを使って作成された暗号文が述語ベクトルを使って復号できるとき、暗号文中にキーワードが存在すると判定する暗号文検索技術である。この場合、属性ベクトルは最大文字数をｒとして、述語論理に最大ｄ−１回の論理和が許される場合に、ｒ個の属性変数Ｘ１，…，Ｘｒからなる次数ｄ以下の単項式を全て辞書式順序で並べた順に各成分とした変数ベクトルＸ→ｒ，ｄに登録用キーワードに含まれる文字を設定して得られるベクトルである。また、この場合、述語ベクトルは述語論理を属性変数と検索用キーワードに含まれる文字を用いて多項式で表現した述語多項式の係数を、変数ベクトルＸ→ｒ，ｄの成分に対応する順に並べたものを成分として持つベクトルである。
【０１２２】
本実施形態では集合部分一致検索が可能になる述語多項式ｐｐｍ１を与える。集合部分一致検索を行うことで、検索用情報が複数の要素からなる場合であっても１回の検証により判定することができる。さらに変形例１ではその効率的な表現を与える。そのために、まずキーワードの部分一致検索（非特許文献１参照）を表現する多項式とそのベクトル長を説明する。キーワード部分一致検索は検索用キーワードに部分的に一致するもの全てを見つける検索である。集合部分一致検索と異なる点は、キーワード部分一致検索は文字の順序（ＡＢＢという文字列の検索は、｛Ａ、Ｂ、Ｂ｝＝｛Ａ、Ｂ｝をＡ⇒Ｂ⇒Ｂの順に含まなければならない）含めて一致したものを検索するが、集合部分一致検索は｛Ａ、Ｂ、Ｂ｝＝｛Ａ、Ｂ｝を含むものが検索されることである。
【０１２３】
従来技術で用いる部分一致検索は、検索用キーワードが、登録用キーワードに当てはまりうる全てのパターンを述語で記述することで実現できる。例えば、登録用キーワードの文字数ｔｒ＝６、検索用キーワードが「ＡＢＣＡ」である時、検索用キーワードの文字数ｔｓ＝４であることから、登録用キーワードが検索用キーワードの含むその含み方は全部でｔｒ−ｔｓ＋１＝３通りである。具体的には、「ABCA**」、「*ABCA*」、「**ABCA」の３通りである。但し、「＊」は任意の文字を表す。従って、これらを論理和でつないだ述語論理を考えればよい。このことから、部分一致検索のための述語多項式ｐｐｍ（Ｘ１，…，Ｘｔｒ）は、
【０１２４】
【数２９】
0005486519.tif 000032
【０１２５】
と書ける（但し、ｒｄｉ，ｊは乱数を表す）。この述語多項式の単項式の数ｎは
２ｔｒ−ｔｓ＋１≦ｎ≦ｔｒ−ｔｓ＋１Ｈｔｓ
である。但し、添え字のｔｒ、ｔｓはそれぞれｔｒ、ｔｓを意味し、ｔｒ−ｔｓ＋１Ｈｔｓはｔｒ−ｔｓ＋１個のものから重複してｔｓ個のものを選ぶ組み合わせの総数を表す。従来技術の上記式（６１）を用いて、集合部分一致検索を実現しようとすると、検索用キーワードを構成する各文字「Ａ」、「Ｂ」、「Ｃ」をそれぞれ、検索用キーワードとして、部分一致検索を行い、全ての検索においてヒットした登録用キーワードを検索結果とすると考えられる。登録用キーワードの文字の中に、検索用キーワードの文字が全て登場するか否かを一回の検証（内積）で判定することができず、演算時間が長くなる。
【０１２６】
一方、第一実施形態では、集合部分一致検索が可能になる述語多項式ｐｐｍ１を与える。Ｆｑを位数ｑの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Ｆｑの元で表現されるｔｒとし、ｒｄ１，…，ｒｄｔｒを乱数とする。
【０１２７】
【数３０】
0005486519.tif 000033
【０１２８】
ｐｐｍ１は登録用キーワードと検索用キーワードの格納領域（変数）の長さをどちらもｔｒとしている。登録用キーワード及び検索用キーワードの文字数がｔｒ未満だった場合、記号⊥に対応する文字をそれ以降に格納していくことで対応する。ｐｐｍを利用して達成する部分一致検索は、文字列ｓ１…ｓｔｓが文字列Ｘ１…Ｘｔｒのどこかに含まれることを文字の順序を含めてチェックする検索であったが、ｐｐｍ１を利用して達成する検索は、ｓ１…ｓｔｒを文字列としてまとめてとらえるのではなく、文字ｓ１、…、ｓｔｓと一つ一つ個別に、文字列Ｘ１…Ｘｔｒの中に含まれているかどうかをチェックするものである。文字ｓ１、…、ｓｔｒが順序に関係なく、文字列Ｘ１…Ｘｔｒの中に全て含まれる場合には、ｐｐｍ１＝０となる。文字列として含まれている場合は、個別の文字として含まれている場合に含まれるので、ｐｐｍ１による検索結果はｐｐｍを含む。ｐｐｍ１は単純に展開すると、
【０１２９】
【数３１】
0005486519.tif 000034
【０１３０】
となる。式（６３）は、Ｘ１，…，Ｘｔｒの基本対称式の線形和に出てくる全ての単項式と同様の単項式（（２ｔｒ−１）個）と、定数項（１個）とを持つ。よって、式（６３）は２ｔｒ個の単項式を持つ。なお、Ｘ１，…，Ｘｔｒのｋ次の基本対称式をＹｋとすると、
【０１３１】
【数３２】
0005486519.tif 000035
【０１３２】
であり、具体的には、
Ｙ１＝−（Ｘ１＋Ｘ２＋…＋Ｘｔｒ）
Ｙ２＝Ｘ１Ｘ２＋Ｘ１Ｘ３＋…＋Ｘ１Ｘｔｒ＋Ｘ２Ｘ３＋…＋Ｘｔｒ−１Ｘｔｒ
…
Ｙｔｒ＝（−１）ｔｒＸ１Ｘ２…Ｘｔｒ
である。なお、Ｘ１，…，Ｘｔｒの基本対称式の線形和とは、ｔｒ個のｋ次の基本対称式Ｙｋの線形和である。本実施形態では、各単項式の値または定数１を要素とする属性ベクトルｗ→を構成し、各単項式の係数の値または定数１に対応する値ａ０を要素とする述語ベクトルｖ→を構成する。つまり、
ｗ→＝（１，Ｘ１，Ｘ２，…，Ｘｔｒ，Ｘ１Ｘ２，…，Ｘ１Ｘ２…Ｘｔｒ）
ｖ→＝（ａ０，ａ１，…，ａ（２＾ｔｒ）−１）
である。但し、（Ｃ＾Ｄ）はＣのＤ乗を表す。よって、各ベクトルの次元は２ｔｒ次元である。内積述語暗号検索可能暗号の検索時間は
演算時間＝各種暗号基本演算（ペアリング演算等）×ベクトルの次元×タグの数（文書数）
である。部分一致検索におけるベクトルの次元数ｎ（但し、２ｔｒ−ｔｓ＋１≦ｎ≦ｔｒ−ｔｓ＋１Ｈｔｓ）はｔｒ−ｔｓ＋１Ｈｔｓに近い値をとることとなり、ｔｒの値が大きくなるにつれて、その傾向は顕著になると考えられ、本実施形態の次元数２ｔｒよりも大きくなる。そのため、ｔｒが大きくなるにつれて、本実施形態の検索システムのほうが、従来技術に比べ、検索時間が短くなる。
【０１３３】
＜検索システム１＞
以下、図１を用いて第一実施形態に係る検索システム１を説明する。検索システム１は、上述の述語多項式ｐｐｍ１を内積述語暗号に適用する（参考文献３及び４参照）。
（参考文献３）：T. Okamoto and K. Takashima. "Hierarchical predicate encryption for inner-products", In ASIACRYPT, 2009, pp. 214-231, 
（参考文献４）：A. B. Lewko, T. Okamoto, A. Sahai, K. Takashima, and B. Waters. "Fullysecure functional encryption: Attribute-based encryption and (hierarchical)
inner product encryption", In EUROCRYPT, 2010, pp. 62-91
検索システム１は、暗号化されたデータベースの検索が可能な検索可能暗号システムである。この実施形態の検索システム１は、図１に示すように、属性ベクトル生成装置１１と、述語ベクトル生成装置１５と、判定装置１６と、保管装置１３とを少なくとも含んで構成される。これらの各装置は、例えばインターネットである通信網１２を介して相互に通信可能とされている。
【０１３４】
検索システム１における検索処理を、図２を参照しながら叙述する。各装置の機能構成については、図３を参照されたい。
【０１３５】
＜事前処理＞
前述したＳｅｔｕｐが実行され、マスタ鍵情報ｍｓｋ，公開パラメータｍｐｋが定められる。マスタ鍵情報ｍｓｋは、マスタ鍵格納部１５３に安全に格納され、属性ベクトル生成装置１１、述語ベクトル生成装置１５、判定装置１６が、公開パラメータｍｐｋを用いた処理が可能なように構成される。
【０１３６】
＜暗号情報及び検索タグの登録処理＞
まず、属性ベクトル生成装置１１の暗号情報生成部１１１は、文字列を含む情報（以下「検索対象情報」という）Ｔｅｘｔｔｉを暗号化して暗号情報ＣＴ（Ｔｅｘｔｔｉ）を得る（ステップＳ２）。この暗号方式（Ｅｎｃ，Ｄｅｃ）に限定はない。この暗号方式として、例えば共通鍵暗号方式や公開鍵暗号方式を利用できる。共通鍵暗号方式の場合、検索対象情報Ｔｅｘｔｔｉは、属性ベクトル生成装置１１と述語ベクトル生成装置１５との間で共有される共通鍵で暗号化される。また、公開鍵暗号方式の場合、検索対象情報Ｔｅｘｔｔｉは述語ベクトル生成装置１５の公開鍵で暗号化される。つまり、暗号情報ＣＴ（Ｔｅｘｔｔｉ）を得るための情報処理は、暗号化アルゴリズムＥｎｃに従う。
【０１３７】
生成された暗号情報ＣＴ（Ｔｅｘｔｔｉ）は、検索対象情報Ｔｅｘｔｔｉに対応する登録用キーワードＸとともに、登録キーワード格納部１１４に格納される。登録用キーワードＸは、例えば、ユーザによって予め設定される、検索対象となるキーワードであり、検索対象情報Ｔｅｘｔｔｉに含まれるキーワードまたはキーワードの集合である。
【０１３８】
次に、属性ベクトル生成装置１１の属性ベクトル生成部１１３は、登録キーワード格納部１１４から、検索対象情報Ｔｅｘｔｔｉに対応する登録用キーワードＸを抽出し、登録用キーワードＸを表す属性ベクトルｗ→が以下の関係を満たすように生成する。この属性ベクトルｗ→は、検索において、文書等を検索するためのインデックスとしての役割を持つ。なお、ｔｒ文字の登録用キーワードＸのｉ番目の文字をＸｉ（１≦ｉ≦ｔｒ）とし、登録用キーワードＸの文字列をＸ１，…，Ｘｉ，…，Ｘｔｒとする。また、後述するｔｒ文字の検索用キーワードｓのｉ番目の文字をｓｉ（１≦ｉ≦ｔｒ）とし、検索用キーワードｓの文字列をｓ１，…，ｓｉ，…，ｓｔｒとする。また、ｒｄ１，…，ｒｄｔｒを乱数とし、図示しない乱数生成部により生成される。
【０１３９】
【数３３】
0005486519.tif 000036
【０１４０】
但し、述語多項式ｐｐｍ１は登録用キーワード及び後述する検索用キーワードの格納領域（変数）の長さをｔｒとする。各キーワードの長さがｔｒ未満の場合、記号⊥に対応する文字をｔｒに達するまで格納することで対応する。また、登録用キーワードのｔｒ番目の格納領域には記号⊥に対応する文字を格納する。つまり、登録用キーワードは実質的には最大（ｔｒ−１）文字である。登録用キーワードに記号⊥に対応する文字が含まれていない場合、登録用キーワードの文字の中に、ｔｒ未満の検索用キーワードに含まれる全ての文字が含まれている場合であっても、記号⊥に対応する文字が含まれていないために、検索されないことが生じうるが、このような構成とすることで、漏れを防ぐことができる。
【０１４１】
式（６２）の述語多項式ｐｐｍ１を単純に展開すると、
【０１４２】
【数３４】
0005486519.tif 000037
となる。本実施形態では、各単項式の値または定数１を要素とする属性ベクトルｗ→を構成する。つまり、属性ベクトル
ｗ→＝（１，Ｘ１，Ｘ２，…，Ｘｔｒ，Ｘ１Ｘ２，…，Ｘ１Ｘ２…Ｘｔｒ）        （６４）
を生成する（ステップＳ３）。つまり、属性ベクトル生成装置１１の属性ベクトル生成部１１３は、各単項式Ｘ１，Ｘ２，…，Ｘｔｒ，Ｘ１Ｘ２，…，Ｘ１Ｘ２…Ｘｔｒに対し、具体的な登録用キーワードＸの文字Ｘ１，…，Ｘｔｒを与え、各単項式の値を計算し、計算結果を求める。この計算結果と定数１を要素とする属性ベクトルを生成する。属性ベクトル生成部１１３は、生成した属性ベクトルｗ→を検索タグ生成部１１２へ出力する。
【０１４３】
検索タグ生成部１１２は、公開パラメータＰＫと属性ベクトルｗ→を入力とし、式（３４）により、暗号文Ｃ１を生成する。
【０１４４】
C1=υ0・(Σμ=1nwμ・bμ)+Σμ=n+1n+ζυμ-n・bμ∈G1n+ζ     (34)
なお、式（３４）において、乱数ν０，ν１，…，νζは、検索タグ生成部１１２内部の図示しない乱数生成部により生成する。なお式（３４）において、ｎ＝２ｔｒである。
【０１４５】
さらに、検索タグ生成部１１２は、公開パラメータＰＫと登録用キーワードＸを入力とし、式（３６）により、暗号文Ｃ２を生成する。
【０１４６】
C2=gTτ・υ1・mes(36)
なお、式（３６）において、ｍｅｓ＝Ｘである。
【０１４７】
検索タグ生成部１１２は、上述の処理により得られた暗号文Ｃ１，Ｃ２の組合せを検索タグＴａｇｔｉ＝（Ｃ１，Ｃ２）として出力する（ステップＳ４）。
【０１４８】
属性ベクトル生成装置１１の送信部１１８は、暗号情報ＣＴ（Ｔｅｘｔｔｉ）と検索タグＴａｇｔｉとを一組として保管装置１３へ送信する（ステップＳ５）。保管装置１３の受信部１３９は、暗号情報と検索タグとの組（Ｔｅｘｔｔｉ，Ｔａｇｔｉ）を受信する（ステップＳ６）。保管装置１３の記憶部１３１には、通常、属性ベクトル生成装置１１から受信した複数の（Ｔｅｘｔｔｉ，Ｔａｇｔｉ）が記憶されている。さらに言えば、保管装置１３の記憶部１３１には、一般的に、複数の属性ベクトル生成装置から受信した複数の（Ｔｅｘｔｔｉ，Ｔａｇｔｉ）が記憶されている。各組（Ｔｅｘｔｔｉ，Ｔａｇｔｉ）には固有のインデックスが割り当てられている。
【０１４９】
＜復号鍵（検索クエリ）生成処理＞
述語ベクトル生成装置１５は、検索用キーワードｓを入力されると、述語ベクトル生成部１５１において、検索用キーワードｓを表す述語ベクトルｖ→を以下の関係を満たすように生成する。なお、この述語ベクトルｖ→は検索において、文書等を検索するためのクエリの役割を持つ。
【０１５０】
【数３５】
0005486519.tif 000038
ｐｐｍ１を単純に展開すると、
【０１５１】
【数３６】
0005486519.tif 000039
【０１５２】
となり、本実施形態では、定数１に対応する値ａ０と各単項式の係数の値を要素とする述語ベクトルｖ→を構成する。つまり、述語ベクトル
【０１５３】
【数３７】
0005486519.tif 000040
【０１５４】
を生成する（Ｓ７）。式（６２）から各単項式の係数は、ｓｉの冪乗（つまりｓｉｋ（但し、０≦ｋ≦ｔｒ））と乱数ｒｄｊの積の和からなる。つまり、述語ベクトル生成装置１５の述語ベクトル生成部１５１は、定数１に対応する値ａ０、各単項式の係数ａ１，…，ａ（２＾ｔｒ）−１に対し、具体的な検索用キーワードｓの文字ｓ１，…，ｓｔｒを与え、さらに乱数ｒｄｊを生成し、これらの値を用いて、値ａ０及び各係数を計算し、計算結果を求める。この計算結果を要素とする述語ベクトルを生成する。
【０１５５】
述語ベクトル生成装置１５の鍵生成部１５２は、マスタ鍵情報ＭＳＫと述語ベクトルｖ→を入力とし、式（３２）により、述語ベクトルｖ→に対応する復号鍵Ｄ＊を生成する（ステップＳ８）。
【０１５６】
D*=σ・(Σμ=1nvμ・bμ*)+Σι=n+1n+ζ'σι-n・bι*∈G2n+ζ’     (32)
但し、乱数や定数等であるσ、σι-ｎは鍵生成部１５２において、生成されるか、または、予め鍵生成部１５２に記憶されているものとする。
【０１５７】
述語ベクトル生成装置１５の送信部１５８は、復号鍵Ｄ＊を判定装置１６へ送信する（ステップＳ９）。
【０１５８】
＜判定処理＞
判定装置１６の受信部１６９は、復号鍵Ｄ＊を受信する（ステップＳ１０）。
【０１５９】
判定装置１６の制御部１６５は、送信部１６８を制御して、保管装置１３に対して保管装置１３の記憶部１３１に記憶されている全ての検索タグを判定装置１６へ送信するように要求し、これを受けて保管装置１３の送信部１３８は記憶部１３１に記憶されている全ての検索タグをインデックスとともに判定装置１６へ送信し、判定装置１６の受信部１６９がこれらを受信する（ステップＳ１１）。
【０１６０】
判定装置１６の復号判定部１６１は、全ての検索タグを復号判定処理の対象とし、復号鍵Ｄ＊を用いて検索タグを個別に復号して検索が当たりか否かを判定する（ステップＳ１２）。具体的には、復号判定部１６１は、全ての検索タグについて、式（３８）に従って、ｅ（Ｃ１，Ｄ＊）を求め、式（３６）、（３７）、（３９）から、ｍｅｓ’＝ｍｅｓの成否を判定する（判定処理）。
【０１６１】
C2=gTτ・υ1・mes(36)
mes’=C2/e(C1,D*)∈GT     (37)
【０１６２】
【数３８】
0005486519.tif 000041
【０１６３】
【数３９】
0005486519.tif 000042
【０１６４】
内積ｗ→・ｖ→＝０であれば、ｍｅｓ’＝ｍｅｓとなり、登録用キーワードＸの文字Ｘ１，Ｘ２，…，Ｘｔｒの中に、検索用キーワードｓの文字ｓ１，ｓ２，…，ｓｔｒが含まれていることが分かる。
【０１６５】
判定装置１６の送信部１６８は、ｍｅｓ’＝ｍｅｓが成立した検索タグのインデックスを述語ベクトル生成装置１５へ送信する（ステップＳ１３）。
【０１６６】
述語ベクトル生成装置１５の受信部１５９は、ｍｅｓ’＝ｍｅｓが成立した検索タグのインデックスを受信する（ステップＳ１４）。
【０１６７】
述語ベクトル生成装置１５の制御部１５５は、送信部１５８を制御して、保管装置１３に対して、保管装置１３の記憶部１３１に記憶されている、判定装置１６から受信したインデックスに対応する暗号情報を述語ベクトル生成装置１５へ送信するように要求し、これを受けて保管装置１３の送信部１３８は当該インデックスに対応する暗号情報を述語ベクトル生成装置１５へ送信し、述語ベクトル生成装置１５の受信部１５９がこれらを受信する（ステップＳ１５）。
【０１６８】
述語ベクトル生成装置１５の復号部１５６は、必要に応じて、保管装置１３から受信した暗号情報ＣＴ（Ｔｅｘｔｔｉ）を復号して検索対象情報Ｔｅｘｔｔｉを得る（ステップＳ１６）。検索対象情報Ｔｅｘｔｔｉを得るための情報処理は、属性ベクトル生成装置１１の暗号情報生成部１１１が実施した暗号方式（Ｅｎｃ，Ｄｅｃ）に対応する復号アルゴリズムＤｅｃに従う。
【０１６９】
＜効果＞
このような構成とすることで、複数の文字からなる検索用キーワードが登録用キーワード内に含まれるか否かを１回の検証により判定することができるという効果を奏する。
【０１７０】
なお、本実施形態において、登録用情報及び検索用情報の単位をキーワードとし、それぞれの要素を文字としているが、登録用情報の単位を文章とし、登録用情報及び検索用情報の要素を単語としてもよい。これは、例えば検索対象情報が英文等である場合、登録用情報を検索対象情報でもある英文自体とし、その英文の単語を要素として、属性ベクトルを構成し、複数の単語を述語ベクトルとして表現し検索することができる。また例えば和文の場合には、形態素解析等を行うことで同様に登録用情報の単位を文章とし、登録用情報及び検索用情報の要素を単語とすることができる。
【０１７１】
＜変形例１＞
第一実施形態と異なる部分を主に説明する。
【０１７２】
属性ベクトル生成装置１１の属性ベクトル生成部１１３と述語ベクトル生成装置１５の述語ベクトル生成部１５１の処理内容が第一実施形態と異なる。他の処理は第一実施形態と同様である。
【０１７３】
属性ベクトル生成装置１１の属性ベクトル生成部１１３は、登録キーワード格納部１１４から、検索対象情報Ｔｅｘｔｔｉに対応する登録用キーワードＸを抽出し、登録用キーワードＸを表すベクトルｗ→が以下の関係を満たすように生成する。
【０１７４】
【数４０】
0005486519.tif 000043
【０１７５】
式（６２）の述語多項式ｐｐｍ１を変形して、−Ｘ１，−Ｘ２，…，−Ｘｔｒのｋ次基本対称式Ｙｋを用いて、属性ベクトルｗ→＝｛Ｙ０，Ｙ１，…，Ｙｋ，…，Ｙｔｒ｝を生成する。以下、説明する。
【０１７６】
【数４１】
0005486519.tif 000044
【０１７７】
但し、Ｘ’ｉ＝−Ｘｉであり、Ｙｋは−Ｘ１，−Ｘ２，…，−Ｘｔｒのｋ次の基本対称式であり（但し、Ｙ０＝１とする）、
【０１７８】
【数４２】
0005486519.tif 000045
【０１７９】
である。具体的には、
Ｙ１＝Ｘ１＋Ｘ２＋…＋Ｘｔｒ
Ｙ２＝Ｘ１Ｘ２＋Ｘ１Ｘ３＋…＋Ｘ１Ｘｔｒ＋Ｘ２Ｘ３＋…＋Ｘｔｒ−１Ｘｔｒ
…
Ｙｔｒ＝Ｘ１Ｘ２…Ｘｔｒ
である。また、
【０１８０】
【数４３】
0005486519.tif 000046
である。
【０１８１】
本変形例の属性ベクトル生成部１１３では、登録用キーワードＸを用いて、式（７４）の−Ｘ１，−Ｘ２，…，−Ｘｔｒのｋ次の基本対称式Ｙｋ（但し、Ｙ０＝１とする）から属性ベクトル
【０１８２】
【数４４】
0005486519.tif 000047
【０１８３】
を生成する。つまり、本変形例の属性ベクトル生成部１１３では、各基本対称式Ｙｋに対し、具体的な登録用キーワードＸの文字Ｘ１，…，Ｘｔｒを与え、各基本対称式Ｙｋの値を計算し、計算結果を求める。Ｙ０（＝１）とこの計算結果を要素とする属性ベクトルを生成する。
【０１８４】
また、本変形例の述語ベクトル生成部１５１では、検索用キーワードｓと乱数ｒｄ１，…，ｒｄｔｒを用いて、述語ベクトル
【０１８５】
【数４５】
0005486519.tif 000048
【０１８６】
を生成する。式（７４）から各基本対称式Ｙｋの係数は、Ｖｋ（ｓｊの冪乗と乱数ｒｄｊの積の和）である。つまり、述語ベクトル生成部１５１は、各基本対称式Ｙｋの係数Ｖｋに対し、具体的な検索用キーワードｓの文字ｓ１，…，ｓｔｒを与え、さらに乱数ｒｄｊを生成し、これらの値を用いて、値Ｖ０及びｋ次の基本対称式Ｙｋに対する係数Ｖｋを計算し、計算結果を求める。この計算結果を要素とする述語ベクトルを生成する。
【０１８７】
＜効果＞
このような構成とすることで、属性ベクトル及び述語ベクトルの次元数をｔｒ＋１とすることができる。従来技術や第一実施形態に比べ、ベクトルの次元数を小さくすることができる。なお、ｔｒが大きくなるに従い、次元数の差は大きくなる。よって、演算時間が短くなるという効果が得られる。
【０１８８】
＜変形例２＞
第一実施形態と異なる部分を主に説明する。
【０１８９】
属性ベクトル生成装置１１の属性ベクトル生成部１１３と述語ベクトル生成装置１５の述語ベクトル生成部１５１の処理内容が第一実施形態及びその変形例１と異なる。他の処理は第一実施形態またはその変形例１と同様である。
【０１９０】
属性ベクトル生成装置１１の属性ベクトル生成部１１３は、検索対象情報に対応する登録用情報の要素から重複する要素を削除して属性ベクトルを生成する。
【０１９１】
また、述語ベクトル生成装置１５の述語ベクトル生成部１５１は、検索用情報の要素から重複する要素を削除して述語ベクトルを生成する。
【０１９２】
つまり、キーワードが「ＡＢＣＣＢＡ」の場合、Ａ，Ｂ，Ｃがそれぞれ重複するので、それぞれ重複する要素を削除し、キーワードを「ＡＢＣ」に変換し、変換後のキーワードを用いて属性ベクトル及び述語ベクトルを作成する。なお、削除した格納領域には記号⊥に対応する文字を格納する。
【０１９３】
＜効果＞
このような構成とすることで、属性ベクトル及び述語ベクトルの生成や判定処理の計算量を減らすことができる。なお、集合部分一致検索を行うため、このような構成が可能となるのであって、従来の部分一致検索ではこのような構成とすることはできない。
【０１９４】
＜その他の変形例＞
集合部分一致検索が可能になる述語多項式ｐｐｍ１を与える点がポイントである。よって、必ずしも暗号化されたデータベースの検索が可能な検索可能暗号システムに述語多項式ｐｐｍ１を用いる必要はない。つまり、暗号化されていないデータベースの検索において、述語多項式ｐｐｍ１を利用してもよい。この場合、属性ベクトル生成装置１１には暗号情報生成部１１１や検索タグ生成部１１２は不要であり、述語ベクトル生成装置１５には鍵生成部１５２や復号部１５６やマスタ鍵格納部１５３は不要である。保管装置１３の記憶部１３１には暗号化されていない検索対象情報と、検索対象情報に対応する登録用キーワードから得られる属性ベクトルが記憶される。判定装置１６は述語ベクトル生成装置１５から述語ベクトルを受信し、保管装置１３から属性ベクトルを受信する。そして、判定装置１６の復号判定部１６１では属性ベクトルと述語ベクトルの内積が０か否かを判定し、内積が０となる属性ベクトルに対応する検索対象情報を検索結果として述語ベクトル構成装置に送信する。
【０１９５】
また、少なくとも属性ベクトル生成装置または述語ベクトル生成装置の何れか一方の機能を有する装置をベクトル構成装置と呼ぶ。本実施形態では属性ベクトル生成装置１１と述語ベクトル生成装置１５は別装置として構成しているが、両方の機能を有するベクトル構成装置として構成してもよい。さらに、本実施形態では、ベクトル構成装置と保管装置、判定装置を別装置としているが、同一装置として構成してもよい。同一装置内の検索システムとして利用することができる。
【０１９６】
また、集合部分一致検索を用いているため、文字列Ｘ１…Ｘｔｒや文字列ｓ１…ｓｔｒの順序を入れ替えて、文字の集合Ｘ１，…，Ｘｔｒやｓ１，…，ｓｔｒを用いて属性ベクトル及び述語ベクトルを生成しても第一実施形態と同様の効果を得ることができる。
【０１９７】
なお、属性ベクトル及び述語ベクトルは式（６２）を満たすものであればよい。ここで、式（６２）は、
【０１９８】
【数４６】
0005486519.tif 000049
【０１９９】
と表現される。但し、ｆｐ（Ｘ１，…，Ｘｔｒ）を、変数ｓ１，…，ｓｔｒを含まない登録用情報の要素Ｘ１，…，Ｘｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とする。なお、「変数ｓ１，…，ｓｔｒを含まない」とは、具体的な値ｓｉと同様の値をｆｐ（Ｘ１，…，Ｘｔｒ）中に含む場合はあるが、検索用情報の要素（変数）としてのｓ１，…，ｓｔｒを含まないことを意味する。例えば、ｆｐ（Ｘ１，…，Ｘｔｒ）は、（１）基本対称式の項、（２）基本対称式の項と定数の積、（３）基本対称式の項または基本対称式の項と定数の積の和（４）定数等として表される。また、ｆｐ（ｓ１，…，ｓｔｒ）を変数Ｘ１，…，Ｘｔｒを含まない検索用情報の要素ｓ１，…，ｓｔｒの少なくとも１つ以上を含む単項式若しくは多項式または定数とする。なお、「変数Ｘ１，…，Ｘｔｒを含まない」とは、具体的な値Ｘｉと同様の値をｆｐ（ｓ１，…，ｓｔｒ）中に含む場合はあるが、登録用情報の要素（変数）としてのＸ１，…，Ｘｔｒを含まないことを意味する。例えば、ｆｐ（ｓ１，…，ｓｔｒ）は、（１）ｓｉの冪乗（つまりｓｉｋ（但し、０≦ｋ≦ｔｒ））、（２）ｓｉの冪乗と定数の積、（３）ｓｉの冪乗またはｓｉの冪乗と定数の積の和（４）定数等として表される。Ｐを１以上の整数とする。式（８１）のｆｐ（Ｘ１，…，Ｘｔｒ）及びｆｐ（ｓ１，…，ｓｔｒ）は式（６２）を満たすように適宜設定される。例えば、式（６２）において、ｔｒ＝２の場合、式（６２）を展開すると、
【０２００】
【数４７】
0005486519.tif 000050
【０２０１】
となる。例えば、第一実施形態の場合は、ｆｐ（Ｘ１，…，Ｘｔｒ）をＸｉの基本対称式の単項式または定数とし、ｆｐ（ｓ１，…，ｓｔｒ）を各単項式の係数または定数に対するｓｉの冪乗と定数の積（ｒｄ１ｓ１２＋ｒｄ２ｓ２２）とするので、Ｐ＝４であり、例えば、ｆ１（Ｘ１，Ｘ２）＝１、ｆ２（Ｘ１，Ｘ２）＝−Ｘ１、ｆ３（Ｘ１，Ｘ２）＝−Ｘ２、ｆ４（Ｘ１，Ｘ２）＝Ｘ１Ｘ２であり、ｆ１（ｓ１，ｓ２）＝ｒｄ１ｓ１２＋ｒｄ２ｓ２２、ｆ２（ｓ１，ｓ２）＝ｒｄ１ｓ１＋ｒｄ２ｓ２、ｆ３（ｓ１，ｓ２）＝ｒｄ１ｓ１＋ｒｄ２ｓ２、ｆ４（ｓ１，ｓ２）＝ｒｄ１＋ｒｄ２である。よって、
w→=(1,-X1,-X2,X1X2)
v→=(rd1s12+rd2s22,rd1s1+rd2s2,rd1s1+rd2s2,rd1+rd2)
である。また、例えば、変形例１の場合は、式（７４）よりｆｐ（Ｘ１，…，Ｘｔｒ）を−Ｘｉのｋ次の基本対称式または定数とし、ｆｐ（ｓ１，…，ｓｔｒ）を各基本対称式の係数または定数に対するｓｉの冪乗と定数の積（ｒｄ１ｓ１２＋ｒｄ２ｓ２２）とするので、Ｐ＝３であり、例えば、ｆ１（Ｘ１，Ｘ２）＝１、ｆ２（Ｘ１，Ｘ２）＝Ｘ１＋Ｘ２、ｆ３（Ｘ１，Ｘ２）＝Ｘ１Ｘ２であり、ｆ１（ｓ１，ｓ２）＝ｒｄ１ｓ１２＋ｒｄ２ｓ２２、ｆ２（ｓ１，ｓ２）＝−ｒｄ１ｓ１−ｒｄ２ｓ２、ｆ３（ｓ１，ｓ２）＝ｒｄ１＋ｒｄ２である。よって、
w→=(1,X1+X2,X1X2)
v→=(rd1s12+rd2s22,-rd1s1-rd2s2,rd1+rd2)
となる。また、例えば、ｆｐ（ｓ１，…，ｓｔｒ）をｓｉｋ（但し、０≦ｋ≦ｔｒ）とし、ｆｐ（Ｘ１，…，Ｘｔｒ）を各ｓｉｋの係数とすると、Ｐ＝６であり、例えば、ｆ１（ｓ１，ｓ２）＝ｓ１０、ｆ２（ｓ１，ｓ２）＝ｓ２０、ｆ３（ｓ１，ｓ２）＝ｓ１、ｆ４（ｓ１，ｓ２）＝ｓ２、ｆ５（ｓ１，ｓ２）＝ｓ１２、ｆ６（ｓ１，ｓ２）＝ｓ２２であり、ｆ１（Ｘ１，Ｘ２）＝ｒｄ１Ｘ１Ｘ２、ｆ２（Ｘ１，Ｘ２）＝ｒｄ２Ｘ１Ｘ２、ｆ３（Ｘ１，Ｘ２）＝−ｒｄ１Ｘ１−ｒｄ１Ｘ２、ｆ４（Ｘ１，Ｘ２）＝−ｒｄ２Ｘ１−ｒｄ２Ｘ２、ｆ５（Ｘ１，Ｘ２）＝−ｒｄ１、ｆ６（Ｘ１，Ｘ２）＝ｒｄ２である。よって、
w→=(rd1X1X2,rd2X1X2,-rd1X1-rd1X2,-rd2X1-rd2X2,rd1,rd2)
v→=(s10, s20,s1,s2,s12,s22)
となる。前述の通り、ｆｐ（Ｘ１，…，Ｘｔｒ）及びｆｐ（ｓ１，…，ｓｔｒ）は式（６２）を満たすように適宜設定されるものであり、例えば、ｒｄｊ等はｆｐ（Ｘ１，…，Ｘｔｒ）またはｆｐ（ｓ１，…，ｓｔｒ）に含まれればよい。
【０２０２】
よって、前述の属性ベクトル生成装置は、登録用情報の要素Ｘ１，…，Ｘｔｒを用いて、ｆｐ（Ｘ１，…，Ｘｔｒ）の値を要素とするＰ次元の属性ベクトルを生成する。つまり、属性ベクトル生成装置は、単項式若しくは多項式または定数であるｆｐ（Ｘ１，…，Ｘｔｒ）に対し、具体的な登録用情報の要素Ｘ１，…，Ｘｔｒを与え、ｆｐ（Ｘ１，…，Ｘｔｒ）を計算し、計算結果を求める。この計算結果を要素とするＰ次元の属性ベクトルを生成する。
【０２０３】
前述の述語ベクトル生成装置は、検索用情報の要素ｓ１，…，ｓｔｒを用いて、ｆｐ（ｓ１，…，ｓｔｒ）の値を要素とするＰ次元の述語ベクトルを生成する。つまり、述語ベクトル生成装置は、単項式若しくは多項式または定数であるｆｐ（ｓ１，…，ｓｔｒ）に対し、具体的な検索用情報の要素ｓ１，…，ｓｔｒを与え、ｆｐ（ｓ１，…，ｓｔｒ）を計算し、計算結果を求める。この計算結果を要素とするＰ次元の述語ベクトルを生成する。
＜第二実施形態＞
＜検索システム２＞
以下、図４を用いて第二実施形態に係る検索システム２を説明する。検索システム２は、上述の述語多項式ｐｐｍ１を階層的内積述語暗号に適用する（参考文献３及び４参照）。検索システム１は、暗号化されたデータベースの検索が可能な検索可能暗号システムである。
【０２０４】
図４に例示するように、本形態の検索可能暗号システム２は、管理装置２７−ｍ（ｍ＝１，…，Ｍ）と属性ベクトル生成装置２１（ｕ＝１，…，Ｕ）と判定装置２６と保管装置２３と述語ベクトル生成装置２５（ｕ＝１，…，Ｕ）とを有する。なお、Ｍ及びＵはそれぞれ１以上の整数である。また、管理装置２７−ｍは、検索可能暗号システム１のｍ番目の管理者が使用する装置である。本形態では、小さいｍに対応する管理者ほど強い管理権限を持つ。すなわち、ｍ＝１に対応する管理者が最も強い権限を持つ。また、属性ベクトル生成装置２１及び述語ベクトル生成装置２５は、検索可能暗号システム１を利用するｕ番目の登録ユーザが使用する装置である。また、各装置は他の装置へ情報を提供可能なように構成されている。装置間の情報提供は通信網１２を通じて行われてもよいし、可搬型記録媒体を介して行われてもよい。
【０２０５】
［管理装置２７］
図５Ａは、実施形態の管理装置２７−１の機能構成を説明するための図であり、図５Ｂは、実施形態の管理装置２７−（ｍ’＋１）（ｍ’＝１，…，Ｍ−１）の機能構成を説明するための図である。
【０２０６】
図５Ａに例示するように、管理装置２７−１は、入力部２７１−１と出力部２７２−１とマスタ鍵格納部２７３−１と制御部２７５−１とベクトル設定部２７６ａ−１と鍵情報生成部２７６ｂ−１とを有する。図５Ｂに例示するように、管理装置２７−（ｍ’＋１）は、入力部２７１−（ｍ’＋１）と出力部２７２−（ｍ’＋１）と制御部２７５−（ｍ’＋１）とベクトル設定部２７６ａ−（ｍ’＋１）と鍵情報生成部２７６ｂ−（ｍ’＋１）とを有する。管理装置２７−ｍは、例えば、ＣＰＵ(central processing unit),ＲＡＭ(random-access memory),ＲＯＭ(read-only memory)などを有する公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、管理装置２７−ｍは、それぞれ、制御部２７５−ｍの制御のもと各処理を実行する。また、管理装置２７−ｍでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【０２０７】
［属性ベクトル生成装置２１］
図６は、実施形態の属性ベクトル生成装置２１−ｕの機能構成を説明するための図である。
【０２０８】
図６に例示するように、属性ベクトル生成装置２１−ｕは、入力部２１１−ｕと出力部２１２−ｕと属性格納部２１３ａ−ｕと登録キーワード格納部２１３ｂ−ｕと検索者鍵格納部２１３ｃ−ｕと制御部２１５−ｕと属性ベクトル生成部２１６ｅ−ｕと検索タグ生成部２１６ｆ−ｕとを有する。属性ベクトル生成装置２１は、例えば、公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、属性ベクトル生成装置２１は、それぞれ、制御部２１５−ｕの制御のもと各処理を実行する。なお、属性ベクトル生成装置２１での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【０２０９】
［判定装置２６］
図７は、実施形態の判定装置２６の機能構成を説明するための図である。
【０２１０】
図７に例示するように、判定装置２６は、入力部２６１と出力部２６２と制御部２６５と検証処理部２６７とを有する。判定装置２６は、例えば、公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、判定装置２６は、それぞれ、制御部２６５の制御のもと各処理を実行する。また、判定装置２６での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【０２１１】
［保管装置２３］
図８Ａは、実施形態の保管装置２３の機能構成を説明するための図である。
【０２１２】
図８Ａに例示するように、保管装置２３は、入力部２３１と出力部２３２と暗号化データベース格納部２３３と制御部２３５と読み書き部２３６とを有する。保管装置２３は、例えば、公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、保管装置２３は、制御部１３５の制御のもと各処理を実行する。
【０２１３】
図８Ｂは、暗号化データベース格納部２３３に格納される暗号化データベースのデータ構成を説明するための図である。
【０２１４】
図８Ｂに例示するように、暗号化データベース格納部２３３には、文書などの検索対象情報Ｔｅｘｔｔｉの暗号文ＣＴ（Ｔｅｘｔｔｉ）と検索対象情報Ｔｅｘｔｔｉのキーワードに対応する暗号化情報であるタグ情報Ｔａｇ（ｔｉ，ｕ）とが互いに対応付けられて格納されている。暗号文ＣＴ（Ｔｅｘｔｔｉ）を生成するための検索対象情報Ｔｅｘｔｔｉの暗号化方式には限定はなく、任意の既存の暗号化方式（共通鍵暗号方式，公開鍵暗号方式，関数暗号方式など）でよい。タグ情報Ｔａｇ（ｔｉ，ｕ）は暗号文ＣＴ（Ｔｅｘｔｔｉ）を検索するための情報である。保管装置２３は、タグ情報Ｔａｇ（ｔｉ，ｕ）が与えられても、それに対応する検索キーワードを知ることができない。タグ情報Ｔａｇ（ｔｉ，ｕ）の生成方法の詳細は後述する。
【０２１５】
［述語ベクトル生成装置２５］
図９は、実施形態の述語ベクトル生成装置２５の機能構成を説明するための図である。
【０２１６】
図９に例示するように、述語ベクトル生成装置２５は、入力部２５１−ｕと出力部２５２−ｕと鍵情報格納部２５３−ｕと検索対象情報復号鍵格納部２５４−ｕと制御部２５５−ｕと述語ベクトル生成部２５６−ｕと検索クエリ生成部２５７−ｕと復号部２５８−ｕとを有する。述語ベクトル生成装置２５は、例えば、公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、述語ベクトル生成装置２５は、それぞれ、制御部２５５−ｕの制御のもと各処理を実行する。
【０２１７】
＜事前処理＞
前述したＳｅｔｕｐが実行され、階層フォーマットξ→，マスタ鍵情報ｍｓｋ，公開パラメータｍｐｋが定められる。マスタ鍵情報ｍｓｋは、管理装置２７−１（図５Ａ）のマスタ鍵格納部２７３−１に安全に格納され、管理装置２７−ｍ，属性ベクトル生成装置２１，述語ベクトル生成装置２５及び判定装置２６が、公開パラメータｍｐｋを用いた処理が可能なように構成される。また、管理装置２７−ｍ及び属性ベクトル生成装置２１が階層フォーマットξ→に従った処理が可能なように構成される。
【０２１８】
属性ベクトル生成装置２１（図６）の登録キーワード格納部２１３ｂ−ｕには、登録を行う検索対象情報Ｔｅｘｔｔｉの暗号文ＣＴ（Ｔｅｘｔｔｉ）と検索対象情報Ｔｅｘｔｔｉに対応するキーワードＸとが格納されている。さらに、属性ベクトル生成装置２１の属性格納部２１３ａ−ｕには、属性ベクトル生成装置２１を利用するユーザの属性を表す情報（以下、単に「属性」という）が格納されている。ユーザの属性の例は、ユーザが所属するグループを表す情報（会社名、所属部門、課、担当、グループなど）、住所、年齢、職業、趣味などである。
【０２１９】
述語ベクトル生成装置２５（図９）の検索対象情報復号鍵格納部２５４−ｕには、属性ベクトル生成装置２１（図６）の登録キーワード格納部２１３ｂ−ｕに格納された暗号文ＣＴ（Ｔｅｘｔｔｉ）を復号するための検索対象情報復号鍵Ｋｅｙｔｉが格納されている。
【０２２０】
＜ユーザ登録＞
ユーザ登録では、管理装置２７−ｍが登録ユーザの属性に対して設定されたベクトル（ｖ１→，…，ｖＭ→）に対応する鍵情報ｋＭ＊を生成する。鍵情報ｋＭ＊の生成方式は大きく分けて２通り存在する。
【０２２１】
一つ目の方式は、管理装置２７−１が前述のＧｅｎＫｅｙのみに従って鍵情報ｋＭ＊を生成する方式である（一括方式）。このような方式は小規模グループに適したものであるといえる。二つ目の方式は、管理装置２７−１が前述のＧｅｎＫｅｙに従い、その他の管理装置２７−（ｍ’＋１）が前述のＤｅｌｅｇａｔｅ（ｍ’）に従い、鍵情報ｋＭ＊を生成する方式である（委託方式）。このような方式は階層化された大規模グループに適したものであるといえる。
【０２２２】
［一括方式］
図７は、一括方式によって鍵情報ｋＭ＊を生成する処理を説明するためのフローチャートである。
【０２２３】
一括方式では、最も強い権限をもつｍ＝１に対応する管理者の管理装置２７−１のみによって鍵情報ｋＭ＊を生成する。
【０２２４】
まず、管理装置２７−１（図５Ａ）の入力部２７１−１に登録ユーザの属性ＡＴＴが入力される。属性ＡＴＴはＭ層ＡＴＴ１，…，ＡＴＴＭに階層化されている。各層に対応する属性ＡＴＴｍを部分属性と呼ぶことにし、小さいｍに対応する部分属性ＡＴＴｍほど上位の属性を表すものとする。例えば、Ｍ＝２の場合、属性ＡＴＴは２層の部分属性ＡＴＴ１及びＡＴＴ２からなり、この場合の部分属性の例は、
ATT1=（○○株式会社，○○部門）              …(81)
ATT2=（○○課，○○担当，○○グループ）      …(82)
である。
【０２２５】
入力された属性ＡＴＴはベクトル設定部２７６ａ−１に入力される。ベクトル設定部２７６ａ−１は、階層フォーマットξ→及びシステム内で定められた規則に従って属性ＡＴＴに対応するベクトル（ｖ１→，…，ｖＭ→）を設定する。例えば、ベクトル設定部２７６ａ−１は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、属性ＡＴＴを表すベクトル（ｗ１→，…，ｗＭ→）を式（４１）に従って設定し、内積ｗω→・ｖω→＝０Ｆとなる式（４２）に従ったベクトル（ｖ１→，…，ｖＭ→）を属性ＡＴＴに対応するベクトルとする。式（８１）（８２）の例を用いて説明すると、例えば、ベクトル設定部２７６ａ−１は、部分属性ＡＴＴ１を「○○株式会社」を表すｗ１及び「○○部門」を表すｗ２を要素とする２次元のベクトル
w1→=(w1,w2)          …(83)
に変換し、部分属性ＡＴＴ２を「○○課」を表すｗ３、「○○担当」を表すｗ４、及び「○○グループ」を表すｗ５を要素とする３次元のベクトル
w2→=(w3,w4,w5)          …(84)
に変換し、属性ＡＴＴを表すベクトル（ｗ１→，ｗ２→）＝（ｗ１，ｗ２，ｗ３，ｗ４，ｗ５）を設定し、内積ｗω→・ｖω→＝０Ｆとなるベクトル（ｖ１→，ｖ２→）＝（ｖ１，ｖ２，ｖ３，ｖ４，ｖ５）を属性ＡＴＴに対応するベクトルとする。なお、システム内で定められた規則に基づいて定められるのであれば、属性ＡＴＴを表すベクトル（ｗ１→，…，ｗＭ→）をどのように定めるかについては特に限定はなく、属性ＡＴＴごとにベクトル（ｗ１→，…，ｗＭ→）が定まるのであればどのような方法でもよい。
【０２２６】
生成されたベクトル（ｖ１→，…，ｖＭ→）は鍵情報生成部２７６ｂ−１に入力される。鍵情報生成部２７６ｂ−１は、マスタ鍵格納部２７３−１からマスタ鍵情報ｍｓｋを読み出し、ｍ＝Ｍとした前述のＧｅｎＫｅｙに従い、ベクトル（ｖ１→，…，ｖＭ→）に対応する鍵情報ｋＭ＊を生成する。例えば、鍵情報生成部２７６ｂ−１は、ｍ＝Ｍとした式（４３）−（４６）に従って鍵情報ｋＭ＊を生成する。生成された鍵情報ｋＭ＊は出力部２７２−１に送られる。
【０２２７】
出力部２７２−１は、鍵情報ｋＭ＊（Ｍ≦ｄ−１）を出力する。鍵情報ｋＭ＊は登録ユーザが使用する述語ベクトル生成装置２５（図９）の入力部２５１−ｕに入力され、鍵情報格納部２５３−ｕに格納される。
【０２２８】
［委託方式］
委託方式では、最も強い権限をもつｍ＝１に対応する管理者の管理装置２７−１が前述のＧｅｎＫｅｙに従って鍵情報ｋ１＊を生成し、上位階層の鍵情報を受け取った下位階層の管理者の管理装置２７−（ｍ’＋１）が前述のＤｅｌｅｇａｔｅ（ｍ’）に従って鍵情報を生成していき、最終的に鍵情報ｋＭ＊が生成される。
【０２２９】
まず、管理装置２７−１（図５Ａ）の入力部２７１−１に登録ユーザの部分属性ＡＴＴ１が入力される。
【０２３０】
入力された部分属性ＡＴＴ１はベクトル設定部２７６ａ−１に入力される。ベクトル設定部２７６ａ−１は、階層フォーマットξ→及びシステム内で定められた規則に従って部分属性ＡＴＴ１に対応するベクトルｖ１→を設定する。例えば、ベクトル設定部２７６ａ−１は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、部分属性ＡＴＴ１を表すベクトルｗ１→を式（４１）に従って設定し、内積ｗ１→・ｖ１→＝０Ｆとなる式（４２）に従ったベクトルｖ１→を部分属性ＡＴＴ１に対応するベクトルとする。式（８１）（８２）の例を用いて説明すると、例えば、ベクトル設定部２７６ａ−１は、式（８３）によって部分属性ＡＴＴ１を表すベクトルｗ１→を設定し、内積ｗ１→・ｖ１→＝０Ｆとなる式（８４）のベクトルｖ１→を、部分属性ＡＴＴ１に対応するベクトルとする。
【０２３１】
生成されたベクトルｖ１→は鍵情報生成部２７６ｂ−１に入力される。鍵情報生成部２７６ｂ−１は、マスタ鍵格納部２７３−１からマスタ鍵情報ｍｓｋを読み出し、ｍ＝１とした前述のＧｅｎＫｅｙに従い、ベクトルｖ１→に対応する鍵情報ｋ１＊を生成する。例えば、鍵情報生成部２７６ｂ−１は、ｍ＝１とした式（４３）−（４６）に従って鍵情報ｋ１＊を生成する。生成された鍵情報ｋ１＊は出力部２７２−１に送られる。
【０２３２】
鍵情報ｋ１＊は管理装置２７−２に入力される。管理装置２７−２以降では前述したＤｅｌｅｇａｔｅ（ｍ’）（ｍ’＝１，…，Ｍ−１）に従って鍵生成が行われる。以下では管理装置２７−ｍ’から鍵情報ｋｍ’＊を受け取る管理装置２７−（ｍ’＋１）の処理を一般化して説明する。
【０２３３】
まず、鍵情報ｋｍ’＊が管理装置２７−（ｍ’＋１）（図５Ｂ）の入力部２７１−（ｍ’＋１）に入力され、鍵情報生成部２７６ｂ−（ｍ’＋１）に入力される。また、部分属性ＡＴＴｍ’＋１がベクトル設定部２７６ａ−（ｍ’＋１）に入力される。ベクトル設定部２７６ａ−（ｍ’＋１）は、階層フォーマットξ→及びシステム内で定められた規則に従って部分属性ＡＴＴｍ’＋１に対応するベクトルｖｍ’＋１→を設定する。例えば、ベクトル設定部２７６ａ−（ｍ’＋１）は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、部分属性ＡＴＴｍ’＋１を表すベクトルｗｍ’＋１→を式（４１）に従って設定し、内積ｗｍ’＋１→・ｖｍ’＋１→＝０Ｆとなる式（４２）に従ったベクトルｖｍ’＋１→を部分属性ＡＴＴｍ’＋１に対応するベクトルとする。生成されたベクトルｖｍ’＋１→は鍵情報生成部２７６ｂ−（ｍ’＋１）に入力される。
【０２３４】
鍵情報ｋｍ’＊とベクトルｖｍ’＋１→とが入力された鍵情報生成部２７６ｂ−（ｍ’＋１）は、前述のＤｅｌｅｇａｔｅ（ｍ’）に従って、ベクトル（ｖ１→，…，ｖｍ’＋１→）に対応する鍵情報ｋｍ’＋１＊を生成する。例えば、鍵情報生成部２７６ｂ−（ｍ’＋１）は、式（４７）−（５０）に従って鍵情報ｋｍ’＋１＊を生成する。生成された鍵情報ｋｍ’＋１＊は出力部２７２−（ｍ’＋１）に送られる。出力部２７２−（ｍ’＋１）は鍵情報ｋｍ’＋１＊を出力する。
【０２３５】
ｍ’＋１＜Ｍの場合、出力された鍵情報ｋｍ’＋１＊は下位階層の管理装置２７−（ｍ’＋２）に入力され、ｍ’＋１を新たなｍ’として同様の処理が実行される。一方、ｍ’＋１＝Ｍの場合、出力された鍵情報ｋｍ’＋１＊＝ｋＭ＊は、登録ユーザが使用する述語ベクトル生成装置２５（図９）の入力部２５１−ｕに入力され、鍵情報格納部２５３−ｕに格納される。
【０２３６】
＜データベース登録＞
登録ユーザは属性ベクトル生成装置２１を用い、以下のようにデータベース登録を行うことができる。
【０２３７】
まず、属性ベクトル生成装置１１の属性ベクトル生成部１１３は、登録キーワード格納部１１４から、検索対象情報Ｔｅｘｔｔｉに対応する登録用キーワードＸを抽出し、登録用キーワードＸを表す属性ベクトルｗＭ＋１→が以下の関係を満たすように生成する。
【０２３８】
【数４８】
0005486519.tif 000051
属性ベクトルｗＭ＋１→の生成方法は第一実施形態及びその変形例と同様である。
【０２３９】
また、属性ベクトル生成部２１６ｅ−ｕが、属性格納部２１３ａ−ｕから登録ユーザの属性ＡＴＴを抽出する。この属性ＡＴＴは当該登録ユーザのユーザ登録時に用いられたものと同じである。属性ベクトル生成部２１６ｅ−ｕは、階層フォーマットξ→及びシステム内で定められた規則に従って属性ＡＴＴを表すベクトル（ｗ１→，…，ｗＭ→）を設定する。当該ベクトル（ｗ１→，…，ｗＭ→）とユーザ登録時のステップＳ１０３で設定されたベクトル（ｖ１→，…，ｖＭ→）とは、ω＝１，…，Ｍについて内積ｗω→・ｖω→＝０Ｆを満たす。
【０２４０】
属性ベクトル生成部２１６ｅ−ｕは、生成したベクトル（ｗ１→，…，ｗＭ→）と属性ベクトルｗＭ＋１→をまとめて検索タグ生成部２１６ｆ−ｕに送る。
【０２４１】
検索タグ生成部２１６ｆ−ｕは、ｗ１→，…，ｗＭ→，ｗＭ＋１→を用い、例えば、ｄ＝Ｍ＋１とした式（５１）に従って暗号文Ｃ１を生成し、ｍｅｓ＝Ｘとした式（５２）に従って暗号文Ｃ２を生成する。検索タグ生成部２１６ｆ−ｕは、上述の処理により得られた暗号文Ｃ１，Ｃ２の組合せを検索タグＴａｇ（ｔｉ，ｕ）＝（Ｃ１，Ｃ２）とする。
【０２４２】
生成されたタグ情報Ｔａｇ（ｔｉ，ｕ）は出力部２１２−ｕに送られる。また、登録キーワード格納部２１３ｂ−ｕから読み出された暗号文ＣＴ（Ｔｅｘｔｔｉ）が出力部２１２−ｕに送られる。出力部２１２−ｕは、暗号文ＣＴ（Ｔｅｘｔｔｉ）とタグ情報Ｔａｇ（ｔｉ，ｕ）とを出力する。これらの組は保管装置２３（図８Ａ）の入力部２３１に入力され、書込み部２３６から暗号化データベース格納部２３３に格納される（図８Ｂ）。
【０２４３】
＜検索＞
登録ユーザは述語ベクトル生成装置２５（図９）を用い、以下のように検索を行うことができる。
【０２４４】
まず、検索を行う登録ユーザによって選択された検索用キーワードｓが入力部２５１−ｕに入力される。検索用キーワードｓは述語ベクトル生成部２５６−ｕに送られる。
【０２４５】
述語ベクトル生成部２５６−ｕにおいて、検索用キーワードｓを表す述語ベクトルｖＭ＋１→を以下の関係を満たすように生成する。
【０２４６】
【数４９】
0005486519.tif 000052
【０２４７】
述語ベクトルｖＭ＋１→の生成方法は第一実施形態及びその変形例と同様である。生成された述語ベクトルｖＭ＋１→は、検索クエリ生成部２５７−ｕに送られる。検索クエリ生成部２５７−ｕは、鍵情報格納部２５３−ｕから鍵情報ｋＭ＊を抽出する。検索クエリ生成部２５７−ｕは、ｋＭ＊，ｖＭ＋１→を用い、ｍ’＝Ｍとした前述のＤｅｌｅｇａｔｅ（ｍ’）によって、ｖ１→，…，ｖＭ→及びｖＭ＋１→に対応する鍵情報（復号鍵）である検索クエリｋＭ＋１＊を生成する。例えば、検索クエリ生成部２５７−ｕは、ｍ’＝Ｍ（Ｍ≦ｄ−１）とした式（４７）−（５０）に従って検索クエリｋＭ＋１＊を生成する。なお、ｍ＝ｄ−１の場合には式（５０）のｋｍ’＋１，α＊を含まない。生成された検索クエリｋＭ＋１＊は出力部２５２−ｕに送られる。出力部２５２−ｕは検索クエリｋＭ＋１＊を出力する。
【０２４８】
検索クエリｋＭ＋１＊は、判定装置２６（図７）の入力部２６１に入力され、検証処理部２６７に送られる。判定装置２６は保管装置２３（図８Ａ）にアクセスし、暗号化データベース格納部２３３に格納されたタグ情報Ｔａｇ（ｔｉ，ｕ）の取得を要求するための情報を出力部２６１から出力する。この情報は保管装置２３の入力部２３１に入力されて読み書き部２３６に送られる。保管装置２３の読み書き部２３６は、暗号化データベース格納部２３３から何れかのタグ情報Ｔａｇ（ｔｉ，ｕ）を読み出し、出力部２３２はそれを判定装置２６に送る。タグ情報Ｔａｇ（ｔｉ，ｕ）は判定装置２６（図７）の入力部２６１に入力され、検証処理部２６７に送られる。
【０２４９】
式（５２）（５３）（５５）より、全てのω＝１，…，Ｍ，Ｍ＋１について内積ｖω→・ｗω→＝０Ｆである場合に、ｍｅｓ’＝ｍｅｓとなる。検証処理部２６７は、公開パラメータｍｐｋと検索クエリｋＭ＋１＊とタグ情報Ｔａｇ（ｔｉ，ｕ）を入力とし、ｍｅｓ’＝ｍｅｓを満たすか否かを検証する。満たす場合には検証合格となる。
【０２５０】
ここで、検証合格とならなかった場合、判定装置２６は保管装置２３に対して未検証のタグ情報Ｔａｇ（ｔｉ，ｕ）が暗号化データベース格納部２３３内に存在するかを問い合わせるための情報を出力部２６２から出力する。この情報は保管装置２３（図８Ａ）の入力部２３１に入力され、読み書き部２３６に送られる。読み書き部２３６は、暗号化データベース格納部２３３を検索して未検証のタグ情報Ｔａｇ（ｔｉ，ｕ）が暗号化データベース格納部２３３内に存在するか否かを判定し、その判定結果が出力部２３２から出力される。判定結果は、判定装置２６（図７）の入力部２６１に入力され、制御部２６５に送られる。ここで、未検証のタグ情報Ｔａｇ（ｔｉ，ｕ）が暗号化データベース格納部２３３内に存在しない旨の応答があった場合、判定装置２６の出力部２６２が「該当なし」を表す⊥を出力して処理を終了する。一方、未検証のタグ情報Ｔａｇ（ｔｉ，ｕ）が暗号化データベース格納部２３３内に存在する旨の応答があった場合には、未検証のタグ情報に対して検証を行う。
【０２５１】
一方、ステップＳ２５７で検証合格となった場合、判定装置２６は保管装置２３に対し、検証合格となったタグ情報Ｔａｇ（ｔｉ，ｕ）に対応する検証対象情報の暗号文ＣＴ（Ｔｅｘｔｔｉ）の出力を要求するための情報を出力部２６２から出力する。この情報は保管装置２３（図８Ａ）の入力部２３１に入力され読み書き部２３６に送られる。読み書き部２３６は、検証合格となったタグ情報Ｔａｇ（ｔｉ，ｕ）に対応する検証対象情報の暗号文ＣＴ（Ｔｅｘｔｔｉ）を暗号化データベース格納部２３３から抽出し、出力部２３２に送る。出力部２３２は暗号文ＣＴ（Ｔｅｘｔｔｉ）を出力する。暗号文ＣＴ（Ｔｅｘｔｔｉ）は、判定装置２６（図７）の入力部２６１に入力され、検証処理部２６７に送られる。暗号文ＣＴ（Ｔｅｘｔｔｉ）は、出力部２６２に送られて出力され、述語ベクトル生成装置（図９）の入力部２５１−ｕに入力される。暗号文ＣＴ（Ｔｅｘｔｔｉ）は、復号部２５８−ｕに送られる。復号部２５８−ｕは検索対象情報復号鍵格納部２５４−ｕから検索対象情報復号鍵Ｋｅｙｔｉを読み出し、これを用いて暗号文ＣＴ（Ｔｅｘｔｔｉ）を復号して検索対象情報Ｔｅｘｔｔｉを出力する。
【０２５２】
＜効果＞
このような構成とすることで、階層的内積述語暗号において部分集合一致検索可能な検索システムを構成することができる。
【０２５３】
＜プログラム及び記録媒体＞
上述した属性ベクトル生成装置、述語ベクトル生成装置、ベクトル構成装置及び判定装置は、コンピュータにより機能させることもできる。この場合はコンピュータに、目的とする装置（各種実施例で図に示した機能構成をもつ装置）として機能させるためのプログラム、またはその処理手順（各実施例で示したもの）の各過程をコンピュータに実行させるためのプログラムを、ＣＤ−ＲＯＭ、磁気ディスク、半導体記憶装置などの記録媒体から、あるいは通信回線を介してそのコンピュータ内にダウンロードし、そのプログラムを実行させればよい。
【０２５４】
＜その他の変形例＞
属性ベクトル生成装置及び述語ベクトル生成装置を関数暗号方式を用いて暗号化されたデータベースの検索が可能な検索可能暗号システムにおいても用いてもよい（参考文献５参照）。
（参考文献５）：Tatsuaki Okamoto, Katsuyuki Takashima, "Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption", Advances in Cryptology - CRYPTO 2010, 2010, p.191-208
【０２５５】
また、本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【０２５６】
１，２  検索システム
１１、２１−ｕ  属性ベクトル生成装置
１２  通信網
１３、２３  保管装置
１５、２５  述語ベクトル生成装置
１６、２６  判定装置
【図１】
0005486519.tif 000063
【図２】
0005486519.tif 000064
【図３】
0005486519.tif 000065
【図４】
0005486519.tif 000066
【図５】
0005486519.tif 000067
【図６】
0005486519.tif 000068
【図７】
0005486519.tif 000069
【図８】
0005486519.tif 000070
【図９】
0005486519.tif 000071