JP5650630B2 - 鍵交換システム、鍵交換装置、鍵交換方法、鍵交換プログラム - Google Patents

Description

本発明は情報セキュリティに関するものであり、特に、二者間でセッション鍵を共有するための鍵交換システム、鍵交換装置、鍵生成装置、鍵交換方法、鍵交換プログラムに関する。

鍵交換時にアクセスポリシーを指定でき、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができる鍵交換システムについて、非特許文献１に公開されている。

Kazuki Yoneyama, "Strongly Secure Two-Pass Attribute-Based Authenti-cated Key Exchange", Pairing 2010, LNCS 6487, pp147-166, 2010.

非特許文献１に対応する内容は、本願出願時には未公開の特願２０１０−２５９０５３に記載されており、以下のとおりである。

［構成］
図１に特願２０１０−２５９０５３の鍵交換システムの構成例を示す。鍵交換システムは、ネットワーク１０００を介して接続された鍵交換装置１００_１，…，１００_Ｑ（ただし、Ｑは２以上の整数、ｑは１以上Ｑ以下の整数、ＡとＢは１以上Ｑ以下の異なる整数）、鍵生成装置３００で構成される。図２に鍵交換装置の機能構成例、図３に鍵生成装置の機能構成例を示す。鍵交換装置１００_ｑは、アクセス構造決定部１１０_ｑ、短期秘密鍵生成部１２０_ｑ、交換情報生成部１３０_ｑ、送信部１４０_ｑ、受信部１４５_ｑ、属性確認部１５０_ｑ、秘密情報取得部１６０_ｑ、セッション鍵計算部１７０_ｑ、中間情報消去部１８０_ｑ、記録部１９０_ｑを備える。また、鍵生成装置３００は、マスタ鍵生成部３１０、長期秘密鍵生成部３２０、記録部３９０を備える。以下の説明では、鍵交換装置１００_Ａ（鍵交換装置αに相当）がイニシエータとして機能し、鍵交換装置１００_Ｂ（鍵交換装置βに相当）がレスポンダとして機能してセッション鍵を共有する場合について説明する。

なお、κは整数、ｐはκビットの素数、ＧとＧ_Ｔは位数ｐの群、ｇは群Ｇの生成元、ｇ_Ｔは群Ｇ_Ｔの生成元、ｅはＧ×Ｇ→Ｇ_Ｔのように写像する双線形写像、Ｈ_１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ_２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ_３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐ_ｎは属性を示す属性要素、属性集合Ｓ_Ａは鍵交換装置１００_Ａの属性を示す属性要素Ｐ_ｎの組み合わせの集合、属性集合Ｓ_Ｂは鍵交換装置１００_Ｂの属性を示す属性要素Ｐ_ｎの組み合わせの集合、Ｎ_ＭＡＸはあらかじめ定めた整数、ｊとｎは１以上Ｎ_ＭＡＸ以下の整数、ｋ_Ａは属性集合Ｓ_Ａの要素、ｋ_Ｂは属性集合Ｓ_Ｂの要素、｛Ｔ_Ａ｝はＴ_Ａ［１］，…，Ｔ_Ａ［Ｎ_ＭＡＸ］の集合、｛Ｔ_Ｂ｝はＴ_Ｂ［１］，…，Ｔ_Ｂ［Ｎ_ＭＡＸ］の集合、｛Ｓ_Ａ｝はＳ_Ａ［１］，…，Ｓ_Ａ［Ｎ_ＭＡＸ］の集合、｛Ｓ_Ｂ｝はＳ_Ｂ［１］，…，Ｓ_Ｂ［Ｎ_ＭＡＸ］の集合、｛Ｕ｝はＵ_ｉ，ｊの集合、｛Ｖ｝はＶ_ｉ，ｊの集合である。

［鍵生成、鍵抽出］
図４に、マスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す。なお、長期秘密鍵生成の処理が鍵抽出に相当する。鍵生成装置３００のマスタ鍵生成部３１０は、０以上ｐ−１以下の整数からランダムにｒとｚを選定する。そして、マスタ公開鍵を（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ）、マスタ秘密鍵をｇ＾ｚとして記録部３９０に記録し、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ）を公開する（Ｓ３１０）。鍵交換装置１００_Ａと鍵交換装置１００_Ｂは、それぞれマスタ公開鍵を（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ）を受信し、記録部１９０_Ａと記録部１９０_Ｂに記録する。

長期秘密鍵生成部３２０は、０以上ｐ−１以下の整数からランダムにｔ_Ａ［１］，…，ｔ_Ａ［Ｎ_ＭＡＸ］を選び、Ｓ’_Ａ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ａ［１］）を計算し、１以上Ｎ_ＭＡＸ以下のｊについてＴ_Ａ［ｊ］＝ｇ＾ｔ_Ａ［１］を計算し、属性集合Ｓ_Ａの要素ｋ_Ａについて

を計算し、長期秘密鍵として（Ｓ’_Ａ，｛Ｔ_Ａ｝，｛Ｓ_Ａ｝）を鍵交換装置１００_Ａに送信する（Ｓ３２０_Ａ）。鍵交換装置１００_Ａは、長期秘密鍵（Ｓ’_Ａ，｛Ｔ_Ａ｝，｛Ｓ_Ａ｝）を受信し、記録部１９０_Ａに記録する（Ｓ１９２_Ａ）。

さらに、長期秘密鍵生成部３２０は、０以上ｐ−１以下の整数からランダムにｔ_Ｂ［１］，…，ｔ_Ｂ［Ｎ_ＭＡＸ］を選び、Ｓ’_Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ｂ［１］）を計算し、１以上Ｎ_ＭＡＸ以下のｊについてＴ_Ｂ［ｊ］＝ｇ＾ｔ_Ｂ［１］を計算し、属性集合Ｓ_Ｂの要素ｋ_Ｂについて

を計算し、長期秘密鍵として（Ｓ’_Ｂ，｛Ｔ_Ｂ｝，｛Ｓ_Ｂ｝）を鍵交換装置１００_Ｂに送信する（Ｓ３２０_Ｂ）。鍵交換装置１００_Ｂは、長期秘密鍵（Ｓ’_Ｂ，｛Ｔ_Ｂ｝，｛Ｓ_Ｂ｝）を受信し、記録部１９０_Ｂに記録する（Ｓ１９２_Ｂ）。

なお、あらかじめ鍵交換装置１００_Ａの記録部１９０_Ａにマスタ公開鍵（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ）と長期秘密鍵（Ｓ’_Ａ，｛Ｔ_Ａ｝，｛Ｓ_Ａ｝）とを記録させ、鍵交換装置１００_Ｂの記録部１９０_Ｂにマスタ公開鍵（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ）と長期秘密鍵（Ｓ’_Ｂ，｛Ｔ_Ｂ｝，｛Ｓ_Ｂ｝）とを記録させておけば、ネットワーク１０００を介して接続された鍵交換装置１００_Ａと鍵交換装置１００_Ｂだけで最低限の鍵交換システムが構成できる。

［鍵交換］
図５にセッション鍵を共有する鍵交換の処理のフローの例を示す。この例は、鍵交換装置１００_Ａ（鍵交換装置αに相当）がイニシエータとして機能し、鍵交換装置１００_Ｂ（鍵交換装置βに相当）がレスポンダとして機能する場合を示している。

鍵交換装置１００_Ａは、アクセス構造決定部１１０_Ａ、短期秘密鍵生成部１２０_Ａ、交換情報生成部１３０_Ａ、送信部１４０_Ａ、受信部１４５_Ａ、属性確認部１５０_Ａ、秘密情報取得部１６０_Ａ、セッション鍵計算部１７０_Ａ、中間情報消去部１８０_Ａを備える。鍵交換装置１００_Ｂは、アクセス構造決定部１１０_Ｂ、短期秘密鍵生成部１２０_Ｂ、交換情報生成部１３０_Ｂ、送信部１４０_Ｂ、受信部１４５_Ｂ、属性確認部１５０_Ｂ、秘密情報取得部１６０_Ｂ、セッション鍵計算部１７０_Ｂ、中間情報消去部１８０_Ｂを備える。

アクセス構造決定部１１０_Ａは、アクセス構造Ａ_Ａを決定し、当該アクセス構造Ａ_Ａに対応するシェア情報生成行列Ｍ_Ａと単射ラベリング関数ρ_Ａを生成する（Ｓ１１０_Ａ）。短期秘密鍵生成部１２０_Ａは、１≦ｊ≦Ｎ_Ａについて、ｕ^〜 _ｊを０以上ｐ−１以下の整数からランダムに選定する（Ｓ１２０_Ａ）。交換情報生成部１３０_Ａは、
１≦ｊ≦Ｎ_Ａについて、ｕ_ｊ＝Ｈ_２（Ｓ’_Ａ，｛Ｔ_Ａ｝，｛Ｓ_Ａ｝，ｕ^〜 _ｊ）、
Ｘ＝ｇ＾ｕ_１、
１≦ｉ≦Ｌ_Ａと１≦ｊ≦Ｎ_Ａについて、
Ｕ_ｉ，ｊ＝ｇ＾（ｒ（Ｍ_Ａ）_ｉ，ｊｕ_ｊ）・Ｈ_１（ｊ，ρ_Ａ（ｉ））＾（−ｕ_１）、
１≦ｉ≦Ｌ_ＡとＮ_Ａ＋１≦ｊ≦Ｎ_ＭＡＸについて、
Ｕ_ｉ，ｊ＝Ｈ_１（ｊ，ρ_Ａ（ｉ））＾（−ｕ_１）
を計算する（１３０_Ａ）。送信部１４０_Ａは、Ｘ、｛Ｕ｝、Ｍ_Ａ、ρ_Ａを鍵交換装置１００_Ｂに送信する（Ｓ１４０_Ａ）。中間情報消去部１８０_Ａは、ｕ_ｊ（１≦ｊ≦Ｎ_Ａ）を消去する（Ｓ１８０_Ａ）。

受信部１４５_Ｂは、鍵交換装置１００_Ａから、Ｘ、｛Ｕ｝、Ｍ_Ａ、ρ_Ａを受信する（Ｓ１４５_Ｂ）。属性確認部１５０_Ｂは、属性集合Ｓ_Ｂがシェア情報生成行列Ｍ_Ａと単射ラベリング関数ρ_Ａを満たすか、Ｘと｛Ｕ｝が群Ｇの要素かを確認する（Ｓ１５０_Ｂ）。

アクセス構造決定部１１０_Ｂは、アクセス構造Ａ_Ｂを決定し、当該アクセス構造Ａ_Ｂに対応するシェア情報生成行列Ｍ_Ｂと単射ラベリング関数ρ_Ｂを生成する（Ｓ１１０_Ｂ）。短期秘密鍵生成部１２０_Ｂは、１≦ｊ≦Ｎ_Ｂについて、ｖ^〜 _ｊを０以上ｐ−１以下の整数からランダムに選定する（Ｓ１２０_Ｂ）。交換情報生成部１３０_Ｂは、
１≦ｊ≦Ｎ_Ｂについて、ｖ_ｊ＝Ｈ_２（Ｓ’_Ｂ，｛Ｔ_Ｂ｝，｛Ｓ_Ｂ｝，ｖ^〜 _ｊ）、
Ｙ＝ｇ＾ｖ_１、
１≦ｉ≦Ｌ_Ｂと１≦ｊ≦Ｎ_Ｂについて、
Ｖ_ｉ，ｊ＝ｇ＾（ｒ（Ｍ_Ｂ）_ｉ，ｊｖ_ｊ）・Ｈ_１（ｊ，ρ_Ｂ（ｉ））＾（−ｖ_１）、
１≦ｉ≦Ｌ_ＢとＮ_Ｂ＋１≦ｊ≦Ｎ_ＭＡＸについて、
Ｖ_ｉ，ｊ＝Ｈ_１（ｊ，ρ_Ｂ（ｉ））＾（−ｖ_１）
を計算する（Ｓ１３０_Ｂ）。送信部１４０_Ｂは、Ｙ、｛Ｖ｝、Ｍ_Ｂ、ρ_Ｂを鍵交換装置１００_Ａに送信する（Ｓ１４０_Ｂ）。

秘密情報取得部１６０_Ｂは、Ｉ_Ｂ＝｛ｋ：ρ_Ａ（ｋ）∈Ｓ_Ｂ｝となる集合Ｉ_Ｂを求め、鍵交換装置１００_Ａが生成した秘密情報ｕ_１に対する正当なシェア情報集合｛（Ｍ_Ａ）_ｉ，ｊｕ_ｊ｝について

が成り立つ０以上ｐ−１以下の整数ｗ_Ｂ［ｋ］（ただし、ｋは集合Ｉ_Ｂの要素）を求める（Ｓ１６０_Ｂ）。セッション鍵計算部１７０_Ｂは、

σ_２＝（ｇ_Ｔ＾ｚ）＾ｖ_１
σ_３＝Ｘ＾ｖ_１
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ_３（σ_１，σ_２，σ_３，（Ｘ，｛Ｕ｝，Ｍ_Ａ，ρ_Ａ），（Ｙ，｛Ｖ｝，Ｍ_Ｂ，ρ_Ｂ））
のように求める（Ｓ１７０_Ｂ）。中間情報消去部１８０_Ｂは、ｖ_ｊ（１≦ｊ≦Ｎ_Ｂ）を消去する（Ｓ１８０_Ｂ）。

受信部１４５_Ａは、鍵交換装置１００_Ｂから、Ｙ、｛Ｖ｝、Ｍ_Ｂ、ρ_Ｂを受信する（Ｓ１４５_Ａ）。属性確認部１５０_Ａは、属性集合Ｓ_Ａがシェア情報生成行列Ｍ_Ｂと単射ラベリング関数ρ_Ｂを満たすか、Ｙと｛Ｖ｝が群Ｇの要素かを確認する（Ｓ１５０_Ａ）。秘密情報取得部１６０_Ａは、Ｉ_Ａ＝｛ｋ：ρ_Ｂ（ｋ）∈Ｓ_Ａ｝となる集合Ｉ_Ａを求め、鍵交換装置１００_Ｂが生成した秘密情報ｖ_１に対する正当なシェア情報集合｛（Ｍ_Ｂ）_ｉ，ｊｖ_ｊ｝について

