WO2009157050A1

WO2009157050A1 - 情報処理装置及びプログラム

Info

Publication number: WO2009157050A1
Application number: PCT/JP2008/061400
Authority: WO
Inventors: 伊藤　隆; 米田　健; 宏郷辻; 和美齋藤; 英憲太田; 松田　規; 充洋服部
Original assignee: 三菱電機株式会社
Priority date: 2008-06-23
Filing date: 2008-06-23
Publication date: 2009-12-30
Also published as: JPWO2009157050A1

Abstract

　鍵管理構造生成部２１２が、ｎ個の葉ノードが含まれる木構造の鍵管理構造を生成し、各ノードに秘密情報を割り当て、端末配置部２１３がｍ（２≦ｍ＜ｎ）個の端末を各葉ノードに割り当て、マルチキャストの対象とする正当端末が割り当てられたノードを正当ノードとし、マルチキャストの対象でない失効端末が割り当てられたノードを失効ノードとし、端末が未割り当てのノードを未使用ノードとし、新たな端末をマルチキャストの対象とする場合に、当該新たな端末を未使用ノードに割り当て、集合導出部２１５が、各ノードへの端末の割り当て状態を解析して、正当端末のみが暗号化メッセージを復号できる秘密情報の組合せであって、通信オーバーヘッドが最も少ない組合せを導出し、暗号部２１７が、導出された組合せの秘密情報を用いて送信メッセージを暗号化し、通信部２１６が暗号化メッセージをマルチキャスト送信する。

Description

情報処理装置及びプログラム

　本発明は、暗号技術を利用して、例えばサーバ装置（以下、サーバともいう）から複数の正当な端末装置（以下、端末ともいう）だけに情報を同報送信（マルチキャスト）する技術に関する。

　セキュアマルチキャストシステムは、暗号技術を利用して、サーバから複数の正当な端末だけに情報を同報送信（マルチキャスト）し、失効した端末（群）には、たとえ失効端末同士で結託があったとしても情報が一切漏れないようにする通信システムである。
　ここで、正当な端末とは、サーバから送信される暗号化メッセージの復号が許される端末であり、失効した端末（群）とは、サーバから送信される暗号化メッセージの復号が禁止される端末（群）である。

　セキュアマルチキャストシステムのうち、端末が保持するデバイス鍵が一切更新されないものをｓｔａｔｅｌｅｓｓな方式という。
　ｓｔａｔｅｌｅｓｓな方式として、端末が保持するデバイス鍵の数、マルチキャストの通信オーバーヘッド、端末が鍵を導出するための演算オーバーヘッドをできるだけ小さくする様々な技術が提案されている。

　非特許文献１にて開示されているＣｏｍｐｌｅｔｅ　Ｓｕｂｔｒｅｅ法（ＣＳ法）やＳｕｂｓｅｔ　Ｄｉｆｆｅｒｅｎｃｅ法（ＳＤ法）は、サーバが各端末を木構造の葉（最下層）に配置し、葉を含む各ノードに秘密情報を割り当て、各端末が自分のノードからルートノードまでのパス上にある各ノードに対応する秘密情報を保持する方式である。
　これらの方式では、サーバがマルチキャストを行う際に、複数の正当な端末を、適切な方法で、端末の部分集合の和Ｓ１＋Ｓ２＋…＋Ｓｊで表現する。その後、Ｓ１に属する端末だけが保持する（もしくは導出可能である）暗号鍵Ｋ１、Ｓ２に属する端末だけが保持する暗号鍵Ｋ２、…、Ｓｊに属する端末だけが保持する暗号鍵Ｋｊを用いて、メッセージＭ（もしくはメッセージＭを暗号化するためのセッション鍵Ｋ）（本明細書では、メッセージＭ及びセッション鍵Ｋをまとめて送信メッセージと表記する）を暗号化する。
　つまり、サーバは、失効した端末は保持していない（導出できない）が、正当な端末は保持している（導出できる）鍵を抽出し、抽出した鍵の各々を用いてメッセージを暗号化し、暗号化メッセージを同報送信する。
　上記のように暗号化を行うことで、正当な端末だけに情報を送信するセキュアマルチキャストが実現できる。

　このとき、通信オーバーヘッドは和で表現した際の要素数ｊに比例する値となるが、ＣＳ法やＳＤ法では、各端末に持たせる秘密情報を工夫することによって、ｊの値を小さくすることを実現している。
　ＣＳ法やＳＤ法は既定の複数個の正当な端末があり、ここから徐々に失効端末が発生するというモデルのもとで、効率の良いセキュアマルチキャストを行うための方式である。
　これに対し、特許文献１にて開示されている方式では、未使用の（端末が割り当てられていない）葉ノードの下に複数のノードを追加することで、端末を制限なく追加することを実現している。
特開２００３－２０４３２１号広報Ｄ．Ｎａｏｒ，　Ｍ．Ｎａｏｒ，　ａｎｄ　Ｊ．Ｌｏｓｔｐｉｅｃｈ，　"Ｒｅｖｏｃａｔｉｏｎ　ａｎｄ　ｔｒａｃｉｎｇ　ｓｃｈｅｍｅｓ　ｆｏｒ　ｓｔａｔｅｌｅｓｓ　ｒｅｃｅｉｖｅｒｓ，"　Ａｄｖａｎｃｅｓ　ｉｎ　Ｃｒｙｐｔｏｌｏｇｙ　－　ＣＲＹＰＴＯ’０１，　ＬＮＣＳ　ｖｏｌ．２１３９，　ｐｐ．４１－６２，　２００１．

　ＣＳ法やＳＤ法などの鍵管理アルゴリズムは、最初に存在する全ての端末を木構造の葉ノードに配置することで鍵管理木を作成し、その後各端末の失効に応じてマルチキャストのヘッダを変更する方式である。
　このため、ＣＳ法やＳＤ法をそのまま用いる場合、端末を新たに追加することができない。
　特許文献１にて開示されている方式では、いくつかの葉ノードを端末に対応付けせずに残しておき、これらのノードが少なくなった際に下に複数ノードを追加することで端末の追加を可能としているが、この場合、端末の追加が多くなるほど木がアンバランスになるため、必要なデバイス鍵や通信オーバーヘッドが全体的に増加するという課題がある。
　また、追加端末をどのノードに割り当てるかについては開示されていない。

　本発明は、上記の課題を解決することを主な目的としており、例えばセキュアマルチキャストシステムにおいて、端末の追加を可能とし、また、通信オーバーヘッドを小さくすることを主な目的とする。

　本発明に係る情報処理装置は、ｍ（ｍ≧２）個の通信装置の中からマルチキャスト送信の対象として選択された２個以上のマルチキャスト対象通信装置に、秘密情報を用いて暗号化された暗号化メッセージをマルチキャスト送信する情報処理装置であって、
　配列されたｎ（ｎ＞ｍ）個のノードが含まれる秘密情報管理構造を生成する秘密情報管理構造生成部と、
　前記秘密情報管理構造のｎ個のノードのうちのｍ個のノードに前記ｍ個の通信装置を割り当てるとともに、前記ｎ個のノードのうち通信装置が割り当てられていないノードを未使用ノードとして指定する装置割当て部と、
　前記装置割当て部による前記秘密情報管理構造への端末装置の割り当て結果に基づいて、前記マルチキャスト対象通信装置にマルチキャスト送信する暗号化メッセージの暗号化に用いる秘密情報を選択する秘密情報選択部とを有することを特徴とする。

