JP4809766B2 - 損失を適応制御したデータストリームの認証方法及び装置 - Google Patents

Description

本出願は、２００３年８月１５日に出願された仮出願第６０／４９５，７８７号の利益を主張する。本出願は、参照によりこの仮出願の開示を含む。

本発明は、データストリーム認証に関し、特に、パケット損失を適応制御した認証方式に関する。

多くの場合、データのストリームに認証情報を付加して、該データが特定の送信元からのものであり、途中で変更されなかったことを受信者に保証することが望ましい。例えば、該データがアプリケーションに提供されている場合、該データが故意又は偶然に破損されていないことは、該アプリケーションにとって重要である。

暗号手法には、かかる認証を可能にする２つの従来方法がある。
１．メッセージ認証符号（ＭＡＣ）
２．電子署名（Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ）

ＭＡＣでは、最初の送信元と最終の受信者の両方が、共有秘密鍵を知っていなければならない。送信者は、元データと秘密鍵とを用いた数学的変換を適用し、タグを生成する。そして受信者は、該データとタグと秘密鍵とを用いた同様の変換を適用し、該データの送信元及び保全性を確認することができる。

電子署名では、鍵は、秘密署名鍵と公開検証鍵の２つに分割される。公開検証鍵は、秘密署名鍵を用いて署名されたものを検証するのに使用することができる。鍵は、公開部分から秘密部分を導出できないように分割される。送信者は、元データと秘密署名鍵とを用いた数学的変換を適用し、署名を生成する。そして、受信者は、該データと署名と公開検証鍵とを用いた同様の変換を適用して、送信者の身元とデータの保全性とを確認することができる。

電子署名は、ＭＡＣにはない否認防止特性を有する。すなわち、署名鍵は、非公開であり、署名者が所有していたものであるので、署名者は、文書に署名したことを後に否認することはできない。もちろん、署名の所有者は、秘密署名鍵が敵に盗まれたといつでも主張することはできる。

従来の認証方式では、それらの性質のために、送信元又は中間者がデータを変換することは許容されない。文書が署名後に変換されると、検証段階でそれが示され、うまくいかない。

しかしながら、多くのアプリケーションにとって、特定の種類の変換を許容することは都合がよいだけではなく、時には必要である。例えば、図１にその原理のハイレベルの図式を示したスケーラブルなビデオ符号化方式は、ストリームの部分集合を復号することができ、その品質が復号量に比例するという特性を有する。このような体系では、ビデオをベース層（ｂａｓｅ ｌａｙｅｒ）に符号化後、ゼロ以上の「エンハンスメント（ｅｎｈａｎｃｅｍｅｎｔ）」層に符号化してもよい。ベース層だけでも、該ストリームを見るのに十分である。エンハンスメント層は、全体的な品質を向上するのに使用する。

ところで、資源が制約された環境においては、エンハンスメント層を取り除いてベース層だけを送信しなければならないかもしれない。ストリーム全体が従来の方法で電子署名又は認証されている場合、エンハンスメント層を取り除くことによって、元のタグや署名は無効となる。従って、ストリーム全体を再認証する必要がある。

また、サイマルキャスト（ｓｉｍｕｌｃａｓｔ）状態におけるように、いくつかの異なる品質のストリームをつなぎ合わせなければならないことがある。高品質バージョンのストリームと、中品質バージョンのストリームと、低品質バージョンのストリームとがあることがある。ネットワーク資源が利用可能である場合、高品質のストリームを送信してもよいが、ネットワークの輻輳が増す場合、中又は低品質ストリームに変更しなければならないかもしれない。別の状況では、受信者が移動可能で、１つのネットワーク環境を出て、資源制約が異なる別のネットワーク環境に入ろうとしている場合がある。上記のつなぎ合わせ状態は、信号伝送品質が低く、そうでなければ、例えば３つのデータストリームをひとつの大きい層状ストリームとして見て、３つのフレームのうち２つが放棄されていると考えることによって、信号伝送品質は劣化しているような損失状態の特別なケースと考えることができる。

さらに、別のアプリケーションには、動的広告がある。送信元は、特定のスロットに表示できる多数の広告を含めてもよい。そして、中間者は、これらの選択肢の中からどの広告を表示したいかを選択することができる。例えば、この選択は、中間者が対象聴衆にとって最もよい広告と考えるものに基づいて行うことができる。広告自体は、中間者や別の者によって作成されることができ、元のフォームで又はハッシュして、送信元に提供されることができる。送信元は、ストリームに署名するときにそれらを入れる。

従って、これらの種類の損失を安全な方法で処理できる署名方式が求められている。ここで「安全」とは、最終受信者が、受信したデータが特定の部分が削除されてはいるが、元々有効に署名されたストリームに由来することを、非常に高い確信をもって判定することができることを意味する。さらに、どのブロックを削除するかを適応的・知能的に決定することができる中間者も必要とされている。

このような制御損失認証問題に対する従来の解決法の１つは、各パケットを個別に認証するというものである。この解決法には、２つの大きな欠点がある。第一に、電子署名を使用する場合、パケットごとに相当な費用のかかる計算を行わなければならない。第二に、電子署名及びＭＡＣのいずれの場合でも、認証情報を各パケットに付加しなければならず、ストリームステムの複数の部分を削除して帯域幅制約を満たす努力を考慮すると、実現可能ではないかもしれない。

Ｃ．Ｋ．Ｗｏｎｇ及びＳ．Ｓ．Ｌａｍ著、「Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅｓ ｆｏｒ Ｆｌｏｗｓ ａｎｄ Ｍｕｌｔｉｃａｓｔｓ」、ＩＥＥＥ／ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎｅｔｗｏｒｋｉｎｇ、７（４）：５０２：５１３、１９９９年８月、において、著者は、各データ要素をハッシュして、その結果生成されたハッシュを、Ｍｅｒｋｌｅ木を使用してダイジェストする解決法を提案している。Ｍｅｒｋｌｅ木の根が認証される。そして、各データ要素と共に、共通ノード（ｃｏ-ｎｏｄｅｓ）を送信することにより、受信者がそれなしに認証できるようにする。Ｗｏｎｇ及びＬａｍは、パケットごとの認証に対処しているので、各パケットは、認証情報を含む。具体的には、

を、Ｍｅｒｋｌｅ木ノードのバイト単位のサイズとし、ｈを、Ｍｅｒｋｌｅ木の高さとすれば、送信される各データ要素は、

バイトを伴わなければならない。従って、この方法は、制御損失認証問題に対処しておらず、帯域効率が低い。

Ｒ．Ｊｏｈｎｓｏｎ、Ｄ．Ｍｏｌｎａｒ、Ｄ．Ｓｏｎｇ及びＤ．Ｗａｇｎｅｒ著、「Ｈｏｍｏｍｏｒｐｈｉｃ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅｓ」、ＲＳＡ ２００２、Ｃｒｙｐｔｏｇｒａｐｈｅｒ’ｓ Ｔｒａｃｋ、において、著者は、編集可能な署名方式を提案している。かかる方式は、データにある特定の変換を行うのを可能にしながらも、受信者が検証できるようにしている。また、係る方式は、署名された文書の部分列を任意に削除できるようにし、検閲用のアプリケーションを有する。ｎ個のメッセージブロックｍ＝ｍ_１，…，ｍ_ｎに署名するものとし、ｎは２の累乗とする。この方式は、最初の秘密鍵ｋで始まり、Ｏ．Ｇｏｌｄｒｅｉｃｈ、Ｓ．Ｇｏｌｄｗａｓｓｅｒ及びＳ．Ｍｉｃａｌｉ著、「Ｈｏｗ ｔｏ Ｃｏｎｓｔｒｕｃｔ Ｒａｎｄｏｍ Ｆｕｎｃｔｉｏｎｓ」、Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ＡＣＭ、ｖｏｌ．３３、Ｎｏ．４、１９８６、２１０〜２１７頁のＧｏｌｄｒｅｉｃｈ、Ｇｏｌｄｗａｓｓｅｒ及びＭｉｃａｌｉ（ＧＧＭ）の構造等の、木のような構造を用いて、秘密鍵ｋを使用してｎ個の鍵ｋ_１，…，ｋ_ｎを生成する。それから、メッセージｍに署名するために、トリプレット（０，ｍ_１，ｋ_１），…，（０，ｍ_ｎ，ｋ_ｎ）をＭｅｒｋｌｅに似た木においてハッシュし、その根ｒに署名して署名ｓを生成する。この木と通常のＭｅｒｋｌｅ木の違いは、内部ハッシュを計算する前に、値１を先頭に付加することである。ｋを知っていれば、誰でもｓを検証することができる。しかしながら、データストリームを検閲するために、ｋの値は、決して公開されない。代わりに、ＧＧＭ木の特定の中間値のみが公開される。これらの値は、検閲されないデータ要素に対応する最終鍵ｋ_ｉを導くのに必要な情報に相当する。非検閲ブロックと、中間ＧＧＭ値と、Ｍｅｒｋｌｅに似た木における共通ノードとにより、署名を検証することができる。しかしながら、上記の準同形署名方式（Ｈｏｍｏｍｏｒｐｈｉｃ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅ）は、ＧＧＭ木を介して、検閲されるデータの機密性を保護するための予防策をとり、検証を可能にするために、全ての非検閲メッセージブロックと、全ての共通ノードと、全てのキーイング情報とを必要とするので、効率的ではない。

従って、認証情報を検証する受信者の能力を弱めることなく、また、検閲されるデータの機密性を要求することなく、ストリームの特定のブロックについての制御された削除を可能にする安全な認証方式が求められている。

上記に鑑み、本発明の目的は、（ＭＡＣを用いた）対称な設定や、（電子署名を用いた）非対称な設定の両方において、適応的データ損失のもとで安全な認証をするための方式であって、送信者、受信者、中間者の計算要件や、それらが通信するチャネルの帯域幅要件に関して効率的である方式を提供することである。

つまり、本発明は、以下の問題に対処している。
１．データチャンクが任意に削除された適応的損失（部分列）認証。
２．いくつかのデータストリームをからみ合わせ、一度に１つのデータチャンクだけを所定のストリームから取り出し、その他のストリームからのデータを削除するサイマルキャスト認証。
３．データチャンク全体を完全に削除することもある適応的損失サイマルキャスト認証。

本発明は、以下の方式を提供する。
１．部分列認証のための線形方式。
２．サイマルキャスト認証のための線形方式。
３．部分列認証のための木方式。
４．サイマルキャスト認証のための木方式。