が成り立つ０以上ｐ−１以下の整数ｗ_Ａ［ｋ］（ただし、ｋは集合Ｉ_Ａの要素）を求める（Ｓ１６０_Ａ）。セッション鍵計算部１７０_Ａは、

σ_１＝（ｇ_Ｔ＾ｚ）＾Ｈ_２（Ｓ’_Ａ，｛Ｔ_Ａ｝，｛Ｓ_Ａ｝，ｕ^〜 _１）
σ_３＝Ｙ＾Ｈ_２（Ｓ’_Ａ，｛Ｔ_Ａ｝，｛Ｓ_Ａ｝，ｕ^〜 _１）
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ_３（σ_１，σ_２，σ_３，（Ｘ，｛Ｕ｝，Ｍ_Ａ，ρ_Ａ），（Ｙ，｛Ｖ｝，Ｍ_Ｂ，ρ_Ｂ））
のように求める。

この鍵交換システムは、上述のような処理によって鍵交換時にアクセスポリシーを指定でき、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができる。しかしながら、安全性を保証するためには、ハッシュ関数が理想的に安全（ランダムオラクル）でなければならないという問題がある。ランダムオラクルは現実のハッシュ関数を用いては実現できないことが知られている。よって、ランダムオラクルを仮定せずに安全性証明が付く方式が望ましい。

本発明は、非特許文献１の鍵交換技術と同じように鍵交換時にアクセスポリシーを指定できることと、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができることを確保しながら、ランダムオラクルを仮定しない安全な鍵交換技術を提供することを目的とする。

本発明の鍵交換システムは、少なくとも鍵交換装置αと鍵交換装置βとを備える。ここで、κは整数、ｐはκビットの素数、ＧとＧ_Ｔは位数ｐの群、ｇは群Ｇの生成元、ｇ_Ｔは群Ｇ_Ｔの生成元、ｅはＧ×Ｇ→Ｇ_Ｔのように写像する双線形写像、Ｆ＿σは任意長の整数を指定された鍵空間Ｋｓｐａｃｅの値σにしたがってκビットの整数に変換する擬似ランダム関数、Ｅｘｔは群Ｇの元を鍵空間Ｋｓｐａｃｅの値に変換する強ランダム抽出器、Ｄは整数、ｄは１以上Ｄ以下の整数、ｇｅｎは検証鍵のビット長がＤであるような使い捨て署名の鍵生成のアルゴリズム、ｓｉｇは検証鍵のビット長がＤであるような使い捨て署名の署名生成のアルゴリズム、ｖｅｒは検証鍵のビット長がＤであるような使い捨て署名の検証のアルゴリズム、ａｔｔ’は属性の全要素数を示す整数、Ｗ_ｄ＿Ｒはｄ番目のダミー属性を示す情報が１ビット以上のビット列Ｒであることを示す記号、Ｐ_ｎは属性を示す属性要素、属性集合Ｓ_Ａは鍵交換装置αの属性を示す属性要素Ｐ_ｎの集合、アクセス構造Ａ_Ａは鍵交換装置αが鍵交換装置βに求める属性要素Ｐ_ｎの組み合わせの集合、単射ラベリング関数ρ_Ａは前記アクセス構造Ａ_Ａを示す関数、属性集合ρ_Ａ（ｉ）は前記アクセス構造Ａ_Ａに対応するｉ番目の集合、シェア情報生成行列Ｍ_Ａはｉ行目が属性集合ρ_Ａ（ｉ）に対応するＬ_Ａ行Ｎ_Ａ列の行列、（Ｍ_Ａ）_ｉはシェア情報生成行列Ｍ_Ａのｉ番目の行に対応するベクトル、属性集合Ｓ_Ｂは鍵交換装置βの属性を示す属性要素Ｐ_ｎの集合、アクセス構造Ａ_Ｂは鍵交換装置βが鍵交換装置αに求める属性要素Ｐ_ｎの組み合わせの集合、単射ラベリング関数ρ_Ｂは前記アクセス構造Ａ_Ｂを示す関数、属性集合ρ_Ｂ（ｉ）は前記アクセス構造Ａ_Ｂに対応するｉ番目の集合、シェア情報生成行列Ｍ_Ｂはｉ行目が属性集合ρ_Ｂ（ｉ）に対応するＬ_Ｂ行Ｎ_Ｂ列の行列、（Ｍ_Ｂ）_ｉはシェア情報生成行列Ｍ_Ｂのｉ番目の行に対応するベクトル、Ｌ_Ａ、Ｎ_Ａ、Ｌ_Ｂ、Ｎ_Ｂは整数、ｎ_Ａは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた１以上Ｎ_Ａ以下の整数、ｎ_Ｂは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた１以上Ｎ_Ｂ以下の整数、ｋ_Ａは属性集合Ｓ_Ａの要素、ｋ_Ｂは属性集合Ｓ_Ｂの要素、ｒとｚは０以上ｐ−１以下の整数、ｈ［１］，…，ｈ［ａｔｔ’］は群Ｇの元、（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔ_Ａは０以上ｐ−１以下の整数、ｔ_Ｂは０以上ｐ−１以下の整数、Ｓ’_Ａ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ａ）、Ｓ’_Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ｂ）、Ｔ_Ａ＝ｇ＾ｔ_Ａ、Ｔ_Ｂ＝ｇ＾ｔ_Ｂ、Ｓ_Ａ［ｋ_Ａ］＝ｈ［ｋ_Ａ］＾ｔ_Ａ、Ｓ_Ｂ［ｋ_Ｂ］＝ｈ［ｋ_Ｂ］＾ｔ_Ｂ、｛Ｓ_Ａ｝はＳ_Ａ［ｋ_Ａ］の集合、｛Ｓ_Ｂ｝はＳ_Ｂ［ｋ_Ｂ］の集合、｛Ｕ_ｉ｝はＵ_ｉの集合、｛Ｘ_ｉ｝はＸ_ｉの集合、｛Ｖ_ｉ｝はＶ_ｉの集合、｛Ｙ_ｉ｝はＹ_ｉの集合、＾はべき乗を示す記号、（＋）はビットごとの排他的論理和を示す記号とする。

鍵交換装置αは、第１の記録部、第１のアクセス構造決定部、第１の短期秘密鍵生成部、第１の交換情報生成部、第１の送信部、第１の受信部、第１の秘密情報取得部、第１の属性確認部、第１のセッション鍵計算部、第１の中間情報消去部を備える。鍵交換装置βは、第２の記録部、第２のアクセス構造決定部、第２の短期秘密鍵生成部、第２の交換情報生成部、第２の送信部、第２の受信部、第２の秘密情報取得部、第２の属性確認部、第２のセッション鍵計算部、第２の中間情報消去部を備える。第１の記録部は、長期秘密鍵としてＳ’_Ａ，Ｔ_Ａ，｛Ｓ_Ａ｝を記録する。第２の記録部は、長期秘密鍵としてＳ’_Ｂ，Ｔ_Ｂ，｛Ｓ_Ｂ｝を記録する。

第１のアクセス構造決定部は、アクセス構造Ａ_Ａを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋ_Ａと使い捨て秘密鍵ｓｋ_Ａを生成し、ダミー属性集合Ｗ_Ａ＝｛Ｗ_１＿ｖｋ_Ａ１，…，Ｗ_ｄ＿ｖｋ_Ａｄ，…，Ｗ_Ｄ＿ｖｋ_ＡＤ｝（ただし、ｖｋ_Ａｄは使い捨て公開鍵ｖｋ_Ａのｄ番目のビット）を設定する。そして、当該アクセス構造Ａ_Ａ又はすべてのダミー属性Ｗ_１＿ｖｋ_Ａ１，…，Ｗ_Ｄ＿ｖｋ_ＡＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列Ｍ_Ａと単射ラベリング関数ρ_Ａを生成する。

第１の短期秘密鍵生成部は、１≦ｊ≦Ｎ_Ａについてｕ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｕ＝（ｕ＿１，…，ｕ＿Ｎ_Ａ）とし、ｘを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦Ｌ_Ａについてｘ_ｉを０以上ｐ−１以下の整数からランダムに選定する。

第１の交換情報生成部は、１≦ｉ≦Ｌ_Ａについてベクトルｕとベクトル（Ｍ_Ａ）_ｉとの内積を計算してシェアλ_Ａｉとする。そして、Ｕ＝ｇ＾ｕ＿ｎ_ＡとＸ＝ｇ＾ｘと、１≦ｉ≦Ｌ_ＡについてＵ_ｉ＝ｇ＾（ｒλ_Ａｉ）ｈ［ρ_Ａ（ｉ）］＾（−ｘ_ｉ）とＸ_ｉ＝ｇ＾ｘ_ｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋ_Ａを鍵、（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝）をメッセージとする使い捨て署名ｓ_Ａを生成する。

第１の送信部は、ＥＰＫ_Ａ＝（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，Ｍ_Ａ，ρ_Ａ，ｖｋ_Ａ，ｓ_Ａ）を鍵交換装置βに送信する。第１の受信部は、鍵交換装置βから、ＥＰＫ_Ｂ＝（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，Ｍ_Ｂ，ρ_Ｂ，ｖｋ_Ｂ，ｓ_Ｂ）を受信する。

第１の秘密情報取得部は、Ｉ_Ａ＝｛ｉ：ρ_Ｂ（ｉ）∈Ｓ_Ａ｝となる集合Ｉ_ＡとＩ’_Ａ＝｛ｉ：ρ_Ｂ（ｉ）∈Ｗ_Ｂ｝となる集合Ｉ’_Ａを求め、シェア情報生成行列Ｍ_Ｂに対応する秘密情報ｖ＿ｎ_Ｂの正当なシェア集合｛λ_Ｂｉ｝について、

が成り立つ０以上ｐ−１以下の整数ｗ_Ａｉと整数ｗ’_Ａｉを求める。

第１の属性確認部は、属性集合Ｓ_Ａがシェア情報生成行列Ｍ_Ｂと単射ラベリング関数ρ_Ｂを満たすかを確認することと、Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋ_Ｂを鍵、（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，ｓ_Ｂ）をメッセージとして検証した結果が真であること、

が成り立つことを確認する。
第１のセッション鍵計算部は、

σ_１＝（ｇ_Ｔ＾ｚ）＾ｕ＿ｎ_Ａ
σ_３＝ｅ（ｇ＾ｒ，Ｙ）＾ｘ
を計算し、σ’_１←Ｅｘｔ（σ_１），σ’_２←Ｅｘｔ（σ_２），σ’_３←Ｅｘｔ（σ_３）を計算し、セッション識別子ｓｉｄを（ＥＰＫ_Ａ，ＥＰＫ_Ｂ）に設定し、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’_１（ｓｉｄ）（＋）Ｆ＿σ’_２（ｓｉｄ）（＋）Ｆ＿σ’_３（ｓｉｄ）
のように求める。

第１の中間情報消去部は、少なくともｕ＿ｊ（１≦ｊ≦Ｎ_Ａ）、ｘ、ｘ_ｉ（１≦ｉ≦Ｌ_Ａ）、ＥＰＫ_Ａ、ＥＰＫ_Ｂ、σ_１、σ_２、σ_３、σ’_１、σ’_２、σ’_３、ｓｉｄ、ｓｋ_Ａを消去する。

第２のアクセス構造決定部は、アクセス構造Ａ_Ｂを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋ_Ｂと使い捨て秘密鍵ｓｋ_Ｂを生成し、ダミー属性集合Ｗ_Ｂ＝｛Ｗ_１＿ｖｋ_Ｂ１，…，Ｗ_ｄ＿ｖｋ_Ｂｄ，…，Ｗ_Ｄ＿ｖｋ_ＢＤ｝（ただし、ｖｋ_Ｂｄは使い捨て公開鍵ｖｋ_Ｂのｄ番目のビット）を設定する。そして、当該アクセス構造Ａ_Ｂ又はすべてのダミー属性Ｗ_１＿ｖｋ_Ｂ１，…，Ｗ_Ｄ＿ｖｋ_ＢＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列Ｍ_Ｂと単射ラベリング関数ρ_Ｂを生成する。

第２の短期秘密鍵生成部は、１≦ｊ≦Ｎ_Ｂについてｖ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｖ＝（ｖ＿１，…，ｖ＿Ｎ_Ｂ）とし、ｙを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦Ｌ_Ｂについてｙ_ｉを０以上ｐ−１以下の整数からランダムに選定する。

第２の交換情報生成部は、１≦ｉ≦Ｌ_Ｂについてベクトルｖとベクトル（Ｍ_Ｂ）_ｉとの内積を計算してシェアλ_Ｂｉとする。そして、Ｖ＝ｇ＾ｖ＿ｎ_ＢとＹ＝ｇ＾ｙと、１≦ｉ≦Ｌ_ＢについてＶ_ｉ＝ｇ＾（ｒλ_Ｂｉ）ｈ［ρ_Ｂ（ｉ）］＾（−ｙ_ｉ）とＹ_ｉ＝ｇ＾ｙ_ｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋ_Ｂを鍵、（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝）をメッセージとする使い捨て署名ｓ_Ｂを生成する。

第２の送信部は、ＥＰＫ_Ｂ＝（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，Ｍ_Ｂ，ρ_Ｂ，ｖｋ_Ｂ，ｓ_Ｂ）を鍵交換装置αに送信する。第２の受信部は、鍵交換装置αから、ＥＰＫ_Ａ＝（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，Ｍ_Ａ，ρ_Ａ，ｖｋ_Ａ，ｓ_Ａ）を受信する。

第２の秘密情報取得部は、Ｉ_Ｂ＝｛ｉ：ρ_Ａ（ｉ）∈Ｓ_Ｂ｝となる集合Ｉ_ＢとＩ’_Ｂ＝｛ｉ：ρ_Ａ（ｉ）∈Ｗ_Ａ｝となる集合Ｉ’_Ｂを求め、シェア情報生成行列Ｍ_Ａに対応する秘密情報ｕ＿ｎ_Ａの正当なシェア集合｛λ_Ａｉ｝について、

が成り立つ０以上ｐ−１以下の整数ｗ_Ｂｉと整数ｗ’_Ｂｉを求める。

