(57)【特許請求の範囲】
【請求項１】
無線暗号通信が可能な複数のノードが所定の散布対象エリア内に散布された際に、散布されたノード間での無線暗号通信を可能とする鍵を各ノードに格納する鍵格納装置であって、
散布対象エリアを所定数のサブエリアに分割するエリア分割部と、
前記エリア分割部による分割後の各サブエリアにサブエリアごとに異なる鍵を割り当てる鍵割当部と、
ノードごとに、散布対象エリア内に散布された際のノードの配置点をノード散布の確率密度関数を用いて予測し、予測配置点から所定の範囲内にあるサブエリアの中からいずれかのサブエリアを選択し、選択したサブエリアに割り当てられている鍵を格納対象の鍵として指定する配置サンプリング部と、
前記配置サンプリング部により指定された鍵を対象のノードに対して書き込む鍵書き込み部とを有し、
前記配置サンプリング部は、
一つのノードに対して所定の複数個の鍵が指定されるまで、一つのノードについて、配置点の予測、予測配置点から所定の範囲内にある特定のサブエリアの選択、及び選択したサブエリアに割り当てられている鍵の指定を繰り返し、
前記鍵書き込み部は、
前記配置サンプリング部により指定された所定の複数個の鍵を対象のノードに対して書き込むことを特徴とする鍵格納装置。
【請求項２】
前記配置サンプリング部は、
予測配置点から当該ノードが無線通信可能な範囲内にあるサブエリアの中からいずれかのサブエリアを選択することを特徴とする請求項１に記載の鍵格納装置。
【請求項３】
前記配置サンプリング部は、
一つのノードに対して所定の複数個の鍵が指定されるまで、一つのノードについて、配置点の予測を複数回繰り返し、配置点の予測の繰り返しにより得られる複数個の予測配置点の各々に対して、予測配置点から所定の範囲内にある特定のサブエリアの選択、及び選択したサブエリアに割り当てられている鍵の指定を行うことを特徴とする請求項１に記載の鍵格納装置。
【請求項４】
前記配置サンプリング部は、
ノードごとに、異なる確率密度関数を用いてノードの配置点を予測可能であることを特徴とする請求項１に記載の鍵格納装置。
【請求項５】
前記鍵割当部は、
前記エリア分割部による分割後の各サブエリアにサブエリアごとに異なる複数の鍵を割り当て、
前記配置サンプリング部は、
選択したサブエリアに割り当てられている複数の鍵の中からいずれかの鍵を選択し、選択した鍵を格納対象の鍵として指定することを特徴とする請求項１に記載の鍵格納装置。
【請求項６】
前記鍵格納装置は、移動体に搭載されて移動可能であり、更に、
鍵格納装置の現在位置の情報を取得する位置取得部と、
鍵格納装置の移動速度の情報を取得する速度取得部と、
前記鍵書き込み部により鍵が書き込まれた後のノードの散布を行うノード散布部と、
前記位置取得部により取得された現在位置の情報と前記速度取得部により取得された移動速度の情報を用いて、所定のタイミングにおける鍵格納装置の位置及び速度ベクトルを計算し、前記所定のタイミングにおいてノード散布が行われる場合の確率密度関数を推定する確率密度関数推定部を有し、
前記配置サンプリング部は、
前記所定のタイミングにおいて散布を行うべき散布対象ノードを特定するとともに、前記確率密度関数推定部により推定された確率密度関数を用いて、散布対象ノードが散布対象エリア内に散布された際の散布対象ノードの配置点を予測し、予測配置点から所定の範囲内にあるサブエリアの中からいずれかのサブエリアを選択し、選択したサブエリアに割り当てられている鍵を散布対象ノードに格納する鍵として指定し、
前記鍵書き込み部は、
前記配置サンプリング部により指定された鍵を散布対象ノードに書き込み、
前記ノード散布部は、
前記所定のタイミングにおいて、前記鍵書き込み部により鍵が書き込まれた後の散布対象ノードの散布を行うことを特徴とする請求項１に記載の鍵格納装置。
【請求項７】
前記配置サンプリング部は、
散布対象ノードに対して所定の複数個の鍵が指定されるまで、散布対象ノードについて、配置点の予測、予測配置点から所定の範囲内にあるいずれかのサブエリアの選択、及び選択したサブエリアに割り当てられている鍵の指定を繰り返し、
前記鍵書き込み部は、
前記配置サンプリング部により指定された所定の複数個の鍵を散布対象ノードに対して書き込むことを特徴とする請求項６に記載の鍵格納装置。
【請求項８】
無線暗号通信が可能な複数のノードが所定の散布対象エリア内に散布された際に、散布されたノード間での無線暗号通信を可能とする鍵を各ノードに格納する鍵格納方法であって、
散布対象エリアを所定数のサブエリアに分割するエリア分割ステップと、
前記エリア分割ステップによる分割後の各サブエリアにサブエリアごとに異なる鍵を割り当てる鍵割当ステップと、
ノードごとに、散布対象エリア内に散布された際のノードの配置点をノード散布の確率密度関数を用いて予測し、予測配置点から所定の範囲内にあるサブエリアの中からいずれかのサブエリアを選択し、選択したサブエリアに割り当てられている鍵を格納対象の鍵として指定する配置サンプリングステップと、
前記配置サンプリングステップにより指定された鍵を対象のノードに対して書き込む鍵書き込みステップとを有し、
前記配置サンプリングステップでは、
一つのノードに対して所定の複数個の鍵が指定されるまで、一つのノードについて、配置点の予測、予測配置点から所定の範囲内にある特定のサブエリアの選択、及び選択したサブエリアに割り当てられている鍵の指定が繰り返され、
前記鍵書き込みステップでは、
前記配置サンプリングステップにより指定された所定の複数個の鍵を対象のノードに対して書き込む処理が行われることを特徴とする鍵格納方法。
【請求項９】
無線暗号通信が可能な複数のノードが所定の散布対象エリア内に散布された際に、散布されたノード間での無線暗号通信を可能とする鍵の各ノードへの格納をコンピュータに実行させるプログラムであって、
散布対象エリアを所定数のサブエリアに分割するエリア分割処理と、
前記エリア分割処理による分割後の各サブエリアにサブエリアごとに異なる鍵を割り当てる鍵割当処理と、
ノードごとに、散布対象エリア内に散布された際のノードの配置点をノード散布の確率密度関数を用いて予測し、予測配置点から所定の範囲内にあるサブエリアの中からいずれかのサブエリアを選択し、選択したサブエリアに割り当てられている鍵を格納対象の鍵として指定する配置サンプリング処理と、
前記配置サンプリング処理により指定された鍵を対象のノードに対して書き込む鍵書き込み処理とをコンピュータに実行させ、
前記配置サンプリング処理では、
前記コンピュータに、一つのノードに対して所定の複数個の鍵が指定されるまで、一つのノードについて、配置点の予測、予測配置点から所定の範囲内にある特定のサブエリアの選択、及び選択したサブエリアに割り当てられている鍵の指定を繰り返させ、
前記鍵書き込み処理では、
前記コンピュータに、前記配置サンプリング処理により指定された所定の複数個の鍵を対象のノードに対して書き込む処理を行わせることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、散布されるセンサノードを用いて、温度の測定、ガス漏れの検出、生存者の発見等、環境情報の収集や、災害時の救出支援を行うシステムにおいて、設置箇所が事前に正確に定まらない複数のセンサノードへの、安全な通信のための初期鍵の格納技術に関する。
【背景技術】
【０００２】
大量のセンサノード（以下、単にノードと記す）から構成されるセンサネットワークにおいて、ノード間通信の安全性確保が課題となっている。このために、事前にノードに格納された暗号化鍵（以下、単に鍵と記す）を用いた暗号通信が利用される。【０００３】
図１５は、大量のノードをある区域に散布し、ノード同士でネットワークを形成してセンシング情報を収集するシステムのイメージ図である。【０００４】
図１５において、ノード作成１０１では各ノードに鍵を格納し、ノード散布１０２では散布対象となるエリアに各ノードを散布し、ネットワーク形成１０３ではノード同士が無線暗号通信によるネットワークを形成してセンシング情報の収集を行っている。【０００５】
ネットワーク形成１０３において、無線通信が可能な範囲にある２つのノード間で暗号通信を行うためには、あらかじめ共通の鍵が２つのノードに格納されている必要がある。しかし、本システムのようにノードの散布を行う場合、散布による配置には誤差が伴うため、どのノード対が無線通信可能範囲に入るかが事前に確定しない。従って、ノード散布１０２の結果ノードがどのように配置されたとしても、ネットワーク形成１０３が可能となるような、ノード作成１０１の方法が課題となる。【０００６】
ノード作成１０１における鍵格納の単純な方法の１つとして、全ノードに共通の鍵を格納する方法があるが、この方法には１つのノードが盗まれて鍵が漏洩すると、システムの安全性が全て失われるという問題がある。また別の方法として、各ノードに、他の全てのノードとの共通鍵を個別に格納する方法があるが、この方法では各ノードに、ノード総数に比例した記憶領域が必要となるため、リソースの制限されたセンサネットワークでの実現が困難という問題があり、加えてノードの追加が困難という問題もある。【０００７】
これらの問題点に対処する技術として、非特許文献１では、大量の鍵プールからランダムに選択した複数の鍵を各ノードに格納し、任意のノード間で確率的な鍵確立を可能とさせることにより、省リソース性と、ノードの盗難による鍵漏洩への耐性を両立させる方式が記載されている。また、上記方式の改良として非特許文献２に記載の方式があり、初期鍵格納の際に、ノードのおおよその配置情報を利用することで、省リソース性・鍵漏洩への耐性を高めている。【０００８】
図１６は、非特許文献２に記載の方式で用いる初期鍵格納装置の構成例を表すブロック図である。鍵プール記憶領域２１２は、ノードに格納されうる全ての鍵をあらかじめ格納するデータ記憶手段である。また、エリア鍵プール記憶領域２１４は、各エリアと、全体鍵集合（鍵プール記憶領域２１２に格納されている鍵の集合）の部分集合との対応づけを格納するデータ記憶手段である。図１７は鍵プール記憶領域２１２が記憶するデータの一例、図１８はエリア鍵プール記憶領域２１４が記憶するデータの一例である。図１９は、上記を用いて行う初期鍵格納処理を説明するためのフローチャートである。【０００９】
上記方式は、エリア鍵プール決定（ステップＳ５１３）において、あらかじめ分割されたノード散布エリアごとに鍵集合（エリア鍵プール）を定め、鍵格納フェーズ（ステップＳ５０２）では散布エリアに対応したエリア鍵プールから鍵選択を行う。近傍エリア間では共通の鍵が高い確率で含まれるように工夫する事により、同一エリア内や近接エリアに散布されるノード間での鍵確立を高確率で可能とすることが特徴である。【００１０】
また、ノード間のセキュリティ通信に関する技術として、特開２００４−２４８１６７号公報に開示の技術がある。
【特許文献１】特開２００４−２４８１６７号公報
【非特許文献１】Ｅｓｃｈｅｎａｕｅｒ  ａｎｄ  Ｖ．  Ｄ．  Ｇｌｉｇｏｒ，  ”Ａ  Ｋｅｙ−Ｍａｎａｇｅｍｅｎｔ  Ｓｃｈｅｍｅ  ｆｏｒ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ，”  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ９ｔｈ  ＡＣＭ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｓｅｃｕｒｉｔｙ，  Ｗａｓｈｉｎｇｔｏｎ，  ＤＣ，  ＵＳＡ，  Ｎｏｖｅｍｂｅｒ  １８−２２  ２００２，  ｐｐ．  ４１−４７．
【非特許文献２】Ｗ．  Ｄｕ，  Ｊ．  Ｄｅｎｇ，  Ｙ．  Ｓ．  Ｈａｎ，  Ｓ．  Ｃｈｅｎ  ａｎｄ  Ｐ．  Ｋ．  Ｖａｒｓｈｎｅｙ，  ”Ａ  Ｋｅｙ  Ｍａｎａｇｅｍｅｎｔ  Ｓｃｈｅｍｅ  ｆｏｒ  Ｗｉｒｅｌｅｓｓ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ  Ｕｓｉｎｇ  Ｄｅｐｌｏｙｍｅｎｔ  Ｋｎｏｗｌｅｄｇｅ，”  ｔｈｅ  ＩＥＥＥ  ＩＮＦＯＣＯＭ  ２００４，  Ｈｏｎｇ  Ｋｏｎｇ，  Ｍａｒｃｈ  ２００４．
【発明の開示】
【発明が解決しようとする課題】
【００１１】
ノードの配置情報を利用した初期鍵格納に関して、非特許文献２に記載の方式では、ノード散布１０２において散布点が規則的に並んでいる（ノード間の間隔が固定的である）ことを前提としている。このため、散布点が不規則な場合や、複数の散布方法を併用する場合には、従来の方式では不規則な散布点又は複数の散布方法に柔軟に対応することができず、近傍のノードとの通信に必要な鍵がノードに格納されない事態が生じ、ネットワーク形成１０３の効率が低下するという問題点があった。本発明は、例えば、上記のような問題点を解決するためになされたもので、散布点が不規則な場合や複数の散布方法を併用する場合においても、ネットワーク形成１０３を高い確率で、少ないメモリで、安全に実現することを主な目的とする。
【課題を解決するための手段】
【００１２】
本発明に係る鍵格納装置は、
無線暗号通信が可能な複数のノードが所定の散布対象エリア内に散布された際に、散布されたノード間での無線暗号通信を可能とする鍵を各ノードに格納する鍵格納装置であって、
散布対象エリアを所定数のサブエリアに分割するエリア分割部と、
前記エリア分割部による分割後の各サブエリアにサブエリアごとに異なる鍵を割り当てる鍵割当部と、
ノードごとに、散布対象エリア内に散布された際のノードの配置点をノード散布の確率密度関数を用いて予測し、予測配置点から所定の範囲内にあるサブエリアの中からいずれかのサブエリアを選択し、選択したサブエリアに割り当てられている鍵を格納対象の鍵として指定する配置サンプリング部と、
前記配置サンプリング部により指定された鍵を対象のノードに対して書き込む鍵書き込み部とを有することを特徴とする。【００１３】
前記配置サンプリング部は、
予測配置点から当該ノードが無線通信可能な範囲内にあるサブエリアの中からいずれかのサブエリアを選択することを特徴とする。【００１４】
前記配置サンプリング部は、
一つのノードに対して所定の複数個の鍵が指定されるまで、一つのノードについて、配置点の予測、予測配置点から所定の範囲内にある特定のサブエリアの選択、及び選択したサブエリアに割り当てられている鍵の指定を繰り返し、
前記鍵書き込み部は、
前記配置サンプリング部により指定された所定の複数個の鍵を対象のノードに対して書き込むことを特徴とする。【００１５】
前記配置サンプリング部は、
ノードごとに、異なる確率密度関数を用いてノードの配置点を予測可能であることを特徴とする。【００１６】
前記鍵割当部は、
前記エリア分割部による分割後の各サブエリアにサブエリアごとに異なる複数の鍵を割り当て、
前記配置サンプリング部は、
選択したサブエリアに割り当てられている複数の鍵の中からいずれかの鍵を選択し、選択した鍵を格納対象の鍵として指定することを特徴とする。【００１７】
前記鍵格納装置は、移動体に搭載されて移動可能であり、更に、
鍵格納装置の現在位置の情報を取得する位置取得部と、
鍵格納装置の移動速度の情報を取得する速度取得部と、
前記鍵書き込み部により鍵が書き込まれた後のノードの散布を行うノード散布部と、
前記位置取得部により取得された現在位置の情報と前記速度取得部により取得された移動速度の情報を用いて、所定のタイミングにおける鍵格納装置の位置及び速度ベクトルを計算し、前記所定のタイミングにおいてノード散布が行われる場合の確率密度関数を推定する確率密度関数推定部を有し、
前記配置サンプリング部は、
前記所定のタイミングにおいて散布を行うべき散布対象ノードを特定するとともに、前記確率密度関数推定部により推定された確率密度関数を用いて、散布対象ノードが散布対象エリア内に散布された際の散布対象ノードの配置点を予測し、予測配置点から所定の範囲内にあるサブエリアの中からいずれかのサブエリアを選択し、選択したサブエリアに割り当てられている鍵を散布対象ノードに格納する鍵として指定し、
前記鍵書き込み部は、
前記配置サンプリング部により指定された鍵を散布対象ノードに書き込み、
前記ノード散布部は、
前記所定のタイミングにおいて、前記鍵書き込み部により鍵が書き込まれた後の散布対象ノードの散布を行うことを特徴とする。【００１８】
前記配置サンプリング部は、
散布対象ノードに対して所定の複数個の鍵が指定されるまで、散布対象ノードについて、配置点の予測、予測配置点から所定の範囲内にあるいずれかのサブエリアの選択、及び選択したサブエリアに割り当てられている鍵の指定を繰り返し、
前記鍵書き込み部は、
前記配置サンプリング部により指定された所定の複数個の鍵を散布対象ノードに対して書き込むことを特徴とする。【００１９】
本発明に係る鍵格納方法は、無線暗号通信が可能な複数のノードが所定の散布対象エリア内に散布された際に、散布されたノード間での無線暗号通信を可能とする鍵を各ノードに格納する鍵格納方法であって、
散布対象エリアを所定数のサブエリアに分割するエリア分割ステップと、
前記エリア分割ステップによる分割後の各サブエリアにサブエリアごとに異なる鍵を割り当てる鍵割当ステップと、
ノードごとに、散布対象エリア内に散布された際のノードの配置点をノード散布の確率密度関数を用いて予測し、予測配置点から所定の範囲内にあるサブエリアの中からいずれかのサブエリアを選択し、選択したサブエリアに割り当てられている鍵を格納対象の鍵として指定する配置サンプリングステップと、
前記配置サンプリングステップにより指定された鍵を対象のノードに対して書き込む鍵書き込みステップとを有することを特徴とする。【００２０】
本発明に係るプログラムは、無線暗号通信が可能な複数のノードが所定の散布対象エリア内に散布された際に、散布されたノード間での無線暗号通信を可能とする鍵の各ノードへの格納をコンピュータに実行させるプログラムであって、
散布対象エリアを所定数のサブエリアに分割するエリア分割処理と、
前記エリア分割処理による分割後の各サブエリアにサブエリアごとに異なる鍵を割り当てる鍵割当処理と、
ノードごとに、散布対象エリア内に散布された際のノードの配置点をノード散布の確率密度関数を用いて予測し、予測配置点から所定の範囲内にあるサブエリアの中からいずれかのサブエリアを選択し、選択したサブエリアに割り当てられている鍵を格納対象の鍵として指定する配置サンプリング処理と、
前記配置サンプリング処理により指定された鍵を対象のノードに対して書き込む鍵書き込み処理とをコンピュータに実行させることを特徴とする。
【発明の効果】
【００２１】
本発明によれば、ノード配置が不規則な場合や複数の散布方法を併用する場合でも、確率密度関数に基づいて各ノードの配置点を正確に予測することができ、予測した配置点に基づいて各ノードに必要な鍵を指定し格納することができ、これによりネットワーク形成を高い確率で、少ないメモリで、安全に実現することができる。
【発明を実施するための最良の形態】
【００２２】
実施の形態１．
まず、最初に、本実施の形態の内容を概説する。【００２３】
本実施の形態では、ノードの散布対象となるエリアの地表を細かい領域に分割し、計算機上で各領域に鍵を割り当てる。次に、散布後のノード配置を、事前に特定された確率分布（確率密度関数）から予測し、予測された位置から所定距離内の位置に割り当てられている鍵をノードに格納する。上記の処理を必要な鍵数分繰り返し、１つのノードへの鍵格納が完了する。そして、同様の処理を各ノードに対して行い、全体の処理を完了する。【００２４】
本実施の形態の主な特徴は、ノードに格納する鍵を、ノードが散布されると予測される位置と、その位置に計算機上で事前に割り当てられた鍵から特定するところにある。これにより、互いに近くに配置されることが予測される２ノードが安全な通信を行える確率が高まり、ネットワーク形成１０３を効率化することができる。以下に本実施の形態に係る初期鍵格納装置の詳細を説明する。【００２５】
図１は、大量のノードをある区域に散布し、ノード同士でネットワークを形成してセンシング情報を収集するシステム（図１５）において、ノードに鍵を格納する初期鍵格納装置（鍵格納装置）の構成例を表すブロック図である。【００２６】
図１において、エリア分割部６１１はノード散布対象空間（ノード散布対象エリア）をいくつかの小空間（サブエリア）に分割する手段であり、パーソナルコンピュータなどの情報処理装置で実現できる。鍵生成部（鍵割当部）６１２は共通鍵暗号の鍵を生成するとともに、生成した鍵をノード散布対象空間の小空間と対応づける手段であり、パーソナルコンピュータなどの情報処理装置で実現できる。鍵プール記憶領域６１３は鍵生成部６１２を用いて生成された鍵を、鍵ＩＤと関連付けて記憶するデータ記憶手段である。図３は鍵プール記憶領域６１３が記憶するデータの一例を表す。【００２７】
配置サンプリング部６１４は配置の確率密度関数に基づいてノードの配置点のサンプリングを行う手段であり、パーソナルコンピュータなどの情報処理装置で実現できる。配置サンプリング部６１４が存在することが本実施の形態の特徴の一つであり、これによって、ノードの配置点を予測できることになり、ノード散布１０２において任意の散布方法が利用可能となる。【００２８】
鍵書き込み部６１５は配置サンプリング部６１４の出力に対応する鍵を鍵プール記憶領域６１３から読み出し、センサノード７０１の鍵記憶領域７１３に格納する手段である。【００２９】
図２は、本実施の形態で用いるセンサノードの構成例を表すブロック図である。【００３０】
図２において、通信部７１１は他のノードと無線通信を行う手段である。暗号部７１２は共通鍵暗号の暗号化や復号などを行う手段である。鍵記憶領域７１３は初期鍵格納装置６０１の鍵書き込み部６１５から与えられた鍵を、鍵ＩＤと関連付けて記憶するデータ記憶手段である。【００３１】
図４は鍵記憶領域７１３が記憶するデータの一例を表す。センサ部７１４は通信対象のデータを収集する手段である。【００３２】
図５は、本実施の形態における初期鍵格納処理を説明するためのフローチャートである。【００３３】
図１２は、ノード同士の鍵確立処理を説明するためのフローチャートである。【００３４】
次に動作について、図５のフローチャートを参照しながら説明する。【００３５】
まず初期鍵格納装置６０１の初期化フェーズを実行する（ステップＳ１００１）。初期化フェーズでの入力は鍵総数（ｎ）、ノード散布対象空間（Ａ）、ノードに格納する鍵数（ｍ）、ノードの通信可能距離（ｒ）である（ステップＳ１０１１）。本例ではＡを二次元空間とするが、Ａが三次元空間の場合でも容易に適用できる。【００３６】
エリア分割部６１１は、ノード散布対象空間Ａを、同じ面積のｎ個の小空間（Ａ１〜Ａｎ）に分割する（エリア分割ステップ）（ステップＳ１０１２）。図６はエリア分割の結果を表すイメージ図である。本例では小空間として正方形を用いることを想定しているが、ノード散布対象空間Ａを敷き詰められるものであり、円になるべく近い形をしているものであれば正方形である必要はない。例えば、長方形、正六角形などでもよい。【００３７】
鍵生成部６１２はｎ個の鍵を生成し、鍵ＩＤ（１〜ｎ）と暗号化鍵（Ｋ１〜Ｋｎ）を組にして鍵プール記憶領域６１３に格納する（鍵割当ステップ）（ステップＳ１０１３）。ここで生成された鍵Ｋ１〜Ｋｎは、ステップＳ１０１２において分割された小空間Ａ１〜Ａｎのそれぞれに対応するものである。すなわち、各小空間Ａｉに各鍵Ｋｉが割り当てられることになる。図７は、各小空間に各鍵が割り当てられたことを表すイメージ図である。【００３８】
以上の初期化フェーズ終了後、各センサノード７０１への鍵格納フェーズを実行する（ステップＳ１００２）。鍵格納フェーズでの入力は、当該ノード（Ｎｊ）の配置の確率密度関数（Ｐｒ（ｘ，  ｙ））である（ステップＳ１０２１）。特に、分布を二次元正規分布と仮定する場合には、入力として平均（分布の中心位置＝散布点）、標準偏差、相関係数を用いても良い。また、全てのノードについて標準偏差および相関係数が一定である場合には、平均（散布点）のみを入力とすれば良い。【００３９】
一方、従来方式における鍵格納フェーズ（ステップＳ５０２）の入力はノード散布対象エリアであり（ステップＳ５２１）、同一エリアに散布するノードはすべて同一条件のもとで鍵格納が行われる。本実施の形態ではノードごとに条件（確率密度関数）を変えることが可能であるため、任意の散布方法に対応可能であるという特徴を持つ。【００４０】
配置サンプリング部６１４は、確率密度関数Ｐｒ（ｘ，  ｙ）に基づき、ノード散布対象空間Ａの内部におけるノード配置点Ｐを一点選び、さらにＰを中心とする半径ｒの円内（Ｐからの通信が可能な領域に相当）からランダムに一点Ｑを選び、Ｑが属する小空間Ａｉを決定する（配置サンプリングステップ）（ステップＳ１０２２）。図８は点Ｐの、図９は点Ｑの選択に関するイメージ図である。図８および図９の大円はノードが散布される領域を示し、Ｐは、確率密度関数に基づいてサンプリングされた、あるノードの予測配置である。図９の小円はＰからの通信が可能な領域を示し、Ｑは、小円からランダムに選択された点である。そして、配置サンプリング部は、図９の例では、Ｐの地点に配置されると予測されるノードに対して、小空間Ａ２８に対応する鍵Ｋ２８を書き込み対象として指定する。【００４１】
鍵書き込み部６１５は、配置サンプリングの指定に従い、小空間Ａｉに対応する暗号化鍵Ｋｉを鍵プール記憶領域６１３から読み出し、鍵ＩＤ（ｉ）と暗号化鍵（Ｋｉ）を当該ノードＮｊの鍵記憶領域７１３に格納する（鍵書き込みステップ）（ステップＳ１０２３）。なお、鍵が重複した場合は配置のサンプリングからやり直す（ステップＳ１０２４）。上記の配置サンプリングおよび鍵格納（ステップＳ１０２２〜Ｓ１０２４）を、当該ノードＮｊの鍵記憶領域７１３にｍ個の鍵が格納されるまで繰り返し（ステップＳ１０２５）、１つのノードへの鍵格納が終了する。【００４２】
以上の鍵格納をノードの数だけ個別に繰り返し（ステップＳ１０２６）、全ノードへの鍵格納が完了したところで鍵格納フェーズを終了する。【００４３】
図１０および図１１は、ある２つのノード（ノードＮ１およびノードＮ２とする）への鍵格納について説明するためのイメージ図である。図１０および図１１において、左の円はノードＮ１が配置されると予測される領域、右の円はノードＮ２が配置されると予測される領域を表す。また、図７に見られるように、空間と鍵が対応づけられているため、各円は各ノードに格納されうる鍵の集合に対応すると考えられる。図１０は、２ノードが互いに近くに配置されることが予測されるような例である。この場合、鍵の集合の共通部分が大きくなるため、２ノードが共通の鍵を持ち、安全な通信が可能となる確率が高くなる。一方、図１１は、２ノードが遠くに配置されることが予測されるような例である。この場合、鍵の集合の共通部分が小さくなるため、２ノードが共通の鍵を持つ確率は低くなってしまうが、そもそもこれらのノードが互いに通信可能な範囲に入る確率が低いため、共通の鍵を持つ必要性は低いと言える。
また、小空間の決定にＰではなくＱを用いることによって、「同一の場所に配置される確率は０であるが、通信可能範囲内に配置される確率を持つ２ノード」が共通の鍵を保持する確率を高くすることができる。【００４４】
以上のように、鍵格納フェーズにおいて、入力として任意の確率密度関数を用いることができるため、散布点が不規則な場合でも本実施の形態をそのまま適用することが可能である。加えて、近くに配置されると予測されるノード対が高確率で共通の鍵を持つため、ネットワーク形成１０３を効率的に行うことが可能となる。【００４５】
ノードが確率密度関数にしたがって散布された後、通信可能な範囲にある２ノード（鍵確立要求ノードおよび近傍ノードとする）が安全な通信を試みるための手順を、図１２のフローチャートを参照しながら説明する。鍵確立要求ノードは通信部７１１を用い、相互に共有している鍵が存在するかを確認するために、鍵記憶領域７１３に格納されている鍵ＩＤのリストを近傍ノードに対してブロードキャストする（ステップＳ１７１１）。これを近傍ノードが通信部７１１で受信し（ステップＳ１７１２）、自身の鍵記憶領域７１３の鍵ＩＤに同じものが含まれているかを確認する（ステップＳ１７１３）。同じ鍵Ｋｉを保持していることを確認した近傍ノードは、その鍵ＩＤであるｉを応答として送信する（ステップＳ１７１４〜Ｓ１７１５）。以降は暗号部７１２と鍵Ｋｉを用いた暗号通信を行う。以上のように、鍵ＩＤの送受信のみで鍵確立が行われるため、以降の通信の安全性が確保される。【００４６】
なお、本実施の形態では、ステップＳ１０１２において、ノード散布対象空間をｎ個の小空間に分割し、各小空間に１個の鍵を対応づけているが、ノード散布対象空間の分割数を減らし、各小空間に複数個の鍵を対応づけた形態で実施することも可能である。この場合、ステップＳ１０２２において小空間を決定した後に、対応づけられた複数個の鍵の中から１個をランダムに選ぶことになる。【００４７】
また、本実施の形態では、ステップＳ１０１３において、鍵生成部６１２を用いてｎ個の鍵を生成しているが、このかわりに、専用の鍵生成装置などを利用してｎ個の鍵をあらかじめ生成しておき、フレキシブルディスクなどを介して、ｎ個の鍵をステップＳ１０１１における入力とすることも可能である。【００４８】
また、本実施の形態では、ステップＳ１０２２において、Ｐを中心とする半径ｒの円内からランダムに一点Ｑを選んでいるが、この半径をｒ以外の適当な値（例えば、ｒ／２や２ｒ）とすることも可能である。半径を小さくする程、互いに近くに配置されることが予測される２ノードが共通の鍵を保持する確率が高くなるが、遠くに配置されることが予測される２ノードが共通の鍵を保持する確率は低くなる。【００４９】
また、本実施の形態では、ステップＳ１０２２において、Ｐを中心とする半径ｒの円内からランダムに一点Ｑを選んでいるが、円内のかわりに円周上からランダムに一点を選んでも良い。【００５０】
また、本実施の形態では、ステップＳ１０２２において、Ｐを中心とする半径ｒの円内からランダムに一点Ｑを選んでいるが、円に限らず、通信可能領域を示すあらゆる条件を指定することが可能である。【００５１】
また、本実施の形態では、ステップＳ１０２４において、鍵が重複した場合は配置のサンプリングからやり直しているが、このかわりに、近隣の小空間に対応する（未格納の）鍵を格納することにしても良い。【００５２】
実施の形態２．
図１３は、大量のノードをある区域に散布し、ノード同士でネットワークを形成してセンシング情報を収集するシステムにおいて、ノードへの鍵の格納およびノード散布の両方の機能を持つ初期鍵格納・ノード散布装置１８０１の構成例を表すブロック図である。なお、本実施の形態に係る初期鍵格納・ノード散布装置１８０１は、ヘリコプターなどの移動体に搭載されて移動可能であり、移動とともにノードの散布を行うことができる。【００５３】
図１３において、エリア分割部６１１、鍵生成部６１２、鍵プール記憶領域６１３、配置サンプリング部６１４、鍵書き込み部６１５に関しては、実施の形態１で示したものと同一であるので、説明は省略する。【００５４】
位置取得部１８１１は初期鍵格納・ノード散布装置１８０１の空間上の位置の情報を取得する手段であり、ＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）などの測位システムを用いて実現できる。速度取得部１８１２は初期鍵格納・ノード散布装置１８０１の速度ベクトル情報を取得する手段であり、ＧＰＳや速度センサなどを用いて実現できる。【００５５】
確率密度関数推定部１８１３は、位置取得部１８１１、速度取得部１８１２の出力に基づいて、散布時のノード配置の確率密度関数を推定する手段であり、パーソナルコンピュータなどの情報処理装置で実現できる。ノード散布部１８１４は鍵格納が完了したノードを発射する手段である。【００５６】
図１４は、本実施の形態における初期鍵格納およびノード散布処理を説明するためのフローチャートである。【００５７】
次に動作について、図１４のフローチャートを参照しながら説明する。【００５８】
まず初期鍵格納・ノード散布装置１８０１の初期化フェーズを実行する（ステップＳ１００１）。初期化フェーズに関しては、実施の形態１で示したものと同一であるので、説
明は省略する。【００５９】
初期化フェーズ終了後、各センサノード７０１について、鍵格納・ノード散布フェーズを実行する（ステップＳ１９０１）。【００６０】
位置取得部１８１１および速度取得部１８１２は、現時点における初期鍵格納・ノード散布装置１８０１の位置および速度ベクトルを取得する（ステップＳ１９１１）。【００６１】
次に、確率密度関数推定部１８１３は、現時点の位置および速度ベクトルを用いてｔ秒後の位置および速度ベクトルを計算し、ｔ秒後におけるノード散布の確率密度関数Ｐｒ（ｘ，ｙ）を推定する（ステップＳ１９１２）。なお、ｔは配置サンプリング（ステップＳ１９１３）と鍵格納（ステップＳ１９１４）の処理速度などを考慮して事前に決定される値である。【００６２】
次に、配置サンプリング部６１４が、確率密度関数推定部１８１３が推定した確率密度関数を用いて配置サンプリングを行い、更に、鍵書き込み部６１５が配置サンプリング部の指定に従って鍵格納（ステップＳ１９１３〜Ｓ１９１６）を行う。これらに関しては、実施の形態１で示したものと同一であるので、説明は省略する。【００６３】
その後、位置・速度取得（ステップＳ１９１１）からｔ秒後に、ノード散布部１８１４はノードの散布を行い（ステップＳ１９１７）、１つのノードの散布が終了する。【００６４】
以上の鍵格納・ノード散布をノードの数だけ個別に繰り返し（ステップＳ１９１８）、全ての鍵格納・ノード散布が完了したところで鍵格納・ノード散布フェーズを終了する。【００６５】
以上のように、鍵格納・ノード散布フェーズにおいて、取得した位置・速度に基づいてリアルタイムに格納する鍵を決定するため、あらかじめ散布点を決めておく必要がなく、例えばヘリコプターで空中からノード散布をする場合に、位置の調整が不要となり、散布コストを削減することが可能となる。【００６６】
なお、実施の形態１で記述したバリエーションは、本実施の形態においても同様に適用することが可能である。【００６７】
また、本実施の形態では、ステップＳ１９１７において、１ノードへの鍵格納が完了するごとにノード散布を行っているが、複数ノードへの鍵格納の完了ごとにノード散布を行うことも可能である。【００６８】
また、以上では、初期鍵格納・ノード散布装置１８０１の位置及び速度に基づいて確率密度関数を推定することとしているが、他の要素、例えば、風速、風向き、温度、湿度、散布対象エリアの地形（傾斜など）といった周囲の状態を示す指標を用いて確率密度関数を推定するようにしてもよい。【００６９】
前述した各実施の形態で、初期鍵格納装置６０１及び初期鍵格納・ノード散布装置１８０１は、コンピュータで実現できるものである。【００７０】
例えば、図２０に示すように、初期鍵格納装置６０１及び初期鍵格納・ノード散布装置１８０１は、プログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１３７を備えている。【００７１】
例えば、ＣＰＵ１３７は、バス１３８を介して、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１３９、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１４０、通信ボード１４４、ＣＲＴ表示装置、Ｋ／Ｂ（キーボード）１４２、マウス１４３、ＦＤＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）１４５、ＣＤＤ（コンパクトディスクドライブ）１８６、磁気ディスク装置１４６、光ディスク装置、プリンタ装置１８７、スキャナ装置１８８等と接続可能である。【００７２】
ＲＡＭは、揮発性メモリの一例である。ＲＯＭ、ＦＤＤ、ＣＤＤ、磁気ディスク装置、光ディスク装置は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部の一例である。【００７３】
前述した各実施の形態の初期鍵格納装置６０１及び初期鍵格納・ノード散布装置１８０１が扱うデータや情報は、記憶装置あるいは記憶部に保存され、初期鍵格納装置６０１及び初期鍵格納・ノード散布装置１８０１の各部により、記録され読み出されるものである。【００７４】
また、通信ボードは、例えば、ＬＡＮ、インターネット、或いはＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）に接続されている。【００７５】
磁気ディスク装置には、オペレーティングシステム（ＯＳ）、ウィンドウシステム、プログラム群、ファイル群（データベース）が記憶されている。【００７６】
プログラム群は、ＣＰＵ、ＯＳ、ウィンドウシステムにより実行される。【００７７】
上記初期鍵格納装置６０１及び初期鍵格納・ノード散布装置１８０１の各部は、一部或いはすべてコンピュータで動作可能なプログラムにより構成しても構わない。或いは、ＲＯＭに記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェア或いは、ハードウェア或いは、ソフトウェアとハードウェアとファームウェアとの組み合わせで実施されても構わない。【００７８】
上記プログラム群には、実施の形態の説明において「〜部」として説明した処理をＣＰＵに実行させるプログラムが記憶される。これらのプログラムは、例えば、Ｃ言語やＪａｖａ（登録商標）言語などのコンピュータ言語により作成される。【００７９】
また、上記プログラムは、磁気ディスク装置、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）、光ディスク、ＣＤ（コンパクトディスク）、ＭＤ（ミニディスク）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のその他の記録媒体に記憶され、ＣＰＵにより読み出され実行される。
【図面の簡単な説明】
【００８０】
【図１】実施の形態１に係る初期鍵格納装置の構成例を示す図。
【図２】実施の形態１に係るセンサノードの構成例を示す図。
【図３】実施の形態１に係る初期鍵格納装置の鍵プール記憶領域の例を示す図。
【図４】実施の形態１に係る初期鍵格納装置の鍵記憶領域の例を示す図。
【図５】実施の形態１に係る初期鍵格納装置の処理例を示すフローチャート図。
【図６】実施の形態１に係る初期鍵格納装置におけるエリア分割の結果を表すイメージ図。
【図７】実施の形態１に係る初期鍵格納装置における鍵の割当結果を表すイメージ図。
【図８】実施の形態１に係る初期鍵格納装置における配置サンプリングの例を説明する図。
【図９】実施の形態１に係る初期鍵格納装置における配置サンプリングの例を説明する図。
【図１０】ノードの配置点と鍵格納との関係を説明する図。
【図１１】ノードの配置点と鍵格納との関係を説明する図。
【図１２】実施の形態１に係るセンサノードの処理例を示すフローチャート図。
【図１３】実施の形態２に係る初期鍵格納・ノード散布装置の構成例を示す図。
【図１４】実施の形態２に係る初期鍵格納・ノード散布装置の処理例を示すフローチャート図。
【図１５】ノード作成、ノード散布、ネットワーク形成の手順を示す図。
【図１６】従来の初期鍵格納装置の構成例を示す図。
【図１７】従来の初期鍵格納装置の鍵プール記憶領域の例を示す図。
【図１８】従来の初期鍵格納装置のエリア鍵プール記憶領域の例を示す図。
【図１９】従来の初期鍵格納装置の処理例を示すフローチャート図。
【図２０】初期鍵格納装置及び初期鍵格納・ノード散布装置のハードウェア構成例を示す図。
【符号の説明】
【００８１】
６０１  初期鍵格納装置、６１１  エリア分割部、６１２  鍵生成部、６１３  鍵プール記憶領域、６１４  配置サンプリング部、６１５  鍵書き込み部、７０１  センサノード、７１１  通信部、７１２  暗号部、７１３  鍵記憶領域、７１４  センサ部、１８０１  初期鍵格納・ノード散布装置、１８１１  位置取得部、１８１２  速度取得部、１８１３  確率密度関数推定部、１８１４  ノード散布部。
【図１】
0004768637.tif 000002
【図２】
0004768637.tif 000003
【図３】
0004768637.tif 000004
【図４】
0004768637.tif 000005
【図５】
0004768637.tif 000006
【図６】
0004768637.tif 000007
【図７】
0004768637.tif 000008
【図８】
0004768637.tif 000009
【図９】
0004768637.tif 000010
【図１０】
0004768637.tif 000011
【図１１】
0004768637.tif 000012
【図１２】
0004768637.tif 000013
【図１３】
0004768637.tif 000014
【図１４】
0004768637.tif 000015
【図１５】
0004768637.tif 000016
【図１６】
0004768637.tif 000017
【図１７】
0004768637.tif 000018
【図１８】
0004768637.tif 000019
【図１９】
0004768637.tif 000020
【図２０】
0004768637.tif 000021