上記方式は、それぞれ、電子署名及びＭＡＣのいずれかを取り入れてもよい。従って、本発明は、８（＝４×２）つの方式を暗に提供している。

これらの方式は、暗号ハッシュ関数を使用して元ストリームのブロックを処理し、短いダイジェストを生成する。そして、電子署名かＭＡＣを該ダイジェストに適用することによって、認証情報を提供する。受信者は、ストリーム全体を与えられた場合、ダイジェストを再計算し、署名を検証することができる。ストリームの特定部分を削除する必要がある場合、削除者は、受信者が効率的にダイジェストを計算するのを可能にする情報を送信する。この設定において、受信者に提供される情報量は、暗号ハッシュ関数の出力サイズに関連し、他の点では、実際のデータストリームと無関係である。

本発明の第１の特徴は、部分列認証のための線形方式であって、中間者又は送信元が、任意のブロックを（位置に関係なく）削除しても、受信者が、情報を認証できるようにすることができる。この方式は、２層ハッシュチェーンを計算し、このチェーンのいくつかの値を受信者に提供することを含む。この方式は、受信者が認証情報の検証に遅延を生じる必要がないという意味で、受信者にとってオンラインである。この方式を最適化及び一般化したものでは、ｒ個の第１層ハッシュのバンドルごとに１つの第２層ハッシュが計算される。ｒ＝１であれば、この方式は、最初の部分列認証の線形方式である。この方式を改良したものでは、第２層ハッシュを実行する前に、いくつかの第１層ハッシュを１つに集める。その結果、実行する必要のある第２層ハッシュは少なくなる。

本発明の第２の特徴は、サイマルキャスト認証のための線形方式であって、中間者又は送信元が、複数のストリームを提供され、どのストリームを送信するかを任意に切り替えても、受信者が、情報を認証できるようにすることができる。この方式は、多層ハッシュチェーンを計算することと、受信者にこのチェーンにおけるいくつかの値を提供することを含む。この方式は、受信者が認証情報の検証に遅延を生じる必要がないという意味で、受信者にとってオンラインである。

本発明の第３の特徴は、部分列認証のための木方式であって、中間者又は送信元が、任意のブロックを（位置に関係なく）削除しても、受信者が、情報を認証できるようにすることができる。この方式は、ハッシュ木を計算することと、この木におけるいくつかの値を受信者に提供することを含む。削除されたブロックの（１つよりも大きい）ある部分集合が、ハッシュ木の部分木を構成する場合、このハッシュ化方式は、対応する線形方式よりも、帯域幅に関してより効率的である。この方式は、受信者が全てのブロックを待たないと認証情報を検証できないという意味で、受信者にとってオンラインではない。

本発明の第４の特徴は、サイマルキャスト認証のための木方式であって、中間者又は送信元が、複数のストリームを提供され、どのストリームを送信するかを任意に切り替えても、受信者が、情報を認証できるようにすることができる。この方式は、ハッシュ木を計算することと、受信者にこの木におけるいくつかの値を提供することを含む。この方式は、受信者が全てのブロックを待たないと認証情報を検証できないという意味で、受信者にとってオンラインではない。

本発明の全ての特徴において、送信者は、始めに、署名される全てのデータを保有しているものとする。メディアが事前記録されている場合のように、ほとんどの場合、このことは問題ではない。ライブストリームの場合において、本発明は、該ストリームを小さいチャンクに分割し、ここに記載の方式を適用する。当業者であれば、本発明の範囲から逸脱することなく変形及び変更が可能であることを理解するであろう。

本発明において、中間者がどのブロックを削除するかを適応的及び知能的に決定してもよい状況が可能になる。本発明の方式は、ブロックを削除するいかなるモデルにも容易に適応する。さらに、中間者は、暗号キーイングマテリアルを知っている必要がない。さらにまた、送信元が、中間者にいくつかのハッシュ値を提供するならば、中間者は、暗号関連の計算を行う必要を避けることができる。代わりに、中間者は、望ましいブロックを、削除するブロックのハッシュ情報と一緒に転送するだけでよい。

上記の発明方式の全ては、所定のブロックが削除されないという知識を前もって与えられると、そのブロックの第１層ハッシュは実行されないという特性を有する。すなわち、そのブロックだけの第１層ハッシュを、恒等関数（ｈ（ｘ）＝ｘ）に置き換えることができる。

線形方式及び木を用いた方式の両方とも、データのブロック間の相関関係を利用することができる。例えば、木を用いた方式において、所定のブロックの部分集合が、全てが削除されるか、全てが保持されるという性質を有するならば、これらのブロックは、同じ部分木の全ての葉として特定することができる。所定の部分集合の全てのパケットが削除される場合、その根だけを送信すればよい。しかしながら、この概念は、相関関係が確率的であっても適用される。例えば、所定のブロックが削除されることにより別のブロックが削除される可能性が高くなる場合、これらのブロックもひとまとめにされることになる。同様に、線形方式において、所定の一連のフレームが全て保持されるか削除される場合、これらのフレームを単一ブロック単位として処理し、ハッシュすることができる。従って、一連のフレーム全体が削除される場合、単一のハッシュ値を送信するだけでよい。

本発明の方式において、図２の最初の送信者２００は、データストリームを認証する責任がある。図に示すように、各送信者２００は、メモリ２０２と双方向通信するプロセッサ２０１を有する。プロセッサ２０１は、本発明の方式を実施するためのプログラムコードを実行して、データストリームを生成、送信、受信する。メモリ２０２は、暗号鍵とプログラムコード、さらに本方式の実施中に使用する中間結果や他の情報を記憶する。通信ネットワーク２０３が設けられ、それにより送信者は受信者と通信することができる。

図３は、受信者のブロック図を示し、受信者は、本発明の一実施形態による通信ネットワークによって、送信者、サーバ、又は中間者からデータストリームを受信する。本発明のシステムは、多数の受信者を含み、受信者は、受信したデータを検証する。各受信者３００は、メモリ３０２と双方向通信するプロセッサ３０１を有する。プロセッサ３０１は、本発明の方式を実施するためのプログラムコードを実行して、データストリームを生成、送信、受信する。プログラムコードは、当技術で公知の方法によって生成してもよい。メモリ３０２は、暗号鍵、プログラムコード、さらに本方式の実施中に使用する中間結果や他の情報を記憶する。

通信ネットワーク３０３が設けられ、それにより送信者と受信者は通信することができる。通信ネットワークは、例えば、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、及び／又は携帯電話ネットワーク等、各種一般的形態のものでもよい。ネットワークは、有線通信又は無線通信のいずれかを可能にするものであってもよい。

図４は、中間者のブロック図を示す。複数の中間者が存在してもよいし、或いは、送信元と中間者が同一であってもよい。中間者と送信元が同一でない場合、中間者は、暗号キーイングマテリアルを持たなくてもよい。送信者用のデータは、送信者又は受信者へ向かう途中に、図４に示す１つ以上の中間者を通過することがある。中間者は、該データに特定の変換を行うことにしてもよい。各中間者４００は、メモリ４０２と双方向通信するプロセッサ４０１を有する。プロセッサ４０１は、本発明の方式を実施するためのプログラムコードを実行して、データストリームを生成、送信、受信する。メモリ４０２は、暗号鍵を記憶していてもよい。

図５は、送信者５０１と、中間者５０３と、受信者５０５と、通信ネットワーク５０２、５０４とを含む本発明の一実施形態によるシステムのブロック図を示す。図に示すように、送信者５０１は、元データストリームを、署名と、任意のヘルパー情報と共に、通信ネットワーク５０２を介して中間者５０３に送信し、中間者５０３は、縮小したデータストリームを、署名と、関連するヘルパー情報と共に、通信ネットワーク５０４を介して受信者５０５に送信する。

上述の変換には、データの特定部分を削除することが含まれる。中間者は、データストリームを変更する場合、受信者が該ストリームに関連する認証情報を検証するのに必要な情報はどれか、もしあれば、判断する。

Ｍは、長さｂのｎ個のブロックに分割することができるメディアストリームを示す。

Ｈは、入力としてｂビットのペイロードとνビットの初期ベクトルＩＶをとり、通常ν＜ｂである場合にνビットの出力を生成する暗号圧縮関数を示す。これらの暗号圧縮関数は、耐衝突性であり、すなわち、一定のＩＶに関して、Ｈ（ＩＶ，ｍ_１）＝Ｈ（ＩＶ，ｍ_２）となるようなｍ_１≠ｍ_２である２つの入力ｍ_１及びｍ_２を見つけるのは難しい。一定で公知であるＩＶ_０と呼ぶ標準ＩＶが存在する。表記を簡潔にするために、下記の説明では、ＩＶをハッシュ関数における独立変数として明記しないが、暗にそこに存在するものとみなすべきである。

かかる暗号圧縮関数の例は、ＳＨＡ−１やＭＤ５に見られる。ＳＨＡ−１の圧縮関数は、１６０ビットの出力とＩＶサイズを有し、一方、ＭＤ５の圧縮関数は、１２８ビットの値で機能する。双方とも、５１２ビットのペイロードサイズを許容する。このペイロードサイズよりも大きいデータブロックを処理する必要がある場合は、圧縮関数の適用を繰り返す。そのように機能しながらも耐衝突特性を保持する関数は、暗号ハッシュ関数と呼ばれる。簡単にするために、以下において、ペイロード内に収まるデータブロックを処理する場合でも、この用語を用いる。

電子署名を伴う方式については、公開鍵のインフラストラクチャが存在し、送信者は、鍵ペア（Ｐｋ，Ｓｋ）を有するものとする。Ｓｋは、メッセージに電子署名を付加するのに使用することができる送信者の秘密署名鍵であり、Ｐｋは、Ｐｋを使用して発行された署名が本物であるかを確認するのに使用することができる送信者の公開検証鍵である。σ（Ｓｋ，Ｍ）は、署名鍵Ｓｋの下のメッセージＭの電子署名アルゴリズムを示し、ν（Ｐｋ，Ｍ，σ）は、検証アルゴリズムを示す。中間者は、署名鍵も検証鍵も知っている必要はない。ＭＡＣを伴う方式については、最初の送信者Ｓと最終の受信者Ｒの両方が、対称鍵を共に知っており、該対称鍵は、中間者に知られる必要がないものとする。

