(57)【要約】【課題】次世代公開鍵暗号によりグループ鍵を共有できる鍵合意システム及び鍵生成装置を提供すること。【解決手段】複数のユーザ端末Ｕが木構造グラフのリーフノードに対応付けられたグループにおいて、グループ鍵を共有する鍵合意システム１は、リーフノードのそれぞれにおいて、同一階層内の奇数ノード又は偶数ノードで互いに異なる空間から秘密情報の組を選択する秘密情報選択部１１と、共通の親ノードを持つノード間で、秘密情報の組を用いてＳＩＤＨ鍵共有プロトコルを実行し、当該親ノードの鍵情報を生成する鍵情報生成部１２と、生成された鍵情報に対して、同一階層内の奇数ノード又は偶数ノードで互いに異なるハッシュ関数を用いて、秘密情報の組を算出する秘密情報算出部１３と、ルートノードの鍵情報に基づいて、グループ鍵を生成するグループ鍵生成部１４と、を備える。【選択図】図２
2020005079.tif 000002
【特許請求の範囲】
【請求項１】
複数の端末が木構造グラフのリーフノードに対応付けられたグループにおいて、グループ鍵を共有する鍵合意システムであって、
前記リーフノードのそれぞれにおいて、同一階層内の奇数ノード又は偶数ノードで互いに異なる空間から秘密情報の組を選択する秘密情報選択部と、
共通の親ノードを持つノード間で、前記秘密情報の組を用いてＳＩＤＨ（Ｓｕｐｅｒｓｉｎｇｕｌａｒ  Ｉｓｏｇｅｎｙ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）鍵共有プロトコルを実行し、当該親ノードの鍵情報を生成する鍵情報生成部と、
前記鍵情報生成部により生成された前記鍵情報に対して、同一階層内の奇数ノード又は偶数ノードで互いに異なるハッシュ関数を用いて、前記秘密情報の組を算出する秘密情報算出部と、
ルートノードの前記鍵情報に基づいて、前記グループ鍵を生成するグループ鍵生成部と、を備える鍵合意システム。
【請求項２】
前記親ノードで前記鍵情報を生成する際に、当該親ノードの配下に対応付けられた各端末がそれぞれ少なくとも１回、前記鍵情報生成部により他の端末と鍵共有し、同一の前記鍵情報を取得する請求項１に記載の鍵合意システム。
【請求項３】
前記親ノードで前記鍵情報を生成する際に、子ノードそれぞれ少なくとも１台ずつの前記端末の間で、前記鍵情報生成部により鍵共有し、
前記グループ鍵を、前記ノード間で共有された前記鍵情報により配送する鍵配送部を備える請求項１に記載の鍵合意システム。
【請求項４】
複数の端末が木構造グラフのリーフノードに対応付けられたグループにおいて、グループ鍵を共有する鍵合意方法であって、
前記リーフノードに対応付けられた端末のそれぞれが、同一階層内の奇数ノード又は偶数ノードで互いに異なる空間から秘密情報の組を選択し、
共通の親ノードを持つノードの配下に対応付けられた端末間で、前記秘密情報の組を用いてＳＩＤＨ（Ｓｕｐｅｒｓｉｎｇｕｌａｒ  Ｉｓｏｇｅｎｙ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）鍵共有プロトコルを実行し、当該親ノードの鍵情報を生成し、
前記親ノードの配下に対応付けられた端末が、生成された前記鍵情報に対して、同一階層内の奇数ノード又は偶数ノードで互いに異なるハッシュ関数を用いて、前記秘密情報の組を算出し、
ルートノードの前記鍵情報を生成した端末が、当該鍵情報に基づいて、前記グループ鍵を生成する鍵合意方法。
【請求項５】
木構造グラフのリーフノードに対応付けられたグループにおいて、グループ鍵を共有する鍵生成装置であって、
自装置が対応付けられたリーフノードが同一階層内において、奇数ノードか又は偶数ノードかに応じて、互いに異なる空間から秘密情報の組を選択する秘密情報選択部と、
共通の親ノードを持つノードの配下に対応付けられた他の装置との間で、前記秘密情報の組を用いてＳＩＤＨ（Ｓｕｐｅｒｓｉｎｇｕｌａｒ  Ｉｓｏｇｅｎｙ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）鍵共有プロトコルを実行し、当該親ノードの鍵情報を生成する鍵情報生成部と、
生成された前記鍵情報に対して、同一階層内の奇数ノード又は偶数ノードで互いに異なるハッシュ関数を用いて、前記秘密情報の組を算出する秘密情報算出部と、
ルートノードの前記鍵情報に基づいて、前記グループ鍵を生成するグループ鍵生成部と、を備える鍵生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グループ鍵共有を行う鍵合意システム及び鍵生成装置に関する。
【背景技術】
【０００２】
従来、複数の端末間でグループ鍵を共有するプロトコルが使用されている。例えば、公開鍵暗号を用いた手法として、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有プロトコルに基づくグループ鍵共有方式が挙げられる。
【０００３】
ところが、近年、量子計算機による共有鍵の解読の可能性が指摘されており、ＩｏＴ端末等の非力な端末においても動作し、かつ、量子計算機による解読に対して耐性を持つ次世代公開鍵暗号が研究されている。
例えば、非特許文献１では、次世代公開鍵暗号により二者間で鍵共有できるＳＩＤＨ（Ｓｕｐｅｒｓｉｎｇｕｌａｒ  Ｉｓｏｇｅｎｙ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）鍵共有プロトコルが提案されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｄａｖｉｄ  Ｊａｏ  ａｎｄ  Ｌｕｃａ  Ｄｅ  Ｆｅｏ．  Ｔｏｗａｒｄｓ  ｑｕａｎｔｕｍ−ｒｅｓｉｓｔａｎｔ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ  ｆｒｏｍ  ｓｕｐｅｒｓｉｎｇｕｌａｒ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｉｓｏｇｅｎｉｅｓ．  Ｉｎ  Ｂｏ−Ｙｉｎ  Ｙａｎｇ，  ｅｄｉｔｏｒ，  Ｐｏｓｔ−Ｑｕａｎｔｕｍ  Ｃｒｙｐｔｏｇｒａｐｈｙ，  ｐａｇｅｓ  １９−３４，  Ｂｅｒｌｉｎ，  Ｈｅｉｄｅｌｂｅｒｇ，  ２０１１．  Ｓｐｒｉｎｇｅｒ  Ｂｅｒｌｉｎ  Ｈｅｉｄｅｌｂｅｒｇ．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、ＳＩＤＨ鍵共有プロトコルでは、楕円曲線間の同種写像を利用していることから二者の公開鍵及び共有鍵について、互いに異なる鍵空間が定義される。このため、二者間の共有鍵を公開鍵生成用の秘密情報として再利用することができない。この結果、二者間での鍵共有を繰り返してグループ鍵を共有することは難しかった。
【０００６】
本発明は、次世代公開鍵暗号によりグループ鍵を共有できる鍵合意システム及び鍵生成装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る鍵合意システムは、複数の端末が木構造グラフのリーフノードに対応付けられたグループにおいて、グループ鍵を共有する鍵合意システムであって、前記リーフノードのそれぞれにおいて、同一階層内の奇数ノード又は偶数ノードで互いに異なる空間から秘密情報の組を選択する秘密情報選択部と、共通の親ノードを持つノード間で、前記秘密情報の組を用いてＳＩＤＨ（Ｓｕｐｅｒｓｉｎｇｕｌａｒ  Ｉｓｏｇｅｎｙ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）鍵共有プロトコルを実行し、当該親ノードの鍵情報を生成する鍵情報生成部と、前記鍵情報生成部により生成された前記鍵情報に対して、同一階層内の奇数ノード又は偶数ノードで互いに異なるハッシュ関数を用いて、前記秘密情報の組を算出する秘密情報算出部と、ルートノードの前記鍵情報に基づいて、前記グループ鍵を生成するグループ鍵生成部と、を備える。
【０００８】
前記鍵合意システムは、前記親ノードで前記鍵情報を生成する際に、当該親ノードの配下に対応付けられた各端末がそれぞれ少なくとも１回、前記鍵情報生成部により他の端末と鍵共有し、同一の前記鍵情報を取得してもよい。
【０００９】
前記鍵合意システムは、前記親ノードで前記鍵情報を生成する際に、子ノードそれぞれ少なくとも１台ずつの前記端末の間で、前記鍵情報生成部により鍵共有し、前記グループ鍵を、前記ノード間で共有された前記鍵情報により配送する鍵配送部を備えてもよい。
【００１０】
本発明に係る鍵合意方法は、複数の端末が木構造グラフのリーフノードに対応付けられたグループにおいて、グループ鍵を共有する鍵合意方法であって、前記リーフノードに対応付けられた端末のそれぞれが、同一階層内の奇数ノード又は偶数ノードで互いに異なる空間から秘密情報の組を選択し、共通の親ノードを持つノードの配下に対応付けられた端末間で、前記秘密情報の組を用いてＳＩＤＨ（Ｓｕｐｅｒｓｉｎｇｕｌａｒ  Ｉｓｏｇｅｎｙ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）鍵共有プロトコルを実行し、当該親ノードの鍵情報を生成し、前記親ノードの配下に対応付けられた端末が、生成された前記鍵情報に対して、同一階層内の奇数ノード又は偶数ノードで互いに異なるハッシュ関数を用いて、前記秘密情報の組を算出し、ルートノードの前記鍵情報を生成した端末が、当該鍵情報に基づいて、前記グループ鍵を生成する。
【００１１】
本発明に係る鍵生成装置は、木構造グラフのリーフノードに対応付けられたグループにおいて、グループ鍵を共有する鍵生成装置であって、自装置が対応付けられたリーフノードが同一階層内において、奇数ノードか又は偶数ノードかに応じて、互いに異なる空間から秘密情報の組を選択する秘密情報選択部と、共通の親ノードを持つノードの配下に対応付けられた他の装置との間で、前記秘密情報の組を用いてＳＩＤＨ（Ｓｕｐｅｒｓｉｎｇｕｌａｒ  Ｉｓｏｇｅｎｙ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）鍵共有プロトコルを実行し、当該親ノードの鍵情報を生成する鍵情報生成部と、生成された前記鍵情報に対して、同一階層内の奇数ノード又は偶数ノードで互いに異なるハッシュ関数を用いて、前記秘密情報の組を算出する秘密情報算出部と、ルートノードの前記鍵情報に基づいて、前記グループ鍵を生成するグループ鍵生成部と、を備える。
【発明の効果】
【００１２】
本発明によれば、次世代公開鍵暗号によりグループ鍵を共有できる。
【図面の簡単な説明】
【００１３】
【図１】第１実施形態に係る鍵合意システムの構成を例示する図である。
【図２】第１実施形態に係るユーザ端末の機能構成を示すブロック図である。
【図３】第１実施形態に係るＳＩＤＨ鍵共有プロトコルの手順を示す図である。
【図４】第１実施形態に係るグループ鍵合意プロトコルの手順を示す図である。
【図５】第２実施形態に係るユーザ端末の機能構成を示すブロック図である。
【発明を実施するための形態】
【００１４】
［第１実施形態］
以下、本発明の第１実施形態について説明する。
図１は、本実施形態に係る鍵合意システム１の構成を例示する図である。
鍵合意システム１は、複数のユーザ端末Ｕ（鍵生成装置）がそれぞれ木構造グラフのリーフノードに対応付けられたグループにおいて、グループ鍵を共有する。
【００１５】
ｎ台のユーザ端末からなるグループを｛Ｕ０，・・・，Ｕｎ−１｝と表す。
木構造グラフを構成するノードを＜ｕ，ｖ＞（２ｕ＿ｍａｘ−１＜ｎ≦２ｕ＿ｍａｘ；ｕ＿ｍａｘはｕの最大値）と表す。
全てのノードは、配下に対応付けられた１台以上のユーザ端末Ｕがスポンサーとなる。ノード＜ｕ，ｖ＞のスポンサーをＳ＜ｕ，ｖ＞と表す。
【００１６】
この例では、ユーザ端末Ｕ０〜Ｕ４の５台がグループ鍵を共有する場合を示している。
本実施形態のツリー型グループ鍵合意の手順では、まず、木構造グラフの最下層において、共通の親ノードを持つノード間、すなわち＜３，０＞と＜３，１＞とで鍵共有のプロトコルが実行される。
次に、１階層上位において、同様に、共通の親ノードを持つノード間、すなわち＜２，０＞と＜２，１＞との間、及び＜２，２＞と＜２，３＞との間で鍵共有のプロトコルが実行される。
最後に、＜１，０＞と＜１，１＞とで鍵共有され、ルートノード＜０，０＞の鍵情報が生成される。
【００１７】
このグループ鍵合意の手順において、ノード間の鍵共有のプロトコルは、ノードのスポンサーによって実行され、スポンサーとなったユーザ端末Ｕが共有鍵を記憶する。
本実施形態では、全てのユーザ端末Ｕが対応するリーフノードからルートノードに至るまでの全てのノードのスポンサーとなるものとする。
すなわち、あるノードで鍵情報を生成する際に、このノードの配下に対応付けられた各ユーザ端末Ｕ、すなわちスポンサーがそれぞれ少なくとも１回、他のユーザ端末Ｕと鍵共有し、同一の鍵情報を取得する。
【００１８】
具体的には、まず、ノード＜２，０＞の鍵情報を生成するために、子ノードの＜３，０＞及び＜３，１＞それぞれのスポンサーであるＵ０とＵ１とが鍵共有のプロトコルを実行する。
続いて、ノード＜１，０＞の鍵情報を生成するために、子ノード＜２，０＞のスポンサーであるＵ０及びＵ１と、＜２，１＞のスポンサーであるＵ２との間で鍵共有のプロトコルを実行する。すなわち、Ｕ０とＵ２、Ｕ１とＵ２がそれぞれ鍵共有のプロトコルを実行することで、Ｕ０〜Ｕ２がそれぞれ共通のノード＜１，０＞の鍵情報を取得する。
【００１９】
次に、ルートノード＜０，０＞の鍵情報を生成するために、子ノード＜１，０＞のスポンサーであるＵ０、Ｕ１及びＵ２と、＜１，１＞のスポンサーであるＵ３及びＵ４との間で鍵共有のプロトコルを実行する。すなわち、例えば、Ｕ０とＵ３、Ｕ１とＵ３、Ｕ２とＵ４がそれぞれ鍵共有のプロトコルを実行することで、Ｕ０〜Ｕ４がそれぞれルートノード＜０，０＞の鍵情報を取得する。
なお、鍵共有のプロトコルを実行するスポンサーの組み合わせは、他にＵ０とＵ４、Ｕ１とＵ４、Ｕ２とＵ３があるが、全スポンサーが鍵共有するためには冗長なため、必ずしも必要ではない。つまり、各スポンサーが少なくとも１回鍵共有を行える組み合わせが選択されればよい。
【００２０】
図２は、本実施形態に係るユーザ端末Ｕの機能構成を示すブロック図である。
ユーザ端末Ｕは、パーソナルコンピュータ又はサーバ等の情報処理装置（コンピュータ）であり、制御部１０及び記憶部２０の他、入出力デバイス及び外部装置との通信インタフェース等を備える。
【００２１】
制御部１０は、記憶部２０に格納されたソフトウェアを読み出し実行することにより、次の各部として機能する。
すなわち、制御部１０は、秘密情報選択部１１と、鍵情報生成部１２と、秘密情報算出部１３と、グループ鍵生成部１４とを備える。
【００２２】
秘密情報選択部１１は、木構造グラフにおけるリーフノードのそれぞれにおいて、同一階層内の奇数ノード（＜ｕ，ｖ＞のｖが奇数）又は偶数ノード（＜ｕ，ｖ＞のｖが偶数）で互いに異なる空間から秘密情報の組を選択する。
【００２３】
鍵情報生成部１２は、共通の親ノードを持つノード間、例えば共通の親ノード＜２，０＞を持つノード＜３，０＞と＜３，１＞との間で、秘密情報の組を用いてＳＩＤＨ鍵共有プロトコルを実行し、親ノードの鍵情報を生成する。
【００２４】
秘密情報算出部１３は、鍵情報生成部１２により生成されたあるノードの鍵情報に対して、同一階層内の奇数ノード又は偶数ノードで互いに異なるハッシュ関数を用いて、このノードの秘密情報の組を算出する。
【００２５】
グループ鍵生成部１４は、ルートノードの鍵情報を、例えば所定のハッシュ関数を用いて所定の鍵長に整形しグループ鍵を生成する。
【００２６】
図３は、本実施形態に係るＳＩＤＨ鍵共有プロトコルの手順を示す図である。
ここでは、Ａｌｉｃｅ（Ａ）及びＢｏｂ（Ｂ）の双方が所定の手順により共有鍵を生成する（非特許文献１参照）。
なお、公開パラメータとして、素数ｐ＝ｌＡｅＡｌＢｅＢｆ±１（ｌＡ，ｌＢ，ｅＡ，ｅＢ，ｆ：整数の定数）、楕円曲線Ｅ０、及び楕円曲線Ｅ０上の２組の２点｛ＰＡ，ＱＡ｝，｛ＰＢ，ＱＢ｝が定義されている。
【００２７】
（１−１）Ａｌｉｃｅは、秘密情報ｍＡ，ｎＡを、Ｚ／ｌＡｅＡＺからランダムに選択する。
（１−２）Ａｌｉｃｅは、秘密情報ｍＡ，ｎＡを用いて、同種写像φＡ：＝Ｅ０／＜［ｍＡ］ＰＡ＋［ｎＡ］ＱＡ＞を計算する。
（１−３）Ａｌｉｃｅは、φＡ（ＰＢ），φＡ（ＱＢ），ＥＡ＝φＡ（Ｅ０）を計算し、Ｂｏｂに送る。
【００２８】
（２−１）Ｂｏｂは、秘密情報ｍＢ，ｎＢを、Ｚ／ｌＢｅＢＺからランダムに選択する。
（２−２）Ｂｏｂは、秘密情報ｍＢ，ｎＢを用いて、同種写像φＢ：＝Ｅ０／＜［ｍＢ］ＰＢ＋［ｎＢ］ＱＢ＞を計算する。
（２−３）Ｂｏｂは、φＢ（ＰＡ），φＢ（ＱＡ），ＥＢ＝φＢ（Ｅ０）を計算し、Ａｌｉｃｅに送る。
【００２９】
（３−１）Ｂｏｂは、自身の同種写像φＢを用いて、φＢ（φＡ（ＰＢ）），φＢ（φＡ（ＱＢ）），ＥＡＢ＝φＢ（ＥＡ）を計算する。
（３−２）Ｂｏｂは、楕円曲線のｊ−不変量Ｋ：＝ｊ（ＥＡＢ）を、Ａｌｉｃｅと共通の値として得る。
【００３０】
（４−１）Ａｌｉｃｅは、自身の同種写像φＡを用いて、φＡ（φＢ（ＰＡ）），φＡ（φＢ（ＱＡ）），ＥＢＡ＝φＡ（ＥＢ）を計算する。
（４−２）Ａｌｉｃｅは、楕円曲線のｊ−不変量Ｋ：＝ｊ（ＥＢＡ）を、Ｂｏｂと共通の値として得る。
【００３１】
図４は、本実施形態に係るツリー型グループ鍵合意プロトコルの手順を示す図である。
公開パラメータとして、以下が定義されているものとする。なお、グループ鍵の長さをｋビット、Ｚを有理整数環、Ｆｐをｐ個の元を持つ有限体とする。
【数１】
2020005079.tif 000003
【００３２】
ステップ１において、ユーザ端末Ｕは、木構造グラフの最下層（ｕ＝ｕｍａｘ）からルートノードの１階層下（ｕ＝１）まで、ステップ２〜３の処理を繰り返す。
【００３３】
ステップ２において、スポンサーＳ＜ｕ，ｖ＞は、値ι＝ｖ  （ｍｏｄ  ２）とすると、ノード＜ｕ，ｖ＞が奇数ノード（ι＝１）か偶数ノード（ι＝０）かに応じて、ノード毎の秘密情報ｍ＜ｕ，ｖ＞，ｎ＜ｕ，ｖ＞を設定する。
＜ｕ，ｖ＞がリーフノードの場合、スポンサーＳ＜ｕ，ｖ＞は、Ｚ／ｌιｅιＺからランダムに秘密情報を選択する。
＜ｕ，ｖ＞がリーフノードでない場合、スポンサーＳ＜ｕ，ｖ＞は、後述のステップで生成される鍵情報Ｋ＜ｕ，ｖ＞を用いて、ιに応じて異なるハッシュ演算を行い、ιに応じた空間の秘密情報を算出する。
【００３４】
さらに、スポンサーＳ＜ｕ，ｖ＞は、設定した秘密情報ｍ＜ｕ，ｖ＞，ｎ＜ｕ，ｖ＞を用いて、タプル｛ＥＳ＜ｕ，ｖ＞，φＳ＜ｕ，ｖ＞（Ｐι），φＳ＜ｕ，ｖ＞（Ｑι）｝を計算し、Ｓ’＜ｕ，ｖ＞へ送信する。
なお、Ｓ’＜ｕ，ｖ＞は、ノード＜ｕ，ｖ＞と親ノードが共通であるノードのスポンサー、すなわちＳＩＤＨ鍵共有プロトコルの実行相手である。
【００３５】
ステップ３において、スポンサーＳ’＜ｕ，ｖ＞は、Ｓ＜ｕ，ｖ＞から受け取ったタプルと、自身の秘密情報を用いて、親ノードの鍵情報Ｋ＜ｕ−１，ｆｌｏｏｒ（ｖ／２）＞＝ｊ（ＥＳ＜ｕ，ｖ＞Ｓ’＜ｕ，ｖ＞）を計算する。なお、ｆｌｏｏｒ（ｘ）は、ｘを超えない最大の整数である。
親ノードのスポンサーは、前述のように、Ｓ＜ｕ，ｖ＞∪Ｓ’＜ｕ，ｖ＞となる。
【００３６】
ステップ４において、ルートノードまで鍵情報が計算されていない場合、ステップ１に戻ってループ処理が継続される。
ステップ５において、グループ内の全てのユーザ端末Ｕは、ステップ１〜４のループ処理により、ルートノードの鍵情報Ｋ＜０，０＞を得る。
ユーザ端末Ｕは、このルートノードの鍵情報にハッシュ演算を行い、所定の長さのグループ鍵Ｋ＝Ｈ’ｔ（ｊ（ＥＳ＜１，０＞Ｓ＜１，１＞））を得る。
【００３７】
本実施形態によれば、鍵合意システム１は、ＳＩＤＨ鍵共有プロトコルで生成される鍵情報に対して所定の空間へのハッシュ演算を行うことで、さらにＳＩＤＨ鍵共有プロトコルで使用可能な秘密情報を算出できる。また、鍵合意システム１は、奇数ノード又は偶数ノードのいずれかによって空間（秘密情報の分布）が異なるＳＩＤＨ鍵共有プロトコルに対応して、個別にハッシュ関数を設けた。
したがって、鍵合意システム１は、リーフノードにユーザ端末Ｕが対応付けられた木構造グラフで定義されたグループにおいて、上位のノードの秘密情報を、二者間で共有された鍵情報から二者間で共通して算出できる。この結果、上位のノード間でさらにＳＩＤＨ鍵共有プロトコルを実行できるため、量子計算機に耐性を持つ次世代公開鍵暗号によりグループ鍵を共有できる。
【００３８】
また、鍵合意システム１は、グループ内の全ユーザ端末Ｕが各階層で少なくとも１回、鍵共有を行う。これにより、グループ内の全ユーザがルートノードの鍵情報を算出でき、グループ鍵を共有できる。
【００３９】
［第２実施形態］
以下、本発明の第２実施形態について説明する。
なお、第１実施形態と同様の構成については同一の符号を付し、説明を省略又は簡略化する。
【００４０】
第１実施形態では、あるノードの配下に対応付けられた全てのユーザ端末Ｕがこのノードのスポンサーとなった。本実施形態では、配下に対応付けられた全てのユーザ端末Ｕのうち、少なくとも１台がスポンサーとなる。
すなわち、親ノードの鍵情報を生成する際に、子ノードそれぞれ少なくとも１台ずつのユーザ端末Ｕの間で、鍵共有が行われる。
【００４１】
例えば、図１に示した木構造グラフの例では、まず、ノード＜２，０＞の鍵情報を生成するために、子ノードの＜３，０＞及び＜３，１＞それぞれのスポンサーであるＵ０とＵ１とが鍵共有のプロトコルを実行する。ここで、ノード＜２，０＞のスポンサーとして、子ノードのスポンサーから１台、例えばＵ０が選択される。
【００４２】
続いて、ノード＜１，０＞の鍵情報を生成するために、子ノード＜２，０＞のスポンサーであるＵ０と、＜２，１＞のスポンサーであるＵ２との間で鍵共有のプロトコルを実行する。これにより、Ｕ０及びＵ２がそれぞれ共通のノード＜１，０＞の鍵情報を取得するが、Ｕ１は、この時点でノード＜１，０＞の鍵情報を取得できていない。
【００４３】
同様に、ルートノード＜０，０＞の鍵情報を生成するために、子ノード＜１，０＞のスポンサーとして選ばれたＵ０と、＜１，１＞のスポンサーとして選ばれたＵ３との間で鍵共有のプロトコルを実行する。これにより、Ｕ０及びＵ３がそれぞれルートノード＜０，０＞の鍵情報を取得する。
【００４４】
本実施形態では、この後、ルートノード＜０，０＞の鍵情報を得られていないユーザ端末Ｕ１，Ｕ２，Ｕ４に対して、後述のようにグループ鍵が配送される。
【００４５】
図５は、本実施形態に係るユーザ端末Ｕの機能構成を示すブロック図である。
制御部１０は、第１実施形態（図２）の構成に加えて、鍵配送部１５をさらに備える。
鍵配送部１５は、生成されたグループ鍵を、各階層のノード間で共有された鍵情報により配送する。
【００４６】
具体的には、例えば、前述の例では、ユーザ端末Ｕ０及びＵ３においてグループ鍵が生成された。この後、例えばＵ０とＵ２との間で共有されたノード＜１，０＞の鍵情報を用いて、Ｕ０がＵ２へグループ鍵を配送する。同様に、Ｕ０とＵ１との間で共有されたノード＜２，０＞の鍵情報を用いて、Ｕ０がＵ１へグループ鍵を配送し、Ｕ３とＵ４との間で共有されたノード＜１，１＞の鍵情報を用いて、Ｕ３がＵ４へグループ鍵を配送する。
【００４７】
本実施形態によれば、鍵合意システム１は、木構造グラフの各ノードのスポンサーとして、少なくとも１台のユーザ端末Ｕを割り当て、この結果、スポンサーに選ばれなかったユーザ端末Ｕに対しては、各階層の二者間で共有された鍵情報によりグループ鍵を配送する。これにより、鍵合意システム１は、二者間の鍵共有プロトコルの実行回数を減らし、処理負荷を低減できる。
【００４８】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、前述した実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、実施形態に記載されたものに限定されるものではない。
【００４９】
鍵合意システム１による鍵合意方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。
【符号の説明】
【００５０】
Ｕ  ユーザ端末
１  鍵合意システム
１０  制御部
１１  秘密情報選択部
１２  鍵情報生成部
１３  秘密情報算出部
１４  グループ鍵生成部
１５  鍵配送部
２０  記憶部
【図１】
2020005079.tif 000004
【図２】
2020005079.tif 000005
【図３】
2020005079.tif 000006
【図４】
2020005079.tif 000007
【図５】
2020005079.tif 000008