(57)【要約】【課題】  通信システムを構成する各通信端末が公開鍵証明書やその失効情報等の認証情報を所持するまでに必要な通信量および時間を削減することができる通信システムおよび通信端末を提供する。【解決手段】  認証情報を生成または受信した通信端末（ノードＳ）に隣接する通信端末のうち、中継端末として選択された通信端末（ノードＡ，Ｄ，Ｅ）が、受信した認証情報をブロードキャストすることによって、認証情報を生成または受信した通信端末に隣接する全ての通信端末のさらに先に隣接する全ての通信端末に認証情報が転送される。これを繰り返すことによって、通信システムを構成する全ての通信端末が同一の認証情報を所持することができる。そして、認証情報の生成元の通信端末から一斉にかつ一方向に認証情報を転送することが可能となるため、通信システムを構成する各通信端末が認証情報を所持するまでに必要な通信量および時間を削減することができる。【選択図】    図３
2007096919.tif 000002
【特許請求の範囲】
【請求項１】
複数の通信端末を備えた通信システムにおいて、
通信相手の認証に用いられる認証情報を生成した通信端末は、
隣接する通信端末の先に隣接する全ての通信端末に前記認証情報が転送されるように、隣接する通信端末の中から、前記認証情報を中継する中継端末を選択し、
前記中継端末として選択したことを通知する通知情報を他の通信端末へ送信またはブロードキャストし、
前記認証情報をブロードキャストし、
前記認証情報をブロードキャストした通信端末に隣接する通信端末の少なくとも一部は、前記通知情報に基づいて、前記中継端末として選択されたと判断した場合にのみ、受信した前記認証情報をブロードキャストする
ことを特徴とする通信システム。
【請求項２】
複数の通信端末を備えた通信システムにおいて、
通信相手の認証に用いられる認証情報を他の通信端末から受信した通信端末は、
隣接する通信端末の先に隣接する全ての通信端末に前記認証情報が転送されるように、隣接する通信端末の中から、前記認証情報を中継する中継端末を選択し、
前記中継端末として選択したことを通知する通知情報を他の通信端末へ送信またはブロードキャストし、
前記認証情報をブロードキャストし、
前記認証情報をブロードキャストした通信端末に隣接する通信端末の少なくとも一部は、前記通知情報に基づいて、前記中継端末として選択されたと判断した場合にのみ、受信した前記認証情報をブロードキャストする
ことを特徴とする通信システム。
【請求項３】
前記通信システムを構成する複数の通信端末のうち、少なくとも一部の通信端末がさらに定期的または不定期的に前記認証情報をブロードキャストすることを特徴とする請求項１または請求項２に記載の通信システム。
【請求項４】
通信相手の認証に用いられる認証情報を生成する認証情報生成手段と、
隣接する通信端末の先に隣接する全ての通信端末に前記認証情報が転送されるように、隣接する通信端末の中から、前記認証情報を中継する中継端末を選択する選択手段と、
前記中継端末として選択したことを通知する通知情報を他の通信端末へ送信またはブロードキャストする通知情報送信手段と、
前記認証情報をブロードキャストする認証情報送信手段と、
を備えたことを特徴とする通信端末。
【請求項５】
他の通信端末から送信された、通信相手の認証に用いられる認証情報を受信する認証情報受信手段と、
隣接する通信端末の先に隣接する全ての通信端末に前記認証情報が転送されるように、隣接する通信端末の中から、前記認証情報を中継する中継端末を選択する選択手段と、
前記中継端末として選択したことを通知する通知情報を他の通信端末へ送信またはブロードキャストする通知情報送信手段と、
前記通知情報を他の通信端末から受信する通知情報受信手段と、
前記通知情報に基づいて、前記中継端末として選択されたと判断した場合にのみ、受信された前記認証情報をブロードキャストする認証情報送信手段と、
を備えたことを特徴とする通信端末。
【請求項６】
前記認証情報送信手段がさらに定期的または不定期的に前記認証情報をブロードキャストすることを特徴とする請求項５に記載の通信端末。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の通信端末を備え、公開鍵証明書やその失効情報等の認証情報に基づいて、各通信端末が通信相手の認証を行う通信システムに関する。また、本発明は、本通信システムに用いられる通信端末にも関する。
【背景技術】
【０００２】
既存のインターネットにおける通信相手を認証するための基盤技術として、PKI（Public Key Infrastructure：公開鍵基盤）がある。PKIでは、公開鍵証明書（PKC：Public Key Certificate）を用いた認証が行われる。公開鍵証明書は、特定のノードの公開鍵と、その特定ノードに関する情報とを組み合わせたデータに対して、公開鍵証明書の発行者が自身の秘密鍵で暗号化を施した署名情報を含んでいる。従来、公開鍵証明書を発行・管理する機関はCA（Certificate Authority）と呼ばれ、従来の無線通信システムにおいては、基地局やアクセスポイント等の固定基盤がその役を担っていた。
【０００３】
基地局やアクセスポイント等を必要とせず、無線で接続された携帯電話やPDA（Personal Digital Asistance）、無線LANを構成するPC（Personal Computer）等の通信端末同士が相互に無線接続を行い、他の通信端末を介して目的の通信相手と接続するマルチホップ接続により無線通信を行うネットワーク形態は無線アドホックネットワークと呼ばれる。しかし、基地局やアクセスポイント等の固定基盤を持たない無線アドホックネットワークの場合、絶対的に信頼できるCAが存在しないため、公開鍵証明書の発行・管理を行うことができなかった。そこで、各ノードが独自に公開鍵証明書を発行・管理する公開鍵証明書分散管理方式（各通信ノードがCAの役割を担うことからこう呼ばれる）が提案されている（例えば、非特許文献１参照）。
【０００４】
この方式では、各ノードが独自の判断（knowledge：知識や経験）で他ノードの公開鍵証明書を発行して管理する。例えば、ノードＡはノードＢに対して公開鍵証明書を発行しておらず、ノードＢと信頼関係を結んでいないとする。また、ノードＡが直接信頼する（公開鍵証明書を発行している）ノードＣはノードＢを直接信頼しているとする。この場合、ノードＡはノードＣの公開鍵証明書を発行しており、ノードＣはノードＢの公開鍵証明書を発行している。ノードＡが発行した公開鍵証明書にはノードＣの公開鍵とノードＡの署名情報が含まれ、ノードＣが発行した公開鍵証明書にはノードＢの公開鍵とノードＣの証明情報が含まれる。
【０００５】
ノードＡがノードＢと通信を行う場合、ノードＡはノードＣからノードＢの公開鍵証明書を受け取り、自身が有するノードＣの公開鍵証明書と、取得したノードＢの公開鍵証明書とを用いてノードＢの認証を行う。ノードＢの公開鍵の正当性および公開鍵証明書の有効性を確認できた場合に、ノードＡはノードＢを信頼する。このようにして、ノードＡとノードＢとの間で結ばれる信頼関係を信頼の輪と呼んでいる。
【０００６】
非特許文献１に記載された方式において、各ノードは、自身が信頼するノードと公開鍵証明書を交換することにより、それらのノードと信頼関係を結ぶ。さらに、それらのノードは他のノードと信頼関係を結んでおり、各ノードは、その信頼関係を利用して被認証ノードまでの信頼の輪を構築する。
【０００７】
以下、図５を参照し、従来の公開鍵証明書分散管理方式における信頼の輪の構築方法を詳細に説明する。図５（ａ）は、通信システムを構成するノード１〜８の信頼関係を示している。各ノードを結ぶ矢印の根元にあるノードが、その矢印の先にあるノードを信頼している。例えば、ノード１はノード２を信頼しており、ノード２の公開鍵証明書を発行している。この公開鍵証明書にはノード２の公開鍵とノード１の署名情報が含まれている。
【０００８】
以下の説明では、通信を開始するノードを認証ノード、通信相手となるノードを最終被認証ノードと呼ぶ。図５（ａ）において、ノード１（認証ノード）が、信頼関係を直接結んでいないノード４（最終被認証ノード）の認証を行うとする。まず、認証のための初期準備として、以下の動作が行われる。
【０００９】
（公開鍵生成）
各ノードは公開鍵と秘密鍵のペアを作成する。
（公開鍵証明書の発行）
各ノードは、既に取得している他ノードについての独自の知識に基づいて、信頼する他ノードの公開鍵に関する公開鍵証明書を発行する。
（リポジトリの作成）
各ノードは、発行した公開鍵証明書をリポジトリ（公開鍵証明書を格納するためにメモリやハードディスク等に構築されるデータベース）に格納し、管理する。
（リポジトリ交換）
各ノードは、各々が所有するリポジトリに格納した公開鍵証明書を各ノード同士の間で交換（リポジトリ交換）し、取得した公開鍵証明書をリポジトリに格納する。各ノードは、電波が届いて直接通信が可能な隣接ノードと定期的に上記のリポジトリ交換を行い（図５（ｂ））、最終的に全ノードのリポジトリを収集する。図５（ｃ）は、通信システムを構成する全ノードの公開鍵証明書の取得が終了した定常状態におけるノード１のリポジトリ内の公開鍵証明書を示している。図中において、例えばノード１がノード２に発行した公開鍵証明書は１→２と表現されている。
【００１０】
続いて、ノードの認証を行う際、ノード１（認証ノード）は、信頼の輪を構築するのに必要な公開鍵証明書を自身のリポジトリから探索する。探索の結果、ノード１（認証ノード）は、ノード４（最終被認証ノード）までの信頼の輪がノード１→ノード２→ノード３→ノード４と繋がると判断する（図５（ｄ））。従来の公開鍵証明書分散管理方式では、全ノードの公開鍵証明書が一旦リポジトリに格納された後には、信頼の輪を短時間で探索することができる。
【００１１】
続いて、ノード１（認証ノード）は、信頼の輪に含まれるノードの公開鍵の正当性および公開鍵証明書の有効性を確認する。公開鍵の正当性を確認するため、ノード１（認証ノード）は、自身がノード２の公開鍵に対して発行した公開鍵証明書をリポジトリから取り出し、自身の公開鍵を用いて署名情報を復号化し、情報が正しいか否かを確認する。情報が正しかった場合、ノード１（認証ノード）がノード２の公開鍵の正当性を確認できたことになる。同様にして、ノード１（認証ノード）は、ノード２がノード３の公開鍵に対して発行した公開鍵証明書をリポジトリから取り出し、ノード２の公開鍵を用いて署名情報を復号化し、情報が正しいか否かを確認する。情報が正しかった場合、ノード１（認証ノード）がノード３の公開鍵の正当性を確認できたことになる。同様にして、ノード１（認証ノード）はノード４（最終被認証ノード）の公開鍵の正当性を確認する。
【００１２】
続いて、ノード１（認証ノード）は、公開鍵証明書の有効性を確認するため、無効となった（失効した）公開鍵証明書の一覧が記載された失効証明書リスト（CRL：Certificate Revocation List）を検証する。各ノードは、失効証明書リスト内の情報を常に最新に保つため、公開鍵証明書を発行したノードに対して、公開鍵証明書の有効性を定期的に確認する必要がある。最終的に、信頼の輪に含まれる全ノードの公開鍵証明書がいずれも失効証明書リストに存在しなかった場合に、ノード１（認証ノード）はノード４（最終被認証ノード）までの信頼の輪が有効であると判断する。
【００１３】
一方、非特許文献２には他の公開鍵証明書分散管理方式が記載されている。非特許分権２に記載された公開鍵証明書分散管理方式においては、通信相手となるノードの認証を行う必要性が発生したときに、認証ノードが、各ノードから必要なノードのみの公開鍵証明書を取得するようにしている。これによって、ネットワークに参加する全てのノードの公開鍵を各ノードが管理する非特許文献１に記載の公開鍵分散管理方式と比較して、通信資源や各ノードの資源を無駄に使うことがなく、公開鍵の管理コストを低減することが可能となっている。
【非特許文献１】Srdjan Capkun，Levente Buttyan，and Jean-Pierre Hubaux，"Self-Organized Public-Key Management for Mobile Ad Hoc Networks"，IEEE TRANSACTIONS ON MOBILE COMPUTING， Vol.2，No.2，JANUARY-MARCH 2003，p.52-63
【非特許文献２】北田夕子，荒川豊，竹森敬祐，渡邊晃，「無線アドホックネットワークに適したルーティング情報を用いたオンデマンド公開鍵分散管理方式」，CSS2004，October 2004
【発明の開示】
【発明が解決しようとする課題】
【００１４】
非特許文献１に記載された公開鍵証明書分散管理方式には以下の問題点がある。すなわち、リポジトリに格納されている公開鍵証明書が少ない場合、認証に失敗する確率が高い。また、この方式では各ノードが公開鍵証明書を収集することに主眼が置かれており、ノード同士でのリポジトリの交換によって、各ノードがばらばらに通信を行うため、ネットワーク内の全ノードの公開鍵証明書を収集するまでに多大な通信量および時間を要する。ノード数が多い大規模ネットワークでは、この通信量および時間は指数関数的に増加する。
【００１５】
また、各ノードが定期的に公開鍵証明書を交換し合うため、全ノードが公開鍵証明書を取得してからも通信量が掛かる。さらに、公開鍵証明書の有効性を確認するために、公開鍵証明書を発行した全ノードに対して公開鍵証明書の有効性を定期的に確認し、失効証明書リストを更新する処理負荷が大きい。
【００１６】
また、非特許文献２に記載された公開鍵証明書分散管理方式では、認証要求が発生した時点のオンデマンドで公開鍵証明書の収集が行われるため、公開鍵証明書の有効性の確認のための通信が不要になる。しかし、この方式では、公開鍵証明書を収集するため、認証ノードおよび中継ノードの全てが、公開鍵証明書を要求するための情報をブロードキャストするため、ノード密度が高いネットワークにおいては、通信量が無視できなくなる。
【００１７】
本発明は、上述した問題点に鑑みてなされたものであって、通信システムを構成する各通信端末が公開鍵証明書やその失効情報等の認証情報を所持するまでに必要な通信量および時間を削減することができる通信システムおよび通信端末を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明は、上記の課題を解決するためになされたものであり、本発明の通信システムは、複数の通信端末を備え、それら複数の通信端末のうち、通信相手の認証に用いられる認証情報（公開鍵証明書やその失効情報等）を生成した通信端末は、後述するOLSR（Optimized Link State Routing）プロトコル等に基づいて、隣接する（すなわち、直接通信が可能な）通信端末の先に隣接する全ての通信端末に認証情報が転送されるように、隣接する通信端末の中から、認証情報を中継する中継端末を選択する。そして、認証情報を生成した通信端末は、中継端末として選択したことを通知する通知情報を他の通信端末へ送信またはブロードキャストし、認証情報をブロードキャストする。認証情報をブロードキャストした通信端末に隣接する通信端末の少なくとも一部は、上記の通知情報に基づいて、中継端末として選択されたと判断した場合にのみ、受信した認証情報をブロードキャストする。認証情報を中継する中継端末の選択および通知情報の送信が認証情報の生成よりも前であるか、後であるかは問わない。
【００１９】
また、本発明の通信システムは、複数の通信端末を備え、それら複数の通信端末のうち、認証情報を他の通信端末から受信した通信端末は、OLSRプロトコル等に基づいて、隣接する通信端末の先に隣接する全ての通信端末に認証情報が転送されるように、隣接する通信端末の中から、認証情報を中継する中継端末を選択する。そして、認証情報を受信した通信端末は、中継端末として選択したことを通知する通知情報を他の通信端末に送信またはブロードキャストし、認証情報をブロードキャストする。認証情報をブロードキャストした通信端末に隣接する通信端末の少なくとも一部は、通知情報に基づいて、中継端末として選択されたと判断した場合にのみ、受信した認証情報をブロードキャストする。認証情報を中継する中継端末の選択および通知情報の送信が認証情報の受信よりも前であるか、後であるかは問わない。
【００２０】
上記の通信システムによれば、認証情報を生成または受信した通信端末に隣接する通信端末のうち、中継端末として選択された通信端末が、受信した認証情報をブロードキャストすることによって、認証情報を生成または受信した通信端末に隣接する全ての通信端末のさらに先に隣接する全ての通信端末に認証情報が転送される。これを繰り返すことによって、通信システムを構成する全ての通信端末が同一の認証情報を所持することができる。そして、認証情報の生成元の通信端末から一斉にかつ一方向に（認証情報の生成元の通信端末から見たホップ数が増加する方向に）認証情報を転送することが可能となるため、通信システムを構成する各通信端末が認証情報を所持するまでに必要な通信量および時間を削減することができる。
【００２１】
特に、認証情報をブロードキャストした通信端末に隣接する通信端末の少なくとも一部が、中継端末として選択されたと判断した場合にのみ認証情報をブロードキャストし、中継端末として選択されなかったと判断した場合には認証情報をブロードキャストしないので、不要な通信量を大幅に削減することができる。また、上記の認証情報が、証明書の有効性の確認に必要な証明書の失効情報である場合には、全ての通信端末が証明書の有効性についての最新の情報を所持することが可能となるため、証明書の有効性を他の通信端末に確認するための通信が不要となる。したがって、各通信端末の失効情報の管理負荷を削減することができる。
【００２２】
また、本発明の通信システムにおいて、通信システムを構成する複数の通信端末のうち、少なくとも一部の通信端末がさらに定期的または不定期的に認証情報をブロードキャストしてもよい。これによって、一時的にどの通信端末からも電波の届かない場所にいた通信端末が認証情報を取得する可能性を高めると共に、通信システムに参加する各通信端末が有する認証情報の同期を図ることができる。
【００２３】
また、本発明の通信端末は、認証情報生成手段、選択手段、通知情報送信手段、および認証情報送信手段を備え、認証情報生成手段が生成した認証情報を認証情報送信手段がブロードキャストする。選択手段は、OLSRプロトコル等に基づいて、隣接する通信端末の先に隣接する全ての通信端末に認証情報が転送されるように、隣接する通信端末の中から、認証情報を中継する中継端末を選択する。通知情報送信手段は、中継端末として選択したことを通知する通知情報を他の通信端末へ送信またはブロードキャストする。認証情報を中継する中継端末の選択および通知情報の送信が認証情報の生成よりも前であるか、後であるかは問わない。
【００２４】
また、本発明の通信端末は、認証情報受信手段、選択手段、通知情報送信手段、および認証情報送信手段を備え、他の通信端末から送信された認証情報を認証情報受信手段が受信し、その認証情報を認証情報送信手段がブロードキャストする。選択手段および通知情報送信手段は上記と同様である。特に本発明の認証情報送信手段は、通知情報に基づいて、中継端末として選択されたと判断した場合にのみ、受信された認証情報をブロードキャストする。認証情報を中継する中継端末の選択および通知情報の送信が認証情報の受信よりも前であるか、後であるかは問わない。
【００２５】
上記の通信端末によれば、認証情報を生成または受信した通信端末に隣接する通信端末のうち、認証情報を中継する中継端末として選択された通信端末が認証情報を受信し、ブロードキャストすることによって、認証情報を生成または受信した通信端末に隣接する全ての通信端末のさらに先に隣接する全ての通信端末に認証情報が転送される。これを繰り返すことによって、通信システムを構成する全ての通信端末が同一の認証情報を所持することができる。そして、認証情報の生成元の通信端末から一斉にかつ一方向に（認証情報の生成元の通信端末から見たホップ数が増加する方向に）認証情報を転送することが可能となるため、通信システムを構成する各通信端末が認証情報を所持するまでに必要な通信量および時間を削減することができる。
【００２６】
特に、他の通信端末から認証情報を受信した通信端末が、中継端末として選択されたと判断した場合にのみ認証情報をブロードキャストし、中継端末として選択されなかったと判断した場合には認証情報をブロードキャストしないので、不要な通信量を大幅に削減することができる。また、上記の認証情報が、証明書の有効性の確認に必要な証明書の失効情報である場合には、前述したように、証明書の有効性を他の通信端末に確認するための通信が不要となり、各通信端末の失効情報の管理負荷を削減することができる。
【００２７】
また、本発明の通信端末において、認証情報送信手段が定期的または不定期的に認証情報をブロードキャストしてもよい。これによって、一時的にどの通信端末からも電波の届かない場所にいた通信端末が認証情報を取得する可能性を高めると共に、通信システムに参加する各通信端末が有する認証情報の同期を図ることができる。
【発明の効果】
【００２８】
本発明によれば、通信システムを構成する各通信端末が公開鍵証明書やその失効情報等の認証情報を所持するまでに必要な通信量および時間を削減することができるという効果が得られる。
【発明を実施するための最良の形態】
【００２９】
以下、図面を参照し、本発明の実施形態を説明する。図１は、本発明の一実施形態による通信システムの構成例を示している。本通信システムは、通信端末としての機能を有するノードＡ〜Ｎ，Ｓを備えている。ノード同士を結ぶ線は、各ノードが互いに電波の到達範囲内に位置し、直接通信が可能であることを示している。図２は各ノードの構成を示している。図２において、アンテナ１０は、他のノードと電波の送受信を行うためのものである。通信部１１は、データの送受信に係る変調・復調処理等を行う。操作部１２は、ユーザによって操作されるキー等を備えている。表示部１３は、ユーザに対して様々な情報を表示する。
【００３０】
記憶部１４は、記録媒体およびデータの読み書き用の回路を備えており、各種の情報を記憶する。リポジトリには、信頼するノードに対して自ノードが発行した公開鍵証明書と、他ノードから取得した公開鍵証明書とが格納される。後述する手法によって、公開鍵証明書の発行を受けた全てのノードの公開鍵証明書がリポジトリに格納される。１ホップ隣接ノード情報領域には、自ノードに隣接する（電波が届いて直接通信が可能な）ノード（１ホップ隣接ノードとする）の情報が格納される。２ホップ隣接ノード情報領域には、１ホップ隣接ノードに隣接するノード（２ホップ隣接ノードとする。自ノードおよび１ホップ隣接ノードは含まれない。）の情報が格納される。MPR情報領域には、後述するMPR集合に属するノードの情報が格納される。MPRセレクタ情報領域には、自ノードをMPR集合として選択している他ノードの情報が格納される。失効証明書リスト領域には、無効となった公開鍵証明書の一覧が記載された失効証明書リストが格納される。
【００３１】
制御部１５はＣＰＵ（Central Processing Unit）を備え、上記の各構成の動作を制御すると共に、各種の情報処理を行う。上述した構成は一例であり、上記以外の構成を追加したり、不要な構成を削除したりしてもよい。
【００３２】
本実施形態における各ノードは、自身が他ノードに対して公開鍵証明書を発行した時点や、公開鍵証明書を失効させた時点で、公開鍵証明書またはその失効情報（どの公開鍵証明書が失効したのかを特定するための情報を少なくとも含むもの）を通信システム全体にフラッディングする。フラッディングとは、送信元の端末が情報をブロードキャストし、それを受信した全ての端末がその情報を転送することを繰り返すことによって、全端末に情報を配信する手法である。各ノードが、OLSR（Optimized Link State Routing）プロトコルに基づいてフラッディングを行うことによって、無駄なフラッディングを防ぐことが可能となっている。OLSRプロトコルの詳細は、例えば下記の文献に記載されている。
S.Corson and J.Macker，"Mobile ad hoc networking(MANET): Routing protocol performance issues and evaluation consideration"，IETF RFC25010，Jan，1999
【００３３】
例えば、ノードＳがブロードキャストを行うと、ノードＳに隣接するノードＡ，Ｂ，Ｃ，Ｄ，Ｅに電波が届き、これらのノードがノードＳからの情報を受信する（図３（ａ））。これらのノードの全てがブロードキャストを行うと、これらのノードに隣接するノードＦ，Ｇ，Ｈ，Ｉ，Ｊ，Ｍに電波が届き、これらのノードが情報を受信する。しかし、例えばノードＭはノードＣおよびＥの両方から情報を受信することになり、不要な通信が発生することが分かる。
【００３４】
OLSRプロトコルでは、より効率的なフラッディングを行うため、ブロードキャストによって送信元からの電波が届いた１ホップ隣接ノードのうち、その先に隣接する全ての２ホップ隣接ノードへ情報を転送するのに必要最小限の数のノードが再送信ノードとなって、ブロードキャストを行う。このように、１ホップ隣接ノードの先に存在する全ての２ホップ隣接ノードへ情報が転送されるような１ホップ隣接ノードの集合はMPR（Multi Point Relay）集合と呼ばれる。
【００３５】
後述するように、ノードＳに隣接するノードのうち、ノードＡ，Ｄ，ＥがMPR集合に属している。これらのノードのみがブロードキャストを行い、残りの１ホップ隣接ノード（ノードＢおよびＣ）は情報を受信してもブロードキャストしない。ノードＦ，Ｇ，ＨはノードＡから情報を受信可能であり、ノードＪはノードＤから情報を受信可能であり、ノードＩ，ＭはノードＥから情報を受信可能である（図３（ｂ））。したがって、１ホップ隣接ノードのうちの一部のノードがブロードキャストを行うだけで、１ホップ隣接ノードの先に隣接する全ての２ホップ隣接ノードまで情報を転送することができるので、効率的なフラッディングを行うことができる。
【００３６】
ノードＡ，Ｄ，Ｅがブロードキャストを行うと、同様にそれらの各ノードのMPR集合に属するノードのみがブロードキャストを行う。これを繰り返すことによって、不要な通信の発生を削減しながら、通信システムを構成する全てのノードに情報を配信することができる。
【００３７】
次に、本実施形態による通信システムの詳細な動作を説明する。まず、MPR集合に属するノードの選択方法を説明する。各ノードは、HELLOメッセージを定期的に周辺のノードへ送信する。これによって、各ノードは他のノードの情報を取得する。初期状態では、各ノードは自身の存在を周辺のノードに通知するために、自身のアドレス（識別情報）を１ホップ隣接ノード情報として含むHELLOメッセージを送信する。すなわち、各ノードの制御部１５はHELLOメッセージを生成して通信部１１へ出力する。このHELLOメッセージは通信部１１で変調された後、アンテナ１０から他のノードへ送信される。送信されたHELLOメッセージは、隣接するノードのアンテナ１０で受信され、通信部１１で復調された後、制御部１５へ出力される。制御部１５は、HELLOメッセージに含まれる１ホップ隣接ノードのアドレスを記憶部１４の１ホップ隣接ノード情報領域に格納する。
【００３８】
また、各ノードは、自身に隣接するノードのアドレス（識別情報）を２ホップ隣接ノード情報として含むHELLOメッセージを送信する。このHELLOメッセージは、隣接するノードによって受信される。受信したノードの制御部１５は、HELLOメッセージに含まれるアドレスのうち、記憶部１４の１ホップ隣接ノード情報領域に格納されたアドレスに含まれないものを記憶部１４の２ホップ隣接ノード情報領域に格納する。上記のようにして、各ノードは１ホップ隣接ノードおよび２ホップ隣接ノードの情報を取得する。
【００３９】
各ノードは、Willingnessという０〜７の範囲の値を持っており、この値が高ければ高いほどMPR集合に選ばれやすい。Willingnessの値はHELLOメッセージに付加されており、各ノードに通知される。HELLOメッセージを受信したノードの制御部１５は、HELLOメッセージに含まれる他ノードのアドレスとWillingnessの値とを関連付けて、記憶部１４の１ホップ隣接ノード情報領域または２ホップ隣接ノード情報領域に格納する。このWillingnessの値が０のノードはMPR集合に選ばれず、７のノードは積極的にMPR集合に選ばれる。電力供給源を持つノードや電池残量の多いノードでWillingnessの値を高く設定したり、隣接ノードへの接続数が多いノードでWillingnessの値を高く設定したりすること等が考えられるが、本実施形態ではWillingnessの設定方法を特に限定しない。図１における各ノードのWillingnessの値は、ノードＡが７（WILL_ALWAYS）、ノードＥが５（WILL_HIGH）、その他のノードが３（WILL_DEFAULT）であるとする。
【００４０】
実際に情報を中継するノードの集合であるMPR集合は、以下のようにして決定される。ここでは一例として、ノードＳについてのMPR集合に属するノードの選択方法を説明する。ノードＳが知っているノードはノードＫ，Ｌ，Ｎ以外の全ノードであり、それらがMPR集合の選択対象となる。ノードＳの制御部１５は、記憶部１４の１ホップ隣接ノード情報領域および２ホップ隣接ノード情報領域に格納された各ノードの情報に基づいて、「Ｎ」と「Ｎ２」という２つの集合を作成する（図４（ａ））。「Ｎ」は、MPR集合となるノードの候補を示す１ホップ隣接ノードの集合であり、ノードＡ，Ｂ，Ｃ，Ｄ，Ｅが含まれる。「Ｎ２」は、まだMPR集合となるノードが選択されていないために、情報が届かないことを示す２ホップ隣接ノードの集合であり、ノードＦ，Ｇ，Ｈ，Ｉ，Ｊ，Ｍが含まれる。
【００４１】
続いて、ノードＳの制御部１５は、「Ｎ」に含まれるノードの中から、Willingnessの値が最も高いノードＡをMPR集合として選択する。もし、同じWillingnessの値を持つノードが複数あった場合には、「Ｎ２」に含まれるノードのより多くへ情報を転送できるノードがMPR集合として選択される。ノードＦ，Ｇ，ＨはノードＡから情報を受け取れるようになるので、制御部１５はそれらのノードを「Ｎ２」から削除する。このときの「Ｎ」および「Ｎ２」は図４（ｂ）のようになる。
【００４２】
続いて、制御部１５は、「Ｎ」に含まれる残りのノードの中から、Willingnessの値が最も高いノードＥをMPR集合として選択する。ノードＩ，ＭはノードＥから情報を受け取れるようになるので、制御部１５はそれらのノードを「Ｎ２」から削除する。このときの「Ｎ」および「Ｎ２」は図４（ｃ）のようになる。「Ｎ２」から全てのノードが削除されるまで上記の処理が繰り返される。続いて、ノードＤがMPR集合として選択されて、ノードＪが「Ｎ２」から削除されるため、MPR集合に属するノードの選択処理が終了する。結果として、MPR集合に属するノードは、ノードＡ，Ｄ，Ｅとなる。
【００４３】
MPR集合の計算を行った後、ノードＳは、MPR集合として選択されていることを通知するためのHELLOメッセージ（通知情報）をノードＡ，Ｄ，Ｅへ送信する。HELLOメッセージを受信した各ノードの制御部１５は、HELLOメッセージに含まれるノードＳのアドレスを記憶部１４のMPRセレクタ情報領域に格納する。MPRセレクタ情報領域に格納された情報を参照することによって、各ノードは、自身がどのノードのMPR集合として選択されているのかを知ることができる。ノードＳ以外の他のノードも、上記と同様にしてMPR集合を決定する。上記のHELLOメッセージの送信はブロードキャストであってもよい。この場合には、MPR集合として選択されたノードのアドレスがHELLOメッセージ中に含まれていることが望ましい。ブロードキャストされたHELLOメッセージを受信したノードは、HELLOメッセージに含まれる、MPR集合として選択されたノードのアドレスが自身のアドレスと一致した場合に、自身がMPR集合として選択されたと判断し、送信元のノードのアドレスを記憶部１４のMPRセレクタ情報領域に格納する。
【００４４】
次に、公開鍵証明書の発行時およびその失効時の通信システムの動作を説明する。なお、各ノードは、一度受信した情報と重複する情報を再度受信した場合には、再度受信した方の情報を削除（破棄）するものとする。したがって、同じ情報を複数回受信した場合でも、各ノードが行うブロードキャストは最大で１回である。以下の説明では、ノードＳが情報の発信源となる場合を説明するが、他のノードが発信源となる場合も同様である。
【００４５】
ノードＳが、あるノードに対して公開鍵証明書を発行する場合、ノードＳの制御部１５は公開鍵証明書を生成し、記憶部１４のリポジトリに格納する。また、ノードＳが、あるノードに対して公開鍵証明書を失効させる場合、ノードＳの制御部１５は失効情報を生成すると共に、記憶部１４の失効証明書リスト領域に格納された失効証明書リストを更新する。続いて、ノードＳは公開鍵証明書またはその失効情報をブロードキャストする。ノードＳにおいて、前述したMPR集合の選択およびHELLOメッセージ（MPR集合として選択されていることを各ノードに通知するためのもの）の送信は、公開鍵証明書または失効情報のブロードキャストよりも前に行われればよく、公開鍵証明書または失効情報の生成よりも前または後のいずれでもよい。また、公開鍵証明書または失効情報に対して、MPR集合として選択されていることを各ノードに通知する情報を付加したものをノードＳがブロードキャストするようにしてもよい。
【００４６】
ブロードキャストされた公開鍵証明書または失効情報は、ノードＳに隣接するノードＡ，Ｂ，Ｃ，Ｄ，Ｅによって受信される。各ノードの制御部１５は、公開鍵証明書を受信した場合には、その公開鍵証明書を記憶部１４のリポジトリに格納する。また、制御部１５は、失効情報を受信した場合には、その失効情報に基づいて、記憶部１４の失効証明書リスト領域に格納された失効証明書リストを更新する。
【００４７】
また、制御部１５は、公開鍵証明書または失効情報の送信元のノードのアドレスが、記憶部１４のMPRセレクタ情報領域に格納されたアドレスのいずれかと一致するか否かを判定する。送信元のノードのアドレスが、MPRセレクタ情報領域に格納されたアドレスのいずれかと一致した場合にのみ、制御部１５は公開鍵証明書または失効情報をブロードキャストする処理を行う。すなわち、図１のノードＡ，Ｄ，Ｅのみが公開鍵証明書または失効情報をブロードキャストする。前述したとおり、これらのノードはMPR集合としてノードＳによって選択されたノードであり、これらのノードがブロードキャストを行うことによって、ノードＳの全ての２ホップ隣接ノード（ノードＦ，Ｇ，Ｈ，Ｉ，Ｍ）へ公開鍵証明書または失効情報を転送することができる。
【００４８】
ノードＡ，Ｄ，ＥもノードＳと同様にMPR集合を決定しており、これらのノードの先に隣接するノードＦ，Ｇ，Ｈ，Ｉ，Ｍの中から、MPR集合として選択されたノードのみが公開鍵証明書または失効情報をブロードキャストする。上記の動作が繰り返されることによって、連鎖的に情報が再送信されていき、最終的に通信システム内の全てのノードが、ノードＳによって生成された公開鍵証明書または失効情報を所持することになる。
【００４９】
ノードの認証を行う必要性が発生した場合に信頼の輪の構築を行う動作は、前述した非特許文献１に記載の公開鍵証明書分散管理方式と同様である。したがって、全ノードの公開鍵証明書が一旦リポジトリに格納された後には、信頼の輪を短時間で探索することができる。しかし、本実施形態では、各ノードが公開鍵証明書の失効情報もリアルタイムでフラッディングすることによって、常に最新の状態の失効証明書リストを各ノードが所持することになるので、公開鍵証明書の有効性を確認するための通信が不要となる。
【００５０】
次に、本実施形態の変形例を説明する。公開鍵証明書または失効情報のフラッディングが行われている際に、通信システム内の他のノードから電波が届かない電波範囲外にいて、公開鍵証明書または失効情報を受信することができないノードが存在する場合もある。そこで、一部のノードが、自身の有する公開鍵証明書または失効情報を定期的または不定期的に通信システム全体にフラッディングすることによって、電波範囲外にいたノードが電波範囲内に入った場合に公開鍵証明書または失効情報を受信することができるようにする。フラッディングの間隔は特に限定されず、所定間隔でも不定間隔でもよい。
【００５１】
一部のノードがフラッディングする公開鍵証明書は、自身が発行した公開鍵証明書でもよいし、他のノードから取得した公開鍵証明書でもよい。また、記憶部１４のリポジトリに格納されている、単一または一部の複数の公開鍵証明書をフラッディングしてもよいし、全ての公開鍵証明書をフラッディングしてもよい。失効情報についても、単一または一部の複数の失効情報をフラッディングしてもよいし、全ての失効情報（これを一元管理するもの、例えば失効証明書リスト（CRL）でもよい）をフラッディングしてもよい。
【００５２】
定期的または不定期的にフラッディングを行うノードは、例えばWillingnessの値が高いノードとすればよい。Willingnessの値が高いか否かの判断においては、Willingnessの値が７である、あるいはWillingnessの値が所定値以上である等の基準を設ければよい。また、他のノードから公開鍵証明書を多く発行されているノード（すなわち多くの他のノードから信頼されているノード）が定期的または不定期的にフラッディングを行ってもよい。本実施形態の通信システムを構成する各ノードは、全てのノードの公開鍵証明書を所持することができるので、それが示す信頼関係の情報に基づいてフラッディングを行うか否かを判断する。この判断においては、公開鍵証明書の被発行数が所定数以上である、あるいは全てのノードの中で自ノードの公開鍵証明書の被発行数が、上位から数えて所定番目以内である等の基準を設ければよい。また、公開鍵証明書を発行し、フラッディングしたノードが同じ公開鍵証明書を定期的または不定期的にフラッディングしてもよい。
【００５３】
本変形例によれば、一時的にどのノードからも電波の届かない場所にいたノードがいずれかのノードから電波の届く場所に来た際に、以前受信できなかった公開鍵証明書または失効情報を受信する可能性を高めることができる。また、通信システムに参加する各ノードが有する公開鍵証明書または失効情報の同期を図る（すなわち、より長い時間、各ノードが同じ公開鍵証明書または失効情報を所持しているようにする）ことができる。
【００５４】
上述したように、本実施形態による通信システムでは、公開鍵証明書または失効情報を生成したノード（上記の例ではノードＳ）に隣接するノード（上記の例ではノードＡ，Ｂ，Ｃ，Ｄ，Ｅ等）、あるいは公開鍵証明書または失効情報を他のノードから受信したノードに隣接するノードのうち、MPR集合に属するノード（すなわち公開鍵証明書または失効情報を中継する中継ノード）として選択されたノード（上記の例ではノードＡ，Ｄ，Ｅ等）が、受信した公開鍵証明書または失効情報をブロードキャストする。この結果、公開鍵証明書または失効情報を生成または受信したノードに隣接する全てのノード（１ホップ隣接ノード）のさらに先に隣接する全てのノード（２ホップ隣接ノード）に公開鍵証明書または失効情報が転送される。
【００５５】
これを繰り返すことによって、通信システムを構成する全てのノードが同一の情報を所持することができる。そして、公開鍵証明書または失効情報の生成元のノードから一斉にかつ一方向に（情報の生成元のノードから見たホップ数が増加する方向に）公開鍵証明書または失効情報を転送することが可能となるため、通信システムを構成する各ノードが公開鍵証明書または失効情報を所持するまでに必要な通信量および時間を削減することができる。特に、公開鍵証明書または失効情報をブロードキャストしたノードに隣接するノードのうち、中継ノードとして選択されたと判断したノードのみが公開鍵証明書または失効情報をブロードキャストするので、効率的なフラッディングが可能となり、不要な通信量を大幅に削減することができる。
【００５６】
また、失効情報を生成したノードから他の全てのノードへ向けて上記のように次々と失効情報が転送される結果、常に最新の状態の失効証明書リストを全てのノードが所持する状態が保たれることになるので、公開鍵証明書の有効性を確認するための通信が不要となる。したがって、各ノードの失効情報の管理負荷を削減することができる。
【００５７】
以上、図面を参照して本発明の実施形態について詳述してきたが、具体的な構成はこれらの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【図面の簡単な説明】
【００５８】
【図１】本発明の一実施形態による通信システムの構成を示す構成図である。
【図２】本発明の一実施形態による通信システムが備える通信端末の構成を示すブロック図である。
【図３】本発明の一実施形態における認証情報の配信方法を説明するための説明図である。
【図４】本発明の一実施形態におけるMPR集合の決定方法を説明するための説明図である。
【図５】従来の通信システムにおける信頼の輪の構築方法を説明するための説明図である。
【符号の説明】
【００５９】
１０・・・アンテナ、１１・・・通信部、１２・・・操作部、１３・・・表示部、１４・・・記憶部、１５・・・制御部
【図１】
2007096919.tif 000003
【図２】
2007096919.tif 000004
【図３】
2007096919.tif 000005
【図４】
2007096919.tif 000006
【図５】
2007096919.tif 000007