JP4464963B2 - 暗号で保護されたプレフィクスを用いたインターネットプロトコルネットワーク用のロケーションプライバシー - Google Patents

Description

（関連出願の相互参照）
本出願は、（２００３年６月２４日に出願された）仮出願第６０／４８２，３５０号及び（２００３年９月３日に出願された）仮出願第６０／５００，１５７号の利益を主張する。本出願は、これらの仮出願の開示を援用する。

本発明は、コンピュータネットワークセキュリティに関し、具体的には、潜在的な攻撃者に対して、ロケーションアドレス情報を与えない技術に関する。

ＩＰｖ６（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ ｖｅｒｓｉｏｎ ６）等のインターネットプロトコル（ＩＰ）のアドレス指定は、ユーザの地理的な位置に関する情報を明らかにすることが可能であり、ハッカーや他の敵対者に対して、ユーザの位置を突き止める及び／又はユーザの行方を追跡する能力を与える。インターネットプロトコルアドレスにおけるトポロジー上の位置は、特定の地理的な位置に対応するため、ＩＰアドレス指定においては、情報が明らかになっている。例えば、ＩＰｖ６は、（一般に、６４ビット長の）固定されたサブネットプレフィクスを用いる。サブネットプレフィクスは、ＩＰｖ６アドレスにおいて明確なテキストとして現れ、かつ、ＩＰｖ６アドレスは、送信された情報のパケットヘッダに現れるため、敵対者には、トポロジー上の位置と地理的な位置との索引を生成するのに十分なデータが提供される。従って、敵対者は、このようなデータの対応関係を利用して、ネットワークを用いて地理的な位置を特定する可能性がある。

上記の問題を扱うネットワークセキュリティの分野は、「ロケーションプライバシーセキュリティ（ｌｏｃａｔｉｏｎ ｐｒｉｖａｃｙ ｓｅｃｕｒｉｔｙ）」として知られている。ロケーションプライバシーセキュリティを扱おうとするスキームは、様々な理由で不完全である。例えば、「オニオン（Ｏｎｉｏｎ）」ルーティングとして知られているものにおいては、システムは、ネットワークの最後のホップオーバレイルータと、２つの対応するホストとの間のリンク上で、盗聴者に対して無防備である。また、オニオンルーティングは、ホスト上で実行している悪意のあるソフトウェアから、エンドホストの位置を保護しない。さらに、（インターネット技術標準化委員会（Ｉｎｔｅｒｎｅｔ Ｅｎｇｉｎｅｅｒｉｎｇ Ｔａｓｋ Ｆｏｒｃｅ、すなわち、ＩＥＴＦ）により公表されたＩＰｓｅｃ規格等の）インターネットプロトコルセキュリティの共通の形式は、オニオンルーティングと共に用いることができない。また、オニオンルーティングは、情報のルーティングに対して著しい遅延を加える。

また、「フリーダムネットワーク（Ｆｒｅｅｄｏｍ Ｎｅｔｗｏｒｋ）（ゼロナレッジ・システムズ社（Ｚｅｒｏ−Ｋｎｏｗｌｅｄｇｅ Ｓｙｓｔｅｍｓ，Ｉｎｃ．）による製品）」等のアプリケーションも、同様の理由で不完全である。例えば、フリーダムネットワークは、ホスト上で実行している悪意のあるソフトウェアから、エンドホストの位置を保護しない。さらに、フリーダムネットワークを用いたネットワークフィルタは、発信元ＩＰアドレスを変えることができないため、フリーダムネットワークは、ＩＰｓｅｃを利用するホストのロケーションプライバシーを保護することができない。また、フリーダムネットワークは、ルーティングに対して著しい遅延を加える。

ロケーションプライバシーセキュリティを実現できる最近の試みは、単一の秘密鍵を用いたＩＰアドレスの暗号化を含む（このようなシステムは、例えば、同時係属中の、共同で譲渡された米国特許出願第１０／２８４，７３９号明細書に開示されている）。しかし、単一の秘密鍵の漏洩は、敵対者が、プライバシードメイン全体にアクセスできる可能性を残したままにする可能性がある。

従って、本発明の全般的な目的は、暗号で保護されたプレフィクスを用いたインターネットプロトコルのアドレス指定の利用を通じて、ロケーションプライバシーをネットワークに提供することである。本発明は、秘密鍵が漏洩しても、及び、ルータに障害が生じても、ホスト上で実行している悪意のあるソフトウェアから、効果的にロケーションプライバシーを維持する。さらに、本発明は、盗聴者に対して、ＩＰアドレス情報を用いてユーザの地理的な位置を特定する能力を与えない。さらに、本発明は、セキュリティの耐性力及びネットワークの頑強性を提供し、ＩＰｓｅｃ及び他のセキュリティプロトコルと共に実行する場合、例えば、ＮＡＴ（Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ ｔｒａｎｓｌａｔｏｒｓ）が、エンドツーエンドのセキュリティスキームと共にうまく作動しない場合、トンネリングを伴うことなく、かつ有害な反応を伴うことなく、セキュリティの耐性力及びネットワークの頑強性を提供する。

本発明は、その構成及び動作の方法の両方に関して、以下の詳細な説明と共に解釈すれば、図１〜図２１を含む図面を参照して、より深く理解することができる。

本発明の非限定的な実施形態に関する以下の説明は、特定の構成及び構成要素を開示する。しかし、本実施形態は、本発明の単なる例に過ぎず、従って、以下に記載した特定の特徴は、単に、このような実施形態を説明し、かつ本発明の全体的な理解をもたらすために用いられるに過ぎない。

従って、当業者は、本発明が、以下に記載された特定の実施形態に限定されないことを容易に理解する。さらに、当業者に知られている本発明の様々な構成及び構成要素の説明は、明確さ及び簡潔さのために省略する。

本願明細書において、ＩＰｖ６は、インターネットプロトコルのアドレス指定の一例として用いられているが、本発明は、ＩＰｖ４や他のプロトコルにも適用できる。

本発明の例示的な実施形態は、「暗号で保護されたプレフィクス（ＣＰＰ）」を用いてＩＰアドレスを生成する。従って、ＣＰＰ ＩＰアドレスと、ホストの地理的な位置との間の対応関係は、容易に使用可能とならない。ＣＰＰを用いる場合、ＩＰアドレスは、多数のセグメントのアドレスのプレフィクスに細別される。各セグメントは、アクセスネットワークドメイン（又は、プライバシードメイン（ＰＤ）におけるルータの部分集合にのみ知られている暗号鍵を用いて暗号化される。そのため、各ルータは、情報のパケットを転送するのに必要な情報を取得するが、追加情報については取得しない。

上記ルータは、レベルと呼ばれる部分集合に細分化される。様々な実施形態において、所定のレベルに属するルータの集合は、全て、単一の暗号化秘密鍵を共用する。加えて、各ルータは、直接付加されているピアと（なお、ピアは、２つのルータがレイヤ２リンクを共用するとき、直接付加されていると考えることができる）、ユニークで動的な秘密セッション鍵を共用してもよい。第２の集合の鍵は、「リンク」鍵と呼ばれる。

インバウンドパケットが、ＣＰＰプライバシードメイン内のＣＰＰ境界ルータに到達すると、ＣＰＰ境界ルータは、当該ＣＰＰ境界ルータのレベル鍵を使用して、プレフィクスの第１の部分を解読する。この解読されたプレフィクス成分に基づいて、境界ルータは、当該パケットを、ＰＤ内の次のホップルータへ転送する。また、境界ルータは、「ホップバイホップオプション」に、上述の共有リンク鍵で暗号化された最初の解読されたプレフィクス成分を含ませる。当該次のホップルータは、当該共用リンク鍵を用いて、ホップバイホップオプションから、最初のプレフィクス成分を解読する。次いで、当該次のホップルータは、当該次のホップルータのレベルの鍵を使用して、ＣＰＰ ＩＰ宛先アドレスから、第２のプレフィクス成分を解読する。当該次のホップルータは、ホップバイホップオプションからの第１のプレフィクス成分と、レベル鍵からの第２のプレフィクス成分とを連結し、連結したプレフィクス成分を、転送するテーブルエントリに対して一致検索（マッチング）するアルゴリズムに基づいて、当該パケットを転送する。

転送されたパケットも、新たな次のホップルータと共用されるリンク鍵を用いて暗号化され、連結されたプレフィクス成分を含む新たなホップバイホップオプションを含む。このようにして、当該パケットが、宛先ホストが接続されているアクセスルータへ受け渡されるまで、宛先ＩＰアドレスのプレフィクス成分が解読される。プレフィクス全体は、アクセスルータに対して使用可能であるため、転送テーブル内のエントリとの的確な一致結果を得ることができる。従って、ＣＰＰは、ＣＰＰアドレスを生成して発行するために、及び、ルータ上の鍵を管理するのを手助けするために（これらは、本願明細書に詳細に説明されている）、アドレスサーバ及び鍵生成サーバ等のいくつかの追加サーバを必要とする。

図１は、例示的なネットワークにおけるＣＣＰを用いた「インバウンドルーティング」を示す。かかる例示的なネットワークにおいて、ＩＰアドレスは、６ビットのプレフィクスを有している（図では、６ビットが使用されているが、当業者には、どのようなビット数を有するプレフィクスも用いることができることは容易に理解でき、例えば、ＩＰｖ６ネットワークは、６４ビットのプレフィクスを用いてもよい）。各リンクには、ルートから最も遠いルータＲ１が、ルートに最も近いルータに通知するプレフィクスがラベル付けされている。例えば、Ｒ２は、プレフィクス「１０１００」をＲ１へ通知する。ユーザホストは、アクセスルータＲ５に接続されている。Ｒ５用の６ビットのプレフィクスは、「１０１００１」である。

ユーザホストは、次のようにＩＰアドレスを得る。すなわち、プレフィクス「１０１００１」は、３つのプレフィクス成分、すなわち、
「Ｐ_０＝１０１０」、
「Ｐ_１＝０」、
「Ｐ_２＝１」、
で構成されている。

「Ｐ_０」は、外界へ通知されるプレフィクス成分である。ＩＰアドレスのサフィックスは、「Ｍ」であり、「Ｍ」は、ランダムに生成される、さらに、
「Ｘ_１＝Ｈ（Ｋ_１，Ｍ） ＸＯＲ Ｐ_１」、
「Ｘ_２＝Ｈ（Ｋ_２，Ｍ） ＸＯＲ Ｐ_２」

「Ｈ（Ｋ_ｉ，Ｍ）」の最初のビット（ｉ＝１，２）は、排他的論理和関数（すなわち、ＸＯＲ）として用いられる。鍵Ｋ１は、Ｒ１に知られている秘密鍵であり、鍵「Ｋ_２」は、Ｒ２及びＲ３に知られている秘密鍵である。「Ｋ_１」及び「Ｋ_２」は、レベル鍵である。ユーザのＩＰアドレスは、「Ａｄｄｒ＝Ｐ_０，Ｘ_１，Ｘ_２，Ｍ」である（ただし、「Ａ，Ｂ」は、ストリングＡとストリングＢとの連結を示す）。

図１において、Ｒ１は、ユーザのホストに宛先が指定されているパケットを受け取る境界ルータである。Ｒ１は、鍵「Ｋ_１」を用いて、「Ｐ_１＝Ｘ_１ ＸＯＲ Ｈ（Ｋ_１，Ｍ）＝０」を計算する。次に、Ｒ１は、（「Ｐ_０＝１０１０」と「Ｐ_１＝０」とを連結することにより）プレフィクス「１０１００」を形成して、Ｒ１の転送テーブルの１０エントリ（すなわち、「１０１００」及び「１０１０１」）に対する「最長マッチ（ｌｏｎｇｅｓｔ ｍａｔｃｈ）」を行う。「１０１００」に対する一致検索に成功したため、Ｒ１は、当該パケットをＲ２へ転送する。Ｒ１は、ホップバイホップオプションに、Ｒ２と共用する鍵で暗号化されたプレフィクス「１０１００」を含ませる。Ｒ２は、ホップバイホップオプションを解読することにより「１０１００」を得る。

Ｒ２は、鍵「Ｋ_２」を用いて、「Ｐ_２＝Ｘ_２ ＸＯＲ Ｈ（Ｋ_２，Ｍ）＝１」を計算する。次に、Ｒ２は、（ホップバイホップのプレフィクス「１０１００」と「Ｐ_２＝１」とを連結することにより、）プレフィクス「１０１００１」を形成して、Ｒ２の転送テーブルの１２エントリ（すなわち、「１０１０００」及び「１０１００１」）に対する「最長マッチ」を行う。

「最長マッチ」は、「１０１００１」を生成し、Ｒ２は、当該パケットを、ホップバイホップオプションにおける暗号化されたプレフィクス「１０１００１」と共にＲ５へ転送する。Ｒ５は、的確な一致結果を得たので、「１０１００１」を解読して、当該パケットをローカルインタフェースの外のユーザホストへ転送する。

ＣＰＰによってもたらされる１つの利益は、各ルータに対して使用可能な情報の量が最少化されることである。例えば、Ｒ１は、当該パケットが、ルータＲ２をルートとするツリーの配下のホストに宛先が指定されていることを学習するのみである。そのため、Ｒ１に知られる秘密鍵の漏洩は、例えば、米国特許出願第１０／２８４，７３９号明細書に記載されているＩＰアドレスのスクランブルスキームで生じる可能性のある損失と比べて、ロケーションプライバシーの部分的な損失を発生させるのみである。

追加実施形態において、本発明は、ＣＰＰと共に、「統合（ａｇｇｒｅｇａｔｉｏｎ）」と呼ばれるものも用いる。ルータ転送テーブルにおけるエントリ数を低減するために、ルータは、いくつかの入力プレフィクスが、単一の出力プレフィクス通知に統合されるように、入力ルータ通知を統合するように構成してもよい。例えば、図１において、Ｒ２は、入力通知「１０１０００」及び「１０１００１」を取得して、かかる入力通知を単一の出力通知「１０１００」に統合する。他のルータは、「１０１００」で始まるいずれのプレフィクスもＲ２へ転送する。

統合においては、プレフィクス「Ｐ」は、２つのストリング、すなわち、「Ｐ_０」と「Ｐ_Ｓ」とで構成されている。ここで、「Ｐ_０」は、ＰＤからインターネットへ通知されるグローバルルーティングプレフィクスであり、「Ｐ_Ｓ」は、パケットをＰＤ内へ転送するのに用いられるサブネットプレフィクスである。内部のＰＤルータ内での統合は、「Ｐ_Ｓ」を細分化するのに用いられる。

一般的なルーティングの例は、「Ｇ＝（Ｖ，Ｅ）」で例示される。ここで、頂点集合「Ｖ」は、ＰＤ内のルータによって構成される。エッジ集合「Ｅ」は、ＰＤルータ間の全てのレイヤ２リンクを含む。境界ルータの１つは、ＰＤルーティンググラフのルートとして選択され、他の境界ルータは、新たなグラフ「Ｈ」を得るために、グラフから排除される。Ｄｉｊｋｓｔｒａ著の「Ａ Ｎｏｔｅ ｏｎ Ｔｗｏ Ｐｒｏｂｌｅｍｓ ｉｎ Ｃｏｎｎｅｃｔｉｏｎ ｗｉｔｈ Ｇｒａｐｈｓ，Ｎｕｍｅｒｉｓｃｈｅ Ｍａｔｈｅｍａｔｉｃ，１，ｐｐ．２６９−２７１（１９６９）」に開示されているもの等のＳＰＦ（Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）アルゴリズムが、「Ｈ」からスパニングツリー「Ｔ」を計算するのに用いられる。

統合は、既存のネットワークにおいて、転送テーブル内のエントリ数を低減するのに用いられるが、本発明の実施形態は、暗号化のためにＩＰアドレスを細分化するために、統合を用いる。ツリー「Ｔ」内のエッジの各々には、ネットワークにおいて対応するリンクに沿って流れるルーティングプロトコルのプレフィクスがラベル付けされている。図１は、このようなラベル付けの一例を示す。頂点に流れるプレフィクスの集合を仮定すると、頂点は、同じプレフィクスの集合と、当該プレフィクスの集合に属するいずれのプレフィクスも送出することができる。

別法として、頂点「ｖ」は、出力プレフィクスのうちの少なくとも１つを切り捨てることができる。例示的な実施形態において、プレフィクスは、以下の場合に切り捨てられ得る。すなわち、
（１）切り捨てられたプレフィクスが、入力プレフィクスの集合における少なくとも２つの元のプレフィクスのプレフィクス（初期サブストリング）である場合、及び
（２）切り捨てられたプレフィクスに一致する（ＩＰアドレスのプレフィクスのいくつかの初期サブストリングは、切り捨てられたストリングに的確に一致する）ＩＰアドレスにおけるプレフィクスが、頂点「ｖ」をルートとするサブツリーの外部のルータ（すなわち、他の頂点）に属していない場合。このような場合、元の集合における２つ以上の一致したプレフィクスは、出力通知プレフィクスの集合における切り捨てられたプレフィクスと置換される。この切り捨てを、統合と呼ぶ。頂点は、統合が実行される場合及び場合のみ、ツリー「Ｔ」内のレベル鍵（及び、レベルルータ）に割り当てられる。

ツリーの頂点には、次のようにレベル付けがなされている。すなわち、ツリーにおける頂点が、統合を行う場合で、かつ、ルートへのユニークなパスにおいて、当該頂点の上方で第１の統合を行っている頂点が、レベルｉを有する場合、当該頂点は、レベル（ｉ−１）を受け取る。このことは、ツリーにおけるルートからリーフまでの最長パスにおいて、アクセスルータの真上のレベルのルータが、レベル１としてラベル付けされるように取り決められている。（このことは、ルートが、レベル１を有し、かつ、番号が小さくなるにつれてレベルが増加するように、逆順で、第１の番号付けを行うことによって、取り決められる。ツリーのリーフに到達した場合で、仮に、ｄレベルが、当該ルートからリーフまでの最長パス上に割り当てられているとすると、レベルｄを有するルートにおいて再番号付けが始まる。）

そして、他の境界ルータは、レベルｄを有する頂点としてグラフに付加される。これらの他の境界ルータが、どのようにグラフに接続しているかにより、当該他の境界ルータは、それらに対する他のレベルの関係により、（レベルｄの鍵に加えて）追加のレベル鍵及び追加の構成を必要とする可能性がある。最良のケースにおいては、当該他の境界ルータは、元のルート境界ルータに必要とされる以上のどのような追加の鍵又は構成も必要としないであろう。

レベル鍵を有するルータは「レベルルータ」とみなされる。各ルータＲは、（適切な鍵設定プロトコルを介して、または、構成を介して）、当該ルータＲの「直接のピア（ｉｍｍｅｄｉａｔｅ ｐｅｅｒ）」との間で共用秘密鍵を設定する。直接のピアは、レイヤ２リンクを介してルータＲに接続されているピアである。各レベルルータは、当該レベルルータのレベルに対する鍵のコピーを有する。

かかるレベルルータは、プレフィクス成分も形成する。プレフィクス「Ｐ_Ｓ」は、上述の境界ルータと上述のアクセスルータとの間で行われる統合から得られるプレフィクス成分によって構成されている。