本発明の方式は、暗号圧縮関数を含む従来の構成を利用するものである。かかる構成の１つは、以下のように暗号圧縮関数から構成される反復ハッシュ関数である。メッセージＭは、長さｂのｎ個のブロックに分割されることができ、Ｈは、ｂビットのペイロード及びνビットの出力の暗号圧縮関数とする。Ｈで定義される反復ハッシュ関数は、値ｘ_ｎである。ここで、

圧縮関数Ｈに衝突を見つけるのが難しいとすると、反復ハッシュに衝突を見つけるのは難しいことになる。通常、メッセージに電子的に署名したい場合、反復ハッシュを該メッセージに適用し、その結果生じる出力に署名する。本発明の方法と、システムと、構成要素とは、同様の構成を含むものであるが、検証を補助するために中間値が提供される。

他の暗号圧縮関数を含む従来の構成は、Ｍｅｒｋｌｅ木である。図６は、８個の葉を有するＭｅｒｋｌｅ木を図式的に示している。各葉は、その下のメッセージのハッシュである。各内部ノードは、その子のハッシュを示している。根が署名される。Ｍは、ｎ個のブロックＭ＝Ｍ_１…Ｍ_ｎに分割できるものとする。簡単にするために、ｎは２の累乗とする。本発明の方式は、２以外の累乗を受け入れることができる。ハッシュ関数Ｈの下のＭに対応するＭｅｒｋｌｅ木は、各ノードが特定の値に対応する２分木である。ｎ個の葉が存在し、各葉ｌ_ｉは、Ｍ_ｉのハッシュ、すなわち、Ｈ（ＩＶ_０，Ｍ_ｉ）を持つ。各内部（葉でない）ノードは、その２つの子の値の連結のハッシュに対応する値を持つ。すなわち、頂点νが、子ν_１及びν_２を持ち、ν_１は、値ｘ_１を持ち、ν_２は、値ｘ_２を持つ場合、νに対応する値は、Ｈ（ＩＶ_０，ｘ_１ ｘ_２）である。

Ｍｅｒｋｌｅ木は、電子署名によく使用され、ダイジェストを形成するメッセージＭに対応する木の根に割り当てられた値が署名される。基礎をなす圧縮又はハッシュ関数が耐衝突性である場合、Ｍｅｒｋｌｅ根の値が同一である２つの異なるメッセージを見つけるのは難しい。

本発明は、また、Ｍｅｒｋｌｅ木における所定の頂点に対する共通ノードという概念を利用している。ある頂点νの共通ノードは、νから根までの経路上にある頂点の直接の兄弟からなる。ある頂点ν及びその共通ノードが与えられると、νから根につながるハッシュ関数の列を計算することができる。
１．部分列認証

本発明の線形部分列認証方式では、メッセージから任意のブロックが削除されても、ストリーム認証が可能である。中間ノードにより送信されたブロックが、元メッセージの真の部分列であれば、受信者は、ストリームを認証することができる。
１．１ 署名

図７は、本発明の一実施形態による基本線形部分列認証方式を示している。メッセージＭが与えられると、署名の生成は、「２つのハッシング層」を使用することを除いて、反復ハッシュと同様のパラダイムに従う。

一実施形態において、メッセージＭ＝Ｍ_１Ｍ_２…Ｍ_ｎが与えられると、本発明は、部分ハッシュ計算値ｈ_１，…ｈ_ｎを、以下のように生成する。

図７に示す方式では、ｈ_１，…，ｈ_ｎを計算する過程で、送信されない補助ハッシュ値ｇ_１，…，ｇ_ｎを計算する。最初の送信者Ｓは、（Ｍ，σ_Ｓｋ（ｈ_ｎ））を送信する。ＩＶ_０の値をＩＶとして使用して、全てのｇ_ｉ値を計算することができる。

或いは、送信者Ｓは、メッセージブロック〈（Ｍ_１，ｈ_ｎ−１，σ_Ｓｋ（ｈ_ｎ）），（Ｍ_２，ｈ_ｎ−２），…（Ｍ_ｎ，ｈ_０）〉と共に、ハッシュ値ｈ_ｉを送信するように決めてもよい。
１．２ 署名の更新

中間ノードが、ｋ個の任意の位置のメッセージブロックを取り除きたい場合、該中間ノードは、Ｍと同一であるが、ｋ個のブロックが削除された結果生じる「メッセージ」Ｍ’を生成する。受信者は、Ｍ’を認証できる必要がある。

受信されたｎ個のブロックのメッセージＭが与えられると、中間ノードは、「新しい」ブロックＭ_１’，…，Ｍ_ｎ’を計算する。メッセージブロックＭ_{ｎ−ｉ＋1}（最後から始めて、ｉ＝１からｉ＝ｎまで）ごとに、中間ノードは、それに対応する補助ハッシュ及び部分ハッシュを、以下のように計算する。

ブロックが転送されるか削除されるかにより、中間ノードは、ブロックＭ_ｉが転送される場合、Ｍ’_{ｎ−ｉ＋1}＝Ｍ_{ｎ−ｉ＋1}を計算し、ブロックＭ_ｉが削除される場合、ｇ_ｉを計算する（式（３））。

ｔを、中間ノードが受信者に送信したい最後のメッセージブロックのインデックスとし、Ｍ_ｔ’＝Ｍ_ｔであり、全てのｌ＞ｔに関し、Ｍ_ｌ’≠Ｍ_ｌとなるようにする。中間ノードは、最終的に、〈Ｍ_１’，…Ｍ_ｎ’σ_Ｓｋ（ｈ_ｎ），ｈ_ｎ−ｔ〉を送信する。

ある標準的な符号化をブロックコンテンツに適用して、「メッセージブロック」と「ハッシュ」とを区別しやすいようにする。当業者は、この符号化を実行するのに多数の方法があることを理解するであろう。

或いは、オンライン検証を可能にするために、中間ノードは、〈（Ｍ_１’，ｈ_ｎ−１，σ_Ｓｋ（ｈ_ｎ）），（Ｍ_２’，ｈ_ｎ−２），…（Ｍ_ｎ’，ｈ_０）〉を送信する。
１．３ 検証

受信者は、以下のように、Ｍ_１’，…，Ｍ_ｋ’及びｈ_ｎ−ｔからｈ_ｎを計算することにより、署名を検証することができる。メッセージブロックＭ’_{ｎ−ｉ＋1}（最後から始めて、ｉ＝１からｉ＝ｎまで）ごとに、受信したブロックが「メッセージブロック」であるか「ハッシュ」であるかによって、受信者は、Ｍ’_{ｎ−ｉ＋１}が「メッセージブロック」である場合、ｈ_ｉ＝Ｈ（ｈ_ｉ−１，Ｈ（ｈ_ｉ−１，Ｍ’_{ｎ−ｉ＋１}））を計算し、Ｍ’_{ｎ−ｉ＋１}が「ハッシュ」である場合、ｈ_ｉ＝Ｈ（ｈ_ｉ−１，Ｍ’_{ｎ−ｉ＋１}））を計算する（式（４））。

受信者は、検証アルゴリズムνを用いて、ｈ_ｎの署名を正規のものと確認することができる。

別のオンライン検証は、以下のように進む。受信者は、関係式（４）を用いて（Ｍ’_１，ｈ_ｎ−１）から部分ハッシュｈ_ｎを計算し、部分ハッシュｈ_ｎの署名を検証する。その後、ｉ＝２，…，ｎについて、（４）を用いて（Ｍ’_ｉ，ｈ_ｎ−ｉ）から部分ハッシュｈ_ｉを計算し、そのように計算されたハッシュが反復ｉ−１で受信したハッシュ値に一致することを確認する。
１．４ セキュリティ

上述のように、基礎をなすハッシュ関数Ｈが耐衝突性であれば、反復ハッシュ構造は耐衝突性である。具体的に、反復構造に衝突が見つかった場合、ある点で内部衝突が存在しており、ハッシュ関数Ｈで衝突を見つけることができることになる。敵が非部分列の偽造（すなわち、元メッセージの部分列を取り出すだけでは得られない１対のメッセージ／署名）を考え出すことができた場合、ハッシュ関数の衝突か、基礎をなす署名方式の偽造のいずれかを証明することができることを示すことができる。従って、署名方式が偽造されにくく、ハッシュ関数が衝突しにくいならば、上記に提示した本方式は安全である。
１．５ パフォーマンス

中間者は、ブロックを削除する場合、削除するブロックのハッシュを計算するだけでよい。この計算は、公開鍵のステップを含まず、かなり効率的である。実際、ＳＨＡ−１のようなアルゴリズムの処理能力は、毎秒数百メガビットである。さらに、中間ノードが、計算に関して資源が限られている場合、送信元は、代替的アプローチに従って、中間のｈ_ｉ値を含むことができる。ＳＨＡ−１の場合、かかる値は、それぞれ２０バイトの長さであり、帯域幅オーバーヘッドは、おそらくかなり小さくなるだろう。

帯域幅使用とバッファリング／計算との間のトレードオフは、選択的にいくつかの中間のｈ_ｉ値を送信することによって可能になる。受信者が、メッセージブロックをｂ個まで記憶することができる場合、中間ノードは、ｂ個のメッセージブロックの後にだけハッシュ値ｈ_ｎ−ｂを送信することができる。認証は、ｈ_ｎ−ｂから始めて、上述のように行うことができる。次に、中間ノードは、第２の「バンドル」（次のｂ個のメッセージブロックとｈ_ｎ−２ｂ）を送信し、該バンドルは、部分ハッシュｈ_ｎ−ｂ，…，ｈ_{ｎ−２ｂ＋１}を再計算し、再計算したハッシュ値ｈ_ｎ−ｂが第１のバンドルで受信したものに一致することを確認することによって、認証される。

本実施形態の計算は、その時々でハッシュ関数に対し１つの入力ブロックだけが必要であるので、ストリーム全体をメモリに記憶する必要はない。

第１の実施形態の方式は、暗号キーイングマテリアルの知識を必要とせずに、任意の数のブロックを削除することを、適応的、知能的に選択することができるという中間者の役割を可能にする。さらに、中間者は、受信者に隣接することができ、損失（すなわちハッシュ情報量）を動的に制御することができる。さらに、認証情報は、受信者によってオンライン形式で検証されることができる。すなわち、受信者は、ストリームを受信しながら認証情報を検証することができるので、いかなる形式の大規模バッファリングも行う必要がない。また、削除されないブロックに関して、第１層ハッシュ計算は必要ない。例えば、ＭＰＥＧ１のフレームやスケーラブルな符号体系のベース層は、故意に削除されない。これらのブロックに関しては、第２層のみが必要である。この場合、該ブロックの第１層ハッシュ関数については、恒等関数ｈ（ｘ）＝ｘに置き換えることができる。同様の精神で、所定の一連のフレームが、全て削除されるか、全て保持される場合、上記の方式は、これらをハッシュ前に単一のブロックとして集めることができるので、さらに一層有益である。
２．部分列認証の効率向上