第２の属性確認部は、属性集合Ｓ_Ｂがシェア情報生成行列Ｍ_Ａと単射ラベリング関数ρ_Ａを満たすかを確認することと、Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋ_Ａを鍵、（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，ｓ_Ａ）をメッセージとして検証した結果が真であること、

が成り立つことを確認する。
第２のセッション鍵計算部は、

σ_２＝（ｇ_Ｔ＾ｚ）＾ｖ＿ｎ_Ｂ
σ_３＝ｅ（ｇ＾ｒ，Ｘ）＾ｙ
を計算し、σ’_１←Ｅｘｔ（σ_１），σ’_２←Ｅｘｔ（σ_２），σ’_３←Ｅｘｔ（σ_３）を計算し、セッション識別子ｓｉｄを（ＥＰＫ_Ａ，ＥＰＫ_Ｂ）に設定し、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’_１（ｓｉｄ）（＋）Ｆ＿σ’_２（ｓｉｄ）（＋）Ｆ＿σ’_３（ｓｉｄ）
のように求める。

第２の中間情報消去部は、少なくともｖ＿ｊ（１≦ｊ≦Ｎ_Ｂ）、ｙ、ｙ_ｉ（１≦ｉ≦Ｌ_Ｂ）、ＥＰＫ_Ａ、ＥＰＫ_Ｂ、σ_１、σ_２、σ_３、σ’_１、σ’_２、σ’_３、ｓｉｄ、ｓｋ_Ｂを消去する。

なお、本発明の鍵交換システムは、さらに、マスタ鍵生成部と長期秘密鍵生成部とを有する鍵生成装置を備えてもよい。この場合は、マスタ鍵生成部が、ｒ，ｚ，ｈ［１］，…，ｈ［ａｔｔ’］をランダムに選定し、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）とマスタ秘密鍵ｇ＾ｚを生成すればよい。また、長期秘密鍵生成部がｔ_Ａとｔ_Ｂをランダムに選定し、Ｓ’_ＡとＳ’_Ｂ、Ｔ_ＡとＴ_Ｂ、Ｓ_Ａ［ｋ_Ａ］とＳ_Ｂ［ｋ_Ｂ］を計算すればよい。

本発明の鍵交換システムによれば、線形秘密分散法を利用することにより、鍵抽出（長期秘密鍵の生成）を行うときには鍵生成装置が、鍵交換装置α、βの属性集合Ｓ_Ａ、Ｓ_Ｂに基づき線形秘密分散法のシェア情報として長期秘密鍵（Ｓ’_Ａ，Ｔ_Ａ，｛Ｓ_Ａ｝）、（Ｓ’_Ｂ，Ｔ_Ｂ，｛Ｓ_Ｂ｝）を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造Ａ_Ａ、Ａ_Ｂを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定することが可能である。また、本発明のマスタ秘密鍵ｇ＾ｚとマスタ公開鍵（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）は、属性集合とは独立なので、属性の全体集合をあらかじめ決めておく必要がない。つまり、鍵抽出時に任意の属性に基づき長期秘密鍵を発行することができる。したがって、非特許文献１と同等の効果が得られる。

さらに、使い捨て署名、強ランダム抽出器、擬似ランダム関数を用いることにより、以下のように、ランダムオラクルを仮定しないで安全性を確保できる。鍵交換を行うユーザは、本来認証に用いる自分の属性集合Ｓ以外に、ダミー属性集合Ｗを用意し、生成した使い捨て署名の検証鍵の値にＷを割り当てる。この時、ユーザは相手が満たすことを希望するアクセス構造Ａに加えて、特定の検証鍵に対応したダミー属性集合Ｗが満たすようなアクセス構造を認証条件として加えて、鍵交換を行う。ダミー属性集合Ｗの方は、実際のユーザ同士が行う鍵交換セッションでは使われることはない。しかし、安全性証明の中で送られてきたメッセージが正しいかどうかを判定する際に、ダミー属性集合Ｗの方の認証条件を用いることにより、アクセス構造Ａを満たす属性集合に対応する秘密鍵の知識なしで判定することができる。また、最後のセッション鍵の導出の時に、ランダムオラクルではなく、強ランダム抽出器と擬似ランダム関数を用いる。具体的には、強ランダム抽出器で共有情報の分布をならし、その値を擬似ランダム関数の鍵とすることで出力をセッション鍵とする。このように、本発明ではランダムオラクルを仮定すること無しに安全性を保つことができる。

特願２０１０−２５９０５３の鍵交換システムの構成例を示す図。 特願２０１０−２５９０５３の鍵交換装置の機能構成例を示す図。 特願２０１０−２５９０５３の鍵生成装置の機能構成例を示す図。 特願２０１０−２５９０５３のマスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す図。 特願２０１０−２５９０５３のセッション鍵を共有する鍵交換の処理のフローの例を示す図。 本発明の鍵交換システムの構成例を示す図。 本発明の鍵交換装置の機能構成例を示す図。 本発明の鍵生成装置の機能構成例を示す図。 本発明のマスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す図。 本発明のセッション鍵を共有する鍵交換の処理のフローの例を示す図。

以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。

［準備］
本発明の鍵交換システムについて説明する前に、本発明を理解する上で必要な理論について説明する。本発明では、アクセスポリシーを次のようなアクセス構造として表すものとする。

まず、｛Ｐ_１，Ｐ_２，…，Ｐ_ｎ，…，Ｐ_Ｎ｝を属性集合とする。ただし、Ｎは整数、ｎは１以上Ｎ以下の整数である。Ｐ_ｎは、例えば、「性別が男性である。」や「○○会社の社員である。」などの鍵生成装置の利用者（ユーザ）の属性を示している。なお、以下の説明では、「鍵生成装置の利用者の属性」を単に「鍵生成装置の属性」と表現する。アクセス構造は｛Ｐ_１，Ｐ_２，…，Ｐ_Ｎ｝の空でない部分集合のべき集合Ａとして表わす。すなわち、
Ａ⊆２＾｛Ｐ_１，Ｐ_２，…，Ｐ_Ｎ｝＼｛φ｝
ただし、“＾”はべき乗を示す記号、“φ”は空集合を示す記号、“＼｛φ｝”は空集合を除くことを示す記号
に属する集合を許可集合、属さない集合を不許可集合とよぶ。本発明では、上記のアクセス構造に基づきアクセスコントロールを行うために次のように線形秘密分散法を用いる。

各属性集合に対応するシェア情報は０以上ｐ−１以下の整数の集合Ｚ_Ｐ上のベクトルとして表される。シェア情報を生成する行列としてＬ行Ｎ列のシェア情報生成行列Ｍを次のように用意する。ｉ＝１，…，Ｌについて、属性ラベリング関数ρを用いてシェア情報生成行列Ｍのｉ行目を属性ρ（ｉ）に対応させる。属性ラベリング関数ρは、ｉを特定すると属性ρ（ｉ）が決まる関数である。また、「属性ρ（ｉ）に対応させる」とは、例えば、属性ρ（１）がＰ_１∧Ｐ_２∧Ｐ_３であれば、１，１，１，０，０，…，０のようにシェア情報生成行列Ｍの１行目を設定し、属性ρ（２）がＰ_１∧Ｐ_Ｎであれば、１，０，０，…，０，１のようにシェア情報生成行列Ｍの２行目を設定するように、属性ρ（ｉ）と対応させてｉ行目を決めることである。なお、上記の例では、アンド条件に含まれる属性Ｐ_ｎに対応する要素を“１”とし、含まれない属性Ｐ_ｎに対応する要素を“０”としたが、これに限る必要はない。異なる条件に対応する行が同じ行にならないように対応付けされていればよいので、属性ラベリング関数ρは単射性を有する範囲で他の対応でもよい。

次に、０以上ｐ−１以下の整数からｒ_１，…，ｒ_Ｎをランダムに選び、ベクトルｖ＝（ｒ_１，…，ｒ_Ｎ）^Ｔを生成する。ただし、Ｔは転置を示す記号である。また、あらかじめ定めておいたｎ番目の要素ｒ_ｎを秘密情報とする。なお、鍵交換したい装置同士の場合、秘密情報として共有する情報が同じであれば任意の情報でかまわないので、ランダムに選んだ整数の何番目を秘密情報にするかをあらかじめ決めておけばよい。この時、Ｍは秘密情報ｒ_ｎのＬ個のシェア情報のベクトルとなる。属性集合ρ（ｉ）にシェア情報（Ｍｖ）_ｉを割り当てる。ただし、（Ｍｖ）_ｉはベクトルＭｖのｉ番目の成分を示している。

このようにシェア情報生成行列Ｍと秘密情報を含む列ベクトルｖを用いると、線形秘密分散法の線形復元性を利用できる。ここで、線形復元性について説明する。あるアクセス構造Ａを考え、属性集合ＳをＳ∈Ａの任意の許可集合とし、Ｉ⊂｛１，２，…，Ｌ｝をＩ＝｛ｉ：ρ（ｉ）∈Ｓ｝と定義する。このとき、｛λ_ｉ｝がｒ_ｎの正しいシェア情報の集合の場合、

となるような０以上ｐ−１以下の整数の集合｛ｗ_ｉ｝が存在する。このような集合｛ｗ_ｉ｝はＭのサイズの多項式時間で見つけられることが知られている。一方、｛λ_ｉ｝がｒ_ｎの正しいシェア情報の集合でない場合、集合｛ｗ_ｉ｝のすべての要素を求めることができない。本発明では、上述のようにシェア情報生成行列Ｍと秘密情報を含む列ベクトルｖを用いることで、線形秘密分散法の線形復元性を利用してセッション鍵を交換する。

［構成］
図６に本発明の鍵交換システムの構成例を示す。本発明の鍵交換システムは、ネットワーク１０００を介して接続された鍵交換装置５００_１，…，５００_Ｑ（ただし、Ｑは２以上の整数、ｑは１以上Ｑ以下の整数、ＡとＢは１以上Ｑ以下の異なる整数）、鍵生成装置６００で構成される。図７に本発明の鍵交換装置の機能構成例、図８に本発明の鍵生成装置の機能構成例を示す。鍵交換装置５００_ｑは、アクセス構造決定部５１０_ｑ、短期秘密鍵生成部５２０_ｑ、交換情報生成部５３０_ｑ、送信部５４０_ｑ、受信部５４５_ｑ、属性確認部５５０_ｑ、秘密情報取得部５６０_ｑ、セッション鍵計算部５７０_ｑ、中間情報消去部５８０_ｑ、記録部５９０_ｑを備える。また、鍵生成装置６００は、マスタ鍵生成部６１０、長期秘密鍵生成部６２０、記録部６９０を備える。以下の説明では、鍵交換装置５００_Ａ（鍵交換装置αに相当）がイニシエータとして機能し、鍵交換装置５００_Ｂ（鍵交換装置βに相当）がレスポンダとして機能してセッション鍵を共有する場合について説明する。

なお、以下の説明では、κは整数、ｐはκビットの素数、ＧとＧ_Ｔは位数ｐの群、ｇは群Ｇの生成元、ｇ_Ｔは群Ｇ_Ｔの生成元、ｅはＧ×Ｇ→Ｇ_Ｔのように写像する双線形写像、Ｆ＿σは任意長の整数を指定された鍵空間Ｋｓｐａｃｅの値σにしたがってκビットの整数に変換する擬似ランダム関数、Ｅｘｔは群Ｇの元を鍵空間Ｋｓｐａｃｅの値に変換する強ランダム抽出器、Ｄは整数（ダミー属性の要素数）、ｄは１以上Ｄ以下の整数、ｇｅｎは検証鍵のビット長がＤであるような使い捨て署名の鍵生成のアルゴリズム、ｓｉｇは検証鍵のビット長がＤであるような使い捨て署名の署名生成のアルゴリズム、ｖｅｒは検証鍵のビット長がＤであるような使い捨て署名の検証のアルゴリズム、ａｔｔ’は属性の全要素数を示す整数（実際の属性とダミー属性の両方を合わせた全要素数）、Ｗ_ｄ＿Ｒはｄ番目のダミー属性を示す情報が１ビット以上のビット列Ｒであることを示す記号（本明細書では、１ビットの場合もビット列と呼ぶことにする）、Ｐ_ｎは属性を示す属性要素、属性集合Ｓ_Ａは鍵交換装置５００_Ａの属性を示す属性要素Ｐ_ｎの集合、アクセス構造Ａ_Ａは鍵交換装置５００_Ａが鍵交換装置５００_Ｂに求める属性要素Ｐ_ｎの組み合わせの集合、単射ラベリング関数ρ_Ａはアクセス構造Ａ_Ａを示す関数、属性集合ρ_Ａ（ｉ）はアクセス構造Ａ_Ａに対応するｉ番目の集合、シェア情報生成行列Ｍ_Ａはｉ行目が属性集合ρ_Ａ（ｉ）に対応するＬ_Ａ行Ｎ_Ａ列の行列、（Ｍ_Ａ）_ｉはシェア情報生成行列Ｍ_Ａのｉ番目の行に対応するベクトル、属性集合Ｓ_Ｂは鍵交換装置５００_Ｂの属性を示す属性要素Ｐ_ｎの集合、アクセス構造Ａ_Ｂは鍵交換装置５００_Ｂが鍵交換装置５００_Ａに求める属性要素Ｐ_ｎの組み合わせの集合、単射ラベリング関数ρ_Ｂはアクセス構造Ａ_Ｂを示す関数、属性集合ρ_Ｂ（ｉ）はアクセス構造Ａ_Ｂに対応するｉ番目の集合、シェア情報生成行列Ｍ_Ｂはｉ行目が属性集合ρ_Ｂ（ｉ）に対応するＬ_Ｂ行Ｎ_Ｂ列の行列、（Ｍ_Ｂ）_ｉはシェア情報生成行列Ｍ_Ｂのｉ番目の行に対応するベクトル、Ｌ_Ａ、Ｎ_Ａ、Ｌ_Ｂ、Ｎ_Ｂは整数、ｎ_Ａは鍵交換装置５００_Ａと鍵交換装置５００_Ｂとで共有するあらかじめ定めた１以上Ｎ_Ａ以下の整数、ｎ_Ｂは鍵交換装置５００_Ａと鍵交換装置５００_Ｂとで共有するあらかじめ定めた１以上Ｎ_Ｂ以下の整数、ｋ_Ａは属性集合Ｓ_Ａの要素、ｋ_Ｂは属性集合Ｓ_Ｂの要素、ｒとｚは０以上ｐ−１以下の整数、ｔ_Ｂは０以上ｐ−１以下の整数、ｈ［１］，…，ｈ［ａｔｔ’］は群Ｇの元、｛Ｓ_Ａ｝はＳ_Ａ［ｋ_Ａ］の集合、｛Ｓ_Ｂ｝はＳ_Ｂ［ｋ_Ｂ］の集合、｛Ｕ_ｉ｝はＵ_ｉの集合、｛Ｘ_ｉ｝はＸ_ｉの集合、｛Ｖ_ｉ｝はＶ_ｉの集合、｛Ｙ_ｉ｝はＹ_ｉの集合、＾はべき乗を示す記号、（＋）はビットごとの排他的論理和を示す記号とする。