　前記装置割当て部は、
　前記ｍ個の通信装置以外の新たな通信装置がマルチキャスト対象通信装置として選択された場合に、前記新たな通信装置を未使用ノードに割り当てることを特徴とする。

　前記情報処理装置は、更に、
　ｎ＋１個以上の秘密情報を記憶する秘密情報記憶部と、
　前記秘密情報記憶部に記憶されている秘密情報のうちｎ個の秘密情報をノード秘密情報として前記秘密情報管理構造のｎ個のノードに対応付けて管理し、前記秘密情報記憶部に記憶されている秘密情報のうちノード秘密情報以外の秘密情報をグループ化された複数個のノードに共通に適用されるグループ秘密情報として管理する秘密情報管理部とを有し、
　前記装置割当て部は、
　前記秘密情報管理構造のｎ個のノードのうちのｍ個のノードに前記ｍ個の通信装置を割り当てるとともに、前記ｍ個のノードのうちマルチキャスト対象通信装置が割り当てられているノードを正当ノードとして指定し、前記ｍ個のノードのうちマルチキャスト対象通信装置以外の通信装置が割り当てられているノードを失効ノードとして指定し、
　前記秘密情報選択部は、
　前記ｎ個のノードにおける正当ノードの位置と失効ノードの位置と未使用ノードの位置に基づき、複数個の正当ノードをグループ化できるか否かを判断し、グループ化できる複数個の正当ノードに対してはグループ秘密情報を適用し、グループ化できない正当ノードに対しては対応付けられているノード秘密情報を適用して、前記マルチキャスト対象通信装置にマルチキャスト送信する暗号化メッセージの暗号化に用いる秘密情報を選択することを特徴とする。

　前記装置割当て部は、
　前記ｍ個の通信装置以外の新たな通信装置がマルチキャスト対象通信装置として選択された場合に、前記新たな通信装置を未使用ノードに割り当て、前記新たな通信装置が割り当てられた未使用ノードを正当ノードに変更することを特徴とする。

　前記装置割当て部は、
　前記新たな通信装置がマルチキャスト対象通信装置として選択された際に前記秘密情報管理構造のｎ個のノードにおいて未使用ノードが１つだけ存在する場合に、前記新たな通信装置を未使用ノードに割り当て、前記新たな通信装置が割り当てられた未使用ノードを正当ノードに変更し、
　前記秘密情報選択部は、
　前記装置割当て部により前記未使用ノードが正当ノードに変更された後の前記ｎ個のノードにおける正当ノードの位置と失効ノードの位置に基づき、複数個の正当ノードをグループ化できるか否かを判断することを特徴とする。

　前記秘密情報選択部は、
　前記新たな通信装置がマルチキャスト対象通信装置として選択された際に前記秘密情報管理構造のｎ個のノードにおいて未使用ノードが複数個存在する場合に、各々の未使用ノードに前記新たな通信装置が割り当てられた場合の前記ｎ個のノードにおける正当ノードの位置と失効ノードの位置と未使用ノードの位置に基づき、未使用ノードごとに、暗号化メッセージの暗号化に用いる秘密情報の数を算出し、算出した秘密情報の数が最小となる未使用ノードを選択し、
　前記装置割当て部は、
　前記秘密情報選択部により選択された未使用ノードに前記新たな通信装置を割り当てることを特徴とする。

　前記秘密情報選択部は、
　前記ｎ個のノードを配列の順に従ってｋ（２≦ｋ＜ｍ）個のノードごとのブロックに分け、ブロックごとに、ブロック内のｋ個のノードにいずれの種類のノードが含まれているかを解析して、複数個の正当ノードをグループ化できるか否かを判断することを特徴とする。

　前記秘密情報選択部は、
　ブロック内のｋ個のノードのすべてが未使用ノードである場合にｋ個のノードの親ノードとして未使用ノードを指定し、
　ブロック内のｋ個のノードに失効ノードが含まれていない場合にｋ個のノードの親ノードとして正当ノードを指定し、
　ブロック内のｋ個のノードに失効ノードが含まれる場合にｋ個のノードの親ノードとして失効ノードを指定し、
　以降、同様の処理を繰り返し、
　失効ノードが指定されるごとに、指定された失効ノードの子孫ノードにあたる複数個の正当ノードをグループ化することを特徴とする。

　前記秘密情報管理構造生成部は、
　最下位階層に前記ｎ個のノードが配置される複数階層のｋ分木構造の秘密情報管理構造を生成し、
　前記秘密情報記憶部は、
　前記秘密情報管理構造に含まれるノード数分の秘密情報を記憶し、
　前記秘密情報管理部は、
　前記秘密情報記憶部に記憶されている秘密情報のうちｎ個の秘密情報をノード秘密情報として前記秘密情報管理構造のｎ個のノードに対応付けて管理し、前記秘密情報記憶部に記憶されている秘密情報のうちノード秘密情報以外の秘密情報をグループ秘密情報として前記ｎ個のノード以外のノードに対応付けて管理し、
　前記秘密情報選択部は、
　グループ化された複数個の正当ノードに対して、祖先ノードである失効ノードの子ノードにあたる正当ノードに対応付けられているグループ秘密情報を適用することを特徴とする。

　前記秘密情報選択部は、
　所定の条件に合致するノードをＳＤ（Ｓｕｂｓｅｔ　Ｄｉｆｆｅｒｅｎｃｅ）ノードとして指定し、
　ブロック内のｋ個のノードのすべてが未使用ノードである場合にｋ個のノードの親ノードとして未使用ノードを指定し、
　ブロック内のｋ個のノードに失効ノードもＳＤノードも含まれていない場合にｋ個のノードの親ノードとして正当ノードを指定し、
　ブロック内のｋ個のノードに失効ノードとＳＤノードが合わせて１個だけ含まれている場合にｋ個のノードの親ノードとしてＳＤノードを指定し、
　ブロック内のｋ個のノードに失効ノードとＳＤノードが合わせて２個以上含まれている場合にｋ個のノードの親ノードとして失効ノードを指定し、
　以降、同様の処理を繰り返し、
　失効ノードが指定されるごとに、指定された失効ノードの子孫ノードにあたる複数個の正当ノードをグループ化することを特徴とする。

　前記秘密情報管理構造生成部は、
　最下位階層に前記ｎ個のノードが配置される複数階層のｋ分木構造の秘密情報管理構造を生成し、
　前記秘密情報記憶部は、
　前記秘密情報管理構造に含まれるノード数分の秘密情報を記憶し、
　前記秘密情報管理部は、
　前記秘密情報記憶部に記憶されている秘密情報のうちｎ個の秘密情報をノード秘密情報として前記秘密情報管理構造のｎ個のノードに対応付けて管理し、前記秘密情報記憶部に記憶されている秘密情報のうちノード秘密情報以外の秘密情報をグループ秘密情報として前記ｎ個のノード以外のノードに対応付けて管理し、
　前記秘密情報選択部は、
　グループ化された複数個の正当ノードに対して、祖先ノードである失効ノードの子ノードにあたる正当ノード及びＳＤノードのいずれかに対応付けられているグループ秘密情報を適用することを特徴とする。

　前記装置割当て部は、
　正当ノードと失効ノードと未使用ノードが分散して配置されるように、前記ｍ個の通信装置を前記ｍ個のノードに割り当てることを特徴とする。

