説明

暗号処理システム、鍵生成装置、鍵委譲装置、暗号化装置、復号装置、暗号処理方法及び暗号処理プログラム

【課題】権限委譲を可能とした述語暗号を実現することを目的とする。
【解決手段】ペアリング演算によって関連付けられた双対ベクトル空間(双対ディストーションベクトル空間)である空間Vと空間Vとを用いて暗号処理を行う。暗号化装置は、空間Vにおけるベクトルであって、送信情報を埋め込んだベクトルを暗号ベクトルとして生成する。復号装置は、空間Vにおける所定のベクトルを鍵ベクトルとして、暗号化装置が生成した暗号ベクトルと鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して送信情報に関する情報を抽出する。

【発明の詳細な説明】
【技術分野】
【0001】
この発明は、階層的述語鍵秘匿方式及び階層的述語暗号に関するものである。
【背景技術】
【0002】
非特許文献18には、ペアリング演算によって関連付けられた双対空間において階層的述語鍵秘匿方式及び階層的述語暗号を実現することが記載されている。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】Bethencourt, J., Sahai, A., Waters, B.:Ciphertext−policy attribute−based encryption.In: 2007 IEEE Symposium on Security and Privacy, pp. 321−−334. IEEE Press (2007)
【非特許文献2】Boneh, D., Boyen, X.: Efficient selective−ID secure identity based encryption without randomoracles.In: Cachin, C., Camenisch, J. (eds.)EUROCRYPT 2004. LNCS, vol. 3027, pp. 223−−238. Springer Heidelberg (2004)
【非特許文献3】Boneh, D., Boyen, X.: Secure identity based encryption without random oracles.In: Franklin, M.K. (ed.) CRYPTO 2004.LNCS, vol. 3152, pp. 443−−459.Springer Heidelberg(2004)
【非特許文献4】Boneh, D., Boyen, X., Goh, E.: Hierarchical identity based encryption with constant sizeciphertext.In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 440−−456.Springer Heidelberg(2005)
【非特許文献5】Boneh, D., Franklin, M.: Identity−based encryption from the Weil pairing.In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213−−229.Springer Heidelberg(2001)
【非特許文献6】Boneh, D., Hamburg, M.: Generalized identity based and broadcast encryption scheme. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 455−−470.Springer Heidelberg(2008)
【非特許文献7】Boneh, D., Waters, B.:Conjunctive, subset, and range queries onencrypted data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 535−−554.Springer Heidelberg(2007)
【非特許文献8】Boyen, X., Waters, B.: Anonymous hierarchical identity−based encryption (without random oracles).In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 290−−307.Springer Heidelberg(2006)
【非特許文献9】Cocks, C.:An identity based encryption scheme based on quadratic residues.In: Honary, B. (ed.) IMA Int. Conf. LNCS, vol. 2260, pp. 360−−363. Springer Heidelberg(2001)
【非特許文献10】Gentry, C.:Practical identity−based encryption without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 445−−464.Springer Heidelberg(2006)
【非特許文献11】Gentry, C., Halevi, S.: Hierarchical identity−based encryption with polynomially many levels. In: Reingold, O. (ed.) TCC 2009.LNCS, vol. 5444, pp. 437−−456.Springer Heidelberg(2009)
【非特許文献12】Gentry, C., Silverberg, A.: Hierarchical ID−based cryptography. In: Zheng, Y. (ed.) ASIACRYPT 2002.LNCS, vol. 2501, pp. 548−−566.Springer Heidelberg(2002)
【非特許文献13】Goyal, V., Pandey, O., Sahai, A., Waters, B.:Attribute−based encryption for fine−grained access control of encrypted data. In: ACM Conference on Computer and Communication Security 2006, pp. 89−−98, ACM (2006)
【非特許文献14】Groth, J., Sahai, A.: Efficient non−interactive proof systems for bilinear groups.In: Smart, N.P. (ed.) EUROCRYPT 2008.LNCS, vol. 4965,pp. 415−−432.Springer Heidelberg(2008)
【非特許文献15】Horwitz, J., Lynn, B.:Towards hierarchical identity−based encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002.LNCS, vol. 2332, pp. 466−−481.Springer Heidelberg(2002)
【非特許文献16】Katz, J., Sahai, A., Waters, B.: Predicate encryption supporting disjunctions,polynomial equations, and inner products.In: Smart, N.P. (ed.) EUROCRYPT 2008.LNCS, vol. 4965,pp. 146−−162.Springer Heidelberg(2008)
【非特許文献17】Okamoto, T., Takashima, K.:Homomorphic encryption and signatures fromvector decomposition.In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 57−−74.Springer Heidelberg(2008)
【非特許文献18】Okamoto, T., Takashima, K.:A geometric approach on pairings and hierarchical predicate encryption.In: Poster session, EUROCRYPT 2009.(2009)
【非特許文献19】Ostrovsky, R., Sahai, A., Waters, B.:Attribute−based encryption with non−monotonic accessstructures.In:ACM Conference on Computer and Communication Security 2007, pp. 195−−203, ACM,(2007)
【非特許文献20】Pirretti, M., Traynor, P., McDaniel, P., Waters, B.: Secure attribute−based systems.In:ACM Conference on Computer and Communication Security 2006, pp. 99−−112, ACM,(2006)
【非特許文献21】Sahai, A., Waters, B.: Fuzzy identity−based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005.LNCS, vol. 3494, pp. 457−−473.Springer Heidelberg(2005)
【非特許文献22】Shi, E., Waters, B.:Delegating capability in predicate encryption systems. In: Aceto, L., Damgard, I., Goldberg, L.A., Halldorsson, M.M., Ingolfsdottir, A., Walukiewicz, I. (eds.)ICALP (2) 2008.LNCS, vol. 5126, pp. 560−−578.Springer Heidelberg(2008)
【非特許文献23】Takashima, K.:Efficiently computable distortion maps for supersingularcurves.In: van der Poorten, A.J., Stein, A. (eds.)ANTS VIII, LNCS, vol. 5011, pp. 88−−101. Springer Heidelberg(2008)
【非特許文献24】Waters, B.:Ciphertext−policy attribute−based encryption: an expressive, efficient, and provably secure realization. ePrint, IACR, http://eprint.iacr.org/2008/290
【発明の概要】
【発明が解決しようとする課題】
【0004】
非特許文献18で提案されている階層的述語鍵秘匿方式及び階層的述語暗号は、理想化されたモデル(Generic Model)における安全性が証明されている。しかし、非特許文献18で提案されている階層的述語鍵秘匿方式及び階層的述語暗号は、標準のモデル(Standard Model)における安全性は証明されていない。
この発明は、安全性が高い述語暗号及び述語鍵秘匿方式を提供することを目的とする。特に、権限委譲を可能とした述語暗号及び述語鍵秘匿方式を提供することを目的とする。
【課題を解決するための手段】
【0005】
この発明に係る暗号処理システムは、例えば、
数1に示すペアリング演算によって関連付けられた双対ベクトル空間である空間Vと空間Vとを用いて述語暗号処理を行う暗号処理システムであり、
前記空間Vにおける所定の基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)の基底ベクトルb(i=1,...,n)と、基底ベクトルb(i=n+1,...,N)のうちの2つ以上の基底ベクトルb(i=n+1,...,m)の和である基底ベクトルdn+1とを基底ベクトルとして有する基底B^におけるベクトルであって、基底ベクトルb(i=1,...,n)うちの少なくとも一部の基底ベクトルに対する係数として属性情報を埋め込むとともに、前記基底ベクトルdn+1に対する係数として所定の情報を埋め込んだベクトルを暗号ベクトルcとして処理装置により生成する暗号化装置と、
前記空間Vの基底Bにおけるベクトルであって、基底Bを構成する基底ベクトルb(i=1,...,n,...,N)の基底ベクトルb(i=1,...,n)うちの少なくとも一部の基底ベクトルに対する係数として述語情報を埋め込むとともに、前記基底Bの基底ベクトルb(i=n+1,...,m)に対する係数の和が1になるように、前記基底ベクトルb(i=n+1,...,m)に対する係数を埋め込んだベクトルを鍵ベクトルkL,decとして、前記暗号化装置が生成した暗号ベクトルcと前記鍵ベクトルkL,decとについて、処理装置により数1に示すペアリング演算e(c,kL,dec)を行い前記暗号ベクトルcを復号して前記所定の情報に関する値を抽出する復号装置と
を備えることを特徴とする。
【数1】

【発明の効果】
【0006】
この発明に係る暗号システムによれば、安全性が高い述語暗号及び述語鍵秘匿方式を実現することができる。
【図面の簡単な説明】
【0007】
【図1】「権限委譲(階層的な権限委譲)」という概念を説明するための図。
【図2】階層を飛ばした権限委譲を説明するための図。
【図3】属性情報と述語情報との階層構造を示す図。
【図4】階層的内積述語暗号の応用例である階層的IDベース暗号の例を示す図。
【図5】基底と基底ベクトルとを説明するための図。
【図6】ベクトル空間における階層構造の実現方法の一例を説明するための図。
【図7】暗号処理システム10の構成図。
【図8】暗号処理システム10の鍵生成装置100と第L層目の暗号化装置200と復号装置300との動作を示すフローチャート。
【図9】暗号処理システム10の第L層目の鍵委譲装置400と、第L+1層目の暗号化装置200と復号装置300との動作を示すフローチャート。
【図10】基底変換方法を説明するための図。
【図11】実施の形態2に係る階層的述語暗号を実現する暗号処理システム10の機能を示す機能ブロック図。
【図12】実施の形態2に係る鍵生成装置100の動作を示すフローチャート。
【図13】実施の形態2に係る暗号化装置200の動作を示すフローチャート。
【図14】実施の形態2に係る復号装置300の動作を示すフローチャート。
【図15】実施の形態2に係る鍵委譲装置400の動作を示すフローチャート。
【図16】実施の形態2に係る双対ペアリングベクトル空間の基底の構造を示す概念図。
【図17】実施の形態2に係る階層的述語鍵秘匿方式を実現する暗号処理システム10の機能を示す機能ブロック図。
【図18】実施の形態2に係る暗号化装置200の動作を示すフローチャート。
【図19】実施の形態2に係る復号装置300の動作を示すフローチャート。
【図20】実施の形態3に係る権限委譲が可能な述語暗号を実現する暗号処理システム10の機能を示す機能ブロック図。
【図21】鍵生成装置100、暗号化装置200、復号装置300、鍵委譲装置400のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【0008】
以下、図に基づき、発明の実施の形態を説明する。
以下の説明において、処理装置は後述するCPU911等である。記憶装置は後述するROM913、RAM914、磁気ディスク920等である。通信装置は後述する通信ボード915等である。入力装置は後述するキーボード902、通信ボード915等である。出力装置は後述するRAM914、磁気ディスク920、通信ボード915、LCD901等である。つまり、処理装置、記憶装置、通信装置、入力装置、出力装置はハードウェアである。
【0009】
以下の説明における記法について説明する。
Aがランダムな変数または分布であるとき、数101は、Aの分布に従いAからyをランダムに選択することを表す。つまり、数101において、yは乱数である。
【数101】

Aが集合であるとき、数102は、Aからyを一様に選択することを表す。つまり、数102において、yは一様乱数である。
【数102】

数103は、yがzにより定義された集合であること、又はyがzを代入された集合であることを表す。
【数103】

aが定数であるとき、数104は、機械(アルゴリズム)Aが入力xに対しaを出力することを表す。
【数104】

ベクトル表記は、有限体Fにおけるベクトル表示を表す。つまり、数105である。
【数105】

数106は、数107に示す2つのベクトルxとvとの数108に示す内積を表す。
【数106】

【数107】

【数108】

