(57)【特許請求の範囲】
【請求項１】
暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な第１暗号方式を用いた検索可能暗号システムであって、
予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する前記第１暗号方式の第１暗号文(T(indt,1),…,T(indt,N))(Nは正整数)を含む暗号化データベースを格納する暗号化データベース格納部と、
検索用キーワードに対応するベクトルに対応する前記第１暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆{1,…,maxt}についての第１暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できるかを判定するバッチ検索部と、
を有する検索可能暗号システム。
【請求項２】
請求項１の検索可能暗号システムであって、
前記inds∈sub⊆{1,…,maxt}についての前記第１暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できないと判定された場合に、subの真部分集合を新たなsubとした前記バッチ検索部の処理を再び実行させる制御部をさらに有する検索可能暗号システム。
【請求項３】
請求項１又は２の検索可能暗号システムであって、
前記検索対象情報TAR(indt)に対応するキーワードに対して設定されるベクトルに対応する前記第１暗号方式の第２暗号文(LT(indt,1),…,LT(indt,N))を含む第２暗号化データベースを格納する第２暗号化データベース格納部と、
前記inds∈sub⊆{1,…,maxt}についての前記第１暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できないと判定された場合に、第２検索クエリを復号鍵として用い、第２暗号文(LT(inds,1),…,LT(inds,N))（inds∈sub）が正しく復号できるかを判定する検索部をさらに有する検索可能暗号システム。
【請求項４】
請求項３の検索可能暗号システムであって、
前記検索対象情報TAR(indt)に対応するキーワードに対して設定されるベクトルと特定のベクトルとが特定の論理式の真理値を偽にする関係にあるとき、前記補集合CSET(indt)に対して設定されるベクトルと当該特定のベクトルとは当該特定の論理式の真理値を真にする関係にある、検索可能暗号システム。
【請求項５】
請求項１から４の何れかの検索可能暗号システムであって、
前記第１暗号文(T(inds,1),…,T(inds,N))の合成値が(BT(1),…,BT(N))であり、BT(indN)(indN=1,…,N)が
【数３６】
0005400809.tif 000039
である、検索可能暗号システム。
【請求項６】
請求項１から５の何れかの検索可能暗号システムであって、
前記第１暗号方式は、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0であるときに当該暗号文が当該復号鍵で復号可能な方式である、検索可能暗号システム。
【請求項７】
暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な第１暗号方式を用いた検索可能暗号方式のストレージ装置であって、
予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する前記第１暗号方式の第１暗号文(T(indt,1),…,T(indt,N))(Nは正整数)を含む暗号化データベースを格納する暗号化データベース格納部を有するストレージ装置。
【請求項８】
暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な第１暗号方式を用いた検索可能暗号方式のストレージ装置を検索する装置であって、
検索用キーワードに対応するベクトルに対応する前記第１暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆{1,…,maxt, maxt≧2}についての第１暗号文(T(inds,1),…,T(inds,N))(Nは正整数)の合成値が正しく復号できるかを判定する装置。
【請求項９】
暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な第１暗号方式を用いた検索可能暗号方法であって、
予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する前記第１暗号方式の第１暗号文(T(indt,1),…,T(indt,N))(Nは正整数)を含む暗号化データベースが暗号化データベース格納部に格納されており、
バッチ検索部で、検索用キーワードに対応するベクトルに対応する前記第１暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆{1,…,maxt}についての第１暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できるかを判定する検索可能暗号方法。
【請求項１０】
請求項９の検索可能暗号方法の処理をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化されたデータベースの検索が可能な検索可能暗号技術に関する。
【背景技術】
【０００２】
検索対象文書からあらかじめキーワードを抽出し、それらのキーワードの暗号文を含むデータベースを構成し、各キーワードが暗号化されたままの状態で部分一致検索を行って検索結果を得る検索可能暗号方式が非特許文献１，２に開示されている。非特許文献１，２では、暗号化条件や復号条件を述語論理で記述することが可能な述語暗号方式（例えば、非特許文献３から６参照）を利用して検索可能暗号方式を実現している。すなわち、非特許文献１，２では、検索対象文書が含む各キーワードの暗号文をタグ情報としてデータベースに格納しておき、検索するキーワードが述語論理を満たす場合にタグ情報が復号できる秘密鍵を検索クエリとして生成し、この検索クエリで各タグ情報を復号できるかどうかでヒットしたかどうかを判定している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】R. Yoshida, A. Nagai, and T. Kobayashi, “Hierarchical Predicate Encryption with Keyword Search in Multi-user Setting,” In Computer Security Symposium, 2010.
【非特許文献２】R. Yoshida, S. Oda, and T. Kobayashi., "Public-key encryption with partial matching keyword search," In Symp. on Cryptography and Information Security, 2010.
【非特許文献３】J. Katz, A. Sahai, and B. Waters., "Predicate encryption supporting disjunctions, polynomial equations, and inner products," In EUROCRYPT, pp. 146-162, 2008.
【非特許文献４】A. B. Lewko, T. Okamoto, A. Sahai, K. Takashima, and B. Waters., "Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption," In EUROCRYPT, pp. 62-91, 2010.
【非特許文献５】T. Okamoto and K. Takashima., "Hierarchical predicate encryption for inner-products," In ASIACRYPT, pp. 214-231, 2009.
【非特許文献６】E. Shi and B. Waters, “Delegating Capabilities in Predicate Encryption Systems,” In ICALP (2), pp. 560-578, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の方式では、タグ情報ごとに検索クエリで復号可能か否かを判定するため、検索を行うための演算回数が多い。
【０００５】
本発明はこのような点に鑑みてなされたものであり、従来よりも少ない演算回数で検索を行うことが可能な検索可能暗号技術を提供する。
【課題を解決するための手段】
【０００６】
予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する第１暗号方式の第１暗号文(T(indt,1),…,T(indt,N))(Nは正整数)を含む暗号化データベースを格納しておく。検索用キーワードに対応するベクトルに対応する第１暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆{1,…,maxt}についての第１暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できるかを判定する。なお第１暗号方式は、暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な方式である。
【発明の効果】
【０００７】
本発明では、検索クエリを用い、キーワードの全体集合から検索対象情報TAR(indt)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する第１暗号文(T(indt,1),…,T(indt,N))をinds∈sub⊆{1,…,maxt}についてまとめて検証することになる。これは、inds∈subの各検索対象情報TAR(inds)が検索用キーワードにヒットしないかをまとめて検証することを意味する。よって、暗号化データベースが含む検索対象情報TAR(indt)に対応するキーワードの多くが検索用キーワードにヒットしないと仮定すると、従来よりも少ない演算回数で検索を行うことができるといえる。
【図面の簡単な説明】
【０００８】
【図１】図１は、第１実施形態の検索可能暗号システムの全体構成を例示するための図である。
【図２】図２Ａは、第１実施形態の管理装置の機能構成を例示するための図である。図２Ｂは、第１実施形態の登録装置の機能構成を例示するための図である。
【図３】図３は、第１実施形態のストレージ装置の機能構成を例示するための図である。
【図４】図４は、第１実施形態の暗号化データベース格納部に格納される暗号化データベース（否定タグ情報含む）のデータ構成を例示するための図である。
【図５】図５は、第１実施形態の暗号化データベース格納部に格納される暗号化データベース（肯定タグ情報含む）のデータ構成を例示するための図である。
【図６】図６は、第１実施形態の検索装置の機能構成を例示するための図である。
【図７】図７は、第１実施形態のデータベース登録の処理を例示するためのフローチャートである。
【図８】図８は、第１実施形態の検索処理を例示するためのフローチャートである。
【図９】図９は、第１実施形態の検索処理を例示するためのフローチャートである。
【図１０】図１０は、第１実施形態の検索処理を例示するための図である。
【図１１】図１１は、第２実施形態の検索可能暗号システムの全体構成を例示するための図である。
【図１２】図１２Ａ及びＢは、第２実施形態の管理装置の機能構成を例示するための図である。
【図１３】図１３は、第２実施形態の登録装置の機能構成を例示するための図である。
【図１４】図１４Ａは、第２実施形態の検索代行装置の機能構成を例示するための図である。図１４Ｂは、第２実施形態のストレージ装置の機能構成を例示するための図である。
【図１５】図１５Ａは、第２実施形態の暗号化データベース格納部に格納される暗号化データベース（否定タグ情報含む）のデータ構成を例示するための図である。図１５Ｂは、第２実施形態の暗号化データベース格納部に格納される暗号化データベース（肯定タグ情報含む）のデータ構成を例示するための図である。
【図１６】図１６は、一括方式によって鍵情報kM*を生成する処理を例示するためのフローチャートである。
【図１７】図１７は、委託方式によって鍵情報kM*を生成する処理を例示するためのフローチャートである。
【図１８】図１８は、委託方式によって鍵情報kM*を生成する処理を例示するためのフローチャートである。
【図１９】図１９は、データベース登録の処理を例示するためのフローチャートである。
【図２０】図２０は、データベース登録の処理を例示するためのフローチャートである。
【図２１】図２１は、検索処理を例示するためのフローチャートである。
【発明を実施するための形態】
【０００９】
以下、図面を参照して本発明の実施形態を説明する。
【００１０】
〔概要〕
以下に説明する各実施形態では、暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な暗号方式（第１暗号方式）を用いて検索可能暗号方式を構成する。このような暗号方式の例は、非特許文献３から６などに開示されている内積述語暗号方式や階層的内積述語暗号方式などの述語暗号方式などである。第１暗号方式が述語暗号方式の例では、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0であるときに当該暗号文が当該復号鍵で復号できる。本発明で利用する第１暗号方式は非特許文献３から６に開示された方式に限定されず、これらと同様な性質を有するどのような方式が用いられてもよい。
【００１１】
各実施形態では、予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する第１暗号方式の第１暗号文(T(indt,1),…,T(indt,N))(Nは正整数)を含む暗号化データベースを格納しておく。なお「補集合CSET(indt)」は、キーワードの全体集合から検索対象情報TAR(indt)に対応するすべてのキーワードを除いた補集合CSET(indt)や、キーワードの全体集合から検索対象情報TAR(indt)に対応する一部のキーワードを除いた補集合CSET(indt)や、キーワードの全体集合から検索対象情報TAR(indt)に対応する一部のキーワードを除いた補集合の集合である。補集合CSET(indt)の定め方は検索方式（検索条件）に依存する。なお、キーワードとは文字や記号、又は、文字や記号からなる列（文字列、記号列、文字・記号列など）を意味する。単語のように特定の意味をなすものだけではなく、例えばアルファベットのように特定の意味を成さないものもキーワードである。例えば、キーワードの全体集合がアルファベットの集合{A,B,C,…X,Y,Z}であり、検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードが{A,B,C}である場合、補集合CSET(indt)は、{D,E,F,…X,Y,Z}となる（詳細は後述）。
【００１２】
暗号化データベースの検索処理は、検索用キーワードに対応するベクトルに対応する第１暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆{1,…,maxt}についての第１暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できるかを判定する処理を含む。
【００１３】
ここで、暗号化データベースが含む第１暗号文(T(indt,1),…,T(indt,N))は、予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する第１暗号方式の暗号文である。また、検索クエリは検索用キーワードに対応するベクトルに対応する第１暗号方式の復号鍵である。そのため、検索用キーワードが検索対象情報TAR(indt)に対応するキーワードにヒットしないときに、検索クエリで第１暗号文(T(indt,1),…,T(indt,N))が復号できる。このような復号が可能か否かの判定がinds∈sub⊆{1,…,maxt}についてまとめて実行される（バッチ検索処理）。これはinds∈subの各検索対象情報TAR(inds)が検索キーワードにヒットしないかをまとめて検証していることになる。これにより、少ない演算回数で検索用キーワードにヒットしない検索対象情報TAR(inds)を特定でき、検索対象を絞り込むことができる。その結果、暗号化データベースが含む検索対象情報TAR(indt)に対応するキーワードの多くが検索用キーワードにヒットしないと仮定すると、この方法では従来よりも少ない演算回数で検索を行うことができることになる。
【００１４】
また各実施形態の例では、inds∈sub⊆{1,…,maxt}についての前記第１暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できないと判定された場合に、subの真部分集合を新たなsubとした上述のバッチ検索処理を再び実行させる。このような繰り返しにより、従来よりも少ない演算回数で検索対象を絞り込むことができる。
【００１５】
また１回のバッチ検証処理の演算コストが１回の検索処理よりも大きい場合は、検索対象情報TAR(indt)ごとの検索処理に切り替えてコストを低減する手法も考えられる。この手法を実現する各実施形態の例では、さらに、検索対象情報TAR(indt)に対応するキーワードに対して設定されるベクトルに対応する第１暗号方式の第２暗号文(LT(indt,1),…,LT(indt,N))を含む第２暗号化データベースを格納しておく。subの要素数が基準値以下であり、かつ、inds∈sub⊆{1,…,maxt}についての第１暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できないと判定された場合に、検索クエリを復号鍵として用い、第２暗号文(LT(inds,1),…,LT(inds,N))（inds∈sub）が正しく復号できるかを判定する。
【００１６】
ここで、第２暗号文(LT(indt,1),…,LT(indt,N))は、検索対象情報TAR(indt)に対応するキーワードに対して設定されるベクトルに対応する第１暗号方式の暗号文である。また、検索クエリは検索用キーワードに対応するベクトルに対応する第１暗号方式の復号鍵である。そのため、検索用キーワードが検索対象情報TAR(indt)に対応するキーワードにヒットするときに、検索クエリで第２暗号文(LT(indt,1),…,LT(indt,N))が正しく復号できる。これは検索対象情報TAR(indt)が絞り込まれてから、当該検索対象情報TAR(indt)が検索クエリにヒットするかを検索対象情報TAR(indt)ごとに個別に検証していることになる。一般に、複数のinds∈subの検索対象情報TAR(inds)に対する１つのバッチ検索処理の演算コストは、検索対象情報TAR(indt)ごとの１つの検索処理の演算コストよりも大きい。そのため、検索対象情報TAR(indt)が絞り込まれ、例えば１回のバッチ検証処理の演算コストが１回の検索処理よりも大きい場合は、検索対象情報TAR(indt)ごとの検索処理に切り替えるほうが全体としての演算コストを低減できる。上述の「基準値」の例は１や２以上の整数定数である。また、subをDIV個に分割して得られる各真部分集合を新たなsubとしてバッチ検索部の処理を繰り返す場合には、DIVを上述の「基準値」としてもよい。また、subの要素数が基準値以下であるという条件の代わりに、集合{1,…,maxt}の分割回数が第２基準値以上であるという条件としてもよい。或いは、subの要素数が基準値以下であるという条件の代わりに、subの要素数が基準値以下であり、かつ、集合{1,…,maxt}の分割回数が第２基準値以上であるという条件としてもよい。
【００１７】
なお、上述の検索対象情報TAR(indt)に対応するキーワードに対して設定されるベクトルと特定のベクトルとが特定の論理式の真理値を偽にする関係にあるとき、上述の補集合CSET(indt)に対して設定されるベクトルと当該特定のベクトルとは当該特定の論理式の真理値を真にする関係にある。第１暗号方式が述語暗号方式の例では、上述の検索対象情報TAR(indt)に対応するキーワードに対して設定されるベクトルと特定のベクトルとの内積が0以外のときに、上述の補集合CSET(indt)に対して設定されるベクトルと当該特定のベクトルとの内積が0となる。
【００１８】
また、上述の第１暗号文(T(inds,1),…,T(inds,N))の合成値は、例えば(BT(1),…,BT(N))であり、これらのBT(indN)(indN=1,…,N)は例えば
【００１９】
【数１】
0005400809.tif 000002
である。
【００２０】
〔定義〕
次に、以下の各実施形態で使用される用語や記号を定義する。
【００２１】
行列：「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
【００２２】
(・)T：(・)Tは・の転置行列を表す。
(・)-1：(・)-1は・の逆行列を表す。
∧：∧は論理積を表す。
∨：∨は論理和を表す。
Ｚ：Ｚは整数集合を表す。
sec：secはセキュリティパラメータ（sec∈Z, sec>0）を表す。
Fq：Fqは位数qの有限体を表す。位数qは１以上の整数であり、例えば、素数や素数のべき乗値を位数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の代数閉包における１のｐ乗根からなる有限集合である。
【００２４】
なお、本形態では、巡回群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以上の整数を表す。ζの一例は２又は３である。
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に写す非退化な双線形写像（bilinear map）を表す。双線形写像eは、巡回群G1のn+ζ個の元γβ(β=1,...,n+ζ)と巡回群G2のn+ζ個の元γβ*(β=1,...,n+ζ)とを入力とし、巡回群GTの１個の元を出力する。
e：G1n+ζ×G2n+ζ→GT          …(1)
双線形写像eは以下の性質を満たす。
【００２６】
［双線形性］すべてのΓ1∈G1n+ζ，Γ2∈G2n+ζ及びν，κ∈Fqについて以下の関係を満たす。
e(ν・Γ1,κ・Γ2)=e(Γ1,Γ2)ν・κ          …(2)
【００２７】
［非退化性］すべてのΓ1∈G1n+ζ，Γ2∈G2n+ζを巡回群GTの単位元に写すものではない。
【００２８】
［計算可能性］あらゆる
Γ1∈G1n+ζ，Γ2∈G2n+ζ          …(3)
についてe(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
【００２９】
本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を計算するための関数
Pair:G1×G2→GT          …(4)
を用いて双線形写像eを構成する。本形態の双線形写像eは、巡回群G1のn+ζ個の元γβ (β=1,...,n+ζ)からなるn+ζ次元ベクトル(γ1,...,γn+ζ)と、巡回群G2のn+ζ個の元γβ*(β=1,...,n+ζ)からなるn+ζ次元ベクトル(γ1*,...,γn+ζ*)との入力に対し、巡回群GTの１個の元
e=Πβ=1n+ζPair(γβ, γβ*)          …(5)
を出力する。
【００３０】
なお、双線形写像Pairは、巡回群G1の１個の元と巡回群G2の１個の元との組を入力とし、巡回群GTの１個の元を出力するものであり、以下の性質を満たす。
【００３１】
［双線形性］すべてのΩ1∈G1，Ω2∈G2及びν，κ∈Fqについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω1,Ω2)ν・κ          …(6)
【００３２】
［非退化性］すべての
Ω1∈G1，Ω2∈G2          …(7)
を巡回群GTの単位元に写すものではない。
【００３３】
［計算可能性］あらゆるΩ1∈G1，Ω2∈G2についてPair(Ω1,Ω2)を効率的に計算するアルゴリズムが存在する。
【００３４】
なお、双線形写像Pairの具体例は、WeilペアリングやTateペアリングなどのペアリングである（例えば、参考文献１「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」等参照）。
【００３５】
ai(i=1,...,n+ζ)：aiは巡回群G1のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ1・g1∈G1をi次元目の要素とし、残りのn個の要素を巡回群G1の単位元（加法的に「0」と表現）とするn+ζ次元の基底ベクトルである。この場合、n+ζ次元の基底ベクトルai(i=1,...,n+ζ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
【００３６】
a1=(κ1・g1,0,0,...,0)
a2=(0,κ1・g1,0,...,0)           …(8)
...
an+ζ=(0,0,0,...,κ1・g1)
【００３７】
ここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ1=1Fである。基底ベクトルaiは直交基底であり、巡回群G1のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルai(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルaiはベクトル空間Vを張る。
【００３８】
ai*(i=1,...,n+ζ)：巡回群G2のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。基底ベクトルai*の一例は、κ2・g2∈G2をi次元目の要素とし、残りのn個の要素を巡回群G2の単位元（加法的に「0」と表現）とするn+ζ次元の基底ベクトルである。この場合、基底ベクトルai*(i=1,...,n+ζ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
【００３９】
a1*=(κ2・g2,0,0,...,0)
a2*=(0,κ2・g2,0,...,0)            …(9)
...
an+ζ*=(0,0,0,...,κ2・g2)
【００４０】
ここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ2=1Fである。基底ベクトルai*は直交基底であり、巡回群G2のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルai*(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルai*はベクトル空間V*を張る。
【００４１】
なお、基底ベクトルaiと基底ベクトルai*とは、0Fを除く有限体Fqの元τ=κ1・κ2について
e(ai, aj*)=gTτ・δ(i,j)           …(10)
を満たす。すなわち、i=jの場合には、式(5)(6)の関係から、
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τ
を満たす。一方、i≠jの場合には、e(ai, aj*)=Πi=1n+ζ Pair(ai, aj*)の右辺は、Pair(κ1・g1,κ2・g2)を含まず、Pair(κ1・g1,0)と Pair(0,κ2・g2)とPair(0,0)との積になる。さらに、式(6)の関係からPair(g1, 0)=Pair(0, g2)=Pair(g1, g2)0を満たす。そのため、i≠jの場合には、
e(ai, aj*)=e(g1, g2)0=gT0
を満たす。
【００４２】
特に、τ=κ1・κ2=1Fである場合（例えば、κ1=κ2=1Fの場合）、
e(ai, aj*)=gTδ(i,j)          …(11)
を満たす。ここで、gT0=1は巡回群GTの単位元であり、gT1=gTは巡回群GTの生成元である。この場合、基底ベクトルaiと基底ベクトルai*とは双対正規直交基底であり、ベクトル空間Vとベクトル空間V*とは、双線形写像を構成可能な双対ベクトル空間〔双対ペアリングベクトル空間（DPVS:Dual Paring Vector space)〕である。
【００４３】
A：基底ベクトルai(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルai(i=1,...,n+ζ)が式(8)によって表現される場合、行列Aは、
【００４４】
【数２】
0005400809.tif 000003
となる。
【００４５】
A*：基底ベクトルai*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルai*(i=1,...,n+ζ)が式(9)によって表現される場合、行列A*は、
【００４６】
【数３】
0005400809.tif 000004
となる。
【００４７】
X：有限体Fqの元を要素とするn+ζ行n+ζ列の行列を表す。基底ベクトルaiの座標変換に用いられる。行列Ｘのi行j列(i=1,...,n+ζ,j=1,...,n+ζ)の要素をχi,j∈Fqとすると、行列Xは、
【００４８】
【数４】
0005400809.tif 000005
となる。なお、行列Ｘの各要素χi,jを変換係数と呼ぶ。
【００４９】
X *：X *は行列Xの逆行列の転置行列Ｘ*=(Ｘ-1)Tを表す。基底ベクトルai*の座標変換に用いられる。行列X*のi行j列の要素をχi,j*∈Fqとすると、行列Ｘ*は、
【００５０】
【数５】
0005400809.tif 000006
となる。なお、行列Ｘ*の各要素χi,j*を変換係数と呼ぶ。
【００５１】
この場合、n+ζ行n+ζ列の単位行列をIとするとＸ・(Ｘ*)T=Ｉを満たす。すなわち、単位行列
【００５２】
【数６】
0005400809.tif 000007
に対し、
【００５３】
【数７】
0005400809.tif 000008
【００５４】
を満たす。ここで、n+ζ次元ベクトル
χi→=(χi,1,...,χi,n+ζ)            …(18)
χj→*=(χj,1*,...,χj,n+ζ*)          …(19)
を定義する。すると、式(17)の関係から、n+ζ次元ベクトルχi→とχj→*との内積は、
χi→・χj→*=δ(i,j)          …(20)
となる。
【００５５】
bi：biは巡回群G1のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。行列Xを用いて基底ベクトルai(i=1,...,n+ζ)を座標変換することで得られる。具体的には、基底ベクトルbiは、
bi=Σj=1n+ζχi,j・aj          …(21)
の演算によって得られる。例えば、基底ベクトルaj(j=1,...,n+ζ)が式(8)によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。
【００５６】
bi=(χi,1・κ1・g1 ,χi,2・κ1・g1 ,...,χi,n+ζ・κ1・g1)    …(22)
巡回群G1のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルbi(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。
【００５７】
bi*：bi*は巡回群G2のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。行列X*を用いて基底ベクトルai*(i=1,...,n+ζ)を座標変換することで得られる。具体的には、基底ベクトルbi*は、
bi*=Σj=1n+ζχi,j*・aj*          …(23)
の演算によって得られる。例えば、基底ベクトルaj*(j=1,...,n+ζ)が式(9)によって表現される場合、基底ベクトルbi*の各要素をそれぞれ列挙して表現すると、以下のようになる。
【００５８】
bi*=(χi,1*・κ2・g2 ,χi,2*・κ2・g2 ,...,χi,n+ζ*・κ2・g2)  …(24)
となる。巡回群G2のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルbi*(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルbi*は前述のベクトル空間V*を張る。
【００５９】
なお、基底ベクトルbiと基底ベクトルbi*とは、0Fを除く有限体Fqの元τ=κ1・κ2について
e(bi, bj*)=gTτ・δ(i,j)          …(25)
を満たす。すなわち、式(5)(20)(22)(24)の関係から、
【００６０】
【数８】
0005400809.tif 000009
【００６１】
を満たす。特に、τ=κ1・κ2=1Fである場合（例えば、κ1=κ2=1Fの場合）、
e(bi, bj*)=gTδ(i,j)          …(26)
を満たす。この場合、基底ベクトルbiと基底ベクトルbi*とは、双対ペアリングベクトル空間（ベクトル空間Vとベクトル空間V*）の双対正規直交基底である。
【００６２】
なお、式(25)の関係を満たすのであれば、式(8)(9)で例示したもの以外の基底ベクトルai及びai*や、式(21)(23)で例示したもの以外の基底ベクトルbi及びbi*を用いてもよい。
【００６３】
B：Bは基底ベクトルbi(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列。B=X・Aを満たす。例えば、基底ベクトルbiが式(22)によって表現される場合、行列Bは、
【００６４】
【数９】
0005400809.tif 000010
となる。
【００６５】
B*：B*は基底ベクトルbi*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。B*=X*・A*を満たす。例えば、基底ベクトルbi*(i=1,...,n+ζ)が式(24)によって表現される場合、行列B*は、
【００６６】
【数１０】
0005400809.tif 000011
【００６７】
となる。
【００６８】
〔内積述語暗号方式〕
次に、内積述語暗号方式について説明する。内積述語暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。内積述語暗号方式では、内積が0となることと論理式の真理値が真となることとが等価である。
【００６９】
［内積と論理式の真理値との関係］
内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。
【００７０】
まず、「x1がη1である」という命題１と「x2がη2である」という命題２との論理和 (x1=η1)∨(x2=η2)を
(x1-η1)・(x2-η2)          …(29)
という多項式で表現する。すると、各真理値と式(29)の関数値との関係は以下のようになる。
【００７１】
【表１】
0005400809.tif 000012
[表1]から分かるように、論理和(x1=η1)∨(x2=η2)が真である場合、式(29)の関数値は0になり、論理和(x1=η1)∨(x2=η2)が偽である場合、式(29)の関数値は0以外の値となる。すなわち、論理和(x1=η1)∨(x2=η2)が真であることと、式(29)の関数値が0となることとは等価である。よって、論理和は式(29)で表現できる。
【００７２】
また、「x1がη1である」という命題１と「x2がη2である」という命題２との論理積 (x1=η1)∧(x2=η2)を
ι1・(x1-η1)+ι2・(x2-η2)          …(30)
という多項式で表現する。ただし、ι1及びι2は乱数である。すると、真理値と式(30)の関数値とは以下の関係となる。
【００７３】
【表２】
0005400809.tif 000013
[表２]から分かるように、論理積 (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・{(x1-η1)・(x2-η2)}+ι2・(x3-η3)+ι3・(x4-η4)    …(31)
で表現できる。以下、このように論理式を表現する多項式のことを述語多項式と呼ぶ。
【００７５】
述語多項式は２つのベクトルの内積で表現できる。すなわち、述語多項式は、各項の不定元成分と１とを各要素とするベクトルと、各項の係数成分を各要素とするベクトルとの内積に等しい。例えば、式(31)の述語多項式は、各項の不定元成分と１を各要素とするベクトル(x1・x2, x1, x2, x3, x4, 1)と、各項の係数成分を各要素とするベクトル(ι1, -ι1・η2, -ι1・η1, ι2, -ι2・η3+ι3, ι1・η1・η2-ι3・η4)との内積に等しい。
【００７６】
そのため、述語多項式の値が0であるか否かと、述語多項式の各項の不定元成分と１とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。言い換えると、論理式の真理値が真であるか否かと、当該論理式を示す述語多項式の各項の不定元成分と１とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。
【００７７】
内積述語暗号方式では、上述の各項の不定元成分と１を各要素とするベクトル及び各項の係数成分を各要素とするベクトルの何れか一方のベクトルが暗号文に埋め込まれ、他方のベクトルが復号鍵に埋め込まれる。以下では、暗号文に埋め込まれるベクトルをw→=(w1,...,wn)とし、復号鍵に埋め込まれるベクトルをv→=(v1,...,vn)とする。
【００７８】
［内積述語暗号方式の基本構成］
内積述語暗号方式で鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する例を示す。この構成はSetup，GenKey，Enc，Decを含む。
【００７９】
《Setup：セットアップ》
−入力：セキュリティパラメータsec
−出力：マスタ鍵情報MSK，公開パラメータPK
Setupの一例では、まず、セキュリティパラメータsecをnとして、n+ζ次元の基底ベクトルai(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列Aと、基底ベクトルai*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列A*と、座標変換のためのn+ζ行n+ζ列の行列X，X*とが選択される。次に、式(21)に従って座標変換されたn+ζ次元の基底ベクトルbi(i=1,...,n+ζ)が算出され、式(23)に従って座標変換されたn+ζ次元の基底ベクトルbi*(i=1,...,n+ζ)が算出される。そして、基底ベクトルbi*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列B*がマスタ鍵情報MSKとして出力され、ベクトル空間V, V*、基底ベクトルbi(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列B、セキュリティパラメータsec、有限体Fq、楕円曲線E、巡回群G1, G2, GT、生成元g1, g2, gT、双線形写像eなどが公開パラメータPKとして出力される。
【００８０】
《GenKey：復号鍵生成》
−入力：マスタ鍵情報MSK，ベクトルv→
−出力：ベクトルv→に対応する復号鍵D*
GenKeyの一例では、まず、有限体Fqから元σ,σι-n∈Fqが選択される。そして、マスタ鍵情報MSKである行列B*を用い、ベクトルv→に対応する復号鍵
D*=σ・(Σμ=1nvμ・bμ*)+Σι=n+1n+ζ'σι-n・bι*∈G2n+ζ'    …(32)
が生成され、出力される。ただし、σ,σι-nは乱数などの変数や定数などであり、ζ'≦ζである（例えばζ=3, ζ'=2）。またΣι=n+1n+ζ'σι-nはシステムで共有される定数値とされる。以下では
Σι=n+1n+ζ'σι-n=1F          …(33)
とされた例を説明する。これは本発明を限定しない。
【００８１】
《Enc：暗号化》
−入力：公開パラメータPK，ベクトルw→，平文mes
−出力：暗号文(C1，C2)
Encの一例では、行列Bなどの公開パラメータPKと、有限体Fqの元である乱数υ0,υ1,...,υζと、ベクトルw→とを用い、暗号文
C1=υ0・(Σμ=1nwμ・bμ)+Σμ=n+1n+ζυμ-ｎ・bμ∈G1n+ζ    …(34)
が生成される。ただし、
υ1=...=υζ'          …(35)
を満たす（例えばζ'=2のときにはυ1=υ2）。また、gTτ・υ1を共通鍵Kとし、所定の共通鍵暗号方式（第２暗号方式）に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、
C2=gTτ・υ1・mes          …(36)
である。添え字のυ1はυ1を意味する。前述のように定数τの一例はτ=1Fである。生成された暗号文(C1，C2)は出力される。
【００８２】
《Dec：復号》
−入力：ベクトルv→に対応する復号鍵D*，暗号文(C1，C2)
−出力：復号値mes'
Decの一例では、まず、暗号文C1と復号鍵D*とが式(1)の双線形写像eに入力され、その演算結果を共通鍵K=e(C1,D*)とし、以下のように復号値mes'が求められる。
【００８３】
mes'=C2/e(C1,D*)∈GT          …(37)
ここで、式(2)(25)(33)(35)の性質から、
【００８４】
【数１１】
0005400809.tif 000014
【００８５】
を満たす。
【００８６】
内積w→・v→=0であれば、式(38)は、
【００８７】
【数１２】
0005400809.tif 000015
を満たす。式(36)(37)(39)から、内積w→・v→=0であればmes'=mesとなり、正しく復号されることがわかる。
【００８８】
［階層的内積述語暗号方式の基本構成］
階層的内積述語暗号方式は内積述語暗号方式の一種であり、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる。さらに階層的内積述語暗号方式では階層的な処理によって復号鍵を生成できる。すなわち、階層的内積述語暗号方式では属性が階層化され、各階層までの属性に対応する鍵情報が存在するとともに、上位の階層に対応する鍵情報を用いて下位の階層に対応する鍵情報を生成できる。そして、このような階層的な処理によって生成された最終的な鍵情報が復号鍵となる。以下に階層的内積述語暗号方式の基本構成を例示する。以下では、階層的内積述語暗号方式を用いて鍵カプセル化メカニズムKEMを構成する場合の基本構成を例示する。ただし、これは本発明を限定するものではない。
【００８９】
《前提》
深さdの属性空間の階層フォーマットを以下の式によって定義する。ただし、dは1以上n以下の整数である。
【００９０】
ξ→=(n,d;ξ1,...,ξd) (0=ξ0<ξ1<...<ξd=n)          …(40)
有限体Fqの元を要素とするξω-ξω-1(ω=1,...,d)次元のベクトル（零ベクトルを除く）を階層ωに対応するベクトル
【００９１】
【数１３】
0005400809.tif 000016
とし、階層1から階層m（m≦d）までに対応するベクトルを(w1→,...,wm→)とする。有限体Fqの元を要素とするξω-ξω-1次元（ω=1,...,d）のベクトル（零ベクトルを除く）を階層ωに対応するベクトル
【００９２】
【数１４】
0005400809.tif 000017
とし、階層1から階層mまでに対応するベクトルを(v1→,...,vm→)とする。
【００９３】
《Setup：セットアップ》
−入力：セキュリティパラメータsec
−出力：階層フォーマットξ→，マスタ秘密鍵MSK，公開パラメータmpk
Setupの一例では、セキュリティパラメータsecの単調増加関数値をnとし、階層フォーマットξ→=(n,d;ξ1,...,ξd)が定められる。また、この例ではζ=3とし、n+3次元の基底ベクトルai(i=1,...,n+3)を要素とするn+3行n+3列の行列Aと、基底ベクトルai*(i=1,...,n+3)を要素とするn+3行n+3列の行列A*と、座標変換のためのn+3行n+3列の行列X，X*とが選択される。次に、式(21)に従って座標変換されたn+3次元の基底ベクトルbi(i=1,...,n+3)が算出され、式(23)に従って座標変換されたn+3次元の基底ベクトルbi*(i=1,...,n+3)が算出される。
【００９４】
この例では、基底ベクトル(b1*,...,bn*,bn+1*,bn+2*,bn+3*)と行列Xとがマスタ秘密鍵MSKとして出力され、基底ベクトル(b1,...,bn,bn+1+bn+2,bn+3)、ベクトル空間V, V*、セキュリティパラメータsec、有限体Fq、楕円曲線E、巡回群G1, G2,GT、生成元g1, g2, gT、双線形写像eなどが公開パラメータmpkとして出力される。
【００９５】
《GenKey：鍵情報生成》
−入力：マスタ秘密鍵MSK，公開パラメータmpk，ベクトル(v1→,...,vm→)
−出力：ベクトル(v1→,...,vm→)に対応する鍵情報km*
GenKeyの一例では、まず、有限体Fqから元σα，ω，Ψ，Φα∈Fq (α=0,...,m+1,ξm+1,...,n; ω=1,...,m)が任意に選択される。この例では、これらとマスタ秘密鍵MSKである基底ベクトル(b1*,...,bn*,bn+1*,bn+2*,bn+3*)とベクトル(v1→,...,vm→)とを用い、ベクトル(v1→,...,vm→)に対応する鍵情報
【００９６】
【数１５】
0005400809.tif 000018
が生成されて出力される。ただし、
【００９７】
【数１６】
0005400809.tif 000019
である。
【００９８】
《Delegate(m')：鍵情報生成委譲》
−入力：公開パラメータmpk，鍵情報km'*，ベクトルvm'+1→
−出力：ベクトル(v1→,...,vm'+1→)に対応する鍵情報km'+1*
階層的内積述語暗号方式では、マスタ秘密鍵MSKを用いることなく、公開パラメータmpk，鍵情報km'*，ベクトルvm'+1→からベクトル(v1→,...,vm'+1→)に対応する鍵情報km'+1*を生成できる。ただし、m'=1,...,d-1である。
【００９９】
Delegate(m')の一例では、有限体Fqから元σ'α，ω，Ψ'，Φ'α∈Fq (α=0,...,m'+2,ξm'+1+1,...,n; ω=1,...,m'+1)が任意に選択される。この例では、これらと鍵情報km'*とベクトルvm'+1→と用い、ベクトル(v1→,...,vm'+1→)に対応する鍵情報
【０１００】
【数１７】
0005400809.tif 000020
が生成されて出力される。ただし、
【０１０１】
【数１８】
0005400809.tif 000021
である。
【０１０２】
《Enc：暗号化》
−入力：公開パラメータmpk，ベクトル(w1→,...,wm→)，平文mes
−出力：暗号文(C1，C2)
Encの一例では、まず、有限体Fqから任意の元υ1,...,υd,υn+3,υが選択される。そして、これらと公開パラメータmpkとベクトル(w1→,...,wm→)とを用い、暗号文
【０１０３】
【数１９】
0005400809.tif 000022
が生成される。また、gTτ・υを共通鍵Kとし、所定の共通鍵暗号方式（第２暗号方式）に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、
C2=gTτ・υ・mes          …(52)
である。なお、前述のように定数τの一例はτ=1Fである。その後、以上のように生成された暗号文(C1，C2)が出力される。
【０１０４】
《Dec：復号》
−入力：公開パラメータmpk，ベクトル(v1→,...,vm→)に対応する鍵情報km*，暗号文(C1，C2)
−出力：復号値mes'
Decの一例では、
mes'=C2/e(C1,km,0*)          …(53)
によって復号値mes'を計算する。
【０１０５】
暗号文C1と鍵情報km*のkm,0*とが式(1)の双線形写像e（この例ではζ=3）に入力されると、式(2)(25)の性質から、
【０１０６】
【数２０】
0005400809.tif 000023
を満たす。なお、σω及びσは有限体Fqの元である。Delegate(m')がなされることなく鍵情報km*が生成された場合にはσω=σ0，ωである。Delegate(m')が１回以上なされた場合には、GenKeyに使用された有限体Fqの元σα，ωやDelegate(m')時に使用された有限体Fqの元σ'α，ωやΦ'αに応じてσωの値が定まる。ここで、すべてのω=1,...,mについて内積vω→・wω→=0Fであれば、式(54)は、
e(C1,km,0*)=gTτ・υ          …(55)
と変形できる。式(52)(53)(55)より、すべてのω=1,...,mについて内積vω→・wω→=0Fである場合にmes'=mesとなり、正しく復号がなされることがわかる。
【０１０７】
〔第１実施形態〕
次に、本発明の第１実施形態を説明する。本形態では第１暗号方式として内積述語暗号方式を用いる。
【０１０８】
＜構成＞
図１に例示するように、本形態の検索可能暗号システム１は、管理装置１１０と登録装置１２０−ｕ（u=1,...,U）とストレージ装置１４０と検索装置１５０−ｕ（u=1,...,U）とを有する。なお、Ｕは１以上の整数である。また、登録装置１２０−ｕ及び検索装置１５０−ｕは、検索可能暗号システム１を利用するｕ番目の登録ユーザが使用する装置である。また、各装置は他の装置へ情報を提供可能なように構成されている。装置間の情報提供はネットワークを通じて行われてもよいし、可搬型記録媒体を介して行われてもよい。
【０１０９】
［管理装置］
図２Ａに例示するように、管理装置１１０は、入力部１１１と出力部１１２とマスタ秘密鍵格納部１１３と制御部１１５と鍵情報生成部１１６ｂとを有する。管理装置１１０は、例えば、CPU(central processing unit),RAM(random-access memory),ROM(read-only memory)などを有する公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、管理装置１１０は、制御部１１５の制御のもと各処理を実行する。管理装置１１０での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【０１１０】
［登録装置］
図２Ｂに例示するように、登録装置１２０−ｕは、出力部１２２−ｕと登録キーワード格納部１２３ｂ−ｕと制御部１２５−ｕと乱数生成部１２６ｃ−ｕとベクトル設定部１２６ｅ−ｕと暗号化部１２６ｆ−ｕとタグ情報生成部１２６ｇ−ｕとを有する。登録装置１２０−ｕは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、登録装置１２０−ｕは、それぞれ、制御部１２５−ｕの制御のもと各処理を実行する。登録装置１２０−ｕでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【０１１１】
［ストレージ装置１４０］
図３に例示するように、ストレージ装置１４０は、入力部１４１と出力部１４２と暗号化データベース格納部１４３と制御部１４５と書込み部１４６とバッチ検索部１４７と検索部１４８とを有する。ストレージ装置１４０は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、ストレージ装置１４０は、制御部１４５の制御のもと各処理を実行する。
【０１１２】
図４に例示するように、暗号化データベース格納部１４３には、文書などの検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)の暗号文CT(TAR(indt))と、予め定められたキーワードの全体集合WSETから検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワード（登録キーワード）WT(indt)を除いた補集合CSET(indt)=WSET-WT(indt)に対して設定されるベクトルw→に対応する第１暗号方式の第１暗号文(T(indt,1),…,T(indt,N))と、第１暗号文(T(indt,1),…,T(indt,N))の復号値を共通鍵Kとした第２暗号方式（共通鍵暗号方式）の暗号文T(indt)と、暗号文T(indt)の復号値RE(indt)とがそれぞれ対応付けられた暗号化データベースが格納されている。暗号文CT(TAR(indt))にそれぞれ対応付けられる((T(indt,1),…,T(indt,N)), T(indt), RE(indt))を検索対象情報TAR(indt)に対応するタグ情報Tag(indt)（否定タグ情報）と呼ぶ。否定タグ情報Tag(indt)の第１暗号文(T(indt,1),…,T(indt,N))は、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットしないときに当該検索クエリを復号鍵として用いて正しく復号される暗号文である。また、この正しい復号値を共通鍵Kとして暗号文T(indt)を復号した場合の復号値はRE(indt)となる。よって、検索クエリを用いて第１暗号文(T(indt,1),…,T(indt,N))を復号して得られる値を共通鍵Kとして暗号文T(indt)を復号した値がRE(indt)である場合、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットしていないことになる。検索クエリに対応する検索用キーワードが登録キーワードにヒットすることの意義は検索方式による。また、暗号文CT(TAR(indt))を生成するための検索対象情報TAR(indt)の暗号化方式には限定はなく、任意の既存の暗号化方式（共通鍵暗号方式，公開鍵暗号方式，述語暗号方式、関数暗号方式など）でよい。また、当該既存の暗号方式は、本形態の検索可能暗号を構成するための第１暗号方式と同じであっても違ってもよい。暗号化データベースの構成及び生成方法の詳細は後述する。
【０１１３】
図５に例示するように、暗号化データベース格納部１４３には、さらに暗号文CT(TAR(indt))と、検索対象情報TAR(indt)に対応する登録キーワードに対して設定されるベクトルw→に対応する第１暗号方式の第２暗号文(LT(indt,1),…,LT(indt,N))と、第２暗号文(LT(indt,1),…,LT(indt,N))の復号値を共通鍵Kとした第３暗号方式（共通鍵暗号方式）の暗号文LT(indt)と、第２暗号文LT(indt)の復号値LR(indt)とが対応付けられた第２暗号化データベースが格納されている。暗号文CT(TAR(indt))にそれぞれ対応付けられる((LT(indt,1),…,LT(indt,N)), LT(indt), LR(indt))を検索対象情報TAR(indt)に対応するタグ情報LTag(indt)（肯定タグ情報）と呼ぶ。肯定タグ情報LTag(indt)の第２暗号文(LT(indt,1),…,LT(indt,N))は、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットするときに当該検索クエリを復号鍵として用いて正しく復号される暗号文である。また、この正しい復号値を共通鍵Kとして暗号文LT(indt)を復号した場合に復号値としてLR(indt)が得られる。よって、検索クエリを用いて第２暗号文(LT(indt,1),…,LT(indt,N))を復号して得られる値を共通鍵Kとして暗号文LT(indt)を復号した値がLR(indt)である場合、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットしていることになる。第２暗号化データベースの構成及び生成方法の詳細は後述する。
【０１１４】
［検索装置１５０−ｕ］
図６に例示するように、検索装置１５０−ｕは、入力部１５１−ｕと出力部１５２−ｕと検索対象情報復号鍵格納部１５４−ｕと制御部１５５−ｕとベクトル設定部１５６−ｕと検索クエリ生成部１５７−ｕと復号部１５８−ｕとを有する。検索装置１５０−ｕは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、検索装置１５０−ｕは、それぞれ、制御部１５５−ｕの制御のもと各処理を実行する。なお、図面表記の便宜上、図６には２つの入力部１５１−ｕが記載されているが、これは入力部の種類や個数を限定するものではない。
【０１１５】
＜事前処理＞
前述した［内積述語暗号方式の基本構成］のSetupが実行され、マスタ秘密鍵MSK，公開パラメータPKが定められる。マスタ秘密鍵MSKは、管理装置１１０（図２Ａ）のマスタ秘密鍵格納部１１３に安全に格納される。管理装置１１０，登録装置１２０−ｕ，及び検索装置１５０−ｕは、公開パラメータPKを用いた処理が可能なように構成される。
【０１１６】
登録装置１２０−ｕ（図２Ｂ）の登録キーワード格納部１２３ｂ−ｕには、登録を行う検索対象情報TAR(indt)の暗号文CT(TAR(indt))と検索対象情報TAR(indt)に対応するキーワードWT(indt)とが格納されている。キーワードWT(indt)は、例えば、検索対象情報TAR(indt)に含まれるキーワード又は複数のキーワードの集合である。
【０１１７】
検索装置１５０−ｕ（図６）の検索対象情報復号鍵格納部１５４−ｕには、登録装置１２０−ｕ（図２Ｂ）の登録キーワード格納部１２３ｂ−ｕに格納された暗号文CT(TAR(indt))を復号するための検索対象情報復号鍵Key(indt)が格納されている。
【０１１８】
＜データベース登録＞
登録ユーザは登録装置１２０−ｕを用い、図７に例示するようにデータベース登録を行う。登録されるデータベースは、図４に例示するような暗号文CT(TAR(indt))と否定タグ情報Tag(indt)とが対応付けられた暗号化データベース、及び、図５に例示するような暗号文CT(TAR(indt))と肯定タグ情報LTag(indt)とが対応付けられた第２暗号化データベースである。
【０１１９】
登録装置１２０−ｕ（図２Ｂ）のベクトル設定部１２６ｅ−ｕが、登録キーワード格納部１２３ｂ−ｕから検索対象情報TAR(indt)に対応する登録キーワードWT(indt)を抽出する（ステップＳ１０１）。ベクトル設定部１２６ｅ−ｕは、予め定められたキーワードの全体集合WSETから検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応する登録キーワードWT(indt)を除いた補集合CSET(indt)=WSET-WT(indt)に対応するベクトルwCSET→∈Fqを設定する。具体的なベクトルwCSET→の構成は検索方式による。以下に具体的なベクトルwCSET→の構成例を示す。
【０１２０】
［ベクトルwCSET→の構成例１（単一単語一致検索の場合）］
ベクトルwCSET→の構成例１は、単一単語一致検索に対応する例である。単一単語一致検索とは、検索用キーワードの少なくとも一部と検索対象情報TAR(indt)に対応する登録キーワードの少なくとも一部とが順序及び内容について一致するという検索条件（「検索条件１」と呼ぶ）を満たした場合にヒットとされる検索方式である。すなわち単一単語一致検索では、検索対象情報TAR(indt)に対応する登録キーワードをWT(indt)={η1(indt),...,ηL(indt)}(Lは1以上の整数)とし、検索用キーワードをWQ={x1,...,xL}とした以下の述語多項式の値が0になるときにヒットとされる。
【０１２１】
(x1-η1(indt))…(xL-ηL(indt))          …(56)
この検索条件の否定を表す述語多項式を考える。すなわち、検索条件１を満たしていないとき（すなわちヒットしないとき）に0になる述語多項式を考える。この例では、キーワードの全体集合WSETから登録キーワードWT(indt)を除いた補集合CSET(indt)を以下のようにする。
【０１２２】
CSET(indt)={ηθ,π(indt)}=WSET-{ηθ(indt)}          …(57)
ただし、θ=1,...,L、π=1,...,πmaxであり、πmaxは1以上の整数であり、ηθ,πmax(indt)=⊥であり、xθに対応するキーワードが存在しない場合に(xθ-⊥)=0を満たす。式(56)が表す検索条件の否定を表す述語多項式は以下のようになる。
【０１２３】
ι1(x1-η1,1(indt))(x1-η1,2(indt))…(x1-η1,πmax-1(indt))(x1-η1,πmax(indt))+…+ιL(xL-ηL,1(indt))(xL-ηL,2(indt))…(xL-ηL,πmax-1(indt))(xL-ηL,πmax(indt))          …(58)
ただし、ι1,...,ιLは乱数である。
【０１２４】
式(56)の述語多項式の値が0となるとき（ヒットするとき）、式(58)の述語多項式の値は0以外となる。式(56)の述語多項式の値が0以外となるとき（ヒットしないとき）、式(58)の述語多項式の値は0となる。式(58)は以下のように変形できる。
【０１２５】
【数２１】
0005400809.tif 000024
ただし、SYθ,π'(indt)は(-ηθ,π(indt))に関するπ'次の基本対称式である。
【０１２６】
ベクトルwCSET→の構成例１では、式(59)の(x1πmax … xL0)がベクトル
wCSET→=(x1πmax … xL0)          …(60)
として設定される。
【０１２７】
［ベクトルwCSET→の構成例２（部分集合判定検索の場合）］
ベクトルwCSET→の構成例２は、部分集合判定検索に対応する例である。部分集合判定検索とは、検索用キーワードの少なくとも一部と検索対象情報TAR(indt)に対応する登録キーワードの少なくとも一部とが順序にかかわらず内容について一致するという検索条件（「検索条件２」と呼ぶ）を満たした場合にヒットとされる検索方式である。すなわち部分集合判定検索では、検索対象情報TAR(indt)に対応する登録キーワードをWT(indt)={η1(indt),...,ηL(indt)}(Lは1以上の整数)とし、検索用キーワードをWQ={x1,...,xL}とした以下の述語多項式の値が0になるときにヒットとされる。
【０１２８】
(x1-η1(indt))(x2-η1(indt))…(xL-η1(indt))+ 
… +(x1-ηL(indt))(x2-ηL(indt))…(xL-ηL(indt))          …(61)
この検索条件の否定を表す述語多項式を考える。すなわち、検索条件２を満たしていないとき（すなわちヒットしないとき）に0になる述語多項式を考える。この例では、キーワードの全体集合WSETから登録キーワードWT(indt)を除いた補集合CSET(indt)を以下のようにする。
【０１２９】
CSET(indt)={ηπ(indt)}=WSET-{η1(indt),...,ηL(indt)}
ただし、π=1,...,πmaxであり、πmaxは1以上の整数であり、ηθ(indt)(L+1≦θ≦πmax)は前述の⊥である。式(61)が表す検索条件の否定を表す述語多項式は以下のようになる。
【０１３０】
ι1(x1-η1(indt))(x2-η1(indt))…(xL-η1(indt))+…+ιL(x1-ηL(indt))(x2-ηL(indt))…(xL-ηL(indt))          …(62)
ただし、ι1,...,ιLは乱数である。
【０１３１】
式(61)の述語多項式の値が0となるとき（ヒットするとき）、式(62)の述語多項式の値は0以外となる。式(61)の述語多項式の値が0以外となるとき（ヒットしないとき）、式(62)の述語多項式の値は0となる。式(62)は以下のように変形できる。
【０１３２】
【数２２】
0005400809.tif 000025
ただし、SYπ'(indt)は(-ηθ(indt))に関するπ'次の基本対称式である
ベクトルwCSET→の構成例２では、式(63)の(x'0… x'πmax)がベクトル
wCSET→=(x'0 … x'πmax)          …(64)
として設定される（ベクトルwCSET→の構成例の説明終わり／ステップＳ１０２）。
【０１３３】
ベクトルwCSET→は暗号化部１２６ｆ−ｕに入力される。暗号化部１２６ｆ−ｕは、第１暗号方式に則ってベクトルwCSET→に対応する第１暗号文(T(indt,1),…,T(indt,N))を生成する。本形態の暗号化部１２６ｆ−ｕは、wCSET→=(w1,...,wn)とした式(34)に従って、以下のような第１暗号文(T(indt,1),…,T(indt,N))を生成する。
【０１３４】
C1=(T(indt,1),…,T(indt,N))∈G1n+ζ          …(65)
ただし、この例ではN=n+ζである（ステップＳ１０３）。
【０１３５】
乱数生成部１２６ｃ−ｕはRE(indt)∈GTをランダムに生成し、RE(indt)を暗号化部１２６ｆ−ｕに送る。暗号化部１２６ｆ−ｕは、gTτ・υ1を共通鍵Kとし、第２暗号方式に則ってRE(indt)を暗号化した暗号文T(indt)を生成する。例えば、暗号化部１２６ｆ−ｕは、mes=RE(indt)とした式(36)に従い、以下のように暗号文T(indt)を生成する。
【０１３６】
C2=T(indt)=gTτ・υ1・RE(indt)∈GT          …(66)
このように生成された(T(indt,1),…,T(indt,N))、T(indt)及びRE(indt)はタグ情報生成部１２６ｇ−ｕに送られる（ステップＳ１０４）。
【０１３７】
タグ情報生成部１２６ｇ−ｕは、(T(indt,1),…,T(indt,N))、T(indt)及びRE(indt)を互いに対応付けた否定タグ情報Tag(indt)を以下のように生成する。
【０１３８】
Tag(indt)=((T(indt,1),…,T(indt,N)), T(indt), RE(indt))    …(67)
否定タグ情報Tag(indt)は出力部１２２−ｕに送られる（ステップＳ１０５）。
【０１３９】
また、ベクトル設定部１２６ｅ−ｕは、検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応する登録キーワードWT(indt)に対応するベクトルwT→∈Fqを設定する。具体的なベクトルwT→の構成は検索方式による。以下に具体的なベクトルwT→の構成例を示す。
【０１４０】
［ベクトルwT→の構成例１（単一単語一致検索の場合）］
ベクトルwT→の構成例１は、前述した単一単語一致検索に対応する例である。前述のように単一単語一致検索では、検索対象情報TAR(indt)に対応する登録キーワードをWT(indt)={η1(indt),...,ηL(indt)}(Lは1以上の整数)とし、検索用キーワードをWQ={x1,...,xL}とした式(56)の述語多項式の値が0になるときにヒットとされる。式(56)もその各項の不定元成分(x1,...,xL)と１Fとを各要素とするベクトルw→=(w1,...,wn)と各項の係数成分を各要素とするベクトルv→=(v1,...,vn)との内積に変形できる。ベクトルwT→の構成例１では、そのベクトルw→=(w1,...,wn)がベクトルwT→として設定される。
【０１４１】
［ベクトルwT→の構成例２（部分集合判定検索の場合）］
ベクトルwT→の構成例２は、前述の部分集合判定検索に対応する例である。前述のように部分集合判定検索では、検索対象情報TAR(indt)に対応する登録キーワードをWT(indt)={η1(indt),...,ηL(indt)}(Lは1以上の整数)とし、検索用キーワードをWQ={x1,...,xL}とした式(61)の述語多項式の値が0になるときにヒットとされる。式(61)もその各項の不定元成分(x1,...,xL)と１Fとを各要素とするベクトルw→=(w1,...,wn)と各項の係数成分を各要素とするベクトルv→=(v1,...,vn)との内積に変形できる。ベクトルwT→の構成例２では、そのベクトルw→=(w1,...,wn)がベクトルwT→として設定される（ベクトルwT→の構成例の説明終わり／ステップＳ１０６）。
【０１４２】
ベクトルwT→は暗号化部１２６ｆ−ｕに入力される。暗号化部１２６ｆ−ｕは、第１暗号方式に則ってベクトルwT→に対応する第２暗号文(LT(indt,1),…,LT(indt,N))を生成する。本形態の暗号化部１２６ｆ−ｕは、wT→=(w1,...,wn)とした式(34)に従って、以下のように第２暗号文(LT(indt,1),…,LT(indt,N))を生成する。
【０１４３】
C1=(LT(indt,1),…,LT(indt,N))∈G1n+ζ          …(68)
ただし、この例ではN=n+ζである（ステップＳ１０７）。
【０１４４】
乱数生成部１２６ｃ−ｕはRE(indt)∈GTをランダムに生成し、RE(indt)を暗号化部１２６ｆ−ｕに送る。暗号化部１２６ｆ−ｕは、gTτ・υ1を共通鍵Kとし、第２暗号方式に則ってLR(indt)を暗号化した暗号文LT(indt)を生成する。例えば、暗号化部１２６ｆ−ｕは、mes=LR(indt)とした式(36)に従い、以下のように暗号文LT(indt)を生成する。
【０１４５】
C2=LT(indt)=gTτ・υ1・LR(indt)∈GT          …(69)
このように生成された(LT(indt,1),…,LT(indt,N))、LT(indt)及びLR(indt)はタグ情報生成部１２６ｇ−ｕに送られる（ステップＳ１０８）。
【０１４６】
タグ情報生成部１２６ｇ−ｕは、(LT(indt,1),…,LT(indt,N))、LT(indt)及びLR(indt)を互いに対応付けた肯定タグ情報LTag(indt)を以下のように生成する。
【０１４７】
LTag(indt)=((LT(indt,1),…,LT(indt,N)), LT(indt), LR(indt))    …(70)
肯定タグ情報LTag(indt)は出力部１２２−ｕに送られる（ステップＳ１０９）。
【０１４８】
出力部１２２−ｕには、さらに前述の否定タグ情報LTag(indt)、及び登録キーワード格納部１２３ｂ−ｕから読み出された検索対象情報TAR(indt)の暗号文CT(TAR(indt))が送られる。出力部１２２−ｕは、CT(TAR(indt))、LTag(indt)及びLTag(indt)を出力する（ステップＳ１１０）。
【０１４９】
CT(TAR(indt))、LTag(indt)及びLTag(indt)はストレージ装置（図３）の入力部１４１に入力される。書込み部１４６はCT(TAR(indt))、LTag(indt)及びLTag(indt)を互いに対応付け、図４及び５に示したように暗号化データベース格納部１４３に格納する（ステップＳ１１１）。
【０１５０】
＜バッチ検索用の事前計算＞
ストレージ装置（図３）のバッチ検索部１４７は、後述するバッチ検索のために以下のような事前計算を行う。この事前計算は定期的に行われてもよいし、暗号化データベース格納部１４３が更新されるたびに行われてもよい。或いは、暗号化データベース格納部１４３の更新後に後述するバッチ検索が始めて実行されるときに行われてもよい。以下では暗号化データベース格納部１４３に、indt=1,…,maxt(maxt≧2)についてのCT(TAR(indt))及びTag(indt)が互いに対応付けられて格納されていることを前提とする（図４参照）。
【０１５１】
バッチ検索部１４７は、まずsub={1,…,maxt}とし、indN=1,…,Nについて式(71)-(73)を事前計算し、BT(indN)(indN=1,…,N)、BT、及びREをsubに対応付けて暗号化データベース格納部１４３に格納する。
【０１５２】
【数２３】
0005400809.tif 000026
同様にsubを分割して得られるsubの真部分集合のそれぞれを新たなsubとし、indN=1,…,Nについて式(71)-(73)が事前計算され、BT(indN)(indN=1,…,N)、BT、及びREがsubに対応付けられて暗号化データベース格納部１４３に格納される処理が繰り返される。subの分割方法や分割回数はストレージ装置１４０で事前に定められ、この分割方法や分割回数は後述のバッチ検索にも対応する。ただし、どのような分割方法や分割回数が設定されるかについての限定はない。subの分割方法の例は、subをDIV個（DIVは2や3などの正整数）の真部分集合に分割する方法などである。subの分割回数の例は、subを分割して得られる新たなsubの要素数が基準値以下になるまで分割する方法や、事前に定められた固定回数まで分割する方法などである。例えば、subを２つの真部分集合に分割してsubを更新し、subの分割回数を２回とするのであれば、例えば、sub={1,…,maxt}に対する式(71)-(73)の事前計算値、sub={1,…,maxt/2}及びsub={(maxt/2)+1,…,maxt}のそれぞれに対する式(71)-(73)の事前計算値、及びsub={1,…,maxt/4},sub={(maxt/4)+1,…,maxt/2},sub={(maxt/2)+1,…, 3・maxt/2},sub={(3・maxt/2)+1,…,maxt}のそれぞれに対する式(71)-(73)の事前計算値が暗号化データベース格納部１４３に格納される（図４参照）。
【０１５３】
＜検索＞
登録ユーザは検索装置１５０−ｕ（図６）を用い、以下のようにストレージ装置１４０に格納された暗号化データベースを検索する。
【０１５４】
図８に例示するように、まず検索を行う登録ユーザによって選択された検索用キーワードWQが入力部１５１−ｕに入力される（ステップＳ１２１）。検索用キーワードWQはベクトル設定部１５６−ｕに送られる。ベクトル設定部１５６−ｕは、システム内で定められた規則に従い、否定タグ情報Tag(indt)及び肯定タグ情報LTag(indt)のそれぞれに対し、検索方式と検索用キーワードWQに対応する第２ベクトルvQ→を設定する。
【０１５５】
否定タグ情報Tag(indt)に対応する第２ベクトルvQ→は、検索方式と検索用キーワードWQとの組に対して第１ベクトルwT→に対応する登録キーワードWT(indt)がヒットする場合に内積wT→・vQ→≠0を満たし、ヒットしない場合に内積wT→・vQ→=0を満たすものである。例えば、前述のベクトルwCSET→の構成例１の場合、ベクトル設定部１５６−ｕは、式(59)が含む以下のベクトルを第２ベクトルvQ→とする。
【０１５６】
(ι1・SY1,0(indt),…,ι1・SY1,πmax(indt),ι2・SY2,0(indt),…,ι2・SY2,πmax(indt),…,ιL・SYL,πmax(indt))      …(74)
或いは、前述のベクトルwCSET→の構成例２の場合、式(59)が含む以下のベクトルを第２ベクトルvQ→とする。
【０１５７】
(SY0(indt),…,SYπmax(indt))          …(75)
肯定タグ情報Tag(indt)に対応する第２ベクトルvQ→は、検索方式と検索用キーワードWQとの組に対して第１ベクトルwT→に対応する登録キーワードWT(indt)がヒットする場合に内積wT→・vQ→=0を満たし、ヒットしない場合に内積wT→・vQ→≠0を満たすものである。例えば、ベクトルwT→の構成例１の場合、式(56)を各項の不定元成分(x1,...,xL)と１Fとを各要素とするベクトルw→=(w1,...,wn)と各項の係数成分を各要素とするベクトルv→=(v1,...,vn)との内積に変形した場合のベクトルv→を第２ベクトルvQ→とする。或いは、ベクトルwT→の構成例２の場合、式(61)を各項の不定元成分(x1,...,xL)と１Fとを各要素とするベクトルw→=(w1,...,wn)と各項の係数成分を各要素とするベクトルv→=(v1,...,vn)との内積に変形した場合のベクトルv→を第２ベクトルvQ→とする（ステップＳ１２２）。
【０１５８】
否定タグ情報Tag(indt)及び肯定タグ情報LTag(indt)のそれぞれに設定された第２ベクトルvQ→は検索クエリ生成部１５７−ｕに送られる。検索クエリ生成部１５７−ｕは、出力部１５２−ｕを介して管理装置１１０にアクセスし、管理装置１１０（図２Ａ）に否定タグ情報Tag(indt)及び肯定タグ情報LTag(indt)のそれぞれに設定された第２ベクトルvQ→を送る。これらは管理装置１１０の入力部１１１に入力され、鍵情報生成部１１６ａに送られる。鍵情報生成部１１６ａは、マスタ秘密鍵格納部１１３に格納されたマスタ鍵情報MSKを用い、否定タグ情報Tag(indt)に対する第２ベクトルvQ→に対応する第１暗号方式の復号鍵である検索クエリQUE(Tag)と、肯定タグ情報LTag(indt)に対する第２ベクトルvQ→に対応する第１暗号方式の復号鍵である検索クエリQUE(LTag)とをそれぞれ生成する。これらはvQ→=(v1,...,vn)とした式(32)に従ってそれぞれ生成できる。
【０１５９】
Tag(indt)=(que1,…,queN)∈G2n+ζ          …(76)
LTag(indt)=(Lque1,…,LqueN)∈G2n+ζ       …(77)
ただし、n+ζ=Nであり、ζ＞ζ'の場合には、
queN-(ζ-ζ')=…=queN=0
LqueN-(ζ-ζ')=…=LqueN=0
とされる。検索クエリQUE(Tag)と検索クエリQUE(LTag)は出力部１１２から出力され、検索装置１５０−ｕ（図６）の入力部１５１−ｕ経由で検索クエリ生成部１５７−ｕに送られる（ステップＳ１２３）。
【０１６０】
生成された検索クエリQUE(Tag)及びQUE(LTag)は出力部１５２−ｕに送られ、出力部１５２−ｕはこれらを出力する（ステップＳ１２４）。
【０１６１】
図９に示すように、検索クエリQUE(Tag)及びQUE(LTag)はストレージ装置１４０（図３）の入力部１４１に入力され、バッチ検索部１４７と検索部１４８にそれぞれ送られる（ステップＳ１３１）。
【０１６２】
制御部１４５は、まずsub={1,…,maxt}とする（ステップＳ１３２）。バッチ検索部１４７は、否定タグ情報Tag(indt)に対する検索クエリQUE(Tag)を用い、暗号化データベース格納部１４３に格納された否定タグ情報Tag(inds)(inds∈sub)をまとめてバッチ検証する。すなわち、検索クエリQUE(Tag)を用い、inds∈sub⊆{1,…,maxt}についての第１暗号文(T(inds,1),…,T(inds,N))の合成値（式(71)）が正しく復号できるかを判定する。具体的には本形態のバッチ検索部１４７は、検索クエリQUE(Tag)を復号鍵として用い、inds∈subについての第１暗号文(T(inds,1),…,T(inds,N))の関数値(BT(1),…,BT(N))（式(71)）を第１暗号方式に則って復号して得られる値を共通鍵とし、inds∈subについての暗号文T(inds)の関数値BT（式(72)）を第２暗号方式に則って復号して得られる値がinds∈subについての復号値RE(inds)の関数値RE（式(73)）であるか（true）否か（false）を判定する。例えば、式(65)(66)のような計算で否定タグ情報Tag(inds)が得られたのであれば、バッチ検索部１４７は、以下を満たすか（true）否か（false）を判定する。
【０１６３】
【数２４】
0005400809.tif 000027
原則、この判定を行うために必要な(BT(1),…,BT(N))、BT、及びREは、前述の事前計算で得られたものである。ただし、必要な(BT(1),…,BT(N))、BT、及びREが格納されていないのであれば、バッチ検索部１４７はそれらを計算してこの判定を行い、以降の処理のためにそれらの値を暗号化データベース格納部１４３に格納しておいてもよい。また、式(78)によって否定タグ情報Tag(inds)(inds∈sub)をまとめてバッチ検証できるのは、次の関係が成り立つことに立脚している。
【０１６４】
【数２５】
0005400809.tif 000028
式(79)の右辺は式(78)の左辺の分母である。この事実は前述した双線形写像Pairの線形性（式(6)参照）から成り立つ（ステップＳ１３３）。
【０１６５】
ステップＳ１３３の判定でtrueと判定された場合には（ステップＳ１３４）、検索用キーワードWQに対して何れの検索対象情報TAR(inds)(inds∈sub)もヒットしないことになる。この場合にはinds∈subに対応する各検索対象情報TAR(inds)に対する検索が終了し、ステップＳ１３９へ進む。一方、ステップＳ１３３の判定でfalseと判定された場合(inds∈sub⊆{1,…,maxt}についての第１暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できないと判定された場合)には（ステップＳ１３４）、検索用キーワードWQに対して何れの検索対象情報TAR(inds)(inds∈sub)がヒットすることになる。この場合にはステップＳ１３５に進み、subの要素数が基準値以下であるかが判定される。なお、「基準値」の例は１や２以上の整数定数やDIVなどである（ステップＳ１３５）。
【０１６６】
ステップＳ１３５でsubの要素数が基準値以下ではないと判定された場合には、subを分割して得られるsubの真部分集合のそれぞれを新たなsubとし、ステップＳ１３３に戻る。なお、ここでのsubの分割方法は、例えば前述のバッチ検索用の事前計算でのsubの分割方法と同一とする（ステップＳ１３６）。
【０１６７】
一方、ステップＳ１３５でsubの要素数が基準値以下であると判定された場合、検索クエリQUE(LTag)を用いた肯定タグ情報LTag(indt)の検証に切り替えられる。すなわち、検索部１４８が検索クエリQUE(LTag)（第２検索クエリ）を復号鍵として用い、第２暗号文(LT(inds,1),…,LT(inds,N))（inds∈sub）が正しく復号できるかを判定する。本形態の検索部１４８は検索クエリQUE(LTag)を復号鍵として用い、肯定タグ情報LTag(indt)が含む第２暗号文(LT(inds,1),…,LT(inds,N))（inds∈sub）（図５）を第１暗号方式に則って復号して得られる値を共通鍵とし、暗号文LT(inds)を第３暗号方式に則って復号して得られる値が復号値LR(inds)であるかを判定する。例えば、式(68)(69)のような計算で肯定タグ情報LTag(inds)が得られたのであれば、検索部１４８は、以下を満たすか（true）否か（false）を判定する。
【０１６８】
【数２６】
0005400809.tif 000029
これは、検索対象情報TAR(inds)が検索用キーワードWQにヒットするか（true）否か（false）を肯定タグ情報LTag(inds)ごとに判定することに相当する（ステップＳ１３７）。
【０１６９】
検索部１４８は、ステップＳ１３７の判定でtrueと判定された肯定タグ情報LTag(inds)のindsに対応する暗号文CT(TAR(inds))を集合HITに追加し、図示しないメモリに格納し（ステップＳ１３８）、ステップＳ１３９に進む。
【０１７０】
ステップＳ１３９では、制御部１４５が未検証のsubが存在するかを判定する（ステップＳ１３９）。ここで、未検証のsubが存在すると判定された場合には、ステップＳ１３３に進む。一方、未検証のsubが存在しないと判定された場合には、検索部１４８は、集合HITの要素である暗号文CT(TAR(indt))を出力する。集合HITの要素が存在しなければ検索部１４８は、ヒットしなかったことを表す⊥を出力する（ステップＳ１４０）。これらは出力部１４２から出力される。
【０１７１】
図８に示すように、集合HITの要素である暗号文CT(TAR(indt))又は⊥は、検索装置（図６）の入力部１５１−ｕに入力される（ステップＳ１２５）。暗号文CT(TAR(indt))は、復号部１５８−ｕに送られる。復号部１５８−ｕは検索対象情報復号鍵格納部１５４−ｕから検索対象情報復号鍵Key(indt)を読み出し、これを用いて暗号文CT(TAR(indt))を復号して検索対象情報TAR(indt)を出力する（ステップＳ１２６）。
【０１７２】
図１０を用いて上記の処理を概念的に説明する。なお、図１０はsubを２個の真部分集合に分割する例であるが、これは本発明を限定しない。
【０１７３】
最初にsub={1,…,maxt}=setとされ（ステップＳ１３２）、検索クエリを用いてTag(inds)(inds∈sub)をまとめてバッチ検証する（ステップＳ１３３）。ステップＳ１３３でtrueであればsubについての検索を終了する。ステップＳ１３３でfalseであれば、setを分割して得られるsub1及びsub2がそれぞれsubとされ（ステップＳ１３６）、ステップＳ１３３の処理が実行される。ステップＳ１３３でtrueと判定されたsubについての検索を終了し、ステップＳ１３３でfalseのsubについてはさらに分割を行う。例えば、sub1及びsub2で共にfalseと判定されたのであれば、sub1を分割して得られるsub3並びにsub4、及びsub2を分割して得られるsub5並びにsub6がそれぞれsubとされ、ステップＳ１３３の処理が実行される。例えばsub3の要素数が基準値以下であるとすると、sub3を分割したsub7及びsub8の各要素に対してステップＳ１３７の処理が実行され、ステップＳ１３７でtrueとされたindsに対応する暗号文CT(TAR(inds))が集合HITに追加される（ステップＳ１３８）。
【０１７４】
〔第２実施形態〕
次に本発明の第２実施形態を説明する。本形態では、第１暗号方式として階層的内積述語暗号方式を用いる。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については第１実施形態と同じ参照番号を用い、説明を簡略化する。
【０１７５】
＜構成＞
図１１に例示するように、本形態の検索可能暗号システム２は、管理装置２１０−ｍ（m=1,...,M）と登録装置２２０−ｕ（u=1,...,U）と検索代行装置２３０とストレージ装置２４０と検索装置２５０−ｕ（u=1,...,U）とを有する。なお、Ｍ及びＵはそれぞれ１以上の整数である。また、管理装置２１０−ｍは、検索可能暗号システム２のｍ番目の管理者が使用する装置である。本形態では、小さいｍに対応する管理者ほど強い管理権限を持つ。すなわち、ｍ＝１に対応する管理者が最も強い権限を持つ。また、登録装置２２０−ｕ及び検索装置２５０−ｕは、検索可能暗号システム２を利用するｕ番目の登録ユーザが使用する装置である。また、各装置は他の装置へ情報を提供可能なように構成されている。装置間の情報提供はネットワークを通じて行われてもよいし、可搬型記録媒体を介して行われてもよい。
【０１７６】
［管理装置］
図１２Ａに例示するように、管理装置２１０−１は、入力部２１１−１と出力部２１２−１とマスタ秘密鍵格納部２１３−１と管理者秘密鍵格納部２１４−１と制御部２１５−１とベクトル設定部２１６ａ−１と鍵情報生成部２１６ｂ−１と補間鍵生成部２１６ｄ−１と検索者鍵生成部２１６ｃ−１と失効情報生成部２１６ｅ−１とを有する。図１２Ｂに例示するように、管理装置２１０−（ｍ’＋１）（m'=1,...,M-1）は、入力部２１１−（ｍ’＋１）と出力部２１２−（ｍ’＋１）と制御部２１５−（ｍ’＋１）とベクトル設定部２１６ａ−（ｍ’＋１）と鍵情報生成部２１６ｂ−（ｍ’＋１）とを有する。管理装置２１０−ｍは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、管理装置２１０−ｍは、それぞれ、制御部２１５−ｍの制御のもと各処理を実行する。また、管理装置２１０−ｍでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【０１７７】
［登録装置］
図１３に例示するように、登録装置２２０−ｕは、入力部２２１−ｕと出力部１２２−ｕと属性格納部２２３ａ−ｕと登録キーワード格納部１２３ｂ−ｕと検索者鍵格納部２２３ｃ−ｕと制御部１２５−ｕと写像部２２６ａ−ｕ，２２６ｄ−ｕと乱数生成部２２６ｂ−ｕ，１２６ｃ−ｕとベクトル設定部２２６ｅ−ｕと暗号化部２２６ｆ−ｕとタグ情報生成部２２６ｇ−ｕとを有する。登録装置２２０−ｕは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、登録装置２２０−ｕは、それぞれ、制御部１２５−ｕの制御のもと各処理を実行する。なお、図面表記の便宜上、図１３には２つの入力部２２１−ｕが記載されているが、これは入力部の種類や個数を限定するものではない。また、登録装置２２０−ｕでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【０１７８】
［検索代行装置２３０］
図１４Ａに例示するように、検索代行装置２３０は、入力部２３１と出力部２３２と補間鍵格納部２３３と制御部２３５と写像部２３６と検証処理部２３７（「バッチ検索部」及び「検索部」に相当）とを有する。検索代行装置２３０は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、検索代行装置２３０は、それぞれ、制御部２３５の制御のもと各処理を実行する。また、検索代行装置２３０での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。なお、図面表記の便宜上、図１４Ａには２つの入力部２３１が記載されているが、これは入力部の種類や個数を限定するものではない。
【０１７９】
［ストレージ装置２４０］
図１４Ｂに例示するように、ストレージ装置２４０は、入力部１４１と出力部１４２と暗号化データベース格納部２４３と制御部１４５と読み書き部２４６とを有する。ストレージ装置２４０は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、ストレージ装置２４０は、制御部２３５の制御のもと各処理を実行する。
【０１８０】
図１５Ａに例示するように、暗号化データベース格納部２４３には、文書などの検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)の暗号文CT(TAR(indt))と、第１実施形態と同様な第１暗号文(T(indt,1),…,T(indt,N))と、第１暗号文(T(indt,1),…,T(indt,N))の復号値を共通鍵Kとした第２暗号方式（共通鍵暗号方式）の暗号文T(indt)と、暗号文T(indt)の復号値r'(indt)=e^(indt)・RE(indt)に対するe^(indt)に対応するh(indt)と、RE(indt)とがそれぞれ対応付けられた暗号化データベースが格納されている。なお、e^(indt)はh(indt)とckuに対応する（詳細は後述）。本形態では、暗号文CT(TAR(indt))にそれぞれ対応付けられる((T(indt,1),…,T(indt,N)), T(indt), h(indt), RE(indt))を検索対象情報TAR(indt)に対応するタグ情報Tag(indt)（否定タグ情報）と呼ぶ。否定タグ情報Tag(indt)の第１暗号文(T(indt,1),…,T(indt,N))は、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットしないときに当該検索クエリを復号鍵として用いて正しく復号される暗号文である。また、この正しい復号値を共通鍵Kとして暗号文T(indt)を復号した場合の復号値はe^(indt)・RE(indt)となる。よって、検索クエリを用いて第１暗号文(T(indt,1),…,T(indt,N))を復号して得られる値を共通鍵Kとして暗号文T(indt)を復号した値がe^(indt)・RE(indt)である場合、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットしていないことになる。暗号化データベースの構成及び生成方法の詳細は後述する。
【０１８１】
図１５Ｂに例示するように、暗号化データベース格納部２４３には、さらに暗号文CT(TAR(indt))と、第１実施形態と同様な第２暗号文(LT(indt,1),…,LT(indt,N))と、第２暗号文(LT(indt,1),…,LT(indt,N))の復号値を共通鍵Kとした第３暗号方式（共通鍵暗号方式）の暗号文LT(indt)と、第２暗号文LT(indt)の復号値Lr'(indt)=e^(indt)・LR(indt)に対するe^(indt)に対応するh(indt)と、LR(indt)とがそれぞれ対応付けられた第２暗号化データベースが格納されている。暗号文CT(TAR(indt))にそれぞれ対応付けられる((LT(indt,1),…,LT(indt,N)), LT(indt), h(indt), LR(indt))を検索対象情報TAR(indt)に対応するタグ情報LTag(indt)（肯定タグ情報）と呼ぶ。肯定タグ情報LTag(indt)の第２暗号文(LT(indt,1),…,LT(indt,N))は、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットするときに当該検索クエリを復号鍵として用いて正しく復号される暗号文である。また、この正しい復号値を共通鍵Kとして暗号文LT(indt)を復号した場合に復号値としてe^(indt)・LR(indt)が得られる。よって、検索クエリを用いて第２暗号文(LT(indt,1),…,LT(indt,N))を復号して得られる値を共通鍵Kとして暗号文LT(indt)を復号した値がe^(indt)・LR(indt)である場合、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットしていることになる。第２暗号化データベースの構成及び生成方法の詳細は後述する。
【０１８２】
［検索装置２５０−ｕ］
第１暗号方式が異なり、検索クエリ生成部２５７−ｕが検索クエリ生成部２５７−ｕに置換され、鍵情報格納部２５３−ｕが追加される以外、第１実施形態と同様であるため説明を省略する。
【０１８３】
＜事前処理＞
前述した［階層的内積述語暗号方式の基本構成］のSetupが実行され、階層フォーマットξ→，マスタ秘密鍵MSK，公開パラメータmpkが定められる。マスタ秘密鍵MSKは、管理装置２１０−１（図１２Ａ）のマスタ秘密鍵格納部２１３−１に安全に格納され、管理装置２１０−ｍ，登録装置２２０−ｕ，検索装置２５０−ｕ及び検索代行装置２３０が、公開パラメータmpkを用いた処理が可能なように構成される。また、管理装置２１０−ｍ及び登録装置２２０−ｕが階層フォーマットξ→に従った処理が可能なように構成される。
【０１８４】
管理装置２１０−１（図１２Ａ）の管理者秘密鍵格納部２１４−１には、有限体Fqの任意の元である管理者秘密鍵ax∈Fqが安全に格納されているものとする。
【０１８５】
登録装置２２０−ｕ（図１３）の登録キーワード格納部１２３ｂ−ｕには、登録を行う検索対象情報TAR(indt)の暗号文CT(TAR(indt))と検索対象情報TAR(indt)に対応するキーワード（登録キーワード）WT(indt)とが格納されている。さらに、登録装置２２０−ｕの属性格納部２２３ａ−ｕには、登録装置２２０−ｕを利用するユーザの属性を表す情報（以下、単に「属性」という）が格納されている。ユーザの属性の例は、ユーザが所属するグループを表す情報（会社名、所属部門、課、担当、グループなど）、住所、年齢、職業、趣味などである。
【０１８６】
検索装置２５０−ｕ（図６）の検索対象情報復号鍵格納部１５４−ｕには、登録装置２２０−ｕ（図１３）の登録キーワード格納部１２３ｂ−ｕに格納された暗号文CT(TAR(indt))を復号するための検索対象情報復号鍵Key(indt)が格納されている。
【０１８７】
＜ユーザ登録＞
ユーザ登録では、管理装置２１０−ｍが登録ユーザの属性に対して設定されたベクトル(v1→,...,vM→)に対応する鍵情報kM*を生成する。鍵情報kM*の生成方式は大きく分けて２通り存在する。
【０１８８】
一つ目の方式は、管理装置２１０−１が前述の［階層的内積述語暗号方式の基本構成］のGenKeyのみに従って鍵情報kM*を生成する方式である（一括方式）。このような方式は小規模グループに適したものであるといえる。二つ目の方式は、管理装置２１０−１が前述のGenKeyに従い、その他の管理装置２１０−（ｍ’＋１）が前述のDelegate(m')に従い、鍵情報kM*を生成する方式である（委託方式）。このような方式は階層化された大規模グループに適したものであるといえる。
【０１８９】
［一括方式］
図１６は、一括方式によって鍵情報kM*を生成する処理を説明するためのフローチャートである。
【０１９０】
一括方式では、最も強い権限をもつｍ＝１に対応する管理者の管理装置２１０−１のみによって鍵情報kM*を生成する。
【０１９１】
まず、管理装置２１０−１（図１２Ａ）の入力部２１１−１に登録ユーザの属性ATTが入力される。属性ATTはM層ATT1,...,ATTMに階層化されている。各層に対応する属性ATTmを部分属性と呼ぶことにし、小さいmに対応する部分属性ATTmほど上位の属性を表すものとする。例えば、M=2の場合、属性ATTは2層の部分属性ATT1及びATT2からなり、この場合の部分属性の例は、
ATT1=（○○株式会社，○○部門）              …(81)
ATT2=（○○課，○○担当，○○グループ）      …(82)
である（ステップＳ２０１）。
【０１９２】
入力された属性ATTはベクトル設定部２１６ａ−１に入力される。ベクトル設定部２１６ａ−１は、階層フォーマットξ→及びシステム内で定められた規則に従って属性ATTに対応するベクトル(v1→,...,vM→)を設定する。例えば、ベクトル設定部２１６ａ−１は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、属性ATTを表すベクトル(w1→,...,wM→)を式(41)に従って設定し、内積wω→・vω→=0Fとなる式(42)に従ったベクトル(v1→,...,vM→)を属性ATTに対応するベクトルとする。式(81)(82)の例を用いて説明すると、例えば、ベクトル設定部２１６ａ−１は、部分属性ATT1を「○○株式会社」を表すw1及び「○○部門」を表すw2を要素とする２次元のベクトル
w1→=(w1,w2)          …(83)
に変換し、部分属性ATT2を「○○課」を表すw3、「○○担当」を表すw4、及び「○○グループ」を表すw5を要素とする３次元のベクトル
w2→=(w3,w4,w5)          …(84)
に変換し、属性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→)は鍵情報生成部２１６ｂ−１に入力される。鍵情報生成部２１６ｂ−１は、マスタ秘密鍵格納部２１３−１からマスタ秘密鍵MSKを読み出し、m=Mとした前述のGenKeyに従い、ベクトル(v1→,...,vM→)に対応する鍵情報kM*を生成する。例えば、鍵情報生成部２１６ｂ−１は、m=Mとした式(43)-(46)に従って鍵情報kM*を生成する。生成された鍵情報kM*は出力部２１２−１に送られる（ステップＳ２０３）。
【０１９４】
また、検索者鍵生成部２１６ｃ−１が、有限体Fqから任意の元を選択し、それを登録ユーザの検索者鍵sxu∈Fqとする。生成された検索者鍵sxuは出力部２１２−１及び補間鍵生成部２１６ｄ−１に送られる（ステップＳ２０４）。
【０１９５】
検索者鍵sxuが送られた補間鍵生成部２１６ｄ−１は、管理者秘密鍵格納部２１４−１から管理者秘密鍵axを抽出し、当該検索者鍵sxuと管理者秘密鍵axとの組の像である補間鍵ckuを生成する。例えば、補間鍵生成部２１６ｄ−１は、
【０１９６】
【数２７】
0005400809.tif 000030
によって補間鍵ckuを生成する。生成された補間鍵ckuは出力部２１２−１に送られる（ステップＳ２０５）。
【０１９７】
出力部２１２−１は、鍵情報kM*（M≦d-1）及び検索者鍵sxuを出力する。鍵情報kM*は登録ユーザが使用する検索装置２５０−ｕ（図６）の入力部１５１−ｕに入力され、鍵情報格納部２５３−ｕに格納される。検索者鍵sxuは登録ユーザが使用する登録装置２２０−ｕ（図１３）の入力部２２１−ｕに入力され、検索者鍵格納部２２３ｃ−ｕに格納される（ステップＳ１０６）。
【０１９８】
また、出力部２１２−１（図１２Ａ）は、補間鍵ckuを出力する。補間鍵ckuは検索代行装置２３０（図１４Ａ）の入力部２３１に入力され、登録ユーザに対応付けられて補間鍵格納部２３３に格納される（ステップＳ２０７）。
【０１９９】
［委託方式］
図１７及び１８は、委託方式によって鍵情報kM*を生成する処理を説明するためのフローチャートである。
【０２００】
委託方式では、最も強い権限をもつｍ＝１に対応する管理者の管理装置２１０−１が前述のGenKeyに従って鍵情報k1*を生成し、上位階層の鍵情報を受け取った下位階層の管理者の管理装置２１０−（ｍ’＋１）が前述のDelegate(m')に従って鍵情報を生成していき、最終的に鍵情報kM*が生成される。
【０２０１】
まず、管理装置２１０−１（図１２Ａ）の入力部２１１−１に登録ユーザの部分属性ATT1が入力される（ステップＳ２１１）。
【０２０２】
入力された部分属性ATT1はベクトル設定部２１６ａ−１に入力される。ベクトル設定部２１６ａ−１は、階層フォーマットξ→及びシステム内で定められた規則に従って部分属性ATT1に対応するベクトルv1→を設定する。例えば、ベクトル設定部２１６ａ−１は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、部分属性ATT1を表すベクトルw1→を式(41)に従って設定し、内積w1→・v1→=0Fとなる式(42)に従ったベクトルv1→を部分属性ATT1に対応するベクトルとする。式(81)(82)の例を用いて説明すると、例えば、ベクトル設定部２１６ａ−１は、式(83)によって部分属性ATT1を表すベクトルw1→を設定し、内積w1→・v1→=0Fとなる式(84)のベクトルv1→を、部分属性ATT1に対応するベクトルとする（ステップＳ２１２）。
【０２０３】
生成されたベクトルv1→は鍵情報生成部２１６ｂ−１に入力される。鍵情報生成部２１６ｂ−１は、マスタ秘密鍵格納部２１３−１からマスタ秘密鍵MSKを読み出し、m=1とした前述のGenKeyに従い、ベクトルv1→に対応する鍵情報k1*を生成する。例えば、鍵情報生成部２１６ｂ−１は、m=1とした式(43)-(46)に従って鍵情報k1*を生成する。生成された鍵情報k1*は出力部２１２−１に送られる（ステップＳ２１３）。
【０２０４】
また、一括方式と同じステップＳ２０４及びＳ２０５の処理が実行される。出力部２１２−１はステップＳ２０４で得られた検索者鍵sxuを出力する。検索者鍵sxuは登録ユーザが使用する登録装置２２０−ｕ（図１３）の入力部２２１−ｕに入力され、検索者鍵格納部２２３ｃ−ｕに格納される（ステップＳ２１６）。また、出力部２１２−１はステップＳ２０５で得られた補間鍵ckuを出力する。補間鍵ckuは検索代行装置２３０（図１４Ａ）の入力部２３１に入力され、登録ユーザに対応付けられて補間鍵格納部２３３に格納される（ステップＳ２０７）。さらに、出力部２１２−１はステップＳ２１３で得られた鍵情報k1*を出力する。
【０２０５】
鍵情報k1*は管理装置２１０−２に入力される。管理装置２１０−２以降では前述したDelegate(m')（m'=1,...,M-1）に従って鍵生成が行われる。以下では管理装置２１０−ｍ’から鍵情報km'*を受け取る管理装置２１０−（ｍ’＋１）の処理を一般化して説明する。
【０２０６】
まず、鍵情報km'*が管理装置２１０−（ｍ’＋１）（図１２Ｂ）の入力部２１１−（ｍ’＋１）に入力され、鍵情報生成部２１６ｂ−（ｍ’＋１）に入力される（ステップＳ２２０）。また、部分属性ATTm'+1がベクトル設定部２１６ａ−（ｍ’＋１）に入力される。ベクトル設定部２１６ａ−（ｍ’＋１）は、階層フォーマットξ→及びシステム内で定められた規則に従って部分属性ATTm'+1に対応するベクトルvm'+1→を設定する。例えば、ベクトル設定部２１６ａ−（ｍ’＋１）は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、部分属性ATTm'+1を表すベクトルwm'+1→を式(41)に従って設定し、内積wm'+1→・vm'+1→=0Fとなる式(42)に従ったベクトルvm'+1→を部分属性ATTm'+1に対応するベクトルとする。生成されたベクトルvm'+1→は鍵情報生成部２１６ｂ−（ｍ’＋１）に入力される（ステップＳ２２２）。
【０２０７】
鍵情報km'*とベクトルvm'+1→とが入力された鍵情報生成部２１６ｂ−（ｍ’＋１）は、前述のDelegate(m')に従って、ベクトル(v1→,...,vm'+1→)に対応する鍵情報km'+1*を生成する。例えば、鍵情報生成部２１６ｂ−（ｍ’＋１）は、式(47)-(50)に従って鍵情報km'+1*を生成する。生成された鍵情報km'+1*は出力部２１２−（ｍ’＋１）に送られる（ステップＳ２２３）。出力部２１２−（ｍ’＋１）は鍵情報km'+1*を出力する（ステップＳ２２８）。
【０２０８】
m'+1<Mの場合、出力された鍵情報km'+1*は下位階層の管理装置２１０−（ｍ’＋２）に入力され、m'+1を新たなm'としてステップＳ２２０−Ｓ２２８の処理が実行される。一方、m'+1=Mの場合、出力された鍵情報km'+1*=kM*は、登録ユーザが使用する検索装置２５０−ｕ（図６）の入力部１５１−ｕに入力され、鍵情報格納部２５３−ｕに格納される。
【０２０９】
＜データベース登録＞
図１９及び２０に示すように、登録ユーザは登録装置２２０−ｕを用い、以下のようにデータベース登録を行うことができる。
【０２１０】
まず、登録装置２２０−ｕ（図１３）の写像部２２６ａ−ｕが、登録キーワード格納部１２３ｂ−ｕから検索対象情報TAR(indt)に対応する登録キーワードWT(indt)を抽出する（ステップＳ２３１）。また、乱数生成部２２６ｂ−ｕが、キーワードWT(indt)に対して有限体Fqの任意の元である選択値rWT(indt)∈Fqを選択する。選択値rWT(indt)は写像部２２６ａ−ｕに入力される（ステップＳ１３２）。写像部２２６ａ−ｕは、さらに検索者鍵格納部２２３ｃ−ｕから検索者鍵sxuを抽出し、WT(indt)，sxu，rWT(indt)を用いて値h(indt)を生成する（登録ユーザの検索者鍵sxuの像である第１値h(indt)）。例えば、写像部２２６ａ−ｕは、入力値に対して巡回群G1の元を出力する擬似ランダム関数Hσを用い、
【０２１１】
【数２８】
0005400809.tif 000031
で表される値h(indt)を生成する。なお、どのような擬似ランダム関数Hσを用いてもかまわないが、例えば、鍵付きハッシュ関数を擬似ランダム関数Hσとして用いることができる（ステップＳ２３３）。生成された値h(indt)は出力部１２２−ｕ及びタグ情報生成部２２６ｇ−ｕに送られる。出力部１２２−ｕは値h(indt)を出力する（ステップＳ２３４）。
【０２１２】
登録装置２２０−ｕから出力された値h(indt)は、検索代行装置２３０（図１４Ａ）の入力部２３１に入力され、写像部２３６に送られる。写像部２３６は、補間鍵格納部２３３から登録装置２２０−ｕを利用する登録ユーザに対応する補間鍵ckuを抽出する。写像部２３６は、当該値h(indt)と補間鍵ckuとの組の像である値e^(indt)を生成する。例えば、写像部２３６は、当該値h(indt)と補間鍵ckuとの組に式(4)の双線形写像Pairを施して値e^(indt)を生成する。すなわち、
e^(indt)=Pair(h(indt),cku)∈GT          …(87)
で表される値e^(indt)を生成する（ステップＳ２３５）。値e^(indt)は出力部２３２送られ、出力部２３２は値e^(indt)を出力する（ステップＳ２３６）。
【０２１３】
検索代行装置２３０から出力された値e^(indt)は、登録装置２２０−ｕ（図１３）の入力部２２１−ｕに入力され、写像部２２６ｄ−ｕに送られる。写像部２２６ｄ−ｕは値e^(indt)の像である値r'(indt)を生成する。例えば、まず乱数生成部１２６ｃ−ｕが巡回群GTの任意の元RE(indt)=LR(indt)を生成して写像部２２６ｄ−ｕ及びタグ情報生成部２２６ｇ−ｕに送り（ステップＳ２３７）、写像部２２６ｄ−ｕが、
r'(indt)＝RE(indt)・e^(indt)          …(88)
で表される値r'(indt)を生成する。値r'(indt)は暗号化部２２６ｆ−ｕに送られる（ステップＳ２３８）。
【０２１４】
また登録装置２２０−ｕ（図１３）のベクトル設定部２２６ｅ−ｕは、属性格納部２２３ａ−ｕから登録ユーザの属性ATTを抽出する。この属性ATTは当該登録ユーザのユーザ登録時に用いられたものと同じである。ベクトル設定部２２６ｅ−ｕは、階層フォーマットξ→及びシステム内で定められた規則に従って属性ATTを表すベクトル(w1→,...,wM→)を設定する。当該ベクトル(w1→,...,wM→)とユーザ登録時のステップＳ２０２で設定されたベクトル(v1→,...,vM→)とは、ω=1,...,Mについて内積wω→・vω→=0Fを満たす。生成されたベクトル(w1→,...,wM→)は暗号化部２２６ｆ−ｕに送られる（ステップＳ２４０）。  ベクトル設定部２２６ｅ−ｕが、第１実施形態のステップＳ１０２と同様に、補集合CSET(indt)に対応するベクトルwCSET→∈Fqを設定する。ベクトルwCSET→は暗号化部２２６ｆ−ｕに入力される。
【０２１５】
暗号化部２２６ｆ−ｕは、第１暗号方式に則ってベクトルw1→,...,wM→,wCSET→に対応する第１暗号文(T(indt,1),…,T(indt,N))を生成する。本形態の暗号化部２２６ｆ−ｕは、(w1→,...,wM→,wCSET→)=(w1→,...,wm→)とした式(51)に従って、以下のような第１暗号文(T(indt,1),…,T(indt,N))を生成する。
【０２１６】
C1=(T(indt,1),…,T(indt,N))∈G1n+3          …(89)
ただし、この例ではN=n+3である（ステップＳ２４３）。
【０２１７】
暗号化部２２６ｆ−ｕは、gTτ・υ1を共通鍵Kとし、第２暗号方式に則って値r'(indt)を暗号化した暗号文T(indt)を生成する。例えば、暗号化部２２６ｆ−ｕは、mes=r'(indt)とした式(52)に従い、以下のように暗号文T(indt)を生成する。
【０２１８】
C2=T(indt)=gTτ・υ1・r'(indt)∈GT          …(90)
このように生成された(T(indt,1),…,T(indt,N))及びT(indt)は、タグ情報生成部２２６ｇ−ｕに送られる（ステップＳ２４４）。
【０２１９】
タグ情報生成部２２６ｇ−ｕは、(T(indt,1),…,T(indt,N))、T(indt)、h(indt)及びRE(indt)を互いに対応付けた否定タグ情報Tag(indt)を以下のように生成する。
【０２２０】
Tag(indt)=((T(indt,1),…,T(indt,N)), T(indt), h(indt), RE(indt))  …(91)
否定タグ情報Tag(indt)は出力部１２２−ｕに送られる（ステップＳ２４５）。
【０２２１】
また、ベクトル設定部２２６ｅ−ｕは、第１実施形態のステップＳ１０６と同様に、検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応する登録キーワードWT(indt)に対応するベクトルwT→∈Fqを設定する。ベクトルwT→は暗号化部２２６ｆ−ｕに入力される。
【０２２２】
暗号化部２２６ｆ−ｕは、第１暗号方式に則ってベクトルw1→,...,wM→,wT→に対応する第２暗号文(LT(indt,1),…,LT(indt,N))を生成する。本形態の暗号化部２２６ｆ−ｕは、(w1→,...,wM→,wT→)=(w1→,...,wm→)とした式(51)に従って、以下のように第２暗号文(LT(indt,1),…,LT(indt,N))を生成する。
【０２２３】
C1=(LT(indt,1),…,LT(indt,N))∈G1n+3          …(92)
ただし、この例ではN=n+3である（ステップＳ２４７）。
【０２２４】
暗号化部２２６ｆ−ｕは、gTτ・υ1を共通鍵Kとし、第２暗号方式に則って値r'(indt)を暗号化した暗号文LT(indt)を生成する。例えば、暗号化部２２６ｆ−ｕは、mes=r'(indt)とした式(52)に従い、以下のように暗号文LT(indt)を生成する。
【０２２５】
C2=T(indt)=gTτ・υ1・r'(indt)∈GT          …(93)
このように生成された(LT(indt,1),…, LT(indt,N))及びLT(indt)は、タグ情報生成部２２６ｇ−ｕに送られる（ステップＳ２４８）。
【０２２６】
タグ情報生成部２２６ｇ−ｕは、(LT(indt,1),…,LT(indt,N))、LT(indt)、h(indt)及びLR(indt)を互いに対応付けた肯定タグ情報LTag(indt)を以下のように生成する。
【０２２７】
LTag(indt)=((LT(indt,1),…,LT(indt,N)), LT(indt), h(indt), LR(indt))  …(94)
否定タグ情報Tag(indt)は出力部１２２−ｕに送られる（ステップＳ２４９）。
【０２２８】
出力部１２２−ｕには、さらに前述の否定タグ情報LTag(indt)、及び登録キーワード格納部１２３ｂ−ｕから読み出された検索対象情報TAR(indt)の暗号文CT(TAR(indt))が送られる。出力部１２２−ｕは、CT(TAR(indt))、LTag(indt)及びLTag(indt)を出力する（ステップＳ２５０）。
【０２２９】
CT(TAR(indt))、LTag(indt)及びLTag(indt)はストレージ装置（図１４Ｂ）の入力部１４１に入力される。書込み部２４６はCT(TAR(indt))、LTag(indt)及びLTag(indt)を互いに対応付け、図１５Ａ及びＢに示したように暗号化データベース格納部２４３に格納する（ステップＳ２５１）。
【０２３０】
＜バッチ検索用の事前計算＞
検索代行装置２３０（図１４Ａ）の検証処理部２３７は、後述するバッチ検索のために以下のような事前計算を行う。この事前計算は定期的に行われてもよいし、暗号化データベース格納部２４３が更新されるたびに行われてもよい。或いは、暗号化データベース格納部２４３の更新後に後述するバッチ検索が始めて実行されるときに行われてもよい。以下ではストレージ装置２４０の暗号化データベース格納部２４３に、indt=1,…,maxt(maxt≧2)についてのCT(TAR(indt))及びTag(indt)が互いに対応付けられて格納されていることを前提とする（図１５Ａ参照）。
【０２３１】
検証処理部２３７は、ストレージ装置２４０にアクセスし、暗号化データベース格納部２４３を用いて以下の処理を行う。検証処理部２３７は、まずsub={1,…,maxt}とし、indN=1,…,Nについて前述の式(71)-(73)及び以下の式(95)(96)を事前計算し、BT(indN)(indN=1,…,N)、BT、RE、h、e^をsubに対応付けて暗号化データベース格納部２４３に格納する。
【０２３２】
【数２９】
0005400809.tif 000032
同様にsubを分割して得られるsubの真部分集合のそれぞれを新たなsubとし、indN=1,…,Nについて式(71)-(73)(95)(96)が事前計算され、BT(indN)(indN=1,…,N)、BT、RE、h、e^がsubに対応付けられて暗号化データベース格納部２４３に格納される処理が繰り返される。subの分割方法や分割回数は、第１実施形態と同様、検索代行装置２３０で事前に定められる。
【０２３３】
＜検索＞
登録ユーザは検索装置２５０−ｕ（図６）を用い、以下のように検索を行う。
【０２３４】
図２１に示すように、まず第１実施形態で説明したステップＳ１２１及びＳ１２２の処理が実行される。否定タグ情報Tag(indt)及び肯定タグ情報LTag(indt)のそれぞれに設定された第２ベクトルvQ→は検索クエリ生成部２５７−ｕに送られる。検索クエリ生成部２５７−ｕは、鍵情報格納部２５３−ｕから鍵情報kM*を抽出する。検索クエリ生成部２５７−ｕは、kM*と否定タグ情報Tag(indt)に設定されたvQ→とを用い、m'=Mとした前述のDelegate(m')によって、ベクトルv1→,...,vM→及びvM+1→=vQ→に対応する鍵情報（復号鍵）kM+1*である検索クエリQUE(Tag)を生成する。また検索クエリ生成部２５７−ｕは、kM*と肯定タグ情報LTag(indt)に設定されたvQ→とを用い、m'=Mとした前述のDelegate(m')によって、ベクトルv1→,...,vM→及びvM+1→=vQ→に対応する鍵情報（復号鍵）kM+1*である検索クエリQUE(LTag)を生成する。これらは例えば、m'=M（M≦d-1）とした式(47)-(50)に従ってそれぞれ生成できる。ただし、m=d-1の場合には式(50)のkm'+1,α*を含まない。
【０２３５】
Tag(indt)=(que1,…,queN)∈G2n+3          …(97)
LTag(indt)=(Lque1,…,LqueN)∈G2n+3       …(98)
ただし、この例ではn+3=Nである（ステップＳ２５３）。
【０２３６】
生成された検索クエリQUE(Tag)及びQUE(LTag)は出力部１５２−ｕに送られ、出力部１５２−ｕはこれらを出力する（ステップＳ１２４）。
【０２３７】
図９に示すように、検索クエリQUE(Tag)及びQUE(LTag)は、検索代行装置２３０（図１４Ａ）の入力部２３１に入力され、検証処理部２３７及び制御部２３５に送られる（ステップＳ２６１）。制御部２３５は、補間鍵格納部２３３を参照し、検索クエリQUE(Tag)及びQUE(LTag)に対応する登録ユーザの補間鍵ckuが利用可能であるかを検証する。検索クエリQUE(Tag)及びQUE(LTag)に対応する登録ユーザの補間鍵ckuが利用可能でない場合とは、検索クエリQUE(Tag)及びQUE(LTag)に対応する登録ユーザの補間鍵ckuが補間鍵格納部２３３に格納されていない場合や、補間鍵格納部２３３に格納された補間鍵ckuの使用が禁止されている場合である（ステップＳ２７１）。
【０２３８】
ここで、検索クエリQUE(Tag)及びQUE(LTag)に対応する登録ユーザの補間鍵ckuが利用可能でない場合には、出力部２３２が「該当なし」を表す⊥を出力して処理を終了する（ステップＳ２７２）。
【０２３９】
一方、検索クエリQUE(Tag)及びQUE(LTag)に対応する登録ユーザの補間鍵ckuが利用可能である場合には、制御部２３５は、まずsub={1,…,maxt}とする（ステップＳ２６２）。検索代行装置２３０はストレージ装置２４０（図１４Ｂ）にアクセスし、入力部２３１，１４１、出力部２３２、１４２、及び読み書き部２４６を通じ、暗号化データベース格納部２４３に格納されたデータにアクセス可能な状態とされる。検索代行装置２３０（図１４Ａ）の検証処理部２３７は、否定タグ情報Tag(indt)に対する検索クエリQUE(Tag)を用い、暗号化データベース格納部２４３に格納された否定タグ情報Tag(inds)(inds∈sub)をまとめてバッチ検証する。すなわち、検索クエリQUE(Tag)を用い、inds∈sub⊆{1,…,maxt}についての第１暗号文(T(inds,1),…,T(inds,N))の合成値（式(71)）が正しく復号できるかを判定する。具体的には本形態の検証処理部２３７は、検索クエリQUE(Tag)を復号鍵として用い、inds∈subについての第１暗号文(T(inds,1),…,T(inds,N))の関数値(BT(1),…,BT(N))（式(71)）を第１暗号方式に則って復号して得られる値を共通鍵とし、inds∈subについての暗号文T(inds)の関数値BT（式(72)）を第２暗号方式に則って復号して得られる値が、inds∈subについての復号値RE(inds)の関数値RE（式(73)）とe^（式(96)）とについてe^・REとなるか（true）否か（false）を判定する。例えば、式(89)(90)のような計算で否定タグ情報Tag(inds)が得られたのであれば、検証処理部２３７は、以下を満たすか（true）否か（false）を判定する。
【０２４０】
【数３０】
0005400809.tif 000033
原則、この判定を行うために必要な(BT(1),…,BT(N))、BT、e^及びREは、前述の事前計算で得られたものである。ただし、必要な(BT(1),…,BT(N))、BT、e^及びREが格納されていないのであれば、検証処理部２３７はそれらを計算してこの判定を行い、以降の処理のためにそれらの値を暗号化データベース格納部２４３に格納しておいてもよい（ステップＳ２６３）。
【０２４１】
ステップＳ２６３の判定でtrueと判定された場合には（ステップＳ２６４）、inds∈subに対応する各検索対象情報TAR(inds)に対する検索が終了し、ステップＳ２６９へ進む。一方、ステップＳ２６３の判定でfalseと判定された場合(inds∈sub⊆{1,…,maxt}についての第１暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できないと判定された場合)には（ステップＳ２６４）、ステップＳ２６５に進み、subの要素数が基準値以下であるかが判定される（ステップＳ２６５）。
【０２４２】
ステップＳ２６５でsubの要素数が基準値以下ではないと判定された場合には、subを分割して得られるsubの真部分集合のそれぞれを新たなsubとし、ステップＳ２６３に戻る。なお、ここでのsubの分割方法は、例えば前述のバッチ検索用の事前計算でのsubの分割方法と同一とする（ステップＳ２６６）。
【０２４３】
一方、ステップＳ２６５でsubの要素数が基準値以下であると判定された場合、検索クエリQUE(LTag)を用いた肯定タグ情報LTag(indt)の検証に切り替えられる。すなわち、検証処理部２３７が検索クエリQUE(LTag)（第２検索クエリ）を復号鍵として用い、第２暗号文(LT(inds,1),…,LT(inds,N))（inds∈sub）が正しく復号できるかを判定する。本形態の検証処理部２３７は検索クエリQUE(LTag)を復号鍵として用い、肯定タグ情報LTag(indt)が含む第２暗号文(LT(inds,1),…,LT(inds,N))（inds∈sub）（図１５Ｂ）を第１暗号方式に則って復号して得られる値を共通鍵とし、暗号文LT(inds)を第３暗号方式に則って復号して得られる値がPair(h,cku)・LR(inds)であるかを判定する。例えば、式(89)(90)のような計算で肯定タグ情報LTag(inds)が得られたのであれば、検証処理部２３７は、以下を満たすか（true）否か（false）を判定する。
【０２４４】
【数３１】
0005400809.tif 000034
これは、肯定タグ情報LTag(inds)に対応する登録キーワードが検索クエリQUE(LTag)に対応する検索用キーワードにヒットするか（true）否か（false）を肯定タグ情報LTag(inds)ごとに判定することに相当する（ステップＳ２６７）。
【０２４５】
検証処理部２３７は、ステップＳ２６７の判定でtrueとされた肯定タグ情報LTag(inds)のindsに対応する暗号文CT(TAR(inds))を集合HITに追加し、図示しないメモリに格納し（ステップＳ２６８）、ステップＳ２６９に進む。
【０２４６】
ステップＳ２６９では、検証処理部２３７が未検証のsubが存在するかを判定する（ステップＳ２６９）。ここで、未検証のsubが存在すると判定された場合には、ステップＳ２６３に進む。一方、未検証のsubが存在しないと判定された場合には、検証処理部２３７は、集合HITの要素である暗号文CT(TAR(indt))を出力する。集合HITの要素が存在しなければ、検証処理部２３７はヒットしなかったことを表す⊥を出力する（ステップＳ２７０）。これらは出力部２３２から出力される。その後、第１実施形態で説明したステップＳ１２５及びＳ１２６の処理が実行される。
【０２４７】
〔各実施形態の特徴〕
上述の方法により、検索処理回数を大幅に削減できる。例えば、maxt個の検索対象情報TAR(indt)に対応する暗号化データベースを検索する場合、従来法であれば最大maxt回の判定処理が必要であったが、上述の方法でsubを2個に分割して新たなsubとする場合にはlog2 maxt回程度の判定処理でよい。
【０２４８】
〔変形例〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、第１実施形態では、具体例として単一単語一致検索や部分集合判定検索を行う場合を例示したが、非特許文献１,２に開示されたようなその他の検索方式を用いる場合に本発明が適用されてもよい。また、上記の各実施形態では、内積述語暗号方式や階層的内積述語暗号方式で鍵カプセル化メカニズムKEMを構成する場合のタグ情報の生成方法や検証方法を例示したが、これは本発明を限定するものではない。例えば、式(65)の第１暗号文(T(indt,1),…,T(indt,N))とgTτ・υ1との組が否定タグ情報とされてもよい。肯定タグ情報についても同様な変形が可能である。
【０２４９】
上記の各実施形態では、否定タグ情報を用いたバッチ検索処理でsubの要素数が基準値以下にまで絞り込んでから、肯定タグ情報を用いた個別の検索処理を行った。しかし肯定タグ情報を用いた個別の検索処理を行うことなく、否定タグ情報のみを用いて検索が行われてもよい。この場合には肯定タグ情報や第２暗号化データベースの生成やそれに対応する検索クエリを生成する必要はない。
【０２５０】
上記実施形態で説明した階層的内積述語暗号方式の基本構成ではζ=3の場合を例示した。しかし、ζがその他の１以上の整数であってもよい。マスタ秘密鍵MSKが含む基底ベクトルをζについて一般化すると(b1*,...,bn*,bn+1*,...,bn+ζ*)となり、公開パラメータmpkが含む基底ベクトルをζについて一般化すると(b1,...,bn,bn+1,...,bn+ζ)となる。前述した式(44)-(46),(51)(52)(54)をζについてそれぞれ一般化すると、例えば、以下のようになる。
【０２５１】
【数３２】
0005400809.tif 000035
ただし、φω,0，φω,αは有限体Fqから選択された任意の元であり、Ωは0以上ζ以下の整数である。また、有限体Fqの元である定数constに対して以下を満たす。定数constの具体例は1Fである。
【０２５２】
【数３３】
0005400809.tif 000036
【数３４】
0005400809.tif 000037
ただし、υωは有限体Fqから選択された任意の元である。
【０２５３】
C2=gTτ・υ・const・mes
【０２５４】
【数３５】
0005400809.tif 000038
また、上述した有限体上の元や演算が有限環上の元や演算に置換された構成でもよい。また、登録装置と検索装置とが一体であってもよいし、検索代理装置とストレージ装置とが一体であってもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０２５５】
〔プログラム等〕
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０２５６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０２５７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０２５８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０２５９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０２６０】
１，２  検索可能暗号システム
１１０，２１０−ｍ  管理装置
１２０−ｕ，２２０−ｕ  登録装置
２３０  検索代行装置
１４０，２４０  ストレージ装置
１５０−ｕ，２５０−ｕ  検索装置
【図１】
0005400809.tif 000040
【図２】
0005400809.tif 000041
【図３】
0005400809.tif 000042
【図４】
0005400809.tif 000043
【図５】
0005400809.tif 000044
【図６】
0005400809.tif 000045
【図７】
0005400809.tif 000046
【図８】
0005400809.tif 000047
【図９】
0005400809.tif 000048
【図１０】
0005400809.tif 000049
【図１１】
0005400809.tif 000050
【図１２】
0005400809.tif 000051
【図１３】
0005400809.tif 000052
【図１４】
0005400809.tif 000053
【図１５】
0005400809.tif 000054
【図１６】
0005400809.tif 000055
【図１７】
0005400809.tif 000056
【図１８】
0005400809.tif 000057
【図１９】
0005400809.tif 000058
【図２０】
0005400809.tif 000059
【図２１】
0005400809.tif 000060