　本発明に係るプログラムは、ｍ（ｍ≧２）個の通信装置の中からマルチキャスト送信の対象として選択された２個以上のマルチキャスト対象通信装置に、秘密情報を用いて暗号化された暗号化メッセージをマルチキャスト送信するコンピュータに、
　配列されたｎ（ｎ＞ｍ）個のノードが含まれる秘密情報管理構造を生成する秘密情報管理構造生成処理と、
　秘密情報記憶領域に記憶されているｎ＋１個以上の秘密情報のうちｎ個の秘密情報をノード秘密情報として前記秘密情報管理構造のｎ個のノードに対応付けて管理し、前記秘密情報記憶領域に記憶されている秘密情報のうちノード秘密情報以外の秘密情報をグループ化された複数個のノードに共通に適用されるグループ秘密情報として管理する秘密情報管理処理と、
　前記秘密情報管理構造のｎ個のノードのうちのｍ個のノードに前記ｍ個の通信装置を割り当てるとともに、前記ｍ個のノードのうちマルチキャスト対象通信装置が割り当てられているノードを正当ノードとして指定し、前記ｍ個のノードのうちマルチキャスト対象通信装置以外の通信装置が割り当てられているノードを失効ノードとして指定し、前記ｎ個のノードのうち通信装置が割り当てられていないノードを未使用ノードとして指定する装置割当て処理と、
　前記ｎ個のノードにおける正当ノードの位置と失効ノードの位置と未使用ノードの位置に基づき、複数個の正当ノードをグループ化できるか否かを判断し、グループ化できる複数個の正当ノードに対してはグループ秘密情報を適用し、グループ化できない正当ノードに対しては対応付けられているノード秘密情報を適用して、前記マルチキャスト対象通信装置にマルチキャスト送信する暗号化メッセージの暗号化に用いる秘密情報を選択する秘密情報選択処理とを実行させることを特徴とする。

　本発明によれば、ｍ個の端末装置に対して、ｎ個のノードが含まれる秘密情報管理構造を生成し、端末装置が割り当てられていないノードを未使用ノードとすることで、新たな端末装置をマルチキャスト送信の対象とする場合に、新たな端末装置を未使用ノードに割り当てることができる。
　また、既に存在している未使用ノードに新たな端末装置を割り当てるものであり、新たな端末装置のためにノードを追加するわけではなく、秘密情報管理構造のノード構成がアンバランスにならず、通信オーバーヘッドを抑制することができる。

　実施の形態１．
　本実施の形態では、運用開始時の端末数よりも十分大きい数の葉ノードから構成される鍵管理木を作成し、各ノードを正当・失効・未使用の３状態で管理してマルチキャストを行うことで、端末の追加を可能とし、かつ通信オーバーヘッドを小さく抑えるセキュアマルチキャストシステムについて説明する。

　図１は、本実施の形態に係るセキュアマルチキャストシステムのシステム構成例を示す。
　図１において、サーバ装置２０１（以下、単にサーバともいう）と複数の端末装置３０１（以下、単に端末ともいう）がネットワーク１０１を介して接続されている。
　本実施の形態に係るセキュアマルチキャストシステムにおいては、暗号技術を利用して、サーバ装置２０１から複数の正当な端末装置３０１だけに情報を同報送信（マルチキャスト）し、失効した端末（群）には、たとえ失効端末同士で結託があったとしても情報が一切漏れないようにする。
　なお、サーバ装置２０１は情報処理装置の例であり、端末装置３０１は通信装置の例である。また、正当な端末装置３０１、つまりサーバ装置２０１からのマルチキャストの対象となる端末装置３０１は、マルチキャスト対象通信装置の例である。

　図２は、サーバ装置２０１の構成例を表すブロック図である。
　本実施の形態に係るサーバ装置２０１は、各端末に格納する鍵の決定と、各端末へのメッセージ送信を行う。

　図２において、アルゴリズム記憶領域２１１は、セキュアマルチキャストにおける鍵割り当て、正当な端末へのメッセージ送信などのアルゴリズムを記憶するデータ記憶手段である。
　本実施の形態では、端末を木構造で管理するアルゴリズムとして、ＣＳ法をベースとするアルゴリズムを利用する。

　鍵管理構造生成部２１２は、アルゴリズム記憶領域２１１に記憶されているアルゴリズムに従い、鍵管理構造を生成し、鍵管理構造上の各要素に秘密情報を割り当てる手段である。秘密情報は例えば鍵、もしくは鍵導出の元となる情報である。
　本実施の形態では、鍵管理木構造（以下、鍵管理木ともいう）が生成され、鍵管理木構造上の各ノード（ルートノード、中間ノード、葉ノード）に秘密情報が割り当てられる。
　より具体的には、サーバ２０１がｍ（ｍ≧２）個の端末３０１に接続され、ｍ個の端末３０１の中からマルチキャスト送信の対象として２個以上の端末３０１が選択される場合に、鍵管理構造生成部２１２は、配列されたｎ（ｎ＞ｍ）個の葉ノードが含まれる木構造の鍵管理構造（秘密情報管理構造）を生成するとともに、ｎ個の秘密情報を鍵管理構造のｎ個の葉ノードに対応付けて管理する。また、鍵管理構造生成部２１２は、葉ノードの上位階層ノード（上位ノードともいう）数分の秘密情報を各上位階層ノードに対応付けて管理する。
　葉ノードの上位ノードは、中間ノードとルートノードである。中間ノードの上位ノードは、より上位の中間ノードとルートノードである。
　なお、ｎ個の葉ノードに対応付けられる秘密情報をノード秘密情報ともいう。また、葉ノードの上位ノードに対応付けられる秘密情報をグループ秘密情報ともいう。グループ秘密情報は、グループ化された複数個の下位階層ノード（下位ノードともいう）に共通に適用される秘密情報である。
　鍵管理構造生成部２１２は、秘密情報管理部及び秘密情報管理構造生成部の例である。

　図６は、鍵管理構造生成部２１２が各ノードに秘密情報を割り当てた状態の鍵管理構造の例を示す。
　図６の例では、葉ノードが８個あり、また、階層ごとに隣合う２個のノードずつ上位ノードに集約され、最終的にルートノードに至る。各ノードに記述されているｋａ－ｋｏは各ノードに割り当てられている秘密情報である。
　８個の葉ノードに割り当てられている秘密情報ｋｈ－ｋｏがノード秘密情報に相当し、上位ノードに割り当てられている秘密情報ｋａ－ｋｇがグループ秘密情報に相当する。

　端末配置部２１３は、各端末を、鍵管理構造記憶領域２１４に記憶されている鍵管理木構造のうち端末が割り当てられていない葉ノードに割り当て、アルゴリズム記憶領域２１１に記憶されているアルゴリズムに従い、鍵管理木構造上の適切な秘密情報を端末に割り当てる手段である。
　より具体的には、端末配置部２１３は、サーバ２０１がｍ個の端末３０１に接続され、また、鍵管理構造生成部２１２によりｎ個の葉ノードが含まれる鍵管理構造が生成された場合に、鍵管理構造のｎ個のノードのうちのｍ個のノードにｍ個の端末を割り当てるとともに、ｍ個の葉ノードのうち正当な端末が割り当てられているノードを正当ノードとして指定し、ｍ個の葉ノードのうち失効端末が割り当てられているノードを失効ノードとして指定し、ｎ個のノードのうち端末が割り当てられていないノードを未使用ノードとして指定する。つまり、葉ノードは、「正当な端末が割り当てられている（正当ノード）」「失効した端末が割り当てられている（失効ノード）」「端末が割り当てられていない（未使用ノード）」の３状態のいずれかで管理される。
　また、端末配置部２１３は、ｍ個の端末以外の新たな端末がマルチキャストの対象として選択された場合に、新たな端末を未使用ノードに割り当て、新たな端末が割り当てられた未使用ノードを正当ノードに変更し、未使用ノードが正当ノードに変更された後のｎ個の葉ノードにおける正当ノードの位置と失効ノードの位置に基づき、複数個の正当ノードをグループ化できるか否か（上位ノードの秘密情報を適用できるか否か）を判断する。
　端末配置部２１３は、装置割当て部の例である。

