説明

検索可能暗号システム、ストレージ装置、それを検索する装置、検索可能暗号方法、及びプログラム

【課題】少ない演算回数で検索を行うことが可能な検索可能暗号技術を提供する。
【解決手段】予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する第1暗号方式の第1暗号文(T(indt,1),…,T(indt,N))(Nは正整数)を含む暗号化データベースを格納しておく。検索用キーワードに対応するベクトルに対応する第1暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆{1,…,maxt}についての第1暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できるかを判定する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、暗号化されたデータベースの検索が可能な検索可能暗号技術に関する。
【背景技術】
【0002】
検索対象文書からあらかじめキーワードを抽出し、それらのキーワードの暗号文を含むデータベースを構成し、各キーワードが暗号化されたままの状態で部分一致検索を行って検索結果を得る検索可能暗号方式が非特許文献1,2に開示されている。非特許文献1,2では、暗号化条件や復号条件を述語論理で記述することが可能な述語暗号方式(例えば、非特許文献3から6参照)を利用して検索可能暗号方式を実現している。すなわち、非特許文献1,2では、検索対象文書が含む各キーワードの暗号文をタグ情報としてデータベースに格納しておき、検索するキーワードが述語論理を満たす場合にタグ情報が復号できる秘密鍵を検索クエリとして生成し、この検索クエリで各タグ情報を復号できるかどうかでヒットしたかどうかを判定している。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】R. Yoshida, A. Nagai, and T. Kobayashi, “Hierarchical Predicate Encryption with Keyword Search in Multi-user Setting,” In Computer Security Symposium, 2010.
【非特許文献2】R. Yoshida, S. Oda, and T. Kobayashi., "Public-key encryption with partial matching keyword search," In Symp. on Cryptography and Information Security, 2010.
【非特許文献3】J. Katz, A. Sahai, and B. Waters., "Predicate encryption supporting disjunctions, polynomial equations, and inner products," In EUROCRYPT, pp. 146-162, 2008.
【非特許文献4】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.
【非特許文献5】T. Okamoto and K. Takashima., "Hierarchical predicate encryption for inner-products," In ASIACRYPT, pp. 214-231, 2009.
【非特許文献6】E. Shi and B. Waters, “Delegating Capabilities in Predicate Encryption Systems,” In ICALP (2), pp. 560-578, 2008.
【発明の概要】
【発明が解決しようとする課題】
【0004】
しかしながら、従来の方式では、タグ情報ごとに検索クエリで復号可能か否かを判定するため、検索を行うための演算回数が多い。
【0005】
本発明はこのような点に鑑みてなされたものであり、従来よりも少ない演算回数で検索を行うことが可能な検索可能暗号技術を提供する。
【課題を解決するための手段】
【0006】
予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する第1暗号方式の第1暗号文(T(indt,1),…,T(indt,N))(Nは正整数)を含む暗号化データベースを格納しておく。検索用キーワードに対応するベクトルに対応する第1暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆{1,…,maxt}についての第1暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できるかを判定する。なお第1暗号方式は、暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な方式である。
【発明の効果】
【0007】
本発明では、検索クエリを用い、キーワードの全体集合から検索対象情報TAR(indt)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する第1暗号文(T(indt,1),…,T(indt,N))をinds∈sub⊆{1,…,maxt}についてまとめて検証することになる。これは、inds∈subの各検索対象情報TAR(inds)が検索用キーワードにヒットしないかをまとめて検証することを意味する。よって、暗号化データベースが含む検索対象情報TAR(indt)に対応するキーワードの多くが検索用キーワードにヒットしないと仮定すると、従来よりも少ない演算回数で検索を行うことができるといえる。
【図面の簡単な説明】
【0008】
【図1】図1は、第1実施形態の検索可能暗号システムの全体構成を例示するための図である。
【図2】図2Aは、第1実施形態の管理装置の機能構成を例示するための図である。図2Bは、第1実施形態の登録装置の機能構成を例示するための図である。
【図3】図3は、第1実施形態のストレージ装置の機能構成を例示するための図である。
【図4】図4は、第1実施形態の暗号化データベース格納部に格納される暗号化データベース(否定タグ情報含む)のデータ構成を例示するための図である。
【図5】図5は、第1実施形態の暗号化データベース格納部に格納される暗号化データベース(肯定タグ情報含む)のデータ構成を例示するための図である。
【図6】図6は、第1実施形態の検索装置の機能構成を例示するための図である。
【図7】図7は、第1実施形態のデータベース登録の処理を例示するためのフローチャートである。
【図8】図8は、第1実施形態の検索処理を例示するためのフローチャートである。
【図9】図9は、第1実施形態の検索処理を例示するためのフローチャートである。
【図10】図10は、第1実施形態の検索処理を例示するための図である。
【図11】図11は、第2実施形態の検索可能暗号システムの全体構成を例示するための図である。
【図12】図12A及びBは、第2実施形態の管理装置の機能構成を例示するための図である。
【図13】図13は、第2実施形態の登録装置の機能構成を例示するための図である。
【図14】図14Aは、第2実施形態の検索代行装置の機能構成を例示するための図である。図14Bは、第2実施形態のストレージ装置の機能構成を例示するための図である。
【図15】図15Aは、第2実施形態の暗号化データベース格納部に格納される暗号化データベース(否定タグ情報含む)のデータ構成を例示するための図である。図15Bは、第2実施形態の暗号化データベース格納部に格納される暗号化データベース(肯定タグ情報含む)のデータ構成を例示するための図である。
【図16】図16は、一括方式によって鍵情報kM*を生成する処理を例示するためのフローチャートである。
【図17】図17は、委託方式によって鍵情報kM*を生成する処理を例示するためのフローチャートである。
【図18】図18は、委託方式によって鍵情報kM*を生成する処理を例示するためのフローチャートである。
【図19】図19は、データベース登録の処理を例示するためのフローチャートである。
【図20】図20は、データベース登録の処理を例示するためのフローチャートである。
【図21】図21は、検索処理を例示するためのフローチャートである。
【発明を実施するための形態】
【0009】
以下、図面を参照して本発明の実施形態を説明する。
【0010】
〔概要〕
以下に説明する各実施形態では、暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な暗号方式(第1暗号方式)を用いて検索可能暗号方式を構成する。このような暗号方式の例は、非特許文献3から6などに開示されている内積述語暗号方式や階層的内積述語暗号方式などの述語暗号方式などである。第1暗号方式が述語暗号方式の例では、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0であるときに当該暗号文が当該復号鍵で復号できる。本発明で利用する第1暗号方式は非特許文献3から6に開示された方式に限定されず、これらと同様な性質を有するどのような方式が用いられてもよい。
【0011】
各実施形態では、予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する第1暗号方式の第1暗号文(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}となる(詳細は後述)。
【0012】
暗号化データベースの検索処理は、検索用キーワードに対応するベクトルに対応する第1暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆{1,…,maxt}についての第1暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できるかを判定する処理を含む。
【0013】
ここで、暗号化データベースが含む第1暗号文(T(indt,1),…,T(indt,N))は、予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する第1暗号方式の暗号文である。また、検索クエリは検索用キーワードに対応するベクトルに対応する第1暗号方式の復号鍵である。そのため、検索用キーワードが検索対象情報TAR(indt)に対応するキーワードにヒットしないときに、検索クエリで第1暗号文(T(indt,1),…,T(indt,N))が復号できる。このような復号が可能か否かの判定がinds∈sub⊆{1,…,maxt}についてまとめて実行される(バッチ検索処理)。これはinds∈subの各検索対象情報TAR(inds)が検索キーワードにヒットしないかをまとめて検証していることになる。これにより、少ない演算回数で検索用キーワードにヒットしない検索対象情報TAR(inds)を特定でき、検索対象を絞り込むことができる。その結果、暗号化データベースが含む検索対象情報TAR(indt)に対応するキーワードの多くが検索用キーワードにヒットしないと仮定すると、この方法では従来よりも少ない演算回数で検索を行うことができることになる。
【0014】
また各実施形態の例では、inds∈sub⊆{1,…,maxt}についての前記第1暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できないと判定された場合に、subの真部分集合を新たなsubとした上述のバッチ検索処理を再び実行させる。このような繰り返しにより、従来よりも少ない演算回数で検索対象を絞り込むことができる。
【0015】
また1回のバッチ検証処理の演算コストが1回の検索処理よりも大きい場合は、検索対象情報TAR(indt)ごとの検索処理に切り替えてコストを低減する手法も考えられる。この手法を実現する各実施形態の例では、さらに、検索対象情報TAR(indt)に対応するキーワードに対して設定されるベクトルに対応する第1暗号方式の第2暗号文(LT(indt,1),…,LT(indt,N))を含む第2暗号化データベースを格納しておく。subの要素数が基準値以下であり、かつ、inds∈sub⊆{1,…,maxt}についての第1暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できないと判定された場合に、検索クエリを復号鍵として用い、第2暗号文(LT(inds,1),…,LT(inds,N))(inds∈sub)が正しく復号できるかを判定する。
【0016】
ここで、第2暗号文(LT(indt,1),…,LT(indt,N))は、検索対象情報TAR(indt)に対応するキーワードに対して設定されるベクトルに対応する第1暗号方式の暗号文である。また、検索クエリは検索用キーワードに対応するベクトルに対応する第1暗号方式の復号鍵である。そのため、検索用キーワードが検索対象情報TAR(indt)に対応するキーワードにヒットするときに、検索クエリで第2暗号文(LT(indt,1),…,LT(indt,N))が正しく復号できる。これは検索対象情報TAR(indt)が絞り込まれてから、当該検索対象情報TAR(indt)が検索クエリにヒットするかを検索対象情報TAR(indt)ごとに個別に検証していることになる。一般に、複数のinds∈subの検索対象情報TAR(inds)に対する1つのバッチ検索処理の演算コストは、検索対象情報TAR(indt)ごとの1つの検索処理の演算コストよりも大きい。そのため、検索対象情報TAR(indt)が絞り込まれ、例えば1回のバッチ検証処理の演算コストが1回の検索処理よりも大きい場合は、検索対象情報TAR(indt)ごとの検索処理に切り替えるほうが全体としての演算コストを低減できる。上述の「基準値」の例は1や2以上の整数定数である。また、subをDIV個に分割して得られる各真部分集合を新たなsubとしてバッチ検索部の処理を繰り返す場合には、DIVを上述の「基準値」としてもよい。また、subの要素数が基準値以下であるという条件の代わりに、集合{1,…,maxt}の分割回数が第2基準値以上であるという条件としてもよい。或いは、subの要素数が基準値以下であるという条件の代わりに、subの要素数が基準値以下であり、かつ、集合{1,…,maxt}の分割回数が第2基準値以上であるという条件としてもよい。
【0017】
なお、上述の検索対象情報TAR(indt)に対応するキーワードに対して設定されるベクトルと特定のベクトルとが特定の論理式の真理値を偽にする関係にあるとき、上述の補集合CSET(indt)に対して設定されるベクトルと当該特定のベクトルとは当該特定の論理式の真理値を真にする関係にある。第1暗号方式が述語暗号方式の例では、上述の検索対象情報TAR(indt)に対応するキーワードに対して設定されるベクトルと特定のベクトルとの内積が0以外のときに、上述の補集合CSET(indt)に対して設定されるベクトルと当該特定のベクトルとの内積が0となる。
【0018】
また、上述の第1暗号文(T(inds,1),…,T(inds,N))の合成値は、例えば(BT(1),…,BT(N))であり、これらのBT(indN)(indN=1,…,N)は例えば
【0019】
【数1】

