鍵交換システム、鍵交換装置、鍵抽出装置、鍵交換方法、鍵抽出方法、及びプログラム
【課題】鍵を共有する相手を多様な条件で指定することを可能とする。
【解決手段】鍵交換装置１１０には、属性情報att(uAL)⊂δBについての論理式を表す木構造データγAが対応付けられ、鍵交換装置１２０には、属性情報att(uBL)⊂δBについての論理式を表す木構造データγBが対応付けられる。鍵交換装置１１０は、与えられた属性集合δBが木構造データγAに表される論理式を真にする場合にセッション鍵Kを生成する。鍵交換装置１２０は、与えられた属性集合δAが木構造データγBに表される論理式を真にする場合にセッション鍵Kを生成する。属性集合δBが木構造データγAに表される論理式を真にし、属性集合δAが木構造データγBに表される論理式を真にする場合、同一のセッション鍵Kが共有される。
【解決手段】鍵交換装置１１０には、属性情報att(uAL)⊂δBについての論理式を表す木構造データγAが対応付けられ、鍵交換装置１２０には、属性情報att(uBL)⊂δBについての論理式を表す木構造データγBが対応付けられる。鍵交換装置１１０は、与えられた属性集合δBが木構造データγAに表される論理式を真にする場合にセッション鍵Kを生成する。鍵交換装置１２０は、与えられた属性集合δAが木構造データγBに表される論理式を真にする場合にセッション鍵Kを生成する。属性集合δBが木構造データγAに表される論理式を真にし、属性集合δAが木構造データγBに表される論理式を真にする場合、同一のセッション鍵Kが共有される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関するものであり、特に、二者間で共通のセッション鍵を共有する鍵交換技術に関するものである。
【背景技術】
【０００２】
従来のID認証鍵交換方式の一つにSYL方式があった（例えば、非特許文献１参照）。以下にSYL方式の概要を説明する。
【０００３】
［パラメータ］
G, GTをκビットの素数位数pの巡回群、gをGの生成元、gT=e(g,g)をGTの生成元、e:G×G→GTをペアリングとする。H:{0,1}*→{0,1}κとし、H1:{0,1}*→Gをハッシュ関数とする。鍵生成者は、マスタ秘密鍵λ∈Zpをランダムに選び、マスタ公開鍵Λ=gλ∈Gを公開する。
【０００４】
［鍵生成］
鍵生成者は、ユーザA,Bの識別子IDA, IDB∈{0,1}*に対して、それぞれQA=H1(IDA)∈G, QB=H1(IDB)∈Gを計算し、マスタ秘密鍵λを用いて秘密鍵DA=QAλ∈G, DB=QBλ∈Gを生成する。
【０００５】
[鍵交換]
識別子IDAと秘密鍵DA=QAλ∈GをもつユーザAと、識別子IDBと秘密鍵DB=QBλ∈GをもつユーザBは、以下のようにして認証鍵交換を行い、セッション鍵（共有鍵）Kを共有する。
【０００６】
ユーザAは、ランダムに短期秘密鍵χA∈UZpを選び、短期公開鍵XA=gχAを計算し、(IDA,IDB,XA)をユーザBに送る。
【０００７】
ユーザBは、(IDA,IDB,XA)を受信し、ランダムに短期秘密鍵χB∈UZpを選び、短期公開鍵XB=gχBを計算し、(IDA,IDB,XA,XB)をユーザAに送る。ユーザBは、σ1=e(QA・XA, DB・ΛχB), σ2=XAχBを計算し、セッション鍵K=H(σ1,σ2,IDA,IDB,XA,XB)を計算する。
【０００８】
ユーザAは、(IDA,IDB,XA,XB)を受信し、σ1=e(DA・ΛχA,QB・XB),σ2=XBχAを計算し、セッション鍵K=H(σ1,σ2,IDA,IDB,XA,XB)を計算する。
【０００９】
σ1=gTλ(log(QA)+χA)・(log(QB)+χB), σ2=gχA・χBとなるので、両者で計算したセッション鍵Kは一致する。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】L. Chen, Z. Cheng, Nigel P. Smart, "Identity-based key agreement protocols from pairings", Int. J. Inf. Sec. 6(4): 213-241 (2007).
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかし、SYL方式は、相手が指定したIDと自分のIDが一致した場合にのみセッション鍵を生成できるという単純な方式であり、セッション鍵を共有する相手を多様な条件で指定することができなかった。
【００１２】
本発明はこのような点に鑑みてなされたものであり、セッション鍵を共有する相手を多様な条件で指定することができる鍵交換技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明では、第１鍵交換装置と第２鍵交換装置とでセッション鍵を生成する。巡回群G1, G2, GTの生成元がそれぞれg1, g2, gTであり、直積空間G1×G2の元を巡回群GTに写す双線形写像がe: G1×G2→GTであり、属性情報jの集合がATTであり、マスタ秘密鍵がλ及びt(j)(j∈ATT)であり、マスタ公開鍵がΛ=gTλ∈GT及びT(j)=g2t(j)∈G2である。UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む木構造データγAが第１鍵交換装置に対応し、ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、葉ノード情報N(uAL)に対応するuALの集合がL(γA)であり、親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、ノード情報N(uA)のそれぞれには情報q(uA, η(uA))が対応し、ルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))がマスタ秘密鍵λであり、親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uAP)に対応する子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))であり、葉ノード情報N(uAL)にはそれぞれ属性情報att(uAL)∈ATTと秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1とが対応し、秘密値D(uAL)(uAL∈L(γA))の集合が第１鍵交換装置の長期秘密鍵DA={D(uAL)}uAL∈L(γA)である。UB(UB≧2)個のノード情報N(uB)(uB∈{1,...,UB})を含む木構造データγBが第２鍵交換装置に対応し、ノード情報N(uB)の一部が親ノード情報N(uBP)(uBP∈{1,...,UB})であり、親ノード情報N(uBP)にはc(uBP)個の子ノード情報N(uBC)(uBC∈{1,...,UB})が対応し、親ノード情報N(uBP)の何れか１つがルートノード情報N(uBR)(uBR∈{1,...,UB})であり、子ノード情報N(uBC)の少なくとも一部が葉ノード情報N(uBL)(uBL∈{1,...,UB})であり、葉ノード情報N(uBL)に対応するuBLの集合がL(γB)であり、親ノード情報N(uBP)のそれぞれには1≦k(uBP)≦c(uBP)を満たすしきい値k(uBP) が対応し、ノード情報N(uB)のそれぞれには情報q(uB, η(uB))が対応し、ルートノード情報N(uBR)に対応する情報q(uBR, η(uBR))がマスタ秘密鍵λであり、親ノード情報N(uBP)に対応する情報q(uBP, η(uBP))をk(uBP)-out-of-c(uBP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uBP)に対応する子ノード情報N(uBC)に対応する情報q(uBC, η(uBC))であり、葉ノード情報N(uBL)にはそれぞれ属性情報att(uBL)∈ATTと秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1とが対応し、秘密値D(uBL)(uBL∈L(γB))の集合が第２鍵交換装置の長期秘密鍵DB={D(uBL)}uBL∈L(γB)である。
【００１４】
第１鍵交換装置は、短期秘密鍵sAを任意に生成し、属性情報の集合ATTの部分集合である属性集合δA⊂ATTと長期秘密鍵DAと短期秘密鍵sAとを用い、長期秘密鍵DAと短期秘密鍵sAとを含む値の像χに対する元T(wA)χ∈G2 (wA∈δA)の集合であるTA={T(wA)χ}wA∈δAを含む第１短期公開鍵を生成し、属性集合δAと第１短期公開鍵とを第２鍵交換装置に対して出力する。
【００１５】
第２鍵交換装置は、短期秘密鍵sBを任意に生成し、属性情報の集合ATTの部分集合である属性集合δB⊂ATTと長期秘密鍵DBと短期秘密鍵sBとを用い、長期秘密鍵DBと短期秘密鍵sBとを含む値の像υに対する元T(wB)υ∈G2 (wB∈δB)の集合であるTB={T(wB)υ}wB∈δBを含む第２短期公開鍵を生成し、属性集合δBと第２短期公開鍵とを第１鍵交換装置に対して出力する。
【００１６】
第１鍵交換装置は、属性集合δBと第２短期公開鍵との入力を受け付け、属性集合δBに属する属性情報att(uAL)∈δBに対応する葉ノード情報N(uAL)に対応する秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1と第２短期公開鍵が含む元T(att(uAL))υ∈G2とに対し、双線形写像eを作用させ、葉ノード情報N(uAL)に対して復元値e(D(uAL), T(att(uAL))υ)=gTυ・q(uAL, η(uAL))∈GTを生成し、自らに対応する子ノード情報N(uAC)のうち復元値gTυ・q(uAC, η(uAC))∈GTが生成されたものの合計数が自らに対応するしきい値k(uAP)以上となる親ノード情報N(uAP)に対し、当該しきい値k(uAP)以上の復元値gTυ・q(uAC, η(uAC))∈GTをk(uAP)-out-of-c(uAP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTυ・q(uAP, η(uAP))∈GTを生成する。ここで、ルートノード情報N(uAR)に対する復元値gTυ・q(uAR, η(uAR))=gTυ・λ∈GTが生成された場合、第１鍵交換装置は、Λχ=gTχ・λ∈GTとgTυ・λ∈GTとを含む値の像を第１セッション鍵として出力する。
【００１７】
第２鍵交換装置は、属性集合δAと第１短期公開鍵との入力を受け、属性集合δAに属する属性情報att(uBL)∈δAに対応する葉ノード情報N(uBL)に対応する秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1と第１短期公開鍵が含む元T(att(uBL))χ∈G2とに対し、双線形写像eを作用させ、葉ノード情報N(uBL)に対して復元値e(D(uBL), T(att(uBL))χ)=gTχ・q(uBL, η(uBL))∈GTを生成し、自らに対応する子ノード情報N(uBC)のうち復元値gTχ・q(uBC, η(uBC))∈GTが生成されたものの合計数が自らに対応するしきい値k(uBP)以上となる親ノード情報N(uBP)に対し、当該しきい値k(uBP)以上の復元値gTχ・q(uBC, η(uBC))∈GTをk(uBP)-out-of-c(uBP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTχ・q(uBP, η(uBP))∈GTを生成する。ここで、ルートノード情報N(uBR)に対する復元値gTχ・q(uBR, η(uBR))=gTχ・λ∈GTが生成されたた場合、第２鍵交換装置は、gTχ・λ∈GTとΛυ=gTυ・λ∈GTとを含む値の像を第２セッション鍵として出力する。
【発明の効果】
【００１８】
本発明の木構造データγA,γBはそれぞれ特定の論理式に対応し、属性集合δAが木構造データγBに対応する論理式を真にし、属性集合δBが木構造データγAに対応する論理式を真にする場合に、第１鍵交換装置と第２鍵交換装置との間で同一のセッション鍵が生成される。そのため、本発明では、セッション鍵を共有する相手を多様な条件で指定することができる。
【図面の簡単な説明】
【００１９】
【図１】図１は、実施形態での鍵交換システムの全体構成を説明するための図である。
【図２】図２は、実施形態での鍵交換装置の構成を説明するための図である。
【図３】図３は、実施形態での鍵交換装置の構成を説明するための図である。
【図４】図４は、実施形態での鍵抽出装置の構成を説明するための図である。
【図５】図５Ａ及び図５Ｂは、実施形態での鍵抽出方法を説明するための図である。
【図６】図６は、実施形態での鍵交換方法を説明するための図である。
【図７】図７は、実施形態での鍵交換方法を説明するための図である。
【図８】図８Ａ及び図８Ｂは、木構造データを例示するための図である。
【図９】図９Ａ及び図９Ｂは、木構造データを例示するための図である。
【図１０】図１０Ａ及び図１０Ｂは、木構造データを例示するための図である。
【図１１】図１１Ａ及び図１１Ｂは、木構造データを例示するための図である。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施形態を説明する。
【００２１】
＜定義＞
本形態で使用する用語を定義する。
∧：∧は論理積を表す。
∨：∨は論理和を表す。
・−：・−は・の否定を表す。
Z：Zは整数集合を表す。
κ：κはセキュリティパラメータ（κ∈Z, κ>0）を表す。
Zp：Zpは位数p（p≧１）の環を表す。Zpの例はpを法とする剰余環である。また、pの例はκビットの素数である。ただし、これらの例は本発明を限定するものではない。
ξ∈UZp：ξ∈UZpは、Zpの任意の元ξを選択することを表す。
【００２２】
{0,1}*：{0,1}*は任意ビット長のバイナリ系列を表す。その一例は、整数0及び1からなる系列である。ただし、{0,1}*は整数0及び1からなる系列に限定されない。{0,1}*は位数2の有限体又はその拡大体と同義である。
【００２３】
{0,1}ζ：{0,1}ζはビット長ζ（ζ∈Z, ζ>0）のバイナリ系列を表す。その一例は、整数0及び1からなる系列である。しかし、{0,1}ζは整数0及び1からなる系列に限定されない。{0,1}ζは位数2の有限体（ζ=1の場合）又はそれをζ次拡大した拡大体（ζ>1の場合）と同義である。
【００２４】
G1, G2, GT：G1, G2, GTのそれぞれは予め定められた巡回群を表し、g1, g2, gTのそれぞれは巡回群G1, G2, GTの生成元を表す。本形態の例では、G1, G2, GTがκビットの素数位数pの巡回群であるものとして説明する。なお、G1=G2であってもよいしG1≠G2であってもよい。巡回群G1, G2の具体例は、楕円曲線の等分点からなる有限集合やその部分群である。巡回群GTの具体例は、拡大体を構成する有限集合からなる群である。なお、本形態では、巡回群G1, G2, GT上で定義された演算が乗法的に表現される。すなわち、β∈Zp及びψ∈G1に対するψβ∈G1は、ψ∈G1に対して巡回群G1で定義された演算をβ回施すことを意味し、ψ1, ψ2∈G1に対するψ1・ψ2∈G1は、ψ1∈G1とψ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。巡回群G2, GTについても同様である。
【００２５】
e：eは、直積空間G1×G2の元を巡回群GTに写す双線形写像G1×G2→GTを表し、e(g1, g2)=gTを満たす。双線形写像eは以下の性質を満たす。
【００２６】
［双線形性］すべてのψ1∈G1，ψ2∈G2及びε，ζ∈Zpについて以下の関係を満たす。
e(ψ1ε,ψ2ζ)=e(ψ1, ψ2)ε・ζ …(1)
［非退化性］すべての
ψ1∈G1，ψ2∈G2 …(2)
を巡回群GTの単位元に写す写像ではない。
［計算可能性］あらゆるψ1∈G1，ψ2∈G2についてe(ψ1, ψ2)を効率的に計算するアルゴリズムが存在する。
【００２７】
双線形写像eの具体例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数である（例えば、参考文献１「Alfred. J. Menezes，ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS， ISBN0-7923-9368-6，pp. 61-81」等参照）。また、楕円曲線の種類に応じ、Tateペアリングなどのペアリング演算を行うための関数と所定の関数phiを組み合わせた変更ペアリング関数e(ψ1,phi(ψ2))（ψ1∈G1，ψ2∈G2）を双線形写像eとして用いてもよい（例えば、参考文献２「RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems」等参照）。また、ペアリング演算をコンピュータ上で行うためのアルゴリズムとしては、周知のMiller のアルゴリズムなどが存在し、ペアリング演算を効率的に行うための楕円曲線や巡回群G1, G2, GTの構成方法はよく知られている。
【００２８】
属性情報：属性情報とは何らかの属性を表す値を意味する。属性情報j:{0,1}Φの集合をATTと表す。本形態の例では、属性情報jが1以上J以下の整数であり(Jは正整数)、ATT={1,...,J}であるものとする。ただし、これは本発明を限定するものではない。
【００２９】
Ω：Ωはプロトコル使用に対応した固有の識別子であるプロトコルＩＤを表す。
【００３０】
k-out-of-c しきい値秘密分散法：k-out-of-c しきい値秘密分散法は、任意の相違なるk個の分散情報SH(φ1),...,SH(φk)(1≦k≦c)が与えられれば秘密情報SKを復元できるが、任意のk-1個の分散情報SH(φ1),...,SH(φk-1)が与えられても秘密情報SKの情報はまったく得られない方式である（例えば、参考文献３「Adi Shamir, "How to share a secret", Communications of the ACM, Volume 22, No. 11, pp.612-613 (November 1979)」等参照）。以下にその一例を示す。
【００３１】
(1) q(η)=SK（ηは定数）を満たす不定元αについてのk-1次の多項式q(α)=ξ0+ξ1・α+ξ2・α2+...+ξK-1・αk-1をランダムに選ぶ。すなわち、q(η)=SKとし、ξ1,..., ξK-1をランダムに選ぶ。なお、定数ηの例はη=0である。そして、分散情報をSH(ρ)=q(index(ρ))（ρ∈{1,...,c}）とする。なお、index(ρ)は各ρに対応する互いに異なるインデックスであり、その例はindex(ρ)=ρである。
【００３２】
(2) 任意の相違なるk個の分散情報q(φ1),...,q(φk)（S={φ1,...,φk}⊂{index(1),...,index(c)}）が得られた場合、例えば、ラグランジェ(Lagrange)の補間公式を用い、以下のような復元処理によって秘密情報SKを復元できる。
【００３３】
SK=q(η)=Δ(φ1, q(η))・q(φ1)+...+Δ(φk, q(η))・q(φk) …(3)
ただし、Δ(ι, q(η))(ι∈S)は、以下に表すラグランジュ係数である。
【００３４】
【数１】
は先頭からι番目の被演算子〔分母の要素(φι-φι)、分子の要素(η-φι)〕が存在しないことを意味する。すなわち、式(4)の分母は、
(φι-φ1)・...・(φι-φι-1)・(φι-φι+1)・...・(φι-φk)
であり、式(4)の分子は
(η-φ1)・...・(η-φι-1)・(η-φι+1)・...・(η-φk)
である。
【００３５】
H:Hは{0,1}*を{0,1}kに移すハッシュ関数H:{0,1}* →{0,1}κを表す。
H':H'は{0,1}*をZpに移すハッシュ関数H:{0,1}* →Zpを表す。
【００３６】
＜原理＞
次に、本形態の原理を説明する。本形態では、第１鍵交換装置と第２鍵交換装置との間でセッション鍵を生成する。第１,２鍵交換装置には、それぞれ、属性情報についての論理式を表す木構造データγA,γBが対応付けられている。第１鍵交換装置は、属性情報の集合ATTの部分集合である属性集合δA⊂ATTを設定して第２鍵交換装置に対して出力し、第２鍵交換装置は、属性情報jの集合ATTの部分集合である属性集合δB⊂ATTを設定して第１鍵交換装置に対して出力する。ここで、属性集合δAが木構造データγBに対応する論理式を真にし、属性集合δBが木構造データγAに対応する論理式を真にする場合に、第１鍵交換装置と第２鍵交換装置との間で同一のセッション鍵が生成される。まず、木構造データの基本構成を説明する。
【００３７】
［木構造データγA］
第１鍵交換装置に対応する木構造データγAは、根付き木構造のデータであり、UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む。ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、親ノード情報N(uAP)にはc(uAP)(c(uAP)≧1)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応する。親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、葉ノード情報N(uAL)に対応するuALの集合がL(γA)である。親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応する。ノード情報N(uA)のそれぞれには情報q(uA, η(uA))が対応する。ルートノード情報N(uAR)に対応する情報q(uAR, 0)はマスタ秘密鍵λである。また、親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uAP)に対応する子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))である。葉ノード情報N(uAL)にはそれぞれ１つの属性情報att(uAL)∈ATTと秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1とが対応し、秘密値D(uAL)(uAL∈L(γA))の集合が第１鍵交換装置の長期秘密鍵DA={D(uAL)}uAL∈L(γA)である。なお、t(j)(j∈ATT)はマスタ秘密鍵である。なお、添字のuAはuAを表す。
【００３８】
なお、例えば、しきい値秘密分散法として参考文献３に記載された方法が用いられる場合には、子ノード情報N(uAC)のそれぞれには識別子index(uAC)が対応し、葉ノード情報N(uAL)にはしきい値k(uAL)=1が対応し、ノード情報N(uA)のそれぞれには不定元αについての次数d(uA)=k(uA)-1の多項式q(uA, α)が対応する。ここで、η(uA)はノード情報N(uA)に対応する定数である。また、情報q(uA, η(uA))が多項式q(uA, α)に定数η(uA)を代入して得られる値であり、子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))が当該子ノード情報N(uAC)に対応する親ノード情報N(uAP)に対応する多項式q(uAP, α)に当該子ノード情報N(uAC)に対応する識別子index(uAC)を代入して得られるq(uAP, index(uAC))である。
【００３９】
［木構造データγB］
第２鍵交換装置に対応する木構造データγBも木構造データγAと同様に構成される。すなわち、木構造データγBは、根付き木構造のデータであり、UB(UB≧2)個のノード情報N(uB)(uB∈{1,...,UB})を含む。ノード情報N(uB)の一部が親ノード情報N(uBP)(uBP∈{1,...,UB})であり、親ノード情報N(uBP)にはc(uBP)(c(uBP)≧1)個の子ノード情報N(uBC)(uBC∈{1,...,UB})が対応する。親ノード情報N(uBP)の何れか１つがルートノード情報N(uBR)(uBR∈{1,...,UB})であり、子ノード情報N(uBC)の少なくとも一部が葉ノード情報N(uBL)(uBL∈{1,...,UB})であり、葉ノード情報N(uBL)に対応するuBLの集合がL(γB)である。親ノード情報N(uBP)のそれぞれには1≦k(uBP)≦c(uBP)を満たすしきい値k(uBP) が対応する。ノード情報N(uB)のそれぞれには情報q(uB, η(uB))が対応する。ルートノード情報N(uBR)に対応する情報q(uBR, η(uBR))はマスタ秘密鍵λである。また、親ノード情報N(uBP)に対応する情報q(uBP, η(uBP))をk(uBP)-out-of-c(uBP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uBP)に対応する子ノード情報N(uBC)に対応する情報q(uBC, η(uBC))である。葉ノード情報N(uBL)にはそれぞれ１つの属性情報att(uBL)∈ATTと秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1とが対応し、秘密値D(uBL)(uBL∈L(γB))の集合が第２鍵交換装置の長期秘密鍵DB={D(uBL)}uBL∈L(γB)である。なお、添字のuBはuBを表す。
【００４０】
なお、例えば、しきい値秘密分散法として参考文献３に記載された方法が用いられる場合には、子ノード情報N(uBC)のそれぞれには識別子index(uBC)が対応し、葉ノード情報N(uBL)にはしきい値k(uBL)=1が対応し、ノード情報N(uB)のそれぞれには不定元αについての次数d(uB)=k(uB)-1の多項式q(uB, α)が対応する。ここで、η(uB)はノード情報N(uB)に対応する定数である。また、情報q(uB, η(uB))が多項式q(uB, α)に定数η(uB)を代入して得られる値であり、子ノード情報N(uBC)に対応する情報q(uBC, η(uBC))が当該子ノード情報N(uBC)に対応する親ノード情報N(uBP)に対応する多項式q(uBP, α)に当該子ノード情報N(uBC)に対応する識別子index(uBC)を代入して得られるq(uBP, index(uBC))である。
【００４１】
［鍵交換］
木構造データγAに対応する第１鍵交換装置と木構造データγBに対応する第２鍵交換装置とは、以下の処理によってセッション鍵の生成を行う。
【００４２】
第１鍵交換装置は、短期秘密鍵sAを任意に生成し、属性情報の集合ATTの部分集合である属性集合δA⊂ATTと長期秘密鍵DAと短期秘密鍵sAとを用い、長期秘密鍵DAと短期秘密鍵sAとを含む値の像χに対する元T(wA)χ∈G2 (wA∈δA)の集合であるTA={T(wA)χ}wA∈δAを含む第１短期公開鍵を生成し、属性集合δAと第１短期公開鍵とを第２鍵交換装置に対して出力する。なお、T(j)=g2t(j)∈G2はマスタ公開鍵である。また、添字のwA,δAは、それぞれwA,δAを表す。
【００４３】
第２鍵交換装置は、短期秘密鍵sBを任意に生成し、属性情報の集合ATTの部分集合である属性集合δB⊂ATTと長期秘密鍵DBと短期秘密鍵sBとを用い、長期秘密鍵DBと短期秘密鍵sBとを含む値の像υに対する元T(wB)υ∈G2 (wB∈δB)の集合であるTB={T(wB)υ}wB∈δBを含む第２短期公開鍵を生成し、属性集合δBと第２短期公開鍵とを第１鍵交換装置に対して出力する。なお、添字のwB,δBは、それぞれwB,δBを表す。
【００４４】
第１鍵交換装置は、属性集合δBと第２短期公開鍵との入力を受け付け、属性集合δBに属する属性情報att(uAL)∈δBに対応する葉ノード情報N(uAL)に対応する秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1と第２短期公開鍵が含む元T(att(uAL))υ∈G2とに対し、双線形写像eを作用させ、葉ノード情報N(uAL)に対して復元値e(D(uAL), T(att(uAL))υ)=gTυ・q(uAL, η(uAL))∈GTを生成する。また、第１鍵交換装置は、自らに対応する子ノード情報N(uAC)のうち復元値gTυ・q(uAC, η(uAC))∈GTが生成されたものの合計数が自らに対応するしきい値k(uAP)以上となる親ノード情報N(uAP)に対し、当該しきい値k(uAP)以上の復元値gTυ・q(uAC, η(uAC))∈GTをk(uAP)-out-of-c(uAP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTυ・q(uAP, η(uAP))∈GTを生成する。ここで、ルートノード情報N(uAR)に対する復元値gTυ・q(uAR, η(uAR))=gTυ・λ∈GTが生成された場合、第２鍵交換装置は、Λχ=gTχ・λ∈GTとgTυ・λ∈GTとを含む値の像を第１セッション鍵として出力する。なお、Λ=gTλ∈GTはマスタ公開鍵を表す。
【００４５】
第２鍵交換装置は、属性集合δAと第１短期公開鍵との入力を受け付け、属性集合δAに属する属性情報att(uBL)∈δAに対応する葉ノード情報N(uBL)に対応する秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1と第１短期公開鍵が含む元T(att(uBL))χ∈G2とに対し、双線形写像eを作用させ、葉ノード情報N(uBL)に対して復元値e(D(uBL), T(att(uBL))χ)=gTχ・q(uBL, η(uBL))∈GTを生成する。また、第２鍵交換装置は、自らに対応する子ノード情報N(uBC)のうち復元値gTχ・q(uBC, η(uBC))∈GTが生成されたものの合計数が自らに対応するしきい値k(uBP)以上となる親ノード情報N(uBP)に対し、当該しきい値k(uBP)以上の復元値gTχ・q(uBC, η(uBC))∈GTをk(uBP)-out-of-c(uBP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTχ・q(uBP, η(uBP))∈GTを生成する。ここで、ルートノード情報N(uBR)に対する復元値gTχ・q(uBR, η(uBR))=gTχ・λ∈GTが生成された場合、第２鍵交換装置は、gTχ・λ∈GTとΛυ=gTυ・λ∈GTとを含む値の像を第２セッション鍵として出力する。
【００４６】
［特徴］
本形態の木構造データγAは各葉ノード情報N(uAL)に対応する属性情報att(uAL)⊂δBについての論理式を表し、第１鍵交換装置は、与えられた属性集合δBが木構造データγAに表される論理式を真にする場合に第１セッション鍵を生成する。言い換えると、与えられた属性集合δBに葉ノード情報N(uAL)に対応する属性情報att(uAL)が含まれた場合（「uALが満たされる」と呼ぶ）、当該属性情報att(uAL)⊂δBに対応する葉ノード情報N(uAL)に対応する情報q(uAL, η(uAL))に対応する復元値gTυ・q(uAL, η(uAL))が復元される。また、子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))に対応する情報が、それらの親ノード情報N(uAP)に対応するしきい値k(uAP)以上得られた場合（「uAPが満たされる」と呼ぶ）、親ノード情報N(uAP)に対応する復元値gTυ・q(uAP, η(uAP))が得られる。そして、ルートノード情報N(uAR)の子ノード情報N(uAC)に対応する復元値gTυ・q(uAC, η(uAC))が、ルートノード情報N(uAR)に対応するしきい値k(uAR)以上得られ（「木構造データγAが満たされる」と呼ぶ）、ルートノード情報N(uAR)に対応する復元値gTυ・q(uAR, η(uAR))=gTυ・λが得られた場合、得られたgTυ・λ=σ2とマスタ公開鍵Λから生成されるΛχ=gTχ・λ=σ1とに対応する第１セッション鍵が生成される。
【００４７】
同様に、本形態の木構造データγBは各葉ノード情報N(uBL)に対応する属性情報att(uBL)⊂δBについての論理式を表し、第２鍵交換装置は、与えられた属性集合δAが木構造データγBに表される論理式を真にする場合に第２セッション鍵を生成する。言い換えると、与えられた属性集合δAに葉ノード情報N(uBL)に対応する属性情報att(uBL)が含まれた場合（「uBLが満たされる」と呼ぶ）、当該属性情報att(uBL)⊂δAに対応する葉ノード情報N(uBL)に対応する復元値gTχ・q(uBL, η(uBL))が復元される。また、子ノード情報N(uBC)に対応する情報q(uBC, η(uBC))に対応する復元値gTχ・q(uBC, η(uBC))が、それらの親ノード情報N(uBP)に対応するしきい値k(uBP)以上得られた場合（「uBPが満たされる」と呼ぶ）、親ノード情報N(uBP)に対応する復元値gTχ・q(uBP, η(uBP))が得られる。そして、ルートノード情報N(uBR)の子ノード情報N(uBC)に対応する復元値gTχ・q(uBC, η(uBC))が、ルートノード情報N(uBR)に対応するしきい値k(uBR)以上得られ（「γBが満たされる」と呼ぶ）、ルートノード情報N(uBR)に対応する復元値gTχ・q(uBR, η(uBR))=gTχ・λが得られた場合、得られたgTχ・λ=σ1∈GTとマスタ公開鍵Λから生成されるΛυ=gTυ・λ=σ2∈GTとに対応する第２セッション鍵が生成される。
【００４８】
ここで、第１鍵交換装置が生成するΛχ=gTχ・λ=σ1は第２鍵交換装置が生成するgTχ・λ=σ1と等しく、第１鍵交換装置が生成するgTυ・λ=σ2は第２鍵交換装置が生成するΛυ=gTυ・λ=σ2と等しい。よって、第１、２鍵交換装置は同一のセッション鍵を共有できる。すなわち、本形態では、属性集合δBに対してγAが満たされ、属性集合δAに対してγBが満たされた場合に、第１、２鍵交換装置で同一のセッション鍵を共有できる。このことを「属性集合が木構造データを満たす」という命題を表す述語
P:{0,1}Φ×{0,1}Φ→{0,1} …(5)
を用いて表現すると、「P(δB, γA)=1かつP(δA, γB)=1の場合に第１、２鍵交換装置が同一のセッション鍵を共有できる」となる。なお、P(δ, γ)=1とは「属性集合δが木構造データγを満たす」という命題を表す述語が真であることを表し、P(δ, γ)=0とは「属性集合δが木構造データγを満たす」という命題を表す述語が偽であることを表す。
【００４９】
また、第１鍵交換装置がさらに元X=g1χ∈G1を生成し、第１短期公開鍵がさらに元X=g1χ∈G1を含み、第２鍵交換装置がさらに元Y=g1υ∈G1を生成し、第２短期公開鍵がさらに元Y=g1υ∈G1を含み、P(δB, γA)=1の場合に第１鍵交換装置がσ1=Λχ=gTχ・λ∈GTとσ2=gTυ・λ∈GTとσ3=Yχ∈G1とを含む値の像を第１セッション鍵として出力し、P(δA, γB)=1の場合に第２鍵生成装置がσ1=gTχ・λ∈GTとσ2=Λυ=gTυ・λ∈GTとσ3=Xυ∈G1とを含む値の像を第２セッション鍵として出力してもよい。この場合（「限定形態」と呼ぶ）、短期秘密鍵が第三者に漏洩したことを考慮したeCKと呼ばれるモデルでの安全性が確保される。
【００５０】
例えば、従来のSYL方式では、短期秘密鍵が攻撃者に漏洩した場合、攻撃者は次のような攻撃を行うことで正規のユーザBに成り済ますことができる。
【００５１】
(1) 攻撃者は、ユーザAの短期秘密鍵χAを得る。
(2) 攻撃者は、ユーザAから(IDA,IDB,XA)を受信したら、IDBからQB=H1(IDB)を計算し、χB=QB(-1)とし、(IDA,IDB,XA,XB)をユーザAに送る。このとき、ユーザAが計算するσ1はσ1=e(DA・ΛχA,QB・QB(-1))=e(DA・ΛχA,QB)0=1∈GTとなるので、攻撃者は他の値を知らなくてもσ1の値を知ることができる。また、攻撃者は短期秘密鍵χAを用いてσ2=XBχAも計算することができる。よって、攻撃者はセッション鍵Kを計算し、ユーザBに成り済ますことができる。
【００５２】
一方、上記の限定形態の場合、短期秘密鍵が攻撃者に漏洩しても、攻撃者はセッション鍵の情報を入手することはできない。なぜなら、υやχは短期秘密鍵と長期秘密鍵とを用いて計算されるため、短期秘密鍵のみが攻撃者に漏洩しても、攻撃者はυやχを知ることができず、σ3=Xυやσ3=Yχを計算することができないからである。
【００５３】
〔実施形態〕
次に、本発明の実施形態を説明する。なお、以下では、しきい値秘密分散法として参考文献３に記載された方法が用いられ、ノード情報N(uA)に対応する定数η(uA)が0であり、ノード情報N(uB)に対応する定数η(uB)が0である場合を例にとって説明する。ただし、これは本発明を限定するものではない。
【００５４】
＜構成＞
図１に例示するように、実施形態の鍵交換システム１は、鍵交換装置１１０、１２０と鍵生成装置１３０と鍵抽出装置１４０とを有し、ネットワークや可搬型記録媒体（以下「ネットワーク等」）を経由して装置間の情報伝達を行う。鍵交換装置１１０、１２０、鍵生成装置１３０、及び鍵抽出装置１４０は、それぞれ、CPU(central processing unit)やRAM(random-access memory)などを備えた公知又は専用のコンピュータと特別なプログラムとによって構成され、特別なプログラムが読み込まれたCPUが当該特別なプログラムに従った処理を実行することで各機能が実現される。なお、特別なプログラムは、単一のプログラム列によって構成されてもよいし、他のプログラムやライブラリを読み出して目的の機能を達成するプログラムであってもよい。また、処理部の少なくとも一部が集積回路によって構成されていてもよい。
【００５５】
［鍵交換装置１１０］
図２に例示するように、実施形態の鍵交換装置１１０は、入力部１１１ａと、出力部１１１ｂと、記憶部１１２と、制御部１１３と、判定部１１４と、短期秘密鍵生成部１１５ａと、ハッシュ演算部１１５ｂと、短期公開鍵生成部１１５ｃ,１１５ｄと、葉ノード復元値生成部１１６と、親ノード復元値生成部１１７と、演算部１１８と、鍵生成部１１９とを有する。入力部１１１ａや出力部１１１ｂは、例えば、通信装置、入出力インタフェース、入出力ポートなどである。記憶部１１２は、例えば、RAM、レジスタ、キャッシュメモリ、ハードディスクなどから構成される記憶領域である。制御部１１３、判定部１１４、短期秘密鍵生成部１１５ａ、ハッシュ演算部１１５ｂ、短期公開鍵生成部１１５ｃ,１１５ｄ、葉ノード復元値生成部１１６、親ノード復元値生成部１１７、演算部１１８、及び鍵生成部１１９は、特別なプログラムが読み込まれたCPUや集積回路である。なお、鍵交換装置１１０は、記憶部１１２の制御のもとで各処理を実行する。
【００５６】
［鍵交換装置１２０］
図３に例示するように、実施形態の鍵交換装置１２０は、入力部１２１ａと、出力部１２１ｂと、記憶部１２２と、制御部１２３と、判定部１２４と、短期秘密鍵生成部１２５ａと、ハッシュ演算部１２５ｂと、短期公開鍵生成部１２５ｃ,１２５ｄと、葉ノード復元値生成部１２６と、親ノード復元値生成部１２７と、演算部１２８と、鍵生成部１２９とを有する。入力部１２１ａや出力部１２１ｂは、例えば、通信装置、入出力インタフェース、入出力ポートなどである。記憶部１２２は、例えば、RAM、レジスタ、キャッシュメモリ、ハードディスクなどから構成される記憶領域である。制御部１２３、判定部１２４、短期秘密鍵生成部１２５ａ、ハッシュ演算部１２５ｂ、短期公開鍵生成部１２５ｃ,１２５ｄ、葉ノード復元値生成部１２６、親ノード復元値生成部１２７、演算部１２８、及び鍵生成部１２９は、特別なプログラムが読み込まれたCPUや集積回路である。なお、鍵交換装置１２０は、記憶部１２２の制御のもとで各処理を実行する。
【００５７】
［鍵抽出装置１４０］
図４に例示するように、鍵抽出装置１４０は、入力部１４１と、出力部１４２と、記憶部１４３と、制御部１４４と、設定部１４５、１４６と、秘密値生成部１４７とを有する。設定部１４５は、情報設定部１４５ａと多項式設定部１４５ｂとを含む。また、設定部１４６は、情報設定部１４６ａと多項式設定部１４６ｂとを含む。入力部１４１や出力部１４２は、例えば、通信装置、入出力インタフェース、入出力ポートなどである。記憶部１４３は、例えば、RAM、レジスタ、キャッシュメモリ、ハードディスクなどから構成される記憶領域である。制御部１４４、設定部１４５、１４６、及び秘密値生成部１４７は、特別なプログラムが読み込まれたCPUや集積回路である。なお、鍵抽出装置１４０は、記憶部１４３の制御のもとで各処理を実行する。
【００５８】
＜公開パラメータ設定処理＞
事前処理として、プロトコルＩＤであるΩ、セキュリティパラメータκ、巡回群G1, G2, GT、生成元g1, g2, gT、ハッシュ関数H, H'、Zp、「属性集合が木構造データを満たす」という命題を表す述語P、属性情報の集合ATT={1,...,J}などの公開パラメータが鍵交換装置１１０、１２０、鍵生成装置１３０、鍵抽出装置１４０に共有され、各装置で利用可能な状態とされる。
【００５９】
＜鍵生成処理＞
鍵生成装置１３０（図１）は、ランダムにマスタ秘密鍵λ∈UZpを選択し、さらに、ランダムにt(j)∈UZpをすべての属性情報j∈ATTについて選択し、すべての属性情報j∈ATTについてのt(j)の集合をマスタ秘密鍵{t(j)}j∈ATTとする。また、鍵生成装置１３０は、マスタ公開鍵Λ=gTλ∈GTを生成し、さらに、すべての属性情報j∈ATTについてT(j)=g2t(j)∈G2を生成し、すべての属性情報j∈ATTについてのT(j)の集合をマスタ公開鍵{T(j)}j∈ATTとする。マスタ秘密鍵λ, {t(j)}j∈ATTは、鍵抽出装置１４０（図４）に安全に送られ、入力部１４１に入力され、記憶部１４３に格納される。一方、マスタ公開鍵Λ, {T(j)}j∈ATTは、鍵交換装置１１０,１２０（図２,３）に送られ、それぞれ、入力部１１１ａ,１２１ａに入力されて記憶部１１２,１２２に格納される。
【００６０】
＜鍵抽出処理＞
事前処理として、選択された属性情報att(uAL)∈ATTについての論理式を表す木構造データγAが鍵交換装置１１０の記憶部１１２に格納され、選択された属性情報att(uBL)∈ATTについての論理式を表す木構造データγBが鍵交換装置１２０の記憶部１２２に格納される。これらの論理式は事前に定められる。また、木構造データγA,γBにはそれぞれに対応する論理式を特定する情報が付される。
【００６１】
本形態の木構造データγAは、UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含み、ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、子ノード情報N(uAC)のそれぞれには識別子index(uAC)が対応する。親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、葉ノード情報N(uAL)に対応するuALの集合がL(γA)である。親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、葉ノード情報N(uAL)にはしきい値k(uAL)=1が対応する。また、葉ノード情報N(uAL)にはそれぞれ１つの属性情報att(uAL)∈ATTが対応する。本形態の木構造データγAは、このようにノード情報N(uA)としきい値k(uA)と識別子index(uAC)と属性情報att(uAL)とが対応付けられたデータである。
【００６２】
本形態の木構造データγBは、UB(UB≧2)個のノード情報N(uB)(uB∈{1,...,UB})を含み、ノード情報N(uB)の一部が親ノード情報N(uBP)(uBP∈{1,...,UB})であり、親ノード情報N(uBP)にはc(uBP)個の子ノード情報N(uBC)(uBC∈{1,...,UB})が対応し、子ノード情報N(uBC)のそれぞれには識別子index(uBC)が対応する。親ノード情報N(uBP)の何れか１つがルートノード情報N(uBR)(uBR∈{1,...,UB})であり、子ノード情報N(uBC)の少なくとも一部が葉ノード情報N(uBL)(uBL∈{1,...,UB})であり、葉ノード情報N(uBL)に対応するuBLの集合がL(γB)である。親ノード情報N(uBP)のそれぞれには1≦k(uBP)≦c(uBP)を満たすしきい値k(uBP)が対応し、葉ノード情報N(uBL)にはしきい値k(uBL)=1が対応する。また、葉ノード情報N(uBL)にはそれぞれ１つの属性情報att(uBL)∈ATTが対応する。本形態の木構造データγBは、このようにノード情報N(uB)としきい値k(uB)と識別子index(uBC)と属性情報att(uBL)とが対応付けられたデータである。
【００６３】
［木構造データの具体例］
以下に、木構造データγAを例にとって木構造データの具体例を示す。ここでは木構造データγAの具体例を示すが、木構造データγBも同様に構成できる。
【００６４】
《論理式(1∧2)∨4の例》
図８Ａ及び図８Ｂに例示する木構造データγAは、属性情報1, 2, 4についての論理式(1∧2)∨4に対応する。この例の木構造データγAは、5個のノード情報N(uA)(uA∈{1,...,5})を含む。ノード情報N(uA)の一部が親ノード情報N(1),N(2)であり、親ノード情報N(1)にはc(1)=2個の子ノード情報N(2), N(5)が対応し、親ノード情報N(2)にはc(2)=2個の子ノード情報N(3), N(4)が対応する。子ノード情報N(2), N(5)のそれぞれには識別子index(2)=1, index(5)=2が対応し、子ノード情報N(3), N(4)のそれぞれには識別子index(3)=1, index(4)=2が対応する。親ノード情報N(1), N(2)の１つがルートノード情報N(1)であり、子ノード情報N(2), N(3), N(4), N(5)の一部が葉ノード情報N(3), N(4), N(5)である。葉ノード情報N(3), N(4), N(5)に対応するuAL=3, 4, 5の集合がL(γA)={3, 4, 5}である。親ノード情報N(1)には1≦k(1)≦2を満たすしきい値k(1)=1が対応し、親ノード情報N(2)には1≦k(2)≦2を満たすしきい値k(2)=2が対応し、葉ノード情報N(3), N(4), N(5)にはしきい値k(3)=k(4)=k(5)=1が対応する。葉ノード情報N(3), N(4), N(5)にはそれぞれ属性情報att(3)=1, att(4)=2, att(5)=4∈ATTが対応する。
【００６５】
《論理式(1∧2)∨(2∧3)∨(1∧3)∨4−の例》
図１０Ａ及び図１０Ｂに例示する木構造データγAは、属性情報1, 2, 3, 4についての論理式(1∧2)∨(2∧3)∨(1∧3)∨4−を表している。ここで、属性情報4−は属性情報4の否定を表し、属性情報4−は属性情報5として表現される。このように特定の属性情報の否定を表す属性情報をATTに追加することにより、否定を含む論理式を表現する木構造データも設定可能となる。
【００６６】
図１０及び図１０Ｂの木構造データγAは、6個のノード情報N(uA)(uA∈{1,...,6})を含む。ノード情報N(uA)の一部が親ノード情報N(1),N(2)であり、親ノード情報N(1)にはc(1)=2個の子ノード情報N(2),N(6)が対応し、親ノード情報N(2)にはc(2)=3個の子ノード情報N(3), N(4), N(5)が対応する。子ノード情報N(2), N(6)のそれぞれには識別子index(2)=1, index(6)=2が対応し、子ノード情報N(3), N(4), N(5)のそれぞれには識別子index(3)=1, index(4)=2, index(5)=3が対応する。親ノード情報N(1),N(2)の１つがルートノード情報N(1)であり、子ノード情報N(2), N(3), N(4), N(5), N(6)の一部が葉ノード情報N(3), N(4), N(5), N(6)である。葉ノード情報N(3), N(4), N(5), N(6)に対応するuAL=3, 4, 5, 6の集合がL(γA)={3, 4, 5, 6}である。親ノード情報N(1)には1≦k(1)≦2を満たすしきい値k(1)=1が対応し、親ノード情報N(2)には1≦k(2)≦2を満たすしきい値k(2)=2が対応し、葉ノード情報N(3), N(4), N(5), N(6)にはしきい値k(3)=k(4)=k(5)=k(6)=1が対応する（［木構造データの具体例］の説明終わり）。
【００６７】
次に、木構造データγAに対応する鍵抽出処理を説明する。なお、以下では構造データγAに対応する鍵抽出処理のみを説明するが、木構造データγBに対応する鍵抽出処理も同様である。本形態の鍵抽出処理では、まず、マスタ秘密鍵λをルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))として設定する。その後、親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報を当該親ノード情報N(uAP)に対応する子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))として設定する処理を再帰的に繰り返す。その後、葉ノード情報N(uAL)に対応する属性情報att(uAL)∈ATTに対し、秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1を生成し、秘密値D(uAL)(uAL∈L(γA))の集合である長期秘密鍵DA={D(uAL)}uAL∈L(γA)を出力する。これらの具体的な処理手順に限定はない。以下に図５Ａ及び図５Ｂを用い、木構造データγAに対応する鍵抽出処理の一例を示す。
【００６８】
まず、鍵交換装置１１０（図２）の記憶部１１２から読み出された木構造データγAが出力部１１１ｂから出力される。木構造データγAは、ネットワーク等を経由して鍵抽出装置１４０（図４）の入力部１４１に入力され、記憶部１４３に格納される（ステップＳ１４１１）。
【００６９】
次に、設定部１４５がマスタ秘密鍵λを木構造データγAのルートノード情報N(uAR)に対応する情報q(uAR, 0)として設定する。本形態では、まず、設定部１４５の情報設定部１４５ａが、記憶部１４３から読み出したマスタ秘密鍵λをルートノード情報N(uAR)に対する情報q(uAR, 0)として設定し、当該情報q(uAR, 0)を記憶部１４３に格納する（ステップＳ１４１２）。次に、設定部１４５の多項式設定部１４５ｂが、記憶部１４３から情報q(uAR, 0)=λとルートノード情報N(uAR)に対応するしきい値k(uAR)とを読み込み、定数項（α=0であるときの関数値）がq(uAR, 0)=λである不定元αについての次数d(uAR)=k(uAR)-1の多項式q(uAR, α)をルートノード情報N(uAR)に対して設定する。例えば、多項式設定部１４５ｂは、d(uAR)個の互いに異なる任意点(α1, β１)（α1, β１∈UZp，α1≠0）をそれぞれランダムに選択し、それらを通る定数項q(uAR, 0)=λの多項式q(uAR, α)を特定する。これによってルートノード情報N(uAR)に対応する多項式q(uAR, α)が一意に定まる。定められた多項式q(uAR, α)は記憶部１４３に格納される（ステップＳ１４１３）。
【００７０】
次に、設定部１４６が、親ノード情報N(uAP)に対応する情報q(uAP, 0)をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報を、当該親ノード情報N(uAP)に対応する子ノード情報N(uAC)に対応する情報q(uAC, 0)として設定する。本形態の場合、設定部１４６がuAPをuAR（uAP←uAR）とおき、その場合の親ノード情報N(uAP)を処理対象として図５Ｂのループ処理を実行する（ステップＳ１４１４）。
【００７１】
［図５Ｂのループ処理］
図５Ｂのループ処理では、処理対象の親ノード情報N(uAP)に対応するすべての子ノード情報N(uAC)に対して以下のステップＳ１４２１とＳ１４２２の処理を実行する。
【００７２】
ステップＳ１４２１では、設定部１４６の情報設定部１４６ａが、記憶部１４３から多項式q(uAP, α)と、処理対象の親ノード情報N(uAP)の各子ノード情報N(uAC)に対応する識別子index(uAC)とを読み出す。情報設定部１４６ａは、処理対象の親ノード情報N(uAP)に対応する多項式q(uAP, α)に、当該親ノード情報N(uAP)に対応する子ノード情報N(uAC)に対応する識別子index(uAC)を代入して得られるq(uAP, index(uAC))を、当該子ノード情報N(uAC)に対応する情報q(uAC, 0)として設定する。各子ノード情報N(uAC)に対応する情報q(uAC, 0)は、記憶部１４３に格納される（ステップＳ１４２１）。
【００７３】
ステップＳ１４２２では、設定部１４６の多項式設定部１４６ｂが、記憶部１４３からステップＳ１４２１で設定された情報q(uAC, 0)を読み出し、当該情報q(uAC, 0)が設定された子ノード情報N(uAC)に対し、定数項（α=0であるときの関数値）をq(uAC, 0)=q(uAP, index(uAC))とする不定元αについての次数d(uAC)=k(uAC)-1の多項式q(uAC, α)を設定する。例えば、多項式設定部１４６ｂは、d(uAC)個の互いに異なる任意点(α2, β2)（α2, β2∈UZp，α2≠0）をそれぞれランダムに選択し、それらを通る定数項q(uAC, 0)の多項式q(uAC, α)を特定する。定められた多項式q(uAC, α)は記憶部１４３に格納される（ステップＳ１４２２）（［図５Ｂのループ処理］の説明終わり）。
【００７４】
ステップＳ１４１４の処理が終了すると、次に、設定部１４６は、多項式q(uAC, α)が設定された子ノード情報N(uAC)に対応するさらなる子ノード情報が存在するか否かを判定する（ステップＳ１４１５）。ここで、さらなる子ノード情報が存在すると判定された場合、設定部１４６は、さらなる子ノード情報が存在すると判定されたすべての子ノード情報N(uAC)について、それぞれ、uAPをuAC（uAP←uAC）とおき、その場合のすべての親ノード情報N(uAP)を処理対象として図５Ｂのループ処理をそれぞれ実行し、その後、ステップＳ１４１５に戻る（ステップＳ１４１６）。
【００７５】
一方、ステップＳ１４１５で、さらなる子ノード情報が存在しないと判定された場合、秘密値生成部１４７が、記憶部１４３からすべての葉ノード情報N(uAL)に対応する属性情報att(uAL)∈ATT及び情報q(uAL, 0)をそれぞれ読み出し、各秘密値
D(uAL)=g1q(uAL, 0)/t(att(uAL))∈G1 …(6)
を生成する。生成された秘密値D(uAL)(uAL∈L(γA))の集合である長期秘密鍵DA={D(uAL)}uAL∈L(γA)が記憶部１４３に格納される（ステップＳ１４１７）。長期秘密鍵DA={D(uAL)}uAL∈L(γA)は出力部１４２に送られ、そこから鍵交換装置１１０（図２）に安全に送られ、鍵交換装置１１０の入力部１１１ａに入力され、記憶部１１２に格納される（ステップＳ１４１８）。
【００７６】
これにより、木構造データγAのノード情報N(uA)のそれぞれに不定元αについての次数d(uA)=k(uA)-1の多項式q(uA, α)が対応し、その結果、ノード情報N(uA)のそれぞれには情報（定数項）q(uA, 0)が対応する。ルートノード情報N(uAR)に対応する情報q(uAR, 0)はマスタ秘密鍵λであり、親ノード情報N(uAP)に対応する情報q(uAP, 0)をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uAP)に対応する子ノード情報N(uAC)に対応する情報q(uAC, 0)であり、葉ノード情報N(uAL)にはそれぞれ秘密値D(uAL)=g1q(uAL, 0)/t(att(uAL))∈G1が対応し、秘密値D(uAL)(uAL∈L(γA))の集合が長期秘密鍵DA={D(uAL)}uAL∈L(γA)となる。
【００７７】
例えば、前述した図８Ａ及び図８Ｂに例示する木構造データγA（論理式(1∧2)∨4の例）の場合、図９Ａ及び図９Ｂに例示するように、木構造データγAのノード情報N(uA)(uA=1,...,5)のそれぞれに不定元αについての次数d(uA)=k(uA)-1の多項式q(uA, α)が対応し、その結果、ノード情報N(uA)のそれぞれには情報q(uA, 0)が対応する。ルートノード情報N(1)に対応する情報q(1, 0)はマスタ秘密鍵λである。親ノード情報（ルートノード情報）N(1)に対応する情報q(1, 0)をk(1)-out-of-c(1)（1-out-of-2）しきい値秘密分散して得られる分散情報である情報q(1,1), q(1,2)が、それぞれ子ノード情報N(2),N(5)に対応する情報q(2,0), q(5,0)である。また、親ノード情報N(2)に対応する情報q(2, 0)をk(2)-out-of-c(2)（2-out-of-2）しきい値秘密分散して得られる分散情報である情報q(2,1), q(2,2)が、それぞれ子ノード情報N(3), N(4)に対応する情報q(3,0), q(4,0)である。また、葉ノード情報N(3), N(4), N(5)にはそれぞれ秘密値D(3)=g1q(3, 0)/t(1), D(4)=g1q(4, 0)/t(2), D(5)=g1q(5, 0)/t(4) ∈G1が対応し、D(3), D(4), D(5)の集合が長期秘密鍵DAとなる。
【００７８】
また、例えば、前述した図１０Ａ及び図１０Ｂに例示する木構造データγA（論理式(1∧2)∨(2∧3)∨(1∧3)∨4−の例）の場合、図１１Ａ及び図１１Ｂに例示するように、木構造データγAのノード情報N(uA)(uA=1,...,6)のそれぞれに不定元αについての次数d(uA)=k(uA)-1の多項式q(uA, α)が対応し、その結果、ノード情報N(uA)のそれぞれには情報q(uA, 0)が対応する。ルートノード情報N(1)に対応する情報q(1, 0)はマスタ秘密鍵λである。親ノード情報（ルートノード情報）N(1)に対応する情報q(1, 0)をk(1)-out-of-c(1)（1-out-of-2）しきい値秘密分散して得られる分散情報である情報q(1,1), q(1,2)が、それぞれ子ノード情報N(2),N(6)に対応する情報q(2,0), q(6,0)である。また、親ノード情報N(2)に対応する情報q(2, 0)をk(2)-out-of-c(2)（2-out-of-3）しきい値秘密分散して得られる分散情報である情報q(2,1), q(2,2), q(2,3)が、それぞれ子ノード情報N(3), N(4) , N(5)に対応する情報q(3,0), q(4,0), q(5,0)である。また、葉ノード情報N(3), N(4), N(5) ,N(6)にはそれぞれ秘密値D(3)=g1q(3, 0)/t(1), D(4)=g1q(4, 0)/t(2), D(5)=g1q(5, 0)/t(3), D(6)=g1q(6, 0)/t(5) ∈G1が対応し、D(3), D(4), D(5), D(6)の集合が長期秘密鍵DAとなる。
【００７９】
＜鍵交換処理＞
次に、鍵交換装置１１０の処理を表す図６と鍵交換装置１２０の処理を表す図７とを用い、本形態の鍵交換処理を説明する。なお、本形態では、鍵交換装置１１０がイニシエータとして機能し、鍵交換装置１２０がレスポンダとして機能する例を示す。
【００８０】
まず、鍵交換装置１１０（図２）の入力部１１１ａに属性情報の集合ATTの部分集合である属性集合δA⊂ATTが入力される。属性集合δAは任意に選択されたものである。例えば、属性集合δAが鍵交換装置１２０の木構造データを満たすならば認証成功となって鍵交換装置１２０とセッション鍵を共有できることを期待して任意に選択された属性集合δAが入力部１１１ａに入力される。属性集合δAは記憶部１１２に格納される（図６／ステップＳ１１１１）。
【００８１】
次に、短期秘密鍵生成部１１５ａが短期秘密鍵sA∈UZpを任意に生成し、ハッシュ演算部１１５ｂに送る（ステップＳ１１１２）。ハッシュ演算部１１５ｂは、記憶部１１２から長期秘密鍵DAを読み出し、ハッシュ値（長期秘密鍵DAと短期秘密鍵sAとを含む値の像）
χ=H'(DA, sA)∈Zp …(7)
を生成して、ハッシュ値χを記憶部１１２に格納する（ステップＳ１１１３）。なお、H'(DA, sA)は、長期秘密鍵DAと短期秘密鍵sAとに対応するバイナリ系列のハッシュ値を表す。長期秘密鍵DAと短期秘密鍵sAとの組をバイナリ系列に写す関数に限定はないが、鍵生成装置１１０，１２０で同一の関数を用いる必要がある。長期秘密鍵DAと短期秘密鍵sAとに対応するバイナリ系列の例は、長期秘密鍵DAと短期秘密鍵sAとのビット結合である。
【００８２】
次に、短期公開鍵生成部１１５ｄが、記憶部１１２から読み出したハッシュ値χを用い、元
X=g1χ∈G1 …(8)
を生成して記憶部１１２に格納する（ステップＳ１１１４）。また、短期公開鍵生成部１１５ｃは、記憶部１１２に格納されたマスタ公開鍵{T(j)}j∈ATTから属性集合δAに対応するT(wA)(wA∈δA)の集合とハッシュ値χとを読み出す。短期公開鍵生成部１１５ｃは、ハッシュ値χに対する元
T(wA)χ∈G2(wA∈δA) …(9)
の集合である
TA={T(wA)χ}wA∈δA …(10)
を生成して記憶部１１２に格納する（ステップＳ１１１５）。本形態では、元Xと集合TAとが短期公開鍵となる。
【００８３】
記憶部１１２に格納された属性集合δAと短期公開鍵X, TAとは出力部１１１ｂに入力され、出力部１１１ｂは、属性集合δAと短期公開鍵X, TAとを鍵交換装置１２０に対して出力する（ステップＳ１１１６）。
【００８４】
属性集合δAと短期公開鍵X, TAとは、鍵交換装置１２０（図３）の入力部１２１ａに入力され、記憶部１２２に格納される（図７／ステップＳ１２１１）。すると、判定部１２４が、記憶部１２２に格納された属性集合δAと木構造データγBに対応する論理式を特定する情報とを読み出し、属性集合δAが木構造データγBを満たすか否かを判定する（ステップＳ１２１２）。ここで、属性集合δAが木構造データγBを満たさないと判定された場合、処理がエラー終了する。一方、属性集合δAが木構造データγBを満たすと判定された場合、判定部１２４が、記憶部１２２に格納されたマスタ公開鍵{T(j)}j∈ATTと短期公開鍵X, TA={T(wA)χ}wA∈δAと属性集合δAとを読み出し、属性集合δAに属するすべての属性情報wA∈δAについて、
e(X, T(wA))=e(g1,T(wA)χ) …(11)
が成り立つか否かを判定する（ステップＳ１２１３）。ここで、少なくとも一部の属性情報wA∈δAについて式(11)が成り立たないと判定された場合、処理がエラー終了する。一方、すべての属性情報wA∈δAについて式(11)が成り立つと判定された場合、入力部１２１ａが属性情報の集合ATTの部分集合である属性集合δB⊂ATTの入力を受け付ける。属性集合δAと同様、属性集合δBは任意に選択されたものである。入力された属性集合δBは記憶部１２２に格納される（ステップＳ１２１４）。
【００８５】
次に、短期秘密鍵生成部１２５ａが短期秘密鍵sB∈UZpを任意に生成し、ハッシュ演算部１２５ｂに送る（ステップＳ１２１５）。ハッシュ演算部１２５ｂは、記憶部１２２から長期秘密鍵DBを読み出し、ハッシュ値（長期秘密鍵DBと短期秘密鍵sBとを含む値の像）
υ=H'(DB, sB)∈Zp …(12)
を生成して、ハッシュ値υを記憶部１２２に格納する（ステップＳ１２１６）。なお、H'(DB, sB)は、長期秘密鍵DBと短期秘密鍵sBとに対応するバイナリ系列のハッシュ値を表す。長期秘密鍵DBと短期秘密鍵sBとの組をバイナリ系列に写す関数に限定はないが、鍵生成装置１１０，１２０で同一の関数を用いる必要がある。長期秘密鍵DBと短期秘密鍵sBとに対応するバイナリ系列の例は、長期秘密鍵DBと短期秘密鍵sBとのビット結合である。
【００８６】
次に、短期公開鍵生成部１２５ｄが、記憶部１２２から読み出したハッシュ値υを用い、元
Y=g1υ∈G1 …(13)
を生成して記憶部１２２に格納する（ステップＳ１２１７）。また、短期公開鍵生成部１２５ｃは、記憶部１２２に格納されたマスタ公開鍵{T(j)}j∈ATTから属性集合δBに対応するT(wB)(wB∈δB)の集合とハッシュ値υとを読み出す。短期公開鍵生成部１２５ｃは、ハッシュ値υに対する元
T(wB)υ∈G2 (wB∈δB) …(14)
の集合である
TB={T(wB)υ}wB∈δB …(15)
を生成して記憶部１２２に格納する（ステップＳ１２１８）。本形態では、元Yと集合TBとが短期公開鍵となる。
【００８７】
記憶部１２２に格納された属性集合δBと短期公開鍵Y, TBとは出力部１２１ｂに入力され、出力部１２１ｂは、属性集合δBと短期公開鍵Y, TBとを鍵交換装置１１０に対して出力する（ステップＳ１２１９）。
【００８８】
また、葉ノード復元値生成部１２６が、記憶部１２２に格納された属性集合δAと木構造データγBとを参照し、属性集合δAに属する属性情報att(uBL)∈δAに対応する木構造データγBの葉ノード情報N(uBL)に対応する秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1を記憶部１２２に格納された長期秘密鍵DBから抽出する。さらに、葉ノード復元値生成部１２６は、当該葉ノード情報N(uBL)に対応する属性情報att(uBL)∈ATTに対応する元T(att(uBL))χを短期公開鍵TAから抽出する。葉ノード復元値生成部１２６は、当該葉ノード情報N(uBL)ごとに、秘密値D(uBL)と元T(att(uBL))χとを作用させ、各葉ノード情報N(uBL)に対する各復元値
e(D(uBL), T(att(uBL))χ)=gTχ・q(uBL, 0)∈GT …(16)
を生成して記憶部１２２に格納する（ステップＳ１２２０）。
【００８９】
次に、判定部１２４は、記憶部１２２に格納された復元値と木構造データγBとを参照し、自らに対応する子ノード情報N(uBC)のうち復元値gTχ・q(uBC, 0)∈GTが生成されたものの合計数が自らに対応するしきい値k(uBP)以上となる親ノード情報N(uBP)が存在されたか否かを判定する。すなわち、判定部１２４は、親ノード情報N(uBP)に対応する子ノード情報N(uBC)のうち復元値gTχ・q(uBC, 0)∈GTが生成されたもののuBCの集合をS(uBP)'とした場合に、
|S(uBP)'|≧k(uBP) …(17)
を満たす親ノード情報N(uBP)が存在するか否かを判定する（ステップＳ１２２１）。ただし、|S(uBP)'|は集合S(uBP)'の要素数を表す。ここで、式(17)を満たす親ノード情報N(uBP)が存在しないと判定された場合、処理がエラー終了する。一方、式(17)を満たす親ノード情報N(uBP)が存在すると判定された場合、親ノード復元値生成部１２７は、式(17)を満たす親ノード情報N(uBP)に対応するしきい値k(uBP)以上の子ノード情報N(uBC)の復元値gTχ・q(uBC, 0)∈GTを、k(uBP)-out-of-c(uBP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値
gTχ・q(uBP, 0)∈GT …(18)
を生成して記憶部１２２に格納する。例えば、親ノード復元値生成部１２７は、集合S(uBP)'の部分集合であるk(uBP)個のuBCからなる集合S(uBP)〜⊂S(uBP)'を選択し、集合S(uBP)〜の要素であるk(uBP)個のuBC∈S(uBP)〜にそれぞれ対応する復元値gTχ・q(uBC, 0)を用い、ラグランジェの補間公式（式(3),(4)）に従って、
【００９０】
【数２】
を計算する。ただし、q(uBC,0)=q(uBP,index(uBC))を満たす。この処理は、式(17)を満たすすべての親ノード情報N(uBP)に対して実行される。これにより、式(17)を満たすすべての親ノード情報N(uBP)に対応する復元値gTχ・q(uBP, 0)がそれぞれ得られる（ステップＳ１２２２）。
【００９１】
次に、判定部１２４は、ステップＳ１２２２においてルートノード情報N(uAR)に対応する復元値gTχ・q(uAR, 0)が得られたか否かを判定する（ステップＳ１２２３）。ここで、ルートノード情報N(uAR)に対応する復元値gTχ・q(uAR, 0)が得られていないと判定された場合、ステップＳ１２２１の処理に戻る。一方、ルートノード情報N(uAR)に対応する復元値gTχ・q(uAR, 0)が得られたと判定された場合、演算部１２８が記憶部１２２からgTχ・q(uAR, 0)=gTχ・λ∈GTとマスタ公開鍵Λと短期公開鍵Xとハッシュ値υとを読み込み、
σ1=gTχ・λ∈GT …(20)
σ2=Λυ=gTυ・λ∈GT …(21)
σ3=Xυ∈G1 …(22)
を生成する（ステップＳ１２２４）。生成されたσ1, σ2, σ3は鍵生成部１２９に送られる。鍵生成部１２９は記憶部１２２から短期公開鍵X, Y, TA, TBと属性集合δAとδBとを読み込み、さらに述語P及びプロトコルＩＤであるΩを用い、セッション鍵
K=H(σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB)) …(23)
を生成して出力する。なお、H(σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB))は、σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB)に対応するバイナリ系列のハッシュ値を表す。これらの情報の組をバイナリ系列に写す関数に限定はないが、鍵生成装置１１０，１２０で同一の関数を用いる必要がある（ステップＳ１２２５）。
【００９２】
一方、ステップＳ１２１９で鍵交換装置１２０から出力された属性集合δBと短期公開鍵Y, TBとは、鍵交換装置１１０（図２）の入力部１１１ａに入力され、記憶部１１２に格納される（図６／ステップＳ１１１７）。すると、判定部１１４が、記憶部１１２に格納された属性集合δBと木構造データγAに対応する論理式を特定する情報とを読み出し、属性集合δBが木構造データγAを満たすか否かを判定する（ステップＳ１１１８）。ここで、属性集合δBが木構造データγAを満たさないと判定された場合、処理がエラー終了する。一方、属性集合δBが木構造データγAを満たすと判定された場合、判定部１１４が、記憶部１１２に格納されたマスタ公開鍵{T(j)}j∈ATTと短期公開鍵Y, TB={T(wB)υ}wB∈δBと属性集合δBとを読み出し、属性集合δBに属するすべての属性情報wB∈δBについて、
e(Y, T(wB))=e(g1,T(wB)υ) …(24)
が成り立つか否かを判定する（ステップＳ１１１９）。ここで、少なくとも一部の属性情報wB∈δBについて式(24)が成り立たないと判定された場合、処理がエラー終了する。一方、すべての属性情報wB∈δBについて式(24)が成り立つと判定された場合、葉ノード復元値生成部１１６が、記憶部１１２に格納された属性集合δBと木構造データγAとを参照し、属性集合δBに属する属性情報att(uAL)∈δBに対応する木構造データγAの葉ノード情報N(uAL)に対応する秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1を記憶部１１２に格納された長期秘密鍵DAから抽出する。さらに、葉ノード復元値生成部１１６は、当該葉ノード情報N(uAL)に対応する属性情報att(uAL)∈ATTに対応する元T(att(uAL))υを短期公開鍵TBから抽出する。葉ノード復元値生成部１１６は、当該葉ノード情報N(uAL)ごとに、秘密値D(uAL)と元T(att(uAL))υとを作用させ、各葉ノード情報N(uAL)に対する各復元値
e(D(uAL), T(att(uAL))υ)=gTυ・q(uAL, 0)∈GT …(25）
を生成して記憶部１１２に格納する（ステップＳ１１２０）。
【００９３】
次に、判定部１１４は、記憶部１１２に格納された復元値と木構造データγAとを参照し、自らに対応する子ノード情報N(uAC)のうち復元値gTυ・q(uAC, 0)∈GTが生成されたものの合計数が自らに対応するしきい値k(uAP)以上となる親ノード情報N(uAP)が存在されたか否かを判定する。すなわち、判定部１１４は、親ノード情報N(uAP)に対応する子ノード情報N(uAC)のうち復元値gTυ・q(uAC, 0)∈GTが生成されたもののuACの集合をS(uAP)'とした場合に、
|S(uAP)'|≧k(uAP) …(26）
を満たす親ノード情報N(uAP)が存在するか否かを判定する（ステップＳ１１２１）。ただし、|S(uAP)'|は集合S(uAP)'の要素数を表す。ここで、式(26）を満たす親ノード情報N(uAP)が存在しないと判定された場合、処理がエラー終了する。一方、式(26）を満たす親ノード情報N(uAP)が存在すると判定された場合、親ノード復元値生成部１１７は、式(26）を満たす親ノード情報N(uAP)に対応するしきい値k(uAP)以上の子ノード情報N(uAC)の復元値gTυ・q(uAC, 0)∈GTをk(uAP)-out-of-c(uAP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値
gTυ・q(uAP, 0)∈GT …(27）
を生成して記憶部１１２に格納する。例えば、親ノード復元値生成部１１７は、集合S(uAP)'の部分集合であるk(uAP)個のuACからなる集合S(uAP)〜⊂S(uAP)'を選択し、集合S(uAP)〜の要素であるk(uAP)個のuAC∈S(uAP)〜にそれぞれ対応する復元値gTυ・q(uAC, 0)を用い、ラグランジェの補間公式（式(3),(4)）に従って、
【００９４】
【数３】
を計算する。ただし、q(uAC,0)=q(uAP,index(uAC))を満たす。この処理は、式(26）を満たすすべての親ノード情報N(uAP)に対して実行される。これにより、式(26）を満たすすべての親ノード情報N(uAP)に対応する復元値gTυ・q(uAP, 0)がそれぞれ得られる（ステップＳ１１２２）。
【００９５】
次に、判定部１１４は、ステップＳ１１２２においてルートノード情報N(uBR)に対応する復元値gTυ・q(uBR, 0)が得られたか否かを判定する（ステップＳ１１２３）。ここで、ルートノード情報N(uBR)に対応する復元値gTυ・q(uBR, 0)が得られていないと判定された場合、ステップＳ１１２１の処理に戻る。一方、ルートノード情報N(uBR)に対応する復元値gTυ・q(uBR, 0)が得られたと判定された場合、演算部１１８が記憶部１１２からgTυ・q(uBR, 0)=gTυ・λ∈GTとマスタ公開鍵Λと短期公開鍵Xとハッシュ値υとを読み込み、
σ1=Λχ=gTχ・λ∈GT …(29）
σ2=gTυ・λ∈GT …(30)
σ3=Yχ∈G1 …(31)
を生成する（ステップＳ１１２４）。生成されたσ1, σ2, σ3は鍵生成部１１９に送られる。鍵生成部１１９は記憶部１１２から短期公開鍵X, Y, TA, TBと属性集合δAとδBとを読み込み、さらに述語P及びプロトコルＩＤであるΩを用い、セッション鍵
K=H(σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB)) …(32)
を生成して出力する。なお、H(σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB))は、σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB)に対応するバイナリ系列のハッシュ値を表す。これらの情報の組をバイナリ系列に写す関数に限定はないが、鍵生成装置１１０，１２０で同一の関数を用いる必要がある（ステップＳ１１２５）。
【００９６】
ここで、鍵交換装置１１０，１２０でそれぞれ生成されたσ1, σ2, σ3は、
σ1=gTχ・λ∈GT …(33）
σ2=gTυ・λ∈GT …(34)
σ3=g1χ・υ∈G1 …(35)
となる。よって、P(δB, γA)=1かつP(δA, γB)=1の場合に鍵交換装置１１０，１２０は同一のセッション鍵Kを共有できる。また、前述のように本形態ではeCKモデルでの安全性が確保される。
【００９７】
〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上記の実施形態では、σ1, σ2, σ3に対応するセッション鍵Kが生成される例を示したが、鍵交換装置１１０，１２０がσ3を生成することなく、σ1, σ2に対応するセッション鍵Kを生成する形態でもよい。この場合、元X, Yの生成は不要となり、鍵交換装置１１０が生成する短期公開鍵は集合TAであり、鍵交換装置１２０が生成する短期公開鍵は集合TBとなる。
【００９８】
また、上記の実施形態では
K=H(σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB))
をセッション鍵としたが、σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB)と所定の付加情報とに依存するバイナリ系列のハッシュ値をセッション鍵としてもよい。また、σ1, σ2と所定の付加情報とに依存するバイナリ系列のハッシュ値をセッション鍵としてもよく、σ1, σ2, σ3と所定の付加情報とに依存するバイナリ系列のハッシュ値をセッション鍵としてもよい。付加情報の例は巡回群G1, G2, GTを特定する情報、生成元g1, g2, gTを特定する情報、位数pを特定する情報などである。ただし、鍵交換装置１１０，１２０でセッション鍵を生成する際の付加情報は互いに同一である必要がある。
【００９９】
また、上記の実施形態で用いたハッシュ関数Hの代わりに、ハッシュ関数Hと定義域と地域とが同一のその他の関数（共通鍵暗号関数など）を用いてもよい。同様に、ハッシュ関数H'の代わりに、ハッシュ関数H'と定義域と地域とが同一のその他の関数を用いてもよい。
【０１００】
また、実施形態では、ステップＳ１１１８，Ｓ１１１９の判定でyesとなった場合にのみステップＳ１１２０以降の処理が実行され、ステップＳ１２１２，Ｓ１２１３の判定でyesとなった場合にのみステップＳ１２１４以降の処理が実行されることとした。しかし、ステップＳ１１１８，Ｓ１１１９やステップＳ１２１２，Ｓ１２１３の判定を行うことなく、ステップＳ１１２０以降の処理やステップＳ１２１４以降の処理が実行されてもよい。
【０１０１】
また、木構造データγAやγBが鍵交換装置１１０，１２０内に格納されるのではなく、木構造データγAやγBが含むしきい値などの情報が必要となるたびに、それらの情報が鍵交換装置１１０，１２０に与えられる構成であってもよい。さらに、しきい値秘密分散法に限定はなく、公知のどのような方法を用いてもよい。また、環Zpでの演算の代わりに整数での演算が行われてもよい。
【０１０２】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０３】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１０４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１０８】
１ 鍵交換システム
１１０，１２０ 鍵交換装置
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関するものであり、特に、二者間で共通のセッション鍵を共有する鍵交換技術に関するものである。
【背景技術】
【０００２】
従来のID認証鍵交換方式の一つにSYL方式があった（例えば、非特許文献１参照）。以下にSYL方式の概要を説明する。
【０００３】
［パラメータ］
G, GTをκビットの素数位数pの巡回群、gをGの生成元、gT=e(g,g)をGTの生成元、e:G×G→GTをペアリングとする。H:{0,1}*→{0,1}κとし、H1:{0,1}*→Gをハッシュ関数とする。鍵生成者は、マスタ秘密鍵λ∈Zpをランダムに選び、マスタ公開鍵Λ=gλ∈Gを公開する。
【０００４】
［鍵生成］
鍵生成者は、ユーザA,Bの識別子IDA, IDB∈{0,1}*に対して、それぞれQA=H1(IDA)∈G, QB=H1(IDB)∈Gを計算し、マスタ秘密鍵λを用いて秘密鍵DA=QAλ∈G, DB=QBλ∈Gを生成する。
【０００５】
[鍵交換]
識別子IDAと秘密鍵DA=QAλ∈GをもつユーザAと、識別子IDBと秘密鍵DB=QBλ∈GをもつユーザBは、以下のようにして認証鍵交換を行い、セッション鍵（共有鍵）Kを共有する。
【０００６】
ユーザAは、ランダムに短期秘密鍵χA∈UZpを選び、短期公開鍵XA=gχAを計算し、(IDA,IDB,XA)をユーザBに送る。
【０００７】
ユーザBは、(IDA,IDB,XA)を受信し、ランダムに短期秘密鍵χB∈UZpを選び、短期公開鍵XB=gχBを計算し、(IDA,IDB,XA,XB)をユーザAに送る。ユーザBは、σ1=e(QA・XA, DB・ΛχB), σ2=XAχBを計算し、セッション鍵K=H(σ1,σ2,IDA,IDB,XA,XB)を計算する。
【０００８】
ユーザAは、(IDA,IDB,XA,XB)を受信し、σ1=e(DA・ΛχA,QB・XB),σ2=XBχAを計算し、セッション鍵K=H(σ1,σ2,IDA,IDB,XA,XB)を計算する。
【０００９】
σ1=gTλ(log(QA)+χA)・(log(QB)+χB), σ2=gχA・χBとなるので、両者で計算したセッション鍵Kは一致する。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】L. Chen, Z. Cheng, Nigel P. Smart, "Identity-based key agreement protocols from pairings", Int. J. Inf. Sec. 6(4): 213-241 (2007).
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかし、SYL方式は、相手が指定したIDと自分のIDが一致した場合にのみセッション鍵を生成できるという単純な方式であり、セッション鍵を共有する相手を多様な条件で指定することができなかった。
【００１２】
本発明はこのような点に鑑みてなされたものであり、セッション鍵を共有する相手を多様な条件で指定することができる鍵交換技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明では、第１鍵交換装置と第２鍵交換装置とでセッション鍵を生成する。巡回群G1, G2, GTの生成元がそれぞれg1, g2, gTであり、直積空間G1×G2の元を巡回群GTに写す双線形写像がe: G1×G2→GTであり、属性情報jの集合がATTであり、マスタ秘密鍵がλ及びt(j)(j∈ATT)であり、マスタ公開鍵がΛ=gTλ∈GT及びT(j)=g2t(j)∈G2である。UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む木構造データγAが第１鍵交換装置に対応し、ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、葉ノード情報N(uAL)に対応するuALの集合がL(γA)であり、親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、ノード情報N(uA)のそれぞれには情報q(uA, η(uA))が対応し、ルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))がマスタ秘密鍵λであり、親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uAP)に対応する子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))であり、葉ノード情報N(uAL)にはそれぞれ属性情報att(uAL)∈ATTと秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1とが対応し、秘密値D(uAL)(uAL∈L(γA))の集合が第１鍵交換装置の長期秘密鍵DA={D(uAL)}uAL∈L(γA)である。UB(UB≧2)個のノード情報N(uB)(uB∈{1,...,UB})を含む木構造データγBが第２鍵交換装置に対応し、ノード情報N(uB)の一部が親ノード情報N(uBP)(uBP∈{1,...,UB})であり、親ノード情報N(uBP)にはc(uBP)個の子ノード情報N(uBC)(uBC∈{1,...,UB})が対応し、親ノード情報N(uBP)の何れか１つがルートノード情報N(uBR)(uBR∈{1,...,UB})であり、子ノード情報N(uBC)の少なくとも一部が葉ノード情報N(uBL)(uBL∈{1,...,UB})であり、葉ノード情報N(uBL)に対応するuBLの集合がL(γB)であり、親ノード情報N(uBP)のそれぞれには1≦k(uBP)≦c(uBP)を満たすしきい値k(uBP) が対応し、ノード情報N(uB)のそれぞれには情報q(uB, η(uB))が対応し、ルートノード情報N(uBR)に対応する情報q(uBR, η(uBR))がマスタ秘密鍵λであり、親ノード情報N(uBP)に対応する情報q(uBP, η(uBP))をk(uBP)-out-of-c(uBP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uBP)に対応する子ノード情報N(uBC)に対応する情報q(uBC, η(uBC))であり、葉ノード情報N(uBL)にはそれぞれ属性情報att(uBL)∈ATTと秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1とが対応し、秘密値D(uBL)(uBL∈L(γB))の集合が第２鍵交換装置の長期秘密鍵DB={D(uBL)}uBL∈L(γB)である。
【００１４】
第１鍵交換装置は、短期秘密鍵sAを任意に生成し、属性情報の集合ATTの部分集合である属性集合δA⊂ATTと長期秘密鍵DAと短期秘密鍵sAとを用い、長期秘密鍵DAと短期秘密鍵sAとを含む値の像χに対する元T(wA)χ∈G2 (wA∈δA)の集合であるTA={T(wA)χ}wA∈δAを含む第１短期公開鍵を生成し、属性集合δAと第１短期公開鍵とを第２鍵交換装置に対して出力する。
【００１５】
第２鍵交換装置は、短期秘密鍵sBを任意に生成し、属性情報の集合ATTの部分集合である属性集合δB⊂ATTと長期秘密鍵DBと短期秘密鍵sBとを用い、長期秘密鍵DBと短期秘密鍵sBとを含む値の像υに対する元T(wB)υ∈G2 (wB∈δB)の集合であるTB={T(wB)υ}wB∈δBを含む第２短期公開鍵を生成し、属性集合δBと第２短期公開鍵とを第１鍵交換装置に対して出力する。
【００１６】
第１鍵交換装置は、属性集合δBと第２短期公開鍵との入力を受け付け、属性集合δBに属する属性情報att(uAL)∈δBに対応する葉ノード情報N(uAL)に対応する秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1と第２短期公開鍵が含む元T(att(uAL))υ∈G2とに対し、双線形写像eを作用させ、葉ノード情報N(uAL)に対して復元値e(D(uAL), T(att(uAL))υ)=gTυ・q(uAL, η(uAL))∈GTを生成し、自らに対応する子ノード情報N(uAC)のうち復元値gTυ・q(uAC, η(uAC))∈GTが生成されたものの合計数が自らに対応するしきい値k(uAP)以上となる親ノード情報N(uAP)に対し、当該しきい値k(uAP)以上の復元値gTυ・q(uAC, η(uAC))∈GTをk(uAP)-out-of-c(uAP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTυ・q(uAP, η(uAP))∈GTを生成する。ここで、ルートノード情報N(uAR)に対する復元値gTυ・q(uAR, η(uAR))=gTυ・λ∈GTが生成された場合、第１鍵交換装置は、Λχ=gTχ・λ∈GTとgTυ・λ∈GTとを含む値の像を第１セッション鍵として出力する。
【００１７】
第２鍵交換装置は、属性集合δAと第１短期公開鍵との入力を受け、属性集合δAに属する属性情報att(uBL)∈δAに対応する葉ノード情報N(uBL)に対応する秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1と第１短期公開鍵が含む元T(att(uBL))χ∈G2とに対し、双線形写像eを作用させ、葉ノード情報N(uBL)に対して復元値e(D(uBL), T(att(uBL))χ)=gTχ・q(uBL, η(uBL))∈GTを生成し、自らに対応する子ノード情報N(uBC)のうち復元値gTχ・q(uBC, η(uBC))∈GTが生成されたものの合計数が自らに対応するしきい値k(uBP)以上となる親ノード情報N(uBP)に対し、当該しきい値k(uBP)以上の復元値gTχ・q(uBC, η(uBC))∈GTをk(uBP)-out-of-c(uBP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTχ・q(uBP, η(uBP))∈GTを生成する。ここで、ルートノード情報N(uBR)に対する復元値gTχ・q(uBR, η(uBR))=gTχ・λ∈GTが生成されたた場合、第２鍵交換装置は、gTχ・λ∈GTとΛυ=gTυ・λ∈GTとを含む値の像を第２セッション鍵として出力する。
【発明の効果】
【００１８】
本発明の木構造データγA,γBはそれぞれ特定の論理式に対応し、属性集合δAが木構造データγBに対応する論理式を真にし、属性集合δBが木構造データγAに対応する論理式を真にする場合に、第１鍵交換装置と第２鍵交換装置との間で同一のセッション鍵が生成される。そのため、本発明では、セッション鍵を共有する相手を多様な条件で指定することができる。
【図面の簡単な説明】
【００１９】
【図１】図１は、実施形態での鍵交換システムの全体構成を説明するための図である。
【図２】図２は、実施形態での鍵交換装置の構成を説明するための図である。
【図３】図３は、実施形態での鍵交換装置の構成を説明するための図である。
【図４】図４は、実施形態での鍵抽出装置の構成を説明するための図である。
【図５】図５Ａ及び図５Ｂは、実施形態での鍵抽出方法を説明するための図である。
【図６】図６は、実施形態での鍵交換方法を説明するための図である。
【図７】図７は、実施形態での鍵交換方法を説明するための図である。
【図８】図８Ａ及び図８Ｂは、木構造データを例示するための図である。
【図９】図９Ａ及び図９Ｂは、木構造データを例示するための図である。
【図１０】図１０Ａ及び図１０Ｂは、木構造データを例示するための図である。
【図１１】図１１Ａ及び図１１Ｂは、木構造データを例示するための図である。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施形態を説明する。
【００２１】
＜定義＞
本形態で使用する用語を定義する。
∧：∧は論理積を表す。
∨：∨は論理和を表す。
・−：・−は・の否定を表す。
Z：Zは整数集合を表す。
κ：κはセキュリティパラメータ（κ∈Z, κ>0）を表す。
Zp：Zpは位数p（p≧１）の環を表す。Zpの例はpを法とする剰余環である。また、pの例はκビットの素数である。ただし、これらの例は本発明を限定するものではない。
ξ∈UZp：ξ∈UZpは、Zpの任意の元ξを選択することを表す。
【００２２】
{0,1}*：{0,1}*は任意ビット長のバイナリ系列を表す。その一例は、整数0及び1からなる系列である。ただし、{0,1}*は整数0及び1からなる系列に限定されない。{0,1}*は位数2の有限体又はその拡大体と同義である。
【００２３】
{0,1}ζ：{0,1}ζはビット長ζ（ζ∈Z, ζ>0）のバイナリ系列を表す。その一例は、整数0及び1からなる系列である。しかし、{0,1}ζは整数0及び1からなる系列に限定されない。{0,1}ζは位数2の有限体（ζ=1の場合）又はそれをζ次拡大した拡大体（ζ>1の場合）と同義である。
【００２４】
G1, G2, GT：G1, G2, GTのそれぞれは予め定められた巡回群を表し、g1, g2, gTのそれぞれは巡回群G1, G2, GTの生成元を表す。本形態の例では、G1, G2, GTがκビットの素数位数pの巡回群であるものとして説明する。なお、G1=G2であってもよいしG1≠G2であってもよい。巡回群G1, G2の具体例は、楕円曲線の等分点からなる有限集合やその部分群である。巡回群GTの具体例は、拡大体を構成する有限集合からなる群である。なお、本形態では、巡回群G1, G2, GT上で定義された演算が乗法的に表現される。すなわち、β∈Zp及びψ∈G1に対するψβ∈G1は、ψ∈G1に対して巡回群G1で定義された演算をβ回施すことを意味し、ψ1, ψ2∈G1に対するψ1・ψ2∈G1は、ψ1∈G1とψ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。巡回群G2, GTについても同様である。
【００２５】
e：eは、直積空間G1×G2の元を巡回群GTに写す双線形写像G1×G2→GTを表し、e(g1, g2)=gTを満たす。双線形写像eは以下の性質を満たす。
【００２６】
［双線形性］すべてのψ1∈G1，ψ2∈G2及びε，ζ∈Zpについて以下の関係を満たす。
e(ψ1ε,ψ2ζ)=e(ψ1, ψ2)ε・ζ …(1)
［非退化性］すべての
ψ1∈G1，ψ2∈G2 …(2)
を巡回群GTの単位元に写す写像ではない。
［計算可能性］あらゆるψ1∈G1，ψ2∈G2についてe(ψ1, ψ2)を効率的に計算するアルゴリズムが存在する。
【００２７】
双線形写像eの具体例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数である（例えば、参考文献１「Alfred. J. Menezes，ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS， ISBN0-7923-9368-6，pp. 61-81」等参照）。また、楕円曲線の種類に応じ、Tateペアリングなどのペアリング演算を行うための関数と所定の関数phiを組み合わせた変更ペアリング関数e(ψ1,phi(ψ2))（ψ1∈G1，ψ2∈G2）を双線形写像eとして用いてもよい（例えば、参考文献２「RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems」等参照）。また、ペアリング演算をコンピュータ上で行うためのアルゴリズムとしては、周知のMiller のアルゴリズムなどが存在し、ペアリング演算を効率的に行うための楕円曲線や巡回群G1, G2, GTの構成方法はよく知られている。
【００２８】
属性情報：属性情報とは何らかの属性を表す値を意味する。属性情報j:{0,1}Φの集合をATTと表す。本形態の例では、属性情報jが1以上J以下の整数であり(Jは正整数)、ATT={1,...,J}であるものとする。ただし、これは本発明を限定するものではない。
【００２９】
Ω：Ωはプロトコル使用に対応した固有の識別子であるプロトコルＩＤを表す。
【００３０】
k-out-of-c しきい値秘密分散法：k-out-of-c しきい値秘密分散法は、任意の相違なるk個の分散情報SH(φ1),...,SH(φk)(1≦k≦c)が与えられれば秘密情報SKを復元できるが、任意のk-1個の分散情報SH(φ1),...,SH(φk-1)が与えられても秘密情報SKの情報はまったく得られない方式である（例えば、参考文献３「Adi Shamir, "How to share a secret", Communications of the ACM, Volume 22, No. 11, pp.612-613 (November 1979)」等参照）。以下にその一例を示す。
【００３１】
(1) q(η)=SK（ηは定数）を満たす不定元αについてのk-1次の多項式q(α)=ξ0+ξ1・α+ξ2・α2+...+ξK-1・αk-1をランダムに選ぶ。すなわち、q(η)=SKとし、ξ1,..., ξK-1をランダムに選ぶ。なお、定数ηの例はη=0である。そして、分散情報をSH(ρ)=q(index(ρ))（ρ∈{1,...,c}）とする。なお、index(ρ)は各ρに対応する互いに異なるインデックスであり、その例はindex(ρ)=ρである。
【００３２】
(2) 任意の相違なるk個の分散情報q(φ1),...,q(φk)（S={φ1,...,φk}⊂{index(1),...,index(c)}）が得られた場合、例えば、ラグランジェ(Lagrange)の補間公式を用い、以下のような復元処理によって秘密情報SKを復元できる。
【００３３】
SK=q(η)=Δ(φ1, q(η))・q(φ1)+...+Δ(φk, q(η))・q(φk) …(3)
ただし、Δ(ι, q(η))(ι∈S)は、以下に表すラグランジュ係数である。
【００３４】
【数１】
は先頭からι番目の被演算子〔分母の要素(φι-φι)、分子の要素(η-φι)〕が存在しないことを意味する。すなわち、式(4)の分母は、
(φι-φ1)・...・(φι-φι-1)・(φι-φι+1)・...・(φι-φk)
であり、式(4)の分子は
(η-φ1)・...・(η-φι-1)・(η-φι+1)・...・(η-φk)
である。
【００３５】
H:Hは{0,1}*を{0,1}kに移すハッシュ関数H:{0,1}* →{0,1}κを表す。
H':H'は{0,1}*をZpに移すハッシュ関数H:{0,1}* →Zpを表す。
【００３６】
＜原理＞
次に、本形態の原理を説明する。本形態では、第１鍵交換装置と第２鍵交換装置との間でセッション鍵を生成する。第１,２鍵交換装置には、それぞれ、属性情報についての論理式を表す木構造データγA,γBが対応付けられている。第１鍵交換装置は、属性情報の集合ATTの部分集合である属性集合δA⊂ATTを設定して第２鍵交換装置に対して出力し、第２鍵交換装置は、属性情報jの集合ATTの部分集合である属性集合δB⊂ATTを設定して第１鍵交換装置に対して出力する。ここで、属性集合δAが木構造データγBに対応する論理式を真にし、属性集合δBが木構造データγAに対応する論理式を真にする場合に、第１鍵交換装置と第２鍵交換装置との間で同一のセッション鍵が生成される。まず、木構造データの基本構成を説明する。
【００３７】
［木構造データγA］
第１鍵交換装置に対応する木構造データγAは、根付き木構造のデータであり、UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む。ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、親ノード情報N(uAP)にはc(uAP)(c(uAP)≧1)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応する。親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、葉ノード情報N(uAL)に対応するuALの集合がL(γA)である。親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応する。ノード情報N(uA)のそれぞれには情報q(uA, η(uA))が対応する。ルートノード情報N(uAR)に対応する情報q(uAR, 0)はマスタ秘密鍵λである。また、親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uAP)に対応する子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))である。葉ノード情報N(uAL)にはそれぞれ１つの属性情報att(uAL)∈ATTと秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1とが対応し、秘密値D(uAL)(uAL∈L(γA))の集合が第１鍵交換装置の長期秘密鍵DA={D(uAL)}uAL∈L(γA)である。なお、t(j)(j∈ATT)はマスタ秘密鍵である。なお、添字のuAはuAを表す。
【００３８】
なお、例えば、しきい値秘密分散法として参考文献３に記載された方法が用いられる場合には、子ノード情報N(uAC)のそれぞれには識別子index(uAC)が対応し、葉ノード情報N(uAL)にはしきい値k(uAL)=1が対応し、ノード情報N(uA)のそれぞれには不定元αについての次数d(uA)=k(uA)-1の多項式q(uA, α)が対応する。ここで、η(uA)はノード情報N(uA)に対応する定数である。また、情報q(uA, η(uA))が多項式q(uA, α)に定数η(uA)を代入して得られる値であり、子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))が当該子ノード情報N(uAC)に対応する親ノード情報N(uAP)に対応する多項式q(uAP, α)に当該子ノード情報N(uAC)に対応する識別子index(uAC)を代入して得られるq(uAP, index(uAC))である。
【００３９】
［木構造データγB］
第２鍵交換装置に対応する木構造データγBも木構造データγAと同様に構成される。すなわち、木構造データγBは、根付き木構造のデータであり、UB(UB≧2)個のノード情報N(uB)(uB∈{1,...,UB})を含む。ノード情報N(uB)の一部が親ノード情報N(uBP)(uBP∈{1,...,UB})であり、親ノード情報N(uBP)にはc(uBP)(c(uBP)≧1)個の子ノード情報N(uBC)(uBC∈{1,...,UB})が対応する。親ノード情報N(uBP)の何れか１つがルートノード情報N(uBR)(uBR∈{1,...,UB})であり、子ノード情報N(uBC)の少なくとも一部が葉ノード情報N(uBL)(uBL∈{1,...,UB})であり、葉ノード情報N(uBL)に対応するuBLの集合がL(γB)である。親ノード情報N(uBP)のそれぞれには1≦k(uBP)≦c(uBP)を満たすしきい値k(uBP) が対応する。ノード情報N(uB)のそれぞれには情報q(uB, η(uB))が対応する。ルートノード情報N(uBR)に対応する情報q(uBR, η(uBR))はマスタ秘密鍵λである。また、親ノード情報N(uBP)に対応する情報q(uBP, η(uBP))をk(uBP)-out-of-c(uBP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uBP)に対応する子ノード情報N(uBC)に対応する情報q(uBC, η(uBC))である。葉ノード情報N(uBL)にはそれぞれ１つの属性情報att(uBL)∈ATTと秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1とが対応し、秘密値D(uBL)(uBL∈L(γB))の集合が第２鍵交換装置の長期秘密鍵DB={D(uBL)}uBL∈L(γB)である。なお、添字のuBはuBを表す。
【００４０】
なお、例えば、しきい値秘密分散法として参考文献３に記載された方法が用いられる場合には、子ノード情報N(uBC)のそれぞれには識別子index(uBC)が対応し、葉ノード情報N(uBL)にはしきい値k(uBL)=1が対応し、ノード情報N(uB)のそれぞれには不定元αについての次数d(uB)=k(uB)-1の多項式q(uB, α)が対応する。ここで、η(uB)はノード情報N(uB)に対応する定数である。また、情報q(uB, η(uB))が多項式q(uB, α)に定数η(uB)を代入して得られる値であり、子ノード情報N(uBC)に対応する情報q(uBC, η(uBC))が当該子ノード情報N(uBC)に対応する親ノード情報N(uBP)に対応する多項式q(uBP, α)に当該子ノード情報N(uBC)に対応する識別子index(uBC)を代入して得られるq(uBP, index(uBC))である。
【００４１】
［鍵交換］
木構造データγAに対応する第１鍵交換装置と木構造データγBに対応する第２鍵交換装置とは、以下の処理によってセッション鍵の生成を行う。
【００４２】
第１鍵交換装置は、短期秘密鍵sAを任意に生成し、属性情報の集合ATTの部分集合である属性集合δA⊂ATTと長期秘密鍵DAと短期秘密鍵sAとを用い、長期秘密鍵DAと短期秘密鍵sAとを含む値の像χに対する元T(wA)χ∈G2 (wA∈δA)の集合であるTA={T(wA)χ}wA∈δAを含む第１短期公開鍵を生成し、属性集合δAと第１短期公開鍵とを第２鍵交換装置に対して出力する。なお、T(j)=g2t(j)∈G2はマスタ公開鍵である。また、添字のwA,δAは、それぞれwA,δAを表す。
【００４３】
第２鍵交換装置は、短期秘密鍵sBを任意に生成し、属性情報の集合ATTの部分集合である属性集合δB⊂ATTと長期秘密鍵DBと短期秘密鍵sBとを用い、長期秘密鍵DBと短期秘密鍵sBとを含む値の像υに対する元T(wB)υ∈G2 (wB∈δB)の集合であるTB={T(wB)υ}wB∈δBを含む第２短期公開鍵を生成し、属性集合δBと第２短期公開鍵とを第１鍵交換装置に対して出力する。なお、添字のwB,δBは、それぞれwB,δBを表す。
【００４４】
第１鍵交換装置は、属性集合δBと第２短期公開鍵との入力を受け付け、属性集合δBに属する属性情報att(uAL)∈δBに対応する葉ノード情報N(uAL)に対応する秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1と第２短期公開鍵が含む元T(att(uAL))υ∈G2とに対し、双線形写像eを作用させ、葉ノード情報N(uAL)に対して復元値e(D(uAL), T(att(uAL))υ)=gTυ・q(uAL, η(uAL))∈GTを生成する。また、第１鍵交換装置は、自らに対応する子ノード情報N(uAC)のうち復元値gTυ・q(uAC, η(uAC))∈GTが生成されたものの合計数が自らに対応するしきい値k(uAP)以上となる親ノード情報N(uAP)に対し、当該しきい値k(uAP)以上の復元値gTυ・q(uAC, η(uAC))∈GTをk(uAP)-out-of-c(uAP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTυ・q(uAP, η(uAP))∈GTを生成する。ここで、ルートノード情報N(uAR)に対する復元値gTυ・q(uAR, η(uAR))=gTυ・λ∈GTが生成された場合、第２鍵交換装置は、Λχ=gTχ・λ∈GTとgTυ・λ∈GTとを含む値の像を第１セッション鍵として出力する。なお、Λ=gTλ∈GTはマスタ公開鍵を表す。
【００４５】
第２鍵交換装置は、属性集合δAと第１短期公開鍵との入力を受け付け、属性集合δAに属する属性情報att(uBL)∈δAに対応する葉ノード情報N(uBL)に対応する秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1と第１短期公開鍵が含む元T(att(uBL))χ∈G2とに対し、双線形写像eを作用させ、葉ノード情報N(uBL)に対して復元値e(D(uBL), T(att(uBL))χ)=gTχ・q(uBL, η(uBL))∈GTを生成する。また、第２鍵交換装置は、自らに対応する子ノード情報N(uBC)のうち復元値gTχ・q(uBC, η(uBC))∈GTが生成されたものの合計数が自らに対応するしきい値k(uBP)以上となる親ノード情報N(uBP)に対し、当該しきい値k(uBP)以上の復元値gTχ・q(uBC, η(uBC))∈GTをk(uBP)-out-of-c(uBP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTχ・q(uBP, η(uBP))∈GTを生成する。ここで、ルートノード情報N(uBR)に対する復元値gTχ・q(uBR, η(uBR))=gTχ・λ∈GTが生成された場合、第２鍵交換装置は、gTχ・λ∈GTとΛυ=gTυ・λ∈GTとを含む値の像を第２セッション鍵として出力する。
【００４６】
［特徴］
本形態の木構造データγAは各葉ノード情報N(uAL)に対応する属性情報att(uAL)⊂δBについての論理式を表し、第１鍵交換装置は、与えられた属性集合δBが木構造データγAに表される論理式を真にする場合に第１セッション鍵を生成する。言い換えると、与えられた属性集合δBに葉ノード情報N(uAL)に対応する属性情報att(uAL)が含まれた場合（「uALが満たされる」と呼ぶ）、当該属性情報att(uAL)⊂δBに対応する葉ノード情報N(uAL)に対応する情報q(uAL, η(uAL))に対応する復元値gTυ・q(uAL, η(uAL))が復元される。また、子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))に対応する情報が、それらの親ノード情報N(uAP)に対応するしきい値k(uAP)以上得られた場合（「uAPが満たされる」と呼ぶ）、親ノード情報N(uAP)に対応する復元値gTυ・q(uAP, η(uAP))が得られる。そして、ルートノード情報N(uAR)の子ノード情報N(uAC)に対応する復元値gTυ・q(uAC, η(uAC))が、ルートノード情報N(uAR)に対応するしきい値k(uAR)以上得られ（「木構造データγAが満たされる」と呼ぶ）、ルートノード情報N(uAR)に対応する復元値gTυ・q(uAR, η(uAR))=gTυ・λが得られた場合、得られたgTυ・λ=σ2とマスタ公開鍵Λから生成されるΛχ=gTχ・λ=σ1とに対応する第１セッション鍵が生成される。
【００４７】
同様に、本形態の木構造データγBは各葉ノード情報N(uBL)に対応する属性情報att(uBL)⊂δBについての論理式を表し、第２鍵交換装置は、与えられた属性集合δAが木構造データγBに表される論理式を真にする場合に第２セッション鍵を生成する。言い換えると、与えられた属性集合δAに葉ノード情報N(uBL)に対応する属性情報att(uBL)が含まれた場合（「uBLが満たされる」と呼ぶ）、当該属性情報att(uBL)⊂δAに対応する葉ノード情報N(uBL)に対応する復元値gTχ・q(uBL, η(uBL))が復元される。また、子ノード情報N(uBC)に対応する情報q(uBC, η(uBC))に対応する復元値gTχ・q(uBC, η(uBC))が、それらの親ノード情報N(uBP)に対応するしきい値k(uBP)以上得られた場合（「uBPが満たされる」と呼ぶ）、親ノード情報N(uBP)に対応する復元値gTχ・q(uBP, η(uBP))が得られる。そして、ルートノード情報N(uBR)の子ノード情報N(uBC)に対応する復元値gTχ・q(uBC, η(uBC))が、ルートノード情報N(uBR)に対応するしきい値k(uBR)以上得られ（「γBが満たされる」と呼ぶ）、ルートノード情報N(uBR)に対応する復元値gTχ・q(uBR, η(uBR))=gTχ・λが得られた場合、得られたgTχ・λ=σ1∈GTとマスタ公開鍵Λから生成されるΛυ=gTυ・λ=σ2∈GTとに対応する第２セッション鍵が生成される。
【００４８】
ここで、第１鍵交換装置が生成するΛχ=gTχ・λ=σ1は第２鍵交換装置が生成するgTχ・λ=σ1と等しく、第１鍵交換装置が生成するgTυ・λ=σ2は第２鍵交換装置が生成するΛυ=gTυ・λ=σ2と等しい。よって、第１、２鍵交換装置は同一のセッション鍵を共有できる。すなわち、本形態では、属性集合δBに対してγAが満たされ、属性集合δAに対してγBが満たされた場合に、第１、２鍵交換装置で同一のセッション鍵を共有できる。このことを「属性集合が木構造データを満たす」という命題を表す述語
P:{0,1}Φ×{0,1}Φ→{0,1} …(5)
を用いて表現すると、「P(δB, γA)=1かつP(δA, γB)=1の場合に第１、２鍵交換装置が同一のセッション鍵を共有できる」となる。なお、P(δ, γ)=1とは「属性集合δが木構造データγを満たす」という命題を表す述語が真であることを表し、P(δ, γ)=0とは「属性集合δが木構造データγを満たす」という命題を表す述語が偽であることを表す。
【００４９】
また、第１鍵交換装置がさらに元X=g1χ∈G1を生成し、第１短期公開鍵がさらに元X=g1χ∈G1を含み、第２鍵交換装置がさらに元Y=g1υ∈G1を生成し、第２短期公開鍵がさらに元Y=g1υ∈G1を含み、P(δB, γA)=1の場合に第１鍵交換装置がσ1=Λχ=gTχ・λ∈GTとσ2=gTυ・λ∈GTとσ3=Yχ∈G1とを含む値の像を第１セッション鍵として出力し、P(δA, γB)=1の場合に第２鍵生成装置がσ1=gTχ・λ∈GTとσ2=Λυ=gTυ・λ∈GTとσ3=Xυ∈G1とを含む値の像を第２セッション鍵として出力してもよい。この場合（「限定形態」と呼ぶ）、短期秘密鍵が第三者に漏洩したことを考慮したeCKと呼ばれるモデルでの安全性が確保される。
【００５０】
例えば、従来のSYL方式では、短期秘密鍵が攻撃者に漏洩した場合、攻撃者は次のような攻撃を行うことで正規のユーザBに成り済ますことができる。
【００５１】
(1) 攻撃者は、ユーザAの短期秘密鍵χAを得る。
(2) 攻撃者は、ユーザAから(IDA,IDB,XA)を受信したら、IDBからQB=H1(IDB)を計算し、χB=QB(-1)とし、(IDA,IDB,XA,XB)をユーザAに送る。このとき、ユーザAが計算するσ1はσ1=e(DA・ΛχA,QB・QB(-1))=e(DA・ΛχA,QB)0=1∈GTとなるので、攻撃者は他の値を知らなくてもσ1の値を知ることができる。また、攻撃者は短期秘密鍵χAを用いてσ2=XBχAも計算することができる。よって、攻撃者はセッション鍵Kを計算し、ユーザBに成り済ますことができる。
【００５２】
一方、上記の限定形態の場合、短期秘密鍵が攻撃者に漏洩しても、攻撃者はセッション鍵の情報を入手することはできない。なぜなら、υやχは短期秘密鍵と長期秘密鍵とを用いて計算されるため、短期秘密鍵のみが攻撃者に漏洩しても、攻撃者はυやχを知ることができず、σ3=Xυやσ3=Yχを計算することができないからである。
【００５３】
〔実施形態〕
次に、本発明の実施形態を説明する。なお、以下では、しきい値秘密分散法として参考文献３に記載された方法が用いられ、ノード情報N(uA)に対応する定数η(uA)が0であり、ノード情報N(uB)に対応する定数η(uB)が0である場合を例にとって説明する。ただし、これは本発明を限定するものではない。
【００５４】
＜構成＞
図１に例示するように、実施形態の鍵交換システム１は、鍵交換装置１１０、１２０と鍵生成装置１３０と鍵抽出装置１４０とを有し、ネットワークや可搬型記録媒体（以下「ネットワーク等」）を経由して装置間の情報伝達を行う。鍵交換装置１１０、１２０、鍵生成装置１３０、及び鍵抽出装置１４０は、それぞれ、CPU(central processing unit)やRAM(random-access memory)などを備えた公知又は専用のコンピュータと特別なプログラムとによって構成され、特別なプログラムが読み込まれたCPUが当該特別なプログラムに従った処理を実行することで各機能が実現される。なお、特別なプログラムは、単一のプログラム列によって構成されてもよいし、他のプログラムやライブラリを読み出して目的の機能を達成するプログラムであってもよい。また、処理部の少なくとも一部が集積回路によって構成されていてもよい。
【００５５】
［鍵交換装置１１０］
図２に例示するように、実施形態の鍵交換装置１１０は、入力部１１１ａと、出力部１１１ｂと、記憶部１１２と、制御部１１３と、判定部１１４と、短期秘密鍵生成部１１５ａと、ハッシュ演算部１１５ｂと、短期公開鍵生成部１１５ｃ,１１５ｄと、葉ノード復元値生成部１１６と、親ノード復元値生成部１１７と、演算部１１８と、鍵生成部１１９とを有する。入力部１１１ａや出力部１１１ｂは、例えば、通信装置、入出力インタフェース、入出力ポートなどである。記憶部１１２は、例えば、RAM、レジスタ、キャッシュメモリ、ハードディスクなどから構成される記憶領域である。制御部１１３、判定部１１４、短期秘密鍵生成部１１５ａ、ハッシュ演算部１１５ｂ、短期公開鍵生成部１１５ｃ,１１５ｄ、葉ノード復元値生成部１１６、親ノード復元値生成部１１７、演算部１１８、及び鍵生成部１１９は、特別なプログラムが読み込まれたCPUや集積回路である。なお、鍵交換装置１１０は、記憶部１１２の制御のもとで各処理を実行する。
【００５６】
［鍵交換装置１２０］
図３に例示するように、実施形態の鍵交換装置１２０は、入力部１２１ａと、出力部１２１ｂと、記憶部１２２と、制御部１２３と、判定部１２４と、短期秘密鍵生成部１２５ａと、ハッシュ演算部１２５ｂと、短期公開鍵生成部１２５ｃ,１２５ｄと、葉ノード復元値生成部１２６と、親ノード復元値生成部１２７と、演算部１２８と、鍵生成部１２９とを有する。入力部１２１ａや出力部１２１ｂは、例えば、通信装置、入出力インタフェース、入出力ポートなどである。記憶部１２２は、例えば、RAM、レジスタ、キャッシュメモリ、ハードディスクなどから構成される記憶領域である。制御部１２３、判定部１２４、短期秘密鍵生成部１２５ａ、ハッシュ演算部１２５ｂ、短期公開鍵生成部１２５ｃ,１２５ｄ、葉ノード復元値生成部１２６、親ノード復元値生成部１２７、演算部１２８、及び鍵生成部１２９は、特別なプログラムが読み込まれたCPUや集積回路である。なお、鍵交換装置１２０は、記憶部１２２の制御のもとで各処理を実行する。
【００５７】
［鍵抽出装置１４０］
図４に例示するように、鍵抽出装置１４０は、入力部１４１と、出力部１４２と、記憶部１４３と、制御部１４４と、設定部１４５、１４６と、秘密値生成部１４７とを有する。設定部１４５は、情報設定部１４５ａと多項式設定部１４５ｂとを含む。また、設定部１４６は、情報設定部１４６ａと多項式設定部１４６ｂとを含む。入力部１４１や出力部１４２は、例えば、通信装置、入出力インタフェース、入出力ポートなどである。記憶部１４３は、例えば、RAM、レジスタ、キャッシュメモリ、ハードディスクなどから構成される記憶領域である。制御部１４４、設定部１４５、１４６、及び秘密値生成部１４７は、特別なプログラムが読み込まれたCPUや集積回路である。なお、鍵抽出装置１４０は、記憶部１４３の制御のもとで各処理を実行する。
【００５８】
＜公開パラメータ設定処理＞
事前処理として、プロトコルＩＤであるΩ、セキュリティパラメータκ、巡回群G1, G2, GT、生成元g1, g2, gT、ハッシュ関数H, H'、Zp、「属性集合が木構造データを満たす」という命題を表す述語P、属性情報の集合ATT={1,...,J}などの公開パラメータが鍵交換装置１１０、１２０、鍵生成装置１３０、鍵抽出装置１４０に共有され、各装置で利用可能な状態とされる。
【００５９】
＜鍵生成処理＞
鍵生成装置１３０（図１）は、ランダムにマスタ秘密鍵λ∈UZpを選択し、さらに、ランダムにt(j)∈UZpをすべての属性情報j∈ATTについて選択し、すべての属性情報j∈ATTについてのt(j)の集合をマスタ秘密鍵{t(j)}j∈ATTとする。また、鍵生成装置１３０は、マスタ公開鍵Λ=gTλ∈GTを生成し、さらに、すべての属性情報j∈ATTについてT(j)=g2t(j)∈G2を生成し、すべての属性情報j∈ATTについてのT(j)の集合をマスタ公開鍵{T(j)}j∈ATTとする。マスタ秘密鍵λ, {t(j)}j∈ATTは、鍵抽出装置１４０（図４）に安全に送られ、入力部１４１に入力され、記憶部１４３に格納される。一方、マスタ公開鍵Λ, {T(j)}j∈ATTは、鍵交換装置１１０,１２０（図２,３）に送られ、それぞれ、入力部１１１ａ,１２１ａに入力されて記憶部１１２,１２２に格納される。
【００６０】
＜鍵抽出処理＞
事前処理として、選択された属性情報att(uAL)∈ATTについての論理式を表す木構造データγAが鍵交換装置１１０の記憶部１１２に格納され、選択された属性情報att(uBL)∈ATTについての論理式を表す木構造データγBが鍵交換装置１２０の記憶部１２２に格納される。これらの論理式は事前に定められる。また、木構造データγA,γBにはそれぞれに対応する論理式を特定する情報が付される。
【００６１】
本形態の木構造データγAは、UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含み、ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、子ノード情報N(uAC)のそれぞれには識別子index(uAC)が対応する。親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、葉ノード情報N(uAL)に対応するuALの集合がL(γA)である。親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、葉ノード情報N(uAL)にはしきい値k(uAL)=1が対応する。また、葉ノード情報N(uAL)にはそれぞれ１つの属性情報att(uAL)∈ATTが対応する。本形態の木構造データγAは、このようにノード情報N(uA)としきい値k(uA)と識別子index(uAC)と属性情報att(uAL)とが対応付けられたデータである。
【００６２】
本形態の木構造データγBは、UB(UB≧2)個のノード情報N(uB)(uB∈{1,...,UB})を含み、ノード情報N(uB)の一部が親ノード情報N(uBP)(uBP∈{1,...,UB})であり、親ノード情報N(uBP)にはc(uBP)個の子ノード情報N(uBC)(uBC∈{1,...,UB})が対応し、子ノード情報N(uBC)のそれぞれには識別子index(uBC)が対応する。親ノード情報N(uBP)の何れか１つがルートノード情報N(uBR)(uBR∈{1,...,UB})であり、子ノード情報N(uBC)の少なくとも一部が葉ノード情報N(uBL)(uBL∈{1,...,UB})であり、葉ノード情報N(uBL)に対応するuBLの集合がL(γB)である。親ノード情報N(uBP)のそれぞれには1≦k(uBP)≦c(uBP)を満たすしきい値k(uBP)が対応し、葉ノード情報N(uBL)にはしきい値k(uBL)=1が対応する。また、葉ノード情報N(uBL)にはそれぞれ１つの属性情報att(uBL)∈ATTが対応する。本形態の木構造データγBは、このようにノード情報N(uB)としきい値k(uB)と識別子index(uBC)と属性情報att(uBL)とが対応付けられたデータである。
【００６３】
［木構造データの具体例］
以下に、木構造データγAを例にとって木構造データの具体例を示す。ここでは木構造データγAの具体例を示すが、木構造データγBも同様に構成できる。
【００６４】
《論理式(1∧2)∨4の例》
図８Ａ及び図８Ｂに例示する木構造データγAは、属性情報1, 2, 4についての論理式(1∧2)∨4に対応する。この例の木構造データγAは、5個のノード情報N(uA)(uA∈{1,...,5})を含む。ノード情報N(uA)の一部が親ノード情報N(1),N(2)であり、親ノード情報N(1)にはc(1)=2個の子ノード情報N(2), N(5)が対応し、親ノード情報N(2)にはc(2)=2個の子ノード情報N(3), N(4)が対応する。子ノード情報N(2), N(5)のそれぞれには識別子index(2)=1, index(5)=2が対応し、子ノード情報N(3), N(4)のそれぞれには識別子index(3)=1, index(4)=2が対応する。親ノード情報N(1), N(2)の１つがルートノード情報N(1)であり、子ノード情報N(2), N(3), N(4), N(5)の一部が葉ノード情報N(3), N(4), N(5)である。葉ノード情報N(3), N(4), N(5)に対応するuAL=3, 4, 5の集合がL(γA)={3, 4, 5}である。親ノード情報N(1)には1≦k(1)≦2を満たすしきい値k(1)=1が対応し、親ノード情報N(2)には1≦k(2)≦2を満たすしきい値k(2)=2が対応し、葉ノード情報N(3), N(4), N(5)にはしきい値k(3)=k(4)=k(5)=1が対応する。葉ノード情報N(3), N(4), N(5)にはそれぞれ属性情報att(3)=1, att(4)=2, att(5)=4∈ATTが対応する。
【００６５】
《論理式(1∧2)∨(2∧3)∨(1∧3)∨4−の例》
図１０Ａ及び図１０Ｂに例示する木構造データγAは、属性情報1, 2, 3, 4についての論理式(1∧2)∨(2∧3)∨(1∧3)∨4−を表している。ここで、属性情報4−は属性情報4の否定を表し、属性情報4−は属性情報5として表現される。このように特定の属性情報の否定を表す属性情報をATTに追加することにより、否定を含む論理式を表現する木構造データも設定可能となる。
【００６６】
図１０及び図１０Ｂの木構造データγAは、6個のノード情報N(uA)(uA∈{1,...,6})を含む。ノード情報N(uA)の一部が親ノード情報N(1),N(2)であり、親ノード情報N(1)にはc(1)=2個の子ノード情報N(2),N(6)が対応し、親ノード情報N(2)にはc(2)=3個の子ノード情報N(3), N(4), N(5)が対応する。子ノード情報N(2), N(6)のそれぞれには識別子index(2)=1, index(6)=2が対応し、子ノード情報N(3), N(4), N(5)のそれぞれには識別子index(3)=1, index(4)=2, index(5)=3が対応する。親ノード情報N(1),N(2)の１つがルートノード情報N(1)であり、子ノード情報N(2), N(3), N(4), N(5), N(6)の一部が葉ノード情報N(3), N(4), N(5), N(6)である。葉ノード情報N(3), N(4), N(5), N(6)に対応するuAL=3, 4, 5, 6の集合がL(γA)={3, 4, 5, 6}である。親ノード情報N(1)には1≦k(1)≦2を満たすしきい値k(1)=1が対応し、親ノード情報N(2)には1≦k(2)≦2を満たすしきい値k(2)=2が対応し、葉ノード情報N(3), N(4), N(5), N(6)にはしきい値k(3)=k(4)=k(5)=k(6)=1が対応する（［木構造データの具体例］の説明終わり）。
【００６７】
次に、木構造データγAに対応する鍵抽出処理を説明する。なお、以下では構造データγAに対応する鍵抽出処理のみを説明するが、木構造データγBに対応する鍵抽出処理も同様である。本形態の鍵抽出処理では、まず、マスタ秘密鍵λをルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))として設定する。その後、親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報を当該親ノード情報N(uAP)に対応する子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))として設定する処理を再帰的に繰り返す。その後、葉ノード情報N(uAL)に対応する属性情報att(uAL)∈ATTに対し、秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1を生成し、秘密値D(uAL)(uAL∈L(γA))の集合である長期秘密鍵DA={D(uAL)}uAL∈L(γA)を出力する。これらの具体的な処理手順に限定はない。以下に図５Ａ及び図５Ｂを用い、木構造データγAに対応する鍵抽出処理の一例を示す。
【００６８】
まず、鍵交換装置１１０（図２）の記憶部１１２から読み出された木構造データγAが出力部１１１ｂから出力される。木構造データγAは、ネットワーク等を経由して鍵抽出装置１４０（図４）の入力部１４１に入力され、記憶部１４３に格納される（ステップＳ１４１１）。
【００６９】
次に、設定部１４５がマスタ秘密鍵λを木構造データγAのルートノード情報N(uAR)に対応する情報q(uAR, 0)として設定する。本形態では、まず、設定部１４５の情報設定部１４５ａが、記憶部１４３から読み出したマスタ秘密鍵λをルートノード情報N(uAR)に対する情報q(uAR, 0)として設定し、当該情報q(uAR, 0)を記憶部１４３に格納する（ステップＳ１４１２）。次に、設定部１４５の多項式設定部１４５ｂが、記憶部１４３から情報q(uAR, 0)=λとルートノード情報N(uAR)に対応するしきい値k(uAR)とを読み込み、定数項（α=0であるときの関数値）がq(uAR, 0)=λである不定元αについての次数d(uAR)=k(uAR)-1の多項式q(uAR, α)をルートノード情報N(uAR)に対して設定する。例えば、多項式設定部１４５ｂは、d(uAR)個の互いに異なる任意点(α1, β１)（α1, β１∈UZp，α1≠0）をそれぞれランダムに選択し、それらを通る定数項q(uAR, 0)=λの多項式q(uAR, α)を特定する。これによってルートノード情報N(uAR)に対応する多項式q(uAR, α)が一意に定まる。定められた多項式q(uAR, α)は記憶部１４３に格納される（ステップＳ１４１３）。
【００７０】
次に、設定部１４６が、親ノード情報N(uAP)に対応する情報q(uAP, 0)をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報を、当該親ノード情報N(uAP)に対応する子ノード情報N(uAC)に対応する情報q(uAC, 0)として設定する。本形態の場合、設定部１４６がuAPをuAR（uAP←uAR）とおき、その場合の親ノード情報N(uAP)を処理対象として図５Ｂのループ処理を実行する（ステップＳ１４１４）。
【００７１】
［図５Ｂのループ処理］
図５Ｂのループ処理では、処理対象の親ノード情報N(uAP)に対応するすべての子ノード情報N(uAC)に対して以下のステップＳ１４２１とＳ１４２２の処理を実行する。
【００７２】
ステップＳ１４２１では、設定部１４６の情報設定部１４６ａが、記憶部１４３から多項式q(uAP, α)と、処理対象の親ノード情報N(uAP)の各子ノード情報N(uAC)に対応する識別子index(uAC)とを読み出す。情報設定部１４６ａは、処理対象の親ノード情報N(uAP)に対応する多項式q(uAP, α)に、当該親ノード情報N(uAP)に対応する子ノード情報N(uAC)に対応する識別子index(uAC)を代入して得られるq(uAP, index(uAC))を、当該子ノード情報N(uAC)に対応する情報q(uAC, 0)として設定する。各子ノード情報N(uAC)に対応する情報q(uAC, 0)は、記憶部１４３に格納される（ステップＳ１４２１）。
【００７３】
ステップＳ１４２２では、設定部１４６の多項式設定部１４６ｂが、記憶部１４３からステップＳ１４２１で設定された情報q(uAC, 0)を読み出し、当該情報q(uAC, 0)が設定された子ノード情報N(uAC)に対し、定数項（α=0であるときの関数値）をq(uAC, 0)=q(uAP, index(uAC))とする不定元αについての次数d(uAC)=k(uAC)-1の多項式q(uAC, α)を設定する。例えば、多項式設定部１４６ｂは、d(uAC)個の互いに異なる任意点(α2, β2)（α2, β2∈UZp，α2≠0）をそれぞれランダムに選択し、それらを通る定数項q(uAC, 0)の多項式q(uAC, α)を特定する。定められた多項式q(uAC, α)は記憶部１４３に格納される（ステップＳ１４２２）（［図５Ｂのループ処理］の説明終わり）。
【００７４】
ステップＳ１４１４の処理が終了すると、次に、設定部１４６は、多項式q(uAC, α)が設定された子ノード情報N(uAC)に対応するさらなる子ノード情報が存在するか否かを判定する（ステップＳ１４１５）。ここで、さらなる子ノード情報が存在すると判定された場合、設定部１４６は、さらなる子ノード情報が存在すると判定されたすべての子ノード情報N(uAC)について、それぞれ、uAPをuAC（uAP←uAC）とおき、その場合のすべての親ノード情報N(uAP)を処理対象として図５Ｂのループ処理をそれぞれ実行し、その後、ステップＳ１４１５に戻る（ステップＳ１４１６）。
【００７５】
一方、ステップＳ１４１５で、さらなる子ノード情報が存在しないと判定された場合、秘密値生成部１４７が、記憶部１４３からすべての葉ノード情報N(uAL)に対応する属性情報att(uAL)∈ATT及び情報q(uAL, 0)をそれぞれ読み出し、各秘密値
D(uAL)=g1q(uAL, 0)/t(att(uAL))∈G1 …(6)
を生成する。生成された秘密値D(uAL)(uAL∈L(γA))の集合である長期秘密鍵DA={D(uAL)}uAL∈L(γA)が記憶部１４３に格納される（ステップＳ１４１７）。長期秘密鍵DA={D(uAL)}uAL∈L(γA)は出力部１４２に送られ、そこから鍵交換装置１１０（図２）に安全に送られ、鍵交換装置１１０の入力部１１１ａに入力され、記憶部１１２に格納される（ステップＳ１４１８）。
【００７６】
これにより、木構造データγAのノード情報N(uA)のそれぞれに不定元αについての次数d(uA)=k(uA)-1の多項式q(uA, α)が対応し、その結果、ノード情報N(uA)のそれぞれには情報（定数項）q(uA, 0)が対応する。ルートノード情報N(uAR)に対応する情報q(uAR, 0)はマスタ秘密鍵λであり、親ノード情報N(uAP)に対応する情報q(uAP, 0)をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uAP)に対応する子ノード情報N(uAC)に対応する情報q(uAC, 0)であり、葉ノード情報N(uAL)にはそれぞれ秘密値D(uAL)=g1q(uAL, 0)/t(att(uAL))∈G1が対応し、秘密値D(uAL)(uAL∈L(γA))の集合が長期秘密鍵DA={D(uAL)}uAL∈L(γA)となる。
【００７７】
例えば、前述した図８Ａ及び図８Ｂに例示する木構造データγA（論理式(1∧2)∨4の例）の場合、図９Ａ及び図９Ｂに例示するように、木構造データγAのノード情報N(uA)(uA=1,...,5)のそれぞれに不定元αについての次数d(uA)=k(uA)-1の多項式q(uA, α)が対応し、その結果、ノード情報N(uA)のそれぞれには情報q(uA, 0)が対応する。ルートノード情報N(1)に対応する情報q(1, 0)はマスタ秘密鍵λである。親ノード情報（ルートノード情報）N(1)に対応する情報q(1, 0)をk(1)-out-of-c(1)（1-out-of-2）しきい値秘密分散して得られる分散情報である情報q(1,1), q(1,2)が、それぞれ子ノード情報N(2),N(5)に対応する情報q(2,0), q(5,0)である。また、親ノード情報N(2)に対応する情報q(2, 0)をk(2)-out-of-c(2)（2-out-of-2）しきい値秘密分散して得られる分散情報である情報q(2,1), q(2,2)が、それぞれ子ノード情報N(3), N(4)に対応する情報q(3,0), q(4,0)である。また、葉ノード情報N(3), N(4), N(5)にはそれぞれ秘密値D(3)=g1q(3, 0)/t(1), D(4)=g1q(4, 0)/t(2), D(5)=g1q(5, 0)/t(4) ∈G1が対応し、D(3), D(4), D(5)の集合が長期秘密鍵DAとなる。
【００７８】
また、例えば、前述した図１０Ａ及び図１０Ｂに例示する木構造データγA（論理式(1∧2)∨(2∧3)∨(1∧3)∨4−の例）の場合、図１１Ａ及び図１１Ｂに例示するように、木構造データγAのノード情報N(uA)(uA=1,...,6)のそれぞれに不定元αについての次数d(uA)=k(uA)-1の多項式q(uA, α)が対応し、その結果、ノード情報N(uA)のそれぞれには情報q(uA, 0)が対応する。ルートノード情報N(1)に対応する情報q(1, 0)はマスタ秘密鍵λである。親ノード情報（ルートノード情報）N(1)に対応する情報q(1, 0)をk(1)-out-of-c(1)（1-out-of-2）しきい値秘密分散して得られる分散情報である情報q(1,1), q(1,2)が、それぞれ子ノード情報N(2),N(6)に対応する情報q(2,0), q(6,0)である。また、親ノード情報N(2)に対応する情報q(2, 0)をk(2)-out-of-c(2)（2-out-of-3）しきい値秘密分散して得られる分散情報である情報q(2,1), q(2,2), q(2,3)が、それぞれ子ノード情報N(3), N(4) , N(5)に対応する情報q(3,0), q(4,0), q(5,0)である。また、葉ノード情報N(3), N(4), N(5) ,N(6)にはそれぞれ秘密値D(3)=g1q(3, 0)/t(1), D(4)=g1q(4, 0)/t(2), D(5)=g1q(5, 0)/t(3), D(6)=g1q(6, 0)/t(5) ∈G1が対応し、D(3), D(4), D(5), D(6)の集合が長期秘密鍵DAとなる。
【００７９】
＜鍵交換処理＞
次に、鍵交換装置１１０の処理を表す図６と鍵交換装置１２０の処理を表す図７とを用い、本形態の鍵交換処理を説明する。なお、本形態では、鍵交換装置１１０がイニシエータとして機能し、鍵交換装置１２０がレスポンダとして機能する例を示す。
【００８０】
まず、鍵交換装置１１０（図２）の入力部１１１ａに属性情報の集合ATTの部分集合である属性集合δA⊂ATTが入力される。属性集合δAは任意に選択されたものである。例えば、属性集合δAが鍵交換装置１２０の木構造データを満たすならば認証成功となって鍵交換装置１２０とセッション鍵を共有できることを期待して任意に選択された属性集合δAが入力部１１１ａに入力される。属性集合δAは記憶部１１２に格納される（図６／ステップＳ１１１１）。
【００８１】
次に、短期秘密鍵生成部１１５ａが短期秘密鍵sA∈UZpを任意に生成し、ハッシュ演算部１１５ｂに送る（ステップＳ１１１２）。ハッシュ演算部１１５ｂは、記憶部１１２から長期秘密鍵DAを読み出し、ハッシュ値（長期秘密鍵DAと短期秘密鍵sAとを含む値の像）
χ=H'(DA, sA)∈Zp …(7)
を生成して、ハッシュ値χを記憶部１１２に格納する（ステップＳ１１１３）。なお、H'(DA, sA)は、長期秘密鍵DAと短期秘密鍵sAとに対応するバイナリ系列のハッシュ値を表す。長期秘密鍵DAと短期秘密鍵sAとの組をバイナリ系列に写す関数に限定はないが、鍵生成装置１１０，１２０で同一の関数を用いる必要がある。長期秘密鍵DAと短期秘密鍵sAとに対応するバイナリ系列の例は、長期秘密鍵DAと短期秘密鍵sAとのビット結合である。
【００８２】
次に、短期公開鍵生成部１１５ｄが、記憶部１１２から読み出したハッシュ値χを用い、元
X=g1χ∈G1 …(8)
を生成して記憶部１１２に格納する（ステップＳ１１１４）。また、短期公開鍵生成部１１５ｃは、記憶部１１２に格納されたマスタ公開鍵{T(j)}j∈ATTから属性集合δAに対応するT(wA)(wA∈δA)の集合とハッシュ値χとを読み出す。短期公開鍵生成部１１５ｃは、ハッシュ値χに対する元
T(wA)χ∈G2(wA∈δA) …(9)
の集合である
TA={T(wA)χ}wA∈δA …(10)
を生成して記憶部１１２に格納する（ステップＳ１１１５）。本形態では、元Xと集合TAとが短期公開鍵となる。
【００８３】
記憶部１１２に格納された属性集合δAと短期公開鍵X, TAとは出力部１１１ｂに入力され、出力部１１１ｂは、属性集合δAと短期公開鍵X, TAとを鍵交換装置１２０に対して出力する（ステップＳ１１１６）。
【００８４】
属性集合δAと短期公開鍵X, TAとは、鍵交換装置１２０（図３）の入力部１２１ａに入力され、記憶部１２２に格納される（図７／ステップＳ１２１１）。すると、判定部１２４が、記憶部１２２に格納された属性集合δAと木構造データγBに対応する論理式を特定する情報とを読み出し、属性集合δAが木構造データγBを満たすか否かを判定する（ステップＳ１２１２）。ここで、属性集合δAが木構造データγBを満たさないと判定された場合、処理がエラー終了する。一方、属性集合δAが木構造データγBを満たすと判定された場合、判定部１２４が、記憶部１２２に格納されたマスタ公開鍵{T(j)}j∈ATTと短期公開鍵X, TA={T(wA)χ}wA∈δAと属性集合δAとを読み出し、属性集合δAに属するすべての属性情報wA∈δAについて、
e(X, T(wA))=e(g1,T(wA)χ) …(11)
が成り立つか否かを判定する（ステップＳ１２１３）。ここで、少なくとも一部の属性情報wA∈δAについて式(11)が成り立たないと判定された場合、処理がエラー終了する。一方、すべての属性情報wA∈δAについて式(11)が成り立つと判定された場合、入力部１２１ａが属性情報の集合ATTの部分集合である属性集合δB⊂ATTの入力を受け付ける。属性集合δAと同様、属性集合δBは任意に選択されたものである。入力された属性集合δBは記憶部１２２に格納される（ステップＳ１２１４）。
【００８５】
次に、短期秘密鍵生成部１２５ａが短期秘密鍵sB∈UZpを任意に生成し、ハッシュ演算部１２５ｂに送る（ステップＳ１２１５）。ハッシュ演算部１２５ｂは、記憶部１２２から長期秘密鍵DBを読み出し、ハッシュ値（長期秘密鍵DBと短期秘密鍵sBとを含む値の像）
υ=H'(DB, sB)∈Zp …(12)
を生成して、ハッシュ値υを記憶部１２２に格納する（ステップＳ１２１６）。なお、H'(DB, sB)は、長期秘密鍵DBと短期秘密鍵sBとに対応するバイナリ系列のハッシュ値を表す。長期秘密鍵DBと短期秘密鍵sBとの組をバイナリ系列に写す関数に限定はないが、鍵生成装置１１０，１２０で同一の関数を用いる必要がある。長期秘密鍵DBと短期秘密鍵sBとに対応するバイナリ系列の例は、長期秘密鍵DBと短期秘密鍵sBとのビット結合である。
【００８６】
次に、短期公開鍵生成部１２５ｄが、記憶部１２２から読み出したハッシュ値υを用い、元
Y=g1υ∈G1 …(13)
を生成して記憶部１２２に格納する（ステップＳ１２１７）。また、短期公開鍵生成部１２５ｃは、記憶部１２２に格納されたマスタ公開鍵{T(j)}j∈ATTから属性集合δBに対応するT(wB)(wB∈δB)の集合とハッシュ値υとを読み出す。短期公開鍵生成部１２５ｃは、ハッシュ値υに対する元
T(wB)υ∈G2 (wB∈δB) …(14)
の集合である
TB={T(wB)υ}wB∈δB …(15)
を生成して記憶部１２２に格納する（ステップＳ１２１８）。本形態では、元Yと集合TBとが短期公開鍵となる。
【００８７】
記憶部１２２に格納された属性集合δBと短期公開鍵Y, TBとは出力部１２１ｂに入力され、出力部１２１ｂは、属性集合δBと短期公開鍵Y, TBとを鍵交換装置１１０に対して出力する（ステップＳ１２１９）。
【００８８】
また、葉ノード復元値生成部１２６が、記憶部１２２に格納された属性集合δAと木構造データγBとを参照し、属性集合δAに属する属性情報att(uBL)∈δAに対応する木構造データγBの葉ノード情報N(uBL)に対応する秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1を記憶部１２２に格納された長期秘密鍵DBから抽出する。さらに、葉ノード復元値生成部１２６は、当該葉ノード情報N(uBL)に対応する属性情報att(uBL)∈ATTに対応する元T(att(uBL))χを短期公開鍵TAから抽出する。葉ノード復元値生成部１２６は、当該葉ノード情報N(uBL)ごとに、秘密値D(uBL)と元T(att(uBL))χとを作用させ、各葉ノード情報N(uBL)に対する各復元値
e(D(uBL), T(att(uBL))χ)=gTχ・q(uBL, 0)∈GT …(16)
を生成して記憶部１２２に格納する（ステップＳ１２２０）。
【００８９】
次に、判定部１２４は、記憶部１２２に格納された復元値と木構造データγBとを参照し、自らに対応する子ノード情報N(uBC)のうち復元値gTχ・q(uBC, 0)∈GTが生成されたものの合計数が自らに対応するしきい値k(uBP)以上となる親ノード情報N(uBP)が存在されたか否かを判定する。すなわち、判定部１２４は、親ノード情報N(uBP)に対応する子ノード情報N(uBC)のうち復元値gTχ・q(uBC, 0)∈GTが生成されたもののuBCの集合をS(uBP)'とした場合に、
|S(uBP)'|≧k(uBP) …(17)
を満たす親ノード情報N(uBP)が存在するか否かを判定する（ステップＳ１２２１）。ただし、|S(uBP)'|は集合S(uBP)'の要素数を表す。ここで、式(17)を満たす親ノード情報N(uBP)が存在しないと判定された場合、処理がエラー終了する。一方、式(17)を満たす親ノード情報N(uBP)が存在すると判定された場合、親ノード復元値生成部１２７は、式(17)を満たす親ノード情報N(uBP)に対応するしきい値k(uBP)以上の子ノード情報N(uBC)の復元値gTχ・q(uBC, 0)∈GTを、k(uBP)-out-of-c(uBP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値
gTχ・q(uBP, 0)∈GT …(18)
を生成して記憶部１２２に格納する。例えば、親ノード復元値生成部１２７は、集合S(uBP)'の部分集合であるk(uBP)個のuBCからなる集合S(uBP)〜⊂S(uBP)'を選択し、集合S(uBP)〜の要素であるk(uBP)個のuBC∈S(uBP)〜にそれぞれ対応する復元値gTχ・q(uBC, 0)を用い、ラグランジェの補間公式（式(3),(4)）に従って、
【００９０】
【数２】
を計算する。ただし、q(uBC,0)=q(uBP,index(uBC))を満たす。この処理は、式(17)を満たすすべての親ノード情報N(uBP)に対して実行される。これにより、式(17)を満たすすべての親ノード情報N(uBP)に対応する復元値gTχ・q(uBP, 0)がそれぞれ得られる（ステップＳ１２２２）。
【００９１】
次に、判定部１２４は、ステップＳ１２２２においてルートノード情報N(uAR)に対応する復元値gTχ・q(uAR, 0)が得られたか否かを判定する（ステップＳ１２２３）。ここで、ルートノード情報N(uAR)に対応する復元値gTχ・q(uAR, 0)が得られていないと判定された場合、ステップＳ１２２１の処理に戻る。一方、ルートノード情報N(uAR)に対応する復元値gTχ・q(uAR, 0)が得られたと判定された場合、演算部１２８が記憶部１２２からgTχ・q(uAR, 0)=gTχ・λ∈GTとマスタ公開鍵Λと短期公開鍵Xとハッシュ値υとを読み込み、
σ1=gTχ・λ∈GT …(20)
σ2=Λυ=gTυ・λ∈GT …(21)
σ3=Xυ∈G1 …(22)
を生成する（ステップＳ１２２４）。生成されたσ1, σ2, σ3は鍵生成部１２９に送られる。鍵生成部１２９は記憶部１２２から短期公開鍵X, Y, TA, TBと属性集合δAとδBとを読み込み、さらに述語P及びプロトコルＩＤであるΩを用い、セッション鍵
K=H(σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB)) …(23)
を生成して出力する。なお、H(σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB))は、σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB)に対応するバイナリ系列のハッシュ値を表す。これらの情報の組をバイナリ系列に写す関数に限定はないが、鍵生成装置１１０，１２０で同一の関数を用いる必要がある（ステップＳ１２２５）。
【００９２】
一方、ステップＳ１２１９で鍵交換装置１２０から出力された属性集合δBと短期公開鍵Y, TBとは、鍵交換装置１１０（図２）の入力部１１１ａに入力され、記憶部１１２に格納される（図６／ステップＳ１１１７）。すると、判定部１１４が、記憶部１１２に格納された属性集合δBと木構造データγAに対応する論理式を特定する情報とを読み出し、属性集合δBが木構造データγAを満たすか否かを判定する（ステップＳ１１１８）。ここで、属性集合δBが木構造データγAを満たさないと判定された場合、処理がエラー終了する。一方、属性集合δBが木構造データγAを満たすと判定された場合、判定部１１４が、記憶部１１２に格納されたマスタ公開鍵{T(j)}j∈ATTと短期公開鍵Y, TB={T(wB)υ}wB∈δBと属性集合δBとを読み出し、属性集合δBに属するすべての属性情報wB∈δBについて、
e(Y, T(wB))=e(g1,T(wB)υ) …(24)
が成り立つか否かを判定する（ステップＳ１１１９）。ここで、少なくとも一部の属性情報wB∈δBについて式(24)が成り立たないと判定された場合、処理がエラー終了する。一方、すべての属性情報wB∈δBについて式(24)が成り立つと判定された場合、葉ノード復元値生成部１１６が、記憶部１１２に格納された属性集合δBと木構造データγAとを参照し、属性集合δBに属する属性情報att(uAL)∈δBに対応する木構造データγAの葉ノード情報N(uAL)に対応する秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1を記憶部１１２に格納された長期秘密鍵DAから抽出する。さらに、葉ノード復元値生成部１１６は、当該葉ノード情報N(uAL)に対応する属性情報att(uAL)∈ATTに対応する元T(att(uAL))υを短期公開鍵TBから抽出する。葉ノード復元値生成部１１６は、当該葉ノード情報N(uAL)ごとに、秘密値D(uAL)と元T(att(uAL))υとを作用させ、各葉ノード情報N(uAL)に対する各復元値
e(D(uAL), T(att(uAL))υ)=gTυ・q(uAL, 0)∈GT …(25）
を生成して記憶部１１２に格納する（ステップＳ１１２０）。
【００９３】
次に、判定部１１４は、記憶部１１２に格納された復元値と木構造データγAとを参照し、自らに対応する子ノード情報N(uAC)のうち復元値gTυ・q(uAC, 0)∈GTが生成されたものの合計数が自らに対応するしきい値k(uAP)以上となる親ノード情報N(uAP)が存在されたか否かを判定する。すなわち、判定部１１４は、親ノード情報N(uAP)に対応する子ノード情報N(uAC)のうち復元値gTυ・q(uAC, 0)∈GTが生成されたもののuACの集合をS(uAP)'とした場合に、
|S(uAP)'|≧k(uAP) …(26）
を満たす親ノード情報N(uAP)が存在するか否かを判定する（ステップＳ１１２１）。ただし、|S(uAP)'|は集合S(uAP)'の要素数を表す。ここで、式(26）を満たす親ノード情報N(uAP)が存在しないと判定された場合、処理がエラー終了する。一方、式(26）を満たす親ノード情報N(uAP)が存在すると判定された場合、親ノード復元値生成部１１７は、式(26）を満たす親ノード情報N(uAP)に対応するしきい値k(uAP)以上の子ノード情報N(uAC)の復元値gTυ・q(uAC, 0)∈GTをk(uAP)-out-of-c(uAP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値
gTυ・q(uAP, 0)∈GT …(27）
を生成して記憶部１１２に格納する。例えば、親ノード復元値生成部１１７は、集合S(uAP)'の部分集合であるk(uAP)個のuACからなる集合S(uAP)〜⊂S(uAP)'を選択し、集合S(uAP)〜の要素であるk(uAP)個のuAC∈S(uAP)〜にそれぞれ対応する復元値gTυ・q(uAC, 0)を用い、ラグランジェの補間公式（式(3),(4)）に従って、
【００９４】
【数３】
を計算する。ただし、q(uAC,0)=q(uAP,index(uAC))を満たす。この処理は、式(26）を満たすすべての親ノード情報N(uAP)に対して実行される。これにより、式(26）を満たすすべての親ノード情報N(uAP)に対応する復元値gTυ・q(uAP, 0)がそれぞれ得られる（ステップＳ１１２２）。
【００９５】
次に、判定部１１４は、ステップＳ１１２２においてルートノード情報N(uBR)に対応する復元値gTυ・q(uBR, 0)が得られたか否かを判定する（ステップＳ１１２３）。ここで、ルートノード情報N(uBR)に対応する復元値gTυ・q(uBR, 0)が得られていないと判定された場合、ステップＳ１１２１の処理に戻る。一方、ルートノード情報N(uBR)に対応する復元値gTυ・q(uBR, 0)が得られたと判定された場合、演算部１１８が記憶部１１２からgTυ・q(uBR, 0)=gTυ・λ∈GTとマスタ公開鍵Λと短期公開鍵Xとハッシュ値υとを読み込み、
σ1=Λχ=gTχ・λ∈GT …(29）
σ2=gTυ・λ∈GT …(30)
σ3=Yχ∈G1 …(31)
を生成する（ステップＳ１１２４）。生成されたσ1, σ2, σ3は鍵生成部１１９に送られる。鍵生成部１１９は記憶部１１２から短期公開鍵X, Y, TA, TBと属性集合δAとδBとを読み込み、さらに述語P及びプロトコルＩＤであるΩを用い、セッション鍵
K=H(σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB)) …(32)
を生成して出力する。なお、H(σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB))は、σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB)に対応するバイナリ系列のハッシュ値を表す。これらの情報の組をバイナリ系列に写す関数に限定はないが、鍵生成装置１１０，１２０で同一の関数を用いる必要がある（ステップＳ１１２５）。
【００９６】
ここで、鍵交換装置１１０，１２０でそれぞれ生成されたσ1, σ2, σ3は、
σ1=gTχ・λ∈GT …(33）
σ2=gTυ・λ∈GT …(34)
σ3=g1χ・υ∈G1 …(35)
となる。よって、P(δB, γA)=1かつP(δA, γB)=1の場合に鍵交換装置１１０，１２０は同一のセッション鍵Kを共有できる。また、前述のように本形態ではeCKモデルでの安全性が確保される。
【００９７】
〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上記の実施形態では、σ1, σ2, σ3に対応するセッション鍵Kが生成される例を示したが、鍵交換装置１１０，１２０がσ3を生成することなく、σ1, σ2に対応するセッション鍵Kを生成する形態でもよい。この場合、元X, Yの生成は不要となり、鍵交換装置１１０が生成する短期公開鍵は集合TAであり、鍵交換装置１２０が生成する短期公開鍵は集合TBとなる。
【００９８】
また、上記の実施形態では
K=H(σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB))
をセッション鍵としたが、σ1, σ2, σ3, Ω, P, (δA, X, TA), (δB, Y, TB)と所定の付加情報とに依存するバイナリ系列のハッシュ値をセッション鍵としてもよい。また、σ1, σ2と所定の付加情報とに依存するバイナリ系列のハッシュ値をセッション鍵としてもよく、σ1, σ2, σ3と所定の付加情報とに依存するバイナリ系列のハッシュ値をセッション鍵としてもよい。付加情報の例は巡回群G1, G2, GTを特定する情報、生成元g1, g2, gTを特定する情報、位数pを特定する情報などである。ただし、鍵交換装置１１０，１２０でセッション鍵を生成する際の付加情報は互いに同一である必要がある。
【００９９】
また、上記の実施形態で用いたハッシュ関数Hの代わりに、ハッシュ関数Hと定義域と地域とが同一のその他の関数（共通鍵暗号関数など）を用いてもよい。同様に、ハッシュ関数H'の代わりに、ハッシュ関数H'と定義域と地域とが同一のその他の関数を用いてもよい。
【０１００】
また、実施形態では、ステップＳ１１１８，Ｓ１１１９の判定でyesとなった場合にのみステップＳ１１２０以降の処理が実行され、ステップＳ１２１２，Ｓ１２１３の判定でyesとなった場合にのみステップＳ１２１４以降の処理が実行されることとした。しかし、ステップＳ１１１８，Ｓ１１１９やステップＳ１２１２，Ｓ１２１３の判定を行うことなく、ステップＳ１１２０以降の処理やステップＳ１２１４以降の処理が実行されてもよい。
【０１０１】
また、木構造データγAやγBが鍵交換装置１１０，１２０内に格納されるのではなく、木構造データγAやγBが含むしきい値などの情報が必要となるたびに、それらの情報が鍵交換装置１１０，１２０に与えられる構成であってもよい。さらに、しきい値秘密分散法に限定はなく、公知のどのような方法を用いてもよい。また、環Zpでの演算の代わりに整数での演算が行われてもよい。
【０１０２】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０３】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１０４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１０８】
１ 鍵交換システム
１１０，１２０ 鍵交換装置
【特許請求の範囲】
【請求項１】
第１鍵交換装置と第２鍵交換装置とを有し、
巡回群G1, G2, GTの生成元がそれぞれg1, g2, gTであり、直積空間G1×G2の元を巡回群GTに写す双線形写像がe: G1×G2→GTであり、属性情報jの集合がATTであり、マスタ秘密鍵がλ及びt(j)(j∈ATT)であり、マスタ公開鍵がΛ=gTλ∈GT及びT(j)=g2t(j)∈G2であり、
UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む木構造データγAが前記第１鍵交換装置に対応し、前記ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、前記親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、前記親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、前記子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、前記葉ノード情報N(uAL)に対応するuALの集合がL(γA)であり、前記親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、前記ノード情報N(uA)のそれぞれには情報q(uA, η(uA))が対応し、前記ルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))が前記マスタ秘密鍵λであり、前記親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uAP)に対応する前記子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))であり、前記葉ノード情報N(uAL)にはそれぞれ属性情報att(uAL)∈ATTと秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1とが対応し、前記秘密値D(uAL)(uAL∈L(γA))の集合が前記第１鍵交換装置の長期秘密鍵DA={D(uAL)}uAL∈L(γA)であり、
UB(UB≧2)個のノード情報N(uB)(uB∈{1,...,UB})を含む木構造データγBが前記第２鍵交換装置に対応し、前記ノード情報N(uB)の一部が親ノード情報N(uBP)(uBP∈{1,...,UB})であり、前記親ノード情報N(uBP)にはc(uBP)個の子ノード情報N(uBC)(uBC∈{1,...,UB})が対応し、前記親ノード情報N(uBP)の何れか１つがルートノード情報N(uBR)(uBR∈{1,...,UB})であり、前記子ノード情報N(uBC)の少なくとも一部が葉ノード情報N(uBL)(uBL∈{1,...,UB})であり、前記葉ノード情報N(uBL)に対応するuBLの集合がL(γB)であり、前記親ノード情報N(uBP)のそれぞれには1≦k(uBP)≦c(uBP)を満たすしきい値k(uBP) が対応し、前記ノード情報N(uB)のそれぞれには情報q(uB, η(uB))が対応し、前記ルートノード情報N(uBR)に対応する情報q(uBR, η(uBR))が前記マスタ秘密鍵λであり、前記親ノード情報N(uBP)に対応する情報q(uBP, η(uBP))をk(uBP)-out-of-c(uBP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uBP)に対応する前記子ノード情報N(uBC)に対応する情報q(uBC, η(uBC))であり、前記葉ノード情報N(uBL)にはそれぞれ属性情報att(uBL)∈ATTと秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1とが対応し、前記秘密値D(uBL)(uBL∈L(γB))の集合が前記第２鍵交換装置の長期秘密鍵DB={D(uBL)}uBL∈L(γB)であり、
短期秘密鍵sAを任意に生成する第１短期秘密鍵生成部と、
前記属性情報の集合ATTの部分集合である属性集合δA⊂ATTと前記長期秘密鍵DAと前記短期秘密鍵sAとを用い、前記長期秘密鍵DAと前記短期秘密鍵sAとを含む値の像χに対する元T(wA)χ∈G2(wA∈δA)の集合であるTA={T(wA)χ}wA∈δAを含む第１短期公開鍵を生成する第１短期公開鍵生成部と、
前記属性集合δAと前記第１短期公開鍵とを前記第２鍵交換装置に対して出力する第１出力部と、を有し、
前記第２鍵交換装置は、
短期秘密鍵sBを任意に生成する第２短期秘密鍵生成部と、
前記属性情報の集合ATTの部分集合である属性集合δB⊂ATTと前記長期秘密鍵DBと前記短期秘密鍵sBとを用い、前記長期秘密鍵DBと前記短期秘密鍵sBとを含む値の像υに対する元T(wB)υ∈G2(wB∈δB)の集合であるTB={T(wB)υ}wB∈δBを含む第２短期公開鍵を生成する第２短期公開鍵生成部と、
前記属性集合δBと前記第２短期公開鍵とを前記第１鍵交換装置に対して出力する第２出力部と、を有し、
前記第１鍵交換装置は、
前記属性集合δBと前記第２短期公開鍵との入力を受け付ける第１入力部と、
前記属性集合δBに属する前記属性情報att(uAL)∈δBに対応する前記葉ノード情報N(uAL)に対応する秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1と前記第２短期公開鍵が含む元T(att(uAL))υ∈G2とに対し、前記双線形写像eを作用させ、前記葉ノード情報N(uAL)に対して復元値e(D(uAL), T(att(uAL))υ)=gTυ・q(uAL, η(uAL))∈GTを生成する第１葉ノード復元値生成部と、
自らに対応する前記子ノード情報N(uAC)のうち復元値gTυ・q(uAC, η(uAC))∈GTが生成されたものの合計数が自らに対応する前記しきい値k(uAP)以上となる前記親ノード情報N(uAP)に対し、当該しきい値k(uAP)以上の前記復元値gTυ・q(uAC, η(uAC))∈GTをk(uAP)-out-of-c(uAP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTυ・q(uAP, η(uAP))∈GTを生成する第１親ノード復元値生成部と、
前記第１親ノード復元値生成部が、前記ルートノード情報N(uAR)に対する復元値gTυ・q(uAR, η(uAR))=gTυ・λ∈GTを生成した場合、Λχ=gTχ・λ∈GTとgTυ・λ∈GTとを含む値の像を第１セッション鍵として出力する第１鍵生成部と、を有し、
前記第２鍵交換装置は、
前記属性集合δAと前記第１短期公開鍵との入力を受け付ける第２入力部と、
前記属性集合δAに属する前記属性情報att(uBL)∈δAに対応する前記葉ノード情報N(uBL)に対応する秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1と前記第１短期公開鍵が含む元T(att(uBL))χ∈G2とに対し、前記双線形写像eを作用させ、前記葉ノード情報N(uBL)に対して復元値e(D(uBL), T(att(uBL))χ)=gTχ・q(uBL, η(uBL))∈GTを生成する第２葉ノード復元値生成部と、
自らに対応する前記子ノード情報N(uBC)のうち復元値gTχ・q(uBC, η(uBC))∈GTが生成されたものの合計数が自らに対応する前記しきい値k(uBP)以上となる前記親ノード情報N(uBP)に対し、当該しきい値k(uBP)以上の前記復元値gTχ・q(uBC, η(uBC))∈GTをk(uBP)-out-of-c(uBP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTχ・q(uBP, η(uBP))∈GTを生成する第２親ノード復元値生成部と、
前記第２親ノード復元値生成部が、前記ルートノード情報N(uBR)に対する復元値gTχ・q(uBR, η(uBR))=gTχ・λ∈GTを生成した場合、gTχ・λ∈GTとΛυ=gTυ・λ∈GTとを含む値の像を第２セッション鍵として出力する第２鍵生成部と、を有する、
ことを特徴とする鍵交換システム。
【請求項２】
請求項１の鍵交換システムであって、
前記第１短期公開鍵生成部は、さらに元X=g1χ∈G1を生成し、前記第１短期公開鍵は、さらに前記元X=g1χ∈G1を含み、
前記第２短期公開鍵生成部は、さらに元Y=g1υ∈G1を生成し、前記第２短期公開鍵は、さらに前記元Y=g1υ∈G1を含み、
前記第１鍵生成部は、Λχ=gTχ・λ∈GTとgTυ・λ∈GTとYχ∈G1とを含む値の像を前記第１セッション鍵として出力し、
前記第２鍵生成部は、gTχ・λ∈GTとΛυ=gTυ・λ∈GTとXυ∈G1とを含む値の像を前記第２セッション鍵として出力する、
ことを特徴とする鍵交換システム。
【請求項３】
請求項１又は２の鍵交換システムであって、
前記子ノード情報N(uAC)のそれぞれには識別子index(uAC)が対応し、前記葉ノード情報N(uAL)にはしきい値k(uAL)=1が対応し、前記ノード情報N(uA)のそれぞれには不定元αについての次数d(uA)=k(uA)-1の多項式q(uA, α)が対応し、η(uA)が前記ノード情報N(uA)に対応する定数であり、前記情報q(uA, η(uA))が前記多項式q(uA, α)に定数η(uA)を代入して得られる値であり、前記子ノード情報N(uAC)に対応する前記情報q(uAC, η(uAC))が当該子ノード情報N(uAC)に対応する前記親ノード情報N(uAP)に対応する多項式q(uAP, α)に当該子ノード情報N(uAC)に対応する前記識別子index(uAC)を代入して得られるq(uAP, index(uAC))であり、
前記子ノード情報N(uBC)のそれぞれには識別子index(uBC)が対応し、前記葉ノード情報N(uBL)にはしきい値k(uBL)=1が対応し、前記ノード情報N(uB)のそれぞれには不定元αについての次数d(uB)=k(uB)-1の多項式q(uB, α)が対応し、η(uB)が前記ノード情報N(uB)に対応する定数であり、前記情報q(uB, η(uB))が前記多項式q(uB, α)に定数η(uB)を代入して得られる値であり、前記子ノード情報N(uBC)に対応する前記情報q(uBC, η(uBC))が当該子ノード情報N(uBC)に対応する前記親ノード情報N(uBP)に対応する多項式q(uBP, α)に当該子ノード情報N(uBC)に対応する前記識別子index(uBC)を代入して得られるq(uBP, index(uBC))である、
ことを特徴とする鍵交換システム。
【請求項４】
巡回群G1, G2, GTの生成元がそれぞれg1, g2, gTであり、直積空間G1×G2の元を巡回群GTに写す双線形写像がe: G1×G2→GTであり、属性情報jの集合がATTであり、マスタ秘密鍵がλ及びt(j)(j∈ATT)であり、マスタ公開鍵がΛ=gTλ∈GT及びT(j)=g2t(j)∈G2であり、UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む木構造データがγAであり、前記ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、前記親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、前記親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、前記子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、前記葉ノード情報N(uAL)に対応するuALの集合がL(γA)であり、前記親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、前記ノード情報N(uA)のそれぞれには情報q(uA, η(uA))が対応し、前記ルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))が前記マスタ秘密鍵λであり、前記親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uAP)に対応する前記子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))であり、前記葉ノード情報N(uAL)にはそれぞれ属性情報att(uAL)∈ATTと秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1とが対応し、前記秘密値D(uAL)(uAL∈L(γA))の集合が長期秘密鍵DA={D(uAL)}uAL∈L(γA)であり、
短期秘密鍵sAを任意に生成する短期秘密鍵生成部と、
前記属性情報の集合ATTの部分集合である属性集合δA⊂ATTと前記長期秘密鍵DAと前記短期秘密鍵sAとを用い、前記長期秘密鍵DAと前記短期秘密鍵sAとを含む値の像χに対する元T(wA)χ∈G2(wA∈δA)の集合であるTA={T(wA)χ}wA∈δAを含む第１短期公開鍵を生成する短期公開鍵生成部と、
前記属性集合δAと前記第１短期公開鍵とを他の鍵交換装置に対して出力する出力部と、
属性集合δBと第２短期公開鍵との入力を受け付ける入力部と、
前記属性集合δBに属する前記属性情報att(uAL)∈δBに対応する前記葉ノード情報N(uAL)に対応する秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1と前記第２短期公開鍵が含む元T(att(uAL))υ∈G2とに対し、前記双線形写像eを作用させ、前記葉ノード情報N(uAL)に対して復元値e(D(uAL), T(att(uAL))υ)=gTυ・q(uAL, η(uAL))∈GTを生成する葉ノード復元値生成部と、
自らに対応する前記子ノード情報N(uAC)のうち復元値gTυ・q(uAC, η(uAC))∈GTが生成されたものの合計数が自らに対応する前記しきい値k(uAP)以上となる前記親ノード情報N(uAP)に対し、当該しきい値k(uAP)以上の前記復元値gTυ・q(uAC, η(uAC))∈GTをk(uAP)-out-of-c(uAP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTυ・q(uAP, η(uAP))∈GTを生成する親ノード復元値生成部と、
前記親ノード復元値生成部が、前記ルートノード情報N(uAR)に対する復元値gTυ・q(uAR, η(uAR))=gTυ・λ∈GTを生成した場合、Λχ=gTχ・λ∈GTとgTυ・λ∈GTとを含む値の像をセッション鍵として出力する鍵生成部と、
を有する鍵交換装置。
【請求項５】
巡回群G1, G2, GTの生成元がそれぞれg1, g2, gTであり、直積空間G1×G2の元を巡回群GTに写す双線形写像がe: G1×G2→GTであり、属性情報jの集合がATTであり、マスタ秘密鍵がλ及びt(j)(j∈ATT)であり、T(j)=g2t(j)∈G2であり、UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む木構造データがγAであり、前記ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、前記親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、前記親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、前記子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、前記葉ノード情報N(uAL)に対応するuALの集合がL(γA)であり、前記親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、
前記マスタ秘密鍵λを前記ルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))として設定する第１設定部と、
前記親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報を当該親ノード情報N(uAP)に対応する前記子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))として設定する第２設定部と、
前記葉ノード情報N(uAL)に対応する属性情報att(uAL)∈ATTに対し、秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1を生成する秘密値生成部と、
前記秘密値D(uAL)(uAL∈L(γA))の集合である長期秘密鍵DA={D(uAL)}uAL∈L(γA)を出力する出力部と、
を有する鍵抽出装置。
【請求項６】
請求項５の鍵抽出装置であって、
前記子ノード情報N(uAC)のそれぞれには識別子index(uAC)が対応し、前記葉ノード情報N(uAL)にはしきい値k(uAL)=1が対応し、前記ノード情報N(uA)のそれぞれには不定元αについての次数d(uA)=k(uA)-1の多項式q(uA, α)が対応し、η(uA)が前記ノード情報N(uA)に対応する定数であり、前記情報q(uA, η(uA))が前記多項式q(uA, α)に定数η(uA)を代入して得られる値であり、
前記第１設定部は、
前記マスタ秘密鍵λを前記ルートノード情報N(uAR)に対する情報q(uAR, η(uAR))として設定する第１設定部と、
α=η(uAR)であるときの関数値q(uAR, η(uAR))が前記マスタ秘密鍵λである不定元αについての次数d(uAR)=k(uAR)-1の多項式q(uAR, α)を前記ルートノード情報N(uAR)に対して設定する第１多項式設定部と、を含み、
前記第２設定部は、
前記親ノード情報N(uAP)に対応する多項式q(uAP, α)に、当該親ノード情報N(uAP)に対応する前記子ノード情報N(uAC)に対応する前記識別子index(uAC)を代入して得られるq(uAP, index(uAC))を、当該子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))として設定する第２設定部と、
α=η(uAC)であるときの関数値q(uAC, η(uAC))がq(uAP, index(uAC))である不定元αについての次数d(uAC)=k(uAC)-1の多項式q(uAC, α)を前記子ノード情報N(uAC)に対して設定する第２多項式設定部と、を含む、
ことを特徴とする鍵抽出装置。
【請求項７】
巡回群G1, G2, GTの生成元がそれぞれg1, g2, gTであり、直積空間G1×G2の元を巡回群GTに写す双線形写像がe: G1×G2→GTであり、属性情報jの集合がATTであり、マスタ秘密鍵がλ及びt(j)(j∈ATT)であり、マスタ公開鍵がΛ=gTλ∈GT及びT(j)=g2t(j)∈G2であり、UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む木構造データがγAであり、前記ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、前記親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、前記親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、前記子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、前記葉ノード情報N(uAL)に対応するuALの集合がL(γA)であり、前記親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、前記ノード情報N(uA)のそれぞれには情報q(uA, η(uA))が対応し、前記ルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))が前記マスタ秘密鍵λであり、前記親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uAP)に対応する前記子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))であり、前記葉ノード情報N(uAL)にはそれぞれ属性情報att(uAL)∈ATTと秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1とが対応し、前記秘密値D(uAL)(uAL∈L(γA))の集合が長期秘密鍵DA={D(uAL)}uAL∈L(γA)であり、
短期秘密鍵生成部において、短期秘密鍵sAを任意に生成するステップと、
短期公開鍵生成部において、前記属性情報の集合ATTの部分集合である属性集合δA⊂ATTと前記長期秘密鍵DAと前記短期秘密鍵sAとを用い、前記長期秘密鍵DAと前記短期秘密鍵sAとを含む値の像χに対する元T(wA)χ∈G2(wA∈δA)の集合であるTA={T(wA)χ}wA∈δAを含む第１短期公開鍵を生成するステップと、
出力部において、前記属性集合δAと前記第１短期公開鍵とを他の鍵交換装置に対して出力するステップと、
入力部において、属性集合δBと第２短期公開鍵との入力を受け付けるステップと、
葉ノード復元値生成部において、前記属性集合δBに属する前記属性情報att(uAL)∈δBに対応する前記葉ノード情報N(uAL)に対応する秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1と前記第２短期公開鍵が含む元T(att(uAL))υ∈G2とに対し、前記双線形写像eを作用させ、前記葉ノード情報N(uAL)に対して復元値e(D(uAL), T(att(uAL))υ)=gTυ・q(uAL, η(uAL))∈GTを生成するステップと、
親ノード復元値生成部において、自らに対応する前記子ノード情報N(uAC)のうち復元値gTυ・q(uAC, η(uAC))∈GTが生成されたものの合計数が自らに対応する前記しきい値k(uAP)以上となる前記親ノード情報N(uAP)に対し、当該しきい値k(uAP)以上の前記復元値gTυ・q(uAC, η(uAC))∈GTをk(uAP)-out-of-c(uAP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTυ・q(uAP, η(uAP))∈GTを生成するステップと、
前記親ノード復元値生成部で前記ルートノード情報N(uAR)に対する復元値gTυ・q(uAR, η(uAR))=gTυ・λ∈GTが生成された場合、鍵生成部において、Λχ=gTχ・λ∈GTとgTυ・λ∈GTとを含む値の像をセッション鍵として出力するステップと、
を有する鍵交換方法。
【請求項８】
巡回群G1, G2, GTの生成元がそれぞれg1, g2, gTであり、直積空間G1×G2の元を巡回群GTに写す双線形写像がe: G1×G2→GTであり、属性情報jの集合がATTであり、マスタ秘密鍵がλ及びt(j)(j∈ATT)であり、T(j)=g2t(j)∈G2であり、UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む木構造データがγAであり、前記ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、前記親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、前記親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、前記子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、前記葉ノード情報N(uAL)に対応するuALの集合がL(γA)であり、前記親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、
第１設定部において、前記マスタ秘密鍵λを前記ルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))として設定するステップと、
第２設定部において、前記親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報を当該親ノード情報N(uAP)に対応する前記子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))として設定するステップと、
秘密値生成部において、前記葉ノード情報N(uAL)に対応する属性情報att(uAL)∈ATTに対し、秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1を生成するステップと、
出力部において、前記秘密値D(uAL)(uAL∈L(γA))の集合である長期秘密鍵DA={D(uAL)}uAL∈L(γA)を出力するステップと、
を有する鍵抽出方法。
【請求項９】
請求項７の鍵交換方法の処理をコンピュータに実行させるためのプログラム。
【請求項１０】
請求項８の鍵抽出方法の処理をコンピュータに実行させるためのプログラム。
【請求項１】
第１鍵交換装置と第２鍵交換装置とを有し、
巡回群G1, G2, GTの生成元がそれぞれg1, g2, gTであり、直積空間G1×G2の元を巡回群GTに写す双線形写像がe: G1×G2→GTであり、属性情報jの集合がATTであり、マスタ秘密鍵がλ及びt(j)(j∈ATT)であり、マスタ公開鍵がΛ=gTλ∈GT及びT(j)=g2t(j)∈G2であり、
UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む木構造データγAが前記第１鍵交換装置に対応し、前記ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、前記親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、前記親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、前記子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、前記葉ノード情報N(uAL)に対応するuALの集合がL(γA)であり、前記親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、前記ノード情報N(uA)のそれぞれには情報q(uA, η(uA))が対応し、前記ルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))が前記マスタ秘密鍵λであり、前記親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uAP)に対応する前記子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))であり、前記葉ノード情報N(uAL)にはそれぞれ属性情報att(uAL)∈ATTと秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1とが対応し、前記秘密値D(uAL)(uAL∈L(γA))の集合が前記第１鍵交換装置の長期秘密鍵DA={D(uAL)}uAL∈L(γA)であり、
UB(UB≧2)個のノード情報N(uB)(uB∈{1,...,UB})を含む木構造データγBが前記第２鍵交換装置に対応し、前記ノード情報N(uB)の一部が親ノード情報N(uBP)(uBP∈{1,...,UB})であり、前記親ノード情報N(uBP)にはc(uBP)個の子ノード情報N(uBC)(uBC∈{1,...,UB})が対応し、前記親ノード情報N(uBP)の何れか１つがルートノード情報N(uBR)(uBR∈{1,...,UB})であり、前記子ノード情報N(uBC)の少なくとも一部が葉ノード情報N(uBL)(uBL∈{1,...,UB})であり、前記葉ノード情報N(uBL)に対応するuBLの集合がL(γB)であり、前記親ノード情報N(uBP)のそれぞれには1≦k(uBP)≦c(uBP)を満たすしきい値k(uBP) が対応し、前記ノード情報N(uB)のそれぞれには情報q(uB, η(uB))が対応し、前記ルートノード情報N(uBR)に対応する情報q(uBR, η(uBR))が前記マスタ秘密鍵λであり、前記親ノード情報N(uBP)に対応する情報q(uBP, η(uBP))をk(uBP)-out-of-c(uBP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uBP)に対応する前記子ノード情報N(uBC)に対応する情報q(uBC, η(uBC))であり、前記葉ノード情報N(uBL)にはそれぞれ属性情報att(uBL)∈ATTと秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1とが対応し、前記秘密値D(uBL)(uBL∈L(γB))の集合が前記第２鍵交換装置の長期秘密鍵DB={D(uBL)}uBL∈L(γB)であり、
短期秘密鍵sAを任意に生成する第１短期秘密鍵生成部と、
前記属性情報の集合ATTの部分集合である属性集合δA⊂ATTと前記長期秘密鍵DAと前記短期秘密鍵sAとを用い、前記長期秘密鍵DAと前記短期秘密鍵sAとを含む値の像χに対する元T(wA)χ∈G2(wA∈δA)の集合であるTA={T(wA)χ}wA∈δAを含む第１短期公開鍵を生成する第１短期公開鍵生成部と、
前記属性集合δAと前記第１短期公開鍵とを前記第２鍵交換装置に対して出力する第１出力部と、を有し、
前記第２鍵交換装置は、
短期秘密鍵sBを任意に生成する第２短期秘密鍵生成部と、
前記属性情報の集合ATTの部分集合である属性集合δB⊂ATTと前記長期秘密鍵DBと前記短期秘密鍵sBとを用い、前記長期秘密鍵DBと前記短期秘密鍵sBとを含む値の像υに対する元T(wB)υ∈G2(wB∈δB)の集合であるTB={T(wB)υ}wB∈δBを含む第２短期公開鍵を生成する第２短期公開鍵生成部と、
前記属性集合δBと前記第２短期公開鍵とを前記第１鍵交換装置に対して出力する第２出力部と、を有し、
前記第１鍵交換装置は、
前記属性集合δBと前記第２短期公開鍵との入力を受け付ける第１入力部と、
前記属性集合δBに属する前記属性情報att(uAL)∈δBに対応する前記葉ノード情報N(uAL)に対応する秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1と前記第２短期公開鍵が含む元T(att(uAL))υ∈G2とに対し、前記双線形写像eを作用させ、前記葉ノード情報N(uAL)に対して復元値e(D(uAL), T(att(uAL))υ)=gTυ・q(uAL, η(uAL))∈GTを生成する第１葉ノード復元値生成部と、
自らに対応する前記子ノード情報N(uAC)のうち復元値gTυ・q(uAC, η(uAC))∈GTが生成されたものの合計数が自らに対応する前記しきい値k(uAP)以上となる前記親ノード情報N(uAP)に対し、当該しきい値k(uAP)以上の前記復元値gTυ・q(uAC, η(uAC))∈GTをk(uAP)-out-of-c(uAP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTυ・q(uAP, η(uAP))∈GTを生成する第１親ノード復元値生成部と、
前記第１親ノード復元値生成部が、前記ルートノード情報N(uAR)に対する復元値gTυ・q(uAR, η(uAR))=gTυ・λ∈GTを生成した場合、Λχ=gTχ・λ∈GTとgTυ・λ∈GTとを含む値の像を第１セッション鍵として出力する第１鍵生成部と、を有し、
前記第２鍵交換装置は、
前記属性集合δAと前記第１短期公開鍵との入力を受け付ける第２入力部と、
前記属性集合δAに属する前記属性情報att(uBL)∈δAに対応する前記葉ノード情報N(uBL)に対応する秘密値D(uBL)=g1q(uBL, η(uBL))/t(att(uBL))∈G1と前記第１短期公開鍵が含む元T(att(uBL))χ∈G2とに対し、前記双線形写像eを作用させ、前記葉ノード情報N(uBL)に対して復元値e(D(uBL), T(att(uBL))χ)=gTχ・q(uBL, η(uBL))∈GTを生成する第２葉ノード復元値生成部と、
自らに対応する前記子ノード情報N(uBC)のうち復元値gTχ・q(uBC, η(uBC))∈GTが生成されたものの合計数が自らに対応する前記しきい値k(uBP)以上となる前記親ノード情報N(uBP)に対し、当該しきい値k(uBP)以上の前記復元値gTχ・q(uBC, η(uBC))∈GTをk(uBP)-out-of-c(uBP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTχ・q(uBP, η(uBP))∈GTを生成する第２親ノード復元値生成部と、
前記第２親ノード復元値生成部が、前記ルートノード情報N(uBR)に対する復元値gTχ・q(uBR, η(uBR))=gTχ・λ∈GTを生成した場合、gTχ・λ∈GTとΛυ=gTυ・λ∈GTとを含む値の像を第２セッション鍵として出力する第２鍵生成部と、を有する、
ことを特徴とする鍵交換システム。
【請求項２】
請求項１の鍵交換システムであって、
前記第１短期公開鍵生成部は、さらに元X=g1χ∈G1を生成し、前記第１短期公開鍵は、さらに前記元X=g1χ∈G1を含み、
前記第２短期公開鍵生成部は、さらに元Y=g1υ∈G1を生成し、前記第２短期公開鍵は、さらに前記元Y=g1υ∈G1を含み、
前記第１鍵生成部は、Λχ=gTχ・λ∈GTとgTυ・λ∈GTとYχ∈G1とを含む値の像を前記第１セッション鍵として出力し、
前記第２鍵生成部は、gTχ・λ∈GTとΛυ=gTυ・λ∈GTとXυ∈G1とを含む値の像を前記第２セッション鍵として出力する、
ことを特徴とする鍵交換システム。
【請求項３】
請求項１又は２の鍵交換システムであって、
前記子ノード情報N(uAC)のそれぞれには識別子index(uAC)が対応し、前記葉ノード情報N(uAL)にはしきい値k(uAL)=1が対応し、前記ノード情報N(uA)のそれぞれには不定元αについての次数d(uA)=k(uA)-1の多項式q(uA, α)が対応し、η(uA)が前記ノード情報N(uA)に対応する定数であり、前記情報q(uA, η(uA))が前記多項式q(uA, α)に定数η(uA)を代入して得られる値であり、前記子ノード情報N(uAC)に対応する前記情報q(uAC, η(uAC))が当該子ノード情報N(uAC)に対応する前記親ノード情報N(uAP)に対応する多項式q(uAP, α)に当該子ノード情報N(uAC)に対応する前記識別子index(uAC)を代入して得られるq(uAP, index(uAC))であり、
前記子ノード情報N(uBC)のそれぞれには識別子index(uBC)が対応し、前記葉ノード情報N(uBL)にはしきい値k(uBL)=1が対応し、前記ノード情報N(uB)のそれぞれには不定元αについての次数d(uB)=k(uB)-1の多項式q(uB, α)が対応し、η(uB)が前記ノード情報N(uB)に対応する定数であり、前記情報q(uB, η(uB))が前記多項式q(uB, α)に定数η(uB)を代入して得られる値であり、前記子ノード情報N(uBC)に対応する前記情報q(uBC, η(uBC))が当該子ノード情報N(uBC)に対応する前記親ノード情報N(uBP)に対応する多項式q(uBP, α)に当該子ノード情報N(uBC)に対応する前記識別子index(uBC)を代入して得られるq(uBP, index(uBC))である、
ことを特徴とする鍵交換システム。
【請求項４】
巡回群G1, G2, GTの生成元がそれぞれg1, g2, gTであり、直積空間G1×G2の元を巡回群GTに写す双線形写像がe: G1×G2→GTであり、属性情報jの集合がATTであり、マスタ秘密鍵がλ及びt(j)(j∈ATT)であり、マスタ公開鍵がΛ=gTλ∈GT及びT(j)=g2t(j)∈G2であり、UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む木構造データがγAであり、前記ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、前記親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、前記親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、前記子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、前記葉ノード情報N(uAL)に対応するuALの集合がL(γA)であり、前記親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、前記ノード情報N(uA)のそれぞれには情報q(uA, η(uA))が対応し、前記ルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))が前記マスタ秘密鍵λであり、前記親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uAP)に対応する前記子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))であり、前記葉ノード情報N(uAL)にはそれぞれ属性情報att(uAL)∈ATTと秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1とが対応し、前記秘密値D(uAL)(uAL∈L(γA))の集合が長期秘密鍵DA={D(uAL)}uAL∈L(γA)であり、
短期秘密鍵sAを任意に生成する短期秘密鍵生成部と、
前記属性情報の集合ATTの部分集合である属性集合δA⊂ATTと前記長期秘密鍵DAと前記短期秘密鍵sAとを用い、前記長期秘密鍵DAと前記短期秘密鍵sAとを含む値の像χに対する元T(wA)χ∈G2(wA∈δA)の集合であるTA={T(wA)χ}wA∈δAを含む第１短期公開鍵を生成する短期公開鍵生成部と、
前記属性集合δAと前記第１短期公開鍵とを他の鍵交換装置に対して出力する出力部と、
属性集合δBと第２短期公開鍵との入力を受け付ける入力部と、
前記属性集合δBに属する前記属性情報att(uAL)∈δBに対応する前記葉ノード情報N(uAL)に対応する秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1と前記第２短期公開鍵が含む元T(att(uAL))υ∈G2とに対し、前記双線形写像eを作用させ、前記葉ノード情報N(uAL)に対して復元値e(D(uAL), T(att(uAL))υ)=gTυ・q(uAL, η(uAL))∈GTを生成する葉ノード復元値生成部と、
自らに対応する前記子ノード情報N(uAC)のうち復元値gTυ・q(uAC, η(uAC))∈GTが生成されたものの合計数が自らに対応する前記しきい値k(uAP)以上となる前記親ノード情報N(uAP)に対し、当該しきい値k(uAP)以上の前記復元値gTυ・q(uAC, η(uAC))∈GTをk(uAP)-out-of-c(uAP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTυ・q(uAP, η(uAP))∈GTを生成する親ノード復元値生成部と、
前記親ノード復元値生成部が、前記ルートノード情報N(uAR)に対する復元値gTυ・q(uAR, η(uAR))=gTυ・λ∈GTを生成した場合、Λχ=gTχ・λ∈GTとgTυ・λ∈GTとを含む値の像をセッション鍵として出力する鍵生成部と、
を有する鍵交換装置。
【請求項５】
巡回群G1, G2, GTの生成元がそれぞれg1, g2, gTであり、直積空間G1×G2の元を巡回群GTに写す双線形写像がe: G1×G2→GTであり、属性情報jの集合がATTであり、マスタ秘密鍵がλ及びt(j)(j∈ATT)であり、T(j)=g2t(j)∈G2であり、UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む木構造データがγAであり、前記ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、前記親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、前記親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、前記子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、前記葉ノード情報N(uAL)に対応するuALの集合がL(γA)であり、前記親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、
前記マスタ秘密鍵λを前記ルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))として設定する第１設定部と、
前記親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報を当該親ノード情報N(uAP)に対応する前記子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))として設定する第２設定部と、
前記葉ノード情報N(uAL)に対応する属性情報att(uAL)∈ATTに対し、秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1を生成する秘密値生成部と、
前記秘密値D(uAL)(uAL∈L(γA))の集合である長期秘密鍵DA={D(uAL)}uAL∈L(γA)を出力する出力部と、
を有する鍵抽出装置。
【請求項６】
請求項５の鍵抽出装置であって、
前記子ノード情報N(uAC)のそれぞれには識別子index(uAC)が対応し、前記葉ノード情報N(uAL)にはしきい値k(uAL)=1が対応し、前記ノード情報N(uA)のそれぞれには不定元αについての次数d(uA)=k(uA)-1の多項式q(uA, α)が対応し、η(uA)が前記ノード情報N(uA)に対応する定数であり、前記情報q(uA, η(uA))が前記多項式q(uA, α)に定数η(uA)を代入して得られる値であり、
前記第１設定部は、
前記マスタ秘密鍵λを前記ルートノード情報N(uAR)に対する情報q(uAR, η(uAR))として設定する第１設定部と、
α=η(uAR)であるときの関数値q(uAR, η(uAR))が前記マスタ秘密鍵λである不定元αについての次数d(uAR)=k(uAR)-1の多項式q(uAR, α)を前記ルートノード情報N(uAR)に対して設定する第１多項式設定部と、を含み、
前記第２設定部は、
前記親ノード情報N(uAP)に対応する多項式q(uAP, α)に、当該親ノード情報N(uAP)に対応する前記子ノード情報N(uAC)に対応する前記識別子index(uAC)を代入して得られるq(uAP, index(uAC))を、当該子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))として設定する第２設定部と、
α=η(uAC)であるときの関数値q(uAC, η(uAC))がq(uAP, index(uAC))である不定元αについての次数d(uAC)=k(uAC)-1の多項式q(uAC, α)を前記子ノード情報N(uAC)に対して設定する第２多項式設定部と、を含む、
ことを特徴とする鍵抽出装置。
【請求項７】
巡回群G1, G2, GTの生成元がそれぞれg1, g2, gTであり、直積空間G1×G2の元を巡回群GTに写す双線形写像がe: G1×G2→GTであり、属性情報jの集合がATTであり、マスタ秘密鍵がλ及びt(j)(j∈ATT)であり、マスタ公開鍵がΛ=gTλ∈GT及びT(j)=g2t(j)∈G2であり、UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む木構造データがγAであり、前記ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、前記親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、前記親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、前記子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、前記葉ノード情報N(uAL)に対応するuALの集合がL(γA)であり、前記親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、前記ノード情報N(uA)のそれぞれには情報q(uA, η(uA))が対応し、前記ルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))が前記マスタ秘密鍵λであり、前記親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報が当該親ノード情報N(uAP)に対応する前記子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))であり、前記葉ノード情報N(uAL)にはそれぞれ属性情報att(uAL)∈ATTと秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1とが対応し、前記秘密値D(uAL)(uAL∈L(γA))の集合が長期秘密鍵DA={D(uAL)}uAL∈L(γA)であり、
短期秘密鍵生成部において、短期秘密鍵sAを任意に生成するステップと、
短期公開鍵生成部において、前記属性情報の集合ATTの部分集合である属性集合δA⊂ATTと前記長期秘密鍵DAと前記短期秘密鍵sAとを用い、前記長期秘密鍵DAと前記短期秘密鍵sAとを含む値の像χに対する元T(wA)χ∈G2(wA∈δA)の集合であるTA={T(wA)χ}wA∈δAを含む第１短期公開鍵を生成するステップと、
出力部において、前記属性集合δAと前記第１短期公開鍵とを他の鍵交換装置に対して出力するステップと、
入力部において、属性集合δBと第２短期公開鍵との入力を受け付けるステップと、
葉ノード復元値生成部において、前記属性集合δBに属する前記属性情報att(uAL)∈δBに対応する前記葉ノード情報N(uAL)に対応する秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1と前記第２短期公開鍵が含む元T(att(uAL))υ∈G2とに対し、前記双線形写像eを作用させ、前記葉ノード情報N(uAL)に対して復元値e(D(uAL), T(att(uAL))υ)=gTυ・q(uAL, η(uAL))∈GTを生成するステップと、
親ノード復元値生成部において、自らに対応する前記子ノード情報N(uAC)のうち復元値gTυ・q(uAC, η(uAC))∈GTが生成されたものの合計数が自らに対応する前記しきい値k(uAP)以上となる前記親ノード情報N(uAP)に対し、当該しきい値k(uAP)以上の前記復元値gTυ・q(uAC, η(uAC))∈GTをk(uAP)-out-of-c(uAP)しきい値秘密分散法の分散情報として用い、当該分散情報に対応する復元値gTυ・q(uAP, η(uAP))∈GTを生成するステップと、
前記親ノード復元値生成部で前記ルートノード情報N(uAR)に対する復元値gTυ・q(uAR, η(uAR))=gTυ・λ∈GTが生成された場合、鍵生成部において、Λχ=gTχ・λ∈GTとgTυ・λ∈GTとを含む値の像をセッション鍵として出力するステップと、
を有する鍵交換方法。
【請求項８】
巡回群G1, G2, GTの生成元がそれぞれg1, g2, gTであり、直積空間G1×G2の元を巡回群GTに写す双線形写像がe: G1×G2→GTであり、属性情報jの集合がATTであり、マスタ秘密鍵がλ及びt(j)(j∈ATT)であり、T(j)=g2t(j)∈G2であり、UA(UA≧2)個のノード情報N(uA)(uA∈{1,...,UA})を含む木構造データがγAであり、前記ノード情報N(uA)の一部が親ノード情報N(uAP)(uAP∈{1,...,UA})であり、前記親ノード情報N(uAP)にはc(uAP)個の子ノード情報N(uAC)(uAC∈{1,...,UA})が対応し、前記親ノード情報N(uAP)の何れか１つがルートノード情報N(uAR)(uAR∈{1,...,UA})であり、前記子ノード情報N(uAC)の少なくとも一部が葉ノード情報N(uAL)(uAL∈{1,...,UA})であり、前記葉ノード情報N(uAL)に対応するuALの集合がL(γA)であり、前記親ノード情報N(uAP)のそれぞれには1≦k(uAP)≦c(uAP)を満たすしきい値k(uAP)が対応し、
第１設定部において、前記マスタ秘密鍵λを前記ルートノード情報N(uAR)に対応する情報q(uAR, η(uAR))として設定するステップと、
第２設定部において、前記親ノード情報N(uAP)に対応する情報q(uAP, η(uAP))をk(uAP)-out-of-c(uAP)しきい値秘密分散して得られる分散情報を当該親ノード情報N(uAP)に対応する前記子ノード情報N(uAC)に対応する情報q(uAC, η(uAC))として設定するステップと、
秘密値生成部において、前記葉ノード情報N(uAL)に対応する属性情報att(uAL)∈ATTに対し、秘密値D(uAL)=g1q(uAL, η(uAL))/t(att(uAL))∈G1を生成するステップと、
出力部において、前記秘密値D(uAL)(uAL∈L(γA))の集合である長期秘密鍵DA={D(uAL)}uAL∈L(γA)を出力するステップと、
を有する鍵抽出方法。
【請求項９】
請求項７の鍵交換方法の処理をコンピュータに実行させるためのプログラム。
【請求項１０】
請求項８の鍵抽出方法の処理をコンピュータに実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１１−２５９１４９（Ｐ２０１１−２５９１４９Ａ）
【公開日】平成２３年１２月２２日（２０１１．１２．２２）
【国際特許分類】
【出願番号】特願２０１０−１３１１３０（Ｐ２０１０−１３１１３０）
【出願日】平成２２年６月８日（２０１０．６．８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年１２月２２日（２０１１．１２．２２）
【国際特許分類】
【出願日】平成２２年６月８日（２０１０．６．８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]