［鍵生成、鍵抽出］
図９に、マスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す。なお、長期秘密鍵生成の処理が鍵抽出に相当する。鍵生成装置６００のマスタ鍵生成部６１０は、０以上ｐ−１以下の整数からランダムにｒ、ｚを選定し、群Ｇの元からランダムにｈ［１］，…，ｈ［ａｔｔ’］を選定する。そして、マスタ公開鍵を（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）、マスタ秘密鍵をｇ＾ｚとして記録部３９０に記録し、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）を公開する（Ｓ６１０）。鍵交換装置５００_Ａと鍵交換装置５００_Ｂは、それぞれマスタ公開鍵（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）を受信し、記録部５９０_Ａと記録部５９０_Ｂに記録する（Ｓ５９１，Ｓ５９２）。

長期秘密鍵生成部６２０は、０以上ｐ−１以下の整数からランダムにｔ_Ａを選定し、Ｓ’_Ａ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ａ）、Ｔ_Ａ＝ｇ＾ｔ_Ａ、属性集合Ｓ_Ａの要素ｋ_ＡについてＳ_Ａ［ｋ_Ａ］＝ｈ［ｋ_Ａ］＾ｔ_Ａを計算し、長期秘密鍵として（Ｓ’_Ａ，Ｔ_Ａ，｛Ｓ_Ａ｝）を鍵交換装置５００_Ａに送信する（Ｓ６２０_Ａ）。鍵交換装置５００_Ａは、長期秘密鍵（Ｓ’_Ａ，Ｔ_Ａ，｛Ｓ_Ａ｝）を受信し、記録部５９０_Ａに記録する（Ｓ５９２_Ａ）。

さらに、長期秘密鍵生成部６２０は、０以上ｐ−１以下の整数からランダムにｔ_Ｂを選定し、Ｓ’_Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ｂ）、Ｔ_Ｂ＝ｇ＾ｔ_Ｂ、属性集合Ｓ_Ｂの要素ｋ_ＢについてＳ_Ｂ［ｋ_Ｂ］＝ｈ［ｋ_Ｂ］＾ｔ_Ｂを計算し、長期秘密鍵として（Ｓ’_Ｂ，Ｔ_Ｂ，｛Ｓ_Ｂ｝）を鍵交換装置５００_Ｂに送信する（Ｓ６２０_Ｂ）。鍵交換装置５００_Ｂは、長期秘密鍵（Ｓ’_Ｂ，Ｔ_Ｂ，｛Ｓ_Ｂ｝）を受信し、記録部５９０_Ｂに記録する（Ｓ５９２_Ｂ）。

なお、あらかじめ鍵交換装置５００_Ａの記録部５９０_Ａにマスタ公開鍵（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）と長期秘密鍵（Ｓ’_Ａ，Ｔ_Ａ，｛Ｓ_Ａ｝）とを記録させ、鍵交換装置５００_Ｂの記録部５９０_Ｂにマスタ公開鍵（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）と長期秘密鍵（Ｓ’_Ｂ，Ｔ_Ｂ，｛Ｓ_Ｂ｝）とを記録させておけば、ネットワーク１０００を介して接続された鍵交換装置５００_Ａと鍵交換装置５００_Ｂだけで最低限の鍵交換システムが構成できる。

［鍵交換］
図１０にセッション鍵を共有する鍵交換の処理のフローの例を示す。この例は、鍵交換装置５００_Ａ（鍵交換装置αに相当）がイニシエータとして機能し、鍵交換装置５００_Ｂ（鍵交換装置βに相当）がレスポンダとして機能する場合を示している。

鍵交換装置５００_Ａは、アクセス構造決定部５１０_Ａ（第１のアクセス構造決定部）、短期秘密鍵生成部５２０_Ａ（第１の短期秘密鍵生成部）、交換情報生成部５３０_Ａ（第１の交換情報生成部）、送信部５４０_Ａ（第１の送信部）、受信部５４５_Ａ（第１の受信部）、属性確認部５５０_Ａ（第１の属性確認部）、秘密情報取得部５６０_Ａ（第１の秘密情報取得部）、セッション鍵計算部５７０_Ａ（第１のセッション鍵計算部）、中間情報消去部５８０_Ａ（第１の中間情報消去部）、記録部５９０_Ａ（第１の記録部）を備える。鍵交換装置５００_Ｂは、アクセス構造決定部５１０_Ｂ（第２のアクセス構造決定部）、短期秘密鍵生成部５２０_Ｂ（第２の短期秘密鍵生成部）、交換情報生成部５３０_Ｂ（第２の交換情報生成部）、送信部５４０_Ｂ（第２の送信部）、受信部５４５_Ｂ（第２の受信部）、属性確認部５５０_Ｂ（第２の属性確認部）、秘密情報取得部５６０_Ｂ（第２の秘密情報取得部）、セッション鍵計算部５７０_Ｂ（第２のセッション鍵計算部）、中間情報消去部５８０_Ｂ（第２の中間情報消去部）、記録部５９０_Ｂ（第２の記録部）を備える。

鍵交換装置５００_Ａでは、記録部５９０_Ａが長期秘密鍵としてＳ’_Ａ，Ｔ_Ａ，｛Ｓ_Ａ｝を記録している。アクセス構造決定部５１０_Ａは、アクセス構造Ａ_Ａを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋ_Ａと使い捨て秘密鍵ｓｋ_Ａを生成し、ダミー属性集合Ｗ_Ａ＝｛Ｗ_１＿ｖｋ_Ａ１，…，Ｗ_ｄ＿ｖｋ_Ａｄ，…，Ｗ_Ｄ＿ｖｋ_ＡＤ｝（ただし、ｖｋ_Ａｄは使い捨て公開鍵ｖｋ_Ａのｄ番目のビット）を設定する。そして、アクセス構造Ａ_Ａ又はすべてのダミー属性Ｗ_１＿ｖｋ_Ａ１，…，Ｗ_Ｄ＿ｖｋ_ＡＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列Ｍ_Ａと単射ラベリング関数ρ_Ａを生成する（Ｓ５１０_Ａ）。

短期秘密鍵生成部５２０_Ａは、１≦ｊ≦Ｎ_Ａについてｕ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｕ＝（ｕ＿１，…，ｕ＿Ｎ_Ａ）とし、ｘを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦Ｌ_Ａについてｘ_ｉを０以上ｐ−１以下の整数からランダムに選定する（Ｓ５２０_Ａ）。

交換情報生成部５３０_Ａは、１≦ｉ≦Ｌ_Ａについてベクトルｕとベクトル（Ｍ_Ａ）_ｉとの内積を計算してシェアλ_Ａｉとする。そして、
Ｕ＝ｇ＾ｕ＿ｎ_Ａ
Ｘ＝ｇ＾ｘ
Ｕ_ｉ＝ｇ＾（ｒλ_Ａｉ）ｈ［ρ_Ａ（ｉ）］＾（−ｘ_ｉ） ただし、１≦ｉ≦Ｌ_Ａ
Ｘ_ｉ＝ｇ＾ｘ_ｉ ただし、１≦ｉ≦Ｌ_Ａ
を計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋ_Ａを鍵、（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝）をメッセージとする使い捨て署名ｓ_Ａを生成する（Ｓ５３０_Ａ）。

第１の送信部５４０_Ａは、ＥＰＫ_Ａ＝（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，Ｍ_Ａ，ρ_Ａ，ｖｋ_Ａ，ｓ_Ａ）を鍵交換装置５００_Ｂに送信する（Ｓ５４０_Ａ）。

一方、鍵交換装置５００_Ｂでは、記録部５９０_Ｂが長期秘密鍵としてＳ’_Ｂ，Ｔ_Ｂ，｛Ｓ_Ｂ｝を記録している。そして、アクセス構造決定部５１０_Ｂは、アクセス構造Ａ_Ｂを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋ_Ｂと使い捨て秘密鍵ｓｋ_Ｂを生成し、ダミー属性集合Ｗ_Ｂ＝｛Ｗ_１＿ｖｋ_Ｂ１，…，Ｗ_ｄ＿ｖｋ_Ｂｄ，…，Ｗ_Ｄ＿ｖｋ_ＢＤ｝（ただし、ｖｋ_Ｂｄは使い捨て公開鍵ｖｋ_Ｂのｄ番目のビット）を設定する。そして、アクセス構造Ａ_Ｂ又はすべてのダミー属性Ｗ_１＿ｖｋ_Ｂ１，…，Ｗ_Ｄ＿ｖｋ_ＢＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列Ｍ_Ｂと単射ラベリング関数ρ_Ｂを生成する（Ｓ５１０_Ｂ）。

短期秘密鍵生成部５２０_Ｂは、１≦ｊ≦Ｎ_Ｂについてｖ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｖ＝（ｖ＿１，…，ｖ＿Ｎ_Ｂ）とし、ｙを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦Ｌ_Ｂについてｙ_ｉを０以上ｐ−１以下の整数からランダムに選定する（Ｓ５２０_Ｂ）。

交換情報生成部５３０_Ｂは、１≦ｉ≦Ｌ_Ｂについてベクトルｖとベクトル（Ｍ_Ｂ）_ｉとの内積を計算してシェアλ_Ｂｉとする。そして、
Ｖ＝ｇ＾ｖ＿ｎ_Ｂ
Ｙ＝ｇ＾ｙ
Ｖ_ｉ＝ｇ＾（ｒλ_Ｂｉ）ｈ［ρ_Ｂ（ｉ）］＾（−ｙ_ｉ） ただし、１≦ｉ≦Ｌ_Ｂ
Ｙ_ｉ＝ｇ＾ｙ_ｉ ただし、１≦ｉ≦Ｌ_Ｂ
を計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋ_Ｂを鍵、（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝）をメッセージとする使い捨て署名ｓ_Ｂを生成する（Ｓ５３０_Ｂ）。

送信部５４０_Ｂは、ＥＰＫ_Ｂ＝（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，Ｍ_Ｂ，ρ_Ｂ，ｖｋ_Ｂ，ｓ_Ｂ）を鍵交換装置５００_Ａに送信する（Ｓ５４０_Ｂ）。

受信部５４５_Ｂは、鍵交換装置５００_Ａから、ＥＰＫ_Ａ＝（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，Ｍ_Ａ，ρ_Ａ，ｖｋ_Ａ，ｓ_Ａ）を受信する（Ｓ５４５_Ｂ）。

属性確認部５５０_Ｂは、属性集合Ｓ_Ｂがシェア情報生成行列Ｍ_Ａと単射ラベリング関数ρ_Ａを満たすかを確認する。そして、満たさないと判断した場合は処理を中止する。満たすと判断した場合は、ステップＳ５６０_Ｂに進む（Ｓ５５１_Ｂ）。

秘密情報取得部５６０_Ｂは、Ｉ_Ｂ＝｛ｉ：ρ_Ａ（ｉ）∈Ｓ_Ｂ｝となる集合Ｉ_ＢとＩ’_Ｂ＝｛ｉ：ρ_Ａ（ｉ）∈Ｗ_Ａ｝となる集合Ｉ’_Ｂを求める。そして、シェア情報生成行列Ｍ_Ａに対応する秘密情報ｕ＿ｎ_Ａの正当なシェア集合｛λ_Ａｉ｝について、

が成り立つ０以上ｐ−１以下の整数ｗ_Ｂｉと整数ｗ’_Ｂｉを求める（Ｓ５６０_Ｂ）。上述のように、ｎ_Ａは鍵交換装置５００_Ａと鍵交換装置５００_Ｂとで共有するあらかじめ定めた１以上Ｎ_Ａ以下の整数であればよい。例えば、ｎ_Ａ＝１とすればよい。

属性確認部５５０_Ｂは、Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋ_Ａを鍵、（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，ｓ_Ａ）をメッセージとして検証した結果が真であること、

が成り立つことを確認する。そして、いずれかの条件を満足しない場合には処理を中止する。すべての条件を満足する場合はステップＳ３７０_Ｂに進む（Ｓ３５２_Ｂ）。
セッション鍵計算部５７０_Ｂは、

σ_２＝（ｇ_Ｔ＾ｚ）＾ｖ＿ｎ_Ｂ
σ_３＝ｅ（ｇ＾ｒ，Ｘ）＾ｙ
を計算する。そして、σ’_１←Ｅｘｔ（σ_１），σ’_２←Ｅｘｔ（σ_２），σ’_３←Ｅｘｔ（σ_３）を計算し、セッション識別子ｓｉｄを（ＥＰＫ_Ａ，ＥＰＫ_Ｂ）に設定する。さらに、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’_１（ｓｉｄ）（＋）Ｆ＿σ’_２（ｓｉｄ）（＋）Ｆ＿σ’_３（ｓｉｄ）
のように求める（Ｓ５７０_Ｂ）。

中間情報消去部５８０_Ｂは、少なくともｖ＿ｊ（１≦ｊ≦Ｎ_Ｂ）、ｙ、ｙ_ｉ（１≦ｉ≦Ｌ_Ｂ）、ＥＰＫ_Ａ、ＥＰＫ_Ｂ、σ_１、σ_２、σ_３、σ’_１、σ’_２、σ’_３、ｓｉｄ、ｓｋ_Ｂを消去する（Ｓ５８０_Ｂ）。一般的には、セッション鍵Ｋ以外の計算の途中で使用した値をすべて消去すればよい。

