説明

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

【課題】システム全体のセキュリティが1つの機関に依存することのない分散多管理者関数型暗号を提供することを目的とする。
【解決手段】複数の鍵生成装置100のうち、任意の1つの鍵生成装置100がgparamを生成し、各鍵生成装置100がgparamに基づき管理者公開鍵apkと管理者秘密鍵askとを生成する。そして、複数の鍵生成装置100うち少なくとも一部の鍵生成装置100が、管理者秘密鍵askに基づきユーザの復号鍵uskgid,(t,xt)の一片を生成する。ユーザは、少なくとも一部の鍵生成装置100が生成した復号鍵uskgid,(t,xt)を合わせて1つの復号鍵として、暗号化データctを復号する。

【発明の詳細な説明】
【技術分野】
【0001】
この発明は、分散多管理者関数型暗号(Decentralized Multi−Authority Functional Encryption)に関するものである。
【背景技術】
【0002】
非特許文献31には、関数型暗号に関する記載がある。
非特許文献12,13,25,26,28には、多管理者属性ベース暗号(Multi−Authority Attribute−Based Encryption)についての記載がある。なお、属性ベース暗号は、関数型暗号の1つのクラスである。
非特許文献25には、分散多管理者属性ベース暗号についての記載がある。
【先行技術文献】
【非特許文献】
【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 Symposiumon 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 Heidelberg (2004)
【非特許文献12】Chase, M.: Multi−authority attribute based encryption. TCC, LNCS, pp. 515・34, Springer Heidelberg(2007).
【非特許文献13】Chase, M. and Chow, S.: Improving privacy and security in multi−authority attribute−based encryption,ACM Conference on Computer and Communications Security, pp. 121・30, ACM (2009).
【非特許文献14】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)
【非特許文献15】Estibals, N.: Compact hardware for computing the Tate pairing over 128−bit−security supersingular curves,IACR ePrint Archive: Report 2010/371 (2010).
【非特許文献16】SECURE HASH STANDARD, FIPS PUB 180−1, 180−2, NIST, USA (1995,2002)
【非特許文献17】Gentry, C.: Practical identity−based encryption without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT2006. LNCS, vol. 4004, pp. 445・64. Springer Heidelberg (2006)
【非特許文献18】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)
【非特許文献19】Gentry, C., Silverberg, A.: Hierarchical ID−based cryptography. In: Zheng, Y. (ed.) ASIACRYPT 2002.LNCS, vol. 2501, pp. 548・66. Springer Heidelberg (2002)
【非特許文献20】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)
【非特許文献21】ISO/IEC 15946−5, Information technology ・Security techniques ・Cryptographic techniques based on elliptic curves ・Part 5: Elliptic curve generation (2009).
【非特許文献22】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)
【非特許文献23】Lewko, A., Okamoto, T., Sahai, A., Takashima, K., Waters, B.: Fully secure functional encryption:Attribute−based encryption and (hierarchical) inner product encryption, EUROCRYPT 2010. LNCS, Springer Heidelberg (2010)
【非特許文献24】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)
【非特許文献25】Lewko, A.B., Waters, B.: Decentralizing Attribute−Based Encryption, IACR ePrint Archive: Report 2010/351 (2010).
【非特許文献26】H. Lin, Z. Cao, X. Liang, and J. Shao.: Secure threshold multi authority attribute based encryption without a central authority, INDOCRYPT, LNCS, vol. 5365, pp. 426・36, Springer Heidelberg (2008).
【非特許文献27】Maji, H., Prabhakaran, M., Rosulek, M.: Attribute−Based Signatures. http://www.cs.uiuc.edu/〜mmp/research.html
【非特許文献28】S. Muller, S. Katzenbeisser, and C. Eckert.; On multi−authority ciphertext−policy attribute−based encryption,Bull. Korean Math Soc. 46, No.4, pp. 803・19 (2009).
【非特許文献29】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)
【非特許文献30】Okamoto, T., Takashima, K.: Hierarchical predicate encryption for inner−products, In: ASIACRYPT 2009,Springer Heidelberg (2009)
【非特許文献31】Okamoto, T., Takashima, K.: Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption, In: CRYPTO 2010, Springer Heidelberg (2010)
【非特許文献32】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)
【非特許文献33】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)
【非特許文献34】Sahai, A., Waters, B.: Fuzzy identity−based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457・73. Springer Heidelberg (2005)
【非特許文献35】Shi, E., Waters, B.: Delegating capability in predicate encryption systems. In: Aceto, L., Damg「ェard, I.,Goldberg, L.A., Halldorsson, M.M., Ingolfsdottir, A., Walukiewicz, I. (eds.) ICALP (2) 2008. LNCS, vol.5126, pp. 560.578. Springer Heidelberg (2008)
【非特許文献36】Waters, B.: Efficient identity based encryption without random oracles. Eurocrypt 2005, LNCS, vol. 3152, pp.443・59. Springer Verlag, (2005)
【非特許文献37】Waters, B.: Ciphertext−policy attribute−based encryption: an expressive, efficient, and provably secure realization. ePrint, IACR, http://eprint.iacr.org/2008/290
【非特許文献38】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】
関数型暗号には、システム全体のセキュリティが1つの機関に依存するという課題がある。
この発明は、システム全体のセキュリティが1つの機関に依存することのない分散多管理者関数型暗号を提供することを目的とする。
【課題を解決するための手段】
【0005】
この発明に係る暗号処理システムは、
d個(dは1以上の整数)の鍵生成装置と、暗号化装置と、復号装置とを備え、t=1,...,dの少なくとも1つ以上の整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムであり、
前記d個の鍵生成装置の各鍵生成装置は、
t=1,...,dのうち鍵生成装置毎に予め定められた整数tについての属性情報x:=(xt,i)(i=1,...,n,nは1以上の整数)を入力する第1情報入力部と、
前記整数tと、前記第1情報入力部が入力した属性情報xと、所定の値δと、基底Bの基底ベクトルbt,i(i=1,...,2n)とに基づき、数1に示すベクトルを含む鍵要素kを生成する鍵要素生成部と、
前記鍵要素生成部が生成した鍵要素kと、前記属性情報xとを含む復号鍵uskを前記復号装置へ送信する復号鍵送信部と
を備え、
前記暗号化装置は、
i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性情報v:=(vi,i’)(i’=1,...,n)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)と、L行r列(rは1以上の整数)の所定の行列Mとを入力する第2情報入力部と、
r個の要素を有するベクトルfと、前記第2情報入力部が入力した行列Mとに基づき列ベクトルs→T:=(s,...,s:=M・f→Tを生成するとともに、s:=h・f→Tとして、s=h・(f’)であるr個の要素を有するベクトルf’と、前記行列Mとに基づき列ベクトル(s’):=(s’,...,s’):=M・(f’)を生成するベクトル生成部と、
前記ベクトル生成部が生成した列ベクトルs→T及び列ベクトル(s’)と、i=1,...,Lの各整数iについての所定の値θ,θ’とに基づき、i=1,...,Lの各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,i’(i’=1,...,2n)を用いて、数2に示すベクトルを含む暗号要素cを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tが示す基底ベクトルbt,i(i=1,...,2n)を用いて、数3に示すベクトルを含む暗号要素cを生成する暗号要素c生成部と、
前記暗号要素c生成部が生成したi=1,...,Lの各整数iについての暗号要素cと、前記変数ρ(i)と、前記行列Mとを含む暗号化データctを前記復号装置へ送信する暗号化データ送信部と
を備え、
前記復号装置は、
前記d個の鍵生成装置のうち、少なくとも1つ以上の鍵生成装置の前記復号鍵送信部が送信した復号鍵uskを受信する復号鍵受信部と、
前記暗号化データ送信部が送信した暗号化データctを受信するデータ受信部と、
前記復号鍵受信部が受信した復号鍵uskに含まれる属性情報xと、前記データ受信部が受信した暗号化データctに含まれる変数ρ(i)とに基づき、i=1,...,Lの各整数iのうち、変数ρ(i)が肯定形の組(t,v)であり、かつ、その組の識別情報tが示すxを含む復号鍵uskを前記復号鍵受信部が受信しており、かつ、その組のvと、その組の識別情報tが示す属性情報xとの内積が0となるiと、変数ρ(i)が否定形の組¬(t,v)であり、かつ、その組の識別情報tが示すxを含む復号鍵uskを前記復号鍵受信部が受信しており、かつ、その組のvと、その組の識別情報tが示す属性情報xとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、前記暗号化データctに含まれる行列Mのi行目の要素であるMに基づき、αを合計した場合に所定のベクトルhとなる補完係数αを計算する補完係数計算部と、
前記補完係数計算部が計算した集合Iと補完係数αとに基づき、前記暗号化データctに含まれる暗号要素cと、前記復号鍵uskに含まれる鍵要素kとについて、数4に示すペアリング演算を行い、前記所定の情報Kを計算するペアリング演算部と
を備えることを特徴とする。
【数1】

【数2】

【数3】

【数4】

【発明の効果】
【0006】
この発明に係る暗号処理システムでは、複数の鍵生成装置それぞれが復号鍵の一片を生成する。したがって、一部の鍵生成装置のセキュリティが破られても、復号鍵の一片の機能が失われるだけであり、システム全体のセキュリティが破られることにはならない。
【図面の簡単な説明】
【0007】
【図1】多管理者の説明図。
【図2】行列M^の説明図。
【図3】行列Mδの説明図。
【図4】sの説明図。
【図5】s→Tの説明図。
【図6】分散多管理者関数型暗号を実行する暗号処理システム10の構成図。
【図7】鍵生成装置100の機能を示す機能ブロック図。
【図8】暗号化装置200の機能を示す機能ブロック図。
【図9】復号装置300の機能を示す機能ブロック図。
【図10】GSetupアルゴリズムの処理を示すフローチャート。
【図11】ASetupアルゴリズムの処理を示すフローチャート。
【図12】AttrGenアルゴリズムの処理を示すフローチャート。
【図13】Encアルゴリズムの処理を示すフローチャート。
【図14】Decアルゴリズムの処理を示すフローチャート。
【図15】鍵生成装置100、暗号化装置200、復号装置300のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【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の転置行列を表す。
数110に示す基底Bと基底Bとに対して、数111である。
【数110】

【数111】

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

【0010】
また、以下の説明において、“nt”が下付き又は上付きで示されている場合、このntはnを意味する。同様に、“Vt”が下付き又は上付きで示されている場合、このVtはVを意味する。同様に、“δi,j”が上付きで示されている場合、このδi,jは、δi,jを意味する。
また、ベクトルを意味する“→”が下付き文字又は上付き文字に付されている場合、この“→”は下付き文字又は上付き文字に上付きで付されていることを意味する。
また、復号鍵uskgid,(t,xt)におけるxtは、xのことである。
【0011】
また、以下の説明において、暗号処理とは、鍵生成処理、暗号化処理、復号処理を含むものである。
【0012】
実施の形態1.
この実施の形態では、「分散多管理者関数型暗号」を実現する基礎となる概念を説明した上で、分散多管理者関数型暗号の構成について説明する。
第1に、分散多管理者関数型暗号について簡単に説明する。まず、関数型暗号について説明する。次に、分散多管理者について説明する。
第2に、関数型暗号を実現するための空間である「双対ペアリングベクトル空間(Dual Pairing Vector Spaces,DPVS)」という豊かな数学的構造を有する空間を説明する。
第3に、関数型暗号を実現するための概念を説明する。ここでは、「スパンプログラム(Span Program)」、「属性ベクトルの内積とアクセスストラクチャ」、「秘密分散(秘密共有)」について説明する。
第4に、この実施の形態に係る「分散多管理者関数型暗号」を説明する。まず、「分散多管理者関数型暗号」の基本構成について説明する。次に、この「分散多管理者関数型暗号」を実現する「暗号処理システム10」の基本構成について説明する。そして、この実施の形態に係る「分散多管理者関数型暗号」及び「暗号処理システム10」について詳細に説明する。
【0013】
<第1.分散多管理者関数型暗号>
<第1−1.関数型暗号>
関数型暗号は、公開鍵暗号の概念を発展させ、きめ細かくした暗号である。関数型暗号は、IDベース暗号(Identity−Based Encryption,IBE)(非特許文献3,4,6,14,17参照)、秘匿ベクトル暗号(Hidden−Vector Encryption)(非特許文献9参照)、述語暗号(Predicate Encryption)(非特許文献22)、属性ベース暗号(Attribute−Based Encryption,ABE)(特許文献2,20,32−34)を特別な場合として包含する暗号方式である。
【0014】
関数型暗号では、復号鍵skψ(秘密鍵)はパラメータψに関連付けられている。そして、メッセージmは、パラメータψとは異なるパラメータγを伴う公開鍵pkを用いて暗号文Enc(m,pk,γ)に暗号化される。関係R(ψ,γ)が成立する場合に限り、復号鍵skψは暗号文Enc(m,pk,γ)を復号することができる。
【0015】
関数型暗号では、管理者(Authority)と呼ばれる信頼された機関が必要である。管理者は、公開鍵pkとマスター秘密鍵mskとのペアを生成する。公開鍵pkはシステムパラメータとして配布され、マスター秘密鍵はユーザのパラメータψに関連付けられたユーザの復号鍵skψを生成するのに用いられる。
【0016】
IDベース暗号の場合、パラメータψは、ユーザのIDであり、関係Rは等号関係である。つまり、関係R(ψ、γ)はψ=γの場合に限り成立する。
一般的なアクセスストラクチャに対するCP(Ciphertext−Policy)属性ベース暗号の場合、パラメータψはユーザの属性の組(x,...,x)であり、関係R(・,γ)は一般的なアクセスストラクチャである。より正確には、関係R(・,γ)は(M^,(v,...,v))によって表される。そして、属性の要素の要素毎の等号関係、つまり{x=vt∈{1,...,i}が(モノトーン)スパンプログラムM^に入力され、関係R(ψ,γ)は(T(x=v),...,T(x=v))の新の値のベクトルがスパンプログラムM^に受理された場合に限り成立する。ここで、ψが真ならT(ψ):=1であり、ψが偽ならT(ψ):=0である。例えば、x=vならT(x=v):=1であり、x≠vならT(x=v):=0である。
【0017】
関数型暗号には多くのアプリケーションが存在する。しかし、関数型暗号の概念には、システム全体のセキュリティが1つの機関に依存するという大きな課題がある。言い換えると、管理者のセキュリティが破られたり、マスター秘密鍵が漏えいした場合、システム全体が機能しなくなってしまう。
【0018】
<第1−2.分散多管理者>
まず、「多管理者」について説明する。多管理者とは、ユーザの復号鍵を生成する管理者が複数存在するという意味である。
上述したように、通常の関数型暗号では、システム全体のセキュリティが1つの機関(管理者)に依存していた。しかし、多管理者とすることで、一部の管理者のセキュリティが破られたり、一部の管理者の秘密鍵(マスター鍵)が漏洩した場合であっても、システムの一部だけが機能しなくなるだけであり、他の部分については正常に機能する状態とすることができる。
【0019】
図1は、多管理者の説明図である。
図1では、役所が、住所、電話番号、年齢等の属性について管理する。また、警察が、運転免許の種別等の属性について管理する。また、会社Aが、会社Aにおける役職、会社Aにおける所属等の属性について管理する。そして、役所が管理する属性に関連付けられた復号鍵1は役所が発行し、警察が管理する属性に関連付けられた復号鍵2は警察が発行し、会社Aが管理する属性に関連付けられた復号鍵3は会社Aが発行する。
暗号文を復号する復号者は、役所、警察、会社A等の各管理者が発行した復号鍵1,2,3を合わせた復号鍵を用い、暗号文を復号する。つまり、復号者から見た場合、各管理者から発行された復号鍵を合わせたものが、自分に発行された1つの復号鍵となる。
例えば、会社Aのマスター鍵が漏洩した場合、暗号処理システムは、会社Aの属性に関しては機能しなくなるが、他の管理者が管理する属性に関しては機能する。つまり、会社Aが管理する属性については、指定した属性以外の属性のユーザによって復号されてしまう虞があるが、他の属性については、指定した属性のユーザによってのみ復号可能である。
【0020】
また、図1の例からも分かるように、関数型暗号では、複数の管理者が存在し、各管理者が属性におけるあるカテゴリー(部分空間)又は定義域を管理し、そのカテゴリーにおけるユーザの属性についての復号鍵(の一片)を発行することが自然である。
【0021】
次に、「分散(Decentralized)」について説明する。分散とは、どの機関も管理者となることができ、他の機関とやりとりすることなく、復号鍵(の一片)を発行することができ、各ユーザが他の機関とやりとりすることなく、管理者から復号鍵(の一片)を取得できることである。
例えば、中央管理者がいる場合、分散とは言えない。中央管理者とは、他の管理者よりも上位の管理者である。中央管理者のセキュリティが破られた場合、全ての管理者のセキュリティが破られてしまう。
【0022】
<第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である。
以下の説明において、数113を、1λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータparam:=(q,G,G,g,e)の値を出力するアルゴリズムとする。
【数113】

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

【数115】

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

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

【数118】

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

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

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

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

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

なお、定数{α}は、行列Mのサイズにおける多項式時間で計算可能である。
【0041】
この実施の形態及び以下の実施の形態に係る関数型暗号方式は、上述したように、スパンプログラムに内積述語と秘密分散方式とを適用してアクセスストラクチャを構成する。そのため、スパンプログラムにおける行列Mや、内積述語における属性情報x及び属性情報v(述語情報)を設計するにより、アクセス制御を自由に設計することができる。つまり、非常に高い自由度でアクセス制御の設計を行うことができる。なお、行列Mの設計は、秘密分散方式の閾値等の条件設計に相当する。
例えば、属性ベース暗号方式は、この実施の形態関数型暗号方式におけるアクセスストラクチャにおいて、内積述語の設計をある条件に限定した場合に相当する。つまり、この実施の形態に係る関数型暗号方式におけるアクセスストラクチャに比べ、属性ベース暗号方式におけるアクセスストラクチャは、内積述語における属性情報x及び属性情報v(述語情報)の設計の自由度がない分、アクセス制御の設計の自由度が低い。なお、具体的には、属性ベース暗号方式は、属性情報{xt∈{1,...,d}と{vt∈{1,...,d}とを、等号関係に対する2次元ベクトル、例えばx:=(1,x)とv:=(v,−1)とに限定した場合に相当する。
【0042】
特に、この実施の形態及び以下の実施の形態に係る関数型暗号方式におけるアクセスストラクチャは、ノンモノトーンスパンプログラムを用いたノンモノトーンアクセスストラクチャを構成する。そのため、アクセス制御の設計の自由度がより高くなる。
具体的には、ノンモノトーンスパンプログラムには、否定形のリテラル(¬p)を含むため、否定形の条件を設定できる。例えば、第1会社には、A部とB部とC部とD部との4つの部署があったとする。ここで、第1会社のB部以外の部署の属するユーザにのみアクセス可能(復号可能)というアクセス制御をしたいとする。この場合に、否定形の条件の設定ができないとすると、「第1会社のA部とC部とD部とのいずれかに属すること」という条件を設定する必要がある。一方、否定形の条件の設定ができるとすると、「第1会社の社員であって、B部以外に属すること」という条件を設定することができる。つまり、否定形の条件が設定できることで、自然な条件設定が可能となる。なお、ここでは部署の数が少ないが、部署の数が多い場合等は非常に有効であることが分かる。
【0043】
<第4.分散多管理者関数型暗号の基本構成>
<第4−1.分散多管理者関数型暗号の基本構成>
分散多管理者関数型暗号の構成を簡単に説明する。
分散多管理者関数型暗号は、GSetup、ASetup、AttrGen、Enc、Decの5つのアルゴリズムを備える。
(GSetup)
GSetupアルゴリズムは、セキュリティパラメータλを入力として、グローバル公開パラメータgparamを出力する確率的アルゴリズムである。GSetupアルゴリズムは、ある1つの機関により実行される。グローバル公開パラメータgparamは公開される。
(ASetup)
ASetupアルゴリズムは、グローバル公開パラメータgparamと、管理者の識別情報tと、属性のフォーマットnとを入力として、管理者公開鍵apkと、管理者秘密鍵askとを出力する確率的アルゴリズムである。ASetupアルゴリズムは、1≦t≦dの少なくとも1つのtを識別情報として持つ管理者tによって実行される。管理者公開鍵apkは公開され、管理者秘密鍵askは管理者tによって保持される。
(AttrGen)
AttrGenアルゴリズムは、グローバル公開パラメータgparamと、管理者の識別情報tと、管理者秘密鍵askと、ユーザの識別情報gidと、属性x:=(xt,i)(i=1,...,n)∈Fとを入力として、復号鍵uskgid,(t,xt)を出力する確率的アルゴリズムである。AttrGenアルゴリズムは、識別情報gidが示すユーザに属性xに関連する復号鍵を管理者tが生成する場合に、管理者tによって実行される。管理者tは復号鍵uskgid,(t,xt)を識別情報gidが示すユーザに与える。
(Enc)
Encアルゴリズムは、グローバル公開パラメータgparamと、管理者公開鍵apkと、メッセージm∈Gと、アクセスストラクチャSとを入力として、暗号化データctを出力する確率的アルゴリズムである。Encアルゴリズムは、暗号化データctを生成するユーザによって実行される。
(Dec)
Decアルゴリズムは、グローバル公開パラメータgparamと、管理者公開鍵apkと、復号鍵uskgid,(t,xt)と、暗号化データctとを入力として、メッセージm、又は、識別情報⊥を出力するアルゴリズムである。Decアルゴリズムは、暗号化データctを復号するユーザによって実行される。
【0044】
<第4−2.暗号処理システム10>
上述した分散多管理者関数型暗号のアルゴリズムを実行する暗号処理システム10について説明する。
図6は、分散多管理者関数型暗号を実行する暗号処理システム10の構成図である。
いずれか(1つ)の鍵生成装置100は、セキュリティパラメータλを入力としてGSetupアルゴリズムを実行して、グローバル公開パラメータgparamを生成する。そして、その鍵生成装置100は、生成したグローバル公開パラメータgparamを公開する。
各鍵生成装置100は、グローバル公開パラメータgparamと、その鍵生成装置100に割り当てられた識別情報tと、属性のフォーマットnとを入力としてASetupアルゴリズムを実行して、管理者公開鍵apkと、管理者秘密鍵askとを生成する。そして、各鍵生成装置100は、グローバル公開パラメータgparamと、その鍵生成装置100に割り当てられた識別情報tと、管理者秘密鍵askと、ユーザの識別情報gidと、属性x:=(xt,i)(i=1,...,n)∈Fとを入力としてAttrGenアルゴリズムを実行して、復号鍵uskgid,(t,xt)を生成して復号装置300へ秘密裡に配布する。
暗号化装置200は、グローバル公開パラメータgparamと、管理者公開鍵apkと、メッセージm∈Gと、アクセスストラクチャSとを入力としてEncアルゴリズムを実行して、暗号化データctを生成する。暗号化装置200は、生成した暗号化データctを復号装置300へ送信する。
復号装置300は、グローバル公開パラメータgparamと、管理者公開鍵apkと、復号鍵uskgid,(t,xt)と、暗号化データctとを入力としてDecアルゴリズムを実行して、メッセージm、又は、識別情報⊥を出力する。
【0045】
<第4−3.分散多管理者関数型暗号及び暗号処理システム10の詳細>
図7から図14に基づき、実施の形態1に係る分散多管理者関数型暗号、及び、分散多管理者関数型暗号を実行する暗号処理システム10の機能と動作とについて説明する。
図7は、鍵生成装置100の機能を示す機能ブロック図である。図8は、暗号化装置200の機能を示す機能ブロック図である。図9は、復号装置300の機能を示す機能ブロック図である。
図10から図12は、鍵生成装置100の動作を示すフローチャートである。なお、図10はGSetupアルゴリズムの処理を示すフローチャートであり、図11はASetupアルゴリズムの処理を示すフローチャートであり、図12はAttrGenアルゴリズムの処理を示すフローチャートである。図13は、暗号化装置200の動作を示すフローチャートであり、Encアルゴリズムの処理を示すフローチャートである。図14は、復号装置300の動作を示すフローチャートであり、Decアルゴリズムの処理を示すフローチャートである。
【0046】
鍵生成装置100の機能と動作とについて説明する。
図7に示すように、鍵生成装置100は、マスター鍵生成部110、マスター鍵記憶部120、情報入力部130(第1情報入力部)、復号鍵生成部140、鍵配布部150(復号鍵送信部)を備える。
また、マスター鍵生成部110は、グローバルパラメータ生成部111、管理者秘密鍵生成部112を備える。復号鍵生成部140は、乱数生成部141、鍵要素生成部142を備える。
【0047】
まず、図10に基づき、鍵生成装置100が実行するGSetupアルゴリズムの処理について説明する。なお、上述したように、GSetupアルゴリズムは、複数の鍵生成装置100のうち1つの鍵生成装置100が実行すればよい。
(S101:セキュリティパラメータ入力ステップ)
グローバルパラメータ生成部111は、入力装置により、セキュリティパラメータλ(1λ)を入力する。
【0048】
(S102:双線形ペアリング群生成ステップ)
グローバルパラメータ生成部111は、処理装置により、S101で入力したセキュリティパラメータλ(1λ)を入力としてアルゴリズムGbpgを実行して、ランダムに双線形ペアリング群のパラメータparam:=(q,G,G,g,e)の値を生成する。
【0049】
(S103:パラメータ生成ステップ)
ハッシュ関数Hを、数124に示すハッシュ関数とする。
【数124】

グローバルパラメータ生成部111は、処理装置により、数125に示すグローバルパラメータgparamの要素G,Gを生成する。
【数125】

また、グローバルパラメータ生成部111は、g:=e(G,G)する。
【0050】
(S104:パラメータ記憶ステップ)
マスター鍵記憶部120は、(S102)で生成したparamと、(S103)で設定したハッシュ関数Hと、要素G,Gと、値gとを、グローバルパラメータgparamとして記憶装置に記憶する。
【0051】
つまり、(S101)から(S103)において、鍵生成装置100は数126に示すGSetupアルゴリズムを実行して、グローバルパラメータgparamを生成する。そして、(S104)で、鍵生成装置100は生成されたグローバルパラメータgparamを記憶装置に記憶する。
なお、グローバルパラメータgparamは、例えば、ネットワークを介して公開され、他の鍵生成装置100や暗号化装置200や復号装置300が取得可能な状態にされる。
【数126】

【0052】
次に、図11に基づき、鍵生成装置100が実行するASetupアルゴリズムの処理について説明する。なお、上述したように、ASetupアルゴリズムは、複数の鍵生成装置100全てが実行してもよいし、複数の鍵生成装置100のうち一部の鍵生成装置100だけが実行してもよい。
(S201:情報入力ステップ)
情報入力部130は、入力装置により、自己(その鍵生成装置100)に割り当てられた識別情報tを入力する。なお、各鍵生成装置100には、それぞれ異なる識別情報tが割り当てられている。
また、情報入力部130は、例えば、通信装置によりネットワークを介して、グローバルパラメータgparamを取得する。なお、自己がグローバルパラメータgparamを生成した鍵生成装置100である場合には、グローバルパラメータgparamをマスター鍵記憶部120から読み出せばよい。
【0053】
(S202:空間生成ステップ)
管理者秘密鍵生成部112は、処理装置により、セキュリティパラメータλ(1λ)と、N=2n+u+w+zと、param:=(q,G,G,g,e)の値とを入力としてアルゴリズムGdpvsを実行して、双対ペアリングベクトル空間のパラメータparamVt:=(q,V,G,A,e)の値を生成する。
なお、n,u,w,zは、1以上の整数である。
【0054】
(S203:基底U生成ステップ)
管理者秘密鍵生成部112は、処理装置により、j=0,1の各整数jについて、基底Uを数127に示すように生成する。
【数127】

【0055】
(S204:線形変換生成ステップ)
管理者秘密鍵生成部112は、処理装置により、Nと、Fとを入力として、線形変換X:=(χt,i,ji,jを数128に示すようにランダムに生成する。
【数128】

なお、GLは、General Linearの略である。つまり、GLは、一般線形群であり、行列式が0でない正方行列の集合であり、乗法に関し群である。また、(χt,i,ji,jは、行列χt,i,jの添え字i,jに関する行列という意味であり、ここでは、i,j=1,...,Nである。
【0056】
(S205:基底B生成ステップ)
管理者秘密鍵生成部112は、処理装置により、基底B及び基底Bを数129に示すように生成する。
【数129】

【0057】
(S206:基底B^生成ステップ)
管理者秘密鍵生成部112は、処理装置により、基底Bの部分基底B^と、基底Bの部分基底B^とを数130に示すように生成する。
【数130】

【0058】
(S207:マスター鍵記憶ステップ)
マスター鍵記憶部120は、(S202)で生成したパラメータparamVtと、(S206)で生成した部分基底B^とを管理者公開鍵apkとして記憶装置に記憶する。また、マスター鍵記憶部120は、(S204)で生成した線形変換Xを管理者秘密鍵askとして記憶装置に記憶する。
【0059】
つまり、(S201)から(S206)において、鍵生成装置100は数131に示すASetupアルゴリズムを実行して、管理者公開鍵apkと管理者秘密鍵askとを生成する。そして、(S207)で、鍵生成装置100は生成された管理者公開鍵apkと管理者秘密鍵askとを記憶装置に記憶する。
なお、管理者公開鍵apkは、例えば、ネットワークを介して公開され、暗号化装置200や復号装置300が取得可能な状態にされる。
【数131】

【0060】
次に、図12に基づき、鍵生成装置100が実行するAttrGenアルゴリズムの処理について説明する。なお、上述したように、AttrGenアルゴリズムは、複数の鍵生成装置100のうち、ASetupアルゴリズムを実行した鍵生成装置100が実行する。
(S301:情報入力ステップ)
情報入力部130は、入力装置により、自己(その鍵生成装置100)に割り当てられた識別情報tと、復号鍵を発行するユーザの識別情報gidと、数132に示す属性情報x:=(xt,i)(i=1,...,n)とを入力する。
また、情報入力部130は、例えば、通信装置によりネットワークを介して、グローバルパラメータgparamを取得する。なお、自己がグローバルパラメータgparamを生成した鍵生成装置100である場合には、グローバルパラメータgparamをマスター鍵記憶部120から読み出せばよい。
また、情報入力部130は、マスター鍵記憶部120から管理者秘密鍵askを読み出す。
【数132】

【0061】
(S302:乱数生成ステップ)
乱数生成部141は、処理装置により、識別情報tについて、乱数φを数133に示すように生成する。
【数133】

【0062】
(S303:鍵要素生成ステップ)
数134であるとする。
【数134】

鍵要素生成部142は、処理装置により、識別情報tについて、復号鍵uskgid,(t,xt)の要素である鍵要素kを数135に示すように生成する。
【数135】

なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数135は、以下のように、基底Bの基底ベクトルの係数が設定されることを意味する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。
基底ベクトル1,...,nの係数として(δ+1)xt,1,...,(δ+1)xt,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,2nの係数として−δxt,1,...,−δxt,nt(ここで、ntはnのことである)が設定される。基底ベクトル2n+1,...,2n+uの係数として0が設定される。基底ベクトル2n+u+1,...,2n+u+wの係数として乱数φt、1,...,φt,wt(ここで、wtはwのことである)が設定される。基底ベクトル2n+u+w+1,...,2n+u+w+zの係数として0が設定される。
【0063】
(S304:鍵配布ステップ)
鍵配布部150は、ユーザの識別情報gidと、識別情報t及び属性情報xと、鍵要素kとを要素とする復号鍵uskgid,(t,xt)を、例えば通信装置によりネットワークを介して秘密裡に復号装置300へ配布する。もちろん、復号鍵uskgid,(t,xt)は、他の方法により復号装置300へ配布されてもよい。
【0064】
つまり、(S301)から(S303)において、鍵生成装置100は数136に示すAttrGenアルゴリズムを実行して、復号鍵uskgid,(t,xt)を生成する。そして、(S304)で、鍵生成装置100は生成された復号鍵uskgid,(t,xt)を復号装置300へ配布する。
【数136】

【0065】
暗号化装置200の機能と動作とについて説明する。
図8に示すように、暗号化装置200は、公開鍵取得部210、情報入力部220(第2情報入力部)、暗号化データ生成部230、暗号化データ送信部240を備える。
また、情報入力部220は、属性情報入力部221、メッセージ入力部222を備える。また、暗号化データ生成部230は、乱数生成部231、fベクトル生成部232、sベクトル生成部233、暗号要素c生成部234、暗号要素cd+1生成部235を備える。
【0066】
図13に基づき、暗号化装置200が実行するEncアルゴリズムの処理について説明する。
(S401:公開鍵取得ステップ)
公開鍵取得部210は、例えば、通信装置によりネットワークを介して、各鍵生成装置100が生成した管理者公開鍵apkを取得する。また、公開鍵取得部210は、鍵生成装置100が生成したグローバルパラメータgparamを取得する。
【0067】
(S402:情報入力ステップ)
属性情報入力部221は、入力装置により、アクセスストラクチャS:=(M,ρ)を入力する。なお、行列Mは、L行×r列の行列である。L,rは、1以上の整数である。
また、メッセージ入力部222は、入力装置により、暗号化するメッセージmを入力する。
なお、アクセスストラクチャSの設定については、実現したいシステムの条件に応じて設定されるものである。
【0068】
(S403:fベクトル生成ステップ)
fベクトル生成部232は、処理装置により、r個の要素を有するベクトルfを数137に示すようにランダムに生成する。
【数137】

【0069】
(S404:sベクトル生成ステップ)
sベクトル生成部233は、処理装置により、(S402)で入力したアクセスストラクチャSの(L行×r列)の行列Mと、(S403)で生成したr個の要素を有するベクトルfとに基づき、ベクトルs→Tを数138に示すように生成する。
【数138】

また、sベクトル生成部233は、処理装置により、(S403)で生成したベクトルfに基づき、値sを数139に示すように生成する。なお、1は、全ての要素が値1のベクトルである。
【数139】

【0070】
(S405:f’ベクトル生成ステップ)
fベクトル生成部232は、処理装置により、r個の要素を有するベクトルf’を数140に示すようにs=1・f’という条件下でランダムに生成する。
【数140】

【0071】
(S406:s’ベクトル生成ステップ)
sベクトル生成部233は、処理装置により、(S402)で入力したアクセスストラクチャSの(L行×r列)の行列Mと、r個の要素を有するベクトルf’とに基づき、(S405)で生成したベクトル(s’)を数141に示すように生成する。
【数141】

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

【0072】
(S408:暗号要素c生成ステップ)
暗号要素生成部234は、処理装置により、i=1,...,Lの各整数iについて、暗号化データctの要素である暗号要素cを数143に示すように生成する。
【数143】

なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数143は、以下のように、基底Bの基底ベクトルの係数が設定されることを意味する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。
ρ(i)が肯定形の組(t,v)である場合には、基底ベクトル1の係数としてs+θi,1が設定される。基底ベクトル2,...,nの係数としてθi,2,...,θi,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1の係数としてs’+θ’vi,1が設定される。基底ベクトルn+2,...,2nの係数としてθ’vi,2,...,θ’vi,nt(ここで、ntはnのことである)が設定される。基底ベクトル2n+1,...,2n+u+wの係数として0が設定される。基底ベクトル2n+u+w+1,...,2n+u+w+zの係数としてηi,1,...,ηi,zt(ここで、ztはzのことである)が設定される。
一方、ρ(i)が否定形の組¬(t,v)である場合には、基底ベクトル1,...,nの係数としてsi,1,...,si,nt(ここで、ntはnのことである)が設定される。基底ベクトルn+1,...,2nの係数としてs’vi,1,...,s’vi,nt(ここで、ntはnのことである)が設定される。基底ベクトル2n+1,...,2n+u+wの係数として0が設定される。基底ベクトル2n+u+w+1,...,2n+u+w+zの係数としてηi,1,...,ηi,zt(ここで、ztはzのことである)が設定される。
【0073】
(S409:暗号要素cd+1生成ステップ)
暗号要素cd+1生成部235は、処理装置により、暗号化データctの要素である暗号要素cd+1を数144に示すように生成する。
【数144】

【0074】
(S410:データ送信ステップ)
暗号化データ送信部240は、アクセスストラクチャS:=(M,ρ)と、暗号要素c(i=1,...,L)と、暗号要素cd+1とを含む暗号化データctを、例えば通信装置によりネットワークを介して復号装置300へ送信する。もちろん、暗号化データctは、他の方法により復号装置300へ送信されてもよい。
【0075】
つまり、(S401)から(S409)において、暗号化装置200は数145に示すEncアルゴリズムを実行して、暗号化データctを生成する。そして、(S410)で、暗号化装置200は生成された暗号化データctを復号装置300へ配布する。
【数145】

【0076】
復号装置300の機能と動作とについて説明する。
図9に示すように、復号装置300は、復号鍵受信部310(復号鍵取得部)、データ受信部320(データ取得部)、スパンプログラム計算部330、補完係数計算部340、ペアリング演算部350、メッセージ計算部360を備える。
【0077】
図14に基づき、Decアルゴリズムの処理について説明する。
(S501:復号鍵取得ステップ)
復号鍵受信部310は、例えば、通信装置によりネットワークを介して、鍵生成装置100から配布された復号鍵uskgid,(t,xt)を受信する。また、復号鍵受信部310は、鍵生成装置100が生成した管理者公開鍵apkを受信する。
【0078】
(S502:データ受信ステップ)
データ受信部320は、例えば、通信装置によりネットワークを介して、暗号化装置200が送信した暗号化データctを受信する。
【0079】
(S503:スパンプログラム計算ステップ)
スパンプログラム計算部330は、処理装置により、(S502)で受信した暗号化データctに含まれるアクセスストラクチャSが、(S501)で取得した復号鍵uskgid,(t,xt)に含まれる属性情報xの集合Γを受理するか否かを判定する。アクセスストラクチャSがΓを受理するか否かの判定方法は、「第3.関数型暗号を実現するための概念」で説明した通りである。
スパンプログラム計算部330は、アクセスストラクチャSがΓを受理する場合(S503で受理)、処理を(S504)へ進める。一方、アクセスストラクチャSがΓを拒絶する場合(S503で拒絶)、暗号化データctを復号鍵uskgid,(t,xt)で復号できないとして処理を終了する。
【0080】
(S504:補完係数計算ステップ)
補完係数計算部340は、処理装置により、数146となるIと、定数(補完係数){αi∈Iとを計算する。
【数146】

【0081】
(S505:ペアリング演算ステップ)
ペアリング演算部350は、処理装置により、数147を計算して、セッション鍵K=gs0(ここで、s0はsのことである)を生成する。
【数147】

なお、数148に示すように、数147を計算することにより鍵K=gs0(ここで、s0はsのことである)が得られる。
【数148】

【0082】
(S506:メッセージ計算ステップ)
メッセージ計算部360は、処理装置により、m’=cd+1/Kを計算して、メッセージm’(=m)を生成する。なお、cd+1は数144に示す通りgs0m(ここで、s0はsのことである)であり、Kはgs0(ここで、s0はsのことである)であるから、m’=cd+1/Kを計算すればメッセージmが得られる。
【0083】
つまり、(S501)から(S506)において、復号装置300は、数149に示すDecアルゴリズムを実行して、メッセージm’(=m)を生成する。
【数149】

【0084】
以上のように、実施の形態1に係る暗号処理システム10は、複数の鍵生成装置100が復号鍵を生成する多管理者関数型暗号方式を実現する。特に、暗号処理システム10が実現する署名方式は、中央管理者がいない分散多管理者関数型暗号方式である。
なお、実施の形態1に係る暗号処理システム10は、ノンモノトーン述語を伴う関数型暗号方式を実現する。
【0085】
なお、上記説明において、u、w、z(t=1,...,d)の次元は、安全性を高めるために設けた次元である。したがって、安全性が低くなってしまうが、u、w、z(t=1,...,d)をそれぞれ0として、u、w、z(t=1,...,d)の次元を設けなくてもよい。
【0086】
また、上記説明では、基底B及び基底Bの次元数をN:=2n+u+w+zに設定した。しかし、2n+u+w+zを2n+3n+2n+1(=7n+1)として、基底B及び基底Bの次元数を7n+1としてもよい。
この場合、数131に示すASetupアルゴリズムは、数150のように書き換えられる。
【数150】

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

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

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

【0090】
実施の形態1で説明した分散多管理者関数型暗号方式を、環Rを係数とする加群において実現すると数154から数158のようになる。
【数154】

【数155】

【数156】

【数157】

【数158】

【0091】
なお、安全性の証明の観点から、以上の実施の形態において、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)である。
【0092】
また、上記説明では、スパンプログラムM^は、入力列δによって行列M^から得られる行列Mδの行を線形結合して1が得られる場合に限り、入力列δを受理するとした。しかし、スパンプログラムM^は、1ではなく、他のベクトルhが得られる場合に限り、入力列δを受理するとしてもよい。
この場合、Encアルゴリズムにおいて、s:=1・f→Tではなく、s:=h・f→Tとし、s:=1・fではなく、s:=h・fとすればよい。
【0093】
次に、実施の形態における暗号処理システム10(鍵生成装置100、暗号化装置200、復号装置300)のハードウェア構成について説明する。
図15は、鍵生成装置100、暗号化装置200、復号装置300のハードウェア構成の一例を示す図である。
図15に示すように、鍵生成装置100、暗号化装置200、復号装置300は、プログラムを実行するCPU911(Central・Processing・Unit、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう)を備えている。CPU911は、バス912を介してROM913、RAM914、LCD901(Liquid Crystal Display)、キーボード902(K/B)、通信ボード915、磁気ディスク装置920と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置920(固定ディスク装置)の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置920は、所定の固定ディスクインタフェースを介して接続される。
【0094】
ROM913、磁気ディスク装置920は、不揮発性メモリの一例である。RAM914は、揮発性メモリの一例である。ROM913とRAM914と磁気ディスク装置920とは、記憶装置(メモリ)の一例である。また、キーボード902、通信ボード915は、入力装置の一例である。また、通信ボード915は、通信装置の一例である。さらに、LCD901は、表示装置の一例である。
【0095】
磁気ディスク装置920又はROM913などには、オペレーティングシステム921(OS)、ウィンドウシステム922、プログラム群923、ファイル群924が記憶されている。プログラム群923のプログラムは、CPU911、オペレーティングシステム921、ウィンドウシステム922により実行される。
【0096】
プログラム群923には、上記の説明において「マスター鍵生成部110」、「マスター鍵記憶部120」、「情報入力部130」、「復号鍵生成部140」、「鍵配布部150」、「公開鍵取得部210」、「情報入力部220」、「暗号化データ生成部230」、「暗号化データ送信部240」、「復号鍵受信部310」、「データ受信部320」、「スパンプログラム計算部330」、「補完係数計算部340」、「ペアリング演算部350」、「メッセージ計算部360」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、CPU911により読み出され実行される。
ファイル群924には、上記の説明において「グローバルパラメータgparam」、「管理者公開鍵apk」、「管理者秘密鍵ask」、「復号鍵uskgid,(t,xt)」、「暗号化データct」、「アクセスストラクチャS」、「属性情報」、「メッセージm」等の情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してCPU911によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのCPU911の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のCPU911の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【0097】
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、RAM914のメモリ、その他光ディスク等の記録媒体やICチップに記録される。また、データや信号は、バス912や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜回路」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ROM913に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ROM913等の記録媒体に記憶される。プログラムはCPU911により読み出され、CPU911により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
【符号の説明】
【0098】
100 鍵生成装置、110 マスター鍵生成部、111 グローバルパラメータ生成部、112 管理者秘密鍵生成部、120 マスター鍵記憶部、130 情報入力部、140 復号鍵生成部、141 乱数生成部、142 鍵要素生成部、150 鍵配布部、200 暗号化装置、210 公開鍵取得部、220 情報入力部、221 属性情報入力部、222 メッセージ入力部、230 暗号化データ生成部、231 乱数生成部、232 fベクトル生成部、233 sベクトル生成部、234 暗号要素c生成部、235 暗号要素cd+1生成部、240 暗号化データ送信部、300 復号装置、310 復号鍵受信部、320 データ受信部、330 スパンプログラム計算部、340 補完係数計算部、350 ペアリング演算部、360 メッセージ計算部。

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

【数2】

【数3】

【数4】

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

【数6】

【数7】

【請求項3】
前記暗号化装置は、さらに、
所定の整数iについて前記基底Bの基底ベクトルbt,iと前記基底Bの基底ベクトルbt,iとについてペアリング演算をして計算される値gと、前記sとに基づき、メッセージmを暗号化した数8に示す暗号要素cd+1を生成する暗号要素cd+1生成部
を備え、
前記暗号化データ送信部は、前記暗号要素cと、前記暗号要素cd+1生成部が生成した暗号要素cd+1とを含む暗号化データctを前記復号装置へ送信し、
前記復号装置は、さらに、
前記ペアリング演算部が計算した所定の情報Kで、前記暗号要素cd+1を除して、前記メッセージmを計算するメッセージ計算部
を備えることを特徴とする請求項1に記載の暗号処理システム。
【数8】

【請求項4】
t=1,...,d(dは1以上の整数)の少なくとも1つ以上の整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムにおいて、復号鍵uskを生成する鍵生成装置であり、
t=1,...,dのうち予め定められた整数tについての属性情報x:=(xt,i)(i=1,...,n,nは1以上の整数)を入力する第1情報入力部と、
前記整数tと、前記第1情報入力部が入力した属性情報xと、所定の値δと、基底Bの基底ベクトルbt,i(i=1,...,2n)とに基づき、数9に示すベクトルを含む鍵要素kを生成する鍵要素生成部と、
前記鍵要素生成部が生成した鍵要素kと、前記属性情報xとを含む復号鍵uskを復号装置へ送信する復号鍵送信部と
を備えることを特徴とする鍵生成装置。
【数9】

【請求項5】
t=1,...,d(dは1以上の整数)の少なくとも1つ以上の整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムにおいて、暗号化データctを生成する暗号化装置であり、
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と、前記第2情報入力部が入力した行列Mとに基づき列ベクトルs→T:=(s,...,s:=M・f→Tを生成するとともに、s:=h・f→Tとして、s=h・(f’)であるr個の要素を有するベクトルf’と、前記行列Mとに基づき列ベクトル(s’):=(s’,...,s’):=M・(f’)を生成するベクトル生成部と、
前記ベクトル生成部が生成した列ベクトルs→T及び列ベクトル(s’)と、i=1,...,Lの各整数iについての所定の値θ,θ’とに基づき、i=1,...,Lの各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,i’(i’=1,...,2n)を用いて、数10に示すベクトルを含む暗号要素cを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tが示す基底ベクトルbt,i(i=1,...,2n)を用いて、数11に示すベクトルを含む暗号要素cを生成する暗号要素c生成部と、
前記暗号要素c生成部が生成したi=1,...,Lの各整数iについての暗号要素cと、前記変数ρ(i)と、前記行列Mとを含む暗号化データctを復号装置へ送信する暗号化データ送信部と
を備えることを特徴とする暗号化装置。
【数10】

【数11】

【請求項6】
t=1,...,d(dは1以上の整数)の少なくとも1つ以上の整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理システムにおいて、暗号化データctを復号鍵uskで復号する復号装置であり、
t=1,...,dのうち少なくとも一部の整数tについて、属性情報x:=(xt,i)(i=1,...,n,nは1以上の整数)と、数12に示すベクトルを含むように生成された鍵要素kとを含む復号鍵uskを受信する復号鍵受信部と、
i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性情報v:=(vi,i’)(i’=1,...,n)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)と、L行r列(rは1以上の整数)の所定の行列Mと、i=1,...,Lの各整数iについて数13に示すベクトルを含むように生成された暗号要素cとを含む暗号化データctを受信するデータ受信部と、
前記復号鍵受信部が受信した復号鍵uskに含まれる属性情報xと、前記データ受信部が受信した暗号化データctに含まれる変数ρ(i)とに基づき、i=1,...,Lの各整数iのうち、変数ρ(i)が肯定形の組(t,v)であり、かつ、その組の識別情報tが示すxを含む復号鍵uskを前記復号鍵受信部が受信しており、かつ、その組のvと、その組の識別情報tが示す属性情報xとの内積が0となるiと、変数ρ(i)が否定形の組¬(t,v)であり、かつ、その組の識別情報tが示すxを含む復号鍵uskを前記復号鍵受信部が受信しており、かつ、その組のvと、その組の識別情報tが示す属性情報xとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、前記暗号化データctに含まれる行列Mのi行目の要素であるMに基づき、αを合計した場合に所定のベクトルhとなる補完係数αを計算する補完係数計算部と、
前記補完係数計算部が計算した集合Iと補完係数αとに基づき、前記暗号化データctに含まれる暗号要素cと、前記復号鍵uskに含まれる鍵要素kとについて、数14に示すペアリング演算を行い、前記所定の情報Kを計算するペアリング演算部と
を備えることを特徴とする復号装置。
【数12】

【数13】

【数14】

【請求項7】
t=1,...,d(dは1以上の整数)の少なくとも1つ以上の整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理方法であり、
複数の鍵生成装置のうち少なくとも1つ以上の鍵生成装置が、t=1,...,dのうち鍵生成装置毎に予め定められた整数tについての属性情報x:=(xt,i)(i=1,...,n,nは1以上の整数)を入力する第1情報入力工程と、
前記1つ以上の鍵生成装置が、前記整数tと、前記第1情報入力工程で入力された属性情報xと、所定の値δと、基底Bの基底ベクトルbt,i(i=1,...,2n)とに基づき、数15に示すベクトルを含む鍵要素kを生成する鍵要素生成工程と、
前記1つ以上の鍵生成装置が、前記鍵要素生成工程で生成された鍵要素kと、前記属性情報xとを含む復号鍵uskを復号装置へ送信する復号鍵送信工程と、
暗号化装置が、i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性情報v:=(vi,i’)(i’=1,...,n)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)と、L行r列(rは1以上の整数)の所定の行列Mとを入力する第2情報入力工程と、
前記暗号化装置が、r個の要素を有するベクトルfと、前記第2情報入力工程で入力された行列Mとに基づき列ベクトルs→T:=(s,...,s:=M・f→Tを生成するとともに、s:=h・f→Tとして、s=h・(f’)であるr個の要素を有するベクトルf’と、前記行列Mとに基づき列ベクトル(s’):=(s’,...,s’):=M・(f’)を生成するベクトル生成工程と、
前記暗号化装置が、前記ベクトル生成工程で生成された列ベクトルs→T及び列ベクトル(s’)と、i=1,...,Lの各整数iについての所定の値θ,θ’とに基づき、i=1,...,Lの各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,i’(i’=1,...,2n)を用いて、数16に示すベクトルを含む暗号要素cを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tが示す基底ベクトルbt,i(i’=1,...,2n)を用いて、数17に示すベクトルを含む暗号要素cを生成する暗号要素c生成工程と、
前記暗号化装置が、前記暗号要素c生成工程で生成されたi=1,...,Lの各整数iについての暗号要素cと、前記変数ρ(i)と、前記行列Mとを含む暗号化データctを前記復号装置へ送信する暗号化データ送信工程と、
前記復号装置が、前記d個の鍵生成装置のうち、前記少なくとも1つ以上の鍵生成装置の前記復号鍵送信工程で送信された復号鍵uskを受信する復号鍵受信工程と、
前記暗号化データ送信工程で送信された暗号化データctを受信するデータ受信工程と、
前記復号装置が、前記復号鍵受信工程で受信された復号鍵uskに含まれる属性情報xと、前記データ受信工程で受信された暗号化データctに含まれる変数ρ(i)とに基づき、i=1,...,Lの各整数iのうち、変数ρ(i)が肯定形の組(t,v)であり、かつ、その組の識別情報tが示すxを含む復号鍵uskを前記復号鍵受信工程で受信されており、かつ、その組のvと、その組の識別情報tが示す属性情報xとの内積が0となるiと、変数ρ(i)が否定形の組¬(t,v)であり、かつ、その組の識別情報tが示すxを含む復号鍵uskを前記復号鍵受信工程で受信されており、かつ、その組のvと、その組の識別情報tが示す属性情報xとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、前記暗号化データctに含まれる行列Mのi行目の要素であるMに基づき、αを合計した場合に所定のベクトルhとなる補完係数αを計算する補完係数計算工程と、
前記復号装置が、前記補完係数計算工程で計算された集合Iと補完係数αとに基づき、前記暗号化データctに含まれる暗号要素cと、前記復号鍵uskに含まれる鍵要素kとについて、数18に示すペアリング演算を行い、前記所定の情報Kを計算するペアリング演算工程と
を備えることを特徴とする暗号処理方法。
【数15】

【数16】

【数17】

【数18】

【請求項8】
d個(dは1以上の整数)の鍵生成装置で動作させる鍵生成プログラムと、暗号化装置で動作させる暗号化プログラムと、復号装置で動作させる復号プログラムとを備え、t=1,...,dの少なくとも1つ以上の整数tについての基底Bと基底Bとを用いて暗号処理を実行する暗号処理プログラムであり、
前記鍵生成プログラムは、
t=1,...,dのうち鍵生成装置毎に予め定められた整数tについての属性情報x:=(xt,i)(i=1,...,n,nは1以上の整数)を入力する第1情報入力処理と、
前記整数tと、前記第1情報入力処理で入力された属性情報xと、所定の値δと、基底Bの基底ベクトルbt,i(i=1,...,2n)とに基づき、数19に示すベクトルを含む鍵要素kを生成する鍵要素生成処理と、
前記鍵要素生成処理で生成された鍵要素kと、前記属性情報xとを含む復号鍵uskを前記復号装置へ送信する復号鍵送信処理と
をコンピュータに実行させ、
前記暗号化プログラムは、
i=1,...,L(Lは1以上の整数)の各整数iについての変数ρ(i)であって、識別情報t(t=1,...,dのいずれかの整数)と、属性情報v:=(vi,i’)(i’=1,...,n)との肯定形の組(t,v)又は否定形の組¬(t,v)のいずれかである変数ρ(i)と、L行r列(rは1以上の整数)の所定の行列Mとを入力する第2情報入力処理と、
r個の要素を有するベクトルfと、前記第2情報入力処理で入力された行列Mとに基づき列ベクトルs→T:=(s,...,s:=M・f→Tを生成するとともに、s:=h・f→Tとして、s=h・(f’)であるr個の要素を有するベクトルf’と、前記行列Mとに基づき列ベクトル(s’):=(s’,...,s’):=M・(f’)を生成するベクトル生成処理と、
前記ベクトル生成処理で生成された列ベクトルs→T及び列ベクトル(s’)と、i=1,...,Lの各整数iについての所定の値θ,θ’とに基づき、i=1,...,Lの各整数iについて、変数ρ(i)が肯定形の組(t,v)である場合には、その組の識別情報tが示す基底Bの基底ベクトルbt,i’(i’=1,...,2n)を用いて、数20に示すベクトルを含む暗号要素cを生成し、変数ρ(i)が否定形の組¬(t,v)である場合には、その組の識別情報tが示す基底ベクトルbt,i(i=1,...,2n)を用いて、数21に示すベクトルを含む暗号要素cを生成する暗号要素c生成処理と、
前記暗号要素c生成処理で生成されたi=1,...,Lの各整数iについての暗号要素cと、前記変数ρ(i)と、前記行列Mとを含む暗号化データctを前記復号装置へ送信する暗号化データ送信処理と
をコンピュータに実行させ、
前記復号プログラムは、
前記復号鍵送信処理で送信された復号鍵uskを受信する復号鍵受信処理と、
前記暗号化データ送信処理で送信された暗号化データctを受信するデータ受信処理と、
前記復号鍵受信処理で受信された復号鍵uskに含まれる属性情報xと、前記データ受信処理で受信された暗号化データctに含まれる変数ρ(i)とに基づき、i=1,...,Lの各整数iのうち、変数ρ(i)が肯定形の組(t,v)であり、かつ、その組の識別情報tが示すxを含む復号鍵uskを前記復号鍵受信処理で受信されており、かつ、その組のvと、その組の識別情報tが示す属性情報xとの内積が0となるiと、変数ρ(i)が否定形の組¬(t,v)であり、かつ、その組の識別情報tが示すxを含む復号鍵uskを前記復号鍵受信処理で受信されており、かつ、その組のvと、その組の識別情報tが示す属性情報xとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、前記暗号化データctに含まれる行列Mのi行目の要素であるMに基づき、αを合計した場合に所定のベクトルhとなる補完係数αを計算する補完係数計算処理と、
前記補完係数計算処理で計算された集合Iと補完係数αとに基づき、前記暗号化データctに含まれる暗号要素cと、前記復号鍵uskに含まれる鍵要素kとについて、数22に示すペアリング演算を行い、前記所定の情報Kを計算するペアリング演算処理と
をコンピュータに実行させることを特徴とする暗号処理プログラム。
【数19】

【数20】

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


【公開番号】特開2012−203182(P2012−203182A)
【公開日】平成24年10月22日(2012.10.22)
【国際特許分類】
【出願番号】特願2011−67471(P2011−67471)
【出願日】平成23年3月25日(2011.3.25)
【出願人】(000006013)三菱電機株式会社 (33,312)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】