例えば、図２に示すように、「Ｐ_Ｓ＝Ｐ_１，…，Ｐ_Ｋ」である。ルータ２４及び２６は、統合を行うレベルルータである。２４より下の低いレベルのルータは、リンク３２を介してルータ２４まで、「Ｐ_０，Ｐ_１，…，Ｐ_ｉ，Ｐ_{（ｊ＋１，１）}」、「Ｐ_０，Ｐ_１，…，Ｐ_ｉ，Ｐ_{（ｊ＋１，２）}」及び「Ｐ_０，Ｐ_１，…，Ｐ_ｉ，Ｐ_{（ｊ＋１，ｒ）}」を通知する。そのため、ルータ２４は、通知を、その後リンク３０を介してルータ２６へ通知される「Ｐ_０，Ｐ_１，…，Ｐ_ｉ」に統合することができる。

「Ｐ_{（ｊ＋１，１）}，…，Ｐ_{（ｊ＋１，ｒ）}」は、プレフィクス成分として定義される。そして、ルータ２６も、「Ｐ_０，Ｐ_１，…，Ｐ_{（ｉ−１）}」を統合して、リンク２８を介して上方へ通知する。例えば、レベルルータ２４は、プレフィクス「Ｐ_１，…，Ｐ_ｉ」に対するターゲットであり、プレフィクス成分「Ｐ_{（ｊ＋１，１）}，…，Ｐ_{（ｊ＋１，ｒ）}」の全てを格納することができると考える。ここで、「Ｐ_{（ｊ＋１，１）}，…，Ｐ_{（ｊ＋１，ｒ）}」は、全て、考えられ得るプレフィクス成分であり、「Ｐ_０，Ｐ_１，…，Ｐ_ｊ，Ｐ_{（ｊ＋１，１）}」、「Ｐ_０，Ｐ_１，…，Ｐ_ｊ，Ｐ_{（ｊ＋１，２）}」及び「Ｐ_０，Ｐ_１，…，Ｐ_ｉ，Ｐ_{（ｊ＋１，ｒ）}」は、プレフィクスである。また、ルータは、当該ルータに転送してもよい他のプレフィックス用の追加のプレフィクス成分も格納しなければならない（上述のプライバシードメイン内の他のどこかにおけるルータ障害又はリンク障害によるものを含む）。

次の実施形態においては、レベルルータは、実際のプレフィクス成分を格納する必要はなく、代わりに、より少ない情報を格納してもよい。ルータは、解読する最長のプレフィクス成分に対応する最大長を格納してもよい。したがって、統合されたルートは、統合している頂点のサブツリーに属さなければならないので、統合の定義から考えると、それ自体が他のプレフィクス成分のプレフィクスであるプレフィクス成分がないということになる。それ故、全てのプレフィクス成分は、最大数のビットを解読し、かつ、プレフィクス成分の格納リストに対して一致検索を行うことによって、識別可能であってもよい。

全てのプレフィクス成分が、同じ長さである場合で、かつ、かかる長さについての考えられ得るストリングの全てが、プレフィクス成分である場合には、プレフィクス成分を実際に格納する必要はないが、その代わり、プレフィクス成分の長さを格納するのが適切である。かかる長さを格納することにより、当該ルータは、どのくらいのビットを解読するのかを知ることとなる。

例えば、「Ｈ」を、一方向性ハッシュ関数とする。一方向性のため、「ｘ」ではなく、「Ｈ（ｘ）」が、「Ｈ」のドメイン内のいずれかの「ｘ」に対して与えられた場合、「ｘ」を計算するのが困難であることを意味する。連結は、「｜」又は「コンマ（，）」のいずれかによって表される。ｄレベルを有する上述のルーティンググラフ「Ｇ」が与えられ、ただし、ｄレベル鍵は、「Ｋ_１，…，Ｋ_ｄ」である。鍵「Ｋ_１」は、レベルｄのルータによって共用される鍵であり、鍵「Ｋ_２」は、レベル（ｄ−１）のルータによって共用される鍵であり、…、鍵「Ｋ_ｄ」は、レベル１のルータによって共用される鍵である（レベルｄのルータは、境界ルータであり、レベル１のルータは、アクセスルータとレイヤ２リンクを共用する）。

図３は、ＩＰアドレスのプレフィクス４０からのＣＰＰ ＩＰアドレス５４の構造を示す。ここで、要素４１は、要素４０から要素５４への変換を示す。すなわち、プレフィクス「Ｐ＝Ｐ_０，Ｐ_１，…，Ｐ_Ｋ」とすると、ＣＰＰアドレスは、同じグローバルルーティングプレフィクス「Ｐ_０（４２）」を維持する。さらに、「Ｘ_ｊ＝Ｔｒｕｎｃ（Ｈ（Ｋ_ｊ，Ｍ）） ＸＯＲ Ｐ_ｊ（１≦ｊ≦ｋ）」である。ここで、「Ｔｒｕｎｃ（Ｈ（Ｋ_ｊ，Ｍ））」は、「Ｐ_ｊ」に含まれるビット数に対して切り捨てられた「Ｈ（Ｋ_ｊ，Ｍ）」を表す。

混同のおそれがない場合、単純に「Ｈ（Ｋ_ｊ，Ｍ）」と書き、「Ｔｒｕｎｃ（Ｈ（Ｋ_ｊ，Ｍ））」を意味するものとする。図３において、要素４４、４６及び４８は、それぞれ、「Ｘ_１」、「Ｘ_２」及び「Ｘ_ｋ」を示す。そして、図３の要素５４によって示されるＣＰＰアドレスは、「Ａ＝Ｐ_０，Ｘ_１，Ｘ_２，…，Ｘ_Ｋ，Ｙ，Ｍ」である。ここで、「５２（Ｍ）」は、アドレスのサフィックスであり、「４２（Ｐ_０）」は、ＰＤ用のグローバルルーティングプレフィクスであり、「５０（Ｙ）」は、内部ルーティングを最適化するのに用いられる成分である。（ＩＰｖ６の場合、「Ｐ_０」は、最初の３ビットが「０」に設定されるように取得されることができ、アドレスのプレフィクスとホスト識別子との間の境界が、６４ビット境界に該当しないことを表す。）（「Ｙ」については、以下で論じる。）

２つの追加ビット５６（「ｌ」及び「ｖ」）は、上述のアドレスについてのロケーションプライバシーが保護されているか否かについてと、現在の鍵のバージョンとを表すのに用いられる。代わりに、ルーティングドメインが、ロケーションプライバシーが保護されていないＩＰアドレスに対応する一方の「Ｐ_０」を得て、ロケーションプライバシーが保護されているアドレスに対応する他方の「Ｐ_０」を得ることを可能にしてもよい。このような代替例の場合においては、別々の１ビットは必要ではない。例えば、２つの「Ｐ_０」が、ビット０〜ビット４６に渡って同一であり、かつ、右端の（４７番目の）ビットにおいてのみ異なる場合には、プライバシードメインルータは、単に、ビット４７を検査して、ＩＰアドレスについてのロケーションプライバシーが保護されているか否かについて識別すればよい。

上述のアドレスについてのロケーションプライバシーが保護されているか否かについて識別するのに「Ｐ_０」を用いることによって、サブネット識別子の全１６ビットを、非ロケーションプライバシーＩＰアドレス用のサブネットの識別に用いることが可能になる。そうではなく、上述したような１ビットの場合には、非ロケーションプライバシーＩＰアドレスは、（６４ビット未満が、ホスト識別子に用いられない限り、）サブネットの識別用に使用可能な１５ビットを有するのみである。鍵のバージョンのビット「ｖ」は、どの鍵が、ＣＰＰ ＩＰアドレスを暗号化するのに用いられたかについて示すのに用いられる。

各ルータは、３鍵期間まで、鍵を維持してもよい。すなわち、各ルータは、「現在の鍵期間」、「直前の鍵期間」、ルータが次の鍵期間用の鍵を取得している場合に必要であれば「次の鍵期間」において、鍵を維持してもよい。図４は、鍵更新の動作と、アドレス割り当て及び鍵更新の相互作用とを示す。要素１５０は、等しい長さの別々の期間に分割されたタイムラインを示す。一つの可能性は、各鍵期間が１日続くことである。より短いまたはより長い他の期間も、セキュリティに係る必要性及び他の理由により可能である。各ルータは、次の鍵期間１５４が始まるまで、次の鍵期間用の鍵を取得しなければならない。例えば、各ルータは、現在の鍵期間１５２の後半中に、次の鍵期間用の鍵を取得してもよい。期間ｉ中に取得されたアドレスは、期間ｉ＋２（１５４）の開始前に期限が切れなければならない。期間ｉ中に発行されたアドレスは、期間ｉの鍵を用いて生成される。そのため、ルータは、鍵を有していない期間中は、有効なアドレスに出会うことはない。

上述の構造の場合、「Ｍ」は、上記レベル鍵の生存期間中、ユニークであるべきである。換言すれば、「Ｍ」は、同じレベル鍵の集合と共に、異なるＩＰアドレスの部分として再使用されるべきではない。

図５は、ＣＰＰが可能なプライバシードメインルータ（又は、単にＣＰＰルータ）が従う処理手順を示す。ＣＰＰルータは、機能１６０において開始する。ＣＰＰルータは、機能１６２において、ＣＰＰルータがＣＰＰプライバシー保護されたパケットを処理できるようにする暗号鍵を、（鍵サーバから）取得する。ＣＰＰルータは、機能１６４において、かかる暗号鍵を使用して、ＣＰＰパケットを転送する（１６４における機能は、さらに、図７に関連して本願明細書に説明されている）。ＣＰＰルータは、機能１５２において、鍵サーバから未使用の暗号鍵を得る。機能１６４において、ＣＰＰルータは、ＣＰＰパケットを転送するのを継続する。

ＣＰＰを利用した他の実施形態では、ＩＳＰルータが、インバウンドパケットを処理する。レベル（ｄ−ｊ）のルータであるルータＲ１が、「宛先ＩＰアドレス：Ａ＝Ｐ_０，Ｘ_１，Ｘ_２，…，Ｘ_Ｋ，Ｙ，Ｍ」を有するパケットを受信すると仮定する。

図６に示すように、パケットも、共用秘密リンク鍵を使用して暗号化されている「Ｐ_１，…，Ｐ_ｊ」を含むホップバイホップオプション６０を含む。図６に示すパケットの「種別」は、判断されることになっている。「長さ」は、（例えば、ＩＰｖ６によって指定された）オプションの長さから得られる。パケットの「オフセット」は、次の解読を始めるビット位置によって示されている（このフィールドは、４ビットに縮められてもよい）。「プレフィクス長」は、「暗号化されたプレフィクス」内のビット数によって示されている（「暗号化されたプレフィクス」フィールドは、考えられ得る最長のプレフィクスを収容するために、固定長であるが、当該フィールド内の全てのビットが、必ずしも送信される「暗号化プレフィクス」の一部である必要はなく、このフィールドもまた、４ビットに縮められてもよい）。従って、「暗号化プレフィクス：＝Ｈ（Ｋ，Ｍ） ＸＯＲ （Ｐ_１，…，Ｐ_ｊ）」である。ここで、「Ｋ」は、共用秘密リンク鍵である。「ターゲットレベル」は、解読すべき次のレベルである。「ターゲットレベル」が「０」の場合、プレフィクスの全てのレベルが既に解読されている。

上述の共用秘密リンク鍵は、Ｒ１と直前のホップとの間で共用される。例えば、「Ｋ」を、共用秘密リンク鍵とする。そして、「Ｈ（Ｋ，Ｍ） ＸＯＲ （Ｐ_１，…，Ｐ_ｊ）」は、ホップバイホップオプションの「暗号化プレフィクス」フィールド内に含まれる。

Ｒ１は、第１に、「ターゲットレベル」フィールド内に含まれるレベルが、Ｒ１のレベルに等しいか否かについて検査する。等しくない場合、Ｒ１は、ホップバイホップオプションからプレフィクスを得て、転送アルゴリズムに当該プレフィクスを用いる。等しい場合は、Ｒ１は、当該レベル鍵を用いて、考えられ得る最長のプレフィクス「Ｘ_{（ｊ＋１）}」を解読する。したがって、この長さは、上述したように、予め設定されている。Ｒ１は、「Ｘ_{（ｊ＋１）}」から「Ｐ_{（ｊ＋１）}」を得る（すなわち、「Ｐ_{（ｊ＋１）}＝Ｈ（Ｋ_{（ｄ−ｊ）}，Ｍ） ＸＯＲ Ｘ_{（ｊ＋１）}」）。

Ｒ１は、ホップバイホップオプションの「オフセット」フィールドによって識別されたビットで解読を開始する。ホップバイホップオプションから「Ｐ_１，…，Ｐ_ｊ」を得た後、Ｒ１は、「Ｐ_１，…，Ｐ_ｊ，Ｐ_{（ｊ＋１）}」を入力プレフィクスとして、転送アルゴリズムを用いる。例示的な実施形態においては、転送アルゴリズムから次のホップ識別を得た後に、Ｒ１が、新たなホップバイホップオプション（１）〜（４）を生成する。
（１）「暗号化されたプレフィクス」フィールドに含まれる「Ｈ（Ｋ_ｎ，Ｍ） ＸＯＲ （Ｐ_１，…，Ｐ_ｊ，Ｐ_{（ｊ＋１）}）」。ここで、「Ｋ_ｎ」は、Ｒ１が次のホップと共用する鍵である。
（２）「暗号化されたプレフィクス」の長さは、「プレフィクス長」フィールドに含まれる。「暗号化されたプレフィクス」フィールドの実際の長さは、常に１６ビットであるが、リンクを横断して送信されるプレフィクスは、より短くてもよいことに注意する。「ＩＰｓｅｃ ＡＨ」を用いることが可能なため、オプション全体の長さは、一定に保持しなければならない。
（３）解読を開始する次のビットは、「オフセット」フィールドに含まれる。
（４）現在のレベル＋１は、「ターゲットレベル」フィールドに含まれる。

本質的に、各ルータは、当該ルータのレベルに関連するプレフィクス情報を得て、かかるプレフィクス情報を用いてパケットを転送する。また、ルータは、（より上位のレベルからのプレフィクス情報と連結された）プレフィクス情報と、転送パス上の次のルータとの共用鍵で暗号化されたホップバイホップオプションにおけるオフセットとを含む。そのため、次のルータは、かかる共用鍵を用いて、より上位のレベルのルータに知られているプレフィクス部を得て、当該次のルータのレベル鍵を用いて、当該次のルータのレベルに対応するプレフィクス部を得る。これら２つのプレフィクス部の連結は、次のルータが、当該次のルータの「最長マッチ転送アルゴリズム」で用いるものである。

オプションデータは、転送中に変更してもよいので、オプション種別における３番目に高いビットは「１」である。「ＩＰｓｅｃ ＡＨ」が用いられる場合、ＩＰｖ６は、ビットがなくなる以外は、ホップバイホップオプションが、計算に含まれることを要する。そのため、ホップバイホップオプションのサイズは、プレフィクスのサイズに関係なく一定である（「暗号化されたプレフィクス」フィールドには、１６ビットを用いることができる）。

ＣＰＰは、モバイルＩＰやＨＭＩＰｖ６等の処理スキームを行う場合、オーバヘッドＩＰトンネリングを必要としない。そのため、（モバイルＩＰやＨＭＩＰｖ６を用いた場合等のように、）追加のＩＰヘッダに関連する４０バイトが節約される。

以下、本発明の転送アルゴリズムについて論じる。「ＦＷａｌｇ（）」が、既存の「最長プレフィクスマッチ転送アルゴリズム（ｌｏｎｇｅｓｔ ｐｒｅｆｉｘ ｍａｔｃｈ ｆｏｒｗａｒｄｉｎｇ ａｌｇｏｒｉｔｈｍ）」を示すものとする。ＩＰアドレスのプレフィクスの最初のサブストリングの一致検索は、転送テーブルエントリに対して行われる（ＩＰアドレスのプレフィクスの残りは、暗号化される）。従って、いくつかの一致検索が存在する可能性があり、それに伴ってアルゴリズムは、わずかな変更を必要とする。

パケットからの最初のサブストリングプレフィクスＳが、プレフィクスを、より多くのプレフィクス成分に対して一致検索することができないことを除いて、「ＦＷａｌｇ＊（）」は、「最長プレフィクスマッチングアルゴリズム」を示すものとする。換言すれば、「Ｓ」は、「Ｓ」と同数の成分を有するプレフィクス又は「Ｓ」未満の成分を有するプレフィクスのいずれかに対する一致検索に成功することができる。ここで、「Ｓ＝Ｐ_０，…，Ｐ_{（ｉ−１）}，Ｐ_ｉ」であり、「Ｐ_ｉ」は、プレフィクス成分である。従って、「Ｓ」の一致検索結果は、（最良の一致検索結果から最悪の一致検索結果の順で、）、以下の通りである。
Ｓ
Ｐ_０，…，Ｐ_{（ｉ−１）}
Ｐ_０，…，Ｐ（_ｉ−２）
Ｐ_０，…，Ｐ_{（ｉ−３）}
…
Ｐ_０

Ｐ_０，…，Ｐ_{（ｉ−１）}，Ｑ_１
Ｐ_０，…，Ｐ_{（ｉ−１）}，Ｑ_２
…
Ｐ_０，…，Ｐ_{（ｉ−１）}，Ｑ_ｋ
Ｐ_０，…，Ｐ_{（ｉ−２）}，Ｑ_１
Ｐ_０，…，Ｐ_{（ｉ−２）}，Ｑ_２
…
Ｐ_０，…，Ｐ_{（ｉ−２）}，Ｑ_ｋ
…
ここで、「｜Ｑ_１｜≦｜Ｑ_２｜≦…≦｜Ｑ_ｋ｜」であり、「Ｑ_ｉ」は、プレフィクス成分である。また、「Ｐ_０，…，Ｑ_ｉ」は、全て、レベルルータによって支配される。

さらに、ローカルインタフェースに対しては、厳密な一致検索が必要である（一致検索されるプレフィクスは、入力プレフィクスと等しくなければならない）。そのため、「Ｓ」が、転送テーブル内のローカルインタフェースのプレフィクスよりも長い場合には、「Ｓ」は、かかるプレフィクスと一致しない。また、パケットも、解読が行われない限り、当該パケットが到着したインタフェースから転送されない。より長いプレフィクスに対して一致検索することができないとしたのは、より長いプレフィクスが、次のプレフィクス成分を解読できないツリー内のより低いレベルのルータに対応するという考えからである。そのため、次のプレフィクス成分が解読される前に、パケットをより低いレベルのルータへ転送することは役に立たない。

図７は、ルータが、変形された（ＣＣＰ）転送アルゴリズムを用いてパケットを転送する本発明の実施形態を示す。プレフィクスが完全に解読されている場合、「ＦＷａｌｇ＊（）＝ＦＷａｌｇ（）」であることに注意する。図７に示すように、

である。

ＣＰＰ転送アルゴリズムの一例は、図７の要素１６４によって示される。図７の機能１９２に示すように、プライバシードメインルータは、入ってくるパケットから宛先ＩＰアドレスＡを得る。機能１９０において、アドレスＡは、それがＣＰＰアドレスであるか否かについて判断するために評価される。ＣＰＰアドレスでない場合、機能１７８は進行して、従来の転送アルゴリズムを用いてパケットが転送される。アドレスＡがＣＰＰアドレスである場合には、機能１８６は、ＡからプレフィクスＰを得る。次いで、機能１８８において、プレフィクス「Ｐ」が、「Ｐ_０」で始まっているか否かについて判断される。プレフィクス「Ｐ」が、「Ｐ_０」で始まっていない場合、パケットは、機能１８０において、境界ルータへ向けてデフォルトルートの上方へ転送される。プレフィクス「Ｐ」が、「Ｐ_０」で始まる場合には、１７０の機能が判断される。

