(57)【特許請求の範囲】
【請求項１】
少なくとも鍵交換装置αと鍵交換装置βとを備え、セッション鍵を交換する鍵交換システムであって、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｆ＿σは任意長の整数を指定された鍵空間Ｋｓｐａｃｅの値σにしたがってκビットの整数に変換する擬似ランダム関数、Ｅｘｔは群Ｇの元を鍵空間Ｋｓｐａｃｅの値に変換する強ランダム抽出器、Ｄは整数、ｄは１以上Ｄ以下の整数、ｇｅｎは検証鍵のビット長がＤであるような使い捨て署名の鍵生成のアルゴリズム、ｓｉｇは検証鍵のビット長がＤであるような使い捨て署名の署名生成のアルゴリズム、ｖｅｒは検証鍵のビット長がＤであるような使い捨て署名の検証のアルゴリズム、ａｔｔ’は属性の全要素数を示す整数、Ｗｄ＿Ｒはｄ番目のダミー属性を示す情報が１ビット以上のビット列Ｒであることを示す記号、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置αの属性を示す属性要素Ｐｎの集合、アクセス構造ＡＡは鍵交換装置αが鍵交換装置βに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉはシェア情報生成行列ＭＡのｉ番目の行に対応するベクトル、属性集合ＳＢは鍵交換装置βの属性を示す属性要素Ｐｎの集合、アクセス構造ＡＢは鍵交換装置βが鍵交換装置αに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉはシェア情報生成行列ＭＢのｉ番目の行に対応するベクトル、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ｎＡは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた１以上ＮＡ以下の整数、ｎＢは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた１以上ＮＢ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、ｈ［１］，…，ｈ［ａｔｔ’］は群Ｇの元、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡは０以上ｐ−１以下の整数、ｔＢは０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ）、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ）、ＴＡ＝ｇ＾ｔＡ、ＴＢ＝ｇ＾ｔＢ、ＳＡ［ｋＡ］＝ｈ［ｋＡ］＾ｔＡ、ＳＢ［ｋＢ］＝ｈ［ｋＢ］＾ｔＢ、｛ＳＡ｝はＳＡ［ｋＡ］の集合、｛ＳＢ｝はＳＢ［ｋＢ］の集合、｛Ｕｉ｝はＵｉの集合、｛Ｘｉ｝はＸｉの集合、｛Ｖｉ｝はＶｉの集合、｛Ｙｉ｝はＹｉの集合、＾はべき乗を示す記号、（＋）はビットごとの排他的論理和を示す記号であり、
前記鍵交換装置αは、
長期秘密鍵としてＳ’Ａ，ＴＡ，｛ＳＡ｝を記録する第１の記録部と、
アクセス構造ＡＡを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋＡと使い捨て秘密鍵ｓｋＡを生成し、ダミー属性集合ＷＡ＝｛Ｗ１＿ｖｋＡ１，…，Ｗｄ＿ｖｋＡｄ，…，ＷＤ＿ｖｋＡＤ｝（ただし、ｖｋＡｄは使い捨て公開鍵ｖｋＡのｄ番目のビット）を設定し、当該アクセス構造ＡＡ又はすべてのダミー属性Ｗ１＿ｖｋＡ１，…，ＷＤ＿ｖｋＡＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する第１のアクセス構造決定部と、
１≦ｊ≦ＮＡについてｕ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｕ＝（ｕ＿１，…，ｕ＿ＮＡ）とし、ｘを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦ＬＡについてｘｉを０以上ｐ−１以下の整数からランダムに選定する第１の短期秘密鍵生成部と、
１≦ｉ≦ＬＡについてベクトルｕとベクトル（ＭＡ）ｉとの内積を計算してシェアλＡｉとし、Ｕ＝ｇ＾ｕ＿ｎＡとＸ＝ｇ＾ｘと、１≦ｉ≦ＬＡについてＵｉ＝ｇ＾（ｒλＡｉ）ｈ［ρＡ（ｉ）］＾（−ｘｉ）とＸｉ＝ｇ＾ｘｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋＡを鍵、（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝）をメッセージとする使い捨て署名ｓＡを生成する第１の交換情報生成部と、
ＥＰＫＡ＝（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ＭＡ，ρＡ，ｖｋＡ，ｓＡ）を鍵交換装置βに送信する第１の送信部と、
鍵交換装置βから、ＥＰＫＢ＝（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ＭＢ，ρＢ，ｖｋＢ，ｓＢ）を受信する第１の受信部と、
ＩＡ＝｛ｉ：ρＢ（ｉ）∈ＳＡ｝となる集合ＩＡとＩ’Ａ＝｛ｉ：ρＢ（ｉ）∈ＷＢ｝となる集合Ｉ’Ａを求め、シェア情報生成行列ＭＢに対応する秘密情報ｖ＿ｎＢの正当なシェア集合｛λＢｉ｝について、
【数２２】
0005650630.tif 000023
が成り立つ０以上ｐ−１以下の整数ｗＡｉと整数ｗ’Ａｉを求める第１の秘密情報取得部と、
属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすかを確認することと、Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋＢを鍵、（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ｓＢ）をメッセージとして検証した結果が真であること、
【数２３】
0005650630.tif 000024
が成り立つことを確認する第１の属性確認部と、
【数２４】
0005650630.tif 000025
σ１＝（ｇＴ＾ｚ）＾ｕ＿ｎＡ
σ３＝ｅ（ｇ＾ｒ，Ｙ）＾ｘ
を計算し、σ’１←Ｅｘｔ（σ１），σ’２←Ｅｘｔ（σ２），σ’３←Ｅｘｔ（σ３）を計算し、セッション識別子ｓｉｄを（ＥＰＫＡ，ＥＰＫＢ）に設定し、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’１（ｓｉｄ）（＋）Ｆ＿σ’２（ｓｉｄ）（＋）Ｆ＿σ’３（ｓｉｄ）
のように求める第１のセッション鍵計算部と、
少なくともｕ＿ｊ（１≦ｊ≦ＮＡ）、ｘ、ｘｉ（１≦ｉ≦ＬＡ）、ＥＰＫＡ、ＥＰＫＢ、σ１、σ２、σ３、σ’１、σ’２、σ’３、ｓｉｄ、ｓｋＡを消去する第１の中間情報消去部と、
を備え、
前記鍵交換装置βは、
長期秘密鍵としてＳ’Ｂ，ＴＢ，｛ＳＢ｝を記録する第２の記録部と、
アクセス構造ＡＢを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋＢと使い捨て秘密鍵ｓｋＢを生成し、ダミー属性集合ＷＢ＝｛Ｗ１＿ｖｋＢ１，…，Ｗｄ＿ｖｋＢｄ，…，ＷＤ＿ｖｋＢＤ｝（ただし、ｖｋＢｄは使い捨て公開鍵ｖｋＢのｄ番目のビット）を設定し、当該アクセス構造ＡＢ又はすべてのダミー属性Ｗ１＿ｖｋＢ１，…，ＷＤ＿ｖｋＢＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する第２のアクセス構造決定部と、
１≦ｊ≦ＮＢについてｖ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｖ＝（ｖ＿１，…，ｖ＿ＮＢ）とし、ｙを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦ＬＢについてｙｉを０以上ｐ−１以下の整数からランダムに選定する第２の短期秘密鍵生成部と、
１≦ｉ≦ＬＢについてベクトルｖとベクトル（ＭＢ）ｉとの内積を計算してシェアλＢｉとし、Ｖ＝ｇ＾ｖ＿ｎＢとＹ＝ｇ＾ｙと、１≦ｉ≦ＬＢについてＶｉ＝ｇ＾（ｒλＢｉ）ｈ［ρＢ（ｉ）］＾（−ｙｉ）とＹｉ＝ｇ＾ｙｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋＢを鍵、（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝）をメッセージとする使い捨て署名ｓＢを生成する第２の交換情報生成部と、
ＥＰＫＢ＝（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ＭＢ，ρＢ，ｖｋＢ，ｓＢ）を鍵交換装置αに送信する第２の送信部と、
鍵交換装置αから、ＥＰＫＡ＝（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ＭＡ，ρＡ，ｖｋＡ，ｓＡ）を受信する第２の受信部と、
ＩＢ＝｛ｉ：ρＡ（ｉ）∈ＳＢ｝となる集合ＩＢとＩ’Ｂ＝｛ｉ：ρＡ（ｉ）∈ＷＡ｝となる集合Ｉ’Ｂを求め、シェア情報生成行列ＭＡに対応する秘密情報ｕ＿ｎＡの正当なシェア集合｛λＡｉ｝について、
【数２５】
0005650630.tif 000026
が成り立つ０以上ｐ−１以下の整数ｗＢｉと整数ｗ’Ｂｉを求める第２の秘密情報取得部と、
属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすかを確認することと、Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋＡを鍵、（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ｓＡ）をメッセージとして検証した結果が真であること、
【数２６】
0005650630.tif 000027
が成り立つことを確認する第２の属性確認部と、
【数２７】
0005650630.tif 000028
σ２＝（ｇＴ＾ｚ）＾ｖ＿ｎＢ
σ３＝ｅ（ｇ＾ｒ，Ｘ）＾ｙ
を計算し、σ’１←Ｅｘｔ（σ１），σ’２←Ｅｘｔ（σ２），σ’３←Ｅｘｔ（σ３）を計算し、セッション識別子ｓｉｄを（ＥＰＫＡ，ＥＰＫＢ）に設定し、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’１（ｓｉｄ）（＋）Ｆ＿σ’２（ｓｉｄ）（＋）Ｆ＿σ’３（ｓｉｄ）
のように求める第２のセッション鍵計算部と、
少なくともｖ＿ｊ（１≦ｊ≦ＮＢ）、ｙ、ｙｉ（１≦ｉ≦ＬＢ）、ＥＰＫＡ、ＥＰＫＢ、σ１、σ２、σ３、σ’１、σ’２、σ’３、ｓｉｄ、ｓｋＢを消去する第２の中間情報消去部と、
を備える
鍵交換システム。
【請求項２】
請求項１記載の鍵交換システムであって、
さらに、マスタ鍵生成部と長期秘密鍵生成部とを有する鍵生成装置を備え、
前記ｒ，ｚ，ｈ［１］，…，ｈ［ａｔｔ’］は、前記マスタ鍵生成部がランダムに選定したものであり、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）とマスタ秘密鍵ｇ＾ｚは前記マスタ鍵生成部が生成したものであり、
前記ｔＡとｔＢは前記長期秘密鍵生成部がランダムに選定したものであり、Ｓ’ＡとＳ’Ｂ、ＴＡとＴＢ、ＳＡ［ｋＡ］とＳＢ［ｋＢ］は前記長期秘密鍵生成部が計算したものであり、
前記鍵交換装置αが記録しておく前記長期秘密鍵（Ｓ’Ａ，ＴＡ，｛ＳＡ｝）は前記鍵生成装置からを取得したものであり、前記鍵交換装置βが記録しておく前記長期秘密鍵（Ｓ’Ｂ，ＴＢ，｛ＳＢ｝）は前記鍵生成装置から取得したものである
ことを特徴とする鍵交換システム。
【請求項３】
セッション鍵を交換する鍵交換装置であって、
鍵交換する対象の鍵交換装置は、当該鍵交換装置と同じ構成であり、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｆ＿σは任意長の整数を指定された鍵空間Ｋｓｐａｃｅの値σにしたがってκビットの整数に変換する擬似ランダム関数、Ｅｘｔは群Ｇの元を鍵空間Ｋｓｐａｃｅの値に変換する強ランダム抽出器、Ｄは整数、ｄは１以上Ｄ以下の整数、ｇｅｎは検証鍵のビット長がＤであるような使い捨て署名の鍵生成のアルゴリズム、ｓｉｇは検証鍵のビット長がＤであるような使い捨て署名の署名生成のアルゴリズム、ｖｅｒは検証鍵のビット長がＤであるような使い捨て署名の検証のアルゴリズム、ａｔｔ’は属性の全要素数を示す整数、Ｗｄ＿Ｒはｄ番目のダミー属性を示す情報が１ビット以上のビット列Ｒであることを示す記号、Ｐｎは属性を示す属性要素、属性集合ＳＡは当該鍵交換装置の属性を示す属性要素Ｐｎの集合、アクセス構造ＡＡは当該鍵交換装置が鍵交換する対象の鍵交換装置に求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉはシェア情報生成行列ＭＡのｉ番目の行に対応するベクトル、属性集合ＳＢは鍵交換する対象の鍵交換装置の属性を示す属性要素Ｐｎの集合、アクセス構造ＡＢは鍵交換する対象の鍵交換装置が求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉはシェア情報生成行列ＭＢのｉ番目の行に対応するベクトル、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ｎＡは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた１以上ＮＡ以下の整数、ｎＢは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた１以上ＮＢ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、ｈ［１］，…，ｈ［ａｔｔ’］は群Ｇの元、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡは０以上ｐ−１以下の整数、ｔＢは０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ）、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ）、ＴＡ＝ｇ＾ｔＡ、ＴＢ＝ｇ＾ｔＢ、ＳＡ［ｋＡ］＝ｈ［ｋＡ］＾ｔＡ、ＳＢ［ｋＢ］＝ｈ［ｋＢ］＾ｔＢ、｛ＳＡ｝はＳＡ［ｋＡ］の集合、｛ＳＢ｝はＳＢ［ｋＢ］の集合、｛Ｕｉ｝はＵｉの集合、｛Ｘｉ｝はＸｉの集合、｛Ｖｉ｝はＶｉの集合、｛Ｙｉ｝はＹｉの集合、＾はべき乗を示す記号、（＋）はビットごとの排他的論理和を示す記号であり、
長期秘密鍵としてＳ’Ａ，ＴＡ，｛ＳＡ｝を記録する記録部と、
アクセス構造ＡＡを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋＡと使い捨て秘密鍵ｓｋＡを生成し、ダミー属性集合ＷＡ＝｛Ｗ１＿ｖｋＡ１，…，Ｗｄ＿ｖｋＡｄ，…，ＷＤ＿ｖｋＡＤ｝（ただし、ｖｋＡｄは使い捨て公開鍵ｖｋＡのｄ番目のビット）を設定し、当該アクセス構造ＡＡ又はすべてのダミー属性Ｗ１＿ｖｋＡ１，…，ＷＤ＿ｖｋＡＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成するアクセス構造決定部と、
１≦ｊ≦ＮＡについてｕ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｕ＝（ｕ＿１，…，ｕ＿ＮＡ）とし、ｘを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦ＬＡについてｘｉを０以上ｐ−１以下の整数からランダムに選定する短期秘密鍵生成部と、
１≦ｉ≦ＬＡについてベクトルｕとベクトル（ＭＡ）ｉとの内積を計算してシェアλＡｉとし、Ｕ＝ｇ＾ｕ＿ｎＡとＸ＝ｇ＾ｘと、１≦ｉ≦ＬＡについてＵｉ＝ｇ＾（ｒλＡｉ）ｈ［ρＡ（ｉ）］＾（−ｘｉ）とＸｉ＝ｇ＾ｘｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋＡを鍵、（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝）をメッセージとする使い捨て署名ｓＡを生成する交換情報生成部と、
ＥＰＫＡ＝（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ＭＡ，ρＡ，ｖｋＡ，ｓＡ）を鍵交換する対象の装置に送信する送信部と、
鍵交換する対象の装置から、ＥＰＫＢ＝（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ＭＢ，ρＢ，ｖｋＢ，ｓＢ）を受信する受信部と、
ＩＡ＝｛ｉ：ρＢ（ｉ）∈ＳＡ｝となる集合ＩＡとＩ’Ａ＝｛ｉ：ρＢ（ｉ）∈ＷＢ｝となる集合Ｉ’Ａを求め、シェア情報生成行列ＭＢに対応する秘密情報ｖ＿ｎＢの正当なシェア集合｛λＢｉ｝について、
【数２８】
0005650630.tif 000029
が成り立つ０以上ｐ−１以下の整数ｗＡｉと整数ｗ’Ａｉを求める秘密情報取得部と、
属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすかを確認することと、Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋＢを鍵、（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ｓＢ）をメッセージとして検証した結果が真であること、
【数２９】
0005650630.tif 000030
が成り立つことを確認する属性確認部と、
【数３０】
0005650630.tif 000031
σ１＝（ｇＴ＾ｚ）＾ｕ＿ｎＡ
σ３＝ｅ（ｇ＾ｒ，Ｙ）＾ｘ
を計算し、σ’１←Ｅｘｔ（σ１），σ’２←Ｅｘｔ（σ２），σ’３←Ｅｘｔ（σ３）を計算し、セッション識別子ｓｉｄを（ＥＰＫＡ，ＥＰＫＢ）に設定し、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’１（ｓｉｄ）（＋）Ｆ＿σ’２（ｓｉｄ）（＋）Ｆ＿σ’３（ｓｉｄ）
のように求めるセッション鍵計算部と、
少なくともｕ＿ｊ（１≦ｊ≦ＮＡ）、ｘ、ｘｉ（１≦ｉ≦ＬＡ）、ＥＰＫＡ、ＥＰＫＢ、σ１、σ２、σ３、σ’１、σ’２、σ’３、ｓｉｄ、ｓｋＡを消去する中間情報消去部と、
を備える鍵交換装置。
【請求項４】
セッション鍵を交換する鍵交換装置であって、
鍵交換する対象の鍵交換装置は、当該鍵交換装置と同じ構成であり、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｆ＿σは任意長の整数を指定された鍵空間Ｋｓｐａｃｅの値σにしたがってκビットの整数に変換する擬似ランダム関数、Ｅｘｔは群Ｇの元を鍵空間Ｋｓｐａｃｅの値に変換する強ランダム抽出器、Ｄは整数、ｄは１以上Ｄ以下の整数、ｇｅｎは検証鍵のビット長がＤであるような使い捨て署名の鍵生成のアルゴリズム、ｓｉｇは検証鍵のビット長がＤであるような使い捨て署名の署名生成のアルゴリズム、ｖｅｒは検証鍵のビット長がＤであるような使い捨て署名の検証のアルゴリズム、ａｔｔ’は属性の全要素数を示す整数、Ｗｄ＿Ｒはｄ番目のダミー属性を示す情報が１ビット以上のビット列Ｒであることを示す記号、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換する対象の鍵交換装置の属性を示す属性要素Ｐｎの集合、アクセス構造ＡＡは鍵交換する対象の鍵交換装置に求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉはシェア情報生成行列ＭＡのｉ番目の行に対応するベクトル、属性集合ＳＢは当該鍵交換装置の属性を示す属性要素Ｐｎの集合、アクセス構造ＡＢは当該鍵交換装置が鍵交換する対象の鍵交換装置に求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉはシェア情報生成行列ＭＢのｉ番目の行に対応するベクトル、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ｎＡは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた１以上ＮＡ以下の整数、ｎＢは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた１以上ＮＢ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、ｈ［１］，…，ｈ［ａｔｔ’］は群Ｇの元、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡは０以上ｐ−１以下の整数、ｔＢは０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ）、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ）、ＴＡ＝ｇ＾ｔＡ、ＴＢ＝ｇ＾ｔＢ、ＳＡ［ｋＡ］＝ｈ［ｋＡ］＾ｔＡ、ＳＢ［ｋＢ］＝ｈ［ｋＢ］＾ｔＢ、｛ＳＡ｝はＳＡ［ｋＡ］の集合、｛ＳＢ｝はＳＢ［ｋＢ］の集合、｛Ｕｉ｝はＵｉの集合、｛Ｘｉ｝はＸｉの集合、｛Ｖｉ｝はＶｉの集合、｛Ｙｉ｝はＹｉの集合、＾はべき乗を示す記号、（＋）はビットごとの排他的論理和を示す記号であり、
長期秘密鍵としてＳ’Ｂ，ＴＢ，｛ＳＢ｝を記録する記録部と、
アクセス構造ＡＢを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋＢと使い捨て秘密鍵ｓｋＢを生成し、ダミー属性集合ＷＢ＝｛Ｗ１＿ｖｋＢ１，…，Ｗｄ＿ｖｋＢｄ，…，ＷＤ＿ｖｋＢＤ｝（ただし、ｖｋＢｄは使い捨て公開鍵ｖｋＢのｄ番目のビット）を設定し、当該アクセス構造ＡＢ又はすべてのダミー属性Ｗ１＿ｖｋＢ１，…，ＷＤ＿ｖｋＢＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成するアクセス構造決定部と、
１≦ｊ≦ＮＢについてｖ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｖ＝（ｖ＿１，…，ｖ＿ＮＢ）とし、ｙを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦ＬＢについてｙｉを０以上ｐ−１以下の整数からランダムに選定する短期秘密鍵生成部と、
１≦ｉ≦ＬＢについてベクトルｖとベクトル（ＭＢ）ｉとの内積を計算してシェアλＢｉとし、Ｖ＝ｇ＾ｖ＿ｎＢとＹ＝ｇ＾ｙと、１≦ｉ≦ＬＢについてＶｉ＝ｇ＾（ｒλＢｉ）ｈ［ρＢ（ｉ）］＾（−ｙｉ）とＹｉ＝ｇ＾ｙｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋＢを鍵、（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝）をメッセージとする使い捨て署名ｓＢを生成する交換情報生成部と、
ＥＰＫＢ＝（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ＭＢ，ρＢ，ｖｋＢ，ｓＢ）を鍵交換する対象の鍵交換装置に送信する送信部と、
鍵交換する対象の鍵交換装置から、ＥＰＫＡ＝（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ＭＡ，ρＡ，ｖｋＡ，ｓＡ）を受信する受信部と、
ＩＢ＝｛ｉ：ρＡ（ｉ）∈ＳＢ｝となる集合ＩＢとＩ’Ｂ＝｛ｉ：ρＡ（ｉ）∈ＷＡ｝となる集合Ｉ’Ｂを求め、シェア情報生成行列ＭＡに対応する秘密情報ｕ＿ｎＡの正当なシェア集合｛λＡｉ｝について、
【数３１】
0005650630.tif 000032
が成り立つ０以上ｐ−１以下の整数ｗＢｉと整数ｗ’Ｂｉを求める秘密情報取得部と、
属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすかを確認することと、Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋＡを鍵、（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ｓＡ）をメッセージとして検証した結果が真であること、
【数３２】
0005650630.tif 000033
が成り立つことを確認する属性確認部と、
【数３３】
0005650630.tif 000034
σ２＝（ｇＴ＾ｚ）＾ｖ＿ｎＢ
σ３＝ｅ（ｇ＾ｒ，Ｘ）＾ｙ
を計算し、σ’１←Ｅｘｔ（σ１），σ’２←Ｅｘｔ（σ２），σ’３←Ｅｘｔ（σ３）を計算し、セッション識別子ｓｉｄを（ＥＰＫＡ，ＥＰＫＢ）に設定し、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’１（ｓｉｄ）（＋）Ｆ＿σ’２（ｓｉｄ）（＋）Ｆ＿σ’３（ｓｉｄ）
のように求めるセッション鍵計算部と、
少なくともｖ＿ｊ（１≦ｊ≦ＮＢ）、ｙ、ｙｉ（１≦ｉ≦ＬＢ）、ＥＰＫＡ、ＥＰＫＢ、σ１、σ２、σ３、σ’１、σ’２、σ’３、ｓｉｄ、ｓｋＢを消去する中間情報消去部と、
を備える鍵交換装置。
【請求項５】
少なくとも鍵交換装置αと鍵交換装置βとを備える鍵交換システムを用いて、セッション鍵を交換する鍵交換方法であって、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｆ＿σは任意長の整数を指定された鍵空間Ｋｓｐａｃｅの値σにしたがってκビットの整数に変換する擬似ランダム関数、Ｅｘｔは群Ｇの元を鍵空間Ｋｓｐａｃｅの値に変換する強ランダム抽出器、Ｄは整数、ｄは１以上Ｄ以下の整数、ｇｅｎは検証鍵のビット長がＤであるような使い捨て署名の鍵生成のアルゴリズム、ｓｉｇは検証鍵のビット長がＤであるような使い捨て署名の署名生成のアルゴリズム、ｖｅｒは検証鍵のビット長がＤであるような使い捨て署名の検証のアルゴリズム、ａｔｔ’は属性の全要素数を示す整数、Ｗｄ＿Ｒはｄ番目のダミー属性を示す情報が１ビット以上のビット列Ｒであることを示す記号、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置αの属性を示す属性要素Ｐｎの集合、アクセス構造ＡＡは鍵交換装置αが鍵交換装置βに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉはシェア情報生成行列ＭＡのｉ番目の行に対応するベクトル、属性集合ＳＢは鍵交換装置βの属性を示す属性要素Ｐｎの集合、アクセス構造ＡＢは鍵交換装置βが鍵交換装置αに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉはシェア情報生成行列ＭＢのｉ番目の行に対応するベクトル、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ｎＡは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた１以上ＮＡ以下の整数、ｎＢは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた１以上ＮＢ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、ｈ［１］，…，ｈ［ａｔｔ’］は群Ｇの元、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡは０以上ｐ−１以下の整数、ｔＢは０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ）、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ）、ＴＡ＝ｇ＾ｔＡ、ＴＢ＝ｇ＾ｔＢ、ＳＡ［ｋＡ］＝ｈ［ｋＡ］＾ｔＡ、ＳＢ［ｋＢ］＝ｈ［ｋＢ］＾ｔＢ、｛ＳＡ｝はＳＡ［ｋＡ］の集合、｛ＳＢ｝はＳＢ［ｋＢ］の集合、｛Ｕｉ｝はＵｉの集合、｛Ｘｉ｝はＸｉの集合、｛Ｖｉ｝はＶｉの集合、｛Ｙｉ｝はＹｉの集合、＾はべき乗を示す記号、（＋）はビットごとの排他的論理和を示す記号であり、
前記鍵交換装置αは、長期秘密鍵としてＳ’Ａ，ＴＡ，｛ＳＡ｝を記録しておき、
前記鍵交換装置βは、長期秘密鍵としてＳ’Ｂ，ＴＢ，｛ＳＢ｝を記録しておき、
前記鍵交換装置αが、アクセス構造ＡＡを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋＡと使い捨て秘密鍵ｓｋＡを生成し、ダミー属性集合ＷＡ＝｛Ｗ１＿ｖｋＡ１，…，Ｗｄ＿ｖｋＡｄ，…，ＷＤ＿ｖｋＡＤ｝（ただし、ｖｋＡｄは使い捨て公開鍵ｖｋＡのｄ番目のビット）を設定し、当該アクセス構造ＡＡ又はすべてのダミー属性Ｗ１＿ｖｋＡ１，…，ＷＤ＿ｖｋＡＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する第１のアクセス構造決定ステップと、
前記鍵交換装置αが、１≦ｊ≦ＮＡについてｕ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｕ＝（ｕ＿１，…，ｕ＿ＮＡ）とし、ｘを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦ＬＡについてｘｉを０以上ｐ−１以下の整数からランダムに選定する第１の短期秘密鍵生成ステップと、
前記鍵交換装置αが、１≦ｉ≦ＬＡについてベクトルｕとベクトル（ＭＡ）ｉとの内積を計算してシェアλＡｉとし、Ｕ＝ｇ＾ｕ＿ｎＡとＸ＝ｇ＾ｘと、１≦ｉ≦ＬＡについてＵｉ＝ｇ＾（ｒλＡｉ）ｈ［ρＡ（ｉ）］＾（−ｘｉ）とＸｉ＝ｇ＾ｘｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋＡを鍵、（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝）をメッセージとする使い捨て署名ｓＡを生成する第１の交換情報生成ステップと、
前記鍵交換装置αが、ＥＰＫＡ＝（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ＭＡ，ρＡ，ｖｋＡ，ｓＡ）を前記鍵交換装置βに送信する第１の送信ステップと、
前記鍵交換装置βが、アクセス構造ＡＢを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋＢと使い捨て秘密鍵ｓｋＢを生成し、ダミー属性集合ＷＢ＝｛Ｗ１＿ｖｋＢ１，…，Ｗｄ＿ｖｋＢｄ，…，ＷＤ＿ｖｋＢＤ｝（ただし、ｖｋＢｄは使い捨て公開鍵ｖｋＢのｄ番目のビット）を設定し、当該アクセス構造ＡＢ又はすべてのダミー属性Ｗ１＿ｖｋＢ１，…，ＷＤ＿ｖｋＢＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する第２のアクセス構造決定ステップと、
前記鍵交換装置βが、１≦ｊ≦ＮＢについてｖ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｖ＝（ｖ＿１，…，ｖ＿ＮＢ）とし、ｙを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦ＬＢについてｙｉを０以上ｐ−１以下の整数からランダムに選定する第２の短期秘密鍵生成ステップと、
前記鍵交換装置βが、１≦ｉ≦ＬＢについてベクトルｖとベクトル（ＭＢ）ｉとの内積を計算してシェアλＢｉとし、Ｖ＝ｇ＾ｖ＿ｎＢとＹ＝ｇ＾ｙと、１≦ｉ≦ＬＢについてＶｉ＝ｇ＾（ｒλＢｉ）ｈ［ρＢ（ｉ）］＾（−ｙｉ）とＹｉ＝ｇ＾ｙｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋＢを鍵、（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝）をメッセージとする使い捨て署名ｓＢを生成する第２の交換情報生成ステップと、
前記鍵交換装置βが、ＥＰＫＢ＝（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ＭＢ，ρＢ，ｖｋＢ，ｓＢ）を前記鍵交換装置αに送信する第２の送信ステップと、
前記鍵交換装置βが、前記鍵交換装置αから、ＥＰＫＡ＝（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ＭＡ，ρＡ，ｖｋＡ，ｓＡ）を受信する第２の受信ステップと、
前記鍵交換装置βが、属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすかを確認する第２の簡易属性確認ステップと、
前記鍵交換装置βが、ＩＢ＝｛ｉ：ρＡ（ｉ）∈ＳＢ｝となる集合ＩＢとＩ’Ｂ＝｛ｉ：ρＡ（ｉ）∈ＷＡ｝となる集合Ｉ’Ｂを求め、シェア情報生成行列ＭＡに対応する秘密情報ｕ＿ｎＡの正当なシェア集合｛λＡｉ｝について、
【数３４】
0005650630.tif 000035
が成り立つ０以上ｐ−１以下の整数ｗＢｉと整数ｗ’Ｂｉを求める第２の秘密情報取得ステップと、
前記鍵交換装置βが、Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋＡを鍵、（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ｓＡ）をメッセージとして検証した結果が真であること、
【数３５】
0005650630.tif 000036
が成り立つことを確認する第２の属性確認ステップと、
前記鍵交換装置βが、
【数３６】
0005650630.tif 000037
σ２＝（ｇＴ＾ｚ）＾ｖ＿ｎＢ
σ３＝ｅ（ｇ＾ｒ，Ｘ）＾ｙ
を計算し、σ’１←Ｅｘｔ（σ１），σ’２←Ｅｘｔ（σ２），σ’３←Ｅｘｔ（σ３）を計算し、セッション識別子ｓｉｄを（ＥＰＫＡ，ＥＰＫＢ）に設定し、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’１（ｓｉｄ）（＋）Ｆ＿σ’２（ｓｉｄ）（＋）Ｆ＿σ’３（ｓｉｄ）
のように求める第２のセッション鍵計算ステップと、
前記鍵交換装置βが、少なくともｖ＿ｊ（１≦ｊ≦ＮＢ）、ｙ、ｙｉ（１≦ｉ≦ＬＢ）、ＥＰＫＡ、ＥＰＫＢ、σ１、σ２、σ３、σ’１、σ’２、σ’３、ｓｉｄ、ｓｋＢを消去する第２の中間情報消去ステップと、
前記鍵交換装置αが、前記鍵交換装置βから、ＥＰＫＢ＝（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ＭＢ，ρＢ，ｖｋＢ，ｓＢ）を受信する第１の受信ステップと、
前記鍵交換装置αが、属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすかを確認する第１の簡易属性確認ステップと、
前記鍵交換装置αが、ＩＡ＝｛ｉ：ρＢ（ｉ）∈ＳＡ｝となる集合ＩＡとＩ’Ａ＝｛ｉ：ρＢ（ｉ）∈ＷＢ｝となる集合Ｉ’Ａを求め、シェア情報生成行列ＭＢに対応する秘密情報ｖ＿ｎＢの正当なシェア集合｛λＢｉ｝について、
【数３７】
0005650630.tif 000038
が成り立つ０以上ｐ−１以下の整数ｗＡｉと整数ｗ’Ａｉを求める第１の秘密情報取得ステップと、
前記鍵交換装置αが、Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋＢを鍵、（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ｓＢ）をメッセージとして検証した結果が真であること、
【数３８】
0005650630.tif 000039
が成り立つことを確認する第１の属性確認ステップと、
前記鍵交換装置αが、
【数３９】
0005650630.tif 000040
σ１＝（ｇＴ＾ｚ）＾ｕ＿ｎＡ
σ３＝ｅ（ｇ＾ｒ，Ｙ）＾ｘ
を計算し、σ’１←Ｅｘｔ（σ１），σ’２←Ｅｘｔ（σ２），σ’３←Ｅｘｔ（σ３）を計算し、セッション識別子ｓｉｄを（ＥＰＫＡ，ＥＰＫＢ）に設定し、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’１（ｓｉｄ）（＋）Ｆ＿σ’２（ｓｉｄ）（＋）Ｆ＿σ’３（ｓｉｄ）
のように求める第１のセッション鍵計算ステップと、
前記鍵交換装置αが、少なくともｕ＿ｊ（１≦ｊ≦ＮＡ）、ｘ、ｘｉ（１≦ｉ≦ＬＡ）、ＥＰＫＡ、ＥＰＫＢ、σ１、σ２、σ３、σ’１、σ’２、σ’３、ｓｉｄ、ｓｋＡを消去する第１の中間情報消去ステップと、
を有する鍵交換方法。
【請求項６】
請求項５記載の鍵交換方法であって、
前記鍵交換システムは、さらにマスタ鍵生成手段と長期秘密鍵生成手段も備え、
前記マスタ鍵生成手段が、前記ｒ，ｚ，ｈ［１］，…，ｈ［ａｔｔ’］をランダムに選定し、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）とマスタ秘密鍵ｇ＾ｚを生成するマスタ鍵生成ステップと、
前記長期秘密鍵生成手段が、前記ｔＡとｔＢをランダムに選定し、Ｓ’ＡとＳ’Ｂ、ＴＡとＴＢ、ＳＡ［ｋＡ］とＳＢ［ｋＢ］を計算する長期秘密鍵生成ステップと、
前記鍵交換装置αが、長期秘密鍵としてＳ’Ａ，ＴＡ，｛ＳＡ｝を取得する第１の長期秘密鍵取得ステップと、
前記鍵交換装置βが、長期秘密鍵としてＳ’Ｂ，ＴＢ，｛ＳＢ｝を取得する第２の長期秘密鍵取得ステップ
も有することを特徴とする鍵交換方法。
【請求項７】
請求項３または４記載の鍵交換装置としてコンピュータを機能させるための鍵交換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報セキュリティに関するものであり、特に、二者間でセッション鍵を共有するための鍵交換システム、鍵交換装置、鍵生成装置、鍵交換方法、鍵交換プログラムに関する。
【背景技術】
【０００２】
鍵交換時にアクセスポリシーを指定でき、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができる鍵交換システムについて、非特許文献１に公開されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Kazuki Yoneyama, “Strongly Secure Two-Pass Attribute-Based Authenti-cated Key Exchange”, Pairing 2010, LNCS 6487, pp147-166, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１に対応する内容は、本願出願時には未公開の特願２０１０−２５９０５３に記載されており、以下のとおりである。
【０００５】
［構成］
図１に特願２０１０−２５９０５３の鍵交換システムの構成例を示す。鍵交換システムは、ネットワーク１０００を介して接続された鍵交換装置１００１，…，１００Ｑ（ただし、Ｑは２以上の整数、ｑは１以上Ｑ以下の整数、ＡとＢは１以上Ｑ以下の異なる整数）、鍵生成装置３００で構成される。図２に鍵交換装置の機能構成例、図３に鍵生成装置の機能構成例を示す。鍵交換装置１００ｑは、アクセス構造決定部１１０ｑ、短期秘密鍵生成部１２０ｑ、交換情報生成部１３０ｑ、送信部１４０ｑ、受信部１４５ｑ、属性確認部１５０ｑ、秘密情報取得部１６０ｑ、セッション鍵計算部１７０ｑ、中間情報消去部１８０ｑ、記録部１９０ｑを備える。また、鍵生成装置３００は、マスタ鍵生成部３１０、長期秘密鍵生成部３２０、記録部３９０を備える。以下の説明では、鍵交換装置１００Ａ（鍵交換装置αに相当）がイニシエータとして機能し、鍵交換装置１００Ｂ（鍵交換装置βに相当）がレスポンダとして機能してセッション鍵を共有する場合について説明する。
【０００６】
なお、κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置１００Ａの属性を示す属性要素Ｐｎの組み合わせの集合、属性集合ＳＢは鍵交換装置１００Ｂの属性を示す属性要素Ｐｎの組み合わせの集合、ＮＭＡＸはあらかじめ定めた整数、ｊとｎは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＴＢ｝はＴＢ［１］，…，ＴＢ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、｛ＳＢ｝はＳＢ［１］，…，ＳＢ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合である。
【０００７】
［鍵生成、鍵抽出］
図４に、マスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す。なお、長期秘密鍵生成の処理が鍵抽出に相当する。鍵生成装置３００のマスタ鍵生成部３１０は、０以上ｐ−１以下の整数からランダムにｒとｚを選定する。そして、マスタ公開鍵を（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）、マスタ秘密鍵をｇ＾ｚとして記録部３９０に記録し、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）を公開する（Ｓ３１０）。鍵交換装置１００Ａと鍵交換装置１００Ｂは、それぞれマスタ公開鍵を（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）を受信し、記録部１９０Ａと記録部１９０Ｂに記録する。
【０００８】
長期秘密鍵生成部３２０は、０以上ｐ−１以下の整数からランダムにｔＡ［１］，…，ｔＡ［ＮＭＡＸ］を選び、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）を計算し、１以上ＮＭＡＸ以下のｊについてＴＡ［ｊ］＝ｇ＾ｔＡ［１］を計算し、属性集合ＳＡの要素ｋＡについて
【０００９】
【数１】
0005650630.tif 000002
【００１０】
を計算し、長期秘密鍵として（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝）を鍵交換装置１００Ａに送信する（Ｓ３２０Ａ）。鍵交換装置１００Ａは、長期秘密鍵（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝）を受信し、記録部１９０Ａに記録する（Ｓ１９２Ａ）。
【００１１】
さらに、長期秘密鍵生成部３２０は、０以上ｐ−１以下の整数からランダムにｔＢ［１］，…，ｔＢ［ＮＭＡＸ］を選び、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ［１］）を計算し、１以上ＮＭＡＸ以下のｊについてＴＢ［ｊ］＝ｇ＾ｔＢ［１］を計算し、属性集合ＳＢの要素ｋＢについて
【００１２】
【数２】
0005650630.tif 000003
【００１３】
を計算し、長期秘密鍵として（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝）を鍵交換装置１００Ｂに送信する（Ｓ３２０Ｂ）。鍵交換装置１００Ｂは、長期秘密鍵（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝）を受信し、記録部１９０Ｂに記録する（Ｓ１９２Ｂ）。
【００１４】
なお、あらかじめ鍵交換装置１００Ａの記録部１９０Ａにマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）と長期秘密鍵（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝）とを記録させ、鍵交換装置１００Ｂの記録部１９０Ｂにマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）と長期秘密鍵（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝）とを記録させておけば、ネットワーク１０００を介して接続された鍵交換装置１００Ａと鍵交換装置１００Ｂだけで最低限の鍵交換システムが構成できる。
【００１５】
［鍵交換］
図５にセッション鍵を共有する鍵交換の処理のフローの例を示す。この例は、鍵交換装置１００Ａ（鍵交換装置αに相当）がイニシエータとして機能し、鍵交換装置１００Ｂ（鍵交換装置βに相当）がレスポンダとして機能する場合を示している。
【００１６】
鍵交換装置１００Ａは、アクセス構造決定部１１０Ａ、短期秘密鍵生成部１２０Ａ、交換情報生成部１３０Ａ、送信部１４０Ａ、受信部１４５Ａ、属性確認部１５０Ａ、秘密情報取得部１６０Ａ、セッション鍵計算部１７０Ａ、中間情報消去部１８０Ａを備える。鍵交換装置１００Ｂは、アクセス構造決定部１１０Ｂ、短期秘密鍵生成部１２０Ｂ、交換情報生成部１３０Ｂ、送信部１４０Ｂ、受信部１４５Ｂ、属性確認部１５０Ｂ、秘密情報取得部１６０Ｂ、セッション鍵計算部１７０Ｂ、中間情報消去部１８０Ｂを備える。
【００１７】
アクセス構造決定部１１０Ａは、アクセス構造ＡＡを決定し、当該アクセス構造ＡＡに対応するシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する（Ｓ１１０Ａ）。短期秘密鍵生成部１２０Ａは、１≦ｊ≦ＮＡについて、ｕ〜ｊを０以上ｐ−１以下の整数からランダムに選定する（Ｓ１２０Ａ）。交換情報生成部１３０Ａは、
１≦ｊ≦ＮＡについて、ｕｊ＝Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜ｊ）、
Ｘ＝ｇ＾ｕ１、
１≦ｉ≦ＬＡと１≦ｊ≦ＮＡについて、
Ｕｉ，ｊ＝ｇ＾（ｒ（ＭＡ）ｉ，ｊｕｊ）・Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）、
１≦ｉ≦ＬＡとＮＡ＋１≦ｊ≦ＮＭＡＸについて、
Ｕｉ，ｊ＝Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）
を計算する（１３０Ａ）。送信部１４０Ａは、Ｘ、｛Ｕ｝、ＭＡ、ρＡを鍵交換装置１００Ｂに送信する（Ｓ１４０Ａ）。中間情報消去部１８０Ａは、ｕｊ（１≦ｊ≦ＮＡ）を消去する（Ｓ１８０Ａ）。
【００１８】
受信部１４５Ｂは、鍵交換装置１００Ａから、Ｘ、｛Ｕ｝、ＭＡ、ρＡを受信する（Ｓ１４５Ｂ）。属性確認部１５０Ｂは、属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすか、Ｘと｛Ｕ｝が群Ｇの要素かを確認する（Ｓ１５０Ｂ）。
【００１９】
アクセス構造決定部１１０Ｂは、アクセス構造ＡＢを決定し、当該アクセス構造ＡＢに対応するシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する（Ｓ１１０Ｂ）。短期秘密鍵生成部１２０Ｂは、１≦ｊ≦ＮＢについて、ｖ〜ｊを０以上ｐ−１以下の整数からランダムに選定する（Ｓ１２０Ｂ）。交換情報生成部１３０Ｂは、
１≦ｊ≦ＮＢについて、ｖｊ＝Ｈ２（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝，ｖ〜ｊ）、
Ｙ＝ｇ＾ｖ１、
１≦ｉ≦ＬＢと１≦ｊ≦ＮＢについて、
Ｖｉ，ｊ＝ｇ＾（ｒ（ＭＢ）ｉ，ｊｖｊ）・Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）、
１≦ｉ≦ＬＢとＮＢ＋１≦ｊ≦ＮＭＡＸについて、
Ｖｉ，ｊ＝Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）
を計算する（Ｓ１３０Ｂ）。送信部１４０Ｂは、Ｙ、｛Ｖ｝、ＭＢ、ρＢを鍵交換装置１００Ａに送信する（Ｓ１４０Ｂ）。
【００２０】
秘密情報取得部１６０Ｂは、ＩＢ＝｛ｋ：ρＡ（ｋ）∈ＳＢ｝となる集合ＩＢを求め、鍵交換装置１００Ａが生成した秘密情報ｕ１に対する正当なシェア情報集合｛（ＭＡ）ｉ，ｊｕｊ｝について
【００２１】
【数３】
0005650630.tif 000004
【００２２】
が成り立つ０以上ｐ−１以下の整数ｗＢ［ｋ］（ただし、ｋは集合ＩＢの要素）を求める（Ｓ１６０Ｂ）。セッション鍵計算部１７０Ｂは、
【００２３】
【数４】
0005650630.tif 000005
【００２４】
σ２＝（ｇＴ＾ｚ）＾ｖ１
σ３＝Ｘ＾ｖ１
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める（Ｓ１７０Ｂ）。中間情報消去部１８０Ｂは、ｖｊ（１≦ｊ≦ＮＢ）を消去する（Ｓ１８０Ｂ）。
【００２５】
受信部１４５Ａは、鍵交換装置１００Ｂから、Ｙ、｛Ｖ｝、ＭＢ、ρＢを受信する（Ｓ１４５Ａ）。属性確認部１５０Ａは、属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすか、Ｙと｛Ｖ｝が群Ｇの要素かを確認する（Ｓ１５０Ａ）。秘密情報取得部１６０Ａは、ＩＡ＝｛ｋ：ρＢ（ｋ）∈ＳＡ｝となる集合ＩＡを求め、鍵交換装置１００Ｂが生成した秘密情報ｖ１に対する正当なシェア情報集合｛（ＭＢ）ｉ，ｊｖｊ｝について
【００２６】
【数５】
0005650630.tif 000006
【００２７】
が成り立つ０以上ｐ−１以下の整数ｗＡ［ｋ］（ただし、ｋは集合ＩＡの要素）を求める（Ｓ１６０Ａ）。セッション鍵計算部１７０Ａは、
【００２８】
【数６】
0005650630.tif 000007
【００２９】
σ１＝（ｇＴ＾ｚ）＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
σ３＝Ｙ＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める。
【００３０】
この鍵交換システムは、上述のような処理によって鍵交換時にアクセスポリシーを指定でき、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができる。しかしながら、安全性を保証するためには、ハッシュ関数が理想的に安全（ランダムオラクル）でなければならないという問題がある。ランダムオラクルは現実のハッシュ関数を用いては実現できないことが知られている。よって、ランダムオラクルを仮定せずに安全性証明が付く方式が望ましい。
【００３１】
本発明は、非特許文献１の鍵交換技術と同じように鍵交換時にアクセスポリシーを指定できることと、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができることを確保しながら、ランダムオラクルを仮定しない安全な鍵交換技術を提供することを目的とする。
【課題を解決するための手段】
【００３２】
本発明の鍵交換システムは、少なくとも鍵交換装置αと鍵交換装置βとを備える。ここで、κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｆ＿σは任意長の整数を指定された鍵空間Ｋｓｐａｃｅの値σにしたがってκビットの整数に変換する擬似ランダム関数、Ｅｘｔは群Ｇの元を鍵空間Ｋｓｐａｃｅの値に変換する強ランダム抽出器、Ｄは整数、ｄは１以上Ｄ以下の整数、ｇｅｎは検証鍵のビット長がＤであるような使い捨て署名の鍵生成のアルゴリズム、ｓｉｇは検証鍵のビット長がＤであるような使い捨て署名の署名生成のアルゴリズム、ｖｅｒは検証鍵のビット長がＤであるような使い捨て署名の検証のアルゴリズム、ａｔｔ’は属性の全要素数を示す整数、Ｗｄ＿Ｒはｄ番目のダミー属性を示す情報が１ビット以上のビット列Ｒであることを示す記号、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置αの属性を示す属性要素Ｐｎの集合、アクセス構造ＡＡは鍵交換装置αが鍵交換装置βに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉはシェア情報生成行列ＭＡのｉ番目の行に対応するベクトル、属性集合ＳＢは鍵交換装置βの属性を示す属性要素Ｐｎの集合、アクセス構造ＡＢは鍵交換装置βが鍵交換装置αに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉはシェア情報生成行列ＭＢのｉ番目の行に対応するベクトル、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ｎＡは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた１以上ＮＡ以下の整数、ｎＢは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた１以上ＮＢ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、ｈ［１］，…，ｈ［ａｔｔ’］は群Ｇの元、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡは０以上ｐ−１以下の整数、ｔＢは０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ）、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ）、ＴＡ＝ｇ＾ｔＡ、ＴＢ＝ｇ＾ｔＢ、ＳＡ［ｋＡ］＝ｈ［ｋＡ］＾ｔＡ、ＳＢ［ｋＢ］＝ｈ［ｋＢ］＾ｔＢ、｛ＳＡ｝はＳＡ［ｋＡ］の集合、｛ＳＢ｝はＳＢ［ｋＢ］の集合、｛Ｕｉ｝はＵｉの集合、｛Ｘｉ｝はＸｉの集合、｛Ｖｉ｝はＶｉの集合、｛Ｙｉ｝はＹｉの集合、＾はべき乗を示す記号、（＋）はビットごとの排他的論理和を示す記号とする。
【００３３】
鍵交換装置αは、第１の記録部、第１のアクセス構造決定部、第１の短期秘密鍵生成部、第１の交換情報生成部、第１の送信部、第１の受信部、第１の秘密情報取得部、第１の属性確認部、第１のセッション鍵計算部、第１の中間情報消去部を備える。鍵交換装置βは、第２の記録部、第２のアクセス構造決定部、第２の短期秘密鍵生成部、第２の交換情報生成部、第２の送信部、第２の受信部、第２の秘密情報取得部、第２の属性確認部、第２のセッション鍵計算部、第２の中間情報消去部を備える。第１の記録部は、長期秘密鍵としてＳ’Ａ，ＴＡ，｛ＳＡ｝を記録する。第２の記録部は、長期秘密鍵としてＳ’Ｂ，ＴＢ，｛ＳＢ｝を記録する。
【００３４】
第１のアクセス構造決定部は、アクセス構造ＡＡを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋＡと使い捨て秘密鍵ｓｋＡを生成し、ダミー属性集合ＷＡ＝｛Ｗ１＿ｖｋＡ１，…，Ｗｄ＿ｖｋＡｄ，…，ＷＤ＿ｖｋＡＤ｝（ただし、ｖｋＡｄは使い捨て公開鍵ｖｋＡのｄ番目のビット）を設定する。そして、当該アクセス構造ＡＡ又はすべてのダミー属性Ｗ１＿ｖｋＡ１，…，ＷＤ＿ｖｋＡＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する。
【００３５】
第１の短期秘密鍵生成部は、１≦ｊ≦ＮＡについてｕ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｕ＝（ｕ＿１，…，ｕ＿ＮＡ）とし、ｘを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦ＬＡについてｘｉを０以上ｐ−１以下の整数からランダムに選定する。
【００３６】
第１の交換情報生成部は、１≦ｉ≦ＬＡについてベクトルｕとベクトル（ＭＡ）ｉとの内積を計算してシェアλＡｉとする。そして、Ｕ＝ｇ＾ｕ＿ｎＡとＸ＝ｇ＾ｘと、１≦ｉ≦ＬＡについてＵｉ＝ｇ＾（ｒλＡｉ）ｈ［ρＡ（ｉ）］＾（−ｘｉ）とＸｉ＝ｇ＾ｘｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋＡを鍵、（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝）をメッセージとする使い捨て署名ｓＡを生成する。
【００３７】
第１の送信部は、ＥＰＫＡ＝（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ＭＡ，ρＡ，ｖｋＡ，ｓＡ）を鍵交換装置βに送信する。第１の受信部は、鍵交換装置βから、ＥＰＫＢ＝（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ＭＢ，ρＢ，ｖｋＢ，ｓＢ）を受信する。
【００３８】
第１の秘密情報取得部は、ＩＡ＝｛ｉ：ρＢ（ｉ）∈ＳＡ｝となる集合ＩＡとＩ’Ａ＝｛ｉ：ρＢ（ｉ）∈ＷＢ｝となる集合Ｉ’Ａを求め、シェア情報生成行列ＭＢに対応する秘密情報ｖ＿ｎＢの正当なシェア集合｛λＢｉ｝について、
【００３９】
【数７】
0005650630.tif 000008
【００４０】
が成り立つ０以上ｐ−１以下の整数ｗＡｉと整数ｗ’Ａｉを求める。
【００４１】
第１の属性確認部は、属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすかを確認することと、Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋＢを鍵、（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ｓＢ）をメッセージとして検証した結果が真であること、
【００４２】
【数８】
0005650630.tif 000009
【００４３】
が成り立つことを確認する。
第１のセッション鍵計算部は、
【００４４】
【数９】
0005650630.tif 000010
【００４５】
σ１＝（ｇＴ＾ｚ）＾ｕ＿ｎＡ
σ３＝ｅ（ｇ＾ｒ，Ｙ）＾ｘ
を計算し、σ’１←Ｅｘｔ（σ１），σ’２←Ｅｘｔ（σ２），σ’３←Ｅｘｔ（σ３）を計算し、セッション識別子ｓｉｄを（ＥＰＫＡ，ＥＰＫＢ）に設定し、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’１（ｓｉｄ）（＋）Ｆ＿σ’２（ｓｉｄ）（＋）Ｆ＿σ’３（ｓｉｄ）
のように求める。
【００４６】
第１の中間情報消去部は、少なくともｕ＿ｊ（１≦ｊ≦ＮＡ）、ｘ、ｘｉ（１≦ｉ≦ＬＡ）、ＥＰＫＡ、ＥＰＫＢ、σ１、σ２、σ３、σ’１、σ’２、σ’３、ｓｉｄ、ｓｋＡを消去する。
【００４７】
第２のアクセス構造決定部は、アクセス構造ＡＢを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋＢと使い捨て秘密鍵ｓｋＢを生成し、ダミー属性集合ＷＢ＝｛Ｗ１＿ｖｋＢ１，…，Ｗｄ＿ｖｋＢｄ，…，ＷＤ＿ｖｋＢＤ｝（ただし、ｖｋＢｄは使い捨て公開鍵ｖｋＢのｄ番目のビット）を設定する。そして、当該アクセス構造ＡＢ又はすべてのダミー属性Ｗ１＿ｖｋＢ１，…，ＷＤ＿ｖｋＢＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する。
【００４８】
第２の短期秘密鍵生成部は、１≦ｊ≦ＮＢについてｖ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｖ＝（ｖ＿１，…，ｖ＿ＮＢ）とし、ｙを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦ＬＢについてｙｉを０以上ｐ−１以下の整数からランダムに選定する。
【００４９】
第２の交換情報生成部は、１≦ｉ≦ＬＢについてベクトルｖとベクトル（ＭＢ）ｉとの内積を計算してシェアλＢｉとする。そして、Ｖ＝ｇ＾ｖ＿ｎＢとＹ＝ｇ＾ｙと、１≦ｉ≦ＬＢについてＶｉ＝ｇ＾（ｒλＢｉ）ｈ［ρＢ（ｉ）］＾（−ｙｉ）とＹｉ＝ｇ＾ｙｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋＢを鍵、（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝）をメッセージとする使い捨て署名ｓＢを生成する。
【００５０】
第２の送信部は、ＥＰＫＢ＝（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ＭＢ，ρＢ，ｖｋＢ，ｓＢ）を鍵交換装置αに送信する。第２の受信部は、鍵交換装置αから、ＥＰＫＡ＝（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ＭＡ，ρＡ，ｖｋＡ，ｓＡ）を受信する。
【００５１】
第２の秘密情報取得部は、ＩＢ＝｛ｉ：ρＡ（ｉ）∈ＳＢ｝となる集合ＩＢとＩ’Ｂ＝｛ｉ：ρＡ（ｉ）∈ＷＡ｝となる集合Ｉ’Ｂを求め、シェア情報生成行列ＭＡに対応する秘密情報ｕ＿ｎＡの正当なシェア集合｛λＡｉ｝について、
【００５２】
【数１０】
0005650630.tif 000011
【００５３】
が成り立つ０以上ｐ−１以下の整数ｗＢｉと整数ｗ’Ｂｉを求める。
【００５４】
第２の属性確認部は、属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすかを確認することと、Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋＡを鍵、（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ｓＡ）をメッセージとして検証した結果が真であること、
【００５５】
【数１１】
0005650630.tif 000012
【００５６】
が成り立つことを確認する。
第２のセッション鍵計算部は、
【００５７】
【数１２】
0005650630.tif 000013
【００５８】
σ２＝（ｇＴ＾ｚ）＾ｖ＿ｎＢ
σ３＝ｅ（ｇ＾ｒ，Ｘ）＾ｙ
を計算し、σ’１←Ｅｘｔ（σ１），σ’２←Ｅｘｔ（σ２），σ’３←Ｅｘｔ（σ３）を計算し、セッション識別子ｓｉｄを（ＥＰＫＡ，ＥＰＫＢ）に設定し、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’１（ｓｉｄ）（＋）Ｆ＿σ’２（ｓｉｄ）（＋）Ｆ＿σ’３（ｓｉｄ）
のように求める。
【００５９】
第２の中間情報消去部は、少なくともｖ＿ｊ（１≦ｊ≦ＮＢ）、ｙ、ｙｉ（１≦ｉ≦ＬＢ）、ＥＰＫＡ、ＥＰＫＢ、σ１、σ２、σ３、σ’１、σ’２、σ’３、ｓｉｄ、ｓｋＢを消去する。
【００６０】
なお、本発明の鍵交換システムは、さらに、マスタ鍵生成部と長期秘密鍵生成部とを有する鍵生成装置を備えてもよい。この場合は、マスタ鍵生成部が、ｒ，ｚ，ｈ［１］，…，ｈ［ａｔｔ’］をランダムに選定し、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）とマスタ秘密鍵ｇ＾ｚを生成すればよい。また、長期秘密鍵生成部がｔＡとｔＢをランダムに選定し、Ｓ’ＡとＳ’Ｂ、ＴＡとＴＢ、ＳＡ［ｋＡ］とＳＢ［ｋＢ］を計算すればよい。
【発明の効果】
【００６１】
本発明の鍵交換システムによれば、線形秘密分散法を利用することにより、鍵抽出（長期秘密鍵の生成）を行うときには鍵生成装置が、鍵交換装置α、βの属性集合ＳＡ、ＳＢに基づき線形秘密分散法のシェア情報として長期秘密鍵（Ｓ’Ａ，ＴＡ，｛ＳＡ｝）、（Ｓ’Ｂ，ＴＢ，｛ＳＢ｝）を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造ＡＡ、ＡＢを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定することが可能である。また、本発明のマスタ秘密鍵ｇ＾ｚとマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）は、属性集合とは独立なので、属性の全体集合をあらかじめ決めておく必要がない。つまり、鍵抽出時に任意の属性に基づき長期秘密鍵を発行することができる。したがって、非特許文献１と同等の効果が得られる。
【００６２】
さらに、使い捨て署名、強ランダム抽出器、擬似ランダム関数を用いることにより、以下のように、ランダムオラクルを仮定しないで安全性を確保できる。鍵交換を行うユーザは、本来認証に用いる自分の属性集合Ｓ以外に、ダミー属性集合Ｗを用意し、生成した使い捨て署名の検証鍵の値にＷを割り当てる。この時、ユーザは相手が満たすことを希望するアクセス構造Ａに加えて、特定の検証鍵に対応したダミー属性集合Ｗが満たすようなアクセス構造を認証条件として加えて、鍵交換を行う。ダミー属性集合Ｗの方は、実際のユーザ同士が行う鍵交換セッションでは使われることはない。しかし、安全性証明の中で送られてきたメッセージが正しいかどうかを判定する際に、ダミー属性集合Ｗの方の認証条件を用いることにより、アクセス構造Ａを満たす属性集合に対応する秘密鍵の知識なしで判定することができる。また、最後のセッション鍵の導出の時に、ランダムオラクルではなく、強ランダム抽出器と擬似ランダム関数を用いる。具体的には、強ランダム抽出器で共有情報の分布をならし、その値を擬似ランダム関数の鍵とすることで出力をセッション鍵とする。このように、本発明ではランダムオラクルを仮定すること無しに安全性を保つことができる。
【図面の簡単な説明】
【００６３】
【図１】特願２０１０−２５９０５３の鍵交換システムの構成例を示す図。
【図２】特願２０１０−２５９０５３の鍵交換装置の機能構成例を示す図。
【図３】特願２０１０−２５９０５３の鍵生成装置の機能構成例を示す図。
【図４】特願２０１０−２５９０５３のマスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す図。
【図５】特願２０１０−２５９０５３のセッション鍵を共有する鍵交換の処理のフローの例を示す図。
【図６】本発明の鍵交換システムの構成例を示す図。
【図７】本発明の鍵交換装置の機能構成例を示す図。
【図８】本発明の鍵生成装置の機能構成例を示す図。
【図９】本発明のマスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す図。
【図１０】本発明のセッション鍵を共有する鍵交換の処理のフローの例を示す図。
【発明を実施するための形態】
【００６４】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００６５】
［準備］
本発明の鍵交換システムについて説明する前に、本発明を理解する上で必要な理論について説明する。本発明では、アクセスポリシーを次のようなアクセス構造として表すものとする。
【００６６】
まず、｛Ｐ１，Ｐ２，…，Ｐｎ，…，ＰＮ｝を属性集合とする。ただし、Ｎは整数、ｎは１以上Ｎ以下の整数である。Ｐｎは、例えば、「性別が男性である。」や「○○会社の社員である。」などの鍵生成装置の利用者（ユーザ）の属性を示している。なお、以下の説明では、「鍵生成装置の利用者の属性」を単に「鍵生成装置の属性」と表現する。アクセス構造は｛Ｐ１，Ｐ２，…，ＰＮ｝の空でない部分集合のべき集合Ａとして表わす。すなわち、
Ａ⊆２＾｛Ｐ１，Ｐ２，…，ＰＮ｝＼｛φ｝
ただし、“＾”はべき乗を示す記号、“φ”は空集合を示す記号、“＼｛φ｝”は空集合を除くことを示す記号
に属する集合を許可集合、属さない集合を不許可集合とよぶ。本発明では、上記のアクセス構造に基づきアクセスコントロールを行うために次のように線形秘密分散法を用いる。
【００６７】
各属性集合に対応するシェア情報は０以上ｐ−１以下の整数の集合ＺＰ上のベクトルとして表される。シェア情報を生成する行列としてＬ行Ｎ列のシェア情報生成行列Ｍを次のように用意する。ｉ＝１，…，Ｌについて、属性ラベリング関数ρを用いてシェア情報生成行列Ｍのｉ行目を属性ρ（ｉ）に対応させる。属性ラベリング関数ρは、ｉを特定すると属性ρ（ｉ）が決まる関数である。また、「属性ρ（ｉ）に対応させる」とは、例えば、属性ρ（１）がＰ１∧Ｐ２∧Ｐ３であれば、１，１，１，０，０，…，０のようにシェア情報生成行列Ｍの１行目を設定し、属性ρ（２）がＰ１∧ＰＮであれば、１，０，０，…，０，１のようにシェア情報生成行列Ｍの２行目を設定するように、属性ρ（ｉ）と対応させてｉ行目を決めることである。なお、上記の例では、アンド条件に含まれる属性Ｐｎに対応する要素を“１”とし、含まれない属性Ｐｎに対応する要素を“０”としたが、これに限る必要はない。異なる条件に対応する行が同じ行にならないように対応付けされていればよいので、属性ラベリング関数ρは単射性を有する範囲で他の対応でもよい。
【００６８】
次に、０以上ｐ−１以下の整数からｒ１，…，ｒＮをランダムに選び、ベクトルｖ＝（ｒ１，…，ｒＮ）Ｔを生成する。ただし、Ｔは転置を示す記号である。また、あらかじめ定めておいたｎ番目の要素ｒｎを秘密情報とする。なお、鍵交換したい装置同士の場合、秘密情報として共有する情報が同じであれば任意の情報でかまわないので、ランダムに選んだ整数の何番目を秘密情報にするかをあらかじめ決めておけばよい。この時、Ｍは秘密情報ｒｎのＬ個のシェア情報のベクトルとなる。属性集合ρ（ｉ）にシェア情報（Ｍｖ）ｉを割り当てる。ただし、（Ｍｖ）ｉはベクトルＭｖのｉ番目の成分を示している。
【００６９】
このようにシェア情報生成行列Ｍと秘密情報を含む列ベクトルｖを用いると、線形秘密分散法の線形復元性を利用できる。ここで、線形復元性について説明する。あるアクセス構造Ａを考え、属性集合ＳをＳ∈Ａの任意の許可集合とし、Ｉ⊂｛１，２，…，Ｌ｝をＩ＝｛ｉ：ρ（ｉ）∈Ｓ｝と定義する。このとき、｛λｉ｝がｒｎの正しいシェア情報の集合の場合、
【００７０】
【数１３】
0005650630.tif 000014
【００７１】
となるような０以上ｐ−１以下の整数の集合｛ｗｉ｝が存在する。このような集合｛ｗｉ｝はＭのサイズの多項式時間で見つけられることが知られている。一方、｛λｉ｝がｒｎの正しいシェア情報の集合でない場合、集合｛ｗｉ｝のすべての要素を求めることができない。本発明では、上述のようにシェア情報生成行列Ｍと秘密情報を含む列ベクトルｖを用いることで、線形秘密分散法の線形復元性を利用してセッション鍵を交換する。
【００７２】
［構成］
図６に本発明の鍵交換システムの構成例を示す。本発明の鍵交換システムは、ネットワーク１０００を介して接続された鍵交換装置５００１，…，５００Ｑ（ただし、Ｑは２以上の整数、ｑは１以上Ｑ以下の整数、ＡとＢは１以上Ｑ以下の異なる整数）、鍵生成装置６００で構成される。図７に本発明の鍵交換装置の機能構成例、図８に本発明の鍵生成装置の機能構成例を示す。鍵交換装置５００ｑは、アクセス構造決定部５１０ｑ、短期秘密鍵生成部５２０ｑ、交換情報生成部５３０ｑ、送信部５４０ｑ、受信部５４５ｑ、属性確認部５５０ｑ、秘密情報取得部５６０ｑ、セッション鍵計算部５７０ｑ、中間情報消去部５８０ｑ、記録部５９０ｑを備える。また、鍵生成装置６００は、マスタ鍵生成部６１０、長期秘密鍵生成部６２０、記録部６９０を備える。以下の説明では、鍵交換装置５００Ａ（鍵交換装置αに相当）がイニシエータとして機能し、鍵交換装置５００Ｂ（鍵交換装置βに相当）がレスポンダとして機能してセッション鍵を共有する場合について説明する。
【００７３】
なお、以下の説明では、κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｆ＿σは任意長の整数を指定された鍵空間Ｋｓｐａｃｅの値σにしたがってκビットの整数に変換する擬似ランダム関数、Ｅｘｔは群Ｇの元を鍵空間Ｋｓｐａｃｅの値に変換する強ランダム抽出器、Ｄは整数（ダミー属性の要素数）、ｄは１以上Ｄ以下の整数、ｇｅｎは検証鍵のビット長がＤであるような使い捨て署名の鍵生成のアルゴリズム、ｓｉｇは検証鍵のビット長がＤであるような使い捨て署名の署名生成のアルゴリズム、ｖｅｒは検証鍵のビット長がＤであるような使い捨て署名の検証のアルゴリズム、ａｔｔ’は属性の全要素数を示す整数（実際の属性とダミー属性の両方を合わせた全要素数）、Ｗｄ＿Ｒはｄ番目のダミー属性を示す情報が１ビット以上のビット列Ｒであることを示す記号（本明細書では、１ビットの場合もビット列と呼ぶことにする）、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置５００Ａの属性を示す属性要素Ｐｎの集合、アクセス構造ＡＡは鍵交換装置５００Ａが鍵交換装置５００Ｂに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡはアクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）はアクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉはシェア情報生成行列ＭＡのｉ番目の行に対応するベクトル、属性集合ＳＢは鍵交換装置５００Ｂの属性を示す属性要素Ｐｎの集合、アクセス構造ＡＢは鍵交換装置５００Ｂが鍵交換装置５００Ａに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢはアクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）はアクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉはシェア情報生成行列ＭＢのｉ番目の行に対応するベクトル、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ｎＡは鍵交換装置５００Ａと鍵交換装置５００Ｂとで共有するあらかじめ定めた１以上ＮＡ以下の整数、ｎＢは鍵交換装置５００Ａと鍵交換装置５００Ｂとで共有するあらかじめ定めた１以上ＮＢ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、ｔＢは０以上ｐ−１以下の整数、ｈ［１］，…，ｈ［ａｔｔ’］は群Ｇの元、｛ＳＡ｝はＳＡ［ｋＡ］の集合、｛ＳＢ｝はＳＢ［ｋＢ］の集合、｛Ｕｉ｝はＵｉの集合、｛Ｘｉ｝はＸｉの集合、｛Ｖｉ｝はＶｉの集合、｛Ｙｉ｝はＹｉの集合、＾はべき乗を示す記号、（＋）はビットごとの排他的論理和を示す記号とする。
【００７４】
［鍵生成、鍵抽出］
図９に、マスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す。なお、長期秘密鍵生成の処理が鍵抽出に相当する。鍵生成装置６００のマスタ鍵生成部６１０は、０以上ｐ−１以下の整数からランダムにｒ、ｚを選定し、群Ｇの元からランダムにｈ［１］，…，ｈ［ａｔｔ’］を選定する。そして、マスタ公開鍵を（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）、マスタ秘密鍵をｇ＾ｚとして記録部３９０に記録し、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）を公開する（Ｓ６１０）。鍵交換装置５００Ａと鍵交換装置５００Ｂは、それぞれマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）を受信し、記録部５９０Ａと記録部５９０Ｂに記録する（Ｓ５９１，Ｓ５９２）。
【００７５】
長期秘密鍵生成部６２０は、０以上ｐ−１以下の整数からランダムにｔＡを選定し、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ）、ＴＡ＝ｇ＾ｔＡ、属性集合ＳＡの要素ｋＡについてＳＡ［ｋＡ］＝ｈ［ｋＡ］＾ｔＡを計算し、長期秘密鍵として（Ｓ’Ａ，ＴＡ，｛ＳＡ｝）を鍵交換装置５００Ａに送信する（Ｓ６２０Ａ）。鍵交換装置５００Ａは、長期秘密鍵（Ｓ’Ａ，ＴＡ，｛ＳＡ｝）を受信し、記録部５９０Ａに記録する（Ｓ５９２Ａ）。
【００７６】
さらに、長期秘密鍵生成部６２０は、０以上ｐ−１以下の整数からランダムにｔＢを選定し、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ）、ＴＢ＝ｇ＾ｔＢ、属性集合ＳＢの要素ｋＢについてＳＢ［ｋＢ］＝ｈ［ｋＢ］＾ｔＢを計算し、長期秘密鍵として（Ｓ’Ｂ，ＴＢ，｛ＳＢ｝）を鍵交換装置５００Ｂに送信する（Ｓ６２０Ｂ）。鍵交換装置５００Ｂは、長期秘密鍵（Ｓ’Ｂ，ＴＢ，｛ＳＢ｝）を受信し、記録部５９０Ｂに記録する（Ｓ５９２Ｂ）。
【００７７】
なお、あらかじめ鍵交換装置５００Ａの記録部５９０Ａにマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）と長期秘密鍵（Ｓ’Ａ，ＴＡ，｛ＳＡ｝）とを記録させ、鍵交換装置５００Ｂの記録部５９０Ｂにマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）と長期秘密鍵（Ｓ’Ｂ，ＴＢ，｛ＳＢ｝）とを記録させておけば、ネットワーク１０００を介して接続された鍵交換装置５００Ａと鍵交換装置５００Ｂだけで最低限の鍵交換システムが構成できる。
【００７８】
［鍵交換］
図１０にセッション鍵を共有する鍵交換の処理のフローの例を示す。この例は、鍵交換装置５００Ａ（鍵交換装置αに相当）がイニシエータとして機能し、鍵交換装置５００Ｂ（鍵交換装置βに相当）がレスポンダとして機能する場合を示している。
【００７９】
鍵交換装置５００Ａは、アクセス構造決定部５１０Ａ（第１のアクセス構造決定部）、短期秘密鍵生成部５２０Ａ（第１の短期秘密鍵生成部）、交換情報生成部５３０Ａ（第１の交換情報生成部）、送信部５４０Ａ（第１の送信部）、受信部５４５Ａ（第１の受信部）、属性確認部５５０Ａ（第１の属性確認部）、秘密情報取得部５６０Ａ（第１の秘密情報取得部）、セッション鍵計算部５７０Ａ（第１のセッション鍵計算部）、中間情報消去部５８０Ａ（第１の中間情報消去部）、記録部５９０Ａ（第１の記録部）を備える。鍵交換装置５００Ｂは、アクセス構造決定部５１０Ｂ（第２のアクセス構造決定部）、短期秘密鍵生成部５２０Ｂ（第２の短期秘密鍵生成部）、交換情報生成部５３０Ｂ（第２の交換情報生成部）、送信部５４０Ｂ（第２の送信部）、受信部５４５Ｂ（第２の受信部）、属性確認部５５０Ｂ（第２の属性確認部）、秘密情報取得部５６０Ｂ（第２の秘密情報取得部）、セッション鍵計算部５７０Ｂ（第２のセッション鍵計算部）、中間情報消去部５８０Ｂ（第２の中間情報消去部）、記録部５９０Ｂ（第２の記録部）を備える。
【００８０】
鍵交換装置５００Ａでは、記録部５９０Ａが長期秘密鍵としてＳ’Ａ，ＴＡ，｛ＳＡ｝を記録している。アクセス構造決定部５１０Ａは、アクセス構造ＡＡを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋＡと使い捨て秘密鍵ｓｋＡを生成し、ダミー属性集合ＷＡ＝｛Ｗ１＿ｖｋＡ１，…，Ｗｄ＿ｖｋＡｄ，…，ＷＤ＿ｖｋＡＤ｝（ただし、ｖｋＡｄは使い捨て公開鍵ｖｋＡのｄ番目のビット）を設定する。そして、アクセス構造ＡＡ又はすべてのダミー属性Ｗ１＿ｖｋＡ１，…，ＷＤ＿ｖｋＡＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する（Ｓ５１０Ａ）。
【００８１】
短期秘密鍵生成部５２０Ａは、１≦ｊ≦ＮＡについてｕ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｕ＝（ｕ＿１，…，ｕ＿ＮＡ）とし、ｘを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦ＬＡについてｘｉを０以上ｐ−１以下の整数からランダムに選定する（Ｓ５２０Ａ）。
【００８２】
交換情報生成部５３０Ａは、１≦ｉ≦ＬＡについてベクトルｕとベクトル（ＭＡ）ｉとの内積を計算してシェアλＡｉとする。そして、
Ｕ＝ｇ＾ｕ＿ｎＡ
Ｘ＝ｇ＾ｘ
Ｕｉ＝ｇ＾（ｒλＡｉ）ｈ［ρＡ（ｉ）］＾（−ｘｉ）  ただし、１≦ｉ≦ＬＡ
Ｘｉ＝ｇ＾ｘｉ  ただし、１≦ｉ≦ＬＡ
を計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋＡを鍵、（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝）をメッセージとする使い捨て署名ｓＡを生成する（Ｓ５３０Ａ）。
【００８３】
第１の送信部５４０Ａは、ＥＰＫＡ＝（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ＭＡ，ρＡ，ｖｋＡ，ｓＡ）を鍵交換装置５００Ｂに送信する（Ｓ５４０Ａ）。
【００８４】
一方、鍵交換装置５００Ｂでは、記録部５９０Ｂが長期秘密鍵としてＳ’Ｂ，ＴＢ，｛ＳＢ｝を記録している。そして、アクセス構造決定部５１０Ｂは、アクセス構造ＡＢを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋＢと使い捨て秘密鍵ｓｋＢを生成し、ダミー属性集合ＷＢ＝｛Ｗ１＿ｖｋＢ１，…，Ｗｄ＿ｖｋＢｄ，…，ＷＤ＿ｖｋＢＤ｝（ただし、ｖｋＢｄは使い捨て公開鍵ｖｋＢのｄ番目のビット）を設定する。そして、アクセス構造ＡＢ又はすべてのダミー属性Ｗ１＿ｖｋＢ１，…，ＷＤ＿ｖｋＢＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する（Ｓ５１０Ｂ）。
【００８５】
短期秘密鍵生成部５２０Ｂは、１≦ｊ≦ＮＢについてｖ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｖ＝（ｖ＿１，…，ｖ＿ＮＢ）とし、ｙを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦ＬＢについてｙｉを０以上ｐ−１以下の整数からランダムに選定する（Ｓ５２０Ｂ）。
【００８６】
交換情報生成部５３０Ｂは、１≦ｉ≦ＬＢについてベクトルｖとベクトル（ＭＢ）ｉとの内積を計算してシェアλＢｉとする。そして、
Ｖ＝ｇ＾ｖ＿ｎＢ
Ｙ＝ｇ＾ｙ
Ｖｉ＝ｇ＾（ｒλＢｉ）ｈ［ρＢ（ｉ）］＾（−ｙｉ）  ただし、１≦ｉ≦ＬＢ
Ｙｉ＝ｇ＾ｙｉ  ただし、１≦ｉ≦ＬＢ
を計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋＢを鍵、（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝）をメッセージとする使い捨て署名ｓＢを生成する（Ｓ５３０Ｂ）。
【００８７】
送信部５４０Ｂは、ＥＰＫＢ＝（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ＭＢ，ρＢ，ｖｋＢ，ｓＢ）を鍵交換装置５００Ａに送信する（Ｓ５４０Ｂ）。
【００８８】
受信部５４５Ｂは、鍵交換装置５００Ａから、ＥＰＫＡ＝（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ＭＡ，ρＡ，ｖｋＡ，ｓＡ）を受信する（Ｓ５４５Ｂ）。
【００８９】
属性確認部５５０Ｂは、属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすかを確認する。そして、満たさないと判断した場合は処理を中止する。満たすと判断した場合は、ステップＳ５６０Ｂに進む（Ｓ５５１Ｂ）。
【００９０】
秘密情報取得部５６０Ｂは、ＩＢ＝｛ｉ：ρＡ（ｉ）∈ＳＢ｝となる集合ＩＢとＩ’Ｂ＝｛ｉ：ρＡ（ｉ）∈ＷＡ｝となる集合Ｉ’Ｂを求める。そして、シェア情報生成行列ＭＡに対応する秘密情報ｕ＿ｎＡの正当なシェア集合｛λＡｉ｝について、
【００９１】
【数１４】
0005650630.tif 000015
【００９２】
が成り立つ０以上ｐ−１以下の整数ｗＢｉと整数ｗ’Ｂｉを求める（Ｓ５６０Ｂ）。上述のように、ｎＡは鍵交換装置５００Ａと鍵交換装置５００Ｂとで共有するあらかじめ定めた１以上ＮＡ以下の整数であればよい。例えば、ｎＡ＝１とすればよい。
【００９３】
属性確認部５５０Ｂは、Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋＡを鍵、（Ｕ，｛Ｕｉ｝，Ｘ，｛Ｘｉ｝，ｓＡ）をメッセージとして検証した結果が真であること、
【００９４】
【数１５】
0005650630.tif 000016
【００９５】
が成り立つことを確認する。そして、いずれかの条件を満足しない場合には処理を中止する。すべての条件を満足する場合はステップＳ３７０Ｂに進む（Ｓ３５２Ｂ）。
セッション鍵計算部５７０Ｂは、
【００９６】
【数１６】
0005650630.tif 000017
【００９７】
σ２＝（ｇＴ＾ｚ）＾ｖ＿ｎＢ
σ３＝ｅ（ｇ＾ｒ，Ｘ）＾ｙ
を計算する。そして、σ’１←Ｅｘｔ（σ１），σ’２←Ｅｘｔ（σ２），σ’３←Ｅｘｔ（σ３）を計算し、セッション識別子ｓｉｄを（ＥＰＫＡ，ＥＰＫＢ）に設定する。さらに、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’１（ｓｉｄ）（＋）Ｆ＿σ’２（ｓｉｄ）（＋）Ｆ＿σ’３（ｓｉｄ）
のように求める（Ｓ５７０Ｂ）。
【００９８】
中間情報消去部５８０Ｂは、少なくともｖ＿ｊ（１≦ｊ≦ＮＢ）、ｙ、ｙｉ（１≦ｉ≦ＬＢ）、ＥＰＫＡ、ＥＰＫＢ、σ１、σ２、σ３、σ’１、σ’２、σ’３、ｓｉｄ、ｓｋＢを消去する（Ｓ５８０Ｂ）。一般的には、セッション鍵Ｋ以外の計算の途中で使用した値をすべて消去すればよい。
【００９９】
鍵交換装置５００Ａの処理に戻る。受信部５４５Ａは、鍵交換装置５００Ｂから、ＥＰＫＢ＝（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ＭＢ，ρＢ，ｖｋＢ，ｓＢ）を受信する（Ｓ５４５Ａ）。
【０１００】
属性確認部５５０Ａは、属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすかを確認する。そして、満たさないと判断した場合は処理を中止する。満たすと判断した場合は、ステップＳ５６０Ａに進む（Ｓ５５１Ａ）。
【０１０１】
秘密情報取得部５６０Ａは、ＩＡ＝｛ｉ：ρＢ（ｉ）∈ＳＡ｝となる集合ＩＡとＩ’Ａ＝｛ｉ：ρＢ（ｉ）∈ＷＢ｝となる集合Ｉ’Ａを求める。そして、シェア情報生成行列ＭＢに対応する秘密情報ｖ＿ｎＢの正当なシェア集合｛λＢｉ｝について、
【０１０２】
【数１７】
0005650630.tif 000018
【０１０３】
が成り立つ０以上ｐ−１以下の整数ｗＡｉと整数ｗ’Ａｉを求める（Ｓ５６０Ａ）。上述のように、ｎＢは鍵交換装置５００Ａと鍵交換装置５００Ｂとで共有するあらかじめ定めた１以上ＮＢ以下の整数であればよい。例えば、ｎＢ＝１とすればよい。
【０１０４】
属性確認部５５０Ａは、Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋＢを鍵、（Ｖ，｛Ｖｉ｝，Ｙ，｛Ｙｉ｝，ｓＢ）をメッセージとして検証した結果が真であること、
【０１０５】
【数１８】
0005650630.tif 000019
【０１０６】
が成り立つことを確認する。そして、いずれかの条件を満足しない場合には処理を中止する。すべての条件を満足する場合はステップＳ５７０Ａに進む（Ｓ５５２Ａ）。
セッション鍵計算部５７０Ａは、
【０１０７】
【数１９】
0005650630.tif 000020
【０１０８】
σ１＝（ｇＴ＾ｚ）＾ｕ＿ｎＡ
σ３＝ｅ（ｇ＾ｒ，Ｙ）＾ｘ
を計算する。そして、σ’１←Ｅｘｔ（σ１），σ’２←Ｅｘｔ（σ２），σ’３←Ｅｘｔ（σ３）を計算し、セッション識別子ｓｉｄを（ＥＰＫＡ，ＥＰＫＢ）に設定する。さらに、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’１（ｓｉｄ）（＋）Ｆ＿σ’２（ｓｉｄ）（＋）Ｆ＿σ’３（ｓｉｄ）
のように求める（Ｓ５７０Ａ）。
【０１０９】
中間情報消去部５８０Ａは、少なくともｕ＿ｊ（１≦ｊ≦ＮＡ）、ｘ、ｘｉ（１≦ｉ≦ＬＡ）、ＥＰＫＡ、ＥＰＫＢ、σ１、σ２、σ３、σ’１、σ’２、σ’３、ｓｉｄ、ｓｋＡを消去する（Ｓ５８０Ａ）。一般的には、セッション鍵Ｋ以外の計算の途中で使用した値をすべて消去すればよい。
【０１１０】
［確認］
最後に鍵交換装置１００Ａと鍵交換装置１００Ｂが取得したセッション鍵Ｋが等しいことを説明する。
【０１１１】
【数２０】
0005650630.tif 000021
【０１１２】
【数２１】
0005650630.tif 000022
【０１１３】
σ３＝ｅ（ｇ＾ｒ，Ｘ）＾ｙ
＝ｇＴ＾（ｒｘｙ）＝ｅ（ｇ＾ｒ，Ｙ）＾ｘ
よって、正しくセッション鍵を共有できる。
【０１１４】
本発明の鍵交換システムによれば、線形秘密分散法を利用することにより、鍵抽出（長期秘密鍵の生成）を行うときには鍵生成装置が、鍵交換装置５００Ａ、５００Ｂの属性集合ＳＡ、ＳＢに基づき線形秘密分散法のシェア情報として長期秘密鍵（Ｓ’Ａ，ＴＡ，｛ＳＡ｝）、（Ｓ’Ｂ，ＴＢ，｛ＳＢ｝）を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造ＡＡ、ＡＢを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定することが可能である。また、本発明のマスタ秘密鍵ｇ＾ｚとマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）は、属性集合とは独立なので、属性の全体集合をあらかじめ決めておく必要がない。つまり、鍵抽出時に任意の属性に基づき長期秘密鍵を発行することができる。したがって、非特許文献１と同等の効果が得られる。
【０１１５】
さらに、使い捨て署名、強ランダム抽出器、擬似ランダム関数を用いることにより、以下のように、ランダムオラクルを仮定しないで安全性を確保できる。鍵交換を行うユーザは、本来認証に用いる自分の属性集合Ｓ以外に、ダミー属性集合Ｗを用意し、生成した使い捨て署名の検証鍵の値にＷを割り当てる。この時、ユーザは相手が満たすことを希望するアクセス構造Ａに加えて、特定の検証鍵に対応したダミー属性集合Ｗが満たすようなアクセス構造を認証条件として加えて、鍵交換を行う。ダミー属性集合Ｗの方は、実際のユーザ同士が行う鍵交換セッションでは使われることはない。しかし、安全性証明の中で送られてきたメッセージが正しいかどうかを判定する際に、ダミー属性集合Ｗの方の認証条件を用いることにより、アクセス構造Ａを満たす属性集合に対応する秘密鍵の知識なしで判定することができる。また、最後のセッション鍵の導出の時に、ランダムオラクルではなく、強ランダム抽出器と擬似ランダム関数を用いる。具体的には、強ランダム抽出器で共有情報の分布をならし、その値を擬似ランダム関数の鍵とすることで出力をセッション鍵とする。このように、本発明ではランダムオラクルを仮定すること無しに安全性を保つことができる。
【０１１６】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１１７】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１１８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１１９】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１２１】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１２２】
本発明は、二者間でセッション鍵を共有した暗号通信に利用することができる。
【符号の説明】
【０１２３】
１００ｑ、５００ｑ  鍵交換装置            １１０ｑ、５１０ｑ  アクセス構造決定部
１２０ｑ、５２０ｑ  短期秘密鍵生成部      １３０ｑ、５３０ｑ  交換情報生成部
１４０ｑ、５４０ｑ  送信部                １４５ｑ、５４５ｑ  受信部
１５０ｑ、５５０ｑ  属性確認部            １６０ｑ、５６０ｑ  秘密情報取得部
１７０ｑ、５７０ｑ  セッション鍵計算部    １８０ｑ、５８０ｑ  中間情報消去部
１９０ｑ、３９０、５９０ｑ、６９０  記録部
３００、６００  鍵生成装置              ３１０、６１０  マスタ鍵生成部
３２０、６２０  長期秘密鍵生成部        １０００  ネットワーク
【図１】
0005650630.tif 000041
【図２】
0005650630.tif 000042
【図３】
0005650630.tif 000043
【図４】
0005650630.tif 000044
【図５】
0005650630.tif 000045
【図６】
0005650630.tif 000046
【図７】
0005650630.tif 000047
【図８】
0005650630.tif 000048
【図９】
0005650630.tif 000049
【図１０】
0005650630.tif 000050