本発明の第２の実施形態は、第２層ハッシュを実行する前に、第１層ハッシュのいくつかを１つに集めることによって、上記の基本線形部分列認証の効率を向上させるものである。その結果、第２の実施形態による方法は、より少ない第２層ハッシュを実行する。ＳＨＡ−１に付随するもの等の通常の圧縮関数について、ペイロードサイズは６４バイトであるが、ダイジェストサイズは２０バイトである。その結果、この場合、第２層関数を呼び出す前に、３つのダイジェストを連結することができる。第２の実施形態において、ｒ個のハッシュを１つに集めるものとする。さらに、１０進数ａに関し、

は、ａ以上の最小の整数を示し、

は、ａ以下の最大の整数を示す。
２．１ 署名

メッセージＭに関し、第２の実施形態による署名の生成は、第１の実施形態の方式と同様のパラダイムに従い、「２つのハッシング層」を使用する。しかしながら、第２の実施形態の方式は、第１の実施形態よりも少ないハッシュを必要とする。図８は、ｒ＝３であり、ｎをｒの倍数として、本発明の一実施形態による改良された線形部分列認証方式を示す。この方式において、ｒ個の第１層のハッシュ群が、第２層でハッシュされる。メッセージＭ＝Ｍ_１Ｍ_２…Ｍ_ｎが与えられると、第２の実施形態の方式は、

として、部分ハッシュ計算値ｈ_１，…，ｈ_ｍを、以下のように生成する。

第１の実施形態の方式と同様に、第２の実施形態の方式は、ｈ_１，…，ｈ_ｍを計算する過程で、補助ハッシュ値ｇ_１，…，ｇ_ｎを計算するが、それらは送信されない。最初の送信者は、（Ｍ，σ_Ｓｋ（ｈ_ｍ））を送信し、ＩＶ_０の値をＩＶとして使用して、全てのｇ_ｉ値を計算することができる。

或いは、送信者は、ｒ番目の各メッセージブロック〈（Ｍ_１，σ_Ｓｋ（ｈ_ｍ）），（Ｍ_２），…，（Ｍ_ｒ，ｈ_ｍ−１），（Ｍ_ｒ＋１），…，（Ｍ_２ｒ，ｈ_ｍ−２），…（Ｍ_ｎ，ｈ_０）〉と共に、ハッシュ値ｈ_ｉを送信するようにしてもよい。
２．２ 署名の更新

ところで、中間ノードが、ｎ−ｋ個の任意の位置のメッセージブロックを取り除かなければならないものとする。該ノードは、その結果、Ｍと同一であるが、ｎ−ｋ個のブロックが削除された「メッセージ」Ｍ’を生成する。受信者は、Ｍ’を認証できる必要がある。

受信したｎ個のブロックのメッセージＭが与えられると、中間ノードは、「新しい」ブロックＭ’_１，…，Ｍ’_ｎを計算する。メッセージブロックＭ_{ｎ−ｉ＋１}（最後から始めて、ｉ＝１からｉ＝ｎまで）ごとに、中間ノードは、それに対応する補助ハッシュ及び部分ハッシュを計算する。

ブロックが転送されるか削除されるかにより、中間ノードは、ブロックＭ_ｉが転送される場合、Ｍ’_{ｎ−ｉ＋１}＝Ｍ_{ｎ−ｉ＋１}を計算し、または、ブロックＭ_ｉが削除される場合、ｇ_ｉを計算する（式（７））。

ハッシュ値ｈ_ｍ，…，ｈ_１は、署名演算と同じように計算される。中間者は、最終的に、〈Ｍ_１’…Ｍ_ｎ’，σ_Ｓｋ（ｈ_ｍ）〉を送信する。

上記の送信では、検証を行うのに、ｒ個のパケットをバッファリングする必要がある。実際には、ｒは、非常に小さいものである。ＳＨＡ−１に基づく方式では、ｒ＝３であり、ＭＤ−５に基づく方式では、ｒ＝４である。

或いは、中間ノードは、「新しい」メッセージブロック〈（Ｍ_１’，σ_Ｓｋ（ｈ_ｍ）），（Ｍ_２’），…，（Ｍ_ｒ’，ｈ_ｍ−１），（Ｍ_ｒ＋１’），…，（Ｍ_２ｒ’，ｈ_ｍ−２），…，（Ｍ_ｎ’，ｈ_０）〉と共に、ハッシュ値ｈ_ｉを送信してもよい。
２．３ 検証

受信者は、以下のように、Ｍ’_１，…，Ｍ’_ｎから、ｈ_ｍを計算することによって、署名を検証することができる。最初に、メッセージブロックＭ′_{ｎ−ｉ＋１}（最後から始めて、ｉ＝１からｉ＝ｎまで）ごとに、受信したブロックが「メッセージブロック」であるか「ハッシュ」であるかによって、受信者は、Ｍ′_{ｎ−ｉ＋１}が「メッセージブロック」である場合、ｇ’_ｉ＝Ｈ（ｈ_ｉ−１，Ｍ’_{ｎ−ｉ＋１}）を計算し、Ｍ’_{ｎ−ｉ＋１}が「ハッシュ」である場合、ｇ’_ｉ＝Ｍ’_{ｎ−ｉ＋１}を計算する（式（８））。

最後に、受信者は、ｈ_ｍを計算する。

受信者は、検証アルゴリズムνを用いて、ｈ_ｍの署名が正規のものであると確認することができる。

オンライン検証を行うには、受信者は、中間ハッシュｈ_ｉを計算可能である必要がある。そのためには、受信者は、適切なｇ値を計算できるように、ｒ個のブロックをバッファリングする必要がある。この方式のオンライン検証は、第１の実施形態のものと類似している。
２．４ セキュリティ

第１の実施形態と同様に、署名方式が偽造されにくく、ハッシュ関数が衝突しにくいのなら、第２の実施形態の方式は安全である。
２．５ パフォーマンス

第１の実施形態と同様に、中間者は、ブロックを削除する場合、削除するブロックのハッシュを計算するだけでよい。

第１の実施形態の部分列方式に比べ、第２の実施形態の部分列方式は、ｒ個の第１層ハッシュごとにたった１つの第２層ハッシュが実行されるので、署名の計算及び検証の両方にかかる時間が少ない。ｒを慎重に選べば（例えば、ＳＨＡ−１にはｒ＝３、ＭＤ−５にはｒ＝４を設定する）、各第２層ハッシュは、圧縮関数を一度呼び出すだけでよい。そのように、第２の実施形態においては、第１の実施形態のｎ回の呼出しに比べ、第２層において

回だけ圧縮関数の呼出しが行われる。

第１の実施形態の利点に加え、第２の実施形態の受信者は、各ｒ個のブロックを受信した後に、認証情報を検証することができる。実際には、ｒは、かなり小さく、およそ２又は３であり、第２層ハッシュの数は、少なくなる。
３． サイマルキャスト認証：多重方式

さて、最初の送信者Ｓが、ｋ個の異なるストリームＭ^（１），Ｍ^（２），…，Ｍ^（ｋ）を同時に送信するものとする。各ストリームは、長さｂであるｎ個のブロックＭ^（ｊ）＝Ｍ_１ ^（ｊ），…，Ｍ_ｎ ^（ｊ）からなる。第３の実施形態の方式では、中間ノードは、１つのストリームを選択して、認証された形式で再送できるだけではなく、（ブロック送信中、任意の時点で）適応的に他のストリームに「切り替える」ことができる。もちろん、受信者は、その結果生じたストリームを認証することができなければならない。
３．１ 署名

図９は、本発明の一実施形態による基本線形サイマルキャスト認証方式を示す。メッセージＭが与えられると、署名の生成は、第１及び第２の実施形態と同じアプローチ、すなわち、逆反復ハッシュに従うが、各ストリームの全てのブロックの部分ハッシュを計算する。

本発明の第３の実施形態の方式では、Ｍ^（ｊ）＝Ｍ_１ ^（ｊ），Ｍ_２ ^（ｊ），…，Ｍ_ｎ ^（ｊ）であるメッセージＭ^（１），Ｍ^（２），…，Ｍ^（ｋ）が与えられると、部分ハッシュ計算値ｈ_１，…，ｈ_ｎが、以下のように生成される。

最初の送信者は、σ_Ｓｋ（ｈ_ｎ）を送信し、次に、Ｍ^（１），…，Ｍ^（ｋ）を同時に送信する。実際には、異なるストリームのメッセージブロックは、送信中にインターリーブされる。
３．２ 署名の更新

中間ノードが、受信したメッセージブロックごとに、異なる可能性のあるストリーム（メッセージ）の選択を望むものとする。例えば、各メッセージが、異なる品質のビデオストリームを符号化している場合、中間ノードは、ネットワークの輻輳状況により、低い又は高い品質を選択しなければならないかもしれない。中間ノードは、種々のストリームの「チャンク」（連続したメッセージブロック）からなる「その結果生じるメッセージ」Ｍ’を生成する。中間ノードは、各瞬間に、単一のストリーム（メッセージ）を選んでもよい。本発明は、層状ストリームの可能性を考慮するものであることを理解すべきである。受信者は、Ｍ’を認証できる必要がある。

受信したｎ個のブロックのメッセージＭ^（１），…，Ｍ^（ｋ）が与えられると、中間ノードは、「新しい」ブロックＭ’_１，…，Ｍ’_ｎを計算する。（最後から始めて、ｉ＝１からｉ＝ｎまでの）メッセージブロック

の集合ごとに、部分ハッシュを計算する。

次に、ストリームｌが選択された場合、１≦ｌ≦ｋ、

を計算する。

中間ノードは、最後に、〈Ｍ’_１…Ｍ’_ｎ，σ_Ｓｋ（ｈ_ｎ）〉を送信する。

或いは、オンライン検証を可能にするために、中間ノードは、

を送信する。
３．３ 検証