機能１７０においては、ＣＰＰオプションがあるか否かについて判断される。ＣＰＰオプションがない場合、機能１９４は、最適化されたルーティングを利用することを要求する。ＣＰＰオプションがある場合には、機能１７２は、パケットが、現在境界ルータにあるか否かについて問い合わせる。パケットがある場合には、機能１８４は、レベル鍵を用いて最初のＰＣを解読し、ＰＣを「ＦＷａｌｇ＊（）」に入力し、それに続いて、次のホップＲが得られ、（Ｒとの）共用秘密リンク鍵を用いて、ホップバイホップオプション内でＰＣが暗号化される。そして、ホップバイホップオプションは、当該パケット内で転送される。

機能１７２において、ＣＰＰオプションがない場合、機能１７４は、共用リンク鍵を用いてホップバイホップオプションを解読し、パケットが、ホップバイホップからのターゲットレベルと等しいレベルを有するレベルルータにあるか否かについて尋ねる。かかるパケットがある場合には、機能１７６は、「Ｘ」の開始ビットにおいて開始することにより（この開始ビットは、ホップバイホップオプションから得られる）、アドレスのＸ成分から次のＰＣを解読する。次に、機能１７６は、ホップバイホップオプションのプレフィクスと新たなＰＣとを連結して、「Ｐｎｅｗ（ＮｅｘｔＨｏｐ＝ＦＷａｌｇ＊（Ｐｎｅｗ））」を得る。次いで、機能１７６は、次のホップへ転送する前に、パケットに挿入されるホップバイホップオプションにおいて共用リンク鍵を用いて「Ｐｎｅｗ」を暗号化する。最後に、機能１７６は、開始ビット及びホップバイホップオプションのターゲットレベルを更新する。

機能１７４の判断が、パケットが、ホップバイホップからのターゲットレベルに等しいレベルを有するレベルルータにないことを示す場合、機能１８２が用いられる。機能１８２は、ホップバイホップオプションからの解読されたプレフィクス（「ＦＷａｌｇ＊（）」への入力プレフィクス）を用いて当該パケットを転送し、その後、ホップバイホップオプションを用いて、次のホップとの共用リンク鍵を用いて当該プレフィクスを再暗号化する。

本発明の別の実施形態は、障害がある場合の転送アルゴリズムの復元力に対して提供する。すなわち、ルーティングリンクに障害が生じた場合には、プレフィクスが統合されるように変化する可能性がある。そのため、より低いレベルのルータは、同じレベル又はより高いレベルのルータを統合することが許されていない。この要求に対する動機は、特定のレベルのプレフィクス成分の解読が必要な場合に、より高いレベルのルータが、他のルータの転送テーブルで認識できるようにすることである。以下の証明のため、非レベルルータは、ルーティングリンクに障害が生じた場合でも、統合を行わない。

図８は、ＩＰアドレスのプレフィクスが、６ビットを有し（６ビットのうちの２ビットが、サブネット識別子用に用いられる）、転送アルゴリズムが、ある程度の数の障害がある場合を含み、パケットを当該パケットの宛先へ転送することに成功することができるＣＰＰアクセスネットワークの一例を示す。各リンクには、当該リンク上の下位のルータによって通知されるプレフィクスがラベル付けされている。例えば、ルータＲ３（要素６０）は、プレフィクス６４（「１０１０１」）を６２（ルータＲ１）に対する上方に通知する。図８においては、Ｒ３が故障することが想定される。そして、さらに、プレフィクス「１０１０１０」を有するパケットを想定する。Ｒ１は、最初のビットを解読して「１０１０１」を得る。Ｒ３が故障失敗した場合、Ｒ１の転送テーブルは、
「１０１００ Ｒ２」
「１０１０１０ Ｒ７」
「１０１０１１ Ｒ７」
「１０１０ ローカル」
になる。

これらのプレフィクスは、「１０１０１」よりも長いため、「１０１０１」は、「１０１０１０」又は「１０１０１１」に対して一致検索することができない。（このような一致検索が許されていると、パケットは、次のビットを解読できないグラフ内の下位のレベルのルータへ送られることになる。そのため、発明者らは、上述の転送アルゴリズムにおけるこのような一致検索を認めない。）

その代わりに、「１０１０１」は、（最後の「０」が除去された場合、）「１０１００」に対して一致検索する。かかるパケットは、後に解読してプレフィクス「１０１０１０」を得るルータＲ２に転送される。そして、このプレフィクスは、Ｒ２の転送テーブル：
「１０１００ ローカル」
「１０１０１０ Ｒ１」
「１０１０１１ Ｒ１」
「１０１０ Ｒ１」
「１０１０００ Ｒ４」
「１０１００１ Ｒ５」
において、当該プレフィクス自体に一致する。

そして、当該パケットは、その後、Ｒ１へ転送される。次いで、Ｒ１は、プレフィクスをＲ７に対して一致検索して、当該パケットをＲ７へ転送する。Ｒ７は、当該パケットをローカルインタフェースで転送する。こうして、当該パケットは、ルータＲ３の故障にも関わらず配信される。

本発明は、一定条件下における次の提案（Ｌｅｍｍａ４．１）によって立証されるような転送アルゴリズムの頑強性も提供する。パケットＰが、境界ルータ又はアクセスルータ（エントリポイントルータ）のいずれかを介して、プライバシードメインに到着すると仮定する。また、パケットＰが、レベル（ｉ＋１）ルータＱを通過し、当該パケットを処理する次のレベルルータＲが下方にある場合（Ｒが、Ｑと同じ接続成分にはない場合）、Ｒは、Ｑと同じ接続成分において兄弟関係のルータを有すると仮定する。ここで、兄弟関係は、Ｑの子孫でもあるレベルｉを有する別のルータとして定義される。そして、当該パケットは、転送プロセス中に、完全に解読される（全てのレベル鍵が適用され、プレフィクス全体がルータに対して使用可能になる）。

立証として、パケットＰが、境界ルータに到達すると仮定する。帰納法を用いて、プレフィクス成分「Ｐ_１，…，Ｐ_ｉ」が解読されていると仮定する。Ｐは、レベル（ｄ−ｉ）のルータへ転送されることが分かっている。Ｒ_ｉは、「Ｐ_ｉ」を解読したレベル（ｄ−ｉ＋１）のルータとする。プレフィクス「Ｐ_１，…，Ｐ_ｉ」を有するルータである元のスパニングツリーにおいて、Ｒを選択する。Ｒは、レベル（ｄ−ｉ）を有する。

ケースａ：Ｒが、上方にあり、Ｒ_ｉと同じ接続成分にある。Ｒ_ｉからＲへのパスがあり（統合が行われない場合）、最少のコストのパスを選択し、かかるパスをＡと呼ぶ。次に、「Ｐ_１，…，Ｐ_ｉ」は、かかるパスに沿った各ルータ用の転送アルゴリズムにおいて的確に一致する。そのため、Ｐは、要望通りに、Ｒへ転送されることになる。

さもなければ、Ｒ_ｉからＲへの最少の統合及びコストを伴うパスＡを選ぶ。ＲｉからＲへのパスにおいては、「Ｔ_１，…，Ｔ_ｋ」を統合を行うルータとする。そして、「Ｔ_ｉ」により通知されるプレフィクスは、「Ｔ_{（ｉ−１）}（Ｔ_０＝Ｒ_ｉ）」用の転送アルゴリズムにおいて、一致検索に成功することになる。この最後の言及は、最少の統合を伴うパスを選んだということから当然の結果である。そのため、Ｐは、要望通りに、Ｒへ転送される。

ケースｂ：Ｒは、異なる接続成分にある。仮定により、Ｒ_ｉは、Ｒと同じレベルを有するルータＴと同じ接続成分にある。そして、「Ｔ」は、「Ｐ_１…Ｐ_{（ｉ−１）}，Ｑ」を通知する。「Ｐ_１…Ｐ_{（ｉ−１）}，Ｑ」は、（Ｒ_ｉの転送テーブル内の）Ｒ_ｉに対して認識できるか、または、統合されたプレフィクス「Ｐ_１，…，Ｐ_ｊ」は、認識できる。最初のケースの場合、認識できる統合されたプレフィクスがない場合、「Ｐ_１，…，Ｐ_{（ｉ−１）}，Ｑ」が、一致検索結果する。このような一致検索は、Ｒ_ｉと「Ｔ」との間のルータのつながりにおいて継続し、その結果、「Ｔ」へ転送されるパケットＰを生じる。そして、「Ｔ」は、要望通りに、当該パケットを解読する。

ここで、統合されたプレフィクス「（Ｐ_１，…，Ｐ_ｊ）」が、Ｒ_ｉに認識できると仮定する。この最良の一致検索は、解読が行われるまで（及び、立証が完了するまで）、又は、より長いプレフィクス成分シーケンス（「Ｐ_１…Ｐ_ｋ」、ここで、「ｋ＞ｊ」）が登場するまで、続けられる。さらに、最良の一致検索は、解読が行われるまで（及び、立証が完了するまで）、又は、より長いプレフィクス成分シーケンスが登場するまで、続けられる。最後に、あるプレフィクス成分「Ｑ_１」に対して、「Ｐ_１，…，Ｐ_{（ｉ−１）}」とならなければならない。以前に対する最良の一致検索は、このプレフィクスを有するルータが、上述の転送アルゴリズムについての言及によるレベルルータであるルータに到達されるまで続けられる（このルータは、適切なレベル鍵を有する兄弟ルータである）。そのため、次の成分が解読され、立証が完了する。

さらに、パケットが、境界ルータ又はアクセスルータ（エントリポイントルータ）のいずれかを介して、上記プライバシードメインに到達すると仮定し、かつ、「（上述した）Ｌｅｍｍａ４．１」の条件を保持すると仮定する。そのため、当該パケットは、宛先のアクセスルータへ配信される。立証として、「Ｌｅｍｍａ４．１」及び既存の最長プレフィクスの特性が、ルーティングアルゴリズムに一致すると考える（プレフィクスが、一旦完全に解読されると、「ＦＷａｌｇ＊（）＝Ｆｗａｌｇ（）」）。

別の実施形態においては、統合に対する要求の１つを緩和することが可能であり、それにより、本願明細書において正規化と呼ぶプロセスにおいて、追加の統合が可能になる。追加の統合の利点には、プライバシーの向上及びルータ転送テーブルにおけるエントリの数のさらなる低減が含まれる。本実施形態において、プレフィクスの所有権についての必要条件は緩和される（この場合、所有するルータは、当該プレフィクスに対する統合を行っているルータ、或いは、当該プレフィクスと等しいＩＰアドレスを有するルータである）。すなわち、統合を行っているルータのサブツリーにおけるルータは、プレフィクスの所有権を所有する必要はない。それに伴って、統合されたプレフィクスは、スパニングツリー「Ｔ」内にないリンクを横断して通知されるルートを含んでもよく、その代わり、当該リンクは、ルーティンググラフ「Ｇ」に含まれてもよい。

図９は、プライバシードメインルーティンググラフ「Ｇ」の一部を示す正規化の一例を示す。この例もまた、プレフィクス内において限定された数のビットを用いる。しかし、リンク８０が、元のスパニングツリー「Ｔ」内に存在しないリンクであることに注意する。そのため、要素７６（ルータＲ２）が、リンク８０を受け入れた場合には、上述したような厳密な統合は起こらない。すなわち、ルータＲ２が、統合用のプレフィクス「１０１００」及び「１０１０１１」の通知を受け取るのみである場合、通常の統合である。しかし、「１０１０１０」は、ルータＲ２をルートとするサブツリーの外にあるので、ルータＲ２は、ルータＲ８からのリンク「１０１０１０」の受け入れのため、統合の通常の規則に従わないことになる。

統合の必要条件を緩和することにより、ルータＲ２は、（８０によって通知された「１０１０１０」と共に、）プレフィクス「１０１００」及び「１０１０１１」をルータＲ１における「１０１０」と統合できるようになる。そのため、要素７２（ルータＲ１）では、Ｒ１の転送テーブルにおいて、１つエントリが減ることになる。プライバシーの観点から、Ｒ１は、もはや、パケットが、８２（ルータ７）に向けられているか否かについて検出することはできなくなる。従って、ルータＲ２（要素７６）が、（要素８０に通知された「１０１０１」と共に、）プレフィクス「１０１００」及び「１０１０１１」を「１０１０」に正規化できるようにした場合、プライバシーは向上する。

本発明者等は、ルータＲ２が「１０１０」に正規化して通知できるようにすることに関して問題がある可能性があることに注目した。要素７０は、リンク７４によって「１０１０１０」を７２（ルータＲ１）に対する上方へ通知する。要素７２は、「１０１０」が意図されたプレフィクスであるかどうか、又は、「１０１０１０」を生じる２つの追加ビットの解読が意図されたプレフィクスであるかどうかについて検知することができなくてもよい。すなわち、意図されたプレフィクスは、「１０１０１１」であってもよいし、「１０１０１０」であってもよい。「１０１０１０」の解読結果は、最後の２ビットが、ルータＲ２の鍵に従って暗号化された「１０１０１１」であってもよい。この問題は、「１０１０」を「１０１００」として符号化することにより解決することができる。従って、この符号化を用いて、ルータＲ１は、２つの追加ビットを解読する（ルータＲ１は、「１０１０」をホップバイホップオプションで受け取る）。

このように、ルータＲ１が上述の解読から得るビットパターンは、「０ｘ」又は「１０」のいずれかである。ここで、「ｘ」は、「０」又は「１」とすることができる。第１のケース（「ｘ＝０」）においては、パケットは、「１０１０」をプレフィクスとして含むホップバイホップオプションを用いて、要素７６（ルータＲ２）へ転送される。ここで、符号化されたプレフィクス（「１０１００」）が送信されるのではなく、転送テーブルのプレフィクスに対応する実際のプレフィクス「１０１０」が送信される。従って、「１０１００」は、「１０１０」に対してマッピングされる。第２のケース（「ｘ＝１」）においては、パケットは、「１０１０１０」のホップバイホッププレフィクスを用いて、要素７０（ルータＲ８）へ転送される。

統合前、要素７６（ルータＲ２）は、レベルを伴わないルータであり、要素７２（ルータＲ１）は、レベル２のルータである。要素７６は、統合を行うことができるようになった後、レベル２のルータとなり、要素７２は、レベル３ルータとなる。７２より上位の全てのルータは、当該ルータのレベルを１だけ増す。要素７８（ルータＲ４）は、統合の前後において、レベル１を有している。プレフィクス成分（ＰＣ）の符号化を用いて、２つの異なるＰＣの集合が導入される。第１の集合は、上述の転送テーブル内のプレフィクスの一部である実際のＰＣである。第２の集合は、ＣＰＰアドレスにおいて暗号化されている集合である。第１の集合は、「Ｃ＿Ｒ」と設定され、第２の集合は、「Ｎ＿Ｒ」と設定されており、この符号化方法は、「正規化」と呼ばれている。

追加の統合が導入された場合、統合を行っている頂点をルートとするスパニングツリーのサブツリー内の統合を行っているルートのみに関して、統合の制約を緩和することにより、レベルが、ルーティンググラフ「Ｇ」内で生じる。レベルルータではないルータＲが、ここで１つになると仮定する。Ｒをルートとするサブツリー内のルータは、同じレベルを保持する。Ｒは、（スパニングツリー内の）Ｒの子よりも大きいレベルを有する。当該グラフ「Ｇ」内の他のレベルのルータは、全て、１だけ増加したレベルを有する。当然、統合を行っている頂点が、既にレベルルータである場合には、ルータのレベルは変化しないことに注意する。

ＰＣの正規化された集合は、各ルータに対するプレフィクスにおいて符号化されることが要求される。ＰＣの正規化された集合を用いて、ＰＣは、他のＰＣのプレフィクスとすることができない。そのため、ＰＣを解読する場合、曖昧さはない。正規化されたＰＣを解読した後、（集合「Ｎ＿Ｒ」に属する）正規化されたＰＣは、ルータＲ用のＰＣの元の集合「Ｃ＿Ｒ」内のＰＣにマッピングされ得る。

ここで、「Ｃ＿Ｒ」を、ルータＲにおけるＰＣの集合とする。ユーザホスト用のサブネットワークを識別するプレフィクスを「Ｐ」であると仮定する。「Ｐ」を、「Ｐ＝Ｐ_１｜Ｐ_２｜Ｐ_３｜…｜Ｐ_ｋ」と書くことができる。ここで、「｜」は、連結を示し、「Ｐ_１｜Ｐ_２｜…｜Ｐ_ｉ」は、（ｄ−ｉ）番目のレベルのルータ用の一致検索を行うプレフィクスである。（ｄ−ｉ）番目のレベル用の鍵を「Ｋ_ｉ」で表す。

ルータＲにおける可能性の有る「Ｐ_ｉ」の集合は、「Ｃ＿Ｒ」である。この場合、「Ｃ＿Ｒ」の正規化されたバージョンが必要である。「Ｎ＿Ｒ」は、以下に示す「Ｄｅｆｉｎｉｔｉｏｎ６．２」の特性を満たす集合である。
「Ｄｅｆｉｎｉｔｉｏｎ６．１」：ストリングＳが、ストリングＴのプレフィクスである場合、（Ｓ，Ｔ）が、プレフィクス対である。
「Ｄｅｆｉｎｉｔｉｏｎ６．２」：「Ｎ＿Ｒ」は、集合であり、全単射ｆ（全単射は、１対１及び上への関数である）は、次の特性を満たす。
- 全単射ｆ：Ｎ＿Ｒ≧Ｃ＿Ｒ
- 「Ｎ＿Ｒ」の構成員である任意の２つのストリング「Ｓ」及び「Ｔ」に対して、「Ｓ」は、「Ｔ」のプレフィクスではない。

「Ｃ＿Ｒ」が、「Ｓ」が「Ｔ」のプレフィクスであるようなストリング「Ｓ」及び「Ｔ」を有していない場合、「Ｎ＿Ｒ＝Ｃ＿Ｒ」である。さもなければ、あるストリング「Ｔ」のプレフィクスである「Ｃ＿Ｒ」におけるストリング「Ｓ」を想定する。ここで、「Ｔ」は、「Ｓ」がプレフィクスである「Ｃ＿Ｒ」における全てのストリングのうちの最短のものである。

集合「Ｅ＝｛ＳＲ：Ｒは、ストリングであり、｜ＳＲ｜＝｜Ｔ｜である｝」は、「Ｃ＿Ｒ」に含まれていない。さもなければ、「最長プレフィクスマッチルーティングアルゴリズムは」、ストリング「Ｓ」を選択しない。「｜ＳＹ｜＝｜Ｔ｜」となるように、「Ｅ」内にはない「Ｙ」を選択する。集合「Ｃ＿Ｒ」から「Ｓ」を取り除いて、「ＳＹ」を新たな集合「Ｎ１＿Ｒ」に加える。

それに応じて、第１の命題は、「Ｎ１＿Ｒ」が、「Ｃ＿Ｒ」よりも厳密に少ないプレフィクス対を含むことを提示する。第２の命題は、「Ｓ」に対する「ＳＹ」のマッピングを除いて「Ｎ１＿Ｒ」上の識別であるマッピング「ｆ１：Ｎ１＿Ｒ→Ｃ＿Ｒ」が全単射であることを提示する。第２の命題は、明白である。第１の命題は、「ＳＹ」が「Ｓ」よりも厳密に少ないストリングのプレフィクスである（「ＳＹ」は、「Ｔ」のプレフィクスではない）ため、理解される。また、「ＳＹ」のプレフィクスである任意のストリングは、「Ｓ」である、「Ｓ」のプレフィクスである、又は、「Ｓ」よりも大きいが「Ｙ」よりも小さい長さを有する。最後のケースは、「Ｔ」が、「Ｓ」が「Ｔ」のプレフィクスである最短のストリングであるため、不可能である。最初のケースは、「Ｓ」が「Ｎ１＿Ｒ」内にないため、不可能である。

