(57)【要約】  本発明は、低電力装置７０１とより高度な装置７０２との間で複数のセッション鍵を共有するシステム６００及び方法に関する。特定の数のパラメータを含む多項式アルゴリズムが用いられる。低電力装置７０１に関して多数のパラメータが固定され、より多くの強力な装置７０２に関して少数のパラメータが固定される。
2008515319.tif 000002
【特許請求の範囲】
【請求項１】
第１装置Ａと第２の異なる装置Ｂとの間において共通秘密を生成する方法であって、
前記第１及び第２装置へ、それぞれの秘密固有アイデンティティ
2008515319.tif 000053
及び
2008515319.tif 000054
と、マスタ多項式
2008515319.tif 000055
に基づき、複数の変数を用いるそれぞれの秘密多項式
2008515319.tif 000056
及び
2008515319.tif 000057
と、を事前配布するステップであって、ここで、
2008515319.tif 000058
であるようなステップと、
前記固有アイデンティティを、前記第１装置により前記第２装置と、及び前記第２装置により前記第１装置と、のうちの少なくとも一方により交換するステップと、
各前記第１及び第２装置によって、それぞれの対応する秘密多項式を用いて共通秘密鍵を
2008515319.tif 000059
として計算するステップと、
を有する方法。
【請求項２】
前記多項式が所定のグループＧのアクションの下で不変である、請求項１に記載の方法。
【請求項３】
前記所定のグループＧが、
2008515319.tif 000060
であるように、GF(pm)においてｋ×ｋの行列を有する、請求項２に記載の方法。
【請求項４】
前記多項式が、
2008515319.tif 000061
、すなわち、各ｇ∈Ｇに関して
2008515319.tif 000062
の評価がＧの下で不変であるように、任意の多項式P(x),x=(x1,…,xk)を選択するステップと、
2008515319.tif 000063
を規定するステップと、
前記交換するステップの後に、p(x)におけるｘｊの最大累乗としての(n-1)及び１≦i＜kに対して、各行列Ｍ∈s(G)に関して、それらの相互同意秘密鍵が
2008515319.tif 000064
であるように、yA,B,Mを計算するステップと、
を実行することによって構成される、請求項２に記載の方法。
【請求項５】
2008515319.tif 000065
であり、Ｈがグループであり、
2008515319.tif 000066
であり、且つ
2008515319.tif 000067
であるような、請求項４に記載の方法。
【請求項６】
装置Ａ及び装置Ｂからなるグループから選択される少なくとも１つの受信装置へ、s(G)のパラメタリゼーションを事前配布するステップと、
前記少なくとも１つの受信装置によってランダムに要素Ｍ∈s(G)を選択するステップと、
を更に有する、請求項４に記載の方法。
【請求項７】
前記受信装置によって、前記選択された要素のパラメタリゼーションを装置Ａ及び装置Ｂからなるグループの他の装置へ送信するステップを更に有する、請求項６に記載の方法。
【請求項８】
装置Ａ及び装置Ｂによって、Ｍ∈s(G)に関する該解yA,B,Mの対応する一部を前記チャネルを介して装置Ｂ及び装置Ａへそれぞれ送信するステップを更に有する、請求項６に記載の方法。
【請求項９】
前記交換するステップが、装置Ａの前記アイデンティティを装置Ｂへ送信する装置Ａによってのみ実行され、
各行列Ｍに関してyA,B,Mを計算する前記ステップが、更に、
i．装置Ｂが、前記鍵
2008515319.tif 000068
を計算するステップと、
ii．装置Ｂが、前記ベクトル
2008515319.tif 000069
を計算し、Ａへ送信するステップと、
iii．装置Ａが、
2008515319.tif 000070
及び
2008515319.tif 000071
になるように、前記送信されたベクトル、前記事前配布されたアイデンティティ、及び前記グループｓ（Ｇ）のパラメタリゼーションを用いて、前記鍵を計算するステップと、
を有する、請求項８に記載の方法。
【請求項１０】
前記事前配布するステップが、暗号化されたアイデンティティを前記アイデンティティとして装置Ａへ、また前記暗号化されたアイデンティティの復号に関してマスタ暗号化鍵を装置Ｂへ事前配布し、
装置Ｂによる各行列Ｍに関してyA,B,Mを計算する前記ステップが、更に、装置Ａの前記送信されたアイデンティティの第１復号化ステップを有する、
請求項９に記載の方法。
【請求項１１】
請求項１に記載の方法を実行するように構成される少なくとも１つの第１装置Ａ及び少なくとも１つの異なる第２装置Ｂを含むシステム。
【請求項１２】
請求項９に記載の第１装置Ａ及び請求項１０に記載の第２装置Ｂからなるグループのうちの少なくとも１つを動作するように構成される装置。
【請求項１３】
装置Ａ及び装置Ｂの前記事前配布された固有秘密アイデンティティ、装置Ａ及び装置Ｂの前記秘密多項式、及び前記グループＧの前記パラメタリゼーションのうちのいずれかを記憶するメモリを備える、請求項１１に記載の装置。
【請求項１４】
請求項４に記載の方法を実行するように構成される少なくとも１つの第１装置Ａ及び少なくとも１つの異なる第２装置Ｂを含むシステム。
【請求項１５】
請求項１４に記載の第１装置Ａ及び請求項１４に記載の第２装置Ｂからなるグループのうちの少なくとも１つを動作するように構成される装置。
【請求項１６】
装置Ａ及び装置Ｂの前記事前配布された固有秘密アイデンティティ、装置Ａ及び装置Ｂの前記秘密多項式、及び前記グループＧの前記パラメタリゼーションのうちのいずれかを記憶するメモリを備える、請求項１５に記載の装置。
【請求項１７】
請求項７に記載の方法を実行するように構成される少なくとも１つの第１装置Ａ及び少なくとも１つの異なる第２装置Ｂを含むシステム。
【請求項１８】
請求項１７に記載の第１装置Ａ及び請求項１７に記載の第２装置Ｂからなるグループのうちの少なくとも１つを動作するように構成される装置。
【請求項１９】
装置Ａ及び装置Ｂの前記事前配布された固有秘密アイデンティティ、装置Ａ及び装置Ｂの前記秘密多項式、及び前記グループＧの前記パラメタリゼーションのうちのいずれかを記憶するメモリを備える、請求項１８に記載の装置。
【請求項２０】
請求項９に記載の方法を実行するように構成される少なくとも１つの第１装置Ａ及び少なくとも１つの異なる第２装置Ｂを含むシステム。
【請求項２１】
請求項２０に記載の第１装置Ａ及び請求項２０に記載の第２装置Ｂからなるグループのうちの少なくとも１つを動作するように構成される装置。
【請求項２２】
装置Ａ及び装置Ｂの前記事前配布された固有秘密アイデンティティ、装置Ａ及び装置Ｂの前記秘密多項式、及び前記グループＧの前記パラメタリゼーションのうちのいずれかを記憶するメモリを備える、請求項２１に記載の装置。
【請求項２３】
少なくとも１つの処理器に請求項１に記載の方法を実行させる計算機プログラム。
【請求項２４】
少なくとも１つの処理器に請求項４に記載の方法を実行させる計算機プログラム。
【請求項２５】
少なくとも１つの処理器に請求項７に記載の方法を実行させる計算機プログラム。
【請求項２６】
少なくとも１つの処理器に請求項９に記載の方法を実行させる計算機プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化システムに関する。より特には、本発明は、セキュアセッション鍵を生成する暗号化鍵配布に関する。最も特には、本発明は、多項式に基づく鍵配布に関するシステム及び方法である。
【背景技術】
【０００２】
低電力装置及び高電力装置間においてセキュアな通信を必要とするアプリケーションの数が増大している。例えば、将来において、ビルは、ビル内の温度の制御だけでなくビルのセキュリティにも寄与する低コスト及び低エネルギのセンサを備え得る。すなわち、これらのセンサは、入館する人及び退出する人などの、ビルのセキュリティに関する情報を収集し得る。これらのセンサは、センサが集める情報を設備へ、すなわちこの情報を収集し処理するビル内の別のポイントへ送信する。この状況において、収集ポイントがセンサ情報入力を信頼することが可能であることが重要である。
【０００３】
信頼のレベルを提供する１つの方法は、センサ及び収集ポイントの間における通信をセキュアにするための簡単な暗号化ツールを組み込み、伝送される情報の認証を可能にすることである。しかし、センサは、限られた量の利用可能な電力のみを有する可能性が高く、理想的には、これらのセンサは、例えばソーラーパワー又はＲＦ電源供給などのセンサの周囲環境から電力を得る。この低電力利用可能性により、公開鍵暗号化は、非常に高価になり、該装置を遅くさせる。更に、秘密鍵システムは、全ての参加者がセキュアに通信を行うために共有秘密鍵を有することが必要である。
【０００４】
低電力暗号化が重要である別のアプリケーションは、チップインディスク（Chip-in-Disc）のＲＦＩＤタグ技術である。この場合、通信は、高電力ディスクプレーヤと低電力ディスクとの間で発生する。ここで含まれるチップは、ディスクにおけるコンテンツへのアクセス権を制御する。当該チップは、プレーヤが信頼できることが確信される場合にコンテンツへの鍵をディスクプレーヤへ提供し、チップが信頼され得ると確信される場合のみにディスクプレーヤはコンテンツを再生する。
【０００５】
これらの例のアプリケーションの両方及びこれらの他のものは、低コスト及び低電力暗号化鍵管理システムを必要としている。しかし、斯様な低コスト及び低電力システムは、記憶容量及び計算能力の両方において非常に制約を受ける。
【０００６】
Blundoらによって提案された従来技術のスキームは、Blomのスキームに基づき、p(x,y):GF(Q)2→GF(q)（ｑは素数累乗(prime  power)である）であり、またp(x,y)=p(y,x)が対称多項式であるようなBlomのスキームにおける対称多項式を用いる。更に、１つの種類の装置Ａのみが存在し、且つ装置Ａが秘密多項式qA(y)=p(xA,y)とともにアイデンティティxA∈GF(q)を得ることを仮定する。いかなる２つの装置Ａ及びＢも、互いに自身のアイデンティティを伝達し、それらに秘密多項式を適用することによって、共有秘密鍵KA,B=qA(xB)=qB(xA)を構成し得る。グループＧに関して、グループＧから特定のベクトル空間Ｖ（このベクトル空間は、多項式p:GF(q)2→GF(q)≡Pの空間であり得る）における線形マッピングＬ（Ｖ）の空間への準同形である表現
2008515319.tif 000003
を、各ｇ∈Ｇと関連付ける。Blomのスキームは、R.BlomによるNon-Public Key Distribution, Advances in Cryptology-Proceedings of Crypto 82, pps 231-236, 1983、及びR.BlomによるAn Optimal Class of Symmetric Key Generation Systems, Advances in Cryptology-Proceedings of EUROCRYPT84, pps 335-338, 1985に記載され、これらの両方のコンテンツの全体は、本文書において参照文献として組み込まれる。Blundo等のスキームは、C. Blundo, A. De Santis, A. Herzberg, Skutten, U. Vaccaro, & M. YungによるPerfectly Secure Key Distribution for Dynamic Conferences, Advances in Cryptology-CRYPTO93, pp. 110-125, 1994に記載され、これのコンテンツの全体は、本文書において参照文献として組み込まれる。
【０００７】
行列グループ
2008515319.tif 000004
を検討し、Ｇにおけるｇに関して、ベクトル空間Ｐにおける線形マッピングの空間におけるＧの表現
2008515319.tif 000005
は、
2008515319.tif 000006
によって与えられる。このマップが、グループＧからL(P)への準同形を与えることは明らかである。グループＧの規定及び対称多項式ｐの規定から、多項式ｐがグループＧのアクションの下で不変であることは、容易に導かれる。
【０００８】
より一般的に、グループＧにベクトル空間
2008515319.tif 000007
において以下の
2008515319.tif 000008
のように作用するようにさせる。またp(x,y)=〈x,Py〉を規定し、ここで、Ｐは、対象行列であり、すなわち、〈Px,y〉=〈x,Py〉であり、
2008515319.tif 000009
は、Ｖにおける内積を示す(Ｇにおけるｇに関してg2=1であることに注意)。この場合、ｐがｇグループＧのアクションの元に不変であることが導かれる。行列Ｐを仮定すると、
2008515319.tif 000010
であるような対称行列ＰＳを常に得ることが可能であり、ここでＴは、行列の転置を表す。
【０００９】
多項式は、以下の
2008515319.tif 000011
のようにして同様にして不変にされる。
【００１０】
ここで、図１を参照すると、同じ種類の２つの装置Ａ及びＢ間における相互作用は、以下のように進められる。
初期化段階：
１．ステップ１０１において、Ａ及びＢはアイデンティティと、同一であるが秘密である、２つの変数ｘ及びｙを用いた対称多項式p(x,y)=p(y,x)とをそれぞれ得る。
セッション鍵移生成段階：
２．ステップ１０２において、Ａは、ＡのアイデンティティxA∈GF(q)をＢへ送信する。
３．ステップ１０３において、Ｂは、ＢのアイデンティティxＢ∈GF(q)をＡへ送信する。
４．ステップ１０４において、Ａは、受信されたＢのアイデンティティ、Ａ自身のアイデンティティ、及び事前に配布された秘密対称多項式を用いて、KA,B=qA(xB)=p(xA,xB)であるように鍵を計算する。
５．ステップ１０５において、Ｂは、受信されたＡのアイデンティティ、Ｂ自身のアイデンティティ、及び事前に配布された秘密対称多項式を用いて、KA,B=qB(xA)=p(xB,xA)であるように鍵を計算する。
６．共有される、同一の秘密鍵は、KA,B=qB(xA)=qA(xB)である。
【００１１】
これらの従来技術のアプローチは、装置の異なる性能を活用せず、使用毎に１つより多い秘密セッション鍵を提供しない。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
したがって、安価で低電力な装置と高価で高電力な装置とが、これらの装置間で将来のセキュアな通信を可能にするために、複数の秘密セッション鍵を共有するのを可能にする解決法が必要とされる。
【課題を解決するための手段】
【００１３】
本発明のシステム及び方法は、低コスト低電力の装置が、高コスト高電力の装置と複数の秘密セッション鍵を共有するのを可能にさせる多項式に基づく鍵配布スキームを提供する。
【００１４】
本発明の第１の好ましい実施例は、複数の変数を用いる多項式を用い、且つ少なくとも２つの種類の装置に適用する鍵配布スキームである。
【００１５】
第２の好ましい実施例は、グループ変換の下で不変である複数の変数を用いる多項式を用い、且つ少なくとも２つの種類の装置に適用する鍵配布スキームである。
【００１６】
非対称のプロトコルに関して、盗聴者に、破るのがより困難な装置すなわちより高価でより高電力の装置のうちの少なくとも１つを破ることを強いるような第３の実施例が提供される。
【００１７】
第４の実施例は、敵対者に少なくとも１つの破るのがより困難である装置すなわちより高価でより高電力な装置を破ることを強いるような実施例である。
【発明を実施するための最良の形態】
【００１８】
当業者によって、以下の記載は、例証の目的に関して提供されており、限定のために提供されていないことを理解されるべきである。当業者は、本発明の精神および添付される請求項の範囲内にある多数の変更態様が存在することを理解する。既知の機能及び動作の不必要な詳細は、本発明を不明瞭にしないように現在の記載から省略され得る。
【００１９】
本発明の第１の好ましい実施例において、少なくとも２つの種類の装置が、秘密鍵を構築するために、配布された多変量多項式を使用する。
【００２０】
始めに、複数の変数を用いる多項式を、その変数
2008515319.tif 000012
のいかなるものの最大パワーも多くてもn-1であるように規定する。多項式p(x1,…xk)は、当該配布スキームにおけるマスタ鍵を表し、前記装置のいずれを用いても記憶されず、ｐから導出される多項式qA,qBのみがＡ及びＢ等に事前配布される。
【００２１】
２つの種類の装置が群Ａ及びＢに分割されることを検討する。Ａ∈Ａに関して、複数の変数を用いる秘密多項式qAを、
2008515319.tif 000013
のように規定し、Ｂ∈Ｂに関して、複数の変数を用いる秘密多項式qBを、
2008515319.tif 000014
のように規定し、装置Ａ及びＢの
2008515319.tif 000015
及び
2008515319.tif 000016
を交換した後で、それらのそれぞれの秘密多項式
2008515319.tif 000017
を用いて、相互に合意された秘密鍵KA,Bを計算する。
【００２２】
Ａタイプの装置は、GF(q)にnk-i+i個の要素を記憶する必要があり（多項式qAは、nの次数(degree)を有し、またk-i個の変数を用いる多項式であり、したがって、我々は、qAを説明するのにGF(q)においてnk-i個の係数を必要とし、Ａのアイデンティティは、GF(q)における別のi個の要素を要する）、タイプＢの装置は、GF(q)においてni+k-i個の要素を記憶する必要がある。
【００２３】
ここで図２を参照すると、異なるタイプの２つの装置Ａ及びＢ間における相互作用は、以下のように進められる。
１．ステップ２０１において、Ａ及びＢはアイデンティティと、それぞれの多項式
2008515319.tif 000018
及び
2008515319.tif 000019
をそれぞれ得る。
２．ステップ２０２において、Ａは、Ａのアイデンティティ
2008515319.tif 000020
をＢへ送信する。
３．ステップ２０３において、Ｂは、Ｂのアイデンティティ
2008515319.tif 000021
をＡへ送信する。
４．ステップ２０４において、Ａは、受信されたＢのアイデンティティ、及びＡへ事前に配布された秘密対称多項式qAを用いて、
2008515319.tif 000022
であるように鍵を計算する。
５．ステップ２０５において、Ｂは、受信されたＡのアイデンティティ、及びＢへ事前に配布された秘密対称多項式qBを用いて、
2008515319.tif 000023
であるように鍵を計算する。
６．相互に同意される秘密鍵は、
2008515319.tif 000024
である。
【００２４】
タイプＡの装置は、nk-i+i個の要素をGF(q)に記憶する必要がある。タイプＢの装置は、ni+k-i個の要素をGF(q)に記憶する必要がある。
【００２５】
好ましい実施例において、タイプＡの装置は、低コスト低電力装置である一方、タイプＢの装置は、より多くの機能性を有するより高価な装置である。
【００２６】
本発明の第２の実施例において、少なくとも２つの種類の装置が、秘密鍵を構築するために、配布される多変量の多項式を用い、前記多項式は、特定のグループの下で不変である。この実施例は、第１の実施例の繰り返しに対して性能が等価である装置の対毎に複数のセッション鍵を得る手法を提供する。
【００２７】
複数の変数を用い、GF(pm)においてk×kの行列からなるグループＧの下で不変である多項式
2008515319.tif 000025
を検討する。斯様な多項式の構築は、任意の多項式p(x),x=(x1,…xk)を用いて、
2008515319.tif 000026
がＧの下で不変であるように開始する。すなわち、各g∈Gに関しての、
2008515319.tif 000027
の評価である。
【００２８】
n-1をp(x)におけるxjの最大累乗であるとする。
【００２９】
1≦i＜kとし、
2008515319.tif 000028
を規定する。セットＡ及びＢに分割される２つの種類の装置を検討する。A∈A及びB∈Bに関して、装置Ａ及びＢの
2008515319.tif 000029
及び
2008515319.tif 000030
を交換した後で、各行列M∈s(G)に関して、それらの相互に合意された秘密鍵が
2008515319.tif 000031
であるように、固有のyA,B,Mを計算する。
【００３０】
装置Ａ及びＢの各対は、|s(G)|一様に配布される秘密セッション鍵を共有し得る。しかし、同一の種類の装置は、秘密を共有し得ない。
【００３１】
上述の第１の実施例に関して説明される記憶装置に加えて、全ての装置がs(G)のパラメタリゼーションを記憶する必要がある。例えば、Ｇが巡回グループである場合、その発生させる行列のみが記憶される必要がある。
【００３２】
Ｇは、例えば以下のように発生され得る。Ｈをグループとし、グループＧを次のような
2008515319.tif 000032
として規定することを仮定する。この場合、
2008515319.tif 000033
であり、我々は、次の式を有する。
2008515319.tif 000034
セッション鍵が全ての装置Ａ及びＢに関するM1,M2∈Gについて等しい場合、このことは、M1=M2であることを意味し、したがって、全てのセッション鍵が(事故的な不一致を除いて)異なることを示すことは容易に表せられ得る。
【００３３】
ここで、図３を参照すると、２つの異なる種類Ａ及びＢの装置の間の相互作用は、以下のように進む。
初期化段階：
１．ステップ３０１において、Ａ及びＢはアイデンティティと、それぞれの秘密対称多項式qA及びqBと、パラメタリゼーションs(G)をそれぞれ得る。
セッション鍵生成段階：
２．ステップ３０２において、Ａは、s(G)におけるＭをランダムに選択し、Ｍのパラメータ表現及びＡのアイデンティティ
2008515319.tif 000035
をＢへ送信する。
３．ステップ３０３において、Ｂは、Ｂのアイデンティティ
2008515319.tif 000036
をＡへ送信する。
４．ステップ３０４において、Ａは、受信されたＢのアイデンティティ、Ａ自身の多項式qAを用いて、
2008515319.tif 000037
であるように鍵を計算する。
５．ステップ３０５において、Ｂは、受信されたＡのアイデンティティ、Ｂ自身の多項式qBを用いて、
2008515319.tif 000038
であるように鍵を計算する。
６．相互に同意される秘密鍵は、
2008515319.tif 000039
である。
【００３４】
好ましい実施例において、タイプＡの装置は、低コスト低電力装置である一方、タイプＢの装置は、より機能性を有するより高価な装置である。
【００３５】
第３の実施例は、破るのが困難な装置が自身のアイデンティティを晒すことなく、両方の装置に同一の鍵を計算させる、第２の実施例の変形態様である。
【００３６】
低コスト低電力装置A∈Aに関して、及びより高電力でより高機能な装置B∈Bに関して、始めにＡにＡのアイデンティティを破るのがより困難な装置Bへ伝送させる。その後Bは、自身のアイデンティティと多項式を用いてベクトル(
2008515319.tif 000040
)を計算する。Bは、自身のアイデンティティを晒すことなく、このベクトルを、
2008515319.tif 000041
をここで計算し得るＡへ伝送する。この非対称プロトコルは、Bのアイデンティティを晒すことはなく、より重要なことには、より低コストで破られやすい装置が、グループGの表現を記憶する必要がない。
【００３７】
ここで、図４を参照すると、同一のタイプの２つの装置Ａ及びB間における相互作用は、以下のように進む。
初期化段階：
１．ステップ４０１において、Ａ及びＢはアイデンティティと秘密対称多項式とをそれぞれ得て、Bは、パラメタリゼーションs(G)を得る。
セッション鍵生成段階：
２．ステップ４０２において、Ａは、Ａのアイデンティティ
2008515319.tif 000042
をＢへ送信する。
３．ステップ４０３において、Ｂは、グループs(G)の事前に配布されたパラメタリゼーションを用いて、s(G)におけるＭをランダムに選択し、受信されたＡのアイデンティティ及びＢ自身の多項式qBを用いて、
2008515319.tif 000043
であるように鍵を計算する。
４．ステップ４０４において、Bは、ベクトル
2008515319.tif 000044
を計算し、それをＡに送信する。
５．ステップ４０５において、Ａは、受信されたベクトル及びＡ自身の多項式qAを用いて、
2008515319.tif 000045
であるように鍵を計算する。
６．相互に同意される秘密鍵は、
2008515319.tif 000046
である。
【００３８】
第４の実施例は、第３の実施例のようにグループGを隠す代わりに、ＡからＡのアイデンティティを、Ａの暗号化版を記憶することによって隠す。Ａの暗号化されたアイデンティティは、Bに送信され、その後Bは、該Ａの暗号化されたアイデンティティを復号化するために（Bにおいて全ての装置に既知である）マスタ鍵を用いる。このことは、敵対者に、Bにおける少なくとも１つの破るのが困難な装置を破ることを強いる。
【００３９】
Ａのタイプの装置のアイデンティティがこれらの装置に暗号化された形式で記憶される場合、Ａの装置のqの多項式を得ることに基づく補間攻撃は、成功しない。斯様な攻撃を成功させるためには、アイデンティティを知っていることが不可欠である。このことは、攻撃者が、Ａ装置のアイデンティティを暗号化するのに用いるマスタ鍵を知るようになるために、少なくとも１つのB装置を破ることを強いられることを意味する。
【００４０】
ここで図５を参照すると、同一のタイプの２つの装置Ａ及びB間における相互作用は、以下のように進む。
１．ステップ５０１において、Ａ及びＢは、アイデンティティであって、Aのアイデンティティが
2008515319.tif 000047
であるように暗号化された、アイデンティティと、秘密対称多項式と、をそれぞれ得て、Bは、パラメタリゼーションs(G)を得る。
２．ステップ５０２において、Ａは、Ａの暗号化されたアイデンティティ
2008515319.tif 000048
をＢへ送信する。
３．ステップ５０３において、Ｂは、受信されたAのアイデンティティを復号化し、グループs(G)の事前に配布されたパラメタリゼーションを用いて、ランダムにs(G)におけるＭを選択し、復号化されたＡのアイデンティティ及びＢ自身の多項式qBを用いて、
2008515319.tif 000049
であるように鍵を計算する。
４．ステップ５０４において、Bは、B自身のアイデンティティ及び多項式を用いてベクトル
2008515319.tif 000050
を計算し、その後Bは、それをＡに送信する。
５．ステップ５０５において、Ａは、受信されたベクトル及びＡ自身の多項式qAを用いて、
2008515319.tif 000051
であるように鍵を計算する。
６．相互に同意される秘密鍵は、
2008515319.tif 000052
である。
【００４１】
ここで図６を参照すると、アンテナ６０１、多項式鍵配布モジュール６０３によって指示されるメッセージを送受信するために前記アンテナに接続されるように動作可能な送受信器６０２、及び、多項式鍵配布モジュール６０３が本発明の多項式鍵配布スキームによって必要とされる様々なデータを記憶するメモリ６０４、を備える、本発明により修正された装置が例証されている。
【００４２】
ここで図７を参照すると、本発明により修正された少なくとも２つの装置Ａ（７０１）及びB（７０２）を備える無線ネットワークシステム７００が例証されており、装置Ａ（７０１）は、装置Ａ（７０１）が低コスト低電力の装置の群を表し装置B（７０２）がより高電力で機能的により性能のある装置である点で、装置B（７０２）とは相違している。
【００４３】
一般的に、Ａのタイプの装置は、チップインディスクのような低電力装置であり、Bのタイプの装置は、ディスクプレーヤなどの機能的により性能のあるより高電力装置である。
【００４４】
本発明の好ましい実施例が例証されて説明されてきたが、本発明の真の範囲から逸脱することなく様々な変更及び修正態様がなされ得、等価物が要素に対して置換され得ることを当業者によって理解され得る。加えて、多数の修正が装置の相対的性能などの特定の状況に適合され得、本発明の教示が、本発明の中央の範囲から逸脱することなく等価的な手法で適合され得る。したがって、本発明は、最適な実施例として開示される特定の実施例及び本発明を実施するために考慮される代替物に制限されないが、本発明が、添付の請求項の範囲内にある全ての実施例を含むことを意図されている。
【図面の簡単な説明】
【００４５】
【図１】図１は、共有鍵生成に対する従来技術のアプローチを例証する。
【図２】図２は、本発明による、共有鍵生成の第１の好ましい実施例を例証する。
【図３】図３は、本発明による、共有鍵生成の第２の好ましい実施例を例証する。
【図４】図４は、本発明による、共有鍵生成の第３の好ましい実施例を例証する。
【図５】図５は、本発明による、共有鍵生成の第４の好ましい実施例を例証する。
【図６】図６は、本発明に従い修正された装置を例証する。
【図７】図７は、本発明に従い修正された、少なくとも２つの装置Ａ及びＢ（７０２）を備える無線ネットワークシステムを例証する。
【図１】
2008515319.tif 000072
【図２】
2008515319.tif 000073
【図３】
2008515319.tif 000074
【図４】
2008515319.tif 000075
【図５】
2008515319.tif 000076
【図６】
2008515319.tif 000077
【図７】
2008515319.tif 000078
【国際調査報告】
2008515319.tif 000079
2008515319.tif 000080
2008515319.tif 000081