受信者は、Ｍ’_１，…，Ｍ’_ｋ及びｈ_０＝ＩＶ_０からｈ_ｎを計算することによって、署名を検証することができる。メッセージブロックＭ’_{ｎ−ｉ＋１}（最後から始めて、ｉ＝１からｉ＝ｎまで）ごとに、Ｍ’_{ｎ−ｉ＋１}が

の形式である場合、

受信者は、

を計算する。

受信者は、検証アルゴリズムνを用いて、ｈ_ｎの署名を正規のものであると確認することができる。

その代わりとなるオンライン検証手続は容易である。受信者は、関係式（１４）を用いて、（Ｍ’_１，ｈ_ｎ−１）から部分ハッシュｈ_ｎを計算して、部分ハッシュｈ_ｎの署名を検証する。その後、ｉ＝２，…，ｎについて、（１４）を用いて（Ｍ’_ｉ，ｈ_ｎ−ｉ）から部分ハッシュｈ_ｉを計算して、そのように計算したハッシュが反復ｉ−１で受信したハッシュ値と一致することを確認する。
３．４ パフォーマンス

第１の実施形態の方式の利点に加え、第３の実施形態の方式のハッシュステップは、線形連鎖方式又はＭｅｒｋｌｅ方式のいずれかにより、圧縮関数を用いて反復することができる。

Ｍｅｒｋｌｅ木のような構造を用いて各一連のブロックＭ_ｉ ^（１），…，Ｍ_ｉ ^（ｋ）をハッシュダウンすることによって、（中間ノードによる）さらに集約的な計算という犠牲を払って、帯域幅を節約することができる。
４． 部分列認証のための木方式

本発明の第４の実施形態は、Ｍｅｒｋｌｅ木を用いて部分列を認証するための方式である。線形部分列認証方式のように、この木を用いた方式は、メッセージから任意のブロックが削除されても、ストリーム認証を可能にする。中間ノードによって送信されたブロックが、元メッセージの真の部分列であれば、受信者は、ストリームを認証することができる。木構造の特徴を利用することによって、木方式は、帯域幅に関し、線形方式よりも効率的である。
４．１ 署名

図１０は、本発明の一実施形態による木を用いた部分列認証方式を示している。第４の実施形態の方式は、メッセージＭ＝Ｍ_１Ｍ_２…Ｍ_ｎが与えられると、図６に示すＭｅｒｋｌｅ木を生成する。νが木の根を示し、ｘが根に対応する値を示すとすると、最初の送信者は、（Ｍ，σ_Ｓｋ（ｘ））を送信する。
４．２ 署名の更新

中間者が、ｋ個の任意の位置のメッセージブロックを取り除かなければならない場合、中間者は、その結果、Ｍと同一であるが、ｋ個のブロックが削除されている「メッセージ」Ｍ’を生成する。受信者は、Ｍ’を認証できる必要がある。ｄ_１，…，ｄ_ｋが、削除されるブロックのインデックスを示すものとし、ｓ_１，…，ｓ_ｎ−ｋが、とどまるブロックを示すものとする。受信したｎ個のブロックメッセージＭが与えられると、中間ノードは、対応する認証情報を、以下のように計算する。
１）削除される全てのブロック

について、中間者は、最初に、これらのブロックに対応するＭｅｒｋｌｅ木の葉

に相当する頂点の集合を求める。
２）Ｍｅｒｋｌｅ木において任意の頂点対が兄弟である場合、中間者は、それらの２つの頂点の両方を、それらの親に置き換える。
３）中間者は、該集合に兄弟である二つの頂点がなくなるまで、上記の処理を繰り返す。
４）中間者は、この頂点集合を取り出し、それらに対応するＭｅｒｋｌｅ木の値ｘ_１，…，ｘ_ｒを計算する。暗号ハッシュ関数は、大域的に計算可能であるので、中間者は、このステップを容易に行うことができる。

中間ノードは、最後に、

を送信する。

本発明の他の実施形態と同様に、標準的な符号化をブロックコンテンツに適用することで、「メッセージブロック」と「ハッシュ」との区別が容易になる。
４．３ 検証

受信者は、以下のアルゴリズムを用いて、Ｍｅｒｋｌｅ木の根の値を計算することによって、署名を検証する。
１） 受信した実際のメッセージブロック

ごとに、

の値を計算する。
２）全てのハッシュｙ_ｉ，…，ｙ_ｎ−ｋ，ｘ_１，…，ｘ_ｒの集合を考慮する。これらは、それぞれ、Ｍｅｒｋｌｅ木の頂点の値に相当する。
３）１対の値ごとに、それらが兄弟である頂点に相当する場合、その対をそれらのハッシュ（親ノードに相当する）に置き換える。
４）１つの値だけが残るまで、上記ステップを繰り返す。この値は根である。

初期メッセージブロックの全てを有するならば、上記アルゴリズムは、Ｍｅｒｋｌｅ木の根を計算するための標準アルゴリズムとなる。受信者が、いくつかのハッシュｘ_１，…，ｘ_ｒを受信したときは、これらは、欠けているブロックの部分集合に対して同じアルゴリズムを実行した中間者から来ている。従って、中間者と受信者は、共に、Ｍｅｒｋｌｅ根の値をもたらすｎ個の全てのブロックに該アルゴリズムを実行している。これが、上記の計算がＭｅｒｋｌｅ根をもたらす理由である。

Ｍｅｒｋｌｅ根の値により、受信者は、受信した署名を検証することができる。
４．４ セキュリティ

上記Ｍｅｒｋｌｅハッシュ構造は、基礎をなすハッシュ関数Ｈが耐衝突性であれば、耐衝突性である。特に、Ｍｅｒｋｌｅ木に衝突が見つかった場合、ある時点で、内部ノードに衝突が存在することになり、ハッシュ関数Ｈに衝突を見つけることができることになる。敵が非部分列偽造を考え出す（つまり、元メッセージの部分列を取り出しただけでは得られない１対のメッセージ／署名を考え出す）ことができた場合、ハッシュ関数における衝突か、基礎をなす署名方式の偽造のいずれかを証明することができる。従って、署名方式が偽造されにくく、ハッシュ関数が衝突しにくいなら、第４の実施形態の方式は安全である。
４．５ パフォーマンス

中間者がブロックを削除する場合、受信者に、それらのメッセージブロックなしで木のＭｅｒｋｌｅ根を計算するのに十分な数の内部ハッシュを提供する必要がある。中間者は、削除する各ブロックに対してｋ個のハッシュを必要とし、また、複数対のハッシュを単一のハッシュに置き換える場合は、多くてｋ−１個のハッシュを必要とする（単一のハッシュにより、２つの値を１つの値に置き換えることによって、総数が１つ減るため）。従って、全計算では、多くて２ｋ−１個のハッシュとなる。中間者によって計算された全ハッシュをｔで示す。

受信者は、ストリームを受信すると、根を計算する必要がある。全てのメッセージブロックを得た場合、最初に各ブロックをハッシュするのに、２ｎ−１ハッシュ−ｎが必要であり、また、複数対のハッシュ値を単一のハッシュに置き換える場合、ｎ−１個のハッシュがさらに必要である（単一関数計算により、２つの値を１つの値に置き換えることになり、最後には、たった１つの値が残っているから）。しかしながら、これらのハッシュのうちのｔは、中間者によって計算される。従って、受信者は、２ｎ−１−ｔ個のハッシュを計算するだけでよい。

この方式における、中間者と受信者との間の全作業は、多くて２ｎ−１個のハッシュである。前の線形方式では、２ｎ個のハッシュが必要であった。

帯域幅に関しては、木を用いた方式は、はるかに効率的かもしれない。ｒ≦ｋ個のハッシュだけが最終的に送信される。最良のケースでは、削除されるｋ個のブロックが全体でＭｅｒｋｌｅ木の部分木の全ての葉を構成する場合、この部分木の根に相当する単一の値のみが送信され、すなわち、ｒ＝１である。最悪のケースでは、兄弟であるブロック対がない場合、帯域幅要件は、線形の場合とまったく同じであり、ｋ個のハッシュ値を送信する必要がある。
５． サイマルキャスト認証のための木方式

本発明の第５の実施形態は、送信の各ステップで、１つのデータブロックが１つのストリームから選択される、複数の平行ストリームを認証するための木を用いた方式である。第３の実施形態の線形多重設定におけるように、最初の送信者Ｓは、ｋ個の異なるストリームＭ^（１），Ｍ^（２），…，Ｍ^（ｋ）を同時に送信するものとする。各ストリームは、長さｂのｎ個のブロックＭ^（ｊ）＝Ｍ_１ ^（ｊ），…，Ｍ_ｎ ^（ｊ）からなる。本方式では、中間ノードは、１つのストリームを選択して、認証された形式で再送することができるだけでなく、（ブロック送信中の任意の時点で）適応的に他のストリームに「切り替える」ことができる。もちろん、受信者は、その結果生じるストリームを認証することができる。第４の実施形態の部分列認証のための木を用いた方式におけるように、第５の実施形態の方式は、帯域幅に関して類似線形方式よりも効率的となるように、木構造の特定の特徴を利用する。他方、第４の実施形態の木構造のように、第５の実施形態の方式はオンライン検証には適していない。それどころか、受信者は、全てのパケットを待たないと検証することができない。実際には、遅延は、ストリームを適当なサイズのセグメントに分割して、各セグメントを別々に認証することによって、小さくすることができる。
５．１ 署名

ｋ個の異なるストリームＭ^（１），Ｍ^（２），…，Ｍ^（ｋ）が与えられると、第５の実施形態の方式の署名生成は、以下のように進む。
１）最初に、署名者は、ストリームごとに別個のＭｅｒｋｌｅ木を生成する。ｖ^（１），…，ｖ^（ｋ）を、木のｋ個の根を示すものとし、ｘ^（１），…，ｘ^（ｋ）を、これらの根にそれぞれ対応する値を示すものとする。
２）次に、署名者は、ｘ＝Ｈ（ＩＶ，ｘ^（１），…，ｘ^（ｋ））を計算する。ここで、ハッシュ関数Ｈは、同じくＭｅｒｋｌｅ木構造を用いて計算することができる。
３）最後に、署名者は、（Ｍ，σ_Ｓｋ（ｘ））を送信する。
５．２ 署名の更新

さて、中間ノードは、受信したメッセージブロックごとに、異なる可能性のあるストリーム（メッセージ）を選択しなければならないものとする。例えば、各メッセージが、異なる品質のビデオストリームを符号化している場合、中間ノードは、ネットワークの輻輳状況によって、低い又は高い品質を選択しなければならないかもしれない。その結果、異なるストリームの「チャンク」（連続するメッセージブロック）からなる「メッセージ」Ｍ’を生成する。受信者は、Ｍ’を認証できる必要がある。