（新たに生成された各集合は、直前のものよりも少ないプレフィクス対を有するので、終わらせなければならない）直前の構造は継続される。したがって、「Ｃ＿Ｒ≧Ｎ１＿Ｒ≧…≧Ｎｋ＿Ｒ＝Ｎ＿Ｒ」が得られ、「Ｎ＿Ｒ」が、「Ｎ＿Ｒ」から「Ｃ＿Ｒ」への全単射を伴う所望の集合となる。

「Ｎ＿Ｒ」は、暗号化されたプレフィクス成分のコンパクトな符号化を提供する。具体的には、各ルータは、考えられ得る最長のプレフィクスを解読することができ、その後、どのような曖昧さに対する心配も伴うことなく、一致するものを探索することができる。「Ｎ＿Ｒ」は、プレフィクス成分の符号化に用いられる。ルータは、「Ｎ＿Ｒ」のストリングを「Ｃ＿Ｒ」のストリングにマッピングして、上述の転送アルゴリズム用の適切な一致するストリングを得る（そのため、転送テーブルのエントリは、このようなマッピング及び符号化に影響を及ぼされない）。しかし、プレフィクス成分の符号化は、実際のプレフィクスよりも多少長くてもよいことに注意する。ルーティングトポロジー及びプレフィクスが、統合の量を最大化するように設定されている場合、サイズの増加の程度は、最少にされ得る、或いは、無視され得る。

本発明の別の実施形態は、最適化されたルーティングを提供する。パケットが、上記プライバシードメイン内で、アクセスルータに接続されたホストから異なるアクセスルータに接続された別のホストへ送られる場合、最適な転送パスは、境界ルータを通過するパケットを必要としない場合が多い。ＣＰＰ用の１つのパフォーマンス尺度は、ＣＰＰが用いられない場合に存在する最適な転送パスが、どの程度、ＣＰＰを用いてなお使用されているかということである。上述したアルゴリズムの場合、入ってくるパケットは、常に、境界ルータのうちの１つを通過する。

本発明においては、（１）境界ルータ上のトラヒック負荷を低減すること、及び、（２）ＣＰＰで保護された宛先アドレスを有するパケットが通過するルータの数を低減することが好ましい。上述のロケーションプライバシーが保護されたＩＰアドレスが、「Ａ＝（Ｐ_０，Ｙ，Ｘ，Ｍ）」であることを思い起こす。ここで、「Ｙ」は、イントラドメイン通信を最適化するのに利用可能である。「Ｙ」は、およそ１６〜３６ビットになると予想される（「Ｐ_０」は、３２又は４８ビットのいずれかであり、「Ｘ」は、おおよそ１６ビットである。「Ｘ」は、正規化が行われる場合、１６ビットよりも少し長くすることができることに注意する。また、「Ｙ」も、ツリー上に多数のルートがある場合には、少し長くすることができる。従って、「Ｍ」は、およそ１８〜２４ビットである）。

本発明の様々な実施形態による最適化されたルーティング用の例は、基本的な例、高度化された基本的な例、最適化された例、最適化された例の特別なサブケース、及び最適化された例の鍵ハッシュ変形例を含む。以下、これらについて論じる。

上述の基本的な例においては、「Ｙ」は、ホスト用のアクセスルータと、当該アクセスルータの親ルータとの間の共用鍵で暗号化されたＩＰアドレスのプレフィクスによって構成されている。ここで、アクセスルータは、（通常、発信元アドレスのプレフィクスを解読して調べることにより、）「イングレスフィルタリング」を行う。親ルータは、宛先アドレスを解読して、当該親ルータの子アクセスルータのうちの１つへ転送すべきか否かについてチェックすることにより、当該宛先アドレスをチェックして、（そのアクセスルータが、共通の親ルータを共用するホスト用に）限定された最適化ルーティングを可能にする。

上述の高度化された基本的な例においては、「Ｙ」は、アクセスルータの２レベル上であるルータと、当該ルータの子との間で共用される鍵で暗号化されたＩＰアドレスのプレフィクスによって構成されている。ここで、アクセスルータの親は、アクセスルータのフィルタを直接用いて、或いは、（より粗い）統合フィルタを用いて、「イングレスフィルタリング」を行う。これらのルータの両方は、それらのサブツリー内のルーティングを最適化することができる。上述の高度化された基本的な例に関しては、親又は祖父のいずれかの障害は、祖父の下の全てのホストに対するロケーションプライバシーの潜在的な損失をもたらすため、安全性は低下する。

上述の基本的な例及び高度化された基本的な例の利点は、「Ｙ」が１６ビットを要するのみなので、２つの例とも実装が容易であることである。加えて、以下にさらに説明する完全に最適化されたルーティングの例は、より大きな解読演算を必要とする。

上述の基本的な例及び高度化された基本的な例に関して、本発明者等が注目した潜在的な問題は、間違った暗号鍵が用いられた場合で、かつ、解読されたプレフィクスが、偶然に、上述の転送テーブル内のプレフィクスに一致した場合に、パケットが、間違ったルートで転送されかねないことである。このような可能性は、転送テーブル内のプレフィクスの数に依存し、プレフィクスは、単に１６ビットであるため、この可能性は、いくつかのネットワークにとってはかなり高くなり得る。

図１０は、最適化されたルーティングの例を示す。本実施形態において、内部のホストから送られたパケットは、宛先アドレスに対する最適なパスの一部であるルータに到達するまで、ルーティンググラフの上方に転送される。このルータは、「クロスオーバルータ」と呼ばれている。パケットは、このポイントで下方へルーティングされるべきである。クロスオーバルータＲは、「Ｙ」成分のセグメント（実際には、「Ｗ（ｊ，ｋ）＝Ｕ（ｊ，ｋ） ＸＯＲ Ｈ（Ｎ_ｊ，Ｍ，Ｘ_ｊ）」）に対して、（上述したように、当該クロスオーバルータＲのレベル鍵を用いて、）標準的なＸＯＲを実行して、ローカルシークレット「Ｕ（ｊ，ｋ）」を得ることにより、このパケット用のクロスオーバルータであることを識別する。結果が、当該シークレットと一致する場合、Ｒは、それがクロスオーバルータであることを知る。

その後、クロスオーバルータＲは、「Ｚ」の最初の部分（ここで、「Ｙ＝（Ｗ，Ｚ）」）を解読して、最初のプレフィクス部分を得る。次いで、Ｒは、インバウンド転送用の上述のアルゴリズムを用いて、パケットを転送する。図１０は、上述のプライバシールーティングドメイン内の９０に接続されたホストによって、同じドメイン内の９２に接続された他のホストへ送信されるパケットＰｋｔ用の最適な転送パスを示す。パケットＰｋｔは、９４を含むいくつかのルータにより、（境界ルータ９８へ向けて）デフォルトルートの上方へ転送される。ルータ９６は、「Ｗ（３，ｋ_３）」及び「Ｕ（３，ｋ_３）」を調べることにより、ルータ９６より下のサブツリー内のホストに、Ｐｋｔの宛先が指定されていることを判断した後、Ｐｋｔをシークレット「Ｕ（４，ｋ_４）」と共に、当該ルータへ転送する。従って、９６は、パケットＰｋｔ用のクロスオーバルータである。その後、Ｐｋｔは、９２に到達するまで、連続するルータにより、ツリーの下方へ転送される。

（安全性の低下という犠牲を払った）さらなる最適化として、クロスオーバシークレットは、共用リンク（ルータグラフ内のクロスリンク）上で同じレベルの他の少数のルータと共用され得る。この共用によって、これらの隣接するルータが、パケットを迅速にクロスオーバルータへ転送することができる。

上述したように、最適化されたルーティング用のＣＰＰアドレスの成分は、追加の必要条件を、ＩＰアドレス内の使用可能なビットに対して課す。図１１は、使用可能なビットに対して課された、考えられ得る必要条件を含む例示的なＩＰアドレス指定を示す。

「Ｍ」に必要とされるビット数を低減することが好ましいと考える。以下の例は、「Ｍ」が、所定のサブネット内でユニークであることを必要とするのみである。換言すれば、同じプレフィクスを有する２つのＣＰＰ ＩＰアドレスは、「Ｍ」に対して異なる値を有していなければならず、そうでない場合、２つのアドレスは、「Ｍ」に対して同じ値を有することができる。それに伴って、この以下のアルゴリズムは、「Ｍ」のサイズを約１６〜２２ビットに低減すると予想される。
上述のように、プレフィクス成分「Ｐ_０，Ｐ_１，…，Ｐ_ｋ」を有するＩＰアドレスを仮定すると、拡張されたＣＰＰ ＩＰアドレスは、「Ｐ_０，ｖ，Ｘ_１，Ｘ_２，…，Ｘ_ｋ，Ｙ，Ｍ」である。ここで、「Ｘ_ｋ＝Ｈ（Ｋ_ｋ，Ｍ，Ｐ_１，…，Ｐ_{（ｋ−１）}） ＸＯＲ Ｐ_ｋ」、「Ｘ_{（ｋ−１）}＝Ｈ（Ｋ_ｋ−１，Ｍ，Ｘ_ｋ） ＸＯＲ Ｐ_{（ｋ−１）}」、…、「Ｘ_１＝Ｈ（Ｋ_１，Ｍ，Ｘ_２） ＸＯＲ Ｐ_１」となる。

図１１は、要素１０１を用いて、ＩＰｖ６アドレスのプレフィクス１００からＣＰＰアドレス１１４への構造について示す。図１１において、「Ｚ＝Ｐ_１ ＸＯＲ Ｈ（Ｔ_２，Ｍ，Ｘ_１）｜Ｐ_２ ＸＯＲ Ｈ（Ｔ_３，Ｍ，Ｘ_２）｜…｜Ｐ_ｋ−１ ＸＯＲ Ｈ（Ｔ_ｋ，Ｍ，Ｘ_ｋ−１）」である。ここで、「Ｔ_ｉ＝ＨＭＡＣ（Ｌ_ｉ，Ｌ_１｜Ｌ_２｜…｜Ｌ_{（ｉ−１）}）、１≦ｉ≦ｋ」であり、例えば、「Ｌ_１」は、境界ルータによって配信された鍵であり、「Ｌ_２」は、次のホップルータ等により配信される。さらに、「Ｗ＝Ｈ（Ｂ（１，ｋ_１），Ｘ_１，Ｍ） ＸＯＲ Ｖ１，Ｈ（Ｂ（２，ｋ_２），Ｘ_２，Ｍ） ＸＯＲ Ｖ_２，…，Ｈ（Ｂ（ｊ，ｋ_ｊ），Ｘｊ，Ｍ） ＸＯＲ Ｖ_ｊ（完全に最適化されたスキームの鍵ハッシュ変形の場合）」であり、「Ｖ_１＝Ｈ（Ｎ_１，Ｍ，Ｘ_１）」、…、「Ｖ_{（ｋ−１）}＝Ｈ（Ｎ_{（ｋ−１）}，Ｍ，Ｘ_ｋ−１）」、「Ｖ_ｋ＝Ｈ（Ｎ_ｋ，Ｍ，Ｘ_ｋ）」である（又は、「Ｗ＝Ｕ（１，ｋ_１） ＸＯＲ Ｖ_１，Ｕ（２，ｋ_２） ＸＯＲ Ｖ_２，…，Ｕ（ｊ，ｋ_ｊ） ＸＯＲ Ｖ_ｊ」）（完全に最適化されたスキームの場合）である。

図１１において、要素１００は、真の、即ち、暗号化されていないＩＰｖ６アドレスを示す。グローバルルーティングプレフィクスは１０２である。要素１０４及び１０６は、「Ｘ_１」及び「Ｘ_ｋ」を示す。上述の「Ｘ_ｉ」の式は、異なるプレフィクス「Ｐ」を有するホストが、それらのＣＰＰアドレスにおいて同じ「Ｍ」の値を共用していても、当該ホストに関連する「Ｘ」を持たせない。

「Ｎ_１，…，Ｎ_ｄ」を、レベル鍵の第２の集合とする。これらは、対の別個の秘密鍵である。当該レベルに属する全てのルータは、各レベル鍵を共用する。次のハッシュ式は、以下のように短縮される。
「Ｖ_１＝Ｈ（Ｎ_１，Ｍ，Ｘ_１）」
…
「Ｖ_{（ｋ−１）}＝Ｈ（Ｎ_{（ｋ−１）１}，Ｍ，Ｘ_ｋ−１）」
「Ｖ_ｋ＝Ｈ（Ｎ_ｋ，Ｍ，Ｘ_ｋ）」

レベル（ｄ＋１−ｊ）のルータの番号は、「１」で始まる。クロスオーバシークレット「Ｕ（ｊ，ｋ）」は、レベル（ｄ＋１−ｊ）のｋ番目のルータ及び鍵サーバのみに知られているシークレットである。「（レベルｊにおける）Ｕ（ｊ，ｋ）」は、対で別個であるため、必要なビット数は、レベル（ｄ＋１−ｊ）のルータの数の底２の対数に等しい。アクセスルータの真上のレベルで始めると、必要なビット数が確保される。「Ｕ（ｊ，ｋ）」に必要な総ビット数は、「ｊ」を越えるレベル（ｄ＋１−ｊ）の番号のルータの底２の対数の合計に等しい。典型的には、ルータの最大数は、アクセスルータのレベルの真上にある。

インターネットからのパケットＰ用の最適なパスが、シークレット「Ｕ（１，ｋ_１），Ｕ（２，ｋ_２），…，Ｕ（ｊ，ｋ_ｊ）」を有するレベルルータを含む。そこで、ＩＰアドレスの「Ｗ」成分は、「Ｗ（ｉ，ｋ）＝Ｕ（ｉ，ｋ） ＸＯＲ Ｖ_ｉ（ここで、「Ｍ」は、上述したサフィックスであり、「Ｖ_ｉ」は、上記で定義した鍵であり、最適なパスは、レベル（ｄ＋１−ｊ）のｋ番目のルータを含む）。ＩＰアドレスは、「Ａ＝（Ｐ_０，Ｘ，Ｙ，Ｍ）」である。ここで、「Ｐ_０」、「Ｘ」及び「Ｍ」は、上述したようなものであり、「Ｙ＝（Ｗ，Ｚ）」であり、「Ｗ＝Ｕ（１，ｋ_１） ＸＯＲ Ｖ_１，Ｕ（２，ｋ_２） ＸＯＲ Ｖ_２，…，Ｕ（ｊ，ｋ_ｊ） ＸＯＲ Ｖ_ｊ」である。

図１１の要素１０８は、「Ｗ」を示す。鍵バージョンビット「ｖ」は、要素１１６として示されている（例えば、ルーティングドメインが、ロケーションプライバシーが保護されたアドレス及びロケーションアドレスが保護されていないアドレス用の別々のグローバルルーティング識別子を得ている場合、必要ではないため、かかる１ビットは、示されていない）。レベル（ｄ＋１−ｊ）のｋ番目のルータは、ＩＰアドレスＡと等しい宛先アドレスを有するパケットが一般に通過するルータである（当然、そうでない場合、この場合の最適化に影響を及ぼす可能性がある）。

図１１は、さらに、拡張されたＣＰＰ ＩＰアドレスを示す。上述の「Ｗ」についての式において、境界ルータと、ホストの最初のホップルータとの間のレベルルータの数は、認識され得る（各レベルのクロスオーバシークレットは、レベルにより固定長を有する）。スパニングツリーにおける境界ルータからアクセスルータへの全てのパスが等しい長さであれば、このことは問題ではない。さもなければ、下位のレベルに対するどのルータにも対応しない追加のクロスオーバシークレットを用いることが好ましい。それらを「Ｗ」についての式に加えることにより、情報漏れは、次のようになくなる。
「Ｖ_１＝Ｈ（Ｎ_１，Ｍ，Ｘ_１）」
…
「Ｖ_{（ｋ−１）}＝Ｈ（Ｎ_{（ｋ−１）}，Ｍ，Ｘ_ｋ−１）」
「Ｖ_ｋ＝Ｈ（Ｎ_ｋ，Ｍ，Ｘ_ｋ）」
「Ｖ_{（ｋ＋１）}＝Ｈ（Ｎ_{（ｋ＋１）}，Ｍ，Ｘ_１）」
…
「Ｖ_ｄ＝Ｈ（Ｎ_ｄ，Ｍ，Ｘ_{（ｄ ｍｏｄ ｋ）}）」
「Ｗ＝Ｕ（１，ｋ_１） ＸＯＲ Ｖ_１，Ｕ（２，ｋ_２） ＸＯＲ Ｖ_２，…，Ｕ（ｄ，ｋ_ｄ） ＸＯＲ Ｖ_ｄ」

全てのレベルルータは、全てのレベルに対するクロスオーバシークレットの長さをもって構成されている。各レベルには、正確な１つの長さがある。別法として、「Ｕ」が、ルーティンググラフにおける少数のレベル用のルーティングを最適化することにのみ用いられる場合には、特別のシークレットに対応する特別の「Ｗ_{（ｊ，ｋ）}」に加える必要はない。一実施形態において、特別の「Ｗ_{（ｊ，ｋ）}」は、結果として生じるツリーが完全にバランスが取れるように、すなわち、境界ルータのルートからアクセスルータへの全ての経路が（「Ｗ_{（ｊ，ｋ）}」によってモデル化されたスパニングツリー用の）同じ長さを有する。このアプローチの場合、ルータにとっては、当該ルータのレベルに対応する「Ｗ_{（ｊ，ｋ）}」成分を見つけるのは簡単なことでもある、すなわち、当該ルータのレベルは、「Ｗ」成分中の同じ位置に常に現れる。

本発明におけるＩＰアドレスの「Ｙ」成分が、「Ｚ」成分を含んでもよいことを思い起こしてほしい。「Ｚ」成分を伴う実施形態の説明を続ける（「Ｚ」は、図１１において、要素１１０として示されている）。各レベルルータは、サブツリー内の当該レベルルータ配下の全ルータとの間で、秘密鍵Ｌを共用する。ここで、当該サブツリーは、当該共用リンク上のルータをルートとしている。元のスパニングツリーにおいて、レベルルータは、子ルータの集合を有する。レベルルータは、各子ルータをルートとするサブツリーの各々との間で、別々の秘密鍵を共用する。成分「Ｚ」は、１４〜１６ビットであり、上述したようにプレフィクス成分に分割されるサブネットプレフィクスからなる。この場合、各成分は、秘密鍵「Ｔ」を用いて暗号化される。

各秘密鍵「Ｔ」は、現在のレベルルータ及び当該現在のレベルルータの上方にあるレベルルータからの秘密鍵「Ｌ」から得られる。そのため、所定のレベルのルータＲは、より高いレベルに対応する「Ｚ」におけるプレフィクス成分を解読することにより、所定のレベルのルータＲの上方にあるレベルルータからプレフィクスを得ることができ、各レベルルータは、当該レベルルータ自体の直接上のレベルからの全ての鍵「Ｌ」を有する。しかし、このことは、Ｒが、パケット用の最適なパス上にある場合にのみ可能であり、それによってセキュリティが維持される（「Ｚ」成分は、ツリー内のいくつかの他のルータに、ＩＰアドレスのロケーションに関する情報を漏らしてもよいことに注意する）。