　鍵管理構造記憶領域２１４は、鍵管理構造生成部２１２が生成した鍵管理構造（秘密情報を含む）の葉ノードに、各端末を割り当てたデータを記憶するデータ記憶手段である。
　図４は鍵管理構造記憶領域２１４が記憶するデータの一例を表す。前述したように、図４において、ｋａからｋｏまでは各ノードに対応する秘密情報である。
　また、鍵管理構造記憶領域２１４は、鍵管理構造に対応付けてｎ＋１個以上の秘密情報を記憶している。具体的には、鍵管理構造に対応付けて鍵管理構造のノード数分の秘密情報を記憶している（図４の例では、１５個のノードに対応させて１５個の秘密情報を記憶している）。
　鍵管理構造記憶領域２１４は、秘密情報記憶部及び秘密情報記憶領域の例である。

　集合導出部２１５は、アルゴリズム記憶領域２１１に記憶されているアルゴリズムに従い、鍵管理構造記憶領域２１４に記憶されている鍵管理構造を入力として、正当な端末の集合が、端末の部分集合の和Ｓ１＋Ｓ２＋…＋Ｓｊに含まれ、失効した端末はこれに含まれないよう、各部分集合Ｓｉを導出する手段である。
　より具体的には、集合導出部２１５は、ｎ個の葉ノードにおける正当ノードの位置と失効ノードの位置と未使用ノードの位置に基づき、複数個の正当ノードをグループ化できるか否かを判断し、グループ化できる複数個の正当ノードに対してはグループ秘密情報を適用し、グループ化できない正当ノードに対しては対応付けられているノード秘密情報を適用して、正当な端末にマルチキャスト送信する暗号化メッセージの暗号化に用いる秘密情報を選択する。
　集合導出部２１５は、秘密情報選択部の例である。

　サーバ装置２０１は、葉ノードに割り当てられているノード秘密情報及び葉ノードに連結する上位ノードに割り当てられているグループ秘密情報を用いて暗号化を行うことができ、また、各端末は自身に対応する葉ノードに割り当てられているノード秘密情報及び葉ノードに連結する上位ノードに割り当てられているグループ秘密情報を用いて暗号化メッセージの復号ができる。
　例えば、図４の例では、端末０に対して、サーバ装置２０１は、秘密情報ｋａ、ｋｂ、ｋｄ、ｋｈのいずれでも暗号化ができ、また、端末０は、秘密情報ｋａ、ｋｂ、ｋｄ、ｋｈのいずれでも暗号化メッセージの復号ができる。同様に、端末４に対して、サーバ装置２０１は、秘密情報ｋａ、ｋｂ、ｋｄ、ｋｉのいずれでも暗号化ができ、また、端末４は、秘密情報ｋａ、ｋｂ、ｋｄ、ｋｉのいずれでも暗号化メッセージの復号ができる。
　このため、端末０及び端末４に対して、ノード秘密情報である秘密情報ｋｈとｋｉを利用するよりも、端末０及び端末４に共通して適用できるグループ秘密情報ｋｄを利用する方が通信オーバーヘッドを少なくすることができる。また、端末４が割り当てられているノードの右隣２つのノードに失効ノードがなければ、４つの端末に共通して適用できるグループ秘密情報ｋｂを利用することで更に通信オーバーヘッドを少なくすることができる（但し、図４の例では、端末２が失効しているので、秘密情報ｋｂは適用できない）。
　集合導出部２１５は、このようなグループ秘密情報の適用可否を判断して、通信オーバーヘッドが最小値となる秘密情報の集合を導出する。

　通信部２１６は、端末装置３０１と通信を行う手段である。
　暗号部２１７は、共通鍵・公開鍵暗号の鍵生成・暗号化、乱数生成などを行う手段である。

　図３は、セキュアマルチキャストシステム（図１）において、サーバ装置２０１からのマルチキャストを受信する端末装置３０１の構成例を表すブロック図である。

　図３において、アルゴリズム記憶領域３１１は、セキュアマルチキャストにおける鍵導出・復号などのアルゴリズムを記憶するデータ記憶手段である。
　本実施の形態では、ＣＳ法のアルゴリズムを利用する。

　秘密情報記憶領域３１２は、サーバ装置２０１が管理する鍵管理構造に対応付けられた秘密情報（暗号鍵、もしくは暗号鍵導出の元となる情報）を記憶するデータ記憶手段である。
　本実施の形態では、全ての端末は木構造に対応付けられた秘密情報を記憶する。図５は秘密情報記憶領域３１２が記憶するデータの一例を表す。
　より具体的には、図５は、図４に示す端末０が保有するデータの例を示している。
　すなわち、端末０は図４の鍵管理構造では、秘密情報ｋａ、ｋｂ、ｋｄ、ｋｈを利用できることが示されるが、図５では、これに対応して、端末０はこれら秘密情報ｋａ、ｋｂ、ｋｄ、ｋｈを保有していることを示している。

　鍵導出部３１３は、アルゴリズム記憶領域３１１に記憶されているアルゴリズムに従い、サーバ装置２０１から受信したメッセージの復号に必要な暗号鍵を、秘密情報記憶領域３１２に記憶されている秘密情報から導出する手段である。

　通信部３１４は、サーバ装置２０１と通信を行う手段である。
　暗号部３１５は、共通鍵・公開鍵暗号の復号、乱数生成などを行う手段である。

　セキュアマルチキャストにおける手続きは、サーバが鍵管理構造を作成する部分、運用開始時にサーバが複数の端末を鍵管理構造に割り当てる部分、端末を失効させる部分、端末を追加する部分、サーバから各端末への暗号通信を行う部分に大別される。
　以下、図１８のフローチャートを参照しながら、それぞれの手続きについて説明する。
　なお、本実施の形態では、（１）から（５）を番号順に実行する例について説明するが、（３）から（５）に関しては任意の順番で、（端末数の制約が許す限り）何度でも繰り返し実行することができる。

（１）鍵管理構造の作成
　鍵管理構造生成部２１２および暗号部２１７は、システムで全体で利用する、失効端末も含めた端末数の最大値ｎを入力として、アルゴリズム記憶領域２１１に格納されている鍵管理アルゴリズムに従い、鍵管理構造を作成し（ステップＳ１８０１）（秘密情報管理構造生成処理）、また、各ノードに秘密情報を割り当てる（ステップＳ１８０２）（秘密情報管理処理）。そして、各ノードに秘密情報が割り当てられた鍵管理構造を鍵管理構造記憶領域２１４に格納する。
　本実施の形態では、鍵管理構造生成部２１２は、ＣＳ法に従い、葉ノード数ｎの鍵管理木を作成する。また、秘密情報は、サーバ装置２０１で生成してもよいし、外部で生成されたものをサーバ装置２０１に入力してもよい。
　なお、この時点では、全ての葉ノードには端末が割り当てられておらず、各葉ノードは「未使用ノード」である。
　例えばｎ＝８の場合、図６のような鍵管理木が作成される。

