(57)【要約】  本発明は、ノードのグループの中で完全な秘密鍵を構成するための方法に関する。ｍ個のノードよりなるグループにおいて、対用（ｐａｉｒ−ｗｉｓｅ）の秘密鍵が割り当てられる。対用の秘密鍵に基づき、これらのｍ個のノードはグループ用（ｇｒｏｕｐ−ｗｉｓｅ）の完全な秘密鍵を発生させる。好適な実施形態においては、それぞれのノードは、公衆の雑音のないブロードキャストを通して他のあらゆるノードと通信する。
2010504695.tif 000002
【特許請求の範囲】
【請求項１】
対称鍵暗号化を利用する複数の無線送受信ユニット（ＷＴＲＵ）を有する無線通信システムにおいて、グループ用の完全な秘密鍵を発生させるための方法であって、
ａ）少なくとも２つのＷＴＲＵの間で対用の完全な秘密鍵を発生させるステップと、
ｂ）前記対用の秘密鍵を使用してグループ用の完全な秘密鍵Ｋを選択するステップと
を具備することを特徴とする方法。
【請求項２】
ｃ）対用の完全な秘密鍵とのＸＯＲ結合を使用して、前記グループ用の完全な秘密鍵を公衆ブロードキャスト・チャンネル上で別のＷＴＲＵに送信するステップと
をさらに具備することを特徴とする請求項１に記載の方法。
【請求項３】
ｃ）前記複数のＷＴＲＵからスパニング・ツリーを決定するステップであって、前記スパニング・ツリーが対用の完全な秘密鍵の長さに等しいそれぞれのＷＴＲＵ対の間の辺（ｅｄｇｅ）の重みを有する、ステップと、
ｄ）ｍ個のＷＴＲＵの中でｍ−１個の対用の秘密鍵によりグループ用の完全な秘密鍵を発生させるステップと、
ｅ）前記スパニング・ツリー上の鍵の長さにより辺の重みを減少させるステップと
をさらに具備することを特徴とする請求項１に記載の方法。
【請求項４】
前記スパニング・ツリーが最大のスパニング・ツリーであることを特徴とする請求項３に記載の方法。
【請求項５】
ｃ）スパニング・ツリーに対して、前記グループ用の完全な秘密鍵であるべき対応する対用の秘密ビットを有する辺を選択するステップと、
ｄ）第１のＷＴＲＵにて、隣接するＷＴＲＵが前記選択された辺の秘密ビットに関する知識を欠いているかを判定するステップと、
ｅ）ＸＯＲ結合を使用して、前記第１のＷＴＲＵおよび隣接するＷＴＲＵによって共有された前記対用の秘密鍵により前記選択された辺の秘密ビットを前記第１のＷＴＲＵから前記隣接するＷＴＲＵへ送信するステップと、
ｆ）前記隣接するＷＴＲＵにて前記選択された辺の秘密鍵ビットを復号化するステップと、
ｇ）すべてのＷＴＲＵが前記秘密ビットを共有するまでステップｃ）からｆ）を繰り返すステップと
をさらに具備することを特徴とする請求項１に記載の方法。
【請求項６】
ｈ）前記複数のＷＴＲＵから最大のスパニング・ツリーを決定するステップであって、前記最大のスパニング・ツリーが、対用の秘密鍵の長さに等しいそれぞれのＷＴＲＵの間の辺の重みを有することと、
ｉ）ステップｅ）に続いて、前記最大のスパニング・ツリーについて辺の重みを１ビットだけ減少させるステップと、
ｊ）その辺の重みがゼロになると、前記スパニング・ツリーから辺を除去するステップと
をさらに具備することを特徴とする請求項５に記載の方法。
【請求項７】
前記最大のスパニング・ツリーを決定するステップが、グリーディ・アルゴリズムを使用して達成されることを特徴とする請求項６に記載の方法。
【請求項８】
前記グリーディ・アルゴリズムが、ＫｒｕｓｋａｌアルゴリズムおよびＰｒｉｍアルゴリズムから成るグループから選択されることを特徴とする請求項７に記載の方法。
【請求項９】
最大のスパニング・ツリーを決定するステップが、このＷＴＲＵに接続しているすべての辺の合計が最大であるようにＷＴＲＵを選択するステップを含むことを特徴とする請求項３に記載の方法。
【請求項１０】
前記対用の完全な秘密鍵が、前記対用チャンネルの結合ランダム性に基づき発生されることを特徴とする請求項１に記載の方法。
【請求項１１】
前記対用の完全な秘密鍵が、量子もつれに基づき発生されることを特徴とする請求項１に記載の方法。
【請求項１２】
対称鍵暗号化を利用する複数の無線送受信ユニット（ＷＴＲＵ）を有する無線通信システムにおいて、グループ用の完全な秘密鍵を発生させる能力のあるＷＴＲＵであって、
接続されたＷＴＲＵと対用の完全な秘密鍵を発生するように構成された処理装置と、
公衆ブロードキャスト・チャンネル上の秘密鍵を受信するための受信機と、
前記対用の秘密鍵に基づきグループ用の完全な秘密鍵Ｋを決定するための処理装置と
を具備することを特徴とするＷＴＲＵ。
【請求項１３】
前記対用の完全な秘密鍵とＸＯＲ結合された前記グループ用の完全な秘密鍵チャンネルを公衆ブロードキャスト上で送信するための送信機をさらに具備することを特徴とする請求項１２に記載のＷＴＲＵ。
【請求項１４】
前記処理装置が、辺から秘密ビットを選択するように構成されることであって、前記ＷＴＲＵおよび隣接するＷＴＲＵによって共有された前記対用の秘密鍵により結合された前記隣接するＷＴＲＵへ選択された辺の秘密ビットを送信するように構成された送信機をさらに具備することを特徴とする請求項１２に記載のＷＴＲＵ。
【請求項１５】
対称鍵暗号化を利用する複数のノードを有する光ファイバー通信ネットワークにおいて、グループ用の完全な秘密鍵を発生させるための方法であって、
ａ）少なくとも２つのノードの間で量子暗号化を使用して対用の完全な秘密鍵を発生させるステップと、
ｂ）前記対用の秘密鍵を使用してグループ用の完全な秘密鍵Ｋを選択するステップと
を具備することを特徴とする方法。
【請求項１６】
ｃ）対用の完全な秘密鍵とのＸＯＲ結合を使用して、前記グループ用の完全な秘密鍵を公衆ブロードキャスト・チャンネル上で別のノードに送信するステップと
をさらに具備することを特徴とする請求項１５に記載の方法。
【請求項１７】
ｃ）前記複数のノードからスパニング・ツリーを決定するステップであって、前記スパニング・ツリーが対用の完全な秘密鍵の長さに等しいそれぞれのノード対の間の辺の重みを有する、ステップと、
ｄ）ｍ個のノードの中でｍ−１個の対用の秘密鍵によりグループ用の完全な秘密鍵を発生させるステップと、
ｅ）前記スパニング・ツリー上の鍵の長さにより辺の重みを減少させるステップと
をさらに具備することを特徴とする請求項１５に記載の方法。
【請求項１８】
前記スパニング・ツリーが最大のスパニング・ツリーであることを特徴とする請求項１７に記載の方法。
【請求項１９】
ｃ）スパニング・ツリーに対して、前記グループ用の完全な秘密鍵であるべき対応する対用の秘密ビットを有する辺を選択するステップと、
ｄ）第１のノードにて、隣接するノードが前記選択された辺の秘密ビットに関する知識を欠いているかを判定するステップと、
ｅ）ＸＯＲ結合を使用して、前記第１のノードおよび隣接するノードによって共有された前記対用の秘密鍵により前記選択された辺の秘密ビットを前記第１のノードから前記隣接するノードへ送信するステップと、
ｆ）前記隣接するノードにて前記選択された辺の秘密鍵ビットを復号化するステップと、
ｇ）すべてのノードが前記秘密ビットを共有するまでステップｃ）からｆ）を繰り返すステップと
をさらに具備することを特徴とする請求項１５に記載の方法。
【請求項２０】
ｈ）前記複数のノードから最大のスパニング・ツリーを決定するステップであって、前記最大のスパニング・ツリーが対用の秘密鍵の長さに等しいそれぞれのノードの間の辺の重みを有する、ステップと、
ｉ）ステップｅ）に続いて、前記最大のスパニング・ツリーについて辺の重みを１ビットだけ減少させるステップと、
ｊ）その辺の重みがゼロになると、前記スパニング・ツリーから辺を除去するステップと
をさらに具備することを特徴とする請求項１５に記載の方法。
【請求項２１】
前記最大のスパニング・ツリーを決定するステップが、グリーディ・アルゴリズムを使用して達成されることを特徴とする請求項２０に記載の方法。
【請求項２２】
前記グリーディ・アルゴリズムが、ＫｒｕｓｋａｌアルゴリズムおよびＰｒｉｍアルゴリズムから成るグループから選択されることを特徴とする請求項２１に記載の方法。
【請求項２３】
最大のスパニング・ツリーを決定するステップが、このノードに接続しているすべての辺の合計が最大であるようにノードを選択するステップを含むことを特徴とする請求項１７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般には、通信の暗号化に関する。より詳細には、グループ用秘密鍵の発生アルゴリズムの方法および機構が開示される。
【背景技術】
【０００２】
対称鍵暗号（ｓｙｍｍｅｔｒｉｃ  ｅｎｃｒｙｐｔｉｏｎ）システムにおいては、２つのノードがそれらの間でのセキュア（ｓｅｃｕｒｅ）な通信のために共通な秘密鍵を共有する必要がある。現存のほとんどの対称鍵暗号化システムにおいては、２つのノードによって共有される秘密鍵は計算上はセキュアである。計算上の秘密鍵を発生させるアルゴリズムには、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵交換および公開鍵に基づくもの（すなわち、秘密鍵を受取人の公開鍵によりその分配前に暗号化するもの）が含まれる。
【０００３】
計算上の秘密鍵のセキュリティは、例えばあるグループにおける、大きい整数の因数分解（ｆａｃｔｏｒｉｎｇ）または離散対数（ｄｉｓｃｒｅｔｅ  ｌｏｇａｒｉｔｈｍ）の計算の、計算上の問題を解く際の困難性に依存する。換言すればセキュリティは、盗聴者の計算能力が限定されているという前提による。しかしながら、高速計算における進歩により、この仮定は成立しないかも知れない。したがって、計算上の暗号化のこの弱点を許さない、新しい方法およびアプローチが必要である。
【０００４】
一方、盗聴者の計算能力における限界に関しての何れの仮定もなしで秘密鍵のセキュリティを厳しく確立可能である場合には、この秘密鍵は完全な秘密鍵（ｐｅｒｆｅｃｔｌｙ  ｓｅｃｒｅｔ  ｋｅｙ）と呼ばれる。秘密鍵に基づくセキュリティ・システムは非秘密鍵システムの先の弱点に曝されることはないであろう。完全な秘密鍵を発生させるという問題は、数人の著者によって研究されている。完全な秘密鍵を発生させるためには、統計的ランダム性の自然発生源へのアクセスが必要である。現在では、好適な統計的ランダム性の自然発生源は２つある。第１は量子暗号化（ｑｕａｎｔｕｍ  ｃｒｙｐｔｏｇｒａｐｈｙ）であり、セキュアな通信を保証するために量子力学を使用する。量子もつれ（ｑｕａｎｔｕｍ  ｅｎｔａｎｇｌｅｍｅｎｔ）などの量子の状態を使用して、盗聴の量を検出し、そしてこれを修正した後にセキュアな通信を可能とする、通信システムを設計しそして実施することが可能である。第２の方法は、それぞれのノードが一意なチャンネル・インパルス応答を共有する、ＪＲＮＳＯ（Ｊｏｉｎｔ−Ｒａｎｄｏｍｎｅｓｓ−Ｎｏｔ−Ｓｈａｒｅｄ−ｂｙ−Ｏｔｈｅｒｓ）の技法に関連した無線チャンネルの使用を伴う。これらの以前の活動は、２つのノードの間での秘密鍵の発生を検討していることに触れておくべきである。２つより多いノードがある通信システムにおいては、すべてのノードまたは２つより多いノードの部分集合が、セキュアなグループ通信のために共通的な秘密鍵を共有することが必要である。以前の活動は、２つより多いノードについて最適な秘密鍵を如何に確立するかを理論上で説明しているが、２つより多いノードがある通信システムにおいて、最適かまたはほぼ最適に働く最適な秘密鍵を確立するための実用的なアルゴリズムを説明することに成功してはいない。さらに、この分野における以前の活動は、複数の基本的なランダム発生源と直接的に機能するグループ鍵の発生アルゴリズムを必要とする。しかしながら、そのようなアプローチは複雑であり、そして事前に発生された対用の鍵に基づきグループ鍵を発生させるアプローチが要求される（すなわち、対用鍵発生問題のみがランダム発生源についての情報を使用する）。そのような階層化は、現存の階層化された通信システムにおける使用を容易にするであろう。したがって、そのようなシステムにおいてグループ用の秘密鍵を発生させるための最適化された方法の実用的な実施方法が必要である。さらに、そのような実施方法が階層化構造であることが望まれる。
【０００５】
秘密鍵容量（Ｓｅｃｒｅｔ  Ｋｅｙ  Ｃａｐａｃｉｔｙ）  
秘密鍵容量の概念は、以下のように定義される。
【０００６】
【数１】
2010504695.tif 000003
【０００７】
のネットワーク・ノードが個々に、ｎの時間間隔に亘って、
【０００８】
【数２】
2010504695.tif 000004
【０００９】
の、ｍ個の独立な、かつ同様に分布した繰り返しを観測すると仮定する。これらのｍ個のノードは、共通な秘密鍵Ｋ（すなわち、グループ用の）を発生させることを望む。そうするために彼らは誤りのない公衆ブロードキャスト・チャンネルを通して互いに通信可能である。秘密鍵レートＨ（Ｋ）／ｎは、秘密鍵Ｋのエントロピー・レートによって定義される。最大の秘密鍵レートは、ＣSにより表され、秘密鍵容量と呼ばれる。秘密鍵容量ＣSの概念は、これらｍ個のノードにより発生可能な最大の秘密鍵の長さを示す。
【００１０】
図１は３つのノード１０１、ノード１０２、およびノード１０３のネットワークを示し、鍵Ｋ1,2がノード１０１およびノード１０２の間に存在し、鍵Ｋ1,3がノード１０１およびノード１０３の間に存在し、そして鍵Ｋ2,3がノード１０２およびノード１０３の間に存在する。
【００１１】
当技術分野において、秘密鍵容量ＣSは、以下の式により計算可能であることが知られている：
【００１２】
【数３】
2010504695.tif 000005
【００１３】
【数４】
2010504695.tif 000006
【００１４】
２つのノード（ｍ＝２）の場合には、式（１）は縮小し、以下のようになる：
【００１５】
【数５】
2010504695.tif 000007
【００１６】
ここで、Ｉは相互情報量(ｍｕｔｕａｌ  Ｉｎｆｏｒｍａｔｉｏｎ)を表す。
３つのノード（ｍ＝３）の場合には、式（１）は縮小し、以下のようになる：
【００１７】
【数６】
2010504695.tif 000008
【００１８】
上で記述されたグループ用の秘密鍵問題に式（３）を置き換えると、グループ用の秘密鍵は、
【００１９】
【数７】
2010504695.tif 000009
【００２０】
より長いはずがないということである。
【発明の概要】
【００２１】
ノードのグループの中で完全な秘密鍵を構成するための方法および機構が開示される。ｍ個のノードよりなるグループにおいて、対用（ｐａｉｒ−ｗｉｓｅ）の秘密鍵が割り当てられる。対用の秘密鍵に基づき、これらのｍ個のノードはグループ用（ｇｒｏｕｐ−ｗｉｓｅ）の完全な秘密鍵を発生させる。
【００２２】
例として与えられかつ添付された図面に関連して理解されるべき好適な実施形態の以下の記述から、本発明のより詳細な理解を得ることができる。
【図面の簡単な説明】
【００２３】
【図１】３つのノードおよび３つの対用の鍵を持つ代表的通信ネットワークを例証する図である。
【図２】グループ用の完全な秘密鍵の発生を表現する方法のフロー図である。
【図３】３つのノードの通信ネットワークに関する重み付きのグラフである。
【図４】図２のネットワークに関する、グループ用の秘密鍵発生の第１の繰り返しの後の重み付きのグラフである。
【図５】図２のネットワークに関する、グループ用の秘密鍵発生の第２の繰り返しの後の重み付きのグラフである。
【図６】図２のネットワークに関する、グループ用の秘密鍵発生の第３の繰り返しの後の重み付きのグラフである。
【図７】グループ用の秘密鍵発生を実施するための方法のフロー図である。
【図８】グループ用の秘密鍵発生を実施するための方法のフロー図である。
【図９】グループ用の秘密鍵を共有する３つの無線送受信ユニットを示すブロック図である。
【図１０】光ファイバー・ネットワーク上でグループ用の秘密鍵を共有する３つのノードを示すブロック図である。
【図１１】８つのノードから成るネットワークを示す図である。
【図１２】グループ用の秘密鍵を発生させるために使用される図１１のネットワークに対するスパニング・ツリーを示す図である。
【発明を実施するための形態】
【００２４】
これ以後参照されると、用語「ＷＴＲＵ（Ｗｉｒｅｌｅｓｓ  Ｔｒａｎｓｍｉｔ  Ｒｅｃｅｉｖｅ  Ｕｎｉｔ：無線送受信ユニット）」は、限定的ではなく、ＵＥ（Ｕｓｅｒ  Ｅｑｕｉｐｍｅｎｔ：ユーザー装置）、ネットワーク・ノード、移動端末、固定型または移動体の加入者ユニット、ページャー、携帯電話、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ：携帯情報端末）、コンピューター、または無線環境において動作する能力のある他の如何なる種別のユーザー・デバイスをも含む。これ以後参照されると、用語「基地局（ｂａｓｅ  ｓｔａｔｉｏｎ）」は、限定的ではなく、ノードＢ（Ｎｏｄｅ−Ｂ）、サイトコントローラー、ＡＰ（Ａｃｃｅｓｓ  Ｐｏｉｎｔ：アクセス・ポイント）、または無線環境において動作する能力のある他の如何なる種別のインターフェイス・デバイスをも含む。
【００２５】
第１の実施形態において、ノードのグループの中での完全な秘密鍵を構成するためのアルゴリズムおよび機構が開示される。ｍ個のノードより成るネットワークにおいては、あらゆる対のＷＴＲＵが完全な秘密鍵を既に発生させていると仮定する。ＪＲＮＳＯ（Ｊｏｉｎｔ−Ｒａｎｄｏｍｎｅｓｓ−Ｎｏｔ−Ｓｈａｒｅｄ−ｂｙ−Ｏｔｈｅｒｓ）による完全な秘密鍵を発生させるための代表的方法は、参照により本発明に組み込まれた、同一出願人により２００６年１月２６日に出願された米国特許申請番号１１／３３９，９５８において開示されている。１対のＷＴＲＵによって共有される秘密鍵は、他のすべてのＷＴＲＵの知識から統計的に独立している。これらのｍ個のＷＴＲＵは、対用の完全な秘密鍵に基づきグループ用の完全な秘密鍵を発生させることを望む。そうするためにそれぞれのＷＴＲＵは、公衆のブロードキャストを通して他のあらゆるＷＴＲＵと通信することが可能である。共有された鍵における誤りによる通信不良を回避するために、公衆ブロードキャストが誤りのない状態で受信されるように、適切なチャンネル保護符号を適用することが可能であると仮定される。誤りのない通信のための１つのそのような技法には、ＦＥＣ（Ｆｏｒｗａｒｄ  Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ）の使用が含まれるであろう。盗聴者は、対用の秘密鍵についての何の情報もなしに、ｍ個のＷＴＲＵの間の公衆伝送を観測することができる。
【００２６】
代替の実施形態においては、複数のＦＴＲＵ（光ファイバー・リンクによって接続されたノード）のグループの中で完全な秘密鍵を構成するためのアルゴリズムおよび機構が開示される。ｍ個のノードより成るネットワークにおいては、あらゆる対のＦＴＲＵは、よく知られている量子暗号化の方法を使用して完全な秘密鍵を既に発生させていると仮定する。１対のＦＴＲＵによって共有される秘密鍵は、他のすべてのＦＴＲＵの知識から統計的に独立している。これらのｍ個のＦＴＲＵは、対用の完全な秘密鍵に基づいてグループ用の完全な秘密鍵を発生させることを希望する。それらがそうする機能は、ＷＴＲＵがそれらのグループ用の共有された鍵を発生させる機能と同じである。
【００２７】
量子暗号化または無線チャンネルに基づく鍵発生の何れかを使用する方法は、以下のように数学的に表現することができる。
【００２８】
【数８】
2010504695.tif 000010
【００２９】
一般性を喪失することなく、あらゆる対用の秘密鍵Ｋi,jが完全エントロピーのビット・ストリングであると仮定される。すなわち、
【００３０】
【数９】
2010504695.tif 000011
【００３１】
ここで、｜．｜はビット・ストリングの長さを表し、そしてＨはエントロピーを表す。ストリングが完全（ｆｕｌｌ）エントロピーのビット・ストリングであることを保証するためによく知られている高性能アルゴリズムの何れをも使用可能である。完全エントロピーに対して一般的に実施されるアルゴリズムには、ＢＺＩＰにおいて使用されるＢｕｒｒｏｗｓ−Ｗｈｅｅｌｅｒ変換が含まれる。Ｖが、ｍ個のＷＴＲＵの間の公衆ブロードキャスト・チャンネル伝送において含まれるすべての情報を表すとする。伝送の後に、ＷＴＲＵｉは以下の制約に従ってグループ用の秘密鍵Ｋを計算する。
【００３２】
【数１０】
2010504695.tif 000012
【００３３】
ここで、式（７）はグループ用の秘密鍵が盗聴者の情報、公衆チャンネル上の情報Ｖ、からほとんど統計的に独立していること、および式（８）はグループ用の秘密鍵が完全エントロピーのビット・ストリングであることを表す。その条件から、グループ用の秘密鍵Ｋが、完全に秘密鍵であることを含意する。したがって、結果としてのグループ用の秘密鍵の長さを最大にするための方法および機構が望まれる。以下は、第１の実施形態を容易にするためにそのようなネットワークのグラフ的表現について記述する。
【００３４】
ｉ、ｊ∈Ｎであるあらゆる２つのそれぞれのノードに対して、ノードｉからノードｊへの経路（ｐａｔｈ）が存在するなら、Ｎ個のノードおよびＥ個の辺（ｅｄｇｅ）を持つ無向性（ｕｎｄｉｒｅｃｔｅｄ）グラフＧ＝（Ｎ、Ｅ）は接続（連結）されていると称される。そうでないなら、グラフは接続（連結）されていないと称される。図１を参照すると、ノード１０１、１０２、および１０３を持つ接続されているグラフが示され、それぞれのノードの対が、対用の秘密鍵Ｋl,2、Ｋ1,3、Ｋ2,3を共有する。重み付きのグラフは、数字の重みをグラフ中のあらゆる辺に関連付ける。また図１を参照すると、辺の重みは、それらの辺の各々の対用の秘密鍵Ｋl,2、Ｋ1,3、Ｋ2,3によって表される。表現された鍵が１ビットのみでできているため、それぞれの辺はすべて、１つの重みを有する。重み付きのグラフにおけるツリーの重みは、選択された辺の重みの合計である。
【００３５】
グラフＧ＝（Ν、Ｅ）についてのカット（ｃｕｔ）とは、ノード群Ｎの２つの集合Ｎ1、Ｎ2への分割である。ｉ∈Ｎ1およびｊ∈Ｎ2である何れの辺（ｉ、ｊ）∈Ｅもカット辺であると称される。重み付きグラフにおいては、カットの大きさは、その辺の重みの合計であると定義される。カットの大きさが、他の何れのカットの大きさよりも大きくないなら、そのカットは最小である。
【００３６】
接続されている無向性グラフＧ＝（Ν、Ｅ）を与えられ、Ｅ1を、スパニング・ツリーがＴ＝（Ｎ、Ｅ1）により定義されるような、Ｅの部分集合であるとする。重み付きグラフからの最小スパニング・ツリーは、その辺の重みの合計が可能な限り小さいように定義される。最小スパニング・ツリーを見出すという問題は、グリーディ（ｇｒｅｅｄｙ）・アルゴリズムなどの、最適化アルゴリズムにより解決することが可能である。そのような技法においては、複合最適化問題はそれぞれのステップにて単純な局所的最適化問題を解決することによる（例えば、グリーディ・アルゴリズムによる）繰り返し法にて解決される。そうすることで、これらのアルゴリズムは通常は低い計算上の複雑性を実現し、多くの最適化問題に対して証明可能な程度に最適な、またはほぼ最適な解をもたらす。ＫｒｕｓｋａｌのアルゴリズムおよびＰｒｉｍのアルゴリズムが、最小スパニング・ツリー問題を解決することが可能なグリーディ・アルゴリズムの２つの例である。
【００３７】
Ｋｒｕｓｋａｌのアルゴリズムは以下のステップにより要約される：
１．重みにより増加する順番にＧの辺をソートする；
２．初期的には空の、Ｇの部分グラフＴを保持する；
３．ソートされた順番におけるそれぞれの辺ｅに対して、ｅの端点がＴにて接続されていないなら、Ｔにｅを加える；
４．Ｔを返す。
【００３８】
Ｐｒｉｍのアルゴリズムは以下のステップにより要約される：
１．ＴがＧにおける単一のノードであるとする；
２．（Ｔが、Ｇより少ないノードを有する）なら以下を繰り返す;
３．ＴをＧ−Ｔに接続している最小の重みの辺を見出す;
４．Ｔにそれを加える；
５．Ｔを返す。
【００３９】
ＫｒｕｓｋａｌアルゴリズムおよびＰｒｉｍアルゴリズムのそれぞれの実行時間は、Ｏ（ｒ＋ｍｌｏｇｍ）およびＯ（ｍ2）によって表され、ここでｍおよびｒはそれぞれＧにおけるノードおよび辺の数である。
【００４０】
図２を参照すると、フロー図がグループ用の秘密鍵を発生させるという問題を如何に解決するかに関する例を示す。第一のステップ２３０において、統計的にランダムな発生源が、対用の秘密鍵を作成するために要求される。図２においては、発生源はチャンネル測定または量子測定の何れかにより実行可能である、物理的測定を通して導出される。発生源測定は次にステップ２２０にて、対用の完全な秘密鍵を発生させるために使用される。最終的にステップ２１０にて、この対用の完全な秘密鍵が、２つより多いノードを持つシステムに対してグループ用の秘密鍵を発生させるために使用される。
【００４１】
グループ用の秘密鍵発生の問題は、重み付けされた無向性グラフによりモデル化が可能である。図３は、ノード３０１、３０２、および３０３を有する、３つのノードのネットワークに対する重み付きのグラフを示す。グラフのそれぞれのノードは、ネットワーク・ノードまたはＷＴＲＵを表し、そしてそれぞれの対用の秘密鍵は、対応するノードを接続する辺であるとみなされる。辺の重みは、対応する対用の秘密鍵の長さと等しく、常に非負の整数である。図３を参照して、例えばノード３０１、３０２、および３０３が、それぞれ長さ５、４、および３を持つ対用の秘密鍵Ｋl,2、Ｋ1,3、およびＫ2,3を共有すると仮定する。
【００４２】
以下の補助定理は、ｍ個のノード間の１つの秘密ビットを、対応する辺がスパニング・ツリーを構成するｍ−１個の対用の秘密鍵からの１ビットに基づき発生させることについて議論する。ｍ個のノードを接続する任意のツリーを考慮する。ツリー上の隣接ノードのあらゆる対が１つの対用の秘密ビットを共有する場合には、１つの秘密ビットはすべてのｍ個のノードの間で発生可能である。以下の方法は、ｍ個のノードすべての間で秘密ビットを発生させる方法を提示する。
【００４３】
ステップ１：スパニング・ツリーから辺（ｉ1、ｉ2）を選択する。ノードｉ1およびｉ2は秘密ビットＫi1,i2を共有する。
【００４４】
ステップ２：ノードｊが、その鍵を共有しているノードｉ1またはノードｉ2の何れかから秘密ビットＫi1,i2を知っているが、その隣接ノードｋは秘密ビットＫi1,i2を知らない場合には、ノードｊがノードｋに、
【００４５】
【数１１】
2010504695.tif 000013
【００４６】
を送出する。ここで、Ｋj,kは、ノードｊおよびｋにより共有される秘密ビットである。このメッセージを受け取ると、ノードｋは秘密ビットＫi1,i2を復号化することができる。上記の条件が成立しなくなるまで、このステップを繰り返す。
【００４７】
すべてのノードがＫi1,i2を復号化できると、繰り返しは完了する。言い換えれば、秘密ビットＫi1,i2はスパニング・ツリーに沿ってセキュアに送信される。対用の秘密鍵は式（５）および式（６）を満足させるので、秘密ビットＫi1,i2はすべての伝送から独立であり、すなわち、
【００４８】
【数１２】
2010504695.tif 000014
【００４９】
である。ここで、Ｋi1,i2はｍ個のノードすべてにより共有される秘密ビットである。
【００５０】
図７を参照すると、上で記述された秘密ビットを共有する方法を実施する方法７００が示される。ステップ７１０において、ＷＴＲＵがスパニング・ツリーから辺を選択する。この辺の選択は、ランダム選択か、あるいは最大のまたは最小の辺の重みを選択することによるか、であることが可能である。次のステップ７２０において、秘密鍵ビットＫi1,i2が隣接するＷＴＲＵによって知られているか否かを、ＷＴＲＵが判定する。Ｋi1,i2が知られていない場合には、ステップ７３０にてＷＴＲＵは
【００５１】
【数１３】
2010504695.tif 000015
【００５２】
を隣接するＷＴＲＵに送出する。ステップ７４０にてここで、隣接するＷＴＲＵは秘密ビットＫi1,i2を復号化することができる。次の辺が選択され（７４５）、そして秘密ビットがＷＴＲＵのそれぞれによって共有されるまで、処理は連続して続けられる。あるいはまた、１ビットより多い秘密ビットを選択し、そして対用の秘密鍵とのＸＯＲ結合を使用してそれぞれの伝送と共有することが可能である。それぞれの秘密鍵ビットに対して、一意な対用の秘密鍵ビットがそれにＸＯＲ結合されねばならない。
【００５３】
秘密ビットが方法７００を使用して共有される場合に対しては、複数ビットの最適化されたグループ用の秘密鍵を構成するために以下の方法ステップが使用される。最大のおよび最小のスパニング・ツリーを決定するという問題は等価であることに注意を要する。辺の重みを無効にし、そして結果のグラフにおいて最小スパニング・ツリー問題を解くことによって、最大のスパニング・ツリーを決定することが可能である。
【００５４】
ステップ３：グリーディ・アルゴリズム（例えば、ＫｒｕｓｋａｌまたはＰｒｉｍのアルゴリズム）を使用して、所与の接続された重み付きのグラフから最大スパニング・ツリーを決定する。
【００５５】
ステップ４：上で記述されたように方法７００を適用することによって、すべてのノードの間での１つの秘密ビットを発生させる。盗聴者に漏えいしている対用秘密鍵における使用済みビットが、残余のグループ用秘密鍵の発生経過において何の役にも立たないことに注意を要する。
【００５６】
ステップ５：決定したスパニング・ツリーにおける辺について、辺の重みを１だけ減少させることによって、グラフを更新する。重みがゼロになった場合には、その辺を除去する。
【００５７】
ステップ６：残余のグラフが接続されていないなら、そこで停止する。さもなければ、ステップ３に戻る。
【００５８】
ステップ３〜６のそれぞれの繰り返し毎に共通的な１つの秘密ビットが発生する。したがって、秘密鍵の全体の長さはグラフが接続されていない状態になるまで動作し得る繰り返しの数と等しい。最大のスパニング・ツリーを捜すこと（任意のスパニング・ツリーを拾い出すことよりむしろ）の目的は、重み除去の手順において辺の重みの「バランスをとること」により、アルゴリズムにおける繰り返しの数を最大にすることである。
【００５９】
図８を参照すると、上のステップ３〜６を取り入れた方法８００が示される。第一のステップ８１０は、所与の重み付きのグラフから最大のスパニング・ツリーを決定する先導的ＷＴＲＵにかかわる。最大のスパニング・ツリーが決定すると、ＷＴＲＵは方法７００を使用し、ステップ８２０〜８４０により記述された共通的な１つの秘密ビットを発生させる。繰り返しの後に、かかわる辺に対して重みを１だけ減少させることによって、グラフを更新せねばならない（ステップ８５０）。グラフが接続されていない状態になるまで、この処理を繰り返す（ステップ８６０）。結果としてグループ用の秘密鍵は、ＷＴＲＵのすべてによって共有されることになる最大の可能な長さを有することになる。グループ用の共有された鍵によりＷＴＲＵが、そのネットワークの中のＷＴＲＵだけが復号化可能なメッセージを公衆にブロードキャストすることが可能になる。図８によって表現された実施形態は、繰り返しの間の１つの秘密ビットの伝送を示すが、同等の数の対用秘密ビットが複数の秘密ビットとＸＯＲ結合されさえすれば、繰り返しの間に複数の秘密ビットを送信することができる。
【００６０】
図９は、無線接続上にネットワークを形成する、３つのＷＴＲＵ９１０、９２０、および９３０のブロック図を示す。ＷＴＲＵ９１０は、先導的ノードとして動作し、そして上で記述された手順を起動し、かつネットワーク形態を決定する。先導的ノードは、可能な限り多くのビットを持つ秘密鍵を作成しようとする。ＷＴＲＵ９１０は、グループ用の共有された鍵を発生させるために方法７００および８００を実施するように構成された処理装置９１５を具備する。そしてＷＴＲＵ９１０は、鍵の選択に関して他のＷＴＲＵ９２０および９３０に通知するメッセージを送出する。ＷＴＲＵ９２０および９３０は、鍵を処理するためにそれぞれ処理装置９２５および９３５を含む。この実施形態の描写は３つのＷＴＲＵのみを示すが、この処理が任意の数のＷＴＲＵまたはノードに適応可能であることに注意するべきである。さらに図９は、特定のノードが先導的ノードとして動作するように表現しているが、何れのノードも決定を為すことが可能である。別の実施形態においては、先導的ノードが決定を為し、そしてそのノードが伝送の数を減少させることを可能にしつつ、それぞれのノードに、為すべき動作と共にこの決定を送信する。さらに別の実施形態においては、無線ローカル・エリア・ネットワークのホットスポットまたは基地局が、上で記述された手順を起動することが可能である。
【００６１】
図１０を参照すると、別の実施形態の装置およびネットワークが示される。それぞれのノードは、量子暗号化を使用して対用の秘密鍵を発生させる。ノードは光ファイバー・ネットワーク１０４０を介して接続される。ノード１０１０は、先導的ノードとして動作し、ならびに上で記述した手順を起動し、そしてネットワーク形態を決定する。先導的ノードは、可能な限り多くのビットを持つ秘密鍵を作成しようとする。先導的ノードの処理装置１０１５は、グループ用の共有された鍵を発生させるために方法７００および８００を実施するように構成される。次に先導的ノードは、光ファイバー・ネットワーク上にメッセージを送出し、他のノード１０２０および１０３０に鍵の選択に関して通知する。ノード１０２０および１０３０は、鍵を処理するためにそれぞれ処理装置１０２５および１０３５を含む。この実施形態の描写は３つのノードのみを示すが、この処理が、光ファイバー・ネットワーク上で接続された任意の数のノードに適用可能であることに注意するべきである。
【００６２】
図３に戻って、方法８００を使用してグループ用の秘密鍵を発生させる処理がここで記述される。
【００６３】
【数１４】
2010504695.tif 000016
【００６４】
第１の繰り返し：
【００６５】
ステップ１において、辺（（１、２）、（１、３））より成るスパニング・ツリーが、スパニング・ツリーの重みの合計が９であり、他のスパニング・ツリーのものより大であるため、選択される。
【００６６】
【数１５】
2010504695.tif 000017
【００６７】
この繰り返しの終わりには、重み付きのグラフが図４に示されるように調整される。
【００６８】
第２の繰り返し：
【００６９】
ステップ１において、辺（（１、２）、（１、３））より成るスパニング・ツリーが決定される。
【００７０】
【数１６】
2010504695.tif 000018
【００７１】
この繰り返しの終わりには、重み付きのグラフは図５に示されるように調整される。
【００７２】
第３の繰り返し：
【００７３】
ステップ１において、辺（（１、２）、（２、３））より成るスパニング・ツリーが決定される。
【００７４】
【数１７】
2010504695.tif 000019
【００７５】
この繰り返しの終わりには、重み付きのグラフが図６に示されるように調整される。
【００７６】
グラフが接続されていない状態になるまで繰り返しが続く。合計６つの繰り返しが、グラフが接続されていない状態になるまでに実行される。最後の３つの繰り返しは図に表現されていないが、最後の３つの繰り返しにおけるスパニング・ツリーおよび公衆伝送は、それぞれ、
【００７７】
【数１８】
2010504695.tif 000020
【００７８】
上で記述されたように、この例における達成可能な最大の秘密鍵は、６ビットを超えない。方法７００はこの上限を達成する。
【００７９】
図１１を参照して、それぞれのノードが端末として表される、８つのノードを持つネットワークを考慮しよう。ネットワークの中では、端末は対用の完全な秘密鍵を取得している。それぞれの対用の完全な秘密鍵は、統計的に独立である。
【００８０】
図１２においては、スパニング・ツリー１２００が図１１において示されるネットワークから選択される。スパニング・ツリーのそれぞれの辺は、１ビットの対用の秘密鍵（Ｋa,b、Ｋa,c、Ｋb,d、Ｋb,e、Ｋc,f、---）を表す。グループ用の完全な秘密鍵を作成するために、ノードａは、グループ用の秘密鍵として選ばれるであろう鍵Ｋa,bまたは鍵Ｋa,cから選択することになる。この例の目的のために、ノードａが鍵Ｋa,bを選択したと仮定するがしかしながら実際には、何れかのビットがランダムにまたはアルゴリズムを通して、選択できるであろう。ノードａは次に、ノードｂに
【００８１】
【数１９】
2010504695.tif 000021
【００８２】
を送信するか、または何も送信しないかの何れかである。これは、秘密ビットとしてＫa,bが選択されたことをノードｂに確認することになる。さらに、ノードａは
【００８３】
【数２０】
2010504695.tif 000022
【００８４】
をノードｃに送信することになり、ノードｃがその対用の秘密鍵Ｋa,cを使用して復号化することが可能になる。同様に、ノードｂおよびノードｃは次に、鍵Ｋa,bをノードｄ，ｅ、およびｆへ、それぞれのノードの対用の秘密鍵ビット（それぞれ、Ｋb,d、Ｋb,e、Ｋc,f）により畳み込む（ｃｏｎｖｏｌｖｅ）ことにより、送信する。鍵Ｋa,bがスパニング・ツリー全体に知られて、そしてグループ用の秘密鍵Ｋa,bがすべてのノードによって知られるようになるまで、この処理が続けられる。図１１において表現される実施形態は、８つのノードのみを示しているが、何れの数のノードにもこの処理は適用可能である。さらに図１２における実施形態は、１ビットのみの秘密鍵を表現するが、何れの長さの秘密ビットをも使用することができる。実施形態への変形において、ノードは隣接するノードに１ビットより多い秘密ビットを送信することができる。あるいはまた、それぞれの繰り返しの後にスパニング・ツリーが再選択される。
【００８５】
実施形態
１．対称鍵暗号化を利用する複数のＷＴＲＵ（Ｗｉｒｅｌｅｓｓ  Ｔｒａｎｓｍｉｔ  Ｒｅｃｅｉｖｅ  Ｕｎｉｔ：無線送受信ユニット）を有する無線通信システムにおいて、グループ用の完全な秘密鍵を発生させるための方法であって、
ａ）少なくとも２つのＷＴＲＵの間で対用の完全な秘密鍵を発生させるステップと、
ｂ）前記対用の秘密鍵を使用してグループ用の完全な秘密鍵Ｋを選択するステップと
を具備することを特徴とする方法。
２．ｃ）対用の完全な秘密鍵とのＸＯＲ結合を使用して、前記グループ用の完全な秘密鍵を公衆ブロードキャスト・チャンネル上で別のＷＴＲＵに送信するステップと
をさらに具備することを特徴とする実施形態１に記載の方法。
３．ｃ）前記複数のＷＴＲＵからスパニング・ツリーを決定するステップであって、前記スパニング・ツリーが、対用の完全な秘密鍵の長さに等しいそれぞれのＷＴＲＵ対の間の辺の重みを有することと、
ｄ）ｍ個のＷＴＲＵの中でｍ−１個の対用の秘密鍵によりグループ用の完全な秘密鍵を発生させるステップと、
ｅ）前記スパニング・ツリー上の鍵の長さにより辺の重みを減少させるステップと
をさらに具備することを特徴とする実施形態１〜２の何れかに記載の方法。
４．前記スパニング・ツリーが最大のスパニング・ツリーであることを特徴とする実施形態１〜３の何れかに記載の方法。
５．ｃ）スパニング・ツリーに対して、前記グループ用の完全な秘密鍵であるべき対応する対用の秘密ビットを有する辺を選択するステップと、
ｄ）第１のＷＴＲＵにて、隣接するＷＴＲＵが前記選択された辺の秘密ビットに関する知識を欠いているかを判定するステップと、
ｅ）ＸＯＲ結合を使用して、前記第１のＷＴＲＵおよび隣接するＷＴＲＵによって共有された前記対用の秘密鍵により前記選択された辺の秘密ビットを前記第１のＷＴＲＵから前記隣接するＷＴＲＵへ送信するステップと、
ｆ）前記隣接するＷＴＲＵにて前記選択された辺の秘密鍵ビットを復号化するステップと、
ｇ）すべてのＷＴＲＵが前記秘密ビットを共有するまでステップｃ）からｆ）を繰り返すステップと
をさらに具備することを特徴とする実施形態１〜４の何れかに記載の方法。
６．ｈ）前記複数のＷＴＲＵから最大のスパニング・ツリーを決定するステップであって、前記最大のスパニング・ツリーが、対用の秘密鍵の長さに等しいそれぞれのＷＴＲＵの間の辺の重みを有することと、
ｉ）ステップｅ）に続いて、前記最大のスパニング・ツリーについて辺の重みを１ビットだけ減少させるステップと、
ｊ）その辺の重みがゼロになると、前記スパニング・ツリーから辺を除去するステップと
をさらに具備することを特徴とする実施形態１〜５の何れかに記載の方法。
７．前記最大のスパニング・ツリーを決定するステップが、グリーディ・アルゴリズムを使用して達成されることを特徴とする実施形態１〜６の何れかに記載の方法。
８．前記グリーディ・アルゴリズムが、ＫｒｕｓｋａｌアルゴリズムおよびＰｒｉｍアルゴリズムから成るグループから選択されることを特徴とする実施形態１〜７の何れかに記載の方法。
９．最大のスパニング・ツリーを決定するステップが、このＷＴＲＵに接続しているすべての辺の合計が最大であるようにＷＴＲＵを選択するステップを含むことを特徴とする実施形態１〜３の何れかに記載の方法。
１０．前記対用の完全な秘密鍵が、前記対用チャンネルの結合ランダム性（ｊｏｉｎｔ  ｒａｎｄｏｍｎｅｓｓ）に基づき発生されることを特徴とする実施形態１〜９の何れかに記載の方法。
１１．前記対用の完全な秘密鍵が、量子もつれに基づき発生されることを特徴とする実施形態１〜９の何れかに記載の方法。
１２．対称鍵暗号化を利用する複数のＷＴＲＵ（Ｗｉｒｅｌｅｓｓ  Ｔｒａｎｓｍｉｔ  Ｒｅｃｅｉｖｅ  Ｕｎｉｔ：無線送受信ユニット）を有する無線通信システムにおいて、グループ用の完全な秘密鍵を発生させる能力のあるＷＴＲＵであって、
接続されたＷＴＲＵと対用の完全な秘密鍵を発生するように構成された処理装置と、
公衆ブロードキャスト・チャンネル上の秘密鍵を受信するための受信機と、
前記対用の秘密鍵に基づきグループ用の完全な秘密鍵Ｋを決定するための処理装置と
を具備することを特徴とするＷＴＲＵ。
１３．前記対用の完全な秘密鍵とＸＯＲ結合された前記グループ用の完全な秘密鍵チャンネルを公衆ブロードキャスト上で送信するための送信機をさらに具備することを特徴とする実施形態１２に記載のＷＴＲＵ。
１４．前記処理装置が、辺から秘密ビットを選択するように構成されることであって、前記ＷＴＲＵおよび隣接するＷＴＲＵによって共有された前記対用の秘密鍵により結合された前記隣接するＷＴＲＵへ選択された辺の秘密ビットを送信するように構成された送信機をさらに具備することを特徴とする実施形態１２〜１３の何れかに記載のＷＴＲＵ。
１５．対称鍵暗号化を利用する複数のノードを有する光ファイバー通信ネットワークにおいて、グループ用の完全な秘密鍵を発生させるための方法であって、
ａ）少なくとも２つのノードの間で量子暗号化を使用して対用の完全な秘密鍵を発生させるステップと、
ｂ）前記対用の秘密鍵を使用してグループ用の完全な秘密鍵Ｋを選択するステップと
を具備することを特徴とする方法。
１６．ｃ）対用の完全な秘密鍵とのＸＯＲ結合を使用して、前記グループ用の完全な秘密鍵を公衆ブロードキャスト・チャンネル上で別のノードに送信するステップと
をさらに具備することを特徴とする実施形態１５に記載の方法。
１７．ｃ）前記複数のノードからスパニング・ツリーを決定するステップであって、前記スパニング・ツリーが、対用の完全な秘密鍵の長さに等しいそれぞれのノード対の間の辺の重みを有することと、
ｄ）ｍ個のノードの中でｍ−１個の対用の秘密鍵によりグループ用の完全な秘密鍵を発生させるステップと、
ｅ）前記スパニング・ツリー上の鍵の長さにより辺の重みを減少させるステップと
をさらに具備することを特徴とする実施形態１５〜１６の何れかに記載の方法。
１８．前記スパニング・ツリーが最大のスパニング・ツリーであることを特徴とする実施形態１５〜１７の何れかに記載の方法。
１９．ｃ）スパニング・ツリーに対して、前記グループ用の完全な秘密鍵であるべき対応する対用の秘密ビットを有する辺を選択するステップと、
ｄ）第１のノードにて、隣接するノードが前記選択された辺の秘密ビットに関する知識を欠いているかを判定するステップと、
ｅ）ＸＯＲ結合を使用して、前記第１のノードおよび隣接するノードによって共有された前記対用の秘密鍵により前記選択された辺の秘密ビットを前記第１のノードから前記隣接するノードへ送信するステップと、
ｆ）前記隣接するノードにて前記選択された辺の秘密鍵ビットを復号化するステップと、
ｇ）すべてのノードが前記秘密ビットを共有するまでステップｃ）からｆ）を繰り返すステップと
をさらに具備することを特徴とする実施形態１５〜１８の何れかに記載の方法。
２０．ｈ）前記複数のノードから最大のスパニング・ツリーを決定するステップであって、前記最大のスパニング・ツリーが、対用の秘密鍵の長さに等しいそれぞれのノードの間の辺の重みを有することと、
ｉ）ステップｅ）に続いて、前記最大のスパニング・ツリーについて辺の重みを１ビットだけ減少させるステップと、
ｊ）その辺の重みがゼロになると、前記スパニング・ツリーから辺を除去するステップと
をさらに具備することを特徴とする実施形態１５の何れかに記載の方法。
２１．前記最大のスパニング・ツリーを決定するステップが、グリーディ・アルゴリズムを使用して達成されることを特徴とする実施形態１５〜２０の何れかに記載の方法。
２２．前記グリーディ・アルゴリズムが、ＫｒｕｓｋａｌアルゴリズムおよびＰｒｉｍアルゴリズムから成るグループから選択されることを特徴とする実施形態１５〜２１の何れかに記載の方法。
２３．最大のスパニング・ツリーを決定するステップが、このノードに接続しているすべての辺の合計が最大であるようにノードを選択するステップを含むことを特徴とする実施形態１５〜１７の何れかに記載の方法。
【００８６】
好適な実施形態において特定の組み合わせにて特徴および要素が記述されているが、それぞれの特徴または要素は、好適な実施形態の他の特徴および要素なしで単独にて、または他の特徴および要素のあるなしにかかわらず様々な組み合わせにて使用可能である。ここに提供された方法またはフロー図は、汎用目的のコンピューターまたは処理装置による実行のために、コンピューターにて読み込み可能な記憶媒体にて実体的に具現化される、コンピューター・プログラム、ソフトウェア、またはファームウェアにて実施することができる。コンピューターにて読み込み可能な記憶媒体の例としては、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ：読み出し専用メモリ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ：ランダム・アクセス・メモリ）、レジスタ、キャッシュ・メモリ、半導体メモリ・デバイス、内蔵ハード・ディスクおよび着脱可能ディスクなどの磁気媒体、磁気−光学媒体、ならびにＣＤ−ＲＯＭディスクおよびＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ：デジタル多用途ディスク）などの光学媒体が含まれる。
【００８７】
適切な処理装置の例としては、汎用目的処理装置、専用目的処理装置、従来の処理装置、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ：デジタル信号処理装置）、複数のマイクロ処理装置、ＤＳＰコアに関連付けられた１つまたは複数のマイクロ処理装置、制御装置、マイクロ制御装置、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）回路、他の何れかの種別のＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ：集積回路）、および／または状態マシンが含まれる。
【００８８】
ＷＴＲＵ（Ｗｉｒｅｌｅｓｓ  Ｔｒａｎｓｍｉｔ  Ｒｅｃｅｉｖｅ  Ｕｎｉｔ：無線送受信ユニット）、ＵＥ（Ｕｓｅｒ  Ｅｑｕｉｐｍｅｎｔ：ユーザー装置）、端末、基地局、ＲＮＣ（Ｒａｄｉｏ  Ｎｅｔｗｏｒｋ  Ｃｏｎｔｒｏｌｌｅｒ：無線ネットワーク制御装置）、または任意のホスト・コンピューターにおいて使用するための無線周波数送受信機を実施するために、ソフトウェアに関連付けられた処理装置を使用することができる。ＷＴＲＵは、ハードウェアおよび／またはソフトウェアにて実施され、カメラ、ビデオカメラ・モジュール、テレビ電話、スピーカーフォン、振動デバイス、スピーカー、マイクロホン、テレビ送受信機、ハンズフリー受話器、キーボード、ブルートゥース（Ｂｌｕｅｔｏｏｔｈ（登録商標））モジュール、ＦＭ（Ｆｒｅｑｕｅｎｃｙ  Ｍｏｄｕｌａｔｅｄ：周波数変調された）無線ユニット、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ：液晶）表示ユニット、ＯＬＥＤ（Ｏｒｇａｎｉｃ  Ｌｉｇｈｔ−Ｅｍｉｔｔｉｎｇ  Ｄｉｏｄｅ：有機発光ダイオード）表示ユニット、デジタル音楽プレーヤー、メディア・プレーヤー、テレビゲーム・プレーヤー・モジュール、インターネット・ブラウザー、および／または任意のＷＬＡＮ（Ｗｉｒｅｌｅｓｓ  Ｌｏｃａｌ  Ａｃｃｅｓｓ  Ｎｅｔｗｏｒｋ：無線ＬＡＮ）モジュールなどのモジュールと連動して使用することができる。
【図１】
2010504695.tif 000023
【図２】
2010504695.tif 000024
【図３】
2010504695.tif 000025
【図４】
2010504695.tif 000026
【図５】
2010504695.tif 000027
【図６】
2010504695.tif 000028
【図７】
2010504695.tif 000029
【図８】
2010504695.tif 000030
【図９】
2010504695.tif 000031
【図１０】
2010504695.tif 000032
【図１１】
2010504695.tif 000033
【図１２】
2010504695.tif 000034
【手続補正書】
【提出日】平成21年5月25日(2009.5.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
グループ用の完全な秘密鍵を発生させるための方法であって、
受信される対用の完全な秘密鍵を受信するステップと、
複数の無線送受信ユニット（ＷＴＲＵ）において隣接するＷＴＲＵと共に使用するために発生される対用の完全な秘密鍵を発生させるステップと、
前記発生された対用の完全な秘密鍵および前記受信された対用の完全な秘密鍵を使用してグループ用の完全な秘密鍵を発生させるステップと
を具備することを特徴とする方法。
【請求項２】
前記選択されたグループ用の完全な秘密鍵を前記発生された対用の完全な秘密鍵とＸＯＲ結合することにより暗号化されたグループ用の完全な秘密鍵を生成するステップと、
前記暗号化されたグループ用の完全な秘密鍵を前記複数のＷＴＲＵにおける１つのＷＴＲＵに送信するステップと
をさらに具備することを特徴とする請求項１に記載の方法。
【請求項３】
前記グループ用の完全な秘密鍵を発生するステップが、
前記複数のＷＴＲＵに対する重み付きグラフを決定するステップであって、前記重み付きグラフが、それぞれの重み付きの辺（ｅｄｇｅ）が前記複数のＷＴＲＵにおける１対のＷＴＲＵを接続している、および前記接続されたＷＴＲＵの対に関連付けられた対用の完全な秘密鍵の長さに対応する重みを有する、複数の重み付きの辺を含む、ステップと、
前記重み付きグラフを使用してグループ用の完全な秘密鍵を選択するステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記グループ用の完全な秘密鍵を選択するステップが、
前記重み付きグラフが接続されたグラフであるという条件により前記重み付きグラフに対する重み付きスパニング・ツリーを計算するステップと、
前記重み付きスパニング・ツリーからの重み付きの辺を、および対応する対用の完全な秘密鍵を、選択するステップと、
前記選択された対応する対用の完全な秘密鍵を前記発生された対用の完全な秘密鍵とＸＯＲ結合することにより、暗号化された対用の完全な秘密鍵を生成するステップと、
前記暗号化された対用の完全な秘密鍵を前記隣接するＷＴＲＵに送信するステップと
を含むことを特徴とする請求項３に記載の方法。
【請求項５】
重み付きスパニング・ツリーを計算するステップが、最大の重み付きスパニング・ツリーを計算するステップを含み、かつ前記グループ用の完全な秘密鍵を選択するステップが、
前記重み付きスパニング・ツリーにおけるそれぞれの重み付きの辺の前記重さを１つずつ減少させることによって、前記重み付きグラフを更新するステップと、
その重みがゼロまで減少した際には、前記重み付きグラフから重み付きの辺を除去するステップと、
前記選択された対応する対用の完全な秘密鍵が前記グループ用の完全な秘密鍵であるという条件により、前記更新された重み付きグラフを使用して前記グループ用の完全な秘密鍵を再選択するステップと
を含むこと特徴とする請求項４に記載の方法。
【請求項６】
前記最大の重み付きスパニング・ツリーを計算するステップが、グリーディ・アルゴリズムを実行するステップを含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記グリーディ・アルゴリズムが、ＫｒｕｓｋａｌアルゴリズムまたはＰｒｉｍアルゴリズムであることを特徴とする請求項６に記載の方法。
【請求項８】
前記発生された対用の完全な秘密鍵を発生させるステップが、前記対用のチャンネルまたは量子もつれの結合ランダム性に基づくことを特徴とする請求項１に記載の方法。
【請求項９】
グループ用の完全な秘密鍵を発生させるための無線送受信ユニット（ＷＴＲＵ）であって、
受信される対用の完全な秘密鍵を受信するように構成された受信機と、
複数のＷＴＲＵにおける隣接するＷＴＲＵと共に使用するために発生される対用の完全な秘密鍵を発生させるように構成された対用鍵発生装置と、
前記発生された対用の完全な秘密鍵および前記受信された対用の完全な秘密鍵を使用してグループ用の完全な秘密鍵を発生させるように構成されたグループ用鍵発生装置と
を具備することを特徴とするＷＴＲＵ。
【請求項１０】
前記選択されたグループ用の完全な秘密鍵を前記発生された対用の完全な秘密鍵とＸＯＲ結合することにより暗号化されたグループ用の秘密鍵を生成するように構成された暗号化装置と、
前記暗号化されたグループ用の完全な秘密鍵を前記複数のＷＴＲＵにおける１つのＷＴＲＵへ送信するように構成された送信機と
をさらに具備することを特徴とする請求項９に記載のＷＴＲＵ。
【請求項１１】
前記グループ用鍵発生装置が、
前記複数のＷＴＲＵに対する重み付きグラフを決定するように構成されたグラフ化装置であって、前記重み付きグラフが、それぞれの重み付きの辺が前記複数のＷＴＲＵにおける１対のＷＴＲＵを接続している、および前記接続されたＷＴＲＵの対に関連付けられた対用の完全な秘密鍵の長さに対応する重みを有する、複数の重み付きの辺を含む、グラフ化装置と、
前記重み付きグラフを使用してグループ用の完全な秘密鍵を選択するように構成されたグループ用鍵選択装置と
を含むことを特徴とする請求項９に記載のＷＴＲＵ。
【請求項１２】
前記グループ用鍵選択装置が、
前記重み付きグラフが接続されたグラフであるという条件により前記重み付きグラフに対する重み付きスパニング・ツリーを計算するように構成されたスパニング・ツリー装置と、
前記重み付きスパニング・ツリーからの重み付きの辺を、および対応する対用の完全な秘密鍵を、選択するように構成された処理装置と、
を含み、
前記暗号化装置が、前記選択された対応する対用の完全な秘密鍵を前記発生された対用の完全な秘密鍵とＸＯＲ結合することにより、暗号化された対用の完全な秘密鍵を生成するように構成され、
前記送信機が、前記暗号化された対用の完全な秘密鍵を前記隣接するＷＴＲＵに送信するように構成された、ことを特徴とする請求項１１に記載のＷＴＲＵ。
【請求項１３】
前記スパニング・ツリー装置が、最大の重み付きスパニング・ツリーを計算するように構成され、
前記グラフ化装置が、前記重み付きスパニング・ツリーにおけるそれぞれの重み付きの辺の前記重みを１つずつ減少させること、およびその重みがゼロまで減少した際には、前記重み付きグラフから重み付きの辺を除去すること、によって前記重み付きグラフを更新するように構成され、
前記グループ用鍵選択装置が、前記選択された対応する対用の完全な秘密鍵が前記グループ用の完全な秘密鍵であるという条件により、前記更新された重み付きグラフを使用して前記グループ用の完全な秘密鍵を再選択するように構成された、ことを特徴とする請求項１２に記載のＷＴＲＵ。
【請求項１４】
前記スパニング・ツリー装置が、ＫｒｕｓｋａｌアルゴリズムまたはＰｒｉｍアルゴリズムを実行するように構成されたことを特徴とする請求項１３に記載のＷＴＲＵ。
【請求項１５】
前記対用鍵発生装置が、前記対用チャンネルまたは量子もつれの結合ランダム性に基づき発生される対用の完全な秘密鍵を発生させるように構成されたことを特徴とする請求項９に記載のＷＴＲＵ。
【国際調査報告】
2010504695.tif 000035
2010504695.tif 000036
2010504695.tif 000037