プレフィクス成分「Ｐ_ｉ」は、鍵「Ｔ_ｉ＝ＨＭＡＣ（Ｌ_ｉ，Ｌ_１｜Ｌ_２｜…｜Ｌ_{（ｉ−１）}）：Ｚ_ｉ＝Ｐ_ｉ ＸＯＲ Ｈ（Ｔ_{（ｉ＋１）}，Ｍ，Ｘ_ｉ）、（２≦ｉ≦ｋ）」を用いて暗号化される。ここで、例えば、「Ｌ_１」は、境界ルータによって配信される鍵であり、「Ｌ_２」は、次のホップルータによって配信される。「ＨＭＡＣ」の式において、「ＨＭＡＣ秘密鍵」として用いられる「Ｌ_ｉ」及び「Ｌ_１｜Ｌ_２｜…｜Ｌ_{（ｉ−１）}」は、「テキスト」である。

「Ｋ_ｉ」に対しては、他の構造が考えられ得る。「ＴＬＳ ＲＦＣ」や様々な暗号の論文は、いくつかの鍵を１つの鍵に結合する方法を記述している。
「Ｚ＝Ｐ_１ ＸＯＲ Ｈ（Ｔ_２，Ｍ，Ｘ_１）｜Ｐ_２ ＸＯＲ Ｈ（Ｔ_３，Ｍ，Ｘ_２）｜…｜Ｐ_ｋ−１ ＸＯＲ Ｈ（Ｔ_ｋ，Ｍ，Ｘ_ｋ−１）」
レベル（ｄ−ｋ＋１）のルータが、「Ｘ」から「Ｐ_ｋ」を得ることができるため、「Ｚ」の最後の成分は必要ではない。

ルータは、一般に、次の方法で、入ってくるパケットを転送する。第１に、当該ルータは、宛先アドレスの「Ｐ_０」プレフィクスビットをチェックして、当該パケットが、内部アドレス向けのものであるか否かについて判断する。内部アドレス向けのものでない場合、当該ルータは、当該パケットを、デフォルトルートを用いて、トップレベルのルータへ向けてルーティングする。内部アドレス向けのものである場合、及び、ＣＰＰホップバイホップオプションがない場合には、当該ルータは、当該ルータのレベルに従って、「Ｗ」成分をチェックする。この情報は、他の転送テーブル情報と共に予め構成される。当該ルータは、クロスオーバルータではない場合、当該パケットを、デフォルトルートを用いて、境界ルータへ向けて転送する。

しかしながら、ルータＲが、当該パケット用のクロスオーバルータであると仮定する。このとき、Ｒは、（境界ルータに対応する）「Ｚ」における最初のレベル成分で開始する。かかる成分は、「Ｐ_１ ＸＯＲ （Ｔ_２，Ｍ，Ｘ_１）」である。Ｒは、クロスオーバルータであるため、「Ｌ_１」及び「Ｌ_２」に対する正確な値を有するので、鍵「Ｔ_２」を計算することができる（Ｒは、直前のインバウンドルーティングアルゴリズムが用いられていなければ、境界ルータではない）。そのため、Ｒは、「Ｐ_１」を得ることができる。同様に、Ｒは、上述のツリーにおいてＲ自体よりも高いレベルに対応する他のＰＣを得ることができる。最後に、Ｒは、インバウンドルーティングアルゴリズムを用いて、Ｒ自体のレベルに対するプレフィクス成分を得る。Ｒは、連結されたプレフィクスを取得して、当該プレフィクスに基づいてパケットを転送する。また、Ｒは、当該連結されたプレフィクスを含むホップバイホップオプションも含む。Ｒは、境界ルータに近いツリーにおけるレベルに対するプレフィクス成分を解読するので、他のルータに対する最大ＰＣ長、及び、（他のルータに対して）考えられ得るＰＣを用いて構成される必要がある（また、正規化を用いる場合、Ｒは、他のルータ用の正規化マップも有することが必要となる）。

従って、このアルゴリズムを用いた場合、上述の最大ＰＣ長の全てのストリングが、ＰＣ自体である場合には、構成の量を低減することが有利である。理想的には、全てのＰＣも、所定のルータに対して、最大ＰＣ長を有する。所定のレベルにおける全てのルータも同じ最大ＰＣ長を有している場合、このことは、必要な構成の量をさらに低減することになる。例えば、レベル１のルータＲは、次のようにして、「Ｕ（１，ｋ_１） ＸＯＲ Ｖ_１」をチェックする。
- 「Ｖ_１」及び「Ｂ＝Ｗ（１，ｋ_１） ＸＯＲ Ｖ_１」を計算する。
- そして、ターゲットホストがＲより下のアクセスルータに属していれば、「Ｂ」は「Ｕ（１，ｋ_１）」である。

統合を行わないルータは、入ってくるパケットを、デフォルトルートを用いて、ルーティンググラフの上方へ転送する。（レベル鍵を有する）レベルルータだけが、内部ＩＰアドレスに宛先が指定された最適パケットをルーティングする。

図１に関連して論じたような次の例について考える。サブネットのプレフィクス符号化「Ｘ」に対して２ビットが要求される。２ビットは、「Ｚ」に対して必要となる。１ビットは、「Ｗ」に必要である。インターネットから、Ｒ５に接続されたホストへ送信されたパケットは、Ｒ１、Ｒ２及びＲ５を通過することになる。Ｒ２に属するシークレット「Ｕ（１，２）」が、１ビットからなるものとする。そして、Ｒ３に属するシークレット「Ｕ（１，３）」が反対の値を有するものとする（Ｒ２は、この特別なケースにおいて、ルータＲ３のシークレットの値を導出するが、ＩＰアドレスのロケーションに関する追加の情報は与えないことに注意する。換言すれば、かかるＩＰアドレスは、Ｒ２の配下にない場合、Ｒ３の配下になければならない）。従って、この場合、「Ｗ」は、単一のビットを有する単一の成分からなる。

Ｒ４からＲ５へ送信されたパケットは、Ｒ２へ転送されることになる。そして、Ｒ２は、「Ｙ」をチェックして、Ｒ２のシークレットとの一致結果を得る。一致結果を得た後、Ｒ２は、当該パケットは、上述のグラフのより下位のレベルへ転送されるべきであることを知る。Ｒ２は、宛先アドレス内の「Ｚ」における２つの成分を解読して、サブネットプレフィクス「０１（Ｐ_１＝０，Ｐ_２＝１）」を得て、このサブネットプレフィクスに基づいて当該パケットをＲ５へルーティングする。

本発明の例示的な最適化されたシステムにおけるＩＰアドレス成分の例示的なサイズは、次の通りである。ＩＰアドレスＡは、フォーム「Ａ＝（Ｐ_０，ｖ，Ｘ，Ｗ，Ｚ，Ｍ）」からなる。

「Ｗ」に必要なビット数は、「Ｘ」に必要なビット数よりも多い。これは、ｄレベルを有するバイナリツリーであるルーティンググラフのケースでは、「Ｗ」に必要なビット数は、各レベルにおけるビット数の対数の合計であることから明らかである。従って、

別の表現では、

限定された数のレベル（４−５）の場合、必要な追加ビット数は、それほど多くはない。例えば、レベル４に１個のルータ、レベル３に８個のルータ、レベル２に６４個のルータ、レベル１に１２８個のルータ及び５１２個のアクセスルータが存在するルーティングツリーの場合、「Ｗ」は、１６ビットを必要とするのに対して、「Ｘ」は、１２ビットを必要とする。「Ｗ」のビット数が、（「Ｍ」のサイズによって決まる）必要とされるＩＰアドレスの数により限定されなければならない場合、１つの選択肢は、上述のグラフ中の最下位のレベルに対してのみ、ルート最適化を用いることである。

上述したように、「Ｘ」は、１６〜１８ビットを有する（正規化を用いる場合、Ｘは、１６ビットよりも長い）。「Ｗ」は、クロスオーバシークレットを含む。「Ｗ」に対しては、２６ビットで十分であると仮定する。１ビットは、鍵のバージョンを表すのに用いられる。１ビットは、（独立したグローバルプレフィクス「Ｐ_０」が、ロケーションプライバシーアドレスを識別するのに用いられる場合に不要とされ得る）ロケーションプライバシーバージョンを表すのに用いられ得る。「Ｐ_０」は、４８ビットを要してもよい。「Ｚ」が１４ビットを含むと仮定する。従って、「Ｍ」に割り当てるために、アドレス割当サーバには、２０ビットが残る。同じプレフィクスを有する２つの異なるＩＰアドレスは、同じ「Ｍ」成分を有するべきではない。

完全に最適化されたルーティングの例に関する特別なサブケースは、いくつかのアクセスネットワークに対して、改善されたパフォーマンス及びセキュリティ特性をもたらす。本発明を利用するネットワークは、可能であれば、この特別なサブケースを利用できるようにするように構成することが推奨される。この例においては、「Ｙ＝Ｗ」である。換言すれば、「Ｚ」成分は、ＩＰアドレス中には存在しない。そのため、（「Ｚ」が用いられないため、）「Ｚ」に関連する約１４ビットが節約される。上述したように、「Ｚ」は、ＩＰアドレスのロケーションに関するいくつかの情報を（プライバシードメイン内のルータへ）漏らすかもしれない。従って、「Ｚ」を取り除くことも、セキュリティの利益をもたらす。

「Ｙ＝Ｗ」である特別なサブケースにおいて、ルータは、プライバシードメイン内のアドレスに宛先が指定されたパケットを転送する場合、「Ｗ」を用いて、当該ルータがクロスオーバルータであるか否かについてチェックする。当該ルータは、クロスオーバルータでない場合、（以下に説明するように、ホップバイホップオプションをつけた後、）当該パケットをデフォルトルートの上方へ転送する。当該ルータは、クロスオーバルータである場合には、当該ルータのレベルに応じて、「Ｘ」成分を解読する。クロスオーバルータは、常に、当該クロスオーバルータのレベルに従って、単一の「Ｘ」成分に基づいてパケットを転送することができるため、かかる特別なケースが発生する。

ホップバイホップオプションは、解読を終了するビットを表すのに用いられる。各ルータは、「Ｘ」成分に関して、ホップバイホップオプションのオフセットフィールドを用いて、次のホップが、解読を終了させるビットを表す。また、他のＰＣのサフィックスであるＰＣはないので、ルータは、（最後のビットが終了ビットに等しい）最大サイズのＰＣを解読した後、当該ルータのＰＣのリストを探索して正確なＰＣを得ることができる。（本願明細書中において、以後、「ＯＲホップバイホップオプション」と呼ぶ）ホップバイホップオプションは、「暗号化されたプレフィクス」フィールドを有せず、かつ、「ターゲットレベル」フィールドが、１バイトの「インバウンドルーティングインジケータ」フィールドと置換され、長さが４バイトであることを除いて、上述のＣＰＰホップバイホップオプションと同じフォーマットを有する。上述の特別なサブケースについて、上述のグラフ内の全ルータが、レベルルータであり、また、ルータが、当該ルータのレイヤ２リンクピアの各々のレベルを維持すると仮定する。

上述の最適化されたルーティング状態を用いる場合、ルータは、常に、「インバウンドルーティングインジケータ」が「０」に等しい場合、当該ルータ自体のレベルに「１」を加えたレベルを有するルータにパケットを転送し、「インバウンドルーティングインジケータ」が「１」に等しい場合、当該ルータ自体のレベルから「１」を引いたレベルを有するルータにパケットを転送する（図７は、ルータが、（パケットに「ＯＲホップバイホップオプション」がない場合に対応する）最適化されたルーティング状態にどのように入るかについて示す）。また、「ＯＲホップバイホップオプション」を有するパケットを受け取るルータは、最適化されたルーティング状態にある。

上述の完全に最適化されたスキーム及び最適化されたルーティングに対する鍵ハッシュ変形スキームとは異なって、クロスオーバルータが一旦決まると、上述のインバウンドルーティングアルゴリズムは用いられない。これは、パケットが、宛先のアクセスルータに到達するまで、各処理ルータによって、当該パケット内で、「ＯＲホップバイホップオプション」が、新たな「ＯＲホップバイホップオプション」に置換され続けられるためである。違いは、クロスオーバルータが、自身がクロスオーバルータであると判断したときに従う「ＯＲホップバイホップオプション」において、「１」に等しい「インバウンドルーティングインジケータ（ＩＲＩ）」を設定することである。後続の全てのルータも、「ＩＲＩ」を「１」に設定する。重要なことは、「ＩＲＩ」フィールドが、「１」に等しい場合、解読用の終了ビットが、解読用の開始ビットになることである。
上記クロスオーバルータの前に、上記ＩＲＩが０に設定される。ルータがクロスオーバルータではない場合でも、ルータは、ホップバイホップオプションにオフセットフィールドを含んでいなければならない。そのため、ルータは、次のレベルのルータのためのエンディング解読ビットを得るために、当該ルータのレベルに対する対応するＸ成分を解読しなければならない。

上述のクロスオーバルータの前に、「ＩＲＩ」が「０」に設定される。ルータが、クロスオーバルータではない場合であっても、当該ルータは、ホップバイホップオプションに「オフセット」フィールドを含んでいなければならない。そのため、ルータは、次のレベルルータ用の終了解読ビットを得るために、当該ルータのレベルに対して対応する「Ｘ」成分を解読しなければならない。

図１２は、最適なルーティングの追加の実施形態を示す。本実施形態において、各ルータは、当該ルータ及びアドレス生成サーバ（アドレス生成については、図１４に関連して以下に論じる）にのみ知られている固有鍵「Ｋ_ｒ」を有して構成される。

（図１２において、）最適なルーティングを示す追加の実施形態において、内部ホストから送られたパケットは、宛先アドレス用の最適なパスの一部であるルータに到達するまで、ルーティンググラフの上方へ転送される。かかるルータは、クロスオーバルータＲ（要素７ｂ９６として示す）と呼ばれる。パケットは、このポイントで下方へルーティングされる。

クロスオーバルータＲは、パケットのサフィックス「Ｍ」、又は、当該サフィックスの一部に対して標準的なハッシュ処理を施して、特定のビットを切り捨てることにより、自身が当該パケット用のクロスオーバルータであることを識別する。そして、当該ルータは、ハッシュ処理の結果と、「０」等の所定の値とを比較する。別法として、アドレス内の特定のビットは、所定値を含むリストに対するインデックス等の特定の値へのポインタ用に確保されていてもよい。かかる特定の値と、ハッシュ及び切り捨ての結果とが同じである場合、当該ルータは、自身がクロスオーバルータであることを知る。ハッシュ及び切り捨ての例は、以下の通りである。

上述のケースが「真」である場合、ルータは、単に、図１３に示すわずかな追加を伴って、図１０に関連して説明した最適化されたルーティングプロセスに従う。

図１３は、図１２に関連して最初に説明したような最適なルーティングの変形例について更に説明するフローチャートである。初めからツリー内の上方へ向けられている任意のパケットは、予め解読された（すなわち、より高いレベルのルータによって予め解読された）プレフィクスを示すホップバイホップオプションを含むことはない。従って、このことは、クロスオーバルータを、解読されたより高いレベルのプレフィクスを有しない場合の境界ルータと同様の状況にする。

ルータは、当該ルータのレベル鍵を用いて、当該ルータのレベルに応じて、解読したプレフィクス成分を得て、解読されたプレフィクス成分を、予め構成されたより高いレベルのプレフィクスに連結する。このより高いレベルのプレフィクスは、全てのより高いレベルの解読されたプレフィクスの連結である。この連結は、ルータが、パケットが転送されなければならない次のより低いレベルのルータを見つけ出せるように、クロスオーバルータに対して、当該クロスオーバルータのルーティングテーブル内で「最長プレフィクスマッチ」を実行するための十分長いプレフィクスを与える。次のホップルータが一旦決定されると、当該クロスオーバルータは、以下のうちの１つを用いてもよい。

ケース１：クロスオーバルータは、パケットを、（図１２に示す７ｂ１００のような）次のホップルータへ転送し、当該次のホップルータのホップバイホップヘッダに、新たに形成された連結プレフィクスを含ませる。ここで、ホップバイホップヘッダは、次のホップルータと共用する鍵を用いて状況に応じて暗号化されてもよい。この場合、次のホップルータは、ホップバイホップオプションを含む他のパケットのように、このパケットを処理することができる。

ケース２：クロスオーバルータは、パケットを次のホップルータへ転送し、ホップバイホップヘッダに、新たに形成された連結プレフィクスを含ませない。この場合、受信ルータは、再び、上述したハッシュ及び切り捨て演算を実行して、当該受信ルータがクロスオーバルータであるか否かについて同様に判断する。この新たなタイプのアドレス指定を用いて、当該ルータは、（当該ルータのレベルに対応するプレフィクス成分を解読し、より高いレベルのプレフィクスの解読された連結と連結することにより）プレフィクスを再生し、当該ルータのルーティングテーブルにおける「最長プレフィクスマッチ」を行い、次のホップルータを見つけ出すことができる（ケース２は、図１２には示していないことに注意する。また、ルータは、アクセスルータの真上のレベルにあるルータである場合には、ケース２を選んではいけない）。

パケットを正確にルーティングすることができる図１３の例示的な実施形態のルータについては、宛先アドレスは、次の条件に従うことになる。

アクセスルータＡＲへルーティングされるアドレスのサフィックス「Ｍ」は、アクセスルータＡＲと境界ルータＢＲとの間の所望のパス又は最適なパス上の全ルータＲ用のものであり、

である。

ここで、「Ｌ」は、ルータ「ｒ」のレベルである。「ＴＲＵＮＣＡＴＥ（ＮＵＭＢＥＲ，Ｌ）」は、「ＮＵＭＢＥＲ」を、レベル「Ｌ」に対応する所望のビット数に切り捨てる。一般的には、「Ｌ」に対応するビット数は、レベル「Ｌ」におけるルータの数のｌｏｇ２について切り上げて整数化された数である。「Ｔａｂｌｅ-Ｌ」で示される独立したテーブルが、各レベル「Ｌ」に対して維持されていてもよい。「Ｋ_ｒ」は、ルータ「ｒ」の固有鍵である。この鍵は、一般に、上述したレベル鍵やリンク鍵とは異なる。これらの鍵は、他の鍵のようにバージョン化されていてもよい。本出願の他の箇所で説明したような「鍵のバージョン化方法」を適用してもよい。

次に、例えば、図１２に関連して上述したようなネットワークに有用なアドレス生成サーバについて考える。サフィックス「Ｍ」のアドレスは、以下の事象が「真」である場合、アクセスルータ７ｂ９２に属することができる。

ここで、「Ｖａｌｕｅ１」、「Ｖａｌｕｅ２」及び「Ｖａｌｕｅ３」は、それぞれ、「７ｂ９６」がレベル１に属し、「７ｂ１０４」及び「７ｂ１００」がレベル２に属し、「７ｂ９４」及び「７ｂ１０２」がレベル３に属すると仮定した場合のレベル１、レベル２及びレベル３における所望の値である。「Ｋｅｙ７ｂ９４」、「Ｋｅｙ７ｂ９６」、「Ｋｅｙ７ｂ１００」、「Ｋｅｙ７ｂ１０２」及び「Ｋｅｙ７ｂ１０４」は、それぞれ、ルータ７ｂ９４、７ｂ９６、７ｂ１００、７ｎ１０２及び７ｂ１０４の固有秘密鍵である。

