ネットワークにおけるセキュア通信に関する方法、通信デバイス、ネットワーク及びコンピュータプログラム
ルート鍵材料を具備する管理デバイス２を有するネットワークにおける第１のノードＮ１と第２のノードＮ２との間の通信を安全に行う方法が、ルート鍵材料に基づき、多数のサブエレメントを有する第１のノードの鍵材料共有物を上記管理デバイスが生成するステップであって、上記第１のノードの鍵材料共有物が、第１の完全な鍵を生成するよう構成される、ステップと、上記管理デバイスが、上記第１の鍵材料共有物のサブエレメントのサブセットを選択するステップであって、上記選択されるサブエレメントの数が、上記第１の鍵材料共有物のサブエレメントの総数以下であり、上記選択されたサブエレメントが、第１のノードの部分的な鍵材料共有物又は対称鍵生成エンジンを形成する、ステップと、上記第１のノードの対称鍵生成エンジン及び上記第２のノードの識別子に基づき、上記第２のノードとの通信を安全に行うのに使用される第１の鍵を上記第１のノードが生成するステップとを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セキュア通信に関する方法、及び通信を安全に行うための暗号化システムといったセキュア手段を用いる通信デバイスを持つ通信ネットワークに関する。本発明は、例えば携帯型ワイヤレスセンサ及びアクチュエータネットワーク（ＷＳＮ）といった通信ネットワークにおいて、より詳細には、患者監視のための医療無線ネットワーク、又は例えば照明環境ネットワーク、ビル自動化ネットワーク、車載装置ネットワークといった他のパーソナルネットワークにおいて、有利な用途を見いだす。
【背景技術】
【０００２】
これらのセンシティブな用途のため、ネットワーク等は、秘密性、認証（authentication）、完全性及びアクセス権限（authorization）といったセキュリティサービスを具備しなければならない。
【０００３】
従来の通信ネットワークにおいて使用される暗号化システムは通常、通信を安全に行うための暗号方法に基づかれるセキュリティサービスを可能にする。暗号方法は、その処理のため暗号鍵を必要とする。
【０００４】
より詳細には、通信相手又はノードを有し、非常にコスト効率が良くなければならないいくつかのネットワークでは通常、必要なセキュリティサービスを可能にするため対称性暗号が適用される。実際、無線センサネットワークのようなネットワークにおいて、ノードは通常、バッテリーパワー、通信帯域幅、処理パワー又はメモリの点で、リソースが制限されている。非対称暗号に基づかれるセキュリティ方法は従って、斯かるノードでは非効率的又は実現不可能と一般には考えられる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
対称性暗号における基本的な問題は、鍵配布にある。即ち、ネットワークに属し、安全に通信しなければならないノードにおける共有される秘密の確立にある。この問題は、ＷＳＮにおいて特に顕著である。なぜなら、それらのサイズは十から数万ノードまで変化することができ、それらの性質は非常に動的であるからである。例えば、ネットワークトポロジが先験的に知られるということができない。
【０００６】
暗号鍵は、公開鍵暗号法、鍵配布センター又は他の対称性技術に基づかれる異なる方法を用いて、関係する通信相手の間で分散及び確立される。特に、最近、センサネットワークに対する鍵配布方式の設計に関する調査が実施された。ランダム鍵事前配布方式、トラストセンターベースの鍵配布方式又は公開鍵暗号法の適用が提案されている。それらの方式の多くにおいて、セキュリティとパフォーマンスとの間のトレードオフが存在する。例えば、ランダム鍵事前配布方式は、Ｍ個の鍵のプールからランダムに選択されるＷ個の鍵をＷＳＮにおける各ノードに配布する。こうして、２つノードは、Ｗ及びＭに依存して、共通の鍵を共有する確率ｐを持ち、セキュア通信リンクを確立することができる。しかしながら、これらの方式は、ノード及び格納された鍵をキャプチャすることにより破られることができる。また、これは比較的多数の鍵の格納を必要とする。例えば、５０〜２００の間であり、１００ビットの鍵に対して５００〜２０００バイトに等しい。公開鍵ベースの鍵合意方式は、単一の鍵の格納で済むが、鍵生成に関するアルゴリズムはかなり複雑である。その上、このシステムは計算的な観点から言えば更に遅い。なぜなら、鍵合意ハンドシェイク手順のため数秒が必要とされるからである。従来の鍵配布方式の中には、αセキュアと呼ばれる鍵材料共有物配布方式を取るものがある。その場合、ネットワークに属するノードは、レディーメードの暗号鍵を直接具備するのではなく、通信を安全に行うためこのネットワークの別のノードと共有される鍵を計算することを可能にするあるノード特有の鍵材料を具備する。このノード特有の情報は、ネットワークの管理デバイスに含まれるルート鍵材料から得られる鍵材料共有物である。これらのαセキュア方式は、パフォーマンス、可用性及びセキュリティ間のトレードオフを提供する。それらのシステムの主な欠点は、αノードのキャプチャ、従ってα鍵材料共有物の組合せのキャプチャがルート鍵材料全体を危うくする性質をルート鍵材料が持つという事実にある。
【０００７】
本発明の目的は、上述した欠点を解決し、従来の鍵配布方式のパフォーマンスを増加させる、ネットワークにおける通信を安全に行う方法を提案することにある。
【０００８】
本発明の別の目的は、任意の数のノードがキャプチャされてもネットワークが危険にならないネットワークを提供することである。
【０００９】
本発明の更に別の目的は、ネットワークのノードに関するリソース要件を最小化しつつ、従来のαセキュア鍵配布方式より非常に高いセキュリティレベルを実現する効果的な鍵配布を確立することである。
【課題を解決するための手段】
【００１０】
このために、本発明は、対称鍵生成エンジン（ＳＫＧＥ）を具備する管理デバイスを有するネットワークにおいて第１のノードと第２のノードとの間の通信を安全に行う方法を提供する。対称鍵生成エンジン
は、３つの望ましい処理特性を用いて、第１の通信相手アリスが、ネットワークにおける他の任意の通信相手、例えば、ボブとのペアワイズ鍵を生成することを可能にする暗号ブロックである。まず、本発明は、鍵合意のための非対称ハンドシェイクより計算的に非常に効率的である。第２に、この鍵生成エンジンは、非常に効率的な態様で格納されることができる。即ち、本発明は、トリビアルな対称鍵分布方式のＮ−１の鍵と比較されるとき、数バイトのストレージで済む。第３に、このエンジンは、破られることが困難である。
【００１１】
一般性のため、エンティティ
、例えばノードのＳＫＧＥを、他の通信相手の識別子が与えられるとき、システムにおける他の任意のエンティティ
での対称鍵の高速かつ効率的な生成をエンティティ
が行うことを可能にする構造として定める。エンティティ
のＳＫＧＥは、同じ秘密鍵材料
に基づかれる。この秘密情報は、ｎの独立した鍵材料共有物
から生成される鍵材料
のセットのｎ個の組合せである。異なるエンティティ
に関する鍵材料共有物
が、いくつかのルート鍵材料
から生成される。
【００１２】
ルート鍵材料
及び鍵材料共有物
は例えば、暗号において使用される既知の数学関数に基づかれる。これらの数学関数は、多項式、行列、組合せ構造等を含むことができる。数学演算は、例えば群（group）、体（field）、環（ring）、ベクトル空間等を含む代数構造といった任意の有限体又は他の数学的構造にわたり実行されることができる。
【００１３】
ＳＫＧＥの処理は、
管理デバイスが、ルート鍵材料、例えば、多項式のルート鍵材料と、第１のノードの識別子とに基づき、例えば第１の多項式の下で、第１のノードに関する鍵材料共有物のセットを生成するステップであって、各第１の鍵材料共有物が、サブエレメントに分割される、ステップと、
管理デバイスが、上記第１の鍵材料共有物のサブエレメントのサブセット、例えば多項式の係数を選択するステップであって、各第１の鍵材料共有物に対して選択されるサブエレメントの数が、上記第１の鍵材料共有物のサブエレメントの総数以下であり、上記選択されたサブエレメントが、第１のノードの部分的な鍵材料共有物又は対称鍵生成エンジンを形成する、ステップと、
管理デバイスが、第１のノードの部分的な物質共有物を第１のノードに送信するステップと、
上記第１のノードの部分的な鍵材料共有物又は対称鍵生成エンジンと上記第２のノードの識別子とに基づき、上記第２のノードとの通信を安全に行うのに使用される第１の鍵を上記第１のノードが生成するステップとを有する。
【００１４】
対称鍵生成エンジンに関する斯かる方法は、鍵配布方式の弾力性を増加させる。なぜなら、ノードは、第１のノードの鍵材料共有物の一部のみを具備し、従って、多数のノードがキャプチャされたとしても、攻撃者は、最初のルート鍵材料を取得することができないからである。
【００１５】
その上、対称鍵生成エンジンは、例えば、異なる有限体にわたり実行される、異なるルート鍵材料の混合処理から生成される異なる鍵材料共有物から生じる多数の要素を結合することができる。
【００１６】
追加的なセキュリティ機能は、異なる複雑さの鍵材料共有物及びルート鍵材料共有物を用いて、設定可能なセキュリティレベルを参照する。例えば、ルート鍵材料が多項式である場合、選択される多項式の次数は、計算的複雑さとセキュリティとの間のトレードオフを提供するために用いられることができる。
【００１７】
更に、ノードは、より少ない数の要素を具備し、こうしてより少ないビット数を具備するので、これらの要素を格納するためのメモリ要件は最小化され、部分的な鍵を生成するための計算要件も減らされる。
【００１８】
別の実施形態では、ルート鍵材料は、対称性の二変量多項式である。第２のノードが、第１のノードの鍵材料共有物と同じ態様で計算される部分的な鍵材料共有物を具備し、これに従って第２の部分的な鍵を生成する場合、斯かる特性は、この第２の鍵が第１の鍵に等しいことをもたらす。
【００１９】
本発明の更に別の実施形態において、ルート鍵材料は、有限体ＧＦ（ｑ）ｎにおける係数を持つ次数１の多項式である。ここで、ｑｎは２ｎ−１に等しい素数である。ｎは整数である。
【００２０】
別の実施形態では、エンティティの対称鍵生成エンジンは、異なる次数で異なる有限体にわたる多数の二変量多項式から生成される多数の多項式の共有物から生じる要素を結合することにより設計される。多項式の共有物の実際の生成が、対応する体で実行されるという態様で、組合せが実行される。しかし、対称鍵生成エンジンは、そうした体全てに共通する要素及び処理を結合する。
【００２１】
本発明の別の側面は、ノードを有するネットワークにおいてルート鍵材料を具備する管理デバイスに関する。この管理デバイスは、
上記ノードの識別子を受信するとき、上記ルート鍵材料に基づき、ノード鍵材料共有物を生成する手段であって、各鍵材料共有物が、サブエレメントに分けられる、手段と、
対称鍵生成エンジンの設計に関する第１の鍵材料共有物のサブエレメントのサブセットを選択する手段であって、各鍵材料共有物から選択される上記サブエレメントの数が、第１の鍵を生成するよう構成されるノードの部分的な鍵材料共有物を形成するよう、このサブ識別子のサブエレメントの総数以下である、手段と、
上記ノードの部分的な鍵生成共有物を上記ノードに配布する手段とを有する。
【００２２】
本発明の別の側面は、上記の管理デバイスと通信デバイスとを有するネットワークシステムに関する。この通信デバイスは、識別子及び対称鍵生成エンジンを具備する。このシステムは、
上記管理デバイスに上記識別子を送信する手段と、
上記管理デバイスから、ノードの部分的な鍵材料共有物を受信する手段と、
上記別のノードの識別子を受信する手段と、
上記受信した対称鍵生成エンジン又はノードの部分的な鍵材料共有物と、上記受信した他のノードの識別子とに基づき、上記他のノードとの通信のための鍵を生成する手段とを有する。
【図面の簡単な説明】
【００２３】
【図１】管理デバイス及び２つのノードを有する本発明によるネットワークを表す図である。
【図２】基本的な対称鍵生成エンジンに関する本発明による方法のシーケンスを示すブロック図である。
【図３】基本的な対称鍵生成エンジンにおける従来の鍵生成処理を示す図である。
【図４ａ】本発明による鍵生成処理を示す図である。
【図４ｂ】本発明による別の鍵生成処理を示す図である。
【図４ｃ】２つの異なる有限体にわたり２つの異なる二変量多項式から生成される２つの多項式の共有物から選択されるサブエレメントが、エンティティＲの対称鍵生成エンジンを作成するために結合される本発明の実施形態を示し、モジュラー乗算に関連付けられる要素だけを表す図である。
【図５】二変量多項式の次数がルート鍵材料として使用されるとき、ＳＫＧＥのいくつかのサブエレメントの生成に関係するルート鍵材料のビットを表す図である。
【発明を実施するための形態】
【００２４】
本発明のこれら及び他の側面が、以下に説明される実施形態から明らかとなり、これらの実施形態を参照して説明されることになる。
【００２５】
本発明が、以下、添付の図面を参照して、例を用いて、より詳細に説明されることになる。
【００２６】
本発明は、ネットワークにおける通信を安全に行う方法に関する。斯かる方法の例示的な動作シークエンスが、本発明によるネットワークを示す図１及びネットワークの動作シークエンスのブロック図を示す図２と共に説明されることになる。図２は、基本的な対称鍵生成エンジンの設計において使用されるいくつかの例示的な要素を含む。
【００２７】
このネットワークは、構成フェーズＣＯＮＦＩＧの間ルート鍵材料を具備する管理デバイス２を有する。ある例示的な実施形態では、ルート鍵材料は、有限体ＧＦ（ｑ）における係数を持つ次数１の対称性の二変量多項式Ｆ（ｘ、ｙ）である。この多項式は、Ｆ（ｘ，ｙ）＝ａ００＋ａ０１ｘ＋ａ１０ｙ＋ａ１１ｘｙのように記述されることができる。ここで、ａ０１＝ａ１０である。
【００２８】
ある実施形態において、体ＧＦ（ｑ）の特性は、素数のメルセンヌ数ｑｎ＝２ｎ−１であり、ここで、ｎは、例えばｎ＝１７、１２７又は５２１といった整数である。
【００２９】
この構成フェーズＣＯＮＦＩＧの間、ネットワークの各ノード（Ｎ１、Ｎ２）は、識別子（ＩＤ１、ＩＤ２）をそれぞれ具備する。それらの識別子は、ｒビット長である。ここで、ｒはｎより少ない整数である。ある例において、ｒは、ｎ／３の整数部に等しい。この構成フェーズは一般に、ネットワークの事前配備フェーズの間に、即ちノードが実際にネットワークに参加する前に発生する。
【００３０】
一旦ノードが配備されると、管理デバイスは、ＧＥＮＥＲフェーズの間、ルート鍵材料Ｆ（ｘ，ｙ）と識別子ＩＤ１とに基づき、ノードＮ１に関する完全な鍵材料共有物を生成する。ノードＮ１に関する完全な鍵材料共有物は、
であり、ここで、この多項式の係数は、以下の
及び
として計算される。斯かる方法において実行される他の全ての処理同様、これらの処理はｑを法として（modulo q）実行される。なぜなら、このシステムは、有限体ＧＦ（ｑ）にわたり実行されるからである。
【００３１】
ここで、従来の方法による鍵生成処理を簡単に説明する。その後、ＳＫＧＥに基づかれる本発明の改良を説明する。
【００３２】
斯かる従来の処理は、図３を参照して、以下の設定で説明されることになる。
【００３３】
−管理デバイスにおいて与えられるルート鍵材料は、Ｆ（ｘ，ｙ）＝ａ００＋ａ０１ｘ＋ａ１０ｙ＋ａ１１ｘｙである。これは、式Ｆ（ｘ，ｙ）＝（ａ００＋ａ０１ｘ）＋（ａ１０＋ａ１１ｘ）ｙと因数分解されることができる。
【００３４】
−Ｆ（ｘ，ｙ）の係数は、連結される３つのセグメントの式の下で表される。
【００３５】
−このネットワークは、２つのノードを有し、その識別はＲ及びＶである。
【００３６】
第１のステップは、ｘ＝ＲにおいてＦ（ｘ，ｙ）を評価することにより、ノードＲに関する鍵材料共有物を生成することにある。これは、
を生成する。
【００３７】
この評価は、図３の上部に示され、ここで、
−上部左側では
の計算となり、及び
-上部右側では
の計算となる。
【００３８】
その後、従来のシステムにおいて、管理デバイスにより生成される完全な鍵材料共有物は、Ｒノード、即ち６つのセグメント
に送信される。
【００３９】
ノードＲとノードＶとの間で通信が確立されなければならないとき、識別子Ｖが、ノードＲに与えられる。その結果、このノードは、通信を安全に行うための完全な鍵を生成することができる。この鍵は、両方のノードが合意するペアワイズ鍵である。これは、ｙ＝ＶにおいてノードＦＲ（ｙ）の鍵材料共有物を評価することにより計算される。この計算は、図３の下部に示される。計算
は、３つの連結されたセグメントＫ１、Ｋ２及びＫ３を含む鍵Ｋを与える。
【００４０】
要素Ｗ１及びｚ１はキャリーに対応し、有限体のサイズに依存する。
【００４１】
斯かる従来のシステムにおいて、ノードの完全な鍵材料共有物のすべてのセグメントが、このノードに送信される。従って、多数のノードがキャプチャされる場合、攻撃者はルート鍵材料及び従ってシステム全体の安全性を低下させることができる。今の例の場合、２つのノードがキャプチャされれば、ルート鍵材料を危うくするのに十分である。なぜなら、次数１の多項式が使用されるからである。
【００４２】
次に、図２及び図４を参照して、他の欠点の中でもこのセキュリティ問題を解決するために本発明により提案される改良を説明する。
【００４３】
図２の動作シークエンスに戻り、ＩＤ１を用いてノードＮ１の完全な鍵材料共有物を生成した後、管理デバイスは、ＳＥＬＥＣＴステップにおいて、部分的な鍵材料共有物を生成するため、異なる係数のいくつかのセグメントを選択する。
【００４４】
サブエレメントとも呼ばれるそれらのセグメントが、完全な鍵の一部の生成を可能にするように選択される。こうして、ある例示的な実施形態において、管理デバイスは、図４における太い正方形で示される以下の係数
だけをノードＮ１に配布する。部分的な鍵材料共有物を形成するそれらの要素が、ノードＮ１にその後配布される。
【００４５】
その後、ノードＮ１とＮ２との間で通信が確立されなければならないとき、識別子ＩＤ２がＮ１に送信され、鍵生成処理（ＫＥＹ＿ＧＥＮ）が実行される。図４から分かるように、
だけを具備しているので、ノードＮ１は、すべての鍵要素Ｋ１、Ｋ２及びＫ３を計算することはできないが、鍵Ｋ３の最上位ビットを生成することができる。読者は、係数の異なる部分と実行されるモジュラー処理との関係を分析することにより、これを理解することができるであろう。部分的な鍵Ｋ３はその後、ノードＮ１とノードＮ２との間の通信を暗号化するために使用される。
【００４６】
同様に、管理デバイスは、ある実施形態において、ルート鍵材料共有物と第２のノードの識別子とに基づき、第２のノードの鍵材料共有物も生成する。この第２のノードの鍵材料共有物は、第２の多項式の形式下にあり、第１の係数と同じ数の係数を持つ。第２の鍵材料共有物は、第２の完全な鍵を生成するために構成される。この第２のノードの鍵材料共有物の第２の多項式の係数は、第１の多項式の係数と同様に分割される。即ち各係数は３つのサブエレメントに分けられる。その後、管理デバイスは、第２のノードの部分的な鍵材料共有物を形成し、それを第２のノードに送信するため、第２の多項式の係数のいくつかのサブエレメントを選択する。
【００４７】
第２の多項式の係数に関して選択されるサブエレメントは、第１のノードの部分的な鍵材料共有物を形成するために選択されるサブエレメントに対応する。この文脈において、「対応する要素」という用語は、同じ位置にあるサブエレメント
を意味し、これは、第１の係数の第３の要素及び第２の係数の第１及び第３の要素を表す。
【００４８】
第２のノードの鍵材料共有物と第１のノードの識別子とに基づき、第２のノードは、第１のノードとの通信を安全に行うのに使用される第２の部分的な鍵を生成する。ルート鍵材料が対称性の多項式であり、対応するサブエレメントが第１のノードの部分的な鍵材料共有物及び第２のノードの鍵材料共有物から選択されるので、第２の部分的な鍵は、第１の部分的な鍵に等しい。更に、この第２の部分的な鍵は、第２の完全な鍵の一部である。
【００４９】
この実施形態は、結果として生じる鍵の最上位ビットだけを使用する点に留意されたい。即ち、単純な対称鍵生成エンジンの本実施形態を用いる２つの通信相手は、Ｋ３の最上位ビットについてのみ合意することができる。これは、この処理が「元の体ＧＦ（ｑ）の外で」実行され、情報の一部が失われるからである。特に、両方の通信相手とも、鍵生成フェーズにおけるキャリーの効果を含むよう、任意の情報を格納するものではない。しかしながら、この効果は最小限である。なぜなら、キャリー伝搬の確率がビット数と共に減少するからである。特に、結果として生じる鍵のｂ個の最下位ビットを除去した後、２つのノードが確率１−２−ｂで共通鍵に関して同意することができるということが証明されることができる。
【００５０】
更に、本発明の提案されたシステムは、従来のαセキュアシステムのパフォーマンスの改善も可能にする。実際に、部分的な鍵材料共有物だけがノードに与えられるので、鍵材料共有物の格納に関するメモリリソース及び鍵を計算するための計算要件は、従来のシステムよりかなり小さい。
【００５１】
下記の表１は、この第１の実施形態によるシステムの３つの構成のストレージ要件及び計算要件を詳述する。
【表１】
【００５２】
それらの３つの構成は、メモリを最小化することを可能にする。なぜなら、ほんの数ビットだけが必要とされるからである。また、計算要件を最小化することも可能にする。なぜなら、２つの非モジュラー乗算と１つの加算だけが実行されなければならないからである。
【００５３】
対称鍵生成エンジンのこの基本的な実施形態のセキュリティは、攻撃者が、ノードに配布される部分的な鍵材料共有物、即ち、ＳＫＧＥに関して使用される情報から、元のルート鍵材料を回復させることができないという事実に依存する。
【００５４】
ＳＫＧＥのセキュリティを説明するために、最初にブロック暗号の既知の概念とこの概念とを比較する。ブロック暗号は、固定長のプレーンテキストのブロックを用いて機能する暗号化方式である。ブロック暗号は、２つの変換、即ち暗号変換
及び復号変換
からなる。Ｋは、両方の変換において使用される秘密鍵である。通信相手アリスは、鍵Ｋを用いてメッセージを暗号化して、ボブにそれを送信するため
を使用することができる。ボブは、受信した暗号化されたメッセージを復号化して、元のメッセージを得るため、同じ鍵及び復号変換
を使用することができる。プレーンテキスト攻撃を想定する場合、即ち、攻撃者が暗号化されていない及び暗号化されたメッセージのペア
を知っている場合、攻撃者は秘密鍵Ｋの回復を試すことができる。ＳＫＧＥを攻撃することは、いくらか類似する。攻撃者は、
個のペア
を得ている多くのノードをキャプチャすることができる。ここで、
は、エンティティ
のＳＫＧＥにおいて使用される鍵材料である。攻撃者は、キャプチャされた
個のペア
を用いることでシステムにおける各エンティティの対称鍵生成エンジンの生成において使用されるルート鍵材料を再構成することを目的とする。ブロック暗号への攻撃とこの攻撃とを比較する場合、ＳＫＧＥのルート鍵材料は、ブロック暗号における暗号化鍵と同じ役割を果たすと言うことができる。その上、
のペアは、プレーン／暗号テキストのペアに等しい。
【００５５】
前述したように、この基本的なＳＫＧＥは、Ｎ＿ｃ個のペア
を危険にすることにより、攻撃されるかもしれない。以下、攻撃フローの輪郭だけを描く。
【００５６】
●事前知識。
【００５７】
○
は、図３にて図示するように、３つのサブエレメント
を有する。
は、ノード
にリンクされる次数１の多項式の共有物の係数
の一部である。
【００５８】
○実験によれば、システムのセキュリティが、ルート鍵材料の係数
に強く依存することが示される。これは容易に理解されることができる。なぜなら、
のすべてのビットだけが、生成された鍵に含まれるからである。システムセキュリティに関する
の強い効果は、これがモジュラー処理が実行される唯一の要素であるという事実にも起因する。従って、攻撃者は、
を回復することにより、この特殊なＳＫＧＥを破壊することができる。
【００５９】
●
個のペア
をキャプチャすることによる
を回復する処理。
【００６０】
○２つのエンティティ
及び
のサブエレメント
を考える。それらのサブエレメントが
から生じるので、それらの間の差、即ち
を算出することができ、こうして、
に非常に相関される結果を得ることができる。結果として生じる
は、
ビット長であり、一方
は
ビット長である。ここで、
である。すると、
と書くことができる。その後、ＧＦ（ｑ）にわたり
の逆数を算出することにより、直接
を得ることができる。
の（
の外の）ｋビットが、こうして得られることができる。残りの
ビットに対して、攻撃者は、
及び
の間の差が１に向かうような態様でエンティティ
のペアを探すことができる。これは、多くのステップにおいて実行されることができる。最終的に、攻撃者は、ペア
を生成又は見つけることができる。その結果、それらの２つの識別子にリンクされる対応する値は
に等しい。ここで、
が成り立つ。
【００６１】
こうすることを必要とするペア
の予想される数は、約
であるべきである。
【００６２】
別の攻撃は、異なるポイントの補間に基づかれることができる。有限体にわたり、任意の関数が、多項式関数として表されることができる。斯かる多項式関数は、ラグランジュ補間法を使用することにより生成されることができる。
【００６３】
上記の基本的なＳＫＧＥに対するこの攻撃は、例えばブロック暗号といった他の暗号構造に対する他の攻撃と比較されることができる。多くのブロック暗号において、システムのセキュリティは、メッセージを暗号化するために用いられるラウンド（round）の数に依存する。数ラウンドを用いる同じブロック暗号は、線形、差分又は補間攻撃といった異なる種類の攻撃に対して弱いかもしれない。
【００６４】
同様に、本発明の異なる実施形態において、セキュア鍵生成エンジンは、セキュリティを強化するため、１つ又は複数の以下の機能を有することができる。
【００６５】
●システムセキュリティを増加させるため、より複雑なルート鍵材料関数の使用。例えば、次数＞１の多項式の使用。多項式の次数を増加させることは、ブロック暗号のラウンドの数を増加させることに相当する。
【００６６】
●情報のより良好な混合を実現するため、等しい又は異なるサイズの環又は体といった異なる数学的構造に対して同じ又は異なる動作を用いて、同じ又は異なる複雑さで生成される鍵材料共有物の要素のスマートな組み合わせ。例えば、異なる体にわたる多数の二変量多項式に基づかれるルート鍵材料が使用されることができる。それらのエンティティのそれぞれの識別子において二変量多項式を評価することにより、多数の多項式の共有物が、多くのエンティティに対して生成される。異なる有限体にわたるそれらの多項式の共有物のサブエレメントはその後、各エンティティのＳＫＧＥを作成するために結合される。
【００６７】
●攻撃者が実際の鍵材料を回復することができないという態様で、更なる別の拡張は、ＳＫＧＥにおける処理の設計を参照する。この最適化は、どのルート鍵材料共有物のどの鍵材料から、ＳＫＧＥのサブエレメントが生成されるかを攻撃者が発見することを不可能にするため、ＳＫＧＥ自体において実行される処理の混合及び組合せを参照する。
【００６８】
ブロック暗号の処理と比較する場合、これらの教示のいくつかがより好適に理解される。例えば、ブロック暗号は、暗号又は復号変換において多くのラウンドを使用する。ラウンドの数が多いほど、セキュリティはより高い。ブロック暗号も、混乱を引き起こし、秘密鍵の回復を難しくするため、ビットを混合することを目的とする。これは、ＳＫＧＥの設計においてより複雑な関数を導入する本発明の目的でもある。次に、上記の拡張を用いるより複雑なＳＫＧＥの実施形態を紹介する。
【００６９】
高次多項式に基づかれるＳＫＧＥ
基本的な実施形態は、次数α＝１の二変量多項式をルート鍵材料として使用する。即ち
である。この実施形態において、ｑは、式
における素数であり、システム識別子は、
ビット長であるよう選ばれる。前述されたように、斯かる構成は、多くのビットに対するラッピングモジュラ処理の効果を制限することを可能にする。この理論に従い、ビットでの体サイズと、ｋビットに等しい識別子サイズとの間の比率は減少しなければならない。特に、この比率を
に等しいとすることができる。ここで、αは多項式の次数である。α＝３とし、多項式
を用いて、
においてそれを評価する場合、
ビット長であり、多項式の共有物
が得られる。各係数
は、
として算出される。斯かる設計は、約
ビットの出力鍵を持つＳＧＫＥを作成することを可能にすることができる。一般性を失うことなく、比率は、２＊α＋１に等しい。α＝１に対して、比率は、３に等しい（基本的な実施形態）。
【００７０】
特に、ＳＫＧＥを従わせるサブエレメントは、
として表されることができる。ノードＮ１に関するＳＫＧＥは、Ｎ２での鍵を生成するために用いられることができ、
となる。この特定の例では、鍵生成の複雑さが増加することが分かる。従って、より計算要件を必要とするが、より好適な混合を実現する。一般に、ノードＮ２での鍵を生成するために有限体
にわたり次数αの二変量多項式をルート鍵材料として使用するノードＮ１のＳＫＧＥに関する処理は、
と書かれることができる。
【００７１】
ここで、一般性を失うことなく、
が成り立つ。値
は、エンティティＮ１のＳＫＧＥのサブエレメントを有し、
として元の多項式の共有物の係数に依存する。
【００７２】
この式は、
での単一の二変量多項式を使用したこの文書の冒頭に記載された基本的なＳＫＧＥ実施形態のより一般的な規定を表す。
【００７３】
エンティティＮ１のＳＫＧＥのそれらのサブエレメントのそれぞれは、元のルート二変量多項式のα＋１係数に依存する。図５は、ノードＮ１に関する多項式の共有物の係数
の生成に関係する元のルート鍵材料
の４つの係数を表す。
から生成されるＳＫＧＥの２つのサブエレメント
も示す。係数は、ｋビットブロックに分けられる。Ｘでマークされるブロックは、ＳＫＧＥ要素の生成に関係するブロックである。これらの生成されたＳＫＧＥ要素は、ＸＸでマークされる。
【００７４】
更に、生成された鍵のサイズにより分けられる鍵の生成に関係するルート鍵材料の実際のビット数は、増加する。同じ長さの鍵を生成する２つのＳＫＧＥだが、第２のＳＫＧＥが、より複雑さの次元の高いルート鍵材料関数、例えば、より高次の二変量多項式を用いる場合、攻撃者は、より多くの情報を決めなければならない。これは、より難しいものとなる。従って、ＳＫＧＥに関するルート鍵材料として、高い次数の多項式といったより複雑な数学関数の使用は、ルート鍵材料の回復をより難しくする。結果的に、αがＳＫＧＥの複雑さ及びセキュリティを決定するように見える。
【００７５】
二変量多項式の係数
は、対称性マトリクス
として図示されることができる。生成された鍵がｋビットブロックであると仮定すれば、次数αの二変量多項式の係数は、２＊α＋１のｋビットブロック長である。ここで、既に規定したのと同じ比率を使用する。次数１の二変量多項式に対して、４つの係数
を持つ。それらのそれぞれは、３つのｋビットブロックに分けられる。この分割は、ルート鍵材料のどの一部が、ＳＫＧＥ要素
のビットに影響を及ぼすかについて分析するのに有益である。これは例えば、図４ｂを分析することにより理解されることができる。
【００７６】
複数の結論が、それから得られることができる。
【００７７】
第１に、次数αの多項式に関して、
のときの
の要素は、わずか１ブロック長であるが、α＋１の効果及び
のブロックを含む。
であるとき、複雑さαのＳＫＧＥの要素
は、
ブロック長であり、
のブロックに依存する。システムが攻撃されたい場合、これを知っていることは有益でありえる。なぜなら、攻撃者は、ルート鍵材料のより少ないブロックに依存するＳＫＧＥのそれらの要素を分析し始めることができるからである。
【００７８】
第２に、最高次の係数のすべてのビットだけが、ＳＫＧＥ要素の生成に関係する。これは、その係数に関する「現実の」モジュラー処理だけを言うことに等しい。
【００７９】
２つの異なる有限体にわたる多項式の組合せに基づかれるＳＫＧＥ
より複雑及び安全なＳＫＧＥは、２つの異なる体
及び
にわたる次数１の２つの二変量多項式
を考慮することにより構築されることができる。特に、
は、式
におけるメルセンヌ素数として考慮されることができ、
は、式
における別の素数として考慮されることができる。ここで、βは、
が素数である最小の正の整数である。これらの特定の値は、斯かる態様で選ばれる。
【００８０】
（ｉ）それらの２つの多項式から生成される多項式の共有物は、異なる体の効果を含む。しかし、
【００８１】
（ｉｉ）この体は、それらの多項式の共有物のいくつかのサブエレメントを結合するよう十分類似する。及び
【００８２】
（ｉｉｉ）各エンティティのＳＫＧＥは、２つの異なる有限体にわたり生成される多項式の共有物のサブエレメントの組合せとして作成される。この特定の実施形態は、例えば次数１の多項式といった低い複雑さの数学関数に関するものであるが、例えば、異なる次数の体、体及び環等の異なる数学的構造の組み合わせが、例えば、より高次の多項式といったより高い複雑さの数学的構造に関して行われることができる点に留意されたい。
【００８３】
この特有の実施形態の基本的概念は、図４及び図４ｃに示される。ここで、２つの要素
及び
を乗算した結果が、識別子Ｒ［ｎ／３］ビット長をｎビット長倍したものであることが分かる。
【００８４】
Ｒの長さは、
及び
の非モジュラー乗算が、４＊［ｎ／３］ビット長であるような態様で選ばれる。選ばれた体の特殊な形式が原因で、これらの４＊［ｎ／３］ビット長の結果の［ｎ／３］の最上位ビットが、両方の結果の［ｎ／３］の最下位ビットと、第２の体
の場合におけるモジュラー処理を適用した後の［ｎ／３］の最上位ビットとに影響を与える。図４の左部分は、有限体
にわたる乗算を表す。この乗算は、例えば、エンティティに関する鍵材料共有物の生成に関係する図３に表される乗算のいずれかとすることができる。
【００８５】
これを念頭におくと、この手法を用いるシステム処理は、以下のように働く。構成エンティティは、２つのエンティティＮ１及びＮ２に関する合計４つの多項式の共有物を生成するため、上記２つの二変量多項式を使用する。両方のエンティティの識別子に関する変数ｘにおいて両方の二変量多項式を評価することにより、これは、通常通り行われる。４つの多項式の共有物は
である。
における
及び
はそれぞれ、多項式の共有物がＮ１又はＮ２に属するかどうか、及びその計算が
又は
に対して実行されたかを示す。これらの多項式の共有物の係数のそれぞれは、基本的な実施形態の場合同様、異なるサブエレメントに分けられる。例えば、
は、３つの要素、即ち
の連結と見られることができる。ここで、
は、連結を表す。同様に、
、
及び
が成り立つ。構成エンティティは、多項式の共有物のサブエレメントの組合せとして両方のエンティティのＳＫＧＥを有することになる要素を算出するため、関係する体の特殊な形式を考慮する。特に、
であるときノード
のＳＫＧＥの３つの要素を考慮すると、
となる。別のノードＮｊの識別子が与えられるときのノードＮｉの一般的なＳＫＧＥ処理は、本実施形態では
となる。ＳＫＧＥの要素
が、異なる多項式の共有物から生じる２つのサブエレメントの加算として得られることが観測される。それらの加算のそれぞれにおいて第２のサブエレメントを除去すれば、基本的なＳＫＧＥ実施形態に戻る。
【００８６】
この拡張は、ＳＫＧＥへの攻撃を難しくする興味深い機能をもたらす。ルート鍵材料は、この特殊なケースにおいて、異なる次数の体にわたる多項式を有する。攻撃者が、基本的な実施形態に対するのと同じ攻撃を実行したい場合、その者は障壁を見つけることになる。実際、ここで、攻撃者は識別子の逆数を算出することができない。なぜなら、それは２つの異なる体の要素だからである。更に、基本的なＳＫＧＥへの以前の攻撃では、システムのセキュリティが、係数
に依存すると述べた。詳細な解析によれば、この特殊かつ例示的な実施形態において、攻撃者が、ｎビットの代わりに４＊［ｎ／３］ビットを見つけなければならないことが示され、これは、システム解析をより困難なものにする。この意味で、ＳＫＧＥの弾力性を測定する方法は、それらのＳＫＧＥサブエレメントのビット長分ＳＫＧＥを有するサブエレメントの生成に関係するルート鍵材料のビット数間の比率を参照する。
【００８７】
この概念は、例えば多項式の共有物といった２つ以上の鍵材料共有物から生成され、例えば異なる有限体にわたる二変量多項式といった異なるルート鍵材料にリンクされる多くのサブエレメントを混合することにより更に拡張される。
【００８８】
例えば体といった異なる代数構造にわたる複数のルート鍵材料を用いる別の拡張は、その結合素数と拡張された有限体とを参照する。例えば、２つの体を参照し、１つは、モジュラー処理のための素数を用いるものであり、もう１つは、ｐを素数とするとき次数
であり、削減のため多項式を用いるものである。この理由は、処理が、体の構造により「互換性がない」ためである。
【００８９】
上記例から、ＳＫＧＥを有するサブエレメントが、単一の鍵材料共有物又はそれらの組合せから生成されたかどうかを攻撃者が区別することはできないように見える。
【００９０】
しかしながら、この情報についての知識は、攻撃者が、ルート鍵材料を回復するためのよりスマートな攻撃を実行することを可能にするかもしれない。これは、異なるルート鍵材料から生成される多数の異なる鍵材料要素からサブエレメントを有するＳＫＧＥを生成し、ルート鍵材料のパラメタを秘密に保つ更なる拡張の可能性を与える。これらのパラメタは、例えば、体、環又はベクトル空間といった使用される数学的構造の種類及び例えば体のサイズ又は多項式の次数といったそれらの複雑さを参照することができる。
【００９１】
最終的に、異なるルート鍵材料から生じる複数の鍵材料共有物の使用に基づかれるシステムの別の拡張は、ＳＫＧＥにおいて鍵生成のために必要とされるそうした要素及び処理が、鍵材料共有物の実際の値を隠すよう構成されることができるという事実を参照する。これを説明するために、４つの異なるルート鍵材料から生成されるエンティティＮ１に対する４つの異なる鍵材料共有物を仮定する。各鍵材料共有物から２つの要素が抽出されると仮定する。即ち、
である。ここで、最後の１つを除き、３つの中から抽出が行われる。また、ＳＫＧＥが、基本的なＳＫＧＥ実施形態のような３つの異なる要素
を有し、鍵が
として生成されると仮定する。ここで、ＳＫＧＥの実際の要素は、異なる鍵材料共有物から選択される上記サブエレメントの組合せである。この特殊な例では、それらは、
として組み合わせられる。鍵材料共有物は互いに独立であるので、異なるサブエレメントは互いを妨害する。従って、斯かる手法は、実際の元のルート鍵材料共有物の回復をより困難なものにする。
【００９２】
完全なＳＫＧＥ設計
このＳＫＧＥ設計は、前の２つの設計を基にしている。この設計は、次数αの単一の二変量多項式に基づかれるＳＫＧＥにおいて、係数
のすべてのビットだけが、多項式の共有物／鍵の計算に関係するという事実により動機づけされる。この理由は、上記の方式が、体サイズと鍵サイズの間の比率が
に等しいよう設計される点にある。係数
は、モジュラー演算の効果を含むが、係数の残りの効果はより小さい。実際に、それらの効果は、非モジュラー処理の効果と比較されることができる。更に、単一のルートに鍵材料だけが用いられる。従って、このシステムは、かなり線形である。
【００９３】
この問題を処理するため、それぞれ次数１、２、…、α及びαのルート鍵材料としてα＋１の二変量多項式を含む完全なＳＫＧＥ設計を説明する。この特定の実施形態では、これらの二変量多項式は、以下の体にわたり存在する。
【００９４】
次数１の
にわたる
。
【００９５】
…
【００９６】
次数ｉの
にわたる
。
【００９７】
…
【００９８】
次数αの
にわたる
。
【００９９】
次数αの
にわたる
。ここで
は
より大きい素数である。
【０１００】
ここで、ＳＫＧＥがｋビット長の鍵を生成すると仮定する。次数
の多項式に関する素数
の式は、以下の事実に依存する。項
は、ルート鍵材料の係数に関する所望の数のｋビット「ブロック」から現れる。
は、
の最上位ｋビットブロック、又は言い換えると、
の最上位のビットに影響を及ぼすモジュラー処理を持つことが必要とされる。結合処理を可能にするため、即ち、多項式の共有物のちょうど一部を用いることにより鍵を生成するため、１が選択される。最終的に、項
が、素数を見つけるために用いられる。βの値は、数
が素数であるための最小の正の整数である。
【０１０１】
このアイデアは、
のモジュラー処理が
の次数１の係数等に影響を及ぼすシステムを設計することである。同じことが
及び
にも言える。一般に、
の貢献は、より高い識別子
を持つすべての多項式に影響を及ぼすことになる。
【０１０２】
この設計は、上述の両方のＳＫＧＥの利点を結合し、更に新たな利点を提供する。まず、すべての多項式で最も高い次数の係数のすべてのビットが鍵の生成に関係するという態様で、このシステムは設計される。これは特に重要である。なぜなら、それらの係数が、モジュラー処理を含むからである。第２に、ビットで測定される異なるサイズの体が使用され、こうして、任意の要素の逆転がずっと困難になる。特に、同じ識別子が、４つの多項式の生成に使用されるが、これらの多項式は、異なる体にわたり存在するので、ルート鍵材料の完全な係数又はその一部を回復するために、識別子の逆要素を計算することはかなり困難である。この事実は、補間攻撃をもより困難なものにする。なぜなら、今や攻撃者は、多項式を用いてＳＫＧＥ挙動を近似することに狙いを定めるからである。しかしながら、斯かる多項式は、異なる体に起源を持ち、未知のビットにより影響された情報の効果を含む。これは、補間多項式の予想次数を非常に高くし、こうして、このシステムは非常に弾力的である。第３に、異なるルート鍵材料（即ち、二変量多項式
）から生じる鍵材料共有物（多項式の共有物）から生成されるサブエレメントが、互いを乱すという態様で、体のオーダーが選択される。これは、元のルート鍵材料の回復をより困難なものにする。この混乱効果は、例えば
といったより高い識別子を持つ多項式の係数に関する、最高次数の多項式
の係数の効果を参照する。追加的な事実は、素数における項
に起因するモジュラー処理の効果を参照する。これらの項は、式
におけるＳＫＧＥの要素に強く影響を及ぼす。これは、異なる有限体にわたる異なる多項式から実際に生じる非線形効果をもたらす。ＳＫＧＥの他の要素
とルート鍵材料の係数との間の関係はそのまま残る。違いは、これらの要素も、α＋１のルート鍵材料すべてに依存する点である。従って、ＳＫＧＥに関するアルゴリズムにおいて使用される処理は、セクション「次数が１より大きな多項式に基づかれるＳＫＧＥ」において導入されたものと変わりがない。そのＳＫＧＥは、
となる。
【０１０３】
これは、
となる。
【０１０４】
ここで、ＳＫＧＥ
の要素が、上記の手法に従い、α＋１の鍵材料共有物の要素の組合せとして生成される。すると、この表現は、例えば補間技術を用いて近似されることがかなり困難である。なぜなら、要素
が、異なる有限体にわたるモジュラー処理の非線形効果をもたらすからである。
【０１０５】
システムの複雑さが大きくなる場合、即ち長いα値が選択される場合、このシステムの実現は、長い整数の非モジュラー乗算を必要とする。ここで、パフォーマンスとセキュリティとの間のトレードオフが発見される。ＳＫＧＥの複雑さを高めるほど、セキュリティレベルは高くなる。これは、暗号セキュリティがラウンド数に依存するブロック暗号の処理に相当する。このトレードオフは特に挑戦的である。なぜなら、乗算の数が、指数的に大きくなるからである。これは、上記のＳＫＧＥの最後の項
を解析することにより理解されることができる。上記の和における要素
は、
ビット長の２つの要素の乗算を含む。これが非モジュラー処理である場合でも、
の大きな値に対しては、非常にコストがかかる（constly）。計算パフォーマンスも、第２の項
に依存する。しかし、その程度はそれほど強くない。ｉ番目の指数に対して、
及び
ビット長の２つの要素の乗算を含む。図５は、乗算が指数関数的に大きくなることを示す。ここで、ｋビット乗算の数を参照する点に留意されたい。
【０１０６】
システムのパフォーマンスは、上記のＳＫＧＥ表現をわずかに修正し、いくつか事前計算をすることで、最適化されることができる。ここで、以下のように規定される３つの変化又は変形例を説明する。
【０１０７】
第１に、ノードＮ１は、両方の項
に関してＮ２の出力を事前計算することができる。これは、再帰的な態様でそれを計算することにより、効率的に実行されることができる。これは、αのｋビット乗算を必要とする。一般に、
となる。
【０１０８】
第２に、Ｎ２の上記の事前計算された出力が与えられるとすると、上記のＳＫＧＥにおける第２の項
の貢献は、Ｎ２のｉ番目の出力のｋ最下位ビットとＳＫＧＥ要素
との乗算として計算されることができる。これは、α（α＋１）／２からαへと、即ち係数（α＋１）／２分、必要とされるｋビット乗算の数を減らす。
【０１０９】
第３の最適化は、上記のＳＫＧＥの第３の項
のパフォーマンスを改善する。これを理解するため、４ｋビット長の２つの要素Ａ及びＢの乗算を観測することができる。ここで、一般性を失うことなく、４ｋビット長オペランドが選択される。Ａ及びＢは、各ｋビット長の４つのサブエレメントを有する。この乗算は、ｉ＝４のとき項
の特殊な乗算を表す。乗算の結果は、８＊ｋビット長変数Ｃである。しかしながら、Ｃ全体を持つ必要はなく、Ｃのｋビットだけを持つ必要がある。従って、和
における項の各々の計算は、最適化されたバージョンにより置換されることができる。計算的な観点から、
に関するこの最適化された表現が、以下に示される。
及び
がそれぞれ、
ｋビット要素を有する点に留意されたい。これらの要素は、
及び
である。そして、
が成り立つ。
【０１１０】
これは、和
のｊ番目の項のこの最適化された生成が、
から
へとｋビット乗算の数を減らすことを可能にすることを意味する。通常、すでに指摘したように、この近似は、結果のいくつかのビットを除去することを必要とする。なぜなら、この最適化は、前の項の効果を含まないからである。その結果、これは、加算から生じるキャリーの効果を含まない。しかしながら、ｋが十分に大きい場合、及び特に上記３つの最適化のある場合と無い場合とでシステムのパフォーマンスを比較する場合、これは軽微な事実である。従って、これらの最適化は、高い複雑さのＳＫＧＥの使用を可能にする。ここで、複雑さは、元のルート二変量多項式を回復するための複雑さを参照する。なぜなら、αのより高い値を選択すると、より多くの多項式が導入されるからである。
【０１１１】
上記すべての教示は、他のＳＫＧＥの設計にも適用されることができる。追加的な設計手法は、システムへの攻撃の可能性を最小化するために多数のランダム特性を満たす識別子を使用することを含む。これは、攻撃者が元のルート鍵材料を回復することを防止する。更に、本書で説明されるシステムは、例えば多変量多項式といった多変量関数を用いることにより、多数の通信相手間での鍵合意のために容易に適合されることができる点に留意されたい。
【０１１２】
本書において説明される技術的特徴は、幅広い用途において使用されることができる。
【０１１３】
主な用途は、無線センサネットワークにおいて実現されるセキュリティシステムでの使用である。例えば、それらのネットワークは、以下の通りである。
【０１１４】
−広範的な患者モニタリングに使用される医療センサネットワーク。それらのネットワークにおいて、ノードは一般に、患者に配置され、メモリ及び計算能力に関する少ないリソースしか持たないセンサノードである。
【０１１５】
−分散照明環境、ビル自動化システム、車載装置ネットワーク、又はアクセス制御方針が設定され、観測されなければならない他の任意のネットワークといったスマートな環境。
【０１１６】
−より詳細には、標準的なＩＥＥＥ ８０２．１５．４／ＺｉｇＢｅｅに基づかれる任意の無線センサネットワーク。
【０１１７】
本発明は、例えばセンサノード又はパーソナルデジタルアシスタントといった資源制約されたデバイス上で、他のシステム及び例えば軽量デジタル証明書といった他の方法と組み合わされることもできる。軽量デジタル証明書は、エンティティを確認及び認証するため、このエンティティに関連付けられる属性のセットから成る。この属性のセットは、エンティティのデジタル識別（名前、職業等）、アクセス制御役割だけでなく、他のパラメタを含むことができる。
【０１１８】
更に、本発明は、以下の領域において新しい機会を開くことができる。
【０１１９】
−無線センサネットワーク又はデータ通信ネットワークにおける安全なブロードキャスト。実際、ネットワークにおけるベースステーションは、ネットワークにおけるルート鍵材料及びノードの複数の各ノードを格納することができる。従って、ベースステーションは、本発明において提供される破られない鍵材料共有物を用いてメッセージを暗号化するためにルート鍵材料を用いることができる。
【０１２０】
−異なる通信用途における完全にセキュアな電子チケットの創作。
【０１２１】
ＳＫＧＥは、偽造発見を含む他の多くの用途を可能にする。この用途において、異なるが、相関されるＳＫＧＥが、製品の一意性の署名を提供する各製品に埋め込まれることができる。例えば、デジタル文書において、ランダムシーケンスを用いてわずかに修正される、例えばデジタル画像の元のデジタルシーケンスを持つことができる。例えば、デジタル画像におけるいくつかのピクセルの最下位ビットをランダムに修正することが可能である。この情報の指紋は、ハッシュ関数を計算することにより決定されることができ、そのデジタル文書に関する秘密のルート鍵材料からＳＫＧＥの要素を生成するため、ハッシュの出力を用いることができる。生成されたＳＫＧＥの要素は、同じデジタル文書に埋め込まれる。例えば、デジタル画像のいくつかのピクセルの最下位（last significant）ビットに埋め込まれる。この手法は、ＳＫＧＥの使用に基づかれる偽造発見を可能にする。即ち、複製されたデジタル文書は、追跡されることができ、偽の文書は、有効なＳＫＧＥを含まない。
【０１２２】
本願明細書及び請求項において、ある要素に先行する「ａ」又は「ａｎ」という単語は、斯かる要素が複数存在することを除外するものではない。更に、「有する」という単語は、記載される要素又はステップ以外の他の要素又はステップの存在を除外するものではない。
【０１２３】
請求項において括弧内の参照符号が含まれることは、理解を助けるためのものであり、限定することを目的とするものではない。
【０１２４】
本開示を読めば、他の修正が当業者に対して明らかであろう。斯かる修正は、セキュア通信の従来技術において既に知られており、本書に説明される特徴の代わりに、又はこれに加えて使用されることができる他の特徴を含むことができる。
【技術分野】
【０００１】
本発明は、セキュア通信に関する方法、及び通信を安全に行うための暗号化システムといったセキュア手段を用いる通信デバイスを持つ通信ネットワークに関する。本発明は、例えば携帯型ワイヤレスセンサ及びアクチュエータネットワーク（ＷＳＮ）といった通信ネットワークにおいて、より詳細には、患者監視のための医療無線ネットワーク、又は例えば照明環境ネットワーク、ビル自動化ネットワーク、車載装置ネットワークといった他のパーソナルネットワークにおいて、有利な用途を見いだす。
【背景技術】
【０００２】
これらのセンシティブな用途のため、ネットワーク等は、秘密性、認証（authentication）、完全性及びアクセス権限（authorization）といったセキュリティサービスを具備しなければならない。
【０００３】
従来の通信ネットワークにおいて使用される暗号化システムは通常、通信を安全に行うための暗号方法に基づかれるセキュリティサービスを可能にする。暗号方法は、その処理のため暗号鍵を必要とする。
【０００４】
より詳細には、通信相手又はノードを有し、非常にコスト効率が良くなければならないいくつかのネットワークでは通常、必要なセキュリティサービスを可能にするため対称性暗号が適用される。実際、無線センサネットワークのようなネットワークにおいて、ノードは通常、バッテリーパワー、通信帯域幅、処理パワー又はメモリの点で、リソースが制限されている。非対称暗号に基づかれるセキュリティ方法は従って、斯かるノードでは非効率的又は実現不可能と一般には考えられる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
対称性暗号における基本的な問題は、鍵配布にある。即ち、ネットワークに属し、安全に通信しなければならないノードにおける共有される秘密の確立にある。この問題は、ＷＳＮにおいて特に顕著である。なぜなら、それらのサイズは十から数万ノードまで変化することができ、それらの性質は非常に動的であるからである。例えば、ネットワークトポロジが先験的に知られるということができない。
【０００６】
暗号鍵は、公開鍵暗号法、鍵配布センター又は他の対称性技術に基づかれる異なる方法を用いて、関係する通信相手の間で分散及び確立される。特に、最近、センサネットワークに対する鍵配布方式の設計に関する調査が実施された。ランダム鍵事前配布方式、トラストセンターベースの鍵配布方式又は公開鍵暗号法の適用が提案されている。それらの方式の多くにおいて、セキュリティとパフォーマンスとの間のトレードオフが存在する。例えば、ランダム鍵事前配布方式は、Ｍ個の鍵のプールからランダムに選択されるＷ個の鍵をＷＳＮにおける各ノードに配布する。こうして、２つノードは、Ｗ及びＭに依存して、共通の鍵を共有する確率ｐを持ち、セキュア通信リンクを確立することができる。しかしながら、これらの方式は、ノード及び格納された鍵をキャプチャすることにより破られることができる。また、これは比較的多数の鍵の格納を必要とする。例えば、５０〜２００の間であり、１００ビットの鍵に対して５００〜２０００バイトに等しい。公開鍵ベースの鍵合意方式は、単一の鍵の格納で済むが、鍵生成に関するアルゴリズムはかなり複雑である。その上、このシステムは計算的な観点から言えば更に遅い。なぜなら、鍵合意ハンドシェイク手順のため数秒が必要とされるからである。従来の鍵配布方式の中には、αセキュアと呼ばれる鍵材料共有物配布方式を取るものがある。その場合、ネットワークに属するノードは、レディーメードの暗号鍵を直接具備するのではなく、通信を安全に行うためこのネットワークの別のノードと共有される鍵を計算することを可能にするあるノード特有の鍵材料を具備する。このノード特有の情報は、ネットワークの管理デバイスに含まれるルート鍵材料から得られる鍵材料共有物である。これらのαセキュア方式は、パフォーマンス、可用性及びセキュリティ間のトレードオフを提供する。それらのシステムの主な欠点は、αノードのキャプチャ、従ってα鍵材料共有物の組合せのキャプチャがルート鍵材料全体を危うくする性質をルート鍵材料が持つという事実にある。
【０００７】
本発明の目的は、上述した欠点を解決し、従来の鍵配布方式のパフォーマンスを増加させる、ネットワークにおける通信を安全に行う方法を提案することにある。
【０００８】
本発明の別の目的は、任意の数のノードがキャプチャされてもネットワークが危険にならないネットワークを提供することである。
【０００９】
本発明の更に別の目的は、ネットワークのノードに関するリソース要件を最小化しつつ、従来のαセキュア鍵配布方式より非常に高いセキュリティレベルを実現する効果的な鍵配布を確立することである。
【課題を解決するための手段】
【００１０】
このために、本発明は、対称鍵生成エンジン（ＳＫＧＥ）を具備する管理デバイスを有するネットワークにおいて第１のノードと第２のノードとの間の通信を安全に行う方法を提供する。対称鍵生成エンジン
は、３つの望ましい処理特性を用いて、第１の通信相手アリスが、ネットワークにおける他の任意の通信相手、例えば、ボブとのペアワイズ鍵を生成することを可能にする暗号ブロックである。まず、本発明は、鍵合意のための非対称ハンドシェイクより計算的に非常に効率的である。第２に、この鍵生成エンジンは、非常に効率的な態様で格納されることができる。即ち、本発明は、トリビアルな対称鍵分布方式のＮ−１の鍵と比較されるとき、数バイトのストレージで済む。第３に、このエンジンは、破られることが困難である。
【００１１】
一般性のため、エンティティ
、例えばノードのＳＫＧＥを、他の通信相手の識別子が与えられるとき、システムにおける他の任意のエンティティ
での対称鍵の高速かつ効率的な生成をエンティティ
が行うことを可能にする構造として定める。エンティティ
のＳＫＧＥは、同じ秘密鍵材料
に基づかれる。この秘密情報は、ｎの独立した鍵材料共有物
から生成される鍵材料
のセットのｎ個の組合せである。異なるエンティティ
に関する鍵材料共有物
が、いくつかのルート鍵材料
から生成される。
【００１２】
ルート鍵材料
及び鍵材料共有物
は例えば、暗号において使用される既知の数学関数に基づかれる。これらの数学関数は、多項式、行列、組合せ構造等を含むことができる。数学演算は、例えば群（group）、体（field）、環（ring）、ベクトル空間等を含む代数構造といった任意の有限体又は他の数学的構造にわたり実行されることができる。
【００１３】
ＳＫＧＥの処理は、
管理デバイスが、ルート鍵材料、例えば、多項式のルート鍵材料と、第１のノードの識別子とに基づき、例えば第１の多項式の下で、第１のノードに関する鍵材料共有物のセットを生成するステップであって、各第１の鍵材料共有物が、サブエレメントに分割される、ステップと、
管理デバイスが、上記第１の鍵材料共有物のサブエレメントのサブセット、例えば多項式の係数を選択するステップであって、各第１の鍵材料共有物に対して選択されるサブエレメントの数が、上記第１の鍵材料共有物のサブエレメントの総数以下であり、上記選択されたサブエレメントが、第１のノードの部分的な鍵材料共有物又は対称鍵生成エンジンを形成する、ステップと、
管理デバイスが、第１のノードの部分的な物質共有物を第１のノードに送信するステップと、
上記第１のノードの部分的な鍵材料共有物又は対称鍵生成エンジンと上記第２のノードの識別子とに基づき、上記第２のノードとの通信を安全に行うのに使用される第１の鍵を上記第１のノードが生成するステップとを有する。
【００１４】
対称鍵生成エンジンに関する斯かる方法は、鍵配布方式の弾力性を増加させる。なぜなら、ノードは、第１のノードの鍵材料共有物の一部のみを具備し、従って、多数のノードがキャプチャされたとしても、攻撃者は、最初のルート鍵材料を取得することができないからである。
【００１５】
その上、対称鍵生成エンジンは、例えば、異なる有限体にわたり実行される、異なるルート鍵材料の混合処理から生成される異なる鍵材料共有物から生じる多数の要素を結合することができる。
【００１６】
追加的なセキュリティ機能は、異なる複雑さの鍵材料共有物及びルート鍵材料共有物を用いて、設定可能なセキュリティレベルを参照する。例えば、ルート鍵材料が多項式である場合、選択される多項式の次数は、計算的複雑さとセキュリティとの間のトレードオフを提供するために用いられることができる。
【００１７】
更に、ノードは、より少ない数の要素を具備し、こうしてより少ないビット数を具備するので、これらの要素を格納するためのメモリ要件は最小化され、部分的な鍵を生成するための計算要件も減らされる。
【００１８】
別の実施形態では、ルート鍵材料は、対称性の二変量多項式である。第２のノードが、第１のノードの鍵材料共有物と同じ態様で計算される部分的な鍵材料共有物を具備し、これに従って第２の部分的な鍵を生成する場合、斯かる特性は、この第２の鍵が第１の鍵に等しいことをもたらす。
【００１９】
本発明の更に別の実施形態において、ルート鍵材料は、有限体ＧＦ（ｑ）ｎにおける係数を持つ次数１の多項式である。ここで、ｑｎは２ｎ−１に等しい素数である。ｎは整数である。
【００２０】
別の実施形態では、エンティティの対称鍵生成エンジンは、異なる次数で異なる有限体にわたる多数の二変量多項式から生成される多数の多項式の共有物から生じる要素を結合することにより設計される。多項式の共有物の実際の生成が、対応する体で実行されるという態様で、組合せが実行される。しかし、対称鍵生成エンジンは、そうした体全てに共通する要素及び処理を結合する。
【００２１】
本発明の別の側面は、ノードを有するネットワークにおいてルート鍵材料を具備する管理デバイスに関する。この管理デバイスは、
上記ノードの識別子を受信するとき、上記ルート鍵材料に基づき、ノード鍵材料共有物を生成する手段であって、各鍵材料共有物が、サブエレメントに分けられる、手段と、
対称鍵生成エンジンの設計に関する第１の鍵材料共有物のサブエレメントのサブセットを選択する手段であって、各鍵材料共有物から選択される上記サブエレメントの数が、第１の鍵を生成するよう構成されるノードの部分的な鍵材料共有物を形成するよう、このサブ識別子のサブエレメントの総数以下である、手段と、
上記ノードの部分的な鍵生成共有物を上記ノードに配布する手段とを有する。
【００２２】
本発明の別の側面は、上記の管理デバイスと通信デバイスとを有するネットワークシステムに関する。この通信デバイスは、識別子及び対称鍵生成エンジンを具備する。このシステムは、
上記管理デバイスに上記識別子を送信する手段と、
上記管理デバイスから、ノードの部分的な鍵材料共有物を受信する手段と、
上記別のノードの識別子を受信する手段と、
上記受信した対称鍵生成エンジン又はノードの部分的な鍵材料共有物と、上記受信した他のノードの識別子とに基づき、上記他のノードとの通信のための鍵を生成する手段とを有する。
【図面の簡単な説明】
【００２３】
【図１】管理デバイス及び２つのノードを有する本発明によるネットワークを表す図である。
【図２】基本的な対称鍵生成エンジンに関する本発明による方法のシーケンスを示すブロック図である。
【図３】基本的な対称鍵生成エンジンにおける従来の鍵生成処理を示す図である。
【図４ａ】本発明による鍵生成処理を示す図である。
【図４ｂ】本発明による別の鍵生成処理を示す図である。
【図４ｃ】２つの異なる有限体にわたり２つの異なる二変量多項式から生成される２つの多項式の共有物から選択されるサブエレメントが、エンティティＲの対称鍵生成エンジンを作成するために結合される本発明の実施形態を示し、モジュラー乗算に関連付けられる要素だけを表す図である。
【図５】二変量多項式の次数がルート鍵材料として使用されるとき、ＳＫＧＥのいくつかのサブエレメントの生成に関係するルート鍵材料のビットを表す図である。
【発明を実施するための形態】
【００２４】
本発明のこれら及び他の側面が、以下に説明される実施形態から明らかとなり、これらの実施形態を参照して説明されることになる。
【００２５】
本発明が、以下、添付の図面を参照して、例を用いて、より詳細に説明されることになる。
【００２６】
本発明は、ネットワークにおける通信を安全に行う方法に関する。斯かる方法の例示的な動作シークエンスが、本発明によるネットワークを示す図１及びネットワークの動作シークエンスのブロック図を示す図２と共に説明されることになる。図２は、基本的な対称鍵生成エンジンの設計において使用されるいくつかの例示的な要素を含む。
【００２７】
このネットワークは、構成フェーズＣＯＮＦＩＧの間ルート鍵材料を具備する管理デバイス２を有する。ある例示的な実施形態では、ルート鍵材料は、有限体ＧＦ（ｑ）における係数を持つ次数１の対称性の二変量多項式Ｆ（ｘ、ｙ）である。この多項式は、Ｆ（ｘ，ｙ）＝ａ００＋ａ０１ｘ＋ａ１０ｙ＋ａ１１ｘｙのように記述されることができる。ここで、ａ０１＝ａ１０である。
【００２８】
ある実施形態において、体ＧＦ（ｑ）の特性は、素数のメルセンヌ数ｑｎ＝２ｎ−１であり、ここで、ｎは、例えばｎ＝１７、１２７又は５２１といった整数である。
【００２９】
この構成フェーズＣＯＮＦＩＧの間、ネットワークの各ノード（Ｎ１、Ｎ２）は、識別子（ＩＤ１、ＩＤ２）をそれぞれ具備する。それらの識別子は、ｒビット長である。ここで、ｒはｎより少ない整数である。ある例において、ｒは、ｎ／３の整数部に等しい。この構成フェーズは一般に、ネットワークの事前配備フェーズの間に、即ちノードが実際にネットワークに参加する前に発生する。
【００３０】
一旦ノードが配備されると、管理デバイスは、ＧＥＮＥＲフェーズの間、ルート鍵材料Ｆ（ｘ，ｙ）と識別子ＩＤ１とに基づき、ノードＮ１に関する完全な鍵材料共有物を生成する。ノードＮ１に関する完全な鍵材料共有物は、
であり、ここで、この多項式の係数は、以下の
及び
として計算される。斯かる方法において実行される他の全ての処理同様、これらの処理はｑを法として（modulo q）実行される。なぜなら、このシステムは、有限体ＧＦ（ｑ）にわたり実行されるからである。
【００３１】
ここで、従来の方法による鍵生成処理を簡単に説明する。その後、ＳＫＧＥに基づかれる本発明の改良を説明する。
【００３２】
斯かる従来の処理は、図３を参照して、以下の設定で説明されることになる。
【００３３】
−管理デバイスにおいて与えられるルート鍵材料は、Ｆ（ｘ，ｙ）＝ａ００＋ａ０１ｘ＋ａ１０ｙ＋ａ１１ｘｙである。これは、式Ｆ（ｘ，ｙ）＝（ａ００＋ａ０１ｘ）＋（ａ１０＋ａ１１ｘ）ｙと因数分解されることができる。
【００３４】
−Ｆ（ｘ，ｙ）の係数は、連結される３つのセグメントの式の下で表される。
【００３５】
−このネットワークは、２つのノードを有し、その識別はＲ及びＶである。
【００３６】
第１のステップは、ｘ＝ＲにおいてＦ（ｘ，ｙ）を評価することにより、ノードＲに関する鍵材料共有物を生成することにある。これは、
を生成する。
【００３７】
この評価は、図３の上部に示され、ここで、
−上部左側では
の計算となり、及び
-上部右側では
の計算となる。
【００３８】
その後、従来のシステムにおいて、管理デバイスにより生成される完全な鍵材料共有物は、Ｒノード、即ち６つのセグメント
に送信される。
【００３９】
ノードＲとノードＶとの間で通信が確立されなければならないとき、識別子Ｖが、ノードＲに与えられる。その結果、このノードは、通信を安全に行うための完全な鍵を生成することができる。この鍵は、両方のノードが合意するペアワイズ鍵である。これは、ｙ＝ＶにおいてノードＦＲ（ｙ）の鍵材料共有物を評価することにより計算される。この計算は、図３の下部に示される。計算
は、３つの連結されたセグメントＫ１、Ｋ２及びＫ３を含む鍵Ｋを与える。
【００４０】
要素Ｗ１及びｚ１はキャリーに対応し、有限体のサイズに依存する。
【００４１】
斯かる従来のシステムにおいて、ノードの完全な鍵材料共有物のすべてのセグメントが、このノードに送信される。従って、多数のノードがキャプチャされる場合、攻撃者はルート鍵材料及び従ってシステム全体の安全性を低下させることができる。今の例の場合、２つのノードがキャプチャされれば、ルート鍵材料を危うくするのに十分である。なぜなら、次数１の多項式が使用されるからである。
【００４２】
次に、図２及び図４を参照して、他の欠点の中でもこのセキュリティ問題を解決するために本発明により提案される改良を説明する。
【００４３】
図２の動作シークエンスに戻り、ＩＤ１を用いてノードＮ１の完全な鍵材料共有物を生成した後、管理デバイスは、ＳＥＬＥＣＴステップにおいて、部分的な鍵材料共有物を生成するため、異なる係数のいくつかのセグメントを選択する。
【００４４】
サブエレメントとも呼ばれるそれらのセグメントが、完全な鍵の一部の生成を可能にするように選択される。こうして、ある例示的な実施形態において、管理デバイスは、図４における太い正方形で示される以下の係数
だけをノードＮ１に配布する。部分的な鍵材料共有物を形成するそれらの要素が、ノードＮ１にその後配布される。
【００４５】
その後、ノードＮ１とＮ２との間で通信が確立されなければならないとき、識別子ＩＤ２がＮ１に送信され、鍵生成処理（ＫＥＹ＿ＧＥＮ）が実行される。図４から分かるように、
だけを具備しているので、ノードＮ１は、すべての鍵要素Ｋ１、Ｋ２及びＫ３を計算することはできないが、鍵Ｋ３の最上位ビットを生成することができる。読者は、係数の異なる部分と実行されるモジュラー処理との関係を分析することにより、これを理解することができるであろう。部分的な鍵Ｋ３はその後、ノードＮ１とノードＮ２との間の通信を暗号化するために使用される。
【００４６】
同様に、管理デバイスは、ある実施形態において、ルート鍵材料共有物と第２のノードの識別子とに基づき、第２のノードの鍵材料共有物も生成する。この第２のノードの鍵材料共有物は、第２の多項式の形式下にあり、第１の係数と同じ数の係数を持つ。第２の鍵材料共有物は、第２の完全な鍵を生成するために構成される。この第２のノードの鍵材料共有物の第２の多項式の係数は、第１の多項式の係数と同様に分割される。即ち各係数は３つのサブエレメントに分けられる。その後、管理デバイスは、第２のノードの部分的な鍵材料共有物を形成し、それを第２のノードに送信するため、第２の多項式の係数のいくつかのサブエレメントを選択する。
【００４７】
第２の多項式の係数に関して選択されるサブエレメントは、第１のノードの部分的な鍵材料共有物を形成するために選択されるサブエレメントに対応する。この文脈において、「対応する要素」という用語は、同じ位置にあるサブエレメント
を意味し、これは、第１の係数の第３の要素及び第２の係数の第１及び第３の要素を表す。
【００４８】
第２のノードの鍵材料共有物と第１のノードの識別子とに基づき、第２のノードは、第１のノードとの通信を安全に行うのに使用される第２の部分的な鍵を生成する。ルート鍵材料が対称性の多項式であり、対応するサブエレメントが第１のノードの部分的な鍵材料共有物及び第２のノードの鍵材料共有物から選択されるので、第２の部分的な鍵は、第１の部分的な鍵に等しい。更に、この第２の部分的な鍵は、第２の完全な鍵の一部である。
【００４９】
この実施形態は、結果として生じる鍵の最上位ビットだけを使用する点に留意されたい。即ち、単純な対称鍵生成エンジンの本実施形態を用いる２つの通信相手は、Ｋ３の最上位ビットについてのみ合意することができる。これは、この処理が「元の体ＧＦ（ｑ）の外で」実行され、情報の一部が失われるからである。特に、両方の通信相手とも、鍵生成フェーズにおけるキャリーの効果を含むよう、任意の情報を格納するものではない。しかしながら、この効果は最小限である。なぜなら、キャリー伝搬の確率がビット数と共に減少するからである。特に、結果として生じる鍵のｂ個の最下位ビットを除去した後、２つのノードが確率１−２−ｂで共通鍵に関して同意することができるということが証明されることができる。
【００５０】
更に、本発明の提案されたシステムは、従来のαセキュアシステムのパフォーマンスの改善も可能にする。実際に、部分的な鍵材料共有物だけがノードに与えられるので、鍵材料共有物の格納に関するメモリリソース及び鍵を計算するための計算要件は、従来のシステムよりかなり小さい。
【００５１】
下記の表１は、この第１の実施形態によるシステムの３つの構成のストレージ要件及び計算要件を詳述する。
【表１】
【００５２】
それらの３つの構成は、メモリを最小化することを可能にする。なぜなら、ほんの数ビットだけが必要とされるからである。また、計算要件を最小化することも可能にする。なぜなら、２つの非モジュラー乗算と１つの加算だけが実行されなければならないからである。
【００５３】
対称鍵生成エンジンのこの基本的な実施形態のセキュリティは、攻撃者が、ノードに配布される部分的な鍵材料共有物、即ち、ＳＫＧＥに関して使用される情報から、元のルート鍵材料を回復させることができないという事実に依存する。
【００５４】
ＳＫＧＥのセキュリティを説明するために、最初にブロック暗号の既知の概念とこの概念とを比較する。ブロック暗号は、固定長のプレーンテキストのブロックを用いて機能する暗号化方式である。ブロック暗号は、２つの変換、即ち暗号変換
及び復号変換
からなる。Ｋは、両方の変換において使用される秘密鍵である。通信相手アリスは、鍵Ｋを用いてメッセージを暗号化して、ボブにそれを送信するため
を使用することができる。ボブは、受信した暗号化されたメッセージを復号化して、元のメッセージを得るため、同じ鍵及び復号変換
を使用することができる。プレーンテキスト攻撃を想定する場合、即ち、攻撃者が暗号化されていない及び暗号化されたメッセージのペア
を知っている場合、攻撃者は秘密鍵Ｋの回復を試すことができる。ＳＫＧＥを攻撃することは、いくらか類似する。攻撃者は、
個のペア
を得ている多くのノードをキャプチャすることができる。ここで、
は、エンティティ
のＳＫＧＥにおいて使用される鍵材料である。攻撃者は、キャプチャされた
個のペア
を用いることでシステムにおける各エンティティの対称鍵生成エンジンの生成において使用されるルート鍵材料を再構成することを目的とする。ブロック暗号への攻撃とこの攻撃とを比較する場合、ＳＫＧＥのルート鍵材料は、ブロック暗号における暗号化鍵と同じ役割を果たすと言うことができる。その上、
のペアは、プレーン／暗号テキストのペアに等しい。
【００５５】
前述したように、この基本的なＳＫＧＥは、Ｎ＿ｃ個のペア
を危険にすることにより、攻撃されるかもしれない。以下、攻撃フローの輪郭だけを描く。
【００５６】
●事前知識。
【００５７】
○
は、図３にて図示するように、３つのサブエレメント
を有する。
は、ノード
にリンクされる次数１の多項式の共有物の係数
の一部である。
【００５８】
○実験によれば、システムのセキュリティが、ルート鍵材料の係数
に強く依存することが示される。これは容易に理解されることができる。なぜなら、
のすべてのビットだけが、生成された鍵に含まれるからである。システムセキュリティに関する
の強い効果は、これがモジュラー処理が実行される唯一の要素であるという事実にも起因する。従って、攻撃者は、
を回復することにより、この特殊なＳＫＧＥを破壊することができる。
【００５９】
●
個のペア
をキャプチャすることによる
を回復する処理。
【００６０】
○２つのエンティティ
及び
のサブエレメント
を考える。それらのサブエレメントが
から生じるので、それらの間の差、即ち
を算出することができ、こうして、
に非常に相関される結果を得ることができる。結果として生じる
は、
ビット長であり、一方
は
ビット長である。ここで、
である。すると、
と書くことができる。その後、ＧＦ（ｑ）にわたり
の逆数を算出することにより、直接
を得ることができる。
の（
の外の）ｋビットが、こうして得られることができる。残りの
ビットに対して、攻撃者は、
及び
の間の差が１に向かうような態様でエンティティ
のペアを探すことができる。これは、多くのステップにおいて実行されることができる。最終的に、攻撃者は、ペア
を生成又は見つけることができる。その結果、それらの２つの識別子にリンクされる対応する値は
に等しい。ここで、
が成り立つ。
【００６１】
こうすることを必要とするペア
の予想される数は、約
であるべきである。
【００６２】
別の攻撃は、異なるポイントの補間に基づかれることができる。有限体にわたり、任意の関数が、多項式関数として表されることができる。斯かる多項式関数は、ラグランジュ補間法を使用することにより生成されることができる。
【００６３】
上記の基本的なＳＫＧＥに対するこの攻撃は、例えばブロック暗号といった他の暗号構造に対する他の攻撃と比較されることができる。多くのブロック暗号において、システムのセキュリティは、メッセージを暗号化するために用いられるラウンド（round）の数に依存する。数ラウンドを用いる同じブロック暗号は、線形、差分又は補間攻撃といった異なる種類の攻撃に対して弱いかもしれない。
【００６４】
同様に、本発明の異なる実施形態において、セキュア鍵生成エンジンは、セキュリティを強化するため、１つ又は複数の以下の機能を有することができる。
【００６５】
●システムセキュリティを増加させるため、より複雑なルート鍵材料関数の使用。例えば、次数＞１の多項式の使用。多項式の次数を増加させることは、ブロック暗号のラウンドの数を増加させることに相当する。
【００６６】
●情報のより良好な混合を実現するため、等しい又は異なるサイズの環又は体といった異なる数学的構造に対して同じ又は異なる動作を用いて、同じ又は異なる複雑さで生成される鍵材料共有物の要素のスマートな組み合わせ。例えば、異なる体にわたる多数の二変量多項式に基づかれるルート鍵材料が使用されることができる。それらのエンティティのそれぞれの識別子において二変量多項式を評価することにより、多数の多項式の共有物が、多くのエンティティに対して生成される。異なる有限体にわたるそれらの多項式の共有物のサブエレメントはその後、各エンティティのＳＫＧＥを作成するために結合される。
【００６７】
●攻撃者が実際の鍵材料を回復することができないという態様で、更なる別の拡張は、ＳＫＧＥにおける処理の設計を参照する。この最適化は、どのルート鍵材料共有物のどの鍵材料から、ＳＫＧＥのサブエレメントが生成されるかを攻撃者が発見することを不可能にするため、ＳＫＧＥ自体において実行される処理の混合及び組合せを参照する。
【００６８】
ブロック暗号の処理と比較する場合、これらの教示のいくつかがより好適に理解される。例えば、ブロック暗号は、暗号又は復号変換において多くのラウンドを使用する。ラウンドの数が多いほど、セキュリティはより高い。ブロック暗号も、混乱を引き起こし、秘密鍵の回復を難しくするため、ビットを混合することを目的とする。これは、ＳＫＧＥの設計においてより複雑な関数を導入する本発明の目的でもある。次に、上記の拡張を用いるより複雑なＳＫＧＥの実施形態を紹介する。
【００６９】
高次多項式に基づかれるＳＫＧＥ
基本的な実施形態は、次数α＝１の二変量多項式をルート鍵材料として使用する。即ち
である。この実施形態において、ｑは、式
における素数であり、システム識別子は、
ビット長であるよう選ばれる。前述されたように、斯かる構成は、多くのビットに対するラッピングモジュラ処理の効果を制限することを可能にする。この理論に従い、ビットでの体サイズと、ｋビットに等しい識別子サイズとの間の比率は減少しなければならない。特に、この比率を
に等しいとすることができる。ここで、αは多項式の次数である。α＝３とし、多項式
を用いて、
においてそれを評価する場合、
ビット長であり、多項式の共有物
が得られる。各係数
は、
として算出される。斯かる設計は、約
ビットの出力鍵を持つＳＧＫＥを作成することを可能にすることができる。一般性を失うことなく、比率は、２＊α＋１に等しい。α＝１に対して、比率は、３に等しい（基本的な実施形態）。
【００７０】
特に、ＳＫＧＥを従わせるサブエレメントは、
として表されることができる。ノードＮ１に関するＳＫＧＥは、Ｎ２での鍵を生成するために用いられることができ、
となる。この特定の例では、鍵生成の複雑さが増加することが分かる。従って、より計算要件を必要とするが、より好適な混合を実現する。一般に、ノードＮ２での鍵を生成するために有限体
にわたり次数αの二変量多項式をルート鍵材料として使用するノードＮ１のＳＫＧＥに関する処理は、
と書かれることができる。
【００７１】
ここで、一般性を失うことなく、
が成り立つ。値
は、エンティティＮ１のＳＫＧＥのサブエレメントを有し、
として元の多項式の共有物の係数に依存する。
【００７２】
この式は、
での単一の二変量多項式を使用したこの文書の冒頭に記載された基本的なＳＫＧＥ実施形態のより一般的な規定を表す。
【００７３】
エンティティＮ１のＳＫＧＥのそれらのサブエレメントのそれぞれは、元のルート二変量多項式のα＋１係数に依存する。図５は、ノードＮ１に関する多項式の共有物の係数
の生成に関係する元のルート鍵材料
の４つの係数を表す。
から生成されるＳＫＧＥの２つのサブエレメント
も示す。係数は、ｋビットブロックに分けられる。Ｘでマークされるブロックは、ＳＫＧＥ要素の生成に関係するブロックである。これらの生成されたＳＫＧＥ要素は、ＸＸでマークされる。
【００７４】
更に、生成された鍵のサイズにより分けられる鍵の生成に関係するルート鍵材料の実際のビット数は、増加する。同じ長さの鍵を生成する２つのＳＫＧＥだが、第２のＳＫＧＥが、より複雑さの次元の高いルート鍵材料関数、例えば、より高次の二変量多項式を用いる場合、攻撃者は、より多くの情報を決めなければならない。これは、より難しいものとなる。従って、ＳＫＧＥに関するルート鍵材料として、高い次数の多項式といったより複雑な数学関数の使用は、ルート鍵材料の回復をより難しくする。結果的に、αがＳＫＧＥの複雑さ及びセキュリティを決定するように見える。
【００７５】
二変量多項式の係数
は、対称性マトリクス
として図示されることができる。生成された鍵がｋビットブロックであると仮定すれば、次数αの二変量多項式の係数は、２＊α＋１のｋビットブロック長である。ここで、既に規定したのと同じ比率を使用する。次数１の二変量多項式に対して、４つの係数
を持つ。それらのそれぞれは、３つのｋビットブロックに分けられる。この分割は、ルート鍵材料のどの一部が、ＳＫＧＥ要素
のビットに影響を及ぼすかについて分析するのに有益である。これは例えば、図４ｂを分析することにより理解されることができる。
【００７６】
複数の結論が、それから得られることができる。
【００７７】
第１に、次数αの多項式に関して、
のときの
の要素は、わずか１ブロック長であるが、α＋１の効果及び
のブロックを含む。
であるとき、複雑さαのＳＫＧＥの要素
は、
ブロック長であり、
のブロックに依存する。システムが攻撃されたい場合、これを知っていることは有益でありえる。なぜなら、攻撃者は、ルート鍵材料のより少ないブロックに依存するＳＫＧＥのそれらの要素を分析し始めることができるからである。
【００７８】
第２に、最高次の係数のすべてのビットだけが、ＳＫＧＥ要素の生成に関係する。これは、その係数に関する「現実の」モジュラー処理だけを言うことに等しい。
【００７９】
２つの異なる有限体にわたる多項式の組合せに基づかれるＳＫＧＥ
より複雑及び安全なＳＫＧＥは、２つの異なる体
及び
にわたる次数１の２つの二変量多項式
を考慮することにより構築されることができる。特に、
は、式
におけるメルセンヌ素数として考慮されることができ、
は、式
における別の素数として考慮されることができる。ここで、βは、
が素数である最小の正の整数である。これらの特定の値は、斯かる態様で選ばれる。
【００８０】
（ｉ）それらの２つの多項式から生成される多項式の共有物は、異なる体の効果を含む。しかし、
【００８１】
（ｉｉ）この体は、それらの多項式の共有物のいくつかのサブエレメントを結合するよう十分類似する。及び
【００８２】
（ｉｉｉ）各エンティティのＳＫＧＥは、２つの異なる有限体にわたり生成される多項式の共有物のサブエレメントの組合せとして作成される。この特定の実施形態は、例えば次数１の多項式といった低い複雑さの数学関数に関するものであるが、例えば、異なる次数の体、体及び環等の異なる数学的構造の組み合わせが、例えば、より高次の多項式といったより高い複雑さの数学的構造に関して行われることができる点に留意されたい。
【００８３】
この特有の実施形態の基本的概念は、図４及び図４ｃに示される。ここで、２つの要素
及び
を乗算した結果が、識別子Ｒ［ｎ／３］ビット長をｎビット長倍したものであることが分かる。
【００８４】
Ｒの長さは、
及び
の非モジュラー乗算が、４＊［ｎ／３］ビット長であるような態様で選ばれる。選ばれた体の特殊な形式が原因で、これらの４＊［ｎ／３］ビット長の結果の［ｎ／３］の最上位ビットが、両方の結果の［ｎ／３］の最下位ビットと、第２の体
の場合におけるモジュラー処理を適用した後の［ｎ／３］の最上位ビットとに影響を与える。図４の左部分は、有限体
にわたる乗算を表す。この乗算は、例えば、エンティティに関する鍵材料共有物の生成に関係する図３に表される乗算のいずれかとすることができる。
【００８５】
これを念頭におくと、この手法を用いるシステム処理は、以下のように働く。構成エンティティは、２つのエンティティＮ１及びＮ２に関する合計４つの多項式の共有物を生成するため、上記２つの二変量多項式を使用する。両方のエンティティの識別子に関する変数ｘにおいて両方の二変量多項式を評価することにより、これは、通常通り行われる。４つの多項式の共有物は
である。
における
及び
はそれぞれ、多項式の共有物がＮ１又はＮ２に属するかどうか、及びその計算が
又は
に対して実行されたかを示す。これらの多項式の共有物の係数のそれぞれは、基本的な実施形態の場合同様、異なるサブエレメントに分けられる。例えば、
は、３つの要素、即ち
の連結と見られることができる。ここで、
は、連結を表す。同様に、
、
及び
が成り立つ。構成エンティティは、多項式の共有物のサブエレメントの組合せとして両方のエンティティのＳＫＧＥを有することになる要素を算出するため、関係する体の特殊な形式を考慮する。特に、
であるときノード
のＳＫＧＥの３つの要素を考慮すると、
となる。別のノードＮｊの識別子が与えられるときのノードＮｉの一般的なＳＫＧＥ処理は、本実施形態では
となる。ＳＫＧＥの要素
が、異なる多項式の共有物から生じる２つのサブエレメントの加算として得られることが観測される。それらの加算のそれぞれにおいて第２のサブエレメントを除去すれば、基本的なＳＫＧＥ実施形態に戻る。
【００８６】
この拡張は、ＳＫＧＥへの攻撃を難しくする興味深い機能をもたらす。ルート鍵材料は、この特殊なケースにおいて、異なる次数の体にわたる多項式を有する。攻撃者が、基本的な実施形態に対するのと同じ攻撃を実行したい場合、その者は障壁を見つけることになる。実際、ここで、攻撃者は識別子の逆数を算出することができない。なぜなら、それは２つの異なる体の要素だからである。更に、基本的なＳＫＧＥへの以前の攻撃では、システムのセキュリティが、係数
に依存すると述べた。詳細な解析によれば、この特殊かつ例示的な実施形態において、攻撃者が、ｎビットの代わりに４＊［ｎ／３］ビットを見つけなければならないことが示され、これは、システム解析をより困難なものにする。この意味で、ＳＫＧＥの弾力性を測定する方法は、それらのＳＫＧＥサブエレメントのビット長分ＳＫＧＥを有するサブエレメントの生成に関係するルート鍵材料のビット数間の比率を参照する。
【００８７】
この概念は、例えば多項式の共有物といった２つ以上の鍵材料共有物から生成され、例えば異なる有限体にわたる二変量多項式といった異なるルート鍵材料にリンクされる多くのサブエレメントを混合することにより更に拡張される。
【００８８】
例えば体といった異なる代数構造にわたる複数のルート鍵材料を用いる別の拡張は、その結合素数と拡張された有限体とを参照する。例えば、２つの体を参照し、１つは、モジュラー処理のための素数を用いるものであり、もう１つは、ｐを素数とするとき次数
であり、削減のため多項式を用いるものである。この理由は、処理が、体の構造により「互換性がない」ためである。
【００８９】
上記例から、ＳＫＧＥを有するサブエレメントが、単一の鍵材料共有物又はそれらの組合せから生成されたかどうかを攻撃者が区別することはできないように見える。
【００９０】
しかしながら、この情報についての知識は、攻撃者が、ルート鍵材料を回復するためのよりスマートな攻撃を実行することを可能にするかもしれない。これは、異なるルート鍵材料から生成される多数の異なる鍵材料要素からサブエレメントを有するＳＫＧＥを生成し、ルート鍵材料のパラメタを秘密に保つ更なる拡張の可能性を与える。これらのパラメタは、例えば、体、環又はベクトル空間といった使用される数学的構造の種類及び例えば体のサイズ又は多項式の次数といったそれらの複雑さを参照することができる。
【００９１】
最終的に、異なるルート鍵材料から生じる複数の鍵材料共有物の使用に基づかれるシステムの別の拡張は、ＳＫＧＥにおいて鍵生成のために必要とされるそうした要素及び処理が、鍵材料共有物の実際の値を隠すよう構成されることができるという事実を参照する。これを説明するために、４つの異なるルート鍵材料から生成されるエンティティＮ１に対する４つの異なる鍵材料共有物を仮定する。各鍵材料共有物から２つの要素が抽出されると仮定する。即ち、
である。ここで、最後の１つを除き、３つの中から抽出が行われる。また、ＳＫＧＥが、基本的なＳＫＧＥ実施形態のような３つの異なる要素
を有し、鍵が
として生成されると仮定する。ここで、ＳＫＧＥの実際の要素は、異なる鍵材料共有物から選択される上記サブエレメントの組合せである。この特殊な例では、それらは、
として組み合わせられる。鍵材料共有物は互いに独立であるので、異なるサブエレメントは互いを妨害する。従って、斯かる手法は、実際の元のルート鍵材料共有物の回復をより困難なものにする。
【００９２】
完全なＳＫＧＥ設計
このＳＫＧＥ設計は、前の２つの設計を基にしている。この設計は、次数αの単一の二変量多項式に基づかれるＳＫＧＥにおいて、係数
のすべてのビットだけが、多項式の共有物／鍵の計算に関係するという事実により動機づけされる。この理由は、上記の方式が、体サイズと鍵サイズの間の比率が
に等しいよう設計される点にある。係数
は、モジュラー演算の効果を含むが、係数の残りの効果はより小さい。実際に、それらの効果は、非モジュラー処理の効果と比較されることができる。更に、単一のルートに鍵材料だけが用いられる。従って、このシステムは、かなり線形である。
【００９３】
この問題を処理するため、それぞれ次数１、２、…、α及びαのルート鍵材料としてα＋１の二変量多項式を含む完全なＳＫＧＥ設計を説明する。この特定の実施形態では、これらの二変量多項式は、以下の体にわたり存在する。
【００９４】
次数１の
にわたる
。
【００９５】
…
【００９６】
次数ｉの
にわたる
。
【００９７】
…
【００９８】
次数αの
にわたる
。
【００９９】
次数αの
にわたる
。ここで
は
より大きい素数である。
【０１００】
ここで、ＳＫＧＥがｋビット長の鍵を生成すると仮定する。次数
の多項式に関する素数
の式は、以下の事実に依存する。項
は、ルート鍵材料の係数に関する所望の数のｋビット「ブロック」から現れる。
は、
の最上位ｋビットブロック、又は言い換えると、
の最上位のビットに影響を及ぼすモジュラー処理を持つことが必要とされる。結合処理を可能にするため、即ち、多項式の共有物のちょうど一部を用いることにより鍵を生成するため、１が選択される。最終的に、項
が、素数を見つけるために用いられる。βの値は、数
が素数であるための最小の正の整数である。
【０１０１】
このアイデアは、
のモジュラー処理が
の次数１の係数等に影響を及ぼすシステムを設計することである。同じことが
及び
にも言える。一般に、
の貢献は、より高い識別子
を持つすべての多項式に影響を及ぼすことになる。
【０１０２】
この設計は、上述の両方のＳＫＧＥの利点を結合し、更に新たな利点を提供する。まず、すべての多項式で最も高い次数の係数のすべてのビットが鍵の生成に関係するという態様で、このシステムは設計される。これは特に重要である。なぜなら、それらの係数が、モジュラー処理を含むからである。第２に、ビットで測定される異なるサイズの体が使用され、こうして、任意の要素の逆転がずっと困難になる。特に、同じ識別子が、４つの多項式の生成に使用されるが、これらの多項式は、異なる体にわたり存在するので、ルート鍵材料の完全な係数又はその一部を回復するために、識別子の逆要素を計算することはかなり困難である。この事実は、補間攻撃をもより困難なものにする。なぜなら、今や攻撃者は、多項式を用いてＳＫＧＥ挙動を近似することに狙いを定めるからである。しかしながら、斯かる多項式は、異なる体に起源を持ち、未知のビットにより影響された情報の効果を含む。これは、補間多項式の予想次数を非常に高くし、こうして、このシステムは非常に弾力的である。第３に、異なるルート鍵材料（即ち、二変量多項式
）から生じる鍵材料共有物（多項式の共有物）から生成されるサブエレメントが、互いを乱すという態様で、体のオーダーが選択される。これは、元のルート鍵材料の回復をより困難なものにする。この混乱効果は、例えば
といったより高い識別子を持つ多項式の係数に関する、最高次数の多項式
の係数の効果を参照する。追加的な事実は、素数における項
に起因するモジュラー処理の効果を参照する。これらの項は、式
におけるＳＫＧＥの要素に強く影響を及ぼす。これは、異なる有限体にわたる異なる多項式から実際に生じる非線形効果をもたらす。ＳＫＧＥの他の要素
とルート鍵材料の係数との間の関係はそのまま残る。違いは、これらの要素も、α＋１のルート鍵材料すべてに依存する点である。従って、ＳＫＧＥに関するアルゴリズムにおいて使用される処理は、セクション「次数が１より大きな多項式に基づかれるＳＫＧＥ」において導入されたものと変わりがない。そのＳＫＧＥは、
となる。
【０１０３】
これは、
となる。
【０１０４】
ここで、ＳＫＧＥ
の要素が、上記の手法に従い、α＋１の鍵材料共有物の要素の組合せとして生成される。すると、この表現は、例えば補間技術を用いて近似されることがかなり困難である。なぜなら、要素
が、異なる有限体にわたるモジュラー処理の非線形効果をもたらすからである。
【０１０５】
システムの複雑さが大きくなる場合、即ち長いα値が選択される場合、このシステムの実現は、長い整数の非モジュラー乗算を必要とする。ここで、パフォーマンスとセキュリティとの間のトレードオフが発見される。ＳＫＧＥの複雑さを高めるほど、セキュリティレベルは高くなる。これは、暗号セキュリティがラウンド数に依存するブロック暗号の処理に相当する。このトレードオフは特に挑戦的である。なぜなら、乗算の数が、指数的に大きくなるからである。これは、上記のＳＫＧＥの最後の項
を解析することにより理解されることができる。上記の和における要素
は、
ビット長の２つの要素の乗算を含む。これが非モジュラー処理である場合でも、
の大きな値に対しては、非常にコストがかかる（constly）。計算パフォーマンスも、第２の項
に依存する。しかし、その程度はそれほど強くない。ｉ番目の指数に対して、
及び
ビット長の２つの要素の乗算を含む。図５は、乗算が指数関数的に大きくなることを示す。ここで、ｋビット乗算の数を参照する点に留意されたい。
【０１０６】
システムのパフォーマンスは、上記のＳＫＧＥ表現をわずかに修正し、いくつか事前計算をすることで、最適化されることができる。ここで、以下のように規定される３つの変化又は変形例を説明する。
【０１０７】
第１に、ノードＮ１は、両方の項
に関してＮ２の出力を事前計算することができる。これは、再帰的な態様でそれを計算することにより、効率的に実行されることができる。これは、αのｋビット乗算を必要とする。一般に、
となる。
【０１０８】
第２に、Ｎ２の上記の事前計算された出力が与えられるとすると、上記のＳＫＧＥにおける第２の項
の貢献は、Ｎ２のｉ番目の出力のｋ最下位ビットとＳＫＧＥ要素
との乗算として計算されることができる。これは、α（α＋１）／２からαへと、即ち係数（α＋１）／２分、必要とされるｋビット乗算の数を減らす。
【０１０９】
第３の最適化は、上記のＳＫＧＥの第３の項
のパフォーマンスを改善する。これを理解するため、４ｋビット長の２つの要素Ａ及びＢの乗算を観測することができる。ここで、一般性を失うことなく、４ｋビット長オペランドが選択される。Ａ及びＢは、各ｋビット長の４つのサブエレメントを有する。この乗算は、ｉ＝４のとき項
の特殊な乗算を表す。乗算の結果は、８＊ｋビット長変数Ｃである。しかしながら、Ｃ全体を持つ必要はなく、Ｃのｋビットだけを持つ必要がある。従って、和
における項の各々の計算は、最適化されたバージョンにより置換されることができる。計算的な観点から、
に関するこの最適化された表現が、以下に示される。
及び
がそれぞれ、
ｋビット要素を有する点に留意されたい。これらの要素は、
及び
である。そして、
が成り立つ。
【０１１０】
これは、和
のｊ番目の項のこの最適化された生成が、
から
へとｋビット乗算の数を減らすことを可能にすることを意味する。通常、すでに指摘したように、この近似は、結果のいくつかのビットを除去することを必要とする。なぜなら、この最適化は、前の項の効果を含まないからである。その結果、これは、加算から生じるキャリーの効果を含まない。しかしながら、ｋが十分に大きい場合、及び特に上記３つの最適化のある場合と無い場合とでシステムのパフォーマンスを比較する場合、これは軽微な事実である。従って、これらの最適化は、高い複雑さのＳＫＧＥの使用を可能にする。ここで、複雑さは、元のルート二変量多項式を回復するための複雑さを参照する。なぜなら、αのより高い値を選択すると、より多くの多項式が導入されるからである。
【０１１１】
上記すべての教示は、他のＳＫＧＥの設計にも適用されることができる。追加的な設計手法は、システムへの攻撃の可能性を最小化するために多数のランダム特性を満たす識別子を使用することを含む。これは、攻撃者が元のルート鍵材料を回復することを防止する。更に、本書で説明されるシステムは、例えば多変量多項式といった多変量関数を用いることにより、多数の通信相手間での鍵合意のために容易に適合されることができる点に留意されたい。
【０１１２】
本書において説明される技術的特徴は、幅広い用途において使用されることができる。
【０１１３】
主な用途は、無線センサネットワークにおいて実現されるセキュリティシステムでの使用である。例えば、それらのネットワークは、以下の通りである。
【０１１４】
−広範的な患者モニタリングに使用される医療センサネットワーク。それらのネットワークにおいて、ノードは一般に、患者に配置され、メモリ及び計算能力に関する少ないリソースしか持たないセンサノードである。
【０１１５】
−分散照明環境、ビル自動化システム、車載装置ネットワーク、又はアクセス制御方針が設定され、観測されなければならない他の任意のネットワークといったスマートな環境。
【０１１６】
−より詳細には、標準的なＩＥＥＥ ８０２．１５．４／ＺｉｇＢｅｅに基づかれる任意の無線センサネットワーク。
【０１１７】
本発明は、例えばセンサノード又はパーソナルデジタルアシスタントといった資源制約されたデバイス上で、他のシステム及び例えば軽量デジタル証明書といった他の方法と組み合わされることもできる。軽量デジタル証明書は、エンティティを確認及び認証するため、このエンティティに関連付けられる属性のセットから成る。この属性のセットは、エンティティのデジタル識別（名前、職業等）、アクセス制御役割だけでなく、他のパラメタを含むことができる。
【０１１８】
更に、本発明は、以下の領域において新しい機会を開くことができる。
【０１１９】
−無線センサネットワーク又はデータ通信ネットワークにおける安全なブロードキャスト。実際、ネットワークにおけるベースステーションは、ネットワークにおけるルート鍵材料及びノードの複数の各ノードを格納することができる。従って、ベースステーションは、本発明において提供される破られない鍵材料共有物を用いてメッセージを暗号化するためにルート鍵材料を用いることができる。
【０１２０】
−異なる通信用途における完全にセキュアな電子チケットの創作。
【０１２１】
ＳＫＧＥは、偽造発見を含む他の多くの用途を可能にする。この用途において、異なるが、相関されるＳＫＧＥが、製品の一意性の署名を提供する各製品に埋め込まれることができる。例えば、デジタル文書において、ランダムシーケンスを用いてわずかに修正される、例えばデジタル画像の元のデジタルシーケンスを持つことができる。例えば、デジタル画像におけるいくつかのピクセルの最下位ビットをランダムに修正することが可能である。この情報の指紋は、ハッシュ関数を計算することにより決定されることができ、そのデジタル文書に関する秘密のルート鍵材料からＳＫＧＥの要素を生成するため、ハッシュの出力を用いることができる。生成されたＳＫＧＥの要素は、同じデジタル文書に埋め込まれる。例えば、デジタル画像のいくつかのピクセルの最下位（last significant）ビットに埋め込まれる。この手法は、ＳＫＧＥの使用に基づかれる偽造発見を可能にする。即ち、複製されたデジタル文書は、追跡されることができ、偽の文書は、有効なＳＫＧＥを含まない。
【０１２２】
本願明細書及び請求項において、ある要素に先行する「ａ」又は「ａｎ」という単語は、斯かる要素が複数存在することを除外するものではない。更に、「有する」という単語は、記載される要素又はステップ以外の他の要素又はステップの存在を除外するものではない。
【０１２３】
請求項において括弧内の参照符号が含まれることは、理解を助けるためのものであり、限定することを目的とするものではない。
【０１２４】
本開示を読めば、他の修正が当業者に対して明らかであろう。斯かる修正は、セキュア通信の従来技術において既に知られており、本書に説明される特徴の代わりに、又はこれに加えて使用されることができる他の特徴を含むことができる。
【特許請求の範囲】
【請求項１】
ルート鍵材料を具備する管理デバイスを有するネットワークにおいて第１のノードと第２のノードとの間の通信を安全に行う方法において、
ルート鍵材料に基づき、多数のサブエレメントを有する第１のノードの鍵材料共有物を前記管理デバイスが生成するステップであって、前記第１のノードの鍵材料共有物が、第１の完全な鍵を生成するよう構成される、ステップと、
前記管理デバイスが、前記第１の鍵材料共有物のサブエレメントのサブセットを選択するステップであって、前記選択されるサブエレメントの数が、前記第１の鍵材料共有物のサブエレメントの総数以下であり、前記選択されたサブエレメントが、第１のノードの部分的な鍵材料共有物又は対称鍵生成エンジンを形成する、ステップと、
前記第１のノードの対称鍵生成エンジンと前記第２のノードの識別子とに基づき、前記第２のノードとの通信を安全に行うのに使用される第１の鍵を前記第１のノードが生成するステップとを有する、方法。
【請求項２】
前記ルート鍵材料が、多数の数学関数を有する、請求項１に記載の方法。
【請求項３】
前記対称鍵生成エンジンのパフォーマンス及び安全性が、ルート数学関数の数、前記数学関数の複雑さ、前記鍵材料共有物の生成が行われる数学的構造、又は前記ルート鍵材料のパラメタを含む多数の秘密性又は公開性設計により規定される、請求項２に記載の方法。
【請求項４】
前記数学関数が、多項式である、請求項２に記載の方法。
【請求項５】
前記多項式のルート鍵材料及び前記第１のノードの識別子に基づき、多数の多項式の共有物の式の下で第１のノードの鍵材料共有物を前記管理デバイスが生成するステップであって、各多項式の共有物係数がサブエレメントに分割され、前記サブエレメントが前記前記第１のノードの鍵材料共有物を有する、ステップと、
前記管理デバイスが、第１の対称鍵生成エンジンを形成する前記第１の多項式の係数のサブエレメントのセットを選択するステップであって、前記第１のノードの対称鍵生成エンジンの前記選択されたサブエレメントが、前記第１のノード鍵材料共有物の前記選択されたサブエレメントに対応する、ステップと、
第１のノードの対称鍵生成エンジン及び第１のノードの識別子に基づき、前記第２のノードとの通信を安全に行うのに使用される部分的な鍵を前記第１のノードが生成するステップとを更に有する、請求項４に記載の方法。
【請求項６】
前記ルート鍵材料が、
前記管理デバイスが、異なる有限体にわたり処理を実行する前記ルート多項式から、第１のデバイスに関する多項式の共有物を生成し、
前記管理デバイスが、前記多項式の共有物をサブエレメントに分けることができ、対称鍵生成エンジンを形成するため前記サブエレメントを結合することができ、
前記対称鍵生成エンジンを有する前記サブエレメントが、前記ルート鍵材料の回復をより困難にするよう結合され、
前記第１のデバイスが、該第１のデバイスの対称鍵生成エンジンと第２のデバイスの識別子とを用いて、前記第２のデバイスでの鍵を生成し、
鍵生成に必要とされる前記処理が、前記体の外で行われる、
という態様で選択される多数の有限体にわたる多項式である、請求項４又は５の方法。
【請求項７】
前記数学関数の複雑さが、前記対称鍵生成エンジンのセキュリティと計算要件との間のトレードオフを提供するよう調整されることができる、請求項２又は３に記載の方法。
【請求項８】
前記数学関数の複雑さが、前記有限体の前記多項式の次数及び／又はサイズを参照する、請求項４又は５の方法。
【請求項９】
前記ルート数学関数から第１のデバイスに関する鍵材料共有物を生成するステップが、単一の数学的構造又は数学的構造の組合せに対する処理を含む、請求項１又は４の方法。
【請求項１０】
前記第１のデバイスの対称鍵生成エンジンと第２のデバイスの識別子とが与えられるとき、第１のデバイス間での鍵の生成に必要とされる前記処理が、共通の数学的構造にわたり実行される、請求項９に記載の方法。
【請求項１１】
前記管理デバイスが、前記第１のノードの鍵材料共有物又は前記第２のノードの鍵材料共有物を生成する前記ステップが、前記第１のノードの識別子又は前記第２のノードの識別子にそれぞれ対応する点における前記対称性の二変量多項式を評価するステップを有する、請求項３又は４に記載の方法。
【請求項１２】
ノードを有するネットワークにおいてルート鍵材料を具備する管理デバイスであって、
前記ノードの識別子を受信するとき、前記ルート鍵材料に基づき、ノード鍵材料を生成する手段であって、各鍵材料共有物が、サブエレメントに分けられる、手段と、
前記第１の鍵材料共有物のサブエレメントのサブセットを選択する手段であって、前記選択されるサブエレメントの数が、第１の鍵を生成するよう構成されるノードの部分的な鍵材料共有物又は対称鍵生成エンジンを形成するよう、前記鍵材料共有物のサブエレメントの総数以下である、手段と、
前記ノードの対称鍵生成エンジンを前記ノードに配布する手段とを有する、管理デバイス。
【請求項１３】
請求項１２に記載の管理デバイスと、識別子を具備する通信デバイスとを有するネットワークシステムであって、
前記管理デバイスに前記識別子を送信する手段と、
前記管理デバイスから、ノードの対称鍵生成エンジンを受信する手段と、
前記別のノードの識別子を受信する手段と、
前記受信したノードの対称鍵生成エンジンと前記受信した他のノードの識別子とに基づき、前記他のノードとの通信のための鍵を生成する手段とを有する、ネットワークシステム。
【請求項１４】
請求項１２に記載の管理デバイスと請求項１３に記載の通信デバイスとを有するネットワークシステム。
【請求項１５】
前記対称鍵生成エンジンが、ハードウェア又はソフトウェアで実現され、前記第２のデバイスの識別子が与えられるとき、第１のデバイスが、第２のデバイスでの対称性鍵を計算することを可能にする、請求項１に記載の方法。
【請求項１】
ルート鍵材料を具備する管理デバイスを有するネットワークにおいて第１のノードと第２のノードとの間の通信を安全に行う方法において、
ルート鍵材料に基づき、多数のサブエレメントを有する第１のノードの鍵材料共有物を前記管理デバイスが生成するステップであって、前記第１のノードの鍵材料共有物が、第１の完全な鍵を生成するよう構成される、ステップと、
前記管理デバイスが、前記第１の鍵材料共有物のサブエレメントのサブセットを選択するステップであって、前記選択されるサブエレメントの数が、前記第１の鍵材料共有物のサブエレメントの総数以下であり、前記選択されたサブエレメントが、第１のノードの部分的な鍵材料共有物又は対称鍵生成エンジンを形成する、ステップと、
前記第１のノードの対称鍵生成エンジンと前記第２のノードの識別子とに基づき、前記第２のノードとの通信を安全に行うのに使用される第１の鍵を前記第１のノードが生成するステップとを有する、方法。
【請求項２】
前記ルート鍵材料が、多数の数学関数を有する、請求項１に記載の方法。
【請求項３】
前記対称鍵生成エンジンのパフォーマンス及び安全性が、ルート数学関数の数、前記数学関数の複雑さ、前記鍵材料共有物の生成が行われる数学的構造、又は前記ルート鍵材料のパラメタを含む多数の秘密性又は公開性設計により規定される、請求項２に記載の方法。
【請求項４】
前記数学関数が、多項式である、請求項２に記載の方法。
【請求項５】
前記多項式のルート鍵材料及び前記第１のノードの識別子に基づき、多数の多項式の共有物の式の下で第１のノードの鍵材料共有物を前記管理デバイスが生成するステップであって、各多項式の共有物係数がサブエレメントに分割され、前記サブエレメントが前記前記第１のノードの鍵材料共有物を有する、ステップと、
前記管理デバイスが、第１の対称鍵生成エンジンを形成する前記第１の多項式の係数のサブエレメントのセットを選択するステップであって、前記第１のノードの対称鍵生成エンジンの前記選択されたサブエレメントが、前記第１のノード鍵材料共有物の前記選択されたサブエレメントに対応する、ステップと、
第１のノードの対称鍵生成エンジン及び第１のノードの識別子に基づき、前記第２のノードとの通信を安全に行うのに使用される部分的な鍵を前記第１のノードが生成するステップとを更に有する、請求項４に記載の方法。
【請求項６】
前記ルート鍵材料が、
前記管理デバイスが、異なる有限体にわたり処理を実行する前記ルート多項式から、第１のデバイスに関する多項式の共有物を生成し、
前記管理デバイスが、前記多項式の共有物をサブエレメントに分けることができ、対称鍵生成エンジンを形成するため前記サブエレメントを結合することができ、
前記対称鍵生成エンジンを有する前記サブエレメントが、前記ルート鍵材料の回復をより困難にするよう結合され、
前記第１のデバイスが、該第１のデバイスの対称鍵生成エンジンと第２のデバイスの識別子とを用いて、前記第２のデバイスでの鍵を生成し、
鍵生成に必要とされる前記処理が、前記体の外で行われる、
という態様で選択される多数の有限体にわたる多項式である、請求項４又は５の方法。
【請求項７】
前記数学関数の複雑さが、前記対称鍵生成エンジンのセキュリティと計算要件との間のトレードオフを提供するよう調整されることができる、請求項２又は３に記載の方法。
【請求項８】
前記数学関数の複雑さが、前記有限体の前記多項式の次数及び／又はサイズを参照する、請求項４又は５の方法。
【請求項９】
前記ルート数学関数から第１のデバイスに関する鍵材料共有物を生成するステップが、単一の数学的構造又は数学的構造の組合せに対する処理を含む、請求項１又は４の方法。
【請求項１０】
前記第１のデバイスの対称鍵生成エンジンと第２のデバイスの識別子とが与えられるとき、第１のデバイス間での鍵の生成に必要とされる前記処理が、共通の数学的構造にわたり実行される、請求項９に記載の方法。
【請求項１１】
前記管理デバイスが、前記第１のノードの鍵材料共有物又は前記第２のノードの鍵材料共有物を生成する前記ステップが、前記第１のノードの識別子又は前記第２のノードの識別子にそれぞれ対応する点における前記対称性の二変量多項式を評価するステップを有する、請求項３又は４に記載の方法。
【請求項１２】
ノードを有するネットワークにおいてルート鍵材料を具備する管理デバイスであって、
前記ノードの識別子を受信するとき、前記ルート鍵材料に基づき、ノード鍵材料を生成する手段であって、各鍵材料共有物が、サブエレメントに分けられる、手段と、
前記第１の鍵材料共有物のサブエレメントのサブセットを選択する手段であって、前記選択されるサブエレメントの数が、第１の鍵を生成するよう構成されるノードの部分的な鍵材料共有物又は対称鍵生成エンジンを形成するよう、前記鍵材料共有物のサブエレメントの総数以下である、手段と、
前記ノードの対称鍵生成エンジンを前記ノードに配布する手段とを有する、管理デバイス。
【請求項１３】
請求項１２に記載の管理デバイスと、識別子を具備する通信デバイスとを有するネットワークシステムであって、
前記管理デバイスに前記識別子を送信する手段と、
前記管理デバイスから、ノードの対称鍵生成エンジンを受信する手段と、
前記別のノードの識別子を受信する手段と、
前記受信したノードの対称鍵生成エンジンと前記受信した他のノードの識別子とに基づき、前記他のノードとの通信のための鍵を生成する手段とを有する、ネットワークシステム。
【請求項１４】
請求項１２に記載の管理デバイスと請求項１３に記載の通信デバイスとを有するネットワークシステム。
【請求項１５】
前記対称鍵生成エンジンが、ハードウェア又はソフトウェアで実現され、前記第２のデバイスの識別子が与えられるとき、第１のデバイスが、第２のデバイスでの対称性鍵を計算することを可能にする、請求項１に記載の方法。
【図１】
【図２】
【図３】
【図４ａ】
【図４ｂ】
【図４ｃ】
【図５】
【図２】
【図３】
【図４ａ】
【図４ｂ】
【図４ｃ】
【図５】
【公表番号】特表２０１２−５２１１３６（Ｐ２０１２−５２１１３６Ａ）
【公表日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願番号】特願２０１２−５００３５３（Ｐ２０１２−５００３５３）
【出願日】平成２２年３月１６日（２０１０．３．１６）
【国際出願番号】ＰＣＴ／ＩＢ２０１０／０５１１３４
【国際公開番号】ＷＯ２０１０／１０６４９６
【国際公開日】平成２２年９月２３日（２０１０．９．２３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＺＩＧＢＥＥ
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【Ｆターム（参考）】
【公表日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願日】平成２２年３月１６日（２０１０．３．１６）
【国際出願番号】ＰＣＴ／ＩＢ２０１０／０５１１３４
【国際公開番号】ＷＯ２０１０／１０６４９６
【国際公開日】平成２２年９月２３日（２０１０．９．２３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＺＩＧＢＥＥ
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【Ｆターム（参考）】
[ Back to top ]