(57)【特許請求の範囲】
【請求項１】
通信ネットワーク内のルータが、複数の擬似ルーティングプリフィックスを設定するステップと、
前記ルータが、該設定された複数の擬似ルーティングプリフィックスの一部を選択するステップ、
前記ルータが、該選択された一部の擬似ルーティングプリフィックスを、前記通信ネットワーク内の全てのルータの間で共有される共通ルーティングプリフィックスとともに、前記通信ネットワーク内にある一以上のホストへ送信するステップと、
前記一以上のホストは、該送信された一部の擬似ルーティングプリフィックスおよび前記共通プリフィックスを受信すると、該受信された一部の擬似ルーティングプリフィックスのいずれか一つと該受信された共通プリフィックスとを用いて、それぞれ、自ホストのネットワークアドレスを生成するステップと
を有するネットワークアドレス割当て方法。
【請求項２】
各擬似ルーティングプリフィックスには寿命が関連付けられることを特徴とする請求項１に記載のネットワークアドレス割当て方法。
【請求項３】
期限切れの擬似ルーティングプリフィックスを、該送信された一部の擬似ルーティングプリフィックスから取り除くステップを更に有するとを特徴とする請求項１に記載のネットワークアドレス割当て方法。
【請求項４】
該期限切れの擬似ルーティングプリフィックスを、前記複数の擬似ルーティングプリフィックスに含まれる他の擬似ルーティングプリフィックスで置換するステップを更に有することを特徴とする請求項３に記載のネットワークアドレス割当て方法。
【請求項５】
前記一部の擬似ルーティングプリフィックスの送信の際に、各擬似ルーティングプリフィックスの前記寿命についての情報を送信することを特徴とする請求項２に記載のネットワークアドレス割当て方法。
【請求項６】
前記ルータが前記複数の擬似ルーティングプリフィックスを設定する際、各擬似ルーティングプリフィックスについて、前記ルータの実際のルーティングプリフィックスと擬似プリフィックスインデックスナンバーとに対し暗号化が行われることを特徴とする請求項１に記載のネットワークアドレス割当て方法。
【請求項７】
前記暗号化の実行の際、前記通信ネットワーク内の複数のルータ間で共有される共有鍵が使用されることを特徴とする請求項６に記載のネットワークアドレス割当て方法。
【請求項８】
前記複数の擬似ルーティングプリフィックスのうち一部は予め決定されており、その余の擬似ルーティングプリフィックスは前記ルータにより生成されることを特徴とする請求項６に記載のネットワークアドレス割当て方法。
【請求項９】
通信ネットワーク内にある、公開鍵を記憶したルータが、実際のルーティングプリフィックスの関数である擬似ルーティングプリフィックスを算出するステップと、
前記擬似ルーティングプリフィックスと、前記通信ネットワーク内の全てのルータで共有される共通ルーティングプリフィックスとを報知するステップと、
前記通信ネットワークのホストが、前記公開鍵および当該ホストのサフィックスを使用して、該報知された擬似ルーティングプリフィックスを暗号化することにより暗号化擬似プリフィックスを取得するステップと、
前記ホストが、該報知された共通ルーティングプリフィックスおよび前記暗号化擬似プリフィックスを使用して、前記ホストのネットワークアドレスを生成するステップと
を有するネットワークアドレス割当て方法。
【請求項１０】
共通のマスター鍵を記憶する複数のルータと、前記マスター鍵を用いて暗号化された情報を復号するための秘密鍵を各々記憶する複数のホストとを有する通信ネットワークにおいてネットワークアドレス割当て方法であって、
前記通信ネットワーク内の一のルータが、当該一のルータの実際のルーティングプリフィックスの関数である擬似ルーティングプリフィックスを算出するステップと、
当該一のルータが、前記擬似ルーティングプリフィックスと前記複数のルータによって共有される共通ルーティングプリフィックスとを報知するステップと、
各ホストが、自己の秘密鍵と自己のサフィックスとを使用して、該報知された擬似ルーティングプリフィックスを暗号化して暗号化擬似プリフィックスを取得するステップと、
各ホストは、該報知された共通ルーティングプリフィックスおよび前記暗号化擬似プリフィックスを使用して、自己のネットワークアドレスを生成するステップと
を有するネットワークアドレス割当て方法。
【請求項１１】
複数の擬似ルーティングプリフィックスを設定する手段と、
該設定された複数の擬似ルーティングプリフィックスの一部を選択する手段と、
該選択された一部の擬似ルーティングプリフィックスを、通信ネットワーク内の全てのルータの間で共有される共通ルーティングプリフィックスとともに、前記通信ネットワーク内にある一以上のホストへ送信する手段と
を有するルータと、
該送信された一部の擬似ルーティングプリフィックスおよび前記共通プリフィックスを受信すると、該受信された一部の擬似ルーティングプリフィックスのいずれか一つと該受信された共通プリフィックスとを用いて、それぞれ、自ホストのネットワークアドレスを生成する手段を有するホストと
を有する通信システム。
【請求項１２】
各擬似ルーティングプリフィックスには寿命が関連付けられることを特徴とする請求項１１に記載の通信システム。
【請求項１３】
期限切れの擬似ルーティングプリフィックスが、該送信された一部の擬似ルーティングプリフィックスから取り除かれることを特徴とする請求項１１に記載の通信システム。
【請求項１４】
該期限切れの擬似ルーティングプリフィックスは、前記複数の擬似ルーティングプリフィックスに含まれる他の擬似ルーティングプリフィックスで置換されることを特徴とする請求項１３に記載の通信システム。
【請求項１５】
前記一部の擬似ルーティングプリフィックスの送信の際に、各擬似ルーティングプリフィックスの前記寿命についての情報が送信されることを特徴とする請求項１２に記載の通信システム。
【請求項１６】
前記ルータが前記複数の擬似ルーティングプリフィックスを設定する際、各擬似ルーティングプリフィックスについて、前記ルータの実際のルーティングプリフィックスと擬似プリフィックスインデックスナンバーとに対し暗号化が行われることを特徴とする請求項１１に記載の通信システム。
【請求項１７】
前記暗号化の実行の際、前記通信ネットワーク内の複数のルータ間で共有される共有鍵が使用されることを特徴とする請求項１６に記載の通信システム。
【請求項１８】
前記複数の擬似ルーティングプリフィックスのうち一部は予め決定されており、その余の擬似ルーティングプリフィックスは前記ルータにより生成されることを特徴とする請求項１６に記載の通信システム。
【請求項１９】
公開鍵を記憶する手段と、
実際のルーティングプリフィックスの関数である擬似ルーティングプリフィックスを算出する手段と、
前記擬似ルーティングプリフィックスと、前記通信ネットワーク内の全てのルータで共有される共通ルーティングプリフィックスとを報知する手段と
を有するルータと、
秘密鍵を記憶する手段と、
前記秘密鍵およびサフィックスを使用して、該報知された擬似ルーティングプリフィックスを暗号化することにより暗号化擬似プリフィックスを取得する手段と、
該報知された共通ルーティングプリフィックスおよび前記暗号化擬似プリフィックスを使用して、ネットワークアドレスを生成する手段と
を有するホストと
を有する通信システム。
【請求項２０】
通信ネットワーク内の他のルータとで共有されるマスター鍵を記憶する手段と、
自装置の実際のルーティングプリフィックスの関数である擬似ルーティングプリフィックスを算出する手段と、
前記擬似ルーティングプリフィックスと前記複数のルータによって共有される共通ルーティングプリフィックスとを報知する手段と
を各々有する複数のルータと、
前記通信ネットワーク内で暗号化された情報を復号するための秘密鍵を記憶する手段と、
自装置の前記秘密鍵と自ホストのサフィックスとを使用して、該報知された擬似ルーティングプリフィックスを暗号化して暗号化擬似プリフィックスを取得する手段と、
該報知された共通ルーティングプリフィックスおよび前記暗号化擬似プリフィックスを使用して、自装置のネットワークアドレスを生成する手段と
を各々有する複数のホストと
を有する通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全体としてネットワーク通信に関する。より具体的には、本発明は、ＩＰアドレス空間スクランブル処理を利用した、ネットワークアクセス中の位置秘匿の維持に関する。
【背景技術】
【０００２】
ＩＰアドレスが相互にわかっていれば、ＩＰネットワーク上の任意のノードは、インターネットプロトコル（ＩＰ）により相互にエンド・ツー・エンドの通信をおこなうことができる。ＩＰネットワークには、通常、一以上の交換機／ルータ、および二以上のホストが含まれている。これらのホストは、有線／無線リンクを介してルータと通信を行なう。同様に、ルータも、他のルータおよびホストと通信を行なう。全ての通信は、通常、インターネットプロトコルにより行なわれる。
【０００３】
各ＩＰメッセージは、一以上のＩＰパケットから構成される。ＩＰパケットのヘッダ情報から送り手と受け手とが識別できるので、ＩＰパケットからＩＰメッセージ全体を再構成することができる。ＩＰパケットはそれぞれ別個に独立しているので、ネットワークの同一の経路を経て送り手から受け手にルーティングされるとは限らない。ＩＰネットワークにおいて、送り手は、ＩＰパケットヘッダの宛先ＩＰアドレスに目的とする受け手のＩＰアドレスをセットして、ＩＰパケットを受け手に送信する。ＩＰネットワークにパケットが放出されると、ルーティングメカニズムが働いて、宛先ホストにパケットを配送するように試行される。
【０００４】
ＩＰパケットの宛先ＩＰアドレスフィールドに含まれる情報により、ネットワークのルーティングメカニズムは、ＩＰパケットを目的とする受け手に配信することができる。ＩＰアドレスは、プリフィックス−サフィックス形式で構成される。ＩＰアドレスのプリフィックス部には、宛先サブネットのサブネットアドレスが含まれる。サブネットアドレスは、パケットの送られることになる行き先を示している。ルータは、ＩＰアドレスに含まれる宛先サブネットプリフィックスに着目し、そのプリフィックスと各ルータに保持されているルーティングテーブルを照合することによって、パケットを送るために必要となるリンクの選択を含む経路（ルート）を決定する。インターネットの異なる部分で、ＲＩＰ、ＯＳＰＦ、およびＢＧＰ等の多数のルーティングプロトコルが使用されている。これらのルーティングプロトコルは、ルータ間の通信のため、および、最新の有効なルーティングテーブルを構築するために使用される。
【０００５】
宛先ＩＰアドレスからの宛先サブネットプリフィックスとルーティングテーブルとを照合することは、現状において、非常に簡単な処理である。ルータは、マスク機能をＩＰアドレスに適用することにより、プリフィックスを得て、このプリフィックスと最長一致するエントリーをルーティングテーブルから探索する。エントリーが見付かると、パケットは、ルーティングテーブルのエントリに記載されたリンクにルーティングされるか、あるいはそのリンクから送出される。
【０００６】
この処理が本質的に単純であることから、ルータはパケットを非常に高速に処理することができ、また多量の転送を処理することができる。しかし、この処理が問題を発生させ得ることにもなる。これらの問題は、インターネットを含むネットワークが通信の主要な手段となったので、ますます重要となってきている。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ロケーションプライバシーは、このような問題の一つである。この問題は、サブネットの大部分、特にスタブサブネットが、通常、地図上の（geographical）かなり狭い地域に固定的に関連付けられているということから生じる。このように固定的に関連付けられていることにより、サブネットプリフィックスと位置とをマッピングして、相当に正確なデータベースを構築することができる。このようにして、ユーザは、自分のロケーションプライバシーの相当な部分を失ってしまう。たとえユーザが移動して、その位置を時間的に変化させても、地図上でユーザの位置を識別することができる。
【０００８】
すでに説明したように、ネットワークにおける真のエンドツーエンド通信のために、インターネットプロトコルでは、複数のホストがＩＰアドレスを相互に知っている必要がある。言い換えると、ホストは、その位置を実際に明らかにすることなく、他のホストとエンドツーエンド形式で通信することができない。その理由は、ＩＰアドレスが与えられると、そのＩＰアドレスからサブネットプリフィックスを大変容易に推定できるからであり、さらに、サブネットプリフィックスが地図上の位置に対応しているからである。
【０００９】
したがって、以上説明してきた「ロケーションプライバシー」の問題を解決する必要がある。
【００１０】
すなわち、ネットワークのユーザにとって、ＩＰアドレス等のネットワークアドレスに宛先サブネット情報が単純かつ容易に推測できる形式で含まれていることから、現在のところ、自身のロケーションプライバシーが制限されている。対応するサブネットを、簡単なマスク機能を適用して決定することにより、位置情報が抽出されてしまうからである。
【課題を解決するための手段】
【００１１】
本発明の一実施形態では、ＩＰアドレスに簡単なマスク機能を適用する代わりに、暗号機能が適用される。この実施形態では、ＩＰアドレスに対応する宛先サブネットが簡単なマスク機能の適用では決定できないようにＩＰアドレスが構成される。その代わりに、ルータが、秘密情報すなわち暗号処理と組み合わされる鍵を使用して、対応するサブネットに対するルーティングプリフィックスを決定する。このスキームの利用により、秘密情報を知らないエンティティは、ＩＰアドレスが与えられても、対応するサブネットプリフィックスを決定することができない。このスキームを利用して、サブネット内のホストのＩＰアドレス間の相関を低減することもできる。
【００１２】
以上説明した「課題を解決するための手段」は、例示としてのものである。発明の範囲を画定する特許請求の範囲を制限するものと解釈されてはならない。
【発明を実施するための最良の形態】
【００１３】
以下、図面を参照して本発明を説明する。図１（Ａ）は、ネットワーク１００を説明するブロック図である。ネットワーク１００は、複数の交換機／ルータ（ルータ１０２、１０４、１０６、１０８、１１０、１１２を含む）および２以上のホスト（ホスト１１４、ホスト１１６を含む）を含む。ネットワーク１００は、公開／非公開のデータ通信用ネットワークとすることができる。典型的な実施形態において、ネットワーク１００は、伝送制御プロトコル（ＴＣＰ）／インターネットプロトコル（ＩＰ）（以下、ＴＣＰ／ＩＰと略記する）にしたがってデータのパケット通信をおこなう。しかし、別のデータフォーマットおよび別の通信プロトコルで置き換えることも、あるいはそれらをＴＣＰおよびＩＰと共存させることもできる。
【００１４】
なお、このネットワーク１００の構成は単なる例示である。ネットワーク内のルータ数およびホスト数、ならびにこれらの装置間の相互接続個々の数を任意に設定することができる。またこれらの数が増減することもある。ネットワーク装置の間の各接続には、イーサネット（Ｅｔｈｅｒｎｅｔ：登録商標）、Ｔ１回線、あるいは総合デジタル通信網（ＩＳＤＮ）等の適切な回線技術が使用される。
また、ネットワーク１００から、インターネットにアクセスすることができる。
ネットワークは、部分ネットワークすなわちサブネットを有することができる。サブネット自体も、より小さなサブネットを一つ以上有することができる。ネットワーク、部分ネットワークすなわちサブネットという用語は、相互に置き換えて使用することができる。サブネットのうち、より小さなサブネットすなわち入れ子になっているサブネットを含まないもの、あるいは２以上のサブネットの間の一時的ネットワーク(ネットワーク間を接続するネットワーク)として機能しないものは、スタブサブネットと一般的に称される。
【００１５】
ルータ１０２、１０４、１０６、１０８、１１０および１１２は装置あるいはソフトウェアとして構成され、受信したデータパケットをその宛先に向けて転送することになる次のネットワークポイントを決定する。各ルータは、ネットワーク１００の少なくとも２つの分枝と接続し、各データパケットを送信する経路を、その時点のネットワーク状況に基づいて決定する。一般に、どんなゲートウェイにもルータが１台設置される。ゲートウェイにおいて、あるネットワークが別のネットワークと接触する。ルータが、ネットワーク交換機の一部として含まれることもある。
【００１６】
ルータは、自身が利用可能なルータおよびそれらの状態についてテーブルを作成し、作成したテーブルを保持することができる。ルータは、この情報に距離アルゴリズムおよび費用アルゴリズムを利用して、与えられたパケットに最良の経路（ルートとも称する）を決定する。パケットとは、ネットワークの発信元と宛先との間でルーティングされるデータの単位である。典型的な実施形態において、ネットワークの発信元位置からネットワークの宛先位置にファイルが送信されると、ＴＣＰ／ＩＰのＴＣＰ層によって、このファイルはルーティングのためにパケットに分割される。各パケットには、個別に番号が付けられ、宛先のネットワークアドレスが含まれている。ユニキャスト転送において、ネットワークアドレスすなわちＩＰアドレスは、ネットワーク上の位置を一意に示すものである。ＩＰアドレスを、一意の数字列として、さらに／あるいはドメインネームと関連付けて表現することができる。
【００１７】
ネットワーク上の各サブネットは、一以上の識別子すなわちネットワークナンバーを有する。ネットワークナンバーは、サブネットプリフィックスあるいは単にプリフィックスと称される。より大きなサブネット内のサブネットは、より大きなサブネットに固有のプリフィックスを有する。普通、より小さな（すなわち入れ子となっている）サブネットのプリフィックスは、その長さが、より大きなサブネットのプリフィックスと同じ長さかより長くなっている。また、より小さなサブネットのプリフィックスの全てに、より大きなプリフィックスのうちのひとつをそのまま含ませることが一般に行なわれている。したがって、より大きなサブネットに入れ子となっている、より小さなサブネットのプリフィックスは、通常、そのより大きなサブネットのプリフィックスとその他の数字とが結合したものとなっている。
【００１８】
あるホスト（ホスト１１４およびホスト１１６を含む）は、ネットワーク１００上の別のホストと接続している。各ホストは、部分ネットワークすなわちサブネットと関連付けられている。ホスト１１４はサブネット１１８と、ホスト１１６はサブネット１２０と関連付けられている。各ホストは、固有のローカルナンバーすなわちホストナンバー（通常、サフィックスと称される）を有す。ホストナンバーは、ネットワークナンバーすなわちサブネットナンバー(通常、サブネットプリフィックスあるいは、単にプリフィックスと称される)と組み合わさって、ホストに固有のＩＰアドレスを形成する。
【００１９】
以上説明してきたように、ホストおよびそのサブネットは、一般に、地図上で、位置が共通している。すでに説明したように、ホストおよびサブネットの位置は、マスク機能を適用することにより推測できる。ここで、マスク機能とは従来からルータが使用している機能であり、サフィックスをプリフィックスから分離し、ルーティングテーブル中のエントリーと比較することによりパケットをルーティングするものである。同様のマスク機能を利用して、宛先サブネットの位置を得ることもできる。
【００２０】
ネットワーク１００において、ロケーションプライバシーを提供するために、ルータのいくつかでは、簡単なマスク機能が暗号機能で置き換えられている。このようなルータの各々は、暗号処理と結びついた秘密情報を利用して対応するサブネットのルーティングプリフィックスを決定する。一方、秘密情報を知らないエンティティは、対応するサブネットプリフィックスを決定することができない。
【００２１】
与えられたＩＰアドレスからルータがサブネットルーティングプリフィックスを復号化するために、ＩＰアドレスの中でサブネットルーティングプリフィックスが最初に暗号化されなければならない。したがって、ルータがＩＰアドレスに復号化処理を適用するときに、正確な／好適なルーティングプリフィックスが結果として得られるように、ＩＰアドレスを注意深く割当てなければならない。
【００２２】
図１（Ａ）の例では、プライバシードメイン１２２が定義されている。プライバシードメインは、相互に接続している複数のルータからなる十分な大きさの集合、すなわちサイズの大きなサブネットである。図１（Ａ）では、プライバシードメイン１２２には、ルータ１０２、１０４および１０６が含まれる。別の実施形態では、あるいはネットワーク１００で定義できる別のプライバシードメインでは、プライバシードメインのメンバーと指定されるルータの数は増減することがある。
【００２３】
プライバシードメイン１２２内の全ルータについて、共有秘密方式で鍵を設定し、その鍵を定期的に再設定することができるものとする。秘密鍵は、特定のフォーマットあるいは特定の内容を有するデータとすることができる。鍵の設定、再設定は、自動／手動のいずれで行なわれてもよい。
【００２４】
図１（Ｂ）は、サブネットルーティングプリフィックスを復号化するために、プライバシードメイン１２２内で使用することができるルータ１５０を例示する。図に示すように、復号鍵が、復号化ユニット／ヘッダ組立ユニット１５２に供給される。ルータ１５０を通って転送されていくパケットは、パケット宛先アドレス抽出部１５４を通過する。抽出部１５４は、パケット宛先アドレスをユニット１５２に供給する。ユニット１５２およびルーティングテーブル１５６は、ルーティングテーブル探査部１５８の入力にそれぞれ接続している。次に、探査部１５８およびユニット１５２の出力は、コレクトインターフェースディスパッチャー１６０に接続している。このとき、復号化されたサブネットルーティングプリフィックスが、ルータ１５０からネットワーク１００越しに供給されることがある。プライバシードメイン１２２内では、サブネットプリフィックスを復号化することにより、ＩＰアドレスによって識別される地図上の特定の位置を明らかとすることなく、プライバシードメイン内のパケットの適切なルーティングが可能となる。
【００２５】
図１（Ｂ）のルータ１５０は、同様に、サブネットルーティングプリフィックスを暗号化できる。図１（Ａ）に示されるネットワーク１００内のルータの全てが、サブネットルーティングプリフィックスを暗号化および復号化できる必要はない。したがって、例えば、ルータ１０２がルータ１５０の機能を有するけれども、ルータ１０８がその機能を有しないことがある。本実施形態における、この状況についての本発明の取り扱いを、以下、詳細に説明する。
【００２６】
図２は、インターネットプロトコル（ＩＰ）のアドレスフォーマット２００を説明している。アドレス２００には、プリフィックス２０２およびサフィックス２０４が含まれている。プリフィックス２０２には、プライバシードメインプリフィックス部（P0と記される）２０６およびルーティングプリフィックス部（PRと記される）２０８が含まれている。プライバシードメインプリフィックス部P0２０６は、プライバシードメインと関連付けられている。あるプライバシードメイン内の全ホストおよび全サブネットは、プライバシードメインプリフィックス部P0２０６を共有する。実施形態により、P0が１６ビット長となることもあれば、ビット長を自由に割当てることもできる。また、ビット長は動的に変化してもよい。
プライバシードメイン内の全ホストがP0をプリフィックスの先頭として共有していることが好ましい。このようになっていると、プライバシードメインの外を発信元とするパケットを、プライバシードメインにルーティングすることができる。プライバシードメイン内の全ルータは、固有のルーティングプリフィックス部PR２０８を有する。プリフィックスPRは、通常、４８ビット長であるが、長さを自由に選んで使用することもできる。全ホスト（ホストiと索引付けられている）は、自身のＩＰアドレスに対してサフィックス２０４を構成することができる。構成されたサフィックス２０４は、Miと記される。サフィックスは、通常、６４ビット長であるが、長さを自由に選択できる。
【００２７】
典型的な実施形態において、ネットワークは、各ホストによるＩＰアドレス２００の６４ビットサフィックス部の構成法を制御することができない。ホストは、サブネット内において一意である、つまり、その値はサブネット内の他のホストに使用されていない任意の値をサフィックス２１０について使用することができる。一意性を保証するために、重複アドレス検出およびホスト／近隣（Neighbor）テーブル等の従来の技術を使用することができる。
【００２８】
図３は、図１（Ａ）のネットワークの動作を説明する流れ図である。この実施形態において、ホストiは、新しくＩＰアドレスを構成する必要がある。ホストが新しいサブネットに移動するか、新しいルータが利用できることを検出するか、先に割当てられたＩＰアドレスが失効するか、あるいは別の理由により、新たに必要となることがある。ホストiはプリフィックスをMiとなるように再構成する。ルータ報知メッセージとしてルータから報知されるプリフィックスを使用してＩＰアドレスを完成させる代わりに、ホストは、プリフィックスを、ルータ、ＤＨＣＰサーバ、あるいは適切な他のアドレス管理エンティティに要求する（ステップ３０２）。ここで、「ルータ」とは、ルータ、ＤＨＣＰサーバ、データ交換機、サーバあるいは他のアドレス管理エンティティおよびこれらと同等のものである。ルータは、この要求を受信する（ステップ３０４）。
【００２９】
ルータは、擬似プリフィックスを計算する（ステップ３０６）。ルータにルーティングプリフィックスPRが割当てられている。ルータは、擬似プリフィックスP0 P`(R,i)を計算し、その値をホストに通信する（ステップ３０８）。添え字(R、i)は、プリフィックスP`が各ホストについてルータ毎に別々に、および各ルータについてホスト毎に別々に計算されることを意味している。つまり、プリフィックスP`は、ルータとホストの全組合せについて異なることがあるということである。P`(R,i)の異なる計算方法を、以下に説明する。ホストはP0 、P`(R,i)およびサフィックスMiを使用して、ＩＰアドレス全体を構成する。
【００３０】
図４は、ルータからの擬似プリフィックスを使用してホストにより構成されるＩＰアドレス４００を説明している。ＩＰアドレス４００は、プリフィックス４０２およびサフィックス４０４を含んでいる。プリフィックスは、ルータに割当てられたルーティングプリフィックスPRおよび擬似プリフィックスP`(R,i)の連結を含む。サフィックスMi４０４はプリフィックスと組み合わさってＩＰアドレス４００を構成する。
【００３１】
図５、図６および図７は、ルータが擬似プリフィックスP`(R,i)を計算することがある典型的な実施形態を説明している。共通するプライバシードメイン内の全ルータは、同一のプリフィックス計算法を使用することが好ましい。
【００３２】
第１の典型的な実施形態において、割当てられたプリフィックスは、ホストのサフィックスMiに、ルータあるいはサブネットのルーティングプリフィックスPRおよび共通秘密鍵を論理的に結合することにより得られる。この鍵は、プライバシードメイン内の全ルータ間で共有される。適切な論理結合であれば、使用することができる。典型的な実施形態において、排他的論理和（ＸＯＲ）関数が使用される。したがって、擬似プリフィックスP`(R,i)は数１のように計算される。
【００３３】
【数１】
0004417847.tif 000002
【００３４】
次に、ホストiが、選択したサフィックスに擬似プリフィックスP`(R,i)を連結することにより、ＩＰアドレス全体を構成する。ホストiは、プライバシードメインの外部の別のホストとの通信に、ＩＰアドレス(P0，P`(R,i) Mi)を使用することができる。プライバシードメインの外部の通常のルータは、ＩＰアドレス(P0，P`(R,i) Mi)を宛先としたパケットに出会うと、従来のマスク機能を適用する。プライバシードメインの外部のルータのルーティングテーブルで最長一致する可能性のあるプリフィックスは、P0である。したがって、ルータは、パケットをプリフィックスP0 に向かうリンクにルーティングする。やがて、パケットは、プライバシードメイン内のルータに届く。プライバシードメイン内のホストを宛先としたパケットがプライバシードメイン内で発信されているときには、パケットがこのプライバシードメインの外部のルータに実際に届くことはない。プライバシードメイン内部のルータがこのパケットに出会うと、ＩＰアドレスに既に含まれているP`(R,i) およびMiを共通秘密鍵と排他的論理和演算をすることにより、このパケットについて実際のルーティングプリフィックスP0 PRを計算することができる。実際のプリフィックスが決定すると、ルータは従来のルーティングテーブル照合法を使用して、ルーティングを実際に決定する。
【００３５】
プライバシードメイン内のルータは、ＩＰアドレスが与えられたときのプリフィックスの計算結果をキャッシュして、全パケットについてルーティングプリフィックスを再計算することを回避し、ルーティング処理を高速化することができる。例えば、鍵が再設定されている間のように計算に使用される秘密が変更されたときには、キャッシュされた値を無効としなければならない。ルータでキャッシュできる容量は限られている場合がある。この場合には、ルータは計算結果を永続的にキャッシュすることができない。その代わりに、ルータは先にキャッシュしたエントリーから削除し、新しいエントリー用に空きを作ることができる。保持するエントリーと削除するエントリーは、キャッシュ置換アルゴリズムによって指定される。数種類のキャッシュ置換アルゴリズムが研究されてきている。
【００３６】
図５は、この処理過程を説明している。ステップ５００から、この方法が開始する。プライバシードメインのルータは、パケットを受信する（ステップ５０２）。ルータは、擬似プリフィックスP0 P`(R,i)に対応する実際のルーティングプリフィックスが既に計算されてキャッシュメモリーに格納されているか否かを決定する（ステップ５０４）。格納されている場合には、ステップ５１０に進むように制御される。格納されていない場合には、ルーティングプリフィックスが計算され（ステップ５０６）、ルーティングテーブルが探索されて、パケットをルーティングするための実際のアドレスが決定され（ステップ５０８）、パケットがルーティングされる（ステップ５１０）。続いて、ルータは、プリフィックスが既にキャッシュに格納されているか否かを決定する（ステップ５１２）。既にキャッシュされている場合は、次のパケットを受信するために、ステップ５０２に戻るように制御される。
プリフィックスがまだキャッシュされていない場合は、プリフィックスがメモリに保存され（ステップ５１４）、ステップ５０２に戻るように制御される。プリフィックスをメモリに保存することに、プライバシードメインの別のルータにプリフィックスを通信することが含まれることもある。
【００３７】
割当てられるプリフィックスを計算するための第２の実施形態において、第２のルーティングプリフィックス部PRに、利用できる余分なビット、すなわちスペアビットがあることを前提としている。この部分は通常４８ビット長であるが、この長さは、実装により変化することがある。また、実際のルーティングプリフィックスのビット長が、４８ビット以下のy ビットであることが前提とされる。この場合、（４８−y）ビットのスペアビットがあることになる。（４８−y）の値が１０ないし３０ビット程度と十分に大きい場合には、これらのビットを、メッセージ認証コード(MAC)に対するナンス（Nonce）を搬送するために使用することができる。メッセージ認証コードは、デ−タ（平文あるいは暗号文）および秘密鍵の両機能を有するビット列であり、データ認証ができるようにデータに添付される。メッセージ認証コードを生成するために使用される関数は一方向関数でなければならない。認証メッセージが関連付けられたデータにより、受け手はメッセージの完全性を検証することができる。したがって、本実施形態において、有効なルータあるいは別の有効なエンティティのみが、ＩＰアドレスに対して正しくプリフィックスを計算することができる。ルータは、割当てられるプリフィックスを数２のように計算することができる。
【００３８】
【数２】
0004417847.tif 000003
【００３９】
本発明では、多数の形式をMACがとることができる。実施形態により、MACは、アドバンスド暗号標準（Advanced Encryption Standard、AES)であることもあれば、セキュアハッシュアルゴリズム（Secure Hash Algorithm、SHA-1）を含むハッシュ関数であることもある。
【００４０】
割当てられるプリフィックスP'(R,i) は、次の(a)、(b)とが連結されたものである：(a) y ビット長の実際のプリフィックスと、ルータの間の共有鍵k を使用してNonceおよびホストに構成されたサフィックスについて計算されたy ビット長のメッセージ認証コードMACとの排他的論理和演算あるいは別の論理結合演算により計算されたもの。(b)（４８−ｙ）ビット長のNonce。
【００４１】
図６は、本実施形態にしたがって割当てられるＩＰアドレス６００を説明している。アドレス６００には、プリフィックス６０２およびサフィックス６０４が含まれる。プリフィックスは、上記説明の様に決定され、プライバシードメインサブネットプリフィックス部P0６０６、割当てられるプリフィックスP*(R,i)６０８、およびNoncei６１０を含んでいる。典型的な実施形態において、実際のプリフィックスPR６０８が必要とするのは長くても１８ビット長であるから、Nonce６１０用に３０ビットが残る。
【００４２】
ホストiは、プライバシードメイン内外の別のホストとの通信にＩＰアドレス(P0，P*(R,i) Noncei Mi)を使用することができる。プライバシードメインの外部のルータがＩＰアドレス (P0，P*(R,i) Noncei Mi)を宛先とするパケットに出会うと、ルータは、プリフィックスP0を有するアドレスに関連付けられたサブネットに向かうリンクにパケットをルーティングする。プライバシードメイン内部のルータがこのパケットに出会うと、ルータは、鍵Kを使用してＩＰヘッダに含まれるNonceiおよびMi についてメッセージ認証コードを計算し、ＩＰアドレスに含まれるメッセージ認証コードとP*(R,i)との排他的論理和を取り、その結果とNonceiとを連結して、このパケットに対して実際のルーティングプリフィックス(P0 PR)を計算することができる。
【００４３】
鍵とは、二進乱数列あるいは二進擬似乱数列等の情報であり、暗号装置における電気信号の暗号化／復号化のために実行される処理を初期設定するとき、あるいは、その処理を定期的に変化させるために利用されるものである。
Nonceとは、暗号学において、カウンターあるいはタイムスタンプ等の時変パラメータとして定義され、メッセージのなりすまし（replay）および別種の攻撃を防止するために鍵管理プロトコルで使用される。この文脈において、Nonceiは、擬似プリフィックス生成時にルータにより選択される乱数である。ルータは、サブネットの全ホストに対して異なる乱数を確実に選択することができる。しかし、このことは必須ではない。
ルータがランダムなあるいは可変のNonceを使用しない場合でも、セキュリティのレベルは低いものの、以上説明してきたシステムおよび方法は機能する。
【００４４】
図７は、本実施形態にしたがうルーティングプリフィックスの計算を説明している。図７は、図５のステップ５０６のある実装の詳細を示している。擬似プリフィックスに対応するルーティングプリフィックスがメモリに格納されていないことを決定し（図５のステップ５０４）た後、ＩＰアドレスに対してルーティングプリフィックスを計算するルータは、まず、メッセージ認証コードを計算する（図７のステップ７０２）。結果として得られるメッセージ認証コードは、割当てられるプリフィックス P*(R,i)と論理結合が取られる（ステップ７０４）。実施形態によっては、排他的論理和が論理結合として演算される。最後に、ステップ７０４の結果にNonceが連結されて、実際のルーティングプリフィックスP'(R,i)が生成される（ステップ７０６）。
【００４５】
図７の処理から、図５のステップ５０８に進むように制御される。実際のプリフィックスを決定すると、ルータは、従来からある簡単な単純なルーティングテーブル探索を使用して実際のルーティングを決定することができる。ルータは、与えられたＩＰアドレスに大して上記の様に計算した結果をキャッシュして、全てのパケットに対してルーティングプリフィックスを再計算することを回避して、ルーティング処理を高速化することができる。
【００４６】
第３実施形態において、割当てられるプリフィックスは、実際のプリフィックス PRを暗号化したものである。暗号化に使用される鍵は、ホストの構成されたサフィックスMiとルータ間で共有される共有秘密とのハッシュとして計算される。
【００４７】
【数３】
0004417847.tif 000004
【００４８】
【数４】
0004417847.tif 000005
【００４９】
この鍵を計算するためのハッシュ関数には、特に、すでに説明したAESおよびSHA-1といったハッシュ関数を含めることができる。暗号化関数も、これらハッシュ関数の一つ等のハッシュ関数であることもある。
【００５０】
第１および第２実施形態のように、ホストiはプライバシードメイン内外の別のホストとの通信に、ＩＰアドレス(P0 , P`(R,i) Mi)を使用することができる。プライバシードメイン外部のルータがＩＰアドレス(P0 , P`(R,i) Mi)を宛先とするパケットに出会うと、ルータは、プリフィックスP0でアドレスされたサブネットアドレスに向かうリンクにパケットをルーティングする。プライバシードメイン内部のルータがこのパケットに出会うと、ルータは、ＩＰアドレス中の共有秘密およびサフィックス Miのハッシュを利用することによって鍵Kをまず生成することによって、このパケットに対する実際のルーティングプリフィックス (P0 PR)を計算することができる、鍵が生成されると、ルータは容易にP`(R, i)を復号化してPRを得ることができる。
【００５１】
図８は、第３実施形態にしたがってプリフィックスを得るルータの動作を説明している。図８は、図５のステップ５０６の実装の詳細のひとつを示している。必要とされるプリフィックスがメモリに格納されていないことが決定され（図５のステップ５０４）た後、ＩＰアドレスに対してルーティングプリフィックスを計算するルータは、まず、復号鍵kを生成する（図８のステップ８０２）。すでに説明したように、アドレスに含まれるプライバシードメインのルータの間で共有される秘密とホストに対するサフィックスMiのハッシュを利用して、復号鍵kが生成される実施形態がある。P`(R,i)の復号化に鍵kが使用される（ステップ８０４）。
【００５２】
以上、説明してきたように、典型的な実施形態において、ＩＰサフィックスが、プリフィックス生成のために使用される。第２実施形態において、新たにＩＰアドレスを構成するためにルータに関連付けられたホストが使用する擬似プリフィックスを、ルータは多数保持している。図９は、本実施形態の一実施例を説明する流れ図である。
【００５３】
第２実施形態にしたがえば、ネットワークにおけるホストは、ネットワークすなわちＩＰアドレスを新たに構成する必要があるかもしない。このことは以下の場合におきるであろう：ホストが新しいサブネットに移動す場合、ホストが新しいルータを利用できることを検出した場合、先に割当てられたＩＰアドレスが期限切れして失効した場合、あるいは、他の理由の場合がある。ホストは、利用できるプリフィックスを含んでいるルータ報知（ＲＡ）メッセージからプリフィックスを得なければならない。ＲＡメッセージは通常、定期的にブロードキャストあるいはマルチキャストされる。連続する報知の間の時間間隔は時と実装により変化する。
【００５４】
また、この実施形態にしたがうと、ルータRは擬似ルーティングプリフィックスSR = {P`(R,1)， P`(R,2)， P`(R,3)，…P`(R,n)}の大きな集合を保持する。ルータは、SRから、擬似ルーティングプリフィックスの小さなサブセットを選択する（ステップ９０２）。ルータは、選択した擬似ルーティングプリフィックスの各々に、プライバシードメインプリフィックスP0をプリフィックスする。
【００５５】
ある実施形態では、ルータは、選択した擬似ルーティングプリフィックスのいずれかが期限切れしているか否かを決定する（ステップ９０４）。この実施形態において、ルータに保持されている擬似プリフィックスの各々に寿命（lifetime）が関連付けられている。この寿命を過ぎると、ルータに送信される報知メッセージには、擬似プリフィックスが含まれることはない。しかし、ルータは、後に、同一の擬似プリフィックスを再導入することができる。ルータは、期限が切れた擬似プリフィックスを削除するか、あるいは期限が切れた擬似プリフィックスを集合SRから取り出した新しいもので置き換えることができる。ルータは、ルータ報知メッセージ中に、擬似プリフィックスの寿命の残り、すなわち期限切れ時間を明示的に表示することができる。あるいは、ルータは、ルータ報知メッセージ中の擬似プリフィックスの順序を定期的に変更し続けることができる。すなわち、リストから徐々に消えていく様に、より古い擬似プリフィックスがリストの最後に移動される。すなわち、ホストは、擬似プリフィックスのリスト中の位置を見ることによって、擬似プリフィックスの寿命の残りを、それとなく推測することができる。ホストが、ルータにより報知された擬似プリフィックスのサブセットから得られる擬似プリフィックスを使用してそのＩＰアドレスを構成した後、ルータにより報知されたサブセットから擬似プリフィックスが消える場合には、ホストは、この事象を擬似プリフィックスの時間切れと捉え、直近に報知されたプリフィックスサブセットから新しいものを選択する。
【００５６】
ルータが、ルータ報知メッセージを送信する（ステップ９０６）。新たにＩＰアドレスを構成する必要があるホストがルータ報知メッセージを受信する（ステップ９０８）。
【００５７】
ホストは、ルータにより報知される擬似プリフィックスのいずれか一つを選択し、ＩＰアドレスを構成することができる。ホストは擬似プリフィックスを選択して、自身のＩＰアドレスを構成する（ステップ９１０）。
【００５８】
ある実施形態では、ホストは、選択した擬似プリフィックスが期限切れ、すなわち失効しているか否かを決定する（ステップ９１２）。擬似プリフィックスが失効しているか、あるいはルータが定期的に送信するＲＡメッセージが徐々に消失している場合には、擬似プリフィックスの時間切れと仮定できる。あるいは、擬似プリフィックスの時間切れを示す明示的なメッセージあるいは別の手段が備わっていても良い。備わっている場合には、別の擬似プリフィックスを選択するためにステップ９１０に戻るように制御される。期限切れの擬似プリフィックスを使用していたホストは、報知されたプリフィックスから新しいものを選択しなければならない。備わっていない場合には、ホストは自身のＩＰアドレスを構成する（ステップ９１４）。この処理の詳細を以下に説明する。続いて、ホストは、ルータ報知メッセージを受信する（ステップ９１６）。ホストは、ステップ９１０で選択した擬似プリフィックスがリスト中にまだあるか、つまり依然として有効であるかを確かめるテストをおこなう（ステップ９１８）。有効である場合には、ホストは次のルータ報知メッセージの受信を待ち、ステップ９１０で選択したプリフィックスの有効性を検証する。選択した擬似プリフィックスが、ルータから送信されるリストにない場合、あるいは、選択した擬似プリフィックスが別の理由により失効／期限切れとなっている場合には、ステップ９１０に進むように制御され、ホストは別の擬似プリフィックスを選択する。
【００５９】
図１０は、擬似プリフィックスの集合SRを計算する方法を説明している。ルータは、ルーティングプリフィックスの集合SRを適切な方法を利用して計算することができる。典型的な方法を以下説明するが、他の方法で置き換えることもできる。
【００６０】
本実施例において、関数 Decryption(P`(R , k))からPRを推測することができる場合に、擬似ルーティングプリフィックスP`(R,k) は、集合SRに属する。例えば、PR = Decryption(P`(R , k))が成立するときである。数種類の方法で推測することができる。その一つをここで説明する。実際のルーティングプリフィックスPRが４８ビット未満のyビット長であるとする。この場合、m =（４８−y）ビットのスペアビットがあり、n = 2m 個の擬似ルーティングプリフィックス候補からなる集合が得られる。ここでも４８ビット長で考える。なぜなら、この長さがプリフィックスとして通常用いられるからである。しかし、この値は実装方法によって変化する。擬似プリフィックスの集合は、数５のよう計算できる：
【００６１】
【数５】
0004417847.tif 000006
【００６２】
図１０は、この計算を説明している。図１０の方法では、まず、インデックス変数kが１となるように初期化される（ステップ１００２）。インデックス変数がテストされ、k = nが成立すると、処理を停止する（ステップ１００４）。k = nとなるまで、数５にしたがって擬似ルーティングプリフィックスが計算される（ステップ１００６）。インデックス変数kに１が加算され、ステップ１００４の戻るように制御される（ステップ１００８）。擬似プリフィックスの集合が適切な方法により作られる別の実施形態がある。例えば、擬似プリフィックスの全集合（すなわち、全ての'k'プリフィックス）を、予め生成しない実施形態もある。むしろ実施形態によっては、ルータ（あるいはルータを補助するいずれかのエンティティ）が、必要な時に、擬似プリフィックスを生成して使用するほうが良い。なぜなら、要素数kである集合SRから、一度に小さなサブセットしか、ルータが使用しないからである。 
【００６３】
P`(R,k)を復号化することにより、yビット長のPRとmビット長のkとが結合された数が得られる。この処理では、暗号処理を適用する前に、PRに結合されたmビットが切り詰められ（すなわち取り除かれ）ることにより、ルーティングプリフィックスが得られる。以上説明したように、現在のところ、４８ビット長のブロックについて容易に利用できる暗号がないことに注意を喚起する。この機能を実行するには、現在利用できる適切な暗号処理／装置、あるいは今後開発される暗号処理／装置を使用することができる。
【００６４】
図１１は、ホストが図１０の方法にしたがって構成したＩＰアドレス１１００を説明している。ＩＰアドレス１１００はプリフィックス１１０２とサフィックス１１０４を有している。プリフィックス１１０２は、プライバシードメインサブネットプリフィックス部P0 １１０６と、ステップ１００６で計算される擬似ルーティングプリフィックスP`(R,k) １１０８の一つとを含んでいる。両部１１０６と１１０８は、ホストサフィックスMi １１０４と連結されて、ＩＰアドレス１１００を構成する。
【００６５】
ホストiは、プライバシードメイン内外の別のホストとの通信にＩＰアドレス(P0，P`(R,k) Mi）１１００を使用することができる。プライバシードメイン外部のルータが、ＩＰアドレス (P0， P`(R,k) Mi)を宛先とするパケットに出会うと、ルータは、プリフィックスP0を含むアドレスを有するルータに向かうリンクに、このパケットをルーティングする。プライバシードメイン内部のルータがこのパケットに出会うと、このパケットについて、このルータは、P`(R,k)を復号化し、それからルーティングプリフィックスPRを得るようにmビットを切り詰めることにより、実際のルーティングプリフィックス(P0 PR)を計算することができる。プライバシードメイン内部のルータだけが、擬似プリフィックスを復号化するための鍵を有しているので、実際のプリフィックスは秘匿化されたままである。
【００６６】
以上説明してきた実施形態と同様に、ルータは、与えられた擬似プリフィックスについての上記計算結果をキャッシュあるいは保存し、各パケットについてルーティングプリフィックスを再計算することを避けることによって、ルーティング処理を高速化することができる。例えば、鍵が再設定される場合のように計算に使用される秘密が変化する場合には、このキャッシュ値は無効とされなければならない。
【００６７】
第２実施形態において、ホストは、自身のサフィックスだけでなく、自身のプリフィックスも構成することができる。これには、２つのバリエーションがある。以下、その詳細を説明する。第１のバリエーションでは、公開鍵暗号が使用される。第２のバリエーションでは、より対称的な暗号が、サフィックスの生成に使用される。これら２つのバリエーションをさらに補うこともできれば、別のバリエーションで置き換えることもできる。
【００６８】
第１のバリエーションにおいて、プライバシードメインは、公開鍵K(Public)および対応する秘密鍵K (Private)を有する。公開鍵K (Public)は、プライバシードメインの全てのホストに知られている。一方、秘密鍵K(Private)は、プライバシードメインの全てのルータにのみ知られている。
【００６９】
図１２は、公開鍵暗号を使用してプリフィックスを生成する方法を説明している。ルータは、ルータ報知メッセージを送信する（ステップ１２０２）。ルータは、自身の実際のルーティングプリフィックスPRの関数 P*R  = f (PR)である、ルーティングプリフィックスP*Rを報知する。この関数には、PR  = f-1 (P*R)となる逆関数f-1 が存在する。関数fの適用はオプションである。プライバシードメイン内部の全ルータだけがこの逆関数f-1を知っている場合に、セキュリティを向上させることができる。
【００７０】
ホストが、ルータ報知メッセージを受信する（ステップ１２０４）。ホストが、プリフィックスP*Rを暗号化し、公開鍵K(Public) およびその所望のサフィックスMi を使用して、擬似プリフィックスP`(R,i)を得る（ステップ１２０６）。擬似プリフィックスP`(R,i)とサフィックスMiとが連結されて、ホストのＩＰアドレスが生成される（ステップ１２０８）。
【００７１】
ホストiは、プライバシードメイン内外の別のホストとの通信に、ＩＰアドレス(P0， P`(R,i) Mi)を使用することができる。プライバシードメイン外部のルータがＩＰアドレス (P0， P`(R,i) Mi)を宛先とするパケットに出会うと、ルータは、プリフィックスP0によりアドレスされるサブネットアドレスに向かうリンクに、パケットをルーティングする。プライバシードメイン内部のルータがこのパケットに出会うと、このパケットについて、ルータは、実際のルーティングプリフィックス(P0 PR)を計算することができる。まず、K(Private) およびMiを使用して擬似プリフィックスP`(R,i)を復号化してP*Rを得る。次に、逆関数f-1を適用し、ルータはルーティングプリフィックスPRを得る。ルーティングプリフィックスPRおよびサフィックスMiを得て、ルータは、目的とするホストにパケットをルーティングすることができる。
【００７２】
第２の実施形態において、プライバシードメイン内部の各ホストiは、秘密鍵Kiを有している。また、プライバシードメイン内部の各ルータは、マスター鍵Kmを有しているので、秘密鍵Kiを使用して暗号化された情報を共通マスター鍵Kmにより復号化することができる。
【００７３】
図１３は、対称鍵暗号を使用してプリフィックスを生成する方法を説明している。ルータは、自身の実際のルーティングプリフィックスPRの関数 P*R = f (PR)である、ルーティングプリフィックスP*Rを生成する（ステップ１３０２）。この関数には、  PR = f-1 (P*R)となる逆関数f-1が存在する。関数f の適用はオプションである。プライバシードメイン内部の全ルータのみがこの逆関数f-1を知っている場合に、セキュリティを向上させることができる。ルータは、ルーティングプリフィックスP*Rとともに、ルータ報知メッセージを送信する（ステップ１３０４）。ルータ報知メッセージが、ホストで、受信される（ステップ１３０６）。ホストが、処理を進めて、自身の秘密鍵Kiおよび自身に選択されているサフィックスMiを使用してP*Rを暗号化する（ステップ１３０８）。この結果、擬似プリフィックスP`(R,i) が得られる。擬似ルーティングプリフィックスP`(R,i)およびサフィックスが連結されて、ホストに対するＩＰアドレスが生成される（ステップ１３１０）。
【００７４】
ホストiは、プライバシードメイン内外の別のホストとの通信用に、ＩＰアドレス(P0， P`(R,i) Mi)を使用することができる。プライバシードメイン外部のルータが、ＩＰアドレス (P0， P`(R,i) Mi)を宛先とするパケットに出会うと、ルータはプリフィックスP0でアドレスされたサブネットに向かうリンクにパケットをルーティングする。プライバシードメイン内部のルータがこのパケットに出会うと、このパケットについて、ルータは、実際のルーティングプリフィックス(P0 PR)を計算することができる。まず、マスター鍵KmおよびMiを使用して擬似プリフィックスP`(R,i)を復号化してP*Rを得る。次に、逆関数f-1を適用し、ルータはルーティングプリフィックスPRを得る。
【００７５】
以上の説明と同様に、プライバシードメイン内部のルータは、与えられた擬似プリフィックスについての上記計算結果をキャッシュあるいは保存し、各パケットについてルーティングプリフィックスを再計算することを避けることによって、ルーティング処理を高速化することができる。新しい秘密鍵がホストに割り当てられるときには、ホストのＩＰアドレスについて保存された値は削除されなければならない。同様に、マスター鍵が変更される（再設定される、re-Keyingと称する）と、キャッシュされた全ての値は削除されなければならない。
【００７６】
さらに、各ホストiが、自身のＩＰアドレスについて、通常の６４ビット長サフィックスで構成することができるという制約を導入する。このサフィックスをMiと表らわす。これが制約とならないアプリケーションもある。例えば、次のような方法である。ホストにＩＰアドレスを自動構成させる代わりに、ルータあるいはＤＨＣＰサーバが、全体のアドレスをホストに割当てる
【００７７】
次の典型的な実施形態として、擬似ＩＰアドレスあるいは別のネットワークアドレスが、復号化パラメータ（すなわち鍵）に埋め込まれている方法を説明する。この実施形態では、ホストiは新しいＩＰアドレスを構成あるいは獲得する必要がある。新しいサブネットにホストが移動するとき、新しいルータを利用できることをホストが検出するとき、あるいは、先に割当てられたＩＰアドレスが期限切れして失効したとき、このことが必要となる。この新しいルータあるいはＤＨＣＰサーバは、このホストについて完全なアドレスを割当てることになる。
【００７８】
ホストは、ルータ、ＤＨＣＰサーバ、あるいは他のアドレス割当てエンティティに、プリフィックスを要求する。ルータは、ルーティングプリフィックスPRを有する。ルータあるいはＤＨＣＰサーバは、擬似ＩＰアドレス P0 P`(R,i) Noncei を計算し、ホストに送信する。ある実施形態では、Nonceiは、このルータとともにある各ホストに固有の乱数である。Noncei を決定する別の方法で置き換えることができる。実施可能性の高いP`(R,i) を計算する方法について、以下説明する。このホストは、アドレス P0 P`(R,i) Nonceiを自身の完全なＩＰアドレスとして使用する。
【００７９】
図１４は、この実施形態にしたがう場合の典型的なＩＰアドレス１４００を説明している。ＩＰアドレス１４００は、プリフィックス１４０２およびNonce部Noncei１４０４を含んでいる。プリフィックス１４０２は、プライバシードメインサブネットプリフィックス部P0１４０６および擬似ルーティングプリフィックス部P`(R, k)１４０８を含んでいる。両部１４０６および１４０８が、Nonce部Noncei１４０４と連結されて、ＩＰアドレス１４００を構成する。
【００８０】
図１５は、図１のネットワークの、この実施形態にしたがう動作を説明する流れ図である。ここで、ホストは、自身のＩＰアドレスを再構成しようとする。ホストは、ルータ、ＤＨＣＰサーバ、あるいは他の適切なアドレス割当てエンティティに、プリフィックスを要求する（ステップ１５０２）。この要求が、ルータで受信される（ステップ１５０４）。
【００８１】
ルータは擬似ＩＰアドレスを計算する（ステップ１５０６）。ルータは、割当てられたルーティングプリフィックスPRを有する。ルータは、擬似ＩＰアドレスP0 P`(R,i) Nonceiを計算し、ホストにこの擬似ＩＰアドレスを送信する（ステップ１５０８）。ホストが、この擬似ＩＰアドレス P0 P`(R,i) Nonceiを受信し（ステップ１５１０）、このネットワークで続く通信において、この擬似ＩＰアドレスを使用する。
【００８２】
ルータは、以下のいずれかの方法あるいは同等の方法を使用して、ルーティングプリフィックスP`(R,i)を計算することができる。第１の方法では、プリフィックスのルーティングに、１１２ビット以下のy ビットのみが使用されると仮定している。この場合、（１１２−y）ビットのスペアビットがあることになる。この（１１２−y）が、例えば４８ないし６４ビットの範囲にあるように十分に大きければ、メッセージ認証コード(MAC)についてのNonceの搬送にこのスペアビットを使用することができる。このようにして、有効なルータあるいは有効な他のエンティティのみが正しいプリフィックスを計算することができる。ルータは、この割当てられたプリフィックスを数６のように計算することができる。
【００８３】
【数６】
0004417847.tif 000007
【００８４】
別の計算方法で置き換えることができる。実際のプリフィックスPRには、必要な場合でも、１８ビットまでしか必要としないことが予想され、Nonce用に９４ビットが空いている。
【００８５】
ホストiは、プライバシードメイン内外の別のホストとの通信に内外の他のホストとの通信のために、ＩＰアドレス(P0， P`(R,i) Noncei)を使用することができる。プライバシードメイン外部のルータが、ＩＰアドレス(P0， P`(R,i) Noncei)を宛先とするパケットに出会うと、ルータは、プリフィックスP0でアドレスされたサブネットに向かうリンクに、パケットをルーティングする。プライバシードメイン内部のルータがこのパケットに出会うと、このルータは、このパケットについて、ＩＰヘッダに含まれるNoncei についての鍵Kを使用することによりメッセージ認証コードを計算し、計算されたメッセージ認証コードとＩＰアドレスにさらに含まれているP`(R,i)との排他的論理和を取ることにより、実際のルーティングプリフィックス(P0 PR)を計算することができる。実際のプリフィックスが決定されると、実際のルーティングを決定するために、従来の単純なルーティングテーブル探索法が使用される。
【００８６】
第２の方法において、割当てられたプリフィックスは、実際のプリフィックスPRが暗号化されたものである。暗号化用の鍵は、Nonceiのハッシュとして計算される。ここで、Nonceiは、ルータあるいはＤＨＣＰサーバにより選択され、サブネットの各ホストについて固有であることが保証されている。プリフィックスおよび鍵は数７のようにして計算できる。
【００８７】
【数７】
0004417847.tif 000008
【００８８】
暗号化とハッシュ化は、第２および第３実施形態についてすでに説明したようなものを使用することができる。ＤＥＳ（データ暗号標準）が使用される場合は、プリフィックスPおよびP`は６４ビット長であることが期待される。これらのビットの中にはスタッフドビットも含まれる。
【００８９】
ホストiは、プライバシードメイン内外の別のホストとの通信にＩＰアドレス(P0，P`(R,i) Noncei)を使用することができる。プライバシードメイン外部のルータがＩＰアドレス(P0， P`(R,i) Noncei)を宛先とするパケットに出会うと、このルータは、プリフィックスP0でアドレスされたサブネットに向かうリンクに、このパケットをルーティングする。プライバシードメイン内部のルータがこのパケットに出会うと、このルータは、このパケットについて、まず、共有秘密とＩＰアドレスに含まれるNonceとのハッシュを使用して、鍵Kを生成することによって、実際のルーティングプリフィックス(P0 PR)を計算することができる。鍵が生成されると、ルータは、容易にP`(R,i)を復号化して、PRを得ることができる。
【００９０】
最後に、図１（Ｂ）を参照して、以上説明してきた本発明の変形を説明する。プライバシードメイン内部の全てのルータがアドレスを復号化することができなくても良い。このような場合、ある実施形態では、以下のように本発明が実行される。
【００９１】
ＩＰアドレスに、専用のビットが設けられ、残りの部分がスクランブルされているかを決定するためにこの専用のビットが使用される。現在のところルータで使用されている伝統的な最長一致基準のルーティングにより、ある実施形態では、これらの識別ビットは、プライバシードメインの共有ルーティングプリフィックスP0に後続する'n'個の最上位ビットである。したがって、これらのビットは、第２水準のプリフィックスを構成する。これらを、スクランブルされたアドレス空間におけるプリフィックスPSASと称する。この方式は、基本的にはドメインのプリフィックスP0の拡張である。スクランブル処理ができないルータは、スクランブルプリフィックスPSASを含むパケットをスクランブル処理できるルータにルーティングして、このパケットが適切にルーティングされる様にする。スクランブル処理できるルータがこのパケットを受信すると、このルータは、すでに説明したようにプリフィックスを復号化し、このパケットを別のスクランブル処理できるルータに転送する。
【００９２】
めったに起こらないことではあるが、パケットループの場合に、つまり、ルータが、転送済みのパケットに再び出会う場合、あるいは、スクランブル処理できるルータへの経路に、パケットが到着した経路以外に外部に向かう経路がない場合、スクランブル処理できるルータは、しばしば、スクランブル処理できる終局宛先ルータに、このパケットを直接トンネル転送する。このパケットは、アドレス P0PR::00にトンネル転送される。ここで、PRは、宛先ルータの復号化されたルーティングプリフィックスである。サフィックス 00 は、トンネリング転送の終点を表示している。各エッジルータは、トンネリング転送の終点用に、このサフィックスを予約している。重要なので、ここでトンネル転送されたパケットのペイロードにP`Rが含まれていることに注意を喚起する。したがって、パケットは、セキュリティの保たれていないルータあるいはリンクを通らなければならないことがあるので、P`Rを学習されてPRマッピングされることが起こり得る。したがって、セキュリティを向上させるためには、プライバシードメインの共有鍵を使用して全てのペイロードを暗号化しなければならない。もちろん、スクランブル処理できるルータは、専用のルータとしても、スクランブルされていない宛先プリフィックスを有する標準的なパケットをルーティングする標準的なルータとしても動作することができる。
【００９３】
本発明の特定の実施形態を説明してきたが、変形することが可能である。したがって、特許請求の範囲に記載の発明は、本発明の意義と範囲とに適合するような変形をも含むものとする。
【図面の簡単な説明】
【００９４】
【図１（Ａ）】図１(A)は、ネットワークを説明するブロック図である。
【図１（Ｂ）】図１(B)は、図１(A)のネットワークで使用することができる型式のルータを説明するブロック図である。
【図２】図２は、インターネットプロトコル（ＩＰ）のアドレスフォーマットを説明する図である。
【図３】図３は、図１(A)のネットワークの第１実施形態にしたがった動作を説明する流れ図である。
【図４】図４は、ホストの要求に対する応答としてルータから与えられる擬似プリフィックスを利用してホストが構成するＩＰアドレスを説明する図である。
【図５】図５は、ルーティングプリフィックスの第１実施形態にしたがった計算を説明する図である。
【図６】図６は、第２実施形態にしたがって割当てられたＩＰアドレス６００を説明する図である。
【図７】図７は、ルーティングプリフィックスの第２実施形態にしたがった計算を説明する図である。
【図８】図８は、ルーティングプリフィックスの第３実施形態にしたがった計算を説明する図である。
【図９】図９は、図１(A)のネットワークの、第２実施形態にしたがった動作を説明する流れ図である。
【図１０】図１０は、擬似プリフィックスの集合を計算する方法を説明する図である。
【図１１】図１１は、図１０の方法にしたがってホストが構成するＩＰアドレスを説明する図である。
【図１２】図１２は、公開鍵暗号を利用したプリフィックス生成方法を説明する図である。
【図１３】図１３は、対称鍵暗号を利用したプリフィックス生成方法を説明する図である。
【図１４】図１４は、本発明の一実施形態に係るＩＰアドレスを例示する図である。
【図１５】図１５は、図１(A)のネットワークの動作を説明する流れ図である。
【図１（Ａ）】
0004417847.tif 000009
【図１（Ｂ）】
0004417847.tif 000010
【図２】
0004417847.tif 000011
【図３】
0004417847.tif 000012
【図４】
0004417847.tif 000013
【図５】
0004417847.tif 000014
【図６】
0004417847.tif 000015
【図７】
0004417847.tif 000016
【図８】
0004417847.tif 000017
【図９】
0004417847.tif 000018
【図１０】
0004417847.tif 000019
【図１１】
0004417847.tif 000020
【図１２】
0004417847.tif 000021
【図１３】
0004417847.tif 000022
【図１４】
0004417847.tif 000023
【図１５】
0004417847.tif 000024