「Ｍ」についての直前の状況を考慮し、かつ、アドレス生成サーバが、ネットワークトポロジー及び当該ネットワークにおけるルータの各々の固有秘密鍵を認識していると仮定すると、当該アドレス生成サーバは、各アクセスルータ用のクロスオーバルータを決めることができ、当該クロスオーバルータと当該アクセスルータとの間の対応するパスを見つけ出すことができ、かつ、上述したように、「Ｍ」の集合を計算することができる。次いで、当該アドレス生成サーバは、かかる「Ｍ」集合を、暗号化したプレフィクスと「Ｐ_０」との連結に連結して、完全なアドレスを形成する。そして、これらのアドレスは、当該アクセスルータの１つ上のレベルのルータに格納される（或いは、別法として、これらのアドレスは、当該アクセスルータに格納されてもよい）。

図１４は、アドレス生成サーバによるアドレス生成の例示的なプロセスを示す。当該アドレスサーバは、（機能２２３６及び機能２２０２に示すように、）適切なプレフィクスを見つけ出すことができる前に、アドレス空間集合「Ｓ」及びルータＲの集合（及び、関連するルータトポロジー情報）を知らなければならない。一旦、前の情報が分かると、当該アドレスサーバは、（機能２２０４に示すように、）一度に、集合「Ｓ」から１つの「Ｍ」を取り出して、取り出した「Ｍ」が、ルータのいずれかにとって適切であるか否かについて判断する。

機能２２０８において、当該アドレス生成サーバは、上述の集合からルータ「ｒ」を取り出して、「ｒ」用のクロスオーバルータの集合を見つけ出す。かかる集合を、集合「Ｐ」と呼ぶ。さらに、「ｒ」用のクロスオーバルータとは考えられないルータの集合「Ｑ」は、機能２２１２において見つけ出される。

多値変数が用いられるか否かにより、考えられ得る値「ｖ」の集合「Ｖ」が、機能２２１６において計算される。多値変数が用いられない場合、かかる集合は、ちょうど１つの要素を有することになる。さらに、機能２２１６において、アドレス生成サーバは、一度に、１つの値「ｖ」を取り出して、機能２２１８、２２２０及び２２２６に示すように、「Ｐ」における全てのルータに対して、「Ｔｒｕｎｃａｔｅ（Ｈａｓｈ（Ｋ_ｐ，Ｍ））」が「ｖ」に等しいか否かについて判断する。「Ｐ」における全てのルータが、この条件を満たす場合、当該アドレスサーバは、機能２２２８、２２３０、２２３２及び２２３４に示すように、集合「Ｑ」における各ルータ「ｑ」に対して、「Ｔｒｕｎｃａｔｅ（Ｈａｓｈ（Ｋ_ｐ，Ｍ））」が「ｖ」に等しくないことを確かめる。また、この条件も満たされる場合、機能２２３４及び２２５０において、（ｖ，Ｍ）対も、ルータ「Ｒ」用の有効なサフィックスとして加えられる。これらのこれまでのステップは、機能２２４８及び２２４６における「ｖ」の他の考えられ得る値に対して繰り返される。

機能２２２４において、「Ｐ」におけるいずれかのルータが、テストに失敗した場合、（ｖ，Ｍ）対を、「ｒ」に対して用いることができない。そして、機能２２４４において、「Ｖ」の他の全ての値が、全てが試されるまで繰り返される。次に、機能２２５２において、次のルータが、「Ｒ」における全てのルータが探索されるまで、評価される。所定の「Ｍ」に対して、全てのルータが探索された場合、次の「Ｍ」が評価される（機能２２５２、２２３６及び２２４０）。機能２２３２において「Ｑ」におけるルータ「ｑ」が上述の条件に当てはまらない状況と同様に（かかる場合、（ｖ，Ｍ）対を「ｒ」に対して使用できない）、機能２２４６において、ルータ「ｒ」用の「Ｍ」を廃棄し、機能２２４４及び２２５２において、「Ｒ」における他のルータに対してテストする前に、集合「Ｖ」における残りの値を通じて繰り返す。

図１５及び図１６は、追加の最適なルーティング、例えば、図１２に関連して説明したルーティング用のアドレスの２つの考えられ得る構造を示す。

図１５において、かかるアドレスは、プライバシードメインプレフィクス１６１０と、当該ＩＰアドレスに対応する鍵のバージョンを表すビット１６１２と、暗号化されたプレフィクスの連結１６１４と、サフィックス「Ｍ」１６１６とによって構成されている。当該アドレスは、これまでに既に決まっているテーブル内の特定のエントリに対するインデックス等の特定の値へのどのようなポインタも含まない。値がない場合、全てのルータ（又は、少なくとも所定のレベルにおける全てのルータ）は、それまでに合意されている特定の値を使用しなければならない。ＩＰｖ６の場合、「Ｍ」の長さは、一般的には、６２ビットであるが、ネットワークに適した他の値が用いられてもよい。

図１６は、（要素１７２１によって）ＩＰアドレス内の値１７１８により示されるインデックステーブル１７２０を示す。当該アドレスは、プライバシードメインプレフィクス１７１０と、当該ＩＰアドレスに対応する鍵のバージョンを表すビット１７１２と、暗号化されたプレフィクスの連結１７１４と、サフィックス「Ｍ」１７１６とによって構成されている。また、当該アドレスは、既に合意されているテーブル内のエントリ、各レベルにおけるルータ用に構成されているテーブル内のエントリ、或いは、特定の値自体に対するインデックス等の特定の値１７２０に対するポインタ１７１８も含む。ポインタ又は特定の値１７１８を有することは、アドレス生成サーバの効率を改善するのに好ましい。ポインタ１７１８を用いて、ルータの所定のトポロジーに必要なアドレスを見つけ出るためにアドレスサーバが行わなければならない計算の量は、平均して「２^ｎ倍」だけ低減される。ここで、「ｎ」は、値のビット数又は値に対するポインタのビット数である。１７１８がある場合、「Ｍ」の長さは、ＩＰｖ６が用いられている場合、一般的には、（６２−ｍ）ビットに低減される。しかし、当業者は、他の値も使用できることを理解している。

図１７は、最適化されたルーティング１９４用の特別なサブケースを示す。ルータが、受信したパケットに対してインバウンドルーティング状態である場合、機能２１６にいる。ＯＲタイプのホップバイホップオプションを用いずにパケットを受信し、インバウンドルーティング状態に達したとき、当該ルータは、機能２１２に示すようになる。当該ルータは、機能２１８に示す「クロスオーバチェック」を行う。機能２１８は、当該ルータが、次に示すように、クロスオーバ状態にあるか否かについて判断する。
- 自身のレベルが「ｊ」であるの場合、「Ｗ（ｊ，ｌ）」を見つける。
- 「Ｗ（ｊ，ｌ）」用の開始ビットは、予め構成されている。
- 「Ｖ_ｊ＝Ｈ（Ｎ（ｊ），Ｍ，Ｘ_ｊ）」を計算する。
- 「Ｈ（Ｂ（ｊ，ｌ），Ｘ_ｊ，Ｍ）＝Ｗ（ｊ，ｌ） ＸＯＲ Ｖ_ｊ」であるか。（ルータが、クロスオーバルータである場合のみ「Ｙｅｓ」）。

次に、機能２１２において、「クロスオーバチェック」を行った後、当該ルータは、右端のビットで始まる「Ｘ」を解読し、その解読されたプレフィクス成分（ＰＣ）用の終了ビットを得る。当該ルータが、クロスオーバルータである場合、当該ルータは、（ＰＣを「ＦＷａｌｇ＊（）」に入力して次のホップルータを得ることにより、）解読されたＰＣに基づいて、パケットを転送する。当該ルータが、クロスオーバルータでない場合、当該ルータは、終了ビットを含むＯＲホップバイホップ及び「ＩＲＩ＝０」で、パケットをデフォルトルートの上方へ転送する。「ＩＲＩ＝１」の場合、「Ｅ／Ｓビット」が開始ビットであり、当該ルータは、開始ビットで解読を開始し、右へ進行する。一方、「ＩＲＩ＝０」の場合には、「Ｅ／Ｓビット」は終了ビットであり、当該ルータは、終了ビットで解読を開始して、左へ進行する。この後者の場合には、ＰＣのサフィックスが、ＰＣ自身ではない特性（この特性は、以下で説明する）を必要とする。

そうでない場合、当該ルータは、受信したパケットがＯＲホップバイホップオプションを有する状態２２０でなければならない。当該ルータは、ＯＲホップバイホップオプションを解読して、「終了又は開始（Ｅ／Ｓ）ビット」及び「ＩＲＩ」を得る。当該ルータは、「Ｅ／Ｓビット」で開始する「Ｘ」を解読して、新たな「Ｅ／Ｓビット」（なお、新たなＰＣが、当該新たな「Ｅ／Ｓビット」で終了する）を得て、ＰＣを解読する。次に、当該ルータは、ホップバイホップオプションからの「ＩＲＩ」が「０」に等しいか否かについてチェックする。「ＩＲＩ」が「０」に等しくない場合、（機能２１０のように、）「ＩＲＩ＝１」であり、当該ルータは、解読したＰＣに基づいて転送を行い、パケット内で、古いホップバイホップオプションに取って代わる新しいホップバイホップオプションに「ＩＲＩ＝１」を設定する。また、新しいＯＲホップバイホップは、新しい「Ｅ／Ｓビット」を含む。

「ＩＲＩ＝０」の場合には、状態２１４である。次いで、「クロスオーバチェック」が行われる。当該ルータが、クロスオーバルータである場合、解読したＰＣに基づいて転送が行われ、「ＯＲホップバイホップオプション」に新たな「Ｅ／Ｓビット」と共に「ＩＲＩ＝１」を設定する。当該ルータが、クロスオーバルータでない場合、「ＩＲＩ＝０」を保持し、ＯＲホップバイホップ内の新たなＥ／Ｓを用いて、デフォルトルートの上方への転送を行う。

プレフィクスは、転送アルゴリズムにおいて、上方へ流れてはいけないことに注意する。プレフィクスがそうなった場合、より高いレベルのルータは、完全に解読されたプレフィクスを得ることができ、ＣＰＰのプライバシー特性が無効になる。

上記の論考に基づくと、以下の問題は自明である。すなわち、ルータが、当該ルータのレベル鍵で暗号化されたプレフィクス成分に基づいて、インバウンドパケットを転送することができると仮定する。さらに、プレフィクス成分のサフィックスが、当該プレフィクス成分自身ではないと仮定する。従って、上述のアルゴリズムは、プライバシードメイン内で最適なルーティングを提供する。

以下の実施形態においては、セキュリティ問題及び適合した鍵ハッシュ変形について完全に最適化されたルーティングの例が提供される。

「Ｕ」が、アドレスのロケーションに関する情報を漏らすことに注意する。それに伴って、レベルルータのシークレットを所有する盗聴者は、十分なパケットを入手することにより、「Ｕ」を計算することができる。このことは、上述の「Ｗ」の式における「Ｕ」を置換することにより阻止することができる。

例えば、「Ｂ（ｊ，ｋ）」を、鍵サーバ及びレベル（ｄ＋１−ｊ）におけるレベルのｋ番目のルータに知られている秘密鍵とする。インターネットからのパケットＰ用の最適なパスが、次の秘密鍵（すなわち、「Ｂ（１，ｋ１），Ｂ（２，ｋ２），…，Ｂ（ｊ，ｋｊ）」）を有するレベルルータを含むと仮定する。すると、「Ｗ」は、「Ｗ＝Ｈ（Ｂ（１，ｋ_１），Ｍ） ＸＯＲ Ｖ_１，Ｈ（Ｂ（２，ｋ_２），Ｍ） ＸＯＲ Ｖ_２，…，Ｈ（Ｂ（ｊ，ｋ_ｊ），Ｍ） ＸＯＲ Ｖ_ｊ」となる。ここで、「Ｈ（Ｂ（ｊ，ｋ），Ｍ）」は、「ｋ」が「１」に等しくない場合、「Ｈ（Ｂ（ｊ，１），Ｍ）」に等しくなく、「Ｔｒｕｎｃ（Ｈ（Ｂ（ｉ，ｋ），Ｍ））用に選択されたビット数が、レベル（ｄ＋１−ｉ）におけるルータの数の２倍の対数の底に等しい。

例えば、上述の例において、レベル１における１２８のルータの場合、１４ビットが、「Ｗ」のレベル１成分に用いられる。ビット数を増やすことにより、潜在的な衝突の数も、単一のレベルにおけるハッシュ関数値の間で低減される。当業者は、バースデーパラドックスは、たとえビット数が増加した場合でも、当時の約４０〜５０％、衝突が予想できることを示すことを認めるであろう。この問題を扱うために、上述の鍵サーバは、レベル（ｄ＋１−ｉ）における全てのルータに対する「Ｔｒｕｎｃ（Ｈ（Ｂ（ｉ，ｋ），Ｍ））を計算することにより、各レベルルータに対して所定の「Ｍ」を検査しなければならない。「Ｍ」は、計算された値に衝突がない場合にのみ用いることができる。レベル（ｄ＋１−ｉ）をチェックした後、当該鍵サーバは、レベル（ｄ−１）が良好にチェックされるまで、レベル（ｄ＋２−ｉ）等をチェックする。「Ｍ」は、最適化されたルーティング成分が「Ｗ」にあるレベルの衝突が全くない場合にのみ用いられる。

各レベルにおいて、「Ｍ」の半分以下を失うことが予想される。そのため、４つのレベルの場合、「Ｍ」の１５／１６未満が失われる。「Ｍ」が、２０ビットの場合、２^１６超の考えられ得る「Ｍ」がある。このようなアプローチは、各成分のサイズを増加させる。従って、このアプローチを伴う最適化されたルーティングの１〜３レベルに対しては、十分なビットがある可能性がある。状況に応じて、「Ｗ」成分は、「Ｗ」の成分が存在すること、或いは、「Ｗ」の成分が存在しないことを示す１ビット又は２ビットを前置きしてもよい。この新しいスキームを用いた別のアプローチは、レベル１のルータ用の最適化したルーティングを省くことである。この場合、レベル２及びレベル３にとって十分なビットであろう、及び、最低でも、レベル４において「Ｕ（ｊ，ｋ）」に対して用いられるビットをいくつか残す。「Ｕ」は、上述のツリーにおけるより高いレベルにおいて、より少ない情報を漏らす。換言すれば、レベル２及びレベル３においては、「Ｈ（Ｂ（ｊ，ｋ），Ｍ）」を用いることができ、レベル４においては、「Ｕ（ｊ，ｋ）」を用いることができる。

別法として、レベル２、３において、及び、ビットが残るより高い他のいかなるレベルにおいても、「Ｈ（Ｂ（ｊ，ｋ），Ｍ）」のみを用いることができる。これらは、当業者にとって明白な追加の変形例である。

レベル４に１個のルータを有し、レベル３に８個のルータを有し、レベル２に６４個のルータを有し、レベル１に１２８個のルータを有し、５１２個のアクセスルータを有するルーティングツリーを含む上述の例について再び考える。「Ｘ」が、１６ビットを使用し、「Ｚ」が、１４ビットを使用する一方、「Ｐ_０」が、４８ビットを要するものと仮定する。「Ｍ」は、２０ビットを有する。２ビットが、鍵バージョン用として、及び、ロケーションプライバシーが保護されたアドレスであることを表すために用いられる。そのため、「Ｗ」は、２８ビットを有する。レベル１のルータにおけるルート最適化が先行した場合、完全に最適化されたスキームの鍵ハッシュ変形は、レベル２に対して１２ビットを使用し、６ビットがレベル３用に必要となる。そのため、「Ｗ」は、１８ビットを必要とする。

別法として、レベル１及びレベル２は、（鍵ハッシュ変形を用いて）最適化され得る。ここで、（１４＋１２）ビット（合計で、２６ビット）が使用される。「Ｕ」が、レベル３における最適化に用いられる場合、さらに３ビットが「Ｗ」に必要である。「Ｗ」は、２８ビットを有し、２６ビットがすでに使用されている。そのため、「Ｍ」から１ビット借りて、「Ｍ」を１９ビットに低減する。「Ｍ」は、（衝突によるいくつかの「Ｍ」の排除により、）実際には１６ビットよりも少し大きいだけである。従って、６５，０００超のＩＰアドレスが、サブネットごとに使用可能となる。

上述の式においては、「Ｈ（Ｂ（ｉ，ｋ_ｉ），Ｍ）」を「Ｈ（Ｂ（ｉ，ｋ_ｉ），Ｘ_ｉ，Ｍ）」と置換することができることに注意する（ここで、１≦ｉ≦ｊである）。この置換の利点は、Ｈ（Ｂ（ｉ，ｋ_ｉ），Ｍ）を得る攻撃者が、この値と関連付けられたロケーション情報と、同じ「Ｍ」の値を共有するホストとを対応付けることを防ぐことである。換言すれば、同じ「Ｍ」の値を共有するホストは、「ｉ」のいくつかの値に対して、同じ「Ｈ（Ｂ（ｉ，ｋ_ｉ），Ｍ）」を共有してもよい。

図１８は、本発明の鍵ハッシュルーティング変形例２０１を示す。図示の実施形態は、「Ｈ（Ｂ（ｉ，ｋｉ），Ｘｉ，Ｍ）」を使用し、「鍵ハッシュ変形例」とは、この例を指す（ここで、図５の機能１６０は、鍵ハッシュが実施されることを表してもよい）。図１８の機能２０６において、パケット用の処理ルータは、自身がレベルルータであるか否かについて判断する。レベルルータでない場合、当該ルータは、機能２０２においてデフォルトルートの上方にパケットを転送する。レベルルータである場合、当該ルータは、機能２０８を実行する。すなわち、
- 当該処理ルータのレベルが「ｊ」の場合、「Ｗ（ｊ，ｌ）」を見つける。
- 「Ｗ（ｊ，ｌ）」の開始ビットは、予め構成されている。
- 「Ｖ_ｊ＝Ｈ（Ｎ（ｊ），Ｍ，Ｘ_ｊ）」を計算する。
- 「Ｈ（Ｂ（ｊ，ｌ）Ｘ_ｊ，Ｍ）＝Ｗ（ｊ，ｌ） ＸＯＲ Ｖ_ｊであるか。

当該パケット用の処理ルータが、機能２０８において、自身がレベルルータではないと判断した場合には、当該処理ルータは、（自身がクロスオーバルータではないため、）機能２００に進んで、パケットを、デフォルトルートの上方へ転送する。次いで、当該処理ルータは、機能２０４へ進んで、次のステップを実行する（かかる場合、当該ルータは、当該パケット用のクロスオーバルータである）。
- 鍵「Ｔ_ｉ＝ＨＭＡＣ（Ｌ_ｉ，Ｌ_１｜Ｌ_２｜…｜Ｌ_{（ｉ−１）}，（ｉ＝２，…，ｊ））」は、予め計算されている。
- 「Ｐ_{（ｉ−１）}＝Ｈ（Ｔ_ｉ，Ｍ，Ｘ_{（ｉ−１）}） ＸＯＲ Ｐ_{（ｉ−１）} ＸＯＲ Ｈ（Ｔ_ｉ，Ｍ，Ｘ_{（ｉ−１）}），（ｉ＝２，…，ｊ）」を計算する。
- 「Ｐ_ｉ」を連結して、プレフィクス「Ｐ_ｃ」を取得する。
- レベル鍵を用いて、「ｊ」、「Ｐ_Ｃ」、「Ｐ_ｄ」を解読し、「Ｐ_ｎｅｗ＝Ｐ_ｃ｜Ｐ_ｄ」を取得する。
- 「Ｐ_ｎｅｗ」を「ＦＷａｌｇ＊（）」に入力することによって、「ＮｅｘｔＨｏｐ（次のホップのルータ）」を取得する。
- 開始ビット（「オフセット＝（Ｐｄの右端のビット）＋１」）及び新たなターゲットレベル（「新たなターゲットレベル＝自身のレベル−１」）と共に、共有リンク鍵を用いて、ホップバイホップオプション内に、「Ｐ_ｎｅｗ」を暗号化する。
- パケットに対して当該ホップバイホップオプションを追加して、「ＮｅｘｔＨｏｐ」に転送する。

