説明

暗号処理システム、鍵生成装置、暗号化装置、復号装置、署名処理システム、署名装置及び検証装置

【課題】多くの暗号機能を有する安全な関数型暗号方式を提供することを目的とする。
【解決手段】スパンプログラムに属性ベクトルの内積を適用することにより、アクセスストラクチャを構成した。このアクセスストラクチャは、スパンプログラムの設計と、属性ベクトルの設計とに自由度があり、アクセス制御の設計に大きな自由度を有する。そして、このアクセスストラクチャに対して秘密分散の概念を用いることで、関数型暗号処理を実現した。

【発明の詳細な説明】
【技術分野】
【0001】
この発明は、関数型暗号(Functional Encryption,FE)方式に関するものである。
【背景技術】
【0002】
非特許文献3−6,10,12,13,15,18には、関数型暗号方式の1つのクラスであるIDベース暗号(Identity−Based Encryption,IBE)方式についての記載がある。また、非特許文献2,7,9,16,19,23−26,28には、関数型暗号方式の1つのクラスである属性ベース暗号(Attribute−Based Encryption,ABE)方式についての記載がある。
【先行技術文献】
【非特許文献】
【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.: Ciphertextpolicy 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.) CRYPTO2001. 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. EUROCRYPT2004, LNCS, Springer−Verlag (2004)
【非特許文献12】Cocks, C.: An identity based encryption scheme based on quadratic residues. In: Honary, B. (ed.) IMAInt. 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 controlof encrypted data. In: ACM Conference on Computer and Communication Security 2006, pp. 89・8, ACM(2006)
【非特許文献17】Groth, J., Sahai, A.: Efficient non−interactive proof systems for bilinear groups. In: Smart, N.P. (ed.)EUROCRYPT 2008. LNCS, vol. 4965, pp. 415・32. Springer Heidelberg (2008)
【非特許文献18】Horwitz, J., Lynn, B.: Towards hierarchical identity−based encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 466・81. Springer Heidelberg (2002)
【非特許文献19】Katz, J., Sahai, A., Waters, B.: Predicate encryption supporting disjunctions, polynomial equations, andinner products. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 146・62. Springer Heidelberg (2008)
【非特許文献20】Lewko, A.B., Waters, B.: Fully secure HIBE with short ciphertexts. ePrint, IACR, http://eprint.iacr.org/2009/482
【非特許文献21】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)
【非特許文献22】Okamoto, T., Takashima, K.: Hierarchical predicate encryption for Inner−Products, In: ASIACRYPT 2009,Springer Heidelberg (2009)
【非特許文献23】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)
【非特許文献24】Pirretti, M., Traynor, P., McDaniel, P., Waters, B.: Secure attribute−based systems. In: ACM Conferenceon Computer and Communication Security 2006, pp. 99・12, ACM, (2006)
【非特許文献25】Sahai, A., Waters, B.: Fuzzy identity−based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS,vol. 3494, pp. 457・73. Springer Heidelberg (2005)
【非特許文献26】Shi, E., Waters, B.: Delegating capability in predicate encryption systems. In: Aceto, L., Damgard, I.,Goldberg, L.A., Halldosson, M.M., Ingofsdotir, A., Walukiewicz, I. (eds.) ICALP (2) 2008. LNCS, vol.5126, pp. 560・78. Springer Heidelberg (2008)
【非特許文献27】Waters, B.: Efficient identity based encryption without random oracles. Eurocrypt 2005, LNCS No. 3152,pp.443・59.Springer Verlag, 2005.
【非特許文献28】Waters, B.: Ciphertext−policy attribute−based encryption: an expressive, efficient, and provably securerealization. ePrint, IACR, http://eprint.iacr.org/2008/290
【非特許文献29】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】
この発明は、多機能な暗号機能を有する安全な関数型暗号方式を提供することを目的とする。
【課題を解決するための手段】
【0005】
この発明に係る暗号処理システムは、
鍵生成装置と暗号化装置と復号装置とを備え、t=0,...,d(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムであり、
前記鍵生成装置は、
i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性ベクトルv:=(vi,i’)(i’=1,...,n,nは1以上の整数)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)と、L行r列(rは1以上の整数)の所定の行列Mとを入力する第1情報入力部と、
r個の要素を有するベクトルf及びwと、前記第1情報入力部が入力した行列Mとに基づき生成される列ベクトルs→T:=(s,...,s:=M・f→Tと、値s:=w・f→Tと、所定の値θ(i=1,...,L)とに基づき、要素kと、i=1,...,Lの各整数iについての要素kとを生成する復号鍵生成部であって、
基底Bの基底ベクトルb0,p(pは所定の値)の係数として前記値−sを設定し、基底ベクトルb0,q(qは前記pとは異なる所定の値)の係数として所定の値κを設定して要素kを生成し、
i=1,...,Lの各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,1の係数としてs+θi,1を設定するとともに、前記識別情報tとi’=2,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてθi,i’を設定して要素kを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tとi’=1,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてsi,i’を設定して要素kを生成する復号鍵生成部と
を備え、
前記暗号化装置は、
t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性ベクトルx:=(xt,i’)(i’=1,...,n,nは1以上の整数)とを有する属性集合Γを入力する第2情報入力部と、
前記第2情報入力部が入力した属性集合Γに基づき、要素cと、前記属性集合Γに含まれる各識別情報tについてについての要素cとを生成する暗号化データ生成部であって、
基底Bの基底ベクトルb0,p(pは前記p)の係数として乱数値δを設定するとともに、基底ベクトルb0,q(qは前記q)の係数として所定の値ζを設定した要素cを生成し、
前記属性集合Γに含まれる各識別情報tについて、基底Bの基底ベクトルbt,i’(i’=1,...,n)の係数として前記乱数値δ倍したxt,i’を設定した要素cとを生成する暗号化データ生成部と
を備え、
前記復号装置は、
前記暗号化データ生成部が生成した要素c及び要素cと、前記属性集合Γとを含む暗号化データcを取得するデータ取得部と、
前記復号鍵生成部が生成した要素k及び要素kと、前記変数ρ(i)とを含む復号鍵skを取得する復号鍵取得部と、
前記データ取得部が取得した暗号化データcに含まれる属性集合Γと、前記復号鍵取得部が取得した復号鍵skに含まれる変数ρ(i)とに基づき、i=1,...,Lの各整数iのうち、変数ρ(i)が肯定形の組(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0となるiと、変数ρ(i)が否定形の組¬(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、αを合計した場合にsとなる補完係数αを計算する補完係数計算部と、
前記暗号化データcに含まれる要素c,要素cと、前記復号鍵skに含まれる要素k,要素kとについて、前記補完係数計算部が特定した集合Iと、前記補完係数計算部が計算した補完係数αとに基づき、数1に示すペアリング演算を行い値K=gζκを計算するペアリング演算部と
を備えることを特徴とする。
【数1】

【発明の効果】
【0006】
この発明に係る暗号処理システムは、スパンプログラム(Span Program)と内積述語とを用いて関数型暗号を実現しており、多機能な暗号機能を実現している。また、従来の関数型暗号方式に比べ、安全性が高い。
【図面の簡単な説明】
【0007】
【図1】行列M^の説明図。
【図2】行列Mδの説明図。
【図3】sの説明図。
【図4】s→Tの説明図。
【図5】Key−Policy関数型暗号方式を実行する暗号処理システム10の構成図。
【図6】Key−Policy関数型暗号方式を実行する暗号処理システム10の機能を示す機能ブロック図。
【図7】Setupアルゴリズムの処理を示すフローチャート。
【図8】KeyGenアルゴリズムの処理を示すフローチャート。
【図9】Encアルゴリズムの処理を示すフローチャート。
【図10】Decアルゴリズムの処理を示すフローチャート。
【図11】Ciphertext−Policy関数型暗号方式のアルゴリズムを実行する暗号処理システム10の構成図。
【図12】Ciphertext−Policy関数型暗号方式を実行する暗号処理システム10の機能を示す機能ブロック図。
【図13】KeyGenアルゴリズムの処理を示すフローチャート。
【図14】Encアルゴリズムの処理を示すフローチャート。
【図15】Decアルゴリズムの処理を示すフローチャート。
【図16】署名処理システム20の構成図。
【図17】署名処理システム20の機能を示す機能ブロック図。
【図18】Setupアルゴリズムの処理を示すフローチャート。
【図19】KeyGenアルゴリズムの処理を示すフローチャート。
【図20】Encアルゴリズムの処理を示すフローチャート。
【図21】Decアルゴリズムの処理を示すフローチャート。
【図22】鍵生成装置100、暗号化装置200、復号装置300、署名装置400、検証装置500のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【0008】
以下、図に基づき、発明の実施の形態を説明する。
以下の説明において、処理装置は後述するCPU911等である。記憶装置は後述するROM913、RAM914、磁気ディスク920等である。通信装置は後述する通信ボード915等である。入力装置は後述するキーボード902、通信ボード915等である。つまり、処理装置、記憶装置、通信装置、入力装置はハードウェアである。
【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の転置行列を表す。
(i=1,...,n)が空間Vのベクトルの要素であるとき、つまり、数110であるとき、数111は、数112によって生成される部分空間を表す。
【数110】

【数111】

【数112】

数113に示す基底Bと基底Bとに対して、数114である。
【数113】

【数114】

【0010】
また、以下の説明において、“nt”が下付き又は上付きで示されている場合、このntはnを意味する。同様に、“Vt”が下付き又は上付きで示されている場合、このVtはVを意味する。同様に、“δi,j”が上付きで示されている場合、このδi,jは、δi,jを意味する。
また、ベクトルを意味する“→”が下付き文字又は上付き文字に付されている場合、この“→”は下付き文字又は上付き文字に上付きで付されていることを意味する。
また、基底を表すB0,Bd+1が下付きで示されている場合、このB0,Bd+1はそれぞれB,Bd+1を表す。同様に、基底を表すB*0,B*d+1が下付きで示されている場合、このB*0,B*d+1はそれぞれB,Bd+1を表す。
【0011】
また、以下の説明において、暗号処理とは、鍵生成処理、暗号化処理、復号処理を含むものであり、署名処理とは、鍵生成処理、署名処理、検証処理を含むものである。
【0012】
実施の形態1.
この実施の形態では、後の実施の形態で説明する「関数型暗号(Functional Encryption)方式」を実現する基礎となる概念と、関数型暗号の1つの構成について説明する。
第1に、関数型暗号について簡単に説明する。
第2に、関数型暗号を実現するための空間である「双対ペアリングベクトル空間(Dual Pairing Vector Spaces,DPVS)」という豊かな数学的構造を有する空間を説明する。
第3に、関数型暗号を実現するための概念を説明する。ここでは、「スパンプログラム(Span Program)」、「属性ベクトルの内積とアクセスストラクチャ」、「秘密分散方式(秘密共有方式)」について説明する。
第4に、この実施の形態に係る「関数型暗号方式」を説明する。この実施の形態では、「Key−Policy関数型暗号(Key−Policy Functional Encryption,KP−FE)方式」について説明する。そこで、まず、「Key−Policy関数型暗号方式」の基本構成について説明する。次に、この「Key−Policy関数型暗号方式」を実現する「暗号処理システム10」の基本構成について説明する。そして、この実施の形態に係る「Key−Policy関数型暗号方式」及び「暗号処理システム10」について詳細に説明する。
【0013】
<第1.関数型暗号方式>
関数型暗号方式は、暗号化鍵(encryption−key,ek)と、復号鍵(decryption−key,dk)との間の関係をより高度化し、より柔軟にした暗号方式である。
関数型暗号方式において、暗号化鍵と復号鍵とは、それぞれ、属性xと属性vとが設定されている。そして、関係Rに対してR(x,v)が成立する場合に限り、復号鍵dk:=(dk,v)は暗号化鍵ek:=(ek,x)で暗号化された暗号文を復号することができる。
関数型暗号方式には、データベースのアクセスコントロール、メールサービス、コンテンツ配布等の様々なアプリケーションが存在する(非特許文献2,7,9,16,19,23−26,28参照)。
【0014】
Rが等号関係である場合、つまり、x=vである場合に限りR(x,v)が成立する場合、関数型暗号方式はIDベース暗号方式である。
【0015】
IDベース暗号方式よりも一般化された関数型暗号方式として、属性ベース暗号方式がある。
属性ベース暗号方式では、暗号化鍵と復号鍵とに設定される属性が属性の組である。例えば、暗号化鍵と復号鍵とに設定される属性が、それぞれ、X:=(x,...,x)と、V:=(v,...,v)とである。
そして、属性のコンポーネントについて、コンポーネント毎の等号関係(例えば、{x=v}t∈{1,...,d})がアクセスストラクチャSに入力される。そして、アクセスストラクチャSが入力を受理した場合にのみ、R(X,V)が成立する。つまり、暗号化鍵で暗号化された暗号文を復号鍵で復号することができる。
アクセスストラクチャSが復号鍵dkに埋め込まれている場合、属性ベース暗号(ABE)方式は、Key−Policy ABE(KP−ABE)と呼ばれる。一方、アクセスストラクチャSが暗号文に埋め込まれている場合、属性ベース暗号(ABE)方式は、Ciphertext−Policy ABE(CP−ABE)と呼ばれる。
【0016】
非特許文献19に記載された内積述語暗号(Inner−Product Encryption,IPE)も関数型暗号の1つのクラスである。ここでは、暗号化鍵と復号鍵とに設定される属性がぞれぞれ体又は環上のベクトルである。例えば、x:=(x,...,x)∈Fとv:=(v,...,v)∈Fとがそれぞれ暗号化鍵と復号鍵とに設定される。そして、x・v=0である場合に限り、R(x,v)が成立する。
【0017】
<第2.双対ペアリングベクトル空間>
まず、対象双線形ペアリング群(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である。
以下の説明において、数115を、1λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータparam:=(q,G,G,g,e)の値を出力するアルゴリズムとする。
【数115】

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

【数117】

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

これは、非退化双線形である。つまり、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である。
【0020】
演算(2):ディストーション写像
数119に示す空間Vにおける線形変換φi,jは、数120を行うことができる。
【数119】

【数120】

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

【0022】
なお、ここでは、上述した対象双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。なお、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。
【0023】
<第3.関数型暗号を実現するための概念>
<第3−1.スパンプログラム>
図1は、行列M^の説明図である。
{p,...,p}を変数の集合とする。M^:=(M,ρ)は、ラベル付けされた行列である。ここで、行列Mは、F上の(L行×r列)の行列である。また、ρは、行列Mの各列に付されたラベルであり、{p,...,p,¬p,...,¬p}のいずれか1つのリテラルへ対応付けられる。なお、Mの全ての行に付されたラベルρi(i=1,...,L)がいずれか1つのリテラルへ対応付けられる。つまり、ρ:{1,...,L}→{p,...,p,¬p,...,¬p}である。
【0024】
全ての入力列δ∈{0,1}に対して、行列Mの部分行列Mδは定義される。行列Mδは、入力列δによってラベルρに値“1”が対応付けられた行列Mの行から構成される部分行列である。つまり、行列Mδは、δ=1であるようなpに対応付けられた行列Mの行と、δ=0であるような¬pに対応付けられた行列Mの行とからなる部分行列である。
図2は、行列Mδの説明図である。なお、図2では、n=7,L=6,r=5としている。つまり、変数の集合は、{p,...,p}であり、行列Mは(6行×5列)の行列である。また、図2において、ラベルρは、ρが¬pに、ρがpに、ρがpに、ρが¬pに、ρが¬pに、ρがpにそれぞれ対応付けられているとする。
ここで、入力列δ∈{0,1}が、δ=1,δ=0,δ=1,δ=0,δ=0,δ=1,δ=1であるとする。この場合、破線で囲んだリテラル(p,p,p,p,¬p,¬p,¬p)に対応付けられている行列Mの行からなる部分行列が行列Mδである。つまり、行列Mの1行目(M),2行目(M),4行目(M)からなる部分行列が行列Mδである。
【0025】
言い替えると、写像γ:{1,...,L}→{0,1}が、[ρ(j)=p]∧[δ=1]又は[ρ(j)=¬p]∧[δ=0]である場合、γ(j)=1であり、他の場合、γ(j)=0であるとする。この場合に、Mδ:=(Mγ(j)=1である。ここで、Mは、行列Mのj番目の行である。
つまり、図2では、写像γ(j)=1(j=1,2,4)であり、写像γ(j)=0(j=3,5,6)である。したがって、(Mγ(j)=1は、M,M,Mであり、行列Mδである。
すなわち、写像γ(j)の値が“0”であるか“1”であるかによって、行列Mのj番目の行が行列Mδに含まれるか否かが決定される。
【0026】
∈span<Mδ>である場合に限り、スパンプログラムM^は入力列δを受理し、他の場合には入力列δを拒絶する。つまり、入力列δによって行列M^から得られる行列Mδの行を線形結合して1が得られる場合に限り、スパンプログラムM^は入力列δを受理する。なお、1とは、各要素が値“1”である行ベクトルである。
例えば、図2の例であれば、行列Mの1,2,4行目からなる行列Mδの各行を線形結合して1が得られる場合に限り、スパンプログラムM^は入力列δを受理する。つまり、α(M)+α(M)+α(M)=1となるα,α,αが存在する場合には、スパンプログラムM^は入力列δを受理する。
【0027】
ここで、ラベルρが正のリテラル{p,...,p}にのみ対応付けられている場合、スパンプログラムはモノトーンと呼ばれる。一方、ラベルρがリテラル{p,...,p,¬p,...,¬p}に対応付けられている場合、スパンプログラムはノンモノトーンと呼ばれる。ここでは、スパンプログラムはノンモノトーンとする。そして、ノンモノトーンスパンプログラムを用いて、アクセスストラクチャ(ノンモノトーンアクセスストラクチャ)を構成する。アクセスストラクチャとは、簡単に言うと暗号へのアクセス制御を行うものである。つまり、暗号文を復号できるか否かの制御を行うものである。
詳しくは後述するが、スパンプログラムがモノトーンではなく、ノンモノトーンであることにより、スパンプログラムを利用して構成する関数型暗号方式の利用範囲が広がる。
【0028】
<第3−2.属性ベクトルの内積とアクセスストラクチャ>
ここでは、属性ベクトルの内積を用いて上述した写像γ(j)を計算する。つまり、属性ベクトルの内積を用いて、行列Mのどの行を行列Mδに含めるかを決定する。
【0029】
(t=1,...,dでありU⊂{0,1})は、部分全集合(sub−universe)であり、属性の集合である。そして、Uは、それぞれ部分全集合の識別情報(t)と、n次元ベクトル(v)とを含む。つまり、Uは、(t,v)である。ここで、t∈{1,...,d}であり、v∈Fntである。
【0030】
:=(t,v)をスパンプログラムM^:=(M,ρ)における変数pとする。つまり、p:=(t,v)である。そして、変数(p:=(t,v),(t’,v’),...)としたスパンプログラムM^:=(M,ρ)をアクセスストラクチャSとする。
つまり、アクセスストラクチャS:=(M,ρ)であり、ρ:{1,...,L}→{(t,v),(t’,v’)},...,¬(t,v),¬(t’,v’),...}である。
【0031】
次に、Γを属性の集合とする。つまり、Γ:={(t,x)|x∈Fqnt,1≦t≦d}である。
アクセスストラクチャSにΓが与えられた場合、スパンプログラムM^:=(M,ρ)に対する写像γ:{1,...,L}→{0,1}は、以下のように定義される。i=1,...,Lの各整数iについて、[ρ(i)=(t,v)]∧[(t,x)∈Γ]∧[v・x=0]、又は、[ρ(i)=¬(t,v)]∧[(t,x)∈Γ]∧[v・x≠0]である場合、γ(j)=1であり、他の場合、γ(j)=0とする。
つまり、属性ベクトルvとxとの内積に基づき、写像γが計算される。そして、上述したように、写像γにより、行列Mのどの行を行列Mδに含めるかが決定される。すなわち、属性ベクトルvとxとの内積により、行列Mのどの行を行列Mδに含めるかが決定され、1∈span<(Mγ(i)=1>である場合に限り、アクセスストラクチャS:=(M,ρ)はΓを受理する。
【0032】
<第3−3.秘密分散方式>
アクセスストラクチャS:=(M,ρ)に対する秘密分散方式について説明する。
なお、秘密分散方式とは、秘密情報を分散させ、意味のない分散情報にすることである。例えば、秘密情報sを10個に分散させ、10個の分散情報を生成する。ここで、10個の分散情報それぞれは、秘密情報sの情報を有していない。したがって、ある1個の分散情報を手に入れても秘密情報sに関して何ら情報を得ることはできない。一方、10個の分散情報を全て手に入れれば、秘密情報sを復元できる。
また、10個の分散情報を全て手に入れなくても、一部だけ(例えば、8個)手に入れれば秘密情報sを復元できる秘密分散方式もある。このように、10個の分散情報のうち8個で秘密情報sを復元できる場合を、8−out−of−10と呼ぶ。つまり、n個の分散情報のうちt個で秘密情報sを復元できる場合を、t−out−of−nと呼ぶ。このtを閾値と呼ぶ。
また、d,...,d10の10個の分散情報を生成した場合に、d,...,dまでの8個の分散情報であれば秘密情報sを復元できるが、d,...,d10までの8個の分散情報であれば秘密情報sを復元できないというような秘密分散方式もある。つまり、手に入れた分散情報の数だけでなく、分散情報の組合せに応じて秘密情報sを復元できるか否かを制御する秘密分散方式もある。
【0033】
図3は、sの説明図である。図4は、s→Tの説明図である。
行列Mを(L行×r列)の行列とする。f→Tを数122に示す列ベクトルとする。
【数122】

数123に示すsを共有される秘密情報とする。
【数123】

また、数124に示すs→TをsのL個の分散情報のベクトルとする。
【数124】

そして、分散情報sをρ(i)に属するものとする。
【0034】
アクセスストラクチャS:=(M,ρ)がΓを受理する場合、つまりγ:{1,...,L}→{0,1}について1∈span<(Mγ(i)=1>である場合、I⊆{i∈{1,...,L}|γ(i)-=1}である定数{α∈F|i∈I}が存在する。
これは、図2の例で、α(M)+α(M)+α(M)=1となるα,α,αが存在する場合には、スパンプログラムM^は入力列δを受理すると説明したことからも明らかである。つまり、α(M)+α(M)+α(M)=1となるα,α,αが存在する場合には、スパンプログラムM^は入力列δを受理するのであれば、スパンプログラムM^は入力列δを受理する場合には、α(M)+α(M)+α(M)=1となるα,α,αが存在する。
そして、数125である。
【数125】

なお、定数{α}は、行列Mのサイズにおける多項式時間で計算可能である。
【0035】
この実施の形態及び以下の実施の形態に係る関数型暗号方式は、上述したように、スパンプログラムに内積述語と秘密分散方式とを適用してアクセスストラクチャを構成する。そのため、スパンプログラムにおける行列Mや、内積述語における属性情報x及び属性情報v(述語情報)を設計するにより、アクセス制御を自由に設計することができる。つまり、非常に高い自由度でアクセス制御の設計を行うことができる。なお、行列Mの設計は、秘密分散方式の閾値等の条件設計に相当する。
例えば、上述した属性ベース暗号方式は、この実施の形態及び以下の実施の形態に係る関数型暗号方式におけるアクセスストラクチャにおいて、内積述語の設計をある条件に限定した場合に相当する。つまり、この実施の形態及び以下の実施の形態に係る関数型暗号方式におけるアクセスストラクチャに比べ、属性ベース暗号方式におけるアクセスストラクチャは、内積述語における属性情報x及び属性情報v(述語情報)を設計の自由度がない分、アクセス制御の設計の自由度が低い。なお、具体的には、属性ベース暗号方式は、属性情報{xt∈{1,...,d}と{vt∈{1,...,d}とを、等号関係に対する2次元ベクトル、例えばx:=(1,x)とv:=(v,−1)とに限定した場合に相当する。
また、上述した内積述語暗号方式は、この実施の形態及び以下の実施の形態に係る関数型暗号方式におけるアクセスストラクチャにおいて、スパンプログラムにおける行列Mの設計をある条件に限定した場合に相当する。つまり、この実施の形態及び以下の実施の形態に係る関数型暗号方式におけるアクセスストラクチャに比べ、内積述語暗号方式におけるアクセスストラクチャは、スパンプログラムにおける行列Mの設計の自由度がない分、アクセス制御の設計の自由度が低い。なお、具体的には、内積述語暗号方式は、秘密分散方式を1−out−of−1(あるいは、d−out−of−d)に限定した場合である。
【0036】
特に、この実施の形態及び以下の実施の形態に係る関数型暗号方式におけるアクセスストラクチャは、ノンモノトーンスパンプログラムを用いたノンモノトーンアクセスストラクチャを構成する。そのため、アクセス制御の設計の自由度がより高くなる。
具体的には、ノンモノトーンスパンプログラムには、否定形のリテラル(¬p)を含むため、否定形の条件を設定できる。例えば、第1会社には、A部とB部とC部とD部との4つの部署があったとする。ここで、第1会社のB部以外の部署の属するユーザにのみアクセス可能(復号可能)というアクセス制御をしたいとする。この場合に、否定形の条件の設定ができないとすると、「第1会社のA部とC部とD部とのいずれかに属すること」という条件を設定する必要がある。一方、否定形の条件の設定ができるとすると、「第1会社の社員であって、B部以外に属すること」という条件を設定することができる。つまり、否定形の条件が設定できることで、自然な条件設定が可能となる。なお、ここでは部署の数が少ないが、部署の数が多い場合等は非常に有効であることが分かる。
【0037】
<第4.関数型暗号方式の基本構成>
<第4−1.Key−Policy関数型暗号方式の基本構成>
Key−Policy関数型暗号方式の構成を簡単に説明する。なお、Key−Policyとは、復号鍵にPolicyが埋め込まれること、つまりアクセスストラクチャが埋め込まれることを意味する。
Key−Policy関数型暗号方式は、Setup、KeyGen、Enc、Decの4つのアルゴリズムを備える。
(Setup)
Setupアルゴリズムは、セキュリティパラメータλと、属性のフォーマットμ:=(d;n,...,n)とが入力され、公開パラメータpkと、マスター鍵skとを出力する確率的アルゴリズムである。
(KeyGen)
KeyGenアルゴリズムは、アクセスストラクチャS:=(M,ρ)と、公開パラメータpkと、マスター鍵skとを入力として、復号鍵skを出力する確率的アルゴリズムである。
(Enc)
Encアルゴリズムは、メッセージmと、属性の集合であるΓ:={(t,x)|x∈Fnt,1≦t≦d}と、公開パラメータpkとを入力として、暗号化データcを出力する確率的アルゴリズムである。
(Dec)
Decアルゴリズムは、属性の集合であるΓの下で暗号化された暗号化データcと、アクセスストラクチャSに対する復号鍵skと、公開パラメータpkとを入力として、メッセージm、又は、識別情報⊥を出力するアルゴリズムである。
【0038】
Key−Policy関数型暗号方式は、全てのアクセスストラクチャSと属性の集合Γと、正しく生成された公開パラメータpkとマスター鍵skと数126に示す暗号文cとに対して、アクセスストラクチャSが属性の集合Γを受理する場合、m=Dec(pk,sk,c)であり、アクセスストラクチャSが属性の集合Γを拒絶する場合、m=Dec(pk,sk,c)となる確率は無視し得る程度である。
【数126】

【0039】
<第4−2.暗号処理システム10>
上述したKey−Policy関数型暗号方式のアルゴリズムを実行する暗号処理システム10について説明する。
図5は、Key−Policy関数型暗号方式を実行する暗号処理システム10の構成図である。
暗号処理システム10は、鍵生成装置100、暗号化装置200、復号装置300を備える。
鍵生成装置100は、セキュリティパラメータλと、属性のフォーマットμ:=(d;n,...,n)とを入力としてSetupアルゴリズムを実行して、公開パラメータpkとマスター鍵skとを生成する。そして、鍵生成装置100は、生成した公開パラメータpkを公開する。また、鍵生成装置100は、アクセスストラクチャSを入力としてKeyGenアルゴリズムを実行して、復号鍵skを生成して復号装置300へ秘密裡に配布する。
暗号化装置200は、メッセージmと、属性の集合Γと、公開パラメータpkとを入力としてEncアルゴリズムを実行して、暗号化データcを生成する。暗号化装置200は、生成した暗号化データcを復号装置300へ送信する。
復号装置300は、公開パラメータpkと、復号鍵skと、暗号化データcとを入力としてDecアルゴリズムを実行して、メッセージm又は識別情報⊥を出力する。
【0040】
<第4−3.Key−Policy関数型暗号方式及び暗号処理システム10の詳細>
図6から図9に基づき、Key−Policy関数型暗号方式、及び、Key−Policy関数型暗号方式を実行する暗号処理システム10の機能と動作とについて説明する。
図6は、Key−Policy関数型暗号方式を実行する暗号処理システム10の機能を示す機能ブロック図である。暗号処理システム10は、上述したように、鍵生成装置100、暗号化装置200、復号装置300を備える。
図7と図8とは、鍵生成装置100の動作を示すフローチャートである。なお、図7はSetupアルゴリズムの処理を示すフローチャートであり、図8はKeyGenアルゴリズムの処理を示すフローチャートである。図9は、暗号化装置200の動作を示すフローチャートであり、Encアルゴリズムの処理を示すフローチャートである。図10は、復号装置300の動作を示すフローチャートであり、Decアルゴリズムの処理を示すフローチャートである。
なお、以下の説明では、xt,1:=1であるとする。
【0041】
鍵生成装置100の機能と動作とについて説明する。鍵生成装置100は、マスター鍵生成部110、マスター鍵記憶部120、情報入力部130(第1情報入力部)、復号鍵生成部140、鍵配布部150を備える。また、復号鍵生成部140は、fベクトル生成部141、sベクトル生成部142、乱数生成部143、鍵要素生成部144を備える。
【0042】
まず、図7に基づき、Setupアルゴリズムの処理について説明する。
(S101:正規直交基底生成ステップ)
マスター鍵生成部110は、処理装置により、数127を計算して、paramμ→と、t=0,...,dの各整数tについて基底B及び基底Bとを生成する。
【数127】

【0043】
つまり、マスター鍵生成部110は以下の処理を実行する。
(1)マスター鍵生成部110は、入力装置により、セキュリティパラメータλ(1λ)と、属性のフォーマットμ:=(d;n,...,n)とを入力する。ここで、dは1以上の整数であり、t=1,...,dまでの各整数tについてnは1以上の整数である。
(2)マスター鍵生成部110は、処理装置により、(1)で入力したセキュリティパラメータλ(1λ)を入力としてアルゴリズムGbpgを実行して、双線形ペアリング群のパラメータparam:=(q,G,G,g,e)の値を生成する。
(3)マスター鍵生成部110は、処理装置により、乱数ψを生成するとともに、Nに5を、t=1,...,dの各整数tについてNに4nを設定する。
【0044】
続いて、マスター鍵生成部110は、t=0,...,dの各整数tについて以下の(4)から(8)までの処理を実行する。
(4)マスター鍵生成部110は、処理装置により、(1)で入力したセキュリティパラメータλ(1λ)と、(3)で設定した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は、paramμ→に(4)で生成した{paramVtt=0,...,dと、gとを設定する。なお、t=0,...,dとi=1,...,Nとの各整数t,iについて、g=e(bt,i,bt,i)である。
【0045】
すなわち、(S101)で、マスター鍵生成部110は、数128に示すアルゴリズムGobを実行して、paramμ→と、t=0,...,dの各整数tについて基底B及び基底Bとを生成する。
【数128】

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

マスター鍵生成部110は、生成した部分基底B^及び部分基底B^と、(S101)で入力されたセキュリティパラメータλ(1λ)と、(S101)で生成したparamμ→とを合わせて、公開パラメータpkとする。
【0047】
(S103:マスター鍵生成ステップ)
マスター鍵生成部110は、処理装置により、(S101)で生成した基底Bの部分基底B^と、t=1,...,dの各整数tについて、部分基底B^とを数130に示すように生成する。
【数130】

マスター鍵生成部110は、生成した部分基底B^と部分基底B^とをマスター鍵skとする。
【0048】
(S104:マスター鍵記憶ステップ)
マスター鍵記憶部120は、(S102)でt=0,...,dの各整数tについて生成した部分基底B^を含む公開パラメータpkを記憶装置に記憶する。また、マスター鍵記憶部120は、(S103)でt=0,...,dの各整数tについて生成した部分基底B^を含むマスター鍵skを記憶装置に記憶する。
【0049】
つまり、(S101)から(S103)において、マスター鍵生成部110は数131に示すSetupアルゴリズムを実行して、公開パラメータpkとマスター鍵skとを生成する。そして、(S104)で、マスター鍵記憶部120が生成された公開パラメータpkとマスター鍵skとを記憶装置に記憶する。
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置200や復号装置300が取得可能な状態にされる。
【数131】

【0050】
次に、図8に基づき、KeyGenアルゴリズムの処理について説明する。
(S201:情報入力ステップ)
情報入力部130は、入力装置により、上述したアクセスストラクチャS:=(M,ρ)を入力する。なお、アクセスストラクチャSの行列Mの設定については、実現したいシステムの条件に応じて設定されるものである。また、アクセスストラクチャSのρは、例えば、復号鍵skの使用者の属性情報が設定されている。
【0051】
(S202:fベクトル生成ステップ)
fベクトル生成部141は、処理装置により、r個の要素を有するベクトルfを数132に示すようにランダムに生成する。
【数132】

【0052】
(S203:sベクトル生成ステップ)
sベクトル生成部142は、処理装置により、(S201)で入力したアクセスストラクチャSに含まれる(L行×r列)の行列Mと、(S202)で生成したベクトルfとに基づき、ベクトルs→T:=(s,...,sを数133に示すように生成する。
【数133】

また、sベクトル生成部142は、処理装置により、(S202)で生成したベクトルfに基づき、値sを数134に示すように生成する。
【数134】

【0053】
(S204:乱数生成ステップ)
乱数生成部143は、処理装置により、乱数ηと、i=1,...,Lの各整数iについて、乱数θとを数135に示すように生成する。
【数135】

【0054】
(S205:鍵要素生成ステップ)
鍵要素生成部144は、処理装置により、復号鍵skの要素kを数136に示すように生成する。
【数136】

なお、上述したように、数113に基底Bと基底Bとに対して、数114である。したがって、数136は、基底Bの基底ベクトルb0,1の係数として−sを設定し、基底ベクトルb0,2の係数として0を設定し、基底ベクトルb0,3の係数として1を設定し、基底ベクトルb0,4の係数としてηを設定し、基底ベクトルb0,5の係数として0を設定することを意味する。
また、鍵要素生成部144は、処理装置により、i=1,...,Lの各整数iについて、復号鍵skの要素kを数137に示すように生成する。
【数137】

つまり、数137は、数136と同様に、ρ(i)が肯定形の組(t,v)である場合には、基底Bの基底ベクトルbt,1の係数としてs+θi,1を設定し、基底ベクトルbt,2,...,bt,ntの係数としてθi,2,...,θi,ntを設定し、基底ベクトルbt,nt+1,...,bt,2ntの係数として0を設定し、基底ベクトルbt,2nt+1,...,bt,3ntの係数としてηi,1,...,ηi,ntを設定し、基底ベクトルbt,3nt+1,...,bt,4ntの係数として0を設定することを意味する。
一方、ρ(i)が否定形の組¬(t,v)である場合には、基底Bの基底ベクトルbt,1,...,bt,ntの係数としてsi,1,...,si,ntを設定し、基底ベクトルbt,nt+1,...,bt,2ntの係数として0を設定し、基底ベクトルbt,2nt+1,...,bt,3ntの係数としてηi,1,...,ηi,ntを設定し、基底ベクトルbt,3nt+1,...,bt,4ntの係数として0を設定することを意味する。
【0055】
(S206:鍵配布ステップ)
鍵配布部150は、(S201)で入力したアクセスストラクチャSと、(S205)で生成されたk,k,...,kとを要素とする復号鍵skを、例えば通信装置によりネットワークを介して秘密裡に復号装置300へ配布する。もちろん、復号鍵skは、他の方法により復号装置300へ配布されてもよい。
【0056】
つまり、(S201)から(S205)において、情報入力部130と復号鍵生成部140とは数138に示すKeyGenアルゴリズムを実行して、復号鍵skを生成する。そして、(S206)で、鍵配布部150が生成された復号鍵skを復号装置300へ配布する。
【数138】

【0057】
暗号化装置200の機能と動作とについて説明する。暗号化装置200は、公開パラメータ取得部210、情報入力部220(第2情報入力部)、暗号化データ生成部230、データ送信部240(データ出力部)を備える。また、暗号化データ生成部230は、乱数生成部231、暗号要素生成部232を備える。
【0058】
図9に基づき、Encアルゴリズムの処理について説明する。
(S301:公開パラメータ取得ステップ)
公開パラメータ取得部210は、例えば、通信装置によりネットワークを介して、鍵生成装置100が生成した公開パラメータpkを取得する。
【0059】
(S302:情報入力ステップ)
情報入力部220は、入力装置により、復号装置300へ送信するメッセージmを入力する。また、情報入力部220は、入力装置により、属性の集合Γ:={(t,x:=(xt,1,...,xt,nt∈Fqnt))|1≦t≦d}を入力する。なお、tは、1以上d以下の全ての整数ではなく、1以上d以下の少なくとも一部の整数であってもよい。また、属性の集合Γは、例えば、復号可能なユーザの属性情報が設定されている。
【0060】
(S303:乱数生成ステップ)
乱数生成部231は、処理装置により、乱数δ、乱数φ,φt,1,...,φt,nt,ζを数139に示すように生成する。
【数139】

【0061】
(S304:cベクトル生成ステップ)
暗号要素生成部232は、処理装置により、暗号化データcの要素cを数140に示すように生成する。
【数140】

また、暗号要素生成部232は、処理装置により、Γに含まれる(t,x)の各整数tについて、暗号化データcの要素cを数141に示すように生成する。
【数141】

また、暗号要素生成部232は、処理装置により、暗号化データcの要素cd+1を数142に示すように生成する。
【数142】

【0062】
(S305:データ送信ステップ)
データ送信部240は、(S302)で入力した属性の集合Γと、(S304)で生成されたc,c,cd+1とを要素とする暗号化データcを、例えば通信装置によりネットワークを介して復号装置300へ送信する。もちろん、暗号化データcは、他の方法により復号装置300へ送信されてもよい。
【0063】
つまり、(S301)から(S304)において、公開パラメータ取得部210、情報入力部220、暗号化データ生成部230は、数143に示すEncアルゴリズムを実行して、暗号化データcを生成する。そして、(S305)で、データ送信部240が生成された暗号化データcを復号装置300へ送信する。
【数143】

【0064】
復号装置300の機能と動作とについて説明する。復号装置300は、復号鍵取得部310、データ受信部320(データ取得部)、スパンプログラム計算部330、補完係数計算部340、ペアリング演算部350、平文情報計算部360を備える。
【0065】
図10に基づき、Decアルゴリズムの処理について説明する。
(S401:復号鍵取得ステップ)
復号鍵取得部310は、例えば、通信装置によりネットワークを介して、鍵生成装置100から配布された復号鍵sk:=(S,k,k,...,k)を取得する。また、復号鍵取得部310は、鍵生成装置100が生成した公開パラメータpkを取得する。
【0066】
(S402:データ受信ステップ)
データ受信部320は、例えば、通信装置によりネットワークを介して、暗号化装置200が送信した暗号化データcを受信する。
【0067】
(S403:スパンプログラム計算ステップ)
スパンプログラム計算部330は、処理装置により、(S401)で取得した復号鍵skに含まれるアクセスストラクチャSが、(S402)で受信した暗号化データcに含まれるΓを受理するか否かを判定する。アクセスストラクチャSがΓを受理するか否かの判定方法は、「第3.関数型暗号を実現するための概念」で説明した通りである。
スパンプログラム計算部330は、アクセスストラクチャSがΓを受理する場合(S403で受理)、処理を(S404)へ進める。一方、アクセスストラクチャSがΓを拒絶する場合(S403で拒絶)、暗号化データcを復号鍵skで復号できないとして処理を終了する。
【0068】
(S404:補完係数計算ステップ)
補完係数計算部340は、処理装置により、数144となるIと、定数(補完係数){αi∈Iとを計算する。
【数144】

【0069】
(S405:ペアリング演算ステップ)
ペアリング演算部350は、処理装置により、数145を計算して、セッション鍵K=gζを生成する。
【数145】

なお、数146に示すように、数145を計算することにより鍵K=gζが得られる。
【数146】

【0070】
(S406:平文情報計算ステップ)
平文情報計算部360は、処理装置により、m’=cd+1/Kを計算して、メッセージm’(=m)を生成する。なお、cd+1は数142に示す通りgζmであり、Kはgζであるから、m’=cd+1/Kを計算すればメッセージmが得られる。
【0071】
つまり、(S401)から(S406)において、公開パラメータ取得部210、情報入力部220、暗号化データ生成部230は、数147に示すDecアルゴリズムを実行して、メッセージm’(=m)を生成する。
【数147】

【0072】
以上のように、暗号処理システム10は、スパンプログラムと内積述語と秘密分散とを用いて構成したアクセスストラクチャSを用いて、暗号方式(関数型暗号方式)を実現する。したがって、暗号処理システム10は、非常に高い自由度でアクセス制御の設計を行うことが可能な暗号方式を実現する。
また、暗号処理システム10が実現する暗号方式は、非常に安全性が高い。上述したように、関数型暗号方式の1つのクラス(最も限定したクラス)にIDベース暗号がある。既存の実用的なIDベース暗号と比較しても、暗号処理システム10が実現する暗号方式はある意味において安全性が高い。
【0073】
なお、上記説明では、(S101)の(3)でNを5に、Nを4n(=n+n+n+n)に設定した。したがって、基底A、基底B、基底Bは、いずれも4n+5次元である。
しかし、n+n+n+nをn+u+w+zにしてもよい。つまり、1つ目のnをそのままnとし、2つ目のnをuとし、3つ目のnをwとし、4つ目のnをzとしてもよい。すなわち、Nをn+u+w+zに設定してもよい。ここで、n,u,w,zは、それぞれ異なる値であってもよく、nは上述したように1以上の整数であり、u,w,zはいずれも0以上の整数である。
この場合、数131に示すSetupアルゴリズムは、数148のように書き換えられる。つまり、基底B^と基底B^の基底ベクトルの添え字が変更される。
【数148】

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

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

なお、数147に示すDecアルゴリズムには変更はない。
【0074】
また、Nは5ではなく、2以上の整数であればよい。Nが2であると、基底Bと基底Bとが2次元になる。この場合、KeyGenアルゴリズムにおいて、k:=(−s,1)B*0とし、Encアルゴリズムにおいて、c:=(δ,ζ)B0とすればよい。
【0075】
また、上記説明では、KeyGenアルゴリズムにおいて、k:=(−s,0,1,η,0)B*0とした。しかし、所定の値κを用いて、k:=(−s,0,κ,η,0)B*0としてもよい。この場合、Decアルゴリズムで計算されるK:=gζκとなるため、Encアルゴリズムにおいて、cd+1:=gζκmとすればよい。
【0076】
また、上記説明では、vi,ntの値について特に限定しなかった。しかし、安全性の証明の観点から、vi,nt:=1である限定としてもよい。
【0077】
また、安全性の証明の観点から、i=1,...,Lの各整数iについてのρ(i)は、それぞれ異なる識別情報tについての肯定形の組(t,v)又は否定形の組¬(t,v)であると限定してもよい。
言い替えると、ρ(i)=(t,v)又はρ(i)=¬(t,v)である場合に、関数ρを、ρ(i)=tである{1,...,L}→{1,...d}の写像であるとする。この場合、ρが単射であると限定してもよい。なお、ρ(i)は、上述したアクセスストラクチャS:=(M,ρ(i))のρ(i)である。
【0078】
実施の形態2.
この実施の形態では、「Ciphertext−Policy関数型暗号(Ciphertext−Policy Functional Encryption,CP−FE)方式」について説明する。なお、この実施の形態で説明する「Ciphertext−Policy関数型暗号方式」も、実施の形態1で説明した概念に基づき構成される。
この実施の形態では、まず、「Ciphertext−Policy関数型暗号方式」の基本構成について説明する。次に、この「Ciphertext−Policy関数型暗号方式」を実現する「暗号処理システム10」の基本構成について説明する。そして、この実施の形態に係る「Ciphertext−Policy関数型暗号方式」及び「暗号処理システム10」について詳細に説明する。
【0079】
<Ciphertext−Policy関数型暗号方式の基本構成>
Ciphertext−Policy関数型暗号方式の構成を簡単に説明する。なお、Ciphertext−Policyとは、暗号文にPolicyが埋め込まれること、つまりアクセスストラクチャが埋め込まれることを意味する。
Ciphertext−Policy関数型暗号方式は、Key−Policy関数型暗号方式と同様に、Setup、KeyGen、Enc、Decの4つのアルゴリズムを備える。
(Setup)
Setupアルゴリズムは、セキュリティパラメータλと、属性のフォーマットμ:=(d;n,...,n)とが入力され、公開パラメータpkと、マスター鍵skとを出力する確率的アルゴリズムである。
(KeyGen)
KeyGenアルゴリズムは、属性の集合であるΓ:={(t,x)|x∈Fnt,1≦t≦d}と、公開パラメータpkと、マスター鍵skとを入力として、復号鍵skΓを出力する確率的アルゴリズムである。
(Enc)
Encアルゴリズムは、メッセージmと、アクセスストラクチャS:=(M,ρ)と、公開パラメータpkとを入力として、暗号化データcを出力する確率的アルゴリズムである。
(Dec)
Decアルゴリズムは、アクセスストラクチャSの下で暗号化された暗号化データcと、属性の集合であるΓに対する復号鍵skΓと、公開パラメータpkとを入力として、メッセージm、又は、識別情報⊥を出力するアルゴリズムである。
【0080】
Ciphertext−Policy関数型暗号方式は、全てのアクセスストラクチャSと属性の集合Γと、正しく生成された公開パラメータpkとマスター鍵skと数151に示す暗号文cとに対して、アクセスストラクチャSが属性の集合Γを受理する場合、m=Dec(pk,skΓ,c)であり、アクセスストラクチャSが属性の集合Γを拒絶する場合、m=Dec(pk,skΓ,c)となる確率は無視し得る程度である。
【数151】

【0081】
<暗号処理システム10>
上述したCiphertext−Policy関数型暗号方式のアルゴリズムを実行する暗号処理システム10について説明する。
図11は、暗号処理システム10の構成図である。
暗号処理システム10は、鍵生成装置100、暗号化装置200、復号装置300を備える。
鍵生成装置100は、セキュリティパラメータλと、属性のフォーマットμ:=(d;n,...,n)とを入力としてSetupアルゴリズムを実行して、公開パラメータpkとマスター鍵skとを生成する。そして、鍵生成装置100は、生成した公開パラメータpkを公開する。また、鍵生成装置100は、属性の集合Γを入力としてKeyGenアルゴリズムを実行して、復号鍵skΓを生成して復号装置300へ秘密裡に配布する。
暗号化装置200は、メッセージmと、アクセスストラクチャSと、公開パラメータpkとを入力としてEncアルゴリズムを実行して、暗号化データcを生成する。暗号化装置200は、生成した暗号化データcを復号装置300へ送信する。
復号装置300は、公開パラメータpkと、復号鍵skと、暗号化データcとを入力としてDecアルゴリズムを実行して、メッセージm又は識別情報⊥を出力する。
【0082】
<Ciphertext−Policy関数型暗号方式及び暗号処理システム10の詳細>
図12から図15に基づき、Ciphertext−Policy関数型暗号方式、及び、Ciphertext−Policy関数型暗号方式を実行する暗号処理システム10の機能と動作とについて説明する。
図12は、Ciphertext−Policy関数型暗号方式を実行する暗号処理システム10の機能を示す機能ブロック図である。暗号処理システム10は、上述したように、鍵生成装置100、暗号化装置200、復号装置300を備える。
図13は、鍵生成装置100の動作を示すフローチャートであり、KeyGenアルゴリズムの処理を示すフローチャートである。なお、Setupアルゴリズムは、Key−Policy関数型暗号方式の場合と同様であるため、ここのでは説明を省略する。図14は、暗号化装置200の動作を示すフローチャートであり、Encアルゴリズムの処理を示すフローチャートである。図15は、復号装置300の動作を示すフローチャートであり、Decアルゴリズムの処理を示すフローチャートである。
なお、以下の説明では、xt,1:=1であるとする。
【0083】
鍵生成装置100の機能と動作とについて説明する。鍵生成装置100は、マスター鍵生成部110、マスター鍵記憶部120、情報入力部130(第1情報入力部)、復号鍵生成部140、鍵配布部150を備える。また、復号鍵生成部140は、乱数生成部143、鍵要素生成部144を備える。
【0084】
上述したように、Setupアルゴリズムは、Key−Policy関数型暗号方式の場合と同様であり、数131に示す通りである。
【0085】
図13に基づき、KeyGenアルゴリズムの処理について説明する。
(S501:情報入力ステップ)
情報入力部130は、入力装置により、属性の集合Γ:={(t,x:=(xt,1,...,xt,nt∈Fnt))|1≦t≦d}を入力する。なお、属性の集合Γは、例えば、復号鍵skΓの使用者の属性情報が設定されている。
【0086】
(S502:乱数生成ステップ)
乱数生成部143は、処理装置により、乱数δ、乱数φ,φt,1,...,φt,ntを数152に示すように生成する。
【数152】

【0087】
(S503:鍵要素生成ステップ)
鍵要素生成部144は、処理装置により、復号鍵skΓの要素kを数153に示すように生成する。
【数153】

また、鍵要素生成部144は、処理装置により、Γに含まれる(t,x)の各整数tについて、復号鍵skΓの要素kを数154に示すように生成する。
【数154】

【0088】
(S504:鍵配布ステップ)
鍵配布部150は、(S501)で入力した属性の集合Γと、(S503)で生成されたk,kとを要素とする復号鍵skΓを、例えば通信装置によりネットワークを介して秘密裡に復号装置300へ配布する。もちろん、復号鍵skΓは、他の方法により復号装置300へ配布されてもよい。
【0089】
つまり、(S501)から(S503)において、情報入力部130と復号鍵生成部140とは数155に示すKeyGenアルゴリズムを実行して、復号鍵skΓを生成する。そして、(S504)で、鍵配布部150が生成された復号鍵skΓを復号装置300へ配布する。
【数155】

【0090】
暗号化装置200の機能と動作とについて説明する。暗号化装置200は、公開パラメータ取得部210、情報入力部220(第2情報入力部)、暗号化データ生成部230、データ送信部240(データ出力部)を備える。また、暗号化データ生成部230は、乱数生成部231、暗号要素生成部232、fベクトル生成部233、sベクトル生成部234を備える。
【0091】
図14に基づき、Encアルゴリズムの処理について説明する。
(S601:公開パラメータ取得ステップ)
公開パラメータ取得部210は、例えば、通信装置によりネットワークを介して、鍵生成装置100が生成した公開パラメータpkを取得する。
【0092】
(S602:情報入力ステップ)
情報入力部220は、入力装置により、アクセスストラクチャS:=(M,ρ)を入力する。なお、アクセスストラクチャSの設定については、実現したいシステムの条件に応じて設定されるものである。また、アクセスストラクチャSのρは、例えば、復号可能なユーザの属性情報が設定されている。
また、情報入力部220は、入力装置により、復号装置300へ送信するメッセージmを入力する。
【0093】
(S603:fベクトル生成ステップ)
fベクトル生成部233は、処理装置により、r個の要素を有するベクトルfを数156に示すようにランダムに生成する。
【数156】

【0094】
(S604:sベクトル生成ステップ)
sベクトル生成部234は、処理装置により、(S602)で入力したアクセスストラクチャSに含まれる(L行×r列)の行列Mと、(S603)で生成したベクトルfとに基づき、ベクトルs→T:=(s,...,sを数157に示すように生成する。
【数157】

また、sベクトル生成部234は、処理装置により、(S603)で生成したベクトルfに基づき、値sを数158に示すように生成する。
【数158】

【0095】
(S605:乱数生成ステップ)
乱数生成部231は、処理装置により、乱数ηと、i=1,...,Lの各整数iについて乱数θと、乱数ζとを数159に示すように生成する。
【数159】

【0096】
(S606:暗号要素生成ステップ)
暗号要素生成部232は、処理装置により、暗号化データcの要素cを数160に示すように生成する。
【数160】

また、暗号要素生成部232は、処理装置により、i=1,...,Lの各整数iについて、暗号化データcの要素cを数161に示すように生成する。
【数161】

また、暗号要素生成部232は、処理装置により、暗号化データcの要素cd+1を数162に示すように生成する。
【数162】

【0097】
(S607:データ送信ステップ)
データ送信部240は、(S602)で入力したアクセスストラクチャSと、(S606)で生成されたc,c,...,c,cd+1とを要素とする暗号化データcを、例えば通信装置によりネットワークを介して復号装置300へ送信する。もちろん、暗号化データcは、他の方法により復号装置300へ送信されてもよい。
【0098】
つまり、(S601)から(S606)において、公開パラメータ取得部210、情報入力部220、暗号化データ生成部230は、数163に示すEncアルゴリズムを実行して、暗号化データcを生成する。そして、(S607)で、データ送信部240が生成された暗号化データcを復号装置300へ送信する。
【数163】

【0099】
復号装置300の機能と動作とについて説明する。復号装置300は、復号鍵取得部310、データ受信部320(データ取得部)、スパンプログラム計算部330、補完係数計算部340、ペアリング演算部350、平文情報計算部360を備える。
【0100】
図15に基づき、Decアルゴリズムの処理について説明する。
(S701:復号鍵取得ステップ)
復号鍵取得部310は、例えば、通信装置によりネットワークを介して、鍵生成装置100から配布された復号鍵skΓを取得する。また、復号鍵取得部310は、鍵生成装置100が生成した公開パラメータpkを取得する。
【0101】
(S702:データ受信ステップ)
データ受信部320は、例えば、通信装置によりネットワークを介して、暗号化装置200が送信した暗号化データcを受信する。
【0102】
(S703:スパンプログラム計算ステップ)
スパンプログラム計算部330は、処理装置により、(S702)で取得した暗号化データcに含まれるアクセスストラクチャSが、(S701)で受信した復号鍵skΓに含まれるΓを受理するか否かを判定する。アクセスストラクチャSがΓを受理するか否かの判定方法は、「第3.関数型暗号を実現するための概念」で説明した通りである。
スパンプログラム計算部330は、アクセスストラクチャSがΓを受理する場合(S703で受理)、処理を(S704)へ進める。一方、アクセスストラクチャSがΓを拒絶する場合(S703で拒絶)、暗号化データcを復号鍵skで復号できないとして処理を終了する。
【0103】
(S704)から(S706)とは、実施の形態1における図9に示す(S404)と(S406)と同様である。
【0104】
つまり、(S701)から(S706)において、公開パラメータ取得部210、情報入力部220、暗号化データ生成部230は、数164に示すDecアルゴリズムを実行して、メッセージm’(=m)を生成する。
【数164】

【0105】
実施の形態2に係る暗号処理システム10は、実施の形態1に係る暗号処理システム10と同様に、非常に高い自由度でアクセス制御の設計を行うことが可能な暗号方式を実現する。また、実施の形態2に係る暗号処理システム10は、実施の形態1に係る暗号処理システム10と同様に、安全性が高い。
【0106】
なお、実施の形態1と同様に、N=n+n+n+nをn+u+w+zにしてもよい。つまり、1つ目のnをそのままnとし、2つ目のnをuとし、3つ目のnをwとし、4つ目のnをzとしてもよい。すなわち、Nをn+u+w+zに設定してもよい。ここで、n,u,w,zは、それぞれ異なる値であってもよく、nは上述したように1以上の整数であり、u,w,zはいずれも0以上の整数である。
この場合、Setupアルゴリズムは、実施の形態1と同様に数148のように書き換えられる。
また、数155に示すKeyGenアルゴリズムは、数165のように書き換えられる。
【数165】

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

なお、数164に示すDecアルゴリズムには変更はない。
【0107】
また、Nは5ではなく、2以上の整数であればよい。Nが2であると、基底Bと基底Bとが2次元になる。この場合、KeyGenアルゴリズムにおいて、k:=(δ,1)B*0とし、Encアルゴリズムにおいて、c:=(−s,ζ)B0とすればよい。
【0108】
また、上記説明では、KeyGenアルゴリズムにおいて、k:=(δ,0,1,φ,0)B*0とした。しかし、所定の値κを用いて、k:=(δ,0,κ,φ,0)B*0としてもよい。この場合、Decアルゴリズムで計算されるK:=gζκとなるため、Encアルゴリズムにおいて、cd+1:=gζκmとすればよい。
【0109】
また、上記説明では、vi,ntの値について特に限定しなかった。しかし、安全性の証明の観点から、vi,nt:=1である限定としてもよい。
【0110】
また、安全性の証明の観点から、i=1,...,Lの各整数iについてのρ(i)は、それぞれ異なる識別情報tについての肯定形の組(t,v)又は否定形の組¬(t,v)であると限定してもよい。
言い替えると、関数ρを、ρ(i)=(t,v)又はρ(i)=¬(t,v)である場合にρ(i)=tである{1,...,L}→{1,...d}の写像であるとする。この場合、ρが単射であると限定してもよい。なお、ρ(i)は、上述したアクセスストラクチャS:=(M,ρ(i))のρ(i)である。
【0111】
また、実施の形態1では、アクセスストラクチャSを復号鍵skに持たせ、属性集合Γを暗号化データcに持たせたKey−Policy関数型暗号について説明した。また、実施の形態2では、アクセスストラクチャSを暗号化データcに持たせ、属性集合Γを復号鍵skΓに持たせたCiphertext−Policy関数型暗号について説明した。
しかし、2つのアクセスストラクチャSとSとを用意し、一方のアクセスストラクチャSを復号鍵に持たせ、他方のアクセスストラクチャSを暗号化データcに持たせるとともに、アクセスストラクチャSに対応する属性集合Γを復号鍵に持たせ、アクセスストラクチャSに対応する属性集合Γを暗号化データcに持たせてもよい。そして、アクセスストラクチャSが属性集合Γを受理し、かつ、アクセスストラクチャSが属性集合Γを受理した場合にのみ、暗号化データcを復号鍵で復号可能としてもよい。
つまり、Key−Policy関数型暗号とCiphertext−Policy関数型暗号とを組み合わせた暗号方式としてもよい。
【0112】
実施の形態3.
この実施の形態では、実施の形態2で説明した「Ciphertext−Policy関数型暗号方式」を応用した署名方式について説明する。
この実施の形態では、まず、「Ciphertext−Policy関数型暗号方式に基づく署名方式」の基本構成について説明する。次に、この「署名方式」を実現する「署名処理システム20」の基本構成について説明する。そして、この実施の形態に係る「署名方式」及び「署名処理システム20」について詳細に説明する。
【0113】
<Ciphertext−Policy関数型暗号方式に基づく署名方式の基本構成>
Ciphertext−Policy関数型暗号方式に基づく署名方式は、Setup、KeyGen、Sig、Verの4つのアルゴリズムを備える。
(Setup)
Setupアルゴリズムは、セキュリティパラメータλと、属性のフォーマットμ:=(d;n,...,n)とが入力され、公開パラメータpkと、マスター鍵skとを出力する確率的アルゴリズムである。
(KeyGen)
KeyGenアルゴリズムは、属性の集合であるΓ:={(t,x)|x∈Fnt,1≦t≦d}と、公開パラメータpkと、マスター鍵skとを入力として、署名鍵skΓを出力する確率的アルゴリズムである。
(Sig)
Sigアルゴリズムは、メッセージmと、署名鍵skΓと、アクセスストラクチャS:=(M,ρ)と、公開パラメータpkとを入力として、署名データsigを出力する確率的アルゴリズムである。
(Ver)
Verアルゴリズムは、メッセージmと、アクセスストラクチャS:=(M,ρ)と、署名データsigと、公開パラメータpkとを入力として、署名の検証に成功したことを示す値“1”、又は、署名の検証に失敗したことを示す値“0”を出力するアルゴリズムである。
【0114】
<署名処理システム20>
上述した署名処理のアルゴリズムを実行する署名処理システム20について説明する。
図16は、署名処理システム20の構成図である。
署名処理システム20は、鍵生成装置100、署名装置400、検証装置500を備える。
鍵生成装置100は、セキュリティパラメータλと、属性のフォーマットμ:=(d;n,...,n)とを入力としてSetupアルゴリズムを実行して、公開パラメータpkとマスター鍵skとを生成する。そして、鍵生成装置100は、生成した公開パラメータpkを公開する。また、鍵生成装置100は、属性の集合Γを入力としてKeyGenアルゴリズムを実行して、署名鍵skΓを生成して署名装置400へ秘密裡に配布する。
署名装置400は、メッセージmと、アクセスストラクチャSと、公開パラメータpkと、署名鍵skΓとを入力としてSigアルゴリズムを実行して、署名ベクトルs→*を生成する。署名装置400は、生成した署名ベクトルs→*と、メッセージmと、アクセスストラクチャSとを検証装置500へ送信する。
検証装置500は、署名ベクトルs→*と、メッセージmと、アクセスストラクチャSと、公開パラメータpkとを入力としてVerアルゴリズムを実行して、値“1”、又は、値“0”を出力する。
【0115】
<署名方式及び署名処理システム20の詳細>
図17から図21に基づき、署名方式、及び、署名処理システム20の機能と動作とについて説明する。
図17は、署名処理システム20の機能を示す機能ブロック図である。署名処理システム20は、上述したように、鍵生成装置100、署名装置400、検証装置500を備える。
図18と図19とは、鍵生成装置100の動作を示すフローチャートである。図18はSetupアルゴリズムの処理を示すフローチャートであり、図19はKeyGenアルゴリズムの処理を示すフローチャートである。図20は、署名装置400の動作を示すフローチャートであり、Sigアルゴリズムの処理を示すフローチャートである。図21は、検証装置500の動作を示すフローチャートであり、Verアルゴリズムの処理を示すフローチャートである。
なお、以下の説明では、xt,1:=1であるとする。
【0116】
鍵生成装置100の機能と動作とについて説明する。鍵生成装置100は、マスター鍵生成部110、マスター鍵記憶部120、情報入力部130(第1情報入力部)、署名鍵生成部160、鍵配布部150を備える。また、署名鍵生成部160は、乱数生成部161、鍵要素生成部162、秘匿要素生成部163を備える。
【0117】
まず、図18に基づき、Setupアルゴリズムの処理について説明する。
(S801:正規直交基底生成ステップ)
マスター鍵生成部110は、処理装置により、数167を計算して、paramμ→と、t=0,...,d+2の各整数tについて基底B及び基底Bとを生成する。
【数167】

【0118】
数167について、実施の形態1における(S101)に示す数127と異なる部分のみ説明する。まず、数167では、(3)でn,nd+1に1を設定し、nd+2に2を設定する。そして、t=0,...,d+2の各整数tについて、Nに4nを設定する。そして、(4)から(8)までの処理が、t=0,...,d+2の各整数tについて繰り返される。
【0119】
すなわち、(S801)で、マスター鍵生成部110は、数168に示すアルゴリズムGobを実行して、paramμ→と、t=0,...,d+2の各整数tについて基底B及び基底Bとを生成する。
【数168】

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

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

【0122】
(S804:マスター鍵記憶ステップ)
マスター鍵生成部110は、t=0,...,d+2の各整数tについての部分基底B^と、t=1,...,d+2の各整数tについての部分基底B^と、基底ベクトルb0,3と、(S101)で入力されたセキュリティパラメータλ(1λ)と、(S101)で生成したparamμ→とを合わせて、公開パラメータpkとする。
また、マスター鍵生成部110は、基底ベクトルb0,1をマスター鍵skとする。
そして、マスター鍵記憶部120は、公開パラメータpkとマスター鍵skとを記憶装置に記憶する。
【0123】
つまり、(S801)から(S803)において、マスター鍵生成部110は数171に示すSetupアルゴリズムを実行して、公開パラメータpkとマスター鍵skとを生成する。そして、(S804)で、マスター鍵記憶部120が生成された公開パラメータpkとマスター鍵skとを記憶装置に記憶する。
なお、公開パラメータは、例えば、ネットワークを介して公開され、署名装置400や検証装置500が取得可能な状態にされる。
【数171】

【0124】
次に、図19に基づき、KeyGenアルゴリズムの処理について説明する。
(S901:情報入力ステップ)
情報入力部130は、入力装置により、属性の集合Γ:={(t,x:=(xt,1,...,xt,nt∈Fnt))|1≦t≦d}を入力する。なお、属性の集合Γは、例えば、署名鍵skΓの使用者の属性情報が設定されている。
【0125】
(S902:乱数生成ステップ)
乱数生成部161は、処理装置により、t=1,...,d、ι=1,...,nの各整数tとιとについて、乱数δ、乱数φ,φt,ι,φd+2,ι,φd+3,ιを数172に示すように生成する。
【数172】

【0126】
(S903:鍵要素生成ステップ)
鍵要素生成部162は、処理装置により、署名鍵skΓの要素kを数173に示すように生成する。
【数173】

また、鍵要素生成部162は、処理装置により、Γに含まれる(t,x)の各整数tについて、署名鍵skΓの要素kを数174に示すように生成する。
【数174】

また、鍵要素生成部162は、処理装置により、署名鍵skΓの要素kd+2と要素kd+3とを数175に示すように生成する。
【数175】

【0127】
(S904:鍵配布ステップ)
鍵配布部150は、(S901)で入力した属性の集合Γと、(S903)で生成されたk,k,kd+2,kd+3とを要素とする署名鍵skΓを、例えば通信装置によりネットワークを介して秘密裡に署名装置400へ配布する。もちろん、復号鍵skΓは、他の方法により署名装置400へ配布されてもよい。
【0128】
つまり、(S901)から(S903)において、情報入力部130と署名鍵生成部160とは数176に示すKeyGenアルゴリズムを実行して、署名鍵skΓを生成する。そして、(S904)で、鍵配布部150が生成された署名鍵skΓを署名装置400へ配布する。
【数176】

【0129】
署名装置400の機能と動作について説明する。署名装置400は、署名鍵取得部410、情報入力部420(第2情報入力部)、補完係数計算部430、行列生成部440、署名生成部450、データ送信部460(データ出力部)を備える。また、署名生成部450は、乱数生成部451、署名要素生成部452を備える。
【0130】
図20に基づき、Sigアルゴリズムの処理について説明する。
(S1001:署名鍵取得ステップ)
署名鍵取得部410は、例えば、通信装置によりネットワークを介して、鍵生成装置100から配布された署名鍵skΓ:=(Γ,k,k,kd+2,kd+3)を取得する。また、署名鍵取得部410は、鍵生成装置100が生成した公開パラメータpkを取得する。
【0131】
(S1002:情報入力ステップ)
情報入力部420は、入力装置により、アクセスストラクチャS:=(M,ρ)を入力する。なお、ここで入力されるアクセスストラクチャSは、(S1001)で入力した署名鍵skΓに含まれる属性の集合Γを受理するものとする。
また、情報入力部220は、入力装置により、署名を付すメッセージmを入力する。
【0132】
(S1003:補完係数計算ステップ)
補完係数計算部430は、処理装置により、数177となるIと、定数(補完係数){αi∈Iとを計算する。
【数177】

なお、Mとは、行列Mのi行目のことである。
【0133】
(S1004:行追加ステップ)
行列生成部440は、処理装置により、行列Mに追加するベクトルML+1とそのラベルρ(L+1)とを数178に示すように生成する。
【数178】

ここでは、vL+1:=(1)とする。
【0134】
(S1005:乱数生成ステップ)
乱数生成部451は、処理装置により、乱数ξを数179に示すように生成する。
【数179】

【0135】
(S1006:署名要素生成ステップ)
署名要素生成部452は、処理装置により、署名ベクトルs→*の要素であるsを数180に示すように生成する。
【数180】

また、署名要素生成部452は、処理装置により、i=1,...,L+1の各整数iについて、署名ベクトルs→*の要素であるsを数181に示すように生成する。
【数181】

また、署名要素生成部452は、処理装置により、署名ベクトルs→*の要素であるsL+2を数182に示すように生成する。
【数182】

【0136】
(S1007:データ送信ステップ)
データ送信部460は、(S1002)で入力したメッセージmと、アクセスストラクチャS:=(M,ρ)と、(S1007)で生成されたs*→とを含む署名データsigを、例えば通信装置によりネットワークを介して検証装置500へ送信する。もちろん、署名データsigは、他の方法により検証装置500へ送信されてもよい。
【0137】
つまり、(S1001)から(S1006)において、署名鍵取得部410、情報入力部420、補完係数計算部430、行列生成部440、署名生成部450は、数183に示すSigアルゴリズムを実行して、署名データsigを生成する。そして、(S1007)で、データ送信部460が生成された署名データを検証装置500へ送信する。
【数183】

【0138】
検証装置500の機能と動作とについて説明する。検証装置500は、公開パラメータ取得部510、データ受信部520(データ取得部)、暗号化データ生成部530、ペアリング演算部540を備える。暗号化データ生成部530は、乱数生成部531、暗号要素生成部532、fベクトル生成部533、sベクトル生成部534を備える。
【0139】
図21に基づき、Verアルゴリズムの処理について説明する。
(S1101:公開パラメータ取得ステップ)
公開パラメータ取得部510は、例えば、通信装置によりネットワークを介して、鍵生成装置100が生成した公開パラメータpkを取得する。
【0140】
(S1102:データ受信ステップ)
データ受信部320は、例えば、通信装置によりネットワークを介して、署名装置400が送信した署名データsigを受信する。
【0141】
(S1103:fベクトル生成ステップ)
fベクトル生成部533は、処理装置により、r個の要素を有するベクトルfを数184に示すようにランダムに生成する。
【数184】

【0142】
(S1104:sベクトル生成ステップ)
sベクトル生成部534は、処理装置により、(S1102)で受信したアクセスストラクチャSに含まれる(L行×r列)の行列Mと、(S1103)で生成したベクトルfとに基づき、ベクトルs→T:=(s,...,sを数185に示すように生成する。
【数185】

また、sベクトル生成部534は、処理装置により、(S1103)で生成したベクトルfに基づき、値sと値sL+1とを数186に示すように生成する。
【数186】

【0143】
(S1105:乱数生成ステップ)
乱数生成部531は、処理装置により、i=1,...,L+2の各整数iについて、乱数η,ηL+2、1,ηL+2、2,θ,sL+2を数187に示すように生成する。
【数187】

(S1106:暗号要素生成ステップ)
暗号要素生成部532は、処理装置により、暗号化データcの要素cを数188に示すように生成する。
【数188】

また、暗号要素生成部532は、処理装置により、i=1,...,L+1の各整数iについて、暗号化データcの要素cを数189に示すように生成する。
【数189】

また、暗号要素生成部532は、処理装置により、暗号化データcの要素cL+2を数190に示すように生成する。
【数190】

【0144】
(S1107:ペアリング演算ステップ)
ペアリング演算部540は、処理装置により、数191を計算する。
【数191】

なお、ここでは、ρ(L+1):=¬(d+1,vL+1:=(1))であるとする。
ペアリング演算部540は、数191を計算した結果が値“1”であれば、値“1”を出力し、その他の値であれば値“0”を出力する。ここで、数191を計算した結果が値“1”であれば、署名が検証できたことを示し、その他の値であれば署名が検証できなかったことを示す。
なお、数192に示すように、署名データsigが正しいデータであれば、数191を計算することにより値“1”が得られる。
【数192】

【0145】
つまり、(S1101)から(S1107)において、公開パラメータ取得部510、データ受信部520、暗号化データ生成部530、ペアリング演算部540は、数193に示すVerアルゴリズムを実行して、署名データsigを検証する。
【数193】

【0146】
以上のように、署名処理システム20は、スパンプログラムと内積述語と秘密分散とを用いて構成したアクセスストラクチャSを用いて、署名方式を実現する。
【0147】
なお、Sigアルゴリズムにおいて、乱数ξや乱数rを用いて署名ベクトルs→*の要素を生成しているのは、署名ベクトルs→*の要素の生成元の情報である署名鍵skΓの要素kの変数δや変数φをランダム化するためである。署名鍵skΓの要素kの変数δや変数φをランダム化することにより、署名データの要素であるs→*からこれらの変数が読み取られることを防止することができる。つまり、署名データがどの署名鍵skΓに基づき生成されたものであるかを読み取られることを防止することができる。すなわち、リンクアビリティを高くすることができる。
【0148】
また、上記説明では、(S801)のNを4n(=n+n+n+n)に設定した。
しかし、n+n+n+nをn+u+w+zにしてもよい。つまり、1つ目のnをそのままnとし、2つ目のnをuとし、3つ目のnをwとし、4つ目のnをzとしてもよい。すなわち、Nをn+u+w+zに設定してもよい。ここで、n,u,w,zは、それぞれ異なる値であってもよく、nは上述したように1以上の整数であり、u,w,zはいずれも0以上の整数である。
この場合、数171に示すSetupアルゴリズムは、数194のように書き換えられる。つまり、基底B^と基底B^の基底ベクトルの添え字が変更される。
【数194】

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

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

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

【0149】
また、NやNd+1は4ではなく、1以上の整数であればよい。Nが1であると、基底Bと基底Bとが1次元になる。この場合、KeyGenアルゴリズムにおいて、k0,j:=(δ)B*0とし、Verアルゴリズムにおいて、c:=(−s−sL+2B0とすればよい。
また、Nd+2は8ではなく、2以上の整数であればよい。Nd+2が2であると、基底Bd+2と基底Bd+2とが2次元になる。この場合、KeyGenアルゴリズムにおいて、kd+2:=(δ(1,0))B*d+2、kd+3:=(δ(0,1))B*d+2とし、Verアルゴリズムにおいて、c:=(sL+2−θL+2m,θL+2Bd+2とすればよい。
【0150】
また、上記説明では、vi,ntの値について特に限定しなかった。しかし、安全性の証明の観点から、vi,nt:=1である限定としてもよい。
【0151】
また、安全性の証明の観点から、i=1,...,Lの各整数iについてのρ(i)は、それぞれ異なる識別情報tについての肯定形の組(t,v)又は否定形の組¬(t,v)であるとしてもよい。
言い替えると、関数ρを、ρ(i)=(t,v)又はρ(i)=¬(t,v)である場合にρ(i)=tである{1,...,L}→{1,...d}の写像であるとする。この場合、ρが単射であるとしてもよい。なお、ρ(i)は、上述したアクセスストラクチャS:=(M,ρ(i))のρ(i)である。
【0152】
また、上記説明では、Sigアルゴリズムにおいて、行追加ステップ(S1004)で、行列MにL+1行目として、ベクトルML+1の1行を追加した。しかし、行列Mに追加する行は、1行以上であれば何行であっても構わない。また、追加したML+1:=1であるとした。しかし、追加する行は、1に限らず他のベクトルであってもよい。
また、上記説明では、追加したL+1行目のラベルρ(L+1):=¬(d+1,vL+1:=(1))とした。しかし、追加する行のラベルの設定は、処理が成立するようになっていればよく、これに限るものではない。
つまり、追加する行や、追加する行のラベルは、Verアルゴリズムのペアリング演算ステップ(S1107)でペアリング演算をした場合に、追加した行の情報が0になるように設定されていればよい。
なお、追加した行が2行以上である場合には、追加した行数に応じて、SigアルゴリズムやVerアルゴリズムにおける処理の繰り返し回数を変更する必要がある。
【0153】
また、署名処理の安全性を高めるため、数171に示す署名アルゴリズムを数198のように変更し、数183に示すSigアルゴリズムを数199のように変更してもよい。
【数198】

【数199】

つまり、Setupアルゴリズムにおいて乱数値が設定された秘匿ベクトルpt,ιを生成し、Sigアルゴリズムでこの秘匿ベクトルpt,ιを用いて署名ベクトルs→*の要素sを生成している点が変更されている。また、Setupアルゴリズムにおいて、基底B^を公開パラメータpkではなく、マスター鍵skに含め、秘密にしている点が変更されている。これにより、署名処理の安全性が高くなっている。
なお、このようにSetupアルゴリズムと、Sigアルゴリズムとを変更した場合であっても、数199に示すように、署名データsigが正しいデータであれば、アルゴリズムにおいて、ペアリング演算を計算することにより値“1”が得られる。
【数200】

【0154】
また、Verアルゴリズムにおいて、暗号要素生成ステップ(S1106)で、cを生成することなく、cL+2:=(s−θL+2m,θL+2,0,0,0,0,ηL+2,1,ηL+2,2)としてもよい。そして、ペアリング演算ステップ(S1107)で、Πi=1L+2e(c,s)を計算するとしてもよい。
つまり、上記説明では、cとcL+2とを乱数sL+2で結びつけ、ペアリング演算を行った場合にcとcL+2との間でsL+2が打ち消されるようにしていた。しかし、予めsL+2を用いず、処理を簡略化してもよい。
この場合、KeyGenアルゴリズムにおいてkを生成する必要はない。同様に、Sigアルゴリズムにおいて、sを生成する必要はない。
【0155】
実施の形態4.
実施の形態1では、安全性の証明の観点から、i=1,...,Lの各整数iについてのρ(i)は、それぞれ異なる識別情報tについての肯定形の組(t,v)又は否定形の組¬(t,v)であるとしてもよいと説明した。つまり、ρが単射であるとしてもよいと説明した。しかし、ρが単射でなくてもよい。
この場合、安全性の証明の観点から、実施の形態1で説明したKey−Policy関数型暗号のSetupアルゴリズム、KeyGenアルゴリズム、Encアルゴリズムを以下のように変更してもよい。ここでは、実施の形態1で説明したKey−Policy関数型暗号の各アルゴリズムについての変更部分のみを説明する。
【0156】
この実施の形態において、φを数201に示す値であるとする。
【数201】

【0157】
Setupアルゴリズムについては、(1λ,μ:=(d;n,...,n))が入力された場合に、Setup(1λ,μ’:=(d;n’,...,n’))を実行する。ここで、t=1,...,dの各整数tについて、n’:=n+φである。
【0158】
KeyGenアルゴリズムについては、kの生成方法を数202のようにする。
【数202】

【0159】
Encアルゴリズムについては、cの生成方法を数203のようにする。
【数203】

【0160】
ここでは、実施の形態1で説明したKey−Policy関数型暗号についてのみ、ρが単射でない場合の処理の変更方法について説明した。しかし、同様の考え方に基づき、他の実施の形態で説明した暗号処理や署名処理を変更してもよい。
【0161】
実施の形態5.
以上の実施の形態では、双対ベクトル空間において暗号処理及び署名処理を実現する方法について説明した。この実施の形態では、双対加群において暗号処理及び署名処理を実現する方法について説明する。
【0162】
つまり、以上の実施の形態では、素数位数qの巡回群において暗号処理を実現した。しかし、合成数Mを用いて数204のように環Rを表した場合、環Rを係数とする加群においても、上記実施の形態で説明した暗号処理を適用することができる。
【数204】

【0163】
例えば、実施の形態1で説明したKey−Policy関数型暗号を、環Rを係数とする加群において実現すると数205から数208のようになる。
【数205】

【数206】

【数207】

【数208】

【0164】
ここでは、実施の形態1で説明したKey−Policy関数型暗号についてのみ、環Rを係数とする加群において実現する方法を示した。しかし、原則として、以上の実施の形態で体Fとして説明した処理を、環Rに置き換えることにより、以上の実施の形態で説明した他の暗号処理や署名処理についても、環Rを係数とする加群において実現できる。
【0165】
なお、以上の実施の形態におけるSetupアルゴリズムは、暗号処理システム10あるいは署名処理システム20のセットアップ時に一度実行すればよく、復号鍵を生成する度に実行する必要はない。また、上記説明では、SetupアルゴリズムとKeyGenアルゴリズムとを鍵生成装置100が実行するとしたが、SetupアルゴリズムとKeyGenアルゴリズムとをそれぞれ異なる装置が実行するとしてもよい。
【0166】
また、以上の実施の形態では、スパンプログラムM^は、入力列δによって行列M^から得られる行列Mδの行を線形結合して1が得られる場合に限り、入力列δを受理するとした。しかし、スパンプログラムM^は、1ではなく、他のベクトルvが得られる場合に限り、入力列δを受理するとしてもよい。
この場合、KeyGenアルゴリズムにおいてs:=1・f→Tではなく、s:=v・f→Tとすればよい。同様に、Sigアルゴリズムにおいてαを計算する際、Σi∈Iα=vとなるαを計算すればよい。
【0167】
また、上記説明における暗号処理は、権限の委譲を行うことも可能である。権限の委譲とは、復号鍵を有する者がその復号鍵よりも権限の弱い下位の復号鍵を生成することである。ここで、権限が弱いとは、復号できる暗号化データが限定されるという意味である。
例えば、第1階層目(最上位)においては、t=1の基底Bと基底Bとを用い、第2階層目においては、t=1,2の基底Bと基底Bとを用い、・・・、第k階層目においては、t−1,...,kの基底Bと基底Bとを用いる。用いる基底Bと基底Bとが増える分、属性情報が多く設定されることになる。したがって、より復号鍵の権限が限定されることになる。
【0168】
次に、実施の形態における暗号処理システム10(鍵生成装置100、暗号化装置200、復号装置300、)と、署名処理システム20(鍵生成装置100、署名装置400、検証装置500)のハードウェア構成について説明する。
図22は、鍵生成装置100、暗号化装置200、復号装置300、署名装置400、検証装置500のハードウェア構成の一例を示す図である。
図22に示すように、鍵生成装置100、暗号化装置200、復号装置300、署名装置400、検証装置500は、プログラムを実行するCPU911(Central・Processing・Unit、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう)を備えている。CPU911は、バス912を介してROM913、RAM914、LCD901(Liquid Crystal Display)、キーボード902(K/B)、通信ボード915、磁気ディスク装置920と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置920(固定ディスク装置)の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置920は、所定の固定ディスクインタフェースを介して接続される。
【0169】
ROM913、磁気ディスク装置920は、不揮発性メモリの一例である。RAM914は、揮発性メモリの一例である。ROM913とRAM914と磁気ディスク装置920とは、記憶装置(メモリ)の一例である。また、キーボード902、通信ボード915は、入力装置の一例である。また、通信ボード915は、通信装置(ネットワークインタフェース)の一例である。さらに、LCD901は、表示装置の一例である。
【0170】
磁気ディスク装置920又はROM913などには、オペレーティングシステム921(OS)、ウィンドウシステム922、プログラム群923、ファイル群924が記憶されている。プログラム群923のプログラムは、CPU911、オペレーティングシステム921、ウィンドウシステム922により実行される。
【0171】
プログラム群923には、上記の説明において「マスター鍵生成部110」、「マスター鍵記憶部120」、「情報入力部130」、「復号鍵生成部140」、「鍵配布部150」、「公開パラメータ取得部210」、「情報入力部220」、「暗号化データ生成部230」、「データ送信部240」、「復号鍵取得部310」、「データ受信部320」、「スパンプログラム計算部330」、「補完係数計算部340」、「ペアリング演算部350」、「平文情報計算部360」、「署名鍵取得部410」、「情報入力部420」、「補完係数計算部430」、「署名生成部450」、「データ送信部460」、「公開パラメータ取得部510」、「データ受信部520」、「暗号化データ生成部530」、「ペアリング演算部540」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、CPU911により読み出され実行される。
ファイル群924には、上記の説明において「公開パラメータpk」、「マスター鍵sk」、「暗号化データc」、「復号鍵sk」、「復号鍵skΓ」、「アクセスストラクチャS」、「属性の集合Γ」、「メッセージm」、「署名データsig」等の情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してCPU911によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのCPU911の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のCPU911の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【0172】
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、RAM914のメモリ、その他光ディスク等の記録媒体やICチップに記録される。また、データや信号は、バス912や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜回路」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ROM913に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ROM913等の記録媒体に記憶される。プログラムはCPU911により読み出され、CPU911により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
【符号の説明】
【0173】
10 暗号処理システム、20 署名処理システム、100 鍵生成装置、110 マスター鍵生成部、120 マスター鍵記憶部、130 情報入力部、140 復号鍵生成部、141 fベクトル生成部、142 sベクトル生成部、143 乱数生成部、144 鍵要素生成部、145 秘匿要素生成部、150 鍵配布部、160 署名鍵生成部、161 乱数生成部、162 鍵要素生成部、200 暗号化装置、210 公開パラメータ取得部、220 情報入力部、230 暗号化データ生成部、231 乱数生成部、232 暗号要素生成部、233 fベクトル生成部、234 sベクトル生成部、240 データ送信部、300 復号装置、310 復号鍵取得部、320 データ受信部、330 スパンプログラム計算部、340 補完係数計算部、350 ペアリング演算部、360 平文情報計算部、400 署名装置、410 署名鍵取得部、420 情報入力部、430 補完係数計算部、440 行列生成部、450 署名生成部、451 乱数生成部、452 署名要素生成部、460 データ送信部、500 検証装置、510 公開パラメータ取得部、520 データ受信部、530 暗号化データ生成部、540 ペアリング演算部、531 乱数生成部、532 暗号要素生成部、533 fベクトル生成部、534 sベクトル生成部。

【特許請求の範囲】
【請求項1】
鍵生成装置と暗号化装置と復号装置とを備え、t=0,...,d(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムであり、
前記鍵生成装置は、
i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性ベクトルv:=(vi,i’)(i’=1,...,n,nは1以上の整数)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)と、L行r列(rは1以上の整数)の所定の行列Mとを入力する第1情報入力部と、
r個の要素を有するベクトルf及びwと、前記第1情報入力部が入力した行列Mとに基づき生成される列ベクトルs→T:=(s,...,s:=M・f→Tと、値s:=w・f→Tと、所定の値θ(i=1,...,L)とに基づき、要素kと、i=1,...,Lの各整数iについての要素kとを生成する復号鍵生成部であって、
基底Bの基底ベクトルb0,p(pは所定の値)の係数として前記値−sを設定し、基底ベクトルb0,q(qは前記pとは異なる所定の値)の係数として所定の値κを設定して要素kを生成し、
i=1,...,Lの各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,1の係数としてs+θi,1を設定するとともに、前記識別情報tとi’=2,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてθi,i’を設定して要素kを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tとi’=1,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてsi,i’を設定して要素kを生成する復号鍵生成部と
を備え、
前記暗号化装置は、
t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性ベクトルx:=(xt,i’)(i’=1,...,n,nは1以上の整数)とを有する属性集合Γを入力する第2情報入力部と、
前記第2情報入力部が入力した属性集合Γに基づき、要素cと、前記属性集合Γに含まれる各識別情報tについてについての要素cとを生成する暗号化データ生成部であって、
基底Bの基底ベクトルb0,p(pは前記p)の係数として乱数値δを設定するとともに、基底ベクトルb0,q(qは前記q)の係数として所定の値ζを設定した要素cを生成し、
前記属性集合Γに含まれる各識別情報tについて、基底Bの基底ベクトルbt,i’(i’=1,...,n)の係数として前記乱数値δ倍したxt,i’を設定した要素cとを生成する暗号化データ生成部と
を備え、
前記復号装置は、
前記暗号化データ生成部が生成した要素c及び要素cと、前記属性集合Γとを含む暗号化データcを取得するデータ取得部と、
前記復号鍵生成部が生成した要素k及び要素kと、前記変数ρ(i)とを含む復号鍵skを取得する復号鍵取得部と、
前記データ取得部が取得した暗号化データcに含まれる属性集合Γと、前記復号鍵取得部が取得した復号鍵skに含まれる変数ρ(i)とに基づき、i=1,...,Lの各整数iのうち、変数ρ(i)が肯定形の組(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0となるiと、変数ρ(i)が否定形の組¬(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、αを合計した場合にsとなる補完係数αを計算する補完係数計算部と、
前記暗号化データcに含まれる要素c,要素cと、前記復号鍵skに含まれる要素k,要素kとについて、前記補完係数計算部が特定した集合Iと、前記補完係数計算部が計算した補完係数αとに基づき、数1に示すペアリング演算を行い値K=gζκを計算するペアリング演算部と
を備えることを特徴とする暗号処理システム。
【数1】

【請求項2】
前記暗号処理システムは、少なくとも基底ベクトルb0,i(i=1,...,5)を有する基底Bと、少なくとも基底ベクトルbt,i(i=1,...,n,...,n+u,...,n+u+w,...,n+u+w+z)(u,w,zは1以上の整数、)を有する基底B(t=1,...,d)と、少なくとも基底ベクトルb0,i(i=1,...,5)を有する基底Bと、少なくとも基底ベクトルbt,i(i=1,...,n,...,n+u,...,n+u+w,...,n+u+w+z)を有する基底B(t=1,...,d)とを用いて暗号処理を実行し、
前記鍵生成装置の前記復号鍵生成部は、乱数値ηと所定の値κとに基づき数2に示す要素kを生成するとともに、変数ρ(i)が肯定形の組(t,v)である場合には、乱数値θ,ηi,i’(i=1,...,L,i’=1,...,w)とに基づき数3に示す要素kを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、乱数値ηi,i’(i=1,...,L,i’=1,...,w)とに基づき数4に示す要素kを生成し、
前記暗号化装置の前記暗号化データ生成部は、乱数値δ,φと所定の値ζとに基づき数5に示す要素cを生成するとともに、前記乱数値δ,φt,i(i=1,...,z)に基づき数6に示す要素cとを生成する
ことを特徴とする請求項1に記載の暗号処理システム。
【数2】

【数3】

【数4】

【数5】

【数6】

【請求項3】
t=0,...,d(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムにおいて、復号鍵skを生成する鍵生成装置であり、
i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性ベクトルv:=(vi,i’)(i’=1,...,n,nは1以上の整数)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)と、L行r列(rは1以上の整数)の所定の行列Mとを入力する第1情報入力部と、
r個の要素を有するベクトルf及びwと、前記第1情報入力部が入力した行列Mとに基づき生成される列ベクトルs→T:=(s,...,s:=M・f→Tと、値s:=w・f→Tと、所定の値θ(i=1,...,L)とに基づき、要素kと、i=1,...,Lの各整数iについての要素kとを生成する復号鍵生成部であって、
基底Bの基底ベクトルb0,p(pは所定の値)の係数として前記値−sを設定し、基底ベクトルb0,q(qは前記pとは異なる所定の値)の係数として所定の値κを設定して要素kを生成し、
i=1,...,Lの各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,1の係数としてs+θi,1を設定するとともに、前記識別情報tとi’=2,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてθi,i’を設定して要素kを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tとi’=1,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてsi,i’を設定して要素kを生成する復号鍵生成部と、
前記第1情報入力部が入力した変数ρ(i)と、前記復号鍵生成部が生成した要素k及び要素kとを含むデータを復号鍵skとして配布する鍵配布部と
を備えることを特徴とする鍵生成装置。
【請求項4】
t=0,...,d(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムにおいて、暗号化データcを生成する暗号化装置であり、
t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性ベクトルx:=(xt,i’)(i’=1,...,n,nは1以上の整数)とを有する属性集合Γを入力する第2情報入力部と、
前記第2情報入力部が入力した属性集合Γに基づき、要素cと、前記属性集合Γに含まれる各識別情報tについての要素cとを生成する暗号化データ生成部であって、
基底Bの基底ベクトルb0,p(pは所定の値)の係数として乱数値δを設定するとともに、基底ベクトルb0,q(qは前記pとは異なる所定の値)の係数として所定の値ζを設定した要素cを生成し、
前記属性集合Γに含まれる各識別情報tについて、基底Bの基底ベクトルbt,i’(i’=1,...,n)の係数として前記乱数値δ倍したxt,i’を設定した要素cとを生成する暗号化データ生成部と、
前記第2情報入力部が入力した属性集合Γと、前記暗号化データ生成部が生成した要素c及び要素cとを暗号化データcとして出力するデータ出力部と
を備えることを特徴とする暗号化装置。
【請求項5】
t=0,...,d(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムにおいて、暗号化データcを復号鍵skで復号する復号装置であり、
t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性ベクトルx:=(xt,i’)(i’=1,...,n,nは1以上の整数)とを有する属性集合Γに基づき生成された要素cと、要素c(前記属性集合Γに含まれる各整数)とであって、
基底Bの基底ベクトルb0,p(pは所定の値)の係数として乱数値δが設定されるとともに、基底ベクトルb0,q(qは前記pとは異なる所定の値)の係数として所定の値ζが設定された要素cと、
前記属性集合Γに含まれる各識別情報tについて、基底Bの基底ベクトルbt,i’(i’=1,...,n)の係数として前記乱数値δ倍したxt,i’が設定された要素c
を前記属性集合Γとともに、暗号化データcとして取得するデータ取得部と、
r個(rは1以上の整数)の要素を有するベクトルf及びwとL行r列の所定の行列Mとに基づき生成される列ベクトルs→T:=(s,...,s:=M・f→T及び値s:=w・f→Tと、所定の値θ(i=1,...,L)と、i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)及び属性ベクトルv:=(vi,i’)(i’=1,...,n,nは1以上の整数)の肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)とに基づき生成された要素kと、要素k(i=1,...,Lの各整数)とであって、
基底Bの基底ベクトルb0,p(pは前記p)の係数として前記値−sが設定され、基底ベクトルb0,q(qは前記q)の係数として所定の値κが設定された要素kと、
i=1,...,Lの各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,1の係数としてs+θi,1が設定されるとともに、前記識別情報tとi’=2,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてθi,i’が設定された要素kであって、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tとi’=1,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてsi,i’が設定された要素k
を前記変数ρ(i)とともに、復号鍵skとして取得する復号鍵取得部と、
前記データ取得部が取得した暗号化データcに含まれる属性集合Γと、前記復号鍵取得部が取得した復号鍵skに含まれる変数ρ(i)とに基づき、i=1,...,Lの各整数iのうち、変数ρ(i)が肯定形の組(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0となるiと、変数ρ(i)が否定形の組¬(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、αを合計した場合にsとなる補完係数αを計算する補完係数計算部と、
前記暗号化データcに含まれる要素c,要素cと、前記復号鍵skに含まれる要素k,要素kとについて、前記補完係数計算部が特定した集合Iと、前記補完係数計算部が計算した補完係数αとに基づき、数7に示すペアリング演算を行い値K=gζκを計算するペアリング演算部と
を備えることを特徴とする復号装置。
【数7】

【請求項6】
鍵生成装置と暗号化装置と復号装置とを備え、t=0,...,d(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムであり、
前記鍵生成装置は、
t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性ベクトルx:=(xt,i’)(i’=1,...,n,nは1以上の整数)とを有する属性集合Γを入力する第1情報入力部と、
前記第1情報入力部が入力した属性集合Γに基づき、要素kと、前記属性集合Γに含まれる各識別情報tについての要素kとを生成する復号鍵生成部であって、
基底Bの基底ベクトルb0,p(pは所定の値)の係数として乱数値δを設定するとともに、基底ベクトルb0,q(qは前記pとは異なる所定の値)の係数として所定の値κを設定した要素kを生成し、
前記属性集合Γに含まれる各識別情報tについて、基底Bの基底ベクトルbt,i’(i’=1,...,n)の係数として前記乱数値δ倍したxt,i’を設定した要素kとを生成する復号鍵生成部と
を備え、
前記暗号化装置は、
i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性ベクトルv:=(vi,i’)(i’=1,...,n,nは1以上の整数)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)と、L行r列(rは1以上の整数)の所定の行列Mとを入力する第2情報入力部と、
r個の要素を有するベクトルf及びwと、前記第2情報入力部が入力した行列Mとに基づき生成される列ベクトルs→T:=(s,...,s:=M・f→Tと、値s:=w・f→Tと、所定の値θ(i=1,...,L)とに基づき、要素cと、i=1,...,Lの各整数iについての要素cとを生成する暗号化データ生成部であって、
基底Bの基底ベクトルb0,p(pは前記p)の係数として前記値−sを設定し、基底ベクトルb0,q(qは前記q)の係数として所定の値ζを設定して要素cを生成し、
i=1,...,Lの各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,1の係数としてs+θi,1を設定するとともに、前記識別情報tとi’=2,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてθi,i’を設定して要素cを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tとi’=1,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてsi,i’を設定して要素cを生成する暗号化データ生成部と
を備え、
前記復号装置は、
前記暗号化データ生成部が生成した要素c及び要素cと、前記変数ρ(i)とを含む暗号化データcを取得するデータ取得部と、
前記復号鍵生成部が生成した要素k及び要素kと、前記属性集合Γとを含む復号鍵skΓを取得する復号鍵取得部と、
前記データ取得部が取得した暗号化データcに含まれるi=1,...,Lの各整数iについての変数ρ(i)と、前記復号鍵取得部が取得した復号鍵skΓに含まれる属性集合Γとに基づき、i=1,...,Lの各整数iのうち、変数ρ(i)が肯定形の組(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0となるiと、変数ρ(i)が否定形の組¬(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、αを合計した場合にsとなる補完係数αを計算する補完係数計算部と、
前記暗号化データcに含まれる要素c,要素cと、前記復号鍵skΓに含まれる要素k,要素kとについて、前記補完係数計算部が特定した集合Iと、前記補完係数計算部が計算した補完係数αとに基づき、数8に示すペアリング演算を行い値K=gζκを計算するペアリング演算部と
を備えることを特徴とする暗号処理システム。
【数8】

【請求項7】
前記暗号処理システムは、少なくとも基底ベクトルb0,i(i=1,...,5)を有する基底Bと、少なくとも基底ベクトルbt,i(i=1,...,n,...,n+u,...,n+u+w,...,n+u+w+z)(u,w,zは1以上の整数、)を有する基底B(t=1,...,d)と、少なくとも基底ベクトルb0,i(i=1,...,5)を有する基底Bと、少なくとも基底ベクトルbt,i(i=1,...,n,...,n+u,...,n+u+w,...,n+u+w+z)を有する基底B(t=1,...,d)とを用いて暗号処理を実行し、
前記鍵生成装置の前記復号鍵生成部は、乱数値δ,φと所定の値κとに基づき数9に示す要素kを生成するとともに、前記乱数値δ,φt,i(i=1,...,w)に基づき数10に示す要素kとを生成し、
前記暗号化装置の前記暗号化データ生成部は、乱数値ηと所定の値ζとに基づき数11に示す要素cを生成するとともに、変数ρ(i)が肯定形の組(t,v)である場合には、乱数値θ,ηi,i’(i=1,...,L,i’=1,...,z)とに基づき数12に示す要素cを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、乱数値ηi,i’(i=1,...,L,i’=1,...,z)とに基づき数13に示す要素cを生成する
ことを特徴とする請求項6に記載の暗号処理システム。
【数9】

【数10】

【数11】

【数12】

【数13】

【請求項8】
t=0,...,d(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムにおいて、復号鍵skΓを生成する鍵生成装置であり、
t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性ベクトルx:=(xt,i’)(i’=1,...,n,nは1以上の整数)とを有する属性集合Γを入力する第1情報入力部と、
前記第1情報入力部が入力した属性集合Γに基づき、要素kと、前記属性集合Γに含まれる各識別情報tについての要素kとを生成する復号鍵生成部であって、
基底Bの基底ベクトルb0,p(pは所定の値)の係数として乱数値δを設定するとともに、基底ベクトルb0,q(qは前記pとは異なる所定の値)の係数として所定の値κを設定した要素kを生成し、
前記属性集合Γに含まれる各識別情報tについて、基底Bの基底ベクトルbt,i’(i’=1,...,n)の係数として前記乱数値δ倍したxt,i’を設定した要素kとを生成する復号鍵生成部と、
前記第1情報入力部が入力した変数ρ(i)と、前記復号鍵生成部が生成した要素k及び要素kとを含むデータを復号鍵skΓとして配布する鍵配布部と
を備えることを特徴とする鍵生成装置。
【請求項9】
t=0,...,d(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムにおいて、暗号化データcを生成する暗号化装置であり、
i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性ベクトルv:=(vi,i’)(i’=1,...,n,nは1以上の整数)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)と、L行r列(rは1以上の整数)の所定の行列Mとを入力する第2情報入力部と、
r個の要素を有するベクトルf及びwと、前記第2情報入力部が入力した行列Mとに基づき生成される列ベクトルs→T:=(s,...,s:=M・f→Tと、値s:=w・f→Tと、所定の値θ(i=1,...,L)とに基づき、要素cと、i=1,...,Lの各整数iについての要素cとを生成する暗号化データ生成部であって、
基底Bの基底ベクトルb0,p(pは前記p)の係数として前記値−sを設定し、基底ベクトルb0,q(qは前記q)の係数として所定の値ζを設定して要素cを生成し、
i=1,...,Lの各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,1の係数としてs+θi,1を設定するとともに、前記識別情報tとi’=2,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてθi,i’を設定して要素cを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tとi’=1,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてsi,i’を設定して要素cを生成する暗号化データ生成部と、
前記第2情報入力部が入力した属性集合Γと、前記暗号化データ生成部が生成した要素c及び要素cとを暗号化データcとして出力するデータ出力部と
を備えることを特徴とする暗号化装置。
【請求項10】
t=0,...,d(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムにおいて、暗号化データcを復号鍵skΓで復号する復号装置であり、
r個(rは1以上の整数)の要素を有するベクトルf及びwとL行r列の所定の行列Mとに基づき生成される列ベクトルs→T:=(s,...,s:=M・f→T及び値s:=w・f→Tと、所定の値θ(i=1,...,L)と、i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性ベクトルv:=(vi,i’)(i’=1,...,n,nは1以上の整数)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)とに基づき生成された要素cと、要素c(i=1,...,Lの各整数)とであって、
基底Bの基底ベクトルb0,p(pは所定の値)の係数として前記値−sが設定され、基底ベクトルb0,q(qは前記pとは異なる所定の値)の係数として所定の値ζが設定された要素cと、
i=1,...,Lの各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,1の係数としてs+θi,1が設定されるとともに、前記識別情報tとi’=2,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてθi,i’が設定された要素cであって、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tとi’=1,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてsi,i’が設定された要素c
を前記変数ρ(i)とともに、暗号化データcとして取得するデータ取得部と、
t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性ベクトルx:=(xt,i’)(i’=1,...,n,nは1以上の整数)とを有する属性集合Γに基づき生成された要素kと、要素k(tは前記属性集合Γに含まれる各整数)とであって、
基底Bの基底ベクトルb0,p(pは前記p)の係数として乱数値δが設定されるとともに、基底ベクトルb0,q(qは前記q)の係数として所定の値κが設定された要素kと、
前記属性集合Γに含まれる各識別情報tについて、基底Bの基底ベクトルbt,i’(i’=1,...,n)の係数として前記乱数値δ倍したxt,i’が設定された要素k
を前記属性集合Γとともに、復号鍵skΓとして取得する復号鍵取得部と、
前記データ取得部が取得した暗号化データcに含まれる変数ρ(i)と、前記復号鍵取得部が取得した復号鍵skに含まれる属性集合Γとに基づき、i=1,...,Lの各整数iのうち、変数ρ(i)が肯定形の組(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0となるiと、変数ρ(i)が否定形の組¬(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、αを合計した場合にsとなる補完係数αを計算する補完係数計算部と、
前記暗号化データcに含まれる要素c,要素cと、前記復号鍵skに含まれる要素k,要素kとについて、前記補完係数計算部が特定した集合Iと、前記補完係数計算部が計算した補完係数αとに基づき、数14に示すペアリング演算を行い値K=gζκを計算するペアリング演算部と
を備えることを特徴とする復号装置。
【数14】

【請求項11】
鍵生成装置と署名装置と検証装置とを備え、t=1,...,d,d+2(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて署名処理を実行する署名処理システムであり、
前記鍵生成装置は、
t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性ベクトルx:=(xt,i’)(i’=1,...,n,nは1以上の整数)とを有する属性集合Γを入力する第1情報入力部と、
前記第1情報入力部が入力した属性集合Γに基づき、前記属性集合Γに含まれる各識別情報tについての要素kと、要素kd+2と、要素kd+3とを生成する署名鍵生成部であって、
前記属性集合Γに含まれる各識別情報tについて、基底Bの基底ベクトルbt,i’(i’=1,...,n)の係数として前記乱数値δ倍したxt,i’を設定した要素kを生成し、
基底Bd+2の基底ベクトルbd+2,p’(p’は所定の値)の係数として前記乱数値δを設定した要素kd+2を生成し、
基底Bd+2の基底ベクトルbd+2,q’(q’は前記p’とは異なる所定の値)の係数として前記乱数値δを設定した要素kd+3を生成する署名鍵生成部と
を備え、
前記署名装置は、
i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性ベクトルv:=(vi,i’)(i’=1,...,n,nは1以上の整数)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)と、L行r列(rは1以上の整数)の所定の行列Mと、メッセージmとを入力する第2情報入力部と、
前記署名鍵生成部が生成した要素kと、要素kd+2と、要素kd+3と、前記属性集合Γとを署名鍵skΓとして取得する署名鍵取得部と、
i=1,...,Lの各整数iについての変数ρ(i)と、前記署名鍵取得部が取得した署名鍵skΓに含まれる属性集合Γとに基づき、i=1,...,Lの各整数iのうち、変数ρ(i)が肯定形の組(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0となるiと、変数ρ(i)が否定形の組¬(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、前記第2情報入力部が入力した行列Mのi行目の要素であるMに基づき、αを合計したした場合に所定のベクトルwとなる補完係数αを計算する補完係数計算部と、
前記変数ρ(i)と、前記属性集合Γと、前記補完係数計算部が特定した集合Iと、前記補完係数計算部が計算した補完係数αとに基づき、i=1,...,Lの各整数iについてのsと、sとを生成する署名生成部であって、
βを、行列Mの各行番号を表す各整数iについて、βを合計した場合に全ての要素が0となる値とし、
行列Mの各行番号を表す各整数iについて、
i∈Iであって、変数ρ(i)が肯定形の組(t,v)である場合には、値γ:=αとし、ベクトルy:=(yi,ι)(ι:=1,...,n)をyとvとの内積が0で、yi,1=1であるベクトルとし、
i∈Iであって、変数ρ(i)が否定形の組¬(t,v)である場合には、値γ:=α/(v・x)とし、ベクトルy:=(yi,ι)(ι:=1,...,n)をyとvとの内積が1であるベクトルとし、
i∈Iでなく、変数ρ(i)が肯定形の組(t,v)である場合には、値γ:=0とし、ベクトルy:=(yi,ι)(ι:=1,...,n)をyとvとの内積が0で、yi,1=1であるベクトルとし、
i∈Iでなく、変数ρ(i)が否定形の組¬(t,v)である場合には、値γ:=0とし、ベクトルy:=(yi,ι)(ι:=1,...,n)をyとvとの内積が1であるベクトルとして、
数15に示すように行列Mの各行番号を表す各整数iについてのsと、sとを生成する署名生成部と
を備え、
前記検証装置は、
前記署名生成部が生成したs,sと、メッセージmと、変数ρ(i)と、行列Mとを含む署名データsigを取得するデータ取得部と、
r個の要素を有するベクトルfと、前記ベクトルwと、前記データ取得部が取得した行列Mとに基づき生成される列ベクトルs→T:=(s,...,s:=M・f→Tと、値s:=w・f→Tと、所定の値θ(iは行列Mの各行番号とX)とに基づき、行列Mの各行番号を表す各整数iについての要素cと、要素cとを生成する暗号化データ生成部であって、
前記行列Mの各行番号を表す各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,1の係数としてs+θi,1を設定するとともに、前記識別情報tとi’=2,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてθi,i’を設定して要素cを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tとi’=1,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてsi,i’を設定して要素cを生成し、
基底Bd+2の基底ベクトルbd+2,p’(p’は前記p’)にs−θmを設定するとともに、基底ベクトルbd+2,q’(q’は前記q’)にθを設定して要素cを生成する暗号化データ生成部と、
行列Mの各行番号とXとを示す各整数iについて、数16に示すペアリング演算を行い、前記署名データsigの正当性を検証するペアリング演算部と
を備えることを特徴とする署名処理システム。
【数15】

【数16】

【請求項12】
前記署名処理システムは、少なくとも基底ベクトルb0,i(i=1,...,4)を有する基底Bと、少なくとも基底ベクトルbt,i(i=1,...,n,...,n+u,...,n+u+w,...,n+u+w+z)(u,w,zは1以上の整数、)を有する基底B(t=1,...,d)と、少なくとも基底ベクトルbd+1,i(i=1,...,4)を有する基底Bd+1と、少なくとも基底ベクトルbd+2,i(i=1,...,8)を有する基底Bd+2と、少なくとも基底ベクトルb0,i(i=1,...,4)を有する基底Bと、少なくとも基底ベクトルbt,i(i=1,...,n,...,n+u,...,n+u+w,...,n+u+w+z)を有する基底B(t=1,...,d)と、少なくとも基底ベクトルbd+1,i(i=1,...,4)を有する基底Bd+1と、少なくとも基底ベクトルbd+2,i(i=1,...,8)を有する基底Bd+2とを用いて署名処理を実行し、
前記鍵生成装置の前記署名鍵生成部は、
前記属性集合Γに含まれる各識別情報tと、ι=1,...,wの各整数ιとについて、要素kと、要素kと、要素kd+2と、要素kd+3とを、乱数値δ,φ,φt,ι,φd+2,1,φd+2,2,φd+3,1,φd+3,2に基づき、数17に示すように生成し、
前記署名装置は、さらに、
前記行列MのL+1行目に所定の行ベクトルML+1を追加する行列生成部
を備え
前記署名装置の前記署名生成部は、
要素kと、要素kと、要素kd+2と、要素kd+3と、乱数値ξとに基づき、数18に示すように、i=1,...,L+1の各整数iについてのsと、sとしてs及びsL+2とを生成し、
前記検証装置の前記暗号化データ生成部は、
i=1,...,L+1の各整数iと、i‘=1,...,zの各整数i’とについて、乱数値θ,ηi,i’,ηL+2,1,ηL+2,2に基づき、数19に示すように、要素cと、要素cとして要素c及び要素cL+2とを生成し、
前記ペアリング演算部は、i=1,...,L+2の各整数iについて、前記ペアリング演算を行う
ことを特徴とする請求項11に記載の署名処理システム。
【数17】

【数18】

【数19】

【請求項13】
t=1,...,d,d+2(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて署名処理を実行する署名処理システムにおいて、署名鍵skΓを生成する鍵生成装置であり、
t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性ベクトルx:=(xt,i’)(i’=1,...,n,nは1以上の整数)とを有する属性集合Γを入力する第1情報入力部と、
前記第1情報入力部が入力した属性集合Γに基づき、前記属性集合Γに含まれる各識別情報tについての要素kと、要素kd+2と、要素kd+3とを生成する署名鍵生成部であって、
前記属性集合Γに含まれる各識別情報tについて、基底Bの基底ベクトルbt,i’(i’=1,...,n)の係数として前記乱数値δ倍したxt,i’を設定した要素kを生成し、
基底Bd+2の基底ベクトルbd+2,p’(p’は所定の値)の係数として前記乱数値δを設定した要素kd+2を生成し、
基底Bd+2の基底ベクトルbd+2,q’(q’は前記p’とは異なる所定の値)の係数として前記乱数値δを設定した要素kd+3を生成する署名鍵生成部と、
前記第1情報入力部が入力した属性集合Γと、前記署名鍵生成部が生成した要素kと、要素kd+2と、要素kd+3とを含むデータを署名鍵skΓとして配布する鍵配布部と
を備えることを特徴とする鍵生成装置。
【請求項14】
t=1,...,d,d+2(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて署名処理を実行する署名処理システムにおいて、署名データsigを生成する署名装置であり、
i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性ベクトルv:=(vi,i’)(i’=1,...,n,nは1以上の整数)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)と、L行r列(rは1以上の整数)の所定の行列Mと、メッセージmとを入力する第2情報入力部と、
t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性ベクトルx:=(xt,i’)(i’=1,...,n,nは1以上の整数)とを有する属性集合Γに基づき生成された要素k(tは前記属性集合Γに含まれる各識別情報)と、要素kd+2と、要素kd+3とであって、
前記属性集合Γに含まれる各識別情報tについて、基底Bの基底ベクトルbt,i’(i’=1,...,n)の係数として前記乱数値δ倍したxt,i’が設定された要素kと、
基底Bd+2の基底ベクトルbd+2,p’(p’は所定の値)の係数として前記乱数値δが設定された要素kd+2と、
基底Bd+2の基底ベクトルbd+2,q’(q’は前記p’とは異なる所定の値)の係数として前記乱数値δが設定された要素kd+3
を前記属性集合Γとともに、署名鍵skΓとして取得する署名鍵取得部と、
i=1,...,Lの各整数iについての変数ρ(i)と、前記署名鍵取得部が取得した署名鍵skΓに含まれる属性集合Γとに基づき、i=1,...,Lの各整数iのうち、変数ρ(i)が肯定形の組(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0となるiと、変数ρ(i)が否定形の組¬(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、前記第2情報入力部が入力した行列Mのi行目の要素であるMに基づき、αを合計した場合に所定のベクトルwとなる補完係数αを計算する補完係数計算部と、
前記変数ρ(i)と、前記属性集合Γと、前記補完係数計算部が特定した集合Iと、前記補完係数計算部が計算した補完係数αとに基づき、行列Mの各行番号を表す各整数iについてのsと、sとを生成する署名生成部であって、
βを、行列Mの各行番号を表す各整数iについて、βを合計した場合に全ての要素が0となる値とし、
行列Mの各行番号を表す各整数iについて、
i∈Iであって、変数ρ(i)が肯定形の組(t,v)である場合には、値γ:=αとし、ベクトルy:=(yi,ι)(ι:=1,...,n)をyとvとの内積が0で、yi,1=1であるベクトルとし、
i∈Iであって、変数ρ(i)が否定形の組¬(t,v)である場合には、値γ:=α/(v・x)とし、ベクトルy:=(yi,ι)(ι:=1,...,n)をyとvとの内積が1であるベクトルとし、
i∈Iでなく、変数ρ(i)が肯定形の組(t,v)である場合には、値γ:=0とし、ベクトルy:=(yi,ι)(ι:=1,...,n)をyとvとの内積が0で、yi,1=1であるベクトルとし、
i∈Iでなく、変数ρ(i)が否定形の組¬(t,v)である場合には、値γ:=0とし、ベクトルy:=(yi,ι)(ι:=1,...,n)をyとvとの内積が1であるベクトルとして、
数20に示すように行列Mの各行番号を表すの各整数iについてのsと、sとを生成する署名生成部と
前記第2情報入力部が入力した変数ρ(i)と行列Mとメッセージmと、前記署名生成部が生成したsとsとsとを含むデータを署名データsigとして出力するデータ出力部と
を備えることを特徴とする署名装置。
【数20】

【請求項15】
t=1,...,d,d+2(dは1以上の整数)の各整数tについての基底Bと基底Bとを用いて署名処理を実行する署名処理システムにおいて、署名データsigを検証する検証装置であり、
t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性ベクトルx:=(xt,i’)(i’=1,...,n,nは1以上の整数)とを有する属性集合Γに基づき生成された要素k(tは前記属性集合Γに含まれる各識別情報)と、要素kd+2と、要素kd+3とであって、
前記属性集合Γに含まれる各識別情報tについて、基底Bの基底ベクトルbt,i’(i’=1,...,n)の係数として前記乱数値δ倍したxt,i’が設定された要素kと、
基底Bd+2の基底ベクトルbd+2,p’(p’は所定の値)の係数として前記乱数値δが設定された要素kd+2と、
基底Bd+2の基底ベクトルbd+2,q’(q’は前記p’とは異なる所定の値)の係数として前記乱数値δが設定された要素kd+3と、
i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性ベクトルv:=(vi,i’)(i’=1,...,n,nは1以上の整数)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)と、前記属性集合Γとに基づき計算された集合Iと補完係数αとであって、
i=1,...,Lの各整数iのうち、変数ρ(i)が肯定形の組(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0となるiと、変数ρ(i)が否定形の組¬(t,v)であり、かつ、その組のvと、その組の識別情報tが示すΓに含まれるxとの内積が0とならないiとの集合Iと、
集合Iに含まれるiについて、前記第2情報入力部が入力した行列Mのi行目の要素であるMに基づき、αを合計した場合に所定のベクトルwとなる補完係数αと、
前記変数ρ(i)と、前記属性集合Γと、前記集合Iと、前記補完係数αとに基づき生成されたs(i=1,...,Lの各整数)と、sとであって、
βを、行列Mの各行番号を表す各整数iについて、βを合計した場合に全ての要素が0となる値とし、
行列Mの各行番号を表す各整数iについて、
i∈Iであって、変数ρ(i)が肯定形の組(t,v)である場合には、値γ:=αとし、ベクトルy:=(yi,ι)(ι:=1,...,n)をyとvとの内積が0で、yi,1=1であるベクトルとし、
i∈Iであって、変数ρ(i)が否定形の組¬(t,v)である場合には、値γ:=α/(v・x)とし、ベクトルy:=(yi,ι)(ι:=1,...,n)をyとvとの内積が1であるベクトルとし、
i∈Iでなく、変数ρ(i)が肯定形の組(t,v)である場合には、値γ:=0とし、ベクトルy:=(yi,ι)(ι:=1,...,n)をyとvとの内積が0で、yi,1=1であるベクトルとし、
i∈Iでなく、変数ρ(i)が否定形の組¬(t,v)である場合には、値γ:=0とし、ベクトルy:=(yi,ι)(ι:=1,...,n)をyとvとの内積が1であるベクトルとして、
数21に示すように生成されたsと、s
のうち、sと、sとメッセージmと、変数ρ(i)と、行列Mとを含む署名データsigを取得するデータ取得部と、
r個(rは1以上の整数)の要素を有するベクトルfと、前記ベクトルwと、前記第2情報入力部が入力した行列Mとに基づき生成される列ベクトルs→T:=(s,...,s:=M・f→Tと、値s:=w・f→Tと、所定の値θ(iは行列Mの各行番号とX)とに基づき、i=1,...,Lの各整数iについての要素cと、要素cとを生成する暗号化データ生成部であって、
行列Mの各行番号を表す各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,1の係数としてs+θi,1を設定するとともに、前記識別情報tとi’=2,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてθi,i’を設定して要素cを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tとi’=1,...,nの各整数i’とが示す基底ベクトルbt,i’の係数としてsi,i’を設定して要素cを生成し、
基底Bd+2の基底ベクトルbd+2,p’(p’は前記p’)にs−θmを設定するとともに、基底ベクトルbd+2,q’(q’は前記q’)にθを設定して要素cを生成する暗号化データ生成部と、
行列Mの各行番号とXとを示す各整数iについて、数22に示すペアリング演算を行い、前記署名データsigの正当性を検証するペアリング演算部と
を備えることを特徴とする検証装置。
【数21】

【数22】


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

【図22】
image rotate


【公開番号】特開2011−232475(P2011−232475A)
【公開日】平成23年11月17日(2011.11.17)
【国際特許分類】
【出願番号】特願2010−101657(P2010−101657)
【出願日】平成22年4月27日(2010.4.27)
【出願人】(000006013)三菱電機株式会社 (33,312)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】