は、行列Xの転置行列を表す。
【0010】
また、以下の説明において、暗号処理とは、暗号化処理、復号処理、鍵生成処理を含むものであり、鍵秘匿処理も含むものである。
【0011】
実施の形態1.
この実施の形態では、後の実施の形態で説明する「権限委譲を有する述語暗号(Predicate Encryption with Delegation)」や「権限委譲を有する述語鍵秘匿方式(Predicate Key Encapsulation Mechanism with Delegation)」を実現する基礎となる概念と、権限委譲を有する述語暗号(述語鍵秘匿方式)の基本構成について説明する。
第1に、権限委譲を有する述語暗号(述語鍵秘匿方式)の一種である「権限委譲を有する内積述語暗号(内積述語鍵秘匿方式)」という概念を説明する。後の実施の形態で説明する権限委譲を有する述語暗号(述語鍵秘匿方式)は、権限委譲を有する内積述語暗号(内積述語鍵秘匿方式)である。権限委譲を有する内積述語暗号という概念を説明するに当たり、まず「権限委譲」という概念を説明する。また、併せて、「階層的(Hierarchial)な権限委譲」という概念を説明する。次に、「内積述語暗号」を説明する。そして、階層的な権限委譲という概念を内積述語暗号に加えた「階層的内積述語暗号(階層的内積述語鍵秘匿方式)」を説明する。さらに、階層的内積述語暗号の理解を深めるため、階層的内積述語暗号の応用例を説明する。
第2に、ベクトル空間における階層的内積述語暗号を説明する。この実施の形態及び以下の実施の形態では、階層的述語暗号と階層的述語鍵秘匿方式とをベクトル空間において実現する。ここでは、まず、「基底」と「基底ベクトル」について説明する。次に、「ベクトル空間における内積述語暗号」について説明する。そして、「ベクトル空間における階層構造の実現方法」について説明する。さらに、理解を深めるため、階層構造の実現例を説明する。
第3に、この実施の形態及び後の実施の形態に係る「階層的述語暗号」と「階層的述語鍵秘匿方式」との基本構成を説明する。併せて、階層的述語暗号と階層的述語鍵秘匿方式とを実行する「暗号処理システム10」の概要を説明する。
第4に、階層的述語鍵秘匿方式や階層的述語暗号を実現するための概念を説明する。ここでは、「双線形ペアリンググループ」、「ベクトル空間Vとベクトル空間V」、「標準的な双対基底A,A」、「ペアリング演算」、「基底変換」、「ディストーション写像」を説明する。
第5に、階層的述語鍵秘匿方式と階層的述語暗号とを実現するための空間である「双対ペアリングベクトル空間(Dual Pairing Vector Spaces,DPVS)」という豊かな数学的構造を有する空間を説明する。
そして、第6に、以上の説明を踏まえ、後の実施の形態で詳細に説明する階層的述語暗号と階層的述語鍵秘匿方式との実現方法を簡単に説明する。
【0012】
<第1.階層的内積述語暗号>
<第1−1.権限委譲(階層的な権限委譲)という概念>
図1は、「権限委譲(階層的な権限委譲)」という概念を説明するための図である。
権限委譲とは、上位の鍵を有する利用者が、その鍵(上位の鍵)よりも機能が制限された下位の鍵を生成することである。
図1では、Root(鍵生成装置)は、マスター秘密鍵を用いて、第1層目(Level−1)の利用者へ秘密鍵を生成する。つまり、Rootは、第1層目の利用者1,2,3それぞれへ鍵1,2,3を生成する。そして、例えば、利用者1であれば、鍵1を用いて、利用者1の下位(第1層目)の利用者である利用者11,12,13それぞれへ鍵11,12,13を生成することができる。ここで、利用者1が有する鍵1よりも、利用者11,12,13が有する鍵11,12,13は機能が制限されている。機能が制限されているとは、その秘密鍵によって復号できる暗号文が限定されているということである。つまり、上位の秘密鍵で復号できる暗号文の一部の暗号文のみ下位の秘密鍵で復号できることを意味する。すなわち、利用者1が有する鍵1で復号できる暗号文のうち、一部の暗号文のみ利用者11,12,13が有する鍵11,12,13で復号することができる。また、通常は、鍵11と鍵12と鍵13とが復号できる暗号文は異なる。一方、鍵11と鍵12と鍵13が復号できる暗号文は、鍵1で復号することができる。
また、図1に示すように、各秘密鍵が階層(レベル)分けされていることを「階層的」という。つまり、図1に示すように、階層的に下位の鍵を生成することを「階層的な権限委譲」と呼ぶ。
【0013】
なお、図1では、Rootが第1層目の利用者へ秘密鍵を生成し、第1層目の利用者が第2層目の利用者へ秘密鍵を生成し、第2層目の利用者が第3層目の利用者へ秘密鍵を生成すると説明した。しかし、図2に示すように、Rootは、第1層目の利用者へ秘密鍵を生成するだけでなく、第2層目以下の層の利用者へ秘密鍵を生成することもできる。同様に、第1層目の利用者は、第2層目の利用者へ秘密鍵を生成するだけでなく、第3層目以下の層の利用者へ秘密鍵を生成することもできる。つまり、Rootや利用者は、自分が持つ秘密鍵よりも下位の層の秘密鍵を生成することができる。
【0014】
<第1−2.内積述語暗号>
次に、「内積述語暗号」について説明する。
まず、述語暗号とは、述語情報fに属性情報xを入力した場合に1(True)となる場合(f(x)=1となる場合)に、暗号文を復号できる暗号方式である。通常、暗号文に属性情報xが埋め込まれ、秘密鍵に述語情報fが埋め込まれる。つまり、述語暗号では、属性情報xに基づき暗号化された暗号文cを、述語情報fに基づき生成された秘密鍵SKにより復号する。述語暗号は、例えば、述語情報fが条件式であり、属性情報xがその条件式への入力情報であり、入力情報(属性情報x)が条件式(述語情報f)を満たせば(f(x)=1)、暗号文を復号できる暗号方式であるとも言える。
なお、述語暗号について詳しくは非特許文献16に記載されている。
【0015】
内積述語暗号とは、属性情報xと述語情報fとの内積が所定の値の場合に、f(x)=1となる述語暗号である。つまり、属性情報xと述語情報fとの内積が所定の値の場合にのみ、属性情報xにより暗号化された暗号文cを、述語情報fに基づき生成された秘密鍵SKにより復号することができる。以下の説明では、属性情報xと述語情報fとの内積が0の場合に、f(x)=1となるものとする。
【0016】
<第1−3.階層的内積述語暗号>
階層的内積述語暗号(階層的内積述語鍵秘匿方式)とは、上述した「階層的な権限委譲」という概念を有する「内積述語暗号」である。
【0017】
階層的内積述語暗号は、内積述語暗号に階層的な権限委譲システムを持たせるため、属性情報と述語情報とに階層構造を持たせる。
図3は、属性情報と述語情報との階層構造を示す図である。
図3において、符号が対応する属性情報と述語情報とは対応する(つまり、内積が0となる)ものとする。つまり、属性1と述語1との内積は0となり、属性11と述語11との内積は0となり、属性12と述語12との内積は0となり、属性13と述語13との内積は0となるとする。すなわち、属性1により暗号化された暗号文c1は、述語1に基づき生成された秘密鍵k1であれば復号できる。また、属性11により暗号化された暗号文c11は、述語11に基づき生成された秘密鍵k11であれば復号できる。属性12と述語12、属性13と述語13についても同様のことが言える。
上記の通り、階層的内積述語暗号は階層的な権限委譲システムを有する。そのため、述語1に基づき生成された秘密鍵k1と、述語11とに基づき、秘密鍵k11を生成することができる。つまり、上位の秘密鍵k1を有する利用者は、その秘密鍵k1と下位の述語11とから、秘密鍵k1の下位の秘密鍵k11を生成することができる。同様に、秘密鍵k1と述語12とから秘密鍵k12を生成でき、秘密鍵k1と述語13とから秘密鍵k13を生成できる。
また、下位の秘密鍵に対応する鍵(公開鍵)で暗号化された暗号文を上位の秘密鍵で復号できる。一方、上位の秘密鍵に対応する鍵(公開鍵)で暗号化された暗号文は、下位の秘密鍵で復号できない。つまり、属性11、属性12、属性13により暗号化された暗号文c11、c12、c13は、述語1に基づき生成された秘密鍵k1であれば復号できる。一方、属性1により暗号化された暗号文c1は、述語11、述語12、述語13に基づき生成された秘密鍵k11、k12、k13では復号できない。すなわち、属性11、属性12、属性13と述語1との内積は0となる。一方、属性1と述語11、述語12、述語13との内積は0とならない。
【0018】
<第1−4.階層的内積述語暗号の応用例>
図4は、後述する階層的内積述語暗号の応用例である階層的IDベース暗号(Hierarchial Identifier Based Encryption,HIBE)の例を示す図である。なお、階層的IDベース暗号とは、IDベース暗号が階層的になった暗号処理である。IDベース暗号は、述語暗号の一種であり、暗号文に含まれるIDと秘密鍵に含まれるIDとが一致する場合に暗号文を復号できるマッチング述語暗号である。
図4に示す例では、Root(鍵生成装置)は、マスター秘密鍵skとA会社のIDである「A」とに基づき、ID「A」に対応する秘密鍵(鍵A)を生成する。例えば、A会社のセキュリティ担当者は、鍵Aと各部門のIDとに基づき、そのIDに対応する秘密鍵を生成する。例えば、セキュリティ担当者は、営業部門のIDである「A−1」に対応する秘密鍵(鍵1)を生成する。次に、例えば、各部門の管理者は、その部門の秘密鍵とその部門に属する各課のIDとに基づき、そのIDに対応する秘密鍵を生成する。例えば、営業部門の管理者は、営業1課のIDである「A−11」に対応する秘密鍵(鍵11)を生成する。
ここで、営業1課のID「A−11」に対応する秘密鍵である鍵11により、営業1課のID「A−11」で暗号化された暗号文を復号することができる。しかし、鍵11により、営業2課や営業3課のIDで暗号化された暗号文は復号することはできない。また、鍵11により、営業部門のIDで暗号化された暗号文は復号することができない。
営業部門のID「A−1」に対応する秘密鍵である鍵1により、営業部門のID「A−1」で暗号化された暗号文を復号することができる。また、鍵1により、営業部門に属する課のIDで暗号化された暗号文を復号することができる。つまり、鍵1により、営業1課、営業2課、営業3課のIDで暗号化された暗号文を復号することができる。しかし、鍵1により、製造部門(ID:A−2)やスタッフ部門(ID:A−3)のIDで暗号化された暗号文は復号することができない。また、鍵1により、A会社のIDで暗号化された暗号文は復号することができない。
A会社のID「A」に対応する秘密鍵である鍵Aにより、A会社のID「A」で暗号化された暗号文を復号することができる。また、A会社に属する各部門や、その部門に属する課のIDで暗号化された暗号文を復号することができる。
【0019】
階層的内積述語暗号は、IDベース暗号以外へも様々な応用が可能である。特に、以下に説明する暗号処理は、等号関係テストのクラスに限定されたものではないため、非常に多くの応用が可能である。例えば、内積述語暗号の一種である検索可能暗号等についても、階層毎に検索可能な範囲をAND条件やOR条件等の条件式を用いて限定する等、従来の権限委譲システムを有する述語暗号では実現できなかった応用が可能である。
つまり、後の実施の形態で説明する階層的述語鍵秘匿方式と階層的述語暗号とは、IDベース暗号や検索可能暗号等へ幅広い応用が可能である。
【0020】
<第2.ベクトル空間における階層的内積述語暗号>
階層的述語鍵秘匿方式と階層的述語暗号とは、後述する双対ペアリングベクトル空間という高次元ベクトル空間において実現される。そこで、ベクトル空間における階層的内積述語暗号を説明する。
【0021】
<第2−1.基底と基底ベクトル>
まず、ベクトル空間の説明において使用する「基底」と「基底ベクトル」とについて簡単に説明する。
図5は、基底と基底ベクトルとを説明するための図である。
図5は、2次元ベクトル空間におけるベクトルvを示す。ベクトルvは、c+cである。また、ベクトルvは、y+yである。ここで、a,aを基底Aにおける基底ベクトルといい、基底A:=(a,a)と表す。また、b,bを基底Bにおける基底ベクトルといい、基底B:=(b,b)と表す。また、c,c,y,yは、各基底ベクトルに対する係数である。図5では、2次元ベクトル空間であったため、各基底における基底ベクトルは2個であった。しかし、N次元ベクトル空間であれば、各基底における基底ベクトルはN個である。
【0022】
<第2−2.ベクトル空間における内積述語暗号>
次に、ベクトル空間における内積述語暗号を説明する。
上記の通り、内積述語暗号とは、属性情報xと述語情報fとの内積が所定の値(ここでは、0)の場合に、f(x)=1となる述語暗号である。属性情報xと述語情報fとがベクトルであった場合、つまり属性ベクトルxと述語ベクトルvとであった場合、内積述語は数109のように定義される。
【数109】

つまり、属性ベクトルxと述語ベクトルvとの内積、つまり要素毎の内積の和が0である場合に、述語情報fに属性情報xを入力した結果が1(True)となる。また、属性ベクトルxと述語ベクトルvとの内積が0でない場合に、述語情報fに属性情報xを入力した結果が0(False)となる述語暗号である。
【0023】
<第2−3.ベクトル空間における階層構造の実現方法>
次に、ベクトル空間における階層構造の実現方法を説明する。
図6は、ベクトル空間における階層構造の実現方法の一例を説明するための図である。
ここで扱うベクトル空間は、高次元(N次元)ベクトル空間であるとする。つまり、ベクトル空間における所定の基底Cには、基底ベクトルc(i=1,...,N)のN個の基底ベクトルが存在する。
N個の基底ベクトルのうちのn個の基底ベクトル(基底ベクトルc(i=1,...,n))を階層構造を表すために使用する。また、基底ベクトルc(i=1,...,n)を、基底ベクトルc(i=1,...,μ)と、基底ベクトルc(i=μ+1,...,μ)と、...、基底ベクトルc(i=μd−1+1,...,n)とのd個に分割する。ここで、dは、階層の深さを表す数となる。
そして、μ個の基底ベクトルc(i=1,...,μ)を第1層目の属性情報や述語情報を表すために割り当てる。また、μ−μ個の基底ベクトルc(i=μ+1,...,μ)を第2層目の属性情報や述語情報を表すために割り当てる。以下同様に、μ−μd−1個の基底ベクトルc(i=μd−1+1,...,μ(=n))を第d層目の属性情報や述語情報を表すために割り当てる。
また、第L層目の属性情報によって暗号文を生成する場合には、第L層目の属性情報だけでなく、第1層目から第L層目までの属性情報を用いて暗号文を生成する。同様に、第L層目の述語情報によって秘密鍵を生成する場合には、第L層目の述語情報だけでなく、第1層目から第L層目までの述語情報を用いて秘密鍵を生成する。つまり、第L層目の属性情報によって暗号文を生成する場合や、第L層目の述語情報によって秘密鍵を生成する場合には、第1層目から第L層目までに割り当てられたμ個の基底ベクトルc(i=1,...,μ)を用いる。例えば、第3層目の属性情報によって暗号文を生成する場合には、第1層目から第3層目までに割り当てられたμ個の基底ベクトルc(i=1,...,μ)を用いて、第1層目から第3層目までの属性情報を用いて暗号文を生成する。同様に、第3層目の述語情報によって秘密鍵を生成する場合には、第1層目から第3層目までに割り当てられたμ個の基底ベクトルc(i=1,...,μ)を用いて、第1層目から第3層目までの述語情報を表して秘密鍵を生成する。つまり、下位の層で使用される属性情報や述語情報には、上位の層で使用される属性情報や述語情報が含まれる。これにより、属性情報と述語情報とに階層構造を持たせる。そして、この属性情報と述語情報とに階層構造を利用して、内積述語暗号に権限委譲システムを持たせる。
【0024】
なお、以下の説明においては、ベクトル空間における階層的構造を示すために、階層情報μを用いる。階層情報μを数110に示す。
【数110】

つまり、階層情報μは、階層構造を表すために割り当てられた基底ベクトル数(次元数)を示すnと、階層の深さを示すdと、各階層に割り当てられた基底ベクトルを示すためのμ,...,μとの情報を有する。
【0025】
次に、ベクトル空間における階層的内積述語暗号を説明する。
属性空間Σ(L=1,...,d)を、第L層目の属性情報を表すために割り当てられた空間であるとする。ここで、各Σは、数111である。
【数111】

階層的な属性を数112に示すΣとする。ここで、和集合は互いに素な和集合である。
【数112】

すると、数113に示す階層的な属性における数114に示す階層的な述語は、数115のように定義される。
【数113】

【数114】

【数115】

階層的な述語空間を数116に示すFとする。
【数116】

また、数117のhと数118のLとを階層と呼ぶ。
【数117】

【数118】

