検索可能暗号システム、検索可能暗号方法、ストレージ装置、検索装置、及び登録者装置
【課題】キーワードの暗号文を含むデータベースを検索する権限が付与された登録ユーザの検索権限を失効させることが可能なシステムを提供する。
【解決手段】ストレージ装置にタグ情報を含む暗号化データベースが格納される。タグ情報は、登録ユーザの属性及びキーワードに対応するベクトルに対応する暗号文と登録ユーザの検索者鍵の像である第１値とを含む。この暗号文は第１値と登録ユーザの補間鍵との組の像である第２値を暗号化した暗号文である。検索装置は、登録ユーザの属性及び検索キーワードに対応するベクトルに対応する復号鍵である検索クエリを生成する。検索代行装置は、登録ユーザの補間鍵を格納し、検索クエリを復号鍵として暗号化データベースのタグ情報に含まれる暗号文を復号して得られる復号値が、当該タグ情報に含まれる第１値と当該補間鍵格納部に格納された補間鍵との組に対応するかを検証する。
【解決手段】ストレージ装置にタグ情報を含む暗号化データベースが格納される。タグ情報は、登録ユーザの属性及びキーワードに対応するベクトルに対応する暗号文と登録ユーザの検索者鍵の像である第１値とを含む。この暗号文は第１値と登録ユーザの補間鍵との組の像である第２値を暗号化した暗号文である。検索装置は、登録ユーザの属性及び検索キーワードに対応するベクトルに対応する復号鍵である検索クエリを生成する。検索代行装置は、登録ユーザの補間鍵を格納し、検索クエリを復号鍵として暗号化データベースのタグ情報に含まれる暗号文を復号して得られる復号値が、当該タグ情報に含まれる第１値と当該補間鍵格納部に格納された補間鍵との組に対応するかを検証する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化されたデータベースの検索が可能な検索可能暗号技術に関する。
【背景技術】
【０００２】
暗号化文書からあらかじめキーワードを抽出し、それらのキーワードの暗号文を含むデータベースを構成し、各キーワードが暗号化されたままの状態で部分一致検索を行って検索結果を得る検索可能暗号方式が非特許文献１，２に開示されている。非特許文献１，２では、暗号化条件や復号条件を述語論理で記述することが可能な述語暗号（例えば、非特許文献３から５参照）を利用して検索可能暗号方式を実現している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】R. Yoshida, S. Oda, and T. Kobayashi., "Public-key encryption with partial matching keyword search," In Symp. on Cryptography and Information Security, 2010.
【非特許文献２】N. Matsuda, M. Hattori, T. Ito, and T. Yoneda., "Secure data center systems with hierarchical predicate encryption," In Symp. on Cryptography and Information Security, 2010.
【非特許文献３】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.
【非特許文献４】J. Katz, A. Sahai, and B. Waters., "Predicate encryption supporting disjunctions, polynomial equations, and inner products," In EUROCRYPT, pp. 146-162, 2008.
【非特許文献５】T. Okamoto and K. Takashima., "Hierarchical predicate encryption for inner-products," In ASIACRYPT, pp. 214-231, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の方式では、キーワードの暗号文を含むデータベースを利用する権限が付与された登録ユーザの利用権限を失効させることが困難であった。
【０００５】
本発明はこのような点に鑑みてなされたものであり、キーワードの暗号文を含むデータベースを利用する権限が付与された登録ユーザの利用権限を失効させることが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のストレージ装置には、検索対象情報に対応するタグ情報を含む暗号化データベースが格納される。タグ情報は、第１ベクトルに対応する暗号文cと登録ユーザの検索者鍵sxuの像である第１値hとを含む。また、第１ベクトルは、登録ユーザの属性に対して設定されたベクトルと検索対象情報のキーワードに対して設定されたベクトルとを含み、暗号文cが第１値hと登録ユーザの補間鍵ckuとの組の像である第２値r'を或る暗号方式に則って暗号化した暗号文である。この暗号方式は、暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な方式である。
【０００７】
本発明の検索装置は、第２ベクトルに対応する復号鍵である検索クエリを上記暗号方式に則って生成する。第２ベクトルは、登録ユーザの属性に対応するベクトルと検索キーワードに対応するベクトルとを含む。
【０００８】
検索代行装置は、登録ユーザの補間鍵ckuを格納し、検索クエリを復号鍵として暗号化データベースのタグ情報に含まれる暗号文cを復号して得られる復号値mes'が、当該タグ情報に含まれる第１値hと当該補間鍵格納部に格納された補間鍵ckuとの組に対応するかを検証する。
【発明の効果】
【０００９】
本発明では、タグ情報が補間鍵ckuを用いて生成され、検索クエリを復号鍵としてタグ情報に含まれる暗号文cを復号して得られる復号値mes'が第１値hと補間鍵ckuとの組に対応することを検証することで、検索クエリに対して検索対象情報のキーワードがヒットしたか否かを判定できる。一方、検索代行装置による登録ユーザの補間鍵ckuの利用が禁止された場合、タグ情報の生成や検証ができなくなる。これにより、キーワードの暗号文を含むデータベースを利用する権限が付与された登録ユーザの利用権限を失効させることができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施形態の検索可能暗号システムの全体構成を説明するための図である。
【図２】図２Ａは、実施形態の管理装置の機能構成を説明するための図であり、図２Ｂは、実施形態の管理装置の機能構成を説明するための図である。
【図３】図３は、実施形態の登録装置の機能構成を説明するための図である。
【図４】図４は、実施形態の検索代行装置の機能構成を説明するための図である。
【図５】図５Ａは、実施形態のストレージ装置の機能構成を説明するための図である。図５Ｂは、暗号化データベース格納部に格納される暗号化データベースのデータ構成を説明するための図である。
【図６】図６は、実施形態の検索装置の機能構成を説明するための図である。
【図７】図７は、一括方式によって鍵情報kM*を生成する処理を説明するためのフローチャートである。
【図８】図８は、委託方式によって鍵情報kM*を生成する処理を説明するためのフローチャートである。
【図９】図９は、委託方式によって鍵情報kM*を生成する処理を説明するためのフローチャートである。
【図１０】図１０は、データベース登録の処理を説明するためのフローチャートである。
【図１１】図１１は、検索処理を説明するためのフローチャートである。
【図１２】図１２は、登録失効処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施形態を説明する。
【００１２】
〔概要〕
以下に説明する各実施形態では、関数暗号方式を用いて検索可能暗号方式を構成する。関数暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。関数暗号方式の例は、非特許文献１から５などに開示されている内積述語暗号方式や階層的内積述語暗号方式などの述語暗号方式や、参考文献１「T. Okamoto, K. Takashima, "Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption," Advances in Cryptology - CRYPTO 2010, Lecture Notes in Computer Science, 2010, Volume 6223/2010, 191-208」などに開示されている方式などである。すなわち、関数暗号方式には、内積述語暗号方式や階層的内積述語暗号方式などの述語暗号方式が含まれる。また、本発明で利用する関数暗号方式は非特許文献１から５や参考文献１に開示された方式に限定されず、どのような方式が用いられてもよい。
【００１３】
各実施形態の検索可能暗号方式では、ストレージ装置の暗号化データベース格納部に、検索対象情報に対応するタグ情報を含む暗号化データベースが格納される。このタグ情報は、第１ベクトルに対応する暗号文cと登録ユーザの検索者鍵sxuの像である第１値hとを含む。第１ベクトルは、登録ユーザの属性に対して設定されたベクトルと検索対象情報のキーワードに対して設定されたベクトルとを含む。また、暗号文cは、第１値hと登録ユーザの補間鍵ckuとの組の像である第２値r'を関数暗号方式に則って暗号化した暗号文である。登録ユーザが利用する検索装置は、第２ベクトルに対応する復号鍵である検索クエリを関数暗号方式に則って生成する。この第２ベクトルは、登録ユーザの属性に対応するベクトルと検索キーワードに対応するベクトルとを含む。検索クエリは検索代行装置に送られる。検索代行装置は登録ユーザの補間鍵ckuを格納している。この検索代行装置は、検索クエリを復号鍵として暗号化データベースのタグ情報に含まれる暗号文cを復号して復号値mes'を得る。検索代行装置は、この復号値mes'がタグ情報に含まれる第１値hと補間鍵ckuとの組に対応するかを検証する。ここで、復号値mes'がタグ情報に含まれる第１値hと補間鍵ckuとの組に対応する場合、検索クエリに対してタグ情報に対応するキーワードがヒットしたことになる。これにより、登録ユーザによる暗号化データベースの検索が可能となっている。一方、検索代行装置による補間鍵ckuの利用が禁止された場合にはこのような判定ができず、利用が禁止された補間鍵ckuに対応する登録ユーザは暗号化データベースの検索を行うことができない。このように検索代行装置による補間鍵ckuの利用を禁止することにより、利用を禁止した補間鍵ckuに対応する登録ユーザの検索権限を失効させることができる。また、登録ユーザの検索権限を失効させるために暗号化データベースを変更する必要はない。
【００１４】
また、各実施形態の検索可能暗号方式では、登録ユーザが利用する登録者装置が登録ユーザの検索者鍵sxuを格納している。登録者装置は、登録ユーザの検索者鍵sxuの像である第１値hを生成し、これを検索代行装置に送る。検索代行装置は、当該検索代行装置に格納された当該登録ユーザの補間鍵ckuを用い、第１値hと補間鍵ckuとの組の像である第３値e^を生成する。第３値e^は登録者装置に送られる。登録者装置は、第３値e^の像である第２値r'を生成し、前述の第１ベクトルを用いて関数暗号方式に則って第２値r'を暗号化して暗号文cを生成し、暗号文cと第１値hとを含むタグ情報を生成する。実施形態では、登録者装置に格納された検索者鍵sxuと検索代行装置に格納された補間鍵ckuとを用いてタグ情報が生成されるため、登録者装置や検索代行装置が単独で正しいタグ情報を生成することができない。これにより、登録者装置や検索代行装置が単独に不正なタグ情報を生成する事態を抑制できる。さらに、検索代行装置による補間鍵ckuの利用を禁止することにより、利用を禁止した補間鍵ckuに対応する登録ユーザのタグ情報の生成権限を失効させることもできる。
【００１５】
なお、検索権限やタグ情報の生成権限を失効させる場合には、例えば、管理装置が失効させる登録ユーザを示す失効情報を検索代行装置に入力する。失効情報が入力された検索代行装置は、当該失効情報が示す登録ユーザに対応する補間鍵ckuの検索代行装置での使用を禁止する。これにより、当該登録ユーザの検索権限やタグ情報の生成権限が失効する。
【００１６】
また、各実施形態の検索可能暗号方式では、管理者秘密鍵axが管理者装置に格納されている。管理者秘密鍵axは補間鍵ckuや検索者鍵sxuが生成される前に生成された情報である。登録ユーザに対応する補間鍵ckuは、当該登録ユーザに対応する検索者鍵sxuと管理者秘密鍵axとの組の像である。これにより、登録者装置に格納された検索者鍵sxuから補間鍵ckuが推測されることを防止できるとともに、検索代行装置に格納された補間鍵ckuから検索者鍵sxuが推測されることを防止できる。
【００１７】
〔実施形態〕
次に、本発明の実施形態を説明する。本形態では、関数暗号方式として階層的内積述語暗号方式を用いる。
【００１８】
＜定義＞
まず、本形態で使用する用語や記号を定義する。
【００１９】
行列：「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
(・)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は、
【００３９】
【数１】
となる。
【００４０】
A*：基底ベクトルai*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルai*(i=1,...,n+ζ)が式(9)によって表現される場合、行列A*は、
【００４１】
【数２】
となる。
【００４２】
X：有限体Fqの元を要素とするn+ζ行n+ζ列の行列を表す。基底ベクトルaiの座標変換に用いられる。行列Ｘのi行j列(i=1,...,n+ζ,j=1,...,n+ζ)の要素をχi,j∈Fqとすると、行列Xは、
【００４３】
【数３】
となる。なお、行列Ｘの各要素χi,jを変換係数と呼ぶ。
【００４４】
X *：X *は行列Xの逆行列の転置行列Ｘ*=(Ｘ-1)Tを表す。基底ベクトルai*の座標変換に用いられる。行列X*のi行j列の要素をχi,j*∈Fqとすると、行列Ｘ*は、
【００４５】
【数４】
となる。なお、行列Ｘ*の各要素χi,j*を変換係数と呼ぶ。
【００４６】
この場合、n+ζ行n+ζ列の単位行列をIとするとＸ・(Ｘ*)T=Ｉを満たす。すなわち、単位行列
【００４７】
【数５】
に対し、
【００４８】
【数６】
を満たす。ここで、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)の関係から、
【００５４】
【数７】
を満たす。特に、τ=κ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は、
【００５７】
【数８】
となる。
【００５８】
B*：B*は基底ベクトルbi*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。B*=X*・A*を満たす。例えば、基底ベクトルbi*(i=1,...,n+ζ)が式(24)によって表現される場合、行列B*は、
【００５９】
【数９】
となる。
【００６０】
〔階層的内積述語暗号方式〕
次に、階層的内積述語暗号方式について説明する。階層的内積述語暗号方式は内積述語暗号方式の一種である。内積述語暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。内積述語暗号では、内積が0となることと論理式の真理値が真となることとが等価である。
【００６１】
［内積と論理式の真理値との関係］
内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。
【００６２】
まず、「x1がη1である」という命題１と「x2がη2である」という命題２との論理和 (x1=η1)∨(x2=η2)を
(x1-η1)・(x2-η2) …(29)
という多項式で表現する。すると、各真理値と式(29)の関数値との関係は以下のようになる。
【００６３】
【表１】
[表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)の関数値とは以下の関係となる。
【００６５】
【表２】
[表２]から分かるように、論理積 (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であるか否かとは等価である。
【００６９】
［階層的内積述語暗号方式の基本構成］
内積述語暗号方式では、述語多項式の各項の不定元成分と１とを各要素とするベクトル及び述語多項式の各項の係数成分を各要素とするベクトルの何れか一方が暗号文に埋め込まれ、他方が復号鍵に埋め込まれる。そして、これらのベクトルの内積が0となるときに当該暗号文が当該復号鍵で復号できる。内積述語暗号方式の一種である階層的内積述語暗号方式もこの性質を持つが、階層的内積述語暗号方式ではさらに階層的な処理によって復号鍵を生成できる。すなわち、階層的内積述語暗号方式では属性が階層化され、各階層までの属性に対応する鍵情報が存在するとともに、上位の階層に対応する鍵情報を用いて下位の階層に対応する鍵情報を生成できる。そして、このような階層的な処理によって生成された最終的な鍵情報が復号鍵となる。以下に階層的内積述語暗号方式の基本構成を例示する。以下では、階層的内積述語暗号方式を用いて鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する場合の基本構成を例示する。ただし、これは本発明を限定するものではない。
【００７０】
《前提》
深さdの属性空間の階層フォーマットを以下の式によって定義する。ただし、dは1以上n以下の整数である。
【００７１】
ξ→=(n,d;ξ1,...,ξd) (0=ξ0<ξ1<...<ξd=n) …(32)
有限体Fqの元を要素とするξω-ξω-1(ω=1,...,d)次元のベクトル（零ベクトルを除く）を階層ωに対応するベクトル
【００７２】
【数１０】
とし、階層1から階層m（m≦d）までに対応するベクトルを(x1→,...,xm→)とする。有限体Fqの元を要素とするξω-ξω-1次元（ω=1,...,d）のベクトル（零ベクトルを除く）を階層ωに対応するベクトル
【００７３】
【数１１】
とし、階層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→)に対応する鍵情報
【００７７】
【数１２】
が生成されて出力される。ただし、
【００７８】
【数１３】
である。
【００７９】
《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→)に対応する鍵情報
【００８１】
【数１４】
が生成されて出力される。ただし、
【００８２】
【数１５】
である。
【００８３】
《Enc：暗号化》
−入力：公開パラメータmpk，ベクトル(v1→,...,vm→)，平文mes
−出力：暗号文(c1，c2)
Encの一例では、まず、有限体Fqから任意の元υ1,...,υd,υn+3,υが選択される。そして、これらと公開パラメータmpkとベクトル(x1→,...,xm→)とを用い、暗号文
【００８４】
【数１６】
が生成される。また、gTτ・υを共通鍵とし、所定の共通鍵暗号方式に則って平文mesの暗号文c2が生成される。暗号文c2の一例は、
c2=gTτ・υ・mes …(44)
である。なお、前述のように定数τの一例はτ=1Fである。その後、以上のように生成された暗号文(c1，c2)が出力される。
【００８５】
《Dec：復号》
−入力：公開パラメータmpk，ベクトル(v1→,...,vm→)に対応する鍵情報km*，暗号文(c1，c2)
−出力：復号値mes'
Decの一例では、
mes'=c2/e(c1,km,0*) …(45)
によって復号値mes'を計算する。
【００８６】
暗号文c1と鍵情報km*のkm,0*とが式(1)の双線形写像e（この例ではζ=3）に入力されると、式(2)(25)の性質から、
【００８７】
【数１７】
を満たす。なお、σω及びσは有限体Fqの元である。Delegate(m')がなされることなく鍵情報km*が生成された場合にはσω=σ0，ωである。Delegate(m')が１回以上なされた場合には、GenKeyに使用された有限体Fqの元σα，ωやDelegate(m')時に使用された有限体Fqの元σ'α，ωやΦ'αに応じてσωの値が定まる。ここで、すべてのω=1,...,mについて内積vω→・xω→=0Fであれば、式(46)は、
e(c1,km,0*)=gTτ・υ …(47)
と変形できる。式(44)(45)(47)より、すべてのω=1,...,mについて内積vω→・xω→=0Fである場合にmes'=mesとなり、正しく復号がなされることがわかる。
【００８８】
＜構成＞
図１は、実施形態の検索可能暗号システム１の全体構成を説明するための図である。
【００８９】
図１に例示するように、本形態の検索可能暗号システム１は、管理装置１１０−ｍ（m=1,...,M）と登録装置１２０−ｕ（u=1,...,U）と検索代行装置１３０とストレージ装置１４０と検索装置１５０−ｕ（u=1,...,U）とを有する。なお、Ｍ及びＵはそれぞれ１以上の整数である。また、管理装置１１０−ｍは、検索可能暗号システム１のｍ番目の管理者が使用する装置である。本形態では、小さいｍに対応する管理者ほど強い管理権限を持つ。すなわち、ｍ＝１に対応する管理者が最も強い権限を持つ。また、登録装置１２０−ｕ及び検索装置１５０−ｕは、検索可能暗号システム１を利用するｕ番目の登録ユーザが使用する装置である。また、各装置は他の装置へ情報を提供可能なように構成されている。装置間の情報提供はネットワークを通じて行われてもよいし、可搬型記録媒体を介して行われてもよい。
【００９０】
［管理装置］
図２Ａは、実施形態の管理装置１１０−１の機能構成を説明するための図であり、図２Ｂは、実施形態の管理装置１１０−（ｍ’＋１）（m'=1,...,M-1）の機能構成を説明するための図である。
【００９１】
図２Ａに例示するように、管理装置１１０−１は、入力部１１１−１と出力部１１２−１とマスタ秘密鍵格納部１１３−１と管理者秘密鍵格納部１１４−１と制御部１１５−１とベクトル設定部１１６ａ−１と鍵情報生成部１１６ｂ−１と補間鍵生成部１１６ｄ−１と検索者鍵生成部１１６ｃ−１と失効情報生成部１１６ｅ−１とを有する。図２Ｂに例示するように、管理装置１１０−（ｍ’＋１）は、入力部１１１−（ｍ’＋１）と出力部１１２−（ｍ’＋１）と制御部１１５−（ｍ’＋１）とベクトル設定部１１６ａ−（ｍ’＋１）と鍵情報生成部１１６ｂ−（ｍ’＋１）とを有する。管理装置１１０−ｍは、例えば、CPU(central processing unit),RAM(random-access memory),ROM(read-only memory)などを有する公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、管理装置１１０−ｍは、それぞれ、制御部１１５−ｍの制御のもと各処理を実行する。また、管理装置１１０−ｍでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【００９２】
［登録装置］
図３は、実施形態の登録装置１２０−ｕの機能構成を説明するための図である。
【００９３】
図３に例示するように、登録装置１２０−ｕは、入力部１２１−ｕと出力部１２２−ｕと属性格納部１２３ａ−ｕと登録キーワード格納部１２３ｂ−ｕと検索者鍵格納部１２３ｃ−ｕと制御部１２５−ｕと写像部１２６ａ−ｕ，１２６ｄ−ｕと乱数生成部１２６ｂ−ｕ，１２６ｃ−ｕとベクトル設定部１２６ｅ−ｕと暗号化部１２６ｆ−ｕとタグ情報生成部１２６ｇ−ｕとを有する。登録装置１２０−ｕは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、登録装置１２０−ｕは、それぞれ、制御部１２５−ｕの制御のもと各処理を実行する。なお、図面表記の便宜上、図３には２つの入力部１２１−ｕが記載されているが、これは入力部の種類や個数を限定するものではない。また、登録装置１２０−ｕでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【００９４】
［検索代行装置１３０］
図４は、実施形態の検索代行装置１３０の機能構成を説明するための図である。
【００９５】
図４に例示するように、検索代行装置１３０は、入力部１３１と出力部１３２と補間鍵格納部１３３と制御部１３５と写像部１３６と検証処理部１３７とを有する。検索代行装置１３０は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、検索代行装置１３０は、それぞれ、制御部１３５の制御のもと各処理を実行する。また、検索代行装置１３０での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。なお、図面表記の便宜上、図４には２つの入力部１３１が記載されているが、これは入力部の種類や個数を限定するものではない。
【００９６】
［ストレージ装置１４０］
図５Ａは、実施形態のストレージ装置１４０の機能構成を説明するための図である。
【００９７】
図５Ａに例示するように、ストレージ装置１４０は、入力部１４１と出力部１４２と暗号化データベース格納部１４３と制御部１４５と読み書き部１４６とを有する。ストレージ装置１４０は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、ストレージ装置１４０は、制御部１３５の制御のもと各処理を実行する。
【００９８】
図５Ｂは、暗号化データベース格納部１４３に格納される暗号化データベースのデータ構成を説明するための図である。
【００９９】
図５Ｂに例示するように、暗号化データベース格納部１４３には、文書などの検索対象情報Texttiの暗号文CT(Textti)と検索対象情報Texttiのキーワードに対応する暗号化情報であるタグ情報Tag(ti,u)とが互いに対応付けられて格納されている。暗号文CT(Textti)を生成するための検索対象情報Texttiの暗号化方式には限定はなく、任意の既存の暗号化方式（共通鍵暗号方式，公開鍵暗号方式，関数暗号方式など）でよい。タグ情報Tag(ti,u)は暗号文CT(Textti)を検索するための情報である。ストレージ装置１４０は、タグ情報Tag(ti,u)が与えられても、それに対応する検索キーワードを知ることができない。タグ情報Tag(ti,u)の生成方法の詳細は後述する。
【０１００】
［検索装置１５０−ｕ］
図６は、実施形態の検索装置１５０−ｕの機能構成を説明するための図である。
【０１０１】
図６に例示するように、検索装置１５０−ｕは、入力部１５１−ｕと出力部１５２−ｕと鍵情報格納部１５３−ｕと検索対象情報復号鍵格納部１５４−ｕと制御部１５５−ｕとベクトル設定部１５６−ｕと検索クエリ生成部１５７−ｕと復号部１５８−ｕとを有する。検索装置１５０−ｕは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、検索装置１５０−ｕは、それぞれ、制御部１５５−ｕの制御のもと各処理を実行する。なお、図面表記の便宜上、図６には２つの入力部１５１−ｕが記載されているが、これは入力部の種類や個数を限定するものではない。
【０１０２】
＜事前処理＞
前述したSetupが実行され、階層フォーマットξ→，マスタ秘密鍵msk，公開パラメータmpkが定められる。マスタ秘密鍵mskは、管理装置１１０−１（図２Ａ）のマスタ秘密鍵格納部１１３−１に安全に格納され、管理装置１１０−ｍ，登録装置１２０−ｕ，検索装置１５０−ｕ及び検索代行装置１３０が、公開パラメータmpkを用いた処理が可能なように構成される。また、管理装置１１０−ｍ及び登録装置１２０−ｕが階層フォーマットξ→に従った処理が可能なように構成される。
【０１０３】
管理装置１１０−１（図２Ａ）の管理者秘密鍵格納部１１４−１には、有限体Fqの任意の元である管理者秘密鍵ax∈Fqが安全に格納されているものとする。
【０１０４】
登録装置１２０−ｕ（図３）の登録キーワード格納部１２３ｂ−ｕには、登録を行う検索対象情報Texttiの暗号文CT(Textti)と検索対象情報Texttiに対応するキーワードWTとが格納されている。キーワードWTは、例えば、検索対象情報Texttiに含まれるキーワード又はキーワードの集合である。さらに、登録装置１２０−ｕの属性格納部１２３ａ−ｕには、登録装置１２０−ｕを利用するユーザの属性を表す情報（以下、単に「属性」という）が格納されている。ユーザの属性の例は、ユーザが所属するグループを表す情報（会社名、所属部門、課、担当、グループなど）、住所、年齢、職業、趣味などである。
【０１０５】
検索装置１５０−ｕ（図６）の検索対象情報復号鍵格納部１５４−ｕには、登録装置１２０−ｕ（図３）の登録キーワード格納部１２３ｂ−ｕに格納された暗号文CT(Textti)を復号するための検索対象情報復号鍵Keytiが格納されている。
【０１０６】
＜ユーザ登録＞
ユーザ登録では、管理装置１１０−ｍが登録ユーザの属性に対して設定されたベクトル(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=（○○株式会社，○○部門） …(48)
ATT2=（○○課，○○担当，○○グループ） …(49)
である（ステップＳ１０１）。
【０１１１】
入力された属性ATTはベクトル設定部１１６ａ−１に入力される。ベクトル設定部１１６ａ−１は、階層フォーマットξ→及びシステム内で定められた規則に従って属性ATTに対応するベクトル(v1→,...,vM→)を設定する。例えば、ベクトル設定部１１６ａ−１は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、属性ATTを表すベクトル(x1→,...,xM→)を式(33)に従って設定し、内積xω→・vω→=0Fとなる式(34)に従ったベクトル(v1→,...,vM→)を属性ATTに対応するベクトルとする。式(48)(49)の例を用いて説明すると、例えば、ベクトル設定部１１６ａ−１は、部分属性ATT1を「○○株式会社」を表すx1及び「○○部門」を表すx2を要素とする２次元のベクトル
x1→=(x1,x2) …(50)
に変換し、部分属性ATT2を「○○課」を表すx3、「○○担当」を表すx4、及び「○○グループ」を表すx5を要素とする３次元のベクトル
x2→=(x3,x4,x5) …(51)
に変換し、属性ATTを表すベクトル(x1→,x2→)=(x1,x2,x3,x4,x5)を設定し、内積xω→・vω→=0Fとなるベクトル(v1→,v2→)=(v1,v2,v3,v4,v5)を属性ATTに対応するベクトルとする。なお、システム内で定められた規則に基づいて定められるのであれば、属性ATTを表すベクトル(x1→,...,xM→)をどのように定めるかについては特に限定はなく、属性ATTごとにベクトル(x1→,...,xM→)が定まるのであればどのような方法でもよい（ステップＳ１０２）。
【０１１２】
生成されたベクトル(v1→,...,vM→)は鍵情報生成部１１６ｂ−１に入力される。鍵情報生成部１１６ｂ−１は、マスタ秘密鍵格納部１１３−１からマスタ秘密鍵mskを読み出し、m=Mとした前述のGenKeyに従い、ベクトル(v1→,...,vM→)に対応する鍵情報kM*を生成する。例えば、鍵情報生成部１１６ｂ−１は、m=Mとした式(35)-(38)に従って鍵情報kM*を生成する。生成された鍵情報kM*は出力部１１２−１に送られる（ステップＳ１０３）。
【０１１３】
また、検索者鍵生成部１１６ｃ−１が、有限体Fqから任意の元を選択し、それを登録ユーザの検索者鍵sxu∈Fqとする。生成された検索者鍵sxuは出力部１１２−１及び補間鍵生成部１１６ｄ−１に送られる（ステップＳ１０４）。
【０１１４】
検索者鍵sxuが送られた補間鍵生成部１１６ｄ−１は、管理者秘密鍵格納部１１４−１から管理者秘密鍵axを抽出し、当該検索者鍵sxuと管理者秘密鍵axとの組の像である補間鍵ckuを生成する。例えば、補間鍵生成部１１６ｄ−１は、
【０１１５】
【数１８】
によって補間鍵ckuを生成する。生成された補間鍵ckuは出力部１１２−１に送られる（ステップＳ１０５）。
【０１１６】
出力部１１２−１は、鍵情報kM*（M≦d-1）及び検索者鍵sxuを出力する。鍵情報kM*は登録ユーザが使用する検索装置１５０−ｕ（図６）の入力部１５１−ｕに入力され、鍵情報格納部１５３−ｕに格納される。検索者鍵sxuは登録ユーザが使用する登録装置１２０−ｕ（図３）の入力部１２１−ｕに入力され、検索者鍵格納部１２３ｃ−ｕに格納される（ステップＳ１０６）。
【０１１７】
また、出力部１１２−１（図２Ａ）は、補間鍵ckuを出力する。補間鍵ckuは検索代行装置１３０（図４）の入力部１３１に入力され、登録ユーザに対応付けられて補間鍵格納部１３３に格納される（ステップＳ１０７）。
【０１１８】
［委託方式］
図８及び９は、委託方式によって鍵情報kM*を生成する処理を説明するためのフローチャートである。
【０１１９】
委託方式では、最も強い権限をもつｍ＝１に対応する管理者の管理装置１１０−１が前述のGenKeyに従って鍵情報k1*を生成し、上位階層の鍵情報を受け取った下位階層の管理者の管理装置１１０−（ｍ’＋１）が前述のDelegate(m')に従って鍵情報を生成していき、最終的に鍵情報kM*が生成される。
【０１２０】
まず、管理装置１１０−１（図２Ａ）の入力部１１１−１に登録ユーザの部分属性ATT1が入力される（ステップＳ１１１）。
【０１２１】
入力された部分属性ATT1はベクトル設定部１１６ａ−１に入力される。ベクトル設定部１１６ａ−１は、階層フォーマットξ→及びシステム内で定められた規則に従って部分属性ATT1に対応するベクトルv1→を設定する。例えば、ベクトル設定部１１６ａ−１は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、部分属性ATT1を表すベクトルx1→を式(33)に従って設定し、内積x1→・v1→=0Fとなる式(34)に従ったベクトルv1→を部分属性ATT1に対応するベクトルとする。式(48)(49)の例を用いて説明すると、例えば、ベクトル設定部１１６ａ−１は、式(50)によって部分属性ATT1を表すベクトルx1→を設定し、内積x1→・v1→=0Fとなる式(51)のベクトルv1→を、部分属性ATT1に対応するベクトルとする（ステップＳ１１２）。
【０１２２】
生成されたベクトルv1→は鍵情報生成部１１６ｂ−１に入力される。鍵情報生成部１１６ｂ−１は、マスタ秘密鍵格納部１１３−１からマスタ秘密鍵mskを読み出し、m=1とした前述のGenKeyに従い、ベクトルv1→に対応する鍵情報k1*を生成する。例えば、鍵情報生成部１１６ｂ−１は、m=1とした式(35)-(38)に従って鍵情報k1*を生成する。生成された鍵情報k1*は出力部１１２−１に送られる（ステップＳ１１３）。
【０１２３】
また、一括方式と同じステップＳ１０４及びＳ１０５の処理が実行される。出力部１１２−１はステップＳ１０４で得られた検索者鍵sxuを出力する。検索者鍵sxuは登録ユーザが使用する登録装置１２０−ｕ（図３）の入力部１２１−ｕに入力され、検索者鍵格納部１２３ｃ−ｕに格納される（ステップＳ１１６）。また、出力部１１２−１はステップＳ１０５で得られた補間鍵ckuを出力する。補間鍵ckuは検索代行装置１３０（図４）の入力部１３１に入力され、登録ユーザに対応付けられて補間鍵格納部１３３に格納される（ステップＳ１０７）。さらに、出力部１１２−１はステップＳ１１３で得られた鍵情報k1*を出力する。
【０１２４】
鍵情報k1*は管理装置１１０−２に入力される。管理装置１１０−２以降では前述したDelegate(m')（m'=1,...,M-1）に従って鍵生成が行われる。以下では管理装置１１０−ｍ’から鍵情報km'*を受け取る管理装置１１０−（ｍ’＋１）の処理を一般化して説明する。
【０１２５】
まず、鍵情報km'*が管理装置１１０−（ｍ’＋１）（図２Ｂ）の入力部１１１−（ｍ’＋１）に入力され、鍵情報生成部１１６ｂ−（ｍ’＋１）に入力される（ステップＳ１２０）。また、部分属性ATTm'+1がベクトル設定部１１６ａ−（ｍ’＋１）に入力される。ベクトル設定部１１６ａ−（ｍ’＋１）は、階層フォーマットξ→及びシステム内で定められた規則に従って部分属性ATTm'+1に対応するベクトルvm'+1→を設定する。例えば、ベクトル設定部１１６ａ−（ｍ’＋１）は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、部分属性ATTm'+1を表すベクトルxm'+1→を式(33)に従って設定し、内積xm'+1→・vm'+1→=0Fとなる式(34)に従ったベクトルvm'+1→を部分属性ATTm'+1に対応するベクトルとする。生成されたベクトルvm'+1→は鍵情報生成部１１６ｂ−（ｍ’＋１）に入力される（ステップＳ１２２）。
【０１２６】
鍵情報km'*とベクトルvm'+1→とが入力された鍵情報生成部１１６ｂ−（ｍ’＋１）は、前述のDelegate(m')に従って、ベクトル(v1→,...,vm'+1→)に対応する鍵情報km'+1*を生成する。例えば、鍵情報生成部１１６ｂ−（ｍ’＋１）は、式(39)-(42)に従って鍵情報km'+1*を生成する。生成された鍵情報km'+1*は出力部１１２−（ｍ’＋１）に送られる（ステップＳ１２３）。出力部１１２−（ｍ’＋１）は鍵情報km'+1*を出力する（ステップＳ１２８）。
【０１２７】
m'+1<Mの場合、出力された鍵情報km'+1*は下位階層の管理装置１１０−（ｍ’＋２）に入力され、m'+1を新たなm'としてステップＳ１２０−Ｓ１２８の処理が実行される。一方、m'+1=Mの場合、出力された鍵情報km'+1*=kM*は、登録ユーザが使用する検索装置１５０−ｕ（図６）の入力部１５１−ｕに入力され、鍵情報格納部１５３−ｕに格納される。
【０１２８】
＜データベース登録＞
図１０は、データベース登録の処理を説明するためのフローチャートである。
【０１２９】
登録ユーザは登録装置１２０−ｕを用い、以下のようにデータベース登録を行うことができる。
【０１３０】
まず、登録装置１２０−ｕ（図３）の写像部１２６ａ−ｕが、登録キーワード格納部１２３ｂ−ｕから検索対象情報Texttiに対応する登録用のキーワードWTを抽出する（ステップＳ１３１）。また、乱数生成部１２６ｂ−ｕが、キーワードWTに対して有限体Fqの任意の元である選択値rwT∈Fqを選択する。選択値rwTは写像部１２６ａ−ｕに入力される（ステップＳ１３２）。写像部１２６ａ−ｕは、さらに検索者鍵格納部１２３ｃ−ｕから検索者鍵sxuを抽出し、WT，sxu，rwTを用いて値hを生成する（登録ユーザの検索者鍵sxuの像である第１値h）。例えば、写像部１２６ａ−ｕは、入力値に対して巡回群G1の元を出力する擬似ランダム関数Hσを用い、
【０１３１】
【数１９】
で表される値hを生成する。なお、どのような擬似ランダム関数Hσを用いてもかまわないが、例えば、鍵付きハッシュ関数を擬似ランダム関数Hσとして用いることができる（ステップＳ１３３）。生成された値hは出力部１２２−ｕ及びタグ情報生成部１２６ｇ−ｕに送られる。出力部１２２−ｕは値hを出力する（ステップＳ１３４）。
【０１３２】
登録装置１２０−ｕから出力された値hは、検索代行装置１３０（図４）の入力部１３１に入力され、写像部１３６に送られる。写像部１３６は、補間鍵格納部１３３から登録装置１２０−ｕを利用する登録ユーザに対応する補間鍵ckuを抽出する。写像部１３６は、当該値hと補間鍵ckuとの組の像である値e^を生成する。例えば、写像部１３６は、当該値hと補間鍵ckuとの組に式(4)の双線形写像Pairを施して値e^を生成する。すなわち、
e^=Pair(h,cku)∈GT …(54)
で表される値e^を生成する（ステップＳ１３５）。値e^は出力部１３２に送られ、出力部１３２は値e^を出力する（ステップＳ１３６）。
【０１３３】
検索代行装置１３０から出力された値e^は、登録装置１２０−ｕ（図３）の入力部１２１−ｕに入力され、写像部１２６ｄ−ｕに送られる。写像部１２６ｄ−ｕは値e^の像である値r'を生成する。例えば、まず乱数生成部１２６ｃ−ｕが巡回群GTの任意の元である選択値rを生成して写像部１２６ｄ−ｕ及びタグ情報生成部１２６ｇ−ｕに送り（ステップＳ１３７）、写像部１２６ｄ−ｕが、
r'＝r・e^ …(55)
で表される値r'を生成する。値r'は暗号化部１２６ｆ−ｕに送られる（ステップＳ１３８）。
【０１３４】
ベクトル設定部１２６ｅ−ｕが、登録キーワード格納部１２３ｂ−ｕから、ステップＳ１３１で抽出されたものと同じ登録用のキーワードWTを抽出する。ベクトル設定部１２６ｅ−ｕは、システム内で定められた規則に従い、登録用のキーワードWTを表すベクトルxM+1→を式(33)のように生成する。システム内で定められた規則に従うのであれば、登録用のキーワードWTを表すベクトルxM+1→をどのように定めるかに限定はない。すなわち、システム内で定められた規則に従って検索方式（完全一致検索、前方一致検索、後方一致検索、部分一致検索など）と検索用のキーワードWQとの組に対してベクトルvM+1→が定まり、当該検索方式と検索用のキーワードWQとの組に対して登録用のキーワードWTがヒットする場合に内積xM+1→・vM+1→=0Fとなるのであれば、ベクトルxM+1→をどのように定めてもよい。例えば、ベクトル設定部１２６ｅ−ｕは、非特許文献１に記載された登録キーワードから属性ベクトルを生成する技術を用いてベクトルxM+1→を生成できる。検索方式としては、例えば、非特許文献１に記載された「完全一致検索」「部分一致検索」「前方一致検索」「後方一致検索」「完全不一致検索」「含まれない」などとすることができるが、以下では一例として検索方式が「部分一致検索」である場合のベクトルxM+1→の生成方法を例示する。
【０１３５】
［検索方式が部分一致検索である場合の例］
登録用のキーワードWTの文字数をΘとし、登録用のキーワードWTの先頭からθ番目の文字に割り当てられた有限体Fqの元をxθ(1≦θ≦Θ)とする。また、検索用のキーワードWQの文字数をΡとし、検索用のキーワードWQの先頭からρ番目の文字に割り当てられた有限体Fqの元をsρ(1≦ρ≦Ρ)とする。この場合、登録用のキーワードWTと検索用のキーワードWQとが部分一致した場合に真理値が真となる論理式に対応する述語多項式の一例は、
【０１３６】
【数２０】
となる。ただし、rdε,ρは有限体Fqからランダムに選択される元である。この場合、式(56)のxθを不定元とみなした場合における、式(56)の各項の不定元成分と１Fとを各要素とするベクトルをxM+1→とすればよい（［検索方式が部分一致検索である場合の例］の説明終わり）。生成されたベクトルxM+1→は暗号化部１２６ｆ−ｕに送られる（ステップＳ１３９）。
【０１３７】
また、ベクトル設定部１２６ｅ−ｕが、属性格納部１２３ａ−ｕから登録ユーザの属性ATTを抽出する。この属性ATTは当該登録ユーザのユーザ登録時に用いられたものと同じである。ベクトル設定部１２６ｅ−ｕは、階層フォーマットξ→及びシステム内で定められた規則に従って属性ATTを表すベクトル(x1→,...,xM→)を設定する。当該ベクトル(x1→,...,xM→)とユーザ登録時のステップＳ１０３で設定されたベクトル(v1→,...,vM→)とは、ω=1,...,Mについて内積xω→・vω→=0Fを満たす。生成されたベクトル(x1→,...,xM→)は暗号化部１２６ｆ−ｕに送られる（ステップＳ１４０）。
【０１３８】
暗号化部１２６ｆ−ｕは、x1→,...,xM→,xM+1→（第１ベクトル）を用い、値r'を前述したEncによって暗号化した暗号文cを生成する。例えば、暗号化部１２６ｆ−ｕは、d=M+1とした式(43)に従って暗号文c1を生成し、mes=r'とした式(44)に従って暗号文c2を生成し、暗号文c=(c1，c2)を出力する。生成された暗号文cはタグ情報生成部１２６ｇ−ｕに送られる（ステップＳ１４１）。
【０１３９】
タグ情報生成部１２６ｇ−ｕは、暗号文cと値hとを含むタグ情報を生成する。本形態の場合、タグ情報生成部１２６ｇ−ｕは、送られたc，h，rを含むタグ情報
Tag(ti,u)=(tag1，tag2，tag3)=(c，h，r) …(57)
を生成する（ステップＳ１４２）。生成されたタグ情報Tag(ti,u)は出力部１２２−ｕに送られる。また、登録キーワード格納部１２３ｂ−ｕから読み出された暗号文CT(Textti)が出力部１２２−ｕに送られる。出力部１２２−ｕは、暗号文CT(Textti)とタグ情報Tag(ti,u)とを出力する。これらの組はストレージ装置１４０（図５Ａ）の入力部１４１に入力され、書込み部１４６から暗号化データベース格納部１４３に格納される（図５Ｂ）。
【０１４０】
＜検索＞
図１１は、検索処理を説明するためのフローチャートである。
【０１４１】
登録ユーザは検索装置１５０−ｕ（図６）を用い、以下のように検索を行うことができる。
【０１４２】
まず、検索を行う登録ユーザによって選択された検索用のキーワードwQが入力部１５１−ｕに入力される（ステップＳ１５１）。検索用のキーワードwQはベクトル設定部１５６−ｕに送られる。ベクトル設定部１５６−ｕは、システム内で定められた規則に従い、検索方式と検索用のキーワードWQに対応するベクトルvM+1→を設定する。ベクトルvM+1→は、検索方式と検索用のキーワードWQとの組に対し、ベクトルxM+1→に対応する登録用のキーワードWTがヒットする場合に内積xM+1→・vM+1→=0Fを満たすものである。例えば、ベクトル設定部１５６−ｕは、非特許文献１に記載された検索キーワードから述語ベクトルを生成する技術を用いてベクトルvM+1→を生成できる。例えば、前述した［検索方式が部分一致検索である場合の例］によって登録用のキーワードWTに対応するベクトルxM+1→が定められるならば、式(56)の各項の係数成分を各要素とするベクトルがvM+1→とされる（ステップＳ１５２）。
【０１４３】
生成された検索用のキーワードWQに対応するベクトルvM+1→は、検索クエリ生成部１５７−ｕに送られる。検索クエリ生成部１５７−ｕは、鍵情報格納部１５３−ｕから鍵情報kM*を抽出する。検索クエリ生成部１５７−ｕは、kM*，vM+1→を用い、m'=Mとした前述のDelegate(m')によって、v1→,...,vM→及びvM+1→（第２ベクトル）に対応する鍵情報（復号鍵）である検索クエリkM+1*を生成する。例えば、検索クエリ生成部１５７−ｕは、m'=M（M≦d-1）とした式(39)-(42)に従って検索クエリkM+1*を生成する。なお、m=d-1の場合には式(42)のkm'+1,α*を含まない（ステップＳ１５３）。生成された検索クエリkM+1*は出力部１５２−ｕに送られる。出力部１５２−ｕは検索クエリkM+1*を出力する（ステップＳ１５４）。
【０１４４】
検索クエリkM+1*は、検索代行装置１３０（図４）の入力部１３１に入力され、検証処理部１３７及び制御部１３５に送られる。制御部１３５は、補間鍵格納部１３３を参照し、検索クエリkM+1*に対応する登録ユーザの補間鍵ckuが利用可能であるかを検証する。検索クエリkM+1*に対応する登録ユーザの補間鍵ckuが利用可能でない場合とは、検索クエリkM+1*に対応する登録ユーザの補間鍵ckuが補間鍵格納部１３３に格納されていない場合や、後述する登録失効処理によって補間鍵格納部１３３に格納された補間鍵ckuの使用が禁止されている場合である（ステップＳ１５５）。
【０１４５】
ここで、検索クエリkM+1*に対応する登録ユーザの補間鍵ckuが利用可能でない場合には、出力部１３２が「該当なし」を表す⊥を出力して処理を終了する（ステップＳ１６３）。
【０１４６】
一方、検索クエリkM+1*に対応する登録ユーザの補間鍵ckuが利用可能である場合には、検索代行装置１３０はストレージ装置１４０（図５Ａ）にアクセスし、暗号化データベース格納部１４３に格納されたタグ情報Tag(ti,u)の取得を要求するための情報を出力部１３１から出力する。この情報はストレージ装置１４０の入力部１４１に入力されて読み書き部１４６に送られる。ストレージ装置１４０の読み書き部１４６は、暗号化データベース格納部１４３から何れかのタグ情報Tag(ti,u)を読み出し、出力部１４２はそれを検索代行装置１３０に送る。タグ情報Tag(ti,u)は検索代行装置１３０（図４）の入力部１３１に入力され、検証処理部１３７に送られる（ステップＳ１５６）。
【０１４７】
検証処理部１３７は、補間鍵格納部１３３から検索クエリkM+1*に対応する登録ユーザの補間鍵ckuを抽出し、kM+1*及びckuを用いてタグ情報Tag(ti,u)を検証する。すなわち、検証処理部１３７は、検索クエリkM+1*を復号鍵としてタグ情報Tag(ti,u)に含まれるtag1=cを前述したDecに従って復号して得られる復号値mes'が、当該タグ情報Tag(ti,u)に含まれるtag2=hと補間鍵ckuとの組に対応するかを検証する。例えば、検証処理部１３７は、タグ情報Tag(ti,u)に含まれるtag2=hとckuとの組に双線形写像pairを施して得られる値をe~とした場合におけるmes'/e~がタグ情報Tag(ti,u)に含まれるtag3=rと等しいかを検証する。すなわち、例えば、tag1=(c1,c2)，mes'=c2/e(c1,kM+1,0*)，e~=pair(tag2,cku)とした場合に、
tag3=mes'/e~ …(58)
を満たすかが検証される。満たす場合には検証合格となる（ステップＳ１５７）。
【０１４８】
ここで、検証合格とならなかった場合（ステップＳ１５８）、検索代行装置１３０はストレージ装置１４０に対して未検証のタグ情報Tag(ti,u)が暗号化データベース格納部１４３内に存在するかを問い合わせるための情報を出力部１３２から出力する。この情報はストレージ装置１４０（図５Ａ）の入力部１４１に入力され、読み書き部１４６に送られる。読み書き部１４６は、暗号化データベース格納部１４３を検索して未検証のタグ情報Tag(ti,u)が暗号化データベース格納部１４３内に存在するか否かを判定し、その判定結果が出力部１４２から出力される。判定結果は、検索代行装置１３０（図４）の入力部１３１に入力され、制御部１３５に送られる。ここで、未検証のタグ情報Tag(ti,u)が暗号化データベース格納部１４３内に存在しない旨の応答があった場合、検索代行装置１３０の出力部１３２が「該当なし」を表す⊥を出力して処理を終了する（ステップＳ１６３）。一方、未検証のタグ情報Tag(ti,u)が暗号化データベース格納部１４３内に存在する旨の応答があった場合には、ステップＳ１５６に戻る。
【０１４９】
一方、ステップＳ１５７で検証合格となった場合（ステップＳ１５８）、検索代行装置１３０はストレージ装置１４０に対し、検証合格となったタグ情報Tag(ti,u)に対応する検証対象情報の暗号文CT(Textti)の出力を要求するための情報を出力部１３２から出力する。この情報はストレージ装置１４０（図５Ａ）の入力部１４１に入力され読み書き部１４６に送られる。読み書き部１４６は、検証合格となったタグ情報Tag(ti,u)に対応する検証対象情報の暗号文CT(Textti)を暗号化データベース格納部１４３から抽出し、出力部１４２に送る。出力部１４２は暗号文CT(Textti)を出力する。暗号文CT(Textti)は、検索代行装置１３０（図４）の入力部１３１に入力され、検証処理部１３７に送られる（ステップＳ１６０）。暗号文CT(Textti)は、出力部１３２に送られて出力され、検索装置（図６）の入力部１５１−ｕに入力される（ステップＳ１６１）。暗号文CT(Textti)は、復号部１５８−ｕに送られる。復号部１５８−ｕは検索対象情報復号鍵格納部１５４−ｕから検索対象情報復号鍵Keytiを読み出し、これを用いて暗号文CT(Textti)を復号して検索対象情報Texttiを出力する（ステップＳ１６２）。
【０１５０】
＜登録失効処理＞
図１２は、登録失効処理を説明するためのフローチャートである。
【０１５１】
管理装置１１０−１（図２Ａ）が或る登録ユーザの登録を失効させる場合、まず、管理装置１１０−１の失効情報生成部１１６ｅ−１が、登録を失効させる登録ユーザを表す失効情報Revuを生成し、出力部１１２−１に送る（ステップＳ１７１）。出力部１１２−１は失効情報Revuを出力し、この失効情報Revuは検索代行装置１３０（図４）の入力部１３１に入力される（ステップＳ１７２）。失効情報Revuは制御部１３５に送られ、制御部１３５は失効情報Revuが示す登録ユーザに対応する補間鍵ckuの検索代行装置１３０での使用を禁止する。これにより、検索代行装置１３０は当該補間鍵ckuに対応する登録ユーザのデータベース登録や検索処理を正しく実行できなくなり、当該登録ユーザはデータベース登録や検索処理を行うことができなくなる。
【０１５２】
この具体的な処理方法に限定はないが、例えば以下の方法を例示できる。
【０１５３】
［例１］
例１では、各登録ユーザに対応する補間鍵ckuが「検索代行装置１３０での使用が可能なグループ」と「検索代行装置１３０での使用が禁止されたグループ」とに区分されて補間鍵格納部１３３に格納可能とされている。写像部１３６及び検証処理部１３７は「検索代行装置１３０での使用が可能なグループ」に属する補間鍵ckuを利用することはできるが、「検索代行装置１３０での使用が禁止されたグループ」に属する補間鍵ckuを利用することはできない。
【０１５４】
前述のユーザ登録時には各ユーザに対応する補間鍵ckuは「検索代行装置１３０での使用が可能なグループ」に区分されて補間鍵格納部１３３に格納される。一方、失効情報Revuが制御部１３５に入力された場合には、制御部１３５は失効情報Revuが示す登録ユーザに対応する補間鍵ckuを「検索代行装置１３０での使用が禁止されたグループ」に移す。
【０１５５】
［例２］
例２では、各登録ユーザに対応する補間鍵ckuが「写像部１３６及び検証処理部１３７での使用が可能なグループ」と「検証処理部１３７での使用が可能だが写像部１３６７での使用が禁止されたグループ」と「写像部１３６及び検証処理部１３７での使用が禁止されたグループ」とに区分されて補間鍵格納部１３３に格納可能とされている。
【０１５６】
写像部１３６は「写像部１３６及び検証処理部１３７での使用が可能なグループ」に属する補間鍵ckuを利用することはできるが、その他のグループに属する補間鍵ckuを利用することはできない。検証処理部１３７は、「写像部１３６及び検証処理部１３７での使用が可能なグループ」及び「検証処理部１３７での使用が可能だが写像部１３６７での使用が禁止されたグループ」に属する補間鍵ckuを利用することはできるが、その他のグループに属する補間鍵ckuを利用することはできない。
【０１５７】
前述のユーザ登録時には各ユーザに対応する補間鍵ckuは「写像部１３６及び検証処理部１３７での使用が可能なグループ」に区分されて補間鍵格納部１３３に格納される。一方、失効情報Revuが制御部１３５に入力された場合には、制御部１３５は失効情報Revuが示す登録ユーザに対応する補間鍵ckuを「検証処理部１３７での使用が可能だが写像部１３６７での使用が禁止されたグループ」又は「写像部１３６及び検証処理部１３７での使用が禁止されたグループ」に移す。どちらに移すかは、例えば、同じ登録ユーザに対して失効情報Revuが何回入力されたかによって定められてもよいし、失効情報Revuがどちらに移すかを指定してもよい。
【０１５８】
［例３］
例３では、失効情報Revuが制御部１３５に入力された場合に、制御部１３５が失効情報Revuが示す登録ユーザに対応する補間鍵ckuを補間鍵格納部１３３から削除する。
【０１５９】
［例４］
例１及び例２に加え、いったん登録を失効させた登録ユーザの登録を復活させる機能が設けられてもよい。
【０１６０】
〔変形例〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上記実施形態で説明した階層的内積述語暗号方式の基本構成ではζ=3の場合を例示した。しかし、ζがその他の１以上の整数であってもよい。マスタ秘密鍵mskが含む基底ベクトルをζについて一般化すると(b1*,...,bn*,bn+1*,...,bn+ζ*)となり、公開パラメータmpkが含む基底ベクトルをζについて一般化すると(b1,...,bn,bn+1,...,bn+ζ)となる。前述した式(36)-(38),(43)(44)(46)をζについてそれぞれ一般化すると、例えば、以下の式(36')-(38'),(43')(44')(46')のようになる。
【０１６１】
【数２１】
ただし、φω,0，φω,αは有限体Fqから選択された任意の元であり、Ωは0以上ζ以下の整数である。また、有限体Fqの元である定数constに対して以下を満たす。定数constの具体例は1Fである。
【０１６２】
【数２２】
【数２３】
ただし、υωは有限体Fqから選択された任意の元である。
【０１６３】
c2=gTτ・υ・const・mes …(44')
【０１６４】
【数２４】
また、上記の実施形態では、関数暗号方式として、Setup，GenKey，Delegate(m')，Enc，Decを含む階層的内積述語暗号方式を利用する場合を例示した。しかし、Delegate(m')を有しない内積述語暗号方式などの関数暗号方式を利用してもよい。この場合には、例えば、検索装置１５０−ｕがそれぞれマスタ秘密鍵mskの一部である基底ベクトル
【０１６５】
【数２５】
を保持し、kM*，vM+1→を用い、
【０１６６】
【数２６】
を検索クエリとして出力してもよい。その他、Delegate(m')を有しない参考文献１の方式を用いてもかまわない。
【０１６７】
また、式(53)の代わりに、検索者鍵sxuの像であるその他の値をhとしてもよい。例えば、巡回群G1の任意の元randに対する、
【０１６８】
【数２７】
を用いてもよい。
【０１６９】
また、上述した有限体上の元や演算が有限環上の元や演算に置換された構成でもよい。また、登録装置と検索装置とが一体であってもよいし、検索代理装置とストレージ装置とが一体であってもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１７０】
〔プログラム等〕
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１７１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１７２】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１７３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１７４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１７５】
１ 検索可能暗号システム
１１０−ｍ 管理装置
１２０−ｕ 登録装置
１３０ 検索代行装置
１４０ ストレージ装置
１５０−ｕ 検索装置
【技術分野】
【０００１】
本発明は、暗号化されたデータベースの検索が可能な検索可能暗号技術に関する。
【背景技術】
【０００２】
暗号化文書からあらかじめキーワードを抽出し、それらのキーワードの暗号文を含むデータベースを構成し、各キーワードが暗号化されたままの状態で部分一致検索を行って検索結果を得る検索可能暗号方式が非特許文献１，２に開示されている。非特許文献１，２では、暗号化条件や復号条件を述語論理で記述することが可能な述語暗号（例えば、非特許文献３から５参照）を利用して検索可能暗号方式を実現している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】R. Yoshida, S. Oda, and T. Kobayashi., "Public-key encryption with partial matching keyword search," In Symp. on Cryptography and Information Security, 2010.
【非特許文献２】N. Matsuda, M. Hattori, T. Ito, and T. Yoneda., "Secure data center systems with hierarchical predicate encryption," In Symp. on Cryptography and Information Security, 2010.
【非特許文献３】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.
【非特許文献４】J. Katz, A. Sahai, and B. Waters., "Predicate encryption supporting disjunctions, polynomial equations, and inner products," In EUROCRYPT, pp. 146-162, 2008.
【非特許文献５】T. Okamoto and K. Takashima., "Hierarchical predicate encryption for inner-products," In ASIACRYPT, pp. 214-231, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の方式では、キーワードの暗号文を含むデータベースを利用する権限が付与された登録ユーザの利用権限を失効させることが困難であった。
【０００５】
本発明はこのような点に鑑みてなされたものであり、キーワードの暗号文を含むデータベースを利用する権限が付与された登録ユーザの利用権限を失効させることが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のストレージ装置には、検索対象情報に対応するタグ情報を含む暗号化データベースが格納される。タグ情報は、第１ベクトルに対応する暗号文cと登録ユーザの検索者鍵sxuの像である第１値hとを含む。また、第１ベクトルは、登録ユーザの属性に対して設定されたベクトルと検索対象情報のキーワードに対して設定されたベクトルとを含み、暗号文cが第１値hと登録ユーザの補間鍵ckuとの組の像である第２値r'を或る暗号方式に則って暗号化した暗号文である。この暗号方式は、暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な方式である。
【０００７】
本発明の検索装置は、第２ベクトルに対応する復号鍵である検索クエリを上記暗号方式に則って生成する。第２ベクトルは、登録ユーザの属性に対応するベクトルと検索キーワードに対応するベクトルとを含む。
【０００８】
検索代行装置は、登録ユーザの補間鍵ckuを格納し、検索クエリを復号鍵として暗号化データベースのタグ情報に含まれる暗号文cを復号して得られる復号値mes'が、当該タグ情報に含まれる第１値hと当該補間鍵格納部に格納された補間鍵ckuとの組に対応するかを検証する。
【発明の効果】
【０００９】
本発明では、タグ情報が補間鍵ckuを用いて生成され、検索クエリを復号鍵としてタグ情報に含まれる暗号文cを復号して得られる復号値mes'が第１値hと補間鍵ckuとの組に対応することを検証することで、検索クエリに対して検索対象情報のキーワードがヒットしたか否かを判定できる。一方、検索代行装置による登録ユーザの補間鍵ckuの利用が禁止された場合、タグ情報の生成や検証ができなくなる。これにより、キーワードの暗号文を含むデータベースを利用する権限が付与された登録ユーザの利用権限を失効させることができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施形態の検索可能暗号システムの全体構成を説明するための図である。
【図２】図２Ａは、実施形態の管理装置の機能構成を説明するための図であり、図２Ｂは、実施形態の管理装置の機能構成を説明するための図である。
【図３】図３は、実施形態の登録装置の機能構成を説明するための図である。
【図４】図４は、実施形態の検索代行装置の機能構成を説明するための図である。
【図５】図５Ａは、実施形態のストレージ装置の機能構成を説明するための図である。図５Ｂは、暗号化データベース格納部に格納される暗号化データベースのデータ構成を説明するための図である。
【図６】図６は、実施形態の検索装置の機能構成を説明するための図である。
【図７】図７は、一括方式によって鍵情報kM*を生成する処理を説明するためのフローチャートである。
【図８】図８は、委託方式によって鍵情報kM*を生成する処理を説明するためのフローチャートである。
【図９】図９は、委託方式によって鍵情報kM*を生成する処理を説明するためのフローチャートである。
【図１０】図１０は、データベース登録の処理を説明するためのフローチャートである。
【図１１】図１１は、検索処理を説明するためのフローチャートである。
【図１２】図１２は、登録失効処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施形態を説明する。
【００１２】
〔概要〕
以下に説明する各実施形態では、関数暗号方式を用いて検索可能暗号方式を構成する。関数暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。関数暗号方式の例は、非特許文献１から５などに開示されている内積述語暗号方式や階層的内積述語暗号方式などの述語暗号方式や、参考文献１「T. Okamoto, K. Takashima, "Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption," Advances in Cryptology - CRYPTO 2010, Lecture Notes in Computer Science, 2010, Volume 6223/2010, 191-208」などに開示されている方式などである。すなわち、関数暗号方式には、内積述語暗号方式や階層的内積述語暗号方式などの述語暗号方式が含まれる。また、本発明で利用する関数暗号方式は非特許文献１から５や参考文献１に開示された方式に限定されず、どのような方式が用いられてもよい。
【００１３】
各実施形態の検索可能暗号方式では、ストレージ装置の暗号化データベース格納部に、検索対象情報に対応するタグ情報を含む暗号化データベースが格納される。このタグ情報は、第１ベクトルに対応する暗号文cと登録ユーザの検索者鍵sxuの像である第１値hとを含む。第１ベクトルは、登録ユーザの属性に対して設定されたベクトルと検索対象情報のキーワードに対して設定されたベクトルとを含む。また、暗号文cは、第１値hと登録ユーザの補間鍵ckuとの組の像である第２値r'を関数暗号方式に則って暗号化した暗号文である。登録ユーザが利用する検索装置は、第２ベクトルに対応する復号鍵である検索クエリを関数暗号方式に則って生成する。この第２ベクトルは、登録ユーザの属性に対応するベクトルと検索キーワードに対応するベクトルとを含む。検索クエリは検索代行装置に送られる。検索代行装置は登録ユーザの補間鍵ckuを格納している。この検索代行装置は、検索クエリを復号鍵として暗号化データベースのタグ情報に含まれる暗号文cを復号して復号値mes'を得る。検索代行装置は、この復号値mes'がタグ情報に含まれる第１値hと補間鍵ckuとの組に対応するかを検証する。ここで、復号値mes'がタグ情報に含まれる第１値hと補間鍵ckuとの組に対応する場合、検索クエリに対してタグ情報に対応するキーワードがヒットしたことになる。これにより、登録ユーザによる暗号化データベースの検索が可能となっている。一方、検索代行装置による補間鍵ckuの利用が禁止された場合にはこのような判定ができず、利用が禁止された補間鍵ckuに対応する登録ユーザは暗号化データベースの検索を行うことができない。このように検索代行装置による補間鍵ckuの利用を禁止することにより、利用を禁止した補間鍵ckuに対応する登録ユーザの検索権限を失効させることができる。また、登録ユーザの検索権限を失効させるために暗号化データベースを変更する必要はない。
【００１４】
また、各実施形態の検索可能暗号方式では、登録ユーザが利用する登録者装置が登録ユーザの検索者鍵sxuを格納している。登録者装置は、登録ユーザの検索者鍵sxuの像である第１値hを生成し、これを検索代行装置に送る。検索代行装置は、当該検索代行装置に格納された当該登録ユーザの補間鍵ckuを用い、第１値hと補間鍵ckuとの組の像である第３値e^を生成する。第３値e^は登録者装置に送られる。登録者装置は、第３値e^の像である第２値r'を生成し、前述の第１ベクトルを用いて関数暗号方式に則って第２値r'を暗号化して暗号文cを生成し、暗号文cと第１値hとを含むタグ情報を生成する。実施形態では、登録者装置に格納された検索者鍵sxuと検索代行装置に格納された補間鍵ckuとを用いてタグ情報が生成されるため、登録者装置や検索代行装置が単独で正しいタグ情報を生成することができない。これにより、登録者装置や検索代行装置が単独に不正なタグ情報を生成する事態を抑制できる。さらに、検索代行装置による補間鍵ckuの利用を禁止することにより、利用を禁止した補間鍵ckuに対応する登録ユーザのタグ情報の生成権限を失効させることもできる。
【００１５】
なお、検索権限やタグ情報の生成権限を失効させる場合には、例えば、管理装置が失効させる登録ユーザを示す失効情報を検索代行装置に入力する。失効情報が入力された検索代行装置は、当該失効情報が示す登録ユーザに対応する補間鍵ckuの検索代行装置での使用を禁止する。これにより、当該登録ユーザの検索権限やタグ情報の生成権限が失効する。
【００１６】
また、各実施形態の検索可能暗号方式では、管理者秘密鍵axが管理者装置に格納されている。管理者秘密鍵axは補間鍵ckuや検索者鍵sxuが生成される前に生成された情報である。登録ユーザに対応する補間鍵ckuは、当該登録ユーザに対応する検索者鍵sxuと管理者秘密鍵axとの組の像である。これにより、登録者装置に格納された検索者鍵sxuから補間鍵ckuが推測されることを防止できるとともに、検索代行装置に格納された補間鍵ckuから検索者鍵sxuが推測されることを防止できる。
【００１７】
〔実施形態〕
次に、本発明の実施形態を説明する。本形態では、関数暗号方式として階層的内積述語暗号方式を用いる。
【００１８】
＜定義＞
まず、本形態で使用する用語や記号を定義する。
【００１９】
行列：「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
(・)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は、
【００３９】
【数１】
となる。
【００４０】
A*：基底ベクトルai*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルai*(i=1,...,n+ζ)が式(9)によって表現される場合、行列A*は、
【００４１】
【数２】
となる。
【００４２】
X：有限体Fqの元を要素とするn+ζ行n+ζ列の行列を表す。基底ベクトルaiの座標変換に用いられる。行列Ｘのi行j列(i=1,...,n+ζ,j=1,...,n+ζ)の要素をχi,j∈Fqとすると、行列Xは、
【００４３】
【数３】
となる。なお、行列Ｘの各要素χi,jを変換係数と呼ぶ。
【００４４】
X *：X *は行列Xの逆行列の転置行列Ｘ*=(Ｘ-1)Tを表す。基底ベクトルai*の座標変換に用いられる。行列X*のi行j列の要素をχi,j*∈Fqとすると、行列Ｘ*は、
【００４５】
【数４】
となる。なお、行列Ｘ*の各要素χi,j*を変換係数と呼ぶ。
【００４６】
この場合、n+ζ行n+ζ列の単位行列をIとするとＸ・(Ｘ*)T=Ｉを満たす。すなわち、単位行列
【００４７】
【数５】
に対し、
【００４８】
【数６】
を満たす。ここで、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)の関係から、
【００５４】
【数７】
を満たす。特に、τ=κ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は、
【００５７】
【数８】
となる。
【００５８】
B*：B*は基底ベクトルbi*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。B*=X*・A*を満たす。例えば、基底ベクトルbi*(i=1,...,n+ζ)が式(24)によって表現される場合、行列B*は、
【００５９】
【数９】
となる。
【００６０】
〔階層的内積述語暗号方式〕
次に、階層的内積述語暗号方式について説明する。階層的内積述語暗号方式は内積述語暗号方式の一種である。内積述語暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。内積述語暗号では、内積が0となることと論理式の真理値が真となることとが等価である。
【００６１】
［内積と論理式の真理値との関係］
内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。
【００６２】
まず、「x1がη1である」という命題１と「x2がη2である」という命題２との論理和 (x1=η1)∨(x2=η2)を
(x1-η1)・(x2-η2) …(29)
という多項式で表現する。すると、各真理値と式(29)の関数値との関係は以下のようになる。
【００６３】
【表１】
[表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)の関数値とは以下の関係となる。
【００６５】
【表２】
[表２]から分かるように、論理積 (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であるか否かとは等価である。
【００６９】
［階層的内積述語暗号方式の基本構成］
内積述語暗号方式では、述語多項式の各項の不定元成分と１とを各要素とするベクトル及び述語多項式の各項の係数成分を各要素とするベクトルの何れか一方が暗号文に埋め込まれ、他方が復号鍵に埋め込まれる。そして、これらのベクトルの内積が0となるときに当該暗号文が当該復号鍵で復号できる。内積述語暗号方式の一種である階層的内積述語暗号方式もこの性質を持つが、階層的内積述語暗号方式ではさらに階層的な処理によって復号鍵を生成できる。すなわち、階層的内積述語暗号方式では属性が階層化され、各階層までの属性に対応する鍵情報が存在するとともに、上位の階層に対応する鍵情報を用いて下位の階層に対応する鍵情報を生成できる。そして、このような階層的な処理によって生成された最終的な鍵情報が復号鍵となる。以下に階層的内積述語暗号方式の基本構成を例示する。以下では、階層的内積述語暗号方式を用いて鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する場合の基本構成を例示する。ただし、これは本発明を限定するものではない。
【００７０】
《前提》
深さdの属性空間の階層フォーマットを以下の式によって定義する。ただし、dは1以上n以下の整数である。
【００７１】
ξ→=(n,d;ξ1,...,ξd) (0=ξ0<ξ1<...<ξd=n) …(32)
有限体Fqの元を要素とするξω-ξω-1(ω=1,...,d)次元のベクトル（零ベクトルを除く）を階層ωに対応するベクトル
【００７２】
【数１０】
とし、階層1から階層m（m≦d）までに対応するベクトルを(x1→,...,xm→)とする。有限体Fqの元を要素とするξω-ξω-1次元（ω=1,...,d）のベクトル（零ベクトルを除く）を階層ωに対応するベクトル
【００７３】
【数１１】
とし、階層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→)に対応する鍵情報
【００７７】
【数１２】
が生成されて出力される。ただし、
【００７８】
【数１３】
である。
【００７９】
《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→)に対応する鍵情報
【００８１】
【数１４】
が生成されて出力される。ただし、
【００８２】
【数１５】
である。
【００８３】
《Enc：暗号化》
−入力：公開パラメータmpk，ベクトル(v1→,...,vm→)，平文mes
−出力：暗号文(c1，c2)
Encの一例では、まず、有限体Fqから任意の元υ1,...,υd,υn+3,υが選択される。そして、これらと公開パラメータmpkとベクトル(x1→,...,xm→)とを用い、暗号文
【００８４】
【数１６】
が生成される。また、gTτ・υを共通鍵とし、所定の共通鍵暗号方式に則って平文mesの暗号文c2が生成される。暗号文c2の一例は、
c2=gTτ・υ・mes …(44)
である。なお、前述のように定数τの一例はτ=1Fである。その後、以上のように生成された暗号文(c1，c2)が出力される。
【００８５】
《Dec：復号》
−入力：公開パラメータmpk，ベクトル(v1→,...,vm→)に対応する鍵情報km*，暗号文(c1，c2)
−出力：復号値mes'
Decの一例では、
mes'=c2/e(c1,km,0*) …(45)
によって復号値mes'を計算する。
【００８６】
暗号文c1と鍵情報km*のkm,0*とが式(1)の双線形写像e（この例ではζ=3）に入力されると、式(2)(25)の性質から、
【００８７】
【数１７】
を満たす。なお、σω及びσは有限体Fqの元である。Delegate(m')がなされることなく鍵情報km*が生成された場合にはσω=σ0，ωである。Delegate(m')が１回以上なされた場合には、GenKeyに使用された有限体Fqの元σα，ωやDelegate(m')時に使用された有限体Fqの元σ'α，ωやΦ'αに応じてσωの値が定まる。ここで、すべてのω=1,...,mについて内積vω→・xω→=0Fであれば、式(46)は、
e(c1,km,0*)=gTτ・υ …(47)
と変形できる。式(44)(45)(47)より、すべてのω=1,...,mについて内積vω→・xω→=0Fである場合にmes'=mesとなり、正しく復号がなされることがわかる。
【００８８】
＜構成＞
図１は、実施形態の検索可能暗号システム１の全体構成を説明するための図である。
【００８９】
図１に例示するように、本形態の検索可能暗号システム１は、管理装置１１０−ｍ（m=1,...,M）と登録装置１２０−ｕ（u=1,...,U）と検索代行装置１３０とストレージ装置１４０と検索装置１５０−ｕ（u=1,...,U）とを有する。なお、Ｍ及びＵはそれぞれ１以上の整数である。また、管理装置１１０−ｍは、検索可能暗号システム１のｍ番目の管理者が使用する装置である。本形態では、小さいｍに対応する管理者ほど強い管理権限を持つ。すなわち、ｍ＝１に対応する管理者が最も強い権限を持つ。また、登録装置１２０−ｕ及び検索装置１５０−ｕは、検索可能暗号システム１を利用するｕ番目の登録ユーザが使用する装置である。また、各装置は他の装置へ情報を提供可能なように構成されている。装置間の情報提供はネットワークを通じて行われてもよいし、可搬型記録媒体を介して行われてもよい。
【００９０】
［管理装置］
図２Ａは、実施形態の管理装置１１０−１の機能構成を説明するための図であり、図２Ｂは、実施形態の管理装置１１０−（ｍ’＋１）（m'=1,...,M-1）の機能構成を説明するための図である。
【００９１】
図２Ａに例示するように、管理装置１１０−１は、入力部１１１−１と出力部１１２−１とマスタ秘密鍵格納部１１３−１と管理者秘密鍵格納部１１４−１と制御部１１５−１とベクトル設定部１１６ａ−１と鍵情報生成部１１６ｂ−１と補間鍵生成部１１６ｄ−１と検索者鍵生成部１１６ｃ−１と失効情報生成部１１６ｅ−１とを有する。図２Ｂに例示するように、管理装置１１０−（ｍ’＋１）は、入力部１１１−（ｍ’＋１）と出力部１１２−（ｍ’＋１）と制御部１１５−（ｍ’＋１）とベクトル設定部１１６ａ−（ｍ’＋１）と鍵情報生成部１１６ｂ−（ｍ’＋１）とを有する。管理装置１１０−ｍは、例えば、CPU(central processing unit),RAM(random-access memory),ROM(read-only memory)などを有する公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、管理装置１１０−ｍは、それぞれ、制御部１１５−ｍの制御のもと各処理を実行する。また、管理装置１１０−ｍでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【００９２】
［登録装置］
図３は、実施形態の登録装置１２０−ｕの機能構成を説明するための図である。
【００９３】
図３に例示するように、登録装置１２０−ｕは、入力部１２１−ｕと出力部１２２−ｕと属性格納部１２３ａ−ｕと登録キーワード格納部１２３ｂ−ｕと検索者鍵格納部１２３ｃ−ｕと制御部１２５−ｕと写像部１２６ａ−ｕ，１２６ｄ−ｕと乱数生成部１２６ｂ−ｕ，１２６ｃ−ｕとベクトル設定部１２６ｅ−ｕと暗号化部１２６ｆ−ｕとタグ情報生成部１２６ｇ−ｕとを有する。登録装置１２０−ｕは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、登録装置１２０−ｕは、それぞれ、制御部１２５−ｕの制御のもと各処理を実行する。なお、図面表記の便宜上、図３には２つの入力部１２１−ｕが記載されているが、これは入力部の種類や個数を限定するものではない。また、登録装置１２０−ｕでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【００９４】
［検索代行装置１３０］
図４は、実施形態の検索代行装置１３０の機能構成を説明するための図である。
【００９５】
図４に例示するように、検索代行装置１３０は、入力部１３１と出力部１３２と補間鍵格納部１３３と制御部１３５と写像部１３６と検証処理部１３７とを有する。検索代行装置１３０は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、検索代行装置１３０は、それぞれ、制御部１３５の制御のもと各処理を実行する。また、検索代行装置１３０での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。なお、図面表記の便宜上、図４には２つの入力部１３１が記載されているが、これは入力部の種類や個数を限定するものではない。
【００９６】
［ストレージ装置１４０］
図５Ａは、実施形態のストレージ装置１４０の機能構成を説明するための図である。
【００９７】
図５Ａに例示するように、ストレージ装置１４０は、入力部１４１と出力部１４２と暗号化データベース格納部１４３と制御部１４５と読み書き部１４６とを有する。ストレージ装置１４０は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、ストレージ装置１４０は、制御部１３５の制御のもと各処理を実行する。
【００９８】
図５Ｂは、暗号化データベース格納部１４３に格納される暗号化データベースのデータ構成を説明するための図である。
【００９９】
図５Ｂに例示するように、暗号化データベース格納部１４３には、文書などの検索対象情報Texttiの暗号文CT(Textti)と検索対象情報Texttiのキーワードに対応する暗号化情報であるタグ情報Tag(ti,u)とが互いに対応付けられて格納されている。暗号文CT(Textti)を生成するための検索対象情報Texttiの暗号化方式には限定はなく、任意の既存の暗号化方式（共通鍵暗号方式，公開鍵暗号方式，関数暗号方式など）でよい。タグ情報Tag(ti,u)は暗号文CT(Textti)を検索するための情報である。ストレージ装置１４０は、タグ情報Tag(ti,u)が与えられても、それに対応する検索キーワードを知ることができない。タグ情報Tag(ti,u)の生成方法の詳細は後述する。
【０１００】
［検索装置１５０−ｕ］
図６は、実施形態の検索装置１５０−ｕの機能構成を説明するための図である。
【０１０１】
図６に例示するように、検索装置１５０−ｕは、入力部１５１−ｕと出力部１５２−ｕと鍵情報格納部１５３−ｕと検索対象情報復号鍵格納部１５４−ｕと制御部１５５−ｕとベクトル設定部１５６−ｕと検索クエリ生成部１５７−ｕと復号部１５８−ｕとを有する。検索装置１５０−ｕは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、検索装置１５０−ｕは、それぞれ、制御部１５５−ｕの制御のもと各処理を実行する。なお、図面表記の便宜上、図６には２つの入力部１５１−ｕが記載されているが、これは入力部の種類や個数を限定するものではない。
【０１０２】
＜事前処理＞
前述したSetupが実行され、階層フォーマットξ→，マスタ秘密鍵msk，公開パラメータmpkが定められる。マスタ秘密鍵mskは、管理装置１１０−１（図２Ａ）のマスタ秘密鍵格納部１１３−１に安全に格納され、管理装置１１０−ｍ，登録装置１２０−ｕ，検索装置１５０−ｕ及び検索代行装置１３０が、公開パラメータmpkを用いた処理が可能なように構成される。また、管理装置１１０−ｍ及び登録装置１２０−ｕが階層フォーマットξ→に従った処理が可能なように構成される。
【０１０３】
管理装置１１０−１（図２Ａ）の管理者秘密鍵格納部１１４−１には、有限体Fqの任意の元である管理者秘密鍵ax∈Fqが安全に格納されているものとする。
【０１０４】
登録装置１２０−ｕ（図３）の登録キーワード格納部１２３ｂ−ｕには、登録を行う検索対象情報Texttiの暗号文CT(Textti)と検索対象情報Texttiに対応するキーワードWTとが格納されている。キーワードWTは、例えば、検索対象情報Texttiに含まれるキーワード又はキーワードの集合である。さらに、登録装置１２０−ｕの属性格納部１２３ａ−ｕには、登録装置１２０−ｕを利用するユーザの属性を表す情報（以下、単に「属性」という）が格納されている。ユーザの属性の例は、ユーザが所属するグループを表す情報（会社名、所属部門、課、担当、グループなど）、住所、年齢、職業、趣味などである。
【０１０５】
検索装置１５０−ｕ（図６）の検索対象情報復号鍵格納部１５４−ｕには、登録装置１２０−ｕ（図３）の登録キーワード格納部１２３ｂ−ｕに格納された暗号文CT(Textti)を復号するための検索対象情報復号鍵Keytiが格納されている。
【０１０６】
＜ユーザ登録＞
ユーザ登録では、管理装置１１０−ｍが登録ユーザの属性に対して設定されたベクトル(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=（○○株式会社，○○部門） …(48)
ATT2=（○○課，○○担当，○○グループ） …(49)
である（ステップＳ１０１）。
【０１１１】
入力された属性ATTはベクトル設定部１１６ａ−１に入力される。ベクトル設定部１１６ａ−１は、階層フォーマットξ→及びシステム内で定められた規則に従って属性ATTに対応するベクトル(v1→,...,vM→)を設定する。例えば、ベクトル設定部１１６ａ−１は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、属性ATTを表すベクトル(x1→,...,xM→)を式(33)に従って設定し、内積xω→・vω→=0Fとなる式(34)に従ったベクトル(v1→,...,vM→)を属性ATTに対応するベクトルとする。式(48)(49)の例を用いて説明すると、例えば、ベクトル設定部１１６ａ−１は、部分属性ATT1を「○○株式会社」を表すx1及び「○○部門」を表すx2を要素とする２次元のベクトル
x1→=(x1,x2) …(50)
に変換し、部分属性ATT2を「○○課」を表すx3、「○○担当」を表すx4、及び「○○グループ」を表すx5を要素とする３次元のベクトル
x2→=(x3,x4,x5) …(51)
に変換し、属性ATTを表すベクトル(x1→,x2→)=(x1,x2,x3,x4,x5)を設定し、内積xω→・vω→=0Fとなるベクトル(v1→,v2→)=(v1,v2,v3,v4,v5)を属性ATTに対応するベクトルとする。なお、システム内で定められた規則に基づいて定められるのであれば、属性ATTを表すベクトル(x1→,...,xM→)をどのように定めるかについては特に限定はなく、属性ATTごとにベクトル(x1→,...,xM→)が定まるのであればどのような方法でもよい（ステップＳ１０２）。
【０１１２】
生成されたベクトル(v1→,...,vM→)は鍵情報生成部１１６ｂ−１に入力される。鍵情報生成部１１６ｂ−１は、マスタ秘密鍵格納部１１３−１からマスタ秘密鍵mskを読み出し、m=Mとした前述のGenKeyに従い、ベクトル(v1→,...,vM→)に対応する鍵情報kM*を生成する。例えば、鍵情報生成部１１６ｂ−１は、m=Mとした式(35)-(38)に従って鍵情報kM*を生成する。生成された鍵情報kM*は出力部１１２−１に送られる（ステップＳ１０３）。
【０１１３】
また、検索者鍵生成部１１６ｃ−１が、有限体Fqから任意の元を選択し、それを登録ユーザの検索者鍵sxu∈Fqとする。生成された検索者鍵sxuは出力部１１２−１及び補間鍵生成部１１６ｄ−１に送られる（ステップＳ１０４）。
【０１１４】
検索者鍵sxuが送られた補間鍵生成部１１６ｄ−１は、管理者秘密鍵格納部１１４−１から管理者秘密鍵axを抽出し、当該検索者鍵sxuと管理者秘密鍵axとの組の像である補間鍵ckuを生成する。例えば、補間鍵生成部１１６ｄ−１は、
【０１１５】
【数１８】
によって補間鍵ckuを生成する。生成された補間鍵ckuは出力部１１２−１に送られる（ステップＳ１０５）。
【０１１６】
出力部１１２−１は、鍵情報kM*（M≦d-1）及び検索者鍵sxuを出力する。鍵情報kM*は登録ユーザが使用する検索装置１５０−ｕ（図６）の入力部１５１−ｕに入力され、鍵情報格納部１５３−ｕに格納される。検索者鍵sxuは登録ユーザが使用する登録装置１２０−ｕ（図３）の入力部１２１−ｕに入力され、検索者鍵格納部１２３ｃ−ｕに格納される（ステップＳ１０６）。
【０１１７】
また、出力部１１２−１（図２Ａ）は、補間鍵ckuを出力する。補間鍵ckuは検索代行装置１３０（図４）の入力部１３１に入力され、登録ユーザに対応付けられて補間鍵格納部１３３に格納される（ステップＳ１０７）。
【０１１８】
［委託方式］
図８及び９は、委託方式によって鍵情報kM*を生成する処理を説明するためのフローチャートである。
【０１１９】
委託方式では、最も強い権限をもつｍ＝１に対応する管理者の管理装置１１０−１が前述のGenKeyに従って鍵情報k1*を生成し、上位階層の鍵情報を受け取った下位階層の管理者の管理装置１１０−（ｍ’＋１）が前述のDelegate(m')に従って鍵情報を生成していき、最終的に鍵情報kM*が生成される。
【０１２０】
まず、管理装置１１０−１（図２Ａ）の入力部１１１−１に登録ユーザの部分属性ATT1が入力される（ステップＳ１１１）。
【０１２１】
入力された部分属性ATT1はベクトル設定部１１６ａ−１に入力される。ベクトル設定部１１６ａ−１は、階層フォーマットξ→及びシステム内で定められた規則に従って部分属性ATT1に対応するベクトルv1→を設定する。例えば、ベクトル設定部１１６ａ−１は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、部分属性ATT1を表すベクトルx1→を式(33)に従って設定し、内積x1→・v1→=0Fとなる式(34)に従ったベクトルv1→を部分属性ATT1に対応するベクトルとする。式(48)(49)の例を用いて説明すると、例えば、ベクトル設定部１１６ａ−１は、式(50)によって部分属性ATT1を表すベクトルx1→を設定し、内積x1→・v1→=0Fとなる式(51)のベクトルv1→を、部分属性ATT1に対応するベクトルとする（ステップＳ１１２）。
【０１２２】
生成されたベクトルv1→は鍵情報生成部１１６ｂ−１に入力される。鍵情報生成部１１６ｂ−１は、マスタ秘密鍵格納部１１３−１からマスタ秘密鍵mskを読み出し、m=1とした前述のGenKeyに従い、ベクトルv1→に対応する鍵情報k1*を生成する。例えば、鍵情報生成部１１６ｂ−１は、m=1とした式(35)-(38)に従って鍵情報k1*を生成する。生成された鍵情報k1*は出力部１１２−１に送られる（ステップＳ１１３）。
【０１２３】
また、一括方式と同じステップＳ１０４及びＳ１０５の処理が実行される。出力部１１２−１はステップＳ１０４で得られた検索者鍵sxuを出力する。検索者鍵sxuは登録ユーザが使用する登録装置１２０−ｕ（図３）の入力部１２１−ｕに入力され、検索者鍵格納部１２３ｃ−ｕに格納される（ステップＳ１１６）。また、出力部１１２−１はステップＳ１０５で得られた補間鍵ckuを出力する。補間鍵ckuは検索代行装置１３０（図４）の入力部１３１に入力され、登録ユーザに対応付けられて補間鍵格納部１３３に格納される（ステップＳ１０７）。さらに、出力部１１２−１はステップＳ１１３で得られた鍵情報k1*を出力する。
【０１２４】
鍵情報k1*は管理装置１１０−２に入力される。管理装置１１０−２以降では前述したDelegate(m')（m'=1,...,M-1）に従って鍵生成が行われる。以下では管理装置１１０−ｍ’から鍵情報km'*を受け取る管理装置１１０−（ｍ’＋１）の処理を一般化して説明する。
【０１２５】
まず、鍵情報km'*が管理装置１１０−（ｍ’＋１）（図２Ｂ）の入力部１１１−（ｍ’＋１）に入力され、鍵情報生成部１１６ｂ−（ｍ’＋１）に入力される（ステップＳ１２０）。また、部分属性ATTm'+1がベクトル設定部１１６ａ−（ｍ’＋１）に入力される。ベクトル設定部１１６ａ−（ｍ’＋１）は、階層フォーマットξ→及びシステム内で定められた規則に従って部分属性ATTm'+1に対応するベクトルvm'+1→を設定する。例えば、ベクトル設定部１１６ａ−（ｍ’＋１）は、まず、階層フォーマットξ→及びシステム内で定められた規則に従い、部分属性ATTm'+1を表すベクトルxm'+1→を式(33)に従って設定し、内積xm'+1→・vm'+1→=0Fとなる式(34)に従ったベクトルvm'+1→を部分属性ATTm'+1に対応するベクトルとする。生成されたベクトルvm'+1→は鍵情報生成部１１６ｂ−（ｍ’＋１）に入力される（ステップＳ１２２）。
【０１２６】
鍵情報km'*とベクトルvm'+1→とが入力された鍵情報生成部１１６ｂ−（ｍ’＋１）は、前述のDelegate(m')に従って、ベクトル(v1→,...,vm'+1→)に対応する鍵情報km'+1*を生成する。例えば、鍵情報生成部１１６ｂ−（ｍ’＋１）は、式(39)-(42)に従って鍵情報km'+1*を生成する。生成された鍵情報km'+1*は出力部１１２−（ｍ’＋１）に送られる（ステップＳ１２３）。出力部１１２−（ｍ’＋１）は鍵情報km'+1*を出力する（ステップＳ１２８）。
【０１２７】
m'+1<Mの場合、出力された鍵情報km'+1*は下位階層の管理装置１１０−（ｍ’＋２）に入力され、m'+1を新たなm'としてステップＳ１２０−Ｓ１２８の処理が実行される。一方、m'+1=Mの場合、出力された鍵情報km'+1*=kM*は、登録ユーザが使用する検索装置１５０−ｕ（図６）の入力部１５１−ｕに入力され、鍵情報格納部１５３−ｕに格納される。
【０１２８】
＜データベース登録＞
図１０は、データベース登録の処理を説明するためのフローチャートである。
【０１２９】
登録ユーザは登録装置１２０−ｕを用い、以下のようにデータベース登録を行うことができる。
【０１３０】
まず、登録装置１２０−ｕ（図３）の写像部１２６ａ−ｕが、登録キーワード格納部１２３ｂ−ｕから検索対象情報Texttiに対応する登録用のキーワードWTを抽出する（ステップＳ１３１）。また、乱数生成部１２６ｂ−ｕが、キーワードWTに対して有限体Fqの任意の元である選択値rwT∈Fqを選択する。選択値rwTは写像部１２６ａ−ｕに入力される（ステップＳ１３２）。写像部１２６ａ−ｕは、さらに検索者鍵格納部１２３ｃ−ｕから検索者鍵sxuを抽出し、WT，sxu，rwTを用いて値hを生成する（登録ユーザの検索者鍵sxuの像である第１値h）。例えば、写像部１２６ａ−ｕは、入力値に対して巡回群G1の元を出力する擬似ランダム関数Hσを用い、
【０１３１】
【数１９】
で表される値hを生成する。なお、どのような擬似ランダム関数Hσを用いてもかまわないが、例えば、鍵付きハッシュ関数を擬似ランダム関数Hσとして用いることができる（ステップＳ１３３）。生成された値hは出力部１２２−ｕ及びタグ情報生成部１２６ｇ−ｕに送られる。出力部１２２−ｕは値hを出力する（ステップＳ１３４）。
【０１３２】
登録装置１２０−ｕから出力された値hは、検索代行装置１３０（図４）の入力部１３１に入力され、写像部１３６に送られる。写像部１３６は、補間鍵格納部１３３から登録装置１２０−ｕを利用する登録ユーザに対応する補間鍵ckuを抽出する。写像部１３６は、当該値hと補間鍵ckuとの組の像である値e^を生成する。例えば、写像部１３６は、当該値hと補間鍵ckuとの組に式(4)の双線形写像Pairを施して値e^を生成する。すなわち、
e^=Pair(h,cku)∈GT …(54)
で表される値e^を生成する（ステップＳ１３５）。値e^は出力部１３２に送られ、出力部１３２は値e^を出力する（ステップＳ１３６）。
【０１３３】
検索代行装置１３０から出力された値e^は、登録装置１２０−ｕ（図３）の入力部１２１−ｕに入力され、写像部１２６ｄ−ｕに送られる。写像部１２６ｄ−ｕは値e^の像である値r'を生成する。例えば、まず乱数生成部１２６ｃ−ｕが巡回群GTの任意の元である選択値rを生成して写像部１２６ｄ−ｕ及びタグ情報生成部１２６ｇ−ｕに送り（ステップＳ１３７）、写像部１２６ｄ−ｕが、
r'＝r・e^ …(55)
で表される値r'を生成する。値r'は暗号化部１２６ｆ−ｕに送られる（ステップＳ１３８）。
【０１３４】
ベクトル設定部１２６ｅ−ｕが、登録キーワード格納部１２３ｂ−ｕから、ステップＳ１３１で抽出されたものと同じ登録用のキーワードWTを抽出する。ベクトル設定部１２６ｅ−ｕは、システム内で定められた規則に従い、登録用のキーワードWTを表すベクトルxM+1→を式(33)のように生成する。システム内で定められた規則に従うのであれば、登録用のキーワードWTを表すベクトルxM+1→をどのように定めるかに限定はない。すなわち、システム内で定められた規則に従って検索方式（完全一致検索、前方一致検索、後方一致検索、部分一致検索など）と検索用のキーワードWQとの組に対してベクトルvM+1→が定まり、当該検索方式と検索用のキーワードWQとの組に対して登録用のキーワードWTがヒットする場合に内積xM+1→・vM+1→=0Fとなるのであれば、ベクトルxM+1→をどのように定めてもよい。例えば、ベクトル設定部１２６ｅ−ｕは、非特許文献１に記載された登録キーワードから属性ベクトルを生成する技術を用いてベクトルxM+1→を生成できる。検索方式としては、例えば、非特許文献１に記載された「完全一致検索」「部分一致検索」「前方一致検索」「後方一致検索」「完全不一致検索」「含まれない」などとすることができるが、以下では一例として検索方式が「部分一致検索」である場合のベクトルxM+1→の生成方法を例示する。
【０１３５】
［検索方式が部分一致検索である場合の例］
登録用のキーワードWTの文字数をΘとし、登録用のキーワードWTの先頭からθ番目の文字に割り当てられた有限体Fqの元をxθ(1≦θ≦Θ)とする。また、検索用のキーワードWQの文字数をΡとし、検索用のキーワードWQの先頭からρ番目の文字に割り当てられた有限体Fqの元をsρ(1≦ρ≦Ρ)とする。この場合、登録用のキーワードWTと検索用のキーワードWQとが部分一致した場合に真理値が真となる論理式に対応する述語多項式の一例は、
【０１３６】
【数２０】
となる。ただし、rdε,ρは有限体Fqからランダムに選択される元である。この場合、式(56)のxθを不定元とみなした場合における、式(56)の各項の不定元成分と１Fとを各要素とするベクトルをxM+1→とすればよい（［検索方式が部分一致検索である場合の例］の説明終わり）。生成されたベクトルxM+1→は暗号化部１２６ｆ−ｕに送られる（ステップＳ１３９）。
【０１３７】
また、ベクトル設定部１２６ｅ−ｕが、属性格納部１２３ａ−ｕから登録ユーザの属性ATTを抽出する。この属性ATTは当該登録ユーザのユーザ登録時に用いられたものと同じである。ベクトル設定部１２６ｅ−ｕは、階層フォーマットξ→及びシステム内で定められた規則に従って属性ATTを表すベクトル(x1→,...,xM→)を設定する。当該ベクトル(x1→,...,xM→)とユーザ登録時のステップＳ１０３で設定されたベクトル(v1→,...,vM→)とは、ω=1,...,Mについて内積xω→・vω→=0Fを満たす。生成されたベクトル(x1→,...,xM→)は暗号化部１２６ｆ−ｕに送られる（ステップＳ１４０）。
【０１３８】
暗号化部１２６ｆ−ｕは、x1→,...,xM→,xM+1→（第１ベクトル）を用い、値r'を前述したEncによって暗号化した暗号文cを生成する。例えば、暗号化部１２６ｆ−ｕは、d=M+1とした式(43)に従って暗号文c1を生成し、mes=r'とした式(44)に従って暗号文c2を生成し、暗号文c=(c1，c2)を出力する。生成された暗号文cはタグ情報生成部１２６ｇ−ｕに送られる（ステップＳ１４１）。
【０１３９】
タグ情報生成部１２６ｇ−ｕは、暗号文cと値hとを含むタグ情報を生成する。本形態の場合、タグ情報生成部１２６ｇ−ｕは、送られたc，h，rを含むタグ情報
Tag(ti,u)=(tag1，tag2，tag3)=(c，h，r) …(57)
を生成する（ステップＳ１４２）。生成されたタグ情報Tag(ti,u)は出力部１２２−ｕに送られる。また、登録キーワード格納部１２３ｂ−ｕから読み出された暗号文CT(Textti)が出力部１２２−ｕに送られる。出力部１２２−ｕは、暗号文CT(Textti)とタグ情報Tag(ti,u)とを出力する。これらの組はストレージ装置１４０（図５Ａ）の入力部１４１に入力され、書込み部１４６から暗号化データベース格納部１４３に格納される（図５Ｂ）。
【０１４０】
＜検索＞
図１１は、検索処理を説明するためのフローチャートである。
【０１４１】
登録ユーザは検索装置１５０−ｕ（図６）を用い、以下のように検索を行うことができる。
【０１４２】
まず、検索を行う登録ユーザによって選択された検索用のキーワードwQが入力部１５１−ｕに入力される（ステップＳ１５１）。検索用のキーワードwQはベクトル設定部１５６−ｕに送られる。ベクトル設定部１５６−ｕは、システム内で定められた規則に従い、検索方式と検索用のキーワードWQに対応するベクトルvM+1→を設定する。ベクトルvM+1→は、検索方式と検索用のキーワードWQとの組に対し、ベクトルxM+1→に対応する登録用のキーワードWTがヒットする場合に内積xM+1→・vM+1→=0Fを満たすものである。例えば、ベクトル設定部１５６−ｕは、非特許文献１に記載された検索キーワードから述語ベクトルを生成する技術を用いてベクトルvM+1→を生成できる。例えば、前述した［検索方式が部分一致検索である場合の例］によって登録用のキーワードWTに対応するベクトルxM+1→が定められるならば、式(56)の各項の係数成分を各要素とするベクトルがvM+1→とされる（ステップＳ１５２）。
【０１４３】
生成された検索用のキーワードWQに対応するベクトルvM+1→は、検索クエリ生成部１５７−ｕに送られる。検索クエリ生成部１５７−ｕは、鍵情報格納部１５３−ｕから鍵情報kM*を抽出する。検索クエリ生成部１５７−ｕは、kM*，vM+1→を用い、m'=Mとした前述のDelegate(m')によって、v1→,...,vM→及びvM+1→（第２ベクトル）に対応する鍵情報（復号鍵）である検索クエリkM+1*を生成する。例えば、検索クエリ生成部１５７−ｕは、m'=M（M≦d-1）とした式(39)-(42)に従って検索クエリkM+1*を生成する。なお、m=d-1の場合には式(42)のkm'+1,α*を含まない（ステップＳ１５３）。生成された検索クエリkM+1*は出力部１５２−ｕに送られる。出力部１５２−ｕは検索クエリkM+1*を出力する（ステップＳ１５４）。
【０１４４】
検索クエリkM+1*は、検索代行装置１３０（図４）の入力部１３１に入力され、検証処理部１３７及び制御部１３５に送られる。制御部１３５は、補間鍵格納部１３３を参照し、検索クエリkM+1*に対応する登録ユーザの補間鍵ckuが利用可能であるかを検証する。検索クエリkM+1*に対応する登録ユーザの補間鍵ckuが利用可能でない場合とは、検索クエリkM+1*に対応する登録ユーザの補間鍵ckuが補間鍵格納部１３３に格納されていない場合や、後述する登録失効処理によって補間鍵格納部１３３に格納された補間鍵ckuの使用が禁止されている場合である（ステップＳ１５５）。
【０１４５】
ここで、検索クエリkM+1*に対応する登録ユーザの補間鍵ckuが利用可能でない場合には、出力部１３２が「該当なし」を表す⊥を出力して処理を終了する（ステップＳ１６３）。
【０１４６】
一方、検索クエリkM+1*に対応する登録ユーザの補間鍵ckuが利用可能である場合には、検索代行装置１３０はストレージ装置１４０（図５Ａ）にアクセスし、暗号化データベース格納部１４３に格納されたタグ情報Tag(ti,u)の取得を要求するための情報を出力部１３１から出力する。この情報はストレージ装置１４０の入力部１４１に入力されて読み書き部１４６に送られる。ストレージ装置１４０の読み書き部１４６は、暗号化データベース格納部１４３から何れかのタグ情報Tag(ti,u)を読み出し、出力部１４２はそれを検索代行装置１３０に送る。タグ情報Tag(ti,u)は検索代行装置１３０（図４）の入力部１３１に入力され、検証処理部１３７に送られる（ステップＳ１５６）。
【０１４７】
検証処理部１３７は、補間鍵格納部１３３から検索クエリkM+1*に対応する登録ユーザの補間鍵ckuを抽出し、kM+1*及びckuを用いてタグ情報Tag(ti,u)を検証する。すなわち、検証処理部１３７は、検索クエリkM+1*を復号鍵としてタグ情報Tag(ti,u)に含まれるtag1=cを前述したDecに従って復号して得られる復号値mes'が、当該タグ情報Tag(ti,u)に含まれるtag2=hと補間鍵ckuとの組に対応するかを検証する。例えば、検証処理部１３７は、タグ情報Tag(ti,u)に含まれるtag2=hとckuとの組に双線形写像pairを施して得られる値をe~とした場合におけるmes'/e~がタグ情報Tag(ti,u)に含まれるtag3=rと等しいかを検証する。すなわち、例えば、tag1=(c1,c2)，mes'=c2/e(c1,kM+1,0*)，e~=pair(tag2,cku)とした場合に、
tag3=mes'/e~ …(58)
を満たすかが検証される。満たす場合には検証合格となる（ステップＳ１５７）。
【０１４８】
ここで、検証合格とならなかった場合（ステップＳ１５８）、検索代行装置１３０はストレージ装置１４０に対して未検証のタグ情報Tag(ti,u)が暗号化データベース格納部１４３内に存在するかを問い合わせるための情報を出力部１３２から出力する。この情報はストレージ装置１４０（図５Ａ）の入力部１４１に入力され、読み書き部１４６に送られる。読み書き部１４６は、暗号化データベース格納部１４３を検索して未検証のタグ情報Tag(ti,u)が暗号化データベース格納部１４３内に存在するか否かを判定し、その判定結果が出力部１４２から出力される。判定結果は、検索代行装置１３０（図４）の入力部１３１に入力され、制御部１３５に送られる。ここで、未検証のタグ情報Tag(ti,u)が暗号化データベース格納部１４３内に存在しない旨の応答があった場合、検索代行装置１３０の出力部１３２が「該当なし」を表す⊥を出力して処理を終了する（ステップＳ１６３）。一方、未検証のタグ情報Tag(ti,u)が暗号化データベース格納部１４３内に存在する旨の応答があった場合には、ステップＳ１５６に戻る。
【０１４９】
一方、ステップＳ１５７で検証合格となった場合（ステップＳ１５８）、検索代行装置１３０はストレージ装置１４０に対し、検証合格となったタグ情報Tag(ti,u)に対応する検証対象情報の暗号文CT(Textti)の出力を要求するための情報を出力部１３２から出力する。この情報はストレージ装置１４０（図５Ａ）の入力部１４１に入力され読み書き部１４６に送られる。読み書き部１４６は、検証合格となったタグ情報Tag(ti,u)に対応する検証対象情報の暗号文CT(Textti)を暗号化データベース格納部１４３から抽出し、出力部１４２に送る。出力部１４２は暗号文CT(Textti)を出力する。暗号文CT(Textti)は、検索代行装置１３０（図４）の入力部１３１に入力され、検証処理部１３７に送られる（ステップＳ１６０）。暗号文CT(Textti)は、出力部１３２に送られて出力され、検索装置（図６）の入力部１５１−ｕに入力される（ステップＳ１６１）。暗号文CT(Textti)は、復号部１５８−ｕに送られる。復号部１５８−ｕは検索対象情報復号鍵格納部１５４−ｕから検索対象情報復号鍵Keytiを読み出し、これを用いて暗号文CT(Textti)を復号して検索対象情報Texttiを出力する（ステップＳ１６２）。
【０１５０】
＜登録失効処理＞
図１２は、登録失効処理を説明するためのフローチャートである。
【０１５１】
管理装置１１０−１（図２Ａ）が或る登録ユーザの登録を失効させる場合、まず、管理装置１１０−１の失効情報生成部１１６ｅ−１が、登録を失効させる登録ユーザを表す失効情報Revuを生成し、出力部１１２−１に送る（ステップＳ１７１）。出力部１１２−１は失効情報Revuを出力し、この失効情報Revuは検索代行装置１３０（図４）の入力部１３１に入力される（ステップＳ１７２）。失効情報Revuは制御部１３５に送られ、制御部１３５は失効情報Revuが示す登録ユーザに対応する補間鍵ckuの検索代行装置１３０での使用を禁止する。これにより、検索代行装置１３０は当該補間鍵ckuに対応する登録ユーザのデータベース登録や検索処理を正しく実行できなくなり、当該登録ユーザはデータベース登録や検索処理を行うことができなくなる。
【０１５２】
この具体的な処理方法に限定はないが、例えば以下の方法を例示できる。
【０１５３】
［例１］
例１では、各登録ユーザに対応する補間鍵ckuが「検索代行装置１３０での使用が可能なグループ」と「検索代行装置１３０での使用が禁止されたグループ」とに区分されて補間鍵格納部１３３に格納可能とされている。写像部１３６及び検証処理部１３７は「検索代行装置１３０での使用が可能なグループ」に属する補間鍵ckuを利用することはできるが、「検索代行装置１３０での使用が禁止されたグループ」に属する補間鍵ckuを利用することはできない。
【０１５４】
前述のユーザ登録時には各ユーザに対応する補間鍵ckuは「検索代行装置１３０での使用が可能なグループ」に区分されて補間鍵格納部１３３に格納される。一方、失効情報Revuが制御部１３５に入力された場合には、制御部１３５は失効情報Revuが示す登録ユーザに対応する補間鍵ckuを「検索代行装置１３０での使用が禁止されたグループ」に移す。
【０１５５】
［例２］
例２では、各登録ユーザに対応する補間鍵ckuが「写像部１３６及び検証処理部１３７での使用が可能なグループ」と「検証処理部１３７での使用が可能だが写像部１３６７での使用が禁止されたグループ」と「写像部１３６及び検証処理部１３７での使用が禁止されたグループ」とに区分されて補間鍵格納部１３３に格納可能とされている。
【０１５６】
写像部１３６は「写像部１３６及び検証処理部１３７での使用が可能なグループ」に属する補間鍵ckuを利用することはできるが、その他のグループに属する補間鍵ckuを利用することはできない。検証処理部１３７は、「写像部１３６及び検証処理部１３７での使用が可能なグループ」及び「検証処理部１３７での使用が可能だが写像部１３６７での使用が禁止されたグループ」に属する補間鍵ckuを利用することはできるが、その他のグループに属する補間鍵ckuを利用することはできない。
【０１５７】
前述のユーザ登録時には各ユーザに対応する補間鍵ckuは「写像部１３６及び検証処理部１３７での使用が可能なグループ」に区分されて補間鍵格納部１３３に格納される。一方、失効情報Revuが制御部１３５に入力された場合には、制御部１３５は失効情報Revuが示す登録ユーザに対応する補間鍵ckuを「検証処理部１３７での使用が可能だが写像部１３６７での使用が禁止されたグループ」又は「写像部１３６及び検証処理部１３７での使用が禁止されたグループ」に移す。どちらに移すかは、例えば、同じ登録ユーザに対して失効情報Revuが何回入力されたかによって定められてもよいし、失効情報Revuがどちらに移すかを指定してもよい。
【０１５８】
［例３］
例３では、失効情報Revuが制御部１３５に入力された場合に、制御部１３５が失効情報Revuが示す登録ユーザに対応する補間鍵ckuを補間鍵格納部１３３から削除する。
【０１５９】
［例４］
例１及び例２に加え、いったん登録を失効させた登録ユーザの登録を復活させる機能が設けられてもよい。
【０１６０】
〔変形例〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上記実施形態で説明した階層的内積述語暗号方式の基本構成ではζ=3の場合を例示した。しかし、ζがその他の１以上の整数であってもよい。マスタ秘密鍵mskが含む基底ベクトルをζについて一般化すると(b1*,...,bn*,bn+1*,...,bn+ζ*)となり、公開パラメータmpkが含む基底ベクトルをζについて一般化すると(b1,...,bn,bn+1,...,bn+ζ)となる。前述した式(36)-(38),(43)(44)(46)をζについてそれぞれ一般化すると、例えば、以下の式(36')-(38'),(43')(44')(46')のようになる。
【０１６１】
【数２１】
ただし、φω,0，φω,αは有限体Fqから選択された任意の元であり、Ωは0以上ζ以下の整数である。また、有限体Fqの元である定数constに対して以下を満たす。定数constの具体例は1Fである。
【０１６２】
【数２２】
【数２３】
ただし、υωは有限体Fqから選択された任意の元である。
【０１６３】
c2=gTτ・υ・const・mes …(44')
【０１６４】
【数２４】
また、上記の実施形態では、関数暗号方式として、Setup，GenKey，Delegate(m')，Enc，Decを含む階層的内積述語暗号方式を利用する場合を例示した。しかし、Delegate(m')を有しない内積述語暗号方式などの関数暗号方式を利用してもよい。この場合には、例えば、検索装置１５０−ｕがそれぞれマスタ秘密鍵mskの一部である基底ベクトル
【０１６５】
【数２５】
を保持し、kM*，vM+1→を用い、
【０１６６】
【数２６】
を検索クエリとして出力してもよい。その他、Delegate(m')を有しない参考文献１の方式を用いてもかまわない。
【０１６７】
また、式(53)の代わりに、検索者鍵sxuの像であるその他の値をhとしてもよい。例えば、巡回群G1の任意の元randに対する、
【０１６８】
【数２７】
を用いてもよい。
【０１６９】
また、上述した有限体上の元や演算が有限環上の元や演算に置換された構成でもよい。また、登録装置と検索装置とが一体であってもよいし、検索代理装置とストレージ装置とが一体であってもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１７０】
〔プログラム等〕
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１７１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１７２】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１７３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１７４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１７５】
１ 検索可能暗号システム
１１０−ｍ 管理装置
１２０−ｕ 登録装置
１３０ 検索代行装置
１４０ ストレージ装置
１５０−ｕ 検索装置
【特許請求の範囲】
【請求項１】
暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な暗号方式を用いた検索可能暗号システムであって、
ストレージ装置と検索装置と検索代行装置とを有し、
前記ストレージ装置は、
検索対象情報に対応するタグ情報を含む暗号化データベースを格納する暗号化データベース格納部を含み、前記タグ情報が第１ベクトルに対応する暗号文cと登録ユーザの検索者鍵sxuの像である第１値hとを含み、前記第１ベクトルが前記登録ユーザの属性に対して設定されたベクトルと前記検索対象情報のキーワードに対して設定されたベクトルとを含み、前記暗号文cが前記第１値hと前記登録ユーザの補間鍵ckuとの組の像である第２値r'を前記暗号方式に則って暗号化した暗号文であり、
前記検索装置は、
第２ベクトルに対応する復号鍵である検索クエリを前記暗号方式に則って生成する検索クエリ生成部を含み、前記第２ベクトルが登録ユーザの属性に対応するベクトルと検索キーワードに対応するベクトルとを含み、
前記検索代行装置は、
前記登録ユーザの補間鍵ckuを格納する補間鍵格納部と、前記検索クエリを復号鍵として前記暗号化データベースの前記タグ情報に含まれる前記暗号文cを復号して得られる復号値decが、当該タグ情報に含まれる前記第１値hと当該補間鍵格納部に格納された前記補間鍵ckuとの組に対応するかを検証する検証処理部と、を含む、
ことを特徴とする検索可能暗号システム。
【請求項２】
請求項１の検索可能暗号システムであって、
登録者装置をさらに有し、
前記登録者装置は、
前記検索者鍵sxuを格納する検索者鍵格納部と、前記第１値hを生成する第１写像部と、を含み、
前記検索代行装置は、
前記第１値hと前記補間鍵格納部に格納された前記補間鍵ckuとの組の像である第３値e^を生成する第３写像部をさらに含み、
前記登録者装置は、
前記第３値e^の像である前記第２値r'を生成する第２写像部と、前記第１ベクトルを用い、前記暗号方式に則って前記第２値r'を暗号化して前記暗号文cを生成する暗号化部と、前記暗号文cと前記第１値hとを含む前記タグ情報を生成するタグ情報生成部と、をさらに含む、
ことを特徴とする検索可能暗号システム。
【請求項３】
請求項１又は２の検索可能暗号システムであって、
管理者秘密鍵axを格納する管理者装置をさらに有し、
前記補間鍵ckuが前記検索者鍵sxuと前記管理者秘密鍵axとの組の像である、
ことを特徴とする検索可能暗号システム。
【請求項４】
請求項１から３の何れかの検索可能暗号システムであって、
前記検索代行装置は、
失効させる登録ユーザを示す失効情報の入力を受け付ける入力部と、前記失効情報が示す前記登録ユーザに対応する前記補間鍵ckuの前記検索代行装置での使用を禁止する制御部と、をさらに含む、
ことを特徴とする検索可能暗号システム。
【請求項５】
請求項１から４の何れかの検索可能暗号システムであって、
前記第１値hが、前記検索対象情報のキーワードをwTとし、擬似ランダム関数をHσとし、第１選択値をrwTとした場合における、
【数２８】
であり、
前記第２値r'が、前記第１値hと前記登録ユーザの補間鍵ckuとの組に双線形写像を施して得られる第３値をe^とし、第２選択値をrとした場合における、r'＝r・e^であり、
前記タグ情報がさらに前記第２選択値rを含む、
ことを特徴とする検索可能暗号システム。
【請求項６】
請求項５の検索可能暗号システムであって、
前記検証処理部は、
前記タグ情報に含まれる前記第１値hと前記補間鍵格納部に格納された前記補間鍵ckuとの組に双線形写像を施して得られる値をe~とした場合におけるmes'/e~が前記タグ情報に含まれる前記第２選択値rと等しいかを検証する、
ことを特徴とする検索可能暗号システム。
【請求項７】
暗号文に対応するベクトルと鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該鍵で復号可能な暗号方式を用いた検索可能暗号方法であって、
検索装置で、登録ユーザの属性に対応するベクトルと検索キーワードに対応するベクトルとを含む第２ベクトルに対応する鍵である検索クエリを前記暗号方式に則って生成する検索クエリ生成ステップと、
登録ユーザの補間鍵ckuを格納する検索代行装置で、前記検索クエリを鍵として暗号化データベースのタグ情報に含まれる暗号文cを復号して得られる復号値mes'が、当該タグ情報に含まれる前記第１値hと前記補間鍵ckuとに対応するかを検証するステップと、有し、
前記暗号化データベースは、
検索対象情報に対応する前記タグ情報とを含み、前記タグ情報が第１ベクトルに対応する前記暗号文cと登録ユーザの検索者鍵sxuの像である前記第１値hとを含み、前記第１ベクトルが前記登録ユーザの属性に対して設定されたベクトルと前記検索対象情報のキーワードに対して設定されたベクトルとを含み、前記暗号文cが前記第１値hと前記登録ユーザの補間鍵ckuとの組の像である第２値r'を前記暗号方式に則って暗号化した暗号文である、
ことを特徴とする検索可能暗号方法。
【請求項８】
請求項１から６の何れかの検索可能暗号システムが有するストレージ装置。
【請求項９】
請求項１から６の何れかの検索可能暗号システムが有する検索装置。
【請求項１０】
請求項２の検索可能暗号システムが有する登録者装置。
【請求項１】
暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な暗号方式を用いた検索可能暗号システムであって、
ストレージ装置と検索装置と検索代行装置とを有し、
前記ストレージ装置は、
検索対象情報に対応するタグ情報を含む暗号化データベースを格納する暗号化データベース格納部を含み、前記タグ情報が第１ベクトルに対応する暗号文cと登録ユーザの検索者鍵sxuの像である第１値hとを含み、前記第１ベクトルが前記登録ユーザの属性に対して設定されたベクトルと前記検索対象情報のキーワードに対して設定されたベクトルとを含み、前記暗号文cが前記第１値hと前記登録ユーザの補間鍵ckuとの組の像である第２値r'を前記暗号方式に則って暗号化した暗号文であり、
前記検索装置は、
第２ベクトルに対応する復号鍵である検索クエリを前記暗号方式に則って生成する検索クエリ生成部を含み、前記第２ベクトルが登録ユーザの属性に対応するベクトルと検索キーワードに対応するベクトルとを含み、
前記検索代行装置は、
前記登録ユーザの補間鍵ckuを格納する補間鍵格納部と、前記検索クエリを復号鍵として前記暗号化データベースの前記タグ情報に含まれる前記暗号文cを復号して得られる復号値decが、当該タグ情報に含まれる前記第１値hと当該補間鍵格納部に格納された前記補間鍵ckuとの組に対応するかを検証する検証処理部と、を含む、
ことを特徴とする検索可能暗号システム。
【請求項２】
請求項１の検索可能暗号システムであって、
登録者装置をさらに有し、
前記登録者装置は、
前記検索者鍵sxuを格納する検索者鍵格納部と、前記第１値hを生成する第１写像部と、を含み、
前記検索代行装置は、
前記第１値hと前記補間鍵格納部に格納された前記補間鍵ckuとの組の像である第３値e^を生成する第３写像部をさらに含み、
前記登録者装置は、
前記第３値e^の像である前記第２値r'を生成する第２写像部と、前記第１ベクトルを用い、前記暗号方式に則って前記第２値r'を暗号化して前記暗号文cを生成する暗号化部と、前記暗号文cと前記第１値hとを含む前記タグ情報を生成するタグ情報生成部と、をさらに含む、
ことを特徴とする検索可能暗号システム。
【請求項３】
請求項１又は２の検索可能暗号システムであって、
管理者秘密鍵axを格納する管理者装置をさらに有し、
前記補間鍵ckuが前記検索者鍵sxuと前記管理者秘密鍵axとの組の像である、
ことを特徴とする検索可能暗号システム。
【請求項４】
請求項１から３の何れかの検索可能暗号システムであって、
前記検索代行装置は、
失効させる登録ユーザを示す失効情報の入力を受け付ける入力部と、前記失効情報が示す前記登録ユーザに対応する前記補間鍵ckuの前記検索代行装置での使用を禁止する制御部と、をさらに含む、
ことを特徴とする検索可能暗号システム。
【請求項５】
請求項１から４の何れかの検索可能暗号システムであって、
前記第１値hが、前記検索対象情報のキーワードをwTとし、擬似ランダム関数をHσとし、第１選択値をrwTとした場合における、
【数２８】
であり、
前記第２値r'が、前記第１値hと前記登録ユーザの補間鍵ckuとの組に双線形写像を施して得られる第３値をe^とし、第２選択値をrとした場合における、r'＝r・e^であり、
前記タグ情報がさらに前記第２選択値rを含む、
ことを特徴とする検索可能暗号システム。
【請求項６】
請求項５の検索可能暗号システムであって、
前記検証処理部は、
前記タグ情報に含まれる前記第１値hと前記補間鍵格納部に格納された前記補間鍵ckuとの組に双線形写像を施して得られる値をe~とした場合におけるmes'/e~が前記タグ情報に含まれる前記第２選択値rと等しいかを検証する、
ことを特徴とする検索可能暗号システム。
【請求項７】
暗号文に対応するベクトルと鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該鍵で復号可能な暗号方式を用いた検索可能暗号方法であって、
検索装置で、登録ユーザの属性に対応するベクトルと検索キーワードに対応するベクトルとを含む第２ベクトルに対応する鍵である検索クエリを前記暗号方式に則って生成する検索クエリ生成ステップと、
登録ユーザの補間鍵ckuを格納する検索代行装置で、前記検索クエリを鍵として暗号化データベースのタグ情報に含まれる暗号文cを復号して得られる復号値mes'が、当該タグ情報に含まれる前記第１値hと前記補間鍵ckuとに対応するかを検証するステップと、有し、
前記暗号化データベースは、
検索対象情報に対応する前記タグ情報とを含み、前記タグ情報が第１ベクトルに対応する前記暗号文cと登録ユーザの検索者鍵sxuの像である前記第１値hとを含み、前記第１ベクトルが前記登録ユーザの属性に対して設定されたベクトルと前記検索対象情報のキーワードに対して設定されたベクトルとを含み、前記暗号文cが前記第１値hと前記登録ユーザの補間鍵ckuとの組の像である第２値r'を前記暗号方式に則って暗号化した暗号文である、
ことを特徴とする検索可能暗号方法。
【請求項８】
請求項１から６の何れかの検索可能暗号システムが有するストレージ装置。
【請求項９】
請求項１から６の何れかの検索可能暗号システムが有する検索装置。
【請求項１０】
請求項２の検索可能暗号システムが有する登録者装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１２−７９１９２（Ｐ２０１２−７９１９２Ａ）
【公開日】平成２４年４月１９日（２０１２．４．１９）
【国際特許分類】
【出願番号】特願２０１０−２２５４５１（Ｐ２０１０−２２５４５１）
【出願日】平成２２年１０月５日（２０１０．１０．５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年４月１９日（２０１２．４．１９）
【国際特許分類】
【出願日】平成２２年１０月５日（２０１０．１０．５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]