(57)【要約】【課題】  メッセージ長およびデバイス鍵の数を減少させることができる鍵管理方法を提供する。【解決手段】  まず、Ｎ個の層（Ｎは３以上の自然数）を有する木構造のリーフにユーザを割り当てる。ついで、木構造におけるルートとリーフとの間の境界ノードから下位のノードをＤＭ法に基づいてカバーリングする。ついで、境界ノードをリーフとし、かつ、ＤＭ法でカバーリングされた部分木の内部に無効化ノードを有する境界ノードを無効化ノードとして、ＣＭ法に基づいて木構造をカバーリングする。【選択図】図１
2004248272.tif 000002
【特許請求の範囲】
【請求項１】
以下のステップを有することを特徴とする鍵管理方法：
（１）Ｎ個の層（Ｎは３以上の自然数）を有する木構造のリーフにユーザを割り当てるステップ；
（２）前記木構造におけるルートとリーフとの間の境界ノードから下位のノードをＤＭ法に基づいてカバーリングするステップ；
（３）ついで、前記境界ノードをリーフとし、かつ、前記ＤＭ法でカバーリングされた部分木の内部に無効化ノードを有する前記境界ノードを無効化ノードとして、ＣＭ法に基づいて前記木構造をカバーリングするステップ。
【請求項２】
以下のステップを有することを特徴とする鍵管理方法：
（１）Ｎ個の層（Ｎは３以上の自然数）を有する木構造のリーフ毎に割り当てたユーザの情報を記憶手段に記憶するステップ；
（２）前記木構造におけるルートとリーフとの間の境界ノードの情報を前記記憶手段に記憶するステップ；
（３）前記境界ノードから下位のノードを、前記記憶手段に格納されたＤＭ法のアルゴリズムに基づいてカバーリングし、カバーリングによるルートのノードの情報を前記記憶手段に格納するステップ；
（４）前記カバーリング毎に、当該カバーリングの内部に無効化ノードを有するか否かの情報を前記記憶手段に格納するステップ；
（５）前記境界ノードをリーフとし、かつ、前記ＤＭ法でカバーリングされた部分木の内部に無効化ノードを有する前記境界ノードを無効化ノードとして、前記記憶手段に格納されたＣＭ法のアルゴリズムに基づいて前記木構造をカバーリングし、カバーリングにおけるルートのノード情報を前記記憶手段に格納するステップ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツ再生のための鍵を管理する方法に関するものである。
【背景技術】
【０００２】
デジタルコンテンツを通信回路や記録媒体を介してユーザに渡す場合には、著作権保護を主な目的として、暗号化されたコンテンツを渡すことが多くなっている。ユーザは、正規の再生装置に格納された鍵を用いて、コンテンツを復号して再生することができる。
【０００３】
ところで、再生装置に格納された鍵が万一暴露されてしまうと、正規の再生装置でなくとも、暗号化されたコンテンツを再生されてしまう。そこで、一旦暴露された鍵は無効とする必要が生じる。つまり、ある鍵が暴露されたことをセンターが知ると、センターは、それ以降は、暴露された鍵では再生できない鍵を用いてコンテンツを暗号化し、ユーザに配信する。
【０００４】
しかしながら、各ユーザ（すなわち再生装置）に割り当てられた鍵を個別管理すると、管理される鍵の数は膨大になってしまう。そこで、木構造を用いることにより鍵数を押さえる手法が既に提案されている。この手法では、コンテンツをコンテンツ鍵で暗号化し、このコンテンツ鍵をデバイス鍵で暗号化する。センターは、暗号化されたコンテンツと、暗号化されたコンテンツ鍵とをユーザに配信する。さらに、センターは、デバイス鍵を木構造のノードに割り当てておく。正当なユーザは、暗号化されたコンテンツを復号できる適切なデバイス鍵を持つ。一方、無効化ユーザは、適切なデバイス鍵を有しない。この鍵管理手法は、さらに、次の二つに分類できる。
【０００５】
第１の手法は、全体の木構造から、無効化ユーザを含まない部分木を構成し、その部分木のルートに対してデバイス鍵を割り当てるものである（下記非特許文献１参照）。この手法を、この明細書では単にＣＭ法（Complete Subtree Method）と称する。ＣＭ法では、各ユーザの再生装置が格納するデバイス鍵の数を減らすことができる。しかしながら、ＣＭ法では、無効化ユーザが多くなると、メッセージ長（デバイス鍵で暗号化されたコンテンツ鍵の数）が長くなってしまう。
【０００６】
第２の手法は、部分木の中に無効化したユーザを含ませるとともに、無効化ユーザでは復号できないデバイス鍵を用いるものである（下記非特許文献１参照）。この手法を、この明細書では単にＤＭ法（Subset Difference Method）と称する。ＤＭ法では、部分木の数を減らすことによってメッセージ長を減らすことができる。しかし、ＤＭ法では、デバイス鍵の数が多くなってしまうという不都合がある。
【非特許文献１】Springer社発行 Joe Kilian編 Dalit Naor他著「Advances in Cryptology-CRYPT2001」４１頁〜６２頁
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、前記の事情に鑑みてなされたものである。本発明の目的は、メッセージ長およびデバイス鍵の数を減少させることができる鍵管理方法を提供することである。
【課題を解決するための手段】
【０００８】
本発明の鍵管理方法は、以下のステップを有している。
（１）Ｎ個の層（Ｎは３以上の自然数）を有する木構造のリーフにユーザを割り当てるステップ。
（２）前記木構造におけるルートとリーフとの間の境界ノードから下位のノードをＤＭ法に基づいてカバーリングするステップ。
（３）ついで、前記境界ノードをリーフとし、かつ、前記ＤＭ法でカバーリングされた部分木の内部に無効化ノードを有する前記境界ノードを無効化ノードとして、ＣＭ法に基づいて前記木構造をカバーリングするステップ。
ここで、ＤＭ法およびＣＭ法の意味は、前記した通りである。
【０００９】
本発明の鍵管理方法は、以下のステップを有する構成としてもよい。
（１）Ｎ個の層（Ｎは３以上の自然数）を有する木構造のリーフ毎に割り当てたユーザの情報を記憶手段に記憶するステップ。
（２）前記木構造におけるルートとリーフとの間の境界ノードの情報を前記記憶手段に記憶するステップ。
（３）前記境界ノードから下位のノードを、前記記憶手段に格納されたＤＭ法のアルゴリズムに基づいてカバーリングし、カバーリングによるルートのノードの情報を前記記憶手段に格納するステップ。
（４）前記カバーリング毎に、当該カバーリングの内部に無効化ノードを有するか否かの情報を前記記憶手段に格納するステップ。
（５）前記境界ノードをリーフとし、かつ、前記ＤＭ法でカバーリングされた部分木の内部に無効化ノードを有する前記境界ノードを無効化ノードとして、前記記憶手段に格納されたＣＭ法のアルゴリズムに基づいて前記木構造をカバーリングし、カバーリングにおけるルートのノード情報を前記記憶手段に格納するステップ。
ここで、記憶手段とは、この鍵管理方法を実行する鍵管理システムが利用できる任意の記憶装置である。
【発明の効果】
【００１０】
本発明によれば、メッセージ長およびデバイス鍵の数を減少させることができる鍵管理方法を提供することができる。
【発明を実施するための最良の形態】
【００１１】
本発明の一実施形態に係る鍵管理方法を、添付の図面を参照しながら説明する。まず、この方法に用いられる管理システムを図１に基づいて説明する。このシステムは、管理装置（センター）１と、再生装置２と、媒体３とを備えている。
【００１２】
管理装置１は、入力部１１と、デバイス鍵生成部１２と、コンテンツ鍵格納部１３と、コンテンツ鍵暗号化部１４と、コンテンツ暗号化部１５とを備えている。入力部１１は、無効化ユーザの情報など、必要な情報が外部装置または操作者により入力されるものである。
【００１３】
デバイス鍵生成部１２は、ＣＭ法に基づくデバイス鍵を生成する部分と、ＤＭ法に基づくラベルおよびラベルに基づくデバイス鍵を生成する部分とを有する。これらの生成アルゴリズムは後述する。また、これらの生成アルゴリズムは、管理装置１における適宜な記憶手段に、コンピュータプログラムとして格納されており、コンピュータによって実行できるようになっている。デバイス鍵生成部１２は、記憶部（図示せず）を備えており、この記憶部には、デバイス鍵管理表５（図２参照）とラベル管理表６（図３参照）とが格納されている。デバイス鍵管理表５には、境界ノード（後述）以上のノードＩＤ毎に、デバイス鍵等のデータが格納されている。ラベル管理表６には、境界ノード（後述）以下のノードＩＤ毎に、ラベル（管理装置１で作成しておく、ノード毎のラベル）等のデータが格納されている。ラベル管理表６には、ノードＩＤ毎に、そのノードの下位に無効化ノードを含むかどうかの情報（１か−１か）を、状態として含んでいる。
【００１４】
コンテンツ鍵格納部１３は、コンテンツを暗号化するための鍵を格納している部分である。この鍵としては、例えば共通鍵を用いることができる。
【００１５】
コンテンツ鍵暗号部１４は、デバイス鍵生成部１２で生成されたデバイス鍵によってコンテンツ鍵を暗号化するものである。コンテンツ暗号化部１５は、コンテンツをコンテンツ鍵で暗号化するものである。使用できる代表的な暗号化手法としては、例えばＤＥＳ暗号やＡＥＳ暗号が知られている。これらの暗号化手法は周知なので説明を省略する。
【００１６】
再生装置２は、受取部２１と、鍵記憶部２２と、コンテンツ鍵復号部２３と、コンテンツ復号部２４と、再生部２５とを備える。受取部２１は、媒体３を介して管理装置１から配信されたデータ（送信データ）を受け取るものである。鍵記憶部２２には、再生装置２の出荷時に、その再生装置２に固有のデバイス鍵、ラベルリストおよび復号化情報（図８参照）を設定しておく。コンテンツ鍵復号部２３は、コンテンツ鍵を復号するものである。この復号においては、鍵記憶部２２に格納されたデバイス鍵を用いる場合と、鍵記憶部２２に格納されたラベルから生成されたデバイス鍵を用いる場合とがある。デバイス鍵と受信データ（すなわち送信データ）とを用いた復号のアルゴリズムは後述する。コンテンツ復号部２４は、復号されたコンテンツ鍵を用いてコンテンツを復号するものである。再生部２５は、復号されたコンテンツを再生するものである。
【００１７】
媒体３は、通信路または記録媒体である。通信路の例は、インターネットなどのコンピュータネットワークまたは放送網などである。通信路は、有線でも無線でも良い。記録媒体の例は、ＤＶＤなどである。記録媒体としては、再生専用であっても書き込み可能型であってもよい。
【００１８】
つぎに、本実施形態の鍵管理方法を図４に基づいて説明する。この図では、５層の木構造を前提としている。この例では、各ノードに、次の規則で符号を付ける。すなわち、ＣＭ法を適用する部分（境界ノード以上のノード）においては、Ｎｄ−ｐとする。ここでｄはルートからの深さ、ｐは左から数えた順番である。数字は０から始める。また、ＤＭ法を適用する部分（境界ノード以下のノード）においては、Ｎｑｄ−ｐで表す。ここでｑは境界ノードにおける左から数えた順番、ｄは境界ノードからの深さ、ｐは境界ノードをルートとみなしたときの、当該ノードを左から数えた順番である。
【００１９】
本実施形態の方法では、まず、最下層のノードであるリーフＮ０２−０〜Ｎ３２−３にユーザ（つまり再生装置）を割り当てる。
【００２０】
一方、木構造におけるルートとリーフとの間に、境界ノードを設定しておく。この例では、第３層のノードＮ２−０〜Ｎ２−３が境界ノードとなる。
【００２１】
ついで、境界ノード以下のノードをＤＭ法に基づいてカバーリングする。つまり、境界ノードをルートとみなして、ＤＭ法を適用する。これにより、ＤＭ法に基づくカバーリングを行うことができる。すると、第３層のノードＮ２−０〜Ｎ２−３をルートとして、４個のカバーリングが生成される。図４の例では、第３層のノードＮ２−１をルートとするカバーリング中に無効化ユーザｕ１（ノードＮ１２−０）および無効化ユーザｕ２（ノードＮ１２−１）を含んでいる。
【００２２】
ついで、境界ノードをリーフとし、かつ、ＤＭ法でカバーリングされた部分木の内部に無効化ノードを有する境界ノードを無効化ノードとして、ＣＭ法に基づいてカバーリングを行う。これにより、ノードＮ２−２とノードＮ２−３とをルートとするカバーリングは統合される。その結果、図４に示されるような、３個のカバーリング（Ｓ２−０，Ｓ１０，１−０，Ｓ１−１）を生成することができる。ここで、Ｓ２−０は、ノードＮ２−０（＝Ｎ００であり、このノードはＤＭ法でのルートのノードになっている。）をルートとしたカバーリングである。Ｓ１０，１−０は、ノードＮ１０を外側の部分木、ノードＮ１１−０を内側の部分木（無効化ノードのルート）としたＤＭ法でのカバーリングである。Ｓ１−１は、ノードＮ２−２とノードＮ２−３をルートに持つ二つのＤＭ部のカバーリングを統合してできたカバーリングである。このカバーリングＳ１−１は、ノードＮ１−１をそのルートとしている。このようなカバーリング方法をこの明細書ではＨＳ法と称する。
【００２３】
カバーリング終了後は、管理装置１において送信データを生成して配信する。再生装置２は、媒体３を介してその送信データを受信し、送信データに含まれるコンテンツを復号する。この手順は、従来のＣＭ法およびＤＭ法と基本的に同様である。
【００２４】
以降においては、デバイス鍵の割り当て、送信データの生成等に関して、本実施形態の方法をより具体的に説明する。
【００２５】
（再生装置出荷時の初期設定）
まず、図５を参照して、再生装置２に対する、デバイス鍵、ラベルおよび復号化情報の割り当てについて説明する。この処理は、再生装置２の出荷時に予め実行されるものである。図４を用いて説明したとおり、ユーザ（再生装置）に、木構造におけるリーフのノードを割り当てる（ステップ５−１）。割り当ての結果は管理装置１中の適宜な記憶手段に保存する。例えば、ラベル管理表６に、再生装置番号という欄を追加する。それにより、ノードＩＤと再生装置番号とを対応付ければよい。
【００２６】
ついで、各ユーザに対応するリーフからルートに辿る各ノードの情報をスタック（図６参照）に保存する（ステップ５−２）。例えば、図４におけるユーザｕであれば、図６に示すようなノードＩＤがスタックに保存される。
【００２７】
ついで、ポップ命令pop()によりスタックからノードＩＤを取り出し、この情報を、ノードを示す変数Ｎに保存する（ステップ５−３）。ついで、この変数Ｎが空（ＮＵＬＬ）かどうかを判断し（ステップ５−４）、空であれば動作を終了する（ステップ５−５）。空でなければ、当該変数ＮがＣＭ部にあるかどうかを判断する（ステップ５−６）。ＣＭ部にあれば、当該変数Ｎに対応するデバイス鍵Ｌを、デバイス鍵管理表５から選び、ノードＩＤと組にして再生装置２に保存する（ステップ５−７）。すなわち、変数Ｎに対応するノードをＮｉ、デバイス鍵をＬｉとすれば、再生装置２の鍵記憶部２２に、ＮｉとＬｉの組として格納する。
【００２８】
変数Ｎに対応するノードが境界ノード以下ならば、ノードＮｉを始点としたラベルを生成する。ラベルの生成アルゴリズムは後述する。生成したラベルは、ユーザの再生装置２における鍵記憶部２２に、ノードＩＤに対応して格納される。ここで、当該ノードが境界ノードであるときは、境界ノードＮd-p（＝Ｎq0）のラベルＬＡＢＥＬq0を擬似乱数発生器Ｇを用いてＧM（ＬＡＢＥＬq0）で計算した結果をデバイス鍵Ｌd-pとして保存する（境界ノードではp=qである）。擬似乱数発生器Ｇについては後述する。また、ＣＭ部および境界ノードにおけるデバイス鍵は、管理装置１が予めノード毎に割り振って、デバイス鍵管理表５に記憶しておく。ここで、ノードＮｉが境界ノードであるときは、ノードＮｉをルートとした部分木に無効化ユーザを含まないカバーリングについてはＣＭ法で扱うが、境界ノードＮｉをルートとした部分木に無効化ユーザが存在する場合にはＤＭ法で扱うことに注意する。（ステップ５−８）。ついで、ステップ５−３に戻り、スタックに積まれた次のデータを取り出し、前記と同様の動作を行う。これにより、デバイス鍵と、ラベルリストと、復号化情報（ルートからユーザまでのパス）とを各再生装置２の鍵記憶部２２に記憶させておくことができる（図８参照）。
【００２９】
つぎに、ノードＮｉを始点としたラベルの生成方法を、図７を参照しながら説明する。以下の手順は、図８にあるラベルリストを作ることが目的である。ラベルリストは、Ｎｑｉ，Ｎｑｊ１，ラベルＬＡＢＥＬｑｉ、ｊ１の３要素を組として持つ。図８の例ではこの組が三つ存在する。ここで、ユーザノードをＮｑｕとすると、Ｎｑｊ１は、ＮｑｉからＮｑｕまで辿れるときに、そのパスから分岐するノードである。例えば、図４においてユーザｕがＮ１２−３のとき、Ｎｑｊ１としては、Ｎ１１−０，Ｎ１２−２である。以降では、Ｎｑｊ１を開始ノードと呼ぶ。このアルゴリズムにおいて使用するＮ０は、始点ノード（Ｎｑｉ）を保持する変数である。Ｎ１，Ｎ２は、ＮｑｉからＮｑｕに辿るときの親ノード（Ｎ１）、子ノード（Ｎ２）を指す変数である。変数ＬＡＢＥＬは、始点ノードＮｑｉに対応したラベルを初期値に持ち、以下に示す子ノードの位置に従って更新していくものである。
【００３０】
まず、始点ノードＮｑｉ、ユーザノードＮｑｕという情報の組が与えられる（ステップ７−１）。ついで、Ｎｑｕから、Ｎｑｉに辿るノードをスタックに保存する。例えば、図４の例では、Ｎ１２−３、Ｎ１１−１、Ｎ１０というノードＩＤがスタックに積まれることになる。さらに、空のラベルリストを生成しておく（ステップ７−２）。ついで、スタックからポップして変数Ｎ０に格納し、さらに、変数Ｎ０の内容を変数Ｎ１に格納する（ステップ７−３）。ここで、変数Ｎ０の内容に対応するラベル（例えばＮ１０のラベル）を変数ＬＡＢＥＬに代入する。ついで、スタックからポップして変数Ｎ２に代入する（ステップ７−４）。例えば、Ｎ１１−１がＮ２に格納される。ついで、変数Ｎ２が空であるかどうかを判断する（ステップ７−５）。
【００３１】
ステップ７−５において変数Ｎ２が空でなければ、Ｎ２がＮ１に対して左右どちらの子ノードかを判断する（ステップ７−７）。ここで、無効化されるノードは、自分の経路にあるノードとは反対側のノードとなることを注意する。Ｎ２がＮ１の左子ノードでない（つまり右子ノードである）ならば、Ｎ０と、Ｎ１の左ノードと、Ｎ１の左子ノードについてのＧＬ（ＬＡＢＥＬ）とを組としてラベルリストに追加する。ここで関数Ｇは疑似乱数発生器であり、
2004248272.tif 000003
で定義される。つまり、入力のビット数をｎとすると、３ｎビットの情報を出力する。出力された情報のうち、先頭のｎビットをＧＬ、中間のｎビットをＧＭ、最後のｎビットをＧＲで表す。
【００３２】
ついで、ＧＲ（ＬＡＢＥＬ）を変数ＬＡＢＥＬに入れる（ステップ７−９）。変数Ｎ２が変数Ｎ１の左ノードであれば、ＧＲ（ＬＡＢＥＬ）をラベルリストに追加し（ステップ７−１０）、ＧＬ（ＬＡＢＥＬ）をＬＡＢＥＬとする（ステップ７−１１）。これにより、図４の例では、ラベルリストとして、（Ｎ１０，Ｎ１１−０，ＬＡＢＥＬ１０，１−０）が生成される。ついで、Ｎ２をＮ１とする（ステップ７−１２）。ついで、ステップ７−４から繰り返す。すると、ラベルリストとして、（Ｎ１０，Ｎ１２−２，ＬＡＢＥＬ１０，２−２）が生成される。ステップ７−５において、変数Ｎ２が空（つまりスタックが空）と判定されたときは、これらのラベルリストが返される（ステップ７−６）。
【００３３】
ついで、図５のステップ５−３に戻り、スタックからポップする。これにより、始点ノードがＮ１１−１となる。ステップ７−１からの手順をさらに実行すると、ラベルリストとして、（Ｎ１１−１，Ｎ１２−２，ＬＡＢＥＬ１１−１，２−２）が生成される。このようにして、最終的に、図８に示されるラベルリストを生成することができる。
【００３４】
（送信データの作成方法）
つぎに、送信データの作成方法を図９に基づいて説明する。まず、コンテンツ鍵を作成し、コンテンツ鍵格納部１３に格納しておく（ステップ９−１）。ついで、入力部１１を介して、無効化ユーザのリストを受け取る（ステップ９−２）。このリストには、無効化ユーザのノードＩＤを表す情報が含まれている。ついで、本実施形態のカバーリング方法（ＨＳ法、後述）を用いて、カバーリングを行う（ステップ９−３）。カバーリングの結果、カバーリングの内部に無効化ノードを有するか否かというリストが生成される。このリストの形式は、（Ｎｉ，φ）または（Ｎｑｉ，Ｎｑｊ２）となる。前者は、内部に無効化ノードを有しない場合である。後者は、内部に無効化ノードを有する場合である。後者の第２項は、無効化ノードのルートのノードである。図４を用いた具体例は後述する。
【００３５】
ついで、カバーリングのうちの一つを選択する（ステップ９−４）。ついで、当該カバーリングが最終のものかどうかを判断し（ステップ９−５）、最終であれば、コンテンツをコンテンツ鍵で暗号化し、それを送信データに含めて（ステップ９−６）、終了させる（ステップ９−７）。
【００３６】
当該カバーリングが最終でなければ、当該カバーリングの内部に無効化ノードを含むか否かを判断する（ステップ９−８）。含まない場合は、ＣＭ法のカバーリングに対応したデバイス鍵を、管理装置１に格納されたものの中から選択する（ステップ９−９）。さらに、カバーリングのルートのノードＮｉと無効化ノードなしという情報φとを送信データに追加する（ステップ９−１０）。無効化ノードを内部に含むカバーリングならばＤＭ法のカバーリングに対応するデバイス鍵を生成する（ステップ９−１１）。この生成アルゴリズムは後述する。さらに、カバーリングのルートのノードＮｑｉと、このルートノードＮｑｉ直下でかつユーザと反対側のノード（すなわち開始ノード）Ｎｑｊ１と、この開始ノードＮｑｊ１から無効化ノードのルートまでの経路リスト（右、左の情報）とを管理装置１の適宜な記憶手段に記憶して、送信データに追加する（ステップ９−１２）。
【００３７】
ついで、コンテンツ鍵を、ステップ９−９または９−１１で得られたデバイス鍵で暗号化し、送信データに追加する（ステップ９−１３）。このようなアルゴリズムで得られる送信データは、次のような構造を持つ。
2004248272.tif 000004
ここで、（Ｎ２−０，φ）〜（Ｎ１−１，φ）は、カバーリング毎のルートノードや、内部に無効ノードを含むかどうか等を示す情報である。なお、Ｎ２−０＝Ｎ００である。また、（ＲＴ／ＬＴ，…）は、ＲＴまたはＬＴのいずれかが含まれることを示している。ＲＴは右、ＬＴは左を示している。この情報は、前記した、開始ノードから無効ノードのルートまでの経路リストとなっている。さらに、（Ｎ２−０，φ）〜（Ｎ１−１，φ）は、デバイス鍵の検索情報の組（ｉ１，ｉ２，…ｉｍ）となる。
2004248272.tif 000005
は、コンテンツ鍵Ｋをデバイス鍵Ｌ２−０〜Ｌ１−１で暗号化した情報である。
ＦＫ（Ｍ）は、コンテンツＭをコンテンツ鍵で暗号化した情報である。
【００３８】
ついで、図９のステップ９−３で記述したＨＳ法のカバーリングアルゴリズムについて、図１０を用いて詳細に説明する。
【００３９】
図９のステップ９−２に続いて、無効化ノードを、境界ノードをルートとする部分木に分類する（ステップ１０−１）。境界ノードを、Ｎｑ０（０≦ｑ＜ｓ）と表す。ｑは０から始まりｓ-1（図４ではｓ＝４）までの整数である。
【００４０】
ついで、ｑを０とする（ステップ１０−２）。ついで、ｑ＜ｓか否かを判断する（ステップ１０−３）。ｑ＜ｓでなければ、全ての境界ノードについての処理が終わっているので、ＣＭ法でのカバーリングを行う（ステップ１０−４）。このとき、既に記載したように、境界ノードをＣＭ法でのリーフノードとみなす。また、境界ノードをルートとするカバーリングの中に無効化ノードがあれば、当該境界ノード（すなわちリーフノード）を無効化ノードとみなす。この状態でＣＭ法のアルゴリズムを適用する。
【００４１】
ＣＭ法のアルゴリズムは、前記した非特許文献１に記載された通りであるが、要約すれば以下の通りである。ＣＭ部のカバーリングは、境界ノードＮｑ０をリーフとした木を考えてカバーリングを行う。リーフＮｑ０の無効化ノード／無効化でないノードの決め方は以下の通りである。すなわち、それぞれのノードをルートとした木を考え、その木に無効化ノードが含まれていれば、無効化ノードとする。その他（その木に無効化ノードが一つもない）ならば、無効化ノードでないとする。さらに、以下のステップを行う。
ステップ１：ＣＭ部とＤＭ部の境界にあるノードＮｑ０が無効化と判定されたノードと、木全体のルートノードとから、シュタイナー木（Steiner Tree）ＳＴ（Ｒ）を考える。なお、図４の例ではＲ＝｛Ｎ１０｝である。
ステップ２：ＳＴ（Ｒ）の各ノード直下のノードでＳＴ（Ｒ）に属さないノードをルートに持つ部分木をカバーＳｉとする。
【００４２】
ステップ１０−４が行われると、カバーリングリストをステップ９−３に返し（ステップ１０−５）、このアルゴリズムは終了する（ステップ１０−６）。
【００４３】
ステップ１０−３の判断がyesであれば、カバーリングの中に無効化ノードＲｑがあるか否かを判断する（ステップ１０−７）。Ｒｑが空集合φである（つまり無効化ノードがない）のであれば、Ｎｑ０を無効化ノードとしない（ステップ１０−８）。さらに、ラベル管理表６のノードＩＤがＮｑ０における状態を−１とする。これは無効化ノードか否かを判別するフラグとなる。ステップ１０−８の処理後は、ステップ１０−１１に進む。
【００４４】
ステップ１０−７の判断がnoであれば、境界ノードＮｑ０を無効化ノードとする（ステップ１０−９）。さらに、ラベル管理表６のノードＩＤ＝Ｎｑ０における状態を１とする。これも、無効化ノードか否かを判別するフラグとなる。
【００４５】
ステップ１０−９の後、境界ノードＮｑ０をルート、Ｒｑを無効化ノードの集合として、ＤＭ法を適用する（ステップ１０−１０）。ＤＭ法は、前記した非特許文献１に記載された通りであるが、要約すれば以下の通りである。
（１）部分木Ｔの二つのリーフｖｉ，ｖｊ（無効化されるユーザに割り当てられたリーフ）の共通の親ノードを見つけ、それをｖとする。このとき、ｖをルートとする部分木の中に、ｖｉ，ｖｊ以外の無効化ノードを含んでいてはならない。ｖの左の子ノードｖｌの子孫にはｖｉを、右の子ノードｖｒの子孫にはｖｊを含むように、それぞれｖｌ、ｖｒを定める。
（２）ｖｌ≠ｖｉならば、部分木のカバーをＳｌ，ｉとし、ｖｒ≠ｖｊならば、部分木のカバーをＳｒ，ｊとする。
（３）ｖの子孫を部分木Ｔから削除し、ｖをリーフとする。例えば、図４の例では、前記の操作の結果、ｖはＮ１１−０となる。
【００４６】
ステップ１０−８またはステップ１０−１０の後、ｑに１を加えて（ステップ１０−１１）、ステップ１０−３に戻る。このようにして、図４に示されるようなカバーリングＳ２−０、Ｓ１０，１−０およびＳ１−１を生成することができる。これらのカバーリングには、ステップ９−３で述べたように、カバーリング中に無効化ノードを含むか等の情報を含む。具体的には、図４の例では、
カバーリングリスト
2004248272.tif 000006
となる。
【００４７】
（デバイス鍵の生成方法）
つぎに、図９のステップ９−１１で述べたデバイス鍵の生成方法について、図１１を参照して説明する。まず、カバーリングにおけるルートのノードをＮｑｉとし、無効化ノードのルートのノードをＮｑｊ２とする（ステップ１１−１）。例えば、図４の例では、｛Ｎｑｉ，Ｎｑｊ２｝＝｛Ｎ１０，Ｎ１１−０｝となる。ついで、Ｎｑｊ２からＮｑｉに辿るノードをスタックに保存する。ついで、スタックからポップして変数Ｎｉに入れる。さらにスタックからポップして変数ＮＪ１に入れる。また、Ｎｉで示されるノードにおけるラベルを変数ＬＡＢＥＬに格納する。さらに、何も記録されていない経路リストを作成しておく（ステップ１１−３）。
【００４８】
ついで、ＮＪ１がＮｉの左ノードかどうかを判断する（ステップ１１−４）。左ノードであれば、ＧＬ（ＬＡＢＥＬ）を変数ＬＡＢＥＬに代入する（ステップ１１ー５）。右ノードであれば、ＧＲ（ＬＡＢＥＬ）を変数ＬＡＢＥＬに代入する（ステップ１１−６）。ついで、ＮＪ１をＮ１とし（ステップ１１−７）、スタックからポップして変数Ｎ２に代入する（ステップ１１−８）。ついで、Ｎ２が空であるかどうかを判断する（ステップ１１−９）。空であれば、スタックが空ということなので、ＧＭ（ＬＡＢＥＬ）をデバイス鍵Ｌとし、Ｎｉ、ＮＪ１、デバイス鍵Ｌ、経路リストを返し（ステップ１１−１０）、終了する。
【００４９】
ステップ１１−９においてＮ２が空でなければ、Ｎ１の左ノードがＮ２であるかどうかを判断する（ステップ１１−１１）。そうであれば、経路リストに、左を示す情報ＬＴを追加し、ＧＬ（ＬＡＢＥＬ）をＬＡＢＥＬに代入する（ステップ１１−１２）。Ｎ１の右子ノードがＮ２であれば、経路リストに、右を示す情報ＲＴを追加し、ＧＲ（ＬＡＢＥＬ）をＬＡＢＥＬとする（ステップ１１−１３）。ついで、Ｎ２をＮ１とし（ステップ１１−１４）、ステップ１１−８に戻る。これにより、ステップ１１−１０において、デバイス鍵を生成することができる。
【００５０】
（受信データの処理方法）
つぎに、受信データの処理方法について図１２を用いて説明する。受信データは、前記のようにして作成された送信データと同じものである。まず、受信データを再生装置２が受け取る（ステップ１２−１）。受信データのヘッダ情報における検索情報の組（ｉ１，…，ｉｍ）は、図４の例では、
（Ｎ２−０，φ），（Ｎ１０，Ｎ１１−０，（ＲＴ／ＬＴ，…，ＲＴ／ＬＴ）），（Ｎ１−１，φ）
となっている。これと、ルートから再生装置２までのパスを表わす復号化情報Ｉｕ（これは再生装置２に記憶されている）とから、ユーザの属する検索情報ｉｋ、つまり、再生装置２が属するカバーリングにおけるルートのノードＩＤであるＮｉまたはＮｑｉを検索する（ステップ１２−２）。なお、図４の例では、開始ノードと無効化ノードのルートとが同じなので、（ＲＴ／ＬＴ，…，ＲＴ／ＬＴ）＝（）（すなわち空）となっている。
【００５１】
ついで、ルートのノードＩＤであるＮｉまたはＮｑｉに対応するカバーリング中に無効化ノードがあるかどうかを判断する（ステップ１２−３）。yesであれば、ユーザの再生装置が持っているラベルから、疑似乱数発生器を用いて、デバイス鍵を計算する（ステップ１２−４）。ラベルからデバイス鍵を計算する方法は後述する。ステップ１２−４の後、生成したデバイス鍵でコンテンツ鍵を復号する（ステップ１２−６）。このとき、無効化された再生装置２では、コンテンツ鍵を復号できず、正当なユーザのみが復号できることが保証される。その理由はＤＭ法と同じなので説明を省略する。要するに、送信データおよび無効化ユーザが持つラベルからは、カバーリングに対応するデバイス鍵を生成することができない。
【００５２】
ステップ１２−３での判断がnoである場合は、ユーザの再生装置が持っているデバイス鍵を検索し（ステップ１２−５）、その鍵でコンテンツ鍵を復号する（ステップ１２−６）。このときも、無効化された再生装置では、コンテンツ鍵を復号できず、正当なユーザのみが復号できることが保証される。その理由はＣＭ法と同様なので説明を省略する。
【００５３】
ついで、復号されたコンテンツ鍵を用いてコンテンツを復号し、再生する（ステップ１２−７）。
【００５４】
つぎに、前記ステップ１２−４で述べた、ラベルからデバイス鍵を計算するアルゴリズムを、図１３を参照して説明する。まず、受信データ中の検索情報の組ｉ１〜ｉｍに基づいて、カバーリングのルートのノードＮｑｉ、その直下の開始ノードＮｑｊ１、開始ノードから無効化ノードのルートＮｑｊ２までの経路リスト（ＲＴ／ＬＴ，…，ＲＴ／ＬＴ）を得る（ステップ１３−１）。経路リストは、前記したように空であることもある。これらの情報の組が、ユーザの属する検索情報ｉｋとなる。
【００５５】
ついで、ｉｋの３番目の要素である経路リストを変数ＲＬ−Ｌｉｓｔに入れる。さらに、１を変数ｎに入れる。さらに、ノードの組（Ｎｑｉ，Ｎｑｊ１）に対応したラベルを変数ＬＡＢＥＬに入れる（ステップ１３−２）。
【００５６】
ついで、変数ＲＬ−Ｌｉｓｔのｎ番目の要素を変数ＲＬに代入する（ステップ１３−３）。次に変数ＲＬが空かどうかを判断する（ステップ１３−４）。空でなければ、ＲＬが左かどうか（つまりＬＴかどうか）を判断する（ステップ１３−５）。ＲＬが左であれば、変数ＬＡＢＥＬにＧＬ（ＬＡＢＥＬ）を代入する（ステップ１３−６）。ＲＬが右であれば、変数ＬＡＢＥＬにＧＲ（ＬＡＢＥＬ）を代入する（ステップ１３−７）。ついで、ｎに１を加えて変数ｎに代入し（ステップ１３−８）、ステップ１３−３に戻る。ステップ１３−４においてＲＬが空であれば、そのときの変数ＬＡＢＥＬを用いてＧＭ（ＬＡＢＥＬ）を計算し、その結果をデバイス鍵Ｌとする（ステップ１３−９）。このようにして、ラベルからデバイス鍵を生成することができる。
【００５７】
（本実施形態の方式の評価）
本実施形態の方法におけるメッセージ長とデバイス鍵数とを近似的に導出した。比較のため、従来のＣＭ法とＤＭ法における計算も行った。結果を表１に示す。ＨＳ法とあるのが本実施形態の方法である。
2004248272.tif 000007
【００５８】
表中ｄＣは、ルートから、ＣＭ部とＤＭ部とを分ける境界ノードまでの深さである。計算条件としては、ユーザ数（再生装置数）を約１０億人（２３０）、無効化ユーザを１．６万人（２１４）とした。また、デバイス鍵数（ここではラベル数を含む意味で用いる）は、
2004248272.tif 000008
により導出した。ここで、ｄＤは、境界ノードからリーフまでのＤＭ部の深さである。また、メッセージ長は、
2004248272.tif 000009
により導出した。ここで、
ｓ：境界ノードの個数
ｒ：無効化ユーザ数（すなわち無効化再生装置の数）
である。
【００５９】
さらに、木の深さとデバイス鍵数との関係を算出した。本実施形態の方法におけるデバイス鍵数は、
2004248272.tif 000010
によって算出できる。結果を図１４に示す。この実施形態の方法では、ＤＭ法に比較して、デバイス鍵数の増加を抑えることができる。このグラフにおいて、ＨＳ（１／３，２／３）とあるのは、境界ノードをルートから１／３の位置に設定したことを示す。同様に、ＨＳ（１／２，１／２）は、境界ノードをルートから１／２の位置とし、ＨＳ（２／３，１／３）は、境界ノードをルートから２／３の位置としている。
【００６０】
また、無効化ユーザ数とメッセージ長との関係を図１５論文の図１２）に示す。メッセージ長の導出には、前記と同様に、
2004248272.tif 000011
を用いた。本実施形態の方法によれば、メッセージ長を、ＤＭ法とほぼ同じレベルにまで抑えることができる。
【００６１】
また、前記実施形態の記載は単なる一例に過ぎず、本発明に必須の構成を示したものではない。各部の構成は、本発明の趣旨を達成できるものであれば、上記に限らない。
さらに、前記実施形態を実現するための各部（機能ブロックを含む）の具体的手段は、ハードウエア、ソフトウエア、ネットワーク、これらの組み合わせ、その他の任意の手段を用いることができ、このこと自体は当業者において自明である。また、機能ブロックどうしが複合して一つの機能ブロックに集約されても良い。さらに、機能ブロックが複数のハードウエアまたはソフトウエアの協働によって実現されても良い。
【図面の簡単な説明】
【００６２】
【図１】本発明の一実施形態に係る鍵管理方法に用いる鍵管理装置の概略的な構成を示すブロック図である。
【図２】デバイス鍵管理表の構成を示す説明図である。
【図３】ラベル管理表の構成を示す説明図である。
【図４】木構造の一例を表す説明図である。
【図５】再生装置へのデバイス鍵等の割り当てを行うアルゴリズムを説明するためのフローチャートである。
【図６】ノードの情報を格納するスタックの構成を説明するための説明図である。
【図７】Nを始点としたラベルの生成アルゴリズムを説明するためのフローチャートである。
【図８】再生装置に格納されるデバイス鍵、ラベルリスト、経路情報の構成を示す説明図である。
【図９】送信データの作成アルゴリズムを説明するためのフローチャートである。
【図１０】本実施形態の方法におけるカバーリングアルゴリズムを説明するためのフローチャートである。
【図１１】ＤＭ法でのカバーリングに対応したデバイス鍵の生成アルゴリズムを説明するためのフローチャートである。
【図１２】受信データの処理アルゴリズムを説明するためのフローチャートである。
【図１３】ラベルからデバイス鍵を計算するアルゴリズムを説明するためのフローチャートである。
【図１４】本実施形態の方法と比較例の方法の計算結果を示すグラフであって、横軸は木構造の深さ、縦軸はデバイス鍵数である。
【図１５】本実施形態の方法と比較例の方法の計算結果を示すグラフであって、横軸は無効ユーザの数、縦軸はメッセージ長である。
【符号の説明】
【００６３】
１  管理装置
２  再生装置
３  媒体
【図１】
2004248272.tif 000012
【図２】
2004248272.tif 000013
【図３】
2004248272.tif 000014
【図４】
2004248272.tif 000015
【図５】
2004248272.tif 000016
【図６】
2004248272.tif 000017
【図７】
2004248272.tif 000018
【図８】
2004248272.tif 000019
【図９】
2004248272.tif 000020
【図１０】
2004248272.tif 000021
【図１１】
2004248272.tif 000022
【図１２】
2004248272.tif 000023
【図１３】
2004248272.tif 000024
【図１４】
2004248272.tif 000025
【図１５】
2004248272.tif 000026