(57)【要約】【課題】ブロードキャスト暗号化およびステートレス・レシーバの鍵取消の方法を提供すること。【解決手段】ツリーを使用して、ブロードキャスト・コンテンツ暗号化システムのステートレス・レシーバを部分集合に分割する。分割の２つの異なる方法を開示する。取り消されたレシーバの集合を識別する時に、取り消されたレシーバによって、互いに素な部分集合による取り消されていないレシーバの比較的小さいカバーが定義される。部分集合に関連する部分集合鍵を使用して、セッション鍵を暗号化し、このセッション鍵を使用して、ブロードキャスト・コンテンツを暗号化する。取り消されていないレシーバだけが、セッション鍵を暗号化解除することができ、したがって、コンテンツを暗号化解除することができる。【特許請求の範囲】
【請求項１】
ブロードキャスト暗号化の方法であって、
ユーザのグループの各ユーザに、めいめいの私用情報Ｉｕを割り当てることと、
少なくとも１つのセッション暗号化鍵Ｋを選択することと、
取消済み集合Ｒに含まれないユーザを、関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍに分割することと、
セッション鍵Ｋのｍ個の暗号化された版を与えるために部分集合鍵Ｌｉ１、…、Ｌｉｍを用いてセッション鍵Ｋを暗号化することと
を含む方法。
【請求項２】
ユーザをグループＳ１、…、Ｓｗに分割することをさらに含み、「ｗ」が整数であり、グループが、ツリー内のサブツリーを確立する、請求項１に記載の方法。
【請求項３】
各部分集合Ｓｉ１、…、Ｓｉｍが、あるノードｖｉをルートとするサブツリーのすべての葉を含み、少なくとも、サブツリー内の各ノードが、めいめいの部分集合鍵に関連する、請求項２に記載の方法。
【請求項４】
コンテンツが、ヘッダを定義する少なくとも１つのメッセージでユーザに供給され、ヘッダが、多くともｒ×ｌｏｇ（Ｎ／ｒ）個の部分集合鍵および暗号化を含み、ｒが、取消済み集合Ｒに含まれるユーザの数であり、Ｎが、ユーザの総数である、請求項３に記載の方法。
【請求項５】
取消済み集合Ｒが、スパニング・ツリーを定義し、スパニング・ツリーのノードに付加されたルートを有するサブツリーが、部分集合を定義する、請求項３に記載の方法。
【請求項６】
ツリーが、ルートおよび複数のノードを含み、各ノードが、少なくとも１つの関連するラベルを有し、各部分集合が、他のノードｖｊをルートとし、あるノードｖｉから下降するサブツリーに含まれない、ノードｖｉをルートとするサブツリー内のすべての葉を含む、請求項２ないし５のいずれかに記載の方法。
【請求項７】
コンテンツが、ヘッダを定義する少なくとも１つのメッセージでユーザに供給され、ヘッダが、多くとも２ｒ−１個の部分集合鍵および暗号化を含み、ｒが、取消済み集合Ｒに含まれるユーザの数である、請求項６に記載の方法。
【請求項８】
各ユーザが、．５ｌｏｇ２  Ｎ  ＋  ．５ｌｏｇ  Ｎ  ＋  １個の鍵を保管しなければならず、Ｎが、ユーザの総数である、請求項６または７に記載の方法。
【請求項９】
コンテンツが、少なくとも１つのメッセージでユーザに供給され、各ユーザが、多くともｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理し、Ｎが、ユーザの総数である、請求項６ないし８のいずれかに記載の方法。
【請求項１０】
取消済み集合Ｒが、スパニング・ツリーを定義し、
カバー・ツリーＴをスパニング・ツリーとして初期化することと、
カバー・ツリーＴが多くとも１つのノードを有するまで、繰り返して、カバー・ツリーＴからノードを除去し、ノードをカバーに追加することと
を含む、請求項６ないし９のいずれかに記載の方法。
【請求項１１】
各ノードが、おそらくはその上位の少なくとも１つによって誘導される少なくとも１つのラベルを有し、各ユーザが、ユーザとルートとの間の直接パスからぶら下がるノードであって、直接パスに含まれるノードではないすべてのノードからラベルを割り当てられる、請求項６ないし１０のいずれかに記載の方法。
【請求項１２】
コンピュータ・システムにロードされ実行される時に、請求項１ないし１１のいずれかに記載の方法のステップを前記コンピュータ・システムに実行させるコンピュータ・プログラム・コードを含むコンピュータ・プログラム。
【請求項１３】
ブロードキャスト暗号化の装置であって、
ユーザのグループの各ユーザに、めいめいの私用情報Ｉｕを割り当てる手段と、
少なくとも１つのセッション暗号化鍵Ｋを選択する手段と、
取消済み集合Ｒに含まれないユーザを、関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍに分割する手段と、
セッション鍵Ｋのｍ個の暗号化された版を与えるために部分集合鍵Ｌｉ１、…、Ｌｉｍを用いてセッション鍵Ｋを暗号化する手段と
を含む装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的に、暗号化鍵を使用するブロードキャスト・データ暗号化に関する。
【背景技術】
【０００２】
米国特許第６，１１８，８７３号に、ブロードキャストされる音楽、ビデオ、および他のコンテンツを暗号化するシステムが開示されている。それに示されているように、許可されたプレイヤ−レコーダだけが、コンテンツのベンダによって確立される規則に従ってのみ、コンテンツを再生し、かつ／またはコピーすることができる。この形で、現在コンテンツ・プロバイダが毎年数十億ドルを費やすコンテンツの海賊コピーを防ぐことができる。
【０００３】
上述の特許で開示された暗号化方法では、許可されるプレイヤ−レコーダが、装置鍵の行列から、ソフトウェアによって実施される装置鍵を発行される。鍵は、互いに同時にまたは経時的に発行することができるが、どの場合でも、プレイヤ−レコーダは、行列の列ごとに複数の装置鍵を有しないと仮定される。２つの装置が、同一の列の同一の鍵を共用することができるが、２つの装置が行列のすべての列からの正確に同一の集合鍵を共用する可能性は、鍵がランダムに割り当てられる時に、非常に低い。これらの鍵が、コンテンツの暗号化解除に使用される。
【０００４】
装置（およびその鍵）が、故意にまたは誤りによって危険にさらされる場合に、その装置の鍵を取り消すことが必要になる。鍵の集合を取り消すことによって、有効に、危険にさらされた装置（およびそのクローンのすべて）が、取消の後に作られるコンテンツを再生するように動作可能でなくなる。上で開示された特許では、取消のそれぞれについて約３２０メッセージ・バイトが必要である。これは有効ではあるが、効率のために、取消メッセージの長さをさらに減らすことが望ましい。
【０００５】
上で参照した特許で開示されたシステムは、有効であるが、メッセージのヘッダ区域（その特許で「媒体鍵ブロック」と称する）のサイズ制約のゆえに、比較的限られた（ＤＶＤ−Ａｕｄｉｏなどの３Ｍヘッダについて１００００個）数の取消だけを、システムの寿命の中で行うことができる。この数は、ヘッダ・サイズを増やすことによって増やすことができるが、追加の取消が、新たに作られる装置だけに適用可能であり、ヘッダ・サイズを増やす前に作られた装置には適用可能でない。「古い」装置と「新しい」装置の多数の取消を実行できる、すなわち、ステートレス・レシーバを説明できることが望ましい。また、複数のデバイスが、上で参照した特許を与えられた発明では、危険にさらされた装置と特定の鍵を共用することができるので、装置鍵の集合を取り消すことによって、罪のない装置によって保持される鍵のいくつかが取り消される可能性がある。「善良な」装置を誤って取り消す可能性をさらに下げ、好ましくは０にすることが望ましい。
【０００６】
さらに、本発明は、「ステートレス」レシーバすなわち、危険にさらされた装置に対する対応策を受け入れるために、ブロードキャストの間で暗号化状態を必ずしも更新しないレシーバという困難なシナリオに対処する。たとえば、有料チャネルに加入したテレビジョンが、更新した暗号化データがシステムを介してブロードキャストされる時間の期間中に、そのセットトップ・ボックスの電源を断たれる場合がある。そのような装置は、電源を再投入された後にそれ自体を更新できない場合に、「ステートレス」にされ、したがって、将来のコンテンツ暗号化解除に必要な更新を所有しない。
【０００７】
さらに、ＣＤおよびＤＶＤなど、公衆に販売され、許可されないコピーを防ぐことが望ましい媒体のコンテンツを保護する必要が高まっている。そのようなシステムのレコーダは、通常、プレイヤと相互作用せず、プレイヤは、プレイヤが売られたすべてのディスクを受け取るのではないので、可能なすべての暗号化データ更新を得ない。その結果、本明細書で理解されるように、売られた媒体のコンテンツ保護は、ステートレス・レシーバへのブロードキャスト暗号化の問題の例になる。
【０００８】
さらに、かなりの数の「悪い」製造業者（すなわち、合法的または非合法に鍵を入手するが、どの場合でも、その鍵を有する多数の許可されない装置を作る製造業者）の存在が、問題になる可能性がある。潜在的に多数の「悪い」製造業者を捕まえることが望ましい。
【０００９】
ブロードキャスト暗号化の他の方法に、Fiat et al.、「BroadcastEncryption」、Crypto '93、LNCS vol. 839、257〜270ページ、1994年に記載の方法が含まれる。この方法では、任意の数のレシーバを、それらの大半「ｔ」個が互いに共謀する限り、除去することが想定されている。しかし、Fiatet al.の方法では、比較的大きいメッセージ長、レシーバで保管される比較的多数の鍵が必要であり、各レシーバが、複数の暗号化解除動作を実行しなければならない。さらに、Fiatet al.の方法では、ステートレス・レシーバのシナリオが想定されていない。先験的に、共謀することができるレシーバの数を仮定することを避ける必要がある。また、性能を最適化するために、メッセージ・サイズおよび保管される鍵の数を最小にし、レシーバによって実行されなければならない暗号化解除動作の数を最小にしなければならない。
【００１０】
Fiat et al.のシステムに似た、他の暗号化システムは、ステートレス・レシーバのシナリオを提供せず、したがって、記録された媒体のコンテンツ保護に、あるがままで効果的に適用することができない。そのようなシステムの例に、Wallneret al.、「Key Management for Multicast: Issues and Architectures」、IETF draftwallner-key、1997年；Wong et al.、「Secure Group Communication Using Key Graphs」、SIGCOMM1998；Canetti et al.、「Multicast Security: A Taxonomv and Some EfficientConstructions」、Proc. of INFOCOM '99、vol. 2、708〜716ページ、1999年；Canetti et al.、「EfficientCommunication-Storage Tradeoffs for Multicast Encryption」、Eurocrypt 1999、459〜474ページ；および、McGrewet al.、「Key Establishment in Large Dynamic Groups Using One-Way Function Trees」、IEEETransactions on Software Engineering（1998年）に提出、で開示されたツリーベースの論理鍵階層システムが含まれる。
【００１１】
Wallner et al.およびWong et al.の方法に関するさらなる特定性について、鍵は、２分木の各ノードに独立のラベルを割り当てることによって割り当てられる。残念ながら、参照された方法では、ラベルのいくつかが、すべての取消で変化する。明らかに、そのままでは、この方法は、ステートレス・レシーバのシナリオに不適当である。取消の一群が、すべてのノードの単一のラベル変化に関連する場合であっても、Wallneret al.およびWong et al.の参照された方法は、レシーバでの少なくともｌｏｇ  Ｎ回の暗号化解除およびｒ  ｌｏｇ  Ｎ回の暗号化の送信を必要とする（ｒは、取り消される装置の数、Ｎは、システム内のレシーバの総数である）が、残念ながら、これはかなり大きい数である。
【特許文献１】米国特許第６，１１８，８７３号
【非特許文献１】Fiat et al.、「Broadcast Encryption」、Crypto'93、LNCS vol. 839、257〜270ページ、1994年
【非特許文献２】Wallner et al.、「Key Management forMulticast: Issues and Architectures」、IETF draft wallner-key、1997年
【非特許文献３】Wong et al.、「Secure Group CommunicationUsing Key Graphs」、SIGCOMM 1998
【非特許文献４】Canetti et al.、「Multicast Security:A Taxonomv and Some Efficient Constructions」、Proc. of INFOCOM '99、vol. 2、708〜716ページ、1999年
【非特許文献５】Canetti et al.、「EfficientCommunication-Storage Tradeoffs for Multicast Encryption」、Eurocrypt 1999、459〜474ページ
【非特許文献６】McGrew et al.、「Key Establishment inLarge Dynamic Groups Using One-Way Function Trees」、IEEE Transactions onSoftware Engineering（1998年）に提出
【発明の開示】
【発明が解決しようとする課題】
【００１２】
暗号化鍵を使用してブロードキャスト・データを暗号化する方法および装置を提供することである。
【課題を解決するための手段】
【００１３】
したがって、本発明は、ブロードキャスト暗号化の方法であって、ユーザのグループの各ユーザに、めいめいの私用情報Ｉｕを割り当てることと、少なくとも１つのセッション暗号化鍵Ｋを選択することと、取消済み集合Ｒに含まれないユーザを、関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍに分割することと、セッション鍵Ｋのｍ個の暗号化された版を与えるために部分集合鍵Ｌｉ１、…、Ｌｉｍを用いてセッション鍵Ｋを暗号化することとを含む方法を提供する。
【００１４】
この方法は、ユーザをグループＳ１、…、Ｓｗに分割することをさらに含み、「ｗ」が整数であり、グループが、ツリー内のサブツリーを確立することが好ましい。
【００１５】
ツリーが、完全な２分木であることが好ましい。
【００１６】
この方法は、セッション鍵を暗号化解除するために私用情報Ｉｕを使用することをさらに含むことが好ましい。
【００１７】
適当に、暗号化解除の動作が、ユーザが、部分集合Ｓｉｊに属するように情報ｉｊを使用することと、ユーザの私用情報を使用して部分集合鍵Ｌｉｊを検索することとを含む。
【００１８】
各部分集合Ｓｉ１、…、Ｓｉｍが、あるノードｖｉをルートとするサブツリーのすべての葉を含み、少なくとも、サブツリー内の各ノードが、めいめいの部分集合鍵に関連することが好ましい。
【００１９】
コンテンツが、ヘッダを定義する少なくとも１つのメッセージでユーザに供給され、ヘッダが、多くともｒ×ｌｏｇ（Ｎ／ｒ）個の部分集合鍵および暗号化を含み、ｒが、取消済み集合Ｒに含まれるユーザの数であり、Ｎが、ユーザの総数であることが好ましい。
【００２０】
各ユーザが、ｌｏｇ  Ｎ個の鍵を保管しなければならず、Ｎが、ユーザの総数であることが好ましい。
【００２１】
コンテンツが、少なくとも１つのメッセージでユーザに供給され、各ユーザが、多くともｌｏｇ  ｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理し、Ｎが、ユーザの総数であることが好ましい。
【００２２】
取消済み集合Ｒが、スパニング・ツリーを定義し、スパニング・ツリーのノードに付加されたルートを有するサブツリーが、部分集合を定義することが好ましい。
【００２３】
ツリーが、ルートおよび複数のノードを含み、各ノードが、少なくとも１つの関連するラベルを有し、各部分集合が、他のノードｖｊをルートとし、あるノードｖｉから下降するサブツリーに含まれない、ノードｖｉをルートとするサブツリー内のすべての葉を含むことが好ましい。
【００２４】
コンテンツが、ヘッダを定義する少なくとも１つのメッセージでユーザに供給され、ヘッダが、多くとも２ｒ−１個の部分集合鍵および暗号化を含み、ｒが、取消済み集合Ｒに含まれるユーザの数であることが好ましい。
【００２５】
各ユーザが、．５ｌｏｇ２  Ｎ  ＋  ．５ｌｏｇ  Ｎ  ＋  １個の鍵を保管しなければならず、Ｎが、ユーザの総数であることが好ましい。
【００２６】
コンテンツが、少なくとも１つのメッセージでユーザに供給され、各ユーザが、多くともｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理し、Ｎが、ユーザの総数であることが好ましい。
【００２７】
取消済み集合Ｒが、スパニング・ツリーを定義し、方法が、カバー・ツリーＴをスパニング・ツリーとして初期化することと、カバー・ツリーＴが多くとも１つのノードを有するまで、繰り返して、カバー・ツリーＴからノードを除去し、ノードをカバーに追加することとを含むことが好ましい。
【００２８】
各ノードが、おそらくはその上位の少なくとも１つによって誘導される少なくとも１つのラベルを有し、各ユーザが、ユーザとルートとの間の直接パスからぶら下がるノードであって、直接パスに含まれるノードではないすべてのノードからラベルを割り当てられることが好ましい。
【００２９】
ラベルが、擬似乱数シーケンス・ジェネレータを使用して部分集合に割り当てられ、暗号化解除の動作が、擬似乱数シーケンス・ジェネレータを評価することを含むことが好ましい。
【００３０】
コンテンツが、暗号関数ＥＬを含むヘッダを有する少なくとも１つのメッセージでユーザに供給され、方法が、暗号関数ＥＬの接頭部切捨を含むことが好ましい。
【００３１】
ツリーが、ルートおよび複数のノードを含み、各ノードが、関連付けられた鍵を有し、各ユーザが、ユーザを表す葉とルートとの間の直接パスに含まれるすべてのノードから鍵を割り当てられることが好ましい。
【００３２】
コンテンツが、複数の部分を定義する少なくとも１つのメッセージでユーザに供給され、各部分が、めいめいのセッション鍵を用いて暗号化されることが好ましい。
【００３３】
本発明は、コンピュータ・プログラム装置であって、複数の部分集合鍵を識別するためにツリーにアクセスする論理手段と、セッション鍵を用いてメッセージを暗号化する論理手段と、セッション鍵の暗号化された版を与えるために部分集合鍵のそれぞれについて少なくとも１回、セッション鍵を暗号化する論理手段と、メッセージのヘッダ内でセッション鍵の暗号化された版を複数のステートレス・レシーバに送信する論理手段とを含む、コンピュータによって使用可能な命令のプログラムを含むコンピュータ・プログラム記憶装置を含むコンピュータ・プログラム装置を適当に提供する。
【００３４】
コンピュータ・プログラム装置が、取消済み集合Ｒに含まれないレシーバを、関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍに分割する論理手段をさらに含むことが好ましい。
【００３５】
コンピュータ・プログラム装置が、ユーザをグループＳ１、…、Ｓｗに分割する論理手段をさらに含み、「ｗ」が整数であり、グループが、ツリー内のサブツリーを確立することが好ましい。
【００３６】
コンピュータ・プログラム装置が、セッション鍵を暗号化解除するために私用情報Ｉｕを使用する論理手段をさらに含むことが好ましい。
【００３７】
暗号化解除する手段が、レシーバが部分集合Ｓｉｊに属するように情報ｉｊを使用し、レシーバの私用情報から鍵Ｌｉｊを検索する論理手段を含むことが好ましい。
【００３８】
各部分集合Ｓｉ１、…、Ｓｉｍが、あるノードｖｉをルートとするサブツリー内のすべての葉を含み、少なくとも、サブツリー内の各ノードが、めいめいの部分集合鍵に関連することが好ましい。
【００３９】
論理手段が、ヘッダを定義する少なくとも１つのメッセージでレシーバにコンテンツを供給し、ヘッダが、多くともｒ×ｌｏｇ（Ｎ／ｒ）個の部分集合鍵および暗号化を含み、ｒが、取消済み集合Ｒに含まれるレシーバの数であり、Ｎが、レシーバの総数であることが好ましい。
【００４０】
各レシーバが、ｌｏｇ  Ｎ個の鍵を保管しなければならず、Ｎが、レシーバの総数であることが好ましい。
【００４１】
論理手段が、少なくとも１つのメッセージでレシーバにコンテンツを供給し、各レシーバが、多くともｌｏｇ  ｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理し、Ｎが、レシーバの総数であることが好ましい。
【００４２】
取消済み集合Ｒが、スパニング・ツリーを定義し、スパニング・ツリーのノードに付加されたルートを有するサブツリーが、部分集合を定義することが好ましい。
【００４３】
ツリーが、ルートおよび複数のノードを含み、各ノードが、少なくとも１つの関連するラベルを有し、各部分集合が、他のノードｖｊをルートとし、あるノードｖｉから下降するサブツリーに含まれない、ノードｖｉをルートとするサブツリー内のすべての葉を含むことが好ましい。
【００４４】
手段が、ヘッダを定義する少なくとも１つのメッセージでコンテンツをレシーバに供給し、ヘッダが、多くとも２ｒ−１個の部分集合鍵および暗号化を含み、ｒが、取消済み集合Ｒに含まれるレシーバの数であることが好ましい。
【００４５】
各レシーバが、．５ｌｏｇ２  Ｎ  ＋  ．５ｌｏｇ  Ｎ  ＋  １個の鍵を保管しなければならず、Ｎが、レシーバの総数であることが好ましい。
【００４６】
論理手段が、少なくとも１つのメッセージでレシーバにコンテンツを供給し、各レシーバが、多くともｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理し、Ｎが、レシーバの総数であることが好ましい。
【００４７】
取消済み集合Ｒが、スパニング・ツリーを定義し、コンピュータ・プログラム装置が、カバー・ツリーＴをスパニング・ツリーとして初期化する論理手段と、カバー・ツリーＴが多くとも１つのノードを有するまで、繰り返して、カバー・ツリーＴからノードを除去し、ノードをカバーに追加する論理手段とを含むことが好ましい。
【００４８】
論理手段が、擬似乱数シーケンス・ジェネレータを使用してレシーバにラベルを割り当て、ラベルが、部分集合鍵を誘導することが好ましい。
【００４９】
暗号化解除する手段が、擬似乱数シーケンス・ジェネレータを評価することを含むことが好ましい。
【００５０】
論理手段が、暗号関数ＥＬを含むヘッダを有する少なくとも１つのメッセージでレシーバにコンテンツを供給し、コンピュータ・プログラム装置が、暗号関数ＥＬの接頭部切捨の論理手段を含むことが好ましい。
【００５１】
ツリーが、ルートおよび複数のノードを含み、各ノードが、関連付けられた鍵を有し、論理手段が、各レシーバに、レシーバを表す葉とルートとの間の直接パスに含まれるすべてのノードから鍵を割り当てることが好ましい。
【００５２】
論理手段が、複数の部分を定義する少なくとも１つのメッセージでレシーバにコンテンツを供給し、各部分が、めいめいのセッション鍵を用いて暗号化されることが好ましい。
【００５３】
本発明は、コンピュータであって、ブロードキャスト・コンテンツを暗号化することと、ブロードキャスト・コンテンツを複数のステートレスな善良なレシーバおよび少なくとも１つの取り消されたレシーバとに送信することであって、各ステートレスな善良なレシーバが、コンテンツを暗号化解除でき、取り消されたレシーバが、コンテンツを暗号化解除できないように送信することとを含む方法動作をコンピュータに実行させる命令を用いてプログラムされたコンピュータを適当に提供する。
【００５４】
方法動作が、レシーバのグループの各レシーバに、めいめいの私用情報Ｉｕを割り当てることと、少なくとも１つのセッション暗号化鍵Ｋを選択することと、取消済み集合Ｒに含まれないすべてのレシーバを、関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍに分割することと、セッション鍵Ｋのｍ個の暗号化された版を与えるために部分集合鍵Ｌｉ１、…、Ｌｉｍを用いてセッション鍵Ｋを暗号化することとをさらに含むことが好ましい。
【００５５】
コンピュータが取り掛かる方法動作が、ユーザをグループＳ１、…、Ｓｗに分割することをさらに含み、「ｗ」が整数であり、グループが、ツリー内のサブツリーを確立することが好ましい。
【００５６】
ツリーが、完全な２分木であることが好ましい。
【００５７】
方法が、セッション鍵を暗号化解除するために私用情報Ｉｕを使用することを含むことが好ましい。
【００５８】
コンピュータが取り掛かる暗号化解除の動作が、レシーバが部分集合Ｓｉｊに属するように情報ｉｊを使用することと、レシーバの私用情報を使用して鍵Ｌｉｊを検索することを含むことが好ましい。
【００５９】
各部分集合Ｓｉ１、…、Ｓｉｍが、あるノードｖｉをルートとするサブツリー内のすべての葉を含み、少なくとも、サブツリー内の各ノードが、めいめいの部分集合鍵に関連することが好ましい。
【００６０】
コンテンツが、ヘッダを定義する少なくとも１つのメッセージでレシーバに供給され、ヘッダが、多くともｒ×ｌｏｇ（Ｎ／ｒ）個の部分集合鍵および暗号化を含み、ｒが、取消済み集合Ｒに含まれるレシーバの数であり、Ｎが、レシーバの総数であることが好ましい。
【００６１】
各レシーバが、ｌｏｇ  Ｎ個の鍵を保管しなければならず、Ｎが、レシーバの総数であることが好ましい。
【００６２】
コンテンツが、少なくとも１つのメッセージでレシーバに供給され、各レシーバが、多くともｌｏｇ  ｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理し、Ｎが、レシーバの総数であることが好ましい。
【００６３】
取消済み集合Ｒが、スパニング・ツリーを定義し、スパニング・ツリーのノードに付加されたルートを有するサブツリーが、部分集合を定義することが好ましい。
【００６４】
ツリーが、ルートおよび複数のノードを含み、各ノードが、少なくとも１つの関連するラベルを有し、各部分集合が、他のノードｖｊをルートとし、あるノードｖｉから下降するサブツリーに含まれない、ノードｖｉをルートとするサブツリー内のすべての葉を含むことが好ましい。
【００６５】
コンテンツが、ヘッダを定義する少なくとも１つのメッセージでレシーバに供給され、ヘッダが、多くとも２ｒ−１個の部分集合鍵および暗号化を含み、ｒが、取消済み集合Ｒに含まれるレシーバの数であることが好ましい。
【００６６】
各レシーバが、．５ｌｏｇ２  Ｎ  ＋  ．５ｌｏｇ  Ｎ  ＋  １個の鍵を保管しなければならず、Ｎが、レシーバの総数であることが好ましい。
【００６７】
コンテンツが、少なくとも１つのメッセージでレシーバに供給され、各レシーバが、多くともｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理し、Ｎが、レシーバの総数であることが好ましい。
【００６８】
取消済み集合Ｒが、スパニング・ツリーを定義し、コンピュータが取り掛かる方法動作が、カバー・ツリーＴをスパニング・ツリーとして初期化することと、カバー・ツリーＴが多くとも１つのノードを有するまで、繰り返して、カバー・ツリーＴからノードを除去し、ノードをカバーに追加することとを含むことが好ましい。
【００６９】
コンピュータが、擬似乱数シーケンス・ジェネレータを使用してツリーからレシーバにノード・ラベルを割り当てることが好ましい。
【００７０】
コンピュータが取り掛かる暗号化解除の動作が、擬似乱数シーケンス・ジェネレータを評価することを含むことが好ましい。
【００７１】
コンテンツが、暗号関数ＥＬを含むヘッダを有する少なくとも１つのメッセージでレシーバに供給され、コンピュータが取り掛かる方法動作が、暗号関数ＥＬの接頭部切捨を含むことが好ましい。
【００７２】
コンテンツが、複数の部分を定義する少なくとも１つのメッセージでレシーバに供給され、各部分が、めいめいのセッション鍵を用いてコンピュータによって暗号化されることが好ましい。
【００７３】
各ノードが、ノードの各上位がめいめいのラベルを誘導する、複数のラベルを有し、各ユーザが、ユーザとルートとの間の直接パスからぶら下がるノードであって、直接パスに含まれるノードではないすべてのノードからラベルを割り当てられることが好ましい。
【００７４】
本発明は、ブロードキャスト暗号化の方法であって、ユーザのグループの各ユーザに、めいめいの私用情報Ｉｕを割り当てることと、少なくとも１つのセッション暗号化鍵Ｋを選択することと、すべてのユーザをグループＳ１、…、Ｓｗに分割することであって、「ｗ」が整数であり、グループが、ツリー内のサブツリーを確立する、分割することと、取消済み集合Ｒに含まれないユーザを、関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍに分割することと、セッション鍵Ｋのｍ個の暗号化された版を与えるために部分集合鍵Ｌｉ１、…、Ｌｉｍを用いてセッション鍵Ｋを暗号化することとを含み、ツリーが、ルートおよび複数のノードを含み、各ノードが、少なくとも１つの関連するラベルを有し、各部分集合が、他のノードｖｊをルートとし、あるノードｖｉから下降するサブツリーに含まれない、ノードｖｉをルートとするサブツリー内のすべての葉を含む、方法を適当に含む。
【００７５】
本発明は、マルチキャスト・システム内の潜在的にステートレスなレシーバであって、少なくとも１つのデータ記憶装置であって、レシーバを表す葉を有するツリーのルートとレシーバとの間の直接パスに含まれるのではなく直接パスからぶら下がるノードの、あるノードｖｉによって誘導される複数のラベルを保管する少なくとも１つのデータ記憶装置を含み、葉の上位が、レシーバを表し、ラベルが、ラベルから導出される部分集合鍵を暗号化解除するのにレシーバによって使用可能な、レシーバの私用情報Ｉｕを確立するレシーバを適当に含む。
【００７６】
レシーバが、他の部分集合鍵を計算せずに、擬似乱数関数を評価することによって、ノードｖｉをルートとする直接パス集合を除くすべての集合の部分集合鍵を計算することが好ましい。
【００７７】
レシーバが、少なくとも１つの部分集合鍵を使用してセッション鍵を暗号化解除し、セッション鍵が、コンテンツの暗号化解除に有用であることが好ましい。
【００７８】
本発明は、コンテンツのレシーバであって、めいめいの私用情報Ｉｕを保管する手段と、複数の部分集合鍵を用いて暗号化される少なくとも１つのセッション暗号化鍵Ｋを受け取る手段であって、セッション鍵が、コンテンツを暗号化する、受け取る手段と、コンテンツを再生するためにセッション鍵Ｋを暗号化解除できるようにするために、私用情報を使用して少なくとも１つの部分集合鍵を得る手段とを含むレシーバを適当に含む。
【００７９】
レシーバが、グループＳ１、…、Ｓｗの集合の１つに分割され、「ｗ」が整数であり、グループが、ノードおよび葉を定義するツリー内のサブツリーを確立することが好ましい。
【００８０】
部分集合Ｓｉ１、…、Ｓｉｍが、カバーを定義するグループＳ１、…、Ｓｗの集合から導出されることが好ましい。
【００８１】
レシーバが、ヘッダを定義する少なくとも１つのメッセージでコンテンツを受信し、ヘッダが、多くともｒ×ｌｏｇ（Ｎ／ｒ）個の部分集合鍵および暗号化を含み、ｒが、取消済み集合Ｒに含まれるレシーバの数であり、Ｎが、レシーバの総数であることが好ましい。
【００８２】
レシーバが、ｌｏｇ  Ｎ個の鍵を保管しなければならず、Ｎが、レシーバの総数であることが好ましい。
【００８３】
レシーバが、ヘッダを定義する少なくとも１つのメッセージでコンテンツを受信し、レシーバが、多くともｌｏｇ  ｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理し、Ｎが、レシーバの総数であることが好ましい。
【００８４】
取消済み集合Ｒが、スパニング・ツリーを定義し、スパニング・ツリーのノードに付加されたルートを有するサブツリーが、部分集合を定義することが好ましい。
【００８５】
ツリーが、ルートおよび複数のノードを含み、各ノードが、少なくとも１つの関連するラベルを有し、各部分集合が、他のノードｖｊをルートとし、あるノードｖｉから下降するサブツリーに含まれない、ノードｖｉをルートとするサブツリー内のすべての葉を含むことが好ましい。
【００８６】
レシーバが、多くとも２ｒー１個の部分集合鍵および暗号化を含むヘッダを有するメッセージでコンテンツを受信し、ｒが、取消済み集合Ｒに含まれるレシーバの数であることが好ましい。
【００８７】
レシーバが、．５ｌｏｇ２  Ｎ  ＋  ．５ｌｏｇ  Ｎ  ＋  １個の鍵を保管しなければならず、Ｎが、レシーバの総数であることが好ましい。
【００８８】
コンテンツが、少なくとも１つのメッセージでレシーバに供給され、レシーバが、多くともｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理し、Ｎが、レシーバの総数であることが好ましい。
【００８９】
レシーバが、擬似乱数シーケンス・ジェネレータを評価することによって部分集合鍵を暗号化解除することが好ましい。
【００９０】
本発明は、コンテンツのレシーバであって、めいめいの私用情報Ｉｕを保管するデータ・ストレージと、複数の部分集合鍵を用いて暗号化された少なくとも１つのセッション暗号化鍵Ｋを受信する処理装置とを含み、セッション鍵が、コンテンツを暗号化し、処理装置が、コンテンツを再生するためにセッション鍵Ｋを暗号化解除できるように、私用情報を使用して少なくとも１つの部分集合鍵を得る、レシーバを適当に含む。
【００９１】
レシーバが、グループＳ１、…、Ｓｗの集合の１つに分割され、「ｗ」が整数であり、グループが、ツリー内のサブツリーを確立することが好ましい。
【００９２】
部分集合Ｓｉ１、…、Ｓｉｍが、カバーを定義するグループＳ１、…、Ｓｗの集合から導出されることが好ましい。
【００９３】
レシーバが、ヘッダを定義する少なくとも１つのメッセージでコンテンツを受信し、ヘッダが、多くともｒ×ｌｏｇ（Ｎ／ｒ）個の部分集合鍵および暗号化を含み、ｒが、取消済み集合Ｒに含まれるレシーバの数であり、Ｎが、レシーバの総数であることが好ましい。
【００９４】
レシーバが、ｌｏｇ  Ｎ個の鍵を保管しなければならず、Ｎが、レシーバの総数であることが好ましい。
【００９５】
レシーバが、ヘッダを定義する少なくとも１つのメッセージでコンテンツを受信し、レシーバが、多くともｌｏｇ  ｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理し、Ｎが、レシーバの総数であることが好ましい。
【００９６】
１つの取消済み集合Ｒが、スパニング・ツリーを定義し、スパニング・ツリーのノードに付加されたルートを有するサブツリーが、部分集合を定義することが好ましい。
【００９７】
ツリーが、ルートおよび複数のノードを含み、各ノードが、少なくとも１つの関連するラベルを有し、各部分集合が、他のノードｖｊをルートとし、あるノードｖｉから下降するサブツリーに含まれない、ノードｖｉをルートとするサブツリー内のすべての葉を含むことが好ましい。
【００９８】
レシーバが、多くとも２ｒー１個の部分集合鍵および暗号化を含むヘッダを有するメッセージでコンテンツを受信し、ｒが、取消済み集合Ｒに含まれるレシーバの数であることが好ましい。
【００９９】
レシーバが、．５ｌｏｇ２  Ｎ  ＋  ．５ｌｏｇ  Ｎ  ＋  １個の鍵を保管しなければならず、Ｎが、レシーバの総数であることが好ましい。
【０１００】
コンテンツが、少なくとも１つのメッセージでレシーバに供給され、レシーバが、多くともｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理し、Ｎが、レシーバの総数であることが好ましい。
【０１０１】
レシーバが、擬似乱数シーケンス・ジェネレータを評価することによって部分集合鍵を暗号化解除することが好ましい。
【０１０２】
本発明は、一般形＜［ｉ１、ｉ２、…、ｉｍ、ＥＬｉ１（Ｋ）、ＥＬｉ２（Ｋ）、…、ＥＬｉｍ（Ｋ）］、ＦＫ（Ｍ）＞のコンテンツのメッセージを保持する媒体であって、Ｋが、セッション鍵であり、ＦＫが、暗号化プリミティブであり、ＥＫが、暗号化プリミティブであり、Ｌｉが、暗号化ブロードキャスト・システム内のレシーバの部分集合に関連する部分集合鍵であり、Ｍが、メッセージ本体であり、ｉ１、ｉ２、…、ｉｍが、カバーを定義するツリー・ノード部分集合である、媒体を適当に含む。
【０１０３】
暗号化プリミティブＦＫが、メッセージ本体Ｍを、セッション鍵Ｋによって生成されるストリーム暗号とＸＯＲすることによって実施されることが好ましい。
【０１０４】
ＥＬが、ブロック暗号の接頭部切捨指定であり、ｌが、その長さがＥＬのブロック長と等しいランダム・ストリングを表し、Ｋが、ＦＫの短い鍵であり、メッセージが、
＜［ｉ１、ｉ２、…、ｉｍ、Ｕ、［Ｐｒｅｆｉｘ−Ｋ−ＥＬｉ１（Ｕ）］／Ｋ、…、［Ｐｒｅｆｉｘ−Ｋ−ＥＬｉｍ（Ｕ）］／Ｋ］、ＦＫ（Ｍ）＞
の形であることが好ましい。
【０１０５】
ｌ／ｉｊが、暗号化され、メッセージが、
＜［ｉ１、ｉ２、…、ｉｍ、Ｕ、［Ｐｒｅｆｉｘ−Ｌ−ＥＬｉ１（Ｕ／ｉ１）］／Ｋ、…、［Ｐｒｅｆｉｘ−Ｌ−ＥＬｉｍ（Ｕ／ｉｍ）］／Ｋ］、ＦＫ（Ｍ）＞
の形であることが好ましい。
【０１０６】
部分集合鍵が、ルートおよび複数のノードを含むツリーから導出され、各ノードが、少なくとも１つの関連するラベルを有し、各部分集合が、他のノードｖｊをルートとし、あるノードｖｉから下降するサブツリーに含まれない、ノードｖｉをルートとするサブツリー内のすべての葉を含むことが好ましい。
【０１０７】
部分集合鍵が、ルートおよび複数のノードを含むツリーから導出され、各ノードが、少なくとも１つの関連するラベルを有し、各部分集合が、あるノードｖｉをルートとするサブツリー内のすべての葉を含み、少なくとも、サブツリー内の各ノードが、めいめいの部分集合鍵に関連することが好ましい。
【０１０８】
分割の動作が、システム・コンピュータから分離されたレシーバのシステム内のシステム・コンピュータによって取り掛かられることが好ましい。
【０１０９】
分割の動作が、レシーバ・コンピュータによって取り掛かられることが好ましい。
【０１１０】
レシーバが、カバー内の部分集合を導出することが好ましい。
【０１１１】
本発明に、適当に、本明細書に記載の発明的論理に取り掛かるコンピュータ・システムが含まれる。本発明は、本発明の論理を保管し、論理を実行するためにプロセッサによってアクセスすることができるコンピュータ・プログラム製品で実施することもできる。また、本発明に、適当に、下で開示する論理に従うコンピュータ実施される方法を含めることができる。
【０１１２】
本発明には、適当に、ユーザを（おそらくはオーバーラップする）ユーザの部分集合にグループ化する方法であって、各部分集合が、一意の好ましくは長寿命の部分集合鍵を有し、各ユーザにめいめいの私用情報Ｉｕを割り当てる方法が含まれる。この方法には、適当に、少なくとも１つの好ましくは短寿命のセッション暗号化鍵Ｋを選択することと、取消済み集合Ｒに含まれないユーザを、それぞれが関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍに分割することも含まれる。セッション鍵Ｋが、部分集合鍵Ｌｉ１、…、Ｌｉｍを用いて適当に暗号化されて、セッション鍵Ｋの暗号化された版が与えられる。１態様では、ユーザが、完全な２分木などのツリー内の葉を確立することができ、部分集合Ｓｉ１、…、Ｓｉｍが、ツリーによって誘導される。
【０１１３】
好ましい実施形態では、ユーザが、当初は、グループＳ１、…、Ｓｗに分割され、ここで、「ｗ」は整数である。所与の送信によって、取り消されていないユーザの「カバー」としてｍ個のそのようなグループが適当に選択され、カバーは、取り消されたユーザの集合によって定義される。「カバー」グループによって、ツリー内のサブツリー（完全サブツリーまたは２つのサブツリーの間の差分のいずれか）が適当に確立される。ユーザの私用情報Ｉｕは、ユーザがグループＳ１、…、Ｓｗの１つの部分集合Ｓｉｊに属することを示す送信されたメッセージ内の情報ｉｊとして見つけられることが好ましい。その後、部分集合鍵Ｌｉｊを、ユーザの私用情報から得るか、その私用情報を使用して導出することができる。
【０１１４】
本明細書で「完全サブツリー」法と称する第１の実施形態では、めいめいのグループが、完全ツリーのすべての可能なサブツリーに対応する。各ユーザは、ユーザを表す葉とツリーのルートの間の直接パス内にあるすべてのノードから鍵を割り当てられる。言い換えると、各部分集合Ｓｉに、あるノードｖｉをルートとするサブツリー内のすべての葉が含まれ、少なくともこのサブツリー内の各ノードが、めいめいの部分集合鍵に関連する。この実施形態では、コンテンツが、ヘッダを定義するメッセージ内でユーザに供給され、このヘッダに、多くともｒ×ｌｏｇ（Ｎ／ｒ）個の部分集合鍵および暗号化が含まれ、ここで、ｒは、取消済み集合Ｒ内のユーザの数、Ｎは、ユーザの総数である。さらに、各ユーザは、ｌｏｇ  Ｎ個の鍵を保管しなければならず、各ユーザは、多くともｌｏｇ  ｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理する。
【０１１５】
本明細書で「部分集合差分」法と称する第２の実施形態では、ユーザのめいめいのグループが、「第１サブツリーＡから、完全にＡに含まれる第２サブツリーＢを引いたもの」として記述できる集合Ｓ１、…、Ｓｗの母集団に対応する。このツリー内の各ノードは、１つはそのノードに一意、その他は上位ノードによって誘導されるラベルの集合を有する。各ユーザは、レシーバとルートの間の直接パス内のノードからぶら下がるすべてのノードからのラベル（そのようなノードのそれぞれからの多くともｌｏｇ  Ｎ個のラベル）を割り当てられるが、直接パス自体のノードからは割り当てられない。言い換えると、各部分集合に、あるノードｖｉから下降するある他のノードｖｊをルートとするサブツリーにない、ｖｉをルートとするサブツリー内のすべての葉が含まれる。特定のユーザの部分集合差ノードのラベルの１つが、そのユーザの私用情報としての送信でユーザに供給される。ラベルを使用して、ユーザが、暗号化解除に必要な部分集合鍵を生成することができる。
【０１１６】
この実施形態では、メッセージ・ヘッダに、多くとも２ｒ−１（平均１．２５ｒ）個の部分集合鍵および暗号化が含まれ、各ユーザが、．５ｌｏｇ２  Ｎ  ＋  ．５ｌｏｇ  Ｎ  ＋  １個の鍵を保管しなければならず、各ユーザが、多くともｌｏｇ  Ｎ回の演算（好ましくは擬似乱数ジェネレータの適用）と単一の暗号化解除動作を使用してメッセージを処理する。
【０１１７】
下で部分集合差分法に関してさらに開示するように、取消済み集合Ｒによって、スパニング・ツリーが定義される。カバー・ツリーＴが、スパニング・ツリーとして初期化され、その後、この方法では、カバー・ツリーＴが多くとも１つのノードを有するまで、反復して、カバー・ツリーＴからノードを除去し、サブツリーをカバー・ツリーＴに追加する。カバー・ツリーＴは、特定の送信で使用される部分集合鍵を識別するのに使用され、ユーザは、擬似乱数シーケンス・ジェネレータを評価して、ラベルから部分集合鍵を導出する。処理効率のために、１時に２つの取消だけをメモリに保持する必要が生じるように、取消を左から右の順序で処理することが好ましい。
【０１１８】
いくつかの特定の実施形態では、メッセージ・ヘッダに、暗号関数ＥＬが含まれ、方法に、暗号接頭関数ＥＬの接頭部切捨が含まれる。望まれる場合に、メッセージの一部を、めいめいのセッション鍵を用いて暗号化することができる。
【０１１９】
もう１つの態様では、コンピュータ・プログラム装置に、コンピュータ・プログラム記憶装置が適当に含まれ、このコンピュータ・プログラム記憶装置に、コンピュータが使用することができる命令のプログラムが含まれる。プログラムには、複数の部分集合鍵を得るためにツリーにアクセスする論理手段と、セッション鍵を用いてメッセージを暗号化する論理手段が含まれる。部分集合鍵のそれぞれを用いてセッション鍵を少なくとも１回暗号化して、セッション鍵の暗号化された版を与える論理手段も設けられる。その後、論理手段によって、複数のステートレス・レシーバへのメッセージのヘッダ内でセッション鍵の暗号化された版が送信される。
【０１２０】
もう１つの態様では、コンピュータが、命令を用いて適当にプログラムされて、コンピュータが、ブロードキャスト・コンテンツを暗号化し、複数のステートレスな善良なレシーバおよび少なくとも１つの取り消されたレシーバにブロードキャスト・コンテンツを送り、各ステートレスな善良なレシーバが、コンテンツを暗号化解除でき、取り消されたレシーバが、コンテンツを暗号化解除できないようにする。
【０１２１】
もう１つの態様では、ブロードキャスト暗号化システム内の潜在的にステートレスのレシーバｕに、めいめいの私用情報Ｉｕを保管するデータ・ストレージと、複数の部分集合鍵を用いて暗号化されるセッション暗号化鍵Ｋを受け取る処理装置とが適当に含まれる。セッション鍵によって、コンテンツが暗号化され、処理装置は、私用情報を使用して少なくとも１つの部分集合鍵を入手し、セッション鍵Ｋを暗号化解除してコンテンツを再生できるようにする。好ましい実施形態では、レシーバが、グループＳ１、…、Ｓｗの集合の１つに分割され、ここで、「ｗ」は整数であり、グループによって、ツリーのサブツリーが確立される。グループＳ１、…、Ｓｗの集合から導出された部分集合Ｓｉ１、…、Ｓｉｍによって、レシーバによってまたはシステム・コンピュータによって計算されるカバーが定義される。ツリーに、ルートおよび複数のノードが含まれることが好ましく、各ノードは、少なくとも１つの関連するラベルを有する。各部分集合に、あるノードｖｉから下降する他のノードｖｊをルートとするサブツリーに含まれない、ノードｖｉをルートとするサブツリー内のすべての葉が含まれる。
【０１２２】
もう１つの態様では、媒体に、一般形が＜［ｉ１、ｉ２、…、ｉｍ、ＥＬｉ１（Ｋ）、ＥＬｉ２（Ｋ）、…、ＥＬｉｍ（Ｋ）］、ＦＫ（Ｍ）＞のコンテンツのメッセージが適当に保持され、ここで、Ｋは、セッション鍵であり、ＦＫは、暗号化プリミティブであり、ＥＫは、暗号化プリミティブであり、Ｌｉは、暗号化ブロードキャスト・システム内のレシーバの部分集合に関連する部分集合鍵であり、Ｍは、メッセージ本体であり、ｉ１、ｉ２、…、ｉｍは、カバーを定義するツリー・ノード部分集合である。
【０１２３】
本発明の好ましい実施形態を、例としてのみ、添付図面に関してこれから説明する。
【発明を実施するための最良の形態】
【０１２４】
まず図１を参照すると、上で参照した特許で開示されたシステムなどであるがこれに制限されない、ブロードキャスト・コンテンツ保護システムで鍵の集合を生成する、全般的に１０と指定されたシステムが示されている。「ブロードキャスト」は、コンテンツ・プロバイダから多数のユーザへの、ケーブル（衛星ソースから）、ワイヤ、ラジオ周波数（衛星ソースを含む）を介して同時に、または広く販売されるコンテンツ・ディスクからの、プログラムの広い散布を意味する。
【０１２５】
図からわかるように、システム１０には、下の開示に従って機能する鍵集合定義モジュール１４にアクセスする鍵集合定義コンピュータ１２が含まれる。コンピュータ１２によって定義される鍵集合は、本明細書で「レシーバ」および「ユーザ」とも称する、コンテンツを暗号化解除するために内部のプロセッサを有する、潜在的にステートレスのプレイヤ−レコーダ装置１８によって使用される。コンテンツは、下で開示されるある種の鍵と共に、たとえば装置製造業者１６を介して媒体１７でめいめいの装置に供給される。プレイヤ−レコーダ装置は、その鍵集合にアクセスして、媒体上のまたは無線通信を介してブロードキャストされるコンテンツを暗号化解除することができる。本明細書で使用する「媒体」には、ＤＶＤ、ＣＤ、ハード・ディスク、およびフラッシュ・メモリ・デバイスを含めることができるが、これに制限はされない。代替実施形態では、各レシーバ１６が、モジュール１４を実行して、取り消されたレシーバの集合を与えられ、下で示す論理に取り掛かることによって、下で開示する「カバー」を計算するステップに取り掛かる。
【０１２６】
モジュール１４に関連するプロセッサが、このモジュールにアクセスして、図示され下で説明される論理に取り掛かるが、この論理を、一連のコンピュータ実行可能命令としてプロセッサによって実行できることを理解されたい。システム１０を使用して、危険にさらされていないレシーバ１６がブロードキャスト・コンテンツを暗号化解除する能力を取り消さずに、危険にさらされたレシーバ１６がブロードキャスト・コンテンツを暗号化解除する能力を選択的に取り消す２つの方法すなわち、完全サブツリー法および部分集合差分法を、本明細書で開示する。
【０１２７】
命令を、コンピュータ可読コード要素をその上に保管されたコンピュータ使用可能媒体を有するコンピュータ・ディスケットなどのコンピュータ可読媒体を有するデータ記憶装置に含めることができる。あるいは、命令を、ＤＡＳＤアレイ、磁気テープ、従来のハード・ディスク、電子読取専用メモリ、光学記憶装置、または他の適当なデータ記憶装置に保管することができる。本発明の例示的実施形態では、コンピュータ実行可能命令を、コンパイルされたＣ＋＋互換コードの行とすることができる。
【０１２８】
実際に、本明細書の流れ図に、コンピュータ・プログラム・ソフトウェアで実施される本発明の好ましい実施形態の論理の構造を示す。当業者は、これらの流れ図に、本発明に従って機能する、集積回路上の論理回路を含むコンピュータ・プログラム・コード要素の構造が示されていることを諒解するであろう。あきらかに、本発明は、その本質的な実施形態において、プログラム・コード要素を、図示のものに対応する機能動作のシーケンスを実行するようにディジタル処理装置（すなわちコンピュータ）に指示する形にする機械構成要素によって実践される。
【０１２９】
部分集合差分法および完全サブツリー法の両方によって実施される本発明の好ましい実施形態の全体的な論理を、図２に関して見ることができる。この開示において、Ｎ個のレシーバ１６がシステム１０に存在し、取り消されたレシーバが連繋して働き（暗号化の知識を共用することによって）すべてのレシーバがまだコンテンツを暗号化解除できる場合であっても、取消済みレシーバ部分集合Ｒのｒ個のレシーバがコンテンツを暗号化解除する能力を取り消すことができることが望ましいと仮定する。ブロック１９で開始されて、システムは、長寿命の部分集合鍵Ｌ１、…、Ｌｗを、部分集合の母集団Ｓ１、…、Ｓｗの対応する部分集合に割り当てることによって開始され、この母集団に、レシーバが下の開示に従ってグループ化され、したがって、各部分集合Ｓｊが、それに関連する長寿命の部分集合鍵Ｌｊを有する。第１の（「完全サブツリー」）方法では、取消済み集合に含まれないレシーバをカバーする部分集合が、単に、下の開示に従って生成されるサブツリーである。第２の（「部分集合差分」）方法では、下でさらに示すように、取消済み集合に含まれないレシーバをカバーする部分集合が、第１サブツリーと、完全に第１サブツリー内にあるより小さいサブツリーとの間の差によって定義される。
【０１３０】
ブロック２０で、コンテンツの暗号化解除に有用な私用情報Ｉｕを各レシーバｕに供給することによって、システムがさらに開始される。私用情報Ｉｕの詳細は、下でさらに示す。Ｉｕが、レシーバｕに供給される秘密情報である場合には、Ｓｊに含まれる各レシーバｕが、そのＩｕからＬｊを導出することができる。下でさらに完全に示すように、取消済み集合Ｒを与えられて、取り消されていないレシーバが、ｍ個の互いに素の部分集合Ｓｉ１、…、Ｓｉｍに分割され、短寿命のセッション鍵Ｋが、めいめいの部分集合Ｓｉ１、…、Ｓｉｍに関連する長寿命の部分集合鍵Ｌｉ１、…、Ｌｉｍを用いてｍ回暗号化される。部分集合鍵は、完全サブツリー法では明示的な部分集合鍵であり、部分集合差分法では部分集合ラベルによって誘導される。
【０１３１】
具体的には、ブロック２２で、少なくとも１つのセッション鍵Ｋを選択し、これを用いて、無線または有線の通信パスまたはＣＤおよびＤＶＤなどの記憶媒体のいずれかを介してメッセージＭでブロードキャストされるコンテンツを暗号化する。セッション鍵Ｋは、メッセージごとに新規に選択されるビットのランダム・ストリングである。望まれる場合に、複数のセッション鍵を使用して、メッセージＭのめいめいの部分を暗号化することができる。
【０１３２】
下で説明する方法の両方で、取り消されていないレシーバを、ブロック２４でツリーを使用して互いに素な部分集合Ｓｉ１、…、Ｓｉｍに分割する。この部分集合を、本明細書で時々「サブツリー」と称するが、第１の方法では、サブツリーが明示的に考慮され、第２の方法では、サブツリーが、「第１サブツリーから、完全に第１サブツリーに含まれる第２サブツリーを引いたもの」という形であるものとみなされる。各部分集合Ｓｉ１、…、Ｓｉｍは、めいめいの部分集合鍵Ｌｉ１、…、Ｌｉｍに関連する。任意のデータ・ツリー様の構造が、本明細書で企図されているが、開示において、ツリーは２分木全体であると仮定する。
【０１３３】
ブロック２６に進んで、一般に、セッション鍵Ｋは、部分集合鍵Ｌｉ１、…、Ｌｉｍのそれぞれを１回用いて、ｍ回暗号化される。ブロードキャストされる、結果の暗号文は、角型括弧の間の部分がメッセージＭのヘッダを表し、ｉ１、ｉ２、…、ｉｍが互いに素の部分集合のインデックスを表すものとして、次のように表すことができる。
＜［ｉ１、ｉ２、…、ｉｍ、ＥＬｉ１（Ｋ）、ＥＬｉ２（Ｋ）、…、ＥＬｉｍ（Ｋ）］、ＦＫ（Ｍ）＞
【０１３４】
一実施形態では、暗号化プリミティブＦＫが、メッセージＭと、セッション鍵Ｋによって生成されるストリーム暗号のＸＯＲをとることによって実施される。暗号化プリミティブＥＬは、長寿命の部分集合鍵を使用してセッション鍵Ｋをレシーバ１６に送達する方法である。ＦＫ、ＥＬに関するすべての暗号化アルゴリズムが、本発明の好ましい実施形態の範囲内であることを理解されたい。ＥＬの好ましい実施形態の１つを、ブロック暗号の接頭部切捨指定とすることができる。ｌが、長さがＥＬのブロック長と等しいランダム・ストリングを表すと仮定し、Ｋが、長さがたとえば５６ビットの暗号ＦＫの短い鍵であると仮定する。その場合に、［Ｐｒｅｆｉｘ−Ｋ−ＥＬ（ｌ）／Ｋ］が、強い暗号化をもたらす。したがって、接頭部を切り捨てられたヘッダは、下記になる。
＜［ｉ１、ｉ２、…、ｉｍ、Ｕ、［Ｐｒｅｆｉｘ−Ｋ−ＥＬｉ１（Ｕ）］／Ｋ、…、［Ｐｒｅｆｉｘ−Ｋ−ＥＬｉｍ（Ｕ）］／Ｋ］、ＦＫ（Ｍ）＞
【０１３５】
これによって、有利なことに、ヘッダの長さが、ｍ−Ｌ−ではなく約ｍ−Ｋ−ビットに短縮される。ＥＬの鍵長さが最小限である場合に、下記を使用して、敵対者が、同一のストリングｌをｍ個の異なる鍵を用いて暗号化することからもたらされるブルートフォース攻撃を有するという要因ｍの利点を除去することができる。ストリングｌ／ｉｊが暗号化される。すなわち、
＜［ｉ１、ｉ２、…、ｉｍ、Ｕ、［Ｐｒｅｆｉｘ−Ｌ−ＥＬｉ１（Ｕ／ｉ１）］／Ｋ、…、［Ｐｒｅｆｉｘ−Ｌ−ＥＬｉｍ（Ｕ／ｉｍ）］／Ｋ］、ＦＫ（Ｍ）＞
【０１３６】
暗号化プリミティブＥおよびＦを実施する好ましい制限的でない形を説明したので、図３に移ると、この図には、レシーバ１６が取り掛かる暗号化解除論理が示されている。ブロック２８から開始して、各取り消されていないレシーバｕが、暗号文の部分集合識別子ｉｊを見つけて、そのレシーバが部分集合Ｓｉｊに属するようにする。下でさらに開示するように、レシーバが、取消済み集合Ｒに含まれる場合に、ブロック２８の結果は存在しない。次に、ブロック３０で、レシーバが、その私用情報Ｉｕを使用して、部分集合Ｓｉｊに対応する部分集合鍵Ｌｉｊを抽出する。この部分集合鍵を使用して、ブロック３２でセッション鍵Ｋを判定し、ブロック３４で、セッション鍵Ｋを使用してメッセージを暗号化解除する。
【０１３７】
上で説明した全体的な論理に取り掛かる２つの好ましい方法を、下で開示する。どちらにおいても、鍵を部分集合に割り当てる形およびコレクションからの互いに素な部分集合を使用して、取り消されていないレシーバをカバーする方法として、部分集合のコレクションが指定される。どちらにおいても、システム内のレシーバの集合が、２分木全体などであるがこれに制限されない木の葉を確立する。
【０１３８】
説明する第１の方法は、図４から７に示された完全サブツリー法である。図４のブロック３６から開始して、独立のランダムな部分集合鍵Ｌｉを、ツリーの各ノードｖｉに割り当てる。この部分集合鍵Ｌｉは、ノードｖｉをルートとするすべての葉を含む部分集合に対応する。その後、ブロック３８で、各レシーバｕに、そのレシーバからルートまでの直接パス内のすべての部分集合鍵を与える。図７を一時的に参照するとわかるように、部分集合Ｓｉに含まれるレシーバｕには、ノードｖｉに関連する部分集合鍵Ｌｉ、ならびにＳｉに含まれるレシーバと木のルートとの間にあるノードＰに関連する鍵が与えられる。
【０１３９】
メッセージを送信し、あるレシーバがメッセージを暗号化解除する能力を取り消すことが望まれる時に、図５の論理が呼び出されて、取り消されていないレシーバが互いに素な部分集合に分割される。ブロック４０から開始して、取り消されたレシーバの集合であるＲの葉によって定義されるスパニング・ツリーを発見する。スパニング・ツリーは、「取り消された」葉を接続する２分木全体の最小限のサブツリーであり、スタイナ木とすることができる。ブロック４２に進んで、ツリー内で１度のノード（すなわち、最小限のツリーに直接に隣接するノード）に隣接するルートを有するサブツリーを識別する。これらのサブツリーによって、「カバー」が定義され、部分集合Ｓｉ１、…、Ｓｉｍが確立される。カバーには、すべての取り消されていないレシーバが含まれる。したがって、ブロック４４で、カバーによって定義される部分集合鍵を使用して、セッション鍵Ｋを暗号化する。
【０１４０】
メッセージを暗号化解除するために、各レシーバが、図６の論理を呼び出す。ブロック４６で開始して、上位ノードがメッセージ・ヘッダ内の集合ｉ１、ｉ２、…、ｉｍの中にあるかどうかを判定することによって、レシーバの上位ノードのどれかが、カバーの部分集合鍵に関連するかどうかを判定する。レシーバの私用情報Ｉｕは、完全サブツリー法ではツリー内の位置および上位ノードに関連する部分集合鍵からなるが、この私用情報Ｉｕが、この判定に使用される。上位が、メッセージ・ヘッダ内で見つかる（レシーバが、取り消されていないレシーバであることを示す）場合には、ブロック４８で部分集合鍵を使用してセッション鍵Ｋを暗号化解除し、その後、ブロック５０で、セッション鍵Ｋを使用してメッセージを暗号化解除する。
【０１４１】
完全サブツリー法では、ヘッダに、多くともｒ×ｌｏｇ（Ｎ／ｒ）個の部分集合鍵および暗号化が含まれる。これは、鍵および暗号化の平均の数でもある。さらに、各レシーバは、ｌｏｇ  Ｎ個の鍵を保管しなければならず、各レシーバが、多くともｌｏｇ  ｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理する。
【０１４２】
次に、図８から１３を参照すると、レシーバの取消に関する部分集合差分法を見ることができる。部分集合差分法では、各レシーバが、完全サブツリー法より比較的多数の鍵（．５ｌｏｇ２  Ｎ  ＋  ．５ｌｏｇ  Ｎ  ＋  １個の鍵）を保管しなければならないが、メッセージ・ヘッダに、多くとも２ｒ−１個の部分集合鍵および暗号化が含まれ（平均１．２５ｒ個）、これは、完全サブツリー法より実質的に少ない。また、部分集合差分法では、メッセージが、擬似乱数ジェネレータの多くともｌｏｇ  Ｎ回の適用と単一の暗号化解除動作を使用して処理される。
【０１４３】
図８および図９を参照すると、部分集合差分法では、部分集合が、より大きい部分集合Ａと、Ａに完全に含まれるより小さい部分集合Ｂとの間の差とみなされる。したがって、図からわかるように、より大きいサブツリーが、ノードｖｉをルートとし、より小さいサブツリーは、ｖｉから下降したノードｖｊをルートとする。結果の部分集合Ｓｉ、ｊは、ｖｊの下の「ｎｏ」というラベルを付けられた葉（および「ｙｅｓ」というラベルを付けられた葉より暗い色の葉）を除く、ｖｉの下のすべての葉「ｙｅｓ」からなる。図９にこれを示すが、部分集合ｖｉ、ｊは、より大きい三角の中でより小さい三角の外の区域によって表される。
【０１４４】
部分集合差分法で、メッセージを送信し、一部のレシーバがメッセージを暗号化解除する能力を取り消すことが望まれる時に、上で説明した構造が、図１０に示されているように使用される。ブロック５２で開始して、取り消されたレシーバの集合であるＲに含まれる葉によって定義されるスパニング・ツリーを発見する。このスパニング・ツリーは、「取り消された」葉を接続する２分木全体の最小限のサブツリーであり、スタイナ木とすることができる。ブロック５４に進んで、カバー・ツリーＴを、スパニング・ツリーとして初期化する。その後、反復ループを開始し、カバー・ツリーＴが多くとも１つのノードを有するようになるまで、ノードをカバー・ツリーから除去し、カバーにサブツリーを追加する。この出力によって、取り消されていないレシーバのカバーが定義される。
【０１４５】
具体的に言うと、ブロック５４からブロック５６に移ると、その最小の共通の上位ｖにＴに他の葉が含まれないように、カバー・ツリーＴ内で葉ｖｉおよびｖｊを見つける。判断菱形５７で、カバー・ツリーＴに１つの葉だけが存在するかどうかを判定する。複数の葉が存在する場合に、論理は、ブロック５８に移動して、ｖｉがｖｌから下降し、ｖｊがｖｋから下降し、ｖｌ、ｖｋがｖの子（すなわち、ｖとｖｌ、ｖｋの間に介在するノードがない、ｖの直接の子孫）であるように、ｖ内のノードｖｌ、ｖｋを見つける。対照的に、Ｔに単一の葉だけが存在する時には、この論理は、判断菱形５７からブロック６０に移動して、ｖｉ＝ｖｊ＝唯一の残っている葉をセットし、ｖをＴのルートに置き、ｖｌ＝ｖｋ＝ルートをセットする。
【０１４６】
ブロック５８または６０から、この論理は、判断菱形６２に移動する。判断菱形６２では、ｖｌとｖｉが等しいかどうかを判定する。同様に、ｖｋとｖｊが等しいかどうかを判定する。ｖｌとｖｉが等しくない場合には、この論理はブロック６４に移動して、Ｔに部分集合Ｓｌ、ｉを追加し、Ｔからｖの子孫のすべてを除去し、ｖを葉にする。同様に、ｖｋとｖｊが等しくない場合に、この論理はブロック６４に移動し、Ｔに部分集合Ｓｋ、ｊを追加し、Ｔからｖの子孫のすべてを除去し、ｖを葉にする。ブロック６４からまたは、不等が判定されない時に判断菱形６２から、この論理はブロック５６にループ・バックする。
【０１４７】
上記の部分集合差分鍵割当方法の全体像を念頭において、特に好ましい実施形態を示す。レシーバが属する部分集合の総数は、Ｎと同程度に大きいが、これらの部分集合を、第１部分集合ｉ（そこから別の部分集合が引かれる）によって定義されるｌｏｇ  Ｎ個のクラスタにグループ化することができる。木全体の内部ノードに対応する１＜ｉ＜Ｎのそれぞれについて、独立のランダムなラベルＬＡＢＥＬｉが選択され、これによって、Ｓｉ、ｊの形の正当な部分集合のすべてのラベルが誘導される。このラベルから、部分集合鍵を導出する。図１１に、下で説明する好ましいラベリング方法を示す。Ｌｉというラベルを付けられたノードは、サブツリーＴｉのルートであり、その子孫は、本発明の原理に従ってラベルを付けられる。
【０１４８】
Ｇが、入力の長さを３倍にする暗号擬似乱数シーケンス・ジェネレータである場合に、Ｇ＿Ｌ（Ｓ）は、種Ｓに対するＧの出力の左１／３を表し、Ｇ＿Ｒ（Ｓ）は右１／３を表し、Ｇ＿Ｍ（Ｓ）は中央１／３を表す。ノードｖｉをルートとし、ラベルＬＡＢＥＬｉを有する、カバー・ツリーＴのサブツリーＴｉを検討されたい。このノードに、Ｓというラベルが付けられる場合に、その２つの子に、それぞれＧ＿Ｌ（Ｓ）およびＧ＿Ｒ（Ｓ）というラベルが付けられる。集合Ｓｉ、ｊに割り当てられる部分集合鍵Ｌｉ、ｊは、サブツリーＴｉ内で導出されるノードｖｊのＬＡＢＥＬｉ、ｊというラベルのＧ＿Ｍである。各ラベルＳによって、３つの部分すなわち、左右の子のラベルおよびノードの鍵が誘導されることに留意されたい。その結果、ノードのラベルを与えられれば、そのすべての子孫のラベルおよび鍵を計算することが可能である。１つの好ましい実施形態では、関数Ｇは暗号ハッシュ、（例えばSecure Hashing Algorithm-1）であるが、他の関数を使用することもできる。
【０１４９】
図１２に、部分集合差分法でレシーバがどのようにしてメッセージを暗号化解除するかを示す。ブロック６６で開始して、レシーバは、それが属する部分集合Ｓｉ、ｊを、関連するラベル（レシーバがＬＡＢＥＬｉ、ｊおよび部分集合鍵Ｌｉ、ｊを導出できるようにする私用情報の一部）と共に見つける。このラベルを使用して、レシーバは、ブロック６８で、関数Ｇを多くともＬＯＧ  Ｎ回評価することによって、部分集合鍵Ｌｉ、ｊを計算する。その後、レシーバは、ブロック７０で、その後のメッセージ暗号化解除のために、部分集合鍵Ｋを使用して、セッション鍵Ｋを暗号化解除する。
【０１５０】
図１３に、ラベルが、したがって部分集合鍵が、部分集合差分でどのようにレシーバに割り当てられるかを示す。本明細書で開示されるラベリング方法は、各レシーバが保管しなければならない鍵の数を最小にするのに使用される。
【０１５１】
ブロック７２で開始して、各レシーバに、そのレシーバとルートの間の直接パスに含まれるのではなく、直接パスから「ぶら下がる」ノードの、ｕの上位のあるノードｖｉによって誘導されたラベルが与えられる。これらのラベルによって、ブロック７４でレシーバの私用情報Ｉｕが確立され、後続のメッセージについて、ブロック７６で、セッション鍵が、ラベルから導出された部分集合鍵を用いて暗号化される。
【０１５２】
図１４を一時的に参照して、上の原理を説明する。レシーバｕのラベルＳを有するすべてのｖｉ上位ノードについて、レシーバｕは、ノードｖｉからレシーバｕへの直接パスからぶら下がるすべてのノード７１のラベルを受け取る。下でさらに説明するように、これらのラベルは、すべてがＳから導出されることが好ましい。完全サブツリー法と著しく対照的に、図８から１４に示された部分集合差分法では、レシーバｕが、レシーバｕからノードｖｉへの直接パスに含まれるすべてのノード７３からラベルを受け取らない。これらのラベルを使用して、レシーバｕは、上で説明した関数Ｇを評価することによって、他の部分集合鍵を計算せずに、ノードｖｉをルートとするすべての集合（直接パス集合を除く）の部分集合鍵を計算することができる。
【０１５３】
従来のマルチキャスト・システムは、逆方向の秘密（backward secrecy）に欠けている、すなわち、取り消されているが常時リスンしているレシーバが、それでも暗号化されたコンテンツのすべてを記録でき、その後、将来のある時に、有効な新しい鍵を獲得し（たとえば再登録によって）、これによって過去のコンテンツの暗号化解除が可能になる。本発明の好ましい実施形態を、そのようなシナリオで使用して、取り消されたレシーバの集合に、まだ割り当てられていないすべてのレシーバ識別を含めることによって、逆方向の秘密の欠如を直すことができる。これは、すべてのレシーバが、連続する順序で葉に割り当てられる場合に行うことができる。この場合に、すべての割り当てられない識別の取消が、メッセージ・ヘッダ・サイズの、そのような識別の数に比例するのではなく適度な増加をもたらす。
【０１５４】
本発明の好ましい実施形態では、メッセージ・ヘッダでの部分集合ｉｊの簡潔なエンコーディングを有することと、レシーバが、そのレシーバが部分集合ｉｊに属するかどうかをすばやく判定する方法を提供することが望ましいことも認められている。ノードが、そのノードのルートへのパスによって示され、０が左の枝を示し、１が右の枝を示すと仮定する。パスの終りは、１とそれに続く０個以上の０のビットによって示される。したがって、ルートは、１０００．．．．０００ｂであり、ルートの右端の子は、０１０００．．．０００ｂであり、ルートの左端の子は、１１０００．．．０００ｂであり、葉は、ｘｘｘｘ．．．ｘｘｘｘ１ｂである。
【０１５５】
本明細書で認められているように、より大きいサブツリーのルートのパスは、より小さいサブツリーのルートのパスの部分集合であり、その結果、部分集合差分を、より小さいサブツリーのルートと、より大きいサブツリーのルートへのパスの長さによって示すことができる。これを念頭におけば、レシーバは、下記のＩｎｔｅｌ  Ｐｅｎｔｉｕｍ（Ｒ）プロセッサ・ループを実行することによって、それが所与の部分集合に含まれるかどうかをすばやく判定することができる。
【０１５６】
ループの外で、下記のレジスタをセット・アップする：ＥＣＸに、レシーバの葉ノードが格納され、ＥＳＩが、メッセージ・バッファ（最初のバイトが、より大きいサブツリーへのパスの長さであり、次の４バイトが、より小さいツリーのルートである）をポイントし、静的テーブルによって、パスの長さによってインデクシングされる時に、最初の長さビットが１であり、残りのビットが０である３２ビットが出力される。
loop: MOV BYTE EBX, [ESI++]
MOV DWORDEAX, [ESI++]
XOR EAX,ECX
AND EAX,TABLE[EBX]
JNZ loop
【０１５７】
レシーバがループから抜けた場合に、これは、必ずしもレシーバが特定の部分集合に属することを意味しない。より小さい除外されたサブツリー内にある場合があり、そうである場合には、ループに戻らなければならない。しかし、大多数の場合に、レシーバは、より大きいサブツリー内にも含まれないので、ループ内では処理時間がほとんどかからない。
【０１５８】
部分集合差分法のさらなる最適化では、システム・サーバが、数百万個になる可能性があるすべてのレベルのそれぞれを記憶する必要がない。その代わりに、ｉ番目のノードのラベルを、ノードの秘密の関数にすることができる。この秘密の関数は、番号ｉに適用される時にｉ番目のノードのラベルを与えるのに秘密鍵を使用するトリプルＤＥＳ暗号化とすることができる。
【図面の簡単な説明】
【０１５９】
【図１】本システムのブロック図である。
【図２】暗号化論理全体の流れ図である。
【図３】暗号化解除論理全体の流れ図である。
【図４】完全サブツリー法の鍵割当部分の流れ図である。
【図５】完全サブツリー法の暗号化部分の流れ図である。
【図６】完全サブツリー法の暗号化解除部分の流れ図である。
【図７】完全サブツリーの部分集合の概略図である。
【図８】部分集合差分法の部分集合の概略図である。
【図９】部分集合差分法の部分集合のもう１つの形態の概略図である。
【図１０】部分集合差分法のカバーを定義する論理の流れ図である。
【図１１】鍵割当を示す、部分集合差分法のツリーの部分集合の概略図である。
【図１２】部分集合差分法の暗号化解除部分の流れ図である。
【図１３】部分集合差分法の鍵を割り当てる論理の流れ図である。
【図１４】部分集合差分法のツリーの部分集合の概略図である。
【図１】
2004520743.tif 000002
【図２】
2004520743.tif 000003
【図３】
2004520743.tif 000004
【図４】
2004520743.tif 000005
【図５】
2004520743.tif 000006
【図６】
2004520743.tif 000007
【図７】
2004520743.tif 000008
【図８】
2004520743.tif 000009
【図９】
2004520743.tif 000010
【図１０】
2004520743.tif 000011
【図１１】
2004520743.tif 000012
【図１２】
2004520743.tif 000013
【図１３】
2004520743.tif 000014
【図１４】
2004520743.tif 000015
【国際公開パンフレット】
2004520743.tif 000016
2004520743.tif 000017
2004520743.tif 000018
2004520743.tif 000019
2004520743.tif 000020
2004520743.tif 000021
2004520743.tif 000022
2004520743.tif 000023
2004520743.tif 000024
2004520743.tif 000025
2004520743.tif 000026
2004520743.tif 000027
2004520743.tif 000028
2004520743.tif 000029
2004520743.tif 000030
2004520743.tif 000031
2004520743.tif 000032
2004520743.tif 000033
2004520743.tif 000034
2004520743.tif 000035
2004520743.tif 000036
2004520743.tif 000037
2004520743.tif 000038
2004520743.tif 000039
2004520743.tif 000040
2004520743.tif 000041
2004520743.tif 000042
2004520743.tif 000043
2004520743.tif 000044
2004520743.tif 000045
2004520743.tif 000046
2004520743.tif 000047
2004520743.tif 000048
2004520743.tif 000049
2004520743.tif 000050
2004520743.tif 000051
2004520743.tif 000052
【国際公開パンフレット（コレクトバージョン）】
2004520743.tif 000053
【国際調査報告】
2004520743.tif 000054
2004520743.tif 000055
2004520743.tif 000056