ＣＰＰは、ルーティングを最適化しているため、トラヒック集中ポイントが回避され、モバイルＩＰやＨＭＩＰｖ６に関連するようなトンネリングオーバヘッドも回避される。

図１９は、本発明の一実施形態における例示的なアーキテクチャ構成要素を示す。ユーザホスト１４４は、アクセスルータと同じ場所に配置されたＤＨＣＰｖ６サーバ１４６から、当該ユーザホスト１４４のＩＰアドレスを得る。この通信は、１２０を介して行われる（ローカルリンク上の盗聴者に対する追加の保護の場合、ＩＰｓｅｃを用いることができれば、１２０を介した通信について暗号化すべきである。）

要素１４６は、通信パス１２２を介して、１２６に配置されたアドレスサーバから、ＣＰＰ ＩＰアドレス（基本ＣＰＰ ＩＰアドレス又は拡張ＣＰＰ ＩＰアドレスのいずれか）の集合を定期的に得る。ここでも、この通信について、（例えば、ＡＡＡ（Ｒａｄｉｕｓ／Ｄｉａｍｅｔｅｒ）又はＩＰｓｅｃ等の）暗号化プロトコルを用いて保護することができる。ＡＡＡサーバは、要素１３８によって示される。

いくつかの鍵の集合がある。基本ＣＰＰ ＩＰアドレスにおいては、レベル鍵及び共用リンク鍵のみが必要となる。共用リンク鍵は、（例えば、ＩＫＥ、ケルベロス、Ｒａｄｉｕｓ／Ｄｉａｍｅｔｅｒ又はＴＬＳ等の）任意の適当な鍵管理／配布プロトコルを用いて、レイヤ２リンクを介して設定される。当該プロトコルは、相互認証及びセッション鍵の設定を提供すべきである。拡張ＣＰＰ ＩＰアドレスの場合、クロスオーバレベル鍵（Ｎ_ｉ）、クロスオーバシークレット（Ｕ（ｊ，ｋ）及び／又はＢ（ｊ，ｋ））、及び、ツリー鍵（Ｌ_ｉ）が、基本レベル（Ｋ_ｉ）鍵に付加される。これらの鍵は、まとめて「ＣＰＰ鍵」と呼ばれる。

ＣＰＰ鍵は、耐タンパ型スマートカード内のマスター鍵生成器上で生成され得る。鍵サーバホストのスマートカードの各々の公開鍵は、マスター鍵生成器のスマートカードに手動で入れられていてもよい。当該スマートカードは、キーボードパッド及びコマンドラインディスプレイインタフェースを有してもよい。（公開鍵暗号化アルゴリズムにおける公開鍵に対応する）プライベート鍵及び秘密鍵は、スマートカードのどれからも出ない。この規則の例外は、上述のＣＰＰ鍵が、スマートカードにのみ知られている鍵、或いは、ターゲットのスマートカードと共用するＴＬＳセッション鍵にいずれかによって暗号化されて、当該スマートカードからホストに出力されることである。

逆に、マスター鍵生成器１３４及びバックアップ鍵生成器１３６の公開鍵は、アドレスサーバ／鍵サーバホストのスマートカードに、手動で入れられる。この手動処理手続きは、スマートカードの寿命中に一度だけ行われる。後に、新たな公開鍵が生成された場合、かかる公開鍵は、ターゲットホストのスマートカードのＴＬＳセッション鍵で暗号化されて、当該スマートカードから出力される。当該ＴＬＳセッション鍵も、当該スマートカードに保持される。当該スマートカード用の最初の公開鍵は、適切なコマンドが入力されたときに、コマンドラインインタフェース上に表示される。

本発明のアーキテクチャは、スマートカードに対する物理的攻撃が成功しない限り、ＴＬＳプロトコルが破壊されない限り、或いは、鍵がＣＰＰ ＩＰアドレス又はプライバシードメインルータから得られない限り、秘密鍵及びプライベート鍵が敵対者／攻撃者に知られないことを保証する。ＴＬＳプロトコルは、上述のホストで実施される（鍵サーバホスト、及び、マスター鍵／バックアップ鍵生成器ホスト）。しかし、当該ホストは、暗号化及び鍵操作のために、スマートカードとのインタフェースであるＡＰＩを用いる。当該ホストは、どのプライベート鍵又は秘密鍵にもアクセスしない。また、当該スマートカードは、ＴＬＳプロトコルの認証状況についての処理を行ってもよい。

スマートカードが、互いに公開鍵を共用するので、認証は、全て自己承認される。そのため、認証動作は、名前検索と、及び、認証における公開鍵が、当該名前に関連付けられており当該スマートカードに記憶されているものと一致するかについてのチェックとに限定される。マスター鍵生成器及び鍵サーバは、共に、以下の要素、すなわち、「ルータＩＤ１」、「クロスオーバシークレットＩＤ１」、「（ツリー鍵１１、ルータＩＤ１１）」、「（ツリー鍵１２、ルータＩＤ１２）」、…、「レベルルータＩＤ２」、「クロスオーバシークレットＩＤ２」、「（ツリー鍵２１、第１のルータＩＤ２１）」、「（ツリー鍵２２、第２のルータＩＤ２２）」、…、レベル…、を含む鍵キャッシュを構築する。

最初の列は、全てのレベルルータをリストする。当該ルータ用のＩＤは、ＤＮＳネーム、ＤＮＳネームのハッシュ、或いは、可能ならばＩＰアドレスのいずれかとすることができる。第２の列は、当該ルータ用のクロスオーバシークレット（Ｕ（ｊ，ｋ））を含む。次のエントリは、当該ルータが、当該ルータの子のルータに配布するツリー鍵である。最後の列は、当該ルータ用のレベルを含む。加えて、鍵キャッシュは、レベル鍵について二重にリンクされたリストと、クロスオーバレベル鍵について二重にリンクされたリストとを含む。

これらのシークレット及び鍵は、マスター鍵生成器のスマートカードに生成される。マスター鍵生成器サーバは、このキャッシュをホスト上に構築する。当該シークレット及び鍵は、暗号化形式でキャッシュ内に存在する。当該シークレット又は鍵用の暗号化形式の例は、次の通りである。
［鍵バージョン、｛ランダムな８バイト（コンファウンダー）、鍵の長さ、鍵、タイムスタンプ（４バイト）｝スマートカード鍵］スマートカード鍵２

「｛…｝Ｋ」という記述は、秘密鍵「Ｋ」を用いた括弧内に含まれるバイトの暗号化を表す。「［…］Ｋ２」という記述は、「…」が、鍵「Ｋ２」及びＨＭＡＣ等の鍵を用いた完全性関数を用いた完全性が保護されたバイトであることを表す。従って、ホストは、秘密鍵にアクセスしない。暗号化された秘密鍵を鍵サーバホストへ送信する前に、マスター鍵生成器サーバは、ＴＬＳプロトコルを用いて、暗号化された鍵を宛先ホスト名と共に、スマートカードへ送信する。

当該スマートカードは、宛先ホストのスマートカードと共用するＴＬＳ秘密セッション鍵（チャネル暗号化鍵）を用いて、鍵を再び暗号化する。次いで、当該マスター鍵生成器サーバは、鍵キャッシュデータを鍵サーバホストへ送信する。上述のフィールド内のタイムスタンプは、ホスト上の悪意のあるソフトウェアからのリプレイを検知するのに用いられる。当該スマートカードは、自身のタイムスタンプを維持する（すなわち、暗号化された鍵の全てのタイムスタンプ値は、当該タイムスタンプよりも後でなければならない）。鍵サーバホスト上の各鍵サーバは、同じ暗号化された鍵プロトコルを用いて、ローカル鍵キャッシュを構築する。このローカル鍵キャッシュは、マスター鍵サーバホスト上のもののコピーである。

別法として、鍵キャッシュは、マスター鍵サーバホスト上の鍵キャッシュの部分集合とすることができる。鍵サーバホストスマートカードは、（このキャッシュが、マスター鍵サーバホストのキャッシュのコピーであっても、マスター鍵
サーバホスト上の鍵キャッシュの部分集合であっても、）アドレスサーバからの要求を処理する場合、鍵キャッシュにアクセスすることになる。

次に、鍵サーバとマスター鍵生成器サーバとの間のプロトコルについて説明する。要求メッセージに関して、以下に示す非排他的な例は、上述のアドレスサーバによって送信されてもよい。
（１）クロスオーバシークレット要求メッセージｉｄ、長さ、ルータＩＤ；
（２）ツリー鍵要求メッセージｉｄ、長さ、親ルータＩＤ、子ルータＩＤ；
（３）レベル鍵要求メッセージｉｄ、長さ、レベル；
（４）クロスオーバレベル鍵要求メッセージｉｄ、長さ、レベル；
（５）公開鍵更新要求メッセージｉｄ、長さ；
（６）最適化されたルーティング鍵更新メッセージ、メッセージｉｄ、ルータＩＤ

直前の要求メッセージに対応する応答メッセージに関して、以下に示す非排他的な例が返されてもよい。
（１）クロスオーバシークレット応答メッセージｉｄ、長さ、ルータＩＤ、暗号化された鍵；
（２）ツリー鍵応答メッセージｉｄ、長さ、親ルータＩＤ、子ルータＩＤ、暗号化された鍵；
（３）レベル鍵応答メッセージｉｄ、長さ、レベル、暗号化された鍵；
（４）クロスオーバレベル鍵応答メッセージｉｄ、長さ、レベル、暗号化された鍵；
（５）公開鍵更新応答メッセージｉｄ、長さ、暗号化された鍵；
（６）最適化されたルーティング鍵応答メッセージｉｄ、長さ、暗号化された鍵及び他のパラメータ

上述のプライバシードメイン内のルータに関する情報を有するデータベースが存在する。典型的なデータベースのエントリは、「当該ルータのＤＮＳネーム」、「他のルータネーム又は識別子」、「当該ルータにより所有されるプレフィクス」、「レベル」、「当該ルータの親」、「当該ルータの子」、「当該ルータの他のレイヤ２ピア」及び「直接接続されたリンク用のリンクコスト」を含む。ＣＰＰ及び／又は拡張ＣＰＰアドレスの構造も、ここに格納される。例えば、種々の成分「Ｍ」、「Ｘ」、「Ｗ」、「Ｚ」に用いられるビット数が格納される。また、「Ｗ」のいずれかの成分が（最適化されたルーティングのために）失われた場合、かかる情報も同様に格納される。

上述のデータベースエントリ内の情報は、当該データベース内で、及び、ネットワークを通過する際に、保護される。同様に、その他の情報があってもよい。各アドレスサーバは、当該データベースにアクセスして、ルータ及びアドレスに関する情報を構築する。当該アドレスサーバは、
「プレフィクス１→ルータの最適なルートリスト；Ｐ_１１，…，Ｐ_１ｋ」
「プレフィクス２→ルータの最適なルートリスト；Ｐ_２１，…，Ｐ_２ｋ」
の形式のアドレスサーバキャッシュを構築する。

「Ｐ_ｉ」は、プレフィクスに対応するプレフィクス成分である。最適なルータのリストは、プレフィクスについて、境界ルータから宛先アクセスルータへの最低のコストのパスを含む。また、アドレスサーバは、マスター鍵生成器サーバに対して、「Ｍ」のブロックを定期的に要求する。これらの「Ｍ」は、ＣＰＰ ＩＰアドレスを構築するのに必要である。これらの「Ｍ」は、ＴＬＳを用いて暗号化され、完全に保護される。「Ｍ」は、暗号化されていない形式では、上述のホストに対して利用可能ではない。

アドレスサーバとスマートカードとの間のインタフェースは、次の通りである。当該アドレスサーバは、「Ｐ_１，…，Ｐ_ｋ」と、ＤＮＳネーム又は最適なルートのルータ用の他の識別子のリストとを含む要求を生成することができる。当該スマートカードは、かかる情報から、ＣＰＰ ＩＰアドレスを生成して返すことになる。当該スマートカードは、ＣＰＰ ＩＰアドレスを構築するために、ルータ鍵情報について、鍵サーバキャッシュに問い合わせる。これらの問い合わせは、レベル鍵及びクロスオーバレベル鍵を要求したときに、ルータＩＤ又はレベルのいずれかで索引付けされる。

また、スマートカードは、「Ｍ」のブロックについて、アドレスサーバに問い合わせることもできる。これらの「Ｍ」は、当該スマートカードに配布されるまでは、暗号化されて完全に保護されたままである。信頼の置けないソフトウェアは、「Ｍ」を変更することができないことが重要である。完全に最適化されたルーティングの鍵ハッシュ変形を用いる場合、当該スマートカードは、レベル（ｄ＋１−ｊ）におけるルータに対応する各「ｋ」に対して「Ｔｒｕｎｃ（Ｈ（Ｂ（ｊ，ｋ），Ｍ））」を計算することにより、各「Ｍ」をテストしなければならない。ここで、「Ｔｒｕｎｃ」は、（ｄ＋１−ｊ）ルータの数の２倍の対数に切り捨てることを示す。これらの計算値に衝突がなければ、「Ｍ」は、（ｄ＋１−ｊ）レベルに対して許容できる。各連続するレベルも、テストされ、「Ｍ」は、全てのレベルにおいて衝突がない場合にのみ用いられる。

図２０は、完全に最適化されたルーティングの鍵ハッシュ変形が用いられる場合に、拡張ＣＰＰ ＩＰアドレスを割り当てる例の機能を示す。（可能であれば、アドレスサーバホスト上のスマートカード内で実行する）割り当てエンティティは、機能２３０で始まる。入力は、機能２３２にリストされており、アドレスプレフィクス成分「Ｐ_０，Ｐ_１，…，Ｐ_ｋ」と、（ネットワーク障害がない場合に、）通常、パケットが通過するルータのリストとを含む（ネットワーク障害は、パケットが、生成されるアドレスへ配信されることを妨げない、或いは、アドレスから配信されることを妨げないが、いくつかのパケットは、ネットワーク障害がある場合、特別なホップを要求してもよいことに注意する）。

機能２３４において、「Ｍ」が選択される。かかる機能は、（リストからのものである、或いは、任意に生成され得る）次の「Ｍ」を得る。加えて、「Ｍ」は、既に「Ｐ_０，Ｐ_１，…，Ｐ_ｋ」に関連付けられているサブネットに対して用いられている場合には、捨てられる。「Ｍ」が捨てられた場合、機能２３４を再度行うことにより、別の「Ｍ」が選択される。機能２３６において、最適化ルーティングが用いられている各レベル「ｊ＝ｄ−１，…，２」について、レベル（ｄ＋１−ｊ）の各ルータ「ｋ」に対する「Ｔｒｕｎｃ（Ｈ（Ｂ（ｊ，ｋ），Ｘｊ，Ｍ））を計算する。いずれか２つの値が一致した場合には、「Ｍ」を捨てる。「Ｍ」が、レベル（ｄ＋１−ｊ）に許容できる場合、「ｊ」を減らして、テストを繰り返す。「Ｍ」が捨てられた場合、機能２３４に戻って、新たな「Ｍ」を選択する。そうでない場合には、機能２３８へ進む。

機能２３８においては、拡張ＣＰＰアドレスＡが生成され、機能２３４及び機能２３６におけるテストを通過した「Ｍ」がある。そこで、「Ｐ_０」をグローバルルーティングプレフィクスとして有する新たなＩＰアドレスが生成される。（このアドレスを生成するのに用いられる鍵バージョンを示す）鍵バージョンビット「ｖ」、「Ｘ＝Ｐ_１ ＸＯＲ Ｈ（Ｋ_１，Ｍ，Ｘ_２）｜…｜Ｐ_ｋ ＸＯＲ Ｈ（Ｋ_ｋ，Ｍ，Ｘ_ｋ−１）」、「Ｗ＝Ｈ（Ｂ（２，Ｋ_２），Ｘ_２，Ｍ） ＸＯＲ Ｖ_２，…，Ｈ（Ｂ（ｄ−１，Ｋ_{（ｄ−１）}），Ｘ_ｄ，Ｍ） ＸＯＲ Ｖ_ｄ」、「Ｚ＝Ｐ_１ ＸＯＲ Ｈ（Ｔ_２，Ｍ，Ｘ_１）｜Ｐ_２ ＸＯＲ Ｈ（Ｔ_３，Ｍ，Ｘ_２）｜…｜Ｐ_ｋ−１ ＸＯＲ Ｈ（Ｔ_ｋ，Ｍ，Ｘ_ｋ−１）」、「Ｍ」

機能２４０においては、上述のＣＰＰアドレスＡは、アドレスサーバに受け渡され、当該アドレスサーバは、アドレス有効期間及び「Ｐ_０，…Ｐ_ｋ」と共に、Ａを、「Ｐ_０，Ｐ_１，…，Ｐ_ｋ」に対応するサブネット内のアクセスルータ（ＡＲ）上のＤＨＣＰｖ６へ受け渡す。（図１９に示す）ＣＰＰレベルルータ１４２は、（図１９に示す）通信パス１２４を介して、鍵サーバから鍵を得る。ルータは、これらの鍵を、新たな鍵期間が始まる前に得なければならない。

例えば、鍵期間は、１日の長さを有してもよい。これらの鍵は、（例えば、ＩＰｓｅｃ、ＴＬＳ、ケルベロス、又は、ＡＡＡが導いた暗号化プロトコル等の）暗号化プロトコルを用いて暗号化される。鍵を配信するプロトコルは、相互認証も提供しなければならない。ルータと鍵サーバとの間のプロトコルは、次のフィールド（すなわち、「ルータ（ＤＮＳネーム又は他の識別子）」、「鍵使用（レベル鍵、クロスオーバシークレット、クロスオーバレベル、又は、ツリー鍵）」、「鍵種別（アルゴリズム）」、「鍵」及び「バージョン」）を含む。スマートカードは、それらの鍵がホストに対して使用可能になるのを防ぐために、暗号化プロトコル用のセッション鍵を管理する。ＣＰＰ鍵は、スマートカード上で、暗号化プロトコルのセッション鍵で暗号化される。プロトコルコード自体は、スマートカード上に実装してもよい。

マスター鍵生成器は、（図１９に示す）１３０を介して、バックアップ鍵生成器１３６に対して、ステータスデータを定期的に転送する。このようなステータスデータは、当該マスターが「Ｍ」ブロックを配布したサーバかについての情報、及び、当該「Ｍ」ブロックの値に関する情報を含んでもよい。当該バックアップは、上述の鍵サーバと同様のローカル鍵キャッシュを構築することもできる。当該バックアップは、当該マスターが故障した場合に、当該マスターの機能を引き継ぐ。当該バックアップ及び当該マスターは、（図１９にも示す）ファイアウォール１４８を用いて、互いに、及び、アドレス／鍵サーバホストを除いて、いかなるホストとも通信することが防止されている。

