暗号鍵更新方法、暗号鍵更新装置、及び暗号鍵更新プログラム
【課題】更新後の鍵をグループ内にのみ安全に配布する。
【解決手段】例えば、グループＧ２，２の新たな鍵ｋ’２，２をグループＧ２，２の暗号鍵とグループＧ０，１の暗号鍵との連接のハッシュ値で暗号化してマルチキャストする。グループＧ２，２のグループヘッドは、これを受信し、ノードｎ以外のノードに転送する。これにより、ノードｎはグループＧ２，２から排除される。
【解決手段】例えば、グループＧ２，２の新たな鍵ｋ’２，２をグループＧ２，２の暗号鍵とグループＧ０，１の暗号鍵との連接のハッシュ値で暗号化してマルチキャストする。グループＧ２，２のグループヘッドは、これを受信し、ノードｎ以外のノードに転送する。これにより、ノードｎはグループＧ２，２から排除される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号鍵を利用し、複数の通信機器を用いて通信を行うネットワークにおいて、安全なネットワーク通信を実施するために必要となる暗号鍵の管理方法に関し、特に鍵の更新方法に着目した暗号鍵更新方法、暗号鍵更新装置、及び暗号鍵更新プログラムに関する。
【背景技術】
【０００２】
暗号鍵を利用し、複数の通信機器を用いて通信を行うネットワーク通信において、特に多数のセンサ搭載無線通信機器（ノード）を用いたネットワークは、一般にセンサネットワークとよばれ、測定対象エリア内に配置されたノードが取得した情報を、無線通信によって収集し、収集した情報をアプリケーションで活用するシステムであり、様々な用途に利用することができるシステムとして注目されている。
以下、本発明においては、暗号鍵を利用し、複数の通信機器を用いて通信を行うネットワーク通信において、構成する通信機器として、サーバ及びサーバと接続されたノードとにより構成されるようなネットワーク、特にセンサネットワークを例に説明を行う。
【０００３】
センサネットワーク利用の多くの局面において、複数のノードによってグループを構成し、グループ内で情報の共有や処理を行うケースが起こりうると考えられる。グループ鍵は、グループに属するノードだけが共通して所有する鍵であり、グループ鍵から暗号化鍵やＭＡＣ鍵を生成して利用することにより、グループ内での各種の暗号技術の利用が可能となる。その意味において、グループ鍵を安全かつ効率的に管理することは、現実的なセンサネットワークアプリケーション構築における重要な基礎技術であると考えることができる。たとえば、あるグループを対象として、秘密データのマルチキャスト配信を行う場合を考える。通信路を盗聴する不正者やデータを中継するグループ外ノードの存在を考慮すると、マルチキャスト配信されるデータは暗号化される必要がある。この際注意が必要なのは、マルチキャスト配信される暗号文は、グループ内ノード全てに対して同一でないといけない点である。もし、ノードごとに異なる暗号鍵を用い、異なる暗号文を構成する必要があるのであれば、マルチキャスト配信を行う意味がない。同一の暗号文を不特定多数がアクセスしうるネットワークに流通させ、グループに属するメンバだけが、その復号を行うことが可能となる仕組みを実現するためには、グループ鍵の存在が必須であると言える。
【０００４】
グループ鍵の管理は、一対一の暗号鍵管理とは異なる困難性を伴う課題を有する。グループ鍵の管理を特徴付ける大きな点として、グループの構成が時間進行に応じて変化する点があげられる。たとえば、新しいノードが新規にグループに参加したり、これまでグループに属していたノードが、なんらかの理由でグループから脱退したりする可能性があることに注意しなければならない。グループ構成員の変化があった場合には、グループ鍵を更新し、更新後の鍵を正しく配布する必要がある。とくに、あるノードを強制的にグループから排除する場合は、排除されるノードが有効なグループ鍵を所有し続けることのないよう、適切に情報の制御を行う必要がある。
【０００５】
センサネットワークを念頭に置いた鍵の更新方式として最も基本的なものは、たとえば非特許文献１に示されるように、サーバを含む任意のノード対間であらかじめ１対１に共有する鍵（リンク鍵）を用いた方式（従来方式１）がある。例えば、複数のノードで構成されるグループで１つのグループ鍵を共有している場合、あるノードを排除する際に鍵更新が必要になるが、従来方式１では、鍵更新を行う際サーバ等の代表ノードが、新しいグループ鍵を決定し、リンク鍵を用いてグループ鍵を暗号化し、暗号化したグループ鍵を、排除するノードを除くその他のノードにユニキャスト的に送信する。
【０００６】
また特許文献１には、あるグループに対応するグループ鍵を根とする木構造の拡頂点に複数の鍵を割り振り、次に複数のグループに加入させる全ノードを木構造の各頂点に配置された鍵と対応付け、ノードの個々の暗号鍵を木構造の根から、木構造の該ノードに対応付けられた位置に至る鍵を有する、鍵列として生成し、生成した暗号鍵を対応するノードへ配信する方式が開示されている。（従来方式２）。このような木構造により、複数のノードの中から、排除ノードが出た場合、排除ノードが有する暗号鍵に関連する鍵のみを変更して、変更された鍵に対応するノードにのみ、変更された暗号鍵を、その鍵の直下の鍵で暗号化して配信することができる。
【０００７】
また特許文献２には、複数のノードを各々が複数のグループに属するようにグループ化して構成されるネットワークシステムにおいて、グループ内の各ノード間を直接接続すると共に、各ノードが、それぞれ自ノードが属するグループの他の全てのノードに同報送信するノード接続手段を具備し、各ノードはそれぞれ自ノードが属する複数のグループのうちの１つのグループの他のノードから受信したデータを、自ノードが属する複数のグループのうちの他のグループの他のノードに同報送信によって中継する方式が開示されている。（従来方式３）。従来方式３を用いると、あるノードの集合に対して、共通のデータを送信するにあたって、各グループをまたがるノード（中継ノード）に対し、データを送信し、同報送信してもらうことによって、データを効率よく配信することができる。
【０００８】
また、特許文献３には、センター及び複数の端末から構成され、各端末がグループを形成しグループで同じ秘密鍵を共有する通信システムにおいて、秘密分散法などの剰余計算を用いて、秘密鍵を更新する方式が開示されている（従来方式４）。従来方式４は、センター側における暗号処理の負担を軽減することを目的とし、秘密分散法に基づき、端末側で剰余計算を行うことを必須として秘密鍵を更新することができる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開平１１−１８７０１３号公報
【特許文献２】特許第２８５２５８６号公報
【特許文献３】特開２００４−３４３８１６号公報
【非特許文献】
【００１０】
【非特許文献１】Ｚｉｇｂｅｅ(登録商標)センサネットワークｐｐ．１１８〜１２０、阪田史郎ら、秀和システム、２００５年
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、ネットワークを構成する通信機器において、チップやメモリの小型化が望まれるような、計算資源に制限があるネットワーク通信においては、安全に通信及び暗号鍵更新を行うことはもちろんのことながら、鍵更新における通信量の低減及び鍵更新による計算量の低減が求められる。
【００１２】
これに対し、従来方式１はサーバからネットワークに送信される通信量がグループ内のノード数をＮとしたとき通信量はＯ（Ｎ）となる。すなわちノード数に比例して鍵更新のための通信量が増大するという問題がある。一方、従来方式２では、この通信量はＯ（ｌｏｇ Ｎ）となる。すなわちノード数の対数に比例して鍵更新のための通信量が増大するという問題がある。従来方式１と比較して効率的であるが、ノード数が増大した場合に鍵更新のためのサーバからの通信量が問題になる点では同様の問題が生じる可能性がある。特にセンサネットワークのようなノード数が従来のシステムに比べ、桁違いに増加することが予想される環境では、通信量がノード数の対数に比例するとしても、本問題が顕在化することが予想される。
【００１３】
一方、従来方式３を暗号鍵の配送用の通信手段として用いることが考えられるが、中継ノードを排除する場合に対応することができないという問題がある。また中継ノードがグループ外ノードである可能性を考慮すると、中継ノードに暗号鍵情報が漏洩する危険もある。
【００１４】
また、従来方式４は秘密分散法に基づいた鍵更新方式であり，巨大な素数ｐのもとでの剰余計算や、大きな数の剰余演算などを用いた大きな計算量が必須とされる。このような剰余計算を用いてグループ鍵の鍵更新を行う方式では，公開鍵方式同様、一般的に非常に大きな計算量となる。しかし、特にセンサネットワークのようなノード側の通信機器に用いる計算資源において、実施可能な計算能力や記憶容量などに制限のある環境下では、ノード側での計算量が限られるために、従来方式４のような大きな数の剰余計算を要する方式は用いることができない。
【００１５】
よって、本発明は上記課題を解決し、暗号鍵を利用し、複数の通信機器を用いて通信を行うネットワーク通信において、通信機器におけるグループの構成が時間進行に応じて変化する場合にも備え、暗号鍵であるグループ鍵を更新し、更新後の鍵をグループ内に安全に配布する仕組みを提供するものであり、鍵更新における通信量及び計算量を低減することを目的とする。
【課題を解決するための手段】
【００１６】
本発明によれば、サーバと多数のノードから構成されるネットワークにおいて、ノードに属性がｄ種類存在する場合、ノードはｄ個のグループに同時に属すると考え、このように定義される各グループに対してグループ鍵を対応付け、サーバがグループ鍵をそのグループに属するノードとだけ共有して、各グループを対象とする暗号通信を実施する方法に関し、グループ構成員の変化があった場合に、サーバがグループ鍵を更新し、更新後の鍵を正しく配信する方法であって、特に、あるノードを強制的にグループから排除する場合に、排除されるノードが有効なグループ鍵を所有し続けることのないよう、適切にグループ鍵配信の制御を行う暗号鍵更新方法が提供される。
【発明の効果】
【００１７】
本発明によれば、暗号鍵を利用し、複数の通信機器を用いて通信を行うネットワーク通信において、ネットワーク構成が時間進行に応じて変化する場合にも備え、暗号鍵であるグループ鍵を更新し、更新後の鍵を安全に配布する仕組みを提供することができる。また、鍵更新における通信量及び計算量を低減することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明を実施するための一実施形態の構成を示す図である。
【図２】本発明における実施例を説明する図である。
【図３】ｎをグループＧｉ，ｊから排除する概要動作を示す流れ図である。
【図４】ｎをグループＧｉ，ｊ（ｉ≠０）から排除する動作を示す流れ図である。
【図５】ｎをグループＧｉ，ｊ（ｉ＝０かつｊ≠１）から排除する動作を示す流れ図である。
【図６】ｎをグループＧｉ，ｊ（ｉ＝０かつｊ＝１）から排除する動作を示す流れ図である。
【図７】ｎをグループＧｉ，ｊ（ｉ≠０）から排除する場合の例を示す図である。
【図８】ｎをグループＧｉ，ｊ（ｉ＝０かつｊ≠１）から排除する場合の例を示す図である。
【図９】ｎをグループＧｉ，ｊ（ｉ＝０かつｊ＝１）から排除する場合の例を示す図である。
【発明を実施するための形態】
【００１９】
以下、図面を参照して本発明を実施するための最良の形態について詳細に説明する。
【００２０】
一般に、一台のセンサノードには複数の属性が存在すると考えられる。例えば、製造ロット番号、ファームウェアのバージョン、設置場所、装備するセンサの種類等は、すべて属性となり得る。センサノードは、各属性に対してなんらかの属性値を有すると考えられる。
【００２１】
本発明は、ある属性に対して同じ属性値を持つノードの集合で、一つのグループを構成するとし、このように定義される各グループに対してグループ鍵を対応付け、グループ鍵を、そのグループに属するノードにだけ配布する暗号鍵管理方法である。
【００２２】
したがって、属性がｄ種類存在する場合、ノードはｄ個のグループに同時に属することとなる。このように定義される各グループに対してグループ鍵を対応付け、グループ鍵を、そのグループに属するノードにだけ配布することを考える。
【００２３】
本発明は、グループ構成員の変化があった場合に、グループ鍵を更新し、更新後の鍵を正しく配信する方法であって、特に、あるノードを強制的にグループから排除する場合に、排除されるノードが有効なグループ鍵を所有し続けることのないよう、適切にグループ鍵配信の制御を行う暗号鍵更新方法である。
【００２４】
図１に、本発明の暗号鍵管理方法の実施形態における全体構成を示す。図１を参照すると、本実施形態において、センサネットワークに代表されるネットワークにおいて、ノード全体からなる集合Ｎと、Ｎに属さないサーバ１０１から構成され、サーバ１０１は、プログラム制御により動作し、ノード追加手段１０３と主ノード排除手段１０５と鍵記憶手段１０７とを、ノードは副ノード排除手段１０９と鍵記憶手段１１１とを備える。ノードは代表的にノード１のみを表記している。サーバの鍵記憶手段１０７とノードの鍵記憶手段１１１の差異は鍵記憶手段に記憶管理する鍵（秘密情報）の差異であり、主にサーバは全グループのグループ鍵を管理するのに対し、ノードは自身の属するグループの中のみで有効なグループ鍵と、ノードのグループ加入および排除の処理の際に必要になる処理用の鍵（後述するメンバ鍵）のみを管理する。
【００２５】
ノードも鍵に関する動作などにおいては、プログラム制御により動作する。
【００２６】
以下、対称鍵暗号を用いたデータの暗号化操作を用いるが、暗号化に用いるアルゴリズムについてはネットワーク参加者が了解しているものとし、サーバ、各ノードは暗号化、復号を実行可能であり、特にサーバ、各ノードともに自身が所有する鍵で暗号化されている情報に関して、適した鍵で復号し復号結果を取得できるものとする。
【００２７】
また、属性をノード全体からなる集合Ｎの分割であるとし、特に、
Ｇｉ⊂Ｎ ．．．（条件１）
ｉ≠ｊならばＧｉ∩Ｇｊは空集合である ．．．（条件２）
Ｇ１∪Ｇ２∪．．．Ｇｍ ＝ Ｎ ．．．（条件３）
の３つの条件を満たす集合族｛Ｇ１， Ｇ２， ．．．， Ｇｍ｝を属性と呼ぶ。
【００２８】
また、ｄ個の属性Ａ１， ．．．， Ａｄを考え、Ａｉ＝｛Ｇｉ，１， ．．．， Ｇｉ，ｍｉ｝とし（ｍｉはＡｉの要素数）、Ｇｉ，ｊは、属性ｉについてｊ番目の属性値を持つノードの集合であるとしたとき、ｋ個の整数１≦ ｉ１， ．．．， ｉｋ ≦ ｄおよびｋ個のグループＧｉ１，ｊ１，．．．，Ｇｉｋ，ｊｋ（ただし、１≦ａ≦ｋに対してＧｉａ，ｊａ∈Ａｉａとする）が存在し、Ｇ＝Ｇｉ１，ｊ１∩．．． ∩Ｇｉｋ，ｊｋとなるノード集合Ｇを位数ｋのグループであるというとき、構造化グループ間の包含関係において極小の集合である位数ｄのグループＣ（極小グループ）を構成するｄ個の属性に加え、
任意の極小グループＣに対し、Ｃ∩Ｇ０，１がちょうど一個のノード（グループヘッド）を含む（条件４）、
任意の極小グループＣ，Ａ０におけるＧ０，１以外のグループＧ０，ｊに対し、Ｃ∩Ｇ０，ｊが高々一個のノード（グループメンバ）を含む（条件５）、
の２つを満たすように構成した特殊な属性Ａ０＝｛Ｇ０，１， ．．．， Ｇ０，ｍ０｝（ただしｍ０ ＞ ０）を導入して、ｄ＋１個の属性組Ａ０， Ａ１， ．．．， Ａｄで構成するｄ次元グループ構造でグループ鍵を更新管理する。
【００２９】
また、ノードはちょうど一個の極小グループに属すること、Ａ０は全ノード集合Ｎの分割になっていることより、任意のノードｎに対してｄ＋１個の整数組ｊ０， ｊ１， ．．．， ｊｄが存在し、Ｇ０，ｊ０ ∩Ｇ１，ｊ１ ∩．．． ∩Ｇｄ，ｊｄ＝｛ｎ｝と表すことができ、ｄ＋１字組（ｊ０， ｊ１， ．．．， ｊｄ） をノードｎの識別子（ＩＤ）として取り扱う。
【００３０】
また、Ａ０， Ａ１， ．．．， Ａｄがｄ次元グループ構造を定義する場合を考え、この時サーバは、位数１のグループＧｉ，ｊ（０≦ｉ≦ｄ， １≦ｊ≦ｍｉ） に属するノードとグループ鍵ｋｉ，ｊ（特に要素鍵と呼ぶ）をあらかじめ共有し、位数ｋのグループ Ｇ＝Ｇｉ１，ｊ１ ∩．．． ∩Ｇｉｋ，ｊｋ（ｉ１＜．．．＜ｉｋ）に対し、ｈ（ｋｉ１，ｊ１｜｜．．．｜｜ｋｉｋ，ｊｋ） （ｈはハッシュ関数などの連接鍵の長さを所定値にするための関数、｜｜は鍵の連接）としてサーバおよびノードで計算できる情報をＧのグループ鍵ｋ（Ｇ）とする。
【００３１】
また、位数ｋのグループＧのグループ鍵ｋ（Ｇ）を知るのはＧに属するノードのみであり、この時、サーバあるいはＧに属するノードは、Ｇに送信したいデータをｋ（Ｇ）により暗号化し、得られた暗号文をＧのノードに対してマルチキャスト配信する。
【００３２】
また、ノードｎのＩＤを（ｊ０， ｊ１， ．．．， ｊｄ）とすると、ｎはｄ＋１個の要素鍵 ｋ０，ｊ０， ．．．， ｋｄ，ｊｄを所有し、これらｄ＋１個の鍵を用いることにより、ｎはｋｎ＝ｈ（ｋ０，ｊ０｜｜．．．｜｜ｋｄ，ｊｄ）を計算することができ、この値ｋｎはｎおよびサーバだけが計算可能な値であるため、サーバはｋｎをｎとサーバとの間で共有された鍵（ノード鍵と呼ぶ）として、サーバは、各ノードに対してそれぞれのノード鍵でデータを暗号化してユニキャスト的に送信する。
【００３３】
また、グループヘッドとそのグループヘッドの属する極小グループの各グループメンバとの間で安全に一対一のメッセージの交換を行うことを可能とするため、サーバは、グループヘッドと各グループメンバに対して、それぞれのノード鍵で共通のユニークな鍵（メンバ鍵）を暗号化してユニキャスト的に送信する。
【００３４】
ノードｎを、位数１のグループＧｉ，ｊに追加する手段（ノード追加手段）は以下のようになる。たとえば、新しいノードを稼働中のセンサネットワークに追加したい場合や、既存のノードの属性値がなんらかの理由で変更される場合等、このようなケースが発生しうる。いずれにせよ、新しくグループに参加するノードｎは、自分が参加する以前にＧｉ，ｊのグループ鍵として使われていた鍵を知る権利はない。逆に、ｎをグループのメンバとして追加する過程において、ｎが以前のグループ鍵を知ることがあってはならない。この性質をグループ鍵における後方安全性(backward security)と呼ぶ。
【００３５】
また、サーバがノードｎを位数１のグループＧｉ，ｊに追加したいとき、データｘを鍵ｋにより暗号化して得られる暗号文をＥｋ（ｘ）と書くこととすると、サーバに備えるノード追加手段は、Ｇｉ，ｊに以前から所属するノードには、ｃ＝Ｅｈ（ｋｉ，ｊ）（ｋ’ｉ，ｊ）を計算し、ｃをＧｉ，ｊに属するノードに対してマルチキャスト配信し、ｎに対してはユニキャスト的に新しい鍵ｋ’ｉ，ｊをサーバとそのノードだけで共有するノード鍵で暗号化してサーバから伝達することで、後方安全性を確保しつつ、新しい鍵ｋ’ｉ，ｊを新しいグループＧｉ，ｊで共有する。
【００３６】
それまでグループＧｉ，ｊに属していたノードを、Ｇｉ，ｊから排除する手段（ノード排除手段）は以下のようになる。あるノードをグループから排除するケースとしては、ノードの属性値が変化した場合、故障等によって停止したノードをネットワークから除外する場合、そして、あるノードが不正者に乗っ取られたおそれがある場合等が考えられる。とくに最後のケースでは、乗っ取られたノードを通じて秘密情報がリークしたり、乗っ取られた情報が他のノードや通信基盤に対してさらなる攻撃を行うことも考えられるため、できるだけ早急にノードを排除することが強く求められる。この際、グループから排除されるノードは、不正な手段によってグループ鍵を保持しようとし続ける可能性がある点に注意しなければならない。ノードを排除するプロトコルにおいては、Ｇｉ，ｊに継続して残るノードには新しい鍵ｋ’ｉ，ｊを確実に配信し、排除されるユーザにはｋ’ｉ，ｊ（および、その後に使用されるグループ鍵）が渡らないようにしなければならない。この性質を、グループ鍵における前方安全性(forward security)と呼ぶ。
【００３７】
前方安全性の確保は、後方安全性の確保に比べて、技術的な困難性が高い。実際、Ｇｉ，ｊに継続して残るノードと、排除されるノードｎとの間には、鍵に関する知識に関し、本質的な差異があるわけではない。たとえば、Ｇｉ，ｊに残るノードも ｎ 自身も、Ｇｉ，ｊにおいてこれまで使用されていたグループ鍵ｋｉ，ｊを知っている。したがって、前節のノード追加のように、古いグループ鍵ｋｉ，ｊを利用して新しい鍵ｋ’ｉ，ｊの配布を行う、といった単純な方法では前方安全性の確保は困難である。
【００３８】
また、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、Ｇｉ，ｊからｎを除いた集合をＧ’ｉ，ｊと書くと、Ｇ’ｉ，ｊは、ｎの排除後もグループにとどまるノード集合であり、Ｇ’ｉ，ｊに属するすべてのノードは、新しい鍵ｋ’ｉ，ｊを入手できなければならず、かつ、前方安全性を確保するため、排除されるノードｎがｋ’ｉ，ｊを知ることがないようにしなければならないため、サーバに備える主ノード排除手段は、極小グループに必ず一個存在するグループヘッドの備える副ノード排除手段と連携して、ノード排除の処理を実施する。
【００３９】
サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、サーバに備える主ノード排除手段は、排除ノードｎがグループヘッドでない場合に、ｎを排除する位数１のグループＧｉ，ｊについて、ｉ≠０である場合と、ｉ＝０である場合（後者の場合、ｎがグループヘッドでないので、自動的にｊ≠１となる）とで、グループヘッドとなるノードの備える副ノード排除手段は処理を分岐する。
【００４０】
サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、排除ノードｎがグループヘッドでなく、ｎを排除する位数１のグループＧｉ，ｊについてｉ≠０である場合、位数１のグループＧｉ，ｊはいくつかの極小グループに分割され、排除されるノードｎは、その中の一つの極小グループに属することとなるので、基本的な考え方として、Ｇｉ，ｊ ∩Ｇ０，１に属するノード（Ｇｉ，ｊに属するグループヘッド）に新しい鍵ｋ’ｉ，ｊを配送し、各グループヘッドからグループメンバに対して鍵ｋ’ｉ，ｊを転送する。
【００４１】
即ち、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、排除ノードｎがグループヘッドでなく、ｎを排除する要素グループＧｉ，ｊについてｉ≠０である場合、サーバの主ノード排除手段は、まず、ｋｉ，ｊをＧｉ，ｊ の要素鍵、ｋ’ｉ，ｊ は新しいＧｉ，ｊ の要素鍵としたとき、ｋ＝ｈ（ｋ０，１｜｜ｋｉ，ｊ） を計算し、ｘ ＝Ｅｋ（ｋ’ｉ，ｊ） を求め、４字組 （ｉ， ｊ， ＩＤｎ， ｘ） をＧｉ，ｊ ∩Ｇ０，１に属するノード（グループヘッド）向けにマルチキャスト送信し（ＩＤｎは排除されるノードｎのＩＤ）、その後、Ｇｉ，ｊ ∩Ｇ０，１に属するノード（グループヘッド）の副ノード排除手段は，ｘを復号してＧｉ，ｊの新しい鍵 ｋ’ｉ，ｊを入手し、最後に、Ｇｉ，ｊ ∩Ｇ０，１に属するノード（グループヘッド）の副ノード排除手段は、自ノードの属する極小グループＣに排除ノードｎを含まないとき、ｋ（Ｃ） （自身の属する極小グループＣのグループ鍵）を用いてｋ’ｉ，ｊを暗号化し、Ｅｋ（Ｃ）（ｋ’ｉ，ｊ）をＣのグループメンバに向けてマルチキャスト配信する一方、グループヘッドの属する極小グループＣに排除ノードｎが含まれるとき、グループヘッドの副ノード排除手段が、ｎ以外のＣのグループメンバ全員に対してメンバ鍵を用いてユニキャスト的にｋ’ｉ，ｊを暗号化して送信する。
【００４２】
サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、排除ノードｎがグループヘッドでなく、ｎを排除する要素グループＧｉ，ｊについてｉ＝０かつｊ≠１である場合、Ｇｉ，ｊ＝Ｇ０，ｊとなり、グループＧｉ，ｊは極小グループに分割することはできない。また、グループヘッドの集合Ｇ０，１とＧｉ，ｊは互いに素である（共通集合を持たない）ため、グループヘッドに新しい要素鍵ｋ’ｉ，ｊを露出してはならない。
【００４３】
即ち、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、排除ノードｎがグループヘッドでなく、ｎを排除する要素グループＧｉ，ｊについて、ｉ＝０かつｊ≠１である場合、サーバの主ノード排除手段は、ｘ１＝Ｅｈ（ｋ０，ｊ）（ｋ’０，ｊ）およびｘ２＝Ｅｈ（ｋ０，１）（ｘ１）を計算し、４字組 （０， ｊ， ＩＤｎ， ｘ２） をグループヘッドの集合 Ｇ０，１ にマルチキャスト配信し、各グループヘッドの副ノード排除手段はｘ２ を復号して ｘ１ を得て（グループヘッドは ｋ０，ｊ を知らないため、ｘ１ を復号することはできない）、Ｇ０，ｊと自身の属する極小グループＣとの積集合に、ノードｎ’が一個含まれ、かつｎ≠ｎ’であれば、グループヘッドの副ノード排除手段が、ｎ’にメンバ鍵でユニキャスト的にｘ１を暗号化して送信する。
【００４４】
また、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、ｎを排除するグループＧｉ，ｊのグループヘッドｎと、そのグループヘッドが属する極小グループ内のノードｎ’との役割を交換する処理を実施し、役割交換処理終了後に排除ノードがグループヘッドでない場合のノード排除処理を施行する。
【００４５】
また、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、ノードの役割交換処理は、グループヘッドｎ、とノードｎ’∈Ｇ０，ｊ（ｊ ≠１）は同一の極小グループに属するものとして、サーバの主ノード排除手段は、まず、Ｇ０，１の要素鍵を更新し、新しい要素鍵ｋ’０，１をＧ０，１からｎを除いたノード集合Ｇ’０，１＝Ｇ０，１＼｛ｎ｝に配信し、その後、Ｇ０，ｊの要素鍵を更新し、新しい要素鍵ｋ’０，ｊをＧ０，ｊからｎ’を除いたノード集合Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ’｝に配信し、最後にｋ’０，１， ｋ’０，ｊをそれぞれｎ’， ｎ に送信する３つの処理からなる。
【００４６】
また、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、まずＧ０，１の要素鍵を更新し、新しい要素鍵ｋ’０，１をＧ０，１からｎを除いたノード集合Ｇ’０，１＝Ｇ０，１＼｛ｎ｝に配信するために、Ｇ’０，１に属する各ノードに対してサーバからユニキャスト的に鍵ｋ’０，１を暗号配信する。
【００４７】
ここで、従来方式２のような方式でＧ０，１を構造化し、Ｇ’０，１に属する各ノードに対してｋ’０，１を配信しても良い。
【００４８】
また、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、Ｇ０，ｊの要素鍵を更新し、新しい要素鍵ｋ’０，ｊをＧ０，ｊからｎ’を除いたノード集合Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ’｝に配信するために、ｘ１＝Ｅｋ０，ｊ（ｋ’０，ｊ）およびｘ２＝Ｅｋ’０，１（ｘ１）を計算し、ｘ２をＧ’０，１のノードに対してマルチキャスト配信し、Ｇ’０，１に属するノード（グループヘッド）の副ノード排除手段はｘ２を復号してｘ１を入手し、Ｇ’０，１に属するノード（グループヘッド）の属する極小グループ内にＧ’０，ｊのノードが存在すれば、グループヘッドの副ノード排除手段が、Ｇ’０，ｊのノードのノード排除手段にユニキャスト的にメンバ鍵でｘ１を暗号化して送信する。
【００４９】
役割交換にともなってＧ０，ｊを離れるノードｎ’については、Ｇ０，１の要素鍵を更新し、新しい要素鍵ｋ’０，１をＧ０，１からｎを除いたノード集合Ｇ’０，１＝Ｇ０，１＼｛ｎ｝に配信した時点で対応する（正当な鍵 ｋ’０，１を保持する）グループヘッドが存在していないため、新しい鍵ｋ’０，ｊの配信を受けることはできない。結果として、Ｇ０，ｊの要素鍵を更新し、新しい要素鍵ｋ’０，ｊをＧ０，ｊからｎ’を除いたノード集合Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ’｝に配信する処理が正しく実現されたことになる。
【００５０】
また、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、ｋ’０，１， ｋ’０，ｊをそれぞれｎ’， ｎに送信するために、ｎ’， ｎにユニキャスト的にｋ’０，１， ｋ’０，ｊをノード鍵で暗号化して送信する。
【実施例】
【００５１】
次に本発明の実施例について、図面を参照して詳細に説明する。ノードは図２に参照されるような、クラスタツリートポロジのネットワークを構成しているとする。ここでクラスタツリートポロジとは、サーバを根ノードとして、根ノード以外のすべての内部ノードについて、その子の中に高々一個の内部ノードしか存在しないツリーのことをいう。クラスタツリーにおいて、一つの内部ノードと、その内部ノードの子の中で葉ノードであるものから構成されるノード集合で一つのクラスタを構成する。クラスタツリートポロジ上では、各ノードの属性として、クラスタツリーにおける何番目の幹に属するかという情報および根ノードからの深さ、クラスタ内で何番目のノードであるかという順序情報を定義できる。クラスタ内での順序情報を特殊な属性Ａ０＝｛Ｇ０，１， Ｇ０，２， Ｇ０，３， Ｇ０，４｝と考えると，幹属性Ａ１＝｛Ｇ１，１， Ｇ１，２， Ｇ１，３｝，深さ属性Ａ２＝｛Ｇ２，１， Ｇ２，２｝で特定できる２次元グループ構造と定義できる。クラスタが２次元グループ構造における極小グループとなる。
【００５２】
この時、ノードｎをグループＧｉ，ｊから排除するときのフローチャートは図３のようになる。図３のＳ３１にてｉ≠０のとき、Ａ１，Ａ２の属性のうちＧ１，１， Ｇ１，２， Ｇ１，３， Ｇ２，１， Ｇ２，２のいずれかの属性値を持つノードの集合からノードｎを排除する処理を実施する。この時、排除するノードはグループヘッドではないので、Ｇｉ，ｊ∩Ｇ０，１に属するノード（Ｇｉ，ｊのグループヘッド）に新しい鍵ｋ’ｉ，ｊを配送し、各グループヘッドからグループメンバに対してｋ’ｉ，ｊを転送する（Ｓ３２）。具体的な処理のフローを図４に示している。まず、サーバがＥ ｈ（ｋ０，１｜｜ｋｉ，ｊ） （ｋ’ｉ，ｊ）を計算し、計算結果をマルチキャストする（Ｓ３１１）。その後、Ｇｉ，ｊ内のグループヘッドだけが本計算結果を復号可能であり、復号してｋ’ｉ，ｊを入手する（Ｓ３１２）。最後に、グループヘッドがＧ’ｉ，ｊ＝Ｇｉ，ｊ＼｛ｎ｝のノードにだけｋ’ｉ，ｊを、グループメンバとの間で共有するメンバ鍵で暗号化してユニキャストして（Ｓ３１３）、処理を終える。
【００５３】
次に、図３のＳ３１にてｉ＝０のとき、Ｓ３３にてｊ≠１ならば、Ａ０の属性のうちＧ０，２あるいはＧ０，３あるいはＧ０，４の属性値を持つノードの集合からノードｎを排除する処理を実施する。この時、Ｇｉ，ｊ ＝Ｇ０，ｊとなりグループヘッドの集合Ｇ０，１とＧｉ，ｊは互いに素（共通集合）を持たないため、グループヘッドにｋ’ｉ，ｊを露出することなく、各グループヘッドからグループメンバに対してｋ’ｉ，ｊを転送する（Ｓ３４）。具体的な処理のフローを図５に示している。まず、サーバがｘ１＝Ｅｈ（ｋ０，ｊ）（ｋ’０，ｊ）を計算し（ｊ≠１） 、ｘ２＝Ｅｈ（ｋ０，１）（ｘ１）をマルチキャストする（Ｓ３４１）。そして、Ｇ０，ｊ内のグループヘッドだけがｘ２を復号可能であり、復号してｘ１を入手する（Ｓ３４２）。グループヘッドはｘ１の復号はできない。その後、グループヘッドがＧ０，ｊ からｎを除いたノード集合Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ｝に属するノードにだけｘ１ をメンバ鍵で暗号化してユニキャストする（Ｓ３４３）。最後に、Ｇ’０，ｊのノードがｘ１をｋ０，ｊを用いて復号し（Ｓ３４４）、処理を終える。
【００５４】
最後に、図３のＳ３１にてｉ＝０のとき、Ｓ３３にてｊ＝１ならば、Ａ０の属性のうちＧ０，１の属性値を持つノードの集合からノードｎを排除する処理を実施する。このときｎはグループヘッドであり、グループヘッドｎと、そのグループヘッドが属する極小グループ内のグループメンバｎ’∈Ｇ０，ｊ（ｊ≠１）との役割を交換する処理を実行し、その後上記の（排除ノードがグループヘッドでない場合の）鍵更新を実行する（Ｓ３５）。具体的な処理のフローを図６に示している。まず、サーバがｋ’０，１をサーバと各ノードに固有なノード鍵で暗号化し、Ｇ０，１からｎを除いたノード集合Ｇ’０，１＝Ｇ０，１＼｛ｎ｝ に含まれるすべてのノードにユニキャストする（Ｓ３５１）。そして、サーバがｘ１ ＝Ｅｈ（ｋ０，ｊ）（ｋ’０，ｊ）を計算し（ｊ≠１）、ｘ２＝Ｅｈ（ｋ’０，１）（ｘ１）をマルチキャストする（Ｓ３５２）。そして、Ｇ’０，１に属するグループヘッドはｘ２を復号してｘ１を入手し（Ｓ３５３）、Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ’｝のノードにｘ１を暗号化してユニキャストする（Ｓ３５４）。その後、Ｇ’０，ｊのノードがｘ１をｋ０，ｊを用いて復号する（Ｓ３５５）。最後に、サーバがｎ’， ｎ にｋ’０，１， ｋ’０，ｊをノード鍵で暗号化してユニキャストして（Ｓ３５６）、役割交換の処理を終了する。この時点で、グループヘッドｎはグループメンバｎ’とその役割を交代し、グループメンバとなる（グループヘッドの集合Ｇ０，１の鍵を所有しなくなる）。その後、図５に示す排除ノードがクラスタヘッドでない場合のノード排除処理を実施してｎを排除し（Ｓ３５７）、処理を終える。
【００５５】
図７は、図４に示す鍵更新処理１の一例として、グループＧ２，２の全ノードのうちグループヘッドノード以外の或るノード（グループＧ２，２且つグループ０，ｉ（ｉ≠０）（例として、ｉ＝４）且つグループ１，ｊ（例として、ｊ＝３）のノード）をグループＧ２，２から排除する例を示す図である。
【００５６】
図７を参照すると、まず、新たな鍵ｋ’２，２を鍵ｋ０，１と鍵２，２とを連接することにより得た鍵のハッシュ値により暗号化し、これをマルチキャストする（図４のステップ３１１）。マルチキャストする鍵には、ノードｎ（グループ０，４且つグループＧ１，３且つグループ２，２に属するノード）の鍵は更新しないという情報を付加しておく。
【００５７】
そうすると、鍵ｋ０，１と鍵２，２とを保有しているグループ２，２のグループヘッドノードがこれを受信して、鍵ｋ’２，２を得る（図４のステップ３１２）。 次に、グループヘッドノードは、自己の配下にあるノードに鍵ｋ’２，２を転送するが、上述した付加情報により特定されるノードには、例外として、鍵ｋ’２，２を転送しない（図４のステップＳ３１３）。
【００５８】
グループ２，１からあるノードを排除する場合の処理とグループ１、ｊ（ｊ＝１〜３）からあるノードを排除する場合の処理は、図７の場合の処理（グループ２，２からあるノードを排除する場合の処理）と同様である（鍵更新処理１である）ので、説明を省略する。
【００５９】
図８は、図５に示す鍵更新処理２の一例として、グループＧ０，３の或るノード（例として、グループＧ０，３且つグループＧ１，１且つグループＧ２，１に属するノード）をグループＧ０，３から排除する例を示す図である。
【００６０】
図８を参照すると、まず、新たな鍵ｋ’０，３を鍵ｋ０，３のハッシュ値により暗号化して、ｘ１を得る（図５のステップＳ３４１の前半部）。次に、ｘ１を鍵ｋ０，１のハッシュ値により暗号化して、ｘ２を得る。そして、ｘ２をマルチキャストする（図５のステップＳ３４１の後半部）。マルチキャストするｘ２には、ノードｎ（グループＧ０，３且つグループＧ１，１且つグループＧ２，１に属するノード）の鍵は更新しないという情報を付加しておく。
【００６１】
そうすると、鍵ｋ０，１を保有しているグループヘッドノードがこれを受信して、ｘ１を得る（図５のステップＳ３４２）。
【００６２】
次に、グループヘッドは、自己の配下にあるノードにｘ１をマルチキャストする。但し、付加情報により特定されたノードにはマルチキャストしない（ステップＳ３４３）。
【００６３】
そうすると、鍵ｋ０，３を保有しているグループＧ０，３のノードがｘ１を受信し、ｋ’０，３を取得する（図５のステップＳ３４４）。但し、付加情報により特定されたノードはグループＧ０，３に属しているが、マルチキャストの対象から外されているので、ｋ’０，３を取得することができない。
【００６４】
グループＧ０，２からあるノードを排除する場合の処理とグループＧ０，４からあるノードを削除する場合の処理は、図８の場合の処理動作と同様である（鍵更新処理２である）ので、説明を省略する。
【００６５】
図９は、図６に示す鍵更新処理３の一例（グループヘッドノード（グループＧ０，１に属するノード）を排除する例）として、グループＧ１，３且つグループＧ２，２のグループのグループヘッドノードｎ（グループＧ１，３且つグループＧ２，２且つグループ０，１に属するノード）を排除する例を示す図である。
【００６６】
図９を参照すると、まず、グループＧ１，３且つグループＧ２，２のグループのグループヘッドノードｎとそのグループの他のノードｎ’（例えば、グループＧ０，３に属するノード）とを交換する。この交換処理は、ステップＳ３５１、Ｓ３５２、Ｓ３５３、Ｓ３５５、Ｓ３５６を有する。
【００６７】
まず、グループＧ１，３且つグループＧ２，２のグループ以外の５つのグループのグループヘッドノードそれぞれに新たな鍵ｋ’０，１を暗号化してユニキャストする（図６のステップＳ３５１）。
【００６８】
次に、新たな鍵ｋ’０，３を鍵ｋ０，３のハッシュ値で暗号化することによりｘ１を生成し（図６のＳ３５２の前半部）、更に、ｘ１をｋ’０，１のハッシュ値で暗号化することによりｘ２を生成し、ｘ２をマルチキャストする（図６のＳ３５２の後半部）。
【００６９】
そうすると、グループＧ１，３且つグループＧ２，２のグループ以外の５つのグループのグループヘッドノードは、鍵ｋ’０，１を保有しているため、ｘ１を復号することができる（図６のステップＳ３５３）。他方、グループＧ１，３且つグループＧ２，２のグループのグループヘッドは鍵ｋ’０，１を保有していないためｘ１を復号することができない。
【００７０】
ｘ１を復号することができた、グループＧ１，３且つグループＧ２，２のグループ以外の５つのグループのグループヘッドノードは、配下のノードにｘ１を送信する（図６のステップＳ３５４）が、鍵０，３を保有しているノード（Ｇ０，３に属するノード）のみがｘ１を復号して、ｋ’０，３を得ることができる（図６のステップＳ３５５）。他方、グループＧ１，３且つグループＧ２，２ではグループヘッドノードがｘ１を復号することができないため、このグループ内のノードはｋ’０，３を得ることができない。
【００７１】
次に、鍵ｋ’０，１をグループヘッドノードｄとなったノードｎ’にユニキャストし、鍵ｋ’０，３をグループヘッドノードｄでなくなったノードｎにユニキャストする（図６のステップＳ３５６）。
【００７２】
この後、ノードｎを排除するために図８に示す方法を実施する（図６のステップＳ３５７）。
【産業上の利用可能性】
【００７３】
よって、本発明によれば、従来方式に比べ、ノード排除時の鍵更新時の通信量を大きく削減することができる。例えば、グループ鍵の更新処理において、サーバからの通信はグループヘッド宛のマルチキャスト配信１回で済み、グループヘッドからは最大でも（そのグループヘッドの属する極小グループのノード数−１）回のユニキャスト通信で鍵更新を行うことができる。極小グループはノード集合の包含関係において極小であるので、大変効率的に処理を行うことが可能である。
【００７４】
また、本発明によれば、役割交換処理を用いることにより、グループヘッドに相当するノード排除による鍵更新を行うことができる。
【００７５】
また、本発明によれば、従来方式に比べ、より少ない計算量で鍵更新を行うことが可能である。よって、例えばセンサネットワークのような計算資源に制限のある環境下においても鍵更新に伴う計算量を低減し、安全に鍵更新を行うことができる。
【００７６】
以上、本発明は、暗号鍵を利用し、複数の通信機器を用いて通信を行うネットワーク通信において、構成する通信機器として、サーバ及びサーバと接続されたノードとにより構成されるようなネットワーク、特にセンサネットワークを例に説明を行ったが、特にこのようなネットワークに限られることはなく様々なネットワーク通信に応用できることはいうまでもない。
【符号の説明】
【００７７】
１０１ サーバ
１０３ ノード追加手段
１０５ 主ノード排除手段
１０７ 鍵記憶手段
１０９ 副ノード排除手段
１１１ 鍵記憶手段
【技術分野】
【０００１】
本発明は、暗号鍵を利用し、複数の通信機器を用いて通信を行うネットワークにおいて、安全なネットワーク通信を実施するために必要となる暗号鍵の管理方法に関し、特に鍵の更新方法に着目した暗号鍵更新方法、暗号鍵更新装置、及び暗号鍵更新プログラムに関する。
【背景技術】
【０００２】
暗号鍵を利用し、複数の通信機器を用いて通信を行うネットワーク通信において、特に多数のセンサ搭載無線通信機器（ノード）を用いたネットワークは、一般にセンサネットワークとよばれ、測定対象エリア内に配置されたノードが取得した情報を、無線通信によって収集し、収集した情報をアプリケーションで活用するシステムであり、様々な用途に利用することができるシステムとして注目されている。
以下、本発明においては、暗号鍵を利用し、複数の通信機器を用いて通信を行うネットワーク通信において、構成する通信機器として、サーバ及びサーバと接続されたノードとにより構成されるようなネットワーク、特にセンサネットワークを例に説明を行う。
【０００３】
センサネットワーク利用の多くの局面において、複数のノードによってグループを構成し、グループ内で情報の共有や処理を行うケースが起こりうると考えられる。グループ鍵は、グループに属するノードだけが共通して所有する鍵であり、グループ鍵から暗号化鍵やＭＡＣ鍵を生成して利用することにより、グループ内での各種の暗号技術の利用が可能となる。その意味において、グループ鍵を安全かつ効率的に管理することは、現実的なセンサネットワークアプリケーション構築における重要な基礎技術であると考えることができる。たとえば、あるグループを対象として、秘密データのマルチキャスト配信を行う場合を考える。通信路を盗聴する不正者やデータを中継するグループ外ノードの存在を考慮すると、マルチキャスト配信されるデータは暗号化される必要がある。この際注意が必要なのは、マルチキャスト配信される暗号文は、グループ内ノード全てに対して同一でないといけない点である。もし、ノードごとに異なる暗号鍵を用い、異なる暗号文を構成する必要があるのであれば、マルチキャスト配信を行う意味がない。同一の暗号文を不特定多数がアクセスしうるネットワークに流通させ、グループに属するメンバだけが、その復号を行うことが可能となる仕組みを実現するためには、グループ鍵の存在が必須であると言える。
【０００４】
グループ鍵の管理は、一対一の暗号鍵管理とは異なる困難性を伴う課題を有する。グループ鍵の管理を特徴付ける大きな点として、グループの構成が時間進行に応じて変化する点があげられる。たとえば、新しいノードが新規にグループに参加したり、これまでグループに属していたノードが、なんらかの理由でグループから脱退したりする可能性があることに注意しなければならない。グループ構成員の変化があった場合には、グループ鍵を更新し、更新後の鍵を正しく配布する必要がある。とくに、あるノードを強制的にグループから排除する場合は、排除されるノードが有効なグループ鍵を所有し続けることのないよう、適切に情報の制御を行う必要がある。
【０００５】
センサネットワークを念頭に置いた鍵の更新方式として最も基本的なものは、たとえば非特許文献１に示されるように、サーバを含む任意のノード対間であらかじめ１対１に共有する鍵（リンク鍵）を用いた方式（従来方式１）がある。例えば、複数のノードで構成されるグループで１つのグループ鍵を共有している場合、あるノードを排除する際に鍵更新が必要になるが、従来方式１では、鍵更新を行う際サーバ等の代表ノードが、新しいグループ鍵を決定し、リンク鍵を用いてグループ鍵を暗号化し、暗号化したグループ鍵を、排除するノードを除くその他のノードにユニキャスト的に送信する。
【０００６】
また特許文献１には、あるグループに対応するグループ鍵を根とする木構造の拡頂点に複数の鍵を割り振り、次に複数のグループに加入させる全ノードを木構造の各頂点に配置された鍵と対応付け、ノードの個々の暗号鍵を木構造の根から、木構造の該ノードに対応付けられた位置に至る鍵を有する、鍵列として生成し、生成した暗号鍵を対応するノードへ配信する方式が開示されている。（従来方式２）。このような木構造により、複数のノードの中から、排除ノードが出た場合、排除ノードが有する暗号鍵に関連する鍵のみを変更して、変更された鍵に対応するノードにのみ、変更された暗号鍵を、その鍵の直下の鍵で暗号化して配信することができる。
【０００７】
また特許文献２には、複数のノードを各々が複数のグループに属するようにグループ化して構成されるネットワークシステムにおいて、グループ内の各ノード間を直接接続すると共に、各ノードが、それぞれ自ノードが属するグループの他の全てのノードに同報送信するノード接続手段を具備し、各ノードはそれぞれ自ノードが属する複数のグループのうちの１つのグループの他のノードから受信したデータを、自ノードが属する複数のグループのうちの他のグループの他のノードに同報送信によって中継する方式が開示されている。（従来方式３）。従来方式３を用いると、あるノードの集合に対して、共通のデータを送信するにあたって、各グループをまたがるノード（中継ノード）に対し、データを送信し、同報送信してもらうことによって、データを効率よく配信することができる。
【０００８】
また、特許文献３には、センター及び複数の端末から構成され、各端末がグループを形成しグループで同じ秘密鍵を共有する通信システムにおいて、秘密分散法などの剰余計算を用いて、秘密鍵を更新する方式が開示されている（従来方式４）。従来方式４は、センター側における暗号処理の負担を軽減することを目的とし、秘密分散法に基づき、端末側で剰余計算を行うことを必須として秘密鍵を更新することができる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開平１１−１８７０１３号公報
【特許文献２】特許第２８５２５８６号公報
【特許文献３】特開２００４−３４３８１６号公報
【非特許文献】
【００１０】
【非特許文献１】Ｚｉｇｂｅｅ(登録商標)センサネットワークｐｐ．１１８〜１２０、阪田史郎ら、秀和システム、２００５年
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、ネットワークを構成する通信機器において、チップやメモリの小型化が望まれるような、計算資源に制限があるネットワーク通信においては、安全に通信及び暗号鍵更新を行うことはもちろんのことながら、鍵更新における通信量の低減及び鍵更新による計算量の低減が求められる。
【００１２】
これに対し、従来方式１はサーバからネットワークに送信される通信量がグループ内のノード数をＮとしたとき通信量はＯ（Ｎ）となる。すなわちノード数に比例して鍵更新のための通信量が増大するという問題がある。一方、従来方式２では、この通信量はＯ（ｌｏｇ Ｎ）となる。すなわちノード数の対数に比例して鍵更新のための通信量が増大するという問題がある。従来方式１と比較して効率的であるが、ノード数が増大した場合に鍵更新のためのサーバからの通信量が問題になる点では同様の問題が生じる可能性がある。特にセンサネットワークのようなノード数が従来のシステムに比べ、桁違いに増加することが予想される環境では、通信量がノード数の対数に比例するとしても、本問題が顕在化することが予想される。
【００１３】
一方、従来方式３を暗号鍵の配送用の通信手段として用いることが考えられるが、中継ノードを排除する場合に対応することができないという問題がある。また中継ノードがグループ外ノードである可能性を考慮すると、中継ノードに暗号鍵情報が漏洩する危険もある。
【００１４】
また、従来方式４は秘密分散法に基づいた鍵更新方式であり，巨大な素数ｐのもとでの剰余計算や、大きな数の剰余演算などを用いた大きな計算量が必須とされる。このような剰余計算を用いてグループ鍵の鍵更新を行う方式では，公開鍵方式同様、一般的に非常に大きな計算量となる。しかし、特にセンサネットワークのようなノード側の通信機器に用いる計算資源において、実施可能な計算能力や記憶容量などに制限のある環境下では、ノード側での計算量が限られるために、従来方式４のような大きな数の剰余計算を要する方式は用いることができない。
【００１５】
よって、本発明は上記課題を解決し、暗号鍵を利用し、複数の通信機器を用いて通信を行うネットワーク通信において、通信機器におけるグループの構成が時間進行に応じて変化する場合にも備え、暗号鍵であるグループ鍵を更新し、更新後の鍵をグループ内に安全に配布する仕組みを提供するものであり、鍵更新における通信量及び計算量を低減することを目的とする。
【課題を解決するための手段】
【００１６】
本発明によれば、サーバと多数のノードから構成されるネットワークにおいて、ノードに属性がｄ種類存在する場合、ノードはｄ個のグループに同時に属すると考え、このように定義される各グループに対してグループ鍵を対応付け、サーバがグループ鍵をそのグループに属するノードとだけ共有して、各グループを対象とする暗号通信を実施する方法に関し、グループ構成員の変化があった場合に、サーバがグループ鍵を更新し、更新後の鍵を正しく配信する方法であって、特に、あるノードを強制的にグループから排除する場合に、排除されるノードが有効なグループ鍵を所有し続けることのないよう、適切にグループ鍵配信の制御を行う暗号鍵更新方法が提供される。
【発明の効果】
【００１７】
本発明によれば、暗号鍵を利用し、複数の通信機器を用いて通信を行うネットワーク通信において、ネットワーク構成が時間進行に応じて変化する場合にも備え、暗号鍵であるグループ鍵を更新し、更新後の鍵を安全に配布する仕組みを提供することができる。また、鍵更新における通信量及び計算量を低減することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明を実施するための一実施形態の構成を示す図である。
【図２】本発明における実施例を説明する図である。
【図３】ｎをグループＧｉ，ｊから排除する概要動作を示す流れ図である。
【図４】ｎをグループＧｉ，ｊ（ｉ≠０）から排除する動作を示す流れ図である。
【図５】ｎをグループＧｉ，ｊ（ｉ＝０かつｊ≠１）から排除する動作を示す流れ図である。
【図６】ｎをグループＧｉ，ｊ（ｉ＝０かつｊ＝１）から排除する動作を示す流れ図である。
【図７】ｎをグループＧｉ，ｊ（ｉ≠０）から排除する場合の例を示す図である。
【図８】ｎをグループＧｉ，ｊ（ｉ＝０かつｊ≠１）から排除する場合の例を示す図である。
【図９】ｎをグループＧｉ，ｊ（ｉ＝０かつｊ＝１）から排除する場合の例を示す図である。
【発明を実施するための形態】
【００１９】
以下、図面を参照して本発明を実施するための最良の形態について詳細に説明する。
【００２０】
一般に、一台のセンサノードには複数の属性が存在すると考えられる。例えば、製造ロット番号、ファームウェアのバージョン、設置場所、装備するセンサの種類等は、すべて属性となり得る。センサノードは、各属性に対してなんらかの属性値を有すると考えられる。
【００２１】
本発明は、ある属性に対して同じ属性値を持つノードの集合で、一つのグループを構成するとし、このように定義される各グループに対してグループ鍵を対応付け、グループ鍵を、そのグループに属するノードにだけ配布する暗号鍵管理方法である。
【００２２】
したがって、属性がｄ種類存在する場合、ノードはｄ個のグループに同時に属することとなる。このように定義される各グループに対してグループ鍵を対応付け、グループ鍵を、そのグループに属するノードにだけ配布することを考える。
【００２３】
本発明は、グループ構成員の変化があった場合に、グループ鍵を更新し、更新後の鍵を正しく配信する方法であって、特に、あるノードを強制的にグループから排除する場合に、排除されるノードが有効なグループ鍵を所有し続けることのないよう、適切にグループ鍵配信の制御を行う暗号鍵更新方法である。
【００２４】
図１に、本発明の暗号鍵管理方法の実施形態における全体構成を示す。図１を参照すると、本実施形態において、センサネットワークに代表されるネットワークにおいて、ノード全体からなる集合Ｎと、Ｎに属さないサーバ１０１から構成され、サーバ１０１は、プログラム制御により動作し、ノード追加手段１０３と主ノード排除手段１０５と鍵記憶手段１０７とを、ノードは副ノード排除手段１０９と鍵記憶手段１１１とを備える。ノードは代表的にノード１のみを表記している。サーバの鍵記憶手段１０７とノードの鍵記憶手段１１１の差異は鍵記憶手段に記憶管理する鍵（秘密情報）の差異であり、主にサーバは全グループのグループ鍵を管理するのに対し、ノードは自身の属するグループの中のみで有効なグループ鍵と、ノードのグループ加入および排除の処理の際に必要になる処理用の鍵（後述するメンバ鍵）のみを管理する。
【００２５】
ノードも鍵に関する動作などにおいては、プログラム制御により動作する。
【００２６】
以下、対称鍵暗号を用いたデータの暗号化操作を用いるが、暗号化に用いるアルゴリズムについてはネットワーク参加者が了解しているものとし、サーバ、各ノードは暗号化、復号を実行可能であり、特にサーバ、各ノードともに自身が所有する鍵で暗号化されている情報に関して、適した鍵で復号し復号結果を取得できるものとする。
【００２７】
また、属性をノード全体からなる集合Ｎの分割であるとし、特に、
Ｇｉ⊂Ｎ ．．．（条件１）
ｉ≠ｊならばＧｉ∩Ｇｊは空集合である ．．．（条件２）
Ｇ１∪Ｇ２∪．．．Ｇｍ ＝ Ｎ ．．．（条件３）
の３つの条件を満たす集合族｛Ｇ１， Ｇ２， ．．．， Ｇｍ｝を属性と呼ぶ。
【００２８】
また、ｄ個の属性Ａ１， ．．．， Ａｄを考え、Ａｉ＝｛Ｇｉ，１， ．．．， Ｇｉ，ｍｉ｝とし（ｍｉはＡｉの要素数）、Ｇｉ，ｊは、属性ｉについてｊ番目の属性値を持つノードの集合であるとしたとき、ｋ個の整数１≦ ｉ１， ．．．， ｉｋ ≦ ｄおよびｋ個のグループＧｉ１，ｊ１，．．．，Ｇｉｋ，ｊｋ（ただし、１≦ａ≦ｋに対してＧｉａ，ｊａ∈Ａｉａとする）が存在し、Ｇ＝Ｇｉ１，ｊ１∩．．． ∩Ｇｉｋ，ｊｋとなるノード集合Ｇを位数ｋのグループであるというとき、構造化グループ間の包含関係において極小の集合である位数ｄのグループＣ（極小グループ）を構成するｄ個の属性に加え、
任意の極小グループＣに対し、Ｃ∩Ｇ０，１がちょうど一個のノード（グループヘッド）を含む（条件４）、
任意の極小グループＣ，Ａ０におけるＧ０，１以外のグループＧ０，ｊに対し、Ｃ∩Ｇ０，ｊが高々一個のノード（グループメンバ）を含む（条件５）、
の２つを満たすように構成した特殊な属性Ａ０＝｛Ｇ０，１， ．．．， Ｇ０，ｍ０｝（ただしｍ０ ＞ ０）を導入して、ｄ＋１個の属性組Ａ０， Ａ１， ．．．， Ａｄで構成するｄ次元グループ構造でグループ鍵を更新管理する。
【００２９】
また、ノードはちょうど一個の極小グループに属すること、Ａ０は全ノード集合Ｎの分割になっていることより、任意のノードｎに対してｄ＋１個の整数組ｊ０， ｊ１， ．．．， ｊｄが存在し、Ｇ０，ｊ０ ∩Ｇ１，ｊ１ ∩．．． ∩Ｇｄ，ｊｄ＝｛ｎ｝と表すことができ、ｄ＋１字組（ｊ０， ｊ１， ．．．， ｊｄ） をノードｎの識別子（ＩＤ）として取り扱う。
【００３０】
また、Ａ０， Ａ１， ．．．， Ａｄがｄ次元グループ構造を定義する場合を考え、この時サーバは、位数１のグループＧｉ，ｊ（０≦ｉ≦ｄ， １≦ｊ≦ｍｉ） に属するノードとグループ鍵ｋｉ，ｊ（特に要素鍵と呼ぶ）をあらかじめ共有し、位数ｋのグループ Ｇ＝Ｇｉ１，ｊ１ ∩．．． ∩Ｇｉｋ，ｊｋ（ｉ１＜．．．＜ｉｋ）に対し、ｈ（ｋｉ１，ｊ１｜｜．．．｜｜ｋｉｋ，ｊｋ） （ｈはハッシュ関数などの連接鍵の長さを所定値にするための関数、｜｜は鍵の連接）としてサーバおよびノードで計算できる情報をＧのグループ鍵ｋ（Ｇ）とする。
【００３１】
また、位数ｋのグループＧのグループ鍵ｋ（Ｇ）を知るのはＧに属するノードのみであり、この時、サーバあるいはＧに属するノードは、Ｇに送信したいデータをｋ（Ｇ）により暗号化し、得られた暗号文をＧのノードに対してマルチキャスト配信する。
【００３２】
また、ノードｎのＩＤを（ｊ０， ｊ１， ．．．， ｊｄ）とすると、ｎはｄ＋１個の要素鍵 ｋ０，ｊ０， ．．．， ｋｄ，ｊｄを所有し、これらｄ＋１個の鍵を用いることにより、ｎはｋｎ＝ｈ（ｋ０，ｊ０｜｜．．．｜｜ｋｄ，ｊｄ）を計算することができ、この値ｋｎはｎおよびサーバだけが計算可能な値であるため、サーバはｋｎをｎとサーバとの間で共有された鍵（ノード鍵と呼ぶ）として、サーバは、各ノードに対してそれぞれのノード鍵でデータを暗号化してユニキャスト的に送信する。
【００３３】
また、グループヘッドとそのグループヘッドの属する極小グループの各グループメンバとの間で安全に一対一のメッセージの交換を行うことを可能とするため、サーバは、グループヘッドと各グループメンバに対して、それぞれのノード鍵で共通のユニークな鍵（メンバ鍵）を暗号化してユニキャスト的に送信する。
【００３４】
ノードｎを、位数１のグループＧｉ，ｊに追加する手段（ノード追加手段）は以下のようになる。たとえば、新しいノードを稼働中のセンサネットワークに追加したい場合や、既存のノードの属性値がなんらかの理由で変更される場合等、このようなケースが発生しうる。いずれにせよ、新しくグループに参加するノードｎは、自分が参加する以前にＧｉ，ｊのグループ鍵として使われていた鍵を知る権利はない。逆に、ｎをグループのメンバとして追加する過程において、ｎが以前のグループ鍵を知ることがあってはならない。この性質をグループ鍵における後方安全性(backward security)と呼ぶ。
【００３５】
また、サーバがノードｎを位数１のグループＧｉ，ｊに追加したいとき、データｘを鍵ｋにより暗号化して得られる暗号文をＥｋ（ｘ）と書くこととすると、サーバに備えるノード追加手段は、Ｇｉ，ｊに以前から所属するノードには、ｃ＝Ｅｈ（ｋｉ，ｊ）（ｋ’ｉ，ｊ）を計算し、ｃをＧｉ，ｊに属するノードに対してマルチキャスト配信し、ｎに対してはユニキャスト的に新しい鍵ｋ’ｉ，ｊをサーバとそのノードだけで共有するノード鍵で暗号化してサーバから伝達することで、後方安全性を確保しつつ、新しい鍵ｋ’ｉ，ｊを新しいグループＧｉ，ｊで共有する。
【００３６】
それまでグループＧｉ，ｊに属していたノードを、Ｇｉ，ｊから排除する手段（ノード排除手段）は以下のようになる。あるノードをグループから排除するケースとしては、ノードの属性値が変化した場合、故障等によって停止したノードをネットワークから除外する場合、そして、あるノードが不正者に乗っ取られたおそれがある場合等が考えられる。とくに最後のケースでは、乗っ取られたノードを通じて秘密情報がリークしたり、乗っ取られた情報が他のノードや通信基盤に対してさらなる攻撃を行うことも考えられるため、できるだけ早急にノードを排除することが強く求められる。この際、グループから排除されるノードは、不正な手段によってグループ鍵を保持しようとし続ける可能性がある点に注意しなければならない。ノードを排除するプロトコルにおいては、Ｇｉ，ｊに継続して残るノードには新しい鍵ｋ’ｉ，ｊを確実に配信し、排除されるユーザにはｋ’ｉ，ｊ（および、その後に使用されるグループ鍵）が渡らないようにしなければならない。この性質を、グループ鍵における前方安全性(forward security)と呼ぶ。
【００３７】
前方安全性の確保は、後方安全性の確保に比べて、技術的な困難性が高い。実際、Ｇｉ，ｊに継続して残るノードと、排除されるノードｎとの間には、鍵に関する知識に関し、本質的な差異があるわけではない。たとえば、Ｇｉ，ｊに残るノードも ｎ 自身も、Ｇｉ，ｊにおいてこれまで使用されていたグループ鍵ｋｉ，ｊを知っている。したがって、前節のノード追加のように、古いグループ鍵ｋｉ，ｊを利用して新しい鍵ｋ’ｉ，ｊの配布を行う、といった単純な方法では前方安全性の確保は困難である。
【００３８】
また、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、Ｇｉ，ｊからｎを除いた集合をＧ’ｉ，ｊと書くと、Ｇ’ｉ，ｊは、ｎの排除後もグループにとどまるノード集合であり、Ｇ’ｉ，ｊに属するすべてのノードは、新しい鍵ｋ’ｉ，ｊを入手できなければならず、かつ、前方安全性を確保するため、排除されるノードｎがｋ’ｉ，ｊを知ることがないようにしなければならないため、サーバに備える主ノード排除手段は、極小グループに必ず一個存在するグループヘッドの備える副ノード排除手段と連携して、ノード排除の処理を実施する。
【００３９】
サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、サーバに備える主ノード排除手段は、排除ノードｎがグループヘッドでない場合に、ｎを排除する位数１のグループＧｉ，ｊについて、ｉ≠０である場合と、ｉ＝０である場合（後者の場合、ｎがグループヘッドでないので、自動的にｊ≠１となる）とで、グループヘッドとなるノードの備える副ノード排除手段は処理を分岐する。
【００４０】
サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、排除ノードｎがグループヘッドでなく、ｎを排除する位数１のグループＧｉ，ｊについてｉ≠０である場合、位数１のグループＧｉ，ｊはいくつかの極小グループに分割され、排除されるノードｎは、その中の一つの極小グループに属することとなるので、基本的な考え方として、Ｇｉ，ｊ ∩Ｇ０，１に属するノード（Ｇｉ，ｊに属するグループヘッド）に新しい鍵ｋ’ｉ，ｊを配送し、各グループヘッドからグループメンバに対して鍵ｋ’ｉ，ｊを転送する。
【００４１】
即ち、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、排除ノードｎがグループヘッドでなく、ｎを排除する要素グループＧｉ，ｊについてｉ≠０である場合、サーバの主ノード排除手段は、まず、ｋｉ，ｊをＧｉ，ｊ の要素鍵、ｋ’ｉ，ｊ は新しいＧｉ，ｊ の要素鍵としたとき、ｋ＝ｈ（ｋ０，１｜｜ｋｉ，ｊ） を計算し、ｘ ＝Ｅｋ（ｋ’ｉ，ｊ） を求め、４字組 （ｉ， ｊ， ＩＤｎ， ｘ） をＧｉ，ｊ ∩Ｇ０，１に属するノード（グループヘッド）向けにマルチキャスト送信し（ＩＤｎは排除されるノードｎのＩＤ）、その後、Ｇｉ，ｊ ∩Ｇ０，１に属するノード（グループヘッド）の副ノード排除手段は，ｘを復号してＧｉ，ｊの新しい鍵 ｋ’ｉ，ｊを入手し、最後に、Ｇｉ，ｊ ∩Ｇ０，１に属するノード（グループヘッド）の副ノード排除手段は、自ノードの属する極小グループＣに排除ノードｎを含まないとき、ｋ（Ｃ） （自身の属する極小グループＣのグループ鍵）を用いてｋ’ｉ，ｊを暗号化し、Ｅｋ（Ｃ）（ｋ’ｉ，ｊ）をＣのグループメンバに向けてマルチキャスト配信する一方、グループヘッドの属する極小グループＣに排除ノードｎが含まれるとき、グループヘッドの副ノード排除手段が、ｎ以外のＣのグループメンバ全員に対してメンバ鍵を用いてユニキャスト的にｋ’ｉ，ｊを暗号化して送信する。
【００４２】
サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、排除ノードｎがグループヘッドでなく、ｎを排除する要素グループＧｉ，ｊについてｉ＝０かつｊ≠１である場合、Ｇｉ，ｊ＝Ｇ０，ｊとなり、グループＧｉ，ｊは極小グループに分割することはできない。また、グループヘッドの集合Ｇ０，１とＧｉ，ｊは互いに素である（共通集合を持たない）ため、グループヘッドに新しい要素鍵ｋ’ｉ，ｊを露出してはならない。
【００４３】
即ち、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、排除ノードｎがグループヘッドでなく、ｎを排除する要素グループＧｉ，ｊについて、ｉ＝０かつｊ≠１である場合、サーバの主ノード排除手段は、ｘ１＝Ｅｈ（ｋ０，ｊ）（ｋ’０，ｊ）およびｘ２＝Ｅｈ（ｋ０，１）（ｘ１）を計算し、４字組 （０， ｊ， ＩＤｎ， ｘ２） をグループヘッドの集合 Ｇ０，１ にマルチキャスト配信し、各グループヘッドの副ノード排除手段はｘ２ を復号して ｘ１ を得て（グループヘッドは ｋ０，ｊ を知らないため、ｘ１ を復号することはできない）、Ｇ０，ｊと自身の属する極小グループＣとの積集合に、ノードｎ’が一個含まれ、かつｎ≠ｎ’であれば、グループヘッドの副ノード排除手段が、ｎ’にメンバ鍵でユニキャスト的にｘ１を暗号化して送信する。
【００４４】
また、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、ｎを排除するグループＧｉ，ｊのグループヘッドｎと、そのグループヘッドが属する極小グループ内のノードｎ’との役割を交換する処理を実施し、役割交換処理終了後に排除ノードがグループヘッドでない場合のノード排除処理を施行する。
【００４５】
また、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、ノードの役割交換処理は、グループヘッドｎ、とノードｎ’∈Ｇ０，ｊ（ｊ ≠１）は同一の極小グループに属するものとして、サーバの主ノード排除手段は、まず、Ｇ０，１の要素鍵を更新し、新しい要素鍵ｋ’０，１をＧ０，１からｎを除いたノード集合Ｇ’０，１＝Ｇ０，１＼｛ｎ｝に配信し、その後、Ｇ０，ｊの要素鍵を更新し、新しい要素鍵ｋ’０，ｊをＧ０，ｊからｎ’を除いたノード集合Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ’｝に配信し、最後にｋ’０，１， ｋ’０，ｊをそれぞれｎ’， ｎ に送信する３つの処理からなる。
【００４６】
また、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、まずＧ０，１の要素鍵を更新し、新しい要素鍵ｋ’０，１をＧ０，１からｎを除いたノード集合Ｇ’０，１＝Ｇ０，１＼｛ｎ｝に配信するために、Ｇ’０，１に属する各ノードに対してサーバからユニキャスト的に鍵ｋ’０，１を暗号配信する。
【００４７】
ここで、従来方式２のような方式でＧ０，１を構造化し、Ｇ’０，１に属する各ノードに対してｋ’０，１を配信しても良い。
【００４８】
また、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、Ｇ０，ｊの要素鍵を更新し、新しい要素鍵ｋ’０，ｊをＧ０，ｊからｎ’を除いたノード集合Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ’｝に配信するために、ｘ１＝Ｅｋ０，ｊ（ｋ’０，ｊ）およびｘ２＝Ｅｋ’０，１（ｘ１）を計算し、ｘ２をＧ’０，１のノードに対してマルチキャスト配信し、Ｇ’０，１に属するノード（グループヘッド）の副ノード排除手段はｘ２を復号してｘ１を入手し、Ｇ’０，１に属するノード（グループヘッド）の属する極小グループ内にＧ’０，ｊのノードが存在すれば、グループヘッドの副ノード排除手段が、Ｇ’０，ｊのノードのノード排除手段にユニキャスト的にメンバ鍵でｘ１を暗号化して送信する。
【００４９】
役割交換にともなってＧ０，ｊを離れるノードｎ’については、Ｇ０，１の要素鍵を更新し、新しい要素鍵ｋ’０，１をＧ０，１からｎを除いたノード集合Ｇ’０，１＝Ｇ０，１＼｛ｎ｝に配信した時点で対応する（正当な鍵 ｋ’０，１を保持する）グループヘッドが存在していないため、新しい鍵ｋ’０，ｊの配信を受けることはできない。結果として、Ｇ０，ｊの要素鍵を更新し、新しい要素鍵ｋ’０，ｊをＧ０，ｊからｎ’を除いたノード集合Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ’｝に配信する処理が正しく実現されたことになる。
【００５０】
また、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、ｋ’０，１， ｋ’０，ｊをそれぞれｎ’， ｎに送信するために、ｎ’， ｎにユニキャスト的にｋ’０，１， ｋ’０，ｊをノード鍵で暗号化して送信する。
【実施例】
【００５１】
次に本発明の実施例について、図面を参照して詳細に説明する。ノードは図２に参照されるような、クラスタツリートポロジのネットワークを構成しているとする。ここでクラスタツリートポロジとは、サーバを根ノードとして、根ノード以外のすべての内部ノードについて、その子の中に高々一個の内部ノードしか存在しないツリーのことをいう。クラスタツリーにおいて、一つの内部ノードと、その内部ノードの子の中で葉ノードであるものから構成されるノード集合で一つのクラスタを構成する。クラスタツリートポロジ上では、各ノードの属性として、クラスタツリーにおける何番目の幹に属するかという情報および根ノードからの深さ、クラスタ内で何番目のノードであるかという順序情報を定義できる。クラスタ内での順序情報を特殊な属性Ａ０＝｛Ｇ０，１， Ｇ０，２， Ｇ０，３， Ｇ０，４｝と考えると，幹属性Ａ１＝｛Ｇ１，１， Ｇ１，２， Ｇ１，３｝，深さ属性Ａ２＝｛Ｇ２，１， Ｇ２，２｝で特定できる２次元グループ構造と定義できる。クラスタが２次元グループ構造における極小グループとなる。
【００５２】
この時、ノードｎをグループＧｉ，ｊから排除するときのフローチャートは図３のようになる。図３のＳ３１にてｉ≠０のとき、Ａ１，Ａ２の属性のうちＧ１，１， Ｇ１，２， Ｇ１，３， Ｇ２，１， Ｇ２，２のいずれかの属性値を持つノードの集合からノードｎを排除する処理を実施する。この時、排除するノードはグループヘッドではないので、Ｇｉ，ｊ∩Ｇ０，１に属するノード（Ｇｉ，ｊのグループヘッド）に新しい鍵ｋ’ｉ，ｊを配送し、各グループヘッドからグループメンバに対してｋ’ｉ，ｊを転送する（Ｓ３２）。具体的な処理のフローを図４に示している。まず、サーバがＥ ｈ（ｋ０，１｜｜ｋｉ，ｊ） （ｋ’ｉ，ｊ）を計算し、計算結果をマルチキャストする（Ｓ３１１）。その後、Ｇｉ，ｊ内のグループヘッドだけが本計算結果を復号可能であり、復号してｋ’ｉ，ｊを入手する（Ｓ３１２）。最後に、グループヘッドがＧ’ｉ，ｊ＝Ｇｉ，ｊ＼｛ｎ｝のノードにだけｋ’ｉ，ｊを、グループメンバとの間で共有するメンバ鍵で暗号化してユニキャストして（Ｓ３１３）、処理を終える。
【００５３】
次に、図３のＳ３１にてｉ＝０のとき、Ｓ３３にてｊ≠１ならば、Ａ０の属性のうちＧ０，２あるいはＧ０，３あるいはＧ０，４の属性値を持つノードの集合からノードｎを排除する処理を実施する。この時、Ｇｉ，ｊ ＝Ｇ０，ｊとなりグループヘッドの集合Ｇ０，１とＧｉ，ｊは互いに素（共通集合）を持たないため、グループヘッドにｋ’ｉ，ｊを露出することなく、各グループヘッドからグループメンバに対してｋ’ｉ，ｊを転送する（Ｓ３４）。具体的な処理のフローを図５に示している。まず、サーバがｘ１＝Ｅｈ（ｋ０，ｊ）（ｋ’０，ｊ）を計算し（ｊ≠１） 、ｘ２＝Ｅｈ（ｋ０，１）（ｘ１）をマルチキャストする（Ｓ３４１）。そして、Ｇ０，ｊ内のグループヘッドだけがｘ２を復号可能であり、復号してｘ１を入手する（Ｓ３４２）。グループヘッドはｘ１の復号はできない。その後、グループヘッドがＧ０，ｊ からｎを除いたノード集合Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ｝に属するノードにだけｘ１ をメンバ鍵で暗号化してユニキャストする（Ｓ３４３）。最後に、Ｇ’０，ｊのノードがｘ１をｋ０，ｊを用いて復号し（Ｓ３４４）、処理を終える。
【００５４】
最後に、図３のＳ３１にてｉ＝０のとき、Ｓ３３にてｊ＝１ならば、Ａ０の属性のうちＧ０，１の属性値を持つノードの集合からノードｎを排除する処理を実施する。このときｎはグループヘッドであり、グループヘッドｎと、そのグループヘッドが属する極小グループ内のグループメンバｎ’∈Ｇ０，ｊ（ｊ≠１）との役割を交換する処理を実行し、その後上記の（排除ノードがグループヘッドでない場合の）鍵更新を実行する（Ｓ３５）。具体的な処理のフローを図６に示している。まず、サーバがｋ’０，１をサーバと各ノードに固有なノード鍵で暗号化し、Ｇ０，１からｎを除いたノード集合Ｇ’０，１＝Ｇ０，１＼｛ｎ｝ に含まれるすべてのノードにユニキャストする（Ｓ３５１）。そして、サーバがｘ１ ＝Ｅｈ（ｋ０，ｊ）（ｋ’０，ｊ）を計算し（ｊ≠１）、ｘ２＝Ｅｈ（ｋ’０，１）（ｘ１）をマルチキャストする（Ｓ３５２）。そして、Ｇ’０，１に属するグループヘッドはｘ２を復号してｘ１を入手し（Ｓ３５３）、Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ’｝のノードにｘ１を暗号化してユニキャストする（Ｓ３５４）。その後、Ｇ’０，ｊのノードがｘ１をｋ０，ｊを用いて復号する（Ｓ３５５）。最後に、サーバがｎ’， ｎ にｋ’０，１， ｋ’０，ｊをノード鍵で暗号化してユニキャストして（Ｓ３５６）、役割交換の処理を終了する。この時点で、グループヘッドｎはグループメンバｎ’とその役割を交代し、グループメンバとなる（グループヘッドの集合Ｇ０，１の鍵を所有しなくなる）。その後、図５に示す排除ノードがクラスタヘッドでない場合のノード排除処理を実施してｎを排除し（Ｓ３５７）、処理を終える。
【００５５】
図７は、図４に示す鍵更新処理１の一例として、グループＧ２，２の全ノードのうちグループヘッドノード以外の或るノード（グループＧ２，２且つグループ０，ｉ（ｉ≠０）（例として、ｉ＝４）且つグループ１，ｊ（例として、ｊ＝３）のノード）をグループＧ２，２から排除する例を示す図である。
【００５６】
図７を参照すると、まず、新たな鍵ｋ’２，２を鍵ｋ０，１と鍵２，２とを連接することにより得た鍵のハッシュ値により暗号化し、これをマルチキャストする（図４のステップ３１１）。マルチキャストする鍵には、ノードｎ（グループ０，４且つグループＧ１，３且つグループ２，２に属するノード）の鍵は更新しないという情報を付加しておく。
【００５７】
そうすると、鍵ｋ０，１と鍵２，２とを保有しているグループ２，２のグループヘッドノードがこれを受信して、鍵ｋ’２，２を得る（図４のステップ３１２）。 次に、グループヘッドノードは、自己の配下にあるノードに鍵ｋ’２，２を転送するが、上述した付加情報により特定されるノードには、例外として、鍵ｋ’２，２を転送しない（図４のステップＳ３１３）。
【００５８】
グループ２，１からあるノードを排除する場合の処理とグループ１、ｊ（ｊ＝１〜３）からあるノードを排除する場合の処理は、図７の場合の処理（グループ２，２からあるノードを排除する場合の処理）と同様である（鍵更新処理１である）ので、説明を省略する。
【００５９】
図８は、図５に示す鍵更新処理２の一例として、グループＧ０，３の或るノード（例として、グループＧ０，３且つグループＧ１，１且つグループＧ２，１に属するノード）をグループＧ０，３から排除する例を示す図である。
【００６０】
図８を参照すると、まず、新たな鍵ｋ’０，３を鍵ｋ０，３のハッシュ値により暗号化して、ｘ１を得る（図５のステップＳ３４１の前半部）。次に、ｘ１を鍵ｋ０，１のハッシュ値により暗号化して、ｘ２を得る。そして、ｘ２をマルチキャストする（図５のステップＳ３４１の後半部）。マルチキャストするｘ２には、ノードｎ（グループＧ０，３且つグループＧ１，１且つグループＧ２，１に属するノード）の鍵は更新しないという情報を付加しておく。
【００６１】
そうすると、鍵ｋ０，１を保有しているグループヘッドノードがこれを受信して、ｘ１を得る（図５のステップＳ３４２）。
【００６２】
次に、グループヘッドは、自己の配下にあるノードにｘ１をマルチキャストする。但し、付加情報により特定されたノードにはマルチキャストしない（ステップＳ３４３）。
【００６３】
そうすると、鍵ｋ０，３を保有しているグループＧ０，３のノードがｘ１を受信し、ｋ’０，３を取得する（図５のステップＳ３４４）。但し、付加情報により特定されたノードはグループＧ０，３に属しているが、マルチキャストの対象から外されているので、ｋ’０，３を取得することができない。
【００６４】
グループＧ０，２からあるノードを排除する場合の処理とグループＧ０，４からあるノードを削除する場合の処理は、図８の場合の処理動作と同様である（鍵更新処理２である）ので、説明を省略する。
【００６５】
図９は、図６に示す鍵更新処理３の一例（グループヘッドノード（グループＧ０，１に属するノード）を排除する例）として、グループＧ１，３且つグループＧ２，２のグループのグループヘッドノードｎ（グループＧ１，３且つグループＧ２，２且つグループ０，１に属するノード）を排除する例を示す図である。
【００６６】
図９を参照すると、まず、グループＧ１，３且つグループＧ２，２のグループのグループヘッドノードｎとそのグループの他のノードｎ’（例えば、グループＧ０，３に属するノード）とを交換する。この交換処理は、ステップＳ３５１、Ｓ３５２、Ｓ３５３、Ｓ３５５、Ｓ３５６を有する。
【００６７】
まず、グループＧ１，３且つグループＧ２，２のグループ以外の５つのグループのグループヘッドノードそれぞれに新たな鍵ｋ’０，１を暗号化してユニキャストする（図６のステップＳ３５１）。
【００６８】
次に、新たな鍵ｋ’０，３を鍵ｋ０，３のハッシュ値で暗号化することによりｘ１を生成し（図６のＳ３５２の前半部）、更に、ｘ１をｋ’０，１のハッシュ値で暗号化することによりｘ２を生成し、ｘ２をマルチキャストする（図６のＳ３５２の後半部）。
【００６９】
そうすると、グループＧ１，３且つグループＧ２，２のグループ以外の５つのグループのグループヘッドノードは、鍵ｋ’０，１を保有しているため、ｘ１を復号することができる（図６のステップＳ３５３）。他方、グループＧ１，３且つグループＧ２，２のグループのグループヘッドは鍵ｋ’０，１を保有していないためｘ１を復号することができない。
【００７０】
ｘ１を復号することができた、グループＧ１，３且つグループＧ２，２のグループ以外の５つのグループのグループヘッドノードは、配下のノードにｘ１を送信する（図６のステップＳ３５４）が、鍵０，３を保有しているノード（Ｇ０，３に属するノード）のみがｘ１を復号して、ｋ’０，３を得ることができる（図６のステップＳ３５５）。他方、グループＧ１，３且つグループＧ２，２ではグループヘッドノードがｘ１を復号することができないため、このグループ内のノードはｋ’０，３を得ることができない。
【００７１】
次に、鍵ｋ’０，１をグループヘッドノードｄとなったノードｎ’にユニキャストし、鍵ｋ’０，３をグループヘッドノードｄでなくなったノードｎにユニキャストする（図６のステップＳ３５６）。
【００７２】
この後、ノードｎを排除するために図８に示す方法を実施する（図６のステップＳ３５７）。
【産業上の利用可能性】
【００７３】
よって、本発明によれば、従来方式に比べ、ノード排除時の鍵更新時の通信量を大きく削減することができる。例えば、グループ鍵の更新処理において、サーバからの通信はグループヘッド宛のマルチキャスト配信１回で済み、グループヘッドからは最大でも（そのグループヘッドの属する極小グループのノード数−１）回のユニキャスト通信で鍵更新を行うことができる。極小グループはノード集合の包含関係において極小であるので、大変効率的に処理を行うことが可能である。
【００７４】
また、本発明によれば、役割交換処理を用いることにより、グループヘッドに相当するノード排除による鍵更新を行うことができる。
【００７５】
また、本発明によれば、従来方式に比べ、より少ない計算量で鍵更新を行うことが可能である。よって、例えばセンサネットワークのような計算資源に制限のある環境下においても鍵更新に伴う計算量を低減し、安全に鍵更新を行うことができる。
【００７６】
以上、本発明は、暗号鍵を利用し、複数の通信機器を用いて通信を行うネットワーク通信において、構成する通信機器として、サーバ及びサーバと接続されたノードとにより構成されるようなネットワーク、特にセンサネットワークを例に説明を行ったが、特にこのようなネットワークに限られることはなく様々なネットワーク通信に応用できることはいうまでもない。
【符号の説明】
【００７７】
１０１ サーバ
１０３ ノード追加手段
１０５ 主ノード排除手段
１０７ 鍵記憶手段
１０９ 副ノード排除手段
１１１ 鍵記憶手段
【特許請求の範囲】
【請求項１】
サーバと多数のノードから構成されるネットワークにおいて、ノードに属性がｄ種類存在する場合、ノードはｄ個のグループに同時に属すると考え、このように定義される各グループに対してグループ鍵を対応付け、サーバがグループ鍵をそのグループに属するノードとだけ共有して、各グループを対象とする暗号通信を実施する方法に関し、グループ構成員の変化があった場合に、サーバがグループ鍵を更新し、更新後の鍵を正しく配信する方法であって、特に、あるノードを強制的にグループから排除する場合に、排除されるノードが有効なグループ鍵を所有し続けることのないよう、適切にグループ鍵配信の制御を行う暗号鍵更新方法。
【請求項２】
請求項１に記載の暗号鍵更新方法において、属性を全ノード集合Ｎの分割であるとし、特に（条件１）Ｇｉ⊂Ｎ、（条件２）ｉ≠ｊならばＧｉ∩Ｇｊは空集合である、（条件３）Ｇ１∪Ｇ２∪．．．Ｇｍ＝Ｎ、の３つの条件を満たす集合族｛Ｇ１，Ｇ２，．．．，Ｇｍ｝を属性と呼ぶとき、ｄ個の属性Ａ１，．．．，Ａｄを考え、Ａｉ＝｛Ｇｉ，１，．．．，Ｇｉ，ｍｉ｝とし（ｍｉはＡｉの要素数）、Ｇｉ，ｊは、属性ｉについてｊ番目の属性値を持つノードの集合であるとしたとき、ｋ個の整数１≦ｉ１，．．．，ｉｋ，≦ｄおよびｋ個のグループＧｉ１，ｊ１，．．．，Ｇｉｋ，ｊｋ（ただし、１≦ａ≦ｋに対してＧｉａ，ｊａ∈Ａｉａとする）が存在し、Ｇ＝Ｇｉ１，ｊ１∩．．．∩Ｇｉｋ，ｊｋとなるノード集合Ｇを位数ｋのグループであるというとき、構造化グループ間の包含関係において極小の集合である位数ｄのグループＣ（極小グループ）を構成するｄ個の属性に加え、（条件４）任意の極小グループＣに対し、Ｃ∩Ｇ０，１がちょうど一個のノード（グループヘッド）を含む、（条件５）任意の極小グループＣ，Ａ０におけるＧ０，１以外のグループＧ０，ｊに対し、Ｃ∩Ｇ０，ｊが高々一個のノード（グループメンバ）を含む、の２つを満たすように構成した特殊な属性Ａ０＝｛Ｇ０，１，．．．，Ｇ０，ｍ０｝（ただしｍ０＞０）を導入して、ｄ＋１個の属性組Ａ０，Ａ１，．．．，Ａｄで構成するｄ次元グループ構造でグループ鍵を更新管理することを特徴とする暗号鍵更新方法。
【請求項３】
請求項２に記載の暗号鍵更新方法において、ノードはちょうど一個の極小グループに属すること、Ａ０はノード集合Ｎの分割になっていることより、任意のノードｎに対してｄ＋１個の整数組ｊ０，ｊ１，．．．，ｊｄが存在し、Ｇ０，ｊ０∩Ｇ１，ｊ１∩．．．∩Ｇｄ，ｊｄ＝｛ｎ｝とあらわすことができ、ｄ＋１字組（ｊ０，ｊ１，．．．，ｊｄ）をノードｎの識別子（ＩＤ）として取り扱うことを特徴とする暗号鍵更新方法。
【請求項４】
請求項３に記載の暗号鍵更新方法において、Ａ０，Ａ１，．．．，Ａｄがｄ次元グループ構造を定義する場合を考え、この時サーバは、位数１のグループＧｉ，ｊ（０≦ｉ≦ｄ，１≦ｊ≦ｍｉ）に属するノードとグループ鍵ｋｉ，ｊ（特に要素鍵と呼ぶ）をあらかじめ共有し、位数ｋのグループＧ＝Ｇｉ１，ｊ１∩．．．∩Ｇｉｋ，ｊｋ（ｉ１＜．．．＜ｉｋ）に対し、ｈ（ｋｉ１，ｊ１｜｜．．．｜｜ｋｉｋ，ｊｋ）（ｈはハッシュ関数、｜｜は鍵の連接）としてサーバおよびノードで計算できる情報をＧのグループ鍵ｋ（Ｇ）とすることを特徴とする暗号鍵更新方法。
【請求項５】
請求項４に記載の暗号鍵更新方法において、位数ｋのグループＧのグループ鍵ｋ（Ｇ）を知るのはＧに属するノードのみであり、この時、サーバあるいはＧに属するノードは、Ｇに送信したいデータをｋ（Ｇ）により暗号化し、得られた暗号文をＧのノードに対してマルチキャスト配信することを特徴とする暗号鍵更新方法。
【請求項６】
請求項５に記載の暗号鍵更新方法において、ノードｎのＩＤを（ｊ０，ｊ１，．．．，ｊｄ）とすると、ｎはｄ＋１個の要素鍵ｋ０，ｊ０，．．．，ｋｄ，ｊｄを所有し、これらｄ＋１個の鍵を用いることにより、ｎはｋｎ＝ｈ（ｋ０，ｊ０｜｜．．．｜｜ｋｄ，ｊｄ）を計算することができ、この値ｋｎはｎおよびサーバだけが計算可能な値であるため、サーバはｋｎをｎとサーバとの間で共有された鍵（ノード鍵）として、サーバは、各ノードに対してそれぞれのノード鍵でデータを暗号化してユニキャスト的に安全に送信することを特徴とする暗号鍵更新方法。
【請求項７】
請求項６に記載の暗号鍵更新方法において、グループヘッドとそのグループヘッドの属する極小グループの各グループメンバとの間で安全に一対一のメッセージの交換を行うことを可能とするため、サーバは、グループヘッドと各グループメンバに対して、それぞれのノード鍵で共通のユニークな鍵（メンバ鍵）を暗号化してユニキャスト的に送信することを特徴とする暗号鍵更新方法。
【請求項８】
請求項７に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊに追加したいとき、データｘを鍵ｋにより暗号化して得られる暗号文をＥｋ（ｘ）と書くこととすると、サーバに備えさせるノード追加手段は、Ｇｉ，ｊに以前から所属するノードには、ｃ＝Ｅｈ（ｋｉ，ｊ）（ｋ’ｉ，ｊ）を計算し、ｃをＧｉ，ｊに属するノードに対してマルチキャスト配信し、ｎに対してはユニキャスト的に新しい鍵ｋ’ｉ，ｊをサーバとそのノードだけで共有するノード鍵で暗号化してサーバから伝達することで、後方安全性を確保しつつ、新しい鍵ｋ’ｉ，ｊを新しいグループＧｉ，ｊで共有することを特徴とする暗号鍵更新方法。
【請求項９】
請求項８に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、Ｇｉ，ｊからｎを除いた集合をＧ’ｉ，ｊと書くと、Ｇ’ｉ，ｊは、ｎの排除後もグループにとどまるノード集合であり、Ｇ’ｉ，ｊに属するすべてのノードは、新しい鍵ｋ’ｉ，ｊを入手できなければならず、かつ、前方安全性を確保するため、排除されるノードｎがｋ’ｉ，ｊを知ることがないようにしなければならないため、サーバに備えさせる主ノード排除手段は、極小グループに必ず一個存在するグループヘッドに備えさせる副ノード排除手段と連携して、ノード排除の処理を実施することを特徴とする暗号鍵更新方法。
【請求項１０】
請求項９に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、排除ノードｎがグループヘッドでなく、ｎを排除する要素グループＧｉ，ｊについてｉ≠０である場合、サーバの主ノード排除手段は、まず、ｋｉ，ｊをＧｉ，ｊの要素鍵、ｋ’ｉ，ｊは新しいＧｉ，ｊの要素鍵としたとき、ｋ＝ｈ（ｋ０，１｜｜ｋｉ，ｊ）を計算し、ｘ＝Ｅｋ（ｋ’ｉ，ｊ）を求め、４字組（ｉ，ｊ，ＩＤｎ，ｘ）をＧｉ，ｊ∩Ｇ０，１に属するノード（グループヘッド）向けにマルチキャスト送信し（ＩＤｎは排除されるノードｎのＩＤ）、その後、Ｇｉ，ｊ∩Ｇ０，１に属するノード（グループヘッド）の副ノード排除手段は、ｘを復号してＧｉ，ｊの新しい鍵ｋ’ｉ，ｊを入手し、最後に、Ｇｉ，ｊ∩Ｇ０，１に属するノード（グループヘッド）の副ノード排除手段は、自ノードの属する極小グループＣに排除ノードｎを含まないとき、ｋ（Ｃ）（自身の属する極小グループＣのグループ鍵）を用いてｋ’ｉ，ｊを暗号化し、Ｅｋ（Ｃ）（ｋ’ｉ，ｊ）をＣのグループメンバに向けてマルチキャスト配信する一方、グループヘッドの属する極小グループＣに排除ノードｎが含まれるとき、グループヘッドの副ノード排除手段が、ｎ以外のＣのグループメンバに対してメンバ鍵を用いてユニキャスト的にｋ’ｉ，ｊを暗号化して送信することを特徴とする暗号鍵更新方法。
【請求項１１】
請求項１０に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、排除ノードｎがグループヘッドでなく、ｎを排除する要素グループＧｉ，ｊについてｉ＝０かつｊ≠１である場合、サーバの主ノード排除手段は、ｘ１＝Ｅｈ（ｋ０，ｊ）（ｋ’０，ｊ）およびｘ２＝Ｅｈ（ｋ０，１）（ｘ１）を計算し、４字組（０，ｊ，ＩＤｎ，ｘ２）をグループヘッドの集合Ｇ０，１にマルチキャスト配信し、各グループヘッドの副ノード排除手段はｘ２を復号してｘ１を得て（グループヘッドはｋ０，ｊを知らないため、ｘ１を復号することはできない）、Ｇ０，ｊと自身の属する極小グループＣとの積集合に、ノードｎ’が一個含まれ、かつｎ≠ｎ’であれば、グループヘッドの副ノード排除手段が、ｎ’にメンバ鍵でユニキャスト的にｘ１を暗号化して送信することを特徴とする暗号鍵更新方法。
【請求項１２】
請求項１１に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、ｎを排除するグループＧｉ，ｊのグループヘッドｎと、そのグループヘッドが属する極小グループ内のノードｎ’との役割を交換する処理を実施し、役割交換処理終了後に排除ノードがグループヘッドでない場合のノード排除処理を施行することを特徴とする暗号鍵更新方法。
【請求項１３】
請求項１２に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、ノードの役割交換処理は、グループヘッドｎ，とノードｎ’∈Ｇ０，ｊ（ｊ≠１）は同一の極小グループに属するものとして、サーバの主ノード排除手段は、まず、Ｇ０，１の要素鍵を更新し、新しい要素鍵ｋ’０，１をＧ０，１からｎを除いたノード集合Ｇ’０，１＝Ｇ０，１＼｛ｎ｝に配信し、その後、Ｇ０，ｊの要素鍵を更新し、新しい要素鍵ｋ’０，ｊをＧ０，ｊからｎ’を除いたノード集合Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ’｝に配信し、最後にｋ’０，１，ｋ’０，ｊをそれぞれｎ’，ｎに送信する３つの処理からなることを特徴とする暗号鍵更新方法。
【請求項１４】
請求項１３に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、まずＧ０，１の要素鍵を更新し、新しい要素鍵ｋ’０，１をＧ０，１からｎを除いたノード集合Ｇ’０，１＝Ｇ０，１＼｛ｎ｝に配信するために、Ｇ’０，１に属する各ノードに対してサーバからユニキャスト的に鍵ｋ’０，１を暗号配信することを特徴とする暗号鍵更新方法。
【請求項１５】
請求項１４に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、Ｇ０，ｊの要素鍵を更新し、新しい要素鍵ｋ’０，ｊをＧ０，ｊからｎ’を除いたノード集合Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ’｝に配信するために、ｘ１＝Ｅｋ０，ｊ（ｋ’０，ｊ）およびｘ２＝Ｅｋ’０，１（ｘ１）を計算し、ｘ２をＧ’０，１のノードに対してマルチキャスト配信し、Ｇ’０，１に属するノード（グループヘッド）の副ノード排除手段はｘ２を復号してｘ１を入手し、Ｇ’０，１に属するノード（グループヘッド）の属する極小グループ内にＧ’０，ｊのノードが存在すれば、グループヘッドの副ノード排除手段が、Ｇ’０，ｊのノードのノード排除手段にユニキャスト的にメンバ鍵でｘ１を暗号化して送信することを特徴とする暗号鍵更新方法。
【請求項１６】
請求項１５に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、ｋ’０，１，ｋ’０，ｊをそれぞれｎ’，ｎに送信するために、ｎ’，ｎにユニキャスト的にｋ’０，１，ｋ’０，ｊをノード鍵で暗号化して送信することを特徴とする暗号鍵更新方法。
【請求項１】
サーバと多数のノードから構成されるネットワークにおいて、ノードに属性がｄ種類存在する場合、ノードはｄ個のグループに同時に属すると考え、このように定義される各グループに対してグループ鍵を対応付け、サーバがグループ鍵をそのグループに属するノードとだけ共有して、各グループを対象とする暗号通信を実施する方法に関し、グループ構成員の変化があった場合に、サーバがグループ鍵を更新し、更新後の鍵を正しく配信する方法であって、特に、あるノードを強制的にグループから排除する場合に、排除されるノードが有効なグループ鍵を所有し続けることのないよう、適切にグループ鍵配信の制御を行う暗号鍵更新方法。
【請求項２】
請求項１に記載の暗号鍵更新方法において、属性を全ノード集合Ｎの分割であるとし、特に（条件１）Ｇｉ⊂Ｎ、（条件２）ｉ≠ｊならばＧｉ∩Ｇｊは空集合である、（条件３）Ｇ１∪Ｇ２∪．．．Ｇｍ＝Ｎ、の３つの条件を満たす集合族｛Ｇ１，Ｇ２，．．．，Ｇｍ｝を属性と呼ぶとき、ｄ個の属性Ａ１，．．．，Ａｄを考え、Ａｉ＝｛Ｇｉ，１，．．．，Ｇｉ，ｍｉ｝とし（ｍｉはＡｉの要素数）、Ｇｉ，ｊは、属性ｉについてｊ番目の属性値を持つノードの集合であるとしたとき、ｋ個の整数１≦ｉ１，．．．，ｉｋ，≦ｄおよびｋ個のグループＧｉ１，ｊ１，．．．，Ｇｉｋ，ｊｋ（ただし、１≦ａ≦ｋに対してＧｉａ，ｊａ∈Ａｉａとする）が存在し、Ｇ＝Ｇｉ１，ｊ１∩．．．∩Ｇｉｋ，ｊｋとなるノード集合Ｇを位数ｋのグループであるというとき、構造化グループ間の包含関係において極小の集合である位数ｄのグループＣ（極小グループ）を構成するｄ個の属性に加え、（条件４）任意の極小グループＣに対し、Ｃ∩Ｇ０，１がちょうど一個のノード（グループヘッド）を含む、（条件５）任意の極小グループＣ，Ａ０におけるＧ０，１以外のグループＧ０，ｊに対し、Ｃ∩Ｇ０，ｊが高々一個のノード（グループメンバ）を含む、の２つを満たすように構成した特殊な属性Ａ０＝｛Ｇ０，１，．．．，Ｇ０，ｍ０｝（ただしｍ０＞０）を導入して、ｄ＋１個の属性組Ａ０，Ａ１，．．．，Ａｄで構成するｄ次元グループ構造でグループ鍵を更新管理することを特徴とする暗号鍵更新方法。
【請求項３】
請求項２に記載の暗号鍵更新方法において、ノードはちょうど一個の極小グループに属すること、Ａ０はノード集合Ｎの分割になっていることより、任意のノードｎに対してｄ＋１個の整数組ｊ０，ｊ１，．．．，ｊｄが存在し、Ｇ０，ｊ０∩Ｇ１，ｊ１∩．．．∩Ｇｄ，ｊｄ＝｛ｎ｝とあらわすことができ、ｄ＋１字組（ｊ０，ｊ１，．．．，ｊｄ）をノードｎの識別子（ＩＤ）として取り扱うことを特徴とする暗号鍵更新方法。
【請求項４】
請求項３に記載の暗号鍵更新方法において、Ａ０，Ａ１，．．．，Ａｄがｄ次元グループ構造を定義する場合を考え、この時サーバは、位数１のグループＧｉ，ｊ（０≦ｉ≦ｄ，１≦ｊ≦ｍｉ）に属するノードとグループ鍵ｋｉ，ｊ（特に要素鍵と呼ぶ）をあらかじめ共有し、位数ｋのグループＧ＝Ｇｉ１，ｊ１∩．．．∩Ｇｉｋ，ｊｋ（ｉ１＜．．．＜ｉｋ）に対し、ｈ（ｋｉ１，ｊ１｜｜．．．｜｜ｋｉｋ，ｊｋ）（ｈはハッシュ関数、｜｜は鍵の連接）としてサーバおよびノードで計算できる情報をＧのグループ鍵ｋ（Ｇ）とすることを特徴とする暗号鍵更新方法。
【請求項５】
請求項４に記載の暗号鍵更新方法において、位数ｋのグループＧのグループ鍵ｋ（Ｇ）を知るのはＧに属するノードのみであり、この時、サーバあるいはＧに属するノードは、Ｇに送信したいデータをｋ（Ｇ）により暗号化し、得られた暗号文をＧのノードに対してマルチキャスト配信することを特徴とする暗号鍵更新方法。
【請求項６】
請求項５に記載の暗号鍵更新方法において、ノードｎのＩＤを（ｊ０，ｊ１，．．．，ｊｄ）とすると、ｎはｄ＋１個の要素鍵ｋ０，ｊ０，．．．，ｋｄ，ｊｄを所有し、これらｄ＋１個の鍵を用いることにより、ｎはｋｎ＝ｈ（ｋ０，ｊ０｜｜．．．｜｜ｋｄ，ｊｄ）を計算することができ、この値ｋｎはｎおよびサーバだけが計算可能な値であるため、サーバはｋｎをｎとサーバとの間で共有された鍵（ノード鍵）として、サーバは、各ノードに対してそれぞれのノード鍵でデータを暗号化してユニキャスト的に安全に送信することを特徴とする暗号鍵更新方法。
【請求項７】
請求項６に記載の暗号鍵更新方法において、グループヘッドとそのグループヘッドの属する極小グループの各グループメンバとの間で安全に一対一のメッセージの交換を行うことを可能とするため、サーバは、グループヘッドと各グループメンバに対して、それぞれのノード鍵で共通のユニークな鍵（メンバ鍵）を暗号化してユニキャスト的に送信することを特徴とする暗号鍵更新方法。
【請求項８】
請求項７に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊに追加したいとき、データｘを鍵ｋにより暗号化して得られる暗号文をＥｋ（ｘ）と書くこととすると、サーバに備えさせるノード追加手段は、Ｇｉ，ｊに以前から所属するノードには、ｃ＝Ｅｈ（ｋｉ，ｊ）（ｋ’ｉ，ｊ）を計算し、ｃをＧｉ，ｊに属するノードに対してマルチキャスト配信し、ｎに対してはユニキャスト的に新しい鍵ｋ’ｉ，ｊをサーバとそのノードだけで共有するノード鍵で暗号化してサーバから伝達することで、後方安全性を確保しつつ、新しい鍵ｋ’ｉ，ｊを新しいグループＧｉ，ｊで共有することを特徴とする暗号鍵更新方法。
【請求項９】
請求項８に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、Ｇｉ，ｊからｎを除いた集合をＧ’ｉ，ｊと書くと、Ｇ’ｉ，ｊは、ｎの排除後もグループにとどまるノード集合であり、Ｇ’ｉ，ｊに属するすべてのノードは、新しい鍵ｋ’ｉ，ｊを入手できなければならず、かつ、前方安全性を確保するため、排除されるノードｎがｋ’ｉ，ｊを知ることがないようにしなければならないため、サーバに備えさせる主ノード排除手段は、極小グループに必ず一個存在するグループヘッドに備えさせる副ノード排除手段と連携して、ノード排除の処理を実施することを特徴とする暗号鍵更新方法。
【請求項１０】
請求項９に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、排除ノードｎがグループヘッドでなく、ｎを排除する要素グループＧｉ，ｊについてｉ≠０である場合、サーバの主ノード排除手段は、まず、ｋｉ，ｊをＧｉ，ｊの要素鍵、ｋ’ｉ，ｊは新しいＧｉ，ｊの要素鍵としたとき、ｋ＝ｈ（ｋ０，１｜｜ｋｉ，ｊ）を計算し、ｘ＝Ｅｋ（ｋ’ｉ，ｊ）を求め、４字組（ｉ，ｊ，ＩＤｎ，ｘ）をＧｉ，ｊ∩Ｇ０，１に属するノード（グループヘッド）向けにマルチキャスト送信し（ＩＤｎは排除されるノードｎのＩＤ）、その後、Ｇｉ，ｊ∩Ｇ０，１に属するノード（グループヘッド）の副ノード排除手段は、ｘを復号してＧｉ，ｊの新しい鍵ｋ’ｉ，ｊを入手し、最後に、Ｇｉ，ｊ∩Ｇ０，１に属するノード（グループヘッド）の副ノード排除手段は、自ノードの属する極小グループＣに排除ノードｎを含まないとき、ｋ（Ｃ）（自身の属する極小グループＣのグループ鍵）を用いてｋ’ｉ，ｊを暗号化し、Ｅｋ（Ｃ）（ｋ’ｉ，ｊ）をＣのグループメンバに向けてマルチキャスト配信する一方、グループヘッドの属する極小グループＣに排除ノードｎが含まれるとき、グループヘッドの副ノード排除手段が、ｎ以外のＣのグループメンバに対してメンバ鍵を用いてユニキャスト的にｋ’ｉ，ｊを暗号化して送信することを特徴とする暗号鍵更新方法。
【請求項１１】
請求項１０に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、排除ノードｎがグループヘッドでなく、ｎを排除する要素グループＧｉ，ｊについてｉ＝０かつｊ≠１である場合、サーバの主ノード排除手段は、ｘ１＝Ｅｈ（ｋ０，ｊ）（ｋ’０，ｊ）およびｘ２＝Ｅｈ（ｋ０，１）（ｘ１）を計算し、４字組（０，ｊ，ＩＤｎ，ｘ２）をグループヘッドの集合Ｇ０，１にマルチキャスト配信し、各グループヘッドの副ノード排除手段はｘ２を復号してｘ１を得て（グループヘッドはｋ０，ｊを知らないため、ｘ１を復号することはできない）、Ｇ０，ｊと自身の属する極小グループＣとの積集合に、ノードｎ’が一個含まれ、かつｎ≠ｎ’であれば、グループヘッドの副ノード排除手段が、ｎ’にメンバ鍵でユニキャスト的にｘ１を暗号化して送信することを特徴とする暗号鍵更新方法。
【請求項１２】
請求項１１に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、ｎを排除するグループＧｉ，ｊのグループヘッドｎと、そのグループヘッドが属する極小グループ内のノードｎ’との役割を交換する処理を実施し、役割交換処理終了後に排除ノードがグループヘッドでない場合のノード排除処理を施行することを特徴とする暗号鍵更新方法。
【請求項１３】
請求項１２に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、ノードの役割交換処理は、グループヘッドｎ，とノードｎ’∈Ｇ０，ｊ（ｊ≠１）は同一の極小グループに属するものとして、サーバの主ノード排除手段は、まず、Ｇ０，１の要素鍵を更新し、新しい要素鍵ｋ’０，１をＧ０，１からｎを除いたノード集合Ｇ’０，１＝Ｇ０，１＼｛ｎ｝に配信し、その後、Ｇ０，ｊの要素鍵を更新し、新しい要素鍵ｋ’０，ｊをＧ０，ｊからｎ’を除いたノード集合Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ’｝に配信し、最後にｋ’０，１，ｋ’０，ｊをそれぞれｎ’，ｎに送信する３つの処理からなることを特徴とする暗号鍵更新方法。
【請求項１４】
請求項１３に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、まずＧ０，１の要素鍵を更新し、新しい要素鍵ｋ’０，１をＧ０，１からｎを除いたノード集合Ｇ’０，１＝Ｇ０，１＼｛ｎ｝に配信するために、Ｇ’０，１に属する各ノードに対してサーバからユニキャスト的に鍵ｋ’０，１を暗号配信することを特徴とする暗号鍵更新方法。
【請求項１５】
請求項１４に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、Ｇ０，ｊの要素鍵を更新し、新しい要素鍵ｋ’０，ｊをＧ０，ｊからｎ’を除いたノード集合Ｇ’０，ｊ＝Ｇ０，ｊ＼｛ｎ’｝に配信するために、ｘ１＝Ｅｋ０，ｊ（ｋ’０，ｊ）およびｘ２＝Ｅｋ’０，１（ｘ１）を計算し、ｘ２をＧ’０，１のノードに対してマルチキャスト配信し、Ｇ’０，１に属するノード（グループヘッド）の副ノード排除手段はｘ２を復号してｘ１を入手し、Ｇ’０，１に属するノード（グループヘッド）の属する極小グループ内にＧ’０，ｊのノードが存在すれば、グループヘッドの副ノード排除手段が、Ｇ’０，ｊのノードのノード排除手段にユニキャスト的にメンバ鍵でｘ１を暗号化して送信することを特徴とする暗号鍵更新方法。
【請求項１６】
請求項１５に記載の暗号鍵更新方法において、サーバがノードｎを位数１のグループＧｉ，ｊから排除するとき、ｉ＝０かつｊ＝１すなわち排除ノードｎがグループヘッドである場合に、サーバに備える主ノード排除手段は、ｋ’０，１，ｋ’０，ｊをそれぞれｎ’，ｎに送信するために、ｎ’，ｎにユニキャスト的にｋ’０，１，ｋ’０，ｊをノード鍵で暗号化して送信することを特徴とする暗号鍵更新方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１３−４１３０９（Ｐ２０１３−４１３０９Ａ）
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願番号】特願２０１２−２５７９３２（Ｐ２０１２−２５７９３２）
【出願日】平成２４年１１月２６日（２０１２．１１．２６）
【分割の表示】特願２００７−１７０８１４（Ｐ２００７−１７０８１４）の分割
【原出願日】平成１９年６月２８日（２００７．６．２８）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願日】平成２４年１１月２６日（２０１２．１１．２６）
【分割の表示】特願２００７−１７０８１４（Ｐ２００７−１７０８１４）の分割
【原出願日】平成１９年６月２８日（２００７．６．２８）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]