鍵交換装置５００_Ａの処理に戻る。受信部５４５_Ａは、鍵交換装置５００_Ｂから、ＥＰＫ_Ｂ＝（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，Ｍ_Ｂ，ρ_Ｂ，ｖｋ_Ｂ，ｓ_Ｂ）を受信する（Ｓ５４５_Ａ）。

属性確認部５５０_Ａは、属性集合Ｓ_Ａがシェア情報生成行列Ｍ_Ｂと単射ラベリング関数ρ_Ｂを満たすかを確認する。そして、満たさないと判断した場合は処理を中止する。満たすと判断した場合は、ステップＳ５６０_Ａに進む（Ｓ５５１_Ａ）。

秘密情報取得部５６０_Ａは、Ｉ_Ａ＝｛ｉ：ρ_Ｂ（ｉ）∈Ｓ_Ａ｝となる集合Ｉ_ＡとＩ’_Ａ＝｛ｉ：ρ_Ｂ（ｉ）∈Ｗ_Ｂ｝となる集合Ｉ’_Ａを求める。そして、シェア情報生成行列Ｍ_Ｂに対応する秘密情報ｖ＿ｎ_Ｂの正当なシェア集合｛λ_Ｂｉ｝について、

が成り立つ０以上ｐ−１以下の整数ｗ_Ａｉと整数ｗ’_Ａｉを求める（Ｓ５６０_Ａ）。上述のように、ｎ_Ｂは鍵交換装置５００_Ａと鍵交換装置５００_Ｂとで共有するあらかじめ定めた１以上Ｎ_Ｂ以下の整数であればよい。例えば、ｎ_Ｂ＝１とすればよい。

属性確認部５５０_Ａは、Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋ_Ｂを鍵、（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，ｓ_Ｂ）をメッセージとして検証した結果が真であること、

が成り立つことを確認する。そして、いずれかの条件を満足しない場合には処理を中止する。すべての条件を満足する場合はステップＳ５７０_Ａに進む（Ｓ５５２_Ａ）。
セッション鍵計算部５７０_Ａは、

σ_１＝（ｇ_Ｔ＾ｚ）＾ｕ＿ｎ_Ａ
σ_３＝ｅ（ｇ＾ｒ，Ｙ）＾ｘ
を計算する。そして、σ’_１←Ｅｘｔ（σ_１），σ’_２←Ｅｘｔ（σ_２），σ’_３←Ｅｘｔ（σ_３）を計算し、セッション識別子ｓｉｄを（ＥＰＫ_Ａ，ＥＰＫ_Ｂ）に設定する。さらに、セッション鍵Ｋを、
Ｋ＝Ｆ＿σ’_１（ｓｉｄ）（＋）Ｆ＿σ’_２（ｓｉｄ）（＋）Ｆ＿σ’_３（ｓｉｄ）
のように求める（Ｓ５７０_Ａ）。

中間情報消去部５８０_Ａは、少なくともｕ＿ｊ（１≦ｊ≦Ｎ_Ａ）、ｘ、ｘ_ｉ（１≦ｉ≦Ｌ_Ａ）、ＥＰＫ_Ａ、ＥＰＫ_Ｂ、σ_１、σ_２、σ_３、σ’_１、σ’_２、σ’_３、ｓｉｄ、ｓｋ_Ａを消去する（Ｓ５８０_Ａ）。一般的には、セッション鍵Ｋ以外の計算の途中で使用した値をすべて消去すればよい。

［確認］
最後に鍵交換装置１００_Ａと鍵交換装置１００_Ｂが取得したセッション鍵Ｋが等しいことを説明する。

σ_３＝ｅ（ｇ＾ｒ，Ｘ）＾ｙ
＝ｇ_Ｔ＾（ｒｘｙ）＝ｅ（ｇ＾ｒ，Ｙ）＾ｘ
よって、正しくセッション鍵を共有できる。

本発明の鍵交換システムによれば、線形秘密分散法を利用することにより、鍵抽出（長期秘密鍵の生成）を行うときには鍵生成装置が、鍵交換装置５００_Ａ、５００_Ｂの属性集合Ｓ_Ａ、Ｓ_Ｂに基づき線形秘密分散法のシェア情報として長期秘密鍵（Ｓ’_Ａ，Ｔ_Ａ，｛Ｓ_Ａ｝）、（Ｓ’_Ｂ，Ｔ_Ｂ，｛Ｓ_Ｂ｝）を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造Ａ_Ａ、Ａ_Ｂを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定することが可能である。また、本発明のマスタ秘密鍵ｇ＾ｚとマスタ公開鍵（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）は、属性集合とは独立なので、属性の全体集合をあらかじめ決めておく必要がない。つまり、鍵抽出時に任意の属性に基づき長期秘密鍵を発行することができる。したがって、非特許文献１と同等の効果が得られる。

さらに、使い捨て署名、強ランダム抽出器、擬似ランダム関数を用いることにより、以下のように、ランダムオラクルを仮定しないで安全性を確保できる。鍵交換を行うユーザは、本来認証に用いる自分の属性集合Ｓ以外に、ダミー属性集合Ｗを用意し、生成した使い捨て署名の検証鍵の値にＷを割り当てる。この時、ユーザは相手が満たすことを希望するアクセス構造Ａに加えて、特定の検証鍵に対応したダミー属性集合Ｗが満たすようなアクセス構造を認証条件として加えて、鍵交換を行う。ダミー属性集合Ｗの方は、実際のユーザ同士が行う鍵交換セッションでは使われることはない。しかし、安全性証明の中で送られてきたメッセージが正しいかどうかを判定する際に、ダミー属性集合Ｗの方の認証条件を用いることにより、アクセス構造Ａを満たす属性集合に対応する秘密鍵の知識なしで判定することができる。また、最後のセッション鍵の導出の時に、ランダムオラクルではなく、強ランダム抽出器と擬似ランダム関数を用いる。具体的には、強ランダム抽出器で共有情報の分布をならし、その値を擬似ランダム関数の鍵とすることで出力をセッション鍵とする。このように、本発明ではランダムオラクルを仮定すること無しに安全性を保つことができる。

［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。

また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。

また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。

また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

本発明は、二者間でセッション鍵を共有した暗号通信に利用することができる。

１００_ｑ、５００_ｑ 鍵交換装置 １１０_ｑ、５１０_ｑ アクセス構造決定部
１２０_ｑ、５２０_ｑ 短期秘密鍵生成部 １３０_ｑ、５３０_ｑ 交換情報生成部
１４０_ｑ、５４０_ｑ 送信部 １４５_ｑ、５４５_ｑ 受信部
１５０_ｑ、５５０_ｑ 属性確認部 １６０_ｑ、５６０_ｑ 秘密情報取得部
１７０_ｑ、５７０_ｑ セッション鍵計算部 １８０_ｑ、５８０_ｑ 中間情報消去部
１９０_ｑ、３９０、５９０_ｑ、６９０ 記録部
３００、６００ 鍵生成装置 ３１０、６１０ マスタ鍵生成部
３２０、６２０ 長期秘密鍵生成部 １０００ ネットワーク

Claims (7)

1. 少なくとも鍵交換装置αと鍵交換装置βとを備え、セッション鍵を交換する鍵交換システムであって、
   κは整数、ｐはκビットの素数、ＧとＧ_Ｔは位数ｐの群、ｇは群Ｇの生成元、ｇ_Ｔは群Ｇ_Ｔの生成元、ｅはＧ×Ｇ→Ｇ_Ｔのように写像する双線形写像、Ｆ＿σは任意長の整数を指定された鍵空間Ｋｓｐａｃｅの値σにしたがってκビットの整数に変換する擬似ランダム関数、Ｅｘｔは群Ｇの元を鍵空間Ｋｓｐａｃｅの値に変換する強ランダム抽出器、Ｄは整数、ｄは１以上Ｄ以下の整数、ｇｅｎは検証鍵のビット長がＤであるような使い捨て署名の鍵生成のアルゴリズム、ｓｉｇは検証鍵のビット長がＤであるような使い捨て署名の署名生成のアルゴリズム、ｖｅｒは検証鍵のビット長がＤであるような使い捨て署名の検証のアルゴリズム、ａｔｔ’は属性の全要素数を示す整数、Ｗ_ｄ＿Ｒはｄ番目のダミー属性を示す情報が１ビット以上のビット列Ｒであることを示す記号、Ｐ_ｎは属性を示す属性要素、属性集合Ｓ_Ａは鍵交換装置αの属性を示す属性要素Ｐ_ｎの集合、アクセス構造Ａ_Ａは鍵交換装置αが鍵交換装置βに求める属性要素Ｐ_ｎの組み合わせの集合、単射ラベリング関数ρ_Ａは前記アクセス構造Ａ_Ａを示す関数、属性集合ρ_Ａ（ｉ）は前記アクセス構造Ａ_Ａに対応するｉ番目の集合、シェア情報生成行列Ｍ_Ａはｉ行目が属性集合ρ_Ａ（ｉ）に対応するＬ_Ａ行Ｎ_Ａ列の行列、（Ｍ_Ａ）_ｉはシェア情報生成行列Ｍ_Ａのｉ番目の行に対応するベクトル、属性集合Ｓ_Ｂは鍵交換装置βの属性を示す属性要素Ｐ_ｎの集合、アクセス構造Ａ_Ｂは鍵交換装置βが鍵交換装置αに求める属性要素Ｐ_ｎの組み合わせの集合、単射ラベリング関数ρ_Ｂは前記アクセス構造Ａ_Ｂを示す関数、属性集合ρ_Ｂ（ｉ）は前記アクセス構造Ａ_Ｂに対応するｉ番目の集合、シェア情報生成行列Ｍ_Ｂはｉ行目が属性集合ρ_Ｂ（ｉ）に対応するＬ_Ｂ行Ｎ_Ｂ列の行列、（Ｍ_Ｂ）_ｉはシェア情報生成行列Ｍ_Ｂのｉ番目の行に対応するベクトル、Ｌ_Ａ、Ｎ_Ａ、Ｌ_Ｂ、Ｎ_Ｂは整数、ｎ_Ａは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた１以上Ｎ_Ａ以下の整数、ｎ_Ｂは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた１以上Ｎ_Ｂ以下の整数、ｋ_Ａは属性集合Ｓ_Ａの要素、ｋ_Ｂは属性集合Ｓ_Ｂの要素、ｒとｚは０以上ｐ−１以下の整数、ｈ［１］，…，ｈ［ａｔｔ’］は群Ｇの元、（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔ_Ａは０以上ｐ−１以下の整数、ｔ_Ｂは０以上ｐ−１以下の整数、Ｓ’_Ａ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ａ）、Ｓ’_Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ｂ）、Ｔ_Ａ＝ｇ＾ｔ_Ａ、Ｔ_Ｂ＝ｇ＾ｔ_Ｂ、Ｓ_Ａ［ｋ_Ａ］＝ｈ［ｋ_Ａ］＾ｔ_Ａ、Ｓ_Ｂ［ｋ_Ｂ］＝ｈ［ｋ_Ｂ］＾ｔ_Ｂ、｛Ｓ_Ａ｝はＳ_Ａ［ｋ_Ａ］の集合、｛Ｓ_Ｂ｝はＳ_Ｂ［ｋ_Ｂ］の集合、｛Ｕ_ｉ｝はＵ_ｉの集合、｛Ｘ_ｉ｝はＸ_ｉの集合、｛Ｖ_ｉ｝はＶ_ｉの集合、｛Ｙ_ｉ｝はＹ_ｉの集合、＾はべき乗を示す記号、（＋）はビットごとの排他的論理和を示す記号であり、
   前記鍵交換装置αは、
   長期秘密鍵としてＳ’_Ａ，Ｔ_Ａ，｛Ｓ_Ａ｝を記録する第１の記録部と、
   アクセス構造Ａ_Ａを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋ_Ａと使い捨て秘密鍵ｓｋ_Ａを生成し、ダミー属性集合Ｗ_Ａ＝｛Ｗ_１＿ｖｋ_Ａ１，…，Ｗ_ｄ＿ｖｋ_Ａｄ，…，Ｗ_Ｄ＿ｖｋ_ＡＤ｝（ただし、ｖｋ_Ａｄは使い捨て公開鍵ｖｋ_Ａのｄ番目のビット）を設定し、当該アクセス構造Ａ_Ａ又はすべてのダミー属性Ｗ_１＿ｖｋ_Ａ１，…，Ｗ_Ｄ＿ｖｋ_ＡＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列Ｍ_Ａと単射ラベリング関数ρ_Ａを生成する第１のアクセス構造決定部と、
   １≦ｊ≦Ｎ_Ａについてｕ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｕ＝（ｕ＿１，…，ｕ＿Ｎ_Ａ）とし、ｘを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦Ｌ_Ａについてｘ_ｉを０以上ｐ−１以下の整数からランダムに選定する第１の短期秘密鍵生成部と、
   １≦ｉ≦Ｌ_Ａについてベクトルｕとベクトル（Ｍ_Ａ）_ｉとの内積を計算してシェアλ_Ａｉとし、Ｕ＝ｇ＾ｕ＿ｎ_ＡとＸ＝ｇ＾ｘと、１≦ｉ≦Ｌ_ＡについてＵ_ｉ＝ｇ＾（ｒλ_Ａｉ）ｈ［ρ_Ａ（ｉ）］＾（−ｘ_ｉ）とＸ_ｉ＝ｇ＾ｘ_ｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋ_Ａを鍵、（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝）をメッセージとする使い捨て署名ｓ_Ａを生成する第１の交換情報生成部と、
   ＥＰＫ_Ａ＝（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，Ｍ_Ａ，ρ_Ａ，ｖｋ_Ａ，ｓ_Ａ）を鍵交換装置βに送信する第１の送信部と、
   鍵交換装置βから、ＥＰＫ_Ｂ＝（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，Ｍ_Ｂ，ρ_Ｂ，ｖｋ_Ｂ，ｓ_Ｂ）を受信する第１の受信部と、
   Ｉ_Ａ＝｛ｉ：ρ_Ｂ（ｉ）∈Ｓ_Ａ｝となる集合Ｉ_ＡとＩ’_Ａ＝｛ｉ：ρ_Ｂ（ｉ）∈Ｗ_Ｂ｝となる集合Ｉ’_Ａを求め、シェア情報生成行列Ｍ_Ｂに対応する秘密情報ｖ＿ｎ_Ｂの正当なシェア集合｛λ_Ｂｉ｝について、
   

   

   が成り立つ０以上ｐ−１以下の整数ｗ_Ａｉと整数ｗ’_Ａｉを求める第１の秘密情報取得部と、
   属性集合Ｓ_Ａがシェア情報生成行列Ｍ_Ｂと単射ラベリング関数ρ_Ｂを満たすかを確認することと、Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋ_Ｂを鍵、（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，ｓ_Ｂ）をメッセージとして検証した結果が真であること、
   

   

   が成り立つことを確認する第１の属性確認部と、
   

   

   σ_１＝（ｇ_Ｔ＾ｚ）＾ｕ＿ｎ_Ａ
   σ_３＝ｅ（ｇ＾ｒ，Ｙ）＾ｘ
   を計算し、σ’_１←Ｅｘｔ（σ_１），σ’_２←Ｅｘｔ（σ_２），σ’_３←Ｅｘｔ（σ_３）を計算し、セッション識別子ｓｉｄを（ＥＰＫ_Ａ，ＥＰＫ_Ｂ）に設定し、セッション鍵Ｋを、
   Ｋ＝Ｆ＿σ’_１（ｓｉｄ）（＋）Ｆ＿σ’_２（ｓｉｄ）（＋）Ｆ＿σ’_３（ｓｉｄ）
   のように求める第１のセッション鍵計算部と、
   少なくともｕ＿ｊ（１≦ｊ≦Ｎ_Ａ）、ｘ、ｘ_ｉ（１≦ｉ≦Ｌ_Ａ）、ＥＰＫ_Ａ、ＥＰＫ_Ｂ、σ_１、σ_２、σ_３、σ’_１、σ’_２、σ’_３、ｓｉｄ、ｓｋ_Ａを消去する第１の中間情報消去部と、
   を備え、
   前記鍵交換装置βは、
   長期秘密鍵としてＳ’_Ｂ，Ｔ_Ｂ，｛Ｓ_Ｂ｝を記録する第２の記録部と、
   アクセス構造Ａ_Ｂを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋ_Ｂと使い捨て秘密鍵ｓｋ_Ｂを生成し、ダミー属性集合Ｗ_Ｂ＝｛Ｗ_１＿ｖｋ_Ｂ１，…，Ｗ_ｄ＿ｖｋ_Ｂｄ，…，Ｗ_Ｄ＿ｖｋ_ＢＤ｝（ただし、ｖｋ_Ｂｄは使い捨て公開鍵ｖｋ_Ｂのｄ番目のビット）を設定し、当該アクセス構造Ａ_Ｂ又はすべてのダミー属性Ｗ_１＿ｖｋ_Ｂ１，…，Ｗ_Ｄ＿ｖｋ_ＢＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列Ｍ_Ｂと単射ラベリング関数ρ_Ｂを生成する第２のアクセス構造決定部と、
   １≦ｊ≦Ｎ_Ｂについてｖ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｖ＝（ｖ＿１，…，ｖ＿Ｎ_Ｂ）とし、ｙを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦Ｌ_Ｂについてｙ_ｉを０以上ｐ−１以下の整数からランダムに選定する第２の短期秘密鍵生成部と、
   １≦ｉ≦Ｌ_Ｂについてベクトルｖとベクトル（Ｍ_Ｂ）_ｉとの内積を計算してシェアλ_Ｂｉとし、Ｖ＝ｇ＾ｖ＿ｎ_ＢとＹ＝ｇ＾ｙと、１≦ｉ≦Ｌ_ＢについてＶ_ｉ＝ｇ＾（ｒλ_Ｂｉ）ｈ［ρ_Ｂ（ｉ）］＾（−ｙ_ｉ）とＹ_ｉ＝ｇ＾ｙ_ｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋ_Ｂを鍵、（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝）をメッセージとする使い捨て署名ｓ_Ｂを生成する第２の交換情報生成部と、
   ＥＰＫ_Ｂ＝（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，Ｍ_Ｂ，ρ_Ｂ，ｖｋ_Ｂ，ｓ_Ｂ）を鍵交換装置αに送信する第２の送信部と、
   鍵交換装置αから、ＥＰＫ_Ａ＝（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，Ｍ_Ａ，ρ_Ａ，ｖｋ_Ａ，ｓ_Ａ）を受信する第２の受信部と、
   Ｉ_Ｂ＝｛ｉ：ρ_Ａ（ｉ）∈Ｓ_Ｂ｝となる集合Ｉ_ＢとＩ’_Ｂ＝｛ｉ：ρ_Ａ（ｉ）∈Ｗ_Ａ｝となる集合Ｉ’_Ｂを求め、シェア情報生成行列Ｍ_Ａに対応する秘密情報ｕ＿ｎ_Ａの正当なシェア集合｛λ_Ａｉ｝について、
   

   

   が成り立つ０以上ｐ−１以下の整数ｗ_Ｂｉと整数ｗ’_Ｂｉを求める第２の秘密情報取得部と、
   属性集合Ｓ_Ｂがシェア情報生成行列Ｍ_Ａと単射ラベリング関数ρ_Ａを満たすかを確認することと、Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋ_Ａを鍵、（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，ｓ_Ａ）をメッセージとして検証した結果が真であること、
   

   

   が成り立つことを確認する第２の属性確認部と、
   

   

   σ_２＝（ｇ_Ｔ＾ｚ）＾ｖ＿ｎ_Ｂ
   σ_３＝ｅ（ｇ＾ｒ，Ｘ）＾ｙ
   を計算し、σ’_１←Ｅｘｔ（σ_１），σ’_２←Ｅｘｔ（σ_２），σ’_３←Ｅｘｔ（σ_３）を計算し、セッション識別子ｓｉｄを（ＥＰＫ_Ａ，ＥＰＫ_Ｂ）に設定し、セッション鍵Ｋを、
   Ｋ＝Ｆ＿σ’_１（ｓｉｄ）（＋）Ｆ＿σ’_２（ｓｉｄ）（＋）Ｆ＿σ’_３（ｓｉｄ）
   のように求める第２のセッション鍵計算部と、
   少なくともｖ＿ｊ（１≦ｊ≦Ｎ_Ｂ）、ｙ、ｙ_ｉ（１≦ｉ≦Ｌ_Ｂ）、ＥＰＫ_Ａ、ＥＰＫ_Ｂ、σ_１、σ_２、σ_３、σ’_１、σ’_２、σ’_３、ｓｉｄ、ｓｋ_Ｂを消去する第２の中間情報消去部と、
   を備える
   鍵交換システム。
