(57)【特許請求の範囲】
【請求項１】
通信ネットワーク中で複数のメンバが加入可能なグループを組織し、該グループ内で通信データの暗号化もしくは認証に用いるグループ鍵を共有するとともに、グループ鍵を最上位の根に割り当て、サブグループ鍵を枝の分岐点であるノードに割り当て、各メンバを最下位の部分木の先端である葉に割り当てて、各メンバはグループ鍵及びグループ鍵から自己に至るまでの全てのサブグループ鍵を保持して通信を行う通信方法であって、
あらかじめグループに属する各メンバにはグループ全体の木構造データ及び、グループ鍵、全てのサブグループ鍵を記憶させておき、
新しいメンバの加入を各メンバが加入脱退検知手段により検知すると、
各メンバが、木構造データ更新手段により、加入メンバを所定の規則に従って木構造の葉に割り当て、自己の記憶する木構造データを更新する木構造データ更新ステップ、
各メンバが、キャプテン当否判定手段により、新しい木構造データから所定の規則に従って自己が部分木のキャプテンとなるか否かを判定するキャプテン当否判定ステップ、
該キャプテンが、新鍵生成配布手段により、少なくとも自己の部分木の各メンバとの間で新鍵を生成し配布する新鍵生成配布ステップ
の各ステップを含むことを特徴とする非集中型鍵管理方式を用いた通信方法。
【請求項２】
前記通信方法における新鍵生成配布ステップが、
該加入メンバと各キャプテンとが、新鍵共有手段により、互いに新しいグループ鍵又はサブグループ鍵の生成情報を通信し、新鍵を生成して共有する新鍵共有ステップ、
各キャプテンが、新鍵配布手段により、新鍵を対応する従前のグループ鍵又はサブグループ鍵で暗号化して部分木の各メンバに配布する新鍵配布ステップ
の各ステップからなることを特徴とする
請求項１に記載の非集中型鍵管理方式を用いた通信方法。
【請求項３】
前記通信方法における新鍵生成配布ステップが、
加入メンバと最下位のキャプテンが新鍵を共有すると共に、順次下位のキャプテンが１階層上位のキャプテンと新鍵を共有する新鍵共有ステップ、
各キャプテンが、新鍵配布手段により、新鍵を対応する従前のグループ鍵又はサブグループ鍵で暗号化して部分木の各メンバに配布すると共に、下位のキャプテンから順次に、該キャプテンが属する部分木の新鍵で１階層上位の新鍵を暗号化して加入メンバに送信する新鍵配布ステップ
の各ステップからなることを特徴とする
請求項１に記載の非集中型鍵管理方式を用いた通信方法。
【請求項４】
前記木構造データ更新ステップにおいて、加入メンバを葉に割り当てる所定の規則が、
木構造全体の最下位でかつ最右側のノードにおける最左側の葉、又は最下位でかつ最左側のノードにおける最右側の葉として割り当てる
請求項１ないし３に記載の非集中型鍵管理方式を用いた通信方法。
【請求項５】
前記キャプテン当否判定ステップにおいて、キャプテンとなるか否かを判定する所定の規則が、
ある部分木におけるキャプテンとなるメンバは、その部分木の上位側からみて加入メンバがいる側の枝と反対側の枝の葉のメンバから選択する
請求項１ないし４に記載の非集中型鍵管理方式を用いた通信方法。
【請求項６】
前記木構造が２分木である
請求項１ないし３に記載の非集中型鍵管理方式を用いた通信方法。
【請求項７】
通信ネットワーク中で複数のメンバが加入可能なグループを組織し、該グループ内で通信データの暗号化もしくは認証に用いるグループ鍵を共有するとともに、グループ鍵を最上位の根に割り当て、サブグループ鍵を枝の分岐点であるノードに割り当て、各メンバを最下位の部分木の先端である葉に割り当てて、各メンバはグループ鍵及びグループ鍵から自己に至るまでの全てのサブグループ鍵を保持して通信を行う通信方法であって、
あらかじめグループに属する各メンバにはグループ全体の木構造データ及び、グループ鍵、全てのサブグループ鍵を記憶させておき、
メンバの脱退を各メンバが加入脱退検知手段により検知すると、
各メンバが、キャプテン当否判定手段により、脱退メンバを除いた木構造データから所定の規則に従って自己が部分木のキャプテンとなるか否かを判定するキャプテン当否判定ステップ、
該キャプテンが、新鍵生成配布手段により、少なくとも自己の部分木のメンバ及び他のキャプテンとの間で新鍵を生成し配布する新鍵生成配布ステップ
各メンバが、木構造データ更新手段により、所定の規則に従って脱退メンバの属する部分木のメンバを葉として再割り当てし、自己の記憶する木構造データを更新する木構造データ更新ステップ
の各ステップを含むことを特徴とする非集中型鍵管理方式を用いた通信方法。
【請求項８】
前記通信方法における新鍵生成配布ステップが、
脱退メンバの生じた最下位の部分木のキャプテンと、脱退メンバの属する部分木のその他全てのキャプテンとが、新鍵共有手段により、互いに新しいグループ鍵又はサブグループ鍵の生成情報を通信し、新鍵を生成して共有する新鍵共有ステップ、
各キャプテンが、新鍵配布手段により、生成された新鍵を１階層下位の従前のサブグループ鍵で暗号化して部分木の各メンバに配布すると共に、脱退メンバの生じた最下位の部分木のキャプテンが、新鍵配布手段により、不足している新鍵をその部分木の従前のサブグループ鍵で暗号化して、当該部分木の各メンバに配布する新鍵配布ステップ
の各ステップからなることを特徴とする
請求項７に記載の非集中型鍵管理方式を用いた通信方法。
【請求項９】
前記通信方法における新鍵生成配布ステップが、
脱退メンバの生じた最下位の部分木のキャプテンから順次に、下位のキャプテンが１階層上位のキャプテンと新鍵を共有する新鍵共有ステップ、
各キャプテンが、新鍵配布手段により、自己の部分木の各メンバに新鍵を配布すると共に、脱退メンバの生じた部分木のキャプテンが、新鍵配布手段により、不足している新鍵をその部分木の従前のサブグループ鍵で暗号化して、当該部分木の各メンバに配布する新鍵配布ステップ
の各ステップからなることを特徴とする
請求項７に記載の非集中型鍵管理方式を用いた通信方法。
【請求項１０】
前記キャプテン当否判定ステップにおいて、キャプテンとなるか否かを判定する所定の規則が、
ある部分木におけるキャプテンとなるメンバは、その部分木の上位側からみて加入メンバがいる側の枝と反対側の枝の葉のメンバから選択する
請求項７ないし９に記載の非集中型鍵管理方式を用いた通信方法。
【請求項１１】
前記木構造が２分木である
請求項７ないし１０に記載の非集中型鍵管理方式を用いた通信方法。
【請求項１２】
通信ネットワーク中で複数のメンバが加入可能なグループを組織し、該グループ内で通信データの暗号化もしくは認証に用いるグループ鍵を共有するとともに、グループ鍵を最上位の根に割り当て、サブグループ鍵を枝の分岐点であるノードに割り当て、各メンバを最下位の部分木の先端である葉に割り当てて、各メンバはグループ鍵及びグループ鍵から自己に至るまでの全てのサブグループ鍵を保持して通信を行う通信システムであって、
各メンバとなる端末装置に、
グループ全体の木構造データ及び、グループ鍵、全てのサブグループ鍵を記憶する記憶手段と、
新しいメンバの加入又はメンバの脱退を検知する加入脱退検知手段と、
加入メンバを所定の規則に従って木構造の葉に割り当て、自己の記憶する木構造データを更新するか、又は所定の規則に従って脱退メンバの属する部分木のメンバを葉として再割り当てし、自己の記憶する木構造データを更新するかの少なくともいずれかの処理を行う木構造データ更新手段と、
木構造データから所定の規則に従って自己が部分木のキャプテンとなるか否かを判定するキャプテン当否判定手段と、
キャプテンとなった場合に、少なくとも自己の部分木のメンバとの間で新鍵を生成し配布する新鍵生成配布手段と
を備えて構成することを特徴とする
非集中型鍵管理方式を用いた通信システム。
【請求項１３】
前記通信システムにおける端末装置の新鍵生成配布手段が、
該加入メンバ及びキャプテン間で、互いに新しいグループ鍵又はサブグループ鍵の生成情報を通信し、新鍵を生成して共有する新鍵共有手段と、
キャプテンの時に、新鍵を対応する従前のグループ鍵又はサブグループ鍵で暗号化して部分木の各メンバに配布する新鍵配布手段と
からなる請求項１２に記載の非集中型鍵管理方式を用いた通信システム。
【請求項１４】
前記通信システムにおける端末装置の新鍵生成配布手段が、
加入メンバと最下位のキャプテンが新鍵を共有すると共に、順次下位のキャプテンが１階層上位のキャプテンと新鍵を共有する新鍵共有手段と、
キャプテンの時に、新鍵を対応する従前のグループ鍵又はサブグループ鍵で暗号化して部分木の各メンバに配布すると共に、下位のキャプテンから順次に、該キャプテンが属する部分木の新鍵で１階層上位の新鍵を暗号化して加入メンバに送信する新鍵配布手段と
からなる請求項１２に記載の非集中型鍵管理方式を用いた通信システム。
【請求項１５】
前記通信システムにおける端末装置の新鍵生成配布手段が、
脱退メンバの生じた最下位の部分木のキャプテンと、脱退メンバの属する部分木のその他全てのキャプテンとが、互いに新しいグループ鍵又はサブグループ鍵の生体情報を通信し、新鍵を生成して共有する新鍵共有手段と、
キャプテンの時に、生成された新鍵を１階層下位の従前のサブグループ鍵で暗号化して部分木の各メンバに配布すると共に、脱退メンバの生じた最下位の部分木のキャプテンが、不足している新鍵をその部分木の従前のサブグループ鍵で暗号化して、当該部分木の各メンバに配布する新鍵配布手段と
からなる請求項１２に記載の非集中型鍵管理方式を用いた通信システム。
【請求項１６】
前記通信システムにおける端末装置の新鍵生成配布手段が、
脱退メンバの生じた最下位の部分木のキャプテンから順次に、下位のキャプテンが１階層上位のキャプテンと新鍵を共有する新鍵共有手段と、
キャプテンの時に、新鍵配布手段により、自己の部分木の各メンバに新鍵を配布すると共に、脱退メンバの生じた部分木のキャプテンが、不足している新鍵をその部分木の従前のサブグループ鍵で暗号化して、当該部分木の各メンバに配布する新鍵配布手段と
からなる請求項１２に記載の非集中型鍵管理方式を用いた通信システム。
【請求項１７】
前記木構造データ更新手段で用いる加入メンバを葉に割り当てる所定の規則が、
木構造全体の最下位でかつ最右側のノードにおける最左側の葉、又は最下位でかつ最左側のノードにおける最右側の葉として割り当てる
請求項１２ないし１６に記載の非集中型鍵管理方式を用いた通信システム。
【請求項１８】
前記キャプテン当否判定手段で用いるキャプテンとなるか否かを判定する所定の規則が、
ある部分木におけるキャプテンとなるメンバは、その部分木の上位側からみて加入メンバがいる側の枝と反対側の枝の葉のメンバから選択する
請求項１２ないし１７に記載の非集中型鍵管理方式を用いた通信システム。
【請求項１９】
前記木構造が２分木である
請求項１２ないし１８に記載の非集中型鍵管理方式を用いた通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信ネットワークにおけるグループ内のメンバでグループ鍵を共有し、該鍵で暗号化した通信を行う通信方法及びシステムに関し、特にグループ鍵を非集中型鍵管理方式により管理する構成に係る。
【背景技術】
【０００２】
近年、携帯電話の普及を端緒にしてモバイルセキュリティ技術の研究開発、さらには製品化が盛んとなってきている。また、２Ｇや３Ｇのセルラ網をはじめ、様々な特質を持った無線をシームレスに統合する次世代の移動体通信ネットワークの研究が進んでおり、例えば本件発明者らによる非特許文献１に開示される。
この次世代通信ネットワークは、利用するモバイルサービスに合わせて自動的に最適な無線が選ばれるといった機能を持っており、非特許文献２に開示されているように様々な無線が柔軟に同ネットワークにプラグインできるようなアーキテクチャが想定される。【０００３】
【非特許文献１】M. Kuroda, M. Inoue, A. Okubo, T. Sakakura, K.Shimizu, and F. Adachi, “Scalable Mobile Ethernet and Fast Vertical Handover,” Proc. IEEE Wireless Communications and Networking Conference 2004,Mar. 2004.
【非特許文献２】M. Yoshida, M. Kuroda, S. Kiyomoto, and T. Tanaka,“A SecureService Architecture for Beyond 3G WirelessNetwork,” Proc. 6th International Symposium onWireless Personal Multimedia Communications，Vol.2, pp. 579-583, 2003.
【０００４】
次世代の移動体通信ネットワークでは、従来のクライアント・サーバ型のサービスだけでなく、複数の利用者が多様な携帯端末を使って動的なグループを形成し，メンバ同士が安全に情報共有を行えるグループ型のサービスにも期待が寄せられている。このような安全なグループ通信の実現に必要な機能には、データの守秘や完全性の検証、送信元の認証、メンバ管理などが挙げられるが、グループのメンバが共有するグループ鍵の管理もまた非常に重要な研究課題である。【０００５】
メンバの加入・脱退が起こり得る動的なグループでは、新しくグループに加入するメンバ（以下、加入メンバと呼ぶ。）が加入以前の情報にアクセスできないよう、またグループから脱退するメンバ（以下、脱退メンバと呼ぶ。）が脱退以後の情報にアクセスできないよう、グループ鍵を更新する必要がある。
グループ鍵の更新機能を有する鍵管理方式は、鍵を集中管理するサーバや無線基地局などを必要とする方式（非特許文献３ないし１１に開示）と、グループのメンバ全員が協力してＤＨ鍵共有を行いグループ鍵を更新するContributory Key Agreement と呼ばれる方式（非特許文献１２ないし１６に開示）とに大別できる。【０００６】
なお、ＤＨ鍵共有は、周知の如くディフィー氏及びヘルマン氏によって開発された鍵共有方式であり、該鍵共有方式では、離散対数問題を利用して、秘密鍵そのものではなく、乱数と秘密鍵から生成した公開情報（公開鍵）を送受信する。これにより、通信内容を第三者に盗聴されても、直ちに秘密鍵を知られることはなく、安全に鍵情報を共有することができる方式である。【０００７】
【非特許文献３】H. Harney, C. Muckenhirn, and T. Rivers, “Group Key Management Protocol (GKMP) Specification,” IETF, RFC 2093, 1997.
【非特許文献４】H. Harney, C. Muckenhirn, and T. Rivers, “Group Key Management Protocol (GKMP) Architecture,” IETF, RFC 2094, 1997.
【非特許文献５】D. Wallner, E. Harder, R. Agee, “Key Management for Multicast: Issues and Architectures,” IETF, RFC 2627, 1999.
【非特許文献６】C. K. Wong, M. Gouda, and S. Lam, “Secure Group Communication Using Key Graphs,” IEEE/ACM Trans. on Networking, Vol. 8, No. 1, pp. 16-30, 2000.
【非特許文献７】R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas, “Multicast Security: A Taxonomy and Efficient Constructions,” Proc.IEEE Infocom’99, Vol.2, pp. 708-716, 1999.
【非特許文献８】D.A. McGrew, and A.T. Sherman, “Key Establishment in Large Dynamic Groups Using One-Way Function Trees,” IEEE Trans. on Software Engineering, Vol.29, No. 5, pp. 444-458, 2003.
【非特許文献９】A. Perrig, D. Song, and J.D. Tygar, “ELK: A NewProtocol for Efficient Large-Group Key Distribution,” Proc. IEEE Security and Privacy Symposium, pp. 247-262, 2001.
【非特許文献１０】A. Perrig, R. Szewczyk, V. Wen, D. Culler, and J. D. Tygar, “SPINS: Security Protocols for Sensor Networks,” Proc. Mobile Computing and Networking 2001, pp. 189-199, 2001.
【非特許文献１１】Y. W. Law, R. Corin, S. Etalle, and P. H. Hartel, “A Formally Verified Decentralized Key Management Architecture for Wireless Sensor Networks,” Proc. Personal Wireless Communications 2003, pp. 27-39, 2003.
【非特許文献１２】D. G. Steer, L. Strawczynski, W. Diffie, and M.Wiener, “A Secure Audio Teleconference System,”Proc. Advances in Cryptology-CRYPTO ’88, pp. 520-528, 1988.
【非特許文献１３】M. Burmester, and Y. Desmedt, “A Secure and Efficient Conference Key Distribution System,” Proc. Advances in Cryptology-EUROCRYPT ’94, pp. 275-286,1994.
【非特許文献１４】M. Steiner, G. Tsudik, and M. Waidner, “Key Agreement in Dynamic Peer Groups,” IEEE Trans. on Parallel and Distributed Systems, Vol. 11, No. 8, pp 769-780,2000.
【非特許文献１５】J. Alves-Foss, “An Efficient Secure Authenticated Group Key Exchange Algorithm for Large and Dynamic Groups,” Proc. 23rd National Information Systems Security Conference, pp. 254-266, 2000.
【非特許文献１６】Y. Kim, A. Perrig, and G. Tsudik, “Simple and Fault-Tolerant Key Agreement for Dynamic Collaborative Groups,” ACM Conference on Computer and Communications Security 2000, pp. 235-244, 2000.
【０００８】
前者は鍵を集中管理するエンティティがSingle Point of Failure となる可能性を持ち、またAd Hoc ネットワークなどのサーバレスなグループ通信には応用が難しい。
後者はグループ鍵更新の際にグループの全てのメンバがベキ乗剰余演算を行う必要があり、計算力の乏しい携帯端末などを含むグループ通信には不向きである。【０００９】
ところで、従来のグループ鍵の更新方法としては、Logical Key Hierarchy（LKH）（非特許文献５及び６に開示）として知られる、木構造で鍵を管理する方式が非常に効率的である。
しかし、このような鍵を集中管理する方法では上記の問題がある他、メンバの加入時・脱退時によりコストの少ない鍵管理方式が望まれている。【００１０】
なお、鍵管理サーバを用いた特許文献としては、特許文献１７や特許文献１８に開示されるような技術が公知であり、特許文献１７では鍵管理サーバが一括管理する方式を開示しており、その際にはグループが大規模であると鍵の更新にかかるコストが大きくなる問
題がある。また、特許文献１８はサブグループを管理するサーブグループ鍵管理サーバを別に設けるが、あくまでも鍵を管理するサーバであって、木構造の上位にあるサーバが管理する方法である。【００１１】
【特許文献１７】特開平9-319673号公報
【特許文献１８】特開2004-023237号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は上記従来技術に鑑みて創出されたものであって、鍵管理サーバを使うことなく、グループのメンバだけで木構造の鍵管理を実現する非集中型鍵管理方式を提案し、安全なグループ通信に寄与する通信方法とシステムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、上記の課題を解決するために、次のような通信方法を提供する。
すなわち、請求項１に記載の発明は、通信ネットワーク中で複数のメンバが加入可能なグループを組織し、該グループ内で通信データの暗号化もしくは認証に用いるグループ鍵を共有するとともに、グループ鍵を最上位の根に割り当て、サブグループ鍵を枝の分岐点であるノードに割り当て、各メンバを最下位の部分木の先端である葉に割り当てて、各メンバはグループ鍵及びグループ鍵から自己に至るまでの全てのサブグループ鍵を保持して通信を行う通信方法である。
そして、あらかじめグループに属する各メンバにはグループ全体の木構造データ及び、グループ鍵、全てのサブグループ鍵を記憶させておき、新しいメンバの加入を各メンバが加入脱退検知手段により検知すると次の各ステップを含む。【００１４】
（１）  各メンバが、木構造データ更新手段により、加入メンバを所定の規則に従って木構造の葉に割り当て、自己の記憶する木構造データを更新する木構造データ更新ステップ。
（２）  メンバが、キャプテン当否判定手段により、新しい木構造データから所定の規則に従って自己が部分木のキャプテンとなるか否かを判定するキャプテン当否判定ステップ。
（３）  該キャプテンが、新鍵生成配布手段により、少なくとも自己の部分木の各メンバとの間で新鍵を生成し配布する新鍵生成配布ステップ。【００１５】
請求項２に記載の発明は、上記請求項１の通信方法における新鍵生成配布ステップが、該加入メンバと各キャプテンとが、新鍵共有手段により、互いに新しいグループ鍵又はサブグループ鍵の生成情報を通信し、新鍵を生成して共有する新鍵共有ステップと、各キャプテンが、新鍵配布手段により、新鍵を対応する従前のグループ鍵又はサブグループ鍵で暗号化して部分木の各メンバに配布する新鍵配布ステップとの各ステップからなることを特徴とする。【００１６】
請求項３に記載の発明は、上記請求項１の通信方法における新鍵生成配布ステップが、加入メンバと最下位のキャプテンが新鍵を共有すると共に、順次下位のキャプテンが１階層上位のキャプテンと新鍵を共有する新鍵共有ステップと、各キャプテンが、新鍵配布手段により、新鍵を対応する従前のグループ鍵又はサブグループ鍵で暗号化して部分木の各メンバに配布すると共に、下位のキャプテンから順次に、該キャプテンが属する部分木の新鍵で１階層上位の新鍵を暗号化して加入メンバに送信する新鍵配布ステップとの各ステップからなることを特徴とする。【００１７】
請求項４に記載の発明は、上記請求項１ないし３に記載の発明の構造データ更新ステッ
プにおいて、加入メンバを葉に割り当てる所定の規則が、木構造全体の最下位でかつ最右側のノードにおける最左側の葉、又は最下位でかつ最左側のノードにおける最右側の葉として割り当てることを特徴とする。【００１８】
請求項５に記載の発明は、上記請求項１ないし３に記載の発明のキャプテン当否判定ステップにおいて、キャプテンとなるか否かを判定する所定の規則が、ある部分木におけるキャプテンとなるメンバは、その部分木の上位側からみて加入メンバがいる側の枝と反対側の枝の葉のメンバから選択することを特徴とする。【００１９】
請求項６に記載の発明は、上記木構造が２分木であることを特徴とするものである。【００２０】
請求項７に記載の発明は、メンバの脱退を各メンバが加入脱退検知手段により検知すると、各ステップを含むことを特徴とする。
（１）  各メンバが、キャプテン当否判定手段により、脱退メンバを除いた木構造データから所定の規則に従って自己が部分木のキャプテンとなるか否かを判定するキャプテン当否判定ステップ。
（２）  該キャプテンが、新鍵生成配布手段により、少なくとも自己の部分木のメンバ及び他のキャプテンとの間で新鍵を生成し配布する新鍵生成配布ステップ。
（３）  各メンバが、木構造データ更新手段により、所定の規則に従って脱退メンバの属する部分木のメンバを葉として再割り当てし、自己の記憶する木構造データを更新する木構造データ更新ステップ。【００２１】
請求項８に記載の発明は、前記通信方法における新鍵生成配布ステップが、脱退メンバの生じた最下位の部分木のキャプテンと、脱退メンバの属する部分木のその他全てのキャプテンとが、新鍵共有手段により、互いに新しいグループ鍵又はサブグループ鍵の生成情報を通信し、新鍵を生成して共有する新鍵共有ステップと、各キャプテンが、新鍵配布手段により、生成された新鍵を１階層下位の従前のサブグループ鍵で暗号化して部分木の各メンバに配布すると共に、脱退メンバの生じた最下位の部分木のキャプテンが、新鍵配布手段により、不足している新鍵をその部分木の従前のサブグループ鍵で暗号化して、当該部分木の各メンバに配布する新鍵配布ステップとの各ステップからなることを特徴とする。【００２２】
請求項９に記載の発明は、前記通信方法における新鍵生成配布ステップが、脱退メンバの生じた最下位の部分木のキャプテンから順次に、下位のキャプテンが１階層上位のキャプテンと新鍵を共有する新鍵共有ステップと、各キャプテンが、新鍵配布手段により、自己の部分木の各メンバに新鍵を配布すると共に、脱退メンバの生じた部分木のキャプテンが、新鍵配布手段により、不足している新鍵をその部分木の従前のサブグループ鍵で暗号化して、当該部分木の各メンバに配布する新鍵配布ステップとの各ステップからなることを特徴とする。【００２３】
請求項１０に記載の発明は、前記キャプテン当否判定ステップにおいて、キャプテンとなるか否かを判定する所定の規則が、ある部分木におけるキャプテンとなるメンバは、その部分木の上位側からみて加入メンバがいる側の枝と反対側の枝の葉のメンバから選択することを特徴とするものである。【００２４】
請求項１１に記載の発明は、請求項７ないし１０の発明において木構造が２分木とするものである。【００２５】
本発明は、次のような通信システムを提供することができる。
すなわち、請求項１２に記載の発明によれば、通信ネットワーク中で複数のメンバが加
入可能なグループを組織し、該グループ内で通信データの暗号化もしくは認証に用いるグループ鍵を共有するとともに、グループ鍵を最上位の根に割り当て、サブグループ鍵を枝の分岐点であるノードに割り当て、各メンバを最下位の部分木の先端である葉に割り当てて、各メンバはグループ鍵及びグループ鍵から自己に至るまでの全てのサブグループ鍵を保持して通信を行う通信システムを提供する。【００２６】
そして、各メンバとなる端末装置に、次の各手段を備える。
（１）  グループ全体の木構造データ及び、グループ鍵、全てのサブグループ鍵を記憶する記憶手段。
（２）  新しいメンバの加入又はメンバの脱退を検知する加入脱退検知手段。
（３）  加入メンバを所定の規則に従って木構造の葉に割り当て、自己の記憶する木構造データを更新するか、又は所定の規則に従って脱退メンバの属する部分木のメンバを葉として再割り当てし、自己の記憶する木構造データを更新するかの少なくともいずれかの処理を行う木構造データ更新手段。
（４）  木構造データから所定の規則に従って自己が部分木のキャプテンとなるか否かを判定するキャプテン当否判定手段。
（５）  キャプテンとなった場合に、少なくとも自己の部分木のメンバとの間で新鍵を生成し配布する新鍵生成配布手段。【００２７】
請求項１３に記載の発明によれば、通信システムにおける端末装置の新鍵生成配布手段が、加入メンバ及びキャプテン間で、互いに新しいグループ鍵又はサブグループ鍵の生成情報を通信し、新鍵を生成して共有する新鍵共有手段と、キャプテンの時に、新鍵を対応する従前のグループ鍵又はサブグループ鍵で暗号化して部分木の各メンバに配布する新鍵配布手段とからなることを特徴とする。【００２８】
請求項１４に記載の発明によれば、通信システムにおける端末装置の新鍵生成配布手段が、加入メンバと最下位のキャプテンが新鍵を共有すると共に、順次下位のキャプテンが１階層上位のキャプテンと新鍵を共有する新鍵共有手段と、キャプテンの時に、新鍵を対応する従前のグループ鍵又はサブグループ鍵で暗号化して部分木の各メンバに配布すると共に、下位のキャプテンから順次に、該キャプテンが属する部分木の新鍵で１階層上位の新鍵を暗号化して加入メンバに送信する新鍵配布手段とからなることを特徴とする。【００２９】
請求項１５に記載の発明は、前記の通信システムにおける端末装置の新鍵生成配布手段が、脱退メンバの生じた最下位の部分木のキャプテンと、脱退メンバの属する部分木のその他全てのキャプテンとが、互いに新しいグループ鍵又はサブグループ鍵の生成情報を通信し、新鍵を生成して共有する新鍵共有手段と、キャプテンの時に、生成された新鍵を１階層下位の従前のサブグループ鍵で暗号化して部分木の各メンバに配布すると共に、脱退メンバの生じた最下位の部分木のキャプテンが、不足している新鍵をその部分木の従前のサブグループ鍵で暗号化して、当該部分木の各メンバに配布する新鍵配布手段とからなるものである。【００３０】
請求項１６に記載の発明は、通信システムにおける端末装置の新鍵生成配布手段が、脱退メンバの生じた最下位の部分木のキャプテンから順次に、下位のキャプテンが１階層上位のキャプテンと新鍵を共有する新鍵共有手段と、キャプテンの時に、新鍵配布手段により、自己の部分木の各メンバに新鍵を配布すると共に、脱退メンバの生じた部分木のキャプテンが、不足している新鍵をその部分木の従前のサブグループ鍵で暗号化して、当該部分木の各メンバに配布する新鍵配布手段とからなるものである。【００３１】
請求項１７に記載の発明は、請求項１２ないし１６の通信システムにおいて、木構造データ更新手段で用いる加入メンバを葉に割り当てる所定の規則が、木構造全体の最下位で
かつ最右側のノードにおける最左側の葉、又は最下位でかつ最左側のノードにおける最右側の葉として割り当てることを特徴とするものである。【００３２】
請求項１８に記載の発明は、上記通信システムにおいてキャプテン当否判定手段で用いるキャプテンとなるか否かを判定する所定の規則が、ある部分木におけるキャプテンとなるメンバは、その部分木の上位側からみて加入メンバがいる側の枝と反対側の枝の葉のメンバから選択することを特徴とするものである。【００３３】
請求項１９に記載の発明は、請求項１２ないし１８の通信システムにおいて、前記木構造が２分木であることを特徴とする。
【発明の効果】
【００３４】
以上の発明により次の効果を奏する。
すなわち、請求項１ないし６に記載の非集中型鍵管理方式を用いた通信方法によれば、メンバの加入時にサーバレスで安全にグループ鍵を共有する鍵管理方式を提供することができ、コストの抑制にも寄与する。【００３５】
請求項７ないし１１に記載の非集中型鍵管理方式を用いた通信方法によれば、メンバの脱退時にサーバレスで安全にグループ鍵を共有する鍵管理方式を提供することができ、コストの抑制にも寄与する。【００３６】
請求項１２ないし１９に記載の発明によれば、上記通信方法を実装し、非集中型鍵管理方式を用いた通信システムを提供することができる。
【図面の簡単な説明】
【００３７】
【図１】本発明に係る通信システムを構成する端末装置の構成図である。
【図２】ＦＤＬＫＨのノード及びメンバの関係を説明する説明図である。
【図３】ＦＤＬＫＨのノード及びメンバの関係を一般化した説明図である。
【図４】本発明の方式によるメンバ加入時の処理を説明する説明図である。
【図５】本発明の方式によるメンバ脱退時の処理を説明する説明図である。
【図６】本発明の方式によるメンバ加入時の処理の流れ図である。
【図７】本発明の方式によるメンバ脱退時の処理の流れ図である。
【図８】本発明の第２の実施例に係る加入プロトコルの流れ図である。
【図９】本発明の第３の実施例に係る加入プロトコルの流れ図である。
【図１０】本発明の第４の実施例に係る脱退プロトコルの流れ図である。
【図１１】本発明の第５の実施例に係る脱退プロトコルの流れ図である。
【図１２】ＦＤＬＫＨ(dedicated方式)のメンバ加入において、メンバ数に対する共通鍵暗号系のコストの変化を示すグラフである。
【図１３】ＦＤＬＫＨ(distributed方式)のメンバ加入において、メンバ数に対する共通鍵暗号系のコストの変化を示すグラフである。
【図１４】ＦＤＬＫＨ(dedicated方式)のメンバ脱退において、メンバ数に対する共通鍵暗号系のコストの変化を示すグラフである。
【図１５】ＦＤＬＫＨ(distributed方式)のメンバ脱退において、メンバ数に対する共通鍵暗号系のコストの変化を示すグラフである。
【符号の説明】
【００３８】
７０    木構造データ更新ステップ
７１    キャプテン選択ステップ
７２    新鍵共有ステップ
７３    新鍵配布ステップ
【発明を実施するための最良の形態】
【００３９】
以下、本発明の実施形態を、図面に示す実施例を基に説明する。なお、実施形態は下記に限定されるものではない。
【実施例１】
【００４０】
図１は本発明に係る通信システムにおける端末装置の構成図である。図示のように、端末装置（１）にはＣＰＵ（１０）と、ネットワーク通信を司るネットワークアダプタ（２０）、データを記憶するメモリ（２１）が付設されている。このような構成は、公知のパーソナルコンピュータや、携帯電話端末、携帯情報通信端末などに備えられており、本発明はこれらの装置に実装可能である。【００４１】
そして、ＣＰＵ（１０）では、ネットワーク上でグループを構成する他のメンバの加入や脱退を検知する加入脱退検知部（１１）による処理や、グループ全体で鍵を管理するための木構造データを更新処理する木構造データ更新部（１２）による処理の他、本発明の方法を実現するキャプテン当否判定部（１３）、新鍵共有部（１４）、新鍵配布部（１５）の各処理を行う。【００４２】
なお、本発明において鍵を生成及び共有する処理については、ネットワーク通信における公開鍵暗号系を用いた暗号鍵の生成及び共有処理が周知であり、これらの周知技術を適用することができる。【００４３】
次に、本発明に係るグループ鍵の概念につき説述する。グループ鍵はグループの全てのメンバが共有する共通鍵暗号の鍵であり、グループを流れる通信はこのグループ鍵によって暗号化される。
メンバの加入・脱退が起こった際にはグループ鍵の更新が必要となる。グループ鍵の更新方法としてはLogical Key Hierarchy（LKH）として知られる、木構造で鍵を管理する方式が非常に効率的であるが、これは集中型の鍵管理サーバを前提に設計されている。【００４４】
そこで、本発明では鍵管理サーバを使うことなく、グループのメンバだけで木構造の鍵管理を実現する非集中型鍵管理方式を提案する。以下、提案方式をFDLKH（Fully Decentralized Key Management Scheme on Logical Key Hierarchy）と呼ぶこととする。
LKHの本質は、グループのメンバを論理的な木のリーフに割り当て、部分木ごとのサブグループグループに分割し、管理サーバがサブグループごとにグループ鍵更新のために使われる鍵を配布することで、１回のグループ鍵更新にかかる暗号化のコストを、メンバ数nに対してO(n)からO(log n)に抑えることにある。【００４５】
本発明に係るFDLKHでは、２分木を用いてメンバをサブグループに分割し、鍵管理サーバの代わりに、各サブグループから１メンバずつが代表として選出され、ＤＨ鍵共有と鍵配布を受け持つ。
これによってLKHと同様に暗号化のコストはO(log n)となり、システム全体の鍵の数はLKHに比べて約半分になる効果を有する。【００４６】
次に、図２はFDLKHで用いる２分木の一部を示す説明図である。木の各ノード（３０）〜（３３）は、木のレベル（３４）l（l=0,1,2,・・・）と、そのレベル（３４）における位置m（0 m 2l-1）を用いて <l,m>と表す。従って、レベル１の位置０（左端）のノード（３１）は<1,0>である。【００４７】
グループのメンバは、子を持たないノード（つまり葉、リーフ）に割り当てられる。以下、このような割り当てを「メンバがノードを占有する」と表現する。ノード<l,m>を占
有するメンバをM<l,m>と表す。例えば、ノード<4,4>の葉となるメンバはM<5,8>（３５）
とM<5,9>（３６）である。【００４８】
メンバに占有されていないノードには鍵が割り当てられ、ノード<l,m>に割り当てられる鍵をK<l,m>と表す。
このK<l,m>は、ノード<l,m>を根とする部分木T<l,m>に属するメンバ間で共有される。
例えば、図２におけるノード<4,4>（３３）を根とする部分木T<4,4>（３７）に属するメンバ間で共有される鍵はK<4,4>であり、本発明ではこれをサブグループ鍵と呼んでいる。【００４９】
なお、K<0,0>は、全てのメンバが共有し、すなわちこれがグループ鍵である。本発明では最も上位の鍵であるグループ鍵と、各階層におけるサブグループ鍵をメンバが保持することになる。
すなわち、メンバM<5,8>（３５）とM<5,9>（３６）が部分木T<4,4>に属して鍵K<4,4>を共有している他、これらのメンバは図示しない部分木T<3,2>，T<2,1>，T<1,0>，T<0,0>にも属するので、両メンバが持つ鍵は、K<4,4>，K<3,2>，K<2,1>，K<1,0> ，K<0,0>の計5 つである。
つまり、あるメンバは、その親ノード（１レベル上位のノード）から根ノード<0,0>（最上位のノード）に到る経路上の全ての鍵を持つ。【００５０】
図３は、ノード<l,m>を占有するメンバM<l,m>（４０）を基点として２分木を一般化したものである。M<l,m>の親ノードは<l-1,[m/2]>（４１）で表され、兄弟メンバ（同じ親ノードに属するメンバ）はM<l,m+(-1)m>（４２）である。
親ノードから根ノードに到る全ての祖先ノード（４３）は<l-i,[m/2i]>(i=1,・・,l)と一般化できる。よって、M<l,m>が属する部分木と、所有する鍵は、それぞれT<l-i,[m/2i]>、K<l-i,[m/2i]>と表せる。【００５１】
本発明において、グループにメンバの加入・脱退が起こった際には、鍵の更新が必要なノードを根とする部分木ごとに１人のメンバを代表として選び、それらの代表が鍵更新の処理を受け持つようにした。これにより、従来鍵管理サーバを用いていた鍵管理を代表のメンバに分散して処理することができる。
このようなメンバを「キャプテン」と呼ぶこととし、部分木T<l,m>を代表するキャプテンをC<l,m>と表す。【００５２】
キャプテンはメンバの加入・脱退が起こった際に、鍵の操作が必要となるノードを根とする部分木を代表して、鍵共有と鍵配布の処理を受け持つ。メンバ加入の際には部分木の各キャプテンと加入メンバがＤＨ鍵共有を行い、メンバ脱退の際にはキャプテン同士がＤＨ鍵共有を行う。
その結果共有した鍵を各キャプテンが部分木のメンバに配布する。M<l,m>が加入もしくは脱退する場合、鍵の操作が必要となるノードはl個あり、ゆえにl人のメンバがキャプテンとして選択される。【００５３】
ある部分木のキャプテンとなるメンバは、その部分木の根ノードからみて、加入・脱退メンバがいる側の枝と逆側の枝の子孫から選択される。
図４はメンバM<3,3>（５０）が加入する例であり、部分木T<2,1>のキャプテンC<2,1>にはノード<2,1>の逆側の枝の子孫であるメンバM<3,2>（５１）が選択される。同様に、部分木T<1,0>のキャプテンC<1,0>にはメンバM<3,0>（５２）が、部分木（木構造全体）T<0,0>のキャプテンC<0,0>にはメンバM<3,4>（５３）が選択される。【００５４】
同様に、図５はメンバM<3,0>（６０）が脱退する例であり、メンバM<3,1>（６１），M<3,3>（６２），M<2,3>（６３）が、それぞれキャプテンC<2,0>，C<1,0>，C<0,0>となる。
次に、部分木にキャプテンの候補となるメンバが複数いる場合を考える。例えば、図４のT<1,0>ではM<3,0>（５２）とM<3,1>（５４）が、T<0,0>ではM<3,4>（５３）とM<3,5>（５５）とM<2,3 >（５６）がキャプテンの候補である。【００５５】
本発明において、各メンバはキャプテン当否判定部（１３）で自己がキャプテンとなるか否かを共通の選択アルゴリズムにより判定する。
最も簡便な選択アルゴリズムとしては、各メンバがメモリ（２１）に常時記憶している木構造データを参照し、上記に従って、自己がその部分木の根ノードからみて、加入・脱退メンバがいる側の枝と逆側の枝の子孫であるか、子孫が複数ある場合には左端のメンバであるか否かを順に判定し、いずれも満たす場合に、自己をその部分木のキャプテンと確定する。【００５６】
この方法は、部分木ごとにキャプテンとなるメンバを固定する方法であり、メンバの計算力に格差があり、高い計算力を持つメンバに処理をある程度集中させたいようなグループに向いている。そこで例えば、計算力に従ってあらかじめメンバに序列をつけておき、自己の序列が最も高い場合に自己をキャプテンと確定するようにしてもよい。【００５７】
また別の方法は、キャプテンの候補となるメンバの間で、キャプテンの役割を持ち回りする変動型の方法である。この方法は、メンバが互いに対等な関係で、処理の負荷を平坦化したいようなグループに向いている。従って、部分木内で例えば左から右に順にキャプテンを持ち回らせるなどの選択アルゴリズムを用いることができる。【００５８】
本発明の非集中型鍵管理方式では、メンバが加入又は脱退する際に、次のように木構造データを更新する。木構造データの更新は、ＣＰＵ（１０）の木構造データ更新部（１２）においてメモリ（２１）のデータを書き換える方法で処理される。【００５９】
すなわち、本発明においてグループの全てのメンバは、２分木の情報を共有している。メンバの加入・脱退が起こると、メンバ各々が２分木の形状を更新する。
図４に示すメンバ加入の際、加入メンバ（５０）は２分木の中で最もレベルが小さく、最も左側のノード（５７）の右の子として加入する。これは本実施例における規則であり、逆に最も右側のノード<2,3>の左の子（右の子でも良い）として加入するなど、任意の所定の規則を用いることができる。
図４では加入メンバはM<3,3>となる。M<3,3>の加入に伴い、ノード<2,1>を占有していたM<2,1>が１つ下層に移動し、ノード<2,1>の左の子M<3,2>となる。【００６０】
メンバ脱退は２分木の任意のノードで起こり得る。図５ではM<3,0>（６０）の脱退に伴い、M<3,0>（６０）の兄弟メンバであったM<3,1>（６１）が１つ上層に移動し、親ノード<2,0>を占有してM<2,0>（６４）となる。脱退メンバの兄弟ノードがメンバに占有されていない（例えば図５のM<2,3>（６３）が脱退する）場合は、その兄弟ノードを根とする部分木ごと上層に移動させ、部分木の子孫ノードの名前を更新する。つまり、T<2,2>をT<1,1>とする。【００６１】
上述の通り、各メンバは加入脱退検知部（１１）でメンバの加入や脱退をネットワークから検知すると、上記の規則に従って、加入メンバの場合には２分木の中で最もレベルが小さく、最も左側のノード（５７）の右の子として加入させて木構造データを更新し、メンバが脱退する場合には、兄弟メンバを１階層上位に移動させたり、兄弟ノードがメンバに占有されていない時には、その兄弟ノードを根とする部分木ごと上層に移動させたりして木構造データを更新する。【００６２】
なお、加入メンバに対しては、加入メンバの親ノードを根とする部分木のキャプテンが
２分木の情報を送信し、加入メンバはメモリ（２１）に記憶する。
また、加入前のメンバ数が２のベキ数で、完全２分木を形成している場合は、根ノード<0,0>を新たに作り、元の根ノードを<1,0>に移して、<1, 0>以下の子孫ノードの名前を更新し、加入メンバを根ノードの右の子M<1,1>とするようにしてもよい。【００６３】
本発明では、従来の鍵管理サーバを用いることなく、キャプテンがグループ鍵及びサブグループ鍵を生成して各メンバに配布することを特徴とし、新鍵生成配布手段により生成及び配布の態様は任意に定めることができる。
メンバの加入・脱退の際にはグループ鍵を更新するために、２分木のノードに割り当てられる鍵の生成や変更あるいは破棄が行われる。これら３つの処理を総称して「鍵の操作」と呼ぶ。【００６４】
メンバの加入・脱退の際に鍵の操作が必要となるノードは、加入もしくは脱退メンバの親ノードから根ノードに到る全ての祖先ノードである。図４のメンバ加入の例では<2,1>
，<1,0>，<0,0>が鍵の操作の必要なノードである。ここで、ノード<2,1>の鍵は新たに生成される。
図５のメンバ脱退の例では<2,0>，<1,0>，<0,0>が鍵の操作の必要なノードである。ここで、ノード<2,0>の鍵は破棄される。【００６５】
鍵の破棄は他のメンバとの協調を必要とせず、破棄すべき鍵を持つメンバがそれぞれ処理を行う。鍵の生成・変更に関しては他のメンバとの協調が必要である。一般にM<l,m>がグループに加入する際、鍵の生成・変更が必要なノードは<l-i,[m/2i]>(i=1,・・,l)と表せる。一方、M<l,m>がグループから脱退する際に、鍵の変更が必要なノードは、鍵が破棄される親ノードを除いた<l-j,[m/2j]>(j=1,・・,l)と表せる。【００６６】
以下に実施態様としてメンバ加入時の２例、メンバ脱退時の２例をそれぞれ実施例２ないし５に説述する。
【実施例２】
【００６７】
まず、メンバ加入時の新鍵生成配布手段を、ＣＰＵ（１０）の新鍵共有部（１４）と新鍵配布部（１５）とで構成し、図６に示す加入プロトコルを処理する実施例を説述する。（本方式をFDLKHのdedicated方式と呼ぶ。）
上述した通り、メンバ（５０）が加入する場合、加入脱退検知部（１１）で検知すると、各メンバにおいて木構造データ更新部（１２）が木構造データの更新処理（７０）を行う。次いで、キャプテン当否判定部（１３）の処理を各メンバが行うことにより、木構造におけるキャプテンが選択（７１）される。
加入メンバ（５０）には、キャプテン（５１）が木構造データを送信する。【００６８】
そして、新鍵共有処理（７２）に進む。ここで、新鍵の生成・変更にはＤＨ鍵共有を用いる。メンバ加入の際には加入メンバと各キャプテンがＤＨ鍵共有を行う。各キャプテンは、ＤＨ鍵共有で共有した値を暗号学的に安全な一方向性ハッシュ関数hに入力し、その結果得られた出力を部分木の根ノードに割り当てる共通鍵暗号の鍵とする。【００６９】
図４において、加入メンバM<3,3>と、キャプテンとして選択されたメンバM<3,2>，M<3,0>，M<3,4>が、公開情報である素数p とZp*の生成元g、ならびにメンバそれぞれが持つ秘密の乱数XM<l,m>∈Zp-1を用いて以下を新鍵共有部（１４）の処理により計算する。
（数１）  YM<l,m>=gXM<l,m> mod p【００７０】
M<3,3>と各キャプテンM<3,2>，M<3,0>，M<3,4>は数１の結果を以下のように送信する。このとき、ユニキャストもしくはマルチキャストで送信するが、man-in-the-middle攻撃
を防ぐためにはディジタル署名等の付加が必要である。ユニキャスト、マルチキャストによる送信方法及び、ディジタル署名の付加技術については周知である。【００７１】
M<3,3>→ [M<3,2>,M<3,0>,M<3,4>] : YM<3,3>
M<3,2>→ M<3,3> : YM<3,2>
M<3,0>→ M<3,3> : YM<3,0>
M<3,4>→ M<3,3> : YM<3,4>
なお、上記において、A→B:XはAがBへデータXを送信することを示す。【００７２】
各メンバにおいて、新鍵共有部（１４）において数１の結果を受信すると、ＤＨ鍵共有のベキ乗剰余演算を行い、その結果の値をハッシュ関数hに入力して演算する。これにより、M<3,3>とM<3,2>，M<3,0>，M<3,4>は、それぞれ以下の鍵を共有することができる。
K'<2,1>=h(gXM<3,3>XM<3,2> mod p)
K'<1,0>=h(gXM<3,3>XM<3,0> mod p)
K'<0,0>=h(gXM<3,3>XM<3,4> mod p)【００７３】
以上の新鍵共有処理（７２）が完了すると、次にキャプテンは、共有した新しい鍵を、部分木の他のメンバに配布する新鍵配布処理（７３）を新鍵配布部（１５）によって行う。
メンバ加入の際は、新しい鍵を加入以前の古い鍵を使って暗号化し、部分木のメンバに配布する。【００７４】
図４では、部分木を代表するM<3,0>（５２）とM<3,4>（５３）がそれぞれ、新しい鍵K'<1,0>、K'<0,0>を古い鍵K<1,0>，K<0,0>で暗号化して各部分木に配布する。すなわち、
M<3,0>→ T<1,0> : E(K<1,0>,K'<1,0>)
M<3,4>→ T<0,0> : E(K<0,0>,K'<0,0>)
ここで、E(K,X)とは共通鍵暗号の鍵ＫによるデータＸの暗号文を表す。
新鍵が配布されると、グループの各メンバは新しい鍵を復号し、該当するノードに割り当てて全てのサブグループ鍵及びグループ鍵を更新する。
グループ内の通信では新しいグループ鍵により暗号化が行われる。【００７５】
以上の加入プロトコルを一般化した処理流れ図を図８に示す。図８において、１〜６はｌ＝１の場合、７〜１３はｌが２以上の場合であり、２及び８では木構造データの更新（７０）、３及び９がキャプテンの選択（７１）、４及び１０が新鍵の共有（７２）、５〜６及び１１〜１３が新鍵の配布（７３）の各処理である。
【実施例３】
【００７６】
メンバ加入時の新鍵共有処理（７２）及び新鍵配布処理（７３）の別実施例を次に示す。（本方式をFDLKHのdistributed方式と呼ぶ。）
まず、新鍵共有処理（７２）において、実施例２のように加入メンバM<3,3>（５０）が各キャプテンM<3,2>，M<3,0>，M<3,4>と鍵の共有を行うのではなく、加入メンバM<3,3>（５０）は最下位のキャプテンM<3,2>（５１）と新鍵を共有し、次いでそのキャプテンM<3,2>（５１）とM<3,0>（５２）、M<3,0>（５２）とM<3,4>（５３）が順次新鍵を共有する。【００７７】
すなわち、
M<3,3>←→ M<3,2> : K'<2,1>
M<3,2>←→ M<3,0> : K'<1,0>
M<3,0>←→ M<3,4> : K'<0,0>
（←→は共有を示す）
のように、各メンバ間でサブグループ鍵、グループ鍵を共有する。【００７８】
そして、新鍵配布処理（７３）では、実施例２と同様に、
M<3,0>→ T<1,0> : E(K<1,0>,K'<1,0>)
M<3,4>→ T<0,0> : E(K<0,0>,K'<0,0>)
としてキャプテンが部分木に新鍵を配布する。
また、本実施例の新鍵共有処理（７２）では、加入メンバM<3,3>はK'<2,1>だけを受け取っているため、メンバM<3,2>（５１）及びM<3,0>（５２）が１つ上位の新鍵を下位の鍵で暗号化し、順次送信するように構成する。すなわち、
M<3,2>→ M<3,3>: E(K'<2,1>,K'<1,0>)
M<3,0>→ M<3,3>: E(K'<1,0>,K'<0,0>)
の処理を新鍵配布処理（７３）で合わせて行う。以上により、加入メンバ（５０）にも全てのサブグループ鍵及びグループ鍵が配布され、各メンバは鍵の更新を行うことができる。【００７９】
以上の加入プロトコルを一般化した処理流れ図を図９に示す。図９において、１〜６はｌ＝１の場合、７〜１５はｌが２以上の場合であり、２及び８では木構造データの更新（７０）、３及び９がキャプテンの選択（７１）、４及び１０〜１１が新鍵の共有（７２）、５〜６及び１２〜１５が新鍵の配布（７３）の各処理である。
【実施例４】
【００８０】
次に、実施例２に対応するメンバが脱退する際の処理(dedicated方式)を説述する。図７はメンバが脱退する場合の脱退プロトコルである。
上述した通り、メンバ（６０）が脱退する場合、加入脱退検知部（１１）で検知すると、キャプテン当否判定部（１３）の処理を各メンバが行うことにより、木構造におけるキャプテンが選択（８０）される。【００８１】
そして、新鍵共有処理（８１）に進む。ここで、新鍵の生成・変更にはＤＨ鍵共有を用いる。メンバ加入の際には加入メンバと各キャプテンがＤＨ鍵共有を行う。各キャプテンは、ＤＨ鍵共有で共有した値を暗号学的に安全な一方向性ハッシュ関数hに入力し、その結果得られた出力を部分木の根ノードに割り当てる共通鍵暗号の鍵とする。【００８２】
図５のメンバ脱退の例では、部分木T<2,0>のキャプテンとして選択されたM<3,1>（６１）と、それ以外のキャプテンとして選択されたM<3,3>（６２），M<2,3>（６３）が前述の数１の結果を以下のように送信する。
M<3,1>→ [M<3,3>,M<2,3>] : YM<3,1>
M<3,3>→ M<3,1> : YM<3,3>
M<2,3>→ M<3,1> : YM<2,3>【００８３】
各メンバにおいて、新鍵共有部（１４）において数１の結果を受信すると、ＤＨ鍵共有のベキ乗剰余演算を行い、その結果の値をハッシュ関数hに入力して演算する。これにより、M<3,1>と、M<3,3>、M<2,3>とは、それぞれ以下の鍵を共有することができる。
K'<1,0>=h(gXM<3,1>XM<3,3> mod p)
K'<0,0>=h(gXM<3,1>XM<2,3> mod p)【００８４】
次いで、新鍵配布処理（８２）を新鍵配布部（１５）で行う。メンバ脱退の際は、部分木の根ノードから１つ下層のノードの鍵を使って新しい鍵を暗号化し、部分木のメンバに配布する。さらにこの配布された新しい鍵を使って、脱退メンバの親ノードを根とする部分木のキャプテンが、各部分木に不足している鍵を暗号化して配布する。【００８５】
図５では、M<3,3>とM<2,3>がそれぞれ、新しい鍵K'<1,0>，K'<0,0>を、鍵K<2,1>，K<1,
1>で暗号化して各部分木に配布する。すなわち、
M<3,3>→ T<2,1> : E(K<2,1>,K'<1,0>)
M<2,3>→ T<1,1> : E(K<1,1>,K'<0,0>)
そしてM<3,1>が部分木T<1,0>に不足している鍵K'<0,0>を、先に配布されたK'<1,0>を使って暗号化し配布する。すなわち、
M<3,1>→ T<1,0> : E(K'<1,0>,K'<0,0>)
のように配布する。【００８６】
そして、鍵配布の後、グループの各メンバは新しい鍵を復号し、該当するノードに割り当てて鍵更新する。
さらに各メンバは木構造データ更新部（１２）により木構造データの更新処理（８３）を行い、脱退処理を完了する。【００８７】
以上の脱退プロトコルを一般化した処理流れ図を図１０に示す。図１０において、１〜３はｌ＝１の場合、４〜１０はｌ＝２の場合、１１〜１８はｌが３以上の場合である。そして、ｌ＝１の場合には根ノードを削除して部分木の名前を更新する処理であり、その他の場合には、５及び１２がキャプテンの選択（８０）、６及び１３が新鍵の共有（８１）、７〜９及び１４〜１７が新鍵の配布（８２）、１０及び１８が木構造データの更新（８３）の各処理である。
【実施例５】
【００８８】
メンバが脱退する場合の別プロトコル(distributed方式)として、次のように構成することもできる。これは実施例３に示す加入プロトコルに対応する方法である。
実施例４において、新鍵共有部（１４）がM<3,1>（６１）と、M<3,3>（６２）、M<2,3>（６３）とが鍵をK'<1,0>及びK'<0,0>を共有したが、本実施例では、M<3,1>（６１）とM<3,3>（６２）がK'<1,0>を、M<3,3>（６２）とM<2,3>（６３）とがK'<0,0>を共有する。【００８９】
そして、新鍵配布処理（８２）ではM<3,3>（６２）が部分木T<2,1>にK<2,1>で暗号化した新鍵K'<1,0>を、M<2,3>（６３）が部分木T<1,1>にK<1,1>で暗号化した新鍵K'<0,0>をそれぞれ送信する。
さらに、M<3,3>（６２）は新鍵K'<0,0>をK'<1,0>で暗号化して部分木T<1,0>に送信する。【００９０】
以上の脱退プロトコルを一般化した処理流れ図を図１１に示す。図１１において、１〜３はｌ＝１の場合、４〜１０はｌ＝２の場合、１１〜１８はｌが３以上の場合である。そして、ｌ＝１の場合には根ノードを削除して部分木の名前を更新する処理であり、その他の場合には、５及び１２がキャプテンの選択（８０）、６及び１３が新鍵の共有（８１）、７〜９及び１４〜１７が新鍵の配布（８２）、１０及び１８が木構造データの更新（８３）の各処理である。
【評価実験】
【００９１】
次に本発明に係るFDLKHの評価実験結果を示す。実験として、鍵の数、およびメンバ加入・脱退時のグループ鍵更新にかかるコスト（DH鍵共有の回数、共通鍵暗号による暗号化・復号の回数）を比較する。
比較対象として鍵を集中管理する鍵管理サーバを用いた２つの鍵管理方式（Flat, LKH）のコストを併せて示す。ここで、Flatは鍵管理サーバとメンバの間で個別の共通鍵（以下、個別鍵と呼ぶ。）を共有し、その他の階層的な鍵の割り当てを行わないスター型のnaive な方式を指し、LKHは同じく鍵管理サーバとメンバの間で個別鍵を共有し、さらにグループ鍵更新のための鍵を木構造で管理する従来の技術として示した方式を指す。
【００９２】
なお評価の簡単化のため、LKHで用いる鍵の木の度数（各ノードが持つ子の数）は２とし、LKH、FDLKHともにメンバの加入後もしくは脱退前のメンバ数ｎは２のベキ数、鍵の木は完全２分木とする。
このとき、加入・脱退メンバをM<l,m>とするとl = log2nが成り立つ。
【００９３】
表１は、Flat、LKH、FDLKHの３方式におけるシステム全体の鍵の総種類数と、１メンバが保持する鍵の数を示している。FDLKHは鍵管理サーバを用いず、ゆえにメンバ毎の個別鍵も存在しないため、１メンバあたりの鍵の数はLKHよりも１つ少なく、鍵の総種類数はLKHの約半分となっている。
【００９４】
【表１】
0004654371.tif 000002
【００９５】
次に、メンバが加入する際のコストを表２に示す。なお、表２のRegular membersは、
キャプテンと加入メンバを除いたその他のメンバを示し、回数はそれぞれ１ノード当たりで表している。
M<l,m>がグループに加入する際、加入メンバ（newcomer）が個別鍵でl 回の復号を行うLKH に対し、FDLKHでは加入メンバと各キャプテンが延べl 回のＤＨ鍵共有を行う。
本発明に係るFDLKHでは鍵管理サーバを必要としない方式であり、サーバレスである代わりに、加入メンバの計算量はLKHに比べて増加する。ただし、FlatやLKHでは鍵管理サーバ(Key server)とメンバ(Members)との間の個別鍵共有のコストが別途必要であり、全体としてのコストはFDLKHが低くなる。
また、distributed方式は、dedicated方式に比して、１メンバに偏っていた加入・脱退プロトコルの際の処理を、さらに分散化させた方式であることが示されている。
【００９６】
【表２】
0004654371.tif 000003
【００９７】
メンバの復号回数はLKHでは平均２回以下である。FDLKHでも同様にキャプテンや加入・
脱退メンバ以外の一般メンバ（regular members）の復号回数は平均2 回以下である。LKHでは鍵管理サーバの暗号化回数は2l回であり、このうち半数は部分木への鍵配布のための暗号化である。
FDLKH(dedicated方式)ではこの鍵配布のための暗号化を各キャプテンが１回ずつ（延べl-1回）行う。また、キャプテンの平均復号回数は(0+1+・・・+l-1)/l=(l-1)/2である。
図１２はFDLKH(dedicated方式)の、図１３はFDLKH(distributed方式)の、それぞれメンバ加入において、メンバ数に対する共通鍵暗号系のコスト（暗号化回数と復号回数の和）の変化を示している。
【００９８】
次に、メンバ脱退時のコストを検討する。M<l,m>がグループから脱退する際には表３に示すようにFlat 方式では、鍵管理サーバが脱退メンバ（seceder）以外のn-1個の個別鍵で新しいグループ鍵を暗号化して各メンバに配布する必要があり、スケーラビリティは低い。
LKHでは鍵管理に木構造を導入し、鍵管理サーバの暗号化回数を2l 回に抑えている。
【００９９】
FDLKH では脱退メンバの親ノードを根とする部分木のキャプテン（generous captain）がl-1回のＤＨ鍵共有とl-2回の鍵配布のための暗号化を行う。それ以外の各キャプテンは１回のＤＨ鍵共有と、１回の暗号化（延べl-1回）を行う。キャプテンの平均復号回数は(0+1+・・・+l-2)/(l-1)=(l-2)/2である。
図１４はFDLKH(dedicated方式)の、図１５はFDLKH(distributed方式)の、メンバ脱退において、メンバ数に対する共通鍵暗号系のコストの変化を示している。また、Buddy captainは、脱退メンバに最も近い（実施例５におけるM<3,1>（６１））キャプテンを示している。
【０１００】
【表３】
0004654371.tif 000004
【図１】
0004654371.tif 000005
【図２】
0004654371.tif 000006
【図３】
0004654371.tif 000007
【図４】
0004654371.tif 000008
【図５】
0004654371.tif 000009
【図６】
0004654371.tif 000010
【図７】
0004654371.tif 000011
【図８】
0004654371.tif 000012
【図９】
0004654371.tif 000013
【図１０】
0004654371.tif 000014
【図１１】
0004654371.tif 000015
【図１２】
0004654371.tif 000016
【図１３】
0004654371.tif 000017
【図１４】
0004654371.tif 000018
【図１５】
0004654371.tif 000019