(57)【要約】【課題】ネットワークにおいて、あるノードの鍵が漏洩した場合でも、他のノード間での暗号化通信への影響が小さくする。【解決手段】通信ノードの一例は、複数のノードを含むネットワークにおいて、暗号化された第１の分散共有鍵に関する情報を含む第１のパケットと、暗号化された第２の分散共有鍵に関する情報を含む第２のパケットが、仮想的なマトリクス空間上で２つの異なる経路に対応して複数のノードを伝達して送付元ノードから宛先ノードまで送られるように、自身から送られるパケットの送付先を決定する。【選択図】図１１
2016005113.tif 000002
【特許請求の範囲】
【請求項１】
送信元ノードから宛先ノードに共有鍵から生成される第１の分散共有鍵に関する情報を含むパケットと第２の分散共有鍵に関する情報を含むパケットを送付し前記送信元ノードと前記宛先ノードの間で共有することによって暗号化通信を行うネットワークを構成する通信ノードであって、
各要素が前記ネットワークを構成する複数のノードの各々に対応する行および列を有する仮想的なマトリクス空間中の前記行で定まる第１の事前共有鍵と、前記列で定まる第２の事前共有鍵とを記憶する記憶部と、
前記第１または前記第２の事前共有鍵を用いて暗号化された第１の分散共有鍵に関する情報を含む前記第１のパケットと、前記第１または前記第２の事前共有鍵を用いて暗号化された第２の分散共有鍵に関する情報を含む第２のパケットが、前記仮想的なマトリクス空間上で２つの異なる経路に対応して前記複数のノードを伝達して前記送付元ノードから前記宛先ノードまで送られるように、第１のパケットの送付先ノードおよび／または前記第２のパケット送付先ノードを特定する送付先決定部と、
を含む通信ノード。
【請求項２】
さらに、
自身が前記送信元ノードの場合に、送信元ノードから宛先ノードに共有鍵に関する情報を含む複数のパケットを送付し前記送信元ノードと前記宛先ノードの間で共有することによって暗号化通信を行うための共有鍵を生成する鍵生成部と、
自身が前記送信元ノードの場合に、前記共有鍵から前記第１または前記第２の事前共有鍵を用いて前記暗号化された第１の分散共有鍵、および前記第１または前記第２の事前共有鍵を用いて前記暗号化された第２の分散共有鍵を生成する分散鍵演算部と、
前記第１のパケットを前記第１のパケットの送付先ノードに送信するおよび前記第２のパケットを前記前記第２のパケットの送付先ノードに送信する送信部と、
を含む請求項１に記載の通信ノード。
【請求項３】
さらに、
自身が前記送信元ノードでない場合に、前記暗号化された第１の分散共有鍵に関する情報を含む前記複数のパケットのうちの第１のパケット、および／または前記暗号化された第２の分散共有鍵に関する情報を含む前記複数のパケットのうちの第２のパケットを受信する受信部と、
前記第１のパケットもしくは前記第２のパケットを受信したとき、前記暗号化された前記第１の分散共有鍵もしくは前記暗号化された前記第２の分散共有鍵から前記第１の分散共有鍵もしくは前記第２の分散共有鍵を復元する、または前記第１のパケットおよび前記第２のパケットを受信したとき、前記暗号化された前記第１の分散共有鍵および前記暗号化された前記第２の分散共有鍵から前記共有鍵を復元する共有鍵復元部（と、
を含み
分散鍵演算部は、自身が前記送信元ノードでない場合に、前記第１の分散共有鍵を前記第１もしくは前記第２の事前共有鍵を用いて暗号化する、または前記第２の分散共有鍵を前記第１もしくは前記第２の事前共有鍵を用いて暗号化する、請求項１または２に記載の通信ノード。
【請求項４】
さらに、
前記宛先ノードが、前記仮想的なマトリクス空間中で同じ行または列にあるかどうかを判定する判定部を含み、
前記送付先決定部は、前記判定の結果を参照し、前記宛先ノードが前記仮想的なマトリクス空間中で自身と同じ行または列にある場合は前記宛先ノードを、前記仮想的なマトリクス空間中で同じ行または列にない場合、前記仮想的なマトリクス空間中で自身と同じ行または列にある前記複数のノードの一つを前記送付先ノードとする、請求項１乃至３のいずれか一項に記載の通信ノード。
【請求項５】
前記分散鍵演算部は、前記送付先ノードが前記仮想的なマトリクス空間中で同じ行にある場合は、前記第１の分散共有鍵または前記第２の分散共有鍵を前記第１の事前共有鍵を用いて暗号化し、前記送付先ノードが前記仮想的なマトリクス空間中で同じ列にある場合は、前記第１の分散共有鍵または前記第２の分散共有鍵を前記第２の事前共有鍵を用いて暗号化する、請求項１乃至４のいずれか一項に記載の通信ノード。
【請求項６】
前記送付先決定部は、前記送付元ノードと前記宛先ノードが前記仮想的なマトリクス空間中で同じ行にある場合は、前記第１のパケットを前記送付元ノードから前記宛先ノードに送り、前記第２のパケットを、前記送付元ノードと前記仮想的なマトリクス空間中で同じ列にある第１の仲介ノードと、前記第１の仲介ノードと前記仮想的なマトリクス空間中で同じ行にあり前記宛先ノードと同じ列にある第２の仲介ノードを介して前記送付元ノードから前記宛先ノードに送るように前記仮想的なマトリクス空間上で前記２つの異なる経路を決定し、前記送付元ノードと前記宛先ノードが前記仮想的なマトリクス空間中で同じ列にある場合は、前記第２のパケットを前記送付元ノードから前記宛先ノードに送り、前記第１のパケットを、前記送付元ノードと前記仮想的なマトリクス空間中で同じ行にある第１の仲介ノードと、前記第１の仲介ノードと前記仮想的なマトリクス空間中で同じ列にあり前記宛先ノードと同じ行にある第２の仲介ノードを介して前記送付元ノードから前記宛先ノードに送るように前記仮想的なマトリクス空間上で前記２つの異なる経路を決定し、前記送付元ノードと前記宛先ノードが前記仮想的なマトリクス空間中で同じ行にも列にもない場合は、前記第１のパケットを、前記仮想的なマトリクス空間中で自身と同じ行にあり前記宛先ノードと同じ列にある第２の仲介ノードを介して、前記第２のパケットを、前記仮想的なマトリクス空間中で自身と同じ列にあり前記宛先ノードと同じ行にある第３の仲介ノードを介して前記送付元ノードから前記宛先ノードに送るように前記仮想的なマトリクス空間上で前記２つの異なる経路を決定する、請求項１乃至５のいずれか一項に記載の通信ノード。
【請求項７】
各要素が前記ネットワークを構成する複数のノードの各々に対応する行および列を有する仮想的なマトリクス空間中の前記行で定まる第１の事前共有鍵と、前記列で定まる第２の事前共有鍵とを記憶するメモリを備えるコンピュータによって実行される通信制御方法であって、
前記第１または前記第２の事前共有鍵を用いて暗号化された第１の分散共有鍵に関する情報を含む前記第１のパケットと、前記第１または前記第２の事前共有鍵を用いて暗号化された第２の分散共有鍵に関する情報を含む第２のパケットが、前記仮想的なマトリクス空間上で２つの異なる経路に対応して前記複数のノードを伝達して前記送付元ノードから前記宛先ノードまで送られるように、第１のパケットおよび／または前記第２のパケットの送付先ノードを特定することと、
前記第１のパケットを前記第１のパケットの送付先ノードに送信するおよび／または前記第２のパケットを前記前記第２のパケットの送付先ノードに送信することと、
を含む通信制御方法。
【請求項８】
各要素が前記ネットワークを構成する複数のノードの各々に対応する行および列を有する仮想的なマトリクス空間中の前記行で定まる第１の事前共有鍵と、前記列で定まる第２の事前共有鍵とを記憶するメモリを備えるコンピュータによって実行される通信制御プログラムであって、
前記第１の事前共有鍵を用いて暗号化された第１の分散共有鍵に関する情報を含む前記第１のパケットと、前記第２の事前共有鍵を用いて暗号化された第２の分散共有鍵に関する情報を含む第２のパケットが、前記仮想的なマトリクス空間上で２つの異なる経路に対応して前記複数のノードを伝達して前記送付元ノードから前記宛先ノードまで送られるように、第１のパケットおよび／または前記第２のパケットの送付先ノードを特定し、
前記第１のパケットを前記第１のパケットの送付先ノードに送信するおよび／または前記第２のパケットを前記前記第２のパケットの送付先ノードに送信する
処理を前記コンピュータに実行させることを特徴とする通信制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ノード、通信制御方法、および通信制御プログラムに関する。
【背景技術】
【０００２】
センサノードなどがセンサネットワークを構成し、データを暗号化して通信することによって、秘匿通信や認証を行うことが行われている。このようなデータの暗号化通信の発達と共に、暗号化および復号のための鍵の管理のための技術に注目が集まっている。
【０００３】
センサネットワークとは、センサノードと呼ばれるセンサ付きの通信端末を空間に散在させ、それらが連携して個々のセンサノード周辺の情報を取得することを可能とするネットワークのことである。特に、通信に無線を利用し、アドホックネットワークを構成する無線センサネットワークは、センサノードの設置に自由度が高いため、自然観測、災害救助、交通状況、軍事目的など幅広い分野での活用が期待されている。以降、単にセンサネットワーク、センサノードと言った場合、無線センサネットワーク、及びそれを構成するセンサノードのこととする。
【０００４】
センサノードは、無線通信を使用するので、通信はセンサ近傍では誰でも受信可能である。そのため、通信内容の秘匿やノードの認証は必須である。
【０００５】
また、センサノードは、人間の近づけない災害現場では空からセンサを散布するなどのように、設置の自由度が高く、ネットワークトポロジをあらかじめ予測することが出来ない。そのため、任意のセンサノード間で通信が可能でなければならない。
【０００６】
一方、センサノードは、内蔵電池駆動の小型装置であり、限られた演算能力とメモリしか持たない。そのため、センサノード上で大きな計算量や大量のメモリを必要とする処理を実現することは困難であることがある。
【０００７】
センサネットワーク等の複数の伝送経路を有するネットワークにおいて、伝送に必要なコストが最も低い伝送経路を選択し、その伝送経路のみを用いてデータを伝送する方式が知られている。そして、このようなネットワークにおいて、選択した伝送経路上に悪意の利用者が存在し、伝送経路上において漏洩があった場合でも伝送すべきデータを保全する技術が知られている（たとえば、特許文献１）。たとえば、送信器は、伝送前にデータを複数の部分データであって、全てのデータが揃わなければ元のデータの内容を復元することが不可能な部分データに分割してから送信する。部分データを受信する受信器は、部分データから元のデータを復元する。
【０００８】
また、配信するデジタルデータに対応する暗号鍵を基に配信用の鍵情報を複数生成し、鍵情報をデジタルデータとは別々に配信する技術が知られている（たとえば、特許文献２）。このような技術を用いることによって、不正行為からコンテンツ提供者を保護することができる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００２−２６１７４６号公報
【特許文献２】特開平９−１１６５３５号公報
【非特許文献】
【００１０】
【非特許文献１】松本、毛利、楫、「複数の小規模鍵プールからの鍵選択に基づくセンサノード鍵格納方式」ＳＣＩＳ２００６、３Ｄ４−４、２００６
【非特許文献２】Ｈａｏｗｅｎ  Ｃｈａｎ，  Ａｄｒｉａｎ  Ｐｅｒｒｉｇ、  「ＰＩＫＥ：  Ｐｅｅｒ  Ｉｎｔｅｒｍｅｄｉａｒｉｅｓ  ｆｏｒ  Ｋｅｙ  Ｅｓｔａｂｌｉｓｈｍｅｎｔ  ｉｎ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ」  ＩＥＥＥ、  ＩＥＥＥ  ＩＮＦＯＣＯＭ  ２００５、ｐｐ．５２４−５３５
【発明の概要】
【発明が解決しようとする課題】
【００１１】
センサネットワークで、全てのノードで同じ事前共有鍵を共有し、さらに共通鍵暗号を用いて暗号化通信を行う方式では、各ノードが保有する事前共有鍵の数は１個であり小さなメモリ容量しか必要としない。さらに、共通鍵暗号の使用により、小さな計算量で暗号化通信が可能である。しかし、センサノードは野外で運用されることがあり、ノードの盗難解析を受けやすい。そして、センサノードの１個が解析され、事前共有鍵が漏洩すれば、センサネットワーク全ての通信の傍受が可能となってしまうという問題がある。
【００１２】
１つの側面において、本発明は、アドホックネットワークにおいて、一つのノードの事前共有鍵が漏洩した場合でも、共通鍵暗号の鍵は完全に復元できない通信ノード、通信制御方法、および通信制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
送信元ノードから宛先ノードに共有鍵から生成される第１の分散共有鍵に関する情報を含むパケットと第２の分散共有鍵に関する情報を含むパケットを送付し前記送信元ノードと前記宛先ノードの間で共有することによって暗号化通信を行うネットワークを構成する通信ノードが提供される。通信ノードは、前記ネットワークを構成する複数のノードの各々が配置される、行および列を有する仮想的なマトリクス空間中の前記行で定まる第１の事前共有鍵と、前記列で定まる第２の事前共有鍵とを記憶する記憶部と、前記第１の事前共有鍵を用いて暗号化された第１の分散共有鍵に関する情報を含む前記第１のパケットと、前記第２の事前共有鍵を用いて暗号化された第２の分散共有鍵に関する情報を含む第２のパケットが、前記仮想的なマトリクス空間上で２つの異なる経路に対応して前記複数のノードを伝達して前記送付元ノードから前記宛先ノードまで送られるように、第１のパケットおよび／または前記第２のパケットの送付先ノードを特定する送付先決定部と、を含むことを特徴とする。
【発明の効果】
【００１４】
実施形態の通信ノード、通信制御方法、および通信制御プログラムでは、アドホックネットワークにおいて、一つのノードの事前共有鍵が漏洩した場合でも、共通鍵暗号の鍵は完全に復元できないという効果を奏する。
【図面の簡単な説明】
【００１５】
【図１】ネットワーク構成の例を示す図である。
【図２】第１の比較例を説明するための図である。
【図３】第２の比較例における暗号化通信を説明するための図である。
【図４】第２の比較例のネットワーク中のノードにおける鍵共有の様子を説明するための図である。
【図５】第１の実施例における暗号化通信を説明するための図である。
【図６】第１の実施例におけるネットワーク中のノードにおける鍵共有の様子を説明するための図である。
【図７】第２の実施例における各ノードが保有する鍵の例を説明するための図である。
【図８】第２の実施例における暗号化通信の例を説明するための図である。
【図９】通信ノードの機能ブロックの例を示す図である。
【図１０】パケットのフォーマットの例を示す図である。
【図１１】第２の実施例における暗号化通信の例を説明するための図である。
【図１２】第２の実施例における暗号化通信の例におけるシーケンスの例を示す図である。
【図１３】第２の実施例における暗号化通信の別の例を説明するための図である。
【図１４】第２の実施例における暗号化通信の別の例におけるシーケンスの例を示す図である。
【図１５】第２の実施例における暗号化通信のさらに別の例を説明するための図である。
【図１６】第２の実施例における暗号化通信のさらに別におけるシーケンスの例を示す図である。
【図１７】通信ノードの構成の例を示す図である。
【図１８】送信元ノードではない通信ノードにおける処理の流れの例を示す図である（その１）。
【図１９】送信元ノードではない通信ノードにおける処理の流れの例を示す図である（その２）。
【図２０】送信元ノードの通信ノードにおける処理の流れの例を示す図である。
【発明を実施するための形態】
【００１６】
以下では、図面を参照して、通信ノード、通信制御方法、および通信制御プログラムの実施例について説明する。
【００１７】
図１は、ネットワーク構成の例を示す図である。
図１に示されているネットワーク１０は、無線センサネットワークでも良い。ネットワーク１０は、互いに無線通信を行う通信ノード１００＿１、・・・、１００＿９（まとめて通信ノード１００とも呼ぶ）と、ネットワークを総括して管理するサーバ１１０を含む。さらにネットワークは、通常、サーバ１１０とインターネット等のネットワークで接続され、サーバ１１０と通信ノード１００−１、・・・、１００−９との無線通信を中継するシンクノード１２０を含む。図１では、通信ノードの数は９つであるが、勿論、任意の数であり得る。また、サーバ１１０とシンクノード１２０は有線または無線で接続される。
【００１８】
通信ノード１００−１、・・・、１００−４、１００−６、・・・、１００−９は通信ノード１００−５の定常的な通信対象である。すなわち、通信ノード１００−１、・・・、１００−４、１００−６、・・・、１００−９は通信ノード１００−５に隣接する通信ノードである。通信ノード１００＿５の定常的な通信対象は複数であれば、任意の数だけ存在しても良い。また、通信ノード１００＿１、・・・、１００＿４、１００−６、・・・、１００−９は互いに直接通信、いわゆるアドホックな通信を実現する。
【００１９】
通信ノード１００−１、・・・、１００−９のほかに、たとえば、通信ノード１００−１０、１００−１１、１００−１２が存在しても良い。この場合、通信ノード１００−５とはアドホックな通信は行われないが、通信ノード１００−１０、１００−１１、１００−１２の３つの通信ノードの間で通信を行い得る。
【００２０】
このように、通信ノード１００−５と、通信ノード１００−１、・・・、１００−４、１００−６、・・・、１００−９と、通信ノード１００−１０、１００−１１、１００−１２とは、無線で互いに接続されることで実現するマルチホップ通信により、無線ネットワークを自律的に構築し得る。このように自律的に構築され得るネットワークをアドホックネットワークと呼ぶことがある。以下で「ネットワーク」と言ったときには、断りのない限り、アドホックネットワークを意味する。
【００２１】
また、以下では、通信ノード１００−１、・・・、１００−９のような「通信ノード」を単に「ノード」と呼ぶことがある。
【００２２】
ネットワークでは、鍵を事前に配布して、全てのノード間で確定的に鍵を共有できることが前提である場合がある。以下では、その前提の上で、各ノードが事前に保有する共有鍵の数は少なく（鍵の数がノード数に依存しない）、事前に保有する共有鍵が漏洩した場合に、他のノード間での暗号化通信への影響が小さい通信ノード、通信制御方法、および通信制御プログラムの実施例について説明する。
【００２３】
実施例の説明の前に、図２〜６を参照して比較例を説明する。
【００２４】
＜第１の比較例＞
まず、図２を参照して第１の比較例を説明する。
【００２５】
図２は、第１の比較例を説明するための図である。第１の比較例では、確率的に共有鍵を生成することで、ノード解析に対する耐性を高めている（たとえば、非特許文献１を参照）。
【００２６】
図２に示されているように、本例は３つの通信ノード１０２、１０４、１０６がアドホックネットワークを構築している例である。
【００２７】
図２に示されているアドホックネットワークは、通信ノード１０２、１０４、１０６とは別に、各ノードに鍵を付与するなどを行う鍵管理部４００を含む。鍵管理部４００は、たとえば、図１のサーバ２００等に含まれていても良い。
【００２８】
鍵管理部２００は、４色の各色に対して３種類だけ存在し、計１２種類の鍵を管理する。各色のことをクラスまたは鍵プールと呼ぶことがある。図２の場合、鍵Ｙ１、Ｙ２、Ｙ３が一つのクラスを構成する。同様に、鍵Ｂ１、Ｂ２、Ｂ３が別のクラスを構成する。また鍵Ｇ１、Ｇ２、Ｇ３がさらに別のクラスを構成し、鍵Ｒ１、Ｒ２、Ｒ３がさらに別のクラスを構成する。鍵管理部２００は、各通信ノードに各クラスごとに１つずつの鍵をランダムに配布する。たとえば、通信ノード１０２には、鍵Ｙ３、Ｂ１、Ｇ１、Ｒ２が配布されている。通信ノードが、ｉ番目プールのｊ番目の鍵を保有している場合、ｉ番目の要素に数字ｊを書き込むことによって表すことができる。これをインデックスと呼ぶことがある。たとえば、通信ノード１０２は、インデックス（３、１、１、２）の鍵を保有しているとも言う。通信ノード１０４には、鍵Ｙ２、Ｂ１、Ｇ３、Ｒ１が配布されている。通信ノード１０６は、インデックス（２、３、１、２）の鍵を保有しているとも言う。このとき、通信ノード１０４は、インデックス（２、１、３、１）の鍵を保有しているとも言う。通信ノード１０６には、鍵Ｙ２、Ｂ３、Ｇ１、Ｒ２が配布されている。そして、各通信ノードが保有する鍵の情報は、インデックスの形式で、隣接する通信ノード１０４、１０６に伝えられても良い。
【００２９】
このように、センサノードに複数の鍵をランダムに配布しておき、確率的に共有されたいくつかの鍵から、ノード間の共有鍵を生成する。鍵の配布は完全にランダムに行うのではなく、全鍵空間（図２の場合１２個）を複数の鍵プール（図２の場合は４個）に分割し、各鍵プールには複数の鍵（図２の場合３個）が配布される。各センサノードには、全鍵プールから１個ずつランダムに鍵が事前配布される。
【００３０】
通信ノード間の鍵共有は、まず、通信ノード間で自ノードが保有する全鍵のインデックスが交換される。次に、相手の全鍵インデックスを基に、共有可能な全ての鍵から(ハッシュ値などを使用して)共有鍵を生成する。
【００３１】
互いに隣接し通信する２つの通信ノード、たとえば通信ノード１０２と通信ノード１０４は、各自が保持している鍵のインデックスを交換する。たとえば、通信ノード１０２から通信ノード１０４には、通信ノード１０２が保有する鍵のインデックス（３、１、１、２）が送られる。また、通信ノード１０４から通信ノード１０２には、通信ノード１０４が保有する鍵のインデックス（２、１、３、１）が送られる。すると、通信ノード１０２と通信ノード１０４は鍵Ｂ１（２０２）を共有していることが分かる。この鍵Ｂ１（２０２）のことを「共有鍵」と呼ぶことがある。同様に、通信ノード１０４と通信ノード１０６は、鍵Ｙ２（２０４）を共有していることが分かる。
【００３２】
通信ノード１０２と通信ノード１０６は、鍵Ｇ１とＲ１（２０６）を共有する。このように複数の鍵を２つの通信ノードが共有する場合は、共有する鍵のハッシュ値を連結して得られる値を、それら２つの通信ノードの共有鍵とする。このように、相手の全鍵インデックスを基に、共有可能な全ての鍵から（ハッシュ値などを使用して）共有鍵を生成しても良い。鍵が共有されれば、その鍵を用いて共通鍵暗号で秘匿通信を行う。
【００３３】
このように、共有鍵を確率的に生成していることから、あるノードが解析され、共有鍵が漏洩したとしても、他のノード間の共有鍵と一致する可能性は極めて低い。従って、小さな計算量で鍵共有と通信の秘匿を可能である。
【００３４】
しかし、鍵の配布がランダムで鍵共有が確率的であるため、ノード間で鍵共有を行えない可能性が残るという問題がある。これは、「任意のセンサノード間で通信が可能」というセンサネットワークの利点を阻害する。これらの確率を低下させるためには、鍵プール数を増加させる必要があるが、保有しなければならない鍵数が増加する上に、完全に確率を０に出来ない。そのため、大規模なセンサネットワークにおいて、センサネットワークの利点を阻害せず、各ノード間で異なる鍵を共有することは困難である。
【００３５】
＜第２の比較例＞
図３〜４を参照して第２の比較例を説明する。
【００３６】
図３は、第２の比較例における暗号化通信を説明するための図、図４は第２の比較例のネットワーク中のノードにおける鍵共有の様子を説明するための図である。
【００３７】
本例では、ネットワーク上の通信ノードが、仮想的なｍ行ｎ列のマトリクス空間に配置されているとし、各通信ノードは、同じ行、同じ列に配置されたそれぞれのノードとの共有鍵を保有する（たとえば、非特許文献２を参照）。
【００３８】
図３に、アドホックネットワークを構成する１２個の通信ノードの各々がマトリクス空間の各要素に対応するような仮想的な４行３列のマトリクス空間の例が示されている。このとき、各通信ノードには、仮想的なマトリクス空間の行番号と列番号の２つの要素からなるインデックスが付与される。たとえば、ｙ行ｘ列に対応する通信ノードには、インデックスＩＤ（ｘ、ｙ）が付与される。仮想的なマトリクス空間中のｙ行ｘ列を単に（ｘ、ｙ）と表すことがある。
【００３９】
本例では、仮想的なマトリクス空間中の同じ行、同じ列に対応する通信ノードが保有する鍵を事前に共有する。
【００４０】
たとえば図３に示されているように、仮想的なマトリクス空間中の（０、０）に対応する通信ノードは、仮想的なマトリクス空間中の同じ行、すなわち（１、０）、（２、０）、（３、０）に対応する通信ノードのそれぞれと共有鍵を保有する。仮想的なマトリクス空間中の（０、０）に対応する通信ノードは、たとえば、仮想的なマトリクス空間中の（０、０）に対応する通信ノードと（１、０）に対応する通信ノードが保有する共有鍵をＫ（０、０）（１、０）と表す。同様に、仮想的なマトリクス空間中の（０、０）に対応する通信ノードは、Ｋ（０、０）（２、０）とＫ（０、０）（３、０）を保有する。
【００４１】
さらに、仮想的なマトリクス空間中の（０、０）に対応する通信ノードは、同じ列、すなわち（０、１）、（０、２）に対応する通信ノードのそれぞれと共有鍵を保有する。仮想的なマトリクス空間中の（０、０）に対応する通信ノードは、Ｋ（０、０）（０，１）とＫ（０、０）（０、２）を保有する。
【００４２】
結局、仮想的なマトリクス空間中の（０、０）に対応する通信ノードは、Ｋ（０、０）（１、０）、Ｋ（０、０）（２、０）、Ｋ（０、０）（３、０）、Ｋ（０、０）（０，１）、Ｋ（０、０）（０、２）の５つの共有鍵を保有する。
【００４３】
以下では、仮想的なマトリクス空間中の（ｘ、ｙ）に対応する通信ノードのことを単に「通信ノード（ｘ、ｙ）」または「ノード（ｘ、ｙ）」と呼ぶことがある。
【００４４】
図３に示されている例では、同じ行、あるいは同じ列に配置されたノードと暗号化通信を行う際は、事前に保有している共有鍵を使用すれば良い。一方で、通信ノードが同じ行にも同じ列にも配置されていない場合であっても、仲介通信ノードと呼ばれる通信ノードを使用することで共有鍵を生成できる。仲介通信ノードとは、鍵を共有したい２つのノードの両方と共有鍵を事前に保有しているノードである。
【００４５】
図３において、通信ノード（１、０）と通信ノード（３、２）の間で共有鍵を生成したい場合、仲介通信ノードは通信ノード（１、２）または（３、０）である。図４にも示されているように、通信ノード（１、２）を仲介ノードとする場合、通信ノード（１、０）は共有鍵ＭＫを生成し、通信ノード（１、０）と仲介通信ノード（１、２）の間の共有鍵Ｋ（１、０）（１、２）を用いて暗号化して、仲介通信ノード（１、２）に送付する。仲介通信ノード（１、２）は、暗号化された共有鍵ＭＫを復号する。そして仲介通信ノード（１、２）は、共有鍵ＭＫを通信ノード（３、２）との共有鍵Ｋ（１，２）（３、２）を用いて再度暗号化したうえで、通信ノード（３、２）に送付する。通信ノード（３、２）は、暗号化された共有鍵ＭＫを復号することで、通信ノード（０、１）との共有鍵ＭＫを得る。
【００４６】
以上のように、この方式では確定的に鍵を共有できるため、秘匿通信可能である。さらに、全ての通信ノード間の共有鍵は必ず異なるため、通信ノードの１個が解析されても、他のノード間の通信は異なる鍵が使用されているため、通信の漏洩は発生しない。
【００４７】
しかし、本方式では、通信ノード数がｍ×ｎ個の場合、各通信ノードが保有する鍵が（（ｍ−１）＋（ｎ−１））個だけ必要である。そのため、通信ノード数が増加すれば、大量のメモリを消費する。従って、大規模なセンサネットワークへの適用は困難である。また、本方式では、同じ行にも同じ列にも配置されていないノードと鍵共有する際に、仲介通信ノードが共有鍵を中継するため、仲介通信ノードが盗難されると共有鍵も漏洩するという問題がある。
【００４８】
＜第１の実施例＞
図５〜６を参照して第１の実施例を説明する。
【００４９】
本例は、第２の比較例に対して事前に保有すべき共有鍵の数を削減することができる。
本例も第２の比較例と同様に、ネットワーク上の通信ノードの配置は、仮想的なｍ行ｎ列のマトリクス空間上の配置に対応付けられているとする。第２の比較例とは、各通信ノードが事前に保有する共有鍵の数が異なる。本例では、仮想的なマトリクス空間で同じ行あるいは同じ列に配置されたノードは一つの共有鍵を保有する。具体的に、各ノードは、仮想的なマトリクス空間で自分と同じ行に配置された全てのノードで１個の鍵を共有し、自分と同じ列に配置された全てのノードで１個の鍵を共有するため、計２個の共有鍵を事前に保有する。
【００５０】
図５は、第１の実施例における暗号化通信を説明するための図、図６は第１の実施例におけるネットワーク中のノードにおける鍵共有の様子を説明するための図である。
【００５１】
図５には、アドホックネットワークを構成する１２個の通信ノードの各々がマトリクス空間の各要素に対応するような仮想的な３行４列のマトリクス空間の例が示されている。
【００５２】
本例では、各通信ノードは仮想的なマトリクス空間中で、同じ行に配置された全ての通信ノードとの共有鍵と、同じ列に配置された全ての通信ノードとの共有鍵を事前に保有する。
【００５３】
たとえば、図５に示されているように、通信ノード（０、０）は、仮想的なマトリクス空間中の同じ行に配置された通信ノード（１、０）、（２、０）、（３、０）との共有鍵Ｌ０と、同じ列に配置された通信ノード（０、１）、（０、２）との共有鍵Ｋ０を保有する。このように各通信ノードは、２個の鍵を保有する。そのため、仮想的なマトリクス空間中の同じ行、あるいは同じ列に配置されたノードと暗号化通信を行う際は、保有している共有鍵を使用すれば良い。一方で、通信相手の通信ノードが同じ行にも同じ列にも配置されていない場合であっても、仲介通信ノードと呼ばれる通信ノードを使用することで共有鍵を生成できる。仲介通信ノードとは、鍵を共有したい２つのノードの両方と共有鍵を事前に保有しているノードである。たとえば、図５において、通信ノード（１、０）と通信ノード（３、２）の間で共有鍵を生成したい場合、仲介通信ノードは通信ノード（１、２）または（３、０）である。図６にも示されているように、通信ノード（１、２）を仲介ノードとする場合、通信ノード（１、０）は共有鍵ＭＫを生成し、通信ノード（１、０）と仲介通信ノード（１、２）の間の共有鍵Ｋ１を用いて暗号化して、仲介通信ノード（１、２）に送付する。仲介通信ノード（１、２）は、暗号化された共有鍵ＭＫを復号する。そして仲介通信ノード（１、２）は、共有鍵ＭＫを通信ノード（３、２）との共有鍵Ｌ２を用いて再度暗号化したうえで、通信ノード（３、２）に送付する。通信ノード（３、２）は、暗号化された共有鍵ＭＫを復号することで、通信ノード（０、１）との共有鍵ＭＫを得る。
【００５４】
以上のように、本例では確定的に鍵を共有できる。さらに、ノード数に関わらず、各ノードが事前に保有する鍵の数は２個のため、大規模なネットワークに適している。しかし、同じ行と同じ列に配置されているノードとは同じ共有鍵を使用しているため、ある通信ノード（ｉ、ｊ）が解析されると、仮想的なマトリクス空間でｉ列目に配列されたノード同士、あるいはｊ行目に配置された通信ノード同士の暗号化通信を復号できる。さらに、仮想的なマトリクス空間中のｉ列目とｊ行目に配列された通信ノード間の暗号化通信を復号できる場合がある。
【００５５】
ある通信ノードが解析され鍵が漏洩した場合、仮想的なマトリクス空間でその通信ノードと同じ行または列の通信ノードが関わる暗号化通信が復号される可能性があることを、図７、８を参照して説明する。
【００５６】
図７は、第１の実施例における仮想的な３行４列のマトリクス空間の例、図８は、第１の実施例における暗号化通信が復号される説明するための図である。
【００５７】
図７、８において、通信ノード（１、１）が解析され、共有鍵Ｋ１、Ｌ１が漏洩したとする。この場合、通信ノード（１、０）と通信ノード（３、２）の間の暗号化通信を復号される可能性がある。通信ノード（１、０）と通信ノード（３、２）の間で暗号化通信を行う場合、同じ行にも列にも配置されていないため、仲介通信ノード（１、２）を用いて共有鍵ＭＫを通信ノード（１、０）から通信ノード（３、２）に送る必要がある。共有鍵ＭＫは仲介通信ノード（１、２）との共有鍵Ｋ１を用いて暗号化されて、送られる。しかし、共有鍵Ｋ１は、通信ノード（１、０）と同じ列に位置する通信ノード（１、１）、（１、２）も保有しているため、これらの通信ノードは暗号化された共有鍵ＥＫ１（ＭＫ）を復号することができる。すなわち、解析された通信ノード（１，１）が暗号化された共有鍵を入手できた場合、共有鍵ＭＫを復号し得る。従って、通信ノード（１、０）と通信ノード（３、２）の間で共有鍵ＭＫを用いた暗号化通信を行っていた場合、解析された通信ノード（１、１）は、この暗号化通信の内容を復号できることとなる。従って、本方式では、ある通信ノードが解析され、事前に共有する鍵が漏洩した場合に、他の通信ノード間での暗号化通信が復号できる可能性が残る。
【００５８】
図７、８において、通信ノード（１、０）と通信ノード（３、２）が鍵ＭＫを共有する場合、通信ノード（３、０）を仲介通信ノードにしていれば、信ノード（１、１）が解析され、共有鍵Ｋ１、Ｌ１が漏洩したとしても、通信ノード（１、０）と通信ノード（３、２）の間の暗号化通信を復号される可能性は低くなる。
【００５９】
＜第２の実施例＞
図９〜１４を参照して、第２の実施例について説明する。本例では、第１の実施例の
（Ａ１）確定的に全ノード間で鍵を共有できる、
（Ａ２）事前に保有する共有鍵は２個である、
というメリットを保ったまま、アドホックネットワークにおいて、確定的に全ノード間で鍵を共有でき、事前に保有する共有鍵は２個であるというメリットを保ったまま、一つのノードの事前共有鍵が漏洩した場合でも、共通鍵暗号の鍵が完全に復元されることを避けることができる。具体的には、秘密分散法を用いて共有鍵を複数の分散共有鍵に分散し、それぞれ別の仲介通信ノードを介して宛先の通信ノードに送ることによって、あるノードに記憶されている事前共有鍵が漏洩しても、共有鍵が完全に復号されることを避けることができる。
【００６０】
以下の説明では、第１の実施例のように、仮想的なマトリクス空間で同じ行あるいは同じ列に配置されたノードは一つの事前共有鍵を保有することを想定する。具体的に、各ノードは、仮想的なマトリクス空間で自分と同じ行に配置された全てのノードで１個の鍵（事前共有鍵）を共有し、自分と同じ列に配置された全てのノードで１個の鍵（事前共有鍵）を共有するため、計２個の鍵（事前共有鍵）を事前に保有する場合を想定する。しかしながら、図３、４を参照して説明したように、ネットワーク上の通信ノードが、仮想的なマトリクス空間に配置され、各通信ノードは、同じ行、同じ列に配置されたそれぞれのノードとの鍵（事前共有鍵）を保有する場合を想定しても良い。その場合でも、上記（Ａ１）のメリットを保ったまま、仲介通信ノードが盗難解析されて事前共有鍵が解読されても、共有鍵は完全に復元できず、暗号化通信の完全な解読が困難であるという効果を奏する。
【００６１】
＜＜通信ノード＞＞
図１に示されているようなアドホックネットワークは複数の通信ノードを含んでいる。仮想的なマトリクス空間では、各通信ノードは、行番号および列番号で特定されるマトリックス要素に対応する。よって、仮想的なマトリクス空間でｖ行u列に配置される通信ノードを通信ノード（ｕ、ｖ）と表すこともある。このとき、通信ノード（ｕ、ｖ）はインデックスＩＤ（ｕ、ｖ）を有するとも言う。またインデックスのことを単に「ＩＤ」と呼ぶこともある。通信ノードのアドレスとは、たとえば、ＭＡＣアドレスのように通信ノードの一つを特定できるものである。
【００６２】
各通信ノードは事前共有鍵を２つずつ保有している。そして、２つの通信ノード同士で鍵を共有することで、暗号化通信を行えるようにする。そのために、ある通信ノードから、もう一方の通信ノードに対して、共有鍵を送信する。そして、共有鍵を受信した通信ノード（宛先ＩＤを有する通信ノード、または単に宛先の通信ノードとも呼ぶ）は、共有鍵を送信した通信ノード（送信元ＩＤを有する通信ノード、または単に送信元の通信ノードとも呼ぶ）と鍵を共有し、暗号化通信を行えるようになる。共有鍵は、ネットワーク上の各ノードが保有する鍵を用いて暗号化されて送られる。
【００６３】
図９は、上述のように通信ノード同士で鍵の共有を行うアドホックネットワークを構成する通信ノードの機能ブロック図である。
【００６４】
通信ノード３００は、送信元ノードから宛先ノードに共有鍵から生成される第１の分散共有鍵に関する情報を含むパケットと第２の分散共有鍵に関する情報を含むパケットを送付し前記送信元ノードと前記宛先ノードの間で共有することによって暗号化通信を行うネットワークを構成する通信ノードである。
【００６５】
通信ノード３００は、判定部３０２、通信部３０４、送信先決定部３０６、記憶部３０８、演算部３１０、および鍵生成部３１２を含む。通信部３０４をさらに、送信部３０４２、受信部３０４４を含み得る。演算部３１０は、分散鍵演算部３１０２、共有鍵復元部３１０４を含み得る。
【００６６】
記憶部３０８は、自身の仮想的なマトリックス空間でのインデックスと事前共有鍵とを記憶する。たとえば記憶部３０８は、ネットワークを構成する複数のノードの各々が配置される、行および列を有する仮想的なマトリクス空間中の行で定まる第１の事前共有鍵と、列で定まる第２の事前共有鍵とを記憶する。
【００６７】
鍵生成部３１２は、自身が送付元の通信ノードの場合、宛先の通信ノードと共有したい共有鍵を生成する。たとえば鍵生成部３１２は、送信元ノードから宛先ノードに共有鍵に関する情報を含む複数のパケットを送付し送信元ノードと宛先ノードの間で鍵を共有することによって暗号化通信を行うための共有鍵を、自身が前記送信元ノードの場合に生成する。
【００６８】
演算部３１０の分散鍵演算部３１０２は、鍵生成部３１２で生成された共有鍵から、秘密分散法を用いて第１の分散共有鍵と第２の分散共有鍵を生成する。
【００６９】
また演算部３１０の分散鍵演算部３１０２は、第１の事前共有鍵または第２の事前共有鍵を用いて第１の分散共有鍵および第２の分散共有鍵を暗号化する暗号化する。
【００７０】
たとえば演算部３１０の分散鍵演算部３１０２は、第１の事前共有鍵または第２の事前共有鍵を用いて第１の分散共有鍵および第２の分散共有鍵を暗号化する。その際、送付先ノードが仮想的なマトリクス空間中で同じ行にある場合は、第１の分散共有鍵または第２の分散共有鍵を第１の事前共有鍵を用いて暗号化し、送付先ノードが仮想的なマトリクス空間中で同じ列にある場合は、第１の分散共有鍵または第２の分散共有鍵を第２の事前共有鍵を用いて暗号化しても良い。
【００７１】
たとえば演算部３１０の共有鍵復元部３１０４は、第１のパケットもしくは第２のパケットを受信したとき、暗号化された第１の分散共有鍵もしくは暗号化された第２の分散共有鍵から第１の分散共有鍵もしくは第２の分散共有鍵を復元する、または第１のパケットおよび第２のパケットを受信したとき、暗号化された第１の分散共有鍵および暗号化された第２の分散共有鍵から共有鍵を復元する。さらに、分散鍵演算部３１０は、自身が前記送信元ノードでない場合に、第１の分散共有鍵を第１もしくは第２の事前共有鍵を用いて暗号化する、または第２の分散共有鍵を第１もしくは第２の事前共有鍵を用いて暗号化する。
【００７２】
判定部３０２は、自身が送信元の通信ノードの場合は鍵を共有したい相手の通信ノード（宛先の通信ノード）、または自身が仲介通信ノードの場合は受信したパケットに含まれている宛先の通信ノードのインデックスから、宛先の通信ノードが仮想的なマトリクス空間で自身と同じ行または同じ列にあるかどうかを判定する。このとき送付先決定部３０６は、判定の結果を参照し、仮想的なマトリクス空間中で同じ行または列にある場合は宛先ノードを、仮想的なマトリクス空間中で同じ行または列にない場合、仮想的なマトリクス空間中で宛先ノードと同じ行または列にある複数のノードの一つを送付先ノードとする。
【００７３】
通信部３０４は、自身が送信元の通信ノードの場合は、隣接する通信ノードに対して、送信元の通信ノードから宛先の通信ノードへの鍵の共有要求を送信する。また自身が仲介通信ノードの場合は、送信元の通信ノードから宛先の通信ノードへの鍵の共有要求を送受信する。
【００７４】
たとえば通信部３０４の受信部３０４４は、自身が送信元ノードでない場合に、暗号化された第１の分散共有鍵に関する情報を含む複数のパケットのうちの第１のパケット、および／または暗号化された第２の分散共有鍵に関する情報を含む複数のパケットのうちの第２のパケットを受信する。
【００７５】
たとえば通信部３０４の送信部３０４２は、第１のパケットおよび／または第２のパケットをそれぞれの送付先ノードに送信する。
【００７６】
送付先決定部３０６は、判定部３０２の判定結果を参照して、自身が送信元の通信ノードの場合は、暗号化された事前共有鍵と宛先の通信ノードに関する情報を送信する隣接する通信ノードを決定する。また、自身が仲介通信ノードの場合は、受信した暗号化された分散共有鍵を送信する隣接する通信ノードを決定する。たとえば送付先決定部３０６は、暗号化された第１の分散共有鍵に関する情報を含む第１のパケットと、暗号化された第２の分散共有鍵に関する情報を含む第２のパケットが、仮想的なマトリクス空間上で２つの異なる経路に対応して複数のノードを伝達して送付元ノードから宛先ノードまで送られるように、第１のパケットおよび／または第２のパケットの送付先ノードを特定する。
【００７７】
より詳細には、送付先決定部３０６、送付元ノードと宛先ノードが仮想的なマトリクス空間中で同じ行にある場合は、第１のパケットを送付元ノードから直接、宛先ノードに送り、第２のパケットを、送付元ノードと仮想的なマトリクス空間中で同じ列にある第１の仲介ノードと、第１の仲介ノードと仮想的なマトリクス空間中で同じ行にあり宛先ノードと同じ列にある第２の仲介ノードを介して送付元ノードから宛先ノードに送るように仮想的なマトリクス空間上で２つの異なる経路を決定し、送付元ノードと宛先ノードが仮想的なマトリクス空間中で同じ列にある場合は、第２のパケットを送付元ノードから直接、宛先ノードに送り、第１のパケットを、送付元ノードと仮想的なマトリクス空間中で同じ行にある第１の仲介ノードと、第１の仲介ノードと仮想的なマトリクス空間中で同じ列にあり宛先ノードと同じ行にある第２の仲介ノードを介して送付元ノードから宛先ノードに送るように仮想的なマトリクス空間上で２つの異なる経路を決定し、送付元ノードと宛先ノードが仮想的なマトリクス空間中で同じ行にも列にもない場合は、第１のパケットを、仮想的なマトリクス空間中で自身と同じ行にあり宛先ノードと同じ列にある第２の仲介ノードを介して、第２のパケットを、仮想的なマトリクス空間中で自身と同じ列にあり宛先ノードと同じ行にある第３の仲介ノードを介して送付元ノードから宛先ノードに送るように仮想的なマトリクス空間上で２つの異なる経路を決定する。
【００７８】
図１０は、各通信ノードの通信部が送受信するパケットのフォーマットの例を示す図である。
【００７９】
図１０に示されているフォーマット４００は、送付先ノードアドレス４０２、前ノードアドレス４０４０、データ部４０６を含んでいる。データ部４０６はさらに、宛先ＩＤ４０８、鍵送信元ＩＤ４１０、送信元ＩＤ４１２、仲介ノードＩＤ１（４１４）、仲介ノードＩＤ２（４１６）、暗号化された分散共有鍵４１８を含んでいる。
【００８０】
送付先ノードアドレス４０２のフィールドには、このパケットを受け取る通信ノードのアドレスが格納される。ここでアドレスとは、アドホックネットワークを構成する複数の通信ノードのうちの一つを特定し得るものである。たとえば、ＭＡＣアドレスなどである。
【００８１】
前ノードアドレス４０４のフィールドには、このパケットを送信した通信ノードのアドレスが格納される。
【００８２】
データ部４０６の宛先ＩＤ４０８のフィールドには、暗号化通信を行う２つの通信ノードのうち、鍵共有要求を受信する通信ノードのインデックスが格納される。たとえば、通信ノード（ｕ、ｖ）から通信ノード（ｘ、ｙ）に鍵共有要求を送信する場合、データ部４０６の宛先ＩＤ４０８は、ＩＤ（ｘ、ｙ）であっても良い。
【００８３】
データ部４０６の鍵送信元ＩＤ４１０のフィールドには、暗号化通信を行う２つの通信ノードのうち、鍵共有要求を送信する通信ノードのインデックスが格納される。たとえば、通信ノード（ｕ、ｖ）から通信ノード（ｘ、ｙ）に鍵共有要求を送信する場合、データ部４０６の鍵送信元ＩＤ４１２は、ＩＤ（ｕ、ｖ）であっても良い。
【００８４】
データ部４０６の送信元ＩＤ４１２のフィールドには、このパケットを送信した通信ノードのインデックスが格納される。
【００８５】
データ部４０６の仲介ノードＩＤ１（４１４）のフィールドには、パケットを中継する最初の仲介通信ノードのインデックスが格納される。たとえば、暗号化された分散共有鍵を通信ノード（ｕ、ｖ）、通信ノード（ｓ、ｖ）、通信ノード（ｓ、ｙ）、通信ノード（ｘ、ｙ）の順で通信ノード（ｕ、ｖ）から通信ノード（ｘ、ｙ）に送る場合、データ部４０６の仲介ノードＩＤ１（４１４）のフィールドには、通信ノード（ｓ、ｖ）のインデックスＩＤ（ｓ、ｖ）が格納される。
【００８６】
データ部４０６の仲介ノードＩＤ２（４１６）のフィールドには、パケットを中継する２番目の仲介通信ノードのインデックスが格納される。たとえば、暗号化された分散共有鍵を通信ノード（ｕ、ｖ）、通信ノード（ｓ、ｖ）、通信ノード（ｓ、ｙ）、通信ノード（ｘ、ｙ）の順で通信ノード（ｕ、ｖ）から通信ノード（ｘ、ｙ）に送る場合、データ部４０６の仲介ノードＩＤ２（４１６）のフィールドには、通信ノード（ｓ、ｙ）のインデックスＩＤ（ｓ、ｙ）が格納される。
【００８７】
データ部４０６の暗号化された分散共有鍵４１８のフィールドには、暗号化された分散共有鍵に関する情報が格納される。
【００８８】
このような構成を採用することによって、確定的に全ノード間で鍵を共有でき、事前に保有する共有鍵は２個であるというメリットを保ったまま、一つのノードの事前共有鍵が漏洩した場合でも、共通鍵暗号の鍵は完全に復元することを避けることができる。
【００８９】
以下では、上のような通信装置３００で構成されるアドホックネットワークにおける通信ノード同士の鍵の共有の処理について説明する。
【００９０】
＜＜仮想的なマトリクス空間中で同じ行に配置された通信ノード同士で鍵を共有する場合＞＞
図１１は、第２の実施例に従うアドホックネットワーク５００を示している。アドホックネットワーク５００では、仮想的なマトリクス空間中で同じ行に配置された通信ノード同士で鍵を共有したいとする。図１１では、通信ノード５０２と通信ノード５０４が鍵を共有したいとする。
【００９１】
図１１に示されているように、ネットワーク５００は通信ノード５０２、５０４、５０６、５０８を含む４つ以上の通信ノードを含んでいる。仮想的なマトリクス空間では、通信ノード５０２はｕ列ｖ行に対応する。よって、通信ノード５０２を通信ノード（ｕ、ｖ）と表すこともある。同様に、通信ノード５０４は、仮想的なマトリクス空間では通信ノード（ｕ、ｖ）と同じ行であるが別の列ｘに存在し、通信ノード（ｘ、ｖ）とも表される。通信ノード５０６は、仮想的なマトリクス空間では通信ノード（ｕ、ｖ）と同じ列であるが別の行ｔに存在し、通信ノード（ｕ、ｔ）とも表される。通信ノード５０８は、仮想的なマトリクス空間で通信ノード（ｘ、ｖ）と同じ列、通信ノード（ｕ、ｔ）と同じ行に存在し、通信ノード（ｘ、ｔ）とも表される。
【００９２】
通信ノード（ｕ、ｖ）は２つの事前共有鍵Ｋｕ、Ｌｖを保有する。通信ノード（ｘ、ｖ）は２つの事前共有鍵Ｋｘ、Ｌｖを保有する。通信ノード（ｕ、ｔ）と通信ノード（ｘ、ｖ）は仮想的なマトリクス空間では同じ行に配置されているので、ともに事前共有鍵Ｌｖを保有している。通信ノード（ｕ、ｔ）は２つの事前共有鍵Ｋｕ、Ｌｔを保有する。通信ノード（ｕ、ｔ）と通信ノード（ｕ、ｖ）は仮想的なマトリクス空間では同じ列に配置されているので、ともに事前共有鍵Ｋｕを保有している。通信ノード（ｘ、ｔ）は２つの事前共有鍵Ｋｘ、Ｌｔを保有する。通信ノード（ｕ、ｔ）と通信ノード（ｘ、ｔ）は仮想的なマトリクス空間では同じ行に配置されているので、ともに事前共有鍵Ｌｔを保有している。通信ノード（ｘ、ｔ）と通信ノード（ｘ、ｖ）は仮想的なマトリクス空間では同じ列に配置されているので、ともに事前共有鍵Ｋｘを保有している。
【００９３】
図１２を参照して、仮想的なマトリクス空間中で同じ行に配置された通信ノード同士で鍵を共有する場合の処理の流れの例について説明する。
【００９４】
図１２は、通信ノード同士で鍵を共有する場合の処理の流れの例を示す図である。
また、通信ノードが図１７に示されているような汎用コンピュータ９００である場合には、下記の説明は、そのような処理を行う制御プログラム（通信制御プログラム）を定義する。すなわち、以下では、下記に説明する処理を汎用コンピュータに行わせる制御プログラム（通信制御プログラム）の説明でもある。
【００９５】
Ｓ１０２で通信ノード（ｕ、ｖ）の鍵生成部３１２は、共有鍵ＭＫを生成する。
次のＳ１０４で次に通信ノード（ｕ、ｖ）の分散鍵演算部３１０２は、秘密分散により共有鍵ＭＫを分散共有鍵ＭＫ１と分散共有鍵ＭＫ２に分散する。共有鍵ＭＫと分散共有鍵ＭＫ１、ＭＫ２は、「＋」を排他的論理和を表す記号とすると、ＭＫ＝ＭＫ１＋ＭＫ２を満たす。具体的には、鍵生成部により分散共有鍵ＭＫ１を生成し、共有鍵ＭＫとのＸＯＲ演算を計算することで、ＭＫ２＝ＭＫ＋ＭＫ１を得る。本ステップの処理が終了すると処理はＳ１０６に進む。
【００９６】
Ｓ１０６で次に通信ノード（ｕ、ｖ）の送付先決定部３０６は、分散共有鍵ＭＫ１と分散共有鍵ＭＫ２の送付先の通信ノードを決定する。
【００９７】
たとえば、宛先の通信ノードのインデックスをＩＤ（ｘ、ｖ）とすると、宛先の通信ノード（ｘ、ｖ）は、送信元の通信ノード（ｕ、ｖ）と仮想的なマトリクス空間では同じ行に配置されていることが分かる。よって、通信ノード（ｕ、ｖ）は、分散共有鍵ＭＫ１の送付先を通信ノード（ｘ、ｖ）と決定する。
【００９８】
事前共有鍵ＭＫ２の送付先は、自身、すなわち通信ノード（ｕ、ｖ）と仮想的なマトリクス空間で同じ列に配置されている別の通信ノードの中から、ランダムに一つを決定する。この通信ノードを通信ノード（ｕ、ｔ）とする。本ステップの処理が終了すると処理はＳ１０８に進む。
【００９９】
Ｓ１０８で通信ノード（ｕ、ｖ）の分散鍵演算部３１０２は、宛先の通信ノード（ｘ、ｖ）と共有している事前共有鍵の一つである事前共有鍵Ｌｖを用いて分散事前共有鍵ＭＫ１を暗号化し、通信ノード（ｕ、ｖ）の送信部３０４２は、暗号化された分散事前共有鍵ＭＫ１を、ＥＬｖ（ＭＫ１）を宛先の通信ノード（ｘ、ｖ）に送信する。本ステップの処理が終了すると処理はＳ１１０に進む。
【０１００】
Ｓ１１０で通信ノード（ｕ、ｖ）の分散鍵演算部３１０２は、通信ノード（ｕ、ｔ）と共有する事前共有鍵Ｋｕを用いて分散共有鍵ＭＫ２を暗号化し、通信ノード（ｕ、ｖ）の送信部３０４２は、宛先の通信ノード（ｘ、ｖ）に関する情報と暗号化された分散共有鍵ＥＫｕ（ＭＫ２）を通信ノード（ｕ、ｔ）に送信する。本ステップの処理が終了すると処理はＳ１１２に進む。ここでＳ１０８とＳ１１０の処理の順番は、逆であっても良い。Ｓ１０８とＳ１１０の処理が終了すると、処理はＳ１１２に進む。
【０１０１】
Ｓ１１２で通信ノード（ｕ、ｔ）の共有鍵復元部３１０４は、受信した暗号化された分散共有鍵ＥＫｕ（ＭＫ２）を復号し、分散共有鍵ＭＫ２を得る。通信ノード（ｕ、ｔ）の判定部３０２は、宛先の通信ノードが通信ノード（ｘ、ｖ）であることを確認すると、宛先の通信ノードは自身ではなく、また、仮想的なマトリクス空間で同じ行でも同じ列でもないので、次の送信先の通信ノードとして仲介通信ノード（ｘ、ｔ）を選択する。仲介通信ノードは、自身のノードのインデックスＩＤ（ｕ、ｔ）と宛先のノードのインデックスＩＤ（ｘ、ｖ）から決定される。今の場合、仮想的なマトリクス空間で、通信ノード（ｕ、ｔ）と通信ノード（ｘ、ｖ）のいずれかと同じ行または同じ列に配置されており、送付元の通信ノード（ｕ、ｖ）と異なる通信ノードとして、通信ノード（ｘ、ｔ）が仲介通信ノードとして選択される。ここで、通信ノード（ｕ、ｔ）は仲介通信ノード（ｘ、ｔ）とは、仮想的なマトリクス空間で同じ行に配置されるので、通信ノード（ｕ、ｔ）と通信ノード（ｘ、ｔ）はともに事前共有鍵Ｌｔを保有している。
【０１０２】
Ｓ１１２で通信ノード（ｕ、ｔ）の分散鍵演算部３１０２は、事前共有鍵Ｌｔを用いて分散共有鍵ＭＫ２を暗号化する。さらにＳ１１２で通信ノード（ｕ、ｔ）の送信部３０４２は、暗号化された分散共有鍵ＥＬｔ（ＭＫ２）を通信ノード（ｘ、ｔ）に送信する。本ステップの処理が終了すると処理はＳ１１４に進む。
【０１０３】
Ｓ１１４で通信ノード（ｘ、ｔ）の共有鍵復元部３１０４は、受信した暗号化分散共有鍵ＥＬｔ（ＭＫ２）を事前共有鍵Ｌｔを用いて復号し、分散共有鍵ＭＫ２を得る。通信ノード（ｘ、ｔ）の判定部３０２が、宛先の通信ノードのインデックスを確認すると、宛先の通信ノードは自分ではないが、同じ列に配置されていることが分かるため、通信ノード（ｘ、ｔ）の送付先決定部３０６は、次の送信先ノードとして宛先の通信ノード（ｘ、ｖ）を選択する。そして通信ノード（ｘ、ｔ）の分散鍵演算部３１０２は、通信ノード（ｘ、ｖ）との共有鍵Ｋｖを用いて分散共有鍵ＭＫ２を暗号化し、通信ノード（ｘ、ｔ）の送信部３０４２は、暗号化された分散共有鍵ＥＫｘ（ＭＫ２）を通信ノード（ｘ、ｖ）に送信する。本ステップの処理が終了すると処理はＳ１１６に進む。
【０１０４】
Ｓ１１６で通信ノード（ｘ、ｖ）は、受信した暗号化された分散共有鍵ＥＬｖ（ＭＫ１）とＥＫｘ（ＭＫ２）を復号する。そして、分散共有鍵ＭＫ１とＭＫ２をＸＯＲ演算することで、共有鍵ＭＫを復元する。
【０１０５】
以上のように、本例では、共有鍵ＭＫを分散共有鍵ＭＫ１とＭＫ２に分散し、それぞれ別のノードを介して宛先の通信ノードに送信する。それによって、ある通信ノードが解析されて、事前共有鍵が漏洩しても、その事前共有情報を用いて他の通信ノード間の暗号化通信に使用する共有鍵を入手できないようになる。
【０１０６】
例えば、送信元の通信ノード（ｕ、ｖ）との事前共有鍵Ｌｖを保有する通信ノード（ａ、ｖ）が解析された場合、事前共有鍵ＫａとＬｖが漏洩する。事前共有鍵Ｌｖを入手した攻撃者は、暗号化された分散共有鍵ＥＬｖ（ＭＫ１）を復号できるため、分散共有鍵ＭＫ１を得ることができる。しかし攻撃者は、暗号化された分散共有鍵ＥＫｕ（ＭＫ２）、ＥＬｔ（ＭＫ２）、 ＥＫｖ（ＭＫ２）を復号するための事前共有鍵Ｋｕ、Ｌｔ、Ｋｖを入手できない。つまり、攻撃者は分散共有鍵ＭＫ２を得ることはできない。よって、共有鍵ＭＫを復元することはできない。
【０１０７】
＜＜仮想的なマトリクス空間中で同じ列に配置された通信ノード同士で鍵を共有する場合＞＞
図１３は、第２の実施例に従うアドホックネットワーク６００を示している。アドホックネットワーク６００では、仮想的なマトリクス空間中で同じ列に配置された通信ノード同士で鍵を共有したいとする。図１３では、通信ノード６０２と通信ノード６０６が鍵を共有したいとする。
【０１０８】
図１３に示されているように、ネットワーク６００は通信ノード６０２、６０４、６０６、６０８を含む４つ以上の通信ノードを含んでいる。仮想的なマトリクス空間では、通信ノード６０２はｕ列ｖ行に対応する。よって、通信ノード６０２を通信ノード（ｕ、ｖ）と表すこともある。同様に、通信ノード６０４は、仮想的なマトリクス空間では通信ノード（ｕ、ｖ）と同じ行であるが別の列ｓに存在し、通信ノード（ｓ、ｖ）とも表される。通信ノード６０６は、仮想的なマトリクス空間では通信ノード（ｕ、ｖ）と同じ列であるが別の行ｔに存在し、通信ノード（ｕ、ｔ）とも表される。通信ノード６０８は、仮想的なマトリクス空間で通信ノード（ｓ、ｖ）と同じ列、通信ノード（ｕ、ｙ）と同じ行に存在し、通信ノード（ｓ、ｙ）とも表される。
【０１０９】
通信ノード（ｕ、ｖ）は２つの事前共有鍵Ｋｕ、Ｌｖを保有する。通信ノード（ｓ、ｖ）は２つの事前共有鍵Ｋｓ、Ｌｖを保有する。通信ノード（ｕ、ｔ）と通信ノード（ｓ、ｖ）は仮想的なマトリクス空間では同じ列に配置されているので、ともに事前共有鍵Ｌｖを保有している。通信ノード（ｕ、ｙ）は２つの事前共有鍵Ｋｕ、Ｌｙを保有する。通信ノード（ｕ、ｙ）と通信ノード（ｕ、ｖ）は仮想的なマトリクス空間では同じ行に配置されているので、ともに事前共有鍵Ｋｕを保有している。通信ノード（ｓ、ｙ）２つの事前共有鍵Ｋｓ、Ｌｙを保有する。通信ノード（ｕ、ｙ）と通信ノード（ｓ、ｙ）は仮想的なマトリクス空間では同じ列に配置されているので、ともに事前共有鍵Ｌｙを保有している。通信ノード（ｓ、ｖ）と通信ノード（ｓ、ｙ）は仮想的なマトリクス空間では同じ列に配置されているので、ともに事前共有鍵Ｋｓを保有している。
【０１１０】
図１４を参照して、仮想的なマトリクス空間中で同じ列に配置された通信ノード同士で鍵を共有する場合の処理の流れの例について説明する。
【０１１１】
図１４は、通信ノード同士で鍵を共有する場合の処理の流れの別の例を示す図である。
また、通信ノードが図１７に示されているような汎用コンピュータ９００である場合には、下記の説明は、そのような処理を行う制御プログラム（通信制御プログラム）を定義する。すなわち、以下では、下記に説明する処理を汎用コンピュータに行わせる制御プログラム（通信制御プログラム）の説明でもある。
【０１１２】
Ｓ２０２で通信ノード（ｕ、ｖ）の鍵生成部３１２は、共有鍵ＭＫを生成する。
次のＳ２０４で通信ノード（ｕ、ｖ）の分散鍵演算部３１０２は、秘密分散により共有鍵ＭＫを分散共有鍵ＭＫ１と分散共有鍵ＭＫ２に分散する。共有鍵ＭＫと分散共有鍵ＭＫ１、ＭＫ２は、「＋」を排他的論理和を表す記号とすると、ＭＫ＝ＭＫ１＋ＭＫ２を満たす。たとえば通信ノード（ｕ、ｖ）の分散鍵演算部３１０２は、鍵生成部により分散共有鍵ＭＫ１を生成し、共有鍵ＭＫとのＸＯＲ演算を計算することで、ＭＫ２＝ＭＫ＋ＭＫ１を得る。本ステップの処理が終了すると処理はＳ２０６に進む。
【０１１３】
Ｓ２０６で通信ノード（ｕ、ｖ）の送付先決定部３０６は、分散共有鍵ＭＫ１と分散共有鍵ＭＫ２の送付先の通信ノードを決定する。
【０１１４】
たとえば、宛先の通信ノードのインデックスＩＤ（ｕ、ｙ）とすると、宛先の通信ノード（ｕ、ｙ）は、送信元の通信ノード（ｕ、ｖ）と仮想的なマトリクス空間では同じ列に配置されていることが分かる。よって、通信ノード（ｕ、ｖ）の送付先決定部３０６は、分散共有鍵ＭＫ１の送付先を通信ノード（ｕ、ｙ）と決定する。また、通信ノード（ｕ、ｖ）の送付先決定部３０６は、事前共有鍵ＭＫ２の送付先は、自身、すなわち通信ノード（ｕ、ｖ）と仮想的なマトリクス空間で同じ行に配置されている別の通信ノードの中から、ランダムに一つを決定する。この通信ノードを通信ノード（ｓ、ｖ）とする。本ステップの処理が終了すると処理はＳ２０８に進む。
【０１１５】
Ｓ２０８で通信ノード（ｕ、ｖ）の分散鍵演算部３１０２は、通信ノード（ｕ、ｙ）と共有している事前共有鍵Ｋｕを用いて分散事前共有鍵ＭＫ１を暗号化し、通信ノード（ｕ、ｖ）の送信部３０４２は、暗号化された分散事前共有鍵ＥＫｕ（ＭＫ１）を宛先の通信ノード（ｕ、ｙ）に送信する。本ステップの処理が終了すると処理はＳ２１０に進む。
【０１１６】
Ｓ２１０で通信ノード（ｕ、ｖ）の分散鍵演算部３１０２は、通信ノード（ｓ、ｖ）と共有する事前共有鍵Ｌｖを用いて分散共有鍵ＭＫ２を暗号化し、通信ノード（ｕ、ｖ）の送信部３０４２は、宛先の通信ノード（ｕ、ｙ）に関する情報と暗号化された分散共有鍵ＥＬｖ （ＭＫ２）を通信ノード（ｓ、ｖ）に送信する。ここでＳ２０８とＳ２１０の処理の順番は、逆であっても良い。Ｓ２０８とＳ２１０の処理が終了すると処理はＳ２１２に進む。
【０１１７】
Ｓ２１２で通信ノード（ｓ、ｖ）の共有鍵復元部３１０４は、受信した暗号化された分散共有鍵ＥＬｖ （ＭＫ２）を復号し、分散共有鍵ＭＫ２を得る。通信ノード（ｓ、ｖ）の判定部３０２は、宛先の通信ノードは自身ではなく、また、仮想的なマトリクス空間で同じ行でも同じ列でもないことを判定し、通信ノード（ｓ、ｖ）の送付先決定部３０６は、次の送信先の通信ノードとして仲介通信ノード（ｓ、ｙ）を選択する。仲介通信ノードは、自身のノードのインデックスＩＤ（ｓ、ｖ）と宛先のノードのインデックスＩＤ（ｘ、ｖ）から決定される。今の場合、仮想的なマトリクス空間で、通信ノード（ｓ、ｖ）と宛先の通信ノード（ｕ、ｙ）のいずれかと同じ行または同じ列に配置されており、送付元の通信ノード（ｕ、ｖ）と異なる通信ノードとして、通信ノード（ｓ、ｙ）が仲介通信ノードとして選択される。
【０１１８】
通信ノード（ｓ、ｖ）は仲介通信ノード（ｓ、ｙ）とは、仮想的なマトリクス空間で同じ列に配置されるので、通信ノード（ｓ、ｖ）と通信ノード（ｓ、ｙ）はともに事前共有鍵Ｋｓを保有している。通信ノード（ｓ、ｖ）の送信部３０４２は事前共有鍵Ｋｓを用いて分散共有鍵ＭＫ２を暗号化し、暗号化された分散共有鍵ＥＫｓ（ＭＫ２）を通信ノード（ｓ、ｙ）に送信する。本ステップの処理が終了すると処理はＳ２１４に進む。
【０１１９】
Ｓ２１４で通信ノード（ｓ、ｙ）の受信部３０４４は、暗号化分散共有鍵ＥＫｓ（ＭＫ２）を受信する。さらに通信ノード（ｓ、ｙ）の分散鍵演算部３１０２は、事前共有鍵Ｋｓを用いて復号し、分散共有鍵ＭＫ２を得る。通信ノード（ｓ、ｙ）の判定部３０２は、宛先の通信ノードのインデックスを参照し、宛先の通信ノードは自分ではないが、同じ行に配置されていることを確認し、通信ノード（ｓ、ｙ）の送付先決定部３０６は、次の送信先ノードとして宛先の通信ノード（ｕ、ｙ）を選択する。そして通信ノード（ｓ、ｙ）の分散鍵演算部３１０２は、通信ノード（ｕ、ｙ）との共有鍵Ｌｙを用いて分散共有鍵ＭＫ２を暗号化し、通信ノード（ｓ、ｙ）の送信部３０４２は、暗号化された分散共有鍵ＥＬｙ（ＭＫ２）を通信ノード（ｕ、ｙ）に送信する。本ステップの処理が終了すると処理はＳ２１６に進む。
【０１２０】
Ｓ２１６で通信ノード（ｕ、ｙ）は、受信した暗号化された分散共有鍵ＥＫｕ（ＭＫ１）とＥＬｙ（ＭＫ２）を復号する。そして、分散共有鍵ＭＫ１とＭＫ２をＸＯＲ演算することで、共有鍵ＭＫを復元する。
【０１２１】
以上のように、本例では、共有鍵ＭＫを分散共有鍵ＭＫ１とＭＫ２に分散し、それぞれ別のノードを介して宛先の通信ノードに送信する。それによって、ある通信ノードが解析されて、事前共有鍵が漏洩しても、その事前共有情報を用いて他の通信ノード間の暗号化通信に使用する共有鍵を入手できないようになる。
【０１２２】
例えば、送信元の通信ノード（ｕ、ｖ）との事前共有鍵Ｋｕを保有する通信ノード（ｕ、ｂ）が解析された場合、事前共有鍵ＫｕとＬｂが漏洩する。事前共有鍵Ｋｕを入手した攻撃者は、暗号化された分散共有鍵ＥＫｕ（ＭＫ１）を復号できるため、分散共有鍵ＭＫ１を得ることができる。しかし攻撃者は、暗号化された分散共有鍵ＥＬｖ（ＭＫ２）、ＥＫｓ（ＭＫ２）、 ＥＬｙ（ＭＫ２）を復号するための事前共有鍵Ｌｖ、Ｋｓ、Ｌｙを入手できない。つまり、攻撃者は分散共有鍵ＭＫ２を得ることはできない。よって、共有鍵ＭＫを復元することはできない。
【０１２３】
＜＜仮想的なマトリクス空間中で同じ行にも同じ列にも配置されていない通信ノード同士で鍵を共有する場合＞＞
図１５は、第２の実施例に従うアドホックネットワーク７００を示している。アドホックネットワーク７００では、仮想的なマトリクス空間中で同じ行にも同じ列にも配置されていない通信ノード同士で鍵を共有したいとする。図１５では、通信ノード７０２と通信ノード７０８が鍵を共有したいとする。
【０１２４】
図１５に示されているように、ネットワーク７００は通信ノード７０２、７０４、７０６、７０８を含む４つ以上の通信ノードを含んでいる。仮想的なマトリクス空間では、通信ノード７０２はｕ列ｖ行に対応する。よって、通信ノード７０２を通信ノード（ｕ、ｖ）と表すこともある。同様に、通信ノード７０４は、仮想的なマトリクス空間では通信ノード（ｕ、ｖ）と同じ行であるが別の列ｘに存在し、通信ノード（ｘ、ｖ）とも表される。通信ノード７０６は、仮想的なマトリクス空間では通信ノード（ｕ、ｖ）と同じ列であるが別の行ｙに存在し、通信ノード（ｕ、ｙ）とも表される。通信ノード７０８は、仮想的なマトリクス空間で通信ノード（ｘ、ｖ）と同じ列、通信ノード（ｕ、ｙ）と同じ行に存在し、通信ノード（ｘ、ｙ）とも表される。
【０１２５】
通信ノード（ｕ、ｖ）は２つの事前共有鍵Ｋｕ、Ｌｖを保有する。通信ノード（ｘ、ｖ）は２つの事前共有鍵Ｋｘ、Ｌｖを保有する。通信ノード（ｕ、ｖ）と通信ノード（ｘ、ｖ）は仮想的なマトリクス空間では同じ行に配置されているので、ともに事前共有鍵Ｌｖを保有している。通信ノード（ｕ、ｙ）は２つの事前共有鍵Ｋｕ、Ｌｙを保有する。通信ノード（ｕ、ｙ）と通信ノード（ｕ、ｖ）は仮想的なマトリクス空間では同じ列に配置されているので、ともに事前共有鍵Ｋｕを保有している。通信ノード（ｘ、ｙ）は２つの事前共有鍵Ｋｘ、Ｌｙを保有する。通信ノード（ｕ、ｙ）と通信ノード（ｘ、ｙ）は仮想的なマトリクス空間では同じ行に配置されているので、ともに事前共有鍵Ｌｙを保有している。通信ノード（ｘ、ｖ）と通信ノード（ｘ、ｙ）は仮想的なマトリクス空間では同じ行に配置されているので、ともに事前共有鍵Ｋｘを保有している。
【０１２６】
図１６を参照して、仮想的なマトリクス空間中で同じ行にも同じ列にも配置されていない通信ノード同士で鍵を共有する場合の処理の流れの例について説明する。
【０１２７】
図１６は、通信ノード同士で鍵を共有する場合の処理の流れのさらに別の例を示す図である。
【０１２８】
また、通信ノードが図１７に示されているような汎用コンピュータ９００である場合には、下記の説明は、そのような処理を行う制御プログラム（通信制御プログラム）を定義する。すなわち、以下では、下記に説明する処理を汎用コンピュータに行わせる制御プログラム（通信制御プログラム）の説明でもある。
【０１２９】
Ｓ３０２で通信ノード（ｕ、ｖ）の鍵生成部３１２は、共有鍵ＭＫを生成する。
次のＳ３０４で通信ノード（ｕ、ｖ）の分散鍵演算部３１０２は、秘密分散により共有鍵ＭＫを分散共有鍵ＭＫ１と分散共有鍵ＭＫ２に分散する。共有鍵ＭＫと分散共有鍵ＭＫ１、ＭＫ２は、「＋」を排他的論理和を表す記号とすると、ＭＫ＝ＭＫ１＋ＭＫ２を満たす。たとえば、分散共有鍵ＭＫ１と共有鍵ＭＫとのＸＯＲ演算を計算することで、ＭＫ２＝ＭＫ＋ＭＫ１を得る。本ステップの処理が終了すると処理はＳ３０６に進む。
【０１３０】
Ｓ３０６で通信ノード（ｕ、ｖ）の送付先決定部３０６は、宛先の通信ノードのインデックスＩＤ（ｘ、ｙ）から分散共有鍵ＭＫ１と分散共有鍵ＭＫ２の送信先を決定する。通信ノード（ｕ、ｖ）の判定部３０２は、宛先の通信ノードのインデックスＩＤ（ｘ、ｙ）から、送信元の通信ノード（ｕ、ｖ）と仮想的なマトリクス空間で、同じ行にも同じ列にも配置されていないことを確認する。通信ノード（ｕ、ｖ）の送付先決定部３０６は、分散共有鍵ＭＫ１とＭＫ２の送信先は、仲介通信ノードと決定する。仲介通信ノードは、送信元の通信ノードのインデックスＩＤ（ｕ、ｖ）と宛先の通信ノードのインデックスＩＤ（ｘ、ｙ）から、通信ノード（ｘ、ｖ）と通信ノード（ｕ、ｙ）に決定される。本ステップの処理が終了すると処理はＳ３０８に進む。
【０１３１】
Ｓ３０８で通信ノード（ｕ、ｖ）の分散鍵演算部３１０２は、通信ノード（ｘ、ｖ）と共有している事前共有鍵Ｌｖを用いて分散共有鍵ＭＫ１を暗号化する。そして通信ノード（ｕ、ｖ）の送信部３０４２は、通信ノード（ｘ、ｖ）に暗号化された分散共有鍵ＥＬｖ（ＭＫ１）と宛先の通信ノードのインデックスＩＤ（ｘ、ｙ）に関する情報を送信する。
【０１３２】
Ｓ３１０で通信ノード（ｕ、ｖ）の分散鍵演算部３１０２は、通信ノード（ｕ、ｙ）と共有している事前共有鍵Ｋｕを用いて分散共有鍵ＭＫ２を暗号化する。そして、通信ノード（ｕ、ｙ）に暗号化された分散共有鍵ＥＫｕ（ＭＫ２）と宛先の通信ノードのインデックスＩＤ（ｘ、ｙ）に関する情報を送信する。ここでＳ３０８とＳ３１０の処理の順番は、逆であっても良い。Ｓ３０８とＳ３１０の処理が終了すると処理はＳ３１２またはＳ３１４に進む。
【０１３３】
Ｓ３１２で通信ノード（ｘ、ｖ）の受信部３０４４は、暗号化された分散共有鍵ＥＬｖ（ＭＫ１）を受信する。そして、通信ノード（ｘ、ｖ）の共有鍵復号部３１０４は、暗号化された分散共有鍵ＥＬｖ（ＭＫ１）を復号し、分散共有鍵ＭＫ１を得る。また通信ノード（ｘ、ｖ）の判定部３０２は、宛先の通信ノードのインデックスＩＤ（ｘ、ｙ）を参照し、宛先の通信ノードは自分ではないが、同じ列に配置されていることを確認する。そして通信ノード（ｘ、ｖ）の送付先決定部３０６、次の送信先ノードとして宛先の通信ノード（ｘ、ｙ）を選択する。そして、通信ノード（ｘ、ｙ）と共有している共有鍵Ｋｘを用いて分散共有鍵ＭＫ１を暗号化する。そして通信ノード（ｘ、ｖ）の送信部３０４２は、暗号化された分散共有鍵ＥＫｘ（ＭＫ１）と宛先の通信ノードのインデックスＩＤ（ｘ、ｙ）に関する情報を通信ノード（ｘ、ｙ）に送信する。ここでＳ３１０とＳ３１２の処理の順番は、逆であっても良い。
【０１３４】
Ｓ３１４で通信ノード（ｕ、ｙ）の受信部３０４４は、暗号化された分散共有鍵ＥＫｕ（ＭＫ２）を受信する。通信ノード（ｕ、ｙ）の共有鍵復号部３１０４は、暗号化された分散共有鍵ＥＫｕ（ＭＫ２）を復号し、分散共有鍵ＭＫ２を得る。また通信ノード（ｕ、ｙ）の判定部３０２、宛先の通信ノードのインデックスＩＤ（ｘ、ｙ）を参照して、宛先の通信ノードは自分ではないが、同じ行に配置されていることを確認する。そして通信ノード（ｕ、ｙ）の送付先決定部３０６は、次の送信先ノードとして宛先の通信ノード（ｘ、ｙ）を選択する。そして通信ノード（ｕ、ｙ）の分散鍵演算部３１０２は、通信ノード（ｘ、ｙ）と共有している共有鍵Ｋｘを用いて分散共有鍵ＭＫ２を暗号化する。そして通信ノード（ｕ、ｙ）の送信部３０４２は、暗号化された分散共有鍵ＥＫｘ（ＭＫ２）と宛先の通信ノードのインデックスＩＤ（ｘ、ｙ）に関する情報を通信ノード（ｘ、ｙ）に送信する。ここでＳ３１２とＳ３１４の処理の順番は、逆であっても良い。Ｓ３１２とＳ３１４の処理が終了すると処理はＳ３１６に進む。またＳ３１４の処理は、Ｓ３１０、Ｓ３１２の前であっても良い。
【０１３５】
Ｓ３１６で通信ノード（ｘ、ｙ）の受信部３０４４は、暗号化された分散共有鍵ＥＫｘ（ＭＫ１）とＥＬｙ（ＭＫ２）を受信する。通信ノード（ｘ、ｙ）の共有鍵復元部３１０４は、暗号化された分散共有鍵ＥＫｘ（ＭＫ１）とＥＬｙ（ＭＫ２）を復号する。そして通信ノード（ｘ、ｙ）の共有鍵復元部３１０４は、分散共有鍵ＭＫ１とＭＫ２をＸＯＲ演算することで、共有鍵ＭＫを復元する。
【０１３６】
以上のように、本例では、共有鍵ＭＫを分散共有鍵ＭＫ１とＭＫ２に分散し、それぞれ別の仲介通信ノードを介して宛先の通信ノードに送信する。それによって、ある通信ノードが解析されて、事前共有鍵が漏洩しても、その事前共有情報を用いて他の通信ノード間の暗号化通信に使用する共有鍵を入手できないようになる。
【０１３７】
例えば、送信元の通信ノード（ｕ、ｖ）との事前共有鍵Ｌｖを保有する通信ノード（ａ、ｖ）が解析された場合、事前共有鍵ＫａとＬｖが漏洩する。事前共有鍵Ｌｖを入手した攻撃者は、暗号化された分散共有鍵ＥＬｖ（ＭＫ１）を復号できるため、分散共有鍵ＭＫ１を得ることができる。しかし攻撃者は、暗号化された分散共有鍵ＥＫｕ（ＭＫ２）、ＥＬｙ（ＭＫ２）を復号するための事前共有鍵Ｋｕ、Ｌｙを入手できない。つまり、攻撃者は分散共有鍵ＭＫ２を得ることはできない。よって、共有鍵ＭＫを復元することはできない。送信元の通信ノード（ｕ、ｖ）との事前共有鍵Ｋｕを保有する通信ノード（ｕ、ｂ）が解析された場合も同様である。
【０１３８】
以上のように、アドホックネットワークにおいて、確定的に全ノード間で鍵を共有でき、事前に保有する共有鍵は２個であるというメリットを保ったまま、一つのノードの事前共有鍵が漏洩した場合でも、共通鍵暗号の鍵が完全に復元されることを避けることができる。
【０１３９】
図１７は、通信ノードの構成の例を示す図である。
このコンピュータ９００は、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ）９０２、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）９０４、及びＲａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）９０６を備えている。コンピュータ９００は、さらに、ハードディスク装置９０８、入力装置９１０、表示装置９１２、インターフェース装置９１４、及び記録媒体駆動装置９１６を備えている。なお、これらの構成要素はバスライン９１８を介して接続されており、ＣＰＵ９０２の管理の下で各種のデータを相互に授受することができる。
【０１４０】
Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ）９０２は、このコンピュータ９００全体の動作を制御する演算処理装置であり、コンピュータ９００の制御処理部として機能する。
【０１４１】
Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）９０４は、所定の基本制御プログラムが予め記録されている読み出し専用半導体メモリである。ＣＰＵ９０２は、この基本制御プログラムをコンピュータ９００の起動時に読み出して実行することにより、このコンピュータ９００の各構成要素の動作制御が可能になる。
【０１４２】
Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）９０６は、ＣＰＵ９０２が各種の制御プログラムを実行する際に、必要に応じて作業用記憶領域として使用する、随時書き込み読み出し可能な半導体メモリである。
【０１４３】
ＲＡＭ９０６やＲＯＭ９０４は単に「メモリ」と呼ぶことがある。
ハードディスク装置９０８は、ＣＰＵ９０２によって実行される各種の制御プログラムや各種のデータを記憶しておく記憶装置である。ＣＰＵ９０２は、ハードディスク装置９０８に記憶されている所定の制御プログラムを読み出して実行することにより、後述する各種の制御処理を行えるようになる。
【０１４４】
入力装置９１０は、例えばマウス装置やキーボード装置であり、情報処理装置のユーザにより操作されると、その操作内容に対応付けられている各種情報の入力を取得し、取得した入力情報をＣＰＵ９０２に送付する。
【０１４５】
表示装置９１２は例えば液晶ディスプレイであり、ＣＰＵ９０２から送付される表示データに応じて各種のテキストや画像を表示する。
【０１４６】
インターフェース装置９１４は、このコンピュータ９００に接続される各種機器との間での各種情報の授受の管理を行う。
【０１４７】
記録媒体駆動装置９１６は、可搬型記録媒体９２０に記録されている各種の制御プログラムやデータの読み出しを行う装置である。ＣＰＵ９０２は、可搬型記録媒体９２０に記録されている所定の制御プログラムを、記録媒体駆動装置９１６を介して読み出して実行することによって、後述する各種の制御処理を行うようにすることもできる。なお、可搬型記録媒体９２０としては、例えばＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）規格のコネクタが備えられているフラッシュメモリ、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ−ＲＯＭ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などがある。
【０１４８】
このようなコンピュータ９００を用いて通信ノードを構成するには、例えば、上述の各処理部における処理をＣＰＵ９０２に行わせるための制御プログラム（分散データ処理プログラム）を作成する。作成された制御プログラムはハードディスク装置９０８若しくは可搬型記録媒体９２０に予め格納しておく。そして、ＣＰＵ９０２に所定の指示を与えてこの制御プログラム（通信制御プログラム）を読み出させて実行させる。こうすることで、通信ノードが備えている機能がＣＰＵ９０２により提供される。
【０１４９】
＜＜送信元ノードではない通信ノードにおける処理＞＞
図１８〜１９を参照して、たとえば、図９に示されている通信ノード３００が、図１０に示されているパケット４００を受信する場合に行う処理について説明する。
【０１５０】
図１８〜１９は、自身が送信元ノードではない通信ノードにおける処理の流れの例を示す図である。
【０１５１】
図１８〜１９において、鍵共有要求を送信する通信ノードは通信ノード（ｕ、ｖ）であり、鍵共有要求を送信する通信ノードは通信ノード（ｘ、ｙ）とする。すなわち、パケット４００において、パケット４００の送信元ＩＤ４１０のフィールドには、通信ノード（ｕ、ｖ）に対応するインデックスが、宛先ＩＤ４０８のフィールドには、通信ノード（ｘ、ｙ）に対応するインデックスが格納される。また、通信ノード（ｕ、ｖ）は、事前共有鍵Ｋｕ、Ｌｖを、通信ノード（ｉ、ｊ）は、事前共有鍵Ｋｉ、Ｌｊを有しているとする。
【０１５２】
また、通信ノードが図１７に示されているような汎用コンピュータ９００である場合には、下記の説明は、そのような処理を行う制御プログラム（通信制御プログラム）を定義する。すなわち、以下では、下記に説明する処理を汎用コンピュータに行わせる制御プログラム（通信制御プログラム）の説明でもある。
【０１５３】
処理が開始されるとＳ４０２で通信ノード３００の通信部３０４は、記憶部３０８に記憶されているフラグｆをリセットする。たとえば、ｆ＝０とする。本ステップの処理が終了すると、処理はＳ４０４に進む。
【０１５４】
Ｓ４０４で通信ノード３００の通信部３０４は、パケット４００を受信したかどうかを判定する。もし、この判定の結果が“ｙｅｓ”、すなわちパケット４００を受信した場合、処理はＳ４０６に進む。もし、この判定の結果が“ｎｏ”、すなわちパケット４００を受信していない場合、処理はＳ４０２に戻る。
【０１５５】
Ｓ４０６で通信ノード３００の通信部３０４は、パケット４００の宛先ＩＤ４０８のフィールドの値が自身の通信ノードのインデックス（ＩＤ）と一致しているかどうかを判定する。もし、この判定の結果が“ｙｅｓ”、すなわちパケット４００の宛先ＩＤ４０８のフィールドの値が自身の通信ノードのインデックス（ＩＤ）と一致している場合、処理はＳ４０８に進む。もし、この判定の結果が“ｎｏ”、すなわちパケット４００の宛先ＩＤ４０８のフィールドの値が自身の通信ノードのインデックス（ＩＤ）と一致していない場合、処理はＳ４２６に進む。
【０１５６】
Ｓ４０８で通信ノード３００の通信部３０４は、フラグｆの値が０か否かを判定する。もし、この判定の結果が“ｙｅｓ”、すなわちフラグｆの値が０の場合、処理はＳ４１０に進む。もし、この判定の結果が“ｎｏ”、すなわちフラグｆの値が０でない場合、処理はＳ４１８に進む。
【０１５７】
Ｓ４１０で通信ノード３００の通信部３０４は、パケット４００の中継ＩＤ２（４１６）のフィールドが空か否かを判定する。つまり、パケット４００の中継ＩＤ２（４１６）のフィールドに何らかの通信ノードのインデックスが格納されているか否かを判定する。もし、この判定の結果が“ｎｏ”、すなわちパケット４００の中継ＩＤ２（４１６）のフィールドが空でない場合、処理はＳ４１２に進む。もし、この判定の結果が“ｙｅｓ”、すなわちパケット４００の中継ＩＤ２（４１６）のフィールドが空である場合、処理はＳ４１４に進む。
【０１５８】
Ｓ４１２で通信ノード３００の通信部３０４は、フラグｆをｆ＝１に設定し、中継ＩＤ２（４１６）の値をダミー変数（ａ１、ｂ１）に格納する。本ステップの処理が終了すると、処理はＳ４１６に進む。
【０１５９】
Ｓ４１４で通信ノード３００の通信部３０４は、フラグｆをｆ＝１に設定し、中継ＩＤ１（４１４）の値をダミー変数（ａ１、ｂ１）に格納する。本ステップの処理が終了すると、処理はＳ４１６に進む。
【０１６０】
Ｓ４１６で通信ノード３００の通信部３０４は、インデックスＩＤ（ａ１、ｂ１）と対応付けて暗号化された分散共有鍵Ｅ（ＭＫ１）を記憶部３０８に記憶する。
【０１６１】
Ｓ４１８で通信ノード３００の判定部３０２は、ダミー変数（ａ１、ｂ１）中のａ１の値がｕであるか否かを判定する。ここで通信ノード３００は、インデックスＩＤ（ｕ、ｖ）を有する。もし、この判定の結果が“ｙｅｓ”、すなわちダミー変数（ａ１、ｂ１）中のａ１の値がｕである場合、処理はＳ４２０に進む。もし、この判定の結果が“ｎｏ”、すなわちダミー変数（ａ１、ｂ１）中のａ１の値がｕでない場合、処理はＳ４２２に進む。
【０１６２】
Ｓ４２０で通信ノード３００の演算部３１０は、暗号化された分散共有鍵Ｅ（ＭＫ１）を事前共有鍵Ｋｕで復号し、暗号化された分散共有鍵Ｅ（ＭＫ２）事前共有鍵Ｌｖで復号し、鍵ＭＫ＝ＭＫ１＋ＭＫ２を復元する。本ステップの処理が終了すると、処理はＳ４２４に進む。
【０１６３】
Ｓ４２２で通信ノード３００の演算部３１０は、暗号化された分散共有鍵Ｅ（ＭＫ１）を事前共有鍵Ｌｖで復号し、暗号化された分散共有鍵Ｅ（ＭＫ２）を事前共有鍵Ｋｕで復号し、鍵ＭＫ＝ＭＫ１＋ＭＫ２を復元する。本ステップの処理が終了すると、処理はＳ４２４に進む。
【０１６４】
Ｓ４２４で通信ノード３００の演算部３１０は、パケット４００中の鍵送信元ＩＤ４１０の値と対応付けて鍵ＭＫを記憶部３０８に記憶する。本ステップの処理が終了すると、処理はＳ４０２に戻る。
【０１６５】
Ｓ４２６で通信ノード３００の通信部３０４は、パケット４００の中継ＩＤ１（４１４）または中継ＩＤ２（４１６）の値が自身の通信ノードのインデックス（ＩＤ）と一致しているかどうかを判定する。もし、この判定の結果が“ｙｅｓ”、すなわちパケット４００の中継ＩＤ１（４１４）または中継ＩＤ２（４１６）の値が自身の通信ノードのインデックス（ＩＤ）と一致している場合、処理はＳ４２８に進む。もし、この判定の結果が“ｎｏ”、すなわちパケット４００の中継ＩＤ１（４１４）または中継ＩＤ２（４１６）の値が自身の通信ノードのインデックス（ＩＤ）と一致していない場合、処理はＳ４０２に戻る。
【０１６６】
Ｓ４２８で通信ノード３００の通信部３０４は、パケット４００の送信元ＩＤ４１２の値をダミー変数（ａ、ｂ）に格納する。本ステップの処理が終了すると、処理はＳ４３０に進む。
【０１６７】
Ｓ４３０で通信ノード３００の判定部３０２は、自身のインデックスＩＤ（ｉ、ｊ）中のｉの値がａであるか否かを判定する。もし、この判定の結果が“ｙｅｓ”、すなわちｉの値がａである場合、処理はＳ４３２に進む。もし、この判定の結果が“ｎｏ”、すなわちｉの値がａではない場合、処理はＳ４３４に進む。
【０１６８】
Ｓ４３２で通信ノード３００の演算部３１０は、暗号化された分散共有鍵をＫｉで復号し、自身が有している事前共有鍵Ｌｊで再度暗号化する。本ステップの処理が終了すると、処理はＳ４３６に進む。
【０１６９】
Ｓ４３２で通信ノード３００の演算部３１０は、暗号化された分散共有鍵をＬｊで復号し、自身が有している事前共有鍵Ｋｉで再度暗号化する。本ステップの処理が終了すると、処理はＳ４３６に進む。
【０１７０】
Ｓ４３６で通信ノード３００の通信部３０４は、自身がパケット４００の中継ＩＤ１（４１４）であり、かつ、パケット４００の中継ＩＤ２（４１６）のフィールドが空であるか否かを判定する。この判定の結果が“ｙｅｓ”、すなわち自身がパケット４００の中継ＩＤ１（４１４）であり、かつ、パケット４００の中継ＩＤ２（４１６）のフィールドが空である場合、処理はＳ４４０に進む。もし、この判定の結果が“ｎｏ”、すなわち自身がパケット４００の中継ＩＤ１（４１４）であり、かつ、パケット４００の中継ＩＤ２（４１６）のフィールドが空でない場合、処理はＳ４３８に進む。
【０１７１】
Ｓ４３８で通信ノード３００の送信先決定部３０６は、送信パケットに、前ノードアドレス、送信元ＩＤに自身のものを、宛先アドレスに中継ＩＤ２に対応するものを設定する。送信パケットの他のフィールドは受信パケットと同様のものを設定する。さらに、Ｓ４３８で通信ノード３００の通信部３０４は、送信パケットを送信する。
【０１７２】
Ｓ４４０で通信ノード３００の送信先決定部３０６は、送信パケットに、前ノードアドレス、送信元ＩＤに自身のものを、宛先アドレスに宛先ＩＤに対応するものを設定する。送信パケットの他のフィールドは受信パケットと同様のものを設定する。さらに、Ｓ４４０で通信ノード３００の通信部３０４は、送信パケットを送信する。
【０１７３】
Ｓ４３８またはＳ４４０のステップの処理が終了すると、処理はＳ４０２に戻る。
【０１７４】
＜＜送信元ノードの通信ノードにおける処理＞＞
図２０を参照して、送信元ノードの通信ノードにおける処理について説明する。
【０１７５】
図２０は、自身が送信元ノードである通信ノードにおける処理の流れの例を示す図である。
【０１７６】
図２０において、鍵共有要求を送信する通信ノードは通信ノード（ｕ、ｖ）であり、鍵共有要求を送信する通信ノードは通信ノード（ｘ、ｙ）とする。また、図２０において、通信ノード数はｍ×ｎであり、仮想的なマトリクスは、ｍ行ｎ列であるとする。
【０１７７】
また、通信ノードが図１７に示されているような汎用コンピュータ９００である場合には、下記の説明は、そのような処理を行う制御プログラム（通信制御プログラム）を定義する。すなわち、以下では、下記に説明する処理を汎用コンピュータに行わせる制御プログラム（通信制御プログラム）の説明でもある。
【０１７８】
処理が開始されるとＳ５０２で、通信ノード３００の鍵生成部３１２は、鍵ＭＫを生成し、分散鍵（分散共有鍵）ＭＫ１とＭＫ２に分散する。本ステップの処理が終了すると、処理はＳ５０４に進む。
【０１７９】
Ｓ５０４で通信ノード３００の送付先決定部３０６は、ｕとｘが等しい、すなわちｕ＝ｘか否かを判定する。もし、この判定の結果が“ｙｅｓ”、すなわちｕとｘが等しい場合、処理はＳ５０６に進む。もし、この判定の結果が“ｎｏ”、すなわちｕとｘが等しくない場合、処理はＳ５０８に進む。
【０１８０】
Ｓ５０６で通信ノード３００の送付先決定部３０６は、０から（ｎ−１）の中でランダムに１つの整数を選び、ｓとする。本ステップの処理が終了すると、処理はＳ５０８に進む。
【０１８１】
Ｓ５０８で通信ノード３００の演算部３１０は、分散鍵の一つＭＫ１を事前共有鍵Ｌｖを用いて暗号化する。暗号化された分散鍵はＥＬｖ（ＭＫ１）と表すこともある。本ステップの処理が終了すると、処理はＳ５１０に進む。
【０１８２】
Ｓ５１０で通信ノード３００の送信先決定部３０６は、送信パケットを生成する。ここで、送信パケットの送付先アドレス４０２には、通信ノード（ｓ、ｖ）のアドレス（インデックス）が格納される。前ノードアドレス４０４には、自身のアドレス（インデックス）が格納される。宛先ＩＤ４０８にはＩＤ（ｘ、ｙ）、鍵送信元ＩＤ４１０にはＩＤ（ｕ、ｖ）、送信元ＩＤ４１２にはＩＤ（ｕ、ｖ）が格納される。また、中継ＩＤ１（４１４）にはＩＤ（ｓ、ｖ）が、中継ＩＤ２（４１６）にはＩＤ（ｓ、ｙ）が格納される。暗号化分散鍵４１８にはＥＬｖ（ＭＫ１）が格納される。本ステップの処理が終了すると、処理はＳ５１２に進む。
【０１８３】
Ｓ５１２で通信ノード３００の演算部３１０は、分散鍵の別の一つＭＫ２を事前共有鍵Ｋｕを用いて暗号化する。暗号化された分散鍵はＥＫｕ（ＭＫ２）と表すこともある。本ステップの処理が終了すると、処理はＳ５１４に進む。
【０１８４】
Ｓ５１４で通信ノード３００の送信先決定部３０６は、送信パケットを生成する。ここで、送信パケットの送付先アドレス４０２には、通信ノード（ｘ、ｙ）のアドレス（インデックス）が格納される。前ノードアドレス４０４には、自身のアドレス（インデックス）が格納される。宛先ＩＤ４０８にはＩＤ（ｘ、ｙ）、鍵送信元ＩＤ４１０にはＩＤ（ｕ、ｖ）、送信元ＩＤ４１２にはＩＤ（ｕ、ｖ）が格納される。また、中継ＩＤ１（４１４）と中継ＩＤ２（４１６）には空を表す０を格納する。暗号化分散鍵４１８にはＥＫｕ（ＭＫ２）が格納される。本ステップの処理が終了すると、処理は終了する。
【０１８５】
Ｓ５１６で通信ノード３００の送付先決定部３０６は、ｖとｙが等しい、すなわちｖ＝ｙか否かを判定する。もし、この判定の結果が“ｙｅｓ”、すなわちｖとｙが等しい場合、処理はＳ５１８に進む。もし、この判定の結果が“ｎｏ”、すなわちｖとｙが等しくない場合、処理はＳ５２８に進む。
【０１８６】
Ｓ５１８で通信ノード３００の送付先決定部３０６は、０から（ｍ−１）の中でランダムに１つの整数を選び、ｔとする。本ステップの処理が終了すると、処理はＳ５２０に進む。
【０１８７】
Ｓ５２０で通信ノード３００の演算部３１０は、分散鍵の一つＭＫ２を事前共有鍵Ｋｕを用いて暗号化する。暗号化された分散鍵はＥＫｕ（ＭＫ２）と表すこともある。本ステップの処理が終了すると、処理はＳ５２２に進む。
【０１８８】
Ｓ５１０で通信ノード３００の送信先決定部３０６は、送信パケットを生成する。ここで、送信パケットの送付先アドレス４０２には、通信ノード（ｕ、ｔ）のアドレス（インデックス）が格納される。前ノードアドレス４０４には、自身のアドレス（インデックス）が格納される。宛先ＩＤ４０８にはＩＤ（ｘ、ｙ）、鍵送信元ＩＤ４１０にはＩＤ（ｕ、ｖ）、送信元ＩＤ４１２にはＩＤ（ｕ、ｖ）が格納される。また、中継ＩＤ１（４１４）にはＩＤ（ｕ、ｔ）が、中継ＩＤ２（４１６）にはＩＤ（ｘ、ｔ）が格納される。暗号化分散鍵４１８にはＥＫｕ（ＭＫ２）が格納される。本ステップの処理が終了すると、処理はＳ５２４に進む。
【０１８９】
Ｓ５２４で通信ノード３００の演算部３１０は、分散鍵の別の一つＭＫ１を事前共有鍵Ｌｖを用いて暗号化する。暗号化された分散鍵はＥＬｖ（ＭＫ１）と表すこともある。本ステップの処理が終了すると、処理はＳ５２６に進む。
【０１９０】
Ｓ５２６で通信ノード３００の送信先決定部３０６は、送信パケットを生成する。ここで、送信パケットの送付先アドレス４０２には、通信ノード（ｘ、ｙ）のアドレス（インデックス）が格納される。前ノードアドレス４０４には、自身のアドレス（インデックス）が格納される。宛先ＩＤ４０８にはＩＤ（ｘ、ｙ）、鍵送信元ＩＤ４１０にはＩＤ（ｕ、ｖ）、送信元ＩＤ４１２にはＩＤ（ｕ、ｖ）が格納される。また、中継ＩＤ１（４１４）と中継ＩＤ２（４１６）には空を表す０が格納される。暗号化分散鍵４１８にはＥＬｖ（ＭＫ１）が格納される。本ステップの処理が終了すると、処理は終了する。
【０１９１】
Ｓ５２８で通信ノード３００の演算部３１０は、分散鍵の一つＭＫ１を事前共有鍵Ｌｖを用いて暗号化する。暗号化された分散鍵はＥＬｖ（ＭＫ１）と表すこともある。本ステップの処理が終了すると、処理はＳ５３０に進む。
【０１９２】
Ｓ５３０で通信ノード３００の送信先決定部３０６は、送信パケットを生成する。ここで、送信パケットの送付先アドレス４０２には、通信ノード（ｘ、ｙ）のアドレス（インデックス）が格納される。前ノードアドレス４０４には、自身のアドレス（インデックス）が格納される。宛先ＩＤ４０８にはＩＤ（ｘ、ｙ）、鍵送信元ＩＤ４１０にはＩＤ（ｕ、ｖ）、送信元ＩＤ４１２にはＩＤ（ｕ、ｖ）が格納される。また、中継ＩＤ１（４１４）にはＩＤ（ｘ、ｖ）が、中継ＩＤ２（４１６）には空を表す０が格納される。暗号化分散鍵４１８にはＥＬｖ（ＭＫ１）が格納される。本ステップの処理が終了すると、処理はＳ５３２に進む。
【０１９３】
Ｓ５３２で通信ノード３００の演算部３１０は、分散鍵の別の一つのＭＫ２を事前共有鍵Ｋｕを用いて暗号化する。暗号化された分散鍵はＥＫｕ（ＭＫ２）と表すこともある。本ステップの処理が終了すると、処理はＳ５１４に進む。
【０１９４】
Ｓ５１４で通信ノード３００の送信先決定部３０６は、送信パケットを生成する。ここで、送信パケットの送付先アドレス４０２には、通信ノード（ｘ、ｙ）のアドレス（インデックス）が格納される。前ノードアドレス４０４には、自身のアドレス（インデックス）が格納される。宛先ＩＤ４０８にはＩＤ（ｘ、ｙ）、鍵送信元ＩＤ４１０にはＩＤ（ｕ、ｖ）、送信元ＩＤ４１２にはＩＤ（ｕ、ｖ）が格納される。また、中継ＩＤ１（４１４）にはＩＤ（ｕ、ｙ）が、中継ＩＤ２（４１６）には空を表す０が格納される。暗号化分散鍵４１８にはＥＫｕ（ＭＫ２）が格納される。本ステップの処理が終了すると、処理は終了する。
【０１９５】
このような処理を採用することによって、確定的に全ノード間で鍵を共有でき、事前に保有する共有鍵は２個であるというメリットを保ったまま、鍵漏洩時の影響を小さくすることができる。
【０１９６】
以上のように、ネットワーク中の送信元の通信ノードは、共有鍵ＭＫを分散共有鍵ＭＫ１とＭＫ２に分散し、それぞれ別のノードを介して宛先の通信ノードに送信する。それによって、ある通信ノードが解析されて、その通信ノードの事前共有鍵が漏洩しても、共有鍵ＭＫを復元することはできない。したがって、アドホックネットワークにおいて、確定的に全ノード間で鍵を共有でき、事前に保有する共有鍵は２個であるというメリットを保ったまま、一つのノードの事前共有鍵が漏洩した場合でも、共通鍵暗号の鍵が完全に復元されることを避けることができる。
【０１９７】
以上において、仮想的なマトリクス空間は２次元空間であったが、次元が２より大きな空間であっても良い。
【０１９８】
また、上記第１および第２の実施例では、仮想的なマトリクス空間において、同じ行、同じ列に配置される通信ノードは、同一の事前共有鍵を有するので、ネットワークに新たな通信ノードを加えるときの処理の負荷が軽いという効果も奏する。
【符号の説明】
【０１９９】
１０      アドホックネットワーク
１００、１０２、１０４、１０６、３００    通信ノード
１１０    サーバ
１２０    シンクノード
２００    鍵管理部
２０２、２０４、２０６    鍵
３０２  判定部
３０４  通信部
３０４２  送信部
３０４４  受信部
３０６  送付先決定部
３０８  記憶部
３１０  演算部
３１０２  分散鍵演算部
３１０４  共有鍵復元部
３１２  鍵生成部
【図１】
2016005113.tif 000003
【図４】
2016005113.tif 000004
【図６】
2016005113.tif 000005
【図９】
2016005113.tif 000006
【図１０】
2016005113.tif 000007
【図１２】
2016005113.tif 000008
【図１４】
2016005113.tif 000009
【図１６】
2016005113.tif 000010
【図１７】
2016005113.tif 000011
【図１８】
2016005113.tif 000012
【図１９】
2016005113.tif 000013
【図２０】
2016005113.tif 000014
【図２】
2016005113.tif 000015
【図３】
2016005113.tif 000016
【図５】
2016005113.tif 000017
【図７】
2016005113.tif 000018
【図８】
2016005113.tif 000019
【図１１】
2016005113.tif 000020
【図１３】
2016005113.tif 000021
【図１５】
2016005113.tif 000022