(57)【要約】  鍵共有のためのネットワークデバイス３００を構成するためのシステム２００が提供され、第１及び第２のネットワークデバイスは、これらの間の共有鍵を決定するように構成される。本システムは、パブリックグローバル低減多項式２１６，Ｎ（ｔ）、二変数多項式の第１のプライベートセット２１２，ｆｉ（，）及び低減多項式の第２のプライベートセット２１４，Ｑｉ（ｔ）を電子形式において取得するための鍵材料取得部を有する。第１のプライベートセットにおける各二変数多項式は、第２のプライベートセットの低減多項式に関連付けられる。本システムは、ネットワークデバイスの識別番号Ａを識別多項式にマッピングすること、第１のプライベートセットの各特定の多項式に対して、識別多項式Ａを特定の多項式ｆｉ（Ａ，）に置換し、特定の多項式に関連付けられた低減多項式を法として低減することにより、一変数多項式のセットを取得すること、及び、一変数多項式のセットを合計することにより、第１及び第２のプライベートセットから一変数秘密鍵多項式２２８を計算するための多項式操作ユニット２２０を有する。本システムは、生成された一変数秘密鍵多項式２２８，２３６及びパブリックグローバル低減多項式２１６，Ｎ（ｔ）をネットワークデバイスに電子的に格納するように更に構成される。第１のネットワークデバイスは、一変数秘密鍵多項式３１２及びパブリックグローバル低減多項式３１４，Ｎ（ｔ）及びその識別番号３１０，Ａを格納する。第１のネットワークデバイスは、第２のネットワークデバイスの識別番号を識別多項式にマッピングし、識別多項式を一変数秘密鍵多項式に置換し、パブリックグローバル低減多項式Ｎ（ｔ）を法として置換の結果を低減することから共有鍵を導出する。
2016526851.tif 000002
【特許請求の範囲】
【請求項１】
鍵共有のためのネットワークデバイスを構成するためのシステムであって、
パブリックグローバル低減多項式、二変数多項式の第１のプライベートセット及び低減多項式の第２のプライベートセットを電子形式において取得するための鍵材料取得部であって、前記第１のプライベートセットにおける各二変数多項式は、前記第２のプライベートセットの低減多項式に関連付けられ、前記二変数多項式の第１のプライベートセットは、少なくとも２つの二変数多項式を有し、前記低減多項式の第２のプライベートセットは、少なくとも２つの異なる低減多項式を有する、鍵材料取得部と、
前記ネットワークデバイスのための識別番号を電子形式において取得するためのネットワークデバイス管理部と、
前記識別番号を識別多項式にマッピングすること、前記第１のプライベートセットの各特定の多項式に対して、前記識別多項式を前記特定の多項式に置換し、前記特定の多項式に関連付けられた低減多項式を法として低減することにより、一変数多項式のセットを取得すること、及び、前記一変数多項式のセットを合計することにより、前記第１及び第２のプライベートセットから一変数秘密鍵多項式を計算するための多項式操作ユニットとを有し、
前記ネットワークデバイス管理部は、生成された一変数秘密鍵多項式及びパブリックグローバル低減多項式を前記ネットワークデバイスに電子的に格納するように更に構成される、システム。
【請求項２】
電子乱数生成部を有し、
前記鍵材料取得部は、前記電子乱数生成部を用いて前記パブリックグローバル低減多項式の１又はそれ以上の係数を生成する、及び／又は、前記電子乱数生成部を用いて前記第１のプライベートセットにおける二変数多項式の１又はそれ以上の係数を生成する、及び／又は、前記電子乱数生成部を用いて前記第２のプライベートセットにおける低減多項式の１又はそれ以上の係数を生成するように構成される、請求項１に記載のシステム。
【請求項３】
前記二変数多項式の第１のプライベートセットは、対称の二変数多項式のみを有する、請求項１に記載のシステム。
【請求項４】
前記二変数多項式の第１のプライベートセットは、少なくとも２つの異なる二変数多項式を有し、及び／又は、前記第１のプライベートセットの少なくとも１つの多項式は、前記少なくとも１つの多項式の２つの変数のうちの１つにおける少なくとも２の次数を有する、請求項１に記載のシステム。
【請求項５】
前記一変数秘密鍵多項式は、係数のリストとして及び標準形において表され、及び／又は、前記識別多項式を前記特定の多項式に置換して前記特定の多項式に関連付けられた前記低減多項式を法として低減した結果は、前記の合計前に係数のリストとして及び標準形において表される、請求項１に記載のシステム。
【請求項６】
前記識別番号を前記識別多項式にマッピングすることは、二進数からの識別番号を２とは異なる基数番号を有する番号に変換すること、及び、変換された識別番号の桁を前記識別多項式の係数として割り当てることにより前記識別番号をマッピングすることを有する、請求項１に記載のシステム。
【請求項７】
前記識別番号を識別多項式にマッピングすることは、前記識別番号をハッシュし、前記のハッシュの結果を前記識別多項式の少なくとも部分に変換することを有する、請求項１に記載のシステム。
【請求項８】
前記鍵材料取得部は、共通多項式を生成し、前記低減多項式を前記パブリックグローバル低減多項式と前記共通多項式の倍数との間の差分として生成するように構成される、請求項１に記載のシステム。
【請求項９】
前記共通多項式の倍数は、Ｍ−ａ（ｂ−１）以下の次数を有し、Ｍは、パブリックグローバル低減多項式の次数であり、ａは、前記二変数多項式の第１のプライベートセットにおける多項式の最も高い次数であり、ｂは、前記識別番号のビットの数である、請求項８に記載のシステム。
【請求項１０】
前記共通多項式の少なくとも１つの倍数は、Ｍ−２ａ（ｂ−１）より高い次数を有する、請求項８又は請求項９に記載のシステム。
【請求項１１】
第２のネットワークデバイスにより共有鍵を決定するように構成される第１のネットワークデバイスであって、
請求項１に記載の鍵共有のためのネットワークデバイスを構成するためのシステムから取得される一変数秘密鍵多項式及びパブリックグローバル低減多項式を格納する電子格納部であって、前記電子格納部は、前記第１のネットワークデバイスのための識別番号を更に格納する、電子格納部と、
前記第１のネットワークデバイスとは異なる前記第２のネットワークデバイスの識別番号を取得するための通信ユニットと、
前記第２のネットワークデバイスの前記識別番号を識別多項式にマッピングし、前記識別多項式を前記一変数秘密鍵多項式に置換し、前記パブリックグローバル低減多項式を法として前記の置換の結果を低減するための多項式操作ユニットと、
前記パブリックグローバル低減多項式を法とした低減の結果から前記共有鍵を導出するための鍵導出デバイスとを有する、第１のネットワークデバイス。
【請求項１２】
前記電子格納部は、請求項８に記載の鍵共有のためのネットワークデバイスを構成するためのシステムから取得される一変数秘密鍵多項式、パブリックグローバル低減多項式及び共通多項式を格納し、
多項式操作ユニットは、前記共通の多項式を法として前記パブリックグローバル低減多項式を法として低減した結果を更に低減するように更に構成される、請求項１１に記載の第１のネットワークデバイス。
【請求項１３】
請求項１に記載の鍵共有のためのネットワークデバイスを構成するためのシステムと、請求項１１に記載の鍵共有のためのネットワークデバイスを構成するためのシステムにより構成される第１及び第２のネットワークデバイスとを有する鍵共有システム。
【請求項１４】
鍵共有のためのネットワークデバイスを構成するための方法であって、
パブリックグローバル低減多項式、二変数多項式の第１のプライベートセット及び低減多項式の第２のプライベートセットを電子形式において取得するステップであって、前記第２のプライベートセットの低減多項式は、前記第１のプライベートセットにおける各二変数多項式に関連付けられ、前記二変数多項式の第１のプライベートセットは、少なくとも２つの二変数多項式を有し、前記低減多項式の第２のプライベートセットは、少なくとも２つの異なる低減多項式を有する、ステップと、
前記ネットワークデバイスのための識別番号を電子形式において取得するステップと、
前記識別番号を識別多項式にマッピングすること、前記第１のプライベートセットの各特定の多項式に対して、前記識別多項式を前記特定の多項式に置換し、前記特定の多項式に関連付けられた低減多項式を法として低減することにより、一変数多項式のセットを取得すること、及び、前記一変数多項式のセットを合計することにより、前記第１及び第２のプライベートセットから一変数秘密鍵多項式を計算するステップと、
生成された一変数秘密鍵多項式及び前記パブリックグローバル低減多項式を前記ネットワークデバイスに格納するステップとを有する、方法。
【請求項１５】
第２のネットワークデバイスにより共有鍵を決定するための方法であって、
請求項１に記載の鍵共有のためのネットワークデバイスを構成するためのシステムから取得される一変数秘密鍵多項式及びパブリックグローバル低減多項式を格納するステップと、
前記第１のネットワークデバイスのための識別番号を格納するステップと、
前記第２のネットワークデバイスの識別番号を取得するステップと、
前記第２のネットワークデバイスの前記識別番号を識別多項式にマッピングするステップと、
前記識別多項式を前記一変数秘密鍵多項式に置換し、前記パブリックグローバル低減多項式を法として前記の置換の結果を低減するステップと、
前記パブリックグローバル低減多項式を法とした低減の結果から前記共有鍵を導出するステップとを有する、方法。
【請求項１６】
コンピュータプログラムがコンピュータ上で実行されたときに請求項１４又は請求項１５の全てのステップを実行するように適合されたコンピュータプログラムコード手段を有する、コンピュータプログラム。
【請求項１７】
コンピュータ読み取り可能な媒体上に具現化された請求項１６に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鍵共有のためのネットワークデバイスを構成するためのシステムに関し、このシステムは、多項式を取得するための鍵材料取得部と、電子形式においてネットワーク装置のための識別番号を取得するためのネットワークデバイス管理部と、多項式操作ユニットとを有する。
【背景技術】
【０００２】
暗号化において、鍵合意プロトコルは、共通鍵をまだ共有していないかもしれない２又はそれ以上の者が斯様な鍵に同意することができるプロトコルである。好ましくは、両者は、いずれの者も鍵の選択を強制することができないように、結果に影響することができる。２者間の全ての通信を盗聴する攻撃者は、鍵について何も学習するべきではない。更に、同じ通信を知る攻撃者が何も学習しないか又はほとんど学習しない一方で、両者自体は共有鍵を導出することができる。
【０００３】
鍵合意プロトコルは、例えば両者間のメッセージを暗号化及び／又は認証するために、例えば通信を確保するのに役立つ。
【０００４】
実用的な鍵合意プロトコルは、Whitfield Diffie及びMartin Hellmanが公開鍵暗号化の概念を取り込んだ１９７６年に導入された。彼らは、ｑ要素を有する有限フィールドＧＦ（ｑ）に渡って対数を計算する外見上の困難を利用する２者間の鍵合意のためのシステムを提案した。このシステムを用いて、２人のユーザは、対称鍵に同意することができる。そして、対称鍵は、言わば２者間の暗号化された通信のために用いられ得る。
【０００５】
鍵合意のためのDiffie-Hellmanシステムは、両者が共有された秘密を未だ有していないときに適用可能である。Diffie-Hellman鍵合意方法は、有限フィールドに渡る累乗演算を実行するような、リソースの多い数学的演算を必要とする。累指数及びフィールドサイズは大きくてもよい。これは、低リソースデバイスに対してあまり適さない鍵合意プロトコルをもたらす。一方、鍵合意プロトコルは、リソースを抑制されたデバイスにおいて非常に有益である。例えば、もののインターネット（internet of things）、ａｄ−ｈｏｃ無線ネットワーク等のようなアプリケーションエリアにおいて、鍵合意は、デバイス間のリンクを保護するために用いられ得る。他の例は、リーダと電子タグとの間、即ちカードリーダとスマートカードとの間、又は、タグリーダとタグ（例えば、ＲＦＩＤタグ又はＮＦＣタグ）との間の通信である。
【０００６】
所与の通信ネットワークにおけるネットワークデバイスのペアの間の安全な接続を設定する問題に対する他のアプローチは、C. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro及びM. Yungらによる"Perfectly-Secure Key distribution for Dynamic Conferences", Mathematics におけるSpringer Lecture Notes, Vol. 740, pp. 471-486, 1993 (Blundoと呼ばれる)において与えられる。
【０００７】
このシステムは、ｐ要素を有する有限フィールドＦにおける係数を伴う対称二変数多項式ｆ（ｘ，ｙ）を生成する、ネットワーク権限又は信頼できる第三者機関（ＴＴＰ；Trusted Third Party）とも呼ばれる中央権限を想定する。ここで、ｐは素数又は素数の累乗である。各デバイスは、Ｆにおける識別番号を有し、ＴＴＰによりローカル鍵材料が供給される。識別子
2016526851.tif 000003
を有するデバイスに関して、ローカル鍵材料は、多項式
2016526851.tif 000004
の係数である。デバイス
2016526851.tif 000005
がデバイス
2016526851.tif 000006
と通信することを望む場合、鍵
2016526851.tif 000007
を生成するためにその鍵材料を用いる。ｆが対称であるので、同じ鍵が生成される。ローカル鍵材料は秘密である。ローカル鍵材料の認識はシステムを直接危険にさらすだろう。とりわけ、これは、盗聴者が同じ共有鍵を取得するのを可能にするだろう。この方法は、デバイスのネットワークにおける各デバイスがそれ自身の固有の識別番号及びローカル鍵材料を有することを必要とする。
【０００８】
この鍵共有方式の問題は、攻撃者がｔ＋１又はそれ以上のデバイスの鍵材料を知っている場合に生じる。ここで、ｔは二変数多項式の次数である。そして、攻撃者は、多項式ｆ（ｘ，ｙ）を復元することができる。その時点でシステムの安全性は完全に壊される。任意の２つのデバイスの識別番号が与えられると、攻撃者は、デバイスのこのペアの間で共有される鍵を復元することができる。
【０００９】
"Method Of Generating A Cryptographic Key, Network And Computer Program Therefor"というタイトルをもつ米国特許出願２０１１／２０６２０１が参照される。Song Guoらによる"A Permutation-Based Multi-Polynomial Scheme for Pairwise Key Establishment in Sensor Networks"という論文が参照される。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
ネットワークデバイス間、とりわけ低いリソースネットワークデバイス間の鍵分配及び鍵共有のための改良されたシステムを有することが有利であるだろう。
【課題を解決するための手段】
【００１１】
鍵共有のためのネットワークデバイスを構成するためのシステムが提供される。本システムは、鍵材料取得部と、ネットワークデバイス管理部と、多項式操作ユニットとを有する。
【００１２】
鍵材料取得部は、電子形式においてパブリックグローバル低減多項式、二変数多項式の第１のプライベートセット及び低減多項式の第２のプライベートセットを取得するように構成される。第１のセットにおける各二変数多項式は、第２のセットの低減多項式に関連付けられる。
【００１３】
ネットワークデバイス管理部は、電子形式においてネットワークデバイスのための識別番号を取得するように構成される。
【００１４】
多項式操作ユニットは、一変数多項式のセットを取得する識別多項式に対して識別番号をマッピングすることにより、第１のプライベートセットの各特定の多項式に対して、識別多項式を特定の多項式に置換し、特定の多項式に関連付けられた低減多項式を法として低減することにより、一変数多項式のセットを合計することにより、第１及び第２のプライベートセットから一変数プライベート鍵多項式を計算するように構成される。
【００１５】
ネットワーク管理部は、生成された一変数プライベート鍵多項式及びパブリックグローバル低減多項式をネットワークデバイスに電子的に格納するように更に構成される。
【００１６】
本システムが、鍵共有のための少なくとも２つのネットワークデバイス、例えば第１及び第２のネットワークデバイスを構成しているときに、２つのネットワークデバイスは、対称の共有鍵に同意することができる。
【００１７】
第１のネットワークデバイスは、第２のネットワークデバイスにより共有鍵を決定するように構成されるよう提供される。第１のネットワークデバイスは、電子格納部、通信ユニット、多項式操作ユニット、及び、鍵導出デバイスを有する。
【００１８】
電子格納部は、鍵共有のためのネットワークデバイスを構成するためのシステムからの取得されるパブリックグローバル低減多項式及び一変数プライベート鍵多項式を格納する。また、格納は、第１のネットワークデバイスのための識別番号を格納する。
【００１９】
通信ユニットは第２のネットワークデバイスの識別番号を取得するように構成され、第２のネットワークデバイスは、第１のネットワークデバイスとは異なる。
【００２０】
多項式操作ユニットは、第２のネットワークデバイスの識別番号を識別多項式にマッピングし、識別多項式を一変数プライベート鍵多項式に置換し、パブリックグローバル低減多項式を法として置換する結果を減らすように構成される。
【００２１】
鍵導出デバイスは、パブリックグローバル低減多項式を法として減らす結果から共有鍵を導出するように構成される。
【００２２】
鍵共有システムのためのシステムは、鍵共有のためのネットワークデバイスを構成するためのシステムと、鍵共有のためのネットワークデバイスを構成するためのシステムにより構成される第１及び第２のネットワークデバイスとを有する。
【００２３】
各々が識別番号とこれらの識別番号のために生成される一変数秘密鍵多項式とを有する複数のネットワークデバイスからの２つのネットワークデバイスの任意のペアは、幾つかのリソースと共有鍵について協議することができる。２つのネットワークデバイスは、これらの識別番号のみを交換する必要があり、これら識別番号は、秘密を維持される必要はなく、多項式の計算を実行する必要もない。必要な計算のタイプは、大きな計算リソースを必要としないものであり、これは、この方法が低コスト高容量タイプのアプリケーションに適していることを意味する。現在のシステムは、幾つかの多項式（例えば、低減多項式）の係数のための有限フィールドを用い得るが、これらは、比較的小さいもの、２と同じくらいであっても選択され得る。
【００２４】
一変数秘密鍵多項式は、異なる多項式環に渡って評価される多項式を加算することにより取得される。結果として、一変数秘密鍵多項式とルート鍵材料との間の関係（即ち、第１及び第２のプライベートセット）は妨害される。１又はそれ以上の一変数秘密鍵多項式へのアクセスを有する攻撃者は、依然として第１及び第２のプライベートセットを取得することができない。これは、システムがネットワークデバイスの共謀に対して安全であることを意味する。
【００２５】
更に、導出された共有鍵へのアクセスについても、他のデバイスのローカル鍵材料を見つけるのは難しい。
【００２６】
グローバル低減多項式と同様に第２のプライベートセットにおける低減多項式の係数は、例えばｐ要素を有する有限の可換環又は有限フィールドＦから得られる整数係数を有する。この場合、ｐは、素数又は素数の累乗である。第１のプライベートセットにおける二変数多項式、一変数多項式及び秘密鍵一変数多項式の係数は、低減多項式により規定される多項式環から得られる係数を有する。
【００２７】
驚くべきことに、異なる多項式リングに渡る計算が混合されるにもかかわらず、２つのネットワークデバイスは依然として同じ共有鍵を一緒に取得することができる。
【００２８】
一実施形態において、識別番号のバイナリ表現は、少なくとも、共有鍵のバイナリ表現と同じくらい多くのビットを有する。より大きな鍵が必要である場合、システムは、一変数秘密鍵多項式及びそれ故に複数の共有鍵を取得するために複数回実行され得る。そして、複数の共有鍵は、より大きな鍵を生成するために、組み合わせられ得る（即ち連結され得る）。複数の共有鍵が生成されたより大きな共有鍵に組み合わせられる一実施形態において、識別番号は、好ましくは共有鍵より大きい。例えば、識別番号は、８倍より大きいか又は多くてもよい。一実施形態において、ネットワークデバイスは、１又はそれ以上の識別番号及び複数の一変数秘密鍵多項式を有する。一変数秘密鍵多項式の各々は、１又はそれ以上の識別番号のうち１つのために生成される。一例として、共有鍵は１６ビットであり得るのに対し、１又はそれ以上の識別番号は１２８ビットである。複数の共有鍵を連結することにより、適切な鍵長が取得されてもよい。例えば、１６ビットの８つの共有鍵は一緒に１２８ビットの共有鍵を与える。攻撃（とりわけ格子攻撃（lattice attack））は、得られた鍵ビットの数が識別番号におけるビットの数より小さい場合に非常により難しくなる。それ故に各々がより大きな識別番号から取得した複数の共有された小さな鍵を１つの共有された大きな鍵に組み合わせることにより、セキュリティは増大する。
【００２９】
一変数秘密鍵多項式の導出は、パブリックグローバル低減多項式とは異なる低減多項式を用いるので、言わば単一の有限フィールドにおいて機能するときに存在する数学的関係が妨害される。これは、多項式を解析するための通常の数学的ツール（例えば有限代数）はもはや適用しないことを意味する。せいぜい、攻撃者は、あまり効率的ではない構造（例えば格子）を用いるかもしれない。本方法は、直接的ペアワイズ鍵生成を可能にし、ネットワークデバイスの極めて高い番号（例えば１０＾５又はそれ以上のオーダ）の捕獲への復元である。
【００３０】
各低減多項式
2016526851.tif 000008
は、多項式環、例えば
2016526851.tif 000009
を規定する。それ故、二変数多項式の第１のプライベートセットの各多項式により、可換環は関連付けられる。ほとんどの実施形態において、多項式環は、幾つかの正の整数ｐのための有限の整数環
2016526851.tif 000010
に渡って規定される。典型的には、この対数係数ｐは、第２のセットにおける全ての多項式に対して同じになるだろう。しかしながら、対数係数ｐｉの第３のセットを規定することが可能であり、従って、第２のセットにおける各低減多項式により、第３のセットにおける低減対数係数が関連付けられる。識別多項式を置換することから取得される一変数多項式は、場合によっては、対数係数ｐ又は関連付けられた対数係数ｐｉを法として低減される。得られた鍵材料は、例えば生成により又は外部ソースから、対数係数を取得するように構成されてもよい。
【００３１】
一変数多項式のセットを合計することは、グローバル環において行われる。このグローバル環は、単純に
2016526851.tif 000011
（又は
2016526851.tif 000012
）であり得る。しかしながら、グローバル環は、例えば、
2016526851.tif 000013
又は
2016526851.tif 000014
であってもよい。数ｐは、パブリックなものであってもよく、各々のネットワークデバイスに格納されてもよい。
【００３２】
一実施形態において、本システムは、電子乱数生成部を有し、鍵材料取得部は、電子乱数生成部を用いてパブリックグローバル低減多項式の１又はそれ以上の係数を生成するように構成される。
【００３３】
一実施形態において、本システムは、電子乱数生成部を有し、鍵材料取得部は、電子乱数生成部を用いて第１のプライベートセットにおける二変数多項式の１又はそれ以上の係数を生成するように構成される。
【００３４】
一実施形態において、本システムは、電子乱数生成部を有し、鍵材料取得部は、電子乱数生成部を用いて第２のプライベートセットにおける低減多項式の１又はそれ以上の係数を生成するように構成される。
【００３５】
ランダムな生成は、根底にある問題の強力なインスタンスを生成する可能性が高い。根底にある問題は、いわゆる"隠された番号問題"に関連する。この種類の問題において、相手は、機密情報に基づいて計算の（部分的な）評価を取得する。そして、相手は、機密情報を復元する任務を負う。
【００３６】
鍵共有のためのシステムの一実施形態において、第１のプライベートセットにおける全ての多項式は、対称の二変数多項式である。斯様なシステムにおいて、任意のデバイスは、任意の他デバイスにより共有鍵を導出することができる。
【００３７】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、二変数多項式の第１のプライベートセットは、少なくとも２つの異なる二変数多項式を有する。好ましくは、少なくとも２つの多項式に関連付けられる低減多項式は異なる。異なる関連付けられた低減多項式により、第１のプライベートセットにおける少なくとも２つの多項式を有することは、複数の環に渡るいわゆる混合効果のための要件である。
【００３８】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、第１のプライベートセットの少なくとも１つの多項式は、前記少なくとも１つの多項式の２つの変数のうちの１つにおける少なくとも２の次数を有する。１を有するか、又は一次の第１のセットにおける全ての多項式でさえも有することは、容易なインスタンスを直接的にもたらさないが、しかしながら、根底にある難しい問題は、その多項式のバージョンの代わりに、古典的な隠れた数の問題まで削減する。隠れた数の問題の多項式のバージョンは、相当に難しく、それ故、暗号システムにとって好ましい。
【００３９】
一実施形態において、第１のセットは、異なる関連付けられた低減多項式を伴う、少なくとも二次の少なくとも２つの多項式を有する。
【００４０】
パブリックグローバル低減多項式の次数は、セキュリティパラメータである。一実施形態において、パブリックグローバル低減多項式の次数は、ネットワークデバイスが構成されるビットにおける共有鍵のサイズより大きい。パブリックグローバル低減多項式の次数は、より大きくてもよく、即ち、ビットにおける共有鍵のサイズの２倍より大きくてもよい。
【００４１】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、一変数秘密鍵多項式は、係数のリストとして、及び、標準形において表される。
【００４２】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、識別多項式を特定の多項式に置換して、前記特定の多項式に関連付けられた低減多項式を法として低減する結果は、合計する前に、係数のリストとして、及び、標準形において表される。
【００４３】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、多項式操作ユニットは、パブリックグローバル低減多項式を法として一変数多項式のセットを合計する結果を低減するように構成される。ネットワークデバイスは、グローバル低減多項式により規定される環において動作するので、このステップが実行された場合でも又はされない場合でも、導出された共有鍵の間で差を作らないだろう。しかしながら、この追加のステップは、第１及び第２のプライベートセットにおける秘密情報の一変数秘密鍵多項式における考えられる観察可能な残りを除去してもよい。
【００４４】
置換の前に、識別番号は、低減多項式により規定される適切な環により規定される環の一要素として理解されなければならない。このステップは、多数の手段において行われ得る。しかしながら、これを行うための最も容易なものの１つは、第１及び第２のセットにおける多項式を規定するために用いられる同じ基数を有する番号システムに識別番号を書き込むことである。基数が２である一実施形態において、これは、識別番号が一のビット列及びこれらのビット列として利用されてもよいことを意味する。ほとんどの現代のコンピュータにおいて、これは、追加の変換を必要としない。また、変換を回避することは、基数番号が２の累乗である場合に考えられる。しかしながら、基数番号が２又はその累乗ではない場合、その後、変換が必要とされ得る。
【００４５】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、識別番号を識別多項式にマッピングすることは、変換識別番号の桁を識別多項式の係数として割り当てることにより識別番号をマッピングすることを有する。
【００４６】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、識別番号を識別多項式にマッピングすることは、二進数からの識別番号を、２とは異なる基数番号を有する数に変換すること、及び、変換された識別番号の桁を識別多項式の係数として割り当てることにより識別番号をマッピングすることを有する。
【００４７】
混合効果は、低次数の単項に対して最少である。攻撃者が、識別多項式が近い多くのデバイスのための鍵材料を発見及び取得することができる場合、即ち、識別多項式間の差分が主として低次数の単項において生じる場合、そして、彼は、近い識別多項式により他のデバイスの鍵材料を復元することができるかもしれない。それ故、とりわけより小さな構成のシステムの潜在的な弱点は、識別番号の生成に関連し得る。この特定の弱点は実体化しなかったこと、及び、このタイプの攻撃はここで述べられるシステムに対して知られないことが強調されるべきである。それにもかかわらず、この攻撃ベクトルを低減することによりセキュリティを増大させるための幾つかの手段が存在する。
【００４８】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、識別番号（Ａ）を識別多項式にマッピングすることは、識別番号をハッシュすること、及び、例えば、場合により異なる数の基数にマッピングされた、前記のハッシュの結果の桁を、識別多項式の係数に割り当てることにより、前記のハッシュの結果を識別多項式の少なくとも部分に変換することを有する。例えば、ビットの識別番号は、ハッシュされてもよく、ビットに連結されてもよい。これは、潜在的な識別番号の全体範囲に渡って識別番号を広げ、これらの識別番号に対する特定の要件（例えばこれらが近いこと）を有する２つのデバイスを見つけるのを極端に難しくする。これをより安全に行うために、識別番号は、より多くのビットまで拡張されてもよい。例えば、ｂ´ビットの識別番号は、ハッシュされ、ｂビットに連結され得る（Ｂ´＜ｂ）。ハッシュ動作の後、識別多項式への通常のマッピングは、例えば桁を係数に割り当てることにより行われてもよい。
【００４９】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、識別番号（Ａ）を識別多項式にマッピングすることは、例えば、識別番号をハッシュし、前記のハッシュの結果の少なくとも部分を識別番号の最下位側に連結することにより、識別番号を拡張することを有する。
【００５０】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、ネットワークデバイスマネージャは、識別番号の少なくとも部分を生成することにより、ネットワークデバイスのための識別番号を取得する。この実施形態において、識別番号の全体又は部分は、システムにより生成され、ネットワークノードに格納される。識別番号を生成することは、ｂ´ビットのランダム列を生成することにより行われてもよい。識別番号を生成することは、より小さな識別番号の後にビットのランダム列を追加することにより行われてもよい。例えば、ネットワークデバイスは、ネットワークノードの識別番号を受信し、或る数（即ち、１０）のランダムビットを追加し、識別番号としての結果をネットワークノード上に格納してもよい。
【００５１】
ハッシュ関数に関して、Ｓｈａ−２５６，Ｒｉｐｅｍｄ−２５６等のような暗号ハッシュが用いられてもよい。
【００５２】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、鍵材料取得部は、共通の多項式を生成し、パブリックグローバル低減多項式と共通の多項式の倍数との間の差分として低減多項式を生成するように構成される。一実施形態において、ネットワーク管理部は、共通の多項式をネットワークデバイスに電子的に格納するように更に構成される。
【００５３】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、共通の多項式の倍数は、Ｍ−ａ（ｂ−１）より小さいか又は等しい次数を有する。ここで、Ｍは、パブリックグローバル低減多項式の次数であり、ａは、二変数多項式の第１のプライベートセットにおける多項式の最高の次数であり、ｂは、識別番号のビットの数である。次数に関するこの制限は、双方が同じ共有鍵を計算することを保証する。一実施形態において、共通の多項式の倍数は、各低減多項式に対してＭ−ａ（ｂ−１）より小さいか又は等しい次数を有する。
【００５４】
鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、共通の多項式の少なくとも１つの倍数が、Ｍ−２ａ（ｂ−１）より大きい次数を有する。この制限は、混合効果が得られることを保証し、これはセキュリティを増大させる。
【００５５】
第１のネットワークデバイスの一実施形態において、電子格納部は、一変数秘密鍵多項式、パブリックグローバル低減多項式及び共通の多項式を格納する。多項式操作ユニットは、共通の多項式を法としてパブリックグローバル低減多項式を法として低減する結果を更に低減するように更に構成される。共通の多項式を法として低減することは、共有鍵のサイズを適切な長さに削減するための一手段である。両者は、低減が共通の多項式を法とする場合、同じ共有鍵を導出する。
【００５６】
本発明の態様は、鍵共有のためのネットワークデバイスを構成するための方法に関する。本発明の態様は、第２のネットワークデバイスにより共有鍵を決定するための方法に関する。
【００５７】
一実施形態において、第１のネットワークデバイスは、共有鍵を用いるように構成される暗号化ユニットを有する。一実施形態において、暗号化ユニットは、共有された対称の鍵により電子メッセージを暗号化するように構成される暗号化ユニットを有する。一実施形態において、暗号化ユニットは、暗号化された電子メッセージを共有された対称の鍵により復号するように構成される復号ユニットを有する。
【００５８】
ネットワークデバイス、例えば第１又は第２のネットワークデバイス及び構成するデバイスは、電子デバイス、例えばセットトップボックス、コンピュータ等である。ネットワークデバイス、例えば第１又は第２のネットワークデバイスは、モバイル電子デバイス、例えば携帯電話機であってもよい。
【００５９】
本発明による方法は、コンピュータに実装された方法としてコンピュータ上で、若しくは専用のハードウェアにおいて、又は双方の組み合わせにおいて実装されてもよい。本発明による方法のための実行コードは、コンピュータプログラム製品上に格納されてもよい。コンピュータプログラム製品の例は、メモリデバイス、光学的格納デバイス、一体型回路、サーバ、オンラインソフト等を含む。好ましくは、前記プログラム製品は、該プログラム製品がコンピュータ上で実行されたときに、本発明による方法を実行するためのコンピュータ読み取り可能な媒体上に格納された非一時的プログラムコード手段を有する。
【００６０】
好ましい実施形態において、コンピュータプログラムは、コンピュータプログラムがコンピュータ上で実行されたときに本発明による方法の全てのステップを実行するように適合されたコンピュータプログラムコード手段を有する。好ましくは、コンピュータプログラムは、コンピュータ読み取り可能な媒体上に具現化される。
【００６１】
鍵共有のためのネットワークデバイスを構成するためのシステムが提供され、第１及び第２のネットワークデバイスは、これらの間の共有鍵を決定するように構成される。本システムは、パブリックグローバル低減多項式Ｎ（ｔ）、二変数多項式の第１のプライベートセットｆｉ（，）及び低減多項式の第２のプライベートセットＱｉ（ｔ）を電子形式において取得するための鍵材料取得部を有し、第１のセットにおける各二変数多項式により、第２のセットの低減多項式が関連付けられ、本システムは、ネットワークデバイスの識別番号Ａを識別多項式にマッピングすること、第１のプライベートセットの各特定の多項式に対して、識別多項式を特定の多項式ｆｉ（Ａ，）に置換し、特定の多項式に関連付けられた低減多項式を法として低減することにより、一変数多項式のセットを取得すること、並びに、一変数多項式のセットを合計すること、により、第１及び第２のプライベートセットから一変数秘密鍵多項式を計算するための多項式操作ユニットを有し、本システムは、生成された一変数秘密鍵多項式及びパブリックグローバル低減多項式Ｎ（ｔ）をネットワークデバイスに電子的に格納するように構成される。第１のネットワークデバイスは、一変数秘密鍵多項式、パブリックグローバル低減多項式Ｎ（ｔ）及びその識別番号Ａを格納する。第１のネットワークデバイスは、第２のネットワークデバイスの識別番号を識別多項式にマッピングし、識別多項式を一変数秘密鍵多項式に置換し、パブリックグローバル低減多項式Ｎ（ｔ）を法として前記の置換の結果を低減することから、共有鍵を導出する。
【００６２】
本発明のこれらの及び他の態様は、以下で述べられる実施形態から明らかになり、これらを参照して説明されるだろう。
【図面の簡単な説明】
【００６３】
【図１】鍵共有のためのネットワークデバイスを構成するためのシステム２００及び第１のネットワークデバイス３００の概略ブロック図である。
【図２】第１のネットワークデバイス３００及び第２のネットワークデバイス３５０の概略ブロック図である。
【図３ａ】鍵共有システム１００の概略ブロック図である。
【図３ｂ】鍵共有システム１０２の概略ブロック図である。
【図４】一体型回路４００の概略ブロック図である。
【図５】鍵共有のための、ネットワークデバイス３００を構成するための方法５００を示すフローチャートである。
【図６】第２のネットワークデバイス３５０により共有鍵を決定する方法６００を示すフローチャートを示す。
【発明を実施するための形態】
【００６４】
異なる図面において同一の参照番号を有するアイテムは、同じ構造的なフィーチャ及び同じ機能を有するか、又は、同じ信号であることに留意されるべきである。斯様なアイテムの機能及び／又は構造が説明された場合、詳細な説明においてその反復説明の必要がない。
【００６５】
本発明は、多くの異なる形式における実施形態を可能とする一方で、これらは、図面において示され、本開示が、本発明の原理の例示的なものであるとみなされ、本発明を示され述べられた特定の実施形態に限定することを意図しないという理解のもとで、１又はそれ以上の特定の実施形態がここで詳細に述べられるだろう。
【００６６】
図１は、鍵共有のためのネットワークデバイスを構成するためのシステム２００及び第１のネットワークデバイス３００の概略ブロック図である。
【００６７】
構成するためのシステム２００は、典型的には、一体型のデバイスとして実装される。例えば、構成するためのシステム２００は、サーバに含まれてもよい。構成するためのシステム２００は、ネットワーク（即ち、ワイヤレスネットワーク又はインターネット等）を介してネットワークデバイスを構成してもよい。しかしながら、構成するためのシステム２００は、ネットワークデバイスを製造するための製造デバイスにおいて一体化されてもよい。
【００６８】
構成するためのシステム２００は、鍵材料取得部２１０、ネットワークデバイス管理部２３０及び多項式操作ユニット２２０を有する。構成するためのシステム２００は、複数のネットワークデバイスによって動作することを意図される。図１は、１つの斯様なデバイス、第１のネットワークデバイス３００を示している。
【００６９】
構成するためのシステム２００は、ルート鍵材料とも呼ばれる秘密鍵材料を選択する。そして、構成するためのシステム２００は、複数のネットワークデバイスのためのローカル鍵材料を導出する。ローカル鍵材料は、ルート鍵材料及びネットワークデバイスのパブリック識別番号Ａから導出される。識別番号は、公式おいて
2016526851.tif 000015
とも呼ばれる。図１において、ネットワークデバイス３００は、識別番号３１０を格納する。
【００７０】
ローカル鍵材料は、特定のネットワークデバイスに対してプライベートである（即ち、１つの特定のネットワークデバイス及び場合により信頼されたデバイスに対してのみアクセス可能である）部分を有する。ローカル鍵材料は、共有鍵を得るために必要とされるにもかかわらず、秘密を維持するのにあまり重要でない部分を含んでもよい。
【００７１】
形容詞のパブリック及びプライベートの使用は、理解に役立つものとして意図される。全ての公開のデータに対するアクセスによっても、プライベートデータは、少なくともアプリケーションの安全が与えられるか又は鍵生成、暗号化及び復号のために必要とされるリソースと比較して不合理な高リソースを伴わないわけではなく、計算され得ない。しかしながら、"パブリック"は、対応するデータが構成するためのシステム２００及びネットワークデバイスより他の誰かに対して必ずしも利用可能であることを意味するものではない。とりわけ、信頼できない者からのパブリックグローバル低減多項式及び他のパブリックパラメータシークレットを保つことは、セキュリティを増大させる。同様に、プライベートデータへのアクセスは、そのデータを生成した又はそのデータを必要とする者に制限されてもよく、これはセキュリティを増大させる。しかしながら、信頼された者は、プライベートデータへのアクセスを可能にされてもよい。プライベートデータへのアクセスはセキュリティを低減させる。
【００７２】
これらのローカル鍵材料及び他者の識別番号を用いて、ネットワークデバイスは、これらの間の共有鍵に同意することができる。
【００７３】
鍵材料取得部２１０は、パブリックグローバル低減多項式（２１６，Ｎ（ｔ））、二変数多項式の第１のプライベートセット（２１２，ｆｉ（，））及び低減多項式の第２のプライベートセット（２１４，Ｑｉ（ｔ））を取得するように構成される。第１のセットにおける各二変数多項式は、第２のセットの低減多項式に関連付けられる。関連付けは、好ましくは１対１の関連付けである。各低減多項式（Ｑｉ及びＮ）は、即ち多項式環を例えば
2016526851.tif 000016
として分割することにより、可換環を規定する。
【００７４】
パブリックグローバル低減多項式２１６，Ｎ（ｔ）は、低減多項式２１４，Ｑｉ（ｔ）の各々とは異なる。好ましくは、パブリックグローバル低減多項式２１６，Ｎ（ｔ）の次数は、少なくとも低減多項式２１４，Ｑｉ（ｔ）の各々の次数と少なくとも同じか又はこれより大きい。
【００７５】
鍵材料取得部２１０は、鍵材料を取得するためにネットワークデバイスをとのインタラクションを必要としない。とりわけ、鍵材料取得部２１０は、識別番号を必要としない。構成するためのシステム２００は、鍵材料取得部２１０が多項式操作ユニット２２０とは異なる物理位置に配置される、分配されたシステムであってもよい。鍵材料取得部２１０は、鍵材料の全部または一部を生成し、及び／又は、外部ソースから鍵材料の全部又は一部を取得する。例えば、鍵材料取得部２１０は、外部ソースからパブリックグローバル低減多項式２１６を受信し、第１のプライベートセット２１２及び第２のセット２１４を生成するのに適している。後者は、全てのネットワークデバイスが固定されたパブリックグローバル低減多項式２１６によって製造されるのを可能にし、コストを削減する。
【００７６】
鍵材料取得部２１０は、電子乱数生成部を有してもよい。乱数生成部は、真の又は疑似の乱数生成部であってもよい。鍵材料取得部２１０は、例えば電子乱数生成部を用いて、パブリックグローバル低減多項式（Ｎ（ｔ））の１又はそれ以上の係数を生成してもよい。パブリックグローバル低減多項式はパブリックな情報であるが、ランダム性の導入は、システムを解析するのをより難しくする。
【００７７】
鍵材料取得部２１０は、例えば電子乱数生成部を用いて、第１のプライベートセットにおける二変数多項式（１２２，ｆｉ（，））の１又はそれ以上の係数を生成してもよい。鍵材料取得部２１０は、この態様において二変数多項式の全てを生成してもよい。鍵材料取得部２１０は、これらの多項式（即ち、２又は３以上）の最大の次数を用いてもよく、次数よりランダムな係数を生成してもよい。ランダムな係数は、整数環、例えば番号（例えば素数）を法とした整数からランダムに選択されてもよい。
【００７８】
鍵材料取得部２１０は、電子乱数生成部を用いて、第２のプライベートセットにおける低減多項式（Ｑｉ（ｔ））の１又はそれ以上の係数を生成してもよい。低減多項式が単純化できないことは必要ではない。しかしながら、これらは、抵抗を増大させるために単純化できないように選択されてもよい。単純化できない多項式は、環の種であるフィールドをもたらす。同じ第１及び第２のプライベートセット、パブリックグローバル低減番号及び低減対数係数は、鍵を共有するために後に必要とする全てのネットワークデバイスに対して用いられる。
【００７９】
プライベートセット２１２における多項式の数及び多項式の次数又は最大次数のような、プライベートなセット２１２の幾つかの態様を規定することが便利である。また、多項式における係数の幾つかが、例えば格納要件を削減するためにゼロであることが規定されてもよい。
【００８０】
第１のセットは、２つの同等の多項式を含んでもよい。しかしながら、これは、関連付けられた低減多項式が異ならない限り、セットが大きさについて低減され得るよう動作するだろう。従って、典型的には、第１のセットにおける２又はそれ以上の二変数多項式が同じであるときはいつでも、関連付けられた低減多項式（即ち、元の環）は異なる。
【００８１】
二変数多項式の第１のプライベートセット（ｆｉ（，））は、対称の二変数多項式のみを有する。対称の多項式のみを用いることは、各ネットワークデバイスが構成されたネットワークデバイスの任意の他のネットワークデバイスにより共有鍵について同意することができるという利点を有する。しかしながら、二変数多項式の第１のプライベートセットは、１又はそれ以上の非対称の多項式を含んでもよい。これは、デバイスが２つのグループに分割され得るという効果を有する。１つのグループからのデバイスは、第２のグループのデバイスによってのみ共有鍵について同意することができる。
【００８２】
鍵材料取得部２１０は、公式においてｆｉ（，）とも呼ばれる、二変数多項式２１２の第１のプライベートセットを電子形式において得るように構成される。以下で述べられる実施形態は、セットにおける全ての二変数多項式２１２が対称であると想定する。
【００８３】
対称の二変数多項式は、プレースホールダとしての２つの形式的変数によってｆｉ（ｘ，ｙ）として記録されてもよい。対称の二変数多項式は、ｆｉ（ｘ，ｙ）＝ｆｉ（ｙ，ｘ）を満たす。この要件は、例えば単項ｘａｙｂの係数は単項ｘｂｙａの係数に等しいという、係数に関する要件に変換する。
【００８４】
第１のプライベートセット２１２における多項式の数は、アプリケーションに依存して異なるように選択されてもよい。本システムは、第１及び第２のセットが単一の多項式のみを含むときに機能するだろう。斯様なシステムにおいて、鍵は、正常に共有されてもよく、適度なレベルのセキュリティを与えてもよい。しかしながら、（以下で説明される）異なる環を介して混合するセキュリティ上の利点は、第１及び第２のセットがこれらにおいて少なくとも２つの多項式を有するときにのみ実現される。プライベートセット２１２は、少なくとも１つの二変数多項式を有する。鍵合意デバイス１００を開始する一実施形態において、プライベートセット２１２は１つの多項式から成る。プライベートセット２１２において１つの多項式のみを有することは、複雑性、格納要件を低減し、速度を増大させる。しかしながら、プライベートセット２１２において１つだけの多項式を有することは、プライベートセット２１２において２又はそれ以上の多項式を有するより安全であるとはみなされない。斯様な一多項式システムは、以下で述べられる合計における追加の混合から利益を得ないためである。しかしながら、鍵共有は、正しく機能するだろう、及び、低セキュリティのアプリケーション及び／又は低い値に対して十分に安全であるとみなされる。
【００８５】
剰余において、我々は、プライベートセット２１２が少なくとも２つの対称の二変数多項式を有することを想定するだろう。一実施形態において、多項式の少なくとも２つは異なり、又は全てであっても異なる。これは、システムの分析をかなり複雑にする。これは必要ではないが、プライベートセット２１２は、２つの同等の多項式を有してもよく、これら２つの多項式が異なる環を介して評価される場合、合計ステップにおける混合から依然として利益を与えてもよい。この点は更に以下で述べられるだろう。一実施形態において、プライベートセット２１２は、異なる関連付けられた低減多項式に関連付けられる少なくとも２つの同等の多項式を有する。第１のセットにおいて２又はそれ以上の同等の多項式を有することは、格納要件を低減する。一実施形態において、第２は、少なくとも２つの多項式を有し、第２のセットにおける全ての多項式は異なる。
【００８６】
プライベートセット２１２における多項式は異なる次数であってもよい。対称の二変数多項式の次数によれば、我々は、２つの変数のうちの１つにおける多項式の次数を意味するだろう。例えば、ｘ２ｙ２+２ｘｙ+１の次数は、ｘの次数が２であるので、２に等しい。多項式は、各変数において同じ次数を有するように選ばれてもよい。プライベートセット２１２における多項式が対称である場合、次数は他の変数において同じになるだろう。
【００８７】
プライベートセット２１２における多項式の次数は、アプリケーションに依存して異なるように選択されてもよい。プライベートセット２１２は、次数１又はそれ以上の少なくとも１つの対称の二変数多項式を有する。一実施形態において、プライベートセット２１２は、次数１の多項式のみを有する。プライベートセット２１２において線形多項式のみを有することは、複雑性、格納要件を低減し、速度を増大させる。しかしながら、プライベートセット２１２において次数１の多項式のみを有することは、プライベートセット２１２において少なくとも２の次数の少なくとも１つの多項式を有するよりは、あまり安全であるとはみなされない。斯様なシステムがかなり線形であるためである。そうでもあっても、プライベートセット２１２における複数の多項式が異なる環に渡って評価される場合、プライベートセット２１２における全ての多項式がそうである場合であっても、生ずる暗号化は線形ではない。一実施形態において、プライベートセット２１２は、次数２又はそれ以上の、少なくとも１つの、好ましくは２つの多項式を有する。しかしながら、鍵生成、暗号化及び復号化は、次数１の多項式のみが用いられた場合に正しく動作するだろう、及び、低セキュリティのアプリケーション及び／又は低い値に対して十分に安全であるとみなされる。
【００８８】
次数０によりプライベートセット２１２において１又はそれ以上の多項式を有することは、より高い次数を有する多項式が充分なセキュリティを与える限り、システムに影響を与えないだろう。
【００８９】
中間のセキュリティのアプリケーションに関して、プライベートセット２１２は、次数２の２つの対称の二変数多項式を有してもよく、又はこれらから成っていてもよい。より高いセキュリティのアプリケーションに関して、プライベートセット２１２は、２つの対称の二変数多項式、即ち、次数２のものと次数が２よりも大きいもの（即ち３のもの）とを有してもよく、又はこれらから成っていてもよい。多項式及び／又はこれらの次数の数を増大させることは、増大されたリソース消費を犠牲にしてセキュリティを更に増大させるだろう。
【００９０】
好ましくは、任意の２つの低減多項式の差分が共通の多項式の除数を有するように、低減多項式が選択される。例えば、低減多項式及びパブリックグローバル低減多項式を生成するための１つの手段は、以下の通りである。
−  最初に、例えば規定された次数のランダムな多項式として、パブリックグローバル低減多項式Ｎ（ｔ）を生成する。
−  共通の多項式
2016526851.tif 000017
を生成する。
−  各低減多項式に関して、多項式
2016526851.tif 000018
を生成し、低減多項式Ｑｉ（ｔ）を差分
2016526851.tif 000019
として生成する。
【００９１】
共通の多項式の次数は、所望のシステムセキュリティに比例して選択されてもよい（例えば同等）。例えば、共通の多項式
2016526851.tif 000020
の次数は、生成された共有鍵におけるビットの数に等しくなるように選ばれてもよい。１つのオプションは、ｂに等しい共通の多項式
2016526851.tif 000021
の次数を選択することである。パブリックグローバル低減多項式の次数は、Ｍと呼ばれる。この次数は、共通の多項式のものより大きくなるように選択される。例えば、良好な選択は、
2016526851.tif 000022
としてＭ又はそれ以上を選択することである。ここで、ａは、二変数多項式の第１のプライベートセットにおける多項式の最も高い次数であり、ｂは、識別番号におけるビットの数である。一実施形態において、ネットワーク管理部は、共通の多項式をネットワークデバイスに電子的に格納するように更に構成される。
【００９２】
更に、共通の多項式
2016526851.tif 000023
の各倍数は、好ましくは、Ｍ−ａ（ｂ−１）よりも小さいか又はこれに等しい次数を有する。ここで、Ｍは、パブリックグローバル低減多項式Ｎ（ｔ）の次数である。混合を向上させるために、共通の多項式
2016526851.tif 000024
の少なくとも１つの倍数は、Ｍ−２ａ（ｂ−１）より高い次数を有する。
【００９３】
商業レベルのセキュリティに関して、以下のパラメータが用いられてもよい。これらは一例であり、値、より高い値及びより低い値が考えられることに注意されたい。第１のプライベートセットにおける多項式の次数は２として利用されてもよい（ａ＝２）。識別番号は、ｂビットを有する（即ちｂ＝１２８）。生成された共有鍵のサイズは、ｂビットに等しいものとして利用される（即ち１２８ビット）。低減多項式は、次数ｂの共通の多項式
2016526851.tif 000025
から生成される（例えば１２８ビット）。次数
2016526851.tif 000026
を利用する（従って、Ｍ＝６３５ビット）。多項式
2016526851.tif 000027
は、少なくともゼロ及び多くてもａ（ｂ−１）−１の次数によってランダムに選択されてもよい（即ち０〜２５３）。第１のプライベートセットｍにおける多項式の数は、２又はそれ以上として利用される。一般に、第１のセットにおける多項式の数は、２ａ（ｂ−１）より小さい。ａのより高い値又は
2016526851.tif 000028
のより低い値は、セキュリティを更に増大させるために必要とされてもよい。
【００９４】
鍵材料取得部２１０は、ソフトウェアにおいて若しくはハードウェアにおいて、又は、その組み合わせにおいてプログラムされてもよい。鍵材料取得部２１０は、多項式操作のための多項式操作ユニット２２０によりリソースを共有してもよい。
【００９５】
ネットワークデバイス管理部２３０は、ネットワークデバイス３００のために、識別番号３１０を電子形式において取得するように構成される。ネットワークデバイス管理部２３０は、ネットワークデバイスから識別番号を受信してもよい。例えば、ネットワークデバイス管理部２３０は、ネットワークを介して識別番号を受信するための通信ユニットを有してもよく、用いてもよい。例えば、ネットワークデバイス管理部２３０は、識別番号を無線信号として受信するためのアンテナを有してもよい。識別番号は、多数のビットとして表されてもよく、典型的には、識別番号におけるビットの数は、少なくとも共有鍵におけるビットの数と同じくらいの大きさである。
【００９６】
多項式操作ユニット２２０は、第１のネットワークデバイス３００から受信された第１及び第２のプライベートセット及び識別番号から一変数秘密鍵多項式２２８を計算するように構成される。一変数秘密鍵多項式及びパブリックグローバル低減多項式は、ローカル鍵材料の部分である。
【００９７】
多項式操作ユニット２２０は、以下のように一変数秘密鍵多項式２２８を計算してもよい。最初に、識別番号Ａは、識別多項式Ａ（ｔ）に変換される。構成するためのシステム２００及びネットワークデバイスの全ては、同じマッピングを用いる。システムが二進数を介して動作する場合、このマッピングは、ビットを識別多項式の係数に単純にマッピングしてもよい。システムが異なる数のシステム（即ち番号ｐを法とする整数）を介して動作する場合、Ａは、基数ｐを有する数に変換されてもよい。次に、基数ｐ番号として書き込まれた識別番号の桁は、識別多項式の係数として用いられてもよい。我々は、説明を簡単にするため後者のマッピングをここで想定するだろう。
【００９８】
しかしながら、マッピングは、より複雑になってもよい。例えば、マッピングは、識別番号を最初にハッシュし、言わばｂビットに連結してもよく、次に、先に述べた通りのマッピングが行われてもよい。これは、識別番号がシステムにおいて"ランダム"に機能することを保証する。とりわけネットワークデバイスが特定の順序に従う所与の識別番号である場合（例えばシリアル番号）、斯様なランダム化ステップは、格子攻撃が簡素化しないことを保証するために望ましい。識別番号のサイズが共有鍵のものより大きい場合、ハッシュのステップは望ましい。マッピングにおけるハッシュのステップは必要でない。例えば、識別番号が高いエントロピを有する場合、これらは省略されてもよい。
【００９９】
非ランダム識別番号に関する潜在的な弱点を減少させるための他の手段は、例えば識別番号Ａの識別多項式へのマッピングの部分として、以下のものを含む。一実施形態において、識別番号はハッシュされ、その結果は、例えば場合により異なる番号基数にマッピングされたハッシュの結果の桁を識別多項式の係数に割り当てることにより、識別多項式の少なくとも部分に変換される。例えば、ｂビットの識別番号は、ハッシュされ、所望のビット数（例えばｂビット）まで切り捨てられてもよい。鍵共有のためのネットワークデバイスを構成するためのシステムの一実施形態において、識別番号Ａを識別多項式にマッピングすることは、例えば識別番号をハッシュし、ハッシュの結果の少なくとも部分を識別番号の最下位側に追加することにより、識別番号を拡張することを有する。
【０１００】
更に、識別番号は、より多くのビットまで拡張されてもよい。例えば、Ｂ´ビットの識別番号は、例えばハッシュ及び／又はｂビット（ｂ´＜ｂ）への連結により、拡張され得る。拡張動作の後、識別多項式への通常のマッピングは、例えば桁を係数に割り当てることにより行われ得る。例えば、識別番号Ａは、Ｈ（Ａ）又は
2016526851.tif 000029
にマッピングされ得る。Ｈは、ハッシュを示し、
2016526851.tif 000030
は、連結を示す。連結は、ＬＳＢ側で行われる。
【０１０１】
一変数多項式は、識別多項式Ａ（ｔ）を第１のプライベートセットにおける多項式の各々に置換することにより取得される。二変数多項式の１つだけの変数のための値を置換することにより、二変数多項式は、一変数多項式まで低減する。そして、生ずる一変数多項式は、識別多項式Ａ（ｔ）が置換された二変数多項式に関連付けられた低減多項式を法として低減される。一変数多項式の生ずるセットは合計される。
【０１０２】
ｆｉ（ｘ，ｙ）は、第１のプライベートセットにおける二変数多項式のうちの１つであると仮定する。この多項式の係数は、環
2016526851.tif 000031
から得られる。即ち、第１のセットにおける多項式の係数は、それ自身、多項式環からの得られる多項式である。斯様な多項式は、３次元アレイとしてメモリにおいて表されてもよい。アレイの２次元は、ｆｉの単項の次数を表し、３次元は、前記係数を表す。簡潔さのために、変数ｘ及びｙは、第１のセットにおける多項式の対称の変数を表すために用いられ、変数ｔは、多項式環における対称の変数を表すために用いられる。
【０１０３】
置換の後、多項式操作ユニット２２０は、ｆｉ（Ａ（ｔ），ｙ）を取得する。多項式操作ユニット２２０は、この項法Ｑｉ（ｔ）を低減するように更に構成される。係数は、例えば対数係数ｐを低減することにより、システムが動作するフィールド（例えばＺｐ）において低減される。好ましくは、多項式操作ユニット２２０は、その結果を標準形（即ち予め決められた規格化された表現）に導く。適切な標準形は、単項の次数によりソートされる係数の表現である。代わりに、置換は、ｙに対するものであってもよい。
【０１０４】
第１のセットが対称の多項式のみを含む場合、識別多項式Ａ（ｔ）の置換は、二変数多項式の２つの変数のうちのいずれの１つにおけるものであってもよい。しかしながら、置換が非対称の多項式において行われる場合、より多くのケアが必要である。例えば、多項式操作ユニット２２０は、第１のネットワークデバイス３００が第１又は第２のグループにあるかを得るように構成されてもよい。第１及び第２のグループは、二変数多項式の第１及び第２の変数にそれぞれ関連付けられる。第１のグループにおけるネットワークデバイスに関して、第１の変数が常に用いられる。第２のグループにおけるネットワークデバイスに関して、第２の変数が常に用いられる。
【０１０５】
図１は、この機能を実装するための１つの考えられる手段を示す。図１は、置換ユニット２２２、多項式低減ユニット２２４、多項式加算ユニット２２６及び一変数多項式２２８のセットの合計を示している。これらは、以下の通りに機能し得る。置換ユニット２２２は、識別多項式を第１のセットの二変数多項式に置換する。置換ユニット２２２は、その結果を標準形に導くために条件を収集してもよいが、これは待ってもよい。多項式低減ユニット２２４は、置換の結果を受信し、置換された二変数多項式に関連付けられた低減多項式を法としてこれを低減する。
【０１０６】
識別多項式Ａ（ｔ）を特定の多項式ｆｉ（Ａ，）に置換し、該多項式に関連付けられた低減多項式を法として低減した結果は、多項式加算ユニット２２６による合計の前に、標準形において係数のリストとして表される。
【０１０７】
多項式加算ユニット２２６は、低減された一変数多項式を受信し、これらを加算部２２８において中間結果に加算する。加算部２２８は、一変数秘密鍵多項式の生成の前に０にリセットされた。
【０１０８】
第１のプライベートセットの全ての多項式がこの手法において処理されるときに、加算部２２８の結果は、一変数秘密鍵多項式として用いられてもよい。（言わば加算部２２８における）生ずる一変数秘密鍵多項式は、係数のリストとして、及び、標準形において表されてもよい。
【０１０９】
ネットワークデバイス管理部２３０は、生成された一変数秘密鍵多項式２２８及びパブリックグローバル低減多項式２１６，Ｎ（ｔ）をネットワークデバイスにおいて電子的に格納するように更に構成される。一変数秘密鍵多項式２２８及び彼の識別番号を用いて、第１のネットワークデバイス３００は、同じルート材料から構成される他のデバイスと鍵を共有することができる。
【０１１０】
多項式操作ユニット２２０がソフトウェアにおいて実装され得るにもかかわらず、多項式操作ユニット２２０は、とりわけハードウェア（特定の多項式低減ユニット２２４）における実装に適している。
【０１１１】
図１は、第１のネットワークデバイス３００から識別番号メッセージ２３２を受信する多項式操作ユニット２２０を示している。第１のネットワークデバイス３００は、鍵材料取得部２１０からパブリックグローバル低減多項式メッセージ２３４を受信し、多項式操作ユニット２２０から一変数秘密鍵多項式メッセージ２３６を受信する。これらのメッセージは、典型的には、ネットワークデバイス管理部２３０を介して送受信される。一変数秘密鍵多項式メッセージ２３６及びパブリックグローバル低減多項式メッセージ２３４は、単一のメッセージにおいて組み合わせられてもよい。
【０１１２】
構成するためのシステム２００は、第１のネットワークデバイス３００のための識別番号を生成することにより識別番号を取得するように構成されてもよい。斯様な設定は、工場によく適している。この場合、第１のネットワークデバイス３００は、識別番号メッセージ２３２を、送信する代わりに設定システム２００から受信する。即ち、鍵材料取得部２１０又は多項式操作ユニット２２０から識別番号メッセージ２３２を受信する。
【０１１３】
図２は、第１のネットワークデバイス３００及び第２のネットワークデバイス３５０の概略ブロック図である。第１のネットワークデバイス３００及び第２のネットワークデバイス３５０は、共有鍵を一緒に決定するように構成される。
【０１１４】
第２のネットワークデバイス３５０は、ネットワークデバイス３００として同じ設計であってもよい。我々は、第１のネットワークデバイス３００のみを詳細に述べ、第２のネットワークデバイス３５０は同じ又は同様であり得る。図２は、第２のネットワークデバイス３５０が識別番号３５５を格納することのみを示している。第２のネットワークデバイス３５０の識別番号３５５は、パブリックであり、鍵を共有するためにネットワークデバイス３００と交換され得る。また、第２のネットワークデバイス３５０は、ローカル鍵材料（図示省略；とりわけ識別番号３５５に対応する一変数秘密鍵多項式）を必要とする。
【０１１５】
第１のネットワークデバイス３００は、電子格納部３２０、通信ユニット３４２、多項式操作ユニット３３０及び鍵導出デバイス３４０を有する。
【０１１６】
格納部３２０は、一変数秘密鍵多項式３１２及びパブリックグローバル低減多項式３１４，Ｎ（ｔ）を格納する（両方ともシステム２００のような鍵共有のためのネットワークデバイスを構成するためのシステムから取得される）。また、格納３２０は、一変数秘密鍵多項式３１２を生成するために用いられた識別番号３１０，Ａを格納する。格納３２０は、フラッシュメモリのようなメモリ（即ち不揮発性及び書き込み可能なメモリ）であってもよい。格納部３２０は、他のタイプの格納部（即ち、ハードディスクのような磁気記憶装置）であってもよい。格納部３２０は、追記型メモリであってもよい。
【０１１７】
通信ユニット３４２は、第２のネットワークデバイス３５０の識別番号３５５を取得するように構成される。通信ユニット３４２は、有線接続、Ｗｉ−Ｆｉ、Ｂｌｕｅｔｏｏｔｈ又はＺｉｇｂｅｅ接続として実装されてもよい。通信ユニット３４２は、データネットワーク（インターネット）を介した接続によって実装されてもよい。
【０１１８】
多項式操作ユニット３３０は、第２のネットワークデバイスの識別番号を識別多項式Ａ（ｔ）にマッピングするように構成される。第１のネットワークデバイス３００及びネットワークデバイスの全ては、第１のネットワークデバイス３００により用いられたものと同じマッピングを用いる。マッピングは、同じハードウェア及び／又はアルゴリズムを用いてもよい。多項式操作ユニット３３０は、識別多項式Ａ（ｔ）を一変数秘密鍵多項式に置換し、パブリックグローバル低減多項式Ｎ（ｔ）を法として置換の結果を低減するように構成される。多項式操作ユニット３３０は、置換ユニット２２２及び多項式低減ユニット２２４と同様のハードウェア又はソフトウェアを用いてもよい。第１のネットワークデバイス３００は、第１及び第２のプライベートセットへのアクセスを有しないことに留意されたい。
【０１１９】
共有鍵のサイズを更に低減するために、更なる低減が行われてもよい。斯様な更なる低減は、両者が同じ共有鍵を取得することを保証するために必要とされてもよい。
【０１２０】
例えば、電子格納部３２０は、共通の多項式
2016526851.tif 000032
を更に格納してもよい。多項式操作ユニット３３０は、パブリックグローバル低減多項式を法として低減した結果を共通の多項式を法として更に低減するように更に構成される。共通の多項式を法として低減することは、共有鍵のサイズを適切な長さまで低減するための１つの手段である。故に、鍵は、以下のように計算されてもよい。ネットワークノードは、他のノードの（対称の変数ｔにおける）識別多項式をそのプライベート一変数多項式に置換し、多項式
2016526851.tif 000033
を法として（変数ｔにおける）生ずる多項式の残りを計算する。結果は、最大でも次数
2016526851.tif 000034
の多項式である。二進数の場合において、この多項式の係数は、
2016526851.tif 000035
ビットの列に連結され、識別子はｂビットである。
【０１２１】
鍵導出デバイス３４０は、パブリックグローバル低減多項式を法とした低減の結果から共有鍵を導出するように構成される。共有鍵は、いわゆる対称の鍵である。低減で生ずるものは、多項式環における多項式である。この結果は、（その係数を連結することにより）鍵としてほぼ直接的に用いられてもよい。
【０１２２】
低減の結果から共有鍵を導出することは、鍵導出機能のアプリケーションを含んでもよい（例えば、OMA DRM Specification of the Open Mobile Alliance (OMA-TS-DRM-DRM-V2_0_2-20080723-A, section 7.1.2 KDF)において規定される機能ＫＤＦ及び類似の機能）。
【０１２３】
図２は、第１のネットワークデバイス３００におけるオプショナルな暗号化ユニット３４５を更に示している。暗号化ユニット３４５は、共有鍵を用いるように構成される。例えば、暗号化ユニット３４５は、共有された対称の鍵により電子メッセージを暗号化するように構成された暗号化ユニットであってもよい。例えば、暗号化ユニット３４５は、共有された対称の鍵により電子メッセージを復号するように構成された復号ユニットであってもよい。
【０１２４】
多項式環を用いる重要な利点は、第１のネットワークデバイス３００と第２のネットワークデバイス３５０との間で取得される共有鍵が常に同じであるということである。幾つかの鍵共有システムによれば、共有鍵は、第１のネットワークデバイス３００と第２のネットワークデバイス３５０との間で時々異なることが考えられた。この可能性は、鍵確認データを介して解決され得るが、現在のシステムについては、この可能性は問題ではない。
【０１２５】
図３ａは、鍵共有システム１００の概略ブロック図である。
【０１２６】
鍵共有システム１００は、構成するためのシステム２００及び複数のネットワークデバイスを有する。ネットワークデバイス３００，３５０及び３６０が示されている。ネットワークデバイスは、構成するためのシステム２００から、識別番号、一変数秘密鍵多項式及びグローバル低減多項式を各々受信する。この情報を使用して、これらは、共有鍵に同意することができる。例えば、第１のネットワークデバイス３００及び第２のネットワークデバイス３５０は、それぞれこれらの識別番号を他者に送る。そして、これらは共有鍵を計算することができる。第１のネットワークデバイス３００と第２のネットワークデバイス３５０との間の通信（及び全体的な低減多項式さえも）の認識をもつ誰かは、不合理に大きなリソースを用いることなく、これらの共有鍵を取得することはできない。デバイス３６０でさえも、デバイス３００とデバイス３５０との間で共有される鍵を導出することができない。
【０１２７】
図３ｂは、類似の鍵共有システム１０２の概略ブロック図である。システム１０２は、ネットワークデバイスがこれらの識別番号を設定サーバ１１０から受信することを除いて、システム１００と同じである。そして、ネットワークデバイスは、これらの識別番号を送ることにより構成するためのシステム２００に登録する。デバイス２６０でさえも、デバイス３００とデバイス３５０との間で共有された鍵を取得することができない。
【０１２８】
設定サーバ１１０は、他の目的のためにも用いられる識別番号を割り当ててもよい。例えば、設定サーバ１１０は、ＭＡＣアドレスのようなネットワークアドレスを割り当ててもよい。ネットワークアドレスは、第２のネットワークノードから自身までのネットワークトラフィックのルートを決めるためのネットワークノードにより用いられる。しかしながら、ネットワークアドレスは、識別番号の２倍であってもよい。この場合、ネットワークノードは、彼のネットワークアドレスをシステム２００において利用可能にし、一変数秘密鍵多項式を受信し、これは、ネットワークノードがそのネットワークアドレスを識別番号として用いて暗号化された通信に関与するのを可能にする。典型的にネットワークノードにより受信されるメッセージは、第２のネットワークノードのネットワークアドレスを含み、従って、ネットワークは、暗号化された応答により直ちに応答することができるため、これは特に便利である。鍵確認ステップが必要とされないためである。
【０１２９】
設定サーバ１１０は、近い識別番号、即ち最も重大なビットの多く又は全てを共有する識別番号を回避することによりシステムのセキュリティを増大させるために識別番号を生成してもよい。例えば、サーバ１１０は、識別番号をランダムに生成してもよい（即ち、真のランダム又は疑似ランダム）。また、予め決められた数のランダムなビットを識別番号（１０ビット）に追加することが十分である。識別番号は、Ａ１がランダムではなく（シリアル番号、ネットワークアドレス等）Ａ２がランダムである形式
2016526851.tif 000036
を有してもよい。Ａ２は、ランダム番号生成部により生成されてもよい。また、Ａ２は、Ａ１をハッシュすることにより生成されてもよい。鍵のついたハッシュ（ＨＭＡＣ）が用いられる場合、Ａ２は、鍵へのアクセスを伴うことなく両者にとってランダムとは区別がつかない。鍵は、サーバ１１０により生成及び格納されてもよい。
【０１３０】
サーバ１１０は、システム２００に含まれてもよい、例えばネットワーク管理部２３０に取り込まれてもよい。
【０１３１】
図４は、一体型回路４００の概略ブロック図である。一体型回路４００は、プロセッサ４２０、メモリ４３０及びＩ／Ｏユニット４４０を有する。一体型回路４００のこれらのユニットは、バスのような相互接続４１０を介して互いの間で通信することができる。プロセッサ４２０は、ここで述べられる方法を実行するためにメモリ４３０に格納されたソフトウェアを実行するように構成される。この手法において、一体型回路４００は、構成するためのシステム２００として、又は、第１のネットワークデバイス３００のようなネットワークデバイスとして、構成されてもよい。メモリ４３０の部分は、パブリックグローバル低減多項式、二変数多項式の第１のプライベートセット、低減多項式の第２のプライベートセット、識別番号、簡単なメッセージ及び／又は必要とされる暗号化されたメッセージを格納してもよい。
【０１３２】
Ｉ／Ｏユニット４４０は、例えば二変数多項式２１２の第１のプライベートセットのような鍵データ及び場合によりサイズ、次数、対数係数等のような関連したパラメータを受信するために、又は、暗号化された及び／又は認証されたメッセージを送受信するために、デバイス２００又は３００のような他のデバイスと通信するために用いられてもよい。Ｉ／Ｏユニット４４０は、無線通信のためのアンテナを有してもよい。Ｉ／Ｏユニット４４０は、有線通信のための電気的インタフェースを有してもよい。
【０１３３】
一体型回路４００は、コンピュータ、携帯電話機のようなモバイル通信デバイス等において一体化されてもよい。また、一体型回路４００は、例えばＬＥＤデバイスによって構成された照明デバイスにおいて一体化されてもよい。例えば、ネットワークデバイスとして構成され、ＬＥＤのような照明装置により構成された一体型回路４００は、共有された対称の鍵により暗号化されたコマンドを受信してもよい。
【０１３４】
照明デバイスに取り込まれた複数のネットワークデバイスは、暗号化されたネットワークのノードを形成してもよく、リンクは、ノード間の共有鍵を用いて暗号化される。
【０１３５】
多項式操作は、メモリ４３０に格納された多項式操作ソフトウェアにより指示されるようにプロセッサ４２０により実行されてもよいが、一体型回路４００がオプショナルな多項式操作ユニット４５０によって構成される場合、鍵生成及び一変数多項式を計算するタスクはより速くなる。この実施形態において、多項式操作ユニット４５０は、置換及び低減動作を実行するためのハードウェアユニットである。
【０１３６】
典型的には、デバイス２００及び３００は、各々、デバイス２００及び３００に格納された適切なソフトウェアを実行するマイクロプロセッサ（図示省略）を有する。例えば、ソフトウェアは、ダウンロードされてもよく、及び／又は、対応するメモリ（例えばＲＡＭのような揮発性メモリ、又は、Ｆｌａｓｈ（図示省略）のような不揮発メモリ）に格納されてもよい。代わりに、デバイス２００及び３００は、完全に又は部分的に、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）として、プログラム可能な論理において実装されてもよい。
【０１３７】
以下に、鍵共有のためのシステムの一実施形態のより数学的説明が与えられる。Ｒ０，Ｒ１...，Ｒｍは、別個の可換環である。
2016526851.tif 000037
（０≦ｉ≦ｍ）は、ＺからＲｉまでのマッピングである。
2016526851.tif 000038
（１≦ｉ≦ｍ）は、ＲｉからＲ０までのマッピングである。１≦ｉ≦ｍに関して、ｆｉは、
2016526851.tif 000039
からの関数である。簡素化のために、我々は、全てがｆｉ対称と仮定するだろう。我々は、ｆｉが双方の変数において大きくても次数ａの多項式である場合を考慮する。
2016526851.tif 000040
ここで、
2016526851.tif 000041
及び
2016526851.tif 000042
ここでは、合計及び乗算がＲｉにおいて作用することに留意されたい。
2016526851.tif 000043
及び
2016526851.tif 000044
に関して、デバイス
2016526851.tif 000045
のための鍵材料（ＫＭ）を
2016526851.tif 000046
として規定し、
2016526851.tif 000047
に関して、デバイス
2016526851.tif 000048
により導出された共有鍵材料を
2016526851.tif 000049
として規定する。
【０１３８】
ｋに渡る合計はＲｉにおけるものである一方で、ｉ及び
2016526851.tif 000050
に渡る合計は、グローバル環Ｒ０におけるものであることに留意されたい。
【０１３９】
最後に、ｘは、Ｒ０からＺまでのマッピングであり、
2016526851.tif 000051
を規定する。ｆｉが対称であっても、
2016526851.tif 000052
及び
2016526851.tif 000053
は、環Ｒ１...，Ｒｍのための全ての選択の間で同じである必要はないことに留意されたい。本システムは、非一定マッピング
2016526851.tif 000054
及び整数のサブセットＤを与え、従って、
2016526851.tif 000055
又は、これが可能ではない場合、
2016526851.tif 000056
を与える。ここで、この文書における
2016526851.tif 000057
は、
2016526851.tif 000058
として理解されなければならない。ここで、ｓは、小さな数（
2016526851.tif 000059
）であり、関数ｇ１，...，ｇｓは既知である。
【０１４０】
例１：整数係数
最初に、我々は、第１のプライベートセットの二変数多項式の係数のための多項式環を用いない例を示すが、代わりに、整数は、整数環（例えば、整数法ｑｉ）から得られる。多項式環の代わりに整数環を用いたとき、斯様な選択は、
2016526851.tif 000060
，
2016526851.tif 000061
により与えられ、ここでは、加算及び乗算法
2016526851.tif 000062
を伴い、加算及び乗算法ｑｉを伴う。ここで、
2016526851.tif 000063
，
2016526851.tif 000064
，
2016526851.tif 000065
及び
2016526851.tif 000066
は、識別マッピングである。
2016526851.tif 000067
2016526851.tif 000068
2016526851.tif 000069
この場合、ｓは１よりも大きい。これは解決され得るが、ｓ＝１の場合により好ましくなるだろう。
【０１４１】
例２：係数のためのバイナリ多項式環
Ｒ１...，Ｒｍは、Ｚ２における係数を伴うＭよりも小さい次数の変数ｔにおける多項式の環である。多項式の加算は、Ｚ２における係数の加算、Ｒ０における乗算により規定される。Ｒｉは、多項式Ｎ（ｔ）によるモジュラ低減を介している。Ｚ２における係数を伴う次数ＭのＱｉ（ｔ）。この場合も同様に、
2016526851.tif 000070
，
2016526851.tif 000071
ここで、
2016526851.tif 000072
（全てのｉの間で同じ）及び
2016526851.tif 000073
は、識別マップである。従って、我々は、
2016526851.tif 000074
及び
2016526851.tif 000075
を有する。
2016526851.tif 000076
を規定する。任意のバイナリ多項式Ｘ（ｔ）は、
2016526851.tif 000077
として書かれ得る。第１行を第３行と比較すると、
2016526851.tif 000078
の次数がＭよりも小さい場合、及びこの場合のみ、Ｐｉ（ｔ）＝Ｐ（ｔ）及び
2016526851.tif 000079
ということになる。そして、これは、
2016526851.tif 000080
を保持し、我々は、この形式における同一性を同様に用いるべきである。０≦ｋ≦ａを伴う
2016526851.tif 000081
に関して、これは、
2016526851.tif 000082
従って、
2016526851.tif 000083
及び
2016526851.tif 000084
を維持する。１≦ｉ≦ｍのための
2016526851.tif 000085
の場合、
2016526851.tif 000086
ということになる。これは、多くてもａ（ｂ−１）−１の次数の幾つかの多項式
2016526851.tif 000087
のためのものである。それ故、
2016526851.tif 000088
ということになる。
2016526851.tif 000089
の次数がより強い境界
2016526851.tif 000090
を満たす場合、
2016526851.tif 000091
になることに留意されたい。
【０１４２】
また、我々が、全ての多項式
2016526851.tif 000092
を選び、共通因子
2016526851.tif 000093
即ち
2016526851.tif 000094
を有し、
2016526851.tif 000095
規定する場合、
2016526851.tif 000096
になる。ここでは、
2016526851.tif 000097
を伴う。Ｒ０からＺまでのマッピングは、生ずる番号のビットとして多項式の係数を利用することにより行われ得る。これは、多項式における置換ｔ＝２に達する。
2016526851.tif 000098
【０１４３】
有利には、これは、対称の関数
2016526851.tif 000099
を与える。即ち、デバイス
2016526851.tif 000100
及び
2016526851.tif 000101
は、同じ共有鍵を導出するだろう。不都合にも、これらの選択は低減されたセキュリティを与える。この関数は、ｆｉの合計にのみ依存し、個々のｆｉ及びＱｉには依存しないためである。従って、異なる環Ｒｉの混合の効果は、最終結果
2016526851.tif 000102
になる。
2016526851.tif 000103
であってもこのような結果になる。最終結果における混合効果の除去の理由は、より強い制約
2016526851.tif 000104
である。
【０１４４】
しかしながら、より弱い制約
2016526851.tif 000105
は、混合を介してより高いセキュリティを可能にする。この制約は、
2016526851.tif 000106
の計算におけるＮ（ｔ）を法とする演算を、Ｑｉ（ｔ）を法とする演算に変換するために用いられ得る。
2016526851.tif 000107
（ここでは、第２の条件は、Ｍよりも小さい次数を有する）
2016526851.tif 000108
【０１４５】
第１の条件は、
2016526851.tif 000109
及び
2016526851.tif 000110
において対称であり、第２の条件はそうではないが、
2016526851.tif 000111
に比例し、従って、
2016526851.tif 000112
を法として低減するときに省かれる。それ故、
2016526851.tif 000113
は、対称であり、
2016526851.tif 000114
により与えられる。従って、ｋの計算において生じる混合に関して、我々は、
2016526851.tif 000115
を必要とする。ここでは、全てのｉに対して、
2016526851.tif 000116
を伴い、少なくとも１つのｉに対して、
2016526851.tif 000117
を伴う。
【０１４６】
例３：ｐアレイ多項式環
バイナリの場合、これらの式は、Ｚ２の代わりにＺｐに渡る多項式環に対して機能する。
【０１４７】
図５は、鍵共有のための、ネットワークデバイス（第１のネットワークデバイス３００）を構成するための方法５００を示すフローチャートを示している。方法５００は、以下のステップを有する。
−  パブリックグローバル低減多項式２１６，Ｎ（ｔ）、二変数多項式２１２，ｆｉ（，）の第１のプライベートセット、及び、低減多項式２１４，Ｑｉ（ｔ）の第２のプライベートセットを電子形式において取得するステップ５０２。第１のセットにおける各二変数多項式により、第２のセットの低減多項式が関連付けられる。ステップ５０２は、鍵材料を取得する部分であってもよい。
−  ネットワークデバイスのための識別番号３１０，Ａを電子形式において取得するステップ５０４。
−  以下のステップにより第１及び第２のプライベートセットから一変数秘密鍵多項式２２８を計算するステップ５０６：第１のプライベートセットの各特定の多項式に関して、識別番号Ａを特定の多項式ｆｉ（Ａ，）に置換すること５０８、及び、特定の多項式に関連付けられた低減多項式を法として低減すること５１０により一変数多項式のセットを取得すること。一変数多項式のセットを合計すること５１２。
−  生成された一変数秘密鍵多項式２２８及びパブリックグローバル低減多項式２１６，Ｎ（ｔ）をネットワークデバイスにおいて格納するステップ５１４。
【０１４８】
図６は、第２のネットワークデバイス３５０により共有鍵を決定する方法６００を示すフローチャートを示している。方法６００は、以下のステップを有する。
−  ここで述べられる鍵共有のためのネットワークデバイスを構成するためのシステムから取得される一変数秘密鍵多項式３１２及びパブリックグローバル低減多項式３１４，Ｎ（ｔ）を格納するステップ６０２。
−  第１のネットワークデバイスのために、識別番号３１０，Ａを格納するステップ６０４。
−  第２のネットワークデバイスのための識別番号３５５を取得するステップ６０６。
−  第２のネットワークデバイスの識別番号を一変数秘密鍵多項式に置換するステップ６０８、及び、パブリックグローバル低減多項式Ｎ（ｔ）を法として前記の置換の結果を低減するステップ６１０。
−  パブリックグローバル低減多項式を法として前記の低減の結果から共有鍵を導出するステップ６１２。
【０１４９】
当業者にとって明らかなように、本方法を実行する多くの異なる手段が考えられる。例えば、ステップの順序は変えられてもよく、又は、一部のステップが並列に実行されてもよい。更に、ステップの間において、他の方法ステップが挿入されてもよい。挿入されたステップは、ここで述べられたような方法の改良を表してもよく、又は、方法に無関係であってもよい。更に、所与のステップは、次のステップが始まる前に、完全に終了していなくてもよい。
【０１５０】
本発明による方法は、処理システムが方法５００及び／又は６００を実行することをもたらすための命令を有するソフトウェアを用いて実行されてもよい。ソフトウェアは、システムの特定のサブエンティティにより利用されるそれらのステップのみを含んでもよい。ソフトウェアは、適切な格納媒体（例えば、ハードディスク、フロッピー、メモリ等）に格納されてもよい。ソフトウェアは、有線若しくは無線に沿った信号として送られてもよく、又は、データネットワーク（例えば、インターネット）を用いてもよい。ソフトウェアは、ダウンロードのため、及び／又は、サーバ上でのリモート使用のために利用可能であってもよい。
【０１５１】
本発明は、本発明を実現するために適合される、コンピュータプログラム、とりわけ担体上の又はそれにおけるコンピュータプログラムにも拡張することはいうまでもないだろう。プログラムは、部分的にコンパイルされた形式のような、ソースコード、オブジェクトコード、コード中間ソース及びオブジェクトコードの形式、又は、本発明の方法の実装における使用に適した任意の他の形式であってもよい。コンピュータプログラム製品に関する一実施形態は、記載された方法のうちの少なくとも１つの処理ステップのそれぞれに対応するコンピュータ実行可能な命令を有する。これらの命令は、サブルーチンに再分割されてもよく、及び／又は、静的又は動的に連結され得る１又はそれ以上のファイルに格納されてもよい。コンピュータプログラム製品に関する他の実施形態は、製品及び／又はシステムのうちの少なくとも１つの手段のそれぞれに対応するコンピュータ実行可能な命令を有する。
【０１５２】
上述の実施形態は、本発明を限定するよりはむしろ例示であり、当業者は、多くの代替実施形態を設計することが可能であることが留意されるべきである。
【０１５３】
請求項において、括弧間に配置された任意の参照符号は、請求項を限定するものとして考慮されるべきではない。"有する"という動詞の使用及びその活用は、請求項に記載されたもの以外の要素又はステップの存在を除外するものではない。要素の単数標記は、斯様な要素の複数の存在を除外するものではない。本発明は、幾つかの異なる要素を有するハードウェアによって、及び、適切にプログラムされたコンピュータによって実装されてもよい。幾つかの手段を列挙している装置に係る請求項において、これらの手段の幾つかは、ハードウェアの全く同一のアイテムにより具現化されてもよい。特定の手段が相互に異なる従属請求項に記載されるという単なる事実は、これらの手段の組み合わせが有効に用いられ得ないことを示すものではない。
【符号の説明】
【０１５４】
１００  鍵共有システム
１１０  パーソナライズデバイス
２００  鍵共有のためのネットワークデバイスを構成するためのシステム
２１０  鍵材料取得部
２１２  二変数多項式の第１のプライベートセット
２１４  低減多項式の第２のプライベートセット
２１６  パブリックグローバル低減多項式
２２０  多項式操作ユニット
２２２  置換ユニット
２２４  多項式低減ユニット
２２６  多項式加算ユニット
２２８  一変数多項式のセットの合計
２３０  ネットワークデバイス管理部
２３２  識別番号メッセージ
２３４  パブリックグローバル低減多項式メッセージ
２３６  一変数秘密鍵多項式メッセージ
３００  第１のネットワークデバイス
３１０  識別番号
３１２  一変数秘密鍵多項式
３１４  パブリックグローバル低減多項式
３２０  電子格納部
３３０  多項式操作ユニット
３３２  置換ユニット
３３４  多項式低減ユニット
３４０  鍵導出デバイス
３４２  通信ユニット
３４５  暗号化ユニット
３５０  第２のネットワークデバイス
３５５  識別番号
３６０  第３のネットワークデバイス
４００  一体型回路
４１０  バス
４２０  プロセッサ
４３０  メモリ
４４０  Ｉ／Ｏユニット
４５０  多項式操作ユニット
【図１】
2016526851.tif 000118
【図２】
2016526851.tif 000119
【図３ａ】
2016526851.tif 000120
【図３ｂ】
2016526851.tif 000121
【図４】
2016526851.tif 000122
【図５】
2016526851.tif 000123
【図６】
2016526851.tif 000124
【国際調査報告】
2016526851.tif 000125
2016526851.tif 000126
2016526851.tif 000127