(57)【要約】【課題】暗号化において当てはまる最悪の場合の想定の下で、盗聴者が、２つの無線端末間で交換される任意のビットを傍受することができ、２つの端末間で秘密鍵を導出するために使用されるアルゴリズムを知っているという難題に直面しながら、相互的無線チャネルから秘密ビット列を明示的に抽出するシステムを設計する必要がある。【解決手段】無線通信ネットワークにおける２つ以上のトランシーバの間の完全にランダムな秘密鍵を生成するための方法および装置が使用される。ポイントツーポイントシステムにおいて、両方のトランシーバが、受信した無線信号に基づいて、チャネルインパルス応答（ＣＩＲ）の推定値を作成する。このＣＩＲ推定値は、同期され、また、エラー訂正および検出を含むことができる。ビット長の長い秘密鍵が、ＣＩＲ推定のデジタル化されたバージョンから生成され、この秘密鍵から、プライバシ増幅によって、完全に秘密の暗号化鍵が導出される。【選択図】図１
2011217415.tif 000002
【特許請求の範囲】
【請求項１】
無線通信のための完全に秘密の暗号化鍵を生成する方法であって、
チャネルインパルス応答（ＣＩＲ）推定を生成するために、第１の無線送受信ユニット（ＷＴＲＵ）において、ＣＩＲを異なるＷＴＲＵにより送信された独立に受信された無線信号に基づいて推定するステップと、
前記ＣＩＲ推定から秘密鍵を生成するステップと、
前記秘密鍵から、完全に秘密の暗号化鍵を生成するステップと
を備えることを特徴とする方法。
【請求項２】
前記秘密鍵から完全に秘密の暗号化鍵を生成するステップは、
前記ＣＩＲ推定からエントロピーを抽出し、公的ビットを除去する汎用ハッシュ関数に従って、前記秘密鍵をマッピングすることを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記秘密鍵から完全に秘密の暗号化鍵を生成するステップは、
バロウズ−ホイラー変換を用いたエントロピ符号化を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記秘密鍵から完全に秘密の暗号化鍵を生成するステップは、
前記秘密鍵のための非システマティック符号を生成することを含むことを特徴とする請求項１に記載の方法。
【請求項５】
第１のＷＴＲＵにおいてシンドロームビットを導出するステップと、
前記シンドロームビットを第２のＷＴＲＵに送信するステップと
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項６】
前記第１のＷＴＲＵにおいて、パリティビットを有するブロックエラー訂正符号を導出するステップと、
前記パリティビットを第２のＷＴＲＵに送信するステップと
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項７】
１つのチャネル条件に基づいて符号のファミリからエラー訂正符号を選択するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項８】
前記エラー訂正符号は、パンクチャリングまたは反復パターンを用いて区別されることを特徴とする請求項７に記載の方法。
【請求項９】
前記チャネル条件は、干渉レベルを含むことを特徴とする請求項７に記載の方法。
【請求項１０】
前記チャネル条件は、ドップラー幅を含むことを特徴とする請求項７に記載の方法。
【請求項１１】
前記チャネル条件は、ドップラー幅、または進行方向、あるいはドップラー幅と進行方向の組み合わせを含むことを特徴とする請求項７に記載の方法。
【請求項１２】
前記チャネル条件は、ビットエラーレートまたはブロックエラーレートに基づいて測定されることを特徴とする請求項７に記載の方法。
【請求項１３】
エラー検出ビットを導出するステップと、
前記エラー検出ビットを、前記ＣＩＲ推定に付加するステップと、
前記エラー検出ビットを含む前記エラー訂正符号を符号化することをさらに含むステップと
をさらに備えることを特徴とする請求項６に記載の方法。
【請求項１４】
前記エラー検出符号は、複数の巡回冗長検査（ＣＲＣ）ビットを含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記受信無線信号は、フレームを含むことを特徴とする請求項１に記載の方法。
【請求項１６】
前記秘密鍵が、予め定義された基準に従って秘密性を妨げる外因的特性に基づいて、排除されるように、弱鍵解析を行うことをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１７】
前記予め定義された基準は、定義された時間内において反復的列を含むことを特徴とする請求項１６に記載の方法。
【請求項１８】
前記推定するステップは、複数のＣＩＲ推定を生成するステップを含み、
前記秘密鍵を生成するステップは、
前記複数のＣＩＲ推定をフィルタリングして、予測された値の集合を作成することと、
推定の現行の集合と前記予測された値との間の差分ベクトルを生成することと、
生成された差分ベクトルを使用して前記秘密鍵を更新すること
のステップによって前記秘密鍵を継続的に更新するステップを含むこと
を特徴とする請求項１に記載の方法。
【請求項１９】
前記差分ベクトルから少なくとも１つのパリティストリームを生成するステップと、
目標の送信レートによるレートで前記パリティストリームに対してパンクチャリングまたは反復を実行するステップと
をさらに備えることを特徴とする請求項１８に記載の方法。
【請求項２０】
１つのチャネル条件に従って前記パンクチャリングレートまたは前記反復レートを調節するステップをさらに含むことを特徴とする請求項１９に記載の方法。
【請求項２１】
前記チャネル条件は、干渉レベルを含むことを特徴とする請求項２０に記載の方法。
【請求項２２】
前記チャネル条件は、ドップラー幅を含むことを特徴とする請求項２０に記載の方法。
【請求項２３】
前記チャネル条件は、ドップラー幅、進行方向、あるいはドップラー幅と進行方向の組み合わせを含むことを特徴とする請求項２０に記載の方法。
【請求項２４】
前記チャネル条件は、ビットエラーレートまたはブロックエラーレートに基づいて測定されることを特徴とする請求項２０に記載の方法。
【請求項２５】
プライバシ増幅が、前記秘密鍵のエラー訂正のためのブロック符号を使用することを含むことを特徴とする請求項１に記載の方法。
【請求項２６】
前記推定するステップは、複数の他の無線送信受信ユニット（ＷＴＲＵ）から受信された複数の無線信号の各々を推定することにより、複数のチャネルインパルス応答（ＣＩＲ）推定を生成することを含み、
前記秘密鍵を生成するステップは、各前記ＣＩＲ推定に基づいて秘密鍵を生成することを含み、
各一時鍵が前記複数の秘密鍵の中の一つの秘密鍵に基づいていて、前記複数の他のＷＴＲＵの中の一つのＷＴＲＵに関連するように、前記秘密鍵を使用して複数の一時鍵を生成するステップと、
前記複数の一時鍵から永久鍵を選択するステップと、
前記それぞれの一時鍵を使用しながら、前記永久鍵を前記複数の他のＷＴＲＵ内の各Ｗ
ＴＲＵに通信するステップと
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項２７】
前記通信するステップは、前記複数の他のＷＴＲＵのツリーグラフを生成することを含むことを特徴とする請求項２６に記載の方法。
【請求項２８】
無線通信において使用される完全に秘密の暗号化鍵を生成する無線送信受信ユニット（ＷＴＲＵ）であって、
異なるＷＴＲＵから受信された独立の無線信号に基づいてチャネルインパルス応答（ＣＩＲ）を推定するように構成されたチャネル推定器と、
秘密鍵を前記ＣＩＲ推定に基づいて作成するように構成されたポストプロセッサと、
前記秘密鍵から完全に秘密の暗号鍵を生成するように構成された暗号プロセッサと
を備えたことを特徴とするＷＴＲＵ。
【請求項２９】
前記暗号プロセッサは、前記ＣＩＲ推定からエントロピを抽出し、公的ビットを除去する汎用ハッシュ関数に従って、前記秘密鍵をマップするようにさらに構成されることを特徴とする請求項２８に記載のＷＴＲＵ。
【請求項３０】
前記暗号プロセッサは、バロウズ−ホイラー変換を実行するように構成されたエントロピエンコーダを備えたことを特徴とする請求項２８に記載のＷＴＲＵ。
【請求項３１】
エラー検出符号に従って複数の巡回冗長検査（ＣＲＣ）ビットを計算し、前記ＣＩＲ推定に付加するように構成されたエラー検出エンコーダをさらに備えたことを特徴とする請求項２８に記載のＷＴＲＵ。
【請求項３２】
前記暗号プロセッサは、前記秘密鍵のために非システマティック符号を生成するように構成されていることを特徴とする請求項２８に記載のＷＴＲＵ。
【請求項３３】
前記秘密鍵を、予め定義された基準に従って秘密性を妨げる外因的特性に基づいて排除するように構成された弱鍵解析器をさらに備えたことを特徴とする請求項２８に記載のＷＴＲＵ。
【請求項３４】
エラー訂正のため、前記異なるＷＴＲＵから受信したパリティビットを復号するように構成されたデコーダをさらに備えたことを特徴とする請求項２８に記載のＷＴＲＵ。
【発明の詳細な説明】
【背景技術】
【０００１】
本発明は、無線通信のセキュリティの分野に関する。詳細には、本発明は、無線チャネルの相互性に基づく秘密鍵の生成に関する。
【０００２】
従来の暗号化技法の多くは、無線通信に適用可能であるが、これらの技法は、正当な当事者が、盗聴者が鍵を入手する数学的不可能性ではなく、その計算の困難さに依拠するという問題がある。盗聴者が利用可能な計算能力が増大するに従って、このような方法の有効性が低下する。更に、このような方法では、ある特定の推量が正しいかどうかを確認することが、たいてい簡単であるという問題がある。したがって、計算量的仮定に基づくのではなく絶対的（無条件の）秘密性を提供する暗号化技法を構築することが有利である。それを行うための１つの方法が、Ｍａｕｒｅｒ、Ｃｓｉｓｚａｒ、Ａｈｌｓｗｅｄｅらの研究に基づく先行技術文献でよく知られている。この手法の簡単な説明を以下で述べる。
【０００３】
２人の当事者であるアリスとボブは、２つのランダム源ＸおよびＹにアクセスすることができ、ＸおよびＹは、ｉで示す所定の時間に、独立したサンプルＸiおよびＹi生成すると仮定する。アリスとボブは、盗聴者のイブがアクセスできる公開チャネルを介して通信することにより、「完全に秘密」の鍵を生成しようとすると仮定する。更に、イブは、独立サンプルＺiを生成する別のランダム源Ｚにアクセスすることもできる。ランダム源Ｚは、ランダム源ＸおよびＹにおそらく依存するが、ＸとＹが互いに相互依存するほどには強く依存しない。したがって、直観的には、アリスとボブは、彼らのランダム源のより強い相互依存により、イブに対する何らかの優位性を共有する。実際、アリスとボブは、この依存性を利用して、「完全に秘密」のランダム鍵を生成できることが示されている。
【０００４】
鍵は、ビットシーケンス（ｂｉｔ  ｓｅｑｕｅｎｃｅ）として一般性を失うことなく定義することができる。長さＮビットの完全に秘密のランダム鍵は、アリスとボブに共有されるＮビットシーケンスＳであり、この鍵シーケンスについての他者（この事例ではイブのみ）による推定値は、２N個の全ての可能なＮビットシーケンスにわたって、おおむね等確率で分布しうることになる。
【０００５】
Ｖは、公開チャネルを介して行われるすべての通信を示し、ｎは、３者それぞれがそれぞれアクセスするランダム源の出力を蓄積する時間インスタンスの数を示し、｜Ｓ｜は、結果の鍵の長さを示すものとする。そして、任意のε＞０において、充分に大きなｎについて以下の関係が成り立つようにプロトコルを捜し求める。
【０００６】
【数１】
2011217415.tif 000003
【０００７】
式１の中で、Ｈは、情報理論に関する先行技術文献で周知の確率変数のエントロピである。式１は、鍵生成のための基本リソースであるため、ランダム源のシングルサンプリング（ｓｉｎｇｌｅ  ｓａｍｐｌｉｎｇ）に正規化されることに留意されたい。
【０００８】
数量
【０００９】
【数２】
2011217415.tif 000004
は、式１により、［｜Ｓ｜／ｎ］と同等に考えることができ、秘密鍵レート（ｓｅｃｒｅｔ  ｋｅｙ  ｒａｔｅ）と呼ばれる。以下では、秘密鍵の長さの概念と秘密鍵レートとは、文脈により適切ならば交換可能である。つまり、特定の秘密鍵の長さに言及するとき、これは、基礎となる確率変数のある特定の数量（ｎ）の観測値に基づいて導出されることを理解されたい。一方、秘密鍵レートが言及される場合、その概念は、確率変数の観測値ごとの秘密鍵ビットの平均数の１つである。
【００１０】
上記の秘密性の定義と、すべての公開鍵システムを含む最近の暗号システムの依拠するそれとは決定的な違いがあることに注目すべきである。具体的には、現代の暗号システムは、暗号鍵を推量で当てることが計算の複雑さの観点から極めて困難であることに依拠している。しかし、これらのシステムの多くでは、いったん正しい推量がもたらされると、それが実際に正しい推量であることを確認することが極めて容易である。実際、ＭａｕｒｅｒおよびＷｏｌｆの研究は、このことが、任意の公開鍵システム、すなわち暗号化鍵が公開される一方で復号鍵が秘密にされるシステムでは避けられないことを示唆している。要点を示すために、公開鍵暗号システムが基づく以下の単純な例を考えるが、最も実用的なシステムは、よりはるかに洗練されていることに留意されたい。
【００１１】
ｐおよびｑは、２つの大きな素数であり、ｓ＝ｐｑとする。２つの大きな素数の積を因数分解する問題は、計算量的に困難であることが知られている。したがって、公開鍵暗号システムでは、通信先にｐおよびｑを秘密裏に選択させその積ｓを公的に利用可能にし、この積を、ある暗号化システムのための暗号化鍵として用いるようにし、この暗号化鍵は、ｐおよびｑが知られない限り容易に復号することができないことが想定できる。暗号化されたメッセージを傍受しようとする盗聴者は、ｓを因数分解しようとする試みから始めるであろうが、これは、計算論的に困難であることが知られている。おそらく、盗聴者が断念することになるか、多くの時間が経過してそのメッセージの秘密はもはや検討課題ではないことになる。しかし、盗聴者が、ｐを推量する場合、それが正しい答えであることを確認することは極めて容易であることに留意されたい。正しい答えが最終的に推量されるとすぐに分かるこの能力により、計算量的な秘密性は、「完全な秘密性」とは別のものにされる。完全な秘密性とは、盗聴者は、鍵が正しく推量したとしても、それが実際に正しく推量されたかを決定する能力を盗聴者が持たないことを意味する。したがって、非常に特殊な意味において、「完全な秘密性」は、現代の暗号システムにおける一般的な概念よりも強い秘密性の概念である。
【００１２】
私達のシナリオにおけるこのようなプロトコル生成完全秘密性が存在することは、自明ではない。とはいえ、その存在、または多くの異なるプロトコルの存在が、ＡｈｌｓｗｅｄｅおよびＣｓｉｓｚａｒ、ＣｓｉｓｚａｒおよびＮａｒａｙａｎ、ならびにＭａｕｒｅｒおよびＷｏｌｆの研究で確立されている。また、これらの先行研究は、幅広い仮定の下で、ランダム源のシングルサンプリングにつき生成されうるランダムビット数に対して様々な上限および下限を与える。
【００１３】
完全に秘密の鍵を生成するためのプロセスは、以下のように概説することができる。アリスとボブは、まず、彼らの共同のランダム性を利用して、イブの視点からの固有エントロピが｜Ｓ｜ビット（ただし｜Ｓ｜＜｜Ｓ’｜）であるビット列シーケンスＳ’を確立することから始める。これは、アリスとボブの間の公開の交換を何回か用いて行われる。多くの事例では、単一の単方向の交換で充分である。この交換の厳密な性質は、共同ランダム源（Ｘ，Ｙ，Ｚ）の性質に依存する。このステップは、通常、情報照合調整（ｉｎｆｏｒｍａｔｉｏｎ  ｒｅｃｏｎｃｉｌｉａｔｉｏｎ）と呼ばれる。
【００１４】
次いで、アリスとボブは、通常は単一の交換で充分であるが、場合によっては別のセットの公開交換を用いて、シーケンスＳ’を完全に秘密の列Ｓに変換する機能について公的に取り決める。これは、一般に、プライバシ増幅（ｐｒｉｖａｃｙ  ａｍｐｌｉｆｉｃａｔｉｏｎ）と呼ばれる。あるいは、この機能は、システム設計時に予め取り決められてもよい。この場合、イブは、これを知っていることが想定される。
【００１５】
アドバンテージディスティレーション（ａｄｖａｎｔａｇｅ  ｄｉｓｔｉｌｌａｔｉｏｎ）と呼ばれる、上述の最初のステップの前に行われる追加のステップが、更に用いられることがあるが、それは、ここでは関係がないためこれ以上説明しない。
【００１６】
このプロセスは、無線通信システムに特定して適用されるとき、更に詳細を要する。相関性があるランダム源を事前の通信なしに生成するのは先天的に難しいが、無線チャネルは、ちょうどそのようなリソースをチャネルインパルス（ｃｈａｎｎｅｌ  ｉｍｐｕｌｓｅ）応答の形態で提供する。具体的には、いくつかの通信システムにおいて、アリスからボブ、ならびにボブからアリスに通信するとき、２人の通信当事者（アリスおよびボブ）が、非常に類似したチャネルインパルス応答を測定する（例えば、広帯域符号分割多重接続（ＷＣＤＭＡ）時分割複信（ＴＤＤ）システムがこの性質を有する）。一方、アリスおよびボブと同じ位置に物理的に配置されていない任意の当事者は、アリスおよびボブのチャネルインパルス応答（ＣＩＲ）とほとんど相関を有しないＣＩＲを測定することが見込まれる。この違いを、完全に秘密の鍵を生成するために利用することができる。また、ＣＩＲ測定ごとのいくらかのビット数の完全に秘密のビットを生成することが重要である。ＣＩＲ測定は、事実上独立であるように、かなり広い時間間隔を空ける必要があることに留意されたい。
【発明の概要】
【発明が解決しようとする課題】
【００１７】
したがって、暗号化において当てはまる最悪の場合の想定の下で、盗聴者が、２つの無線端末間で交換される任意のビットを傍受することができ、２つの端末間で秘密鍵を導出するために使用されるアルゴリズムを知っているという難題に直面しながら、相互的無線チャネルから秘密ビット列を明示的に抽出するシステムを設計する必要がある。
【００１８】
更に他の課題は、各対のみが先天的に固有のチャネル特性を共有しながら、トランシーバのネットワーク全体が共通の完全に秘密の鍵を共有するように、完全に秘密の鍵の生成を２つのトランシーバ端末から複数のトランシーバに拡張することが望まれることがあることである。つまり、トランシーバの各対は、共通のランダム鍵を生成するが、これらの鍵は、対ごとに異なる。これにより、同じ情報が２つ以上の受信者にブロードキャストされる場合、かかるネットワークにおける情報の共有がかなり非効率になる。なぜならば、メッセージは受信者ごとに異なる鍵で暗号化されて、したがって異なるメッセージとして見え、そのため各受信者に別々に伝達されなければならないからである。これに対して、共有鍵で暗号化されたメッセージは、一度にマルチキャストされ、すべての正当な受信者が、単一の送信を暗号化することが可能である。
【課題を解決するための手段】
【００１９】
本発明は、無線通信ネットワークにおける複数の端末間の完全なランダム秘密鍵を生成し、確信を持って使用される鍵を盗聴者が導出するまたは推量で当てることを数学的に不可能なようにするための、方法およびシステムである。本発明は、ポイントツーポイント無線チャネルにおいて固有の独自のランダム性を利用する。盗聴者は、正しい鍵を推量する可能性があるが、それを間違った鍵と見分けることができない。
【００２０】
１対のトランシーバ（送受信機）間で、主導トランシーバが共有チャネルのＣＩＲ推定値を導出し、次いで、この推定値は、長い秘密鍵を作成するために離散的に処理される。エラー訂正符号が生成され、パリティビットが第２のトランシーバに送信される。第２のトランシーバで同期されたＣＩＲ推定を保証するために、任意選択の同期ビット列も生成され第２のトランシーバに送信される。第２のトランシーバは、独立してそれの共有チャネルのＣＩＲ推定値を導出し、主導トランシーバから送られた受信パリティビットおよび同期符号により、そのＣＩＲ推定値を処理する。この結果は、パリティビットを除いて鍵を公的に共有することなく、主導トランシーバで導出されたものと同一の長い秘密鍵となる。交換されたパリティビットによって失われた相関性および秘密性を除去するために、各トランシーバは、プライバシ増幅処理によってそれぞれの長い秘密鍵を更に処理する。
【００２１】
この完全に秘密の鍵を確立するための技術は、３つ以上のトランシーバのための汎用のネットワーク設定にも単一の完全に秘密の鍵を共有するように拡張される。
【００２２】
本発明のより詳細な理解は、例として与えられ添付の図面と併せて理解される以下の好ましい実施形態の説明から得ることができる。        
【発明の効果】
【００２３】
以上説明したように、本発明によって、無線通信ネットワークにおける複数の端末間の完全なランダム秘密鍵を生成し、確信を持って使用される鍵を盗聴者が導出するまたは推量で当てることを数学的に不可能なようにする方法およびシステムが実現できる。
【図面の簡単な説明】
【００２４】
【図１】図１は、主導トランシーバであるトランシーバＡにおける秘密処理を示すブロック図である。
【図２】図２は、トランシーバＢにおける秘密処理を示すブロック図である。
【図３】図３は、時間遅延領域における同期問題の例を示す図である。
【図４】図４は、畳込み符号を使用した差分ベクトル符号化を示す図である。
【図５】図５は、３ノードネットワークを示す図および４ノードネットワークを示す図である。
【発明を実施するための形態】
【００２５】
本発明の特徴および要素は、特定の組み合わせとしての好ましい実施形態で説明されるが、各特徴または要素は、（好ましい実施形態の他の特徴および要素なしに）単独で、あるいは本発明の他の特徴および要素の有無を問わず様々な組み合わせで使用することができる。
【００２６】
以下では、トランシーバ（送受信機）は、無線送受信ユニット（ＷＴＲＵ）、ネットワークノード、ユーザ機器、移動局、固定または移動加入者ユニット、ページャ（ｐａｇｅｒ）、あるいは、無線環境において動作可能な任意の他のタイプの装置を含むが、それだけに限定されない。基地局は、以下で言及されるとき、ノードＢ、サイトコントローラ（ｓｉｔｅ  ｃｏｎｔｒｏｌｌｅｒ）、アクセスポイント、または、無線環境における任意の他のタイプのインターフェース装置を含むが、それだけに限定されない。
【００２７】
図１および図２はそれぞれ、トランシーバ１００および２００のブロック図であり、ポイントツーポイントシステムで通信している正当な２当事者を表している。本発明は、２つのトランシーバ１００と２００の間で完全に秘密の鍵を確立し、ここではトランシーバ１００が主導トランシーバとして選択される（すなわち、トランシーバ１００は、鍵確立プロセスを先導する）。トランシーバ１００および２００は、好ましくは、より大きな通信システムのサブコンポーネント、および／または特定用途向け集積回路（ＡＳＩＣ）であることに留意されたい。図１および２に示す処理要素の一部または全部は、秘密性と関係ない他のタスクのために共用されうる。
【００２８】
一般的に、トランシーバ１００および２００は、暗号化された通信のための完全な秘密を生成するための以下の初期手順のステップをたどる。
【００２９】
１）  各トランシーバは、相互に、特別設計の信号（例えば、トーンのコーム（ｃｏｍｂ  ｏｆ  ｔｏｎｅｓ））、または他の用途にも用いることができるパイロットシーケンスを互いに送信する。
【００３０】
２）  無線物理チャネルは、いくらか物理環境に従ってシーケンスを自然に修正し、信号フェージングおよび歪みを作り出すが、チャネル相互性のためこれらの修正は非常に類似している。したがって、トランシーバ１００および２００は、それらの共有チャネルに固有の共同ランダム性を利用して、秘密鍵を確立する。
【００３１】
３）  次いで、各トランシーバは、その受信信号を、ある様式のバイナリ（または他のある種の離散形式）シーケンスに変換する。
【００３２】
図１に示すように、主導トランシーバ１００は、チャネル推定器１０１、チャネルインパルス応答（ＣＩＲ）ポストプロセッサ１０２、プライバシ増幅（ＰＡ）プロセッサ１０３、ブロック符号エンコーダ（ｂｌｏｃｋ  ｃｏｄｅ  ｅｎｃｏｄｅｒ）１０４、任意選択の同期符号ユニット１０５、パリティビットおよび同期ビットマルチプレクサ（ＭＵＸ）１０６、ならびに、任意選択の弱鍵解析プロセッサ１１２を含む。
【００３３】
トランシーバ１００では、チャネル推定器１０１が、トランシーバ２００からの受信無線信号からチャネルインパルス応答（ＣＩＲ）を推定し、次いでそれはＣＩＲポストプロセッサ１０２によって処理される。ＣＩＲポストプロセッサの主なタスクは、推定されたＣＩＲを、以下で長い秘密鍵１１０として知られるビット列に変換することである。トランシーバ１００は、情報照合調整プロセスの完了の際に、トランシーバ２００が、長い秘密鍵２１０として示される同じビット列を保有していることを想定する。この長い秘密鍵１１０および２１０は、以下の２つの理由により完全に秘密ではない。１）ＣＩＲサンプルは潜在的に相関する（高いサンプリングレートでは高く相関する）ため、ビットは独立して分布しない、２）プロトコルの一定の部分は公開通信を必要としたため、情報の一部が潜在的な盗聴者に漏れている。プライバシ増幅（ＰＡ）プロセッサ（１０３）は、これらの問題を補正する。
【００３４】
情報照合調整プロセスの一部として、ブロック符号エンコーダ１０４が、トランシーバ２００でのエラー訂正のためのパリティビットを有するブロック符号を導出する。少なくとも１つの好ましい実施形態では、同期符号エンコーダ１０５が、トランシーバ１００と２００の間のＣＩＲ推定を同期するために使用される符号を作成する。パリティビットおよび同期符号ビットは、トランシーバ２００に送信するためにＭＵＸ１０６によって多重化される。
【００３５】
任意選択の弱鍵解析プロセッサ１１２は、長い秘密鍵１１０が脆弱な長い秘密鍵であると決定された場合に、それを検出し排除する。
【００３６】
図２に示されるように、トランシーバ２００は、チャネル推定器２０１、ＣＩＲポストプロセッサ２０２、プライバシ増幅プロセッサ２０３、同期ビットデコーダ２０４、パリティビットデコーダ２０９、同期アップ（ｓｙｎｃｈ−ｕｐ）ＣＩＲユニット２０５、および、弱鍵解析プロセッサ２１２を含む。
【００３７】
トランシーバ２００において、チャネル推定器２０１が、トランシーバ１００から無線信号を受け取り、ＣＩＲを推定する。ＣＩＲポストプロセッサ２０２は、ＣＩＲ推定値をフィルタリングする。これら２つのユニットは、トランシーバ１００の対応するデバイス１０１および１０２と同様に動作する。ＣＩＲポストプロセッサ２０２の出力は、「ランダム秘密鍵」ビット列である。理想的には、この列は、２つのトランシーバ間に存在するチャネル相互性に基づきトランシーバ１００上の長い秘密鍵と同一である。しかし、実際のＣＩＲ推定値は、ＣＩＲ歪み、チャネルノイズ、および異なるチャネル推定開始点のため同一ではなく、２つの列は、実際いくぶん異なる。
【００３８】
ＣＩＲポストプロセッサ２０２の実際の出力が、ＣＩＲポストプロセッサ１０２のそれと同じであった場合、ＰＡプロセッサ２０３によるプライバシ増幅、および任意選択の弱鍵解析を、トランシーバ１００におけるのと同じ完全に秘密の鍵を生成するために適用することができる。ＰＡプロセッサ２０３の性質は、ＰＡプロセッサ１０３の性質と同じであり、ＷＫＡプロセッサ２１２は、ＷＫＡプロセッサ１１２と同じである。しかし、ＣＩＲポストプロセッサ２０２の出力は、ＣＩＲポストプロセッサ１０２の出力と同じではないので、ＰＡ処理およびＷＫＡ処理を、直接それに適用することができない。そのかわり、トランシーバ２００は、トランシーバ１００によって送信されたパリティおよび同期ビットを使用してその差を修正する。
【００３９】
同期符号エンコーダ１０５が実装された実施形態において、同期ビットデコーダ２０５およびパリティビットデコーダ２０４が、受信信号から同期ビットおよびパリティビットを復号する。ＣＩＲ同期アップユニット２０７は、復号された同期ビットを処理し、ＣＩＲ推定をトランシーバ１００のＣＩＲ推定と同期する。パリティビットデコーダ２０４は、復号されたパリティビットを処理し、同期されたＣＩＲ推定値に対してエラー訂正を実施する。これで、長い秘密鍵２１０はトランシーバ１００で存在しているように回復され、ＰＡおよびＷＫＡ処理が適用可能である。トランシーバ１００からの受信無線信号内に埋め込まれた長い秘密鍵２１０は、完全に秘密の鍵を提供するためにＰＡプロセッサ２０３により処理される。任意選択の弱鍵解析プロセッサ２１２は、脆弱な長い秘密鍵を検出し排除する。
【００４０】
チャネル推定値からの完全に秘密の鍵の生成についての説明は、次の通りである。トランシーバ１００および２００の両方は、チャネル推定ユニット１０１および２０１における受信無線信号に基づいてＣＩＲの推定値を導出する。両方のトランシーバは、この動作を、ある種の無線信号の送信によってサポートしなければならない。これは、通常、秘密鍵生成以外の目的の、チャネル推定に使用される特別に設計されたパイロット信号である。たいていの最近のシステムは、それをデータ推定の目的で組み込む。このステップを実施するためのいくつかの方法があり、その方法には、他方のトランシーバにおいてこのプロセスを支援するための、両方のトランシーバによる特殊な信号の伝達が含まれるが、これだけに限らない。かかる信号伝達の実装は、時分割複信（ＴＤＤ）で使用されるようなミッドアンブル（ｍｉｄａｍｂｌｅ）、ＩＳ−９５およびＦＤＤシステムにおけるような連続パイロット、多くのＯＦＤＭシステムにおけるような特定の周波数での組込みパイロットを使用することを含むことができる。
【００４１】
チャネル推定ユニット１０１および２０１の出力は、ＣＩＲのデジタル化された表現である。ＣＩＲ推定値は、トランシーバ１００および２００の両方における表現技法が同じである限り、時間領域、周波数領域、および抽象ベクトル空間の使用を含め多くの様々な方法で生成し格納することができる。好ましい実施形態では、ＣＩＲ推定器１０１および２０１の出力でのＣＩＲ推定値が、ＣＩＲ位相情報を無視する一方で、秘密鍵の生成のための振幅／プロファイル出力を提供する。あるいは、チャネル推定値のチャネルＣＩＲ位相情報も、このプロセスで使用してもよい。実装形態によっては、ＣＩＲについての部分情報のみが、相反的であり、したがって共通の秘密の生成のために適していることがある。
【００４２】
デジタル信号からＣＩＲを生成する際の一般的問題は、Ａ／Ｄ変換器のサンプリング位相の差が、大幅に異なって見えるＣＩＲ推定値をもたらすおそれがあることである。これは、ＣＩＲが時間領域で格納される場合、特に問題である。ＣＩＲが周波数領域で格納される場合は、深刻な問題ではない。他の代替格納方法でこれが問題となる程度は、様々である。この問題に対処する単純な方法は、送信帯域幅を考慮した最小レート（すなわち、ナイキストレート（Ｎｙｑｕｉｓｔ  ｒａｔｅ））よりも有意に高いレートでアンテナにおいてアナログ信号をサンプリングすることである。ナイキストレートの４から１０倍のレートで、既に有意に高いと考えられる。
【００４３】
ＣＩＲポストプロセッサ１０２および２０２は、結果のＣＩＲ推定値に対して、ローパスフィルタと場合によっては補間フィルタを用いて後処理を行う。トランシーバがＭＩＭＯを備えられ、アンテナの数の差異のためアンテナパターンがＣＩＲ推定値に差異を生じさせることがある場合に、追加の後処理が必要とされることがある。このような場合、トランシーバ１００および２００が、それらのアンテナ構成に関する情報を交換することを必要とすることがあり、それによって、トランシーバ１００および２００は、それらの観測値から対称的なＣＩＲ推定値を導出することを可能にされる。
【００４４】
トランシーバ１００と２００の間のチャネル相互性のため、トランシーバで生成される各後処理ＣＩＲ推定値は、非常に近くなることが期待される。しかし、以下の３つの誤差源のいずれかによって、トランシーバ１００および２００においてＣＩＲ推定値間の差がもたらされることがある。
【００４５】
第１の誤差源は、トランシーバ１００および２００の双方において同時発生のチャネル推定を仮定するチャネル相互性に由来する。この同時性での差異が、チャネル推定値でいくらかの差異をもたらす。
【００４６】
第２の誤差源は、デジタル化されたＣＩＲ推定値が、開始点について同期が必要なことがあることである。例えば、推定値が時間遅延領域でデジタル化される場合、ＣＩＲの有意な部分の開始は、２つのトランシーバ１００および２００における基準ゼロ時（ｒｅｆｅｒｅｎｃｅ  ｚｅｒｏ−ｔｉｍｅ）に対して異なる位置で発生することがある。図３に示すように、トランシーバ１００は、基準ゼロ時から時間遅延τ1を有する開始点を有し、トランシーバ２００は、基準ゼロ時から時間遅延τ2を有する開始点を有し、ここで、τ1≠τ2である。他の例として、ＣＩＲが周波数領域表現を用いて格納される場合、格納パラメータを決定する際に、異なる開始周波数／基準位相が仮定されることがある。
【００４７】
第３の誤差源は、ＣＩＲ推定値が、任意の無線チャネルに固有の干渉によって生じる誤差に起因して異なるようになることである。この干渉は、同じ周波数帯、および／または受信ノイズ、および／または熱雑音などの環境雑音で動作する、他のデバイスに起因しうる。
【００４８】
トランシーバ１００および２００でのチャネル推定の同時性の保証は、たいていの通信システムに現在存在しているいくつかの手段を用いることによって達成することができる。そのような１つの手段は、チャネル推定タイミングを、無線フレームやスロット境界、およびＵＭＴＳシステムにおけるスーパーフレームカウンタ（ｓｕｐｅｒ  ｆｒａｍｅ  ｃｏｕｎｔｅｒ）のような、特定のシステム時間と結び付けることである。もう１つの手段は、チャネル推定をサポートするためにトランシーバが発するパケット信号に同期信号を埋め込むことによる。あるいは、同期イベントが、特別の信号を埋め込む必要なくそのようなパケット信号から導出されてもよい。同時性を保証するための第３の手段は、両方のトランシーバが利用する絶対時間基準に、チャネル推定イベントを結び付けることによるものであり、絶対時間基準には、グローバルポジショニングシステム（ＧＰＳ）衛星や、無線通信システムに使用される共通システム時間が含まれる。同時性を保証するための４つの可能な手段は、所定の技法を用いて往復の遅延を測定して、同期をこの遅延に基づかせる。
【００４９】
このような手段を用いた後も、小さな同期差が依然として存在しうるが、これらがシステム性能に有意な影響を与えるほど大きくないことはほぼ確実である。残っているどんな小さな剰余数の不一致も、ブロック符号やＣＲＣ符号のような無線チャネルでの干渉による不一致を解決する同じメカニズムによって対処することができ、これについては後で説明する。
【００５０】
格納されたＣＩＲについての開始点同期（ｓｔａｒｔｉｎｇ  ｐｏｉｎｔ  ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ）は、トランシーバ１００において開始点を記録することによって処理し、誤りのない送信を保証するために高信頼性の符号を使用してトランシーバ２００に送信することができる。あるいは、そのような符号のいくつかの周知のファミリ（ｆａｍｉｌｙ）（例えば、コンマフリー符号）から特殊な同期符号を使用してもよい。同期問題は、通常、単にいくつかのサンプルに限られるので、そのような特殊な同期符号からはごく限られた性能が必要とされるだけである。同期符号エンコーダ１０５は同期ビットデコーダ２０５およびＣＩＲ同期アップユニット２０７と協働して、格納されたＣＩＲに対する開始点同期のためのこれらの解決策を実施する。デコーダ２０５が、同期ビットが別の符号を使用して送られると同期ビットを復号する一方、ＣＩＲ同期アップユニット２０７が、同期ビットに従って局所基準に対してＣＩＲの位置を調節する。あるいは、干渉誤りを訂正するために使用されるブロック符号を、後述するように上記の２つの方法と併せてもしくはそれだけで用いてもよい。更に別の代替案は、この開始点同期問題に敏感ではないＣＩＲ後処理方法を用いることである。
【００５１】
開始点同期はまた、タイミング情報の符号化に頼ることなく取り扱うこともできる。そのような１つの方法では、トランシーバ１００および２００が、共通のタイミング源（例えば、ＧＰＳ）に関係する特殊な同期信号を生成するようにし、こうした信号を基準にしてＣＩＲ推定を行うことができる。あるいは、開始点同期は、それが問題とならない領域でＣＩＲを処理することによって達成することができる。しかし、このような手法は、いくらか秘密性の度合いを犠牲にする必要がある。例えば、ＣＩＲ位相情報が好ましい実施形態に従って無視されるとすると、同期問題は周波数領域に存在しない。チャネルの干渉レベルに応じて、秘密性の度合いの損失は、大きくも最小にもなりうる。別の例として、非常に雑音のあるチャネルでは、位相情報は、極めて信頼性できないおそれがあり、したがって、それを無視することにより、秘密性の度合いの損失が最小限となる。
【００５２】
送信された列と受信された列との不一致がチャネル干渉により生じるところで、ブロック符号エンコーダ１０４は、パリティビットの形態でシステマティックエラー訂正符号を提供し、これはパリティビットデコーダ２０４でトランシーバ２００によって復号される。システマティックエラー訂正符号は、デコーダ２０４の出力の符号語が、エンコーダ１０４の入力の元のメッセージを含むものである。ここでは、システマティックエラー訂正符号は、主導トランシーバ１００の送信機にあるエンコーダ１０４、およびトランシーバ２００の受信機に位置するパリティビットデコーダ２０４によって実装される。通常、ブロック符号は、システム設計者によって予め選択される。あるいは、ある種のリアルタイム基準に基づいて動的に選択されてもよく、この選択は、トランシーバ１００と２００の間で公的に伝達される。プライバシ増幅が使用されるため、ブロック符号が公的に知られていることは、秘密性を生成するシステムの能力を低減させない。
【００５３】
ブロック符号エンコーダ１０４は、入力ビットを受け取り１組のパリティチェックビットを生成し、これらのパリティチェックビットは、入力ビットなしに送信されることになる。次いでパリティビットデコーダ２０４は、チャネルから受け取ったパリティビットをＣＩＲポストプロセッサ２０２の出力と組み合わせて、完全な「破壊された符号語（ｃｏｒｒｕｐｔｅｄ  ｃｏｄｅｗｏｒｄ）」を作成し、長い秘密鍵２１０を復号する。パリティビットの処理は、トランシーバ１００において存在する長い秘密鍵１１０と同じになるように、訂正されるＣＩＲポストプロセッサ２０２の出力をもたらす復号動作を完了する。
【００５４】
本発明によれば、ブロック符号は、従来とは異なる様式で利用される。トランシーバ１００におけるＣＩＲ推定値は、ブロック符号に対する入力として使用されるが、エンコーダ１０４によって生成されたパリティビットのみが送信される。トランシーバ２００は、この送信を場合によってはいくつかのエラーとともに受け取ると、それ自体のＣＩＲ推定値を、エラーをやはり含みうる符号語のメッセージ部分として取り扱い、受信したパリティチェックビットを使用してこれらのエラーを訂正する。ブロック符号が適切に選ばれたとすると、パリティビットデコーダ２０４の出力は、非常に高い確率でトランシーバ１００のＣＩＲ推定値と同じである。したがって、トランシーバ１００および２００は、同じ列を得ることに成功するが、その間、その一部のみ、すなわちパリティチェックビットの送信しか公的に明らかにしない。
【００５５】
ブロック符号を選択する際、潜在的な盗聴者が、どんなブロック符号が使用されるかを発見する能力を有し、したがってこの秘密を維持しようとする試みがないことが想定される。ブロック符号の性質は、そのエラー訂正機能および符号化／複合化の複雑さが、設計配慮として検討される限りにおいて重要なだけである。リードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）およびターボ（ｔｕｒｂｏ）符号を含めて任意のシステマティックブロックエラー訂正符号を使用することができる。ほとんどのシステムでＣＩＲの長さに合理的な上限が置かれているため、ブロック符号サイズは、予め定められるのが好ましい。しかし、これをすることができないと、公開ディスカッション（ｐｕｂｌｉｃ  ｄｉｓｃｕｓｓｉｏｎ）を用いて、予め取り決められたファミリの符号から特定の符号が選択される。あるいは、ブロック符号のファミリ、例えば、可変のエラー訂正機能を有するファミリが選択される。次いで、トランシーバ１００、２００は、ブロック符号ファミリから、チャネル条件（干渉レベル、ドップラー幅、他）に基づいて、どの符号を使用するかを選択する。ブロック符号に関する取り決めは、公開通信を介して確立される。秘密性を保証するために、選択されたブロック符号を秘密にする必要がないため、これは、システムを危うくしない。
【００５６】
結果の列に保たれている秘密性は、ＣＩＲ推定値の初期のエントロピーにおおよそ等しく、使用されるパリティビット数が少ないほど、ＣＩＲ推定値について潜在的盗聴者が有する可能性がある情報が少ない。ＣＩＲ推定値に関する盗聴者の知識が少ないと仮定すると、最大限の秘密性のために、できる限り少ないパリティビットを使用することが望ましい。他方で、許容できる確率閾値が予め決められていて、トランシーバ２００が、非常に高い確率で、デジタル化されたシーケンスがトランシーバ１００におけるシーケンスと厳密に同じになるように帰結することを保証するには、充分な数のパリティビットが必要とされる。したがって、このトレードオフにおいて適正なバランスを維持するために、特定のチャネル条件を充たすように符号のファミリからブロック符号を選択する能力が実装されうる。この意思決定メカニズムは、ブロック符号エンコーダ１０４に対する任意選択のアドオン機能である。
【００５７】
先に紹介したように、ブロック符号は、デジタル化されたＣＩＲの開始点の同期をサポートするためにも使用することができる。同期アップメカニズムが使用されないためか、またはそれが不確実性を完全に低減しないため、トランシーバ２００が正確な開始点について確実でない場合、それは、不確実性を、限定された通常は小さい一連の可能性に絞り込む。次いで、トランシーバ２００は、受信されたパリティビットを使用して、可能な開始点のそれぞれを用いて復号を試みる。そうする際、それは、ＣＩＲエラー訂正器２０６によって訂正されるそれ自体のＣＩＲ推定値における「エラー」の数をカウントする必要がある。非常に高い確率で、正しいものを除くすべての位置は、非常に多数の訂正を生じ、一方、正しい位置は、非常に少数の訂正を生じる。このようにして、ブロック符号復号プロセスは、開始点同期プロセスを支援するまたは完全にサポートすることができる。
【００５８】
良いエラー訂正符号の利用により、同じ鍵が両方の端末で生成される高い可能性がもたらされるが、このプロセスは成功を保証されない。この手順が失敗する場合、端末は、２つの異なる秘密列をもって終結する。これらが１ビットのみ異なったとしても、もはや通信は可能ではない。この問題は、いくつかの方法のいずれかで軽減されうる。端末が、復号されたメッセージが正しくないことを検出する方法を有する場合、鍵の取り決めの失敗を、まさにそうした方法で検出することができる。しかし、このような検出プロセスは、通信リソースの浪費という意味で、しばしば実現不可能であるかまたはコストが高すぎる。この場合、エラー検出符号化を利用する代替方法が適用されうる。
【００５９】
エラー検出符号化の一般的なタイプは、ＣＲＣ符号化であり、以下の例でエラー検出符号化の好ましい選択肢として説明する。ＣＲＣプロセッサ１０８は、ある予め選択されたＣＲＣ符号に基づいて、長い秘密鍵に対するＣＲＣチェックビットを計算する。ＣＲＣビットを有する結果の列は、次いでトランシーバ２００に転送される。
【００６０】
次いで、トランシーバ２００は、ちょうど上述のようなブロック復号化を進める。復号化に続いて、ＣＲＣプロセッサ２０８は、同じＣＲＣ符号を用いてそれ自体のＣＲＣビットを計算し、それらをトランシーバ１００から受け取ったビットと比較する。結果のエラー訂正された列がＣＲＣチェックをパスすると、成功が宣言される。そうでなければ、トランシーバ２００は鍵生成の失敗を宣言し、鍵生成プロセスが反復されることになる。
【００６１】
最後に、チャネル条件が良くしたがってＣＩＲが同一である可能性が高い場合、トランシーバ２００におけるパリティビットデコーダ２０４でエラーが検出されないことを単に確認することにより、エラーチェックのためにブロック符号を代わりに使用することができる。
【００６２】
非システマティックエラー符号が利用される代替実施形態として、次の例では、シンドローム（ｓｙｎｄｒｏｍｅ）の実装を示す。アリスおよびボブは、２つの相関性があるバイナリ独立で全く同様に分布したシーケンスＸn（Ｘ1，…，Ｘn）およびＹn（Ｙ1，…，Ｙn）をそれぞれ知っていると仮定する。アリスは、Ｘnの情報をボブに送信することによってボブがＸnを回復するのを助ける。相関性があるシーケンスＹnによって、ボブはＸnの一部の情報を既に知っているため、アリスは、Ｘnのすべてをボブに送信する必要はないことに留意されたい。スレピアン−ウォルフ限界（Ｓｌｅｐｉａｎ−Ｗｏｌｆ  ｂｏｕｎｄ）として知られる１つの既知の解決策は、ボブがＸnを再構成することを可能にするアリスからボブへの送信ビットの最小数が、ｎＨ（Ｘ｜Ｙ）（ただし、Ｈ（Ｘ｜Ｙ）は条件付きエントロピを示す）であることを示唆する。本発明によるシンドロームを使用すると、Ｙnおよび送信されたビットに基づいて、ｎＨ（Ｘ｜Ｙ）送信ビットを決定することができ、更にＸnの再構成することができる。シンドロームベースの手法が重要となる一実施形態では、低密度パリティチェック（ＬＤＰＣ）符号がエラー訂正のために使用される場合、ＬＤＰＣ符号は通常は非システマティックである。
【００６３】
例示的な例であるが以下の単純な例を検討する。Ｘ3＝（Ｘ1，Ｘ2，Ｘ3）およびＹ3＝（Ｙ1，Ｙ2，Ｙ3）は、ハミング距離が１以下の２つの（長さｎ＝３の）バイナリシーケンスとする。アリスおよびボブはそれぞれ、Ｘ3およびＹ3を観測する。アリスは、Ｘ3の部分情報を送信することにより、ボブがＸ3を再構成するのを助ける。Ｘ3が集合｛０００，１１１｝に属することをボブが知っている場合、Ｘ3とＹ3の間のハミング距離が１以下であり「０００」と「１１１」の間のハミング距離が３であるため、彼は容易にＸ3を復号できることに留意されたい。したがって、ボブのデコーダがＸ＝１００またはＸ＝１１１であることを知っている場合、ハミング距離でどちらがより近いかを検査することによって不確実性が解決される。同様に、集合｛００１，１１０｝、｛０１０，１０１｝、および｛１００，０１１｝のいずれかにＸ3が属することを知っていることにより、これらも３のハミング距離を有するのでボブがＸ3を回復するのを助けることができる。したがって、アリスは、（上記の４つの集合のうちから）どの集合にＸ3が属するかをボブに通知するだけでよい。
【００６４】
上記の４つの集合は、それぞれの部分集合について３のハミング距離を有し、線形符号｛０００，１１１｝についての剰余類（ｃｏｓｅｔ）と呼ばれ、パリティチェック行列が、
【００６５】
【数３】
2011217415.tif 000005
である。シーケンスＸ3のシンドロームは、有効な符号語のパリティチェックを確認し、また、Ｐ（Ｘ3）tとして定義され、ｔは転置を示す。同じ剰余類におけるすべてのシーケンスは同じシンドロームを有し、それぞれ異なる剰余類の２つのシーケンスはすべて異なるシンドロームを有することが知られている。したがって、アリスは、単に、Ｘ3を含む剰余類を示す彼女の観測値Ｘ3のシンドロームを送信する。
【００６６】
次に、図１および２に示されるＰＡプロセッサ１０３、２０３を参照すると、これらは、ストリングのビットの長さが、鍵により提供される秘密の量にほぼ相当するようにストリングを縮小することを担う。これらは、汎用ハッシュ機能を用いて実装され、使用される特定の機能は、予め取り決められても公開通信を用いて取り決められてもよい。使用されるブロック符号のような機能は、秘密にする必要がなく、したがって、公開無線チャネルを用いて取り決めることができる。
【００６７】
ハッシュ関数は、次元Ｍの入力ストリングをより小さい次元Ｎ（Ｍ＞Ｎ）にする変換関数である。  
ｆ：｛０，１｝M⇒｛０，１｝N                    式（５）
ハッシュ関数は、コンピュータサイエンスにおいて辞書問題を解くために一般的に使用される。辞書問題は、所与のアイテムの集合（語、名前、オブジェクト、キー、その他）およびそれらの関連属性を、それ以降これらのアイテムが効率的に探索されるように格納するための、メカニズムの確立として定義される。ハッシュ関数は、与えられた集合の探索動作時間コストや格納および探索メカニズムの単純な実装などの属性を含む。
【００６８】
探索動作コスト時間を求めることは、入力ストリングが通常は一様分布からのものではないため、また、より大きい次元Ｍからより小さい次元Ｎへの複雑なマッピングのため、非常に難しい課題である。これらの理由から、ハッシュ関数の出力における衝突は珍しくなく、ここで、衝突とは、２つ以上の入力ストリングが同じ出力値を生成する結果である。ダブルハッシュ（ｄｏｕｂｌｅ  ｈａｓｈｉｎｇ）、プロービング（線形および２次）、連鎖など様々な方式が、これらのハッシュ関数についての探索動作コスト時間に接近するために使用される。
【００６９】
本発明のハッシュ関数は、完全な秘密を達成するのに有用な以下の特性を有する。まず、ハッシュ関数は、逆方向より順方向に計算をすることがかなり容易であるという点で、一方向な非可逆である。一般に、順方向に計算するのに数秒かかる一方、その逆を求めるのは計算量的に不可能である。すなわち、与えられたハッシュ関数ｙ＝ｈ（ｘ）について、与えられたｘの値に対するｙの値を求めることは容易であるが、与えられたｙの値に対するｘの値を求めることは計算量的に不可能である
次に、本発明によるハッシュ関数は、弱衝突耐性および強衝突耐性を有する。弱衝突耐性は、次にように定義される。メッセージｘ、およびそれの（メッセージダイジェストとも呼ばれる）ハッシュ値ｙが与えられたとすると、別のメッセージｚを、それらのハッシュ関数は等価すなわちｈ（ｘ）＝ｈ（ｚ）であるように求めることは計算量的に不可能である。ユーザは、メッセージおよびそのハッシュ値の選択の選択権を持たないが、同じハッシュ値で異なるメッセージを決定しなければならないことに留意されたい。
【００７０】
強衝突耐性は、２つの異なるメッセージｘおよびｚ（ただし、ｘ≠ｚ）を、それらのハッシュ関数は等価すなわちｈ（ｘ）＝ｈ（ｚ）であるように求めることが計算量的に不可能である場合に存在する。ユーザはこの場合にメッセージを選択することができるので、この特性は、強衝突耐性と呼ばれる。
【００７１】
これらの特性は、ほとんどの規格化されたハッシュ関数に参照される。２つの主な規格として、セキュアハッシュアルゴリズム（Ｓｅｃｕｒｅ  ｈａｓｈ  ａｌｇｏｒｉｔｈｍ）ＳＨＡファミリ、およびメッセージダイジェストアルゴリズム（ＭＤ）ファミリがある。更に、ＳＨＡファミリおよびＭＤファミリは、暗号システムの潜在的攻撃者が、それを破る計算リソースを持たない場合、計算量的に安全である。汎用ハッシュ関数は、かかる暗号システムを破るための努力が、任意の一般的難問（例えば、大きな数の因数分解、合成数を法とする整数のフィールドにおける平方根の計算、有限群上の離散対数の計算など）を解決するのと同様に難しいという意味で証明可能に安全である。
【００７２】
本発明によれば、汎用ハッシュ関数ｇ(a,b)（ｘ）は、鍵の各対ｘi，ｘj（ただし、ｘi≠ｘj）について衝突数が小さくなるように、各サイズがＭビットの鍵｛ｘ｝の領域を、各サイズがＮビットの固定されたハッシュ値にマップする（ただし、Ｎ＜Ｍ）。つまり、ｇ（ｘi）＝ｇ（ｘj）での衝突数は１／２Nに等しい。
【００７３】
ハッシュ値は、以下の式のような汎用ハッシュ関数を用いて導出される。  
ｇ(a,b)（ｘ）＝（（ａｘ＋ｂ）ｍｏｄｐ）ｍｏｄ２Ｎ          式（６）
ただし、
ｐは、ｐ≧（２M−１）の素数、
ａ＝｛１，２，…，ｐ−１｝、
ｂ＝｛０，１，…，ｐ−１｝
である。
【００７４】
ａおよびｂの選択対象の範囲を考慮すると、ｐ（ｐ−１）個の汎用ハッシュ値がある。かかる関数の集合Ｇ＝｛ｇ(a,b)（ｘ）｝は、一括してハッシュ関数の普遍クラスと呼ばれ、Ｇ（ｘi）＝Ｇ（ｘj）での衝突数は、多くても｜Ｇ｜／２Nである。
【００７５】
ハッシュ値処理の結果では、公的に交換されたビットを最終的な完全秘密鍵が含まないという点で、盗聴者によって傍受されていると想定される公的に交換されたビットが「徹底的に切り刻まれ（ｈａｓｈｅｄ  ｏｕｔ）」ている。
【００７６】
長い秘密鍵１１０、２１０が相関しない場合に、エントロピ符号器、またはバロウズ−ホイラー（Ｂｕｒｒｏｗｓ−Ｗｈｅｅｌｅｒ）変換のような優れた圧縮アルゴリズムが、ＰＡ処理と併せて使用される必要がありうることに留意されたい。いくつかの事例では、このような符号器を使用すると、よりはるかに単純な手法でも行えるように（例えば、特定の出力ビットだけを選択する）、ハッシュ関数ベースのＰＡ処理の必要性を除去することもできる。
【００７７】
最後に、いくつかの事例では、ＬＤＰＣ符号化を例としてエラー訂正に関して先に説明したように、非システマティック符号ベースの手法が使用される場合に、ハッシュ関数ベースのＰＡ処理が必要ないことに留意されたい。
【００７８】
システムの性能を更に向上するために、ＰＡステップの前または後に、弱鍵解析（ＷＫＡ）ステップを導入することができる。図１および図２に示されるように、ＷＫＡプロセッサ１１２、２１２は、ランダムに生成された完全に秘密の鍵が、何らかの外因的コンテキストの情報に従って傍受の高い確率を有するという（ありそうでなくても）可能性から、システムを保護する。このような鍵の例は、すべて１、すべて０、または定義された時間内のシーケンスのストリームを含む。システム設計により、特定の基準が選択される。
【００７９】
ＷＫＡが弱鍵を検出した場合、該当する手順が、この鍵を拒否しプロセスを反復する。ブロック符号化プロセスまたはＰＡプロセスが、使用されるべき符号／ハッシュ関数のリアルタイム通信を伴う場合、新しい符号／ハッシュ関数を選択することができ、そのプロセスは、同じＣＩＲで反復される。これは、秘密鍵レートを減少させるが、そうでなければ、端末は、新しいＣＩＲが使用可能になるまで待機する必要がある。この秘密鍵レートの減少は、報告されなければならない。
【００８０】
上記に概説した手法の主要な特徴は、ランダムシーケンスが、大きなブロックにおいて生成されることである。これらのブロックは、頻繁に更新されることができず、それは、あるブロックは、ＣＩＲが先行のブロックとほぼ完全に相関がなくなるまで待機しなければならないためである。しかし、いくつかの状況では、少数の秘密ビットのより一層の頻繁な更新が望まれる。例えば、頻繁に１つずつ出力秘密ビットを共用した「ブラックボックス」を持ちたいことがある。これを達成する１つの方法は、生成された秘密ビットのブロックを取り込み、それらを１つずつ出力することである。別の方法は、少量の秘密ビットを継続的に生成するために、上述のプロセスを修正することである。これは、次のように行うことができる。図１および２の高水準ブロック図をやはり用いる。ただし、ここでは、チャネル推定ユニット１０１、２０１は、チャネルの頻繁な推定を行い、ＣＩＲポストプロセッサ１０２、２０２は、現行の推定値と先行の推定値の間の差分ベクトルを生成する。
【００８１】
差分ベクトルは、いくつかの異なる方法で生成することができる。最も単純な方法は、単にＣＩＲの２つの連続する表現の差を取ることである。しかし、これは、通常、それを行うための最も効率的な方法ではない。より良い代替方法は、カルマン予測フィルタのような優れた予測フィルタでＣＩＲを継続的にフィルタリングし、予測された値と実際に観測された値の差を取ることを含む。これらの手法の他の変形形態も使用されうる。
【００８２】
ＣＩＲが１つの測定値から次の測定値に関連付けられる場合に差を取ることは実用的であり、したがって、差を取ることにより冗長性が除去されることにここでは留意されたい。別の手法では、相関がないことを保証するある周波数でチャネルの独立サンプルを取り、推定値に対し先入れ先出し（ＦＩＦＯ）手法を取り、次いで、ある間隔で新しい値を伝達して、鍵の継続的更新および変更を可能にする。ここでの主要目的は、所定の時間にわたり最小限の情報を送信して、新しい独立の鍵が所望の周波数で生成されるのを可能にすることである。
【００８３】
差分ベクトルは、小さいことが見込まれ、したがって、これのブロック符号化は、あまり効果的ではないはずである。しかし、差分ベクトルのシーケンスを情報ストリームとして見ることもできる。情報ストリームの符号化は、畳込み符号によって効率的に行われ、したがって、システマティック畳込み符号が、上述のシステマティックブロック符号の代わりとして提案される。
【００８４】
図４は、図１に示されたブロック符号エンコーダ１０４に代わって主導トランシーバ１００内にあるそのようなエンコーダのブロック図を示す。差分ベクトルシステム４０１は、標準畳込みエンコーダ４０２（典型的には、ＸＯＲゲートを有するシフトレジスタ）に提供され、標準畳込みエンコーダ４０２は、１つまたはいくつかのパラレルパリティストリーム（ｐａｒａｌｌｅｌ  ｐａｒｉｔｙ  ｓｔｒｅａｍ）４０３を生成する（簡単にするために１つを示す）。このようなストリームは、通常、所望の秘密性のレベルを維持するために送信されるべきビットよりもはるかに多くのビットを含む。しかし、畳込み符号のレートは、パンクチャリング（ｐｕｎｃｔｕｒｉｎｇ）によって効率的に制御されるので、パリティストリーム４０３は、送信に先立って、所望の送信レート４０４に従ってパンクチャリングプロセッサ４０５によってパンクチャリングされる。更に、適用されるパンクチャリングの量を変更することによって、トランシーバ１００は、生成されるランダム性の量に対して符号のエラー訂正能力を効率的に交換することができる。ブロック符号を使用する第１の実施形態と同様に、チャネル干渉レベルなどのチャネル条件に畳込み符号化レートを適応させることにより、最適化のレベルを提供する。
【００８５】
畳込みエラー符号化を用いたこの実施形態について続けると、システマティック入力が、局所的に生成された差分ベクトルである場合、標準畳込み符号デコーダ（例えば、ビタビデコーダ（Ｖｉｔｅｒｂｉ  ｄｅｃｏｄｅｒ））が、トランシーバ２００内のパリティビットデコーダ２０４（図２）の代わりになる。ブロック符号と同様に、符号の性質は公的に知られると想定され、したがって、符号のファミリが使用されうる。しかし、パンクチャリングまたは反復を用いて非常に効率的にエラー訂正性能と残余の秘密性とを交換することができるので、これを使用する必要はほとんどない。
【００８６】
２つのパリティ間のＣＩＲ相互性に基づき秘密鍵を生成するための必要な技法を確立したので、これをより広いネットワークに拡張することを次に検討する。先に背景技術で論じたように、問題は、基本的に以下のようである。すべての正当な当事者が同じ鍵を共有することが望ましい。しかし、トランシーバの各対は、固有のＣＩＲを共有するので、このＣＩＲに基づいて完全な秘密性の生成をサポートするのは、まさにこの特性である。トランシーバの各対は、単にそれ自体の固有のＣＩＲを利用し、そして、各対は、それ自体の鍵で終結することが見込まれる。このことは、かかるネットワーク内の共通の情報の伝送を、かなり非実用的なものにするが、それは、異なる鍵で暗号化された同じメッセージが、暗号文の統計的に独立のインスタンスを生じるためである。無線チャネルを介して独立の情報を送信することは、かなり効率が低く、そして、同じ情報を当該のチャネルでブロードキャストする。ここで、私達は、３つ以上の端末のネットワークで同じ鍵を生成するためのいくつかの方法を提案する。
【００８７】
汎用ネットワークにおいて全域木に基づく単純な方法は、以下の通りである。ネットワークノード（トランシーバ）がツリーを形成し、ツリー内でない接続のためのリンク（ＣＩＲ）は無視される。任意の実現可能な鍵の長さが、何らかの従来の通信方法によって確立され、ここで、実現可能とは、ツリー内で使用される各リンクが、少なくともこのサイズの秘密鍵を生成するために使用可能であることを意味する。
【００８８】
接続されたノードの各対は、トランシーバ１００および２００について上述した様式で、それ自体のＣＩＲに基づいて一時鍵を確立する。これが行われると、ツリーのルートのノードが、それが永久鍵として有するおそらくいくつかの鍵のうちの１つを選択する。次いで、それは、他のすべてのリンクに対して確立された一時鍵を使用して、この秘密鍵を、その子ノードに伝達する。次いで、子ノードが、それらが確立した一時鍵を使用して、永久鍵を更にツリーを下って伝達し、以下同様に行われる。永久鍵がすべての葉ノードに到達すると、ネットワークは、共通の秘密鍵を共有し、共通の秘密通信が可能になる。このような通信は、鍵の配布に対して定義されたツリーに従って行われる必要はない。
【００８９】
単一の端末が鍵配布用のサーバの役割をするブロードキャストのシナリオは、ツリーがルート（サーバ端末）より下に１階層しか有しない上記の事例の特殊な事例であることに留意されたい。このシナリオでは、最も短い一時鍵を、永久鍵とすることができ、この特定の鍵を確立するルートおよび葉ノードは、もはや通信する必要がない。この鍵は、他のノードへそれらの一時鍵を使用してブロードキャストされる。これは最も単純なツリー構成であるが、基地局がルートノードまたは無線ＬＡＮの自然な選択肢であり、アクセスポイントがルートノードの自然な選択肢である、セルラネットワークなどの集中型ネットワークに大いに適用できる。
【００９０】
本発明によるネットワーク生成のためのより洗練された手法は、次の通りである。ノードの各対が、生成された他のすべての秘密鍵から独立した秘密鍵を生成する、ネットワークを検討する。また、生成を行う対以外のノードは、この鍵について知らない。このモデルは、実際にいくつかの事例で適用可能である。１つの例は、ノードがそれらのポイントツーポイントチャネルの固有の特徴を使用して秘密鍵を生成する無線ネットワークである。このようなチャネルの特性の結果として、（正当な当事者または敵対者を問わず）任意の他のノードが特定の対のチャネルについて持ちうる知識は、通常は無視してよく、したがって、この例のモデルは、ここで直接適用できる。望ましくは、単一の秘密鍵をこのネットワークにおいて配布する。
【００９１】
図５は、３ノードネットワーク５０１および４ノードネットワーク５０２を示す。Ｓklが、ノードｋおよびｌによって共有される秘密鍵を表し、｜Ｓkl｜がこの鍵の長さであるとする。３ノードネットワーク５０１から始めると、｜Ｓ12｜＞｜Ｓ13｜として、以下の戦略が考えられる。まず、サーバの役割をするノード１が、上述のブロードキャスト手法を用いて、ノード２および３で共同鍵を確立する。２つの鍵の最小サイズの鍵が選択され、長さ｜Ｓ13｜の鍵が得られる。しかし、ノード１および２は、依然として、使用されないままの｜Ｓ12｜−｜Ｓ13｜の長さの残余秘密列を共有する。｜Ｓ23｜が｜Ｓ12｜−｜Ｓ13｜と比べてどうであるかに応じて、ノード２は、これらの残余ビットを使用して、仮定によりＳ12およびＳ13から独立しているストリングＳ23の全部または一部を、送信することができる。したがって、この戦略を用いて、ネットワークは、長さ｜Ｓ｜：
｜Ｓ｜＝ｍｉｎ［｜Ｓ12｜，｜Ｓ13｜＋｜Ｓ23｜］          式７
の共有鍵を生成することができる。
【００９２】
次に、｜Ｓ12｜＞｜Ｓ13｜＞｜Ｓ14｜である４ノードネットワーク５０２を検討する。上述の３ノードネットワーク戦略を使用して、ノード２、３、および４は、Ｓ12、Ｓ13、Ｓ14から独立した共通の鍵Ｓ(2,3,4)を共有する。次いで、ノード１が、ブロードキャストネットワーク手法を用いて、Ｓ14が最も短い列であるためＳ14を選んで、列Ｓ14をノード２および３に配布する。次いで、ノード２は、長さ｜Ｓ12｜−｜Ｓ14｜の未使用の鍵部分を使用して、ノード１に、Ｓ(2,3,4)のできる限り多くを提供する。したがって、ネットワークは、ここで、長さ｜Ｓ｜：
｜Ｓ｜＝ｍｉｎ［｜Ｓ12｜，｜Ｓ14＋Ｓ(2,3,4)｜］          式８
の鍵を共有する。この手法を一般化するために、以下の概念が導入される。１からＫのインデックスが付けられたｋ個のノードを有するネットワークを考え、Πが、これらのインデックス上の順列の集合を示すものとする。ポイントツーポイントの秘密鍵レートの集合｛Ｓlk｝（ただし、ｌ≠ｋ）が与えられたとすると、ネットワークによって全体として達成可能な秘密鍵レートは、
【００９３】
【数４】
2011217415.tif 000006
によって下限が限定され、上式において、
【００９４】
【数５】
2011217415.tif 000007
であり、
Ｌ2（π）＝｜Ｓπ(1)π(2)｜          式９ｃ
である。
【００９５】
本発明は、所望に応じて任意のタイプの無線通信システムに実装することができる。例えば、本発明は、任意のタイプの８０２型システムに実装することができる。本発明はまた、特定用途向け集積回路（ＡＳＩＣ）、複数の集積回路などの集積回路、論理プログラマブルゲートアレイ（ｌｏｇｉｃａｌ  ｐｒｏｇｒａｍｍａｂｌｅ  ｇａｔｅ  ａｒｒａｙ）（ＬＰＧＡ）、複数のＬＰＧＡ、個別部品、または、（複数の）集積回路、ＬＰＧＡ、および個別部品の組み合わせに実装してもよい。本発明はまた、ＷＴＲＵ、基地局、アクセスポイント、ＷＬＡＮ端末、ノード、またはセンサの実装として、部分的にあるいはシステムまたはネットワーク全体として、ソフトウェア、ハードウェア、またはデジタルシグナルプロセッサとして実装することができる。本発明は、無線通信システムまたは装置の物理層（無線もしくはデジタルベースバンド（ｄｉｇｉｔａｌ  ｂａｓｅｂａｎｄ））、または物理層におけるセキュリティ層に適用できる。
【産業上の利用可能性】
【００９６】
本発明は、一般的に無線通信システムに利用することができる。
【符号の説明】
【００９７】
１００、２００  トランシーバ
１０１、２０１  チャネル推定器
１０２、２０２  ＣＩＲポストプロセッサ
１０８、２０８  ＣＲＣ
【図１】
2011217415.tif 000008
【図２】
2011217415.tif 000009
【図３】
2011217415.tif 000010
【図４】
2011217415.tif 000011
【図５】
2011217415.tif 000012