（２）運用開始時の端末割り当て
　端末配置部２１３は、鍵管理構造記憶領域２１４に記憶されている鍵管理木に対し、運用開始時に利用するｍ（ｍ＜ｎ）個の端末を割り当てる（ステップＳ１８０３）（装置割当て処理）。
　端末が割り当てられた葉ノードは「正当ノード」となる。
　ここで、ｍ個の端末が、鍵管理構造の上でなるべく分散されるように配置を行う。
　一例として、ｎ＝８の鍵管理木に端末０から端末５までを配置する場合、各端末ＩＤを３桁の二進表記で表したビット列を逆転させ、これが表す値の場所に当該端末の配置を行う（端末０→０００→０００→左から０番目、端末１→００１→１００→左から４番目、端末２→０１０→０１０→左から２番目、…）。
　例えば図６の鍵管理木に６個の端末を割り当てる場合、図７のような鍵管理木が作成される。
　その後、サーバ装置２０１は、アルゴリズム記憶領域２１１に記憶されているアルゴリズムに従い、各端末に必要な秘密情報を格納する。
　本実施の形態では、ＣＳ法に従って秘密情報の格納が行われる。

（３）端末の失効
　正当な端末を失効させる必要がある場合、端末配置部２１３は、鍵管理構造記憶領域２１４に記憶されている鍵管理木において、当該の正当端末に対応する「正当ノード」を「失効ノード」に変更する（ステップＳ１８０４）（装置割当て処理）。
　これにより、正当ノード、失効ノードが指定される（ステップＳ１８０５）（装置割当て処理）。
　例えば図７の鍵管理木において端末２を失効させると、図８のような鍵管理木が作成される。
（４）端末の追加
　新たな端末をシステムに追加する場合（ステップＳ１８０６でＹＥＳ）、端末配置部２１３は、鍵管理構造記憶領域２１４に記憶されている鍵管理木における「未使用ノード」の数を判断し（ステップＳ１８０７）、未使用ノードの数が１つの場合は、当該未使用ノードに追加端末を割り当てる（ステップＳ１８０８）。
　一方、未使用ノードが複数存在する場合は、複数の未使用ノードから１つを選択する必要がある。
　選択にあたっては、各未使用ノードに新たな端末装置を割り当てた鍵管理木を用いて図１０のＳ１００１からＳ１００４及びＳ１００６の処理を行って（ステップＳ１８０９）、未使用ノードごとに、鍵管理木全体として暗号化に必要な秘密情報の数を算出し、秘密情報の数が最も小さくなる未使用ノードを選択し、選択した未使用ノードに追加端末を割り当てることとする（ステップＳ１８１０）。
　なお、図１０の各ステップの詳細は後述する。ただし、ステップＳ１８０９においては、暗号化を実際に行う必要はない。なお、通信オーバーヘッドが最小となるような「未使用ノード」が複数ある場合には、端末が鍵管理木の上でなるべく分散されるようなものを選択する。
　その後、追加端末を割り当てたノードを「正当ノード」に変更する（ステップＳ１８１１）。
　例えば図８の鍵管理木において新たな端末６を未使用ノード（右端）に割り当てると、図９のような鍵管理木となる。
　また、サーバ装置２０１は、アルゴリズム記憶領域２１１に記憶されているアルゴリズムに従い、追加端末に必要な秘密情報を格納する。本実施の形態では、ＣＳ法に従って秘密情報の格納が行われる。
　なお、「（５）サーバから各端末への暗号通信」では、図１０のＳ１００１以降の処理が行われるが（ステップＳ１８１２）、すでにステップＳ１８０９が行われている場合は、すでに暗号化に用いる秘密情報が選択されているので、選択された秘密情報を用いて暗号化を行い（ステップＳ１００５）、選択された秘密情報を用いて暗号化を行い（ステップＳ１００５、Ｓ１００７）、暗号化メッセージを送信する（ステップＳ１００８）ようにすればよい。

（５）サーバから各端末への暗号通信
　図１０は、暗号通信処理における動作を説明するフローチャートである。
　以下、図１０のフローチャートを参照しながら説明する。
　暗号通信処理を行う前に、あらかじめサーバ装置２０１と各端末装置３０１とで、セキュアマルチキャストのアルゴリズムを共有しておく。
　ここでは、アルゴリズム記憶領域２１１にＣＳ法をベースとするアルゴリズム（詳細は後述）が、アルゴリズム記憶領域３１１にＣＳ法の復号アルゴリズムが格納されているものとする。
　また、サーバ装置２０１の鍵管理構造記憶領域２１４には前記（１）～（４）で作成されている鍵管理木が、端末装置３０１の秘密情報記憶領域３１２にはこれに対応する秘密情報が格納されている（ステップＳ１００１、Ｓ１００２）。
　以下では、鍵管理構造記憶領域２１４に図８で表される鍵管理木が格納されているものとする。

　処理の開始時には、全ての葉ノードに「正当ノード」「失効ノード」「未使用ノード」のいずれかの状態が割り当てられており、中間ノード（およびルートノード）には状態が割り当てられていない（図１１）。
　集合導出部２１５は、全ての子ノードに状態が割り当てられており、かつ自身には状態が割り当てられていないような中間ノード（もしくはルートノード）を一つ選択する（ステップＳ１００３）。
　そして、図１２の規則に従い、当該ノードの状態を決定する（ステップＳ１００４）。
　さらに、図１２の「暗号化」欄に記載されているとおり、暗号部２１７がメッセージ（もしくはセッション鍵）の暗号化を行う（ステップＳ１００５）。
　以上の処理を、ルートノードの状態が決定するまで繰り返し（ステップＳ１００６）、最終的にルートノードが「正当ノード」となった場合は、暗号部２１７がルートノードに対応する鍵でメッセージ（もしくはセッション鍵）の暗号化を行う（ステップＳ１００７）。

　通信部２１６は、端末装置３０１に、ステップＳ１００５やステップＳ１００７で作られた全ての暗号化メッセージ（もしくはセッション鍵）をマルチキャストする（ステップＳ１００８）。
　正当な端末装置３０１の通信部３１４はメッセージを受信し（ステップＳ１００９）、鍵導出部３１３と暗号部３１５が、アルゴリズム記憶領域３１１に記憶されているアルゴリズムに従い、秘密情報記憶領域３１２に記憶されている秘密情報から導出した暗号鍵で受信メッセージを復号する（ステップＳ１０１０）。
　ステップＳ１０１０の詳細は、アルゴリズム記憶領域３１１に記憶されているアルゴリズムに依存する。本実施の形態では、ＣＳ法の復号アルゴリズムが用いられる。
　一方、失効された端末装置３０１は、マルチキャストのメッセージを受信しても、復号に必要な暗号鍵を導出できないため、情報を得ることができない。
　以上の処理を行うことで、セキュアマルチキャストを実現することができる。

　なお、図８で表される鍵管理木を利用する上述の例では、最終的な全ノードの状態は図１３のようになり、太線で示したノードに対応する秘密情報で暗号化が行われる。
　図１２の規則は、２個の子ノードがいずれの種類の状態（正当、失効、未使用）であるかを解析し、子ノードの状態の組合せに応じて上位ノードの状態を決定するものである。
　例えば、図８において、端末０と端末４が割り当てられている葉ノードでは、両者ともに状態が正当なので、これら葉ノードの上位ノードである中間ノード（中間ノード１とする）は正当ノードとなる。また、この時点での暗号化は行われない。
　また、例えば、端末２が割り当てられている葉ノードとその右隣の端末が割り当てられていない葉ノードでは、失効と未使用の組合せとなるので、これら葉ノードの上位ノードである中間ノード（中間ノード２とする）は失効ノードとなる。そして、この中間ノード２の下位の正当ノードに割り当てられている秘密情報で暗号化が行われるが、中間ノード２の下位には正当ノードが存在しないので、暗号化は行われない。
　また、中間ノード１と中間ノード２では、正当と失効の組合せであるので、中間ノード１と中間ノード２の上位ノードは失効ノードとなる。このため、当該上位ノードの下位の正当ノードである中間ノード１に割り当てられている秘密情報を用いて端末０及び端末４に対する暗号化が行われる。

