(57)【要約】【課題】従来のＳＤ法が有する結託攻撃に対する耐性を維持しつつ、通信量および利用者が保持するラベル数を削減する。【解決手段】コンテンツサーバから利用者端末にコンテンツを配信するコンテンツ配信サービスにおいて、３分木の木構造を構成し、コンテンツ鍵を３分木のリーフノードに割り当てられた正当な利用者端末にのみ配布する３分木型ＳＤ法であって、正当な利用者端末の部分集合の集合Ｃを求める部分集合抽出処理と、リーフノードに割り当てられた各利用者端末に、ラベルを割り当てるラベル割り当て処理と、コンテンツサーバが平文メッセージを暗号化する暗号化処理と、利用者端末が、受信した暗号化されたメッセージを復号化する復号化処理とを有する。【選択図】図１
2009284220.tif 000002
【特許請求の範囲】
【請求項１】
コンテンツサーバから利用者端末にコンテンツを配信するコンテンツ配信サービスにおいて、３分木の木構造を構成し、コンテンツ鍵を前記３分木のリーフノードに割り当てられた正当な利用者端末にのみ配布する３分木型ＳＤ法であって、
前記正当な利用者端末の部分集合の集合Ｃを求める部分集合抽出処理と、
前記リーフノードに割り当てられた各利用者端末に、ラベルを割り当てるラベル割り当て処理と、
前記コンテンツサーバが平文メッセージを暗号化する暗号化処理と、
前記利用者端末が、受信した前記暗号化されたメッセージを復号化する復号化処理と、
を有することを特徴とする３分木型ＳＤ法。
【請求項２】
前記部分集合Ｃに、ｉを頂点とする部分木のリーフノードに割り当てられた前記利用者端末の集合から、ｊ１を頂点とする部分木のリーフノードに割り当てられた端末の集合を除外した部分集合Ｄｉ、ｊ１と、ｉを頂点とする部分木のリーフノードに割り当てられた前記利用者端末の集合から、ｊ１およびｊ２を頂点とする２つの部分木のリーフノードに割り当てられた端末の集合を除外したＤｉ、ｊ１＋ｊ２とがあり、
前記部分集合抽出処理が、
すべての兄弟ノードがリーフノードであるようなノードｊ１、・・・、ｊｋ を検出する第１のステップと、
ｋ＝３である場合に、これらのノードｊ１、・・・、ｊ３を木Ｔ から除去する第２のステップと、
ｋ＜３である場合に、兄弟を持つ祖先ノードのうち、最も下位に位置するノードｉ を選択し、これをＣ：＝Ｃ∪{Ｄｉ、ｊ１＋・・・＋ｊｋ} と定義して、ノードｉの子孫ノードを全て木Ｔから削除する第３のステップと、
ｋ＜３である場合に、兄弟を持つ祖先ノードが見つからなかったときに、これをＣ：＝Ｃ∪{Ｄｒｏｏｔ、ｊ１＋・・・＋ｊｋ}と定義して、ルート以外の全てのノードを、木Ｔから削除する第４のステップと、
木Ｔが単一のノードになるまで、前記第１のステップから第４のステップまでを繰り返し実行する第５のステップと、
を有することを特徴とする請求項１に記載の３分木型ＳＤ法。
【請求項３】
前記ラベル割り当て処理が、
３分木を生成し、リーフノードに各利用者端末を割り当てる第１のステップと、
リーフノード以外のノードに、初期ラベルを任意に割り当てる第２のステップと、
各利用者端末にラベルを割り当てる第３のステップと、
を有することを特徴とする請求項１に記載の３分木型ＳＤ法。
【請求項４】
前記暗号化処理が、
メッセージを暗号化するためのセッション鍵を選ぶ第１のステップと、
前記部分集合抽出処理を用いて、全ての正当な利用者端末の集合を重複のない部分集合に分割する第２のステップと、
前記セッション鍵を各部分集合に割り当てられた鍵でそれぞれ暗号化し、データをすべての利用者端末に配布する第３のステップと、
を有することを特徴とする請求項１に記載の３分木型ＳＤ法。
【請求項５】
前記復号化処理が、
暗号化されたデータを受信した利用者端末自らが所属する部分集合を検索する第１のステップと、
ラベルを用いて、前記検索した部分集合に対応する鍵を導出する第２のステップと、
セッション鍵を暗号化する関数を前記導出した鍵を用いて復号し、セッション鍵を取得する第３のステップと、
メッセージを暗号化する関数を取得したセッション鍵を用いて復号し、メッセージを得る第４のステップと、
を有することを特徴とする請求項１に記載の３分木型ＳＤ法。
【請求項６】
コンテンツサーバから利用者端末にコンテンツを配信するコンテンツ配信サービスにおいて、３分木の木構造を構成し、コンテンツ鍵を前記３分木のリーフノードに割り当てられた正当な利用者端末にのみ配布する３分木型ＳＤ法をコンピュータに実行させるためのプログラムであって、
前記正当な利用者端末の部分集合の集合Ｃを求める部分集合抽出処理と、
前記リーフノードに割り当てられた各利用者端末に、ラベルを割り当てるラベル割り当て処理と、
前記コンテンツサーバが平文メッセージを暗号化する暗号化処理と、
前記利用者端末が、受信した前記暗号化されたメッセージを復号化する復号化処理と、
をコンピュータに実行させるためのプログラム。
【請求項７】
前記部分集合Ｃに、ｉを頂点とする部分木のリーフノードに割り当てられた前記利用者端末の集合から、ｊ１を頂点とする部分木のリーフノードに割り当てられた端末の集合を除外した部分集合Ｄｉ、ｊ１と、ｉを頂点とする部分木のリーフノードに割り当てられた前記利用者端末の集合から、ｊ１およびｊ２を頂点とする２つの部分木のリーフノードに割り当てられた端末の集合を除外したＤｉ、ｊ１＋ｊ２とがあり、
前記部分集合抽出処理が、
すべての兄弟ノードがリーフノードであるようなノードｊ１、・・・、ｊｋ を検出する第１のステップと、
ｋ＝３である場合に、これらのノードｊ１、・・・、ｊ３を木Ｔ から除去する第２のステップと、
ｋ＜３である場合に、兄弟を持つ祖先ノードのうち、最も下位に位置するノードｉ を選択し、これをＣ：＝Ｃ∪{Ｄｉ、ｊ１＋・・・＋ｊｋ} と定義して、ノードｉの子孫ノードを全て木Ｔから削除する第３のステップと、
ｋ＜３である場合に、兄弟を持つ祖先ノードが見つからなかったときに、これをＣ：＝Ｃ∪{Ｄｒｏｏｔ、ｊ１＋・・・＋ｊｋ}と定義して、ルート以外の全てのノードを、木Ｔから削除する第４のステップと、
木Ｔが単一のノードになるまで、前記第１のステップから第４のステップまでを繰り返し実行する第５のステップと、
をコンピュータに実行させるための請求項６に記載のプログラム。
【請求項８】
前記ラベル割り当て処理が、
３分木を生成し、リーフノードに各利用者端末を割り当てる第１のステップと、
リーフノード以外のノードに、初期ラベルを任意に割り当てる第２のステップと、
各利用者端末にラベルを割り当てる第３のステップと、
をコンピュータに実行させるための請求項６に記載のプログラム。
【請求項９】
前記暗号化処理が、
メッセージを暗号化するためのセッション鍵を選ぶ第１のステップと、
前記部分集合抽出処理を用いて、全ての正当な利用者端末の集合を重複のない部分集合に分割する第２のステップと、
前記セッション鍵を各部分集合に割り当てられた鍵でそれぞれ暗号化し、データをすべての利用者端末に配布する第３のステップと、
をコンピュータに実行させるための請求項６に記載のプログラム。
【請求項１０】
前記復号化処理が、
暗号化されたデータを受信した利用者端末自らが所属する部分集合を検索する第１のステップと、
ラベルを用いて、前記検索した部分集合に対応する鍵を導出する第２のステップと、
セッション鍵を暗号化する関数を前記導出した鍵を用いて復号し、セッション鍵を取得する第３のステップと、
メッセージを暗号化する関数を取得したセッション鍵を用いて復号し、メッセージを得る第４のステップと、
をコンピュータに実行させるための請求項６に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、従来のＳＤ法およびプログラムを改良し、結託攻撃に耐性のある効率的な放送型暗号を構成する３分木型ＳＤ法およびプログラムに関する。
【背景技術】
【０００２】
コンテンツ配信サービスにおいては、著作権保護のため、コンテンツを暗号化して配布することが必要である。コンテンツを暗号化する方法として、コンテンツ鍵を用いた暗号化方法が知られている。また、コンテンツ鍵を正当なクライアント端末のみに配布するための技術として、ブロードキャスト暗号が知られている。
【０００３】
ブロードキャスト暗号においては、各クライアント端末に、複数の鍵（鍵束）を事前に格納する。この鍵束は、クライアント端末ごとに異なり、更新されることはない。鍵管理サーバは、無効化されたクライアント端末のリストに基づき、コンテンツ鍵を暗号化し、ブロードキャスト鍵ブロックを作成する。そして、作成したブロードキャスト鍵ブロックを、各クライアント端末に配布する。
【０００４】
ブロードキャスト鍵ブロックを受信したクライアント端末は、自身に格納されている鍵束を用いてコンテンツ鍵の復号を試みる。このとき、正当なクライアント端末は、ブロードキャスト鍵ブロックから、コンテンツ鍵を正しく復号できる。一方で、無効化されたクライアント端末は、ブロードキャスト鍵ブロックから、コンテンツ鍵を復号できない。図７にブロードキャスト暗号の概念図を示す。
【０００５】
ところで、ブロードキャスト暗号を実現する最も自明な方式として、クライアント端末ごとに異なる個別鍵を格納しておき、コンテンツ鍵を各個別鍵で暗号化したものを、ブロードキャスト鍵ブロックとする方法がある。しかしながら、本方式では、ブロードキャスト鍵ブロックがクライアント端末の総数に比例し、増大するという課題がある。
【０００６】
そのため、非特許文献１に示されるように、木構造に基づく鍵の階層化を行い、ブロードキャスト鍵ブロックを構成するＣｏｍｐｌｅｔｅ  Ｓｕｂｔｒｅｅ  Ｍｅｔｈｏｄ（ＣＳ法）が提案されている。本方式においては、前記の方式と比較して、ブロードキャスト鍵ブロックのサイズを削減できるという特徴がある。
【０００７】
しかしながら、本方式では、ブロードキャスト鍵ブロックのサイズが、無効化されたクライアント端末の数に依存し、増大するという課題がある。つまり、木構造の次数をａ、クライアント端末の総数をＮ、無効化されたクライアント端末の数をｒ、コンテンツ鍵Ｋのサイズを｜Ｋ｜とすると、ブロードキャスト鍵ブロックのサイズは、数１となることが示されている。
【０００８】
【数１】
2009284220.tif 000003
【０００９】
そこで、非特許文献１では、差分木（ｓｕｂｓｅｔ  ｄｉｆｆｅｒｅｎｃｅ  ｔｒｅｅ）を用いて、ブロードキャスト鍵ブロックを構成するＳｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ  Ｍｅｔｈｏｄ（ＳＤ法）が提案されている。このＳＤ法においては、ブロードキャストブロックのサイズは、最大で、（２ｒ−１）｜Ｋ｜であり、平均で、２ｌｏｇ２・ｒ｜Ｋ｜であることが示されている。
【非特許文献１】Ｄａｌｉｔ  Ｎａｏｒ，Ｍｏｎｉ  Ｎａｏｒ，ａｎｄＪｅｆｆ  Ｌｏｔｓｐｉｅｃｈ，“Ｒｅｖｏｃａｔｉｏｎ  ａｎｄ  Ｔｒａｃｉｎｇ Ｓｃｈｅｍｅｓ  ｆｏｒ Ｓｔａｔｅｌｅｓｓ  Ｒｅｃｅｉｖｅｒｓ，”Ｐｒｏｃ．ｏｆ  Ｃｒｙｐｔ  ２００１，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ２１３９，ｐｐ．４１−６２，２００１．
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、従来のＳＤ法では、結託攻撃に耐性のある方法であるものの、２分木のみを対象とするため、通信量および利用者の保持するラベル数の観点からは、必ずしも最適ではないという問題があった。
【００１１】
そこで、本発明は、上述の課題に鑑みてなされたものであり、従来のＳＤ法が有する結託攻撃に対する耐性を維持しつつ、通信量および利用者が保持するラベル数を削減する放送型暗号化方式の３分木型ＳＤ法およびプログラム提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は、上記の課題を解決するために、以下の事項を提案している。
【００１３】
（１）本発明は、コンテンツサーバから利用者端末にコンテンツを配信するコンテンツ配信サービスにおいて、３分木の木構造を構成し、コンテンツ鍵を前記３分木のリーフノードに割り当てられた正当な利用者端末にのみ配布する３分木型ＳＤ法であって、前記正当な利用者端末の部分集合の集合Ｃを求める部分集合抽出処理と、前記リーフノードに割り当てられた各利用者端末に、ラベルを割り当てるラベル割り当て処理と、前記コンテンツサーバが平文メッセージを暗号化する暗号化処理と、前記利用者端末が、受信した前記暗号化されたメッセージを復号化する復号化処理と、を有することを特徴とする３分木型ＳＤ法を提案している。
【００１４】
この発明によれば、正当な利用者端末の部分集合の集合Ｃを求める部分集合抽出処理と、リーフノードに割り当てられた各利用者端末に、ラベルを割り当てるラベル割り当て処理と、コンテンツサーバが平文メッセージを暗号化する暗号化処理と、利用者端末が、受信した暗号化されたメッセージを復号化する復号化処理とから構成されているため、従来のＳＤ法が有する結託攻撃に対する耐性を維持しつつ、通信量および利用者が保持するラベル数を削減することができる。
【００１５】
（２）本発明は、（１）の３分木型ＳＤ法について、前記部分集合Ｃに、ｉを頂点とする部分木のリーフノードに割り当てられた前記利用者端末の集合から、ｊ１を頂点とする部分木のリーフノードに割り当てられた端末の集合を除外した部分集合Ｄｉ、ｊ１と、ｉを頂点とする部分木のリーフノードに割り当てられた前記利用者端末の集合から、ｊ１およびｊ２を頂点とする２つの部分木のリーフノードに割り当てられた端末の集合を除外したＤｉ、ｊ１＋ｊ２とがあり、前記部分集合抽出処理が、すべての兄弟ノードがリーフノードであるようなノードｊ１、・・・、ｊｋ
を検出する第１のステップと、ｋ＝３である場合に、これらのノードｊ１、・・・、ｊ３を木Ｔ から除去する第２のステップと、ｋ＜３である場合に、兄弟を持つ祖先ノードのうち、最も下位に位置するノードｉ
を選択し、これをＣ：＝Ｃ∪{Ｄｉ、ｊ１＋・・・＋ｊｋ}
と定義して、ノードｉの子孫ノードを全て木Ｔから削除する第３のステップと、ｋ＜３である場合に、兄弟を持つ祖先ノードが見つからなかったときに、これをＣ：＝Ｃ∪{Ｄｒｏｏｔ、ｊ１＋・・・＋ｊｋ}と定義して、ルート以外の全てのノードを、木Ｔから削除する第４のステップと、木Ｔが単一のノードになるまで、前記第１のステップから第４のステップまでを繰り返し実行する第５のステップと、を有することを特徴とする３分木型ＳＤ法を提案している。
【００１６】
この発明によれば、部分集合Ｃに、ｉを頂点とする部分木のリーフノードに割り当てられた利用者端末の集合から、ｊ１を頂点とする部分木のリーフノードに割り当てられた端末の集合を除外した部分集合Ｄｉ、ｊ１と、ｉを頂点とする部分木のリーフノードに割り当てられた利用者端末の集合から、ｊ１およびｊ２を頂点とする２つの部分木のリーフノードに割り当てられた端末の集合を除外したＤｉ、ｊ１＋ｊ２とがあり、部分集合抽出処理が、すべての兄弟ノードがリーフノードであるようなノードｊ１、・・・、ｊｋ
を検出し、ｋ＝３である場合に、これらのノードｊ１、・・・、ｊ３を木Ｔ から除去し、ｋ＜３である場合に、兄弟を持つ祖先ノードのうち、最も下位に位置するノードｉ を選択し、これをＣ：＝Ｃ∪{Ｄｉ、ｊ１＋・・・＋ｊｋ} と定義して、ノードｉの子孫ノードを全て木Ｔから削除する。一方、ｋ＜３である場合に、兄弟を持つ祖先ノードが見つからなかったときに、これをＣ：＝Ｃ∪{Ｄｒｏｏｔ、ｊ１＋・・・＋ｊｋ}と定義して、ルート以外の全てのノードを、木Ｔから削除し、木Ｔが単一のノードになるまで、第１のステップから第４のステップまでを繰り返し実行する。したがって、正当な利用者端末を、部分集合で被覆し、それぞれの部分集合に対し、鍵を割り当てることができる。
【００１７】
（３）本発明は、（１）の３分木型ＳＤ法について、前記ラベル割り当て処理が、３分木を生成し、リーフノードに各利用者端末を割り当てる第１のステップと、リーフノード以外のノードに、初期ラベルを任意に割り当てる第２のステップと、各利用者端末にラベルを割り当てる第３のステップと、を有することを特徴とする３分木型ＳＤ法を提案している。
【００１８】
この発明によれば、ラベル割り当て処理が、３分木を生成し、リーフノードに各利用者端末を割り当て、リーフノード以外のノードに、初期ラベルを任意に割り当てる。そして、各利用者端末にラベルを割り当てる。したがって、ラベル数を削減しつつ、利用者端末にラベルを割り当てることができる。
【００１９】
（４）本発明は、（１）の３分木型ＳＤ法について、前記暗号化処理が、メッセージを暗号化するためのセッション鍵を選ぶ第１のステップと、前記部分集合抽出処理を用いて、全ての正当な利用者端末の集合を重複のない部分集合に分割する第２のステップと、前記セッション鍵を各部分集合に割り当てられた鍵でそれぞれ暗号化し、データをすべての利用者端末に配布する第３のステップと、を有することを特徴とする３分木型ＳＤ法を提案している。
【００２０】
この発明によれば、暗号化処理が、メッセージを暗号化するためのセッション鍵を選択し、部分集合抽出処理を用いて、全ての正当な利用者端末の集合を重複のない部分集合に分割する。そして、セッション鍵を各部分集合に割り当てられた鍵でそれぞれ暗号化し、データをすべての利用者端末に配布する。したがって、重複のない部分集合に対応する個別の鍵を割り当てて、その個別の鍵により、暗号化を行うため、利用者間の結託を的確に防止することができる。
【００２１】
（５）本発明は、（１）の３分木型ＳＤ法について、前記復号化処理が、暗号化されたデータを受信した利用者端末自らが所属する部分集合を検索する第１のステップと、ラベルを用いて、前記検索した部分集合に対応する鍵を導出する第２のステップと、セッション鍵を暗号化する関数を前記導出した鍵を用いて復号し、セッション鍵を取得する第３のステップと、メッセージを暗号化する関数を取得したセッション鍵を用いて復号し、メッセージを得る第４のステップと、を有することを特徴とする３分木型ＳＤ法を提案している。
【００２２】
この発明によれば、復号化処理が、暗号化されたデータを受信した利用者端末自らが所属する部分集合を検索し、ラベルを用いて、検索した部分集合に対応する鍵を導出する。そして、セッション鍵を暗号化する関数を導出した鍵を用いて復号し、セッション鍵を取得し、メッセージを暗号化する関数を取得したセッション鍵を用いて復号し、メッセージを得る。したがって、部分集合を検索し、ラベルを用いて、検索した部分集合に対応する鍵を導出して、メッセージを復号するためのセッション鍵を取得することから、利用者間の結託を的確に防止することができる。
【００２３】
（６）本発明は、コンテンツサーバから利用者端末にコンテンツを配信するコンテンツ配信サービスにおいて、３分木の木構造を構成し、コンテンツ鍵を前記３分木のリーフノードに割り当てられた正当な利用者端末にのみ配布する３分木型ＳＤ法をコンピュータに実行させるためのプログラムであって、前記正当な利用者端末の部分集合の集合Ｃを求める部分集合抽出処理と、前記リーフノードに割り当てられた各利用者端末に、ラベルを割り当てるラベル割り当て処理と、前記コンテンツサーバが平文メッセージを暗号化する暗号化処理と、前記利用者端末が、受信した前記暗号化されたメッセージを復号化する復号化処理と、をコンピュータに実行させるためのプログラムを提案している。
【００２４】
この発明によれば、正当な利用者端末の部分集合の集合Ｃを求める部分集合抽出処理と、リーフノードに割り当てられた各利用者端末に、ラベルを割り当てるラベル割り当て処理と、コンテンツサーバが平文メッセージを暗号化する暗号化処理と、利用者端末が、受信した暗号化されたメッセージを復号化する復号化処理とから構成されているため、従来のＳＤ法が有する結託攻撃に対する耐性を維持しつつ、通信量および利用者が保持するラベル数を削減することができる。
【００２５】
（７）本発明は、（６）のプログラムについて、前記部分集合Ｃに、ｉを頂点とする部分木のリーフノードに割り当てられた前記利用者端末の集合から、ｊ１を頂点とする部分木のリーフノードに割り当てられた端末の集合を除外した部分集合Ｄｉ、ｊ１と、ｉを頂点とする部分木のリーフノードに割り当てられた前記利用者端末の集合から、ｊ１およびｊ２を頂点とする２つの部分木のリーフノードに割り当てられた端末の集合を除外したＤｉ、ｊ１＋ｊ２とがあり、前記部分集合抽出処理が、すべての兄弟ノードがリーフノードであるようなノードｊ１、・・・、ｊｋ
を検出する第１のステップと、ｋ＝３である場合に、これらのノードｊ１、・・・、ｊ３を木Ｔ から除去する第２のステップと、ｋ＜３である場合に、兄弟を持つ祖先ノードのうち、最も下位に位置するノードｉ
を選択し、これをＣ：＝Ｃ∪{Ｄｉ、ｊ１＋・・・＋ｊｋ}
と定義して、ノードｉの子孫ノードを全て木Ｔから削除する第３のステップと、ｋ＜３である場合に、兄弟を持つ祖先ノードが見つからなかったときに、これをＣ：＝Ｃ∪{Ｄｒｏｏｔ、ｊ１＋・・・＋ｊｋ}と定義して、ルート以外の全てのノードを、木Ｔから削除する第４のステップと、木Ｔが単一のノードになるまで、前記第１のステップから第４のステップまでを繰り返し実行する第５のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００２６】
この発明によれば、部分集合Ｃに、ｉを頂点とする部分木のリーフノードに割り当てられた利用者端末の集合から、ｊ１を頂点とする部分木のリーフノードに割り当てられた端末の集合を除外した部分集合Ｄｉ、ｊ１と、ｉを頂点とする部分木のリーフノードに割り当てられた利用者端末の集合から、ｊ１およびｊ２を頂点とする２つの部分木のリーフノードに割り当てられた端末の集合を除外したＤｉ、ｊ１＋ｊ２とがあり、部分集合抽出処理が、すべての兄弟ノードがリーフノードであるようなノードｊ１、・・・、ｊｋ
を検出し、ｋ＝３である場合に、これらのノードｊ１、・・・、ｊ３を木Ｔ から除去し、ｋ＜３である場合に、兄弟を持つ祖先ノードのうち、最も下位に位置するノードｉ を選択し、これをＣ：＝Ｃ∪{Ｄｉ、ｊ１＋・・・＋ｊｋ} と定義して、ノードｉの子孫ノードを全て木Ｔから削除する。一方、ｋ＜３である場合に、兄弟を持つ祖先ノードが見つからなかったときに、これをＣ：＝Ｃ∪{Ｄｒｏｏｔ、ｊ１＋・・・＋ｊｋ}と定義して、ルート以外の全てのノードを、木Ｔから削除し、木Ｔが単一のノードになるまで、第１のステップから第４のステップまでを繰り返し実行する。したがって、正当な利用者端末を、部分集合で被覆し、それぞれの部分集合に対し、鍵を割り当てることができる。
【００２７】
（８）本発明は、（６）のプログラムについて、前記ラベル割り当て処理が、３分木を生成し、リーフノードに各利用者端末を割り当てる第１のステップと、リーフノード以外のノードに、初期ラベルを任意に割り当てる第２のステップと、各利用者端末にラベルを割り当てる第３のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００２８】
この発明によれば、ラベル割り当て処理が、３分木を生成し、リーフノードに各利用者端末を割り当て、リーフノード以外のノードに、初期ラベルを任意に割り当てる。そして、各利用者端末にラベルを割り当てる。したがって、ラベル数を削減しつつ、利用者端末にラベルを割り当てることができる。
【００２９】
（９）本発明は、（６）のプログラムについて、前記暗号化処理が、メッセージを暗号化するためのセッション鍵を選ぶ第１のステップと、前記部分集合抽出処理を用いて、全ての正当な利用者端末の集合を重複のない部分集合に分割する第２のステップと、前記セッション鍵を各部分集合に割り当てられた鍵でそれぞれ暗号化し、データをすべての利用者端末に配布する第３のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００３０】
この発明によれば、暗号化処理が、メッセージを暗号化するためのセッション鍵を選択し、部分集合抽出処理を用いて、全ての正当な利用者端末の集合を重複のない部分集合に分割する。そして、セッション鍵を各部分集合に割り当てられた鍵でそれぞれ暗号化し、データをすべての利用者端末に配布する。したがって、重複のない部分集合に対応する個別の鍵を割り当てて、その個別の鍵により、暗号化を行うため、利用者間の結託を的確に防止することができる。
【００３１】
（１０）本発明は、（６）のプログラムについて、前記復号化処理が、暗号化されたデータを受信した利用者端末自らが所属する部分集合を検索する第１のステップと、ラベルを用いて、前記検索した部分集合に対応する鍵を導出する第２のステップと、セッション鍵を暗号化する関数を前記導出した鍵を用いて復号し、セッション鍵を取得する第３のステップと、メッセージを暗号化する関数を取得したセッション鍵を用いて復号し、メッセージを得る第４のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００３２】
この発明によれば、復号化処理が、暗号化されたデータを受信した利用者端末自らが所属する部分集合を検索し、ラベルを用いて、検索した部分集合に対応する鍵を導出する。そして、セッション鍵を暗号化する関数を導出した鍵を用いて復号し、セッション鍵を取得し、メッセージを暗号化する関数を取得したセッション鍵を用いて復号し、メッセージを得る。したがって、部分集合を検索し、ラベルを用いて、検索した部分集合に対応する鍵を導出して、メッセージを復号するためのセッション鍵を取得することから、利用者間の結託を的確に防止することができる。
【発明の効果】
【００３３】
本発明によれば、従来のＳＤ法が有する結託攻撃に対する耐性を維持しつつ、通信量および利用者が保持するラベル数を削減することができるという効果がある。具体的には、安全性、および利用者端末における計算量を保ちつつ、従来技術と比較し、通信量を約１２パーセント、ラベル数を約２０パーセント削減できた。
【発明を実施するための最良の形態】
【００３４】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００３５】
図１から図８を用いて、本発明の実施形態について説明する。
【００３６】
＜３分木型ＳＤ法の処理＞
本発明に係る３分木型ＳＤ法は、図１に示すように、正当な利用者端末の部分集合の集合Ｃを求める部分集合抽出処理（ステップＳ１０１）と、リーフノードに割り当てられた各利用者端末に、ラベルを割り当てるラベル割り当て処理（ステップＳ１０２）と、コンテンツサーバが平文メッセージを暗号化する暗号化処理（ステップＳ１０３）と、利用者端末が、受信した暗号化されたメッセージを復号化する復号化処理（ステップＳ１０４）とからなる。以下、それぞれの処理について、詳細に説明する。なお、本実施形態においては、暗号プリミティブとして次のものを用いる。「メッセージを暗号化するための関数Ｆ」、「セッション鍵を暗号化するための関数Ｅ」、「ハッシュ関数ｈ、ｈｋｅｙ、ｈ１、ｈ２
およびｈ３」
【００３７】
＜部分集合抽出処理＞
部分集合抽出処理について、図２から図４を用いて、説明する。
本実施形態では、各利用者端末（正当な端末、無効化端末を含む）を、木のリーフノードに割り当てる。正当な利用者端末を、部分集合Ｓｎで被覆し、それぞれの部分集合に対し、鍵を割り当てる。部分集合のパターンとしては、下記の２つがある。図３
は、ｉを頂点とする部分木のリーフノードに割り当てられた利用者端末の集合から、ｊ１ を頂点とする部分木のリーフノードに割り当てられた端末の集合を除外したものであり、Ｄ＿｛ｉ,ｊ１｝ と表記する。図４は、ｉを頂点とする部分木のリーフノードに割り当てられた利用者端末の集合から、ｊ１およびｊ２ を頂点とする２つの部分木のリーフノードに割り当てられた端末の集合を除外したものであり、Ｄ＿｛ｉ,ｊ１＋ｊ２｝と表記する。
【００３８】
正当な利用者端末の部分集合の集合Ｃは、以下の手順を用いて求める。
ここで、Ｃ ← φ（空集合）、Ｔ←ＳＴ（Ｒ）とする。ただし、ＳＴ（Ｒ）は、無効化した利用者端末が割り当てられているリーフノード、およびその先祖ノードから構成される部分木である。
【００３９】
図２に示すように、以下の処理を、木Ｔが、単一のノードになるまで繰り返す。
（１）すべての兄弟ノードがリーフノードであるようなノードｊ１、・・・、ｊｋ を検出する。
（２）ｋ＝３である場合に、これらのノードｊ１、・・・、ｊ３を木Ｔ から除去する。
（３）ｋ＜３である場合に、兄弟を持つ祖先ノードのうち、最も下位に位置するノードｉ を選択し、これをＣ：＝Ｃ∪{Ｄｉ、ｊ１＋・・・＋ｊｋ} と定義して、ノードｉの子孫ノードを全て木Ｔから削除する。
（４）ｋ＜３である場合に、兄弟を持つ祖先ノードが見つからなかったときに、これをＣ：＝Ｃ∪{Ｄｒｏｏｔ、ｊ１＋・・・＋ｊｋ}と定義して、ルート以外の全てのノードを、木Ｔから削除する。
【００４０】
＜ラベル割り当て処理＞
ラベル割り当て処理について、図５および図６を用いて、説明する。
図５に示すように、まず、３分木を生成し、リーフノードに各利用者端末を割り当てる（ステップＳ３０１）。次に、リーフノード以外のノードに、初期ラベルを任意に割り当てる（ステップＳ３０２）。ここで、頂点ｕに割り当てられる初期ラベルを、ｌ（ｕ、
ｕ）とする。この方式で使われるその他のラベルは、全てこれらの初期ラベルから、ハッシュ関数ｈ１、ｈ２、ｈ３、およびｈを用いて導出できる。ｗ が、ｖの左からｎ番目の子ノードである場合には、ｌ（ｕ、ｗ）＝ｈｎ（ｈ（ｌ（ｕ, ｖ））  ｎ＝１、２、３となる。
【００４１】
そして、各利用者端末にラベルを割り当てる（ステップＳ３０３）。ノードｕに割り当てられた利用者端末には、下記の集合に含まれるラベル
Ｌａｂｅｌ（ｕ）＝｛ｈ（ｌ（ｘ、ｙ））｜ｘ  ∈  Ｐａｔｈ（ｒｏｏｔ, ｕ）−｛ｕ｝、
ｙ＝ｌｅｆｔ（ｖ） ただし、ｖ ∈ Ｐａｔｈ（ｘ、ｕ）￥｛ｘ｝
∪ ｛ｌ（ｘ、ｙ）｜ｕ ∈ Ｐａｔｈ（ｒｏｏｔ、ｕ）−｛ｕ｝、ｙ ＝ ｒｉｇｈｔ（ｖ） ただし、ｖ ∈ Ｐａｔｈ（ｘ、ｕ）−｛ｘ｝
∪ ｛ｌ（ａｌｌ ）｝
が与えられる。ここで、Ｐａｔｈ（ｕ、ｖ）は、ノードｕからｖにいたる経路上に存在するノードの集合（ただし、ｕおよびｖを含む）を指す。また、ｌｅｆｔ（ｕ）は、ノードｕの左の兄弟ノードを指し、ｒｉｇｈｔ（ｕ）は、ｕの右の兄弟ノードを指す。したがって、ｕが右端のノードである場合は、ｒｉｇｈｔ（ｕ）は左端のノードであり、ｕが左端のノードである場合は、ｌｅｆｔ（ｕ）は、右端のノードである。また、ｌ（ａｌｌ
） は、無効化端末がない場合に用いる特別なラベルである。図６に、ラベルの割り当て例を示す。
【００４２】
＜暗号処理＞
暗号処理について、図７を用いて、説明する。
なお、この処理は、サーバが平文メッセージＭ に対して行なう処理である。
【００４３】
まず、平文メッセージＭを暗号化するためのセッション鍵Ｋを選ぶ（ステップＳ４０１）。次に、部分集合抽出処理を用いて、全ての正当な利用者端末の集合Ｎ−Ｒを重複のない部分集合Ｓ１、・・・、Ｓｗに分割する（ステップＳ４０２）。ここで、Ｌ１、・・・、
Ｌｗ を各部分集合に割り当てられた鍵とする。また、部分集合Ｄ＿｛ｉ,ｊ１｝ には、鍵ｈｋｅｙ（ｈ（ｌ（ｉ, ｊ１）））を割り当て、部分集合Ｄ＿｛ｉ,ｊ１＋ｊ２｝、ただし、ｊ２ ＝
ｒｉｇｈｔ（ｊ１）には、鍵ｈｋｅｙ （ｌ（ｉ, ｊ１））を割り当てる。
【００４４】
そして、セッション鍵Ｋを鍵Ｌ１、・・・、 Ｌｗでそれぞれ暗号化し、以下のデータをすべての利用者端末に配布する（ステップＳ４０３）。
＜[Ｓ１、・・・、Ｓｗ、Ｅ＿｛Ｌ１｝（Ｋ）、・・・、Ｅ＿｛Ｌｗ｝（Ｋ）]、Ｆ＿Ｋ（Ｍ）＞
【００４５】
＜復号処理＞
復号処理について、図８を用いて、説明する。
なお、この処理は、データ＜[Ｓ１、・・・、Ｓｗ、Ｅ＿｛Ｌ１｝（Ｋ）、・・・、Ｅ＿｛Ｌｗ｝（Ｋ）]、Ｆ＿Ｋ（Ｍ）＞を受信した利用者端末が行なう。
【００４６】
まず、利用者端末自らが所属する部分集合Ｓｎを検索する（ステップＳ５０１）。次に、 ラベルを用いて、上記の部分集合に対応する鍵Ｌｎを導出する（ステップＳ５０２）。
【００４７】
そして、Ｅ＿｛Ｌｎ｝（Ｋ）を鍵Ｌｎを用いて復号し、セッション鍵Ｋを得て（ステップＳ５０３）、Ｆ＿Ｋ（Ｍ）をセッション鍵Ｋを用いて復号し、メッセージＭを得る（ステップＳ５０４）。
【００４８】
したがって、本実施形態によれば、正当な利用者端末の部分集合の集合を求める部分集合抽出処理と、リーフノードに割り当てられた各利用者端末に、ラベルを割り当てるラベル割り当て処理と、コンテンツサーバが平文メッセージを暗号化する暗号化処理と、利用者端末が、受信した暗号化されたメッセージを復号化する復号化処理とから構成されているため、従来のＳＤ法が有する結託攻撃に対する耐性を維持しつつ、通信量および利用者が保持するラベル数を削減することができる。
【００４９】
なお、本発明の３分木型ＳＤ法の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを装置に読み込ませ、実行することによって本発明の３分木型ＳＤ法を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００５０】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００５１】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。更に、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００５２】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００５３】
【図１】本実施形態の処理を示すフローである。
【図２】本実施形態に係る部分集合抽出処理のフローである。
【図３】本実施形態に係る第１の形態の部分集合を示す図である。
【図４】本実施形態に係る第２の形態の部分集合を示す図である。
【図５】本実施形態に係るラベル割り当て処理のフローである。
【図６】利用者端末へのラベルの割り当てを例示した図である。
【図７】本実施形態に係る暗号処理のフローである。
【図８】本実施形態に係る復号処理のフローである。
【図９】従来例に係るブロードキャスト暗号の概念図である。
【図１】
2009284220.tif 000004
【図２】
2009284220.tif 000005
【図３】
2009284220.tif 000006
【図４】
2009284220.tif 000007
【図５】
2009284220.tif 000008
【図６】
2009284220.tif 000009
【図７】
2009284220.tif 000010
【図８】
2009284220.tif 000011
【図９】
2009284220.tif 000012