次に、本発明の「ＩＣＭＰ（Ｉｎｔｅｒｎｅｔ Ｃｏｎｔｒｏｌ Ｍｅｓｓａｇｅ Ｐｒｏｔｏｃｏｌ）」との相互作用について説明する。「ｔｒａｃｅｒｏｕｔｅ」等のパケットによって取られたパスを判断する標準的なＩＰツールは、修正しない限り、又は、ＩＰｓｅｃを用いない限り、ロケーションプライバシーを危うくする。「ｔｒａｃｅｒｏｕｔｅ」は、接続の他端の通信相手に到達するまで、徐々に増加する「ＴＴＬ（ｔｉｍｅ ｔｏ ｌｉｖｅ）」値を伴ってパケットを送出することにより、クライアントのトポロジーにおけるロケーションを決める。

通信相手に到達するのに要されるより小さな「ＴＴＬ」は、減少して「０」になる。ＴＴＬ値が減少して「０」になると、「減少」を行うルータは、「ＩＣＭＰ時間超過メッセージ（ＩＣＭＰ Ｔｉｍｅ Ｅｘｃｅｅｄｅｄ ｍｅｓｓａｇｅ）」を発信元へ返信する。このパケットにおける発信元アドレスは、「ＴＴＬ＝０」が検知されたルータである。攻撃者は、このような情報を利用して、ネットワークのトポロジーと地理とを対応させるマップを形成することができる。

無許可のロケーション情報の決定を防ぐため、ルータは、送信者が、トポロジー情報を要求するのを許可されているか否かについて判断することができなければ、「時間超過メッセージ」の送信をやめるべきである。他のＩＣＭＰエラーメッセージも同じ分類である。ルータ又はホストは、受信者に、メッセージを受信することが許可されていることが分かっていない限り、ＣＰＰアドレスを用いて、ホストに対して、かかるメッセージのうちの１つを送信してはいけない。具体的には、受信者は、ＣＰＰアドレスと当該受信者のロケーションとの間のマッピングによって信用されなければならない。ＩＰｓｅｃは、このシナリオにおいて認証を提供するための候補プロトコルである。

本発明は、本願明細書において説明したように、ローカルリンク上での盗聴者に対する防御も提供する。ローカルリンク上での盗聴者に対する防御を所望する場合、ＣＰＰ ＩＰアドレスは、当該ローカルリンク上で暗号化されなければならない。例えば、ＩＰｓｅｃトンネルを、ホストからアクセスルータへのパケットをトンネリングするのに用いることができる。内部のＩＰｓｅｃトンネルアドレスは、ＣＰＰアドレスである。外部のトンネルアドレスについては、
（１）「トポロジー的に正しいＩＰアドレス」 − かかるアドレスは、企業内ルーティングを良好に機能させることができる（一方、かかるアドレスは、ホストのロケーションを当該ホスト上の悪意のあるソフトウェアにさらす）、又は、
（２）「任意に生成されたＩＰアドレス」 − かかるアドレスは、悪意のあるソフトウェアが、（１）のようなトポロジー的に正しいＩＰアドレスにアクセスするのを防ぐ（この場合、ホストルートを用いなければならない）、
のいずれかとすることができる。

追加の防御について、ＣＰＰルータは、当該ＣＰＰルータのレイヤ２リンクを介して、ＩＰｓｅｃを用いることもできる。このようなことは、当該リンク上での盗聴者に対する追加の防御を提供する。一般に、盗聴者は、転送パス上で、ホストのローカルリンクからのアドレスを追跡する必要があり、かつ、当該リンクのうちの１つで、ＣＰＰ ＩＰアドレスを明瞭に見ようとする。ＩＰｓｅｃ暗号化は、この種の攻撃アタックを防ぐ。

本発明には、多くの展開オプションがある。例えば、ＣＰＰルータは、オーバレイルータとして実施することができ、トンネルを用いることができる。このため、全てのルータを修正することを防ぐ。別のオプションは、境界ルータのみをレベルルータにすることである。そして、かかるルータは、同じ秘密鍵を共用する（かかる場合、ＣＰＰプレフィクスは、１つのみのセグメントを有する）。このようなルータは、パケットを受信したときに、プレフィクスを解読して、真の宛先ＩＰアドレスを得る。そして、かかるルータは、プレフィクスをホップバイホップオプションに封じ込めて、当該パケットを次のホップへ転送する。他の展開オプションも、当業者には明白である。

図２１は、ソフトウェアをベースとするルータの考えられ得る実装を示す。かかるルータは、バス２４２１に接続された多数のネットワークインタフェース（この場合、２４０２…２４１２の６個）によって構成されており、少なくとも１つの中央処理装置（ＣＰＵ）２４１４と、揮発性メモリ２４１８と、（プログラマブルＲＯＭ等の）不揮発性メモリ２４２０と、セキュリティ及び鍵関連機能のためのスマートカードインタフェース２４１６とを含む。かかる実装は、キーボード、マウス及びディスプレイ等のいくつかの他のＩ／Ｏインタフェースを必要に応じて有してもよい。このようなシステムは、本願明細書で言及したロジック及びアルゴリズムを実装し、このような実装は、ソフトウェアを用いて（全体的にまたは部分的に）行われてもよい。

本発明の有利な特徴は、以下の内容を含む。
（１）ホスト上の悪意のあるソフトウェアからの攻撃に対する防御。この場合、ＩＰアドレスは、未許可で信頼の置けないソフトウェアにさらされる；
（２）障害が発生したルータに対する防御。この場合、ＩＰアドレス空間のスクランブリングは無防備である；
（３）盗聴者に対する保護；
（４）最適なルーティング、及び、トラヒック集中ポイント／部分的に最適なルーティングの防止；
（５）ネットワークの構成要素が故障した場合の安定性、パケットを配信し続けることを保証すること；
（６）基本的なインバウンドルーティングアルゴリズムによって示したような安全性；
（７）追加の統合をスパニングツリーの外で使用できるようにする正規化、従ってルーティングを改善；
（８）トンネリングの排除（唯一の追加のオーバヘッドは、ホップバイホップオプション用の６〜８バイトであり、これは、例えば、ＨＭＩＰｖ６及びモバイルＩＰｖ６に必要なトンネリングオーバヘッドの僅かな部分である）；
（９）ＩＰｓｅｃ及び他のセキュリティプロトコルとのネガティブな相互作用がないこと。

上述の実施形態の説明は、当業者が本発明を実行しかつ利用できるように記載されている。これらの実施形態に対する様々な変更は、当業者には容易に理解でき、本願明細書で定義された包括的な原理及び特定の例は、発明の機能を用いていない他の実施形態に適用されてもよい。例えば、上述の異なる実施形態の特徴のうちのいくつか又は全てについて、かかる実施形態から削除してもよい。従って、本発明は、本願明細書に記載した実施形態に限定しようとするものではなく、特許請求の範囲及びそれらの均等物によってのみ定義される最も広い範囲を認容すべきである。

本発明の実施形態に係る暗号で保護されたプレフィクス（ＣＰＰ）を用いた例示的なネットワークを示す。 本発明の実施形態に係る統合からプレフィクス要素を得ることの実施例である。 本発明の実施形態に係る（ＩＰｖ６を例として用いた）ＣＰＰインターネットプロトコルアドレスの構造を示す。 鍵のバージョンを示すビットを含み、かつ、鍵のロールオーバをサポートする本発明の例示的な実施形態を示す。 ＣＰＰプライバシードメインルータの処理機能を含む本発明の例示的な実施形態を示す。 ホップバイホップオプションを含む本発明の例示的な実施形態を示す。 ＣＰＰ転送アルゴリズムを含む本発明の例示的な実施形態を示す。 ルーティング障害を考慮したＣＰＰ転送アルゴリズムを含む本発明の例示的な実施形態を示す。 正規化の例を含む本発明の例示的な実施形態を示す。 最適化されたルーティングスキームを含む本発明の例示的な実施形態を示す。 （例示的な形式においてＩＰｖ６を用いた）プレフィクスにより識別されるサブネット内にＣＰＰ拡張アドレスを含む本発明の例示的な実施形態を示す。 最適化されたルーティングを含む本発明の例示的な実施形態を示す。 ＣＰＰルータ機能を含む本発明の例示的な実施形態を示す。 ルーティングアドレス生成を含む本発明の例示的な実施形態を示す。 最適化されたルーティング用のアドレス構造を含む本発明の例示的な実施形態を示す。 最適化されたルーティング用の追加のアドレス構造を含む本発明の例示的な実施形態を示す。 最適化されたルーティング用の特別な部分的なケースを含む本発明の例示的な実施形態を示す。 鍵ハッシュで最適化されたルーティング機能の例を含む本発明の例示的な実施形態を示す。 アーキテクチャ要素の一例を含む本発明の例示的な実施形態を示す。 最適化されたルーティングの鍵ハッシュの変形が用いられたときに、拡張ＣＰＰを生成するのに用いられる機能の一例を含む本発明の例示的な実施形態を示す。 本発明の例示的な実施形態をソフトウェアで実施するための考えられ得るハードウェアを示す。

Claims (39)

1. 複数の相互接続されたルータを備えるネットワークであって、
   データは、前記相互接続されたルータを介して前記ネットワーク上で送信され、
   前記データは、ＩＰアドレスを含み、
   前記ＩＰアドレスは、前記データの宛先であるルータの論理的な位置を少なくとも識別し、
   前記ＩＰアドレスは、複数の部分に分割され、
   少なくとも前記複数の部分の部分集合は、暗号化され、
   前記相互接続されたルータの部分集合は、少なくとも前記ＩＰアドレスの一部を解読でき、
   前記相互接続されたルータの前記部分集合は、少なくとも前記ＩＰアドレスの一部を解読するための鍵を受け取り、
   前記相互接続されたルータの前記部分集合は、同じレベルのルータを含み、
   前記鍵は、前記同じレベルの前記ルータによって共有されることを特徴とするネットワーク。
2. 少なくとも前記ＩＰアドレスの第１の部分は、前記ＩＰアドレスの他の部分とは別に暗号化されることを特徴とする請求項１に記載のネットワーク。
3. 前記相互接続されたルータの部分集合は、少なくとも、前記第１の部分とは異なる前記ＩＰアドレスの部分を解読できないことを特徴とする請求項２に記載のネットワーク。
4. 前記ＩＰアドレスは、ルーティングドメインツリー内のルータの統合によって、少なくとも部分的に分割され、
   前記ルーティングドメインツリーは、前記複数の相互接続されたルータ間の相互接続を表し、
   前記統合は、共通の親ルータを共有する複数のルータに対して行われることを特徴とする請求項３に記載のネットワーク。
5. 第１の期間中に、前記相互接続されたルータは、少なくとも前記ＩＰアドレスの一部を解読することができ、
   前記相互接続されたルータは、前記第１の期間中に、少なくとも前記ＩＰアドレスの一部を解読することができ、或いは、第２の期間中に、前記ＩＰアドレスの他の部分を解読することができることを特徴とする請求項１に記載のネットワーク。
6. 前記ＩＰアドレスの前記第１の部分は、鍵を用いて解読され得ることを特徴とする請求項３に記載のネットワーク。
7. 前記相互接続されたルータの前記部分集合は、共通リンクを共有するルータを含み、
   前記鍵は、前記共通リンクを共有する前記ルータによって共有されることを特徴とする請求項１に記載のネットワーク。
8. 前記相互接続されたルータの前記部分集合は、少なくともクロスオーバルータを備えることを特徴とする請求項１に記載のネットワーク。
9. 前記鍵は、前記クロスオーバルータと同じレベルのルータによって共用されることを特徴とする請求項８に記載のネットワーク。
10. 前記相互接続されたルータの前記部分集合は、論理ツリー内に構成されていることを特徴とする請求項１に記載のネットワーク。
11. ネットワークであって、
    複数の相互接続されたルータと、
    前記ネットワークを介して、ＩＰアドレスを含むデータを送信する手段と、
    前記ＩＰアドレスを複数の部分に分割する分割手段と、
    少なくとも前記複数の部分の部分集合を暗号化する暗号化手段とを備え、
    前記相互接続されたルータの部分集合は、少なくとも前記ＩＰアドレスの一部を解読でき、
    前記相互接続されたルータの前記部分集合は、少なくとも前記ＩＰアドレスの一部を解読するための鍵を受け取り、
    前記相互接続されたルータの前記部分集合は、同じレベルのルータを含み、
    前記鍵は、前記同じレベルの前記ルータによって共有されることを特徴とするネットワーク。
12. 複数の相互接続されたルータを含むネットワーク上でデータを共有する方法であって、
    前記ネットワーク上で、ＩＰアドレスを含むデータを送信する工程と、
    前記ＩＰアドレスにおいて、少なくとも、前記データの宛先であるルータの論理的な位置を識別する工程と、
    前記ＩＰアドレスを、複数の部分に分割する工程と、
    少なくとも前記複数の部分の部分集合を暗号化する工程と、
    前記相互接続されたルータの部分集合に対して、少なくとも前記ＩＰアドレスの一部を解読するための鍵を与える工程と、
    前記相互接続されたルータの前記部分集合を用いて、少なくとも前記ＩＰアドレスの一部を解読する工程と、
    同じレベルのルータとの間で前記鍵を共有する工程とを含み、
    前記レベルは、前記相互接続されたルータの前記部分集合で構成されていることを特徴とする記載の方法。
13. 少なくとも前記ＩＰアドレスの第１の部分を、他の部分とは別に暗号化する工程を含むことを特徴とする請求項１２に記載の方法。
14. 少なくとも、前記第１の部分とは異なる前記ＩＰアドレスの部分を解読できない前記相互接続されたルータの前記部分集合を含むことを特徴とする請求項１３に記載の方法。
15. ルーティングドメインツリー内のルータの統合によって、少なくとも部分的に前記ＩＰアドレスを分割する工程を含み、
    前記ルーティングドメインツリーは、前記複数の相互接続されたルータ間の相互接続を表し、前記統合は、共通の親ルータを共有する複数のルータに対して行われることを特徴とする請求項１２に記載の方法。
16. 第１の期間中に、少なくとも前記ＩＰアドレスの一部を解読する工程と、
    前記第１の期間中に、第２の期間のために、少なくとも前記ＩＰアドレスの一部を解読する鍵を受け取る工程とを含むことを特徴とする請求項１２に記載の方法。
17. 鍵を用いて、前記ＩＰアドレスの前記第１の部分を解読する工程を含むことを特徴とする請求項１４に記載の方法。
18. 共通リンクを共有するルータとの間で前記鍵を共有する工程を含み、
    前記相互接続されたルータの前記部分集合は、共通リンクを共有するルータを含むことを特徴とする請求項１２に記載の方法。
19. 前記相互接続されたルータの前記部分集合は、少なくともクロスオーバルータを備えることを特徴とする請求項１２に記載の方法。
20. 前記クロスオーバルータと同じレベルのルータと、前記鍵を共用する工程を有することを特徴とする請求項１９に記載の方法。
21. 前記相互接続されたルータの部分集合は、同じツリーのルータを備えることを特徴とする請求項１２に記載の方法。
22. 前記ＩＰアドレスに対するハッシュ関数を演算する工程を含み、
    前記ＩＰアドレスに対する前記ハッシュ関数の結果として、期待値が生成され、
    前記期待値は、所望のパス上の前記ＩＰアドレスの宛先を表すことを特徴とする請求項１２に記載の方法。
23. 前記期待値を、前記ＩＰアドレスのサフィックスに対応させる工程を有することを特徴とする請求項２２に記載の方法。
24. 前記期待値は、前記ＩＰアドレスに含まれていることを特徴とする請求項２２に記載の方法。
25. 前記ＩＰアドレスに含まれている修飾子から前記期待値を指し示す工程を含み、
    前記期待値は、前記ＩＰアドレスとは別個のテーブル内にあることを特徴とする請求項２２に記載の方法。
26. プロセッサとデータパスとを備えるルータであって、
    データは、前記ルータに対して、前記ルータを介して、及び/又は、前記ルータから送信され、前記データは、前記プロセッサによって処理が施されて、前記データパスに沿って送信され、
    前記データは、前記プロセッサによって、ＩＰアドレスについての処理を含む処理が施され、前記ＩＰアドレスは、前記データの宛先である相互接続されたルータ群内のルータの少なくとも論理的な位置を識別し、
    前記処理は、前記ＩＰアドレスを複数の部分に分割することを含み、少なくとも前記複数の部分の部分集合は暗号化され、
    前記ルータは、少なくとも前記ＩＰアドレスの一部を解読することができ、
    前記ルータには、少なくとも前記ＩＰアドレスの一部を解読するための鍵が与えられ、
    前記ルータは、同じレベルのルータを含む前記相互接続されたルータの部分集合の構成員であり、
    前記鍵は、前記同じレベルのルータによって共用されることを特徴とするルータ。
27. 少なくとも前記ＩＰアドレスの最初の部分は、他の部分とは別に暗号化されることを特徴とする請求項２６に記載のルータ。
28. 前記ルータは、少なくとも前記最初の部分とは異なる前記ＩＰアドレスの部分を解読することができないことを特徴とする請求項２７に記載のルータ。
29. 前記ＩＰアドレスは、ルーティングドメインツリー内のルータの統合により、少なくとも部分的に分割され、
    前記ルーティング領域ツリーは、前記相互接続されたルータ群の間の相互接続を表し、
    前記統合は、共通の親ルータを共有する複数のルータに対して行われることを特徴とする請求項２６に記載のルータ。
30. 前記ルータは、第１の期間中に、少なくとも前記ＩＰアドレスの一部を解読することができ、
    前記ルータは、前記第１の期間中に、少なくとも前記ＩＰアドレスの一部を解読することができ、或いは、第２の期間中に、前記ＩＰアドレスの別の部分を解読することができることを特徴とする請求項２６に記載のルータ。
31. 少なくとも前記ＩＰアドレスの第１の部分は、鍵を用いて解読され得ることを特徴とする請求項２７に記載のルータ。
32. 前記ルータは、共通リンクを共用するルータを含む前記相互接続されたルータの部分集合の構成員であり、
    前記鍵は、前記共通リンクを共用するルータによって共用されることを特徴とする請求項２６に記載のルータ。
33. 前記ルータは、少なくともクロスオーバルータを含む前記相互接続されたルータの部分集合の構成員であることを特徴とする請求項２６に記載のルータ。
34. 前記鍵は、前記クロスオーバルータと同じレベルのルータによって共用されることを特徴とする請求項３３に記載のルータ。
35. 前記ルータは、論理ツリー内に構成されている相互接続されたルータの部分集合の構成員であることを特徴とする請求項２６に記載のルータ。
36. 前記ＩＰアドレスは、該ＩＰアドレスに対するハッシュ関数の結果として、期待値が生成される特性を含み、
    前記期待値は、前記データの宛先への所望のパスを表すことを特徴とする請求項２６に記載のルータ。
37. 前記期待値は、前記ＩＰアドレスのサフィックスに対応することを特徴とする請求項３６に記載のルータ。
38. 前記期待値は、前記ＩＰアドレスに含まれていることを特徴とする請求項３６に記載のルータ。
39. 前記期待値は、前記ＩＰアドレスに明示的に含まれていないが、前記ＩＰアドレスは、前記期待値に対するポインタを含み、
    前記期待値は、テーブル内に含まれていることを特徴とする請求項３６に記載のルータ。

Images