(57)【特許請求の範囲】
【請求項１】
第１のノードと第２のノードとの間でネットワークにおいて通信する方法において、
前記第１のノードが、複数の暗号要素を含む暗号要素の第１のリストを有し、
前記第２のノードが、複数の暗号要素を含む暗号要素の第２のリストを有し、
前記方法が、
ａ）前記第１のノードが、前記第２のノードから第２のノード識別子を受信するステップと、
ｂ）前記第１のノードが、前記第２のノード識別子及び前記第１のノード自体の識別子から、前記暗号要素のリストの全体的な組成を生成することなしに、前記第２のリストの１つの暗号要素との共通のルートに基づく少なくとも１つの暗号要素の前記第１のリスト内の位置を決定するステップと、
ｃ）前記第１のノードが、共通のルートを持つ前記暗号要素を用いて暗号化鍵を生成するステップと、
を有する方法。
【請求項２】
前記の各ノードの対に共通の要素の前記の各リスト内の位置と前記の各ノードの識別子との間に関係が存在する、請求項１記載の方法。
【請求項３】
前記暗号要素が、前記第１のノードと前記第２のノードとの間の共有鍵を生成する鍵材料である、請求項１又は２に記載の方法。
【請求項４】
前記方法が、前記ステップａ）の前に、暗号要素のリストを前記ネットワークの各ノードに割り当てるステップを有し、前記リストが、対応するノードの識別子に依存して、暗号要素の複数の利用可能なリストの中から選択される、請求項１又は２に記載の方法。
【請求項５】
前記暗号要素のリストは、如何なるリストの対も、共通のルートを持つ少なくとも１つの暗号要素を各々有するように生成される、請求項４に記載の方法。
【請求項６】
前記暗号要素のリストは、前記暗号要素のリストの全体的な組成を生成することなしに２つの異なるリスト内の共通の要素の位置が発見されることができるように生成される、請求項４に記載の方法。
【請求項７】
各検討されるリストの対と、共通のルートを持つ前記少なくとも１つの鍵材料の対の各リスト内の位置との間に関係が存在する、請求項４に記載の方法。
【請求項８】
前記鍵材料のリストが、有限投影面の要素として生成される、請求項３又は４に記載の方法。
【請求項９】
前記ステップｂ）が、第２のノードブロック識別子を、ｊ2＝ｉ2 ｍｏｄ（ｎ2＋ｎ＋１）のように計算することを有し、ここでｊ2が、前記第２のノードのブロック識別子であり、ｉ2が、前記第２のノード識別子であり、ｎが、前記有限投影面の次数である、請求項８に記載の方法。
【請求項１０】
前記第１のノードの第１のブロック識別子が、ｊ1＝ｉ1 ｍｏｄ（ｎ2＋ｎ＋１）に等しく、ここでｊ1が前記ブロック識別子であり、ｉ1が前記第１のノード識別子であり、ｎが前記有限投影面の次数であり、前記第２のノードブロック識別子が前記第１のブロック識別子に等しい場合に、共通のルートを持つ前記鍵材料の前記第１のリスト内の位置ｋ1が、
ｋ1＝｜ｉ1−ｉ2｜／（ｎ2＋ｎ＋１） （ｍｏｄ ｎ＋１）
のように得られる、請求項９に記載の方法。
【請求項１１】
前記方法は、前記第２のノードブロック識別子が前記第１のブロック識別子に等しくない場合に、前記第１のノードが、
ｋ＝｜ｊ2−ｊ1｜／｜ａ2−ａ1｜ （ｍｏｄ ｎ）
を計算するステップを有し、ここでａ2が床関数（ｊ2／ｎ）に等しく、ａ1が床関数（ｊ1／ｎ）に等しい、請求項１０に記載の方法。
【請求項１２】
少なくとも１つの他の通信ノードとネットワークにおいて通信する通信ノードにおいて、
前記通信ノードが、複数の暗号要素を含む暗号要素の第１のリストと、前記他のノードからノード識別子を受信する受信器と、前記他のノード識別子及び当該通信ノード自体の識別子から、前記暗号要素のリストの全体的な組成を生成することなしに、前記他のノードに対応する暗号要素の他のリストの１つの暗号要素と共通のルートを持つ少なくとも１つの暗号要素の前記第１のリスト内の位置を決定し、共通のルートを持つ前記暗号要素を用いて暗号化鍵を生成するコントローラとを有する、
通信ノード。
【請求項１３】
前記の各ノードの対に共通の要素の前記の各リスト内の位置と前記の各ノードの識別子との間に関係が存在する、請求項１２記載の通信ノード。
【請求項１４】
ネットワークにおいて通信する第１のノード及び第２のノードを有する通信システムにおいて、
前記第１のノードが、複数の暗号要素を含む暗号要素の第１のリストを有し、
前記第２のノードが、複数の暗号要素を含む暗号要素の第２のリストを有し、
前記第１のノードが、前記第２のノードから第２のノード識別子を受信する受信器と、前記第２のノード識別子及び前記第１のノード自体の識別子から、前記暗号要素のリストの全体的な組成を生成することなしに、前記第２のリストの１つの暗号要素と共通のルートを持つ少なくとも１つの暗号要素の前記第１のリスト内の位置を決定し、共通のルートを持つ前記暗号要素を用いて暗号化鍵を生成するコントローラとを有する、
通信システム。
【請求項１５】
前記の各ノードの対に共通の要素の前記の各リスト内の位置と前記の各ノードの識別子との間に関係が存在する、請求項１４記載の通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の通信装置を有するネットワークにおいて通信する方法、このような装置、及び複数のこのような装置を有するシステムに関する。より具体的には、本発明は、安全に通信することができるようにネットワークの通信装置に配送される暗号化材料を使用する通信のシステムに関する。
【０００２】
本発明は、例えば、無線センサ及びアクチュエータネットワーク（ＷＳＮ）のようなセンサネットワークに関連し、センサノードは、低電力低コスト装置である。
【背景技術】
【０００３】
センサネットワーク、例えば移動無線センサ及びアクチュエータネットワーク（ＷＳＮ）は、幅広い範囲の応用で使用されている。このようなネットワークのサイズは、数十から数万のノードまで変化することができる。これらの性質は、非常に動的であり、すなわち、ネットワークトポロジは、時間とともに変化しうる。センサノードは、非常にコスト効率が良くなくてはならず、典型的には、バッテリパワー、通信帯域幅、処理パワー、及びメモリ等のような非常に限定されたリソースを持つ。
【０００４】
機密性、認証、インテグリティ及び権限のようなセキュリティサービスは、患者モニタリング又は無線制御ネットワークのような応用により必要とされるので医療的応用及びジグビー（ZigBee）のような応用に必須である。しかしながら、前記ノードのリソース制約性質のため、非対称暗号に基づくセキュリティ方法は、一般に、不十分又は実行不可能と見なされる。したがって、対称暗号が、通常は、所要のセキュリティサービスを可能にするように使用される。しかしながら、対称暗号に対する根本的な問題は、鍵配送（key-distribution）、すなわち、安全に通信する必要のあるノードにおいて共有される秘密をどのように確立するかである。この問題は、動的な性質及び場合により大きなサイズのために、ＷＳＮにおいて特に高位である。
【０００５】
したがって、前記センサノードの各々が展開（deployment）の前に暗号要素のセットを備える鍵配送方法が提案されている。一度前記ノードが展開されると、前記暗号要素は、前記セキュリティサービスが基づく共通秘密を確立することを可能にする。２つの自明な鍵事前配送方法は、最適なスケーラビリティを提供するが、最小の回復力（resilience）を提供する全てのノードにおける同じ対称鍵をロードすること、及び最適な回復力を提供するが、最小のスケーラビリティを提供するノードの可能な対毎に異なる鍵を提供することである。
【０００６】
結果として、これら２つの方法のトレードオフである方法を使用することが提案されている。しかしながら、１つのノードが他のノードと通信することを望む場合、前記他のノードの要素のセットの組成（composition）を計算し、この他のセットをこれ自体の要素のセットと比較することにより、いずれの暗号化要素が両方のノードに共通であるかを発見する必要がある。前記暗号化要素のセット内の異なる暗号化要素の数、及び各ノードに前記暗号化要素を配送する方法に依存して、この共通の暗号化要素の発見するステップは、高い計算パワー及び高いメモリ容量を必要としうる。結果として、この方法は、ノードが低い許容量を持つセンサネットワークには適合されない。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、安全な通信を可能にするネットワーク、特にセンサネットワークにおいて通信する方法を提案することである。
【０００８】
本発明の他の目的は、効率的に共通の暗号化要素を発見することを可能にする安全な通信を有する如何なる種類のネットワークでも通信する方法を提案することである。
【課題を解決するための手段】
【０００９】
このために、本発明による第１のノードと第２のノードとの間のネットワークにおいて通信する方法は、
前記第１のノードが、複数の暗号要素を含む暗号要素の第１のリストを有し、
前記第２のノードが、複数の暗号要素を含む暗号要素の第２のリストを有し、
前記方法が、
ａ）前記第１のノードが、前記第２のノードから第２のノード識別子を受信するステップと、
ｂ）前記第１のノードが、前記第２のノード識別子から、前記第２のリストの１つの暗号要素と共通のルートに基づいて少なくとも１つの暗号要素の前記第１のリスト内の位置を決定するステップと、
ｃ）前記第１のノードが、前記第２のノード識別子及び前記共通のルートを持つ暗号要素を用いて暗号化鍵を生成するステップと、
を有することを特徴とする。
【００１０】
結果として、前記第１のノードは、前記他のノードの暗号要素の完全なセットを構築する必要がなく、前記他のノードの識別子から、いずれの要素が共通のルートに基づくかを推定することができる。例えば、前記暗号要素が暗号化鍵である場合、共通のルートに基づく２つの鍵は等しい。前記暗号要素が鍵材料（keying materials）、すなわち鍵生成器関数である場合、これらは、これらの関数が単一の共通鍵共有（common key share）から決定される場合に共通のルートに基づく。例えば、前記共通鍵ルートは、二変数対称多項式であることができる。
【００１１】
本発明の第二の態様によると、少なくとも１つの他の通信ノードとネットワークにおいて通信する通信ノードが提案され、
前記通信ノードは、複数の鍵材料を含む鍵材料の第１のリストと、前記他のノードからノード識別子を受信する受信器と、前記他のノード識別子から、前記他のノードに対応する鍵材料の他のリストの１つの鍵材料と共通のルートを持つ少なくとも１つの鍵材料の前記第１のリスト内の位置を決定し、前記他のノード識別子及び共通のルートを持つ前記鍵材料を用いて暗号化鍵を生成するコントローラとを有する。
【００１２】
本発明の第３の態様によると、ネットワークにおいて通信する第１のノード及び第２のノードを有する通信システムが提案され、
前記第１のノードが、複数の鍵材料を含む鍵材料の第１のリストを有し、
前記第２のノードが、複数の鍵材料を含む鍵材料の第２のリストを有し、
前記第１のノードが、前記第２のノードから第２のノード識別子を受信する受信器と、前記第２のノード識別子から、前記第２のリストの１つの鍵材料と共通のルートを持つ少なくとも１つの鍵材料の前記第１のリスト内の位置を決定し、前記第２のノード識別子及び共通のルートを持つ前記鍵材料を用いて暗号化鍵を生成するコントローラとを有する。
【００１３】
本発明のこれら及び他の態様は、以下に記載される実施例を参照して説明され、明らかになる。
【００１４】
本発明は、ここで、添付の図面を参照して、例として、より詳細に記載される。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施例によるネットワークである。
【図２】本発明の一実施例による、第１のノードから第２のノードへの安全な通信に対する方法のブロック図である。
【発明を実施するための形態】
【００１６】
本発明は、ネットワークにおいて第１のノードから第２のノードへの安全な通信に対する方法に関する。本発明は、より特別には、例えば患者モニタリングに使用される無線センサ及びアクチュエータネットワーク、例えば患者の身体パラメータを感知するセンサノード、医療スタッフに前記パラメータを提供するレセプタノード及びアクチュエータノードを有するネットワークに対して専用化される。
【００１７】
しかしながら、注意すべきは、本発明が、このようなネットワークに限定されず、如何なる技術的応用に対して使用される如何なるタイプのネットワークにおいても実行されることができることである。
【００１８】
本発明の一実施例による方法は、ここで図１及び２に関連して記載される。
【００１９】
本発明によるネットワークは、少なくとも２つのノードＮ１及びＮ２を有し、各々が、それぞれＩＤ１及びＩＤ２と称される識別子を備える。一実施例において、前記ネットワークは、前記ネットワークの構成に使用され、暗号鍵を生成するために全ての必要な情報をノードＮ１及びＮ２に提供するトラストセンタノードＴＣをも有する。
【００２０】
動作段階中に、前記ネットワークの第１のノードＮ１と第２のノードＮ２との間の通信を保証するために、前記ノードの各々は、共有鍵を生成し、他のノードに送信される通信を符号化するのに、又はこの他のノードから受信する通信を復号するのにこの鍵を使用する。図２は、前記第２のノードと通信するための共有鍵を生成するのに前記第１のノードに対して必要とされる異なるステップを記載する。同様のステップは、前記第１のノードと通信するための対応する共有鍵を生成するために前記第２のノードにより実行されることができる。
【００２１】
この例によると、鍵を生成するために、２つのノードは、鍵材料共有、それぞれＫＭ(ID1)及びＫＭ(ID2)、すなわち、鍵確立を可能にする情報を備えている必要がある。各鍵材料共有は、一般に、前記ネットワークの設定段階又は配送段階の間にトラストセンタＴＣから受信される。前記ノードに与えられた前記鍵材料共有は、前記トラストセンタにのみ知られている暗号情報であるルート鍵材料ＫＭから生成される。この例において、前記ルート鍵材料は、多項式のような二変数関数であり、各鍵材料共有は、一変数関数である。有利には、前記ルート鍵材料は、対称二変数関数である。注意すべきは、本発明の他の例において、前記鍵材料共有が、対称暗号化システムの多変数関数又は暗号化鍵であることである。
【００２２】
上記の方法は、したがって、特定のノードに適用されることを意図されず、前記ネットワークの如何なるノードによっても実行されることができる。
【００２３】
通信が、前記第１のノードと前記第２のノードとの間で確立されるべきである場合、前記第１のノードは、ステップａ）において、前記第２のノードの識別子ＩＤ２を前記第２のノードから受信する。
【００２４】
前記第２のノードと通信するための前記共有鍵を発見するために、前記第１のノードは、ステップｂ）において、前記通信に関与する２つのノードＮ１及びＮ２の暗号要素のそれぞれのリストの共通の要素を決定する必要がある。この場合、ステップｃ）において、ノードＮ１は、例えば前記暗号化要素が上で説明したように一変数関数である場合にＮ２の識別子の助けで計算することにより、この決定された共通要素を持つ鍵を生成する。
【００２５】
実際に、以前に紹介されたように、この種のネットワークにおいて使用されることができるλ回復鍵配送スキームによると、ノードは、既製の鍵を共有しない。代わりに、ノードは、前記ノードが前記ノードの識別子の入力に対して他のノードとの共有鍵を計算することを可能にするノード固有情報を備える。このノード固有情報は、鍵ルート（ＫＲ）から得られ、ノードｉに対するノード固有共有は、ＫＲ(i)により示される。したがって、異なる共有ＫＲ(i)は、全て異なるが、関連している。このアプローチは、(i)無線ノードのリソース制約性質、(ii)ノードの可動性、又は(iii)ジグビー・アライアンスにより取り組まれる患者モニタリング又は無線制御ネットワークのような応用シナリオの低い遅延要件を含む異なる理由のため、移動無線センサ及びアクチュエータネットワークに対して特に関心がある。
【００２６】
本発明の本実施例の方法は、組み合わせ鍵事前配送方法に応用されることができる。これらは、以下のように機能する決定論的対鍵事前配送スキーム（ＤＰＫＰＳ）の基礎を形成する。ＤＰＫＰＳにおいて、１つではなく複数の鍵ルートが生成される。組み合わせ概念は、巧妙に前記ノードに鍵ルート共有の特定のセットを事前配送するのに使用される。この組み合わせ概念は、（ｎプライムを持つ）次数ｎ及びパラメータ（ｎ2＋ｎ＋１，ｎ＋１，１）の有限投影面（ＦＰＰ）であることができ、これは、
−各ブロックが、厳密にｎ＋１の要素を含み、
−各要素が、厳密にｎ＋１のブロックにおいて生じ、
−ブロックの各対が、厳密に１の要素を共通に持つ、
ようにｎ2＋ｎ＋１のブロックに対するｎ2＋ｎ＋１の別個の要素の配置として規定される。
【００２７】
前記要素のセットは、Ｅ＝｛０，...，ｎ2＋ｎ｝により示され、前記ブロックのセットは、Ｂ＝｛Ｂ0，...，Ｂn2+n｝により示され、ここでブロックＢi＝｛ｂi,0，...，ｂi,n｝⊂Ｅである。
【００２８】
前記ＦＰＰの要素は、前記システムにおける異なる鍵ルートＫＲ0，...，ＫＲn2+nに対応する。前記動作段階の前の事前展開において、前記センサノードは、巧妙な配送によって特定のＦＰＰブロックに割り当てられる。ここで、ノードｉ（ｉ∈｛０，１，１，...｝）は、ブロックＢjに割り当てられ、
ｊ≡ｉ（ｍｏｄ  ｎ2＋ｎ＋１）
である。
【００２９】
ノードが備える鍵材料は、特定のブロック内の前記ルートから得られる前記共有からなる。したがって、ノードｉは、鍵材料ＫＭ(i)を得る、すなわち、
ＫＭ(i)＝｛ＫＲbj,0(i)，ＫＲbj,1(i)，...，ＫＲbj,n(i)｝
である。
【００３０】
前記ＦＰＰの規定により、全てのノードが、異なるブロック内にある場合に１つの共通のルートを持ち、又は同じブロック内にある場合にｎ＋１の共通のルートを持つことに注意する。前記ノードが展開された後に、ノードｉ2との共有鍵を確立することを望むノードｉ1は、以下の鍵確立手順、すなわち、
１．ブロック識別子ｊ2≡ｉ2（ｍｏｄ  ｎ2＋ｎ＋１）を決定する、
２．共通ルート発見、すなわち、
a ブロック識別子ｊ2を持つＦＰＰブロック、Ｂj2＝｛ｂj,0，...，ｂj2,n｝を生成する、
b 共通の要素ｂを発見するためにブロックＢj2の要素を（計算労力を節約するように記憶されていてもよい）独自のブロックＢj1の要素と比較する、
c 鍵材料から鍵ルート共有ＫＲb(i1)を取り出す、
３．共有ＫＲb(i1)及び識別子ｉ1から前記鍵を計算する、
を実行する。例えば、一変数多項式であるＫＲb(ｉ1)は、変数として値ｉ2を用いて計算されることができる。ある他の例において、この共有は、ｉ2において各々計算されるサブ多項式に分割され、次いで例えばＸＯＲオペランドと連結又は結合される。前記λ回復スキームの規定により、この鍵は、ノードｉ2が共有ＫＲb(i2)及び識別子ｉ1から計算する鍵に等しい。
【００３１】
以下の表は、パラメータ（７，３，１）を持つｎ＝２次のＦＰＰを表す。第１の列は、ルート｛ＫＲ0，ＫＲ2，ＫＲ4｝に対応するブロックＢ0を表し、第２の列は、ルート（ＫＲ1，ＫＲ3，ＫＲ4）に対応するブロックＢ1を表し、以下同様である。巧妙な配送によると、ノードｉ（ｉ∈｛０，１，２，...｝）は、ブロックＢjに割り当てられ、
ｊ≡ｉ（ｍｏｄ  ｎ2＋ｎ＋１）
である。
【表１】
0005637990.tif 000002
【００３２】
例えば、ノード８は、ブロックＢ1に割り当てられ、したがって、ＫＭ(8)で示される鍵材料は、共有のセットにより与えられ、
ＫＭ(8)＝｛ＫＲb1,0(8)，ＫＲb1,1(8)，ＫＲb1,2(8)｝＝｛ＫＲ1(8)，ＫＲ3(8)，ＫＲ4(8)｝
である。
【００３３】
ノード８が、ノード１４との鍵を確立することを望む場合、鍵確立手順に従う。
１．ブロック識別子ｊ≡１４（ｍｏｄ  ｎ2＋ｎ＋１）、したがってｊ＝０を決定する。
２．共通ルート発見、すなわち、
a ＦＰＰブロックＢ0＝｛１，３，４｝を生成する。
b 共通の要素ｂ＝４を発見するためにＢ0＝｛０，２，４｝を独自の（記憶された）ＦＰＰブロックと比較する。
c 鍵材料ＫＭ(8)から共有ＫＲ4(8)を取り出す。
３．共有ＫＲ4(8)及び識別子１４から前記鍵を計算する。
【００３４】
例えば組み合わせ鍵事前配送方法においてこのスキームを用いる主な問題の１つは、前記鍵確立手順のステップ２、すなわち、２つのＦＰＰブロックにおける共有される要素の発見である。限定的なリソースのため、この発見は、可能な限り効率的に行われるべきであり、すなわち、最小量の計算労力、メモリ及びコードサイズを要求する。
【００３５】
最新技術の方法は、上記のように、すなわち、前記ＦＰＰブロックの要素を生成し、共通の要素を見つけるために独自のＦＰＰブロックと比較し、前記鍵材料から対応する共有を取りだすことにより進行する。代替例は、ノードが、前記ノード識別子に加えてＦＰＰブロックの要素をも送信することであることができるが、これは、結果として高い通信オーバヘッド及び認証問題を生じる。
【００３６】
本発明の本質的なアイデアは、前記共有されるＦＰＰ要素の値が無関係である−それぞれのＦＰＰブロック内の位置のみが必要とされるという洞察に基づく。したがって、ＦＰＰブロック全体を計算し、独自の（記憶された）ブロックと比較する代わりに、ノードは、前記ブロック内の前記共有される要素の位置、したがって鍵材料内の前記共有される鍵ルートの位置を、前記ブロック識別子から直接的に計算することができる。
【００３７】
以下に、暗号要素の各セットの共通の要素の位置が前記ノードの識別子にリンクされるように前記ＦＰＰを生成する可能な方法の１つが記載される。この方法は、前記ブロック内の前記共有される要素の位置と前記それぞれのブロック識別子との間の代数関係を確立するように設計される。この場合、動作段階において、これらの関係は、前記ブロック識別子から前記位置を直接的に算出する方法を規定するのに使用される。
【００３８】
この方法により必要とされる計算労力及びコードサイズは、通常のＦＰＰブロックの生成と比較可能である。したがって、現在の方法と比較して、この方法は、前記ブロックを比較し、共通の要素を選択するのに必要とされる計算労力及びコードサイズを節約する。更に、この方法は、追加のメモリ要件を持たない。これは、ノードが独自のＦＰＰブロックの要素を恒久的に記憶し、他のノードのものを一時的に記憶する、以前に記載された方法と対照的である。
【００３９】
ｎプライムに対してパラメータ（ｎ2＋ｎ＋１，ｎ＋１，１）を持つＦＰＰを生成するために、いずれの要素がいずれのブロックに含まれるべきであるかを規定するのを助ける相互直交ラテン方陣（ＭＯＬＳ）のセットを使用することが提案された。この手順は、ブロックのより便利なインデックス付け及び配置を規定し、これらのブロックの生成に対する具体的な式を指定するように構成されている。結果として、これは、これらのブロック内の共有される要素の位置及びブロック識別子の対の間の明確に定義された関係を確立する。これらの以前には欠けていた関係は、この場合、前記ＦＰＰブロックを生成及び比較する必要なしに、これらの位置を直接的に決定する方法を指定するのに使用される。
【００４０】
前記ＦＰＰの生成に対して、前記展開段階において、ｎプライムに対して、ｎ×ｎ行列Ｍ、すなわち、
【数１】
0005637990.tif 000003
が規定される。
【００４１】
Ｍの行及び列は、０ないしｎ−１までインデック付けされ、したがって、Ｍの要素は、
Ｍi,j＝ｉ・ｎ＋ｊ  （０≦ｉ，ｊ≦ｎ−１）
により決定される。
【００４２】
０ないしｎ−１までインデックス付けされた０≦ａ≦ｎ−１に対するｎ×ｎ行列Ｌ(a)を、
Ｌ(a)k,l＝（ａ・ｋ＋ｌ）mod n  （０≦ｋ，ｌ≦ｎ−１）
により規定する。
【００４３】
ｎ＝３に対する応用的な例において、行列、
【数２】
0005637990.tif 000004
を持つ。
【００４４】
Ｂj＝｛ｂj,0，...，ｂj,n｝⊂｛０，...，ｎ2＋ｎ｝であるＦＰＰブロックＢ0，...，Ｂn2+nの構築は、以下のように規定される。
・０≦ｊ≦ｎ2−１及び０≦ｋ≦ｎ−１に対して、要素ｂj,kは、行列Ｍから値を選ぶ。特に、インデックスｋは、Ｍの行番号を示すのに対し、値Ｌ(a)k,lは、列番号を示し、ここでｌ＝ｊ（ｍｏｄ  ｎ）及び
0005637990.tif 000005
であり、ここで、
0005637990.tif 000006
は、床関数オペレータであり、ｎ≦ｘ＜ｎ＋１に対して、ｎを返す。したがって、
・０≦ｊ≦ｎ2−１及び０≦ｋ≦ｎ−１に対して、
【数３】
0005637990.tif 000007
である。
・ｎ2≦ｊ≦ｎ2＋ｎ−１及び０≦ｋ≦ｎ−１に対して、要素ｂj,0，...，ｂj,n-1は、Ｍの行により形成され、したがって、
ｂj,k＝Ｍj,k＝（ｊ−ｎ2）ｎ＋ｋ
である。
・０≦ｊ≦ｎ2＋ｎ及びｋ＝ｎに対して、要素ｂj,kは、
【数４】
0005637990.tif 000008
により規定される。
・ｊ＝ｎ2＋ｎ及び０≦ｋ≦ｎに対して、要素ｂj,kは、
ｂj,k＝ｎ2＋ｋ
により規定される。この構築は、以下の式により記述されることができる。
【数５】
0005637990.tif 000009
前記位置の直接的な計算のため、このＦＰＰ構築が、前記ノードにより実行される必要が無いことに注意する。代わりに、これらの関係は、前記ＦＰＰブロック識別子から共通の要素の位置を直接的に計算するのに使用されることができる。前記ノードに前記鍵材料を事前配送するパーティのみが、完全なＦＰＰを計算しなくてはならない。
【００４５】
ｎ＝３に対して、前記構築は、以下の表に描かれたＦＰＰを生じる。
【表２】
0005637990.tif 000010
【００４６】
前記要素が０≦ｊ≦ｎ2−１及び０≦ｋ≦ｎ−１に対して選択される方法を説明するために、例えば、列ｊ＝５を検討する。０≦ｋ≦ｎ−１に対して、要素ｂj,kは、行番号ｋ及び値Ｌ(a)k.lに等しい列番号を持つＭ内の値を獲得する。ここで、
0005637990.tif 000011
及びｌ＝ｊ（ｍｏｄ  ｎ）＝２であるので、Ｍに対する列番号は、行列Ｌ(l)内の列２により与えられ、したがって２、０及び１である。したがって、値ｂ5,0、ｂ5,1及びｂ5,2は、それぞれＭの列２、０及び１から取られる。したがって、以下に見られるように、｛ｂ5,0，ｂ5,1，ｂ5,2｝＝｛２，３，７｝である。
【数６】
0005637990.tif 000012
【００４７】
識別子ｉ1を持つノードは、ブロック識別ｊ1＝ｉ1 ｍｏｄ（ｎ2＋ｎ＋１）及び補助パラメータ
0005637990.tif 000013
を一回計算し、記憶する。以前とは異なり、ノードｉ1がＦＰＰブロック全体を計算及び記憶する必要はない。他のノードｉ2と共有される鍵を確立するために、前記ノードは、ｊ2＝ｉ2 ｍｏｄ（ｎ2＋ｎ＋１）及び
0005637990.tif 000014
を計算する。前記鍵材料におけるノードｉ1及びｉ2の位置ｋ1及びｋ2をそれぞれ決定するために、以下の５つの場合を区別することができる（一般性を失うことなしに、ｊ1≦ｊ2を仮定する）。
【００４８】
１．ｊ1＝ｊ2。この場合、前記２つのノードは、同じＦＰＰブロックを共有し、前記ブロック内の如何なる要素も選ばれることができる。常に同じ要素（例えば第１の要素）を選ぶことは、セキュリティを低減させる。したがって、前記選択された要素は、前記ノード識別子に依存し、ｎ＋１の要素にわたり一様に分布し、両方のノードに対して直接的に計算可能であるべきである。これは、
【数７】
0005637990.tif 000015
をセットすることにより達成される。
【００４９】
規定により、ｊ1＝ｊ2が、｜ｉ1−ｉ2｜がｎ2＋ｎ＋１により除算可能であり、したがってこの除算が、モジュラー演算を必要としないので、安価な演算であることに注意する。
【００５０】
２．ｊ1≠ｊ2及びａ1＝ａ2。この場合、ａ1及びａ2は、ｎに等しいことができず、そうでなければｊ1がｊ2に等しい。したがって、０≦ｊ1，ｊ2≦ｎ2＋ｎ＋１であり、結果的に、
【数８】
0005637990.tif 000016
である。
【００５１】
したがって、前記共通の要素は、両方のブロックにおいて位置ｎにあり、したがってｋ1＝ｋ2＝ｎである。
【００５２】
３．ａ1＜ａ2＝ｎ＋１。この場合、ｊ2＝ｎ2＋ｎであり、全てのｋ2に対して、ｂj2,k2＝ｎ2＋ｋ2と書くことができることは、容易に検証されることができる。更に、ｋ2＝ａ1に対して、
【数９】
0005637990.tif 000017
であることがいえる。
【００５３】
したがって、前記共通の要素は、ブロックＢj1内の位置ｋ1＝ｎ及びブロックＢj2内の位置ｋ2＝ａ1に位置する。
【００５４】
４．ａ1＜ａ2＝ｎ。この場合、０≦ｊ1≦ｎ2−１及びｎ2≦ｊ2≦ｎ2＋ｎ−１である。構築により、ｊ2−ｎ2が、ブロックＢj2の最初のｎの要素、すなわちｂj2,0，...，ｂj2,n-1を規定するＭの行を示すことに注意する。０≦ｊ1≦ｎ2−１に対して、ブロックＢj1の最初の要素は、Ｍの最初の行から来て、二番目の要素は第二行から来て、以下同様であるので、ｋ1＝ｊ2−ｎ2であることを見つける。更に、Ｌ(a)k1,l＝（ａ1・ｋ1＋ｌ）mod n＝（ａ1・ｊ2＋ｊ1）mod nにより与えられる特定の要素のＭ内の列番号は、Ｂj2内の当該要素の位置ｋ2を示す。ｋ1＝ｊ2−ｎ2及びｋ2＝（ｊ1＋ａ1ｊ2）mod nに対して、
【数１０】
0005637990.tif 000018
であることを見つける。
【００５５】
５．ａ1＜ａ2＜ｎ。ｋ1＝ｋ2＝（（ｊ2−ｊ1）／（ａ1−ａ2））mod nに対して、ａ1ｋ1＋ｊ1＝ａ2ｋ2＋ｊ2（ｍｏｄ  ｎ）である。
【００５６】
この場合、
ｂj1,k1＝ｋ1ｎ＋（ｋ1ａ1＋ｊ1）mod n＝ｋ2ｎ＋（ｋ2ａ2＋ｊ2）mod n＝ｂj2,k2である。
【００５７】
したがって、この場合、前記位置は、
ｋ1＝ｋ2＝（（ｊ2−ｊ1）／（ａ1−ａ2））mod n
により与えられる。
【００５８】
これは、比較的高価なモジュラー減算が前記位置を計算するのに必要とされる唯一の場合である。この計算は、等式
（ａ1−ａ2）ｋ＝ｊ2−ｊ1 （ｍｏｄ  ｎ）
に対してｋ＝０，１，２，...を試みることにより実行されることができる。
【００５９】
上記のことは、ノードｉ1及び他のノードｉ2に対するＦＰＰブロック内の共通の要素の位置の検出に対する以下のアルゴリズムに要約されることができる。ここで、ノードｉ1が、既に計算されており、ブロック識別子ｊ1＝ｉ1 ｍｏｄ（ｎ2＋ｎ＋１）及び補助変数
0005637990.tif 000019
を記憶していると仮定する。
・ｊ2＝ｉ2 ｍｏｄ（ｎ2＋ｎ＋１）及び
0005637990.tif 000020
を計算する。
・Ａ＝ａｒｇｍｉｎ（ｊ1，ｊ2）及びＢ＝ａrｇｍａｘ（ｊ1，ｊ2）をセットする。
・ｊA＝ｊBの場合、ｋA＝ｋB＝（｜ｉA−ｉB｜／（ｎ2＋ｎ＋１））（ｍｏｄ  ｎ＋１）。
・さもなければ、ａA＝ａBの場合、ｋA＝ｋB＝ｎ。
・さもなければ、ａB＝ｎ＋１の場合、ｋA＝ｎ及びｋB＝ａA。
・さもなければ、ａB＝ｎの場合、ｋA＝ｊB−ｎ2及びｋB＝ｊA＋ａA・ｊB （ｍｏｄ  ｎ）。
・さもなければ、ｋA＝ｋB＝（（ｊB−ｊA）／（ａA−ａB）） （ｍｏｄ  ｎ）。
【００６０】
本発明のこの実施例は、患者モニタリング及び分散型無線制御ネットワークに対するリソース制約無線ノードにおいてセキュリティをブートするのに使用されるλ安全鍵配送スキームの性能を向上させる重要な特徴としてジグビーネットワークにおいて応用を見つける。加えて、この実施例は、有限投影面（ＦＰＰ）に基づく組み合わせ配送の計算を必要とするシステムの性能を向上させるのに使用されることもできる。
【００６１】
ＦＰＰの他のアルゴリズム又は規定は、ノードの対に共通の要素のリスト内の位置とこれらの識別子との間に関係が存在する限り使用されることができる。
【００６２】
ＷＳＮは、環境モニタリング（例えば氷河、火事）、計測、商業ビルディング自動化又は患者モニタリングを含む多数の潜在的な応用を持つ。これらのＷＳＮ応用に対して共通の相互利用可能なプロトコルを提供するために、ジグビー・アライアンスは、ＷＳＮノードに対して、新しい低データレート、長いバッテリ寿命、及び安全なプロトコルを開発している。
【００６３】
本明細書及び請求項において、要素に先行する単語"１つの"（"a"又は"an"）は、複数のこのような要素の存在を除外しない。更に、単語"有する"は、記載された要素又はステップ以外の要素又はステップの存在を除外しない。
【００６４】
本開示を読むことにより、他の修正例は、当業者に明らかである。このような修正例は、無線通信の分野及び送信器パワー制御の分野において既知であり、ここに既に記載されたフィーチャの代わりに又は加えて使用されることができる他のフィーチャを含むことができる。
【図１】
0005637990.tif 000021
【図２】
0005637990.tif 000022