【0026】
<第2−4.階層構造の実現例>
ここで、簡単な例を用いて階層構造を説明する。ここでは、3つの階層を備え、各階層が2次元で構成された6次元空間を用いて説明する。つまり、μ:=(n,d;μ,...,μ)=(6,3;2,4,6)である。
第1層目の述語ベクトルv:=(v,v)に基づき生成された第1層目の秘密鍵skを有する利用者は、第1層目の秘密鍵skと第2層目の述語ベクトルv:=(v,v)に基づき第2層目の秘密鍵skを生成することができる。つまり、第2層目の秘密鍵skは、述語ベクトル(v,v)に基づき生成される。同様に、第2層目の秘密鍵skを有する利用者は、第2層目の秘密鍵skと第3層目の述語ベクトルv:=(v,v)に基づき第3層目の秘密鍵skを生成することができる。つまり、第3層目の秘密鍵skは、述語ベクトル(v,v,v)に基づき生成される。
第1層目の述語ベクトルvに基づき生成された第1層目の秘密鍵skは、(v,(0,0),(0,0))により生成された秘密鍵である。そのため、第1層目の秘密鍵skは、属性ベクトル(x,(*,*),(*,*)):=((x,x),(*,*),(*,*))により暗号化された暗号文を、v・x=0である場合には復号できる。なぜなら、(*,*)・(0,0)=0であるためである。ここで、“*”は、任意の値を示す。
同様に、第2層目の述語ベクトル(v,v)に基づき生成された第2層目の秘密鍵skは、(v,v,(0,0))により生成された秘密鍵である。そのため、第2層目の秘密鍵skは、属性ベクトル(x,x,(*,*)):=((x,x),(x,x),(*,*))により暗号化された暗号文を、v・x=0かつv・x=0である場合には復号できる。
しかし、第2層目の秘密鍵skは、第1層目の属性ベクトルx:=(x,x)(つまり、(x,(*,*),(*,*))により暗号化された暗号文を復号することはできない。なぜなら、v=(0,0)でなければ、(*,*)・v≠0であり、v・x≠0であるためである。そのため、第2層目の秘密鍵skは、親である秘密鍵鍵skよりも限定された能力のみを有していると言える。
【0027】
<第3.階層的述語暗号と階層的述語鍵秘匿方式との構成>
<第3−1.階層的述語暗号>
階層的述語暗号の構成を簡単に説明する。
階層的述語暗号は、Setup、GenKey、Enc、Dec、Delegate(L=1,...,d−1)の5つの確率的多項式時間アルゴリズムを備える。
(Setup)
Setupアルゴリズムでは、セキュリティパラメータ1λと階層情報μとが入力され、マスター公開鍵pkとマスター秘密鍵skとが出力される。マスター秘密鍵skは最も上位の鍵である。
(GenKey)
GenKeyアルゴリズムでは、マスター公開鍵pkとマスター秘密鍵skと数119に示す述語ベクトルが入力され、数120に示す第L層目の秘密鍵が出力される。
【数119】

【数120】

(Enc)
Encアルゴリズムでは、マスター公開鍵pkと数121に示す属性ベクトルと平文情報mとが入力され、暗号文cが出力される。つまり、Encアルゴリズムでは、平文情報mを埋め込み、数121に示す属性ベクトルにより暗号化された暗号文cが出力される。
【数121】

(Dec)
Decアルゴリズムでは、マスター公開鍵pkと数122に示す第L層目の秘密鍵と暗号文cとが入力され、平文情報m又は識別情報⊥が出力される。識別情報⊥とは、復号に失敗したことを示す情報である。つまり、Decアルゴリズムでは、暗号文cを第L層目の秘密鍵で復号して、平文情報mを抽出する。また、復号に失敗した場合には識別情報⊥を出力する。
【数122】

(Delegate
Delegateでは、マスター公開鍵pkと数123に示す第L層目の秘密鍵と数124に示す第L+1層目の述語ベクトルとが入力され、数125に示す第L+1層目の秘密鍵が出力される。つまり、Delegateアルゴリズムでは、下位の秘密鍵が出力される。
【数123】

【数124】

【数125】

【0028】
<第3−2.階層的述語暗号>
階層的述語鍵秘匿方式の構成を簡単に説明する。
階層的述語鍵秘匿方式は、階層的述語暗号と同様に、Setup、GenKey、Enc、Dec、Delegate(L=1,...,d−1)の5つの確率的多項式時間アルゴリズムを備える。
(Setup)
Setupアルゴリズムでは、セキュリティパラメータ1λと階層情報μとが入力され、マスター公開鍵pkとマスター秘密鍵skとが出力される。マスター秘密鍵skは最も上位の鍵である。
(GenKey)
GenKeyアルゴリズムでは、マスター公開鍵pkとマスター秘密鍵skと数126に示す述語ベクトルが入力され、数127に示す第L層目の秘密鍵が出力される。
【数126】

【数127】

(Enc)
Encアルゴリズムでは、マスター公開鍵pkと数128に示す属性ベクトルとが入力され、暗号文cとセッション鍵Kとが出力される。つまり、Encアルゴリズムでは、所定の情報(ρ)を埋め込み、数128に示す属性ベクトルにより暗号化された暗号文cと、所定の情報(ρ)から生成したセッション鍵Kとが出力される。
【数128】

(Dec)
Decアルゴリズムでは、マスター公開鍵pkと数129に示す第L層目の秘密鍵と暗号文cとが入力され、セッション鍵K又は識別情報⊥が出力される。識別情報⊥とは、復号に失敗したことを示す情報である。つまり、Decアルゴリズムでは、暗号文cを第L層目の秘密鍵で復号して、所定の情報(ρ)に関する情報を抽出し、セッション鍵Kを生成する。また、復号に失敗した場合には識別情報⊥を出力する。
【数129】

(Delegate
Delegateアルゴリズムでは、マスター公開鍵pkと数130に示す第L層目の秘密鍵と数131に示す第L+1層目の述語ベクトルとが入力され、数132に示す第L+1層目の秘密鍵が出力される。つまり、Delegateアルゴリズムでは、下位の秘密鍵が出力される。
【数130】

【数131】

【数132】

【0029】
<第3−3.暗号処理システム10>
暗号処理システム10について説明する。暗号処理システム10は、上述した階層的述語暗号と階層的述語鍵秘匿方式とのアルゴリズムを実行する。
図7は、暗号処理システム10の構成図である。
暗号処理システム10は、鍵生成装置100、暗号化装置200、復号装置300、鍵委譲装置400を備える。なお、ここでは、復号装置300は、鍵委譲装置400を備えるものとする。また、上述したように、暗号処理システム10は、階層的な暗号処理を実行するものであるため、暗号処理システム10は、複数の暗号化装置200、複数の復号装置300、複数の鍵委譲装置400を備えるものとする。
鍵生成装置100は、階層的述語鍵秘匿方式と階層的述語暗号とのSetup、GenKeyアルゴリズムを実行する。
暗号化装置200は、階層的述語鍵秘匿方式と階層的述語暗号とのEncアルゴリズムを実行する。
復号装置300は、階層的述語鍵秘匿方式と階層的述語暗号とのDecアルゴリズムを実行する。
鍵委譲装置400は、階層的述語鍵秘匿方式と階層的述語暗号とのDelegateアルゴリズムを実行する。
【0030】
図8は、暗号処理システム10の鍵生成装置100と第L層目の暗号化装置200と復号装置300との動作を示すフローチャートである。つまり、図8は、マスター鍵(マスター公開鍵とマスター秘密鍵)の生成、第L層目の秘密鍵の生成から、第L層目における暗号化と復号とまでの動作を示すフローチャートである。
(S101:鍵生成ステップ)
鍵生成装置100は、Setupアルゴリズムを実行してマスター公開鍵pkとマスター秘密鍵skとを生成する。また、鍵生成装置100は、生成したマスター公開鍵pkとマスター秘密鍵skと、所定の復号装置300(第L層目の復号装置300)に対応する述語ベクトルv(v=(v,...,v)(i=μ))とに基づき、GenKeyアルゴリズムを実行して第L層目の秘密鍵を生成する。そして、鍵生成装置100は、生成したマスター公開鍵pkを公開(配布)するとともに、第L層目の秘密鍵を前記所定の復号装置300へ秘密裡に配布する。なお、鍵生成装置100は、マスター秘密鍵を秘密裡に保持する。
(S102:暗号化ステップ)
暗号化装置200は、(S101)で鍵生成装置100が配布したマスター公開鍵pkと、前記復号装置300の属性ベクトルx(x=(x,...,x)(i=μ))とに基づき、Encアルゴリズムを実行して暗号文cを生成する。なお、階層的述語鍵秘匿方式であれば、暗号化装置200は、セッション鍵Kも併せて生成する。そして、暗号化装置200は、生成した暗号文cを前記復号装置300へネットワーク等を介して送信する。なお、属性ベクトルxは、公開されているものとしてもよいし、暗号化装置200が鍵生成装置100や復号装置300から取得するものとしてもよい。
(S103:復号ステップ)
復号装置300は、(S101)で鍵生成装置100が配布したマスター公開鍵pkと第L層目の秘密鍵とに基づき、アルゴリズムDecを実行して、暗号化装置200から受信した暗号文cを復号する。復号装置300は、暗号文cを復号した結果、階層的述語鍵秘匿方式であればセッション鍵Kを取得し、階層的述語暗号であれば平文情報mを取得する。復号装置300は、復号に失敗した場合には識別情報⊥を出力する。
【0031】
図9は、暗号処理システム10の第L層目の鍵委譲装置400と、第L+1層目の暗号化装置200と復号装置300との動作を示すフローチャートである。つまり、図9は、第L+1層目の秘密鍵の生成から、第L+1層目における暗号化と復号とまでの動作を示すフローチャートである。
(S201:鍵委譲ステップ)
第L層目の鍵委譲装置400(第L層目の復号装置300が備える鍵委譲装置400)は、(S101)で鍵生成装置100が配布したマスター公開鍵pkと、鍵生成装置100又は第L−1層目の鍵委譲装置400が配布した第L層目の秘密鍵と、第L+1層目の復号装置300に対応する述語ベクトルvL+1(vL+1=(v,...,v)(i=μ+1,j=μL+1))とに基づき、アルゴリズムDelegateを実行して第L+1層目の秘密鍵を生成する。そして、第L層目の鍵委譲装置400は、生成した秘密鍵を第L+1層目の復号装置300へ秘密裡に配布する。
(S202:暗号化ステップ)
暗号化装置200は、(S101)で鍵生成装置100が配布したマスター公開鍵pkと、第L+1層目までの復号装置300の属性ベクトルxから属性ベクトルxL+1(x(i=1,...,L+1)(=(x,...,x)(i=μL+1)))とに基づき、Encアルゴリズムを実行して暗号文cを生成する。なお、階層的述語鍵秘匿方式であれば、暗号化装置200は、セッション鍵Kも併せて生成する。そして、暗号化装置200は、生成した暗号文cを前記復号装置300へネットワーク等を介して送信する。なお、属性ベクトルxから属性ベクトルxL+1(x(i=1,...,L+1))は、公開されているものとしてもよいし、暗号化装置200が鍵生成装置100や復号装置300から取得するものとしてもよい。
(S203:復号ステップ)
復号装置300は、(S101)で鍵生成装置100が配布したマスター公開鍵pkと、(S201)で第L層目の鍵委譲装置400が配布した秘密鍵とに基づき、アルゴリズムDecを実行して、暗号化装置200から受信した暗号文cを復号する。復号装置300は、暗号文cを復号した結果、階層的述語鍵秘匿方式であればセッション鍵Kを取得し、階層的述語暗号であれば平文情報mを取得する。
【0032】
<第4.階層的述語鍵秘匿方式と階層的述語暗号とを実現するための概念>
次に、上述した階層的述語暗号と階層的述語鍵秘匿方式との各アルゴリズムを実現するために必要となる概念を説明する。
ここでは、非対称ペアリンググループの直積により後述する双対ペアリングベクトル空間を構成する例を用いて、暗号処理を実現する方法を説明する。しかし、双対ペアリングベクトル空間は、非対称ペアリンググループの直積により実現されるものに限定されない。つまり、他の方法により構成された双対ペアリングベクトル空間においても、以下に説明する暗号処理は実現可能である。なお、双対ペアリングベクトル空間の典型的な3つの例が、非特許文献17に記載されている。
【0033】
<第4−1.双線形ペアリンググループ>
双線形ペアリンググループ(q,G,G,G,g,g,g)を説明する。
双線形ペアリンググループ(q,G,G,G,g,g,g)は、位数qの3つの巡回群G,G,Gの組である。gはGの生成元であり、gはGの生成元である。そして、双線形ペアリンググループ(q,G,G,G,g,g,g)は、以下の非退化双線形ペアリングの条件を満たす。
(条件:非退化双線形ペアリング)
多項式時間で計算可能な数133に示す非退化双線形ペアリングが存在すること。
【数133】

ここで、G=G(=:G)である場合、対称双線形ペアリングと呼ぶ。一方、G≠Gである場合、非対称双線形ペアリングと呼ぶ。対称双線形ペアリングは、超特異(超)楕円曲線を用いて構築できる。一方、非対称双線形ペアリングは、どんな(超)楕円曲線を用いても構築できる。非対称双線形ペアリングは、例えば、通常の楕円曲線を用いて構築できる。
【0034】
<第4−2.ベクトル空間Vとベクトル空間V
1次元空間の巡回群を高次元空間(高次元ベクトル空間)へ拡張する。つまり、数134に示すように、GとGとの直積によりN次元ベクトル空間VとN次元ベクトル空間Vとを構築する。
【数134】

【0035】
<第4−3.標準的な双対基底A,A
N次元ベクトル空間Vの標準基底Aと、N次元ベクトル空間Vの標準基底Aとを説明する。
数135は、標準基底Aと標準基底Aとを示す。
【数135】

標準基底Aと標準基底Aとは、数136に示す条件を満たす。
【数136】

つまり、標準基底Aと標準基底Aとは、双対正規直交基底であり、空間Vと空間Vとは、ペアリング演算eによって関連付けられた双対ベクトル空間である。
標準基底Aと標準基底Aとが数136に示す条件を満たすことについて補足する。
まず、e(a,a)=gであることについて説明する。一例として、e(a,a)について計算する。上記の通り、a=(g,0,...,0)であり、a=(g,0,...,0)である。したがって、e(a,a)=e(g,g)×e(0,0)×,...,×e(0,0)である。ここで、上記の通り、e(g,g)=gである。また、e(0,0)=e(0・g,0・g)=e(g,gであるから、e(0,0)=1である。したがって、e(a,a)=gとなる。他のe(a,a)についても同様の計算が成立し、e(a,a)=gとなる。
次に、e(a,a)=1(i≠j)であることについて説明する。一例として、e(a,a)について計算する。上記の通り、a=(g,0,...,0)であり、a=(0,g,0,...,0)である。したがって、e(a,a)=e(g,0)×e(0,g)×e(0,0)×,...,×e(0,0)である。e(g,0)=e(g,0・g)=e(g,gであるから、e(g,0)=1である。同様に、e(0,g)=1である。また、上記の通り、e(0,0)=1である。したがって、e(a,a)=1となる。他のe(a,a)についても同様の計算が成立し、e(a,a)=1となる。
したがって、標準基底Aと標準基底Aとにおいて、e(a,a)=gであり、e(a,a)=1(i≠j)である。
【0036】
<第4−4.ペアリング演算>
N次元ベクトル空間V,Vにおけるペアリング演算eを数137に示すように定義する。
【数137】

つまり、N次元ベクトル空間Vのベクトルx:=(x,x,...,x)とN次元ベクトル空間Vのベクトルy:=(y,y,...,y)とのペアリング演算e(x,y)は、ベクトルxとベクトルyとの要素毎のペアリング演算の積と定義する。すると、上述した非退化双線形ペアリングの条件から、ペアリング演算e(x,y)は、数138に示すように表すことができる。
【数138】

【0037】
<第4−5.基底変換>
標準基底Aと標準基底Aとから他の基底Bと基底Bとへ変換する基底変換方法について説明する。図10は、基底変換方法を説明するための図である。
空間Vにおける標準基底Aから空間Vにおける他の基底B:=(b,...,b)へ変換する。ここでは、数139に示す一様に選択された線形変換Xを用いて、数140に示すように空間Vにおける標準基底Aから空間Vにおける他の基底Bに変換する。
【数139】

【数140】

ここで、GLは、General Linearの略である。つまり、GLは、一般線形群であり、行列式が0でない正方行列の集合であり、乗法に関し群である。
Xを用いることにより、空間Vにおける標準基底Aから空間Vにおける基底B:=(b,...,b)を効率的に計算できる。ここでは、数141に示すようにXを用いて、空間Vにおける基底Bを計算する。
【数141】

【0038】
ここで、数142が成立する。
【数142】

つまり、基底Bと基底Bとは、双対空間VとVにおける双対正規直交基底である。すなわち、Xを用いて標準基底AとAとを変形した場合であっても、双対正規直交基底は保存される。
【0039】
<第4−6.ディストーション写像>
標準基底Aにおける空間Vの生成元xに対するディストーション写像という線形変換について説明する。
空間Vの標準基底Aにおけるディストーション写像φi,jは、数143に示す写像である。
【数143】

数144が成立するため、ディストーション写像φi,jは、数145の変換を行うことができる。
【数144】

【数145】

つまり、標準基底Aのベクトルxの基底ベクトルjの要素を基底ベクトルiの要素へ変換することができる。この際、変換された基底ベクトルjの要素を除く他の要素は、全て0となる。すなわち、ベクトルxの基底ベクトルjの要素が基底ベクトルiの要素となり、その他の要素は0となる。
空間Vの標準基底Aにおけるディストーション写像φi,jも、空間Vの標準基底Aにおけるディストーション写像φi,jと同様に表すことができる。
【0040】
ディストーション写像φi,j(φi,j)を用いることにより、数146に示すN×N行列として表される線形変換Wであって、x∈Vに対するどんな線形変換Wも数147によって効率的に計算することができる。
【数146】

【数147】

【0041】
<第5.双対ペアリングベクトル空間>
第4で説明した概念を踏まえて、双対ペアリングベクトル空間について説明する。後述する階層的述語暗号と階層的述語鍵秘匿方式とは、双対ペアリングベクトル空間において実現される。
双対ペアリングベクトル空間(q,V,V,G,A,A)は、素数位数qと、F上の2つのN次元ベクトル空間V,Vと、位数qの巡回群Gと、空間Vの標準基底A:=(a,...,aN−1)と、空間Vの標準基底A:=(a,...,aN−1)とを有する空間である。そして、双対ペアリングベクトル空間(q,V,V,G,A,A)は、以下の(1)非退化双線形ペアリングが存在する、(2)標準基底A,Aが双対正規直交基底である、(3)ディストーション写像が存在するという3つの条件を満たす空間である。
【0042】
(1)非退化双線形ペアリング(上記第4−1参照)
多項式時間で計算可能な非退化双線形ペアリングeが存在すること。
つまり、数148に示す非退化双線形ペアリングeが存在することが1つ目の条件である。
【数148】

【0043】
(2)双対正規直交基底(上記第4−2参照)
空間Vの標準基底Aと空間Vの標準基底Aとが双対正規直交基底であること。
つまり、空間Vの標準基底Aと空間Vの標準基底Aとが、数149に示す条件を満たすことが2つ目の条件である。
【数149】

【0044】
(3)ディストーション写像(上記第4−6参照)
多項式時間で計算可能なディストーション写像φi,jとφi,jが存在すること。
つまり、数150に示す空間Vの準同型φi,jと空間Vの準同型φi,jが多項式時間で計算可能であることが3つ目の条件である。
【数150】

3つ目の条件を満たすことにより、空間Vと空間Vとがペアリング演算e(上記第4−2参照)によって関連付けられた双対空間であるということも言える。
【0045】
<第6.階層的述語暗号と階層的述語鍵秘匿方式との実現方法の概要>
上述した概念(上記第4参照)と、双対ペアリングベクトル空間(上記第5参照)とを踏まえて、上述した暗号処理システム10(上記第3参照)が階層的述語暗号と階層的述語鍵秘匿方式とを実現する方法を簡単に説明する。
【0046】
まず、暗号処理システム10により実現される内積述語暗号の概要について説明する。なお、説明の簡単のため、ここでは、階層的という概念を省略し、1階層のみで構成される内積述語暗号の概要について説明する。
暗号処理システム10は、双対ペアリングベクトル空間(q,V,V,G,A,A)において内積述語暗号を実現する。なお、ここで、空間V,Vは、いずれもn+3次元空間である。
鍵生成装置100は、第4−5で説明した基底変換により、標準基底A,Aから正規直交基底B:=(b,...,bn+3)と、B:=(b,...,bn+3)とを生成する。鍵生成装置100は、基底B:=(b,...,bn+3)のうちの基底ベクトルbn+1と基底ベクトルbn+2とを、基底ベクトルbn+1と基底ベクトルbn+2との和である基底ベクトルdn+1に置き換えた基底B^:=(b,...,b,dn+1,bn+3)を生成する。そして、基底B^をマスター公開鍵pkとし、基底Bをマスター秘密鍵skとする。さらに、鍵生成装置100は、述語ベクトルv(v=(v,...,v)∈Fから秘密鍵kを数151のように生成して復号装置300へ秘密裡に送信する。
【数151】

暗号化装置200は、属性ベクトルx(x=(x,...,x)∈Fと平文情報mとから、2つの暗号文cとcとを生成する。暗号文cとcとは数152のように生成される。
【数152】

復号装置300は、暗号文c,cと秘密鍵kとに基づき、数153を計算して、平文情報mを抽出する。
【数153】

ここで、v・x=0であるなら、数154に示すように、数153を計算することにより、復号装置300は平文情報mを得ることができる。
【数154】

【0047】
次に、階層的な権限委譲を可能にした内積述語暗号、つまり階層的内積述語暗号の概要について、簡単な例を用いて説明する。ここでは、3つの階層を備え、各階層が2次元で構成された6次元を述語ベクトルと属性ベクトルとに用い、その他に3次元を有する9次元空間を用いて説明する。つまり、空間V,Vは、9次元空間である。したがって、マスター公開鍵に含まれる基底B^:=(b,...,b,d,b)である。なお、d:=b+bである。また、マスター秘密鍵に含まれる基底B:=(b,...,b)である。
なお、以下の説明において、添え字の「dec」は「decryption」の略であり、添え字に「dec」とあるものは、暗号文の復号に用いられる鍵ベクトルである。また、添え字の「ran」は「randomization」の略であり、添え字に「ran」とあるものは、下位の鍵ベクトルの所定の基底ベクトルに対する係数をランダム化するためのランダム化ベクトルである。また、添え字の「del」は「delegation」の略であり、添え字に「del」とあるものは、下位の鍵ベクトルを生成するための鍵生成用ベクトルである。
【0048】
ここで、暗号文c,cは、属性ベクトル(x,x,x):=((x,x),(x,x),(x,x))と平文情報mとにより、数155のように生成される。
【数155】

もし、属性ベクトルが、x:=(x,x)のように高い階層である場合、属性ベクトルを数156のように修正する。
【数156】

つまり、属性ベクトルxで生成された暗号文cは、数156に示す属性ベクトルx→+で生成された暗号文cとして生成される。
【0049】
第1層目の述語ベクトルv:=(v,v)∈Fに基づき生成された第1層目の秘密鍵k→*:=(k1,dec,k1,ran,1,k1,ran,2,k1,del,3,...,k1,del,6)は、k1,decと、(k1,ran,1,k1,ran,2)と、(k1,del,3,...,k1,del,6)との3つの要素からなる。ここで、k1,decは、暗号文の復号に用いられる鍵ベクトルである。(k1,ran,1,k1,ran,2)は、下位の鍵ベクトルの所定の基底ベクトルに対する係数をランダム化するためのランダム化ベクトルである。(k1,del,3,...,k1,del,6)は、下位の鍵ベクトルを生成するための鍵生成用ベクトルである。k1,decと、(k1,ran,1,k1,ran,2)と、(k1,del,3,...,k1,del,6)とは、数157のように生成される。
【数157】

暗号文cを生成する際用いられた属性ベクトルが、(x,x)・(v,v)=0となる((x,x),(*,*),(*,*))であるなら、数158であるため、k1,0は、数159を計算することにより、暗号文c,cを復号することができる。
【数158】

【数159】

【0050】
第2層目の述語ベクトルv:=(v,v)により第2層目の秘密鍵k→*:=(k2,dec,k2,ran,1,k2,ran,2,k2,ran,3,k2,del,5,k2,del,6)を生成する。
まず、k2,decを生成する場合、σ2,0(v1,del,3+v1,del,4)を、k1,decに加える。k2,ran,jを生成する場合、σ2,j(v1,del,3+v1,del,4)を0に加える(j=1,2,3)。k2,del,jを生成する場合、σ2,j(v1,del,3+v1,del,4)をψ1,del,jに加える(j=5,6)。ここで、σ2,j(j=0,1,2,3,5,6)と、ψとは一様に選択された値である。
また、第2層目の秘密鍵の(v+v)とbとbとの係数の値をランダム化する(一様に分布させる)。そこで、k2,decを生成する場合、さらに(α0,11,ran,1+α0,21,ran,2)を加える。k2,ran,jを生成する場合、(αj,11,ran,1+αj,21,ran,2)を加える(j=1,2,3)。k2,del,jを生成する場合、(αj,11,ran,1+αj,21,ran,2)を加える(j=5,6)。ここで、αj,1とαj,2と(j=0,1,2,3,5,6)は一様に選択された値である。
つまり、第2層目の秘密鍵鍵k→*:=(k2,dec,k2,ran,1,k2,ran,2,k2,ran,3,k2,del,5,k2,del,6)が数160のように生成される。
【数160】

なお、k2,decは、暗号文の復号に用いられる鍵ベクトルである。(k2,ran,1,k2,ran,2,k2,ran,3)は、下位の鍵ベクトルの所定の基底ベクトルに対する係数をランダム化するためのランダム化ベクトルである。(k2,del,5,k2,del,6)は、下位の鍵の生成に用いられる。
【0051】
一般に、第L層目の秘密鍵k→*:=(kL,dec,kL,ran,j,kL,del,j)において、kL,decは、暗号文の復号に用いられる鍵ベクトルである。kL,ran,jは、下位の鍵ベクトルの所定の基底ベクトルに対する係数をランダム化するためのランダム化ベクトルである。kL,del,jは、下位の鍵ベクトルを生成するための鍵生成用ベクトルである。
【0052】
実施の形態2.
この実施の形態では、実施の形態1で説明した概念に基づき、階層的述語暗号を実現する暗号処理システム10について説明する。
【0053】
図11から図16に基づき、実施の形態2に係る暗号処理システム10の機能と動作とについて説明する。
図11は、階層的述語暗号を実現する暗号処理システム10の機能を示す機能ブロック図である。暗号処理システム10は、上述したように、鍵生成装置100、暗号化装置200、復号装置300、鍵委譲装置400を備える。また、ここでも、復号装置300が鍵委譲装置400を備えるものとする。
図12は、鍵生成装置100の動作を示すフローチャートである。図13は、暗号化装置200の動作を示すフローチャートである。図14は、復号装置300の動作を示すフローチャートである。図15は、鍵委譲装置400の動作を示すフローチャートである。
図16は、双対ペアリングベクトル空間の基底の構造を示す概念図である。
【0054】
鍵生成装置100の機能と動作とについて説明する。鍵生成装置100は、マスター鍵生成部110、マスター鍵記憶部120、鍵ベクトル生成部130、ランダム化ベクトル生成部140、鍵生成用ベクトル生成部150、鍵配布部160を備える。
【0055】
(S301:マスター鍵生成ステップ)
マスター鍵生成部110は、数161を計算して、マスター公開鍵pkとマスター秘密鍵skとを処理装置により生成してマスター鍵記憶部120に記憶する。
【数161】

つまり、(1)マスター鍵生成部110は、セキュリティパラメータ1λで、N(=n+3)次元の双対ペアリングベクトル空間(q,V,V,G,A,A)を処理装置により生成する。ここで、Gdpvsは、1λとNとを入力として、セキュリティパラメータ1λとN次元空間とについての双対ペアリングベクトル空間(q,V,V,G,A,A)を出力する双対ペアリングベクトル空間生成アルゴリズムである。
(2)マスター鍵生成部110は、標準基底Aから基底Bを生成するための線形変換Xを処理装置によりランダムに選択する。
(3)マスター鍵生成部110は、選択した線形変換Xに基づき、基底A:=(a,...,a)から基底B:=(b,...,b)を処理装置により生成する。
(4)マスター鍵生成部110は、基底Bにおける基底ベクトルbn+1と基底ベクトルbn+2とを、基底ベクトルbn+1と基底ベクトルbn+2との和である基底ベクトルdn+1に置き換えた基底ベクトルB^:=(b,...,b,dn+1,bn+3)を処理装置により生成する。
(5)マスター鍵生成部110は、基底A:=(a,...,a)から基底B:=(b,...,b)を生成するための線形変換(X−1を線形変換Xから処理装置により生成する。
(6)マスター鍵生成部110は、生成した線形変換(X−1に基づき、基底Aから基底B:=(b,...,b)を処理装置により生成する。
(7)マスター鍵生成部110は、生成した線形変換Xと基底Bとをマスター秘密鍵skとし、生成した基底B^を含む(1λ,q,V,V,G,A,A,B^)をマスター公開鍵pkとする。そして、マスター鍵記憶部120は、マスター鍵生成部110が生成したマスター公開鍵pkとマスター秘密鍵skとを記憶装置に記憶する。
なお、双対ペアリングベクトル空間の次元数は、N(=n+3)であるとした。ここで、nは、階層情報μが有する階層構造をあらわすために割り当てられている基底数を表すnである。つまり、ここでは、階層構造をあらわすために割り当てられている基底数nに加え、3つの基底ベクトルが設けられている。もちろん、これよりも多くの基底ベクトルを設けてもよい。
図16に示すように、N(=n+3)個の基底ベクトルのうち、n個の基底ベクトルが述語ベクトルや属性ベクトルのために割り当てられている。述語ベクトルや属性ベクトルのために割り当てられている基底ベクトルの構造は、図6に示す構造と同様である。残り3つの基底ベクトルのうちの2つの基底ベクトル(n+1番目とn+2番目との基底ベクトル)は、セッション鍵を生成する情報のための基底ベクトルである。残りの1つの基底ベクトル(n+3番目の基底ベクトル)は、暗号文cをランダム化するための基底ベクトルである。
【0056】
すなわち、(S301)において、マスター鍵生成部110は、数162に示すSetupアルゴリズムを実行して、マスター公開鍵pkとマスター秘密鍵skとを生成する。
【数162】

【0057】
(S302:鍵ベクトルkL,dec生成ステップ)
鍵ベクトル生成部130は、マスター公開鍵pkとマスター秘密鍵skと、数163に示す述語ベクトル(v,...,v)とに基づき、数164を計算して、第L層目(レベルL)の秘密鍵の先頭要素である鍵ベクトルkL,decを処理装置により生成する。
【数163】

【数164】

つまり、(1)鍵ベクトル生成部130は、乱数σ0,i(i=1,...,L)と乱数ηとを処理装置により生成する。
(2)鍵ベクトル生成部130は、基底ベクトルb(i=1,...,μ)に対する係数として生成した乱数σ0,tでランダム化した述語ベクトルの各要素を処理装置により設定する。つまり、基底ベクトルb(i=1,...,μ)に対する係数には、述語ベクトルの各要素が埋め込まれる。また、鍵ベクトル生成部130は、基底ベクトルbn+1に対する係数として乱数ηを処理装置により設定するとともに、基底ベクトルbn+2に対する係数として1から乱数ηを引いた値(1−η)を処理装置により設定する。つまり、基底ベクトルbn+1に対する係数と基底ベクトルbn+2に対する係数との和が1となるように、基底ベクトルbn+1に対する係数と基底ベクトルbn+2に対する係数とが設定される。これにより、鍵ベクトル生成部130は、鍵ベクトルkL,decを生成する。
【0058】
(S303:ランダム化ベクトルkL,ran,j生成ステップ)
ランダム化ベクトル生成部140は、マスター公開鍵pkとマスター秘密鍵skと、数163に示す述語ベクトル(v,...,v)とに基づき、数165を計算して、ランダム化ベクトルkL,ran,j(j=1,...,L+1)を生成する。ランダム化ベクトルkL,ran,j(j=1,...,L+1)は、下位の鍵のうち、述語ベクトルの各要素が埋め込まれる基底ベクトルに対する係数を一様に分布させるためのベクトルである。なお、ランダム化ベクトルkL,ran,jは、第L層目の秘密鍵のj番目の要素である。
【数165】

つまり、(1)ランダム化ベクトル生成部140は、乱数σj,i(j=1,...,L+1;i=1,...,L)と乱数η(j=1,...,L+1)とを処理装置により生成する。
(2)ランダム化ベクトル生成部140は、j=1,...,L+1の各jについて、基底ベクトルb(i=1,...,μ)に対する係数として、乱数σj,tでランダム化した述語ベクトルの各要素を設定したベクトルvvを処理装置により生成する。つまり、基底ベクトルb(i=1,...,μ)に対する係数には、述語ベクトルの各要素が埋め込まれる。
(3)ランダム化ベクトル生成部140は、j=1,...,L+1の各jについて、基底ベクトルbn+1に対する係数として乱数ηを処理装置により設定するとともに、基底ベクトルbn+2に対する係数として0から乱数ηを引いた値(−η)を設定したベクトルdvを処理装置により生成する。つまり、基底ベクトルbn+1に対する係数と基底ベクトルbn+2に対する係数との和が0となるように、基底ベクトルbn+1に対する係数と基底ベクトルbn+2に対する係数とが設定される。
(4)ランダム化ベクトル生成部140は、j=1,...,L+1の各jについて、生成したベクトルvvとベクトルdvと加算して、ランダム化ベクトルkL,ran,j(j=1,...,L+1)を生成する。
【0059】
(S304:鍵生成用ベクトルkL,del,j生成ステップ)
鍵生成用ベクトル生成部150は、マスター公開鍵pkとマスター秘密鍵skと、数163に示す述語ベクトル(v,...,v)とに基づき、数166を計算して、鍵生成用ベクトルkL,del,j(j=μ+1,...,n)を処理装置により生成する。鍵生成用ベクトルkL,del,j(j=μ+1,...,n)は、下位の秘密鍵(下位の鍵ベクトル)を生成するためのベクトルである。なお、鍵生成用ベクトルkL,del,jは、第L層目の秘密鍵のj番目の要素である。
【数166】

つまり、(1)鍵生成用ベクトル生成部150は、乱数σj,i(j=μ+1,...,n;i=1,...,L)と乱数ψと乱数η(j=μ+1,...,n)とを処理装置により生成する。
(2)鍵生成用ベクトル生成部150は、j=μ+1,...,nの各jについて、基底ベクトルb(i=1,...,μ)に対する係数として、乱数σj,tでランダム化した述語ベクトルの各要素を設定して、ベクトルvvを処理装置により生成する。つまり、基底ベクトルb(i=1,...,μ)に対する係数には、述語ベクトルの各要素が埋め込まれる。
(3)鍵生成用ベクトル生成部150は、j=μ+1,...,nの各jについて、基底ベクトルbに対する係数として乱数ψを設定して、ベクトルψvを処理装置により生成する。
(4)鍵生成用ベクトル生成部150は、j=μ+1,...,nの各jについて、基底ベクトルbn+1に対する係数として乱数ηを処理装置により設定するとともに、基底ベクトルbn+2に対する係数として0から乱数ηを引いた値(−η)を設定して、ベクトルdvを処理装置により生成する。つまり、基底ベクトルbn+1に対する係数と基底ベクトルbn+2に対する係数との和が0となるように、基底ベクトルbn+1に対する係数と基底ベクトルbn+2に対する係数とが設定される。
(5)鍵生成用ベクトル生成部150は、j=μ+1,...,nの各jについて、ベクトルvvと、ベクトルψvと、ベクトルdvとを加算して、鍵生成用ベクトルkL,del,j(j=μ+1,...,n)を生成する。
【0060】
すなわち、(S302)から(S304)において、鍵ベクトル生成部130とランダム化ベクトル生成部140と鍵生成用ベクトル生成部150とは、数167に示すGenKeyアルゴリズムを処理装置により実行する。これにより、鍵ベクトルkL,decと、ランダム化ベクトルkL,ran,j(j=1,...,L+1)と、鍵生成用ベクトルkL,del,j(j=μ+1,...,n)とを含む第L層目の秘密鍵(鍵情報k→*)が生成される。
【数167】

【0061】
(S305:鍵配布ステップ)
鍵配布部160は、マスター鍵生成部110が生成したマスター公開鍵と、鍵ベクトル生成部130とランダム化ベクトル生成部140と鍵生成用ベクトル生成部150とが生成した鍵情報k→*とを復号装置300へ通信装置を介して送信する。また、鍵配布部160は、マスター公開鍵を暗号化装置200へ通信装置を介して送信する。ここで、鍵情報k→*は秘密裡に復号装置300へ送信されるが、鍵情報k→*を秘密裡に復号装置300へ送信する方法に関しては、どのような方法であっても構わない。例えば、従来の暗号処理を使用して送信してもよい。
【0062】
暗号化装置200の機能と動作とについて説明する。暗号化装置200は、送信情報設定部210、暗号ベクトル生成部220、暗号情報生成部230、データ送信部240、公開鍵取得部250を備える。
なお、以下の処理の前に、公開鍵取得部250は、マスター公開鍵pkと、復号装置300の述語情報ベクトルに対応する属性情報ベクトルを取得しているものとする。
【0063】
(S401:送信情報設定ステップ)
送信情報設定部210は、マスター公開鍵pkに基づき、数168を処理装置により計算して送信情報ベクトルζvを生成する。
【数168】

つまり、(1)送信情報設定部210は、乱数ζを処理装置により生成する。
(2)送信情報設定部210は、マスター公開鍵pkに含まれる基底B^の基底ベクトルdn+1に対する係数として乱数ζを処理装置により設定して、送信情報ベクトルζvを生成する。
【0064】
(S402:暗号ベクトルc生成ステップ)
暗号ベクトル生成部220は、マスター公開鍵pkと、数169に示す属性ベクトル(x,...,x)とに基づき、数170を処理装置により計算して暗号ベクトルcを生成する。
【数169】

【数170】

つまり、(1)暗号ベクトル生成部220は、乱数(xL+1,...,x)と、乱数δ(i=1,...,d,n+3)を処理装置により生成する。
(2)暗号ベクトル生成部220は、マスター公開鍵pkに含まれる基底Bの基底ベクトルb(i=1,...,μ)に対する係数として属性ベクトルの各要素を処理装置により設定する。つまり、基底ベクトルb(i=1,...,μ)に対する係数には、属性ベクトルの各要素が埋め込まれる。また、暗号ベクトル生成部220は、基底ベクトルb(i=μ+1,...,n)に対する係数として乱数を処理装置により設定する。これにより、暗号ベクトル生成部220は、ベクトルxvを生成する。
(3)暗号ベクトル生成部220は、マスター公開鍵pkに含まれる基底Bの基底ベクトルbn+3に対する係数として乱数δn+3を処理装置により設定して、ベクトルrvを生成する。
(4)暗号ベクトル生成部220は、生成したベクトルxvとベクトルrvとを、送信情報設定部210が生成した送信情報ベクトルζvに加算して暗号ベクトルcを処理装置により生成する。
なお、ベクトルrvは、安全性を高くするために加えられるものであり、必須の要素ではない。
【0065】
(S403:暗号情報c生成ステップ)
暗号情報生成部230は、平文情報mに基づき、数171を処理装置により計算して暗号情報cを生成する。
【数171】

【0066】
(S404:データ送信ステップ)
データ送信部240は、暗号ベクトル生成部220が生成した暗号ベクトルcと、暗号情報生成部230が生成した暗号情報cとを復号装置300へ通信装置を介して送信する。
【0067】
すなわち、暗号化装置200は、数172に示すEncアルゴリズムを実行して、暗号ベクトルcと暗号情報cとを生成する。
【数172】

【0068】
復号装置300の機能と動作とについて説明する。復号装置300は、ベクトル入力部310、鍵ベクトル記憶部320、ペアリング演算部330を備える。
【0069】
(S501:ベクトル入力ステップ)
ベクトル入力部310は、暗号化装置200のデータ送信部240が送信した暗号ベクトルcと暗号情報cとを通信装置を介して受信して入力する。
【0070】
(S502:復号ステップ)
ペアリング演算部330は、マスター公開鍵pkと第L層目の秘密鍵の先頭要素である鍵ベクトルkL,decとに基づき、数173を処理装置により計算して平文情報m’を生成する。
【数173】

つまり、ペアリング演算部330は、ベクトル入力部310が入力した暗号ベクトルcと、鍵ベクトル記憶部320が記憶装置に記憶した鍵ベクトルkL,decとについて、ペアリング演算eを処理装置により行う。これにより、ペアリング演算部330は、gζを計算する。そして、計算したgζで暗号情報c(=gζm)を除することにより、平文情報m’(=m)を計算する。なお、鍵ベクトル記憶部320は、鍵生成装置100又は上位の鍵委譲装置400から鍵ベクトルkL,decを配布された際、鍵ベクトルkL,decを記憶装置に記憶している。
ここで、暗号化装置200が暗号化に用いた属性ベクトルx(i=1,...,h)と、復号装置300が復号に用いた鍵ベクトルの述語ベクトルv(i=1,...,L)とについて、L≦hであり、全てのi(i=1,...,L)についてx・v=0であれば、数174に示すように、暗号ベクトルcと鍵ベクトルkL,decとについてペアリング演算eを行うことにより、gζを得ることができる。
【数174】

【0071】
つまり、復号装置300は、数175に示すDecアルゴリズムを実行して、平文情報m’を生成する。
【数175】

【0072】
鍵委譲装置400の機能と動作とについて説明する。鍵委譲装置400は、鍵ベクトル取得部410(鍵生成用ベクトル取得部)、鍵ベクトル生成部420、ランダム化ベクトル生成部430、鍵生成用ベクトル生成部440、鍵配布部450を備える。
【0073】
(S601:鍵情報k取得ステップ)
鍵ベクトル取得部410は、第L層目の秘密鍵の先頭要素である鍵ベクトルkL,decと、ランダム化ベクトルkL,ran,j(j=1,...,L+1)と、鍵生成用ベクトルkL,del,j(j=μ+1,...,n)とを含む第L層目の秘密鍵(鍵情報k→*)を通信装置を介して取得する。
【0074】
(S602:鍵ベクトルkL+1,dec生成ステップ)
鍵ベクトル生成部420は、マスター公開鍵pkと鍵情報k→*と数176に示す述語ベクトルvL+1とに基づき、数177を計算して、第L+1層目の秘密鍵の先頭要素である鍵ベクトルkL+1,decを処理装置により生成する。
【数176】

【数177】

つまり、(1)鍵ベクトル生成部420は、乱数α0,i(i=1,...,L+1)と乱数σとを処理装置により生成する。
(2)鍵ベクトル生成部420は、i=1,...,L+1の各iについて、ランダム化ベクトルkL,ran,iの係数を乱数α0,i倍したベクトルを加算して、ベクトルrvを処理装置により生成する。なお、ランダム化ベクトルkL,ran,i(i=1,...,L+1)における基底ベクトルb(i=1,...,μ)に対する係数には、述語ベクトルの各要素が埋め込まれている。そのため、ベクトルrvにおける基底ベクトルb(i=1,...,μ)に対する係数には、乱数倍された述語ベクトルの各要素が埋め込まれる。
(3)鍵ベクトル生成部420は、鍵生成用ベクトルkL,del,i(i=μ+1,...,μL+1)の係数に述語ベクトルvL+1の各要素を設定したベクトルを加算し、乱数σ倍してベクトルvvを処理装置により生成する。つまり、基底ベクトルb(i=μ+1,...,μL+1)に対する係数には、述語ベクトルの各要素が埋め込まれる。
(4)鍵ベクトル生成部420は、鍵ベクトルkL,decと、ベクトルrvとベクトルvvとを加算して、鍵ベクトルkL+1,decを処理装置により生成する。
【0075】
(S603:ランダム化ベクトルkL+1,ran,j生成ステップ)
ランダム化ベクトル生成部430は、マスター公開鍵pkと鍵情報k→*と数176に示す述語ベクトルvL+1とに基づき、数178を計算して、ランダム化ベクトルkL,ran,j(j=1,...,L+2)を生成する。ランダム化ベクトルkL,ran,j(j=1,...,L+2)は、下位の鍵のうち、述語ベクトルの各要素が埋め込まれる基底ベクトルに対する係数を一様に分布させるためのベクトルである。なお、ランダム化ベクトルkL,ran,jは、第L+1層目の秘密鍵のj番目の要素である。
【数178】

つまり、(1)ランダム化ベクトル生成部430は、乱数αj,i(j=1,...,L+2;i=1,...,L)と乱数σ(j=1,...,L+2)とを処理装置により生成する。
(2)ランダム化ベクトル生成部430は、j=1,...,L+2の各jについて、ランダム化ベクトルkL,ran,i(i=1,...,L+1)の係数を乱数αj,i(i=1,...,L+1)倍してベクトルrvを処理装置により生成する。上述したように、ランダム化ベクトルkL,ran,i(i=1,...,L+1)における基底ベクトルb(i=1,...,μ)に対する係数には、述語ベクトルの各要素が埋め込まれている。そのため、ベクトルrvにおける基底ベクトルb(i=1,...,μ)に対する係数には、乱数倍された述語ベクトルの各要素が埋め込まれる。
(3)ランダム化ベクトル生成部430は、j=1,...,L+2の各jについて、鍵生成用ベクトルkL,del,i(i=μ+1,...,μL+1)の係数に述語ベクトルの各要素を設定したベクトルを加算し、乱数σ倍してベクトルvvを処理装置により生成する。つまり、基底ベクトルb(i=μ+1,...,μL+1)に対する係数には、述語ベクトルの各要素が埋め込まれる。
(4)ランダム化ベクトル生成部430は、j=1,...,L+2の各jについて、生成したベクトルrvとベクトルvvとを加算して、ランダム化ベクトルkL+1,ran,jを処理装置により生成する。
【0076】
(S604:鍵生成用ベクトルkL+1,del,j生成ステップ)
鍵生成用ベクトル生成部440は、マスター公開鍵pkと鍵情報k→*と数176に示す述語ベクトルvL+1とに基づき、数179を計算して、鍵生成用ベクトルkL+1,del,j(j=μL+1+1,...,n)を処理装置により生成する。鍵生成用ベクトルkL+1,del,j(j=μL+1+1,...,n)は、下位の秘密鍵(下位の鍵ベクトル)を生成するためのベクトルである。なお、鍵生成用ベクトルkL+1,del,jは、第L+1層目の秘密鍵のj番目の要素である。
【数179】

つまり、(1)鍵生成用ベクトル生成部440は、乱数αj,i(j=μL+1+1,...,n;i=1,...,L+1)と、乱数σ(j=μL+1+1,...,n)と、乱数ψ’とを処理装置により生成する。
(2)鍵生成用ベクトル生成部440は、j=μL+1+1,...,nの各jについて、ランダム化ベクトルkL,ran,i(i=1,...,L+1)の係数を乱数αj,i倍したベクトルrvを処理装置により生成する。上述したように、ランダム化ベクトルkL,ran,i(i=1,...,L+1)における基底ベクトルb(i=1,...,μ)に対する係数には、述語ベクトルの各要素が埋め込まれている。そのため、ベクトルrvにおける基底ベクトルb(i=1,...,μ)に対する係数には、乱数倍された述語ベクトルの各要素が埋め込まれる。
(3)鍵生成用ベクトル生成部440は、j=μL+1+1,...,nの各jについて、鍵生成用ベクトルkL,del,i(i=μ+1,...,μL+1)の係数に述語ベクトルの各要素を設定したベクトルを加算し、乱数σ倍してベクトルvvを処理装置により生成する。つまり、基底ベクトルb(i=μ+1,...,μL+1)に対する係数には、述語ベクトルの各要素が埋め込まれる。
(4)鍵生成用ベクトル生成部440は、j=μL+1+1,...,nの各jについて、鍵生成用ベクトルkL,del,jの係数を乱数ψ’倍して、ベクトルψvを処理装置により生成する。なお、鍵生成用ベクトルkL,del,jにおける基底ベクトルb(j=μL+1+1,...,n)に対する係数には、述語ベクトルの要素が埋め込まれている。そのため、ベクトルψv(j=μL+1+1,...,n)における基底ベクトルbに対する係数には、乱数倍された述語ベクトルの要素が埋め込まれる。
(5)鍵生成用ベクトル生成部440は、j=μL+1+1,...,nの各jについて、生成したベクトルrvと、ベクトルvvと、ベクトルψvとを加算して、鍵生成用ベクトルkL+1,del,j(j=μL+1+1,...,n)を処理装置により生成する。
【0077】
すなわち、(S602)から(S604)において、鍵ベクトル生成部420とランダム化ベクトル生成部430と鍵生成用ベクトル生成部440とは、数180に示すDelegateアルゴリズムを実行して、鍵ベクトルkL+1,decと、ランダム化ベクトルkL+1,ran,j(j=1,...,L+2)と、鍵生成用ベクトルkL+1,del,j(j=μL+1+1,...,n)とを含む第L+1層目の秘密鍵(鍵情報k→*L+1)を処理装置により生成する。
【数180】

【0078】
(S605:鍵配布ステップ)
鍵配布部440は、鍵ベクトル生成部420とランダム化ベクトル生成部430と鍵生成用ベクトル生成部440とが生成した鍵情報k→*L+1を下位の復号装置300へ通信装置を介して送信する。ここで、鍵情報k→*L+1は秘密裡に復号装置300へ送信されるが、鍵情報k→*L+1を秘密裡に復号装置300へ送信する方法に関しては、どのような方法であっても構わない。例えば、従来の暗号処理を使用して送信してもよい。
【0079】
以上のように、暗号処理システム10が実現する暗号処理は、非特許文献18で提案されている暗号処理よりも安全性が高く、標準のモデル(Standard Model)における安全性を証明することができる。
この理由は、主に以下の(1)(2)の2点である。
(1)暗号化装置200が送信情報を設定する基底ベクトルdn+1が2次元(基底ベクトルbn+1と基底ベクトルbn+2)である。これにより、基底ベクトルdn+1に対応する鍵ベクトルkL,decにおける基底ベクトルbn+1と基底ベクトルbn+2とに対する係数をランダムに選択することが可能となる。また、基底ベクトルdn+1が公開されるだけであり、基底ベクトルbn+1と基底ベクトルbn+2とは秘密にされている。
(2)鍵委譲装置400が下位の鍵を生成する場合に、ランダム化ベクトルを用いて生成する。これにより、下位の鍵の所定の基底ベクトルに対する係数をランダム化することができ、下位の鍵を生成することによって、鍵の安全性が劣化しない。
ここで、ランダム化ベクトルを用いない場合、鍵情報k→*から生成される2つの下位の鍵ベクトルkL+1,dec(A)と鍵ベクトルkL+1,dec(B)とは、数181のようになる。
【数181】

つまり、ランダム化ベクトルを用いない場合、鍵ベクトルkL,decに含まれる述語情報が設定された基底ベクトルb(i=1,...,μ)の係数は、鍵ベクトルkL+1,dec(A)と鍵ベクトルkL+1,dec(B)との間で共通になってしまう。
しかし、ランダム化ベクトルを用いる場合、鍵情報k→*から生成される2つの下位の鍵ベクトルkL+1,dec(A)と鍵ベクトルkL+1,dec(B)とは、数182のようになる。
【数182】

つまり、ランダム化ベクトルを用いる場合、鍵ベクトルkL+1,dec(A)には、乱数αA,iで係数の値を一様に分布したランダム化ベクトルkL,ran,iが加えられ、鍵ベクトルkL+1,dec(B)には、乱数αB,iで係数の値を一様に分布したランダム化ベクトルkL,ran,iが加えられる。ここで、ランダム化ベクトルkL,ran,iには、基底ベクトルb(i=1,...,μ)が含まれている。したがって、鍵ベクトルkL+1,dec(A)と鍵ベクトルkL+1,dec(B)とにおける基底ベクトルb(i=1,...,μ)の係数の値は一様に分布している。つまり、鍵ベクトルkL+1,dec(A)と鍵ベクトルkL+1,dec(B)とにおいて、述語情報が設定された基底ベクトルb(i=1,...,μ)の係数は異なる。
【0080】
なお、以上の説明では、暗号化装置200が送信情報を設定する基底ベクトルdn+1を2次元とした。しかし、基底ベクトルdn+1は3次元以上のm次元(基底ベクトルbn+1,...,基底ベクトルbn+m)であってもよい。
この場合には、(S301)において、マスター鍵生成部110は、N=n+m+1とする。また、鍵ベクトルkL,dec生成ステップ(S302)において、鍵ベクトル生成部130は、基底ベクトルbn+1,...,基底ベクトルbn+mに対する係数の和が1になるように、基底ベクトルbn+1,...,基底ベクトルbn+mに対する係数を設定する。また、ランダム化ベクトルkL,ran,j生成ステップ(S303)において、ランダム化ベクトル生成部140は、基底ベクトルbn+1,...,基底ベクトルbn+mに対する係数の和が0になるように、基底ベクトルbn+1,...,基底ベクトルbn+mに対する係数を設定する。同様に、鍵生成ベクトルkL,del,j生成ステップ(S304)において、鍵生成用ベクトル生成部150は、基底ベクトルbn+1,...,基底ベクトルbn+mに対する係数の和が0になるように、基底ベクトルbn+1,...,基底ベクトルbn+mに対する係数を設定する。また、暗号ベクトルc生成ステップ(S402)において、暗号ベクトル生成部220は、基底ベクトルbn+m+1に対する係数として乱数を設定してベクトルrvを生成する。
【0081】
また、上記説明では、N(=n+3)次元ベクトル空間で暗号処理を実現したが、権限委譲のない暗号処理であれば、nは1以上の整数である。したがって、Nは4以上の整数である。また、権限委譲を有する暗号処理であれば、nは2以上の整数である。したがって、Nは5以上の整数である。なお、上述したように、(S402)において、暗号化装置200が基底ベクトルbn+3を用いて、ベクトルrvを生成することは必須ではない。ベクトルrvを生成しないのであれば、N(=n+2)次元ベクトル空間で暗号処理を実現できる。したがって、権限委譲のない暗号処理であれば、Nは3以上の整数であり、権限委譲を有する暗号処理であれば、Nは4以上の整数である。
【0082】
また、上述した暗号処理では、双対ペアリングベクトル空間であることの条件に含まれていたディストーション写像を利用していない。ディストーション写像については、暗号処理を実現するアルゴリズムでは使用せず、暗号処理の安全性を証明するために使用する。したがって、上述した暗号処理は、ディストーション写像がない空間であっても成立するということができる。すなわち、上述した暗号処理を実現する空間にディストーション写像があることは、必須ではない。以下に説明する暗号処理についても同様である。
【0083】
また、上記説明では、階層的述語暗号について説明した。次に、階層的述語鍵秘匿方式について説明する。階層的述語鍵秘匿方式について、上述した階層的述語暗号と異なる部分のみを説明する。
図17は、階層的述語鍵秘匿方式を実現する暗号処理システム10の機能を示す機能ブロック図である。
ここで、鍵生成装置100の処理と鍵委譲装置400の処理とは、上述した階層的述語暗号の場合と同様である。そこで、ここでは、暗号化装置200の処理と復号装置300の処理とのみを説明する。
図18は、暗号化装置200の動作を示すフローチャートである。図19は、復号装置300の動作を示すフローチャートである。
【0084】
暗号化装置200の機能と動作とについて説明する。
図17に示す暗号化装置200は、図11に示す暗号化装置200が備える機能に加え、セッション鍵生成部260を備える。なお、図17に示す暗号化装置200は、図11に示す暗号化装置200が備える暗号情報生成部230は備えていない。
(S701)と(S702)とは、(S401)と(S402)と同様である。
(S703:データ送信ステップ)では、(S702)で暗号ベクトル生成部220が生成した暗号ベクトルcを復号装置300へ通信装置を介して送信する。つまり、階層的述語鍵秘匿方式では、平文情報mを埋め込んだ暗号情報cは生成されず、復号装置300へ送信されない。
(S704:セッション鍵生成ステップ)では、セッション鍵生成部260が数183を処理装置により計算してセッション鍵Kを生成する。
【数183】

【0085】
すなわち、暗号化装置200は、数184に示すEncアルゴリズムを実行して、暗号ベクトルcとセッション鍵Kとを生成する。
【数184】

【0086】
復号装置300の機能と動作とについて説明する。
図17に示す復号装置300は、図11に示す復号装置300と同様の機能構成である。
(S801:ベクトル入力ステップ)
ベクトル入力部310は、暗号化装置200のデータ送信部240が送信した暗号ベクトルcを通信装置を介して受信して入力する。
【0087】
(S802:復号ステップ)
ペアリング演算部330は、マスター公開鍵pkと第L層目の秘密鍵の先頭要素である鍵ベクトルkL,decとに基づき、数185を処理装置により計算してセッション鍵Kを生成する。
【数185】

つまり、ペアリング演算部330は、ベクトル入力部310が入力した暗号ベクトルcと、鍵ベクトル記憶部320が記憶装置に記憶した鍵ベクトルkL,decとについて、ペアリング演算eを処理装置により行う。これにより、ペアリング演算部330は、暗号化装置200が埋め込んだζに関する値であるgζ(=K)を計算する。
【0088】
すなわち、復号装置300は、数186に示すDecアルゴリズムを実行して、セッション鍵K’(=K)を生成する。
【数186】

【0089】
以上のように、階層的述語鍵秘匿方式によれば、暗号化装置200から復号装置300へ、セッション鍵Kを秘密裡に送信することができる。つまり、暗号化装置200と復号装置300との間でセッション鍵を共有することができる。
【0090】
実施の形態3.
実施の形態3では、実施の形態2で説明した階層的述語暗号と階層的述語鍵秘匿方式とよりも一般化された権限委譲を有する述語暗号について説明する。
【0091】
上述したように、実施の形態2で説明した階層的述語暗号と階層的述語鍵秘匿方式とでは、図16に示すように基底ベクトルを使用した。つまり、n+3個の基底ベクトルのうち、n個の基底ベクトルを属性ベクトルや述語ベクトルのための基底ベクトルとして、階層構造を表すために使用した。特に、初めのμ個の基底ベクトルを第1層目の属性ベクトルや述語ベクトルのための基底ベクトルとし、μ−μ個の基底ベクトルを第2層目の属性ベクトルや述語ベクトルのための基底ベクトルとし、以下同様に、μ−μL−1個の基底ベクトルを第L層目の属性ベクトルや述語ベクトルのための基底ベクトルとした。
そして、第L層目の鍵ベクトルkL,decを数164に示すように計算した。つまり、第L層目の鍵ベクトルkL,decは、基底ベクトルb(i=1,...,L)に対する係数として述語ベクトルの各要素を割り当てられ、基底ベクトルb(i=L+1,...,n)に対する係数として0を割り当てられた。
また、第L層目の暗号ベクトルcを数170に示すように計算した。つまり、第L層目の暗号ベクトルcは、基底ベクトルb(i=1,...,L)に対する係数として属性ベクトルの各要素を割り当てられ、基底ベクトルb(i=L+1,...,n)に対する係数として乱数を割り当てられた。
これにより、階層的に権限委譲することが実現された。
【0092】
実施の形態3で説明する述語暗号(述語鍵秘匿方式)では、実施の形態2の場合と同様に、n+3個の基底ベクトルのうち、n個の基底ベクトルを属性ベクトルや述語ベクトルのための基底ベクトルとして使用する。しかし、どの鍵であっても(上位の鍵であっても、下位の鍵であっても)、n個の基底ベクトル全てを述語ベクトルのための基底ベクトルとする。つまり、n個の基底ベクトル全てを常に属性ベクトルや述語ベクトルのための基底ベクトルとする。
そして、鍵ベクトルkL,decは、基底ベクトルb(i=1,...,n)に対する係数として述語ベクトルの各要素を割り当てられる。また、第L層目の暗号ベクトルcは、基底ベクトルb(i=1,...,n)に対する係数として属性ベクトルの各要素を割り当てられる。
つまり、n個の基底ベクトルについて階層構造という概念はない。また、秘密鍵が階層的に権限委譲される概念はない。そのため、実施の形態2で説明した暗号方式に比べ、より自由度の高い権限委譲が可能となる。
【0093】
まず、権限委譲を有する述語暗号を実現する場合について説明する。
図20は、権限委譲を有する述語暗号を実現する暗号処理システム10の機能を示す機能ブロック図である。なお、図20に示す暗号処理システム10が備える機能は、図11に示す暗号処理システム10が備える機能と同様である。
権限委譲を有する述語暗号を実現する場合における実施の形態3に係る暗号処理システム10の動作の流れは、実施の形態2に係る暗号処理システム10の動作の流れと同様である。そこで、図20と、図12から図16とに基づき、実施の形態3に係る暗号処理システム10の機能と動作とについて説明する。
【0094】
鍵生成装置100の機能と動作とについて説明する。
(S301:マスター鍵生成ステップ)
実施の形態2における(S301)と同様に、マスター鍵生成部110は、数187を計算して、マスター公開鍵pkとマスター秘密鍵skとを処理装置により生成してマスター鍵記憶部120に記憶する。
【数187】

【0095】
(S302:鍵ベクトルkL,dec生成ステップ)
鍵ベクトル生成部130は、マスター公開鍵pkとマスター秘密鍵skと、数188に示す述語ベクトル(v,...,v)とに基づき、数189を計算して、第L層目(レベルL)の秘密鍵の先頭要素である鍵ベクトルkL,decを処理装置により生成する。
【数188】

【数189】

【0096】
(S303:ランダム化ベクトルkL,ran,j生成ステップ)
ランダム化ベクトル生成部140は、マスター公開鍵pkとマスター秘密鍵skと、数188に示す述語ベクトル(v,...,v)とに基づき、数190を計算して、ランダム化ベクトルkL,ran,j(j=1,...,L+1)を生成する。
【数190】

【0097】
(S304:鍵生成用ベクトルkL,del,j生成ステップ)
鍵生成用ベクトル生成部150は、マスター公開鍵pkとマスター秘密鍵skと、数188に示す述語ベクトル(v,...,v)とに基づき、数191を計算して、鍵生成用ベクトルkL,del,j(j=1,...,n)を処理装置により生成する。
【数191】

【0098】
すなわち、(S302)から(S304)において、鍵ベクトル生成部130とランダム化ベクトル生成部140と鍵生成用ベクトル生成部150とは、数192に示すGenKeyアルゴリズムを処理装置により実行する。これにより、鍵ベクトルkL,decと、ランダム化ベクトルkL,ran,j(j=1,...,L+1)と、鍵生成用ベクトルkL,del,j(j=1,...,n)とを含む第L層目の秘密鍵(鍵情報k→*)が生成される。
【数192】

【0099】
(S305:鍵配布ステップ)
実施の形態2における(S305)と同様に、鍵配布部160は、マスター鍵生成部110が生成したマスター公開鍵と、鍵ベクトル生成部130とランダム化ベクトル生成部140と鍵生成用ベクトル生成部150とが生成した鍵情報k→*とを復号装置300へ通信装置を介して送信する。また、鍵配布部160は、マスター公開鍵を暗号化装置200へ通信装置を介して送信する。
【0100】
暗号化装置200の機能と動作とについて説明する。
(S401:送信情報設定ステップ)
実施の形態2における(S401)と同様に、送信情報設定部210は、マスター公開鍵pkに基づき、数193を処理装置により計算して送信情報ベクトルζvを生成する。
【数193】

【0101】
(S402:暗号ベクトルc生成ステップ)
暗号ベクトル生成部220は、マスター公開鍵pkと、数194に示す属性ベクトル(x,...,x)とに基づき、数195を処理装置により計算して暗号ベクトルcを生成する。
【数194】

【数195】

【0102】
(S403:暗号情報c生成ステップ)
実施の形態2における(S403)と同様に、暗号情報生成部230は、平文情報mに基づき、数196を処理装置により計算して暗号情報cを生成する。
【数196】

【0103】
(S404:データ送信ステップ)
実施の形態2における(S404)と同様に、データ送信部240は、暗号ベクトル生成部220が生成した暗号ベクトルcと、暗号情報生成部230が生成した暗号情報cとを復号装置300へ通信装置を介して送信する。
【0104】
すなわち、暗号化装置200は、数197に示すEncアルゴリズムを実行して、暗号ベクトルcと暗号情報cとを生成する。
【数197】

【0105】
復号装置300の機能と動作とについて説明する。
(S501:ベクトル入力ステップ)
実施の形態2における(S501)と同様に、ベクトル入力部310は、暗号化装置200のデータ送信部240が送信した暗号ベクトルcと暗号情報cとを通信装置を介して受信して入力する。
【0106】
(S502:復号ステップ)
実施の形態2における(S502)と同様に、ペアリング演算部330は、マスター公開鍵pkと第L層目の秘密鍵の先頭要素である鍵ベクトルkL,decとに基づき、数198を処理装置により計算して平文情報m’を生成する。
【数198】

ここで、暗号化装置200が暗号化に用いた属性ベクトルx(i=1,...,h)と、復号装置300が復号に用いた鍵ベクトルの述語ベクトルv(j=1,...,L)とについて、全てのi(i=1,...,h)、j(j=1,...,L)についてx・v=0であるなら、ペアリング演算部330は、平文情報mを生成することができる。なお、平文情報m∈Gであるとする。
【0107】
つまり、復号装置300は、数199に示すDecアルゴリズムを実行して、平文情報m’を生成する。
【数199】

【0108】
鍵委譲装置400の機能と動作とについて説明する。
(S601:鍵情報k→*取得ステップ)
実施の形態2における(S601)と同様に、鍵ベクトル取得部410は、第L層目の秘密鍵の先頭要素である鍵ベクトルkL,decと、ランダム化ベクトルkL,ran,j(j=1,...,L+1)と、鍵生成用ベクトルkL,del,j(j=1,...,n)とを含む第L層目の秘密鍵(鍵情報k→*)を通信装置を介して取得する。
【0109】
(S602:鍵ベクトルkL+1,dec生成ステップ)
鍵ベクトル生成部420は、マスター公開鍵pkと鍵情報k→*と数200に示す述語ベクトルvL+1とに基づき、数201を計算して、第L+1層目の秘密鍵の先頭要素である鍵ベクトルkL+1,decを処理装置により生成する。
【数200】

【数201】

【0110】
(S603:ランダム化ベクトルkL+1,ran,j生成ステップ)
ランダム化ベクトル生成部430は、マスター公開鍵pkと鍵情報k→*と数200に示す述語ベクトルvL+1とに基づき、数202を計算して、ランダム化ベクトルkL+1,ran,j(j=1,...,L+2)を生成する。
【数202】

【0111】
(S604:鍵生成用ベクトルkL+1,del,j生成ステップ)
鍵生成用ベクトル生成部440は、マスター公開鍵pkと鍵情報k→*と数200に示す述語ベクトルvL+1とに基づき、数203を計算して、鍵生成用ベクトルkL+1,del,j(j=1,...,n)を処理装置により生成する。
【数203】

【0112】
すなわち、(S602)から(S604)において、鍵ベクトル生成部420とランダム化ベクトル生成部430と鍵生成用ベクトル生成部440とは、数204に示すDelegateアルゴリズムを実行して、鍵ベクトルkL+1,decと、ランダム化ベクトルkL+1,ran,j(j=1,...,L+2)と、鍵生成用ベクトルkL+1,del,j(j=1,...,n)とを含む第L+1層目の秘密鍵(鍵情報k→*L+1)を処理装置により生成する。
【数204】

【0113】
(S605:鍵配布ステップ)
実施の形態2における(S605)と同様に、鍵配布部450は、鍵ベクトル生成部420とランダム化ベクトル生成部430と鍵生成用ベクトル生成部440とが生成した鍵情報k→*L+1を下位の復号装置300へ通信装置を介して送信する。
【0114】
上述したように、暗号化装置200が暗号化に用いた属性ベクトルx(i=1,...,h)と、復号装置300が復号に用いた鍵ベクトルkL,decの述語ベクトルv(j=1,...,L)とについて、全てのi(i=1,...,h)、j(j=1,...,L)についてx・v=0であるなら、復号装置300は復号することができる。つまり、述語ベクトル(v)に基づき生成された鍵ベクトルk1,decで復号する場合、x・v=0であるなら、復号装置300は復号することができる。また、述語ベクトル(v,v)に基づき生成された鍵ベクトルk2,decで復号する場合、x・v=0かつx・v=0であるなら、復号装置300は復号することができる。つまり、実施の形態2で説明したアルゴリズムと同様に、下位の鍵ベクトルk2,decは、上位の鍵ベクトルk1,decよりも機能が制限されている。
【0115】
なお、実施の形態2と同様に、以上の説明では、暗号化装置200が送信情報を設定する基底ベクトルdn+1を2次元とした。しかし、基底ベクトルdn+1は3次元以上のm次元(基底ベクトルbn+1,...,基底ベクトルbn+m)であってもよい。
【0116】
また、実施の形態2と同様に、暗号化装置200が実行するEncアルゴリズムと、復号装置300が実行するDecアルゴリズムとを、それぞれ数205と数206とのように変更することで、階層的述語鍵秘匿方式を実現することも可能である。
【数205】

【数206】

【0117】
実施の形態4.
以上の実施の形態では、双対ベクトル空間において暗号処理を実現する方法について説明した。この実施の形態では、双対加群において暗号処理を実現する方法について説明する。
【0118】
つまり、以上の実施の形態では、素数位数qの巡回群において暗号処理を実現した。しかし、合成数Mを用いて数207のように環Rを表した場合、環Rを係数とする加群においても、上記実施の形態で説明した暗号処理を適用することができる。
【数207】

【0119】
例えば、実施の形態2で説明した階層的述語暗号を、環Rを係数とする加群において実現すると数208から数212のようになる。
【数208】

【数209】

【数210】

【数211】

【数212】

【0120】
ここでは、実施の形態2で説明した階層的述語暗号についてのみ、環Rを係数とする加群において実現する方法を示した。しかし、原則として、以上の実施の形態で体Fとして説明した処理を、環Rに置き換えることにより、以上の実施の形態で説明した他の暗号処理についても、環Rを係数とする加群において実現できる。
【0121】
次に、実施の形態における暗号処理システム10(鍵生成装置100、暗号化装置200、復号装置300、鍵委譲装置400)のハードウェア構成について説明する。
図21は、鍵生成装置100、暗号化装置200、復号装置300、鍵委譲装置400のハードウェア構成の一例を示す図である。
図21に示すように、鍵生成装置100、暗号化装置200、復号装置300、鍵委譲装置400は、プログラムを実行するCPU911(Central・Processing・Unit、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう)を備えている。CPU911は、バス912を介してROM913、RAM914、LCD901(Liquid Crystal Display)、キーボード902(K/B)、通信ボード915、磁気ディスク装置920と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置920(固定ディスク装置)の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置920は、所定の固定ディスクインタフェースを介して接続される。
【0122】
ROM913、磁気ディスク装置920は、不揮発性メモリの一例である。RAM914は、揮発性メモリの一例である。ROM913とRAM914と磁気ディスク装置920とは、記憶装置(メモリ)の一例である。また、キーボード902、通信ボード915は、入力装置の一例である。また、通信ボード915は、通信装置(ネットワークインタフェース)の一例である。さらに、LCD901は、表示装置の一例である。
【0123】
磁気ディスク装置920又はROM913などには、オペレーティングシステム921(OS)、ウィンドウシステム922、プログラム群923、ファイル群924が記憶されている。プログラム群923のプログラムは、CPU911、オペレーティングシステム921、ウィンドウシステム922により実行される。
【0124】
プログラム群923には、上記の説明において「マスター鍵生成部110」、「マスター鍵記憶部120」、「鍵ベクトル生成部130」、「ランダム化ベクトル生成部140」、「鍵生成用ベクトル生成部150」、「鍵配布部160」、「送信情報設定部210」、「暗号ベクトル生成部220」、「暗号情報生成部230」、「データ送信部240」、「公開鍵取得部250」、「セッション鍵生成部260」、「ベクトル入力部310」、「鍵ベクトル記憶部320」、「ペアリング演算部330」、「鍵ベクトル取得部410」、「鍵ベクトル生成部420」、「ランダム化ベクトル生成部430」、「鍵生成用ベクトル生成部440」、「鍵配布部450」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、CPU911により読み出され実行される。
ファイル群924には、上記の説明において「マスター公開鍵pk」、「マスター秘密鍵sk」、「暗号ベクトルc」、「鍵ベクトル」等の情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してCPU911によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのCPU911の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のCPU911の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【0125】
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、RAM914のメモリ、その他光ディスク等の記録媒体やICチップに記録される。また、データや信号は、バス912や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜回路」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ROM913に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ROM913等の記録媒体に記憶される。プログラムはCPU911により読み出され、CPU911により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
【符号の説明】
【0126】
10 暗号処理システム、100 鍵生成装置、110 マスター鍵生成部、120 マスター鍵記憶部、130 鍵ベクトル生成部、140 ランダム化ベクトル生成部、150 鍵生成用ベクトル生成部、160 鍵配布部、200 暗号化装置、210 送信情報設定部、220 暗号ベクトル生成部、230 暗号情報生成部、240 データ送信部、250 公開鍵取得部、260 セッション鍵生成部、300 復号装置、310 ベクトル入力部、320 鍵ベクトル記憶部、330 ペアリング演算部、400 鍵委譲装置、410 鍵ベクトル取得部、420 鍵ベクトル生成部、430 ランダム化ベクトル生成部、440 鍵生成用ベクトル生成部、450 鍵配布部。

【特許請求の範囲】
【請求項1】
数1に示すペアリング演算によって関連付けられた双対ベクトル空間である空間Vと空間Vとを用いて述語暗号処理を行う暗号処理システムであり、
前記空間Vにおける所定の基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)の基底ベクトルb(i=1,...,n)と、基底ベクトルb(i=n+1,...,N)のうちの2つ以上の基底ベクトルb(i=n+1,...,m)の和である基底ベクトルdn+1とを基底ベクトルとして有する基底B^におけるベクトルであって、基底ベクトルb(i=1,...,n)うちの少なくとも一部の基底ベクトルに対する係数として属性情報を埋め込むとともに、前記基底ベクトルdn+1に対する係数として所定の情報を埋め込んだベクトルを暗号ベクトルcとして処理装置により生成する暗号化装置と、
前記空間Vの基底Bにおけるベクトルであって、基底Bを構成する基底ベクトルb(i=1,...,n,...,N)の基底ベクトルb(i=1,...,n)うちの少なくとも一部の基底ベクトルに対する係数として述語情報を埋め込むとともに、前記基底Bの基底ベクトルb(i=n+1,...,m)に対する係数の和が1になるように、前記基底ベクトルb(i=n+1,...,m)に対する係数を埋め込んだベクトルを鍵ベクトルkL,decとして、前記暗号化装置が生成した暗号ベクトルcと前記鍵ベクトルkL,decとについて、処理装置により数1に示すペアリング演算e(c,kL,dec)を行い前記暗号ベクトルcを復号して前記所定の情報に関する値を抽出する復号装置と
を備えることを特徴とする暗号処理システム。
【数1】

【請求項2】
前記暗号処理システムは、さらに、
前記基底Bを構成する基底ベクトルb(i=1,...,N)のうち、基底ベクトルb(i=0,...,n)の少なくとも一部の基底ベクトルに対する係数として述語情報を設定するとともに、基底ベクトルb(i=n+1,...,m)に対する係数の和が1になるように、b(i=n+1,...,m)に対する係数を設定したベクトルを鍵ベクトルkL,decとして処理装置により生成する鍵生成装置を備え、
前記復号装置は、前記鍵生成装置が生成した鍵ベクトルkL,decを取得して、取得した鍵ベクトルkL,decと暗号ベクトルcとについて前記ペアリング演算を行う
ことを特徴とする請求項1に記載の暗号処理システム。
【請求項3】
前記暗号処理システムは、さらに、
前記鍵生成装置が生成した鍵ベクトルkL,decが復号可能な暗号ベクトルのうちの一部の暗号ベクトルを復号可能なベクトルであって、述語情報を設定した基底ベクトルに対する係数として一様に分布させた値を持つ乱数を設定したベクトルを鍵ベクトルkL+1,decとして生成する鍵委譲装置
を備えることを特徴とする請求項2に記載の暗号処理システム。
【請求項4】
述語暗号における秘密鍵である鍵ベクトルkL,decを生成する鍵生成装置であり、
ペアリング演算によって関連付けられた双対ベクトル空間である空間Vと空間Vとのうちの前記空間Vにおける所定の基底Bを記憶装置に記憶するマスター鍵記憶部と、
前記マスター鍵記憶部が記憶した前記基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)のうち、基底ベクトルb(i=1,...,n)の少なくとも一部の基底ベクトルb(i=1,...,μ)に対する係数として述語情報を設定するとともに、基底ベクトルb(i=n+1,...,N)うちの2つ以上の所定の基底ベクトルに対する係数の和が1になるように、前記所定の基底ベクトルに対する係数を設定したベクトルを鍵ベクトルkL,decとして処理装置により生成する鍵ベクトル生成部と
を備えることを特徴とする鍵生成装置。
【請求項5】
前記鍵ベクトル生成部は、数2に示す鍵ベクトルkL,decを生成する
ことを特徴とする請求項4に記載の鍵生成装置。
【数2】

【請求項6】
前記鍵ベクトル生成部は、数3に示す鍵ベクトルkL,decを生成する
ことを特徴とする請求項4に記載の鍵生成装置。
【数3】

【請求項7】
前記鍵生成装置は、さらに、
前記鍵ベクトル生成部が生成した鍵ベクトルkL,decで復号可能な暗号ベクトルのうちの一部の暗号ベクトルを復号可能な鍵ベクトルkL+1,decを生成するためのベクトルであって、少なくともj=μ+1,...,nの各jについて、基底ベクトルbに対する係数として所定の値が設定された少なくともn−μ個のベクトルを鍵生成用ベクトルkL,del,jとして処理装置により生成する鍵生成用ベクトル生成部と、
前記鍵生成用ベクトル生成部が生成した鍵生成用ベクトルkL,del,jで生成される鍵ベクトルkL+1,decのうち、述語情報が設定される基底ベクトルの係数に一様に分布した値を設定するためのベクトルであって、少なくともj=1,...,L+1の各jについて、基底ベクトルbに対する係数として所定の値が設定された少なくともL+1個のベクトルをランダム化ベクトルkL,ran,jとして処理装置により生成するランダム化ベクトル生成部と
を備えることを特徴とする請求項4に記載の鍵生成装置。
【請求項8】
前記鍵ベクトル生成部は、数4に示す鍵生成用ベクトルkL,del,jを生成し、
前記ランダム化ベクトル生成部は、数5に示すランダム化ベクトルkL,ran,jを生成する
ことを特徴とする請求項7に記載の鍵生成装置。
【数4】

【数5】

【請求項9】
前記鍵ベクトル生成部は、数6に示す鍵生成用ベクトルkL,del,jを生成し、
前記ランダム化ベクトル生成部は、数7に示すランダム化ベクトルkL,ran,jを生成する
ことを特徴とする請求項7に記載の鍵生成装置。
【数6】

【数7】

【請求項10】
述語暗号における秘密鍵である鍵ベクトルkL,decで復号可能な暗号ベクトルのうちの一部の暗号ベクトルを復号可能な鍵ベクトルkL+1,decを生成する鍵委譲装置であり、
ペアリング演算によって関連付けられた双対ベクトル空間である空間Vと空間Vとのうちの前記空間Vにおける所定の基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)のうち、基底ベクトルb(i=1,...,n)の少なくとも一部の基底ベクトルb(i=1,...,μ)に対する係数として述語情報が設定されるとともに、基底ベクトルb(i=n+1,...,N)のうちの2つ以上の所定の基底ベクトルに対する係数の和が1になるように、前記所定の基底ベクトルに対する係数が設定された鍵ベクトルkL,decを取得する鍵ベクトル取得部と、
少なくともj=μ+1,...,nの各jについて、基底ベクトルbに対する係数として所定の値が設定された少なくともn−μ個の鍵生成用ベクトルkL,del,jを取得する鍵生成用ベクトル取得部と、
前記鍵生成用ベクトル取得部が取得した前記鍵生成用ベクトルkL,del,jの少なくとも一部の前記鍵生成用ベクトルkL,del,jの各基底ベクトルの係数を述語情報倍し、前記鍵ベクトル取得部が取得した前記鍵ベクトルkL,decに加算して鍵ベクトルkL+1,decを生成する鍵ベクトル生成部と
を備えることを特徴とする鍵委譲装置。
【請求項11】
前記鍵委譲装置は、さらに、
少なくともj=1,...,L+1の各jについて、基底ベクトルbに対する係数として所定の値が設定された少なくともL+1個のランダム化ベクトルkL,ran,jを取得するランダム化ベクトル取得部を備え、
前記鍵ベクトル生成部は、前記ランダム化ベクトル取得部が取得した前記ランダム化ベクトルkL,ran,jの少なくとも一部の前記ランダム化ベクトルkL,ran,jの各基底ベクトルの係数を乱数倍し、前記鍵ベクトルkL+1,decにさらに加算して鍵ベクトルkL+1,decを生成する
ことを特徴とする請求項10に記載の鍵委譲装置。
【請求項12】
前記鍵ベクトル取得部は、数8に示す鍵ベクトルkL,decを取得し、
前記鍵生成用ベクトル取得部は、数9に示す鍵生成用ベクトルkL,del,jを取得し、
前記ランダム化ベクトル取得部は、数10に示すランダム化ベクトルkL,ran,jを取得し、
前記鍵ベクトル生成部は、数11に示す鍵ベクトルkL+1,decを生成する
ことを特徴とする請求項11に記載の鍵委譲装置。
【数8】

【数9】

【数10】

【数11】

【請求項13】
前記鍵ベクトル取得部は、数12に示す鍵ベクトルkL,decを取得し、
前記鍵生成用ベクトル取得部は、数13に示す鍵生成用ベクトルkL,del,jを取得し、
前記ランダム化ベクトル取得部は、数14に示すランダム化ベクトルkL,ran,jを取得し、
前記鍵ベクトル生成部は、数15に示す鍵ベクトルkL+1,decを生成する
ことを特徴とする請求項11に記載の鍵委譲装置。
【数12】

【数13】

【数14】

【数15】

【請求項14】
前記鍵委譲装置は、さらに、
前記鍵ベクトル生成部が生成した鍵ベクトルkL+1,decで復号可能な暗号ベクトルのうちの一部の暗号ベクトルを復号可能な鍵ベクトルkL+2,decを生成するためのベクトルであって、少なくともj=μL+1+1,...,nの各jについて、基底ベクトルbに対する係数として所定の値を設定した少なくともn−μL+1個のベクトルを鍵生成用ベクトルkL+1,del,jとして処理装置により生成する鍵生成用ベクトル生成部と、
前記鍵生成用ベクトル生成部が生成した鍵生成用ベクトルkL+1,del,jで生成される鍵ベクトルkL+2,decのうち、述語情報が設定される基底ベクトルの係数に一様に分布した値を設定するためのベクトルであって、少なくともj=1,...,L+2の各jについて、基底ベクトルbに対する係数として所定の値を設定した少なくともL+2個のベクトルをランダム化ベクトルkL+1,ran,jとして処理装置により生成するランダム化ベクトル生成部と
を備えることを特徴とする請求項11に記載の鍵委譲装置。
【請求項15】
前記鍵生成用ベクトル取得部は、数16に示す鍵生成用ベクトルkL,del,jを取得し、
前記ランダム化ベクトル取得部は、数17に示すランダム化ベクトルkL,ran,jを取得し、
前記鍵ベクトル生成部は、数18に示す鍵生成用ベクトルkL+1,del,jを生成し、
前記ランダム化ベクトル生成部は、数19に示すランダム化ベクトルkL+1,ran,jを生成する
ことを特徴とする請求項14に記載の鍵委譲装置。
【数16】

【数17】

【数18】

【数19】

【請求項16】
前記鍵生成用ベクトル取得部は、数20に示す鍵生成用ベクトルkL,del,jを取得し、
前記ランダム化ベクトル取得部は、数21に示すランダム化ベクトルkL,ran,jを取得し、
前記鍵ベクトル生成部は、数22に示す鍵生成用ベクトルkL+1,del,jを生成し、
前記ランダム化ベクトル生成部は、数23に示すランダム化ベクトルkL+1,ran,jを生成する
ことを特徴とする請求項14に記載の鍵委譲装置。
【数20】

【数21】

【数22】

【数23】

【請求項17】
述語暗号における暗号文である暗号ベクトルcを生成する暗号化装置であり、
ペアリング演算によって関連付けられた双対ベクトル空間である空間Vと空間Vとのうちの前記空間Vにおける所定の基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)の基底ベクトルb(i=1,...,n)と、基底ベクトルb(i=n+1,...,N)のうちの2つ以上の所定の基底ベクトルの和である基底ベクトルdn+1とを基底ベクトルとして有する基底B^を取得するとともに、所定の属性情報を取得する公開鍵取得部と、
前記公開鍵取得部が取得した基底B^におけるベクトルであって、前記基底ベクトルdn+1に対する係数として所定の情報を設定したベクトルを送信情報ベクトルζvとして処理装置により生成する送信情報設定部と、
前記基底B^の前記基底ベクトルb(i=1,...,n)のうちの少なくとも一部の基底ベクトルに対する係数として属性情報を設定した属性情報ベクトルを、前記送信情報設定部が生成した送信情報ベクトルζvに加算して暗号ベクトルcを処理装置により生成する暗号ベクトル生成部と
を備えることを特徴とする暗号化装置。
【請求項18】
前記送信情報設定部は、数24に示す送信情報ベクトルζvを生成し、
前記暗号ベクトル生成部は、数25に示す暗号ベクトルcを生成する
ことを特徴とする請求項17に記載の暗号化装置。
【数24】

【数25】

【請求項19】
前記送信情報設定部は、数26に示す送信情報ベクトルζvを生成し、
前記暗号ベクトル生成部は、数27に示す暗号ベクトルcを生成する
ことを特徴とする請求項17に記載の暗号化装置。
【数26】

【数27】

【請求項20】
前記暗号化装置は、さらに、
数28に示す暗号情報cを生成する暗号情報生成部
を備えることを特徴とする請求項17に記載の暗号化装置。
【数28】

【請求項21】
述語暗号における暗号文を復号する復号装置であり、
ペアリング演算によって関連付けられた双対ベクトル空間である空間Vと空間Vとのうちの前記空間Vにおける所定の基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)の基底ベクトルb(i=1,...,n)と、基底ベクトルb(i=n+1,...,N)のうちの2つ以上の所定の基底ベクトルの和である基底ベクトルdn+1とを有する基底B^におけるベクトルであって、基底ベクトルb(i=1,...,n)のうち少なくとも基底ベクトルb(i=1,...,μ)に対する係数として属性情報が設定されるとともに、前記基底ベクトルdn+1に対する係数として所定の情報が設定されたベクトルである暗号ベクトルcを入力するベクトル入力部と、
前記空間Vにおける所定の基底Bの基底ベクトルb(i=1,...,n,...,N)のうち、基底ベクトルb(i=1,...,n)の少なくとも基底ベクトルb(i=1,...,μ)(μ≦μ)に対する係数として述語情報v(i=1,...,μ)が設定されるとともに、前記基底ベクトルdn+1を構成する基底ベクトルbに対応する基底ベクトルbに対する係数の和が1になるように、前記所定の基底ベクトルに対する係数が設定された鍵ベクトルkL,decを記憶装置に記憶する鍵ベクトル記憶部と、
前記ベクトル入力部が入力した暗号ベクトルcと、前記鍵ベクトル記憶部が記憶した鍵ベクトルkL,decとについて処理装置により前記ペアリング演算を行い、前記暗号ベクトルcから前記所定の情報に関する値を抽出するペアリング演算部と
を備えることを特徴とする復号装置。
【請求項22】
前記ベクトル入力部は、数29に示す暗号ベクトルcを入力し、
前記鍵ベクトル記憶部は、数30に示す鍵ベクトルkL,decを記憶し、
前記ペアリング演算部は、数31に示すペアリング演算を行い、前記暗号ベクトルから前記所定の情報に関する値を抽出する
ことを特徴とする請求項21に記載の復号装置。
【数29】

【数30】

【数31】

【請求項23】
前記ベクトル入力部は、数32に示す暗号ベクトルcを入力し、
前記鍵ベクトル記憶部は、数33に示す鍵ベクトルkL,decを記憶し、
前記ペアリング演算部は、数34に示すペアリング演算を行い、前記暗号ベクトルから前記所定の情報に関する値を抽出する
ことを特徴とする請求項21に記載の復号装置。
【数32】

【数33】

【数34】

【請求項24】
前記ベクトル入力部は、数35に示す暗号ベクトルcと、平文情報mを暗号化した数36に示す暗号情報cとを入力し、
前記鍵ベクトル記憶部は、数37に示す鍵ベクトルkL,decを記憶し、
前記ペアリング演算部は、数38に示す演算を行い、前記暗号ベクトルcから前記平文情報mを抽出する
ことを特徴とする請求項21に記載の復号装置。
【数35】

【数36】

【数37】

【数38】

【請求項25】
前記ベクトル入力部は、数39に示す暗号ベクトルcと、平文情報mを暗号化した数40に示す暗号情報cとを入力し、
前記鍵ベクトル記憶部は、数41に示す鍵ベクトルkL,decを記憶し、
前記ペアリング演算部は、数42に示す演算を行い、前記暗号ベクトルcから前記平文情報mを抽出する
ことを特徴とする請求項21に記載の復号装置。
【数39】

【数40】

【数41】

【数42】

【請求項26】
数43に示すペアリング演算によって関連付けられた双対加群である空間Vと空間Vとを用いて述語暗号処理を行う暗号処理システムであり、
前記空間Vにおける所定の基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)の基底ベクトルb(i=1,...,n)と、基底ベクトルb(i=n+1,...,N)のうちの2つ以上の基底ベクトルb(i=n+1,...,m)の和である基底ベクトルdn+1とを基底ベクトルとして有する基底B^におけるベクトルであって、基底ベクトルb(i=1,...,n)うちの少なくとも一部の基底ベクトルに対する係数として属性情報を埋め込むとともに、前記基底ベクトルdn+1に対する係数として所定の情報を埋め込んだベクトルを暗号ベクトルcとして処理装置により生成する暗号化装置と、
前記空間Vの基底Bにおけるベクトルであって、基底Bを構成する基底ベクトルb(i=1,...,n,...,N)の基底ベクトルb(i=1,...,n)うちの少なくとも一部の基底ベクトルに対する係数として述語情報を埋め込むとともに、前記基底Bの基底ベクトルb(i=n+1,...,m)に対する係数の和が1になるように、前記基底ベクトルb(i=n+1,...,m)に対する係数を埋め込んだベクトルを鍵ベクトルkL,decとして、前記暗号化装置が生成した暗号ベクトルcと前記鍵ベクトルkL,decとについて、処理装置により数43に示すペアリング演算e(c,kL,dec)を行い前記暗号ベクトルcを復号して前記所定の情報に関する値を抽出する復号装置と
を備えることを特徴とする暗号処理システム。
【数43】

【請求項27】
述語暗号における秘密鍵である鍵ベクトルkL,decを生成する鍵生成装置であり、
ペアリング演算によって関連付けられた双対加群である空間Vと空間Vとのうちの前記空間Vにおける所定の基底Bを記憶装置に記憶するマスター鍵記憶部と、
前記マスター鍵記憶部が記憶した前記基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)のうち、基底ベクトルb(i=1,...,n)の少なくとも一部の基底ベクトルに対する係数として述語情報を設定するとともに、基底ベクトルb(i=n+1,...,N)うちの2つ以上の所定の基底ベクトルに対する係数の和が1になるように、前記所定の基底ベクトルに対する係数を設定したベクトルを鍵ベクトルkL,decとして処理装置により生成する鍵ベクトル生成部と
を備えることを特徴とする鍵生成装置。
【請求項28】
述語暗号における秘密鍵である鍵ベクトルkL,decで復号可能な暗号ベクトルのうちの一部の暗号ベクトルを復号可能な鍵ベクトルkL+1,decを生成する鍵委譲装置であり、
ペアリング演算によって関連付けられた双対加群である空間Vと空間Vとのうちの前記空間Vにおける所定の基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)のうち、基底ベクトルb(i=1,...,n)の少なくとも一部の基底ベクトルb(i=1,...,μ)に対する係数として述語情報が設定されるとともに、基底ベクトルb(i=n+1,...,N)のうちの2つ以上の所定の基底ベクトルに対する係数の和が1になるように、前記所定の基底ベクトルに対する係数が設定された鍵ベクトルkL,decを取得する鍵ベクトル取得部と、
少なくともj=μ+1,...,nの各jについて、基底ベクトルbに対する係数として所定の値が設定された少なくともn−(μ+1)個の鍵生成用ベクトルkL,del,jを取得する鍵生成用ベクトル取得部と、
前記鍵生成用ベクトル取得部が取得した前記鍵生成用ベクトルkL,del,jの少なくとも一部の前記鍵生成用ベクトルkL,del,jの各基底ベクトルの係数を述語情報倍し、前記鍵ベクトル取得部が取得した前記鍵ベクトルkL,decに加算して鍵ベクトルkL+1,decを生成する鍵ベクトル生成部と
を備えることを特徴とする鍵委譲装置。
【請求項29】
ペアリング演算によって関連付けられた双対加群である空間Vと空間Vとのうちの前記空間Vにおける所定の基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)の基底ベクトルb(i=1,...,n)と、基底ベクトルb(i=n+1,...,N)のうちの2つ以上の所定の基底ベクトルの和である基底ベクトルdn+1とを基底ベクトルとして有する基底B^を取得するとともに、所定の属性情報を取得する公開鍵取得部と、
前記公開鍵取得部が取得した基底B^におけるベクトルであって、前記基底ベクトルdn+1に対する係数として所定の情報を設定したベクトルを送信情報ベクトルζvとして処理装置により生成する送信情報設定部と、
前記基底B^の前記基底ベクトルb(i=1,...,n)のうちの少なくとも一部の基底ベクトルに対する係数として属性情報を設定した属性情報ベクトルを、前記送信情報設定部が生成した送信情報ベクトルに加算して暗号ベクトルcを処理装置により生成する暗号ベクトル生成部と
を備えることを特徴とする暗号化装置。
【請求項30】
ペアリング演算によって関連付けられた双対加群である空間Vと空間Vとのうちの前記空間Vにおける所定の基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)の基底ベクトルb(i=1,...,n)と、基底ベクトルb(i=n+1,...,N)のうちの2つ以上の所定の基底ベクトルの和である基底ベクトルdn+1とを有する基底B^におけるベクトルであって、基底ベクトルb(i=1,...,n)の少なくとも基底ベクトルb(i=1,...,μ)に対する係数として属性情報が設定されるとともに、前記基底ベクトルdn+1に対する係数として所定の情報が設定されたベクトルである暗号ベクトルcを入力するベクトル入力部と、
前記空間Vにおける所定の基底Bの基底ベクトルb(i=1,...,n,...,N)のうち、基底ベクトルb(i=1,...,n)の少なくとも基底ベクトルb(i=1,...,μ)(μ≦μ)に対する係数として述語情報v(i=1,...,μ)が設定されるとともに、前記基底ベクトルdn+1を構成する基底ベクトルbに対応する基底ベクトルbに対する係数の和が1になるように、前記所定の基底ベクトルに対する係数が設定された鍵ベクトルkL,decを記憶装置に記憶する鍵ベクトル記憶部と、
前記ベクトル入力部が入力した暗号ベクトルcと、前記鍵ベクトル記憶部が記憶した鍵ベクトルkL,decとについて処理装置により前記ペアリング演算を行い、前記暗号ベクトルcから前記所定の情報に関する値を抽出するペアリング演算部と
を備えることを特徴とする復号装置。
【請求項31】
数44に示すペアリング演算によって関連付けられた双対ベクトル空間である空間Vと空間Vとを用いて述語暗号処理を行う暗号処理方法であり、
処理装置が、前記空間Vにおける所定の基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)の基底ベクトルb(i=1,...,n)と、基底ベクトルb(i=n+1,...,N)のうちの2つ以上の基底ベクトルb(i=n+1,...,m)の和である基底ベクトルdn+1とを基底ベクトルとして有する基底B^におけるベクトルであって、基底ベクトルb(i=1,...,n)うちの少なくとも一部の基底ベクトルに対する係数として属性情報を埋め込むとともに、前記基底ベクトルdn+1に対する係数として所定の情報を埋め込んだベクトルを暗号ベクトルcとして生成する暗号化ステップと、
処理装置が、前記空間Vの基底Bにおけるベクトルであって、基底Bを構成する基底ベクトルb(i=1,...,n,...,N)の基底ベクトルb(i=1,...,n)うちの少なくとも一部の基底ベクトルに対する係数として述語情報を埋め込むとともに、前記基底Bの基底ベクトルb(i=n+1,...,m)に対する係数の和が1になるように、前記基底ベクトルb(i=n+1,...,m)に対する係数を埋め込んだベクトルを鍵ベクトルkL,decとして、前記暗号化ステップで生成した暗号ベクトルcと前記鍵ベクトルkL,decとについて、数44に示すペアリング演算e(c,kL,dec)を行い前記暗号ベクトルcを復号して前記所定の情報に関する値を抽出する復号ステップと
を備えることを特徴とする暗号処理方法。
【数44】