2. 請求項１記載の鍵交換システムであって、
   さらに、マスタ鍵生成部と長期秘密鍵生成部とを有する鍵生成装置を備え、
   前記ｒ，ｚ，ｈ［１］，…，ｈ［ａｔｔ’］は、前記マスタ鍵生成部がランダムに選定したものであり、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）とマスタ秘密鍵ｇ＾ｚは前記マスタ鍵生成部が生成したものであり、
   前記ｔ_Ａとｔ_Ｂは前記長期秘密鍵生成部がランダムに選定したものであり、Ｓ’_ＡとＳ’_Ｂ、Ｔ_ＡとＴ_Ｂ、Ｓ_Ａ［ｋ_Ａ］とＳ_Ｂ［ｋ_Ｂ］は前記長期秘密鍵生成部が計算したものであり、
   前記鍵交換装置αが記録しておく前記長期秘密鍵（Ｓ’_Ａ，Ｔ_Ａ，｛Ｓ_Ａ｝）は前記鍵生成装置からを取得したものであり、前記鍵交換装置βが記録しておく前記長期秘密鍵（Ｓ’_Ｂ，Ｔ_Ｂ，｛Ｓ_Ｂ｝）は前記鍵生成装置から取得したものである
   ことを特徴とする鍵交換システム。
3. セッション鍵を交換する鍵交換装置であって、
   鍵交換する対象の鍵交換装置は、当該鍵交換装置と同じ構成であり、
   κは整数、ｐはκビットの素数、ＧとＧ_Ｔは位数ｐの群、ｇは群Ｇの生成元、ｇ_Ｔは群Ｇ_Ｔの生成元、ｅはＧ×Ｇ→Ｇ_Ｔのように写像する双線形写像、Ｆ＿σは任意長の整数を指定された鍵空間Ｋｓｐａｃｅの値σにしたがってκビットの整数に変換する擬似ランダム関数、Ｅｘｔは群Ｇの元を鍵空間Ｋｓｐａｃｅの値に変換する強ランダム抽出器、Ｄは整数、ｄは１以上Ｄ以下の整数、ｇｅｎは検証鍵のビット長がＤであるような使い捨て署名の鍵生成のアルゴリズム、ｓｉｇは検証鍵のビット長がＤであるような使い捨て署名の署名生成のアルゴリズム、ｖｅｒは検証鍵のビット長がＤであるような使い捨て署名の検証のアルゴリズム、ａｔｔ’は属性の全要素数を示す整数、Ｗ_ｄ＿Ｒはｄ番目のダミー属性を示す情報が１ビット以上のビット列Ｒであることを示す記号、Ｐ_ｎは属性を示す属性要素、属性集合Ｓ_Ａは当該鍵交換装置の属性を示す属性要素Ｐ_ｎの集合、アクセス構造Ａ_Ａは当該鍵交換装置が鍵交換する対象の鍵交換装置に求める属性要素Ｐ_ｎの組み合わせの集合、単射ラベリング関数ρ_Ａは前記アクセス構造Ａ_Ａを示す関数、属性集合ρ_Ａ（ｉ）は前記アクセス構造Ａ_Ａに対応するｉ番目の集合、シェア情報生成行列Ｍ_Ａはｉ行目が属性集合ρ_Ａ（ｉ）に対応するＬ_Ａ行Ｎ_Ａ列の行列、（Ｍ_Ａ）_ｉはシェア情報生成行列Ｍ_Ａのｉ番目の行に対応するベクトル、属性集合Ｓ_Ｂは鍵交換する対象の鍵交換装置の属性を示す属性要素Ｐ_ｎの集合、アクセス構造Ａ_Ｂは鍵交換する対象の鍵交換装置が求める属性要素Ｐ_ｎの組み合わせの集合、単射ラベリング関数ρ_Ｂは前記アクセス構造Ａ_Ｂを示す関数、属性集合ρ_Ｂ（ｉ）は前記アクセス構造Ａ_Ｂに対応するｉ番目の集合、シェア情報生成行列Ｍ_Ｂはｉ行目が属性集合ρ_Ｂ（ｉ）に対応するＬ_Ｂ行Ｎ_Ｂ列の行列、（Ｍ_Ｂ）_ｉはシェア情報生成行列Ｍ_Ｂのｉ番目の行に対応するベクトル、Ｌ_Ａ、Ｎ_Ａ、Ｌ_Ｂ、Ｎ_Ｂは整数、ｎ_Ａは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた１以上Ｎ_Ａ以下の整数、ｎ_Ｂは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた１以上Ｎ_Ｂ以下の整数、ｋ_Ａは属性集合Ｓ_Ａの要素、ｋ_Ｂは属性集合Ｓ_Ｂの要素、ｒとｚは０以上ｐ−１以下の整数、ｈ［１］，…，ｈ［ａｔｔ’］は群Ｇの元、（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔ_Ａは０以上ｐ−１以下の整数、ｔ_Ｂは０以上ｐ−１以下の整数、Ｓ’_Ａ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ａ）、Ｓ’_Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ｂ）、Ｔ_Ａ＝ｇ＾ｔ_Ａ、Ｔ_Ｂ＝ｇ＾ｔ_Ｂ、Ｓ_Ａ［ｋ_Ａ］＝ｈ［ｋ_Ａ］＾ｔ_Ａ、Ｓ_Ｂ［ｋ_Ｂ］＝ｈ［ｋ_Ｂ］＾ｔ_Ｂ、｛Ｓ_Ａ｝はＳ_Ａ［ｋ_Ａ］の集合、｛Ｓ_Ｂ｝はＳ_Ｂ［ｋ_Ｂ］の集合、｛Ｕ_ｉ｝はＵ_ｉの集合、｛Ｘ_ｉ｝はＸ_ｉの集合、｛Ｖ_ｉ｝はＶ_ｉの集合、｛Ｙ_ｉ｝はＹ_ｉの集合、＾はべき乗を示す記号、（＋）はビットごとの排他的論理和を示す記号であり、
   長期秘密鍵としてＳ’_Ａ，Ｔ_Ａ，｛Ｓ_Ａ｝を記録する記録部と、
   アクセス構造Ａ_Ａを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋ_Ａと使い捨て秘密鍵ｓｋ_Ａを生成し、ダミー属性集合Ｗ_Ａ＝｛Ｗ_１＿ｖｋ_Ａ１，…，Ｗ_ｄ＿ｖｋ_Ａｄ，…，Ｗ_Ｄ＿ｖｋ_ＡＤ｝（ただし、ｖｋ_Ａｄは使い捨て公開鍵ｖｋ_Ａのｄ番目のビット）を設定し、当該アクセス構造Ａ_Ａ又はすべてのダミー属性Ｗ_１＿ｖｋ_Ａ１，…，Ｗ_Ｄ＿ｖｋ_ＡＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列Ｍ_Ａと単射ラベリング関数ρ_Ａを生成するアクセス構造決定部と、
   １≦ｊ≦Ｎ_Ａについてｕ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｕ＝（ｕ＿１，…，ｕ＿Ｎ_Ａ）とし、ｘを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦Ｌ_Ａについてｘ_ｉを０以上ｐ−１以下の整数からランダムに選定する短期秘密鍵生成部と、
   １≦ｉ≦Ｌ_Ａについてベクトルｕとベクトル（Ｍ_Ａ）_ｉとの内積を計算してシェアλ_Ａｉとし、Ｕ＝ｇ＾ｕ＿ｎ_ＡとＸ＝ｇ＾ｘと、１≦ｉ≦Ｌ_ＡについてＵ_ｉ＝ｇ＾（ｒλ_Ａｉ）ｈ［ρ_Ａ（ｉ）］＾（−ｘ_ｉ）とＸ_ｉ＝ｇ＾ｘ_ｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋ_Ａを鍵、（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝）をメッセージとする使い捨て署名ｓ_Ａを生成する交換情報生成部と、
   ＥＰＫ_Ａ＝（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，Ｍ_Ａ，ρ_Ａ，ｖｋ_Ａ，ｓ_Ａ）を鍵交換する対象の装置に送信する送信部と、
   鍵交換する対象の装置から、ＥＰＫ_Ｂ＝（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，Ｍ_Ｂ，ρ_Ｂ，ｖｋ_Ｂ，ｓ_Ｂ）を受信する受信部と、
   Ｉ_Ａ＝｛ｉ：ρ_Ｂ（ｉ）∈Ｓ_Ａ｝となる集合Ｉ_ＡとＩ’_Ａ＝｛ｉ：ρ_Ｂ（ｉ）∈Ｗ_Ｂ｝となる集合Ｉ’_Ａを求め、シェア情報生成行列Ｍ_Ｂに対応する秘密情報ｖ＿ｎ_Ｂの正当なシェア集合｛λ_Ｂｉ｝について、
   

   

   が成り立つ０以上ｐ−１以下の整数ｗ_Ａｉと整数ｗ’_Ａｉを求める秘密情報取得部と、
   属性集合Ｓ_Ａがシェア情報生成行列Ｍ_Ｂと単射ラベリング関数ρ_Ｂを満たすかを確認することと、Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋ_Ｂを鍵、（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，ｓ_Ｂ）をメッセージとして検証した結果が真であること、
   

   

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

   

   σ_１＝（ｇ_Ｔ＾ｚ）＾ｕ＿ｎ_Ａ
   σ_３＝ｅ（ｇ＾ｒ，Ｙ）＾ｘ
   を計算し、σ’_１←Ｅｘｔ（σ_１），σ’_２←Ｅｘｔ（σ_２），σ’_３←Ｅｘｔ（σ_３）を計算し、セッション識別子ｓｉｄを（ＥＰＫ_Ａ，ＥＰＫ_Ｂ）に設定し、セッション鍵Ｋを、
   Ｋ＝Ｆ＿σ’_１（ｓｉｄ）（＋）Ｆ＿σ’_２（ｓｉｄ）（＋）Ｆ＿σ’_３（ｓｉｄ）
   のように求めるセッション鍵計算部と、
   少なくともｕ＿ｊ（１≦ｊ≦Ｎ_Ａ）、ｘ、ｘ_ｉ（１≦ｉ≦Ｌ_Ａ）、ＥＰＫ_Ａ、ＥＰＫ_Ｂ、σ_１、σ_２、σ_３、σ’_１、σ’_２、σ’_３、ｓｉｄ、ｓｋ_Ａを消去する中間情報消去部と、
   を備える鍵交換装置。
