鍵交換装置、鍵生成装置、鍵交換システム、鍵交換方法、プログラム
【課題】鍵交換時にアクセスポリシーを指定でき、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができる鍵交換システムを提供する。
【解決手段】本発明の鍵交換システムは、少なくとも鍵交換装置αと鍵交換装置βとを備え、セッション鍵を交換する。本発明の鍵交換システムは、線形秘密分散法を利用することにより、長期秘密鍵の生成を行うときには鍵生成装置が、鍵交換装置αの属性集合ＳＡに基づき線形秘密分散法のシェア情報として長期秘密鍵Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造ＡＡを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定する。また、本発明では、属性集合とは独立なマスタ秘密鍵ｇ＾ｚとマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）を用いる。
【解決手段】本発明の鍵交換システムは、少なくとも鍵交換装置αと鍵交換装置βとを備え、セッション鍵を交換する。本発明の鍵交換システムは、線形秘密分散法を利用することにより、長期秘密鍵の生成を行うときには鍵生成装置が、鍵交換装置αの属性集合ＳＡに基づき線形秘密分散法のシェア情報として長期秘密鍵Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造ＡＡを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定する。また、本発明では、属性集合とは独立なマスタ秘密鍵ｇ＾ｚとマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）を用いる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報セキュリティに関するものであり、特に、二者間でセッション鍵を共有するための鍵交換装置、鍵生成装置、鍵交換システム、鍵交換方法、プログラムに関する。
【背景技術】
【０００２】
非特許文献１の述語認証鍵交換方式が従来技術として知られている。図１は、非特許文献１の鍵交換システムの構成例を示す図である。このシステムは、ネットワーク１０００で接続された鍵生成手段９００、鍵抽出手段８００、鍵交換装置７００１，…，７００Ｑ（ただし、Ｑは２以上の整数、ＡとＢは１以上Ｑ以下の異なる整数）で構成されている。以下に、このシステムを用いた鍵交換について説明する。
【０００３】
［準備］
γを根付き木とし、Ｌ（γ）をγの全ての葉ノードの集合とする。葉ノードでないノードに対してｃｕを子ノードの数とし、葉ノードについてはｃｕ＝１として扱う。つまり、葉ノードを１つだけ持つノードと葉ノードのｃｕが１である。
【０００４】
それぞれのノードｕにはしきい値ｋｕ（１≦ｋｕ≦ｃｕ）が割り当てられる。ここで、葉ノードを１つだけ持つノードと葉ノードについてはｋｕ＝ｃｕ＝１となる。それぞれのノードｕに対して、
ｉｎｄｅｘ（ｕ）∈｛１，…，ｃｗ｝
を割り当てる。ただし、ノードｗはノードｕの親ノードとし、ノードｕはノードｗのｉｎｄｅｘ（ｕ）番目の子ノードとする。このとき、根付き木のそれぞれのノードｕにはｋｕ−ｏｕｔ−ｏｆ−ｃｕのしきい値ゲートが割り当てられる。
【０００５】
Ｕ＝｛１，２，…，ｎ｝
を属性の全体集合とする。それぞれの葉ノードに対して
ａｔｔ（ｕ）∈Ｕ
を割り当てる。すなわち、根付き木のそれぞれの葉ノードｕに１つの属性が割り当てられる。(ｋｕ，ｉｎｄｅｘ（ｕ），ａｔｔ（ｕ）) を持つ根付き木γをアクセス木と呼ぶ。
【０００６】
属性集合δ⊂Ｕがアクセス木γを満たすことを次のように定義する。葉ノードｕについて、
ａｔｔ（ｕ）⊂δ
が成り立つとき、ｕは満たされたという。葉ノードでないノードｕについて、ｕの満たされた子ノードの数がｋｕ以上であるとき、ｕは満たされたという。根ノードｕｒが満たされたとき、属性集合δ⊂Ｕがアクセス木γを満たすという。
【０００７】
［公開パラメータ］
ｐｉｄはプロトコルＩＤであって、プロトコル仕様に対応した固有の識別子とする。セキュリティパラメータをκとする。ｐをκビット素数とし、ＧとＧＴをそれぞれ双線形ペアリング関数ｅ：Ｇ×Ｇ→ＧＴを効率的に計算可能なｇとｇＴを生成元とする群とする。Ｈは任意長の整数をκビットの整数に変換するハッシュ関数、Ｈ’は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数とする。０以上ｐ−１以下の整数ｉと０以上ｐ−１以下の整数のある要素Ｓについて、Δｉ，Ｓ（ｘ）を
【０００８】
【数１】
【０００９】
となるようなラグランジュ係数とする。
［鍵生成］
鍵生成手段９００は、マスタ秘密鍵ｚを０以上ｐ−１以下の整数からランダムに選定する。また、すべての属性ｉ（ただし、ｉ∈Ｕ）について、ｔｉを０以上ｐ−１以下の整数からランダムに選定する。さらに、鍵生成手段９００は、群ＧＴの元であるマスタ公開鍵Ｚ＝ｇＴ＾ｚと｛Ｔｉ＝ｇ＾ｔｉ｝（ただし、ｉ∈Ｕ）を公開する。ここで、＾はべき乗を示している。
【００１０】
［鍵抽出］
鍵抽出手段８００は、鍵交換装置７００Ａのアクセス木γＡが入力されると、長期秘密鍵｛Ｄｕ｝（ただし、ｕ∈Ｌ（γＡ））をγＡのそれぞれのノードについて多項式ｑｕを選ぶことによって次のように計算する。
【００１１】
まず、鍵抽出手段８００は、多項式ｑｕの次数をｄｕ＝ｋｕ−１に設定する。根ノードｕｒについて、ｑｕ＿ｒ（０）＝ｚとしｑｕ＿ｒのその他のｄｕ＿ｒ点を０以上ｐ−１以下の整数からランダムに選ぶ。よって、ｑｕ＿ｒが一意に定まるため、残りｃｕ＿ｒ−ｄｕ＿ｒ点も一意に決まる。なお、ｑｕ＿ｒ、ｃｕ＿ｒ、ｄｕ＿ｒの下付きの添え字である“ｕ＿ｒ”は、“ｕｒ”を意味している。その他のノードｕについて、ｑｕ（０）＝ｑｕ’（ｉｎｄｅｘ（ｕ））とする。ただし、ｕ’はｕの親ノードである。ｑｕのその他のｄｕ点を０以上ｐ−１以下の整数からランダムに選ぶ。このように全てのノードの多項式を再帰的に決定していく。次に、それぞれの葉ノードｕの秘密の値を
【００１２】
【数２】
【００１３】
として計算する。ただし、ｉ＝ａｔｔ（ｕ）である。最後に、鍵抽出手段８００は、ｕ∈Ｌ（γＡ）であるすべてのｕについての秘密の値Ｄｕの集合（以下では、｛Ｄｕ｝（ｕ∈Ｌ（γＡ）と表記する）を長期秘密鍵として出力する。
鍵交換装置７００Ｂのアクセス木γＢに対する長期秘密鍵｛Ｄｕ｝（ｕ∈Ｌ（γＢ））も同様の手続きによって計算する。
【００１４】
［鍵交換］
以下では、鍵交換装置７００Ａを鍵交換処理でのイニシエータ、鍵交換装置７００Ｂをレスポンダとする。鍵交換装置７００Ａはアクセス木γＡに対応する長期秘密鍵｛Ｄｕ｝（ｕ∈Ｌ（γＡ））を持ち、鍵交換装置７００Ｂはアクセス木γＢに対応する長期秘密鍵｛Ｄｕ｝（ｕ∈Ｌ（γＢ））を持つ。このとき、鍵交換装置７００Ａは属性集合δＡに対応する短期公開鍵（Ｘ，｛Ｔｉｘ｝）（ただし、ｉ∈δＡ）を鍵交換装置７００Ｂに送り、鍵交換装置７００Ｂは属性集合δＢに対応する短期公開鍵（Ｙ，｛Ｔｉｙ｝）（ただし、ｉ∈δＢ）を鍵交換装置７００Ａに送る。最後に、鍵交換装置７００Ａと鍵交換装置７００Ｂは、属性集合δＢがアクセス木γＡを満たし、属性集合δＡがアクセス木γＢを満たしたとき、またはその限りにおいて、セッション鍵Ｋを共有できる。なお、属性集合δＢがアクセス木γＡを満たし、属性集合δＡがアクセス木γＢを満たすとは、
述語Ｐ:｛０，１｝Ｌ×｛０，１｝Ｌ→｛０，１｝
を用いて、それぞれＰ（γＡ，δＢ）＝１，Ｐ（γＢ，δＡ）＝１と表現する。なお、ＬはＬ（γ）に属する全葉ノードの数である。本発明の場合、Ｐは「属性集合がアクセス木を満たす」という命題を表す。
【００１５】
つまり、鍵交換装置７００Ａは、属性集合δＡが鍵交換装置７００Ｂのアクセス木γＢを満たすならば認証成功となることを期待して属性集合δＡを設定する。また、鍵交換装置７００Ｂは、属性集合δＢが鍵交換装置７００Ａのアクセス木γＡを満たすならば認証成功となることを期待して属性集合δＢを設定する。なお、鍵交換の具体的な処理については、非特許文献１を参照されたい。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】A.Fujioka, K.Suzuki, K.Yoneyama,”Predicate-based Authenticated Key Exchange Resilient to Ephemeral Key Leakage”, In: WISA 2010.
【発明の概要】
【発明が解決しようとする課題】
【００１７】
しかしながら、従来技術は以下のような２つの課題がある。
（課題１）アクセスポリシーを鍵交換時に指定できない。
（課題２）マスタ秘密鍵とマスタ公開鍵が属性の全体集合にパラメータライズされるため、鍵生成時に属性の全体集合をあらかじめ決めておかなければならない。したがって、あらかじめ決めた属性以外の任意の属性を扱うことができない。
【００１８】
本発明はこのような課題に鑑みてなされたものであり、鍵交換時にアクセスポリシーを指定でき、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができる鍵交換システムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
本発明の鍵交換システムは、少なくとも鍵交換装置αと鍵交換装置βとを備え、セッション鍵を交換する。ここで、κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置αの属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＡは鍵交換装置αが鍵交換装置βに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉ，ｊはシェア情報生成行列ＭＡのｉ行ｊ列の要素、属性集合ＳＢは鍵交換装置βの属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＢは鍵交換装置βが鍵交換装置αに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉ，ｊはシェア情報生成行列ＭＢのｉ行ｊ列の要素、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ＮＭＡＸはＮＡとＮＢが取りうる最大の整数、ｎとｊは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡ［１］，…，ｔＡ［ＮＭＡＸ］は０以上ｐ−１以下の整数、ｔＢ［１］，…，ｔＢ［ＮＭＡＸ］は０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ［１］）、ＴＡ［ｊ］＝ｇ＾ｔＡ［１］、ＴＢ［ｊ］＝ｇ＾ｔＢ［１］、
【００２０】
【数３】
、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＴＢ｝はＴＢ［１］，…，ＴＢ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、｛ＳＢ｝はＳＢ［１］，…，ＳＢ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合、＾はべき乗を示す記号とする。
【００２１】
鍵交換装置αは、第１のアクセス構造決定部、第１の短期秘密鍵生成部、第１の交換情報生成部、第１の送信部、第１の受信部、第１の属性確認部、第１の秘密情報取得部、第１のセッション鍵計算部、第１の中間情報消去部を備える。鍵交換装置βは、第２のアクセス構造決定部、第２の短期秘密鍵生成部、第２の交換情報生成部、第２の送信部、第２の受信部、第２の属性確認部、第２の秘密情報取得部、第２のセッション鍵計算部、第２の中間情報消去部を備える。
【００２２】
第１のアクセス構造決定部は、アクセス構造ＡＡを決定し、当該アクセス構造ＡＡに対応するシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する。第１の短期秘密鍵生成部は、１≦ｊ≦ＮＡについて、ｕ〜ｊを０以上ｐ−１以下の整数からランダムに選定する。第１の交換情報生成部は、
１≦ｊ≦ＮＡについて、ｕｊ＝Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜ｊ）、
Ｘ＝ｇ＾ｕ１、
１≦ｉ≦ＬＡと１≦ｊ≦ＮＡについて、
Ｕｉ，ｊ＝ｇ＾（ｒ（ＭＡ）ｉ，ｊｕｊ）・Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）、
１≦ｉ≦ＬＡとＮＡ＋１≦ｊ≦ＮＭＡＸについて、
Ｕｉ，ｊ＝Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）
を計算する。第１の送信部は、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを鍵交換装置βに送信する。第１の受信部は、鍵交換装置βから、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを受信する。第１の属性確認部は、属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすか、Ｙと｛Ｖ｝が群Ｇの要素かを確認する。第１の秘密情報取得部は、ＩＡ＝｛ｋ：ρＢ（ｋ）∈ＳＡ｝となる集合ＩＡを求め、鍵交換装置βが生成した秘密情報ｖ１に対する正当なシェア情報集合｛（ＭＢ）ｉ，ｊｖｊ｝について
【００２３】
【数４】
が成り立つ０以上ｐ−１以下の整数ｗＡ［ｋ］（ただし、ｋは集合ＩＡの要素）を求める。第１のセッション鍵計算部は、
【００２４】
【数５】
σ１＝（ｇＴ＾ｚ）＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
σ３＝Ｙ＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める。第１の中間情報消去部は、ｕｊ（１≦ｊ≦ＮＡ）を消去する。
【００２５】
第２のアクセス構造決定部は、アクセス構造ＡＢを決定し、当該アクセス構造ＡＢに対応するシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する。第２の短期秘密鍵生成部は、１≦ｊ≦ＮＢについて、ｖ〜ｊを０以上ｐ−１以下の整数からランダムに選定する。
【００２６】
第２の交換情報生成部は、
１≦ｊ≦ＮＢについて、ｖｊ＝Ｈ２（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝，ｖ〜ｊ）と、
Ｙ＝ｇ＾ｖ１と、
１≦ｉ≦ＬＢと１≦ｊ≦ＮＢについて、
Ｖｉ，ｊ＝ｇ＾（ｒ（ＭＢ）ｉ，ｊｖｊ）・Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と、
１≦ｉ≦ＬＢとＮＢ＋１≦ｊ≦ＮＭＡＸについて、
Ｖｉ，ｊ＝Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と
を計算する。第２の送信部は、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを鍵交換装置αに送信する。第２の受信部は、鍵交換装置αから、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを受信する。第２の属性確認部は、属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすか、Ｘと｛Ｕ｝が群Ｇの要素かを確認する。第２の秘密情報取得部は、ＩＢ＝｛ｋ：ρＡ（ｋ）∈ＳＢ｝となる集合ＩＢを求め、鍵交換装置αが生成した秘密情報ｕ１に対する正当なシェア情報集合｛（ＭＡ）ｉ，ｊｕｊ｝について
【００２７】
【数６】
【００２８】
が成り立つ０以上ｐ−１以下の整数ｗＢ［ｋ］（ただし、ｋは集合ＩＢの要素）を求める。第２のセッション鍵計算部は、
【００２９】
【数７】
σ２＝（ｇＴ＾ｚ）＾ｖ１
σ３＝Ｘ＾ｖ１
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める。第２の中間情報消去部は、ｖｊ（１≦ｊ≦ＮＢ）を消去する。
【００３０】
なお、本発明の鍵交換システムは、さらに、マスタ鍵生成部と長期秘密鍵生成部とを有する鍵生成装置を備えてもよい。マスタ鍵生成部がランダムにｒとｚを選定し、前記マスタ鍵生成部がマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）とマスタ秘密鍵ｇ＾ｚを生成すればよい。また、前記長期秘密鍵生成部がｔＡ［１］，…，ｔＡ［ＮＭＡＸ］とｔＢ［１］，…，ｔＢ［ＮＭＡＸ］をランダムに選定し、Ｓ’ＡとＳ’Ｂ、ＴＡ［ｊ］とＴＢ［ｊ］、ＳＡ［ｋＡ］とＳＢ［ｋＢ］を計算する。そして、鍵交換装置αは、鍵生成装置から長期秘密鍵としてＳ’Ａ，｛ＴＡ｝，｛ＳＡ｝を取得し、鍵交換装置βは、鍵生成装置から長期秘密鍵としてＳ’Ｂ，｛ＴＢ｝，｛ＳＢ｝を取得すればよい。
【発明の効果】
【００３１】
本発明の鍵交換システムによれば、線形秘密分散法を利用することにより、鍵抽出（長期秘密鍵の生成）を行うときには鍵生成装置が、鍵交換装置αの属性集合ＳＡに基づき線形秘密分散法のシェア情報として長期秘密鍵Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造ＡＡを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定することが可能となった。このことによって、課題１を解決できる。また、本発明のマスタ秘密鍵ｇ＾ｚとマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）は、属性集合とは独立なので、属性の全体集合をあらかじめ決めておく必要がない。つまり、鍵抽出時に任意の属性に基づき長期秘密鍵を発行することができるので、課題２を解決できる。
【図面の簡単な説明】
【００３２】
【図１】従来の鍵交換システムの構成例を示す図。
【図２】本発明の鍵交換システムの構成例を示す図。
【図３】本発明の鍵交換装置の機能構成例を示す図。
【図４】鍵生成装置の機能構成例を示す図。
【図５】マスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す図。
【図６】セッション鍵を共有する鍵交換の処理のフローの例を示す図。
【発明を実施するための形態】
【００３３】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００３４】
［準備］
本発明の鍵交換システムについて説明する前に、本発明を理解する上で必要な理論について説明する。本発明では、アクセスポリシーを次のようなアクセス構造として表すものとする。
【００３５】
まず、｛Ｐ１，Ｐ２，…，Ｐｎ，…，ＰＮ｝を属性集合とする。ただし、Ｎは整数、ｎは１以上Ｎ以下の整数である。Ｐｎは、例えば、「性別が男性である。」や「○○会社の社員である。」などの鍵生成装置の利用者（ユーザ）の属性を示している。なお、以下の説明では、「鍵生成装置の利用者の属性」を単に「鍵生成装置の属性」と表現する。アクセス構造は｛Ｐ１，Ｐ２，…，ＰＮ｝の空でない部分集合のべき集合Ａとして表わす。すなわち、
Ａ⊆２＾｛Ｐ１，Ｐ２，…，ＰＮ｝＼｛φ｝
ただし、“＾”はべき乗を示す記号、“φ”は空集合を示す記号、“＼｛φ｝”は空集合を除くことを示す記号
に属する集合を許可集合、属さない集合を不許可集合とよぶ。本発明では、上記のアクセス構造に基づきアクセスコントロールを行うために次のように線形秘密分散法を用いる。
【００３６】
各属性集合に対応するシェア情報は０以上ｐ−１以下の整数の集合ＺＰ上のベクトルとして表される。シェア情報を生成する行列としてＬ行Ｎ列のシェア情報生成行列Ｍを次のように用意する。ｉ＝１，…，Ｌについて、属性ラベリング関数ρを用いてシェア情報生成行列Ｍのｉ行目を属性ρ（ｉ）に対応させる。属性ラベリング関数ρは、ｉを特定すると属性ρ（ｉ）が決まる関数である。また、「属性ρ（ｉ）に対応させる」とは、例えば、属性ρ（１）がＰ１∧Ｐ２∧Ｐ３であれば、１，１，１，０，０，…，０のようにシェア情報生成行列Ｍの１行目を設定し、属性ρ（２）がＰ１∧ＰＮであれば、１，０，０，…，０，１のようにシェア情報生成行列Ｍの２行目を設定するように、属性ρ（ｉ）と対応させてｉ行目を決めることである。なお、上記の例では、アンド条件に含まれる属性Ｐｎに対応する要素を“１”とし、含まれない属性Ｐｎに対応する要素を“０”としたが、これに限る必要はない。異なる条件に対応する行が同じ行にならないように対応付けされていればよいので、属性ラベリング関数ρは単射性を有する範囲で他の対応でもよい。
【００３７】
次に、０以上ｐ−１以下の整数ｓを秘密情報とし、０以上ｐ−１以下の整数からｒ２，…，ｒＮをランダムに選び、列ベクトルｖ＝（ｓ，ｒ２，…，ｒＮ）Ｔを生成する。ただし、Ｔは転置を示す記号である。この時、Ｍｖは秘密情報ｓのＬ個のシェア情報のベクトルとなる。属性集合ρ（ｉ）にシェア情報（Ｍｖ）ｉを割り当てる。ただし、（Ｍｖ）ｉはベクトルＭｖのｉ番目の成分を示している。
【００３８】
このようにシェア情報生成行列Ｍと秘密情報ｓを含む列ベクトルｖを用いると、線形秘密分散法の線形復元性を利用できる。ここで、線形復元性について説明する。あるアクセス構造Ａを考え、集合ＳをＳ∈Ａの任意の許可集合とし、Ｉ⊂｛１，２，…，Ｌ｝をＩ＝｛ｉ：ρ（ｉ）∈Ｓ｝と定義する。このとき、｛λｉ｝がｓの正しいシェア情報の集合の場合、
【００３９】
【数８】
【００４０】
となるような０以上ｐ−１以下の整数の集合｛ｗｉ｝が存在する。このような集合｛ｗｉ｝はＭのサイズの多項式時間で見つけられることが知られている。一方、｛λｉ｝がｓの正しいシェア情報の集合でない場合、集合｛ｗｉ｝のすべての要素を求めることができない。本発明では、上述のようにシェア情報生成行列Ｍと秘密情報ｓを含む列ベクトルｖを用いることで、線形秘密分散法の線形復元性を利用してセッション鍵を交換する。
【００４１】
［構成］
図２に本発明の鍵交換システムの構成例を示す。本発明の鍵交換システムは、ネットワーク１０００を介して接続された鍵交換装置１００１，…，１００Ｑ（ただし、Ｑは２以上の整数、ｑは１以上Ｑ以下の整数、ＡとＢは１以上Ｑ以下の異なる整数）、鍵生成装置３００で構成される。図３に本発明の鍵交換装置の機能構成例、図４に鍵生成装置の機能構成例を示す。鍵交換装置１００ｑは、アクセス構造決定部１１０ｑ、短期秘密鍵生成部１２０ｑ、交換情報生成部１３０ｑ、送信部１４０ｑ、受信部１４５ｑ、属性確認部１５０ｑ、秘密情報取得部１６０ｑ、セッション鍵計算部１７０ｑ、中間情報消去部１８０ｑ、記録部１９０ｑを備える。また、鍵生成装置３００は、マスタ鍵生成部３１０、長期秘密鍵生成部３２０、記録部３９０を備える。以下の説明では、鍵交換装置１００Ａ（鍵交換装置αに相当）がイニシエータとして機能し、鍵交換装置１００Ｂ（鍵交換装置βに相当）がレスポンダとして機能してセッション鍵を共有する場合について説明する。
【００４２】
なお、κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置１００Ａの属性を示す属性要素Ｐｎの組み合わせの集合、属性集合ＳＢは鍵交換装置１００Ｂの属性を示す属性要素Ｐｎの組み合わせの集合、ＮＭＡＸはあらかじめ定めた整数、ｊとｎは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＴＢ｝はＴＢ［１］，…，ＴＢ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、｛ＳＢ｝はＳＢ［１］，…，ＳＢ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合である。
【００４３】
［鍵生成、鍵抽出］
図５に、マスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す。なお、長期秘密鍵生成の処理が従来技術の鍵抽出に相当する。鍵生成装置３００のマスタ鍵生成部３１０は、０以上ｐ−１以下の整数からランダムにｒとｚを選定する。そして、マスタ公開鍵を（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）、マスタ秘密鍵をｇ＾ｚとして記録部３９０に記録し、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）を公開する（Ｓ３１０）。鍵交換装置１００Ａと鍵交換装置１００Ｂは、それぞれマスタ公開鍵を（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）を受信し、記録部１９０Ａと記録部１９０Ｂに記録する。
【００４４】
長期秘密鍵生成部３２０は、０以上ｐ−１以下の整数からランダムにｔＡ［１］，…，ｔＡ［ＮＭＡＸ］を選び、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）を計算し、１以上ＮＭＡＸ以下のｊについてＴＡ［ｊ］＝ｇ＾ｔＡ［１］を計算し、属性集合ＳＡの要素ｋＡについて
【００４５】
【数９】
【００４６】
を計算し、長期秘密鍵として（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝）を鍵交換装置１００Ａに送信する（Ｓ３２０Ａ）。鍵交換装置１００Ａは、長期秘密鍵（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝）を受信し、記録部１９０Ａに記録する（Ｓ１９２Ａ）。
【００４７】
さらに、長期秘密鍵生成部３２０は、０以上ｐ−１以下の整数からランダムにｔＢ［１］，…，ｔＢ［ＮＭＡＸ］を選び、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ［１］）を計算し、１以上ＮＭＡＸ以下のｊについてＴＢ［ｊ］＝ｇ＾ｔＢ［１］を計算し、属性集合ＳＢの要素ｋＢについて
【００４８】
【数１０】
【００４９】
を計算し、長期秘密鍵として（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝）を鍵交換装置１００Ｂに送信する（Ｓ３２０Ｂ）。鍵交換装置１００Ｂは、長期秘密鍵（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝）を受信し、記録部１９０Ｂに記録する（Ｓ１９２Ｂ）。
【００５０】
なお、あらかじめ鍵交換装置１００Ａの記録部１９０Ａにマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）と長期秘密鍵（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝）とを記録させ、鍵交換装置１００Ｂの記録部１９０Ｂにマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）と長期秘密鍵（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝）とを記録させておけば、ネットワーク１０００を介して接続された鍵交換装置１００Ａと鍵交換装置１００Ｂだけで最低限の鍵交換システムが構成できる。
【００５１】
［鍵交換］
図６にセッション鍵を共有する鍵交換の処理のフローの例を示す。この例は、鍵交換装置１００Ａ（鍵交換装置αに相当）がイニシエータとして機能し、鍵交換装置１００Ｂ（鍵交換装置βに相当）がレスポンダとして機能する場合を示している。
【００５２】
鍵交換装置１００Ａは、アクセス構造決定部１１０Ａ（第１のアクセス構造決定部）、短期秘密鍵生成部１２０Ａ（第１の短期秘密鍵生成部）、交換情報生成部１３０Ａ（第１の交換情報生成部）、送信部１４０Ａ（第１の送信部）、受信部１４５Ａ（第１の受信部）、属性確認部１５０Ａ（第１の属性確認部）、秘密情報取得部１６０Ａ（第１の秘密情報取得部）、セッション鍵計算部１７０Ａ（第１のセッション鍵計算部）、中間情報消去部１８０Ａ（第１の中間情報消去部）を備える。鍵交換装置１００Ｂは、アクセス構造決定部１１０Ｂ（第２のアクセス構造決定部）、短期秘密鍵生成部１２０Ｂ（第２の短期秘密鍵生成部）、交換情報生成部１３０Ｂ（第２の交換情報生成部）、送信部１４０Ｂ（第２の送信部）、受信部１４５Ｂ（第２の受信部）、属性確認部１５０Ｂ（第２の属性確認部）、秘密情報取得部１６０Ｂ（第２の秘密情報取得部）、セッション鍵計算部１７０Ｂ（第２のセッション鍵計算部）、中間情報消去部１８０Ｂ（第２の中間情報消去部）を備える。
【００５３】
アクセス構造決定部１１０Ａは、アクセス構造ＡＡを決定し、当該アクセス構造ＡＡに対応するシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する（Ｓ１１０Ａ）。短期秘密鍵生成部１２０Ａは、１≦ｊ≦ＮＡについて、ｕ〜ｊを０以上ｐ−１以下の整数からランダムに選定する（Ｓ１２０Ａ）。交換情報生成部１３０Ａは、
１≦ｊ≦ＮＡについて、ｕｊ＝Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜ｊ）、
Ｘ＝ｇ＾ｕ１、
１≦ｉ≦ＬＡと１≦ｊ≦ＮＡについて、
Ｕｉ，ｊ＝ｇ＾（ｒ（ＭＡ）ｉ，ｊｕｊ）・Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）、
１≦ｉ≦ＬＡとＮＡ＋１≦ｊ≦ＮＭＡＸについて、
Ｕｉ，ｊ＝Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）
を計算する（１３０Ａ）。送信部１４０Ａは、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを鍵交換装置１００Ｂに送信する（Ｓ１４０Ａ）。中間情報消去部１８０Ａは、ｕｊ（１≦ｊ≦ＮＡ）を消去する（Ｓ１８０Ａ）。
【００５４】
受信部１４５Ｂは、鍵交換装置１００Ａから、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを受信する（Ｓ１４５Ｂ）。属性確認部１５０Ｂは、属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすか、Ｘと｛Ｕ｝が群Ｇの要素かを確認する（Ｓ１５０Ｂ）。
【００５５】
アクセス構造決定部１１０Ｂは、アクセス構造ＡＢを決定し、当該アクセス構造ＡＢに対応するシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する（Ｓ１１０Ｂ）。短期秘密鍵生成部１２０Ｂは、１≦ｊ≦ＮＢについて、ｖ〜ｊを０以上ｐ−１以下の整数からランダムに選定する（Ｓ１２０Ｂ）。交換情報生成部１３０Ｂは、
１≦ｊ≦ＮＢについて、ｖｊ＝Ｈ２（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝，ｖ〜ｊ）、
Ｙ＝ｇ＾ｖ１、
１≦ｉ≦ＬＢと１≦ｊ≦ＮＢについて、
Ｖｉ，ｊ＝ｇ＾（ｒ（ＭＢ）ｉ，ｊｖｊ）・Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）、
１≦ｉ≦ＬＢとＮＢ＋１≦ｊ≦ＮＭＡＸについて、
Ｖｉ，ｊ＝Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）
を計算する（Ｓ１３０Ｂ）。送信部１４０Ｂは、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを鍵交換装置１００Ａに送信する（Ｓ１４０Ｂ）。
【００５６】
秘密情報取得部１６０Ｂは、ＩＢ＝｛ｋ：ρＡ（ｋ）∈ＳＢ｝となる集合ＩＢを求め、鍵交換装置１００Ａが生成した秘密情報ｕ１に対する正当なシェア情報集合｛（ＭＡ）ｉ，ｊｕｊ｝について
【００５７】
【数１１】
【００５８】
が成り立つ０以上ｐ−１以下の整数ｗＢ［ｋ］（ただし、ｋは集合ＩＢの要素）を求める（Ｓ１６０Ｂ）。セッション鍵計算部１７０Ｂは、
【００５９】
【数１２】
σ２＝（ｇＴ＾ｚ）＾ｖ１
σ３＝Ｘ＾ｖ１
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める（Ｓ１７０Ｂ）。中間情報消去部１８０Ｂは、ｖｊ（１≦ｊ≦ＮＢ）を消去する（Ｓ１８０Ｂ）。
【００６０】
受信部１４５Ａは、鍵交換装置１００Ｂから、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを受信する（Ｓ１４５Ａ）。属性確認部１５０Ａは、属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすか、Ｙと｛Ｖ｝が群Ｇの要素かを確認する（Ｓ１５０Ａ）。秘密情報取得部１６０Ａは、ＩＡ＝｛ｋ：ρＢ（ｋ）∈ＳＡ｝となる集合ＩＡを求め、鍵交換装置１００Ｂが生成した秘密情報ｖ１に対する正当なシェア情報集合｛（ＭＢ）ｉ，ｊｖｊ｝について
【００６１】
【数１３】
【００６２】
が成り立つ０以上ｐ−１以下の整数ｗＡ［ｋ］（ただし、ｋは集合ＩＡの要素）を求める（Ｓ１６０Ａ）。セッション鍵計算部１７０Ａは、
【００６３】
【数１４】
σ１＝（ｇＴ＾ｚ）＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
σ３＝Ｙ＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める。
【００６４】
最後に鍵交換装置１００Ａと鍵交換装置１００Ｂが取得したセッション鍵Ｋが等しいことを説明する。
【００６５】
【数１５】
【００６６】
【数１６】
σ３＝Ｘ＾ｖ１＝Ｙ＾ｕ１＝ｇ＾ｕ１ｖ１
よって、正しくセッション鍵を共有できる。
【００６７】
本発明の鍵交換システムによれば、線形秘密分散法を利用することにより、鍵抽出（長期秘密鍵の生成）を行うときには鍵生成装置が、鍵交換装置αの属性集合ＳＡに基づき線形秘密分散法のシェア情報として長期秘密鍵Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造ＡＡを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定することが可能となる。このことによって、課題１を解決できる。また、本発明のマスタ秘密鍵ｇ＾ｚとマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）は、属性集合とは独立なので、属性の全体集合をあらかじめ決めておく必要がない。つまり、鍵抽出時に任意の属性に基づき長期秘密鍵を発行することができるので、課題２を解決できる。
【００６８】
さらに、従来技術と本発明との違いを属性集合とアクセスポリシーの観点から説明する。従来技術では、マスタ秘密鍵、マスタ公開鍵を生成する際には、属性の全体集合に対応したマスタ秘密鍵、マスタ公開鍵を生成する。長期秘密鍵を生成する際には、鍵交換装置（の使用者）がアクセスできるポリシーを決定する。そして、鍵交換のときに、属性集合を指定する。一方、本発明では、マスタ秘密鍵、マスタ公開鍵を生成する際には、属性集合とは独立にマスタ秘密鍵、マスタ公開鍵を生成する。長期秘密鍵を生成する際には、鍵交換装置（の使用者）が持っている属性に応じて、長期秘密鍵を生成する。そして、鍵交換のときに、アクセスポリシーを指定する。このように、本発明は、従来とは異なるアクセスコントロールの考え方を採用し、この考え方を実現できるセッション鍵を共有する技術を創作したものである。
【００６９】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７０】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７２】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００７５】
本発明は、二者間でセッション鍵を共有した暗号通信に利用することができる。
【符号の説明】
【００７６】
１００ｑ、７００ 鍵交換装置 １１０ｑ アクセス構造決定部
１２０ｑ 短期秘密鍵生成部 １３０ｑ 交換情報生成部
１４０ｑ 送信部 １４５ｑ 受信部
１５０ｑ 属性確認部 １６０ｑ 秘密情報取得部
１７０ｑ セッション鍵計算部 １８０ｑ 中間情報消去部
１９０ｑ、３９０ 記録部 ３００ 鍵生成装置
３１０ マスタ鍵生成部 ３２０ 長期秘密鍵生成部
８００ 鍵抽出手段 ９００ 鍵生成手段
１０００ ネットワーク
【技術分野】
【０００１】
本発明は情報セキュリティに関するものであり、特に、二者間でセッション鍵を共有するための鍵交換装置、鍵生成装置、鍵交換システム、鍵交換方法、プログラムに関する。
【背景技術】
【０００２】
非特許文献１の述語認証鍵交換方式が従来技術として知られている。図１は、非特許文献１の鍵交換システムの構成例を示す図である。このシステムは、ネットワーク１０００で接続された鍵生成手段９００、鍵抽出手段８００、鍵交換装置７００１，…，７００Ｑ（ただし、Ｑは２以上の整数、ＡとＢは１以上Ｑ以下の異なる整数）で構成されている。以下に、このシステムを用いた鍵交換について説明する。
【０００３】
［準備］
γを根付き木とし、Ｌ（γ）をγの全ての葉ノードの集合とする。葉ノードでないノードに対してｃｕを子ノードの数とし、葉ノードについてはｃｕ＝１として扱う。つまり、葉ノードを１つだけ持つノードと葉ノードのｃｕが１である。
【０００４】
それぞれのノードｕにはしきい値ｋｕ（１≦ｋｕ≦ｃｕ）が割り当てられる。ここで、葉ノードを１つだけ持つノードと葉ノードについてはｋｕ＝ｃｕ＝１となる。それぞれのノードｕに対して、
ｉｎｄｅｘ（ｕ）∈｛１，…，ｃｗ｝
を割り当てる。ただし、ノードｗはノードｕの親ノードとし、ノードｕはノードｗのｉｎｄｅｘ（ｕ）番目の子ノードとする。このとき、根付き木のそれぞれのノードｕにはｋｕ−ｏｕｔ−ｏｆ−ｃｕのしきい値ゲートが割り当てられる。
【０００５】
Ｕ＝｛１，２，…，ｎ｝
を属性の全体集合とする。それぞれの葉ノードに対して
ａｔｔ（ｕ）∈Ｕ
を割り当てる。すなわち、根付き木のそれぞれの葉ノードｕに１つの属性が割り当てられる。(ｋｕ，ｉｎｄｅｘ（ｕ），ａｔｔ（ｕ）) を持つ根付き木γをアクセス木と呼ぶ。
【０００６】
属性集合δ⊂Ｕがアクセス木γを満たすことを次のように定義する。葉ノードｕについて、
ａｔｔ（ｕ）⊂δ
が成り立つとき、ｕは満たされたという。葉ノードでないノードｕについて、ｕの満たされた子ノードの数がｋｕ以上であるとき、ｕは満たされたという。根ノードｕｒが満たされたとき、属性集合δ⊂Ｕがアクセス木γを満たすという。
【０００７】
［公開パラメータ］
ｐｉｄはプロトコルＩＤであって、プロトコル仕様に対応した固有の識別子とする。セキュリティパラメータをκとする。ｐをκビット素数とし、ＧとＧＴをそれぞれ双線形ペアリング関数ｅ：Ｇ×Ｇ→ＧＴを効率的に計算可能なｇとｇＴを生成元とする群とする。Ｈは任意長の整数をκビットの整数に変換するハッシュ関数、Ｈ’は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数とする。０以上ｐ−１以下の整数ｉと０以上ｐ−１以下の整数のある要素Ｓについて、Δｉ，Ｓ（ｘ）を
【０００８】
【数１】
【０００９】
となるようなラグランジュ係数とする。
［鍵生成］
鍵生成手段９００は、マスタ秘密鍵ｚを０以上ｐ−１以下の整数からランダムに選定する。また、すべての属性ｉ（ただし、ｉ∈Ｕ）について、ｔｉを０以上ｐ−１以下の整数からランダムに選定する。さらに、鍵生成手段９００は、群ＧＴの元であるマスタ公開鍵Ｚ＝ｇＴ＾ｚと｛Ｔｉ＝ｇ＾ｔｉ｝（ただし、ｉ∈Ｕ）を公開する。ここで、＾はべき乗を示している。
【００１０】
［鍵抽出］
鍵抽出手段８００は、鍵交換装置７００Ａのアクセス木γＡが入力されると、長期秘密鍵｛Ｄｕ｝（ただし、ｕ∈Ｌ（γＡ））をγＡのそれぞれのノードについて多項式ｑｕを選ぶことによって次のように計算する。
【００１１】
まず、鍵抽出手段８００は、多項式ｑｕの次数をｄｕ＝ｋｕ−１に設定する。根ノードｕｒについて、ｑｕ＿ｒ（０）＝ｚとしｑｕ＿ｒのその他のｄｕ＿ｒ点を０以上ｐ−１以下の整数からランダムに選ぶ。よって、ｑｕ＿ｒが一意に定まるため、残りｃｕ＿ｒ−ｄｕ＿ｒ点も一意に決まる。なお、ｑｕ＿ｒ、ｃｕ＿ｒ、ｄｕ＿ｒの下付きの添え字である“ｕ＿ｒ”は、“ｕｒ”を意味している。その他のノードｕについて、ｑｕ（０）＝ｑｕ’（ｉｎｄｅｘ（ｕ））とする。ただし、ｕ’はｕの親ノードである。ｑｕのその他のｄｕ点を０以上ｐ−１以下の整数からランダムに選ぶ。このように全てのノードの多項式を再帰的に決定していく。次に、それぞれの葉ノードｕの秘密の値を
【００１２】
【数２】
【００１３】
として計算する。ただし、ｉ＝ａｔｔ（ｕ）である。最後に、鍵抽出手段８００は、ｕ∈Ｌ（γＡ）であるすべてのｕについての秘密の値Ｄｕの集合（以下では、｛Ｄｕ｝（ｕ∈Ｌ（γＡ）と表記する）を長期秘密鍵として出力する。
鍵交換装置７００Ｂのアクセス木γＢに対する長期秘密鍵｛Ｄｕ｝（ｕ∈Ｌ（γＢ））も同様の手続きによって計算する。
【００１４】
［鍵交換］
以下では、鍵交換装置７００Ａを鍵交換処理でのイニシエータ、鍵交換装置７００Ｂをレスポンダとする。鍵交換装置７００Ａはアクセス木γＡに対応する長期秘密鍵｛Ｄｕ｝（ｕ∈Ｌ（γＡ））を持ち、鍵交換装置７００Ｂはアクセス木γＢに対応する長期秘密鍵｛Ｄｕ｝（ｕ∈Ｌ（γＢ））を持つ。このとき、鍵交換装置７００Ａは属性集合δＡに対応する短期公開鍵（Ｘ，｛Ｔｉｘ｝）（ただし、ｉ∈δＡ）を鍵交換装置７００Ｂに送り、鍵交換装置７００Ｂは属性集合δＢに対応する短期公開鍵（Ｙ，｛Ｔｉｙ｝）（ただし、ｉ∈δＢ）を鍵交換装置７００Ａに送る。最後に、鍵交換装置７００Ａと鍵交換装置７００Ｂは、属性集合δＢがアクセス木γＡを満たし、属性集合δＡがアクセス木γＢを満たしたとき、またはその限りにおいて、セッション鍵Ｋを共有できる。なお、属性集合δＢがアクセス木γＡを満たし、属性集合δＡがアクセス木γＢを満たすとは、
述語Ｐ:｛０，１｝Ｌ×｛０，１｝Ｌ→｛０，１｝
を用いて、それぞれＰ（γＡ，δＢ）＝１，Ｐ（γＢ，δＡ）＝１と表現する。なお、ＬはＬ（γ）に属する全葉ノードの数である。本発明の場合、Ｐは「属性集合がアクセス木を満たす」という命題を表す。
【００１５】
つまり、鍵交換装置７００Ａは、属性集合δＡが鍵交換装置７００Ｂのアクセス木γＢを満たすならば認証成功となることを期待して属性集合δＡを設定する。また、鍵交換装置７００Ｂは、属性集合δＢが鍵交換装置７００Ａのアクセス木γＡを満たすならば認証成功となることを期待して属性集合δＢを設定する。なお、鍵交換の具体的な処理については、非特許文献１を参照されたい。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】A.Fujioka, K.Suzuki, K.Yoneyama,”Predicate-based Authenticated Key Exchange Resilient to Ephemeral Key Leakage”, In: WISA 2010.
【発明の概要】
【発明が解決しようとする課題】
【００１７】
しかしながら、従来技術は以下のような２つの課題がある。
（課題１）アクセスポリシーを鍵交換時に指定できない。
（課題２）マスタ秘密鍵とマスタ公開鍵が属性の全体集合にパラメータライズされるため、鍵生成時に属性の全体集合をあらかじめ決めておかなければならない。したがって、あらかじめ決めた属性以外の任意の属性を扱うことができない。
【００１８】
本発明はこのような課題に鑑みてなされたものであり、鍵交換時にアクセスポリシーを指定でき、マスタ秘密鍵とマスタ公開鍵を生成した後にも任意の属性を扱うことができる鍵交換システムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
本発明の鍵交換システムは、少なくとも鍵交換装置αと鍵交換装置βとを備え、セッション鍵を交換する。ここで、κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置αの属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＡは鍵交換装置αが鍵交換装置βに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉ，ｊはシェア情報生成行列ＭＡのｉ行ｊ列の要素、属性集合ＳＢは鍵交換装置βの属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＢは鍵交換装置βが鍵交換装置αに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉ，ｊはシェア情報生成行列ＭＢのｉ行ｊ列の要素、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ＮＭＡＸはＮＡとＮＢが取りうる最大の整数、ｎとｊは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡ［１］，…，ｔＡ［ＮＭＡＸ］は０以上ｐ−１以下の整数、ｔＢ［１］，…，ｔＢ［ＮＭＡＸ］は０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ［１］）、ＴＡ［ｊ］＝ｇ＾ｔＡ［１］、ＴＢ［ｊ］＝ｇ＾ｔＢ［１］、
【００２０】
【数３】
、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＴＢ｝はＴＢ［１］，…，ＴＢ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、｛ＳＢ｝はＳＢ［１］，…，ＳＢ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合、＾はべき乗を示す記号とする。
【００２１】
鍵交換装置αは、第１のアクセス構造決定部、第１の短期秘密鍵生成部、第１の交換情報生成部、第１の送信部、第１の受信部、第１の属性確認部、第１の秘密情報取得部、第１のセッション鍵計算部、第１の中間情報消去部を備える。鍵交換装置βは、第２のアクセス構造決定部、第２の短期秘密鍵生成部、第２の交換情報生成部、第２の送信部、第２の受信部、第２の属性確認部、第２の秘密情報取得部、第２のセッション鍵計算部、第２の中間情報消去部を備える。
【００２２】
第１のアクセス構造決定部は、アクセス構造ＡＡを決定し、当該アクセス構造ＡＡに対応するシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する。第１の短期秘密鍵生成部は、１≦ｊ≦ＮＡについて、ｕ〜ｊを０以上ｐ−１以下の整数からランダムに選定する。第１の交換情報生成部は、
１≦ｊ≦ＮＡについて、ｕｊ＝Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜ｊ）、
Ｘ＝ｇ＾ｕ１、
１≦ｉ≦ＬＡと１≦ｊ≦ＮＡについて、
Ｕｉ，ｊ＝ｇ＾（ｒ（ＭＡ）ｉ，ｊｕｊ）・Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）、
１≦ｉ≦ＬＡとＮＡ＋１≦ｊ≦ＮＭＡＸについて、
Ｕｉ，ｊ＝Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）
を計算する。第１の送信部は、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを鍵交換装置βに送信する。第１の受信部は、鍵交換装置βから、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを受信する。第１の属性確認部は、属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすか、Ｙと｛Ｖ｝が群Ｇの要素かを確認する。第１の秘密情報取得部は、ＩＡ＝｛ｋ：ρＢ（ｋ）∈ＳＡ｝となる集合ＩＡを求め、鍵交換装置βが生成した秘密情報ｖ１に対する正当なシェア情報集合｛（ＭＢ）ｉ，ｊｖｊ｝について
【００２３】
【数４】
が成り立つ０以上ｐ−１以下の整数ｗＡ［ｋ］（ただし、ｋは集合ＩＡの要素）を求める。第１のセッション鍵計算部は、
【００２４】
【数５】
σ１＝（ｇＴ＾ｚ）＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
σ３＝Ｙ＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める。第１の中間情報消去部は、ｕｊ（１≦ｊ≦ＮＡ）を消去する。
【００２５】
第２のアクセス構造決定部は、アクセス構造ＡＢを決定し、当該アクセス構造ＡＢに対応するシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する。第２の短期秘密鍵生成部は、１≦ｊ≦ＮＢについて、ｖ〜ｊを０以上ｐ−１以下の整数からランダムに選定する。
【００２６】
第２の交換情報生成部は、
１≦ｊ≦ＮＢについて、ｖｊ＝Ｈ２（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝，ｖ〜ｊ）と、
Ｙ＝ｇ＾ｖ１と、
１≦ｉ≦ＬＢと１≦ｊ≦ＮＢについて、
Ｖｉ，ｊ＝ｇ＾（ｒ（ＭＢ）ｉ，ｊｖｊ）・Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と、
１≦ｉ≦ＬＢとＮＢ＋１≦ｊ≦ＮＭＡＸについて、
Ｖｉ，ｊ＝Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と
を計算する。第２の送信部は、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを鍵交換装置αに送信する。第２の受信部は、鍵交換装置αから、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを受信する。第２の属性確認部は、属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすか、Ｘと｛Ｕ｝が群Ｇの要素かを確認する。第２の秘密情報取得部は、ＩＢ＝｛ｋ：ρＡ（ｋ）∈ＳＢ｝となる集合ＩＢを求め、鍵交換装置αが生成した秘密情報ｕ１に対する正当なシェア情報集合｛（ＭＡ）ｉ，ｊｕｊ｝について
【００２７】
【数６】
【００２８】
が成り立つ０以上ｐ−１以下の整数ｗＢ［ｋ］（ただし、ｋは集合ＩＢの要素）を求める。第２のセッション鍵計算部は、
【００２９】
【数７】
σ２＝（ｇＴ＾ｚ）＾ｖ１
σ３＝Ｘ＾ｖ１
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める。第２の中間情報消去部は、ｖｊ（１≦ｊ≦ＮＢ）を消去する。
【００３０】
なお、本発明の鍵交換システムは、さらに、マスタ鍵生成部と長期秘密鍵生成部とを有する鍵生成装置を備えてもよい。マスタ鍵生成部がランダムにｒとｚを選定し、前記マスタ鍵生成部がマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）とマスタ秘密鍵ｇ＾ｚを生成すればよい。また、前記長期秘密鍵生成部がｔＡ［１］，…，ｔＡ［ＮＭＡＸ］とｔＢ［１］，…，ｔＢ［ＮＭＡＸ］をランダムに選定し、Ｓ’ＡとＳ’Ｂ、ＴＡ［ｊ］とＴＢ［ｊ］、ＳＡ［ｋＡ］とＳＢ［ｋＢ］を計算する。そして、鍵交換装置αは、鍵生成装置から長期秘密鍵としてＳ’Ａ，｛ＴＡ｝，｛ＳＡ｝を取得し、鍵交換装置βは、鍵生成装置から長期秘密鍵としてＳ’Ｂ，｛ＴＢ｝，｛ＳＢ｝を取得すればよい。
【発明の効果】
【００３１】
本発明の鍵交換システムによれば、線形秘密分散法を利用することにより、鍵抽出（長期秘密鍵の生成）を行うときには鍵生成装置が、鍵交換装置αの属性集合ＳＡに基づき線形秘密分散法のシェア情報として長期秘密鍵Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造ＡＡを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定することが可能となった。このことによって、課題１を解決できる。また、本発明のマスタ秘密鍵ｇ＾ｚとマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）は、属性集合とは独立なので、属性の全体集合をあらかじめ決めておく必要がない。つまり、鍵抽出時に任意の属性に基づき長期秘密鍵を発行することができるので、課題２を解決できる。
【図面の簡単な説明】
【００３２】
【図１】従来の鍵交換システムの構成例を示す図。
【図２】本発明の鍵交換システムの構成例を示す図。
【図３】本発明の鍵交換装置の機能構成例を示す図。
【図４】鍵生成装置の機能構成例を示す図。
【図５】マスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す図。
【図６】セッション鍵を共有する鍵交換の処理のフローの例を示す図。
【発明を実施するための形態】
【００３３】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００３４】
［準備］
本発明の鍵交換システムについて説明する前に、本発明を理解する上で必要な理論について説明する。本発明では、アクセスポリシーを次のようなアクセス構造として表すものとする。
【００３５】
まず、｛Ｐ１，Ｐ２，…，Ｐｎ，…，ＰＮ｝を属性集合とする。ただし、Ｎは整数、ｎは１以上Ｎ以下の整数である。Ｐｎは、例えば、「性別が男性である。」や「○○会社の社員である。」などの鍵生成装置の利用者（ユーザ）の属性を示している。なお、以下の説明では、「鍵生成装置の利用者の属性」を単に「鍵生成装置の属性」と表現する。アクセス構造は｛Ｐ１，Ｐ２，…，ＰＮ｝の空でない部分集合のべき集合Ａとして表わす。すなわち、
Ａ⊆２＾｛Ｐ１，Ｐ２，…，ＰＮ｝＼｛φ｝
ただし、“＾”はべき乗を示す記号、“φ”は空集合を示す記号、“＼｛φ｝”は空集合を除くことを示す記号
に属する集合を許可集合、属さない集合を不許可集合とよぶ。本発明では、上記のアクセス構造に基づきアクセスコントロールを行うために次のように線形秘密分散法を用いる。
【００３６】
各属性集合に対応するシェア情報は０以上ｐ−１以下の整数の集合ＺＰ上のベクトルとして表される。シェア情報を生成する行列としてＬ行Ｎ列のシェア情報生成行列Ｍを次のように用意する。ｉ＝１，…，Ｌについて、属性ラベリング関数ρを用いてシェア情報生成行列Ｍのｉ行目を属性ρ（ｉ）に対応させる。属性ラベリング関数ρは、ｉを特定すると属性ρ（ｉ）が決まる関数である。また、「属性ρ（ｉ）に対応させる」とは、例えば、属性ρ（１）がＰ１∧Ｐ２∧Ｐ３であれば、１，１，１，０，０，…，０のようにシェア情報生成行列Ｍの１行目を設定し、属性ρ（２）がＰ１∧ＰＮであれば、１，０，０，…，０，１のようにシェア情報生成行列Ｍの２行目を設定するように、属性ρ（ｉ）と対応させてｉ行目を決めることである。なお、上記の例では、アンド条件に含まれる属性Ｐｎに対応する要素を“１”とし、含まれない属性Ｐｎに対応する要素を“０”としたが、これに限る必要はない。異なる条件に対応する行が同じ行にならないように対応付けされていればよいので、属性ラベリング関数ρは単射性を有する範囲で他の対応でもよい。
【００３７】
次に、０以上ｐ−１以下の整数ｓを秘密情報とし、０以上ｐ−１以下の整数からｒ２，…，ｒＮをランダムに選び、列ベクトルｖ＝（ｓ，ｒ２，…，ｒＮ）Ｔを生成する。ただし、Ｔは転置を示す記号である。この時、Ｍｖは秘密情報ｓのＬ個のシェア情報のベクトルとなる。属性集合ρ（ｉ）にシェア情報（Ｍｖ）ｉを割り当てる。ただし、（Ｍｖ）ｉはベクトルＭｖのｉ番目の成分を示している。
【００３８】
このようにシェア情報生成行列Ｍと秘密情報ｓを含む列ベクトルｖを用いると、線形秘密分散法の線形復元性を利用できる。ここで、線形復元性について説明する。あるアクセス構造Ａを考え、集合ＳをＳ∈Ａの任意の許可集合とし、Ｉ⊂｛１，２，…，Ｌ｝をＩ＝｛ｉ：ρ（ｉ）∈Ｓ｝と定義する。このとき、｛λｉ｝がｓの正しいシェア情報の集合の場合、
【００３９】
【数８】
【００４０】
となるような０以上ｐ−１以下の整数の集合｛ｗｉ｝が存在する。このような集合｛ｗｉ｝はＭのサイズの多項式時間で見つけられることが知られている。一方、｛λｉ｝がｓの正しいシェア情報の集合でない場合、集合｛ｗｉ｝のすべての要素を求めることができない。本発明では、上述のようにシェア情報生成行列Ｍと秘密情報ｓを含む列ベクトルｖを用いることで、線形秘密分散法の線形復元性を利用してセッション鍵を交換する。
【００４１】
［構成］
図２に本発明の鍵交換システムの構成例を示す。本発明の鍵交換システムは、ネットワーク１０００を介して接続された鍵交換装置１００１，…，１００Ｑ（ただし、Ｑは２以上の整数、ｑは１以上Ｑ以下の整数、ＡとＢは１以上Ｑ以下の異なる整数）、鍵生成装置３００で構成される。図３に本発明の鍵交換装置の機能構成例、図４に鍵生成装置の機能構成例を示す。鍵交換装置１００ｑは、アクセス構造決定部１１０ｑ、短期秘密鍵生成部１２０ｑ、交換情報生成部１３０ｑ、送信部１４０ｑ、受信部１４５ｑ、属性確認部１５０ｑ、秘密情報取得部１６０ｑ、セッション鍵計算部１７０ｑ、中間情報消去部１８０ｑ、記録部１９０ｑを備える。また、鍵生成装置３００は、マスタ鍵生成部３１０、長期秘密鍵生成部３２０、記録部３９０を備える。以下の説明では、鍵交換装置１００Ａ（鍵交換装置αに相当）がイニシエータとして機能し、鍵交換装置１００Ｂ（鍵交換装置βに相当）がレスポンダとして機能してセッション鍵を共有する場合について説明する。
【００４２】
なお、κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置１００Ａの属性を示す属性要素Ｐｎの組み合わせの集合、属性集合ＳＢは鍵交換装置１００Ｂの属性を示す属性要素Ｐｎの組み合わせの集合、ＮＭＡＸはあらかじめ定めた整数、ｊとｎは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＴＢ｝はＴＢ［１］，…，ＴＢ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、｛ＳＢ｝はＳＢ［１］，…，ＳＢ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合である。
【００４３】
［鍵生成、鍵抽出］
図５に、マスタ秘密鍵とマスタ公開鍵と長期秘密鍵の生成の処理フローの例を示す。なお、長期秘密鍵生成の処理が従来技術の鍵抽出に相当する。鍵生成装置３００のマスタ鍵生成部３１０は、０以上ｐ−１以下の整数からランダムにｒとｚを選定する。そして、マスタ公開鍵を（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）、マスタ秘密鍵をｇ＾ｚとして記録部３９０に記録し、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）を公開する（Ｓ３１０）。鍵交換装置１００Ａと鍵交換装置１００Ｂは、それぞれマスタ公開鍵を（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）を受信し、記録部１９０Ａと記録部１９０Ｂに記録する。
【００４４】
長期秘密鍵生成部３２０は、０以上ｐ−１以下の整数からランダムにｔＡ［１］，…，ｔＡ［ＮＭＡＸ］を選び、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）を計算し、１以上ＮＭＡＸ以下のｊについてＴＡ［ｊ］＝ｇ＾ｔＡ［１］を計算し、属性集合ＳＡの要素ｋＡについて
【００４５】
【数９】
【００４６】
を計算し、長期秘密鍵として（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝）を鍵交換装置１００Ａに送信する（Ｓ３２０Ａ）。鍵交換装置１００Ａは、長期秘密鍵（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝）を受信し、記録部１９０Ａに記録する（Ｓ１９２Ａ）。
【００４７】
さらに、長期秘密鍵生成部３２０は、０以上ｐ−１以下の整数からランダムにｔＢ［１］，…，ｔＢ［ＮＭＡＸ］を選び、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ［１］）を計算し、１以上ＮＭＡＸ以下のｊについてＴＢ［ｊ］＝ｇ＾ｔＢ［１］を計算し、属性集合ＳＢの要素ｋＢについて
【００４８】
【数１０】
【００４９】
を計算し、長期秘密鍵として（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝）を鍵交換装置１００Ｂに送信する（Ｓ３２０Ｂ）。鍵交換装置１００Ｂは、長期秘密鍵（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝）を受信し、記録部１９０Ｂに記録する（Ｓ１９２Ｂ）。
【００５０】
なお、あらかじめ鍵交換装置１００Ａの記録部１９０Ａにマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）と長期秘密鍵（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝）とを記録させ、鍵交換装置１００Ｂの記録部１９０Ｂにマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）と長期秘密鍵（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝）とを記録させておけば、ネットワーク１０００を介して接続された鍵交換装置１００Ａと鍵交換装置１００Ｂだけで最低限の鍵交換システムが構成できる。
【００５１】
［鍵交換］
図６にセッション鍵を共有する鍵交換の処理のフローの例を示す。この例は、鍵交換装置１００Ａ（鍵交換装置αに相当）がイニシエータとして機能し、鍵交換装置１００Ｂ（鍵交換装置βに相当）がレスポンダとして機能する場合を示している。
【００５２】
鍵交換装置１００Ａは、アクセス構造決定部１１０Ａ（第１のアクセス構造決定部）、短期秘密鍵生成部１２０Ａ（第１の短期秘密鍵生成部）、交換情報生成部１３０Ａ（第１の交換情報生成部）、送信部１４０Ａ（第１の送信部）、受信部１４５Ａ（第１の受信部）、属性確認部１５０Ａ（第１の属性確認部）、秘密情報取得部１６０Ａ（第１の秘密情報取得部）、セッション鍵計算部１７０Ａ（第１のセッション鍵計算部）、中間情報消去部１８０Ａ（第１の中間情報消去部）を備える。鍵交換装置１００Ｂは、アクセス構造決定部１１０Ｂ（第２のアクセス構造決定部）、短期秘密鍵生成部１２０Ｂ（第２の短期秘密鍵生成部）、交換情報生成部１３０Ｂ（第２の交換情報生成部）、送信部１４０Ｂ（第２の送信部）、受信部１４５Ｂ（第２の受信部）、属性確認部１５０Ｂ（第２の属性確認部）、秘密情報取得部１６０Ｂ（第２の秘密情報取得部）、セッション鍵計算部１７０Ｂ（第２のセッション鍵計算部）、中間情報消去部１８０Ｂ（第２の中間情報消去部）を備える。
【００５３】
アクセス構造決定部１１０Ａは、アクセス構造ＡＡを決定し、当該アクセス構造ＡＡに対応するシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する（Ｓ１１０Ａ）。短期秘密鍵生成部１２０Ａは、１≦ｊ≦ＮＡについて、ｕ〜ｊを０以上ｐ−１以下の整数からランダムに選定する（Ｓ１２０Ａ）。交換情報生成部１３０Ａは、
１≦ｊ≦ＮＡについて、ｕｊ＝Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜ｊ）、
Ｘ＝ｇ＾ｕ１、
１≦ｉ≦ＬＡと１≦ｊ≦ＮＡについて、
Ｕｉ，ｊ＝ｇ＾（ｒ（ＭＡ）ｉ，ｊｕｊ）・Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）、
１≦ｉ≦ＬＡとＮＡ＋１≦ｊ≦ＮＭＡＸについて、
Ｕｉ，ｊ＝Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）
を計算する（１３０Ａ）。送信部１４０Ａは、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを鍵交換装置１００Ｂに送信する（Ｓ１４０Ａ）。中間情報消去部１８０Ａは、ｕｊ（１≦ｊ≦ＮＡ）を消去する（Ｓ１８０Ａ）。
【００５４】
受信部１４５Ｂは、鍵交換装置１００Ａから、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを受信する（Ｓ１４５Ｂ）。属性確認部１５０Ｂは、属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすか、Ｘと｛Ｕ｝が群Ｇの要素かを確認する（Ｓ１５０Ｂ）。
【００５５】
アクセス構造決定部１１０Ｂは、アクセス構造ＡＢを決定し、当該アクセス構造ＡＢに対応するシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する（Ｓ１１０Ｂ）。短期秘密鍵生成部１２０Ｂは、１≦ｊ≦ＮＢについて、ｖ〜ｊを０以上ｐ−１以下の整数からランダムに選定する（Ｓ１２０Ｂ）。交換情報生成部１３０Ｂは、
１≦ｊ≦ＮＢについて、ｖｊ＝Ｈ２（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝，ｖ〜ｊ）、
Ｙ＝ｇ＾ｖ１、
１≦ｉ≦ＬＢと１≦ｊ≦ＮＢについて、
Ｖｉ，ｊ＝ｇ＾（ｒ（ＭＢ）ｉ，ｊｖｊ）・Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）、
１≦ｉ≦ＬＢとＮＢ＋１≦ｊ≦ＮＭＡＸについて、
Ｖｉ，ｊ＝Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）
を計算する（Ｓ１３０Ｂ）。送信部１４０Ｂは、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを鍵交換装置１００Ａに送信する（Ｓ１４０Ｂ）。
【００５６】
秘密情報取得部１６０Ｂは、ＩＢ＝｛ｋ：ρＡ（ｋ）∈ＳＢ｝となる集合ＩＢを求め、鍵交換装置１００Ａが生成した秘密情報ｕ１に対する正当なシェア情報集合｛（ＭＡ）ｉ，ｊｕｊ｝について
【００５７】
【数１１】
【００５８】
が成り立つ０以上ｐ−１以下の整数ｗＢ［ｋ］（ただし、ｋは集合ＩＢの要素）を求める（Ｓ１６０Ｂ）。セッション鍵計算部１７０Ｂは、
【００５９】
【数１２】
σ２＝（ｇＴ＾ｚ）＾ｖ１
σ３＝Ｘ＾ｖ１
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める（Ｓ１７０Ｂ）。中間情報消去部１８０Ｂは、ｖｊ（１≦ｊ≦ＮＢ）を消去する（Ｓ１８０Ｂ）。
【００６０】
受信部１４５Ａは、鍵交換装置１００Ｂから、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを受信する（Ｓ１４５Ａ）。属性確認部１５０Ａは、属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすか、Ｙと｛Ｖ｝が群Ｇの要素かを確認する（Ｓ１５０Ａ）。秘密情報取得部１６０Ａは、ＩＡ＝｛ｋ：ρＢ（ｋ）∈ＳＡ｝となる集合ＩＡを求め、鍵交換装置１００Ｂが生成した秘密情報ｖ１に対する正当なシェア情報集合｛（ＭＢ）ｉ，ｊｖｊ｝について
【００６１】
【数１３】
【００６２】
が成り立つ０以上ｐ−１以下の整数ｗＡ［ｋ］（ただし、ｋは集合ＩＡの要素）を求める（Ｓ１６０Ａ）。セッション鍵計算部１７０Ａは、
【００６３】
【数１４】
σ１＝（ｇＴ＾ｚ）＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
σ３＝Ｙ＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める。
【００６４】
最後に鍵交換装置１００Ａと鍵交換装置１００Ｂが取得したセッション鍵Ｋが等しいことを説明する。
【００６５】
【数１５】
【００６６】
【数１６】
σ３＝Ｘ＾ｖ１＝Ｙ＾ｕ１＝ｇ＾ｕ１ｖ１
よって、正しくセッション鍵を共有できる。
【００６７】
本発明の鍵交換システムによれば、線形秘密分散法を利用することにより、鍵抽出（長期秘密鍵の生成）を行うときには鍵生成装置が、鍵交換装置αの属性集合ＳＡに基づき線形秘密分散法のシェア情報として長期秘密鍵Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝を発行する。また、鍵交換時にアクセスポリシーとして線形秘密分散のアクセス構造ＡＡを割り当てることによって、相手のアクセスポリシーを鍵交換時に指定することが可能となる。このことによって、課題１を解決できる。また、本発明のマスタ秘密鍵ｇ＾ｚとマスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）は、属性集合とは独立なので、属性の全体集合をあらかじめ決めておく必要がない。つまり、鍵抽出時に任意の属性に基づき長期秘密鍵を発行することができるので、課題２を解決できる。
【００６８】
さらに、従来技術と本発明との違いを属性集合とアクセスポリシーの観点から説明する。従来技術では、マスタ秘密鍵、マスタ公開鍵を生成する際には、属性の全体集合に対応したマスタ秘密鍵、マスタ公開鍵を生成する。長期秘密鍵を生成する際には、鍵交換装置（の使用者）がアクセスできるポリシーを決定する。そして、鍵交換のときに、属性集合を指定する。一方、本発明では、マスタ秘密鍵、マスタ公開鍵を生成する際には、属性集合とは独立にマスタ秘密鍵、マスタ公開鍵を生成する。長期秘密鍵を生成する際には、鍵交換装置（の使用者）が持っている属性に応じて、長期秘密鍵を生成する。そして、鍵交換のときに、アクセスポリシーを指定する。このように、本発明は、従来とは異なるアクセスコントロールの考え方を採用し、この考え方を実現できるセッション鍵を共有する技術を創作したものである。
【００６９】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７０】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７２】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００７５】
本発明は、二者間でセッション鍵を共有した暗号通信に利用することができる。
【符号の説明】
【００７６】
１００ｑ、７００ 鍵交換装置 １１０ｑ アクセス構造決定部
１２０ｑ 短期秘密鍵生成部 １３０ｑ 交換情報生成部
１４０ｑ 送信部 １４５ｑ 受信部
１５０ｑ 属性確認部 １６０ｑ 秘密情報取得部
１７０ｑ セッション鍵計算部 １８０ｑ 中間情報消去部
１９０ｑ、３９０ 記録部 ３００ 鍵生成装置
３１０ マスタ鍵生成部 ３２０ 長期秘密鍵生成部
８００ 鍵抽出手段 ９００ 鍵生成手段
１０００ ネットワーク
【特許請求の範囲】
【請求項１】
セッション鍵を交換する鍵交換装置であって、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは当該鍵交換装置の属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＡは当該鍵交換装置が鍵交換の対象となる装置に求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉ，ｊはシェア情報生成行列ＭＡのｉ行ｊ列の要素、アクセス構造ＡＢは鍵交換の対象となる装置が当該鍵交換装置に求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉ，ｊはシェア情報生成行列ＭＢのｉ行ｊ列の要素、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ＮＭＡＸはＮＡとＮＢが取りうる最大の整数、ｎとｊは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、ｒとｚは０以上ｐ−１以下の整数、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡ［１］，…，ｔＡ［ＮＭＡＸ］は０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）、ＴＡ［ｊ］＝ｇ＾ｔＡ［１］、
【数１７】
、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合、＾はべき乗を示す記号であり、
アクセス構造ＡＡを決定し、当該アクセス構造ＡＡに対応するシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成するアクセス構造決定部と、
１≦ｊ≦ＮＡについて、ｕ〜ｊを０以上ｐ−１以下の整数からランダムに選定する短期秘密鍵生成部と、
１≦ｊ≦ＮＡについて、ｕｊ＝Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜ｊ）と、
Ｘ＝ｇ＾ｕ１と、
１≦ｉ≦ＬＡと１≦ｊ≦ＮＡについて、
Ｕｉ，ｊ＝ｇ＾（ｒ（ＭＡ）ｉ，ｊｕｊ）・Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）と、
１≦ｉ≦ＬＡとＮＡ＋１≦ｊ≦ＮＭＡＸについて、
Ｕｉ，ｊ＝Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）と
を計算する交換情報生成部と、
（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを鍵交換する対象の装置に送信する送信部と、
鍵交換する対象の装置から、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを受信する受信部と、
属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすか、Ｙと｛Ｖ｝が群Ｇの要素かを確認する属性確認部と、
ＩＡ＝｛ｋ：ρＢ（ｋ）∈ＳＡ｝となる集合ＩＡを求め、鍵交換する対象の装置が生成した秘密情報ｖ１に対する正当なシェア情報集合｛（ＭＢ）ｉ，ｊｖｊ｝について
【数１８】
が成り立つ０以上ｐ−１以下の整数ｗＡ［ｋ］（ただし、ｋは集合ＩＡの要素）を求める秘密情報取得部と、
【数１９】
σ１＝（ｇＴ＾ｚ）＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
σ３＝Ｙ＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求めるセッション鍵計算部と、
ｕｊ（１≦ｊ≦ＮＡ）を消去する中間情報消去部と、
を備える鍵交換装置。
【請求項２】
セッション鍵を交換する鍵交換装置であって、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＢは当該鍵交換装置の属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＢは当該鍵交換装置が鍵交換の対象となる装置に求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉ，ｊはシェア情報生成行列ＭＢのｉ行ｊ列の要素、アクセス構造ＡＡは鍵交換の対象となる装置が当該鍵交換装置に求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉ，ｊはシェア情報生成行列ＭＡのｉ行ｊ列の要素、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ＮＭＡＸはＮＡとＮＢが取りうる最大の整数、ｎとｊは１以上ＮＭＡＸ以下の整数、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＢ［１］，…，ｔＢ［ＮＭＡＸ］は０以上ｐ−１以下の整数、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ［１］）、ＴＢ［ｊ］＝ｇ＾ｔＢ［１］、
【数２０】
、｛ＴＢ｝はＴＢ［１］，…，ＴＢ［ＮＭＡＸ］の集合、｛ＳＢ｝はＳＢ［１］，…，ＳＢ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合、＾はべき乗を示す記号であり、
アクセス構造ＡＢを決定し、当該アクセス構造ＡＢに対応するシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成するアクセス構造決定部と、
１≦ｊ≦ＮＢについて、ｖ〜ｊを０以上ｐ−１以下の整数からランダムに選定する短期秘密鍵生成部と、
１≦ｊ≦ＮＢについて、ｖｊ＝Ｈ２（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝，ｖ〜ｊ）と、
Ｙ＝ｇ＾ｖ１と、
１≦ｉ≦ＬＢと１≦ｊ≦ＮＢについて、
Ｖｉ，ｊ＝ｇ＾（ｒ（ＭＢ）ｉ，ｊｖｊ）・Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と、
１≦ｉ≦ＬＢとＮＢ＋１≦ｊ≦ＮＭＡＸについて、
Ｖｉ，ｊ＝Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と
を計算する交換情報生成部と、
（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを鍵交換する対象の装置に送信する送信部と、
鍵交換する対象の装置から、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを受信する受信部と、
属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすか、Ｘと｛Ｕ｝が群Ｇの要素かを確認する属性確認部と、
ＩＢ＝｛ｋ：ρＡ（ｋ）∈ＳＢ｝となる集合ＩＢを求め、鍵交換する対象の装置が生成した秘密情報ｕ１に対する正当なシェア情報集合｛（ＭＡ）ｉ，ｊｕｊ｝について
【数２１】
が成り立つ０以上ｐ−１以下の整数ｗＢ［ｋ］（ただし、ｋは集合ＩＢの要素）を求める秘密情報取得部と、
【数２２】
σ２＝（ｇＴ＾ｚ）＾ｖ１
σ３＝Ｘ＾ｖ１
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求めるセッション鍵計算部と、
ｖｊ（１≦ｊ≦ＮＢ）を消去する中間情報消去部と、
を備える鍵交換装置。
【請求項３】
鍵交換装置用のマスタ秘密鍵、マスタ公開鍵、長期秘密鍵を生成する鍵生成装置であって、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは前記鍵交換装置の属性を示す属性要素Ｐｎの組み合わせの集合、ＮＭＡＸはあらかじめ定めた整数、ｊは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、＾はべき乗を示す記号であり、
０以上ｐ−１以下の整数からランダムにｒとｚを選定し、マスタ公開鍵を（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）、マスタ秘密鍵をｇ＾ｚとするマスタ鍵生成部と、
０以上ｐ−１以下の整数からランダムにｔＡ［１］，…，ｔＡ［ＮＭＡＸ］を選び、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）を計算し、１以上ＮＭＡＸ以下のｊについてＴＡ［ｊ］＝ｇ＾ｔＡ［１］を計算し、属性集合ＳＡの要素ｋＡについて
【数２３】
を計算し、長期秘密鍵として（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝）を出力する長期秘密鍵生成部と、
を備える鍵生成装置。
【請求項４】
少なくとも鍵交換装置αと鍵交換装置βとを備え、セッション鍵を交換する鍵交換システムであって、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置αの属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＡは鍵交換装置αが鍵交換装置βに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉ，ｊはシェア情報生成行列ＭＡのｉ行ｊ列の要素、属性集合ＳＢは鍵交換装置βの属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＢは鍵交換装置βが鍵交換装置αに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉ，ｊはシェア情報生成行列ＭＢのｉ行ｊ列の要素、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ＮＭＡＸはＮＡとＮＢが取りうる最大の整数、ｎとｊは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡ［１］，…，ｔＡ［ＮＭＡＸ］は０以上ｐ−１以下の整数、ｔＢ［１］，…，ｔＢ［ＮＭＡＸ］は０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ［１］）、ＴＡ［ｊ］＝ｇ＾ｔＡ［１］、ＴＢ［ｊ］＝ｇ＾ｔＢ［１］、
【数２４】
、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＴＢ｝はＴＢ［１］，…，ＴＢ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、｛ＳＢ｝はＳＢ［１］，…，ＳＢ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合、＾はべき乗を示す記号であり、
前記鍵交換装置αは、
アクセス構造ＡＡを決定し、当該アクセス構造ＡＡに対応するシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する第１のアクセス構造決定部と、
１≦ｊ≦ＮＡについて、ｕ〜ｊを０以上ｐ−１以下の整数からランダムに選定する第１の短期秘密鍵生成部と、
１≦ｊ≦ＮＡについて、ｕｊ＝Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜ｊ）と、
Ｘ＝ｇ＾ｕ１と、
１≦ｉ≦ＬＡと１≦ｊ≦ＮＡについて、
Ｕｉ，ｊ＝ｇ＾（ｒ（ＭＡ）ｉ，ｊｕｊ）・Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）と、
１≦ｉ≦ＬＡとＮＡ＋１≦ｊ≦ＮＭＡＸについて、
Ｕｉ，ｊ＝Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）と
を計算する第１の交換情報生成部と、
（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを鍵交換装置βに送信する第１の送信部と、
鍵交換装置βから、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを受信する第１の受信部と、
属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすか、Ｙと｛Ｖ｝が群Ｇの要素かを確認する第１の属性確認部と、
ＩＡ＝｛ｋ：ρＢ（ｋ）∈ＳＡ｝となる集合ＩＡを求め、鍵交換装置βが生成した秘密情報ｖ１に対する正当なシェア情報集合｛（ＭＢ）ｉ，ｊｖｊ｝について
【数２５】
が成り立つ０以上ｐ−１以下の整数ｗＡ［ｋ］（ただし、ｋは集合ＩＡの要素）を求める第１の秘密情報取得部と、
【数２６】
σ１＝（ｇＴ＾ｚ）＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
σ３＝Ｙ＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める第１のセッション鍵計算部と、
ｕｊ（１≦ｊ≦ＮＡ）を消去する第１の中間情報消去部と、
を備え、
前記鍵交換装置βは、
アクセス構造ＡＢを決定し、当該アクセス構造ＡＢに対応するシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する第２のアクセス構造決定部と、
１≦ｊ≦ＮＢについて、ｖ〜ｊを０以上ｐ−１以下の整数からランダムに選定する第２の短期秘密鍵生成部と、
１≦ｊ≦ＮＢについて、ｖｊ＝Ｈ２（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝，ｖ〜ｊ）と、
Ｙ＝ｇ＾ｖ１と、
１≦ｉ≦ＬＢと１≦ｊ≦ＮＢについて、
Ｖｉ，ｊ＝ｇ＾（ｒ（ＭＢ）ｉ，ｊｖｊ）・Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と、
１≦ｉ≦ＬＢとＮＢ＋１≦ｊ≦ＮＭＡＸについて、
Ｖｉ，ｊ＝Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と
を計算する第２の交換情報生成部と、
（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを鍵交換装置αに送信する第２の送信部と、
鍵交換装置αから、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを受信する第２の受信部と、
属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすか、Ｘと｛Ｕ｝が群Ｇの要素かを確認する第２の属性確認部と、
ＩＢ＝｛ｋ：ρＡ（ｋ）∈ＳＢ｝となる集合ＩＢを求め、鍵交換装置αが生成した秘密情報ｕ１に対する正当なシェア情報集合｛（ＭＡ）ｉ，ｊｕｊ｝について
【数２７】
が成り立つ０以上ｐ−１以下の整数ｗＢ［ｋ］（ただし、ｋは集合ＩＢの要素）を求める第２の秘密情報取得部と、
【数２８】
σ２＝（ｇＴ＾ｚ）＾ｖ１
σ３＝Ｘ＾ｖ１
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める第２のセッション鍵計算部と、
ｖｊ（１≦ｊ≦ＮＢ）を消去する第２の中間情報消去部と、
を備える
鍵交換システム。
【請求項５】
請求項４記載の鍵交換システムであって、
さらに、マスタ鍵生成部と長期秘密鍵生成部とを有する鍵生成装置を備え、
前記ｒとｚは、前記マスタ鍵生成部がランダムに選定したものであり、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）とマスタ秘密鍵ｇ＾ｚは前記マスタ鍵生成部が生成したものであり、
前記ｔＡ［１］，…，ｔＡ［ＮＭＡＸ］とｔＢ［１］，…，ｔＢ［ＮＭＡＸ］は前記長期秘密鍵生成部がランダムに選定したものであり、Ｓ’ＡとＳ’Ｂ、ＴＡ［ｊ］とＴＢ［ｊ］、ＳＡ［ｋＡ］とＳＢ［ｋＢ］は前記長期秘密鍵生成部が計算したものであり、
前記鍵交換装置αは、前記鍵生成装置から長期秘密鍵としてＳ’Ａ，｛ＴＡ｝，｛ＳＡ｝を取得し、前記鍵交換装置βは、前記鍵生成装置から長期秘密鍵としてＳ’Ｂ，｛ＴＢ｝，｛ＳＢ｝を取得する
ことを特徴とする鍵交換システム。
【請求項６】
少なくとも鍵交換装置αと鍵交換装置βとを備える鍵交換システムを用いて、セッション鍵を交換する鍵交換方法であって、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置αの属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＡは鍵交換装置αが鍵交換装置βに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉ，ｊはシェア情報生成行列ＭＡのｉ行ｊ列の要素、属性集合ＳＢは鍵交換装置βの属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＢは鍵交換装置βが鍵交換装置αに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉ，ｊはシェア情報生成行列ＭＢのｉ行ｊ列の要素、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ＮＭＡＸはＮＡとＮＢが取りうる最大の整数、ｎとｊは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡ［１］，…，ｔＡ［ＮＭＡＸ］は０以上ｐ−１以下の整数、ｔＢ［１］，…，ｔＢ［ＮＭＡＸ］は０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ［１］）、ＴＡ［ｊ］＝ｇ＾ｔＡ［１］、ＴＢ［ｊ］＝ｇ＾ｔＢ［１］、
【数２９】
、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＴＢ｝はＴＢ［１］，…，ＴＢ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、｛ＳＢ｝はＳＢ［１］，…，ＳＢ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合、＾はべき乗を示す記号であり、
前記鍵交換装置αが、アクセス構造ＡＡを決定し、当該アクセス構造ＡＡに対応するシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する第１のアクセス構造決定ステップと、
前記鍵交換装置αが、１≦ｊ≦ＮＡについて、ｕ〜ｊを０以上ｐ−１以下の整数からランダムに選定する第１の短期秘密鍵生成ステップと、
前記鍵交換装置αが、
１≦ｊ≦ＮＡについて、ｕｊ＝Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜ｊ）と、
Ｘ＝ｇ＾ｕ１と、
１≦ｉ≦ＬＡと１≦ｊ≦ＮＡについて、
Ｕｉ，ｊ＝ｇ＾（ｒ（ＭＡ）ｉ，ｊｕｊ）・Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）と、
１≦ｉ≦ＬＡとＮＡ＋１≦ｊ≦ＮＭＡＸについて、
Ｕｉ，ｊ＝Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）と
を計算する第１の交換情報生成ステップと、
前記鍵交換装置αが、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを鍵交換装置βに送信する第１の送信ステップと、
前記鍵交換装置αが、ｕｊ（１≦ｊ≦ＮＡ）を消去する第１の中間情報消去ステップと、
前記鍵交換装置βが、鍵交換装置αから、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを受信する第２の受信ステップと、
前記鍵交換装置βが、属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすか、Ｘと｛Ｕ｝が群Ｇの要素かを確認する第２の属性確認ステップと、
前記鍵交換装置βが、アクセス構造ＡＢを決定し、当該アクセス構造ＡＢに対応するシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する第２のアクセス構造決定ステップと、
前記鍵交換装置βが、１≦ｊ≦ＮＢについて、ｖ〜ｊを０以上ｐ−１以下の整数からランダムに選定する第２の短期秘密鍵生成ステップと、
前記鍵交換装置βが、
１≦ｊ≦ＮＢについて、ｖｊ＝Ｈ２（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝，ｖ〜ｊ）と、
Ｙ＝ｇ＾ｖ１と、
１≦ｉ≦ＬＢと１≦ｊ≦ＮＢについて、
Ｖｉ，ｊ＝ｇ＾（ｒ（ＭＢ）ｉ，ｊｖｊ）・Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と、
１≦ｉ≦ＬＢとＮＢ＋１≦ｊ≦ＮＭＡＸについて、
Ｖｉ，ｊ＝Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と
を計算する第２の交換情報生成ステップと、
前記鍵交換装置βが、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを鍵交換装置αに送信する第２の送信ステップと、
前記鍵交換装置βが、ＩＢ＝｛ｋ：ρＡ（ｋ）∈ＳＢ｝となる集合ＩＢを求め、鍵交換装置αが生成した秘密情報ｕ１に対する正当なシェア情報集合｛（ＭＡ）ｉ，ｊｕｊ｝について
【数３０】
が成り立つ０以上ｐ−１以下の整数ｗＢ［ｋ］（ただし、ｋは集合ＩＢの要素）を求める第２の秘密情報取得ステップと、
前記鍵交換装置βが、
【数３１】
σ２＝（ｇＴ＾ｚ）＾ｖ１
σ３＝Ｘ＾ｖ１
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める第２のセッション鍵計算ステップと、
前記鍵交換装置βが、ｖｊ（１≦ｊ≦ＮＢ）を消去する第２の中間情報消去ステップと、
前記鍵交換装置αが、鍵交換装置βから、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを受信する第１の受信ステップと、
前記鍵交換装置αが、属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすか、Ｙと｛Ｖ｝が群Ｇの要素かを確認する第１の属性確認ステップと、
前記鍵交換装置αが、ＩＡ＝｛ｋ：ρＢ（ｋ）∈ＳＡ｝となる集合ＩＡを求め、鍵交換装置βが生成した秘密情報ｖ１に対する正当なシェア情報集合｛（ＭＢ）ｉ，ｊｖｊ｝について
【数３２】
が成り立つ０以上ｐ−１以下の整数ｗＡ［ｋ］（ただし、ｋは集合ＩＡの要素）を求める第１の秘密情報取得ステップと、
前記鍵交換装置αが、
【数３３】
σ１＝（ｇＴ＾ｚ）＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
σ３＝Ｙ＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める第１のセッション鍵計算ステップと、
を有する鍵交換方法。
【請求項７】
請求項６記載の鍵交換方法であって、
前記鍵交換システムは、さらにマスタ鍵生成手段と長期秘密鍵生成手段も備え、
前記マスタ鍵生成手段が、前記ｒとｚをランダムに選定し、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）とマスタ秘密鍵ｇ＾ｚを生成する前記マスタ鍵生成ステップと、
前記長期秘密鍵生成手段が、前記ｔＡ［１］，…，ｔＡ［ＮＭＡＸ］とｔＢ［１］，…，ｔＢ［ＮＭＡＸ］をランダムに選定し、Ｓ’ＡとＳ’Ｂ、ＴＡ［ｊ］とＴＢ［ｊ］、ＳＡ［ｋＡ］とＳＢ［ｋＢ］を計算する長期秘密鍵生成ステップと、
前記鍵交換装置αが、長期秘密鍵としてＳ’Ａ，｛ＴＡ｝，｛ＳＡ｝を取得する第１の長期秘密鍵取得ステップと、
前記鍵交換装置βが、長期秘密鍵としてＳ’Ｂ，｛ＴＢ｝，｛ＳＢ｝を取得する第２の長期秘密鍵取得ステップ
も有することを特徴とする鍵交換方法。
【請求項８】
請求項１または２記載の鍵交換装置、もしくは請求項３記載の鍵生成装置としてコンピュータを機能させるためのプログラム。
【請求項１】
セッション鍵を交換する鍵交換装置であって、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは当該鍵交換装置の属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＡは当該鍵交換装置が鍵交換の対象となる装置に求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉ，ｊはシェア情報生成行列ＭＡのｉ行ｊ列の要素、アクセス構造ＡＢは鍵交換の対象となる装置が当該鍵交換装置に求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉ，ｊはシェア情報生成行列ＭＢのｉ行ｊ列の要素、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ＮＭＡＸはＮＡとＮＢが取りうる最大の整数、ｎとｊは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、ｒとｚは０以上ｐ−１以下の整数、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡ［１］，…，ｔＡ［ＮＭＡＸ］は０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）、ＴＡ［ｊ］＝ｇ＾ｔＡ［１］、
【数１７】
、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合、＾はべき乗を示す記号であり、
アクセス構造ＡＡを決定し、当該アクセス構造ＡＡに対応するシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成するアクセス構造決定部と、
１≦ｊ≦ＮＡについて、ｕ〜ｊを０以上ｐ−１以下の整数からランダムに選定する短期秘密鍵生成部と、
１≦ｊ≦ＮＡについて、ｕｊ＝Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜ｊ）と、
Ｘ＝ｇ＾ｕ１と、
１≦ｉ≦ＬＡと１≦ｊ≦ＮＡについて、
Ｕｉ，ｊ＝ｇ＾（ｒ（ＭＡ）ｉ，ｊｕｊ）・Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）と、
１≦ｉ≦ＬＡとＮＡ＋１≦ｊ≦ＮＭＡＸについて、
Ｕｉ，ｊ＝Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）と
を計算する交換情報生成部と、
（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを鍵交換する対象の装置に送信する送信部と、
鍵交換する対象の装置から、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを受信する受信部と、
属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすか、Ｙと｛Ｖ｝が群Ｇの要素かを確認する属性確認部と、
ＩＡ＝｛ｋ：ρＢ（ｋ）∈ＳＡ｝となる集合ＩＡを求め、鍵交換する対象の装置が生成した秘密情報ｖ１に対する正当なシェア情報集合｛（ＭＢ）ｉ，ｊｖｊ｝について
【数１８】
が成り立つ０以上ｐ−１以下の整数ｗＡ［ｋ］（ただし、ｋは集合ＩＡの要素）を求める秘密情報取得部と、
【数１９】
σ１＝（ｇＴ＾ｚ）＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
σ３＝Ｙ＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求めるセッション鍵計算部と、
ｕｊ（１≦ｊ≦ＮＡ）を消去する中間情報消去部と、
を備える鍵交換装置。
【請求項２】
セッション鍵を交換する鍵交換装置であって、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＢは当該鍵交換装置の属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＢは当該鍵交換装置が鍵交換の対象となる装置に求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉ，ｊはシェア情報生成行列ＭＢのｉ行ｊ列の要素、アクセス構造ＡＡは鍵交換の対象となる装置が当該鍵交換装置に求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉ，ｊはシェア情報生成行列ＭＡのｉ行ｊ列の要素、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ＮＭＡＸはＮＡとＮＢが取りうる最大の整数、ｎとｊは１以上ＮＭＡＸ以下の整数、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＢ［１］，…，ｔＢ［ＮＭＡＸ］は０以上ｐ−１以下の整数、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ［１］）、ＴＢ［ｊ］＝ｇ＾ｔＢ［１］、
【数２０】
、｛ＴＢ｝はＴＢ［１］，…，ＴＢ［ＮＭＡＸ］の集合、｛ＳＢ｝はＳＢ［１］，…，ＳＢ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合、＾はべき乗を示す記号であり、
アクセス構造ＡＢを決定し、当該アクセス構造ＡＢに対応するシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成するアクセス構造決定部と、
１≦ｊ≦ＮＢについて、ｖ〜ｊを０以上ｐ−１以下の整数からランダムに選定する短期秘密鍵生成部と、
１≦ｊ≦ＮＢについて、ｖｊ＝Ｈ２（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝，ｖ〜ｊ）と、
Ｙ＝ｇ＾ｖ１と、
１≦ｉ≦ＬＢと１≦ｊ≦ＮＢについて、
Ｖｉ，ｊ＝ｇ＾（ｒ（ＭＢ）ｉ，ｊｖｊ）・Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と、
１≦ｉ≦ＬＢとＮＢ＋１≦ｊ≦ＮＭＡＸについて、
Ｖｉ，ｊ＝Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と
を計算する交換情報生成部と、
（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを鍵交換する対象の装置に送信する送信部と、
鍵交換する対象の装置から、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを受信する受信部と、
属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすか、Ｘと｛Ｕ｝が群Ｇの要素かを確認する属性確認部と、
ＩＢ＝｛ｋ：ρＡ（ｋ）∈ＳＢ｝となる集合ＩＢを求め、鍵交換する対象の装置が生成した秘密情報ｕ１に対する正当なシェア情報集合｛（ＭＡ）ｉ，ｊｕｊ｝について
【数２１】
が成り立つ０以上ｐ−１以下の整数ｗＢ［ｋ］（ただし、ｋは集合ＩＢの要素）を求める秘密情報取得部と、
【数２２】
σ２＝（ｇＴ＾ｚ）＾ｖ１
σ３＝Ｘ＾ｖ１
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求めるセッション鍵計算部と、
ｖｊ（１≦ｊ≦ＮＢ）を消去する中間情報消去部と、
を備える鍵交換装置。
【請求項３】
鍵交換装置用のマスタ秘密鍵、マスタ公開鍵、長期秘密鍵を生成する鍵生成装置であって、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは前記鍵交換装置の属性を示す属性要素Ｐｎの組み合わせの集合、ＮＭＡＸはあらかじめ定めた整数、ｊは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、＾はべき乗を示す記号であり、
０以上ｐ−１以下の整数からランダムにｒとｚを選定し、マスタ公開鍵を（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）、マスタ秘密鍵をｇ＾ｚとするマスタ鍵生成部と、
０以上ｐ−１以下の整数からランダムにｔＡ［１］，…，ｔＡ［ＮＭＡＸ］を選び、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）を計算し、１以上ＮＭＡＸ以下のｊについてＴＡ［ｊ］＝ｇ＾ｔＡ［１］を計算し、属性集合ＳＡの要素ｋＡについて
【数２３】
を計算し、長期秘密鍵として（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝）を出力する長期秘密鍵生成部と、
を備える鍵生成装置。
【請求項４】
少なくとも鍵交換装置αと鍵交換装置βとを備え、セッション鍵を交換する鍵交換システムであって、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置αの属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＡは鍵交換装置αが鍵交換装置βに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉ，ｊはシェア情報生成行列ＭＡのｉ行ｊ列の要素、属性集合ＳＢは鍵交換装置βの属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＢは鍵交換装置βが鍵交換装置αに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉ，ｊはシェア情報生成行列ＭＢのｉ行ｊ列の要素、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ＮＭＡＸはＮＡとＮＢが取りうる最大の整数、ｎとｊは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡ［１］，…，ｔＡ［ＮＭＡＸ］は０以上ｐ−１以下の整数、ｔＢ［１］，…，ｔＢ［ＮＭＡＸ］は０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ［１］）、ＴＡ［ｊ］＝ｇ＾ｔＡ［１］、ＴＢ［ｊ］＝ｇ＾ｔＢ［１］、
【数２４】
、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＴＢ｝はＴＢ［１］，…，ＴＢ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、｛ＳＢ｝はＳＢ［１］，…，ＳＢ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合、＾はべき乗を示す記号であり、
前記鍵交換装置αは、
アクセス構造ＡＡを決定し、当該アクセス構造ＡＡに対応するシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する第１のアクセス構造決定部と、
１≦ｊ≦ＮＡについて、ｕ〜ｊを０以上ｐ−１以下の整数からランダムに選定する第１の短期秘密鍵生成部と、
１≦ｊ≦ＮＡについて、ｕｊ＝Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜ｊ）と、
Ｘ＝ｇ＾ｕ１と、
１≦ｉ≦ＬＡと１≦ｊ≦ＮＡについて、
Ｕｉ，ｊ＝ｇ＾（ｒ（ＭＡ）ｉ，ｊｕｊ）・Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）と、
１≦ｉ≦ＬＡとＮＡ＋１≦ｊ≦ＮＭＡＸについて、
Ｕｉ，ｊ＝Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）と
を計算する第１の交換情報生成部と、
（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを鍵交換装置βに送信する第１の送信部と、
鍵交換装置βから、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを受信する第１の受信部と、
属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすか、Ｙと｛Ｖ｝が群Ｇの要素かを確認する第１の属性確認部と、
ＩＡ＝｛ｋ：ρＢ（ｋ）∈ＳＡ｝となる集合ＩＡを求め、鍵交換装置βが生成した秘密情報ｖ１に対する正当なシェア情報集合｛（ＭＢ）ｉ，ｊｖｊ｝について
【数２５】
が成り立つ０以上ｐ−１以下の整数ｗＡ［ｋ］（ただし、ｋは集合ＩＡの要素）を求める第１の秘密情報取得部と、
【数２６】
σ１＝（ｇＴ＾ｚ）＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
σ３＝Ｙ＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める第１のセッション鍵計算部と、
ｕｊ（１≦ｊ≦ＮＡ）を消去する第１の中間情報消去部と、
を備え、
前記鍵交換装置βは、
アクセス構造ＡＢを決定し、当該アクセス構造ＡＢに対応するシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する第２のアクセス構造決定部と、
１≦ｊ≦ＮＢについて、ｖ〜ｊを０以上ｐ−１以下の整数からランダムに選定する第２の短期秘密鍵生成部と、
１≦ｊ≦ＮＢについて、ｖｊ＝Ｈ２（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝，ｖ〜ｊ）と、
Ｙ＝ｇ＾ｖ１と、
１≦ｉ≦ＬＢと１≦ｊ≦ＮＢについて、
Ｖｉ，ｊ＝ｇ＾（ｒ（ＭＢ）ｉ，ｊｖｊ）・Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と、
１≦ｉ≦ＬＢとＮＢ＋１≦ｊ≦ＮＭＡＸについて、
Ｖｉ，ｊ＝Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と
を計算する第２の交換情報生成部と、
（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを鍵交換装置αに送信する第２の送信部と、
鍵交換装置αから、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを受信する第２の受信部と、
属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすか、Ｘと｛Ｕ｝が群Ｇの要素かを確認する第２の属性確認部と、
ＩＢ＝｛ｋ：ρＡ（ｋ）∈ＳＢ｝となる集合ＩＢを求め、鍵交換装置αが生成した秘密情報ｕ１に対する正当なシェア情報集合｛（ＭＡ）ｉ，ｊｕｊ｝について
【数２７】
が成り立つ０以上ｐ−１以下の整数ｗＢ［ｋ］（ただし、ｋは集合ＩＢの要素）を求める第２の秘密情報取得部と、
【数２８】
σ２＝（ｇＴ＾ｚ）＾ｖ１
σ３＝Ｘ＾ｖ１
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める第２のセッション鍵計算部と、
ｖｊ（１≦ｊ≦ＮＢ）を消去する第２の中間情報消去部と、
を備える
鍵交換システム。
【請求項５】
請求項４記載の鍵交換システムであって、
さらに、マスタ鍵生成部と長期秘密鍵生成部とを有する鍵生成装置を備え、
前記ｒとｚは、前記マスタ鍵生成部がランダムに選定したものであり、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）とマスタ秘密鍵ｇ＾ｚは前記マスタ鍵生成部が生成したものであり、
前記ｔＡ［１］，…，ｔＡ［ＮＭＡＸ］とｔＢ［１］，…，ｔＢ［ＮＭＡＸ］は前記長期秘密鍵生成部がランダムに選定したものであり、Ｓ’ＡとＳ’Ｂ、ＴＡ［ｊ］とＴＢ［ｊ］、ＳＡ［ｋＡ］とＳＢ［ｋＢ］は前記長期秘密鍵生成部が計算したものであり、
前記鍵交換装置αは、前記鍵生成装置から長期秘密鍵としてＳ’Ａ，｛ＴＡ｝，｛ＳＡ｝を取得し、前記鍵交換装置βは、前記鍵生成装置から長期秘密鍵としてＳ’Ｂ，｛ＴＢ｝，｛ＳＢ｝を取得する
ことを特徴とする鍵交換システム。
【請求項６】
少なくとも鍵交換装置αと鍵交換装置βとを備える鍵交換システムを用いて、セッション鍵を交換する鍵交換方法であって、
κは整数、ｐはκビットの素数、ＧとＧＴは位数ｐの群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形写像、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈ３は任意長の整数をκビットの整数に変換するハッシュ関数、Ｐｎは属性を示す属性要素、属性集合ＳＡは鍵交換装置αの属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＡは鍵交換装置αが鍵交換装置βに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＡは前記アクセス構造ＡＡを示す関数、属性集合ρＡ（ｉ）は前記アクセス構造ＡＡに対応するｉ番目の集合、シェア情報生成行列ＭＡはｉ行目が属性集合ρＡ（ｉ）に対応するＬＡ行ＮＡ列の行列、（ＭＡ）ｉ，ｊはシェア情報生成行列ＭＡのｉ行ｊ列の要素、属性集合ＳＢは鍵交換装置βの属性を示す属性要素Ｐｎの組み合わせの集合、アクセス構造ＡＢは鍵交換装置βが鍵交換装置αに求める属性要素Ｐｎの組み合わせの集合、単射ラベリング関数ρＢは前記アクセス構造ＡＢを示す関数、属性集合ρＢ（ｉ）は前記アクセス構造ＡＢに対応するｉ番目の集合、シェア情報生成行列ＭＢはｉ行目が属性集合ρＢ（ｉ）に対応するＬＢ行ＮＢ列の行列、（ＭＢ）ｉ，ｊはシェア情報生成行列ＭＢのｉ行ｊ列の要素、ＬＡ、ＮＡ、ＬＢ、ＮＢは整数、ＮＭＡＸはＮＡとＮＢが取りうる最大の整数、ｎとｊは１以上ＮＭＡＸ以下の整数、ｋＡは属性集合ＳＡの要素、ｋＢは属性集合ＳＢの要素、ｒとｚは０以上ｐ−１以下の整数、（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）はマスタ公開鍵、ｇ＾ｚはマスタ秘密鍵、ｔＡ［１］，…，ｔＡ［ＮＭＡＸ］は０以上ｐ−１以下の整数、ｔＢ［１］，…，ｔＢ［ＮＭＡＸ］は０以上ｐ−１以下の整数、Ｓ’Ａ＝ｇ＾ｚ・ｇ＾（ｒｔＡ［１］）、Ｓ’Ｂ＝ｇ＾ｚ・ｇ＾（ｒｔＢ［１］）、ＴＡ［ｊ］＝ｇ＾ｔＡ［１］、ＴＢ［ｊ］＝ｇ＾ｔＢ［１］、
【数２９】
、｛ＴＡ｝はＴＡ［１］，…，ＴＡ［ＮＭＡＸ］の集合、｛ＴＢ｝はＴＢ［１］，…，ＴＢ［ＮＭＡＸ］の集合、｛ＳＡ｝はＳＡ［１］，…，ＳＡ［ＮＭＡＸ］の集合、｛ＳＢ｝はＳＢ［１］，…，ＳＢ［ＮＭＡＸ］の集合、｛Ｕ｝はＵｉ，ｊの集合、｛Ｖ｝はＶｉ，ｊの集合、＾はべき乗を示す記号であり、
前記鍵交換装置αが、アクセス構造ＡＡを決定し、当該アクセス構造ＡＡに対応するシェア情報生成行列ＭＡと単射ラベリング関数ρＡを生成する第１のアクセス構造決定ステップと、
前記鍵交換装置αが、１≦ｊ≦ＮＡについて、ｕ〜ｊを０以上ｐ−１以下の整数からランダムに選定する第１の短期秘密鍵生成ステップと、
前記鍵交換装置αが、
１≦ｊ≦ＮＡについて、ｕｊ＝Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜ｊ）と、
Ｘ＝ｇ＾ｕ１と、
１≦ｉ≦ＬＡと１≦ｊ≦ＮＡについて、
Ｕｉ，ｊ＝ｇ＾（ｒ（ＭＡ）ｉ，ｊｕｊ）・Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）と、
１≦ｉ≦ＬＡとＮＡ＋１≦ｊ≦ＮＭＡＸについて、
Ｕｉ，ｊ＝Ｈ１（ｊ，ρＡ（ｉ））＾（−ｕ１）と
を計算する第１の交換情報生成ステップと、
前記鍵交換装置αが、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを鍵交換装置βに送信する第１の送信ステップと、
前記鍵交換装置αが、ｕｊ（１≦ｊ≦ＮＡ）を消去する第１の中間情報消去ステップと、
前記鍵交換装置βが、鍵交換装置αから、（Ｘ，｛Ｕ｝）、ＭＡ、ρＡを受信する第２の受信ステップと、
前記鍵交換装置βが、属性集合ＳＢがシェア情報生成行列ＭＡと単射ラベリング関数ρＡを満たすか、Ｘと｛Ｕ｝が群Ｇの要素かを確認する第２の属性確認ステップと、
前記鍵交換装置βが、アクセス構造ＡＢを決定し、当該アクセス構造ＡＢに対応するシェア情報生成行列ＭＢと単射ラベリング関数ρＢを生成する第２のアクセス構造決定ステップと、
前記鍵交換装置βが、１≦ｊ≦ＮＢについて、ｖ〜ｊを０以上ｐ−１以下の整数からランダムに選定する第２の短期秘密鍵生成ステップと、
前記鍵交換装置βが、
１≦ｊ≦ＮＢについて、ｖｊ＝Ｈ２（Ｓ’Ｂ，｛ＴＢ｝，｛ＳＢ｝，ｖ〜ｊ）と、
Ｙ＝ｇ＾ｖ１と、
１≦ｉ≦ＬＢと１≦ｊ≦ＮＢについて、
Ｖｉ，ｊ＝ｇ＾（ｒ（ＭＢ）ｉ，ｊｖｊ）・Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と、
１≦ｉ≦ＬＢとＮＢ＋１≦ｊ≦ＮＭＡＸについて、
Ｖｉ，ｊ＝Ｈ１（ｊ，ρＢ（ｉ））＾（−ｖ１）と
を計算する第２の交換情報生成ステップと、
前記鍵交換装置βが、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを鍵交換装置αに送信する第２の送信ステップと、
前記鍵交換装置βが、ＩＢ＝｛ｋ：ρＡ（ｋ）∈ＳＢ｝となる集合ＩＢを求め、鍵交換装置αが生成した秘密情報ｕ１に対する正当なシェア情報集合｛（ＭＡ）ｉ，ｊｕｊ｝について
【数３０】
が成り立つ０以上ｐ−１以下の整数ｗＢ［ｋ］（ただし、ｋは集合ＩＢの要素）を求める第２の秘密情報取得ステップと、
前記鍵交換装置βが、
【数３１】
σ２＝（ｇＴ＾ｚ）＾ｖ１
σ３＝Ｘ＾ｖ１
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める第２のセッション鍵計算ステップと、
前記鍵交換装置βが、ｖｊ（１≦ｊ≦ＮＢ）を消去する第２の中間情報消去ステップと、
前記鍵交換装置αが、鍵交換装置βから、（Ｙ，｛Ｖ｝）、ＭＢ、ρＢを受信する第１の受信ステップと、
前記鍵交換装置αが、属性集合ＳＡがシェア情報生成行列ＭＢと単射ラベリング関数ρＢを満たすか、Ｙと｛Ｖ｝が群Ｇの要素かを確認する第１の属性確認ステップと、
前記鍵交換装置αが、ＩＡ＝｛ｋ：ρＢ（ｋ）∈ＳＡ｝となる集合ＩＡを求め、鍵交換装置βが生成した秘密情報ｖ１に対する正当なシェア情報集合｛（ＭＢ）ｉ，ｊｖｊ｝について
【数３２】
が成り立つ０以上ｐ−１以下の整数ｗＡ［ｋ］（ただし、ｋは集合ＩＡの要素）を求める第１の秘密情報取得ステップと、
前記鍵交換装置αが、
【数３３】
σ１＝（ｇＴ＾ｚ）＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
σ３＝Ｙ＾Ｈ２（Ｓ’Ａ，｛ＴＡ｝，｛ＳＡ｝，ｕ〜１）
を計算し、セッション鍵Ｋを、
Ｋ＝Ｈ３（σ１，σ２，σ３，（Ｘ，｛Ｕ｝，ＭＡ，ρＡ），（Ｙ，｛Ｖ｝，ＭＢ，ρＢ））
のように求める第１のセッション鍵計算ステップと、
を有する鍵交換方法。
【請求項７】
請求項６記載の鍵交換方法であって、
前記鍵交換システムは、さらにマスタ鍵生成手段と長期秘密鍵生成手段も備え、
前記マスタ鍵生成手段が、前記ｒとｚをランダムに選定し、マスタ公開鍵（ｇ，ｇ＾ｒ，ｇＴ＾ｚ）とマスタ秘密鍵ｇ＾ｚを生成する前記マスタ鍵生成ステップと、
前記長期秘密鍵生成手段が、前記ｔＡ［１］，…，ｔＡ［ＮＭＡＸ］とｔＢ［１］，…，ｔＢ［ＮＭＡＸ］をランダムに選定し、Ｓ’ＡとＳ’Ｂ、ＴＡ［ｊ］とＴＢ［ｊ］、ＳＡ［ｋＡ］とＳＢ［ｋＢ］を計算する長期秘密鍵生成ステップと、
前記鍵交換装置αが、長期秘密鍵としてＳ’Ａ，｛ＴＡ｝，｛ＳＡ｝を取得する第１の長期秘密鍵取得ステップと、
前記鍵交換装置βが、長期秘密鍵としてＳ’Ｂ，｛ＴＢ｝，｛ＳＢ｝を取得する第２の長期秘密鍵取得ステップ
も有することを特徴とする鍵交換方法。
【請求項８】
請求項１または２記載の鍵交換装置、もしくは請求項３記載の鍵生成装置としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１２−１０９９１７（Ｐ２０１２−１０９９１７Ａ）
【公開日】平成２４年６月７日（２０１２．６．７）
【国際特許分類】
【出願番号】特願２０１０−２５９０５３（Ｐ２０１０−２５９０５３）
【出願日】平成２２年１１月１９日（２０１０．１１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年６月７日（２０１２．６．７）
【国際特許分類】
【出願日】平成２２年１１月１９日（２０１０．１１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]