受信者が、ｘ_ｉの値のそれぞれを正確に計算できる場合、署名を検証することができる。従って、中間者は、これらの値を計算するのに必要な情報をユーザに提供するだけでよい。各Ｍｅｒｋｌｅ木を別々に処理することによって、中間者は、第４の実施形態のＭｅｒｋｌｅ方式においてそうしたように、必要な値の集合を計算することができる。中間者は、これらの値を受信者に送信し、受信者は、ｘ_ｉの値を計算し、その結果、認証情報を検証することができる。

具体的には、１≦ｉ≦ｋである各ｉに関し、ｋｓ（ｉ）が、ストリームＭ^（ｉ）から実際に送信されるブロックの数を示すものとする。ストリームＭ^（ｉ）に関しては、

が、含まれるブロックのインデックスを示すものとする。Ｍ′^（ｉ）を、これらのブロックを示すものとする。

削除するブロックのインデックスについては、１≦ｉ≦ｋである各ｉに関し、ｋｄ（ｉ）が、ストリームＭ^（ｉ）から実際に削除されるブロックの数を示すものとする。ストリームＭ^（ｉ）に関し、

が、削除されるブロックのインデックスを示すものとする。

第４の実施形態の木方式におけるように、中間者は、各ストリームＭ^（ｉ）に関して、受信者が検証するのに必要な値を、以下のように計算する。
１）削除される全てのブロック

に関し、中間者は、最初に、これらのブロックに対応するＭｅｒｋｌｅ木の葉

に相当する頂点の集合を求める。
２）そこで、Ｍｅｒｋｌｅ木において任意の頂点対が兄弟である場合、中間者は、それら２つの頂点の両方を、それらの親、すなわち、兄弟に対応する値の連結のハッシュと置き換える。
３）中間者は、該集合に兄弟である２つの頂点がなくなるまで、上記の処理を繰り返す。
４）中間者は、この集合の頂点を取り出し、それらに対応するＭｅｒｋｌｅ木の値Ｘ^（ｉ）＝ｘ_１ ^（ｉ），…，ｘ_ｒ ^（ｉ）を計算する。暗号ハッシュ関数は、大域的に計算可能であるので、中間者は、このステップを容易に行うことができる。

中間ノードは、最後に、以下の情報を送信する。

ストリームは、適切な順序で送信される。すなわち、各Ｍ’^（ｉ）からのブロックは、受信者がストリームを見ることができるようにインターリーブしてもよい。受信者がメッセージブロックとハッシュ値とを区別できるように、標準的な符号化をブロックコンテンツに適用する。
５．３ 検証

受信者は、最初に、各Ｍｅｒｋｌｅ木の根の値を計算し、その後、これらの値をハッシュして、署名を検証する。各ｉに行われる以下のアルゴリズムを用いて、この目的を達する。
１）最初に、受信者は、受信した実際のメッセージブロック

ごとに、

の値を計算する。
２）上述のように、前ステップで計算された全てのハッシュの集合と、該送信において受信された集合Ｘ^（１），…，Ｘ^（ｋ）に含まれるハッシュ値とを考慮する。
３）１対の値ごとに、該対が兄弟である頂点に相当するものであるならば、該対をそれらのハッシュ（Ｍｅｒｋｌｅ木の親ノードに相当する）に置き換える。
４）１つの値だけが残るまで上記ステップを繰り返す。この値は根ｘ^（ｉ）である。

初期メッセージブロックの全てを得ているならば、上記のアルゴリズムは、Ｍｅｒｋｌｅ木の根を計算するための標準アルゴリズムとなる。受信者が、いくつかのハッシュｘ_１ ^（ｉ），…，ｘ_ｒ ^（ｉ）を受信するときは、欠けているブロックの部分集合に対して同じアルゴリズムを実行している中間者からそれらは来ている。従って、中間者と受信者は、共に、Ｍｅｒｋｌｅ根の値をもたらすｎ個のブロックの全てについて該アルゴリズムを実行している。これが、上記の計算がＭｅｒｋｌｅ根をもたらす理由である。

受信者は、Ｍｅｒｋｌｅ根の値、ｘ^（１），…，ｘ^（ｋ）によって、ｘ＝Ｈ（ＩＶ，ｘ^（１），…，ｘ^（ｋ））を計算し、受信した署名を検証することができる。

図１１は、本発明の第５の実施形態の署名及び検証を示すものであり、４つのストリームと４つのメッセージブロックを有する例である。図に示すように、４つのストリームＭ^（１），Ｍ^（２），Ｍ^（３），Ｍ^（４）は、それぞれ、４つのブロックからなる。黒い葉は、実際に送信されるメッセージブロックを示す。残りは、削除される。影付きの頂点は、カバーを示す。すなわち、これらの頂点に相当する値は、受信者に送信される。４つのＭｅｒｋｌｅ木の根は、それぞれ、ｘ^（１），ｘ^（２），ｘ^（３），ｘ^（４）である。最終的な根の値ｘは、Ｍｅｒｋｌｅ根ｘ^（１），ｘ^（２），ｘ^（３），ｘ^（４）をハッシュすることによって計算される。このハッシュは、Ｍｅｒｋｌｅのような形式でも実行することができる。最後に、値ｘが実際に署名される。この方式において、６つのハッシュ値だけが受信者に送信される。線形サイマルキャスト方式では、１２のハッシュが送信されていた（送信される１ブロックごとに３つ）。従って、削除されるブロックをひとかたまりにするたびに、節約が達成される。例えば、図１１において、ストリームＭ^（４）のブロックは、全て削除される。その結果、対応するＭｅｒｋｌｅ木の根ｘ^（４）を送信するだけでよい。

また、Ｍｅｒｋｌｅ根は、それ自体、Ｍｅｒｋｌｅのような構造においてハッシュされるので、さらに最適化する余地がある。具体的には、Ｍｅｒｋｌｅ根が、さらに大きい木において兄弟である２つの完全な部分木について、全てのブロックを削除するものとする。その結果、２つのＭｅｒｋｌｅ根を送信する代わりに、それらのハッシュを送信することができる。
５．４ セキュリティ

第４の実施形態と同様に、第５の実施形態は、署名方式が偽造されにくく、ハッシュ関数が衝突しにくいならば、安全である。従って、上記に示した本発明は安全である。
５．５ パフォーマンス

第５実施形態のパフォーマンスは、木を用いた部分列方式と線形サイマルキャスト方式とに関する分析を拡張することによって、分析することができる。

上述の全ての実施形態において、特定のペイロードサイズと特定のＩＶとを用いたハッシュ関数が用いられる。連鎖構造は、ある既存の出力を取り出し、次のブロックのＩＶとして用いる傾向がある。さらなる実施形態では、ＩＶとして現時点の出力をロードする代わりに、現時点の出力を次のペイロードに連結することができる。

本発明の線形方式と木方式を組み合わせて、ハイブリッドの解決法を得ることで、有益なトレードオフをもたらすことができる。さらなる実施形態では、ある方式が、各ストリームＭ^（ｉ）を、長さｂのブロックのセグメントに分割することによって始まる。次に、木方式を、全てのストリームの第１のセグメントに適用して、Ｍｅｒｋｌｅ根ｘ_１を計算し、次に第２のセグメントに関する根、というふうに、全てのセグメントが処理されるまで計算する。こうして、Ｍｅｒｋｌｅ根

が得られる。これらの根の１つ１つに署名するかわりに、上記に説明した木方式におけるように、根は、線形方式を用いて結合される。従って、受信者が、ｂ個のブロックをバッファリングすることができる場合、検証は、「オンライン」でできる。さらに、ｂ個のブロックのセグメントごとに送信されるハッシュの数は、削除されるブロックの数よりもはるかに少なくてもよいので（最悪のケースでは同じであるが）、通信オーバーヘッドは、簡単な線形方式に比べて減少する。同様のアプローチを、部分列認証にも採用することができる。このハイブリッド方法により、バッファ領域を、通信オーバーヘッドとトレードすることができる。

さらなる実施形態においては、線形方式を各ストリームに適用し、その結果についてＭｅｒｋｌｅ木を計算する。

上記の実施形態は、バイナリのＭｅｒｋｌｅ木を使用しているが、その構造は、一般的な木に適用することができる。所定のブロックが、同様の性質を有する、すなわち、全てが削除されるか、又は、全てが保持されるかのいずれかである場合、それらを１つにまとめることは、さらに有益であるかもしれない。

ブロック間に相関がある場合、木を用いた方式において、これらのブロックをひとまとめにすることは、理にかなっている。例えば、あるブロック群が、全て削除されるか、全て保持されるかのいずれかである場合、これらのブロックが、部分木の全ての葉を構成するようにすることは有益である。従って、パケットを削除する場合、その部分木の根を送信するだけでよい。

さらに、Ｍｅｒｋｌｅ木構造を最適化することができる。一実施形態において、ストリームの１つが、他のものよりも使用される可能性が高い場合、この優先ストリームが根に近い（例えば、おそらく右下にある）不均衡なＭｅｒｋｌｅ木を使用することは都合がよい。前述のハイブリッド方式に関連して、ストリームは、優先順位をつけられるので、高い優先度のストリームは、連鎖の最終値に近くなる。この順序付けは、層状ストリームを使用する場合、特に理にかなっている。かかる場合、検証において、根に到達するためのハッシュステップがより少なくて済む。

ＭＰＥＧストリームのＩフレームや、スケーラブルに符号化されたストリームのベース層など、削除すべきではないブロックが存在する。署名者は、削除されないブロックについて、最初の第１層ハッシュを直接計算しなくて済む。線形方式では、ハッシュ層は２つある。ブロックが削除されない場合、第１層のハッシュを計算する必要はなく、代わりに、第２層だけを計算すればよい。

本発明の方式は、２つの段階を有すると解釈することができる。第１の段階では、各データブロックをハッシュするのに便利な方法を見つける。第２の段階では、ハッシュに署名する。そうする理由は、ブロックが削除される場合、それを完全な形で再送する必要がないからである。その代わりに、第１の段階で計算されたハッシュのみを送信する。署名は、ハッシュに行われたものとみなすことができるので、受信者は、この情報で十分検証できる。