【請求項32】
数45に示すペアリング演算によって関連付けられた双対ベクトル空間である空間Vと空間Vとを用いて述語暗号処理を行う暗号処理プログラムであり、
前記空間Vにおける所定の基底Bを構成する基底ベクトルb(i=1,...,n,...,N)(Nは3以上の整数,nは1以上N−2以下の整数)の基底ベクトルb(i=1,...,n)と、基底ベクトルb(i=n+1,...,N)のうちの2つ以上の基底ベクトルb(i=n+1,...,m)の和である基底ベクトルdn+1とを基底ベクトルとして有する基底B^におけるベクトルであって、基底ベクトルb(i=1,...,n)うちの少なくとも一部の基底ベクトルに対する係数として属性情報を埋め込むとともに、前記基底ベクトルdn+1に対する係数として所定の情報を埋め込んだベクトルを暗号ベクトルcとして生成する暗号化処理と、
前記空間Vの基底Bにおけるベクトルであって、基底Bを構成する基底ベクトルb(i=1,...,n,...,N)の基底ベクトルb(i=1,...,n)うちの少なくとも一部の基底ベクトルに対する係数として述語情報を埋め込むとともに、前記基底Bの基底ベクトルb(i=n+1,...,m)に対する係数の和が1になるように、前記基底ベクトルb(i=n+1,...,m)に対する係数を埋め込んだベクトルを鍵ベクトルkL,decとして、前記暗号化処理で生成した暗号ベクトルcと前記鍵ベクトルkL,decとについて、により数45に示すペアリング演算e(c,kL,dec)を行い前記暗号ベクトルcを復号して前記所定の情報に関する値を抽出する復号処理と
をコンピュータに実行させることを特徴とする暗号処理プログラム。
【数45】


【図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


【公開番号】特開2011−128609(P2011−128609A)
【公開日】平成23年6月30日(2011.6.30)
【国際特許分類】
【出願番号】特願2010−258447(P2010−258447)
【出願日】平成22年11月19日(2010.11.19)
【出願人】(000006013)三菱電機株式会社 (33,312)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】