　このように、集合導出部２１５は、ｎ個のノードを配列の順に従ってｋ（２≦ｋ＜ｍ）個のノードごとのブロック（図１２の例では２個のノードごとのブロック）に分け、ブロックごとに、ブロック内のｋ個のノードにいずれの種類のノードが含まれているかを解析して、複数個の正当ノードをグループ化できるか否かを判断している。
　より具体的には、集合導出部２１５は、ブロック内のｋ個のノードのすべてが未使用ノードである場合にｋ個のノードの親ノードとして未使用ノードを指定し、ブロック内のｋ個のノードに失効ノードが含まれていない場合にｋ個のノードの親ノードとして正当ノードを指定し、ブロック内のｋ個のノードに失効ノードが含まれる場合にｋ個のノードの親ノードとして失効ノードを指定し、以降、同様の処理を繰り返す。
　そして、失効ノードが指定されるごとに、その子孫ノードのうち正当ノードであるものについて、失効ノードの子ノードである正当ノードに対応付けられている秘密情報を適用して暗号化を行う。

　鍵管理アルゴリズムの一つであるＣＳ法では、一度鍵管理木を作成するとその後ノードは追加されないため、端末の追加を行うためには、端末が割り当てられないノードをあらかじめ用意しておく必要がある。
　ＣＳ法ではこのノードを「正当」「失効」のいずれかの状態で管理せざるを得なかったが、本実施の形態のように「未使用」の状態で管理し、ＣＳ法に修正を加えたアルゴリズムを用いると、「未使用ノード」に対応する端末は存在しないので、「未使用ノード」を秘密情報の選択において考慮する必要がなく、正当な端末を部分集合の和として表す際の自由度が増し、結果的にマルチキャストの通信オーバーヘッドを削減することが可能となる。
　また、運用開始時・端末追加時に端末を割り当てるノードの選択を工夫することにより、システム全体を通しての通信オーバーヘッドを削減できるという効果が得られ、狭帯域でセキュアマルチキャストを行う際に有効である。

　なお、本実施の形態では、鍵管理構造へのノード追加を想定していないが、鍵管理構造へのノード追加を行う既存の方式と組み合わせることも可能である。

　また、本実施の形態では、鍵管理アルゴリズムとして、ＣＳ法をベースとしたものを利用しているが、ＳＤ法をベースとしたものを利用することも可能である。
　この場合、ステップＳ１００４における中間ノード状態決定において、中間ノードの状態として新たに「ＳＤノード」を導入し、図１４の状態決定規則を用いる。
　また、ステップＳ１００７では、最終的にルートノードが「正当ノード」もしくは「ＳＤノード」となった場合に、暗号部２１７がルートノードに対応する鍵でメッセージ（もしくはセッション鍵）を暗号化する。
　なお、図８で表される鍵管理木を利用する上述の例では、最終的な全ノードの状態は図１５のようになり、太線で示したノードに対応する鍵で暗号化が行われる。

　すなわち、ＳＤ法をベースとする場合は、ノードの状態として新たに「ＳＤノード」を導入したうえで、集合導出部２１５は、ブロック内のｋ個のノードのすべてが未使用ノードである場合にｋ個のノードの親ノードとして未使用ノードを指定し、ブロック内のｋ個のノードに失効ノードもＳＤノードも含まれていない場合にｋ個のノードの親ノードとして正当ノードを指定し、ブロック内のｋ個のノードに失効ノードとＳＤノードが合わせて１個だけ含まれている場合にｋ個のノードの親ノードとしてＳＤノードを指定し、ブロック内のｋ個のノードに失効ノードとＳＤノードが合わせて２個以上含まれている場合にｋ個のノードの親ノードとして失効ノードを指定し、以降、同様の処理を繰り返す。
　そして、失効ノードが指定されるごとに、その子孫ノードのうち正当・ＳＤノードであるものについて、失効ノードの子ノードである正当・ＳＤノードに対応付けられている秘密情報を適用して暗号化を行う。

　また、本実施の形態では、鍵管理アルゴリズムとして、木構造を用いた鍵管理を行う方式を利用しているが、直線状・円状・格子状・グラフ状など、任意の構造で鍵管理を行う方式を利用することも可能である。

　また、本実施の形態では、「（２）運用開始時の端末割り当て」において、ビット列を用いた規則的な割り当てを行っているが、端末が適切に分散されるものであれば、これ以外の確定的もしくは確率的な方法を用いても良い。

　また、本実施の形態では、木構造として２分木を利用しているが、３分木や４分木などを利用した場合でも、同様のセキュアマルチキャストを行うことが可能である。また、各ノードの子ノードの数が異なっていても良い。
　図１６は、３分木構造の鍵管理構造に対するＣＳ法をベースにした状態決定規則の例を示している。
　また、図１７は、３分木構造の鍵管理構造に対するＳＤ法をベースにした状態決定規則の例を示している。

　なお、本実施の形態では、各端末に格納する鍵の決定と、各端末へのメッセージ送信を同一のサーバ装置が行っているが、これらを別々の装置で行っても良い。

　以上、本実施の形態では、セキュアマルチキャストシステムにおいて、情報を送信するサーバが、情報を受信する複数の端末を管理するために、各ノードを正当・失効・未使用の３状態で管理し、この状態に基づいてマルチキャストのヘッダを決定することで、端末の追加を可能としつつ、マルチキャストの際に生じる通信オーバーヘッドを削減する方式を説明した。

　また、本実施の形態では、端末を鍵管理構造に追加する際、その後のセキュアマルチキャストの通信オーバーヘッドが最小になる箇所を選んで端末を割り当てる方式を説明した。

　また、本実施の形態では、運用開始時の正当端末を鍵管理構造上に分散配置する方式を説明した。

　また、本実施の形態では、ＣＳ法をベースとして秘密情報管理を行う方式及びＳＤ法をベースとして秘密情報管理を行う方式を説明した。

　最後に、実施の形態１に示したサーバ装置２０１のハードウェア構成例について説明する。
　図１９は、実施の形態１に示すサーバ装置２０１のハードウェア資源の一例を示す図である。
　なお、図１９の構成は、あくまでもサーバ装置２０１のハードウェア構成の一例を示すものであり、サーバ装置２０１のハードウェア構成は図１９に記載の構成に限らず、他の構成であってもよい。

　図１９において、サーバ装置２０１は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。
　ＣＰＵ９１１は、バス９１２を介して、例えば、ＲＯＭ（Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）９１３、ＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）９１４、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。
　更に、ＣＰＵ９１１は、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ　Ｄｉｓｋ　Ｄｒｉｖｅ）、コンパクトディスク装置９０５（ＣＤＤ）、プリンタ装置９０６、スキャナ装置９０７と接続していてもよい。また、磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカード（登録商標）読み書き装置などの記憶装置でもよい。
　ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置の一例である。
　通信ボード９１５、キーボード９０２、マウス９０３、スキャナ装置９０７、ＦＤＤ９０４などは、入力装置の一例である。
　また、通信ボード９１５、表示装置９０１、プリンタ装置９０６などは、出力装置の一例である。