4. セッション鍵を交換する鍵交換装置であって、
   鍵交換する対象の鍵交換装置は、当該鍵交換装置と同じ構成であり、
   κは整数、ｐはκビットの素数、ＧとＧ_Ｔは位数ｐの群、ｇは群Ｇの生成元、ｇ_Ｔは群Ｇ_Ｔの生成元、ｅはＧ×Ｇ→Ｇ_Ｔのように写像する双線形写像、Ｆ＿σは任意長の整数を指定された鍵空間Ｋｓｐａｃｅの値σにしたがってκビットの整数に変換する擬似ランダム関数、Ｅｘｔは群Ｇの元を鍵空間Ｋｓｐａｃｅの値に変換する強ランダム抽出器、Ｄは整数、ｄは１以上Ｄ以下の整数、ｇｅｎは検証鍵のビット長がＤであるような使い捨て署名の鍵生成のアルゴリズム、ｓｉｇは検証鍵のビット長がＤであるような使い捨て署名の署名生成のアルゴリズム、ｖｅｒは検証鍵のビット長がＤであるような使い捨て署名の検証のアルゴリズム、ａｔｔ’は属性の全要素数を示す整数、Ｗ_ｄ＿Ｒはｄ番目のダミー属性を示す情報が１ビット以上のビット列Ｒであることを示す記号、Ｐ_ｎは属性を示す属性要素、属性集合Ｓ_Ａは鍵交換する対象の鍵交換装置の属性を示す属性要素Ｐ_ｎの集合、アクセス構造Ａ_Ａは鍵交換する対象の鍵交換装置に求める属性要素Ｐ_ｎの組み合わせの集合、単射ラベリング関数ρ_Ａは前記アクセス構造Ａ_Ａを示す関数、属性集合ρ_Ａ（ｉ）は前記アクセス構造Ａ_Ａに対応するｉ番目の集合、シェア情報生成行列Ｍ_Ａはｉ行目が属性集合ρ_Ａ（ｉ）に対応するＬ_Ａ行Ｎ_Ａ列の行列、（Ｍ_Ａ）_ｉはシェア情報生成行列Ｍ_Ａのｉ番目の行に対応するベクトル、属性集合Ｓ_Ｂは当該鍵交換装置の属性を示す属性要素Ｐ_ｎの集合、アクセス構造Ａ_Ｂは当該鍵交換装置が鍵交換する対象の鍵交換装置に求める属性要素Ｐ_ｎの組み合わせの集合、単射ラベリング関数ρ_Ｂは前記アクセス構造Ａ_Ｂを示す関数、属性集合ρ_Ｂ（ｉ）は前記アクセス構造Ａ_Ｂに対応するｉ番目の集合、シェア情報生成行列Ｍ_Ｂはｉ行目が属性集合ρ_Ｂ（ｉ）に対応するＬ_Ｂ行Ｎ_Ｂ列の行列、（Ｍ_Ｂ）_ｉはシェア情報生成行列Ｍ_Ｂのｉ番目の行に対応するベクトル、Ｌ_Ａ、Ｎ_Ａ、Ｌ_Ｂ、Ｎ_Ｂは整数、ｎ_Ａは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた１以上Ｎ_Ａ以下の整数、ｎ_Ｂは当該鍵交換装置と鍵交換する対象の鍵交換装置とで共有するあらかじめ定めた１以上Ｎ_Ｂ以下の整数、ｋ_Ａは属性集合Ｓ_Ａの要素、ｋ_Ｂは属性集合Ｓ_Ｂの要素、ｒとｚは０以上ｐ−１以下の整数、ｈ［１］，…，ｈ［ａｔｔ’］は群Ｇの元、（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔ_Ａは０以上ｐ−１以下の整数、ｔ_Ｂは０以上ｐ−１以下の整数、Ｓ’_Ａ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ａ）、Ｓ’_Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ｂ）、Ｔ_Ａ＝ｇ＾ｔ_Ａ、Ｔ_Ｂ＝ｇ＾ｔ_Ｂ、Ｓ_Ａ［ｋ_Ａ］＝ｈ［ｋ_Ａ］＾ｔ_Ａ、Ｓ_Ｂ［ｋ_Ｂ］＝ｈ［ｋ_Ｂ］＾ｔ_Ｂ、｛Ｓ_Ａ｝はＳ_Ａ［ｋ_Ａ］の集合、｛Ｓ_Ｂ｝はＳ_Ｂ［ｋ_Ｂ］の集合、｛Ｕ_ｉ｝はＵ_ｉの集合、｛Ｘ_ｉ｝はＸ_ｉの集合、｛Ｖ_ｉ｝はＶ_ｉの集合、｛Ｙ_ｉ｝はＹ_ｉの集合、＾はべき乗を示す記号、（＋）はビットごとの排他的論理和を示す記号であり、
   長期秘密鍵としてＳ’_Ｂ，Ｔ_Ｂ，｛Ｓ_Ｂ｝を記録する記録部と、
   アクセス構造Ａ_Ｂを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋ_Ｂと使い捨て秘密鍵ｓｋ_Ｂを生成し、ダミー属性集合Ｗ_Ｂ＝｛Ｗ_１＿ｖｋ_Ｂ１，…，Ｗ_ｄ＿ｖｋ_Ｂｄ，…，Ｗ_Ｄ＿ｖｋ_ＢＤ｝（ただし、ｖｋ_Ｂｄは使い捨て公開鍵ｖｋ_Ｂのｄ番目のビット）を設定し、当該アクセス構造Ａ_Ｂ又はすべてのダミー属性Ｗ_１＿ｖｋ_Ｂ１，…，Ｗ_Ｄ＿ｖｋ_ＢＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列Ｍ_Ｂと単射ラベリング関数ρ_Ｂを生成するアクセス構造決定部と、
   １≦ｊ≦Ｎ_Ｂについてｖ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｖ＝（ｖ＿１，…，ｖ＿Ｎ_Ｂ）とし、ｙを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦Ｌ_Ｂについてｙ_ｉを０以上ｐ−１以下の整数からランダムに選定する短期秘密鍵生成部と、
   １≦ｉ≦Ｌ_Ｂについてベクトルｖとベクトル（Ｍ_Ｂ）_ｉとの内積を計算してシェアλ_Ｂｉとし、Ｖ＝ｇ＾ｖ＿ｎ_ＢとＹ＝ｇ＾ｙと、１≦ｉ≦Ｌ_ＢについてＶ_ｉ＝ｇ＾（ｒλ_Ｂｉ）ｈ［ρ_Ｂ（ｉ）］＾（−ｙ_ｉ）とＹ_ｉ＝ｇ＾ｙ_ｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋ_Ｂを鍵、（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝）をメッセージとする使い捨て署名ｓ_Ｂを生成する交換情報生成部と、
   ＥＰＫ_Ｂ＝（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，Ｍ_Ｂ，ρ_Ｂ，ｖｋ_Ｂ，ｓ_Ｂ）を鍵交換する対象の鍵交換装置に送信する送信部と、
   鍵交換する対象の鍵交換装置から、ＥＰＫ_Ａ＝（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，Ｍ_Ａ，ρ_Ａ，ｖｋ_Ａ，ｓ_Ａ）を受信する受信部と、
   Ｉ_Ｂ＝｛ｉ：ρ_Ａ（ｉ）∈Ｓ_Ｂ｝となる集合Ｉ_ＢとＩ’_Ｂ＝｛ｉ：ρ_Ａ（ｉ）∈Ｗ_Ａ｝となる集合Ｉ’_Ｂを求め、シェア情報生成行列Ｍ_Ａに対応する秘密情報ｕ＿ｎ_Ａの正当なシェア集合｛λ_Ａｉ｝について、
   

   

   が成り立つ０以上ｐ−１以下の整数ｗ_Ｂｉと整数ｗ’_Ｂｉを求める秘密情報取得部と、
   属性集合Ｓ_Ｂがシェア情報生成行列Ｍ_Ａと単射ラベリング関数ρ_Ａを満たすかを確認することと、Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋ_Ａを鍵、（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，ｓ_Ａ）をメッセージとして検証した結果が真であること、
   

   

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

   

   σ_２＝（ｇ_Ｔ＾ｚ）＾ｖ＿ｎ_Ｂ
   σ_３＝ｅ（ｇ＾ｒ，Ｘ）＾ｙ
   を計算し、σ’_１←Ｅｘｔ（σ_１），σ’_２←Ｅｘｔ（σ_２），σ’_３←Ｅｘｔ（σ_３）を計算し、セッション識別子ｓｉｄを（ＥＰＫ_Ａ，ＥＰＫ_Ｂ）に設定し、セッション鍵Ｋを、
   Ｋ＝Ｆ＿σ’_１（ｓｉｄ）（＋）Ｆ＿σ’_２（ｓｉｄ）（＋）Ｆ＿σ’_３（ｓｉｄ）
   のように求めるセッション鍵計算部と、
   少なくともｖ＿ｊ（１≦ｊ≦Ｎ_Ｂ）、ｙ、ｙ_ｉ（１≦ｉ≦Ｌ_Ｂ）、ＥＰＫ_Ａ、ＥＰＫ_Ｂ、σ_１、σ_２、σ_３、σ’_１、σ’_２、σ’_３、ｓｉｄ、ｓｋ_Ｂを消去する中間情報消去部と、
   を備える鍵交換装置。
