説明

鍵交換システム、鍵交換装置、鍵生成装置、鍵交換方法、鍵交換プログラム

【課題】ランダムオラクルを仮定しない安全な鍵交換技術を提供する。
【解決手段】本発明の鍵交換システムは、少なくとも鍵交換装置αと鍵交換装置βとを備え、セッション鍵を交換する。本発明の鍵交換システムでは、鍵交換を行うユーザは、本来認証に用いる自分の属性集合S以外に、ダミー属性集合Wを用意し、生成した使い捨て署名の検証鍵の値にWを割り当てる。この時、ユーザは相手が満たすことを希望するアクセス構造Aに加えて、特定の検証鍵に対応したダミー属性集合Wが満たすようなアクセス構造を認証条件として加えて、鍵交換を行う。また、最後のセッション鍵の導出の時に、ランダムオラクルではなく、強ランダム抽出器と擬似ランダム関数を用いる。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は情報セキュリティに関するものであり、特に、二者間でセッション鍵を共有するための鍵交換システム、鍵交換装置、鍵生成装置、鍵交換方法、鍵交換プログラムに関する。
【背景技術】
【0002】
鍵交換時にアクセスポリシーを指定でき、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができる鍵交換システムについて、非特許文献1に公開されている。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】Kazuki Yoneyama, “Strongly Secure Two-Pass Attribute-Based Authenti-cated Key Exchange”, Pairing 2010, LNCS 6487, pp147-166, 2010.
【発明の概要】
【発明が解決しようとする課題】
【0004】
非特許文献1に対応する内容は、本願出願時には未公開の特願2010−259053に記載されており、以下のとおりである。
【0005】
[構成]
図1に特願2010−259053の鍵交換システムの構成例を示す。鍵交換システムは、ネットワーク1000を介して接続された鍵交換装置100,…,100(ただし、Qは2以上の整数、qは1以上Q以下の整数、AとBは1以上Q以下の異なる整数)、鍵生成装置300で構成される。図2に鍵交換装置の機能構成例、図3に鍵生成装置の機能構成例を示す。鍵交換装置100は、アクセス構造決定部110、短期秘密鍵生成部120、交換情報生成部130、送信部140、受信部145、属性確認部150、秘密情報取得部160、セッション鍵計算部170、中間情報消去部180、記録部190を備える。また、鍵生成装置300は、マスタ鍵生成部310、長期秘密鍵生成部320、記録部390を備える。以下の説明では、鍵交換装置100(鍵交換装置αに相当)がイニシエータとして機能し、鍵交換装置100(鍵交換装置βに相当)がレスポンダとして機能してセッション鍵を共有する場合について説明する。
【0006】
なお、κは整数、pはκビットの素数、GとGは位数pの群、gは群Gの生成元、gは群Gの生成元、eはG×G→Gのように写像する双線形写像、Hは任意長の整数を群Gの元に変換するハッシュ関数、Hは任意長の整数を0以上p−1以下の整数に変換するハッシュ関数、Hは任意長の整数をκビットの整数に変換するハッシュ関数、Pは属性を示す属性要素、属性集合Sは鍵交換装置100の属性を示す属性要素Pの組み合わせの集合、属性集合Sは鍵交換装置100の属性を示す属性要素Pの組み合わせの集合、NMAXはあらかじめ定めた整数、jとnは1以上NMAX以下の整数、kは属性集合Sの要素、kは属性集合Sの要素、{T}はT[1],…,T[NMAX]の集合、{T}はT[1],…,T[NMAX]の集合、{S}はS[1],…,S[NMAX]の集合、{S}はS[1],…,S[NMAX]の集合、{U}はUi,jの集合、{V}はVi,jの集合である。
【0007】
[鍵生成、鍵抽出]
図4に、マスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す。なお、長期秘密鍵生成の処理が鍵抽出に相当する。鍵生成装置300のマスタ鍵生成部310は、0以上p−1以下の整数からランダムにrとzを選定する。そして、マスタ公開鍵を(g,g^r,g^z)、マスタ秘密鍵をg^zとして記録部390に記録し、マスタ公開鍵(g,g^r,g^z)を公開する(S310)。鍵交換装置100と鍵交換装置100は、それぞれマスタ公開鍵を(g,g^r,g^z)を受信し、記録部190と記録部190に記録する。
【0008】
長期秘密鍵生成部320は、0以上p−1以下の整数からランダムにt[1],…,t[NMAX]を選び、S’=g^z・g^(rt[1])を計算し、1以上NMAX以下のjについてT[j]=g^t[1]を計算し、属性集合Sの要素kについて
【0009】
【数1】

【0010】
を計算し、長期秘密鍵として(S’,{T},{S})を鍵交換装置100に送信する(S320)。鍵交換装置100は、長期秘密鍵(S’,{T},{S})を受信し、記録部190に記録する(S192)。
【0011】
さらに、長期秘密鍵生成部320は、0以上p−1以下の整数からランダムにt[1],…,t[NMAX]を選び、S’=g^z・g^(rt[1])を計算し、1以上NMAX以下のjについてT[j]=g^t[1]を計算し、属性集合Sの要素kについて
【0012】
【数2】