　通信ボード９１５は、図１に示すように、ネットワークに接続されている。例えば、通信ボード９１５は、ＬＡＮ（ローカルエリアネットワーク）、インターネット、ＷＡＮ（ワイドエリアネットワーク）などに接続されていても構わない。

　磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。
　プログラム群９２３のプログラムは、ＣＰＵ９１１がオペレーティングシステム９２１、ウィンドウシステム９２２を利用しながら実行する。

　また、ＲＡＭ９１４には、ＣＰＵ９１１に実行させるオペレーティングシステム９２１のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。
　また、ＲＡＭ９１４には、ＣＰＵ９１１による処理に必要な各種データが格納される。

　また、ＲＯＭ９１３には、ＢＩＯＳ（Ｂａｓｉｃ　Ｉｎｐｕｔ　Ｏｕｔｐｕｔ　Ｓｙｓｔｅｍ）プログラムが格納され、磁気ディスク装置９２０にはブートプログラムが格納されている。
　サーバ装置２０１の起動時には、ＲＯＭ９１３のＢＩＯＳプログラム及び磁気ディスク装置９２０のブートプログラムが実行され、ＢＩＯＳプログラム及びブートプログラムによりオペレーティングシステム９２１が起動される。

　上記プログラム群９２３には、実施の形態１の説明において「・・・部」として説明している機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。

　ファイル群９２４には、実施の形態１の説明において、「・・・の判断」、「・・・の計算」、「・・・の算出」、「・・・の比較」、「・・・の生成」、「・・・の導出」、「・・・の抽出」、「・・・の更新」、「・・・の指定」、「・・・の登録」、「・・・の選択」等として説明している処理の結果を示す情報やデータや信号値や変数値やパラメータが、「・・・ファイル」や「・・・データベース」の各項目として記憶されている。
　「・・・ファイル」や「・・・データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示などのＣＰＵの動作に用いられる。
　抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリ、レジスタ、キャッシュメモリ、バッファメモリ等に一時的に記憶される。
　また、実施の形態１で説明しているフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、ＦＤＤ９０４のフレキシブルディスク、ＣＤＤ９０５のコンパクトディスク、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ等の記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。

　また、実施の形態１の説明において「・・・部」として説明しているものは、「・・・回路」、「・・・装置」、「・・・機器」であってもよく、また、「・・・ステップ」、「・・・手順」、「・・・処理」であってもよい。すなわち、「・・・部」として説明しているものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、実施の形態１の「・・・部」としてコンピュータを機能させるものである。あるいは、実施の形態１の「・・・部」の手順や方法をコンピュータに実行させるものである。

　このように、実施の形態１に示すサーバ装置２０１は、処理装置たるＣＰＵ、記憶装置たるメモリ、磁気ディスク等、入力装置たるキーボード、マウス、通信ボード等、出力装置たる表示装置、通信ボード等を備えるコンピュータであり、上記したように「・・・部」として示された機能をこれら処理装置、記憶装置、入力装置、出力装置を用いて実現するものである。

実施の形態１に係るセキュアマルチキャストシステムの構成例を示す図。実施の形態１に係るサーバ装置の構成例を示す図。実施の形態１に係る端末装置の構成例を示す図。実施の形態１に係る鍵管理構造の例を示す図。実施の形態１に係る端末装置が記憶するデータの例を示す図。実施の形態１に係る鍵管理構造の例を示す図。実施の形態１に係る鍵管理構造の例を示す図。実施の形態１に係る鍵管理構造の例を示す図。実施の形態１に係る鍵管理構造の例を示す図。実施の形態１に係るサーバ装置の動作例を示すフローチャート図。実施の形態１に係る鍵管理構造の例を示す図。実施の形態１に係るＣＳ法をベースにした状態決定規則の例を示す図。実施の形態１に係る鍵管理構造の例を示す図。実施の形態１に係るＳＤ法をベースにした状態決定規則の例を示す図。実施の形態１に係る鍵管理構造の例を示す図。実施の形態１に係るＣＳ法をベースにした状態決定規則の例を示す図。実施の形態１に係るＳＤ法をベースにした状態決定規則の例を示す図。実施の形態１に係るサーバ装置の動作例を示すフローチャート図。実施の形態１に係るサーバ装置及び端末装置のハードウェア構成例を示す図。

符号の説明

　１０１　ネットワーク、２０１　サーバ装置、２１１　アルゴリズム記憶領域、２１２　鍵管理構造生成部、２１３　端末配置部、２１４　鍵管理構造記憶領域、２１５　集合導出部、２１６　通信部、２１７　暗号部、３０１　端末装置、３１１　アルゴリズム記憶領域、３１２　秘密情報記憶領域、３１３　鍵導出部、３１４　通信部、３１５　暗号部。

Claims