である。
【0020】
〔定義〕
次に、以下の各実施形態で使用される用語や記号を定義する。
【0021】
行列:「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
【0022】
(・)T:(・)Tは・の転置行列を表す。
(・)-1:(・)-1は・の逆行列を表す。
∧:∧は論理積を表す。
∨:∨は論理和を表す。
Z:Zは整数集合を表す。
sec:secはセキュリティパラメータ(sec∈Z, sec>0)を表す。
Fq:Fqは位数qの有限体を表す。位数qは1以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。
0F:0Fは有限体Fqの加法単位元(零元)を表す。一般化した加法単位元を0と表す。
1F:1Fは有限体Fqの乗法単位元を表す。一般化した乗法単位元を1と表す。
δ(i,j):δ(i,j)はクロネッカーのデルタ関数を表す。i=jの場合にδ(i,j)=1Fを満たし、i≠jの場合にδ(i,j)=0Fを満たす。
E:Eは有限体Fq上で定義された楕円曲線を表す。
【0023】
G1, G2,GT:G1, G2, GTは位数qの巡回群を表す。巡回群G1, G2の具体例は、楕円曲線Eのp等分点からなる有限集合E[p]やその部分群である。G1=G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における1のp乗根からなる有限集合である。
【0024】
なお、本形態では、巡回群G1, G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。すなわち、χ∈Fq及びΩ∈G1に対するχ・Ω∈G1は、Ω∈G1に対して巡回群G1で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G1に対するΩ12∈G1は、Ω1∈G1とΩ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。同様に、χ∈Fq及びΩ∈G2に対するχ・Ω∈G2は、Ω∈G2に対して巡回群G2で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G2に対するΩ12∈G2は、Ω1∈G2とΩ2∈G2とを被演算子として巡回群G2で定義された演算を行うことを意味する。一方、χ∈Fq及びΩ∈GTに対するΩχ∈GTは、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω12∈GTに対するΩ1・Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。
【0025】
n:nは1以上の整数を表す。
ζ:ζは1以上の整数を表す。ζの一例は2又は3である。
G1n+ζ:G1n+ζはn+ζ個の巡回群G1の直積を表す。
G2n+ζ:G2n+ζはn+ζ個の巡回群G2の直積を表す。
g1, g2,gT:g1, g2, gTは巡回群G, G1, G2, GTの生成元を表す。
V:Vはn+ζ個の巡回群G1の直積からなるn+ζ次元のベクトル空間を表す。
V*:V*はn+ζ個の巡回群G2の直積からなるn+ζ次元のベクトル空間を表す。
e:eは直積G1n+ζと直積G2n+ζとの直積G1n+ζ×G2n+ζを巡回群GTに写す非退化な双線形写像(bilinear map)を表す。双線形写像eは、巡回群G1のn+ζ個の元γβ(β=1,...,n+ζ)と巡回群G2のn+ζ個の元γβ*(β=1,...,n+ζ)とを入力とし、巡回群GTの1個の元を出力する。
e:G1n+ζ×G2n+ζ→GT …(1)
双線形写像eは以下の性質を満たす。
【0026】
[双線形性]すべてのΓ1∈G1n+ζ,Γ2∈G2n+ζ及びν,κ∈Fqについて以下の関係を満たす。
e(ν・Γ1,κ・Γ2)=e(Γ12)ν・κ …(2)
【0027】
[非退化性]すべてのΓ1∈G1n+ζ,Γ2∈G2n+ζを巡回群GTの単位元に写すものではない。
【0028】
[計算可能性]あらゆる
Γ1∈G1n+ζ,Γ2∈G2n+ζ …(3)
についてe(Γ12)を効率的に計算するアルゴリズムが存在する。
【0029】
本形態では、巡回群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の1個の元
e=Πβ=1n+ζPair(γβ, γβ*) …(5)
を出力する。
【0030】
なお、双線形写像Pairは、巡回群G1の1個の元と巡回群G2の1個の元との組を入力とし、巡回群GTの1個の元を出力するものであり、以下の性質を満たす。
【0031】
[双線形性]すべてのΩ1∈G1,Ω2∈G2及びν,κ∈Fqについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω12)ν・κ …(6)
【0032】
[非退化性]すべての
Ω1∈G1,Ω2∈G2 …(7)
を巡回群GTの単位元に写すものではない。
【0033】
[計算可能性]あらゆるΩ1∈G1,Ω2∈G2についてPair(Ω12)を効率的に計算するアルゴリズムが存在する。
【0034】
なお、双線形写像Pairの具体例は、WeilペアリングやTateペアリングなどのペアリングである(例えば、参考文献1「Alfred. J. Menezes,ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS, KLUWER ACADEMIC PUBLISHERS, ISBN0-7923-9368-6,pp. 61-81」、参考文献2「RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems」等参照)。
【0035】
ai(i=1,...,n+ζ):aiは巡回群G1のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ1・g1∈G1をi次元目の要素とし、残りのn個の要素を巡回群G1の単位元(加法的に「0」と表現)とするn+ζ次元の基底ベクトルである。この場合、n+ζ次元の基底ベクトルai(i=1,...,n+ζ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
【0036】
a1=(κ1・g1,0,0,...,0)
a2=(0,κ1・g1,0,...,0) …(8)
...
an+ζ=(0,0,0,...,κ1・g1)
【0037】
ここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ1=1Fである。基底ベクトルaiは直交基底であり、巡回群G1のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルai(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルaiはベクトル空間Vを張る。
【0038】
ai*(i=1,...,n+ζ):巡回群G2のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。基底ベクトルai*の一例は、κ2・g2∈G2をi次元目の要素とし、残りのn個の要素を巡回群G2の単位元(加法的に「0」と表現)とするn+ζ次元の基底ベクトルである。この場合、基底ベクトルai*(i=1,...,n+ζ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
【0039】
a1*=(κ2・g2,0,0,...,0)
a2*=(0,κ2・g2,0,...,0) …(9)
...
an+ζ*=(0,0,0,...,κ2・g2)
【0040】
ここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ2=1Fである。基底ベクトルai*は直交基底であり、巡回群G2のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルai*(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルai*はベクトル空間V*を張る。
【0041】
なお、基底ベクトルaiと基底ベクトルai*とは、0Fを除く有限体Fqの元τ=κ1・κ2について
e(ai, aj*)=gTτ・δ(i,j) …(10)
を満たす。すなわち、i=jの場合には、式(5)(6)の関係から、
e(ai, aj*)= Pair(κ1・g12・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・g12・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
を満たす。
【0042】
特に、τ=κ1・κ2=1Fである場合(例えば、κ12=1Fの場合)、
e(ai, aj*)=gTδ(i,j) …(11)
を満たす。ここで、gT0=1は巡回群GTの単位元であり、gT1=gTは巡回群GTの生成元である。この場合、基底ベクトルaiと基底ベクトルai*とは双対正規直交基底であり、ベクトル空間Vとベクトル空間V*とは、双線形写像を構成可能な双対ベクトル空間〔双対ペアリングベクトル空間(DPVS:Dual Paring Vector space)〕である。
【0043】
A:基底ベクトルai(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルai(i=1,...,n+ζ)が式(8)によって表現される場合、行列Aは、
【0044】
【数2】

となる。
【0045】
A*:基底ベクトルai*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルai*(i=1,...,n+ζ)が式(9)によって表現される場合、行列A*は、
【0046】
【数3】

となる。
【0047】
X:有限体Fqの元を要素とするn+ζ行n+ζ列の行列を表す。基底ベクトルaiの座標変換に用いられる。行列Xのi行j列(i=1,...,n+ζ,j=1,...,n+ζ)の要素をχi,j∈Fqとすると、行列Xは、
【0048】
【数4】

となる。なお、行列Xの各要素χi,jを変換係数と呼ぶ。
【0049】
X *:X *は行列Xの逆行列の転置行列X*=(X-1)Tを表す。基底ベクトルai*の座標変換に用いられる。行列X*のi行j列の要素をχi,j*∈Fqとすると、行列X*は、
【0050】
【数5】

となる。なお、行列X*の各要素χi,j*を変換係数と呼ぶ。
【0051】
この場合、n+ζ行n+ζ列の単位行列をIとするとX・(X*)T=Iを満たす。すなわち、単位行列
【0052】
【数6】

に対し、
【0053】
【数7】

【0054】
を満たす。ここで、n+ζ次元ベクトル
χi=(χi,1,...,χi,n+ζ) …(18)
χj→*=(χj,1*,...,χj,n+ζ*) …(19)
を定義する。すると、式(17)の関係から、n+ζ次元ベクトルχiとχj→*との内積は、
χi・χj→*=δ(i,j) …(20)
となる。
【0055】
bi:biは巡回群G1のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。行列Xを用いて基底ベクトルai(i=1,...,n+ζ)を座標変換することで得られる。具体的には、基底ベクトルbiは、
bij=1n+ζχi,j・aj …(21)
の演算によって得られる。例えば、基底ベクトルaj(j=1,...,n+ζ)が式(8)によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。
【0056】
bi=(χi,1・κ1・g1i,2・κ1・g1 ,...,χi,n+ζ・κ1・g1) …(22)
巡回群G1のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルbi(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。
【0057】
bi*:bi*は巡回群G2のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。行列X*を用いて基底ベクトルai*(i=1,...,n+ζ)を座標変換することで得られる。具体的には、基底ベクトルbi*は、
bi*j=1n+ζχi,j*・aj* …(23)
の演算によって得られる。例えば、基底ベクトルaj*(j=1,...,n+ζ)が式(9)によって表現される場合、基底ベクトルbi*の各要素をそれぞれ列挙して表現すると、以下のようになる。
【0058】
bi*=(χi,1*・κ2・g2i,2*・κ2・g2 ,...,χi,n+ζ*・κ2・g2) …(24)
となる。巡回群G2のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルbi*(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルbi*は前述のベクトル空間V*を張る。
【0059】
なお、基底ベクトルbiと基底ベクトルbi*とは、0Fを除く有限体Fqの元τ=κ1・κ2について
e(bi, bj*)=gTτ・δ(i,j) …(25)
を満たす。すなわち、式(5)(20)(22)(24)の関係から、
【0060】
【数8】

【0061】
を満たす。特に、τ=κ1・κ2=1Fである場合(例えば、κ12=1Fの場合)、
e(bi, bj*)=gTδ(i,j) …(26)
を満たす。この場合、基底ベクトルbiと基底ベクトルbi*とは、双対ペアリングベクトル空間(ベクトル空間Vとベクトル空間V*)の双対正規直交基底である。
【0062】
なお、式(25)の関係を満たすのであれば、式(8)(9)で例示したもの以外の基底ベクトルai及びai*や、式(21)(23)で例示したもの以外の基底ベクトルbi及びbi*を用いてもよい。
【0063】
B:Bは基底ベクトルbi(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列。B=X・Aを満たす。例えば、基底ベクトルbiが式(22)によって表現される場合、行列Bは、
【0064】
【数9】

となる。
【0065】
B*:B*は基底ベクトルbi*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。B*=X*・A*を満たす。例えば、基底ベクトルbi*(i=1,...,n+ζ)が式(24)によって表現される場合、行列B*は、
【0066】
【数10】

【0067】
となる。
【0068】
〔内積述語暗号方式〕
次に、内積述語暗号方式について説明する。内積述語暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。内積述語暗号方式では、内積が0となることと論理式の真理値が真となることとが等価である。
【0069】
[内積と論理式の真理値との関係]
内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。
【0070】
まず、「x1がη1である」という命題1と「x2がη2である」という命題2との論理和 (x11)∨(x22)を
(x11)・(x22) …(29)
という多項式で表現する。すると、各真理値と式(29)の関数値との関係は以下のようになる。
【0071】
【表1】

[表1]から分かるように、論理和(x11)∨(x22)が真である場合、式(29)の関数値は0になり、論理和(x11)∨(x22)が偽である場合、式(29)の関数値は0以外の値となる。すなわち、論理和(x11)∨(x22)が真であることと、式(29)の関数値が0となることとは等価である。よって、論理和は式(29)で表現できる。
【0072】
また、「x1がη1である」という命題1と「x2がη2である」という命題2との論理積 (x11)∧(x22)を
ι1・(x11)+ι2・(x22) …(30)
という多項式で表現する。ただし、ι1及びι2は乱数である。すると、真理値と式(30)の関数値とは以下の関係となる。
【0073】
【表2】

[表2]から分かるように、論理積 (x11)∧(x22)が真である場合、式(30)の関数値は0になり、論理積 (x11)∧(x22)が偽である場合、式(30)の関数値は0以外の値となる。すなわち、論理積 (x11)∧(x22)が真であることと、式(30)の関数値が0となることとは等価である。よって、論理積は式(30)で表現できる。
【0074】
以上から、論理和や論理積からなる任意の論理式を多項式で表現できることが分かる。例えば、論理式{(x11)∨(x22)}∧(x33)∧(x44)は、多項式
ι1・{(x11)・(x22)}+ι2・(x33)+ι3・(x44) …(31)
で表現できる。以下、このように論理式を表現する多項式のことを述語多項式と呼ぶ。
【0075】
述語多項式は2つのベクトルの内積で表現できる。すなわち、述語多項式は、各項の不定元成分と1とを各要素とするベクトルと、各項の係数成分を各要素とするベクトルとの内積に等しい。例えば、式(31)の述語多項式は、各項の不定元成分と1を各要素とするベクトル(x1・x2, x1, x2, x3, x4, 1)と、各項の係数成分を各要素とするベクトル(ι1, -ι1・η2, -ι1・η1, ι2, -ι2・η33, ι1・η1・η23・η4)との内積に等しい。
【0076】
そのため、述語多項式の値が0であるか否かと、述語多項式の各項の不定元成分と1とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。言い換えると、論理式の真理値が真であるか否かと、当該論理式を示す述語多項式の各項の不定元成分と1とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。
【0077】
内積述語暗号方式では、上述の各項の不定元成分と1を各要素とするベクトル及び各項の係数成分を各要素とするベクトルの何れか一方のベクトルが暗号文に埋め込まれ、他方のベクトルが復号鍵に埋め込まれる。以下では、暗号文に埋め込まれるベクトルをw=(w1,...,wn)とし、復号鍵に埋め込まれるベクトルをv=(v1,...,vn)とする。
【0078】
[内積述語暗号方式の基本構成]
内積述語暗号方式で鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する例を示す。この構成はSetup,GenKey,Enc,Decを含む。
【0079】
《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として出力される。
【0080】
《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)
とされた例を説明する。これは本発明を限定しない。
【0081】
《Enc:暗号化》
−入力:公開パラメータPK,ベクトルw,平文mes
−出力:暗号文(C1,C2)
Encの一例では、行列Bなどの公開パラメータPKと、有限体Fqの元である乱数υ01,...,υζと、ベクトルwとを用い、暗号文
C10・(Σμ=1nwμ・bμ)+Σμ=n+1n+ζυμ-n・bμ∈G1n+ζ …(34)
が生成される。ただし、
υ1=...=υζ' …(35)
を満たす(例えばζ'=2のときにはυ12)。また、gTτ・υ1を共通鍵Kとし、所定の共通鍵暗号方式(第2暗号方式)に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、
C2=gTτ・υ1・mes …(36)
である。添え字のυ1はυ1を意味する。前述のように定数τの一例はτ=1Fである。生成された暗号文(C1,C2)は出力される。
【0082】
《Dec:復号》
−入力:ベクトルvに対応する復号鍵D*,暗号文(C1,C2)
−出力:復号値mes'
Decの一例では、まず、暗号文C1と復号鍵D*とが式(1)の双線形写像eに入力され、その演算結果を共通鍵K=e(C1,D*)とし、以下のように復号値mes'が求められる。
【0083】
mes'=C2/e(C1,D*)∈GT …(37)
ここで、式(2)(25)(33)(35)の性質から、
【0084】
【数11】

【0085】
を満たす。
【0086】
内積w・v=0であれば、式(38)は、
【0087】
【数12】

を満たす。式(36)(37)(39)から、内積w・v=0であればmes'=mesとなり、正しく復号されることがわかる。
【0088】
[階層的内積述語暗号方式の基本構成]
階層的内積述語暗号方式は内積述語暗号方式の一種であり、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる。さらに階層的内積述語暗号方式では階層的な処理によって復号鍵を生成できる。すなわち、階層的内積述語暗号方式では属性が階層化され、各階層までの属性に対応する鍵情報が存在するとともに、上位の階層に対応する鍵情報を用いて下位の階層に対応する鍵情報を生成できる。そして、このような階層的な処理によって生成された最終的な鍵情報が復号鍵となる。以下に階層的内積述語暗号方式の基本構成を例示する。以下では、階層的内積述語暗号方式を用いて鍵カプセル化メカニズムKEMを構成する場合の基本構成を例示する。ただし、これは本発明を限定するものではない。
【0089】
《前提》
深さdの属性空間の階層フォーマットを以下の式によって定義する。ただし、dは1以上n以下の整数である。
【0090】
ξ=(n,d;ξ1,...,ξd) (0=ξ01<...<ξd=n) …(40)
有限体Fqの元を要素とするξωω-1(ω=1,...,d)次元のベクトル(零ベクトルを除く)を階層ωに対応するベクトル
【0091】
【数13】

とし、階層1から階層m(m≦d)までに対応するベクトルを(w1,...,wm)とする。有限体Fqの元を要素とするξωω-1次元(ω=1,...,d)のベクトル(零ベクトルを除く)を階層ωに対応するベクトル
【0092】
【数14】

とし、階層1から階層mまでに対応するベクトルを(v1,...,vm)とする。
【0093】
《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)が算出される。
【0094】
この例では、基底ベクトル(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として出力される。
【0095】
《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)に対応する鍵情報
【0096】
【数15】

が生成されて出力される。ただし、
【0097】
【数16】

である。
【0098】
《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である。
【0099】
Delegate(m')の一例では、有限体Fqから元σ'α,ω,Ψ',Φ'α∈Fq (α=0,...,m'+2,ξm'+1+1,...,n; ω=1,...,m'+1)が任意に選択される。この例では、これらと鍵情報km'*とベクトルvm'+1と用い、ベクトル(v1,...,vm'+1)に対応する鍵情報
【0100】
【数17】

が生成されて出力される。ただし、
【0101】
【数18】

である。
【0102】
《Enc:暗号化》
−入力:公開パラメータmpk,ベクトル(w1,...,wm),平文mes
−出力:暗号文(C1,C2)
Encの一例では、まず、有限体Fqから任意の元υ1,...,υdn+3,υが選択される。そして、これらと公開パラメータmpkとベクトル(w1,...,wm)とを用い、暗号文
【0103】
【数19】

が生成される。また、gTτ・υを共通鍵Kとし、所定の共通鍵暗号方式(第2暗号方式)に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、
C2=gTτ・υ・mes …(52)
である。なお、前述のように定数τの一例はτ=1Fである。その後、以上のように生成された暗号文(C1,C2)が出力される。
【0104】
《Dec:復号》
−入力:公開パラメータmpk,ベクトル(v1,...,vm)に対応する鍵情報km*,暗号文(C1,C2)
−出力:復号値mes'
Decの一例では、
mes'=C2/e(C1,km,0*) …(53)
によって復号値mes'を計算する。
【0105】
暗号文C1と鍵情報km*のkm,0*とが式(1)の双線形写像e(この例ではζ=3)に入力されると、式(2)(25)の性質から、
【0106】
【数20】

を満たす。なお、σω及びσは有限体Fqの元である。Delegate(m')がなされることなく鍵情報km*が生成された場合にはσω0,ωである。Delegate(m')が1回以上なされた場合には、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となり、正しく復号がなされることがわかる。
【0107】
〔第1実施形態〕
次に、本発明の第1実施形態を説明する。本形態では第1暗号方式として内積述語暗号方式を用いる。
【0108】
<構成>
図1に例示するように、本形態の検索可能暗号システム1は、管理装置110と登録装置120−u(u=1,...,U)とストレージ装置140と検索装置150−u(u=1,...,U)とを有する。なお、Uは1以上の整数である。また、登録装置120−u及び検索装置150−uは、検索可能暗号システム1を利用するu番目の登録ユーザが使用する装置である。また、各装置は他の装置へ情報を提供可能なように構成されている。装置間の情報提供はネットワークを通じて行われてもよいし、可搬型記録媒体を介して行われてもよい。
【0109】
[管理装置]
図2Aに例示するように、管理装置110は、入力部111と出力部112とマスタ秘密鍵格納部113と制御部115と鍵情報生成部116bとを有する。管理装置110は、例えば、CPU(central processing unit),RAM(random-access memory),ROM(read-only memory)などを有する公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、管理装置110は、制御部115の制御のもと各処理を実行する。管理装置110での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【0110】
[登録装置]
図2Bに例示するように、登録装置120−uは、出力部122−uと登録キーワード格納部123b−uと制御部125−uと乱数生成部126c−uとベクトル設定部126e−uと暗号化部126f−uとタグ情報生成部126g−uとを有する。登録装置120−uは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、登録装置120−uは、それぞれ、制御部125−uの制御のもと各処理を実行する。登録装置120−uでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【0111】
[ストレージ装置140]
図3に例示するように、ストレージ装置140は、入力部141と出力部142と暗号化データベース格納部143と制御部145と書込み部146とバッチ検索部147と検索部148とを有する。ストレージ装置140は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、ストレージ装置140は、制御部145の制御のもと各処理を実行する。
【0112】
図4に例示するように、暗号化データベース格納部143には、文書などの検索対象情報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に対応する第1暗号方式の第1暗号文(T(indt,1),…,T(indt,N))と、第1暗号文(T(indt,1),…,T(indt,N))の復号値を共通鍵Kとした第2暗号方式(共通鍵暗号方式)の暗号文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)の第1暗号文(T(indt,1),…,T(indt,N))は、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットしないときに当該検索クエリを復号鍵として用いて正しく復号される暗号文である。また、この正しい復号値を共通鍵Kとして暗号文T(indt)を復号した場合の復号値はRE(indt)となる。よって、検索クエリを用いて第1暗号文(T(indt,1),…,T(indt,N))を復号して得られる値を共通鍵Kとして暗号文T(indt)を復号した値がRE(indt)である場合、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットしていないことになる。検索クエリに対応する検索用キーワードが登録キーワードにヒットすることの意義は検索方式による。また、暗号文CT(TAR(indt))を生成するための検索対象情報TAR(indt)の暗号化方式には限定はなく、任意の既存の暗号化方式(共通鍵暗号方式,公開鍵暗号方式,述語暗号方式、関数暗号方式など)でよい。また、当該既存の暗号方式は、本形態の検索可能暗号を構成するための第1暗号方式と同じであっても違ってもよい。暗号化データベースの構成及び生成方法の詳細は後述する。
【0113】
図5に例示するように、暗号化データベース格納部143には、さらに暗号文CT(TAR(indt))と、検索対象情報TAR(indt)に対応する登録キーワードに対して設定されるベクトルwに対応する第1暗号方式の第2暗号文(LT(indt,1),…,LT(indt,N))と、第2暗号文(LT(indt,1),…,LT(indt,N))の復号値を共通鍵Kとした第3暗号方式(共通鍵暗号方式)の暗号文LT(indt)と、第2暗号文LT(indt)の復号値LR(indt)とが対応付けられた第2暗号化データベースが格納されている。暗号文CT(TAR(indt))にそれぞれ対応付けられる((LT(indt,1),…,LT(indt,N)), LT(indt), LR(indt))を検索対象情報TAR(indt)に対応するタグ情報LTag(indt)(肯定タグ情報)と呼ぶ。肯定タグ情報LTag(indt)の第2暗号文(LT(indt,1),…,LT(indt,N))は、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットするときに当該検索クエリを復号鍵として用いて正しく復号される暗号文である。また、この正しい復号値を共通鍵Kとして暗号文LT(indt)を復号した場合に復号値としてLR(indt)が得られる。よって、検索クエリを用いて第2暗号文(LT(indt,1),…,LT(indt,N))を復号して得られる値を共通鍵Kとして暗号文LT(indt)を復号した値がLR(indt)である場合、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットしていることになる。第2暗号化データベースの構成及び生成方法の詳細は後述する。
【0114】
[検索装置150−u]
図6に例示するように、検索装置150−uは、入力部151−uと出力部152−uと検索対象情報復号鍵格納部154−uと制御部155−uとベクトル設定部156−uと検索クエリ生成部157−uと復号部158−uとを有する。検索装置150−uは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、検索装置150−uは、それぞれ、制御部155−uの制御のもと各処理を実行する。なお、図面表記の便宜上、図6には2つの入力部151−uが記載されているが、これは入力部の種類や個数を限定するものではない。
【0115】
<事前処理>
前述した[内積述語暗号方式の基本構成]のSetupが実行され、マスタ秘密鍵MSK,公開パラメータPKが定められる。マスタ秘密鍵MSKは、管理装置110(図2A)のマスタ秘密鍵格納部113に安全に格納される。管理装置110,登録装置120−u,及び検索装置150−uは、公開パラメータPKを用いた処理が可能なように構成される。
【0116】
登録装置120−u(図2B)の登録キーワード格納部123b−uには、登録を行う検索対象情報TAR(indt)の暗号文CT(TAR(indt))と検索対象情報TAR(indt)に対応するキーワードWT(indt)とが格納されている。キーワードWT(indt)は、例えば、検索対象情報TAR(indt)に含まれるキーワード又は複数のキーワードの集合である。
【0117】
検索装置150−u(図6)の検索対象情報復号鍵格納部154−uには、登録装置120−u(図2B)の登録キーワード格納部123b−uに格納された暗号文CT(TAR(indt))を復号するための検索対象情報復号鍵Key(indt)が格納されている。
【0118】
<データベース登録>
登録ユーザは登録装置120−uを用い、図7に例示するようにデータベース登録を行う。登録されるデータベースは、図4に例示するような暗号文CT(TAR(indt))と否定タグ情報Tag(indt)とが対応付けられた暗号化データベース、及び、図5に例示するような暗号文CT(TAR(indt))と肯定タグ情報LTag(indt)とが対応付けられた第2暗号化データベースである。
【0119】
登録装置120−u(図2B)のベクトル設定部126e−uが、登録キーワード格納部123b−uから検索対象情報TAR(indt)に対応する登録キーワードWT(indt)を抽出する(ステップS101)。ベクトル設定部126e−uは、予め定められたキーワードの全体集合WSETから検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応する登録キーワードWT(indt)を除いた補集合CSET(indt)=WSET-WT(indt)に対応するベクトルwCSET∈Fqを設定する。具体的なベクトルwCSETの構成は検索方式による。以下に具体的なベクトルwCSETの構成例を示す。
【0120】
[ベクトルwCSETの構成例1(単一単語一致検索の場合)]
ベクトルwCSETの構成例1は、単一単語一致検索に対応する例である。単一単語一致検索とは、検索用キーワードの少なくとも一部と検索対象情報TAR(indt)に対応する登録キーワードの少なくとも一部とが順序及び内容について一致するという検索条件(「検索条件1」と呼ぶ)を満たした場合にヒットとされる検索方式である。すなわち単一単語一致検索では、検索対象情報TAR(indt)に対応する登録キーワードをWT(indt)={η1(indt),...,ηL(indt)}(Lは1以上の整数)とし、検索用キーワードをWQ={x1,...,xL}とした以下の述語多項式の値が0になるときにヒットとされる。
【0121】
(x11(indt))…(xLL(indt)) …(56)
この検索条件の否定を表す述語多項式を考える。すなわち、検索条件1を満たしていないとき(すなわちヒットしないとき)に0になる述語多項式を考える。この例では、キーワードの全体集合WSETから登録キーワードWT(indt)を除いた補集合CSET(indt)を以下のようにする。
【0122】
CSET(indt)={ηθ,π(indt)}=WSET-{ηθ(indt)} …(57)
ただし、θ=1,...,L、π=1,...,πmaxであり、πmaxは1以上の整数であり、ηθ,πmax(indt)=⊥であり、xθに対応するキーワードが存在しない場合に(xθ-⊥)=0を満たす。式(56)が表す検索条件の否定を表す述語多項式は以下のようになる。
【0123】
ι1(x11,1(indt))(x11,2(indt))…(x11,πmax-1(indt))(x11,πmax(indt))+…+ιL(xLL,1(indt))(xLL,2(indt))…(xLL,πmax-1(indt))(xLL,πmax(indt)) …(58)
ただし、ι1,...,ιLは乱数である。
【0124】
式(56)の述語多項式の値が0となるとき(ヒットするとき)、式(58)の述語多項式の値は0以外となる。式(56)の述語多項式の値が0以外となるとき(ヒットしないとき)、式(58)の述語多項式の値は0となる。式(58)は以下のように変形できる。
【0125】
【数21】

ただし、SYθ,π'(indt)は(-ηθ,π(indt))に関するπ'次の基本対称式である。
【0126】
ベクトルwCSETの構成例1では、式(59)の(x1πmax … xL0)がベクトル
wCSET=(x1πmax … xL0) …(60)
として設定される。
【0127】
[ベクトルwCSETの構成例2(部分集合判定検索の場合)]
ベクトルwCSETの構成例2は、部分集合判定検索に対応する例である。部分集合判定検索とは、検索用キーワードの少なくとも一部と検索対象情報TAR(indt)に対応する登録キーワードの少なくとも一部とが順序にかかわらず内容について一致するという検索条件(「検索条件2」と呼ぶ)を満たした場合にヒットとされる検索方式である。すなわち部分集合判定検索では、検索対象情報TAR(indt)に対応する登録キーワードをWT(indt)={η1(indt),...,ηL(indt)}(Lは1以上の整数)とし、検索用キーワードをWQ={x1,...,xL}とした以下の述語多項式の値が0になるときにヒットとされる。
【0128】
(x11(indt))(x21(indt))…(xL1(indt))+
… +(x1L(indt))(x2L(indt))…(xLL(indt)) …(61)
この検索条件の否定を表す述語多項式を考える。すなわち、検索条件2を満たしていないとき(すなわちヒットしないとき)に0になる述語多項式を考える。この例では、キーワードの全体集合WSETから登録キーワードWT(indt)を除いた補集合CSET(indt)を以下のようにする。
【0129】
CSET(indt)={ηπ(indt)}=WSET-{η1(indt),...,ηL(indt)}
ただし、π=1,...,πmaxであり、πmaxは1以上の整数であり、ηθ(indt)(L+1≦θ≦πmax)は前述の⊥である。式(61)が表す検索条件の否定を表す述語多項式は以下のようになる。
【0130】
ι1(x11(indt))(x21(indt))…(xL1(indt))+…+ιL(x1L(indt))(x2L(indt))…(xLL(indt)) …(62)
ただし、ι1,...,ιLは乱数である。
【0131】
式(61)の述語多項式の値が0となるとき(ヒットするとき)、式(62)の述語多項式の値は0以外となる。式(61)の述語多項式の値が0以外となるとき(ヒットしないとき)、式(62)の述語多項式の値は0となる。式(62)は以下のように変形できる。
【0132】
【数22】

ただし、SYπ'(indt)は(-ηθ(indt))に関するπ'次の基本対称式である
ベクトルwCSETの構成例2では、式(63)の(x'0… x'πmax)がベクトル
wCSET=(x'0 … x'πmax) …(64)
として設定される(ベクトルwCSETの構成例の説明終わり/ステップS102)。
【0133】
ベクトルwCSETは暗号化部126f−uに入力される。暗号化部126f−uは、第1暗号方式に則ってベクトルwCSETに対応する第1暗号文(T(indt,1),…,T(indt,N))を生成する。本形態の暗号化部126f−uは、wCSET=(w1,...,wn)とした式(34)に従って、以下のような第1暗号文(T(indt,1),…,T(indt,N))を生成する。
【0134】
C1=(T(indt,1),…,T(indt,N))∈G1n+ζ …(65)
ただし、この例ではN=n+ζである(ステップS103)。
【0135】
乱数生成部126c−uはRE(indt)∈GTをランダムに生成し、RE(indt)を暗号化部126f−uに送る。暗号化部126f−uは、gTτ・υ1を共通鍵Kとし、第2暗号方式に則ってRE(indt)を暗号化した暗号文T(indt)を生成する。例えば、暗号化部126f−uは、mes=RE(indt)とした式(36)に従い、以下のように暗号文T(indt)を生成する。
【0136】
C2=T(indt)=gTτ・υ1・RE(indt)∈GT …(66)
このように生成された(T(indt,1),…,T(indt,N))、T(indt)及びRE(indt)はタグ情報生成部126g−uに送られる(ステップS104)。
【0137】
タグ情報生成部126g−uは、(T(indt,1),…,T(indt,N))、T(indt)及びRE(indt)を互いに対応付けた否定タグ情報Tag(indt)を以下のように生成する。
【0138】
Tag(indt)=((T(indt,1),…,T(indt,N)), T(indt), RE(indt)) …(67)
否定タグ情報Tag(indt)は出力部122−uに送られる(ステップS105)。
【0139】
また、ベクトル設定部126e−uは、検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応する登録キーワードWT(indt)に対応するベクトルwT∈Fqを設定する。具体的なベクトルwTの構成は検索方式による。以下に具体的なベクトルwTの構成例を示す。
【0140】
[ベクトルwTの構成例1(単一単語一致検索の場合)]
ベクトルwTの構成例1は、前述した単一単語一致検索に対応する例である。前述のように単一単語一致検索では、検索対象情報TAR(indt)に対応する登録キーワードをWT(indt)={η1(indt),...,ηL(indt)}(Lは1以上の整数)とし、検索用キーワードをWQ={x1,...,xL}とした式(56)の述語多項式の値が0になるときにヒットとされる。式(56)もその各項の不定元成分(x1,...,xL)と1Fとを各要素とするベクトルw=(w1,...,wn)と各項の係数成分を各要素とするベクトルv=(v1,...,vn)との内積に変形できる。ベクトルwTの構成例1では、そのベクトルw=(w1,...,wn)がベクトルwTとして設定される。
【0141】
[ベクトルwTの構成例2(部分集合判定検索の場合)]
ベクトルwTの構成例2は、前述の部分集合判定検索に対応する例である。前述のように部分集合判定検索では、検索対象情報TAR(indt)に対応する登録キーワードをWT(indt)={η1(indt),...,ηL(indt)}(Lは1以上の整数)とし、検索用キーワードをWQ={x1,...,xL}とした式(61)の述語多項式の値が0になるときにヒットとされる。式(61)もその各項の不定元成分(x1,...,xL)と1Fとを各要素とするベクトルw=(w1,...,wn)と各項の係数成分を各要素とするベクトルv=(v1,...,vn)との内積に変形できる。ベクトルwTの構成例2では、そのベクトルw=(w1,...,wn)がベクトルwTとして設定される(ベクトルwTの構成例の説明終わり/ステップS106)。
【0142】
ベクトルwTは暗号化部126f−uに入力される。暗号化部126f−uは、第1暗号方式に則ってベクトルwTに対応する第2暗号文(LT(indt,1),…,LT(indt,N))を生成する。本形態の暗号化部126f−uは、wT=(w1,...,wn)とした式(34)に従って、以下のように第2暗号文(LT(indt,1),…,LT(indt,N))を生成する。
【0143】
C1=(LT(indt,1),…,LT(indt,N))∈G1n+ζ …(68)
ただし、この例ではN=n+ζである(ステップS107)。
【0144】
乱数生成部126c−uはRE(indt)∈GTをランダムに生成し、RE(indt)を暗号化部126f−uに送る。暗号化部126f−uは、gTτ・υ1を共通鍵Kとし、第2暗号方式に則ってLR(indt)を暗号化した暗号文LT(indt)を生成する。例えば、暗号化部126f−uは、mes=LR(indt)とした式(36)に従い、以下のように暗号文LT(indt)を生成する。
【0145】
C2=LT(indt)=gTτ・υ1・LR(indt)∈GT …(69)
このように生成された(LT(indt,1),…,LT(indt,N))、LT(indt)及びLR(indt)はタグ情報生成部126g−uに送られる(ステップS108)。
【0146】
タグ情報生成部126g−uは、(LT(indt,1),…,LT(indt,N))、LT(indt)及びLR(indt)を互いに対応付けた肯定タグ情報LTag(indt)を以下のように生成する。
【0147】
LTag(indt)=((LT(indt,1),…,LT(indt,N)), LT(indt), LR(indt)) …(70)
肯定タグ情報LTag(indt)は出力部122−uに送られる(ステップS109)。
【0148】
出力部122−uには、さらに前述の否定タグ情報LTag(indt)、及び登録キーワード格納部123b−uから読み出された検索対象情報TAR(indt)の暗号文CT(TAR(indt))が送られる。出力部122−uは、CT(TAR(indt))、LTag(indt)及びLTag(indt)を出力する(ステップS110)。
【0149】
CT(TAR(indt))、LTag(indt)及びLTag(indt)はストレージ装置(図3)の入力部141に入力される。書込み部146はCT(TAR(indt))、LTag(indt)及びLTag(indt)を互いに対応付け、図4及び5に示したように暗号化データベース格納部143に格納する(ステップS111)。
【0150】
<バッチ検索用の事前計算>
ストレージ装置(図3)のバッチ検索部147は、後述するバッチ検索のために以下のような事前計算を行う。この事前計算は定期的に行われてもよいし、暗号化データベース格納部143が更新されるたびに行われてもよい。或いは、暗号化データベース格納部143の更新後に後述するバッチ検索が始めて実行されるときに行われてもよい。以下では暗号化データベース格納部143に、indt=1,…,maxt(maxt≧2)についてのCT(TAR(indt))及びTag(indt)が互いに対応付けられて格納されていることを前提とする(図4参照)。
【0151】
バッチ検索部147は、まずsub={1,…,maxt}とし、indN=1,…,Nについて式(71)-(73)を事前計算し、BT(indN)(indN=1,…,N)、BT、及びREをsubに対応付けて暗号化データベース格納部143に格納する。
【0152】
【数23】

同様にsubを分割して得られるsubの真部分集合のそれぞれを新たなsubとし、indN=1,…,Nについて式(71)-(73)が事前計算され、BT(indN)(indN=1,…,N)、BT、及びREがsubに対応付けられて暗号化データベース格納部143に格納される処理が繰り返される。subの分割方法や分割回数はストレージ装置140で事前に定められ、この分割方法や分割回数は後述のバッチ検索にも対応する。ただし、どのような分割方法や分割回数が設定されるかについての限定はない。subの分割方法の例は、subをDIV個(DIVは2や3などの正整数)の真部分集合に分割する方法などである。subの分割回数の例は、subを分割して得られる新たなsubの要素数が基準値以下になるまで分割する方法や、事前に定められた固定回数まで分割する方法などである。例えば、subを2つの真部分集合に分割してsubを更新し、subの分割回数を2回とするのであれば、例えば、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)の事前計算値が暗号化データベース格納部143に格納される(図4参照)。
【0153】
<検索>
登録ユーザは検索装置150−u(図6)を用い、以下のようにストレージ装置140に格納された暗号化データベースを検索する。
【0154】
図8に例示するように、まず検索を行う登録ユーザによって選択された検索用キーワードWQが入力部151−uに入力される(ステップS121)。検索用キーワードWQはベクトル設定部156−uに送られる。ベクトル設定部156−uは、システム内で定められた規則に従い、否定タグ情報Tag(indt)及び肯定タグ情報LTag(indt)のそれぞれに対し、検索方式と検索用キーワードWQに対応する第2ベクトルvQを設定する。
【0155】
否定タグ情報Tag(indt)に対応する第2ベクトルvQは、検索方式と検索用キーワードWQとの組に対して第1ベクトルwTに対応する登録キーワードWT(indt)がヒットする場合に内積wT・vQ≠0を満たし、ヒットしない場合に内積wT・vQ=0を満たすものである。例えば、前述のベクトルwCSETの構成例1の場合、ベクトル設定部156−uは、式(59)が含む以下のベクトルを第2ベクトルvQとする。
【0156】
1・SY1,0(indt),…,ι1・SY1,πmax(indt),ι2・SY2,0(indt),…,ι2・SY2,πmax(indt),…,ιL・SYL,πmax(indt)) …(74)
或いは、前述のベクトルwCSETの構成例2の場合、式(59)が含む以下のベクトルを第2ベクトルvQとする。
【0157】
(SY0(indt),…,SYπmax(indt)) …(75)
肯定タグ情報Tag(indt)に対応する第2ベクトルvQは、検索方式と検索用キーワードWQとの組に対して第1ベクトルwTに対応する登録キーワードWT(indt)がヒットする場合に内積wT・vQ=0を満たし、ヒットしない場合に内積wT・vQ≠0を満たすものである。例えば、ベクトルwTの構成例1の場合、式(56)を各項の不定元成分(x1,...,xL)と1Fとを各要素とするベクトルw=(w1,...,wn)と各項の係数成分を各要素とするベクトルv=(v1,...,vn)との内積に変形した場合のベクトルvを第2ベクトルvQとする。或いは、ベクトルwTの構成例2の場合、式(61)を各項の不定元成分(x1,...,xL)と1Fとを各要素とするベクトルw=(w1,...,wn)と各項の係数成分を各要素とするベクトルv=(v1,...,vn)との内積に変形した場合のベクトルvを第2ベクトルvQとする(ステップS122)。
【0158】
否定タグ情報Tag(indt)及び肯定タグ情報LTag(indt)のそれぞれに設定された第2ベクトルvQは検索クエリ生成部157−uに送られる。検索クエリ生成部157−uは、出力部152−uを介して管理装置110にアクセスし、管理装置110(図2A)に否定タグ情報Tag(indt)及び肯定タグ情報LTag(indt)のそれぞれに設定された第2ベクトルvQを送る。これらは管理装置110の入力部111に入力され、鍵情報生成部116aに送られる。鍵情報生成部116aは、マスタ秘密鍵格納部113に格納されたマスタ鍵情報MSKを用い、否定タグ情報Tag(indt)に対する第2ベクトルvQに対応する第1暗号方式の復号鍵である検索クエリQUE(Tag)と、肯定タグ情報LTag(indt)に対する第2ベクトルvQに対応する第1暗号方式の復号鍵である検索クエリQUE(LTag)とをそれぞれ生成する。これらはvQ=(v1,...,vn)とした式(32)に従ってそれぞれ生成できる。
【0159】
Tag(indt)=(que1,…,queN)∈G2n+ζ …(76)
LTag(indt)=(Lque1,…,LqueN)∈G2n+ζ …(77)
ただし、n+ζ=Nであり、ζ>ζ'の場合には、
queN-(ζ-ζ')=…=queN=0
LqueN-(ζ-ζ')=…=LqueN=0
とされる。検索クエリQUE(Tag)と検索クエリQUE(LTag)は出力部112から出力され、検索装置150−u(図6)の入力部151−u経由で検索クエリ生成部157−uに送られる(ステップS123)。
【0160】
生成された検索クエリQUE(Tag)及びQUE(LTag)は出力部152−uに送られ、出力部152−uはこれらを出力する(ステップS124)。
【0161】
図9に示すように、検索クエリQUE(Tag)及びQUE(LTag)はストレージ装置140(図3)の入力部141に入力され、バッチ検索部147と検索部148にそれぞれ送られる(ステップS131)。
【0162】
制御部145は、まずsub={1,…,maxt}とする(ステップS132)。バッチ検索部147は、否定タグ情報Tag(indt)に対する検索クエリQUE(Tag)を用い、暗号化データベース格納部143に格納された否定タグ情報Tag(inds)(inds∈sub)をまとめてバッチ検証する。すなわち、検索クエリQUE(Tag)を用い、inds∈sub⊆{1,…,maxt}についての第1暗号文(T(inds,1),…,T(inds,N))の合成値(式(71))が正しく復号できるかを判定する。具体的には本形態のバッチ検索部147は、検索クエリQUE(Tag)を復号鍵として用い、inds∈subについての第1暗号文(T(inds,1),…,T(inds,N))の関数値(BT(1),…,BT(N))(式(71))を第1暗号方式に則って復号して得られる値を共通鍵とし、inds∈subについての暗号文T(inds)の関数値BT(式(72))を第2暗号方式に則って復号して得られる値がinds∈subについての復号値RE(inds)の関数値RE(式(73))であるか(true)否か(false)を判定する。例えば、式(65)(66)のような計算で否定タグ情報Tag(inds)が得られたのであれば、バッチ検索部147は、以下を満たすか(true)否か(false)を判定する。
【0163】
【数24】

原則、この判定を行うために必要な(BT(1),…,BT(N))、BT、及びREは、前述の事前計算で得られたものである。ただし、必要な(BT(1),…,BT(N))、BT、及びREが格納されていないのであれば、バッチ検索部147はそれらを計算してこの判定を行い、以降の処理のためにそれらの値を暗号化データベース格納部143に格納しておいてもよい。また、式(78)によって否定タグ情報Tag(inds)(inds∈sub)をまとめてバッチ検証できるのは、次の関係が成り立つことに立脚している。
【0164】
【数25】

式(79)の右辺は式(78)の左辺の分母である。この事実は前述した双線形写像Pairの線形性(式(6)参照)から成り立つ(ステップS133)。
【0165】
ステップS133の判定でtrueと判定された場合には(ステップS134)、検索用キーワードWQに対して何れの検索対象情報TAR(inds)(inds∈sub)もヒットしないことになる。この場合にはinds∈subに対応する各検索対象情報TAR(inds)に対する検索が終了し、ステップS139へ進む。一方、ステップS133の判定でfalseと判定された場合(inds∈sub⊆{1,…,maxt}についての第1暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できないと判定された場合)には(ステップS134)、検索用キーワードWQに対して何れの検索対象情報TAR(inds)(inds∈sub)がヒットすることになる。この場合にはステップS135に進み、subの要素数が基準値以下であるかが判定される。なお、「基準値」の例は1や2以上の整数定数やDIVなどである(ステップS135)。
【0166】
ステップS135でsubの要素数が基準値以下ではないと判定された場合には、subを分割して得られるsubの真部分集合のそれぞれを新たなsubとし、ステップS133に戻る。なお、ここでのsubの分割方法は、例えば前述のバッチ検索用の事前計算でのsubの分割方法と同一とする(ステップS136)。
【0167】
一方、ステップS135でsubの要素数が基準値以下であると判定された場合、検索クエリQUE(LTag)を用いた肯定タグ情報LTag(indt)の検証に切り替えられる。すなわち、検索部148が検索クエリQUE(LTag)(第2検索クエリ)を復号鍵として用い、第2暗号文(LT(inds,1),…,LT(inds,N))(inds∈sub)が正しく復号できるかを判定する。本形態の検索部148は検索クエリQUE(LTag)を復号鍵として用い、肯定タグ情報LTag(indt)が含む第2暗号文(LT(inds,1),…,LT(inds,N))(inds∈sub)(図5)を第1暗号方式に則って復号して得られる値を共通鍵とし、暗号文LT(inds)を第3暗号方式に則って復号して得られる値が復号値LR(inds)であるかを判定する。例えば、式(68)(69)のような計算で肯定タグ情報LTag(inds)が得られたのであれば、検索部148は、以下を満たすか(true)否か(false)を判定する。
【0168】
【数26】

これは、検索対象情報TAR(inds)が検索用キーワードWQにヒットするか(true)否か(false)を肯定タグ情報LTag(inds)ごとに判定することに相当する(ステップS137)。
【0169】
検索部148は、ステップS137の判定でtrueと判定された肯定タグ情報LTag(inds)のindsに対応する暗号文CT(TAR(inds))を集合HITに追加し、図示しないメモリに格納し(ステップS138)、ステップS139に進む。
【0170】
ステップS139では、制御部145が未検証のsubが存在するかを判定する(ステップS139)。ここで、未検証のsubが存在すると判定された場合には、ステップS133に進む。一方、未検証のsubが存在しないと判定された場合には、検索部148は、集合HITの要素である暗号文CT(TAR(indt))を出力する。集合HITの要素が存在しなければ検索部148は、ヒットしなかったことを表す⊥を出力する(ステップS140)。これらは出力部142から出力される。
【0171】
図8に示すように、集合HITの要素である暗号文CT(TAR(indt))又は⊥は、検索装置(図6)の入力部151−uに入力される(ステップS125)。暗号文CT(TAR(indt))は、復号部158−uに送られる。復号部158−uは検索対象情報復号鍵格納部154−uから検索対象情報復号鍵Key(indt)を読み出し、これを用いて暗号文CT(TAR(indt))を復号して検索対象情報TAR(indt)を出力する(ステップS126)。
【0172】
図10を用いて上記の処理を概念的に説明する。なお、図10はsubを2個の真部分集合に分割する例であるが、これは本発明を限定しない。
【0173】
最初にsub={1,…,maxt}=setとされ(ステップS132)、検索クエリを用いてTag(inds)(inds∈sub)をまとめてバッチ検証する(ステップS133)。ステップS133でtrueであればsubについての検索を終了する。ステップS133でfalseであれば、setを分割して得られるsub1及びsub2がそれぞれsubとされ(ステップS136)、ステップS133の処理が実行される。ステップS133でtrueと判定されたsubについての検索を終了し、ステップS133でfalseのsubについてはさらに分割を行う。例えば、sub1及びsub2で共にfalseと判定されたのであれば、sub1を分割して得られるsub3並びにsub4、及びsub2を分割して得られるsub5並びにsub6がそれぞれsubとされ、ステップS133の処理が実行される。例えばsub3の要素数が基準値以下であるとすると、sub3を分割したsub7及びsub8の各要素に対してステップS137の処理が実行され、ステップS137でtrueとされたindsに対応する暗号文CT(TAR(inds))が集合HITに追加される(ステップS138)。
【0174】
〔第2実施形態〕
次に本発明の第2実施形態を説明する。本形態では、第1暗号方式として階層的内積述語暗号方式を用いる。以下では、第1実施形態との相違点を中心に説明し、第1実施形態と共通する事項については第1実施形態と同じ参照番号を用い、説明を簡略化する。
【0175】
<構成>
図11に例示するように、本形態の検索可能暗号システム2は、管理装置210−m(m=1,...,M)と登録装置220−u(u=1,...,U)と検索代行装置230とストレージ装置240と検索装置250−u(u=1,...,U)とを有する。なお、M及びUはそれぞれ1以上の整数である。また、管理装置210−mは、検索可能暗号システム2のm番目の管理者が使用する装置である。本形態では、小さいmに対応する管理者ほど強い管理権限を持つ。すなわち、m=1に対応する管理者が最も強い権限を持つ。また、登録装置220−u及び検索装置250−uは、検索可能暗号システム2を利用するu番目の登録ユーザが使用する装置である。また、各装置は他の装置へ情報を提供可能なように構成されている。装置間の情報提供はネットワークを通じて行われてもよいし、可搬型記録媒体を介して行われてもよい。
【0176】
[管理装置]
図12Aに例示するように、管理装置210−1は、入力部211−1と出力部212−1とマスタ秘密鍵格納部213−1と管理者秘密鍵格納部214−1と制御部215−1とベクトル設定部216a−1と鍵情報生成部216b−1と補間鍵生成部216d−1と検索者鍵生成部216c−1と失効情報生成部216e−1とを有する。図12Bに例示するように、管理装置210−(m’+1)(m'=1,...,M-1)は、入力部211−(m’+1)と出力部212−(m’+1)と制御部215−(m’+1)とベクトル設定部216a−(m’+1)と鍵情報生成部216b−(m’+1)とを有する。管理装置210−mは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、管理装置210−mは、それぞれ、制御部215−mの制御のもと各処理を実行する。また、管理装置210−mでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【0177】
[登録装置]
図13に例示するように、登録装置220−uは、入力部221−uと出力部122−uと属性格納部223a−uと登録キーワード格納部123b−uと検索者鍵格納部223c−uと制御部125−uと写像部226a−u,226d−uと乱数生成部226b−u,126c−uとベクトル設定部226e−uと暗号化部226f−uとタグ情報生成部226g−uとを有する。登録装置220−uは、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、登録装置220−uは、それぞれ、制御部125−uの制御のもと各処理を実行する。なお、図面表記の便宜上、図13には2つの入力部221−uが記載されているが、これは入力部の種類や個数を限定するものではない。また、登録装置220−uでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【0178】
[検索代行装置230]
図14Aに例示するように、検索代行装置230は、入力部231と出力部232と補間鍵格納部233と制御部235と写像部236と検証処理部237(「バッチ検索部」及び「検索部」に相当)とを有する。検索代行装置230は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、検索代行装置230は、それぞれ、制御部235の制御のもと各処理を実行する。また、検索代行装置230での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。なお、図面表記の便宜上、図14Aには2つの入力部231が記載されているが、これは入力部の種類や個数を限定するものではない。
【0179】
[ストレージ装置240]
図14Bに例示するように、ストレージ装置240は、入力部141と出力部142と暗号化データベース格納部243と制御部145と読み書き部246とを有する。ストレージ装置240は、例えば、公知のコンピュータ又は専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、ストレージ装置240は、制御部235の制御のもと各処理を実行する。
【0180】
図15Aに例示するように、暗号化データベース格納部243には、文書などの検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)の暗号文CT(TAR(indt))と、第1実施形態と同様な第1暗号文(T(indt,1),…,T(indt,N))と、第1暗号文(T(indt,1),…,T(indt,N))の復号値を共通鍵Kとした第2暗号方式(共通鍵暗号方式)の暗号文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)の第1暗号文(T(indt,1),…,T(indt,N))は、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットしないときに当該検索クエリを復号鍵として用いて正しく復号される暗号文である。また、この正しい復号値を共通鍵Kとして暗号文T(indt)を復号した場合の復号値はe^(indt)・RE(indt)となる。よって、検索クエリを用いて第1暗号文(T(indt,1),…,T(indt,N))を復号して得られる値を共通鍵Kとして暗号文T(indt)を復号した値がe^(indt)・RE(indt)である場合、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットしていないことになる。暗号化データベースの構成及び生成方法の詳細は後述する。
【0181】
図15Bに例示するように、暗号化データベース格納部243には、さらに暗号文CT(TAR(indt))と、第1実施形態と同様な第2暗号文(LT(indt,1),…,LT(indt,N))と、第2暗号文(LT(indt,1),…,LT(indt,N))の復号値を共通鍵Kとした第3暗号方式(共通鍵暗号方式)の暗号文LT(indt)と、第2暗号文LT(indt)の復号値Lr'(indt)=e^(indt)・LR(indt)に対するe^(indt)に対応するh(indt)と、LR(indt)とがそれぞれ対応付けられた第2暗号化データベースが格納されている。暗号文CT(TAR(indt))にそれぞれ対応付けられる((LT(indt,1),…,LT(indt,N)), LT(indt), h(indt), LR(indt))を検索対象情報TAR(indt)に対応するタグ情報LTag(indt)(肯定タグ情報)と呼ぶ。肯定タグ情報LTag(indt)の第2暗号文(LT(indt,1),…,LT(indt,N))は、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットするときに当該検索クエリを復号鍵として用いて正しく復号される暗号文である。また、この正しい復号値を共通鍵Kとして暗号文LT(indt)を復号した場合に復号値としてe^(indt)・LR(indt)が得られる。よって、検索クエリを用いて第2暗号文(LT(indt,1),…,LT(indt,N))を復号して得られる値を共通鍵Kとして暗号文LT(indt)を復号した値がe^(indt)・LR(indt)である場合、検索クエリに対応する検索用キーワードが検索対象情報TAR(indt)に対応する登録キーワードにヒットしていることになる。第2暗号化データベースの構成及び生成方法の詳細は後述する。
【0182】
[検索装置250−u]
第1暗号方式が異なり、検索クエリ生成部257−uが検索クエリ生成部257−uに置換され、鍵情報格納部253−uが追加される以外、第1実施形態と同様であるため説明を省略する。
【0183】
<事前処理>
前述した[階層的内積述語暗号方式の基本構成]のSetupが実行され、階層フォーマットξ,マスタ秘密鍵MSK,公開パラメータmpkが定められる。マスタ秘密鍵MSKは、管理装置210−1(図12A)のマスタ秘密鍵格納部213−1に安全に格納され、管理装置210−m,登録装置220−u,検索装置250−u及び検索代行装置230が、公開パラメータmpkを用いた処理が可能なように構成される。また、管理装置210−m及び登録装置220−uが階層フォーマットξに従った処理が可能なように構成される。
【0184】
管理装置210−1(図12A)の管理者秘密鍵格納部214−1には、有限体Fqの任意の元である管理者秘密鍵ax∈Fqが安全に格納されているものとする。
【0185】
登録装置220−u(図13)の登録キーワード格納部123b−uには、登録を行う検索対象情報TAR(indt)の暗号文CT(TAR(indt))と検索対象情報TAR(indt)に対応するキーワード(登録キーワード)WT(indt)とが格納されている。さらに、登録装置220−uの属性格納部223a−uには、登録装置220−uを利用するユーザの属性を表す情報(以下、単に「属性」という)が格納されている。ユーザの属性の例は、ユーザが所属するグループを表す情報(会社名、所属部門、課、担当、グループなど)、住所、年齢、職業、趣味などである。
【0186】
検索装置250−u(図6)の検索対象情報復号鍵格納部154−uには、登録装置220−u(図13)の登録キーワード格納部123b−uに格納された暗号文CT(TAR(indt))を復号するための検索対象情報復号鍵Key(indt)が格納されている。
【0187】
<ユーザ登録>
ユーザ登録では、管理装置210−mが登録ユーザの属性に対して設定されたベクトル(v1,...,vM)に対応する鍵情報kM*を生成する。鍵情報kM*の生成方式は大きく分けて2通り存在する。
【0188】
一つ目の方式は、管理装置210−1が前述の[階層的内積述語暗号方式の基本構成]のGenKeyのみに従って鍵情報kM*を生成する方式である(一括方式)。このような方式は小規模グループに適したものであるといえる。二つ目の方式は、管理装置210−1が前述のGenKeyに従い、その他の管理装置210−(m’+1)が前述のDelegate(m')に従い、鍵情報kM*を生成する方式である(委託方式)。このような方式は階層化された大規模グループに適したものであるといえる。
【0189】
[一括方式]
図16は、一括方式によって鍵情報kM*を生成する処理を説明するためのフローチャートである。
【0190】
一括方式では、最も強い権限をもつm=1に対応する管理者の管理装置210−1のみによって鍵情報kM*を生成する。
【0191】
まず、管理装置210−1(図12A)の入力部211−1に登録ユーザの属性ATTが入力される。属性ATTはM層ATT1,...,ATTMに階層化されている。各層に対応する属性ATTmを部分属性と呼ぶことにし、小さいmに対応する部分属性ATTmほど上位の属性を表すものとする。例えば、M=2の場合、属性ATTは2層の部分属性ATT1及びATT2からなり、この場合の部分属性の例は、
ATT1=(○○株式会社,○○部門) …(81)
ATT2=(○○課,○○担当,○○グループ) …(82)
である(ステップS201)。
【0192】
入力された属性ATTはベクトル設定部216a−1に入力される。ベクトル設定部216a−1は、階層フォーマットξ及びシステム内で定められた規則に従って属性ATTに対応するベクトル(v1,...,vM)を設定する。例えば、ベクトル設定部216a−1は、まず、階層フォーマットξ及びシステム内で定められた規則に従い、属性ATTを表すベクトル(w1,...,wM)を式(41)に従って設定し、内積wω・vω=0Fとなる式(42)に従ったベクトル(v1,...,vM)を属性ATTに対応するベクトルとする。式(81)(82)の例を用いて説明すると、例えば、ベクトル設定部216a−1は、部分属性ATT1を「○○株式会社」を表すw1及び「○○部門」を表すw2を要素とする2次元のベクトル
w1=(w1,w2) …(83)
に変換し、部分属性ATT2を「○○課」を表すw3、「○○担当」を表すw4、及び「○○グループ」を表すw5を要素とする3次元のベクトル
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)が定まるのであればどのような方法でもよい(ステップS202)。
【0193】
生成されたベクトル(v1,...,vM)は鍵情報生成部216b−1に入力される。鍵情報生成部216b−1は、マスタ秘密鍵格納部213−1からマスタ秘密鍵MSKを読み出し、m=Mとした前述のGenKeyに従い、ベクトル(v1,...,vM)に対応する鍵情報kM*を生成する。例えば、鍵情報生成部216b−1は、m=Mとした式(43)-(46)に従って鍵情報kM*を生成する。生成された鍵情報kM*は出力部212−1に送られる(ステップS203)。
【0194】
また、検索者鍵生成部216c−1が、有限体Fqから任意の元を選択し、それを登録ユーザの検索者鍵sxu∈Fqとする。生成された検索者鍵sxuは出力部212−1及び補間鍵生成部216d−1に送られる(ステップS204)。
【0195】
検索者鍵sxuが送られた補間鍵生成部216d−1は、管理者秘密鍵格納部214−1から管理者秘密鍵axを抽出し、当該検索者鍵sxuと管理者秘密鍵axとの組の像である補間鍵ckuを生成する。例えば、補間鍵生成部216d−1は、
【0196】
【数27】

によって補間鍵ckuを生成する。生成された補間鍵ckuは出力部212−1に送られる(ステップS205)。
【0197】
出力部212−1は、鍵情報kM*(M≦d-1)及び検索者鍵sxuを出力する。鍵情報kM*は登録ユーザが使用する検索装置250−u(図6)の入力部151−uに入力され、鍵情報格納部253−uに格納される。検索者鍵sxuは登録ユーザが使用する登録装置220−u(図13)の入力部221−uに入力され、検索者鍵格納部223c−uに格納される(ステップS106)。
【0198】
また、出力部212−1(図12A)は、補間鍵ckuを出力する。補間鍵ckuは検索代行装置230(図14A)の入力部231に入力され、登録ユーザに対応付けられて補間鍵格納部233に格納される(ステップS207)。
【0199】
[委託方式]
図17及び18は、委託方式によって鍵情報kM*を生成する処理を説明するためのフローチャートである。
【0200】
委託方式では、最も強い権限をもつm=1に対応する管理者の管理装置210−1が前述のGenKeyに従って鍵情報k1*を生成し、上位階層の鍵情報を受け取った下位階層の管理者の管理装置210−(m’+1)が前述のDelegate(m')に従って鍵情報を生成していき、最終的に鍵情報kM*が生成される。
【0201】
まず、管理装置210−1(図12A)の入力部211−1に登録ユーザの部分属性ATT1が入力される(ステップS211)。
【0202】
入力された部分属性ATT1はベクトル設定部216a−1に入力される。ベクトル設定部216a−1は、階層フォーマットξ及びシステム内で定められた規則に従って部分属性ATT1に対応するベクトルv1を設定する。例えば、ベクトル設定部216a−1は、まず、階層フォーマットξ及びシステム内で定められた規則に従い、部分属性ATT1を表すベクトルw1を式(41)に従って設定し、内積w1・v1=0Fとなる式(42)に従ったベクトルv1を部分属性ATT1に対応するベクトルとする。式(81)(82)の例を用いて説明すると、例えば、ベクトル設定部216a−1は、式(83)によって部分属性ATT1を表すベクトルw1を設定し、内積w1・v1=0Fとなる式(84)のベクトルv1を、部分属性ATT1に対応するベクトルとする(ステップS212)。
【0203】
生成されたベクトルv1は鍵情報生成部216b−1に入力される。鍵情報生成部216b−1は、マスタ秘密鍵格納部213−1からマスタ秘密鍵MSKを読み出し、m=1とした前述のGenKeyに従い、ベクトルv1に対応する鍵情報k1*を生成する。例えば、鍵情報生成部216b−1は、m=1とした式(43)-(46)に従って鍵情報k1*を生成する。生成された鍵情報k1*は出力部212−1に送られる(ステップS213)。
【0204】
また、一括方式と同じステップS204及びS205の処理が実行される。出力部212−1はステップS204で得られた検索者鍵sxuを出力する。検索者鍵sxuは登録ユーザが使用する登録装置220−u(図13)の入力部221−uに入力され、検索者鍵格納部223c−uに格納される(ステップS216)。また、出力部212−1はステップS205で得られた補間鍵ckuを出力する。補間鍵ckuは検索代行装置230(図14A)の入力部231に入力され、登録ユーザに対応付けられて補間鍵格納部233に格納される(ステップS207)。さらに、出力部212−1はステップS213で得られた鍵情報k1*を出力する。
【0205】
鍵情報k1*は管理装置210−2に入力される。管理装置210−2以降では前述したDelegate(m')(m'=1,...,M-1)に従って鍵生成が行われる。以下では管理装置210−m’から鍵情報km'*を受け取る管理装置210−(m’+1)の処理を一般化して説明する。
【0206】
まず、鍵情報km'*が管理装置210−(m’+1)(図12B)の入力部211−(m’+1)に入力され、鍵情報生成部216b−(m’+1)に入力される(ステップS220)。また、部分属性ATTm'+1がベクトル設定部216a−(m’+1)に入力される。ベクトル設定部216a−(m’+1)は、階層フォーマットξ及びシステム内で定められた規則に従って部分属性ATTm'+1に対応するベクトルvm'+1を設定する。例えば、ベクトル設定部216a−(m’+1)は、まず、階層フォーマットξ及びシステム内で定められた規則に従い、部分属性ATTm'+1を表すベクトルwm'+1を式(41)に従って設定し、内積wm'+1・vm'+1=0Fとなる式(42)に従ったベクトルvm'+1を部分属性ATTm'+1に対応するベクトルとする。生成されたベクトルvm'+1は鍵情報生成部216b−(m’+1)に入力される(ステップS222)。
【0207】
鍵情報km'*とベクトルvm'+1とが入力された鍵情報生成部216b−(m’+1)は、前述のDelegate(m')に従って、ベクトル(v1,...,vm'+1)に対応する鍵情報km'+1*を生成する。例えば、鍵情報生成部216b−(m’+1)は、式(47)-(50)に従って鍵情報km'+1*を生成する。生成された鍵情報km'+1*は出力部212−(m’+1)に送られる(ステップS223)。出力部212−(m’+1)は鍵情報km'+1*を出力する(ステップS228)。
【0208】
m'+1<Mの場合、出力された鍵情報km'+1*は下位階層の管理装置210−(m’+2)に入力され、m'+1を新たなm'としてステップS220−S228の処理が実行される。一方、m'+1=Mの場合、出力された鍵情報km'+1*=kM*は、登録ユーザが使用する検索装置250−u(図6)の入力部151−uに入力され、鍵情報格納部253−uに格納される。
【0209】
<データベース登録>
図19及び20に示すように、登録ユーザは登録装置220−uを用い、以下のようにデータベース登録を行うことができる。
【0210】
まず、登録装置220−u(図13)の写像部226a−uが、登録キーワード格納部123b−uから検索対象情報TAR(indt)に対応する登録キーワードWT(indt)を抽出する(ステップS231)。また、乱数生成部226b−uが、キーワードWT(indt)に対して有限体Fqの任意の元である選択値rWT(indt)∈Fqを選択する。選択値rWT(indt)は写像部226a−uに入力される(ステップS132)。写像部226a−uは、さらに検索者鍵格納部223c−uから検索者鍵sxuを抽出し、WT(indt),sxu,rWT(indt)を用いて値h(indt)を生成する(登録ユーザの検索者鍵sxuの像である第1値h(indt))。例えば、写像部226a−uは、入力値に対して巡回群G1の元を出力する擬似ランダム関数Hσを用い、
【0211】
【数28】

で表される値h(indt)を生成する。なお、どのような擬似ランダム関数Hσを用いてもかまわないが、例えば、鍵付きハッシュ関数を擬似ランダム関数Hσとして用いることができる(ステップS233)。生成された値h(indt)は出力部122−u及びタグ情報生成部226g−uに送られる。出力部122−uは値h(indt)を出力する(ステップS234)。
【0212】
登録装置220−uから出力された値h(indt)は、検索代行装置230(図14A)の入力部231に入力され、写像部236に送られる。写像部236は、補間鍵格納部233から登録装置220−uを利用する登録ユーザに対応する補間鍵ckuを抽出する。写像部236は、当該値h(indt)と補間鍵ckuとの組の像である値e^(indt)を生成する。例えば、写像部236は、当該値h(indt)と補間鍵ckuとの組に式(4)の双線形写像Pairを施して値e^(indt)を生成する。すなわち、
e^(indt)=Pair(h(indt),cku)∈GT …(87)
で表される値e^(indt)を生成する(ステップS235)。値e^(indt)は出力部232送られ、出力部232は値e^(indt)を出力する(ステップS236)。
【0213】
検索代行装置230から出力された値e^(indt)は、登録装置220−u(図13)の入力部221−uに入力され、写像部226d−uに送られる。写像部226d−uは値e^(indt)の像である値r'(indt)を生成する。例えば、まず乱数生成部126c−uが巡回群GTの任意の元RE(indt)=LR(indt)を生成して写像部226d−u及びタグ情報生成部226g−uに送り(ステップS237)、写像部226d−uが、
r'(indt)=RE(indt)・e^(indt) …(88)
で表される値r'(indt)を生成する。値r'(indt)は暗号化部226f−uに送られる(ステップS238)。
【0214】
また登録装置220−u(図13)のベクトル設定部226e−uは、属性格納部223a−uから登録ユーザの属性ATTを抽出する。この属性ATTは当該登録ユーザのユーザ登録時に用いられたものと同じである。ベクトル設定部226e−uは、階層フォーマットξ及びシステム内で定められた規則に従って属性ATTを表すベクトル(w1,...,wM)を設定する。当該ベクトル(w1,...,wM)とユーザ登録時のステップS202で設定されたベクトル(v1,...,vM)とは、ω=1,...,Mについて内積wω・vω=0Fを満たす。生成されたベクトル(w1,...,wM)は暗号化部226f−uに送られる(ステップS240)。 ベクトル設定部226e−uが、第1実施形態のステップS102と同様に、補集合CSET(indt)に対応するベクトルwCSET∈Fqを設定する。ベクトルwCSETは暗号化部226f−uに入力される。
【0215】
暗号化部226f−uは、第1暗号方式に則ってベクトルw1,...,wM,wCSETに対応する第1暗号文(T(indt,1),…,T(indt,N))を生成する。本形態の暗号化部226f−uは、(w1,...,wM,wCSET)=(w1,...,wm)とした式(51)に従って、以下のような第1暗号文(T(indt,1),…,T(indt,N))を生成する。
【0216】
C1=(T(indt,1),…,T(indt,N))∈G1n+3 …(89)
ただし、この例ではN=n+3である(ステップS243)。
【0217】
暗号化部226f−uは、gTτ・υ1を共通鍵Kとし、第2暗号方式に則って値r'(indt)を暗号化した暗号文T(indt)を生成する。例えば、暗号化部226f−uは、mes=r'(indt)とした式(52)に従い、以下のように暗号文T(indt)を生成する。
【0218】
C2=T(indt)=gTτ・υ1・r'(indt)∈GT …(90)
このように生成された(T(indt,1),…,T(indt,N))及びT(indt)は、タグ情報生成部226g−uに送られる(ステップS244)。
【0219】
タグ情報生成部226g−uは、(T(indt,1),…,T(indt,N))、T(indt)、h(indt)及びRE(indt)を互いに対応付けた否定タグ情報Tag(indt)を以下のように生成する。
【0220】
Tag(indt)=((T(indt,1),…,T(indt,N)), T(indt), h(indt), RE(indt)) …(91)
否定タグ情報Tag(indt)は出力部122−uに送られる(ステップS245)。
【0221】
また、ベクトル設定部226e−uは、第1実施形態のステップS106と同様に、検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応する登録キーワードWT(indt)に対応するベクトルwT∈Fqを設定する。ベクトルwTは暗号化部226f−uに入力される。
【0222】
暗号化部226f−uは、第1暗号方式に則ってベクトルw1,...,wM,wTに対応する第2暗号文(LT(indt,1),…,LT(indt,N))を生成する。本形態の暗号化部226f−uは、(w1,...,wM,wT)=(w1,...,wm)とした式(51)に従って、以下のように第2暗号文(LT(indt,1),…,LT(indt,N))を生成する。
【0223】
C1=(LT(indt,1),…,LT(indt,N))∈G1n+3 …(92)
ただし、この例ではN=n+3である(ステップS247)。
【0224】
暗号化部226f−uは、gTτ・υ1を共通鍵Kとし、第2暗号方式に則って値r'(indt)を暗号化した暗号文LT(indt)を生成する。例えば、暗号化部226f−uは、mes=r'(indt)とした式(52)に従い、以下のように暗号文LT(indt)を生成する。
【0225】
C2=T(indt)=gTτ・υ1・r'(indt)∈GT …(93)
このように生成された(LT(indt,1),…, LT(indt,N))及びLT(indt)は、タグ情報生成部226g−uに送られる(ステップS248)。
【0226】
タグ情報生成部226g−uは、(LT(indt,1),…,LT(indt,N))、LT(indt)、h(indt)及びLR(indt)を互いに対応付けた肯定タグ情報LTag(indt)を以下のように生成する。
【0227】
LTag(indt)=((LT(indt,1),…,LT(indt,N)), LT(indt), h(indt), LR(indt)) …(94)
否定タグ情報Tag(indt)は出力部122−uに送られる(ステップS249)。
【0228】
出力部122−uには、さらに前述の否定タグ情報LTag(indt)、及び登録キーワード格納部123b−uから読み出された検索対象情報TAR(indt)の暗号文CT(TAR(indt))が送られる。出力部122−uは、CT(TAR(indt))、LTag(indt)及びLTag(indt)を出力する(ステップS250)。
【0229】
CT(TAR(indt))、LTag(indt)及びLTag(indt)はストレージ装置(図14B)の入力部141に入力される。書込み部246はCT(TAR(indt))、LTag(indt)及びLTag(indt)を互いに対応付け、図15A及びBに示したように暗号化データベース格納部243に格納する(ステップS251)。
【0230】
<バッチ検索用の事前計算>
検索代行装置230(図14A)の検証処理部237は、後述するバッチ検索のために以下のような事前計算を行う。この事前計算は定期的に行われてもよいし、暗号化データベース格納部243が更新されるたびに行われてもよい。或いは、暗号化データベース格納部243の更新後に後述するバッチ検索が始めて実行されるときに行われてもよい。以下ではストレージ装置240の暗号化データベース格納部243に、indt=1,…,maxt(maxt≧2)についてのCT(TAR(indt))及びTag(indt)が互いに対応付けられて格納されていることを前提とする(図15A参照)。
【0231】
検証処理部237は、ストレージ装置240にアクセスし、暗号化データベース格納部243を用いて以下の処理を行う。検証処理部237は、まずsub={1,…,maxt}とし、indN=1,…,Nについて前述の式(71)-(73)及び以下の式(95)(96)を事前計算し、BT(indN)(indN=1,…,N)、BT、RE、h、e^をsubに対応付けて暗号化データベース格納部243に格納する。
【0232】
【数29】

同様にsubを分割して得られるsubの真部分集合のそれぞれを新たなsubとし、indN=1,…,Nについて式(71)-(73)(95)(96)が事前計算され、BT(indN)(indN=1,…,N)、BT、RE、h、e^がsubに対応付けられて暗号化データベース格納部243に格納される処理が繰り返される。subの分割方法や分割回数は、第1実施形態と同様、検索代行装置230で事前に定められる。
【0233】
<検索>
登録ユーザは検索装置250−u(図6)を用い、以下のように検索を行う。
【0234】
図21に示すように、まず第1実施形態で説明したステップS121及びS122の処理が実行される。否定タグ情報Tag(indt)及び肯定タグ情報LTag(indt)のそれぞれに設定された第2ベクトルvQは検索クエリ生成部257−uに送られる。検索クエリ生成部257−uは、鍵情報格納部253−uから鍵情報kM*を抽出する。検索クエリ生成部257−uは、kM*と否定タグ情報Tag(indt)に設定されたvQとを用い、m'=Mとした前述のDelegate(m')によって、ベクトルv1,...,vM及びvM+1=vQに対応する鍵情報(復号鍵)kM+1*である検索クエリQUE(Tag)を生成する。また検索クエリ生成部257−uは、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,α*を含まない。
【0235】
Tag(indt)=(que1,…,queN)∈G2n+3 …(97)
LTag(indt)=(Lque1,…,LqueN)∈G2n+3 …(98)
ただし、この例ではn+3=Nである(ステップS253)。
【0236】
生成された検索クエリQUE(Tag)及びQUE(LTag)は出力部152−uに送られ、出力部152−uはこれらを出力する(ステップS124)。
【0237】
図9に示すように、検索クエリQUE(Tag)及びQUE(LTag)は、検索代行装置230(図14A)の入力部231に入力され、検証処理部237及び制御部235に送られる(ステップS261)。制御部235は、補間鍵格納部233を参照し、検索クエリQUE(Tag)及びQUE(LTag)に対応する登録ユーザの補間鍵ckuが利用可能であるかを検証する。検索クエリQUE(Tag)及びQUE(LTag)に対応する登録ユーザの補間鍵ckuが利用可能でない場合とは、検索クエリQUE(Tag)及びQUE(LTag)に対応する登録ユーザの補間鍵ckuが補間鍵格納部233に格納されていない場合や、補間鍵格納部233に格納された補間鍵ckuの使用が禁止されている場合である(ステップS271)。
【0238】
ここで、検索クエリQUE(Tag)及びQUE(LTag)に対応する登録ユーザの補間鍵ckuが利用可能でない場合には、出力部232が「該当なし」を表す⊥を出力して処理を終了する(ステップS272)。
【0239】
一方、検索クエリQUE(Tag)及びQUE(LTag)に対応する登録ユーザの補間鍵ckuが利用可能である場合には、制御部235は、まずsub={1,…,maxt}とする(ステップS262)。検索代行装置230はストレージ装置240(図14B)にアクセスし、入力部231,141、出力部232、142、及び読み書き部246を通じ、暗号化データベース格納部243に格納されたデータにアクセス可能な状態とされる。検索代行装置230(図14A)の検証処理部237は、否定タグ情報Tag(indt)に対する検索クエリQUE(Tag)を用い、暗号化データベース格納部243に格納された否定タグ情報Tag(inds)(inds∈sub)をまとめてバッチ検証する。すなわち、検索クエリQUE(Tag)を用い、inds∈sub⊆{1,…,maxt}についての第1暗号文(T(inds,1),…,T(inds,N))の合成値(式(71))が正しく復号できるかを判定する。具体的には本形態の検証処理部237は、検索クエリQUE(Tag)を復号鍵として用い、inds∈subについての第1暗号文(T(inds,1),…,T(inds,N))の関数値(BT(1),…,BT(N))(式(71))を第1暗号方式に則って復号して得られる値を共通鍵とし、inds∈subについての暗号文T(inds)の関数値BT(式(72))を第2暗号方式に則って復号して得られる値が、inds∈subについての復号値RE(inds)の関数値RE(式(73))とe^(式(96))とについてe^・REとなるか(true)否か(false)を判定する。例えば、式(89)(90)のような計算で否定タグ情報Tag(inds)が得られたのであれば、検証処理部237は、以下を満たすか(true)否か(false)を判定する。
【0240】
【数30】

原則、この判定を行うために必要な(BT(1),…,BT(N))、BT、e^及びREは、前述の事前計算で得られたものである。ただし、必要な(BT(1),…,BT(N))、BT、e^及びREが格納されていないのであれば、検証処理部237はそれらを計算してこの判定を行い、以降の処理のためにそれらの値を暗号化データベース格納部243に格納しておいてもよい(ステップS263)。
【0241】
ステップS263の判定でtrueと判定された場合には(ステップS264)、inds∈subに対応する各検索対象情報TAR(inds)に対する検索が終了し、ステップS269へ進む。一方、ステップS263の判定でfalseと判定された場合(inds∈sub⊆{1,…,maxt}についての第1暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できないと判定された場合)には(ステップS264)、ステップS265に進み、subの要素数が基準値以下であるかが判定される(ステップS265)。
【0242】
ステップS265でsubの要素数が基準値以下ではないと判定された場合には、subを分割して得られるsubの真部分集合のそれぞれを新たなsubとし、ステップS263に戻る。なお、ここでのsubの分割方法は、例えば前述のバッチ検索用の事前計算でのsubの分割方法と同一とする(ステップS266)。
【0243】
一方、ステップS265でsubの要素数が基準値以下であると判定された場合、検索クエリQUE(LTag)を用いた肯定タグ情報LTag(indt)の検証に切り替えられる。すなわち、検証処理部237が検索クエリQUE(LTag)(第2検索クエリ)を復号鍵として用い、第2暗号文(LT(inds,1),…,LT(inds,N))(inds∈sub)が正しく復号できるかを判定する。本形態の検証処理部237は検索クエリQUE(LTag)を復号鍵として用い、肯定タグ情報LTag(indt)が含む第2暗号文(LT(inds,1),…,LT(inds,N))(inds∈sub)(図15B)を第1暗号方式に則って復号して得られる値を共通鍵とし、暗号文LT(inds)を第3暗号方式に則って復号して得られる値がPair(h,cku)・LR(inds)であるかを判定する。例えば、式(89)(90)のような計算で肯定タグ情報LTag(inds)が得られたのであれば、検証処理部237は、以下を満たすか(true)否か(false)を判定する。
【0244】
【数31】

これは、肯定タグ情報LTag(inds)に対応する登録キーワードが検索クエリQUE(LTag)に対応する検索用キーワードにヒットするか(true)否か(false)を肯定タグ情報LTag(inds)ごとに判定することに相当する(ステップS267)。
【0245】
検証処理部237は、ステップS267の判定でtrueとされた肯定タグ情報LTag(inds)のindsに対応する暗号文CT(TAR(inds))を集合HITに追加し、図示しないメモリに格納し(ステップS268)、ステップS269に進む。
【0246】
ステップS269では、検証処理部237が未検証のsubが存在するかを判定する(ステップS269)。ここで、未検証のsubが存在すると判定された場合には、ステップS263に進む。一方、未検証のsubが存在しないと判定された場合には、検証処理部237は、集合HITの要素である暗号文CT(TAR(indt))を出力する。集合HITの要素が存在しなければ、検証処理部237はヒットしなかったことを表す⊥を出力する(ステップS270)。これらは出力部232から出力される。その後、第1実施形態で説明したステップS125及びS126の処理が実行される。
【0247】
〔各実施形態の特徴〕
上述の方法により、検索処理回数を大幅に削減できる。例えば、maxt個の検索対象情報TAR(indt)に対応する暗号化データベースを検索する場合、従来法であれば最大maxt回の判定処理が必要であったが、上述の方法でsubを2個に分割して新たなsubとする場合にはlog2 maxt回程度の判定処理でよい。
【0248】
〔変形例〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、第1実施形態では、具体例として単一単語一致検索や部分集合判定検索を行う場合を例示したが、非特許文献1,2に開示されたようなその他の検索方式を用いる場合に本発明が適用されてもよい。また、上記の各実施形態では、内積述語暗号方式や階層的内積述語暗号方式で鍵カプセル化メカニズムKEMを構成する場合のタグ情報の生成方法や検証方法を例示したが、これは本発明を限定するものではない。例えば、式(65)の第1暗号文(T(indt,1),…,T(indt,N))とgTτ・υ1との組が否定タグ情報とされてもよい。肯定タグ情報についても同様な変形が可能である。
【0249】
上記の各実施形態では、否定タグ情報を用いたバッチ検索処理でsubの要素数が基準値以下にまで絞り込んでから、肯定タグ情報を用いた個別の検索処理を行った。しかし肯定タグ情報を用いた個別の検索処理を行うことなく、否定タグ情報のみを用いて検索が行われてもよい。この場合には肯定タグ情報や第2暗号化データベースの生成やそれに対応する検索クエリを生成する必要はない。
【0250】
上記実施形態で説明した階層的内積述語暗号方式の基本構成ではζ=3の場合を例示した。しかし、ζがその他の1以上の整数であってもよい。マスタ秘密鍵MSKが含む基底ベクトルをζについて一般化すると(b1*,...,bn*,bn+1*,...,bn+ζ*)となり、公開パラメータmpkが含む基底ベクトルをζについて一般化すると(b1,...,bn,bn+1,...,bn+ζ)となる。前述した式(44)-(46),(51)(52)(54)をζについてそれぞれ一般化すると、例えば、以下のようになる。
【0251】
【数32】

ただし、φω,0,φω,αは有限体Fqから選択された任意の元であり、Ωは0以上ζ以下の整数である。また、有限体Fqの元である定数constに対して以下を満たす。定数constの具体例は1Fである。
【0252】
【数33】

【数34】

ただし、υωは有限体Fqから選択された任意の元である。
【0253】
C2=gTτ・υ・const・mes
【0254】
【数35】

また、上述した有限体上の元や演算が有限環上の元や演算に置換された構成でもよい。また、登録装置と検索装置とが一体であってもよいし、検索代理装置とストレージ装置とが一体であってもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【0255】
〔プログラム等〕
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【0256】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【0257】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0258】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。
【0259】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【0260】
1,2 検索可能暗号システム
110,210−m 管理装置
120−u,220−u 登録装置
230 検索代行装置
140,240 ストレージ装置
150−u,250−u 検索装置

【特許請求の範囲】
【請求項1】
暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な第1暗号方式を用いた検索可能暗号システムであって、
予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する前記第1暗号方式の第1暗号文(T(indt,1),…,T(indt,N))(Nは正整数)を含む暗号化データベースを格納する暗号化データベース格納部と、
検索用キーワードに対応するベクトルに対応する前記第1暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆{1,…,maxt}についての第1暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できるかを判定するバッチ検索部と、
を有する検索可能暗号システム。
【請求項2】
請求項1の検索可能暗号システムであって、
前記inds∈sub⊆{1,…,maxt}についての前記第1暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できないと判定された場合に、subの真部分集合を新たなsubとした前記バッチ検索部の処理を再び実行させる制御部をさらに有する検索可能暗号システム。
【請求項3】
請求項1又は2の検索可能暗号システムであって、
前記検索対象情報TAR(indt)に対応するキーワードに対して設定されるベクトルに対応する前記第1暗号方式の第2暗号文(LT(indt,1),…,LT(indt,N))を含む第2暗号化データベースを格納する第2暗号化データベース格納部と、
前記inds∈sub⊆{1,…,maxt}についての前記第1暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できないと判定された場合に、第2検索クエリを復号鍵として用い、第2暗号文(LT(inds,1),…,LT(inds,N))(inds∈sub)が正しく復号できるかを判定する検索部をさらに有する検索可能暗号システム。
【請求項4】
請求項3の検索可能暗号システムであって、
前記検索対象情報TAR(indt)に対応するキーワードに対して設定されるベクトルと特定のベクトルとが特定の論理式の真理値を偽にする関係にあるとき、前記補集合CSET(indt)に対して設定されるベクトルと当該特定のベクトルとは当該特定の論理式の真理値を真にする関係にある、検索可能暗号システム。
【請求項5】
請求項1から4の何れかの検索可能暗号システムであって、
前記第1暗号文(T(inds,1),…,T(inds,N))の合成値が(BT(1),…,BT(N))であり、BT(indN)(indN=1,…,N)が
【数36】

である、検索可能暗号システム。
【請求項6】
請求項1から5の何れかの検索可能暗号システムであって、
前記第1暗号方式は、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0であるときに当該暗号文が当該復号鍵で復号可能な方式である、検索可能暗号システム。
【請求項7】
暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な第1暗号方式を用いた検索可能暗号方式のストレージ装置であって、
予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する前記第1暗号方式の第1暗号文(T(indt,1),…,T(indt,N))(Nは正整数)を含む暗号化データベースを格納する暗号化データベース格納部を有するストレージ装置。
【請求項8】
暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な第1暗号方式を用いた検索可能暗号方式のストレージ装置を検索する装置であって、
検索用キーワードに対応するベクトルに対応する前記第1暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆{1,…,maxt, maxt≧2}についての第1暗号文(T(inds,1),…,T(inds,N))(Nは正整数)の合成値が正しく復号できるかを判定する装置。
【請求項9】
暗号文に対応するベクトルと復号鍵に対応するベクトルとが特定の論理式の真理値を真にする関係にあるときに当該暗号文が当該復号鍵で復号可能な第1暗号方式を用いた検索可能暗号方法であって、
予め定められたキーワードの全体集合から検索対象情報TAR(indt)(indt=1,…,maxt, maxt≧2)に対応するキーワードを除いた補集合CSET(indt)に対して設定されるベクトルに対応する前記第1暗号方式の第1暗号文(T(indt,1),…,T(indt,N))(Nは正整数)を含む暗号化データベースが暗号化データベース格納部に格納されており、
バッチ検索部で、検索用キーワードに対応するベクトルに対応する前記第1暗号方式の復号鍵である検索クエリを用い、inds∈sub⊆{1,…,maxt}についての第1暗号文(T(inds,1),…,T(inds,N))の合成値が正しく復号できるかを判定する検索可能暗号方法。
【請求項10】
請求項9の検索可能暗号方法の処理をコンピュータに実行させるためのプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate


【公開番号】特開2012−146063(P2012−146063A)
【公開日】平成24年8月2日(2012.8.2)
【国際特許分類】
【出願番号】特願2011−3017(P2011−3017)
【出願日】平成23年1月11日(2011.1.11)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】