説明

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

【課題】演算等の効率をよくした階層的内積述語暗号を提供することを目的とする。
【解決手段】暗号処理システム10は、鍵生成装置100と暗号化装置200と復号装置300とを備える。鍵生成装置100は、t=1,...,Lの各整数tについての基底Bの基底ベクトルに述語情報vを埋め込んだベクトルを復号鍵skとして生成する。暗号化装置200は、t=1,...,Lのうち少なくとも一部の整数tについての基底Bの基底ベクトルに属性情報xを埋め込んだベクトルを暗号化データctとして生成する。復号装置300は、鍵生成装置100が生成した復号鍵skと暗号化装置200が生成した暗号化データctとについてペアリング演算を行い、暗号化データctを復号する。

【発明の詳細な説明】
【技術分野】
【0001】
この発明は、階層的述語暗号(Hierarchical Predicate Encryption)に関するものである。
【背景技術】
【0002】
非特許文献21には、階層的内積述語暗号(Hierarchical Predicate Encryption for Inner Products)についての記載がある。また、非特許文献18には、関数型暗号(Functional Encryption)についての記載がある。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】Beimel, A., Secure schemes for secret sharing and key distribution. PhD Thesis, Israel Institute of Technology, Technion, Haifa, Israel, 1996.
【非特許文献2】Bethencourt, J., Sahai, A., Waters, B.: Ciphertext−policy attribute−based encryption. In:2007 IEEE Symposium on Security and Privacy, pp. 321・34. IEEE Press (2007)
【非特許文献3】Boneh, D., Boyen, X.: Efficient selective−ID secure identity based encryption without random oracles. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp.223・38. Springer Heidelberg (2004)
【非特許文献4】Boneh, D., Boyen, X.: Secure identity based encryption without random oracles. In:Franklin, M.K. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 443・59. Springer Heidelberg (2004)
【非特許文献5】Boneh, D., Boyen, X., Goh, E.: Hierarchical identity based encryption with constant size ciphertext. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 440・56. Springer Heidelberg (2005)
【非特許文献6】Boneh, D., Franklin, M.: Identity−based encryption from the Weil pairing. In: Kilian, J.(ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213・29. Springer Heidelberg (2001)
【非特許文献7】Boneh, D., Hamburg, M.: Generalized identity based and broadcast encryption scheme. In:Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 455・70. Springer Heidelberg (2008)
【非特許文献8】Boneh, D., Katz, J., Improved efficiency for CCA−secure cryptosystems built using identity based encryption. RSA−CT 2005, LNCS, Springer Verlag (2005)
【非特許文献9】Boneh, D., Waters, B.: Conjunctive, subset, and range queries on encrypted data. In:Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 535・54. Springer Heidelberg (2007)
【非特許文献10】Boyen, X., Waters, B.: Anonymous hierarchical identity−based encryption (without random oracles). In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 290・07. Springer Heidelberg (2006)
【非特許文献11】Canetti, R., Halevi S., Katz J.: Chosen−ciphertext security from identity−based encryption.EUROCRYPT 2004, LNCS, Springer−Verlag (2004)
【非特許文献12】Cocks, C.: An identity based encryption scheme based on quadratic residues. In: Honary,B. (ed.) IMA Int. Conf. LNCS, vol. 2260, pp. 360・63. Springer Heidelberg (2001)
【非特許文献13】Gentry, C.: Practical identity−based encryption without random oracles. In: Vaudenay, S.(ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 445・64. Springer Heidelberg (2006)
【非特許文献14】Gentry, C., Halevi, S.: Hierarchical identity−based encryption with polynomially many levels. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 437・56. Springer Heidelberg(2009)
【非特許文献15】Gentry, C., Silverberg, A.: Hierarchical ID−based cryptography. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 548・66. Springer Heidelberg (2002)
【非特許文献16】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・8, ACM (2006)
【非特許文献17】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・62. Springer Heidelberg (2008)
【非特許文献18】Lewko, A., Okamoto, T., Sahai, A., Takashima, K., Waters, B.: Fully secure functionalencryption: Attribute−based encryption and (hierarchical) inner product encryption, EUROCRYPT 2010. LNCS, Springer Heidelberg (2010)
【非特許文献19】Lewko, A.B., Waters, B.: New techniques for dual system encryption and fully secure HIBE with short ciphertexts. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 455・79. Springer Heidelberg (2010)
【非特許文献20】Okamoto, T., Takashima, K.: Homomorphic encryption and signatures from vector decomposition.In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp.57・4. Springer Heidelberg (2008)
【非特許文献21】Okamoto, T., Takashima, K.: Hierarchical predicate encryption for inner−products, In:ASIACRYPT 2009, Springer Heidelberg (2009)
【非特許文献22】Ostrovsky, R., Sahai, A., Waters, B.: Attribute−based encryption with non−monotonic access structures. In: ACM Conference on Computer and Communication Security 2007, pp. 195・03, ACM (2007)
【非特許文献23】Pirretti, M., Traynor, P., McDaniel, P., Waters, B.: Secure attribute−based systems. In:ACM Conference on Computer and Communication Security 2006, pp. 99・12, ACM, (2006)
【非特許文献24】Sahai, A., Waters, B.: Fuzzy identity−based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457・73. Springer Heidelberg (2005)
【非特許文献25】Shi, E., Waters, B.: Delegating capability in predicate encryption systems. In: Aceto, L.,Damg「ェard, I., Goldberg, L.A., Halldゥェrsson, M.M., Ingゥェlfsdゥェttir, A., Walukiewicz, I. (eds.)ICALP (2) 2008. LNCS, vol. 5126, pp. 560.578. Springer Heidelberg (2008)
【非特許文献26】Waters, B.: Efficient identity based encryption without random oracles. Eurocrypt 2005,LNCS, vol. 3152, pp.443・59. Springer Verlag, (2005)
【非特許文献27】Waters, B.: Ciphertext−policy attribute−based encryption: an expressive, efficient, and provably secure realization. ePrint, IACR, http://eprint.iacr.org/2008/290
【非特許文献28】Waters, B.: Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 619・36. Springer Heidelberg (2009)
【発明の概要】
【発明が解決しようとする課題】
【0004】
非特許文献21に記載された階層的内積述語暗号方式では、1つの大きな空間を使って暗号処理を構築していた。そのため、この階層的内積述語暗号方式を実装した場合、鍵のサイズが大きくなり、演算等の効率が悪くなる虞がある。
この発明は、演算等の効率をよくした階層的内積述語暗号を提供することを目的とする。
【課題を解決するための手段】
【0005】
この発明に係る暗号処理システムは、
t=1,...,L+1(Lは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を行う暗号処理システムであり、
t=1,...,Lのうち少なくとも一部の整数tについての基底Bの基底ベクトルに属性情報xを埋め込んだベクトルを暗号化データctとして生成する暗号化装置と、
t=1,...,Lの各整数tについての基底Bの基底ベクトルに述語情報vを埋め込んだベクトルを復号鍵skとして、前記暗号化装置が生成した暗号化データctと前記復号鍵skとについてペアリング演算を行い前記暗号化データctを復号する復号装置と、
基底BL+1の基底ベクトルに述語情報を埋め込んだベクトルと、前記復号装置が使用した復号鍵skとに基づき、前記復号鍵skの下位の復号鍵skL+1を生成する鍵委譲装置と
を備えることを特徴とする。
【発明の効果】
【0006】
この発明に係る暗号処理システムでは、複数の空間を用いて階層構造を構築している。そのため、鍵のサイズを小さくでき、演算効率がよくなる。
【図面の簡単な説明】
【0007】
【図1】「権限委譲(階層的な権限委譲)」という概念を説明するための図。
【図2】階層を飛ばした権限委譲を説明するための図。
【図3】属性情報と述語情報との階層構造を示す図。
【図4】階層的IDベース暗号の例を示す図。
【図5】基底と基底ベクトルとを説明するための図。
【図6】ベクトル空間における階層構造の実現方法の一例を説明するための図。
【図7】階層的内積述語暗号方式のアルゴリズムを実行する暗号処理システム10の構成図。
【図8】鍵生成装置100の機能を示す機能ブロック図。
【図9】暗号化装置200の機能を示す機能ブロック図。
【図10】復号装置300の機能を示す機能ブロック図。
【図11】鍵委譲装置400の機能を示す機能ブロック図。
【図12】Setupアルゴリズムの処理を示すフローチャート。
【図13】KeyGenアルゴリズムの処理を示すフローチャート。
【図14】Encアルゴリズムの処理を示すフローチャート。
【図15】Decアルゴリズムの処理を示すフローチャート。
【図16】Delegateアルゴリズムの処理を示すフローチャート。
【図17】KeyGenアルゴリズムの処理を示すフローチャート。
【図18】Decアルゴリズムの処理を示すフローチャート。
【図19】Delegateアルゴリズムの処理を示すフローチャート。
【図20】鍵生成装置100、暗号化装置200、復号装置300のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【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】

数105、つまりFは、位数qの有限体を示す。
【数105】

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

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

【数108】

【数109】

は、行列Xの転置行列を表す。
数110に示す基底Bと基底Bとに対して、数111である。
【数110】

【数111】

t,jは、数112に示す正規基底ベクトルを示す。
【数112】

また、数113から数117である。
【数113】

【数114】

【数115】

【数116】

【数117】

また、数118である場合に、数119である。
【数118】

【数119】

【0010】
また、以下の説明において、Fntにおけるntはnのことである。
同様に、秘密鍵sk(v→1,...,v→L)における(v→1,...,v→L)は(v,...,v)のことであり、秘密鍵sk(v→1,...,v→L+1)における(v→1,...,v→L+1)は(v,...,vL+1)のことである。
同様に、“δi,j”が上付きで示されている場合、このδi,jは、δi,jを意味する。
また、ベクトルを意味する“→”が下付き文字又は上付き文字に付されている場合、この“→”は下付き文字又は上付き文字に上付きで付されていることを意味する。
【0011】
また、以下の説明において、暗号処理とは、暗号化処理、復号処理、鍵生成処理、鍵委譲処理を含むものである。
【0012】
実施の形態1.
この実施の形態では、「階層的内積述語暗号」を実現する基礎となる概念と、「階層的内積述語暗号」の構成について説明する。
第1に、階層的内積述語暗号の概念について説明する。階層的内積述語暗号という概念を説明するに当たり、まず「権限委譲」という概念を説明する。また、併せて、「階層的(Hierarchial)な権限委譲」という概念を説明する。次に、「内積述語暗号」を説明する。そして、階層的な権限委譲という概念を内積述語暗号に加えた「階層的内積述語暗号」を説明する。さらに、階層的内積述語暗号の理解を深めるため、階層的内積述語暗号の応用例を説明する。
第2に、ベクトル空間における階層的内積述語暗号を説明する。この実施の形態及び以下の実施の形態では、階層的述語暗号と階層的述語鍵秘匿方式とをベクトル空間において実現する。ここでは、まず、「基底」と「基底ベクトル」について説明する。次に、「ベクトル空間における内積述語暗号」について説明する。そして、「ベクトル空間における階層構造の実現方法」について説明する。さらに、理解を深めるため、階層構造の実現例を説明する。
第3に、階層的内積述語暗号を実現するための空間である「双対ペアリングベクトル空間(Dual Pairing Vector Spaces,DPVS)」という豊かな数学的構造を有する空間を説明する。
第4に、この実施の形態に係る「階層的内積述語暗号方式」の基本構成を説明する。次に、階層的述語暗号を実行する「暗号処理システム10」の基本構成を説明する。そして、この実施の形態に係る階層的述語暗号方式及び暗号処理システム10について詳細に説明する。
【0013】
<第1.階層的内積述語暗号>
<第1−1.権限委譲(階層的な権限委譲)という概念>
図1は、「権限委譲(階層的な権限委譲)」という概念を説明するための図である。
権限委譲とは、上位の鍵を有する利用者が、その鍵(上位の鍵)よりも機能が制限された下位の鍵を生成することである。
図1では、Root(鍵生成装置)は、マスター秘密鍵を用いて、第1層目(Level−1)の利用者へ秘密鍵を生成する。つまり、Rootは、第1層目の利用者1,2,3それぞれへ鍵1,2,3を生成する。そして、例えば、利用者1であれば、鍵1を用いて、利用者1の下位(第2層目)の利用者である利用者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に示すように、階層的に下位の鍵を生成することを「階層的な権限委譲」と呼ぶ。
【0014】
なお、図1では、Rootが第1層目の利用者へ秘密鍵を生成し、第1層目の利用者が第2層目の利用者へ秘密鍵を生成し、第2層目の利用者が第3層目の利用者へ秘密鍵を生成すると説明した。しかし、図2に示すように、Rootは、第1層目の利用者へ秘密鍵を生成するだけでなく、第2層目以下の層の利用者へ秘密鍵を生成することもできる。同様に、第1層目の利用者は、第2層目の利用者へ秘密鍵を生成するだけでなく、第3層目以下の層の利用者へ秘密鍵を生成することもできる。つまり、Rootや利用者は、自分が持つ秘密鍵よりも下位の層の秘密鍵を生成することができる。
【0015】
<第1−2.内積述語暗号>
次に、「内積述語暗号」について説明する。
まず、述語暗号とは、述語情報fに属性情報xを入力した場合に1(True)となる場合(f(x)=1となる場合)に、暗号文を復号できる暗号方式である。通常、暗号文に属性情報xが埋め込まれ、秘密鍵に述語情報fが埋め込まれる。つまり、述語暗号では、属性情報xに基づき暗号化された暗号文cを、述語情報fに基づき生成された秘密鍵SKにより復号する。述語暗号は、例えば、述語情報fが条件式であり、属性情報xがその条件式への入力情報であり、入力情報(属性情報x)が条件式(述語情報f)を満たせば(f(x)=1)、暗号文を復号できる暗号方式であるとも言える。
なお、述語暗号について詳しくは非特許文献17に記載されている。
【0016】
内積述語暗号とは、属性情報xと述語情報fとの内積が所定の値の場合に、f(x)=1となる述語暗号である。つまり、属性情報xと述語情報fとの内積が所定の値の場合にのみ、属性情報xにより暗号化された暗号文cを、述語情報fに基づき生成された秘密鍵SKにより復号することができる。
実施の形態1では、原則として、属性情報xと述語情報fとの内積が0の場合に、f(x)=1となるものとする。
【0017】
<第1−3.階層的内積述語暗号>
階層的内積述語暗号(階層的内積述語鍵秘匿方式)とは、上述した「階層的な権限委譲」という概念を有する「内積述語暗号」である。
【0018】
階層的内積述語暗号は、内積述語暗号に階層的な権限委譲システムを持たせるため、属性情報と述語情報とに階層構造を持たせる。
図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とならない。
【0019】
<第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で暗号化された暗号文を復号することができる。
【0020】
階層的内積述語暗号は、IDベース暗号以外へも様々な応用が可能である。特に、以下に説明する暗号処理は、等号関係テストのクラスに限定されたものではないため、非常に多くの応用が可能である。例えば、内積述語暗号の一種である検索可能暗号等についても、階層毎に検索可能な範囲をAND条件やOR条件等の条件式を用いて限定する等、従来の権限委譲システムを有する述語暗号では実現できなかった応用が可能である。
つまり、後の実施の形態で説明する階層的述語鍵秘匿方式と階層的述語暗号とは、IDベース暗号や検索可能暗号等へ幅広い応用が可能である。
【0021】
<第2.ベクトル空間における階層的内積述語暗号>
階層的述語鍵秘匿方式と階層的述語暗号とは、後述する双対ペアリングベクトル空間という高次元ベクトル空間において実現される。そこで、ベクトル空間における階層的内積述語暗号を説明する。
【0022】
<第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個である。
【0023】
<第2−2.ベクトル空間における内積述語暗号>
次に、ベクトル空間における内積述語暗号を説明する。
上記の通り、内積述語暗号とは、属性情報xと述語情報fとの内積が所定の値(ここでは、0)の場合に、f(x)=1となる述語暗号である。属性情報xと述語情報fとがベクトルであった場合、つまり属性ベクトルxと述語ベクトルvとであった場合、内積述語は数120のように定義される。
【数120】

つまり、属性ベクトルxと述語ベクトルvとの内積、つまり要素毎の内積の和が0である場合に、述語情報fに属性情報xを入力した結果が1(True)となる。また、属性ベクトルxと述語ベクトルvとの内積が0でない場合に、述語情報fに属性情報xを入力した結果が0(False)となる述語暗号である。
【0024】
<第2−3.ベクトル空間における階層構造の実現方法>
次に、ベクトル空間における階層構造の実現方法を説明する。
図6は、ベクトル空間における階層構造の実現方法の一例を説明するための図である。
ここではd個(dは1以上の整数)のベクトル空間を扱う。各ベクトル空間は、高次元(N次元(t=1,...,d))ベクトル空間である。つまり、各ベクトル空間における所定の基底C(t=1,...,d)には、基底ベクトルc(i=1,...,N)のN個の基底ベクトルが存在する。
そして、基底Cを第1層目の属性情報や述語情報を設定するための空間とする。また、基底Cを第2層目の属性情報や述語情報を設定するための空間とする。以下同様に、基底Cを第L層目の属性情報や述語情報を設定するための空間とする。したがって、ここでは、d層の階層を表すことができる。
ここで、第L層目の秘密鍵は、基底Cを用いて第L層目の述語情報を設定するだけでなく、基底Cから基底CL−1を用いて第1層目から第L−1層目の述語情報を設定して生成される。つまり、下位の層の秘密鍵には、上位の層の秘密鍵に設定される述語情報も設定される。これにより、述語情報に階層構造を持たせる。そして、この述語情報に持たせた階層構造を利用して、内積述語暗号における権限委譲システムを構成する。
【0025】
なお、以下の説明においては、ベクトル空間における階層的構造を示すために、階層情報n:=(d;N,...,N)を用いる。ここで、dは、上述した階層の深さを表す値である。N(i=1,...,d)は、各層iに割り当てられた空間の次元数、つまり基底ベクトルの数を表す値である。
【0026】
<第2−4.階層構造の実現例>
ここで、簡単な例を用いて階層構造を説明する。ここでは、3つの階層を備え、各階層に割り当てられた空間が2次元で構成された例を用いて説明する。つまり、n:=(d;N,...,N)=(3;2,2,2)である。
第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.双対ペアリングベクトル空間>
まず、対称双線形ペアリング群(Symmetric Bilinear Pairing Groups)について説明する。
対称双線形ペアリング群(q,G,G,g,e)は、素数qと、位数qの巡回加法群Gと、位数qの巡回乗法群Gと、g≠0∈Gと、多項式時間で計算可能な非退化双線形ペアリング(Nondegenerate Bilinear Pairing)e:G×G→Gとの組である。非退化双線形ペアリングは、e(sg,tg)=e(g,g)stであり、e(g,g)≠1である。
以下の説明において、数121を、1λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータparam:=(q,G,G,g,e)の値を出力するアルゴリズムとする。
【数121】

【0028】
次に、双対ペアリングベクトル空間について説明する。
双対ペアリングベクトル空間(q,V,G,A,e)は、対称双線形ペアリング群(param:=(q,G,G,g,e))の直積によって構成することができる。双対ペアリングベクトル空間(q,V,G,A,e)は、素数q、数122に示すF上のN次元ベクトル空間V、位数qの巡回群G、空間Vの標準基底A:=(a,...,a)の組であり、以下の演算(1)(2)を有する。ここで、aは、数123に示す通りである。
【数122】

【数123】

【0029】
演算(1):非退化双線形ペアリング
空間Vにおけるペアリングは、数124によって定義される。
【数124】

これは、非退化双線形である。つまり、e(sx,ty)=e(x,y)stであり、全てのy∈Vに対して、e(x,y)=1の場合、x=0である。また、全てのiとjとに対して、e(a,a)=e(g,g)δi,jである。ここで、i=jであれば、δi,j=1であり、i≠jであれば、δi,j=0である。また、e(g,g)≠1∈Gである。
【0030】
演算(2):ディストーション写像
数125に示す空間Vにおける線形変換φi,jは、数126を行うことができる。
【数125】

【数126】

ここで、線形変換φi,jをディストーション写像と呼ぶ。
【0031】
以下の説明において、数127を、1λ(λ∈自然数)、N∈自然数、双線形ペアリング群のパラメータparam:=(q,G,G,g,e)の値を入力として、セキュリティパラメータがλであり、N次元の空間Vとする双対ペアリングベクトル空間のパラメータparam:=(q,V,G,A,e)の値を出力するアルゴリズムとする。
【数127】

【0032】
なお、ここでは、上述した対称双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。なお、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。
【0033】
<第4.階層的述語暗号の構成と暗号処理システム10>
<第4−1.階層的内積述語暗号の基本構成>
階層的内積述語暗号方式の構成を簡単に説明する。
階層的内積述語暗号方式は、Setup、KeyGen、Enc、Dec、Delegate(L=1,...,d−1)の5つの確率的多項式時間アルゴリズムを備える。
(Setup)
Setupアルゴリズムでは、セキュリティパラメータ1λと階層情報n:=(d;N,...,N)とが入力され、マスター公開鍵pkとマスター秘密鍵skとが出力される。マスター秘密鍵skは最も上位の鍵である。
(KeyGen)
KeyGenアルゴリズムでは、マスター公開鍵pkとマスター秘密鍵skと述語ベクトル(v,...,v)(1≦L≦d)が入力され、第L層目の秘密鍵sk(v→1,...,v→L)が出力される。
(Enc)
Encアルゴリズムでは、マスター公開鍵pkと属性ベクトル(x,...,x)(1≦h≦d)と平文情報mとが入力され、暗号化データct(暗号文)が出力される。つまり、Encアルゴリズムでは、平文情報mを埋め込み、属性ベクトル(x,...,x)により暗号化された暗号化データctが出力される。
(Dec)
Decアルゴリズムでは、マスター公開鍵pkと第L層目の秘密鍵sk(v→1,...,v→L)と暗号化データctとが入力され、平文情報m又は識別情報⊥が出力される。識別情報⊥とは、復号に失敗したことを示す情報である。つまり、Decアルゴリズムでは、暗号化データctを第L層目の秘密鍵で復号して、平文情報mを抽出する。また、復号に失敗した場合には識別情報⊥を出力する。
(Delegate
Delegateでは、マスター公開鍵pkと第L層目の秘密鍵sk(v→1,...,v→L)と第L+1層目の述語ベクトルvL+1(L+1≦d)とが入力され、第L+1層目の秘密鍵sk(v→1,...,v→L+1)が出力される。つまり、Delegateアルゴリズムでは、下位の秘密鍵が出力される。
【0034】
<第4−2.暗号処理システム10>
階層的内積述語暗号方式のアルゴリズムを実行する暗号処理システム10について説明する。
図7は、階層的内積述語暗号方式のアルゴリズムを実行する暗号処理システム10の構成図である。
暗号処理システム10は、鍵生成装置100、暗号化装置200、復号装置300、鍵委譲装置400を備える。なお、ここでは、復号装置300が、鍵委譲装置400を備えるものとして説明するが、鍵委譲装置400は、復号装置300とは別に設けられていてもよい。
鍵生成装置100は、セキュリティパラメータλと、階層情報n:=(d;N,...,N)とを入力としてSetupアルゴリズムを実行して、マスター公開鍵pkとマスター秘密鍵skとを生成する。そして、鍵生成装置100は、生成したマスター公開鍵pkを公開する。また、鍵生成装置100は、マスター公開鍵pkとマスター秘密鍵skと述語ベクトル(v,...,v)(1≦L≦d)とを入力としてKeyGenアルゴリズムを実行して、第L層目の秘密鍵sk(v→1,...,v→L)を生成して第L層目の復号装置300へ秘密裡に配布する。
暗号化装置200は、マスター公開鍵pkと属性ベクトル(x,...,x)(1≦h≦d)と平文情報mとを入力としてEncアルゴリズムを実行して、暗号化データctを生成する。暗号化装置200は、生成した暗号化データctを復号装置300へ送信する。
復号装置300は、マスター公開鍵pkと第L層目の秘密鍵sk(v→1,...,v→L)と暗号化データctとを入力としてDecアルゴリズムを実行して、平文情報m又は識別情報⊥を出力する。
鍵委譲装置400は、スター公開鍵pkと第L層目の秘密鍵sk(v→1,...,v→L)と第L+1層目の述語ベクトルvL+1(L+1≦d)とを入力としてDelegateアルゴリズムを実行して、第L+1層目の秘密鍵sk(v→1,...,v→L+1)を生成して第L+1層目の復号装置300へ秘密裡に配布する。
【0035】
<第4−3.階層的内積述語暗号方式及び暗号処理システム10の詳細>
図8から図16に基づき、実施の形態1に係る階層的内積述語暗号方式、及び、階層的内積述語暗号方式を実行する暗号処理システム10の機能と動作とについて説明する。
図8は、鍵生成装置100の機能を示す機能ブロック図である。図9は、暗号化装置200の機能を示す機能ブロック図である。図10は、復号装置300の機能を示す機能ブロック図である。図11は、鍵委譲装置400の機能を示す機能ブロック図である。
図12と図13とは、鍵生成装置100の動作を示すフローチャートである。なお、図12はSetupアルゴリズムの処理を示すフローチャートであり、図13はKeyGenアルゴリズムの処理を示すフローチャートである。図14は、暗号化装置200の動作を示すフローチャートであり、Encアルゴリズムの処理を示すフローチャートである。図15は、復号装置300の動作を示すフローチャートであり、Decアルゴリズムの処理を示すフローチャートである。図16は、鍵委譲装置400の動作を示すフローチャートであり、Delegateアルゴリズムの処理を示すフローチャートである。
【0036】
なお、以下の説明において、添え字の「dec」は「decryption」の略であり、添え字に「dec」とあるものは、暗号化データの復号に用いられる復号要素である。また、添え字の「ran」は「randomization」の略であり、添え字に「ran」とあるものは、下位の復号鍵の所定の基底ベクトルに対する係数をランダム化するためのランダム化要素である。また、添え字の「del」は「delegation」の略であり、添え字に「del」とあるものは、下位の復号鍵を生成するための委譲要素である。
【0037】
鍵生成装置100の機能と動作とについて説明する。
図8に示すように、鍵生成装置100は、マスター鍵生成部110、マスター鍵記憶部120、情報入力部130(第1情報入力部)、復号鍵生成部140、鍵配布部150(復号鍵送信部)を備える。
また、復号鍵生成部140は、乱数生成部141、復号要素生成部142、ランダム化要素生成部143、委譲要素生成部144を備える。
【0038】
まず、図12に基づき、Setupアルゴリズムの処理について説明する。
(S101:正規直交基底生成ステップ)
マスター鍵生成部110は、処理装置により、数128を計算して、paramn→と、t=0,...,dの各整数tについて基底B及び基底Bとをランダムに生成する。
【数128】

【0039】
つまり、マスター鍵生成部110は以下の処理を実行する。
(1)マスター鍵生成部110は、入力装置により、セキュリティパラメータλ(1λ)と、属性のフォーマットn:=(d;n,...,n,u,...,u,w,...,w,z,...,z)とを入力する。ここで、dは1以上の整数である。t=1,...,dの各整数tについてnは1以上の整数である。t=0,...,dまでの各整数tについてu,w,zは1以上の整数である。また、マスター鍵生成部110は、N:=1+u+1+w+zとし、t=1,...,dの各整数tについてN:=n+u+w+zとする。
(2)マスター鍵生成部110は、処理装置により、(1)で入力したセキュリティパラメータλ(1λ)を入力としてアルゴリズムGbpgを実行して、ランダムに双線形ペアリング群のパラメータparam:=(q,G,G,g,e)の値を生成する。
(3)マスター鍵生成部110は、処理装置により、乱数ψを生成する。
【0040】
続いて、マスター鍵生成部110は、t=0,...,dの各整数tについて以下の(4)から(8)までの処理を実行する。
(4)マスター鍵生成部110は、処理装置により、(1)で入力したセキュリティパラメータλ(1λ)及びNと、(2)で生成したparam:=(q,G,G,g,e)の値とを入力としてアルゴリズムGdpvsを実行して、双対ペアリングベクトル空間のパラメータparamVt:=(q,V,G,A,e)の値を生成する。
(5)マスター鍵生成部110は、処理装置により、(3)で設定したNと、Fとを入力として、線形変換X:=(χt,i,ji,jをランダムに生成する。なお、GLは、General Linearの略である。つまり、GLは、一般線形群であり、行列式が0でない正方行列の集合であり、乗法に関し群である。また、(χt,i,ji,jは、行列χt,i,jの添え字i,jに関する行列という意味であり、ここでは、i,j=1,...,Nである。
(6)マスター鍵生成部110は、処理装置により、乱数ψと線形変換Xとに基づき、(νt,i,ji,j:=ψ・(X−1を生成する。なお、(νt,i,ji,jも(χt,i,ji,jと同様に、行列νt,i,jの添え字i,jに関する行列という意味であり、ここでは、i,j=1,...,Nである。
(7)マスター鍵生成部110は、処理装置により、(5)で生成した線形変換Xに基づき、(4)で生成した標準基底Aから基底Bを生成する。
(8)マスター鍵生成部110は、処理装置により、(6)で生成した(νt,i,ji,jに基づき、(4)で生成した標準基底Aから基底Bを生成する。
(9)マスター鍵生成部110は、処理装置により、gにe(g,g)ψを設定する。また、マスター鍵生成部110は、paramn→に(4)で生成した{paramVtt=0,...,dと、gとを設定する。なお、t=0,...,dとi=1,...,Nとの各整数t,iについて、g=e(bt,i,bt,i)である。
【0041】
すなわち、(S101)で、マスター鍵生成部110は、数129に示すアルゴリズムGobを実行して、paramn→と、t=0,...,dの各整数tについて基底B及び基底Bとを生成する。
【数129】

【0042】
(S102:マスター公開鍵生成ステップ)
マスター鍵生成部110は、処理装置により、基底Bの部分基底B^と、t=1,...,dの各整数tについて、基底Bの部分基底B^を数130に示すように生成する。
【数130】

マスター鍵生成部110は、生成した部分基底B^及び部分基底B^と、(S101)で入力されたセキュリティパラメータλ(1λ)と、(S101)で生成したparamn→と、基底ベクトルb0,1+u0+1+1,...,0,1+u0+1+w0(ここでu0、w0は、u,wのことである)と、t=1,...,dの各整数tについて基底ベクトルbt,nt+ut+1,...,bt,nt+ut+wt(ここでnt,ut,wtは、n,u,wのことである)とを合わせて、マスター公開鍵pkとする。
【0043】
(S103:マスター秘密鍵生成ステップ)
マスター鍵生成部110は、処理装置により、基底Bの部分基底B^と、t=1,...,dの各整数tについて、基底Bの部分基底B^を数131に示すように生成する。
【数131】

マスター鍵生成部110は、生成した部分基底B^及び部分基底B^とをマスター秘密鍵とする。
【0044】
(S104:マスター鍵記憶ステップ)
マスター鍵記憶部120は、(S102)で生成したマスター公開鍵pkを記憶装置に記憶する。また、マスター鍵記憶部120は、(S103)で生成したマスター秘密鍵skを記憶装置に記憶する。
【0045】
つまり、(S101)から(S103)において、鍵生成装置100は数132に示すSetupアルゴリズムを実行して、マスター公開鍵pkとマスター秘密鍵skとを生成する。そして、(S104)で、鍵生成装置100は生成された公開パラメータpkとマスター鍵skとを記憶装置に記憶する。
なお、マスター公開鍵pkは、例えば、ネットワークを介して公開され、復号装置300が取得可能な状態にされる。
【数132】

【0046】
次に、図13に基づき、鍵生成装置100が実行するKeyGenアルゴリズムの処理について説明する。
(S201:情報入力ステップ)
情報入力部130は、入力装置により、述語情報(v,...,v):=((v1,i(i=1,...,n)),...,(vL,i(i=1,...,n)))を入力する。なお、述語情報としては、鍵を使用する者の属性が入力される。
【0047】
(S202:乱数生成ステップ)
乱数生成部141は、処理装置により、j=1,...,2Lと,τ=L+1,...,dと,(τ,ι)=(τ,1),...,(τ,nτ)との各整数j,τ,ιについて、乱数ψと、乱数sdec,t,sran,j,t(t=1,...,L)と、乱数θdec,t,θran,j,t,ηdec,t,ηran,j,t(t=0,...,L)と、乱数sran,(τ,ι),t,sdel,(τ,ι),t(t=1,...,L+1)と、乱数θran,(τ,ι),t,θdel,(τ,ι),t,ηran,(τ,ι),t,ηdel,(τ,ι),t(t=0,...,L+1)とを数133に示すように生成する。
【数133】

また、数134に示すようにsdec,0と、sran,j,0と、sran,(τ,ι),0と、sdel,(τ,ι),0とを設定する。
【数134】

【0048】
(S203:復号要素生成ステップ)
復号要素生成部142は、処理装置により、復号鍵skの要素である復号要素kL,decを数135に示すように生成する。
【数135】

なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数135は、以下のように、基底B及び基底B(t=1,...,L)の基底ベクトルの係数が設定され、復号要素kL,decが生成されることを意味する。
まず、基底Bの部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。
基底Bの基底ベクトル1の係数として−sdec,0が設定される。基底ベクトル1+1,...,1+uの係数として0が設定される。基底ベクトル1+u+1の係数として1が設定される。基底ベクトル1+u+1+1,...,1+u+1+wの係数としてηdec,0,1,...,ηdec,0,wo(ここで、w0はwのことである)が設定される。基底ベクトル1+u+1+w+1,...,1+u+1+w+zの係数として0が設定される。
次に、基底B(t=1,...,L)の部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。
基底B(t=1,...,L)の基底ベクトル1の係数としてsdec,t+θdec,tt,1が設定される。基底ベクトル2,...,nの係数としてθdec,tt,2,...,θdec,tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηdec,t,1,...,ηdec,t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
【0049】
(S204:第1ランダム化要素生成ステップ)
ランダム化要素生成部143は、処理装置により、j=1,...,2Lの各整数jについて、復号鍵skの要素である第1ランダム化要素kL,ran,jを数136に示すように生成する。
【数136】

なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数136は、以下のように、基底B及び基底B(t=1,...,L)の基底ベクトルの係数が設定され、第1ランダム化要素kL,ran,jが生成されることを意味する。
まず、基底Bの部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。
基底Bの基底ベクトル1の係数として−sran,j,0が設定される。基底ベクトル1+1,...,1+u+1の係数として0が設定される。基底ベクトル1+u+1+1,...,1+u+1+wの係数としてηran,j,0,1,...,ηran,j,0,wo(ここで、w0はwのことである)が設定される。基底ベクトル1+u+1+w+1,...,1+u+1+w+zの係数として0が設定される。
次に、基底B(t=1,...,L)の部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。
基底B(t=1,...,L)の基底ベクトル1の係数としてsran,j,t+θran,j,tt,1が設定される。基底ベクトル2,...,nの係数としてθran,j,tt,2,...,θran,j,tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηran,j,t,1,...,ηran,j,t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
【0050】
(S205:第2ランダム化要素生成ステップ)
ランダム化要素生成部143は、処理装置により、τ=L+1,...,dの各整数τと、各整数τについてι=1,...,nτの各整数ιとについて、復号鍵skの要素である第2ランダム化要素kL,ran,(τ,ι)を数137に示すように生成する。
【数137】

なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数137は、以下のように、基底Bと基底B(t=1,...,L)と基底Bτとの基底ベクトルの係数が設定され、第2ランダム化要素kL,ran,(τ,ι)が生成されることを意味する。
まず、基底Bの部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。
基底Bの基底ベクトル1の係数として−sran,(τ,ι),0が設定される。基底ベクトル1+1,...,1+u+1の係数として0が設定される。基底ベクトル1+u+1+1,...,1+u+1+wの係数としてηran,(τ,ι),0,1,...,ηran,(τ,ι),0,wo(ここで、w0はwのことである)が設定される。基底ベクトル1+u+1+w+1,...,1+u+1+w+zの係数として0が設定される。
次に、基底B(t=1,...,L)の部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。
基底B(t=1,...,L)の基底ベクトル1の係数としてsran,(τ,ι),t+θran,(τ,ι),tt,1が設定される。基底ベクトル2,...,nの係数としてθran,(τ,ι),tt,2,...,θran,(τ,ι),tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηran,(τ,ι),t,1,...,ηran,(τ,ι),t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
次に、基底Bτの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbτ,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbτ,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbτ,1,...,bτ,3を意味する。
基底Bτの基底ベクトル1の係数としてsran,(τ,ι),L+1が設定される。基底ベクトル2,...,nτ,...,nτ+uτの係数として0が設定される。基底ベクトルnτ+uτ+1,...,nτ+uτ+wτの係数としてηran,(τ,ι),L+1,1,...,ηran,(τ,ι),L+1,wτ(ここで、wτはwτのことである)が設定される。基底ベクトルnτ+uτ+wτ+1,...,nτ+uτ+wτ+zτの係数として0が設定される。
【0051】
(S206:委譲要素生成ステップ)
委譲要素生成部144は、処理装置により、τ=L+1,...,dの各整数τと、各整数τについてι=1,...,nτの各整数ιとについて、復号鍵skの要素である委譲要素kL,del,(τ,ι)を数138に示すように生成する。
【数138】

なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数138は、以下のように、基底Bと基底B(t=1,...,L)と基底Bτとの基底ベクトルの係数が設定され、委譲要素kL,del,(τ,ι)が生成されることを意味する。
まず、基底Bの部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。
基底Bの基底ベクトル1の係数として−sdel,(τ,ι),0が設定される。基底ベクトル1+1,...,1+u+1の係数として0が設定される。基底ベクトル1+u+1+1,...,1+u+1+wの係数としてηdel,(τ,ι),0,1,...,ηdel,(τ,ι),0,wo(ここで、w0はwのことである)が設定される。基底ベクトル1+u+1+w+1,...,1+u+1+w+zの係数として0が設定される。
次に、基底B(t=1,...,L)の部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。
基底B(t=1,...,L)の基底ベクトル1の係数としてsdel,(τ,ι),t+θdel,(τ,ι),tt,1が設定される。基底ベクトル2,...,nの係数としてθdel,(τ,ι),tt,2,...,θdel,(τ,ι),tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηdel,(τ,ι),t,1,...,ηdel,(τ,ι),t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
次に、基底Bτの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbτ,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbτ,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbτ,1,...,bτ,3を意味する。
基底Bτの基底ベクトル1,...,nτの係数としてsdel,(τ,ι),L+1τ,1+ψeτ,ιが設定される。基底ベクトルnτ+1,...,nτ+uτの係数として0が設定される。基底ベクトルnτ+uτ+1,...,nτ+uτ+wτの係数としてηdel,(τ,ι),L+1,1,...,ηdel,(τ,ι),L+1,wτ(ここで、wτはwτのことである)が設定される。基底ベクトルnτ+uτ+wτ+1,...,nτ+uτ+wτ+zτの係数として0が設定される。
【0052】
(S207:鍵配布ステップ)
鍵配布部150は、復号要素kL,decと、第1ランダム化要素kL,ran,j(j=1,...,2L)と、第2ランダム化要素kL,ran,(τ,ι)(τ=L+1,...,d;(τ,ι)=(τ,1),...,(τ,nτ))と、委譲要素kL,del,(τ,ι)(τ=L+1,...,d;(τ,ι)=(τ,1),...,(τ,nτ))とを要素とする復号鍵skを、例えば通信装置によりネットワークを介して秘密裡に復号装置300へ配布する。もちろん、復号鍵skは、他の方法により復号装置300へ配布されてもよい。
【0053】
つまり、(S201)から(S206)において、鍵生成装置100は数139、数140に示すKeyGenアルゴリズムを実行して、復号鍵skを生成する。そして、(S207)で、鍵生成装置100は生成された復号鍵skを復号装置300へ配布する。
【数139】

【数140】

【0054】
暗号化装置200の機能と動作とについて説明する。
図9に示すように、暗号化装置200は、マスター公開鍵取得部210、情報入力部220(第2情報入力部)、暗号化データ生成部230、データ送信部240を備える。
また、情報入力部220は、属性情報入力部221、メッセージ入力部222を備える。また、暗号化データ生成部230は、乱数生成部231、暗号化データc1生成部232、暗号化データc2生成部233を備える。
【0055】
図14に基づき、暗号化装置200が実行するEncアルゴリズムの処理について説明する。
(S301:マスター公開鍵取得ステップ)
マスター公開鍵取得部210は、例えば、通信装置によりネットワークを介して、鍵生成装置100が生成したマスター公開鍵pkを取得する。
【0056】
(S302:情報入力ステップ)
属性情報入力部221は、入力装置により、属性情報(x,...,x):=((x1,i(i=1,...,n)),...,(xL,i(i=1,...,n)))を入力する。なお、属性情報としては、暗号化したメッセージを復号可能な者の属性が入力される。
また、メッセージ入力部222は、入力装置により、暗号化するメッセージmを入力する。
【0057】
(S303:乱数生成ステップ)
乱数生成部231は、処理装置により、乱数(xL+1,...,x):=((xL+1,i(i=1,...,nL+1)),...,(xd,i(i=1,...,n)))と、乱数ω,ζ,φ(t=0,...,d)とを数141に示すように生成する。
【数141】

【0058】
(S304:暗号化データc1生成ステップ)
暗号化データc1生成部232は、処理装置により、暗号化データctの要素である暗号化データcを数142に示すように生成する。
【数142】

なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数142は、以下のように、基底B及び基底B(t=1,...,d)の基底ベクトルの係数が設定され、暗号化データcが生成されることを意味する。
まず、基底Bの部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。
基底Bの基底ベクトル1の係数としてωが設定される。基底ベクトル1+1,...,1+uの係数として0が設定される。基底ベクトル1+u+1の係数としてζが設定される。基底ベクトル1+u+1+1,...,1+u+1+wの係数として0が設定される。基底ベクトル1+u+1+w+1,...,1+u+1+w+zの係数としてφ0,1,...,φ0,zo(ここで、z0はzのことである)が設定される。
次に、基底B(t=1,...,d)の部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。
基底B(t=1,...,d)の基底ベクトル1,...,nの係数としてωxt,1,...,ωxt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+u+wの係数として0が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数としてφt,1,...,φt,zt(ここで、ztはzのことである)が設定される。
【0059】
(S305:暗号化データc2生成ステップ)
暗号化データc2生成部233は、処理装置により、暗号化データctの要素である暗号化データcを数143に示すように生成する。
【数143】

【0060】
(S306:データ送信ステップ)
データ送信部240は、暗号化データcと、暗号化データcとを含む暗号化データctを、例えば通信装置によりネットワークを介して復号装置300へ送信する。もちろん、暗号化データctは、他の方法により復号装置300へ送信されてもよい。
【0061】
つまり、(S301)から(S305)において、暗号化装置200は数144に示すEncアルゴリズムを実行して、暗号化データctを生成する。そして、(S306)で、暗号化装置200は生成された暗号化データctを復号装置300へ送信する。
【数144】

【0062】
復号装置300の機能と動作とについて説明する。
図10に示すように、復号装置300は、復号鍵取得部310、データ受信部320、ペアリング演算部330、メッセージ計算部340を備える。
【0063】
図15に基づき、復号装置300が実行するDecアルゴリズムの処理について説明する。
(S401:復号鍵取得ステップ)
復号鍵取得部310は、例えば、通信装置によりネットワークを介して、復号鍵skを取得する。また、復号鍵取得部310は、鍵生成装置100が生成した公開パラメータpkを取得する。
【0064】
(S402:データ受信ステップ)
データ受信部320は、例えば、通信装置によりネットワークを介して、暗号化装置200が送信した暗号化データctを受信する。
【0065】
(S403:ペアリング演算ステップ)
ペアリング演算部330は、処理装置により、数145に示すペアリング演算を行い、セッション鍵K=gζを計算する。
【数145】

なお、(v,...,v)と(x,...,x)との内積が0であれば、数145を計算することにより、セッション鍵Kが計算される。
【0066】
(S404:メッセージ計算ステップ)
メッセージ計算部340は、処理装置により、暗号化データc2をセッション鍵Kで割ることにより、メッセージm’(=m)を計算する。
【0067】
つまり、(S401)から(S404)において、復号装置300は数146に示すDecアルゴリズムを実行して、メッセージm’(=m)を計算する。
【数146】

【0068】
鍵委譲装置400の機能と動作とについて説明する。
図11に示すように、鍵委譲装置400は、復号鍵取得部410、情報入力部420(第3情報入力部)、委譲鍵生成部430、鍵配布部440(委譲鍵送信部)を備える。
また、委譲鍵生成部430は、乱数生成部431、下位復号要素生成部432、下位ランダム化要素生成部433、下位委譲要素生成部434を備える。
【0069】
図16に基づき、鍵委譲装置400が実行するDelegateアルゴリズムの処理について説明する。
(S501:復号鍵取得ステップ)
復号鍵取得部410は、例えば、通信装置によりネットワークを介して、復号鍵skを取得する。また、復号鍵取得部410は、鍵生成装置100が生成した公開パラメータpkを取得する。
【0070】
(S502:情報入力ステップ)
情報入力部420は、入力装置により、述語情報vL+1:=(vL+1,i(i=1,...,nL+1))を入力する。なお、述語情報としては、鍵を委譲される者の属性が入力される。
【0071】
(S503:乱数生成ステップ)
乱数生成部431は、処理装置により、j=1,...,2Lと,j’=1,...,2(L+1)と,τ=L+2,...,dと,(τ,ι)=(τ,1),...,(τ,nτ)と,t=0,...,L+1,τと,(t,i)=(t,1),...,(t,n)との各整数j,j’,τ,ι,t,iについて、乱数αdec,j,σdec,αran,j’,j,σran,j’,αran,(τ,ι),j,σran,(τ,ι),φran,(τ,ι),αdel,(τ,ι),j,σdel,(τ,ι),φdel,(τ,ι),ψ’,ηdec,(t,i),ηran,j’,(t,i),ηran,(τ,ι),(t,i),ηdel,(τ,ι),(t,i)を数147に示すように生成する。
【数147】

【0072】
(S504:下位復号要素生成ステップ)
下位復号要素生成部432は、処理装置により、委譲鍵skL+1の要素である下位復号要素kL+1,decを数148に示すように生成する。
【数148】

【0073】
(S505:第1下位ランダム化要素生成ステップ)
下位ランダム化要素生成部433は、処理装置により、j’=1,...,2(L+1)の各整数j’について、委譲鍵skL+1の要素である第1下位ランダム化要素kL+1,ran,j’を数149に示すように生成する。
【数149】

【0074】
(S506:第2下位ランダム化要素生成ステップ)
下位ランダム化要素生成部433は、処理装置により、τ=L+2,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、委譲鍵skL+1の要素である第2下位ランダム化要素kL+1,ran,(τ,ι)を数150に示すように生成する。
【数150】

【0075】
(S507:下位委譲要素生成ステップ)
下位委譲要素生成部434は、処理装置により、τ=L+2,...,dの各整数τと、各整数τについてι=1,...,nτの各整数ιとについて、委譲鍵skL+1の要素である下位委譲要素kL+1,del,(τ,ι)を数151に示すように生成する。
【数151】

【0076】
(S508:鍵配布ステップ)
鍵配布部150は、下位復号要素kL+1,decと、第1下位ランダム化要素kL+1,ran,j’(j’=1,...,2(L+1))と、第2下位ランダム化要素kL+1,ran,(τ,ι)(τ=L+2,...,d;(τ,ι)=(τ,1),...,(τ,nτ))と、下位委譲要素kL+1,del,(τ,ι)(τ=L+2,...,d;(τ,ι)=(τ,1),...,(τ,nτ))とを要素とする委譲鍵skL+1(下位の復号鍵)を、例えば通信装置によりネットワークを介して秘密裡に下位の復号装置300へ配布する。もちろん、委譲鍵skL+1は、他の方法により下位の復号装置300へ配布されてもよい。
【0077】
つまり、(S501)から(S507)において、鍵委譲装置400は数152、153に示すDelegateアルゴリズムを実行して、委譲鍵skL+1を生成する。そして、(S508)で、鍵委譲装置400は生成された委譲鍵skL+1を下位の復号装置300へ配布する。
【数152】

【数153】

【0078】
なお、下位の復号装置300が、委譲鍵skL+1を用いてDecアルゴリズムを実行した場合、図15の(S403)では、(v,...,vL+1)と(x,...,xL+1)との内積が0であれば、数145を計算することにより、セッション鍵Kが計算される。
【0079】
以上のように、実施の形態1に係る暗号処理システム10は、d+1個のN(t=0,...,d)次元空間を用いて、d階層の階層的内積述語暗号方式を実現する。ここで、第L層目(1≦L≦d)の暗号処理に必要な空間は、L+1個のN(t=0,...,L)次元空間である。したがって、鍵のサイズを小さくでき、演算等の効率をよくすることができる。また、鍵を記録するメモリやレジスタ等の領域も小さくなる。
【0080】
なお、上記説明において、u、w、z(t=0,...,d)の次元は、安全性を高めるために設けた次元である。したがって、安全性が低くなってしまうが、u、w、z(t=0,...,d)をそれぞれ0として、u、w、z(t=0,...,d)の次元を設けなくてもよい。
【0081】
また、上記説明では、Nに1+u+1+w+zを設定し、Nにn+u+w+zを設定した。しかし、1+u+1+w+zを1+1+1+1+1としてNに5を設定し、n+u+w+zをn+n+n+1としてNに3n+1を設定してもよい。
この場合、数132に示すSetupアルゴリズムは、数154のように書き換えられる。なお、Gobは数155のように書き換えられる。
【数154】

【数155】

また、数139、数140に示すKeyGenアルゴリズムは、数156、数157のように書き換えられる。
【数156】

【数157】

また、数144に示すEncアルゴリズムは、数158のように書き換えられる。
【数158】

また、数152、数153に示すDelegateアルゴリズムは、数159、数160のように書き換えられる。
【数159】

【数160】

なお、数146に示すDecアルゴリズムに変更はない。
【0082】
また、Setupアルゴリズムは、暗号処理システム10のセットアップ時に一度実行すればよく、復号鍵を生成する度に実行する必要はない。また、上記説明では、SetupアルゴリズムとKeyGenアルゴリズムとを鍵生成装置100が実行するとしたが、SetupアルゴリズムとKeyGenアルゴリズムとをそれぞれ異なる装置が実行するとしてもよい。
【0083】
実施の形態2.
この実施の形態では、実施の形態1で説明した方式を一般化した階層的内積述語暗号方式について説明する。
【0084】
実施の形態1で説明した階層的内積述語暗号方式では、原則として暗号化データctに設定された属性情報と、復号鍵に設定された述語情報との内積が0の場合に、暗号化データctを復号鍵で復号可能であった。
しかし、実施の形態2で説明する階層的内積述語暗号方式では、暗号化データctに設定された属性情報と、復号鍵に設定された述語情報との内積が0とならない場合であっても復号可能となるように設定できる。
具体的には、以下の説明において、ρ(t=1,...,d)の値が0である整数tについては、属性情報xと述語情報vとの内積が0となり、ρ(t=1,...,d)の値が1である整数tについては、属性情報xと述語情報vとの内積が0とならない場合に、復号可能となる。
これにより、例えば、ρ(t=1,...,d)の値の設定に応じて、肯定形の条件式(例えば、属性情報=述語情報)と否定形の条件式(属性情報≠述語情報)との設定をすることができる。
【0085】
図17から図19に基づき、実施の形態2に係る階層的内積述語暗号方式、及び、階層的内積述語暗号方式を実行する暗号処理システム10の機能と動作とについて説明する。
なお、実施の形態2に係る暗号処理システム10の機能構成については、図8から図11に示す実施の形態1に係る暗号処理システム10の機能構成と同一である。
図17は、鍵生成装置100の動作を示すフローチャートであり、KeyGenアルゴリズムの処理を示すフローチャートである。図18は、復号装置300の動作を示すフローチャートであり、Decアルゴリズムの処理を示すフローチャートである。図19は、鍵委譲装置400の動作を示すフローチャートであり、Delegateアルゴリズムの処理を示すフローチャートである。
なお、実施の形態2に係るSetupアルゴリズムとEncアルゴリズムとの処理は、実施の形態1に係るSetupアルゴリズムとEncアルゴリズムとの処理と同一であるため、説明を省略する。但し、Encアルゴリズムでは、暗号化データctに、暗号化データc,cだけでなく、属性情報x(i=1,...,L)も含めて、復号装置300へ送信する。
【0086】
図17に基づき、鍵生成装置100が実行するKeyGenアルゴリズムの処理について説明する。
(S601:情報入力ステップ)
情報入力部130は、入力装置により、述語情報((v,ρ),...,(v,ρ)):=((v1,i(i=1,...,n),ρ∈{0,1}),...,(vL,i(i=1,...,n),ρ∈{0,1}))を入力する。なお、述語情報としては、鍵を使用する者の属性が入力される。
【0087】
(S602:乱数生成ステップ)
乱数生成部141は、処理装置により、j=1,...,2Lと、τ=L+1,...,dと、(τ,ι)=(τ,1),...,(τ,nτ)との各整数j,τ,ιについて、乱数ψと、乱数sdec,t,sran,j,t(t=1,...,L)と、乱数θdec,t,θran,j,t,ηdec,t,ηran,j,t,ηran,0,t,ηdel,0,t,ηdel,1,t(t=0,...,L)と、乱数sran,0,t,sdel,0,t,sdel,1,t(t=0,...,L+1)と、乱数θran,0,t,θdel,0,t,θdel,1,t(t=0,...,L+1)と、乱数ηran,(τ,ι),ηdel,0,(τ,ι),ηdel,1,(τ,ι)とを数161に示すように生成する。
【数161】

また、数162に示すようにsdec,0と、sran,j,0と、sran,0,0と、sdel,0,0と、sdel,1,0とを設定する。
【数162】

【0088】
(S603:復号要素生成ステップ)
復号要素生成部142は、処理装置により、復号鍵skの要素である復号要素kL,decを数163に示すように生成する。
【数163】

なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数163は、以下のように、基底B及び基底B(t=1,...,L)の基底ベクトルの係数が設定され、復号要素kL,decが生成されることを意味する。
まず、基底Bの部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。
基底Bの基底ベクトル1の係数として−sdec,0が設定される。基底ベクトル1+1,...,1+uの係数として0が設定される。基底ベクトル1+u+1の係数として1が設定される。基底ベクトル1+u+1+1,...,1+u+1+wの係数としてηdec,0,1,...,ηdec,0,wo(ここで、w0はwのことである)が設定される。基底ベクトル1+u+1+w+1,...,1+u+1+w+zの係数として0が設定される。
次に、基底B(t=1,...,L)の部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。また、基底B(t=1,...,L)については、ρの値が0であるか、1であるかによって場合分けされる。
ρの値が0の場合、基底B(t=1,...,L)の基底ベクトル1の係数としてsdec,t+θdec,tt,1が設定される。基底ベクトル2,...,nの係数としてθdec,tt,2,...,θdec,tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηdec,t,1,...,ηdec,t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
一方、ρの値が1の場合、基底B(t=1,...,L)の基底ベクトル1,...,nの係数としてsdec,tt,1,...,sdec,tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηdec,t,1,...,ηdec,t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
【0089】
(S604:第1ランダム化要素生成ステップ)
ランダム化要素生成部143は、処理装置により、j=1,...,2Lの各整数jについて、復号鍵skの要素である第1ランダム化要素kL,ran,jを数164に示すように生成する。
【数164】

なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数164は、以下のように、基底B及び基底B(t=1,...,L)の基底ベクトルの係数が設定され、第1ランダム化要素kL,ran,jが生成されることを意味する。
まず、基底Bの部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。
基底Bの基底ベクトル1の係数として−sran,j,0が設定される。基底ベクトル1+1,...,1+u+1の係数として0が設定される。基底ベクトル1+u+1+1,...,1+u+1+wの係数としてηran,j,0,1,...,ηran,j,0,wo(ここで、w0はwのことである)が設定される。基底ベクトル1+u+1+w+1,...,1+u+1+w+zの係数として0が設定される。
次に、基底B(t=1,...,L)の部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。また、基底B(t=1,...,L)については、ρの値が0であるか、1であるかによって場合分けされる。
ρの値が0の場合、基底B(t=1,...,L)の基底ベクトル1の係数としてsran,j,t+θran,j,tt,1が設定される。基底ベクトル2,...,nの係数としてθran,j,tt,2,...,θran,j,tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηran,j,t,1,...,ηran,j,t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
一方、ρの値が1の場合、基底B(t=1,...,L)の基底ベクトル1,...,nの係数としてsran,j,tt,1,...,sran,j,tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηran,j,t,1,...,ηran,j,t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
【0090】
(S605:第2ランダム化要素生成ステップ)
ランダム化要素生成部143は、処理装置により、τ=L+1,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、復号鍵skの要素である第2ランダム化要素kL,ran,(τ,ι,0)を数165に示すように生成する。
【数165】

なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数165は、以下のように、基底Bと基底B(t=1,...,L)と基底Bτとの基底ベクトルの係数が設定され、第2ランダム化要素kL,ran,(τ,ι,0)が生成されることを意味する。
まず、基底Bの部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。
基底Bの基底ベクトル1の係数として−sran,0,0が設定される。基底ベクトル1+1,...,1+u+1の係数として0が設定される。基底ベクトル1+u+1+1,...,1+u+1+wの係数としてηran,0,0,1,...,ηran,0,0,wo(ここで、w0はwのことである)が設定される。基底ベクトル1+u+1+w+1,...,1+u+1+w+zの係数として0が設定される。
次に、基底B(t=1,...,L)の部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。また、基底B(t=1,...,L)については、ρの値が0であるか、1であるかによって場合分けされる。
ρの値が0の場合、基底B(t=1,...,L)の基底ベクトル1の係数としてsran,0,t+θran,0,tt,1が設定される。基底ベクトル2,...,nの係数としてθran,0,tt,2,...,θran,0,tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηran,0,t,1,...,ηran,0,t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
一方、ρの値が1の場合、基底B(t=1,...,L)の基底ベクトル1,...,nの係数としてsran,0,tt,1,...,sran,0,tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηran,0,t,1,...,ηran,0,t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
次に、基底Bτの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbτ,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbτ,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbτ,1,...,bτ,3を意味する。
基底Bτの基底ベクトル1の係数としてsran,0,L+1が設定される。基底ベクトル2,...,nτ,...,nτ+uτの係数として0が設定される。基底ベクトルnτ+uτ+1,...,nτ+uτ+wτの係数としてηran,0,(τ,ι),1,...,ηran,0,(τ,ι)s,wτ(ここで、wτはwτのことである)が設定される。基底ベクトルnτ+uτ+wτ+1,...,nτ+uτ+wτ+zτの係数として0が設定される。
【0091】
(S606:第1委譲要素生成ステップ)
委譲要素生成部144は、処理装置により、τ=L+1,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、復号鍵skの要素である第1委譲要素kL,del,(τ,ι,0)を数166に示すように生成する。
【数166】

なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数166は、以下のように、基底Bと基底B(t=1,...,L)と基底Bτとの基底ベクトルの係数が設定され、第1委譲要素kL,del,(τ,ι,0)が生成されることを意味する。
まず、基底Bの部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。
基底Bの基底ベクトル1の係数として−sdel,0,0が設定される。基底ベクトル1+1,...,1+u+1の係数として0が設定される。基底ベクトル1+u+1+1,...,1+u+1+wの係数としてηdel,0,0,1,...,ηdel,0,0,wo(ここで、w0はwのことである)が設定される。基底ベクトル1+u+1+w+1,...,1+u+1+w+zの係数として0が設定される。
次に、基底B(t=1,...,L)の部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。また、基底B(t=1,...,L)については、ρの値が0であるか、1であるかによって場合分けされる。
ρの値が0の場合、基底B(t=1,...,L)の基底ベクトル1の係数としてsdel,0,t+θdel,0,tt,1が設定される。基底ベクトル2,...,nの係数としてθdel,0,tt,2,...,θdel,0,tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηdel,0,t,1,...,ηdel,0,t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
一方、ρの値が1の場合、基底B(t=1,...,L)の基底ベクトル1,...,nの係数としてsdel,0,tt,1,...,sdel,0,tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηdel,0,t,1,...,ηdel,0,t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
次に、基底Bτの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbτ,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbτ,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbτ,1,...,bτ,3を意味する。
基底Bτの基底ベクトル1,...,nτの係数としてsdel,0,L+1τ,1+ψeτ,ιが設定される。基底ベクトルnτ+1,...,nτ+uτの係数として0が設定される。基底ベクトルnτ+uτ+1,...,nτ+uτ+wτの係数としてηdel,0,(τ,ι),1,...,ηdel,0,(τ,ι),wτ(ここで、wτはwτのことである)が設定される。基底ベクトルnτ+uτ+wτ+1,...,nτ+uτ+wτ+zτの係数として0が設定される。
【0092】
(S607:第2委譲要素生成ステップ)
委譲要素生成部144は、処理装置により、τ=L+1,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、復号鍵skの要素である第2委譲要素kL,del,(τ,ι,1)を数167に示すように生成する。
【数167】

なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数167は、以下のように、基底Bと基底B(t=1,...,L)と基底Bτとの基底ベクトルの係数が設定され、第2委譲要素kL,del,(τ,ι,1)が生成されることを意味する。
まず、基底Bの部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。
基底Bの基底ベクトル1の係数として−sdel,1,0が設定される。基底ベクトル1+1,...,1+u+1の係数として0が設定される。基底ベクトル1+u+1+1,...,1+u+1+wの係数としてηdel,1,0,1,...,ηdel,1,0,wo(ここで、w0はwのことである)が設定される。基底ベクトル1+u+1+w+1,...,1+u+1+w+zの係数として0が設定される。
次に、基底B(t=1,...,L)の部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。また、基底B(t=1,...,L)については、ρの値が0であるか、1であるかによって場合分けされる。
ρの値が0の場合、基底B(t=1,...,L)の基底ベクトル1の係数としてsdel,1,t+θdel,1,tt,1が設定される。基底ベクトル2,...,nの係数としてθdel,1,tt,2,...,θdel,1,tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηdel,1,t,1,...,ηdel,1,t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
一方、ρの値が1の場合、基底B(t=1,...,L)の基底ベクトル1,...,nの係数としてsdel,1,tt,1,...,sdel,1,tt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,n+uの係数として0が設定される。基底ベクトルn+u+1,...,n+u+wの係数としてηdel,1,t,1,...,ηdel,1,t,wt(ここで、wtはwのことである)が設定される。基底ベクトルn+u+w+1,...,n+u+w+zの係数として0が設定される。
次に、基底Bτの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbτ,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbτ,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbτ,1,...,bτ,3を意味する。
基底Bτの基底ベクトル1,...,nτの係数としてsdel,1,L+1τ,ιが設定される。基底ベクトルnτ+1,...,nτ+uτの係数として0が設定される。基底ベクトルnτ+uτ+1,...,nτ+uτ+wτの係数としてηdel,1,(τ,ι),1,...,ηdel,1,(τ,ι),wτ(ここで、wτはwτのことである)が設定される。基底ベクトルnτ+uτ+wτ+1,...,nτ+uτ+wτ+zτの係数として0が設定される。
【0093】
(S608:鍵配布ステップ)
鍵配布部150は、復号要素kL,decと、第1ランダム化要素kL,ran,j(j=1,...,2L)と、第2ランダム化要素kL,ran,(τ,ι,0)(τ=L+1,...,d;(τ,ι)=(τ,1),...,(τ,nτ))と、第1委譲要素kL,del,(τ,ι,0)(τ=L+1,...,d;(τ,ι)=(τ,1),...,(τ,nτ))と、第2委譲要素kL,del,(τ,ι,1)(τ=L+1,...,d;(τ,ι)=(τ,1),...,(τ,nτ))とを要素とする復号鍵skを、例えば通信装置によりネットワークを介して秘密裡に復号装置300へ配布する。もちろん、復号鍵skは、他の方法により復号装置300へ配布されてもよい。
【0094】
つまり、(S601)から(S607)において、鍵生成装置100は数168、数169に示すKeyGenアルゴリズムを実行して、復号鍵skを生成する。そして、(S608)で、鍵生成装置100は生成された復号鍵skを復号装置300へ配布する。
【数168】

【数169】

【0095】
図18に基づき、復号装置300が実行するDecアルゴリズムの処理について説明する。
(S701:復号鍵取得ステップ)
復号鍵取得部310は、例えば、通信装置によりネットワークを介して、復号鍵skを取得する。また、復号鍵取得部310は、鍵生成装置100が生成した公開パラメータpkを取得する。
【0096】
(S702:データ受信ステップ)
データ受信部320は、例えば、通信装置によりネットワークを介して、暗号化装置200が送信した暗号化データctを受信する。
【0097】
(S703:ペアリング演算ステップ)
ペアリング演算部330は、処理装置により、数170に示すペアリング演算を行い、セッション鍵K=gζを計算する。
【数170】

ここで、数171である。
【数171】

なお、t=1,...,Lの各整数tに関して、ρ=0の整数tについてvとxとの内積が0であり、ρ=1の整数tについてvとxとの内積が0でなければ、数170を計算することにより、セッション鍵Kが計算される。
【0098】
(S704:メッセージ計算ステップ)
メッセージ計算部340は、処理装置により、暗号化データc2をセッション鍵Kで割ることにより、メッセージm’(=m)を計算する。
【0099】
つまり、(S701)から(S704)において、復号装置300は数172に示すDecアルゴリズムを実行して、メッセージm’(=m)を計算する。
【数172】

【0100】
図19に基づき、鍵委譲装置400が実行するDelegateアルゴリズムの処理について説明する。
(S801:復号鍵取得ステップ)
復号鍵取得部410は、例えば、通信装置によりネットワークを介して、復号鍵skを取得する。また、復号鍵取得部410は、鍵生成装置100が生成した公開パラメータpkを取得する。
【0101】
(S802:情報入力ステップ)
情報入力部420は、入力装置により、述語情報(vL+1,ρL+1):=(vL+1,i(i=1,...,nL+1),ρL+1∈{0,1})を入力する。なお、述語情報としては、鍵を委譲される者の属性が入力される。
【0102】
(S803:乱数生成ステップ)
乱数生成部431は、処理装置により、j=1,...,2Lと,j’=1,...,2(L+1)と,τ=L+2,...,dと,(τ,ι)=(τ,1),...,(τ,nτ)と,t=0,...,L+1,τと,(t,i)=(t,1),...,(t,n)との各整数j,j’,τ,ι,t,iについて、乱数αdec,j,σdec,αran,j’,j,σran,j’,αran,(τ,ι,0),j,σran,(τ,ι,0),φran,(τ,ι,0),αdel,(τ,ι,0),j,σdel,(τ,ι,0),φdel,(τ,ι,0),αdel,(τ,ι,1),j,σdel,(τ,ι,1),φdel,(τ,ι,1),ηdec,(t,i),ηran,j’,(t,i),ηran,(τ,ι,0),(t,i),ηdel,(τ,ι,0),(t,i),ηdel,(τ,ι,1),(t,i),ψ,ψを数173に示すように生成する。
【数173】

【0103】
(S804:下位復号要素生成ステップ)
下位復号要素生成部432は、処理装置により、委譲鍵skL+1の要素である下位復号要素kL+1,decを数174に示すように生成する。
【数174】

【0104】
(S805:第1下位ランダム化要素生成ステップ)
下位ランダム化要素生成部433は、処理装置により、j’=1,...,2(L+1)の各整数j’について、委譲鍵skL+1の要素である第1下位ランダム化要素kL+1,ran,j’を数175に示すように生成する。
【数175】

【0105】
(S806:第2下位ランダム化要素生成ステップ)
下位ランダム化要素生成部433は、処理装置により、τ=L+2,...,dの各整数τと、各整数τについてι=1,...,nτの各整数ιとについて、委譲鍵skL+1の要素である第2下位ランダム化要素kL+1,ran,(τ,ι)を数176に示すように生成する。
【数176】

【0106】
(S807:第1下位委譲要素生成ステップ)
下位委譲要素生成部434は、処理装置により、τ=L+2,...,dの各整数τと、各整数τについてι=1,...,nτの各整数ιとについて、委譲鍵skL+1の要素である第1下位委譲要素kL+1,del,(τ,ι,0)を数177に示すように生成する。
【数177】

【0107】
(S808:第2下位委譲要素生成ステップ)
下位委譲要素生成部434は、処理装置により、τ=L+2,...,dの各整数τと、各整数τについてι=1,...,nτの各整数ιとについて、委譲鍵skL+1の要素である第2下位委譲要素kL+1,del,(τ,ι,1)を数178に示すように生成する。
【数178】

【0108】
(S809:鍵配布ステップ)
鍵配布部150は、下位復号要素kL+1,decと、第1下位ランダム化要素kL+1,ran,j’(j’=1,...,2(L+1))と、第2下位ランダム化要素kL+1,ran,(τ,ι,0)(τ=L+2,...,d;(τ,ι)=(τ,1),...,(τ,nτ))と、第1下位委譲要素kL+2,del,(τ,ι,0)(τ=L+2,...,d;(τ,ι)=(τ,1),...,(τ,nτ))と、第2下位委譲要素kL+2,del,(τ,ι,1)(τ=L+2,...,d;(τ,ι)=(τ,1),...,(τ,nτ))とを要素とする委譲鍵skL+1を、例えば通信装置によりネットワークを介して秘密裡に下位の復号装置300へ配布する。もちろん、委譲鍵skL+1は、他の方法により下位の復号装置300へ配布されてもよい。
【0109】
つまり、(S501)から(S507)において、鍵委譲装置400は数179、数180に示すDelegateアルゴリズムを実行して、委譲鍵skL+1を生成する。そして、(S508)で、鍵委譲装置400は生成された委譲鍵skL+1を下位の復号装置300へ配布する。
【数179】

【数180】

【0110】
なお、下位の復号装置300が、委譲鍵skL+1を用いてDecアルゴリズムを実行した場合、図15の(S403)では、(v,...,vL+1)と(x,...,xL+1)との内積が0であれば、数170を計算することにより、セッション鍵Kが計算される。
【0111】
以上のように、実施の形態2に係る暗号処理システム10は、一部については属性情報と述語情報との内積が0となり、残りの部分については属性情報と述語情報との内積が0とならない場合に、復号可能な階層的内積述語暗号方式を実現する。そのため、例えば、肯定形と否定形との条件設定などが可能である。
【0112】
なお、上記説明において、u、w、z(t=0,...,d)の次元は、安全性を高めるために設けた次元である。したがって、安全性が低くなってしまうが、u、w、z(t=0,...,d)をそれぞれ0として、u、w、z(t=0,...,d)の次元を設けなくてもよい。
【0113】
また、上記説明では、Nに1+u+1+w+zを設定し、Nにn+u+w+zを設定した。しかし、1+u+1+w+zを1+1+1+1+1としてNに5を設定し、n+u+w+zをn+n+n+1としてNに3n+1を設定してもよい。
この場合、数168、数169に示すKeyGenアルゴリズムは、数181、数182のように書き換えられる。
【数181】

【数182】

また、数179、数180に示すDelegateアルゴリズムは、数183、数184のように書き換えられる。
【数183】

【数184】

なお、数172に示すDecアルゴリズムに変更はない。
【0114】
また、Setupアルゴリズムは、暗号処理システム10のセットアップ時に一度実行すればよく、復号鍵を生成する度に実行する必要はない。また、上記説明では、SetupアルゴリズムとKeyGenアルゴリズムとを鍵生成装置100が実行するとしたが、SetupアルゴリズムとKeyGenアルゴリズムとをそれぞれ異なる装置が実行するとしてもよい。
【0115】
実施の形態3.
以上の実施の形態では、双対ベクトル空間において暗号処理を実現する方法について説明した。この実施の形態では、双対加群において暗号処理を実現する方法について説明する。
【0116】
つまり、以上の実施の形態では、素数位数qの巡回群において暗号処理を実現した。しかし、合成数Mを用いて数185のように環Rを表した場合、環Rを係数とする加群においても、上記実施の形態で説明した暗号処理を適用することができる。
【数185】

【0117】
実施の形態1で説明した階層的述語暗号方式を、環Rを係数とする加群において実現すると数186から数193のようになる。
【数186】

【数187】

【数188】

【数189】

【数190】

【数191】

【数192】

【数193】

【0118】
実施の形態2で説明した階層的述語暗号方式を、環Rを係数とする加群において実現すると数194から数199のようになる。なお、SetupアルゴリズムとGobアルゴリズムとは、数186と数187とに示す通りである。
【数194】

【数195】

【数196】

【数197】

【数198】

【数199】

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

【特許請求の範囲】
【請求項1】
t=1,...,L+1(Lは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を行う暗号処理システムであり、
t=1,...,Lのうち少なくとも一部の整数tについての基底Bの基底ベクトルに属性情報xを埋め込んだベクトルを暗号化データctとして生成する暗号化装置と、
t=1,...,Lの各整数tについての基底Bの基底ベクトルに述語情報vを埋め込んだベクトルを復号鍵skとして、前記暗号化装置が生成した暗号化データctと前記復号鍵skとについてペアリング演算を行い前記暗号化データctを復号する復号装置と、
基底BL+1の基底ベクトルに述語情報vL+1を埋め込んだベクトルと、前記復号装置が使用した復号鍵skとに基づき、前記復号鍵skの下位の復号鍵skL+1を生成する鍵委譲装置と
を備えることを特徴とする暗号処理システム。
【請求項2】
前記暗号処理システムは、さらに、前記復号鍵skを生成する鍵生成装置を備え、
前記鍵生成装置は、
t=1,...,Lの各整数tについて述語情報v:=(vt,i)(i=1,...,n)を入力する第1情報入力部と、
前記第1情報入力部が入力した述語情報vと、所定の値Δと、t=1,...,Lの各整数tについての所定の値θdec,tと、sdec,0=Σt=1dec,tであるようなt=0,...,Lの各整数tについての所定の値sdec,tとを用いて、基底Bの基底ベクトルb0,p(pは所定の値)の係数として−sdec,0を設定し、基底Bの基底ベクトルb0,q(qは所定の値)の係数として前記Δを設定し、t=1,...,Lの各整数tについての基底Bの基底ベクトルbt,i(i=1,...,n)の係数としてsdec,tt,1+θdec,tt,i(i=1,...,n)を設定した復号要素kL,decを生成する復号要素生成部と、
前記復号要素生成部が生成した復号要素kL,decを含む復号鍵skを前記復号装置へ送信する復号鍵送信部と
を備え、
前記暗号化装置は、
t=1,...,Lの少なくとも一部の整数tについて属性情報x:=(xt,i)(i=1,...,n)を入力する第2情報入力部と、
前記第2情報入力部が入力した属性情報xと、所定の値ω,ζとを用いて、基底Bの基底ベクトルb0,pの係数として前記ωを設定し、基底Bの基底ベクトルb0,qの係数として前記ζを設定し、前記少なくとも一部の整数tについての基底Bの基底ベクトルbt,i(i=1,...,n)の係数としてωxt,i(i=1,...,n)を設定した暗号化データcを生成する暗号化データc1生成部と、
前記暗号化データc1生成部が生成した暗号化データcを含む暗号化データctを前記復号装置へ送信するデータ送信部と
を備え、
前記復号装置は、
前記データ送信部が送信した暗号化データctに含まれる暗号化データcと、前記復号鍵送信部が送信した前記復号鍵skに含まれる復号要素kL,decとについて、ペアリング演算e(c,kL,dec)を行うペアリング演算部
を備えることを特徴とする請求項1に記載の暗号処理システム。
【請求項3】
前記暗号化装置は、さらに、
値g=e(b0,1,b0,1)と、前記Δと、前記ζとから得られるgΔζを、メッセージmに乗じた暗号化データcを生成する暗号化データc2生成部
を備え、
前記データ送信部は、暗号化データcと、前記暗号化データc2生成部が生成した暗号化データcとを含む暗号化データctを前記復号装置へ送信し、
前記ペアリング演算部は、前記ペアリング演算e(c,kL,dec)を行い、セッション鍵K:=gΔζを計算し、
前記復号装置は、さらに、
前記ペアリング演算部が計算したセッション鍵Kで、前記暗号化データcを除して、前記メッセージmを計算するメッセージ計算部
を備えることを特徴とする請求項2に記載の暗号処理システム。
【請求項4】
前記鍵生成装置は、さらに、
τ=L+1である整数τと、ι=1,...,nτの各整数ιとについて委譲要素kL,del,(τ,ι)を生成する委譲要素生成部であって、t=1,...,Lの各整数tについての所定の値θdel,(τ,ι),tと、所定の値ψと、sdel,(τ,ι),0=Σt=1L+1del,(τ,ι),tであるようなt=0,...,L+1の各整数tについての所定の値sdel,(τ,ι),tとを用いて、基底Bの基底ベクトルb0,pの係数として−sdel,(τ,ι),0を設定し、t=1,...,Lの各整数tについての基底Bの基底ベクトルbt,i(i=1,...,n)の係数としてsdel,(τ,ι),tt,1+θdel,(τ,ι),tt,i(i=1,...,n)を設定し、基底Bτの基底ベクトルbτ,i(i=1,...,nτ)の係数としてsdel,(τ,ι),L+1τ,1+ψeτ,ι(i=1,...,nτ)を設定して委譲要素kL,del,(τ,ι)を生成する委譲要素生成部
を備え、
前記復号鍵送信部は、前記復号要素kL,decと、前記委譲要素生成部が生成した委譲要素kL,del,(τ,ι)とを含む復号鍵skを前記委譲装置へ送信し、
前記鍵委譲装置は、
述語情報vL+1:=(vL+1,i)(i=1,...,nL+1)を入力する第3情報入力部と、
前記第3情報入力部が入力した述語情報vL+1と、前記復号鍵送信部が送信した復号鍵skとを用いて、数1に示すベクトルを含む下位復号要素kL+1,decを生成する下位復号要素生成部と、
前記下位復号要素生成部が生成した下位復号要素kL+1,decを含む下位の復号鍵skL+1を下位の復号装置へ送信する委譲鍵送信部と
を備えることを特徴とする請求項2に記載の暗号処理システム。
【数1】

【請求項5】
前記暗号処理システムは、
少なくとも基底ベクトルb0,i(i=1,...,1+n,1+n+1,...,1+n+1+u,...,1+n+1+u+w,...,1+n+1+u+w+z)(n,u,w,zは1以上の整数)を有する基底Bと、
少なくとも基底ベクトルb0,i(i=1,...,1+n,1+n+1,...,1+n+1+u,...,1+n+1+u+w,...,1+n+1+u+w+z)(n,u,w,zは1以上の整数)を有する基底Bと、
少なくとも基底ベクトルbt,i(i=1,...,n,...,n+u,...,n+u+w,...,n+u+w+z)(u,w,zは1以上の整数)を有する基底B(t=1,...,L+1)と、
少なくとも基底ベクトルbt,i(i=1,...,n,...,n+u,...,n+u+w,...,n+u+w+z)を有する基底B(t=1,...,L+1)と
を用いて暗号処理を行い、
前記復号要素生成部は、t=0,...,Lの各整数tについての乱数ηdec,t:=(ηdec,t,i)(i=1,...,w)に基づき、数2に示す復号要素をkL,decを生成し、
前記暗号化データc1生成部は、t=0,...,Lの各整数tについての乱数φ:=(φt,i)(i=1,...,z)に基づき、数3に示す暗号化データcを生成する
ことを特徴とする請求項2に記載の暗号処理システム。
【数2】

【数3】

【請求項6】
前記鍵生成装置は、さらに、
j=1,...,2Lの各整数jについて、第1ランダム化要素kL,ran,jを生成するとともに、τ=L+1,...,d(dはL+1以上の整数)の各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、第2ランダム化要素kL,ran,(τ,ι)を生成するランダム化要素生成部であって、
t=1,...,Lの各整数tについての所定の値θran,j,tと、sran,j,0=Σt=1ran,j,tであるようなt=0,...,Lについての所定の値sran,j,tと、t=0,...,Lの各整数tについての乱数ηran,j,t:=(ηran,j,t,i)(i=1,...,w)とに基づき、数4に示す第1ランダム化要素kL,ran,jを生成し、
t=1,...,Lの各整数tについての所定の値θran,(τ,ι),tと、sran,(τ,ι),0=Σt=1L+1ran,(τ,ι),tであるようなt=0,...,L+1についての所定の値sran,(τ,ι),tと、t=0,...,L+1の各整数tについての乱数ηran,(τ,ι),t:=(ηran,(τ,ι),t,i)(i=1,...,w)とに基づき、数5に示す第2ランダム化要素kL,ran,(τ,ι)を生成するランダム化要素生成部
を備え、
前記委譲要素生成部は、τ=L+1,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、t=0,...,L+1の各整数tについての乱数ηdel,(τ,ι),t:=(ηdel,(τ,ι),t,i)(i=1,...,w)に基づき、数6に示す委譲要素kL,del,(τ,ι)を生成し、
前記復号鍵送信部は、前記復号要素kL,decと、前記ランダム化要素生成部が生成した第1ランダム化要素kL,ran,j及び第2ランダム化要素kL,ran,(τ,ι)と、前記委譲要素生成部が生成した委譲要素kL,del,(τ,ι)とを含む復号鍵skを前記委譲装置へ送信し、
前記下位復号要素生成部は、前記述語情報vL+1と、前記復号鍵送信部が送信した復号鍵skと、j=1,...,2Lの各整数jについての乱数αdec,jと、乱数σdecと、t=0,...,L+1の各整数tとi=1,...,wの各整数iとについての乱数ηdec,(t,i)とを用いて、数7に示す下位復号要素kL+1,decを生成する
ことを特徴とする請求項5に記載の暗号処理システム。
【数4】

【数5】

【数6】

【数7】

【請求項7】
前記委譲装置は、さらに、
j’=1,...,2(L+1)の各整数j’について、第1下位ランダム化要素kL+1,ran,j’を生成するとともに、τ=L+2,...,d(dはL+2以上の整数)の各整数τと、各整数τに関してι=1,...,nτの各整数ιについて、第2下位ランダム化要素kL+1,ran,(τ,ι)を生成する下位ランダム化要素生成部であって、
前記述語情報vL+1と、前記復号鍵skと、j=1,...,2Lの各整数jとj’=1,...,2(L+1)の各整数j’とについての乱数αran,j’,jと、j’=1,...,2(L+1)の各整数j’についての乱数σran,j’と、t=0,...,L+1の各整数tとi=1,...,wの各整数iとについての乱数ηran,j’,(t,i)とに基づき、数8に示す第1下位ランダム化要素kL+1,ran,j’を生成し、
前記述語情報vL+1と、前記復号鍵skと、j=1,...,2Lの各整数jについての乱数αran,(τ,ι),jと、乱数σran,(τ,ι)と、乱数φran,(τ,ι)と、t=0,...,L+1,τの各整数tとi=1,...,wの各整数iとについてのηran,(τ,ι),(t,i)とに基づき、数9に示す第2下位ランダム化要素kL+1,ran,(τ,ι)を生成する下位ランダム化要素生成部と、
τ=L+2,...,d(dはL+2以上の整数)の各整数τと、各整数τに関してι=1,...,nτの各整数ιについて、下位委譲要素kL+1,del,(τ,ι)を生成する下位委譲要素生成部であって、前記述語情報vL+1と、前記復号鍵skと、j=1,...,2Lの各整数jについての乱数αdel,(τ,ι),jと、乱数σdel,(τ,ι)と、乱数ψ’と、乱数φdel,(τ,ι)と、t=0,...,L+1,τの各整数tとi=1,...,wの各整数iとについてのηdel,(τ,ι),(t,i)とに基づき、数10に示す下位委譲要素kL+1,del,(τ,ι)を生成する下位委譲要素生成部と
を備え、
前記委譲鍵送信部は、前記下位復号要素生成部が生成した下位復号要素kL+1,decと、前記下位ランダム化要素生成部が生成した第1下位ランダム化要素kL+1,ran,j’及び第2下位ランダム化要素kL+1,ran,(τ,ι)と、前記下位委譲要素生成部が生成した下位委譲要素kL+1,del,(τ,ι)とを含む下位の復号鍵skL+1を下位の委譲装置へ送信する
ことを特徴とする請求項6に記載の暗号処理システム。
【数8】

【数9】

【数10】

【請求項8】
前記第1情報入力部は、t=1,...,Lの各整数tについて述語情報(v:=(vt,i)(i=1,...,n),ρ∈{0,1})を入力し、
前記復号要素生成部は、基底ベクトルb0,pの係数として−sdec,0を設定し、基底ベクトルb0,qの係数として前記Δを設定し、t=1,...,Lの各整数tについての基底ベクトルbt,iの係数として、ρが0の場合にはsdec,tt,1+θdec,tt,i(i=1,...,n)を設定し、ρが1の場合にはsdec,tt,i(i=1,...,n)を設定した復号要素kL,decを生成する
ことを特徴とする請求項2に記載の暗号処理システム。
【請求項9】
前記鍵生成装置は、さらに、
τ=L+1である整数τと、ι=1,...,nτの各整数ιとについて第1委譲要素kL,del,(τ,ι,0)と第2委譲要素kL,del,(τ,ι,1)とを生成する委譲要素生成部であって、
t=1,...,Lの各整数tについての所定の値θdel,0,tと、所定の値ψと、sdel,0,0=Σt=1L+1del,0,tであるようなt=0,...,L+1についての所定の値sdel,0,tとを用いて、基底Bの基底ベクトルb0,pの係数として−sdel,0,0を設定し、t=1,...,Lの各整数tについての基底Bの基底ベクトルbt,i(i=1,...,n)の係数として、ρが0の場合にはsdel,0,tt,1+θdel,0,tt,i(i=1,...,n)を設定し、ρが1の場合にはsdel,0,tt,i(i=1,...,n)を設定し、基底Bτの基底ベクトルbτ,i(i=1,...,nτ)の係数としてsdel,0,L+1τ,1+ψeτ,ι(i=1,...,nτ)を設定して第1委譲要素kL,del,(τ,ι,0)を生成し、
t=1,...,Lの各整数tについての所定の値θdel,1,tと、sdel,1,0=Σt=1L+1del,1,tであるようなt=0,...,L+1についての所定の値sdel,1,tとを用いて、基底Bの基底ベクトルb0,pの係数として−sdel,1,0を設定し、t=1,...,Lの各整数tについての基底Bの基底ベクトルbt,i(i=1,...,n)の係数として、ρが0の場合にはsdel,1,tt,1+θdel,1,tt,i(i=1,...,n)を設定し、ρが1の場合にはsdel,1,tt,i(i=1,...,n)を設定し、基底Bτの基底ベクトルbτ,i(i=1,...,nτ)の係数としてsdel,1,L+1τ,1(i=1,...,nτ)を設定して第2委譲要素kL,del,(τ,ι,1)を生成する委譲要素生成部
を備え、
前記復号鍵送信部は、前記復号要素kL,decと、前記委譲要素生成部が生成した第1委譲要素kL,del,(τ,ι,0)及び第2委譲要素kL,del,(τ,ι,1)とを含む復号鍵skを前記委譲装置へ送信し、
前記鍵委譲装置は、
述語情報(vL+1:=(vL+1,i)(i=1,...,nL+1),ρL+1∈{0,1})を入力する第3情報入力部と、
前記第3情報入力部が入力した述語情報vL+1と、前記復号鍵送信部が送信した復号鍵skとを用いて、数11に示すベクトルを含む下位復号要素kL+1,decを生成する下位復号要素生成部
を備えることを特徴とする請求項8に記載の暗号処理システム。
【数11】

【請求項10】
前記暗号処理システムは、
少なくとも基底ベクトルb0,i(i=1,...,1+n,1+n+1,...,1+n+1+u,...,1+n+1+u+w,...,1+n+1+u+w+z)(n,u,w,zは1以上の整数)を有する基底Bと、
少なくとも基底ベクトルb0,i(i=1,...,1+n,1+n+1,...,1+n+1+u,...,1+n+1+u+w,...,1+n+1+u+w+z)(n,u,w,zは1以上の整数)を有する基底Bと、
少なくとも基底ベクトルbt,i(i=1,...,n,...,n+u,...,n+u+w,...,n+u+w+z)(u,w,zは1以上の整数)を有する基底B(t=1,...,L+1)と、
少なくとも基底ベクトルbt,i(i=1,...,n,...,n+u,...,n+u+w,...,n+u+w+z)を有する基底B(t=1,...,L+1)と
を用いて暗号処理を行い、
前記復号要素生成部は、t=0,...,Lの各整数tについての乱数ηdec,t:=(ηdec,t,i)(i=1,...,w)に基づき、数12に示す復号要素をkL,decを生成し、
前記暗号化データc1生成部は、t=0,...,Lの各整数tについての乱数φ:=(φt,i)(i=1,...,z)に基づき、数13に示す暗号化データcを生成する
ことを特徴とする請求項8に記載の暗号処理システム。
【数12】

【数13】

【請求項11】
前記鍵生成装置は、さらに、
j=1,...,2Lの各整数jについて、第1ランダム化要素kL,ran,jを生成するとともに、τ=L+1,...,d(dはL+1以上の整数)の各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、第2ランダム化要素kL,ran,(τ,ι,0)を生成するランダム化要素生成部であって、
t=1,...,Lの各整数tについての所定の値θran,j,tと、sran,j,0=Σt=1ran,j,tであるようなt=0,...,Lについての所定の値sran,j,tと、t=0,...,Lの各整数tについての乱数ηran,j,t:=(ηran,j,t,i)(i=1,...,w)に基づき、数14に示す第1ランダム化要素kL,ran,jを生成し、
t=1,...,Lの各整数tについての所定の値θran,0,tと、sran,0,0=Σt=1L+1ran,0,tであるようなt=0,...,L+1についての所定の値sran,0,tと、t=0,...,Lの各整数tについての乱数ηran,0,t:=(ηran,0,t,i)(i=1,...,w)と、乱数ηran,0,(τ,ι):=(ηran,0,(τ,ι),i)(i=1,...,w)とに基づき、数15に示す第2ランダム化要素kL,ran,(τ,ι,0)を生成するランダム化要素生成部
を備え、
前記委譲要素生成部は、τ=L+1,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、t=0,...,Lの各整数tについての乱数ηdel,0,t:=(ηdel,0,t,i)(i=1,...,w)と、乱数ηdel,0,(τ,ι):=(ηdel,0,(τ,ι),i)(i=1,...,w)とに基づき、数16に示す第1委譲要素kL,del,(τ,ι,0)を生成するとともに、τ=L+1,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、t=0,...,Lの各整数tについての乱数ηdel,1,t:=(ηdel,1,t,i)(i=1,...,w)と、乱数ηdel,1,(τ,ι):=(ηdel,1,(τ,ι),i)(i=1,...,w)とに基づき、数17に示す第2委譲要素kL,del,(τ,ι,1)を生成し、
前記復号鍵送信部は、前記復号要素kL,decと、前記ランダム化要素生成部が生成した第1ランダム化要素kL,ran,j及び第2ランダム化要素kL,ran,(τ,ι,0)と、前記委譲要素生成部が生成した第1委譲要素kL,del,(τ,ι,0)及び第2委譲要素kL,del,(τ,ι,1)とを含む復号鍵skを前記委譲装置へ送信し、
前記下位復号要素生成部は、前記述語情報vL+1と、前記復号鍵送信部が送信した復号鍵skと、j=1,...,2Lの各整数jについての乱数αdec,jと、乱数σdecと、t=0,...,L+1の各整数tとi=1,...,wの各整数iとについての乱数ηdec,(t,i)とを用いて、数18に示す下位復号要素kL+1,decを生成する
ことを特徴とする請求項10に記載の暗号処理システム。
【数14】

【数15】

【数16】

【数17】

【数18】

【請求項12】
前記委譲装置は、さらに、
j’=1,...,2(L+1)の各整数j’について、第1下位ランダム化要素kL+1,ran,j’を生成するとともに、τ=L+2,...,d(dはL+2以上の整数)の各整数τと、各整数τに関してι=1,...,nτの各整数ιについて、第2下位ランダム化要素kL+1,ran,(τ,ι,0)を生成する下位ランダム化要素生成部であって、
前記述語情報vL+1と、前記復号鍵skと、j=1,...,2Lの各整数jとj’=1,...,2(L+1)の各整数j’とについての乱数αran,j’,jと、j’=1,...,2(L+1)の各整数j’についての乱数σran,j’と、t=0,...,L+1の各整数tとi=1,...,wの各整数iとについての乱数ηran,j’,(t,i)とに基づき、数19に示す第1下位ランダム化要素kL+1,ran,j’を生成し、
前記述語情報vL+1と、前記復号鍵skと、j=1,...,2Lの各整数jについての乱数αran,(τ,ι),jと、乱数σran,(τ,ι,0)と、乱数φran,(τ,ι,0)と、t=0,...,L+1の各整数tとi=1,...,wの各整数iとについてのηran,(τ,ι,0),(t,i)とに基づき、数20に示す第2下位ランダム化要素kL+1,ran,(τ,ι,0)を生成する下位ランダム化要素生成部と、
τ=L+2,...,d(dはL+2以上の整数)の各整数τと、各整数τに関してι=1,...,nτの各整数ιについて、第1下位委譲要素kL+1,del,(τ,ι,0)と第2下位委譲要素kL+1,del,(τ,ι,1)とを生成する下位委譲要素生成部であって、
前記述語情報vL+1と、前記復号鍵skと、j=1,...,2Lの各整数jについての乱数αdel,(τ,ι,0),jと、乱数σdel,(τ,ι,0)と、乱数ψと、乱数φdel,(τ,ι,0)と、t=0,...,L+1の各整数tとi=1,...,wの各整数iとについてのηdel,(τ,ι,0),(t,i)とに基づき、数21に示す第1下位委譲要素kL+1,del,(τ,ι,0)を生成し、
前記述語情報vL+1と、前記復号鍵skと、j=1,...,2Lの各整数jについての乱数αdel,(τ,ι,1),jと、乱数σdel,(τ,ι,1)と、乱数ψと、乱数φdel,(τ,ι,1)と、t=0,...,L+1の各整数tとi=1,...,wの各整数iとについてのηdel,(τ,ι,1),(t,i)とに基づき、数22に示す第2下位委譲要素kL+1,del,(τ,ι,1)を生成する下位委譲要素生成部と
を備える
ことを特徴とする請求項11に記載の暗号処理システム。
【数19】

【数20】

【数21】

【数22】

【請求項13】
t=1,...,L(Lは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を行う暗号処理システムにおいて、復号鍵skを生成する鍵生成装置であり、
t=1,...,Lの各整数tについて述語情報v:=(vt,i)(i=1,...,n)を入力する第1情報入力部と、
前記第1情報入力部が入力した述語情報vと、所定の値Δと、t=1,...,Lの各整数tについての所定の値θdec,tと、sdec,0=Σt=1dec,tであるようなt=0,...,Lの各整数tについての所定の値sdec,tとを用いて、基底Bの基底ベクトルb0,p(pは所定の値)の係数として−sdec,0を設定し、基底Bの基底ベクトルb0,q(qは所定の値)の係数として前記Δを設定し、t=1,...,Lの各整数tについての基底Bの基底ベクトルbt,i(i=1,...,n)の係数としてsdec,tt,1+θdec,tt,i(i=1,...,n)を設定した復号要素kL,decを生成する復号要素生成部と、
前記復号要素生成部が生成した復号要素kL,decを含む復号鍵skを復号装置へ送信する復号鍵送信部と
を備えることを特徴とする鍵生成装置。
【請求項14】
t=1,...,L(Lは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を行う暗号処理システムにおいて、暗号化データctを生成する暗号化装置であり、
t=1,...,Lの少なくとも一部の整数tについて属性情報x:=(xt,i)(i=1,...,n)を入力する第2情報入力部と、
前記第2情報入力部が入力した属性情報xと、所定の値ω,ζとを用いて、基底Bの基底ベクトルb0,p(pは所定の値)の係数として前記ωを設定し、基底Bの基底ベクトルb0,q(qは所定の値)の係数として前記ζを設定し、前記少なくとも一部の整数tについての基底Bの基底ベクトルbt,i(i=1,...,n)の係数としてωxt,i(i=1,...,n)を設定した暗号化データcを生成する暗号化データc1生成部と、
前記暗号化データc1生成部が生成した暗号化データcを含む暗号化データctを復号装置へ送信するデータ送信部と
を備えることを特徴とする暗号化装置。
【請求項15】
t=1,...,L(Lは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を行う暗号処理システムにおいて、暗号化データcを復号鍵skにより復号する復号装置であり、
属性情報x:=(xt,i)(i=1,...,n)と、所定の値ω,ζとを用いて、基底Bの基底ベクトルb0,p(pは所定の値)の係数として前記ωを設定し、基底Bの基底ベクトルb0,q(qは所定の値)の係数として前記ζを設定し、前記少なくとも一部の整数tについての基底Bの基底ベクトルbt,i(i=1,...,n)の係数としてωxt,i(i=1,...,n)を設定した暗号化データcを暗号化装置から受信するデータ受信部と、
述語情報v:=(vt,i)(i=1,...,n)と、所定の値Δと、t=1,...,Lの各整数tについての所定の値θdec,tと、sdec,0=Σt=1dec,tであるようなt=0,...,Lの各整数tについての所定の値sdec,tとを用いて、基底Bの基底ベクトルb0,p(pは所定の値)の係数として−sdec,0を設定し、基底Bの基底ベクトルb0,q(qは所定の値)の係数として前記Δを設定し、t=1,...,Lの各整数tについての基底Bの基底ベクトルbt,i(i=1,...,n)の係数としてsdec,tt,1+θdec,tt,i(i=1,...,n)を設定した復号要素kL,decを含む復号鍵skを鍵生成装置から取得する復号鍵取得部と、
前記データ受信部が受信した暗号化データcと、前記復号鍵取得部が取得した前記復号鍵skに含まれる復号要素kL,decとについて、ペアリング演算e(c,kL,dec)を行い、前記暗号化データcを復号するペアリング演算部と
を備えることを特徴とする復号装置。
【請求項16】
t=1,...,L+1(Lは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を行う暗号処理システムにおいて、復号鍵skの下位の復号鍵skL+1を生成する鍵委譲装置であり、
t=1,...,Lの各整数tについての基底Bの基底ベクトルに述語情報vを埋め込んだベクトルを復号鍵skとして取得する復号鍵取得部と、
前記復号鍵取得部が取得した復号鍵skと、基底BL+1の基底ベクトルに述語情報vL+1を埋め込んだベクトルとに基づき、前記復号鍵skの下位の復号鍵skL+1を生成する委譲鍵生成部と
を備えることを特徴とする鍵委譲装置。
【請求項17】
t=1,...,L+1(Lは1以上の整数)の各整数tについての基底Bと基底Bとを用いた暗号処理方法であり、
暗号化装置が、t=1,...,Lのうち少なくとも一部の整数tについての基底Bの基底ベクトルに属性情報xを埋め込んだベクトルを暗号化データctとして生成する暗号化工程と、
復号装置が、t=1,...,Lの各整数tについての基底Bの基底ベクトルに述語情報vを埋め込んだベクトルを復号鍵skとして、前記暗号化工程で生成した暗号化データctと前記復号鍵skとについて、ペアリング演算を行い前記暗号化データctを復号する復号工程と、
鍵委譲装置が、基底BL+1の基底ベクトルに述語情報を埋め込んだベクトルvL+1と、前記復号工程で使用した復号鍵skとに基づき、前記復号鍵skの下位の復号鍵skL+1を生成する鍵委譲工程と
を備えることを特徴とする暗号処理方法。
【請求項18】
t=1,...,L+1(Lは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理プログラムであり、
t=1,...,Lのうち少なくとも一部の整数tについての基底Bの基底ベクトルに属性情報xを埋め込んだベクトルを暗号化データctとして生成する暗号化処理と、
t=1,...,Lの各整数tについての基底Bの基底ベクトルに述語情報vを埋め込んだベクトルを復号鍵skとして、前記暗号化装置が生成した暗号化データctと前記復号鍵skとについて、ペアリング演算を行い前記暗号化データctを復号する復号処理と、
基底BL+1の基底ベクトルに述語情報を埋め込んだベクトルvL+1と、前記復号処理で使用した復号鍵skとに基づき、前記復号鍵skの下位の復号鍵skL+1を生成する鍵委譲処理と
を備えることを特徴とする暗号処理プログラム。

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


【公開番号】特開2012−163917(P2012−163917A)
【公開日】平成24年8月30日(2012.8.30)
【国際特許分類】
【出願番号】特願2011−26216(P2011−26216)
【出願日】平成23年2月9日(2011.2.9)
【出願人】(000006013)三菱電機株式会社 (33,312)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】