(57)【要約】  本発明は、全体の鍵管理メッセージの減少を可能にするステートレス技術とステートフル技術との強力で独創的な組み合わせを提案する。暗号鍵の集合がステートレスな部分集合カバー・スキームに基づき作成され、各ユーザは、部分集合カバー・スキームのリーフに関連付けられる。本発明の基本的着想は、次に、ステート鍵と、該ステート鍵を持つユーザの部分集合と該ステート鍵を持たないユーザの部分集合とを表す対応するステートを確立し、確立したステートを表す情報に基づき部分集合カバーを決定することである。最後に、グループ鍵管理メッセージは、少なくとも一部の計算された部分集合カバーに基づき決定することができる。導入されたステートは、効率的な部分集合カバーの計算のために公開され、鍵管理メッセージサイズを縮小する。
2008521278.tif 000002
【特許請求の範囲】
【請求項１】
サービスアクセス鍵を含むグループ鍵管理メッセージが選択されたサービスへのアクセス用にユーザのグループに転送される、サービスへの選択的アクセスのためのシステムにおける改善された鍵配信の方法であって、
各ユーザが部分集合カバー・スキームのリーフに関連付けられ、ステートレスの前記部分集合カバー・スキームに基づいて暗号鍵の集合を生成する工程と、
ステート鍵と、該ステート鍵を有するユーザの部分集合と該ステート鍵を有さないユーザの部分集合とを表す対応するステートとを確立する工程と、
前記確立されたステートを表す情報に基づいて、部分集合カバーを決定する工程と、
少なくとも一部を前記決定された部分集合カバーに基づいて、前記グループ鍵管理メッセージを決定する工程と、
を有することを特徴とする方法。
【請求項２】
前記グループ鍵管理メッセージを決定する工程は、前記ステート鍵を有するユーザのサブグループにより抽出可能な第１メッセージ部を決定する工程を有することを特徴とする請求項１に記載の方法。
【請求項３】
前記ステート鍵を有する前記ユーザのサブグループは、前記ステート鍵を有しアクティブに留まるつもりのユーザを含むことを特徴とする請求項２に記載の方法。
【請求項４】
少なくとも一部を前記ステート鍵に基づき、情報保護鍵を保護する工程と、
前記グループ鍵管理メッセージに前記保護された情報保護鍵を統合する工程と、
を更に有することを特徴とする請求項２に記載の方法。
【請求項５】
前記情報保護鍵を保護する工程では、前記ステート鍵および付加鍵に基づき、
前記付加鍵は、アクティブに留まるつもりのユーザの部分集合カバーの暗号鍵に基づき保護され、前記グループ鍵管理メッセージの前記第１メッセージ部に保護された形で統合されることを特徴とする請求項４に記載の方法。
【請求項６】
前記グループ鍵管理メッセージＭは、次式、
【数１】
2008521278.tif 000016
ここで、Ｔはステート識別子、Ｋstateは前記現ステート鍵、Ｓrs，…，Ｓtuは前記ステート鍵を有するそれらのユーザの間でアクティブに留まるつもりのユーザをカバーするユーザ集合、Ｅは暗号化関数、ＨSrs，…，ＨStuは前記ユーザ集合に対応する前記ステートレスな部分集合カバー・スキームの暗号鍵、ＫPは前記付加鍵、ＫEは前記付加鍵と前記ステート鍵との関数Ｆとして計算されるエンベロープ鍵、およびＫMは前記情報保護鍵である、
により決定されることを特徴とする請求項５に記載の方法。
【請求項７】
前記情報保護鍵および新ステート鍵は、少なくとも一部を現ステート鍵に基づき保護され、前記保護された新ステート鍵も前記グループ鍵管理メッセージに統合されることを特徴とする請求項４に記載の方法。
【請求項８】
前記グループ鍵管理メッセージを決定する工程は、前記ステート鍵を有さないユーザのサブグループにより抽出可能な第２メッセージ部を決定する工程を更に有することを特徴とする請求項２に記載の方法。
【請求項９】
前記ステート鍵を有さない前記ユーザサブグループは、アクティブ・ユーザとして参加するユーザを含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記ステート鍵およびメディア保護鍵は、アクティブ・ユーザとして参加するユーザの部分集合カバーの暗号鍵に基づき保護され、保護された形で前記グループ鍵管理メッセージの前記第２メッセージ部に統合されることを特徴とする請求項８に記載の方法。
【請求項１１】
前記部分集合カバーを決定する工程は、
前記ステート情報に基づきユーザに印を付ける工程と、
前記ユーザの印に基づき前記部分集合カバーを計算する工程と、
を有することを特徴とする請求項１に記載の方法。
【請求項１２】
前記ステート情報に基づきユーザに印を付ける工程は、前記ステート鍵を有さないユーザにアクティブ・ユーザの印を付ける工程を有し、
前記計算工程は、一般の部分集合カバーの計算手順の使用を含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記ステート情報に基づきユーザに印を付ける工程は、前記ステート鍵を有するが取消されるつもりのユーザと、前記ステート鍵を有しアクティブに留まるつもりのユーザと、前記ステート鍵を有さないユーザと、の３種類のユーザの分類に基づき実施されることを特徴とする請求項１１に記載の方法。
【請求項１４】
前記ステート情報に基づきユーザに印を付ける工程は、
前記ステート鍵を有さないユーザにまず未定義ユーザと印を付ける工程と、
前記ステート鍵を有する各ユーザを、メンバと呼ぶアクティブのまま留まるつもりのユーザ、およびメンバ外と呼ぶ取消されるつもりのユーザの１つとして印を付ける工程と、
各未定義のユーザを、前記ステート鍵を有するユーザの以前の印に依存して、メンバおよびメンバ外の１つとして印を付け直す工程と、
を有することを特徴とする請求項１３に記載の方法。
【請求項１５】
前記ステートに基づきユーザに印を付ける工程、および前記ユーザの印に基づき前記部分集合カバーを計算する工程は、統合された方法で同時に実施されることを特徴とする請求項１１に記載の方法。
【請求項１６】
前記統合された印付け工程と計算工程とは、前記ステート鍵を有するが取消されるつもりのユーザと、前記ステート鍵を有しアクティブのまま留まるつもりのユーザと、前記ステート鍵を有さないユーザと、の３種類のユーザの分類に基づき実施されることを特徴とする請求項１５に記載の方法。
【請求項１７】
前記分類に依存してユーザに色が割り当てられ、前記統合された印付け工程と計算工程とは、着色アルゴリズムに従って実施されることを特徴とする請求項１６に記載の方法。
【請求項１８】
前記グループ鍵管理メッセージは、複数のサービスにアクセスするための複数の鍵を含み、
前記確立する工程は、複数のサービスのおのおのに対して、サービスステート鍵と、該サービスステート鍵を有するユーザの部分集合および前記サービスステート鍵を有さないユーザの部分集合を表す対応するステートを確立する工程を更に有し、
前記部分集合カバーを決定する工程は、複数のサービスのおのおのに対して、前記確立されたサービスステートを表す情報に基づき、サービスの部分集合カバーを決定する工程を更に有し、
前記前記グループ鍵管理メッセージを決定する工程は、各サービスに対して、少なくとも一部を前記確立したサービスの部分集合カバーを表す情報に基づき、前記管理メッセージの構成要素を決定する工程を有し、
更なる工程は、前記グループ鍵管理メッセージを形成するために、前記構成要素を組み合わせることを特徴とする請求項１乃至１６のいずれか１項に記載の方法。
【請求項１９】
グループ鍵管理メッセージがユーザグループに転送され、サービスへの選択的アクセスのための鍵配信を改善したシステムであって、
各ユーザがステートレスな部分集合カバー・スキームのリーフに関連付けられる前記ステートレスな部分集合カバー・スキームに基づき、暗号鍵の集合を作成する手段と、
少なくとも１つのステート鍵と、該少なくとも１つのステート鍵を有するユーザの部分集合および該少なくとも１つのステート鍵を有さないユーザの部分集合を表す対応する少なくとも１つのステートとを確立する手段と、
前記確立された少なくとも１つのステートを表す情報に基づき、少なくとも１つの部分集合カバーを決定する手段と、
少なくとも一部を前記決定された少なくとも１つの部分集合カバーに基づいて、前記グループ鍵管理メッセージの少なくとも一部を決定する手段と、
を有することを特徴とするシステム
【請求項２０】
前記グループ鍵管理メッセージを決定する手段は、前記少なくとも１つのステート鍵を有するユーザのサブグループにより抽出可能な第１メッセージ部を決定する手段を有することを特徴とする請求項１９に記載のシステム。
【請求項２１】
前記少なくとも１つのステート鍵を有する前記ユーザのサブグループは、前記少なくとも１つのステート鍵を有しアクティブに留まるつもりのユーザを含むことを特徴とする請求項２０に記載のシステム。
【請求項２２】
少なくとも一部を前記少なくとも１つのステート鍵に基づいて、少なくとも１つのサービス保護鍵を保護する手段と、
前記グループ鍵管理メッセージに前記保護された少なくとも１つのサービス保護鍵を統合する手段と、
を更に有することを特徴とする請求項２０に記載のシステム。
【請求項２３】
前記少なくとも１つのサービス保護鍵を保護する手段は、前記少なくとも１つのステート鍵および少なくとも１つの付加鍵に基づき、前記少なくとも１つのサービス保護鍵を保護するため使用可能であり、
前記少なくとも１つの付加鍵は、アクティブに留まるつもりのユーザの部分集合カバーの暗号鍵に基づき保護され、前記グループ鍵管理メッセージの前記第１メッセージ部に保護された形で統合されることを特徴とする請求項２２に記載のシステム。
【請求項２４】
前記少なくとも１つのステート鍵は、主ステート鍵Ｋstateを含み、
前記グループ鍵管理メッセージを決定する手段は、次式、
【数２】
2008521278.tif 000017
ここで、Ｔはステート識別子、Ｓrs，…，Ｓtuは前記少なくとも１つのステート鍵を有するそれらのユーザの間でアクティブに留まるつもりのユーザをカバーするユーザ集合、ＨSrs，…，ＨStuは前記ユーザ集合に対応するステートレスな部分集合カバー・スキームの暗号鍵、ＫPは前記少なくとも１つの付加鍵、ＫEは前記少なくとも１つの付加鍵および前記主ステート鍵の関数Ｆとして計算される対応するエンベロープ鍵、ＫMはサービス保護鍵である、
で求められる少なくとも１つのメッセージ部を決定するために使用されることを特徴とする請求項２３に記載のシステム。
【請求項２５】
前記少なくとも１つのサービス保護鍵および新ステート鍵は、少なくとも一部を前記主ステート鍵に基づいて保護され、前記保護された新ステート鍵も前記グループ鍵管理メッセージに統合されることを特徴とする請求項２２に記載のシステム。
【請求項２６】
前記グループ鍵管理メッセージを決定する手段は、前記少なくとも１つのステート鍵も有さないユーザのサブグループにより抽出可能な第２のメッセージ部を決定する手段を更に有することを特徴とする請求項２０に記載のシステム。
【請求項２７】
前記少なくとも１つのステート鍵も有さないユーザのサブグループは、アクティブ・ユーザとして参加するユーザを含むことを特徴とする請求項２６に記載のシステム。
【請求項２８】
アクティブ・ユーザとして参加するユーザの部分集合カバーの暗号鍵に基づき前記少なくとも１つのステート鍵および１つのサービス保護鍵を保護する手段と、
前記グループ鍵管理メッセージの前記第２の部分に保護された形で前記少なくとも１つのステート鍵および１つのサービス保護鍵を統合する手段と、
を更に有することを特徴とする請求項２７に記載のシステム。
【請求項２９】
前記部分集合カバーを決定する手段は、
前記ステート情報に基づきユーザに印を付ける手段と、
前記ユーザの印に基づき前記部分集合カバーを計算する手段と、
を有することを特徴とする請求項１９に記載のシステム。
【請求項３０】
前記ステート情報に基づきユーザに印を付ける手段は、少なくとも１つのステート鍵も有さないユーザにアクティブ・ユーザの印を付ける手段を有し、
前記計算手段は、一般の部分集合カバーの計算手順に従って演算することを特徴とする請求項２９に記載のシステム。
【請求項３１】
前記ステート情報に基づきユーザに印を付ける手段は、前記少なくとも１つのステート鍵を有するが取消されるつもりのユーザと、前記少なくとも１つのステート鍵を有しアクティブに留まるつもりのユーザと、前記少なくとも１つのステート鍵も有さないユーザと、の３種類のユーザの分類に基づきユーザに印を付けるよう動作することを特徴とする請求項２９に記載のシステム。
【請求項３２】
前記ステート情報に基づきユーザに印を付ける手段は、
前記少なくとも１つのステート鍵も有さないユーザにまず未定義ユーザの印を付ける手段と、
前記少なくとも１つのステート鍵を有する各ユーザを、メンバと呼ぶアクティブに留まるつもりのユーザと、メンバ外と呼ぶ取消されるつもりのユーザの１つとして印を付ける手段と、
各未定義のユーザを、前記少なくとも１つのステート鍵を有するユーザの以前の印に依存して、メンバおよびメンバ外の１つとして印を付け直す手段と、
を有することを特徴とする請求項３１に記載のシステム。
【請求項３３】
前記ステート情報に基づきユーザに印を付ける手段と、前記ユーザの印に基づき前記部分集合カバーを計算する手段とは、統合されたやり方で同時に演算するように構成されることを特徴とする請求項２９に記載のシステム。
【請求項３４】
前記印付けと計算の統合演算は、前記少なくとも１つのステート鍵を有するが取消されるつもりのユーザと、前記少なくとも１つのステート鍵を有しアクティブに留まるつもりのユーザと、前記少なくとも１つのステート鍵も有さないユーザと、の３種類のユーザの分類に基づくことを特徴とする請求項３３に記載のシステム。
【請求項３５】
前記分類に依存してユーザに色を割り当てる手段を更に備え、前記印付けと計算の統合演算は着色アルゴリズムに従って実施されることを特徴とする請求項３４に記載のシステム。
【請求項３６】
前記システムが鍵サーバに実装されることを特徴とする請求項１９に記載のシステム。
【請求項３７】
特定されたユーザに、暗号鍵の集合の部分集合、ステート識別子およびステート鍵を送信する手段を更に有することを特徴とする請求項１９に記載のシステム。
【請求項３８】
前記部分集合、前記ステート識別子および前記ステート鍵を受信して格納する手段を更に有することを特徴とする請求項３７に記載のシステム。
【請求項３９】
前記受信して格納する手段はユーザ端末装置に実装されることを特徴とする請求項３８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、情報への選択的アクセスのためのシステムの鍵管理に関し、より具体的には、例えば、安全が保証されたブロードキャストを復号するためのメディア鍵または同等物を導出する鍵メッセージの配信と、そのような鍵メッセージの最適化とに関する。
【背景技術】
【０００２】
鍵管理は、ブロードキャスト保護システムまたはマルチキャスト保護システムなどの、情報に選択的にアクセスするあらゆるシステムにおいて決定的に重要である。図１に概略的に図示されるように、ブロードキャストおよびマルチキャストにより、無線応用技術および標準的なデータ通信の両方において、大きな受信者グループに対して保護された情報を効率的に配信することが可能になる。以下では、ブロードキャストとの文言を、ブロードキャストとマルチキャストとの両方を参照するために使用する。最近の成果は、無線ネットワークのブロードキャストに集中しており、主要なテーマは、無線リンクをできるだけ効率的に使用することである。例えば、メディアアクセスに要する時間を減少することである。
【０００３】
関心を集めるもう１つの主要テーマは、安全が保証された(secure)ブロードキャストを提供することである。したがって、保護する情報の暗号化は、商用のブロードキャスト・サービスを可能にする重要な手段である。商用のブロードキャストには、いくつかの関係者、例えば保護されたブロードキャスト情報を受信するユーザ、ネットワークプロバイダおよびコンテンツプロバイダが係わっている。ブロードキャストを商業上の要件を満たすユーザだけに宛てて送信するために、コンテンツプロバイダは、鍵配信プロセスでこれらのユーザに有効な暗号鍵を提供する。活動的な視聴者グループは動的であり、時間とともに変わるので、鍵の更新は重要なテーマにふさわしい。
【０００４】
ユーザの視点からは、鍵の更新が迅速に行われ、じれったい待ち時間をなくすことが重要である。ネットワークプロバイダおよび／またはコンテンツプロバイダの視点からも、高価な無線資源を節約するために、鍵の更新はできるだけ速く且つ効率的に行われことが重要である。
【０００５】
ブロードキャスト保護システムは、通常、相当数の分類した工程に分けて処理をする。ユーザがサービスプロバイダと契約するサービス登録工程は、たいてい必要である。このサービス登録工程では、ユーザは本人用の唯一の秘密鍵を提供される。鍵配信工程では、メディア鍵（またはより一般的には情報保護鍵）が、ブロードキャスト保護情報の解読のために登録ユーザに配信される。サービスプロバイダは、メディア配信保護（ＭＤＰ: media delivery protection）工程で、保護される情報を暗号化する。例えば、新規ユーザが登録するかまたはユーザが退会するとき、あるいはメディア鍵が危険になったときには、鍵再配信工程が、保護情報鍵を更新するため必要になる。周期的な鍵再配信もまた、システムのセキュリティを向上するために使用されてよい。サービス登録は、たいてい、ユーザとコンテンツプロバイダとの間でのポイント・ツー・ポイントであり、通信には安全が保証された認証手段を使用してよい。鍵配信工程およびメディア配信保護工程は、一対多数のやり方で実行されるだろう。
【０００６】
鍵配信の主な問題は、ユーザが、多数のグループにも拡張できる方法で、新たにグループに参加またはやめるときにできるだけ早くＭＤＰ鍵を更新することである。各ユーザに対して個別に暗号化した更新されたＭＤＰ鍵を送信する素朴な手法は、量の拡大がうまく行かないし、それに計算コストと帯域幅の消費との両方を増やして、資源を消費してしまう。
【０００７】
拡張性を改善するため提案された、グループ鍵配信プロトコルと呼ばれる仕組みがある。そのプロトコルの例に、ＬＫＨ（Logical Key Hierarchy）、ＳＤ（Subset Difference）、ＬＳＤ（Layered Subset Difference）がある。これらは、階層型のグループ鍵配信プロトコルの例である。
【０００８】
階層型の各グループ鍵配信プロトコルに対しては、暗号鍵集合が付随する。抽象的な階層ツリーを、これらの鍵の配列および鍵間の関連を図示するために使用できる。図２は、ユーザの集合Ｕ１〜Ｕ８を最下段に持つ階層ツリーを図示する。階層の最上段は、特定の階層型プロトコルの出力鍵ＫMである。ユーザ全員からなるグループのサブグループが階層ツリーのサブツリーを決定し、そのサブツリーは、順に識別できるメッセージ要素の集合を備えるグループ鍵管理メッセージを決定する。最下段と最上段との間のツリーモデルのノードは、グループ鍵管理メッセージの要素を解読するために必要とされる暗号鍵と結びついている。各ユーザは、加入時に、これらの鍵、例えば特定のユーザＵｉと出力鍵ＫMとの間のパス上の全部の鍵、の部分集合を演繹する情報を受信する。階層型のグループ鍵配信プロトコルは、線形の初期鍵生成性能および改善された対数鍵再生性能をもたらす。これらの方法は、非線形性能のため最も拡張性があり効率的な方法である。
【０００９】
図２は、ＬＫＨ法を検討するのに都合よく使用できる。ＬＫＨ法は、拡張性のあるグループ鍵配信プロトコルであり、ツリー内の各ノード（ｉ）と鍵Ｋiを関連付ける手法に基づいている。ここで、（ｉ）は、１次元または数次元のインデックスである。ルート鍵ＫMは、ツリーの最上段に関連する鍵であり、ＭＤＰ鍵として使用される。ユーザグループ内の各ユーザは、例えば登録時に個別鍵を提供され、この鍵はツリーの最下段のリーフＫ(rst)に関連する。各ユーザは、そのリーフからルートまでのパスにあるすべての鍵も受取る。典型的なメッセージは、三重項｛ｉ，ｊ，［Ｋi］Kj｝から作られる。ここで、ｉ＞ｊは、ノードｉがノードｊの祖先であることを示す。ｊがルートまでのパス上にある場合、すなわちノードｊに関連する鍵Ｋjの使用でＫiを回復することができる場合、ユーザはメッセージ部を解読できる。
【００１０】
したがって、Ｋiの集合は、ルート鍵ＫMの階層型暗号化からなる。ユーザが参加または退会するためにＭＤＰ鍵を更新するとき、必要なメッセージ数は少ないし、メッセージのサイズも小さい。考えられる欠点は、システムがステートフル(state-full)すなわち状態に依存する(state-dependent)ことにある。すなわち、新しく生成されたグループ鍵を暗号化するために、アルゴリズムは以前のグループ鍵を使用する。したがって、ステートの従属関係がスキーム(scheme)のために必要とされる。あるステートに対するグループ鍵が紛失した場合、どのようにしても参加者が容易にセッションを再補足することができない。
【００１１】
もう１つの欠点は、一括した鍵再生すなわち鍵の一括更新のために提供されている方法は、特に、ユーザ状態の大規模で瞬間的な変更の時にはあまり効率的でない。
【００１２】
部分集合カバー・アルゴリズム(Subset Cover algorithms)は、グループ鍵配信プロトコルの一般的種類であり、グループユーザがユーザの部分集合に関連していて、その部分集合は特定の鍵に関連していることを特徴とする。図３に例示されるＳＤ(Subset Difference)プロトコルは、これらのプロトコルの一例である。図３を参照すると、ノードはインデックスｊで番号を付けられている。図３の例では、ノード１〜１５が示されている。部分集合Ｓi,jを集めると、全員そろったグループを網羅し、全ユーザの集合をはっきりと決定する。部分集合Ｓi,jは、ノードｉの下にあり且つノードｊの下にないリーフの集合を示す。図３では、集合Ｓ2,5とＳ3,12が図示されている。ＭＤＰ鍵を更新するとき、ユーザグループは、これらの部分集合で正確に覆われ、更新鍵は部分集合の鍵のおのおののもとで暗号化される。
【００１３】
ＳＤ(Subset Difference)スキームは、より一般的なＳＣ(Subset Cover)プロトコルと同じく、状態に依存しない(stateless)グループ鍵配信プロトコルである。ＳＤスキームは、可能なユーザ数と同数のリーフを有する二進法のツリーを作る。ある構造内のリーフの数は固定される。リーフの中にはアクティブ・ユーザに占有されているものもあり、取消されたユーザすなわちブロードキャストを去ったユーザのものがあり、そして、占有されていなくてブロードキャストに参加する新規ユーザのために空いているものがある。鍵サーバ（ＫＳ）はエンティティＳi,jの集合Ｓを作る。各部分集合Ｓi,jは、鍵Ｌi,jとは一意的に関連しており、部分集合Ｓi,jの各ユーザは鍵Ｌi,jを計算できるが、他のグループのユーザは鍵Ｌi,jを計算できない。鍵Ｌi,jを使用してＭＤＰ鍵を暗号化することにより、ＭＤＰ鍵は、特定の部分集合Ｓi,jに対して更新できる。これは、集合Ｓに属するあらゆる部分集合Ｓi,jに対して行われなければならないことに注意すべきである。鍵Ｌi,jは階層的方法で作成され、ノードｉに関連するランダムシードは、１方向機能を反復使用してノードｊ＞ｉに拡大される。
【００１４】
ＬＳＤ(Layered Subset Difference)スキームは、ＳＤスキームであるが、潜在的な各ユーザがオリジナルのスキームより少ない鍵しか格納する必要のない特別な層を持っている。
【００１５】
これらのシステムのすべてにおいて、全ユーザにブロードキャストされるグループ鍵管理メッセージは非常に大きい。
【００１６】
特許文献１は、ユーザグループの部分集合カバーに基づくステートレス階層型の方法を開示している。鍵管理メッセージのサイズは、大きなグループでは非常に大きくなる傾向がある。したがって、鍵管理メッセージのブロードキャストをできるだけ効率的にするために、様々な試みが行われている。非特許文献１は、ユーザが危険に合うであろう確率に依存してユーザを配列し、それにより鍵管理システムの効率向上を可能にする方法を開示している。
【００１７】
鍵管理メッセージのサイズが原因で、セルラー方式ネットワーク上でそのメッセージを頻繁にマルチキャストまたはブロードキャストすると、非常に資源を消費するだろう。関係者の誰が、メッセージを送信するために必要な高価な無線リンク資源の資金を提供するかの問題もある。特許文献２及び非特許文献２は、全員のグループのサブグループを管理する各エンティティのエンティティ分散システムを勧めている。各サブグループは、更に、個別のグループ鍵に関連している。
【特許文献１】国際特許申請ＷＯ−２００２６０１１６（ＬＯＴＳＰＩＥＣＨＩ  Ｊ  Ｂ、ＮＡＯＲ  Ｄ、ＮＡＯＲ  Ｓ）
【非特許文献１】ＬＫＨベースのマルチキャスト鍵配信スキームの確率的最適化  Ａ．Ｓｅｌｃｕｋ他著、２０００年１月インターネット草稿、ｈｔｔｐ：／／ｗｗｗ．ｓｅｃｕｒｅｍｕｌｔｉｃａｓｔ．ｏｒｇ／ｄｒａｆｔ−ｓｅｌｃｕｋ−ｐｒｏｂａｂｉｌｉｓｔｉｃ−ｌｋｈ−００．ｔｘｔ
【特許文献２】米国特許第５，７４８，７３６号
【非特許文献２】モバイルネットワークにおける安全が保証されたマルチキャスト・グループ通信に関する鍵管理、Ｔ．Ｋｏｓｔａｓ他著、ｈｔｔｐ：／／ｎｅｖｅｌｅｘ．ｃｏｍ／ｄｏｗｎｌｏａｄｓ／ｄｉｓｃｅｘ．ｐｄｆ
【発明の開示】
【発明が解決しようとする課題】
【００１８】
これらのシステムは、拡張性はあるけれども複雑で高価になる。引用された方法の別の問題は、別のエンティティへのセキュリティ機能の分散に関連しており、そのような他のエンティティがセキュリティ機能を安全に取り扱うと信頼されてなければならない。このことは、そのシステムをより危険にさらすことになる。その結果として、そのようなシステムは、信頼されないエンティティが行う鍵または他の秘密情報の最適化を取り扱わないことになる。
【００１９】
更に、1つを超えるメディアセッションに関する鍵が同時に配信されるときに生じる、実践上の問題もある。独立して選択される複数のチャネルを提供するサービスプロバイダがその一例である。上記システムは、希望するユーザが各チャネルをオン／オフできる複数のチャネルを管理するための容易な方法を提供しない。素朴な方法は、各チャネルに対して個別のシステムを使用することだろうが、それは非常に非効率だろう。
【００２０】
ＳＤなどのステートレス・スキームの短所は、各鍵の更新時に、鍵管理メッセージのサイズがシステムから取消されたユーザの合計数に依存することである。したがって、鍵の更新で１ユーザだけが取消される場合に、それでもメッセージのサイズは、すでに取消されているユーザの合計数に依存する。ステートフルなＬＫＨシステムでは、１ユーザの取消しは、すでに取消されたユーザの合計数には依存しないが、その代わり存在するユーザの対数に依存する。
【００２１】
したがって、ブロードキャスト・システムおよびマルチキャスト・システムのグループ鍵配信に関して、先行技術のシステムの欠点を克服する効率的で信頼できる方法が必要である。特に、メッセージサイズの最適化を提供する方法が必要である。
【００２２】
本発明は、先行技術の装置のこれらの欠点や他の欠点を克服する。
【００２３】
本発明の全体的目的は、ブロードキャスト保護システムなどの中にある保護された情報に選択的にアクセスするグループのユーザに、グループ鍵配信の効率的な方法を提供することにある。
【００２４】
ステートレスな部分集合カバー・スキーム(stateless subset cover scheme)に類似した、暗号鍵集合を備える鍵管理システムを作成し、全体の鍵管理メッセージの減少を可能にする改善を提供するのが１つの目的である。
【００２５】
情報に選択的にアクセスするシステム内の鍵配信を改善する装置を作成することが１つの目的である。
【００２６】
改良した鍵配信装置内に、暗号鍵の部分集合とステート鍵とを受信して格納するユーザ端末を作成することは、特別の目的である。
【００２７】
別の目的は、許容できるセキュリティレベルを維持すると同時に、グループ鍵管理メッセージのサイズを著しく減少することである。
【００２８】
ユーザの部分集合の作成を最適化し、それによってユーザの部分集合に宛てられる鍵管理メッセージのサイズを縮小することも１つの目的である。
【００２９】
おのおのがサービスに関連している複数のコンテンツ鍵を効率的に管理することは、更に特別の目的である。
【００３０】
更に別の目的は、安全が保証されたグループ鍵配信システムの中で必要とされる、暗号化計算に関する鍵配信サーバの計算オーバーヘッドを減少することである。
【課題を解決するための手段】
【００３１】
これらの目的および他の目的は、添付の特許請求の範囲に記載される本発明により達成される。
【００３２】
簡潔に言うと、全体の鍵管理メッセージの減少を可能にするステートレス技術とステートフル技術との強力で独創的な組み合わせを提案する。暗号鍵の集合がまずステートレスな部分集合カバー・スキームに基づき作成され、各ユーザは部分集合カバー・スキームのリーフに関連付けられる。本発明の基本的着想は、次に、ステート鍵と、該ステート鍵を持つユーザの部分集合と該ステート鍵を持たないユーザの部分集合とを表す対応ステートを確立し、確立したステートを表す情報に基づき部分集合カバーを決定することである。最後に、グループ鍵管理メッセージを、少なくとも一部は計算された部分集合カバーに基づいて決定することができる。導入されたステートは、効率的な部分集合カバーの計算のために公開され、鍵管理メッセージサイズを縮小する。
【００３３】
言い換えると、本発明は、ステートレス技術とステートフル技術とを組み合わせるため、ステートＴとステート鍵Ｋstateとを確立する工程を含む。本発明によれば、縮小された全体の鍵管理メッセージおよび複数サービス用の鍵を扱う可能性との両方を提供する動的システムが創出される。より正確には、本発明は、取消しが一般に鍵更新プロセスで取消されるユーザ数だけに依存するシステムを創出するために、２つの手法（ステートレスおよびステート依存）を組み合わせる。これを達成するために、ＳＤまたはＬＳＤなどの部分集合カバーに基づく新しいシステムが創出される。従来の部分集合カバー・システムに関連する鍵に加えて、ユーザは通常、初期にステート識別Ｔとステート鍵Ｋstatetoとを受取る。本発明によれば、すでに取消されているユーザと、取消し時の該ユーザのステートおよびステート鍵を登録する手段が含まれるのが好ましい。したがって、ユーザが取消されるまたは再びアクティブにされるとき、その特定のユーザにだけ依存する鍵管理メッセージを作成することが可能となる。ステート識別子とステート鍵とを備えるステートを導入することにより、現在係わっている、例えば取消されるユーザだけを鍵管理メッセージに含めることが可能である。本発明によれば、新アルゴリズムは、合計集合数を減少させる更新集合を計算するために使用されるのが好ましい。
【００３４】
先行技術のステート依存システム、例えばＬＫＨの短所が、システムの完全更新を基礎をなすステートレスなＳＤシステムを使用してステートと暗号鍵とを再定義することで常に実現できることにより、減少されることに注目されたい。
【発明の効果】
【００３５】
本発明による方法は、以下の長所を提供する。
【００３６】
−特定の更新で必要な鍵数の減少。
【００３７】
−更新を送信するために必要なデータパケット数の減少。
【００３８】
−更新時間の減少。
【００３９】
−通常のステートレスな部分集合カバー・スキームへ復帰する可能性。
【００４０】
−複数のサービス鍵の取扱いの提供。
【００４１】
シミュレーションの結果は、ある状況のもとでは、本独創的方法によりメッセージサイズの９０％減少が達成できることを示している。
【００４２】
本発明が提供する他の長所は、以下の本発明の実施形態の記述を読むときに理解されるだろう。
【発明を実施するための最良の形態】
【００４３】
本発明は、その更にある目的および長所とともに、添付の図面とともに以下の記述を参照することにより最もよく理解されるだろう。
【００４４】
好ましい実施形態を、これから基礎をなすＳＤ構造を基に記述する。しかし、当業者により理解されるように、鍵管理メッセージ配信用のどんなステートレスな部分集合カバー・システムであっても本発明で使用することができ、そのためどの２つのそのような実現もが詳細構造において異なっているかもしれない。
【００４５】
＜予備段階＞
図６は、シミュレーションから得たデータを示す。図６は、ユーザの最大数が２15だった通常のＳＤの使用を説明する。表１のシステムの変動(dynamic)は約１％に設定された。すなわち、シミュレーションのためにシステムを去る「通常(normal)」のユーザを除いて、現在のユーザの１％は、鍵再生成の間に無作為に置き換えられると想定している。図７は、同じ条件のもとで本発明の方法の使用を説明する。このシミュレーションでは、時間内の１０周期目ごとに完全なＳＤメッセージが送信され、それは平均値および最大値に影響を与えた。
【００４６】
図７は、本独創的方法によれば、平均のメッセージは、通常のＳＤ法で取得されたメッセージの１０％未満であることを示す。
【００４７】
本独創的方法が作られた方法から、本独創的方法は、ステートフル・システムとステートレス・システムとの両方の特徴を示す属性を有する。したがって、ステートが鍵更新を通して変更されないままである場合、システムはステートレス・システムに似ている。本明細書を通して、この属性はセミ・ステートレスと呼ぶ。他方、ユーザがステート鍵を紛失すると、ユーザは鍵の更新を受けることができず、システムはステートフル・システムの特徴を示す。さらに、この状態は、本発明によれば完全更新を実施することにより修復することができる。これは、システムのステートレス属性に依存する可能性である。本独創的システムは、基礎をなすＳＤ構造の発展と見なすことができるけれども、同様にまったく新しいシステムと描写することもできる。発明の独創性を特定する視点からは、前者の手法が既知の事項と新規な特徴との間の明確な境界を与えるので都合がよい。
【００４８】
本発明は、セキュリティ問題をすべては解決しないことに注意されたい。本仕組みは、ある条件のもとでは、メディア鍵（またはより一般的には情報保護鍵）を回収するために、ステート鍵を所有しない除外されたユーザが、ステート鍵を持つもう１人の除外されたユーザと「協同する(cooperate)」する可能性を与える。しかしながら、このことは、実施段階では許容されると見なされる計算されるリスクである。実際には、伝統的な方法に従うシステムの完全更新を使用すれば、この結果の影響は減少する。
【００４９】
図面を通して同じ参照記号は、対応する要素または同様の要素のために使用される。
【００５０】
ＳＤおよびＬＳＤなどのツリー構造に基づく部分集合カバー・アルゴリズムに関連して、以下の表記法を使用するつもりである。
【００５１】
【数３】
2008521278.tif 000003
【００５２】
ここで、Ｍは鍵管理メッセージである。Ｓxyは、特定のユーザの部分集合を定義し、そのユーザは、メディア鍵またはより一般的にはＫMを取得するために、対応するＥ（ＨSxy，ＫM）を解読するのに必要な鍵ＨSxyを演繹することができる。
【００５３】
本発明によれば、システムは、ステートと対応するステート鍵Ｋstateとを有する。ステート鍵は一意的にシステム・ステートを規定するけれども、システム・ステートを規定するには、ペア（Ｔ，Ｋstate）を使用するのが便利である。
【００５４】
どの部分集合カバー・スキームも、関連する対象が全部そろった集合を有する。本明細書では、その対象のことをリーフと呼ぶ。部分集合カバー・スキームにおける特定の部分集合は、リーフの全部そろった集合に対応する部分集合に関連する。
【００５５】
ユーザは、保護される情報にアクセスする許可を与えられる可能性がある人、システムまたは装置であると理解されるものとする。
【００５６】
各ユーザをリーフと関連付けることができる。ユーザとリーフの関連付けは登録プロセスで行われる、例えば人を情報サービスのユーザとして登録する。
【００５７】
アクティブ・ユーザは、保護される情報に現在アクセスするユーザであり、それ故、そのような暗号化された情報を復号するための前提条件がシステムによりサポートされているユーザである。
【００５８】
保護される情報にアクセスするのに有効な鍵情報をユーザに提供するプロセスを、以下ユーザ参加と呼ぶ。
【００５９】
ユーザの取消しは、取消されるユーザを除く全ユーザに新しい情報保護鍵を配信するプロセスであると理解するものとする。したがって、取消されたユーザは、ステートとステート鍵とを有しているが、それは保護された情報へのアクセスにはもはや有効ではない。
【００６０】
ステート変更を伴わない更新プロセスはソフト(soft)と呼び、一方、ステート変更を伴う更新プロセスはハード(hard)と呼ぶものとする。ソフト更新の可能性のせいで、本発明による方法は時には、本明細書内でセミ・ステートレスと呼ぶ。
【００６１】
本明細書を通して、以下の表記が使用される。
Ｐ：潜在的な全ユーザ、すなわちツリーのリーフに関連するユーザを示す。
ＵA：アクティブ・ユーザを示し、それはアクティブのまま留まるつもりのユーザ、および以前取消されたユーザでアクティブ・ユーザに参加するつもりのユーザ、および現ステート鍵を持つユーザを示す。
ＵJ：ステート鍵を持たないかまたはステート鍵がもう使われていなくて、アクティブに参加するユーザを示す。
ＵR：ステート鍵を持つが、すでに取消されているかまたは今回の更新で取消されるユーザを示す。
ＵO：取消されていて、現のステート鍵を持たないユーザを示す。
【００６２】
上記のユーザ集合の定義に関して、ここで説明するのは適切である。集合ＵAに関して、取消されたユーザは、取消し以降にステート変更が発生していない場合、すなわちハード更新が行われていない場合には、まだ現ステートであってよい。
【００６３】
集合ＵJは、以前取消されたユーザを含むが、取消し以降にステートが変更している場合であり、それによりこのユーザが持つステート鍵は、現ステート鍵と同じではない。さらに、この集合には、以前アクティブだったことがなく、それゆえ当然以前のステート鍵を一度も持ったことがないユーザを含む。
【００６４】
カバー（Ａ，Ｂ）は、Ａ内の全員がカバーされ、Ｂ内のユーザは条件付きでカバーされるようにおおう。Ｂ内のカバーされるだろうユーザを決定することは、更に説明されるように、関連する集合を作成するアルゴリズムの一部である。Ｐ＼（Ａ∪Ｂ）のユーザはカバーされない。ここで表記Ｘ＼Ｙは、集合Ｙを除く集合Ｘを示す。
【００６５】
本発明により達成することができる最適化の種類を説明するため、例をこれから検討する。図３を参照して、３名のユーザ１０、１１、１２が集合Ｓ2,5とＳ3,12２とを使用して取消されていると想定する。これからユーザ１３も取消されるものと更に想定する。従来の部分集合カバー・スキームでこれを安全に行うためには、アクティブ・ユーザをカバーし、そうして他のすべてのユーザを取消すために集合Ｓ2,5とＳ3,6との使用が必要とされるだろう。しかし、本発明によるシステムでは、今回取消されるユーザだけに依存して１集合だけが必要とされる。
【００６６】
本独創的方法を説明する図４の例では、ユーザ１３の取消しをするのに１集合（Ｓ1,6）だけ必要であるのに対して、通常のアルゴリズムは２集合を必要とした。通常のＳＤプロトコルでは、集合Ｓ1,6に宛てられたメッセージを、ノード５の下にある前に除外されたユーザが聞くことが可能である。しかし、本独創的プロトコルによれば、その除外されたユーザが聞くことを防げる。その理由は、ノード５の下にあるユーザは、現のステート鍵を持たないので、メッセージを解釈することができないからである。
【００６７】
＜詳細記述＞
以下の記述では、ＳＤ構造が例示的に想定されているが、当業者はどのステートレス・スキームも使用できると理解するだろう。
【００６８】
システムを扱う鍵サーバは、当初は通常の部分集合カバーに基づく鍵構造を作成する。基本的には、異なる鍵がツリーの異なるノードに関連する論理ツリーが作成される。各ユーザは、最下段のリーフと関連付けられる。例示のユーザは、ブロードキャストを聞いている人、システムまたは広くサービスのあらゆる消費者である。鍵サーバは、少なくとも、鍵構造、ツリーに関連する鍵、どのユーザにもまだ関連付けられていないリーフに加えてユーザに関連するすべてのリーフのリストＵを把握している。更に、システムは、リストＵR、ＵAおよびＵJを更新し続けなければならない。特定のステートに関して、全アクティブ・ユーザおよび鍵サーバは、ステート鍵を持つ必要がある。
【００６９】
新しいステートがシステムに作成されるときはいつでも、ステート鍵が更新される。アクティブのまま留まるつもりのアクティブ・ユーザは、新しいステート、ステート鍵およびメディア鍵を含む更新メッセージを受信する。アクティブ・ユーザのグループに参加していてステート鍵を持たないユーザは、本独創的システムの属性を思い起こさせるステートレス・システムに特有の形態の更新メッセージを受信する。ステートＴとステート鍵とは、アクティブ・ユーザのグループを表現する。普通のステートレス・ツリーから現ステート鍵を持たないリーフを除外することにより、特定のステートＴに相当するツリー構造を定義することは時には役に立つ。
【００７０】
図５Ａは、所与の瞬間にツリーは５枚のリーフだけで形成されているステートの例を示す。既知の階層的方法による対応する構造は、８枚のリーフを持つだろう。失われたリーフは、現ステートＴに関連しないリーフである。これらのリーフは、本明細書内では未定義とも呼ぶ。したがって、ステートＴの導入は、トポロジーを規定する。ステートＴの導入により、鍵管理メッセージのサイズを縮小することが可能になることが示されるだろう。
【００７１】
＜初期化＞
ＳＤパラメータおよび場合により他のパラメータも、設定段階で、例えば自動登録プロトコルまたはスマートカードを通じて、ユーザ装置に提供される。ステート鍵は、様々な方法でアクティブ・ユーザに配信することができる。都合のよいことに、ステート鍵は設定段階で配信される。別の方法では、ステート鍵の初期化は、図３によるシステムの完全更新で行われ、そこでは部分集合カバー・アルゴリズムはその通常モードで実行される。次いで、ステート鍵は、場合によってはメディア鍵とともに、すべてのアクティブ・ユーザに配信される。鍵管理の初期化メッセージは、次のように見えるだろう。
【００７２】
【数４】
2008521278.tif 000004
【００７３】
ここで、‖は連結を示す。Ｔ‖Ｋstate‖ＫMは数回暗号化されており、実際には付加情報を含むこともあるので、これらの鍵が１度だけ暗号化されるように、エンベロープ手法を使用するほうがより便利なことが時々ある。エンベロープを使用すると、メッセージは次のように見えるだろう。
【００７４】
【数５】
2008521278.tif 000005
【００７５】
ここで、ＫEは、Ｔ‖Ｋstate‖ＫMを暗号化するために使用されるエンベロープ鍵である。簡潔化のために、本明細書の残りでは、鍵管理メッセージを記述するとき、この後の方法のエンベロープ手法を使用するつもりである。
【００７６】
＜例示される一般的方法＞
本発明による例示の一般的方法を、これから図８を参照して記述する。一般に、システム更新は３つの異なる種類のユーザに係わり、そのおのおのの種類はユーザ集合に対応する。第１の集合ＵAは、アクティブのまま留まるつもりの現アクティブ・ユーザとステート鍵を持つ参加するユーザとを示す。第２の集合ＵJは、更新に参加するつもりの新規ユーザを備える。このユーザは、ステート鍵を所有しないかまたはステート鍵がもう使われていない。第３の集合ＵRは、ステート鍵を持つが、すでに取消されているかまたは今回の更新で取消される取消しユーザを備える。３つのユーザ集合は、対応する部分集合カバーを決定するためのアルゴリズムへの入力である。部分集合カバーを最適化する問題に対し、本明細書の後の方で開示される代替実施形態から明らかなように、いくつかの解決策がある。
【００７７】
図８で提供されるフローチャートの次の工程は、配信される新しいメディア鍵を保護する鍵管理メッセージの作成に係わる。一般に、本発明によれば、保護は現ステート鍵の使用を含む。
【００７８】
その後、フローチャートは２つに分岐する。１つのブランチは、更新プロセスでステート鍵が更新されない場合、すなわちソフト更新の場合に辿られる。次いで、前の工程で作成された鍵管理メッセージの修正はもう必要ない。もう１つのブランチは、ステートとステート鍵との更新に係わり、本明細書でハード更新と呼ばれるものである。この場合、新しいステート鍵も保護されなければならない。
【００７９】
ユーザの取消しおよび参加は、あるイベントに対する応答として、または周期的に例えば１時間毎に１回、実施することができる。更新プロセスを開始できる例示的イベントには、ユーザによるグループからの除外要求、またはグループへの参加要求、ユーザの購読料の支払い中止、あるいはユーザにより手動でまたはユーザ装置により自動的に生成された鍵紛失に関して出された報告を含む。更新プロセスは、処理されるユーザの一括訂正を含むことができる。
【００８０】
一般に、更新プロセスは、参加する新規ユーザおよび取消されるアクティブ・ユーザに同時に係わる。更に、処理されるユーザは、ステート鍵を所有していなくてよいことに気付く。
【００８１】
次いで、新しいメディア鍵および場合によっては新ステートおよびステート鍵で更新されるユーザを適正にアドレスする鍵管理メッセージの一般構造が、説明される。
【００８２】
並行して更新される２つの独立したツリー構造を想像することにより、この実施形態の理解が容易になる。この第１の構造は、ステート鍵を所有しない全部のユーザ、すなわち以前はアクティブでなかった新規ユーザと、もう使われないステート鍵を持つ参加する取消しユーザとを収容する。第２の構造は、ステート鍵を有する全ユーザを収容する。
【００８３】
＜参加ユーザ＞
最初に、ステート鍵を持たないユーザがアクティブ・ユーザになるために参加する事例を考慮する。参加するユーザだけをアドレスするために、参加するユーザがツリー内の唯一のアクティブ・ユーザであり、該アクティブ・ユーザ（ＵA）は未定義と見なされ、他のユーザは取消されていると見なすことによりこれが可能であることに気付く。次いで、集合ＳA＝｛Ｓab …Ｓcd｝は、ＵJのすべてがカバーされ、場合によってはＵAの一部もカバーされるように計算できる。対応する鍵ＨSabは演繹され、次いでＳAに宛てられたメッセージは次のように見えるだろう。
【００８４】
【数６】
2008521278.tif 000006
【００８５】
式２(Eq2)で、Ｅは前に採用したエンベロープ式暗号化を示す。
【００８６】
参加したユーザに、メディア鍵と新ステート鍵との両方を提供するのはたぶん都合がよい。その場合には、式２'(Eq2')が式２の代わりに使用してよい。
【００８７】
【数７】
2008521278.tif 000007
【００８８】
＜ステート鍵を持つユーザの更新＞
これから、現ステート鍵を所有する全ユーザを収容する第２の構造に取り掛かる。すでにステート鍵を所有するユーザの間では取消しは行われていない（すなわち、ＵRは空）と想定して、グループのアクティブ・ユーザは、現ステート鍵を使用してメッセージを暗号化することにより、セキュアにアドレスされることがわかる。したがって、新しいメディア鍵は、現ステート鍵を使用して送信することができる。すなわち、
【００８９】
【数８】
2008521278.tif 000008
【００９０】
新しいステート鍵はこのメッセージに含まれてもよく、次のようになる。
【００９１】
【数９】
2008521278.tif 000009
【００９２】
＜現ステートのユーザを取消し、且つアクティブに留まるユーザを更新＞
集合ＵRが空でない事例に取組むために、集合ＳT＝｛Ｓrs …Ｓtu｝は、現ステート鍵を有する全ユーザの間でアクティブに留まるつもりのユーザ、すなわちＵAを、ステート鍵Ｔでカバーして計算される。このカバーのために、取消されるユーザは未定義として取り扱われる。図５Ａを思い起こすと、集合ＳrsはステートＴでないユーザを含んでもよい。ステートＴで同時にカバーＳRの中にいるユーザだけに取組むために、新しい鍵ＫPが導入され、鍵ＨSrsで保護される。次いでエンベロープ鍵ＫEは、関数ＦにＫPとＫstateを入力として使用することにより取得される。その関数の例は、疑似ランダム関数、メッセージ認証コードおよび暗号化変換である。関数Ｆは、例えば設定段階でユーザ装置に提供することができる。その時、ＳT宛てのメッセージは、次のように見えるだろう。
【００９３】
【数１０】
2008521278.tif 000010
【００９４】
集合Ｓxy内で且つ現ステート鍵Ｋstateも持つユーザは、まず鍵ＫPを演繹することができる。関数Ｆとステート鍵Ｋstateとを使用して、次いでユーザはＫE＝Ｆ（ＫP，Ｋstate）を演繹でき、最後にメディア鍵ＫMを演繹することができる。さらに、ステートがＴからＴ’に同時に更新される場合、次の式が適用される。
【００９５】
【数１１】
2008521278.tif 000011
【００９６】
＜全部そろったメッセージ＞
上記のことは、ステート鍵を持たないで参加するユーザに対する更新メッセージの作成方法およびステート鍵を持つユーザの更新方法を示す。実際面では、これらは１つのメッセージを作成するために組み合わせることができる。式２(Eq2)と式３(Eq3)の両方に対応するユーザは、以下の１つのメッセージに含めてよい。
【００９７】
【数１２】
2008521278.tif 000012
【００９８】
代わりに、ステートが新しいステートに更新される場合は、次のようになる。
【００９９】
【数１３】
2008521278.tif 000013
【０１００】
要約すると、現ステート鍵を所有しない参加するユーザと現ステート鍵を所有する現アクティブ・ユーザとを備えるグループのステートとステート鍵とを更新するために、この式は使用されてよい。現ステート鍵を持たない参加ユーザのグループは、以前取消されたが古いステート鍵を持つユーザ、すなわちこれらのユーザの取消し以降に少なくとも１回のステート変更が行われているユーザを含んでもよいことに気付く。
【０１０１】
同じように、式２(Eq2)と式４(Eq4)を完全に一般化すると、以下の式をもたらす。
【０１０２】
【数１４】
2008521278.tif 000014
【０１０３】
【数１５】
2008521278.tif 000015
【０１０４】
ＵRが空でない（すなわち、ステート鍵を持つユーザの間に取消しするユーザがいる）とき、式６(Eq6)は式５(Eq5)の代わりに使用される。
【０１０５】
これらの式で示されるように、新ステートとステート鍵とは、メディア鍵ととともに配信できる。しかし、ある状況では、ステートを変更しないことが好都合である。例えば、少数のユーザだけが参加および去るだろうと予想される場合、ステートを変更しないことは、過剰なオーバーヘッドをたぶん加えないだろう。したがって、有利な点は、システムはこの期間中ある程度、セミ・ステートレス・モードで動作することである。
【０１０６】
図１１は、上記の事例の要約を提供するステート図である。ステート図の左ブランチでは、完全更新が初期化メッセージを使用して実施される。その結果、すべてのユーザはアクティブ・ユーザになり、現ステート鍵を持つ取消しユーザＵRはいない。最後のステートは、図１１で示されるように、集合ＵA ∪ ＵJで置き換えられたＵAと、空集合に設定されたＵJとを備える。
【０１０７】
図の右ブランチは部分更新に相当する。まず、カバーＣ(cover Ｃ)が，集合ＵJと場合によってはＵAのユーザとを備えて作成される。次いで、図は、現ステート鍵を持つユーザに両方とも関連する２本のブランチに分割される。右ブランチは、取消されるユーザがない事例に対応する。ステートが更新されているかどうか次第で、式３(Eq3)または式３'(Eq3')が、ＵA内のユーザのステート鍵の更新に使用される。フローは、ステート鍵を持たないユーザを考慮するために続く。
代わりに左ブランチに従う場合、すなわちＵR≠０の場合、カバー集合Ｃ1が集合ＵA＼Ｃ（この事例のＣは、カバーＣでカバーされるユーザの集合と見られる）と、場合によってはＰ＼ＵRのユーザを備えて形成される。その後、ステートが更新されているか否か次第で、集合Ｃ1とともに式４(Eq4)または式４'(Eq4')が適用される。フローは、ステート鍵を持たないユーザを考慮するために続く。
【０１０８】
図１１内の図の下側のマークで区画された部分は、参加するつもりのステート鍵を持たないユーザ、すなわち集合ＵJに関連する。ＵJ内の参加するユーザが新しいステート鍵を受取るだろうか否か次第で、式２(Eq2)または式２'(Eq2')が集合Ｃとともに使用される。式２'(Eq2')が使用される場合、最終ステートは、図の上の左ブランチの事例のように設定される。さもなければ、最終ステートは、ＵJを空集合に設定することを備える。
【０１０９】
代替の実施形態では、鍵サーバは、いくつかのステート、各ステートに対応する鍵構造、ならびにＵR集合、ＵA集合およびＵJ集合を維持する。
【０１１０】
ユーザが同期をはずれることもある。この問題を軽減するために、ユーザの要求により再同期化するメカニズムを提供できる。例として、最新のステートを特定の場所から要求できる。代わりに、再初期化メカニズムを定期的間隔で適用することもできる。また別の可能性は、ユーザが必要な情報を捜すことができる公開の場所において、全鍵管理メッセージを公表することである。
【０１１１】
こうして、ステートおよびステート鍵が導入され、式６(Eq6)が更新メッセージの例示的形態を開示する発明の第１の態様を記述したので、これから、本発明の第２の態様に取り掛かる。
【０１１２】
＜最適化された部分集合カバーの計算＞
第２の態様によれば、方法は、更新メッセージのサイズを縮小するように最適の方法で集合Ｓrs …Ｓtuを作成するために勧められる。ステート鍵が使用されるとき、ツリーの一部は大体未定義であることに気付くことは価値がある。最小の部分集合を作成するとき、これを利用できる。時には、この未定義の部分を「取消された(revoked)」ユーザと見なすのが都合が好いことがあり、時には「アクティブ・ユーザ」と見なすのがよいことがある（ツリー内で未定義部分がどのように分散しているかに依存する）。
【０１１３】
一般に、部分集合カバー・アルゴリズム内の部分集合を特定する方法では、ツリーがよくバランスが取れている、すなわちリーフはすべてツリー内のほぼ同じ深さに存在する、およびどのリーフが取消されているか、どれがユーザであるかは、あいまいなところがなく定義されている、と見なしている。このことは、例えば未定義のリーフはないことを意味する。前に述べたように、本発明によれば、ステート鍵の使用は、十分にバランスが取れていない２つの独立したツリーの作成を可能にする。部分集合を特定する一般アルゴリズムが使用される場合、うまく定義され最適化もされたツリーを作成する方法がなければならない。さもなければ、未定義のリーフを有するツリーの上に直接かぶせるカバーを作成できる新しい方法が発明されなければならない。その方法を、基礎をなすスキームとしてＳＤが使用されるときのツリーに対して開示する。
【０１１４】
以下では、ステート鍵を所有するユーザを表すツリーに基づき、これを達成する実施形態を開示する。しかし、この方法は、ステート鍵を所有しない、すなわち対応するノードが未定義のユーザを表すツリーの上でも同様にうまく機能する。実際、以下に記述する方法は、一定の種類、例えばアクティブ、取消されたまたは未定義のノードのカバーを生成するために使用することができる。
【０１１５】
一般に、以下に記述される方法は、２つの工程を備える。第１の工程では、ユーザは特定のアルゴリズムに従って印を付けられる。第２の工程は、部分集合の計算とユーザおよびノードの印付けとの組み合わせを備える。すなわち、ユーザの以前の印はこの工程で変更されてよい。
【０１１６】
第１の実施形態によれば、通常のツリーが第１の工程で作成され、ステート鍵を持たない全ユーザは、グループのアクティブ・ユーザとして印を付けられる。そうすることにより、次に一般のカバー法を使用して、第２の工程である部分集合を計算するのは易しいだろう。これを見るために、図５Ｂを考えてみよう。図５Ｂでは、リーフ８、９、１０、１３、１５はステート鍵を持ち、リーフ１１、１２、１４はステート鍵を持たない。第１の工程によれば、リーフ１１、１２、１４はアクティブと印を付けられている。図５Ｂでは、現ステートを持たないことを思い起こさせるため影付きで示されている。リーフ１３、１５（図５Ｂでは、×印が付いている）を取消すことを望む場合、一般アルゴリズムでは、ルートの左ブランチの全リーフをカバーするために集合Ｓ1,3を作成し、リーフ１２をカバーするためにＳ6,13を作成し、リーフ１４をカバーするためにＳ7,15を作成しただろう。式４(Eq4)または式４'(Eq4')の鍵更新メッセージが使用される。次いで、リーフ１１、１２、１４は上記で特定した集合によりカバーされるが、これらのリーフは現ステート鍵を持たないので、新しい鍵を回収することはまだできないだろう。
【０１１７】
この実施形態により作成される集合は最適ではない。最適の部分集合は、部分集合Ｓ2,11だけであったろう。それによりリーフ８、９、１０は更新され、リーフ１１は影響を受けず、リーフ１３、１５はカバー集合に含まれていなくて取消されただろう。
【０１１８】
第２の実施形態によれば、前述の第２の工程は，第１の実施形態の第１の工程により作成される部分集合Ｓ＝｛Ｓrs …Ｓtu｝の後処理を備える。したがって、第２の実施形態によれば、Ｓijの下にある全リーフが元のツリーで未定義である場合、集合Ｓij∈ＳはＳから除去される。したがって、上記の例では、集合Ｓ6,13とＳ7,15とは後処理で削除され、ほぼ最適のカバーになる（これは、部分集合の最適数を使用するが、未定義のユーザを不必要にカバーする）。カバーされる未定義のユーザ数を減らすことは、取消されたユーザが協力して鍵を不法に回収できるというリスクを減少する。
【０１１９】
第３の実施形態によれば、前述の第１の印を付ける工程は、以下のルールによりリーフに印を付ける工程を含む。
−ステート鍵を持たないリーフはすべて、未定義の印を付けられる。
−ステート鍵を持つリーフはすべて、同様にユーザかまたはユーザ外かの印を付けられる。
【０１２０】
図５Ｃでは、未定義のリーフは斜線の印を付けられ、ステート鍵を持つリーフはドットの印を付けられている。更に、図５Ｃでは、リーフ１３、１５はこれらのリーフがユーザ外であることを示すために×印が付けられている。
【０１２１】
前述の印付けと計算との組み合わせの第２の工程は、図５Ｃに図示されるツリーに適用される、次のアルゴリズムを備える。
−ツリーの各レベルに対して、リーフから出発してツリーを１レベル上がり、そのレベルの各ノードに、以下の工程を行う。
ａ．左と右の両方の子供が未定義と印を付けられている場合、そのノードに未定義と印を付ける。
ｂ．ｘで示される１人の子供が未定義と印を付けられているが、ｙで示される別の子供は印を付けられているユーザかまたは印を付けられていないユーザの場合、ノードにｙの印を付け、ｘの下のすべてのリーフにｙの印を付ける。
ｃ．未定義と印を付けられている子供がいない場合、現ノードにユーザと印を付ける。
【０１２２】
このアルゴリズムに従って、すべてのリーフは、ユーザまたはユーザ外と印を付けられるだろう。したがって、以前未定義のユーザは再び印を付けられ定義されるだろう。図５Ｃの例では、工程２によれば、リーフ８、９、１０はユーザの印を付けられ、リーフ１１、１２、１４は未定義と印を付けられ、リーフ１３、１５はユーザ外の印を付けられる。
【０１２３】
サブステップａにより影響されるノードはない。サブステップｂによれば、ノード５はユーザと印を付けられ、ノード６はユーザ外と印を付けられる。更に、サブステップｃによれば、ノード４はユーザの印を付けられている。次の工程では、サブステップｃだけが適用され、ノード１、２、３は、リーフに何らの影響もなくユーザの印を付けられているだろう。ユーザだけをカバーするカバーが今や作られている。図５Ｃの例によれば、集合Ｓ1,3が生じるだろう。見られるように、この事例では生じたカバーは、ほぼ最適である。使用される部分集合の数では、カバーは最適であるが、不必要に未定義のリーフ（１１）をカバーする。
【０１２４】
第４の実施形態によれば、第２の実施形態による後処理がまず実施され、その後、第３の実施形態によるアルゴリズムが実施される。
【０１２５】
第５の実施形態によれば、最適なカバーに導く部分集合カバーを作成するより効率的な方法を開示する。この方法は、ノードの状態に依存する異なる色を与えられる着色アルゴリズムに基づく。この実施形態によれば、前述の第１の工程はリーフに着色する工程を含む。リーフが今回の更新プロセスで取消される場合、すなわち集合ＵRに属する場合は、そのリーフは「赤」に着色される。すでに取消されていて現ステート鍵を持たない場合、すなわち集合ＵOに属する場合は、リーフは「黒」に着色される。最後に、今回の更新でグループのユーザに留まるつもりの場合、すなわち集合ＵAに属する場合は、リーフは「青」に着色される。リーフはこれらの色の１つだけを持つことができるというルールに従う。
【０１２６】
その後、印付けと計算との組み合わせの第２工程が実施される。印付けは、次のルールに従って進む。最下段の上にあるノードは着色される。子供の色は基本的に親の色を補うために「加え」られる。少なくとも１人の子供が赤である場合、親は赤だろう。少なくとも１人の子供が青の場合、親は青だろう。青と赤は、それぞれカバーされなければならないかまたはカバーされてはならないノードの下のリーフの存在を示す。どちらの子供も青色でない場合、親は、両方の子供の合計数の黒を持つか（ノード内の黒の量は、そのノードの下の何枚の未定義のリーフを取消すことができるか示す）、そうでなければ子供の黒の最大数を持つだろう。着色プロセスは、最下段から上の全レベルを通して進む（これは、ツリーの縦型横断で実施することもできる）。図１２は、着色ツリーの例を説明する。ここで、「ｋ、ｄ、ｅ」は、それぞれ「黒、赤、青」の色を示す。
【０１２７】
これから、第２工程に含まれる計算の説明に取り掛かる。アルゴリズムを理解し易くするために、まず定義をする。赤糸(thread)は赤色のノードから始まるパスと定義され、赤く着色されたその下のレベルのノードを含む。糸の一番上のノードは、赤く着色された最上段のノードであり、ただ１つの赤く着色された兄弟を持つ。図１２では、ノード２、４、８は糸を形成する、すなわちノード２が一番上のノードである。赤糸の一番上のノードは、青にも着色され、そのノードの下の青いリーフをカバーするために、部分集合が使用されなければならないことを示す。
【０１２８】
アルゴリズムは青の一番上のノードを持つ赤糸を捜し、そのような赤糸を見つけるとき、必要なカバー集合を作るためＦｉｎｄｓｅｔ（）関数を呼び出す。次いで、その糸の一番上のノードの親ノードは赤色だけに着色され（すなわち青および黒の通常の伝播はそこで終わる）、その後、残りのツリーの着色はいつものように進む。図９に疑似コードとして説明されているＦｉｎｄｓｅｔ（）アルゴリズムの原則は、赤糸の一番上から青ノードに従って、両方の子供が青に着色されている点に到達するまで下に向かう。そのようなノードが見つかるとき、たいてい赤糸の一番上である可能性があるが、これは部分集合の一番上のノードにちがいないと気付く（万一到達したノードが青だけで黒も赤も存在しない場合、特別の事例が必要とされる）。
【０１２９】
次いで、新しく見つけた一番上のノードから下へ赤に従って、青のないノードに到着するまで進む。その青のないノードは除外されたサブツリーのルートに違いない。赤が存在しない場合、その代わり除外された未定義ユーザ数を最大化しようとするだろう。そして、黒の最大数を下へ、また青が存在しないノードに到達するまで従う。この場合、このノードは除外されたサブツリーのルートであるだろう。
【０１３０】
図１２では、その種の２本の糸が記述されている。ノード２、３は、これらの糸のそれぞれの一番上のノードである。左の糸に従うと、二人の子供は青くないことに気付く、それでルートを下りノード４に行く。ノード４から赤糸に従って下がるとき、青に着色されていない最初のノードはノード８であり、それが除外されたサブツリーのルートであるだろう。その結果、集合Ｓ4,8がカバーに加えられる。同じやり方で右の糸に関しては、ルートはノード３になるだろう、そしてノード６が青のない最初の到達したノードであり、除外されたサブツリーのルートにするだろう。結果は、集合Ｓ3,6も最終的に生じるカバーに加えられる。
【０１３１】
アルゴリズムによれば、「赤」と「青」の色はブール値で表され、「黒」色は整数で表される。代わりに、「黒」色もブール値で表されるが、厳密に必要とされる以上の黒ノードをカバーすることもあるという意味では、これは最適な部分集合カバー与えないだろう。しかしそれでも、その修正では、カバーに対して集合のより多い数をまだ使用しないだろうから、両方法とも帯域幅の視点からは最適であることに、注意する価値はある。
【０１３２】
アルゴリズムが図１０に記述される。先に説明された原則に従って、リーフが「青」「赤」「黒」に着色しているツリーを仮定すると、図１０に説明されているカバー関数Ｃｏｖｅｒ（）は、ツリーに対する完全な部分集合カバーを作成する。関数Ｃｏｖｅｒ（）は、図９に説明されているサブ関数Ｆｉｎｄｓｅｔ（）を使用する。サブ関数Ｆｉｎｄｓｅｔ（）は、所与のノードに根ざすサブツリーをカバーするためできるだけ小さい集合を演繹する。すなわち、できるだけ少ない「黒」と「赤」のノードをカバーすることにより、ツリーをカバーする。関数は、部分集合Ｓｘ，ｙのインデックスを戻す。図１０では、「ルート」はツリーのルートノードを指定する。このノードは決して更新されない。前述のように、黒色は整数で表され、アルゴリズム内の和「＋」は、整数の通常の和である。残りのシンタクス要素は自明であり、当業者にはよく知られている。
【０１３３】
代替の実施形態では、黒色もブール値で表される。この場合、図１０のｎ.ｂｌａｃｋの計算は、ｎ.ｂｌａｃｋ＝ｌｅｆｔ（ｎ）.ｂｌａｃｋ｜ｒｉｇｈｔ（ｎ）.ｂｌａｃｋのように修正される。
【０１３４】
＜複数のサービス＞
前述の好ましい実施形態は、特定のサービスに関連する鍵の管理には都合が好い。しかし、ユーザが複数のサービスに加入することがよくある。本発明の既述の実施形態は、鍵および鍵管理メッセージを管理するために、そのようなサービスのおのおのに対して使用することができる。鍵識別子を鍵と対応するサービスを関連付けるために使用できる。明らかに、この直接的な手法は、多数の鍵管理メッセージをもたらすだろう。更に、異なるユーザ状態グループを持つ複数のサービスに対して、スキーム内のステート依存性の導入方法は明らかでない。
【０１３５】
したがって、本発明の別の実施形態によれば、提案されたシステムの拡張は、異なる加入ユーザを持ってよいサービスの複数の同時サービスの場合の、鍵配信管理に関して開示される。この種のサービスの例を、図１３に示す。相当数のサービス・パッケージをサービス・パッケージ１〜４で示す。各パッケージは、図のチャネルａ〜ｈで示される、１つまたはいくつかの配信チャネルで配信される。チャネルは、例えば典型的に周波数で識別されるブロードキャスト・チャネルに関連してよい。様々なサービス・パッケージに加入する７人の加入者が、右に示されている。図示されているユーザの２人は、どのサービス・パッケージにも加入していなくて、どの鍵更新プロセスにも参加しないだろうことを示すため×印で示されている。メディア配信装置は、各加入ユーザに対してサービス・パッケージを編集し、鍵サーバから取得した適切なメディア鍵を使用してパッケージを暗号化する。
【０１３６】
この実施形態によれば、前述で以下では主ステートとも呼ぶステートＴに加えて、各サービス・パッケージ（ｉ）は、ＴPiと定められるサービス特有のステートおよび対応するステート鍵ＫTPiに割り当てられる。各ステートＴPiは、前述のように対応するツリー構造を規定する。同じＳＤツリーが全部のサービス・パッケージに対して利用されてよいことに注意のこと。ユーザは、対応するツリー構造を使用して特定のサービスに加えられたり取消されたりする。ユーザは、主ステート鍵を使用して取消されてよい。これを行うと、次いでユーザは加入しているすべてのサービスから取消される結果をもたらすだろう。
【０１３７】
特定のサービス用のメディア鍵が配信され、主ステート鍵Ｔのもとと適切なサービス・ステート鍵ＴPiのもととの両方で保護される。効率を改善するための代替実施形態では、メディア鍵は、関数ｆを適用して、マスタ鍵およびサービス・パッケージ・シードから演繹される。図１４を参照して、ハッシュ関数などの一方向関数ｆは、シードＳP1およびマスタ鍵ＫMKに適用され、第１のサービスに相当するサービス・メディア・マスタ鍵ＫPM1を生成する。他の利用できるサービスも同様である。これらのサービス・パッケージ・マスタ鍵から、更なる鍵ＫMx（ｘ＝ａ−ｈ）が、各チャネルに対して生成されてよい。これらのチャネル鍵の引き出しは、サービス・パッケージ・マスタ鍵の生成と同様に、すなわちＫPMxとシードに対して関数ｆを使用することにより、行うことができる。この方法で、鍵再生成中、ＫMK鍵の１つだけが送信される必要がある。その鍵再生成が行われる前に、シードと関数ｆが同意されていなければならないことに注意すべきである。これは、例えばサービスの初期登録中に行われる。
【０１３８】
＜代替の実施形態＞
本発明によれば、すでに取消されているユーザとその取消し時のステートとステート鍵とを登録する手段が含まれるのが好ましい。代替の実施形態では、システム・パラメータがこの履歴登録の深さ、すなわち登録で維持されるべきステートＴの最大数を決定するのが好ましい。
【０１３９】
上記の実施形態は単に例として挙げられており、本発明はそれに限られていないと理解されるべきである。本文書で開示および主張された基礎をなす原則を維持し更に行う修正、変更および改善は、本発明の範囲および趣旨の中にある。
【図面の簡単な説明】
【０１４０】
【図１】グループ鍵メッセージを配信するネットワークの例示的概観図である。
【図２】特定のユーザグループへのグループ鍵管理メッセージに適応させた先行技術の階層型システムの論理ツリーの典型的な図である。
【図３】先行技術の階層型システムの別の論理ツリー例の図である。
【図４】本独創的方法を図示する論理ツリー例の図である。
【図５Ａ】、
【図５Ｂ】、
【図５Ｃ】本独創的方法を図示する論理ツリー例を示す図である。
【図６】先行技術ＳＤ法に基づくシミュレーションから受取ったデータの表を示す図である。
【図７】本独創的方法に基づくシミュレーションから受取ったデータの表を示す図である。
【図８】本発明による実施形態を説明するフローチャートである。
【図９】本独創的方法を説明する例示的疑似コードを示す図である。
【図１０】本独創的方法を説明する補完的な例示的疑似コードを示す図である。
【図１１】本独創的方法を図示するステート図である。
【図１２】部分集合作成する本発明の好ましい実施形態の図である。
【図１３】複数サービスに関連する本発明による好ましい実施形態の図である。
【図１４】複数サービスの場合の本発明による鍵管理の図である。
【図１】
2008521278.tif 000018
【図２】
2008521278.tif 000019
【図３】
2008521278.tif 000020
【図４】
2008521278.tif 000021
【図５Ａ】
2008521278.tif 000022
【図５Ｂ】
2008521278.tif 000023
【図５Ｃ】
2008521278.tif 000024
【図６】
2008521278.tif 000025
【図７】
2008521278.tif 000026
【図８】
2008521278.tif 000027
【図９】
2008521278.tif 000028
【図１０】
2008521278.tif 000029
【図１１】
2008521278.tif 000030
【図１２】
2008521278.tif 000031
【図１３】
2008521278.tif 000032
【図１４】
2008521278.tif 000033
【国際調査報告】
2008521278.tif 000034
2008521278.tif 000035
2008521278.tif 000036