(57)【要約】【課題】  ＳＤ方式に基づく木構造を適用した暗号文提供構成において、暗号文復号を行なう機器に格納すべき情報量を削減可能とした構成を提供する。【解決手段】  ブロードキャストエンクリプション方式の一態様であるＳＤ方式、ＬＳＤ方式において設定するサブセット対応のラベル（ＬＡＢＥＬ）中、一部の特別サブセット対応ラベルを、中間ラベル（ＩＬ）から算出可能な値に設定し、異なる中間ラベル間の関係式としての関数を公開し、中間ラベルから算出可能なラベルを除くラベルと、１つの中間ラベルを階層木のリーフ（葉）対応の受信機に提供する。受信機は中間ラベルに基づいて必要なラベルを算出可能となる。本構成により、各受信機が安全に保持すべき情報量を削減することが可能となる。【選択図】  図１７
2005191805.tif 000002
【特許請求の範囲】
【請求項１】
階層木構成に基づくブロードキャストエンクリプション方式を適用し、排除（リボーク）機器を除く特定の選択機器にのみ復号可能な暗号文配信構成を実現する暗号文配信方法であり、
階層木においてＳＤ（Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に基づいて設定するサブセット各々に対応するラベル（ＬＡＢＥＬ）中、選択された一部の特別サブセットに対応するラベルを、該特別サブセット対応の中間ラベル（ＩＬ）から算出可能な値として設定するラベル設定ステップと、
異なる特別サブセットに対応する異なる中間ラベル間の関係式としての関数を公開するする関数公開ステップと、
前記ラベル設定ステップにおいて生成したラベル中、中間ラベルから算出可能なラベルを除くラベルと、１つの中間ラベルを、前記階層木のリーフ（葉）対応の受信機に提供するラベル提供ステップと、
選択したサブセットに対応するサブセットキーを適用した暗号文を生成し、前記受信機に提供する暗号文配信ステップと、
を有することを特徴とする暗号文配信方法。
【請求項２】
前記ラベル設定ステップは、
前記特別サブセットに対応するラベルを、該特別サブセット対応の中間ラベル（ＩＬ）に基づくハッシュ値として設定するステップであることを特徴とする請求項１に記載の暗号文配信方法。
【請求項３】
前記ラベル設定ステップにおいて選択する特別サブセットは、
階層木において、ノードｉを頂点とする部分木からノードｉより下層のノードｊを頂点とする部分木を除く集合として定義されたサブセットＳｉ，ｊ中、ノードｉおよびノードｊが階層木において直結された親子関係にある第１特別サブセットと、
階層木のすべてのリーフを含むルートを頂点とする全体木の集合として定義されたサブセットＳ１，φである第２特別サブセットと、
によって構成されていることを特徴とする請求項１に記載の暗号文配信方法。
【請求項４】
前記ラベル提供ステップは、
前記階層木のリーフ（葉）対応の受信機に提供する１つの中間ラベルを前記第１特別サブセットを構成するサブセットＳｉ，ｊ中、最下層のサブセットに対応する中間ラベルとするステップであることを特徴とする請求項３に記載の暗号文配信方法。
【請求項５】
前記ラベル設定ステップは、
２つの素数の積であるＭＬおよびＭＲ、ただしＭＬ≠ＭＲ、を生成するステップと、
Ｎ個のリーフを持つ階層木のルートからリーフに至る全ノードに、ルートをｉ＝１とし、上位から幅優先で番号付けしたノードｉ（ｉ＝１〜２Ｎ−１）各々に対応するノード対応値ｘｉを、
【数１】
2005191805.tif 000016
を満足する値として設定するノード対応値設定ステップと、
前記ノード対応値に等しい値として、前記中間ラベルを設定するステップと、
を有することを特徴とする請求項３に記載の暗号文配信方法。
【請求項６】
前記関数公開ステップは、
ＦＬ（ｘ）＝ｘ２ｍｏｄＭＬ
ＦＲ（ｘ）＝ｘ２ｍｏｄＭＲ
を公開するステップであることを特徴とする請求項５に記載の暗号文配信方法。
【請求項７】
前記ラベル設定ステップは、
階層木中に設定した１つの特別レベルによって分離したレイヤ別のサブセット管理構成を持つベーシックＬＳＤ（Ｂａｓｉｃ  Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に従って設定するサブセット各々に対応するラベル（ＬＡＢＥＬ）中、選択された一部の特別サブセットに対応するラベルを、該特別サブセット対応の中間ラベル（ＩＬ）から算出可能な値として設定するステップであることを特徴とする請求項１乃至６いずれかに記載の暗号文配信方法。
【請求項８】
前記ラベル設定ステップは、
階層木中に設定した複数の特別レベルによって分離したレイヤ別のサブセット管理構成を持つ一般化ＬＳＤ（Ｇｅｎｅｒａｌ  Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に従って設定するサブセット各々に対応するラベル（ＬＡＢＥＬ）中、選択された一部の特別サブセットに対応するラベルを、該特別サブセット対応の中間ラベル（ＩＬ）から算出可能な値として設定するステップであることを特徴とする請求項１乃至６いずれかに記載の暗号文配信方法。
【請求項９】
階層木構成に基づくブロードキャストエンクリプション方式であるＳＤ（Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に基づくサブセット各々に対応するサブセットキーを適用して生成された暗号文の復号処理を実行する情報処理装置であり、
前記サブセットから選択された特別サブセット対応の中間ラベル（ＩＬ）と、前記中間ラベル（ＩＬ）から算出できないサブセット対応のラベル（ＬＡＢＥＬ）とを格納した記憶部と、
前記中間ラベル（ＩＬ）に基づくラベルの算出処理を実行するとともに、前記ラベルに基づくサブセットキー算出処理を実行する演算部と、
前記サブセットキーに基づく暗号文の復号処理を実行する暗号処理部と、
を有することを特徴とする情報処理装置。
【請求項１０】
前記演算部は、
前記特別サブセットに対応するラベルを、特別サブセット対応の中間ラベル（ＩＬ）に基づくハッシュ値として算出する処理を実行する構成であることを特徴とする請求項９に記載の情報処理装置。
【請求項１１】
前記記憶部に格納される特別サブセット対応の中間ラベル（ＩＬ）は、
階層木において、ノードｉを頂点とする部分木からノードｉより下層のノードｊを頂点とする部分木を除く集合として定義されたサブセットＳｉ，ｊ中、ノードｉおよびノードｊが階層木において直結された親子関係にある第１特別サブセットと、
階層木のすべてのリーフを含むルートを頂点とする全体木の集合として定義されたサブセットＳ１，φである第２特別サブセットと、
から構成される特別サブセットから選択された１つのサブセットに対応する中間ラベルであることを特徴とする請求項９に記載の情報処理装置。
【請求項１２】
前記演算部は、
記憶部に保持した１つの特別サブセットに対応する中間ラベルに基づいて、異なる特別サブセットの中間ラベルを算出する処理を実行する構成であることを特徴とする請求項９に記載の情報処理装置。
【請求項１３】
前記演算部は、
記憶部に保持した１つの特別サブセットに対応する中間ラベルに基づいて、下記式、
ＩＬＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））＝ＦＬ（ＩＬＰ（ｙ），Ｓ（ｙ））
ＩＬＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））＝ＦＲ（ＩＬＰ（ｙ），Ｓ（ｙ））
のいずれかに基づいて、異なる特別サブセットの中間ラベルの算出処理を実行する構成である、
ただし、ＩＬｉ，ｊは、階層木において、ノードｉを頂点とする部分木からノードｉより下層のノードｊを頂点とする部分木を除く集合として定義されたサブセットＳｉ，ｊに対応する中間ラベルであり、
Ｐ（ｉ）＝ノードｉの親ノード、
Ｓ（ｉ）＝ノードｉの兄弟ノード
であり、
関数ＦＬおよび、ＦＲは、下記の関数、
ＦＬ（ｘ）＝ｘ２ｍｏｄＭＬ
ＦＲ（ｘ）＝ｘ２ｍｏｄＭＲ
ただし、ＭＬおよびＭＲは、ＭＬ≠ＭＲを満足する２つの素数の積、
であることを特徴とする請求項１２に記載の情報処理装置。
【請求項１４】
階層木構成に基づくブロードキャストエンクリプション方式であるＳＤ（Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に基づくサブセット各々に対応するサブセットキーを適用して生成された暗号文の復号処理を実行する情報処理方法であり、
前記サブセットから選択された特別サブセット対応の中間ラベル（ＩＬ）に基づくサブセット対応のラベル（ＬＡＢＥＬ）算出処理を実行するラベル算出ステップと、
前記ラベルに基づくサブセットキー算出処理を実行するサブセットキー算出ステップと、
前記サブセットキーに基づく暗号文の復号処理を実行する暗号文復号ステップと、
を有することを特徴とする情報処理方法。
【請求項１５】
前記ラベル算出ステップは、
前記特別サブセットに対応するラベルを、特別サブセット対応の中間ラベル（ＩＬ）に基づくハッシュ値として算出する処理を実行するステップであることを特徴とする請求項１４に記載の情報処理方法。
【請求項１６】
前記特別サブセット対応の中間ラベル（ＩＬ）は、
階層木において、ノードｉを頂点とする部分木からノードｉより下層のノードｊを頂点とする部分木を除く集合として定義されたサブセットＳｉ，ｊ中、ノードｉおよびノードｊが階層木において直結された親子関係にある第１特別サブセットと、
階層木のすべてのリーフを含むルートを頂点とする全体木の集合として定義されたサブセットＳ１，φである第２特別サブセットと、
から構成される特別サブセットから選択された１つのサブセットに対応する中間ラベルであることを特徴とする請求項１４に記載の情報処理方法。
【請求項１７】
前記情報処理方法は、さらに、
１つの特別サブセットに対応する中間ラベルに基づいて、異なる特別サブセットの中間ラベルを算出する処理を実行する中間ラベル算出ステップを有することを特徴とする請求項１４に記載の情報処理方法。
【請求項１８】
前記中間ラベル算出ステップは、
１つの特別サブセットに対応する中間ラベルに基づいて、下記式、
ＩＬＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））＝ＦＬ（ＩＬＰ（ｙ），Ｓ（ｙ））
ＩＬＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））＝ＦＲ（ＩＬＰ（ｙ），Ｓ（ｙ））
のいずれかに基づいて、異なる特別サブセットの中間ラベルの算出処理を実行するステップである、
ただし、ＩＬｉ，ｊは、階層木において、ノードｉを頂点とする部分木からノードｉより下層のノードｊを頂点とする部分木を除く集合として定義されたサブセットＳｉ，ｊに対応する中間ラベルであり、
Ｐ（ｉ）＝ノードｉの親ノード、
Ｓ（ｉ）＝ノードｉの兄弟ノード
であり、
関数ＦＬおよび、ＦＲは、下記の関数、
ＦＬ（ｘ）＝ｘ２ｍｏｄＭＬ
ＦＲ（ｘ）＝ｘ２ｍｏｄＭＲ
ただし、ＭＬおよびＭＲは、ＭＬ≠ＭＲを満足する２つの素数の積、
であることを特徴とする請求項１７に記載の情報処理方法。
【請求項１９】
階層木構成に基づくブロードキャストエンクリプション方式であるＳＤ（Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に基づくサブセット各々に対応するサブセットキーを適用して生成された暗号文の復号処理を実行するコンピュータ・プログラムであり、
前記サブセットから選択された特別サブセット対応の中間ラベル（ＩＬ）に基づくサブセット対応のラベル（ＬＡＢＥＬ）算出処理を実行するラベル算出ステップと、
前記ラベルに基づくサブセットキー算出処理を実行するサブセットキー算出ステップと、
前記サブセットキーに基づく暗号文の復号処理を実行する暗号文復号ステップと、
を有することを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号文配信方法、情報処理装置、および情報処理方法、並びにコンピュータ・プログラムに関する。さらに、詳細には、階層木構造を適用したブロードキャストエンクリプション方式において現在知られているＳｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式、およびＬａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＬＳＤ）方式を、平方剰余木を用いて改良することで、効率的でセキュアな情報配信を可能とした暗号文配信方法、情報処理装置、および情報処理方法、並びにコンピュータ・プログラムに関する。
【背景技術】
【０００２】
昨今、音楽等のオーディオデータ、映画等の画像データ、ゲームプログラム、各種アプリケーションプログラム等、様々なソフトウエアデータ（以下、これらをコンテンツ（Content）と呼ぶ）が、インターネット等のネットワークを介して、あるいはＣＤ(Compact Disc)、ＤＶＤ(Digital Versatile Disk)、ＭＤ(Mini Disk)等の情報記録媒体（メディア）を介して流通している。これらの流通コンテンツは、ユーザの所有するＰＣ（Personal Computer）やプレーヤ、あるいはゲーム機器等、様々な情報処理装置において再生され利用される。
【０００３】
音楽データ、画像データ等、多くのコンテンツは、一般的にその作成者あるいは販売者に頒布権等が保有されている。従って、これらのコンテンツの配布に際しては、一定の利用制限、すなわち、正規なユーザに対してのみ、コンテンツの利用を許諾し、許可のない複製等が行われないようにする構成をとるのが一般的となっている。
【０００４】
特に、近年においては、情報をデジタル的に記録する記録装置や記憶媒体が普及しつつある。このようなデジタル記録装置および記憶媒体によれば、例えば画像や音声を劣化させることなく記録、再生を繰り返すことが可能であり、不正コピーコンテンツのインターネットを介した配信や、ＣＤ−Ｒ等の記録媒体に対する不正コピーという問題が発生している。
【０００５】
このようなコンテンツの不正利用を防止する１つの方式として、コンテンツあるいは暗号化コンテンツを復号するための鍵を暗号化して配布し、特定の正規ユーザまたは正規デバイスのみが、配布データの復号を可能としたシステムがある。例えばブロードキャストエンクリプション（Broadcast Encryption）方式の一態様である階層型木構造を適用した構成が知られている。
【０００６】
階層型木構造を適用した暗号鍵等の暗号データ提供処理について、図を参照して説明する。
【０００７】
図１に示す階層型木構造は２分木を用いており、その最下層がリーフ（葉）と呼ばれ、頂点、各分岐部およびリーフを含む部分をノードと称する。なお、頂点をルート、あるいはルートノードと呼ぶ。図１に示す２分木階層型木構造において、リーフは８〜１５、ノードは１〜１５、ルートは１である。
【０００８】
この２分木階層型木構造におけるリーフ８〜１５にコンテンツの利用機器としての再生機、受信機等の情報処理装置を１つずつ割り当てる。
【０００９】
また、木の各ノード（リーフを含む）１〜１５にそれぞれノードキーを１つずつ割り当てる。リーフ８〜１５に割り当てるノードキーはリーフキーと呼ばれる場合もある。
【００１０】
リーフに対応する各情報処理装置には、対応するリーフからルートまでの経路にあるノードに割り当てられたノードキーが与えられる。図１の構成では、リーフ８から１５までに割り当てられた８台の情報処理装置があり、ノード１から１５までにそれぞれノードキーが割り当てられており、リーフ８に対応する情報処理装置１０１には、ノード１，２，４，８に割り当てられた４個のノードキーが与えられる。また、リーフ１２に対応する情報処理装置１０２には、ノード１，３，６，１２に割り当てられた４個のノードキーが与えられる。各情報処理装置は、これらのノードキーを安全に保管する。
【００１１】
このノードキーの配布処理を伴うセッティングを用いて、選択した情報処理装置のみが取得可能な情報を送信する方法を図２を参照して説明する。たとえば、特定の音楽、画像データ等のコンテンツを暗号化した暗号化コンテンツをブロードキャスト配信、あるいはＤＶＤ等の記録媒体に格納して誰でも取得可能な状態で流通させ、その暗号化コンテンツを復号するための鍵（コンテンツキーＫｃ）を特定のユーザ、すなわち正規なコンテンツ利用権を持つユーザまたは情報処理装置にのみ提供する構成を想定する。
【００１２】
図２に示すリーフ１４に割り当てられた情報処理装置を不正な機器として、排除（リボーク）し、それ以外の情報処理装置が正規な情報処理装置であるとする。この場合、リーフ１４に割り当てられた情報処理装置ではコンテンツキーＫｃを取得できないが、他の情報処理装置ではコンテンツキーＫｃを取得できる暗号文を生成して、その暗号文をネットワークを介してあるいは記録媒体に格納して配布する。
【００１３】
この場合、リボーク（排除）される情報処理装置が持つノードキー（図２では×印で表現）以外のノードキーのうち、できるだけ多数の情報処理装置に共有されているもの、すなわち木の上部にあるものをいくつか用いて、コンテンツキーを暗号化して送信すればよい。
【００１４】
図２に示す例では、ノード２，６，１５のノードキーを用いて、コンテンツキーＫｃを暗号化した暗号文のセットを生成して提供する。すなわち、
Ｅ（ＮＫ２，Ｋｃ），Ｅ（ＮＫ６，Ｋｃ），Ｅ（ＮＫ１５，Ｋｃ）
の暗号文を生成して、ネットワーク配信あるいは記録媒体に格納して提供する。なお、Ｅ（Ａ，Ｂ）はデータＢを鍵Ａで暗号化したデータを意味する。またＮＫｎは、図に示す第ｎ番のノードキーを意味する。従って、上記式は、
コンテンツキーＫｃをノードキーＮＫ２で暗号化した暗号化データＥ（ＮＫ２，Ｋｃ）と、コンテンツキーＫｃをノードキーＮＫ６で暗号化した暗号化データＥ（ＮＫ６，Ｋｃ）と、コンテンツキーＫｃをノードキーＮＫ１５で暗号化した暗号化データＥ（ＮＫ１５，Ｋｃ）と、を含む３つの暗号文のセットであることを意味している。
【００１５】
上記３つの暗号文を作り、例えば同報通信路を用いて全情報処理装置に送信すれば、リボーク対象でない情報処理装置（図２示すリーフ８〜１３および１５に対応する情報処理装置）はいずれかの暗号文を自分が持つノードキーで復号することが可能であり、コンテンツキーＫｃを得ることができる。しかし、リボーク（排除）されたリーフ１４に対応する情報処理装置は、上記の３つの暗号文に適用された３つのノードキーＮＫ２、ＮＫ６、ＮＫ１５のいずれも保有していないので、この暗号文を受領しても、復号処理を行うことができずコンテンツキーＫｃを得ることはできない。
【００１６】
上述のブロードキャストエンクリプション（Broadcast Encryption）方式は、Ｃｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ方式と呼ばれる。このような木構造を用いて情報配信を行なう場合、リーフに対応する情報処理装置（ユーザ機器）が増大すると同報送信すべきメッセージが増大し、また各情報処理装置（ユーザ機器）において安全に格納すべきノードキーなどの鍵情報も増大してしまうという問題がある。
【００１７】
このような問題を解決する手法として、これまでに提案されている方式として、Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式、および、その改良版であるＬａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＬＳＤ）方式がある。ＳＤ方式については、例えば非特許文献１に記載され、ＬＳＤ方式については、例えば非特許文献２に記載されている。
【００１８】
いずれの方式も、ブロードキャストエンクリプションシステムの全受信機（受信者）数をＮとし、そのうち排除（リボーク）される、即ち、同報通信される秘密情報を受け取ることができない受信機の数をｒとしたときに、同報通信すべきメッセージ（暗号文）の数がＯ（ｒ）であり、これは上述したＣｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ方式などの他方式に比べて小さく、優れている。
【００１９】
しかし、各受信機が安全なメモリに保持すべき鍵（ラベル）の数が、ＳＤ方式ではＯ（ｌｏｇ２Ｎ）、ＬＳＤ方式では、Ｏ（ｌｏｇ１＋εＮ）となる。ここでεは任意の正の数である。この鍵の数は、Ｃｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ方式などの他方式に比べて多く、これを減らすことが課題となっている。
【非特許文献１】Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ−Ｃｒｙｐｔｏ  ２００１，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ２１３９，Ｓｐｒｉｎｇｅｒ，２００１  ｐｐ．４１−６２「Ｄ．Ｎａｏｒ，Ｍ．Ｎａｏｒ  ａｎｄ  Ｊ．Ｌｏｔｓｐｉｅｃｈ著"Ｒｅｖｏｃａｔｉｏｎ  ａｎｄ  Ｔｒａｃｉｎｇ  Ｓｃｈｅｍｅｓ  ｆｏｒ  Ｓｔａｔｅｌｅｓｓ  Ｒｅｃｅｉｖｅｒｓ"」
【非特許文献２】Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ−Ｃｒｙｐｔｏ  ２００２，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ２４４２，Ｓｐｒｉｎｇｅｒ，２００２，ｐｐ４７−６０「Ｄ．Ｈａｌｅｖｙ  ａｎｄ  Ａ．Ｓｈａｍｉｒ著"Ｔｈｅ  ＬＳＤ  Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ"」
【発明の開示】
【発明が解決しようとする課題】
【００２０】
本発明は、このような状況に鑑みてなされたものであり、ブロードキャストエンクリプション（Broadcast Encryption）方式の一態様である階層型木構造を適用した情報配信構成において比較的に効率的な構成であるとされているＳｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式、およびＬａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＬＳＤ）方式に対して、さらに平方剰余木を適用することにより、各受信機が安全に保持すべき情報量を削減することを可能とし、効率的でセキュアな情報配信を可能とした暗号文配信方法、情報処理装置、および情報処理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【００２１】
より、具体的にはＳＤ方式、ＬＳＤ方式、それぞれの方式において各受信機が安全に保持すべき情報量（ラベルの数）をそれぞれｌｏｇＮだけ減少させる。すなわち、ＳＤ方式およびＬＳＤ方式で定義される鍵の中でひとつの受信機が保持すべきもののうち、特定のｌｏｇＮ＋１個の鍵をひとつの鍵から計算により導出可能な設定とすることにより、各受信機が安全に保持すべき情報量（ラベルの数）を削減することを可能とした暗号文配信方法、情報処理装置、および情報処理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２２】
本発明の第１の側面は、
階層木構成に基づくブロードキャストエンクリプション方式を適用し、排除（リボーク）機器を除く特定の選択機器にのみ復号可能な暗号文配信構成を実現する暗号文配信方法であり、
階層木においてＳＤ（Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に基づいて設定するサブセット各々に対応するラベル（ＬＡＢＥＬ）中、選択された一部の特別サブセットに対応するラベルを、該特別サブセット対応の中間ラベル（ＩＬ）から算出可能な値として設定するラベル設定ステップと、
異なる特別サブセットに対応する異なる中間ラベル間の関係式としての関数を公開するする関数公開ステップと、
前記ラベル設定ステップにおいて生成したラベル中、中間ラベルから算出可能なラベルを除くラベルと、１つの中間ラベルを、前記階層木のリーフ（葉）対応の受信機に提供するラベル提供ステップと、
選択したサブセットに対応するサブセットキーを適用した暗号文を生成し、前記受信機に提供する暗号文配信ステップと、
を有することを特徴とする暗号文配信方法にある。
【００２３】
さらに、本発明の暗号文配信方法の一実施態様において、前記ラベル設定ステップは、前記特別サブセットに対応するラベルを、該特別サブセット対応の中間ラベル（ＩＬ）に基づくハッシュ値として設定するステップであることを特徴とする。
【００２４】
さらに、本発明の暗号文配信方法の一実施態様において、前記ラベル設定ステップにおいて選択する特別サブセットは、階層木において、ノードｉを頂点とする部分木からノードｉより下層のノードｊを頂点とする部分木を除く集合として定義されたサブセットＳｉ，ｊ中、ノードｉおよびノードｊが階層木において直結された親子関係にある第１特別サブセットと、階層木のすべてのリーフを含むルートを頂点とする全体木の集合として定義されたサブセットＳ１，φである第２特別サブセットと、によって構成されていることを特徴とする。
【００２５】
さらに、本発明の暗号文配信方法の一実施態様において、前記ラベル提供ステップは、前記階層木のリーフ（葉）対応の受信機に提供する１つの中間ラベルを前記第１特別サブセットを構成するサブセットＳｉ，ｊ中、最下層のサブセットに対応する中間ラベルとするステップであることを特徴とする。
【００２６】
さらに、本発明の暗号文配信方法の一実施態様において、前記ラベル設定ステップは、２つの素数の積であるＭＬおよびＭＲ、ただしＭＬ≠ＭＲ、を生成するステップと、Ｎ個のリーフを持つ階層木のルートからリーフに至る全ノードに、ルートをｉ＝１とし、上位から幅優先で番号付けしたノードｉ（ｉ＝１〜２Ｎ−１）各々に対応するノード対応値ｘｉを、
【数２】
2005191805.tif 000003
を満足する値として設定するノード対応値設定ステップと、前記ノード対応値に等しい値として、前記中間ラベルを設定するステップと、を有することを特徴とする。
【００２７】
さらに、本発明の暗号文配信方法の一実施態様において、前記関数公開ステップは、
ＦＬ（ｘ）＝ｘ２ｍｏｄＭＬ
ＦＲ（ｘ）＝ｘ２ｍｏｄＭＲ
を公開するステップであることを特徴とする。
【００２８】
さらに、本発明の暗号文配信方法の一実施態様において、前記ラベル設定ステップは、階層木中に設定した１つの特別レベルによって分離したレイヤ別のサブセット管理構成を持つベーシックＬＳＤ（Ｂａｓｉｃ  Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に従って設定するサブセット各々に対応するラベル（ＬＡＢＥＬ）中、選択された一部の特別サブセットに対応するラベルを、該特別サブセット対応の中間ラベル（ＩＬ）から算出可能な値として設定するステップであることを特徴とする。
【００２９】
さらに、本発明の暗号文配信方法の一実施態様において、前記ラベル設定ステップは、階層木中に設定した複数の特別レベルによって分離したレイヤ別のサブセット管理構成を持つ一般化ＬＳＤ（Ｇｅｎｅｒａｌ  Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に従って設定するサブセット各々に対応するラベル（ＬＡＢＥＬ）中、選択された一部の特別サブセットに対応するラベルを、該特別サブセット対応の中間ラベル（ＩＬ）から算出可能な値として設定するステップであることを特徴とする。
【００３０】
さらに、本発明の第２の側面は、
階層木構成に基づくブロードキャストエンクリプション方式であるＳＤ（Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に基づくサブセット各々に対応するサブセットキーを適用して生成された暗号文の復号処理を実行する情報処理装置であり、
前記サブセットから選択された特別サブセット対応の中間ラベル（ＩＬ）と、前記中間ラベル（ＩＬ）から算出できないサブセット対応のラベル（ＬＡＢＥＬ）とを格納した記憶部と、
前記中間ラベル（ＩＬ）に基づくラベルの算出処理を実行するとともに、前記ラベルに基づくサブセットキー算出処理を実行する演算部と、
前記サブセットキーに基づく暗号文の復号処理を実行する暗号処理部と、
を有することを特徴とする情報処理装置にある。
【００３１】
さらに、本発明の情報処理装置の一実施態様において、前記演算部は、前記特別サブセットに対応するラベルを、特別サブセット対応の中間ラベル（ＩＬ）に基づくハッシュ値として算出する処理を実行する構成であることを特徴とする。
【００３２】
さらに、本発明の情報処理装置の一実施態様において、前記記憶部に格納される特別サブセット対応の中間ラベル（ＩＬ）は、階層木において、ノードｉを頂点とする部分木からノードｉより下層のノードｊを頂点とする部分木を除く集合として定義されたサブセットＳｉ，ｊ中、ノードｉおよびノードｊが階層木において直結された親子関係にある第１特別サブセットと、階層木のすべてのリーフを含むルートを頂点とする全体木の集合として定義されたサブセットＳ１，φである第２特別サブセットと、から構成される特別サブセットから選択された１つのサブセットに対応する中間ラベルであることを特徴とする。
【００３３】
さらに、本発明の情報処理装置の一実施態様において、前記演算部は、記憶部に保持した１つの特別サブセットに対応する中間ラベルに基づいて、異なる特別サブセットの中間ラベルを算出する処理を実行する構成であることを特徴とする。
【００３４】
さらに、本発明の情報処理装置の一実施態様において、前記演算部は、記憶部に保持した１つの特別サブセットに対応する中間ラベルに基づいて、下記式、
ＩＬＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））＝ＦＬ（ＩＬＰ（ｙ），Ｓ（ｙ））
ＩＬＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））＝ＦＲ（ＩＬＰ（ｙ），Ｓ（ｙ））
のいずれかに基づいて、異なる特別サブセットの中間ラベルの算出処理を実行する構成である、
ただし、ＩＬｉ，ｊは、階層木において、ノードｉを頂点とする部分木からノードｉより下層のノードｊを頂点とする部分木を除く集合として定義されたサブセットＳｉ，ｊに対応する中間ラベルであり、
Ｐ（ｉ）＝ノードｉの親ノード、
Ｓ（ｉ）＝ノードｉの兄弟ノード
であり、
関数ＦＬおよび、ＦＲは、下記の関数、
ＦＬ（ｘ）＝ｘ２ｍｏｄＭＬ
ＦＲ（ｘ）＝ｘ２ｍｏｄＭＲ
ただし、ＭＬおよびＭＲは、ＭＬ≠ＭＲを満足する２つの素数の積、
であることを特徴とする。
【００３５】
さらに、本発明の第３の側面は、
階層木構成に基づくブロードキャストエンクリプション方式であるＳＤ（Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に基づくサブセット各々に対応するサブセットキーを適用して生成された暗号文の復号処理を実行する情報処理方法であり、
前記サブセットから選択された特別サブセット対応の中間ラベル（ＩＬ）に基づくサブセット対応のラベル（ＬＡＢＥＬ）算出処理を実行するラベル算出ステップと、
前記ラベルに基づくサブセットキー算出処理を実行するサブセットキー算出ステップと、
前記サブセットキーに基づく暗号文の復号処理を実行する暗号文復号ステップと、
を有することを特徴とする情報処理方法にある。
【００３６】
さらに、本発明の情報処理方法の一実施態様において、前記ラベル算出ステップは、前記特別サブセットに対応するラベルを、特別サブセット対応の中間ラベル（ＩＬ）に基づくハッシュ値として算出する処理を実行するステップであることを特徴とする。
【００３７】
さらに、本発明の情報処理方法の一実施態様において、前記特別サブセット対応の中間ラベル（ＩＬ）は、階層木において、ノードｉを頂点とする部分木からノードｉより下層のノードｊを頂点とする部分木を除く集合として定義されたサブセットＳｉ，ｊ中、ノードｉおよびノードｊが階層木において直結された親子関係にある第１特別サブセットと、
階層木のすべてのリーフを含むルートを頂点とする全体木の集合として定義されたサブセットＳ１，φである第２特別サブセットと、から構成される特別サブセットから選択された１つのサブセットに対応する中間ラベルであることを特徴とする。
【００３８】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法は、さらに、１つの特別サブセットに対応する中間ラベルに基づいて、異なる特別サブセットの中間ラベルを算出する処理を実行する中間ラベル算出ステップを有することを特徴とする。
【００３９】
さらに、本発明の情報処理方法の一実施態様において、前記中間ラベル算出ステップは、１つの特別サブセットに対応する中間ラベルに基づいて、下記式、
ＩＬＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））＝ＦＬ（ＩＬＰ（ｙ），Ｓ（ｙ））
ＩＬＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））＝ＦＲ（ＩＬＰ（ｙ），Ｓ（ｙ））
のいずれかに基づいて、異なる特別サブセットの中間ラベルの算出処理を実行するステップである、
ただし、ＩＬｉ，ｊは、階層木において、ノードｉを頂点とする部分木からノードｉより下層のノードｊを頂点とする部分木を除く集合として定義されたサブセットＳｉ，ｊに対応する中間ラベルであり、
Ｐ（ｉ）＝ノードｉの親ノード、
Ｓ（ｉ）＝ノードｉの兄弟ノード
であり、
関数ＦＬおよび、ＦＲは、下記の関数、
ＦＬ（ｘ）＝ｘ２ｍｏｄＭＬ
ＦＲ（ｘ）＝ｘ２ｍｏｄＭＲ
ただし、ＭＬおよびＭＲは、ＭＬ≠ＭＲを満足する２つの素数の積、
であることを特徴とする。
【００４０】
さらに、本発明の第４の側面は、
階層木構成に基づくブロードキャストエンクリプション方式であるＳＤ（Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に基づくサブセット各々に対応するサブセットキーを適用して生成された暗号文の復号処理を実行するコンピュータ・プログラムであり、
前記サブセットから選択された特別サブセット対応の中間ラベル（ＩＬ）に基づくサブセット対応のラベル（ＬＡＢＥＬ）算出処理を実行するラベル算出ステップと、
前記ラベルに基づくサブセットキー算出処理を実行するサブセットキー算出ステップと、
前記サブセットキーに基づく暗号文の復号処理を実行する暗号文復号ステップと、
を有することを特徴とするコンピュータ・プログラムにある。
【００４１】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００４２】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００４３】
本発明の構成によれば、ブロードキャストエンクリプション（Broadcast Encryption）方式の一態様である階層型木構造を適用した情報配信構成において比較的に効率的な構成であるとされているＳｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式、およびＬａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＬＳＤ）方式に対して、さらに平方剰余木を適用することにより、各受信機（情報処理装置）が安全に保持すべき情報量を削減することが可能となる。
【００４４】
さらに、本発明の構成によれば、ＳＤ方式、ＬＳＤ方式、それぞれの方式において各受信機が安全に保持すべき情報量をそれぞれｌｏｇＮだけ減少させる。すなわち、ＳＤ方式およびＬＳＤ方式で定義されるラベルの中でひとつの受信機が保持すべきもののうち、特定のｌｏｇＮ＋１個のラベルをひとつの中間ラベルから計算により導出可能な設定としたので、各受信機（情報処理装置）が安全に保持すべき情報量を削減することが可能となる。
【００４５】
さらに、本発明の構成によれば、階層木構成に基づくブロードキャストエンクリプション方式を適用し、排除（リボーク）機器を除く特定の選択機器にのみ復号可能な暗号文配信構成を実現する暗号文配信において、ＳＤ方式、ＬＳＤ方式に基づいて設定するサブセット各々に対応するラベル（ＬＡＢＥＬ）中、選択された一部の特別サブセットに対応するラベルを、特別サブセット対応の中間ラベル（ＩＬ）から算出可能な値として設定し、異なる特別サブセットに対応する異なる中間ラベル間の関係式としての関数を公開し、中間ラベルから算出可能なラベルを除くラベルと、１つの中間ラベルを、階層木のリーフ（葉）対応の受信機（情報処理装置）に提供する構成とし、受信機側において保持する中間ラベルに基づいて必要なラベルを算出可能としたので、各受信機が安全に保持すべき情報量を削減することが可能となる。
【発明を実施するための最良の形態】
【００４６】
以下、図面を参照しながら本発明の暗号文配信方法、情報処理装置、および情報処理方法、並びにコンピュータ・プログラムの詳細について説明する。
【００４７】
なお、説明は、以下の項目に従って行なう。
１．Ｃｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ（ＣＳ）方式の概要
２．Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式の概要
３．平方剰余木を用いたＳＤ方式のラベル数削減構成
４．平方剰余木の構成例
５．平方剰余木を適用した情報配信処理例
６．Ｂａｓｉｃ  Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ベーシックＬＳＤ）方式の概要
７．平方剰余木を用いたベーシックＬＳＤ方式のラベル数削減構成
８．Ｇｅｎｅｒａｌ  Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（一般化ＬＳＤ）方式の概要
９．平方剰余木を用いた一般化ＬＳＤ方式のラベル数削減構成
【００４８】
［１．Ｃｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ（ＣＳ）方式の概要］
まず既存の階層型木構造を適用したブロードキャストエンクリプション（Broadcast Encryption）方式として知られているＣｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ（ＣＳ）方式の概要について説明する。
【００４９】
なお、以下の説明においては、簡単のために、階層型木構造のリーフに対応して設定される情報処理装置（受信機）の総数Ｎは２のべき乗の数であるとする。また、以下の説明において、関数ｌｏｇの底はすべて２である。なお、階層型木構造のリーフに対応する機器は、以下に説明する秘密情報の復号処理を実行可能であれば、様々な機器、例えばＰＣ、携帯端末など、様々な情報処理装置の設定が可能である。ここでは、これらを総称して受信機として説明する。また、本発明における暗号文配信処理とは、通信ネットワークを介した通信による提供処理のみならず、記録媒体に格納した暗号文の提供処理も含むものである。
【００５０】
なお、以下の説明においては、下記の記号を用いて説明する。
Ｐ（ｉ）：ノードｉの親ノード
Ｓ（ｉ）：ノードｉの兄弟（ｓｉｂｌｉｎｇ）であるノード（すなわち、ｉと異なるノードで、ｉと同じ親を持つノード）
ＬＣ（ｉ）：ノードｉの左側の子ノード
ＲＣ（ｉ）：ノードｉの右側の子ノード
【００５１】
（１）Ｃｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ（ＣＳ）方式
Ｃｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ（ＣＳ）方式は、基本的に背景技術の欄において説明した構成に相当し、図３に示すように、階層型木構造として各ノードが２つに分岐する形を持つ２分木を用いる。図３は、受信機数Ｎ＝１６の例である。この２分木の各リーフ（葉）に各受信機を割り当てる（図３におけるｕ１〜ｕ１６）。また、木の各ノード（節）を用いて、「そのノードを頂点とする部分木のリーフ（葉）に割り当てられた受信機からなる集合」を表す。図３におけるノードｉ２０１は、受信機ｕ５とｕ６からなる集合を表す。
【００５２】
そして、図３に示す２分木の各構成ノードに鍵（ノードキー）が定義される。各受信機には、各受信機が割り当てられているリーフ（葉）から木のルート（頂点）に至るパス上のノードに割り当てられたノードキーが与えられ、受信機はこれらのノードキーを安全なメモリに保持する。木の定義やノードキーの定義、受信機の割り当てやノードキーの配布などは、Ｔｒｕｓｔｅｄ  Ｃｅｎｔｅｒ（ＴＣ）と呼ばれる信頼される管理センタが行なう。
【００５３】
図４に示すように、階層木には１６台の受信機ｕ１〜ｕ１６が割り当てられ、ノードは１〜３１の３１個、存在する。受信機ｕ４には、ノード１，２，４，９，１９に割り当てられた５個のノードキーが与えられる。すなわち、全受信機数をＮとした場合には、各受信機はｌｏｇＮ＋１個のノードキーを保持することになる。
【００５４】
図５を用いて、このセッティングを用いて秘密情報（たとえば、暗号化されたコンテンツを復号するためのコンテンツキー）をどのようにリボークされない受信機に送信するかについて説明する。ここでは、管理センタ（ＴＣ）が秘密情報の送信者になるとする。いま、受信機ｕ２，ｕ１１，ｕ１２がリボークされる受信機とする。すなわち、受信機ｕ２，ｕ１１，ｕ１２を不正な機器として排除（リボーク）し、それ以外の受信機においてのみ安全に情報を受領、すなわち同報配信される暗号文に基づく復号を行なうことを可能とする。
【００５５】
管理センタ（ＴＣ）が秘密情報の送信を行なう場合、リボーク受信機ｕ２，ｕ１１，ｕ１２が割り当てられているリーフ（葉）から木のルートに至るパス上のノードに割り当てられたノードキーを暗号鍵として使用せず、暗号文のセットを生成して同報送信する。
【００５６】
リボーク受信機ｕ２，ｕ１１，ｕ１２が割り当てられているリーフ（葉）から木のルートに至るパス上のリーフまたはノードに割り当てられたノードキーを使用すると、これらは、リボークすべき受信機が持つキーであるため、リボーク機器において秘密情報を入手できてしまう。従って、これらのキーを用いずに暗号文のセットを生成して同報送信する。
【００５７】
リボーク受信機ｕ２，ｕ１１，ｕ１２が割り当てられているリーフ（葉）から木のルートに至るパス上のノードおよびパスを木から除外すると、１つ以上の部分木が残る。例えば、ノード５を頂点とする部分木、あるいはノード１２を頂点とする部分木などである。
【００５８】
秘密情報の送信者は、それぞれの部分木の頂点に最も近いノード、すなわち、図５に示す例では、ノード５，７，９，１２，１６に割り当てられたノードキーを用いて秘密情報を暗号化した暗号文のセットを送信する。例えば送信秘密情報を暗号化コンテンツの復号に適用するコンテンツキーＫｃであるとし、ノード５，７，９，１２，１６に割り当てられたノードキーをＮＫ５，ＮＫ７，ＮＫ９，ＮＫ１２，ＮＫ１６とすると、秘密情報の送信者は、
Ｅ（ＮＫ５，Ｋｃ），Ｅ（ＮＫ７，Ｋｃ），Ｅ（ＮＫ９，Ｋｃ），Ｅ（ＮＫ１２，Ｋｃ），Ｅ（ＮＫ１６，Ｋｃ）
の暗号文セットを生成して、ネットワーク配信あるいは記録媒体に格納して提供する。なお、Ｅ（Ａ，Ｂ）はデータＢを鍵Ａで暗号化したデータを意味する。
【００５９】
上記暗号文セットは、リボーク受信機ｕ２，ｕ１１，ｕ１２のみが復号することができず、その他の受信機では復号可能である。このような暗号文セットを生成し送信することで、効率的で安全な秘密情報の伝送が行える。
【００６０】
受信機は、伝送された暗号文のうち、自分が復号できるもの、すなわち、自身が割り当てられたリーフ（葉）からルートに至るまでのパス上のノードに対応するノードキーを用いて暗号化されたものを復号して秘密情報を得ることができる。上記の例では、受信機ｕ４はノード９のノードキーを保持しているので、これを用いて暗号化された暗号文Ｅ（ＮＫ９，Ｋｃ）を復号することができる。このように、リボークされていない受信機が復号できる暗号文は受信した暗号文セット中に必ずひとつ存在する。
【００６１】
［２．Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式］
上記のように、Ｃｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ（ＣＳ）方式においては、階層木の各ノード（節）を用いて、「そのノードを頂点とする部分木のリーフ（葉）に割り当てられた受信機からなる集合」を表していた。これに対し、Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式においては、階層木の２つのノードｉ，ｊ（ただしｉはｊの先祖であるノード）を用いて、「（ノードｉを頂点とする部分木のリーフ（葉）からなる集合）から（ノードｊを頂点とする部分木のリーフ（葉）からなる集合）を引いた集合」を表す。
【００６２】
たとえば図６のノードｉ２３１，とノードｊ２３２で定義される集合Ｓｉ，ｊは、受信機ｕ１〜ｕ８の集合からｕ５，ｕ６を除いたものであり、すなわち、Ｓｉ，ｊ＝｛ｕ１，ｕ２，ｕ３，ｕ４，ｕ７，ｕ８｝である。ノードｉがノードｊの先祖である（すなわち、ノードｊはノードｉと同一ではなく、ノードｊからルートへのパス上にノードｉが存在する）すべてのノードの組についてこのような集合を定義する。
【００６３】
サブセットＳｉ，ｊに対応する鍵としてサブセットキーＳＫｉ，ｊが設定される。サブセットキーＳＫｉ，ｊは、ｕ１〜ｕ８の集合からｕ５，ｕ６を除いたサブセットＳｉ，ｊ＝｛ｕ１，ｕ２，ｕ３，ｕ４，ｕ７，ｕ８｝が共通に保有する鍵として設定され、サブセットキーＳＫｉ，ｊを暗号鍵として秘密情報を暗号化した情報を送信することにより、サブセットＳｉ，ｊ＝｛ｕ１，ｕ２，ｕ３，ｕ４，ｕ７，ｕ８｝においてのみ復号可能となり、ｕ５，ｕ６をリボーク（排除）することができる。
【００６４】
このようなセッティングでは、ひとつの受信機が所属する集合の個数は、下式によって示される数Ｏ（Ｎ）となる。
【数３】
2005191805.tif 000004
【００６５】
従って、それぞれの集合（サブセット）に鍵（サブセットキー）を独立に割り当てたのでは、各受信機がＯ（Ｎ）個のサブセットキーを安全に保持する必要がある。しかし、これは、総受信機数Ｎの増大に伴い飛躍的に増大し、これらの大量の情報を各機器に安全に保管させることは現実的に困難である。
【００６６】
このため、Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式では以下に述べる工夫を用いている。前述したＣｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ（ＣＳ）方式と同様に、管理センタ（ＴＣ）が階層木の定義やサブセットの定義、鍵の定義、配布などを行うものとする。
【００６７】
まず、図７（Ａ）に示すように、管理センタ（ＴＣ）は、ある内部ノード（すなわち、リーフ（葉）でないノード）ｉに注目し、そのノードｉのラベルをＬＡＢＥＬｉとしてＣビットの値Ｓをランダムに選択する。
【００６８】
次に、図７（Ｂ）の図に示すように、ＬＡＢＥＬｉ＝Ｓを、Ｃビット入力、３Ｃビット出力の擬似乱数生成器Ｇに入力する。この出力を左から（最上位ビット側から）Ｃビットずつに区切り、それぞれＧＬ（Ｓ），ＧＭ（Ｓ），ＧＲ（Ｓ）とする。そして、ＧＬ（Ｓ）を、図７（Ａ）に示すノードｉの左側の子ノードｋのラベルとし、またＧＲ（Ｓ）をノードｉの右側の子ノードのラベルとする。
【００６９】
いま、この処理により、図７においてノードｉの左側の子であるノードｋについて、ノードｉを始点にした場合のノードｋのラベルＬＡＢＥＬｉ，ｋは、ＬＡＢＥＬｉ，ｋ＝ＧＬ（Ｓ）となった。これをＴとおく。次に、今度はノードｋのラベルＬＡＢＥＬｉ，ｋ＝ＧＬ（Ｓ）＝Ｔを、図７（Ｂ）に示す擬似乱数生成器Ｇに入力し、その出力を左からＣビットずつに区切った、ＧＬ（Ｔ），ＧＭ（Ｔ），ＧＲ（Ｔ）を、それぞれ以下のように設定する。
ＧＬ（Ｔ）＝ノードｉを始点にした場合のノードｋの左側の子ノードＬＣ（ｋ）のラベルＬＡＢＥＬｉ，ＬＣ（ｋ）
ＧＭ（Ｔ）＝ノードｉを始点にした場合のノードｋの鍵（これを集合Ｓｉ，ｋに対応するサブセットキーＳＫｉ，ｋとする）
ＧＲ（Ｔ）＝ノードｉを始点にした場合のノードｉの右側の子ノードＲＣ（ｋ）のラベルＬＡＢＥＬｉ，ＲＣ（ｋ）
【００７０】
この処理を繰り返すことにより、ノードｉを始点とした場合の、その子孫となるすべてのノードに対応するラベルを作り出す。なお、上記の定義によれば集合Ｓｉ，ｉは空集合であり、ノードｉを始点とした場合に、ノードｉの鍵というものは不要であるため、ＬＡＢＥＬｉを擬似乱数生成器Ｇに入力した出力の中央部分であるＧＭ（Ｓ）は使われないことに注意されたい。
【００７１】
図７（Ａ）の例で示すと、始点であるノードｉのラベルＳが定められ、ＧＲ（Ｓ）がノードｉを始点とした場合のｉの右の子ノードのラベルとなり、さらにそれを擬似乱数生成器Ｇに入力して得られたＧＬ（ＧＲ（Ｓ））が、ノードｉを始点とした場合のノードｊのラベルＬＡＢＥＬｉ，ｊとなる。ノードｉを始点とした場合の、その子孫となるすべてのノードに対応するラベルを作り出す処理を、すべての内部ノードｉに対して行う。
【００７２】
これらの処理はシステムのセットアップ時に、管理センタ（ＴＣ）によって行われるが、擬似乱数生成器（あるいは擬似乱数生成関数）Ｇは、管理センタ（ＴＣ）によって定められ公開されており、これを用いることによって、ＬＡＢＥＬｉ，ｊを与えられた受信機は、ノードｉを始点とした場合の、ノードｊの子孫となるすべてのノードｎのラベルＬＡＢＥＬｉ，ｎを計算することおよび、ノードｉを始点とした場合の、ノードｊおよびその子孫ノードｎのサブセットキーＳＫｉ，ｎを計算することが可能となる。
【００７３】
このような設定により、図８（Ａ）に示すように、ある受信機ｕは、それが割り当てられたリーフ（葉）から木の頂点へのパス上のそれぞれの内部ノードｉについて、ノードｉを始点として、このリーフ（葉）ｕからｉへのパスから直接枝分かれしているノードであるノードａ，ｂ，ｃのラベルのみを保持しておけばよいことになる。
【００７４】
これらのノードａ，ｂ，ｃおよびその子孫となるノードの、ノードｉを始点としたサブセットキーを作り出すことが可能となる。図８（Ａ）では、ノードｉに注目したときに、ｕからｉへのパスから直接枝分かれしているノードはａ，ｂ，ｃの３つであり、受信機ｕはこれら３つのラベルをシステムのセットアップ時に、管理センタ（ＴＣ）から与えられて保持する。
【００７５】
リーフｕは、ノードａのラベルＬＡＢＥＬｉ，ａに基づく擬似乱数生成器Ｇの処理によって、サブセットＳｉ，ａに対応するサブセットキーＳＫｉ，ａを求ることができる。すなわち、
ＧＭ（ＬＡＢＥＬｉ，ａ）＝ＳＫｉ，ａとなる。
サブセットＳｉ，ａは、図８（ａ）に示すように、ノードａを頂点とした部分木のリーフをリボーク機器として設定したサブセットであり、ノードｉを頂点とした部分木のリーフのうちノードａを頂点とした部分木のリーフ以外のリーフのみを情報配信対象として設定されるサブセットである。
【００７６】
また、リーフｕは、ノードｂのラベルＬＡＢＥＬｉ，ｂに基づく擬似乱数生成器Ｇの処理によって、サブセットＳｉ，ｂに対応するサブセットキーＳＫｉ，ｂを求めることができる。すなわち、
ＧＭ（ＬＡＢＥＬｉ，ｂ）＝ＳＫｉ，ｂとなる。
サブセットＳｉ，ｂは、図８（ｂ）に示すように、ノードｂを頂点とした部分木のリーフをリボーク機器として設定したサブセットであり、ノードｉを頂点とした部分木のリーフのうちノードｂを頂点とした部分木のリーフ以外のリーフのみを情報配信対象として設定されるサブセットである。
【００７７】
また、リーフｕは、ノードｃのラベルＬＡＢＥＬｉ，ｃに基づく擬似乱数生成器Ｇの処理によって、サブセットＳｉ，ｃに対応するサブセットキーＳＫｉ，ｃを求ることができる。すなわち、
ＧＭ（ＬＡＢＥＬｉ，ｃ）＝ＳＫｉ，ｃとなる。
サブセットＳｉ，ｃは、図８（ｃ）に示すように、ノードｃ（リーフｃ）をリボーク機器として設定したサブセットであり、ノードｉを頂点とした部分木のリーフのうちリーフｃ以外のリーフのみを情報配信対象として設定されるサブセットである。
【００７８】
ｉを始点とする階層木において、リーフｕ以外のリーフをリボークする構成は、これら３つ以外にも様々設定可能である。例えば図８（ａ）のリーフｄ２５１のみをリポーク対象とする場合は、サブセットＳｉ，ｄを設定し、サブセットキーＳＫｉ，ｄを適用することが必要である。しかし、各ノード、リーフに対応する鍵、すなわちサブセットキーは、上位のラベルに基づく擬似乱数生成処理により生成可能である。従って、リーフｕは、リーフｄ２５１のリボークに対応するサブセットキーＳＫｉ，ｄを、リーフｕが保有するノードａのラベルＬＡＢＥＬｉ，ａに基づいて生成可能となる。
【００７９】
その他のサブセット構成についても同様であり、図８（Ａ）に示すように、ある受信機ｕは、それが割り当てられたリーフ（葉）から木の頂点へのパス上のそれぞれの内部ノードｉについて、ノードｉを始点として、このリーフ（葉）ｕからｉへのパスから直接枝分かれしているノードであるノードａ，ｂ，ｃのラベルのみを保持しておけばよいことになる。
【００８０】
図９は全受信機数Ｎ＝１６の設定の場合に各受信機が保持すべきラベルを示す図である。いま、受信機ｕ４を考えると、それが割り当てられたリーフ（葉）であるノード１９から頂点１へのパス上の内部ノード１，２，４，９が始点（ノードｉ）となる。ノード１を始点とすると、ノード１９からノード１へのパスから直接枝分かれしているノードは３，５，８，１８の４つであるため、受信機ｕ４は４つのラベル、すなわち、
ＬＡＢＥＬ１，３，
ＬＡＢＥＬ１，５，
ＬＡＢＥＬ１，８，
ＬＡＢＥＬ１，１８，
を保持する。
【００８１】
同様に、ノード２を始点とした場合には、
ＬＡＢＥＬ２，５，
ＬＡＢＥＬ２，８，
ＬＡＢＥＬ２，１８，
の３つのラベルを保持する。
【００８２】
ノード４を始点とした場合には、
ＬＡＢＥＬ４，８，
ＬＡＢＥＬ４，１８，
の２つのラベルを保持する。
【００８３】
ノード９を始点とした場合には、
ＬＡＢＥＬ９，１８，
の１つのラベルを保持する。
【００８４】
また、リボークすべき受信機がないという特別な場合に使用する全受信機を含む集合（これをサブセットＳ１，φと表すことにする）に対応するラベル
ＬＡＢＥＬ１，φ，
を１つ保持する。
【００８５】
すなわち、図９の構成においてｕ４が持つＬＡＢＥＬをまとめると、図９にも記載しているように、
ｉ＝１に対してｊ＝３，５，８，１８の４つのラベル
ｉ＝２に対してｊ＝５，８，１８の３つのラベル
ｉ＝４に対してｊ＝８，１８の２つのラベル
ｉ＝９に対してｊ＝１８の１つのラベル
リボークなしの場合用のＬＡＢＥＬを１つ
の計１１個のラベルとなる。
【００８６】
ただし、ここでは説明を統一するため、サブセットＳ１，φに対応するラベルとしているが、ラベルではなくサブセットＳ１，φに対応するに対応するサブセットキーを直接保持してもよい。
【００８７】
上記のように、各受信機は、リーフ（葉）からルートへのパス上の各内部ノードについて、その内部ノードの高さ分だけのラベルと特別な１つのラベルを保持する必要があるから、送受信機数をＮとした場合に各受信機が保持するラベル数は、下記式によって算出される数となる。
【数４】
2005191805.tif 000005
【００８８】
各受信機は、上記式によって示される数のラベルを保持し、公開されている擬似乱数生成関数Ｇを用いることにより必要とするサブセットキーを作り出すことができる。受信機はこれらのラベルを安全に保持する必要がある。
【００８９】
［３．平方剰余木を用いたＳＤ方式のラベル数削減構成］
次に、本発明に係る平方剰余木を用いたＳｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式のラベル数の削減構成について説明する。上述したＳｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式を観察すると、以下のことがわかる。
【００９０】
すなわち、ラベルＬＡＢＥＬｉ，ｊは、
（Ａ）受信機に直接、管理センタ（ＴＣ）から与えられる場合と、
（Ｂ）受信機がそれ以外のラベルから擬似乱数生成器Ｇを用いて導出する場合と、
があるが、
ノードｉとノードｊが親子の関係（距離１、すなわち連続する階層にある）であるラベルについては、上記の（Ｂ）の場合は存在せず、すべて、（Ａ）受信機に直接、管理センタ（ＴＣ）から与えられる場合しかありえない。
【００９１】
これは、ある受信機がＬＡＢＥＬｉ，ｊを擬似乱数生成器Ｇを用いて作り出すためには、ノードｊの先祖となるノードｋを用いたＬＡＢＥＬｉ，ｋを知る必要があるが、ノードｉ，ｊが親子関係であるため、ノードｊの先祖であり、ノードｉの子孫となるようなノードｋは存在せず、また、ＬＡＢＥＬｉはどの受信機にも与えられていないためである。
【００９２】
図１０の構成例を参照して説明する。ＬＡＢＥＬ２，８は、受信機ｕ４には直接、管理センタ（ＴＣ）から与えられるが、受信機ｕ５には直接は与えられず、受信機ｕ５は、管理センタ（ＴＣ）から与えられたＬＡＢＥＬ２，４から擬似乱数生成器Ｇを用いてＧＬ（ＬＡＢＥＬ２，４）を計算することによりＬＡＢＥＬ２，８を導出する。
【００９３】
これに対し、図１１に示すように、ノード２とノード５が親子関係になるＬＡＢＥＬ２，５は、サブセットＳ２，５に属している受信機ｕ１，ｕ２，ｕ３，ｕ４には直接与えられ、これ以外の受信機はその集合に属していないため、計算で導出することもできない。すなわち、このようなラベルは受信機に対し直接、管理センタ（ＴＳ）から与えられるだけで、擬似乱数生成器Ｇを用いて導出されることはない。
【００９４】
また、ＳＤ方式において、あるノードｉが異なる２つのノードｊ，ｋの親ノードであり、ノードｊがそれらとは別のノードｎの親ノードであるとき、サブセットＳｊ，ｎに属する受信機は必ずサブセットＳｉ，ｋにも所属することがわかる。
【００９５】
たとえば図１２に示すように、サブセットＳ９，１８に属している受信機Ｕ４は、サブセットＳ４，８、サブセットＳ２，５、サブセットＳ１，３のいずれにも属している。すなわち、
Ｓ９，１８＝｛ｕ４｝
Ｓ４，８＝｛ｕ３，ｕ４｝
Ｓ２，５＝｛ｕ１，ｕ２，ｕ３，ｕ４｝
Ｓ１，３＝｛ｕ１，ｕ２，ｕ３，ｕ４，ｕ５，ｕ６，ｕ７，ｕ８｝
である。
【００９６】
またサブセットＳ４，８に属する受信機ｕ４以外の受信機である受信機ｕ３も、サブセットＳ２，５、サブセットＳ１，３のいずれにも属している。
【００９７】
本発明では、ノードｉとノードｊが親子関係になるラベルＬＡＢＥＬｉ，ｊと、リボークすべき受信機がないという特別な場合に使用する全受信機を含む集合であるサブセットＳ１，φに対応するラベルであるＬＡＢＥＬ１，φに対して、平方剰余木を適用することにより受信機が保持するラベル数を削減する。
【００９８】
上述したＳｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式においては各受信機は、ノードｉとノードｊが親子関係になるラベルＬＡＢＥＬｉ，ｊを、受信機が割り当てられたリーフ（葉）から木の頂点へのパス上の内部ノード１つにつき１つずつ、合計ｌｏｇＮ個保持するため、上記の工夫によりｌｏｇＮ＋１個のラベルを１つに削減できる。
【００９９】
オリジナルのＳＤ方式では、図９を参照して説明したように、受信機ｕ４は計１１個のラベル、すなわち、
ｉ＝１に対してｊ＝３，５，８，１８の４つのラベル
ＬＡＢＥＬ１，３，
ＬＡＢＥＬ１，５，
ＬＡＢＥＬ１，８，
ＬＡＢＥＬ１，１８，
ｉ＝２に対してｊ＝５，８，１８の３つのラベル
ＬＡＢＥＬ２，５，
ＬＡＢＥＬ２，８，
ＬＡＢＥＬ２，１８，
ｉ＝４に対してｊ＝８，１８の２つのラベル
ＬＡＢＥＬ４，８，
ＬＡＢＥＬ４，１８，
ｉ＝９に対してｊ＝１８の１つのラベル
ＬＡＢＥＬ９，１８，
リボークなしの場合用のＬＡＢＥＬを１つ
ＬＡＢＥＬ１，φ，
計１１のラベルを安全に保持する必要があったが、本発明の構成を適用することにより、ノードｉ，ｊが親子関係になるラベル、すなわち、
ＬＡＢＥＬ１，３，
ＬＡＢＥＬ２，５，
ＬＡＢＥＬ４，８，
ＬＡＢＥＬ９，１８，
さらに、リボークなしの場合用のＬＡＢＥＬである
ＬＡＢＥＬ１，φ，
これらのラベルを、ＬＡＢＥＬ９，１８を生成する元となる中間リベル［ＩＬ９，１８］から平方剰余木を用いて計算によって導出可能とし、各受信機に格納する必要のあるラベル数を削減する。
【０１００】
［４．平方剰余木の構成例］
以下、本発明にかかる平方剰余木を用いた階層木構成に基づく情報配信構成について説明する。なお、本明細書の説明において用いている「平方剰余木」とは、一般的な用語ではなく本発明の説明のために用いる言葉である。
【０１０１】
Ｎ個のリーフ（葉）を持つ完全２分木方の階層木が平方剰余木であるとは、ルートを１、それ以降のノードを上位、左から順に、２，３，・・・，２Ｎ−１と幅優先で番号付けした場合に、ノードｉに対応する値ｘｉ（ｉ＝１，２，・・・，２Ｎ−１）のすべてにおいて、
【数５】
2005191805.tif 000006
を満たすことをいう。ここで、ＭＬおよびＭＲはそれぞれ大きな２つの素数の積であり、ＭＬ≠ＭＲである。
【０１０２】
また、
【数６】
2005191805.tif 000007
であるとは、
ｙ２＝ｘｉ（ｍｏｄＭＬ）
なるｙが存在する（すなわち、ｘｉがＭＬに関する平方剰余である）ことをいう。
【０１０３】
奇素数ｐに関してｘが平方剰余か否かを、Ｌｅｇｅｎｄｒｅ記号（ｘ／ｐ）により１（平方剰余）および−１（平方非剰余）で表す。Ｌｅｇｅｎｄｒｅ記号は、
（ｘ／ｐ）＝ｘ（ｐ−１）／２ｍｏｄｐ・・・（式３）
により計算できる。
【０１０４】
２つの奇素数ｐ，ｑの積である合成数Ｍ＝ｐｑに関して、ｘが平方剰余であるためには、
（ｘ／ｐ）＝１、かつ
（ｘ／ｑ）＝１
であることが必要十分である。
【０１０５】
平方剰余を利用した暗号の代表的なものに、Ｒａｂｉｎ暗号がある。Ｒａｂｉｎ暗号は、２つの大きな素数ｐ，ｑを秘密鍵とし、その積Ｍ＝ｐｑを公開鍵とする公開鍵暗号である。メッセージｍ∈ＺＭの暗号化は、
ｃ＝ｍ２ｍｏｄＭ・・・（式４）
により行われる。
【０１０６】
秘密鍵ｐ，ｑを知る者は、下記のように暗号文ｃを復号することができる。すなわち、
ｍｐ＝ｃ１／２ｍｏｄｐ・・・（式５）
ｍｑ＝ｃ１／２ｍｏｄｑ・・・（式６）
を計算し、（ｍｐ，ｍｑ），（ｍｐ，−ｍｑ），（−ｍｐ，ｍｑ），（−ｍｐ，−ｍｑ）を中国人剰余定理により合成し、上記式（式４）を満たす４つの値ｍ１，ｍ２，ｍ３，ｍ４を求める。このうちの１つがｍであり、Ｒａｂｉｎ暗号では何らかの付加的情報によりｍを選択する。
【０１０７】
なお、一般的に式（５）を計算するためのアルゴリズムは、ＢｅｒｌｅｋａｍｐのアルゴリズムやＲａｂｉｎのアルゴリズムなどが知られているが、素数ｐ，ｑとして、
【数７】
2005191805.tif 000008
であるものを用いると、ｍｐは、
ｍｐ＝ｃ（ｐ＋１）／４ｍｏｄｐ・・・（式７）
により計算することができる。
【０１０８】
さて、リーフ（葉）がＮ個である２分木の平方剰余木を構成するアルゴリズムの例を下記に示す。このアルゴリズムの入力はリーフ（葉）の数Ｎであり、出力は２つの合成数ＭＬ、ＭＲと２Ｎ−１個の数ｘ１，ｘ２，・・・，ｘ２Ｎ−１である。
【０１０９】
［ステップ１］
４つの大きな素数ｐＬ，ｑＬ，ｐＲ，ｑＲを選択し、ＭＬ＝ｐＬｑＬ，ＭＲ＝ｐＲｑＲを定める。
［ステップ２］
ルートに対応する値ｘ１をランダムに選び、それが上記式（式１）を満たすかどうかを判定する。満たさなければ別の値をランダムに選んでｘ１とし、条件を満たすまで繰り返す。
［ステップ３］
ノードｉに対応する値ｘｉをＲａｂｉｎ暗号文の暗号文とみなし、法ＭＬを用いて復号したときの４つの候補のいずれかを、ノードｉの左の子ノード２ｉに対応する値ｘ２ｉとし、また同様に法ＭＲを用いて復号したときの候補のいずれかをノードｉの右の子ノード２ｉ＋１に対応する値ｘ２ｉ＋１とする。
【０１１０】
［ステップ４］
ステップ３で定めた値ｘ２ｉおよびｘ２ｉ＋１が上記式（式１）を満たすかどうか、上記のＬｅｇｅｎｄｒｅ記号を用いて調べる。満たさないときは、４つの候補のうち別のものを用いて検査を繰り返す。
［ステップ５］
もしも、あるノードｉの左の子ノードに対応する値ｘ２ｉの４つの候補のいずれもが上記式（式１）を満たさない場合、または、右の子ノードに対応する値ｘ２ｉ＋１の４つの候補のいずれもが（式１）を満たさない場合には、ノードｉに対応する値ｘｉに別の候補の値を用いてやり直す。ｘｉの４つの候補もすべて使いきってしまった場合には、その親ノードに対応する値に別の候補の値を用いてやり直す。このようにしてやり直しが続き、ルートの子ノードの候補をすべて使い切ってしまった場合には、ルートに対応する値ｘｉをランダムに選び、ステップ１に戻り、再度やり直す。
【０１１１】
［ステップ６］
ｉを増加させていき、最終的に２Ｎ−１個のノードに対し、条件を満たす値を割り当てられたら、それらの値とＭＬ，ＭＲを出力して終了する。すなわち、ｘ１からｘ２Ｎ−１まで、条件を満たす値を作れたら、それらｘ１からｘ２Ｎ−１の値と２つの合成数ＭＬ，ＭＲを出力して終了する。ここで、リーフ（葉）の数がＮである完全２分木のノードの総数は２Ｎ−１である点に注意されたい。
【０１１２】
Ｎ＝１６のときに、ｘ１からｘ３１の値を順に生成する手順を示す図を図１３に示す。図１３に示すように、ｘ１からｘ３１の値は、ルートから下層に向かい左から幅優先で割り当てられる値となり、まず、ルートに対応する値ｘ１を算出する。これは、上記［ステップ１］、［ステップ２］の処理として実行される。この結果、ｘ１は、（式１）を満足する値として設定される。
【０１１３】
さらに、上記［ステップ３］の処理によって、ｘ２とｘ３を算出する。さらに、［ステップ４］において、ｘ２とｘ３が（式１）を満足するか否かを検証し、満足しない場合は、［ステップ５］において［ステップ１］に戻って再試行する。最終的にｘ２とｘ３を（式１）を満足する値として設定する。
【０１１４】
以下、同様に、上位ノードの値に基づいて、下位ノードの２つの値を算出する処理を実行し、ｘ１からｘ３１の値をすべて（式１）を満足する値として設定する。
【０１１５】
［５．平方剰余木を適用した情報配信処理例］
次に、上述した平方剰余木を適用した情報配信処理例について説明する。以下、
（５−１）セットアップ処理
（５−２）情報配信処理
（５−３）受信および復号処理
の各処理について順次、説明する。
【０１１６】
（５−１）セットアップ処理
セットアップ処理はシステムの立ち上げ時に１度だけ行う。これ以降の情報配信および受信と復号の処理は、送信すべき情報が生じる毎に実行する。たとえば新しいコンテンツを格納したＤＶＤディスクなどのコンテンツ格納記録媒体が作成され、ユーザに対して配布される毎、あるいはインターネットを介して暗号化コンテンツが配信される毎に繰り返し行う。
【０１１７】
セットアップ処理は、以下のステップ１〜４の処理によって実行する。各ステップについて説明する。
【０１１８】
ａ．ステップ１
まず、管理センタ（ＴＣ）は、２分木でありＮ個のリーフ（葉）を持つ階層木を定義する。階層木中の各ノードに対応する識別子として、ｋ（ｋ＝１，２，・・・，２Ｎ−１）を設定する。ただしルートを１とし、以下、下層ノードについて順次、幅優先（ｂｒｅａｄｔｈ  ｆｉｒｓｔ  ｏｒｄｅｒ）で、識別子（番号）付与を行う。
【０１１９】
次に、受信機ｕｍ（ｍ＝１，２，・・・，Ｎ）を階層木の各リーフ（葉）に割り当てる。また、各内部ノードｉ（ｉ＝１，２，・・・，Ｎ−１）について、ノードｉの子孫であるノードｊに対応するサブセットＳｉ，ｊを定義する。さらに、上で定義されたすべてのサブセットＳｉ，ｊの中で、ノードｉとノードｊが親子関係になっているものを第１の特別なサブセット（スペシャルサブセット：Ｓｐｅｃｉａｌ  Ｓｕｂｓｅｔ）ＳＳｉ，ｊと表すことにする。ここで、木のルートを除く各ノードは、それぞれ唯一の親ノードを持つので、ＳＳｉ，ｊのｊには、ｊ＝２，３，・・・，２Ｎ−１なるｊがただ１度ずつ使用されることに注意されたい。さらに、リボークする受信機がひとつもない場合に使用する、全受信機を含む第２の特別なサブセットＳＳ'１，φを定義する。
【０１２０】
また、Ｃビット出力のハッシュ関数Ｈと擬似乱数生成器Ｇを選択して公開する。ハッシュ関数Ｈは、任意長の入力に対してあらかじめ定められた長さの出力を出す関数である。たとえば１２８ビット出力のハッシュ関数としてはＭＤ５が、１６０ビット出力のハッシュ関数としてはＳＨＡ−１がよく知られている。なお、ＭＤ５については、Ａ．Ｊ．Ｍｅｎｅｚｅｓ，Ｐ．Ｃ．ｖａｎ  Ｏｏｒｓｃｈｏｔ  ａｎｄ  Ｓ．Ａ．Ｖａｎｓｔｏｎｅ著，Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ，ＣＲＣ  Ｐｒｅｓｓ，１９７７のｐ．３４７に、またＳＨＡ−１については、同書のｐ．３４８にアルゴリズムが紹介されている。また、擬似乱数生成器Ｇは、Ｃビットの入力に対し３Ｃビットの擬似乱数を出力するもので、ＳＤ方式を提案したＮａｏｒらの論文で使われているものと同じものである。
【０１２１】
ｂ．ステップ２
管理センタ（ＴＣ）は、前述の［４．平方剰余木の構成例］で述べた方法を用いて、２つの合成数ＭＬおよびＭＲと、Ｎ個のリーフ（葉）を持つ２分木の平方剰余木を作成する。すなわち、合成数ＭＬおよびＭＲと、ノード１から２Ｎ−１に対応する値ｘ１からｘ２Ｎ−１を定める。また、この平方剰余木に関連して２つの関数ＦＬおよびＦＲを定め、これらの関数を公開する。ここで、
ＦＬ（ｘ）＝ｘ２ｍｏｄＭＬ・・・（式８）
ＦＲ（ｘ）＝ｘ２ｍｏｄＭＲ・・・（式９）
である。
【０１２２】
管理センタ（ＴＣ）は、上述の処理において定めた値ｘ１を、リボークする受信機がひとつもない場合に使用する全受信機を含む第２の特別なサブセットＳＳ'１，φのラベルの生成元データとしての中間ラベル（Ｉｎｔｅｒｍｅｄｉａｔｅ  Ｌａｂｅｌ，ＩＬ）として設定する。すなわち、
ＩＬ１，φ＝ｘ１
とする。
【０１２３】
第２の特別なサブセットＳＳ'１，φのラベルをＬＡＢＥＬ１，φとし、ＬＡＢＥＬ１，φは、上記の中間ラベルＩＬ１，φに対するハッシュ（Ｈ）によって算出する値とする。すなわち、
ＬＡＢＥＬ１，φ＝Ｈ（ＩＬ１，φ）
である。
【０１２４】
さらに、すべてのサブセットＳｉ，ｊの中で、ノードｉとノードｊが親子関係になっている第１の特別なサブセットＳＳｉ，ｊ（ただし、上述のようにｊ＝２，３，・・・，２Ｎ−１である）に対応するラベルの生成元データとしての中間ラベルＩＬｉ，ｊを下記のように定める。すなわち、前述の処理によってノード１から２Ｎ−１に対応する値として設定したｘ１からｘ２Ｎ−１の中のルート対応値ｘ１を除くｘｙ（ｙ＝２，３，・・・，２Ｎ−１）をノードｙの兄弟ノードと親ノードで指定される第１の特別なサブセットＳＳＰ（ｙ），Ｓ（ｙ）に対応する中間ラベルＩＬＰ（ｙ），Ｓ（ｙ）とする。すなわち、
ｘｙ＝ＩＬＰ（ｙ），Ｓ（ｙ）
とする。
なお、Ｐ（ｉ）はノードｉの親ノードであり、Ｓ（ｉ）はノードｉの兄弟ノードである。
【０１２５】
図１４に具体的な例を示す。図１４において、ノードｙ３０１にはノード対応値としてのｘｙが割り当てられる。なお、ｘｙを含むすべてのノード対応値は前述の式（式１）を満足する値であり、
ｘｙ＝ＩＬＰ（ｙ），Ｓ（ｙ）
である。
【０１２６】
ノードｙ３０１の親ノードは、Ｐ（ｙ）３０２であり、兄弟ノードはＳ（ｙ）３０３である。ノードｙ３０１の兄弟ノードＳ（ｙ）３０３と親ノードＰ（ｙ）３０２で指定される第１の特別なサブセットＳＳＰ（ｙ），Ｓ（ｙ）は、図１４に示すサブセットＳＳＰ（ｙ），Ｓ（ｙ）３１０である。
【０１２７】
このとき、サブセットＳＳＰ（ｙ），Ｓ（ｙ）３１０に対応するラベルは、ＬＡＢＥＬＰ（ｙ），Ｓ（ｙ）となるが、
ＬＡＢＥＬＰ（ｙ），Ｓ（ｙ）を、中間ラベルＩＬＰ（ｙ），Ｓ（ｙ）（これはノードｙ３０１のノード対応値ｘｙに等しい）に基づくハッシュ値として設定する。すなわち、
ＬＡＢＥＬＰ（ｙ），Ｓ（ｙ）＝Ｈ（ＩＬＰ（ｙ），Ｓ（ｙ））
である。
上記式は、
ＬＡＢＥＬＰ（ｙ），Ｓ（ｙ）＝Ｈ（ｘｙ）
と等価である。
【０１２８】
一般式として示すと、すべてのサブセットＳｉ，ｊの中で、ノードｉとノードｊが親子関係になっている第１の特別なサブセットＳＳｉ，ｊ（ただし、上述のようにｊ＝２，３，・・・，２Ｎ−１である）に対応するラベルＬＡＢＥＬｉ，ｊは、中間ラベルＩＬｉ，ｊに基づくハッシュ値、すなわち、
ＬＡＢＥＬｉ，ｊ＝Ｈ（ＩＬｉ，ｊ）
として算出する。
【０１２９】
なお、前述したように、リボークする受信機がひとつもない場合に使用する全受信機を含む第２の特別なサブセットＳＳ'１，φのラベルＬＡＢＥＬ１，φについても中間ラベルＩＬ１，φに対するハッシュ（Ｈ）によって算出可能、すなわち、
ＬＡＢＥＬ１，φ＝Ｈ（ＩＬ１，φ）
である。
【０１３０】
なお、本例では、中間ラベルに基づくラベルの算出処理にハッシュを適用した例を説明しているが、ハッシュ以外の演算処理によって算出する構成としてもよい。ただし、一方向性関数であることが望ましい。
【０１３１】
管理センタは、ステップ２において、
（ａ）リボークする受信機がひとつもない場合に使用する全受信機を含む全体木に対応する第２の特別なサブセットＳＳ'１，φのラベルＬＡＢＥＬ１，φと、
（ｂ）ノードｉとノードｊが親子関係になっている第１の特別なサブセットＳＳｉ，ｊ（ただし、上述のようにｊ＝２，３，・・・，２Ｎ−１である）に対応するラベルＬＡＢＥＬｉ，ｊと、
上記（ａ），（ｂ）の特別なサブセット対応のラベルを、それぞれ
中間ラベルＩＬｉ，φのハッシュ値、
中間ラベルＩＬｉ，ｊのハッシュ値
として設定する処理を実行する。
【０１３２】
なお、なお中間ラベルの値は、ノード対応値ｘｉの値であり、前記の式（式１）を満足する値である。すなわち、
ＩＬ１，φ＝ｘ１
また、ｙ＝１，２，・・・，Ｎ−１に対して、
ＩＬｙ，２ｙ＝ｘ２ｙ＋１
ＩＬｙ，２ｙ＋１＝ｘ２ｙ
となる。
【０１３３】
図１５に、（ａ）リボークする受信機がひとつもない場合に使用する全受信機を含む全体木に対応する第２の特別なサブセットＳＳ'１，φのラベルＬＡＢＥＬ１，φと、（ｂ）ノードｉとノードｊが親子関係になっている第１の特別なサブセットＳＳｉ，ｊ（ただし、上述のようにｊ＝２，３，・・・，２Ｎ−１である）に対応するラベルＬＡＢＥＬｉ，ｊとの生成元データである中間ラベル（ＩＬ）の設定処理例を示す。これらの中間ラベルはすべて、図１５に示すように各ノードの対応値を適用して設定される。
【０１３４】
管理センタ（ＴＣ）は、設定した中間ラベルに基づいて、ハッシュ値を算出し、（ａ）リボークする受信機がひとつもない場合に使用する全受信機を含む第２の特別なサブセットＳＳ'１，φのラベルＬＡＢＥＬ１，φと、（ｂ）ノードｉとノードｊが親子関係になっている第１の特別なサブセットＳＳｉ，ｊ（ただし、上述のようにｊ＝２，３，・・・，２Ｎ−１である）に対応するラベルＬＡＢＥＬｉ，ｊを決定する。
【０１３５】
図１６に、先に説明した図１４に対応する具体例を示す。ノードｙ３０１を図に示すように、ノード番号８であるとする。ノードｙ３０１にはノード対応値としてのｘ８が割り当てられる。ノードｙ３０１の親ノードは、Ｐ（ｙ）３０２でありノード番号４、兄弟ノードＳ（ｙ）３０３のノード番号は９である。ノードｙ３０１の兄弟ノードＳ（ｙ）３０３と親ノードＰ（ｙ）３０２で指定される第１の特別なサブセットＳＳＰ（ｙ），Ｓ（ｙ）は、図１６に示すサブセットＳＳ４，９３１０である。このとき、ＳＳ４，９３１０に対応するラベルの生成元データとしての中間ラベルは、
ｘ８＝ＩＬＰ（ｙ），Ｓ（ｙ）
＝ＩＬ４，９
である。
【０１３６】
サブセットＳＳ４，９３１０に対応するラベルは、ＬＡＢＥＬ４，９であり、ＬＡＢＥＬ４，９を、中間ラベルＩＬ４，９（これはノードｙ３０１のノード対応値ｘ８に等しい）に基づくハッシュ値として設定する。すなわち、
ＬＡＢＥＬ４，９＝Ｈ（ＩＬ４，９）
である。
上記式は、
ＬＡＢＥＬ４，９＝Ｈ（ｘ８）
と等価である。
【０１３７】
管理センタは、上述したように、ステップ２において、
（ａ）リボークする受信機がひとつもない場合に使用する全受信機を含む全体木に対応する第２の特別なサブセットＳＳ'１，φのラベルＬＡＢＥＬ１，φと、
（ｂ）ノードｉとノードｊが親子関係になっている第１の特別なサブセットＳＳｉ，ｊ（ただし、上述のようにｊ＝２，３，・・・，２Ｎ−１である）に対応するラベルＬＡＢＥＬｉ，ｊと、
を決定する。各ラベルは、ノード対応値に等しい中間ラベルのハッシュ値によって算出する。
【０１３８】
ｃ．ステップ３
次に、管理センタ（ＴＣ）は、ノードｉとノードｊが親子関係になっている第１の特別なサブセットＳＳｉ，ｊのラベルＬＡＢＥＬｉ，ｊを擬似乱数生成器Ｇに入力し、ノードｉを始点とした、ノードｊの子ノードのラベルＬＡＢＥＬｉ，ＬＣ（ｊ）と、ＬＡＢＥＬｉ，ＲＣ（ｊ）を求める。
【０１３９】
すなわち、ビット数ＣのＬＡＢＥＬｉ，ｊを擬似乱数生成器Ｇに入力して得られる３Ｃビットの擬似乱数の上位ＣビットであるＧＬ（ＬＡＢＥＬｉ，ｊ）を、ノードｉを始点とした、ノードｊの左の子ノードＬＣ（ｊ）に対応する（特別でない）サブセットＳｉ，ＬＣ（ｊ）のラベルＬＡＢＥＬｉ，ＬＣ（ｊ）として設定し、さらに、ビット数ＣのＬＡＢＥＬｉ，ｊを擬似乱数生成器Ｇに入力して得られる３Ｃビットの擬似乱数の下位ＣビットであるＧＲ（ＬＡＢＥＬｉ，ｊ）を、ノードｉを始点とした、ノードｊの右の子ノードＲＣ（ｊ）に対応する（特別でない）サブセットＳｉ，ＲＣ（ｊ）のラベルＬＡＢＥＬｉ，ＲＣ（ｊ）として設定する。すなわち、
ＬＡＢＥＬｉ，ＬＣ（ｊ）＝ＧＬ（ＬＡＢＥＬｉ，ｊ）
ＬＡＢＥＬｉ，ＲＣ（ｊ）＝ＧＲ（ＬＡＢＥＬｉ，ｊ）
として、各ラベルを設定する。
【０１４０】
さらにこれらの出力（ラベル）を擬似乱数生成器Ｇに繰り返し入力することで、ノードｉを始点とした、ノードｊの子孫であるすべてのノードに対応するラベルを求める。これをすべての特別なサブセットＳＳｉ，ｊのラベルに対して行い、ステップ１で定義したすべてのサブセットＳｉ，ｊのラベルを求める。
【０１４１】
ｄ．ステップ４
次に管理センタ（ＴＣ）は、受信機ｕｍに対し、オリジナルのＳＤ方式において与えるラベルを選択する。これは、受信機ｕｍが割り当てられたリーフ（葉）からルートに至るパスｐａｔｈｍ上の内部ノードｉを始点とし、このリーフ（葉）からｉまでのパスから直接枝分かれしたノードｊに対応するサブセットＳｉ，ｊのラベルＬＡＢＥＬｉ，ｊと、上記の第２の特別なサブセットＳＳ'１，φに対応するラベルＬＡＢＥＬ１，φである。
【０１４２】
図１７を参照して受信機に提供するラベルの種類について説明する。例えば、図１７のノード番号１９に対応する受信機ｕ４に対する仮選択ラベルとして、
ＬＡＢＥＬ１，３、ＬＡＢＥＬ１，５、ＬＡＢＥＬ１，８、ＬＡＢＥＬ１，１８、ＬＡＢＥＬ２，５、ＬＡＢＥＬ２，８、ＬＡＢＥＬ２，１８、ＬＡＢＥＬ４，８、ＬＡＢＥＬ４，１８、ＬＡＢＥＬ９，１８、ＬＡＢＥＬ１，φの１１個のラベルが選択される。
【０１４３】
次に、これらの仮選択ラベルのうち、前述した第１および第２の特別なサブセットに対応するものを除外したラベルを受信機ｕ４に対する最終選択ラベルすなわち提供ラベルとする。
【０１４４】
さらに、管理センタ（ＴＣ）は、受信機に、その受信機が割り当てられているリーフ（葉）ｊの親ノードＰ（ｊ）を始点とし、ｊの兄弟ノードＳ（ｊ）に対応する特別なサブセットＳＳＰ（ｊ），Ｓ（ｊ）の中間ラベルＩＬＰ（ｊ），Ｓ（ｊ）を与える。上記の例では、管理センタ（ＴＣ）は、は受信機ｕ４に、ＩＬ９，１８を与える。受信機は与えられたラベルと中間ラベルを
安全に保管する。
【０１４５】
すなわち、まず、受信機ｕ４が持つ必要のあるラベル（ＬＡＢＥＬ）として、ＬＡＢＥＬｉ，ｊのｉ，ｊの組を以下のものとしたラベルを仮選択ラベルとする。
ｉ＝１に対してｊ＝３，５，８，１８
ｉ＝２に対してｊ＝５，８，１８
ｉ＝４に対してｊ＝８，１８
ｉ＝９に対してｊ＝１８
リボークなしの場合用のＬＡＢＥＬを１つ
【０１４６】
次に、上記の１１個の仮選択ラベルから、前述した第１および第２の特別なサブセットに対応するものを除外したラベルと、１つの中間ラベルを受信機ｕ４に対する最終選択ラベルすなわち提供ラベルとする。すなわち、ＬＡＢＥＬｉ，ｊのｉ，ｊの組を以下のものとしたラベルを提供ラベルとする。
ｉ＝１に対してｊ＝５，８，１８
ｉ＝２に対してｊ＝８，１８
ｉ＝４に対してｊ＝１８
中間ラベルＩＬ９，１８
以上、６つのラベルと１つの中間ラベルを提供ラベルとする。
【０１４７】
なお、受信機ｕｍに対する提供ラベルとして設定される１つの中間ラベルは、階層木において、受信機ｕｍに最も近い祖先によって定義される第１の特別なサブセット、すなわち、ノードｉとノードｊが親子関係になっている第１の特別なサブセットＳＳｉ，ｊ（ただし、上述のようにｊ＝２，３，・・・，２Ｎ−１である）に対応する中間ラベルＩＬｉ，ｊとなる。すなわち、階層木のリーフ（葉）対応の受信機に提供する１つの中間ラベルは、前述の第１特別サブセットを構成するサブセットＳｉ，ｊ中、最下層の特別サブセットに対応する中間ラベルである。
【０１４８】
図１８に、上記のセットアップで、管理センタ（ＴＣ）が行う処理のフローを示す。まず、ステップＳ１０１において、階層木（ＨＫＴ）の構成を定義する。ステップＳ１０２において、設定した階層木に対応してサブセットの定義を行なう。サブセット定義は、必ずしも全てのリーフを個別にリボーク可能とする設定に限らず、配信情報に応じて、例えば特定のリーフの集合をまとめてリボーク単位としたサブセットなど、任意の設定が可能である。
【０１４９】
次に、ステップＳ１０３において、２つの合成数ＭＬ，ＭＲを作成し、平方剰余木を作成する。この処理は、前述の［４．平方剰余木の構成例］の項目において説明した処理であり、４つの大きな素数ｐＬ，ｑＬ，ｐＲ，ｑＲを選択し、ＭＬ＝ｐＬｑＬ，ＭＲ＝ｐＲｑＲを定め、さらに、各ノードに対応するノード対応値ｘｉを対応付ける処理として実行する。ノード対応値ｘｉは、前述の式（式１）を満足するとして設定される。
【０１５０】
次にステップＳ１０４において、２つの合成数ＭＬ，ＭＲを公開するとともに、平方剰余木に関連する２つの関数ＦＬおよびＦＲを定め、これらの関数を公開する。
ＦＬ（ｘ）＝ｘ２ｍｏｄＭＬ
ＦＲ（ｘ）＝ｘ２ｍｏｄＭＲ
である。
【０１５１】
次に、ステップＳ１０５において、擬似乱数生成関数Ｇと、ハッシュ関数Ｈを公開する。ステップＳ１０６において、中間ラベルＩＬｉ，ｊを、平方剰余木の各ノードに対応して設定したノード対応値ｘｉに基づいて導出する。
【０１５２】
なお、ここで求める中間ラベルは、
（ａ）リボークする受信機がひとつもない場合に使用する全受信機を含む第２の特別なサブセットＳＳ'１，φと、
（ｂ）ノードｉとノードｊが親子関係になっている第１の特別なサブセットＳＳｉ，ｊ（ただし、上述のようにｊ＝２，３，・・・，２Ｎ−１である）と、
に対応する中間ラベルである。
【０１５３】
次に、ステップＳ１０７において、ステップＳ１０６で導出した中間ラベルＩＬｉ，ｊのハッシュにより、一部のラベルＬＡＢＥＬｉ，ｊを導出し、さらに、導出した一部のラベルＬＡＢＥＬｉ，ｊに基づく擬似乱数生成関数Ｇの適用によって、ステップＳ１０２において設定したサブセットに対応するすべてのラベルＬＡＢＥＬｉ，ｊを導出する。
【０１５４】
次にステップＳ１０８において、階層木のリーフに対応して設定される各受信機へ提供するラベルを選択する。この処理は、前述したように仮選択ラベルの選択と提供ラベルの選択の２段階処理として実行される。
【０１５５】
すなわち、まず、受信機ｕｍが持つ必要のあるラベル（ＬＡＢＥＬ）として，オリジナルのＳＤ方式において与えるラベル、すなわち受信機ｕｍが割り当てられたリーフ（葉）からルートに至るパスｐａｔｈｍ上の内部ノードｉを始点とし、このリーフ（葉）からｉまでのパスから直接枝分かれしたノードｊに対応するサブセットＳｉ，ｊのラベルＬＡＢＥＬｉ，ｊと、上記の第２の特別なサブセットＳＳ'１，φに対応するラベルＬＡＢＥＬ１，φを仮選択ラベルとして選択する。その後、仮選択ラベルから、前述した第１および第２の特別なサブセットに対応するものを除外したラベルＬＡＢＥＬｉ，ｊと、１つの中間ラベルが提供ラベルとして設定される。
【０１５６】
なお、提供ラベルとして設定される１つの中間ラベルは、階層木において、受信機ｕｍが割り当てられた葉ｎの親ノードと兄弟ノードによって定義される第１の特別なサブセット、すなわち、ノードｉが葉ｎの親ノードであり，ノードｊが葉ｎの兄弟ノードであるような第１の特別なサブセットＳＳｉ，ｊ（ただし、ｊは葉であるためｊ＝Ｎ，Ｎ＋１，・・・，２Ｎ−１である）に対応する中間ラベルＩＬｉ，ｊとなる。例えば、図１７に示すノード番号１９の設定された受信機ｕ４に対して提供する中間ラベルは、中間ラベルＩＬ９，１８となる。
【０１５７】
ステップＳ１０９において、ステップＳ１０８で決定した受信機に対する提供ラベルを受信機に提供し、処理を終了する。なお、ラベルの提供は、予め受信機の製造時に耐タンパ方のメモリに格納するか、あるいは、情報漏れの発生しないセキュアな通信路、あるいは媒体などの手段を適用して行なう。なお、図１８に示す処理フローの各ステップは、必ずしもこの順番である必要はない。
【０１５８】
（５−２）情報配信処理
次に、上述のセットアップ処理後に実行する秘密情報の送信処理の詳細について説明する。情報配信、すなわち秘密情報の送信は、管理センタ（ＴＣ）が１つ以上の暗号文を同報送信することによってなされる。それぞれの暗号文は、秘密情報をサブセットキーの１つを用いて暗号化したものである。例えば、管理センタが送信する秘密情報は、同じ送信秘密情報を異なるサブセットキーを用いて暗号化した複数の暗号文のセットとして構成される。
【０１５９】
例えば秘密情報を暗号化コンテンツの複合に適用する鍵：コンテンツキーＫｃとした場合、コナテンツキーＫｃを複数のサブセットキーで暗号化した暗号文のセットを生成して提供する。例えば、
Ｅ（ＳＫａ，ｂ，Ｋｃ），Ｅ（ＳＫｃ，ｄ，Ｋｃ），Ｅ（ＳＫｅ，ｆ，Ｋｃ）
の暗号文を生成して、ネットワーク配信あるいは記録媒体に格納して提供する。なお、Ｅ（Ａ，Ｂ）はデータＢを鍵Ａで暗号化したデータを意味する。上記例は３つの異なるサブセットキーを適用して暗号化した３つの暗号文からなる暗号文セットである。
【０１６０】
サブセットキーＳＫａ，ｂ、サブセットキーＳＫｃ，ｄ、サブセットキーＳＫｅ，ｆのそれぞれは、特定の機器をリボーク機器として設定するために管理センタ（ＴＣ）において選択されたサブセットに対応するサブセットキーである。
【０１６１】
リボーク対象以外の受信機が、暗号文の暗号化に適用されたサブセットキーのいずれかを、受信機の保有するラベル（ラベルおよび中間ラベル）に基づいて生成可能であり、リボーク機器以外の正当な選択された受信機のみが、
Ｅ（ＳＫａ，ｂ，Ｋｃ），Ｅ（ＳＫｃ，ｄ，Ｋｃ），Ｅ（ＳＫｅ，ｆ，Ｋｃ）
に含まれるいずれかの暗号文の復号によってコンテンツキーＫｃを取得することができる。
【０１６２】
図１９に総受信機数Ｎ＝１６に設定した階層木構成において、受信機ｕ２，ｕ１１，ｕ１２をリボークする際に用いるサブセットを示す。受信機ｕ２，ｕ１１，ｕ１２をリボークする際に用いるサブセットは、図１９に示す２つのサブセットＳ２，１７とＳ３，１３である。
【０１６３】
リボークされない受信機は２つのサブセットＳ２，１７とＳ３，１３のいずれかに含まれ、リボークされる受信機ｕ２，ｕ１１，ｕ１２はそのいずれにも含まれないので、これらのサブセットに対応するサブセットキーＳＫ２，１７とＳＫ３，１３を用いて秘密情報を暗号化して送信すれば、リボークされない受信機のみが暗号文を復号して秘密情報を得ることができる。
【０１６４】
情報配信処理の処理手順について、図２０に示すフローを参照して説明する。図２０に示すフロー中の各ステップについて説明する。
【０１６５】
まず管理センタ（ＴＣ）は、ステップＳ２０１において、リボーク受信機、すなわち送信秘密情報の提供対象外とする排除機器を選択する。なお、すべての受信機は、階層木構成のリーフに対応して設定されている。
【０１６６】
次にステップＳ２０２において、決定したリボーク受信機に対応する階層木のリーフ位置に基づいて、秘密情報の配信名の際に適用するサブセットを決定する。例えば図１９の例では、リボーク受信機として受信機ｕ２，ｕ１１，ｕ１２を選択しており、適用するサブセットは２つのサブセットＳ２，１７とＳ３,１３となる。
【０１６７】
ステップＳ２０３において、決定したサブセットに対応するサブセットキーを選択する。管理センタ（ＴＣ）は、予めサブセットに対応するサブセットキーを保持している。例えば図１９の例では、２つのサブセットＳ２，１７とＳ３,１３とに対応する２つのサブセットキーＳＫ２，１７とＳＫ３,１３とが選択される。
【０１６８】
次に、ステップＳ２０４において、ステップＳ２０３で選択したサブセットキーを用いて秘密情報を暗号化して暗号文セットを生成する。例えば図１９の例では、２つのサブセットキーＳＫ２，１７とＳＫ３,１３を用いて秘密情報を暗号化して暗号文セットを生成する。例えば図１９の例では、２つのサブセットキーＳＫ２，１７とＳＫ３,１３とを用いて秘密情報（例えばコンテンツキーＫｃ）を暗号化して、以下の暗号文セット、
Ｅ（ＳＫ２，１７，Ｋｃ），Ｅ（ＳＫ３，１３，Ｋｃ）
を生成する。
【０１６９】
ステップＳ２０５では、ステップＳ２０４において生成した暗号文セットを受信機に向けて送信（同報送信）する。送信される暗号文セットは、リボーク機器以外の受信機においてのみ復号可能な暗号文のみから構成され、リボーク機器においては復号できず、安全な情報配信が可能となる。
【０１７０】
なお、暗号文セットの送信に際しては、暗号文に含まれる各サブセット対応の暗号文の配列情報としてのサブセット指定情報を併せて送信してもよい。受信機は、この指定情報に基づいて、自装置で生成可能なサブセットキーを適用した暗号文を容易に抽出可能となる。この具体手な方式としては、例えば、特開２００１−３５２３２２号公報に示されている鍵指定コードを利用する構成が適用可能である。
【０１７１】
なお、暗号化に利用するサブセットキーは、管理センタ（ＴＣ）がセットアップフェイズにおいて作成して保管しておいたものを使用するようにしてもよいし、セットアップフェイズにおいて作成して保管しておいた各サブセットごとのラベルから擬似乱数生成器Ｇを用いて導出してもよい。なお、リボークする受信機がない場合には、前述の第２の特別なサブセットＳＳ'１，φのサブセットキーＳＫ１，φを用いて秘密情報の暗号化に用いる。
【０１７２】
（５−３）受信および復号処理
リボークされない受信機は、上記のサブセットのいずれかただ１つに属しているので、そのサブセットに対応するサブセットキーを用いて作られた暗号文を復号すれば秘密情報を得ることができる。受信機が復号すべき暗号文を見つけるためには、前述のサブセット指定情報を用いればよい。暗号文を特定した後、受信機は所有するラベルまたは中間ラベルからサブセットキーを導出し、これを用いて暗号文を復号する。サブセットキーを導出する方法を以下に述べる。
【０１７３】
受信機ｕｍはまず、暗号文の復号処理に適用する求めるべきサブセットキーＳＫｉ，ｊに対応するサブセットＳｉ，ｊのノードｊが、
（Ａ）受信機が直接ラベルＬＡＢＥＬｉ，ｋを持つノードｋの子孫である（ただしｊ＝ｋの場合を含む）か、
（Ｂ）ノードｉの子ノードのうち、受信機が割り当てられたリーフ（葉）ｎからルートへのパス上にないほうのノード（つまり、パス上にあるノードｉの子ノードの兄弟であるノード）ｋと一致するかその子孫であるか（すなわち、ノードｊが、ＳＤ方式において受信機ｕｍにラベルが与えられたサブセットのうち、第１の特別なサブセットＳＳｉ，ｋを構成するノードｋの子孫であるか）
を判断する。なお、リボークする受信機がなく、第２の特別なサブセットＳＳ'１，φのサブセットキーＳＫ１，φが秘密情報の暗号化に用いられている場合には、（Ｂ）であるとみなす。
【０１７４】
（Ｂ）の場合には、下記のように、受信機に与えられている中間ラベルＩＬＰ（ｎ），Ｓ（ｎ）から第１の特別なサブセットＳＳｉ，ｋの中間ラベルを導出する。
【０１７５】
まず、ｉ＝Ｐ（ｎ），ｊ＝ｋ＝Ｓ（ｎ）である場合には、受信機はすでにこの中間ラベルを持っているので特に何もする必要はない。そうでない場合は、受信機は中間ラベルＩＬＰ（ｎ），Ｓ（ｎ）に対し公開されている関数ＦＬまたはＦＲを適用することで、上位のサブセットに対応する中間ラベルを順次計算していく。受信機が持つ中間ラベルＩＬＰ（ｎ），Ｓ（ｎ）に対し、受信機が割り当てられたリーフ（葉）ｎが親ノードＰ（ｎ）の左側の子ノードであるとき、すなわちｎ＝ＬＣ（Ｐ（ｎ））であるとき、ノードＰ（ｎ）の親ノードＰ（Ｐ（ｎ））を始点とし、ノードＰ（ｎ）の兄弟ノードＳ（Ｐ（ｎ））に対応する特別なサブセットＳＳＰ（Ｐ（ｎ）），Ｓ（Ｐ（ｎ））の中間ラベルＩＬＰ（Ｐ（ｎ）），Ｓ（Ｐ（ｎ））は、
ＩＬＰ（Ｐ（ｎ）），Ｓ（Ｐ（ｎ））＝ＦＬ（ＩＬＰ（ｎ），Ｓ（ｎ））
によって求められる。
【０１７６】
逆に、リーフ（葉）ｎが親ノードＰ（ｎ）の右側の子ノードであるとき、すなわちｎ＝ＲＣ（Ｐ（ｎ））であるとき、ノードＰ（ｎ）の親ノードＰ（Ｐ（ｎ））を始点とし、ノードＰ（ｎ）の兄弟ノードＳ（Ｐ（ｎ））に対応する特別なサブセットＳＳＰ（Ｐ（ｎ）），Ｓ（Ｐ（ｎ））の中間ラベルＩＬＰ（Ｐ（ｎ）），Ｓ（Ｐ（ｎ））は、
ＩＬＰ（Ｐ（ｎ）），Ｓ（Ｐ（ｎ））＝ＦＲ（ＩＬＰ（ｎ），Ｓ（ｎ））
によって求められる。
【０１７７】
これらの出力にさらに関数ＦＬまたはＦＲを繰り返していくことにより、受信機はサブセットＳＳ１，２またはＳＳ１，３まで、ＳＤ方式において自身がラベルを保持すべきサブセットのうち第１の特別なサブセットのすべての中間ラベルを求めることができる。すなわち、あるノードｙがその親ノードＰ（ｙ）の左側の子であるとき、ノードＰ（ｙ）の親ノードＰ（Ｐ（ｙ））を始点とし、ノードＰ（ｙ）の兄弟ノードＳ（Ｐ（ｙ））に対応する特別なサブセットＳＳＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））の中間ラベルＩＬＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））は、
ＩＬＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））＝ＦＬ（ＩＬＰ（ｙ），Ｓ（ｙ））
によって求められる。
【０１７８】
逆にノードｙがその親ノードＰ（ｙ）の右側の子であるとき、ノードＰ（ｙ）の親ノードＰ（Ｐ（ｙ））を始点とし、ノードＰ（ｙ）の兄弟ノードＳ（Ｐ（ｙ））に対応する特別なサブセットＳＳＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））の中間ラベルＩＬＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））は、
ＩＬＰ（Ｐ（ｙ）），Ｓ（Ｐ（ｙ））＝ＦＲ（ＩＬＰ（ｙ），Ｓ（ｙ））
によって求められる。なおここで、ノードｙは受信機が割り当てられたリーフ（葉）からルートへのパス上に存在するノードである。
【０１７９】
また、中間ラベルＩＬ１，２に対しては関数ＦＲを、中間ラベルＩＬ１，３に対しては関数ＦＬを適用することにより、第２の特別なサブセットＳＳ'１，φに対応する中間ラベルＩＬ１，φを求めることができる。
【０１８０】
受信機によって実行する具体的な中間ラベル取得処理について、図２１を参照して説明する。リーフ（葉）１９に割り当てられた受信機ｕ４は中間ラベルＩＬ９，１８を保持している。ノード１９はノード９の右側の子ノードであるから、関数ＦＲを用いることにより、ノード９の親ノード４と兄弟ノード８で決定されるサブセットＳ４，８の中間ラベルＩＬ４，８を、
ＩＬ４，８＝ＦＲ（ＩＬ９，１８）
として求めることができる。
【０１８１】
また、ノード９はノード４の右側の子ノードであるから、関数ＦＲを用いることにより、ノード４の親ノード２と兄弟ノード５で決定されるサブセットＳ２，５の中間ラベルＩＬ２，５を、
ＩＬ２，５＝ＦＲ（ＩＬ４，８）
として求めることができる。
【０１８２】
この処理を繰り返していくことにより、受信機ｕ４は、ＩＬ１，３＝ＦＬ（ＩＬ２，５）およびＩＬ１，φ＝ＦＬ（ＩＬ１，３）を求めることができる。
【０１８３】
上記のようにして、サブセットＳｉ，ｋに対応する中間ラベルＩＬｉ，ｋを導出したら、受信機はラベルＬＡＢＥＬｉ，ｋを、
ＬＡＢＥＬｉ，ｋ＝Ｈ（ＩＬｉ，ｋ）として求める。
【０１８４】
それから、先に図７を用いて説明したように、擬似乱数生成器Ｇを用いて必要なサブセットＳｉ，ｊのラベルＬＡＢＥＬｉ，ｊを求め、さらにそのサブセットのサブセットキーＳＫｉ，ｊを
ＳＫｉ，ｊ＝ＧＭ（ＬＡＢＥＬｉ，ｊ）
により求め、このサブセットキーＳＫｉ，ｊを用いて暗号文を復号する。
【０１８５】
具体的なサブセットキーの導出処理例について、図２２を参照して説明する。図２２に示すように、受信機ｕ２，ｕ１１，ｕ１２がリボークされ、サブセットＳ２，１７およびサブセットＳ３，１３に対応するサブセットキーで暗号化された暗号文が同報配信されたとする。
【０１８６】
受信機ｕ４は、ＬＡＢＥＬ１，５，ＬＡＢＥＬ１，８，ＬＡＢＥＬ１，１８，ＬＡＢＥＬ２，８，ＬＡＢＥＬ２，１８，ＬＡＢＥＬ４，１８，の６個のラベルと、ＩＬ１，φ，ＩＬ１，３，ＩＬ２，５，ＩＬ４，８を導出できる中間ラベルＩＬ９，１８を保持している。受信機ｕ４は上記の（Ａ）である。すなわち、受信機ｕ４はサブセットＳ２，１７に対し、ノード１７の先祖であるノード８を用いたラベルＬＡＢＥＬ２，１８を直接保持しているため、これに擬似乱数生成器Ｇを必要な回数だけ適用することでサブセットキーＳＫ２，１７を得ることができる。
【０１８７】
また、同じセッティングで、受信機ｕ５は、ＬＡＢＥＬ１，４，ＬＡＢＥＬ１，１１，ＬＡＢＥＬ１，２１，ＬＡＢＥＬ２，１１，ＬＡＢＥＬ２，２１，ＬＡＢＥＬ５，２１の６個のラベルと、ＩＬ１，φ，ＩＬ１，３，ＩＬ２，４，ＩＬ５，１１を導出できる中間ラベルＩＬ１０，２１を保持している。受信機ｕ５は上記の（Ｂ）である。すなわち、受信機ｕ５はサブセットＳ２，１７に対し、ノード１７の先祖であるノードｋを用いたラベルＬＡＢＥＬ２，ｋを直接保持していない。このため、保持している中間ラベルＩＬ１０，２１から、ノード１７の先祖であるノード４に対応した中間ラベルＩＬ２，４を先に述べた手法でまず導出し、その後にラベルＬＡＢＥＬ２，４を求め、これに擬似乱数生成器Ｇを必要な回数だけ適用することでサブセットキーＳＫ２，１７を得ることができる。
【０１８８】
もし、リボークすべき受信機が１台もなく、サブセットとして第２の特別なサブセットＳＳ'１，φが使用されていた場合、受信機ｕｍは、上記の処理により中間ラベルＩＬ１，φを求め、これを用いてラベルＬＡＢＥＬ１，φを、
ラベルＬＡＢＥＬ１，φ＝Ｈ（ＩＬ１，φ）として計算し、
それを擬似乱数生成器Ｇに入力して出力の中央部分のＣビットを求める、すなわち、
ＳＫ１，φ＝ＧＭ（ＬＡＢＥＬ１，φ）
によりサブセットＳ１，φに対応するサブセットキーＳＫ１，φを求め、これを暗号文の復号に用いる。
【０１８９】
受信機によって実行する暗号文受領からサブセットキーの取得、復号処理の手順を図２３のフローチャートを参照して説明する。
【０１９０】
ステップＳ３０１において、まず受信機は、複数の暗号文からなる暗号文セットの中で自身が復号するものを決定する。これは、自身が生成可能なサブセットキーによって暗号化された暗号文を抽出する処理である。ここで、受信機が復号すべき暗号を決定できないということは、その受信機がリボークされていることを意味している。この暗号文選択処理は、例えば暗号文とともに送付されるサブセット指定情報に基づいて実行される。
【０１９１】
暗号文を決定したら、ステップＳ３０２において、受信機は、その暗号文の暗号化に用いられたサブセットキーを上記の手法で導出する。
【０１９２】
サブセットキーの導出処理の詳細手順について、図２４を参照して説明する。ステップＳ４０１において、受信機はまず、暗号文の復号処理に適用する求めるべきサブセットキーＳＫｉ，ｊに対応するサブセットＳｉ，ｊのノードｊが、
（Ａ）受信機が直接ラベルＬＡＢＥＬｉ，ｋを持つノードｋの子孫である（ただしｊ＝ｋの場合を含む）か、
（Ｂ）ノードｉの子ノードのうち、受信機が割り当てられたリーフ（葉）ｎからルートへのパス上にないほうのノード（つまり、パス上にあるノードｉの子ノードの兄弟であるノード）ｋと一致するかその子孫であるか（すなわち、ノードｊが、ＳＤ方式において受信機ｕｍにラベルが与えられたサブセットのうち、第１の特別なサブセットＳＳｉ，ｋを構成するノードｋの子孫であるか）
を判断する。なお、リボークする受信機がなく、第２の特別なサブセットＳＳ'１，φのサブセットキーＳＫ１，φが秘密情報の暗号化に用いられている場合には、（Ｂ）であるとみなす。
【０１９３】
（Ａ）の場合には、ステップＳ４０３に進み、受信機が持つラベルに基づいて擬似乱数生成器Ｇを必要な回数適用して必要なサブセットキーを求める。
（Ｂ）の場合には、ステップＳ４０４に進み、受信機に与えられている中間ラベルＩＬＰ（ｎ），Ｓ（ｎ）から第１の特別なサブセットＳＳｉ，ｋの中間ラベルを導出し、関数ＦＬまたはＦＲの適用により、必要なサブセットキーに対応するサブセット対応の中間ラベルを算出する。さらに、ステップＳ４０５において、算出した中間ラベルのハッシュ計算によって、そのサブセットに対応するラベルＬＡＢＥＬを算出し、ステップＳ４０６において算出ラベルＬＡＢＥＬに基づいて擬似乱数生成器Ｇを適用して必要なサブセットキーを求める。
【０１９４】
図２３のフローに戻る。上記処理によってサブセットキーを導出した受信機は、ステップＳ３０４において、ステップＳ３０２で、暗号文セットから選択した暗号文を導出したサブセットキーで復号し、送信された秘密情報を得る。秘密情報はたとえばテレビ放送システムの暗号化コンテンツを復号するためのコンテンツキーであり、この場合には受信機は暗号化コンテンツを受信し、コンテンツキーを用いて復号して出力する。
【０１９５】
図２５に、受信機５００を構成する情報処理装置例としてのブロック図を示す。図中で点線で囲われたブロックは必ずしも備わっているわけではない。たとえばメディアインタフェース５０７は、受信機５００が光ディスクプレーヤ等である場合に装備する。入出力インタフェース５０３は、受信機５００が他の機器と情報のやりとりをしたり、アンテナからの信号を受信したりする場合に装備される。重要なのは、セキュア記憶部５０４であり、セットアップフェイズにおいて、管理センタ（ＴＣ）から与えられたラベル、中間ラベルが安全に保管される。
【０１９６】
受信機５００は、階層木構造のリーフに設定される機器である。一例としての受信機５００は、図２５に示すように、コントローラ５０１、演算ユニット５０２、入出力インタフェース５０３、セキュア記憶部５０４、メイン記憶部５０５、ディスプレイ装置５０６、メディアインタフェース５０７を備える。
【０１９７】
コントローラ５０１は、例えばコンピュータ・プログラムに従ったデータ処理を実行する制御部としての機能を有するＣＰＵによって構成される。演算ユニット５０２は、例えば暗号鍵の生成、乱数生成、及び暗号処理のための専用の演算部および暗号処理部として機能する。中間ラベル（ＩＬ）に基づくラベルの算出処理、ラベルに基づくサブセットキー算出処理を実行する。また、中間ラベル（ＩＬ）から異なる中間ラベルを算出する処理も実行する。さらに、サブセットキーに基づく暗号文の復号処理を実行する。
【０１９８】
入出力インタフェース５０３は、キーボード、マウス等の入力手段からのデータ入力や、外部出力装置に対するデータ出力、ネットワークを介したデータ送受信処理に対応するインタフェースである。
【０１９９】
セキュア記憶部５０４は、例えばセットアップフェイズにおいて、管理センタ（ＴＣ）から与えられたラベル、中間ラベル、各種ＩＤなど、安全にまたは秘密に保持すべきデータを保存する記憶部である。
【０２００】
セキュア記憶部５０４は、サブセットから選択された特別サブセット対応の中間ラベル（ＩＬ）と、前記中間ラベル（ＩＬ）から算出できないサブセット対応のラベル（ＬＡＢＥＬ）とを格納している。
【０２０１】
セキュア記憶部５０４に格納される中間ラベルは、
階層木において、ノードｉを頂点とする部分木からノードｉより下層のノードｊを頂点とする部分木を除く集合として定義されたサブセットＳｉ，ｊ中、ノードｉおよびノードｊが階層木において直結された親子関係にある第１特別サブセットと、
階層木のすべてのリーフを含むルートを頂点とする全体木の集合として定義されたサブセットＳ１，φである第２特別サブセットと、
から構成される特別サブセットから選択された１つのサブセットに対応する中間ラベルである。
【０２０２】
メイン記憶部５０５は、例えばコントローラ５０１において実行するデータ処理プログラム、その他、一時記憶処理パラメータ、プログラム実行のためのワーク領域等に使用されるメモリ領域である。セキュア記憶部５０４及びメイン記憶部５０５は、例えばＲＡＭ、ＲＯＭ等によって構成されるメモリである。ディスプレイ装置５０６は復号コンテンツの出力等に利用される。メディアインタフェース５０７は、ＣＤ、ＤＶＤ、ＭＤ等のメディアに対する読出／書込機能を提供する。
【０２０３】
［６．Ｂａｓｉｃ  Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ベーシックＬＳＤ）方式の概要］
次に、Ｂａｓｉｃ  Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ベーシックＬＳＤ）方式の概要について説明する。
【０２０４】
前述の背景技術の欄で説明した［非特許文献２：  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ−Ｃｒｙｐｔｏ  ２００２，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ２４４２，Ｓｐｒｉｎｇｅｒ，２００２，ｐｐ４７−６０「Ｄ．Ｈａｌｅｖｙ  ａｎｄ  Ａ．Ｓｈａｍｉｒ著"Ｔｈｅ  ＬＳＤ  Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ"」］には、ＳＤ方式を改良したＬａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ方式が提案されている。ＬＳＤ方式には、Ｂａｓｉｃ（基本）方式と、その拡張であるＧｅｎｅｒａｌ（一般化）方式がある。ここではＢａｓｉｃ方式について説明する。
【０２０５】
ＬＳＤ方式はＳＤ方式の拡張であり、レイヤという新たな概念を取り入れたものである。ＳＤ方式における木構造の中で、特定の高さを特別レベル（Ｓｐｅｃｉａｌ  Ｌｅｖｅｌ）として定義する。ベーシックＬＳＤ方式においては特別レベルは、１種類だけであるが、一般化ＬＳＤ方式においては重要度の異なる複数の特別レベルを用いる。
【０２０６】
いま、簡単のため、ｌｏｇ１／２Ｎを整数であるとする。ベーシックＬＳＤ方式では、図２６に示すように、木のルートからリーフ（葉）に至るまでのそれぞれのレベル（階）のうち、ルートとリーフ（葉）のレベルを含むｌｏｇ１／２Ｎごとのレベルを特別レベルであると決める。そして、隣り合う２つの特別レベルに挟まれた階層（両端の特別レベルを含む）を、レイヤと呼ぶ。図２６の例では、ルートのレベル、ノードｋを含むレベル、リーフ（葉）のレベルが特別レベルであり、ルートのレベルとノードｉを含むレベルとノードｋを含むレベルが１つのレイヤを構成する。またノードｋを含むレベルとノードｊを含むレベルとリーフ（葉）を含むレベルが別のレイヤを構成する。
【０２０７】
ベーシックＬＳＤ方式においては、ＳＤ方式において定義されたサブセットＳｉ，ｊのうち、（１）ノードｉとノードｊが同一レイヤにあるか、もしくは（２）ノードｉが特別レベルにあるか，少なくとも一方の条件を満たすものだけを定義する。このようにすると、ＳＤ方式において用いられたサブセットのうちのいくつかはベーシックＬＳＤ方式では定義されなくなってしまうが、このサブセットはベーシックＬＳＤ方式で定義されたサブセットの高々２つの和集合で表すことができる。たとえば図２６の例では、サブセットＳｉ，ｊは、ベーシックＬＳＤ方式では定義されないが、ノードｉからノードｊへのパス上の、ノードｉに最も近い特別レベル上のノード（ノードｋ）を用いて、
Ｓｉ，ｊ＝Ｓｉ，ｋ∪Ｓｋ，ｊ
と表すことができる。
【０２０８】
つまり、ＳＤ方式においてはサブセットＳｉ，ｋに対応するサブセットキーＳＫｉ，ｋを用いて暗号化した１つの暗号文の代わりに、ベーシックＬＳＤ方式においてはサブセットＳｉ，ｋとＳｋ，ｊに対応するサブセットキーＳＫｉ，ｋとＳＫｋ，ｊを用いて暗号化した２つの暗号文を送信する。
【０２０９】
この工夫により、送信される暗号文の数はＳＤ方式の高々２倍に増加するのみであり、一方、各受信機が保持するラベルの数は、上述したＳＤ方式よりも減らすことができる。
【０２１０】
先に図９を参照して、ＳＤ方式において各受信機が保持するラベルの数の説明を行なったが、同じセッティングの場合のベーシックＬＳＤ方式における各受信機が保持するラベルの数について、図２７を参照して説明する。図２７中の受信機ｕ４は、ｉ，ｊが同一レイヤにあるか、ｉが特別レベルにあるラベルＬＡＢＥＬｉ，ｊのみ保持しておけばよい。すなわち、受信機ｕ４が保持するラベルは、ＬＡＢＥＬ１，３，ＬＡＢＥＬ１，５，ＬＡＢＥＬ１，８，ＬＡＢＥＬ１，１８，ＬＡＢＥＬ２，５，ＬＡＢＥＬ４，８，ＬＡＢＥＬ４，１８，ＬＡＢＥＬ９，１８となる。さらに、ＳＤ方式と同様に、リボークする受信機がない場合に用いる特別なラベルも保持する必要がある。
【０２１１】
総受信機数をＮとしたときに、各受信機が保持しておくラベルの総数は下記のように求められる。まず、レイヤ１つあたりのラベル数は、ノードｉを決めるとラベル内でのｉの高さ分だけノードｊが存在するので、下式によって算出される数となる。
【数８】
2005191805.tif 000009
となる。
【０２１２】
階層木にレイヤは、ｌｏｇ１／２Ｎ個あるから、階層木全体のレイヤでのラベル数は下式によって算出される数となる。
【数９】
2005191805.tif 000010
である。
【０２１３】
次にノードｉが特別レベルであるものを考えると、階層木全体におけるｉの高さ分だけノードｊが存在するので、ノードｉが特別レベルであるものを含む階層木全体のラベル数は下式によって算出される数となる。
【数１０】
2005191805.tif 000011
である。
【０２１４】
いま、ノードｉが特別レベルにあり、ノードｊが同一レイヤにあるものは重複して数えたので、その分を引く必要がある。この組み合わせは、１つのレイヤにつきｌｏｇ１／２Ｎ個あるので全体ではｌｏｇＮ個である。これらと、リボークする受信機がない場合のための特別な１つを加えると、ベーシックＬＳＤ方式において各受信機が保持するラベルの総数は、下式によって与えられる数となる。
【数１１】
2005191805.tif 000012
である。
【０２１５】
［７．平方剰余木を用いたベーシックＬＳＤ方式のラベル数削減構成］
次に、平方剰余木を用いたベーシックＬＳＤ方式のラベル数削減構成について説明する。前述のＳＤ方式を基にした本発明では、ノードｉがノードｊの親である場合のサブセットＳｉ，ｊのラベルＬＡＢＥＬｉ，ｊを求めるための中間ラベルＩＬｉ，ｊを導出できる特定の中間ラベルを１つだけ持つようにすることで、各受信機が持つラベルの数を減らした。この手法は、ベーシックＬＳＤ方式についても同様に適用することができる。
【０２１６】
具体的な構成方法は、前述の本発明の実施例とほぼ同じである。ただ、セットアップ時に、管理センタ（ＴＣ）が擬似乱数生成器Ｇを用いてラベルＬＡＢＥＬｉ，ｊを次々と作成していく際に、ノードｉが特別レベルにない場合、ｉの直下の特別レベルよりも下のノードをｊとするラベルは利用されないので、その特別レベルまででラベルの生成を止めることができる。また、作られたラベルを各受信機に配布する際も、上述の条件を満たす
ラベルのみが作成されているので、それだけを受信機に配布すればよい。
【０２１７】
図２７を参照して説明したと同様のセッティングとして、平方剰余木を用いたベーシックＬＳＤ方式のラベル数削減構成の具体例を図２８を参照して説明する。ベーシックＬＳＤ方式において、受信機ｕ４が保持するラベルは、図２７を参照して説明したように、ＬＡＢＥＬ１，３，ＬＡＢＥＬ１，５，ＬＡＢＥＬ１，８，ＬＡＢＥＬ１，１８，ＬＡＢＥＬ２，５，ＬＡＢＥＬ４，８，ＬＡＢＥＬ４，１８，ＬＡＢＥＬ９，１８と、さらに、ＳＤ方式と同様の、リボークする受信機がない場合に用いる特別なラベルの合計９個のラベルを保持しておく必要があった。これに対し、本発明のようにノードｉ，ｊが親子関係となるものと、リボークする受信機がない場合に使われる特別なサブセットに対応する中間ラベルＩＬｉ，ｊおよびＩＬ１，φを導出できる中間ラベルＩＬ９，１８を持つようにすると、４個のラベルＬＡＢＥＬ１，５，ＬＡＢＥＬ１，８，ＬＡＢＥＬ１，１８，ＬＡＢＥＬ４，１８と、１つのと中間ラベルＩＬ９，１８の合計５個を保持すればよい。
【０２１８】
総受信機数をＮとした場合に本発明により削減できるラベルの個数を考える。本発明を適用しないベーシックＬＳＤ方式において、ノードｉ，ｊが親子関係になるようなラベルＬＡＢＥＬｉ，ｊを各受信機がいくつ保持すべきかを考える。
【０２１９】
ノードｉ，ｊが親子関係になっているときには、以下の３つの場合が考えられる。
（Ａ）ノードｉが特別レベルにある。
（Ｂ）ノードｊが特別レベルにある。
（Ｃ）ノードｉもｊも特別レベルにない。
これらのいずれの場合も、ノードｉ，ｊが親子関係にある（つまり、隣り合っている）場合には、ｉとｊは同一レイヤに存在する。すなわち、サブセットＳｉ，ｊはベーシックＬＳＤ方式で定義されるための条件を満たしている。つまり、このようなサブセットはベーシックＬＳＤ方式で定義され使用されるため、受信機はそれに対応するＬＥＢＥＬｉ，ｊを保持しておく必要がある。
【０２２０】
ある受信機に対してこのようなノードｉ，ｊは、ｉの取り方が木の高さ分（すなわち、受信機が割り当てられたリーフ（葉）からルートへのパス上の、リーフ（葉）を除くノードすべて）あり、ｉを決めればｊがただ１つ決まる（ｉの子で、上記のパス上にないノード）ため、木の高さ分、すなわちｌｏｇＮ個だけ存在する。
【０２２１】
本発明を用いて、これらのｌｏｇＮ個のラベルと１つの特別なラベルを、１つの中間ラベルから作り出すようにすることにより、受信機が保持するラベルの数を、
ｌｏｇＮ＋１−１＝ｌｏｇＮ
だけ削減することが可能となる。
【０２２２】
上述のように、ベーシックＬＳＤ方式では受信機が保持するラベルの総数は、
ｌｏｇ３／２Ｎ＋１
であったため、本発明を適用することによりこれを、
ｌｏｇ３／２Ｎ−ｌｏｇＮ＋１
に削減することができる。
【０２２３】
［８．Ｇｅｎｅｒａｌ  Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（一般化ＬＳＤ）方式の概要］
次に、Ｇｅｎｅｒａｌ  Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（一般化ＬＳＤ）方式の概要について説明する。
【０２２４】
ベーシックＬＳＤ方式では、１種類の特別レベルを用いていたが、Ｇｅｎｅｒａｌ  Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（一般化ＬＳＤ）方式では、重要度の異なる複数の特別レベルを用いる。
【０２２５】
ＬＳＤ方式を提案した論文と同様に、階層木において、ルートからノードｉを経てノードｊに至るパスを１本のグラフとして考える。木のルートとノードｊが端点となり、木のノードがグラフのノードとなり、端点以外のノードのひとつがノードｉとなっている。このグラフでは、各ノードはルートからの距離で表される。この距離は、ｄ桁のｂ進数（ただしｂ＝（ｌｏｇ１／ｄＮ））で表される。たとえば、ルートは０...００と表され、その隣のノード（階層木構造で、ルートの子ノードであるノード）は０...０１と表される。
【０２２６】
サブセットＳｉ，ｊは、定義された変換（ノードからノードへの遷移）を組み合わせての、ノードｉからノードｊへの最終的な遷移であると考える。定義された変換は定義されたサブセットを表し、最終的な遷移に要する個々の遷移が、サブセットＳｉ，ｊを分割して表すのに必要な定義されたサブセットを示す。もとの論文にあるように、ノードｉ，ｋ１，ｋ２，・・・，ｋｄ−１，ｊがこの順で木のパス上に存在するときには、ＳＤ方式におけるサブセットＳｉ，ｊは一般化ＬＳＤ方式においては、下式によって示される。
【数１２】
2005191805.tif 000013
であり、高々ｄ個のサブセットの和集合で表される。
【０２２７】
一般化ＬＳＤ方式では、ノードｉが上記のグラフで［ｘ］（→）ａ［０］（→）（ただしａは非ゼロの数字のうち一番右にある数字、［ｘ］（→）は任意の数字列、［０］（→）はゼロの列である）と表されるとき、［ｘ＋１］（→）０［０］（→）、もしくは、［ｘ］（→）ａ'［ｙ］（→）（ただしａ'＞ａであり、［ｙ］（→）は［０］（→）と同じ長さの任意の数字列）のいずれかで表されるノードｊへの遷移をすべて定義する。すなわち，そのようなｉ，ｊの組で表されるサブセットＳｉ，ｊをすべて定義する．
【０２２８】
このようにすると、ベーシックＬＳＤ方式は、一般化ＬＳＤ方式においてｄ＝２で、（一番右の）最終桁が０である２桁の数字で表されるレベルが特別レベルであるものと考えることができる。一般化ＬＳＤ方式では、ノードｉを表す数字における一番右のゼロの列の桁数が、そのレベルの重要度を表し、ノードｊはｉ＋１からｉよりも重要度の高い最初のノードまでのいずれのノード（両端のノードを含む）にもなる可能性がある。このようなセッティングで、たとえばｉ＝８２５９１７，ｊ＝８６４５６３とすると、ｉからｊへの遷移、すなわちＳＤ方式におけるサブセットＳｉ，ｊは、
８２５９１７→８２５９２０→８２６０００→８３００００→８６４５６３
という一般化ＬＳＤ方式で定義された４つの遷移によって表すことができる。
【０２２９】
すなわち、ｋ１＝８２５９２０，ｋ２＝８２６０００，ｋ３＝８３００００とおけば、サブセットＳｉ，ｊは下式によって示される。すなわち、
【数１３】
2005191805.tif 000014
となる。
【０２３０】
ＳＤ方式の上記のサブセットＳｉ，ｊに属する受信機に秘密情報を伝送するためには、一般化ＬＳＤ方式においては、下式によって示されるサブセット、
【数１４】
2005191805.tif 000015
に対応するサブセットキーで暗号化した４つの暗号文を送信する。
【０２３１】
一般化ＬＳＤ方式で各受信機が保持すべきラベル数は、パラメータｄを大きくしていくことにより減少していき、最終的には、
Ｏ（ｌｏｇ１＋εＮ）
を得る。ただしε＝１／ｄである。またこのとき、送信すべき暗号文数の上限は、
ｄ（２ｒ−１）
となる。詳細については上記の論文を参照されたい。
【０２３２】
［９．平方剰余木を用いた一般化ＬＳＤ方式のラベル数削減構成］
次に、平方剰余木を用いた一般化ＬＳＤ方式のラベル数削減構成について説明する。前述の、ベーシックＬＳＤ方式に平方剰余木を用いて受信機が保持すべきラベル数を削減する手法は、一般化ＬＳＤ方式についても適用できる。具体的には、ベーシックＬＳＤ方式と一般化ＬＳＤ方式は定義されるサブセットが満たすべき条件が違うのみであり、平方剰余木を利用する部分に違いはない。
【０２３３】
一般化ＬＳＤ方式においても、受信機ｕｍは、ＳＤ方式において定義され受信機ｕｍに与えられるラベルのうち、ノードｉ，ｊが親子関係になっているサブセットＳｉ，ｊに対応するラベルＬＡＢＥＬｉ，ｊをすべて保持しておく必要がある。これは、ノードｉとしてどんな値をとっても、その子ノードｊ（すなわちｉ＋１）への遷移は、上述の定義される遷移の条件に当てはまるためである。すなわち、ベーシックＬＳＤ方式と同様に、ある受信機にとって、保持すべきラベルのうちノードｉ，ｊが親子関係になっているものはｌｏｇＮ個ある。これらのラベルと特別なラベルを１つの中間ラベルから作り出すようにすることにより、ｌｏｇＮ個のラベルの削減が可能となる。もともと一般化ＬＳＤ方式で各受信機が保持しておくべきラベルの数は、
Ｏ（ｌｏｇ１＋εＮ）
（ただしεは任意の正数）であったため、ここからｌｏｇＮ個のラベルを削減できることになる。
【０２３４】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、冒頭に記載した特許請求の範囲の欄を参酌すべきである。
【０２３５】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【０２３６】
例えば、プログラムは記録媒体としてのハードディスクやＲＯＭ（Read Only Memory)に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)，ＭＯ(Magneto optical)ディスク，ＤＶＤ(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【０２３７】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０２３８】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０２３９】
以上、説明したように、本発明の構成によれば、ブロードキャストエンクリプション（Broadcast Encryption）方式の一態様である階層型木構造を適用した情報配信構成において比較的に効率的な構成であるとされているＳｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式、およびＬａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＬＳＤ）方式に対して、さらに平方剰余木を適用することにより、各受信機が安全に保持すべき情報量を削減することが可能となる。従って、本発明の適用により、暗号文の復号、再生を実行するユーザデバイスとしての情報処理装置に格納すべき情報量を削減することが可能となり、階層木構造を適用した暗号文の提供システムの効率的な構築、運用が実現される。
【０２４０】
さらに、本発明の構成によれば、ＳＤ方式、ＬＳＤ方式、それぞれの方式において各受信機が安全に保持すべき情報量をそれぞれｌｏｇＮだけ減少させる。すなわち、ＳＤ方式およびＬＳＤ方式で定義される鍵の中でひとつの受信機が保持すべきもののうち、特定のｌｏｇＮ＋１個の鍵をひとつの鍵から計算により導出可能な設定としたので、各受信機が安全に保持すべき情報量を削減することが可能となる。従って、本発明の適用により、暗号文の復号、再生を実行するユーザデバイスとしての情報処理装置に格納すべき情報量を削減することが可能となり、階層木構造を適用した暗号文の提供システムの効率的な構築、運用が実現される。
【０２４１】
さらに、本発明の構成によれば、階層木構成に基づくブロードキャストエンクリプション方式を適用し、排除（リボーク）機器を除く特定の選択機器にのみ復号可能な暗号文配信構成を実現する暗号文配信において、ＳＤ方式、ＬＳＤ方式に基づいて設定するサブセット各々に対応するラベル（ＬＡＢＥＬ）中、選択された一部の特別サブセットに対応するラベルを、特別サブセット対応の中間ラベル（ＩＬ）から算出可能な値として設定し、異なる特別サブセットに対応する異なる中間ラベル間の関係式としての関数を公開し、中間ラベルから算出可能なラベルを除くラベルと、１つの中間ラベルを、階層木のリーフ（葉）対応の受信機（情報処理装置）に提供する構成とし、受信機側において保持する中間ラベルに基づいて必要なラベルを算出可能としたので、各受信機が安全に保持すべき情報量を削減することが可能となる。従って、本発明の適用により、暗号文の復号、再生を実行するユーザデバイスとしての情報処理装置に格納すべき情報量を削減することが可能となり、階層木構造を適用した暗号文の提供システムの効率的な構築、運用が実現される。
【図面の簡単な説明】
【０２４２】
【図１】２分木階層型木構造について説明する図である。
【図２】２分木階層型木構造において、選択した情報処理装置のみが取得可能な情報を送信する方法を説明する図である。
【図３】Ｃｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ（ＣＳ）方式において適用するノードが２つに分岐する階層型木構造を説明する図である。
【図４】Ｃｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ（ＣＳ）方式においてリーフ対応の受信機の持つノードキーについて説明する図である。
【図５】ＣＳ方式において秘密情報をリボークされない受信機のみに選択的に提供するかについて説明する図である。
【図６】Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式におけるサブセットの定義について説明する図である。
【図７】Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式におけるラベルの設定および構成について説明する図である。
【図８】Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ（ＳＤ）方式におけるサブセットの設定について説明する図である。
【図９】ＳＤ方式において、全受信機数Ｎ＝１６の設定の場合に各受信機が保持すべきラベルを示す図である。
【図１０】ＳＤ方式において、各受信機が保持すべきラベルの詳細について説明する図である。
【図１１】ＳＤ方式において、各受信機が保持すべきラベルの詳細について説明する図である。
【図１２】ＳＤ方式において、特定の受信機ｕ４画属するサブセットの詳細について説明する図である。
【図１３】平方剰余木として設定した階層木において、Ｎ＝１６のときに、ノード対応値ｘ１からｘ３１の値を順に生成する手順を示す図である。
【図１４】ノードｙの兄弟ノードと親ノードで指定される第１の特別なサブセットＳＳＰ（ｙ），Ｓ（ｙ）の詳細と、ラベルおよび中間ラベルの関係について説明する図である。
【図１５】中間ラベル（ＩＬ）の設定処理例を示す図である。
【図１６】図１４に対応するサブセットにおける中間ラベル、ラベルの対応について説明する図である。
【図１７】本発明を適用した場合、すなわち平方剰余木を適用したＳＤ方式において受信機に提供するラベルの種類について説明する図である。
【図１８】平方剰余木を適用したＳＤ方式におけるセットアップ処理手順を説明するフローチャートを示す図である。
【図１９】総受信機数Ｎ＝１６に設定した階層木構成において、受信機ｕ２，ｕ１１，ｕ１２をリボークする際に用いるサブセットを示す図である。
【図２０】平方剰余木を適用したＳＤ方式における情報配信処理の処理手順について説明するフローチャートを示した図である。
【図２１】受信機によって実行する具体的な中間ラベル取得処理について説明する図である。
【図２２】具体的なサブセットキーの導出処理例について説明する図である。
【図２３】受信機によって実行する暗号文受領からサブセットキーの取得、復号処理の手順を説明するフローチャートを示す図である。
【図２４】平方剰余木を適用したＳＤ方式において、受信機におけるサブセットキー導出処理の詳細手順について説明するフロー図である。
【図２５】受信機を構成する情報処理装置例としてのブロック図を示す図である。
【図２６】ベーシックＬＳＤ方式について説明する図である。
【図２７】ベーシックＬＳＤ方式における各受信機が保持するラベルの数について説明する図である。
【図２８】平方剰余木を用いたベーシックＬＳＤ方式のラベル数削減構成について説明する図である。
【符号の説明】
【０２４３】
１０１  情報処理装置
２０１  ノード
２３１，２３２  ノード
３０１  ノード
３０２  親ノードＰ（ｉ）
３０３  兄弟ノードＳ（ｉ）
３１０  サブセットＳＳＰ（ｙ），Ｓ（ｙ）
５００  受信機
５０１  コントローラ
５０２  演算ユニット
５０３  入出力インタフェース
５０４  セキュア記憶部
５０５  メイン記憶部
５０６  ディスプレイ装置
５０７  メディアインタフェース
【図１】
2005191805.tif 000017
【図２】
2005191805.tif 000018
【図３】
2005191805.tif 000019
【図４】
2005191805.tif 000020
【図５】
2005191805.tif 000021
【図６】
2005191805.tif 000022
【図７】
2005191805.tif 000023
【図８】
2005191805.tif 000024
【図９】
2005191805.tif 000025
【図１０】
2005191805.tif 000026
【図１１】
2005191805.tif 000027
【図１２】
2005191805.tif 000028
【図１３】
2005191805.tif 000029
【図１４】
2005191805.tif 000030
【図１５】
2005191805.tif 000031
【図１６】
2005191805.tif 000032
【図１７】
2005191805.tif 000033
【図１８】
2005191805.tif 000034
【図１９】
2005191805.tif 000035
【図２０】
2005191805.tif 000036
【図２１】
2005191805.tif 000037
【図２２】
2005191805.tif 000038
【図２３】
2005191805.tif 000039
【図２４】
2005191805.tif 000040
【図２５】
2005191805.tif 000041
【図２６】
2005191805.tif 000042
【図２７】
2005191805.tif 000043
【図２８】
2005191805.tif 000044