損失を適応制御したデータストリームの認証方法及び装置
【課題】電子署名又はメッセージ認証符号のいずれかによる効率的な認証と、送信元から受信者にゼロ以上の中間者を介して送信されたデジタルストリームの検証のための方法、構成要素、及びシステムであって、送信元又は中間者(或いはその両方)は、最終受信者が受信データの真正性と保全性を検証する能力を妨げることなく、データストリームの特定部分を削除することができる。
【解決手段】送信元は、データストリーム全体に一度署名することができるが、それ自身又は中間者が、該ストリームを最終受信者に送信する前に、ストリーム全体に再署名する必要なく該ストリームの特定部分を効率的に削除するのを可能にする。アプリケーションには、特定環境の資源要件に対処するためにさらに処理する必要が多いメディアストリームの署名が含まれる。別のアプリケーションでは、中間者が所定のスロットに入れる広告を選ぶことができる。
【解決手段】送信元は、データストリーム全体に一度署名することができるが、それ自身又は中間者が、該ストリームを最終受信者に送信する前に、ストリーム全体に再署名する必要なく該ストリームの特定部分を効率的に削除するのを可能にする。アプリケーションには、特定環境の資源要件に対処するためにさらに処理する必要が多いメディアストリームの署名が含まれる。別のアプリケーションでは、中間者が所定のスロットに入れる広告を選ぶことができる。
【発明の詳細な説明】
【技術分野】
【0001】
本出願は、2003年8月15日に出願された仮出願第60/495,787号の利益を主張する。本出願は、参照によりこの仮出願の開示を含む。
【0002】
本発明は、データストリーム認証に関し、特に、パケット損失を適応制御した認証方式に関する。
【背景技術】
【0003】
多くの場合、データのストリームに認証情報を付加して、該データが特定の送信元からのものであり、途中で変更されなかったことを受信者に保証することが望ましい。例えば、該データがアプリケーションに提供されている場合、該データが故意又は偶然に破損されていないことは、該アプリケーションにとって重要である。
【0004】
暗号手法には、かかる認証を可能にする2つの従来方法がある。
1.メッセージ認証符号(MAC)
2.電子署名(Digital Signature)
【0005】
MACでは、最初の送信元と最終の受信者の両方が、共有秘密鍵を知っていなければならない。送信者は、元データと秘密鍵とを用いた数学的変換を適用し、タグを生成する。そして受信者は、該データとタグと秘密鍵とを用いた同様の変換を適用し、該データの送信元及び保全性を確認することができる。
【0006】
電子署名では、鍵は、秘密署名鍵と公開検証鍵の2つに分割される。公開検証鍵は、秘密署名鍵を用いて署名されたものを検証するのに使用することができる。鍵は、公開部分から秘密部分を導出できないように分割される。送信者は、元データと秘密署名鍵とを用いた数学的変換を適用し、署名を生成する。そして、受信者は、該データと署名と公開検証鍵とを用いた同様の変換を適用して、送信者の身元とデータの保全性とを確認することができる。
【0007】
電子署名は、MACにはない否認防止特性を有する。すなわち、署名鍵は、非公開であり、署名者が所有していたものであるので、署名者は、文書に署名したことを後に否認することはできない。もちろん、署名の所有者は、秘密署名鍵が敵に盗まれたといつでも主張することはできる。
【0008】
従来の認証方式では、それらの性質のために、送信元又は中間者がデータを変換することは許容されない。文書が署名後に変換されると、検証段階でそれが示され、うまくいかない。
【0009】
しかしながら、多くのアプリケーションにとって、特定の種類の変換を許容することは都合がよいだけではなく、時には必要である。例えば、図1にその原理のハイレベルの図式を示したスケーラブルなビデオ符号化方式は、ストリームの部分集合を復号することができ、その品質が復号量に比例するという特性を有する。このような体系では、ビデオをベース層(base layer)に符号化後、ゼロ以上の「エンハンスメント(enhancement)」層に符号化してもよい。ベース層だけでも、該ストリームを見るのに十分である。エンハンスメント層は、全体的な品質を向上するのに使用する。
【0010】
ところで、資源が制約された環境においては、エンハンスメント層を取り除いてベース層だけを送信しなければならないかもしれない。ストリーム全体が従来の方法で電子署名又は認証されている場合、エンハンスメント層を取り除くことによって、元のタグや署名は無効となる。従って、ストリーム全体を再認証する必要がある。
【0011】
また、サイマルキャスト(simulcast)状態におけるように、いくつかの異なる品質のストリームをつなぎ合わせなければならないことがある。高品質バージョンのストリームと、中品質バージョンのストリームと、低品質バージョンのストリームとがあることがある。ネットワーク資源が利用可能である場合、高品質のストリームを送信してもよいが、ネットワークの輻輳が増す場合、中又は低品質ストリームに変更しなければならないかもしれない。別の状況では、受信者が移動可能で、1つのネットワーク環境を出て、資源制約が異なる別のネットワーク環境に入ろうとしている場合がある。上記のつなぎ合わせ状態は、信号伝送品質が低く、そうでなければ、例えば3つのデータストリームをひとつの大きい層状ストリームとして見て、3つのフレームのうち2つが放棄されていると考えることによって、信号伝送品質は劣化しているような損失状態の特別なケースと考えることができる。
【0012】
さらに、別のアプリケーションには、動的広告がある。送信元は、特定のスロットに表示できる多数の広告を含めてもよい。そして、中間者は、これらの選択肢の中からどの広告を表示したいかを選択することができる。例えば、この選択は、中間者が対象聴衆にとって最もよい広告と考えるものに基づいて行うことができる。広告自体は、中間者や別の者によって作成されることができ、元のフォームで又はハッシュして、送信元に提供されることができる。送信元は、ストリームに署名するときにそれらを入れる。
【0013】
従って、これらの種類の損失を安全な方法で処理できる署名方式が求められている。ここで「安全」とは、最終受信者が、受信したデータが特定の部分が削除されてはいるが、元々有効に署名されたストリームに由来することを、非常に高い確信をもって判定することができることを意味する。さらに、どのブロックを削除するかを適応的・知能的に決定することができる中間者も必要とされている。
【0014】
このような制御損失認証問題に対する従来の解決法の1つは、各パケットを個別に認証するというものである。この解決法には、2つの大きな欠点がある。第一に、電子署名を使用する場合、パケットごとに相当な費用のかかる計算を行わなければならない。第二に、電子署名及びMACのいずれの場合でも、認証情報を各パケットに付加しなければならず、ストリームステムの複数の部分を削除して帯域幅制約を満たす努力を考慮すると、実現可能ではないかもしれない。
【0015】
C.K.Wong及びS.S.Lam著、「Digital Signatures for Flows and Multicasts」、IEEE/ACM Transactions on Networking、7(4):502:513、1999年8月、において、著者は、各データ要素をハッシュして、その結果生成されたハッシュを、Merkle木を使用してダイジェストする解決法を提案している。Merkle木の根が認証される。そして、各データ要素と共に、共通ノード(co-nodes)を送信することにより、受信者がそれなしに認証できるようにする。Wong及びLamは、パケットごとの認証に対処しているので、各パケットは、認証情報を含む。具体的には、
【数1】
を、Merkle木ノードのバイト単位のサイズとし、hを、Merkle木の高さとすれば、送信される各データ要素は、
【数2】
バイトを伴わなければならない。従って、この方法は、制御損失認証問題に対処しておらず、帯域効率が低い。
【0016】
R.Johnson、D.Molnar、D.Song及びD.Wagner著、「Homomorphic Signature Schemes」、RSA 2002、Cryptographer’s Track、において、著者は、編集可能な署名方式を提案している。かかる方式は、データにある特定の変換を行うのを可能にしながらも、受信者が検証できるようにしている。また、係る方式は、署名された文書の部分列を任意に削除できるようにし、検閲用のアプリケーションを有する。n個のメッセージブロックm=m1,…,mnに署名するものとし、nは2の累乗とする。この方式は、最初の秘密鍵kで始まり、O.Goldreich、S.Goldwasser及びS.Micali著、「How to Construct Random Functions」、Journal of the ACM、vol.33、No.4、1986、210〜217頁のGoldreich、Goldwasser及びMicali(GGM)の構造等の、木のような構造を用いて、秘密鍵kを使用してn個の鍵k1,…,knを生成する。それから、メッセージmに署名するために、トリプレット(0,m1,k1),…,(0,mn,kn)をMerkleに似た木においてハッシュし、その根rに署名して署名sを生成する。この木と通常のMerkle木の違いは、内部ハッシュを計算する前に、値1を先頭に付加することである。kを知っていれば、誰でもsを検証することができる。しかしながら、データストリームを検閲するために、kの値は、決して公開されない。代わりに、GGM木の特定の中間値のみが公開される。これらの値は、検閲されないデータ要素に対応する最終鍵kiを導くのに必要な情報に相当する。非検閲ブロックと、中間GGM値と、Merkleに似た木における共通ノードとにより、署名を検証することができる。しかしながら、上記の準同形署名方式(Homomorphic Signature Scheme)は、GGM木を介して、検閲されるデータの機密性を保護するための予防策をとり、検証を可能にするために、全ての非検閲メッセージブロックと、全ての共通ノードと、全てのキーイング情報とを必要とするので、効率的ではない。
【0017】
従って、認証情報を検証する受信者の能力を弱めることなく、また、検閲されるデータの機密性を要求することなく、ストリームの特定のブロックについての制御された削除を可能にする安全な認証方式が求められている。
【発明の開示】
【発明が解決しようとする課題】
【0018】
上記に鑑み、本発明の目的は、(MACを用いた)対称な設定や、(電子署名を用いた)非対称な設定の両方において、適応的データ損失のもとで安全な認証をするための方式であって、送信者、受信者、中間者の計算要件や、それらが通信するチャネルの帯域幅要件に関して効率的である方式を提供することである。
【0019】
つまり、本発明は、以下の問題に対処している。
1.データチャンクが任意に削除された適応的損失(部分列)認証。
2.いくつかのデータストリームをからみ合わせ、一度に1つのデータチャンクだけを所定のストリームから取り出し、その他のストリームからのデータを削除するサイマルキャスト認証。
3.データチャンク全体を完全に削除することもある適応的損失サイマルキャスト認証。
【0020】
本発明は、以下の方式を提供する。
1.部分列認証のための線形方式。
2.サイマルキャスト認証のための線形方式。
3.部分列認証のための木方式。
4.サイマルキャスト認証のための木方式。
【0021】
上記方式は、それぞれ、電子署名及びMACのいずれかを取り入れてもよい。従って、本発明は、8(=4×2)つの方式を暗に提供している。
【0022】
これらの方式は、暗号ハッシュ関数を使用して元ストリームのブロックを処理し、短いダイジェストを生成する。そして、電子署名かMACを該ダイジェストに適用することによって、認証情報を提供する。受信者は、ストリーム全体を与えられた場合、ダイジェストを再計算し、署名を検証することができる。ストリームの特定部分を削除する必要がある場合、削除者は、受信者が効率的にダイジェストを計算するのを可能にする情報を送信する。この設定において、受信者に提供される情報量は、暗号ハッシュ関数の出力サイズに関連し、他の点では、実際のデータストリームと無関係である。
【課題を解決するための手段】
【0023】
本発明の第1の特徴は、部分列認証のための線形方式であって、中間者又は送信元が、任意のブロックを(位置に関係なく)削除しても、受信者が、情報を認証できるようにすることができる。この方式は、2層ハッシュチェーンを計算し、このチェーンのいくつかの値を受信者に提供することを含む。この方式は、受信者が認証情報の検証に遅延を生じる必要がないという意味で、受信者にとってオンラインである。この方式を最適化及び一般化したものでは、r個の第1層ハッシュのバンドルごとに1つの第2層ハッシュが計算される。r=1であれば、この方式は、最初の部分列認証の線形方式である。この方式を改良したものでは、第2層ハッシュを実行する前に、いくつかの第1層ハッシュを1つに集める。その結果、実行する必要のある第2層ハッシュは少なくなる。
【0024】
本発明の第2の特徴は、サイマルキャスト認証のための線形方式であって、中間者又は送信元が、複数のストリームを提供され、どのストリームを送信するかを任意に切り替えても、受信者が、情報を認証できるようにすることができる。この方式は、多層ハッシュチェーンを計算することと、受信者にこのチェーンにおけるいくつかの値を提供することを含む。この方式は、受信者が認証情報の検証に遅延を生じる必要がないという意味で、受信者にとってオンラインである。
【0025】
本発明の第3の特徴は、部分列認証のための木方式であって、中間者又は送信元が、任意のブロックを(位置に関係なく)削除しても、受信者が、情報を認証できるようにすることができる。この方式は、ハッシュ木を計算することと、この木におけるいくつかの値を受信者に提供することを含む。削除されたブロックの(1つよりも大きい)ある部分集合が、ハッシュ木の部分木を構成する場合、このハッシュ化方式は、対応する線形方式よりも、帯域幅に関してより効率的である。この方式は、受信者が全てのブロックを待たないと認証情報を検証できないという意味で、受信者にとってオンラインではない。
【0026】
本発明の第4の特徴は、サイマルキャスト認証のための木方式であって、中間者又は送信元が、複数のストリームを提供され、どのストリームを送信するかを任意に切り替えても、受信者が、情報を認証できるようにすることができる。この方式は、ハッシュ木を計算することと、受信者にこの木におけるいくつかの値を提供することを含む。この方式は、受信者が全てのブロックを待たないと認証情報を検証できないという意味で、受信者にとってオンラインではない。
【0027】
本発明の全ての特徴において、送信者は、始めに、署名される全てのデータを保有しているものとする。メディアが事前記録されている場合のように、ほとんどの場合、このことは問題ではない。ライブストリームの場合において、本発明は、該ストリームを小さいチャンクに分割し、ここに記載の方式を適用する。当業者であれば、本発明の範囲から逸脱することなく変形及び変更が可能であることを理解するであろう。
【0028】
本発明において、中間者がどのブロックを削除するかを適応的及び知能的に決定してもよい状況が可能になる。本発明の方式は、ブロックを削除するいかなるモデルにも容易に適応する。さらに、中間者は、暗号キーイングマテリアルを知っている必要がない。さらにまた、送信元が、中間者にいくつかのハッシュ値を提供するならば、中間者は、暗号関連の計算を行う必要を避けることができる。代わりに、中間者は、望ましいブロックを、削除するブロックのハッシュ情報と一緒に転送するだけでよい。
【0029】
上記の発明方式の全ては、所定のブロックが削除されないという知識を前もって与えられると、そのブロックの第1層ハッシュは実行されないという特性を有する。すなわち、そのブロックだけの第1層ハッシュを、恒等関数(h(x)=x)に置き換えることができる。
【0030】
線形方式及び木を用いた方式の両方とも、データのブロック間の相関関係を利用することができる。例えば、木を用いた方式において、所定のブロックの部分集合が、全てが削除されるか、全てが保持されるという性質を有するならば、これらのブロックは、同じ部分木の全ての葉として特定することができる。所定の部分集合の全てのパケットが削除される場合、その根だけを送信すればよい。しかしながら、この概念は、相関関係が確率的であっても適用される。例えば、所定のブロックが削除されることにより別のブロックが削除される可能性が高くなる場合、これらのブロックもひとまとめにされることになる。同様に、線形方式において、所定の一連のフレームが全て保持されるか削除される場合、これらのフレームを単一ブロック単位として処理し、ハッシュすることができる。従って、一連のフレーム全体が削除される場合、単一のハッシュ値を送信するだけでよい。
【発明を実施するための最良の形態】
【0031】
本発明の方式において、図2の最初の送信者200は、データストリームを認証する責任がある。図に示すように、各送信者200は、メモリ202と双方向通信するプロセッサ201を有する。プロセッサ201は、本発明の方式を実施するためのプログラムコードを実行して、データストリームを生成、送信、受信する。メモリ202は、暗号鍵とプログラムコード、さらに本方式の実施中に使用する中間結果や他の情報を記憶する。通信ネットワーク203が設けられ、それにより送信者は受信者と通信することができる。
【0032】
図3は、受信者のブロック図を示し、受信者は、本発明の一実施形態による通信ネットワークによって、送信者、サーバ、又は中間者からデータストリームを受信する。本発明のシステムは、多数の受信者を含み、受信者は、受信したデータを検証する。各受信者300は、メモリ302と双方向通信するプロセッサ301を有する。プロセッサ301は、本発明の方式を実施するためのプログラムコードを実行して、データストリームを生成、送信、受信する。プログラムコードは、当技術で公知の方法によって生成してもよい。メモリ302は、暗号鍵、プログラムコード、さらに本方式の実施中に使用する中間結果や他の情報を記憶する。
【0033】
通信ネットワーク303が設けられ、それにより送信者と受信者は通信することができる。通信ネットワークは、例えば、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WAN)、及び/又は携帯電話ネットワーク等、各種一般的形態のものでもよい。ネットワークは、有線通信又は無線通信のいずれかを可能にするものであってもよい。
【0034】
図4は、中間者のブロック図を示す。複数の中間者が存在してもよいし、或いは、送信元と中間者が同一であってもよい。中間者と送信元が同一でない場合、中間者は、暗号キーイングマテリアルを持たなくてもよい。送信者用のデータは、送信者又は受信者へ向かう途中に、図4に示す1つ以上の中間者を通過することがある。中間者は、該データに特定の変換を行うことにしてもよい。各中間者400は、メモリ402と双方向通信するプロセッサ401を有する。プロセッサ401は、本発明の方式を実施するためのプログラムコードを実行して、データストリームを生成、送信、受信する。メモリ402は、暗号鍵を記憶していてもよい。
【0035】
図5は、送信者501と、中間者503と、受信者505と、通信ネットワーク502、504とを含む本発明の一実施形態によるシステムのブロック図を示す。図に示すように、送信者501は、元データストリームを、署名と、任意のヘルパー情報と共に、通信ネットワーク502を介して中間者503に送信し、中間者503は、縮小したデータストリームを、署名と、関連するヘルパー情報と共に、通信ネットワーク504を介して受信者505に送信する。
【0036】
上述の変換には、データの特定部分を削除することが含まれる。中間者は、データストリームを変更する場合、受信者が該ストリームに関連する認証情報を検証するのに必要な情報はどれか、もしあれば、判断する。
【0037】
Mは、長さbのn個のブロックに分割することができるメディアストリームを示す。
【数3】
Hは、入力としてbビットのペイロードとνビットの初期ベクトルIVをとり、通常ν<bである場合にνビットの出力を生成する暗号圧縮関数を示す。これらの暗号圧縮関数は、耐衝突性であり、すなわち、一定のIVに関して、H(IV,m1)=H(IV,m2)となるようなm1≠m2である2つの入力m1及びm2を見つけるのは難しい。一定で公知であるIV0と呼ぶ標準IVが存在する。表記を簡潔にするために、下記の説明では、IVをハッシュ関数における独立変数として明記しないが、暗にそこに存在するものとみなすべきである。
【0038】
かかる暗号圧縮関数の例は、SHA−1やMD5に見られる。SHA−1の圧縮関数は、160ビットの出力とIVサイズを有し、一方、MD5の圧縮関数は、128ビットの値で機能する。双方とも、512ビットのペイロードサイズを許容する。このペイロードサイズよりも大きいデータブロックを処理する必要がある場合は、圧縮関数の適用を繰り返す。そのように機能しながらも耐衝突特性を保持する関数は、暗号ハッシュ関数と呼ばれる。簡単にするために、以下において、ペイロード内に収まるデータブロックを処理する場合でも、この用語を用いる。
【0039】
電子署名を伴う方式については、公開鍵のインフラストラクチャが存在し、送信者は、鍵ペア(Pk,Sk)を有するものとする。Skは、メッセージに電子署名を付加するのに使用することができる送信者の秘密署名鍵であり、Pkは、Pkを使用して発行された署名が本物であるかを確認するのに使用することができる送信者の公開検証鍵である。σ(Sk,M)は、署名鍵Skの下のメッセージMの電子署名アルゴリズムを示し、ν(Pk,M,σ)は、検証アルゴリズムを示す。中間者は、署名鍵も検証鍵も知っている必要はない。MACを伴う方式については、最初の送信者Sと最終の受信者Rの両方が、対称鍵を共に知っており、該対称鍵は、中間者に知られる必要がないものとする。
【0040】
本発明の方式は、暗号圧縮関数を含む従来の構成を利用するものである。かかる構成の1つは、以下のように暗号圧縮関数から構成される反復ハッシュ関数である。メッセージMは、長さbのn個のブロックに分割されることができ、Hは、bビットのペイロード及びνビットの出力の暗号圧縮関数とする。Hで定義される反復ハッシュ関数は、値xnである。ここで、
【数4】
【0041】
圧縮関数Hに衝突を見つけるのが難しいとすると、反復ハッシュに衝突を見つけるのは難しいことになる。通常、メッセージに電子的に署名したい場合、反復ハッシュを該メッセージに適用し、その結果生じる出力に署名する。本発明の方法と、システムと、構成要素とは、同様の構成を含むものであるが、検証を補助するために中間値が提供される。
【0042】
他の暗号圧縮関数を含む従来の構成は、Merkle木である。図6は、8個の葉を有するMerkle木を図式的に示している。各葉は、その下のメッセージのハッシュである。各内部ノードは、その子のハッシュを示している。根が署名される。Mは、n個のブロックM=M1…Mnに分割できるものとする。簡単にするために、nは2の累乗とする。本発明の方式は、2以外の累乗を受け入れることができる。ハッシュ関数Hの下のMに対応するMerkle木は、各ノードが特定の値に対応する2分木である。n個の葉が存在し、各葉liは、Miのハッシュ、すなわち、H(IV0,Mi)を持つ。各内部(葉でない)ノードは、その2つの子の値の連結のハッシュに対応する値を持つ。すなわち、頂点νが、子ν1及びν2を持ち、ν1は、値x1を持ち、ν2は、値x2を持つ場合、νに対応する値は、H(IV0,x1 x2)である。
【0043】
Merkle木は、電子署名によく使用され、ダイジェストを形成するメッセージMに対応する木の根に割り当てられた値が署名される。基礎をなす圧縮又はハッシュ関数が耐衝突性である場合、Merkle根の値が同一である2つの異なるメッセージを見つけるのは難しい。
【0044】
本発明は、また、Merkle木における所定の頂点に対する共通ノードという概念を利用している。ある頂点νの共通ノードは、νから根までの経路上にある頂点の直接の兄弟からなる。ある頂点ν及びその共通ノードが与えられると、νから根につながるハッシュ関数の列を計算することができる。
1.部分列認証
【0045】
本発明の線形部分列認証方式では、メッセージから任意のブロックが削除されても、ストリーム認証が可能である。中間ノードにより送信されたブロックが、元メッセージの真の部分列であれば、受信者は、ストリームを認証することができる。
1.1 署名
【0046】
図7は、本発明の一実施形態による基本線形部分列認証方式を示している。メッセージMが与えられると、署名の生成は、「2つのハッシング層」を使用することを除いて、反復ハッシュと同様のパラダイムに従う。
【0047】
一実施形態において、メッセージM=M1M2…Mnが与えられると、本発明は、部分ハッシュ計算値h1,…hnを、以下のように生成する。
【数5】
【0048】
図7に示す方式では、h1,…,hnを計算する過程で、送信されない補助ハッシュ値g1,…,gnを計算する。最初の送信者Sは、(M,σSk(hn))を送信する。IV0の値をIVとして使用して、全てのgi値を計算することができる。
【0049】
或いは、送信者Sは、メッセージブロック〈(M1,hn−1,σSk(hn)),(M2,hn−2),…(Mn,h0)〉と共に、ハッシュ値hiを送信するように決めてもよい。
1.2 署名の更新
【0050】
中間ノードが、k個の任意の位置のメッセージブロックを取り除きたい場合、該中間ノードは、Mと同一であるが、k個のブロックが削除された結果生じる「メッセージ」M’を生成する。受信者は、M’を認証できる必要がある。
【0051】
受信されたn個のブロックのメッセージMが与えられると、中間ノードは、「新しい」ブロックM1’,…,Mn’を計算する。メッセージブロックMn−i+1(最後から始めて、i=1からi=nまで)ごとに、中間ノードは、それに対応する補助ハッシュ及び部分ハッシュを、以下のように計算する。
【数6】
【0052】
ブロックが転送されるか削除されるかにより、中間ノードは、ブロックMiが転送される場合、M’n−i+1=Mn−i+1を計算し、ブロックMiが削除される場合、giを計算する(式(3))。
【0053】
tを、中間ノードが受信者に送信したい最後のメッセージブロックのインデックスとし、Mt’=Mtであり、全てのl>tに関し、Ml’≠Mlとなるようにする。中間ノードは、最終的に、〈M1’,…Mn’σSk(hn),hn−t〉を送信する。
【0054】
ある標準的な符号化をブロックコンテンツに適用して、「メッセージブロック」と「ハッシュ」とを区別しやすいようにする。当業者は、この符号化を実行するのに多数の方法があることを理解するであろう。
【0055】
或いは、オンライン検証を可能にするために、中間ノードは、〈(M1’,hn−1,σSk(hn)),(M2’,hn−2),…(Mn’,h0)〉を送信する。
1.3 検証
【0056】
受信者は、以下のように、M1’,…,Mk’及びhn−tからhnを計算することにより、署名を検証することができる。メッセージブロックM’n−i+1(最後から始めて、i=1からi=nまで)ごとに、受信したブロックが「メッセージブロック」であるか「ハッシュ」であるかによって、受信者は、M’n−i+1が「メッセージブロック」である場合、hi=H(hi−1,H(hi−1,M’n−i+1))を計算し、M’n−i+1が「ハッシュ」である場合、hi=H(hi−1,M’n−i+1))を計算する(式(4))。
【0057】
受信者は、検証アルゴリズムνを用いて、hnの署名を正規のものと確認することができる。
【0058】
別のオンライン検証は、以下のように進む。受信者は、関係式(4)を用いて(M’1,hn−1)から部分ハッシュhnを計算し、部分ハッシュhnの署名を検証する。その後、i=2,…,nについて、(4)を用いて(M’i,hn−i)から部分ハッシュhiを計算し、そのように計算されたハッシュが反復i−1で受信したハッシュ値に一致することを確認する。
1.4 セキュリティ
【0059】
上述のように、基礎をなすハッシュ関数Hが耐衝突性であれば、反復ハッシュ構造は耐衝突性である。具体的に、反復構造に衝突が見つかった場合、ある点で内部衝突が存在しており、ハッシュ関数Hで衝突を見つけることができることになる。敵が非部分列の偽造(すなわち、元メッセージの部分列を取り出すだけでは得られない1対のメッセージ/署名)を考え出すことができた場合、ハッシュ関数の衝突か、基礎をなす署名方式の偽造のいずれかを証明することができることを示すことができる。従って、署名方式が偽造されにくく、ハッシュ関数が衝突しにくいならば、上記に提示した本方式は安全である。
1.5 パフォーマンス
【0060】
中間者は、ブロックを削除する場合、削除するブロックのハッシュを計算するだけでよい。この計算は、公開鍵のステップを含まず、かなり効率的である。実際、SHA−1のようなアルゴリズムの処理能力は、毎秒数百メガビットである。さらに、中間ノードが、計算に関して資源が限られている場合、送信元は、代替的アプローチに従って、中間のhi値を含むことができる。SHA−1の場合、かかる値は、それぞれ20バイトの長さであり、帯域幅オーバーヘッドは、おそらくかなり小さくなるだろう。
【0061】
帯域幅使用とバッファリング/計算との間のトレードオフは、選択的にいくつかの中間のhi値を送信することによって可能になる。受信者が、メッセージブロックをb個まで記憶することができる場合、中間ノードは、b個のメッセージブロックの後にだけハッシュ値hn−bを送信することができる。認証は、hn−bから始めて、上述のように行うことができる。次に、中間ノードは、第2の「バンドル」(次のb個のメッセージブロックとhn−2b)を送信し、該バンドルは、部分ハッシュhn−b,…,hn−2b+1を再計算し、再計算したハッシュ値hn−bが第1のバンドルで受信したものに一致することを確認することによって、認証される。
【0062】
本実施形態の計算は、その時々でハッシュ関数に対し1つの入力ブロックだけが必要であるので、ストリーム全体をメモリに記憶する必要はない。
【0063】
第1の実施形態の方式は、暗号キーイングマテリアルの知識を必要とせずに、任意の数のブロックを削除することを、適応的、知能的に選択することができるという中間者の役割を可能にする。さらに、中間者は、受信者に隣接することができ、損失(すなわちハッシュ情報量)を動的に制御することができる。さらに、認証情報は、受信者によってオンライン形式で検証されることができる。すなわち、受信者は、ストリームを受信しながら認証情報を検証することができるので、いかなる形式の大規模バッファリングも行う必要がない。また、削除されないブロックに関して、第1層ハッシュ計算は必要ない。例えば、MPEG1のフレームやスケーラブルな符号体系のベース層は、故意に削除されない。これらのブロックに関しては、第2層のみが必要である。この場合、該ブロックの第1層ハッシュ関数については、恒等関数h(x)=xに置き換えることができる。同様の精神で、所定の一連のフレームが、全て削除されるか、全て保持される場合、上記の方式は、これらをハッシュ前に単一のブロックとして集めることができるので、さらに一層有益である。
2.部分列認証の効率向上
【0064】
本発明の第2の実施形態は、第2層ハッシュを実行する前に、第1層ハッシュのいくつかを1つに集めることによって、上記の基本線形部分列認証の効率を向上させるものである。その結果、第2の実施形態による方法は、より少ない第2層ハッシュを実行する。SHA−1に付随するもの等の通常の圧縮関数について、ペイロードサイズは64バイトであるが、ダイジェストサイズは20バイトである。その結果、この場合、第2層関数を呼び出す前に、3つのダイジェストを連結することができる。第2の実施形態において、r個のハッシュを1つに集めるものとする。さらに、10進数aに関し、
【数7】
は、a以上の最小の整数を示し、
【数8】
は、a以下の最大の整数を示す。
2.1 署名
【0065】
メッセージMに関し、第2の実施形態による署名の生成は、第1の実施形態の方式と同様のパラダイムに従い、「2つのハッシング層」を使用する。しかしながら、第2の実施形態の方式は、第1の実施形態よりも少ないハッシュを必要とする。図8は、r=3であり、nをrの倍数として、本発明の一実施形態による改良された線形部分列認証方式を示す。この方式において、r個の第1層のハッシュ群が、第2層でハッシュされる。メッセージM=M1M2…Mnが与えられると、第2の実施形態の方式は、
【数9】
として、部分ハッシュ計算値h1,…,hmを、以下のように生成する。
【数10】
【0066】
第1の実施形態の方式と同様に、第2の実施形態の方式は、h1,…,hmを計算する過程で、補助ハッシュ値g1,…,gnを計算するが、それらは送信されない。最初の送信者は、(M,σSk(hm))を送信し、IV0の値をIVとして使用して、全てのgi値を計算することができる。
【0067】
或いは、送信者は、r番目の各メッセージブロック〈(M1,σSk(hm)),(M2),…,(Mr,hm−1),(Mr+1),…,(M2r,hm−2),…(Mn,h0)〉と共に、ハッシュ値hiを送信するようにしてもよい。
2.2 署名の更新
【0068】
ところで、中間ノードが、n−k個の任意の位置のメッセージブロックを取り除かなければならないものとする。該ノードは、その結果、Mと同一であるが、n−k個のブロックが削除された「メッセージ」M’を生成する。受信者は、M’を認証できる必要がある。
【0069】
受信したn個のブロックのメッセージMが与えられると、中間ノードは、「新しい」ブロックM’1,…,M’nを計算する。メッセージブロックMn−i+1(最後から始めて、i=1からi=nまで)ごとに、中間ノードは、それに対応する補助ハッシュ及び部分ハッシュを計算する。
【数11】
【0070】
ブロックが転送されるか削除されるかにより、中間ノードは、ブロックMiが転送される場合、M’n−i+1=Mn−i+1を計算し、または、ブロックMiが削除される場合、giを計算する(式(7))。
【0071】
ハッシュ値hm,…,h1は、署名演算と同じように計算される。中間者は、最終的に、〈M1’…Mn’,σSk(hm)〉を送信する。
【0072】
上記の送信では、検証を行うのに、r個のパケットをバッファリングする必要がある。実際には、rは、非常に小さいものである。SHA−1に基づく方式では、r=3であり、MD−5に基づく方式では、r=4である。
【0073】
或いは、中間ノードは、「新しい」メッセージブロック〈(M1’,σSk(hm)),(M2’),…,(Mr’,hm−1),(Mr+1’),…,(M2r’,hm−2),…,(Mn’,h0)〉と共に、ハッシュ値hiを送信してもよい。
2.3 検証
【0074】
受信者は、以下のように、M’1,…,M’nから、hmを計算することによって、署名を検証することができる。最初に、メッセージブロックM′n−i+1(最後から始めて、i=1からi=nまで)ごとに、受信したブロックが「メッセージブロック」であるか「ハッシュ」であるかによって、受信者は、M′n−i+1が「メッセージブロック」である場合、g’i=H(hi−1,M’n−i+1)を計算し、M’n−i+1が「ハッシュ」である場合、g’i=M’n−i+1を計算する(式(8))。
【0075】
最後に、受信者は、hmを計算する。
【数12】
【0076】
受信者は、検証アルゴリズムνを用いて、hmの署名が正規のものであると確認することができる。
【0077】
オンライン検証を行うには、受信者は、中間ハッシュhiを計算可能である必要がある。そのためには、受信者は、適切なg値を計算できるように、r個のブロックをバッファリングする必要がある。この方式のオンライン検証は、第1の実施形態のものと類似している。
2.4 セキュリティ
【0078】
第1の実施形態と同様に、署名方式が偽造されにくく、ハッシュ関数が衝突しにくいのなら、第2の実施形態の方式は安全である。
2.5 パフォーマンス
【0079】
第1の実施形態と同様に、中間者は、ブロックを削除する場合、削除するブロックのハッシュを計算するだけでよい。
【0080】
第1の実施形態の部分列方式に比べ、第2の実施形態の部分列方式は、r個の第1層ハッシュごとにたった1つの第2層ハッシュが実行されるので、署名の計算及び検証の両方にかかる時間が少ない。rを慎重に選べば(例えば、SHA−1にはr=3、MD−5にはr=4を設定する)、各第2層ハッシュは、圧縮関数を一度呼び出すだけでよい。そのように、第2の実施形態においては、第1の実施形態のn回の呼出しに比べ、第2層において
【数13】
回だけ圧縮関数の呼出しが行われる。
【0081】
第1の実施形態の利点に加え、第2の実施形態の受信者は、各r個のブロックを受信した後に、認証情報を検証することができる。実際には、rは、かなり小さく、およそ2又は3であり、第2層ハッシュの数は、少なくなる。
3. サイマルキャスト認証:多重方式
【0082】
さて、最初の送信者Sが、k個の異なるストリームM(1),M(2),…,M(k)を同時に送信するものとする。各ストリームは、長さbであるn個のブロックM(j)=M1(j),…,Mn(j)からなる。第3の実施形態の方式では、中間ノードは、1つのストリームを選択して、認証された形式で再送できるだけではなく、(ブロック送信中、任意の時点で)適応的に他のストリームに「切り替える」ことができる。もちろん、受信者は、その結果生じたストリームを認証することができなければならない。
3.1 署名
【0083】
図9は、本発明の一実施形態による基本線形サイマルキャスト認証方式を示す。メッセージMが与えられると、署名の生成は、第1及び第2の実施形態と同じアプローチ、すなわち、逆反復ハッシュに従うが、各ストリームの全てのブロックの部分ハッシュを計算する。
【0084】
本発明の第3の実施形態の方式では、M(j)=M1(j),M2(j),…,Mn(j)であるメッセージM(1),M(2),…,M(k)が与えられると、部分ハッシュ計算値h1,…,hnが、以下のように生成される。
【数14】
【0085】
最初の送信者は、σSk(hn)を送信し、次に、M(1),…,M(k)を同時に送信する。実際には、異なるストリームのメッセージブロックは、送信中にインターリーブされる。
3.2 署名の更新
【0086】
中間ノードが、受信したメッセージブロックごとに、異なる可能性のあるストリーム(メッセージ)の選択を望むものとする。例えば、各メッセージが、異なる品質のビデオストリームを符号化している場合、中間ノードは、ネットワークの輻輳状況により、低い又は高い品質を選択しなければならないかもしれない。中間ノードは、種々のストリームの「チャンク」(連続したメッセージブロック)からなる「その結果生じるメッセージ」M’を生成する。中間ノードは、各瞬間に、単一のストリーム(メッセージ)を選んでもよい。本発明は、層状ストリームの可能性を考慮するものであることを理解すべきである。受信者は、M’を認証できる必要がある。
【0087】
受信したn個のブロックのメッセージM(1),…,M(k)が与えられると、中間ノードは、「新しい」ブロックM’1,…,M’nを計算する。(最後から始めて、i=1からi=nまでの)メッセージブロック
【数15】
の集合ごとに、部分ハッシュを計算する。
【数16】
【0088】
次に、ストリームlが選択された場合、1≦l≦k、
【数17】
を計算する。
【0089】
中間ノードは、最後に、〈M’1…M’n,σSk(hn)〉を送信する。
【0090】
或いは、オンライン検証を可能にするために、中間ノードは、
【数18】
を送信する。
3.3 検証
【0091】
受信者は、M’1,…,M’k及びh0=IV0からhnを計算することによって、署名を検証することができる。メッセージブロックM’n−i+1(最後から始めて、i=1からi=nまで)ごとに、M’n−i+1が
【数19】
の形式である場合、
【0092】
受信者は、
【数20】
を計算する。
【0093】
受信者は、検証アルゴリズムνを用いて、hnの署名を正規のものであると確認することができる。
【0094】
その代わりとなるオンライン検証手続は容易である。受信者は、関係式(14)を用いて、(M’1,hn−1)から部分ハッシュhnを計算して、部分ハッシュhnの署名を検証する。その後、i=2,…,nについて、(14)を用いて(M’i,hn−i)から部分ハッシュhiを計算して、そのように計算したハッシュが反復i−1で受信したハッシュ値と一致することを確認する。
3.4 パフォーマンス
【0095】
第1の実施形態の方式の利点に加え、第3の実施形態の方式のハッシュステップは、線形連鎖方式又はMerkle方式のいずれかにより、圧縮関数を用いて反復することができる。
【0096】
Merkle木のような構造を用いて各一連のブロックMi(1),…,Mi(k)をハッシュダウンすることによって、(中間ノードによる)さらに集約的な計算という犠牲を払って、帯域幅を節約することができる。
4. 部分列認証のための木方式
【0097】
本発明の第4の実施形態は、Merkle木を用いて部分列を認証するための方式である。線形部分列認証方式のように、この木を用いた方式は、メッセージから任意のブロックが削除されても、ストリーム認証を可能にする。中間ノードによって送信されたブロックが、元メッセージの真の部分列であれば、受信者は、ストリームを認証することができる。木構造の特徴を利用することによって、木方式は、帯域幅に関し、線形方式よりも効率的である。
4.1 署名
【0098】
図10は、本発明の一実施形態による木を用いた部分列認証方式を示している。第4の実施形態の方式は、メッセージM=M1M2…Mnが与えられると、図6に示すMerkle木を生成する。νが木の根を示し、xが根に対応する値を示すとすると、最初の送信者は、(M,σSk(x))を送信する。
4.2 署名の更新
【0099】
中間者が、k個の任意の位置のメッセージブロックを取り除かなければならない場合、中間者は、その結果、Mと同一であるが、k個のブロックが削除されている「メッセージ」M’を生成する。受信者は、M’を認証できる必要がある。d1,…,dkが、削除されるブロックのインデックスを示すものとし、s1,…,sn−kが、とどまるブロックを示すものとする。受信したn個のブロックメッセージMが与えられると、中間ノードは、対応する認証情報を、以下のように計算する。
1)削除される全てのブロック
【数21】
について、中間者は、最初に、これらのブロックに対応するMerkle木の葉
【数22】
に相当する頂点の集合を求める。
2)Merkle木において任意の頂点対が兄弟である場合、中間者は、それらの2つの頂点の両方を、それらの親に置き換える。
3)中間者は、該集合に兄弟である二つの頂点がなくなるまで、上記の処理を繰り返す。
4)中間者は、この頂点集合を取り出し、それらに対応するMerkle木の値x1,…,xrを計算する。暗号ハッシュ関数は、大域的に計算可能であるので、中間者は、このステップを容易に行うことができる。
【0100】
中間ノードは、最後に、
【数23】
を送信する。
【0101】
本発明の他の実施形態と同様に、標準的な符号化をブロックコンテンツに適用することで、「メッセージブロック」と「ハッシュ」との区別が容易になる。
4.3 検証
【0102】
受信者は、以下のアルゴリズムを用いて、Merkle木の根の値を計算することによって、署名を検証する。
1) 受信した実際のメッセージブロック
【数24】
ごとに、
【数25】
の値を計算する。
2)全てのハッシュyi,…,yn−k,x1,…,xrの集合を考慮する。これらは、それぞれ、Merkle木の頂点の値に相当する。
3)1対の値ごとに、それらが兄弟である頂点に相当する場合、その対をそれらのハッシュ(親ノードに相当する)に置き換える。
4)1つの値だけが残るまで、上記ステップを繰り返す。この値は根である。
【0103】
初期メッセージブロックの全てを有するならば、上記アルゴリズムは、Merkle木の根を計算するための標準アルゴリズムとなる。受信者が、いくつかのハッシュx1,…,xrを受信したときは、これらは、欠けているブロックの部分集合に対して同じアルゴリズムを実行した中間者から来ている。従って、中間者と受信者は、共に、Merkle根の値をもたらすn個の全てのブロックに該アルゴリズムを実行している。これが、上記の計算がMerkle根をもたらす理由である。
【0104】
Merkle根の値により、受信者は、受信した署名を検証することができる。
4.4 セキュリティ
【0105】
上記Merkleハッシュ構造は、基礎をなすハッシュ関数Hが耐衝突性であれば、耐衝突性である。特に、Merkle木に衝突が見つかった場合、ある時点で、内部ノードに衝突が存在することになり、ハッシュ関数Hに衝突を見つけることができることになる。敵が非部分列偽造を考え出す(つまり、元メッセージの部分列を取り出しただけでは得られない1対のメッセージ/署名を考え出す)ことができた場合、ハッシュ関数における衝突か、基礎をなす署名方式の偽造のいずれかを証明することができる。従って、署名方式が偽造されにくく、ハッシュ関数が衝突しにくいなら、第4の実施形態の方式は安全である。
4.5 パフォーマンス
【0106】
中間者がブロックを削除する場合、受信者に、それらのメッセージブロックなしで木のMerkle根を計算するのに十分な数の内部ハッシュを提供する必要がある。中間者は、削除する各ブロックに対してk個のハッシュを必要とし、また、複数対のハッシュを単一のハッシュに置き換える場合は、多くてk−1個のハッシュを必要とする(単一のハッシュにより、2つの値を1つの値に置き換えることによって、総数が1つ減るため)。従って、全計算では、多くて2k−1個のハッシュとなる。中間者によって計算された全ハッシュをtで示す。
【0107】
受信者は、ストリームを受信すると、根を計算する必要がある。全てのメッセージブロックを得た場合、最初に各ブロックをハッシュするのに、2n−1ハッシュ−nが必要であり、また、複数対のハッシュ値を単一のハッシュに置き換える場合、n−1個のハッシュがさらに必要である(単一関数計算により、2つの値を1つの値に置き換えることになり、最後には、たった1つの値が残っているから)。しかしながら、これらのハッシュのうちのtは、中間者によって計算される。従って、受信者は、2n−1−t個のハッシュを計算するだけでよい。
【0108】
この方式における、中間者と受信者との間の全作業は、多くて2n−1個のハッシュである。前の線形方式では、2n個のハッシュが必要であった。
【0109】
帯域幅に関しては、木を用いた方式は、はるかに効率的かもしれない。r≦k個のハッシュだけが最終的に送信される。最良のケースでは、削除されるk個のブロックが全体でMerkle木の部分木の全ての葉を構成する場合、この部分木の根に相当する単一の値のみが送信され、すなわち、r=1である。最悪のケースでは、兄弟であるブロック対がない場合、帯域幅要件は、線形の場合とまったく同じであり、k個のハッシュ値を送信する必要がある。
5. サイマルキャスト認証のための木方式
【0110】
本発明の第5の実施形態は、送信の各ステップで、1つのデータブロックが1つのストリームから選択される、複数の平行ストリームを認証するための木を用いた方式である。第3の実施形態の線形多重設定におけるように、最初の送信者Sは、k個の異なるストリームM(1),M(2),…,M(k)を同時に送信するものとする。各ストリームは、長さbのn個のブロックM(j)=M1(j),…,Mn(j)からなる。本方式では、中間ノードは、1つのストリームを選択して、認証された形式で再送することができるだけでなく、(ブロック送信中の任意の時点で)適応的に他のストリームに「切り替える」ことができる。もちろん、受信者は、その結果生じるストリームを認証することができる。第4の実施形態の部分列認証のための木を用いた方式におけるように、第5の実施形態の方式は、帯域幅に関して類似線形方式よりも効率的となるように、木構造の特定の特徴を利用する。他方、第4の実施形態の木構造のように、第5の実施形態の方式はオンライン検証には適していない。それどころか、受信者は、全てのパケットを待たないと検証することができない。実際には、遅延は、ストリームを適当なサイズのセグメントに分割して、各セグメントを別々に認証することによって、小さくすることができる。
5.1 署名
【0111】
k個の異なるストリームM(1),M(2),…,M(k)が与えられると、第5の実施形態の方式の署名生成は、以下のように進む。
1)最初に、署名者は、ストリームごとに別個のMerkle木を生成する。v(1),…,v(k)を、木のk個の根を示すものとし、x(1),…,x(k)を、これらの根にそれぞれ対応する値を示すものとする。
2)次に、署名者は、x=H(IV,x(1),…,x(k))を計算する。ここで、ハッシュ関数Hは、同じくMerkle木構造を用いて計算することができる。
3)最後に、署名者は、(M,σSk(x))を送信する。
5.2 署名の更新
【0112】
さて、中間ノードは、受信したメッセージブロックごとに、異なる可能性のあるストリーム(メッセージ)を選択しなければならないものとする。例えば、各メッセージが、異なる品質のビデオストリームを符号化している場合、中間ノードは、ネットワークの輻輳状況によって、低い又は高い品質を選択しなければならないかもしれない。その結果、異なるストリームの「チャンク」(連続するメッセージブロック)からなる「メッセージ」M’を生成する。受信者は、M’を認証できる必要がある。
【0113】
受信者が、xiの値のそれぞれを正確に計算できる場合、署名を検証することができる。従って、中間者は、これらの値を計算するのに必要な情報をユーザに提供するだけでよい。各Merkle木を別々に処理することによって、中間者は、第4の実施形態のMerkle方式においてそうしたように、必要な値の集合を計算することができる。中間者は、これらの値を受信者に送信し、受信者は、xiの値を計算し、その結果、認証情報を検証することができる。
【0114】
具体的には、1≦i≦kである各iに関し、ks(i)が、ストリームM(i)から実際に送信されるブロックの数を示すものとする。ストリームM(i)に関しては、
【数26】
が、含まれるブロックのインデックスを示すものとする。M′(i)を、これらのブロックを示すものとする。
【数27】
【0115】
削除するブロックのインデックスについては、1≦i≦kである各iに関し、kd(i)が、ストリームM(i)から実際に削除されるブロックの数を示すものとする。ストリームM(i)に関し、
【数28】
が、削除されるブロックのインデックスを示すものとする。
【0116】
第4の実施形態の木方式におけるように、中間者は、各ストリームM(i)に関して、受信者が検証するのに必要な値を、以下のように計算する。
1)削除される全てのブロック
【数29】
に関し、中間者は、最初に、これらのブロックに対応するMerkle木の葉
【数30】
に相当する頂点の集合を求める。
2)そこで、Merkle木において任意の頂点対が兄弟である場合、中間者は、それら2つの頂点の両方を、それらの親、すなわち、兄弟に対応する値の連結のハッシュと置き換える。
3)中間者は、該集合に兄弟である2つの頂点がなくなるまで、上記の処理を繰り返す。
4)中間者は、この集合の頂点を取り出し、それらに対応するMerkle木の値X(i)=x1(i),…,xr(i)を計算する。暗号ハッシュ関数は、大域的に計算可能であるので、中間者は、このステップを容易に行うことができる。
【0117】
中間ノードは、最後に、以下の情報を送信する。
【数31】
【0118】
ストリームは、適切な順序で送信される。すなわち、各M’(i)からのブロックは、受信者がストリームを見ることができるようにインターリーブしてもよい。受信者がメッセージブロックとハッシュ値とを区別できるように、標準的な符号化をブロックコンテンツに適用する。
5.3 検証
【0119】
受信者は、最初に、各Merkle木の根の値を計算し、その後、これらの値をハッシュして、署名を検証する。各iに行われる以下のアルゴリズムを用いて、この目的を達する。
1)最初に、受信者は、受信した実際のメッセージブロック
【数32】
ごとに、
【数33】
の値を計算する。
2)上述のように、前ステップで計算された全てのハッシュの集合と、該送信において受信された集合X(1),…,X(k)に含まれるハッシュ値とを考慮する。
3)1対の値ごとに、該対が兄弟である頂点に相当するものであるならば、該対をそれらのハッシュ(Merkle木の親ノードに相当する)に置き換える。
4)1つの値だけが残るまで上記ステップを繰り返す。この値は根x(i)である。
【0120】
初期メッセージブロックの全てを得ているならば、上記のアルゴリズムは、Merkle木の根を計算するための標準アルゴリズムとなる。受信者が、いくつかのハッシュx1(i),…,xr(i)を受信するときは、欠けているブロックの部分集合に対して同じアルゴリズムを実行している中間者からそれらは来ている。従って、中間者と受信者は、共に、Merkle根の値をもたらすn個のブロックの全てについて該アルゴリズムを実行している。これが、上記の計算がMerkle根をもたらす理由である。
【0121】
受信者は、Merkle根の値、x(1),…,x(k)によって、x=H(IV,x(1),…,x(k))を計算し、受信した署名を検証することができる。
【0122】
図11は、本発明の第5の実施形態の署名及び検証を示すものであり、4つのストリームと4つのメッセージブロックを有する例である。図に示すように、4つのストリームM(1),M(2),M(3),M(4)は、それぞれ、4つのブロックからなる。黒い葉は、実際に送信されるメッセージブロックを示す。残りは、削除される。影付きの頂点は、カバーを示す。すなわち、これらの頂点に相当する値は、受信者に送信される。4つのMerkle木の根は、それぞれ、x(1),x(2),x(3),x(4)である。最終的な根の値xは、Merkle根x(1),x(2),x(3),x(4)をハッシュすることによって計算される。このハッシュは、Merkleのような形式でも実行することができる。最後に、値xが実際に署名される。この方式において、6つのハッシュ値だけが受信者に送信される。線形サイマルキャスト方式では、12のハッシュが送信されていた(送信される1ブロックごとに3つ)。従って、削除されるブロックをひとかたまりにするたびに、節約が達成される。例えば、図11において、ストリームM(4)のブロックは、全て削除される。その結果、対応するMerkle木の根x(4)を送信するだけでよい。
【0123】
また、Merkle根は、それ自体、Merkleのような構造においてハッシュされるので、さらに最適化する余地がある。具体的には、Merkle根が、さらに大きい木において兄弟である2つの完全な部分木について、全てのブロックを削除するものとする。その結果、2つのMerkle根を送信する代わりに、それらのハッシュを送信することができる。
5.4 セキュリティ
【0124】
第4の実施形態と同様に、第5の実施形態は、署名方式が偽造されにくく、ハッシュ関数が衝突しにくいならば、安全である。従って、上記に示した本発明は安全である。
5.5 パフォーマンス
【0125】
第5実施形態のパフォーマンスは、木を用いた部分列方式と線形サイマルキャスト方式とに関する分析を拡張することによって、分析することができる。
【0126】
上述の全ての実施形態において、特定のペイロードサイズと特定のIVとを用いたハッシュ関数が用いられる。連鎖構造は、ある既存の出力を取り出し、次のブロックのIVとして用いる傾向がある。さらなる実施形態では、IVとして現時点の出力をロードする代わりに、現時点の出力を次のペイロードに連結することができる。
【0127】
本発明の線形方式と木方式を組み合わせて、ハイブリッドの解決法を得ることで、有益なトレードオフをもたらすことができる。さらなる実施形態では、ある方式が、各ストリームM(i)を、長さbのブロックのセグメントに分割することによって始まる。次に、木方式を、全てのストリームの第1のセグメントに適用して、Merkle根x1を計算し、次に第2のセグメントに関する根、というふうに、全てのセグメントが処理されるまで計算する。こうして、Merkle根
【数34】
が得られる。これらの根の1つ1つに署名するかわりに、上記に説明した木方式におけるように、根は、線形方式を用いて結合される。従って、受信者が、b個のブロックをバッファリングすることができる場合、検証は、「オンライン」でできる。さらに、b個のブロックのセグメントごとに送信されるハッシュの数は、削除されるブロックの数よりもはるかに少なくてもよいので(最悪のケースでは同じであるが)、通信オーバーヘッドは、簡単な線形方式に比べて減少する。同様のアプローチを、部分列認証にも採用することができる。このハイブリッド方法により、バッファ領域を、通信オーバーヘッドとトレードすることができる。
【0128】
さらなる実施形態においては、線形方式を各ストリームに適用し、その結果についてMerkle木を計算する。
【0129】
上記の実施形態は、バイナリのMerkle木を使用しているが、その構造は、一般的な木に適用することができる。所定のブロックが、同様の性質を有する、すなわち、全てが削除されるか、又は、全てが保持されるかのいずれかである場合、それらを1つにまとめることは、さらに有益であるかもしれない。
【0130】
ブロック間に相関がある場合、木を用いた方式において、これらのブロックをひとまとめにすることは、理にかなっている。例えば、あるブロック群が、全て削除されるか、全て保持されるかのいずれかである場合、これらのブロックが、部分木の全ての葉を構成するようにすることは有益である。従って、パケットを削除する場合、その部分木の根を送信するだけでよい。
【0131】
さらに、Merkle木構造を最適化することができる。一実施形態において、ストリームの1つが、他のものよりも使用される可能性が高い場合、この優先ストリームが根に近い(例えば、おそらく右下にある)不均衡なMerkle木を使用することは都合がよい。前述のハイブリッド方式に関連して、ストリームは、優先順位をつけられるので、高い優先度のストリームは、連鎖の最終値に近くなる。この順序付けは、層状ストリームを使用する場合、特に理にかなっている。かかる場合、検証において、根に到達するためのハッシュステップがより少なくて済む。
【0132】
MPEGストリームのIフレームや、スケーラブルに符号化されたストリームのベース層など、削除すべきではないブロックが存在する。署名者は、削除されないブロックについて、最初の第1層ハッシュを直接計算しなくて済む。線形方式では、ハッシュ層は2つある。ブロックが削除されない場合、第1層のハッシュを計算する必要はなく、代わりに、第2層だけを計算すればよい。
【0133】
本発明の方式は、2つの段階を有すると解釈することができる。第1の段階では、各データブロックをハッシュするのに便利な方法を見つける。第2の段階では、ハッシュに署名する。そうする理由は、ブロックが削除される場合、それを完全な形で再送する必要がないからである。その代わりに、第1の段階で計算されたハッシュのみを送信する。署名は、ハッシュに行われたものとみなすことができるので、受信者は、この情報で十分検証できる。
【0134】
すでに述べたように、本発明は、制御損失のケースに対処するものであり、すなわち、送信者は、特定のブロックを故意に削除する。もちろん、多くの実際のアプリケーションにおいて、非制御の損失事態に対処しなければならないかもしれない。例えば、UDPのように、トランスポートプロトコルが信頼できない場合や、無線ネットワークのように、環境が損失動作に左右される場合、このような事態は起こりうる。本発明は、パケットが削除された場合、送信されるハッシュを複製することによって、非制御損失に対処するのに使用することができる。
【0135】
消去符号等の順方向誤り訂正(FEC)技術を本発明のハッシュに適用することによって、複製する必要なしに非制御損失事態に対処することが可能である。このアプローチは、異なる受信者が異なるパケットを失っているが、同一の誤り訂正情報を与えられるマルチキャスト設定において、特に有益であるかもしれない。このアプローチで考慮するべきことは、受信者が復号処理を行わなければならず、オンライン形式で認証情報を検証する能力を犠牲にしなければならない可能性があることである。
【0136】
さらに、本発明の方式は、認証情報(すなわち、ハッシュ出力)に対する順方向誤り訂正量を適応的に選択できる中間者を必要とする。換言すると、送信元に、どれくらいの損失が起こるかを予測させて、十分な認証順方向誤り訂正情報を含めて対処させるのではなく、送信元は、認証順方向誤り訂正情報をまったく含めないことにすることができ、代わりに、中間者が、認証順方向誤り訂正情報を動的に含めて、ストリームを認証できる確率をさらに高めることができるようにすることができる。
【0137】
中間者は、適応的・知能的制御損失に加え、順方向誤り訂正により対処する非制御損失の両方を考慮する方式の不可欠な部分となる。例えば、Merkle木構造において、受信者にとって、(単なる葉ノードではなく)中間ノードを回復すれば十分かもしれない。かかる場合、中間者は、順方向誤り訂正情報を提供することにして、認証に必要な(おそらく内部)ノードを回復できるようにすることができ、おそらくより少ない順方向誤り訂正情報で済む。
【0138】
中間者が、複数の受信者に対して、例えば、受信者がそれぞれ見ている品質について様々なリソースの制約があるために、同一ストリームの様々なバージョンを送信している場合、中間者は、作業労力を再利用することができる。具体的に、中間者は、第1層ハッシュを記憶し再利用することができる。その結果、多くても、完全な第1層ハッシュの集合を計算するだけでよい。
【0139】
この線に沿って、送信元と中間者との間で作業は再利用することができる。すなわち、送信元は、認証を補助するのに必要なハッシュ計算値を、中間者に提供することができる。従って、中間者は、暗号的性質の作業を実行する必要がない。代わりに、どのブロックを削除するかを決め、それに対応する送信する認証情報を選択することができる。
【0140】
本発明の別のアプリケーションは、ストリームに広告を挿入し、広告を選択することである。中間者又は他の者は、広告、又は、例えばMerkle木を用いてハッシュした広告のハッシュを、送信元に提供する。すると送信元は、ストリームにプレースホルダーとしてMerkleハッシュを含めて、中間者が使用したい広告を選ぶことができるようにする。もちろん、この概念は、必ずしも広告者に限定されるものではない。
【0141】
本発明の中心は、情報を認証することにあるが、上記の方式は、暗号方式に関連して使用することもできる。ただし、受信者が、他の多くのブロックの復号又は存在を必要とせずに、所定のブロックを復号することができるように、該方式が構成されていればである。2つのブロック暗号暗号化モードにより、この方法は容易になる。1つは、カウンタモード暗号化であり、他方は、電子コードブック(ECB)暗号化である。或いは、ストリーム暗号を用いることもできる。ただし、受信者は、受信したストリームの1部分ではなく、元ストリームのサイズに比例した作業を実行する必要があるかもしれない。受信者が、復号する中間情報を受信しているならば、連鎖又はフィードバックモード(暗号ブロック連鎖方式(CBC)、出力フィードバック(OFB)等)を使用することが可能かもしれない。かかる情報は、中間IVや、実際の暗号文ブロックを含んでいてもよい。さらに他の方法は、該モードを混合するものである。すなわち、削除されない大きいセグメントに関しては、連鎖又はフィードバックモードを使用することができ、一方、その他のブロックに関しては、カウンタモード又はECBモードを使用することができる。例えば、MPEGストリームにおいては、Iフレームは、故意に削除されることはないので別に処理し、CBCモードを使用して暗号化することができる。同様のことが、スケーラブルな符号体系のベース層にも言える。
【0142】
上記において、本発明を様々な実施形態について詳細に説明してきたが、当業者であれば、これらの実施形態を本発明の範囲及び精神から逸脱することなく、変更することができることを理解するであろう。従って、本発明は、添付の請求項の範囲によってのみ限定されるものとみなされるべきである。
【図面の簡単な説明】
【0143】
【図1】スケーラブルなコーダのハイレベル図を示す。
【図2】送信者又は送信元のブロック図を示す。
【図3】受信者のブロック図を示す。
【図4】中間者のブロック図を示す。
【図5】送信者、受信者、及び中間者を含むシステムのブロック図を示す。
【図6】8個の葉を持つMerkle木を示す。
【図7】本発明の一実施形態による、基本線形部分列認証方式を示す。
【図8】本発明の一実施形態による、r=3であり、nがrの倍数である、最適化された線形部分列認証方式を示す。
【図9】本発明の一実施形態による、基本線形サイマルキャスト認証方式を示す。
【図10】本発明の一実施形態による、木を用いた部分列認証方式を示す。
【図11】本発明の一実施形態による、木を用いたサイマルキャスト認証方式を示す。
【技術分野】
【0001】
本出願は、2003年8月15日に出願された仮出願第60/495,787号の利益を主張する。本出願は、参照によりこの仮出願の開示を含む。
【0002】
本発明は、データストリーム認証に関し、特に、パケット損失を適応制御した認証方式に関する。
【背景技術】
【0003】
多くの場合、データのストリームに認証情報を付加して、該データが特定の送信元からのものであり、途中で変更されなかったことを受信者に保証することが望ましい。例えば、該データがアプリケーションに提供されている場合、該データが故意又は偶然に破損されていないことは、該アプリケーションにとって重要である。
【0004】
暗号手法には、かかる認証を可能にする2つの従来方法がある。
1.メッセージ認証符号(MAC)
2.電子署名(Digital Signature)
【0005】
MACでは、最初の送信元と最終の受信者の両方が、共有秘密鍵を知っていなければならない。送信者は、元データと秘密鍵とを用いた数学的変換を適用し、タグを生成する。そして受信者は、該データとタグと秘密鍵とを用いた同様の変換を適用し、該データの送信元及び保全性を確認することができる。
【0006】
電子署名では、鍵は、秘密署名鍵と公開検証鍵の2つに分割される。公開検証鍵は、秘密署名鍵を用いて署名されたものを検証するのに使用することができる。鍵は、公開部分から秘密部分を導出できないように分割される。送信者は、元データと秘密署名鍵とを用いた数学的変換を適用し、署名を生成する。そして、受信者は、該データと署名と公開検証鍵とを用いた同様の変換を適用して、送信者の身元とデータの保全性とを確認することができる。
【0007】
電子署名は、MACにはない否認防止特性を有する。すなわち、署名鍵は、非公開であり、署名者が所有していたものであるので、署名者は、文書に署名したことを後に否認することはできない。もちろん、署名の所有者は、秘密署名鍵が敵に盗まれたといつでも主張することはできる。
【0008】
従来の認証方式では、それらの性質のために、送信元又は中間者がデータを変換することは許容されない。文書が署名後に変換されると、検証段階でそれが示され、うまくいかない。
【0009】
しかしながら、多くのアプリケーションにとって、特定の種類の変換を許容することは都合がよいだけではなく、時には必要である。例えば、図1にその原理のハイレベルの図式を示したスケーラブルなビデオ符号化方式は、ストリームの部分集合を復号することができ、その品質が復号量に比例するという特性を有する。このような体系では、ビデオをベース層(base layer)に符号化後、ゼロ以上の「エンハンスメント(enhancement)」層に符号化してもよい。ベース層だけでも、該ストリームを見るのに十分である。エンハンスメント層は、全体的な品質を向上するのに使用する。
【0010】
ところで、資源が制約された環境においては、エンハンスメント層を取り除いてベース層だけを送信しなければならないかもしれない。ストリーム全体が従来の方法で電子署名又は認証されている場合、エンハンスメント層を取り除くことによって、元のタグや署名は無効となる。従って、ストリーム全体を再認証する必要がある。
【0011】
また、サイマルキャスト(simulcast)状態におけるように、いくつかの異なる品質のストリームをつなぎ合わせなければならないことがある。高品質バージョンのストリームと、中品質バージョンのストリームと、低品質バージョンのストリームとがあることがある。ネットワーク資源が利用可能である場合、高品質のストリームを送信してもよいが、ネットワークの輻輳が増す場合、中又は低品質ストリームに変更しなければならないかもしれない。別の状況では、受信者が移動可能で、1つのネットワーク環境を出て、資源制約が異なる別のネットワーク環境に入ろうとしている場合がある。上記のつなぎ合わせ状態は、信号伝送品質が低く、そうでなければ、例えば3つのデータストリームをひとつの大きい層状ストリームとして見て、3つのフレームのうち2つが放棄されていると考えることによって、信号伝送品質は劣化しているような損失状態の特別なケースと考えることができる。
【0012】
さらに、別のアプリケーションには、動的広告がある。送信元は、特定のスロットに表示できる多数の広告を含めてもよい。そして、中間者は、これらの選択肢の中からどの広告を表示したいかを選択することができる。例えば、この選択は、中間者が対象聴衆にとって最もよい広告と考えるものに基づいて行うことができる。広告自体は、中間者や別の者によって作成されることができ、元のフォームで又はハッシュして、送信元に提供されることができる。送信元は、ストリームに署名するときにそれらを入れる。
【0013】
従って、これらの種類の損失を安全な方法で処理できる署名方式が求められている。ここで「安全」とは、最終受信者が、受信したデータが特定の部分が削除されてはいるが、元々有効に署名されたストリームに由来することを、非常に高い確信をもって判定することができることを意味する。さらに、どのブロックを削除するかを適応的・知能的に決定することができる中間者も必要とされている。
【0014】
このような制御損失認証問題に対する従来の解決法の1つは、各パケットを個別に認証するというものである。この解決法には、2つの大きな欠点がある。第一に、電子署名を使用する場合、パケットごとに相当な費用のかかる計算を行わなければならない。第二に、電子署名及びMACのいずれの場合でも、認証情報を各パケットに付加しなければならず、ストリームステムの複数の部分を削除して帯域幅制約を満たす努力を考慮すると、実現可能ではないかもしれない。
【0015】
C.K.Wong及びS.S.Lam著、「Digital Signatures for Flows and Multicasts」、IEEE/ACM Transactions on Networking、7(4):502:513、1999年8月、において、著者は、各データ要素をハッシュして、その結果生成されたハッシュを、Merkle木を使用してダイジェストする解決法を提案している。Merkle木の根が認証される。そして、各データ要素と共に、共通ノード(co-nodes)を送信することにより、受信者がそれなしに認証できるようにする。Wong及びLamは、パケットごとの認証に対処しているので、各パケットは、認証情報を含む。具体的には、
【数1】
を、Merkle木ノードのバイト単位のサイズとし、hを、Merkle木の高さとすれば、送信される各データ要素は、
【数2】
バイトを伴わなければならない。従って、この方法は、制御損失認証問題に対処しておらず、帯域効率が低い。
【0016】
R.Johnson、D.Molnar、D.Song及びD.Wagner著、「Homomorphic Signature Schemes」、RSA 2002、Cryptographer’s Track、において、著者は、編集可能な署名方式を提案している。かかる方式は、データにある特定の変換を行うのを可能にしながらも、受信者が検証できるようにしている。また、係る方式は、署名された文書の部分列を任意に削除できるようにし、検閲用のアプリケーションを有する。n個のメッセージブロックm=m1,…,mnに署名するものとし、nは2の累乗とする。この方式は、最初の秘密鍵kで始まり、O.Goldreich、S.Goldwasser及びS.Micali著、「How to Construct Random Functions」、Journal of the ACM、vol.33、No.4、1986、210〜217頁のGoldreich、Goldwasser及びMicali(GGM)の構造等の、木のような構造を用いて、秘密鍵kを使用してn個の鍵k1,…,knを生成する。それから、メッセージmに署名するために、トリプレット(0,m1,k1),…,(0,mn,kn)をMerkleに似た木においてハッシュし、その根rに署名して署名sを生成する。この木と通常のMerkle木の違いは、内部ハッシュを計算する前に、値1を先頭に付加することである。kを知っていれば、誰でもsを検証することができる。しかしながら、データストリームを検閲するために、kの値は、決して公開されない。代わりに、GGM木の特定の中間値のみが公開される。これらの値は、検閲されないデータ要素に対応する最終鍵kiを導くのに必要な情報に相当する。非検閲ブロックと、中間GGM値と、Merkleに似た木における共通ノードとにより、署名を検証することができる。しかしながら、上記の準同形署名方式(Homomorphic Signature Scheme)は、GGM木を介して、検閲されるデータの機密性を保護するための予防策をとり、検証を可能にするために、全ての非検閲メッセージブロックと、全ての共通ノードと、全てのキーイング情報とを必要とするので、効率的ではない。
【0017】
従って、認証情報を検証する受信者の能力を弱めることなく、また、検閲されるデータの機密性を要求することなく、ストリームの特定のブロックについての制御された削除を可能にする安全な認証方式が求められている。
【発明の開示】
【発明が解決しようとする課題】
【0018】
上記に鑑み、本発明の目的は、(MACを用いた)対称な設定や、(電子署名を用いた)非対称な設定の両方において、適応的データ損失のもとで安全な認証をするための方式であって、送信者、受信者、中間者の計算要件や、それらが通信するチャネルの帯域幅要件に関して効率的である方式を提供することである。
【0019】
つまり、本発明は、以下の問題に対処している。
1.データチャンクが任意に削除された適応的損失(部分列)認証。
2.いくつかのデータストリームをからみ合わせ、一度に1つのデータチャンクだけを所定のストリームから取り出し、その他のストリームからのデータを削除するサイマルキャスト認証。
3.データチャンク全体を完全に削除することもある適応的損失サイマルキャスト認証。
【0020】
本発明は、以下の方式を提供する。
1.部分列認証のための線形方式。
2.サイマルキャスト認証のための線形方式。
3.部分列認証のための木方式。
4.サイマルキャスト認証のための木方式。
【0021】
上記方式は、それぞれ、電子署名及びMACのいずれかを取り入れてもよい。従って、本発明は、8(=4×2)つの方式を暗に提供している。
【0022】
これらの方式は、暗号ハッシュ関数を使用して元ストリームのブロックを処理し、短いダイジェストを生成する。そして、電子署名かMACを該ダイジェストに適用することによって、認証情報を提供する。受信者は、ストリーム全体を与えられた場合、ダイジェストを再計算し、署名を検証することができる。ストリームの特定部分を削除する必要がある場合、削除者は、受信者が効率的にダイジェストを計算するのを可能にする情報を送信する。この設定において、受信者に提供される情報量は、暗号ハッシュ関数の出力サイズに関連し、他の点では、実際のデータストリームと無関係である。
【課題を解決するための手段】
【0023】
本発明の第1の特徴は、部分列認証のための線形方式であって、中間者又は送信元が、任意のブロックを(位置に関係なく)削除しても、受信者が、情報を認証できるようにすることができる。この方式は、2層ハッシュチェーンを計算し、このチェーンのいくつかの値を受信者に提供することを含む。この方式は、受信者が認証情報の検証に遅延を生じる必要がないという意味で、受信者にとってオンラインである。この方式を最適化及び一般化したものでは、r個の第1層ハッシュのバンドルごとに1つの第2層ハッシュが計算される。r=1であれば、この方式は、最初の部分列認証の線形方式である。この方式を改良したものでは、第2層ハッシュを実行する前に、いくつかの第1層ハッシュを1つに集める。その結果、実行する必要のある第2層ハッシュは少なくなる。
【0024】
本発明の第2の特徴は、サイマルキャスト認証のための線形方式であって、中間者又は送信元が、複数のストリームを提供され、どのストリームを送信するかを任意に切り替えても、受信者が、情報を認証できるようにすることができる。この方式は、多層ハッシュチェーンを計算することと、受信者にこのチェーンにおけるいくつかの値を提供することを含む。この方式は、受信者が認証情報の検証に遅延を生じる必要がないという意味で、受信者にとってオンラインである。
【0025】
本発明の第3の特徴は、部分列認証のための木方式であって、中間者又は送信元が、任意のブロックを(位置に関係なく)削除しても、受信者が、情報を認証できるようにすることができる。この方式は、ハッシュ木を計算することと、この木におけるいくつかの値を受信者に提供することを含む。削除されたブロックの(1つよりも大きい)ある部分集合が、ハッシュ木の部分木を構成する場合、このハッシュ化方式は、対応する線形方式よりも、帯域幅に関してより効率的である。この方式は、受信者が全てのブロックを待たないと認証情報を検証できないという意味で、受信者にとってオンラインではない。
【0026】
本発明の第4の特徴は、サイマルキャスト認証のための木方式であって、中間者又は送信元が、複数のストリームを提供され、どのストリームを送信するかを任意に切り替えても、受信者が、情報を認証できるようにすることができる。この方式は、ハッシュ木を計算することと、受信者にこの木におけるいくつかの値を提供することを含む。この方式は、受信者が全てのブロックを待たないと認証情報を検証できないという意味で、受信者にとってオンラインではない。
【0027】
本発明の全ての特徴において、送信者は、始めに、署名される全てのデータを保有しているものとする。メディアが事前記録されている場合のように、ほとんどの場合、このことは問題ではない。ライブストリームの場合において、本発明は、該ストリームを小さいチャンクに分割し、ここに記載の方式を適用する。当業者であれば、本発明の範囲から逸脱することなく変形及び変更が可能であることを理解するであろう。
【0028】
本発明において、中間者がどのブロックを削除するかを適応的及び知能的に決定してもよい状況が可能になる。本発明の方式は、ブロックを削除するいかなるモデルにも容易に適応する。さらに、中間者は、暗号キーイングマテリアルを知っている必要がない。さらにまた、送信元が、中間者にいくつかのハッシュ値を提供するならば、中間者は、暗号関連の計算を行う必要を避けることができる。代わりに、中間者は、望ましいブロックを、削除するブロックのハッシュ情報と一緒に転送するだけでよい。
【0029】
上記の発明方式の全ては、所定のブロックが削除されないという知識を前もって与えられると、そのブロックの第1層ハッシュは実行されないという特性を有する。すなわち、そのブロックだけの第1層ハッシュを、恒等関数(h(x)=x)に置き換えることができる。
【0030】
線形方式及び木を用いた方式の両方とも、データのブロック間の相関関係を利用することができる。例えば、木を用いた方式において、所定のブロックの部分集合が、全てが削除されるか、全てが保持されるという性質を有するならば、これらのブロックは、同じ部分木の全ての葉として特定することができる。所定の部分集合の全てのパケットが削除される場合、その根だけを送信すればよい。しかしながら、この概念は、相関関係が確率的であっても適用される。例えば、所定のブロックが削除されることにより別のブロックが削除される可能性が高くなる場合、これらのブロックもひとまとめにされることになる。同様に、線形方式において、所定の一連のフレームが全て保持されるか削除される場合、これらのフレームを単一ブロック単位として処理し、ハッシュすることができる。従って、一連のフレーム全体が削除される場合、単一のハッシュ値を送信するだけでよい。
【発明を実施するための最良の形態】
【0031】
本発明の方式において、図2の最初の送信者200は、データストリームを認証する責任がある。図に示すように、各送信者200は、メモリ202と双方向通信するプロセッサ201を有する。プロセッサ201は、本発明の方式を実施するためのプログラムコードを実行して、データストリームを生成、送信、受信する。メモリ202は、暗号鍵とプログラムコード、さらに本方式の実施中に使用する中間結果や他の情報を記憶する。通信ネットワーク203が設けられ、それにより送信者は受信者と通信することができる。
【0032】
図3は、受信者のブロック図を示し、受信者は、本発明の一実施形態による通信ネットワークによって、送信者、サーバ、又は中間者からデータストリームを受信する。本発明のシステムは、多数の受信者を含み、受信者は、受信したデータを検証する。各受信者300は、メモリ302と双方向通信するプロセッサ301を有する。プロセッサ301は、本発明の方式を実施するためのプログラムコードを実行して、データストリームを生成、送信、受信する。プログラムコードは、当技術で公知の方法によって生成してもよい。メモリ302は、暗号鍵、プログラムコード、さらに本方式の実施中に使用する中間結果や他の情報を記憶する。
【0033】
通信ネットワーク303が設けられ、それにより送信者と受信者は通信することができる。通信ネットワークは、例えば、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WAN)、及び/又は携帯電話ネットワーク等、各種一般的形態のものでもよい。ネットワークは、有線通信又は無線通信のいずれかを可能にするものであってもよい。
【0034】
図4は、中間者のブロック図を示す。複数の中間者が存在してもよいし、或いは、送信元と中間者が同一であってもよい。中間者と送信元が同一でない場合、中間者は、暗号キーイングマテリアルを持たなくてもよい。送信者用のデータは、送信者又は受信者へ向かう途中に、図4に示す1つ以上の中間者を通過することがある。中間者は、該データに特定の変換を行うことにしてもよい。各中間者400は、メモリ402と双方向通信するプロセッサ401を有する。プロセッサ401は、本発明の方式を実施するためのプログラムコードを実行して、データストリームを生成、送信、受信する。メモリ402は、暗号鍵を記憶していてもよい。
【0035】
図5は、送信者501と、中間者503と、受信者505と、通信ネットワーク502、504とを含む本発明の一実施形態によるシステムのブロック図を示す。図に示すように、送信者501は、元データストリームを、署名と、任意のヘルパー情報と共に、通信ネットワーク502を介して中間者503に送信し、中間者503は、縮小したデータストリームを、署名と、関連するヘルパー情報と共に、通信ネットワーク504を介して受信者505に送信する。
【0036】
上述の変換には、データの特定部分を削除することが含まれる。中間者は、データストリームを変更する場合、受信者が該ストリームに関連する認証情報を検証するのに必要な情報はどれか、もしあれば、判断する。
【0037】
Mは、長さbのn個のブロックに分割することができるメディアストリームを示す。
【数3】
Hは、入力としてbビットのペイロードとνビットの初期ベクトルIVをとり、通常ν<bである場合にνビットの出力を生成する暗号圧縮関数を示す。これらの暗号圧縮関数は、耐衝突性であり、すなわち、一定のIVに関して、H(IV,m1)=H(IV,m2)となるようなm1≠m2である2つの入力m1及びm2を見つけるのは難しい。一定で公知であるIV0と呼ぶ標準IVが存在する。表記を簡潔にするために、下記の説明では、IVをハッシュ関数における独立変数として明記しないが、暗にそこに存在するものとみなすべきである。
【0038】
かかる暗号圧縮関数の例は、SHA−1やMD5に見られる。SHA−1の圧縮関数は、160ビットの出力とIVサイズを有し、一方、MD5の圧縮関数は、128ビットの値で機能する。双方とも、512ビットのペイロードサイズを許容する。このペイロードサイズよりも大きいデータブロックを処理する必要がある場合は、圧縮関数の適用を繰り返す。そのように機能しながらも耐衝突特性を保持する関数は、暗号ハッシュ関数と呼ばれる。簡単にするために、以下において、ペイロード内に収まるデータブロックを処理する場合でも、この用語を用いる。
【0039】
電子署名を伴う方式については、公開鍵のインフラストラクチャが存在し、送信者は、鍵ペア(Pk,Sk)を有するものとする。Skは、メッセージに電子署名を付加するのに使用することができる送信者の秘密署名鍵であり、Pkは、Pkを使用して発行された署名が本物であるかを確認するのに使用することができる送信者の公開検証鍵である。σ(Sk,M)は、署名鍵Skの下のメッセージMの電子署名アルゴリズムを示し、ν(Pk,M,σ)は、検証アルゴリズムを示す。中間者は、署名鍵も検証鍵も知っている必要はない。MACを伴う方式については、最初の送信者Sと最終の受信者Rの両方が、対称鍵を共に知っており、該対称鍵は、中間者に知られる必要がないものとする。
【0040】
本発明の方式は、暗号圧縮関数を含む従来の構成を利用するものである。かかる構成の1つは、以下のように暗号圧縮関数から構成される反復ハッシュ関数である。メッセージMは、長さbのn個のブロックに分割されることができ、Hは、bビットのペイロード及びνビットの出力の暗号圧縮関数とする。Hで定義される反復ハッシュ関数は、値xnである。ここで、
【数4】
【0041】
圧縮関数Hに衝突を見つけるのが難しいとすると、反復ハッシュに衝突を見つけるのは難しいことになる。通常、メッセージに電子的に署名したい場合、反復ハッシュを該メッセージに適用し、その結果生じる出力に署名する。本発明の方法と、システムと、構成要素とは、同様の構成を含むものであるが、検証を補助するために中間値が提供される。
【0042】
他の暗号圧縮関数を含む従来の構成は、Merkle木である。図6は、8個の葉を有するMerkle木を図式的に示している。各葉は、その下のメッセージのハッシュである。各内部ノードは、その子のハッシュを示している。根が署名される。Mは、n個のブロックM=M1…Mnに分割できるものとする。簡単にするために、nは2の累乗とする。本発明の方式は、2以外の累乗を受け入れることができる。ハッシュ関数Hの下のMに対応するMerkle木は、各ノードが特定の値に対応する2分木である。n個の葉が存在し、各葉liは、Miのハッシュ、すなわち、H(IV0,Mi)を持つ。各内部(葉でない)ノードは、その2つの子の値の連結のハッシュに対応する値を持つ。すなわち、頂点νが、子ν1及びν2を持ち、ν1は、値x1を持ち、ν2は、値x2を持つ場合、νに対応する値は、H(IV0,x1 x2)である。
【0043】
Merkle木は、電子署名によく使用され、ダイジェストを形成するメッセージMに対応する木の根に割り当てられた値が署名される。基礎をなす圧縮又はハッシュ関数が耐衝突性である場合、Merkle根の値が同一である2つの異なるメッセージを見つけるのは難しい。
【0044】
本発明は、また、Merkle木における所定の頂点に対する共通ノードという概念を利用している。ある頂点νの共通ノードは、νから根までの経路上にある頂点の直接の兄弟からなる。ある頂点ν及びその共通ノードが与えられると、νから根につながるハッシュ関数の列を計算することができる。
1.部分列認証
【0045】
本発明の線形部分列認証方式では、メッセージから任意のブロックが削除されても、ストリーム認証が可能である。中間ノードにより送信されたブロックが、元メッセージの真の部分列であれば、受信者は、ストリームを認証することができる。
1.1 署名
【0046】
図7は、本発明の一実施形態による基本線形部分列認証方式を示している。メッセージMが与えられると、署名の生成は、「2つのハッシング層」を使用することを除いて、反復ハッシュと同様のパラダイムに従う。
【0047】
一実施形態において、メッセージM=M1M2…Mnが与えられると、本発明は、部分ハッシュ計算値h1,…hnを、以下のように生成する。
【数5】
【0048】
図7に示す方式では、h1,…,hnを計算する過程で、送信されない補助ハッシュ値g1,…,gnを計算する。最初の送信者Sは、(M,σSk(hn))を送信する。IV0の値をIVとして使用して、全てのgi値を計算することができる。
【0049】
或いは、送信者Sは、メッセージブロック〈(M1,hn−1,σSk(hn)),(M2,hn−2),…(Mn,h0)〉と共に、ハッシュ値hiを送信するように決めてもよい。
1.2 署名の更新
【0050】
中間ノードが、k個の任意の位置のメッセージブロックを取り除きたい場合、該中間ノードは、Mと同一であるが、k個のブロックが削除された結果生じる「メッセージ」M’を生成する。受信者は、M’を認証できる必要がある。
【0051】
受信されたn個のブロックのメッセージMが与えられると、中間ノードは、「新しい」ブロックM1’,…,Mn’を計算する。メッセージブロックMn−i+1(最後から始めて、i=1からi=nまで)ごとに、中間ノードは、それに対応する補助ハッシュ及び部分ハッシュを、以下のように計算する。
【数6】
【0052】
ブロックが転送されるか削除されるかにより、中間ノードは、ブロックMiが転送される場合、M’n−i+1=Mn−i+1を計算し、ブロックMiが削除される場合、giを計算する(式(3))。
【0053】
tを、中間ノードが受信者に送信したい最後のメッセージブロックのインデックスとし、Mt’=Mtであり、全てのl>tに関し、Ml’≠Mlとなるようにする。中間ノードは、最終的に、〈M1’,…Mn’σSk(hn),hn−t〉を送信する。
【0054】
ある標準的な符号化をブロックコンテンツに適用して、「メッセージブロック」と「ハッシュ」とを区別しやすいようにする。当業者は、この符号化を実行するのに多数の方法があることを理解するであろう。
【0055】
或いは、オンライン検証を可能にするために、中間ノードは、〈(M1’,hn−1,σSk(hn)),(M2’,hn−2),…(Mn’,h0)〉を送信する。
1.3 検証
【0056】
受信者は、以下のように、M1’,…,Mk’及びhn−tからhnを計算することにより、署名を検証することができる。メッセージブロックM’n−i+1(最後から始めて、i=1からi=nまで)ごとに、受信したブロックが「メッセージブロック」であるか「ハッシュ」であるかによって、受信者は、M’n−i+1が「メッセージブロック」である場合、hi=H(hi−1,H(hi−1,M’n−i+1))を計算し、M’n−i+1が「ハッシュ」である場合、hi=H(hi−1,M’n−i+1))を計算する(式(4))。
【0057】
受信者は、検証アルゴリズムνを用いて、hnの署名を正規のものと確認することができる。
【0058】
別のオンライン検証は、以下のように進む。受信者は、関係式(4)を用いて(M’1,hn−1)から部分ハッシュhnを計算し、部分ハッシュhnの署名を検証する。その後、i=2,…,nについて、(4)を用いて(M’i,hn−i)から部分ハッシュhiを計算し、そのように計算されたハッシュが反復i−1で受信したハッシュ値に一致することを確認する。
1.4 セキュリティ
【0059】
上述のように、基礎をなすハッシュ関数Hが耐衝突性であれば、反復ハッシュ構造は耐衝突性である。具体的に、反復構造に衝突が見つかった場合、ある点で内部衝突が存在しており、ハッシュ関数Hで衝突を見つけることができることになる。敵が非部分列の偽造(すなわち、元メッセージの部分列を取り出すだけでは得られない1対のメッセージ/署名)を考え出すことができた場合、ハッシュ関数の衝突か、基礎をなす署名方式の偽造のいずれかを証明することができることを示すことができる。従って、署名方式が偽造されにくく、ハッシュ関数が衝突しにくいならば、上記に提示した本方式は安全である。
1.5 パフォーマンス
【0060】
中間者は、ブロックを削除する場合、削除するブロックのハッシュを計算するだけでよい。この計算は、公開鍵のステップを含まず、かなり効率的である。実際、SHA−1のようなアルゴリズムの処理能力は、毎秒数百メガビットである。さらに、中間ノードが、計算に関して資源が限られている場合、送信元は、代替的アプローチに従って、中間のhi値を含むことができる。SHA−1の場合、かかる値は、それぞれ20バイトの長さであり、帯域幅オーバーヘッドは、おそらくかなり小さくなるだろう。
【0061】
帯域幅使用とバッファリング/計算との間のトレードオフは、選択的にいくつかの中間のhi値を送信することによって可能になる。受信者が、メッセージブロックをb個まで記憶することができる場合、中間ノードは、b個のメッセージブロックの後にだけハッシュ値hn−bを送信することができる。認証は、hn−bから始めて、上述のように行うことができる。次に、中間ノードは、第2の「バンドル」(次のb個のメッセージブロックとhn−2b)を送信し、該バンドルは、部分ハッシュhn−b,…,hn−2b+1を再計算し、再計算したハッシュ値hn−bが第1のバンドルで受信したものに一致することを確認することによって、認証される。
【0062】
本実施形態の計算は、その時々でハッシュ関数に対し1つの入力ブロックだけが必要であるので、ストリーム全体をメモリに記憶する必要はない。
【0063】
第1の実施形態の方式は、暗号キーイングマテリアルの知識を必要とせずに、任意の数のブロックを削除することを、適応的、知能的に選択することができるという中間者の役割を可能にする。さらに、中間者は、受信者に隣接することができ、損失(すなわちハッシュ情報量)を動的に制御することができる。さらに、認証情報は、受信者によってオンライン形式で検証されることができる。すなわち、受信者は、ストリームを受信しながら認証情報を検証することができるので、いかなる形式の大規模バッファリングも行う必要がない。また、削除されないブロックに関して、第1層ハッシュ計算は必要ない。例えば、MPEG1のフレームやスケーラブルな符号体系のベース層は、故意に削除されない。これらのブロックに関しては、第2層のみが必要である。この場合、該ブロックの第1層ハッシュ関数については、恒等関数h(x)=xに置き換えることができる。同様の精神で、所定の一連のフレームが、全て削除されるか、全て保持される場合、上記の方式は、これらをハッシュ前に単一のブロックとして集めることができるので、さらに一層有益である。
2.部分列認証の効率向上
【0064】
本発明の第2の実施形態は、第2層ハッシュを実行する前に、第1層ハッシュのいくつかを1つに集めることによって、上記の基本線形部分列認証の効率を向上させるものである。その結果、第2の実施形態による方法は、より少ない第2層ハッシュを実行する。SHA−1に付随するもの等の通常の圧縮関数について、ペイロードサイズは64バイトであるが、ダイジェストサイズは20バイトである。その結果、この場合、第2層関数を呼び出す前に、3つのダイジェストを連結することができる。第2の実施形態において、r個のハッシュを1つに集めるものとする。さらに、10進数aに関し、
【数7】
は、a以上の最小の整数を示し、
【数8】
は、a以下の最大の整数を示す。
2.1 署名
【0065】
メッセージMに関し、第2の実施形態による署名の生成は、第1の実施形態の方式と同様のパラダイムに従い、「2つのハッシング層」を使用する。しかしながら、第2の実施形態の方式は、第1の実施形態よりも少ないハッシュを必要とする。図8は、r=3であり、nをrの倍数として、本発明の一実施形態による改良された線形部分列認証方式を示す。この方式において、r個の第1層のハッシュ群が、第2層でハッシュされる。メッセージM=M1M2…Mnが与えられると、第2の実施形態の方式は、
【数9】
として、部分ハッシュ計算値h1,…,hmを、以下のように生成する。
【数10】
【0066】
第1の実施形態の方式と同様に、第2の実施形態の方式は、h1,…,hmを計算する過程で、補助ハッシュ値g1,…,gnを計算するが、それらは送信されない。最初の送信者は、(M,σSk(hm))を送信し、IV0の値をIVとして使用して、全てのgi値を計算することができる。
【0067】
或いは、送信者は、r番目の各メッセージブロック〈(M1,σSk(hm)),(M2),…,(Mr,hm−1),(Mr+1),…,(M2r,hm−2),…(Mn,h0)〉と共に、ハッシュ値hiを送信するようにしてもよい。
2.2 署名の更新
【0068】
ところで、中間ノードが、n−k個の任意の位置のメッセージブロックを取り除かなければならないものとする。該ノードは、その結果、Mと同一であるが、n−k個のブロックが削除された「メッセージ」M’を生成する。受信者は、M’を認証できる必要がある。
【0069】
受信したn個のブロックのメッセージMが与えられると、中間ノードは、「新しい」ブロックM’1,…,M’nを計算する。メッセージブロックMn−i+1(最後から始めて、i=1からi=nまで)ごとに、中間ノードは、それに対応する補助ハッシュ及び部分ハッシュを計算する。
【数11】
【0070】
ブロックが転送されるか削除されるかにより、中間ノードは、ブロックMiが転送される場合、M’n−i+1=Mn−i+1を計算し、または、ブロックMiが削除される場合、giを計算する(式(7))。
【0071】
ハッシュ値hm,…,h1は、署名演算と同じように計算される。中間者は、最終的に、〈M1’…Mn’,σSk(hm)〉を送信する。
【0072】
上記の送信では、検証を行うのに、r個のパケットをバッファリングする必要がある。実際には、rは、非常に小さいものである。SHA−1に基づく方式では、r=3であり、MD−5に基づく方式では、r=4である。
【0073】
或いは、中間ノードは、「新しい」メッセージブロック〈(M1’,σSk(hm)),(M2’),…,(Mr’,hm−1),(Mr+1’),…,(M2r’,hm−2),…,(Mn’,h0)〉と共に、ハッシュ値hiを送信してもよい。
2.3 検証
【0074】
受信者は、以下のように、M’1,…,M’nから、hmを計算することによって、署名を検証することができる。最初に、メッセージブロックM′n−i+1(最後から始めて、i=1からi=nまで)ごとに、受信したブロックが「メッセージブロック」であるか「ハッシュ」であるかによって、受信者は、M′n−i+1が「メッセージブロック」である場合、g’i=H(hi−1,M’n−i+1)を計算し、M’n−i+1が「ハッシュ」である場合、g’i=M’n−i+1を計算する(式(8))。
【0075】
最後に、受信者は、hmを計算する。
【数12】
【0076】
受信者は、検証アルゴリズムνを用いて、hmの署名が正規のものであると確認することができる。
【0077】
オンライン検証を行うには、受信者は、中間ハッシュhiを計算可能である必要がある。そのためには、受信者は、適切なg値を計算できるように、r個のブロックをバッファリングする必要がある。この方式のオンライン検証は、第1の実施形態のものと類似している。
2.4 セキュリティ
【0078】
第1の実施形態と同様に、署名方式が偽造されにくく、ハッシュ関数が衝突しにくいのなら、第2の実施形態の方式は安全である。
2.5 パフォーマンス
【0079】
第1の実施形態と同様に、中間者は、ブロックを削除する場合、削除するブロックのハッシュを計算するだけでよい。
【0080】
第1の実施形態の部分列方式に比べ、第2の実施形態の部分列方式は、r個の第1層ハッシュごとにたった1つの第2層ハッシュが実行されるので、署名の計算及び検証の両方にかかる時間が少ない。rを慎重に選べば(例えば、SHA−1にはr=3、MD−5にはr=4を設定する)、各第2層ハッシュは、圧縮関数を一度呼び出すだけでよい。そのように、第2の実施形態においては、第1の実施形態のn回の呼出しに比べ、第2層において
【数13】
回だけ圧縮関数の呼出しが行われる。
【0081】
第1の実施形態の利点に加え、第2の実施形態の受信者は、各r個のブロックを受信した後に、認証情報を検証することができる。実際には、rは、かなり小さく、およそ2又は3であり、第2層ハッシュの数は、少なくなる。
3. サイマルキャスト認証:多重方式
【0082】
さて、最初の送信者Sが、k個の異なるストリームM(1),M(2),…,M(k)を同時に送信するものとする。各ストリームは、長さbであるn個のブロックM(j)=M1(j),…,Mn(j)からなる。第3の実施形態の方式では、中間ノードは、1つのストリームを選択して、認証された形式で再送できるだけではなく、(ブロック送信中、任意の時点で)適応的に他のストリームに「切り替える」ことができる。もちろん、受信者は、その結果生じたストリームを認証することができなければならない。
3.1 署名
【0083】
図9は、本発明の一実施形態による基本線形サイマルキャスト認証方式を示す。メッセージMが与えられると、署名の生成は、第1及び第2の実施形態と同じアプローチ、すなわち、逆反復ハッシュに従うが、各ストリームの全てのブロックの部分ハッシュを計算する。
【0084】
本発明の第3の実施形態の方式では、M(j)=M1(j),M2(j),…,Mn(j)であるメッセージM(1),M(2),…,M(k)が与えられると、部分ハッシュ計算値h1,…,hnが、以下のように生成される。
【数14】
【0085】
最初の送信者は、σSk(hn)を送信し、次に、M(1),…,M(k)を同時に送信する。実際には、異なるストリームのメッセージブロックは、送信中にインターリーブされる。
3.2 署名の更新
【0086】
中間ノードが、受信したメッセージブロックごとに、異なる可能性のあるストリーム(メッセージ)の選択を望むものとする。例えば、各メッセージが、異なる品質のビデオストリームを符号化している場合、中間ノードは、ネットワークの輻輳状況により、低い又は高い品質を選択しなければならないかもしれない。中間ノードは、種々のストリームの「チャンク」(連続したメッセージブロック)からなる「その結果生じるメッセージ」M’を生成する。中間ノードは、各瞬間に、単一のストリーム(メッセージ)を選んでもよい。本発明は、層状ストリームの可能性を考慮するものであることを理解すべきである。受信者は、M’を認証できる必要がある。
【0087】
受信したn個のブロックのメッセージM(1),…,M(k)が与えられると、中間ノードは、「新しい」ブロックM’1,…,M’nを計算する。(最後から始めて、i=1からi=nまでの)メッセージブロック
【数15】
の集合ごとに、部分ハッシュを計算する。
【数16】
【0088】
次に、ストリームlが選択された場合、1≦l≦k、
【数17】
を計算する。
【0089】
中間ノードは、最後に、〈M’1…M’n,σSk(hn)〉を送信する。
【0090】
或いは、オンライン検証を可能にするために、中間ノードは、
【数18】
を送信する。
3.3 検証
【0091】
受信者は、M’1,…,M’k及びh0=IV0からhnを計算することによって、署名を検証することができる。メッセージブロックM’n−i+1(最後から始めて、i=1からi=nまで)ごとに、M’n−i+1が
【数19】
の形式である場合、
【0092】
受信者は、
【数20】
を計算する。
【0093】
受信者は、検証アルゴリズムνを用いて、hnの署名を正規のものであると確認することができる。
【0094】
その代わりとなるオンライン検証手続は容易である。受信者は、関係式(14)を用いて、(M’1,hn−1)から部分ハッシュhnを計算して、部分ハッシュhnの署名を検証する。その後、i=2,…,nについて、(14)を用いて(M’i,hn−i)から部分ハッシュhiを計算して、そのように計算したハッシュが反復i−1で受信したハッシュ値と一致することを確認する。
3.4 パフォーマンス
【0095】
第1の実施形態の方式の利点に加え、第3の実施形態の方式のハッシュステップは、線形連鎖方式又はMerkle方式のいずれかにより、圧縮関数を用いて反復することができる。
【0096】
Merkle木のような構造を用いて各一連のブロックMi(1),…,Mi(k)をハッシュダウンすることによって、(中間ノードによる)さらに集約的な計算という犠牲を払って、帯域幅を節約することができる。
4. 部分列認証のための木方式
【0097】
本発明の第4の実施形態は、Merkle木を用いて部分列を認証するための方式である。線形部分列認証方式のように、この木を用いた方式は、メッセージから任意のブロックが削除されても、ストリーム認証を可能にする。中間ノードによって送信されたブロックが、元メッセージの真の部分列であれば、受信者は、ストリームを認証することができる。木構造の特徴を利用することによって、木方式は、帯域幅に関し、線形方式よりも効率的である。
4.1 署名
【0098】
図10は、本発明の一実施形態による木を用いた部分列認証方式を示している。第4の実施形態の方式は、メッセージM=M1M2…Mnが与えられると、図6に示すMerkle木を生成する。νが木の根を示し、xが根に対応する値を示すとすると、最初の送信者は、(M,σSk(x))を送信する。
4.2 署名の更新
【0099】
中間者が、k個の任意の位置のメッセージブロックを取り除かなければならない場合、中間者は、その結果、Mと同一であるが、k個のブロックが削除されている「メッセージ」M’を生成する。受信者は、M’を認証できる必要がある。d1,…,dkが、削除されるブロックのインデックスを示すものとし、s1,…,sn−kが、とどまるブロックを示すものとする。受信したn個のブロックメッセージMが与えられると、中間ノードは、対応する認証情報を、以下のように計算する。
1)削除される全てのブロック
【数21】
について、中間者は、最初に、これらのブロックに対応するMerkle木の葉
【数22】
に相当する頂点の集合を求める。
2)Merkle木において任意の頂点対が兄弟である場合、中間者は、それらの2つの頂点の両方を、それらの親に置き換える。
3)中間者は、該集合に兄弟である二つの頂点がなくなるまで、上記の処理を繰り返す。
4)中間者は、この頂点集合を取り出し、それらに対応するMerkle木の値x1,…,xrを計算する。暗号ハッシュ関数は、大域的に計算可能であるので、中間者は、このステップを容易に行うことができる。
【0100】
中間ノードは、最後に、
【数23】
を送信する。
【0101】
本発明の他の実施形態と同様に、標準的な符号化をブロックコンテンツに適用することで、「メッセージブロック」と「ハッシュ」との区別が容易になる。
4.3 検証
【0102】
受信者は、以下のアルゴリズムを用いて、Merkle木の根の値を計算することによって、署名を検証する。
1) 受信した実際のメッセージブロック
【数24】
ごとに、
【数25】
の値を計算する。
2)全てのハッシュyi,…,yn−k,x1,…,xrの集合を考慮する。これらは、それぞれ、Merkle木の頂点の値に相当する。
3)1対の値ごとに、それらが兄弟である頂点に相当する場合、その対をそれらのハッシュ(親ノードに相当する)に置き換える。
4)1つの値だけが残るまで、上記ステップを繰り返す。この値は根である。
【0103】
初期メッセージブロックの全てを有するならば、上記アルゴリズムは、Merkle木の根を計算するための標準アルゴリズムとなる。受信者が、いくつかのハッシュx1,…,xrを受信したときは、これらは、欠けているブロックの部分集合に対して同じアルゴリズムを実行した中間者から来ている。従って、中間者と受信者は、共に、Merkle根の値をもたらすn個の全てのブロックに該アルゴリズムを実行している。これが、上記の計算がMerkle根をもたらす理由である。
【0104】
Merkle根の値により、受信者は、受信した署名を検証することができる。
4.4 セキュリティ
【0105】
上記Merkleハッシュ構造は、基礎をなすハッシュ関数Hが耐衝突性であれば、耐衝突性である。特に、Merkle木に衝突が見つかった場合、ある時点で、内部ノードに衝突が存在することになり、ハッシュ関数Hに衝突を見つけることができることになる。敵が非部分列偽造を考え出す(つまり、元メッセージの部分列を取り出しただけでは得られない1対のメッセージ/署名を考え出す)ことができた場合、ハッシュ関数における衝突か、基礎をなす署名方式の偽造のいずれかを証明することができる。従って、署名方式が偽造されにくく、ハッシュ関数が衝突しにくいなら、第4の実施形態の方式は安全である。
4.5 パフォーマンス
【0106】
中間者がブロックを削除する場合、受信者に、それらのメッセージブロックなしで木のMerkle根を計算するのに十分な数の内部ハッシュを提供する必要がある。中間者は、削除する各ブロックに対してk個のハッシュを必要とし、また、複数対のハッシュを単一のハッシュに置き換える場合は、多くてk−1個のハッシュを必要とする(単一のハッシュにより、2つの値を1つの値に置き換えることによって、総数が1つ減るため)。従って、全計算では、多くて2k−1個のハッシュとなる。中間者によって計算された全ハッシュをtで示す。
【0107】
受信者は、ストリームを受信すると、根を計算する必要がある。全てのメッセージブロックを得た場合、最初に各ブロックをハッシュするのに、2n−1ハッシュ−nが必要であり、また、複数対のハッシュ値を単一のハッシュに置き換える場合、n−1個のハッシュがさらに必要である(単一関数計算により、2つの値を1つの値に置き換えることになり、最後には、たった1つの値が残っているから)。しかしながら、これらのハッシュのうちのtは、中間者によって計算される。従って、受信者は、2n−1−t個のハッシュを計算するだけでよい。
【0108】
この方式における、中間者と受信者との間の全作業は、多くて2n−1個のハッシュである。前の線形方式では、2n個のハッシュが必要であった。
【0109】
帯域幅に関しては、木を用いた方式は、はるかに効率的かもしれない。r≦k個のハッシュだけが最終的に送信される。最良のケースでは、削除されるk個のブロックが全体でMerkle木の部分木の全ての葉を構成する場合、この部分木の根に相当する単一の値のみが送信され、すなわち、r=1である。最悪のケースでは、兄弟であるブロック対がない場合、帯域幅要件は、線形の場合とまったく同じであり、k個のハッシュ値を送信する必要がある。
5. サイマルキャスト認証のための木方式
【0110】
本発明の第5の実施形態は、送信の各ステップで、1つのデータブロックが1つのストリームから選択される、複数の平行ストリームを認証するための木を用いた方式である。第3の実施形態の線形多重設定におけるように、最初の送信者Sは、k個の異なるストリームM(1),M(2),…,M(k)を同時に送信するものとする。各ストリームは、長さbのn個のブロックM(j)=M1(j),…,Mn(j)からなる。本方式では、中間ノードは、1つのストリームを選択して、認証された形式で再送することができるだけでなく、(ブロック送信中の任意の時点で)適応的に他のストリームに「切り替える」ことができる。もちろん、受信者は、その結果生じるストリームを認証することができる。第4の実施形態の部分列認証のための木を用いた方式におけるように、第5の実施形態の方式は、帯域幅に関して類似線形方式よりも効率的となるように、木構造の特定の特徴を利用する。他方、第4の実施形態の木構造のように、第5の実施形態の方式はオンライン検証には適していない。それどころか、受信者は、全てのパケットを待たないと検証することができない。実際には、遅延は、ストリームを適当なサイズのセグメントに分割して、各セグメントを別々に認証することによって、小さくすることができる。
5.1 署名
【0111】
k個の異なるストリームM(1),M(2),…,M(k)が与えられると、第5の実施形態の方式の署名生成は、以下のように進む。
1)最初に、署名者は、ストリームごとに別個のMerkle木を生成する。v(1),…,v(k)を、木のk個の根を示すものとし、x(1),…,x(k)を、これらの根にそれぞれ対応する値を示すものとする。
2)次に、署名者は、x=H(IV,x(1),…,x(k))を計算する。ここで、ハッシュ関数Hは、同じくMerkle木構造を用いて計算することができる。
3)最後に、署名者は、(M,σSk(x))を送信する。
5.2 署名の更新
【0112】
さて、中間ノードは、受信したメッセージブロックごとに、異なる可能性のあるストリーム(メッセージ)を選択しなければならないものとする。例えば、各メッセージが、異なる品質のビデオストリームを符号化している場合、中間ノードは、ネットワークの輻輳状況によって、低い又は高い品質を選択しなければならないかもしれない。その結果、異なるストリームの「チャンク」(連続するメッセージブロック)からなる「メッセージ」M’を生成する。受信者は、M’を認証できる必要がある。
【0113】
受信者が、xiの値のそれぞれを正確に計算できる場合、署名を検証することができる。従って、中間者は、これらの値を計算するのに必要な情報をユーザに提供するだけでよい。各Merkle木を別々に処理することによって、中間者は、第4の実施形態のMerkle方式においてそうしたように、必要な値の集合を計算することができる。中間者は、これらの値を受信者に送信し、受信者は、xiの値を計算し、その結果、認証情報を検証することができる。
【0114】
具体的には、1≦i≦kである各iに関し、ks(i)が、ストリームM(i)から実際に送信されるブロックの数を示すものとする。ストリームM(i)に関しては、
【数26】
が、含まれるブロックのインデックスを示すものとする。M′(i)を、これらのブロックを示すものとする。
【数27】
【0115】
削除するブロックのインデックスについては、1≦i≦kである各iに関し、kd(i)が、ストリームM(i)から実際に削除されるブロックの数を示すものとする。ストリームM(i)に関し、
【数28】
が、削除されるブロックのインデックスを示すものとする。
【0116】
第4の実施形態の木方式におけるように、中間者は、各ストリームM(i)に関して、受信者が検証するのに必要な値を、以下のように計算する。
1)削除される全てのブロック
【数29】
に関し、中間者は、最初に、これらのブロックに対応するMerkle木の葉
【数30】
に相当する頂点の集合を求める。
2)そこで、Merkle木において任意の頂点対が兄弟である場合、中間者は、それら2つの頂点の両方を、それらの親、すなわち、兄弟に対応する値の連結のハッシュと置き換える。
3)中間者は、該集合に兄弟である2つの頂点がなくなるまで、上記の処理を繰り返す。
4)中間者は、この集合の頂点を取り出し、それらに対応するMerkle木の値X(i)=x1(i),…,xr(i)を計算する。暗号ハッシュ関数は、大域的に計算可能であるので、中間者は、このステップを容易に行うことができる。
【0117】
中間ノードは、最後に、以下の情報を送信する。
【数31】
【0118】
ストリームは、適切な順序で送信される。すなわち、各M’(i)からのブロックは、受信者がストリームを見ることができるようにインターリーブしてもよい。受信者がメッセージブロックとハッシュ値とを区別できるように、標準的な符号化をブロックコンテンツに適用する。
5.3 検証
【0119】
受信者は、最初に、各Merkle木の根の値を計算し、その後、これらの値をハッシュして、署名を検証する。各iに行われる以下のアルゴリズムを用いて、この目的を達する。
1)最初に、受信者は、受信した実際のメッセージブロック
【数32】
ごとに、
【数33】
の値を計算する。
2)上述のように、前ステップで計算された全てのハッシュの集合と、該送信において受信された集合X(1),…,X(k)に含まれるハッシュ値とを考慮する。
3)1対の値ごとに、該対が兄弟である頂点に相当するものであるならば、該対をそれらのハッシュ(Merkle木の親ノードに相当する)に置き換える。
4)1つの値だけが残るまで上記ステップを繰り返す。この値は根x(i)である。
【0120】
初期メッセージブロックの全てを得ているならば、上記のアルゴリズムは、Merkle木の根を計算するための標準アルゴリズムとなる。受信者が、いくつかのハッシュx1(i),…,xr(i)を受信するときは、欠けているブロックの部分集合に対して同じアルゴリズムを実行している中間者からそれらは来ている。従って、中間者と受信者は、共に、Merkle根の値をもたらすn個のブロックの全てについて該アルゴリズムを実行している。これが、上記の計算がMerkle根をもたらす理由である。
【0121】
受信者は、Merkle根の値、x(1),…,x(k)によって、x=H(IV,x(1),…,x(k))を計算し、受信した署名を検証することができる。
【0122】
図11は、本発明の第5の実施形態の署名及び検証を示すものであり、4つのストリームと4つのメッセージブロックを有する例である。図に示すように、4つのストリームM(1),M(2),M(3),M(4)は、それぞれ、4つのブロックからなる。黒い葉は、実際に送信されるメッセージブロックを示す。残りは、削除される。影付きの頂点は、カバーを示す。すなわち、これらの頂点に相当する値は、受信者に送信される。4つのMerkle木の根は、それぞれ、x(1),x(2),x(3),x(4)である。最終的な根の値xは、Merkle根x(1),x(2),x(3),x(4)をハッシュすることによって計算される。このハッシュは、Merkleのような形式でも実行することができる。最後に、値xが実際に署名される。この方式において、6つのハッシュ値だけが受信者に送信される。線形サイマルキャスト方式では、12のハッシュが送信されていた(送信される1ブロックごとに3つ)。従って、削除されるブロックをひとかたまりにするたびに、節約が達成される。例えば、図11において、ストリームM(4)のブロックは、全て削除される。その結果、対応するMerkle木の根x(4)を送信するだけでよい。
【0123】
また、Merkle根は、それ自体、Merkleのような構造においてハッシュされるので、さらに最適化する余地がある。具体的には、Merkle根が、さらに大きい木において兄弟である2つの完全な部分木について、全てのブロックを削除するものとする。その結果、2つのMerkle根を送信する代わりに、それらのハッシュを送信することができる。
5.4 セキュリティ
【0124】
第4の実施形態と同様に、第5の実施形態は、署名方式が偽造されにくく、ハッシュ関数が衝突しにくいならば、安全である。従って、上記に示した本発明は安全である。
5.5 パフォーマンス
【0125】
第5実施形態のパフォーマンスは、木を用いた部分列方式と線形サイマルキャスト方式とに関する分析を拡張することによって、分析することができる。
【0126】
上述の全ての実施形態において、特定のペイロードサイズと特定のIVとを用いたハッシュ関数が用いられる。連鎖構造は、ある既存の出力を取り出し、次のブロックのIVとして用いる傾向がある。さらなる実施形態では、IVとして現時点の出力をロードする代わりに、現時点の出力を次のペイロードに連結することができる。
【0127】
本発明の線形方式と木方式を組み合わせて、ハイブリッドの解決法を得ることで、有益なトレードオフをもたらすことができる。さらなる実施形態では、ある方式が、各ストリームM(i)を、長さbのブロックのセグメントに分割することによって始まる。次に、木方式を、全てのストリームの第1のセグメントに適用して、Merkle根x1を計算し、次に第2のセグメントに関する根、というふうに、全てのセグメントが処理されるまで計算する。こうして、Merkle根
【数34】
が得られる。これらの根の1つ1つに署名するかわりに、上記に説明した木方式におけるように、根は、線形方式を用いて結合される。従って、受信者が、b個のブロックをバッファリングすることができる場合、検証は、「オンライン」でできる。さらに、b個のブロックのセグメントごとに送信されるハッシュの数は、削除されるブロックの数よりもはるかに少なくてもよいので(最悪のケースでは同じであるが)、通信オーバーヘッドは、簡単な線形方式に比べて減少する。同様のアプローチを、部分列認証にも採用することができる。このハイブリッド方法により、バッファ領域を、通信オーバーヘッドとトレードすることができる。
【0128】
さらなる実施形態においては、線形方式を各ストリームに適用し、その結果についてMerkle木を計算する。
【0129】
上記の実施形態は、バイナリのMerkle木を使用しているが、その構造は、一般的な木に適用することができる。所定のブロックが、同様の性質を有する、すなわち、全てが削除されるか、又は、全てが保持されるかのいずれかである場合、それらを1つにまとめることは、さらに有益であるかもしれない。
【0130】
ブロック間に相関がある場合、木を用いた方式において、これらのブロックをひとまとめにすることは、理にかなっている。例えば、あるブロック群が、全て削除されるか、全て保持されるかのいずれかである場合、これらのブロックが、部分木の全ての葉を構成するようにすることは有益である。従って、パケットを削除する場合、その部分木の根を送信するだけでよい。
【0131】
さらに、Merkle木構造を最適化することができる。一実施形態において、ストリームの1つが、他のものよりも使用される可能性が高い場合、この優先ストリームが根に近い(例えば、おそらく右下にある)不均衡なMerkle木を使用することは都合がよい。前述のハイブリッド方式に関連して、ストリームは、優先順位をつけられるので、高い優先度のストリームは、連鎖の最終値に近くなる。この順序付けは、層状ストリームを使用する場合、特に理にかなっている。かかる場合、検証において、根に到達するためのハッシュステップがより少なくて済む。
【0132】
MPEGストリームのIフレームや、スケーラブルに符号化されたストリームのベース層など、削除すべきではないブロックが存在する。署名者は、削除されないブロックについて、最初の第1層ハッシュを直接計算しなくて済む。線形方式では、ハッシュ層は2つある。ブロックが削除されない場合、第1層のハッシュを計算する必要はなく、代わりに、第2層だけを計算すればよい。
【0133】
本発明の方式は、2つの段階を有すると解釈することができる。第1の段階では、各データブロックをハッシュするのに便利な方法を見つける。第2の段階では、ハッシュに署名する。そうする理由は、ブロックが削除される場合、それを完全な形で再送する必要がないからである。その代わりに、第1の段階で計算されたハッシュのみを送信する。署名は、ハッシュに行われたものとみなすことができるので、受信者は、この情報で十分検証できる。
【0134】
すでに述べたように、本発明は、制御損失のケースに対処するものであり、すなわち、送信者は、特定のブロックを故意に削除する。もちろん、多くの実際のアプリケーションにおいて、非制御の損失事態に対処しなければならないかもしれない。例えば、UDPのように、トランスポートプロトコルが信頼できない場合や、無線ネットワークのように、環境が損失動作に左右される場合、このような事態は起こりうる。本発明は、パケットが削除された場合、送信されるハッシュを複製することによって、非制御損失に対処するのに使用することができる。
【0135】
消去符号等の順方向誤り訂正(FEC)技術を本発明のハッシュに適用することによって、複製する必要なしに非制御損失事態に対処することが可能である。このアプローチは、異なる受信者が異なるパケットを失っているが、同一の誤り訂正情報を与えられるマルチキャスト設定において、特に有益であるかもしれない。このアプローチで考慮するべきことは、受信者が復号処理を行わなければならず、オンライン形式で認証情報を検証する能力を犠牲にしなければならない可能性があることである。
【0136】
さらに、本発明の方式は、認証情報(すなわち、ハッシュ出力)に対する順方向誤り訂正量を適応的に選択できる中間者を必要とする。換言すると、送信元に、どれくらいの損失が起こるかを予測させて、十分な認証順方向誤り訂正情報を含めて対処させるのではなく、送信元は、認証順方向誤り訂正情報をまったく含めないことにすることができ、代わりに、中間者が、認証順方向誤り訂正情報を動的に含めて、ストリームを認証できる確率をさらに高めることができるようにすることができる。
【0137】
中間者は、適応的・知能的制御損失に加え、順方向誤り訂正により対処する非制御損失の両方を考慮する方式の不可欠な部分となる。例えば、Merkle木構造において、受信者にとって、(単なる葉ノードではなく)中間ノードを回復すれば十分かもしれない。かかる場合、中間者は、順方向誤り訂正情報を提供することにして、認証に必要な(おそらく内部)ノードを回復できるようにすることができ、おそらくより少ない順方向誤り訂正情報で済む。
【0138】
中間者が、複数の受信者に対して、例えば、受信者がそれぞれ見ている品質について様々なリソースの制約があるために、同一ストリームの様々なバージョンを送信している場合、中間者は、作業労力を再利用することができる。具体的に、中間者は、第1層ハッシュを記憶し再利用することができる。その結果、多くても、完全な第1層ハッシュの集合を計算するだけでよい。
【0139】
この線に沿って、送信元と中間者との間で作業は再利用することができる。すなわち、送信元は、認証を補助するのに必要なハッシュ計算値を、中間者に提供することができる。従って、中間者は、暗号的性質の作業を実行する必要がない。代わりに、どのブロックを削除するかを決め、それに対応する送信する認証情報を選択することができる。
【0140】
本発明の別のアプリケーションは、ストリームに広告を挿入し、広告を選択することである。中間者又は他の者は、広告、又は、例えばMerkle木を用いてハッシュした広告のハッシュを、送信元に提供する。すると送信元は、ストリームにプレースホルダーとしてMerkleハッシュを含めて、中間者が使用したい広告を選ぶことができるようにする。もちろん、この概念は、必ずしも広告者に限定されるものではない。
【0141】
本発明の中心は、情報を認証することにあるが、上記の方式は、暗号方式に関連して使用することもできる。ただし、受信者が、他の多くのブロックの復号又は存在を必要とせずに、所定のブロックを復号することができるように、該方式が構成されていればである。2つのブロック暗号暗号化モードにより、この方法は容易になる。1つは、カウンタモード暗号化であり、他方は、電子コードブック(ECB)暗号化である。或いは、ストリーム暗号を用いることもできる。ただし、受信者は、受信したストリームの1部分ではなく、元ストリームのサイズに比例した作業を実行する必要があるかもしれない。受信者が、復号する中間情報を受信しているならば、連鎖又はフィードバックモード(暗号ブロック連鎖方式(CBC)、出力フィードバック(OFB)等)を使用することが可能かもしれない。かかる情報は、中間IVや、実際の暗号文ブロックを含んでいてもよい。さらに他の方法は、該モードを混合するものである。すなわち、削除されない大きいセグメントに関しては、連鎖又はフィードバックモードを使用することができ、一方、その他のブロックに関しては、カウンタモード又はECBモードを使用することができる。例えば、MPEGストリームにおいては、Iフレームは、故意に削除されることはないので別に処理し、CBCモードを使用して暗号化することができる。同様のことが、スケーラブルな符号体系のベース層にも言える。
【0142】
上記において、本発明を様々な実施形態について詳細に説明してきたが、当業者であれば、これらの実施形態を本発明の範囲及び精神から逸脱することなく、変更することができることを理解するであろう。従って、本発明は、添付の請求項の範囲によってのみ限定されるものとみなされるべきである。
【図面の簡単な説明】
【0143】
【図1】スケーラブルなコーダのハイレベル図を示す。
【図2】送信者又は送信元のブロック図を示す。
【図3】受信者のブロック図を示す。
【図4】中間者のブロック図を示す。
【図5】送信者、受信者、及び中間者を含むシステムのブロック図を示す。
【図6】8個の葉を持つMerkle木を示す。
【図7】本発明の一実施形態による、基本線形部分列認証方式を示す。
【図8】本発明の一実施形態による、r=3であり、nがrの倍数である、最適化された線形部分列認証方式を示す。
【図9】本発明の一実施形態による、基本線形サイマルキャスト認証方式を示す。
【図10】本発明の一実施形態による、木を用いた部分列認証方式を示す。
【図11】本発明の一実施形態による、木を用いたサイマルキャスト認証方式を示す。
【特許請求の範囲】
【請求項1】
サーバと受信者との間でデータを通信する方法であって、
複数のブロックを含む少なくとも1つの元データストリームに署名する工程と、
前記元データストリームのブロックを検閲せずに、任意のブロックが適応的に削除された前記署名されたデータストリームに対する中間データストリームを生成する工程と、
前記中間データストリームを前記受信者に通信する工程と、
前記受信者において、前記中間データストリームを認証する工程とを含むことを特徴とする方法。
【請求項2】
前記元データストリームに署名する工程は、補助ハッシュ値と部分ハッシュ値とを含むハッシュ計算値を生成する工程をさらに含むことを特徴とする請求項1に記載の方法。
【請求項3】
前記中間データストリームを生成する工程は、前記署名されたデータストリームのブロックごとに、前記部分ハッシュ値と補助ハッシュ値とを計算する工程をさらに含むことを特徴とする請求項2に記載の方法。
【請求項4】
前記中間データストリームは、
前記受信者に送信されるデータストリームブロックと、
前記削除されるブロックに対する補助ハッシュ値とを含むことを特徴とする請求項2に記載の方法。
【請求項5】
前記受信者において、受信したブロックがデータストリームブロックであるか否かについてを判定する工程をさらに含むことを特徴とする請求項4に記載の方法。
【請求項6】
前記受信者において、前記データストリームブロックに対する前記部分ハッシュ値を再計算する工程をさらに含むことを特徴とする請求項4に記載の方法。
【請求項7】
前記受信者において、前記再計算された部分ハッシュ値に基づいて、前記署名を検証する工程をさらに含むことを特徴とする請求項6に記載の方法。
【請求項8】
部分ハッシュ値を計算する前に、いくつかの補助ハッシュ値をまとめる工程をさらに含むことを特徴とする請求項2に記載の方法。
【請求項9】
前記元データストリームに署名する工程は、前記元データストリームに対するMerkle木を生成し、該Merkle木の根に対応する値を計算する工程をさらに含むことを特徴とする請求項1に記載の方法。
【請求項10】
前記中間データストリームは、
前記受信者が前記Merkle木の根を再計算するためのMerkle木の値と、
データストリームブロックとを含むことを特徴とする請求項9に記載の方法。
【請求項11】
前記中間データストリームを生成する工程は、
前記削除されるブロックに対応する前記Merkle木の葉に相当する頂点の集合を決定する工程と、
前記Merkle木において任意の頂点対が兄弟である場合、該頂点対における2つの頂点を該2つの頂点の親に置き換える工程と、
前記Merkle木において任意の頂点対が兄弟でない場合、該頂点に対応する前記Merkle木の値を計算する工程とをさらに含むことを特徴とする請求項9に記載の方法。
【請求項12】
受信者において、前記Merkle木の根の値を再計算する工程をさらに含むことを特徴とする請求項11に記載の方法。
【請求項13】
前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項11に記載の方法。
【請求項14】
前記受信者において、前記Merkle木の根の値により前記署名を検証する工程をさらに含むことを特徴とする請求項12に記載の方法。
【請求項15】
前記元データストリームに署名する工程は、各元データストリームの各ブロックの部分ハッシュ値を計算して、多層ハッシュチェーンを計算する工程をさらに含むことを特徴とする請求項1に記載の方法。
【請求項16】
前記中間データストリームを生成する工程は、各署名されたデータストリームの各ブロックに対する前記部分ハッシュ値を計算する工程をさらに含むことを特徴とする請求項15に記載の方法。
【請求項17】
前記中間データストリームは、異なるデータストリームから適応的に選択されたデータストリームブロックを含むことを特徴とする請求項15に記載の方法。
【請求項18】
前記受信者において、前記中間データストリームの各ブロックに対する前記部分ハッシュ値を再計算する工程をさらに含むことを特徴とする請求項15に記載の方法。
【請求項19】
前記受信者において、前記再計算された部分ハッシュ値に基づいて、前記署名を検証する工程をさらに含むことを特徴とする請求項18に記載の方法。
【請求項20】
前記元データストリームに署名する工程は、
前記元データストリームごとに、Merkle木を生成する工程と、
前記Merkle木の各々の根に対応する値を計算する工程と、
前記Merkle木の根の値をハッシュすることによって、最終的な根の値を生成する工程とをさらに含むことを特徴とする請求項1に記載の方法。
【請求項21】
前記中間データストリームは、
データストリームブロックと、
前記受信者が前記Merkle木の根を再計算するための前記Merkle木の値とを含むことを特徴とする請求項20に記載の方法。
【請求項22】
前記中間データストリームを生成する工程は、
署名されたデータストリームごとに、前記削除されるブロックに対応する前記Merkle木の葉に相当する頂点の集合を決定する工程と、
前記Merkle木において任意の頂点対が兄弟である場合、該頂点対における2つの頂点を該2つの頂点の親に置き換える工程と、
前記Merkle木において任意の頂点対が兄弟でない場合、該頂点に対応する前記Merkle木の値を計算する工程とをさらに含むことを特徴とする請求項20に記載の方法。
【請求項23】
前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項22に記載の方法。
【請求項24】
前記受信者において、前記Merkle木の各々の根の値を再計算する工程をさらに含むことを特徴とする請求項20に記載の方法。
【請求項25】
前記受信者において、前記Merkle木の根の値をハッシュすることによって、前記最終的な根の値を再計算する工程をさらに含むことを特徴とする請求項24に記載の方法。
【請求項26】
前記受信者において、前記最終的な根の値により前記署名を検証する工程をさらに含むことを特徴とする請求項25に記載の方法。
【請求項27】
前記最終的な根の値は、反復ハッシュによって再計算されることを特徴とする請求項25に記載の方法。
【請求項28】
前記最終根の値は、Merkleハッシュによって再計算されることを特徴とする請求項25に記載の方法。
【請求項29】
前記Merkle木は、不均衡であることを特徴とする請求項9に記載の方法。
【請求項30】
前記Merkle木は、不均衡であることを特徴とする請求項20に記載の方法。
【請求項31】
全てが削除される一群のブロックによって部分木を形成する工程をさらに含むことを特徴とする請求項9に記載の方法。
【請求項32】
全てが削除される一群のブロックによって部分木を形成する工程をさらに含むことを特徴とする請求項20に記載の方法。
【請求項33】
全てが送信される一群のブロックによって部分木を形成する工程をさらに含むことを特徴とする請求項9に記載の方法。
【請求項34】
全てが送信される一群のブロックによって部分木を形成する工程をさらに含むことを特徴とする請求項20に記載の方法。
【請求項35】
前記最終的な根の値は、反復ハッシュによって生成されることを特徴とする請求項20に記載の方法。
【請求項36】
前記最終的な根の値は、Merkleハッシュによって生成されることを特徴とする請求項20に記載の方法。
【請求項37】
決して削除されないブロックを決定する工程をさらに含むことを特徴とする請求項1に記載の方法。
【請求項38】
前記ブロックが決して削除されない場合、恒等関数を第1層ハッシュとして適用する工程をさらに含むことを特徴とする請求項37に記載の方法。
【請求項39】
前記ハッシュ値に、順方向誤り訂正(FEC)技術を適用する工程をさらに含むことを特徴とする請求項2に記載の方法。
【請求項40】
前記ハッシュ値に、順方向誤り訂正(FEC)技術を適用する工程をさらに含むことを特徴とする請求項15に記載の方法。
【請求項41】
前記元データストリームに署名する工程は、電子署名を使用することを特徴とする請求項1に記載の方法。
【請求項42】
前記電子署名は、前記元データストリームのブロックの最終ハッシュ値に適用することを特徴とする請求項41に記載の方法。
【請求項43】
前記元データストリームに署名する工程は、メッセージ認証符号を使用することを特徴とする請求項1に記載の方法。
【請求項44】
前記メッセージ認証符号は、前記元データストリームのブロックの最終ハッシュ値に適用することを特徴とする請求項43に記載の方法。
【請求項45】
前記削除されるデータストリームブロックは、広告を含むことを特徴とする請求項1に記載の方法。
【請求項46】
サーバと受信者との間でデータを通信するシステムであって、
複数のブロックを含む少なくとも1つの元データストリームに署名する署名者と、
前記元データストリームのブロックを検閲せずに、任意のブロックが適応的に削除された前記署名されたデータストリームに対する中間データストリームを生成するデータストリーム生成者と、
前記中間データストリームを認証する受信者とを含むことを特徴とするシステム。
【請求項47】
前記署名者は、補助ハッシュ値と部分ハッシュ値とを含むハッシュ計算値を生成することを特徴とする請求項46に記載のシステム。
【請求項48】
前記データストリーム生成者は、前記署名されたデータストリームを受信し、該データストリームのブロックごとに、前記部分ハッシュ値と補助ハッシュ値とを計算することを特徴とする請求項47に記載のシステム。
【請求項49】
前記受信者は、前記中間データストリームを受信し、前記データストリームブロックに対する前記部分ハッシュ値を再計算することを特徴とする請求項47に記載のシステム。
【請求項50】
前記署名者は、部分ハッシュ値を計算する前に、いくつかの補助ハッシュ値をまとめることを特徴とする請求項47に記載のシステム。
【請求項51】
前記署名者は、元データストリームについて生成されたMerkle木の根に対応する値を計算することを特徴とする請求項46に記載のシステム。
【請求項52】
前記データストリーム生成者は、
前記署名されたデータストリームを受信し、
前記削除されるブロックに対応する前記Merkle木の葉に相当する頂点の集合を決定し、
前記Merkle木において任意の頂点対が兄弟である場合、該頂点対における2つの頂点を該2つの頂点の親に置き換え、
前記Merkle木において任意の頂点対が兄弟でない場合、該頂点に対応する前記Merkle木の値を計算することを特徴とする請求項51に記載のシステム。
【請求項53】
前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項52に記載の方法。
【請求項54】
前記受信者は、前記中間データストリームを受信し、前記Merkle木の根の値を再計算することを特徴とする請求項51に記載のシステム。
【請求項55】
前記署名者は、各データストリームの各ブロックに対する部分ハッシュ値を計算して、多層ハッシュチェーンを計算することを特徴とする請求項46に記載のシステム。
【請求項56】
前記データストリーム生成者は、前記署名されたデータストリームを受信し、各署名されたデータストリームのブロックごとに、前記部分ハッシュ値を計算することを特徴とする請求項55に記載のシステム。
【請求項57】
前記受信者は、前記中間データストリームを受信し、前記中間データストリームのブロックごとに、前記部分ハッシュ値を再計算することを特徴とする請求項55に記載のシステム。
【請求項58】
前記署名者は、
前記元データストリームごとに、Merkle木を生成し、
前記Merkle木の各々の根に対応する値を計算し、
前記Merkle木の根の値をハッシュすることによって、最終的な根の値を生成することを特徴とする請求項46に記載のシステム。
【請求項59】
前記データストリーム生成者は、
前記署名されたデータストリームを受信し、
署名されたデータストリームごとに、前記削除されるブロックに対応する前記Merkle木の葉に相当する頂点の集合を決定し、
前記Merkle木において任意の頂点対が兄弟である場合、該頂点対における2つの頂点を該2つの頂点の親に置き換え、
前記Merkle木において任意の頂点対が兄弟でない場合、該頂点に対応する前記Merkle木の値を計算することを特徴とする請求項58に記載のシステム。
【請求項60】
前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項59に記載の方法。
【請求項61】
前記受信者は、前記中間データストリームを受信し、各Merkle木の根の値を再計算することを特徴とする請求項58に記載のシステム。
【請求項62】
元データストリームに署名する方法を実行するためのプログラムコードを含むコンピュータプログラム製品であって、
前記方法は、
少なくとも1つの元データストリームを複数のブロックに分解する工程と、
前記署名されたデータストリームのブロックについての部分ハッシュ値と、前記元データストリームについて生成されたMerkle木の根に関連する値と、各データストリームの各ブロックの部分ハッシュ値から計算された多層ハッシュチェーンと、それぞれが該元データストリームに対応するMerkle木の根の値をハッシュすることによって計算された最終的な根の値とからなるグループから選択された補助情報を計算する工程と、
前記補助情報に基づいて、各ブロックの認証情報を計算する工程と、
前記元データストリームと前記認証情報とを含む署名されたデータストリームを生成する工程と、
前記元データストリームを検閲せずに、任意のブロックを適応的に削除することによって、中間データストリームを生成する工程とを含み、
前記中間データストリームは、受信者によって認証可能であることを特徴とするコンピュータプログラム製品。
【請求項63】
電子署名を認証に使用することを特徴とする請求項62に記載のコンピュータプログラム製品。
【請求項64】
前記電子署名は、前記元データストリームのブロックの最終ハッシュ値に適用されることを特徴とする請求項63に記載の方法。
【請求項65】
メッセージ認証符号を認証に使用することを特徴とする請求項62に記載のコンピュータプログラム製品。
【請求項66】
前記メッセージ認証符号は、前記元データストリームのブロックの最終ハッシュ値に適用されることを特徴とする請求項65に記載の方法。
【請求項67】
前記補助情報は、署名者において計算されることを特徴とする請求項62に記載の方法。
【請求項68】
前記補助情報は、中間者において計算されることを特徴とする請求項62に記載の方法。
【請求項69】
元データストリームについて、署名したデータストリームから任意のブロックを適応的に削除する方法を実行するためのプログラムコードを含むコンピュータプログラム製品であって、
前記方法は、
前記元データストリームを検閲せずに、前記署名されたデータストリームにおいて送信されるデータストリームブロックを決定する工程と、
中間データストリームを生成することによって、前記署名されたデータストリームにおいてその他のブロックを適応的に削除する工程と、
前記中間データストリームを受信者に送信して認証させる工程とを含むことを特徴とするコンピュータプログラム製品。
【請求項70】
前記方法は、前記署名されたデータストリームのブロックごとに、前記部分ハッシュ値及び補助ハッシュ値を計算する工程をさらに含むことを特徴とする請求項69に記載のコンピュータプログラム製品。
【請求項71】
前記中間データストリームは、送信されるデータストリームブロックと、前記削除されるブロックに対する前記補助ハッシュ値とを含むことを特徴とする請求項70に記載のコンピュータプログラム製品。
【請求項72】
前記部分ハッシュ値及び補助ハッシュ値を送信する工程をさらに含むことを特徴とする請求項70に記載の方法。
【請求項73】
前記方法は、
前記削除されるブロックに対応する前記Merkle木の葉に相当する頂点の集合を決定する工程と、
前記Merkle木において任意の頂点対が兄弟である場合、該頂点対における2つの頂点を該2つの頂点の親に置き換える工程と、
前記Merkle木において任意の頂点対が兄弟でない場合、頂点に対応する前記Merkle木の値を計算する工程とをさらに含むことを特徴とする請求項69に記載のコンピュータプログラム製品。
【請求項74】
前記中間データストリームは、送信されるデータストリームブロックと、前記削除されるブロックに対応するMerkle木の値とを含むことを特徴とする請求項73に記載のコンピュータプログラム製品。
【請求項75】
前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項73に記載の方法。
【請求項76】
前記中間データストリームは、異なるデータストリームから適応的に選択されたデータストリームブロックを含むことを特徴とする請求項69に記載のコンピュータプログラム製品。
【請求項77】
中間データストリームを認証する方法を実行するためのプログラムコードを含むコンピュータプログラム製品であって、
前記方法は、
元データブロックから生成されているが、一部のデータが削除されている前記中間データストリームにおいて、データストリームブロックを識別する工程と、
前記中間データストリームのブロックの補助情報を計算する工程であって、前記補助情報が、前記中間データストリームのブロックの部分ハッシュ値と、前記元データストリームについて生成されたMerkle木の根に関連する値と、多層ハッシュチェーンと、元データストリームについて生成されたMerkle木の根の値をハッシュすることによって計算された最終的な根の値とからなるグループから選択される工程と、
認証情報を検証する工程とを含むことを特徴とするコンピュータプログラム製品。
【請求項78】
電子署名を認証に使用することを特徴とする請求項77に記載のコンピュータプログラム製品。
【請求項79】
メッセージ認証符号を認証に使用することを特徴とする請求項77に記載のコンピュータプログラム製品。
【請求項80】
データ通信ネットワークにおけるサーバであって、プロセッサと、請求項62に記載のコンピュータプログラム製品とを含むことを特徴とするサーバ。
【請求項81】
データ通信ネットワークにおける中間ノードであって、プロセッサと、請求項69に記載のコンピュータプログラム製品とを含むことを特徴とする中間ノード。
【請求項82】
データ通信ネットワークにおける受信者であって、プロセッサと、請求項77に記載のコンピュータプログラム製品とを含むことを特徴とする受信者。
【請求項1】
サーバと受信者との間でデータを通信する方法であって、
複数のブロックを含む少なくとも1つの元データストリームに署名する工程と、
前記元データストリームのブロックを検閲せずに、任意のブロックが適応的に削除された前記署名されたデータストリームに対する中間データストリームを生成する工程と、
前記中間データストリームを前記受信者に通信する工程と、
前記受信者において、前記中間データストリームを認証する工程とを含むことを特徴とする方法。
【請求項2】
前記元データストリームに署名する工程は、補助ハッシュ値と部分ハッシュ値とを含むハッシュ計算値を生成する工程をさらに含むことを特徴とする請求項1に記載の方法。
【請求項3】
前記中間データストリームを生成する工程は、前記署名されたデータストリームのブロックごとに、前記部分ハッシュ値と補助ハッシュ値とを計算する工程をさらに含むことを特徴とする請求項2に記載の方法。
【請求項4】
前記中間データストリームは、
前記受信者に送信されるデータストリームブロックと、
前記削除されるブロックに対する補助ハッシュ値とを含むことを特徴とする請求項2に記載の方法。
【請求項5】
前記受信者において、受信したブロックがデータストリームブロックであるか否かについてを判定する工程をさらに含むことを特徴とする請求項4に記載の方法。
【請求項6】
前記受信者において、前記データストリームブロックに対する前記部分ハッシュ値を再計算する工程をさらに含むことを特徴とする請求項4に記載の方法。
【請求項7】
前記受信者において、前記再計算された部分ハッシュ値に基づいて、前記署名を検証する工程をさらに含むことを特徴とする請求項6に記載の方法。
【請求項8】
部分ハッシュ値を計算する前に、いくつかの補助ハッシュ値をまとめる工程をさらに含むことを特徴とする請求項2に記載の方法。
【請求項9】
前記元データストリームに署名する工程は、前記元データストリームに対するMerkle木を生成し、該Merkle木の根に対応する値を計算する工程をさらに含むことを特徴とする請求項1に記載の方法。
【請求項10】
前記中間データストリームは、
前記受信者が前記Merkle木の根を再計算するためのMerkle木の値と、
データストリームブロックとを含むことを特徴とする請求項9に記載の方法。
【請求項11】
前記中間データストリームを生成する工程は、
前記削除されるブロックに対応する前記Merkle木の葉に相当する頂点の集合を決定する工程と、
前記Merkle木において任意の頂点対が兄弟である場合、該頂点対における2つの頂点を該2つの頂点の親に置き換える工程と、
前記Merkle木において任意の頂点対が兄弟でない場合、該頂点に対応する前記Merkle木の値を計算する工程とをさらに含むことを特徴とする請求項9に記載の方法。
【請求項12】
受信者において、前記Merkle木の根の値を再計算する工程をさらに含むことを特徴とする請求項11に記載の方法。
【請求項13】
前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項11に記載の方法。
【請求項14】
前記受信者において、前記Merkle木の根の値により前記署名を検証する工程をさらに含むことを特徴とする請求項12に記載の方法。
【請求項15】
前記元データストリームに署名する工程は、各元データストリームの各ブロックの部分ハッシュ値を計算して、多層ハッシュチェーンを計算する工程をさらに含むことを特徴とする請求項1に記載の方法。
【請求項16】
前記中間データストリームを生成する工程は、各署名されたデータストリームの各ブロックに対する前記部分ハッシュ値を計算する工程をさらに含むことを特徴とする請求項15に記載の方法。
【請求項17】
前記中間データストリームは、異なるデータストリームから適応的に選択されたデータストリームブロックを含むことを特徴とする請求項15に記載の方法。
【請求項18】
前記受信者において、前記中間データストリームの各ブロックに対する前記部分ハッシュ値を再計算する工程をさらに含むことを特徴とする請求項15に記載の方法。
【請求項19】
前記受信者において、前記再計算された部分ハッシュ値に基づいて、前記署名を検証する工程をさらに含むことを特徴とする請求項18に記載の方法。
【請求項20】
前記元データストリームに署名する工程は、
前記元データストリームごとに、Merkle木を生成する工程と、
前記Merkle木の各々の根に対応する値を計算する工程と、
前記Merkle木の根の値をハッシュすることによって、最終的な根の値を生成する工程とをさらに含むことを特徴とする請求項1に記載の方法。
【請求項21】
前記中間データストリームは、
データストリームブロックと、
前記受信者が前記Merkle木の根を再計算するための前記Merkle木の値とを含むことを特徴とする請求項20に記載の方法。
【請求項22】
前記中間データストリームを生成する工程は、
署名されたデータストリームごとに、前記削除されるブロックに対応する前記Merkle木の葉に相当する頂点の集合を決定する工程と、
前記Merkle木において任意の頂点対が兄弟である場合、該頂点対における2つの頂点を該2つの頂点の親に置き換える工程と、
前記Merkle木において任意の頂点対が兄弟でない場合、該頂点に対応する前記Merkle木の値を計算する工程とをさらに含むことを特徴とする請求項20に記載の方法。
【請求項23】
前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項22に記載の方法。
【請求項24】
前記受信者において、前記Merkle木の各々の根の値を再計算する工程をさらに含むことを特徴とする請求項20に記載の方法。
【請求項25】
前記受信者において、前記Merkle木の根の値をハッシュすることによって、前記最終的な根の値を再計算する工程をさらに含むことを特徴とする請求項24に記載の方法。
【請求項26】
前記受信者において、前記最終的な根の値により前記署名を検証する工程をさらに含むことを特徴とする請求項25に記載の方法。
【請求項27】
前記最終的な根の値は、反復ハッシュによって再計算されることを特徴とする請求項25に記載の方法。
【請求項28】
前記最終根の値は、Merkleハッシュによって再計算されることを特徴とする請求項25に記載の方法。
【請求項29】
前記Merkle木は、不均衡であることを特徴とする請求項9に記載の方法。
【請求項30】
前記Merkle木は、不均衡であることを特徴とする請求項20に記載の方法。
【請求項31】
全てが削除される一群のブロックによって部分木を形成する工程をさらに含むことを特徴とする請求項9に記載の方法。
【請求項32】
全てが削除される一群のブロックによって部分木を形成する工程をさらに含むことを特徴とする請求項20に記載の方法。
【請求項33】
全てが送信される一群のブロックによって部分木を形成する工程をさらに含むことを特徴とする請求項9に記載の方法。
【請求項34】
全てが送信される一群のブロックによって部分木を形成する工程をさらに含むことを特徴とする請求項20に記載の方法。
【請求項35】
前記最終的な根の値は、反復ハッシュによって生成されることを特徴とする請求項20に記載の方法。
【請求項36】
前記最終的な根の値は、Merkleハッシュによって生成されることを特徴とする請求項20に記載の方法。
【請求項37】
決して削除されないブロックを決定する工程をさらに含むことを特徴とする請求項1に記載の方法。
【請求項38】
前記ブロックが決して削除されない場合、恒等関数を第1層ハッシュとして適用する工程をさらに含むことを特徴とする請求項37に記載の方法。
【請求項39】
前記ハッシュ値に、順方向誤り訂正(FEC)技術を適用する工程をさらに含むことを特徴とする請求項2に記載の方法。
【請求項40】
前記ハッシュ値に、順方向誤り訂正(FEC)技術を適用する工程をさらに含むことを特徴とする請求項15に記載の方法。
【請求項41】
前記元データストリームに署名する工程は、電子署名を使用することを特徴とする請求項1に記載の方法。
【請求項42】
前記電子署名は、前記元データストリームのブロックの最終ハッシュ値に適用することを特徴とする請求項41に記載の方法。
【請求項43】
前記元データストリームに署名する工程は、メッセージ認証符号を使用することを特徴とする請求項1に記載の方法。
【請求項44】
前記メッセージ認証符号は、前記元データストリームのブロックの最終ハッシュ値に適用することを特徴とする請求項43に記載の方法。
【請求項45】
前記削除されるデータストリームブロックは、広告を含むことを特徴とする請求項1に記載の方法。
【請求項46】
サーバと受信者との間でデータを通信するシステムであって、
複数のブロックを含む少なくとも1つの元データストリームに署名する署名者と、
前記元データストリームのブロックを検閲せずに、任意のブロックが適応的に削除された前記署名されたデータストリームに対する中間データストリームを生成するデータストリーム生成者と、
前記中間データストリームを認証する受信者とを含むことを特徴とするシステム。
【請求項47】
前記署名者は、補助ハッシュ値と部分ハッシュ値とを含むハッシュ計算値を生成することを特徴とする請求項46に記載のシステム。
【請求項48】
前記データストリーム生成者は、前記署名されたデータストリームを受信し、該データストリームのブロックごとに、前記部分ハッシュ値と補助ハッシュ値とを計算することを特徴とする請求項47に記載のシステム。
【請求項49】
前記受信者は、前記中間データストリームを受信し、前記データストリームブロックに対する前記部分ハッシュ値を再計算することを特徴とする請求項47に記載のシステム。
【請求項50】
前記署名者は、部分ハッシュ値を計算する前に、いくつかの補助ハッシュ値をまとめることを特徴とする請求項47に記載のシステム。
【請求項51】
前記署名者は、元データストリームについて生成されたMerkle木の根に対応する値を計算することを特徴とする請求項46に記載のシステム。
【請求項52】
前記データストリーム生成者は、
前記署名されたデータストリームを受信し、
前記削除されるブロックに対応する前記Merkle木の葉に相当する頂点の集合を決定し、
前記Merkle木において任意の頂点対が兄弟である場合、該頂点対における2つの頂点を該2つの頂点の親に置き換え、
前記Merkle木において任意の頂点対が兄弟でない場合、該頂点に対応する前記Merkle木の値を計算することを特徴とする請求項51に記載のシステム。
【請求項53】
前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項52に記載の方法。
【請求項54】
前記受信者は、前記中間データストリームを受信し、前記Merkle木の根の値を再計算することを特徴とする請求項51に記載のシステム。
【請求項55】
前記署名者は、各データストリームの各ブロックに対する部分ハッシュ値を計算して、多層ハッシュチェーンを計算することを特徴とする請求項46に記載のシステム。
【請求項56】
前記データストリーム生成者は、前記署名されたデータストリームを受信し、各署名されたデータストリームのブロックごとに、前記部分ハッシュ値を計算することを特徴とする請求項55に記載のシステム。
【請求項57】
前記受信者は、前記中間データストリームを受信し、前記中間データストリームのブロックごとに、前記部分ハッシュ値を再計算することを特徴とする請求項55に記載のシステム。
【請求項58】
前記署名者は、
前記元データストリームごとに、Merkle木を生成し、
前記Merkle木の各々の根に対応する値を計算し、
前記Merkle木の根の値をハッシュすることによって、最終的な根の値を生成することを特徴とする請求項46に記載のシステム。
【請求項59】
前記データストリーム生成者は、
前記署名されたデータストリームを受信し、
署名されたデータストリームごとに、前記削除されるブロックに対応する前記Merkle木の葉に相当する頂点の集合を決定し、
前記Merkle木において任意の頂点対が兄弟である場合、該頂点対における2つの頂点を該2つの頂点の親に置き換え、
前記Merkle木において任意の頂点対が兄弟でない場合、該頂点に対応する前記Merkle木の値を計算することを特徴とする請求項58に記載のシステム。
【請求項60】
前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項59に記載の方法。
【請求項61】
前記受信者は、前記中間データストリームを受信し、各Merkle木の根の値を再計算することを特徴とする請求項58に記載のシステム。
【請求項62】
元データストリームに署名する方法を実行するためのプログラムコードを含むコンピュータプログラム製品であって、
前記方法は、
少なくとも1つの元データストリームを複数のブロックに分解する工程と、
前記署名されたデータストリームのブロックについての部分ハッシュ値と、前記元データストリームについて生成されたMerkle木の根に関連する値と、各データストリームの各ブロックの部分ハッシュ値から計算された多層ハッシュチェーンと、それぞれが該元データストリームに対応するMerkle木の根の値をハッシュすることによって計算された最終的な根の値とからなるグループから選択された補助情報を計算する工程と、
前記補助情報に基づいて、各ブロックの認証情報を計算する工程と、
前記元データストリームと前記認証情報とを含む署名されたデータストリームを生成する工程と、
前記元データストリームを検閲せずに、任意のブロックを適応的に削除することによって、中間データストリームを生成する工程とを含み、
前記中間データストリームは、受信者によって認証可能であることを特徴とするコンピュータプログラム製品。
【請求項63】
電子署名を認証に使用することを特徴とする請求項62に記載のコンピュータプログラム製品。
【請求項64】
前記電子署名は、前記元データストリームのブロックの最終ハッシュ値に適用されることを特徴とする請求項63に記載の方法。
【請求項65】
メッセージ認証符号を認証に使用することを特徴とする請求項62に記載のコンピュータプログラム製品。
【請求項66】
前記メッセージ認証符号は、前記元データストリームのブロックの最終ハッシュ値に適用されることを特徴とする請求項65に記載の方法。
【請求項67】
前記補助情報は、署名者において計算されることを特徴とする請求項62に記載の方法。
【請求項68】
前記補助情報は、中間者において計算されることを特徴とする請求項62に記載の方法。
【請求項69】
元データストリームについて、署名したデータストリームから任意のブロックを適応的に削除する方法を実行するためのプログラムコードを含むコンピュータプログラム製品であって、
前記方法は、
前記元データストリームを検閲せずに、前記署名されたデータストリームにおいて送信されるデータストリームブロックを決定する工程と、
中間データストリームを生成することによって、前記署名されたデータストリームにおいてその他のブロックを適応的に削除する工程と、
前記中間データストリームを受信者に送信して認証させる工程とを含むことを特徴とするコンピュータプログラム製品。
【請求項70】
前記方法は、前記署名されたデータストリームのブロックごとに、前記部分ハッシュ値及び補助ハッシュ値を計算する工程をさらに含むことを特徴とする請求項69に記載のコンピュータプログラム製品。
【請求項71】
前記中間データストリームは、送信されるデータストリームブロックと、前記削除されるブロックに対する前記補助ハッシュ値とを含むことを特徴とする請求項70に記載のコンピュータプログラム製品。
【請求項72】
前記部分ハッシュ値及び補助ハッシュ値を送信する工程をさらに含むことを特徴とする請求項70に記載の方法。
【請求項73】
前記方法は、
前記削除されるブロックに対応する前記Merkle木の葉に相当する頂点の集合を決定する工程と、
前記Merkle木において任意の頂点対が兄弟である場合、該頂点対における2つの頂点を該2つの頂点の親に置き換える工程と、
前記Merkle木において任意の頂点対が兄弟でない場合、頂点に対応する前記Merkle木の値を計算する工程とをさらに含むことを特徴とする請求項69に記載のコンピュータプログラム製品。
【請求項74】
前記中間データストリームは、送信されるデータストリームブロックと、前記削除されるブロックに対応するMerkle木の値とを含むことを特徴とする請求項73に記載のコンピュータプログラム製品。
【請求項75】
前記置き換え工程は、兄弟である頂点対がなくなるまで繰り返されることを特徴とする請求項73に記載の方法。
【請求項76】
前記中間データストリームは、異なるデータストリームから適応的に選択されたデータストリームブロックを含むことを特徴とする請求項69に記載のコンピュータプログラム製品。
【請求項77】
中間データストリームを認証する方法を実行するためのプログラムコードを含むコンピュータプログラム製品であって、
前記方法は、
元データブロックから生成されているが、一部のデータが削除されている前記中間データストリームにおいて、データストリームブロックを識別する工程と、
前記中間データストリームのブロックの補助情報を計算する工程であって、前記補助情報が、前記中間データストリームのブロックの部分ハッシュ値と、前記元データストリームについて生成されたMerkle木の根に関連する値と、多層ハッシュチェーンと、元データストリームについて生成されたMerkle木の根の値をハッシュすることによって計算された最終的な根の値とからなるグループから選択される工程と、
認証情報を検証する工程とを含むことを特徴とするコンピュータプログラム製品。
【請求項78】
電子署名を認証に使用することを特徴とする請求項77に記載のコンピュータプログラム製品。
【請求項79】
メッセージ認証符号を認証に使用することを特徴とする請求項77に記載のコンピュータプログラム製品。
【請求項80】
データ通信ネットワークにおけるサーバであって、プロセッサと、請求項62に記載のコンピュータプログラム製品とを含むことを特徴とするサーバ。
【請求項81】
データ通信ネットワークにおける中間ノードであって、プロセッサと、請求項69に記載のコンピュータプログラム製品とを含むことを特徴とする中間ノード。
【請求項82】
データ通信ネットワークにおける受信者であって、プロセッサと、請求項77に記載のコンピュータプログラム製品とを含むことを特徴とする受信者。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公表番号】特表2007−503134(P2007−503134A)
【公表日】平成19年2月15日(2007.2.15)
【国際特許分類】
【出願番号】特願2006−523251(P2006−523251)
【出願日】平成16年8月4日(2004.8.4)
【国際出願番号】PCT/US2004/025513
【国際公開番号】WO2005/017809
【国際公開日】平成17年2月24日(2005.2.24)
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Fターム(参考)】
【公表日】平成19年2月15日(2007.2.15)
【国際特許分類】
【出願日】平成16年8月4日(2004.8.4)
【国際出願番号】PCT/US2004/025513
【国際公開番号】WO2005/017809
【国際公開日】平成17年2月24日(2005.2.24)
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Fターム(参考)】
[ Back to top ]