(57)【特許請求の範囲】
【請求項１】
認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムにおいて、
前記認証端末は、
前記公開鍵の検証に必要な情報を要求するための要求情報を送信する第1の送信手段と、
前記中継端末から、前記情報を含む検証用情報を受信する第1の受信手段と、
該検証用情報に基づいて前記公開鍵を検証する検証手段と、
を具備し、
前記中継端末は、
前記要求情報によって要求された情報を所持していない場合には、前記要求情報を他の中継端末へ送信し、前記要求情報によって要求された情報を所持している場合には、前記情報を含む検証用情報を前記認証端末または他の中継端末へ送信する第２の送信手段と、
を具備する
ことを特徴とする通信システム。
【請求項２】
認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムにおいて、
前記認証端末は、
前記公開鍵の検証に必要な第１の証明書情報を要求するための要求情報をブロードキャストする第１の送信手段と、
前記第１の証明書情報を含む検証用情報を前記中継端末から受信する第１の受信手段と、
前記検証用情報に基づいて前記公開鍵を検証する検証手段と、
を具備し、
前記中継端末は、
証明書情報を記憶する第１の記憶手段と、
前記要求情報を受信する第２の受信手段と、
該要求情報に基づいて、前記第１の証明書情報が前記第１の記憶手段に記憶されているかどうか判定する判定手段と、
記憶されていないと判定された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、該要求情報をブロードキャストし、記憶されていると判定された場合には、前記要求情報に付加された証明書情報と前記第１の証明書情報とを含む検証用情報を前記認証端末へ送信する第２の送信手段と、
を具備する
ことを特徴とする通信システム。
【請求項３】
前記第１の送信手段は、前記公開鍵の検証に必要な第１の証明書情報を要求するための、経由情報を含む要求情報をブロードキャストし、
前記第２の送信手段は、
前記第１の証明書情報が前記第１の記憶手段に記憶されていないと判定された場合には、前記要求情報に含まれる前記経由情報を更新し、前記要求情報をブロードキャストし、
前記第１の証明書情報が前記第１の記憶手段に記憶されていると判定された場合には、前記第１の証明書情報と、経由する端末を示す返信経由情報とを含む検証用情報を前記返信経由情報が示す前記認証端末または前記中継端末へ送信し、
前記検証用情報が受信された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、前記返信経由情報が示す前記認証端末または前記中継端末へ送信する
ことを特徴とする請求項２に記載の通信システム。
【請求項４】
前記認証端末はさらに、信頼する中継端末を記憶する第２の記憶手段を具備し、
前記第１の送信手段は、前記公開鍵の検証に必要な第１の証明書情報を要求するための要求情報を、前記第２の記憶手段によって記憶されている前記中継端末へ送信し、
前記第１の記憶手段は、証明書情報および信頼する他の中継端末を記憶し、
前記第２の送信手段は、
前記第１の証明書情報が前記第１の記憶手段に記憶されていないと判定された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、前記第１の記憶手段によって記憶されている前記中継端末へ該要求情報を送信し、
前記第１の証明書情報が前記第１の記憶手段に記憶されていると判定された場合には、前記要求情報に付加された証明書情報と前記第１の証明書情報とを含む検証用情報を前記認証端末へ送信する
ことを特徴とする請求項２に記載の通信システム。
【請求項５】
前記第１の送信手段は、前記公開鍵の検証に必要な第１の証明書情報を要求するための、経由情報を含む要求情報を、前記第２の記憶手段によって記憶されている前記中継端末へ送信し、
前記第２の送信手段は、
前記第１の証明書情報が前記第１の記憶手段に記憶されていないと判定された場合には、前記要求情報に含まれる前記経由情報を更新し、前記第１の記憶手段によって記憶されている前記中継端末へ該要求情報を送信し、
前記第１の証明書情報が前記第１の記憶手段に記憶されていると判定された場合には、前記第１の証明書情報と、経由する端末を示す返信経由情報とを含む検証用情報を前記返信経由情報が示す前記認証端末または前記中継端末へ送信し、
前記検証用情報が受信された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、前記返信経由情報が示す前記認証端末または前記中継端末へ送信する
ことを特徴とする請求項４に記載の通信システム。
【請求項６】
前記第１の受信手段はさらに、前記被認証端末から、前記公開鍵を証明する第２の証明書情報を予め受信し、
前記第１の証明書情報は、前記第２の証明書情報に含まれる署名情報の検証に必要な公開鍵を証明する
ことを特徴とする請求項１〜請求項５のいずれかの項に記載の通信システム。
【請求項７】
前記第１の受信手段はさらに、前記被認証端末から、前記公開鍵と、該被認証端末を信頼する端末に関する被信頼情報とを予め受信し、
前記第１の証明書情報は、前記公開鍵を証明し、
前記要求情報は、前記第１の証明書情報を、前記被信頼情報によって示される端末から取得することを示す
ことを特徴とする請求項１〜請求項５のいずれかの項に記載の通信システム。
【請求項８】
認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムにおいて、
前記認証端末は、
前記公開鍵の検証に必要な情報を要求するための要求情報を他の端末へ送信すると共に、
他の端末から、前記公開鍵の検証に必要な情報を含む検証用情報を受信し、
該検証用情報に基づいて前記公開鍵を検証し、
前記中継端末は、
自身が信頼する端末の識別情報と、他の端末に到達する経路に関する経路情報とを予め記憶し、
自身を信頼しない他の端末から前記要求情報を受信し、該要求情報が経由する端末として自身が指定されている場合には、前記公開鍵の検証に必要な情報を含むと共に、前記経路情報に基づいて、他の中継端末または前記被認証端末への到達を指定する情報を含む新たな要求情報を生成し、
該要求情報を他の端末へ送信し、
前記被認証端末は、
前記要求情報を受信した場合に、該要求情報に含まれる、前記公開鍵の検証に必要な情報と、自身が所持する、前記公開鍵の検証に必要な情報とを含む前記検証用情報を生成して前記認証端末へ送信する
ことを特徴とする通信システム。
【請求項９】
前記中継端末が生成した新たな要求情報は、該要求情報が経由した他の中継端末または前記認証端末によって生成された、自身の公開鍵を証明する証明書情報を含み、
前記被認証端末が生成した前記検証情報は、前記要求情報に付加された前記中継端末の証明書情報と、前記要求情報が経由した前記中継端末によって生成された、自身の公開鍵を証明する証明書情報とを含む
ことを特徴とする請求項８に記載の通信システム。
【請求項１０】
認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムにおいて、
前記認証端末は、
前記公開鍵の検証に必要な情報を要求するための要求情報を他の端末へ送信すると共に、
他の端末から、前記公開鍵の検証に必要な情報を含む検証用情報を受信し、
該検証用情報に基づいて前記公開鍵を検証し、
前記中継端末は、
自身が信頼する端末の識別情報と、他の端末に到達する経路に関する経路情報とを予め記憶し、
自身を信頼しない他の端末から前記要求情報を受信し、該要求情報が経由する端末として自身が指定されており、前記被認証端末の公開鍵を証明する証明書情報を所持していない場合には、前記要求情報が経由した他の中継端末または前記認証端末によって生成された、自身の公開鍵を証明する証明書情報を含むと共に、前記経路情報に基づいて、他の中継端末または前記被認証端末への到達を指定する情報を含む新たな要求情報を生成して他の端末へ送信し、
前記要求情報を受信し、前記被認証端末の公開鍵を証明する証明書情報を所持している場合には、前記要求情報が経由した他の中継端末または前記認証端末によって生成された、自身の公開鍵を証明する証明書情報と、前記要求情報に付加された前記証明書情報と、前記被認証端末の公開鍵を証明する前記証明書情報とを含む前記検証用情報を生成して前記認証端末へ送信する
ことを特徴とする通信システム。
【請求項１１】
認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムで用いられる通信端末において、
前記認証端末として、
前記公開鍵の検証に必要な情報を要求するための要求情報を送信する第1の送信手段と、
前記中継端末から、前記情報を含む検証用情報を受信する第1の受信手段と、
該検証用情報に基づいて前記公開鍵を検証する検証手段と、
を具備し、
前記中継端末として、
前記要求情報によって要求された情報を所持していない場合には、前記要求情報を他の中継端末へ送信し、前記要求情報によって要求された情報を所持している場合には、前記情報を含む検証用情報を前記認証端末または他の中継端末へ送信する第２の送信手段と、
を具備する
ことを特徴とする通信端末。
【請求項１２】
認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムで用いられる通信端末において、
前記認証端末として、
前記公開鍵の検証に必要な第１の証明書情報を要求するための要求情報をブロードキャストする第１の送信手段と、
前記第１の証明書情報を含む検証用情報を前記中継端末から受信する第１の受信手段と、
前記検証用情報に基づいて前記公開鍵を検証する検証手段と、
を具備し、
前記中継端末として、
証明書情報を記憶する第１の記憶手段と、
前記要求情報を受信する第２の受信手段と、
該要求情報に基づいて、前記第１の証明書情報が前記第１の記憶手段に記憶されているかどうか判定する判定手段と、
記憶されていないと判定された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、該要求情報をブロードキャストし、記憶されていると判定された場合には、前記要求情報に付加された証明書情報と前記第１の証明書情報とを含む検証用情報を前記認証端末へ送信する第２の送信手段と、
を具備する
ことを特徴とする通信端末。
【請求項１３】
前記第１の送信手段は、前記公開鍵の検証に必要な第１の証明書情報を要求するための、経由情報を含む要求情報をブロードキャストし、
前記第２の送信手段は、
前記第１の証明書情報が前記第１の記憶手段に記憶されていないと判定された場合には、前記要求情報に含まれる前記経由情報を更新し、前記要求情報をブロードキャストし、
前記第１の証明書情報が前記第１の記憶手段に記憶されていると判定された場合には、前記第１の証明書情報と、経由する端末を示す返信経由情報とを含む検証用情報を前記返信経由情報が示す前記認証端末または前記中継端末へ送信し、
前記検証用情報が受信された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、前記返信経由情報が示す前記認証端末または前記中継端末へ送信する
ことを特徴とする請求項１２に記載の通信端末。
【請求項１４】
前記認証端末としてさらに、信頼する中継端末を記憶する第２の記憶手段を具備し、
前記第１の送信手段は、前記公開鍵の検証に必要な第１の証明書情報を要求するための要求情報を、前記第２の記憶手段によって記憶されている前記中継端末へ送信し、
前記第１の記憶手段は、証明書情報および信頼する他の中継端末を記憶し、
前記第２の送信手段は、
前記第１の証明書情報が前記第１の記憶手段に記憶されていないと判定された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、前記第１の記憶手段によって記憶されている前記中継端末へ該要求情報を送信し、
前記第１の証明書情報が前記第１の記憶手段に記憶されていると判定された場合には、前記要求情報に付加された証明書情報と前記第１の証明書情報とを含む検証用情報を前記認証端末へ送信する
ことを特徴とする請求項１２に記載の通信端末。
【請求項１５】
前記第１の送信手段は、前記公開鍵の検証に必要な第１の証明書情報を要求するための、経由情報を含む要求情報を、前記第２の記憶手段によって記憶されている前記中継端末へ送信し、
前記第２の送信手段は、
前記第１の証明書情報が前記第１の記憶手段に記憶されていないと判定された場合には、前記要求情報に含まれる前記経由情報を更新し、前記第１の記憶手段によって記憶されている前記中継端末へ該要求情報を送信し、
前記第１の証明書情報が前記第１の記憶手段に記憶されていると判定された場合には、前記第１の証明書情報と、経由する端末を示す返信経由情報とを含む検証用情報を前記返信経由情報が示す前記認証端末または前記中継端末へ送信し、
前記検証用情報が受信された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、前記返信経由情報が示す前記認証端末または前記中継端末へ送信する
ことを特徴とする請求項１４に記載の通信端末。
【請求項１６】
前記第１の受信手段はさらに、前記被認証端末から、前記公開鍵を証明する第２の証明書情報を予め受信し、
前記第１の証明書情報は、前記第２の証明書情報に含まれる署名情報の検証に必要な公開鍵を証明する
ことを特徴とする請求項１１〜請求項１５のいずれかの項に記載の通信端末。
【請求項１７】
前記第１の受信手段はさらに、前記被認証端末から、前記公開鍵と、該被認証端末を信頼する端末に関する被信頼情報とを予め受信し、
前記第１の証明書情報は、前記公開鍵を証明し、
前記要求情報は、前記第１の証明書情報を、前記被信頼情報によって示される端末から取得することを示す
ことを特徴とする請求項１１〜請求項１５のいずれかの項に記載の通信端末。
【請求項１８】
認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムで用いられる通信端末において、
前記認証端末として、
前記公開鍵の検証に必要な情報を要求するための要求情報を他の端末へ送信する第１の送信手段と、
他の端末から、前記公開鍵の検証に必要な情報を含む検証用情報を受信する第１の受信手段と、
受信された前記検証用情報に基づいて前記公開鍵を検証する検証手段と、
を具備し、
前記中継端末として、
自身が信頼する端末の識別情報と、他の端末に到達する経路に関する経路情報とを予め記憶する記憶手段と、
前記要求情報を受信する第２の受信手段と、
自身を信頼しない他の端末から前記要求情報を受信し、該要求情報が経由する端末として自身が指定されている場合には、前記公開鍵の検証に必要な情報を含むと共に、前記経路情報に基づいて、他の中継端末または前記被認証端末への到達を指定する情報を含む新たな要求情報を生成する第１の情報生成手段と、
該要求情報を他の端末へ送信する第２の送信手段と、
を具備し、
前記被認証端末として、
前記要求情報を受信する第３の受信手段と、
受信された前記要求情報に含まれる、前記公開鍵の検証に必要な情報と、自身が所持する、前記公開鍵の検証に必要な情報とを含む前記検証用情報を生成する第２の情報生成手段と、
該検証用情報を前記認証端末へ送信する第３の送信手段と、
を具備することを特徴とする通信端末。
【請求項１９】
前記第１の情報生成手段が生成した新たな要求情報は、該要求情報が経由した他の中継端末または前記認証端末によって生成された、自身の公開鍵を証明する証明書情報を含み、
前記第２の情報生成手段が生成した前記検証情報は、前記要求情報に付加された前記中継端末の証明書情報と、前記要求情報が経由した前記中継端末によって生成された、自身の公開鍵を証明する証明書情報とを含む
ことを特徴とする請求項１８に記載の通信端末。
【請求項２０】
認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムで用いられる通信端末において、
前記認証端末として、
前記公開鍵の検証に必要な情報を要求するための要求情報を他の端末へ送信する第１の送信手段と、
他の端末から、前記公開鍵の検証に必要な情報を含む検証用情報を受信する第１の受信手段と、
受信された前記検証用情報に基づいて前記公開鍵を検証する検証手段と、
を具備し、
前記中継端末として、
自身が信頼する端末の識別情報と、他の端末に到達する経路に関する経路情報とを予め記憶する記憶手段と、
前記要求情報を受信する第２の受信手段と、
自身を信頼しない他の端末から前記要求情報を受信し、該要求情報が経由する端末として自身が指定されており、前記被認証端末の公開鍵を証明する証明書情報を所持していない場合には、前記要求情報が経由した他の中継端末または前記認証端末によって生成された、自身の公開鍵を証明する証明書情報を含むと共に、前記経路情報に基づいて、他の中継端末または前記被認証端末への到達を指定する情報を含む新たな要求情報を生成し、前記被認証端末の公開鍵を証明する証明書情報を所持している場合には、前記要求情報が経由した他の中継端末または前記認証端末によって生成された、自身の公開鍵を証明する証明書情報と、前記要求情報に付加された前記証明書情報と、前記被認証端末の公開鍵を証明する前記証明書情報とを含む前記検証用情報を生成する第１の情報生成手段と、
新たな要求情報を他の端末へ送信すると共に、前記検証用情報を前記認証端末へ送信する第３の送信手段と、
を具備することを特徴とする通信端末。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化通信を行う通信システムに関し、特に、暗号化通信における公開鍵の管理方式の改善を図った通信システムおよび通信端末に関する。
【背景技術】
【０００２】
基地局やアクセスポイントなどを必要とせず、無線で接続された携帯電話、ＰＨＳ（登録商標）、およびＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｉｓｔａｎｃｅ）などの無線通信端末同士が相互に無線接続を行い、他の無線通信端末を介して目的の通信相手と接続するマルチホップ接続により無線通信を行うネットワーク形態は無線アドホックネットワークと呼ばれる。無線アドホックネットワークにおいては、あるノードから電波の届く範囲内の全てのノードがそのノードを盗聴することができるため、エンド−エンド間の通信を秘匿するためのＶＰＮ（Ｖｉｒｔｕａｌ  Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋ）が必要になる。
【０００３】
従来、セキュリティの高いＶＰＮを構築するために、暗号化されたデータを通信でやりとりする暗号方式がよく使用されている。その暗号方式の一例としてよく知られるものに、公開鍵暗号方式がある。これは、データの送信側が用いる暗号化用の鍵と受信側が用いる復号化用の鍵とで異なる鍵が用いられる方式である。例えば、データの送信側は受信側から予め公開鍵を受け取り、この公開鍵を用いて暗号化したデータを受信側へ送信する。このデータを受信した受信側は、自身の公開鍵に対応した秘密鍵を用いて復号化を行い、データを取得する。
【０００４】
また、公開鍵暗号方式においては、不特定多数に対して公開される公開鍵の正当性を証明するために、公開鍵に対して公開鍵証明書を付与し、その公開鍵の信頼度および安全性を高めることが一般的に行われている。この公開鍵証明書を発行・管理する機関はＣＡ（Ｃｅｒｔｉｆｉｃａｔｅ  Ａｕｔｈｏｒｉｔｙ）と呼ばれ、従来の無線通信システムにおいては、基地局やアクセスポイント等の固定基盤がその役を担っていた。従来の無線通信システムにおいては、ノードは予めＣＡに対して自身の公開鍵を通知する。そして、ＣＡは、その公開鍵を持つノードが信頼できると判断した場合に、そのノードに対して公開鍵証明書を発行する。
【０００５】
公開鍵証明書は、公開鍵とその公開鍵の所有ノードに関する情報とを組み合わせたデータに対して、ＣＡが自身の秘密鍵（共通鍵）を用いて行った電子書名を含むものである。あるノード（ノードＡとする）が他のノード（ノードＢとする）の公開鍵を認証する場合、ノードＡはノードＢから公開鍵証明書を取得する。そして、ノードＡは、ＣＡから予め取得したＣＡの公開鍵を用いて公開鍵証明書の電子署名を検証し、その電子署名が確かにＣＡによって行われたものだと認証した場合は、公開鍵証明書に付与されたノードＢの公開鍵は正当なものであると判断する。この場合、ノードＡは前述したとおり、この公開鍵を用いてノードＢとの通信を行う。
【０００６】
しかし、基地局やアクセスポイント等の固定基盤を持たない無線アドホックネットワークの場合、絶対的に信頼できるＣＡが存在しないため、公開鍵証明書の発行・管理を行うことができなかった。そこで、各ノードが独自に公開鍵証明書を発行・管理する公開鍵証明書分散管理方式（各通信ノードがＣＡの役割を担うことからこう呼ばれる）が提案された（例えば、非特許文献１）。
【０００７】
この方式は、各ノードが独自の判断（ｋｎｏｗｌｅｄｇｅ：知識や経験）で通信ノードの公開鍵証明書を発行して管理するものである。例えば、ノードＡはノードＢに対して公開鍵証明書を発行しておらず、ノードＢと信頼関係を結んでいないとする。また、ノードＡが直接信頼する（公開鍵証明書を発行している）ノードＣはノードＢを直接信頼しているとする。ノードＡがノードＢと暗号化通信を行う場合、ノードＡはノードＣからノードＢの公開鍵証明書を受け取ることにより、ノードＢを信頼することができる。このようにして、ノードＡとノードＢとの間で結ばれる信頼関係を信頼の輪と呼んでいる。
【０００８】
非特許文献１に記載される方式においては、各ノードは公開鍵証明書に関する情報を自身が信頼するノードと交換することにより、それらのノードと信頼関係を結ぶ。さらに、それらのノードは他のノードと信頼関係を結んでおり、その信頼関係を利用して被認証ノードまでの信頼の輪を構築する手法である。被認証ノードまでの信頼の輪がつながれば、被認証ノードの公開鍵の正当性を証明したことになる。
【０００９】
より具体的には、この方式においては以下のような処理が行われる。まず、各ノードは自身の公開鍵とそれに対応した秘密鍵とを作成する。続いて、各ノードは自身が既に取得している他ノードの公開鍵の知識に基づいて、他ノードの公開鍵に関する公開鍵証明書を作成し、それらの公開鍵を所有する各ノードに対して公開鍵証明書を発行する。各ノードは作成した公開鍵証明書を各ノード同士の間で交換し、各々が所有するリポジトリ（公開鍵証明書を格納するためにハードディスクドライブなどに構築されるデータベース）に、取得した公開鍵証明書を格納する。そして、各ノードはリポジトリ内の情報を交換し合い、ネットワークに参加している全てのノードのリポジトリ内の情報を取得する。目的とするノードと通信を行いたいノードは、このリポジトリ内の情報に基づいて、目的とするノードまでの信頼の輪の構築計算を行う。
【非特許文献１】Ｓｒｄｊａｎ  Ｃａｐｋｕｎ、外２名，「Ｓｅｌｆ−Ｏｒｇａｎｉｚｅｄ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｍａｎａｇｅｍｅｎｔ  ｆｏｒ  Ｍｏｂｉｌｅ  Ａｄ  Ｈｏｃ  Ｎｅｔｗｏｒｋｓ」，ＩＥＥＥ  ＴＲＡＮＳＡＣＴＩＯＮＳ  ＯＮ  ＭＯＢＩＬＥ  ＣＯＭＰＵＴＩＮＧ，２００３，Ｖｏｌ．２，Ｎｏ．１，ｐ．５２−６３
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかし、上述した従来の公開鍵証明書分散管理方式においては、各ノードがネットワークに参加している全てのノードのリポジトリ内の情報を予め受け取り、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）もしくはメモリ上で管理することを前提としている。したがって、ノード数が増えるにつれ、公開鍵証明書情報の交換のための通信量が増大する。また、リポジトリの管理に必要なメモリおよびＨＤＤの容量やＣＰＵ資源には限界があるため、公開鍵を管理することができるノードの数に限界がある。たとえ、全ノードの信頼関係に関する情報を収集し、保存することができたとしても、目的とする被認証ノードまでの信頼の輪のつながりをリポジトリから探索する場合には、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）に大きな負荷が掛かるため、通信中に認証を行うにはリアルタイム性に問題が生じる。
【００１１】
また、たとえ信頼の輪を探索することができたとしても、リポジトリ内の各公開鍵証明書の有効性を確認しなければならない。公開鍵証明書が有効でないと判断されたノードは失効証明書リスト（ＣＲＬ：Ｃｅｒｔｉｆｉｃａｔｉｏｎ  Ｒｅｖｏｃａｔｉｏｎ  Ｌｉｓｔ）に記載される。公開鍵証明書の有効性の判断はこの失効証明書リストに基づいて実施される。従来の公開鍵証明書分散管理方式においては、信頼の輪がつながった時点において、通信を行うノードが、信頼の輪を構成しているノードに対して、失効証明書リストに関する情報を問い合わせる通信が発生し、その通信コストも問題である。
【００１２】
本発明は、上述した問題点に鑑みてなされたものであって、通信資源や各ノードの資源を無駄に使うことがなく、公開鍵の管理コストを低減することができる通信システムおよび通信端末を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は上記の課題を解決するためになされたもので、請求項１に記載の発明は、認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムにおいて、前記認証端末は、前記公開鍵の検証に必要な情報を要求するための要求情報を送信する第1の送信手段と、前記中継端末から、前記情報を含む検証用情報を受信する第1の受信手段と、該検証用情報に基づいて前記公開鍵を検証する検証手段とを具備し、前記中継端末は、前記要求情報によって要求された情報を所持していない場合には、前記要求情報を他の中継端末へ送信し、前記要求情報によって要求された情報を所持している場合には、前記情報を含む検証用情報を前記認証端末または他の中継端末へ送信する第２の送信手段とを具備することを特徴とする通信システムである。
【００１４】
請求項２に記載の発明は、認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムにおいて、前記認証端末は、前記公開鍵の検証に必要な第１の証明書情報を要求するための要求情報をブロードキャストする第１の送信手段と、前記第１の証明書情報を含む検証用情報を前記中継端末から受信する第１の受信手段と、前記検証用情報に基づいて前記公開鍵を検証する検証手段とを具備し、前記中継端末は、証明書情報を記憶する第１の記憶手段と、前記要求情報を受信する第２の受信手段と、該要求情報に基づいて、前記第１の証明書情報が前記第１の記憶手段に記憶されているかどうか判定する判定手段と、記憶されていないと判定された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、該要求情報をブロードキャストし、記憶されていると判定された場合には、前記要求情報に付加された証明書情報と前記第１の証明書情報とを含む検証用情報を前記認証端末へ送信する第２の送信手段とを具備することを特徴とする通信システムである。
【００１５】
請求項３に記載の発明は、請求項２に記載の通信システムにおいて、前記第１の送信手段は、前記公開鍵の検証に必要な第１の証明書情報を要求するための、経由情報を含む要求情報をブロードキャストし、前記第２の送信手段は、前記第１の証明書情報が前記第１の記憶手段に記憶されていないと判定された場合には、前記要求情報に含まれる前記経由情報を更新し、前記要求情報をブロードキャストし、前記第１の証明書情報が前記第１の記憶手段に記憶されていると判定された場合には、前記第１の証明書情報と、経由する端末を示す返信経由情報とを含む検証用情報を前記返信経由情報が示す前記認証端末または前記中継端末へ送信し、前記検証用情報が受信された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、前記返信経由情報が示す前記認証端末または前記中継端末へ送信することを特徴とする。
【００１６】
請求項４に記載の発明は、請求項２に記載の通信システムにおいて、前記認証端末はさらに、信頼する中継端末を記憶する第２の記憶手段を具備し、前記第１の送信手段は、前記公開鍵の検証に必要な第１の証明書情報を要求するための要求情報を、前記第２の記憶手段によって記憶されている前記中継端末へ送信し、前記第１の記憶手段は、証明書情報および信頼する他の中継端末を記憶し、前記第２の送信手段は、前記第１の証明書情報が前記第１の記憶手段に記憶されていないと判定された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、前記第１の記憶手段によって記憶されている前記中継端末へ該要求情報を送信し、前記第１の証明書情報が前記第１の記憶手段に記憶されていると判定された場合には、前記要求情報に付加された証明書情報と前記第１の証明書情報とを含む検証用情報を前記認証端末へ送信することを特徴とする。
各端末間の信頼関係は、例えば、公開鍵証明書の発行により定義される。ある端末（Ａ）が他の端末（Ｂ）を信頼するとは、端末（Ａ）が端末（Ｂ）の公開鍵に対して公開鍵証明書を発行していることを意味している。第１および第２の記憶手段は、自身が公開鍵証明書を発行している発行先の端末を記憶する。
【００１７】
請求項５に記載の発明は、請求項４に記載の通信システムにおいて、前記第１の送信手段は、前記公開鍵の検証に必要な第１の証明書情報を要求するための、経由情報を含む要求情報を、前記第２の記憶手段によって記憶されている前記中継端末へ送信し、前記第２の送信手段は、前記第１の証明書情報が前記第１の記憶手段に記憶されていないと判定された場合には、前記要求情報に含まれる前記経由情報を更新し、前記第１の記憶手段によって記憶されている前記中継端末へ該要求情報を送信し、前記第１の証明書情報が前記第１の記憶手段に記憶されていると判定された場合には、前記第１の証明書情報と、経由する端末を示す返信経由情報とを含む検証用情報を前記返信経由情報が示す前記認証端末または前記中継端末へ送信し、前記検証用情報が受信された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、前記返信経由情報が示す前記認証端末または前記中継端末へ送信することを特徴とする。
【００１８】
請求項６に記載の発明は、請求項１〜請求項５に記載の通信システムにおいて、前記第１の受信手段はさらに、前記被認証端末から、前記公開鍵を証明する第２の証明書情報を予め受信し、前記第１の証明書情報は、前記第２の証明書情報に含まれる署名情報の検証に必要な公開鍵を証明することを特徴とする。
【００１９】
請求項７に記載の発明は、請求項１〜請求項５に記載の通信システムにおいて、前記第１の受信手段はさらに、前記被認証端末から、前記公開鍵と、該被認証端末を信頼する端末に関する被信頼情報とを予め受信し、前記第１の証明書情報は、前記公開鍵を証明し、前記要求情報は、前記第１の証明書情報を、前記被信頼情報によって示される端末から取得することを示すことを特徴とする。
【００２０】
請求項８に記載の発明は、認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムにおいて、前記認証端末は、前記公開鍵の検証に必要な情報を要求するための要求情報を他の端末へ送信すると共に、他の端末から、前記公開鍵の検証に必要な情報を含む検証用情報を受信し、該検証用情報に基づいて前記公開鍵を検証し、前記中継端末は、自身が信頼する端末の識別情報と、他の端末に到達する経路に関する経路情報とを予め記憶し、前記要求情報を受信した場合に、前記公開鍵の検証に必要な情報を含むと共に、前記経路情報に基づいて、経由する端末を指定する情報を含む新たな要求情報を生成し、該要求情報を他の端末へ送信し、前記被認証端末は、前記要求情報を受信した場合に、該要求情報に含まれる、前記公開鍵の検証に必要な情報と、自身が所持する、前記公開鍵の検証に必要な情報とを含む前記検証用情報を生成して前記認証端末へ送信することを特徴とする通信システムである。
【００２１】
請求項９に記載の発明は、請求項８に記載の通信システムにおいて、前記中継端末が生成した新たな要求情報は、該要求情報が経由した他の中継端末または前記認証端末によって生成された、自身の公開鍵を証明する証明書情報を含み、前記被認証端末が生成した前記検証情報は、前記要求情報に付加された前記中継端末の証明書情報と、前記要求情報が経由した前記中継端末によって生成された、自身の公開鍵を証明する証明書情報とを含むことを特徴とする。
【００２２】
請求項１０に記載の発明は、認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムにおいて、前記認証端末は、前記公開鍵の検証に必要な情報を要求するための要求情報を他の端末へ送信すると共に、他の端末から、前記公開鍵の検証に必要な情報を含む検証用情報を受信し、該検証用情報に基づいて前記公開鍵を検証し、前記中継端末は、自身が信頼する端末の識別情報と、他の端末に到達する経路に関する経路情報とを予め記憶し、前記要求情報を受信し、前記被認証端末の公開鍵を証明する証明書情報を所持していない場合には、前記要求情報が経由した他の中継端末または前記認証端末によって生成された、自身の公開鍵を証明する証明書情報を含むと共に、前記経路情報に基づいて、経由する端末を指定する情報を含む新たな要求情報を生成して他の端末へ送信し、前記要求情報を受信し、前記被認証端末の公開鍵を証明する証明書情報を所持している場合には、前記要求情報が経由した他の中継端末または前記認証端末によって生成された、自身の公開鍵を証明する証明書情報と、前記要求情報に付加された前記証明書情報と、前記被認証端末の公開鍵を証明する前記証明書情報とを含む前記検証用情報を生成して前記認証端末へ送信することを特徴とする通信システムである。
【００２３】
請求項１１に記載の発明は、請求項８〜請求項１０のいずれかの項に記載の通信システムにおいて、前記中継端末は、自身を信頼しない他の端末から前記要求情報を受信し、該要求情報が経由する端末として自身が指定されている場合には、他の中継端末または前記被認証端末への到達を指定する情報を含む新たな要求情報を生成することを特徴とする。
【００２４】
請求項１２に記載の発明は、認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムで用いられる通信端末において、前記認証端末として、前記公開鍵の検証に必要な情報を要求するための要求情報を送信する第1の送信手段と、前記中継端末から、前記情報を含む検証用情報を受信する第1の受信手段と、該検証用情報に基づいて前記公開鍵を検証する検証手段とを具備し、前記中継端末として、前記要求情報によって要求された情報を所持していない場合には、前記要求情報を他の中継端末へ送信し、前記要求情報によって要求された情報を所持している場合には、前記情報を含む検証用情報を前記認証端末または他の中継端末へ送信する第２の送信手段とを具備することを特徴とする通信端末である。
【００２５】
請求項１３に記載の発明は、認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムで用いられる通信端末において、前記認証端末として、前記公開鍵の検証に必要な第１の証明書情報を要求するための要求情報をブロードキャストする第１の送信手段と、前記第１の証明書情報を含む検証用情報を前記中継端末から受信する第１の受信手段と、前記検証用情報に基づいて前記公開鍵を検証する検証手段とを具備し、前記中継端末として、証明書情報を記憶する第１の記憶手段と、前記要求情報を受信する第２の受信手段と、該要求情報に基づいて、前記第１の証明書情報が前記第１の記憶手段に記憶されているかどうか判定する判定手段と、記憶されていないと判定された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、該要求情報をブロードキャストし、記憶されていると判定された場合には、前記要求情報に付加された証明書情報と前記第１の証明書情報とを含む検証用情報を前記認証端末へ送信する第２の送信手段とを具備することを特徴とする通信端末である。
【００２６】
請求項１４に記載の発明は、請求項１３に記載の通信端末において、前記第１の送信手段は、前記公開鍵の検証に必要な第１の証明書情報を要求するための、経由情報を含む要求情報をブロードキャストし、前記第２の送信手段は、前記第１の証明書情報が前記第１の記憶手段に記憶されていないと判定された場合には、前記要求情報に含まれる前記経由情報を更新し、前記要求情報をブロードキャストし、前記第１の証明書情報が前記第１の記憶手段に記憶されていると判定された場合には、前記第１の証明書情報と、経由する端末を示す返信経由情報とを含む検証用情報を前記返信経由情報が示す前記認証端末または前記中継端末へ送信し、前記検証用情報が受信された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、前記返信経由情報が示す前記認証端末または前記中継端末へ送信することを特徴とする。
【００２７】
請求項１５に記載の発明は、請求項１３に記載の通信端末において、前記認証端末としてさらに、信頼する中継端末を記憶する第２の記憶手段を具備し、前記第１の送信手段は、前記公開鍵の検証に必要な第１の証明書情報を要求するための要求情報を、前記第２の記憶手段によって記憶されている前記中継端末へ送信し、前記第１の記憶手段は、証明書情報および信頼する他の中継端末を記憶し、前記第２の送信手段は、前記第１の証明書情報が前記第１の記憶手段に記憶されていないと判定された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、前記第１の記憶手段によって記憶されている前記中継端末へ該要求情報を送信し、前記第１の証明書情報が前記第１の記憶手段に記憶されていると判定された場合には、前記要求情報に付加された証明書情報と前記第１の証明書情報とを含む検証用情報を前記認証端末へ送信することを特徴とする。
【００２８】
請求項１６に記載の発明は、請求項１５に記載の通信端末において、前記第１の送信手段は、前記公開鍵の検証に必要な第１の証明書情報を要求するための、経由情報を含む要求情報を、前記第２の記憶手段によって記憶されている前記中継端末へ送信し、前記第２の送信手段は、前記第１の証明書情報が前記第１の記憶手段に記憶されていないと判定された場合には、前記要求情報に含まれる前記経由情報を更新し、前記第１の記憶手段によって記憶されている前記中継端末へ該要求情報を送信し、前記第１の証明書情報が前記第１の記憶手段に記憶されていると判定された場合には、前記第１の証明書情報と、経由する端末を示す返信経由情報とを含む検証用情報を前記返信経由情報が示す前記認証端末または前記中継端末へ送信し、前記検証用情報が受信された場合には、前記第１の記憶手段によって記憶されている証明書情報を前記要求情報に付加し、前記返信経由情報が示す前記認証端末または前記中継端末へ送信することを特徴とする。
【００２９】
請求項１７に記載の発明は、請求項１２〜請求項１６に記載の通信端末において、前記第１の受信手段はさらに、前記被認証端末から、前記公開鍵を証明する第２の証明書情報を予め受信し、前記第１の証明書情報は、前記第２の証明書情報に含まれる署名情報の検証に必要な公開鍵を証明することを特徴とする。
【００３０】
請求項１８に記載の発明は、請求項１２〜請求項１６に記載の通信端末において、前記第１の受信手段はさらに、前記被認証端末から、前記公開鍵と、該被認証端末を信頼する端末に関する被信頼情報とを予め受信し、前記第１の証明書情報は、前記公開鍵を証明し、前記要求情報は、前記第１の証明書情報を、前記被信頼情報によって示される端末から取得することを示すことを特徴とする。
【００３１】
請求項１９に記載の発明は、認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムで用いられる通信端末において、前記認証端末として、前記公開鍵の検証に必要な情報を要求するための要求情報を他の端末へ送信する第１の送信手段と、他の端末から、前記公開鍵の検証に必要な情報を含む検証用情報を受信する第１の受信手段と、受信された前記検証用情報に基づいて前記公開鍵を検証する検証手段とを具備し、前記中継端末として、自身が信頼する端末の識別情報と、他の端末に到達する経路に関する経路情報とを予め記憶する記憶手段と、前記要求情報を受信する第２の受信手段と、前記要求情報が受信された場合に、前記公開鍵の検証に必要な情報を含むと共に、前記経路情報に基づいて、経由する端末を指定する情報を含む新たな要求情報を生成する第１の情報生成手段と、該要求情報を他の端末へ送信する第２の送信手段とを具備し、前記被認証端末として、前記要求情報を受信する第３の受信手段と、受信された前記要求情報に含まれる、前記公開鍵の検証に必要な情報と、自身が所持する、前記公開鍵の検証に必要な情報とを含む前記検証用情報を生成する第２の情報生成手段と、該検証用情報を前記認証端末へ送信する第３の送信手段とを具備することを特徴とする通信端末である。
【００３２】
請求項２０に記載の発明は、請求項１９に記載の通信端末において、前記第１の情報生成手段が生成した新たな要求情報は、該要求情報が経由した他の中継端末または前記認証端末によって生成された、自身の公開鍵を証明する証明書情報を含み、前記第２の情報生成手段が生成した前記検証情報は、前記要求情報に付加された前記中継端末の証明書情報と、前記要求情報が経由した前記中継端末によって生成された、自身の公開鍵を証明する証明書情報とを含むことを特徴とする。
【００３３】
請求項２１に記載の発明は、認証端末が１以上の中継端末を介して被認証端末の公開鍵を検証し、検証した公開鍵を用いて前記被認証端末と暗号化通信を行う通信システムで用いられる通信端末において、前記認証端末として、前記公開鍵の検証に必要な情報を要求するための要求情報を他の端末へ送信する第１の送信手段と、他の端末から、前記公開鍵の検証に必要な情報を含む検証用情報を受信する第１の受信手段と、受信された前記検証用情報に基づいて前記公開鍵を検証する検証手段とを具備し、前記中継端末として、自身が信頼する端末の識別情報と、他の端末に到達する経路に関する経路情報とを予め記憶する記憶手段と、前記要求情報を受信する第２の受信手段と、前記被認証端末の公開鍵を証明する証明書情報を所持していない場合には、前記要求情報が経由した他の中継端末または前記認証端末によって生成された、自身の公開鍵を証明する証明書情報を含むと共に、前記経路情報に基づいて、経由する端末を指定する情報を含む新たな要求情報を生成し、前記被認証端末の公開鍵を証明する証明書情報を所持している場合には、前記要求情報が経由した他の中継端末または前記認証端末によって生成された、自身の公開鍵を証明する証明書情報と、前記要求情報に付加された前記証明書情報と、前記被認証端末の公開鍵を証明する前記証明書情報とを含む前記検証用情報を生成する第１の情報生成手段と、新たな要求情報を他の端末へ送信すると共に、前記検証用情報を前記認証端末へ送信する第３の送信手段とを具備することを特徴とする通信端末である。
【００３４】
請求項２２に記載の発明は、請求項１９〜請求項２１のいずれかの項に記載の通信システムにおいて、前記第２の受信手段は、自身を信頼しない他の端末から前記要求情報を受信し、前記第１の情報生成手段は、前記要求情報が経由する端末として自身が指定されている場合には、他の中継端末または前記被認証端末への到達を指定する情報を含む新たな要求情報を生成することを特徴とする。
【発明の効果】
【００３５】
本発明によれば、被認証端末の公開鍵の認証を行う必要性が発生したときに、認証端末が、信頼の輪を構築する各端末から必要な端末のみの公開鍵証明書を取得するようにしたので、通信資源や各ノードの資源を無駄に使うことがなく、公開鍵の管理コストを低減することができるという効果が得られる。
【発明を実施するための最良の形態】
【００３６】
以下、図面を参照し、本発明を実施するための最良の形態について説明する。本実施形態においては、認証局（ＣＡ）を持たない通信システムとして、無線アドホックネットワークを例として説明する。図１は、本発明の一実施形態による通信システムの構成を示す概略構成図である。図には、ノード１Ａ〜１Ｎが示されている。本実施形態におけるノードとは、携帯電話、ＰＨＳ（登録商標）、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｃｅ）などの無線通信機能を有する端末または無線ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）を構成するパーソナルコンピュータなどの通信端末である。なお、この構成図は各ノードの位置関係を示すものではなく、論理的な接続関係を示すものである。また、この通信システムにはノード１Ａ〜１Ｎに限られず、図示せぬノードも含まれるものとする。
【００３７】
図２は各ノードの構成を示すブロック図である。図において、１０はデータ送受信用のアンテナである。１１は通信部であり、データの送受信に係る変調・復調処理等を行う。１２はユーザによって操作される操作部である。１３は表示部であり、ユーザに対して様々な情報を表示する。１４は一時記憶部であり、他ノードとの通信において取得した情報（公開鍵証明書等）を一時的に保持する。他ノードとの通信が終了したら、一時記憶部１４内の情報は消去される。
【００３８】
１５は長期間保持される情報が格納される記憶部である。記憶部１５には、自ノードが信頼するノードに対して発行した公開鍵証明書と、自ノードを信頼しているノードから発行された公開鍵証明書とが証明書リポジトリとして格納されている。また、自ノードが直接信頼しているノードの情報が信頼ノードリストとして格納され、自ノードがどのノードに直接信頼されているのかを示す情報が被信頼ノードリストとして格納されている。１６は制御部であり、上記各部を制御すると共に、データの暗号化および復号化を行う。
【００３９】
次に、本実施形態における各ノードの動作を説明する。まず、各ノード間の信頼関係について説明する。図１で示される通信システムにおいては、ノード１Ａがノード１Ｂおよびノード１Ｃを信頼している。また、ノード１Ａに信頼されているノード１Ｂおよびノード１Ｃも、図示されるように、それぞれ他のノードを信頼している。ここで、ノード１Ａがノード１Ｂを信頼しているとは、ノード１Ａがノード１Ｂの公開鍵に対する公開鍵証明書を発行していることを意味している。図１において、各矢印は各ノードの信頼関係を示している。
【００４０】
ノード１Ａは予めノード１Ｂからノード１Ｂの公開鍵を通知されており、ノード１Ｂを信頼できると判断した場合に、ノード１Ｂの公開鍵に対する公開鍵証明書を作成し、ノード１Ａの記憶部１５中の証明書リポジトリ内にその公開鍵証明書を追加すると共に、信頼ノードリストにノード１Ｂの情報を追加する。この公開鍵証明書には、ノード１Ｂの公開鍵およびノード１Ｂの識別子等の公開鍵情報と署名情報（ノード１Ａによる電子署名および署名者であるノード１Ａの識別子）とが含まれている。ノード１Ａの電子署名とは、上記の公開鍵情報がノード１Ａの秘密鍵によって暗号化されたものであり、ノード１Ａの公開鍵によってのみ復号化することができる。
【００４１】
以下、本実施形態に係る説明においては、ノード１Ｂの公開鍵ＫＢとノード１Ａの署名情報ＳＡを含む公開鍵証明書を（ＫＢ／ＳＡ）として表現することにする。なお、Ｋは公開鍵（ｐｕｂｌｉｃ  ｋｅｙ）を表し、Ｓは署名（ｓｉｇｎａｔｕｒｅ）を表す。
【００４２】
ノード１Ａは、ノード１Ｂに対する公開鍵証明書を作成した際に、ノード１Ｂに対して、公開鍵証明書（ＫＢ／ＳＡ）を送信する。この公開鍵証明書を取得したノード１Ｂは、公開鍵証明書を記憶部１５中の証明書リポジトリに追加すると共に、記憶部１５中の被信頼ノードリストにノード１Ａの情報を追加する。これにより、ノード１Ｂはノード１Ａから信頼されていることを認識することができる。
【００４３】
次に、本実施形態における通信経路の確立方法を説明する。本実施形態においては、図１におけるノード１Ａがノード１Ｎと暗号化通信を行うものとする。本実施形態においては、ＤＳＲ（Ｄｙｎａｍｉｃ  Ｓｏｕｒｃｅ  Ｒｏｕｔｉｎｇ）プロトコルや、ＡＯＤＶ（Ａｄ  Ｈｏｃ  Ｏｎ−Ｄｅｍａｎｄ  Ｄｉｓｔａｎｃｅ  Ｖｅｃｔｏｒ  Ｒｏｕｔｉｎｇ）プロトコル等の従来のプロトコルに従って各ノード間の通信経路が確立されるものとする。以下、ＤＳＲプロトコルとＡＯＤＶプロトコルによる経路探索方式を説明する。
【００４４】
ＤＳＲプロトコルにおいては、経路探索を行う認証ノードは、ＲＲＥＱ（Ｒｏｕｔｅ  Ｒｅｑｕｅｓｔ）と呼ばれるパケットを周囲のノードへ送信する。これを受信した周囲のノードは、そのパケットの宛先が自分でなければ、自身の情報をパケット中の経路情報に追加して、ＲＲＥＱパケットをさらに周囲のノードへ送信する。宛先ノードがこのパケットを受信した場合、ＲＲＥＱパケット中の経路情報に従って、ＲＲＥＰ（Ｒｏｕｔｅ  Ｒｅｐｌｙ）パケットを認証ノードへ送信する。中継ノードを介してこのＲＲＥＰパケットを受信した認証ノードは、ＲＲＥＰパケットに含まれる経路情報で示される中継ノードを介して、宛先ノードと通信を行う。
【００４５】
一方、ＡＯＤＶプロトコルにおいては、経路探索を行う認証ノードは、経路情報を含まないＲＲＥＱパケットを周囲のノードへ送信する。周囲のノードは、ＲＲＥＱパケットに含まれる送信ノード（自分の一つ前にＲＲＥＱパケットを送信したノード）の識別子を通信相手として記憶する。この通信相手は、認証ノード側に位置するノードである。続いて、周囲のノードは、ＲＲＥＱパケットの送信ノード識別子を自身の識別子に書き換え、ＲＲＥＱパケットをさらに周囲の他のノードへ送信する。
【００４６】
宛先ノードがこのパケットを受信した場合、宛先ノードは通信相手を記憶すると共に、その通信相手に向けてＲＲＥＰパケットを送信する。ＲＲＥＰパケットを受信したノードは、ＲＲＥＰパケットに含まれる送信ノード（自分の一つ前にＲＲＥＰパケットを送信したノード）を通信相手として記憶する。この通信相手は、宛先ノード側に位置するノードである。続いて、ＲＲＥＰパケットを受信したノードは、送信ノード識別子を自身の識別子に書き換えたＲＲＥＰパケットを、ＲＲＥＱパケットにより記憶した被認証ノードへ送信する。ＲＲＥＰパケットを受信した認証ノードは、同様に通信相手を記憶し、中継ノードを介して宛先ノードと通信を行う。
【００４７】
なお、上述したＤＳＲプロトコルおよびＡＯＤＶプロトコルは、無線アドホックネットワークにおける通信方式の一例であり、本実施形態における通信経路の確立方法はこれらの方法に限定されない。
【００４８】
次に、通信時の各ノードの動作を説明する。まず、本実施形態における第1の動作例を説明する。暗号化通信を行う前に、ノード１Ａ（認証端末）はノード１Ｎ（被認証端末）との通信経路を予め確立し、ノード１Ｎの公開鍵証明書（ＫＮ／ＳＭ）をノード１Ｎから取得する。ノード１Ｎの公開鍵証明書には、ノード１Ｎの公開鍵ＫＮと、その公開鍵に対する署名情報ＳＭが含まれている。ノード１Ａはこの公開鍵証明書に含まれる公開鍵ＫＮの認証を行うため、自身の記憶部１５中の証明書リポジトリを参照し、ノード１Ｎの公開鍵証明書（ＫＮ／ＳＡ）があるかどうか判断する。
【００４９】
ノード１Ａはノード１Ｎを直接信頼していないため、ノード１Ｎの公開鍵証明書を所持していない。その場合、ノード１Ａはノード１Ｎから取得した公開鍵証明書に含まれる署名情報ＳＭを参照する。この署名情報は、ノード１Ｎを信頼しているノード１Ｍによって生成されたもので、署名情報に含まれる電子署名はノード１Ｍの公開鍵によってのみ復号化される。ノード１Ａはノード１Ｍを直接信頼していないため、ノード１Ｍの公開鍵証明書はノード１Ａの証明書リポジトリにはない。したがって、ノード１Ａはノード１Ｍを信頼しているノードからノード１Ｍの公開鍵証明書を取得することになる。
【００５０】
続いて、ノード１Ａは、ノード１Ｍの公開鍵証明書を要求する証明書要求情報（要求情報）をブロードキャストする。この証明書要求情報には、ノード１Ａがノード１Ｍの公開鍵証明書を要求していることを示す情報と、証明書要求情報を中継したノード（最初はノード１Ａ）を示す中継ノード情報とが含まれている。この証明書要求情報は各ノードによって転送される。図３には第1の動作例による通信の様子が示されている。図３（ａ）には、ノード１Ａによって送信された証明書要求情報が転送されていく様子が示されている。なお、この図は証明書要求情報の転送の一部を示したものであり、図示せぬノード（例えばノード１Ｂ、ノード１Ｄ等）も同様の処理を行っている。
【００５１】
図１において図示されぬノード（例えば、ノード１Ａ−ノード１Ｃ間に存在するノード）がこの証明書要求情報を受信した場合、そのノードは中継ノード情報を参照することにより、ノード１Ａが送信者であることを知り、自身の記憶部１５の被信頼ノードリスト中にノード１Ａが含まれているかどうか判断する。図示せぬノードは、ノード１Ａから信頼されていないので、信頼の輪の構築に参加すべきではないと判断し、証明書要求情報をそのままブロードキャストする。なお、証明書要求情報が経路探索としての役目も果たすように、前述したＲＲＥＱを含んでいてもよい。
【００５２】
ノード１Ｃ（中継端末：ノード１Ｂも同様）が証明書要求情報を受信した場合、ノード１Ｃは中継ノード情報を参照することにより、ノード１Ａが送信者であることを知り、自身の記憶部１５の被信頼ノードリスト中にノード１Ａが含まれているかどうか判断する。ノード１Ｃの被信頼ノードリストにはノード１Ａが含まれているので、ノード１Ｃは信頼の輪の構築に参加すべきであると判断する。ノード１Ｃは証明書要求情報に対して、中継ノード情報を自身の情報に書き換えると共に、ノード１Ａから発行された自身の公開鍵証明書（ＫＣ／ＳＡ）を付加し、証明書要求情報をブロードキャストする。
【００５３】
ノード１Ｆはこの証明書要求情報を受信し、証明書要求情報中の中継ノード情報と記憶部１５中の被信頼ノードリストとを参照することにより、自身がノード１Ｃから信頼されていると認識し、信頼の輪の構築に参加すべきであると判断する。ノード１Ｆは、証明書要求情報に対して、中継ノード情報を自身の情報に書き換えると共に、ノード１Ｃから発行された自身の公開鍵証明書（ＫＦ／ＳＣ）を付加し、証明書要求情報をブロードキャストする。
【００５４】
以上のように各ノードが証明書要求情報をブロードキャストすることにより、この証明書要求情報はノード１Ｍの公開鍵証明書を所持するノード１Ｊに転送される。ノード１Ｊは他のノードと同様に、証明書要求情報中の送信者情報と記憶部１５中の被信頼ノードリストを参照することにより、自身がノード１Ｆから信頼されていると認識し、信頼の輪の構築に参加すべきであると判断する。また、証明書要求情報により、ノード１Ａがノード１Ｍの公開鍵証明書を要求していることが示されており、ノード１Ｍの公開鍵証明書は記憶部１５中の証明書リポジトリに存在するので、ノード１Ｊはノード１Ｍの公開鍵証明書をノード１Ａに対して送信すべきであると判断する。
【００５５】
図３（ｂ）はノード１Ｊがノード１Ａに対してノード１Ｍの公開鍵証明書（ＫＭ／ＳＪ）を含む返信情報（検証用情報）を送信する場合の送信の様子を示している。ノード１Ｊは、宛先がノード１Ａであることは指定するが、経由するノードは指定しない。なお、ノード１Ｊ−ノード１Ａ間の通信において、証明書要求情報の転送の際に経由したノード１Ｃ等が経路に含まれていてもよいが、あくまで、ノード１Ｊはノード１Ｃ等の経由を指定する訳ではない。
【００５６】
返信情報には、最終宛先がノード１Ａであることを示す最終宛先情報と、ノード１Ｊが受信した証明書要求情報に付加された公開鍵証明書（ＫＦ／ＳＣ）・（ＫＣ／ＳＡ）およびノード１Ｊが所持する公開鍵証明書（ＫＭ／ＳＪ）・（ＫＪ／ＳＦ）とが含まれる。ノード１Ｊは直接または複数のノードを介してノード１Ａと通信を行い、ノード１Ａに上記の返信情報を送信する。
【００５７】
ノード１Ａは返信情報を受信し、返信情報中に目的のノード１Ｍの公開鍵証明書が含まれていることを確認する。続いて、ノード１Ａは公開鍵証明書（ＫＣ／ＳＡ）に含まれるノード１Ｃの公開鍵を用いて、公開鍵証明書（ＫＦ／ＳＣ）に含まれるノード１Ｆの公開鍵を検証する。具体的には、ノード１Ａは公開鍵ＫＣにより、署名情報ＳＣ中のノード１Ｃによる電子署名を復号化する。そして、公開鍵証明書に平文として含まれていた公開鍵ＫＦと、電子署名の復号化により得られた公開鍵ＫＦとを比較し、両者が同一であるかどうか判断する。
【００５８】
両者が同一であった場合、ノード１Ａは公開鍵ＫＦを認証したことになる。同様に、ノード１Ａは公開鍵ＫＦにより、公開鍵証明書（ＫＪ／ＳＦ）中の公開鍵ＫＪの検証を行い、公開鍵ＫＪの検証に成功したら、公開鍵ＫＪにより公開鍵証明書（ＫＭ／ＳＪ）中の公開鍵ＫＭの検証を行う。この検証に成功した場合、ノード１Ａは公開鍵ＫＭにより、公開鍵証明書（ＫＮ／ＳＭ）中の公開鍵ＫＮの検証を行う。この検証に成功した場合、ノード１Ａはノード１Ｎと暗号化通信を開始する。
【００５９】
ノード１Ａとノード１Ｎとの暗号化通信は以下のようにして行われる。ノード１Ａは、ノード１Ｎの公開鍵ＫＮの認証に成功したことにより、ノード１Ｎを信頼する。ノード１Ａは、自身のみが知っている秘密鍵（共通鍵）を、ノード１Ｎの公開鍵により暗号化し、ノード１Ｎへ送信する。ノード１Ｎは、自身の公開鍵から生成した秘密鍵を用いて、ノード１Ａから受信した情報を復号化し、ノード１Ａの共通鍵を取得する。これにより、ノード１Ａおよびノード１Ｎは同一の共通鍵を所有することになる。
【００６０】
以後、ノード１Ａおよびノード１Ｎ間の通信は、共通鍵による共通鍵暗号（秘密鍵暗号）方式の通信となる。例えば、ノード１Ａがノード１Ｎへデータを送信する場合、ノード１Ａは、共通鍵を用いてデータを暗号化し、ノード１Ｎへ送信する。ノード１Ｎは、受信したデータを、ノード１Ａから取得した共通鍵を用いて復号化する。共通鍵により暗号化されたデータは、同一の共通鍵によってしか復号化することができないので、ノード１Ｎのみがデータを復号化することができる。ノード１Ｎがノード１Ａへデータを送信する場合も、共通鍵による暗号化・復号化により、安全な通信を行うことができる。
【００６１】
なお、以上の動作において、ノード１Ａは自身が直接信頼するノード１Ｃの公開鍵証明書（ＫＣ／ＳＡ）を予め所持しているので、ノード１Ｃは証明書要求情報を転送する際に、公開鍵証明書（ＫＣ／ＳＡ）を付加しなくてもよい。
【００６２】
次に、第１の動作例における認証ノード（ノードＸ：図１のノード１Ａに相当）の動作を図４および図５のフローチャートにより説明する。まず、ノードＸは被認証ノード（ノードＹ：図１のノード１Ｎに相当）との通信経路を確立する。この通信経路には、図示せぬ複数のノードが含まれている場合もある。通信経路の確立後、ノードＸはノードＹからノードＹの公開鍵証明書を受信する。この場合、通信部１１は、アンテナ１０を介して公開鍵証明書を含む情報を受信し、この情報を制御部１６へ出力する（ステップＳ４０１）。
【００６３】
この公開鍵証明書には、ノードＹの公開鍵およびノードＹの識別子等の公開鍵情報と署名情報（ノードＺによる電子署名および署名者であるノードＺの識別子）とが含まれている。ノードＺは図１のノード１Ｍに相当する。この電子署名とは、上記の公開鍵情報がノードＺの秘密鍵によって暗号化されたものである。制御部１６は、署名者の識別子により、電子署名がノードＺによって行われたことを認識することができる。
【００６４】
続いて、制御部１６は記憶部１５中の証明書リポジトリを参照し、ノードＹの公開鍵証明書（ＫＹ／ＳＸ）が格納されているかどうか判定する（ステップＳ４０２）。ステップＳ４０２においてＹＥＳと判定された場合、制御部１６はこの公開鍵証明書（ＫＹ／ＳＸ）中の公開鍵ＫＹと、ノードＹから受信した公開鍵証明書（ＫＹ／ＳＺ）中の公開鍵ＫＹとが同一かどうか判定する（ステップＳ４０３）。ステップＳ４０３においてＹＥＳと判定された場合、ノードＸはノードＹの公開鍵の認証に成功し、ノードＹと暗号化通信を開始する。
【００６５】
一方、ステップＳ４０２またはステップＳ４０３においてＮＯと判定された場合、制御部１６は、ノードＺの公開鍵証明書（ＫＺ／ＳＸ）が記憶部１５中の証明書リポジトリに格納されているかどうか判定する（ステップＳ４０４）。ステップＳ４０４においてＹＥＳと判定された場合、制御部１６は公開鍵ＫＺを用いて、公開鍵証明書（ＫＹ／ＳＺ）の署名情報を検証し、公開鍵ＫＹが正当かどうか判定する（ステップＳ４０５）。ステップＳ４０５においてＹＥＳと判定された場合、ノードＸはノードＹの公開鍵の認証に成功し、ノードＹと暗号化通信を開始する。
【００６６】
ステップＳ４０４またはステップＳ４０５においてＮＯと判定された場合、ノードＸは、ノードＹの公開鍵証明書の署名者であるノードＺの公開鍵証明書を他のノードから取得するための動作を行う。この場合の動作は図５のようになる。制御部１６はノードＹから取得した公開鍵証明書を一時記憶部１４へ格納する。そして、制御部１６は、ノード１Ｊの公開鍵証明書を要求するための証明書要求情報を作成し、通信部１１へ出力する。
【００６７】
証明書要求情報には、ノードＸがノードＺの公開鍵証明書を要求していることを示す情報、中継ノード情報（最初はノードＸとする）、中継ノードが所有する公開鍵証明書、ホップ数（証明書要求情報を中継したノードの数）、および証明書要求情報の作成時刻が含まれる。なお、ノードＸにおいては、ホップ数はゼロとし、証明書要求情報中には公開鍵証明書は格納されていない。通信部１１はアンテナ１０を介して、この証明書要求情報をブロードキャストする（ステップＳ５０１）。
【００６８】
続いて、制御部１６は、要求したノードＺの公開鍵証明書を含む返信情報を受信したかどうか判定する（ステップＳ５０２）。なお、受信の判定に関しては、制限時間を設け、制御部１６が制限時間内に返信情報を受信したかどうか判定するようにしてもよい。ステップＳ５０２においてＹＥＳと判定された場合、制御部１６は受信した１以上の公開鍵証明書に基づいて、前述したように、ノードＹの公開鍵ＫＹが正当であるかどうか判定する（ステップＳ５０３）。ステップＳ５０３においてＹＥＳと判定された場合、ノードＸはノードＹの公開鍵の認証に成功し、ノードＹとの暗号化通信を開始する。一方、ステップＳ５０２またはステップＳ５０３においてＮＯと判定された場合、ノードＸはノードＹの公開鍵の認証に失敗する。
【００６９】
図６は中継ノード（図１における図示せぬノードまたはノード１Ｂ、ノード１Ｃ等）の動作を示すフローチャートである。アンテナ１０を介して他のノードから証明書要求情報を受信した通信部１１は、証明書要求情報を制御部１６へ出力する（ステップＳ６０１）。制御部１６は証明書要求情報中の中継ノード情報を参照すると共に、記憶部１５から被信頼ノードリストを読み出して参照する。制御部１６は、中継ノード情報が示すノードが被信頼ノードリスト中にあるかどうか判定することにより、信頼の輪の構築に参加すべきであるかどうか判定する（ステップＳ６０２）。中継ノード情報が示すノードが被信頼ノードリスト中にある場合は信頼の輪の構築に参加すべきであると判定され、ない場合は信頼の輪の構築に参加すべきでないと判定される。
【００７０】
ステップＳ６０２においてＮＯと判定された場合、制御部１６は通信部１１へ証明書要求情報を出力し、通信部１１はアンテナ１０を介して証明書要求情報をブロードキャストする（ステップＳ６０３）。一方、ステップＳ６０２においてＹＥＳと判定された場合、制御部１６は証明書要求情報中の情報を参照し、ノードＺの公開鍵証明書が要求されていると判断する。これに基づいて、制御部１６は記憶部１５中の証明書リポジトリを参照し、ノードＺの公開鍵証明書が格納されているかどうか判定する（ステップＳ６０４）。
【００７１】
ステップＳ６０４においてＹＥＳと判定された場合、制御部１６はノードＺの公開鍵証明書を含む返信情報を作成する（ステップＳ６０５）。返信情報には、最終宛先がノードＸであることを示す最終宛先情報と、証明書要求情報に付加された公開鍵証明書（図１の例では、公開鍵証明書（ＫＣ／ＳＡ）・（ＫＦ／ＳＣ））と、自身が所持する公開鍵証明書とが含まれている。自身が所持する公開鍵証明書とは、ノードＺの公開鍵証明書（図１の例では、公開鍵証明書（ＫＭ／ＳＪ））と、証明書要求情報の中継ノード情報が示すノードが自身に対して発行した公開鍵証明書（図１の例では、公開鍵証明書（ＫＪ／ＳＦ））とを意味する。
【００７２】
制御部１６は返信情報を通信部１１へ出力し、通信部１１はアンテナ１０を介して返信情報をノードＸへ送信する（ステップＳ６０６）。また、ステップＳ６０４においてＮＯと判定された場合、制御部１６は証明書要求情報の作成時刻を参照し、作成時刻と現在時刻との差から経過時間を求め、その時間が制限時間以内であるかどうか判定する（ステップＳ６０７）。ステップＳ６０７においてＹＥＳと判定された場合、制御部１６は証明書要求情報のホップ数を参照し、その値が制限ホップ数以内であるかどうか判定する（ステップＳ６０８）。
【００７３】
ステップＳ６０８においてＹＥＳと判定された場合、制御部１６は証明書要求情報の中継ノード情報が示すノードによって発行された公開鍵証明書を証明書要求情報に付加し、中継ノード情報を自身の情報に書き換えると共に、ホップ数を１だけ増加させ、証明書要求情報を通信部１１へ出力する。通信部１１はアンテナ１０を介して証明書要求情報をブロードキャストする（ステップＳ６０９）。ステップＳ６０７またはステップＳ６０８においてＮＯと判定された場合、証明書要求情報はブロードキャストされずに処理が終了する。なお、信頼の輪の構築に参加しないノードは、受信した証明書要求情報をブロードキャストせずに棄却するようにしてもよい。これは以下の動作例においても同様である。
【００７４】
次に、本実施形態における第２の動作例を説明する。図７は第２の動作例における通信の様子を示している。第２の動作例においては、図７（ａ）のように証明書要求情報の転送の様子は第１の動作例と同様であるが、同図（ｂ）のように、返信情報の送信においては、証明書要求情報の転送時に信頼の輪の構築に参加したノードを逆にたどっていく。
【００７５】
第１の動作例と同様に、ノード１Ａはノード１Ｎからノード１Ｎの公開鍵証明書を取得し、その署名者であるノード１Ｍの公開鍵証明書を要求するための証明書要求情報をブロードキャストする。この証明書要求情報には、ノード１Ａがノード１Ｍの公開鍵証明書を要求していることを示す情報と、証明書要求情報を中継したノード（最初はノード１Ａ）を示す中継ノード情報と、経由ノード（最初はノード１Ａ）を示す経由ノード情報（経由情報）とが含まれている。なお、第１の動作例とは異なり、証明書要求情報には公開鍵証明書は付加されない。
【００７６】
図示せぬノードが証明書要求情報を受信した場合、第１の動作例と同様に、証明書要求情報をそのままブロードキャストする。ノード１Ｃ（ノード１Ｂも同様）が証明書要求情報を受信した場合、ノード１Ｃは中継ノード情報を参照することにより、ノード１Ａが送信者であることを知り、自身の記憶部１５の被信頼ノードリスト中にノード１Ａが含まれているかどうか判断する。ノード１Ｃの被信頼ノードリストにはノード１Ａが含まれているので、ノード１Ｃは信頼の輪の構築に参加すべきであると判断する。ノード１Ｃは、証明書要求情報中の中継ノード情報を自身の情報に書き換え、経由ノード情報の末尾に自身の情報を追加し（経由ノード情報を更新し）、証明書要求情報をブロードキャストする。
【００７７】
ノード１Ｆはこの証明書要求情報を受信し、証明書要求情報中の中継ノード情報と記憶部１５中の被信頼ノードリストとを参照することにより、自身がノード１Ｃから信頼されていると認識し、信頼の輪の構築に参加すべきであると判断する。ノード１Ｆは、証明書要求情報に対して、送信者情報を自身の情報に書き換えると共に、経由ノード情報に自身の情報を追加し、証明書要求情報をブロードキャストする。
【００７８】
証明書要求情報を受信したノード１Ｊは他のノードと同様に、証明書要求情報中の中継ノード情報と記憶部１５中の被信頼ノードリストを参照することにより、自身がノード１Ｆから信頼されていると認識し、信頼の輪の構築に参加すべきであると判断する。また、第１の動作例と同様に、ノード１Ｊは記憶部１５中の証明書リポジトリに格納されているノード１Ｍの公開鍵証明書（ＫＭ／ＳＪ）をノード１Ａに対して送信すべきであると判断する。
【００７９】
ノード１Ｊは返信情報を作成し、ノード１Ｆまでの通信経路を確立し、返信情報をノード１Ｆへ送信する。この返信情報には、最終宛先がノード１Ａであることを示す最終宛先情報と、ノード１Ａまでに経由するノードを示す経由ノード情報（返信経由情報）と、ノード１Ｊが所持する公開鍵証明書（ＫＭ／ＳＪ）とを含んでいる。
【００８０】
ノード１Ｆはこの返信情報を受信し、経由ノード情報が示す次の経由ノードであるノード１Ｃまでの通信経路を確立し、返信情報をノード１Ｃへ送信する。この返信情報には、公開鍵証明書（ＫＪ／ＳＦ）が付加される。この返信情報を受信したノード１Ｃは、同様に、返信情報に公開鍵証明書（ＫＦ／ＳＣ）を付加し、ノード１Ａへ送信する。なお、ノード１Ｊがノード１Ａ宛の返信情報を送信する場合に、経由ノード情報が示すノードを経由するようなノード１Ａまでの通信経路を予め確立するようにしてもよい。
【００８１】
ノード１Ａは、公開鍵証明書（ＫＭ／ＳＪ）・（ＫＪ／ＳＦ）・（ＫＦ／ＳＣ）が付加された返信情報を受信する。ノード１Ａは第１の動作例と同様に、これらの公開鍵証明書と、自身が所持する公開鍵証明書（ＫＣ／ＳＡ）とから公開鍵ＫＭの検証を行い、続いて、公開鍵ＫＮの検証を行う。公開鍵ＫＮの検証に成功した場合、ノード１Ａはノード１Ｎと暗号化通信を開始する。
【００８２】
次に、第２の動作例における認証ノードおよび中継ノードの動作を説明する。ノードＸ、Ｙ、Ｚの定義は第１の動作例と同様とする。認証ノードであるノードＸの動作は図４および図５と同様である。ただし、証明書要求情報には信頼の輪の構築に参加したノードを示す経由ノード情報が付加され、中継ノードが所持する公開鍵証明書は付加されない。
【００８３】
図８は中継ノードの動作を示すフローチャートである。図において、ステップＳ８０１〜ステップＳ８０５の動作は、図６におけるステップＳ６０１〜ステップＳ６０５の動作と同様であるので、説明を省略する。ただし、ステップＳ８０５において作成される返信情報には、最終宛先がノードＸであることを示す最終宛先情報と、自身が所持するノードＺの公開鍵証明書と、経由ノード情報とが含まれている。
【００８４】
続いて、通信部１１は制御部１６と連携し、経由ノード情報が示す経由ノードまでの通信経路を確立する。制御部１６は返信情報を通信部１１へ出力し、通信部１１はアンテナ１０を介して返信情報を経由ノードへ送信する（ステップＳ８０６）。ステップＳ８０７〜ステップＳ８０９の動作は図６のステップＳ６０７〜ステップＳ６０９の動作と同様であるので、説明を省略する。ただし、ステップＳ８０９において、証明書要求情報に公開鍵証明書は付加されない。ステップＳ８１０において、制御部１６は、制限時間以内に返信情報を受信するかどうか判定する。
【００８５】
ステップＳ８１０においてＹＥＳと判定された場合、通信部１１は制御部１６と連携し、返信情報中の経由ノード情報が示す次の経由ノードまでの通信経路を確立する。制御部１６は、経由ノード情報が示す次の経由ノードによって発行された公開鍵証明書を返信情報に付加し、返信情報を通信部１１へ出力する。通信部１１はアンテナ１０を介して返信情報を次の経由ノードへ送信する（ステップＳ８１１）。ステップＳ８０７、ステップＳ８０８、またはステップＳ８１０においてＮＯと判定された場合、証明書要求情報は送信されずに処理が終了する。
【００８６】
第２の動作例によれば、第１の動作例と比較して、ノード１Ｊからノード１Ａまでの返信情報の転送に時間が掛かる可能性があるが、証明書要求情報に公開鍵証明書が付加されないので、証明書要求情報の容量を削減することができる。特に、証明書要求情報がブロードキャストされることによる無用な通信が発生するため、この容量を削減することにより、ネットワークのトラヒックを削減することができる。なお、各ノードがセッション（一連の通信に係る処理）を短時間保持し、その間の通信経路を保持すると仮定した場合は、証明書要求情報および返信情報に経由ノード情報が含まれていなくてもよい。
【００８７】
次に、本実施形態における第３の動作例を説明する。第１の動作例と同様に、ノード１Ａはノード１Ｎからノード１Ｎの公開鍵証明書を取得し、その署名者であるノード１Ｍの公開鍵証明書を要求するための証明書要求情報を作成する。図９は第３の動作例における通信の様子を示している。図９（ａ）は、各ノードによる証明書要求情報の転送の様子を示している。この図も、証明書要求情報の転送の一部を示したものである。第３の動作例においては、信頼の輪の構築に参加するノードは証明書要求情報をブロードキャストするのではなく、自身が信頼する１以上のノードを選択し、それらのノードに対して、証明書要求情報を送信する。この証明書要求情報には、ノード１Ａがノード１Ｍの公開鍵証明書を要求していることを示す情報と、証明書要求情報を中継したノード（最初はノード１Ａ）を示す中継ノード情報とが含まれている。
【００８８】
ノード１Ａは証明書要求情報を、自身が信頼するノード１Ｂおよび１Ｃへ送信する。この場合、ノード１Ａはノード１Ｂおよびノード１Ｃまでの通信経路を確立し、証明書要求情報を送信する。図示せぬノードは証明書要求情報を宛先のノードまで転送する。ノード１Ｃ（ノード１Ｂも同様）が証明書要求情報を受信した場合、ノード１Ｃは、証明書要求情報中の中継ノード情報と記憶部１５中の被信頼ノードリストを参照することにより、自身がノード１Ａから信頼されていると認識し、信頼の輪の構築に参加すべきであると判断する。ノード１Ｃは、証明書要求情報に対して、中継ノード情報を自身の情報に書き換えると共に、ノード１Ａから発行された自身の公開鍵証明書（ＫＣ／ＳＡ）を付加し、自身が信頼するノード（記憶部１５中の信頼ノードリストで示されるノード：ノード１Ｆおよび１Ｇ）へ証明書要求情報を送信する。
【００８９】
ノード１Ｆも同様の動作によって証明書要求情報を転送する。ノード１Ｊはこの証明書要求情報を受信し、第１および第２の動作例と同様に、ノード１Ｍの公開鍵証明書（ＫＭ／ＳＪ）をノード１Ａに対して送信すべきであると判断する。図９（ｂ）はノード１Ｊによる返信情報の送信の様子を示している。第１の動作例と同様に、ノード１Ｊはノード１Ａまでの通信経路を確立し、返信情報を送信する。ノード１Ａは第１の動作例と同様に、公開鍵ＫＭの検証を行い、続いて、公開鍵ＫＮの検証を行う。公開鍵ＫＮの検証に成功した場合、ノード１Ａはノード１Ｎと暗号化通信を開始する。
【００９０】
第３の動作例によれば、信頼の輪の構築に参加する中継ノードが、自身の信頼するノード宛に証明書要求情報を転送するので、証明書要求情報をブロードキャストする場合と比較して、通信量を削減することができる。なお、各ノードが証明書要求情報を自身の信頼するノード宛に転送する場合に、複数の信頼ノードの中から適宜ノードを選択して送信するようにしてもよい。
【００９１】
次に、本実施形態における第４の動作例を説明する。第４の動作例においては、証明書要求情報の転送処理は第３の動作例と同様であり、返信情報は第２の動作例と同様に、証明書要求情報の転送において信頼の輪の構築に参加したノードをたどって転送される。この場合の証明書要求情報は、第２の動作例における証明書要求情報と同様である。
【００９２】
次に、本実施形態における第５の動作例を説明する。以下の第５〜第８の動作例においては、ノード１Ａはまずノード１Ｎからノード１Ｎの公開鍵ＫＮと、ノード１Ｎの被信頼情報とを受信する。被信頼情報は、ノード１Ｎの記憶部１５中の被信頼ノードリストで示されるノードの情報である。ノード１Ａはノード１Ｎの公開鍵ＫＮを検証するために、ノード１Ｎの公開鍵証明書を所持しているノードを探索する。その場合、ノード１Ａはノード１Ｎの被信頼情報を参照し、ノード１Ｎを信頼しているノード１Ｍから公開鍵証明書（ＫＮ／ＳＭ）を取得すればよいと認識する。ノード１Ａは証明書要求情報を作成し、第１の動作例と同様にブロードキャストする。
【００９３】
この証明書要求情報には、ノード１Ａがノード１Ｎの公開鍵証明書を要求していることを示す情報と、証明書要求情報を中継したノード（最初はノード１Ａ）を示す中継ノード情報と、ノード１Ｍがノード１Ｎの公開鍵証明書を所持していることを示す証明書所持情報とが含まれている。証明書要求情報を受信した各ノードの動作は第１の動作例と同様である。ただし、ノード１Ｊは証明書要求情報をブロードキャストするのではなく、ノード１Ｍにユニキャストする。
【００９４】
ノード１Ｊの動作は以下のように行われる。ノード１Ｊが証明書要求情報を受信した場合、制御部１６は、中継ノード情報によって示されるノード１Ｆが記憶部１５の被信頼ノードリスト中にあることにより、信頼の輪の構築に参加すべきであると判断する。また、制御部１６は記憶部１５中の信頼ノードリストに、証明書要求情報中の証明書所持情報によって示されるノード１Ｍが存在していることを認識する。これにより、制御部１６は証明書要求情報をブロードキャストするのではなく、ノード１Ｍ宛に送信すればよいと判断する。これにより、ブロードキャストに伴う無用な通信の発生を抑えることができる。なお、第１の動作例と同様に、ノード１Ｊが証明書要求情報をブロードキャストするようにしてもよい。
【００９５】
ノード１Ｍは証明書要求情報を受信し、返信情報を作成し、第１あるいは第３の動作例と同様に、ノード１Ａまでの通信経路を確立し、返信情報を送信する。この返信情報には、公開鍵証明書（ＫＮ／ＳＭ）・（ＫＭ／ＳＪ）・（ＫＪ／ＳＦ）・（ＫＦ／ＳＣ）・（ＫＣ／ＳＡ）が付加されている。ノード１Ａは返信情報を受信し、公開鍵証明書（ＫＮ／ＳＭ）中の公開鍵ＫＮとノード１Ｎから取得した公開鍵ＫＮとが一致するかどうか検証を行う。両者が一致した場合、ノード１Ａはノード１Ｎと暗号化通信を開始する。
【００９６】
次に、本実施形態における第６の動作例を説明する。第６の動作例においても、第５の動作例と同様に、ノード１Ａはノード１Ｎから公開鍵ＫＮとノード１Ｎの被信頼情報とを受信する。ノード１Ａは第５の動作例と同様に証明書要求情報をブロードキャストする。以後の動作は第５の動作例と同様である。ただし、第２または第４の動作例と同様に、証明書要求情報には経由ノード情報が付加され、公開鍵証明書は付加されない。ノード１Ｍは証明書要求情報を受信し、返信情報を作成する。返信情報にはノード１Ｎの公開鍵証明書（ＫＮ／ＳＭ）が付加される。ノード１Ｍは、経由ノード情報に基づいて、ノード１Ｊまでの通信経路を確立し、返信情報を送信する。この返信情報は第２または第４の動作例と同様に、ノード１Ｆ・１Ｃによってノード１Ａへ転送される。返信情報を受信したノード１Ａの動作は第５の動作例と同様である。
【００９７】
次に、本実施形態における第７の動作例を説明する。第７の動作例においても、ノード１Ａはノード１Ｎから公開鍵ＫＮとノード１Ｎの被信頼情報とを受信する。ノード１Ａは証明書要求情報を作成し、自身が信頼するノードに対して証明書要求情報を送信する。以下の各ノードの動作は第３の動作例と同様であり、信頼の輪の構築に参加するノードは、自身が信頼するノードへ証明書要求情報を転送する。ノード１Ｍは証明書要求情報を受信し、公開鍵証明書（ＫＮ／ＳＭ）が付加された返信情報を作成する。返信情報がノード１Ａまで転送される動作は第1または第３の動作例と同様であり、ノード１Ｍはノード１Ａまでの通信経路を確立し、返信情報を送信する。返信情報を受信したノード１Ａの動作は第５の動作例と同様である。
【００９８】
次に、本実施形態における第８の動作例を説明する。第８の動作例においても、ノード１Ａはノード１Ｎから公開鍵ＫＮとノード１Ｎの被信頼情報とを受信する。ノード１Ａは証明書要求情報を作成し、自身が信頼するノードに対して証明書要求情報を送信する。以下の各ノードの動作は第４の動作例と同様であり、信頼の輪の構築に参加するノードは、自身が信頼するノードへ証明書要求情報を転送する。ノード１Ｍは証明書要求情報を受信し、公開鍵証明書（ＫＮ／ＳＭ）が付加された返信情報を作成する。返信情報がノード１Ａまで転送される場合の動作は第２または第４の動作例と同様であり、返信情報は経由ノード情報で示されるノードを経由してノード１Ｍからノード１Ａまで転送される。返信情報を受信したノード１Ａの動作は第５の動作例と同様である。
【００９９】
次に、第３・第４・第７・第８の動作例におけるノードの選択方法について説明する。これらの動作例においては、各ノードは自身が信頼している１以上のノードを選択し、そのノードに証明書要求情報を送信する。絶対的に信頼できるＣＡを持たない無線アドホックネットワークにおいては、信頼の輪の構築に関して、信頼の輪の信頼度と構築速度との間にトレードオフがあることが想定される。そこで、この両者の重み付けによってノードを選択する方法を提案する。
【０１００】
この選択方法を、図１０および図１１により説明する。図にはノード１ａ〜１ｏの各ノードが示されており、各ノードを結ぶ矢印はノード間の信頼関係を示している。なお、図において、一部のノードは図示が省略されている。矢印の根元のノードは矢印の先のノードに対して公開鍵証明書を発行している。例えば、ノード１ａはノード１ｉに対して公開鍵証明書を発行している。すなわちノード１ａはノード１ｉを信頼している。また、各ノードのそばに記載された数字は、公開鍵証明書の発行・被発行数を示している。例えば、ノード１ａは、４つのノードに対して公開鍵証明書を発行しており、１つのノードから公開鍵証明書を発行されている。各ノードは記憶部１５中の信頼ノードリストおよび被信頼ノードリストを参照することにより、公開鍵証明書の発行・被発行数を知ることができる。また、各ノードは、自身の周囲ノードに対して、上記の発行・被発行数を予め通知しているものとする。
【０１０１】
各ノードが構築速度を重視して信頼の輪の構築を行う場合、公開鍵証明書の発行数の多いノード（多くのノードを信頼しているノード）を優先的に選択する。例えば、ノード１ａが周囲ノードを選択する場合、周囲ノードの中で最も公開鍵証明書の発行数が多いノード１ｉを選択する。発行数が同じ場合は、任意にノードを選択すればよい。各ノードが同様の動作を行うことにより、図１０の点線の矢印で示される経路で信頼の輪の構築が行われる。
【０１０２】
各ノードが信頼度を重視して信頼の輪の構築を行う場合、公開鍵証明書の被発行数の多いノード（多くのノードから信頼されているノード）を優先的に選択する。例えば、ノード１ａが周囲ノードを選択する場合、周囲ノードの中で最も公開鍵証明書の被発行数が多いノード１ｃまたはノード１ｅを選択する。被発行数が同じ場合は、任意にノードを選択すればよい。各ノードが同様の動作を行うことにより、図１１の点線の矢印で示される経路で信頼の輪の構築が行われる。
【０１０３】
なお、ノードの選択数は１に限られる訳ではなく、公開鍵証明書の発行数または被発行数が多い方から適宜複数のノードを選択するようにしてもよい。
【０１０４】
次に、上述した周囲ノードの選択方式において、互いにトレードオフの関係にある信頼の輪の信頼度と構築速度とを的確に選択するための手法を提案する。以下の式は、信頼度と構築速度とに対する重み付けを式で示したものである。
ｗｅｉｇｈｔ＝ｏｕｔｅｄｇｅ×α＋ｉｎｅｄｇｅ×β  ・・・（１）
α＋β＝１                                          ・・・（２）
【０１０５】
上記の（１）式において、ｗｅｉｇｈｔは重み付けを示す値である。ｏｕｔｅｄｇｅは特定の周囲ノードに注目した場合の外向きの矢印の本数（公開鍵証明書の発行数）であり、ｉｎｅｄｇｅは内向きの矢印の本数（公開鍵証明書の被発行数）である。αおよびβは０以上であると共に、（２）式を満たす数である。各ノードは周囲ノードを選択する場合に、αおよびβを適宜決定し、（１）式により、各々の周囲ノードについてｗｅｉｇｈｔを算出し、ｗｅｉｇｈｔが最大となるノードを選択する。
【０１０６】
αおよびβに関しては、信頼の輪の構築速度を最も重視する場合には、α＝１、β＝０となる。また、信頼度を最も重視する場合には、α＝０、β＝１となる。なお、各ノードの構築速度と信頼度の重視の度合により、各ノードはαおよびβの値を適宜選択すればよい。
【０１０７】
次に、各ノードによる公開鍵証明書の管理について説明する。従来の公開鍵証明書分散管理方式においては、各ノードはネットワークに参加する全てのノードの公開鍵証明書を管理していた。しかし、本実施形態においては、各ノードは、自身を信頼するノードが発行した自身の公開鍵証明書と、自身が信頼する周囲ノードの公開鍵証明書とを記憶部１５中の証明書リポジトリ内に保持する。なお、周囲ノードの公開鍵証明書に加えて、本実施形態における信頼の輪の構築時に他のノードから取得して一時記憶部１４に格納した公開鍵証明書のうち、自身が信頼する周囲ノードからｋホップ（ｋは正の整数）以内に存在するノードの公開鍵証明書を記憶部１５中の証明書リポジトリに格納して管理するようにしてもよい。また、本実施形態においては、自身が発行した公開鍵証明書および自身に対して発行された公開鍵証明書を各ノードが管理しているが、自身に対して発行された公開鍵証明書のみを管理するようにしてもよい。
【０１０８】
例えば、図１において、ノード１Ａは自身の周囲ノードであるノード１Ｂおよび１Ｃに加えて、これらのノードの周囲ノードであるノード１Ｄ〜１Ｇから公開鍵証明書を取得したとする。もし、ノード１Ｄ〜１Ｇがノード１Ｂまたはノード１Ｃからｋホップ以内に存在していれば、ノード１Ａはこれらのノードの公開鍵証明書を証明書リポジトリ内に保持する。なお、ｋの値は記憶部１５の容量に従って適宜変更されるようにしてもよい。
【０１０９】
また、各ノードは利用頻度の小さい公開鍵証明書を証明書リポジトリから動的に削除する。例えば、各ノードは、特定の公開鍵証明書を最後に利用した日時に関する情報を記憶部１５中に保持し、最後に利用してから所定時間経過しても再度の利用がなされなかった公開鍵証明書を削除する。あるいは一回限りしか利用しないことがわかっている公開鍵証明書を利用後に削除する。以上により、各ノードが保持する公開鍵証明書の有効性が保証される。
【０１１０】
次に、本実施形態における、目的の公開鍵証明書を所持するノードの探索が成功しなかった場合について説明する。例えば、各ノードが自身の信頼する周囲ノードを一つだけ選択し、そのノードに対して証明書要求情報を送信する場合、送信先のノードが周囲ノードを一つも信頼していないことにより、探索が失敗する可能性がある。その場合は、最初のノードから探索をやり直したり、探索に失敗したノードの一つ手前のノードから、ノードの選択方式を変更するなどにより探索をやり直したりする。また、本実施形態においては、ある決められた制限時間以内または制限ホップ数以内で信頼の輪が構築されなかった場合は、構築を停止する。
【０１１１】
次に、本実施形態によって構築された信頼の輪の可視化について説明する。目的のノードまでの信頼の輪が構築された場合、認証ノード（例えば図１におけるノード１Ａ）においては、ユーザに対して確認を促すため、制御部１６は表示部１３へ表示データを出力する。表示部１３はこの表示データに基づいた表示を行う。図１２は表示部１３による表示例を示す参考図である。この表示によって、自ノードから相手ノードまでの信頼の輪の構築の様子がユーザに対して通知される。
【０１１２】
表示部１３には、信頼の輪のパスの様子や、信頼の輪を構築する各ノードがいくつの周囲ノードから信頼されているのかなどが表示される。ユーザは表示部１３を参照し、この信頼の輪を用いて相手ノードと通信を行うかどうか判断する。ユーザが通信を行うと判断し、操作部１２より通信の開始指示を入力すると、操作部１２はユーザによる指示を示す信号を制御部１６へ出力する。制御部１６はこの信号に基づいて、通信部１１等を制御し、相手ノードとの暗号化通信を開始する。
【０１１３】
また、複数のパスが構築された場合、表示部１３には複数のパスが表示される。図１３はこの場合の表示例を示す参考図である。さらに、信頼の輪を構築することができない場合には、図１４のように表示される。自ノードから相手ノードまでの信頼の輪が構築されなかった場合でも、表示部１３には、周囲のノードから信頼度数が高いノードに関しては、その信頼度が表示される。
【０１１４】
以上説明したように、本実施形態によれば、通信相手となるノードの公開鍵の認証を行う必要性が発生したときに、信頼の輪を構築する各ノードから必要なノードのみの公開鍵証明書を取得するようにしたので、ネットワークに参加する全てのノードの公開鍵を各ノードが管理する従来の公開鍵分散管理方式と比較して、通信資源や各ノードの資源を無駄に使うことがなく、公開鍵の管理コストを低減することができる。例えば、認証ノードは被認証ノードの公開鍵の認証に必要なノードのみの公開鍵証明書を取得するので、各ノードがネットワークに参加する全ノードの証明書リポジトリ内の情報を取得する従来の公開鍵分散管理方式と比較して、通信資源の使用量を削減することができる。
【０１１５】
また、各ノードは自身の信頼するノードのみの公開鍵証明書を証明書リポジトリに保持するので、ネットワークに参加するノード数が増加しても、各ノードによるメモリおよびＨＤＤ資源の使用量を従来よりも大幅に低減することができる。さらに、各ノードは自身に対して発行された公開鍵証明書のみ、あるいは、その公開鍵証明書に加えて、自身が発行した公開鍵証明書を管理するので、各ノードが他のノードから公開鍵証明書を取得する際に、その公開鍵証明書の有効性が保証される。したがって、本実施形態における通信システムにおいては、失効証明書リストに基づいた公開鍵証明書の有効性の確認が必要でないため、失効証明書リストの交換に伴う通信資源の使用量を削減することができる。以上により、公開鍵の管理コストを低減することができる。
【０１１６】
また、信頼の輪の構築において、各ノードが自身が信頼するノードの中から、証明書要求情報を送信するノードを選択する際に、周囲ノードの信頼数・被信頼数を考慮することにより、信頼の輪の構築速度および信頼度の重視の度合に基づいた構築を行うことができる。
【０１１７】
また、制限時間以内または制限ホップ数以内で信頼の輪の構築を行うことができなかった場合に、信頼の輪の構築を中止することにより、不要な通信の発生を抑えることができる。特に、各ノードが証明書要求情報をブロードキャストする場合には、不要な通信が発生しやすいので、通信量の削減を行うことができる。
【０１１８】
また、構築した信頼の輪の様子をユーザに対して通知することにより、ユーザに対して確認を促すことができる。特に、複数の信頼の輪のパスが構築された場合に、どのパスを用いて通信を行うのかをユーザが選択することができるようになる。
【０１１９】
次に、本発明の他の実施形態について説明する。図１５は、本実施形態による通信システムの構成を示す概略構成図である。図１５（ａ）に示されるように、本通信システムはノード２Ａ〜２Ｈによって構成されている。各ノードの内部構成は前述した実施形態と同様である。図１５（ｂ）は各ノードの信頼関係（公開鍵証明書の発行関係）を示している。例えば「２Ｆ→２Ａ」と示されているのは、ノード２Ｆがノード２Ａを信頼しており、ノード２Ａに対して公開鍵証明書（ＫＡ／ＳＦ）を発行していることを意味している。発行された公開鍵証明書は、前述した実施形態と同様に、その公開鍵証明書の発行元および発行先のノードにおいて、図２における記憶部１５の証明書リポジトリに格納される。また、図１５（ｂ）に示される各ノードの信頼関係は記憶部１５の信頼ノードリストおよび被信頼ノードリストに格納されている。
【０１２０】
本実施形態においては、ノード２Ａ（認証端末）がノード２Ｄ（被認証端末）と暗号化通信を行うため、ノード２Ｄの認証、すなわちノード２Ｄの公開鍵ＫＤの正当性の検証を行うとする。ノード２Ａは、公開鍵ＫＤについての公開鍵証明書を要求するために、証明書要求情報を送信するが、本実施形態においては、不要な情報の送信を抑え、証明書要求情報をノード２Ｄまで効率的に到達させるため、各ノードは以下のように動作する。各ノードは、信頼の輪を構築するため、他のノードへの経路に関する経路情報を予め所持しているものとする。この経路情報の収集には、無線アドホックネットワークにおけるルーティングプロトコルとしてＰｒｏａｃｔｉｖｅ型プロトコルを利用する。Ｐｒｏａｃｔｉｖｅ型プロトコルにおいては、定期的に経路情報を各ノード間で交換することにより、通信システムを構成する他のノードまでの経路に関する情報を各ノードが収集して、他のノードまでの経路に関するルーティングテーブルを構築し、保持する。
【０１２１】
図１６は、ノード２Ａが所持するルーティングテーブルの内容を示している。「Ｄｅｓｔｉｎａｔｉｏｎ  Ｎｏｄｅ」は到達先のノードを示している。「Ｎｅｘｔ  Ｈｏｐ  Ｎｏｄｅ」は、到達先のノードに到達する経路において、次に経由するノードを示している。「Ｎｅｘｔ  Ｈｏｐ  Ｎｏｄｅ」にノードの識別情報がない場合は、他のノードを経由することなく到達先のノードに到達することができることを示している。このようなルーティングテーブルは、各ノードの記憶部１５中に記憶されている。
【０１２２】
次に、各ノードにおけるルーティングテーブルの構築方法について説明する。Ｐｒｏａｃｔｉｖｅ型プロトコルは、以下の基本機能からなる。
（１）隣接するノードの発見プロセス
（２）ネットワークトポロジの構築プロセス
隣接ノードの発見プロセスにおいては、各ノードは、ノード間のハローメッセージの交換によってリンク状態を確認しあう。ネットワークトポロジの構築プロセスにおいては、各ノードは、ローカルなリンク情報をトポロジ制御メッセージに付加し、アドホックネットワーク全体にフラッディング広告して、その情報を得たノード自身が経路表を作成する。この際、フラッディングする制御パケットには、無駄なフラッディングを防ぐために、ＴＴＬ、ホップ数、メッセージシーケンス番号等が記入される。その後は、定期的に差分情報を広報しあうことにより、各ノードが持つネットワーク全体のルーティングテーブルが維持および管理される。
【０１２３】
次に、ノード２Ａがノード２Ｄの公開鍵ＫＤについての公開鍵証明書を取得するまでの各ノードの動作について説明する。ノード２Ａにおいて制御部１６は記憶部１５からルーティングテーブルを読み出して参照する（図１７（ａ）のルーティングテーブル２００Ａ）。ノード２Ｄへは直接到達することができないため、制御部１６は、ノード２Ａが信頼するノードへ証明書要求情報を送信すべきであると判断し、記憶部１５から信頼ノードリストを読み出して参照する。図１５（ｂ）に示されるように、ノード２Ａはノード２Ｂおよび２Ｅを信頼しているので、制御部１６は、これらのノードに対する新たな証明書要求情報を作成する。
【０１２４】
図１７（ａ）には、ノード２Ａによって作成された証明書要求情報２０１に含まれる情報の内容が示されている。経由ノード情報２０１ａは、経由するノードの情報であり、ルーティングテーブル２００Ａに基づいた情報である。この場合には、ノード２Ａが信頼しているノード２Ｂおよび２Ｅが経由ノードとして指定され、ノード２Ｂを経由するための経由ノードとして、ノード２Ａから直接信頼されていないノード２Ｆが指定されている。認証ノード情報２０１ｂは、認証を行う主体のノード（この場合、ノード２Ａ）の識別情報を示している。被認証ノード情報２０１ｃは、最終的な認証の対象となるノード（この場合、ノード２Ｄ）の識別情報を示している。探索制限数情報２０１ｄは、目的とする最終的な認証の対象ノードまでの間に経由する、信頼の輪に加わるノードの最大数を示している。
【０１２５】
制御部１６は、作成した証明書要求情報を通信部１１へ出力する。通信部１１は、アンテナ１０を介して証明書要求情報をブロードキャストする。この証明書要求情報は、ノード２Ａから電波の届く範囲内に存在するノード２Ｅ、ノード２Ｆ、およびノード２Ｈによって受信される（図２０（ａ）参照）。各ノードにおいて、通信部１１はアンテナ１０を介して証明書要求情報を受信し、制御部１６へ出力する。
【０１２６】
証明書要求情報を受信したノード２Ｈの動作は以下のようになる。ノード２Ｈの制御部１６は、証明書要求情報中の被認証ノード情報を参照し、ノード２Ｈが被認証ノードであるかどうかを判断する。被認証ノードはノード２Ｄであるから、制御部１６は、ノード２Ｈが被認証ノードではないと判断する。続いて、制御部１６は経由ノード情報を参照し、ノード２Ｈが経由ノードであるかどうか判断する。経由ノード情報中にノード２Ｈの識別情報がないことから、制御部１６は、ノード２Ｈが経由ノードでないと判断し、証明書要求情報を棄却する。
【０１２７】
また、ノード２Ａからの証明書要求情報を受信したノード２Ｅの動作は以下のようになる。ノード２Ｅの制御部１６は証明書要求情報中の被認証ノード情報を参照し、ノード２Ｅが被認証ノードではないと判断する。続いて、制御部１６は、証明書要求情報中の経由ノード情報を参照し、経由ノード情報中にノード２Ｅの識別情報があることから、信頼の輪の構築に参加すべきであると判断する。制御部１６は記憶部１５からルーティングテーブル（図１７（ｂ）のルーティングテーブル２００Ｅ）を読み出して参照し、被認証ノードであるノード２Ｄへは直接到達することができないため、信頼しているノード２Ｆを経由ノードとして指定する。また、制御部１６は、ノード２Ｆに到達するための経由ノードとしてノード２Ａを指定する。
【０１２８】
制御部１６は証明書要求情報を作成する。図１７（ｂ）には、ノード２Ｅによって送信される証明書要求情報２０２の内容が示されている。経由ノード情報２０２ａの内容は上述したとおりであり、認証ノード情報２０２ｂおよび被認証ノード情報２０２ｃの内容は、ノード２Ａから受信した証明書要求情報の内容と同一である。ノード２Ａが直接信頼するノード２Ｅを経由したことから、探索制限数情報２０２ｄが示す数は１だけ減らされる。上記の内容は、ノード２Ａから送信された証明書要求情報と同様であるが、さらに、公開鍵証明書（ＫＥ／ＳＡ）を含む証明書情報２０２ｅが付加されている。証明書情報２０２ｅは、認証ノードであるノード２Ａによる公開鍵の検証の際に必要となる情報である。
【０１２９】
制御部１６は、信頼の輪の構築に参加すべきであると判断したので、記憶部１５の証明書リポジトリから必要な公開鍵証明書を読み出して、証明書要求情報に付加する。この場合、制御部１６は記憶部１５の証明書リポジトリから、認証ノードであるノード２Ａによって発行された公開鍵証明書（ＫＥ／ＳＡ）を読み出し、証明書要求情報に付加する。なお、証明書要求情報に他の公開鍵証明書が既に付加されている場合には、その公開鍵証明書に含まれる公開鍵によって示されるノードを既に経由してきたことが分かるので、制御部１６は、そのノードによって発行された公開鍵証明書を付加する。また、次に公開鍵証明書を証明書要求情報に付加すべきノードを指定する情報を証明書要求情報に別途格納するようにし、証明書要求情報を受信したノードが、その情報に基づいて、必要な公開鍵証明書を証明書要求情報に付加するようにしてもよい。
【０１３０】
制御部１６は、作成した証明書要求情報を通信部１１へ出力する。通信部１１は、アンテナ１０を介して証明書要求情報をブロードキャストする。この証明書要求情報は、ノード２Ｅから電波の届く範囲内に存在するノード２Ａ、ノード２Ｇ、およびノード２Ｈによって受信される（図２０（ｂ）参照）。ノード２Ｇおよびノード２Ｈは経由ノードではないため、これらのノードにおいては、証明書要求情報は棄却される。また、ノード２Ａは認証ノードであり、既に証明書要求情報を送信しているので、証明書要求情報を棄却する。
【０１３１】
一方、図２０（ａ）において、ノード２Ａからの証明書要求情報を受信したノード２Ｆの動作は以下のようになる。ノード２Ｆの制御部１６は証明書要求情報中の被認証ノード情報を参照し、ノード２Ｆが被認証ノードではないと判断する。続いて、制御部１６は、証明書要求情報中の経由ノード情報を参照し、ノード２Ｆがノード２Ｂへの経由ノードとして指定されていることから、証明書要求情報をノード２Ｂへ届けなければならないと判断する。制御部１６は記憶部１５からルーティングテーブル（図１８（ａ）のルーティングテーブル２００Ｆ）を読み出して参照し、ノード２Ｂへは直接到達することができるので、ノード２Ｂを経由ノードとして指定する。ノード２Ｆはノード２Ａによって直接信頼されているノードではなく、ノード２Ａによって信頼されているノードへ証明書要求情報を転送するためのノードであるため、公開鍵証明書の付加は行わない。制御部１６は証明書要求情報を作成し（図１８（ａ）の証明書要求情報２０３）、通信部１１へ出力する。通信部１１は、アンテナ１０を介して証明書要求情報をブロードキャストする。
【０１３２】
この証明書要求情報は、ノード２Ｆから電波の届く範囲内に存在するノード２Ａおよびノード２Ｂによって受信される（図２１（ａ）参照）。ノード２Ａは認証ノードであり、既に証明書要求情報を送信しているので、証明書要求情報を棄却する。証明書要求情報を受信したノード２Ｂの動作は以下のようになる。ノード２Ｂの制御部１６は証明書要求情報中の被認証ノード情報を参照し、ノード２Ｂが被認証ノードではないと判断する。続いて、制御部１６は、証明書要求情報中の経由ノード情報を参照し、経由ノード情報中にノード２Ｂの識別情報があることから、信頼の輪の構築に参加すべきであると判断する。制御部１６は記憶部１５からルーティングテーブル（図１８（ｂ）のルーティングテーブル２００Ｂ）を読み出して参照し、被認証ノードであるノード２Ｄへは直接到達することができないため、信頼しているノード２Ｃを経由ノードとして指定する。
【０１３３】
続いて、制御部１６は証明書要求情報を作成する（図１８（ｂ）の証明書要求情報２０４）。このとき、制御部１６は、信頼の輪の構築に参加すべきであると判断したので、記憶部１５の証明書リポジトリから必要な公開鍵証明書を読み出して、証明書要求情報に付加する。制御部１６は記憶部１５の証明書リポジトリから、ノード２Ａによって発行された公開鍵証明書（ＫB／ＳＡ）を読み出し、証明書要求情報に付加する。
【０１３４】
制御部１６は、作成した証明書要求情報を通信部１１へ出力する。通信部１１は、アンテナ１０を介して証明書要求情報をブロードキャストする。この証明書要求情報は、ノード２Bから電波の届く範囲内に存在するノード２Fおよびノード２Cによって受信される（図２１（ｂ）参照）。ノード２Fは経由ノードではないため、証明書要求情報を棄却する。証明書要求情報を受信したノード２Cの動作は以下のようになる。
【０１３５】
ノード２Cの制御部１６は証明書要求情報中の被認証ノード情報を参照し、ノード２Cが被認証ノードではないと判断する。続いて、制御部１６は、証明書要求情報中の経由ノード情報を参照し、経由ノード情報中にノード２Cの識別情報があることから、信頼の輪の構築に参加すべきであると判断する。制御部１６は記憶部１５からルーティングテーブル（図１９（ａ）のルーティングテーブル２００C）を読み出して参照し、被認証ノードであるノード２Dへは直接到達することができるので、ノード２Dを宛先ノードとして指定する。
【０１３６】
続いて、制御部１６は証明書要求情報を作成する（図１９（ａ）の証明書要求情報２０５）。このとき、制御部１６は、信頼の輪の構築に参加すべきであると判断したので、記憶部１５の証明書リポジトリから必要な公開鍵証明書を読み出して、証明書要求情報に付加する。ノード２Ｂから受信された証明書要求情報に既に公開鍵証明書（ＫＢ／ＳＡ）が付加されていることから、制御部１６は、ノード２Ｂによって発行された公開鍵証明書を証明書要求情報に付加すればよいと判断する。制御部１６は記憶部１５の証明書リポジトリから公開鍵証明書（ＫＣ／ＳＢ）を読み出し、証明書要求情報に付加する。
【０１３７】
制御部１６は、作成した証明書要求情報を通信部１１へ出力する。通信部１１は、アンテナ１０を介して証明書要求情報をノード２Ｄへ送信する（図２２（ａ）参照）。ノード２Ｄはこの証明書要求情報を受信する。ノード２Ｄの制御部１６は証明書要求情報中の被認証ノード情報を参照し、ノード２Ｄが被認証ノードであると判断する。したがって、制御部１６は、ノード２Ａへ返信するための返信情報を作成する（図１９（ｂ）の返信情報２０６）。ノード２Ｃから受信された証明書要求情報には公開鍵証明書（ＫＢ／ＳＡ）および（ＫＣ／ＳＢ）が付加されていることから、制御部１６は、ノード２Ｃによって発行された公開鍵証明書を返信情報に付加すればよいと判断する。
【０１３８】
制御部１６は記憶部１５の証明書リポジトリから公開鍵証明書（ＫＤ／ＳＣ）を読み出し、返信情報に付加する。この返信情報には、送信元である被認証ノード（ノード２Ｄ）の識別情報と、送信先である認証ノード（ノード２Ａ）の識別情報とが格納されている。制御部１６は、作成した返信情報を通信部１１へ出力する。通信部１１は、アンテナ１０を介して返信情報をノード２Ａへ送信する（図２２（ｂ）参照）。返信情報を返信する際の経路については限定されない。
【０１３９】
ノード２Ａはこの返信情報を受信する。返信情報を受信したノード２Ａの動作は前述した実施形態と同様である。すなわち、ノード２Ａは、返信情報に付加された公開鍵証明書を用いてノード２Ｄの公開鍵ＫＤの正当性を検証する。公開鍵ＫＤの正当性の検証に成功した場合、ノード２Ａはノード２Ｄと暗号化通信を開始する。
【０１４０】
なお、ノード２Ｃは、自身がノード２Ｄに対して発行した公開鍵証明書（ＫＤ／ＳＣ）を記憶部１５の証明書リポジトリに所持していることから、ノード２Ｃがノード２Ａへ返信情報を返信するようにしてもよい。すなわち、被認証ノードの公開鍵についての公開鍵証明書を所持するノードは、証明書要求情報を受信すると、返信情報を作成してノード２Ａへ送信し、被認証ノードの公開鍵についての公開鍵証明書を所持しないノードは、ルーティングテーブルに基づいて経由ノードを指定して証明書要求情報を他のノードへ送信することになる。
【０１４１】
また、前述した実施形態と同様に、ノード２Ａが通信前にノード２Ｄから予め公開鍵証明書（ＫＤ／ＳＣ）を受信し、その公開鍵証明書の署名情報に含まれる電子署名の署名者であるノード２Ｃを被認証ノードとしてもよい。さらに、各ノードは証明書要求情報をブロードキャストするのではなく、自身が信頼するノードへユニキャストで送信したり、自身が信頼するノードに到達する経路上の経由ノードへユニキャストで送信したりしてもよい。
【０１４２】
上述した本実施形態によっても、前述した実施形態と同様に、通信相手となるノードの公開鍵の認証を行う必要性が発生したときに、信頼の輪を構築する各ノードから必要なノードのみの公開鍵証明書を取得するようにしたので、ネットワークに参加する全てのノードの公開鍵を各ノードが管理する従来の公開鍵分散管理方式と比較して、通信資源や各ノードの資源を無駄に使うことがなく、公開鍵の管理コストを低減することができる。
【０１４３】
また、各ノードが証明書要求情報を送信する際に、ルーティングテーブルを参照し、被認証ノードまでの経路、および自身が信頼するノードまでの経路に関する情報に基づいて証明書要求情報の経由ノードを決定することにより、信頼の輪を効率的に構築することができる。さらに、信頼の輪の構築に参加したノードに信頼されていなくても、信頼の輪の構築に参加すべき他のノードへ証明書要求情報を転送する経由ノード（例えばノード２Ｆ）が存在することにより、被認証ノードまで証明書要求情報がより確実に転送される。
【０１４４】
以上、図面を参照して本発明の実施形態について詳述してきたが、具体的な構成はこれらの実施の形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。例えば、上記の実施形態においては、通信システムは無線アドホックネットワークであるとしたが、全てのノードが無線通信により互いに接続される形態でなくてもよい。すなわち、一部に通信ケーブルによって有線接続されたノードを含んでいてもよいし、全ノードが有線接続されていてもよい。本発明は、認証局（ＣＡ）を持たないネットワークに対しての広範な適用が可能である。
【産業上の利用可能性】
【０１４５】
本発明の活用例として、無線アドホックネットワークにおける公開鍵基盤の構築への適用が挙げられる。また、本発明は、無線ネットワークに限らず、その一部または全部が有線接続されたノードで構成され、認証局（ＣＡ）を持たないネットワークに対しても適用できる。
【図面の簡単な説明】
【０１４６】
【図１】本発明の一実施形態による通信システムの構成を示す概略構成図である。
【図２】ノードの構成を示すブロック図である。
【図３】第１の動作例における通信の様子を示す概略参考図である。
【図４】第１の動作例における認証ノードの動作を示すフローチャートである。
【図５】第１の動作例における認証ノードの動作を示すフローチャートである。
【図６】第１の動作例における中継ノードの動作を示すフローチャートである。
【図７】第２の動作例における通信の様子を示す概略参考図である。
【図８】第２の動作例における中継ノードの動作を示すフローチャートである。
【図９】第３の動作例における通信の様子を示す概略参考図である。
【図１０】周囲ノードの選択方法を説明するための概略参考図である。
【図１１】周囲ノードの選択方法を説明するための概略参考図である。
【図１２】表示部１３による表示例を示す参考図である。
【図１３】表示部１３による他の表示例を示す参考図である。
【図１４】表示部１３による他の表示例を示す参考図である。
【図１５】本発明の他の実施形態による通信システムの構成を示す概略構成図である。
【図１６】ルーティングテーブルの内容を示す参考図である。
【図１７】ルーティングテーブルおよび証明書要求情報の内容を示す参考図である。
【図１８】ルーティングテーブルおよび証明書要求情報の内容を示す参考図である。
【図１９】ルーティングテーブルおよび証明書要求情報の内容を示す参考図である。
【図２０】証明書要求情報の送信の様子を示す概略参考図である。
【図２１】証明書要求情報の送信の様子を示す概略参考図である。
【図２２】証明書要求情報の送信の様子を示す概略参考図である。
【符号の説明】
【０１４７】
１・・・ノード、１０・・・アンテナ、１１・・・通信部、１２・・・操作部、１３・・・表示部、１４・・・一時記憶部、１５・・・記憶部、１６・・・制御部。
【図１】
0004690007.tif 000002
【図２】
0004690007.tif 000003
【図３】
0004690007.tif 000004
【図４】
0004690007.tif 000005
【図５】
0004690007.tif 000006
【図６】
0004690007.tif 000007
【図７】
0004690007.tif 000008
【図８】
0004690007.tif 000009
【図９】
0004690007.tif 000010
【図１０】
0004690007.tif 000011
【図１１】
0004690007.tif 000012
【図１２】
0004690007.tif 000013
【図１３】
0004690007.tif 000014
【図１４】
0004690007.tif 000015
【図１５】
0004690007.tif 000016
【図１６】
0004690007.tif 000017
【図１７】
0004690007.tif 000018
【図１８】
0004690007.tif 000019
【図１９】
0004690007.tif 000020
【図２０】
0004690007.tif 000021
【図２１】
0004690007.tif 000022
【図２２】
0004690007.tif 000023