(57)【要約】  患者を監視する無線ネットワーク（２、１５０）は、患者に動作可能に結合され、患者の健康状態に関する情報を収集して無線ネットワーク（２、１５０）に伝達する１つ以上の無線センサ（６、８、１０、１２、１４、１６、１８、２０、１５６、１５８、１６０、１６２、１６４、１６６、１６８、１７０）を有する人体センサネットワーク（２２、２４、２６、１７２、１７４、１７６）を有する。設定サーバ（４、１５４）は、１つ以上のセンサ（６、８、１０、１２、１４、１６、１８、２０、１５６、１５８、１６０、１６２、１６４、１６６、１６８、１７０）が無線ネットワーク（２、１５０）に配置される前に、鍵情報で１つ以上の無線センサ（６、８、１０、１２、１４、１６、１８、２０、１５６、１５８、１６０、１６２、１６４、１６６、１６８、１７０）を構成する。基地局（１７８、１８０）は、人体センサネットワーク（２２、２４、２６、１７２、１７４、１７６）に関連する１つ以上のセンサ（６、８、１０、１２、１４、１６、１８、２０、１５６、１５８、１６０、１６２、１６４、１６６、１６８、１７０）に鍵証明書を配布し、これにより、２つのセンサは、事前配布鍵情報と、基地局（１７８、１８０）により配布された鍵証明書とに少なくとも部分的に基づいて、固有の鍵ペアを生成する。
2008543245.tif 000002
【特許請求の範囲】
【請求項１】
患者を監視する無線ネットワークであって：
前記患者に動作可能に結合され、前記患者の健康状態に関する情報を収集して前記無線ネットワークに伝達する１つ以上の無線センサを有する人体センサネットワークと；
前記１つ以上のセンサが前記無線ネットワークに配置される前に、鍵情報で前記１つ以上の無線センサを構成する設定サーバと；
前記人体センサネットワークに関連する前記１つ以上のセンサに鍵証明書を配布し、これにより、２つのセンサは、事前配布鍵情報と、基地局により配布された前記鍵証明書とに少なくとも部分的に基づいて、固有の鍵ペアを生成する基地局と；
を有する無線ネットワーク。
【請求項２】
前記設定サーバは、Ｆｑ’でｔ×（ｎ２＋ｎ＋１）のλ次２変数多項式
（外１）
2008543245.tif 000020
の集合
（外２）
2008543245.tif 000021
をランダムに生成し、
前記設定サーバは、
（外３）
2008543245.tif 000022
からｔの多項式を順に選択し、ｎ２＋ｎ＋１のｔ多項式集合Ｆｊ（ｘ，ｙ）を形成し、
ただし、λは前記無線ネットワークのノードの数であり、１より大きい整数であり、ｎはプライム出力であり、ｔは１以上の整数であり、Ｆｑ’は有限フィールドであり、ｑ’は暗号化鍵を提供するのに十分に大きい素数である、請求項１に記載のシステム。
【請求項３】
前記設定サーバは、集合Ｓに属する要素で有限射影平面（ｎ２＋ｎ＋１）を生成し、
ただし、｜Ｓ｜＝ｎ２＋ｎ＋１であり、前記集合Ｓは、Ｓの各要素が前記ｔ多項式集合Ｆｊ（ｘ，ｙ）の別個のものに関連するように関連付けられ、ｎはプライム出力である、請求項２に記載のシステム。
【請求項４】
各センサノードは、前記設定サーバからｎ＋１のｔ多項式集合の割り当てＦｂｉ．ｊ（ｐｕ，ｊ，ｙ）を受信し、
ただし、ｐｕ，ｊ∈Ｆｑ’であり、ｂｉ，ｊ∈Ｂｉ∈有限射影平面であり、ｊ＝１．．．ｎ＋１であり、ｎはプライム出力である、請求項３に記載のシステム。
【請求項５】
有限射影平面の第１のブロックＢ１は、要素｛ｂ１，１，．．．ｂ１，ｎ＋１｝を有し、
前記センサノードは、Ｆｑ’のポイントｐａで評価されたｔ多項式集合の割り当てＦｂ１，１（ｐａ，ｙ）〜Ｆｂ１，ｎ＋１（ｐａ，ｙ）を受信し、
ただし、ａは１とＮ’／（ｎ＋１）との間であり、Ｎは異なる無線ネットワークで潜在的に見つかる相互運用可能なノードのグループのサイズであり、１以上の整数であり、ｎはプライム出力である、請求項４に記載のシステム。
【請求項６】
有限射影平面の第２のブロックＢ２は、要素｛ｂ２，１，．．．ｂ２，ｎ＋１｝を有し、ｂ１，１＝ｂ２，１であり、
センサノードｕ１＋Ｎ’／（ｎ＋１）は、ポイントｐ１＋Ｎ’／（ｎ＋１）で評価されたｔ多項式集合の割り当てＦｂ１，１（ｐ１＋Ｎ’／（ｎ＋１），ｙ）を受信し、ポイントｐ１で評価されたｔ多項式集合の割り当てＦｂ２，２（ｐ１，ｙ）〜Ｆｂ２，ｎ＋１（ｐ１，ｙ）を受信し、
ただし、Ｎは異なる無線ネットワークで潜在的に見つかる相互運用可能なノードのグループのサイズであり、１以上の整数であり、ｎはプライム出力である、請求項５に記載のシステム。
【請求項７】
前記センサノードは、ＩＤを交換し、
前記ＩＤは、前記ＩＤにより伝達される前記ｎ＋１のｔ多項式集合の割り当てのインデックスと、前記それぞれのｎ＋１のｔ多項式集合の割り当てが評価されるポイントｐｕ１．．．ｐｕｎ＋１、ｐｖ１．．．ｐｖｎ＋１をそれぞれ有し、
ただし、ｎは１以上の整数である、請求項６に記載のシステム。
【請求項８】
各センサノードは、共通のｔ多項式集合Ｆｋ（ｘ，ｙ）に対応するインデックスｋと各評価ポイントｐｕ及びｐｖを見つける、請求項７に記載のシステム。
【請求項９】
ノードｕは、ｉ＝１．．．ｔについて、ポイントｐｖで前記ｔのλ次２変数多項式ｆｋｉ（ｐｕ，ｙ）（すなわち、ｆｊｉ（ｐｕ，ｐｖ））を評価し、ｔの部分鍵を取得し、前記ｔの部分鍵をｌｏｇｑ’ビットに切り捨て、ｔの鍵セグメントを連結し、ｌｏｇｑビットの最終的な鍵ペアＫｕｖを形成し、
ただし、ｔは正の整数である、請求項８に記載のシステム。
【請求項１０】
鍵証明書を配布することは：
１つ以上の無線センサを初期化し；
前記基地局と前記１つ以上の無線センサとに鍵ペアを配布し；
鍵要素の連鎖を生成し；
前記鍵連鎖の最初の要素を前記１つ以上の無線センサに配布し；
有効な鍵証明書を発行し、ある期間に鍵を有効にし、前記期間の間にセキュリティサーバに連絡し；
前記期間の間に人体センサネットワークに連絡し；
前記１つ以上の無線センサのそれぞれと安全な通信を認証して確立し；
それぞれ認証されたセンサノードに鍵証明書を配布し；
前記１つ以上の無線センサの間で鍵ペアを確立する；
ことを有する、請求項１に記載のシステム。
【請求項１１】
前記設定サーバは、固有の識別子とセキュリティ情報とで前記１つ以上の無線センサを初期化し、前記基地局と前記１つ以上の無線センサとについて鍵ペアをランダムに選択して配布し、
前記基地局は、限られた期間に事前配布鍵を有効にする鍵証明書を損傷されていないノードに発行する、請求項１に記載のシステム。
【請求項１２】
前記基地局は、時間間隔Ｉｌ−１の間に、１つ以上の他の基地局と散発的に相互接続し、時間間隔Ｉｌ＋１に対応する鍵証明書について合意し、
ただし、ｌは正の整数であり、
時間間隔Ｉｌの後に、各基地局は、前記鍵証明書を忘れ、鍵は前記１つ以上の無線センサの間で確立される、請求項１１に記載のシステム。
【請求項１３】
前記１つ以上の無線センサは、固有の識別子とセキュリティ情報とで初期化され、前記１つ以上の無線センサに対して鍵ペアをランダムに選択して配布し、
秘密Ｓを生成し、閾値方式に従って前記秘密ＳからＭの割り当てＳ１，Ｓ２，．．．，ＳＭを生成し、前記基地局と前記ネットワークの１つ以上の他の基地局とに前記秘密Ｓを安全に配布し、
ただし、Ｍは正の整数である、請求項１に記載のシステム。
【請求項１４】
時間間隔Ｉｌ−１の間に、前記１つ以上の基地局は、散発的に安全に相互接続し、小規模の相互接続されていないグループＧｇ（Ｇ１，Ｇ２．．．ｇ＜Ｍｉ）を形成し、
各基地局は、少なくとも１つのグループＧｇに接続し、
ただし、ｇ及びｌは正の整数であり、
各グループメンバは、ＫＣｇｌ＋１＝Ｆ（Ｓ，ＮＧｇｌ）を計算することにより、間隔Ｉｌ＋１に鍵証明書を独立して計算し、
ただし、ＮＧｇｌは間隔Ｉｌ＋１にグループＧｇに排他的なナンスであり、
各グループメンバはＳを忘れる、請求項１３に記載のシステム。
【請求項１５】
時間間隔Ｉｌの間に、少なくとも１つの基地局は：
前記人体センサネットワークに散発的に短く連絡し、
少なくとも１つの鍵を使用して、それぞれ損傷していない無線センサと安全な通信を認証して確立し、前記人体センサの一部を形成し、
前記時間間隔Ｉｌ＋１に前記鍵証明書ＫＣｌ＋１をそれぞれ認証されたセンサノードに配布し、前記１つ以上の無線センサの間で鍵を確立する、請求項１４に記載のシステム。
【請求項１６】
１つ以上の無線ノードを有するネットワークと；
前記１つ以上のノードが無線ネットワークに配置される前に、鍵情報で前記１つ以上の無線ノードを構成する設定サーバと；
前記ネットワークに関連する前記１つ以上のノードに鍵証明書を配布し、これにより、２つのノードは、事前配布鍵情報と、基地局により配布された鍵証明書とに少なくとも部分的に基づいて、固有の鍵ペアを生成する基地局と；
を有する無線ネットワーク。
【請求項１７】
移動センサシステムで第１のセンサを特定する方法であって：
オーダｎのｎ−１の直交ラテン方陣の集合から有限射影平面（ｎ２＋ｎ＋１，ｎ＋１，１）を構築し、但し、ｎはプライム出力であり；
前記有限射影平面から共通のｔ多項式集合の割り当てを発見し；
前記第１のセンサの識別子から第２のセンサによりｔ多項式集合の割り当ての評価ポイントを導く；
ことを有する方法。
【請求項１８】
前記直交ラテン方陣の直交関係Ｌｅｍ＝｜ｌｉｊｅｍ｜のセルのｎのエントリについて、要素ｅｍ（ｍ＝１，２，．．．ｎ）毎に直交行列の要素ｌｉｊｅｍを順に計算する、請求項１７に記載の方法。
【請求項１９】
前記有限射影平面は、第１から第ｎ行までｎ２の整数１〜ｎ２を自然の順序で配置することにより行列Ｍを構成することにより構成され、
ただし、ｎはプライム出力である、請求項１７に記載の方法。
【請求項２０】
ノードｕが鍵Ｋｕｖを生成するためのｔ多項式集合の割り当てのその割り当てＦｋ（ｐｕ，ｙ）を評価するポイントｐｖを導き；
前記有限射影平面の第１のｎ２の要素がｎの続くブロックＢ１＋ｔ，Ｂ２＋ｔ，．．．Ｂｎ＋ｔ（ｔ＝０，ｎ，２ｎ，３ｎ，．．．ｎ×ｎ）の各グループに１回現れるように、前記直交ラテン方陣から前記有限射影平面を構成し；
ブロックインデックスｉ（１≦ｉ≦ｎ２＋ｎ）と、ｔ多項式集合のインデックスｋ（ｋ≦ｎ２）とから出現回数ｓｋを導き、ｋは正の整数であり、ｎはプライム出力である；
ことを更に有する、請求項１７に記載の方法。
【請求項２１】
センサｕが有している前記ｔ多項式集合の割り当てＦｂｉ，１（ｕ，ｙ），Ｆｂｉ，２（ｕ，ｙ）．．．Ｆｂｉ，ｎ＋１（ｕ，ｙ）のインデックスは、Ｂｉ∈ＦＰＰの要素｛ｂｉ，１，ｂｉ，２，．．．ｂｉ，ｎ＋１｝と一対一のマッピングであり、
ただし、１≦ｉ≦ｎ２＋ｎ＋１であり、ｎはプライム出力である、請求項１８に記載の方法。
【請求項２２】
オーダｎのアフィン平面ＡＧ（２，ｎ）は、前記直交ラテン方陣から生成され、
前記直交ラテン方陣において、
（ｉ）第１のｎのブロックＢｉは、前記行列Ｍの行であり、
（ｉｉ）第２のｎのブロックは、前記行列Ｍの列であり、
（ｉｉｉ）残りのｎ２−ｎのブロックは、Ｍに前記行列Ｌｅｍのそれぞれを順に重ね合わせ、前記行列Ｌｅｍのそれぞれの単一の要素ｌｅｍに対応する前記行列Ｍの要素を前記ブロックとして取り入れることにより形成され、
ただし、ｎはプライム出力である、請求項１９に記載の方法。
【請求項２３】
無線システムの拡張性、弾力性及び性能を最大化する方法であって：
前記無線システムでノードに関連するｔ多項式集合の割り当てを評価し；
前記無線システムで前記評価されたノードにｔ多項式集合の割り当てを配布し；
前記無線システムで損傷しておらず通信する第１のノード及び第２のノードに対して、設定サーバを介してセキュリティ鍵を事前配布する；
ことを有する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線ネットワークに関する。本発明は、無線人体センサネットワーク内で情報の安全な通信を確立することに特に用途を見出す。しかし、本発明はまた、他の無線装置と他の無線トランスポンダとの間の安全な通信を提供することにも用途を見出す。
【背景技術】
【０００２】
移動人体センサネットワーク（ＢＳＮ：ｂｏｄｙ  ｓｅｎｓｏｒ  ｎｅｔｗｏｒｋ）が医療用途で注目されており、一般的に患者管理及び監視のために使用される。ＢＳＮは、データ収集ノードと、任意選択で制御ノードとを有する。センサノードは電池式であり、限られた計算機能及びメモリを有し、無線周波数を介した間欠的な無線通信に依存する。通常では、大量のグループ（例えば、数千）の相互運用可能なノードが病院のような医療区域に配置されており、異なる手段により、別の切断したＢＳＮを形成するように自発的に参加する。通常では、ＢＳＮは、全てのノード（例えば、医療区域の個々の患者に関連するノード）のうち小規模なサブセット（２〜５０ノード）で構成されている。事前に、ＢＳＮのサイズ及びメンバシップは未知である。ＢＳＮノードは、ＢＳＮ形成時点で存在してもよく、その後に追加及び削除されてもよい。あるノードは、ＢＳＮの形成後に限られた移動性を有するが、あるノードはかなり移動性があり、しばしば同じ区域に形成された異なる独立したＢＳＮを移動する（例えば、人間ユーザにより運ばれるデータ収集及び制御ノード、人により装着されるセンサ等）。あるノードは無人のままでもよい。ＢＳＮの存続期間は、数日、数週間、数ヶ月等に限定される。典型的には、センサノードの存続期間は、ＢＳＮインスタンスの存続期間より長い。ＢＳＮは、通信が監視可能であり、センサノードが悪質な個人による占領及び操作を受けやすい公的な区域又は敵対する区域に形成される。異なる患者に関連するＢＳＮのノード間でのクロストークは、検出データの医療上の正当性を損傷する（ｃｏｍｐｒｏｍｉｓｅ）ことがある。
【０００３】
これらの困難な動作要件は、同様にＢＳＮ設計で困難なセキュリティの制約を課す。ＢＳＮのセキュリティサービスは、認証と通信の機密性とを有する。典型的には、鍵管理サービスは、前述のセキュリティサービスを満たす基本的なセキュリティ情報を提供及び管理する。ＢＳＮセンサノードの計算上及び通信上の制約により、公開鍵暗号化に基づく何らかのセキュリティ対策を使用することは非現実的である。ＢＳＮのアドホックの性質及びＢＳＮの動作要件により、典型的なオンラインサーバ型対策も不適切になる。
【０００４】
鍵事前配布方式（ＫＰＳ：ｋｅｙ  ｐｒｅ−ｄｉｓｔｒｉｂｕｔｉｏｎ  ｓｃｈｅｍｅ）に基づく鍵管理は、ＢＳＮの１つの選択肢である。ＢＳＮメンバシップ及びサイズと独立して、固有のノード認証及び鍵確立の必要性は、ＢＳＮのＫＰＳに厳しい要件を課す。しかし、既存のＫＰＳの提案は、ＢＳＮでは限られている。第１に、ネットワーク規模の鍵事前配布は十分なセキュリティを提供しないか、ＢＳＮで管理不可能である。第２に、通常のＫＰＳはＢＳＮで拡張可能でなく、管理可能でない。第３に、ＢｌｕｎｄｏのＫＰＳ（Ｐｅｒｆｅｃｔｌｙ  Ｓｅｃｕｒｅ  Ｋｅｙ  Ｄｉｓｔｒｉｂｕｔｉｏｎ  ｆｏｒ  Ｄｙｎａｍｉｃ  Ｃｏｎｆｅｒｅｎｃｅｓ．  Ｉｎ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ’９２，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  Ｂｅｒｌｉｎ，  １９９３，  ｐｐ．４７１−４８６）の弾力性（ｒｅｓｉｌｉｅｎｃｙ）及び拡張性はセンサノードのメモリ及び計算能力により制限される。第４に、ランダムな鍵事前配布は、限られた数のノードを有するＢＳＮにとって良好な接続特性を提供しない。最後に、Ｃａｍｔｅｐｅ及びＹｅｎｅｒの組み合わせ設計理論に基づく決定論的ＫＰＳ（Ｃｏｍｂｉｎａｔｏｒｉａｌ  Ｄｅｓｉｇｎ  ｏｆ  Ｋｅｙ  Ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｍｅｃｈａｎｉｓｍｓ  ｆｏｒ  Ｗｉｒｅｌｅｓｓ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ．  Ｉｎ  Ｐｒｏｃ．  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｅｃｕｒｉｔｙ−ＥＳＯＲＩＣＳ，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ＬＮＣＳ  ３１９３，  ２００４，  ｐｐ．２９３−３０８）は、ＢＳＮについて相性の良い接続特性と適度の弾力性を有するが、固有の鍵ペアを提供しない。
【０００５】
Ｂａｓａｇｎｉ他（Ｓｅｃｕｒｅ  ｐｅｂｂｌｅｎｅｔｓ．  Ｉｎ  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  ２ｎｄ  ＡＣＭ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｍｏｂｉｌｅ  Ａｄ  Ｈｏｃ  Ｎｅｔｗｏｒｋｉｎｇ  ａｎｄ  Ｃｏｍｐｕｔｉｎｇ，  ｐｐ．１５６−１６３．  ２００１）は、全てのセンサノードにより共有されるグループ対称鍵を定期的に更新することにより、センサ通信を安全にする鍵管理方式を提示している。この方式は、不正防止センサと、分散センサネットワーク（ＤＳＮ：ｄｉｓｔｒｉｂｕｔｅｄ  ｓｅｎｓｏｒ  ｎｅｔｗｏｒｋ）規模の接続管理インフラストラクチャを仮定し、この仮定はＢＳＮに適用できない（大規模のＤＳＮは、個別の動作上及びネットワーキングの違いを有する複数のＢＳＮの相互接続としてみなすことができる。また、ＢＳＮは、大規模ＤＳＮの複数の切断した分割としてみなされる）。
【０００６】
Ｐｅｒｒｉｎｇ他（ＳＰＩＮＳ：  Ｓｅｃｕｒｉｔｙ  ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  ｓｅｎｓｏｒ  ｎｅｔｗｏｒｋｓ．  Ｉｎ  Ｐｒｏｃ．  ｏｆ  ＭＯＢＩＣＯＭ，  ２００１）は、ＳＰＩＮＳ（センサネットワーク用に特に設計されたセキュリティアーキテクチャ）を提案している。ＳＰＩＮＳでは、各センサノードは、基地局と秘密鍵を共有する。２つのセンサノードは、秘密鍵を直接確立することができない。しかし、秘密鍵を設定するために、信頼を受けた第三者として基地局を使用することができる。ＢＳＮでは、基地局は、鍵管理の時点で利用可能でないことがある。
【０００７】
Ｂｌｕｎｄｏ他は、グループ鍵を導くために多項式型ＫＰＳを提案する。２ユーザのグループでは、Ｂｌｕｎｄｏの鍵事前配布方式は、ＢＳＮで鍵ペアを確立するために使用可能である。設定サーバは、有限フィールドＦｑで対称２変数λ次多項式（ｓｙｍｍｅｔｒｉｃ  ｂｉｖａｒｉａｔｅ  λ−ｄｅｇｒｅｅ  ｐｏｌｙｎｏｍｉａｌ）
（外４）
2008543245.tif 000003
をランダムに生成する。ただし、ｑは、暗号鍵を提供するのに十分大きい素数である。対称性ｆ（ｘ，ｙ）＝ｆ（ｙ，ｘ）の特性により、設定サーバは、センサｕ毎にｆ（ｘ，ｙ）の多項式の割り当て（すなわち、ｆ（ｕ，ｙ））を計算して配布する。各センサｕは固有の識別子を有する。配置段階の後に、２つの任意のノードｕ及びｖについて、ノードｕは、ポイントｖでｆ（ｕ，ｙ）を評価することにより共通鍵Ｋｕｖ＝ｆ（ｕ，ｖ）を計算することができ、ノードｖは、ポイントｕでｆ（ｖ，ｙ）を評価することにより同じ鍵Ｋｕｖ＝ｆ（ｖ，ｕ）＝ｆ（ｕ，ｖ）を計算することができる。
【０００８】
ＢｌｕｎｄｏのＫＰＳの弾力性αは、α＝λ＋１である。すなわち、攻撃者は、損傷していないセンサの鍵ペアを生成可能になるために、αのセンサを損傷する必要がある。各センサノードｕは、λ次多項式の割り当てｆ（ｕ，ｙ）を格納する必要があり、これは（λ＋１）ｌｏｇｑの記憶空間を占有する。λはセンサで利用可能なメモリｍにより制限されることがわかる（すなわち、ｍ≧λ＋１の鍵である）。鍵ペア確立処理の間に通信オーバヘッドは存在しない。鍵ペアを確立するために、双方のセンサノードは、他のセンサノードのＩＤで多項式を評価する必要がある。これは、Ｆｑでλのモジュラ乗算とλのモジュラ加算とを必要とし、このことは、限られたＣＰＵ機能を備えたセンサでは高コストになる可能性がある。
【０００９】
Ｌｉｕ他（Ｅｓｔａｂｌｉｓｈｉｎｇ  ｐａｉｒｗｉｓｅ  ｋｅｙｓ  ｉｎ  ｄｉｓｔｒｉｂｕｔｅｄ  ｓｅｎｓｏｒ  ｎｅｔｗｏｒｋｓ．  Ｉｎ  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  １０ｔｈ  ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ  （ＣＣＳ），  ２００３，  ｐｐ．５２  −  ６１）は、除算命令のない低ビットＣＰＵにより課される制約に適合する多項式評価の変更を記載している。従ってセンサでの計算要件を低減する。これは、λ次２変数多項式の係数のビットの長さをｌｏｇｑ’に低減し、ｑ’＝２ｋ＋１の式のｑ’を選択することにより実現される。
【００１０】
Ｌｉｕ他は、ｔのλ次２変数多項式の割り当て｛ｆｉ（ｕ，ｙ）｝ｉ＝１，．．．，ｔで生成されたｔの部分鍵をＦｑ’の係数と連結することにより、かなりのセキュリティの損失なしに、ｌｏｇｑビットの鍵が複合され得ることを示している。ただし、
（外５）
2008543245.tif 000004
である。すなわち、結果のｌｏｇｑビットの鍵は、Ｆｑの係数でλ次２変数多項式で生成されたものと同様のエントロピーを有する。ｔのλ次２変数多項式｛ｆｉ（ｘ，ｙ）｝ｉ＝１，．．．，ｔとＦｑ’の係数との結合した集合は、ｔ多項式集合（ｔ−ｐｏｌｙｎｏｍｉａｌ−ｓｅｔ）Ｆｉ（ｘ，ｙ）と呼ばれる。ポイントｕで評価されたｔ多項式集合Ｆｉ（ｕ，ｙ）は、以下ではｔ多項式集合の割り当て（ｔ−ｐｏｌｙｎｏｍｉａｌ−ｓｅｔ  ｓｈａｒｅ）である。
【００１１】
この技術の欠点は、Ｆｑ’での多項式が（ｑ−１ではなく）最大でｑ’−１のセンサに対応することしかできない点にある。特に、並列に結合されたＦｑ’でのｔの多項式（すなわち、ｔ多項式集合）は、最大でＮ’＝ｑ’−１のノードに対応することしかできない。例えば、８ビットＣＰＵでは、ｑ’＝２８＋１が最適な計算性能を提供するが、最大ノード数Ｎ’は２５６になる。依然として適用できる特性は、Ｆｑ’での各２変数多項式｛ｆｉ（ｘ，ｙ）｝ｉ＝１，．．．ｔ（従って、ｔ多項式集合）はλ結合耐性（λ−ｃｏｌｌｕｓｉｏｎ  ｒｅｓｉｓｔａｎｔ）があるという点である。多項式分割技術は、ｑとｑ’とＫＰＳにより使用されるＦｑ’での多項式の総数とにより課されるλの特定の下界のもとで、如何なる多項式型ＫＰＳにも適用可能である。
【００１２】
釣り合い型不完備ブロック設計（ＢＩＢＤ：ｂａｌａｎｃｅｄ  ｉｎｃｏｍｐｌｅｔｅ  ｂｌｏｃｋ  ｄｅｓｉｇｎ）は、各ブロックがちょうどｋの別個のオブジェクトを有し、各オブジェクトがちょうどｒの異なるブロックに現れ、全ての対の別個のオブジェクトがちょうどｔのブロックに一緒に現れるように、ｖの別個のオブジェクトをｂのブロックに構成することであり、この設計は、（ｖ，ｋ，ｔ）、又は同等に（ｖ，ｂ，ｋ，ｒ，ｔ）として表現可能であり、ｔ（ｖ−１）＝ｒ（ｋ−１）且つｂｋ＝ｖｒである。
【００１３】
対称のＢＩＢＤ（ＳＰＩＢＤ）では、ｂ＝ｖであるため、ｋ＝ｒである。ＳＰＩＢＤは、４つの特性を有する。各ブロックはｋ＝ｒの要素を有し、各要素はｋ＝ｒのブロックに現れ、全ての対の要素はｔのブロックに現れ、全ての対のブロックはｔの要素と交差する。
【００１４】
｜Ｓ｜＝ｖのオブジェクトの集合Ｓと｜Ｂ｜＝ｂのブロックの集合Ｂ＝｛Ｂ１，Ｂ２，．．．Ｂｂ｝とを有するブロック設計Ｄ＝（ｖ，ｋ，ｔ）を仮定し、各ブロックがちょうどｋのオブジェクトを有することを仮定すると、相補設計（ｃｏｍｐｌｅｍｅｎｔａｒｙ  ｄｅｓｉｇｎ）
（外６）
2008543245.tif 000005
は、そのブロックとして
（外７）
2008543245.tif 000006
を有する（ただし、１≦ｉ≦ｂ）。
【００１５】
（外８）
2008543245.tif 000007
は、パラメータ（ｖ，ｂ，ｂ−ｒ，ｖ−ｋ，ｂ−２ｒ＋ｔ）（ただし、ｂ−２ｒ＋ｔ＞０）を有するＢＩＢＤである。Ｄ＝（ｖ，ｋ，ｔ）がＳＢＩＢＤである場合、
（外９）
2008543245.tif 000008
もＳＢＩＢＤである。
【００１６】
有限射影平面（ＦＰＰ：Ｆｉｎｉｔｅ  Ｐｒｏｊｅｃｔｉｖｅ  Ｐｌａｎｅ）は、鍵事前配布に特に関心のあるＳＰＩＢＤのサブセットである。ＦＰＰは、パラメータ（ｎ２＋ｎ＋１，ｎ＋１，１）を有するＳＰＩＢＤである。ＦＰＰは、如何なるプライム出力ｎ（ただしｎ≧２）について存在する。オーダｎのＦＰＰは４つの特性を有する。（ｉ）各ブロックはちょうどｎ＋１のポイントを有する。（ｉｉ）各ポイントはちょうどｎ＋１のブロックに現れる。（ｉｉｉ）ちょうどｎ２＋ｎ＋１のポイントが存在する。（ｉｖ）ちょうどｎ２＋ｎ＋１のブロックが存在する。Ｃａｍｔｅｐｅ及びＹｅｎｅｒ（Ｃｏｍｂｉｎａｔｏｒｉａｌ  Ｄｅｓｉｇｎ  ｏｆ  Ｋｅｙ  Ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｍｅｃｈａｎｉｓｍｓ  ｆｏｒ  Ｗｉｒｅｌｅｓｓ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ．  Ｉｎ  Ｐｒｏｃ．  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｅｃｕｒｉｔｙ−ＥＳＯＲＩＣＳ，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ＬＮＣＳ  ３１９３，  ２００４，  ｐｐ．２９３−３０８）は、ＳＮの鍵事前配布にＳＢＩＢＤ設計を適用する。
【００１７】
パラメータ（ｎ２＋ｎ＋１，ｎ＋１，１）を有し、要素が集合Ｓに属し、｜Ｓ｜＝ｎ２＋ｎ＋１であるＦＰＰを仮定する。Ｅｓｃｈｅｎａｕｅｒ及びＧｌｉｇｏｒ（Ａ  ｋｅｙ−ｍａｎａｇｅｍｅｎｔ  ｓｃｈｅｍｅ  ｏｒ  ｄｉｓｔｒｉｂｕｔｅｄ  ｓｅｎｓｏｒ  ｎｅｔｗｏｒｋｓ．  Ｉｎ  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  ９ｔｈ  ＡＣＭ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｓｅｃｕｒｉｔｙ，  ｐｐ．４１−４７，  ２００２）の用語を使用すると、Ｓは、鍵プールに関連する。すなわち、Ｓの各要素は別個のランダムな鍵に関連する。更に、ＦＰＰの各ブロックは、鍵リング（ｋｅｙ  ｒｉｎｇ）に関連する。ＦＰＰの特性は、如何なる対の鍵リング（ブロック）も１つのランダムな鍵（要素）を共通に有することを保証する。
【００１８】
合計でＮの鍵リングを有するＮのノードのセンサネットワーク（ＳＮ）では、ｎ２＋ｎ＋１≧Ｎのブロックを有するＦＰＰは、集合Ｓを使用することにより構成される必要がある。これは、それぞれＫ＝ｎ＋１の鍵と共通の１つの鍵とを有するｎ２＋ｎ＋１≧Ｎの鍵リングを提供する。１つのノードで必要なメモリサイズは（ｎ＋１）×ｌｏｇｑ（同等にｍ＝ｎ＋１）になる。賢い攻撃者は、ＳＮを損傷可能にするためにα＝Ｋ＝ｎ＋１のノードを占領する必要がある。
【００１９】
Ｎ個のＳＮの各センサノードは、異なる鍵リングを受信する。それぞれ２つのノードが共通に特定の鍵を共有することを観測する。実際に、ＦＰＰの特性のため、それぞれｎ＋１のセンサは同じ特定の鍵を共有する。従って、このＫＰＳの鍵は、ノードの固有の認証に使用することができない。第２の関係する問題は、（ｉ）ｎがプライム出力であり、（ｉｉ）ｍ≧ｎ＋１の制約でｎ２＋ｎ＋１≧ＮであるＦＰＰを見つけることが常に可能であるとは限らない点である。
【００２０】
Ｃａｍｔｅｐｅ及びＹｅｎｅｒは、ＦＰＰ（ｎ２＋ｎ＋１，ｎ＋１，１）のうちｎ２＋ｎ＋１のブロック（ただし、ｎ＜ｍ−１（すなわち、鍵リングのサイズはｍ≧Ｋ＞ｎ＋１である））と、
（外１０）
2008543245.tif 000009
のうちＮ−ｎ２＋ｎ＋１の任意に選択された（ｎ＋１）の要素のサブブロックとを有するハイブリッド設計を構成することにより、前記の問題を解決する。副作用は次の通りである。（ｉ）Ｋ＞ｎ＋１である。（ｉｉ）いくつかの特定の鍵がｎ＋１より多くのノードにより共有される。（ｉｉｉ）いくつかの対のノードが共通にｎ２−ｎまでの鍵を共有することがある。（ｉｖ）少なくともＮ−ｎ２＋ｎ＋１のブロックは共通に鍵を有さない。従って、（ｉｖ）のため、少なくともＮ−ｎ２＋ｎ＋１は、共通鍵を直接確立することができず、（ｉ）、（ｉｉ）及び（ｉｉｉ）のため、α≦ｎ＋１＜Ｋ≦ｍであり、すなわち、ネットワークの弾力性が低下する。
【００２１】
近年、大規模ＤＳＮの通信インフラストラクチャを安全にするために、鍵事前配布に基づく複数のランダムな鍵管理方式が提案されている。このような管理方式は、センサノードが無線で最小程度の周辺ノード（例えば、無線通信範囲内のノード）に接続することができ、センサノードが配置の後に非常に限られた移動性を有するという仮定に基づいて、ＤＳＮ規模の接続性を仮定する。これらの方式は、ＤＳＮの動作上の制約を満たすが、最大でＤＳＮ規模の安全な接続性と、ネットワークの弾力性を目的とする。ランダムな鍵事前配布方式では、各ノードは、配置前に大規模の鍵プールから鍵のランダムなサブセットを受信する。ある程度の確率で安全な通信を行う鍵について合意するために、２つの周辺ノードは、これらのサブセット内で１つの共通鍵を見つけ、その鍵を共有秘密鍵として使用する。共通鍵を見つけなかった２つのセンサノードは、共通鍵を確立することを支援するために、周辺の又は数ホップ離れた他の信頼のあるノードを利用する。Ｂｌｏｍ（Ａｎ  ｏｐｔｉｍａｌ  ｃｌａｓｓ  ｏｆ  ｓｙｍｍｅｔｒｉｃ  ｋｅｙ  ｇｅｎｅｒａｔｉｏｎ  ｓｙｓｔｅｍｓ．  Ｉｎ  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  ＥＵＲＯＣＲＹＰＴ  ８４  ｗｏｒｋｓｈｏｐ  ｏｎ  Ａｄｖａｎｃｅｓ  ｉｎ  ｃｒｙｐｔｏｌｏｇｙ  ｔｈｅｏｒｙ  ａｎｄ  ａｐｐｌｉｃａｔｉｏｎ  ｏｆ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｔｅｃｈｎｉｑｕｅｓ，  ｐｐ．３３５−３３８，  １９８５）又はＢｌｕｎｄｏの方式に基づくランダムな鍵ペア事前配布方式は、ネットワークの弾力性を増加し、更にノード認証を提供することにより、前者を拡張する。
【００２２】
しかし、ランダムな鍵事前配布方式は、安全なＢＳＮには適していない。第１に、小規模の周辺ノードのため、ＢＳＮにより、常に２つの任意のノードが共通鍵を直接的又は間接的に確立することができるとは限らない。第２に、ノード占領（ｎｏｄｅ  ｃａｐｔｕｒｅ）の可能性のため、ノード認証が仲介なしに直接実行されるべきである。
【００２３】
独立したＢＳＮは相互接続されていないため、ＤＳＮ又はアドホックネットワークについて示唆されている集中型又は分散型グローバル侵入検知システム（ＩＤＳ：ｉｎｔｒｕｓｉｏｎ  ｄｅｔｅｃｔｉｏｎ  ｓｙｓｔｅｍ）は、ＢＳＮでは使用不可能である。損傷したノードがＢＳＮで検出され得るが、通常のシステム及び方法は、他のＢＳＮの残りのノードにこの情報を効率的に配布しない。従って、ＢＳＮは、大規模ＤＳＮよりノード複製攻撃をかなり受けやすい。例えば、病院では、利口な攻撃者からの攻撃がＢＳＮのセキュリティにとって最大の脅威である。文献に明確に記載されていないが、前の鍵配布方式のノード占領及びノード複製に対するネットワークの弾力性は、ＤＳＮ規模の有効なＩＤＳの存在にかなり依存する。ネットワークの弾力性の無いことは、攻撃者が全体のＤＳＮ通信の機能を損傷するために占領する必要のあるノードの数λとして定義される。賢い攻撃者は、攻撃を開始するために、わざわざλのノードを占領して不正に変更しない。賢い攻撃者は、１つ又は小部分のノードだけを占領し、ネットワークを攻撃するために損傷した鍵を使用する。実際に、気付かれないようにするため、攻撃者は、ネットワークのネットワーク動作を混乱させず、機密情報を読み取ること若しくは変更することを試み、又は誤ったメッセージを投入する。このように、攻撃者は、他のネットワーク通信を損傷するために自分のリソースを浪費せずに、所望の情報を取得及び／又は投入し得る。
【００２４】
最後に、周辺により支援される鍵確立機構は、ある方式では、高度の安全なＤＳＮの接続性を実現する必要がある。適切な鍵を有する攻撃者は、１つ以上の周辺ノード、このようなノードに隣接するノード等から支援を取得し、完全な周辺と鍵を確立することができる。ノードの周辺への鍵確立の支援を制限することによってセキュリティを改善するために安全な接続性が犠牲になる場合、攻撃者は依然として移動して、できるだけ多くの周辺を攻撃しようとすることができる。効率的且つ安全な鍵管理方式は、特にＢＳＮの設定で賢い攻撃者を考慮しなければならない。
【発明の開示】
【発明が解決しようとする課題】
【００２５】
必要なものは、認証、機密性及び整合性サービスを可能にし、最適な性能効率と結合した更なるネットワークの安全な接続性、弾力性及び拡張性を提供する鍵事前配布方式である。また、ＢＳＮの動作条件に適した事前配布鍵の使用を制御する鍵管理方式も必要である。本発明は、前述の制約及び他のものを克服する改善した装置及び方法を検討する。
【課題を解決するための手段】
【００２６】
一態様によれば、患者を監視する無線ネットワークは、患者に動作可能に結合され、患者の健康状態に関する情報を収集して無線ネットワークに伝達する１つ以上の無線センサを有する人体センサネットワークを有する。設定サーバは、１つ以上のセンサが無線ネットワークに配置される前に、鍵情報で１つ以上の無線センサを構成する。移動基地局は、人体センサネットワークに関連する１つ以上のセンサに鍵証明書を配布し、２つのセンサは、事前配布鍵情報と、基地局により配布された鍵証明書とに少なくとも部分的に基づいて、固有の鍵ペアを生成する。
【００２７】
他の態様によれば、無線ネットワークは、１つ以上の無線ノードを有するネットワークと、１つ以上のノードが無線ネットワークに配置される前に、鍵情報で１つ以上の無線ノードを構成する設定サーバとを有する。基地局は、ネットワークに関連する１つ以上のノードに鍵証明書を配布し、これにより、２つのノードは、事前配布鍵情報と、基地局により配布された鍵証明書とに少なくとも部分的に基づいて、固有の鍵ペアを生成する。
【００２８】
更に他の態様によれば、無線システムで通信するセンサノードｕ及びセンサノードｖに対して設定サーバを介してセキュリティ鍵を事前配布することを有する方法は、無線システムの拡張性、弾力性及び性能効率を最大化するために、組み合わせの配布を使用してｔ多項式集合の割り当てを評価して配布する。
【００２９】
更に他の態様によれば、オーダｎのｎ−１の直交ラテン方陣（ただしｎはプライム出力である）の集合から有限射影平面（ｎ２＋ｎ＋１）を構築することを有する方法は、移動センサシステムでセンサｕを特定する。共通のｔ多項式集合の割り当てが効率的に発見され、ｔ多項式集合の割り当ての評価ポイントが、ｕのセンサ識別子からセンサｖにより効率的に導かれる。
【発明の効果】
【００３０】
本発明の１つの利点は、多数のセンサノードにセキュリティ鍵を提供し、電池とＣＰＵ電力とメモリとに制約のあるノードで通信上、計算上及び記憶上の効率を最適化する点にある。
【００３１】
他の利点は、多数のセンサノードへの事前配布されたセキュリティ鍵に対する拡張したセキュリティ強度を提供する点にある。
【００３２】
他の利点は、セキュリティが無線ネットワークのユーザにトランスペアレントに提供される点にある。
【００３３】
他の利点は、どのような任意の対のセンサノード（又は多数のセンサ）であれ、固有の識別認証を可能にし、センサ、無線の周辺密度又はサイズに無関係に信頼関係の確立を可能にするセキュリティが提供される点にある。
【００３４】
他の利点は、セキュリティは無線ネットワークが損傷し得る程度を緩和するという点にある。
【００３５】
好ましい実施例の以下の詳細な説明を読むことで、多数の更なる利点が当業者に明らかになる。
【発明を実施するための最良の形態】
【００３６】
本発明は、様々な構成要素及び構成要素の構成の形式、並びに様々なステップ及びステップの構成の形式になってもよい。図面は、単に好ましい実施例を説明するためのものであり、本発明を限定するものとして解釈されるべきではない。
【００３７】
［決定論的鍵ペア事前配布システム（ＤＰＫＰＳ：Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｐａｉｒｗｉｓｅ  Ｋｅｙ  Ｐｒｅ−ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｓｙｓｔｅｍ）及び方法］
図１は、設定サーバ４と、複数の無線センサ６、８、１０、１２、１４、１６、１８及び２０と、複数の人体センサネットワーク２２、２４及び２６とを有する移動センサシステム２を示している。設定サーバ４は、セキュリティ専用サーバであり、センサの配置の前にセキュリティのみに積極的に関与する。無線センサ６−２０は、センサ６−２０が使用される前の初期構成段階（例えば、配置前）に設定サーバ４に接続する。設定サーバ４は、典型的には物理的に保護された外周の中にあり、許可された人にのみアクセス可能である。配置段階中に、無線センサは、設定サーバに連絡する手段を有さない。配置領域は、典型的には公にアクセス可能である。無線センサ６−２０は、患者の医療データを収集して伝達する役目をする。センサ６−２０のいずれかは、１つ以上のセンサ６−２０と無線接続を確立する。センサノードは、メモリと電池とＣＰＵとに制約がある。人体センサネットワーク（ＢＳＮ：ｂｏｄｙ  ｓｅｎｓｏｒ  ｎｅｔｗｏｒｋ）２２−２６は、無線ネットワーク接続されたセンサノードの集合であり、これらのセンサノードは１人以上の患者（図示せず）に取り付けられてもよい。ＢＳＮ２２−２６は、システム内の多数のノードのため、典型的には帯域に制約がある。例えば、病院環境では、数百又は数千ものＢＳＮ（例えば、患者毎に１つ）が存在し得る。
【００３８】
ＢＳＮアプリケーションは、ｌｏｇｑビットの鍵を必要とする。実施例によれば、
（外１１）
2008543245.tif 000010
であり、ｔ≧１である。所要のセキュリティレベルにｑを固定すると（例えば、６４ビット）、Ｆｑ’の多項式が計算可能になり、ｌｏｇｑビットの鍵を得るためにＬｉｕ他の多項式の最適化が適用可能になる。ｔのλ次２変数多項式｛ｆｉ（ｘ，ｙ）｝ｉ＝１，．．．，ｔとＦｑ’の係数との結合した集合は、ｔ多項式集合（ｔ−ｐｏｌｙｎｏｍｉａｌ−ｓｅｔ）Ｆｉ（ｘ，ｙ）と呼ばれる。ポイントｕで評価されたｔ多項式集合Ｆｉ（ｕ，ｙ）は、以下ではｔ多項式集合の割り当て（ｔ−ｐｏｌｙｎｏｍｉａｌ−ｓｅｔ  ｓｈａｒｅ）である。
【００３９】
図２は、前述のシステム２のようにセンサ間で固有の鍵ペアを確立するために使用される設定方法３２と、鍵事前配置方法３４と、ｔ多項式集合の割り当ての発見方法３６と、鍵確立方法３８とを有する方法３０を示している。３２において、設定サーバは、Ｎのセンサに対応するために使用され得るｔ多項式集合の割り当てと組み合わせ設計とを生成する。ただし、Ｎは相互運用可能なノードのグループのサイズであり、１以上の整数である。３４において、設定サーバは、組み合わせ配布に従ってｔ多項式集合の割り当てを各センサに配布する。配置されると、３６において、２つの任意のセンサｕ及びｖは、何のｔ多項式集合の割り当てを共通に有しているかを見つける。３８において、２つの任意のセンサｕ及びｖは、共通のｔ多項式集合の割り当てを評価することにより、固有の鍵ペアＫｕｖを生成する。
【００４０】
この実施例の一態様は、弾力性を減少させずに、最適なノード性能効率を維持しつつ、ｔ多項式集合に基づくＫＰＳの拡張性を増加させる。１つの手法では、ＦＰＰ（ｎ２＋ｎ＋１，ｎ＋１，ｎ）に従って（すなわち、各ｔ多項式集合Ｆｂｉ，ｊ（ｘ，ｙ）のＮ’／（ｎ＋１）の別個の割り当てを、ＦＰＰのブロックＢｉ（ｉ＝ｎ２＋ｎ＋１）に属する各要素ｂｉ，ｊ（ｊ＝１，．．．ｎ＋１）に関連付けることにより）、ｎ＋１のｔ多項式集合が各ノードｕに配布される。ＦＰＰの特性のため、異なるブロックＢｉ，Ｂｊ∈ＦＰＰ（ｉ≠ｊ）の要素に従って配布されたそれぞれｎ＋１のｔ多項式集合の割り当てを有する２つの任意のノードｕ及びｖは、１つのｔ多項式集合Ｆｋ（ｘ，ｙ）を共有する。この１つのｔ多項式集合Ｆｋ（ｘ，ｙ）は、ｌｏｇｑビットの固有の鍵ペアを計算するために使用することができる。同様に、同じブロックＢｉ∈ＦＰＰの要素に従って配布されたそれぞれｎ＋１のｔ多項式集合の割り当てを有する２つのノードは、ｎ＋１のｔ多項式集合の割り当てを共通に有する。このように、ノードは、ｌｏｇｑビットの固有の鍵ペアを計算するために、いずれかのｎ＋１のｔ多項式集合の割り当てを使用可能することができる。
【００４１】
この技術により、ネットワークの弾力性を失わず、計算上の性能を最適に保持して固有の鍵ペアを共有する確率を保持しつつ、Ｂｌｕｎｄｏ他とＣａｍｔｅｐｅ及びＹｅｎｅｒのＫＰＳとの拡張性を増加することが可能になる。更に、このような手法は、ネットワークの弾力性又は直接の信頼する接続性の欠点なしに、Ｃａｍｔｅｐｅ及びＹｅｎｅｒのＫＰＳのＦＰＰ存在問題を解決する。
【００４２】
３２において、設定サーバは、Ｆｑ’でｔ×（ｎ２＋ｎ＋１）のλ次２変数多項式
（外１２）
2008543245.tif 000011
の集合
（外１３）
2008543245.tif 000012
をランダムに生成する。次に、ｊ＝１，．．．ｎ２＋ｎ＋１について、設定サーバは、
（外１４）
2008543245.tif 000013
からｔの多項式を順に選択し、ｎ２＋ｎ＋１のｔ多項式集合Ｆｊ（ｘ，ｙ）を形成する。次に、集合Ｓ（ただし｜Ｓ｜＝ｎ２＋ｎ＋１）に属する要素でＦＦＰ（ｎ２＋ｎ＋１，ｎ＋１，１）を生成する。集合Ｓは、多項式プールに関連する。すなわち、Ｓの各要素ｊは別個のｔ多項式集合Ｆｊ（ｘ，ｙ）に関連する。更に、ＦＰＰの各ブロックは多項式リングに関連する。ＦＰＰの特性は、多項式リング（ＦＰＰのブロック）の如何なる対も１つのｔ多項式集合Ｆｋ（ｘ，ｙ）（要素ｋ）を共通に有することを保証する。
【００４３】
３４において、各センサノードｕは、設定サーバからｎ＋１のｔ多項式集合の割り当てＦｂｉ，ｊ（ｐｕ，ｊ，ｙ）を受信する。ただし、ｐｕ，ｊ∈Ｆｑ’、ｂｉ，ｊ∈Ｂｉ∈ＦＰＰ、ｊ＝１，．．．ｎ＋１である。ポイントｐｕ，ｊは有限フィールドＦｑ’から取り出されなければならない。このことは、ｐｕ，ｊをｑ’−１の異なる可能な値に制限する。しかし、対応するセンサの数Ｎは、ｑ’−１より大きくなる可能性がある。鍵ペアの固有性を保証するために、２つの異なるセンサｕ及びｖは、同じポイントｐｋで評価された同じｔ多項式集合Ｆｋ（ｘ，ｙ）を有することができない。各ｔ多項式集合Ｆｊ（ｘ，ｙ）（ｊ＝１，．．．ｎ２＋ｎ＋１）は、Ｎ’＝ｑ’−１の異なるポイントで評価可能であり、Ｆｊ（ｘ，ｙ）のインデックスｊはｎ＋１のＦＰＰブロックに現れるため、（ｊが現れる）これらのブロックのそれぞれは、せいぜいＮ’／（ｎ＋１）の異なるセンサにＦｊ（ｘ，ｙ）の別個の割り当てを事前配布するために使用される。Ｎ≦Ｎ’ｎ（１−１／（ｎ＋１））＋Ｎ’のノードに対応するための鍵事前配布処理は、以下のステップを使用する。
１．要素｛ｂ１，１，．．．ｂ１，ｎ＋１｝を有するＦＰＰの第１のブロックＢ１で始まり、第１のノード（ｕ１）は、Ｆｑ’のポイントｐ１で評価されたｔ多項式集合の割り当てＦｂ１，１（ｐ１，ｙ）〜Ｆｂ１，ｎ＋１（ｐ１，ｙ）を受信する。第２のセンサ（ｕ２）は、ポイントｐ２で評価されたＦｂ１，１（ｐ２，ｙ）〜Ｆｂ１，ｎ＋１（ｐ２，ｙ）を受信する。第Ｎ’／（ｎ−１）のセンサ（ｕＮ’／（ｎ＋１））がポイントｐＮ’／（ｎ＋１）で評価されたＦｂ１，１（ｐＮ’／（ｎ＋１），ｙ）〜Ｆｂ１，ｎ＋１（ｐＮ’／（ｎ＋１），ｙ）を受信するまで以下同様に続く。
２．要素｛ｂ２，１，．．．ｂ２，ｎ＋１｝を有するＦＰＰの第２のブロックＢ２で続き、ｂ１，１＝ｂ２，１を仮定して、センサｕ１＋Ｎ’／（ｎ＋１）は、ポイントｐ１＋Ｎ’／（ｎ＋１）で評価されたＦｂ１，１（ｐ１＋Ｎ’／（ｎ＋１），ｙ）を受信し（Ｆｂ１，１（ｘ，ｙ）はセンサｕ１，．．．ｕＮ’／（ｎ＋１）の低いポイントで既に評価されているため）、ポイントｐ１で評価されたＦｂ２，２（ｐ１，ｙ）〜Ｆｂ２，ｎ＋１（ｐ１，ｙ）を受信し、以下同様に続く。
３．ＦＰＰの全てのブロックを使用して、システムのＮのノードに対応するためにステップ１及び２を繰り返す。
【００４４】
３６において、ｔ多項式集合の割り当てが発見される。配置の後で鍵ペアを確立する前に、各センサノードｕは、どのｔ多項式集合を相手のノードｖと共有するかを発見しなければならない。このため、ノードｕ及びｖはこれらのＩＤを交換する。これらのＩＤは、自分が持っているｎ＋１のｔ多項式集合の割り当てのインデックスと、それぞれｎ＋１のｔ多項式集合の割り当てが評価されたポイントｐｕ１，．．．ｐｕｎ＋１、ｐｖ１，．．．ｐｖｎ＋１とを暗示的に有する。最後に、（共通のｔ多項式集合Ｆｋ（ｘ，ｙ）に対応する）インデックスｋと、それぞれの評価ポイントｐｕ及びｐｖとを見つける。
【００４５】
３８において、鍵が確立される。鍵ペアＫｕｖを計算するために、ノードｕは、ｉ＝１，．．．ｔについて、ポイントｐｖ（すなわち、ｆｊｉ（ｐｕ，ｐｖ））で（Ｆｋ（ｐｕ，ｙ）に含まれる）ｔのλ次２変数多項式ｆｋｉ（ｐｕ，ｙ）を評価し、ｔの部分鍵を取得する。次に、ノードｕはｔの部分鍵をｌｏｇｑ’ビットに切り捨て、ｔの鍵セグメントを連結し、ｌｏｇｑビットの最終的な鍵ペアＫｕｖを形成する。
【００４６】
［簡単なセンサＩＤ］
図３は、ＤＰＫＰＳでセンサｕを特定する方法５０を示している。５２において、有しているｎ＋１のｔ多項式集合の割り当てのｎ＋１のインデックスｂｉ．１，．．．ｂｉ，ｎ＋１は、評価されたｎ＋１のポイントｐｕ１，．．．ｐｕｎ＋１と連結される。５４において、このようなＩＤは、センサｕを一意に特定し、５６において、共通のｔ多項式集合の割り当てとｔ多項式集合の割り当ての評価ポイントとの非常に簡単な発見が可能になる。
【００４７】
５８において、簡単なセンサＩＤを使用することにより共通のｔ多項式集合の割り当てが発見され、２つのセンサｕ及びｖは、各ＩＤでどのインデックスが共通であるか（例えば、インデックスｋ）を見つける。６０において、ｔ多項式集合の割り当ての評価ポイントは、簡単なセンサＩＤに含まれる第ｋのポイントを得ることで導かれる。
【００４８】
［最適化センサＩＤ］
簡単なセンサＩＤを使用することはｎが増大したときにＤＰＫＰＳの記憶及び通信コストを増加させるため、直交ラテン方陣（ＭＯＬＳ：ｍｕｔｕａｌｌｙ  ｏｒｔｈｏｇｏｎａｌ  Ｌａｔｉｎ  ｓｑｕａｒｅ）に基づいてＦＰＰの特性を利用することにより、代替の最適化センサＩＤ方法が使用され得る。この最適化方法は、ｎの実用的な値で非常に短い長さを有するセンサＩＤを構築する。
【００４９】
図４は、前述のシステム２のような移動センサシステムでセンサを特定するために使用される方法７０を示している。
【００５０】
ＦＰＰ（ｎ２＋ｎ＋１，ｎ＋１，１）は、オーダｎのｎ−１の直交ラテン方陣（ＭＯＬＳ）の集合から構築される。ラテン方陣は、各シンボルが各行及び各列にちょうど１つ現れるようにエントリがｎのシンボルを有するｎ×ｎの正方行列Ｌである。シンボルは、１，．．．ｎからの整数として使用される。Ｌを構築する非常に簡単な方法は、整数１，２，．．．ｎを最初の行から自然の順序で配置し、続く行では前の行を右に循環的に回転することによるものである。
【００５１】
７２において、直交ラテン方陣（ＭＯＬＳ）が構築される。重ね合わされたときにｎ２の対のシンボル（ｌｉｊ１，ｌｊｉ２）（ｉ＝１，２，．．．ｎ、ｊ＝１，２，．．．ｎ）のそれぞれがちょうど１回現れる場合に、ｎのシンボル１，２，．．．ｎで２つのラテン方陣Ｌ１＝｜ｌｉｊ１｜及びＬ２＝｜ｌｉｊ２｜は直交する。それぞれ他のものと直交関係にそれぞれある同じオーダｎのラテン方陣Ｌ１，Ｌ２，．．．Ｌｔの集合は、ＭＯＬＳの集合と呼ばれる。オーダｎのｎ−１のＭＯＬＳの集合は完全系（ｃｏｍｐｅｔｅ  ｓｅｔ）である。
【００５２】
直交ラテン方陣Ｌ１＝｜ｌｉｊ１｜及びＬ２＝｜ｌｉｊ２｜の対が与えられると、第１の方陣のセルは、１つの特定のシンボルｌ１を有する。ラテン方陣の特性のため、各行及び列にこれらのセルのうち１つのみが存在する。直交性のため、第１の方陣のセルに対応する直交関係のセルのｎのエントリは、直交関係で横断線（ｔｒａｎｓｖｅｒｓａｌ）を形成する。例えば、ｎのエントリはちょうど１つ各シンボルを有し、これらのセルのそれぞれは異なる行及び列にある。
【００５３】
ｎのプライム出力について、ｆａ（ｘ，ｙ）＝ａｘ＋ｙ（ａ≠０∈Ｆｎ）の多項式の集合は、オーダｎのｎ−１のＭＯＬＳの完全系を表す。これは非常に簡単な構成方法をもたらす。ｅ１，ｅ２，．．．ｅｎをＦｎの要素（すなわち、整数１，．．．ｎ）とする。この場合、各要素ｅｍ（ｍ＝１，２，．．．ｎ）について、行列Ｌｅｍ＝｜ｌｉｊｅｍ｜の要素ｌｉｊｅｍは、順に以下のように計算される。
ｌｉｊｅｍ＝（ｅｍ×ｅｉ）＋ｅｊ      （式１）
パラメータｎ及びｅｍは、特定の直交ラテン方陣Ｌｅｍ＝｜ｌｉｊｅｍ｜を再構成するのに十分である。
【００５４】
７４において、有限射影平面（ＦＰＰ）がＭＯＬＳから構成される。Ｌ１，Ｌ２，．．．Ｌｎ−１をオーダｎのＭＯＬＳの完全系であり、Ｍをｎ×ｎの行列であるとする。まず、行列Ｍは、第１行から第ｎ行まで自然の順序でｎ２の整数１，．．．ｎ２を配置することにより構成される。次に、オーダｎのアフィン平面ＡＧ（２，ｎ）がＭＯＬＳから以下のように生成される。（ｉ）最初のｎのブロックはＭの行である。（ｉｉ）次のｎのブロックはＭの列である。（ｉｉｉ）残りのｎ２−ｎのブロックは、Ｍに各Ｌｅｍを順に重ね合わせ、各Ｌｅｍの単一のシンボルｌｅｍに対応するＭの要素をブロックとして採用することにより形成される。各Ｌｅｍはｎの異なるシンボルを有するため、それぞれのＬｅｍ：Ｍの重ね合わせはｎのブロックを生じる。最後に、ＦＰＰ（ｎ２＋ｎ＋１，ｎ＋１，１）を取得するため、（ｉ）アフィン平面の最初のｎのブロックに新規の整数ｎ２＋１を加算し、（ｉｉ）次のｎのブロックに新規の整数ｎ２＋２を加算し、（ｉｉｉ）各Ｌｅｍから構成されたｎのブロックに整数ｎ２＋２＋ｅｍを加算し、（ｉｖ）ｎ＋１の新規に加算された整数を有する新規のブロックを設計に追加する。
【００５５】
ｎ及びｉが与えられると、ブロックＢｉ∈ＦＰＰ（１＜ｉ≦２ｎ）を再構成することは簡単である。例えばｎ＝３では、ブロックＢ４は、Ｍ３×３の最初の列と整数１１とから構成される。すなわち、Ｂ４＝（１，４，７，１１）である。ブロックＢｉ∈ＦＰＰ（２ｎ＜ｉ≦ｎ２＋ｎ）では、インデックスｉもまた、Ｂｉが生成されたラテン方陣Ｌｅｍのインデックスｅｍ（１≦ｅｍ≦ｎ−１）を暗示的に特定する。例えばｎ＝３では、ブロックＢ１２はＬ２から生成される。これらのブロックＢｉ（２ｎ＜ｉ≦ｎ２＋ｎ）のうち１つを再構成するために、要素ｌｅｍが更に必要になる。
【００５６】
７６において、３つの数字ｉ、ｉｐ及びｌｅｍを連結することで、センサｕが特定される。ただし、１≦ｉ≦ｎ２＋ｎ＋１、１≦ｉｐ≦Ｎ’／（ｎ＋１）、１≦ｅｍ≦ｎである。最初のｉは、ｕのどのｔ多項式集合の割り当てが選択されたかに従ってブロックＢｉ∈ＦＰＰを特定する。第２のものは、Ｂｉ内でのｕへのｔ多項式集合の割り当ての配布の順序ｉｐであり、第３のものは、Ｂｉが導かれたラテン方陣Ｌｉの要素である。このようなＩＤは、センサｕを一意に特定し、簡単なＩＤに比べて、共通のｔ多項式集合の割り当てとｔ多項式集合の割り当ての評価ポイントとのより効率的な発見を可能にする。
【００５７】
７８において、最適化センサＩＤについてｔ多項式集合の割り当てが発見される。８０において、最適化センサＩＤについてｔ多項式集合の評価ポイントが導かれる。
【００５８】
図５は、最適化センサＩＤに含まれる情報を使用することにより、共通のｔ多項式集合の割り当てを発見する方法１００を示している。１０２において、最適化センサＩＤにより、センサノードｕは、自分のｔ多項式集合の割り当てのインデックスと、相手のノードｖのインデックスとを計算することが可能になる。１０４において、この情報を比較することにより、ノードｕは、ノードｖと共通のｔ多項式集合の割り当てＦｋ（ｐｕ，ｙ）のインデックスｋ（１≦ｋ≦ｎ２＋ｎ＋１）を導くことができる。
【００５９】
センサｕが有しているｔ多項式集合の割り当てＦｂｉ，ｊ（ｐｕｊ，ｙ）（ｊ＝１，．．．ｎ＋１）のインデックスは、Ｂｉ∈ＦＰＰの要素｛ｂｉ，１，ｂｉ，２，．．．ｂｉ，ｎ＋１｝の一対一のマッピングである。前述のように、ｎとＢｉのインデックスｉと整数ｌｅｍとを与えられると、一意に｛ｂｉ，１，ｂｉ，２，．．．ｂｉ，ｎ＋１｝＝Ｂｉを再構成することが可能になる。ここで、２つの場合を区別する必要がある。１０６において、再構成が自明であるブロックＢｉ（１≦ｉ≦２ｎ）及びＢｎ２＋ｎ＋１である。代替として、１０８において、再構成が簡単であるが以下の分析を必要とするブロックＢｉ（２ｎ＜ｉ≦ｎ２＋ｎ）である。１０８において、（図３ａからのステップ５４での）アフィン平面の構成ステップ（ｉｉｉ）により、Ｂｉの要素｛ｂｉ，１，ｂｉ，２，．．．ｂｉ，ｎ＋１｝は、２ｎの座標｛（ｉ１，ｊ１），（ｉ２，ｊ２），．．．（ｉｎ，ｊｎ）｝により指定されたＭでの位置から受け取られる。ただし、ｌｅｍはＬｅｍ内に現れる。従って、これらの座標を決定して、Ｂｉの要素を得る。１１０において、インデックスｉから、Ｂｉの要素のうちｎを取り出すために使用されるラテン方陣Ｌｅｍを特定するｅｍを導くことは簡単である。１１２において、要素ｌｅｍの位置は、Ｌｅｍの横断線を決定し、ｌｅｍはＬｅｍの各行に１回現れる。従って、ｌｅｍは位置｛（１，ｊ１），（２，ｊ２），．．．（ｎ，ｊｎ）｝に現れる。ｌｅｍ及びｅｍが既知であることを仮定すると、式１を使用して以下を得る。
ｌｅｍ＝（ｅｍ×１）＋ｅｊ１，  ｅｉ１＝１
ｌｅｍ＝（ｅｍ×２）＋ｅｊ２，  ｅｉ２＝２
．．．
ｌｅｍ＝（ｅｍ×ｎ）＋ｅｊｎ，  ｅｉｎ＝ｎ
１１４において、これらの式を解き、別個の値（ｅｊ１，ｅｊ２，ｅｊｎ）∈ＦｎのベクトルＶを生成する。前述のように、Ｆｎからの要素ｅ１，ｅ２，．．．ｅｎは、行列Ｌｅｍ＝｜ｌｉｊｅｍ｜の各要素ｌｉｊｅｍを計算するために順に使用される。すなわち、要素ｅ１は位置｛（１，１），（２，１），．．（ｎ，１）｝の要素を計算するために使用され、要素ｅ２は位置｛（１，２），（２，２），（３，２），．．（ｎ，２）｝の要素を計算するために使用され、以下同様である。換言すると、各値（ｅｊ１，ｅｊ２，ｅｊｎ）∈Ｆｎはｌｅｍが現れる座標｛（１，ｊ１），（２，ｊ２），．．．（ｎ，ｊｎ）｝を決定する。例えば、ｉ３＝３についてｅｊ３＝２である場合、ｊ３＝２である（ｌｅｍは｛（１，ｊ１），（２，ｊ２），（３，２），．．．（ｎ，ｊｎ）｝に現れる）。
【００６０】
最後に１１６において、これらの座標は行列Ｍの要素にマッピングされ、Ｂｉのｎ＋１の要素からｎを決定することが簡単になる。ここで、アフィン平面のブロックを有している。そのブロックにｎ２＋ｎ＋ｅｍを加算して、｛ｂｉ，１，ｂｉ，２，．．．ｂｉ，ｎ＋１｝＝Ｂｉを得る。この方法でＦＰＰのブロックを生成することは、Ｆｎで（せいぜい）ｎの加算とｎの乗算とを必要とする。
【００６１】
図６は、ｔ多項式集合の割り当ての評価ポイントを導く方法１３０を示している。ノードｕが鍵Ｋｕｖを生成するためにその割り当てＦｋ（ｐｕ，ｙ）を評価するポイントｐｖを導くために、ノードｕはＦＰＰの特性により可能になる簡単な処理に従わなければならない。
【００６２】
前述のように、ｉｐはブロックＢｉ∈ＦＰＰ（１≦ｉ≦ｎ２＋ｎ＋１）に従ったｔ多項式集合の割り当ての配布におけるノードｖのオーダである。ｔ多項式集合Ｆｋ（ｘ，ｙ）の割り当てがｖに配布されていることを仮定する。以下に説明する処理により、ｖの割り当てＦｋ（ｐｖ，ｙ）が評価されるポイントｐｖ∈Ｆｑ’の導出が可能になる。
【００６３】
（外１５）
2008543245.tif 000014
であることを仮定する。ただし、ｓｋは、ブロックＢｊ∈ＦＰＰ（ｊ＝１，．．．ｉ）でのＦｋ（ｘ，ｙ）の出現回数を定量化したものである。
【００６４】
１３２において、ＦＰＰはＭＯＬＳから構成されるため、その最初のｎ２の要素は、ｎの続くブロックＢ１＋ｔ，Ｂ２＋ｔ，．．．Ｂｎ＋ｔ（ｔ＝０，ｎ，２ｎ，３ｎ，．．．ｎ×ｎ）の各グループに１回現れる。１３４において、ブロックインデックスｉ（１≦ｉ≦ｎ２＋ｎ）とｔ多項式集合のインデックスｋ（ｋ≦ｎ２）とが与えられると、その出現回数ｓｋを導くことは自明である。すなわち、
（外１６）
2008543245.tif 000015
である。
式ｋ＝ｎ２＋ｊ（ｊ＝１，．．．ｎ＋１）の各要素は、ブロックＢｉ＋ｎ（ｊ−１）（ｉ＝１，．．．ｎ）のグループでｎ回出現する。この場合、ｓｋ＝ｉ−ｎ（ｊ−１）である。１３６において、ブロックＢｎ２＋ｎ＋１の要素ｋ＝ｎ２＋ｊ（ｊ＝１，．．．ｎ＋１）は、ＦＰＰ内でｎ＋１回だけ出現する。従って、ｔ多項式集合のインデックスｋとブロックインデックスｉとＦＰＰのオーダｎとが与えられると、ノードｕがノードｖとの共通の割り当てＦｋ（ｐｕ，ｙ）を評価するポイントｐｖを導くことは簡単である。
【００６５】
前記のランダムな鍵事前配布方法と異なり、この実施例により、ＢＳＮのサイズ及び密度（又はＤＳＮの期間での周辺）に無関係に、２つのランダムに選択されたセンサノードが認証するための共通鍵を直接見つけることが可能になる。更に、センサノードは、異なるＢＳＮに移動し、依然として安全な通信を認証及び／又は確立することが可能になる。ＢＳＮのセキュリティは、ＢＳＮの人間のユーザの積極的又は意識的な関与を必要とせずに機能する。
【００６６】
［運用鍵管理］
図７及び８は、セキュリティサーバ１５２と、設定サーバ１５４と、複数の無線センサ１５６、１５８、１６０、１６２、１６４、１６６、１６８、１７０と、複数の人体センサネットワーク１７２、１７４、１７６と、移動基地局１７８及び１８０とを有するシステム１５０を示している。図７は、センサ１５６−１７０が配置される前のシステム１５０を示している。図８は、センサが配置された後のシステム１５０を示している。一例では、セキュリティサーバ１５２及び／又は設定サーバ１５４は、セキュリティに使用される専用サーバである。セキュリティサーバ１５２はセキュリティ専用サーバであり、センサの配置前及び配置後にセキュリティに積極的に関与する。設定サーバ１５４はセキュリティ専用サーバであり、センサの配置前にのみ、セキュリティに積極的に関与する。センサ１５６−１７０及び基地局１７８、１８０の配置の後に、専ら移動基地局に継続的又は散発的な接続を有する。図８に示すように、配置されると、センサ１５６−１７０は、セキュリティサーバ１５２に接続しない。図７に示すように、移動基地局１７８、１８０及びセンサ１５６−１７０は、配置前段階（すなわち、装置が使用される前の初期構成段階）にのみ、設定サーバ１５４に接続することができる。
【００６７】
無線センサ１５６−１７０は、患者の医療データを収集して伝達する役目をする。一例では、センサ１５６は、第２の任意のセンサ１５８及び／又は基地局１８０への無線接続を確立してもよい。センサノードは、メモリと電池とＣＰＵとに制約がある。病院では、数千ものセンサが存在してもよい。１つ以上のＢＳＮは、無線ネットワーク接続されたセンサノードの集合である。ＢＳＮのノードは１人以上の患者に取り付けられてもよい。ＢＳＮは、典型的には帯域に制約がある。病院では、数百又は数千ものＢＳＮ（例えば、患者毎に１つ）が存在し得る。移動基地局（ＢＳ）１７８、１８０は、データにアクセスしてＢＳＮを構成するために使用される移動装置である。ＢＳは、典型的には適度のリソース及び電力の装置である。病院では、数百又は数千ものＢＳが存在し得る。
【００６８】
運用鍵管理の対策は以下の方法を有する。
１．鍵事前配布。設定／セキュリティサーバは、基本的な鍵情報を、基本的な鍵事前配布方式に従って各センサに配布し、異なる手法に従って各移動基地局に配布する。これは、センサ又は基地局が（例えば病院に）配置される前の構成段階で行われる。
２．事前配布鍵証明書。任意のＢＳは、任意のＢＳＮを形成するセンサにアクセスし、鍵証明書ＫＣｌを配布する。鍵証明書ＫＣｌは所定の後の期間Ｉｌに前のステップの事前配布鍵情報を有効にする。
３．鍵確立。２つの任意のセンサｕ及びｖは、事前配布鍵情報と有効な鍵証明書とを使用することにより、固有の鍵ペアＫｕｖを生成する。
【００６９】
［基本的な鍵事前配布方式］
ここに記載した方式の基本的なフレームワークとして使用可能な対称鍵事前配布方式（例えば、Ｂｌｏｍ、Ｂｌｕｎｏ他又はＤＰＫＰＳ）を実施するために様々な方法が使用可能である。
【００７０】
図９は、Ｂｌｏｍの対称鍵事前配布方式を使用する鍵事前配布方法２３０を示している。Ｂｌｏｍの方式は、ネットワークの如何なる対のノードも秘密鍵ペアを導くことを可能にする。Ｄｕ他（Ａ  ｐａｉｒｗｉｓｅ  ｋｅｙ  ｐｒｅ−ｄｉｓｔｒｉｂｕｔｉｏｎ  ｓｃｈｅｍｅ  ｆｏｒ  ｗｉｒｅｌｅｓｓ  ｓｅｎｓｏｒ  ｎｅｔｗｏｒｋｓ．  Ｉｎ  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  １０ｔｈ  ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ  （ＣＣＳ），  ２００３，  ｐｐ．４２−５１）による研究に基づいて、この実施例では、ＢＳＮに適するため、Ｂｌｏｍの元の方式への何らかのわずかな修正が追加されている。
【００７１】
Ｂｌｏｍの方式は以下のように使用可能である。配置前段階の間に、２３２において、設定サーバは、有限フィールドＦｑで（λ＋１）×Ｎの行列Ｇを構成する。ただし、Ｎは、異なるＢＳＮで潜在的に接触する相互運用可能なノードのグループのサイズであり、ｑは、暗号化鍵を提供するのに十分大きい数である。Ｇは、公の情報として考えられる。すなわち、潜在的に悪質なユーザを含み、如何なるセンサもＧの内容を知ることができる。２３４において、設定サーバは、Ｆｑでランダムな秘密の（λ＋１）×（λ＋１）の対称行列Ｄを生成し、２３６において、Ｎ×（λ＋１）の行列Ａ＝（ＤＧ）Ｔを計算する。ただし、（ＤＧ）ＴはＤＧ行列の転置である。Ｄは対称的であるため、Ｋ＝ＡＧは対称行列である。従って、Ｋｕｖ＝Ｋｖｕであり、Ｋｕｖは第ｕ行及び第ｖ列にあるＫの要素である。Ｋｕｖ（又はＫｖｕ）は、ノードｕとノードｖとの間の鍵ペアとして使用される。最後に、ｋ＝１，２，．．．Ｎについて、設定サーバは、
１．２３８において、行列Ａの第ｋ行をノードｋに配布し、
２．２４０において、行列Ｇの第ｋ列をノードｋに配布する。代替として、記憶要件を節約するため、行列Ｇの第ｋ列を生成するためのシードＧ（ｋ）がノードｋに配布されてもよい。
【００７２】
２４２において、シードが配布されたか否かが決定される。配布されていない場合、配置段階の後に、ノードｕ及びｖがこれらの間で鍵ペアを見つける必要があるときに、まず、Ｇの列を交換する。代替として、２４４において、シードが配布されている場合、ノードｕ及びｖはシードを交換し、他のノードのＧの列を計算する。２４６において、Ａの秘密の行を使用して、ノードｕ及びｖは、それぞれＫｕｖ及びＫｖｕを計算することができる。Ｇは公の情報であるため、その列（又はシード）は平文で送信可能である。
【００７３】
代替として、図１０に示すように、方法２５０は、鍵事前配布のためにＢｌｕｎｄｏの方式を利用する。Ｂｌｕｎｄｏ他は、グループ鍵を導くために、多項式型の鍵事前配布プロトコルを提案する。２人のユーザのグループでは、Ｂｌｕｎｄｏの方式は、唯一の利点を有するＢｌｏｍの方式の特別の場合になる。その唯一の利点とは、鍵ペア確立処理の間に通信のオーバヘッドが存在しない。ＢＳＮに関して、多項式型の鍵ペアの確立の特別な場合について以下に扱われる。
【００７４】
２５２において、設定サーバは、有限フィールドＦｑで２変数λ次多項式
（外１７）
2008543245.tif 000016
をランダムに生成する。ただし、ｑは、ｆ（ｘ，ｙ）＝ｆ（ｙ，ｘ）の特性を有するような暗号化鍵を提供するのに十分に大きい素数である。各センサは固有の識別子（ＩＤ）を有していることを仮定する。２５４において、設定サーバは、各センサｕへのｆ（ｘ，ｙ）の多項式の割り当て（すなわち、ｆ（ｕ，ｙ））を計算して配布する。
【００７５】
２５６において、何らかの２つのセンサノードｕ及びｖについて、ノードｕは、ポイントｖでｆ（ｕ，ｙ）を評価することにより、共通鍵Ｋｕｖ＝ｆ（ｕ，ｖ）を計算することができ、ノードｖは、ポイントｕでｆ（ｖ，ｙ）を評価することにより、同じ鍵Ｋｖｕ＝ｆ（ｖ，ｕ）＝ｆ（ｕ，ｖ）を計算することができる。Ｂｌｕｎｄｏ他のセキュリティの証明は、この方式は無条件に安全であり、λ結合耐性（λ−ｃｏｌｌｕｓｉｏｎ  ｒｅｓｉｓｔａｎｔ）があることを確保する。すなわち、せいぜいλの損傷したセンサノードの連合は、何らかの２つの損傷されていないノードの間での鍵ペアについて何も認識しない。
【００７６】
好ましい代替形態として、ＤＰＫＰＳは、センサへの鍵ペアの最初の事前配布に使用されてもよい。
【００７７】
何らかの鍵事前配布方式で事前配布された鍵の使用の信頼性を増加して制御し、従って損傷したノードの影響を減少させるために、プロアクティブな方法が使用される。
【００７８】
全てのセンサノードの存続期間が、Ｉ０，Ｉ１，Ｉ２，．．．Ｉｎとして示される期間Ｔのｎ＋１の共通の間隔に分割されることを仮定する。すなわち、センサノードは、異なるＢＳＮに接続されている場合であっても、全てグローバルの基準時間におおまかに同期する。
【００７９】
図１１は、事前配布鍵を証明する方法２６０を示しており、以下の図１２〜１５の鍵証明方法の要約である。２６２において、各時間間隔Ｉｌ−１の間に、移動基地局（ＢＳ）は、（どのセンサであれ）センサに散発的に連絡し、２６４において、センサの整合性を確認した後に、２６６において、それぞれ損傷していないセンサノードに鍵証明書ＫＣｌを配布する。２６８において、鍵証明書ＫＣｌは単一の間隔Ｉｌにセンサの事前配布鍵の整合性を有効にする。すなわち、事前配布鍵は時間間隔Ｉｌの間に有効になる。同様に、２７０において、損傷したノードｕは、鍵証明書ＫＣｌを受信しないため、その事前配布鍵は無効になる。
【００８０】
以下では、一連の方法２８０、３１０、３３０及び３７０が提示される。それぞれ後の方式は、その制約のいくつかに対処することにより、前のものを改善する。方法２８０、３１０、３３０及び３７０の間の違いは、基地局間の接続性のレベルと、基地局とセキュリティサーバとの間の接続性のレベルとにある。これらの方法はまた、どのように鍵証明書が生成又は合意されるかについて異なる。
【００８１】
図１２は、グローバル鍵証明書を集中的に発行するために使用される方法２８０を示している。このセクションでは、セキュリティサーバは、ＢＳＮ配置領域と異なる安全な場所にある。前述のように、セキュリティサーバはセキュリティ専用サーバであり、センサの配置前及び配置後にセキュリティに積極的に関与する。設定サーバはセキュリティ専用サーバであり、センサの配置前にのみ、セキュリティに積極的に関与する。従って、設定サーバは、センサが配置された後にオフラインのままになる。１つ以上の移動基地局がＢＳＮで散発的に短く存在することも仮定する。基地局もまた、セキュリティサーバと散発的に連絡する。基地局は高価なノードであるため、不正防止ハードウェアを使用し、計算能力又はメモリに制限がない。従って、移動基地局の数は、センサノードの数よりかなり小さい。典型的には基地局は無人のままであり、ＢＳＮ配置領域のみに存在するため、占領又は損傷されにくい。
【００８２】
センサノードは移動体であるため、基地局がＢＳＮの無線範囲に常にあることを仮定することができない（例えば、数個のセンサを人体に取り付けられた患者は病院の庭を散歩する）。それにもかかわらず、ＢＳＮの目的は、エンドユーザに配布されるデータを収集することであるため、ＢＳＮが基地局の無線範囲に散発的にあることを仮定する。これは、ＢＳＮにとって重要な要件である。そうでなければ、センサノードにより収集された情報は、センサノードの記憶容量の制限のため失われる可能性がある。センサネットワークのセキュリティについて静的な専用サーバを有することの制限は周知である。例えば、悪質な人は、専用サーバに対してサービス拒否（ＤｏＳ：ｄｅｎｉａｌ  ｏｆ  ｓｅｒｖｉｃｅ）攻撃を開始しようとすることがある。専用サーバが複製の移動体であり、ＢＳＮに常に存在するとは限らない場合、このような制限は消滅する。ＢＳＮ環境では、移動基地局の存在が仮定される。例えば、ある場合には、医者は庭の患者のＢＳＮからデータをダウンロードする。以下では、基地局という用語は移動基地局を示し、移動基地局はセキュリティに使用され得る。
【００８３】
配置前に、基本的な鍵事前配布方式（例えば、Ｂｌｏｍ、Ｂｌｕｎｄｏ他、ＤＰＫＰＳ）のいずれかに続いて、２８２において、センサノードは、固有の識別子とセキュリティ情報とで初期化される。λの損傷したノードの連合が基地局を扮するリスクを回避するため、センサノードと基地局との間で鍵ペアを提供するために基本的な鍵配布方式は使用されない。更に、単一のノードの損傷が残りのノードのセキュリティを損傷し、従って、セキュリティについて基地局Ｂｉを動作不可能にするため、基地局ＢＳｉとセンサノードとの間で共有されるグループ鍵は提示されない。その代わりに、２８４において、通常の鍵配布方式に続いて、基地局毎ＢＳｉ＝１，．．．，Ｍ及びセンサ毎ｕ＝１，．．．，Ｎ（Ｎ＞＞Ｍ）に、セキュリティサーバは、鍵ペアＫｕ，ＢＳｉをランダムに選択して配布する。この方式により、各センサノードは、基地局ＢＳｉと安全に通信することが可能になる。これは無条件に安全であり、ノードに必要な更なる記憶容量は、単にＭ×ｌｏｇｑである。最後に、２８６において、セキュリティサーバは、ランダムに秘密Ｋｎを選択し、ｋ＝０，１，．．．，ｎ−１についてＫｋ＝Ｆ（Ｋｋ＋１）を生成することにより、ｎ＋１の要素Ｋ０，Ｋ１，．．．，Ｋｎの鍵連鎖を生成する。ただし、Ｆは疑似乱数関数である。２８８において、セキュリティサーバは、各センサノードｕ＝１，．．．，Ｎに鍵連鎖Ｋ０の最初の要素を配布する。疑似乱数関数Ｆで、鍵連鎖のＫｋが与えられると、如何なるセンサノードも、全ての前の鍵Ｋｍ（０≦ｍ≦ｋ）を計算することができるが、後の鍵Ｋｍ（ｋ＋１≦ｍ≦ｎ）は計算不可能である。従って、最初の鍵Ｋ０を認識すると、センサノードは、単に疑似乱数関数演算を実行することにより、鍵連鎖の如何なる鍵も認証することが可能になる。鍵連鎖の第２の要素Ｋ１は、各基地局ＢＳｉに最初に配布される。
【００８４】
基地局は、信頼を受けたルートとしてのセキュリティサーバを有する公開鍵インフラストラクチャの代理の証明機関と同様の役目をする。２９０において、基地局は、損傷されていないノードに鍵証明書（ＫＣ）を発行し、損傷されていないノードは、限られた期間Ｔにその事前配布鍵を有効にする。期間Ｔの後に、ノードの事前配布鍵はもはや有効ではない。鍵連鎖の要素Ｋ０，Ｋ１，．．．，Ｋｎは、各間隔Ｉ１，Ｉ２，．．．及びＩｎの鍵証明書として順に使用される。以下では、鍵連鎖の要素は、鍵証明書ＫＣ０，ＫＣ１，．．．，ＫＣｎと呼ばれる。
【００８５】
２９２において、時間間隔Ｉｌの間に、全ての基地局ＢＳｉはセキュリティサーバに散発的に連絡する。基地局及びセキュリティサーバは強力なノードであるため、通信を安全にするために公開鍵暗号化を使用することができる。セキュリティサーバは、次の鍵証明書ＫＣｌ＋１を各基地局ＢＳｉ（ＢＳｉ＝１，．．．，Ｍ）に配布する。なお、基地局の損傷という起こりそうにない場合に、次の鍵証明書の開示を危険にさらすことなく、唯一の証明書が損傷する。すなわち、損傷した基地局自体は、次の鍵証明書を計算することができない。基地局は次の時間間隔Ｉｌ＋１にセキュリティサーバに連絡しないため、基地局の損傷は検出することが容易である。従って、損傷した基地局は、損傷した間隔まで次の間隔で鍵証明書を受け取らない。このような場合であっても、残りの基地局は、損傷した基地局ＢＳｉの識別情報について全てのセンサノードに通知するべきである。各センサノードｕは、ＢＳｉとのその共有鍵Ｋｕ，ＢＳｉを削除し、従って、信頼のある基地局のリストからＢＳｉを削除する。
【００８６】
２９４において、Ｉｌの時間間隔の間に、少なくとも１つの任意の基地局ＢＳｉは、散発的に短くＢＳＮに連絡する。２９６において、適切な鍵Ｋｕ，ＢＳｉを使用して、基地局ＢＳｉは、ＢＳＮの一部を形成するそれぞれの損傷されていないセンサノードと安全な通信を認証して確立する。２９８において、基地局は、それぞれ認証されたセンサノードに対して、時間間隔Ｉｌ＋１に対応する鍵証明書ＫＣｌ＋１を配布する。第３に、センサノードは、ｈ（Ｋｌ＋１）が格納されたＫｌと等しいことを確認する。否定的な場合に、センサノードは、基地局ＢＳｉが損傷していることを確実に推測することができ、このため、偽の鍵証明書ＫＣ’ｌ＋１を拒否することができる。
【００８７】
３００において、鍵が確立される。２つのノードが鍵ペアを確立する必要がある場合、まず、前述のように鍵ペアを導く。次に、双方が基地局ＢＳｉから有効な鍵証明書を有していることを検査する。悪質なユーザが有効な鍵証明書を取得することを妨げるために、２つのセンサノードｕ及びｖにより実行される鍵証明書の検証処理は安全でなければならない。従って、この処理は、まず、それぞれの鍵証明書を交換し、次に、現在の時間間隔Ｉｌについて発行されたことを検査し、鍵連鎖の最初の鍵Ｋ０（又は導かれた認証済みの鍵Ｋｍ（ｍ＜ｌ））により認証可能であることを検査することにより、鍵証明書を有効にすることを要求することができない。その代わりに、双方のセンサは、ゼロ知識（ＺＫ：ｚｅｒｏ  ｋｎｏｗｌｅｄｇｅ）プロトコルを動作し、双方が、実際に公開することなく、有効な証明書を有していることを証明する。ＺＫプロトコルは以下のように与えられる。
【００８８】
【表１】
2008543245.tif 000017
（１）において、ノードｕは、自己生成されたナンス（ｎｏｎｃｅ）Ｎｕをノードｖに送信する。（２）において、ノードｕは、自己生成されたナンスＮｖをノードｕに送信する。（３）において、ｕは、メッセージ認証コード（ＭＡＣ：ｍｅｓｓａｇｅ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｃｏｄｅ）を計算するために、鍵証明書ＫＣｌと双方のナンスＮｕ及びＮｖを使用する。双方のナンスは、反射攻撃（ｒｅｆｌｅｃｔｉｏｎ  ａｔｔａｃｋ）を回避するために、メッセージ（３）及び（４）に含まれなければならない。すなわち、ｖは、ＫＣｌを知らない場合に、ｖが第３のノードｗとＺＫプロトコルをうまく動作することができるＫＺＮＰを計算することにｕをだます。計算されたＭＡＣは、ＺＫプロトコルの鍵ＫＺＮＰｕｖを構成する。同様の手順で、（４）において、ｖは同じＺＫプロトコル鍵ＫＺＮＰｖｕを計算する。なお、ＫＺＮＰｕｖ≠ＫＺＮＰｖｕである。ｖがＫＣｌを知らない場合に、ＺＫプロトコルをうまく動作するためにちょうどメッセージ（７）を再生することを妨げるため、双方のＺＫプロトコル鍵は異ならなければならない。（５）において、ｕは、鍵ペアＫｕｖを使用してＫＺＮＰｕｖのＭＡＣを計算する。（６）において、ｖは、鍵ペアＫｖｕを使用してＫＺＮＰｖｕのＭＡＣを計算する。これらの２つのステップは、ＫＣｌの知識をそれぞれｕ及びｖに関連付けるために必要である。これらはまた、攻撃者が（７）及び（８）で交換されたメッセージを傍受することに対抗する。最後に、ｕは、ｖがＫＣｌを知っていることを検証する。ｖが（４）及び（７）で行うステップに続いて、ｕは、（８）でｖから受信した情報と比較するための情報を計算することができる。ノードｖは、同様の手順に従い、ｕのＫＣｌについての知識を検証することができる。なお、（７）及び（８）の交換されるメッセージは、それぞれノードｕ及びｖにより内部で格納されている情報で計算されたＭＡＣであり、更なる情報が開示されていないため、ＫＣｌについての情報は公開されない。
【００８９】
図１３は、集中的に合意されたグローバル鍵証明書を提供する方法３１０を示している。図１２からの方法２８０は、いくつかの用途にとって重要な欠点を有する。すなわち、基地局ＢＳｉがセキュリティサーバと連絡しなければならいことを要求することは、これらの用途では実現不可能なことがある。それにもかかわらず、多くの用途では、基地局は、ＢＳＮに次にアクセスする前の何らかの時間に、相互に散発的な相互接続を有する。例えば、異なるＢＳＮで収集された情報をグローバルに交換するためである。方法３１０では、このような事実を利用する。
【００９０】
方法３１０において、ＢＳＮ配置領域と異なる安全な場所にあるオフラインの設定サーバを仮定する。また、散発的に短くＢＳＮに存在する複数の移動基地局ＢＳｉ（ＢＳｉ＝１，．．．，Ｍ）の存在を仮定する。しかし、方法３１０では、基地局は、配置段階の後に設定サーバと散発的な連絡を行わない。その代わりに、散発的に短く相互接続する。方法２８０で説明した基地局についての残りの仮定は、方法３１０にも当てはまる。
【００９１】
３１２において、配置前に、基本的な鍵事前配布方式のいずれかに続いて、センサノードは、固有の識別子とセキュリティ情報とで初期化される。３１４において、通常の鍵配布方式に続いて、基地局毎ＢＳｉ＝１，．．．，Ｍ及びセンサ毎ｕ＝１，．．．，Ｎ（Ｎ＞＞Ｍ）に、セキュリティサーバは、鍵ペアＫｕ，ＢＳｉをランダムに選択して配布する。
【００９２】
基地局は、公開鍵インフラストラクチャの相互接続された証明機関と同様の役目を有する。３１６において、基地局は、損傷されていないノードに鍵証明書を発行し、損傷されていないノードは、限られた期間Ｔにその事前配布鍵を有効にする。期間Ｔの後に、ノードの事前配布鍵はもはや有効ではない。３１８において、時間間隔Ｉｌの間に、全ての基地局ＢＳｉは散発的に相互接続する。基地局は強力なノードであるため、通信を安全にするために公開鍵暗号化を使用することができる。３２０において、基地局は、時間間隔Ｉｌ＋１に対応する鍵証明書ＫＣｌ＋１について合意する。
【００９３】
時間間隔Ｉｌの間に、少なくとも１つの任意の基地局ＢＳｉは、散発的に短くＢＳＮに連絡する。３２２において、適切な鍵Ｋｕ，ＢＳｉを使用して、基地局ＢＳｉは、ＢＳＮの一部を形成するそれぞれの損傷されていないセンサノードと安全な通信を認証して確立する。３２４において、基地局は、それぞれ認証されたセンサノードに対して、時間間隔Ｉｌ＋１に対応する鍵証明書ＫＣｌ＋１を配布する。
【００９４】
時間間隔Ｉｌの後に、基地局ＢＳｉは鍵証明書Ｋｌ＋１を忘れる。従って、最大で、基地局ＢＳｉは２つの時間間隔Ｉｌ−１及びＩｌの間に鍵証明書ＫＣｌ＋１を保持する。なお、基地局の損傷という起こりそうにない場合に、次の鍵証明書の開示を危険にさらすことなく、２つのみの鍵証明書ＫＣｌ及びＫＣｌ＋１が損傷する。すなわち、損傷した基地局は、ＫＣｌ＋１への次の鍵証明書を予測することができない。基地局は次の時間間隔Ｉｌ＋１に残りの基地局に連絡しないため、基地局の損傷は検出することが容易である。このような場合であっても、残りの基地局は、損傷した基地局ＢＳｉの識別情報について全てのセンサノードに通知するべきであり、可能な場合には、この現在の時間間隔Ｉｌ＋１に新たな鍵証明書ＫＣｒｅｎｅｗｅｄｌ＋１を配布するべきである。各センサノードｕは、ＢＳｉとの共有鍵Ｋｕ，ＢＳｉを削除し、従って、信頼のある基地局のリストからＢＳｉを削除する。
【００９５】
３２６において、鍵が確立される。２つのノードが鍵ペアを確立する必要がある場合、まず、前述のように鍵ペアを導く。次に、双方が方法２８０で説明したようにＺＫプロトコルを動作することにより、有効な鍵証明書を有していることを検査する。
【００９６】
図１４は、グローバル鍵証明書がローカルで合意されることを可能にする方法３３０を示している。方法３００は、いくつかの用途にとって重要な欠点を有する。すなわち、時間間隔Ｉｌの間に全ての基地局ＢＳｉが相互接続されることを要求することは、これらの用途では実現不可能又は非実用的なことがある。依然として、確実に、基地局は、ＢＳＮに次にアクセスする前の何らかの時間に、小規模の集合で散発的に相互接続する。例えば、異なるＢＳＮで収集された情報を交換するためである。方法３３０では、このような事実が利用される。
【００９７】
３３２において、配置前に、基本的な鍵事前配布方式のいずれかに続いて、センサノードは、固有の識別子とセキュリティ情報とで初期化される。３３４において、通常の鍵配布方式に続いて、基地局毎ＢＳｉ＝１，．．．，Ｍ及びセンサ毎ｕ＝１，．．．，Ｎ（Ｎ＞＞Ｍ）に、設定サーバは、鍵ペアＫｕ，ＢＳｉをランダムに選択して配布する。３３６において、セキュリティサーバは秘密Ｓを生成する。３３８において、（ｔ，Ｍ）の閾値方式（ｔ≦Ｍ）に従って、設定サーバは、秘密ＳからＭの割り当てＳ１，Ｓ２，．．．，ＳＭを生成し、各基地局ＢＳｉにＳｉを安全に配布する。割り当てをプールしている如何なるｔ以上の基地局は、容易にＳを復元するが、ｔ−１以下の割り当てしか知らない基地局のグループは復元できない。なお、特別な場合ｔ＝１では、各基地局ＢＳｉは実際の秘密Ｓを保持する。
【００９８】
この特定の手法では、基地局は、公開鍵インフラストラクチャの相互接続された証明機関と同様の役目を有する。３４０において、基地局は、損傷されていないノードに鍵証明書を発行し、損傷されていないノードは、限られた期間Ｔにその事前配布鍵を有効にする。期間Ｔの後に、ノードの事前配布鍵はもはや有効ではない。
【００９９】
３４２において、時間間隔Ｉｌの間に、全ての基地局ＢＳｉは散発的に安全に相互接続し、小規模の相互接続されていないグループＧｇ（Ｇ１，Ｇ２，．．．ｇ＜Ｍ）を形成する。各基地局ＢＳｉは少なくとも１つのグループＧｇに接続する。従って、各グループのメンバ数は、
（外１８）
2008543245.tif 000018
であり、
（外１９）
2008543245.tif 000019
は、ｘ以下の最大の自然数ｙである。グループＧｇは、Ｇｇ＝｛Ｇｇ１，．．．，Ｇｇｋ；ｋ＝｜Ｇｇ｜｝として表され得る。例えば、Ｍ＝７の基地局でありｇ＝３である場合、｜Ｇｇ｜≧２であり、グループの構成は、Ｇ１＝｛ＢＳ２，ＢＳ３，ＢＳ６｝及びＧ２＝｛ＢＳ１，ＢＳ４，ＢＳ５｝及びＧ３＝｛ＢＳ１，ＢＳ７｝でもよい。なお、グループＧ３については、｜Ｇ３｜＝２であり、Ｇｇ１＝ＢＳ１且つＧｇ２＝ＢＳ７である。ここで従う必要な条件は、全てのｇについて｜Ｇｇ｜≧ｔであるという点である。３４４においおて、グループＧｇのメンバＧｇ１，．．．，Ｇｇｋは、Ｓを計算するための割り当てＳＧｇ１，．．．ＳＧｇｋをプールする。この場合、各グループメンバは、ＫＣｌ＋１＝Ｆ（Ｓ，ｌ＋１）を計算することにより、間隔Ｉｌ＋１に鍵証明書ＫＣｌ＋１を独立して計算する。最後に、各グループメンバはＳを忘れる。
【０１００】
時間間隔Ｉｌの間に、少なくとも１つの任意の基地局ＢＳｉは、ＢＳＮに散発的に短く連絡する。３４６において、適切な鍵Ｋｕ，ＢＳｉを使用して、基地局ＢＳｉは、ＢＳＮの一部を形成するそれぞれの損傷されていないセンサノードと安全な通信を認証して確立する。３４８において、基地局は、それぞれ認証されたセンサノードに対して、時間間隔Ｉｌ＋１に鍵証明書ＫＣｌ＋１を配布する。方法３００と同様に、時間間隔Ｉｌの後に、各基地局ＢＳｉは鍵証明書ＫＣｌ＋１を忘れる。
【０１０１】
３５０において、鍵が確立される。２つのノードが鍵ペアを確立する必要がある場合、まず、方法３００で説明したように鍵ペアを導く。次に、双方が方法２７０で説明したようにＺＫプロトコルを動作することにより、有効な鍵証明書を有していることを検査する。
【０１０２】
図１５は、別個の鍵証明書がローカルで合意することを可能にする方法３７０を示している。方法３３０は、方法２７０及び３３０に対してかなりの動作上の改善を有する。基地局のそれぞれの小部分が、設定サーバに連絡する必要なく、鍵証明書を独立して管理することができる。更に、基地局の損傷という起こりそうにない場合に、全てのＢＳＮのセキュリティも残りの時間間隔に損傷されない。
【０１０３】
前の方式は重要な利点を有する。全てのセンサノードは、移動性にかかわらず、時間間隔Ｉｌの間に安全な通信を相互に認証及び／又は確立することができる。すなわち、時間間隔Ｉｌの間に、センサノードは、異なるＢＳＮを移動することができ、依然としてこれらの全てで安全に通信することができる。換言すると、方法２７０、３００及び３３０により、単一のセキュリティドメインを通じて異なるＢＳＮでノードの論理的に安全な相互接続が可能になる。逆に、このことはセキュリティについて問題のある影響を有する。検出されていない損傷されたノードは、ＫＣｌを保持しているため、損傷の間隔Ｉｌの残りの時間に依然としてＢＳＮに接続することができ、場合によっては既にＫＣｌ＋１を保持している場合に、次の間隔Ｉｌ＋１にも接続することができる。損傷したノードは基地局をだますことができないことがわかる。従って、損傷したノードがＫｌ＋１を取得する唯一の方法は、損傷される前にそれを取得することによるものである。
【０１０４】
しかし、いくつかのセンサ用途では、システムの脆弱性はあまり重要ではない。ここでは、センサが非常に低い移動性を有する用途について言及する。例えば、一式のセンサが人体に取り付けられている場合を想定する。人体は当然に移動体であるが、取り付けられたセンサは相互に対して移動しない。
【０１０５】
方法３７０では、ＢＳＮは、同じ鍵証明書ＫＣｌを共有する全てにより論理的に安全に相互接続されていない。むしろ、この実施例では、異なるＢＳＮは、異なる鍵証明書ＫＣ１ｌ，ＫＣ２ｌ．．ＫＣｍｌを有してもよく、ＢＳＮに属するセンサノードを、異なる鍵証明書ＫＣｉｌ及びＫＣｊｌ（ｉ≠ｊ）を有するＢＳＮに属する残りのノードから隔離する。換言すると、全体のセンサは、異なる動的なセキュリティドメインに属しており、各セキュリティドメインは、基地局のグループにより専ら合意された鍵証明書により決定される。２つのセンサノードは、所定の時間間隔Ｉｌに同じセキュリティドメインに属している場合にのみ、安全に通信することができる。
【０１０６】
３７２において、鍵は、方法３００に記載したように事前配布される。３７４において、鍵証明書が事前配布される。基地局は、公開鍵インフラストラクチャのルート証明機関と同様の役目を有する。３７６において、基地局は、損傷されていないノードに鍵証明書を発行し、損傷されていないノードは、限られた期間Ｔにその事前配布鍵を有効にする。期間Ｔの後に、ノードの事前配布鍵はもはや有効ではない。異なる基地局ＢＳｉ及びＢＳｊ（ｉ≠ｊ）からの鍵証明書ＫＣＢＳｉｌ及びＫＣＢＳｊｌは等しくなくてもよい。
【０１０７】
３７８において、時間間隔Ｉｌ−１の間に、全ての基地局ＢＳｉは散発的に安全に相互接続し、小規模の相互接続されていないグループＧｇ（Ｇ１，Ｇ２．．．ｇ＜Ｍ）を形成する。各基地局ＢＳｉは少なくとも１つのグループＧｇに接続する。３８０において、グループＧｇのメンバＧｇ１，．．．，Ｇｇｋは、Ｓを計算するための割り当てＳＧｇ１，．．．ＳＧｇｋをプールする。３８２において、各グループメンバは、ＫＣｇｌ＋１＝Ｆ（Ｓ，ＮＧｇｌ）を計算することにより、間隔Ｉｌ＋１に鍵証明書ＫＣｇｌ＋１を独立して計算する。ただし、ＮＧｇｌは、間隔Ｉｌ＋１のグループＧｇに排他的なナンスである。３８４において、各グループメンバはＳを忘れる。
【０１０８】
３８６において、時間間隔Ｉｌの間に、少なくとも１つの任意の基地局ＢＳｉは、ＢＳＮに散発的に短く連絡する。３８８において、適切な鍵Ｋｕ，ＢＳｉを使用して、基地局ＢＳｉは、ＢＳＮの一部を形成するそれぞれの損傷されていないセンサノードと安全な通信を認証して確立する。３９０において、基地局は、それぞれ認証されたセンサノードに対して、時間間隔Ｉｌ＋１に鍵証明書ＫＣｇｌ＋１を配布する。前の方式と同様に、時間間隔Ｉｌの後に、各基地局ＢＳｉは鍵証明書ＫＣｇｌ＋１を忘れる。
【０１０９】
方法３７０では３つの特別の場合が存在する。第１に、各基地局ＢＳｉは、グループＧｇに一回のみ参加することを許可される場合、単一の鍵証明書Ｋｇｌ＋１を導く。その効果は、グループＧｇと同じ程度の異なるセキュリティドメインを有することである。特別な場合ｔ＝１では、各基地局ＢＳｉは自分のグループＧｉを形成し、このため、その効果は、基地局ＢＳｉと同じ数の異なるセキュリティドメインを有することである。第２に、基地局ＢＳｉがｎの異なるグループＧ１，Ｇ２，．．．Ｇｎ（１＜ｎ≦ｇ）に参加することを許可されている場合、ｎの異なる鍵証明書ＫＣ１ｌ＋１，ＫＣ２ｌ＋１，ＫＣｎｌ＋１を導く。その効果は、いくつかが論理的に接続された異なるセキュリティドメインを有することである。第３に、全ての基地局が同じ固有のグループに相互接続する場合、同じ鍵証明書について合意するため、その効果は、方法３３０と同様のグローバルなセキュリティドメインである。
【０１１０】
３９２において、鍵が確立される。２つのノードが鍵ペアを確立する必要がある場合、まず、方法３００で説明したように鍵ペアを導く。次に、双方が方法２７０で説明したようにＺＫプロトコルを動作することにより、有効な鍵証明書を有していることを検査する。異なる鍵証明書を有する２つのセンサノードは、鍵を確立することができない。
【０１１１】
方法３７０では、損傷したセンサノードは、損傷したノードにより保持されたものと異なる鍵証明書を有するセンサを攻撃するために使用不可能である。しかし、方法３７０を利用して、異なる鍵証明書を有するセンサノードは、同じＢＳＮで安全に通信することができない。この鍵管理システムは、ＢＳＮの何らかのグローバルＩＤに依存せずに、ノード占領に対する弾力性を改善し、基本的な鍵事前配布方式により必要なものより少ないセンサのメモリを使用する。
【０１１２】
好ましい実施例を参照して本発明について説明した。前述の詳細な説明を読んで理解することにより、変更形態及び代替形態が他人に明らかになり得る。本発明は、特許請求の範囲内及びその均等の範囲内にある限り、全てのこのような変更形態及び代替形態を含むものとして解釈されることを意図する。
【図面の簡単な説明】
【０１１３】
【図１】配置前段階中に複数のセンサの鍵情報を構成するために設定サーバを使用する移動センサシステム
【図２】固有の鍵ペアを利用して無線センサの対の間で安全な通信を提供する方法
【図３】図１のシステムのような移動センサシステムでセンサ識別子を使用する方法
【図４】図１のシステムのような移動センサシステムでセンサを識別する他の方法、図１のシステムのような移動センサシステムでセンサ識別子を使用する方法
【図５】共通のｔ多項式集合の割り当てを発見する方法
【図６】ｔ多項式集合の割り当ての評価ポイントを導く方法
【図７】配置前段階中に複数のセンサの鍵情報を構成するために設定サーバを使用する移動センサシステム
【図８】配置後段階中に移動センサシステムにおいて複数のセンサと対応する人体センサネットワークとの間で安全な通信を可能にするためにセキュリティサーバと基地局とを使用する移動センサシステム
【図９】Ｂｌｏｍの対称の鍵事前配布方式を使用する鍵事前配布方法
【図１０】鍵事前配布のためにＢｌｕｎｄｏの方式を使用する鍵事前配布方法
【図１１】事前配布鍵を証明する方法
【図１２】事前配布鍵を管理する方法
【図１３】事前配布鍵を管理する方法
【図１４】事前配布鍵を管理する方法
【図１５】事前配布鍵を管理する方法
【図１】
2008543245.tif 000023
【図２】
2008543245.tif 000024
【図３】
2008543245.tif 000025
【図４】
2008543245.tif 000026
【図５】
2008543245.tif 000027
【図６】
2008543245.tif 000028
【図７】
2008543245.tif 000029
【図８】
2008543245.tif 000030
【図９】
2008543245.tif 000031
【図１０】
2008543245.tif 000032
【図１１】
2008543245.tif 000033
【図１２】
2008543245.tif 000034
【図１３】
2008543245.tif 000035
【図１４】
2008543245.tif 000036
【図１５】
2008543245.tif 000037
【国際調査報告】
2008543245.tif 000038
2008543245.tif 000039