"属性ベクトル生成装置と、述語ベクトル生成装置と、判定装置と、からなる検索システムであって、Fqを位数qの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fqの元で表現されるtrとし、添え字trはtrを意味し、rd1,...,rdtrを乱数とし、検索対象情報に対応する登録用情報の要素をX1,...,Xtrとし、検索用情報の要素をs1,...,strとし、とし、fpX1,...,Xtrを変数s1,...,strを含まないX1,...,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、fps1,...,strを変数X1,...,Xtrを含まないs1,...,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、Pを1以上の整数とし、前記式Aはと表現されるものとし、前記属性ベクトル生成装置は検索対象情報に対応する登録用情報の要素の集合X1,...,Xtrを用いて、前記式BのfpX1,...,Xtrの値を要素とする属性ベクトルを生成し、前記述語ベクトル生成装置は検索用情報の要素の集合s1,...,strを用いて、前記式Bのfps1,...,strの値を要素とする述語ベクトルを生成し、前記判定装置は前記属性ベクトルと前記述語ベクトルとの内積が0のとき、前記検索対象情報に対応する登録用情報中に前記検索用情報が含まれると判定する、検索システム。請求項1記載の検索システムであって、Y0=1とし、前記属性ベクトル生成装置は-X1,-X2,...,-Xtrのk次基本対称式Ykを用いて、k次基本対称式Ykの値を要素とする属性ベクトルw→={Y0,Y1,...,Yk,...,Ytr}を生成し、前記述語ベクトル生成装置はの値を要素とする述語ベクトルv→={V0,V1,...,Vk,...,Vtr}を生成する、検索システム。請求項1または2記載の検索システムであって、前記属性ベクトル生成装置は、検索対象情報に対応する登録用情報の要素の集合から重複する要素を削除して属性ベクトルを生成し、前記述語ベクトル生成装置は、検索用情報の要素の集合から重複する要素を削除して述語ベクトルを生成する、検索システム。請求項1から3の何れかに記載の検索システムにおいて用いられる判定装置。少なくとも属性ベクトルまたは述語ベクトルを生成するベクトル構成装置であって、Fqを位数qの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fqの元で表現されるtrとし、添え字trはtrを意味し、rd1,...,rdtrを乱数とし、検索対象情報に対応する登録用情報の要素をX1,...,Xtrとし、検索用情報の要素をs1,...,strとし、とし、fpX1,...,Xtrを変数s1,...,strを含まないX1,...,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、fps1,...,strを変数X1,...,Xtrを含まないs1,...,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、Pを1以上の整数とし、前記式Aはと表現されるものとし、少なくとも検索対象情報に対応する登録用情報の要素の集合X1,...,Xtrを用いて、前記式BのfpX1,...,Xtrの値を要素とする属性ベクトルを生成するか、前記述語ベクトル生成装置は検索用情報の要素の集合s1,...,strを用いて、前記式Bのfps1,...,strの値を要素とする述語ベクトルを生成する、ベクトル構成装置。請求項5記載のベクトル構成装置であって、Y0=1とし、少なくとも-X1,-X2,...,-Xtrのk次の基本対称式Ykを用いて、k次基本対称式Ykの値を要素とする属性ベクトルw→={Y0,Y1,...,Yk,...,Ytr}として生成するか、の値を要素とする述語ベクトルv→={V0,V1,...,Vk,...,Vtr}を生成する、ベクトル構成装置。請求項6または7記載のベクトル構成装置であって、少なくとも、検索対象情報に対応する登録用情報の要素の集合から重複する要素を削除して属性ベクトルを生成するか、または、検索用情報の要素の集合から重複する要素を削除して述語ベクトルを生成する、ベクトル構成装置。属性ベクトル生成ステップと、述語ベクトル生成ステップと、判定ステップと、からなる検索方法であって、Fqを位数qの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fqの元で表現されるtrとし、添え字trはtrを意味し、rd1,...,rdtrを乱数とし、検索対象情報に対応する登録用情報の要素をX1,...,Xtrとし、検索用情報の要素をs1,...,strとし、とし、fpX1,...,Xtrを変数s1,...,strを含まないX1,...,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、fps1,...,strを変数X1,...,Xtrを含まないs1,...,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、Pを1以上の整数とし、前記式Aはと表現されるものとし、前記属性ベクトル生成ステップにおいて、検索対象情報に対応する登録用情報の要素の集合X1,...,Xtrを用いて、前記式BのfpX1,...,Xtrの値を要素とする属性ベクトルを生成し、前記述語ベクトル生成ステップにおいて、検索用情報の要素の集合s1,...,strを用いて、前記式Bのfps1,...,strの値を要素とする述語ベクトルを生成し、前記判定ステップにおいて、前記属性ベクトルと前記述語ベクトルとの内積が0のとき、前記検索対象情報に対応する登録用情報中に前記検索用情報が含まれると判定する、検索方法。少なくとも属性ベクトルまたは述語ベクトルを生成するベクトル構成方法であって、Fqを位数qの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fqの元で表現されるtrとし、添え字trはtrを意味し、rd1,...,rdtrを乱数とし、検索対象情報に対応する登録用情報の要素をX1,...,Xtrとし、検索用情報の要素をs1,...,strとし、とし、fpX1,...,Xtrを変数s1,...,strを含まないX1,...,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、fps1,...,strを変数X1,...,Xtrを含まないs1,...,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、Pを1以上の整数とし、前記式Aはと表現されるものとし、少なくとも検索対象情報に対応する登録用情報の要素の集合X1,...,Xtrを用いて、前記式BのfpX1,...,Xtrの値を要素とする属性ベクトルを生成するか、前記述語ベクトル生成方法は検索用情報の要素の集合s1,...,strを用いて、前記式Bのfps1,...,strの値を要素とする述語ベクトルを生成する、ベクトル構成方法。請求項4から7の何れかに記載の判定装置またはベクトル構成装置としてコンピュータを機能させるためのプログラム。従来技術では、ある長さnの属性ベクトルから検索タグを作成し、そして同じ長さnの述語ベクトルから検索クエリを生成し、それぞれの属性ベクトルと述語ベクトルの内積が0となるか否かを判定することで、暗号情報に対してキーワード検索や文書照合を行う。従来の属性ベクトル及び述語ベクトルの構成方法では、検索しようとする情報以下、検索用情報という、例えば検索しようとするキーワードや照合しようとする文書等が複数の要素例えば文字や単語等からなる場合、検索対象情報に対応する登録用情報の要素の中に、検索用情報の要素が全て登場するか否かを一回の検証内積で判定することが難しい。本発明は、述語多項式を用いて集合部分一致検索を行い、検索用情報の要素の集合が検索対象情報に対応する登録用情報の要素の集合内に含まれるか否かを判定する検索システム、判定装置、ベクトル構成装置、その方法及びプログラムを提供することを目的とする。上記の課題を解決するために、本発明の第一の態様に係る検索システムは、属性ベクトル生成装置と、述語ベクトル生成装置と、判定装置と、からなる。Fqを位数qの有限体とする。検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fqの元で表現されるtrとする。添え字trはtrを意味する。rd1,...,rdtrを乱数とする。検索対象情報に対応する登録用情報の要素をX1,...,Xtrとし、検索用情報の要素をs1,...,strとする。とする。fpX1,...,Xtrを変数s1,...,strを含まないX1,...,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。fps1,...,strを変数X1,...,Xtrを含まないs1,...,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。Pを1以上の整数とする。式Aはと表現されるものとする。属性ベクトル生成装置は検索対象情報に対応する登録用情報の要素の集合X1,...,Xtrを用いて、式BのfpX1,...,Xtrの値を要素とする属性ベクトルを生成する。述語ベクトル生成装置は検索用情報の要素の集合s1,...,strを用いて、式Bのfps1,...,strの値を要素とする述語ベクトルを生成し、判定装置は属性ベクトルと述語ベクトルとの内積が0のとき、検索対象情報に対応する登録用情報中に検索用情報が含まれると判定する。上記の課題を解決するために、本発明の第二の態様に係るベクトル構成装置によれば、少なくとも属性ベクトルまたは述語ベクトルを生成する。Fqを位数qの有限体とする。検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fqの元で表現されるtrとする。添え字trはtrを意味する。rd1,...,rdtrを乱数とする。検索対象情報に対応する登録用情報の要素をX1,...,Xtrとする。検索用情報の要素をs1,...,strとする。とする。fpX1,...,Xtrを変数s1,...,strを含まないX1,...,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。fps1,...,strを変数X1,...,Xtrを含まないs1,...,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。Pを1以上の整数とする。式Aはと表現されるものとする。少なくとも検索対象情報に対応する登録用情報の要素の集合X1,...,Xtrを用いて、式BのfpX1,...,Xtrの値を要素とする属性ベクトルを生成するか、または、述語ベクトル生成装置は検索用情報の要素の集合s1,...,strを用いて、式Bのfps1,...,strの値を要素とする述語ベクトルを生成する。上記の課題を解決するために、本発明の第三の態様に係る検索方法は、属性ベクトル生成ステップと、述語ベクトル生成ステップと、判定ステップと、からなる。Fqを位数qの有限体とする。検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fqの元で表現されるtrとする。添え字trはtrを意味する。rd1,...,rdtrを乱数とする。検索対象情報に対応する登録用情報の要素をX1,...,Xtrとする。検索用情報の要素をs1,...,strとする。とする。fpX1,...,Xtrを変数s1,...,strを含まないX1,...,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。fps1,...,strを変数X1,...,Xtrを含まないs1,...,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。Pを1以上の整数とする。式Aはと表現されるものとする。属性ベクトル生成ステップにおいて、検索対象情報に対応する登録用情報の要素の集合X1,...,Xtrを用いて、式BのfpX1,...,Xtrの値を要素とする属性ベクトルを生成する。述語ベクトル生成ステップにおいて、検索用情報の要素の集合s1,...,strを用いて、式Bのfps1,...,strの値を要素とする述語ベクトルを生成する。判定ステップにおいて、属性ベクトルと述語ベクトルとの内積が0のとき、検索対象情報に対応する登録用情報中に検索用情報が含まれると判定する。上記の課題を解決するために、本発明の第四の態様に係るベクトル構成方法によれば、少なくとも属性ベクトルまたは述語ベクトルを生成する。Fqを位数qの有限体とする。検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fqの元で表現されるtrとする。添え字trはtrを意味し、rd1,...,rdtrを乱数とする。検索対象情報に対応する登録用情報の要素をX1,...,Xtrとする。検索用情報の要素をs1,...,strとする。とする。fpX1,...,Xtrを変数s1,...,strを含まないX1,...,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。fps1,...,strを変数X1,...,Xtrを含まないs1,...,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。Pを1以上の整数とする。式Aはと表現されるものとする。少なくとも検索対象情報に対応する登録用情報の要素の集合X1,...,Xtrを用いて、式BのfpX1,...,Xtrの値を要素とする属性ベクトルを生成するか、述語ベクトル生成方法は検索用情報の要素の集合s1,...,strを用いて、式Bのfps1,...,strの値を要素とする述語ベクトルを生成する。本発明は、を満たす属性ベクトルと述語ベクトルを用いて、登録用情報中に検索用情報が含まれるか否かを判定するため、検索用情報が複数の要素からなる場合であっても1回の検証により判定することができるという効果を奏する。以下、本発明の実施形態について、説明する。定義まず、各実施形態で使用される用語や記号を定義する。行列:行列とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも行列と表現する。T:Tはの転置行列を表す。-1:-1はの逆行列を表す。∧:∧は論理積を表す。∨:∨は論理和を表す。Z:Zは整数集合を表す。sec:secはセキュリティパラメータsec∈Z,sec>0を表す。Fq:Fqは位数qの有限体を表す。位数qは1以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。0F:0Fは有限体Fqの加法単位元零元を表す。一般化した加法単位元を0と表す。1F:1Fは有限体Fqの乗法単位元を表す。一般化した乗法単位元を1と表す。δi,j:δi,jはクロネッカーのデルタ関数を表す。i=jの場合にδi,j=1Fを満たし、i≠jの場合にδi,j=0Fを満たす。E:Eは有限体Fq上で定義された楕円曲線を表す。G1,G2,GT:G1,G2,GTは位数qの巡回群を表す。巡回群G1,G2の具体例は、楕円曲線Eのp等分点からなる有限集合E[p]やその部分群である。G1=G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における1のp乗根からなる有限集合である。なお、本形態では、巡回群G1,G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。すなわち、χ∈Fq及びΩ∈G1に対するχΩ∈G1は、Ω∈G1に対して巡回群G1で定義された演算をχ回施すことを意味し、Ω1,Ω2∈G1に対するΩ1Ω2∈G1は、Ω1∈G1とΩ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。同様に、χ∈Fq及びΩ∈G2に対するχΩ∈G2は、Ω∈G2に対して巡回群G2で定義された演算をχ回施すことを意味し、Ω1,Ω2∈G2に対するΩ1Ω2∈G2は、Ω1∈G2とΩ2∈G2とを被演算子として巡回群G2で定義された演算を行うことを意味する。一方、χ∈Fq及びΩ∈GTに対するΩχ∈GTは、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω1,Ω2∈GTに対するΩ1Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。n:nは1以上の整数を表す。ζ:ζは1以上の整数を表す。ζの一例は2または3である。G1nζ:G1nζはnζ個の巡回群G1の直積を表す。G2nζ:G2nζはnζ個の巡回群G2の直積を表す。g1,g2,gT:g1,g2,gTは巡回群G,G1,G2,GTの生成元を表す。V:Vはnζ個の巡回群G1の直積からなるnζ次元のベクトル空間を表す。V:Vはnζ個の巡回群G2の直積からなるnζ次元のベクトル空間を表す。e:eは直積G1nζと直積G2nζとの直積G1nζ×G2nζを巡回群GTに写す非退化な双線形写像bilinearmapを表す。双線形写像eは、巡回群G1のnζ個の元γββ=1,...,nζと巡回群G2のnζ個の元γββ=1,...,nζとを入力とし、巡回群GTの1個の元を出力する。eG1nζ×G2nζ→GT双線形写像eは以下の性質を満たす。[双線形性]全てのΓ1∈G1nζ,Γ2∈G2nζ及びν,κ∈Fqについて以下の関係を満たす。eeνκ[非退化性]全てのΓ1∈G1nζ,Γ2∈G2nζを巡回群GTの単位元に写すものではない。[計算可能性]あらゆるΓ1∈G1nζΓ2∈G2nζについてeΓ1,Γ2を効率的に計算するアルゴリズムが存在する。本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を計算するための関数PairG1×G2→GTを用いて双線形写像eを構成する。本形態の双線形写像eは、巡回群G1のnζ個の元γββ=1,...,nζからなるnζ次元ベクトルγ1,...,γnζと、巡回群G2のnζ個の元γββ=1,...,nζからなるnζ次元ベクトルγ1,...,γnζとの入力に対し、巡回群GTの1個の元eΠβ1nζPairを出力する。なお、双線形写像Pairは、巡回群G1の1個の元と巡回群G2の1個の元との組を入力とし、巡回群GTの1個の元を出力するものであり、以下の性質を満たす。[双線形性]全てのΩ1∈G1,Ω2∈G2及びν,κ∈Fqについて以下の関係を満たす。PairPairνκ[非退化性]全てのΩ1∈G1Ω2∈G2を巡回群GTの単位元に写すものではない。[計算可能性]あらゆるΩ1∈G1,Ω2∈G2についてPairΩ1,Ω2を効率的に計算するアルゴリズムが存在する。なお、双線形写像Pairの具体例は、WeilペアリングやTateペアリングなどのペアリングである例えば、参考文献1及び2等参照。参考文献1AlfredJMenezes,ELLIPTICCURVEPUBLICKEYCRYPTOSYSTEMS,KLUWERACADEMICPUBLISHERS,ISBN0792393686,pp6181参考文献2RFC5091IdentityBasedCryptographyStandard1SupersingularCurveImplementationsoftheBFandBB1Cryptosystemsaii=1,...,nζ:aiは巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ1g1∈G1をi次元目の要素とし、残りのn個の要素を巡回群G1の単位元加法的に0と表現とするnζ次元の基底ベクトルである。この場合、nζ次元の基底ベクトルaii=1,...,nζの各要素をそれぞれ列挙して表現すると、以下のようになる。a1a2...anζここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ1=1Fである。基底ベクトルaiは直交基底であり、巡回群G1のnζ個の元を要素とする全てのnζ次元ベクトルは、nζ次元の基底ベクトルaii=1,...,nζの線形和によって表される。すなわち、nζ次元の基底ベクトルaiはベクトル空間Vを張る。aii=1,...,nζ:巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ2g2∈G2をi次元目の要素とし、残りのn個の要素を巡回群G2の単位元加法的に0と表現とするnζ次元の基底ベクトルである。この場合、基底ベクトルaii=1,...,nζの各要素をそれぞれ列挙して表現すると、以下のようになる。a1a2...anζここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ2=1Fである。基底ベクトルaiは直交基底であり、巡回群G2のnζ個の元を要素とする全てのnζ次元ベクトルは、nζ次元の基底ベクトルaii=1,...,nζの線形和によって表される。すなわち、nζ次元の基底ベクトルaiはベクトル空間Vを張る。なお、基底ベクトルaiと基底ベクトルaiとは、0Fを除く有限体Fqの元τ=κ1κ2についてegTτδを満たす。すなわち、i=jの場合には、式56の関係から、ePairPair...PairPairκ1κ2Pair00...Pair00Pairκ1κ2gTτを満たす。一方、i≠jの場合には、eai,aj=Πi=1nζPairai,ajの右辺は、Pairκ1g1,κ2g2を含まず、Pairκ1g1,0とPair0,κ2g2とPair0,0との積になる。さらに、式6の関係からPairg1,0=Pair0,g2=Pairg1,g20を満たす。そのため、i≠jの場合には、ee0gT0を満たす。特に、τ=κ1κ2=1Fである場合例えば、κ1=κ2=1Fの場合、egTδを満たす。ここで、gT0=1は巡回群GTの単位元であり、gT1=gTは巡回群GTの生成元である。この場合、基底ベクトルaiと基底ベクトルaiとは双対正規直交基底であり、ベクトル空間Vとベクトル空間Vとは、双線形写像を構成可能な双対ベクトル空間双対ペアリングベクトル空間DPVS:DualParingVectorspaceである。A:基底ベクトルaii=1,...,nζを要素とするnζ行nζ列の行列を表す。例えば、基底ベクトルaii=1,...,nζが式8によって表現される場合、行列Aは、となる。A:基底ベクトルaii=1,...,nζを要素とするnζ行nζ列の行列を表す。例えば、基底ベクトルaii=1,...,nζが式9によって表現される場合、行列Aは、となる。X:有限体Fqの元を要素とするnζ行nζ列の行列を表す。基底ベクトルaiの座標変換に用いられる。行列Xのi行j列i=1,...,nζ,j=1,...,nζの要素をχi,j∈Fqとすると、行列Xは、となる。なお、行列Xの各要素χi,jを変換係数と呼ぶ。X:Xは行列Xの逆行列の転置行列X=X-1Tを表す。基底ベクトルaiの座標変換に用いられる。行列Xのi行j列の要素をχi,j∈Fqとすると、行列Xは、となる。なお、行列Xの各要素χi,jを変換係数と呼ぶ。この場合、nζ行nζ列の単位行列をIとするとXXT=Iを満たす。すなわち、単位行列に対し、を満たす。ここで、nζ次元ベクトルχi→χj→を定義する。すると、式17の関係から、nζ次元ベクトルχi→とχj→との内積は、χi→χj→δとなる。bi:biは巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルを表す。行列Xを用いて基底ベクトルaii=1,...,nζを座標変換することで得られる。具体的には、基底ベクトルbiは、biΣj1nζχijajの演算によって得られる。例えば、基底ベクトルajj=1,...,nζが式8によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。bi巡回群G1のnζ個の元を要素とする全てのnζ次元ベクトルは、nζ次元の基底ベクトルbii=1,...,nζの線形和によって表される。すなわち、nζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。bi:biは巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルを表す。行列Xを用いて基底ベクトルaii=1,...,nζを座標変換することで得られる。具体的には、基底ベクトルbiは、biΣj1nζχijajの演算によって得られる。例えば、基底ベクトルajj=1,...,nζが式9によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。biとなる。巡回群G2のnζ個の元を要素とする全てのnζ次元ベクトルは、nζ次元の基底ベクトルbii=1,...,nζの線形和によって表される。すなわち、nζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。なお、基底ベクトルbiと基底ベクトルbiとは、0Fを除く有限体Fqの元τ=κ1κ2についてegTτδを満たす。すなわち、式5202224の関係から、を満たす。特に、τ=κ1κ2=1Fである場合例えば、κ1=κ2=1Fの場合、egTδを満たす。この場合、基底ベクトルbiと基底ベクトルbiとは、双対ペアリングベクトル空間ベクトル空間Vとベクトル空間Vの双対正規直交基底である。なお、式25の関係を満たすのであれば、式89で例示したもの以外の基底ベクトルai及びaiや、式2123で例示したもの以外の基底ベクトルbi及びbiを用いてもよい。B:Bは基底ベクトルbii=1,...,nζを要素とするnζ行nζ列の行列。B=XAを満たす。例えば、基底ベクトルbiが式22によって表現される場合、行列Bは、となる。B:Bは基底ベクトルbii=1,...,nζを要素とするnζ行nζ列の行列を表す。B=XAを満たす。例えば、基底ベクトルbii=1,...,nζが式24によって表現される場合、行列Bは、となる。内積述語暗号方式次に、内積述語暗号方式について説明する。内積述語暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。内積述語暗号方式では、内積が0となることと論理式の真理値が真となることとが等価である。[内積と論理式の真理値との関係]内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。まず、x1がη1であるという命題1とx2がη2であるという命題2との論理和x1=η1∨x2=η2をという多項式で表現する。すると、各真理値と式29の関数値との関係は以下のようになる。[表1]から分かるように、論理和x1=η1∨x2=η2が真である場合、式29の関数値は0になり、論理和x1=η1∨x2=η2が偽である場合、式29の関数値は0以外の値となる。すなわち、論理和x1=η1∨x2=η2が真であることと、式29の関数値が0となることとは等価である。よって、論理和は式29で表現できる。また、x1がη1であるという命題1とx2がη2であるという命題2との論理積x1=η1∧x2=η2をι1ι2という多項式で表現する。但し、ι1及びι2は乱数である。すると、真理値と式30の関数値とは以下の関係となる。[表2]から分かるように、論理積x1=η1∧x2=η2が真である場合、式30の関数値は0になり、論理積x1=η1∧x2=η2が偽である場合、式30の関数値は0以外の値となる。すなわち、論理積x1=η1∧x2=η2が真であることと、式30の関数値が0となることとは等価である。よって、論理積は式30で表現できる。以上から、論理和や論理積からなる任意の論理式を多項式で表現できることが分かる。例えば、論理式{x1=η1∨x2=η2}∧x3=η3∧x4=η4は、多項式ι1ι2ι3で表現できる。以下、このように論理式を表現する多項式のことを述語多項式と呼ぶ。述語多項式は2つのベクトルの内積で表現できる。すなわち、述語多項式は、各項の不定元成分と1とを各要素とするベクトルと、各項の係数成分を各要素とするベクトルとの内積に等しい。例えば、式31の述語多項式は、各項の不定元成分と1を各要素とするベクトルx1x2,x1,x2,x3,x4,1と、各項の係数成分を各要素とするベクトルι1,-ι1η2,-ι1η1,ι2,-ι2η3ι3,ι1η1η2-ι3η4との内積に等しい。そのため、述語多項式の値が0であるか否かと、述語多項式の各項の不定元成分と1とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。言い換えると、論理式の真理値が真であるか否かと、当該論理式を示す述語多項式の各項の不定元成分と1とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。内積述語暗号方式では、上述の各項の不定元成分と1を各要素とするベクトル以下、属性ベクトルという及び各項の係数成分を各要素とするベクトル以下、述語ベクトルというの何れか一方のベクトルが暗号文に埋め込まれ、他方のベクトルが復号鍵に埋め込まれる。以下では、暗号文に埋め込まれるベクトルをw→=w1,...,wnとし、復号鍵に埋め込まれるベクトルをv→=v1,...,vnとする。[内積述語暗号方式の基本構成]内積述語暗号方式で鍵カプセル化メカニズムKEMKeyEncapsulationMechanismsを構成する例を示す。この構成はSetup,GenKey,Enc,Decを含む。《Setup:セットアップ》-入力:セキュリティパラメータsec-出力:マスタ鍵情報MSK,公開パラメータPKSetupの一例では、まず、セキュリティパラメータsecをnとして、nζ次元の基底ベクトルaii=1,...,nζを要素とするnζ行nζ列の行列Aと、基底ベクトルaii=1,...,nζを要素とするnζ行nζ列の行列Aと、座標変換のためのnζ行nζ列の行列X,Xとが選択される。次に、式21に従って座標変換されたnζ次元の基底ベクトルbii=1,...,nζが算出され、式23に従って座標変換されたnζ次元の基底ベクトルbii=1,...,nζが算出される。そして、基底ベクトルbii=1,...,nζを要素とするnζ行nζ列の行列Bがマスタ鍵情報MSKとして出力され、ベクトル空間V,V、基底ベクトルbii=1,...,nζを要素とするnζ行nζ列の行列B、セキュリティパラメータsec、有限体Fq、楕円曲線E、巡回群G1,G2,GT、生成元g1,g2,gT、双線形写像eなどが公開パラメータPKとして出力される。《GenKey:復号鍵生成》-入力:マスタ鍵情報MSK,ベクトルv→-出力:ベクトルv→に対応する復号鍵DGenKeyの一例では、まず、有限体Fqから元σ,σι-n∈Fqが選択される。そして、マスタ鍵情報MSKである行列Bを用い、ベクトルv→に対応する復号鍵DσΣιn1nζ’σιnbι∈G2nζ’が生成され、出力される。但し、σ,σι-nは乱数などの変数や定数などであり、ζ’≦ζである例えばζ=3,ζ’=2。またΣι=n1nζ’σι-nはシステムで共有される定数値とされる。以下ではΣιn1nζ’σιn1Fとされた例を説明する。これは本発明を限定しない。《Enc:暗号化》-入力:公開パラメータPK,ベクトルw→,平文mes-出力:暗号文C1,C2Encの一例では、行列Bなどの公開パラメータPKと、有限体Fqの元である乱数υ0,υ1,...,υζと、ベクトルw→とを用い、暗号文C1υ0Σμn1nζυμnbμ∈G1nζが生成される。但し、υ1...υζ’を満たす例えばζ’=2のときにはυ1=υ2。また、gTτυ1を共通鍵Kとし、所定の共通鍵暗号方式第2暗号方式に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、C2gTτυ1mesである。添え字のυ1はυ1を意味する。前述のように定数τの一例はτ=1Fである。生成された暗号文C1,C2は出力される。《Dec:復号》-入力:ベクトルv→に対応する復号鍵D,暗号文C1,C2-出力:復号値mes’Decの一例では、まず、暗号文C1と復号鍵Dとが式1の双線形写像eに入力され、その演算結果を共通鍵K=eC1,Dとし、以下のように復号値mes’が求められる。mes’C2e∈GTここで、式2253335の性質から、を満たす。内積w→v→=0であれば、式38は、を満たす。式363739から、内積w→v→=0であればmes’=mesとなり、正しく復号されることが分かる。[階層的内積述語暗号方式の基本構成]階層的内積述語暗号方式は内積述語暗号方式の一種であり、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる。さらに階層的内積述語暗号方式では階層的な処理によって復号鍵を生成できる。すなわち、階層的内積述語暗号方式では属性が階層化され、各階層までの属性に対応する鍵情報が存在するとともに、上位の階層に対応する鍵情報を用いて下位の階層に対応する鍵情報を生成できる。そして、このような階層的な処理によって生成された最終的な鍵情報が復号鍵となる。以下に階層的内積述語暗号方式の基本構成を例示する。以下では、階層的内積述語暗号方式を用いて鍵カプセル化メカニズムKEMを構成する場合の基本構成を例示する。但し、これは本発明を限定するものではない。《前提》深さdの属性空間の階層フォーマットを以下の式によって定義する。但し、dは1以上n以下の整数である。ξ→有限体Fqの元を要素とするξω-ξω-1ω=1,...,d次元のベクトル零ベクトルを除くを階層ωに対応するベクトルとし、階層1から階層mm≦dまでに対応するベクトルをw1→,...,wm→とする。有限体Fqの元を要素とするξω-ξω-1次元ω=1,...,dのベクトル零ベクトルを除くを階層ωに対応するベクトルとし、階層1から階層mまでに対応するベクトルをv1→,...,vm→とする。《Setup:セットアップ》-入力:セキュリティパラメータsec-出力:階層フォーマットξ→,マスタ鍵情報MSK,公開パラメータmpkSetupの一例では、セキュリティパラメータsecの単調増加関数値をnとし、階層フォーマットξ→=n,d;ξ1,...,ξdが定められる。また、この例ではζ=3とし、n3次元の基底ベクトルaii=1,...,n3を要素とするn3行n3列の行列Aと、基底ベクトルaii=1,...,n3を要素とするn3行n3列の行列Aと、座標変換のためのn3行n3列の行列X,Xとが選択される。次に、式21に従って座標変換されたn3次元の基底ベクトルbii=1,...,n3が算出され、式23に従って座標変換されたn3次元の基底ベクトルbii=1,...,n3が算出される。この例では、基底ベクトルb1,...,bn,bn1,bn2,bn3と行列Xとがマスタ鍵情報MSKとして出力され、基底ベクトルb1,...,bn,bn1bn2,bn3、ベクトル空間V,V、セキュリティパラメータsec、有限体Fq、楕円曲線E、巡回群G1,G2,GT、生成元g1,g2,gT、双線形写像eなどが公開パラメータmpkとして出力される。《GenKey:鍵情報生成》-入力:マスタ鍵情報MSK,公開パラメータmpk,ベクトルv1→,...,vm→-出力:ベクトルv1→,...,vm→に対応する鍵情報kmGenKeyの一例では、まず、有限体Fqから元σα,ω,Ψ,Φα∈Fqα=0,...,m1,ξm1,...,n;ω=1,...,mが任意に選択される。この例では、これらとマスタ鍵情報MSKである基底ベクトルb1,...,bn,bn1,bn2,bn3とベクトルv1→,...,vm→とを用い、ベクトルv1→,...,vm→に対応する鍵情報が生成されて出力される。但し、である。《Delegatem’:鍵情報生成委譲》-入力:公開パラメータmpk,鍵情報km’,ベクトルvm’1→-出力:ベクトルv1→,...,vm’1→に対応する鍵情報km’1階層的内積述語暗号方式では、マスタ鍵情報MSKを用いることなく、公開パラメータmpk,鍵情報km’,ベクトルvm’1→からベクトルv1→,...,vm’1→に対応する鍵情報km’1を生成できる。但し、m’=1,...,d-1である。Delegatem’の一例では、有限体Fqから元σ’α,ω,Ψ’,Φ’α∈Fqα=0,...,m’2,ξm’11,...,n;ω=1,...,m’1が任意に選択される。この例では、これらと鍵情報km’とベクトルvm’1→と用い、ベクトルv1→,...,vm’1→に対応する鍵情報が生成されて出力される。但し、である。《Enc:暗号化》-入力:公開パラメータmpk,ベクトルw1→,...,wm→,平文mes-出力:暗号文C1,C2Encの一例では、まず、有限体Fqから任意の元υ1,...,υd,υn3,υが選択される。そして、これらと公開パラメータmpkとベクトルw1→,...,wm→とを用い、暗号文が生成される。また、gTτυを共通鍵Kとし、所定の共通鍵暗号方式第2暗号方式に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、C2gTτυmesである。なお、前述のように定数τの一例はτ=1Fである。その後、以上のように生成された暗号文C1,C2が出力される。《Dec:復号》-入力:公開パラメータmpk,ベクトルv1→,...,vm→に対応する鍵情報km,暗号文C1,C2-出力:復号値mes’Decの一例では、mes’C2eによって復号値mes’を計算する。暗号文C1と鍵情報kmのkm,0とが式1の双線形写像eこの例ではζ=3に入力されると、式225の性質から、を満たす。なお、σω及びσは有限体Fqの元である。Delegatem’がなされることなく鍵情報kmが生成された場合にはσω=σ0,ωである。Delegatem’が1回以上なされた場合には、GenKeyに使用された有限体Fqの元σα,ωやDelegatem’時に使用された有限体Fqの元σ’α,ωやΦ’αに応じてσωの値が定まる。ここで、全てのω=1,...,mについて内積vω→wω→=0Fであれば、式54は、egTτυと変形できる。式525355より、全てのω=1,...,mについて内積vω→wω→=0Fである場合にmes’=mesとなり、正しく復号がなされることが分かる。<第一実施形態>以下に説明する情報処理では、文字列を含む情報が暗号化の対象となるが、暗号処理の実際では、人間が意味内容を認識可能なテキスト情報である文字そのものが暗号化されるのではなく、例えば当該文字に割り当てられている文字コード情報EUCJP、ShiftJIS、UTF8などのバイト表現が暗号化の対象となる。従って、後述の説明において例えば変数Xに文字wを代入ないし設定するX=wとは、テキスト情報としての文字wを変数Xに代入ないし設定することではなく、文字コード情報としての文字wを変数Xに代入ないし設定することと理解するべきである。このことは暗号処理の常套手段であるから、その詳細な説明を省略する。また、この明細書では、ベクトルの表記として慣用的にベクトルであることを示す記号→を省略している場合がある。従って、或る記号がベクトルであるか否かは明細書全体の記載から合理的に理解されたい。<ポイント>式32等で用いる述語ベクトルv→及び式34等で用いる属性ベクトルw→の構成方法が従来の方法と異なる。まず、従来技術の述語ベクトル及び属性ベクトルの構成方法について説明する。従来の内積述語検索可能暗号非特許文献1及び2参照は、属性ベクトルや述語ベクトルをキーワードに見立てて、属性ベクトルを使って作成された暗号文が述語ベクトルを使って復号できるとき、暗号文中にキーワードが存在すると判定する暗号文検索技術である。この場合、属性ベクトルは最大文字数をrとして、述語論理に最大d-1回の論理和が許される場合に、r個の属性変数X1,...,Xrからなる次数d以下の単項式を全て辞書式順序で並べた順に各成分とした変数ベクトルX→r,dに登録用キーワードに含まれる文字を設定して得られるベクトルである。また、この場合、述語ベクトルは述語論理を属性変数と検索用キーワードに含まれる文字を用いて多項式で表現した述語多項式の係数を、変数ベクトルX→r,dの成分に対応する順に並べたものを成分として持つベクトルである。本実施形態では集合部分一致検索が可能になる述語多項式ppm1を与える。集合部分一致検索を行うことで、検索用情報が複数の要素からなる場合であっても1回の検証により判定することができる。さらに変形例1ではその効率的な表現を与える。そのために、まずキーワードの部分一致検索非特許文献1参照を表現する多項式とそのベクトル長を説明する。キーワード部分一致検索は検索用キーワードに部分的に一致するもの全てを見つける検索である。集合部分一致検索と異なる点は、キーワード部分一致検索は文字の順序ABBという文字列の検索は、{A、B、B}={A、B}をA⇒B⇒Bの順に含まなければならない含めて一致したものを検索するが、集合部分一致検索は{A、B、B}={A、B}を含むものが検索されることである。従来技術で用いる部分一致検索は、検索用キーワードが、登録用キーワードに当てはまりうる全てのパターンを述語で記述することで実現できる。例えば、登録用キーワードの文字数tr=6、検索用キーワードがABCAである時、検索用キーワードの文字数ts=4であることから、登録用キーワードが検索用キーワードの含むその含み方は全部でtr-ts1=3通りである。具体的には、ABCA、ABCA、ABCAの3通りである。但し、は任意の文字を表す。従って、これらを論理和でつないだ述語論理を考えればよい。このことから、部分一致検索のための述語多項式ppmX1,...,Xtrは、と書ける但し、rdi,jは乱数を表す。この述語多項式の単項式の数nは2tr-ts1≦n≦tr-ts1Htsである。但し、添え字のtr、tsはそれぞれtr、tsを意味し、tr-ts1Htsはtr-ts1個のものから重複してts個のものを選ぶ組み合わせの総数を表す。従来技術の上記式61を用いて、集合部分一致検索を実現しようとすると、検索用キーワードを構成する各文字A、B、Cをそれぞれ、検索用キーワードとして、部分一致検索を行い、全ての検索においてヒットした登録用キーワードを検索結果とすると考えられる。登録用キーワードの文字の中に、検索用キーワードの文字が全て登場するか否かを一回の検証内積で判定することができず、演算時間が長くなる。一方、第一実施形態では、集合部分一致検索が可能になる述語多項式ppm1を与える。Fqを位数qの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fqの元で表現されるtrとし、rd1,...,rdtrを乱数とする。ppm1は登録用キーワードと検索用キーワードの格納領域変数の長さをどちらもtrとしている。登録用キーワード及び検索用キーワードの文字数がtr未満だった場合、記号⊥に対応する文字をそれ以降に格納していくことで対応する。ppmを利用して達成する部分一致検索は、文字列s1...stsが文字列X1...Xtrのどこかに含まれることを文字の順序を含めてチェックする検索であったが、ppm1を利用して達成する検索は、s1...strを文字列としてまとめてとらえるのではなく、文字s1、...、stsと一つ一つ個別に、文字列X1...Xtrの中に含まれているかどうかをチェックするものである。文字s1、...、strが順序に関係なく、文字列X1...Xtrの中に全て含まれる場合には、ppm1=0となる。文字列として含まれている場合は、個別の文字として含まれている場合に含まれるので、ppm1による検索結果はppmを含む。ppm1は単純に展開すると、となる。式63は、X1,...,Xtrの基本対称式の線形和に出てくる全ての単項式と同様の単項式2tr-1個と、定数項1個とを持つ。よって、式63は2tr個の単項式を持つ。なお、X1,...,Xtrのk次の基本対称式をYkとすると、であり、具体的には、Y1=-X1X2...XtrY2=X1X2X1X3...X1XtrX2X3...Xtr-1Xtr...Ytr=-1trX1X2...Xtrである。なお、X1,...,Xtrの基本対称式の線形和とは、tr個のk次の基本対称式Ykの線形和である。本実施形態では、各単項式の値または定数1を要素とする属性ベクトルw→を構成し、各単項式の係数の値または定数1に対応する値a0を要素とする述語ベクトルv→を構成する。つまり、w→=1,X1,X2,...,Xtr,X1X2,...,X1X2...Xtrv→=a0,a1,...,a2^tr-1である。但し、C^DはCのD乗を表す。よって、各ベクトルの次元は2tr次元である。内積述語暗号検索可能暗号の検索時間は演算時間=各種暗号基本演算ペアリング演算等×ベクトルの次元×タグの数文書数である。部分一致検索におけるベクトルの次元数n但し、2tr-ts1≦n≦tr-ts1Htsはtr-ts1Htsに近い値をとることとなり、trの値が大きくなるにつれて、その傾向は顕著になると考えられ、本実施形態の次元数2trよりも大きくなる。そのため、trが大きくなるにつれて、本実施形態の検索システムのほうが、従来技術に比べ、検索時間が短くなる。<検索システム1>以下、図1を用いて第一実施形態に係る検索システム1を説明する。検索システム1は、上述の述語多項式ppm1を内積述語暗号に適用する参考文献3及び4参照。参考文献3:TOkamotoandKTakashimaHierarchicalpredicateencryptionforinnerproductsInASIACRYPT2009pp214231参考文献4:ABLewkoTOkamotoASahaiKTakashimaandBWatersFullysecurefunctionalencryptionAttributebasedencryptionandinnerproductencryptionInEUROCRYPT2010pp6291検索システム1は、暗号化されたデータベースの検索が可能な検索可能暗号システムである。この実施形態の検索システム1は、図1に示すように、属性ベクトル生成装置11と、述語ベクトル生成装置15と、判定装置16と、保管装置13とを少なくとも含んで構成される。これらの各装置は、例えばインターネットである通信網12を介して相互に通信可能とされている。検索システム1における検索処理を、図2を参照しながら叙述する。各装置の機能構成については、図3を参照されたい。<事前処理>前述したSetupが実行され、マスタ鍵情報msk,公開パラメータmpkが定められる。マスタ鍵情報mskは、マスタ鍵格納部153に安全に格納され、属性ベクトル生成装置11、述語ベクトル生成装置15、判定装置16が、公開パラメータmpkを用いた処理が可能なように構成される。<暗号情報及び検索タグの登録処理>まず、属性ベクトル生成装置11の暗号情報生成部111は、文字列を含む情報以下検索対象情報というTexttiを暗号化して暗号情報CTTexttiを得るステップS2。この暗号方式Enc,Decに限定はない。この暗号方式として、例えば共通鍵暗号方式や公開鍵暗号方式を利用できる。共通鍵暗号方式の場合、検索対象情報Texttiは、属性ベクトル生成装置11と述語ベクトル生成装置15との間で共有される共通鍵で暗号化される。また、公開鍵暗号方式の場合、検索対象情報Texttiは述語ベクトル生成装置15の公開鍵で暗号化される。つまり、暗号情報CTTexttiを得るための情報処理は、暗号化アルゴリズムEncに従う。生成された暗号情報CTTexttiは、検索対象情報Texttiに対応する登録用キーワードXとともに、登録キーワード格納部114に格納される。登録用キーワードXは、例えば、ユーザによって予め設定される、検索対象となるキーワードであり、検索対象情報Texttiに含まれるキーワードまたはキーワードの集合である。次に、属性ベクトル生成装置11の属性ベクトル生成部113は、登録キーワード格納部114から、検索対象情報Texttiに対応する登録用キーワードXを抽出し、登録用キーワードXを表す属性ベクトルw→が以下の関係を満たすように生成する。この属性ベクトルw→は、検索において、文書等を検索するためのインデックスとしての役割を持つ。なお、tr文字の登録用キーワードXのi番目の文字をXi1≦i≦trとし、登録用キーワードXの文字列をX1,...,Xi,...,Xtrとする。また、後述するtr文字の検索用キーワードsのi番目の文字をsi1≦i≦trとし、検索用キーワードsの文字列をs1,...,si,...,strとする。また、rd1,...,rdtrを乱数とし、図示しない乱数生成部により生成される。但し、述語多項式ppm1は登録用キーワード及び後述する検索用キーワードの格納領域変数の長さをtrとする。各キーワードの長さがtr未満の場合、記号⊥に対応する文字をtrに達するまで格納することで対応する。また、登録用キーワードのtr番目の格納領域には記号⊥に対応する文字を格納する。つまり、登録用キーワードは実質的には最大tr-1文字である。登録用キーワードに記号⊥に対応する文字が含まれていない場合、登録用キーワードの文字の中に、tr未満の検索用キーワードに含まれる全ての文字が含まれている場合であっても、記号⊥に対応する文字が含まれていないために、検索されないことが生じうるが、このような構成とすることで、漏れを防ぐことができる。式62の述語多項式ppm1を単純に展開すると、となる。本実施形態では、各単項式の値または定数1を要素とする属性ベクトルw→を構成する。つまり、属性ベクトルw→=1,X1,X2,...,Xtr,X1X2,...,X1X2...Xtr64を生成するステップS3。つまり、属性ベクトル生成装置11の属性ベクトル生成部113は、各単項式X1,X2,...,Xtr,X1X2,...,X1X2...Xtrに対し、具体的な登録用キーワードXの文字X1,...,Xtrを与え、各単項式の値を計算し、計算結果を求める。この計算結果と定数1を要素とする属性ベクトルを生成する。属性ベクトル生成部113は、生成した属性ベクトルw→を検索タグ生成部112へ出力する。検索タグ生成部112は、公開パラメータPKと属性ベクトルw→を入力とし、式34により、暗号文C1を生成する。C1υ0Σμn1nζυμnbμ∈G1nζなお、式34において、乱数ν0,ν1,...,νζは、検索タグ生成部112内部の図示しない乱数生成部により生成する。なお式34において、n=2trである。さらに、検索タグ生成部112は、公開パラメータPKと登録用キーワードXを入力とし、式36により、暗号文C2を生成する。C2gTτυ1mesなお、式36において、mes=Xである。検索タグ生成部112は、上述の処理により得られた暗号文C1,C2の組合せを検索タグTagti=C1,C2として出力するステップS4。属性ベクトル生成装置11の送信部118は、暗号情報CTTexttiと検索タグTagtiとを一組として保管装置13へ送信するステップS5。保管装置13の受信部139は、暗号情報と検索タグとの組Textti,Tagtiを受信するステップS6。保管装置13の記憶部131には、通常、属性ベクトル生成装置11から受信した複数のTextti,Tagtiが記憶されている。さらに言えば、保管装置13の記憶部131には、一般的に、複数の属性ベクトル生成装置から受信した複数のTextti,Tagtiが記憶されている。各組Textti,Tagtiには固有のインデックスが割り当てられている。<復号鍵検索クエリ生成処理>述語ベクトル生成装置15は、検索用キーワードsを入力されると、述語ベクトル生成部151において、検索用キーワードsを表す述語ベクトルv→を以下の関係を満たすように生成する。なお、この述語ベクトルv→は検索において、文書等を検索するためのクエリの役割を持つ。ppm1を単純に展開すると、となり、本実施形態では、定数1に対応する値a0と各単項式の係数の値を要素とする述語ベクトルv→を構成する。つまり、述語ベクトルを生成するS7。式62から各単項式の係数は、siの冪乗つまりsik但し、0≦k≦trと乱数rdjの積の和からなる。つまり、述語ベクトル生成装置15の述語ベクトル生成部151は、定数1に対応する値a0、各単項式の係数a1,...,a2^tr-1に対し、具体的な検索用キーワードsの文字s1,...,strを与え、さらに乱数rdjを生成し、これらの値を用いて、値a0及び各係数を計算し、計算結果を求める。この計算結果を要素とする述語ベクトルを生成する。述語ベクトル生成装置15の鍵生成部152は、マスタ鍵情報MSKと述語ベクトルv→を入力とし、式32により、述語ベクトルv→に対応する復号鍵Dを生成するステップS8。DσΣιn1nζσιnbι∈G2nζ’但し、乱数や定数等であるσ、σιnは鍵生成部152において、生成されるか、または、予め鍵生成部152に記憶されているものとする。述語ベクトル生成装置15の送信部158は、復号鍵Dを判定装置16へ送信するステップS9。<判定処理>判定装置16の受信部169は、復号鍵Dを受信するステップS10。判定装置16の制御部165は、送信部168を制御して、保管装置13に対して保管装置13の記憶部131に記憶されている全ての検索タグを判定装置16へ送信するように要求し、これを受けて保管装置13の送信部138は記憶部131に記憶されている全ての検索タグをインデックスとともに判定装置16へ送信し、判定装置16の受信部169がこれらを受信するステップS11。判定装置16の復号判定部161は、全ての検索タグを復号判定処理の対象とし、復号鍵Dを用いて検索タグを個別に復号して検索が当たりか否かを判定するステップS12。具体的には、復号判定部161は、全ての検索タグについて、式38に従って、eC1,Dを求め、式36、37、39から、mes’=mesの成否を判定する判定処理。C2gTτυ1mesmes’C2e∈GT内積w→v→=0であれば、mes’=mesとなり、登録用キーワードXの文字X1,X2,...,Xtrの中に、検索用キーワードsの文字s1,s2,...,strが含まれていることが分かる。判定装置16の送信部168は、mes’=mesが成立した検索タグのインデックスを述語ベクトル生成装置15へ送信するステップS13。述語ベクトル生成装置15の受信部159は、mes’=mesが成立した検索タグのインデックスを受信するステップS14。述語ベクトル生成装置15の制御部155は、送信部158を制御して、保管装置13に対して、保管装置13の記憶部131に記憶されている、判定装置16から受信したインデックスに対応する暗号情報を述語ベクトル生成装置15へ送信するように要求し、これを受けて保管装置13の送信部138は当該インデックスに対応する暗号情報を述語ベクトル生成装置15へ送信し、述語ベクトル生成装置15の受信部159がこれらを受信するステップS15。述語ベクトル生成装置15の復号部156は、必要に応じて、保管装置13から受信した暗号情報CTTexttiを復号して検索対象情報Texttiを得るステップS16。検索対象情報Texttiを得るための情報処理は、属性ベクトル生成装置11の暗号情報生成部111が実施した暗号方式Enc,Decに対応する復号アルゴリズムDecに従う。<効果>このような構成とすることで、複数の文字からなる検索用キーワードが登録用キーワード内に含まれるか否かを1回の検証により判定することができるという効果を奏する。なお、本実施形態において、登録用情報及び検索用情報の単位をキーワードとし、それぞれの要素を文字としているが、登録用情報の単位を文章とし、登録用情報及び検索用情報の要素を単語としてもよい。これは、例えば検索対象情報が英文等である場合、登録用情報を検索対象情報でもある英文自体とし、その英文の単語を要素として、属性ベクトルを構成し、複数の単語を述語ベクトルとして表現し検索することができる。また例えば和文の場合には、形態素解析等を行うことで同様に登録用情報の単位を文章とし、登録用情報及び検索用情報の要素を単語とすることができる。<変形例1>第一実施形態と異なる部分を主に説明する。属性ベクトル生成装置11の属性ベクトル生成部113と述語ベクトル生成装置15の述語ベクトル生成部151の処理内容が第一実施形態と異なる。他の処理は第一実施形態と同様である。属性ベクトル生成装置11の属性ベクトル生成部113は、登録キーワード格納部114から、検索対象情報Texttiに対応する登録用キーワードXを抽出し、登録用キーワードXを表すベクトルw→が以下の関係を満たすように生成する。式62の述語多項式ppm1を変形して、-X1,-X2,...,-Xtrのk次基本対称式Ykを用いて、属性ベクトルw→={Y0,Y1,...,Yk,...,Ytr}を生成する。以下、説明する。但し、X’i=-Xiであり、Ykは-X1,-X2,...,-Xtrのk次の基本対称式であり但し、Y0=1とする、である。具体的には、Y1=X1X2...XtrY2=X1X2X1X3...X1XtrX2X3...Xtr-1Xtr...Ytr=X1X2...Xtrである。また、である。本変形例の属性ベクトル生成部113では、登録用キーワードXを用いて、式74の-X1,-X2,...,-Xtrのk次の基本対称式Yk但し、Y0=1とするから属性ベクトルを生成する。つまり、本変形例の属性ベクトル生成部113では、各基本対称式Ykに対し、具体的な登録用キーワードXの文字X1,...,Xtrを与え、各基本対称式Ykの値を計算し、計算結果を求める。Y0=1とこの計算結果を要素とする属性ベクトルを生成する。また、本変形例の述語ベクトル生成部151では、検索用キーワードsと乱数rd1,...,rdtrを用いて、述語ベクトルを生成する。式74から各基本対称式Ykの係数は、Vksjの冪乗と乱数rdjの積の和である。つまり、述語ベクトル生成部151は、各基本対称式Ykの係数Vkに対し、具体的な検索用キーワードsの文字s1,...,strを与え、さらに乱数rdjを生成し、これらの値を用いて、値V0及びk次の基本対称式Ykに対する係数Vkを計算し、計算結果を求める。この計算結果を要素とする述語ベクトルを生成する。<効果>このような構成とすることで、属性ベクトル及び述語ベクトルの次元数をtr1とすることができる。従来技術や第一実施形態に比べ、ベクトルの次元数を小さくすることができる。なお、trが大きくなるに従い、次元数の差は大きくなる。よって、演算時間が短くなるという効果が得られる。<変形例2>第一実施形態と異なる部分を主に説明する。属性ベクトル生成装置11の属性ベクトル生成部113と述語ベクトル生成装置15の述語ベクトル生成部151の処理内容が第一実施形態及びその変形例1と異なる。他の処理は第一実施形態またはその変形例1と同様である。属性ベクトル生成装置11の属性ベクトル生成部113は、検索対象情報に対応する登録用情報の要素から重複する要素を削除して属性ベクトルを生成する。また、述語ベクトル生成装置15の述語ベクトル生成部151は、検索用情報の要素から重複する要素を削除して述語ベクトルを生成する。つまり、キーワードがABCCBAの場合、A,B,Cがそれぞれ重複するので、それぞれ重複する要素を削除し、キーワードをABCに変換し、変換後のキーワードを用いて属性ベクトル及び述語ベクトルを作成する。なお、削除した格納領域には記号⊥に対応する文字を格納する。<効果>このような構成とすることで、属性ベクトル及び述語ベクトルの生成や判定処理の計算量を減らすことができる。なお、集合部分一致検索を行うため、このような構成が可能となるのであって、従来の部分一致検索ではこのような構成とすることはできない。<その他の変形例>集合部分一致検索が可能になる述語多項式ppm1を与える点がポイントである。よって、必ずしも暗号化されたデータベースの検索が可能な検索可能暗号システムに述語多項式ppm1を用いる必要はない。つまり、暗号化されていないデータベースの検索において、述語多項式ppm1を利用してもよい。この場合、属性ベクトル生成装置11には暗号情報生成部111や検索タグ生成部112は不要であり、述語ベクトル生成装置15には鍵生成部152や復号部156やマスタ鍵格納部153は不要である。保管装置13の記憶部131には暗号化されていない検索対象情報と、検索対象情報に対応する登録用キーワードから得られる属性ベクトルが記憶される。判定装置16は述語ベクトル生成装置15から述語ベクトルを受信し、保管装置13から属性ベクトルを受信する。そして、判定装置16の復号判定部161では属性ベクトルと述語ベクトルの内積が0か否かを判定し、内積が0となる属性ベクトルに対応する検索対象情報を検索結果として述語ベクトル構成装置に送信する。また、少なくとも属性ベクトル生成装置または述語ベクトル生成装置の何れか一方の機能を有する装置をベクトル構成装置と呼ぶ。本実施形態では属性ベクトル生成装置11と述語ベクトル生成装置15は別装置として構成しているが、両方の機能を有するベクトル構成装置として構成してもよい。さらに、本実施形態では、ベクトル構成装置と保管装置、判定装置を別装置としているが、同一装置として構成してもよい。同一装置内の検索システムとして利用することができる。また、集合部分一致検索を用いているため、文字列X1...Xtrや文字列s1...strの順序を入れ替えて、文字の集合X1,...,Xtrやs1,...,strを用いて属性ベクトル及び述語ベクトルを生成しても第一実施形態と同様の効果を得ることができる。なお、属性ベクトル及び述語ベクトルは式62を満たすものであればよい。ここで、式62は、と表現される。但し、fpX1,...,Xtrを、変数s1,...,strを含まない登録用情報の要素X1,...,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。なお、変数s1,...,strを含まないとは、具体的な値siと同様の値をfpX1,...,Xtr中に含む場合はあるが、検索用情報の要素変数としてのs1,...,strを含まないことを意味する。例えば、fpX1,...,Xtrは、1基本対称式の項、2基本対称式の項と定数の積、3基本対称式の項または基本対称式の項と定数の積の和4定数等として表される。また、fps1,...,strを変数X1,...,Xtrを含まない検索用情報の要素s1,...,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。なお、変数X1,...,Xtrを含まないとは、具体的な値Xiと同様の値をfps1,...,str中に含む場合はあるが、登録用情報の要素変数としてのX1,...,Xtrを含まないことを意味する。例えば、fps1,...,strは、1siの冪乗つまりsik但し、0≦k≦tr、2siの冪乗と定数の積、3siの冪乗またはsiの冪乗と定数の積の和4定数等として表される。Pを1以上の整数とする。式81のfpX1,...,Xtr及びfps1,...,strは式62を満たすように適宜設定される。例えば、式62において、tr=2の場合、式62を展開すると、となる。例えば、第一実施形態の場合は、fpX1,...,XtrをXiの基本対称式の単項式または定数とし、fps1,...,strを各単項式の係数または定数に対するsiの冪乗と定数の積rd1s12rd2s22とするので、P=4であり、例えば、f1X1,X2=1、f2X1,X2=-X1、f3X1,X2=-X2、f4X1,X2=X1X2であり、f1s1,s2=rd1s12rd2s22、f2s1,s2=rd1s1rd2s2、f3s1,s2=rd1s1rd2s2、f4s1,s2=rd1rd2である。よって、w→v→である。また、例えば、変形例1の場合は、式74よりfpX1,...,Xtrを-Xiのk次の基本対称式または定数とし、fps1,...,strを各基本対称式の係数または定数に対するsiの冪乗と定数の積rd1s12rd2s22とするので、P=3であり、例えば、f1X1,X2=1、f2X1,X2=X1X2、f3X1,X2=X1X2であり、f1s1,s2=rd1s12rd2s22、f2s1,s2=-rd1s1-rd2s2、f3s1,s2=rd1rd2である。よって、w→v→となる。また、例えば、fps1,...,strをsik但し、0≦k≦trとし、fpX1,...,Xtrを各sikの係数とすると、P=6であり、例えば、f1s1,s2=s10、f2s1,s2=s20、f3s1,s2=s1、f4s1,s2=s2、f5s1,s2=s12、f6s1,s2=s22であり、f1X1,X2=rd1X1X2、f2X1,X2=rd2X1X2、f3X1,X2=-rd1X1-rd1X2、f4X1,X2=-rd2X1-rd2X2、f5X1,X2=-rd1、f6X1,X2=rd2である。よって、w→v→となる。前述の通り、fpX1,...,Xtr及びfps1,...,strは式62を満たすように適宜設定されるものであり、例えば、rdj等はfpX1,...,Xtrまたはfps1,...,strに含まれればよい。よって、前述の属性ベクトル生成装置は、登録用情報の要素X1,...,Xtrを用いて、fpX1,...,Xtrの値を要素とするP次元の属性ベクトルを生成する。つまり、属性ベクトル生成装置は、単項式若しくは多項式または定数であるfpX1,...,Xtrに対し、具体的な登録用情報の要素X1,...,Xtrを与え、fpX1,...,Xtrを計算し、計算結果を求める。この計算結果を要素とするP次元の属性ベクトルを生成する。前述の述語ベクトル生成装置は、検索用情報の要素s1,...,strを用いて、fps1,...,strの値を要素とするP次元の述語ベクトルを生成する。つまり、述語ベクトル生成装置は、単項式若しくは多項式または定数であるfps1,...,strに対し、具体的な検索用情報の要素s1,...,strを与え、fps1,...,strを計算し、計算結果を求める。この計算結果を要素とするP次元の述語ベクトルを生成する。<第二実施形態><検索システム2>以下、図4を用いて第二実施形態に係る検索システム2を説明する。検索システム2は、上述の述語多項式ppm1を階層的内積述語暗号に適用する参考文献3及び4参照。検索システム1は、暗号化されたデータベースの検索が可能な検索可能暗号システムである。図4に例示するように、本形態の検索可能暗号システム2は、管理装置27-mm=1,...,Mと属性ベクトル生成装置21u=1,...,Uと判定装置26と保管装置23と述語ベクトル生成装置25u=1,...,Uとを有する。なお、M及びUはそれぞれ1以上の整数である。また、管理装置27-mは、検索可能暗号システム1のm番目の管理者が使用する装置である。本形態では、小さいmに対応する管理者ほど強い管理権限を持つ。すなわち、m=1に対応する管理者が最も強い権限を持つ。また、属性ベクトル生成装置21及び述語ベクトル生成装置25は、検索可能暗号システム1を利用するu番目の登録ユーザが使用する装置である。また、各装置は他の装置へ情報を提供可能なように構成されている。装置間の情報提供は通信網12を通じて行われてもよいし、可搬型記録媒体を介して行われてもよい。[管理装置27]図5Aは、実施形態の管理装置27-1の機能構成を説明するための図であり、図5Bは、実施形態の管理装置27-m’1m’=1,...,M-1の機能構成を説明するための図である。図5Aに例示するように、管理装置27-1は、入力部271-1と出力部272-1とマスタ鍵格納部273-1と制御部275-1とベクトル設定部276a-1と鍵情報生成部276b-1とを有する。図5Bに例示するように、管理装置27-m’1は、入力部271-m’1と出力部272-m’1と制御部275-m’1とベクトル設定部276a-m’1と鍵情報生成部276b-m’1とを有する。管理装置27-mは、例えば、CPURAMROMなどを有する公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、管理装置27-mは、それぞれ、制御部275-mの制御のもと各処理を実行する。また、管理装置27-mでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。[属性ベクトル生成装置21]図6は、実施形態の属性ベクトル生成装置21-uの機能構成を説明するための図である。図6に例示するように、属性ベクトル生成装置21-uは、入力部211-uと出力部212-uと属性格納部213a-uと登録キーワード格納部213b-uと検索者鍵格納部213c-uと制御部215-uと属性ベクトル生成部216e-uと検索タグ生成部216f-uとを有する。属性ベクトル生成装置21は、例えば、公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、属性ベクトル生成装置21は、それぞれ、制御部215-uの制御のもと各処理を実行する。なお、属性ベクトル生成装置21での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。[判定装置26]図7は、実施形態の判定装置26の機能構成を説明するための図である。図7に例示するように、判定装置26は、入力部261と出力部262と制御部265と検証処理部267とを有する。判定装置26は、例えば、公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、判定装置26は、それぞれ、制御部265の制御のもと各処理を実行する。また、判定装置26での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。[保管装置23]図8Aは、実施形態の保管装置23の機能構成を説明するための図である。図8Aに例示するように、保管装置23は、入力部231と出力部232と暗号化データベース格納部233と制御部235と読み書き部236とを有する。保管装置23は、例えば、公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、保管装置23は、制御部135の制御のもと各処理を実行する。図8Bは、暗号化データベース格納部233に格納される暗号化データベースのデータ構成を説明するための図である。図8Bに例示するように、暗号化データベース格納部233には、文書などの検索対象情報Texttiの暗号文CTTexttiと検索対象情報Texttiのキーワードに対応する暗号化情報であるタグ情報Tagti,uとが互いに対応付けられて格納されている。暗号文CTTexttiを生成するための検索対象情報Texttiの暗号化方式には限定はなく、任意の既存の暗号化方式共通鍵暗号方式,公開鍵暗号方式,関数暗号方式などでよい。タグ情報Tagti,uは暗号文CTTexttiを検索するための情報である。保管装置23は、タグ情報Tagti,uが与えられても、それに対応する検索キーワードを知ることができない。タグ情報Tagti,uの生成方法の詳細は後述する。[述語ベクトル生成装置25]図9は、実施形態の述語ベクトル生成装置25の機能構成を説明するための図である。図9に例示するように、述語ベクトル生成装置25は、入力部251-uと出力部252-uと鍵情報格納部253-uと検索対象情報復号鍵格納部254-uと制御部255-uと述語ベクトル生成部256-uと検索クエリ生成部257-uと復号部258-uとを有する。述語ベクトル生成装置25は、例えば、公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、述語ベクトル生成装置25は、それぞれ、制御部255-uの制御のもと各処理を実行する。<事前処理>前述したSetupが実行され、階層フォーマットξ→,マスタ鍵情報msk,公開パラメータmpkが定められる。マスタ鍵情報mskは、管理装置27-1図5Aのマスタ鍵格納部273-1に安全に格納され、管理装置27-m,属性ベクトル生成装置21,述語ベクトル生成装置25及び判定装置26が、公開パラメータmpkを用いた処理が可能なように構成される。また、管理装置27-m及び属性ベクトル生成装置21が階層フォーマットξ→に従った処理が可能なように構成される。属性ベクトル生成装置21図6の登録キーワード格納部213b-uには、登録を行う検索対象情報Texttiの暗号文CTTexttiと検索対象情報Texttiに対応するキーワードXとが格納されている。さらに、属性ベクトル生成装置21の属性格納部213a-uには、属性ベクトル生成装置21を利用するユーザの属性を表す情報以下、単に属性というが格納されている。ユーザの属性の例は、ユーザが所属するグループを表す情報会社名、所属部門、課、担当、グループなど、住所、年齢、職業、趣味などである。述語ベクトル生成装置25図9の検索対象情報復号鍵格納部254-uには、属性ベクトル生成装置21図6の登録キーワード格納部213b-uに格納された暗号文CTTexttiを復号するための検索対象情報復号鍵Keytiが格納されている。<ユーザ登録>ユーザ登録では、管理装置27-mが登録ユーザの属性に対して設定されたベクトルv1→,...,vM→に対応する鍵情報kMを生成する。鍵情報kMの生成方式は大きく分けて2通り存在する。一つ目の方式は、管理装置27-1が前述のGenKeyのみに従って鍵情報kMを生成する方式である一括方式。このような方式は小規模グループに適したものであるといえる。二つ目の方式は、管理装置27-1が前述のGenKeyに従い、その他の管理装置27-m’1が前述のDelegatem’に従い、鍵情報kMを生成する方式である委託方式。このような方式は階層化された大規模グループに適したものであるといえる。[一括方式]図7は、一括方式によって鍵情報kMを生成する処理を説明するためのフローチャートである。一括方式では、最も強い権限をもつm=1に対応する管理者の管理装置27-1のみによって鍵情報kMを生成する。まず、管理装置27-1図5Aの入力部271-1に登録ユーザの属性ATTが入力される。属性ATTはM層ATT1,...,ATTMに階層化されている。各層に対応する属性ATTmを部分属性と呼ぶことにし、小さいmに対応する部分属性ATTmほど上位の属性を表すものとする。例えば、M=2の場合、属性ATTは2層の部分属性ATT1及びATT2からなり、この場合の部分属性の例は、ATT1○○株式会社,○○部門...ATT2○○課,○○担当,○○グループ...である。入力された属性ATTはベクトル設定部276a-1に入力される。ベクトル設定部276a-1は、階層フォーマットξ→及びシステム内で定められた規則に従って属性ATTに対応するベクトルv1→,...,vM→を設定する。例えば、ベクトル設定部276a-1は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、属性ATTを表すベクトルw1→,...,wM→を式41に従って設定し、内積wω→vω→=0Fとなる式42に従ったベクトルv1→,...,vM→を属性ATTに対応するベクトルとする。式8182の例を用いて説明すると、例えば、ベクトル設定部276a-1は、部分属性ATT1を○○株式会社を表すw1及び○○部門を表すw2を要素とする2次元のベクトルw1→...に変換し、部分属性ATT2を○○課を表すw3、○○担当を表すw4、及び○○グループを表すw5を要素とする3次元のベクトルw2→...に変換し、属性ATTを表すベクトルw1→,w2→=w1,w2,w3,w4,w5を設定し、内積wω→vω→=0Fとなるベクトルv1→,v2→=v1,v2,v3,v4,v5を属性ATTに対応するベクトルとする。なお、システム内で定められた規則に基づいて定められるのであれば、属性ATTを表すベクトルw1→,...,wM→をどのように定めるかについては特に限定はなく、属性ATTごとにベクトルw1→,...,wM→が定まるのであればどのような方法でもよい。生成されたベクトルv1→,...,vM→は鍵情報生成部276b-1に入力される。鍵情報生成部276b-1は、マスタ鍵格納部273-1からマスタ鍵情報mskを読み出し、m=Mとした前述のGenKeyに従い、ベクトルv1→,...,vM→に対応する鍵情報kMを生成する。例えば、鍵情報生成部276b-1は、m=Mとした式43-46に従って鍵情報kMを生成する。生成された鍵情報kMは出力部272-1に送られる。出力部272-1は、鍵情報kMM≦d-1を出力する。鍵情報kMは登録ユーザが使用する述語ベクトル生成装置25図9の入力部251-uに入力され、鍵情報格納部253-uに格納される。[委託方式]委託方式では、最も強い権限をもつm=1に対応する管理者の管理装置27-1が前述のGenKeyに従って鍵情報k1を生成し、上位階層の鍵情報を受け取った下位階層の管理者の管理装置27-m’1が前述のDelegatem’に従って鍵情報を生成していき、最終的に鍵情報kMが生成される。まず、管理装置27-1図5Aの入力部271-1に登録ユーザの部分属性ATT1が入力される。入力された部分属性ATT1はベクトル設定部276a-1に入力される。ベクトル設定部276a-1は、階層フォーマットξ→及びシステム内で定められた規則に従って部分属性ATT1に対応するベクトルv1→を設定する。例えば、ベクトル設定部276a-1は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、部分属性ATT1を表すベクトルw1→を式41に従って設定し、内積w1→v1→=0Fとなる式42に従ったベクトルv1→を部分属性ATT1に対応するベクトルとする。式8182の例を用いて説明すると、例えば、ベクトル設定部276a-1は、式83によって部分属性ATT1を表すベクトルw1→を設定し、内積w1→v1→=0Fとなる式84のベクトルv1→を、部分属性ATT1に対応するベクトルとする。生成されたベクトルv1→は鍵情報生成部276b-1に入力される。鍵情報生成部276b-1は、マスタ鍵格納部273-1からマスタ鍵情報mskを読み出し、m=1とした前述のGenKeyに従い、ベクトルv1→に対応する鍵情報k1を生成する。例えば、鍵情報生成部276b-1は、m=1とした式43-46に従って鍵情報k1を生成する。生成された鍵情報k1は出力部272-1に送られる。鍵情報k1は管理装置27-2に入力される。管理装置27-2以降では前述したDelegatem’m’=1,...,M-1に従って鍵生成が行われる。以下では管理装置27-m’から鍵情報km’を受け取る管理装置27-m’1の処理を一般化して説明する。まず、鍵情報km’が管理装置27-m’1図5Bの入力部271-m’1に入力され、鍵情報生成部276b-m’1に入力される。また、部分属性ATTm’1がベクトル設定部276a-m’1に入力される。ベクトル設定部276a-m’1は、階層フォーマットξ→及びシステム内で定められた規則に従って部分属性ATTm’1に対応するベクトルvm’1→を設定する。例えば、ベクトル設定部276a-m’1は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、部分属性ATTm’1を表すベクトルwm’1→を式41に従って設定し、内積wm’1→vm’1→=0Fとなる式42に従ったベクトルvm’1→を部分属性ATTm’1に対応するベクトルとする。生成されたベクトルvm’1→は鍵情報生成部276b-m’1に入力される。鍵情報km’とベクトルvm’1→とが入力された鍵情報生成部276b-m’1は、前述のDelegatem’に従って、ベクトルv1→,...,vm’1→に対応する鍵情報km’1を生成する。例えば、鍵情報生成部276b-m’1は、式47-50に従って鍵情報km’1を生成する。生成された鍵情報km’1は出力部272-m’1に送られる。出力部272-m’1は鍵情報km’1を出力する。m’1<Mの場合、出力された鍵情報km’1は下位階層の管理装置27-m’2に入力され、m’1を新たなm’として同様の処理が実行される。一方、m’1=Mの場合、出力された鍵情報km’1=kMは、登録ユーザが使用する述語ベクトル生成装置25図9の入力部251-uに入力され、鍵情報格納部253-uに格納される。<データベース登録>登録ユーザは属性ベクトル生成装置21を用い、以下のようにデータベース登録を行うことができる。まず、属性ベクトル生成装置11の属性ベクトル生成部113は、登録キーワード格納部114から、検索対象情報Texttiに対応する登録用キーワードXを抽出し、登録用キーワードXを表す属性ベクトルwM1→が以下の関係を満たすように生成する。属性ベクトルwM1→の生成方法は第一実施形態及びその変形例と同様である。また、属性ベクトル生成部216e-uが、属性格納部213a-uから登録ユーザの属性ATTを抽出する。この属性ATTは当該登録ユーザのユーザ登録時に用いられたものと同じである。属性ベクトル生成部216e-uは、階層フォーマットξ→及びシステム内で定められた規則に従って属性ATTを表すベクトルw1→,...,wM→を設定する。当該ベクトルw1→,...,wM→とユーザ登録時のステップS103で設定されたベクトルv1→,...,vM→とは、ω=1,...,Mについて内積wω→vω→=0Fを満たす。属性ベクトル生成部216e-uは、生成したベクトルw1→,...,wM→と属性ベクトルwM1→をまとめて検索タグ生成部216f-uに送る。検索タグ生成部216f-uは、w1→,...,wM→,wM1→を用い、例えば、d=M1とした式51に従って暗号文C1を生成し、mes=Xとした式52に従って暗号文C2を生成する。検索タグ生成部216f-uは、上述の処理により得られた暗号文C1,C2の組合せを検索タグTagti,u=C1,C2とする。生成されたタグ情報Tagti,uは出力部212-uに送られる。また、登録キーワード格納部213b-uから読み出された暗号文CTTexttiが出力部212-uに送られる。出力部212-uは、暗号文CTTexttiとタグ情報Tagti,uとを出力する。これらの組は保管装置23図8Aの入力部231に入力され、書込み部236から暗号化データベース格納部233に格納される図8B。<検索>登録ユーザは述語ベクトル生成装置25図9を用い、以下のように検索を行うことができる。まず、検索を行う登録ユーザによって選択された検索用キーワードsが入力部251-uに入力される。検索用キーワードsは述語ベクトル生成部256-uに送られる。述語ベクトル生成部256-uにおいて、検索用キーワードsを表す述語ベクトルvM1→を以下の関係を満たすように生成する。述語ベクトルvM1→の生成方法は第一実施形態及びその変形例と同様である。生成された述語ベクトルvM1→は、検索クエリ生成部257-uに送られる。検索クエリ生成部257-uは、鍵情報格納部253-uから鍵情報kMを抽出する。検索クエリ生成部257-uは、kM,vM1→を用い、m’=Mとした前述のDelegatem’によって、v1→,...,vM→及びvM1→に対応する鍵情報復号鍵である検索クエリkM1を生成する。例えば、検索クエリ生成部257-uは、m’=MM≦d-1とした式47-50に従って検索クエリkM1を生成する。なお、m=d-1の場合には式50のkm’1,αを含まない。生成された検索クエリkM1は出力部252-uに送られる。出力部252-uは検索クエリkM1を出力する。検索クエリkM1は、判定装置26図7の入力部261に入力され、検証処理部267に送られる。判定装置26は保管装置23図8Aにアクセスし、暗号化データベース格納部233に格納されたタグ情報Tagti,uの取得を要求するための情報を出力部261から出力する。この情報は保管装置23の入力部231に入力されて読み書き部236に送られる。保管装置23の読み書き部236は、暗号化データベース格納部233から何れかのタグ情報Tagti,uを読み出し、出力部232はそれを判定装置26に送る。タグ情報Tagti,uは判定装置26図7の入力部261に入力され、検証処理部267に送られる。式525355より、全てのω=1,...,M,M1について内積vω→wω→=0Fである場合に、mes’=mesとなる。検証処理部267は、公開パラメータmpkと検索クエリkM1とタグ情報Tagti,uを入力とし、mes’=mesを満たすか否かを検証する。満たす場合には検証合格となる。ここで、検証合格とならなかった場合、判定装置26は保管装置23に対して未検証のタグ情報Tagti,uが暗号化データベース格納部233内に存在するかを問い合わせるための情報を出力部262から出力する。この情報は保管装置23図8Aの入力部231に入力され、読み書き部236に送られる。読み書き部236は、暗号化データベース格納部233を検索して未検証のタグ情報Tagti,uが暗号化データベース格納部233内に存在するか否かを判定し、その判定結果が出力部232から出力される。判定結果は、判定装置26図7の入力部261に入力され、制御部265に送られる。ここで、未検証のタグ情報Tagti,uが暗号化データベース格納部233内に存在しない旨の応答があった場合、判定装置26の出力部262が該当なしを表す⊥を出力して処理を終了する。一方、未検証のタグ情報Tagti,uが暗号化データベース格納部233内に存在する旨の応答があった場合には、未検証のタグ情報に対して検証を行う。一方、ステップS257で検証合格となった場合、判定装置26は保管装置23に対し、検証合格となったタグ情報Tagti,uに対応する検証対象情報の暗号文CTTexttiの出力を要求するための情報を出力部262から出力する。この情報は保管装置23図8Aの入力部231に入力され読み書き部236に送られる。読み書き部236は、検証合格となったタグ情報Tagti,uに対応する検証対象情報の暗号文CTTexttiを暗号化データベース格納部233から抽出し、出力部232に送る。出力部232は暗号文CTTexttiを出力する。暗号文CTTexttiは、判定装置26図7の入力部261に入力され、検証処理部267に送られる。暗号文CTTexttiは、出力部262に送られて出力され、述語ベクトル生成装置図9の入力部251-uに入力される。暗号文CTTexttiは、復号部258-uに送られる。復号部258-uは検索対象情報復号鍵格納部254-uから検索対象情報復号鍵Keytiを読み出し、これを用いて暗号文CTTexttiを復号して検索対象情報Texttiを出力する。<効果>このような構成とすることで、階層的内積述語暗号において部分集合一致検索可能な検索システムを構成することができる。<プログラム及び記録媒体>上述した属性ベクトル生成装置、述語ベクトル生成装置、ベクトル構成装置及び判定装置は、コンピュータにより機能させることもできる。この場合はコンピュータに、目的とする装置各種実施例で図に示した機能構成をもつ装置として機能させるためのプログラム、またはその処理手順各実施例で示したものの各過程をコンピュータに実行させるためのプログラムを、CD-ROM、磁気ディスク、半導体記憶装置などの記録媒体から、あるいは通信回線を介してそのコンピュータ内にダウンロードし、そのプログラムを実行させればよい。<その他の変形例>属性ベクトル生成装置及び述語ベクトル生成装置を関数暗号方式を用いて暗号化されたデータベースの検索が可能な検索可能暗号システムにおいても用いてもよい参考文献5参照。参考文献5:TatsuakiOkamotoKatsuyukiTakashimaFullySecureFunctionalEncryptionwithGeneralRelationsfromtheDecisionalLinearAssumptionAdvancesinCryptologyCRYPTO20102010p191208また、本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。"