　ｍ（ｍ≧２）個の通信装置の中からマルチキャスト送信の対象として選択された２個以上のマルチキャスト対象通信装置に、秘密情報を用いて暗号化された暗号化メッセージをマルチキャスト送信する情報処理装置であって、
　配列されたｎ（ｎ＞ｍ）個のノードが含まれる秘密情報管理構造を生成する秘密情報管理構造生成部と、
　前記秘密情報管理構造のｎ個のノードのうちのｍ個のノードに前記ｍ個の通信装置を割り当てるとともに、前記ｎ個のノードのうち通信装置が割り当てられていないノードを未使用ノードとして指定する装置割当て部と、
　前記装置割当て部による前記秘密情報管理構造への端末装置の割り当て結果に基づいて、前記マルチキャスト対象通信装置にマルチキャスト送信する暗号化メッセージの暗号化に用いる秘密情報を選択する秘密情報選択部とを有することを特徴とする情報処理装置。
　前記装置割当て部は、
　前記ｍ個の通信装置以外の新たな通信装置がマルチキャスト対象通信装置として選択された場合に、前記新たな通信装置を未使用ノードに割り当てることを特徴とする請求項１に記載の情報処理装置。
　前記情報処理装置は、更に、
　ｎ＋１個以上の秘密情報を記憶する秘密情報記憶部と、
　前記秘密情報記憶部に記憶されている秘密情報のうちｎ個の秘密情報をノード秘密情報として前記秘密情報管理構造のｎ個のノードに対応付けて管理し、前記秘密情報記憶部に記憶されている秘密情報のうちノード秘密情報以外の秘密情報をグループ化された複数個のノードに共通に適用されるグループ秘密情報として管理する秘密情報管理部とを有し、
　前記装置割当て部は、
　前記秘密情報管理構造のｎ個のノードのうちのｍ個のノードに前記ｍ個の通信装置を割り当てるとともに、前記ｍ個のノードのうちマルチキャスト対象通信装置が割り当てられているノードを正当ノードとして指定し、前記ｍ個のノードのうちマルチキャスト対象通信装置以外の通信装置が割り当てられているノードを失効ノードとして指定し、
　前記秘密情報選択部は、
　前記ｎ個のノードにおける正当ノードの位置と失効ノードの位置と未使用ノードの位置に基づき、複数個の正当ノードをグループ化できるか否かを判断し、グループ化できる複数個の正当ノードに対してはグループ秘密情報を適用し、グループ化できない正当ノードに対しては対応付けられているノード秘密情報を適用して、前記マルチキャスト対象通信装置にマルチキャスト送信する暗号化メッセージの暗号化に用いる秘密情報を選択することを特徴とする請求項１又は２に記載の情報処理装置。
　前記装置割当て部は、
　前記ｍ個の通信装置以外の新たな通信装置がマルチキャスト対象通信装置として選択された場合に、前記新たな通信装置を未使用ノードに割り当て、前記新たな通信装置が割り当てられた未使用ノードを正当ノードに変更することを特徴とする請求項３に記載の情報処理装置。
　前記装置割当て部は、
　前記新たな通信装置がマルチキャスト対象通信装置として選択された際に前記秘密情報管理構造のｎ個のノードにおいて未使用ノードが１つだけ存在する場合に、前記新たな通信装置を未使用ノードに割り当て、前記新たな通信装置が割り当てられた未使用ノードを正当ノードに変更し、
　前記秘密情報選択部は、
　前記装置割当て部により前記未使用ノードが正当ノードに変更された後の前記ｎ個のノードにおける正当ノードの位置と失効ノードの位置に基づき、複数個の正当ノードをグループ化できるか否かを判断することを特徴とする請求項４に記載の情報処理装置。
　前記秘密情報選択部は、
　前記新たな通信装置がマルチキャスト対象通信装置として選択された際に前記秘密情報管理構造のｎ個のノードにおいて未使用ノードが複数個存在する場合に、各々の未使用ノードに前記新たな通信装置が割り当てられた場合の前記ｎ個のノードにおける正当ノードの位置と失効ノードの位置と未使用ノードの位置に基づき、未使用ノードごとに、暗号化メッセージの暗号化に用いる秘密情報の数を算出し、算出した秘密情報の数が最小となる未使用ノードを選択し、
　前記装置割当て部は、
　前記秘密情報選択部により選択された未使用ノードに前記新たな通信装置を割り当てることを特徴とする請求項４に記載の情報処理装置。
　前記秘密情報選択部は、
　前記ｎ個のノードを配列の順に従ってｋ（２≦ｋ＜ｍ）個のノードごとのブロックに分け、ブロックごとに、ブロック内のｋ個のノードにいずれの種類のノードが含まれているかを解析して、複数個の正当ノードをグループ化できるか否かを判断することを特徴とする請求項３に記載の情報処理装置。
　前記秘密情報選択部は、
　ブロック内のｋ個のノードのすべてが未使用ノードである場合にｋ個のノードの親ノードとして未使用ノードを指定し、
　ブロック内のｋ個のノードに失効ノードが含まれていない場合にｋ個のノードの親ノードとして正当ノードを指定し、
　ブロック内のｋ個のノードに失効ノードが含まれる場合にｋ個のノードの親ノードとして失効ノードを指定し、
　以降、同様の処理を繰り返し、
　失効ノードが指定されるごとに、指定された失効ノードの子孫ノードにあたる複数個の正当ノードをグループ化することを特徴とする請求項７に記載の情報処理装置。
　前記秘密情報管理構造生成部は、
　最下位階層に前記ｎ個のノードが配置される複数階層のｋ分木構造の秘密情報管理構造を生成し、
　前記秘密情報記憶部は、
　前記秘密情報管理構造に含まれるノード数分の秘密情報を記憶し、
　前記秘密情報管理部は、
　前記秘密情報記憶部に記憶されている秘密情報のうちｎ個の秘密情報をノード秘密情報として前記秘密情報管理構造のｎ個のノードに対応付けて管理し、前記秘密情報記憶部に記憶されている秘密情報のうちノード秘密情報以外の秘密情報をグループ秘密情報として前記ｎ個のノード以外のノードに対応付けて管理し、
　前記秘密情報選択部は、
　グループ化された複数個の正当ノードに対して、祖先ノードである失効ノードの子ノードにあたる正当ノードに対応付けられているグループ秘密情報を適用することを特徴とする請求項８に記載の情報処理装置。
　前記秘密情報選択部は、
　所定の条件に合致するノードをＳＤ（Ｓｕｂｓｅｔ　Ｄｉｆｆｅｒｅｎｃｅ）ノードとして指定し、
　ブロック内のｋ個のノードのすべてが未使用ノードである場合にｋ個のノードの親ノードとして未使用ノードを指定し、
　ブロック内のｋ個のノードに失効ノードもＳＤノードも含まれていない場合にｋ個のノードの親ノードとして正当ノードを指定し、
　ブロック内のｋ個のノードに失効ノードとＳＤノードが合わせて１個だけ含まれている場合にｋ個のノードの親ノードとしてＳＤノードを指定し、
　ブロック内のｋ個のノードに失効ノードとＳＤノードが合わせて２個以上含まれている場合にｋ個のノードの親ノードとして失効ノードを指定し、
　以降、同様の処理を繰り返し、
　失効ノードが指定されるごとに、指定された失効ノードの子孫ノードにあたる複数個の正当ノードをグループ化することを特徴とする請求項７に記載の情報処理装置。
　前記秘密情報管理構造生成部は、
　最下位階層に前記ｎ個のノードが配置される複数階層のｋ分木構造の秘密情報管理構造を生成し、
　前記秘密情報記憶部は、
　前記秘密情報管理構造に含まれるノード数分の秘密情報を記憶し、
　前記秘密情報管理部は、
　前記秘密情報記憶部に記憶されている秘密情報のうちｎ個の秘密情報をノード秘密情報として前記秘密情報管理構造のｎ個のノードに対応付けて管理し、前記秘密情報記憶部に記憶されている秘密情報のうちノード秘密情報以外の秘密情報をグループ秘密情報として前記ｎ個のノード以外のノードに対応付けて管理し、
　前記秘密情報選択部は、
　グループ化された複数個の正当ノードに対して、祖先ノードである失効ノードの子ノードにあたる正当ノード及びＳＤノードのいずれかに対応付けられているグループ秘密情報を適用することを特徴とする請求項１０に記載の情報処理装置。
　前記装置割当て部は、
　正当ノードと失効ノードと未使用ノードが分散して配置されるように、前記ｍ個の通信装置を前記ｍ個のノードに割り当てることを特徴とする請求項３に記載の情報処理装置。
　ｍ（ｍ≧２）個の通信装置の中からマルチキャスト送信の対象として選択された２個以上のマルチキャスト対象通信装置に、秘密情報を用いて暗号化された暗号化メッセージをマルチキャスト送信するコンピュータに、
　配列されたｎ（ｎ＞ｍ）個のノードが含まれる秘密情報管理構造を生成する秘密情報管理構造生成処理と、
　秘密情報記憶領域に記憶されているｎ＋１個以上の秘密情報のうちｎ個の秘密情報をノード秘密情報として前記秘密情報管理構造のｎ個のノードに対応付けて管理し、前記秘密情報記憶領域に記憶されている秘密情報のうちノード秘密情報以外の秘密情報をグループ化された複数個のノードに共通に適用されるグループ秘密情報として管理する秘密情報管理処理と、
　前記秘密情報管理構造のｎ個のノードのうちのｍ個のノードに前記ｍ個の通信装置を割り当てるとともに、前記ｍ個のノードのうちマルチキャスト対象通信装置が割り当てられているノードを正当ノードとして指定し、前記ｍ個のノードのうちマルチキャスト対象通信装置以外の通信装置が割り当てられているノードを失効ノードとして指定し、前記ｎ個のノードのうち通信装置が割り当てられていないノードを未使用ノードとして指定する装置割当て処理と、
　前記ｎ個のノードにおける正当ノードの位置と失効ノードの位置と未使用ノードの位置に基づき、複数個の正当ノードをグループ化できるか否かを判断し、グループ化できる複数個の正当ノードに対してはグループ秘密情報を適用し、グループ化できない正当ノードに対しては対応付けられているノード秘密情報を適用して、前記マルチキャスト対象通信装置にマルチキャスト送信する暗号化メッセージの暗号化に用いる秘密情報を選択する秘密情報選択処理とを実行させることを特徴とするプログラム。