【0013】
を計算し、長期秘密鍵として(S’,{T},{S})を鍵交換装置100に送信する(S320)。鍵交換装置100は、長期秘密鍵(S’,{T},{S})を受信し、記録部190に記録する(S192)。
【0014】
なお、あらかじめ鍵交換装置100の記録部190にマスタ公開鍵(g,g^r,g^z)と長期秘密鍵(S’,{T},{S})とを記録させ、鍵交換装置100の記録部190にマスタ公開鍵(g,g^r,g^z)と長期秘密鍵(S’,{T},{S})とを記録させておけば、ネットワーク1000を介して接続された鍵交換装置100と鍵交換装置100だけで最低限の鍵交換システムが構成できる。
【0015】
[鍵交換]
図5にセッション鍵を共有する鍵交換の処理のフローの例を示す。この例は、鍵交換装置100(鍵交換装置αに相当)がイニシエータとして機能し、鍵交換装置100(鍵交換装置βに相当)がレスポンダとして機能する場合を示している。
【0016】
鍵交換装置100は、アクセス構造決定部110、短期秘密鍵生成部120、交換情報生成部130、送信部140、受信部145、属性確認部150、秘密情報取得部160、セッション鍵計算部170、中間情報消去部180を備える。鍵交換装置100は、アクセス構造決定部110、短期秘密鍵生成部120、交換情報生成部130、送信部140、受信部145、属性確認部150、秘密情報取得部160、セッション鍵計算部170、中間情報消去部180を備える。
【0017】
アクセス構造決定部110は、アクセス構造Aを決定し、当該アクセス構造Aに対応するシェア情報生成行列Mと単射ラベリング関数ρを生成する(S110)。短期秘密鍵生成部120は、1≦j≦Nについて、uを0以上p−1以下の整数からランダムに選定する(S120)。交換情報生成部130は、
1≦j≦Nについて、u=H(S’,{T},{S},u)、
X=g^u
1≦i≦Lと1≦j≦Nについて、
i,j=g^(r(Mi,j)・H(j,ρ(i))^(−u)、
1≦i≦LとN+1≦j≦NMAXについて、
i,j=H(j,ρ(i))^(−u
を計算する(130)。送信部140は、X、{U}、M、ρを鍵交換装置100に送信する(S140)。中間情報消去部180は、u(1≦j≦N)を消去する(S180)。
【0018】
受信部145は、鍵交換装置100から、X、{U}、M、ρを受信する(S145)。属性確認部150は、属性集合Sがシェア情報生成行列Mと単射ラベリング関数ρを満たすか、Xと{U}が群Gの要素かを確認する(S150)。
【0019】
アクセス構造決定部110は、アクセス構造Aを決定し、当該アクセス構造Aに対応するシェア情報生成行列Mと単射ラベリング関数ρを生成する(S110)。短期秘密鍵生成部120は、1≦j≦Nについて、vを0以上p−1以下の整数からランダムに選定する(S120)。交換情報生成部130は、
1≦j≦Nについて、v=H(S’,{T},{S},v)、
Y=g^v
1≦i≦Lと1≦j≦Nについて、
i,j=g^(r(Mi,j)・H(j,ρ(i))^(−v)、
1≦i≦LとN+1≦j≦NMAXについて、
i,j=H(j,ρ(i))^(−v
を計算する(S130)。送信部140は、Y、{V}、M、ρを鍵交換装置100に送信する(S140)。
【0020】
秘密情報取得部160は、I={k:ρ(k)∈S}となる集合Iを求め、鍵交換装置100が生成した秘密情報uに対する正当なシェア情報集合{(Mi,j}について
【0021】
【数3】

【0022】
が成り立つ0以上p−1以下の整数w[k](ただし、kは集合Iの要素)を求める(S160)。セッション鍵計算部170は、
【0023】
【数4】

【0024】
σ=(g^z)^v
σ=X^v
を計算し、セッション鍵Kを、
K=H(σ,σ,σ,(X,{U},M,ρ),(Y,{V},M,ρ))
のように求める(S170)。中間情報消去部180は、v(1≦j≦N)を消去する(S180)。
【0025】
受信部145は、鍵交換装置100から、Y、{V}、M、ρを受信する(S145)。属性確認部150は、属性集合Sがシェア情報生成行列Mと単射ラベリング関数ρを満たすか、Yと{V}が群Gの要素かを確認する(S150)。秘密情報取得部160は、I={k:ρ(k)∈S}となる集合Iを求め、鍵交換装置100が生成した秘密情報vに対する正当なシェア情報集合{(Mi,j}について
【0026】
【数5】

【0027】
が成り立つ0以上p−1以下の整数w[k](ただし、kは集合Iの要素)を求める(S160)。セッション鍵計算部170は、
【0028】
【数6】

【0029】
σ=(g^z)^H(S’,{T},{S},u
σ=Y^H(S’,{T},{S},u
を計算し、セッション鍵Kを、
K=H(σ,σ,σ,(X,{U},M,ρ),(Y,{V},M,ρ))
のように求める。
【0030】
この鍵交換システムは、上述のような処理によって鍵交換時にアクセスポリシーを指定でき、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができる。しかしながら、安全性を保証するためには、ハッシュ関数が理想的に安全(ランダムオラクル)でなければならないという問題がある。ランダムオラクルは現実のハッシュ関数を用いては実現できないことが知られている。よって、ランダムオラクルを仮定せずに安全性証明が付く方式が望ましい。
【0031】
本発明は、非特許文献1の鍵交換技術と同じように鍵交換時にアクセスポリシーを指定できることと、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができることを確保しながら、ランダムオラクルを仮定しない安全な鍵交換技術を提供することを目的とする。
【課題を解決するための手段】
【0032】
本発明の鍵交換システムは、少なくとも鍵交換装置αと鍵交換装置βとを備える。ここで、κは整数、pはκビットの素数、GとGは位数pの群、gは群Gの生成元、gは群Gの生成元、eはG×G→Gのように写像する双線形写像、F_σは任意長の整数を指定された鍵空間Kspaceの値σにしたがってκビットの整数に変換する擬似ランダム関数、Extは群Gの元を鍵空間Kspaceの値に変換する強ランダム抽出器、Dは整数、dは1以上D以下の整数、genは検証鍵のビット長がDであるような使い捨て署名の鍵生成のアルゴリズム、sigは検証鍵のビット長がDであるような使い捨て署名の署名生成のアルゴリズム、verは検証鍵のビット長がDであるような使い捨て署名の検証のアルゴリズム、att’は属性の全要素数を示す整数、W_Rはd番目のダミー属性を示す情報が1ビット以上のビット列Rであることを示す記号、Pは属性を示す属性要素、属性集合Sは鍵交換装置αの属性を示す属性要素Pの集合、アクセス構造Aは鍵交換装置αが鍵交換装置βに求める属性要素Pの組み合わせの集合、単射ラベリング関数ρは前記アクセス構造Aを示す関数、属性集合ρ(i)は前記アクセス構造Aに対応するi番目の集合、シェア情報生成行列Mはi行目が属性集合ρ(i)に対応するL行N列の行列、(Mはシェア情報生成行列Mのi番目の行に対応するベクトル、属性集合Sは鍵交換装置βの属性を示す属性要素Pの集合、アクセス構造Aは鍵交換装置βが鍵交換装置αに求める属性要素Pの組み合わせの集合、単射ラベリング関数ρは前記アクセス構造Aを示す関数、属性集合ρ(i)は前記アクセス構造Aに対応するi番目の集合、シェア情報生成行列Mはi行目が属性集合ρ(i)に対応するL行N列の行列、(Mはシェア情報生成行列Mのi番目の行に対応するベクトル、L、N、L、Nは整数、nは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた1以上N以下の整数、nは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた1以上N以下の整数、kは属性集合Sの要素、kは属性集合Sの要素、rとzは0以上p−1以下の整数、h[1],…,h[att’]は群Gの元、(g,g^r,g^z,h[1],…,h[att’])はマスタ公開鍵、g^zはマスタ秘密鍵、tは0以上p−1以下の整数、tは0以上p−1以下の整数、S’=g^z・g^(rt)、S’=g^z・g^(rt)、T=g^t、T=g^t、S[k]=h[k]^t、S[k]=h[k]^t、{S}はS[k]の集合、{S}はS[k]の集合、{U}はUの集合、{X}はXの集合、{V}はVの集合、{Y}はYの集合、^はべき乗を示す記号、(+)はビットごとの排他的論理和を示す記号とする。
【0033】
鍵交換装置αは、第1の記録部、第1のアクセス構造決定部、第1の短期秘密鍵生成部、第1の交換情報生成部、第1の送信部、第1の受信部、第1の秘密情報取得部、第1の属性確認部、第1のセッション鍵計算部、第1の中間情報消去部を備える。鍵交換装置βは、第2の記録部、第2のアクセス構造決定部、第2の短期秘密鍵生成部、第2の交換情報生成部、第2の送信部、第2の受信部、第2の秘密情報取得部、第2の属性確認部、第2のセッション鍵計算部、第2の中間情報消去部を備える。第1の記録部は、長期秘密鍵としてS’,T,{S}を記録する。第2の記録部は、長期秘密鍵としてS’,T,{S}を記録する。
【0034】
第1のアクセス構造決定部は、アクセス構造Aを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkと使い捨て秘密鍵skを生成し、ダミー属性集合W={W_vkA1,…,W_vkAd,…,W_vkAD}(ただし、vkAdは使い捨て公開鍵vkのd番目のビット)を設定する。そして、当該アクセス構造A又はすべてのダミー属性W_vkA1,…,W_vkADを満たす条件に対応する線形秘密分散法のシェア情報生成行列Mと単射ラベリング関数ρを生成する。
【0035】
第1の短期秘密鍵生成部は、1≦j≦Nについてu_jを0以上p−1以下の整数からランダムに選定してu=(u_1,…,u_N)とし、xを0以上p−1以下の整数からランダムに選定し、1≦i≦Lについてxを0以上p−1以下の整数からランダムに選定する。
【0036】
第1の交換情報生成部は、1≦i≦Lについてベクトルuとベクトル(Mとの内積を計算してシェアλAiとする。そして、U=g^u_nとX=g^xと、1≦i≦LについてU=g^(rλAi)h[ρ(i)]^(−x)とX=g^xを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskを鍵、(U,{U},X,{X})をメッセージとする使い捨て署名sを生成する。
【0037】
第1の送信部は、EPK=(U,{U},X,{X},M,ρ,vk,s)を鍵交換装置βに送信する。第1の受信部は、鍵交換装置βから、EPK=(V,{V},Y,{Y},M,ρ,vk,s)を受信する。
【0038】
第1の秘密情報取得部は、I={i:ρ(i)∈S}となる集合IとI’={i:ρ(i)∈W}となる集合I’を求め、シェア情報生成行列Mに対応する秘密情報v_nの正当なシェア集合{λBi}について、
【0039】
【数7】

【0040】
が成り立つ0以上p−1以下の整数wAiと整数w’Aiを求める。
【0041】
第1の属性確認部は、属性集合Sがシェア情報生成行列Mと単射ラベリング関数ρを満たすかを確認することと、V,{V},Y,{Y}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkを鍵、(V,{V},Y,{Y},s)をメッセージとして検証した結果が真であること、
【0042】
【数8】

【0043】
が成り立つことを確認する。
第1のセッション鍵計算部は、
【0044】
【数9】

【0045】
σ=(g^z)^u_n
σ=e(g^r,Y)^x
を計算し、σ’←Ext(σ),σ’←Ext(σ),σ’←Ext(σ)を計算し、セッション識別子sidを(EPK,EPK)に設定し、セッション鍵Kを、
K=F_σ’(sid)(+)F_σ’(sid)(+)F_σ’(sid)
のように求める。
【0046】
第1の中間情報消去部は、少なくともu_j(1≦j≦N)、x、x(1≦i≦L)、EPK、EPK、σ、σ、σ、σ’、σ’、σ’、sid、skを消去する。
【0047】
第2のアクセス構造決定部は、アクセス構造Aを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkと使い捨て秘密鍵skを生成し、ダミー属性集合W={W_vkB1,…,W_vkBd,…,W_vkBD}(ただし、vkBdは使い捨て公開鍵vkのd番目のビット)を設定する。そして、当該アクセス構造A又はすべてのダミー属性W_vkB1,…,W_vkBDを満たす条件に対応する線形秘密分散法のシェア情報生成行列Mと単射ラベリング関数ρを生成する。
【0048】
第2の短期秘密鍵生成部は、1≦j≦Nについてv_jを0以上p−1以下の整数からランダムに選定してv=(v_1,…,v_N)とし、yを0以上p−1以下の整数からランダムに選定し、1≦i≦Lについてyを0以上p−1以下の整数からランダムに選定する。
【0049】
第2の交換情報生成部は、1≦i≦Lについてベクトルvとベクトル(Mとの内積を計算してシェアλBiとする。そして、V=g^v_nとY=g^yと、1≦i≦LについてV=g^(rλBi)h[ρ(i)]^(−y)とY=g^yを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskを鍵、(V,{V},Y,{Y})をメッセージとする使い捨て署名sを生成する。
【0050】
第2の送信部は、EPK=(V,{V},Y,{Y},M,ρ,vk,s)を鍵交換装置αに送信する。第2の受信部は、鍵交換装置αから、EPK=(U,{U},X,{X},M,ρ,vk,s)を受信する。
【0051】
第2の秘密情報取得部は、I={i:ρ(i)∈S}となる集合IとI’={i:ρ(i)∈W}となる集合I’を求め、シェア情報生成行列Mに対応する秘密情報u_nの正当なシェア集合{λAi}について、
【0052】
【数10】

【0053】
が成り立つ0以上p−1以下の整数wBiと整数w’Biを求める。
【0054】
第2の属性確認部は、属性集合Sがシェア情報生成行列Mと単射ラベリング関数ρを満たすかを確認することと、U,{U},X,{X}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkを鍵、(U,{U},X,{X},s)をメッセージとして検証した結果が真であること、
【0055】
【数11】

【0056】
が成り立つことを確認する。
第2のセッション鍵計算部は、
【0057】
【数12】

【0058】
σ=(g^z)^v_n
σ=e(g^r,X)^y
を計算し、σ’←Ext(σ),σ’←Ext(σ),σ’←Ext(σ)を計算し、セッション識別子sidを(EPK,EPK)に設定し、セッション鍵Kを、
K=F_σ’(sid)(+)F_σ’(sid)(+)F_σ’(sid)
のように求める。
【0059】
第2の中間情報消去部は、少なくともv_j(1≦j≦N)、y、y(1≦i≦L)、EPK、EPK、σ、σ、σ、σ’、σ’、σ’、sid、skを消去する。
【0060】
なお、本発明の鍵交換システムは、さらに、マスタ鍵生成部と長期秘密鍵生成部とを有する鍵生成装置を備えてもよい。この場合は、マスタ鍵生成部が、r,z,h[1],…,h[att’]をランダムに選定し、マスタ公開鍵(g,g^r,g^z,h[1],…,h[att’])とマスタ秘密鍵g^zを生成すればよい。また、長期秘密鍵生成部がtとtをランダムに選定し、S’とS’、TとT、S[k]とS[k]を計算すればよい。
【発明の効果】
【0061】
本発明の鍵交換システムによれば、線形秘密分散法を利用することにより、鍵抽出(長期秘密鍵の生成)を行うときには鍵生成装置が、鍵交換装置α、βの属性集合S、Sに基づき線形秘密分散法のシェア情報として長期秘密鍵(S’,T,{S})、(S’,T,{S})を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造A、Aを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定することが可能である。また、本発明のマスタ秘密鍵g^zとマスタ公開鍵(g,g^r,g^z,h[1],…,h[att’])は、属性集合とは独立なので、属性の全体集合をあらかじめ決めておく必要がない。つまり、鍵抽出時に任意の属性に基づき長期秘密鍵を発行することができる。したがって、非特許文献1と同等の効果が得られる。
【0062】
さらに、使い捨て署名、強ランダム抽出器、擬似ランダム関数を用いることにより、以下のように、ランダムオラクルを仮定しないで安全性を確保できる。鍵交換を行うユーザは、本来認証に用いる自分の属性集合S以外に、ダミー属性集合Wを用意し、生成した使い捨て署名の検証鍵の値にWを割り当てる。この時、ユーザは相手が満たすことを希望するアクセス構造Aに加えて、特定の検証鍵に対応したダミー属性集合Wが満たすようなアクセス構造を認証条件として加えて、鍵交換を行う。ダミー属性集合Wの方は、実際のユーザ同士が行う鍵交換セッションでは使われることはない。しかし、安全性証明の中で送られてきたメッセージが正しいかどうかを判定する際に、ダミー属性集合Wの方の認証条件を用いることにより、アクセス構造Aを満たす属性集合に対応する秘密鍵の知識なしで判定することができる。また、最後のセッション鍵の導出の時に、ランダムオラクルではなく、強ランダム抽出器と擬似ランダム関数を用いる。具体的には、強ランダム抽出器で共有情報の分布をならし、その値を擬似ランダム関数の鍵とすることで出力をセッション鍵とする。このように、本発明ではランダムオラクルを仮定すること無しに安全性を保つことができる。
【図面の簡単な説明】
【0063】
【図1】特願2010−259053の鍵交換システムの構成例を示す図。
【図2】特願2010−259053の鍵交換装置の機能構成例を示す図。
【図3】特願2010−259053の鍵生成装置の機能構成例を示す図。
【図4】特願2010−259053のマスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す図。
【図5】特願2010−259053のセッション鍵を共有する鍵交換の処理のフローの例を示す図。
【図6】本発明の鍵交換システムの構成例を示す図。
【図7】本発明の鍵交換装置の機能構成例を示す図。
【図8】本発明の鍵生成装置の機能構成例を示す図。
【図9】本発明のマスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す図。
【図10】本発明のセッション鍵を共有する鍵交換の処理のフローの例を示す図。
【発明を実施するための形態】
【0064】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例1】
【0065】
[準備]
本発明の鍵交換システムについて説明する前に、本発明を理解する上で必要な理論について説明する。本発明では、アクセスポリシーを次のようなアクセス構造として表すものとする。
【0066】
まず、{P,P,…,P,…,P}を属性集合とする。ただし、Nは整数、nは1以上N以下の整数である。Pは、例えば、「性別が男性である。」や「○○会社の社員である。」などの鍵生成装置の利用者(ユーザ)の属性を示している。なお、以下の説明では、「鍵生成装置の利用者の属性」を単に「鍵生成装置の属性」と表現する。アクセス構造は{P,P,…,P}の空でない部分集合のべき集合Aとして表わす。すなわち、
A⊆2^{P,P,…,P}\{φ}
ただし、“^”はべき乗を示す記号、“φ”は空集合を示す記号、“\{φ}”は空集合を除くことを示す記号
に属する集合を許可集合、属さない集合を不許可集合とよぶ。本発明では、上記のアクセス構造に基づきアクセスコントロールを行うために次のように線形秘密分散法を用いる。
【0067】
各属性集合に対応するシェア情報は0以上p−1以下の整数の集合Z上のベクトルとして表される。シェア情報を生成する行列としてL行N列のシェア情報生成行列Mを次のように用意する。i=1,…,Lについて、属性ラベリング関数ρを用いてシェア情報生成行列Mのi行目を属性ρ(i)に対応させる。属性ラベリング関数ρは、iを特定すると属性ρ(i)が決まる関数である。また、「属性ρ(i)に対応させる」とは、例えば、属性ρ(1)がP∧P∧Pであれば、1,1,1,0,0,…,0のようにシェア情報生成行列Mの1行目を設定し、属性ρ(2)がP∧Pであれば、1,0,0,…,0,1のようにシェア情報生成行列Mの2行目を設定するように、属性ρ(i)と対応させてi行目を決めることである。なお、上記の例では、アンド条件に含まれる属性Pに対応する要素を“1”とし、含まれない属性Pに対応する要素を“0”としたが、これに限る必要はない。異なる条件に対応する行が同じ行にならないように対応付けされていればよいので、属性ラベリング関数ρは単射性を有する範囲で他の対応でもよい。
【0068】
次に、0以上p−1以下の整数からr,…,rをランダムに選び、ベクトルv=(r,…,rを生成する。ただし、Tは転置を示す記号である。また、あらかじめ定めておいたn番目の要素rを秘密情報とする。なお、鍵交換したい装置同士の場合、秘密情報として共有する情報が同じであれば任意の情報でかまわないので、ランダムに選んだ整数の何番目を秘密情報にするかをあらかじめ決めておけばよい。この時、Mは秘密情報rのL個のシェア情報のベクトルとなる。属性集合ρ(i)にシェア情報(Mv)を割り当てる。ただし、(Mv)はベクトルMvのi番目の成分を示している。
【0069】
このようにシェア情報生成行列Mと秘密情報を含む列ベクトルvを用いると、線形秘密分散法の線形復元性を利用できる。ここで、線形復元性について説明する。あるアクセス構造Aを考え、属性集合SをS∈Aの任意の許可集合とし、I⊂{1,2,…,L}をI={i:ρ(i)∈S}と定義する。このとき、{λ}がrの正しいシェア情報の集合の場合、
【0070】
【数13】

【0071】
となるような0以上p−1以下の整数の集合{w}が存在する。このような集合{w}はMのサイズの多項式時間で見つけられることが知られている。一方、{λ}がrの正しいシェア情報の集合でない場合、集合{w}のすべての要素を求めることができない。本発明では、上述のようにシェア情報生成行列Mと秘密情報を含む列ベクトルvを用いることで、線形秘密分散法の線形復元性を利用してセッション鍵を交換する。
【0072】
[構成]
図6に本発明の鍵交換システムの構成例を示す。本発明の鍵交換システムは、ネットワーク1000を介して接続された鍵交換装置500,…,500(ただし、Qは2以上の整数、qは1以上Q以下の整数、AとBは1以上Q以下の異なる整数)、鍵生成装置600で構成される。図7に本発明の鍵交換装置の機能構成例、図8に本発明の鍵生成装置の機能構成例を示す。鍵交換装置500は、アクセス構造決定部510、短期秘密鍵生成部520、交換情報生成部530、送信部540、受信部545、属性確認部550、秘密情報取得部560、セッション鍵計算部570、中間情報消去部580、記録部590を備える。また、鍵生成装置600は、マスタ鍵生成部610、長期秘密鍵生成部620、記録部690を備える。以下の説明では、鍵交換装置500(鍵交換装置αに相当)がイニシエータとして機能し、鍵交換装置500(鍵交換装置βに相当)がレスポンダとして機能してセッション鍵を共有する場合について説明する。
【0073】
なお、以下の説明では、κは整数、pはκビットの素数、GとGは位数pの群、gは群Gの生成元、gは群Gの生成元、eはG×G→Gのように写像する双線形写像、F_σは任意長の整数を指定された鍵空間Kspaceの値σにしたがってκビットの整数に変換する擬似ランダム関数、Extは群Gの元を鍵空間Kspaceの値に変換する強ランダム抽出器、Dは整数(ダミー属性の要素数)、dは1以上D以下の整数、genは検証鍵のビット長がDであるような使い捨て署名の鍵生成のアルゴリズム、sigは検証鍵のビット長がDであるような使い捨て署名の署名生成のアルゴリズム、verは検証鍵のビット長がDであるような使い捨て署名の検証のアルゴリズム、att’は属性の全要素数を示す整数(実際の属性とダミー属性の両方を合わせた全要素数)、W_Rはd番目のダミー属性を示す情報が1ビット以上のビット列Rであることを示す記号(本明細書では、1ビットの場合もビット列と呼ぶことにする)、Pは属性を示す属性要素、属性集合Sは鍵交換装置500の属性を示す属性要素Pの集合、アクセス構造Aは鍵交換装置500が鍵交換装置500に求める属性要素Pの組み合わせの集合、単射ラベリング関数ρはアクセス構造Aを示す関数、属性集合ρ(i)はアクセス構造Aに対応するi番目の集合、シェア情報生成行列Mはi行目が属性集合ρ(i)に対応するL行N列の行列、(Mはシェア情報生成行列Mのi番目の行に対応するベクトル、属性集合Sは鍵交換装置500の属性を示す属性要素Pの集合、アクセス構造Aは鍵交換装置500が鍵交換装置500に求める属性要素Pの組み合わせの集合、単射ラベリング関数ρはアクセス構造Aを示す関数、属性集合ρ(i)はアクセス構造Aに対応するi番目の集合、シェア情報生成行列Mはi行目が属性集合ρ(i)に対応するL行N列の行列、(Mはシェア情報生成行列Mのi番目の行に対応するベクトル、L、N、L、Nは整数、nは鍵交換装置500と鍵交換装置500とで共有するあらかじめ定めた1以上N以下の整数、nは鍵交換装置500と鍵交換装置500とで共有するあらかじめ定めた1以上N以下の整数、kは属性集合Sの要素、kは属性集合Sの要素、rとzは0以上p−1以下の整数、tは0以上p−1以下の整数、h[1],…,h[att’]は群Gの元、{S}はS[k]の集合、{S}はS[k]の集合、{U}はUの集合、{X}はXの集合、{V}はVの集合、{Y}はYの集合、^はべき乗を示す記号、(+)はビットごとの排他的論理和を示す記号とする。
【0074】
[鍵生成、鍵抽出]
図9に、マスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す。なお、長期秘密鍵生成の処理が鍵抽出に相当する。鍵生成装置600のマスタ鍵生成部610は、0以上p−1以下の整数からランダムにr、zを選定し、群Gの元からランダムにh[1],…,h[att’]を選定する。そして、マスタ公開鍵を(g,g^r,g^z,h[1],…,h[att’])、マスタ秘密鍵をg^zとして記録部390に記録し、マスタ公開鍵(g,g^r,g^z,h[1],…,h[att’])を公開する(S610)。鍵交換装置500と鍵交換装置500は、それぞれマスタ公開鍵(g,g^r,g^z,h[1],…,h[att’])を受信し、記録部590と記録部590に記録する(S591,S592)。
【0075】
長期秘密鍵生成部620は、0以上p−1以下の整数からランダムにtを選定し、S’=g^z・g^(rt)、T=g^t、属性集合Sの要素kについてS[k]=h[k]^tを計算し、長期秘密鍵として(S’,T,{S})を鍵交換装置500に送信する(S620)。鍵交換装置500は、長期秘密鍵(S’,T,{S})を受信し、記録部590に記録する(S592)。
【0076】
さらに、長期秘密鍵生成部620は、0以上p−1以下の整数からランダムにtを選定し、S’=g^z・g^(rt)、T=g^t、属性集合Sの要素kについてS[k]=h[k]^tを計算し、長期秘密鍵として(S’,T,{S})を鍵交換装置500に送信する(S620)。鍵交換装置500は、長期秘密鍵(S’,T,{S})を受信し、記録部590に記録する(S592)。
【0077】
なお、あらかじめ鍵交換装置500の記録部590にマスタ公開鍵(g,g^r,g^z,h[1],…,h[att’])と長期秘密鍵(S’,T,{S})とを記録させ、鍵交換装置500の記録部590にマスタ公開鍵(g,g^r,g^z,h[1],…,h[att’])と長期秘密鍵(S’,T,{S})とを記録させておけば、ネットワーク1000を介して接続された鍵交換装置500と鍵交換装置500だけで最低限の鍵交換システムが構成できる。
【0078】
[鍵交換]
図10にセッション鍵を共有する鍵交換の処理のフローの例を示す。この例は、鍵交換装置500(鍵交換装置αに相当)がイニシエータとして機能し、鍵交換装置500(鍵交換装置βに相当)がレスポンダとして機能する場合を示している。
【0079】
鍵交換装置500は、アクセス構造決定部510(第1のアクセス構造決定部)、短期秘密鍵生成部520(第1の短期秘密鍵生成部)、交換情報生成部530(第1の交換情報生成部)、送信部540(第1の送信部)、受信部545(第1の受信部)、属性確認部550(第1の属性確認部)、秘密情報取得部560(第1の秘密情報取得部)、セッション鍵計算部570(第1のセッション鍵計算部)、中間情報消去部580(第1の中間情報消去部)、記録部590(第1の記録部)を備える。鍵交換装置500は、アクセス構造決定部510(第2のアクセス構造決定部)、短期秘密鍵生成部520(第2の短期秘密鍵生成部)、交換情報生成部530(第2の交換情報生成部)、送信部540(第2の送信部)、受信部545(第2の受信部)、属性確認部550(第2の属性確認部)、秘密情報取得部560(第2の秘密情報取得部)、セッション鍵計算部570(第2のセッション鍵計算部)、中間情報消去部580(第2の中間情報消去部)、記録部590(第2の記録部)を備える。
【0080】
鍵交換装置500では、記録部590が長期秘密鍵としてS’,T,{S}を記録している。アクセス構造決定部510は、アクセス構造Aを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkと使い捨て秘密鍵skを生成し、ダミー属性集合W={W_vkA1,…,W_vkAd,…,W_vkAD}(ただし、vkAdは使い捨て公開鍵vkのd番目のビット)を設定する。そして、アクセス構造A又はすべてのダミー属性W_vkA1,…,W_vkADを満たす条件に対応する線形秘密分散法のシェア情報生成行列Mと単射ラベリング関数ρを生成する(S510)。
【0081】
短期秘密鍵生成部520は、1≦j≦Nについてu_jを0以上p−1以下の整数からランダムに選定してu=(u_1,…,u_N)とし、xを0以上p−1以下の整数からランダムに選定し、1≦i≦Lについてxを0以上p−1以下の整数からランダムに選定する(S520)。
【0082】
交換情報生成部530は、1≦i≦Lについてベクトルuとベクトル(Mとの内積を計算してシェアλAiとする。そして、
U=g^u_n
X=g^x
=g^(rλAi)h[ρ(i)]^(−x) ただし、1≦i≦L
=g^x ただし、1≦i≦L
を計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskを鍵、(U,{U},X,{X})をメッセージとする使い捨て署名sを生成する(S530)。
【0083】
第1の送信部540は、EPK=(U,{U},X,{X},M,ρ,vk,s)を鍵交換装置500に送信する(S540)。
【0084】
一方、鍵交換装置500では、記録部590が長期秘密鍵としてS’,T,{S}を記録している。そして、アクセス構造決定部510は、アクセス構造Aを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkと使い捨て秘密鍵skを生成し、ダミー属性集合W={W_vkB1,…,W_vkBd,…,W_vkBD}(ただし、vkBdは使い捨て公開鍵vkのd番目のビット)を設定する。そして、アクセス構造A又はすべてのダミー属性W_vkB1,…,W_vkBDを満たす条件に対応する線形秘密分散法のシェア情報生成行列Mと単射ラベリング関数ρを生成する(S510)。
【0085】
短期秘密鍵生成部520は、1≦j≦Nについてv_jを0以上p−1以下の整数からランダムに選定してv=(v_1,…,v_N)とし、yを0以上p−1以下の整数からランダムに選定し、1≦i≦Lについてyを0以上p−1以下の整数からランダムに選定する(S520)。
【0086】
交換情報生成部530は、1≦i≦Lについてベクトルvとベクトル(Mとの内積を計算してシェアλBiとする。そして、
V=g^v_n
Y=g^y
=g^(rλBi)h[ρ(i)]^(−y) ただし、1≦i≦L
=g^y ただし、1≦i≦L
を計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskを鍵、(V,{V},Y,{Y})をメッセージとする使い捨て署名sを生成する(S530)。
【0087】
送信部540は、EPK=(V,{V},Y,{Y},M,ρ,vk,s)を鍵交換装置500に送信する(S540)。
【0088】
受信部545は、鍵交換装置500から、EPK=(U,{U},X,{X},M,ρ,vk,s)を受信する(S545)。
【0089】
属性確認部550は、属性集合Sがシェア情報生成行列Mと単射ラベリング関数ρを満たすかを確認する。そして、満たさないと判断した場合は処理を中止する。満たすと判断した場合は、ステップS560に進む(S551)。
【0090】
秘密情報取得部560は、I={i:ρ(i)∈S}となる集合IとI’={i:ρ(i)∈W}となる集合I’を求める。そして、シェア情報生成行列Mに対応する秘密情報u_nの正当なシェア集合{λAi}について、
【0091】
【数14】

【0092】
が成り立つ0以上p−1以下の整数wBiと整数w’Biを求める(S560)。上述のように、nは鍵交換装置500と鍵交換装置500とで共有するあらかじめ定めた1以上N以下の整数であればよい。例えば、n=1とすればよい。
【0093】
属性確認部550は、U,{U},X,{X}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkを鍵、(U,{U},X,{X},s)をメッセージとして検証した結果が真であること、
【0094】
【数15】

【0095】
が成り立つことを確認する。そして、いずれかの条件を満足しない場合には処理を中止する。すべての条件を満足する場合はステップS370に進む(S352)。
セッション鍵計算部570は、
【0096】
【数16】

【0097】
σ=(g^z)^v_n
σ=e(g^r,X)^y
を計算する。そして、σ’←Ext(σ),σ’←Ext(σ),σ’←Ext(σ)を計算し、セッション識別子sidを(EPK,EPK)に設定する。さらに、セッション鍵Kを、
K=F_σ’(sid)(+)F_σ’(sid)(+)F_σ’(sid)
のように求める(S570)。
【0098】
中間情報消去部580は、少なくともv_j(1≦j≦N)、y、y(1≦i≦L)、EPK、EPK、σ、σ、σ、σ’、σ’、σ’、sid、skを消去する(S580)。一般的には、セッション鍵K以外の計算の途中で使用した値をすべて消去すればよい。
【0099】
鍵交換装置500の処理に戻る。受信部545は、鍵交換装置500から、EPK=(V,{V},Y,{Y},M,ρ,vk,s)を受信する(S545)。
【0100】
属性確認部550は、属性集合Sがシェア情報生成行列Mと単射ラベリング関数ρを満たすかを確認する。そして、満たさないと判断した場合は処理を中止する。満たすと判断した場合は、ステップS560に進む(S551)。
【0101】
秘密情報取得部560は、I={i:ρ(i)∈S}となる集合IとI’={i:ρ(i)∈W}となる集合I’を求める。そして、シェア情報生成行列Mに対応する秘密情報v_nの正当なシェア集合{λBi}について、
【0102】
【数17】

【0103】
が成り立つ0以上p−1以下の整数wAiと整数w’Aiを求める(S560)。上述のように、nは鍵交換装置500と鍵交換装置500とで共有するあらかじめ定めた1以上N以下の整数であればよい。例えば、n=1とすればよい。
【0104】
属性確認部550は、V,{V},Y,{Y}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkを鍵、(V,{V},Y,{Y},s)をメッセージとして検証した結果が真であること、
【0105】
【数18】

【0106】
が成り立つことを確認する。そして、いずれかの条件を満足しない場合には処理を中止する。すべての条件を満足する場合はステップS570に進む(S552)。
セッション鍵計算部570は、
【0107】
【数19】

【0108】
σ=(g^z)^u_n
σ=e(g^r,Y)^x
を計算する。そして、σ’←Ext(σ),σ’←Ext(σ),σ’←Ext(σ)を計算し、セッション識別子sidを(EPK,EPK)に設定する。さらに、セッション鍵Kを、
K=F_σ’(sid)(+)F_σ’(sid)(+)F_σ’(sid)
のように求める(S570)。
【0109】
中間情報消去部580は、少なくともu_j(1≦j≦N)、x、x(1≦i≦L)、EPK、EPK、σ、σ、σ、σ’、σ’、σ’、sid、skを消去する(S580)。一般的には、セッション鍵K以外の計算の途中で使用した値をすべて消去すればよい。
【0110】
[確認]
最後に鍵交換装置100と鍵交換装置100が取得したセッション鍵Kが等しいことを説明する。
【0111】
【数20】

【0112】
【数21】

【0113】
σ=e(g^r,X)^y
=g^(rxy)=e(g^r,Y)^x
よって、正しくセッション鍵を共有できる。
【0114】
本発明の鍵交換システムによれば、線形秘密分散法を利用することにより、鍵抽出(長期秘密鍵の生成)を行うときには鍵生成装置が、鍵交換装置500、500の属性集合S、Sに基づき線形秘密分散法のシェア情報として長期秘密鍵(S’,T,{S})、(S’,T,{S})を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造A、Aを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定することが可能である。また、本発明のマスタ秘密鍵g^zとマスタ公開鍵(g,g^r,g^z,h[1],…,h[att’])は、属性集合とは独立なので、属性の全体集合をあらかじめ決めておく必要がない。つまり、鍵抽出時に任意の属性に基づき長期秘密鍵を発行することができる。したがって、非特許文献1と同等の効果が得られる。
【0115】
さらに、使い捨て署名、強ランダム抽出器、擬似ランダム関数を用いることにより、以下のように、ランダムオラクルを仮定しないで安全性を確保できる。鍵交換を行うユーザは、本来認証に用いる自分の属性集合S以外に、ダミー属性集合Wを用意し、生成した使い捨て署名の検証鍵の値にWを割り当てる。この時、ユーザは相手が満たすことを希望するアクセス構造Aに加えて、特定の検証鍵に対応したダミー属性集合Wが満たすようなアクセス構造を認証条件として加えて、鍵交換を行う。ダミー属性集合Wの方は、実際のユーザ同士が行う鍵交換セッションでは使われることはない。しかし、安全性証明の中で送られてきたメッセージが正しいかどうかを判定する際に、ダミー属性集合Wの方の認証条件を用いることにより、アクセス構造Aを満たす属性集合に対応する秘密鍵の知識なしで判定することができる。また、最後のセッション鍵の導出の時に、ランダムオラクルではなく、強ランダム抽出器と擬似ランダム関数を用いる。具体的には、強ランダム抽出器で共有情報の分布をならし、その値を擬似ランダム関数の鍵とすることで出力をセッション鍵とする。このように、本発明ではランダムオラクルを仮定すること無しに安全性を保つことができる。
【0116】
[プログラム、記録媒体]
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【0117】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【0118】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【0119】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0120】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。
【0121】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【0122】
本発明は、二者間でセッション鍵を共有した暗号通信に利用することができる。
【符号の説明】
【0123】
100、500 鍵交換装置 110、510 アクセス構造決定部
120、520 短期秘密鍵生成部 130、530 交換情報生成部
140、540 送信部 145、545 受信部
150、550 属性確認部 160、560 秘密情報取得部
170、570 セッション鍵計算部 180、580 中間情報消去部
190、390、590、690 記録部
300、600 鍵生成装置 310、610 マスタ鍵生成部
320、620 長期秘密鍵生成部 1000 ネットワーク

【特許請求の範囲】
【請求項1】
少なくとも鍵交換装置αと鍵交換装置βとを備え、セッション鍵を交換する鍵交換システムであって、
κは整数、pはκビットの素数、GとGは位数pの群、gは群Gの生成元、gは群Gの生成元、eはG×G→Gのように写像する双線形写像、F_σは任意長の整数を指定された鍵空間Kspaceの値σにしたがってκビットの整数に変換する擬似ランダム関数、Extは群Gの元を鍵空間Kspaceの値に変換する強ランダム抽出器、Dは整数、dは1以上D以下の整数、genは検証鍵のビット長がDであるような使い捨て署名の鍵生成のアルゴリズム、sigは検証鍵のビット長がDであるような使い捨て署名の署名生成のアルゴリズム、verは検証鍵のビット長がDであるような使い捨て署名の検証のアルゴリズム、att’は属性の全要素数を示す整数、W_Rはd番目のダミー属性を示す情報が1ビット以上のビット列Rであることを示す記号、Pは属性を示す属性要素、属性集合Sは鍵交換装置αの属性を示す属性要素Pの集合、アクセス構造Aは鍵交換装置αが鍵交換装置βに求める属性要素Pの組み合わせの集合、単射ラベリング関数ρは前記アクセス構造Aを示す関数、属性集合ρ(i)は前記アクセス構造Aに対応するi番目の集合、シェア情報生成行列Mはi行目が属性集合ρ(i)に対応するL行N列の行列、(Mはシェア情報生成行列Mのi番目の行に対応するベクトル、属性集合Sは鍵交換装置βの属性を示す属性要素Pの集合、アクセス構造Aは鍵交換装置βが鍵交換装置αに求める属性要素Pの組み合わせの集合、単射ラベリング関数ρは前記アクセス構造Aを示す関数、属性集合ρ(i)は前記アクセス構造Aに対応するi番目の集合、シェア情報生成行列Mはi行目が属性集合ρ(i)に対応するL行N列の行列、(Mはシェア情報生成行列Mのi番目の行に対応するベクトル、L、N、L、Nは整数、nは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた1以上N以下の整数、nは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた1以上N以下の整数、kは属性集合Sの要素、kは属性集合Sの要素、rとzは0以上p−1以下の整数、h[1],…,h[att’]は群Gの元、(g,g^r,g^z,h[1],…,h[att’])はマスタ公開鍵、g^zはマスタ秘密鍵、tは0以上p−1以下の整数、tは0以上p−1以下の整数、S’=g^z・g^(rt)、S’=g^z・g^(rt)、T=g^t、T=g^t、S[k]=h[k]^t、S[k]=h[k]^t、{S}はS[k]の集合、{S}はS[k]の集合、{U}はUの集合、{X}はXの集合、{V}はVの集合、{Y}はYの集合、^はべき乗を示す記号、(+)はビットごとの排他的論理和を示す記号であり、
前記鍵交換装置αは、
長期秘密鍵としてS’,T,{S}を記録する第1の記録部と、
アクセス構造Aを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkと使い捨て秘密鍵skを生成し、ダミー属性集合W={W_vkA1,…,W_vkAd,…,W_vkAD}(ただし、vkAdは使い捨て公開鍵vkのd番目のビット)を設定し、当該アクセス構造A又はすべてのダミー属性W_vkA1,…,W_vkADを満たす条件に対応する線形秘密分散法のシェア情報生成行列Mと単射ラベリング関数ρを生成する第1のアクセス構造決定部と、
1≦j≦Nについてu_jを0以上p−1以下の整数からランダムに選定してu=(u_1,…,u_N)とし、xを0以上p−1以下の整数からランダムに選定し、1≦i≦Lについてxを0以上p−1以下の整数からランダムに選定する第1の短期秘密鍵生成部と、
1≦i≦Lについてベクトルuとベクトル(Mとの内積を計算してシェアλAiとし、U=g^u_nとX=g^xと、1≦i≦LについてU=g^(rλAi)h[ρ(i)]^(−x)とX=g^xを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskを鍵、(U,{U},X,{X})をメッセージとする使い捨て署名sを生成する第1の交換情報生成部と、
EPK=(U,{U},X,{X},M,ρ,vk,s)を鍵交換装置βに送信する第1の送信部と、
鍵交換装置βから、EPK=(V,{V},Y,{Y},M,ρ,vk,s)を受信する第1の受信部と、
={i:ρ(i)∈S}となる集合IとI’={i:ρ(i)∈W}となる集合I’を求め、シェア情報生成行列Mに対応する秘密情報v_nの正当なシェア集合{λBi}について、
【数22】


が成り立つ0以上p−1以下の整数wAiと整数w’Aiを求める第1の秘密情報取得部と、
属性集合Sがシェア情報生成行列Mと単射ラベリング関数ρを満たすかを確認することと、V,{V},Y,{Y}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkを鍵、(V,{V},Y,{Y},s)をメッセージとして検証した結果が真であること、
【数23】


が成り立つことを確認する第1の属性確認部と、
【数24】


σ=(g^z)^u_n
σ=e(g^r,Y)^x
を計算し、σ’←Ext(σ),σ’←Ext(σ),σ’←Ext(σ)を計算し、セッション識別子sidを(EPK,EPK)に設定し、セッション鍵Kを、
K=F_σ’(sid)(+)F_σ’(sid)(+)F_σ’(sid)
のように求める第1のセッション鍵計算部と、
少なくともu_j(1≦j≦N)、x、x(1≦i≦L)、EPK、EPK、σ、σ、σ、σ’、σ’、σ’、sid、skを消去する第1の中間情報消去部と、
を備え、
前記鍵交換装置βは、
長期秘密鍵としてS’,T,{S}を記録する第2の記録部と、
アクセス構造Aを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkと使い捨て秘密鍵skを生成し、ダミー属性集合W={W_vkB1,…,W_vkBd,…,W_vkBD}(ただし、vkBdは使い捨て公開鍵vkのd番目のビット)を設定し、当該アクセス構造A又はすべてのダミー属性W_vkB1,…,W_vkBDを満たす条件に対応する線形秘密分散法のシェア情報生成行列Mと単射ラベリング関数ρを生成する第2のアクセス構造決定部と、
1≦j≦Nについてv_jを0以上p−1以下の整数からランダムに選定してv=(v_1,…,v_N)とし、yを0以上p−1以下の整数からランダムに選定し、1≦i≦Lについてyを0以上p−1以下の整数からランダムに選定する第2の短期秘密鍵生成部と、
1≦i≦Lについてベクトルvとベクトル(Mとの内積を計算してシェアλBiとし、V=g^v_nとY=g^yと、1≦i≦LについてV=g^(rλBi)h[ρ(i)]^(−y)とY=g^yを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskを鍵、(V,{V},Y,{Y})をメッセージとする使い捨て署名sを生成する第2の交換情報生成部と、
EPK=(V,{V},Y,{Y},M,ρ,vk,s)を鍵交換装置αに送信する第2の送信部と、
鍵交換装置αから、EPK=(U,{U},X,{X},M,ρ,vk,s)を受信する第2の受信部と、
={i:ρ(i)∈S}となる集合IとI’={i:ρ(i)∈W}となる集合I’を求め、シェア情報生成行列Mに対応する秘密情報u_nの正当なシェア集合{λAi}について、
【数25】


が成り立つ0以上p−1以下の整数wBiと整数w’Biを求める第2の秘密情報取得部と、
属性集合Sがシェア情報生成行列Mと単射ラベリング関数ρを満たすかを確認することと、U,{U},X,{X}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkを鍵、(U,{U},X,{X},s)をメッセージとして検証した結果が真であること、
【数26】


が成り立つことを確認する第2の属性確認部と、
【数27】


σ=(g^z)^v_n
σ=e(g^r,X)^y
を計算し、σ’←Ext(σ),σ’←Ext(σ),σ’←Ext(σ)を計算し、セッション識別子sidを(EPK,EPK)に設定し、セッション鍵Kを、
K=F_σ’(sid)(+)F_σ’(sid)(+)F_σ’(sid)
のように求める第2のセッション鍵計算部と、
少なくともv_j(1≦j≦N)、y、y(1≦i≦L)、EPK、EPK、σ、σ、σ、σ’、σ’、σ’、sid、skを消去する第2の中間情報消去部と、
を備える
鍵交換システム。
【請求項2】
請求項1記載の鍵交換システムであって、
さらに、マスタ鍵生成部と長期秘密鍵生成部とを有する鍵生成装置を備え、
前記r,z,h[1],…,h[att’]は、前記マスタ鍵生成部がランダムに選定したものであり、マスタ公開鍵(g,g^r,g^z,h[1],…,h[att’])とマスタ秘密鍵g^zは前記マスタ鍵生成部が生成したものであり、
前記tとtは前記長期秘密鍵生成部がランダムに選定したものであり、S’とS’、TとT、S[k]とS[k]は前記長期秘密鍵生成部が計算したものであり、
前記鍵交換装置αが記録しておく前記長期秘密鍵(S’,T,{S})は前記鍵生成装置からを取得したものであり、前記鍵交換装置βが記録しておく前記長期秘密鍵(S’,T,{S})は前記鍵生成装置から取得したものである
ことを特徴とする鍵交換システム。
【請求項3】
セッション鍵を交換する鍵交換装置であって、
κは整数、pはκビットの素数、GとGは位数pの群、gは群Gの生成元、gは群Gの生成元、eはG×G→Gのように写像する双線形写像、F_σは任意長の整数を指定された鍵空間Kspaceの値σにしたがってκビットの整数に変換する擬似ランダム関数、Extは群Gの元を鍵空間Kspaceの値に変換する強ランダム抽出器、Dは整数、dは1以上D以下の整数、genは検証鍵のビット長がDであるような使い捨て署名の鍵生成のアルゴリズム、sigは検証鍵のビット長がDであるような使い捨て署名の署名生成のアルゴリズム、verは検証鍵のビット長がDであるような使い捨て署名の検証のアルゴリズム、att’は属性の全要素数を示す整数、W_Rはd番目のダミー属性を示す情報が1ビット以上のビット列Rであることを示す記号、Pは属性を示す属性要素、属性集合Sは当該鍵交換装置の属性を示す属性要素Pの集合、アクセス構造Aは当該鍵交換装置が鍵交換する対象の鍵交換装置に求める属性要素Pの組み合わせの集合、単射ラベリング関数ρは前記アクセス構造Aを示す関数、属性集合ρ(i)は前記アクセス構造Aに対応するi番目の集合、シェア情報生成行列Mはi行目が属性集合ρ(i)に対応するL行N列の行列、(Mはシェア情報生成行列Mのi番目の行に対応するベクトル、属性集合Sは鍵交換する対象の鍵交換装置の属性を示す属性要素Pの集合、アクセス構造Aは鍵交換する対象の鍵交換装置が求める属性要素Pの組み合わせの集合、単射ラベリング関数ρは前記アクセス構造Aを示す関数、属性集合ρ(i)は前記アクセス構造Aに対応するi番目の集合、シェア情報生成行列Mはi行目が属性集合ρ(i)に対応するL行N列の行列、(Mはシェア情報生成行列Mのi番目の行に対応するベクトル、L、N、L、Nは整数、nは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた1以上N以下の整数、nは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた1以上N以下の整数、kは属性集合Sの要素、kは属性集合Sの要素、rとzは0以上p−1以下の整数、h[1],…,h[att’]は群Gの元、(g,g^r,g^z,h[1],…,h[att’])はマスタ公開鍵、g^zはマスタ秘密鍵、tは0以上p−1以下の整数、tは0以上p−1以下の整数、S’=g^z・g^(rt)、S’=g^z・g^(rt)、T=g^t、T=g^t、S[k]=h[k]^t、S[k]=h[k]^t、{S}はS[k]の集合、{S}はS[k]の集合、{U}はUの集合、{X}はXの集合、{V}はVの集合、{Y}はYの集合、^はべき乗を示す記号、(+)はビットごとの排他的論理和を示す記号であり、
アクセス構造Aを決定し、当該アクセス構造Aに対応するシェア情報生成行列Mと単射ラベリング関数ρを生成するアクセス構造決定部と、
長期秘密鍵としてS’,T,{S}を記録する記録部と、
アクセス構造Aを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkと使い捨て秘密鍵skを生成し、ダミー属性集合W={W_vkA1,…,W_vkAd,…,W_vkAD}(ただし、vkAdは使い捨て公開鍵vkのd番目のビット)を設定し、当該アクセス構造A又はすべてのダミー属性W_vkA1,…,W_vkADを満たす条件に対応する線形秘密分散法のシェア情報生成行列Mと単射ラベリング関数ρを生成するアクセス構造決定部と、
1≦j≦Nについてu_jを0以上p−1以下の整数からランダムに選定してu=(u_1,…,u_N)とし、xを0以上p−1以下の整数からランダムに選定し、1≦i≦Lについてxを0以上p−1以下の整数からランダムに選定する短期秘密鍵生成部と、
1≦i≦Lについてベクトルuとベクトル(Mとの内積を計算してシェアλAiとし、U=g^u_nとX=g^xと、1≦i≦LについてU=g^(rλAi)h[ρ(i)]^(−x)とX=g^xを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskを鍵、(U,{U},X,{X})をメッセージとする使い捨て署名sを生成する交換情報生成部と、
EPK=(U,{U},X,{X},M,ρ,vk,s)を鍵交換する対象の装置に送信する送信部と、
鍵交換する対象の装置から、EPK=(V,{V},Y,{Y},M,ρ,vk,s)を受信する受信部と、
={i:ρ(i)∈S}となる集合IとI’={i:ρ(i)∈W}となる集合I’を求め、シェア情報生成行列Mに対応する秘密情報v_nの正当なシェア集合{λBi}について、
【数28】


が成り立つ0以上p−1以下の整数wAiと整数w’Aiを求める秘密情報取得部と、
属性集合Sがシェア情報生成行列Mと単射ラベリング関数ρを満たすかを確認することと、V,{V},Y,{Y}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkを鍵、(V,{V},Y,{Y},s)をメッセージとして検証した結果が真であること、
【数29】


が成り立つことを確認する属性確認部と、
【数30】


σ=(g^z)^u_n
σ=e(g^r,Y)^x
を計算し、σ’←Ext(σ),σ’←Ext(σ),σ’←Ext(σ)を計算し、セッション識別子sidを(EPK,EPK)に設定し、セッション鍵Kを、
K=F_σ’(sid)(+)F_σ’(sid)(+)F_σ’(sid)
のように求めるセッション鍵計算部と、
少なくともu_j(1≦j≦N)、x、x(1≦i≦L)、EPK、EPK、σ、σ、σ、σ’、σ’、σ’、sid、skを消去する中間情報消去部と、
を備える鍵交換装置。
【請求項4】
セッション鍵を交換する鍵交換装置であって、
κは整数、pはκビットの素数、GとGは位数pの群、gは群Gの生成元、gは群Gの生成元、eはG×G→Gのように写像する双線形写像、F_σは任意長の整数を指定された鍵空間Kspaceの値σにしたがってκビットの整数に変換する擬似ランダム関数、Extは群Gの元を鍵空間Kspaceの値に変換する強ランダム抽出器、Dは整数、dは1以上D以下の整数、genは検証鍵のビット長がDであるような使い捨て署名の鍵生成のアルゴリズム、sigは検証鍵のビット長がDであるような使い捨て署名の署名生成のアルゴリズム、verは検証鍵のビット長がDであるような使い捨て署名の検証のアルゴリズム、att’は属性の全要素数を示す整数、W_Rはd番目のダミー属性を示す情報が1ビット以上のビット列Rであることを示す記号、Pは属性を示す属性要素、属性集合Sは鍵交換する対象の鍵交換装置の属性を示す属性要素Pの集合、アクセス構造Aは鍵交換する対象の鍵交換装置に求める属性要素Pの組み合わせの集合、単射ラベリング関数ρは前記アクセス構造Aを示す関数、属性集合ρ(i)は前記アクセス構造Aに対応するi番目の集合、シェア情報生成行列Mはi行目が属性集合ρ(i)に対応するL行N列の行列、(Mはシェア情報生成行列Mのi番目の行に対応するベクトル、属性集合Sは当該鍵交換装置の属性を示す属性要素Pの集合、アクセス構造Aは当該鍵交換装置が鍵交換する対象の鍵交換装置に求める属性要素Pの組み合わせの集合、単射ラベリング関数ρは前記アクセス構造Aを示す関数、属性集合ρ(i)は前記アクセス構造Aに対応するi番目の集合、シェア情報生成行列Mはi行目が属性集合ρ(i)に対応するL行N列の行列、(Mはシェア情報生成行列Mのi番目の行に対応するベクトル、L、N、L、Nは整数、nは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた1以上N以下の整数、nは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた1以上N以下の整数、kは属性集合Sの要素、kは属性集合Sの要素、rとzは0以上p−1以下の整数、h[1],…,h[att’]は群Gの元、(g,g^r,g^z,h[1],…,h[att’])はマスタ公開鍵、g^zはマスタ秘密鍵、tは0以上p−1以下の整数、tは0以上p−1以下の整数、S’=g^z・g^(rt)、S’=g^z・g^(rt)、T=g^t、T=g^t、S[k]=h[k]^t、S[k]=h[k]^t、{S}はS[k]の集合、{S}はS[k]の集合、{U}はUの集合、{X}はXの集合、{V}はVの集合、{Y}はYの集合、^はべき乗を示す記号、(+)はビットごとの排他的論理和を示す記号であり、
長期秘密鍵としてS’,T,{S}を記録する記録部と、
アクセス構造Aを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkと使い捨て秘密鍵skを生成し、ダミー属性集合W={W_vkB1,…,W_vkBd,…,W_vkBD}(ただし、vkBdは使い捨て公開鍵vkのd番目のビット)を設定し、当該アクセス構造A又はすべてのダミー属性W_vkB1,…,W_vkBDを満たす条件に対応する線形秘密分散法のシェア情報生成行列Mと単射ラベリング関数ρを生成するアクセス構造決定部と、
1≦j≦Nについてv_jを0以上p−1以下の整数からランダムに選定してv=(v_1,…,v_N)とし、yを0以上p−1以下の整数からランダムに選定し、1≦i≦Lについてyを0以上p−1以下の整数からランダムに選定する短期秘密鍵生成部と、
1≦i≦Lについてベクトルvとベクトル(Mとの内積を計算してシェアλBiとし、V=g^v_nとY=g^yと、1≦i≦LについてV=g^(rλBi)h[ρ(i)]^(−y)とY=g^yを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskを鍵、(V,{V},Y,{Y})をメッセージとする使い捨て署名sを生成する交換情報生成部と、
EPK=(V,{V},Y,{Y},M,ρ,vk,s)を鍵交換する対象の鍵交換装置に送信する送信部と、
鍵交換する対象の鍵交換装置から、EPK=(U,{U},X,{X},M,ρ,vk,s)を受信する受信部と、
={i:ρ(i)∈S}となる集合IとI’={i:ρ(i)∈W}となる集合I’を求め、シェア情報生成行列Mに対応する秘密情報u_nの正当なシェア集合{λAi}について、
【数31】


が成り立つ0以上p−1以下の整数wBiと整数w’Biを求める秘密情報取得部と、
属性集合Sがシェア情報生成行列Mと単射ラベリング関数ρを満たすかを確認することと、U,{U},X,{X}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkを鍵、(U,{U},X,{X},s)をメッセージとして検証した結果が真であること、
【数32】


が成り立つことを確認する属性確認部と、
【数33】


σ=(g^z)^v_n
σ=e(g^r,X)^y
を計算し、σ’←Ext(σ),σ’←Ext(σ),σ’←Ext(σ)を計算し、セッション識別子sidを(EPK,EPK)に設定し、セッション鍵Kを、
K=F_σ’(sid)(+)F_σ’(sid)(+)F_σ’(sid)
のように求めるセッション鍵計算部と、
少なくともv_j(1≦j≦N)、y、y(1≦i≦L)、EPK、EPK、σ、σ、σ、σ’、σ’、σ’、sid、skを消去する中間情報消去部と、
を備える鍵交換装置。
【請求項5】
鍵交換装置用のマスタ秘密鍵、マスタ公開鍵、長期秘密鍵を生成する鍵生成装置であって、
κは整数、pはκビットの素数、GとGは位数pの群、gは群Gの生成元、gは群Gの生成元、att’は属性の全要素数を示す整数、{S}はS[k]の集合、^はべき乗を示す記号であり、
0以上p−1以下の整数からランダムにr、zを選定し、群Gの元からランダムにh[1],…,h[att’]を選定し、マスタ公開鍵を(g,g^r,g^z,h[1],…,h[att’])、マスタ秘密鍵をg^zとするマスタ鍵生成部と、
0以上p−1以下の整数からランダムにtを選定し、S’=g^z・g^(rt)、T=g^t、属性集合Sの要素kについてS[k]=h[k]^tを計算し、長期秘密鍵として(S’,T,{S})を出力する長期秘密鍵生成部と、
を備える鍵生成装置。
【請求項6】
少なくとも鍵交換装置αと鍵交換装置βとを備える鍵交換システムを用いて、セッション鍵を交換する鍵交換方法であって、
κは整数、pはκビットの素数、GとGは位数pの群、gは群Gの生成元、gは群Gの生成元、eはG×G→Gのように写像する双線形写像、F_σは任意長の整数を指定された鍵空間Kspaceの値σにしたがってκビットの整数に変換する擬似ランダム関数、Extは群Gの元を鍵空間Kspaceの値に変換する強ランダム抽出器、Dは整数、dは1以上D以下の整数、genは検証鍵のビット長がDであるような使い捨て署名の鍵生成のアルゴリズム、sigは検証鍵のビット長がDであるような使い捨て署名の署名生成のアルゴリズム、verは検証鍵のビット長がDであるような使い捨て署名の検証のアルゴリズム、att’は属性の全要素数を示す整数、W_Rはd番目のダミー属性を示す情報が1ビット以上のビット列Rであることを示す記号、Pは属性を示す属性要素、属性集合Sは鍵交換装置αの属性を示す属性要素Pの集合、アクセス構造Aは鍵交換装置αが鍵交換装置βに求める属性要素Pの組み合わせの集合、単射ラベリング関数ρは前記アクセス構造Aを示す関数、属性集合ρ(i)は前記アクセス構造Aに対応するi番目の集合、シェア情報生成行列Mはi行目が属性集合ρ(i)に対応するL行N列の行列、(Mはシェア情報生成行列Mのi番目の行に対応するベクトル、属性集合Sは鍵交換装置βの属性を示す属性要素Pの集合、アクセス構造Aは鍵交換装置βが鍵交換装置αに求める属性要素Pの組み合わせの集合、単射ラベリング関数ρは前記アクセス構造Aを示す関数、属性集合ρ(i)は前記アクセス構造Aに対応するi番目の集合、シェア情報生成行列Mはi行目が属性集合ρ(i)に対応するL行N列の行列、(Mはシェア情報生成行列Mのi番目の行に対応するベクトル、L、N、L、Nは整数、nは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた1以上N以下の整数、nは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた1以上N以下の整数、kは属性集合Sの要素、kは属性集合Sの要素、rとzは0以上p−1以下の整数、h[1],…,h[att’]は群Gの元、(g,g^r,g^z,h[1],…,h[att’])はマスタ公開鍵、g^zはマスタ秘密鍵、tは0以上p−1以下の整数、tは0以上p−1以下の整数、S’=g^z・g^(rt)、S’=g^z・g^(rt)、T=g^t、T=g^t、S[k]=h[k]^t、S[k]=h[k]^t、{S}はS[k]の集合、{S}はS[k]の集合、{U}はUの集合、{X}はXの集合、{V}はVの集合、{Y}はYの集合、^はべき乗を示す記号、(+)はビットごとの排他的論理和を示す記号であり、
前記鍵交換装置αは、長期秘密鍵としてS’,T,{S}を記録しておき、
前記鍵交換装置βは、長期秘密鍵としてS’,T,{S}を記録しておき、
前記鍵交換装置αが、アクセス構造Aを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkと使い捨て秘密鍵skを生成し、ダミー属性集合W={W_vkA1,…,W_vkAd,…,W_vkAD}(ただし、vkAdは使い捨て公開鍵vkのd番目のビット)を設定し、当該アクセス構造A又はすべてのダミー属性W_vkA1,…,W_vkADを満たす条件に対応する線形秘密分散法のシェア情報生成行列Mと単射ラベリング関数ρを生成する第1のアクセス構造決定ステップと、
前記鍵交換装置αが、1≦j≦Nについてu_jを0以上p−1以下の整数からランダムに選定してu=(u_1,…,u_N)とし、xを0以上p−1以下の整数からランダムに選定し、1≦i≦Lについてxを0以上p−1以下の整数からランダムに選定する第1の短期秘密鍵生成ステップと、
前記鍵交換装置αが、1≦i≦Lについてベクトルuとベクトル(Mとの内積を計算してシェアλAiとし、U=g^u_nとX=g^xと、1≦i≦LについてU=g^(rλAi)h[ρ(i)]^(−x)とX=g^xを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskを鍵、(U,{U},X,{X})をメッセージとする使い捨て署名sを生成する第1の交換情報生成ステップと、
前記鍵交換装置αが、EPK=(U,{U},X,{X},M,ρ,vk,s)を前記鍵交換装置βに送信する第1の送信ステップと、
前記鍵交換装置βが、アクセス構造Aを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkと使い捨て秘密鍵skを生成し、ダミー属性集合W={W_vkB1,…,W_vkBd,…,W_vkBD}(ただし、vkBdは使い捨て公開鍵vkのd番目のビット)を設定し、当該アクセス構造A又はすべてのダミー属性W_vkB1,…,W_vkBDを満たす条件に対応する線形秘密分散法のシェア情報生成行列Mと単射ラベリング関数ρを生成する第2のアクセス構造決定ステップと、
前記鍵交換装置βが、1≦j≦Nについてv_jを0以上p−1以下の整数からランダムに選定してv=(v_1,…,v_N)とし、yを0以上p−1以下の整数からランダムに選定し、1≦i≦Lについてyを0以上p−1以下の整数からランダムに選定する第2の短期秘密鍵生成ステップと、
前記鍵交換装置βが、1≦i≦Lについてベクトルvとベクトル(Mとの内積を計算してシェアλBiとし、V=g^v_nとY=g^yと、1≦i≦LについてV=g^(rλBi)h[ρ(i)]^(−y)とY=g^yを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskを鍵、(V,{V},Y,{Y})をメッセージとする使い捨て署名sを生成する第2の交換情報生成ステップと、
前記鍵交換装置βが、EPK=(V,{V},Y,{Y},M,ρ,vk,s)を前記鍵交換装置αに送信する第2の送信ステップと、
前記鍵交換装置βが、前記鍵交換装置αから、EPK=(U,{U},X,{X},M,ρ,vk,s)を受信する第2の受信ステップと、
前記鍵交換装置βが、属性集合Sがシェア情報生成行列Mと単射ラベリング関数ρを満たすかを確認する第2の簡易属性確認ステップと、
前記鍵交換装置βが、I={i:ρ(i)∈S}となる集合IとI’={i:ρ(i)∈W}となる集合I’を求め、シェア情報生成行列Mに対応する秘密情報u_nの正当なシェア集合{λAi}について、
【数34】


が成り立つ0以上p−1以下の整数wBiと整数w’Biを求める第2の秘密情報取得ステップと、
前記鍵交換装置βが、U,{U},X,{X}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkを鍵、(U,{U},X,{X},s)をメッセージとして検証した結果が真であること、
【数35】


が成り立つことを確認する第2の属性確認ステップと、
前記鍵交換装置βが、
【数36】


σ=(g^z)^v_n
σ=e(g^r,X)^y
を計算し、σ’←Ext(σ),σ’←Ext(σ),σ’←Ext(σ)を計算し、セッション識別子sidを(EPK,EPK)に設定し、セッション鍵Kを、
K=F_σ’(sid)(+)F_σ’(sid)(+)F_σ’(sid)
のように求める第2のセッション鍵計算ステップと、
前記鍵交換装置βが、少なくともv_j(1≦j≦N)、y、y(1≦i≦L)、EPK、EPK、σ、σ、σ、σ’、σ’、σ’、sid、skを消去する第2の中間情報消去ステップと、
前記鍵交換装置αが、前記鍵交換装置βから、EPK=(V,{V},Y,{Y},M,ρ,vk,s)を受信する第1の受信ステップと、
前記鍵交換装置αが、属性集合Sがシェア情報生成行列Mと単射ラベリング関数ρを満たすかを確認する第1の簡易属性確認ステップと、
前記鍵交換装置αが、I={i:ρ(i)∈S}となる集合IとI’={i:ρ(i)∈W}となる集合I’を求め、シェア情報生成行列Mに対応する秘密情報v_nの正当なシェア集合{λBi}について、
【数37】


が成り立つ0以上p−1以下の整数wAiと整数w’Aiを求める第1の秘密情報取得ステップと、
前記鍵交換装置αが、V,{V},Y,{Y}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkを鍵、(V,{V},Y,{Y},s)をメッセージとして検証した結果が真であること、
【数38】


が成り立つことを確認する第1の属性確認ステップと、
前記鍵交換装置αが、
【数39】


σ=(g^z)^u_n
σ=e(g^r,Y)^x
を計算し、σ’←Ext(σ),σ’←Ext(σ),σ’←Ext(σ)を計算し、セッション識別子sidを(EPK,EPK)に設定し、セッション鍵Kを、
K=F_σ’(sid)(+)F_σ’(sid)(+)F_σ’(sid)
のように求める第1のセッション鍵計算ステップと、
前記鍵交換装置αが、少なくともu_j(1≦j≦N)、x、x(1≦i≦L)、EPK、EPK、σ、σ、σ、σ’、σ’、σ’、sid、skを消去する第1の中間情報消去ステップと、
を有する鍵交換方法。
【請求項7】
請求項6記載の鍵交換方法であって、
前記鍵交換システムは、さらにマスタ鍵生成手段と長期秘密鍵生成手段も備え、
前記マスタ鍵生成手段が、前記r,z,h[1],…,h[att’]をランダムに選定し、マスタ公開鍵(g,g^r,g^z,h[1],…,h[att’])とマスタ秘密鍵g^zを生成するマスタ鍵生成ステップと、
前記長期秘密鍵生成手段が、前記tとtをランダムに選定し、S’とS’、TとT、S[k]とS[k]を計算する長期秘密鍵生成ステップと、
前記鍵交換装置αが、長期秘密鍵としてS’,T,{S}を取得する第1の長期秘密鍵取得ステップと、
前記鍵交換装置βが、長期秘密鍵としてS’,T,{S}を取得する第2の長期秘密鍵取得ステップ
も有することを特徴とする鍵交換方法。
【請求項8】
請求項3または4記載の鍵交換装置、もしくは請求項5記載の鍵生成装置としてコンピュータを機能させるための鍵交換プログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate