"少なくとも鍵交換装置αと鍵交換装置βとを備え、セッション鍵を交換する鍵交換システムであって、κは整数、pはκビットの素数、GとGTは位数pの群、gは群Gの生成元、gTは群GTの生成元、eはG×G→GTのように写像する双線形写像、F_σは任意長の整数を指定された鍵空間Kspaceの値σにしたがってκビットの整数に変換する擬似ランダム関数、Extは群Gの元を鍵空間Kspaceの値に変換する強ランダム抽出器、Dは整数、dは1以上D以下の整数、genは検証鍵のビット長がDであるような使い捨て署名の鍵生成のアルゴリズム、sigは検証鍵のビット長がDであるような使い捨て署名の署名生成のアルゴリズム、verは検証鍵のビット長がDであるような使い捨て署名の検証のアルゴリズム、att’は属性の全要素数を示す整数、Wd_Rはd番目のダミー属性を示す情報が1ビット以上のビット列Rであることを示す記号、Pnは属性を示す属性要素、属性集合SAは鍵交換装置αの属性を示す属性要素Pnの集合、アクセス構造AAは鍵交換装置αが鍵交換装置βに求める属性要素Pnの組み合わせの集合、単射ラベリング関数ρAは前記アクセス構造AAを示す関数、属性集合ρAiは前記アクセス構造AAに対応するi番目の集合、シェア情報生成行列MAはi行目が属性集合ρAiに対応するLA行NA列の行列、MAiはシェア情報生成行列MAのi番目の行に対応するベクトル、属性集合SBは鍵交換装置βの属性を示す属性要素Pnの集合、アクセス構造ABは鍵交換装置βが鍵交換装置αに求める属性要素Pnの組み合わせの集合、単射ラベリング関数ρBは前記アクセス構造ABを示す関数、属性集合ρBiは前記アクセス構造ABに対応するi番目の集合、シェア情報生成行列MBはi行目が属性集合ρBiに対応するLB行NB列の行列、MBiはシェア情報生成行列MBのi番目の行に対応するベクトル、LA、NA、LB、NBは整数、nAは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた1以上NA以下の整数、nBは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた1以上NB以下の整数、kAは属性集合SAの要素、kBは属性集合SBの要素、rとzは0以上p-1以下の整数、h[1],...,h[att’]は群Gの元、g,g^r,gT^z,h[1],...,h[att’]はマスタ公開鍵、g^zはマスタ秘密鍵、tAは0以上p-1以下の整数、tBは0以上p-1以下の整数、S’A=g^zg^rtA、S’B=g^zg^rtB、TA=g^tA、TB=g^tB、SA[kA]=h[kA]^tA、SB[kB]=h[kB]^tB、{SA}はSA[kA]の集合、{SB}はSB[kB]の集合、{Ui}はUiの集合、{Xi}はXiの集合、{Vi}はViの集合、{Yi}はYiの集合、^はべき乗を示す記号、はビットごとの排他的論理和を示す記号であり、前記鍵交換装置αは、長期秘密鍵としてS’A,TA,{SA}を記録する第1の記録部と、アクセス構造AAを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkAと使い捨て秘密鍵skAを生成し、ダミー属性集合WA={W1_vkA1,...,Wd_vkAd,...,WD_vkAD}ただし、vkAdは使い捨て公開鍵vkAのd番目のビットを設定し、当該アクセス構造AA又はすべてのダミー属性W1_vkA1,...,WD_vkADを満たす条件に対応する線形秘密分散法のシェア情報生成行列MAと単射ラベリング関数ρAを生成する第1のアクセス構造決定部と、1≦j≦NAについてu_jを0以上p-1以下の整数からランダムに選定してu=u_1,...,u_NAとし、xを0以上p-1以下の整数からランダムに選定し、1≦i≦LAについてxiを0以上p-1以下の整数からランダムに選定する第1の短期秘密鍵生成部と、1≦i≦LAについてベクトルuとベクトルMAiとの内積を計算してシェアλAiとし、U=g^u_nAとX=g^xと、1≦i≦LAについてUi=g^rλAih[ρAi]^-xiとXi=g^xiを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskAを鍵、U,{Ui},X,{Xi}をメッセージとする使い捨て署名sAを生成する第1の交換情報生成部と、EPKA=U,{Ui},X,{Xi},MA,ρA,vkA,sAを鍵交換装置βに送信する第1の送信部と、鍵交換装置βから、EPKB=V,{Vi},Y,{Yi},MB,ρB,vkB,sBを受信する第1の受信部と、IA={i:ρBi∈SA}となる集合IAとI’A={i:ρBi∈WB}となる集合I’Aを求め、シェア情報生成行列MBに対応する秘密情報v_nBの正当なシェア集合{λBi}について、が成り立つ0以上p-1以下の整数wAiと整数w’Aiを求める第1の秘密情報取得部と、属性集合SAがシェア情報生成行列MBと単射ラベリング関数ρBを満たすかを確認することと、V,{Vi},Y,{Yi}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkBを鍵、V,{Vi},Y,{Yi},sBをメッセージとして検証した結果が真であること、が成り立つことを確認する第1の属性確認部と、σ1=gT^z^u_nAσ3=eg^r,Y^xを計算し、σ’1←Extσ1,σ’2←Extσ2,σ’3←Extσ3を計算し、セッション識別子sidをEPKA,EPKBに設定し、セッション鍵Kを、K=F_σ’1sidF_σ’2sidF_σ’3sidのように求める第1のセッション鍵計算部と、少なくともu_j1≦j≦NA、x、xi1≦i≦LA、EPKA、EPKB、σ1、σ2、σ3、σ’1、σ’2、σ’3、sid、skAを消去する第1の中間情報消去部と、を備え、前記鍵交換装置βは、長期秘密鍵としてS’B,TB,{SB}を記録する第2の記録部と、アクセス構造ABを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkBと使い捨て秘密鍵skBを生成し、ダミー属性集合WB={W1_vkB1,...,Wd_vkBd,...,WD_vkBD}ただし、vkBdは使い捨て公開鍵vkBのd番目のビットを設定し、当該アクセス構造AB又はすべてのダミー属性W1_vkB1,...,WD_vkBDを満たす条件に対応する線形秘密分散法のシェア情報生成行列MBと単射ラベリング関数ρBを生成する第2のアクセス構造決定部と、1≦j≦NBについてv_jを0以上p-1以下の整数からランダムに選定してv=v_1,...,v_NBとし、yを0以上p-1以下の整数からランダムに選定し、1≦i≦LBについてyiを0以上p-1以下の整数からランダムに選定する第2の短期秘密鍵生成部と、1≦i≦LBについてベクトルvとベクトルMBiとの内積を計算してシェアλBiとし、V=g^v_nBとY=g^yと、1≦i≦LBについてVi=g^rλBih[ρBi]^-yiとYi=g^yiを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskBを鍵、V,{Vi},Y,{Yi}をメッセージとする使い捨て署名sBを生成する第2の交換情報生成部と、EPKB=V,{Vi},Y,{Yi},MB,ρB,vkB,sBを鍵交換装置αに送信する第2の送信部と、鍵交換装置αから、EPKA=U,{Ui},X,{Xi},MA,ρA,vkA,sAを受信する第2の受信部と、IB={i:ρAi∈SB}となる集合IBとI’B={i:ρAi∈WA}となる集合I’Bを求め、シェア情報生成行列MAに対応する秘密情報u_nAの正当なシェア集合{λAi}について、が成り立つ0以上p-1以下の整数wBiと整数w’Biを求める第2の秘密情報取得部と、属性集合SBがシェア情報生成行列MAと単射ラベリング関数ρAを満たすかを確認することと、U,{Ui},X,{Xi}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkAを鍵、U,{Ui},X,{Xi},sAをメッセージとして検証した結果が真であること、が成り立つことを確認する第2の属性確認部と、σ2=gT^z^v_nBσ3=eg^r,X^yを計算し、σ’1←Extσ1,σ’2←Extσ2,σ’3←Extσ3を計算し、セッション識別子sidをEPKA,EPKBに設定し、セッション鍵Kを、K=F_σ’1sidF_σ’2sidF_σ’3sidのように求める第2のセッション鍵計算部と、少なくともv_j1≦j≦NB、y、yi1≦i≦LB、EPKA、EPKB、σ1、σ2、σ3、σ’1、σ’2、σ’3、sid、skBを消去する第2の中間情報消去部と、を備える鍵交換システム。請求項1記載の鍵交換システムであって、さらに、マスタ鍵生成部と長期秘密鍵生成部とを有する鍵生成装置を備え、前記r,z,h[1],...,h[att’]は、前記マスタ鍵生成部がランダムに選定したものであり、マスタ公開鍵g,g^r,gT^z,h[1],...,h[att’]とマスタ秘密鍵g^zは前記マスタ鍵生成部が生成したものであり、前記tAとtBは前記長期秘密鍵生成部がランダムに選定したものであり、S’AとS’B、TAとTB、SA[kA]とSB[kB]は前記長期秘密鍵生成部が計算したものであり、前記鍵交換装置αが記録しておく前記長期秘密鍵S’A,TA,{SA}は前記鍵生成装置からを取得したものであり、前記鍵交換装置βが記録しておく前記長期秘密鍵S’B,TB,{SB}は前記鍵生成装置から取得したものであることを特徴とする鍵交換システム。セッション鍵を交換する鍵交換装置であって、κは整数、pはκビットの素数、GとGTは位数pの群、gは群Gの生成元、gTは群GTの生成元、eはG×G→GTのように写像する双線形写像、F_σは任意長の整数を指定された鍵空間Kspaceの値σにしたがってκビットの整数に変換する擬似ランダム関数、Extは群Gの元を鍵空間Kspaceの値に変換する強ランダム抽出器、Dは整数、dは1以上D以下の整数、genは検証鍵のビット長がDであるような使い捨て署名の鍵生成のアルゴリズム、sigは検証鍵のビット長がDであるような使い捨て署名の署名生成のアルゴリズム、verは検証鍵のビット長がDであるような使い捨て署名の検証のアルゴリズム、att’は属性の全要素数を示す整数、Wd_Rはd番目のダミー属性を示す情報が1ビット以上のビット列Rであることを示す記号、Pnは属性を示す属性要素、属性集合SAは当該鍵交換装置の属性を示す属性要素Pnの集合、アクセス構造AAは当該鍵交換装置が鍵交換する対象の鍵交換装置に求める属性要素Pnの組み合わせの集合、単射ラベリング関数ρAは前記アクセス構造AAを示す関数、属性集合ρAiは前記アクセス構造AAに対応するi番目の集合、シェア情報生成行列MAはi行目が属性集合ρAiに対応するLA行NA列の行列、MAiはシェア情報生成行列MAのi番目の行に対応するベクトル、属性集合SBは鍵交換する対象の鍵交換装置の属性を示す属性要素Pnの集合、アクセス構造ABは鍵交換する対象の鍵交換装置が求める属性要素Pnの組み合わせの集合、単射ラベリング関数ρBは前記アクセス構造ABを示す関数、属性集合ρBiは前記アクセス構造ABに対応するi番目の集合、シェア情報生成行列MBはi行目が属性集合ρBiに対応するLB行NB列の行列、MBiはシェア情報生成行列MBのi番目の行に対応するベクトル、LA、NA、LB、NBは整数、nAは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた1以上NA以下の整数、nBは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた1以上NB以下の整数、kAは属性集合SAの要素、kBは属性集合SBの要素、rとzは0以上p-1以下の整数、h[1],...,h[att’]は群Gの元、g,g^r,gT^z,h[1],...,h[att’]はマスタ公開鍵、g^zはマスタ秘密鍵、tAは0以上p-1以下の整数、tBは0以上p-1以下の整数、S’A=g^zg^rtA、S’B=g^zg^rtB、TA=g^tA、TB=g^tB、SA[kA]=h[kA]^tA、SB[kB]=h[kB]^tB、{SA}はSA[kA]の集合、{SB}はSB[kB]の集合、{Ui}はUiの集合、{Xi}はXiの集合、{Vi}はViの集合、{Yi}はYiの集合、^はべき乗を示す記号、はビットごとの排他的論理和を示す記号であり、アクセス構造AAを決定し、当該アクセス構造AAに対応するシェア情報生成行列MAと単射ラベリング関数ρAを生成するアクセス構造決定部と、長期秘密鍵としてS’A,TA,{SA}を記録する記録部と、アクセス構造AAを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkAと使い捨て秘密鍵skAを生成し、ダミー属性集合WA={W1_vkA1,...,Wd_vkAd,...,WD_vkAD}ただし、vkAdは使い捨て公開鍵vkAのd番目のビットを設定し、当該アクセス構造AA又はすべてのダミー属性W1_vkA1,...,WD_vkADを満たす条件に対応する線形秘密分散法のシェア情報生成行列MAと単射ラベリング関数ρAを生成するアクセス構造決定部と、1≦j≦NAについてu_jを0以上p-1以下の整数からランダムに選定してu=u_1,...,u_NAとし、xを0以上p-1以下の整数からランダムに選定し、1≦i≦LAについてxiを0以上p-1以下の整数からランダムに選定する短期秘密鍵生成部と、1≦i≦LAについてベクトルuとベクトルMAiとの内積を計算してシェアλAiとし、U=g^u_nAとX=g^xと、1≦i≦LAについてUi=g^rλAih[ρAi]^-xiとXi=g^xiを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskAを鍵、U,{Ui},X,{Xi}をメッセージとする使い捨て署名sAを生成する交換情報生成部と、EPKA=U,{Ui},X,{Xi},MA,ρA,vkA,sAを鍵交換する対象の装置に送信する送信部と、鍵交換する対象の装置から、EPKB=V,{Vi},Y,{Yi},MB,ρB,vkB,sBを受信する受信部と、IA={i:ρBi∈SA}となる集合IAとI’A={i:ρBi∈WB}となる集合I’Aを求め、シェア情報生成行列MBに対応する秘密情報v_nBの正当なシェア集合{λBi}について、が成り立つ0以上p-1以下の整数wAiと整数w’Aiを求める秘密情報取得部と、属性集合SAがシェア情報生成行列MBと単射ラベリング関数ρBを満たすかを確認することと、V,{Vi},Y,{Yi}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkBを鍵、V,{Vi},Y,{Yi},sBをメッセージとして検証した結果が真であること、が成り立つことを確認する属性確認部と、σ1=gT^z^u_nAσ3=eg^r,Y^xを計算し、σ’1←Extσ1,σ’2←Extσ2,σ’3←Extσ3を計算し、セッション識別子sidをEPKA,EPKBに設定し、セッション鍵Kを、K=F_σ’1sidF_σ’2sidF_σ’3sidのように求めるセッション鍵計算部と、少なくともu_j1≦j≦NA、x、xi1≦i≦LA、EPKA、EPKB、σ1、σ2、σ3、σ’1、σ’2、σ’3、sid、skAを消去する中間情報消去部と、を備える鍵交換装置。セッション鍵を交換する鍵交換装置であって、κは整数、pはκビットの素数、GとGTは位数pの群、gは群Gの生成元、gTは群GTの生成元、eはG×G→GTのように写像する双線形写像、F_σは任意長の整数を指定された鍵空間Kspaceの値σにしたがってκビットの整数に変換する擬似ランダム関数、Extは群Gの元を鍵空間Kspaceの値に変換する強ランダム抽出器、Dは整数、dは1以上D以下の整数、genは検証鍵のビット長がDであるような使い捨て署名の鍵生成のアルゴリズム、sigは検証鍵のビット長がDであるような使い捨て署名の署名生成のアルゴリズム、verは検証鍵のビット長がDであるような使い捨て署名の検証のアルゴリズム、att’は属性の全要素数を示す整数、Wd_Rはd番目のダミー属性を示す情報が1ビット以上のビット列Rであることを示す記号、Pnは属性を示す属性要素、属性集合SAは鍵交換する対象の鍵交換装置の属性を示す属性要素Pnの集合、アクセス構造AAは鍵交換する対象の鍵交換装置に求める属性要素Pnの組み合わせの集合、単射ラベリング関数ρAは前記アクセス構造AAを示す関数、属性集合ρAiは前記アクセス構造AAに対応するi番目の集合、シェア情報生成行列MAはi行目が属性集合ρAiに対応するLA行NA列の行列、MAiはシェア情報生成行列MAのi番目の行に対応するベクトル、属性集合SBは当該鍵交換装置の属性を示す属性要素Pnの集合、アクセス構造ABは当該鍵交換装置が鍵交換する対象の鍵交換装置に求める属性要素Pnの組み合わせの集合、単射ラベリング関数ρBは前記アクセス構造ABを示す関数、属性集合ρBiは前記アクセス構造ABに対応するi番目の集合、シェア情報生成行列MBはi行目が属性集合ρBiに対応するLB行NB列の行列、MBiはシェア情報生成行列MBのi番目の行に対応するベクトル、LA、NA、LB、NBは整数、nAは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた1以上NA以下の整数、nBは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた1以上NB以下の整数、kAは属性集合SAの要素、kBは属性集合SBの要素、rとzは0以上p-1以下の整数、h[1],...,h[att’]は群Gの元、g,g^r,gT^z,h[1],...,h[att’]はマスタ公開鍵、g^zはマスタ秘密鍵、tAは0以上p-1以下の整数、tBは0以上p-1以下の整数、S’A=g^zg^rtA、S’B=g^zg^rtB、TA=g^tA、TB=g^tB、SA[kA]=h[kA]^tA、SB[kB]=h[kB]^tB、{SA}はSA[kA]の集合、{SB}はSB[kB]の集合、{Ui}はUiの集合、{Xi}はXiの集合、{Vi}はViの集合、{Yi}はYiの集合、^はべき乗を示す記号、はビットごとの排他的論理和を示す記号であり、長期秘密鍵としてS’B,TB,{SB}を記録する記録部と、アクセス構造ABを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkBと使い捨て秘密鍵skBを生成し、ダミー属性集合WB={W1_vkB1,...,Wd_vkBd,...,WD_vkBD}ただし、vkBdは使い捨て公開鍵vkBのd番目のビットを設定し、当該アクセス構造AB又はすべてのダミー属性W1_vkB1,...,WD_vkBDを満たす条件に対応する線形秘密分散法のシェア情報生成行列MBと単射ラベリング関数ρBを生成するアクセス構造決定部と、1≦j≦NBについてv_jを0以上p-1以下の整数からランダムに選定してv=v_1,...,v_NBとし、yを0以上p-1以下の整数からランダムに選定し、1≦i≦LBについてyiを0以上p-1以下の整数からランダムに選定する短期秘密鍵生成部と、1≦i≦LBについてベクトルvとベクトルMBiとの内積を計算してシェアλBiとし、V=g^v_nBとY=g^yと、1≦i≦LBについてVi=g^rλBih[ρBi]^-yiとYi=g^yiを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskBを鍵、V,{Vi},Y,{Yi}をメッセージとする使い捨て署名sBを生成する交換情報生成部と、EPKB=V,{Vi},Y,{Yi},MB,ρB,vkB,sBを鍵交換する対象の鍵交換装置に送信する送信部と、鍵交換する対象の鍵交換装置から、EPKA=U,{Ui},X,{Xi},MA,ρA,vkA,sAを受信する受信部と、IB={i:ρAi∈SB}となる集合IBとI’B={i:ρAi∈WA}となる集合I’Bを求め、シェア情報生成行列MAに対応する秘密情報u_nAの正当なシェア集合{λAi}について、が成り立つ0以上p-1以下の整数wBiと整数w’Biを求める秘密情報取得部と、属性集合SBがシェア情報生成行列MAと単射ラベリング関数ρAを満たすかを確認することと、U,{Ui},X,{Xi}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkAを鍵、U,{Ui},X,{Xi},sAをメッセージとして検証した結果が真であること、が成り立つことを確認する属性確認部と、σ2=gT^z^v_nBσ3=eg^r,X^yを計算し、σ’1←Extσ1,σ’2←Extσ2,σ’3←Extσ3を計算し、セッション識別子sidをEPKA,EPKBに設定し、セッション鍵Kを、K=F_σ’1sidF_σ’2sidF_σ’3sidのように求めるセッション鍵計算部と、少なくともv_j1≦j≦NB、y、yi1≦i≦LB、EPKA、EPKB、σ1、σ2、σ3、σ’1、σ’2、σ’3、sid、skBを消去する中間情報消去部と、を備える鍵交換装置。鍵交換装置用のマスタ秘密鍵、マスタ公開鍵、長期秘密鍵を生成する鍵生成装置であって、κは整数、pはκビットの素数、GとGTは位数pの群、gは群Gの生成元、gTは群GTの生成元、att’は属性の全要素数を示す整数、{SA}はSA[kA]の集合、^はべき乗を示す記号であり、0以上p-1以下の整数からランダムにr、zを選定し、群Gの元からランダムにh[1],...,h[att’]を選定し、マスタ公開鍵をg,g^r,gT^z,h[1],...,h[att’]、マスタ秘密鍵をg^zとするマスタ鍵生成部と、0以上p-1以下の整数からランダムにtAを選定し、S’A=g^zg^rtA、TA=g^tA、属性集合SAの要素kAについてSA[kA]=h[kA]^tAを計算し、長期秘密鍵としてS’A,TA,{SA}を出力する長期秘密鍵生成部と、を備える鍵生成装置。少なくとも鍵交換装置αと鍵交換装置βとを備える鍵交換システムを用いて、セッション鍵を交換する鍵交換方法であって、κは整数、pはκビットの素数、GとGTは位数pの群、gは群Gの生成元、gTは群GTの生成元、eはG×G→GTのように写像する双線形写像、F_σは任意長の整数を指定された鍵空間Kspaceの値σにしたがってκビットの整数に変換する擬似ランダム関数、Extは群Gの元を鍵空間Kspaceの値に変換する強ランダム抽出器、Dは整数、dは1以上D以下の整数、genは検証鍵のビット長がDであるような使い捨て署名の鍵生成のアルゴリズム、sigは検証鍵のビット長がDであるような使い捨て署名の署名生成のアルゴリズム、verは検証鍵のビット長がDであるような使い捨て署名の検証のアルゴリズム、att’は属性の全要素数を示す整数、Wd_Rはd番目のダミー属性を示す情報が1ビット以上のビット列Rであることを示す記号、Pnは属性を示す属性要素、属性集合SAは鍵交換装置αの属性を示す属性要素Pnの集合、アクセス構造AAは鍵交換装置αが鍵交換装置βに求める属性要素Pnの組み合わせの集合、単射ラベリング関数ρAは前記アクセス構造AAを示す関数、属性集合ρAiは前記アクセス構造AAに対応するi番目の集合、シェア情報生成行列MAはi行目が属性集合ρAiに対応するLA行NA列の行列、MAiはシェア情報生成行列MAのi番目の行に対応するベクトル、属性集合SBは鍵交換装置βの属性を示す属性要素Pnの集合、アクセス構造ABは鍵交換装置βが鍵交換装置αに求める属性要素Pnの組み合わせの集合、単射ラベリング関数ρBは前記アクセス構造ABを示す関数、属性集合ρBiは前記アクセス構造ABに対応するi番目の集合、シェア情報生成行列MBはi行目が属性集合ρBiに対応するLB行NB列の行列、MBiはシェア情報生成行列MBのi番目の行に対応するベクトル、LA、NA、LB、NBは整数、nAは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた1以上NA以下の整数、nBは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた1以上NB以下の整数、kAは属性集合SAの要素、kBは属性集合SBの要素、rとzは0以上p-1以下の整数、h[1],...,h[att’]は群Gの元、g,g^r,gT^z,h[1],...,h[att’]はマスタ公開鍵、g^zはマスタ秘密鍵、tAは0以上p-1以下の整数、tBは0以上p-1以下の整数、S’A=g^zg^rtA、S’B=g^zg^rtB、TA=g^tA、TB=g^tB、SA[kA]=h[kA]^tA、SB[kB]=h[kB]^tB、{SA}はSA[kA]の集合、{SB}はSB[kB]の集合、{Ui}はUiの集合、{Xi}はXiの集合、{Vi}はViの集合、{Yi}はYiの集合、^はべき乗を示す記号、はビットごとの排他的論理和を示す記号であり、前記鍵交換装置αは、長期秘密鍵としてS’A,TA,{SA}を記録しておき、前記鍵交換装置βは、長期秘密鍵としてS’B,TB,{SB}を記録しておき、前記鍵交換装置αが、アクセス構造AAを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkAと使い捨て秘密鍵skAを生成し、ダミー属性集合WA={W1_vkA1,...,Wd_vkAd,...,WD_vkAD}ただし、vkAdは使い捨て公開鍵vkAのd番目のビットを設定し、当該アクセス構造AA又はすべてのダミー属性W1_vkA1,...,WD_vkADを満たす条件に対応する線形秘密分散法のシェア情報生成行列MAと単射ラベリング関数ρAを生成する第1のアクセス構造決定ステップと、前記鍵交換装置αが、1≦j≦NAについてu_jを0以上p-1以下の整数からランダムに選定してu=u_1,...,u_NAとし、xを0以上p-1以下の整数からランダムに選定し、1≦i≦LAについてxiを0以上p-1以下の整数からランダムに選定する第1の短期秘密鍵生成ステップと、前記鍵交換装置αが、1≦i≦LAについてベクトルuとベクトルMAiとの内積を計算してシェアλAiとし、U=g^u_nAとX=g^xと、1≦i≦LAについてUi=g^rλAih[ρAi]^-xiとXi=g^xiを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskAを鍵、U,{Ui},X,{Xi}をメッセージとする使い捨て署名sAを生成する第1の交換情報生成ステップと、前記鍵交換装置αが、EPKA=U,{Ui},X,{Xi},MA,ρA,vkA,sAを前記鍵交換装置βに送信する第1の送信ステップと、前記鍵交換装置βが、アクセス構造ABを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkBと使い捨て秘密鍵skBを生成し、ダミー属性集合WB={W1_vkB1,...,Wd_vkBd,...,WD_vkBD}ただし、vkBdは使い捨て公開鍵vkBのd番目のビットを設定し、当該アクセス構造AB又はすべてのダミー属性W1_vkB1,...,WD_vkBDを満たす条件に対応する線形秘密分散法のシェア情報生成行列MBと単射ラベリング関数ρBを生成する第2のアクセス構造決定ステップと、前記鍵交換装置βが、1≦j≦NBについてv_jを0以上p-1以下の整数からランダムに選定してv=v_1,...,v_NBとし、yを0以上p-1以下の整数からランダムに選定し、1≦i≦LBについてyiを0以上p-1以下の整数からランダムに選定する第2の短期秘密鍵生成ステップと、前記鍵交換装置βが、1≦i≦LBについてベクトルvとベクトルMBiとの内積を計算してシェアλBiとし、V=g^v_nBとY=g^yと、1≦i≦LBについてVi=g^rλBih[ρBi]^-yiとYi=g^yiを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskBを鍵、V,{Vi},Y,{Yi}をメッセージとする使い捨て署名sBを生成する第2の交換情報生成ステップと、前記鍵交換装置βが、EPKB=V,{Vi},Y,{Yi},MB,ρB,vkB,sBを前記鍵交換装置αに送信する第2の送信ステップと、前記鍵交換装置βが、前記鍵交換装置αから、EPKA=U,{Ui},X,{Xi},MA,ρA,vkA,sAを受信する第2の受信ステップと、前記鍵交換装置βが、属性集合SBがシェア情報生成行列MAと単射ラベリング関数ρAを満たすかを確認する第2の簡易属性確認ステップと、前記鍵交換装置βが、IB={i:ρAi∈SB}となる集合IBとI’B={i:ρAi∈WA}となる集合I’Bを求め、シェア情報生成行列MAに対応する秘密情報u_nAの正当なシェア集合{λAi}について、が成り立つ0以上p-1以下の整数wBiと整数w’Biを求める第2の秘密情報取得ステップと、前記鍵交換装置βが、U,{Ui},X,{Xi}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkAを鍵、U,{Ui},X,{Xi},sAをメッセージとして検証した結果が真であること、が成り立つことを確認する第2の属性確認ステップと、前記鍵交換装置βが、σ2=gT^z^v_nBσ3=eg^r,X^yを計算し、σ’1←Extσ1,σ’2←Extσ2,σ’3←Extσ3を計算し、セッション識別子sidをEPKA,EPKBに設定し、セッション鍵Kを、K=F_σ’1sidF_σ’2sidF_σ’3sidのように求める第2のセッション鍵計算ステップと、前記鍵交換装置βが、少なくともv_j1≦j≦NB、y、yi1≦i≦LB、EPKA、EPKB、σ1、σ2、σ3、σ’1、σ’2、σ’3、sid、skBを消去する第2の中間情報消去ステップと、前記鍵交換装置αが、前記鍵交換装置βから、EPKB=V,{Vi},Y,{Yi},MB,ρB,vkB,sBを受信する第1の受信ステップと、前記鍵交換装置αが、属性集合SAがシェア情報生成行列MBと単射ラベリング関数ρBを満たすかを確認する第1の簡易属性確認ステップと、前記鍵交換装置αが、IA={i:ρBi∈SA}となる集合IAとI’A={i:ρBi∈WB}となる集合I’Aを求め、シェア情報生成行列MBに対応する秘密情報v_nBの正当なシェア集合{λBi}について、が成り立つ0以上p-1以下の整数wAiと整数w’Aiを求める第1の秘密情報取得ステップと、前記鍵交換装置αが、V,{Vi},Y,{Yi}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkBを鍵、V,{Vi},Y,{Yi},sBをメッセージとして検証した結果が真であること、が成り立つことを確認する第1の属性確認ステップと、前記鍵交換装置αが、σ1=gT^z^u_nAσ3=eg^r,Y^xを計算し、σ’1←Extσ1,σ’2←Extσ2,σ’3←Extσ3を計算し、セッション識別子sidをEPKA,EPKBに設定し、セッション鍵Kを、K=F_σ’1sidF_σ’2sidF_σ’3sidのように求める第1のセッション鍵計算ステップと、前記鍵交換装置αが、少なくともu_j1≦j≦NA、x、xi1≦i≦LA、EPKA、EPKB、σ1、σ2、σ3、σ’1、σ’2、σ’3、sid、skAを消去する第1の中間情報消去ステップと、を有する鍵交換方法。請求項6記載の鍵交換方法であって、前記鍵交換システムは、さらにマスタ鍵生成手段と長期秘密鍵生成手段も備え、前記マスタ鍵生成手段が、前記r,z,h[1],...,h[att’]をランダムに選定し、マスタ公開鍵g,g^r,gT^z,h[1],...,h[att’]とマスタ秘密鍵g^zを生成するマスタ鍵生成ステップと、前記長期秘密鍵生成手段が、前記tAとtBをランダムに選定し、S’AとS’B、TAとTB、SA[kA]とSB[kB]を計算する長期秘密鍵生成ステップと、前記鍵交換装置αが、長期秘密鍵としてS’A,TA,{SA}を取得する第1の長期秘密鍵取得ステップと、前記鍵交換装置βが、長期秘密鍵としてS’B,TB,{SB}を取得する第2の長期秘密鍵取得ステップも有することを特徴とする鍵交換方法。請求項3または4記載の鍵交換装置、もしくは請求項5記載の鍵生成装置としてコンピュータを機能させるための鍵交換プログラム。非特許文献1に対応する内容は、本願出願時には未公開の特願2010-259053に記載されており、以下のとおりである。[構成]図1に特願2010-259053の鍵交換システムの構成例を示す。鍵交換システムは、ネットワーク1000を介して接続された鍵交換装置1001,...,100Qただし、Qは2以上の整数、qは1以上Q以下の整数、AとBは1以上Q以下の異なる整数、鍵生成装置300で構成される。図2に鍵交換装置の機能構成例、図3に鍵生成装置の機能構成例を示す。鍵交換装置100qは、アクセス構造決定部110q、短期秘密鍵生成部120q、交換情報生成部130q、送信部140q、受信部145q、属性確認部150q、秘密情報取得部160q、セッション鍵計算部170q、中間情報消去部180q、記録部190qを備える。また、鍵生成装置300は、マスタ鍵生成部310、長期秘密鍵生成部320、記録部390を備える。以下の説明では、鍵交換装置100A鍵交換装置αに相当がイニシエータとして機能し、鍵交換装置100B鍵交換装置βに相当がレスポンダとして機能してセッション鍵を共有する場合について説明する。なお、κは整数、pはκビットの素数、GとGTは位数pの群、gは群Gの生成元、gTは群GTの生成元、eはG×G→GTのように写像する双線形写像、H1は任意長の整数を群Gの元に変換するハッシュ関数、H2は任意長の整数を0以上p-1以下の整数に変換するハッシュ関数、H3は任意長の整数をκビットの整数に変換するハッシュ関数、Pnは属性を示す属性要素、属性集合SAは鍵交換装置100Aの属性を示す属性要素Pnの組み合わせの集合、属性集合SBは鍵交換装置100Bの属性を示す属性要素Pnの組み合わせの集合、NMAXはあらかじめ定めた整数、jとnは1以上NMAX以下の整数、kAは属性集合SAの要素、kBは属性集合SBの要素、{TA}はTA[1],...,TA[NMAX]の集合、{TB}はTB[1],...,TB[NMAX]の集合、{SA}はSA[1],...,SA[NMAX]の集合、{SB}はSB[1],...,SB[NMAX]の集合、{U}はUi,jの集合、{V}はVi,jの集合である。[鍵生成、鍵抽出]図4に、マスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す。なお、長期秘密鍵生成の処理が鍵抽出に相当する。鍵生成装置300のマスタ鍵生成部310は、0以上p-1以下の整数からランダムにrとzを選定する。そして、マスタ公開鍵をg,g^r,gT^z、マスタ秘密鍵をg^zとして記録部390に記録し、マスタ公開鍵g,g^r,gT^zを公開するS310。鍵交換装置100Aと鍵交換装置100Bは、それぞれマスタ公開鍵をg,g^r,gT^zを受信し、記録部190Aと記録部190Bに記録する。長期秘密鍵生成部320は、0以上p-1以下の整数からランダムにtA[1],...,tA[NMAX]を選び、S’A=g^zg^rtA[1]を計算し、1以上NMAX以下のjについてTA[j]=g^tA[1]を計算し、属性集合SAの要素kAについてを計算し、長期秘密鍵としてS’A,{TA},{SA}を鍵交換装置100Aに送信するS320A。鍵交換装置100Aは、長期秘密鍵S’A,{TA},{SA}を受信し、記録部190Aに記録するS192A。さらに、長期秘密鍵生成部320は、0以上p-1以下の整数からランダムにtB[1],...,tB[NMAX]を選び、S’B=g^zg^rtB[1]を計算し、1以上NMAX以下のjについてTB[j]=g^tB[1]を計算し、属性集合SBの要素kBについてを計算し、長期秘密鍵としてS’B,{TB},{SB}を鍵交換装置100Bに送信するS320B。鍵交換装置100Bは、長期秘密鍵S’B,{TB},{SB}を受信し、記録部190Bに記録するS192B。なお、あらかじめ鍵交換装置100Aの記録部190Aにマスタ公開鍵g,g^r,gT^zと長期秘密鍵S’A,{TA},{SA}とを記録させ、鍵交換装置100Bの記録部190Bにマスタ公開鍵g,g^r,gT^zと長期秘密鍵S’B,{TB},{SB}とを記録させておけば、ネットワーク1000を介して接続された鍵交換装置100Aと鍵交換装置100Bだけで最低限の鍵交換システムが構成できる。[鍵交換]図5にセッション鍵を共有する鍵交換の処理のフローの例を示す。この例は、鍵交換装置100A鍵交換装置αに相当がイニシエータとして機能し、鍵交換装置100B鍵交換装置βに相当がレスポンダとして機能する場合を示している。鍵交換装置100Aは、アクセス構造決定部110A、短期秘密鍵生成部120A、交換情報生成部130A、送信部140A、受信部145A、属性確認部150A、秘密情報取得部160A、セッション鍵計算部170A、中間情報消去部180Aを備える。鍵交換装置100Bは、アクセス構造決定部110B、短期秘密鍵生成部120B、交換情報生成部130B、送信部140B、受信部145B、属性確認部150B、秘密情報取得部160B、セッション鍵計算部170B、中間情報消去部180Bを備える。アクセス構造決定部110Aは、アクセス構造AAを決定し、当該アクセス構造AAに対応するシェア情報生成行列MAと単射ラベリング関数ρAを生成するS110A。短期秘密鍵生成部120Aは、1≦j≦NAについて、u~jを0以上p-1以下の整数からランダムに選定するS120A。交換情報生成部130Aは、1≦j≦NAについて、uj=H2S’A,{TA},{SA},u~j、X=g^u1、1≦i≦LAと1≦j≦NAについて、Ui,j=g^rMAi,jujH1j,ρAi^-u1、1≦i≦LAとNA1≦j≦NMAXについて、Ui,j=H1j,ρAi^-u1を計算する130A。送信部140Aは、X、{U}、MA、ρAを鍵交換装置100Bに送信するS140A。中間情報消去部180Aは、uj1≦j≦NAを消去するS180A。受信部145Bは、鍵交換装置100Aから、X、{U}、MA、ρAを受信するS145B。属性確認部150Bは、属性集合SBがシェア情報生成行列MAと単射ラベリング関数ρAを満たすか、Xと{U}が群Gの要素かを確認するS150B。アクセス構造決定部110Bは、アクセス構造ABを決定し、当該アクセス構造ABに対応するシェア情報生成行列MBと単射ラベリング関数ρBを生成するS110B。短期秘密鍵生成部120Bは、1≦j≦NBについて、v~jを0以上p-1以下の整数からランダムに選定するS120B。交換情報生成部130Bは、1≦j≦NBについて、vj=H2S’B,{TB},{SB},v~j、Y=g^v1、1≦i≦LBと1≦j≦NBについて、Vi,j=g^rMBi,jvjH1j,ρBi^-v1、1≦i≦LBとNB1≦j≦NMAXについて、Vi,j=H1j,ρBi^-v1を計算するS130B。送信部140Bは、Y、{V}、MB、ρBを鍵交換装置100Aに送信するS140B。秘密情報取得部160Bは、IB={k:ρAk∈SB}となる集合IBを求め、鍵交換装置100Aが生成した秘密情報u1に対する正当なシェア情報集合{MAi,juj}についてが成り立つ0以上p-1以下の整数wB[k]ただし、kは集合IBの要素を求めるS160B。セッション鍵計算部170Bは、σ2=gT^z^v1σ3=X^v1を計算し、セッション鍵Kを、K=H3σ1,σ2,σ3,X,{U},MA,ρA,Y,{V},MB,ρBのように求めるS170B。中間情報消去部180Bは、vj1≦j≦NBを消去するS180B。受信部145Aは、鍵交換装置100Bから、Y、{V}、MB、ρBを受信するS145A。属性確認部150Aは、属性集合SAがシェア情報生成行列MBと単射ラベリング関数ρBを満たすか、Yと{V}が群Gの要素かを確認するS150A。秘密情報取得部160Aは、IA={k:ρBk∈SA}となる集合IAを求め、鍵交換装置100Bが生成した秘密情報v1に対する正当なシェア情報集合{MBi,jvj}についてが成り立つ0以上p-1以下の整数wA[k]ただし、kは集合IAの要素を求めるS160A。セッション鍵計算部170Aは、σ1=gT^z^H2S’A,{TA},{SA},u~1σ3=Y^H2S’A,{TA},{SA},u~1を計算し、セッション鍵Kを、K=H3σ1,σ2,σ3,X,{U},MA,ρA,Y,{V},MB,ρBのように求める。この鍵交換システムは、上述のような処理によって鍵交換時にアクセスポリシーを指定でき、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができる。しかしながら、安全性を保証するためには、ハッシュ関数が理想的に安全ランダムオラクルでなければならないという問題がある。ランダムオラクルは現実のハッシュ関数を用いては実現できないことが知られている。よって、ランダムオラクルを仮定せずに安全性証明が付く方式が望ましい。本発明は、非特許文献1の鍵交換技術と同じように鍵交換時にアクセスポリシーを指定できることと、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができることを確保しながら、ランダムオラクルを仮定しない安全な鍵交換技術を提供することを目的とする。本発明の鍵交換システムは、少なくとも鍵交換装置αと鍵交換装置βとを備える。ここで、κは整数、pはκビットの素数、GとGTは位数pの群、gは群Gの生成元、gTは群GTの生成元、eはG×G→GTのように写像する双線形写像、F_σは任意長の整数を指定された鍵空間Kspaceの値σにしたがってκビットの整数に変換する擬似ランダム関数、Extは群Gの元を鍵空間Kspaceの値に変換する強ランダム抽出器、Dは整数、dは1以上D以下の整数、genは検証鍵のビット長がDであるような使い捨て署名の鍵生成のアルゴリズム、sigは検証鍵のビット長がDであるような使い捨て署名の署名生成のアルゴリズム、verは検証鍵のビット長がDであるような使い捨て署名の検証のアルゴリズム、att’は属性の全要素数を示す整数、Wd_Rはd番目のダミー属性を示す情報が1ビット以上のビット列Rであることを示す記号、Pnは属性を示す属性要素、属性集合SAは鍵交換装置αの属性を示す属性要素Pnの集合、アクセス構造AAは鍵交換装置αが鍵交換装置βに求める属性要素Pnの組み合わせの集合、単射ラベリング関数ρAは前記アクセス構造AAを示す関数、属性集合ρAiは前記アクセス構造AAに対応するi番目の集合、シェア情報生成行列MAはi行目が属性集合ρAiに対応するLA行NA列の行列、MAiはシェア情報生成行列MAのi番目の行に対応するベクトル、属性集合SBは鍵交換装置βの属性を示す属性要素Pnの集合、アクセス構造ABは鍵交換装置βが鍵交換装置αに求める属性要素Pnの組み合わせの集合、単射ラベリング関数ρBは前記アクセス構造ABを示す関数、属性集合ρBiは前記アクセス構造ABに対応するi番目の集合、シェア情報生成行列MBはi行目が属性集合ρBiに対応するLB行NB列の行列、MBiはシェア情報生成行列MBのi番目の行に対応するベクトル、LA、NA、LB、NBは整数、nAは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた1以上NA以下の整数、nBは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた1以上NB以下の整数、kAは属性集合SAの要素、kBは属性集合SBの要素、rとzは0以上p-1以下の整数、h[1],...,h[att’]は群Gの元、g,g^r,gT^z,h[1],...,h[att’]はマスタ公開鍵、g^zはマスタ秘密鍵、tAは0以上p-1以下の整数、tBは0以上p-1以下の整数、S’A=g^zg^rtA、S’B=g^zg^rtB、TA=g^tA、TB=g^tB、SA[kA]=h[kA]^tA、SB[kB]=h[kB]^tB、{SA}はSA[kA]の集合、{SB}はSB[kB]の集合、{Ui}はUiの集合、{Xi}はXiの集合、{Vi}はViの集合、{Yi}はYiの集合、^はべき乗を示す記号、はビットごとの排他的論理和を示す記号とする。鍵交換装置αは、第1の記録部、第1のアクセス構造決定部、第1の短期秘密鍵生成部、第1の交換情報生成部、第1の送信部、第1の受信部、第1の秘密情報取得部、第1の属性確認部、第1のセッション鍵計算部、第1の中間情報消去部を備える。鍵交換装置βは、第2の記録部、第2のアクセス構造決定部、第2の短期秘密鍵生成部、第2の交換情報生成部、第2の送信部、第2の受信部、第2の秘密情報取得部、第2の属性確認部、第2のセッション鍵計算部、第2の中間情報消去部を備える。第1の記録部は、長期秘密鍵としてS’A,TA,{SA}を記録する。第2の記録部は、長期秘密鍵としてS’B,TB,{SB}を記録する。第1のアクセス構造決定部は、アクセス構造AAを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkAと使い捨て秘密鍵skAを生成し、ダミー属性集合WA={W1_vkA1,...,Wd_vkAd,...,WD_vkAD}ただし、vkAdは使い捨て公開鍵vkAのd番目のビットを設定する。そして、当該アクセス構造AA又はすべてのダミー属性W1_vkA1,...,WD_vkADを満たす条件に対応する線形秘密分散法のシェア情報生成行列MAと単射ラベリング関数ρAを生成する。第1の短期秘密鍵生成部は、1≦j≦NAについてu_jを0以上p-1以下の整数からランダムに選定してu=u_1,...,u_NAとし、xを0以上p-1以下の整数からランダムに選定し、1≦i≦LAについてxiを0以上p-1以下の整数からランダムに選定する。第1の交換情報生成部は、1≦i≦LAについてベクトルuとベクトルMAiとの内積を計算してシェアλAiとする。そして、U=g^u_nAとX=g^xと、1≦i≦LAについてUi=g^rλAih[ρAi]^-xiとXi=g^xiを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskAを鍵、U,{Ui},X,{Xi}をメッセージとする使い捨て署名sAを生成する。第1の送信部は、EPKA=U,{Ui},X,{Xi},MA,ρA,vkA,sAを鍵交換装置βに送信する。第1の受信部は、鍵交換装置βから、EPKB=V,{Vi},Y,{Yi},MB,ρB,vkB,sBを受信する。第1の秘密情報取得部は、IA={i:ρBi∈SA}となる集合IAとI’A={i:ρBi∈WB}となる集合I’Aを求め、シェア情報生成行列MBに対応する秘密情報v_nBの正当なシェア集合{λBi}について、が成り立つ0以上p-1以下の整数wAiと整数w’Aiを求める。第1の属性確認部は、属性集合SAがシェア情報生成行列MBと単射ラベリング関数ρBを満たすかを確認することと、V,{Vi},Y,{Yi}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkBを鍵、V,{Vi},Y,{Yi},sBをメッセージとして検証した結果が真であること、が成り立つことを確認する。第1のセッション鍵計算部は、σ1=gT^z^u_nAσ3=eg^r,Y^xを計算し、σ’1←Extσ1,σ’2←Extσ2,σ’3←Extσ3を計算し、セッション識別子sidをEPKA,EPKBに設定し、セッション鍵Kを、K=F_σ’1sidF_σ’2sidF_σ’3sidのように求める。第1の中間情報消去部は、少なくともu_j1≦j≦NA、x、xi1≦i≦LA、EPKA、EPKB、σ1、σ2、σ3、σ’1、σ’2、σ’3、sid、skAを消去する。第2のアクセス構造決定部は、アクセス構造ABを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkBと使い捨て秘密鍵skBを生成し、ダミー属性集合WB={W1_vkB1,...,Wd_vkBd,...,WD_vkBD}ただし、vkBdは使い捨て公開鍵vkBのd番目のビットを設定する。そして、当該アクセス構造AB又はすべてのダミー属性W1_vkB1,...,WD_vkBDを満たす条件に対応する線形秘密分散法のシェア情報生成行列MBと単射ラベリング関数ρBを生成する。第2の短期秘密鍵生成部は、1≦j≦NBについてv_jを0以上p-1以下の整数からランダムに選定してv=v_1,...,v_NBとし、yを0以上p-1以下の整数からランダムに選定し、1≦i≦LBについてyiを0以上p-1以下の整数からランダムに選定する。第2の交換情報生成部は、1≦i≦LBについてベクトルvとベクトルMBiとの内積を計算してシェアλBiとする。そして、V=g^v_nBとY=g^yと、1≦i≦LBについてVi=g^rλBih[ρBi]^-yiとYi=g^yiを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskBを鍵、V,{Vi},Y,{Yi}をメッセージとする使い捨て署名sBを生成する。第2の送信部は、EPKB=V,{Vi},Y,{Yi},MB,ρB,vkB,sBを鍵交換装置αに送信する。第2の受信部は、鍵交換装置αから、EPKA=U,{Ui},X,{Xi},MA,ρA,vkA,sAを受信する。第2の秘密情報取得部は、IB={i:ρAi∈SB}となる集合IBとI’B={i:ρAi∈WA}となる集合I’Bを求め、シェア情報生成行列MAに対応する秘密情報u_nAの正当なシェア集合{λAi}について、が成り立つ0以上p-1以下の整数wBiと整数w’Biを求める。第2の属性確認部は、属性集合SBがシェア情報生成行列MAと単射ラベリング関数ρAを満たすかを確認することと、U,{Ui},X,{Xi}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkAを鍵、U,{Ui},X,{Xi},sAをメッセージとして検証した結果が真であること、が成り立つことを確認する。第2のセッション鍵計算部は、σ2=gT^z^v_nBσ3=eg^r,X^yを計算し、σ’1←Extσ1,σ’2←Extσ2,σ’3←Extσ3を計算し、セッション識別子sidをEPKA,EPKBに設定し、セッション鍵Kを、K=F_σ’1sidF_σ’2sidF_σ’3sidのように求める。第2の中間情報消去部は、少なくともv_j1≦j≦NB、y、yi1≦i≦LB、EPKA、EPKB、σ1、σ2、σ3、σ’1、σ’2、σ’3、sid、skBを消去する。なお、本発明の鍵交換システムは、さらに、マスタ鍵生成部と長期秘密鍵生成部とを有する鍵生成装置を備えてもよい。この場合は、マスタ鍵生成部が、r,z,h[1],...,h[att’]をランダムに選定し、マスタ公開鍵g,g^r,gT^z,h[1],...,h[att’]とマスタ秘密鍵g^zを生成すればよい。また、長期秘密鍵生成部がtAとtBをランダムに選定し、S’AとS’B、TAとTB、SA[kA]とSB[kB]を計算すればよい。本発明の鍵交換システムによれば、線形秘密分散法を利用することにより、鍵抽出長期秘密鍵の生成を行うときには鍵生成装置が、鍵交換装置α、βの属性集合SA、SBに基づき線形秘密分散法のシェア情報として長期秘密鍵S’A,TA,{SA}、S’B,TB,{SB}を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造AA、ABを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定することが可能である。また、本発明のマスタ秘密鍵g^zとマスタ公開鍵g,g^r,gT^z,h[1],...,h[att’]は、属性集合とは独立なので、属性の全体集合をあらかじめ決めておく必要がない。つまり、鍵抽出時に任意の属性に基づき長期秘密鍵を発行することができる。したがって、非特許文献1と同等の効果が得られる。さらに、使い捨て署名、強ランダム抽出器、擬似ランダム関数を用いることにより、以下のように、ランダムオラクルを仮定しないで安全性を確保できる。鍵交換を行うユーザは、本来認証に用いる自分の属性集合S以外に、ダミー属性集合Wを用意し、生成した使い捨て署名の検証鍵の値にWを割り当てる。この時、ユーザは相手が満たすことを希望するアクセス構造Aに加えて、特定の検証鍵に対応したダミー属性集合Wが満たすようなアクセス構造を認証条件として加えて、鍵交換を行う。ダミー属性集合Wの方は、実際のユーザ同士が行う鍵交換セッションでは使われることはない。しかし、安全性証明の中で送られてきたメッセージが正しいかどうかを判定する際に、ダミー属性集合Wの方の認証条件を用いることにより、アクセス構造Aを満たす属性集合に対応する秘密鍵の知識なしで判定することができる。また、最後のセッション鍵の導出の時に、ランダムオラクルではなく、強ランダム抽出器と擬似ランダム関数を用いる。具体的には、強ランダム抽出器で共有情報の分布をならし、その値を擬似ランダム関数の鍵とすることで出力をセッション鍵とする。このように、本発明ではランダムオラクルを仮定すること無しに安全性を保つことができる。以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。[準備]本発明の鍵交換システムについて説明する前に、本発明を理解する上で必要な理論について説明する。本発明では、アクセスポリシーを次のようなアクセス構造として表すものとする。まず、{P1,P2,...,Pn,...,PN}を属性集合とする。ただし、Nは整数、nは1以上N以下の整数である。Pnは、例えば、性別が男性である。や○○会社の社員である。などの鍵生成装置の利用者ユーザの属性を示している。なお、以下の説明では、鍵生成装置の利用者の属性を単に鍵生成装置の属性と表現する。アクセス構造は{P1,P2,...,PN}の空でない部分集合のべき集合Aとして表わす。すなわち、A⊆2^{P1,P2,...,PN}\{φ}ただし、^はべき乗を示す記号、φは空集合を示す記号、\{φ}は空集合を除くことを示す記号に属する集合を許可集合、属さない集合を不許可集合とよぶ。本発明では、上記のアクセス構造に基づきアクセスコントロールを行うために次のように線形秘密分散法を用いる。各属性集合に対応するシェア情報は0以上p-1以下の整数の集合ZP上のベクトルとして表される。シェア情報を生成する行列としてL行N列のシェア情報生成行列Mを次のように用意する。i=1,...,Lについて、属性ラベリング関数ρを用いてシェア情報生成行列Mのi行目を属性ρiに対応させる。属性ラベリング関数ρは、iを特定すると属性ρiが決まる関数である。また、属性ρiに対応させるとは、例えば、属性ρ1がP1∧P2∧P3であれば、1,1,1,0,0,...,0のようにシェア情報生成行列Mの1行目を設定し、属性ρ2がP1∧PNであれば、1,0,0,...,0,1のようにシェア情報生成行列Mの2行目を設定するように、属性ρiと対応させてi行目を決めることである。なお、上記の例では、アンド条件に含まれる属性Pnに対応する要素を1とし、含まれない属性Pnに対応する要素を0としたが、これに限る必要はない。異なる条件に対応する行が同じ行にならないように対応付けされていればよいので、属性ラベリング関数ρは単射性を有する範囲で他の対応でもよい。次に、0以上p-1以下の整数からr1,...,rNをランダムに選び、ベクトルv=r1,...,rNTを生成する。ただし、Tは転置を示す記号である。また、あらかじめ定めておいたn番目の要素rnを秘密情報とする。なお、鍵交換したい装置同士の場合、秘密情報として共有する情報が同じであれば任意の情報でかまわないので、ランダムに選んだ整数の何番目を秘密情報にするかをあらかじめ決めておけばよい。この時、Mは秘密情報rnのL個のシェア情報のベクトルとなる。属性集合ρiにシェア情報Mviを割り当てる。ただし、MviはベクトルMvのi番目の成分を示している。このようにシェア情報生成行列Mと秘密情報を含む列ベクトルvを用いると、線形秘密分散法の線形復元性を利用できる。ここで、線形復元性について説明する。あるアクセス構造Aを考え、属性集合SをS∈Aの任意の許可集合とし、I⊂{1,2,...,L}をI={i:ρi∈S}と定義する。このとき、{λi}がrnの正しいシェア情報の集合の場合、となるような0以上p-1以下の整数の集合{wi}が存在する。このような集合{wi}はMのサイズの多項式時間で見つけられることが知られている。一方、{λi}がrnの正しいシェア情報の集合でない場合、集合{wi}のすべての要素を求めることができない。本発明では、上述のようにシェア情報生成行列Mと秘密情報を含む列ベクトルvを用いることで、線形秘密分散法の線形復元性を利用してセッション鍵を交換する。[構成]図6に本発明の鍵交換システムの構成例を示す。本発明の鍵交換システムは、ネットワーク1000を介して接続された鍵交換装置5001,...,500Qただし、Qは2以上の整数、qは1以上Q以下の整数、AとBは1以上Q以下の異なる整数、鍵生成装置600で構成される。図7に本発明の鍵交換装置の機能構成例、図8に本発明の鍵生成装置の機能構成例を示す。鍵交換装置500qは、アクセス構造決定部510q、短期秘密鍵生成部520q、交換情報生成部530q、送信部540q、受信部545q、属性確認部550q、秘密情報取得部560q、セッション鍵計算部570q、中間情報消去部580q、記録部590qを備える。また、鍵生成装置600は、マスタ鍵生成部610、長期秘密鍵生成部620、記録部690を備える。以下の説明では、鍵交換装置500A鍵交換装置αに相当がイニシエータとして機能し、鍵交換装置500B鍵交換装置βに相当がレスポンダとして機能してセッション鍵を共有する場合について説明する。なお、以下の説明では、κは整数、pはκビットの素数、GとGTは位数pの群、gは群Gの生成元、gTは群GTの生成元、eはG×G→GTのように写像する双線形写像、F_σは任意長の整数を指定された鍵空間Kspaceの値σにしたがってκビットの整数に変換する擬似ランダム関数、Extは群Gの元を鍵空間Kspaceの値に変換する強ランダム抽出器、Dは整数ダミー属性の要素数、dは1以上D以下の整数、genは検証鍵のビット長がDであるような使い捨て署名の鍵生成のアルゴリズム、sigは検証鍵のビット長がDであるような使い捨て署名の署名生成のアルゴリズム、verは検証鍵のビット長がDであるような使い捨て署名の検証のアルゴリズム、att’は属性の全要素数を示す整数実際の属性とダミー属性の両方を合わせた全要素数、Wd_Rはd番目のダミー属性を示す情報が1ビット以上のビット列Rであることを示す記号本明細書では、1ビットの場合もビット列と呼ぶことにする、Pnは属性を示す属性要素、属性集合SAは鍵交換装置500Aの属性を示す属性要素Pnの集合、アクセス構造AAは鍵交換装置500Aが鍵交換装置500Bに求める属性要素Pnの組み合わせの集合、単射ラベリング関数ρAはアクセス構造AAを示す関数、属性集合ρAiはアクセス構造AAに対応するi番目の集合、シェア情報生成行列MAはi行目が属性集合ρAiに対応するLA行NA列の行列、MAiはシェア情報生成行列MAのi番目の行に対応するベクトル、属性集合SBは鍵交換装置500Bの属性を示す属性要素Pnの集合、アクセス構造ABは鍵交換装置500Bが鍵交換装置500Aに求める属性要素Pnの組み合わせの集合、単射ラベリング関数ρBはアクセス構造ABを示す関数、属性集合ρBiはアクセス構造ABに対応するi番目の集合、シェア情報生成行列MBはi行目が属性集合ρBiに対応するLB行NB列の行列、MBiはシェア情報生成行列MBのi番目の行に対応するベクトル、LA、NA、LB、NBは整数、nAは鍵交換装置500Aと鍵交換装置500Bとで共有するあらかじめ定めた1以上NA以下の整数、nBは鍵交換装置500Aと鍵交換装置500Bとで共有するあらかじめ定めた1以上NB以下の整数、kAは属性集合SAの要素、kBは属性集合SBの要素、rとzは0以上p-1以下の整数、tBは0以上p-1以下の整数、h[1],...,h[att’]は群Gの元、{SA}はSA[kA]の集合、{SB}はSB[kB]の集合、{Ui}はUiの集合、{Xi}はXiの集合、{Vi}はViの集合、{Yi}はYiの集合、^はべき乗を示す記号、はビットごとの排他的論理和を示す記号とする。[鍵生成、鍵抽出]図9に、マスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す。なお、長期秘密鍵生成の処理が鍵抽出に相当する。鍵生成装置600のマスタ鍵生成部610は、0以上p-1以下の整数からランダムにr、zを選定し、群Gの元からランダムにh[1],...,h[att’]を選定する。そして、マスタ公開鍵をg,g^r,gT^z,h[1],...,h[att’]、マスタ秘密鍵をg^zとして記録部390に記録し、マスタ公開鍵g,g^r,gT^z,h[1],...,h[att’]を公開するS610。鍵交換装置500Aと鍵交換装置500Bは、それぞれマスタ公開鍵g,g^r,gT^z,h[1],...,h[att’]を受信し、記録部590Aと記録部590Bに記録するS591,S592。長期秘密鍵生成部620は、0以上p-1以下の整数からランダムにtAを選定し、S’A=g^zg^rtA、TA=g^tA、属性集合SAの要素kAについてSA[kA]=h[kA]^tAを計算し、長期秘密鍵としてS’A,TA,{SA}を鍵交換装置500Aに送信するS620A。鍵交換装置500Aは、長期秘密鍵S’A,TA,{SA}を受信し、記録部590Aに記録するS592A。さらに、長期秘密鍵生成部620は、0以上p-1以下の整数からランダムにtBを選定し、S’B=g^zg^rtB、TB=g^tB、属性集合SBの要素kBについてSB[kB]=h[kB]^tBを計算し、長期秘密鍵としてS’B,TB,{SB}を鍵交換装置500Bに送信するS620B。鍵交換装置500Bは、長期秘密鍵S’B,TB,{SB}を受信し、記録部590Bに記録するS592B。なお、あらかじめ鍵交換装置500Aの記録部590Aにマスタ公開鍵g,g^r,gT^z,h[1],...,h[att’]と長期秘密鍵S’A,TA,{SA}とを記録させ、鍵交換装置500Bの記録部590Bにマスタ公開鍵g,g^r,gT^z,h[1],...,h[att’]と長期秘密鍵S’B,TB,{SB}とを記録させておけば、ネットワーク1000を介して接続された鍵交換装置500Aと鍵交換装置500Bだけで最低限の鍵交換システムが構成できる。[鍵交換]図10にセッション鍵を共有する鍵交換の処理のフローの例を示す。この例は、鍵交換装置500A鍵交換装置αに相当がイニシエータとして機能し、鍵交換装置500B鍵交換装置βに相当がレスポンダとして機能する場合を示している。鍵交換装置500Aは、アクセス構造決定部510A第1のアクセス構造決定部、短期秘密鍵生成部520A第1の短期秘密鍵生成部、交換情報生成部530A第1の交換情報生成部、送信部540A第1の送信部、受信部545A第1の受信部、属性確認部550A第1の属性確認部、秘密情報取得部560A第1の秘密情報取得部、セッション鍵計算部570A第1のセッション鍵計算部、中間情報消去部580A第1の中間情報消去部、記録部590A第1の記録部を備える。鍵交換装置500Bは、アクセス構造決定部510B第2のアクセス構造決定部、短期秘密鍵生成部520B第2の短期秘密鍵生成部、交換情報生成部530B第2の交換情報生成部、送信部540B第2の送信部、受信部545B第2の受信部、属性確認部550B第2の属性確認部、秘密情報取得部560B第2の秘密情報取得部、セッション鍵計算部570B第2のセッション鍵計算部、中間情報消去部580B第2の中間情報消去部、記録部590B第2の記録部を備える。鍵交換装置500Aでは、記録部590Aが長期秘密鍵としてS’A,TA,{SA}を記録している。アクセス構造決定部510Aは、アクセス構造AAを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkAと使い捨て秘密鍵skAを生成し、ダミー属性集合WA={W1_vkA1,...,Wd_vkAd,...,WD_vkAD}ただし、vkAdは使い捨て公開鍵vkAのd番目のビットを設定する。そして、アクセス構造AA又はすべてのダミー属性W1_vkA1,...,WD_vkADを満たす条件に対応する線形秘密分散法のシェア情報生成行列MAと単射ラベリング関数ρAを生成するS510A。短期秘密鍵生成部520Aは、1≦j≦NAについてu_jを0以上p-1以下の整数からランダムに選定してu=u_1,...,u_NAとし、xを0以上p-1以下の整数からランダムに選定し、1≦i≦LAについてxiを0以上p-1以下の整数からランダムに選定するS520A。交換情報生成部530Aは、1≦i≦LAについてベクトルuとベクトルMAiとの内積を計算してシェアλAiとする。そして、U=g^u_nAX=g^xUi=g^rλAih[ρAi]^-xiただし、1≦i≦LAXi=g^xiただし、1≦i≦LAを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskAを鍵、U,{Ui},X,{Xi}をメッセージとする使い捨て署名sAを生成するS530A。第1の送信部540Aは、EPKA=U,{Ui},X,{Xi},MA,ρA,vkA,sAを鍵交換装置500Bに送信するS540A。一方、鍵交換装置500Bでは、記録部590Bが長期秘密鍵としてS’B,TB,{SB}を記録している。そして、アクセス構造決定部510Bは、アクセス構造ABを決定し、使い捨て署名の鍵生成のアルゴリズムgenにしたがって使い捨て公開鍵vkBと使い捨て秘密鍵skBを生成し、ダミー属性集合WB={W1_vkB1,...,Wd_vkBd,...,WD_vkBD}ただし、vkBdは使い捨て公開鍵vkBのd番目のビットを設定する。そして、アクセス構造AB又はすべてのダミー属性W1_vkB1,...,WD_vkBDを満たす条件に対応する線形秘密分散法のシェア情報生成行列MBと単射ラベリング関数ρBを生成するS510B。短期秘密鍵生成部520Bは、1≦j≦NBについてv_jを0以上p-1以下の整数からランダムに選定してv=v_1,...,v_NBとし、yを0以上p-1以下の整数からランダムに選定し、1≦i≦LBについてyiを0以上p-1以下の整数からランダムに選定するS520B。交換情報生成部530Bは、1≦i≦LBについてベクトルvとベクトルMBiとの内積を計算してシェアλBiとする。そして、V=g^v_nBY=g^yVi=g^rλBih[ρBi]^-yiただし、1≦i≦LBYi=g^yiただし、1≦i≦LBを計算し、使い捨て署名の署名生成のアルゴリズムsigにしたがってskBを鍵、V,{Vi},Y,{Yi}をメッセージとする使い捨て署名sBを生成するS530B。送信部540Bは、EPKB=V,{Vi},Y,{Yi},MB,ρB,vkB,sBを鍵交換装置500Aに送信するS540B。受信部545Bは、鍵交換装置500Aから、EPKA=U,{Ui},X,{Xi},MA,ρA,vkA,sAを受信するS545B。属性確認部550Bは、属性集合SBがシェア情報生成行列MAと単射ラベリング関数ρAを満たすかを確認する。そして、満たさないと判断した場合は処理を中止する。満たすと判断した場合は、ステップS560Bに進むS551B。秘密情報取得部560Bは、IB={i:ρAi∈SB}となる集合IBとI’B={i:ρAi∈WA}となる集合I’Bを求める。そして、シェア情報生成行列MAに対応する秘密情報u_nAの正当なシェア集合{λAi}について、が成り立つ0以上p-1以下の整数wBiと整数w’Biを求めるS560B。上述のように、nAは鍵交換装置500Aと鍵交換装置500Bとで共有するあらかじめ定めた1以上NA以下の整数であればよい。例えば、nA=1とすればよい。属性確認部550Bは、U,{Ui},X,{Xi}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkAを鍵、U,{Ui},X,{Xi},sAをメッセージとして検証した結果が真であること、が成り立つことを確認する。そして、いずれかの条件を満足しない場合には処理を中止する。すべての条件を満足する場合はステップS370Bに進むS352B。セッション鍵計算部570Bは、σ2=gT^z^v_nBσ3=eg^r,X^yを計算する。そして、σ’1←Extσ1,σ’2←Extσ2,σ’3←Extσ3を計算し、セッション識別子sidをEPKA,EPKBに設定する。さらに、セッション鍵Kを、K=F_σ’1sidF_σ’2sidF_σ’3sidのように求めるS570B。中間情報消去部580Bは、少なくともv_j1≦j≦NB、y、yi1≦i≦LB、EPKA、EPKB、σ1、σ2、σ3、σ’1、σ’2、σ’3、sid、skBを消去するS580B。一般的には、セッション鍵K以外の計算の途中で使用した値をすべて消去すればよい。鍵交換装置500Aの処理に戻る。受信部545Aは、鍵交換装置500Bから、EPKB=V,{Vi},Y,{Yi},MB,ρB,vkB,sBを受信するS545A。属性確認部550Aは、属性集合SAがシェア情報生成行列MBと単射ラベリング関数ρBを満たすかを確認する。そして、満たさないと判断した場合は処理を中止する。満たすと判断した場合は、ステップS560Aに進むS551A。秘密情報取得部560Aは、IA={i:ρBi∈SA}となる集合IAとI’A={i:ρBi∈WB}となる集合I’Aを求める。そして、シェア情報生成行列MBに対応する秘密情報v_nBの正当なシェア集合{λBi}について、が成り立つ0以上p-1以下の整数wAiと整数w’Aiを求めるS560A。上述のように、nBは鍵交換装置500Aと鍵交換装置500Bとで共有するあらかじめ定めた1以上NB以下の整数であればよい。例えば、nB=1とすればよい。属性確認部550Aは、V,{Vi},Y,{Yi}のすべてが群Gの元であること、使い捨て署名の検証のアルゴリズムにしたがってvkBを鍵、V,{Vi},Y,{Yi},sBをメッセージとして検証した結果が真であること、が成り立つことを確認する。そして、いずれかの条件を満足しない場合には処理を中止する。すべての条件を満足する場合はステップS570Aに進むS552A。セッション鍵計算部570Aは、σ1=gT^z^u_nAσ3=eg^r,Y^xを計算する。そして、σ’1←Extσ1,σ’2←Extσ2,σ’3←Extσ3を計算し、セッション識別子sidをEPKA,EPKBに設定する。さらに、セッション鍵Kを、K=F_σ’1sidF_σ’2sidF_σ’3sidのように求めるS570A。中間情報消去部580Aは、少なくともu_j1≦j≦NA、x、xi1≦i≦LA、EPKA、EPKB、σ1、σ2、σ3、σ’1、σ’2、σ’3、sid、skAを消去するS580A。一般的には、セッション鍵K以外の計算の途中で使用した値をすべて消去すればよい。[確認]最後に鍵交換装置100Aと鍵交換装置100Bが取得したセッション鍵Kが等しいことを説明する。σ3=eg^r,X^y=gT^rxy=eg^r,Y^xよって、正しくセッション鍵を共有できる。本発明の鍵交換システムによれば、線形秘密分散法を利用することにより、鍵抽出長期秘密鍵の生成を行うときには鍵生成装置が、鍵交換装置500A、500Bの属性集合SA、SBに基づき線形秘密分散法のシェア情報として長期秘密鍵S’A,TA,{SA}、S’B,TB,{SB}を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造AA、ABを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定することが可能である。また、本発明のマスタ秘密鍵g^zとマスタ公開鍵g,g^r,gT^z,h[1],...,h[att’]は、属性集合とは独立なので、属性の全体集合をあらかじめ決めておく必要がない。つまり、鍵抽出時に任意の属性に基づき長期秘密鍵を発行することができる。したがって、非特許文献1と同等の効果が得られる。さらに、使い捨て署名、強ランダム抽出器、擬似ランダム関数を用いることにより、以下のように、ランダムオラクルを仮定しないで安全性を確保できる。鍵交換を行うユーザは、本来認証に用いる自分の属性集合S以外に、ダミー属性集合Wを用意し、生成した使い捨て署名の検証鍵の値にWを割り当てる。この時、ユーザは相手が満たすことを希望するアクセス構造Aに加えて、特定の検証鍵に対応したダミー属性集合Wが満たすようなアクセス構造を認証条件として加えて、鍵交換を行う。ダミー属性集合Wの方は、実際のユーザ同士が行う鍵交換セッションでは使われることはない。しかし、安全性証明の中で送られてきたメッセージが正しいかどうかを判定する際に、ダミー属性集合Wの方の認証条件を用いることにより、アクセス構造Aを満たす属性集合に対応する秘密鍵の知識なしで判定することができる。また、最後のセッション鍵の導出の時に、ランダムオラクルではなく、強ランダム抽出器と擬似ランダム関数を用いる。具体的には、強ランダム抽出器で共有情報の分布をならし、その値を擬似ランダム関数の鍵とすることで出力をセッション鍵とする。このように、本発明ではランダムオラクルを仮定すること無しに安全性を保つことができる。[プログラム、記録媒体]上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"