(57)【要約】【課題】ＳＤ法の対象を多分木に拡張することで、より柔軟なクライアント端末の被覆が実現でき、ブロードキャスト鍵ブロックのサイズの軽減を図ることができる。【解決手段】ａ分木の末端のノードにクライアント端末を割り当て、木の全ノードに｜Ｋ｜ビットのラベルを割り当てて、一方向性関数を用いて、ラベルを生成する。そして、各クライアント端末にラベルを割り当て、すべての正当なクライアント端末を複数の差分木で被覆し、作成した各被覆に対して、コンテンツ鍵を暗号化し、暗号化したコンテンツ鍵を連接してブロードキャスト鍵ブロックを生成する。【選択図】図１
2009044516.tif 000002
【特許請求の範囲】
【請求項１】
一般の木構造（ａ分木）におけるＳＤ法を用いたブロードキャスト暗号の生成方法であって、
該ａ分木の末端のノードにクライアント端末を割り当てる第１のステップと、
木の全ノードに｜Ｋ｜ビットのラベルを割り当てて、一方向性関数を用いて、ラベルを生成する第２のステップと、
各クライアント端末にラベルを割り当てる第３のステップと、
すべての正当なクライアント端末を複数の差分木で被覆する第４のステップと、
作成した各被覆に対して、コンテンツ鍵を暗号化し、該暗号化したコンテンツ鍵を連接してブロードキャスト鍵ブロックを生成する第５のステップと、
を備えたことを特徴とするブロードキャスト暗号の生成方法。
【請求項２】
前記一方向関数は、ラベル長ｎに対してｎ＋１倍の出力をする関数であり、ｈ（Ｌ）の先頭から｜Ｋ｜ビットを抜き出したものをｈ１（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈ２（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈ３（Ｌ）、・・・、（ａ−１）｜Ｋ｜＋１ビット目から、ａ｜Ｋ｜ビット目までを抜き出したものをｈａ（Ｌ）、最後の｜Ｋ｜ビットを抜き出したものを、ｈｋ（Ｌ）としたときに、ｈ１（Ｌ）、ｈ２（Ｌ）、・・・、ｈａ（Ｌ）をあるノードのラベルＬから、子ノードのラベルを導出するため用い、ｈｋ（Ｌ）をラベルＬからコンテンツ鍵を導出するために用いることを特徴とする請求項１に記載のブロードキャスト暗号の生成方法。
【請求項３】
一般の木構造（ａ分木）におけるＳＤ法を用いたブロードキャスト暗号の生成方法をコンピュータに実行させるためのプログラムであって、
該ａ分木の末端のノードにクライアント端末を割り当てる第１のステップと、
木の全ノードに｜Ｋ｜ビットのラベルを割り当てて、一方向性関数を用いて、ラベルを生成する第２のステップと、
各クライアント端末にラベルを割り当てる第３のステップと、
すべての正当なクライアント端末を複数の差分木で被覆する第４のステップと、
作成した各被覆に対して、コンテンツ鍵を暗号化し、該暗号化したコンテンツ鍵を連接してブロードキャスト鍵ブロックを生成する第５のステップと、
をコンピュータに実行させるためのプログラム。
【請求項４】
前記一方向関数は、ラベル長ｎに対してｎ＋１倍の出力をする関数であり、ｈ（Ｌ）の先頭から｜Ｋ｜ビットを抜き出したものをｈ１（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈ２（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈ３（Ｌ）、・・・、（ａ−１）｜Ｋ｜＋１ビット目から、ａ｜Ｋ｜ビット目までを抜き出したものをｈａ（Ｌ）、最後の｜Ｋ｜ビットを抜き出したものを、ｈｋ（Ｌ）としたときに、ｈ１（Ｌ）、ｈ２（Ｌ）、・・・、ｈａ（Ｌ）をあるノードのラベルＬから、子ノードのラベルを導出するため用い、ｈｋ（Ｌ）をラベルＬからコンテンツ鍵を導出するために用いることを特徴とする請求項３に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ａ分木におけるＳＤ法を用いたブロードキャスト暗号の生成方法およびプログラムに関する。
【背景技術】
【０００２】
コンテンツ配信サービスにおいては、著作権保護のため、コンテンツを暗号化して配布することが必要である。その方法の一つとして、ブロードキャスト暗号は、コンテンツ鍵を正当なクライアント端末のみに配布する技術である。
【０００３】
ここで、コンテンツ鍵とは、配布されるコンテンツを暗号化するための鍵である。ブロードキャスト暗号においては、各クライアント端末に、複数の鍵（鍵束）を事前に格納する。この鍵束は、クライアント端末ごとに異なり、更新されることはない。鍵管理サーバは、無効化されたクライアント端末のリストに基づき、コンテンツ鍵を暗号化しブロードキャスト鍵ブロックを作成する。作成したブロードキャスト鍵ブロックを、各クライアント端末に配布する。ブロードキャスト鍵ブロックを受信したクライアント端末は、自身に格納されている鍵束を用いてコンテンツ鍵の復号を試みる。正当なクライアント端末は、ブロードキャスト鍵ブロックから、コンテンツ鍵を正しく復号できる。一方で、無効化されたクライアント端末は、ブロードキャスト鍵ブロックから、コンテンツ鍵を復号できない。図４にブロードキャスト暗号の概念図を示す。
【０００４】
ところで、ブロードキャスト暗号を実現する最も自明な方式として、クライアント端末ごとに異なる個別鍵を格納しておき、コンテンツ鍵を各個別鍵で暗号化したものを、ブロードキャスト鍵ブロックとする方法がある。しかしながら、本方式では、ブロードキャスト鍵ブロックがクライアント端末の総数に比例し、増大するという課題がある。
【０００５】
そのため、非特許文献１に示されるように、木構造に基づく鍵の階層化を行い、ブロードキャスト鍵ブロックを構成するＣｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ  Ｍｅｔｈｏｄ（ＣＳ法）が提案されている。本方式においては、前記の方式と比較して、ブロードキャスト鍵ブロックのサイズを削減できるという特徴がある。下記に具体的な手順を示す。
【０００６】
（１）鍵の割り当て方法
＜手順１＞  クライアント端末の総数をＮとする。a分木の末端のノード（リーフノード）に、クライアント端末を割り当てる。ここで、Ｎ＝ａｈとならない場合は、Ｎ台の正当なクライアント端末、ａｈ−Ｎ(台)の無効化されたクライアント端末を配置するとみなせばよいので、Ｎ＝ａｈとして一般性を失わない。以下の説明は、Ｎ＝ａｈとして行う。
【０００７】
＜手順２＞上記手順で作成した木構造の各ノードに対し鍵を生成し、割り当てる。
【０００８】
＜手順３＞木の末端の各ノード（リーフノード）に、各クライアント端末を割り当てる。
【０００９】
＜手順４＞各クライアント端末に、鍵を配置する。ここで、リーフノードｘに割り当てられているクライアント端末は、ルートノードからリーフノードｘに至るまでの経路上にあるすべてのノードに割り当てられた鍵を所有するものとする。図５の例では、左端のクライアント端末は、ノード１，２，４および８に割り当てられた鍵ｋ１、ｋ２、ｋ４およびｋ８を保有する。
【００１０】
（２）ブロードキャスト鍵ブロックの生成
＜手順１＞正当なクライアント端末を、部分木により被覆する。図５の例では、ノード１２に割り当てられている無効化されたクライアント端末以外のクライアント端末を、ノード２、ノード７およびノード１３を頂点とする３つの部分木で被覆する。
【００１１】
＜手順２＞コンテンツ鍵を、手順１で求めた部分木の頂点のノードに割り当てられた鍵で暗号化する。ここで得られた複数の暗号化されたコンテンツ鍵を連接したものを、ブロードキャスト鍵ブロックとする。図５の例では、コンテンツ鍵Ｋは、鍵ｋ２、ｋ７およびｋ１３で暗号化される。ブロードキャスト鍵ブロックＢＫＢは、これらの暗号化されたコンテンツ鍵を連接した数１となる。
【００１２】
【数１】
2009044516.tif 000003
【００１３】
ノード１２に割り当てられているクライアント端末以外は、鍵ｋ２、ｋ７およびｋ１３のうち少なくとも１つの鍵を保有している。このため、ブロードキャスト鍵ブロックから、コンテンツ鍵Ｋを復号できる。一方、ノード１２に割り当てられている端末は、鍵ｋ２、ｋ７およびｋ１３のいずれの鍵も保有しないため（ここでは、保有する鍵はｋ１、ｋ３、ｋ６およびｋ１２である）、ブロードキャスト鍵ブロックからコンテンツ鍵Ｋを復号できない。
【００１４】
しかしながら、本方式では、ブロードキャスト鍵ブロックのサイズが、無効化されたクライアント端末の数に依存し、増大するという課題がある。つまり、木構造の次数をａ、クライアント端末の総数をＮ、無効化されたクライアント端末の数をｒ、コンテンツ鍵Ｋのサイズを｜Ｋ｜とすると、ブロードキャスト鍵ブロックのサイズは、数２となることが示されている。
【００１５】
【数２】
2009044516.tif 000004
【００１６】
そこで、非特許文献１では、差分木（ｓｕｂｓｅｔ  ｄｉｆｆｅｒｅｎｃｅ  ｔｒｅｅ）を用いて、ブロードキャスト鍵ブロックを構成するＳｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ  Ｍｅｔｈｏｄ（ＳＤ法）が提案されている。このＳＤ法においては、ブロードキャストブロックのサイズは、最大で、数３であり、平均で、数４であることが示されている。
【００１７】
【数３】
2009044516.tif 000005
【００１８】
【数４】
2009044516.tif 000006
【００１９】
ＳＤ法では、クライアント端末は、暗号学的に安全な一方向性関数ｈ：｛０，１｝｜Ｋ｜→｛０，１｝３｜Ｋ｜を用いる。ここで、ｈ（Ｌ）の先頭から｜Ｋ｜ビットを抜き出したものをｈｌ（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈｋ（Ｌ）、最後の｜Ｋ｜ビットを抜き出したものを、ｈｒ（Ｌ）とする。ｈｌ（Ｌ）およびｈｒ（Ｌ）は、あるノードのラベルＬから、子ノードのラベルを導出するために用いられ、ｈｋ（Ｌ）は、ラベルＬから鍵を導出するために用いる。下記に具体的な手順を示す。
【００２０】
（１）ラベルの割り当て処理
＜手順１＞クライアント端末の総数をＮとする。２分木の末端のノード（リーフノード）に、クライアント端末を割り当てる。ここで、Ｎ＝２ｈとならない場合は、Ｎ台の正当なクライアント端末、２＾ｈ−Ｎ(台)の無効化されたクライアント端末を配置するとみなせばよいので、Ｎ＝２ｈとして一般性を失わない。以下の説明は、Ｎ＝２ｈとして行う。
＜手順２＞木の全ノードに｜Ｋ｜ビットのラベルｌ（ｘ，ｘ）を任意に割り当てる。その後、一方向性関数を用いて、ラベル数５を生成する。ここで、ノードｘを頂点とし、ノードｙを含む部分木が存在するとき、ノードｙをノードｘの子孫であるという。また、Ｄｅｓｃｅｎｄａｎｔ（ｘ）は、ノードｘの子孫からなる集合をあらわす。
【００２１】
【数５】
2009044516.tif 000007
【００２２】
＜手順３＞クライアント端末に、ラベルを割り当てられる。リーフノードｘに割り当てられたクライアント端末が保有するラベルの集合Ｌは、下記数６の通りである。
【００２３】
【数６】
2009044516.tif 000008
【００２４】
ただし、Ｐａｔｈ（ｉ、ｊ）は、ノードｉから、ノードｊに至るまでの経路に含まれるノードの集合（ノードｉおよびノードｊを含む）、Ｓｉｂｌｉｎｇ（ｉ）は、ノードｉと同一の親ノードをもつノードからなる集合（ノードｉを含まない）である。例えば、図６において、Ｐａｔｈ（１、８）＝｛１，２，４，８｝であり、Ｓｉｂｌｉｎｇ（４）＝｛５｝である。また、ｌ（ＡＬＬ）は無効化したクライアント端末が存在しない場合に用いられるラベルである。図６の例では、リーフノード８に割り当てられているクライアント端末は、以下のラベル数７を保有する。具体的に書き下すと、
ｌ（１，３），ｌ（１，５），ｌ（１，９），ｌ（２，５），ｌ（２，９），ｌ（４．９），ｌ（ＡＬＬ）となる。
【００２５】
【数７】
2009044516.tif 000009
【００２６】
（２）ブロードキャスト鍵ブロックの構成方法
＜手順１＞すべての正当なクライアント端末を、複数の差分木で被覆する。ここで、差分木とは、あるノードを頂点とする部分木から、このノードの子孫のノードを頂点とする部分木を除外した木構造である。図６の例では、正当なクライアント端末が１つの差分木のみで被覆される。この差分木は、ノード１を頂点とする部分木から、ノード５を頂点とする部分木を除外したものである。
【００２７】
＜手順２＞得られた差分木に対して、鍵を割り当てる。ここでは、ノードｉを頂点とし、ノードｊを頂点とする部分木を除外された差分木に対して、コンテンツ鍵Ｋを、鍵ｋ（ｉ，ｊ)で暗号化する。ただし、ｋ（ｉ，ｊ)は、ラベルl（ｉ，ｊ)から、一方向性関数ｈを用いて、数８で導出される。
【００２８】
【数８】
2009044516.tif 000010
【００２９】
ここで得られた複数の暗号化鍵を連接したものを、ブロードキャスト鍵ブロックとする。図６の例では、ブロードキャスト鍵ブロックＢＫＢは、数９となる。
【００３０】
【数９】
2009044516.tif 000011
【００３１】
例えば、ノード１５に割り当てられているクライアント端末が保有しているラベルは、ｌ（１，２），ｌ（１，６），ｌ（１，１４），ｌ（３，６），ｌ（３，１４），ｌ（７，１４），ｌ（ＡＬＬ）である。これらのラベルから一方向性関数を利用して鍵を導出し、コンテンツ鍵Ｋを復号できる。はじめに、数１０としてラベルｌ（１，２）からラベルｌ（１，５）を導出する。
【００３２】
【数１０】
2009044516.tif 000012
【００３３】
次に、数１１として鍵ｋ（１，５）を導出する。一方で、無効化されている左から３番目のクライアント端末が保有しているラベルは、ｌ（１，３），ｌ（１，４），ｌ（１，１１），ｌ（２，４），ｌ（２，１１），ｌ（５，１１），ｌ（ＡＬＬ）であるが、鍵ｋ（１，５）を導出するためのラベルｌ（１，２）およびｌ（１，５）を保有しない。このため、コンテンツ鍵Ｋを復号することができない。
【００３４】
【数１１】
2009044516.tif 000013
【非特許文献１】Ｄａｌｉｔ  Ｎａｏｒ，Ｍｏｎｉ  Ｎａｏｒ，ａｎｄ  Ｊｅｆｆ  Ｌｏｔｓｐｉｅｃｈ，“Ｒｅｖｏｃａｔｉｏｎ  ａｎｄ  Ｔｒａｃｉｎｇ  Ｓｃｈｅｍｅｓ  ｆｏｒ  Ｓｔａｔｅｌｅｓｓ  Ｒｅｃｅｉｖｅｒｓ，”Ｐｒｏｃ  ｏｆ  Ｃｒｙｐｔ  ２００１，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ２１３９，ｐｐ．４１−６２，２００１．
【発明の開示】
【発明が解決しようとする課題】
【００３５】
しかしながら、上述のＣＳ法では、一般の木構造（ａ分木）を対象にしているのに対し、ＳＤ法は、２分木のみを対象にしていため、ブロードキャスト鍵ブロックのサイズが小さいものの一般化できていないという問題があった。
【００３６】
そこで、本発明は上述の課題に鑑みてなされたものであり、ＳＤ法の対象を多分木に拡張することで、より柔軟なクライアント端末の被覆が実現でき、ブロードキャスト鍵ブロックのサイズの軽減を図ることができるブロードキャスト暗号の生成方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００３７】
本発明は、上記の課題を解決するために、以下の事項を提案している。
（１）本発明は、一般の木構造（ａ分木）におけるＳＤ法を用いたブロードキャスト暗号の生成方法であって、該ａ分木の末端のノードにクライアント端末を割り当てる第１のステップと、木の全ノードに｜Ｋ｜ビットのラベルを割り当てて、一方向性関数を用いて、ラベルを生成する第２のステップと、各クライアント端末にラベルを割り当てる第３のステップと、すべての正当なクライアント端末を複数の差分木で被覆する第４のステップと、作成した各被覆に対して、コンテンツ鍵を暗号化し、該暗号化したコンテンツ鍵を連接してブロードキャスト鍵ブロックを生成する第５のステップと、を備えたことを特徴とするブロードキャスト暗号の生成方法を提案している。
【００３８】
この発明によれば、ａ分木の末端のノードにクライアント端末を割り当て、木の全ノードに｜Ｋ｜ビットのラベルを割り当てて、一方向性関数を用いて、ラベルを生成する。そして、各クライアント端末にラベルを割り当て、すべての正当なクライアント端末を複数の差分木で被覆し、作成した各被覆に対して、コンテンツ鍵を暗号化し、該暗号化したコンテンツ鍵を連接してブロードキャスト鍵ブロックを生成する。したがって、ＳＤ法を一般的な木構造にも適用できるとともに、ブロードキャスト鍵ブロックのサイズの軽減を図ることができる。
【００３９】
（２）本発明は、（１）のブロードキャスト暗号の生成方法について、前記一方向関数は、ラベル長ｎに対してｎ＋１倍の出力をする関数であり、ｈ（Ｌ）の先頭から｜Ｋ｜ビットを抜き出したものをｈ１（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈ２（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈ３（Ｌ）、・・・、（ａ−１）｜Ｋ｜＋１ビット目から、ａ｜Ｋ｜ビット目までを抜き出したものをｈａ（Ｌ）、最後の｜Ｋ｜ビットを抜き出したものを、ｈｋ（Ｌ）としたときに、ｈ１（Ｌ）、ｈ２（Ｌ）、・・・、ｈａ（Ｌ）をあるノードのラベルＬから、子ノードのラベルを導出するため用い、ｈｋ（Ｌ）をラベルＬからコンテンツ鍵を導出するために用いることを特徴とするブロードキャスト暗号の生成方法を提案している。
【００４０】
この発明によれば、一方向関数は、ラベル長ｎに対してｎ＋１倍の出力をする関数であり、ｈ（Ｌ）の先頭から｜Ｋ｜ビットを抜き出したものをｈ１（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈ２（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈ３（Ｌ）、・・・、（ａ−１）｜Ｋ｜＋１ビット目から、ａ｜Ｋ｜ビット目までを抜き出したものをｈａ（Ｌ）、最後の｜Ｋ｜ビットを抜き出したものを、ｈｋ（Ｌ）としたときに、ｈ１（Ｌ）、ｈ２（Ｌ）、・・・、ｈａ（Ｌ）をあるノードのラベルＬから、子ノードのラベルを導出するため用い、ｈｋ（Ｌ）をラベルＬからコンテンツ鍵を導出するために用いる。したがって、各クライアント端末が保有するラベルから一方向性関数を利用することにより、コンテンツ鍵を復号することができる。
【００４１】
（３）本発明は、一般の木構造（ａ分木）におけるＳＤ法を用いたブロードキャスト暗号の生成方法をコンピュータに実行させるためのプログラムであって、該ａ分木の末端のノードにクライアント端末を割り当てる第１のステップと、木の全ノードに｜Ｋ｜ビットのラベルを割り当てて、一方向性関数を用いて、ラベルを生成する第２のステップと、各クライアント端末にラベルを割り当てる第３のステップと、すべての正当なクライアント端末を複数の差分木で被覆する第４のステップと、作成した各被覆に対して、コンテンツ鍵を暗号化し、該暗号化したコンテンツ鍵を連接してブロードキャスト鍵ブロックを生成する第５のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００４２】
この発明によれば、ａ分木の末端のノードにクライアント端末を割り当て、木の全ノードに｜Ｋ｜ビットのラベルを割り当てて、一方向性関数を用いて、ラベルを生成する。そして、各クライアント端末にラベルを割り当て、すべての正当なクライアント端末を複数の差分木で被覆し、作成した各被覆に対して、コンテンツ鍵を暗号化し、該暗号化したコンテンツ鍵を連接してブロードキャスト鍵ブロックを生成する。したがって、ＳＤ法を一般的な木構造にも適用できるとともに、ブロードキャスト鍵ブロックのサイズの軽減を図ることができる。
【００４３】
（４）本発明は、（３）のプログラムについて、前記一方向関数は、ラベル長ｎに対してｎ＋１倍の出力をする関数であり、ｈ（Ｌ）の先頭から｜Ｋ｜ビットを抜き出したものをｈ１（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈ２（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈ３（Ｌ）、・・・、（ａ−１）｜Ｋ｜＋１ビット目から、ａ｜Ｋ｜ビット目までを抜き出したものをｈａ（Ｌ）、最後の｜Ｋ｜ビットを抜き出したものを、ｈｋ（Ｌ）としたときに、ｈ１（Ｌ）、ｈ２（Ｌ）、・・・、ｈａ（Ｌ）をあるノードのラベルＬから、子ノードのラベルを導出するため用い、ｈｋ（Ｌ）をラベルＬからコンテンツ鍵を導出するために用いることを特徴とするプログラムを提案している。
【００４４】
この発明によれば、一方向関数は、ラベル長ｎに対してｎ＋１倍の出力をする関数であり、ｈ（Ｌ）の先頭から｜Ｋ｜ビットを抜き出したものをｈ１（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈ２（Ｌ）、次の｜Ｋ｜ビットを抜き出したものをｈ３（Ｌ）、・・・、（ａ−１）｜Ｋ｜＋１ビット目から、ａ｜Ｋ｜ビット目までを抜き出したものをｈａ（Ｌ）、最後の｜Ｋ｜ビットを抜き出したものを、ｈｋ（Ｌ）としたときに、ｈ１（Ｌ）、ｈ２（Ｌ）、・・・、ｈａ（Ｌ）をあるノードのラベルＬから、子ノードのラベルを導出するため用い、ｈｋ（Ｌ）をラベルＬからコンテンツ鍵を導出するために用いる。したがって、各クライアント端末が保有するラベルから一方向性関数を利用することにより、コンテンツ鍵を復号することができる。
【発明の効果】
【００４５】
本発明によれば、ＳＤ法の対象を多分木に拡張することで、より柔軟なクライアント端末の被覆が実現でき、ブロードキャスト鍵ブロックのサイズの軽減を図ることができるという効果がある。
【発明を実施するための最良の形態】
【００４６】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００４７】
図１を用いて、本実施形態に係るブロードキャスト暗号の生成方法について説明する。
【００４８】
（１）ラベルの割り当て処理
＜ステップＳ１０１＞
まず、クライアント端末の総数をＮとする。そして、ａ分木の末端のノード（リーフノード）に、クライアント端末を割り当てる。ここで、Ｎ＝ａｈとならない場合は、Ｎ台の正当なクライアント端末、ａｈ−Ｎ(台)の無効化されたクライアント端末を配置するとみなせばよいので、Ｎ＝ａｈして一般性を失わない。以下の説明は、Ｎ＝ａｈして行う。
【００４９】
＜ステップＳ１０２＞
木の全ノードに｜Ｋ｜ビットのラベルｌ（ｘ，ｘ）を任意に割り当てる。その後、一方向性関数を用いて、ラベルを数１２のように生成する。
【００５０】
【数１２】
2009044516.tif 000014
【００５１】
＜ステップＳ１０３＞
クライアント端末に、ラベルを割り当てる。リーフノードｘに割り当てられたクライアント端末が保有するラベルの集合Ｌは、数１３のようになる。
【００５２】
【数１３】
2009044516.tif 000015
【００５３】
（２）ブロードキャスト鍵ブロックの構成方法
＜ステップＳ１０４＞
すべての正当なクライアント端末を、複数の差分木で被覆する。本方式における差分木とは、ノードｘを頂点とする部分木から、ノードｘの子孫のノードであるノードｙ１、ｙ２、・・・、ｙｍ  （ただし、１≦ｍ≦ａ−１）を頂点とする部分木を除外した木構造である。ここで、ノードｙ１、ｙ２、・・・、ｙｍは、同一のノードを親ノードとして持つものとする。すなわち、これらのノードは、兄弟の位置関係にある。
【００５４】
＜ステップＳ１０５＞
ブロードキャスト鍵ブロックの作成を行う。ステップＳ１０４で作成した各被覆に対し、コンテンツ鍵を暗号化する。ここでは、ノードｘを頂点とし、ノードｙ１、ｙ２、・・・、ｙｍを頂点とする部分木を除外した差分木に対して以下数１４の鍵を生成する。次に生成した鍵を用いて、コンテンツ鍵を暗号化する。これらの暗号化コンテンツ鍵を全て連接して、ブロードキャスト鍵ブロックとする。
【００５５】
【数１４】
2009044516.tif 000016
【００５６】
したがって、本実施形態に係るブロードキャスト暗号の生成方法によれば、ＳＤ法を一般的な木構造にも適用できるとともに、ブロードキャスト鍵ブロックのサイズの軽減を図ることができる。
【００５７】
＜実施例＞
次に、図２および図３を用いて、４分木の場合を例にとった実施例をしめす。
なお、２つの例は、前提条件として、各クライアント端末には、以下のラベルが割り当てられているものとする。
ｃ１：ｌ（１，３），ｌ（１，４），ｌ（１，５），ｌ（１，７），ｌ（１，８），ｌ（１，９），ｌ（２，７），ｌ（２，８），ｌ（２，９），ｌ（ＡＬＬ）
ｃ２：  ｌ（１，３），ｌ（１，４），ｌ（１，５），ｌ（１，６），ｌ（１，８），ｌ（１，９），ｌ（２，６），ｌ（２，８），ｌ（２，９），ｌ（ＡＬＬ）
ｃ３：  ｌ（１，３），ｌ（１，４），ｌ（１，５），ｌ（１，６），ｌ（１，７），ｌ（１，９），ｌ（２，６），ｌ（２，７），ｌ（２，９）,ｌ（ＡＬＬ）
ｃ４：  ｌ（１，３），ｌ（１，４），ｌ（１，５），ｌ（１，６），ｌ（１，７），ｌ（１，８），ｌ（２，６），ｌ（２，７），ｌ（２，８）,ｌ（ＡＬＬ）
ｃ５：ｌ（１，２），ｌ（１，４），ｌ（１，５），ｌ（１，１１），ｌ（１，１２），ｌ（１，１３），ｌ（３，１１），ｌ（３，１２），ｌ（３，１３）,ｌ（ＡＬＬ）
ｃ６：ｌ（１，２），ｌ（１，４），ｌ（１，５），ｌ（１，１０），ｌ（１，１２），ｌ（１，１３），ｌ（３，１０），ｌ（３，１２）,  ｌ（３，１３）,ｌ（ＡＬＬ）
ｃ７：ｌ（１，２），ｌ（１，４），ｌ（１，５），ｌ（１，１０），ｌ（１，１１），ｌ（１，１３），ｌ（３，１０），ｌ（３，１１），ｌ（３，１３）,ｌ（ＡＬＬ）
ｃ８：ｌ（１，２），ｌ（１，４），ｌ（１，５），ｌ（１，１０），ｌ（１，１１），ｌ（１，１２），ｌ（３，１０），ｌ（３，１１）,ｌ（３，１２）  ,ｌ（ＡＬＬ）
ｃ９：ｌ（１，２），ｌ（１，３），ｌ（１，５），ｌ（１，１５），ｌ（１，１６），ｌ（１，１７）,ｌ（４，１５）,ｌ（４，１６）,ｌ（４，１７）,ｌ（ＡＬＬ）
ｃ１０：ｌ（１，２），ｌ（１，３），ｌ（１，５），ｌ（１，１４），ｌ（１，１６），ｌ（１，１７），ｌ（４，１４），ｌ（４，１６）,ｌ（４，１７），ｌ（ＡＬＬ）
ｃ１１：ｌ（１，２），ｌ（１，３），ｌ（１，５），ｌ（１，１４），ｌ（１，１５），ｌ（１，１７），ｌ（４，１４），ｌ（４，１５），ｌ（４，１７），ｌ（ＡＬＬ）
ｃ１２：ｌ（１，２），ｌ（１，３），ｌ（１，５），ｌ（１，１４），ｌ（１，１５），ｌ（１，１６），ｌ（４，１４），ｌ（４，１５），ｌ（４，１６），ｌ（ＡＬＬ）
ｃ１３：ｌ（１，２），ｌ（１，３），ｌ（１，４），ｌ（１，１９），ｌ（１，２０），ｌ（１，２１），ｌ（５，１９），ｌ（５，２０），ｌ（５，２１），ｌ（ＡＬＬ）
ｃ１４：ｌ（１，２），ｌ（１，３），ｌ（１，４），ｌ（１，１８）,ｌ（１，２０），ｌ（１，２１），ｌ（５，１８），ｌ（５，２０）,ｌ（５，２１），ｌ（ＡＬＬ）
ｃ１５：ｌ（１，２），ｌ（１，３）,ｌ（１，４），ｌ（１，１８）,ｌ（１，１９），ｌ（１，２１）,ｌ（５，１８），ｌ（５，１９）,ｌ（５，２１），ｌ（ＡＬＬ）
ｃ１６：ｌ（１，２），ｌ（１，３），ｌ（１，４），ｌ（１，１８），ｌ（１，１９），ｌ（１，２０），ｌ（５，１８），ｌ（５，１９）,ｌ（５，２０），ｌ（ＡＬＬ）
【００５８】
＜実施例１＞
図２では、ｃ３、ｃ６、ｃ８、ｃ１０、ｃ１１、ｃ１２およびｃ１３が無効化されたクライアント端末であり、その他の端末が正当な端末である。この場合は、正当なクライアント端末は、4つの差分木で被覆される。
このとき、ブロードキャスト鍵ブロックＢＫＢは、数１５のようになる。
【００５９】
【数１５】
2009044516.tif 000017
【００６０】
ここで、正当なクライアント端末Ｃ１、ｃ２およびｃ４は、ラベルｌ（２，８）を保有しているので、このラベルから一方向性関数を利用して鍵ｋ（２，８）を、数１６のように導出して、コンテンツ鍵を復号できる。
【００６１】
【数１６】
2009044516.tif 000018
【００６２】
また、正当なクライアント端末ｃ５およびｃ７は、ラベルｌ（３，１１）、ラベルｌ（３，１３）をともに保有しているので、これらのラベルから一方向性関数を利用して鍵を、数１７のように導出し、コンテンツ鍵を復号できる。
【００６３】
【数１７】
2009044516.tif 000019
【００６４】
また、正当なクライアント端末ｃ９は、ラベルｌ（４，１５）,  ｌ（４，１６）およびｌ（４，１７）をすべて保有しているので、一方向性関数を利用し鍵を吸う１８のように導出し、コンテンツ鍵を復号できる。
【００６５】
【数１８】
2009044516.tif 000020
【００６６】
さらに、正当なクライアント端末ｃ１４、ｃ１５およびｃ１６は、ラベルｌ（５，１８）を保有しているので、このラベルから一方向性関数を利用して鍵ｋ（５，１８）を数１９のように導出し、コンテンツ鍵を復号できる。
【００６７】
【数１９】
2009044516.tif 000021
【００６８】
一方で、無効化されたクライアント端末c３は、ラベルｌ（２，８)を保持していないので、鍵ｋ（２，８）を導出できない。また、ラベルｌ（３，＊），  ｌ（４，＊），ｌ（５，＊）（＊は任意の整数）のいずれも保有しないので、鍵（数２０）、鍵（数２１）および鍵ｋ（５，８）のいずれも導出できない。ゆえに、コンテンツ鍵を復号できない。
【００６９】
【数２０】
2009044516.tif 000022
【００７０】
【数２１】
2009044516.tif 000023
【００７１】
また、無効化されたクライアント端末ｃ６およびｃ８は、ラベルｌ（３，１１）、ラベルｌ（３，１３）のいずれか一方のみを保有ので、導出に双方のラベルが必要となる鍵（数２２）を導出できない。また、ラベルｌ（２，＊）、ラベルｌ（４，＊）およびラベル  ｌ（５，＊)（＊は任意の整数）のいずれも保有しないので、鍵ｋ（２，８）、鍵（数２３）および鍵ｋ（５，８）のいずれも導出できない。ゆえに、コンテンツ鍵を復号できない。
【００７２】
【数２２】
2009044516.tif 000024
【００７３】
【数２３】
2009044516.tif 000025
【００７４】
さらに、無効化されたクライアント端末ｃ１０、ｃ１１およびc１２は、ラベルｌ（４，１５）、ラベルｌ（４，１６）およびラベルｌ（４，１７）のいずれか２つのみを保有ので、導出にこれら３つのラベルが全て必要となる鍵（数２４）を導出できない。また、ラベルｌ（２，＊）、ラベルｌ（３，＊）および  ラベルｌ（５，＊)（＊は任意の整数）のいずれも保有しないので、鍵ｋ（２，８）、鍵（数２５）および鍵ｋ（５，８）のいずれも導出できない。ゆえに、コンテンツ鍵を復号できない。
【００７５】
【数２４】
2009044516.tif 000026
【００７６】
【数２５】
2009044516.tif 000027
【００７７】
また、無効化されたクライアント端末ｃ１３は、ラベルｌ（５，１８）を保有しないので、鍵ｋ（５，１８）を導出できない。また、ラベルｌ（２，＊）、ラベルｌ（３，＊）およびラベル  ｌ（４，＊）（＊は任意の整数）のいずれも保有しないので、鍵ｋ（２，８）、鍵（数２６）および鍵（数２７）のいずれも導出できない。ゆえに、コンテンツ鍵を復号できない。
【００７８】
【数２６】
2009044516.tif 000028
【００７９】
【数２７】
2009044516.tif 000029
【００８０】
＜実施例２＞
図３では、ｃ１３およびｃ１４が無効化されたクライアント端末であり、その他の端末が正当な端末である。この場合は、正当なクライアント端末は、２つの差分木で被覆される。このとき、ブロードキャスト鍵ブロックＢＫＢは、数２８のようになる。
【００８１】
【数２８】
2009044516.tif 000030
【００８２】
正当なクライアント端末ｃ１、ｃ２、ｃ３、ｃ４、ｃ５、ｃ６、ｃ７、ｃ８、ｃ９、ｃ１０、ｃ１１およびｃ１２は、ラベルｌ（１，５）を保有しているので、このラベルから一方向性関数を利用して鍵（数２９）を、数３０から導出して、コンテンツ鍵を復号をできる。
【００８３】
【数２９】
2009044516.tif 000031
【００８４】
【数３０】
2009044516.tif 000032
【００８５】
また、正当なクライアント端末ｃ１５およびｃ１６は、ラベルｌ（１，１８）、ラベルｌ（１，１９）をともに保有しているので、これらのラベルから一方向性関数を利用して鍵（数３１）を、数３２から導出して、コンテンツ鍵を復号できる。
【００８６】
【数３１】
2009044516.tif 000033
【００８７】
【数３２】
2009044516.tif 000034
【００８８】
一方、無効化されたクライアント端末ｃ１３およびｃ１４は、ラベルｌ（１，１８）およびラベルｌ（１，１９）のいずれか一方のみを保有するので、導出にこれらのラベル双方を必要とする鍵（数３３）を導出できない。また、ラベルｌ（１，５）を保有していないため、ラベルｌ（１，１８）またはｌ（１，１９）を導出することもできない。ゆえに、コンテンツ鍵を復号できない。
【００８９】
【数３３】
2009044516.tif 000035
【００９０】
なお、ブロードキャスト暗号の生成方法の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを装置に読み込ませ、実行することによって本発明のブロードキャスト暗号の生成方法を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００９１】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００９２】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。更に、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００９３】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００９４】
【図１】本実施形態に係る処理フローである。
【図２】実施例として４分木型ＳＤ法を例示した説明図である。
【図３】実施例として４分木型ＳＤ法を例示した説明図である。
【図４】従来例に係るブロードキャスト暗号の概念図である。
【図５】従来例に係るＣＳ法の概念図である。
【図６】従来例に係るＳＤ法の概念図である。
【図１】
2009044516.tif 000036
【図２】
2009044516.tif 000037
【図３】
2009044516.tif 000038
【図４】
2009044516.tif 000039
【図５】
2009044516.tif 000040
【図６】
2009044516.tif 000041