(57)【要約】  通信ネットワーク内の２つのノード間で信用性を確立するための方法及び装置。第１のノードは、ネットワークノードから、前記第１のノードに特有の認証データを受信する。前記認証データは、前記第１のノードについての検証データのコンパクト表現を導出するために使用可能である。前記第１のノードはまた前記ネットワーク内のすべてのノードの検証データの証明付きコンパクト表現も受信する。前記第１のノードは、前記ノードについての前記認証データから信用性情報を導出し、第２のノードへ、前記信用性情報と前記認証データの少なくとも一部とを含むメッセージを送信する。前記第２のノードは、前記ネットワーク内のすべてのノードの検証データの前記証明付きコンパクト表現の自分用のコピーを有しており、前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現と、前記受信した信用性情報および認証データとを用いて、前記第１のノードからの前記メッセージの真正性を検証する。
2013520070.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワーク内の２つのノード間で信用性を確立するための方法であって、
第１のノードにおいて、ネットワークノードから、前記第１のノードに特有の認証データと、前記ネットワーク内のすべてのノードの検証データのコンパクト表現と、を受信するステップであって、前記認証データから前記第１のノードについての検証データのコンパクト表現を導出可能であり、前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現は前記ネットワークノードによって証明される、ステップと、
前記ノードについての前記認証データから信用性情報を導出するステップと、
前記第１のノードから第２のノードへ、前記信用性情報と前記認証データの少なくとも一部とを含むメッセージを送信するステップであって、前記第２のノードも前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現を受信済みである、ステップと、
前記第２のノードにおいて、前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現と、前記受信した信用性情報および認証データとを用いて、前記第１のノードからの前記メッセージの真正性を検証するステップと、
を備えることを特徴とする方法。
【請求項２】
前記第１のノードの前記検証データの前記コンパクト表現はマークル木のルートを含み、前記マークル木は、前記第１のノードに特有の前記認証データと、所定の時間枠の中の基本基準時間に関係する複数の基準時間とから導出されたものである
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現は、前記ネットワーク内のすべてのノードの前記検証データから導出された、ブルームフィルタとマークル木のルートとのうちの一方を含む
ことを特徴とする請求項１又は２に記載の方法。
【請求項４】
前記第１のノードにおいて、前記第１のノードに特有の前記認証データと、前記第１のノードにおける時計から取得された情報から導出された単一の基準時間とから、マークル木の葉を導出するステップを更に備え、
前記信用性情報は、前記導出された葉から導出される
ことを特徴とする請求項１乃至３のいずれか１項に記載の方法。
【請求項５】
前記第２のノードは、
前記認証データと、前記第２のノードにおける時計から取得された情報から導出された基準時間とから、マークル木の葉を導出し、
前記信用性情報を検証し、
前記第１のノードの検証データの第２のコンパクト表現を導出し、
前記第１のノードの検証データの前記第２のコンパクト表現が、前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現と調和することを検証する
ことによって、前記第１のノードからの前記メッセージの真正性を検証する
ことを特徴とする請求項４に記載の方法。
【請求項６】
前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現は、ブルームフィルタを含んでおり、
検証データの前記第２のコンパクト表現が前記ブルームフィルタのメンバとして示されている場合に、前記第１のノードの検証データの前記第２のコンパクト表現は、前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現と調和する
ことを特徴とする請求項５に記載の方法。
【請求項７】
前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現は、前記ネットワーク内のすべてのノードの認証データから導出されたマークル木のルートを含んでおり、
前記マークル木のルートが前記第１のノードの検証データの前記第２のコンパクト表現から導出可能である場合に、前記第１のノードの検証データの前記第２のコンパクト表現は、前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現と調和する
ことを特徴とする請求項５に記載の方法。
【請求項８】
前記第１のノードにおいて、或るグループに属するすべてのネットワークノードが利用可能なグループ鍵を前記ネットワークノードから受信するステップと、
前記第１のノードにおいて、前記メッセージを前記第２のノードに送信する前に、前記メッセージの少なくとも一部を前記グループ鍵を用いて暗号化するステップと、
を更に備えることを特徴とする請求項１乃至７のいずれか１項に記載の方法。
【請求項９】
前記メッセージは、前記第２のノードからのクエリに応じて送信され、前記第２のノードからの前記クエリは、前記第１のノードによって送信された広告メッセージに応じて送信されたものである
ことを特徴とする請求項１乃至８のいずれか１項に記載の方法。
【請求項１０】
通信ネットワークで用いる移動通信ノードであって、
ネットワークノードから、前記ノードに特有の認証データと、前記ネットワーク内のすべてのノードの検証データのコンパクト表現と、を受信する受信器であって、前記認証データから前記ノードについての検証データのコンパクト表現を導出可能であり、前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現は前記ネットワークノードによって証明される、受信器と、
前記認証データから信用性情報を導出するプロセッサと、
前記信用性情報と前記認証データの少なくとも一部とを第２のノードに送信する送信器と、を備え、
前記第２のノードが、前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現と、受信された前記信用性情報および認証データとを用いてメッセージの真正性を検証するために、前記信用性情報を使用可能である
ことを特徴とする移動通信ノード。
【請求項１１】
時計を更に含み、
前記プロセッサは、前記ノードに特有の前記認証データと前記時計から取得された情報から導出された単一の基準時間とからマークル木の葉を導出するように構成され、
前記信用性情報は、前記導出された葉から導出される
ことを特徴とする請求項１０に記載の移動通信ノード。
【請求項１２】
グループ鍵を記憶するためのメモリを更に備え、
前記プロセッサは、前記メッセージを前記第２のノードに送信する前に、前記メッセージの少なくとも一部を前記グループ鍵を用いて暗号化するように構成される
ことを特徴とする請求項１０又は１１に記載の移動通信ノード。
【請求項１３】
前記検証データの前記コンパクト表現は、マークル木のルートを含み、前記マークル木は、前記ノードに特有の前記認証データと、所定の時間枠の中の基本基準時間に関係する複数の基準時間とから導出されたものである
ことを特徴とする請求項１０乃至１２のいずれか１項に記載の移動通信ノード。
【請求項１４】
前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現は、前記ネットワーク内のすべてのノードの前記認証データから導出された、ブルームフィルタとマークル木のルートとのうちの一方を含む
ことを特徴とする請求項１０乃至１３のいずれか１項に記載の移動通信ノード。
【請求項１５】
通信ネットワークで用いる移動通信ノードであって、
ネットワークノードによって証明された、前記ネットワーク内のすべてのノードの検証データのコンパクト表現を、前記ネットワークノードから受信する受信器と、
前記ネットワークノードによって証明された、前記ネットワーク内のすべてのノードの検証データの前記受信したコンパクト表現を記憶するメモリと、
を備え、
前記受信器は更に、広告側ノードからメッセージを受信するように構成されており、前記メッセージは、認証データと、前記広告側ノードについての認証データから導出された信用性情報と、を含み、
前記移動通信ノードは更に、前記ネットワーク内のすべてのノードの検証データの前記コンパクト表現と、前記受信した信用性情報と、前記広告側ノードについての前記受信した認証データと、を用いて前記メッセージの真正性を検証するプロセッサを備える
ことを特徴とする移動通信ノード。
【請求項１６】
時計を更に備え、
前記プロセッサは、前記信用性情報をマークル木の葉から導出された情報と比較することにより、前記信用性情報を検証するように構成され、
前記葉は、前記認証データと、前記時計から取得された時刻から導出された情報とから導出され、
前記プロセッサは更に、前記ネットワーク内のすべてのノードの検証データの第２のコンパクト表現を導出するように構成されていて、すべてのノードの検証データの前記第２のコンパクト表現が前記ネットワーク内のすべてのノードの検証データの前記記憶したコンパクト表現と調和するかどうかを検証する
ことを特徴とする請求項１５に記載の移動通信ノード。
【請求項１７】
通信ネットワークで用いるネットワークノードであって、
前記通信ネットワークに関連付けられた複数のノードの各々について、個々のノードに特有の認証データを導出すると共に、前記ネットワーク内のすべてのノードの検証データの証明付きコンパクト表現を導出するプロセッサと、
個々のノードに特有の前記認証データと、前記ネットワーク内のすべてのノードの検証データの証明付きコンパクト表現とを前記複数のノードの各々に送信する送信器と、
を備えることを特徴とするネットワークノード。
【請求項１８】
移動通信ノード上で実行された場合に、前記移動通信ノードを請求項１０乃至１６のいずれか１項に記載の移動通信ノードとして動作させるコンピュータ可読コードを含む、コンピュータプログラム。
【請求項１９】
ネットワークノード上で実行された場合に、前記ネットワークノードを請求項１７に記載のネットワークノードとして動作させるコンピュータ可読コードを含む、コンピュータプログラム。
【請求項２０】
コンピュータ可読媒体と、請求項１８又は１９に記載のコンピュータプログラムとを含むコンピュータプログラム製品であって、前記コンピュータプログラムは前記コンピュータ可読媒体上に記憶される
ことを特徴とするコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークにおける信用性の発見の分野に関する。
【背景技術】
【０００２】
ワイヤレスアドホックネットワークは、ある意味では、分散型のワイヤレスネットワークである。基地局との間で通信するのに用いるのと同じかまたはそれに類似した無線インタフェースを用いて、ネットワーク内の端末同士が相互に通信する。これを「直接モード」通信と呼ぶこともある。完全なアドホックワイヤレスネットワークの場合、既存のネットワークインフラ、例えば基地局等に頼る必要はない。その代わりに、個々のノードが、他のノードへのデータを転送することによってルーティングに参加し、それゆえ、どのノードがデータを転送するかという判定は、ネットワークの接続性に基づいて動的に行なわれる。もう少しコントロールされたアドホックネットワークでは、端末は、相互に通信することもできるし、および／または、既存のネットワークインフラと通信することもできる。これは、ネットワークインフラから何らかの支援を受けるアドホックネットワークとみなしてもよいだろう。典型的には、ワイヤレスアドホックネットワークは、直接モードを用いる場合、例えば数十メートルまたは数百メートルというように、距離が限定されている。もっと長い距離も可能だが、アドホック（移動）ノードとインフラをベースにした（固定）ノードとがいずれも同じスペクトルを用いる場合、干渉による問題を引き起こす可能性がある。
【０００３】
図１は、３つの例示するアドホックネットワークのシナリオを示す図である。図１ａは、ネットワーク制御によるローカルブレークアウトを示しており、ここで端末１は、端末３との通信を開始するためにネットワークインフラ２にコンタクトする。図１ｂは、「中継」シナリオを示しており、ここで端末１と３とは、相互に通信を確立するが、端末１だけがネットワーク２と通信する。図１ｃは、本当のアドホックネットワークシナリオを示し、ここで３つの端末１、３、４は、ネットワークインフラ２と通信することなく、直接、相互に通信する。典型的には、このシナリオの前に、最初の２つのシナリオのうちの１つが先行する。以下の記述は、ＬＴＥ（Ｌｏｎｇ  Ｔｅｒｍ  Ｅｖｏｌｕｔｉｏｎ）ネットワークを想定しているが、それらの概念が他のタイプのセルラーネットワークにも適用されることは理解されるであろう。
【０００４】
端末がアドホックネットワークを確立するには、或る程度の信用性が必要である。これは、典型的には、強固な認証と鍵の交換とを用いて達成されるが、このステップが行われる前に、迅速かつ双方の「隣接者の信用性の発見」が必要である。典型的には、或る端末（広告側ノード）が、その存在を広告し、もう１つの端末（応答側ノード）が応答してもよい。迅速な隣接者信用性発見のための軽い事前認証段階がない場合、２つの端末は、ＤｏＳ（ｄｅｎｉａｌ−ｏｆ  ｓｅｒｖｉｃｅ）攻撃にさらされてしまい、例えば、セキュリティの関連付けを確立する場合に電池残量を不要に浪費してしまう。
【０００５】
ＬＴＥ端末のことをユーザ装置（ＵＥ）と呼ぶ。この例では、アドホックワイヤレスネットワークは、展開されたＬＴＥインフラの派生物である。アドホックワイヤレスネットワークによって、ＬＴＥインフラを用いることなく、使用可能なＵＥの集合が互いの存在を感知し、および／または、多様な公的および私的サービスを広告することができるようになる。加えて、これらの使用可能なＵＥは、それらの周辺環境を常に感知することができ、従って、例えばレストランのメニュー／献立、公共交通の時刻表といった、近接性に基づくサービスからの広告を受信することができる。社会的活動に加えて、これらのサービスは、商業活動、マルチメディア、近接性に基づく広告、友達のプレゼンス等を含んでいてもよい。
【０００６】
ＵＥ１を使用中のユーザ（ボブ）がチェスのゲームをすることを希望していると広告し、ＵＥ３を使用中の興味を持ったユーザがボブの広告を検出して、彼とチェスのゲームの約束をすることにするというシナリオを考えよう。アリスとボブは、赤の他人であって、彼らの間にも彼らのＵＥの間にも信頼関係は存在しないことがありうる。第１のステップは、アリスが「隣接者信用性発見」プロトコルを開始することであり、それによって、アリスとボブは、お互いの正当性を相互にチェックすることができる。これが完了した後、鍵の交換を含めて、もっとセキュアな認証を行うことができる。
【０００７】
このタイプの環境では、アリスがボブの正当性をチェックすることは簡単ではない。さらに、そのような交換をするとすれば、いずれのＵＥも、近隣の悪意のあるノードによって送信される、なりすましによる鍵交換プロトコルメッセージの形でのＤｏＳ攻撃にさらされることを意味するであろう。また、鍵交換を始めた２つのノードが、それを完了したノードと同じであることを保証することもできない。
【０００８】
隣接者信用性の発見の問題に対する１つの解決策は、ネットワークインフラが、従来の公開鍵証明書を個々のユーザに提供することである。プライバシの理由で、これらの証明書は、長期のＩＤではなく、「仮名」を持つ短期のものであるべきである。ネットワークがすべての公開鍵を証明することが必要となることから、これは、ネットワークに多大なオーバヘッドを生じさせるであろう。また、個々の端末は、他のすべてのノード、または少なくとも、端末がアドホックネットワークを確立しうる他のすべてのノードの証明書を記憶（または、必要に応じて、取得）することが必要となりうるため、それは、端末にかかるオーバヘッドも意味するであろう。
【発明の概要】
【０００９】
発明者らは、隣接者信用性発見に関連する諸問題に気付き、ＤｏＳ攻撃のリスクを最小化しながら、ノードが接続の確立と鍵交換とに先立って隣接者信用性発見を行うことを可能にする、セキュアで効率的なやり方を考案した。
【００１０】
本発明の第１の態様によって、通信ネットワーク内の２つのノード間で信用性を確立するための方法を提供する。第１のノードが、第１のノード特有の認証データをネットワークノードから受信する。この認証データを用いて、第１のノードについての検証データのコンパクト表現を導出することができる。また、第１のノードは、ネットワーク内のすべてのノードの検証データの証明付きコンパクト表現も受信する。第１のノードは、第２のノードとの間でアドホックネットワークをセットアップすることを望んだ場合、そのノードについての認証データから信用性情報を導出し、信用性情報と少なくとも認証データの一部とを含むメッセージを第２のノードに送信する。第２のノードは、ネットワーク内のすべてのノードの検証データの証明付きコンパクト表現の自分用のコピーを有しており、ネットワーク内のすべてのノードの検証データのコンパクト表現と、受信された信用性情報および認証データとを用いて、第１のノードからのメッセージの真正性を検証する。検証データの証明付きコンパクト表現を両方のノードがネットワークから受信したのだから、それらは、さらにネットワークと通信する必要なしに、鍵交換の前に或る程度の信用性を確立することができる。
【００１１】
１つの選択肢として、第１のノードの検証データのコンパクト表現は、第１のノード特有の認証データと、所定の時間枠の中の基本基準時間に関係する複数の基準時間とから導出されたマークル木のルートを含む。また、基準時間を用いることによって、第２のノードは、メッセージの真正性を検証する際に、時間を用いて支援することができる。
【００１２】
別の選択肢として、ネットワーク内のすべてのノードの検証データのコンパクト表現は、ネットワーク内のすべてのノードの検証データから導出された、ブルームフィルタとマークル木のルートとのうちの一方を含む。
【００１３】
方法は、任意で、第１のノードにおいて、第１のノード特有の認証データと、第１のノードにおける時計から取得された情報から導出された単一の基準時間とから、マークル木の葉を導出することを含んでおり、ここで、導出された葉から信用性情報が導出される。これによって、第２のノードが、第２のノードにおいて時計から導出された情報を用いてメッセージの真正性を検証することが可能になる。第２のノードは任意で、認証データと、第２のノードにおける時計から取得された情報から導出された基準時間とから、マークル木の葉を導出し、信用性情報を検証し、第１のノードの検証データの第２のコンパクト表現を導出し、そして、第１のノードの検証データの第２のコンパクト表現が、ネットワーク内のすべてのノードの検証データのコンパクト表現と調和することを検証することによって、第１のノードからのメッセージの真正性を検証する。
【００１４】
別の選択肢として、ネットワーク内のすべてのノードの検証データのコンパクト表現は、ブルームフィルタを含んでおり、そして、第１のノードの検証データの第２のコンパクト表現は、検証データの第２のコンパクト表現がブルームフィルタのメンバとして示されている場合、ネットワーク内のすべてのノードの検証データのコンパクト表現と調和する。あるいは、ネットワーク内のすべてのノードの検証データのコンパクト表現は、ネットワーク内のすべてのノードの検証データから導出されたマークル木のルートを含んでおり、そして、第１のノードの検証データの第２のコンパクト表現は、マークル木のルートが第１のノードの検証データの第２のコンパクト表現から導出されうる場合、ネットワーク内のすべてのノードの検証データのコンパクト表現と調和する。
【００１５】
セキュリティをさらに向上させるため、方法は、任意で、さらに、第１のノードが、或るグループに属するすべてのネットワークノードが利用可能なグループ鍵をネットワークノードから受信することと、第１のノードが、メッセージを第２のノードに送信する前にメッセージの少なくとも一部をグループ鍵を用いて暗号化することとを含む。このようにして、メッセージの一部が暗号化され、グループの他のメンバだけがアクセスできるようにされてもよい。
【００１６】
メッセージは任意で、第１のノードによって送信された広告メッセージに応じて送信された、第２のノードからのクエリに応じて送信される。
【００１７】
本発明の第２の態様によって、通信ネットワークで用いる移動通信ノードを提供する。ノードは、ノードについての検証データのコンパクト表現がそこから導出されうるノード特有の認証データと、ネットワーク内のすべてのノードの検証データのコンパクト表現とを、ネットワークノードから受信するための受信器を備えており、ネットワーク内のすべてのノードの検証データのコンパクト表現は、ネットワークノードによって証明されている。また、ノードは、認証データから信用性情報を導出するためのプロセッサと、信用性情報と認証データの少なくとも一部とを第２のノードに送信するための送信器とを備えている。第２のノードは、信用性情報を利用することができ、それによって、ネットワーク内のすべてのノードの検証データのコンパクト表現と、受信された信用性情報および認証データとを用いてメッセージの真正性を検証することができる。
【００１８】
移動通信ノードは、任意で、さらに、時計を含み、ここで、プロセッサは、ノード特有の認証データと時計から取得された情報から導出された単一の基準時間とからマークル木の葉を導出するように構成されており、ここで信用性情報が、導出された葉から導出される。
【００１９】
１つの選択肢として、移動通信ノードはさらにグループ鍵を記憶するためのメモリを備え、ここで、プロセッサは、メッセージの少なくとも一部を、それを第２のノードに送信する前にグループ鍵を用いて暗号化するように構成される。
【００２０】
検証データのコンパクト表現は、任意で、ノード特有の認証データと、所定の時間枠の中の基本基準時間に関係する複数の基準時間とから導出されたマークル木のルートを含む。別の選択肢として、ネットワーク内のすべてのノードの検証データのコンパクト表現は、ネットワーク内のすべてのノードの認証データから導出された、ブルームフィルタとマークル木のルートとのうちの一方を含む。
【００２１】
本発明の第３の態様によって、通信ネットワークで用いる移動通信ノードを提供する。ノードは、ネットワークノードによって証明された、ネットワーク内のすべてのノードの検証データのコンパクト表現を、ネットワークノードから受信するための受信器を備えている。ネットワークノードによって証明された、ネットワーク内のすべてのノードの検証データの、受信されたコンパクト表現を記憶するため、メモリが設けられている。受信器はさらに、広告側ノードからメッセージを受信するように構成されており、そのメッセージは、認証データと、広告側ノードについての認証データから導出された信用性情報とを含んでいる。ネットワーク内のすべてのノードの検証データのコンパクト表現と、受信された信用性情報と、広告側ノードについての受信された認証データと、を用いてメッセージの真正性を検証するプロセッサが設けられている。
【００２２】
移動通信ノードは、任意で、時計を備えており、ここで、プロセッサは、信用性情報を、マークル木の葉から導出された情報と比較することによって検証するように構成され、その葉は、認証データと、時計から取得された時刻から導出された情報とから導出され、プロセッサは、さらに、ネットワーク内のすべてのノードの検証データの第２のコンパクト表現を導出するように構成されていて、すべてのノードの検証データの第２のコンパクト表現が、ネットワーク内のすべてのノードの検証データの記憶されたコンパクト表現と調和するかどうかを検証する。
【００２３】
本発明の第４の態様によって、通信ネットワークで用いるネットワークノードを提供する。ネットワークノードは、通信ネットワークに関連付けられた複数のノードの各々について、個々のノード特有の認証データを導出すると共に、ネットワーク内のすべてのノードの検証データの証明付きコンパクト表現を導出するためのプロセッサを備えている。また、個々のノード特有の認証データと、ネットワーク内のすべてのノードの検証データの証明付きコンパクト表現とを複数のノードの各々に送信するため、送信器も設けられている。
【００２４】
本発明の第５の態様によって、移動通信ノード上で実行された場合に移動通信ノードを本発明の第２または第３の態様のいずれかの中で上述した移動通信ノードとして動作させるようなコンピュータ可読コードを含む、コンピュータプログラムを提供する。
【００２５】
本発明の第６の態様によって、ネットワークノード上で実行された場合にネットワークノードを本発明の第４の態様の中で上述したネットワークノードとして動作させるようなコンピュータ可読コードを含む、コンピュータプログラムを提供する。
【００２６】
本発明の第７の態様によって、コンピュータ可読媒体と、本発明の第５または第６の態様の中で上述したコンピュータプログラムとを含む、コンピュータプログラムプロダクトを提供し、ここで、コンピュータプログラムは、コンピュータ可読媒体上に記憶される。
【図面の簡単な説明】
【００２７】
【図１】例示的なネットワークシナリオをブロック図として略示する図である。
【図２】ハッシュキーで生成されたマークル木を略示する図である。
【図３】本発明の一実施形態によるシグナリングを示すシグナリング図である。
【図４】本発明の第１の実施形態のステップを示すフロー図である。
【図５】本発明の一実施形態による広告側端末をブロック図として略示する図である。
【図６】本発明の一実施形態による受信側端末をブロック図として略示する図である。
【図７】本発明の一実施形態によるネットワークノードをブロック図として略示する図である。
【発明を実施するための形態】
【００２８】
以下の記述は、ネットワーク内の個々のノードが、（アドホックネットワークを構築するために）ネットワークを介して通信することなく、中央ネットワークノードと、あるいは相互に、通信することができると仮定している。ＬＴＥネットワークを仮定しているが、同様の方法がいかなるタイプの通信ネットワークにおいても用いられうるであろうということは理解されるであろう。ＬＴＥインフラは、ユニキャストおよび／またはマルチキャストチャネル、例えば「ページング」またはセル同報を用いて、いつでもどこでもいかなるアドホック対応ノードにも達することができる。また、個々のノードは、内部時計を有し、かつ、それらはすべて、時刻が同期していると仮定する。この時刻同期は、ウインドウメカニズムが用いられる場合、厳密である必要はない。
【００２９】
或るノードが別のノードとの間でアドホックネットワークを形成することを望む時、そのノードは、広告を送信する。以下のような３つの広告カテゴリが考えられる。
・主にビジネス向けの広告を扱う「パブリック」広告（例えば、公共交通／民間交通など）
・主に特別のノード集合に対するプレゼンスと近接性の公表を扱う「プライベート」広告（例えば、自分と自分の友達との間で）
・社会的および安全性向けの広告を扱う「セミ・パブリック」広告（例えば、ゲーム、医療サービス、社会的サービス、車両用メッセージなど）
【００３０】
ＬＴＥネットワーク２にアタッチしているＵＥ１は、ＬＴＥインフラ、例えばＭＭＥ（モビリティ管理エンティティ）によって生成された「セキュリティパラメータ」セットをセキュアな形で取得し、それらがＵＥ１に対して送信される。この送信についてのセキュリティは、典型的には、既存のＵＥ対ネットワークへのシグナリングプロトコルによって提供されるであろう。第１の実施形態では、セキュリティパラメータは、マークル木を用いて実装される。これらのパラメータは、発信広告を認証するのに用いられるパラメータセットと、着信広告を検証するのに用いられる（単一の）パラメータとの２つのカテゴリに分類することができる。これは、ＬＴＥインフラが、例えばＤｏＳ攻撃のような、何らかの悪意のある動作を、送信者まで遡って追跡し、いずれかの必要な行動を取る（例えば、そのユーザをネットワークから締め出す）ことができることを意味する。
【００３１】
セキュリティパラメータのコンパクト表現が、ネットワーク内の個々のＵＥに対して送信される。本発明の第１の実施形態によると、コンパクト表現は、マークル木に基づいており、本発明の第２の実施形態によると、コンパクト表現は、ブルームフィルタに基づいている。ＵＥがいずれかの他のＵＥからの広告を検証する必要がありうるため、このコンパクト表現が必要となる。ネットワーク内には他のＵＥが何千も存在することがあり、そのため、コンパクトでない表現を送信するという正攻法のやり方を行えば、実行不可能なほど多くの帯域幅を消費するであろう。
【００３２】
プライベートのカテゴリではそれ自身のプライバシとセキュリティとが必須であるため、以下に記述する方法は、主に、広告のセミ・パブリックのカテゴリに関する。しかし、個々のパブリック広告についてインフラにクエリする必要性をなくすことによってＬＴＥ帯域幅の利用を著しく最適化しうることから、この方法は、パブリック広告のカテゴリに適用されてもよい。
【００３３】
下記のような、アドホックネットワークにおいて信頼関係を確立する方法は、「初期の」信用性メカニズムとしての動作であると考えられており、鍵交換プロトコルに対する前触れであることが意図されている。広告側ＵＥと応答側ＵＥとの間の迅速な信用性の発見を可能にすることによって、両方のノードが、普通ならペアリング手順の最中に開始されるかもしれない、見込まれるＤｏＳ攻撃から確実に保護される。
【００３４】
ＵＥ同士が対話することを決めると、典型的には、発見（ディスカバリー）に続いて、例えばＤｉｆｆｉｅ−Ｈｅｌｌｍａｎに基づく、ペアを成す鍵の確立も行われるであろう。しかしながら、これは本発明の範囲外である。ただし、本発明は、送信されたＤｉｆｆｉｅ−Ｈｅｌｌｍａｎパラメータを認証するのにも適用可能であろうということに留意されたい。
【００３５】
本発明の第１の実施形態をよりよく記述するため、図２を参照しながら、マークル木について以下に説明する。
【００３６】
マークル木とは、ラベル付きの二分木である。葉のラベルは、Ｌ１＝Ｈ（Ｒ１）、Ｌ２＝Ｈ（Ｒ２）、・・・、Ｌｎ＝Ｈ（Ｒｎ）という形をしており、ここでＨは（例えばＳＨＡ−２５６を用いて、またはＷｈｉｒｌｐｏｏｌハッシュ関数を用いて実装される）（一方通行の）暗号化ハッシュ関数であり、Ｒｊは任意の値であってもよい。内部の頂点のラベルｖは、「子孫」に対するラベルから再帰的に定義され、すなわち、
Ｌａｂｅｌ（ｖ）＝Ｈ（Ｌａｂｅｌ（ｌｅｆｔ（ｖ））||Ｌａｂｅｌ（ｒｉｇｈｔ（ｖ）））
ここで、ｌｅｆｔ（ｖ）とｒｉｇｈｔ（ｖ）とは、ｖの左右の子に対応し、||は、連結を表す。木は、ルートのラベルによって関連付けられ／識別されてもよい。
【００３７】
Ｈのようなハッシュ関数を用いて、単一のメッセージが認証または「署名」されてもよい。ユーザは、メッセージｍおよびＨ（Ｈ（Ｒ）||ｍ）を公開し、ここでＲは何らかのランダムな値である。検証を可能にするため、ユーザはＲを開示する。検証器が、Ｒは、上記の式によるメッセージを使ってハッシュした場合、同じ結果を生じることをチェックする。不利点は、Ｒは開示された瞬間に消費されるため、セキュアな形で署名されるのは、１つのメッセージだけである可能性があることである。
【００３８】
図２の例では、キー０００乃至キー００３からルート値のハッシュ０が生成される。個々のキーの値は、マークル木の１つの葉である。
【００３９】
マークル木によって、複数のメッセージの認証が可能になる。個々の葉は、１つのメッセージの「公開鍵」であって、（木の深さにおける）幾何学級数的な数のメッセージを認証する手段を提供すると考えることができる。マークル木を用いる場合、ユーザは、葉を示すだけではなく、葉からルートまでのパスに沿った「パスの外の」兄弟姉妹たちも示さなければならないことに留意されたい。（木の大きさにおける）対数的な数の兄弟姉妹たちが存在する。
【００４０】
本発明の第２の実施形態をより良く記述するため、ブルームフィルタは、所定の長さｍのビットベクトルであり、それと共に、ｋ個のハッシュ関数ｈ１、ｈ２、・・・、ｈｋの集合が、集合{１、２、・・・、ｍ}にマッピングされる。データ項目ｘをブルームフィルタに挿入する場合、ビットベクトルのビット位置ｈ１（ｘ）、ｈ２（ｘ）、・・・ｈｋ（ｘ）はすべて「１」に設定される。逆に、或るデータ項目の候補ｙが、ブルームフィルタによって符号化されたデータ集合のメンバであるかどうか判定するため、ビット位置ｈ１（ｙ）、ｈ２（ｙ）、・・・ｈｋ（ｙ）がチェックされ、そして、これらのビット位置がすべて「１」である場合、ｙはデータ集合のメンバであると仮定することができる。結果として、ビット位置は、ｙとは異なる何らかの他の要素によって「１」に設定されうるのだから、ブルームフィルタは、いわゆる「偽陽性」を与えうる。しかし、偽陽性の割合は、ｍとｋの適切な値を選択することによって、コントロールすることができる。例えば、ブルームフィルタのサイズが少なくともｍ＝１．４４×ｔ×Ｎであるならば、偽陽性率２^（−ｔ）を有するブルームフィルタを作成することができ、ここでＮは、挿入される要素の数である。
【００４１】
次に本発明の第１の実施形態について記述するが、ＭＭＥは、基本時間枠を基準にして複数の時間枠を決める。例えば、基本時間枠が真夜中である場合に最小時間枠が６秒であると仮定すると、複数の時間枠のうちの個々の時間枠は、真夜中＋６秒、真夜中＋１２秒、真夜中＋１８秒というようになる。個々の時間枠を用いて、ノードが広告を送信してもよい。個々の広告に、認証データと信用性情報と呼ばれる２つの特別パラメータが割り当てられ、それらは少なくとも部分的には、広告側ノードの中に事前に記憶されている。従って、２４時間の時間枠は、上記の精度を持つ１４４００個の異なる信用性パラメータを必要とすることになる。パラメータの数は、ｎと呼ばれる（この例では、ｎ＝１４４００がデフォルトである）。
【００４２】
またＭＭＥは、サービス提供されるユーザの最大数Ｎも判定する。そのような個々のユーザｕ＝１、２、・・・Ｎと、個々の時間枠ｊ＝１、２、・・・ｎとについて、ネットワークは、対応する時間枠Ｔｊについての認証データとして機能する（疑似）ランダム値Ｓｕｊを割り振る。
【００４３】
ＭＭＥは、マークル木を算出し、それを個々の正当なユーザ／ＵＥについて（例えば、ネットワークアタッチの際に）証明する。マークル木の個々の葉は、１４４００個の時間枠の各々を使ってそのＵＥに関連するランダムな認証データＳｕｊをハッシュすることによって、演算される。これは、ｌｅａｆ（ｊ）すなわちＬ（ｊ）＝Ｆｉｒｓｔ[１２８，Ｈ（Ｓｕｊ|Ｔｊ）]を意味し、ここでＳｕｊは、Ｔｊに関連付けられた上記の秘密であって、ネットワークによって選択されたものであり、かつ、ユーザにも知られており、そして、Ｔｊは、特定の時間枠に相当する。話を簡単にするために、すべてのＴｊは同じ持続時間を有すると仮定するが、異なる持続時間のＴｊを用いることも可能である。これは、所与の時間枠の中により多くのＴｊを許容するような、ネットワーク内のピーク時のトラヒックを考慮に入れてもよい。
【００４４】
ＬＴＥネットワークのような典型的な事例では、個々のＳｕｊは、例えばＳｕｊ＝Ｈ（Ｓｕ，ｊ）によってネットワークとＵＥとの間で共有されるキーであるＳｕから生成されてもよいだろうということに留意されたい。次いでＳｕは、ＵＥとネットワークとに限って利用可能であるようになされなければならず、他のＵＥに対して開示されてはならない。
【００４５】
個々のＵＥに特有で、かつ、その後の２４時間をカバーするマークル木が、ＬＴＥによって生成され、記憶される。ＬＴＥネットワークは、それゆえ、ユーザｕのマークル木のルートＲ（ｕ）を（ユーザが接続する前に）事前に演算する。これが、すべてのＮ個のユーザについて繰り返される。留意すべきことだが、木全体ではなく、ＳｕとＴ０とｎとＲ（ｕ）とを記憶するだけでよく、必要に応じて、Ｔ０とｎとＳｕとから、いずれかの内部頂点を再構築することができる。これには、Ｏ（Ｎ＊ｎ）のハッシュ演算が含まれる。
【００４６】
いずれかの時点で、ＵＥ１が、ＬＴＥによる認証と許可とを介してアドホック・ソーシャル・エコシステムに接続し、その間に、ネットワークから認証データＳｕｊ（またはＳｕ）およびｎをセキュアな形で受信する。ＵＥ１は、自分自身のハッシュ木の主要パラメータを作成することができるが、それは、ＵＥ１とＬＴＥネットワークとが、いかなる特定の葉も交換する必要がないことを意味し、なぜなら、ＵＥ１とＬＴＥネットワークとがいずれも、必要な場合にはいつでもそれらを、Ｔ１とｎと共有するＳｕと一方通行のハッシュＨとを用いて生成することができるからである。また、ＵＥ１は、少なくとも現在接続されているすべてのユーザの集合を表す１枚のシステム証明書を受信する。（また、証明書は、下記のように、未接続のユーザを表すこともできる。）このシステム証明書は、以下に説明する、すべてのユーザのマークル木のルートのコンパクトで検証可能な表現である。
【００４７】
ＵＥ１が、ネットワーク２をさらに含めることなく、別のＵＥ３とアドホックネットワークを形成することを望む場合、ＵＥ１は、認証データＳｕｊと、トランザクションの現行の時間間隔Ｔｊとに関連付けられた、対応する葉Ｌｊに基づく信用性情報とを含む広告を送信する。例えば、Ｌｊはメッセージ認証コード（ＭＡＣ）を演算するためのキー、例えばハッシュ（Ｌｊ，メッセージ）として用いられてもよい。
【００４８】
Ｓｕｊ（および場合によっては、必要に応じて兄弟姉妹）を送信することによって、受信側ＵＥ３は、ルートを演算し、その有効性を、ＵＥ３がネットワークから以前に受信していたシステム証明書のローカルなコピーを介してチェックすることができる。受信器は、葉が木の一部であるかどうかをチェックする必要はない。代わりに、パラメータの集合が、有効なパラメータであるルートに至るかどうか、言い換えれば、システム証明書によって証明されているかどうかをチェックする。
【００４９】
システム証明書は、受信側ノードがネットワーク内のいずれかのノードを検証することを可能にすべきである。上記のように、ネットワークに登録されている個々のＵＥに関連するルートを分配することは、それらが非常に多数でありうるという理由から、望ましくない。従ってネットワークは、個々の登録されたＵＥのルートＲ（１）、Ｒ（２）、・・・Ｒ（Ｎ）を入力葉として用いて、第２のマークル木を作成する。システム全体のルートをＲと名づける。ネットワークは、従来の署名メカニズム、例えばＲＳＡ公開鍵暗号化を用いてＲに署名し、それを分配する。個々のユーザｕについて、ネットワークは、「パスの外の」兄弟姉妹を含めてパスの情報をＲ（ｕ）からルートＲへと送信する。ゆえに、ユーザの数をＮ＝２^ｔと仮定すると、個々のユーザは、Ｏ（ｌｏｇ  Ｎ）＝Ｏ（ｔ）の加算値を得る。この集合をＳｉｂ（ｕ）と名付ける。留意すべきことだが、この分配はネットワークから個々のＵＥへのユニキャストであることから、ＲＳＡを用いる代わりに、代替として、前から存在するＬＴＥ（共有）キーを用いてＲおよびこの情報が「署名」されてもよい。
【００５０】
留意されるべきだが、Ｒを構築するためのネットワークの全演算作業は、Ｏ（Ｎ＊（ｎ＋１））ハッシュ関数評価であり、すなわち、すべてのＲ（ｕ）を構築するためのＯ（Ｎ＊ｎ）と、その後それらをＲと結合させるためのＯ（Ｎ）とである。
【００５１】
ワイヤレスアドホックネットワーク内の２つのノード間のその後の隣接者信用性の発見の交換の間、受信側ノードは、例えばＭＭＥのようないかなる中央ネットワークノードとも通信することなく、広告側ノードによって送信された認証データおよび信用性情報を検査しなければならない。広告を認証するため、広告側ノードＵＥ１は、自分の木の中の（ＵＥ１の内部時計から取得された時間枠Ｔｊに関連する）１つの葉と、それに対応するルートＲ（ｕ）に至るパスの外の情報とを、すなわち、ｄ＝ｌｏｇ  ｎである場合のＯ（ｄ）の値を、リリースする。また、広告側ユーザも、Ｓｉｂ（ｕ）、すなわちＯ（ｔ）の値を送信する。「署名」は今、サイズＯ（ｄ＋ｔ）を有する。留意すべきことだが、Ｓｉｂ（ｕ）は、記憶スペースに余裕がある場合、今後の利用のためにキャッシュされてもよい。
【００５２】
また、受信側ノードＵＥ３が広告を検証するために行わなければならないハッシュ演算の回数も、Ｏ（ｄ＋ｔ）である。これは、最初に再構築Ｒ（ｕ）を再構築し、次いで、Ｒ（ｕ）とＳｉｂ（ｕ）とからＲを再構築することによって行われる。
【００５３】
留意されるべきだが、受信側ノードは、広告メッセージに応答する場合、認証データと信用性情報とを含めることによって、ＵＥ１とＵＥ３とがいずれも正当であることを相互に確信できるようにするべきである。
【００５４】
２つのノードＵＥ１とＵＥ３との間の鍵交換プロトコルは、隣接者信用性の発見プロトコルの間に信用性が表示されることを包含すべきであるが、ノードの身元を決して開示すべきではない。このために、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ交換を行うのに必要な最初の２つのメッセージは、マルチキャストモードで送信されてもよいだろうし、そして、２つのノード間で交換される「信用性パラメータ」からかまたは隣接者信用性の発見交換の間に生成される、追加のパラメータを搬送するべきである。
【００５５】
図３に関して、以下のステップで本発明の概要を記述するが、以下の番号は図の番号に対応している。
【００５６】
Ｓ１およびＳ２．ＭＭＥ２が、個々のノードに関係する認証データＳｕ（またはＳｕｊ）および署名されたシステム証明書を、（ＵＥ１とＵＥ３とを含めて）ネットワーク内のすべてのノードに対して送信する。これは典型的には、個々のノードがネットワークに接続する際に行われる。
【００５７】
Ｓ３．ＵＥ１が、別のノードとの間でアドホックネットワークをセットアップすることを望む場合、現在時刻Ｔｊに関連するそのマークル木の葉Ｌｊと、その内部時計から判定された、対応する認証データＳｕｊとを含む信用性情報を判定する。信用性情報と認証データとは、広告ｍを認証するために用いられる。
【００５８】
Ｓ４．ＵＥ１が、信用性情報と認証データとを、広告の中でＵＥ３に対して送信する。それゆえ、送信された情報は、「メッセージ」、Ｈ（Ｌｊ、「メッセージ」）、Ｓｕｊ（すなわち、広告自体と、ＭＡＣおよび認証データを含む信用性情報）を含んでいる。
【００５９】
Ｓ５．ＵＥ３が、Ｌｊ＝Ｈ（Ｓｕｊ|Ｔｊ）を演算し、Ｈ（Ｌｊ，「メッセージ」）を検証し、次いでＵＥ１についてのマークル木のルートを判定し、次いでＵＥ１についてのルートとＳｉｂ（ｕ）とからルートＲが導出されうることを判定することによって、広告を検証する。
【００６０】
図４は、第１の特定の実施形態を詳細に示す図であり、以下の番号は、図４の番号に対応している。
【００６１】
Ｓ６．ＵＥ１が、その認証情報（Ｓｕｊ）と、ネットワーク内のすべてのノードの認証データから導出された証明付きマークル木とを受信する。
【００６２】
Ｓ７．ＵＥ１が、その認証データ（Ｓｕｊ）と、その内部時計から間接的に取得された時刻（Ｔｊ）とを用いて、マークル木の１つの葉（Ｌｊ）を導出する。導出された葉Ｌｊを用いて、信用性情報の残余部分Ｈ（Ｌｊ，「メッセージ」）を導出する。
【００６３】
Ｓ８．ＵＥ１が、ＵＥ２に対して、信用性情報を含むメッセージを送信する。
【００６４】
Ｓ９．ＵＥ３が、認証データと、自分自身の内部時計から間接的に取得された基準時間とを用いて、マークル木の１つの葉を導出する。理解されるであろうが、ＵＥ１とＵＥ３との内部時計は、合理的に緊密に同期されるべきであるが、受信されたメッセージをキャッシュするＵＥ３についてはいくらかの差は許容されてもよい。信用性情報の残余部分Ｈ（Ｌｊ，「メッセージ」）も検証される。
【００６５】
Ｓ１０．ＵＥ３が、導出された葉を用いて、第１のノードについてのマークル木のルートを導出する。
【００６６】
Ｓ１１．ＵＥ３が、ネットワーク内のすべてのノードの検証データから導出された証明付きマークル木のルートは、自分が導出した第１のノードについてのマークル木のルートから導出されうるかどうかを判定する。もしそうなら、メッセージが検証される。
【００６７】
以下の例は、ｍビットの出力、例えばｍ＝１２８、を生じるハッシュ関数Ｈが用いられることを仮定する。システムは、Ｎ人のユーザを有しており、ｎの時間枠が必要である（例えば、ｎ＝１４４００）。
【００６８】
システムの初期化
１．ネットワークノード２（例えばＭＭＥ）が、現行の時間枠Ｔ１（またはその直前）でパラメータＮおよびｎを決める。
【００６９】
２．個々のｕ＝１，２，・・・Ｎ，について、ネットワークノード２が、ランダムなＳｕ（または疑似ランダムＳｕｊ）を選び、ＳｕおよびＴ１，Ｔ２，・・・ＴｎからＲ（ｕ）を構築し、ＳｕとＲ（ｕ）とを記憶する。
【００７０】
３．Ｒ（１），Ｒ（２），・・・Ｒ（Ｎ）からＲが判定されて、記憶される。
【００７１】
４．ネットワークがＲに署名し、それをネットワーク内のすべてのノードに対して送信する。
【００７２】
参加
これは、ｕで示す新たなＵＥがアタッチする場合に実行される。
【００７３】
１．通常のＬＴＥアクセスセキュリティが行われる。
【００７４】
２．ネットワークが、Ｔ１、ｎ、ＳｕおよびＲ（ｕ）を、ＬＴＥアクセスセキュリティによって保護されているＵＥに対して送信する（約２ｍビット）。あるいは、ＵＥが、Ｓｕを選択して、ネットワークに対して送信してもよい。
【００７５】
３．（ネットワークは信用できると仮定されているため）選択が任意の実施形態で、ＵＥが、Ｒ（ｕ）が適切に作成されていることを検証するため「サンプル」を採取してもよく、すなわち、何らかの（ランダムな）パスを葉からルートまで評価してもよい。
【００７６】
４．ネットワークが、Ｓｉｂ（ｕ）、すなわち、ＲにおけるＲ（ｕ）のＯ（ｌｏｇ  Ｎ）のパスの外の兄弟姉妹を、ＬＴＥアクセスセキュリティによって保護されているｕに対して送信する。
【００７７】
オプションの実施形態で、ＵＥが、Ｒが正確であることを検証する（Ｏ（ｌｏｇ  Ｎ）のハッシュ演算を必要とする）。
【００７８】
広告を認証する
１．ＵＥ１が、Ｓｕｊと現行の時間枠Ｔｊとに対応する、正確な葉Ｌｊを導出する。
【００７９】
２．ＵＥ１が、Ｌｊと、認証データＳｕｊと、ＬｊのＯ（ｌｏｇ  ｎ）のパスの外の兄弟姉妹およびＲ（ｕ）のＯ（ｌｏｇ  Ｎ）のパスの外の兄弟姉妹とによって認証された（Ｌｊによる認証は、ＬｊをＨについてのキーとして利用する。従ってＨの演算は１度だけでよい）広告を、ＵＥ３に対して行う。ステップ２の代替としては、ＵＥは、メッセージおよびＭＡＣだけを送信する。次いで、広告を受信するノードＵＥ３は、ＵＥ１に、認証データと兄弟姉妹とを要求する必要がある。いずれの場合でも、他の誰よりも前に、送信者からの通信全体が、（第１の）広告はＯ（ｍ＊（１＋ｌｏｇ  ｎ＋ｌｏｇ  Ｎ））であることを検証することができる（次のセクションを参照のこと）。
【００８０】
広告を検証する
１．ＵＥ３が、ＵＥ１から（第１の）広告を受信し、（ＵＥ１に対応する）認証データと兄弟姉妹とを、上記で論じたように、広告の一部としてかまたはＵＥがそれらを要求することによって、取得する。
【００８１】
２．ＵＥ３が、ＭＡＣが正確であり、かつ、Ｌｊおよび兄弟姉妹がルートＲ（ｕ）に至るということをチェックするが、ここではＨのＯ（１＋ｌｏｇ  Ｎ）評価が用いられる。
【００８２】
３．正確であるならば、ＵＥ３が、Ｒ（ｕ）および（現行の）システム全体の木Ｒの兄弟姉妹が、Ｒのルートに至ることを検証し、すなわち、ＨのＯ（ｌｏｇ  Ｎ）評価を行う。
【００８３】
ステップ２の後で、受信側ＵＥは、その後のメッセージがＲ（ｕ）およびＲの生存時間の間に受信される場合にはステップ１および２だけ行われればよいように、Ｒ（ｕ）をキャッシュしてもよい。
【００８４】
第２の特定の実施形態によると、個々のユーザｕは、そのルートＲ（ｕ）によって識別されるマークル木を有する。原理は、他者がルートまでのパスを演算することを可能にするためにユーザが葉と兄弟姉妹とを示し、それによって広告を認証するという点で、第１の実施形態と同じである。第２の実施形態の違いは、すべてのユーザの公開鍵の「コンパクト表現」が取得されるやり方にある。第１の特定の実施形態では、このためのもう１つのマークル木が用いられたが、他方、第２の特定の実施形態では、ブルームフィルタが用いられる。
【００８５】
個々のユーザのマークル木のルート{Ｒ（１），Ｒ（２），Ｒ（ｕ），・・・，Ｒ（Ｎ）}が、ブルームフィルタの中に挿入される。ＬＴＥネットワークが、例えばＲＳＡを用いて、ブルームフィルタに署名する。ユーザが広告を認証することを望む場合には、ユーザｕの（候補）ルートＲ（ｕ）を計算した後、検証側ユーザが、Ｒ（ｕ）は署名されたシステム全体のブルームフィルタのメンバであるかどうかをチェックする。
【００８６】
ブルームフィルタの利用に際しては、利点と不利点とがいくつかある。第１に、ＬＴＥネットワークがシステムパラメータを初期化する場合、未接続のユーザについてマークル木を生成する必要はない。これは、後になって任意の要素がブルームフィルタの中に挿入されることがあるからである。新たなユーザが追加されると、ネットワークノードは、ブルームフィルタを更新し、それに再署名する。システム全体のマークル木は、ハッシュ関数Ｈの「一方通行」の性質のため、この特性を有しておらず、葉は、「後で」追加されることはできず、木は、最初に葉からルートまで生成されなければならない。また、関連する木の深さは、システム内のユーザの総数に依存するのではなく、個々のユーザによって行われる広告の数だけに依存するため、ブルームフィルタを用いた広告の検証は、より効率的である。言い換えると、マークル木の実施形態は、ブルームフィルタを用いる場合には、深度の合計がＯ（ｌｏｇ  ｎ）よりむしろＯ（ｌｏｇ  ｎ＋ｌｏｇ  Ｎ）である木を増加させるであろう。ユーザｕのマークル木のルートが与えられている場合、ブルームフィルタをチェックすることは、本質的に瞬時に行われる。特に、ブルームフィルタがｋ個のハッシュ関数を有すると仮定すると、ブルームフィルタをチェックすることは、ｋ回のハッシュ演算に対応する。
【００８７】
ブルームフィルタによる手法の欠点は、上述したブルームフィルタの偽陽性率である。ルートＲ（ｕ）がブルームフィルタに挿入されない場合でさえ、そのように見えることもありうる。しかし、これは、ＢＦパラメータを選ぶことによってコントロールすることができる。
【００８８】
ブルームフィルタを用いる下記の例は、第１の特定の実施形態を記述する際に行ったのと同じ仮定を行う。
【００８９】
システムの初期化
１．ネットワークノード２が、パラメータＮを決める。現在の時間枠はＴ１（またはその直前）であると仮定する。システムが、（Ｎおよび所望の偽陽性率に基づいて）適切なサイズかつ適切なｋを持つブルームフィルタを選ぶ。ブルームフィルタは空であるように初期化される。
【００９０】
２．ネットワークがブルームフィルタに署名し、それをネットワーク内のすべてのノードに対して送信し始める（例えば同報する）。
【００９１】
参加
これは、ｕで示す新たなＵＥが接続する場合に実行される。
１．通常のＬＴＥアクセスセキュリティが行われる。
【００９２】
２．ＵＥ１が、ｎ個の葉を選び、マークル木Ｒ（ｕ）を形成し、それが、ＬＴＥアクセスセキュリティによって保護されているネットワークノード２に対して送信される。（あるいは、ネットワークノード２が、上述したようにＳｕ／Ｓｕｊの値に基づいて、木／葉を選ぶこともできる。）
【００９３】
３．任意で、木を生成していない当事者が、Ｒ（ｕ）が適切に作成されていることを検証するためサンプルを採取してもよく、すなわち、何らかの（ランダムな）パスを葉からルートまで評価してもよい。
【００９４】
４．ネットワークが、Ｒ（ｕ）をブルームフィルタに追加し、ブルームフィルタに再署名し、そして、新たな値を同報し始める。
【００９５】
広告を認証する
１．ＵＥ１が、現在の時間枠Ｔｊに対応する、正確な認証データＳｕｊ（それゆえ、対応する葉Ｌｊ）を見つける。
【００９６】
２．ＵＥ１が、Ｌｊと、認証データと、ＬｉのＯ（ｌｏｇ  ｎ）のパスの外の兄弟姉妹とによって認証された（Ｌｊによる認証は、例えばＬｊをＨについてのキーとして利用する。従ってＨの演算は１度だけでよい）広告を行う。
【００９７】
ステップ２の代替として、ＵＥは、メッセージおよびＭＡＣだけを送信する。次いで、広告を受信するユーザは、認証データと兄弟姉妹とを要求する必要がある。いずれの場合でも、他の誰よりも前に、送信者からの通信全体が、（第１の）広告はＯ（ｍ＊（１＋ｌｏｇ  ｎ＋ｌｏｇ  Ｎ））であることを検証することができる（以下を参照のこと）。
【００９８】
広告を検証する
１．ＵＥ１からの（第１の）広告を受信するＵＥ３は、最初に、認証データと兄弟姉妹とを、上記で論じたように、広告の一部としてかまたはＵＥ１がそれらを要求することによって、取得する必要がある。ＵＥ３は、最近同報され（署名され）たブルームフィルタのコピーを有すると仮定する。
【００９９】
２．受信側ＵＥ３は、ルートＲ（ｕ）を導出し、そして、ＭＡＣが正確であり、かつ、Ｌｊおよび兄弟姉妹がルートＲ（ｕ）に至るということをチェックした後、Ｒ（ｕ）が、同報されたブルームフィルタの中にあることをチェックし、すなわち、ＨのＯ（１＋ｌｏｇ  Ｎ）評価を行う。
【０１００】
２の後で、受信側ＵＥは、その後のメッセージがＲ（ｕ）およびＲの生存時間の間に送信される場合にはステップ１および２だけ行われればよいように、Ｒ（ｕ）をキャッシュしてもよい。
【０１０１】
次に図５を参照するが、ここでは広告メッセージを送信するＵＥ１のブロック図を略示する。ＵＥ１は、その認証情報と証明付きマークル木（または、第２の実施形態が用いられる場合には、ブルームフィルタ。上記のブルームフィルタが用いられうるだろうということを当業者であれば理解するであろうが、本記述では、マークル木について述べよう。）を受信するための受信器５を備えている。認証データと基準時間とを用いてＵＥ１のマークル木の１つの葉を導出し、そして、その葉から信用性情報を導出するため、プロセッサ６が設けられている。時間は、直接的または間接的に時計８から取得される。信用性情報と認証データとをＵＥ３に対して送信するため、送信器７が設けられている。グループ鍵を記憶するため、メモリ９が設けられており、その場合、プロセッサ６は、メッセージの少なくとも一部を、それをＵＥ３に対して送信する前に、（第３の特定の実施形態の中で以下に述べるように）グループ鍵を用いて暗号化するように構成されている。また、メモリ９は、ＵＥ１を上記のように動作させるコンピュータプログラム１０を記憶するために用いられてもよい。
【０１０２】
図６は、ブロック図の中に、例えばＵＥ３のような受信側ノードを略示する図である。ＵＥ３は、証明付きマークル木を受信するための受信器１１を備えている。これは、メモリ１２の中に記憶される。また、受信器１１は、ＵＥ１から、認証データと導出された信用性情報とを含むメッセージを受信するように構成されている。証明付きマークル木と、受信された認証データおよび信用性情報とを用いてメッセージの真正性を検証するために、プロセッサ１３が設けられている。また、プロセッサ１３が上記のように信用性情報を検証できるようにするため、時計１４が設けられている。また、ＵＥ３を上記のように動作させるコンピュータプログラム１５を記憶するために、メモリ１２が用いられてもよい。
【０１０３】
図７は、ブロック図の中に例えばＭＭＥのようなネットワークノード２を略示する図である。ＭＭＥは、ネットワーク内の個々のノードに関連付けられた認証データからマークル木（またはブルームフィルタ）を導出して証明するためのプロセッサ１６を備えている。証明付きマークル木（またはブルームフィルタ）を、個々のノード特有の認証データと共に、ネットワーク内の複数のノードの各々に対して送信するための送信器１７が設けられている。また、データと、ＭＭＥを上記のように動作させるコンピュータプログラム１９とを記憶するために、メモリ１８が設けられている。
【０１０４】
以下の記述は、２つの実施形態の利点と不利点との分析を提供する。
【０１０５】
セキュリティの観点から、２つの「攻撃」を考慮しなければならない。
【０１０６】
１．「ニセモノの」ユーザを作成する確率
２．正当なユーザに成り代わった「ニセモノ」の広告の確率
いずれの実施形態においても、攻撃２の確率は、ユーザ毎のマークル木で用いられるハッシュ関数のサイズによって決まり、例えばｔ＝１２８または２５６のようなｔビットのハッシュ関数を用いる場合、例えば２^（−ｔ）のように、非常に小さくすることができる。
【０１０７】
しかし、攻撃１の確率は、コンパクト表現用にマークル木またはブルームフィルタが用いられるかどうかに依存する。
【０１０８】
マークル木を用いる場合、確率は、ハッシュ関数のサイズ、すなわちｔにも依存する。従って、マークル木を用いる場合、攻撃１と２とが同じ（低い）確率を有することを保証することは容易である。
【０１０９】
しかし、ブルームフィルタを用いる場合、攻撃１の確率は、ブルームフィルタの偽陽性率と同じである。上記のように、これを２^（−ｔ）まで低下させるには、ブルームフィルタは、ｍ＝１．４４＊ｔ＊Ｎのサイズを有しなければならず、この場合、Ｎはユーザの数である。留意すべきだが、これは、単一のシステム全体のルートについてｔビットしか必要でないマークル木の実施形態より悪い。確かに、このｍの値は、すべてのユーザの個別のマークル木のルートをただ連結しただけの「些細な」解決策より、実際に４４％大きくなっているのだが、これは「コンパクト」表現についてはサイズｔ＊Ｎに達するであろう。２^（−ｔ／１．４４）という偽陽性率を犠牲にすれば、この些細な解決策より小さいブルームフィルタが達成されうるであろう。例えば、ｔ＝１２８の場合、偽陽性率は、およそ２^（−８８）であろう。一般に、ささいな解決策に比べてｃ倍の「圧縮」を達成するには、２^（−ｔ／（１．４４＊ｃ））の偽陽性率を容認する必要があるであろう。
【０１１０】
ブルームフィルタを用いる場合に攻撃１の確率の上昇を容認する必要性があるにもかかわらず、それでもやはりブルームフィルタは、検証の複雑性がユーザの数Ｎに依存しないという点で有利であり、他方、マークル木だけを用いた場合、検証の複雑性はＮと共に対数的に増加する。また、当初の広告の認証に続く第２の（強力な、相互の）ユーザ認証段階によって補完されるならば、偽陽性率の上昇も容認されうる。
【０１１１】
最初の２つの実施形態の中で記述したように、ユーザは自分のパラメータ（例えば、ルートＲ（ｕ））を示すことを介して追跡されることがあるため、システムは完全に秘密であるとはいえない。ユーザのアイデンティティは知られないままであるが、このタイプの追跡は望ましくないであろう。
【０１１２】
第３の特定の実施形態によって、これは第１および第２の特定の実施形態のいずれかと互換性があるのだが、プライバシを向上させるため、共有される秘密鍵が、「友達グループ」の中のすべてのユーザの間に導入されてもよい。この鍵は、ＫＢと名付けられており、ネットワークノード２によって選ばれて、ユーザが接続する際にユーザに通信されてもよい。ＬＴＥネットワークノード２は、ユーザがどのグループに属するかを知っていると仮定する。
【０１１３】
ボブが広告を行う場合、すべてのものがＫＢを用いて暗号化される。グループのメンバだけが解読できるのだが、留意されるべきだが、彼らは、ボブの木を再構築することを試行する前に、広告が彼らを対象としたものだったとは確信できない。従って、ボブは、自分の木のルートＲ（ｕ）を暗号化するだけでなく、「メッセージはこの友達グループを対象としていると言う（暗号化されていない）テキストによって、それに「プレフィックス」を付ける。グループの個々のメンバは、メッセージが彼らを対象にしているかどうか、そして、木を再構築するために何らかのポイントがあるかどうかをチェックするのに、メッセージの最初の部分だけを解読すればよい。
【０１１４】
理解されるであろうが、第２の実施形態と共に第３の実施形態を用いる場合、ｋを増やす代わりに、複数のブルームフィルタを使ってもよいだろう。この場合、個々の友達グループは、（署名された）ブルームフィルタの形で証明書を有するが、それは、その具体的な友達グループのマークル木だけを含んでいる。
【０１１５】
当業者には理解されるであろうが、本発明の範囲から逸脱することなく、上記の実施形態に対して各種の修正形態が行われうる。特に、本発明は、いかなるタイプの通信ネットワークに適用されてもよい。さらに、理解されるであろうが、上記の記述は、第１のノードから送信されたメッセージの真正性を非依存的に検証することを支援するために時計から取得された時間を用いているが、代わりの非依存の変数が用いられてもよい。
【０１１６】
上記の記述においては以下の略語が用いられる。
ＤｏＳ  サービス拒否攻撃（Ｄｅｎｉａｌ−ｏｆ−Ｓｅｒｖｉｃｅ）
ＬＴＥ  （Ｌｏｎｇ  Ｔｅｒｍ  Ｅｖｏｌｕｔｉｏｎ）
ＵＥ  ユーザ装置（Ｕｓｅｒ  Ｅｑｕｉｐｍｅｎｔ）
ＭＭＥ  モビリティ管理エンティティ（Ｍｏｂｉｌｉｔｙ  Ｍａｎａｇｅｍｅｎｔ  Ｅｎｔｉｔｙ）
ＣＡ  認証局（Ｃｅｒｔｉｆｙｉｎｇ  Ａｕｔｈｏｒｉｔｙ）
【図１】
2013520070.tif 000003
【図２】
2013520070.tif 000004
【図３】
2013520070.tif 000005
【図４】
2013520070.tif 000006
【図５】
2013520070.tif 000007
【図６】
2013520070.tif 000008
【図７】
2013520070.tif 000009
【国際調査報告】
2013520070.tif 000010
2013520070.tif 000011
2013520070.tif 000012