すでに述べたように、本発明は、制御損失のケースに対処するものであり、すなわち、送信者は、特定のブロックを故意に削除する。もちろん、多くの実際のアプリケーションにおいて、非制御の損失事態に対処しなければならないかもしれない。例えば、ＵＤＰのように、トランスポートプロトコルが信頼できない場合や、無線ネットワークのように、環境が損失動作に左右される場合、このような事態は起こりうる。本発明は、パケットが削除された場合、送信されるハッシュを複製することによって、非制御損失に対処するのに使用することができる。

消去符号等の順方向誤り訂正（ＦＥＣ）技術を本発明のハッシュに適用することによって、複製する必要なしに非制御損失事態に対処することが可能である。このアプローチは、異なる受信者が異なるパケットを失っているが、同一の誤り訂正情報を与えられるマルチキャスト設定において、特に有益であるかもしれない。このアプローチで考慮するべきことは、受信者が復号処理を行わなければならず、オンライン形式で認証情報を検証する能力を犠牲にしなければならない可能性があることである。

さらに、本発明の方式は、認証情報（すなわち、ハッシュ出力）に対する順方向誤り訂正量を適応的に選択できる中間者を必要とする。換言すると、送信元に、どれくらいの損失が起こるかを予測させて、十分な認証順方向誤り訂正情報を含めて対処させるのではなく、送信元は、認証順方向誤り訂正情報をまったく含めないことにすることができ、代わりに、中間者が、認証順方向誤り訂正情報を動的に含めて、ストリームを認証できる確率をさらに高めることができるようにすることができる。

中間者は、適応的・知能的制御損失に加え、順方向誤り訂正により対処する非制御損失の両方を考慮する方式の不可欠な部分となる。例えば、Ｍｅｒｋｌｅ木構造において、受信者にとって、（単なる葉ノードではなく）中間ノードを回復すれば十分かもしれない。かかる場合、中間者は、順方向誤り訂正情報を提供することにして、認証に必要な（おそらく内部）ノードを回復できるようにすることができ、おそらくより少ない順方向誤り訂正情報で済む。

中間者が、複数の受信者に対して、例えば、受信者がそれぞれ見ている品質について様々なリソースの制約があるために、同一ストリームの様々なバージョンを送信している場合、中間者は、作業労力を再利用することができる。具体的に、中間者は、第１層ハッシュを記憶し再利用することができる。その結果、多くても、完全な第１層ハッシュの集合を計算するだけでよい。

この線に沿って、送信元と中間者との間で作業は再利用することができる。すなわち、送信元は、認証を補助するのに必要なハッシュ計算値を、中間者に提供することができる。従って、中間者は、暗号的性質の作業を実行する必要がない。代わりに、どのブロックを削除するかを決め、それに対応する送信する認証情報を選択することができる。

本発明の別のアプリケーションは、ストリームに広告を挿入し、広告を選択することである。中間者又は他の者は、広告、又は、例えばＭｅｒｋｌｅ木を用いてハッシュした広告のハッシュを、送信元に提供する。すると送信元は、ストリームにプレースホルダーとしてＭｅｒｋｌｅハッシュを含めて、中間者が使用したい広告を選ぶことができるようにする。もちろん、この概念は、必ずしも広告者に限定されるものではない。

本発明の中心は、情報を認証することにあるが、上記の方式は、暗号方式に関連して使用することもできる。ただし、受信者が、他の多くのブロックの復号又は存在を必要とせずに、所定のブロックを復号することができるように、該方式が構成されていればである。２つのブロック暗号暗号化モードにより、この方法は容易になる。１つは、カウンタモード暗号化であり、他方は、電子コードブック（ＥＣＢ）暗号化である。或いは、ストリーム暗号を用いることもできる。ただし、受信者は、受信したストリームの１部分ではなく、元ストリームのサイズに比例した作業を実行する必要があるかもしれない。受信者が、復号する中間情報を受信しているならば、連鎖又はフィードバックモード（暗号ブロック連鎖方式（ＣＢＣ）、出力フィードバック（ＯＦＢ）等）を使用することが可能かもしれない。かかる情報は、中間ＩＶや、実際の暗号文ブロックを含んでいてもよい。さらに他の方法は、該モードを混合するものである。すなわち、削除されない大きいセグメントに関しては、連鎖又はフィードバックモードを使用することができ、一方、その他のブロックに関しては、カウンタモード又はＥＣＢモードを使用することができる。例えば、ＭＰＥＧストリームにおいては、Ｉフレームは、故意に削除されることはないので別に処理し、ＣＢＣモードを使用して暗号化することができる。同様のことが、スケーラブルな符号体系のベース層にも言える。

上記において、本発明を様々な実施形態について詳細に説明してきたが、当業者であれば、これらの実施形態を本発明の範囲及び精神から逸脱することなく、変更することができることを理解するであろう。従って、本発明は、添付の請求項の範囲によってのみ限定されるものとみなされるべきである。

スケーラブルなコーダのハイレベル図を示す。 送信者又は送信元のブロック図を示す。 受信者のブロック図を示す。 中間者のブロック図を示す。 送信者、受信者、及び中間者を含むシステムのブロック図を示す。 ８個の葉を持つＭｅｒｋｌｅ木を示す。 本発明の一実施形態による、基本線形部分列認証方式を示す。 本発明の一実施形態による、ｒ＝３であり、ｎがｒの倍数である、最適化された線形部分列認証方式を示す。 本発明の一実施形態による、基本線形サイマルキャスト認証方式を示す。 本発明の一実施形態による、木を用いた部分列認証方式を示す。 本発明の一実施形態による、木を用いたサイマルキャスト認証方式を示す。

Claims (61)

1. サーバと受信者との間でデータを通信する方法であって、
   複数のブロックを含む少なくとも１つの元データストリームに署名する工程と、
   前記元データストリームを構成する複数のブロックのそれぞれに署名を行わずに、任意のブロックが適応的に削除された前記署名されたデータストリームに対する中間データストリームを生成する工程と、
   前記中間データストリームを前記受信者に通信する工程と、
   前記受信者において、前記中間データストリームを認証する工程を含み、
   前記元データストリームに署名する工程は、補助ハッシュ値と部分ハッシュ値とを含むハッシュ計算値を生成する工程を含み、
   前記中間データストリームを生成する工程は、前記署名されたデータストリームのブロックごとに、前記部分ハッシュ値と前記補助ハッシュ値とを計算する工程を含み、
   前記中間データストリームは、前記受信者に送信されるデータストリームブロックと、前記削除されるブロックに対する補助ハッシュ値とを含み、
   前記補助ハッシュ値は、当該補助ハッシュ値に対応するブロック以外のブロックを用いた算出されるハッシュ値であり、
   前記補助ハッシュ値は、前記署名者から送信されないハッシュ値であり、
   前記部分ハッシュ値は、当該補助ハッシュ値に対応するブロック以外のブロックに対応する部分ハッシュ値、及び、当該部分ハッシュ値に対応するブロックに対応する補助ハッシュ値を用いて算出されるハッシュ値であることを特徴とする方法。
2. 前記受信者において、受信したブロックがデータストリームブロックであるか否かについてを判定する工程をさらに含むことを特徴とする請求項１に記載の方法。
3. 前記受信者において、前記データストリームブロックに対する前記部分ハッシュ値を再計算する工程をさらに含むことを特徴とする請求項１に記載の方法。
4. 前記受信者において、前記再計算された部分ハッシュ値に基づいて、前記署名を検証する工程をさらに含むことを特徴とする請求項３に記載の方法。
5. 前記部分ハッシュ値を計算する前に、いくつかの補助ハッシュ値をまとめる工程をさらに含むことを特徴とする請求項１に記載の方法。
6. 前記元データストリームに署名する工程は、前記元データストリームに対するＭｅｒｋｌｅ木を生成し、該Ｍｅｒｋｌｅ木の根に対応する値を計算する工程をさらに含むことを特徴とする請求項１に記載の方法。
7. 前記中間データストリームは、
   前記受信者が前記Ｍｅｒｋｌｅ木の根を再計算するためのＭｅｒｋｌｅ木の値と、
   データストリームブロックとを含むことを特徴とする請求項６に記載の方法。
8. 前記中間データストリームを生成する工程は、
   前記削除されるブロックに対応する前記Ｍｅｒｋｌｅ木の葉に相当する頂点の集合を決定する工程と、
   前記Ｍｅｒｋｌｅ木において任意の頂点対が兄弟である場合、該頂点対における２つの頂点を該２つの頂点の親に置き換える工程と、
   前記Ｍｅｒｋｌｅ木において任意の頂点対が兄弟でない場合、該頂点に対応する前記Ｍｅｒｋｌｅ木の値を計算する工程とをさらに含むことを特徴とする請求項６に記載の方法。
9. 受信者において、前記Ｍｅｒｋｌｅ木の根の値を再計算する工程をさらに含むことを特徴とする請求項８に記載の方法。
10. 前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項８に記載の方法。
11. 前記受信者において、前記Ｍｅｒｋｌｅ木の根の値により前記署名を検証する工程をさらに含むことを特徴とする請求項９に記載の方法。
12. 前記元データストリームに署名する工程は、各元データストリームの各ブロックの部分ハッシュ値を計算して、多層ハッシュチェーンを計算する工程をさらに含むことを特徴とする請求項１に記載の方法。
13. 前記中間データストリームを生成する工程は、各署名されたデータストリームの各ブロックに対する前記部分ハッシュ値を計算する工程をさらに含むことを特徴とする請求項１２に記載の方法。
14. 前記中間データストリームは、異なるデータストリームから適応的に選択されたデータストリームブロックを含むことを特徴とする請求項１２に記載の方法。
15. 前記受信者において、前記中間データストリームの各ブロックに対する前記部分ハッシュ値を再計算する工程をさらに含むことを特徴とする請求項１２に記載の方法。
16. 前記受信者において、前記再計算された部分ハッシュ値に基づいて、前記署名を検証する工程をさらに含むことを特徴とする請求項１５に記載の方法。
17. 前記元データストリームに署名する工程は、
    前記元データストリームごとに、Ｍｅｒｋｌｅ木を生成する工程と、
    前記Ｍｅｒｋｌｅ木の各々の根に対応する値を計算する工程と、
    前記Ｍｅｒｋｌｅ木の根の値をハッシュすることによって、最終的な根の値を生成する工程とをさらに含むことを特徴とする請求項１に記載の方法。
