"暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な第1暗号方式を用いた検索可能暗号システムであって、予め定められたキーワードの全体集合から検索対象情報TARに対応するキーワードを除いた補集合CSETに対して設定されるベクトルに対応する前記第1暗号方式の第1暗号文...Tを含む暗号化データベースを格納する暗号化データベース格納部と、検索用キーワードに対応するベクトルに対応する前記第1暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆1...maxtについての第1暗号文...Tの合成値が正しく復号できるかを判定するバッチ検索部と、を有する検索可能暗号システム。請求項1の検索可能暗号システムであって、前記inds∈sub⊆1...maxtについての前記第1暗号文...Tの合成値が正しく復号できないと判定された場合に、subの真部分集合を新たなsubとした前記バッチ検索部の処理を再び実行させる制御部をさらに有する検索可能暗号システム。請求項1又は2の検索可能暗号システムであって、前記検索対象情報TARに対応するキーワードに対して設定されるベクトルに対応する前記第1暗号方式の第2暗号文...LTを含む第2暗号化データベースを格納する第2暗号化データベース格納部と、前記inds∈sub⊆1...maxtについての前記第1暗号文...Tの合成値が正しく復号できないと判定された場合に、第2検索クエリを復号鍵として用い、第2暗号文...LTinds∈subが正しく復号できるかを判定する検索部をさらに有する検索可能暗号システム。請求項3の検索可能暗号システムであって、前記検索対象情報TARに対応するキーワードに対して設定されるベクトルと特定のベクトルとが特定の論理式の真理値を偽にする関係にあるとき、前記補集合CSETに対して設定されるベクトルと当該特定のベクトルとは当該特定の論理式の真理値を真にする関係にある、検索可能暗号システム。請求項1から4の何れかの検索可能暗号システムであって、前記第1暗号文...Tの合成値が...BTであり、BTがである、検索可能暗号システム。請求項1から5の何れかの検索可能暗号システムであって、前記第1暗号方式は、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0であるときに当該暗号文が当該復号鍵で復号可能な方式である、検索可能暗号システム。暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な第1暗号方式を用いた検索可能暗号方式のストレージ装置であって、予め定められたキーワードの全体集合から検索対象情報TARに対応するキーワードを除いた補集合CSETに対して設定されるベクトルに対応する前記第1暗号方式の第1暗号文...Tを含む暗号化データベースを格納する暗号化データベース格納部を有するストレージ装置。暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な第1暗号方式を用いた検索可能暗号方式のストレージ装置を検索する装置であって、検索用キーワードに対応するベクトルに対応する前記第1暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆1...maxtmaxt≧2についての第1暗号文...Tの合成値が正しく復号できるかを判定する装置。暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な第1暗号方式を用いた検索可能暗号方法であって、予め定められたキーワードの全体集合から検索対象情報TARに対応するキーワードを除いた補集合CSETに対して設定されるベクトルに対応する前記第1暗号方式の第1暗号文...Tを含む暗号化データベースが暗号化データベース格納部に格納されており、バッチ検索部で、検索用キーワードに対応するベクトルに対応する前記第1暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆1...maxtについての第1暗号文...Tの合成値が正しく復号できるかを判定する検索可能暗号方法。請求項9の検索可能暗号方法の処理をコンピュータに実行させるためのプログラム。しかしながら、従来の方式では、タグ情報ごとに検索クエリで復号可能か否かを判定するため、検索を行うための演算回数が多い。本発明はこのような点に鑑みてなされたものであり、従来よりも少ない演算回数で検索を行うことが可能な検索可能暗号技術を提供する。予め定められたキーワードの全体集合から検索対象情報TARに対応するキーワードを除いた補集合CSETに対して設定されるベクトルに対応する第1暗号方式の第1暗号文...Tを含む暗号化データベースを格納しておく。検索用キーワードに対応するベクトルに対応する第1暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆1...maxtについての第1暗号文...Tの合成値が正しく復号できるかを判定する。なお第1暗号方式は、暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な方式である。本発明では、検索クエリを用い、キーワードの全体集合から検索対象情報TARに対応するキーワードを除いた補集合CSETに対して設定されるベクトルに対応する第1暗号文...Tをinds∈sub⊆1...maxtについてまとめて検証することになる。これは、inds∈subの各検索対象情報TARが検索用キーワードにヒットしないかをまとめて検証することを意味する。よって、暗号化データベースが含む検索対象情報TARに対応するキーワードの多くが検索用キーワードにヒットしないと仮定すると、従来よりも少ない演算回数で検索を行うことができるといえる。以下、図面を参照して本発明の実施形態を説明する。概要以下に説明する各実施形態では、暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な暗号方式第1暗号方式を用いて検索可能暗号方式を構成する。このような暗号方式の例は、非特許文献3から6などに開示されている内積述語暗号方式や階層的内積述語暗号方式などの述語暗号方式などである。第1暗号方式が述語暗号方式の例では、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0であるときに当該暗号文が当該復号鍵で復号できる。本発明で利用する第1暗号方式は非特許文献3から6に開示された方式に限定されず、これらと同様な性質を有するどのような方式が用いられてもよい。各実施形態では、予め定められたキーワードの全体集合から検索対象情報TARに対応するキーワードを除いた補集合CSETに対して設定されるベクトルに対応する第1暗号方式の第1暗号文...Tを含む暗号化データベースを格納しておく。なお補集合CSETは、キーワードの全体集合から検索対象情報TARに対応するすべてのキーワードを除いた補集合CSETや、キーワードの全体集合から検索対象情報TARに対応する一部のキーワードを除いた補集合CSETや、キーワードの全体集合から検索対象情報TARに対応する一部のキーワードを除いた補集合の集合である。補集合CSETの定め方は検索方式検索条件に依存する。なお、キーワードとは文字や記号、又は、文字や記号からなる列文字列、記号列、文字記号列などを意味する。単語のように特定の意味をなすものだけではなく、例えばアルファベットのように特定の意味を成さないものもキーワードである。例えば、キーワードの全体集合がアルファベットの集合ABC...XYZであり、検索対象情報TARに対応するキーワードがABCである場合、補集合CSETは、DEF...XYZとなる詳細は後述。暗号化データベースの検索処理は、検索用キーワードに対応するベクトルに対応する第1暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆1...maxtについての第1暗号文...Tの合成値が正しく復号できるかを判定する処理を含む。ここで、暗号化データベースが含む第1暗号文...Tは、予め定められたキーワードの全体集合から検索対象情報TARに対応するキーワードを除いた補集合CSETに対して設定されるベクトルに対応する第1暗号方式の暗号文である。また、検索クエリは検索用キーワードに対応するベクトルに対応する第1暗号方式の復号鍵である。そのため、検索用キーワードが検索対象情報TARに対応するキーワードにヒットしないときに、検索クエリで第1暗号文...Tが復号できる。このような復号が可能か否かの判定がinds∈sub⊆1...maxtについてまとめて実行されるバッチ検索処理。これはinds∈subの各検索対象情報TARが検索キーワードにヒットしないかをまとめて検証していることになる。これにより、少ない演算回数で検索用キーワードにヒットしない検索対象情報TARを特定でき、検索対象を絞り込むことができる。その結果、暗号化データベースが含む検索対象情報TARに対応するキーワードの多くが検索用キーワードにヒットしないと仮定すると、この方法では従来よりも少ない演算回数で検索を行うことができることになる。また各実施形態の例では、inds∈sub⊆1...maxtについての前記第1暗号文...Tの合成値が正しく復号できないと判定された場合に、subの真部分集合を新たなsubとした上述のバッチ検索処理を再び実行させる。このような繰り返しにより、従来よりも少ない演算回数で検索対象を絞り込むことができる。また1回のバッチ検証処理の演算コストが1回の検索処理よりも大きい場合は、検索対象情報TARごとの検索処理に切り替えてコストを低減する手法も考えられる。この手法を実現する各実施形態の例では、さらに、検索対象情報TARに対応するキーワードに対して設定されるベクトルに対応する第1暗号方式の第2暗号文...LTを含む第2暗号化データベースを格納しておく。subの要素数が基準値以下であり、かつ、inds∈sub⊆1...maxtについての第1暗号文...Tの合成値が正しく復号できないと判定された場合に、検索クエリを復号鍵として用い、第2暗号文...LTinds∈subが正しく復号できるかを判定する。ここで、第2暗号文...LTは、検索対象情報TARに対応するキーワードに対して設定されるベクトルに対応する第1暗号方式の暗号文である。また、検索クエリは検索用キーワードに対応するベクトルに対応する第1暗号方式の復号鍵である。そのため、検索用キーワードが検索対象情報TARに対応するキーワードにヒットするときに、検索クエリで第2暗号文...LTが正しく復号できる。これは検索対象情報TARが絞り込まれてから、当該検索対象情報TARが検索クエリにヒットするかを検索対象情報TARごとに個別に検証していることになる。一般に、複数のinds∈subの検索対象情報TARに対する1つのバッチ検索処理の演算コストは、検索対象情報TARごとの1つの検索処理の演算コストよりも大きい。そのため、検索対象情報TARが絞り込まれ、例えば1回のバッチ検証処理の演算コストが1回の検索処理よりも大きい場合は、検索対象情報TARごとの検索処理に切り替えるほうが全体としての演算コストを低減できる。上述の基準値の例は1や2以上の整数定数である。また、subをDIV個に分割して得られる各真部分集合を新たなsubとしてバッチ検索部の処理を繰り返す場合には、DIVを上述の基準値としてもよい。また、subの要素数が基準値以下であるという条件の代わりに、集合1...maxtの分割回数が第2基準値以上であるという条件としてもよい。或いは、subの要素数が基準値以下であるという条件の代わりに、subの要素数が基準値以下であり、かつ、集合1...maxtの分割回数が第2基準値以上であるという条件としてもよい。なお、上述の検索対象情報TARに対応するキーワードに対して設定されるベクトルと特定のベクトルとが特定の論理式の真理値を偽にする関係にあるとき、上述の補集合CSETに対して設定されるベクトルと当該特定のベクトルとは当該特定の論理式の真理値を真にする関係にある。第1暗号方式が述語暗号方式の例では、上述の検索対象情報TARに対応するキーワードに対して設定されるベクトルと特定のベクトルとの内積が0以外のときに、上述の補集合CSETに対して設定されるベクトルと当該特定のベクトルとの内積が0となる。また、上述の第1暗号文...Tの合成値は、例えば...BTであり、これらのBTは例えばである。定義次に、以下の各実施形態で使用される用語や記号を定義する。行列:行列とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも行列と表現する。T:Tはの転置行列を表す。1:1はの逆行列を表す。∧:∧は論理積を表す。∨:∨は論理和を表す。Z:Zは整数集合を表す。sec:secはセキュリティパラメータsec∈Zsec0を表す。Fq:Fqは位数qの有限体を表す。位数qは1以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。0F:0Fは有限体Fqの加法単位元零元を表す。一般化した加法単位元を0と表す。1F:1Fは有限体Fqの乗法単位元を表す。一般化した乗法単位元を1と表す。δ:δはクロネッカーのデルタ関数を表す。ijの場合にδ1Fを満たし、i≠jの場合にδ0Fを満たす。E:Eは有限体Fq上で定義された楕円曲線を表す。G1G2GT:G1G2GTは位数qの巡回群を表す。巡回群G1G2の具体例は、楕円曲線Eのp等分点からなる有限集合Epやその部分群である。G1G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における1のp乗根からなる有限集合である。なお、本形態では、巡回群G1G2上で定義された演算を加法的に表現し、巡回群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の直積を表す。g1g2gT:g1g2gTは巡回群GG1G2GTの生成元を表す。V:Vはnζ個の巡回群G1の直積からなるnζ次元のベクトル空間を表す。V:Vはnζ個の巡回群G2の直積からなるnζ次元のベクトル空間を表す。e:eは直積G1nζと直積G2nζとの直積G1nζ×G2nζを巡回群GTに写す非退化な双線形写像bilinearmapを表す。双線形写像eは、巡回群G1のnζ個の元γβと巡回群G2のnζ個の元γβとを入力とし、巡回群GTの1個の元を出力する。e:G1nζ×G2nζ→GT...双線形写像eは以下の性質を満たす。[双線形性]すべてのΓ1∈G1nζ,Γ2∈G2nζ及びν,κ∈Fqについて以下の関係を満たす。eeνκ...[非退化性]すべてのΓ1∈G1nζ,Γ2∈G2nζを巡回群GTの単位元に写すものではない。[計算可能性]あらゆるΓ1∈G1nζ,Γ2∈G2nζ...についてeを効率的に計算するアルゴリズムが存在する。本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を計算するための関数PairG1×G2→GT...を用いて双線形写像eを構成する。本形態の双線形写像eは、巡回群G1のnζ個の元γβからなるnζ次元ベクトルと、巡回群G2のnζ個の元γβからなる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を効率的に計算するアルゴリズムが存在する。なお、双線形写像Pairの具体例は、WeilペアリングやTateペアリングなどのペアリングである例えば、参考文献1AlfredJMenezes,ELLIPTICCURVEPUBLICKEYCRYPTOSYSTEMS,KLUWERACADEMICPUBLISHERS,ISBN0792393686,pp6181、参考文献2RFC5091IdentityBasedCryptographyStandard1SupersingularCurveImplementationsoftheBFandBB1Cryptosystems等参照。ai:aiは巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ1g1∈G1をi次元目の要素とし、残りのn個の要素を巡回群G1の単位元加法的に0と表現とするnζ次元の基底ベクトルである。この場合、nζ次元の基底ベクトルaiの各要素をそれぞれ列挙して表現すると、以下のようになる。a1a2...anζここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ11Fである。基底ベクトルaiは直交基底であり、巡回群G1のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルaiの線形和によって表される。すなわち、nζ次元の基底ベクトルaiはベクトル空間Vを張る。ai:巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ2g2∈G2をi次元目の要素とし、残りのn個の要素を巡回群G2の単位元加法的に0と表現とするnζ次元の基底ベクトルである。この場合、基底ベクトルaiの各要素をそれぞれ列挙して表現すると、以下のようになる。a1a2...anζここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ21Fである。基底ベクトルaiは直交基底であり、巡回群G2のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルaiの線形和によって表される。すなわち、nζ次元の基底ベクトルaiはベクトル空間Vを張る。なお、基底ベクトルaiと基底ベクトルaiとは、0Fを除く有限体Fqの元τκ1κ2についてegTτδ...を満たす。すなわち、ijの場合には、式の関係から、ePairPairPairPairκ1κ2Pair00Pair00Pairκ1κ2gTτを満たす。一方、i≠jの場合には、eΠi1nζPairの右辺は、Pairを含まず、PairとPairとPairとの積になる。さらに、式の関係からPairPairPair0を満たす。そのため、i≠jの場合には、ee0gT0を満たす。特に、τκ1κ21Fである場合例えば、κ1κ21Fの場合、egTδ...を満たす。ここで、gT01は巡回群GTの単位元であり、gT1gTは巡回群GTの生成元である。この場合、基底ベクトルaiと基底ベクトルaiとは双対正規直交基底であり、ベクトル空間Vとベクトル空間Vとは、双線形写像を構成可能な双対ベクトル空間双対ペアリングベクトル空間DPVSDualParingVectorspaceである。A:基底ベクトルaiを要素とするnζ行nζ列の行列を表す。例えば、基底ベクトルaiが式によって表現される場合、行列Aは、となる。A:基底ベクトルaiを要素とするnζ行nζ列の行列を表す。例えば、基底ベクトルaiが式によって表現される場合、行列Aは、となる。X:有限体Fqの元を要素とするnζ行nζ列の行列を表す。基底ベクトルaiの座標変換に用いられる。行列Xのi行j列の要素をχij∈Fqとすると、行列Xは、となる。なお、行列Xの各要素χijを変換係数と呼ぶ。X:Xは行列Xの逆行列の転置行列XTを表す。基底ベクトルaiの座標変換に用いられる。行列Xのi行j列の要素をχij∈Fqとすると、行列Xは、となる。なお、行列Xの各要素χijを変換係数と呼ぶ。この場合、nζ行nζ列の単位行列をIとするとXTIを満たす。すなわち、単位行列に対し、を満たす。ここで、nζ次元ベクトルχi→...χj→...を定義する。すると、式の関係から、nζ次元ベクトルχi→とχj→との内積は、χi→χj→δ...となる。bi:biは巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルを表す。行列Xを用いて基底ベクトルaiを座標変換することで得られる。具体的には、基底ベクトルbiは、biΣj1nζχijaj...の演算によって得られる。例えば、基底ベクトルajが式によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。bi...巡回群G1のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルbiの線形和によって表される。すなわち、nζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。bi:biは巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルを表す。行列Xを用いて基底ベクトルaiを座標変換することで得られる。具体的には、基底ベクトルbiは、biΣj1nζχijaj...の演算によって得られる。例えば、基底ベクトルajが式によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。bi...となる。巡回群G2のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルbiの線形和によって表される。すなわち、nζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。なお、基底ベクトルbiと基底ベクトルbiとは、0Fを除く有限体Fqの元τκ1κ2についてegTτδ...を満たす。すなわち、式の関係から、を満たす。特に、τκ1κ21Fである場合例えば、κ1κ21Fの場合、egTδ...を満たす。この場合、基底ベクトルbiと基底ベクトルbiとは、双対ペアリングベクトル空間ベクトル空間Vとベクトル空間Vの双対正規直交基底である。なお、式の関係を満たすのであれば、式で例示したもの以外の基底ベクトルai及びaiや、式で例示したもの以外の基底ベクトルbi及びbiを用いてもよい。B:Bは基底ベクトルbiを要素とするnζ行nζ列の行列。BXAを満たす。例えば、基底ベクトルbiが式によって表現される場合、行列Bは、となる。B:Bは基底ベクトルbiを要素とするnζ行nζ列の行列を表す。BXAを満たす。例えば、基底ベクトルbiが式によって表現される場合、行列Bは、となる。内積述語暗号方式次に、内積述語暗号方式について説明する。内積述語暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。内積述語暗号方式では、内積が0となることと論理式の真理値が真となることとが等価である。[内積と論理式の真理値との関係]内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。まず、x1がη1であるという命題1とx2がη2であるという命題2との論理和∨を...という多項式で表現する。すると、各真理値と式の関数値との関係は以下のようになる。表1から分かるように、論理和∨が真である場合、式の関数値は0になり、論理和∨が偽である場合、式の関数値は0以外の値となる。すなわち、論理和∨が真であることと、式の関数値が0となることとは等価である。よって、論理和は式で表現できる。また、x1がη1であるという命題1とx2がη2であるという命題2との論理積∧をι1ι2...という多項式で表現する。ただし、ι1及びι2は乱数である。すると、真理値と式の関数値とは以下の関係となる。表2から分かるように、論理積∧が真である場合、式の関数値は0になり、論理積∧が偽である場合、式の関数値は0以外の値となる。すなわち、論理積∧が真であることと、式の関数値が0となることとは等価である。よって、論理積は式で表現できる。以上から、論理和や論理積からなる任意の論理式を多項式で表現できることが分かる。例えば、論理式∨∧∧は、多項式ι1ι2ι3...で表現できる。以下、このように論理式を表現する多項式のことを述語多項式と呼ぶ。述語多項式は2つのベクトルの内積で表現できる。すなわち、述語多項式は、各項の不定元成分と1とを各要素とするベクトルと、各項の係数成分を各要素とするベクトルとの内積に等しい。例えば、式の述語多項式は、各項の不定元成分と1を各要素とするベクトルと、各項の係数成分を各要素とするベクトルとの内積に等しい。そのため、述語多項式の値が0であるか否かと、述語多項式の各項の不定元成分と1とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。言い換えると、論理式の真理値が真であるか否かと、当該論理式を示す述語多項式の各項の不定元成分と1とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。内積述語暗号方式では、上述の各項の不定元成分と1を各要素とするベクトル及び各項の係数成分を各要素とするベクトルの何れか一方のベクトルが暗号文に埋め込まれ、他方のベクトルが復号鍵に埋め込まれる。以下では、暗号文に埋め込まれるベクトルをw→とし、復号鍵に埋め込まれるベクトルをv→とする。[内積述語暗号方式の基本構成]内積述語暗号方式で鍵カプセル化メカニズムKEMを構成する例を示す。この構成はSetup,GenKey,Enc,Decを含む。《Setup:セットアップ》-入力:セキュリティパラメータsec-出力:マスタ鍵情報MSK,公開パラメータPKSetupの一例では、まず、セキュリティパラメータsecをnとして、nζ次元の基底ベクトルaiを要素とするnζ行nζ列の行列Aと、基底ベクトルaiを要素とするnζ行nζ列の行列Aと、座標変換のためのnζ行nζ列の行列X,Xとが選択される。次に、式に従って座標変換されたnζ次元の基底ベクトルbiが算出され、式に従って座標変換されたnζ次元の基底ベクトルbiが算出される。そして、基底ベクトルbiを要素とするnζ行nζ列の行列Bがマスタ鍵情報MSKとして出力され、ベクトル空間VV、基底ベクトルbiを要素とするnζ行nζ列の行列B、セキュリティパラメータsec、有限体Fq、楕円曲線E、巡回群G1G2GT、生成元g1g2gT、双線形写像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-出力:暗号文Encの一例では、行列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である。生成された暗号文は出力される。《Dec:復号》-入力:ベクトルv→に対応する復号鍵D,暗号文-出力:復号値mesDecの一例では、まず、暗号文C1と復号鍵Dとが式の双線形写像eに入力され、その演算結果を共通鍵Keとし、以下のように復号値mesが求められる。mesC2e∈GT...ここで、式の性質から、を満たす。内積w→v→0であれば、式は、を満たす。式から、内積w→v→0であればmesmesとなり、正しく復号されることがわかる。[階層的内積述語暗号方式の基本構成]階層的内積述語暗号方式は内積述語暗号方式の一種であり、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる。さらに階層的内積述語暗号方式では階層的な処理によって復号鍵を生成できる。すなわち、階層的内積述語暗号方式では属性が階層化され、各階層までの属性に対応する鍵情報が存在するとともに、上位の階層に対応する鍵情報を用いて下位の階層に対応する鍵情報を生成できる。そして、このような階層的な処理によって生成された最終的な鍵情報が復号鍵となる。以下に階層的内積述語暗号方式の基本構成を例示する。以下では、階層的内積述語暗号方式を用いて鍵カプセル化メカニズムKEMを構成する場合の基本構成を例示する。ただし、これは本発明を限定するものではない。《前提》深さdの属性空間の階層フォーマットを以下の式によって定義する。ただし、dは1以上n以下の整数である。ξ→...有限体Fqの元を要素とするξωξω1次元のベクトル零ベクトルを除くを階層ωに対応するベクトルとし、階層1から階層mm≦dまでに対応するベクトルをとする。有限体Fqの元を要素とするξωξω1次元ω1dのベクトル零ベクトルを除くを階層ωに対応するベクトルとし、階層1から階層mまでに対応するベクトルをとする。《Setup:セットアップ》-入力:セキュリティパラメータsec-出力:階層フォーマットξ→,マスタ秘密鍵MSK,公開パラメータmpkSetupの一例では、セキュリティパラメータsecの単調増加関数値をnとし、階層フォーマットξ→が定められる。また、この例ではζ3とし、n3次元の基底ベクトルaiを要素とするn3行n3列の行列Aと、基底ベクトルaiを要素とするn3行n3列の行列Aと、座標変換のためのn3行n3列の行列X,Xとが選択される。次に、式に従って座標変換されたn3次元の基底ベクトルbiが算出され、式に従って座標変換されたn3次元の基底ベクトルbiが算出される。この例では、基底ベクトルと行列Xとがマスタ秘密鍵MSKとして出力され、基底ベクトル、ベクトル空間VV、セキュリティパラメータsec、有限体Fq、楕円曲線E、巡回群G1G2GT、生成元g1g2gT、双線形写像eなどが公開パラメータmpkとして出力される。《GenKey:鍵情報生成》-入力:マスタ秘密鍵MSK,公開パラメータmpk,ベクトル-出力:ベクトルに対応する鍵情報kmGenKeyの一例では、まず、有限体Fqから元σα,ω,Ψ,Φα∈Fqが任意に選択される。この例では、これらとマスタ秘密鍵MSKである基底ベクトルとベクトルとを用い、ベクトルに対応する鍵情報が生成されて出力される。ただし、である。《Delegate:鍵情報生成委譲》-入力:公開パラメータmpk,鍵情報km,ベクトルvm1→-出力:ベクトルに対応する鍵情報km1階層的内積述語暗号方式では、マスタ秘密鍵MSKを用いることなく、公開パラメータmpk,鍵情報km,ベクトルvm1→からベクトルに対応する鍵情報km1を生成できる。ただし、m1d1である。Delegateの一例では、有限体Fqから元σα,ω,Ψ,Φα∈Fqが任意に選択される。この例では、これらと鍵情報kmとベクトルvm1→と用い、ベクトルに対応する鍵情報が生成されて出力される。ただし、である。《Enc:暗号化》-入力:公開パラメータmpk,ベクトル,平文mes-出力:暗号文Encの一例では、まず、有限体Fqから任意の元υ1υdυn3υが選択される。そして、これらと公開パラメータmpkとベクトルとを用い、暗号文が生成される。また、gTτυを共通鍵Kとし、所定の共通鍵暗号方式第2暗号方式に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、C2gTτυmes...である。なお、前述のように定数τの一例はτ1Fである。その後、以上のように生成された暗号文が出力される。《Dec:復号》-入力:公開パラメータmpk,ベクトルに対応する鍵情報km,暗号文-出力:復号値mesDecの一例では、mesC2e...によって復号値mesを計算する。暗号文C1と鍵情報kmのkm0とが式の双線形写像eこの例ではζ3に入力されると、式の性質から、を満たす。なお、σω及びσは有限体Fqの元である。Delegateがなされることなく鍵情報kmが生成された場合にはσωσ0,ωである。Delegateが1回以上なされた場合には、GenKeyに使用された有限体Fqの元σα,ωやDelegate時に使用された有限体Fqの元σα,ωやΦαに応じてσωの値が定まる。ここで、すべてのω1mについて内積vω→wω→0Fであれば、式は、egTτυ...と変形できる。式より、すべてのω1mについて内積vω→wω→0Fである場合にmesmesとなり、正しく復号がなされることがわかる。第1実施形態次に、本発明の第1実施形態を説明する。本形態では第1暗号方式として内積述語暗号方式を用いる。<構成>図1に例示するように、本形態の検索可能暗号システム1は、管理装置110と登録装置120-uu1Uとストレージ装置140と検索装置150-uu1Uとを有する。なお、Uは1以上の整数である。また、登録装置120-u及び検索装置150-uは、検索可能暗号システム1を利用するu番目の登録ユーザが使用する装置である。また、各装置は他の装置へ情報を提供可能なように構成されている。装置間の情報提供はネットワークを通じて行われてもよいし、可搬型記録媒体を介して行われてもよい。[管理装置]図2Aに例示するように、管理装置110は、入力部111と出力部112とマスタ秘密鍵格納部113と制御部115と鍵情報生成部116bとを有する。管理装置110は、例えば、CPURAMROMなどを有する公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、管理装置110は、制御部115の制御のもと各処理を実行する。管理装置110での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。[登録装置]図2Bに例示するように、登録装置120-uは、出力部122-uと登録キーワード格納部123b-uと制御部125-uと乱数生成部126c-uとベクトル設定部126e-uと暗号化部126f-uとタグ情報生成部126g-uとを有する。登録装置120-uは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、登録装置120-uは、それぞれ、制御部125-uの制御のもと各処理を実行する。登録装置120-uでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。[ストレージ装置140]図3に例示するように、ストレージ装置140は、入力部141と出力部142と暗号化データベース格納部143と制御部145と書込み部146とバッチ検索部147と検索部148とを有する。ストレージ装置140は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、ストレージ装置140は、制御部145の制御のもと各処理を実行する。図4に例示するように、暗号化データベース格納部143には、文書などの検索対象情報TARの暗号文CTと、予め定められたキーワードの全体集合WSETから検索対象情報TARに対応するキーワード登録キーワードWTを除いた補集合CSETWSETWTに対して設定されるベクトルw→に対応する第1暗号方式の第1暗号文...Tと、第1暗号文...Tの復号値を共通鍵Kとした第2暗号方式共通鍵暗号方式の暗号文Tと、暗号文Tの復号値REとがそれぞれ対応付けられた暗号化データベースが格納されている。暗号文CTにそれぞれ対応付けられる...TTREを検索対象情報TARに対応するタグ情報Tag否定タグ情報と呼ぶ。否定タグ情報Tagの第1暗号文...Tは、検索クエリに対応する検索用キーワードが検索対象情報TARに対応する登録キーワードにヒットしないときに当該検索クエリを復号鍵として用いて正しく復号される暗号文である。また、この正しい復号値を共通鍵Kとして暗号文Tを復号した場合の復号値はREとなる。よって、検索クエリを用いて第1暗号文...Tを復号して得られる値を共通鍵Kとして暗号文Tを復号した値がREである場合、検索クエリに対応する検索用キーワードが検索対象情報TARに対応する登録キーワードにヒットしていないことになる。検索クエリに対応する検索用キーワードが登録キーワードにヒットすることの意義は検索方式による。また、暗号文CTを生成するための検索対象情報TARの暗号化方式には限定はなく、任意の既存の暗号化方式共通鍵暗号方式,公開鍵暗号方式,述語暗号方式、関数暗号方式などでよい。また、当該既存の暗号方式は、本形態の検索可能暗号を構成するための第1暗号方式と同じであっても違ってもよい。暗号化データベースの構成及び生成方法の詳細は後述する。図5に例示するように、暗号化データベース格納部143には、さらに暗号文CTと、検索対象情報TARに対応する登録キーワードに対して設定されるベクトルw→に対応する第1暗号方式の第2暗号文...LTと、第2暗号文...LTの復号値を共通鍵Kとした第3暗号方式共通鍵暗号方式の暗号文LTと、第2暗号文LTの復号値LRとが対応付けられた第2暗号化データベースが格納されている。暗号文CTにそれぞれ対応付けられる...LTLTLRを検索対象情報TARに対応するタグ情報LTag肯定タグ情報と呼ぶ。肯定タグ情報LTagの第2暗号文...LTは、検索クエリに対応する検索用キーワードが検索対象情報TARに対応する登録キーワードにヒットするときに当該検索クエリを復号鍵として用いて正しく復号される暗号文である。また、この正しい復号値を共通鍵Kとして暗号文LTを復号した場合に復号値としてLRが得られる。よって、検索クエリを用いて第2暗号文...LTを復号して得られる値を共通鍵Kとして暗号文LTを復号した値がLRである場合、検索クエリに対応する検索用キーワードが検索対象情報TARに対応する登録キーワードにヒットしていることになる。第2暗号化データベースの構成及び生成方法の詳細は後述する。[検索装置150-u]図6に例示するように、検索装置150-uは、入力部151-uと出力部152-uと検索対象情報復号鍵格納部154-uと制御部155-uとベクトル設定部156-uと検索クエリ生成部157-uと復号部158-uとを有する。検索装置150-uは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、検索装置150-uは、それぞれ、制御部155-uの制御のもと各処理を実行する。なお、図面表記の便宜上、図6には2つの入力部151-uが記載されているが、これは入力部の種類や個数を限定するものではない。<事前処理>前述した[内積述語暗号方式の基本構成]のSetupが実行され、マスタ秘密鍵MSK,公開パラメータPKが定められる。マスタ秘密鍵MSKは、管理装置110図2Aのマスタ秘密鍵格納部113に安全に格納される。管理装置110,登録装置120-u,及び検索装置150-uは、公開パラメータPKを用いた処理が可能なように構成される。登録装置120-u図2Bの登録キーワード格納部123b-uには、登録を行う検索対象情報TARの暗号文CTと検索対象情報TARに対応するキーワードWTとが格納されている。キーワードWTは、例えば、検索対象情報TARに含まれるキーワード又は複数のキーワードの集合である。検索装置150-u図6の検索対象情報復号鍵格納部154-uには、登録装置120-u図2Bの登録キーワード格納部123b-uに格納された暗号文CTを復号するための検索対象情報復号鍵Keyが格納されている。<データベース登録>登録ユーザは登録装置120-uを用い、図7に例示するようにデータベース登録を行う。登録されるデータベースは、図4に例示するような暗号文CTと否定タグ情報Tagとが対応付けられた暗号化データベース、及び、図5に例示するような暗号文CTと肯定タグ情報LTagとが対応付けられた第2暗号化データベースである。登録装置120-u図2Bのベクトル設定部126e-uが、登録キーワード格納部123b-uから検索対象情報TARに対応する登録キーワードWTを抽出するステップS101。ベクトル設定部126e-uは、予め定められたキーワードの全体集合WSETから検索対象情報TARに対応する登録キーワードWTを除いた補集合CSETWSETWTに対応するベクトルwCSET→∈Fqを設定する。具体的なベクトルwCSET→の構成は検索方式による。以下に具体的なベクトルwCSET→の構成例を示す。[ベクトルwCSET→の構成例1単一単語一致検索の場合]ベクトルwCSET→の構成例1は、単一単語一致検索に対応する例である。単一単語一致検索とは、検索用キーワードの少なくとも一部と検索対象情報TARに対応する登録キーワードの少なくとも一部とが順序及び内容について一致するという検索条件検索条件1と呼ぶを満たした場合にヒットとされる検索方式である。すなわち単一単語一致検索では、検索対象情報TARに対応する登録キーワードをWTη1ηLとし、検索用キーワードをWQx1xLとした以下の述語多項式の値が0になるときにヒットとされる。......この検索条件の否定を表す述語多項式を考える。すなわち、検索条件1を満たしていないときすなわちヒットしないときに0になる述語多項式を考える。この例では、キーワードの全体集合WSETから登録キーワードWTを除いた補集合CSETを以下のようにする。CSETηθπWSETηθ...ただし、θ1L、π1πmaxであり、πmaxは1以上の整数であり、ηθπmax⊥であり、xθに対応するキーワードが存在しない場合に0を満たす。式が表す検索条件の否定を表す述語多項式は以下のようになる。ι1......ιL......ただし、ι1ιLは乱数である。式の述語多項式の値が0となるときヒットするとき、式の述語多項式の値は0以外となる。式の述語多項式の値が0以外となるときヒットしないとき、式の述語多項式の値は0となる。式は以下のように変形できる。ただし、SYθπはに関するπ次の基本対称式である。ベクトルwCSET→の構成例1では、式のがベクトルwCSET→...として設定される。[ベクトルwCSET→の構成例2部分集合判定検索の場合]ベクトルwCSET→の構成例2は、部分集合判定検索に対応する例である。部分集合判定検索とは、検索用キーワードの少なくとも一部と検索対象情報TARに対応する登録キーワードの少なくとも一部とが順序にかかわらず内容について一致するという検索条件検索条件2と呼ぶを満たした場合にヒットとされる検索方式である。すなわち部分集合判定検索では、検索対象情報TARに対応する登録キーワードをWTη1ηLとし、検索用キーワードをWQx1xLとした以下の述語多項式の値が0になるときにヒットとされる。............この検索条件の否定を表す述語多項式を考える。すなわち、検索条件2を満たしていないときすなわちヒットしないときに0になる述語多項式を考える。この例では、キーワードの全体集合WSETから登録キーワードWTを除いた補集合CSETを以下のようにする。CSETηπWSETη1ηLただし、π1πmaxであり、πmaxは1以上の整数であり、ηθは前述の⊥である。式が表す検索条件の否定を表す述語多項式は以下のようになる。ι1......ιL......ただし、ι1ιLは乱数である。式の述語多項式の値が0となるときヒットするとき、式の述語多項式の値は0以外となる。式の述語多項式の値が0以外となるときヒットしないとき、式の述語多項式の値は0となる。式は以下のように変形できる。ただし、SYπはに関するπ次の基本対称式であるベクトルwCSET→の構成例2では、式のがベクトルwCSET→...として設定されるベクトルwCSET→の構成例の説明終わり/ステップS102。ベクトルwCSET→は暗号化部126f-uに入力される。暗号化部126f-uは、第1暗号方式に則ってベクトルwCSET→に対応する第1暗号文...Tを生成する。本形態の暗号化部126f-uは、wCSET→とした式に従って、以下のような第1暗号文...Tを生成する。C1...T∈G1nζ...ただし、この例ではNnζであるステップS103。乱数生成部126c-uはRE∈GTをランダムに生成し、REを暗号化部126f-uに送る。暗号化部126f-uは、gTτυ1を共通鍵Kとし、第2暗号方式に則ってREを暗号化した暗号文Tを生成する。例えば、暗号化部126f-uは、mesREとした式に従い、以下のように暗号文Tを生成する。C2TgTτυ1RE∈GT...このように生成された...T、T及びREはタグ情報生成部126g-uに送られるステップS104。タグ情報生成部126g-uは、...T、T及びREを互いに対応付けた否定タグ情報Tagを以下のように生成する。Tag...TTRE...否定タグ情報Tagは出力部122-uに送られるステップS105。また、ベクトル設定部126e-uは、検索対象情報TARに対応する登録キーワードWTに対応するベクトルwT→∈Fqを設定する。具体的なベクトルwT→の構成は検索方式による。以下に具体的なベクトルwT→の構成例を示す。[ベクトルwT→の構成例1単一単語一致検索の場合]ベクトルwT→の構成例1は、前述した単一単語一致検索に対応する例である。前述のように単一単語一致検索では、検索対象情報TARに対応する登録キーワードをWTη1ηLとし、検索用キーワードをWQx1xLとした式の述語多項式の値が0になるときにヒットとされる。式もその各項の不定元成分と1Fとを各要素とするベクトルw→と各項の係数成分を各要素とするベクトルv→との内積に変形できる。ベクトルwT→の構成例1では、そのベクトルw→がベクトルwT→として設定される。[ベクトルwT→の構成例2部分集合判定検索の場合]ベクトルwT→の構成例2は、前述の部分集合判定検索に対応する例である。前述のように部分集合判定検索では、検索対象情報TARに対応する登録キーワードをWTη1ηLとし、検索用キーワードをWQx1xLとした式の述語多項式の値が0になるときにヒットとされる。式もその各項の不定元成分と1Fとを各要素とするベクトルw→と各項の係数成分を各要素とするベクトルv→との内積に変形できる。ベクトルwT→の構成例2では、そのベクトルw→がベクトルwT→として設定されるベクトルwT→の構成例の説明終わり/ステップS106。ベクトルwT→は暗号化部126f-uに入力される。暗号化部126f-uは、第1暗号方式に則ってベクトルwT→に対応する第2暗号文...LTを生成する。本形態の暗号化部126f-uは、wT→とした式に従って、以下のように第2暗号文...LTを生成する。C1...LT∈G1nζ...ただし、この例ではNnζであるステップS107。乱数生成部126c-uはRE∈GTをランダムに生成し、REを暗号化部126f-uに送る。暗号化部126f-uは、gTτυ1を共通鍵Kとし、第2暗号方式に則ってLRを暗号化した暗号文LTを生成する。例えば、暗号化部126f-uは、mesLRとした式に従い、以下のように暗号文LTを生成する。C2LTgTτυ1LR∈GT...このように生成された...LT、LT及びLRはタグ情報生成部126g-uに送られるステップS108。タグ情報生成部126g-uは、...LT、LT及びLRを互いに対応付けた肯定タグ情報LTagを以下のように生成する。LTag...LTLTLR...肯定タグ情報LTagは出力部122-uに送られるステップS109。出力部122-uには、さらに前述の否定タグ情報LTag、及び登録キーワード格納部123b-uから読み出された検索対象情報TARの暗号文CTが送られる。出力部122-uは、CT、LTag及びLTagを出力するステップS110。CT、LTag及びLTagはストレージ装置図3の入力部141に入力される。書込み部146はCT、LTag及びLTagを互いに対応付け、図4及び5に示したように暗号化データベース格納部143に格納するステップS111。<バッチ検索用の事前計算>ストレージ装置図3のバッチ検索部147は、後述するバッチ検索のために以下のような事前計算を行う。この事前計算は定期的に行われてもよいし、暗号化データベース格納部143が更新されるたびに行われてもよい。或いは、暗号化データベース格納部143の更新後に後述するバッチ検索が始めて実行されるときに行われてもよい。以下では暗号化データベース格納部143に、indt1...maxtについてのCT及びTagが互いに対応付けられて格納されていることを前提とする図4参照。バッチ検索部147は、まずsub1...maxtとし、indN1...Nについて式を事前計算し、BT、BT、及びREをsubに対応付けて暗号化データベース格納部143に格納する。同様にsubを分割して得られるsubの真部分集合のそれぞれを新たなsubとし、indN1...Nについて式が事前計算され、BT、BT、及びREがsubに対応付けられて暗号化データベース格納部143に格納される処理が繰り返される。subの分割方法や分割回数はストレージ装置140で事前に定められ、この分割方法や分割回数は後述のバッチ検索にも対応する。ただし、どのような分割方法や分割回数が設定されるかについての限定はない。subの分割方法の例は、subをDIV個DIVは2や3などの正整数の真部分集合に分割する方法などである。subの分割回数の例は、subを分割して得られる新たなsubの要素数が基準値以下になるまで分割する方法や、事前に定められた固定回数まで分割する方法などである。例えば、subを2つの真部分集合に分割してsubを更新し、subの分割回数を2回とするのであれば、例えば、sub1...maxtに対する式の事前計算値、sub1...maxt2及びsub1...maxtのそれぞれに対する式の事前計算値、及びsub1...maxt4sub1...maxt2sub1...3maxt2sub1...maxtのそれぞれに対する式の事前計算値が暗号化データベース格納部143に格納される図4参照。<検索>登録ユーザは検索装置150-u図6を用い、以下のようにストレージ装置140に格納された暗号化データベースを検索する。図8に例示するように、まず検索を行う登録ユーザによって選択された検索用キーワードWQが入力部151-uに入力されるステップS121。検索用キーワードWQはベクトル設定部156-uに送られる。ベクトル設定部156-uは、システム内で定められた規則に従い、否定タグ情報Tag及び肯定タグ情報LTagのそれぞれに対し、検索方式と検索用キーワードWQに対応する第2ベクトルvQ→を設定する。否定タグ情報Tagに対応する第2ベクトルvQ→は、検索方式と検索用キーワードWQとの組に対して第1ベクトルwT→に対応する登録キーワードWTがヒットする場合に内積wT→vQ→≠0を満たし、ヒットしない場合に内積wT→vQ→0を満たすものである。例えば、前述のベクトルwCSET→の構成例1の場合、ベクトル設定部156-uは、式が含む以下のベクトルを第2ベクトルvQ→とする。...ι1SY1πmaxι2SY20...ι2SY2πmax...ιLSYLπmax...或いは、前述のベクトルwCSET→の構成例2の場合、式が含む以下のベクトルを第2ベクトルvQ→とする。...SYπmax...肯定タグ情報Tagに対応する第2ベクトルvQ→は、検索方式と検索用キーワードWQとの組に対して第1ベクトルwT→に対応する登録キーワードWTがヒットする場合に内積wT→vQ→0を満たし、ヒットしない場合に内積wT→vQ→≠0を満たすものである。例えば、ベクトルwT→の構成例1の場合、式を各項の不定元成分と1Fとを各要素とするベクトルw→と各項の係数成分を各要素とするベクトルv→との内積に変形した場合のベクトルv→を第2ベクトルvQ→とする。或いは、ベクトルwT→の構成例2の場合、式を各項の不定元成分と1Fとを各要素とするベクトルw→と各項の係数成分を各要素とするベクトルv→との内積に変形した場合のベクトルv→を第2ベクトルvQ→とするステップS122。否定タグ情報Tag及び肯定タグ情報LTagのそれぞれに設定された第2ベクトルvQ→は検索クエリ生成部157-uに送られる。検索クエリ生成部157-uは、出力部152-uを介して管理装置110にアクセスし、管理装置110図2Aに否定タグ情報Tag及び肯定タグ情報LTagのそれぞれに設定された第2ベクトルvQ→を送る。これらは管理装置110の入力部111に入力され、鍵情報生成部116aに送られる。鍵情報生成部116aは、マスタ秘密鍵格納部113に格納されたマスタ鍵情報MSKを用い、否定タグ情報Tagに対する第2ベクトルvQ→に対応する第1暗号方式の復号鍵である検索クエリQUEと、肯定タグ情報LTagに対する第2ベクトルvQ→に対応する第1暗号方式の復号鍵である検索クエリQUEとをそれぞれ生成する。これらはvQ→とした式に従ってそれぞれ生成できる。Tag∈G2nζ...LTag∈G2nζ...ただし、nζNであり、ζ>ζの場合には、queN...queN0LqueN...LqueN0とされる。検索クエリQUEと検索クエリQUEは出力部112から出力され、検索装置150-u図6の入力部151-u経由で検索クエリ生成部157-uに送られるステップS123。生成された検索クエリQUE及びQUEは出力部152-uに送られ、出力部152-uはこれらを出力するステップS124。図9に示すように、検索クエリQUE及びQUEはストレージ装置140図3の入力部141に入力され、バッチ検索部147と検索部148にそれぞれ送られるステップS131。制御部145は、まずsub1...maxtとするステップS132。バッチ検索部147は、否定タグ情報Tagに対する検索クエリQUEを用い、暗号化データベース格納部143に格納された否定タグ情報Tagをまとめてバッチ検証する。すなわち、検索クエリQUEを用い、inds∈sub⊆1...maxtについての第1暗号文...Tの合成値式が正しく復号できるかを判定する。具体的には本形態のバッチ検索部147は、検索クエリQUEを復号鍵として用い、inds∈subについての第1暗号文...Tの関数値...BT式を第1暗号方式に則って復号して得られる値を共通鍵とし、inds∈subについての暗号文Tの関数値BT式を第2暗号方式に則って復号して得られる値がinds∈subについての復号値REの関数値RE式であるかtrue否かfalseを判定する。例えば、式のような計算で否定タグ情報Tagが得られたのであれば、バッチ検索部147は、以下を満たすかtrue否かfalseを判定する。原則、この判定を行うために必要な...BT、BT、及びREは、前述の事前計算で得られたものである。ただし、必要な...BT、BT、及びREが格納されていないのであれば、バッチ検索部147はそれらを計算してこの判定を行い、以降の処理のためにそれらの値を暗号化データベース格納部143に格納しておいてもよい。また、式によって否定タグ情報Tagをまとめてバッチ検証できるのは、次の関係が成り立つことに立脚している。式の右辺は式の左辺の分母である。この事実は前述した双線形写像Pairの線形性式参照から成り立つステップS133。ステップS133の判定でtrueと判定された場合にはステップS134、検索用キーワードWQに対して何れの検索対象情報TARもヒットしないことになる。この場合にはinds∈subに対応する各検索対象情報TARに対する検索が終了し、ステップS139へ進む。一方、ステップS133の判定でfalseと判定された場合...Tの合成値が正しく復号できないと判定された場合にはステップS134、検索用キーワードWQに対して何れの検索対象情報TARがヒットすることになる。この場合にはステップS135に進み、subの要素数が基準値以下であるかが判定される。なお、基準値の例は1や2以上の整数定数やDIVなどであるステップS135。ステップS135でsubの要素数が基準値以下ではないと判定された場合には、subを分割して得られるsubの真部分集合のそれぞれを新たなsubとし、ステップS133に戻る。なお、ここでのsubの分割方法は、例えば前述のバッチ検索用の事前計算でのsubの分割方法と同一とするステップS136。一方、ステップS135でsubの要素数が基準値以下であると判定された場合、検索クエリQUEを用いた肯定タグ情報LTagの検証に切り替えられる。すなわち、検索部148が検索クエリQUE第2検索クエリを復号鍵として用い、第2暗号文...LTinds∈subが正しく復号できるかを判定する。本形態の検索部148は検索クエリQUEを復号鍵として用い、肯定タグ情報LTagが含む第2暗号文...LTinds∈sub図5を第1暗号方式に則って復号して得られる値を共通鍵とし、暗号文LTを第3暗号方式に則って復号して得られる値が復号値LRであるかを判定する。例えば、式のような計算で肯定タグ情報LTagが得られたのであれば、検索部148は、以下を満たすかtrue否かfalseを判定する。これは、検索対象情報TARが検索用キーワードWQにヒットするかtrue否かfalseを肯定タグ情報LTagごとに判定することに相当するステップS137。検索部148は、ステップS137の判定でtrueと判定された肯定タグ情報LTagのindsに対応する暗号文CTを集合HITに追加し、図示しないメモリに格納しステップS138、ステップS139に進む。ステップS139では、制御部145が未検証のsubが存在するかを判定するステップS139。ここで、未検証のsubが存在すると判定された場合には、ステップS133に進む。一方、未検証のsubが存在しないと判定された場合には、検索部148は、集合HITの要素である暗号文CTを出力する。集合HITの要素が存在しなければ検索部148は、ヒットしなかったことを表す⊥を出力するステップS140。これらは出力部142から出力される。図8に示すように、集合HITの要素である暗号文CT又は⊥は、検索装置図6の入力部151-uに入力されるステップS125。暗号文CTは、復号部158-uに送られる。復号部158-uは検索対象情報復号鍵格納部154-uから検索対象情報復号鍵Keyを読み出し、これを用いて暗号文CTを復号して検索対象情報TARを出力するステップS126。図10を用いて上記の処理を概念的に説明する。なお、図10はsubを2個の真部分集合に分割する例であるが、これは本発明を限定しない。最初にsub1...maxtsetとされステップS132、検索クエリを用いてTagをまとめてバッチ検証するステップS133。ステップS133でtrueであればsubについての検索を終了する。ステップS133でfalseであれば、setを分割して得られるsub1及びsub2がそれぞれsubとされステップS136、ステップS133の処理が実行される。ステップS133でtrueと判定されたsubについての検索を終了し、ステップS133でfalseのsubについてはさらに分割を行う。例えば、sub1及びsub2で共にfalseと判定されたのであれば、sub1を分割して得られるsub3並びにsub4、及びsub2を分割して得られるsub5並びにsub6がそれぞれsubとされ、ステップS133の処理が実行される。例えばsub3の要素数が基準値以下であるとすると、sub3を分割したsub7及びsub8の各要素に対してステップS137の処理が実行され、ステップS137でtrueとされたindsに対応する暗号文CTが集合HITに追加されるステップS138。第2実施形態次に本発明の第2実施形態を説明する。本形態では、第1暗号方式として階層的内積述語暗号方式を用いる。以下では、第1実施形態との相違点を中心に説明し、第1実施形態と共通する事項については第1実施形態と同じ参照番号を用い、説明を簡略化する。<構成>図11に例示するように、本形態の検索可能暗号システム2は、管理装置210-mm1Mと登録装置220-uu1Uと検索代行装置230とストレージ装置240と検索装置250-uu1Uとを有する。なお、M及びUはそれぞれ1以上の整数である。また、管理装置210-mは、検索可能暗号システム2のm番目の管理者が使用する装置である。本形態では、小さいmに対応する管理者ほど強い管理権限を持つ。すなわち、m=1に対応する管理者が最も強い権限を持つ。また、登録装置220-u及び検索装置250-uは、検索可能暗号システム2を利用するu番目の登録ユーザが使用する装置である。また、各装置は他の装置へ情報を提供可能なように構成されている。装置間の情報提供はネットワークを通じて行われてもよいし、可搬型記録媒体を介して行われてもよい。[管理装置]図12Aに例示するように、管理装置210-1は、入力部211-1と出力部212-1とマスタ秘密鍵格納部213-1と管理者秘密鍵格納部214-1と制御部215-1とベクトル設定部216a-1と鍵情報生成部216b-1と補間鍵生成部216d-1と検索者鍵生成部216c-1と失効情報生成部216e-1とを有する。図12Bに例示するように、管理装置210-m’1m1M1は、入力部211-m’1と出力部212-m’1と制御部215-m’1とベクトル設定部216a-m’1と鍵情報生成部216b-m’1とを有する。管理装置210-mは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、管理装置210-mは、それぞれ、制御部215-mの制御のもと各処理を実行する。また、管理装置210-mでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。[登録装置]図13に例示するように、登録装置220-uは、入力部221-uと出力部122-uと属性格納部223a-uと登録キーワード格納部123b-uと検索者鍵格納部223c-uと制御部125-uと写像部226a-u,226d-uと乱数生成部226b-u,126c-uとベクトル設定部226e-uと暗号化部226f-uとタグ情報生成部226g-uとを有する。登録装置220-uは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、登録装置220-uは、それぞれ、制御部125-uの制御のもと各処理を実行する。なお、図面表記の便宜上、図13には2つの入力部221-uが記載されているが、これは入力部の種類や個数を限定するものではない。また、登録装置220-uでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。[検索代行装置230]図14Aに例示するように、検索代行装置230は、入力部231と出力部232と補間鍵格納部233と制御部235と写像部236と検証処理部237バッチ検索部及び検索部に相当とを有する。検索代行装置230は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、検索代行装置230は、それぞれ、制御部235の制御のもと各処理を実行する。また、検索代行装置230での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。なお、図面表記の便宜上、図14Aには2つの入力部231が記載されているが、これは入力部の種類や個数を限定するものではない。[ストレージ装置240]図14Bに例示するように、ストレージ装置240は、入力部141と出力部142と暗号化データベース格納部243と制御部145と読み書き部246とを有する。ストレージ装置240は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、ストレージ装置240は、制御部235の制御のもと各処理を実行する。図15Aに例示するように、暗号化データベース格納部243には、文書などの検索対象情報TARの暗号文CTと、第1実施形態と同様な第1暗号文...Tと、第1暗号文...Tの復号値を共通鍵Kとした第2暗号方式共通鍵暗号方式の暗号文Tと、暗号文Tの復号値reREに対するeに対応するhと、REとがそれぞれ対応付けられた暗号化データベースが格納されている。なお、eはhとckuに対応する詳細は後述。本形態では、暗号文CTにそれぞれ対応付けられる...TThREを検索対象情報TARに対応するタグ情報Tag否定タグ情報と呼ぶ。否定タグ情報Tagの第1暗号文...Tは、検索クエリに対応する検索用キーワードが検索対象情報TARに対応する登録キーワードにヒットしないときに当該検索クエリを復号鍵として用いて正しく復号される暗号文である。また、この正しい復号値を共通鍵Kとして暗号文Tを復号した場合の復号値はeREとなる。よって、検索クエリを用いて第1暗号文...Tを復号して得られる値を共通鍵Kとして暗号文Tを復号した値がeREである場合、検索クエリに対応する検索用キーワードが検索対象情報TARに対応する登録キーワードにヒットしていないことになる。暗号化データベースの構成及び生成方法の詳細は後述する。図15Bに例示するように、暗号化データベース格納部243には、さらに暗号文CTと、第1実施形態と同様な第2暗号文...LTと、第2暗号文...LTの復号値を共通鍵Kとした第3暗号方式共通鍵暗号方式の暗号文LTと、第2暗号文LTの復号値LreLRに対するeに対応するhと、LRとがそれぞれ対応付けられた第2暗号化データベースが格納されている。暗号文CTにそれぞれ対応付けられる...LTLThLRを検索対象情報TARに対応するタグ情報LTag肯定タグ情報と呼ぶ。肯定タグ情報LTagの第2暗号文...LTは、検索クエリに対応する検索用キーワードが検索対象情報TARに対応する登録キーワードにヒットするときに当該検索クエリを復号鍵として用いて正しく復号される暗号文である。また、この正しい復号値を共通鍵Kとして暗号文LTを復号した場合に復号値としてeLRが得られる。よって、検索クエリを用いて第2暗号文...LTを復号して得られる値を共通鍵Kとして暗号文LTを復号した値がeLRである場合、検索クエリに対応する検索用キーワードが検索対象情報TARに対応する登録キーワードにヒットしていることになる。第2暗号化データベースの構成及び生成方法の詳細は後述する。[検索装置250-u]第1暗号方式が異なり、検索クエリ生成部257-uが検索クエリ生成部257-uに置換され、鍵情報格納部253-uが追加される以外、第1実施形態と同様であるため説明を省略する。<事前処理>前述した[階層的内積述語暗号方式の基本構成]のSetupが実行され、階層フォーマットξ→,マスタ秘密鍵MSK,公開パラメータmpkが定められる。マスタ秘密鍵MSKは、管理装置210-1図12Aのマスタ秘密鍵格納部213-1に安全に格納され、管理装置210-m,登録装置220-u,検索装置250-u及び検索代行装置230が、公開パラメータmpkを用いた処理が可能なように構成される。また、管理装置210-m及び登録装置220-uが階層フォーマットξ→に従った処理が可能なように構成される。管理装置210-1図12Aの管理者秘密鍵格納部214-1には、有限体Fqの任意の元である管理者秘密鍵ax∈Fqが安全に格納されているものとする。登録装置220-u図13の登録キーワード格納部123b-uには、登録を行う検索対象情報TARの暗号文CTと検索対象情報TARに対応するキーワード登録キーワードWTとが格納されている。さらに、登録装置220-uの属性格納部223a-uには、登録装置220-uを利用するユーザの属性を表す情報以下、単に属性というが格納されている。ユーザの属性の例は、ユーザが所属するグループを表す情報会社名、所属部門、課、担当、グループなど、住所、年齢、職業、趣味などである。検索装置250-u図6の検索対象情報復号鍵格納部154-uには、登録装置220-u図13の登録キーワード格納部123b-uに格納された暗号文CTを復号するための検索対象情報復号鍵Keyが格納されている。<ユーザ登録>ユーザ登録では、管理装置210-mが登録ユーザの属性に対して設定されたベクトルに対応する鍵情報kMを生成する。鍵情報kMの生成方式は大きく分けて2通り存在する。一つ目の方式は、管理装置210-1が前述の[階層的内積述語暗号方式の基本構成]のGenKeyのみに従って鍵情報kMを生成する方式である一括方式。このような方式は小規模グループに適したものであるといえる。二つ目の方式は、管理装置210-1が前述のGenKeyに従い、その他の管理装置210-m’1が前述のDelegateに従い、鍵情報kMを生成する方式である委託方式。このような方式は階層化された大規模グループに適したものであるといえる。[一括方式]図16は、一括方式によって鍵情報kMを生成する処理を説明するためのフローチャートである。一括方式では、最も強い権限をもつm=1に対応する管理者の管理装置210-1のみによって鍵情報kMを生成する。まず、管理装置210-1図12Aの入力部211-1に登録ユーザの属性ATTが入力される。属性ATTはM層ATT1ATTMに階層化されている。各層に対応する属性ATTmを部分属性と呼ぶことにし、小さいmに対応する部分属性ATTmほど上位の属性を表すものとする。例えば、M2の場合、属性ATTは2層の部分属性ATT1及びATT2からなり、この場合の部分属性の例は、ATT1○○株式会社,○○部門...ATT2○○課,○○担当,○○グループ...であるステップS201。入力された属性ATTはベクトル設定部216a-1に入力される。ベクトル設定部216a-1は、階層フォーマットξ→及びシステム内で定められた規則に従って属性ATTに対応するベクトルを設定する。例えば、ベクトル設定部216a-1は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、属性ATTを表すベクトルを式に従って設定し、内積wω→vω→0Fとなる式に従ったベクトルを属性ATTに対応するベクトルとする。式の例を用いて説明すると、例えば、ベクトル設定部216a-1は、部分属性ATT1を○○株式会社を表すw1及び○○部門を表すw2を要素とする2次元のベクトルw1→...に変換し、部分属性ATT2を○○課を表すw3、○○担当を表すw4、及び○○グループを表すw5を要素とする3次元のベクトルw2→...に変換し、属性ATTを表すベクトルを設定し、内積wω→vω→0Fとなるベクトルを属性ATTに対応するベクトルとする。なお、システム内で定められた規則に基づいて定められるのであれば、属性ATTを表すベクトルをどのように定めるかについては特に限定はなく、属性ATTごとにベクトルが定まるのであればどのような方法でもよいステップS202。生成されたベクトルは鍵情報生成部216b-1に入力される。鍵情報生成部216b-1は、マスタ秘密鍵格納部213-1からマスタ秘密鍵MSKを読み出し、mMとした前述のGenKeyに従い、ベクトルに対応する鍵情報kMを生成する。例えば、鍵情報生成部216b-1は、mMとした式に従って鍵情報kMを生成する。生成された鍵情報kMは出力部212-1に送られるステップS203。また、検索者鍵生成部216c-1が、有限体Fqから任意の元を選択し、それを登録ユーザの検索者鍵sxu∈Fqとする。生成された検索者鍵sxuは出力部212-1及び補間鍵生成部216d-1に送られるステップS204。検索者鍵sxuが送られた補間鍵生成部216d-1は、管理者秘密鍵格納部214-1から管理者秘密鍵axを抽出し、当該検索者鍵sxuと管理者秘密鍵axとの組の像である補間鍵ckuを生成する。例えば、補間鍵生成部216d-1は、によって補間鍵ckuを生成する。生成された補間鍵ckuは出力部212-1に送られるステップS205。出力部212-1は、鍵情報kMM≦d1及び検索者鍵sxuを出力する。鍵情報kMは登録ユーザが使用する検索装置250-u図6の入力部151-uに入力され、鍵情報格納部253-uに格納される。検索者鍵sxuは登録ユーザが使用する登録装置220-u図13の入力部221-uに入力され、検索者鍵格納部223c-uに格納されるステップS106。また、出力部212-1図12Aは、補間鍵ckuを出力する。補間鍵ckuは検索代行装置230図14Aの入力部231に入力され、登録ユーザに対応付けられて補間鍵格納部233に格納されるステップS207。[委託方式]図17及び18は、委託方式によって鍵情報kMを生成する処理を説明するためのフローチャートである。委託方式では、最も強い権限をもつm=1に対応する管理者の管理装置210-1が前述のGenKeyに従って鍵情報k1を生成し、上位階層の鍵情報を受け取った下位階層の管理者の管理装置210-m’1が前述のDelegateに従って鍵情報を生成していき、最終的に鍵情報kMが生成される。まず、管理装置210-1図12Aの入力部211-1に登録ユーザの部分属性ATT1が入力されるステップS211。入力された部分属性ATT1はベクトル設定部216a-1に入力される。ベクトル設定部216a-1は、階層フォーマットξ→及びシステム内で定められた規則に従って部分属性ATT1に対応するベクトルv1→を設定する。例えば、ベクトル設定部216a-1は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、部分属性ATT1を表すベクトルw1→を式に従って設定し、内積w1→v1→0Fとなる式に従ったベクトルv1→を部分属性ATT1に対応するベクトルとする。式の例を用いて説明すると、例えば、ベクトル設定部216a-1は、式によって部分属性ATT1を表すベクトルw1→を設定し、内積w1→v1→0Fとなる式のベクトルv1→を、部分属性ATT1に対応するベクトルとするステップS212。生成されたベクトルv1→は鍵情報生成部216b-1に入力される。鍵情報生成部216b-1は、マスタ秘密鍵格納部213-1からマスタ秘密鍵MSKを読み出し、m1とした前述のGenKeyに従い、ベクトルv1→に対応する鍵情報k1を生成する。例えば、鍵情報生成部216b-1は、m1とした式に従って鍵情報k1を生成する。生成された鍵情報k1は出力部212-1に送られるステップS213。また、一括方式と同じステップS204及びS205の処理が実行される。出力部212-1はステップS204で得られた検索者鍵sxuを出力する。検索者鍵sxuは登録ユーザが使用する登録装置220-u図13の入力部221-uに入力され、検索者鍵格納部223c-uに格納されるステップS216。また、出力部212-1はステップS205で得られた補間鍵ckuを出力する。補間鍵ckuは検索代行装置230図14Aの入力部231に入力され、登録ユーザに対応付けられて補間鍵格納部233に格納されるステップS207。さらに、出力部212-1はステップS213で得られた鍵情報k1を出力する。鍵情報k1は管理装置210-2に入力される。管理装置210-2以降では前述したDelegatem1M1に従って鍵生成が行われる。以下では管理装置210-m’から鍵情報kmを受け取る管理装置210-m’1の処理を一般化して説明する。まず、鍵情報kmが管理装置210-m’1図12Bの入力部211-m’1に入力され、鍵情報生成部216b-m’1に入力されるステップS220。また、部分属性ATTm1がベクトル設定部216a-m’1に入力される。ベクトル設定部216a-m’1は、階層フォーマットξ→及びシステム内で定められた規則に従って部分属性ATTm1に対応するベクトルvm1→を設定する。例えば、ベクトル設定部216a-m’1は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、部分属性ATTm1を表すベクトルwm1→を式に従って設定し、内積wm1→vm1→0Fとなる式に従ったベクトルvm1→を部分属性ATTm1に対応するベクトルとする。生成されたベクトルvm1→は鍵情報生成部216b-m’1に入力されるステップS222。鍵情報kmとベクトルvm1→とが入力された鍵情報生成部216b-m’1は、前述のDelegateに従って、ベクトルに対応する鍵情報km1を生成する。例えば、鍵情報生成部216b-m’1は、式に従って鍵情報km1を生成する。生成された鍵情報km1は出力部212-m’1に送られるステップS223。出力部212-m’1は鍵情報km1を出力するステップS228。m1Mの場合、出力された鍵情報km1は下位階層の管理装置210-m’2に入力され、m1を新たなmとしてステップS220-S228の処理が実行される。一方、m1Mの場合、出力された鍵情報km1kMは、登録ユーザが使用する検索装置250-u図6の入力部151-uに入力され、鍵情報格納部253-uに格納される。<データベース登録>図19及び20に示すように、登録ユーザは登録装置220-uを用い、以下のようにデータベース登録を行うことができる。まず、登録装置220-u図13の写像部226a-uが、登録キーワード格納部123b-uから検索対象情報TARに対応する登録キーワードWTを抽出するステップS231。また、乱数生成部226b-uが、キーワードWTに対して有限体Fqの任意の元である選択値rWT∈Fqを選択する。選択値rWTは写像部226a-uに入力されるステップS132。写像部226a-uは、さらに検索者鍵格納部223c-uから検索者鍵sxuを抽出し、WT,sxu,rWTを用いて値hを生成する登録ユーザの検索者鍵sxuの像である第1値h。例えば、写像部226a-uは、入力値に対して巡回群G1の元を出力する擬似ランダム関数Hσを用い、で表される値hを生成する。なお、どのような擬似ランダム関数Hσを用いてもかまわないが、例えば、鍵付きハッシュ関数を擬似ランダム関数Hσとして用いることができるステップS233。生成された値hは出力部122-u及びタグ情報生成部226g-uに送られる。出力部122-uは値hを出力するステップS234。登録装置220-uから出力された値hは、検索代行装置230図14Aの入力部231に入力され、写像部236に送られる。写像部236は、補間鍵格納部233から登録装置220-uを利用する登録ユーザに対応する補間鍵ckuを抽出する。写像部236は、当該値hと補間鍵ckuとの組の像である値eを生成する。例えば、写像部236は、当該値hと補間鍵ckuとの組に式の双線形写像Pairを施して値eを生成する。すなわち、ePaircku∈GT...で表される値eを生成するステップS235。値eは出力部232送られ、出力部232は値eを出力するステップS236。検索代行装置230から出力された値eは、登録装置220-u図13の入力部221-uに入力され、写像部226d-uに送られる。写像部226d-uは値eの像である値rを生成する。例えば、まず乱数生成部126c-uが巡回群GTの任意の元RELRを生成して写像部226d-u及びタグ情報生成部226g-uに送りステップS237、写像部226d-uが、r=REe...で表される値rを生成する。値rは暗号化部226f-uに送られるステップS238。また登録装置220-u図13のベクトル設定部226e-uは、属性格納部223a-uから登録ユーザの属性ATTを抽出する。この属性ATTは当該登録ユーザのユーザ登録時に用いられたものと同じである。ベクトル設定部226e-uは、階層フォーマットξ→及びシステム内で定められた規則に従って属性ATTを表すベクトルを設定する。当該ベクトルとユーザ登録時のステップS202で設定されたベクトルとは、ω1Mについて内積wω→vω→0Fを満たす。生成されたベクトルは暗号化部226f-uに送られるステップS240。ベクトル設定部226e-uが、第1実施形態のステップS102と同様に、補集合CSETに対応するベクトルwCSET→∈Fqを設定する。ベクトルwCSET→は暗号化部226f-uに入力される。暗号化部226f-uは、第1暗号方式に則ってベクトルw1→wM→wCSET→に対応する第1暗号文...Tを生成する。本形態の暗号化部226f-uは、とした式に従って、以下のような第1暗号文...Tを生成する。C1...T∈G1n3...ただし、この例ではNn3であるステップS243。暗号化部226f-uは、gTτυ1を共通鍵Kとし、第2暗号方式に則って値rを暗号化した暗号文Tを生成する。例えば、暗号化部226f-uは、mesrとした式に従い、以下のように暗号文Tを生成する。C2TgTτυ1r∈GT...このように生成された...T及びTは、タグ情報生成部226g-uに送られるステップS244。タグ情報生成部226g-uは、...T、T、h及びREを互いに対応付けた否定タグ情報Tagを以下のように生成する。Tag...TThRE...否定タグ情報Tagは出力部122-uに送られるステップS245。また、ベクトル設定部226e-uは、第1実施形態のステップS106と同様に、検索対象情報TARに対応する登録キーワードWTに対応するベクトルwT→∈Fqを設定する。ベクトルwT→は暗号化部226f-uに入力される。暗号化部226f-uは、第1暗号方式に則ってベクトルw1→wM→wT→に対応する第2暗号文...LTを生成する。本形態の暗号化部226f-uは、とした式に従って、以下のように第2暗号文...LTを生成する。C1...LT∈G1n3...ただし、この例ではNn3であるステップS247。暗号化部226f-uは、gTτυ1を共通鍵Kとし、第2暗号方式に則って値rを暗号化した暗号文LTを生成する。例えば、暗号化部226f-uは、mesrとした式に従い、以下のように暗号文LTを生成する。C2TgTτυ1r∈GT...このように生成された...LT及びLTは、タグ情報生成部226g-uに送られるステップS248。タグ情報生成部226g-uは、...LT、LT、h及びLRを互いに対応付けた肯定タグ情報LTagを以下のように生成する。LTag...LTLThLR...否定タグ情報Tagは出力部122-uに送られるステップS249。出力部122-uには、さらに前述の否定タグ情報LTag、及び登録キーワード格納部123b-uから読み出された検索対象情報TARの暗号文CTが送られる。出力部122-uは、CT、LTag及びLTagを出力するステップS250。CT、LTag及びLTagはストレージ装置図14Bの入力部141に入力される。書込み部246はCT、LTag及びLTagを互いに対応付け、図15A及びBに示したように暗号化データベース格納部243に格納するステップS251。<バッチ検索用の事前計算>検索代行装置230図14Aの検証処理部237は、後述するバッチ検索のために以下のような事前計算を行う。この事前計算は定期的に行われてもよいし、暗号化データベース格納部243が更新されるたびに行われてもよい。或いは、暗号化データベース格納部243の更新後に後述するバッチ検索が始めて実行されるときに行われてもよい。以下ではストレージ装置240の暗号化データベース格納部243に、indt1...maxtについてのCT及びTagが互いに対応付けられて格納されていることを前提とする図15A参照。検証処理部237は、ストレージ装置240にアクセスし、暗号化データベース格納部243を用いて以下の処理を行う。検証処理部237は、まずsub1...maxtとし、indN1...Nについて前述の式及び以下の式を事前計算し、BT、BT、RE、h、eをsubに対応付けて暗号化データベース格納部243に格納する。同様にsubを分割して得られるsubの真部分集合のそれぞれを新たなsubとし、indN1...Nについて式が事前計算され、BT、BT、RE、h、eがsubに対応付けられて暗号化データベース格納部243に格納される処理が繰り返される。subの分割方法や分割回数は、第1実施形態と同様、検索代行装置230で事前に定められる。<検索>登録ユーザは検索装置250-u図6を用い、以下のように検索を行う。図21に示すように、まず第1実施形態で説明したステップS121及びS122の処理が実行される。否定タグ情報Tag及び肯定タグ情報LTagのそれぞれに設定された第2ベクトルvQ→は検索クエリ生成部257-uに送られる。検索クエリ生成部257-uは、鍵情報格納部253-uから鍵情報kMを抽出する。検索クエリ生成部257-uは、kMと否定タグ情報Tagに設定されたvQ→とを用い、mMとした前述のDelegateによって、ベクトルv1→vM→及びvM1→vQ→に対応する鍵情報復号鍵kM1である検索クエリQUEを生成する。また検索クエリ生成部257-uは、kMと肯定タグ情報LTagに設定されたvQ→とを用い、mMとした前述のDelegateによって、ベクトルv1→vM→及びvM1→vQ→に対応する鍵情報復号鍵kM1である検索クエリQUEを生成する。これらは例えば、mMM≦d1とした式に従ってそれぞれ生成できる。ただし、md1の場合には式のkm1αを含まない。Tag∈G2n3...LTag∈G2n3...ただし、この例ではn3NであるステップS253。生成された検索クエリQUE及びQUEは出力部152-uに送られ、出力部152-uはこれらを出力するステップS124。図9に示すように、検索クエリQUE及びQUEは、検索代行装置230図14Aの入力部231に入力され、検証処理部237及び制御部235に送られるステップS261。制御部235は、補間鍵格納部233を参照し、検索クエリQUE及びQUEに対応する登録ユーザの補間鍵ckuが利用可能であるかを検証する。検索クエリQUE及びQUEに対応する登録ユーザの補間鍵ckuが利用可能でない場合とは、検索クエリQUE及びQUEに対応する登録ユーザの補間鍵ckuが補間鍵格納部233に格納されていない場合や、補間鍵格納部233に格納された補間鍵ckuの使用が禁止されている場合であるステップS271。ここで、検索クエリQUE及びQUEに対応する登録ユーザの補間鍵ckuが利用可能でない場合には、出力部232が該当なしを表す⊥を出力して処理を終了するステップS272。一方、検索クエリQUE及びQUEに対応する登録ユーザの補間鍵ckuが利用可能である場合には、制御部235は、まずsub1...maxtとするステップS262。検索代行装置230はストレージ装置240図14Bにアクセスし、入力部231,141、出力部232、142、及び読み書き部246を通じ、暗号化データベース格納部243に格納されたデータにアクセス可能な状態とされる。検索代行装置230図14Aの検証処理部237は、否定タグ情報Tagに対する検索クエリQUEを用い、暗号化データベース格納部243に格納された否定タグ情報Tagをまとめてバッチ検証する。すなわち、検索クエリQUEを用い、inds∈sub⊆1...maxtについての第1暗号文...Tの合成値式が正しく復号できるかを判定する。具体的には本形態の検証処理部237は、検索クエリQUEを復号鍵として用い、inds∈subについての第1暗号文...Tの関数値...BT式を第1暗号方式に則って復号して得られる値を共通鍵とし、inds∈subについての暗号文Tの関数値BT式を第2暗号方式に則って復号して得られる値が、inds∈subについての復号値REの関数値RE式とe式とについてeREとなるかtrue否かfalseを判定する。例えば、式のような計算で否定タグ情報Tagが得られたのであれば、検証処理部237は、以下を満たすかtrue否かfalseを判定する。原則、この判定を行うために必要な...BT、BT、e及びREは、前述の事前計算で得られたものである。ただし、必要な...BT、BT、e及びREが格納されていないのであれば、検証処理部237はそれらを計算してこの判定を行い、以降の処理のためにそれらの値を暗号化データベース格納部243に格納しておいてもよいステップS263。ステップS263の判定でtrueと判定された場合にはステップS264、inds∈subに対応する各検索対象情報TARに対する検索が終了し、ステップS269へ進む。一方、ステップS263の判定でfalseと判定された場合...Tの合成値が正しく復号できないと判定された場合にはステップS264、ステップS265に進み、subの要素数が基準値以下であるかが判定されるステップS265。ステップS265でsubの要素数が基準値以下ではないと判定された場合には、subを分割して得られるsubの真部分集合のそれぞれを新たなsubとし、ステップS263に戻る。なお、ここでのsubの分割方法は、例えば前述のバッチ検索用の事前計算でのsubの分割方法と同一とするステップS266。一方、ステップS265でsubの要素数が基準値以下であると判定された場合、検索クエリQUEを用いた肯定タグ情報LTagの検証に切り替えられる。すなわち、検証処理部237が検索クエリQUE第2検索クエリを復号鍵として用い、第2暗号文...LTinds∈subが正しく復号できるかを判定する。本形態の検証処理部237は検索クエリQUEを復号鍵として用い、肯定タグ情報LTagが含む第2暗号文...LTinds∈sub図15Bを第1暗号方式に則って復号して得られる値を共通鍵とし、暗号文LTを第3暗号方式に則って復号して得られる値がPairLRであるかを判定する。例えば、式のような計算で肯定タグ情報LTagが得られたのであれば、検証処理部237は、以下を満たすかtrue否かfalseを判定する。これは、肯定タグ情報LTagに対応する登録キーワードが検索クエリQUEに対応する検索用キーワードにヒットするかtrue否かfalseを肯定タグ情報LTagごとに判定することに相当するステップS267。検証処理部237は、ステップS267の判定でtrueとされた肯定タグ情報LTagのindsに対応する暗号文CTを集合HITに追加し、図示しないメモリに格納しステップS268、ステップS269に進む。ステップS269では、検証処理部237が未検証のsubが存在するかを判定するステップS269。ここで、未検証のsubが存在すると判定された場合には、ステップS263に進む。一方、未検証のsubが存在しないと判定された場合には、検証処理部237は、集合HITの要素である暗号文CTを出力する。集合HITの要素が存在しなければ、検証処理部237はヒットしなかったことを表す⊥を出力するステップS270。これらは出力部232から出力される。その後、第1実施形態で説明したステップS125及びS126の処理が実行される。各実施形態の特徴上述の方法により、検索処理回数を大幅に削減できる。例えば、maxt個の検索対象情報TARに対応する暗号化データベースを検索する場合、従来法であれば最大maxt回の判定処理が必要であったが、上述の方法でsubを2個に分割して新たなsubとする場合にはlog2maxt回程度の判定処理でよい。変形例なお、本発明は上述の実施の形態に限定されるものではない。例えば、第1実施形態では、具体例として単一単語一致検索や部分集合判定検索を行う場合を例示したが、非特許文献12に開示されたようなその他の検索方式を用いる場合に本発明が適用されてもよい。また、上記の各実施形態では、内積述語暗号方式や階層的内積述語暗号方式で鍵カプセル化メカニズムKEMを構成する場合のタグ情報の生成方法や検証方法を例示したが、これは本発明を限定するものではない。例えば、式の第1暗号文...TとgTτυ1との組が否定タグ情報とされてもよい。肯定タグ情報についても同様な変形が可能である。上記の各実施形態では、否定タグ情報を用いたバッチ検索処理でsubの要素数が基準値以下にまで絞り込んでから、肯定タグ情報を用いた個別の検索処理を行った。しかし肯定タグ情報を用いた個別の検索処理を行うことなく、否定タグ情報のみを用いて検索が行われてもよい。この場合には肯定タグ情報や第2暗号化データベースの生成やそれに対応する検索クエリを生成する必要はない。上記実施形態で説明した階層的内積述語暗号方式の基本構成ではζ3の場合を例示した。しかし、ζがその他の1以上の整数であってもよい。マスタ秘密鍵MSKが含む基底ベクトルをζについて一般化するととなり、公開パラメータmpkが含む基底ベクトルをζについて一般化するととなる。前述した式をζについてそれぞれ一般化すると、例えば、以下のようになる。ただし、φω0,φωαは有限体Fqから選択された任意の元であり、Ωは0以上ζ以下の整数である。また、有限体Fqの元である定数constに対して以下を満たす。定数constの具体例は1Fである。ただし、υωは有限体Fqから選択された任意の元である。C2gTτυconstmesまた、上述した有限体上の元や演算が有限環上の元や演算に置換された構成でもよい。また、登録装置と検索装置とが一体であってもよいし、検索代理装置とストレージ装置とが一体であってもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。プログラム等上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"