5. 少なくとも鍵交換装置αと鍵交換装置βとを備える鍵交換システムを用いて、セッション鍵を交換する鍵交換方法であって、
   κは整数、ｐはκビットの素数、ＧとＧ_Ｔは位数ｐの群、ｇは群Ｇの生成元、ｇ_Ｔは群Ｇ_Ｔの生成元、ｅはＧ×Ｇ→Ｇ_Ｔのように写像する双線形写像、Ｆ＿σは任意長の整数を指定された鍵空間Ｋｓｐａｃｅの値σにしたがってκビットの整数に変換する擬似ランダム関数、Ｅｘｔは群Ｇの元を鍵空間Ｋｓｐａｃｅの値に変換する強ランダム抽出器、Ｄは整数、ｄは１以上Ｄ以下の整数、ｇｅｎは検証鍵のビット長がＤであるような使い捨て署名の鍵生成のアルゴリズム、ｓｉｇは検証鍵のビット長がＤであるような使い捨て署名の署名生成のアルゴリズム、ｖｅｒは検証鍵のビット長がＤであるような使い捨て署名の検証のアルゴリズム、ａｔｔ’は属性の全要素数を示す整数、Ｗ_ｄ＿Ｒはｄ番目のダミー属性を示す情報が１ビット以上のビット列Ｒであることを示す記号、Ｐ_ｎは属性を示す属性要素、属性集合Ｓ_Ａは鍵交換装置αの属性を示す属性要素Ｐ_ｎの集合、アクセス構造Ａ_Ａは鍵交換装置αが鍵交換装置βに求める属性要素Ｐ_ｎの組み合わせの集合、単射ラベリング関数ρ_Ａは前記アクセス構造Ａ_Ａを示す関数、属性集合ρ_Ａ（ｉ）は前記アクセス構造Ａ_Ａに対応するｉ番目の集合、シェア情報生成行列Ｍ_Ａはｉ行目が属性集合ρ_Ａ（ｉ）に対応するＬ_Ａ行Ｎ_Ａ列の行列、（Ｍ_Ａ）_ｉはシェア情報生成行列Ｍ_Ａのｉ番目の行に対応するベクトル、属性集合Ｓ_Ｂは鍵交換装置βの属性を示す属性要素Ｐ_ｎの集合、アクセス構造Ａ_Ｂは鍵交換装置βが鍵交換装置αに求める属性要素Ｐ_ｎの組み合わせの集合、単射ラベリング関数ρ_Ｂは前記アクセス構造Ａ_Ｂを示す関数、属性集合ρ_Ｂ（ｉ）は前記アクセス構造Ａ_Ｂに対応するｉ番目の集合、シェア情報生成行列Ｍ_Ｂはｉ行目が属性集合ρ_Ｂ（ｉ）に対応するＬ_Ｂ行Ｎ_Ｂ列の行列、（Ｍ_Ｂ）_ｉはシェア情報生成行列Ｍ_Ｂのｉ番目の行に対応するベクトル、Ｌ_Ａ、Ｎ_Ａ、Ｌ_Ｂ、Ｎ_Ｂは整数、ｎ_Ａは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた１以上Ｎ_Ａ以下の整数、ｎ_Ｂは前記鍵交換装置αと前記鍵交換装置βとで共有するあらかじめ定めた１以上Ｎ_Ｂ以下の整数、ｋ_Ａは属性集合Ｓ_Ａの要素、ｋ_Ｂは属性集合Ｓ_Ｂの要素、ｒとｚは０以上ｐ−１以下の整数、ｈ［１］，…，ｈ［ａｔｔ’］は群Ｇの元、（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔ_Ａは０以上ｐ−１以下の整数、ｔ_Ｂは０以上ｐ−１以下の整数、Ｓ’_Ａ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ａ）、Ｓ’_Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔ_Ｂ）、Ｔ_Ａ＝ｇ＾ｔ_Ａ、Ｔ_Ｂ＝ｇ＾ｔ_Ｂ、Ｓ_Ａ［ｋ_Ａ］＝ｈ［ｋ_Ａ］＾ｔ_Ａ、Ｓ_Ｂ［ｋ_Ｂ］＝ｈ［ｋ_Ｂ］＾ｔ_Ｂ、｛Ｓ_Ａ｝はＳ_Ａ［ｋ_Ａ］の集合、｛Ｓ_Ｂ｝はＳ_Ｂ［ｋ_Ｂ］の集合、｛Ｕ_ｉ｝はＵ_ｉの集合、｛Ｘ_ｉ｝はＸ_ｉの集合、｛Ｖ_ｉ｝はＶ_ｉの集合、｛Ｙ_ｉ｝はＹ_ｉの集合、＾はべき乗を示す記号、（＋）はビットごとの排他的論理和を示す記号であり、
   前記鍵交換装置αは、長期秘密鍵としてＳ’_Ａ，Ｔ_Ａ，｛Ｓ_Ａ｝を記録しておき、
   前記鍵交換装置βは、長期秘密鍵としてＳ’_Ｂ，Ｔ_Ｂ，｛Ｓ_Ｂ｝を記録しておき、
   前記鍵交換装置αが、アクセス構造Ａ_Ａを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋ_Ａと使い捨て秘密鍵ｓｋ_Ａを生成し、ダミー属性集合Ｗ_Ａ＝｛Ｗ_１＿ｖｋ_Ａ１，…，Ｗ_ｄ＿ｖｋ_Ａｄ，…，Ｗ_Ｄ＿ｖｋ_ＡＤ｝（ただし、ｖｋ_Ａｄは使い捨て公開鍵ｖｋ_Ａのｄ番目のビット）を設定し、当該アクセス構造Ａ_Ａ又はすべてのダミー属性Ｗ_１＿ｖｋ_Ａ１，…，Ｗ_Ｄ＿ｖｋ_ＡＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列Ｍ_Ａと単射ラベリング関数ρ_Ａを生成する第１のアクセス構造決定ステップと、
   前記鍵交換装置αが、１≦ｊ≦Ｎ_Ａについてｕ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｕ＝（ｕ＿１，…，ｕ＿Ｎ_Ａ）とし、ｘを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦Ｌ_Ａについてｘ_ｉを０以上ｐ−１以下の整数からランダムに選定する第１の短期秘密鍵生成ステップと、
   前記鍵交換装置αが、１≦ｉ≦Ｌ_Ａについてベクトルｕとベクトル（Ｍ_Ａ）_ｉとの内積を計算してシェアλ_Ａｉとし、Ｕ＝ｇ＾ｕ＿ｎ_ＡとＸ＝ｇ＾ｘと、１≦ｉ≦Ｌ_ＡについてＵ_ｉ＝ｇ＾（ｒλ_Ａｉ）ｈ［ρ_Ａ（ｉ）］＾（−ｘ_ｉ）とＸ_ｉ＝ｇ＾ｘ_ｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋ_Ａを鍵、（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝）をメッセージとする使い捨て署名ｓ_Ａを生成する第１の交換情報生成ステップと、
   前記鍵交換装置αが、ＥＰＫ_Ａ＝（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，Ｍ_Ａ，ρ_Ａ，ｖｋ_Ａ，ｓ_Ａ）を前記鍵交換装置βに送信する第１の送信ステップと、
   前記鍵交換装置βが、アクセス構造Ａ_Ｂを決定し、使い捨て署名の鍵生成のアルゴリズムｇｅｎにしたがって使い捨て公開鍵ｖｋ_Ｂと使い捨て秘密鍵ｓｋ_Ｂを生成し、ダミー属性集合Ｗ_Ｂ＝｛Ｗ_１＿ｖｋ_Ｂ１，…，Ｗ_ｄ＿ｖｋ_Ｂｄ，…，Ｗ_Ｄ＿ｖｋ_ＢＤ｝（ただし、ｖｋ_Ｂｄは使い捨て公開鍵ｖｋ_Ｂのｄ番目のビット）を設定し、当該アクセス構造Ａ_Ｂ又はすべてのダミー属性Ｗ_１＿ｖｋ_Ｂ１，…，Ｗ_Ｄ＿ｖｋ_ＢＤを満たす条件に対応する線形秘密分散法のシェア情報生成行列Ｍ_Ｂと単射ラベリング関数ρ_Ｂを生成する第２のアクセス構造決定ステップと、
   前記鍵交換装置βが、１≦ｊ≦Ｎ_Ｂについてｖ＿ｊを０以上ｐ−１以下の整数からランダムに選定してｖ＝（ｖ＿１，…，ｖ＿Ｎ_Ｂ）とし、ｙを０以上ｐ−１以下の整数からランダムに選定し、１≦ｉ≦Ｌ_Ｂについてｙ_ｉを０以上ｐ−１以下の整数からランダムに選定する第２の短期秘密鍵生成ステップと、
   前記鍵交換装置βが、１≦ｉ≦Ｌ_Ｂについてベクトルｖとベクトル（Ｍ_Ｂ）_ｉとの内積を計算してシェアλ_Ｂｉとし、Ｖ＝ｇ＾ｖ＿ｎ_ＢとＹ＝ｇ＾ｙと、１≦ｉ≦Ｌ_ＢについてＶ_ｉ＝ｇ＾（ｒλ_Ｂｉ）ｈ［ρ_Ｂ（ｉ）］＾（−ｙ_ｉ）とＹ_ｉ＝ｇ＾ｙ_ｉを計算し、使い捨て署名の署名生成のアルゴリズムｓｉｇにしたがってｓｋ_Ｂを鍵、（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝）をメッセージとする使い捨て署名ｓ_Ｂを生成する第２の交換情報生成ステップと、
   前記鍵交換装置βが、ＥＰＫ_Ｂ＝（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，Ｍ_Ｂ，ρ_Ｂ，ｖｋ_Ｂ，ｓ_Ｂ）を前記鍵交換装置αに送信する第２の送信ステップと、
   前記鍵交換装置βが、前記鍵交換装置αから、ＥＰＫ_Ａ＝（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，Ｍ_Ａ，ρ_Ａ，ｖｋ_Ａ，ｓ_Ａ）を受信する第２の受信ステップと、
   前記鍵交換装置βが、属性集合Ｓ_Ｂがシェア情報生成行列Ｍ_Ａと単射ラベリング関数ρ_Ａを満たすかを確認する第２の簡易属性確認ステップと、
   前記鍵交換装置βが、Ｉ_Ｂ＝｛ｉ：ρ_Ａ（ｉ）∈Ｓ_Ｂ｝となる集合Ｉ_ＢとＩ’_Ｂ＝｛ｉ：ρ_Ａ（ｉ）∈Ｗ_Ａ｝となる集合Ｉ’_Ｂを求め、シェア情報生成行列Ｍ_Ａに対応する秘密情報ｕ＿ｎ_Ａの正当なシェア集合｛λ_Ａｉ｝について、
   

   

   が成り立つ０以上ｐ−１以下の整数ｗ_Ｂｉと整数ｗ’_Ｂｉを求める第２の秘密情報取得ステップと、
   前記鍵交換装置βが、Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋ_Ａを鍵、（Ｕ，｛Ｕ_ｉ｝，Ｘ，｛Ｘ_ｉ｝，ｓ_Ａ）をメッセージとして検証した結果が真であること、
   

   

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

   

   σ_２＝（ｇ_Ｔ＾ｚ）＾ｖ＿ｎ_Ｂ
   σ_３＝ｅ（ｇ＾ｒ，Ｘ）＾ｙ
   を計算し、σ’_１←Ｅｘｔ（σ_１），σ’_２←Ｅｘｔ（σ_２），σ’_３←Ｅｘｔ（σ_３）を計算し、セッション識別子ｓｉｄを（ＥＰＫ_Ａ，ＥＰＫ_Ｂ）に設定し、セッション鍵Ｋを、
   Ｋ＝Ｆ＿σ’_１（ｓｉｄ）（＋）Ｆ＿σ’_２（ｓｉｄ）（＋）Ｆ＿σ’_３（ｓｉｄ）
   のように求める第２のセッション鍵計算ステップと、
   前記鍵交換装置βが、少なくともｖ＿ｊ（１≦ｊ≦Ｎ_Ｂ）、ｙ、ｙ_ｉ（１≦ｉ≦Ｌ_Ｂ）、ＥＰＫ_Ａ、ＥＰＫ_Ｂ、σ_１、σ_２、σ_３、σ’_１、σ’_２、σ’_３、ｓｉｄ、ｓｋ_Ｂを消去する第２の中間情報消去ステップと、
   前記鍵交換装置αが、前記鍵交換装置βから、ＥＰＫ_Ｂ＝（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，Ｍ_Ｂ，ρ_Ｂ，ｖｋ_Ｂ，ｓ_Ｂ）を受信する第１の受信ステップと、
   前記鍵交換装置αが、属性集合Ｓ_Ａがシェア情報生成行列Ｍ_Ｂと単射ラベリング関数ρ_Ｂを満たすかを確認する第１の簡易属性確認ステップと、
   前記鍵交換装置αが、Ｉ_Ａ＝｛ｉ：ρ_Ｂ（ｉ）∈Ｓ_Ａ｝となる集合Ｉ_ＡとＩ’_Ａ＝｛ｉ：ρ_Ｂ（ｉ）∈Ｗ_Ｂ｝となる集合Ｉ’_Ａを求め、シェア情報生成行列Ｍ_Ｂに対応する秘密情報ｖ＿ｎ_Ｂの正当なシェア集合｛λ_Ｂｉ｝について、
   

   

   が成り立つ０以上ｐ−１以下の整数ｗ_Ａｉと整数ｗ’_Ａｉを求める第１の秘密情報取得ステップと、
   前記鍵交換装置αが、Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝のすべてが群Ｇの元であること、使い捨て署名の検証のアルゴリズムにしたがってｖｋ_Ｂを鍵、（Ｖ，｛Ｖ_ｉ｝，Ｙ，｛Ｙ_ｉ｝，ｓ_Ｂ）をメッセージとして検証した結果が真であること、
   

   

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

   

   σ_１＝（ｇ_Ｔ＾ｚ）＾ｕ＿ｎ_Ａ
   σ_３＝ｅ（ｇ＾ｒ，Ｙ）＾ｘ
   を計算し、σ’_１←Ｅｘｔ（σ_１），σ’_２←Ｅｘｔ（σ_２），σ’_３←Ｅｘｔ（σ_３）を計算し、セッション識別子ｓｉｄを（ＥＰＫ_Ａ，ＥＰＫ_Ｂ）に設定し、セッション鍵Ｋを、
   Ｋ＝Ｆ＿σ’_１（ｓｉｄ）（＋）Ｆ＿σ’_２（ｓｉｄ）（＋）Ｆ＿σ’_３（ｓｉｄ）
   のように求める第１のセッション鍵計算ステップと、
   前記鍵交換装置αが、少なくともｕ＿ｊ（１≦ｊ≦Ｎ_Ａ）、ｘ、ｘ_ｉ（１≦ｉ≦Ｌ_Ａ）、ＥＰＫ_Ａ、ＥＰＫ_Ｂ、σ_１、σ_２、σ_３、σ’_１、σ’_２、σ’_３、ｓｉｄ、ｓｋ_Ａを消去する第１の中間情報消去ステップと、
   を有する鍵交換方法。
6. 請求項５記載の鍵交換方法であって、
   前記鍵交換システムは、さらにマスタ鍵生成手段と長期秘密鍵生成手段も備え、
   前記マスタ鍵生成手段が、前記ｒ，ｚ，ｈ［１］，…，ｈ［ａｔｔ’］をランダムに選定し、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇ_Ｔ＾ｚ，ｈ［１］，…，ｈ［ａｔｔ’］）とマスタ秘密鍵ｇ＾ｚを生成するマスタ鍵生成ステップと、
   前記長期秘密鍵生成手段が、前記ｔ_Ａとｔ_Ｂをランダムに選定し、Ｓ’_ＡとＳ’_Ｂ、Ｔ_ＡとＴ_Ｂ、Ｓ_Ａ［ｋ_Ａ］とＳ_Ｂ［ｋ_Ｂ］を計算する長期秘密鍵生成ステップと、
   前記鍵交換装置αが、長期秘密鍵としてＳ’_Ａ，Ｔ_Ａ，｛Ｓ_Ａ｝を取得する第１の長期秘密鍵取得ステップと、
   前記鍵交換装置βが、長期秘密鍵としてＳ’_Ｂ，Ｔ_Ｂ，｛Ｓ_Ｂ｝を取得する第２の長期秘密鍵取得ステップ
   も有することを特徴とする鍵交換方法。
7. 請求項３または４記載の鍵交換装置としてコンピュータを機能させるための鍵交換プログラム。

Images