(57)【要約】【課題】ブロードキャスト暗号化システムでトレイタ・レシーバをトレースする方法を提供すること。【解決手段】この方法には、偽鍵を使用して、システム内のレシーバを表す複数の部分集合をエンコードすることが含まれる。部分集合は、部分集合カバー・システムを使用してツリーから導出され、トレイタ・レシーバは、潜在的にクローニングされた海賊レシーバによって入手された１つまたは複数の危険にさらされた鍵に関連する。海賊レシーバのクローンを使用して、部分集合の適当な集合を生成することによって、トレイタ・レシーバの識別を判定するか、危険にさらされた鍵を使用してデータを暗号化解除するのに海賊レシーバ・クローンが有用でないようにする。
2004527937.tif 000002
【特許請求の範囲】
【請求項１】
ブロードキャスト暗号化システムで、少なくとも１つの関連する一意の危険にさらされた暗号化解除鍵を有する少なくとも１つのトレイタ・レシーバを識別するか使用不可にする方法であって、
葉を定義するツリーから導出された部分集合の集合を受け取ることであって、各葉が、めいめいのレシーバを表す、受け取ることと、
トレイタ・レシーバを表す少なくとも１つの葉を含むものとして部分集合の集合から少なくとも１つのトレイタ部分集合を識別することと、
トレイタ部分集合を使用し、トレイタ・レシーバを識別するか使用不可にすることと
を含む方法。
【請求項２】
トレイタ部分集合が少なくとも１つのトレイタ・レシーバを表すかどうかを判定し、そうである場合に、トレイタ部分集合を２つの子集合に分割すること
をさらに含む、請求項１に記載の方法。
【請求項３】
トレイタ部分集合がフロンティア集合の要素であるかどうかを判定し、そうである場合に、フロンティア集合から補間部分集合を除去することをさらに含む、請求項２に記載の方法。
【請求項４】
識別するか使用不可にする動作が、部分集合の集合の複数の部分集合を偽鍵を用いてエンコードすることを含む、請求項１に記載の方法。
【請求項５】
確率を使用して、部分集合の集合に対する二分探索を実行することをさらに含む、請求項４に記載の方法。
【請求項６】
二分探索が、最初のｊ個の部分集合に偽鍵が含まれる時にメッセージを暗号化解除する確率ｐｊと、最初のｊ−１個の部分集合に偽鍵が含まれる時にメッセージを暗号化解除する確率ｐｊ−１との間の差が、少なくとも所定の確率と等しいかどうかを判定することによって終了する、請求項５に記載の方法。
【請求項７】
トレイタ部分集合が、−ｐｊ−１−ｐｊ−  ＞ｐ／ｍである時に識別され、ここで、ｍが、部分集合の集合に含まれる集合の数である、請求項６に記載の方法。
【請求項８】
部分集合の集合が、
レシーバのグループの各レシーバに、めいめいの私用情報Ｉｕを割り当てることと、
少なくとも１つのセッション暗号化鍵Ｋを選択することと、
取消済み集合Ｒに含まれないレシーバを、関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍの集合に分割することと、
セッション鍵Ｋおよび偽鍵を、部分集合鍵Ｌｉ１、…、Ｌｉｍを用いて暗号化することと
によって生成される、請求項１に記載の方法。
【請求項９】
ツリーが、ルートおよび複数のノードを含み、各ノードが、関連する鍵を有し、各レシーバが、レシーバを表す葉とルートとの間の直接パス内のすべてのノードから鍵を割り当てられる、請求項８に記載の方法。
【請求項１０】
ツリーが、ルートおよび複数のノードを含み、各ノードが、ラベルの集合に関連付けられ、各レシーバが、レシーバとルートとの間の直接パスからぶら下がるが直接パスに含まれないすべてのノードからラベルを割り当てられる、請求項８に記載の方法。
【請求項１１】
取消済み集合Ｒが、スパニング・ツリーを定義し、方法が、
カバー・ツリーＴをスパニング・ツリーとして初期化することと、
カバー・ツリーＴが多くとも１つのノードを有するまで、繰り返して、カバー・ツリーＴからノードを除去し、カバー・ツリーＴにノードを追加することと
を含む、請求項１０に記載の方法。
【請求項１２】
コンピュータ・システムにロードされ、実行される時に、請求項１ないし１１のいずれかに記載の方法のステップをコンピュータに実行させるコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的に、暗号化鍵を使用するブロードキャスト・データ暗号化に関する。
【背景技術】
【０００２】
ＣＤおよびＤＶＤなどの記録された媒体を使用してまたは衛星放送などの無線放送方法を介して、潜在的に数百万台のレシーバにブロードキャストされるコンテンツを暗号化する、さまざまなブロードキャスト暗号化システムが提案されてきた。これらのシステムは、コンテンツを暗号化し、許可されたレシーバ（「ユーザ」または「プレイヤ−レコーダ」とも称する）だけが、コンテンツをデコードでき、再生できるが、許可された装置からどうにかして有効な暗号化解除鍵を得ること（「トレイタ」：反逆者）ができた、ソフトウェアまたはハードウェアによって実施される海賊装置（「クローン」または「悪い装置」とも称する）が、それでもコンテンツを暗号化解除し、再生することができないようにすることを意図されている。
【０００３】
そのようなシステムの例が、参照によって本明細書に組み込まれる、本願の譲受人の米国特許第６，１１８，８７３号に開示されている。それに示されているように、許可されたプレイヤ−レコーダだけが、コンテンツのベンダによって確立される規則に従ってのみ、コンテンツを再生し、かつ／またはコピーすることができる。この形で、現在コンテンツ・プロバイダが毎年数十億ドルを費やすコンテンツの海賊コピーを防ぐことができる。
【０００４】
ブロードキャスト暗号化システムのもう１つの例が、参照によって本明細書に組み込まれる、本願の譲受人の米国仮特許出願第号［整理番号ＡＲＣ９２００１００＿ＵＳ］に開示されている。説明のためにその詳細を下で示す、この後者のシステムは、「ステートレス」レシーバすなわち、海賊装置に対する対応策を受け入れるために、ブロードキャストの間で暗号化状態を必ずしも更新しないレシーバという困難なシナリオに対処する。たとえば、有料チャネルに加入したテレビジョンが、更新した暗号化データがシステムを介してブロードキャストされる時間の期間中に、そのセットトップ・ボックスの電源を断たれる場合がある。そのような装置は、電源を再投入された後にそれ自体を更新できない場合に、「ステートレス」にされ、将来のコンテンツ暗号化解除に必要な更新を受信しなくなる。ステートレス・レシーバのもう１つの例が、ＣＤおよびＤＶＤのプレイヤ−レコーダであり、これらは、普通は、他のシステム構成要素と相互作用せず、すべての売られたディスクを受け取るプレイヤは存在しないので、暗号化データ更新のすべてを受け取るのではない。
【特許文献１】
米国特許第６，１１８，８７３号
【特許文献２】
米国仮特許出願第号［整理番号ＡＲＣ９２００１００＿ＵＳ］
【発明の開示】
【発明が解決しようとする課題】
【０００５】
当業者が認めるように、ブロードキャスト暗号化システムの暗号化解除鍵が、危険にさらされ、許可されない海賊装置がコンテンツを暗号化解除できるようになる可能性がある。そのような海賊装置は、ハードウェアまたはソフトウェアで実施することができ、後者の場合に、プロプラエタリ・コンテンツを支払なしで入手することを求める誰もが自由にダウンロードできるようにインターネットにポストされる可能性がある。どの場合でも、本発明は、その鍵を海賊が入手したシステム・レシーバ（トレイタ・レシーバ：反逆者レシーバ）の識別を見つけることによって海賊クローンの普及を押しとどめること、またはクローンが暗号化解除できないが許可されたユーザが暗号化解除できる暗号化を見つけることによって海賊クローンを役に立たなくすることを対象とする。
【課題を解決するための手段】
【０００６】
本発明は、特に（排他的ではないが）、部分集合カバー・システムでのトレイタのトレースの問題に焦点を合わせたものである。上で参照した’８７３特許のシステムと異なって、部分集合カバー・システムでは、装置の間の鍵のオーバーラップが存在しない。鍵オーバーラップの結果の１つが、’８７３特許のシステムで、動作中に、ある装置鍵がコンテンツを正しく暗号化解除し、ある装置鍵がそうでないことが完全に普通であり、その結果、クローンは、それに送信されるメッセージを、そのクローンのすべての鍵を用いて暗号化解除できないかどうかを観察することによって、そのクローンがテストされているかどうかを確かめることができないことである。これは、部分集合カバー・システムでは真でない。というのは、すべての装置が、少なくとも１つの一意の鍵を有するからである。その結果、クローンが、複数のトレイタから鍵を入手し、あるトレイタからの１つの鍵が、コンテンツを正しく暗号化解除するが、別のトレイタからの別の鍵が、コンテンツを正しく暗号化解除しない場合に、クローンは、それがテストされていると推論することができる。
【０００７】
クローンは、それがテストされていると推論したならば、トレイタの間での識別の切替え、または自己破壊など、複数の対向手段のどれにでも取り掛かることができる。もちろん、自己破壊の場合に、ライセンスを交付する機関が、さらなる（修正された）テストのために、単純に別のクローンを入手することができるが、これには時間がかかる。これらのクリティカルな観察を念頭において、本発明の好ましい実施形態は、１つまたは複数の観察に対する下記の解決策を提供した。
【０００８】
したがって、本発明は、第１の態様で、ブロードキャスト暗号化システムで、少なくとも１つの関連する一意の危険にさらされた暗号化解除鍵を有する少なくとも１つのトレイタ・レシーバを識別するか使用不可にする方法であって、葉を定義するツリーから導出された部分集合の集合を受け取ることであって、各葉が、めいめいのレシーバを表す、受け取ることと、トレイタ・レシーバを表す少なくとも１つの葉を含むものとして部分集合の集合から少なくとも１つのトレイタ部分集合を識別することと、トレイタ部分集合を使用し、トレイタ・レシーバを識別するか使用不可にすることとを含む方法を提供する。
【０００９】
第１の態様の方法は、適当に、トレイタ部分集合が少なくとも１つのトレイタ・レシーバを表すかどうかを判定し、そうである場合に、トレイタ部分集合を２つの子集合に分割することをさらに含む。
【００１０】
第１の態様の方法は、適当に、トレイタ部分集合がフロンティア集合の要素であるかどうかを判定し、そうである場合に、フロンティア集合から補間部分集合を除去することをさらに含む。
【００１１】
適当に、識別するか使用不可にする動作が、部分集合の集合の複数の部分集合を偽鍵を用いてエンコードすることを含む。
【００１２】
第１の態様の方法は、適当に、確率を使用して、部分集合の集合に対する二分探索を実行することをさらに含む。
【００１３】
適当に、二分探索が、最初のｊ個の部分集合に偽鍵が含まれる時にメッセージを暗号化解除する確率ｐｊと、最初のｊ−１個の部分集合に偽鍵が含まれる時にメッセージを暗号化解除する確率ｐｊ−１との間の差が、少なくとも所定の確率と等しいかどうかを判定することによって終了する。
【００１４】
適当に、トレイタ部分集合が、−ｐｊ−１−ｐｊ−  ＞ｐ／ｍである時に識別され、ここで、ｍが、部分集合の集合に含まれる部分集合の数である。
【００１５】
適当に、部分集合の集合が、レシーバのグループの各レシーバに、めいめいの私用情報Ｉｕを割り当てることと、少なくとも１つのセッション暗号化鍵Ｋを選択することと、取消済み集合Ｒに含まれないレシーバを、関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍの集合に分割することと、セッション鍵Ｋおよび偽鍵を、部分集合鍵Ｌｉ１、…、Ｌｉｍを用いて暗号化することとによって生成される。
【００１６】
適当に、ツリーが、ルートおよび複数のノードを含み、各ノードが、関連する鍵を有し、各レシーバが、レシーバを表す葉とルートとの間の直接パス内のすべてのノードから鍵を割り当てられる。
【００１７】
適当に、ツリーが、ルートおよび複数のノードを含み、各ノードが、ラベルの集合に関連付けられ、各レシーバが、レシーバとルートとの間の直接パスからぶら下がるが直接パスに含まれないすべてのノードからラベルを割り当てられる。
【００１８】
適当に、取消済み集合Ｒが、スパニング・ツリーを定義し、方法が、カバー・ツリーＴをスパニング・ツリーとして初期化することと、カバー・ツリーＴが多くとも１つのノードを有するまで、繰り返して、カバー・ツリーＴからノードを除去し、カバー・ツリーＴにノードを追加することとを含む。
【００１９】
第１の態様の方法は、適当に、クローンで実施される複数のトレイタ・レシーバを識別するか使用不可にすることをさらに含む。
【００２０】
適当に、識別するか使用不可にすることが、部分集合の集合の最初のｊ個の部分集合を、偽鍵を用いてエンコードすることを含む。
【００２１】
本発明は、コンピュータ・プログラム装置であって、コンピュータによって使用可能な命令のプログラムを含むコンピュータ・プログラム記憶装置を含み、前記命令のプログラムが、ツリーの部分集合の集合を生成するためにツリーにアクセスする論理手段であって、ツリーが、危険にさらされた鍵を特徴とする少なくとも１つのトレイタ装置を表す葉を含む、論理手段と、偽鍵をｊ回暗号化し、セッション鍵をｍ−ｊ回暗号化する論理手段であって、ｍが、部分集合の集合に含まれる部分集合の数である、論理手段と、暗号化する手段に応答して、トレイタ部分集合を識別する論理手段と、トレイタ装置を識別するか使用不可にするためにトレイタ部分集合を使用する論理手段とを含む、コンピュータ・プログラム装置を適当に提供することができる。
【００２２】
コンピュータ・プログラム装置のさらなる好ましい特徴に、第１の態様の好ましい特徴による好ましい方法のステップをコンピューティング・システムに実行させる論理手段を含めることができる。
【００２３】
第２の態様で、本発明は、コンピューティング・システムにロードされ、実行される時に、第１の態様による方法のステップをコンピューティング・システムに実行させるコンピュータ・プログラム・コードを含むコンピュータ・プログラムを提供する。
【００２４】
第２の態様の好ましい特徴に、第１の態様の好ましい特徴による方法の好ましいステップをコンピューティング・システムに実行させるコンピュータ・プログラム・コードが含まれる。
【００２５】
本発明は、適当に、ステートレス・レシーバを表す複数の部分集合をエンコードするために偽鍵を使用することであって、前記レシーバのうちの少なくとも１つのトレイタ・レシーバが、少なくとも１つの海賊レシーバによって入手された少なくとも１つの危険にさらされた鍵に関連する、使用することと、海賊レシーバまたはそのクローンを使用するか、トレイタ・レシーバの識別を判定するか、海賊レシーバまたはそのクローンを危険にさらされた鍵を使用するデータの暗号化解除に有用でなくすることとを含む方法動作をコンピュータに実行させる命令を用いてプログラムされたコンピュータをさらに提供することができる。
【００２６】
適当に、部分集合が、部分集合の集合を定義し、コンピュータによって取り掛かられる方法動作が、葉を定義するツリーから導出された部分集合の集合を受け取ることであって、各葉が、めいめいのレシーバを表す、受け取ることと、トレイタ・レシーバを表す少なくとも１つの葉を含むものとして、部分集合の集合から少なくとも１つのトレイタ部分集合を識別することと、トレイタ部分集合を使用し、トレイタ・レシーバを識別することとをさらに含む。
【００２７】
適当に、コンピュータによって取り掛かられる方法動作が、トレイタ部分集合が少なくとも１つのトレイタ・レシーバを表すかどうかを判定し、そうである場合に、トレイタ部分集合を２つの子集合に分割することをさらに含む。
【００２８】
適当に、コンピュータによって取り掛かられる方法動作が、トレイタ部分集合がフロンティア集合の要素であるかどうかを判定し、そうである場合に、フロンティア集合から補間部分集合を除去することをさらに含む。
【００２９】
適当に、識別する動作が、部分集合の集合の複数の部分集合を偽鍵を用いてエンコードすることを含む。
【００３０】
適当に、コンピュータによって取り掛かられる方法動作が、確率を使用して、部分集合の集合に対する二分探索を実行することをさらに含む。
【００３１】
適当に、二分探索が、最初のｊ個の部分集合に偽鍵が含まれる時にメッセージを暗号化解除する確率ｐｊが、少なくとも所定の確率と等しいかどうかを判定することによって終了する。
【００３２】
適当に、トレイタ部分集合が、−ｐｊ−１−ｐｊ−  ＞ｐ／ｍである時に識別され、ここで、ｍが、部分集合の集合に含まれる部分集合の数である。
【００３３】
適当に、部分集合の集合が、レシーバのグループの各レシーバに、めいめいの私用情報Ｉｕを割り当てることと、少なくとも１つのセッション暗号化鍵Ｋを選択することと、取消済み集合Ｒに含まれないレシーバを、関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍの集合に分割することと、セッション鍵Ｋおよび偽鍵を、部分集合鍵Ｌｉ１、…、Ｌｉｍを用いて暗号化することとによって生成され、ツリーが、ルートおよび複数のノードを含み、各ノードが、ラベルの集合に関連付けられ、各レシーバが、レシーバとルートとの間の直接パスからぶら下がるが直接パスに含まれないすべてのノードからラベルを割り当てられる。
【００３４】
適当に、本発明は、本明細書に記載の発明的論理に取り掛かるコンピュータ・システムを含む。本発明は、本発明の論理を保管し、論理を実行するためにプロセッサによってアクセスされることができるコンピュータ・プログラム製品でも実施することができる。また、本発明は、下で開示される論理に従うコンピュータ実施される方法である。
【００３５】
コンピュータを適当にプログラムして、偽鍵を使用してステートレス・レシーバを表す複数の部分集合をエンコードする。システム内の少なくとも１つのトレイタ・レシーバが、クローニングされた海賊レシーバによって入手された危険にさらされた鍵に関連する。海賊レシーバのクローンを使用して、コンピュータが、トレイタ・レシーバの識別を判定し、あるいは、適当な暗号化戦略を生成することによって、海賊レシーバ・クローンを、危険にされされた鍵を使用してデータを暗号化解除するのに有用でなくする。
【００３６】
もう１つの態様で、ブロードキャスト暗号化システム内で、関連する一意の危険にさらされた暗号化解除鍵を有するトレイタ・レシーバを識別する好ましい方法を開示する。この方法には、葉を定義するツリーから導出された部分集合の集合を受け取ることが含まれ、各葉が、めいめいのレシーバを表す。また、この方法には、少なくとも１つのトレイタ・レシーバを含むものとして部分集合の集合からトレイタ部分集合を識別することと、その後、トレイタ部分集合を使用し、トレイタ・レシーバを識別することが含まれる。
【００３７】
好ましい実施形態では、方法に、トレイタ部分集合が１つまたは複数のトレイタ・レシーバを表すかどうかを判定し、そうである場合に、トレイタ部分集合を２つの子集合に分割し、２つの個集合を使用して新しいトレイタ部分集合を識別することが含まれる。好ましい方法には、トレイタ部分集合がフロンティア集合の要素であるかどうかを判定し、そうである場合に、フロンティア集合から補間部分集合を除去することも含まれる。
【００３８】
トレイタ部分集合を識別する好ましい形には、偽鍵を用いて部分集合の集合の最初のｊ個の部分集合をエンコードし、その後、確率を使用して部分集合の集合に対する二分探索を実行することが含まれる。二分探索は、最初のｊ個の部分集合に偽鍵が含まれる時にメッセージを暗号化解除する確率ｐｊと、最初のｊ−１個の部分集合に偽鍵が含まれる時に暗号化解除する確率ｐｊ−１との間の差が、少なくとも所定の確率と等しいかどうかを判定することによって終了する。具体的に言うと、トレイタ部分集合は、−ｐｊ−１−ｐｊ−  ＞ｐ／ｍである時に識別され、ここで、ｍは、部分集合の集合に含まれる部分集合の数である。部分集合の集合は、二股に分けることができる部分集合を生成するという特性を有する部分集合カバー方式によって生成される。
【００３９】
もう１つの態様では、コンピュータ・プログラム装置に、ツリーの部分集合の集合を生成するためにツリーにアクセスする論理手段が含まれ、ツリーに、危険にさらされた鍵を特徴とする少なくとも１つのトレイタ装置を表す葉が含まれる。偽鍵をｊ回暗号化し、セッション鍵をｍ−ｊ回暗号化する論理手段が設けられ、ｍは、部分集合の集合に含まれる部分集合の数である。また、暗号化する手段に応答して、トレイタ部分集合を識別する論理手段がある。その後、論理手段で、トレイタ部分集合を使用して、トレイタ装置を識別する。
【００４０】
本発明の好ましい実施形態を、例としてのみ、添付図面に関して説明する。
【発明を実施するための最良の形態】
【００４１】
本発明の好ましい実施形態を、複数のブロードキャスト暗号化方法のいずれかと共に使用することができる。制限的でない例として、そのようなシステムの１つすなわち部分集合カバー・システムを、まず示し、その後、本発明のトレース・アルゴリズムを、部分集合カバー・システムに関して開示する。
【００４２】
まず図１を参照すると、上で参照した特許で開示されたシステムなどであるがこれに制限されない、ブロードキャスト・コンテンツ保護システムで鍵の集合を生成する、全般的に１０と指定されたシステムが示されている。「ブロードキャスト」は、コンテンツ・プロバイダから多数のユーザへの、ケーブル（衛星ソースから）、ワイヤ、ラジオ周波数（衛星ソースを含む）を介して同時に、または広く販売されるコンテンツ・ディスクからの、プログラムの広い散布を意味する。
【００４３】
図からわかるように、システム１０には、下の開示に従って機能する鍵集合定義モジュール１４にアクセスする鍵集合定義コンピュータ１２が含まれる。コンピュータ１２によって定義される鍵集合は、本明細書で「レシーバ」および「ユーザ」とも称する、コンテンツを暗号化解除するために内部のプロセッサを有する、潜在的にステートレスのプレイヤ−レコーダ装置１６によって使用される。コンテンツは、下で開示されるある種の鍵と共に、たとえば装置製造業者１６を介して媒体１７でめいめいの装置に供給される。プレイヤ−レコーダ装置は、その鍵集合にアクセスして、媒体上のまたは無線通信を介してブロードキャストされるコンテンツを暗号化解除することができる。本明細書で使用する「媒体」には、ＤＶＤ、ＣＤ、ハード・ディスク、およびフラッシュ・メモリ・デバイスを含めることができるが、これに制限はされない。代替実施形態では、各レシーバ１６が、モジュール１４を実行して、取り消されたレシーバの集合を与えられ、下で示す論理に取り掛かることによって、下で開示する「カバー」を計算するステップに取り掛かる。
【００４４】
モジュール１４に関連するプロセッサが、このモジュールにアクセスして、図示され下で説明される論理に取り掛かるが、この論理を、一連のコンピュータ実行可能命令としてプロセッサによって実行できることを理解されたい。システム１０を使用して、危険にさらされていないレシーバ１６がブロードキャスト・コンテンツを暗号化解除する能力を取り消さずに、危険にさらされたレシーバ１６がブロードキャスト・コンテンツを暗号化解除する能力を選択的に取り消す２つの方法すなわち、完全サブツリー法および部分集合差分法を、本明細書で開示する。
【００４５】
命令を、コンピュータ可読コード要素をその上に保管されたコンピュータ使用可能媒体を有するコンピュータ・ディスケットなどのコンピュータ可読媒体を有するデータ記憶装置に含めることができる。あるいは、命令を、ＤＡＳＤアレイ、磁気テープ、従来のハード・ディスク、電子読取専用メモリ、光学記憶装置、または他の適当なデータ記憶装置に保管することができる。本発明の例示的実施形態では、コンピュータ実行可能命令を、コンパイルされたＣ＋＋互換コードの行とすることができる。
【００４６】
実際に、本明細書の流れ図に、コンピュータ・プログラム・ソフトウェアで実施される本発明の好ましい実施形態の論理の構造を示す。当業者は、これらの流れ図に、本発明に従って機能する、集積回路上の論理回路を含むコンピュータ・プログラム・コード要素の構造が示されていることを諒解するであろう。あきらかに、本発明は、その本質的な実施形態において、プログラム・コード要素を、図示のものに対応する機能動作のシーケンスを実行するようにディジタル処理装置（すなわちコンピュータ）に指示する形にする機械構成要素によって実践される。
【００４７】
部分集合差分法および完全サブツリー法の両方によって実施される本発明の好ましい実施形態の全体的な論理を、図２に関して見ることができる。この開示において、Ｎ個のレシーバ１６がシステム１０に存在し、取り消されたレシーバが連繋して働き（暗号化の知識を共用することによって）すべてのレシーバがまだコンテンツを暗号化解除できる場合であっても、取消済みレシーバ部分集合Ｒのｒ個のレシーバがコンテンツを暗号化解除する能力を取り消すことができることが望ましいと仮定する。ブロック１９で開始されて、システムは、長寿命の部分集合鍵Ｌ１、…、Ｌｗを、部分集合の母集団Ｓ１、…、Ｓｗの対応する部分集合に割り当てることによって開始され、この母集団に、レシーバが下の開示に従ってグループ化され、したがって、各部分集合Ｓｊが、それに関連する長寿命の部分集合鍵Ｌｊを有する。第１の（「完全サブツリー」）方法では、取消済み集合に含まれないレシーバをカバーする部分集合が、単に、下の開示に従って生成されるサブツリーである。第２の（「部分集合差分」）方法では、下でさらに示すように、取消済み集合に含まれないレシーバをカバーする部分集合が、第１サブツリーと、完全に第１サブツリー内にあるより小さいサブツリーとの間の差によって定義される。
【００４８】
ブロック２０で、コンテンツの暗号化解除に有用な私用情報Ｉｕを各レシーバｕに供給することによって、システムがさらに開始される。私用情報Ｉｕの詳細は、下でさらに示す。Ｉｕが、レシーバｕに供給される秘密情報である場合には、Ｓｊに含まれる各レシーバｕが、そのＩｕからＬｊを導出することができる。下でさらに完全に示すように、取消済み集合Ｒを与えられて、取り消されていないレシーバが、ｍ個の互いに素の部分集合Ｓｉ１、…、Ｓｉｍに分割され、短寿命のセッション鍵Ｋが、めいめいの部分集合Ｓｉ１、…、Ｓｉｍに関連する長寿命の部分集合鍵Ｌｉ１、…、Ｌｉｍを用いてｍ回暗号化される。部分集合鍵は、完全サブツリー法では明示的な部分集合鍵であり、部分集合差分法では部分集合ラベルによって誘導される。
【００４９】
具体的には、ブロック２２で、少なくとも１つのセッション鍵Ｋを選択し、これを用いて、無線または有線の通信パスまたはＣＤおよびＤＶＤなどの記憶媒体のいずれかを介してメッセージＭでブロードキャストされるコンテンツを暗号化する。セッション鍵Ｋは、メッセージごとに新規に選択されるビットのランダム・ストリングである。望まれる場合に、複数のセッション鍵を使用して、メッセージＭのめいめいの部分を暗号化することができる。
【００５０】
下で説明する方法の両方で、取り消されていないレシーバを、ブロック２４でツリーを使用して互いに素な部分集合Ｓｉ１、…、Ｓｉｍに分割する。この部分集合を、本明細書で時々「サブツリー」と称するが、第１の方法では、サブツリーが明示的に考慮され、第２の方法では、サブツリーが、「第１サブツリーから、完全に第１サブツリーに含まれる第２サブツリーを引いたもの」という形であるものとみなされる。各部分集合Ｓｉ１、…、Ｓｉｍは、めいめいの部分集合鍵Ｌｉ１、…、Ｌｉｍに関連する。任意のデータ・ツリー様の構造が、本明細書で企図されているが、開示において、ツリーは２分木全体であると仮定する。
【００５１】
ブロック２６に進んで、一般に、セッション鍵Ｋは、部分集合鍵Ｌｉ１、…、Ｌｉｍのそれぞれを１回用いて、ｍ回暗号化される。ブロードキャストされる、結果の暗号文は、角型括弧の間の部分がメッセージＭのヘッダを表し、ｉ１、ｉ２、…、ｉｍが互いに素の部分集合のインデックスを表すものとして、次のように表すことができる。
＜［ｉ１、ｉ２、…、ｉｍ、ＥＬｉ１（Ｋ）、ＥＬｉ２（Ｋ）、…、ＥＬｉｍ（Ｋ）］、ＦＫ（Ｍ）＞
【００５２】
一実施形態では、暗号化プリミティブＦＫが、メッセージＭと、セッション鍵Ｋによって生成されるストリーム暗号のＸＯＲをとることによって実施される。暗号化プリミティブＥＬは、長寿命の部分集合鍵を使用してセッション鍵Ｋをレシーバ１６に送達する方法である。ＦＫ、ＥＬに関するすべての暗号化アルゴリズムが、本発明の範囲内であることを理解されたい。ＥＬの好ましい実施形態の１つを、ブロック暗号の接頭部切捨指定とすることができる。ｌが、長さがＥＬのブロック長と等しいランダム・ストリングを表すと仮定し、Ｋが、長さがたとえば５６ビットの暗号ＦＫの短い鍵であると仮定する。その場合に、［Ｐｒｅｆｉｘ−Ｋ−ＥＬ（ｌ）／Ｋ］が、強い暗号化をもたらす。したがって、接頭部を切り捨てられたヘッダは、下記になる。
＜［ｉ１、ｉ２、…、ｉｍ、Ｕ、［Ｐｒｅｆｉｘ−Ｋ−ＥＬｉ１（Ｕ）］／Ｋ、…、［Ｐｒｅｆｉｘ−Ｋ−ＥＬｉｍ（Ｕ）］／Ｋ］、ＦＫ（Ｍ）＞
【００５３】
これによって、有利なことに、ヘッダの長さが、ｍ−Ｌ−ではなく約ｍ−Ｋ−ビットに短縮される。ＥＬの鍵長さが最小限である場合に、下記を使用して、敵対者が、同一のストリングｌをｍ個の異なる鍵を用いて暗号化することからもたらされるブルートフォース攻撃を有するという要因ｍの利点を除去することができる。ストリングｌ／ｉｊが暗号化される。すなわち、
＜［ｉ１、ｉ２、…、ｉｍ、Ｕ、［Ｐｒｅｆｉｘ−Ｌ−ＥＬｉ１（Ｕ／ｉ１）］／Ｋ、…、［Ｐｒｅｆｉｘ−Ｌ−ＥＬｉｍ（Ｕ／ｉｍ）］／Ｋ］、ＦＫ（Ｍ）＞
【００５４】
暗号化プリミティブＥおよびＦを実施する好ましい制限的でない形を説明したので、図３に移ると、この図には、レシーバ１６が取り掛かる暗号化解除論理が示されている。ブロック２８から開始して、各取り消されていないレシーバｕが、暗号文の部分集合識別子ｉｊを見つけて、そのレシーバが部分集合Ｓｉｊに属するようにする。下でさらに開示するように、レシーバが、取消済み集合Ｒに含まれる場合に、ブロック２８の結果は存在しない。次に、ブロック３０で、レシーバが、その私用情報Ｉｕを使用して、部分集合Ｓｉｊに対応する部分集合鍵Ｌｉｊを抽出する。この部分集合鍵を使用して、ブロック３２でセッション鍵Ｋを判定し、ブロック３４で、セッション鍵Ｋを使用してメッセージを暗号化解除する。
【００５５】
上で説明した全体的な論理に取り掛かる２つの好ましい方法を、下で開示する。どちらにおいても、鍵を部分集合に割り当てる形およびコレクションからの互いに素な部分集合を使用して、取り消されていないレシーバをカバーする方法として、部分集合のコレクションが指定される。どちらにおいても、システム内のレシーバの集合が、２分木全体などであるがこれに制限されない木の葉を確立する。
【００５６】
説明する第１の方法は、図４から７に示された完全サブツリー法である。図４のブロック３６から開始して、独立のランダムな部分集合鍵Ｌｉを、ツリーの各ノードｖｉに割り当てる。この部分集合鍵Ｌｉは、ノードｖｉをルートとするすべての葉を含む部分集合に対応する。その後、ブロック３８で、各レシーバｕに、そのレシーバからルートまでの直接パス内のすべての部分集合鍵を与える。図７を一時的に参照するとわかるように、部分集合Ｓｉに含まれるレシーバｕには、ノードｖｉに関連する部分集合鍵Ｌｉ、ならびにＳｉに含まれるレシーバと木のルートとの間にあるノードＰに関連する鍵が与えられる。
【００５７】
メッセージを送信し、あるレシーバがメッセージを暗号化解除する能力を取り消すことが望まれる時に、図５の論理が呼び出されて、取り消されていないレシーバが互いに素な部分集合に分割される。ブロック４０から開始して、取り消されたレシーバの集合であるＲの葉によって定義されるスパニング・ツリーを発見する。スパニング・ツリーは、「取り消された」葉を接続する２分木全体の最小限のサブツリーであり、スタイナ木とすることができる。ブロック４２に進んで、ツリー内で１度のノード（すなわち、最小限のツリーに直接に隣接するノード）に隣接するルートを有するサブツリーを識別する。これらのサブツリーによって、「カバー」が定義され、部分集合Ｓｉ１、…、Ｓｉｍが確立される。カバーには、すべての取り消されていないレシーバが含まれる。したがって、ブロック４４で、カバーによって定義される部分集合鍵を使用して、セッション鍵Ｋを暗号化する。
【００５８】
メッセージを暗号化解除するために、各レシーバが、図６の論理を呼び出す。ブロック４６で開始して、上位ノードがメッセージ・ヘッダ内の集合ｉ１、ｉ２、…、ｉｍの中にあるかどうかを判定することによって、レシーバの上位ノードのどれかが、カバーの部分集合鍵に関連するかどうかを判定する。レシーバの私用情報Ｉｕは、完全サブツリー法ではツリー内の位置および上位ノードに関連する部分集合鍵からなるが、この私用情報Ｉｕが、この判定に使用される。上位が、メッセージ・ヘッダ内で見つかる（レシーバが、取り消されていないレシーバであることを示す）場合には、ブロック４８で部分集合鍵を使用してセッション鍵Ｋを暗号化解除し、その後、ブロック５０で、セッション鍵Ｋを使用してメッセージを暗号化解除する。
【００５９】
完全サブツリー法では、ヘッダに、多くともｒ×ｌｏｇ（Ｎ／ｒ）個の部分集合鍵および暗号化が含まれる。これは、鍵および暗号化の平均の数でもある。さらに、各レシーバは、ｌｏｇ  Ｎ個の鍵を保管しなければならず、各レシーバが、多くともｌｏｇ  ｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理する。
【００６０】
次に、図８から１３を参照すると、レシーバの取消に関する部分集合差分法を見ることができる。部分集合差分法では、各レシーバが、完全サブツリー法より比較的多数の鍵（．５ｌｏｇ２  Ｎ  ＋  ．５ｌｏｇ  Ｎ  ＋  １個の鍵）を保管しなければならないが、メッセージ・ヘッダに、多くとも２ｒ−１個の部分集合鍵および暗号化が含まれ（平均１．２５ｒ個）、これは、完全サブツリー法より実質的に少ない。また、部分集合差分法では、メッセージが、擬似乱数ジェネレータの多くともｌｏｇ  Ｎ回の適用と単一の暗号化解除動作を使用して処理される。
【００６１】
図８および図９を参照すると、部分集合差分法では、部分集合が、より大きい部分集合Ａと、Ａに完全に含まれるより小さい部分集合Ｂとの間の差とみなされる。したがって、図からわかるように、より大きいサブツリーが、ノードｖｉをルートとし、より小さいサブツリーは、ｖｉから下降したノードｖｊをルートとする。結果の部分集合Ｓｉ、ｊは、ｖｊの下の「ｎｏ」というラベルを付けられた葉（および「ｙｅｓ」というラベルを付けられた葉より暗い色の葉）を除く、ｖｉの下のすべての葉「ｙｅｓ」からなる。図９にこれを示すが、部分集合ｖｉ、ｊは、より大きい三角の中でより小さい三角の外の区域によって表される。
【００６２】
部分集合差分法で、メッセージを送信し、一部のレシーバがメッセージを暗号化解除する能力を取り消すことが望まれる時に、上で説明した構造が、図１０に示されているように使用される。ブロック５２で開始して、取り消されたレシーバの集合であるＲに含まれる葉によって定義されるスパニング・ツリーを発見する。このスパニング・ツリーは、「取り消された」葉を接続する２分木全体の最小限のサブツリーであり、スタイナ木とすることができる。ブロック５４に進んで、カバー・ツリーＴを、スパニング・ツリーとして初期化する。その後、反復ループを開始し、カバー・ツリーＴが多くとも１つのノードを有するようになるまで、ノードをカバー・ツリーから除去し、カバーにサブツリーを追加する。この出力によって、取り消されていないレシーバのカバーが定義される。
【００６３】
具体的に言うと、ブロック５４からブロック５６に移ると、その最小の共通の上位ｖにＴに  の葉が含まれないように、カバー・ツリーＴ内で葉ｖｉおよびｖｊを見つける。判断菱形５７で、カバー・ツリーＴに１つの葉だけが存在するかどうかを判定する。複数の葉が存在する場合に、論理は、ブロック５８に移動して、ｖｉがｖｌから下降し、ｖｊがｖｋから下降し、ｖｌ、ｖｋがｖの子（すなわち、ｖとｖｌ、ｖｋの間に介在するノードがない、ｖの直接の子孫）であるように、ｖ内のノードｖｌ、ｖｋを見つける。対照的に、Ｔに単一の葉だけが存在する時には、この論理は、判断菱形５７からブロック６０に移動して、ｖｉ＝ｖｊ＝唯一の残っている葉をセットし、ｖをＴのルートに置き、ｖｌ＝ｖｋ＝ルートをセットする。
【００６４】
ブロック５８または６０から、この論理は、判断菱形６２に移動する。判断菱形６２では、ｖｌとｖｉが等しいかどうかを判定する。同様に、ｖｋとｖｊが等しいかどうかを判定する。ｖｌとｖｉが等しくない場合には、この論理はブロック６４に移動して、Ｔに部分集合Ｓｌ、ｉを追加し、Ｔからｖの子孫のすべてを除去し、ｖを葉にする。同様に、ｖｋとｖｊが等しくない場合に、この論理はブロック６４に移動し、Ｔに部分集合Ｓｋ、ｊを追加し、Ｔからｖの子孫のすべてを除去し、ｖを葉にする。ブロック６４からまたは、不等が判定されない時に判断菱形６２から、この論理はブロック５６にループ・バックする。
【００６５】
上記の部分集合差分鍵割当方法の全体像を念頭において、特に好ましい実施形態を示す。レシーバが属する部分集合の総数は、Ｎと同程度に大きいが、これらの部分集合を、第１部分集合ｉ（そこから別の部分集合が引かれる）によって定義されるｌｏｇ  Ｎ個のクラスタにグループ化することができる。木全体の内部ノードに対応する１＜ｉ＜Ｎのそれぞれについて、独立のランダムなラベルＬＡＢＥＬｉが選択され、これによって、Ｓｉ、ｊの形の正当な部分集合のすべてのラベルが誘導される。このラベルから、部分集合鍵を導出する。図１１に、下で説明する好ましいラベリング方法を示す。Ｌｉというラベルを付けられたノードは、サブツリーＴｉのルートであり、その子孫は、本発明の原理に従ってラベルを付けられる。
【００６６】
Ｇが、入力の長さを３倍にする暗号擬似乱数シーケンス・ジェネレータである場合に、Ｇ＿Ｌ（Ｓ）は、種Ｓに対するＧの出力の左１／３を表し、Ｇ＿Ｒ（Ｓ）は右１／３を表し、Ｇ＿Ｍ（Ｓ）は中央１／３を表す。ノードｖｉをルートとし、ラベルＬＡＢＥＬｉを有する、カバー・ツリーＴのサブツリーＴｉを検討されたい。このノードに、Ｓというラベルが付けられる場合に、その２つの子に、それぞれＧ＿Ｌ（Ｓ）およびＧ＿Ｒ（Ｓ）というラベルが付けられる。集合Ｓｉ、ｊに割り当てられる部分集合鍵Ｌｉ、ｊは、サブツリーＴｉ内で導出されるノードｖｊのＬＡＢＥＬｉ、ｊというラベルのＧ＿Ｍである。各ラベルＳによって、３つの部分すなわち、左右の子のラベルおよびノードの鍵が誘導されることに留意されたい。その結果、ノードのラベルを与えられれば、そのすべての子孫のラベルおよび鍵を計算することが可能である。１つの好ましい実施形態では、関数Ｇは暗号ハッシュ、（例えばSecure Hashing Algorithm-1）であるが、他の関数を使用することもできる。
【００６７】
図１２に、部分集合差分法でレシーバがどのようにしてメッセージを暗号化解除するかを示す。ブロック６６で開始して、レシーバは、それが属する部分集合Ｓｉ、ｊを、関連するラベル（レシーバがＬＡＢＥＬｉ、ｊおよび部分集合鍵Ｌｉ、ｊを導出できるようにする私用情報の一部）と共に見つける。このラベルを使用して、レシーバは、ブロック６８で、関数Ｇを多くともＬＯＧ  Ｎ回評価することによって、部分集合鍵Ｌｉ、ｊを計算する。その後、レシーバは、ブロック７０で、その後のメッセージ暗号化解除のために、部分集合鍵Ｋを使用して、セッション鍵Ｋを暗号化解除する。
【００６８】
図１３に、ラベルが、したがって部分集合鍵が、部分集合差分でどのようにレシーバに割り当てられるかを示す。本明細書で開示されるラベリング方法は、各レシーバが保管しなければならない鍵の数を最小にするのに使用される。
【００６９】
ブロック７２で開始して、各レシーバに、そのレシーバとルートの間の直接パスに含まれるのではなく、直接パスから「ぶら下がる」ノードの、ｕの上位のあるノードｖｉによって誘導されたラベルが与えられる。これらのラベルによって、ブロック７４でレシーバの私用情報Ｉｕが確立され、後続のメッセージについて、ブロック７６で、セッション鍵が、ラベルから導出された部分集合鍵を用いて暗号化される。
【００７０】
図１４を一時的に参照して、上の原理を説明する。レシーバｕのラベルＳを有するすべてのｖｉ上位ノードについて、レシーバｕは、ノードｖｉからレシーバｕへの直接パスからぶら下がるすべてのノード７１のラベルを受け取る。下でさらに説明するように、これらのラベルは、すべてがＳから導出されることが好ましい。完全サブツリー法と著しく対照的に、図８から１４に示された部分集合差分法では、レシーバｕが、レシーバｕからノードｖｉへの直接パスに含まれるすべてのノード７３からラベルを受け取らない。これらのラベルを使用して、レシーバｕは、上で説明した関数Ｇを評価することによって、他の部分集合鍵を計算せずに、ノードｖｉをルートとするすべての集合（直接パス集合を除く）の部分集合鍵を計算することができる。
【００７１】
従来のマルチキャスト・システムは、逆方向の秘密（backward secrecy）に欠けている、すなわち、取り消されているが常時リスンしているレシーバが、それでも暗号化されたコンテンツのすべてを記録でき、その後、将来のある時に、有効な新しい鍵を獲得し（たとえば再登録によって）、これによって過去のコンテンツの暗号化解除が可能になる。本発明の好ましい実施形態を、そのようなシナリオで使用して、取り消されたレシーバの集合に、まだ割り当てられていないすべてのレシーバ識別を含めることによって、逆方向の秘密の欠如を直すことができる。これは、すべてのレシーバが、連続する順序で葉に割り当てられる場合に行うことができる。この場合に、すべての割り当てられない識別の取消が、メッセージ・ヘッダ・サイズの、そのような識別の数に比例するのではなく適度な増加をもたらす。
【００７２】
本発明の好ましい実施形態では、メッセージ・ヘッダでの部分集合ｉｊの簡潔なエンコーディングを有することと、レシーバが、そのレシーバが部分集合ｉｊに属するかどうかをすばやく判定する方法を提供することが望ましいことも認められている。ノードが、そのノードのルートへのパスによって示され、０が左の枝を示し、１が右の枝を示すと仮定する。パスの終りは、１とそれに続く０個以上の０のビットによって示される。したがって、ルートは、１０００．．．．０００ｂであり、ルートの右端の子は、０１０００．．．０００ｂであり、ルートの左端の子は、１１０００．．．０００ｂであり、葉は、ｘｘｘｘ．．．ｘｘｘｘ１ｂである。
【００７３】
本明細書で認められているように、より大きいサブツリーのルートのパスは、より小さいサブツリーのルートのパスの部分集合であり、その結果、部分集合差分を、より小さいサブツリーのルートと、より大きいサブツリーのルートへのパスの長さによって示すことができる。これを念頭におけば、レシーバは、下記のＩｎｔｅｌ  Ｐｅｎｔｉｕｍ（Ｒ）プロセッサ・ループを実行することによって、それが所与の部分集合に含まれるかどうかをすばやく判定することができる。
【００７４】
ループの外で、下記のレジスタをセット・アップする：ＥＣＸに、レシーバの葉ノードが格納され、ＥＳＩが、メッセージ・バッファ（最初のバイトが、より大きいサブツリーへのパスの長さであり、次の４バイトが、より小さいツリーのルートである）をポイントし、静的テーブルによって、パスの長さによってインデクシングされる時に、最初の長さビットが１であり、残りのビットが０である３２ビットが出力される。
2004527937.tif 000003
【００７５】
レシーバがループから抜けた場合に、これは、必ずしもレシーバが特定の部分集合に属することを意味しない。より小さい除外されたサブツリー内にある場合があり、そうである場合には、ループに戻らなければならない。しかし、大多数の場合に、レシーバは、より大きいサブツリー内にも含まれないので、ループ内では処理時間がほとんどかからない。
【００７６】
部分集合差分法のさらなる最適化では、システム・サーバが、数百万個になる可能性があるすべてのレベルのそれぞれを記憶する必要がない。その代わりに、ｉ番目のノードのラベルを、ノードの秘密の関数にすることができる。この秘密の関数は、番号ｉに適用される時にｉ番目のノードのラベルを与えるのに秘密鍵を使用するトリプルＤＥＳ暗号化とすることができる。
【００７７】
本発明の好ましい実施形態をそれと共に使用することができる部分集合カバー・システムの詳細を説明したので、図１５および１６を参照されたい。ブロック１００で開始して、部分集合Ｓｉ１、…、Ｓｉｍの分割Ｓを、認可トレース機関によって入手された疑わしい海賊クローン装置に入力する。最初の分割は、取り消された装置の現在の集合によって誘導され、装置が取り消されていない場合には、最初の分割Ｓが、すべてのユーザの集合である。判断菱形１０２に移動して、クローンが、上で開示した部分集合カバー・システムの原理に従って、好ましくは部分集合差分実施形態の原理に従って、分割Ｓを使用してコンテンツを暗号化解除したかどうかを判定する。クローンがコンテンツを暗号化解除するとみなされるのは、ある所定の確率、たとえばｐ＞．５でメッセージを暗号化解除できる場合である。ほとんどの実用的なクローンで、ｐ＝１である。クローンが暗号化解除できない場合には、クローンをうちまかす暗号化が見つかっており、したがって、この処理は状態１０４で終了する。
【００７８】
しかし、クローンが、コンテンツを成功裡に暗号化解除した場合には、この処理は、ブロック１２４に移る。ブロック１２４では、下でさらに説明する図１６の部分集合トレース論理が、分割Ｓに対して実行されて、部分集合Ｓｉｊが作られ、論理は、ブロック１０６に進んで、部分集合Ｓｉｊを受け取る。判断菱形１０８に進んで、部分集合Ｓｉｊが、単一のトレイタ候補だけを含むかどうか、すなわち、部分集合Ｓｉｊが、単一の葉だけを有するかどうかを判定する。そうである場合には、トレイタが見つかっており、この処理は、ブロック１１０で、ｊ番目の装置を「トレイタ」として示し、取り消されていないレシーバの集合からトレイタを除去することと、トレイタを取り消されたレシーバの集合Ｒに置くことによって、トレイタを取り消す。これによって、ブロック１１１で新しいカバー集合Ｓが定義され、処理は、ブロック１２４に進むが、このブロックについては下でさらに完全に説明する。
【００７９】
部分集合Ｓｉｊが、複数のトレイタ候補を有する場合には、この論理は、判断菱形１０８からブロック１１２に進み、ここで、集合Ｓｉｊを、２つの子集合Ｓ１ｉｊおよびＳ２ｉｊに分割する。これは、部分集合カバー・システムの二股に分かれる特性のゆえに可能であり、部分集合カバー・システムでは、サブツリーをおおむね（必ずしも正確ではない）２つに分割することができる。
【００８０】
ｔ個のトレイタをトレースするのに必要なメッセージの長さを減らすことによって効率の良さを実現するために、好ましい実施形態の１つで、ブロック１１２から、ブロック１１４から１２２に示されたサブルーチンに移動することができる。このサブルーチンは、トレイタを含むことがまだ見つかっていない部分集合を単一の効率的に処理されるグループに合併するように機能する。そのような削減が必要でない場合には、Ｓ１ｉｊおよびＳ２ｉｊをカバーに加え、ブロック１１４から１２２を省略する。
【００８１】
ブロック１１４で、子集合Ｓ１ｉｊおよびＳ２ｉｊを、フロンティア集合Ｆに加え、「仲間集合」としてお互いに関連付ける。次に、判断菱形１１６で、集合Ｓｉｊが前のフロンティア集合Ｆ（すなわち、子集合Ｓ１ｉｊおよびＳ２ｉｊが追加される前に存在した集合Ｆ）に含まれたかどうかを判定する。含まれた場合には、これが、集合Ｓｉｊが、やはりフロンティア集合Ｆに含まれた補集合、いわゆる「相棒」集合を有したことを意味し、ブロック１１８で、「相棒」集合（１つまたは複数のレシーバを表す）が、フロンティア集合Ｆから除去される。この形で、まだトレイタ候補を含むことが見つかっていない集合が、フロンティア集合Ｆとは別にグループ化される。
【００８２】
ブロック１１８からまたは、テスト結果が否定である場合の判断菱形１１６から、この論理は、ブロック１２０に進み、ここで、カバーＣを、上で示した部分集合カバー原理に従って、フロンティア集合Ｆの集合で表されないすべてのレシーバｕについて計算する。具体的に言うと、フロンティア集合Ｆに含まれる集合によって表されるレシーバを、一時的に取消済み集合Ｒに分類し、上の原理に従ってカバーを判定する。ブロック１２２で、新しい分割Ｓを、カバーＣとフロンティア集合Ｆに含まれる部分集合との和集合として定義する。その後、ブロック１２４で、新しいＳに対して図１６の部分集合トレース論理を実行して、別のＳｉｊを作り、この論理はブロック１０６にループ・バックする。
【００８３】
したがって、図１６の部分集合トレース論理を検討すると、ブロック１２６で開始して、分割Ｓが受け取られる。この論理では、ステップのシーケンスが管理され、通常のステップでは、暗号化が実行され、最初のｊ個の部分集合が、セッション鍵Ｋと同一の長さを有する偽鍵ＲＫを用いてエンコードされる。すなわち、ｐが、クローンが分割Ｓを用いて正しく暗号化解除する確率である時に、下記の形のメッセージが作られる。
＜Ｅｌｉ１（ＲＫ）、ＥＬｉ２（ＲＫ）、…、ＥＬｉｊ（ＲＫ）、ＥＬｉ（ｊ＋１）（Ｋ）、…、ＥＬｉｍ（Ｋ）、ＦＫ（Ｍ）＞
ｐｊは、最初のｊ個の部分集合に偽鍵が含まれる時の暗号化解除の確率である。−ｐｊ−１−ｐｊ−  ＞ｐ／ｍの場合に、本発明の好ましい実施形態によれば、Ｓｉｊに、トレイタを表す葉が含まれる。確率ｐｊを見つけるために、ｍ２ｌｏｇ（１／ｅ）回の実験に取り掛かって、実験の全シーケンスのうちで何回、クローンが実際のメッセージＭを出力するかを判定する。具体的に言うと、クローンが、最後のｍ−ｊ個の部分集合からの鍵（実際のセッション鍵Ｋを暗号化した鍵）を全く有しない場合に、クローンは、絶対にＭを判定できない（単なる偶然を除いて）。
【００８４】
したがって、二分探索を実行して、全区間［０、ｍ］から開始し、上下界［ａ、ｂ］（ブロック１３０で［０、ｍ］に初期化される）を使用して連続して区間を半分にすることによって、トレイタを含むＳｉｊを効率的に見つける。ｐ０＝ｐかつｐｍ＝０であることに留意されたい。さらに、ほとんどの実用的な場合に、ｐ＝１すなわち、クローンが、通常動作中に必ず暗号化解除する。
【００８５】
二分探索は、判断菱形１３２で開始され、ここでは、上界および下界が１つ離れている（探索の終りを示す）かどうかを判定する。そうである場合には、この論理は、ブロック１３４で、上界ｂとしてｊ番目のトレイタのインデックスを返す。そうでない場合には、この論理は、ブロック１３６に移って、区間［ａ、ｂ］の中点ｃの確率すなわち、最初のｃ個の部分集合に偽鍵が含まれ、他の部分集合に真の鍵が含まれる時の暗号化解除の確率を見つける。
【００８６】
本発明の好ましい実施形態によれば、最初のｊ個の部分集合に偽鍵が含まれる時にメッセージが成功裡に暗号化解除される確率ｐｊは、繰り返して、鍵Ｋと共にメッセージＭを選択することと、ＭをＦｋ（Ｍ）として暗号化することと、偽鍵を用いて最初のｊ個の部分集合をエンコードし、真の鍵Ｋを用いて最後のｍ−ｊ個の部分集合をエンコードすることと、クローンがＭを成功裡に暗号化解除するかどうかを観察することによって計算される。
【００８７】
その後、判断菱形１３８で、中点の確率と下界の確率の間の差の絶対値が、少なくとも、下界の確率と上界の確率の間の差の半分の絶対値と等しいかどうかが判定される（すなわち、−ｐｃ−ｐａ−  ＞  −ｐｃ−ｐｂ−であるかどうかを判定するために）。そうである場合に、ブロック１４０で、上界ｂを現在の中点ｃと等しくすることと、上界確率ｐｂを中点確率ｐｃと等しくすることによって、区間を半分の［ａ、ｃ］にする。その一方で、判断菱形１３８での否定のテストの場合には、この論理はブロック１４２に進む。ブロック１４２では、下界を現在の中点ｃと等しくすることと、下界確率ｐａを中点確率ｐｃと等しくすることによって、区間を半分の［ｃ、ｂ］にする。この論理は、その後、判断菱形１３２にループ・バックする。
【００８８】
ブロック１３６で、中点の確率ｐｃが、１／ｍの精度まで計算されることが好ましい。ｐｃが、１−ｅの確率で正確に推定されることを保証するために、クローンに対するｍ２  ｌｏｇ（１／ｅ）回の照会を観察することが必要である。
【００８９】
したがって、図１６の論理では、クローンに対するｍ２ｌｏｇ（ｍ）ｌｏｇ（１／ｅ）回の照会を使用することが好ましい。望まれる場合に、１−Ｑの確率（Ｑは１／２に近い値、たとえばＱ＝１／３である）で正しい判断が得られると各ステップで仮定される、ノイズの多い二分探索に取り掛かることができる。各回答が、ヒストリから独立のある固定された確率（たとえば２／３超）で正しいモデルで、ｍ個の集合に対する二分探索をｌｏｇ  ｍ  ＋  ｌｏｇ  １／Ｑ回の照会で実行することが可能である。上で開示した実施形態では、中点確率が、確率Ｑで誤った値を生じると仮定することができる。これは、手順全体に対する照会の数を、ｍ２（ｌｏｇ  ｍ  ＋  ｌｏｇ  １／Ｑ）に減らすことができることを暗示する。というのは、確率１−Ｑでｐｃを正確に計算するために、各ステップでｍ２回の照会が必要になるからである。
【００９０】
同一の入力を用いてクローンに対してトレース・アルゴリズムを並列に稼動させることによって、トレイタを、複数のクローンからトレースすることができる。最初の入力は、どれもが取消済み集合Ｒに配置されてないすべてのユーザの集合から生じる分割Ｓ０である。処理が進行するにつれて、最初のクローンが、その集合の１つでトレイタを「検出」する時に、そのクローンは、それ相応にその集合を再分割する（トレイタを取消済み集合Ｒに移動することによって）。新しい分割が、すべてのクローンに同時に入力される。同時方法の出力は、すべての取り消されたレシーバおよびクローンを無効にする分割（または「取消戦略」）である。
【００９１】
本発明の好ましい実施形態は、比較的小さいメッセージを使用して、比較的多数のトレイタをトレースする能力を提供する。本発明の好ましい実施形態を、上で参照した部分集合カバー・システムとシームレスに統合することができる。また、トレースできるトレイタの数に対する先験的な限界は不要である。さらに、本発明の好ましい実施形態は、クローンがトレースに対抗して行うことに無関係に、トレイタをトレースすることまたは海賊クローンを有用でなくすることのいずれかによって機能する。
【００９２】
本明細書で図示され説明された特定の「ブロードキャスト暗号化システムでトレイタ・レシーバをトレースする方法」は、本発明の上で説明した目的を完全に達成することができるが、これが、本発明の現在好ましい実施形態であり、したがって本発明の好ましい実施形態によって広義に企図される対象を表すことと、本発明の好ましい実施形態の範囲が、当業者に明白になる可能性がある他の実施形態を完全に包含することと、本発明の好ましい実施形態の範囲が、したがって、請求項以外の何物によっても制限されず、請求項では、単数形の要素への言及が、請求項で他の形で指定されない限り、「唯一」ではなく「少なくとも１つ」を意味することを理解されたい。当業者に既知であるか後に既知になる、上で説明した好ましい実施形態の要素に対する構造的同等物および機能的同等物のすべてが、参照によって本明細書に特に組み込まれ、請求項に含まれることが意図されている。さらに、請求項によって包含されるために、装置または方法が、本発明の好ましい実施形態によって解決されることが求められるすべての問題のそれぞれに対処する必要はない。さらに、この開示の要素、構成要素、または方法ステップは、それらの要素、構成要素、または方法ステップが請求項で特に具陳されているかどうかに無関係に、公衆に捧げられる。本明細書の請求の要素は、その要素が句「〜の手段」と特に具陳されない限り、または、方法クレームの場合に、その要素が「動作」の代わりに「ステップ」と具陳されない限り、米国特許法セクション１１２第６パラグラフの規定の下で解釈されてはならない。
【図面の簡単な説明】
【００９３】
【図１】本システムのブロック図である。
【図２】暗号化論理全体の流れ図である。
【図３】暗号化解除論理全体の流れ図である。
【図４】完全サブツリー法の鍵割当部分の流れ図である。
【図５】完全サブツリー法の暗号化部分の流れ図である。
【図６】完全サブツリー法の暗号化解除部分の流れ図である。
【図７】完全サブツリーの部分集合の概略図である。
【図８】部分集合差分法の部分集合の概略図である。
【図９】部分集合差分法の部分集合のもう１つの形態の概略図である。
【図１０】部分集合差分法のカバーを定義する論理の流れ図である。
【図１１】鍵割当を示す、部分集合差分法のツリーの部分集合の概略図である。
【図１２】部分集合差分法の暗号化解除部分の流れ図である。
【図１３】部分集合差分法の鍵を割り当てる論理の流れ図である。
【図１４】部分集合差分法のツリーの部分集合の概略図である。
【図１５】本発明のトレース論理を示す流れ図である。
【図１６】トレース論理の部分集合トレース・モジュールを示す流れ図である。
【図１】
2004527937.tif 000004
【図２】
2004527937.tif 000005
【図３】
2004527937.tif 000006
【図４】
2004527937.tif 000007
【図５】
2004527937.tif 000008
【図６】
2004527937.tif 000009
【図７】
2004527937.tif 000010
【図８】
2004527937.tif 000011
【図９】
2004527937.tif 000012
【図１０】
2004527937.tif 000013
【図１１】
2004527937.tif 000014
【図１２】
2004527937.tif 000015
【図１３】
2004527937.tif 000016
【図１４】
2004527937.tif 000017
【図１５】
2004527937.tif 000018
【図１６】
2004527937.tif 000019
【国際公開パンフレット】
2004527937.tif 000020
2004527937.tif 000021
2004527937.tif 000022
2004527937.tif 000023
2004527937.tif 000024
2004527937.tif 000025
2004527937.tif 000026
2004527937.tif 000027
2004527937.tif 000028
2004527937.tif 000029
2004527937.tif 000030
2004527937.tif 000031
2004527937.tif 000032
2004527937.tif 000033
2004527937.tif 000034
2004527937.tif 000035
2004527937.tif 000036
2004527937.tif 000037
2004527937.tif 000038
2004527937.tif 000039
2004527937.tif 000040
2004527937.tif 000041
2004527937.tif 000042
2004527937.tif 000043
2004527937.tif 000044
2004527937.tif 000045
2004527937.tif 000046
2004527937.tif 000047
2004527937.tif 000048
2004527937.tif 000049
2004527937.tif 000050
2004527937.tif 000051
2004527937.tif 000052
2004527937.tif 000053
2004527937.tif 000054
2004527937.tif 000055
【国際公開パンフレット（コレクトバージョン）】
2004527937.tif 000056
2004527937.tif 000057
【手続補正書】
【提出日】平成15年2月11日(2003.2.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ブロードキャスト暗号化システムで、少なくとも１つの関連する一意の危険にさらされた暗号化解除鍵を有する少なくとも１つのトレイタ・レシーバを識別するか使用不可にする方法であって、
葉を定義するツリーから導出された部分集合の集合を受け取ることであって、各葉が、めいめいのレシーバを表す、受け取ることと、
トレイタ・レシーバを表す少なくとも１つの葉を含むものとして部分集合の集合から少なくとも１つのトレイタ部分集合を識別することと、
トレイタ・レシーバを識別するか使用不可にするためにトレイタ部分集合を使用することと
を含み、識別するか使用不可にする動作が、偽鍵を用いて部分集合の集合の複数の部分集合をエンコードすることを含む
方法。
【請求項２】
トレイタ部分集合が少なくとも１つのトレイタ・レシーバを表すかどうかを判定し、そうである場合に、トレイタ部分集合を２つの子集合に分割すること
をさらに含む、請求項１に記載の方法。
【請求項３】
トレイタ部分集合がフロンティア集合の要素であるかどうかを判定し、そうである場合に、フロンティア集合から補間部分集合を除去することをさらに含む、請求項２に記載の方法。
【請求項４】
確率を使用して、部分集合の集合に対する二分探索を実行することをさらに含む、請求項３に記載の方法。
【請求項５】
二分探索が、最初のｊ個の部分集合に偽鍵が含まれる時にメッセージを暗号化解除する確率ｐｊと、最初のｊ−１個の部分集合に偽鍵が含まれる時にメッセージを暗号化解除する確率ｐｊ−１との間の差が、少なくとも所定の確率と等しいかどうかを判定することによって終了する、請求項４に記載の方法。
【請求項６】
トレイタ部分集合が、−ｐｊ−１−ｐｊ−  ＞ｐ／ｍである時に識別され、ここで、ｍが、部分集合の集合に含まれる集合の数である、請求項５に記載の方法。
【請求項７】
部分集合の集合が、
レシーバのグループの各レシーバに、めいめいの私用情報Ｉｕを割り当てることと、
少なくとも１つのセッション暗号化鍵Ｋを選択することと、
取消済み集合Ｒに含まれないレシーバを、関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍの集合に分割することと、
セッション鍵Ｋおよび偽鍵を、部分集合鍵Ｌｉ１、…、Ｌｉｍを用いて暗号化することと
によって生成される、請求項１に記載の方法。
【請求項８】
ツリーが、ルートおよび複数のノードを含み、各ノードが、関連する鍵を有し、各レシーバが、レシーバを表す葉とルートとの間の直接パス内のすべてのノードから鍵を割り当てられる、請求項７に記載の方法。
【請求項９】
ツリーが、ルートおよび複数のノードを含み、各ノードが、ラベルの集合に関連付けられ、各レシーバが、レシーバとルートとの間の直接パスからぶら下がるが直接パスに含まれないすべてのノードからラベルを割り当てられる、請求項７に記載の方法。
【請求項１０】
取消済み集合Ｒが、スパニング・ツリーを定義し、方法が、
カバー・ツリーＴをスパニング・ツリーとして初期化することと、
カバー・ツリーＴが多くとも１つのノードを有するまで、繰り返して、カバー・ツリーＴからノードを除去し、カバー・ツリーＴにノードを追加することと
を含む、請求項９に記載の方法。
【請求項１１】
コンピュータ・システムにロードされ、実行される時に、請求項１ないし１０のいずれかに記載の方法のステップをコンピュータに実行させるコンピュータ・プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的に、暗号化鍵を使用するブロードキャスト・データ暗号化に関する。
【背景技術】
【０００２】
ＣＤおよびＤＶＤなどの記録された媒体を使用してまたは衛星放送などの無線放送方法を介して、潜在的に数百万台のレシーバにブロードキャストされるコンテンツを暗号化する、さまざまなブロードキャスト暗号化システムが提案されてきた。これらのシステムは、コンテンツを暗号化し、許可されたレシーバ（「ユーザ」または「プレイヤ−レコーダ」とも称する）だけが、コンテンツをデコードでき、再生できるが、許可された装置からどうにかして有効な暗号化解除鍵を得ること（「トレイタ」：反逆者）ができた、ソフトウェアまたはハードウェアによって実施される海賊装置（「クローン」または「悪い装置」とも称する）が、それでもコンテンツを暗号化解除し、再生することができないようにすることを意図されている。
【０００３】
そのようなシステムの例が、参照によって本明細書に組み込まれる、本願の譲受人の米国特許第６，１１８，８７３号に開示されている。それに示されているように、許可されたプレイヤ−レコーダだけが、コンテンツのベンダによって確立される規則に従ってのみ、コンテンツを再生し、かつ／またはコピーすることができる。この形で、現在コンテンツ・プロバイダが毎年数十億ドルを費やすコンテンツの海賊コピーを防ぐことができる。
【０００４】
ブロードキャスト暗号化システムのもう１つの例が、参照によって本明細書に組み込まれる、本願の譲受人の米国仮特許出願第号［整理番号ＡＲＣ９２００１００＿ＵＳ］に開示されている。説明のためにその詳細を下で示す、この後者のシステムは、「ステートレス」レシーバすなわち、海賊装置に対する対応策を受け入れるために、ブロードキャストの間で暗号化状態を必ずしも更新しないレシーバという困難なシナリオに対処する。たとえば、有料チャネルに加入したテレビジョンが、更新した暗号化データがシステムを介してブロードキャストされる時間の期間中に、そのセットトップ・ボックスの電源を断たれる場合がある。そのような装置は、電源を再投入された後にそれ自体を更新できない場合に、「ステートレス」にされ、将来のコンテンツ暗号化解除に必要な更新を受信しなくなる。ステートレス・レシーバのもう１つの例が、ＣＤおよびＤＶＤのプレイヤ−レコーダであり、これらは、普通は、他のシステム構成要素と相互作用せず、すべての売られたディスクを受け取るプレイヤは存在しないので、暗号化データ更新のすべてを受け取るのではない。
【特許文献１】
米国特許第６，１１８，８７３号
【特許文献２】
米国仮特許出願第号［整理番号ＡＲＣ９２００１００＿ＵＳ］
【発明の開示】
【発明が解決しようとする課題】
【０００５】
当業者が認めるように、ブロードキャスト暗号化システムの暗号化解除鍵が、危険にさらされ、許可されない海賊装置がコンテンツを暗号化解除できるようになる可能性がある。そのような海賊装置は、ハードウェアまたはソフトウェアで実施することができ、後者の場合に、プロプラエタリ・コンテンツを支払なしで入手することを求める誰もが自由にダウンロードできるようにインターネットにポストされる可能性がある。どの場合でも、本発明は、その鍵を海賊が入手したシステム・レシーバ（トレイタ・レシーバ：反逆者レシーバ）の識別を見つけることによって海賊クローンの普及を押しとどめること、またはクローンが暗号化解除できないが許可されたユーザが暗号化解除できる暗号化を見つけることによって海賊クローンを役に立たなくすることを対象とする。
【発明を解決するための手段】
【０００６】
本発明は、特に（排他的ではないが）、部分集合カバー・システムでのトレイタのトレースの問題に焦点を合わせたものである。上で参照した’８７３特許のシステムと異なって、部分集合カバー・システムでは、装置の間の鍵のオーバーラップが存在しない。鍵オーバーラップの結果の１つが、’８７３特許のシステムで、動作中に、ある装置鍵がコンテンツを正しく暗号化解除し、ある装置鍵がそうでないことが完全に普通であり、その結果、クローンは、それに送信されるメッセージを、そのクローンのすべての鍵を用いて暗号化解除できないかどうかを観察することによって、そのクローンがテストされているかどうかを確かめることができないことである。これは、部分集合カバー・システムでは真でない。というのは、すべての装置が、少なくとも１つの一意の鍵を有するからである。その結果、クローンが、複数のトレイタから鍵を入手し、あるトレイタからの１つの鍵が、コンテンツを正しく暗号化解除するが、別のトレイタからの別の鍵が、コンテンツを正しく暗号化解除しない場合に、クローンは、それがテストされていると推論することができる。
【０００７】
クローンは、それがテストされていると推論したならば、トレイタの間での識別の切替え、または自己破壊など、複数の対向手段のどれにでも取り掛かることができる。もちろん、自己破壊の場合に、ライセンスを交付する機関が、さらなる（修正された）テストのために、単純に別のクローンを入手することができるが、これには時間がかかる。これらのクリティカルな観察を念頭において、本発明の好ましい実施形態は、１つまたは複数の観察に対する下記の解決策を提供した。
【０００８】
したがって、本発明は、第１の態様で、ブロードキャスト暗号化システムで、少なくとも１つの関連する一意の危険にさらされた暗号化解除鍵を有する少なくとも１つのトレイタ・レシーバを識別するか使用不可にする方法であって、葉を定義するツリーから導出された部分集合の集合を受け取ることであって、各葉が、めいめいのレシーバを表す、受け取ることと、トレイタ・レシーバを表す少なくとも１つの葉を含むものとして部分集合の集合から少なくとも１つのトレイタ部分集合を識別することと、トレイタ部分集合を使用し、トレイタ・レシーバを識別するか使用不可にすることとを含み、識別するか使用不可にする動作が、偽鍵を用いて部分集合の集合の複数の部分集合をエンコードすることを含む方法を提供する。
【０００９】
第１の態様の方法は、適当に、トレイタ部分集合が少なくとも１つのトレイタ・レシーバを表すかどうかを判定し、そうである場合に、トレイタ部分集合を２つの子集合に分割することをさらに含む。
【００１０】
第１の態様の方法は、適当に、トレイタ部分集合がフロンティア集合の要素であるかどうかを判定し、そうである場合に、フロンティア集合から補間部分集合を除去することをさらに含む。
【００１１】
第１の態様の方法は、適当に、確率を使用して、部分集合の集合に対する二分探索を実行することをさらに含む。
【００１２】
適当に、二分探索が、最初のｊ個の部分集合に偽鍵が含まれる時にメッセージを暗号化解除する確率ｐｊと、最初のｊ−１個の部分集合に偽鍵が含まれる時にメッセージを暗号化解除する確率ｐｊ−１との間の差が、少なくとも所定の確率と等しいかどうかを判定することによって終了する。
【００１３】
適当に、トレイタ部分集合が、−ｐｊ−１−ｐｊ−  ＞ｐ／ｍである時に識別され、ここで、ｍが、部分集合の集合に含まれる部分集合の数である。
【００１４】
適当に、部分集合の集合が、レシーバのグループの各レシーバに、めいめいの私用情報Ｉｕを割り当てることと、少なくとも１つのセッション暗号化鍵Ｋを選択することと、取消済み集合Ｒに含まれないレシーバを、関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍの集合に分割することと、セッション鍵Ｋおよび偽鍵を、部分集合鍵Ｌｉ１、…、Ｌｉｍを用いて暗号化することとによって生成される。
【００１５】
適当に、ツリーが、ルートおよび複数のノードを含み、各ノードが、関連する鍵を有し、各レシーバが、レシーバを表す葉とルートとの間の直接パス内のすべてのノードから鍵を割り当てられる。
【００１６】
適当に、ツリーが、ルートおよび複数のノードを含み、各ノードが、ラベルの集合に関連付けられ、各レシーバが、レシーバとルートとの間の直接パスからぶら下がるが直接パスに含まれないすべてのノードからラベルを割り当てられる。
【００１７】
適当に、取消済み集合Ｒが、スパニング・ツリーを定義し、方法が、カバー・ツリーＴをスパニング・ツリーとして初期化することと、カバー・ツリーＴが多くとも１つのノードを有するまで、繰り返して、カバー・ツリーＴからノードを除去し、カバー・ツリーＴにノードを追加することとを含む。
【００１８】
第１の態様の方法は、適当に、クローンで実施される複数のトレイタ・レシーバを識別するか使用不可にすることをさらに含む。
【００１９】
適当に、識別するか使用不可にすることが、部分集合の集合の最初のｊ個の部分集合を、偽鍵を用いてエンコードすることを含む。
【００２０】
本発明は、コンピュータ・プログラム装置であって、コンピュータによって使用可能な命令のプログラムを含むコンピュータ・プログラム記憶装置を含み、前記命令のプログラムが、ツリーの部分集合の集合を生成するためにツリーにアクセスする論理手段であって、ツリーが、危険にさらされた鍵を特徴とする少なくとも１つのトレイタ装置を表す葉を含む、論理手段と、偽鍵をｊ回暗号化し、セッション鍵をｍ−ｊ回暗号化する論理手段であって、ｍが、部分集合の集合に含まれる部分集合の数である、論理手段と、暗号化する手段に応答して、トレイタ部分集合を識別する論理手段と、トレイタ装置を識別するか使用不可にするためにトレイタ部分集合を使用する論理手段とを含む、コンピュータ・プログラム装置を適当に提供することができる。
【００２１】
コンピュータ・プログラム装置のさらなる好ましい特徴に、第１の態様の好ましい特徴による好ましい方法のステップをコンピューティング・システムに実行させる論理手段を含めることができる。
【００２２】
第２の態様で、本発明は、コンピューティング・システムにロードされ、実行される時に、第１の態様による方法のステップをコンピューティング・システムに実行させるコンピュータ・プログラム・コードを含むコンピュータ・プログラムを提供する。
【００２３】
第２の態様の好ましい特徴に、第１の態様の好ましい特徴による方法の好ましいステップをコンピューティング・システムに実行させるコンピュータ・プログラム・コードが含まれる。
【００２４】
本発明は、適当に、ステートレス・レシーバを表す複数の部分集合をエンコードするために偽鍵を使用することであって、前記レシーバのうちの少なくとも１つのトレイタ・レシーバが、少なくとも１つの海賊レシーバによって入手された少なくとも１つの危険にさらされた鍵に関連する、使用することと、海賊レシーバまたはそのクローンを使用するか、トレイタ・レシーバの識別を判定するか、海賊レシーバまたはそのクローンを危険にさらされた鍵を使用するデータの暗号化解除に有用でなくすることとを含む方法動作をコンピュータに実行させる命令を用いてプログラムされたコンピュータをさらに提供することができる。
【００２５】
適当に、部分集合が、部分集合の集合を定義し、コンピュータによって取り掛かられる方法動作が、葉を定義するツリーから導出された部分集合の集合を受け取ることであって、各葉が、めいめいのレシーバを表す、受け取ることと、トレイタ・レシーバを表す少なくとも１つの葉を含むものとして、部分集合の集合から少なくとも１つのトレイタ部分集合を識別することと、トレイタ部分集合を使用し、トレイタ・レシーバを識別することとをさらに含む。
【００２６】
適当に、コンピュータによって取り掛かられる方法動作が、トレイタ部分集合が少なくとも１つのトレイタ・レシーバを表すかどうかを判定し、そうである場合に、トレイタ部分集合を２つの子集合に分割することをさらに含む。
【００２７】
適当に、コンピュータによって取り掛かられる方法動作が、トレイタ部分集合がフロンティア集合の要素であるかどうかを判定し、そうである場合に、フロンティア集合から補間部分集合を除去することをさらに含む。
【００２８】
適当に、識別する動作が、部分集合の集合の複数の部分集合を偽鍵を用いてエンコードすることを含む。
【００２９】
適当に、コンピュータによって取り掛かられる方法動作が、確率を使用して、部分集合の集合に対する二分探索を実行することをさらに含む。
【００３０】
適当に、二分探索が、最初のｊ個の部分集合に偽鍵が含まれる時にメッセージを暗号化解除する確率ｐｊが、少なくとも所定の確率と等しいかどうかを判定することによって終了する。
【００３１】
適当に、トレイタ部分集合が、−ｐｊ−１−ｐｊ−  ＞ｐ／ｍである時に識別され、ここで、ｍが、部分集合の集合に含まれる部分集合の数である。
【００３２】
適当に、部分集合の集合が、レシーバのグループの各レシーバに、めいめいの私用情報Ｉｕを割り当てることと、少なくとも１つのセッション暗号化鍵Ｋを選択することと、取消済み集合Ｒに含まれないレシーバを、関連する部分集合鍵Ｌｉ１、…、Ｌｉｍを有する互いに素な部分集合Ｓｉ１、…、Ｓｉｍの集合に分割することと、セッション鍵Ｋおよび偽鍵を、部分集合鍵Ｌｉ１、…、Ｌｉｍを用いて暗号化することとによって生成され、ツリーが、ルートおよび複数のノードを含み、各ノードが、ラベルの集合に関連付けられ、各レシーバが、レシーバとルートとの間の直接パスからぶら下がるが直接パスに含まれないすべてのノードからラベルを割り当てられる。
【００３３】
適当に、本発明は、本明細書に記載の発明的論理に取り掛かるコンピュータ・システムを含む。本発明は、本発明の論理を保管し、論理を実行するためにプロセッサによってアクセスされることができるコンピュータ・プログラム製品でも実施することができる。また、本発明は、下で開示される論理に従うコンピュータ実施される方法である。
【００３４】
コンピュータを適当にプログラムして、偽鍵を使用してステートレス・レシーバを表す複数の部分集合をエンコードする。システム内の少なくとも１つのトレイタ・レシーバが、クローニングされた海賊レシーバによって入手された危険にさらされた鍵に関連する。海賊レシーバのクローンを使用して、コンピュータが、トレイタ・レシーバの識別を判定し、あるいは、適当な暗号化戦略を生成することによって、海賊レシーバ・クローンを、危険にされされた鍵を使用してデータを暗号化解除するのに有用でなくする。
【００３５】
もう１つの態様で、ブロードキャスト暗号化システム内で、関連する一意の危険にさらされた暗号化解除鍵を有するトレイタ・レシーバを識別する好ましい方法を開示する。この方法には、葉を定義するツリーから導出された部分集合の集合を受け取ることが含まれ、各葉が、めいめいのレシーバを表す。また、この方法には、少なくとも１つのトレイタ・レシーバを含むものとして部分集合の集合からトレイタ部分集合を識別することと、その後、トレイタ部分集合を使用し、トレイタ・レシーバを識別することが含まれる。
【００３６】
好ましい実施形態では、方法に、トレイタ部分集合が１つまたは複数のトレイタ・レシーバを表すかどうかを判定し、そうである場合に、トレイタ部分集合を２つの子集合に分割し、２つの個集合を使用して新しいトレイタ部分集合を識別することが含まれる。好ましい方法には、トレイタ部分集合がフロンティア集合の要素であるかどうかを判定し、そうである場合に、フロンティア集合から補間部分集合を除去することも含まれる。
【００３７】
トレイタ部分集合を識別する好ましい形には、偽鍵を用いて部分集合の集合の最初のｊ個の部分集合をエンコードし、その後、確率を使用して部分集合の集合に対する二分探索を実行することが含まれる。二分探索は、最初のｊ個の部分集合に偽鍵が含まれる時にメッセージを暗号化解除する確率ｐｊと、最初のｊ−１個の部分集合に偽鍵が含まれる時に暗号化解除する確率ｐｊ−１との間の差が、少なくとも所定の確率と等しいかどうかを判定することによって終了する。具体的に言うと、トレイタ部分集合は、−ｐｊ−１−ｐｊ−  ＞ｐ／ｍである時に識別され、ここで、ｍは、部分集合の集合に含まれる部分集合の数である。部分集合の集合は、二股に分けることができる部分集合を生成するという特性を有する部分集合カバー方式によって生成される。
【００３８】
もう１つの態様では、コンピュータ・プログラム装置に、ツリーの部分集合の集合を生成するためにツリーにアクセスする論理手段が含まれ、ツリーに、危険にさらされた鍵を特徴とする少なくとも１つのトレイタ装置を表す葉が含まれる。偽鍵をｊ回暗号化し、セッション鍵をｍ−ｊ回暗号化する論理手段が設けられ、ｍは、部分集合の集合に含まれる部分集合の数である。また、暗号化する手段に応答して、トレイタ部分集合を識別する論理手段がある。その後、論理手段で、トレイタ部分集合を使用して、トレイタ装置を識別する。
【００３９】
本発明の好ましい実施形態を、例としてのみ、添付図面に関して説明する。
【発明を実施するための最良の形態】
【００４０】
本発明の好ましい実施形態を、複数のブロードキャスト暗号化方法のいずれかと共に使用することができる。制限的でない例として、そのようなシステムの１つすなわち部分集合カバー・システムを、まず示し、その後、本発明のトレース・アルゴリズムを、部分集合カバー・システムに関して開示する。
【００４１】
まず図１を参照すると、上で参照した特許で開示されたシステムなどであるがこれに制限されない、ブロードキャスト・コンテンツ保護システムで鍵の集合を生成する、全般的に１０と指定されたシステムが示されている。「ブロードキャスト」は、コンテンツ・プロバイダから多数のユーザへの、ケーブル（衛星ソースから）、ワイヤ、ラジオ周波数（衛星ソースを含む）を介して同時に、または広く販売されるコンテンツ・ディスクからの、プログラムの広い散布を意味する。
【００４２】
図からわかるように、システム１０には、下の開示に従って機能する鍵集合定義モジュール１４にアクセスする鍵集合定義コンピュータ１２が含まれる。コンピュータ１２によって定義される鍵集合は、本明細書で「レシーバ」および「ユーザ」とも称する、コンテンツを暗号化解除するために内部のプロセッサを有する、潜在的にステートレスのプレイヤ−レコーダ装置１６によって使用される。コンテンツは、下で開示されるある種の鍵と共に、たとえば装置製造業者１６を介して媒体１７でめいめいの装置に供給される。プレイヤ−レコーダ装置は、その鍵集合にアクセスして、媒体上のまたは無線通信を介してブロードキャストされるコンテンツを暗号化解除することができる。本明細書で使用する「媒体」には、ＤＶＤ、ＣＤ、ハード・ディスク、およびフラッシュ・メモリ・デバイスを含めることができるが、これに制限はされない。代替実施形態では、各レシーバ１６が、モジュール１４を実行して、取り消されたレシーバの集合を与えられ、下で示す論理に取り掛かることによって、下で開示する「カバー」を計算するステップに取り掛かる。
【００４３】
モジュール１４に関連するプロセッサが、このモジュールにアクセスして、図示され下で説明される論理に取り掛かるが、この論理を、一連のコンピュータ実行可能命令としてプロセッサによって実行できることを理解されたい。システム１０を使用して、危険にさらされていないレシーバ１６がブロードキャスト・コンテンツを暗号化解除する能力を取り消さずに、危険にさらされたレシーバ１６がブロードキャスト・コンテンツを暗号化解除する能力を選択的に取り消す２つの方法すなわち、完全サブツリー法および部分集合差分法を、本明細書で開示する。
【００４４】
命令を、コンピュータ可読コード要素をその上に保管されたコンピュータ使用可能媒体を有するコンピュータ・ディスケットなどのコンピュータ可読媒体を有するデータ記憶装置に含めることができる。あるいは、命令を、ＤＡＳＤアレイ、磁気テープ、従来のハード・ディスク、電子読取専用メモリ、光学記憶装置、または他の適当なデータ記憶装置に保管することができる。本発明の例示的実施形態では、コンピュータ実行可能命令を、コンパイルされたＣ＋＋互換コードの行とすることができる。
【００４５】
実際に、本明細書の流れ図に、コンピュータ・プログラム・ソフトウェアで実施される本発明の好ましい実施形態の論理の構造を示す。当業者は、これらの流れ図に、本発明に従って機能する、集積回路上の論理回路を含むコンピュータ・プログラム・コード要素の構造が示されていることを諒解するであろう。あきらかに、本発明は、その本質的な実施形態において、プログラム・コード要素を、図示のものに対応する機能動作のシーケンスを実行するようにディジタル処理装置（すなわちコンピュータ）に指示する形にする機械構成要素によって実践される。
【００４６】
部分集合差分法および完全サブツリー法の両方によって実施される本発明の好ましい実施形態の全体的な論理を、図２に関して見ることができる。この開示において、Ｎ個のレシーバ１６がシステム１０に存在し、取り消されたレシーバが連繋して働き（暗号化の知識を共用することによって）すべてのレシーバがまだコンテンツを暗号化解除できる場合であっても、取消済みレシーバ部分集合Ｒのｒ個のレシーバがコンテンツを暗号化解除する能力を取り消すことができることが望ましいと仮定する。ブロック１９で開始されて、システムは、長寿命の部分集合鍵Ｌ１、…、Ｌｗを、部分集合の母集団Ｓ１、…、Ｓｗの対応する部分集合に割りて当ることによって開始され、この母集団に、レシーバが下の開示に従ってグループ化され、したがって、各部分集合Ｓｊが、それに関連する長寿命の部分集合鍵Ｌｊを有する。第１の（「完全サブツリー」）方法では、取消済み集合に含まれないレシーバをカバーする部分集合が、単に、下の開示に従って生成されるサブツリーである。第２の（「部分集合差分」）方法では、下でさらに示すように、取消済み集合に含まれないレシーバをカバーする部分集合が、第１サブツリーと、完全に第１サブツリー内にあるより小さいサブツリーとの間の差によって定義される。
【００４７】
ブロック２０で、コンテンツの暗号化解除に有用な私用情報Ｉｕを各レシーバｕに供給することによって、システムがさらに開始される。私用情報Ｉｕの詳細は、下でさらに示す。Ｉｕが、レシーバｕに供給される秘密情報である場合には、Ｓｊに含まれる各レシーバｕが、そのＩｕからＬｊを導出することができる。下でさらに完全に示すように、取消済み集合Ｒを与えられて、取り消されていないレシーバが、ｍ個の互いに素の部分集合Ｓｉ１、…、Ｓｉｍに分割され、短寿命のセッション鍵Ｋが、めいめいの部分集合Ｓｉ１、…、Ｓｉｍに関連する長寿命の部分集合鍵Ｌｉ１、…、Ｌｉｍを用いてｍ回暗号化される。部分集合鍵は、完全サブツリー法では明示的な部分集合鍵であり、部分集合差分法では部分集合ラベルによって誘導される。
【００４８】
具体的には、ブロック２２で、少なくとも１つのセッション鍵Ｋを選択し、これを用いて、無線または有線の通信パスまたはＣＤおよびＤＶＤなどの記憶媒体のいずれかを介してメッセージＭでブロードキャストされるコンテンツを暗号化する。セッション鍵Ｋは、メッセージごとに新規に選択されるビットのランダム・ストリングである。望まれる場合に、複数のセッション鍵を使用して、メッセージＭのめいめいの部分を暗号化することができる。
【００４９】
下で説明する方法の両方で、取り消されていないレシーバを、ブロック２４でツリーを使用して互いに素な部分集合Ｓｉ１、…、Ｓｉｍに分割する。この部分集合を、本明細書で時々「サブツリー」と称するが、第１の方法では、サブツリーが明示的に考慮され、第２の方法では、サブツリーが、「第１サブツリーから、完全に第１サブツリーに含まれる第２サブツリーを引いたもの」という形であるものとみなされる。各部分集合Ｓｉ１、…、Ｓｉｍは、めいめいの部分集合鍵Ｌｉ１、…、Ｌｉｍに関連する。任意のデータ・ツリー様の構造が、本明細書で企図されているが、開示において、ツリーは２分木全体であると仮定する。
【００５０】
ブロック２６に進んで、一般に、セッション鍵Ｋは、部分集合鍵Ｌｉ１、…、Ｌｉｍのそれぞれを１回用いて、ｍ回暗号化される。ブロードキャストされる、結果の暗号文は、角型括弧の間の部分がメッセージＭのヘッダを表し、ｉ１、ｉ２、…、ｉｍが互いに素の部分集合のインデックスを表すものとして、次のように表すことができる。
＜［ｉ１、ｉ２、…、ｉｍ、ＥＬｉ１（Ｋ）、ＥＬｉ２（Ｋ）、…、ＥＬｉｍ（Ｋ）］、ＦＫ（Ｍ）＞
【００５１】
一実施形態では、暗号化プリミティブＦＫが、メッセージＭと、セッション鍵Ｋによって生成されるストリーム暗号のＸＯＲをとることによって実施される。暗号化プリミティブＥＬは、長寿命の部分集合鍵を使用してセッション鍵Ｋをレシーバ１６に送達する方法である。ＦＫ、ＥＬに関するすべての暗号化アルゴリズムが、本発明の範囲内であることを理解されたい。ＥＬの好ましい実施形態の１つを、ブロック暗号の接頭部切捨指定とすることができる。ｌが、長さがＥＬのブロック長と等しいランダム・ストリングを表すと仮定し、Ｋが、長さがたとえば５６ビットの暗号ＦＫの短い鍵であると仮定する。その場合に、［Ｐｒｅｆｉｘ−Ｋ−ＥＬ（ｌ）／Ｋ］が、強い暗号化をもたらす。したがって、接頭部を切り捨てられたヘッダは、下記になる。
＜［ｉ１、ｉ２、…、ｉｍ、Ｕ、［Ｐｒｅｆｉｘ−Ｋ−ＥＬｉ１（Ｕ）］／Ｋ、…、［Ｐｒｅｆｉｘ−Ｋ−ＥＬｉｍ（Ｕ）］／Ｋ］、ＦＫ（Ｍ）＞
【００５２】
これによって、有利なことに、ヘッダの長さが、ｍ−Ｌ−ではなく約ｍ−Ｋ−ビットに短縮される。ＥＬの鍵長さが最小限である場合に、下記を使用して、敵対者が、同一のストリングｌをｍ個の異なる鍵を用いて暗号化することからもたらされるブルートフォース攻撃を有するという要因ｍの利点を除去することができる。ストリングｌ／ｉｊが暗号化される。すなわち、
＜［ｉ１、ｉ２、…、ｉｍ、Ｕ、［Ｐｒｅｆｉｘ−Ｌ−ＥＬｉ１（Ｕ／ｉ１）］／Ｋ、…、［Ｐｒｅｆｉｘ−Ｌ−ＥＬｉｍ（Ｕ／ｉｍ）］／Ｋ］、ＦＫ（Ｍ）＞
【００５３】
暗号化プリミティブＥおよびＦを実施する好ましい制限的でない形を説明したので、図３に移ると、この図には、レシーバ１６が取り掛かる暗号化解除論理が示されている。ブロック２８から開始して、各取り消されていないレシーバｕが、暗号文の部分集合識別子ｉｊを見つけて、そのレシーバが部分集合Ｓｉｊに属するようにする。下でさらに開示するように、レシーバが、取消済み集合Ｒに含まれる場合に、ブロック２８の結果は存在しない。次に、ブロック３０で、レシーバが、その私用情報Ｉｕを使用して、部分集合Ｓｉｊに対応する部分集合鍵Ｌｉｊを抽出する。この部分集合鍵を使用して、ブロック３２でセッション鍵Ｋを判定し、ブロック３４で、セッション鍵Ｋを使用してメッセージを暗号化解除する。
【００５４】
上で説明した全体的な論理に取り掛かる２つの好ましい方法を、下で開示する。どちらにおいても、鍵を部分集合に割り当てる形およびコレクションからの互いに素な部分集合を使用して、取り消されていないレシーバをカバーする方法として、部分集合のコレクションが指定される。どちらにおいても、システム内のレシーバの集合が、２分木全体などであるがこれに制限されない木の葉を確立する。
【００５５】
説明する第１の方法は、図４から７に示された完全サブツリー法である。図４のブロック３６から開始して、独立のランダムな部分集合鍵Ｌｉを、ツリーの各ノードｖｉに割り当てる。この部分集合鍵Ｌｉは、ノードｖｉをルートとするすべての葉を含む部分集合に対応する。その後、ブロック３８で、各レシーバｕに、そのレシーバからルートまでの直接パス内のすべての部分集合鍵を与える。図７を一時的に参照するとわかるように、部分集合Ｓｉに含まれるレシーバｕには、ノードｖｉに関連する部分集合鍵Ｌｉ、ならびにＳｉに含まれるレシーバと木のルートとの間にあるノードＰに関連する鍵が与えられる。
【００５６】
メッセージを送信し、あるレシーバがメッセージを暗号化解除する能力を取り消すことが望まれる時に、図５の論理が呼び出されて、取り消されていないレシーバが互いに素な部分集合に分割される。ブロック４０から開始して、取り消されたレシーバの集合であるＲの葉によって定義されるスパニング・ツリーを発見する。スパニング・ツリーは、「取り消された」葉を接続する２分木全体の最小限のサブツリーであり、スタイナ木とすることができる。ブロック４２に進んで、ツリー内で１度のノード（すなわち、最小限のツリーに直接に隣接するノード）に隣接するルートを有するサブツリーを識別する。これらのサブツリーによって、「カバー」が定義され、部分集合Ｓｉ１、…、Ｓｉｍが確立される。カバーには、すべての取り消されていないレシーバが含まれる。したがって、ブロック４４で、カバーによって定義される部分集合鍵を使用して、セッション鍵Ｋを暗号化する。
【００５７】
メッセージを暗号化解除するために、各レシーバが、図６の論理を呼び出す。ブロック４６で開始して、上位ノードがメッセージ・ヘッダ内の集合ｉ１、ｉ２、…、ｉｍの中にあるかどうかを判定することによって、レシーバの上位ノードのどれかが、カバーの部分集合鍵に関連するかどうかを判定する。レシーバの私用情報Ｉｕは、完全サブツリー法ではツリー内の位置および上位ノードに関連する部分集合鍵からなるが、この私用情報Ｉｕが、この判定に使用される。上位が、メッセージ・ヘッダ内で見つかる（レシーバが、取り消されていないレシーバであることを示す）場合には、ブロック４８で部分集合鍵を使用してセッション鍵Ｋを暗号化解除し、その後、ブロック５０で、セッション鍵Ｋを使用してメッセージを暗号化解除する。
【００５８】
完全サブツリー法では、ヘッダに、多くともｒ×ｌｏｇ（Ｎ／ｒ）個の部分集合鍵および暗号化が含まれる。これは、鍵および暗号化の平均の数でもある。さらに、各レシーバは、ｌｏｇ  Ｎ個の鍵を保管しなければならず、各レシーバが、多くともｌｏｇ  ｌｏｇ  Ｎ回の演算および単一の暗号化解除動作を使用してメッセージを処理する。
【００５９】
次に、図８から１３を参照すると、レシーバの取消に関する部分集合差分法を見ることができる。部分集合差分法では、各レシーバが、完全サブツリー法より比較的多数の鍵（．５ｌｏｇ２  Ｎ  ＋  ．５ｌｏｇ  Ｎ  ＋  １個の鍵）を保管しなければならないが、メッセージ・ヘッダに、多くとも２ｒ−１個の部分集合鍵および暗号化が含まれ（平均１．２５ｒ個）、これは、完全サブツリー法より実質的に少ない。また、部分集合差分法では、メッセージが、擬似乱数ジェネレータの多くともｌｏｇ  Ｎ回の適用と単一の暗号化解除動作を使用して処理される。
【００６０】
図８および図９を参照すると、部分集合差分法では、部分集合が、より大きい部分集合Ａと、Ａに完全に含まれるより小さい部分集合Ｂとの間の差とみなされる。したがって、図からわかるように、より大きいサブツリーが、ノードｖｉをルートとし、より小さいサブツリーは、ｖｉから下降したノードｖｊをルートとする。結果の部分集合Ｓｉ、ｊは、ｖｊの下の「ｎｏ」というラベルを付けられた葉（および「ｙｅｓ」というラベルを付けられた葉より暗い色の葉）を除く、ｖｉの下のすべての葉「ｙｅｓ」からなる。図９にこれを示すが、部分集合ｖｉ、ｊは、より大きい三角の中でより小さい三角の外の区域によって表される。
【００６１】
部分集合差分法で、メッセージを送信し、一部のレシーバがメッセージを暗号化解除する能力を取り消すことが望まれる時に、上で説明した構造が、図１０に示されているように使用される。ブロック５２で開始して、取り消されたレシーバの集合であるＲに含まれる葉によって定義されるスパニング・ツリーを発見する。このスパニング・ツリーは、「取り消された」葉を接続する２分木全体の最小限のサブツリーであり、スタイナ木とすることができる。ブロック５４に進んで、カバー・ツリーＴを、スパニング・ツリーとして初期化する。その後、反復ループを開始し、カバー・ツリーＴが多くとも１つのノードを有するようになるまで、ノードをカバー・ツリーから除去し、カバーにサブツリーを追加する。この出力によって、取り消されていないレシーバのカバーが定義される。
【００６２】
具体的に言うと、ブロック５４からブロック５６に移ると、その最小の共通の上位ｖにＴに  の葉が含まれないように、カバー・ツリーＴ内で葉ｖｉおよびｖｊを見つける。判断菱形５７で、カバー・ツリーＴに１つの葉だけが存在するかどうかを判定する。複数の葉が存在する場合に、論理は、ブロック５８に移動して、ｖｉがｖｌから下降し、ｖｊがｖｋから下降し、ｖｌ、ｖｋがｖの子（すなわち、ｖとｖｌ、ｖｋの間に介在するノードがない、ｖの直接の子孫）であるように、ｖ内のノードｖｌ、ｖｋを見つける。対照的に、Ｔに単一の葉だけが存在する時には、この論理は、判断菱形５７からブロック６０に移動して、ｖｉ＝ｖｊ＝唯一の残っている葉をセットし、ｖをＴのルートに置き、ｖｌ＝ｖｋ＝ルートをセットする。
【００６３】
ブロック５８または６０から、この論理は、判断菱形６２に移動する。判断菱形６２では、ｖｌとｖｉが等しいかどうかを判定する。同様に、ｖｋとｖｊが等しいかどうかを判定する。ｖｌとｖｉが等しくない場合には、この論理はブロック６４に移動して、Ｔに部分集合Ｓｌ、ｉを追加し、Ｔからｖの子孫のすべてを除去し、ｖを葉にする。同様に、ｖｋとｖｊが等しくない場合に、この論理はブロック６４に移動し、Ｔに部分集合Ｓｋ、ｊを追加し、Ｔからｖの子孫のすべてを除去し、ｖを葉にする。ブロック６４からまたは、不等が判定されない時に判断菱形６２から、この論理はブロック５６にループ・バックする。
【００６４】
上記の部分集合差分鍵割当方法の全体像を念頭において、特に好ましい実施形態を示す。レシーバが属する部分集合の総数は、Ｎと同程度に大きいが、これらの部分集合を、第１部分集合ｉ（そこから別の部分集合が引かれる）によって定義されるｌｏｇ  Ｎ個のクラスタにグループ化することができる。木全体の内部ノードに対応する１＜ｉ＜Ｎのそれぞれについて、独立のランダムなラベルＬＡＢＥＬｉが選択され、これによって、Ｓｉ、ｊの形の正当な部分集合のすべてのラベルが誘導される。このラベルから、部分集合鍵を導出する。図１１に、下で説明する好ましいラベリング方法を示す。Ｌｉというラベルを付けられたノードは、サブツリーＴｉのルートであり、その子孫は、本発明の原理に従ってラベルを付けられる。
【００６５】
Ｇが、入力の長さを３倍にする暗号擬似乱数シーケンス・ジェネレータである場合に、Ｇ＿Ｌ（Ｓ）は、種Ｓに対するＧの出力の左１／３を表し、Ｇ＿Ｒ（Ｓ）は右１／３を表し、Ｇ＿Ｍ（Ｓ）は中央１／３を表す。ノードｖｉをルートとし、ラベルＬＡＢＥＬｉを有する、カバー・ツリーＴのサブツリーＴｉを検討されたい。このノードに、Ｓというラベルが付けられる場合に、その２つの子に、それぞれＧ＿Ｌ（Ｓ）およびＧ＿Ｒ（Ｓ）というラベルが付けられる。集合Ｓｉ、ｊに割り当てられる部分集合鍵Ｌｉ、ｊは、サブツリーＴｉ内で導出されるノードｖｊのＬＡＢＥＬｉ、ｊというラベルのＧ＿Ｍである。各ラベルＳによって、３つの部分すなわち、左右の子のラベルおよびノードの鍵が誘導されることに留意されたい。その結果、ノードのラベルを与えられれば、そのすべての子孫のラベルおよび鍵を計算することが可能である。１つの好ましい実施形態では、関数Ｇは暗号ハッシュ、（例えばSecure Hashing Algorithm-1）であるが、他の関数を使用することもできる。
【００６６】
図１２に、部分集合差分法でレシーバがどのようにしてメッセージを暗号化解除するかを示す。ブロック６６で開始して、レシーバは、それが属する部分集合Ｓｉ、ｊを、関連するラベル（レシーバがＬＡＢＥＬｉ、ｊおよび部分集合鍵Ｌｉ、ｊを導出できるようにする私用情報の一部）と共に見つける。このラベルを使用して、レシーバは、ブロック６８で、関数Ｇを多くともＬＯＧ  Ｎ回評価することによって、部分集合鍵Ｌｉ、ｊを計算する。その後、レシーバは、ブロック７０で、その後のメッセージ暗号化解除のために、部分集合鍵Ｋを使用して、セッション鍵Ｋを暗号化解除する。
【００６７】
図１３に、ラベルが、したがって部分集合鍵が、部分集合差分でどのようにレシーバに割り当てられるかを示す。本明細書で開示されるラベリング方法は、各レシーバが保管しなければならない鍵の数を最小にするのに使用される。
【００６８】
ブロック７２で開始して、各レシーバに、そのレシーバとルートの間の直接パスに含まれるのではなく、直接パスから「ぶら下がる」ノードの、ｕの上位のあるノードｖｉによって誘導されたラベルが与えられる。これらのラベルによって、ブロック７４でレシーバの私用情報Ｉｕが確立され、後続のメッセージについて、ブロック７６で、セッション鍵が、ラベルから導出された部分集合鍵を用いて暗号化される。
【００６９】
図１４を一時的に参照して、上の原理を説明する。レシーバｕのラベルＳを有するすべてのｖｉ上位ノードについて、レシーバｕは、ノードｖｉからレシーバｕへの直接パスからぶら下がるすべてのノード７１のラベルを受け取る。下でさらに説明するように、これらのラベルは、すべてがＳから導出されることが好ましい。完全サブツリー法と著しく対照的に、図８から１４に示された部分集合差分法では、レシーバｕが、レシーバｕからノードｖｉへの直接パスに含まれるすべてのノード７３からラベルを受け取らない。これらのラベルを使用して、レシーバｕは、上で説明した関数Ｇを評価することによって、他の部分集合鍵を計算せずに、ノードｖｉをルートとするすべての集合（直接パス集合を除く）の部分集合鍵を計算することができる。
【００７０】
従来のマルチキャスト・システムは、逆方向の秘密（backward secrecy）に欠けている、すなわち、取り消されているが常時リスンしているレシーバが、それでも暗号化されたコンテンツのすべてを記録でき、その後、将来のある時に、有効な新しい鍵を獲得し（たとえば再登録によって）、これによって過去のコンテンツの暗号化解除が可能になる。本発明の好ましい実施形態を、そのようなシナリオで使用して、取り消されたレシーバの集合に、まだ割り当てられていないすべてのレシーバ識別を含めることによって、逆方向の秘密の欠如を直すことができる。これは、すべてのレシーバが、連続する順序で葉に割り当てられる場合に行うことができる。この場合に、すべての割り当てられない識別の取消が、メッセージ・ヘッダ・サイズの、そのような識別の数に比例するのではなく適度な増加をもたらす。
【００７１】
本発明の好ましい実施形態では、メッセージ・ヘッダでの部分集合ｉｊの簡潔なエンコーディングを有することと、レシーバが、そのレシーバが部分集合ｉｊに属するかどうかをすばやく判定する方法を提供することが望ましいことも認められている。ノードが、そのノードのルートへのパスによって示され、０が左の枝を示し、１が右の枝を示すと仮定する。パスの終りは、１とそれに続く０個以上の０のビットによって示される。したがって、ルートは、１０００．．．．０００ｂであり、ルートの右端の子は、０１０００．．．０００ｂであり、ルートの左端の子は、１１０００．．．０００ｂであり、葉は、ｘｘｘｘ．．．ｘｘｘｘ１ｂである。
【００７２】
本明細書で認められているように、より大きいサブツリーのルートのパスは、より小さいサブツリーのルートのパスの部分集合であり、その結果、部分集合差分を、より小さいサブツリーのルートと、より大きいサブツリーのルートへのパスの長さによって示すことができる。これを念頭におけば、レシーバは、下記のＩｎｔｅｌ  Ｐｅｎｔｉｕｍ（Ｒ）プロセッサ・ループを実行することによって、それが所与の部分集合に含まれるかどうかをすばやく判定することができる。
【００７３】
ループの外で、下記のレジスタをセット・アップする：ＥＣＸに、レシーバの葉ノードが格納され、ＥＳＩが、メッセージ・バッファ（最初のバイトが、より大きいサブツリーへのパスの長さであり、次の４バイトが、より小さいツリーのルートである）をポイントし、静的テーブルによって、パスの長さによってインデクシングされる時に、最初の長さビットが１であり、残りのビットが０である３２ビットが出力される。
2004527937.tif 000058
【００７４】
レシーバがループから抜けた場合に、これは、必ずしもレシーバが特定の部分集合に属することを意味しない。より小さい除外されたサブツリー内にある場合があり、そうである場合には、ループに戻らなければならない。しかし、大多数の場合に、レシーバは、より大きいサブツリー内にも含まれないので、ループ内では処理時間がほとんどかからない。
【００７５】
部分集合差分法のさらなる最適化では、システム・サーバが、数百万個になる可能性があるすべてのレベルのそれぞれを記憶する必要がない。その代わりに、ｉ番目のノードのラベルを、ノードの秘密の関数にすることができる。この秘密の関数は、番号ｉに適用される時にｉ番目のノードのラベルを与えるのに秘密鍵を使用するトリプルＤＥＳ暗号化とすることができる。
【００７６】
本発明の好ましい実施形態をそれと共に使用することができる部分集合カバー・システムの詳細を説明したので、図１５および１６を参照されたい。ブロック１００で開始して、部分集合Ｓｉ１、…、Ｓｉｍの分割Ｓを、認可トレース機関によって入手された疑わしい海賊クローン装置に入力する。最初の分割は、取り消された装置の現在の集合によって誘導され、装置が取り消されていない場合には、最初の分割Ｓが、すべてのユーザの集合である。判断菱形１０２に移動して、クローンが、上で開示した部分集合カバー・システムの原理に従って、好ましくは部分集合差分実施形態の原理に従って、分割Ｓを使用してコンテンツを暗号化解除したかどうかを判定する。クローンがコンテンツを暗号化解除するとみなされるのは、ある所定の確率、たとえばｐ＞．５でメッセージを暗号化解除できる場合である。ほとんどの実用的なクローンで、ｐ＝１である。クローンが暗号化解除できない場合には、クローンをうちまかす暗号化が見つかっており、したがって、この処理は状態１０４で終了する。
【００７７】
しかし、クローンが、コンテンツを成功裡に暗号化解除した場合には、この処理は、ブロック１２４に移る。ブロック１２４では、下でさらに説明する図１６の部分集合トレース論理が、分割Ｓに対して実行されて、部分集合Ｓｉｊが作られ、論理は、ブロック１０６に進んで、部分集合Ｓｉｊを受け取る。判断菱形１０８に進んで、部分集合Ｓｉｊが、単一のトレイタ候補だけを含むかどうか、すなわち、部分集合Ｓｉｊが、単一の葉だけを有するかどうかを判定する。そうである場合には、トレイタが見つかっており、この処理は、ブロック１１０で、ｊ番目の装置を「トレイタ」として示し、取り消されていないレシーバの集合からトレイタを除去することと、トレイタを取り消されたレシーバの集合Ｒに置くことによって、トレイタを取り消す。これによって、ブロック１１１で新しいカバー集合Ｓが定義され、処理は、ブロック１２４に進むが、このブロックについては下でさらに完全に説明する。
【００７８】
部分集合Ｓｉｊが、複数のトレイタ候補を有する場合には、この論理は、判断菱形１０８からブロック１１２に進み、ここで、集合Ｓｉｊを、２つの子集合Ｓ１ｉｊおよびＳ２ｉｊに分割する。これは、部分集合カバー・システムの二股に分かれる特性のゆえに可能であり、部分集合カバー・システムでは、サブツリーをおおむね（必ずしも正確ではない）２つに分割することができる。
【００７９】
ｔ個のトレイタをトレースするのに必要なメッセージの長さを減らすことによって効率の良さを実現するために、好ましい実施形態の１つで、ブロック１１２から、ブロック１１４から１２２に示されたサブルーチンに移動することができる。このサブルーチンは、トレイタを含むことがまだ見つかっていない部分集合を単一の効率的に処理されるグループに合併するように機能する。そのような削減が必要でない場合には、Ｓ１ｉｊおよびＳ２ｉｊをカバーに加え、ブロック１１４から１２２を省略する。
【００８０】
ブロック１１４で、子集合Ｓ１ｉｊおよびＳ２ｉｊを、フロンティア集合Ｆに加え、「仲間集合」としてお互いに関連付ける。次に、判断菱形１１６で、集合Ｓｉｊが前のフロンティア集合Ｆ（すなわち、子集合Ｓ１ｉｊおよびＳ２ｉｊが追加される前に存在した集合Ｆ）に含まれたかどうかを判定する。含まれた場合には、これが、集合Ｓｉｊが、やはりフロンティア集合Ｆに含まれた補集合、いわゆる「相棒」集合を有したことを意味し、ブロック１１８で、「相棒」集合（１つまたは複数のレシーバを表す）が、フロンティア集合Ｆから除去される。この形で、まだトレイタ候補を含むことが見つかっていない集合が、フロンティア集合Ｆとは別にグループ化される。
【００８１】
ブロック１１８からまたは、テスト結果が否定である場合の判断菱形１１６から、この論理は、ブロック１２０に進み、ここで、カバーＣを、上で示した部分集合カバー原理に従って、フロンティア集合Ｆの集合で表されないすべてのレシーバｕについて計算する。具体的に言うと、フロンティア集合Ｆに含まれる集合によって表されるレシーバを、一時的に取消済み集合Ｒに分類し、上の原理に従ってカバーを判定する。ブロック１２２で、新しい分割Ｓを、カバーＣとフロンティア集合Ｆに含まれる部分集合との和集合として定義する。その後、ブロック１２４で、新しいＳに対して図１６の部分集合トレース論理を実行して、別のＳｉｊを作り、この論理はブロック１０６にループ・バックする。
【００８２】
したがって、図１６の部分集合トレース論理を検討すると、ブロック１２６で開始して、分割Ｓが受け取られる。この論理では、ステップのシーケンスが管理され、通常のステップでは、暗号化が実行され、最初のｊ個の部分集合が、セッション鍵Ｋと同一の長さを有する偽鍵ＲＫを用いてエンコードされる。すなわち、ｐが、クローンが分割Ｓを用いて正しく暗号化解除する確率である時に、下記の形のメッセージが作られる。
＜Ｅｌｉ１（ＲＫ）、ＥＬｉ２（ＲＫ）、…、ＥＬｉｊ（ＲＫ）、ＥＬｉ（ｊ＋１）（Ｋ）、…、ＥＬｉｍ（Ｋ）、ＦＫ（Ｍ）＞
ｐｊは、最初のｊ個の部分集合に偽鍵が含まれる時の暗号化解除の確率である。−ｐｊ−１−ｐｊ−  ＞ｐ／ｍの場合に、本発明の好ましい実施形態によれば、Ｓｉｊに、トレイタを表す葉が含まれる。確率ｐｊを見つけるために、ｍ２ｌｏｇ（１／ｅ）回の実験に取り掛かって、実験の全シーケンスのうちで何回、クローンが実際のメッセージＭを出力するかを判定する。具体的に言うと、クローンが、最後のｍ−ｊ個の部分集合からの鍵（実際のセッション鍵Ｋを暗号化した鍵）を全く有しない場合に、クローンは、絶対にＭを判定できない（単なる偶然を除いて）。
【００８３】
したがって、二分探索を実行して、全区間［０、ｍ］から開始し、上下界［ａ、ｂ］（ブロック１３０で［０、ｍ］に初期化される）を使用して連続して区間を半分にすることによって、トレイタを含むＳｉｊを効率的に見つける。ｐ０＝ｐかつｐｍ＝０であることに留意されたい。さらに、ほとんどの実用的な場合に、ｐ＝１すなわち、クローンが、通常動作中に必ず暗号化解除する。
【００８４】
二分探索は、判断菱形１３２で開始され、ここでは、上界および下界が１つ離れている（探索の終りを示す）かどうかを判定する。そうである場合には、この論理は、ブロック１３４で、上界ｂとしてｊ番目のトレイタのインデックスを返す。そうでない場合には、この論理は、ブロック１３６に移って、区間［ａ、ｂ］の中点ｃの確率すなわち、最初のｃ個の部分集合に偽鍵が含まれ、他の部分集合に真の鍵が含まれる時の暗号化解除の確率を見つける。
【００８５】
本発明の好ましい実施形態によれば、最初のｊ個の部分集合に偽鍵が含まれる時にメッセージが成功裡に暗号化解除される確率ｐｊは、繰り返して、鍵Ｋと共にメッセージＭを選択することと、ＭをＦｋ（Ｍ）として暗号化することと、偽鍵を用いて最初のｊ個の部分集合をエンコードし、真の鍵Ｋを用いて最後のｍ−ｊ個の部分集合をエンコードすることと、クローンがＭを成功裡に暗号化解除するかどうかを観察することによって計算される。
【００８６】
その後、判断菱形１３８で、中点の確率と下界の確率の間の差の絶対値が、少なくとも、下界の確率と上界の確率の間の差の半分の絶対値と等しいかどうかが判定される（すなわち、−ｐｃ−ｐａ−  ＞  −ｐｃ−ｐｂ−であるかどうかを判定するために）。そうである場合に、ブロック１４０で、上界ｂを現在の中点ｃと等しくすることと、上界確率ｐｂを中点確率ｐｃと等しくすることによって、区間を半分の［ａ、ｃ］にする。その一方で、判断菱形１３８での否定のテストの場合には、この論理はブロック１４２に進む。ブロック１４２では、下界を現在の中点ｃと等しくすることと、下界確率ｐａを中点確率ｐｃと等しくすることによって、区間を半分の［ｃ、ｂ］にする。この論理は、その後、判断菱形１３２にループ・バックする。
【００８７】
ブロック１３６で、中点の確率ｐｃが、１／ｍの精度まで計算されることが好ましい。ｐｃが、１−ｅの確率で正確に推定されることを保証するために、クローンに対するｍ２  ｌｏｇ（１／ｅ）回の照会を観察することが必要である。
【００８８】
したがって、図１６の論理では、クローンに対するｍ２ｌｏｇ（ｍ）ｌｏｇ（１／ｅ）回の照会を使用することが好ましい。望まれる場合に、１−Ｑの確率（Ｑは１／２に近い値、たとえばＱ＝１／３である）で正しい判断が得られると各ステップで仮定される、ノイズの多い二分探索に取り掛かることができる。各回答が、ヒストリから独立のある固定された確率（たとえば２／３超）で正しいモデルで、ｍ個の集合に対する二分探索をｌｏｇ  ｍ  ＋  ｌｏｇ  １／Ｑ回の照会で実行することが可能である。上で開示した実施形態では、中点確率が、確率Ｑで誤った値を生じると仮定することができる。これは、手順全体に対する照会の数を、ｍ２（ｌｏｇ  ｍ  ＋  ｌｏｇ  １／Ｑ）に減らすことができることを暗示する。というのは、確率１−Ｑでｐｃを正確に計算するために、各ステップでｍ２回の照会が必要になるからである。
【００８９】
同一の入力を用いてクローンに対してトレース・アルゴリズムを並列に稼動させることによって、トレイタを、複数のクローンからトレースすることができる。最初の入力は、どれもが取消済み集合Ｒに配置されてないすべてのユーザの集合から生じる分割Ｓ０である。処理が進行するにつれて、最初のクローンが、その集合の１つでトレイタを「検出」する時に、そのクローンは、それ相応にその集合を再分割する（トレイタを取消済み集合Ｒに移動することによって）。新しい分割が、すべてのクローンに同時に入力される。同時方法の出力は、すべての取り消されたレシーバおよびクローンを無効にする分割（または「取消戦略」）である。
【００９０】
本発明の好ましい実施形態は、比較的小さいメッセージを使用して、比較的多数のトレイタをトレースする能力を提供する。本発明の好ましい実施形態を、上で参照した部分集合カバー・システムとシームレスに統合することができる。また、トレースできるトレイタの数に対する先験的な限界は不要である。さらに、本発明の好ましい実施形態は、クローンがトレースに対抗して行うことに無関係に、トレイタをトレースすることまたは海賊クローンを有用でなくすることのいずれかによって機能する。
【００９１】
本明細書で図示され説明された特定の「ブロードキャスト暗号化システムでトレイタ・レシーバをトレースする方法」は、本発明の上で説明した目的を完全に達成することができるが、これが、本発明の現在好ましい実施形態であり、したがって本発明の好ましい実施形態によって広義に企図される対象を表すことと、本発明の好ましい実施形態の範囲が、当業者に明白になる可能性がある他の実施形態を完全に包含することと、本発明の好ましい実施形態の範囲が、したがって、請求項以外の何物によっても制限されず、請求項では、単数形の要素への言及が、請求項で他の形で指定されない限り、「唯一」ではなく「少なくとも１つ」を意味することを理解されたい。当業者に既知であるか後に既知になる、上で説明した好ましい実施形態の要素に対する構造的同等物および機能的同等物のすべてが、参照によって本明細書に特に組み込まれ、請求項に含まれることが意図されている。さらに、請求項によって包含されるために、装置または方法が、本発明の好ましい実施形態によって解決されることが求められるすべての問題のそれぞれに対処する必要はない。さらに、この開示の要素、構成要素、または方法ステップは、それらの要素、構成要素、または方法ステップが請求項で特に具陳されているかどうかに無関係に、公衆に捧げられる。本明細書の請求の要素は、その要素が句「〜の手段」と特に具陳されない限り、または、方法クレームの場合に、その要素が「動作」の代わりに「ステップ」と具陳されない限り、米国特許法セクション１１２第６パラグラフの規定の下で解釈されてはならない。
【図面の簡単な説明】
【００９２】
【図１】本システムのブロック図である。
【図２】暗号化論理全体の流れ図である。
【図３】暗号化解除論理全体の流れ図である。
【図４】完全サブツリー法の鍵割当部分の流れ図である。
【図５】完全サブツリー法の暗号化部分の流れ図である。
【図６】完全サブツリー法の暗号化解除部分の流れ図である。
【図７】完全サブツリーの部分集合の概略図である。
【図８】部分集合差分法の部分集合の概略図である。
【図９】部分集合差分法の部分集合のもう１つの形態の概略図である。
【図１０】部分集合差分法のカバーを定義する論理の流れ図である。
【図１１】鍵割当を示す、部分集合差分法のツリーの部分集合の概略図である。
【図１２】部分集合差分法の暗号化解除部分の流れ図である。
【図１３】部分集合差分法の鍵を割り当てる論理の流れ図である。
【図１４】部分集合差分法のツリーの部分集合の概略図である。
【図１５】本発明のトレース論理を示す流れ図である。
【図１６】トレース論理の部分集合トレース・モジュールを示す流れ図である。




【国際調査報告】
2004527937.tif 000059
2004527937.tif 000060
2004527937.tif 000061