(57)【要約】ホワイトリストベースの認証では、システム(100)の第１の装置(102)は、無効でない装置識別子の範囲を特定するグループ証明書を使用して、第２の装置(103)に対して自己を認証し、前記範囲は第１の装置(102)の装置識別子を含む。好ましくは、装置識別子は階層順のツリーのリーフノードに対応し、グループ証明書は、リーフノードが前記範囲に対応するサブツリーを表すツリーのノード(202-207)を特定する。グループ証明書はまた、リーフノードが無効の装置識別子に対応するサブツリーを表すサブツリーの更なるノード(308、310、312)を特定することができる。代替として、装置識別子は連続した順序の範囲から選択され、グループ証明書は、連続した順序の範囲のサブ範囲を特定し、前記サブ範囲はホワイトリストの装置識別子を含む。
2005530396.tif 000002
【特許請求の範囲】
【請求項１】
複数の装置を有するシステムであって、
前記複数の装置が第１の装置と第２の装置を少なくとも有し、
前記複数の装置はそれぞれ装置識別子を割り当てられ、
前記第１の装置が、無効でない装置識別子の範囲を特定するグループ証明書を第２の装置に提示することにより、第２の装置に対して自己を認証するように構成され、
前記範囲が前記第１の装置の装置識別子を含むシステム。
【請求項２】
請求項１に記載のシステムであって、
各装置識別子が階層順のツリーのリーフノード(leaf  node)に対応し、
前記グループ証明書が、前記階層順のツリーのノードを特定し、
前記ノードは、無効でない装置識別子の範囲に前記リーフノードが対応するサブツリーを表すシステム。
【請求項３】
請求項２に記載のシステムであって、
前記グループ証明書が、前記サブツリーの更なるノードを特定し、
前記更なるノードは、無効でない装置識別子の範囲から除外された装置識別子に前記リーフノードが対応する更なるサブツリーを表すシステム。
【請求項４】
請求項１に記載のシステムであって、
各装置識別子は連続した順序の範囲から選択され、
前記グループ証明書が、前記連続した順序の範囲のサブ範囲を特定し、
前記サブ範囲が、無効でない装置識別子の範囲を含むシステム。
【請求項５】
請求項１に記載のシステムであって、
外部ソースからグループ証明書を受信し、前記システムの少なくとも１つの装置識別子が前記受信したグループ証明書で特定される特定の範囲内にある場合には、前記受信したグループ証明書を前記システムの装置に配信するように構成されたゲートウェイ装置を更に有するシステム。
【請求項６】
請求項５に記載のシステムであって、
ゲートウェイ装置が、全ての前記受信したグループ証明書の少なくともサブセットをキャッシュするように更に構成されたシステム。
【請求項７】
請求項１に記載の方法であって、
単一のグループ証明書が、無効でない装置識別子の複数の各範囲を特定するシステム。
【請求項８】
請求項７に記載のシステムであって、
前記単一のグループ証明書の前記複数の各範囲が連続した順序であり、
前記単一のグループ証明書が、連続した順序の最低と最高の各範囲の表示を通じて、前記複数の各範囲を特定するシステム。
【請求項９】
請求項１に記載のシステムであって、
前記グループ証明書が有効期間の表示を有し、
前記有効期間が条件内である場合に、前記第２の装置が前記第１の装置を認証するシステム。
【請求項１０】
請求項１に記載のシステムであって、
前記第２の装置は、前記第１の装置の認証の成功時に、最低の条件内の証明書のバージョン表示を有する保護されたコンテンツを前記第１の装置に配信し、前記グループ証明書のバージョン表示が前記最低の条件内の証明書のバージョン表示と少なくとも等しい場合に、前記第１の装置を成功して認証するように構成されるシステム。
【請求項１１】
請求項１に記載のシステムであって、
前記第２の装置は、前記第１の装置の認証の成功時に、保護されたコンテンツを配信し、前記グループ証明書のバージョン表示が前記第２の装置のグループ証明書のバージョン表示と少なくとも等しい場合に、前記第１の装置を成功して認証するように構成されるシステム。
【請求項１２】
装置識別子を割り当てられ、無効でない装置の範囲を特定するグループ証明書を第２の装置に提示することにより、第２の装置に対して自己を認証するように構成された第１の装置であって、前記範囲が前記第１の装置の装置識別子を含む第１の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、第１の装置と第２の装置とを有するシステムであって、第１の装置が装置識別子を割り当てられ、第２の装置に対して自己を認証するように構成されたシステムに関するものである。
【背景技術】
【０００２】
近年、コンテンツ保護システムの量は急速に成長してきている。これらのシステムには、不正コピーのみを保護するものもあり、ユーザがコンテンツにアクセスすることを禁止するものもある。第１の分類はコピープロテクト(CP:Copy  Protection)システムと呼ばれており、この種類のコンテンツ保護は安価な方法で実装可能なように考えられ、コンテンツプロバイダと双方向のインタラクションを必要としないため、従来から家庭用電化製品(CE:Consumer  Electronics)装置で主要な焦点になっている。これらの例は、CSS(Content  Scrambling  System)や、DVD  ROMディスクの保護システムや、DTCP(Digital  Transmission  Content  Protection)であるIEEE1394接続用の保護システムがある。第２の分類は、いくつかの名前で知られている。放送業界では一般的にCA(Conditional  Access)システムとして知られており、インターネット業界では一般的にDRM(デジタル著作権管理(Digital  Rights  Management)システムとして知られている。
【０００３】
近年、新しいコンテンツ保護システム(ThomsonからのSmartRight又はDTLAからのDTCP等)が導入されてきており、一式の装置が双方向接続を介して相互に認証することができる。この認証に基づいて、装置は相互に信頼し、これにより保護されたコンテンツを交換することが可能になる。コンテンツに伴うライセンスには、どの権利をユーザが所有しており、コンテンツでどの動作が実行を許可されているかが記載されている。
【０００４】
装置間の相互通信に必要な信頼はいくつかの秘密に基づいており、安全な実装を有していると信頼及び保証された装置に対してのみ認識されている。秘密の認識は認証プロトコルを使用してテストされる。これらのプロトコルの最善の解決策は、一対の２つの異なる鍵を使用する‘公開鍵’の暗号化を使用するものである。テストされる秘密は一対の鍵であり、公開鍵はテストの結果を確認するために使用され得る。公開鍵の正確性を確保し、鍵の対が証明された装置の正当な対であるか否かを検査するために、公開鍵は、証明機関(全装置の公開鍵/秘密鍵の対の分配を管理する組織)によりデジタル署名された証明書が伴う。単純な実装では、証明機関の公開鍵は装置の実装にハードコードされている。
【０００５】
証明書は、Mビットのメッセージ部とそれに追加してCビットの署名部を含むビット列である。Cは、通常は512ビットから2048ビットの範囲内であり、一般的に1024ビットである。M＜Cの場合には、署名はメッセージ自体に基づいて計算され、M＞Cの場合には、署名はメッセージの要約に基づいて計算される。以下では、最初のケースであるM＜Cに関連するものである。署名はメッセージの内容に敏感に依存し、証明機関によりのみ構成され得るが、全員により検証され得るという特性を有する。この文脈における検証とは、署名がメッセージと相反しないことを検査することを意味する。誰かがメッセージの単一のビットを変更した場合には、署名は一致しない。
【０００６】
一般的なセキュリティのシナリオでは、いくつかの異なる装置が含まれており、その装置の全ては同等のレベルの不正防止を実装していないことがある。従って、そのようなシステムは、デジタルコンテンツの不正保存、コピー及び／又は再配信を可能にする個々の装置のハッキングに対して耐久性があるべきである。耐久性を増加させる重要な技術は、ハッキングされた装置のいわゆる無効である。
【０００７】
無効は、その装置の信頼の撤回である。無効の効果は、ネットワークの他の装置が無効の装置と通信しようとしないことである。無効はいくつかの異なる方法で達成され得る。２つの異なる技術は、いわゆるブラックリスト(無効の装置のリスト)又はホワイトリスト(無効でない装置のリスト)を使用することである。
【０００８】
ブラックリストのシナリオでは、通信相手の信頼を検証する装置が、最新バージョンのリストを有する必要があり、他の装置のIDがそのリスト上にあるか否かを検査する。ブラックリストの利点は、装置がデフォルトで信頼され、装置のIDが無効リストにあるときに限り、その装置の信頼が無効になる。このリストは最初には非常に小さいが、無制限に増える可能性がある。従って、この無効リストのCE装置の配置と保存は長期的には問題になることがある。
【０００９】
ホワイトリストのシナリオでは、許可された通信相手のリストに装置が依然としてあることを他の装置に対して証明しなければならない。装置がホワイトリストにあるということを示す最新バージョンの証明書を提示することにより、前記のことを実行する。ホワイトリスト技術は、装置がホワイトリストにあることを証明する各装置に格納された固定長の証明書のみを有することにより、保存の問題を克服する。無効の装置以外の全ての装置に新しいバージョンのホワイトリスト証明書を送信することにより、無効が動作する。装置のストレージが限られているため、ホワイトリスト証明書の配信は、効率的な機構が利用可能でない場合には、ほとんど克服できない問題になる。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
ホワイトリスト証明書の効率的な配信と保存を可能にするプリアンブルによるシステムを提供することが本発明の１つの目的である。
【課題を解決するための手段】
【００１１】
この目的は、本発明に従って、複数の装置を有するシステムで達成され、前記複数の装置は第１の装置と第２の装置を少なくとも有し、前記複数の装置はそれぞれ装置識別子を割り当てられ、第１の装置は無効でない装置識別子の範囲を特定するグループ証明書を第２の装置に提示することにより、第２の装置に対して自己を認証するように構成され、前記範囲は第１の装置の装置識別子を含む。
【００１２】
本発明は、ブラックリストの利点(最初は小さい配信リスト)とホワイトリストの主な利点(限られた保存)を結合した技術を提供する。好ましくは、この技術は、装置のIDを証明する装置証明書を更に使用する。この装置証明書は、(無効に関わらず)最初の信頼の基礎として既に装置内に存在しており、例えば工場での製造中に組み込まれる。
【００１３】
各装置は、単一のグループ証明書(すなわち、その装置識別子を含む範囲を特定するグループ証明書)を格納しさえすればよい。このことは、証明書の保存要件が固定であり、事前に計算可能であることを意味する。従って、例えば従来技術で必要なように“十分に大きい”メモリではなく、ちょうどよい大きさのメモリを組み込むことにより、これらの装置の実装を最適化することが可能になる。
【００１４】
配信に関しては、システムの単一の装置毎に異なる証明書を常に送信する必要がなくなる。適切なグループの装置識別子を選択することにより、グループの全ての装置に対して単一のグループ証明書で十分である。
【００１５】
当然のことながら、第２の装置に対する第１の装置の認証は、グループ証明書を提示するステップに加えて、その他のステップを有してもよい。例えば、第１の装置はまた、第２の装置との安全な認証チャネルを確立し、その装置識別子を含む証明書を第２の装置に提示すること等ができる。第１の装置の装置識別子がグループ証明書に定められた範囲に実際に含まれることを第２の装置が決定した場合には、認証が成功する。単に第２の装置に対してそのグループ証明書を第１の装置に提示させることにより、認証は相互になり得る。
【００１６】
一実施例では、各装置識別子が階層順のツリーのリーフノード(leaf  node)に対応し、グループ証明書が階層順のツリーのノードを特定し、前記ノードは、リーフノードが無効でない装置識別子の範囲に対応するサブツリーを表す。このことは、階層の使用によりグループを非常に効率的に特定することが可能になるという利点を有する。非常に大きいグループの装置は、階層の上位のノードに対応する単一の識別子で特定され得る。
【００１７】
この実施例の改良では、グループ証明書は、サブツリーの更なるノードを更に特定し、前記更なるノードは、リーフノードが無効でない装置識別子の範囲から除外された装置識別子に対応する更なるサブツリーを表す。以前の手法では、サブツリーの装置が無効になると、残りの無効でないサブツリー用に複数の新たな証明書が発行される必要がある。この改良は、サブツリーの少数の装置が無効になったときに、多数の新たなサブツリー用の新たな証明書を即座に発行する必要がないという利点を有する。
【００１８】
拡張として、更にもう１つのサブツリー(更なるサブツリーの部分)を特定するその他のグループ証明書が発行され得る。このように、サブツリーの前記部分が、無効でない装置識別子の範囲で維持され得る。
【００１９】
グループの１つの装置ID(例えば装置ID0)を無効にする前に常に、同意を行うことが望ましいことがある。このように実際の装置が無効にならなくても、常にグループ証明書が一貫して形成される。
【００２０】
更なる実施例では、各装置識別子は連続した順序の範囲から選択され、グループ証明書は連続した順序の範囲のサブ範囲を特定し、前記サブ範囲は、無効でない装置識別子の範囲を含む。これは、前述の単純なブラックリスト方法の小さい伝送サイズとホワイトリスト方法の小さい保存サイズとを有利に結合する。全ての無効の装置のソートされたリスト(例えば昇順)が作られると、認証されるグループは、このリストの如何なる２つの要素間の装置で構成される。伝送サイズは、単純なブラックリストの場合とほぼ同等である(当然のことながら、伝送されるデータはブラックリストと同一であるが、解釈が異なる)。
【００２１】
更なる実施例では、前記システムは、外部ソースからグループ証明書を受信し、システムの少なくとも１つの装置識別子が前記受信したグループ証明書で特定される特定の範囲内にある場合には、その受信したグループ証明書をシステムの装置に配信するように構成されたゲートウェイ装置を更に有する。このことは、システムの装置の多数は低い処理能力を有すると考えられるが、その装置が外部ソースにより送信された全てのグループ証明書を処理する必要がなく、ゲートウェイ装置によりフィルタリングされたもののみを処理すればよいという利点を有する。
【００２２】
更なる実施例では、ゲートウェイ装置は、全ての受信したグループ証明書の少なくともサブセットをキャッシュするように更に構成される。このように、後で新たな装置がシステムに追加された場合に、ゲートウェイ装置はキャッシュから新たな装置のグループ証明書を探し、キャッシュされたグループ証明書を新たな装置に配信することができる。従って、新たな装置はシステムの他の装置に対して迅速に自己を認証し始めることができる。
【００２３】
更なる実施例では、単一のグループ証明書は、無効でない装置識別子の複数の各範囲を特定する。このように、前述のゲートウェイ装置のような装置は、大きい計算コストで多数のデジタル署名を検証することなく、特定のグループ証明書が特定の装置に関連するか否かを容易に知ることができる。その結果、全く関連のないグループ証明書をフィルタで除去することができ、又は関連のあるグループ証明書の如何なるデジタル署名も検証することができる。
【００２４】
この実施例の変形では、単一のグループ証明書の複数の各範囲は連続した順序であり、単一のグループ証明書は、連続した順序の最低と最高の各範囲の表示を通じて、複数の各範囲を特定する。このことにより、この証明書が関連するものであるか否かをフィルタリングして決定することが可能になる。これは、署名を調べている宛先装置自体で検証され得る。このことにより、無関係の証明書の大半を迅速に拒否することが可能になる。
【００２５】
更なる実施例では、グループ証明書は有効期間の表示を有し、その有効期間が条件内であれば、第２の装置が第１の装置を認証する。“条件内”とは、“現在日時が示された期間内にある”ことを単に意味するだけでなく、好ましくは示された期間に対するある程度の延長も受け入れることができるべきである。このように、新たなグループ証明書の伝搬の遅延により、自動的に装置が認証の失敗を生じなくなる。
【００２６】
更なる実施例では、第２の装置は、第１の装置の認証の成功時に、最低の条件内の証明書のバージョン表示を有する保護されたコンテンツを第１の装置に配信し、グループ証明書のバージョン表示が最低の条件内の証明書のバージョン表示と少なくとも等しい場合に、第１の装置を成功して認証するように構成される。
【００２７】
装置は、自ら使用しているものと少なくとも同じ新しさのバージョンを通信相手から必要とするが、このことは、無効になったリストにある装置がコンテンツの如何なる交換からも完全に閉め出されるという問題を提供する。新たな無効リストが配信される前には許可されていた古いコンテンツからも締め出される。この実施例では、このような問題が回避される。後で第１の装置が無効になっても、その古いグループ証明書を使用して依然として古いコンテンツにアクセスすることが可能である。
【００２８】
“バージョン”は、例えば“バージョン3.1”のように数字で特定され、又は例えば“2002年1月バージョン”のように特定の時点と結合され得る。後者のものは、特定のバージョンが古すぎるため、既に条件内ではないことを人間に説明することが容易であるという点で有利である。その特定のバージョンは、現時刻に対してその時点を比較することにより容易に認識され得る。純粋に数字のバージョンでは、このことは困難である。
【００２９】
この表示は、例えばデジタル著作権コンテナ、Entitlement  Management  Message(EMM)等の一部にすることにより、好ましくは安全にコンテンツに組み込まれる。このように、アタッカーが表示を変更することができなくなる。
【００３０】
更なる実施例では、第２の装置は、第１の装置の認証の成功時に、保護されたコンテンツを配信し、グループ証明書のバージョン表示が第２の装置のグループ証明書のバージョン表示と少なくとも等しい場合に、第１の装置を成功して認証するように構成される。
【００３１】
装置識別子を割り当てられ、無効でない装置の範囲を特定するグループ証明書を第２の装置に提示することにより、第２の装置に対して自己を認証するように構成された第１の装置を提供することが、本発明の更なる目的であり、前記範囲は第１の装置の装置識別子を含む。
【発明を実施するための最良の形態】
【００３２】
本発明は、一例として添付図面を参照して更に詳細に以下に説明される。
【００３３】
図面を通じて、同じ参照数字は類似の機能又は対応する機能を示す。図面に示された機能のうちのいくつかは、一般的にソフトウェアに実装され、それゆえにソフトウェアモジュール又はオブジェクトのようなソフトウェア要素を表す。
【００３４】
図１は、ネットワーク110を介して相互接続された装置101-105を有するシステム100を概略的に示している。この実施例では、システム100はホームネットワークである。一般的なデジタルホームネットワークは、複数の装置(例えば、ラジオ受信機、チューナ／デコーダ、CDプレイヤ、一対のスピーカ、テレビ、VCR、テープデッキ等)を有する。１つの装置(例えばテレビ)が他の装置(例えばVCR)を制御するように、これらの装置は通常は相互接続される。例えばチューナ／デコーダ又はセットトップボックス(STB)のような１つの装置は、通常は他の装置に対する中央制御を提供する中央装置である。
【００３５】
一般的に音楽や歌曲や映画やTV番組や写真等を有するコンテンツは、住居ゲートウェイ又はセットトップボックス101を通じて受信される。ソース(source)はブロードバンドケーブルネットワークや、インターネット接続や、衛星ダウンリンク等と接続され得る。コンテンツは、ネットワーク110を通じて処理用のシンク(sink)に転送され得る。シンクは、例えばテレビディスプレイ102、携帯表示装置103、携帯電話104及び／又は音声再生装置105でもよい。
【００３６】
コンテンツアイテムが処理される正確な方法は、装置の種類とコンテンツの種類に依存する。例えばラジオ受信機では、処理は音声信号を生成し、それをスピーカに供給することを有する。テレビ受信機では、処理は一般的に、音声信号と映像信号を生成し、これらをディスプレイスクリーンとスピーカに供給することを有する。その他の種類のコンテンツでは、同様の適切な動作が行われなければならない。処理はまた、受信信号の解読又は逆スクランブルや、音声信号と映像信号の同期等のような動作を有してもよい。
【００３７】
セットトップボックス101又はシステム100のその他の装置は、適切な大きさのハードディスクのようなストレージ媒体S1を有してもよく、受信コンテンツの記録と後の再生を可能にする。ストレージS1は、セットトップボックス101が接続されているある種類のパーソナルデジタルレコーダ(PDR)(例えばDVD+RW)でもよい。コンテンツはまた、コンパクトディスク(CD)又はデジタル多用途ディスク(DVD)のようなキャリア120に格納されたシステム100に提供され得る。
【００３８】
携帯再生装置103と携帯電話104は、基地局111を使用して(例えばBluetooth又はIEEE802.11bを使用して)ネットワーク110に無線で接続される。その他の装置は、従来の有線接続を使用して接続される。装置101-105が相互作用することを可能にするために、異なる装置がメッセージ及び情報を交換して相互に制御することを可能にするいくつかの相互運用標準が利用可能である。１つの周知の標準は、2000年1月に公表されたホーム・オーディオ／ビデオ・インターオペラビリティ(HAVi)標準のバージョン1.0であり、これはアドレスhttp://www.havi.orgでインターネット上で入手可能である。その他の周知の標準は、ドメスティック・デジタル・バス(D2B:domestic  digital  bus)標準と、IEC1030に記載された通信プロトコルと、ユニバーサル・プラグアンドプレイ(http://www.upnp.org)がある。
【００３９】
ホームネットワークの装置101-105がコンテンツの不当なコピーを行わないように確保することがしばしば重要である。このため、一般的にデジタル著作権管理(DRM:Digital  Rights  Management)と呼ばれるセキュリティのフレームワークが必要である。
【００４０】
１つのそのようなフレームワークでは、ホームネットワークは概念的には限定アクセス(CA:Conditional  Access)ドメインとコピープロテクト(CP:Copy  Protection)ドメインに分割される。一般的にシンク(sink)はCPドメインに配置される。このことは、コンテンツがシンクに提供されるときに、CPドメインのコピープロテクト機構により不当なコンテンツのコピーが行われ得ないように確保する。CPドメインの装置は、一時コピーを行うストレージ媒体を有してもよいが、そのようなコピーはCPドメインからエクスポートされないことがある。このフレームワークは、この出願と同一出願人による欧州特許出願01204668.6(代理人管理番号PHNL010880)に記載されている。
【００４１】
選択された特有の方法に関わらず、セキュリティフレームワークを実装したホームネットワークの全ての装置は、実装の要件に従ってそれを行う。このフレームワークを使用して、これらの装置は相互に認証し、コンテンツを安全に配信することができる。コンテンツへのアクセスはセキュリティシステムにより管理される。このことにより、プロテクトされていないコンテンツが不当な装置に漏れ、信頼のない装置から生じたデータがシステムに入ることが回避される。
【００４２】
事前に認証が成功した他の装置にのみ装置がコンテンツを配信することが重要である。このことは、対抗者が不当な装置を使用して不当なコピーを行うことができないように確保する。例えば、認証された製造者のみが認証の成功に必要な特定の秘密を認識しているため、又はその装置が信頼された第三者機関により発行された証明書を備えているため、装置が認証された製造者により製造された場合にのみ、成功して認証することができる。
［装置の無効］
一般的に、装置の無効は、装置内の秘密情報(例えば識別子又は解読鍵)が漏れた場合、又はハッキングを通じて発見された場合の、その機能の１つ以上の縮小又は完全な抑止である。例えば、CE装置の無効は、その装置が解読及び使用可能なデジタルコンテンツの種類に制限をかけてもよい。代替として、無効により、CE装置がコピーのような受信した如何なるコンテンツについての特定の機能を実行できないようにしてもよい。
【００４３】
無効の通常の効果は、ネットワーク110の他の装置が無効の装置と通信しようとしないことである。無効はいくつかの異なる方法で達成され得る。２つの異なる技術は、いわゆるブラックリスト(無効の装置のリスト)又はホワイトリスト(無効でない装置のリスト)を使用することである。
【００４４】
複数のバージョンの無効リストが存在してもよい。最新バージョンの実行のためにいくつかの機構が使用され得る。例えば、装置は、自ら使用しているものと少なくとも同じ新しさのバージョンを通信相手から必要とする。しかし、このことは、無効になったリストにある装置がコンテンツの如何なる交換からも完全に閉め出されるという問題を提供することがある。新たな無効リストが配信される前ではその装置は古いコンテンツが再生可能であるが、その装置は古いコンテンツからも締め出される。
【００４５】
その他のバージョン制御機構は、配信されたコンテンツを特定のバージョンの無効リストにリンクさせることであり、すなわち、無効リストの現在のバージョン番号がコンテンツに伴うライセンスの一部になる。全ての通信相手がコンテンツに必要なバージョンと少なくとも同じ新しさのバージョンを有する場合にのみ、装置がコンテンツを配信すべきである。バージョン番号付けは、例えば単調増加数を使用することにより実装され得る。
【００４６】
無効の機構の魅力(それ故に用途の可能性)を決定する複数のコスト要素が存在する。１つの要素は伝送サイズである。全ての無効でない装置は、無効システムの現在バージョンに依然として参加しているという事実を証明する署名付きのメッセージを受信しなければならない。その他の要素は保存サイズである。全ての無効でない装置は、無効システムの現在のバージョンに依然として参加していることを証明する証明書を格納しなければならない。これらの２つの要素は矛盾するように見える。小さい伝送サイズでは、全ての無効になった装置の表示を含む１つの署名付きメッセージを機関がブロードキャストするが、100,000くらいの無効の装置の場合にはかなりの保存の要件を生じる。保存サイズを最小化するために、証明機関は、装置の装置ID(例えばシリアル番号、イーサーネットアドレス等)を含む個々の証明書をそれぞれの無効でない装置に伝送する。しかし、このことは、ブロードキャストされる多数のメッセージを生じる。当然のことながら、双方向リンク(例えば電話接続装置を備えたセットトップボックス)の場合、ADの装置に関連のある証明書をダウンロードしてもよい。
【００４７】
前述のように、ブラックリストの手法とホワイトリストの手法により表される２つの手段の間で有意義な妥協を提供することが、本発明の目的の１つである。本発明は、暗号化で周知の階層的鍵配信機構に部分的に基づく。本発明の実施例では、証明機関は特定のグループの装置が無効でないことを確認する署名付きメッセージ(無効でないグループ毎に１つの署名付きメッセージ)を伝送する。一般的にグループの数は装置の数よりかなり小さいため、限られた伝送サイズを必要とする。更に、装置は、その装置がメンバであるグループに関するメッセージのみを格納するため、限られた保存サイズのみを必要とする。２つの装置間の認証中に、“証明者”は２つの証明書を提示する。証明者がメンバであるグループが無効になっていないことを示す最新の無効メッセージと、その装置ID(すなわち、その装置が最新の無効メッセージに関するステップで述べられたグループのメンバであること)を確認する(工場で組み込まれた)証明書である。
【００４８】
一般的に、このような証明書は、装置ID  iと公開鍵PKiとを有する。iがメンバであるグループの証明書を傍受し、iを模倣しようとするアタッカーは、PKiに対応する秘密鍵SKiを有さず、前述の認証プロトコルに従って全ての更なる通信が中断される。
【００４９】
利点を記述するために、以下の表記が導入される。
・全ての装置が装置ID  iを有する。0≦i＜Nであり、N=2nは装置の総数であり、各装置ID番号はnビットの文字列である。
・D={0,1,...,N-1}は、全装置のセットである。
・R={f1,f2,...,fr}は、r個の無効の装置のセットである(代々引き継いで変化/増加する)。
【００５０】
証明機関は、(個々に合わせた)メッセージをmグループの全てS1,...Smに送信し、そのグループのメンバが無効になっていないことを確認する。グループiの各メンバは、グループiのメッセージ／証明書を格納する。S1∪S2∪...∪Sm=D|Rであるようにグループが選択される(すなわち、全セットSk(1≦k≦m)が合わせて、Dから無効の装置のセットを引いたものに等しい無効でない装置のセットを形成する)。
【００５１】
解決すべき課題は、所定のRについてS1...SmへのD|Rの区分を選択する方法である。留意すべき点は、この区分はRが変更したときの次の世代で異なる点である。Nが一般的に40ビット数であり(実質的に全世界で一人当たり約200個の装置を許容する)、r=|R|であることを仮定すると、無効の装置の数は＜100,000である。以下では、５つの区分について説明され、伝送及び保存サイズにおけるその各コストが説明される。この区分化機構は、単純なブラックリスト、単純なホワイトリスト、完全サブツリー方法(Complete  Subtree  Method)、サブセット差分方法(Subset  Difference  Method)、変更ブラックリスト方法(Modified  Black-Listing  Method)である。区分化方法とそのコストを説明した後に、署名の影響が検討される。
［単純なブラックリスト］
前述のように、伝送サイズを最小化するために、最善のものは、Rの要素を記述する署名付きメッセージを全装置に送信することである。実際に、D|Rは単一のグループm=1に区分化される。伝送サイズの理論上の下限は以下ようになる。
【００５２】
【数１】
2005530396.tif 000003
1≪r≪Nの時に近似値が適用でき、これはコンテンツプロテクトシステムに関連するパラメータの範囲である。この下限に近い通常の実装は、機関がr・nビットを取る全ての無効の装置の署名付きリストを送信することである(各装置がnビットの装置IDを有する)。保存サイズは明らかに同じであり、r・nビットである(〜1/2Mバイト)。
［単純なホワイトリスト］
保存サイズを最小化するために、機関は装置IDを含む異なる証明書をそれぞれの無効でない装置に送信する。実際に、D|Rはm=|D|R|=(N-r)グループに区分化され、各グループは唯一のメンバを備える。伝送サイズは(N-r)・nである(又は場合によっては(N’-r)・nであり、N’=これまで発行された装置数である)。
［完全サブツリー方法(Complete  Subtree  Method)］
一式の識別子を階層順のセットに区分化する方法は、D.NaorとM.NaorとJ.Lotspiechの2001年SpringerのAdv.  in  Cryptology,  CRYPTO’01,  LNCS2139の41-62ページ“Revocation  and  Tracing  Schemes  for  Stateless  Receivers”に記載されているが、この文献は、本発明のようなグループ識別子を作るために順序付けられたセットを使用することについて説明しない。
【００５３】
完全サブツリー方法(Complete  Subtree  Method)と、後述するサブセット差分方法(Subset  Difference  Method)を説明するために、全ての可能なnビットの装置IDは、(n+1)レイヤのバイナリツリーのリーフ(終点)として解釈される。用語のいくつかを以下に示す。
・ツリーの終点はリーフと呼ばれる。(n+1)レイヤのツリーに2nのリーフが存在する。
・ノードは、ツリーの分岐が接合する所である。リーフはノードとも考えられる。
・ルートは、頂点のノードである。
・ノードνがノードuのすぐ上にある場合、νはuの親と呼ばれ、uはνの子と呼ばれる。νのその他の子u’はuの兄弟と呼ばれる。νはその親や祖父等と共にuの祖先と呼ばれ、逆にuはそれらの子孫と呼ばれる。
・νをルートとするサブツリーは、νとその全ての子孫で構成されるセットである。
【００５４】
ツリーを上に移動すること(祖先にアクセスすること)は、装置IDのバイナリ表示のLSB(最小位ビット)をレイヤ毎に１ビットずつ切り取るようなものである。
【００５５】
複数のリーフR={f1,...,fr}が無効になることを仮定する。全ての無効のリーフから上にツリーのルートまでパスが描かれる。合流するパスの集合は、リーフRに対応するSteinerツリーST(R)と呼ばれる。これが図２に示されており、N=16の装置についてバイナリツリー構成が示されている。装置IDが0と7と8と9の装置が無効になっている。最終的に頂点のノード201と無効のノードを接続するツリーを通じたパスは、対応するSteinerツリーST(R)を形成する。これらのパスは囲われた領域202-207の外側にある。それぞれの囲われた領域の頂点に、囲われた領域により表されたグループSiを生成するStainerツリーを取り付けている兄弟のノードがある。これらの囲われた領域はS0001、S001、S010、S0110、S101、S11とラベル付けされている。
【００５６】
完全サブツリー方法は、ST(R)を“取り付けている”ノード(すなわち{ν1,...,νm}と呼ばれるST(R)のノードの兄弟)に注意を向ける。証明機関は区分S1,...,Smを選択し、Siはνiをルートにするサブツリーのリーフに対応する。各証明書は１つのみのνiを含む。構成により、Rの要素はSiの要素でなくなり、D|Rの各要素はS1∪S2∪...∪Smに含まれなければならない。グループは重複しない。
【００５７】
ST(R)を取り付けている約m=r・n個のノード(それぞれの無効の装置毎にnのノード(ルートへのパスはnのノードを有する)とrの装置)が存在すると考えられる。しかし、m≦r・(n-log2r)であることがわかる。その理由は、ルートに到達する前にST(R)のパスが長く合流する傾向にあるからである。このことと各νiがnビット数であるという事実を使用して、無効メッセージの伝送サイズは、n・r・(n-log2r)[数十Mバイト]の上限に制約される。保存サイズに関しては、装置は所属するSiの署名のみ(nビット)を格納する。
【００５８】
更なる装置(例えば図２の装置ID3の装置)が無効になる場合には、S001に代替する新たなグループ(及び対応するグループ証明書)S0010が作られる。この代替は、例えばS0010に高いバージョンを追加することにより、実現され得る。グループ証明書が有効期間表示を有する場合、証明書S0010はその有効期間が経過した後に自動的に消滅し、代替が自動的になる。
【００５９】
その代わりに装置ID14の装置が無効になると、２つの新たなグループ証明書が必要になる。グループS110に対応する第１のグループ証明書は、装置ID14を含まないグループS11のサブツリーを特定する。第２のグループ証明書は、S1111のサブツリーに対応する。
［サブセット差分方法(Subset  Difference  Method)］
N=16の装置について図３に示されているこの方法は、前述の完全サブツリー方法と同様に、バイナリツリーのリーフとして装置の装置IDを解釈する。同様に、SteinerツリーST(R)が描かれる。ここで、ST(R)で出次数1のチェーン、すなわち、ST(R)に単一の子又は兄弟のみを有するSteinerツリーの結果のノード(図３の点線)が特定される。その各チェーンにグループSa,bが割り当てられ、そのグループSa,bに以下のように証明書が送信される。aをチェーンの最初の要素(出次数2の直後のノード)とし、bを最後の要素(出次数2のリーフ又はノード)とする。この場合、Sa,bはaをルートとするサブツリーのリーフのセットからbをルートとするサブツリーのリーフを引いたものになる。
【００６０】
装置ID  0、7、8、9の装置が無効になっている。対応するSteinerツリーは、0000、000、00、0、01、011、0111、1000、1001、100、10、1のラベルのノードと頂点ノード301により形成される。aは各囲われた領域の頂点のノード302、304、306であり、bはノード308、310、312である。Sa,bは、最も外側の囲われた領域から、bノード308-312を取り付けているサブツリーにより示された領域を引いたものである。
【００６１】
留意すべき点は、(ツリーの下から上に進む２つのパスの合流の間の)そのようなチェーンは無効の子孫を有することができないことである(そうでなければ、Steinerツリーのこのチェーンにノード出次数2が存在する)。留意すべき点は、バイナリツリーが使用されているという事実により、グループは重複しないことである。当然のことながら、重複が生じ得るその他の種類のツリー又は階層順が使用され得る。これは本発明にとって重要ではない。
【００６２】
この構成は非常に効率的であることがわかる。D|Rをカバーするために、せいぜい2r-1グループSa,bが必要になる。実際に最悪の場合には、ランダムに選択されたR={f1,...,fr}について現実的な数のグループは1.25・rであるという事実を不明確にする。伝送サイズを決定するために、Sa,bの対{a,b}を効率的に符号化する方法を計算する必要がある。aがレイヤjにあり、bがレイヤkにある場合には、bはaと共通する最初のjビットを有する点に留意すべきである。
【００６３】
{a,b}を符号化する現実的な方法は、j‖k‖bを伝送することであり、“‖”は連結を示す。jとkはlog2nビット(現実的なN、rの場合は約6ビット)を取るため、j‖ｋ‖bの長さは、上限(n+2・log2n)に制約される。従って、合計伝送サイズは(2r-1)・(n+2・log2n)に制約され、一般的には1.25r・(n+2・log2n)である[一般的な値を使用して〜1Mバイト]。
【００６４】
更なる装置が無効になると(例えば図３の装置ID3の装置)、新しいグループ(及び対応するグループ証明書)S001,0011とS000,0000が作られ、S00,0000と交替する。
［変更ブラックリスト方法(Modified  Black-Listing  Method)］
この方法は、前述の単純なブラックリスト方法の小さい伝送サイズと、ホワイトリスト方法の小さい保存サイズとを直接結合する。基本的にD|Rはm=|D|R|=(r+1)グループに区分化され、各グループSiは装置{fi+1...fi+1-1}で構成される。単純な機構では、このことは2・r・nの伝送サイズを導く。効率的な機構は以下の通りである。全ての無効の装置のソートされたリスト(例えば昇順)が作られると、認証グループは、このリストの何らかの２つの要素間の装置で構成される。よって、伝送サイズはせいぜいr・nのみであり、これは単純なブラックリストの場合のサイズと同じである(当然のことながら、伝送されるデータはブラックリストと同一であるが、解釈が異なる)。
【００６５】
保存については、装置は、その装置IDを含む２つの無効の装置の装置IDを包含する証明書のみを抽出すればよい。例えば、図４において、装置4はグループS0,7をカバーする証明書(約2nビットの情報)のみを保存する。
【００６６】
当然のことながら、順序付けされたリストの境界の表記は、多様な方法で選択され得る。前述の例では、数字0と7が２つの無効の装置を表し、無効でないリストは1から6を含む数字を有する。同様にグループS0,7をS1,6と呼ぶこともできる。これは単なる決まりと表記の容易さの問題である。
［効率的な証明書の配信］
前述の段落は、装置をグループに分割し、グループに証明書を配信することにより、装置に無効/認証情報を(伝送サイズと保存サイズの双方に関して)効率的な方法で提供する方法について説明した。以下では、Sa,bのa,bのようなグループ識別子(グループID)を証明書に変更する方法(すなわち、そのようなグループ識別子に証明機関の署名を適用する方法)に関して、いくつかの例を説明する。前述のように、メッセージサイズ自体に関係なく、署名はCビット(一般的に1024ビット)だけメッセージを拡大する。単純には、証明書がmグループに送信され、各グループ識別子がlビットである場合には、合計伝送サイズはm・lビットではなく、m・(l+C)ビットである。前述の方法では、lは一般的に40...100ビットのオーダーに過ぎない(すなわちl≪C)ため、署名が伝送/保存サイズの大半を構成する。しかし、Cは署名が保護するメッセージサイズに無関係であるため、発明者は署名によるオーバーヘッドを大幅に減少させる以下の最適化を提案する。
【００６７】
第１の最適化機構では、証明書は、複数グループのグループIDを含むメッセージ部分で構成され、そのグループIDの全てに署名が追加される。証明書はいわばグループのグループを確認する。留意すべき点は、現実的な理由で、グループのグループにおけるグループIDの合計の長さは、好ましくはCを超えない。
【００６８】
更なる最適化機構において、証明書のメッセージ部分は圧縮される。長さm＜Cのメッセージの署名は、メッセージが署名自体から取り出され得るという特性を有する。単純には、グループID自体を証明書のメッセージ部分に含める必要がないと考えるかもしれない。しかし、署名処理が非常にコストのかかるものであり、各証明書に対して行われる必要があるため、証明書のフィルタリング(すなわち、例えばゲートウェイ装置によりどの証明書がどの装置に対応すべきかを決定すること)が非常に困難／高コストになる。
【００６９】
そのようなフィルタリング装置を支援するため、以下のことが提案される。単純なホワイトリスト、完全サブツリー方法又は変更ブラックリストの場合のように、グループIDでの順序付けを定めることが可能な場合には、証明書のメッセージ部分は、グループのグループに存在する“最低”及び“最高”のグループIDを含めればよい(“最低”と“最高”は順序関係に関して決定される)。このことにより、この証明書が関連のグループIDを含むか否かをフィルタが決定することが可能になる。これは、署名を調べる宛先装置自体により検証され得る。それにより、無関係の証明書の大半を迅速に拒否することが可能になる。
【００７０】
前述のことは図５のテーブルに示されている。参照数字402は、一式のkグループS1,...,Skの各グループがそれぞれ署名Sign[S1],...,Sign[Sk]を備えている機構を示している。各グループSiは、前述のように、一般的に40ビットのオーダーの長さの文字列で特定される。署名Sign[Si]の長さは、前述のように、一般的に1024ビットである。
【００７１】
参照数字404は、前述の第１の最適化の機構を示している。署名の数(ここではk)は、全体グループS1,...,Skを確認する単一の署名に交替されている。k以上の署名が存在する場合には、より多くの証明書(kの証明書の各グループ毎に１つ)が作られる必要がある。しかし、このことによっても配信される必要のある証明書の数の実質的な節約(ｋの元の証明書毎に１つ)を生じることが明らかである。
【００７２】
参照数字406は、メッセージS1S2...SkをS1Skに減少させることからなる前述の更なる最適化に関連する。この更なる最適化は、第１の機構の２の因数を(1024+80)/1024≒1.08のオーダーの因数に減少させる。すなわち、署名からのオーバーヘッドがほぼ完全に取り消される。
【００７３】
これらの最適化は、以下のように前述の多様な区分化機構に影響を及ぼす。
［単純なブラックリスト］
この場合には、証明書はr・nビットの長いブラックリストに追加され、合計でr・n+Cビットの伝送サイズになる。同じことが保存サイズにも当てはまる。署名サイズは無視し得る。１つのグループのみしか存在しないため、署名の適用に関する最適化は機能しない。
［単純なホワイトリスト］
(おおよそ)nビット毎の全サイズに(N-r)のグループが存在する。署名を加えると、伝送サイズで(N-r)・(C+n)ビットになる。第１の最適化機構では、
【００７４】
【数２】
2005530396.tif 000004
の無効でない装置毎に唯一の単一の署名が計算/伝送される必要がある(
【００７５】
【数３】
2005530396.tif 000005
のシリアル番号は
【００７６】
【数４】
2005530396.tif 000006
を取るため)。更なる最適化を適用するために、(無効でない)装置が例えば装置IDにより順序付けられ、そのようなグループの
【００７７】
【数５】
2005530396.tif 000007
のシリアル番号の最初と最後のみがメッセージ部分自体に入れられる。これにより、
【００７８】
【数６】
2005530396.tif 000008
の伝送サイズになる(ここで、Nは与えられた装置の総数である)。保存については、１つのみの証明書が取り出されて格納される必要がある(Cビット)。
［完全サブツリー方法］
それぞれnビット数(ツリーノード)により記述されたr・(n-log2r)のグループが存在する。第１の最適化に続いて、その
【００７９】
【数７】
2005530396.tif 000009
がCビットに適合され、これらの全てに単一の署名が与えられ得る。また、ツリーノードを順序付け、メッセージ自体に２つ(最低と最高)のみのツリーノードを残すことにより、更なる最適化が実行され得る。合計伝送サイズは、
【００８０】
【数８】
2005530396.tif 000010
である。保存については、単一の証明書のみが格納される必要がある(Cビット)。
［サブセット差分方法］
それぞれ(n+2・log2n)ビット数(2のツリーノード)により記述された(統計的に)1.25rのグループが存在する。第１の最適化に続いて、その
【００８１】
【数９】
2005530396.tif 000011
がCビットに適合され、これらの全てに単一の署名が与えられ得る。また、ツリーノードを順序付け、メッセージ自体に２つのみのツリーノードを残すことにより、更なる最適化が実行され得る。合計伝送サイズは、
【００８２】
【数１０】
2005530396.tif 000012
である。保存については、単一の証明書の署名部分のみが格納される必要があり、メッセージ自体は必要ではない(Cビット)。
［変更ブラックリスト方法］
それぞれrの数のnビットにより記述された(r+1)のグループが存在する。第１の最適化に続いて、
【００８３】
【数１１】
2005530396.tif 000013
の数はCビットに適合され、これらの全てに単一の署名が与えられ得る。更なる最適化も実行され得る。例えば、署名が{f1,f2...fk}により記述されるグループのグループ(すなわちグループS(f1,f2)S(f2,f3)...S(fk-2,fk-1)S(fk-1,fk))を保護する。そのようなグループのグループは、f1とfkをメッセージ部に入れることにより記述され得る。伝送サイズは
【００８４】
【数１２】
2005530396.tif 000014
になる。保存については、単一の署名の署名部分のみが格納される必要があり、メッセージ自体は必要ではない(Cビット)。
【００８５】
留意すべき点は、無効の装置のランダムな配信では、変更ブラックリスト方法がその他の方法より圧倒的に優れている。実際に、変更ブラックリスト方法は、ブラックリストにより提供される伝送サイズの下限と、ホワイトリストにより提供される保存サイズの下限をほとんど達成する。装置が階層的に構成されている場合(例えば典型的には特定のモデルの全てが無効にされる必要がある場合)には、その他の方法が適切になることがある。
【００８６】
従って、本発明は、証明書のメッセージ部分のほとんどを伝送せずに、署名部分からの受信時にそれを再構成することにより、署名によるオーバーヘッドを減少させるいくつかの方法を提供する。暗号化の観点からは、メッセージを備えた効率的にパックされた署名はほとんど冗長性を有しておらず、かなりの冗長性を有さない署名は安全でないと考えられるため、これはセキュリティのリスクを導くことがある。すなわち、証明機関の秘密鍵なしに生成することが容易になりすぎる。ハッカーはランダムなCビットの数を生成し、それを証明書として提示するに過ぎない。ほとんど全てのメッセージが有効であると考えられる場合には、全ての署名が有効であると考えられる。以下では、ハッカーが無効な署名を構成することが事実上不可能になるように、グループのグループの記述に十分な冗長性が存在している理由について説明する。
【００８７】
証明書の署名の検証は、証明機関の公開鍵に加えて、その内部フォーマットの事前知識を必要とする。共通に使用される技術は、全体メッセージに対するハッシュ値を計算し、それを署名によりカバーされるデータに含める(すなわち証明機関の秘密鍵を使用して暗号化される)ことである。この技術は、メッセージが十分に短い場合を除いて、少なくともハッシュ値のサイズだけメッセージのサイズを拡大するという欠点を有する。留意すべき点は、署名によりカバーされるこのデータは元のメッセージの部分を有してもよい点であり、その部分は別の方法では伝送されない。この場合は、メッセージ回復を備えたデジタル署名と呼ばれる。代替として、全体メッセージが署名と別に伝送される。この場合は、付加を備えたデジタル署名と呼ばれる。
【００８８】
ここに記載された方法のいくつかについて、証明書のサイズに関して効率的な代替の技術が使用され得る。前述の通り、装置の認証を保証するために２つの証明書が使用される。第１のものはいわゆる装置証明書であり、その装置証明書は装置IDとその公開鍵を有する。これは製造時に装置に組み込まれる。第２のものはいわゆる認証証明書であり、その認証証明書は認証されたいくつかの装置IDのリストを有する。対応する認証証明書に記載されたID付きの装置証明書を提示可能な装置のみが、システムにより認証される。２つの証明書の間の関係は、署名検証処理で使用される要素のうちの１つである。その他の要素は、認証証明書の認証された装置IDの符号化フォーマットの知識である。留意すべき点は、検証のみが認証証明書の署名で検討される。装置証明書の署名の検証は、標準化技術(例えばハッシュ関数を使用するもの)に従って実行され得る。
【００８９】
以下において、認証された装置IDのリストは、一式のグループに区分化され、そのグループがnビットの数により特徴付けられることを仮定する。また、署名(すなわち認証証明書)のサイズがCビットであることも仮定する。表され得るグループの総数は、N=2nである。最後に、符号化の複雑性を(わずかに)減少させるために、装置0とN-1が初めから無効になっていると仮定する。
【００９０】
証明書毎に複数の
【００９１】
【数１３】
2005530396.tif 000015
のグループIDがパックされており、mが証明書の連続番号及び他の関連情報を符号化するビット数を表す。有効な証明書の境界条件は、全てのグループIDが一意であり、昇順にソートされていること(例えばID0＜ID1＜....＜IDk-1)である。ここで、kのグループIDより小さい証明書が含まれている場合には、開放箇所はこの境界条件に一致するランダムなデータで埋められる。有効なエントリの数を示すために、mで表される予備ビットの部分が使用される。ランダムな署名の生成は、kのグループIDのランダムな連続に署名することに対応する。境界条件が満たされる(すなわち順序付けられる)確率Pは、以下のようになる。
【００９２】
【数１４】
2005530396.tif 000016
Cとnの現実的な値については、例えばn=40とC=1024であり、この確率Plist≒1/283である。この数の意味は、有効な認証証明書を作るために、アタッカーが282と281+mの間で公開鍵の演算を実行しなければならないことである。この数は、アタッカーがうまく仮の証明書を生成するにはかなり大きい。
【００９３】
当然のことながら、前述の実施例は本発明を限定するものではなく、説明するものであり、当業者は特許請求の範囲から逸脱することなく、多数の代替の実施例を設計することができる。
【００９４】
特許請求の範囲において、括弧の間にある如何なる参照数字も特許請求の範囲を限定するものとして解釈されるべきでない。“有する”という用語は、特許請求の範囲に記載されたもの以外の要素又はステップの存在を除外するものではない。要素に先行する不定冠詞は、その要素の複数の存在を除外するものではない。本発明はいくつかの別個の要素を有するハードウェアを用いて、及び適切にプログラムされたコンピュータを用いて実装され得る。
【００９５】
いくつかの手段を列挙する装置クレームにおいて、これらの手段のうちのいくつかは同一のアイテムのハードウェアに具体化され得る。特定の手段が相互に異なる従属項に記載されているという事実は、これらの手段の組合せが有利に使用できないということを示すものではない。
【図面の簡単な説明】
【００９６】
【図１】ネットワークを介して相互接続された装置101-105を有するシステムを概略的に示したものである。
【図２】完全サブツリー方法(Complete  Subtree  Method)のバイナリツリーの構成を示した図である。
【図３】サブセット差分方法(Subset  Difference  Method)のバイナリツリーの構成を示した図である。
【図４】変更ブラックリスト方法(Modified  Black-Listing  Method)を示した図である。
【図５】証明書を生成する最適化機構を示したテーブルである。
【図１】
2005530396.tif 000017
【図２】
2005530396.tif 000018
【図３】
2005530396.tif 000019
【図４】
2005530396.tif 000020
【図５】
2005530396.tif 000021
【国際調査報告】
2005530396.tif 000022
2005530396.tif 000023
2005530396.tif 000024