18. 前記中間データストリームは、
    データストリームブロックと、
    前記受信者が前記Ｍｅｒｋｌｅ木の根を再計算するための前記Ｍｅｒｋｌｅ木の値とを含むことを特徴とする請求項１７に記載の方法。
19. 前記中間データストリームを生成する工程は、
    署名されたデータストリームごとに、前記削除されるブロックに対応する前記Ｍｅｒｋｌｅ木の葉に相当する頂点の集合を決定する工程と、
    前記Ｍｅｒｋｌｅ木において任意の頂点対が兄弟である場合、該頂点対における２つの頂点を該２つの頂点の親に置き換える工程と、
    前記Ｍｅｒｋｌｅ木において任意の頂点対が兄弟でない場合、該頂点に対応する前記Ｍｅｒｋｌｅ木の値を計算する工程とをさらに含むことを特徴とする請求項１７に記載の方法。
20. 前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項１９に記載の方法。
21. 前記受信者において、前記Ｍｅｒｋｌｅ木の各々の根の値を再計算する工程をさらに含むことを特徴とする請求項１７に記載の方法。
22. 前記受信者において、前記Ｍｅｒｋｌｅ木の根の値をハッシュすることによって、前記最終的な根の値を再計算する工程をさらに含むことを特徴とする請求項２１に記載の方法。
23. 前記受信者において、前記最終的な根の値により前記署名を検証する工程をさらに含むことを特徴とする請求項２２に記載の方法。
24. 前記最終的な根の値は、反復ハッシュによって再計算されることを特徴とする請求項２２に記載の方法。
25. 前記最終根の値は、Ｍｅｒｋｌｅハッシュによって再計算されることを特徴とする請求項２２に記載の方法。
26. 前記Ｍｅｒｋｌｅ木は、不均衡であることを特徴とする請求項６に記載の方法。
27. 前記Ｍｅｒｋｌｅ木は、不均衡であることを特徴とする請求項１７に記載の方法。
28. 全てが削除される一群のブロックによって部分木を形成する工程をさらに含むことを特徴とする請求項６に記載の方法。
29. 全てが削除される一群のブロックによって部分木を形成する工程をさらに含むことを特徴とする請求項１７に記載の方法。
30. 全てが送信される一群のブロックによって部分木を形成する工程をさらに含むことを特徴とする請求項６に記載の方法。
31. 全てが送信される一群のブロックによって部分木を形成する工程をさらに含むことを特徴とする請求項１７に記載の方法。
32. 前記最終的な根の値は、反復ハッシュによって生成されることを特徴とする請求項６に記載の方法。
33. 前記最終的な根の値は、Ｍｅｒｋｌｅハッシュによって生成されることを特徴とする請求項１７に記載の方法。
34. 決して削除されないブロックを決定する工程をさらに含むことを特徴とする請求項１に記載の方法。
35. 前記ブロックが決して削除されない場合、恒等関数を第１層ハッシュとして適用する工程をさらに含むことを特徴とする請求項３４に記載の方法。
36. 前記ハッシュ値に、順方向誤り訂正（ＦＥＣ）技術を適用する工程をさらに含むことを特徴とする請求項１に記載の方法。
37. 前記元データストリームに署名する工程は、電子署名を使用することを特徴とする請求項１に記載の方法。
38. 前記電子署名は、前記元データストリームのブロックの最終ハッシュ値に適用することを特徴とする請求項３７に記載の方法。
39. 前記元データストリームに署名する工程は、メッセージ認証符号を使用することを特徴とする請求項１に記載の方法。
40. 前記メッセージ認証符号は、前記元データストリームのブロックの最終ハッシュ値に適用することを特徴とする請求項３９に記載の方法。
41. 前記削除されるデータストリームブロックは、広告を含むことを特徴とする請求項１に記載の方法。
42. サーバと受信者との間でデータを通信するシステムであって、
    複数のブロックを含む少なくとも１つの元データストリームに署名する署名者と、
    前記元データストリームを構成する複数のブロックのそれぞれに署名を行わずに、任意のブロックが適応的に削除された前記署名されたデータストリームに対する中間データストリームを生成するデータストリーム生成者と、
    前記中間データストリームを認証する受信者とを含み、
    前記署名者は、補助ハッシュ値と部分ハッシュ値とを含むハッシュ計算値を生成し、
    前記データストリーム生成者は、前記署名されたデータストリームを受信し、該データストリームのブロックごとに、前記部分ハッシュ値と前記補助ハッシュ値とを計算し、
    前記中間データストリームは、前記受信者に送信されるデータストリームブロックと、前記削除されるブロックに対する補助ハッシュ値とを含み、
    前記補助ハッシュ値は、当該補助ハッシュ値に対応するブロック以外のブロックを用いた算出されるハッシュ値であり、
    前記補助ハッシュ値は、前記署名者から送信されないハッシュ値であり、
    前記部分ハッシュ値は、当該補助ハッシュ値に対応するブロック以外のブロックに対応する部分ハッシュ値、及び、当該部分ハッシュ値に対応するブロックに対応する補助ハッシュ値を用いて算出されるハッシュ値であることを特徴とするシステム。
43. 前記受信者は、前記中間データストリームを受信し、前記データストリームブロックに対する前記部分ハッシュ値を再計算することを特徴とする請求項４２に記載のシステム。
44. 前記署名者は、部分ハッシュ値を計算する前に、いくつかの補助ハッシュ値をまとめることを特徴とする請求項４３に記載のシステム。
45. 前記署名者は、元データストリームについて生成されたＭｅｒｋｌｅ木の根に対応する値を計算することを特徴とする請求項４２に記載のシステム。
46. 前記データストリーム生成者は、
    前記署名されたデータストリームを受信し、
    前記削除されるブロックに対応する前記Ｍｅｒｋｌｅ木の葉に相当する頂点の集合を決定し、
    前記Ｍｅｒｋｌｅ木において任意の頂点対が兄弟である場合、該頂点対における２つの頂点を該２つの頂点の親に置き換え、
    前記Ｍｅｒｋｌｅ木において任意の頂点対が兄弟でない場合、該頂点に対応する前記Ｍｅｒｋｌｅ木の値を計算することを特徴とする請求項４５に記載のシステム。
47. 前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項４６に記載の方法。
48. 前記受信者は、前記中間データストリームを受信し、前記Ｍｅｒｋｌｅ木の根の値を再計算することを特徴とする請求項４５に記載のシステム。
49. 前記署名者は、各データストリームの各ブロックに対する部分ハッシュ値を計算して、多層ハッシュチェーンを計算することを特徴とする請求項４２に記載のシステム。
50. 前記データストリーム生成者は、前記署名されたデータストリームを受信し、各署名されたデータストリームのブロックごとに、前記部分ハッシュ値を計算することを特徴とする請求項４９に記載のシステム。
51. 前記受信者は、前記中間データストリームを受信し、前記中間データストリームのブロックごとに、前記部分ハッシュ値を再計算することを特徴とする請求項４９に記載のシステム。
52. 前記署名者は、
    前記元データストリームごとに、Ｍｅｒｋｌｅ木を生成し、
    前記Ｍｅｒｋｌｅ木の各々の根に対応する値を計算し、
    前記Ｍｅｒｋｌｅ木の根の値をハッシュすることによって、最終的な根の値を生成することを特徴とする請求項４２に記載のシステム。
53. 前記データストリーム生成者は、
    前記署名されたデータストリームを受信し、
    署名されたデータストリームごとに、前記削除されるブロックに対応する前記Ｍｅｒｋｌｅ木の葉に相当する頂点の集合を決定し、
    前記Ｍｅｒｋｌｅ木において任意の頂点対が兄弟である場合、該頂点対における２つの頂点を該２つの頂点の親に置き換え、
    前記Ｍｅｒｋｌｅ木において任意の頂点対が兄弟でない場合、該頂点に対応する前記Ｍｅｒｋｌｅ木の値を計算することを特徴とする請求項５２に記載のシステム。
54. 前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項５３に記載の方法。
55. 前記受信者は、前記中間データストリームを受信し、各Ｍｅｒｋｌｅ木の根の値を再計算することを特徴とする請求項５２に記載のシステム。
56. 元データストリームについて、署名したデータストリームから任意のブロックを適応的に削除するプログラムであって、
    前記元データストリームを構成する複数のブロックのそれぞれに署名を行わずに、前記署名されたデータストリームにおいて送信されるデータストリームブロックを決定する工程と、
    中間データストリームを生成することによって、前記署名されたデータストリームにおいてその他のブロックを適応的に削除する工程と、
    前記中間データストリームを受信者に送信して認証させる工程と、
    前記署名されたデータストリームのブロックごとに、前記部分ハッシュ値及び補助ハッシュ値を計算する工程とをコンピュータに実行させ、
    前記中間データストリームは、送信されるデータストリームブロックと、前記削除されるブロックに対する前記補助ハッシュ値とを含み、
    前記補助ハッシュ値は、当該補助ハッシュ値に対応するブロック以外のブロックを用いた算出されるハッシュ値であり、
    前記補助ハッシュ値は、前記署名者から送信されないハッシュ値であり、
    前記部分ハッシュ値は、当該補助ハッシュ値に対応するブロック以外のブロックに対応する部分ハッシュ値、及び、当該部分ハッシュ値に対応するブロックに対応する補助ハッシュ値を用いて算出されるハッシュ値であることを特徴とするプログラム。
57. 前記部分ハッシュ値及び補助ハッシュ値を送信する工程をさらに含むことを特徴とする請求項５６に記載のプログラム。
58. 前記削除されるブロックに対応する前記Ｍｅｒｋｌｅ木の葉に相当する頂点の集合を決定する工程と、
    前記Ｍｅｒｋｌｅ木において任意の頂点対が兄弟である場合、該頂点対における２つの頂点を該２つの頂点の親に置き換える工程と、
    前記Ｍｅｒｋｌｅ木において任意の頂点対が兄弟でない場合、頂点に対応する前記Ｍｅｒｋｌｅ木の値を計算する工程とをコンピュータに実行させることを特徴とする請求項５６に記載のプログラム。
59. 前記中間データストリームは、送信されるデータストリームブロックと、前記削除されるブロックに対応するＭｅｒｋｌｅ木の値とを含むことを特徴とする請求項５８に記載のプログラム。
60. 前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項５８に記載の方法。
61. 前記中間データストリームは、異なるデータストリームから適応的に選択されたデータストリームブロックを含むことを特徴とする請求項５６に記載のプログラム。

Images