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