(57)【要約】【課題】各種のブロードキャスト・エンクリプション方式の鍵配信方法におけるヘッダ構造を改良した鍵提供システム、鍵提供装置、端末装置、鍵提供方法、及び鍵生成方法を提供すること。【解決手段】データの暗号化又は復号に用いる鍵を所定の端末装置に提供することが可能な鍵提供装置であって、複数の端末装置の組合せを表す部分集合が各々に対応付けられた複数の座標点を有する座標軸上に、座標点間を結ぶ少なくとも１つの有向枝を配置して形成された有向グラフを取得する取得部と、有向グラフの始点と所定の座標点とを結ぶ有向パスに含まれる全ての有向枝の情報を抽出する抽出部と、有向グラフに基づき、所定の端末装置が所属する部分集合に対応付けられた鍵を生成する鍵生成部と、を備え、有向枝の情報を所定の端末装置に提供することを特徴とする、鍵提供装置が提供される。【選択図】図８
2008236377.tif 000002
【特許請求の範囲】
【請求項１】
複数の端末装置と、これら複数の端末装置に対して情報の暗号化又は復号に用いる鍵情報を提供する鍵提供装置とを備える鍵提供システムであって、
前記鍵提供装置は、
前記複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報及びこれら複数の集合情報の一つに対応する鍵情報から他の一つに対応する鍵情報を生成するのに必要となる鍵生成経路を示す鍵生成経路情報を複数含む集合関係情報を取得する集合関係情報取得部と、
前記集合関係情報に含まれる複数の前記鍵生成経路情報から、これら複数の前記鍵生成経路情報の一部の鍵生成経路情報を抽出する鍵生成経路情報抽出部と、
この鍵生成経路情報抽出部で抽出された前記一部の鍵生成経路情報を前記端末装置に提供する鍵生成経路情報提供部と、
を備え、
前記端末装置は、
前記一部の鍵生成経路情報を取得する鍵生成経路情報取得部と、
前記一部の鍵生成経路情報に基づき、前記複数の集合情報の一つに対応する鍵情報から前記複数の集合情報の他の一つに対応する鍵情報を生成する鍵情報生成部と、
を備えることを特徴とする、鍵提供システム。
【請求項２】
複数の端末装置に対して情報の暗号化又は復号に用いる鍵情報を提供する鍵提供装置であって、
前記複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報及びこれら複数の集合情報の一つに対応する鍵情報から他の一つに対応する鍵情報を生成するのに必要となる鍵生成経路を示す鍵生成経路情報を複数含む集合関係情報を取得する集合関係情報取得部と、
前記集合関係情報に含まれる複数の前記鍵生成経路情報から、これら複数の前記鍵生成経路情報の一部の鍵生成経路情報を抽出する鍵生成経路情報抽出部と、
この鍵生成経路情報抽出部で抽出された前記一部の鍵生成経路情報を前記端末装置に提供する鍵生成経路情報提供部と、
を備えることを特徴とする、鍵提供装置。
【請求項３】
前記鍵生成経路情報提供部は、ネットワークを介して前記鍵生成経路情報を前記端末装置に送信する通信部を備えることを特徴とする、請求項２に記載の鍵提供装置。
【請求項４】
前記鍵生成経路情報提供部は、前記鍵生成経路情報を前記端末装置に提供するための記録媒体に記録する記録部を備えることを特徴とする、請求項２に記載の鍵提供装置。
【請求項５】
前記複数の集合情報の一つに対応する鍵情報を用いて情報を暗号化する暗号化部と、
暗号化された前記情報を前記端末装置に提供する暗号情報提供部と、
をさらに備えることを特徴とする、請求項２に記載の鍵提供装置。
【請求項６】
前記鍵生成経路情報取得部は、前記集合関係情報として、前記複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報に対応付けられた複数の座標点に対し、当該座標点間を結ぶ有向枝によって形成された有向グラフを取得することを特徴とする、請求項２に記載の鍵提供装置。
【請求項７】
前記鍵生成経路情報抽出部は、前記一部の鍵生成経路情報として、前記端末装置が属する前記集合情報に対応付けられた座標点に到達する前記有向グラフの一部を抽出することを特徴とする、請求項６に記載の鍵提供装置。
【請求項８】
前記鍵生成経路情報抽出部は、前記一部の鍵生成経路情報として、前記有向グラフの一部を構成する有向枝の終端位置を示す情報を抽出することを特徴とする、請求項７に記載の鍵提供装置。
【請求項９】
前記鍵生成経路情報抽出部は、前記一部の鍵生成経路情報として、前記有向グラフの一部を構成する有向枝の長さを示す情報を抽出することを特徴とする、請求項７に記載の鍵提供装置。
【請求項１０】
前記座標点Ｓ０に対応する前記鍵情報ｋ（Ｓ０）の入力に応じて、前記座標点Ｓ０を始端とする全ての前記有向枝の終端の座標点Ｓ１，・・・，Ｓｍに対応する前記鍵情報ｋ（Ｓ１），・・・，ｋ（Ｓｍ）を生成する鍵情報生成部をさらに備えることを特徴とする、請求項６に記載の鍵提供装置。
【請求項１１】
前記鍵情報は、情報を暗号化又は復号するためのセット鍵ｋと、当該セット鍵ｋを生成するための中間鍵ｔとにより構成され、
前記座標点Ｓ０に対応する前記中間鍵ｔ（Ｓ０）の入力に応じて、前記座標点Ｓ０に対応する前記セット鍵ｋ（Ｓ０）と、前記座標点Ｓ０を始端とする全ての前記有向枝の終端の座標点Ｓ１，・・・，Ｓｍに対応する前記中間鍵ｔ（Ｓ１），・・・，ｔ（Ｓｍ）とを生成する鍵情報生成部をさらに備えることを特徴とする、請求項６に記載の鍵提供装置。
【請求項１２】
複数の端末装置に対して情報の暗号化又は復号に用いる鍵情報を提供する鍵提供装置であって、
前記複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報及びこれら複数の集合情報の一つに対応する鍵情報から他の一つに対応する鍵情報を生成するのに必要となる鍵生成経路を示す鍵生成経路情報を複数含む集合関係情報を生成する集合関係情報生成部と、
前記集合関係情報に含まれる複数の前記鍵生成経路情報から、これら複数の前記鍵生成経路情報の一部の鍵生成経路情報を抽出する鍵生成経路情報抽出部と、
この鍵生成経路情報抽出部で抽出された前記一部の鍵生成経路情報を前記端末装置に提供する鍵生成経路情報提供部と、
を備えることを特徴とする、鍵提供装置。
【請求項１３】
情報の暗号化又は復号に用いる鍵情報を生成する端末装置であって、
複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報及びこれら複数の集合情報の一つに対応する鍵情報から他の一つに対応する鍵情報を生成するのに必要となる鍵生成経路を示す鍵生成経路情報を複数含む集合関係情報の中から抽出された、これら複数の前記鍵生成経路情報の一部の鍵生成経路情報を取得する鍵生成経路情報取得部と、
前記一部の鍵生成経路情報に基づき、前記複数の集合情報の一つに対応する鍵情報から前記複数の集合情報の他の一つに対応する鍵情報を生成する鍵情報生成部と、
を備えることを特徴とする、端末装置。
【請求項１４】
前記鍵生成経路情報取得部は、ネットワークを介して前記鍵生成経路情報を受信する通信部を備えることを特徴とする、請求項１３に記載の端末装置。
【請求項１５】
前記鍵生成経路情報取得部は、前記鍵生成経路情報が記録された記録媒体を取得し、前記記録媒体から前記鍵生成経路情報を読み出す読出部を備えることを特徴とする、請求項１３に記載の端末装置。
【請求項１６】
前記複数の集合情報の他の一つに対応する鍵情報を用いて暗号化された情報を取得する暗号情報取得部と、
前記鍵情報生成部により生成された前記複数の集合情報の他の一つに対応する鍵情報を用いて、前記暗号化された情報を復号する暗号情報復号部と、
をさらに備えることを特徴とする、請求項１３に記載の端末装置。
【請求項１７】
前記鍵生成経路情報取得部は、前記複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報に対応付けられた複数の座標点に対し、当該座標点間を結ぶ有向枝によって形成された有向グラフの中から抽出された、前記端末装置が属する前記集合情報に対応付けられた座標点に到達する前記有向グラフの一部を前記一部の鍵生成経路情報として取得することを特徴とする、請求項１３に記載の端末装置。
【請求項１８】
前記鍵生成経路情報取得部は、前記一部の鍵生成経路情報として、前記有向グラフの一部を構成する有向枝の終端位置を示す情報を取得することを特徴とする、請求項１７に記載の端末装置。
【請求項１９】
前記鍵生成経路情報取得部は、前記一部の鍵生成経路情報として、前記有向グラフの一部を構成する有向枝の長さを示す情報を取得することを特徴とする、請求項１７に記載の端末装置。
【請求項２０】
前記有向枝の始端Ｓ０に対応する前記鍵情報ｋ（Ｓ０）の入力に応じて、前記有向枝の終端の座標点Ｓ１に対応する前記鍵情報ｋ（Ｓ１）を生成する鍵情報生成部をさらに備えることを特徴とする、請求項１７に記載の端末装置。
【請求項２１】
前記鍵情報は、情報を暗号化又は復号するためのセット鍵ｋと、当該セット鍵ｋを生成するための中間鍵ｔとにより構成され、
前記有向枝の始端Ｓ０に対応する前記中間鍵ｔ（Ｓ０）の入力に応じて、前記有向枝の始端Ｓ０に対応する前記セット鍵ｋ（Ｓ０）と、前記有向枝の終端Ｓ１に対応する前記中間鍵ｔ（Ｓ１）とを生成する鍵情報生成部をさらに備えることを特徴とする、請求項１７に記載の端末装置。
【請求項２２】
複数の端末装置に対してデータの暗号化又は復号に用いる鍵情報を提供するための鍵提供方法であって、
前記複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報及びこれら複数の集合情報の一つに対応する鍵情報から他の一つに対応する鍵情報を生成するのに必要となる鍵生成経路を示す鍵生成経路情報を複数含む集合関係情報を取得する集合関係情報取得ステップと、
前記集合関係情報に含まれる複数の前記鍵生成経路情報から、これら複数の前記鍵生成経路情報の一部の鍵生成経路情報を抽出する鍵生成経路情報抽出ステップと、
この鍵生成経路情報抽出部で抽出された前記一部の鍵生成経路情報を前記端末装置に提供する鍵生成経路情報提供ステップと、
を含むことを特徴とする、鍵提供方法。
【請求項２３】
情報の暗号化又は復号に用いる鍵情報を生成するための鍵生成方法であって、
複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報及びこれら複数の集合情報の一つに対応する鍵情報から他の一つに対応する鍵情報を生成するのに必要となる鍵生成経路を示す鍵生成経路情報を複数含む集合関係情報の中から抽出された、これら複数の前記鍵生成経路情報の一部の鍵生成経路情報を取得する鍵生成経路情報取得ステップと、
前記一部の鍵生成経路情報に基づき、前記複数の集合情報の一つに対応する鍵情報から前記複数の集合情報の他の一つに対応する鍵情報を生成する鍵情報生成ステップと、
を含むことを特徴とする、鍵生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鍵提供システム、鍵提供装置、端末装置、鍵提供方法、及び鍵生成方法に関する。
【背景技術】
【０００２】
近年、パーソナルコンピュータ（以下、ＰＣ）、携帯電話、及びデジタル家電等の情報機器が一般にも広く普及してきている。また、これらの情報機器やそれらの間を繋ぐ情報通信に関する技術が非常に大きく発達してきており、これらの情報機器を利用した音楽配信や映像配信といったコンテンツ配信サービスが広く展開されるようになってきている。例えば、ＣＡＴＶ（Ｃｏｍｍｕｎｉｔｙ  Ａｎｔｅｎｎａ  ＴｅｌｅＶｉｓｉｏｎ）、衛星放送、又はインターネット等を利用した有料放送、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）又はＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）等物理メディアを利用したコンテンツ販売等がコンテンツ配信サービスの一例である。
【０００３】
しかし、このようなコンテンツ配信サービスを提供するには、当該サービスの提供者（以下、システム管理者）と視聴者との間で締結した契約に基づき、その契約者のみがコンテンツを取得できるようにする仕組みが必要とされる。この問題に対し、例えば、システム管理者が契約者に対して所定の鍵を提供しておき、暗号化されたコンテンツＭと共に、コンテンツＭを暗号化するために利用したコンテンツ鍵ｍｅｋを前記所定の鍵により生成するためのヘッダ情報ｈとを配信する仕組みが考案されている。
【０００４】
上記の仕組みを実現させる具体的な一手段として、ブロードキャスト・エンクリプション（Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ）方式と呼ばれるコンテンツ配信方式が知られている。このブロードキャスト・エンクリプション方式とは、各契約者を集合の要素に対応付けた上で、契約者全体を表す契約者集合を複数の部分集合に分割し、特定の部分集合に属する契約者のみがコンテンツ鍵ｍｅｋを取得できるようなヘッダｈを配信する方式である。つまり、当該方式を適用すると、システム管理者が指定した特定の契約者を排除してコンテンツＭの配信を実現することができる。しかし、現実的には、システム管理者側のサーバ装置（以下、センタ）及び契約者側の端末装置におけるコンテンツ鍵ｍｅｋの生成に係る演算負荷、及びサーバ装置と端末装置との間の通信負荷等を考慮すると、従来のブロードキャスト・エンクリプション方式をより効率化する必要がある。
【０００５】
具体的には、上記のコンテンツ配信をする際に、センタが配信するヘッダｈのサイズに応じて増大する通信量、各端末装置が保持すべき鍵数に応じて増大するメモリ量、及び各端末装置がコンテンツ鍵ｍｅｋを生成するために必要な計算量を如何にして低減させるかということが問題となる。上記の各量は、契約者集合の分割方法によって大きく異なる。そこで、効率的なコンテンツ配信を実現させるため、契約者集合の分割方法に工夫を凝らした種々のブロードキャスト・エンクリプション方式が提案されている。例えば、下記の非特許文献１には、上記の各量を低減させるための一つの手段として、Ｎｕｔｔａｐｏｎｇ  Ａｔｔｒａｐａｄｕｎｇ  ａｎｄ  Ｈｉｄｅｋｉ  Ｉｍａｉらにより、Ｓｕｂｓｅｔ  Ｉｎｃｒｅｍｅｎｔａｌ  Ｃｈａｉｎ  Ｂａｓｅｄ  Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ方式と呼ばれるコンテンツ配信方式が開示されている（以下、ＡＩ０５方式）。
【０００６】
【非特許文献１】Ｎｕｔｔａｐｏｎｇ  Ａｔｔｒａｐａｄｕｎｇ  ａｎｄ  Ｈｉｄｅｋｉ  Ｉｍａｉ、”Ｓｕｂｓｅｔ  Ｉｎｃｒｅｍｅｎｔａｌ  Ｃｈａｉｎ  Ｂａｓｅｄ  Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ｓｈｏｒｔｅｒ  Ｃｉｐｈｅｒｔｅｘｔ”、Ｔｈｅ  ２８ｔｈ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ａｎｄ  Ｉｔｓ  Ａｐｐｌｉｃａｔｉｏｎｓ（ＳＩＴＡ２００５）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
また、本件出願人は、上記の非特許文献１に記載のコンテンツ配信方式よりも、各端末装置が鍵を保持するために要求されるメモリ量を低減することが可能な第１の改良方式（以下、Ａ０６（Ａ）方式）、各端末装置がコンテンツ鍵を生成するために要求される計算量を低減することが可能な第２の改良方式（以下、Ａ０６（Ｂ）方式）、及び上記のメモリ量と計算量とを低減させることが可能な第３の改良方式（以下、Ａ０６（Ａ＋Ｂ）方式）を開発し、既に日本国特許庁に特許出願している（Ａ０６（Ａ）方式：特願２００６−３１０１８２、Ａ０６（Ｂ）方式：特願２００６−３１０２１３、Ａ０６（Ａ＋Ｂ）方式：特願２００６−３１０２２６）。当該各方式の特徴は、擬似乱数生成器を利用してコンテンツ鍵ｍｅｋを生成する際に、各方式固有の有向グラフにより表現される鍵生成アルゴリズムに基づき、擬似乱数生成演算を実行する点にある。
【０００８】
しかし、上記の各方式に限らず、ある方式に従って一つの部分集合に対応する鍵から他の部分集合に対応する鍵を生成する場合、例えば、複数の鍵生成経路の情報を含む有向グラフのような集合関係情報を端末装置側で全て保持しなければならないとすると、複数の鍵生成経路の情報を保持するために要する記憶容量が大きくなってしまうという問題がある。一方、鍵提供装置が有する複数の鍵生成経路の情報を端末装置が全て取得しなければならないとすると、複数の鍵生成経路の情報を端末装置が取得するために伝播される容量が大きくなってしまうという問題もある。
【０００９】
本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、端末装置が予め全ての鍵生成経路情報を伝播又は保持している場合に比べて、端末装置が鍵生成に要する情報を伝播又は保持するために必要な容量を低減することが可能な、新規かつ改良された鍵提供システム、鍵提供装置、端末装置、鍵提供方法及び鍵生成方法を提供することにある。
【課題を解決するための手段】
【００１０】
上記課題を解決するために、本発明のある観点によれば、複数の端末装置と、これら複数の端末装置に情報の暗号化又は復号に用いる鍵情報を提供する鍵提供装置とを備える鍵提供システムが提供される。
また、前記鍵提供装置は、前記複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報及びこれら複数の集合情報の一つに対応する鍵情報から他の一つに対応する鍵情報を生成するのに必要となる鍵生成経路を示す鍵生成経路情報を複数含む集合関係情報を取得する集合関係情報取得部と、前記集合関係情報に含まれる複数の前記鍵生成経路情報から、これら複数の前記鍵生成経路情報の一部の鍵生成経路情報を抽出する鍵生成経路情報抽出部と、この鍵生成経路情報抽出部で抽出された前記一部の鍵生成経路情報を前記端末装置に提供する鍵生成経路情報提供部と、を備えていてもよい。
さらに、前記端末装置は、前記一部の鍵生成経路情報を取得する鍵生成経路情報取得部と、前記一部の鍵生成経路情報に基づき、前記複数の集合情報の一つに対応する鍵情報から前記複数の集合情報の他の一つに対応する鍵情報を生成する鍵情報生成部と、を備えていてもよい。
【００１１】
また、上記課題を解決するために、本発明の別の観点によれば、複数の端末装置に対してデータの暗号化又は復号に用いる鍵情報を提供する鍵提供装置が提供される。当該鍵提供装置は、前記複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報及びこれら複数の集合情報の一つに対応する鍵情報から他の一つに対応する鍵情報を生成するのに必要となる鍵生成経路を示す鍵生成経路情報を複数含む集合関係情報を取得する集合関係情報取得部と、前記集合関係情報に含まれる複数の前記鍵生成経路情報から、これら複数の前記鍵生成経路情報の一部の鍵生成経路情報を抽出する鍵生成経路情報抽出部と、この鍵生成経路情報抽出部で抽出された前記一部の鍵生成経路情報を前記端末装置に提供する鍵生成経路情報提供部と、を備えることを特徴とする。
【００１２】
また、前記鍵生成経路情報提供部は、ネットワークを介して前記鍵生成経路情報を前記端末装置に送信する通信部を備えていてもよい。
【００１３】
また、前記鍵生成経路情報提供部は、前記鍵生成経路情報を前記端末装置に提供するための記録媒体に記録する記録部を備えていてもよい。
【００１４】
また、前記複数の集合情報の一つに対応する鍵情報を用いて情報を暗号化する暗号化部と、暗号化された前記情報を前記端末装置に提供する暗号情報提供部と、をさらに備えていてもよい。
【００１５】
また、前記鍵生成経路情報取得部は、前記集合関係情報として、前記複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報に対応付けられた複数の座標点に対し、当該座標点間を結ぶ有向枝によって形成された有向グラフを取得するように構成されていてもよい。
【００１６】
また、前記鍵生成経路情報抽出部は、前記一部の鍵生成経路情報として、前記端末装置が属する前記集合情報に対応付けられた座標点に到達する前記有向グラフの一部を抽出するように構成されていてもよい。
【００１７】
また、前記鍵生成経路情報抽出部は、前記一部の鍵生成経路情報として前記有向グラフの一部を構成する有向枝の終端位置を示す情報を抽出するように構成されていてもよい。
【００１８】
また、前記鍵生成経路情報抽出部は、前記一部の鍵生成経路情報として、前記有向グラフの一部を構成する有向枝の長さを示す情報を抽出するように構成されていてもよい。
【００１９】
また、前記座標点Ｓ０に対応する前記鍵情報ｋ（Ｓ０）の入力に応じて、前記座標点Ｓ０を始端とする全ての前記有向枝の終端の座標点Ｓ１，・・・，Ｓｍに対応する前記鍵情報ｋ（Ｓ１），・・・，ｋ（Ｓｍ）を生成する鍵情報生成部をさらに備えていてもよい。
【００２０】
また、前記鍵情報は、情報を暗号化又は復号するためのセット鍵ｋと、当該セット鍵ｋを生成するための中間鍵ｔとにより構成されていてもよい。さらに、前記座標点Ｓ０に対応する前記中間鍵ｔ（Ｓ０）の入力に応じて、前記座標点Ｓ０に対応する前記セット鍵ｋ（Ｓ０）と、前記座標点Ｓ０を始端とする全ての前記有向枝の終端の座標点Ｓ１，・・・，Ｓｍに対応する前記中間鍵ｔ（Ｓ１），・・・，ｔ（Ｓｍ）とを生成する鍵情報生成部をさらに備えていてもよい。
【００２１】
また、上記課題を解決するために、本発明の別の観点によれば、複数の端末装置に対してデータの暗号化又は復号に用いる鍵情報を提供する鍵提供装置が提供される。当該鍵提供装置は、前記複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報及びこれら複数の集合情報の一つに対応する鍵情報から他の一つに対応する鍵情報を生成するのに必要となる鍵生成経路を示す鍵生成経路情報を複数含む集合関係情報を生成する集合関係情報生成部と、前記集合関係情報に含まれる複数の前記鍵生成経路情報から、これら複数の前記鍵生成経路情報の一部の鍵生成経路情報を抽出する鍵生成経路情報抽出部と、この鍵生成経路情報抽出部で抽出された前記一部の鍵生成経路情報を前記端末装置に提供する鍵生成経路情報提供部と、を備えることを特徴とする。
【００２２】
また、上記課題を解決するために、本発明の別の観点によれば、情報の暗号化又は復号に用いる鍵情報を生成する端末装置が提供される。当該端末装置は、複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報及びこれら複数の集合情報の一つに対応する鍵情報から他の一つに対応する鍵情報を生成するのに必要となる鍵生成経路を示す鍵生成経路情報を複数含む集合関係情報の中から抽出された、これら複数の前記鍵生成経路情報の一部の鍵生成経路情報を取得する鍵生成経路情報取得部と、前記一部の鍵生成経路情報に基づき、前記複数の集合情報の一つに対応する鍵情報から前記複数の集合情報の他の一つに対応する鍵情報を生成する鍵情報生成部と、を備えることを特徴とする。
【００２３】
また、前記鍵生成経路情報取得部は、ネットワークを介して前記鍵生成経路情報を受信する通信部を備えていてもよい。
【００２４】
また、前記鍵生成経路情報取得部は、前記鍵生成経路情報が記録された記録媒体を取得し、前記記録媒体から前記鍵生成経路情報を読み出す読出部を備えていてもよい。
【００２５】
また、前記複数の集合情報の他の一つに対応する鍵情報を用いて暗号化された情報を取得する暗号情報取得部と、前記鍵情報生成部により生成された前記複数の集合情報の他の一つに対応する鍵情報を用いて、前記暗号化された情報を復号する復号部と、をさらに備えていてもよい。
【００２６】
また、前記鍵生成経路情報取得部は、前記複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報に対応付けられた複数の座標点に対し、当該座標点間を結ぶ有向枝によって形成された有向グラフの中から抽出された、前記端末装置が属する前記集合情報に対応付けられた座標点に到達する前記有向グラフの一部を前記一部の鍵生成経路情報として取得するように構成されていてもよい。
【００２７】
また、前記鍵生成経路情報取得部は、前記一部の鍵生成経路情報として前記有向グラフの一部を構成する有向枝の終端位置を示す情報を取得するように構成されていてもよい。
【００２８】
また、前記鍵生成経路情報取得部は、前記一部の鍵生成経路情報として、前記有向グラフの一部を構成する有向枝の長さを示す情報を取得するように構成されていてもよい。
【００２９】
また、前記有向枝の始端Ｓ０に対応する前記鍵情報ｋ（Ｓ０）の入力に応じて、前記有向枝の終端の座標点Ｓ１に対応する前記鍵情報ｋ（Ｓ１）を生成する鍵情報生成部をさらに備えていてもよい。
【００３０】
また、前記鍵情報は、情報を暗号化又は復号するためのセット鍵ｋと、当該セット鍵ｋを生成するための中間鍵ｔとにより構成されていてもよい。さらに、前記有向枝の始端Ｓ０に対応する前記中間鍵ｔ（Ｓ０）の入力に応じて、前記有向枝の始端Ｓ０に対応する前記セット鍵ｋ（Ｓ０）と、前記有向枝の終端Ｓ１に対応する前記中間鍵ｔ（Ｓ１）とを生成する鍵情報生成部をさらに備えていてもよい。
【００３１】
また、上記課題を解決するために、本発明の別の観点によれば、複数の端末装置に対してデータの暗号化又は復号に用いる鍵情報を提供するための鍵提供方法が提供される。当該鍵提供方法は、前記複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報及びこれら複数の集合情報の一つに対応する鍵情報から他の一つに対応する鍵情報を生成するのに必要となる鍵生成経路を示す鍵生成経路情報を複数含む集合関係情報を取得する集合関係情報取得ステップと、前記集合関係情報に含まれる複数の前記鍵生成経路情報から、これら複数の前記鍵生成経路情報の一部の鍵生成経路情報を抽出する鍵生成経路情報抽出ステップと、この鍵生成経路情報抽出部で抽出された前記一部の鍵生成経路情報を前記端末装置に提供する鍵生成経路情報提供ステップと、を含むことを特徴とする。
【００３２】
また、上記課題を解決するために、本発明の別の観点によれば、情報の暗号化又は復号に用いる鍵情報を生成するための鍵生成方法が提供される。当該鍵生成方法は、複数の端末装置の異なる組合せをそれぞれ示す複数の集合情報及びこれら複数の集合情報の一つに対応する鍵情報から他の一つに対応する鍵情報を生成するのに必要となる鍵生成経路を示す鍵生成経路情報を複数含む集合関係情報の中から抽出された、これら複数の前記鍵生成経路情報の一部の鍵生成経路情報を取得する鍵生成経路情報取得ステップと、前記一部の鍵生成経路情報に基づき、前記複数の集合情報の一つに対応する鍵情報から前記複数の集合情報の他の一つに対応する鍵情報を生成する鍵情報生成ステップと、を含むことを特徴とする。
【００３３】
上記の各構成によると、鍵提供装置により抽出された一部の鍵生成経路情報が端末装置に提供され、端末装置が一つの集合に対応する鍵から他の集合に対応する鍵を導出できるため、鍵提供装置が持つ全ての鍵生成経路情報の提供を受ける場合に比べて、鍵提供装置から端末装置に鍵生成経路情報を伝播するために必要な容量を制限することができる。また、端末装置が予め全ての鍵生成経路情報を保持している場合に比べても、端末装置が保持のために要する容量を制限することができる。
【発明の効果】
【００３４】
以上説明したように、本発明によれば、端末装置が予め全ての鍵生成経路情報を伝播又は保持する場合に比べて、端末装置が鍵生成に要する情報を伝播又は保持するために必要な容量を低減することが可能になる。
【発明を実施するための最良の形態】
【００３５】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００３６】
＜第１実施形態＞
以下、本発明の第１実施形態に係る鍵提供システム１００の構成、及び鍵配信に係る具体的な方式について詳細に説明する。
【００３７】
［概要］
まず、本実施形態に係る鍵提供システム１００の構成について詳細に説明するに先立ち、本実施形態に係る鍵配信方式の概要について簡単に説明する。
【００３８】
本実施形態は、種々の鍵配信方式に適用することが可能であるが、説明の都合上、本実施形態をＡＩ０５方式、及びＡ０６（Ａ＋Ｂ）方式に適用するケースを例に挙げて説明する。そこで、本実施形態を適用可能なＡＩ０５方式等の基本的な考え方について簡単に説明する。
【００３９】
ＡＩ０５方式等では、通常のブロードキャスト・エンクリプション方式と同様、鍵提供システムに含まれる各端末装置を集合の要素に対応付け、端末装置全体の集合を考える。そして、当該集合を分割して得られる複数の部分集合を利用して鍵配信を実行する。つまり、この部分集合により端末装置の組合せが表現される。まず、鍵配信サーバは、論理二分木（ＢＴ；Ｂｉｎａｒｙ  Ｔｒｅｅ）を形成して各端末装置を葉ノードに対応付ける。次いで、鍵配信サーバは、所定の規則に則って上記の部分集合を要素とする複数の「部分集合の集合」を生成し、当該各部分集合の集合をＢＴの根ノード、及び各中間ノードに対応付ける。さらに、鍵配信サーバは、上記の部分集合の集合に含まれる複数の部分集合を所定の規則（以下、ジャンプと呼ぶことがある）に基づいて関連付ける。そして、この部分集合間の関係を表すのが有向グラフ又は有向枝である。なお、集合及びその集合の要素である部分集合は、上記の集合情報の一例である。また、ＡＩ０５方式等により生成される有向グラフは、上記の集合関係情報の一例である。さらに、それを構成する有向枝は、上記の鍵生成経路情報の一例である。但し、上記の鍵生成経路情報は、例えば、１本以上の有向枝により構成される鍵生成経路を表す情報であるか、又は空集合に対応する有向グラフである。
【００４０】
上記の有向グラフは、上記の部分集合の集合に含まれる各部分集合が各座標点に対応付けられた座標軸上に形成され、上記のジャンプに基づいて複数の座標点間を連結する有向枝により構成されている。鍵配信サーバは、上記のＢＴに含まれる根ノード、及び各中間ノードに対応付けられた部分集合の集合毎に、それに含まれる複数の部分集合間の関係が表現された有向グラフを形成する。
【００４１】
さらに、鍵配信サーバは、配信先となる端末装置が含まれる部分集合を選択し、当該部分集合が含まれる有向グラフを特定する。そして、鍵配信サーバは、特定された有向グラフに基づいて擬似乱数生成器（ＰＲＳＧ；Ｐｓｅｕｄｏ−Ｒａｎｄｏｍ  Ｓｅｑｕｅｎｃｅ  Ｇｅｎｅｒａｔｏｒ）による演算を繰り返すことによって鍵を生成する。ＡＩ０５方式の特徴は、従来のブロードキャスト・エンクリプション方式に比べて、通信量、各端末装置が保持すべき鍵数、各端末装置が鍵生成に要する計算量を削減するように、全ての端末装置を表す集合を部分集合に分割する点にある。このように、ＡＩ０５方式等を適用した鍵配信方式では、有向グラフを利用して各端末装置に配信する鍵を生成することができる。
【００４２】
なお、Ａ０６（Ａ）方式では、有向グラフを構成する有向枝の長さを短くする処理を加えることにより、上記のＡＩ０５方式よりも各端末装置が保持すべき鍵数を低減させる改良が施されている。また、Ａ０６（Ｂ）方式では、有向枝の長さが長くなるように有向グラフを形成することにより、上記のＡＩ０５方式よりも各端末装置が鍵生成に要する計算量を低減させる改良が施されている。さらに、Ａ０６（Ａ＋Ｂ）方式では、Ａ０６（Ｂ）方式と同様にして有向枝の長い有向グラフを形成した後、Ａ０６（Ａ）方式と同様に所定の有向枝を短い有向枝に置換することにより、上記のＡＩ０５方式よりも各端末装置が鍵生成に要する計算量及び保持すべき鍵数を低減させる改良が施されている。従って、Ａ０６（Ａ）、Ａ０６（Ｂ）、及びＡ０６（Ａ＋Ｂ）の各方式を適用することにより、ＡＩ０５方式よりも端末装置に掛かる負荷を低減させることができる。
【００４３】
しかし、上記のＡＩ０５方式等には、各端末装置が鍵を生成するために必要な有向グラフの情報を如何にして取得するかということについて明確に開示がされておらず、各端末装置が予め有向グラフの情報を全て保持しているか、又は各端末装置が鍵配信サーバと同じアルゴリズムに基づいて各自で有向グラフを生成しているという暗黙の仮定が存在している。しかし、現実的な状況に鑑み、鍵提供システムに含まれる端末装置の数を想定すると、各端末装置が保持すべき有向グラフの情報量、及び有向グラフを生成するための計算量は膨大であるため、一般的な端末装置が有する限られたリソースの中では実現が困難である。
【００４４】
より具体的に、上記のＡ０６（Ｂ）方式の場合で考えてみると、通常、鍵提供システムに含まれる端末装置の数ｎはｎ＝２３２程度であるため、有向枝１本の情報を４ｂｙｔｅ程度で表現できたとしても、各端末装置が保持すべき情報量は約３２ＧＢｙｔｅにもなる。また、各端末装置が有向グラフを生成する場合には、端末装置の数ｎ＝２３２に対し、（ｎ−１）本の有向枝を算出する必要があるため、各端末装置が有向グラフを生成するのに掛かる演算負荷は非常に大きいと言える。
【００４５】
しかし、上記の各方式では、各端末装置がコンテンツ鍵ｍｅｋを生成する際に、予め各端末装置が保持している各有向グラフの情報を利用することが示唆されているのみであり、具体的な手段については示されていなかった。上記の通り、契約者数が多い場合には、各端末装置が保持すべき有向グラフの情報量が膨大になるため、その情報を端末装置に格納しておくのは現実的に困難である。また、各端末装置がそれぞれ有向グラフを算出する場合には、各端末装置の演算量が膨大になり実現が困難である。
【００４６】
そこで、本実施形態に係る鍵配信サーバは、各端末装置が鍵生成に要する有向グラフの情報を提供する構成を有する。また、各端末装置は、鍵配信サーバから取得した有向グラフの情報に基づいて擬似乱数演算を実行して必要な鍵を生成する構成を有する。
【００４７】
以上、本実施形態を適用可能な鍵配信方式について簡単に説明した。もちろん、本実施形態を適用可能な鍵配信方式は、上記のＡＩ０５、Ａ０６（Ａ）、Ａ０６（Ｂ）、Ａ０６（Ａ＋Ｂ）の各方式に限定されるものではなく、他の鍵配信方式にも適用することが可能である。以下では、説明の都合上、本実施形態をＡＩ０５方式、及びＡ０６（Ａ＋Ｂ）方式に適用する場合について詳細に説明するが、当業者であれば、当該記載に基づいて容易に他の鍵配信方式への適用手段を想起することが可能である。
【００４８】
［鍵提供システム１００の構成］
ここで、図１を参照しながら、本発明の第１実施形態に係る鍵提供システム１００の構成について簡単に説明する。図１は、本実施形態に係る鍵提供システム１００の構成を示す説明図である。
【００４９】
図１を参照すると、鍵提供システム１００は、主に、鍵配信サーバ１０２と、端末装置１２２と、ネットワーク１０とにより構成される。なお、鍵配信サーバ１０２は、鍵提供装置の一例である。
【００５０】
（ネットワーク１０）
ネットワーク１０は、鍵配信サーバ１０２と端末装置１２２とを双方向通信又は一方向通信可能に接続する通信回線網である。ネットワーク１０は、例えば、インターネット、電話回線網、衛星通信網、同報通信路等の公衆回線網、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＩＰ−ＶＰＮ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ−Ｖｉｒｔｕａｌ  Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋ）、ワイヤレスＬＡＮ等の専用回線網等により構成されており有線／無線を問わない。
【００５１】
（鍵配信サーバ１０２）
鍵配信サーバ１０２は、コンテンツ配信時に種々の電子データを暗号化して配信することが可能である。例えば、鍵配信サーバ１０２は、コンテンツを暗号化又は復号するためのコンテンツ鍵を生成して配信することが可能である。なお、コンテンツ鍵は、例えば、擬似乱数生成器により算出された乱数（擬似乱数）、所定の文字列、又は数列等により表現されていてもよい。さらに、コンテンツ鍵は、暗号化用のコンテンツ鍵と復号用のコンテンツ鍵とにより構成されていてもよい。そして、鍵配信サーバ１０２は、このコンテンツ鍵を用いて、所定の暗号化ロジックに基づきコンテンツを暗号化することができる。さらに、鍵配信サーバ１０２は、コンテンツ及びコンテンツ鍵の一方又は両方を任意の端末装置１２２に対して配信することが可能である。
【００５２】
さらに、鍵配信サーバ１０２は、コンテンツ鍵を暗号化又は復号するための複数のセット鍵を生成することが可能である。このとき、鍵配信サーバ１０２は、擬似乱数生成器を利用し、所定の有向グラフに基づいて複数のセット鍵を生成する。また、鍵配信サーバ１０２は、各セット鍵を用いてコンテンツ鍵を暗号化し、この暗号化されたコンテンツ鍵を所定の端末装置１２２に対して配信する。さらに、鍵配信サーバ１０２は、所定のセット鍵を生成するために利用した有向グラフの情報を所定の端末装置１２２に対して配信することも可能である。なお、セット鍵は、上記の鍵情報の一例である。また、コンテンツ鍵は、上記の鍵情報により暗号化／復号される情報の一例である。
【００５３】
上記の複数のセット鍵は、それぞれ、多数の契約者の中から選択された複数の契約者の部分集合群に対応付けされており、鍵配信サーバ１０２は、コンテンツの再生を許諾する契約者（以下、許諾契約者）の集合だけがコンテンツ鍵を復号できるようにセット鍵を生成し、それを用いてコンテンツ鍵を暗号化し、全ての契約者の端末装置１２２に対して暗号化されたコンテンツ鍵を配信する。このように、鍵配信サーバ１０２は、コンテンツだけでなく、コンテンツ鍵も暗号化して配信するように構成される。もちろん、コンテンツを暗号化して配信することにより、ある程度のセキュリティレベルを確保することができるけれども、多数の契約者の中からコンテンツの使用が許諾される契約者を追加又は削除する際にフレキシブルに対応するためにはコンテンツ鍵を暗号化して配信する方が有利である。
【００５４】
上記の構成により、所定の端末装置１２２にのみ暗号化されたコンテンツ鍵を復号することが可能になるため、所定の端末装置１２２だけがコンテンツを復号して視聴することができるようになる。もし、許諾契約者の集合が変更された場合には、鍵配信サーバ１０２は、コンテンツ鍵の暗号化に用いるセット鍵を変更することにより対応可能である。
【００５５】
なお、上記の擬似乱数生成器は、所定のシード値を入力することによって長周期の擬似的な乱数列を出力することが可能な装置又はプログラムであり、線形合同法やメルセンヌ・ツイスター法等のロジックを用いて実現されるものである。もちろん、本実施形態に適用可能な擬似乱数生成器は、これに限定されるものではなく、他のロジックを用いて擬似乱数を発生させてもよいし、或いは、特殊な情報又は条件を含んだ擬似乱数列を生成することが可能な装置又はプログラムであってもよい。
【００５６】
なお、鍵配信サーバ１０２は、サーバ機能を備えたパーソナルコンピュータ（ＰＣ；Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）等の情報処理装置により構成され、ネットワーク１０を介して各種の情報を外部装置に送信可能である。例えば、鍵配信サーバ１０２は、ブロードキャスト・エンクリプション方式の暗号鍵を生成して、この暗号鍵を端末装置１２２に配信することができる。また、鍵配信サーバ１０２は、例えば、映像配信サービス、又は電子音楽配信サービス等のコンテンツ配信サービスを提供するコンテンツ配信サーバとしての機能を具備していてもよく、端末装置１２２に対してコンテンツを配信することが可能な機能を有していてもよい。なお、鍵配信サーバ１０２とコンテンツ配信サーバとを別装置として構成することも勿論可能である。
【００５７】
ここで、コンテンツとは、例えば、映画、テレビジョン番組、ビデオプログラム、図表等の動画又は静止画からなる映像（Ｖｉｄｅｏ）コンテンツ、音楽、講演、ラジオ番組等の音声（Ａｕｄｉｏ）コンテンツ、ゲームコンテンツ、文書コンテンツ、又はソフトウェア等が含まれる任意のコンテンツデータであってもよい。また、映像コンテンツとは、映像データのみならず、音声データを含んでいてもよい。
【００５８】
（端末装置１２２）
端末装置１２２は、鍵配信サーバ１０２から種々の情報を受信することができる。例えば、端末装置１２２は、鍵配信サーバ１０２により配信されたコンテンツ又はコンテンツ鍵を受信することができる。また、端末装置１２２は、鍵配信サーバ１０２から受信したコンテンツ鍵を用いて、暗号化されたコンテンツを復号することができる。ただし、鍵配信サーバ１０２から送信されるコンテンツ又はコンテンツ鍵は、所定のセット鍵により暗号化されているため、当該コンテンツ又はコンテンツ鍵を復号しなくてはならない。そこで、端末装置１２２は、鍵配信サーバ１０２から取得した所定のセット鍵を利用して暗号化されたコンテンツ又はコンテンツ鍵を復号することができる。さらに、端末装置１２２は、予め保持しているセット鍵又は所定のセット鍵を生成可能な中間鍵を利用して、鍵配信サーバ１０２がコンテンツ又はコンテンツ鍵を暗号化する際に用いたセット鍵を生成することができる。このとき、端末装置１２２は、鍵配信サーバ１０２から取得した有向グラフに関する情報に基づいて、自己が保持するセット鍵又は中間鍵を擬似乱数生成器に入力して所望のセット鍵を生成することができる。なお、中間鍵は、上記の鍵情報の一例である。
【００５９】
上記の構成により、端末装置１２２は、所望のセット鍵を生成するために必要な有向グラフを生成する必要がなくなり、保持すべき情報量を低減させることが可能な上、セット鍵の生成に掛かる演算負荷を低減させることが可能になる。
【００６０】
なお、端末装置１２２は、ネットワーク１０を介して外部装置とデータ通信が可能な端末装置であり、各契約者によって所有される。端末装置１２２は、例えば、図示のようにパーソナルコンピュータ等の情報処理装置により構成されるが、かかる例に限定されず、ネットワーク１０を介して情報通信が可能な通信機能を有する機器であれば、例えば、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）、家庭用ゲーム機、ＤＶＤ／ＨＤＤレコーダ、又はテレビジョン受像器等の情報家電、テレビジョン放送用のチューナやデコーダ等により構成することも可能である。また、端末装置１２２は、例えば、携帯型ゲーム機、携帯電話、携帯型映像／音声プレーヤ、ＰＤＡ、又はＰＨＳ等の契約者が持ち運び可能な携帯端末（Ｐｏｒｔａｂｌｅ  Ｄｅｖｉｃｅ）であってもよい。
【００６１】
以上、本実施形態に係る鍵提供システム１００の構成について簡単に説明した。次に、鍵提供システム１００を構成する鍵配信サーバ１０２及び端末装置１２２のハードウェア構成の具体例について簡単に説明する。
【００６２】
［鍵配信サーバ１０２及び端末装置１２２のハードウェア構成］
ここで、図２を参照しながら、本実施形態に係る鍵配信サーバ１０２及び端末装置１２２のハードウェア構成について簡単に説明する。図２は、本実施形態に係る鍵配信サーバ１０２又は端末装置１２２の機能を実現可能なハードウェア構成の一例である。
【００６３】
図２を参照すると、鍵配信サーバ１０２及び端末装置１２２は、例えば、コントローラ２０２と、演算ユニット２０４と、入出力インターフェース２０６と、セキュア記憶部２０８と、メイン記憶部２１０と、ネットワークインターフェース２１２と、メディアインターフェース２１６とにより構成される。
【００６４】
（コントローラ２０２）
コントローラ２０２は、バスを介して他の構成要素に接続されており、主に、メイン記憶部２１０に格納されたプログラム及びデータに基づいて装置内の各部を制御する役割を担う。なお、コントローラ２０２は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）等の演算処理装置により構成されていてもよい。
【００６５】
（演算ユニット２０４（鍵配信サーバ１０２の場合））
鍵配信サーバ１０２が備える演算ユニット２０４は、例えば、コンテンツの暗号化、コンテンツ鍵の暗号化、有向グラフの生成、セット鍵の生成、及びセット鍵を生成するために用いる中間鍵の導出を実行することができる。従って、演算ユニット２０４は、所定のデータ（シード値等）に基づいて擬似乱数を発生させる擬似乱数生成器として機能し得ると同時に、所定のアルゴリズムに基づいてコンテンツ又はコンテンツ鍵を暗号化することが可能である。なお、上記所定のアルゴリズムは、演算ユニット２０４が判読可能なプログラムとしてメイン記憶部２１０に格納されていてもよい。また、上記所定のデータは、メイン記憶部２１０又はセキュア記憶部２０８に格納されていてもよい。なお、演算ユニット２０４は、上記の各種演算処理を実行して得られた出力結果をメイン記憶部２１０又はセキュア記憶部２０８に記録することができる。また、演算ユニット２０４は、ＣＰＵ等の演算処理装置により構成される。なお、演算ユニット２０４は、上記のコントローラ２０２と一体に形成されていてもよい。
【００６６】
（演算ユニット２０４（端末装置１２２の場合））
端末装置１２２が備える演算ユニット２０４は、例えば、コンテンツの復号、コンテンツ鍵の復号、セット鍵の生成、及びセット鍵を生成するために用いる中間鍵の生成を実行することができる。従って、演算ユニット２０４は、所定のデータ（シード値等）に基づいて擬似乱数を発生させる擬似乱数生成器として機能し得ると同時に、所定のアルゴリズムに基づいてコンテンツ又はコンテンツ鍵を復号することが可能である。なお、所定のアルゴリズムは、演算ユニット２０４が判読可能なプログラムとしてメイン記憶部２１０に格納されていてもよい。また、所定のデータは、メイン記憶部２１０又はセキュア記憶部２０８に格納されていてもよい。なお、演算ユニット２０４は、上記の各種演算処理を実行して得られた出力結果をメイン記憶部２１０又はセキュア記憶部２０８に記録することが可能である。また、演算ユニット２０４は、例えば、ＣＰＵ等の演算処理装置により構成される。なお、演算ユニット２０４は、上記のコントローラ２０２と一体に形成されていてもよい。
【００６７】
（入出力インターフェース２０６）
入出力インターフェース２０６は、主に、ユーザがデータを入力するための入力デバイスと、演算結果又はコンテンツの中身を出力する出力デバイスとに接続されている。例えば、入力デバイスは、キーボード、マウス、トラックボール、タッチペン、キーパッド、又はタッチパネル等であってもよい。これらの入力デバイスは、入出力インターフェース２０６に対して有線又は無線により接続されていてもよい。また、入力デバイスは、有線又は無線により接続された携帯電話やＰＤＡ等の携帯型電子機器であってもよい。一方、出力デバイスは、例えば、ディスプレイ等の表示装置、又はスピーカ等の音声出力デバイス等であってもよい。そして、出力デバイスは、入出力インターフェース２０６に対して有線又は無線により接続されていてもよい。なお、上記の入出力デバイスは、鍵配信サーバ１０２又は端末装置１２２に対して一体として形成されていてもよい。
【００６８】
なお、入出力インターフェース２０６は、バスを介して他の構成要素に接続されており、入出力インターフェース２０６を介して入力されたデータをメイン記憶部２１０等に伝達することが可能である。逆に、入出力インターフェース２０６は、メイン記憶部２１０等に格納されたデータ、ネットワークインターフェース２１２等を介して入力されたデータ、又は演算ユニット２０４により当該データに基づき演算して得られた結果等を出力デバイスに出力することができる。
【００６９】
（セキュア記憶部２０８）
セキュア記憶部２０８は、主に、コンテンツ鍵、セット鍵、及び中間鍵等の秘匿が必要なデータを安全に格納するための記憶装置である。セキュア記憶部２０８は、例えば、ハードディスク等の磁気記憶装置、光ディスク等の光記憶装置、光磁気記憶装置、又は半導体記憶装置等により構成されていてもよい。また、セキュア記憶部２０８は、例えば、耐タンパ性を有する記憶装置により構成されていてもよい。
【００７０】
（メイン記憶部２１０）
メイン記憶部２１０は、例えば、コンテンツ又はコンテンツ鍵等を暗号化するための暗号化プログラム、暗号化されたコンテンツ又はコンテンツ鍵等を復号するための復号プログラム、又はセット鍵や中間鍵を生成するための鍵生成プログラム等が格納されていてもよい。また、メイン記憶部２１０は、演算ユニット２０４から出力された計算結果を一時的又は永続的に格納したり、入出力インターフェース２０６、ネットワークインターフェース２１２、又はメディアインターフェース２１６等から入力されたデータを格納してもよい。メイン記憶部２１０は、例えば、ハードディスク等の磁気記憶装置、光ディスク等の光記憶装置、光磁気記憶装置、又は半導体記憶装置等により構成されていてもよい。
【００７１】
（ネットワークインターフェース２１２）
ネットワークインターフェース２１２は、ネットワーク１０を介して他の通信装置等に接続されており、例えば、暗号化されたコンテンツ又はコンテンツ鍵、セット鍵、中間鍵等のデータ、暗号化に用いるパラメータ情報、及び許諾契約者の集合に関するデータを送受信するためのインターフェース手段である。ネットワークインターフェース２１２は、バスを介して他の構成要素に接続されており、ネットワーク１０上にある外部装置から受信したデータを他の構成要素に伝達し、又は他の構成要素が有するデータをネットワーク１０上にある外部装置に送信することが可能である。
【００７２】
（メディアインターフェース２１６）
メディアインターフェース２１６は、情報メディア２１８を着脱してデータを読み書きするためのインターフェースであり、バスを介して他の構成要素に接続されている。このメディアインターフェース２１６は、例えば、装着された情報メディア２１８からデータを読み出して他の構成要素に伝達し、又は他の構成要素から供給されたデータを情報メディア２１８に書き込むことが可能である。情報メディア２１８は、例えば、光ディスク、磁気ディスク、半導体メモリ等のポータブル記憶媒体（着脱可能な記憶媒体）であってもよいし、又はネットワーク１０を介さずに比較的近距離で有線／無線接続された情報端末の記憶媒体等であってもよい。
【００７３】
以上、本実施形態に係る鍵配信サーバ１０２及び端末装置１２２の機能を実現可能なハードウェア構成の一例を示した。上記の各構成要素は、汎用的な部材を用いて構成されていてもよいし、各構成要素の機能に特化した専用のハードウェアにより構成されていてもよい。従って、本実施形態を実施する時々の技術レベルに応じて、適宜、利用するハードウェア構成を変更することが可能である。また、上記のハードウェア構成は、あくまでも一例であり、これに限定されるものでないことは言うまでもない。例えば、コントローラ２０２と演算ユニット２０４とを同一の演算装置により構成してもよいし、セキュア記憶部２０８とメイン記憶部２１０とを同一の記憶装置により構成してもよい。また、利用形態によっては、メディアインターフェース２１６、又は入出力インターフェース２０６等を省略する構成も可能である。
【００７４】
［本実施形態を適用可能な鍵配信方式］
次に、本実施形態を適用可能な鍵配信方式の例として、ＡＩ０５方式とＡ０６（Ａ＋Ｂ）方式とについて詳細に説明する。もちろん、本実施形態を適用可能な鍵配信方式がこれに限定されないことは言うまでもなく、当業者であれば、以下の記載から他の鍵配信方式に本実施形態を適用する手段を容易に想起することが可能である。
【００７５】
（ＡＩ０５方式）
ここで、本実施形態を適用可能なＡＩ０５方式について説明する。ＡＩ０５方式は、コンテンツが配信される端末装置１２２の集合を複数の部分集合に分け、各部分集合に対応付けられたセット鍵によってコンテンツ鍵を暗号化して配信する方式である。なお、以下で説明する各処理は、主に、鍵配信サーバ１０２により実行されるものであるが、端末装置１２２においても、コンテンツ又はコンテンツ鍵を復号するための鍵を生成するために下記アルゴリズムの少なくとも一部が利用されうる。
【００７６】
ＡＩ０５方式では、コンテンツ配信の対象となる端末装置１２２の集合を複数の部分集合に分けて考える。そこで、図３を参照しながら、ＡＩ０５方式に係る部分集合の分け方について説明する。もちろん、部分集合の分け方は一通りではないが、ＡＩ０５方式では、二分木構造を用いた部分集合の分け方を採用している。ＡＩ０５方式では、二分木構造を形成する各結節点（ノード）に対し、ノード間の位置関係を考慮して所定の部分集合を対応付けることにより、所定の組合せを有する端末装置１２２の部分集合を網羅的に選択する。まず、図３を参照しながら、二分木構造の構築方法について説明する。なお、その説明に用いる表現を下記のように定義する。
【００７７】
（各種定義）
・全ての端末装置（契約者）の集合Ｎ＝｛１，・・・，ｎ｝（ｎは２のべき乗）
自然数ｉ及びｊ（但し、ｉ≦ｊ）について、
・［ｉ，ｊ］＝｛ｉ，ｉ＋１，・・・，ｊ｝
・（ｉ→ｉ）＝（ｉ←ｉ）＝｛｛ｉ｝｝
・（ｉ→ｊ）＝｛｛ｉ｝，｛ｉ，ｉ＋１｝，・・・，｛ｉ，ｉ＋１，・・・，ｊ｝｝
＝｛［ｉ，ｉ］，［ｉ，ｉ＋１］，・・・，［ｉ，ｊ］｝
・（ｉ←ｊ）＝｛｛ｊ｝，｛ｊ，ｊ−１｝，・・・，｛ｊ，ｊ−１，・・・，ｉ｝｝
＝｛［ｊ，ｊ］，［ｊ，ｊ−１］，・・・，［ｊ，ｉ］｝
【００７８】
さらに、二分木構造上の末端に位置するノードを葉ノード、頂点に位置するノードを根ノード、根ノードと葉ノードとの間に位置する各ノードを中間ノードと呼ぶことにする。また、各葉ノードは、各端末装置１２２に対応付けられている。図３の例では、ＢＴの葉ノード数ｎがｎ＝６４の場合が示されている。
【００７９】
（二分木構造の形成）
まず、葉ノードの数がｎ（例えば、ｎ＝６４）となるようにＢＴを作成する。そして、各葉ノードに対し、左端から右方向に向かって番号１，・・・，ｎを対応付ける。つまり、番号１，・・・，ｎは、各端末装置１２２に対応付けられる。次いで、ある中間ノードｖに割り当てる部分集合を規定するための指標ｌｖ及びｒｖを定義する。さらに、ある中間ノードｖの下位に位置する葉ノードのうち、最左にある葉ノードの番号をｌｖ、最右にある葉ノードの番号をｒｖと定義する。なお、中間ノードｖは、ｖを指標とするＢＴ上の中間ノードを示す。
【００８０】
次に、ＢＴ上の中間ノードを２つの集合に分類する。ＢＴ上の中間ノードのうち、親ノードの左側に位置する中間ノードの集合をＢＴＬと定義し、親ノードの右側に位置する中間ノードの集合をＢＴＲと定義する。なお、ＢＴ上で接続された２つのノード間の位置関係について、上位に位置するノードを親ノードと呼び、下位に位置するノードを子ノードと呼ぶことにする。
【００８１】
（根ノードに対する集合の対応付け）
次に、ＢＴ上の根ノードに対応付ける集合を設定する。根ノードには、その下位に全ての葉ノードが連結されているため、全ての端末装置１２２の一部又は全部が含まれる部分集合を要素に持つ集合が対応付けられる。つまり、根ノードに対応付ける集合として、集合（１→ｎ）と集合（２←ｎ）とが設定される。例えば、図３の根ノードには、集合（１→６４）と集合（２←６４）とが対応付けられる。
【００８２】
この対応付けは、以下の理由による。上記の定義により、集合（１→６４）は、部分集合［１，１］，・・・，［１，６４］を要素として含んでいるため、全ての端末装置１２２（番号１〜６４）を含む端末装置１２２のグループを［１，６４］＝｛１，・・・，６４｝により表現することができる。同様に、部分集合［１，１５］と部分集合［６４，１７］とを用いることによって、番号１６の端末装置１２２を除外した全ての端末装置１２２を表現することができる。このとき、部分集合［１，１５］は集合（１→６４）に含まれており、部分集合［６４，１７］は集合（２←６４）に含まれている。つまり、根ノードに対応付けられた集合の部分集合を用いることで、根ノードの下位に位置する葉ノード（つまり、端末装置１２２）の任意の組合せを表現することができるのである。
【００８３】
（中間ノードに対する集合の対応付け）
次に、ＢＴ上の各中間ノードに部分集合を対応付ける。まず、全てのｖについて、上記の集合ＢＴＬに属する中間ノードｖに集合（ｌｖ＋１←ｒｖ）を対応付ける。同様に、全てのｖについて、上記の集合ＢＴＲに属する中間ノードｖに集合（ｌｖ→ｒｖ−１）を対応付ける。図３には、各中間ノードに対応付けられた集合が記載されている。
【００８４】
例えば、集合（２←４）が対応付けられた中間ノードを参照すると、この中間ノードの下位に位置する２つの中間ノードには、集合（２←２）と集合（３→３）とが対応付けられている。さらに、２つの中間ノードの下位には、番号１〜４の葉ノードが連結されている。そこで、番号３を除外した葉ノードの組合せを表現する場合には、｛［１，１］，［２，２］，［４，４］｝又は｛［１，２］，［４，４］｝という部分集合の組を対応付ければよい。部分集合［１，１］及び［１，２］は、根ノードに割り当てられた集合（１→６４）の要素であり、部分集合［２，２］及び［４，４］は、それぞれ、集合（２←２）及び（２←４）の要素である。つまり、各中間ノードに対応付けられた集合の部分集合を用いることで、葉ノード（端末装置１２２）の所望の組合せを表現することができる。
【００８５】
上記の通り、ＡＩ０５方式では、ＢＴを用いて端末装置１２２の組合せを表す部分集合の組を定義している。なお、上記の部分集合により形成された全体集合のことをセットシステムＳＳと呼ぶことにする。また、セットシステムＳＳは、下式（１）のように数学的に表現される。
【００８６】
【数１】
2008236377.tif 000003
【００８７】
以上、ＡＩ０５方式における二分木構造の形成方法について説明した。ＡＩ０５方式の基本コンセプトは、上記の各部分集合に対して、コンテンツ又はコンテンツ鍵を暗号化するための複数のセット鍵を生成し、各セット鍵によりコンテンツ又はコンテンツ鍵を暗号化して所定の端末装置１２２に対して配信することにある。これまでの記載からはあまり明示的ではないかもしれないが、上記の規則に従って部分集合を定義したことにより、端末装置１２２の組合せを効率的に分類する手段が提供可能となる。以下では、上記の部分集合を利用してセット鍵を生成するアルゴリズムについて説明する。
【００８８】
（有向グラフの生成）
ここで、図４を参照しながら、セット鍵を生成するためのアルゴリズムについて説明する。このアルゴリズムは、複数の有向枝により形成される有向グラフによって表現される。そこで、この有向グラフの生成方法について詳細に説明する。まず、コンテンツ鍵を暗号化するセット鍵と、セット鍵を生成するための中間鍵とについて説明する。
【００８９】
ＡＩ０５方式では、セット鍵を生成するために擬似乱数生成器ＰＲＳＧを用いる。このＰＲＳＧは、ある部分集合Ｓ０に対応する中間鍵ｔ（Ｓ０）が入力されると、部分集合Ｓ０に対応するセット鍵ｋ（Ｓ０）と、部分集合Ｓ１，Ｓ２，・・・，Ｓｋに対応する中間鍵ｔ（Ｓ１），ｔ（Ｓ２），・・・，ｔ（Ｓｋ）とを出力する。ここで、部分集合Ｓ０と、他の部分集合Ｓ１，・・・，Ｓｋとの関係は、後述する有向グラフにより規定される。
【００９０】
なお、集合Ｓ０，Ｓ１，・・・，Ｓｋは、上記のセットシステムＳＳを構成する部分集合のいずれかであり、上記の通り、端末装置１２２の組合せを表現するものである。ＡＩ０５方式の特徴は、ＰＲＳＧの入力（例えば、ｔ（Ｓ０））と出力（例えば、ｋ（Ｓ０），ｔ（Ｓ１），・・・，ｔ（Ｓｋ））との関係を規定するロジックが表現された有向グラフの形状にある。そこで、ＡＩ０５方式に係る有向グラフの生成方法について説明する。まず、以下で用いる記号等を定義する。
【００９１】
（各種定義）
・部分集合Ｓｉに対応する中間鍵    ：  ｔ（Ｓｉ）
・部分集合Ｓｉに対応するセット鍵  ：  ｋ（Ｓｉ）
・コンテンツ鍵                    ：  ｍｅｋ
・擬似乱数生成器                  ：  ＰＲＳＧ
・有向枝                          ：  Ｅ
・有向パス（経路）                ：  Ｐ
・有向グラフ                      ：  Ｈ
・部分集合Ｓｉに対応する座標点を始点とする有向枝の数：ｄ
【００９２】
なお、集合（ｉ→ｊ）、又は集合（ｉ←ｊ）に対応するＡＩ０５方式の有向グラフをＨ（ｉ→ｊ）、又はＨ（ｉ←ｊ）と表記する。また、有向パスＰは、上記の鍵生成経路情報の一例である。さらに、ＰＲＳＧの入出力を下式（２）のように表記する。これは、ＰＲＳＧに中間鍵ｔ（Ｓ０）が入力された結果、セット鍵ｋ（Ｓ０）と、複数の中間鍵ｔ（Ｓ１），・・・，ｔ（Ｓｄ）とが出力されたことを示す。
【００９３】
【数２】
2008236377.tif 000004
【００９４】
（アルゴリズム）
まず、パラメータｋ（ｋは自然数）を決定する。但し、簡単のために、ｋ｜ｌｏｇ（ｎ）（以下、ｌｏｇの底は２）とする。パラメータｋは、結果的に端末装置１２２が保持すべき中間鍵の個数、及び端末装置１２２がセット鍵を生成するのに必要な計算量に関係する。従って、パラメータｋは、実施の態様に応じて適宜設定されるべきパラメータである。図４の例ではｋ＝６と設定している。
【００９５】
ここで、図４を参照しながら、ある中間ノードｖに対応する有向グラフＨ（ｌｖ→ｒｖ−１）に関し、有向グラフの生成方法について具体的に説明する。
【００９６】
（ステップ１）
まず、有向グラフＨ（ｌｖ→ｒｖ−１）を構成するための水平座標軸を設定する。当該水平座標軸の各座標点には、集合（ｌｖ→ｒｖ−１）を構成する各部分集合Ｓｉが対応付けられる。但し、各座標点に対応付けられる部分集合Ｓｉは、左から右に向かって包含関係が大きくなるように配置される。例えば、有向グラフＨ（５→７）＝Ｈ（｛［５，５］，［５，６］，［５，７］｝）を例に挙げると、水平座標軸の座標点には、左から順に部分集合［５，５］，［５，６］，［５，７］が対応付けられる。
【００９７】
また、図４を参照すると、各有向グラフＨが形成される水平座標軸に対して直交する複数の縦線ｚ（ｚ＝１〜６４）が描かれている。この縦線ｚと有向グラフＨとの交点が上記の座標値を表している。例えば、有向グラフＨ（ｌｖ＋１←ｒｖ）と縦線ｚとの交点は、部分集合［ｒｖ，ｚ］に対応付けられた座標点を表し、有向グラフＨ（ｌｖ→ｒｖ−１）と縦線ｚとの交点は、部分集合［ｌｖ，ｚ］に対応付けられた座標点を表す。以下、部分集合Ｓｉに対応付けられた座標点のことを座標点Ｓｉと表記することがある。
【００９８】
上記の規則に則って水平座標軸が設定された後、水平座標軸上の最左に位置する座標点の左側に１つの仮座標点を設定する。さらに、水平座標軸の最右に位置する座標点の右側に１つの仮座標点を設定する。そして、左端の仮座標点を始点とし、右端の仮座標点を終点とする。なお、左端に位置する仮座標点から右端に位置する仮座標点までの長さＬｖはＬｖ＝ｒｖ−ｌｖ＋１となる。
【００９９】
（ステップ２）有向グラフＨ（ｌｖ→ｒｖ−１）を形成する有向枝を設定する。
（２−１）ｎ（ｘ−１）／ｋ＜Ｌｖ≦ｎｘ／ｋを満たす整数ｘを算出する。但し、整数ｘは、１≦ｘ≦ｋである。
（２−２）カウンタｉを０からｘ−１まで動かしながら、次の操作を繰り返し実行する。水平座標軸上の始点から開始し、有向枝の終端が水平座標軸上の終点に到達するか、或いは、次に形成される有向枝の終端が水平座標軸上の終点を超えるまで、その座標点からｎｉ／ｋだけ離れた座標点に延びる右向きの有向枝（つまり、その座標点からｎｉ／ｋだけ離れた座標点へのジャンプ）を繰り返し生成する。
【０１００】
（ステップ３）
仮座標点を始点又は終点とする有向枝を全て削除する。
【０１０１】
（ステップ４）
ある座標点に到達する有向枝が複数ある場合、最長の有向枝のみを残して他の有向枝を全て削除する。
【０１０２】
上記のアルゴリズム（ステップ１〜ステップ４）を実行することで、有向グラフＨ（ｌｖ→ｒｖ−１）を構築することができる。
【０１０３】
ここで、図４の有向グラフＨ（３３→６３）を例に挙げて有向グラフの構成について具体的に説明する。有向グラフＨ（３３→６３）は、複数のアーチ状の曲線と、各アーチ状の曲線の一端に接続されて水平方向に延伸した直線とにより構成される。このアーチ状の曲線と水平方向に延伸した直線とが有向枝である。そして、各有向枝の端部と縦線との交点が水平座標軸の座標点である。また、連結した複数の有向枝により形成される座標点間の経路のことを有向パスと呼ぶことにする。
【０１０４】
なお、有向グラフＨ（３３→６３）の上側に表示された白抜きの矢印は、有向枝の方向を示している。この有向グラフ（３３→６３）は、ｌｖ＝３３、ｒｖ＝６４、ｋ＝６、ｎ＝６４のケースにおいて、上記のアルゴリズムを実行した結果として得られたものである。なお、図４の最下段に描かれた黒丸は、左からそれぞれ、有向グラフＨ（２←２），・・・，Ｈ（６３→６３）を表している。
【０１０５】
上記のアルゴリズムは、右向きの有向グラフＨ（ｌｖ→ｒｖ−１）を生成するためのものであったが、左向きの有向グラフＨ（ｌｖ＋１←ｒｖ）についても同様のアルゴリズムを適用して生成することが可能である。但し、有向グラフＨ（ｌｖ＋１←ｒｖ）及びＨ（２←ｎ）を形成する水平座標軸を設定する場合、水平座標軸上に右から左に向かって包含関係が大きくなるように部分集合Ｓｉを配列する点、及び有向枝の向きを左向きにする点に注意する必要がある。
【０１０６】
以上、ＡＩ０５方式に係る有向グラフＨの生成方法について説明した。以下では、有向グラフＨを用いてセット鍵を生成するロジックについて説明する。
【０１０７】
（セット鍵の生成）
ＡＩ０５方式では、セットシステムＳＳを構成する各部分集合Ｓｉに対応する各セット鍵ｋ（Ｓｉ）を用いてコンテンツ鍵ｍｅｋが暗号化される。また、上記の通り、有向グラフＨの各座標点は、端末装置１２２の組合せを表す部分集合Ｓｉに対応する。そして、セット鍵ｋ（Ｓｉ）、及び中間鍵ｔ（Ｓｉ）は、上記の各部分集合Ｓｉに対応付けられている。これらの対応関係を踏まえ、有向グラフＨに基づいてセット鍵ｋ（Ｓｉ）を生成する方法について説明する。
【０１０８】
以下、座標点Ｓ０を始端とする１本以上の有向枝の終端が示す座標点を当該有向枝の始端Ｓ０に近い順（有向枝が短い順）にＳ１，Ｓ２，・・・，Ｓｋと表現する。但し、座標点Ｓ０を始端とする有向枝の本数がｑ本（ｑ＜ｋ）である場合、座標点Ｓ（ｑ＋１），Ｓ（ｑ＋２），・・・，Ｓｋはダミーとしてカウントするが実際には使用しない。なお、上記の（ステップ２−２）における繰り返し処理の回数がｘ回（１≦ｘ≦ｋ）であるため、有向グラフＨの各座標点を始端とする有向枝の本数は最大でｋ本である。
【０１０９】
ＡＩ０５方式によると、λビットの入力に対して（ｋ＋１）＊λビットを出力するＰＲＳＧを利用してセット鍵ｋ（Ｓｉ）を生成する。このＰＲＳＧは、座標点Ｓ０に対応する中間鍵ｔ（Ｓ０）を入力すると、座標点Ｓ０を始端とする有向枝が到達する各座標点（例えば、座標点Ｓ１，Ｓ２，・・・，Ｓｋ）に対応する中間鍵ｔ（Ｓ１），ｔ（Ｓ２），・・・，ｔ（Ｓｋ）と、入力した中間鍵（Ｓ０）に対応するセット鍵ｋ（Ｓ０）とが出力される。つまり、ｔ（Ｓ１）｜｜・・・｜｜ｔ（Ｓｋ）｜｜ｋ（Ｓ０）←ＰＲＳＧ（ｔ（Ｓ０））となる。そこで、ＰＲＳＧの出力を左からλビット毎に区切ることにより、中間鍵ｔ（Ｓ１），ｔ（Ｓ２），・・・，ｔ（Ｓｋ）と、セット鍵ｋ（Ｓ０）とを生成することができる。
【０１１０】
例えば、図４を参照し、有向グラフＨ（１→６４）の座標点Ｓ０＝［１，８］（左端から８番目の座標点）に注目すると、座標点Ｓ０からは４本の有向枝が出ていることが分かる。この有向枝の終点は、それぞれ、座標点Ｓ１＝［１，９］，Ｓ２＝［１，１０］，Ｓ３＝［１、１２］，Ｓ４＝［１、１６］である。そこで、中間鍵ｔ（Ｓ０）をＰＲＳＧに入力すると、セット鍵ｋ（Ｓ０）と、中間鍵ｔ（Ｓ１），ｔ（Ｓ２），ｔ（Ｓ３），ｔ（Ｓ４）とを生成することができる。さらに、中間鍵ｔ（Ｓ４）をＰＲＳＧに入力することにより、セット鍵ｋ（Ｓ４）と、Ｓ１１＝［１，１７］，Ｓ１２＝［１，１８］，Ｓ１３＝［１，２０］，Ｓ１４＝［１，２４］，Ｓ１５＝［１，３２］に対応する中間鍵ｔ（Ｓ１１），ｔ（Ｓ１２），ｔ（Ｓ１３），ｔ（Ｓ１４），ｔ（Ｓ１５）とを生成することができる。このように、ＰＲＳＧを繰り返し用いることによって複数のセット鍵を算出することができる。
【０１１１】
上記の通り、所定の中間鍵ｔ（Ｓ０）を保持していると、有向グラフＨに基づいて中間鍵とセット鍵とを生成することが可能になる。しかし、有向グラフＨの情報を参照できない場合には、所定の中間鍵ｔ（Ｓ０）をＰＲＳＧに入力して生成される中間鍵又はセット鍵が不明であるため、所望のセット鍵を生成することが困難である。この問題に対する解決策を提供するのが本実施形態の目的である。これについては後述する。
【０１１２】
これまで、中間鍵を利用する鍵生成方法について説明したが、既存のＡＩ０５方式においても、後述する本実施形態においても中間鍵を利用する構成は必須ではない。そもそも、中間鍵は、安全性を高める目的で使用しているのであって、安全性に格段の注意を払わなくてもよい場面、又はセット鍵生成のための演算量を減らしたい場合等においては、中間鍵を使わずに、セット鍵ｋ（Ｓ０）から別のセット鍵ｋ（Ｓ１）等を直接的に算出可能な構成にしてもよい。例えば、セット鍵ｋ（Ｓ０）がＰＲＳＧに入力されると、座標点Ｓ０から伸びる有向枝の到達先に対応するセット鍵ｋ（Ｓ１），ｋ（Ｓ２），ｋ（Ｓ３），ｋ（Ｓ４）が出力されるように構成してもよい。
【０１１３】
以上、セット鍵の生成方法について説明した。上記の例から容易に理解される通り、ある中間鍵を保持していると、その中間鍵を利用し、ＰＲＳＧを反復して実行することにより、その中間鍵に対応する座標点から伸びた有向枝の鎖によって到達可能な全ての座標点に対応する中間鍵とセット鍵とを導き出すことができるのである。従って、各端末装置１２２は、自己が要素として含まれる部分集合に対応する中間鍵を全て導出できる最低限の中間鍵を保持していればよいことになる。
【０１１４】
なお、鍵配信サーバ１０２は、各有向グラフＨの先頭座標点（以下、ルートと呼ぶ）に対応する中間鍵を利用し、ＰＲＳＧによる演算を繰り返し実行することにより、各有向グラフを構成する有向枝が到達可能な全ての座標点に対応するセット鍵を導出することができる。
【０１１５】
従って、鍵提供システム１００の管理者は、鍵提供システム１００のセットアップ時に、例えばλビットの乱数を生成し、鍵配信サーバ１０２において各有向グラフＨのルートの中間鍵として設定すればよい。上記の有向グラフＨのルートとは、その座標点から有向枝が出ているが、その座標点に到達することのない座標点のことを言う。例えば、図４の有向グラフＨ（１→６４）のルートは、水平座標軸の左端に位置する座標点［１，１］である。
【０１１６】
以上、セット鍵の生成方法について説明した。この方法は、コンテンツ又はコンテンツ鍵の送信者側である鍵配信サーバ１０２がコンテンツ又はコンテンツ鍵を暗号化するためのセット鍵と、各端末装置１２２に配信する中間鍵とを生成する際に用いられるだけでなく、受信者側の端末装置１２２においても、自己が予め保持する中間鍵を利用して所望のセット鍵を生成するために用いられる。
【０１１７】
（中間鍵の配信方法）
次いで、鍵配信サーバ１０２が各端末装置１２２に対して所定の中間鍵を配信する方法について説明する。なお、各端末装置１２２に対しては、その端末装置１２２が含まれる全ての部分集合に対応するセット鍵を導出可能な複数の中間鍵が予め与えられている。逆に、その端末装置１２２に対し、当該端末装置１２２が含まれていない部分集合に対応するセット鍵を導出することが可能な中間鍵を与えてはならないし、当該端末装置１２２に与える中間鍵の数が最小限になる方が好ましい。
【０１１８】
そこで、鍵配信サーバ１０２は、契約者ｕの端末装置１２２が含まれる部分集合に対応する座標点に到達可能な有向グラフＨを全て抽出する。そのうち、有向グラフＨのルートに対応する部分集合に契約者ｕの端末装置１２２が含まれる場合は、そのルートに対応する中間鍵のみを契約者ｕの端末装置１２２に与える。
【０１１９】
また、有向グラフＨのルート以外の座標点に対応する部分集合のいずれかに契約者ｕの端末装置１２２が含まれる場合は、契約者ｕの端末装置１２２が部分集合Ｓ０に含まれ、かつ、部分集合Ｓ０の親である部分集合ｐａｒｅｎｔ（Ｓ０）に含まれない部分集合Ｓ０を抽出する。そして、その部分集合Ｓ０に対応する中間鍵ｔ（Ｓ０）を契約者ｕの端末装置１２２に対して与える。
【０１２０】
つまり、有向グラフＨのルート以外の複数の座標点に対応する部分集合に契約者ｕの端末装置１２２が含まれる場合は、各座標点に到達する有向枝の始端を参照し、各座標点の始端に対応する部分集合が契約者ｕに対応する端末装置１２２を含まないような座標点を選択する。この座標点に対応する部分集合をＳ０とし、座標点Ｓ０に到達する有向枝の始端（親）に対応する部分集合をｐａｒｅｎｔ（Ｓ０）とすると、部分集合ｐａｒｅｎｔ（Ｓ０）を含まない座標点Ｓ０に対応する中間鍵ｔ（Ｓ０）を契約者ｕの端末装置１２２に与えればよいことになる。
【０１２１】
もし、そのような座標点Ｓ０が複数個存在する場合は、それぞれの中間鍵ｔ（Ｓ０）を契約者ｕの端末装置１２２に与える。なお、座標点の親子関係は、有向枝により規定される。つまり、有向枝の始端が終端の親となり、有向枝の終端が始端の子となる。また、座標点Ｓ０の親をｐａｒｅｎｔ（Ｓ０）と表記する。もちろん、座標点Ｓ０が有効グラフＨのルートである場合には座標点Ｓ０の親は存在しない。また、有効グラフＨのルートではない場合には座標点Ｓ０の親はただ１つ存在する。
【０１２２】
ここで、図４の例を参照しながら、中間鍵の配信方法について具体的に説明する。
【０１２３】
（例１）
契約者１の端末装置１２２に対して配信される中間鍵について考える。まず、契約者１の端末装置１２２が含まれる部分集合に到達可能な有向グラフＨを抽出する。図４を参照すると、そのような有向グラフＨは、有向グラフＨ（１→６４）のみであることが分かる。そして、契約者１の端末装置１２２は、有向グラフＨ（１→６４）のルートに対応する部分集合［１，１］に属している。従って、契約者１の端末装置１２２には、中間鍵ｔ（［１，１］）が配信される。
【０１２４】
（例２）
契約者３の端末装置１２２に対して配信される中間鍵について考える。まず、契約者３の端末装置１２２が含まれる部分集合に到達可能な有向グラフＨを抽出する。図４を参照すると、そのような有向グラフＨは、有向グラフＨ（１→６４），Ｈ（２←６４），Ｈ（２←３２），Ｈ（２←１６），Ｈ（２←８），Ｈ（２←４），Ｈ（３→３）であることが分かる。まず、有向グラフＨ（１→６４）について検討すると、契約者３の端末装置１２２は、有向グラフＨ（１→６４）のルートに対応する部分集合［１，１］に含まれていないことが分かる。
【０１２５】
しかし、契約者３の端末装置１２２は、３番目の座標点以降の部分集合［１，３］，［１，４］，・・・，［１，６４］に含まれている。そこで、これらの座標点の親の部分集合を参照すると、親の部分集合に契約者３の端末装置１２２を含まない座標点は、［１，３］及び［１，４］のみであることが分かる。従って、座標点［１，３］，［１，４］の親ｐａｒｅｎｔ（［１，３］）及びｐａｒｅｎｔ（［１，４］）に該当する座標点［１，２］は、契約者３の端末装置１２２を含んでいないことが分かる。
【０１２６】
その結果、契約者３の端末装置１２２には、有向グラフＨ（１→６４）に対応する中間鍵ｔ（［１，３］）及びｔ（［１，４］）が配信される。同様に、他の有向グラフＨ（２←６４），Ｈ（２←３２），Ｈ（２←１６），Ｈ（２←８），Ｈ（２←４），Ｈ（３→３）についても中間鍵が選択されて契約者３の端末装置１２２に配信される。結局、契約者３の端末装置１２２には、合計８個の中間鍵が配信される。
【０１２７】
次に、図５を参照しながら、鍵配信サーバ１０２が各端末装置１２２に中間鍵を配信する処理について簡単に説明する。図５は、システムをセットアップする際に鍵配信サーバ１０２が各端末装置１２２に中間鍵を配信する処理を表した流れ図である。
【０１２８】
図５を参照すると、鍵配信サーバ１０２は、契約者数ｎ、セット鍵及び中間鍵のビット数λ、所定のパラメータｋ、及びＰＲＳＧによる擬似乱数生成アルゴリズム等を決定し、全ての端末装置１２２に対して公開する（Ｓ１０２）。次いで、鍵配信サーバ１０２は、端末装置１２２の集合を所定の部分集合に分けた後、その和集合によって表現されるセットシステムＳＳ（上式（１））を決定して全ての端末装置１２２に対して公開する（Ｓ１０４）。次いで、鍵配信サーバ１０２は、複数の有向枝Ｔにより形成される有向グラフＨを決定し、その情報の一部又は全部を全ての端末装置１２２に対して公開する（Ｓ１０６）。次いで、セットシステムＳＳを構成する各部分集合に対応する中間鍵を決定する（Ｓ１０８）。そして、各端末装置１２２に対し、各端末装置１２２が有向グラフに基づいて所望のセット鍵を導出するために必要な中間鍵を配布する（Ｓ１１０）。
【０１２９】
以上、中間鍵の配信方法について説明した。この配信方法を用いると、各許諾契約者の端末装置１２２がセット鍵を生成するために必要な中間鍵を効率的に配信することが可能になり、鍵配信サーバ１０２と端末装置１２２と間の通信量、及び各端末装置１２２が鍵の保持に要するメモリ量を節約することができる。
【０１３０】
（コンテンツ鍵の配信方法）
次に、鍵配信サーバ１０２により暗号化されたコンテンツ鍵ｍｅｋの配信方法について説明する。
【０１３１】
まず、鍵配信サーバ１０２は、許諾契約者の端末装置１２２のみが生成可能なセット鍵を用いてコンテンツ鍵ｍｅｋを暗号化する。鍵配信サーバ１０２は、排除すべき契約者（以下、排除契約者）の端末装置１２２が含まれる集合Ｒを決定し、全契約者１〜ｎの端末装置１２２が含まれる集合Ｎから集合Ｒを除外した集合Ｎ＼Ｒを決定する。
【０１３２】
そして、セットシステムＳＳを構成する部分集合の中から１又は複数の部分集合Ｓｉ（ｉ＝１，２，・・・，ｍ）を選択し、選択された部分集合を用いて集合Ｎ＼Ｒ＝Ｓ１∪Ｓ２∪・・・∪Ｓｍを表現する。このとき、部分集合Ｓｉの組合せは多数存在するが、ｍが最小となるような部分集合Ｓｉを選択する方が望ましい。
【０１３３】
鍵配信サーバ１０２は、上記の部分集合Ｓｉを選択した後、各部分集合Ｓｉに対応するセット鍵ｋ（Ｓｉ）を用いてコンテンツ鍵ｍｅｋを暗号化し、セット鍵ｋ（Ｓ１）、ｋ（Ｓ２），・・・，ｋ（Ｓｍ）によって暗号化されたｍ個のコンテンツ鍵ｍｅｋを生成する。そして、鍵配信サーバ１０２は、ｍ個の暗号化されたコンテンツ鍵ｍｅｋが全契約者１〜ｎの端末装置１２２に対して配信する。このとき、鍵配信サーバ１０２は、集合Ｎ＼Ｒの情報、及びｍ個の部分集合Ｓｉの情報の一方又は両方も同時に各端末装置１２２に対して配信する。
【０１３４】
次に、図６を参照しながら、鍵配信サーバ１０２により暗号化されたコンテンツ鍵ｍｅｋの配信処理について簡単に説明する。図６は、コンテンツ鍵の配信処理の流れを示す説明図である。
【０１３５】
図６を参照すると、鍵配信サーバ１０２は、排除契約者の集合Ｒを決定し、許諾契約者の集合Ｎ＼Ｒを決定する（Ｓ１１２）。次いで、鍵配信サーバ１０２は、セットシステムＳＳを構成する部分集合から、和集合がＮ＼Ｒとなるｍ個の部分集合Ｓｉ（ｉ＝１，２，・・・，ｍ）を選択する（Ｓ１１４）。次いで、鍵配信サーバ１０２は、選択された各部分集合Ｓｉに対応するセット鍵ｋ（Ｓｉ）を用いてコンテンツ鍵ｍｅｋをそれぞれ暗号化する（Ｓ１１６）。次いで、鍵配信サーバ１０２は、集合Ｎ＼Ｒ又は各部分集合Ｓｉを表す情報と、ｍ個の暗号化されたコンテンツ鍵ｍｅｋとを全ての端末装置１２２に対して配信する（Ｓ１１８）。
【０１３６】
以上、鍵配信サーバ１０２によるコンテンツ鍵ｍｅｋの暗号化方法、及び配信方法について説明した。上記の暗号化方法を用いると、暗号化に要するセット鍵数が最小限となるように部分集合Ｓｉを選択することができる。そのため、コンテンツ鍵ｍｅｋを暗号化する際に、暗号化に要する計算量を低減できると共に、配信すべき暗号化されたコンテンツ鍵ｍｅｋの数を低減させることが可能になり、通信量の低減化も実現されうる。
【０１３７】
（コンテンツ鍵の復号方法）
次に、各端末装置１２２におけるコンテンツ又はコンテンツ鍵の復号処理について説明する。端末装置１２２は、上記鍵配信サーバから受信した集合Ｎ＼Ｒ又はｍ個の部分集合Ｓｉの情報と、ｍ個の暗号化されたコンテンツ鍵とに基づいてコンテンツ鍵ｍｅｋを復号する。
【０１３８】
端末装置１２２は、鍵配信サーバ１０２から暗号化されたコンテンツ鍵ｍｅｋと、集合Ｎ＼Ｒを表す情報又はｍ個の部分集合Ｓｉを表す情報とを受信する。次いで、端末装置１２２は、これらの情報を解析して、自身がｍ個の部分集合Ｓｉのいずれかに含まれるか否かを判断する。次いで、端末装置１２２は、自身がいずれの部分集合にも含まれないと判断した場合、自身が排除契約者の端末装置１２２であると判断して復号処理を終了する。逆に、自身が含まれる部分集合Ｓｉが発見された場合、端末装置１２２は、上記のＰＲＳＧを利用して当該部分集合Ｓｉに対応するセット鍵ｋ（Ｓｉ）を導出する。但し、端末装置１２２が利用するＰＲＳＧの構成は、上記の鍵配信サーバ１０２が暗号化に利用したＰＲＳＧの構成と同様である。
【０１３９】
なお、端末装置１２２は、システムのセットアップに際し、鍵配信サーバ１０２から上記の部分集合Ｓｉに対応する中間鍵ｔ（Ｓｉ）又は当該中間鍵ｔ（Ｓｉ）を導出可能な中間鍵ｔ（Ｓｊ）が予め配信されているものとする。従って、端末装置１２２は、保持している中間鍵ｔ（Ｓｉ）又はｔ（Ｓｊ）をＰＲＳＧに入力し、上記部分集合Ｓｉに対応するセット鍵ｋ（Ｓｉ）を導出することが可能である。このとき、端末装置１２２は、有向グラフの情報を参照してＰＲＳＧの処理を繰り返し実行し、上記のセット鍵ｋ（Ｓｉ）を算出する必要があるかもしれない。次いで、端末装置１２２は、導出したセット鍵ｋ（Ｓｉ）を用いて暗号化されたコンテンツ鍵ｍｅｋを復号する。
【０１４０】
ここで、再び図４を参照する。図４を参照しながら、端末装置１２２における上記セット鍵ｋ（Ｓｉ）の導出方法について具体例を挙げて説明する。
【０１４１】
（例１）
図４に示した有向グラフＨに基づいて、契約者３の端末装置１２２が部分集合［１，８］に対応するセット鍵を導出する過程について考える。なお、鍵配信サーバ１０２は、システムセットアップの際、契約者３の端末装置１２２に対して予め部分集合［１，４］の中間鍵を配信している。
【０１４２】
まず、有向グラフＨ（１→６４）を参照すると、座標点［１，４］から座標点［１，８］に延びる有向枝が存在する。この有向枝は、座標点［１，４］を始端とする有向枝のうち３番目に距離が短いものである。そこで、契約者３の端末装置１２２は、座標点［１，４］に対応する中間鍵ｔ（［１，４］）をＰＲＳＧに入力して得られる出力のうち、先頭から第３番目のλビットの部分を抽出する。出力の第３番目のλビット部分が部分集合［１，８］に対応する中間鍵ｔ（［１，８］）なのである。そこで、契約者３の端末装置１２２は、ＰＲＳＧの出力から中間鍵ｔ（［１，８］）を抽出した後、中間鍵ｔ（Ｓ［１，８］）を再度ＰＲＳＧに入力して得られた出力の最終λビットを抽出する。出力の最終λビットが所望のセット鍵ｋ（［１，８］）なのである。以上の処理により、契約者３の端末装置１２２は、所望のセット鍵ｋ（［１，８］）を生成することができる。
【０１４３】
（例２）
同様に、図４の有向グラフＨに基づいて、契約者１の端末装置１２２がセット鍵ｋ（［１，８］）を生成する場合について考える。契約者１の端末装置１２２は、部分集合［１，１］に対応する中間鍵ｔ（［１，１］）を予め保持している。そこで、契約者１の端末装置１２２は、中間鍵ｔ（［１，１］）をＰＲＳＧに入力して得られた出力の先頭から第１番目のλビットの部分（中間鍵ｔ（［１，２］））を抽出する。次いで、契約者１の端末装置１２２は、中間鍵ｔ（［１，２］）を再度ＰＲＳＧに入力して得られた出力の先頭から第２番目のλビットの部分（中間鍵ｔ（［１，４］））を抽出する。さらに、契約者１の端末装置１２２は、中間鍵ｔ（［１，４］）を再度ＰＲＳＧに入力して得られた出力の先頭から第３番目のλビットの部分（中間鍵ｔ（［１，８］））を抽出する。最後に、契約者１の端末装置１２２は、中間鍵ｔ（［１，８］）をＰＲＳＧに入力して得られた出力の最終λビット（セット鍵ｋ（［１，８］））を抽出して、所望のセット鍵ｋ（［１，８］）を取得することができる。
【０１４４】
次に、図７を参照しながら、各端末装置１２２における暗号化されたコンテンツ鍵ｍｅｋの復号処理について説明する。図７は、各端末装置１２２におけるコンテンツ鍵の復号処理の流れを示す説明図である。
【０１４５】
図７を参照すると、端末装置１２２は、鍵配信サーバ１０２からｍ個の暗号化されたコンテンツ鍵ｍｅｋと、集合Ｎ＼Ｒを表す情報又はｍ個の部分集合Ｓｉ（ｉ＝１，２，・・・，ｍ）を表す情報とを受信する（Ｓ１２０）。次いで、端末装置１２２は、自身が含まれる部分集合Ｓｉを検索し（Ｓ１２２）、自身がｍ個の部分集合Ｓｉのいずれかに含まれているか否かを判断する（Ｓ１２４）。
【０１４６】
自身が含まれる部分集合Ｓｉが存在する場合、端末装置１２２は、上記のＰＲＳＧを利用して、その部分集合Ｓｉに対応するセット鍵ｋ（Ｓｉ）を導出する（Ｓ１２６）。次いで、端末装置１２２は、導出したセット鍵ｋ（Ｓｉ）を用いて暗号化されたコンテンツ鍵ｍｅｋを復号する（Ｓ１２８）。
【０１４７】
一方、自身がいずれの部分集合Ｓｉにも含まれないと判断した場合、端末装置１２２は、自身が許諾契約者の端末装置１２２ではない旨（排除契約者である旨）を表示出力し（Ｓ１３０）、コンテンツ鍵の復号処理を終了する。
【０１４８】
以上、端末装置１２２におけるコンテンツ鍵の復号方法について説明した。上記の復号方法には、端末装置１２２側にも有向グラフの情報とＰＲＳＧとが必要とされる。しかし、有向グラフの情報を全て端末装置１２２が保持しておくことは端末装置１２２のメモリ量を大きく圧迫するという点で困難であり、また、端末装置１２２が全ての有向グラフを生成することも端末装置１２２の演算負荷を増大させるという点で困難である。もちろん、有向グラフの情報を全て配信することも通信量の著しい増大又は配信媒体の記憶容量の圧迫という点から困難である。本実施形態に係る鍵提供システム１００は、こうした問題点を解決する手段を提供するものであり、その特徴については後述する。
【０１４９】
（ＡＩ０５方式のまとめ）
以上、本実施形態を適用可能なＡＩ０５方式について説明してきた。このＡＩ０５方式を用いると、各端末装置１２２が保持すべき中間鍵の個数をＯ（ｋ＊ｌｏｇ（ｎ））に抑えることができる。また、セット鍵の生成に要する計算量（ＰＲＳＧの動作回数）を（２ｋ−１）＊（ｎ１／ｋ−１）程度又はそれ以下に抑えることができる。しかし、本件出願人が既に指摘している通り、ＡＩ０５方式には効率化の観点からいくつかの改善の余地が残されている。例えば、Ａ０６（Ａ）方式では端末装置１２２が保持すべき鍵数を削減することに成功しており、Ａ０６（Ｂ）方式では端末装置１２２が鍵生成に要する演算量を低減させることに成功している。そして、Ａ０６（Ａ＋Ｂ）方式において端末装置１２２の保持すべき鍵数と鍵生成に要する演算量とをバランス良く低減させることに成功している。本実施形態の特徴は、端末装置１２２が鍵生成する際に必要な有向グラフの情報を如何にして提供するかという点にあるため、少なくとも上記の各方式の全てに適用が可能である。
【０１５０】
（Ａ０６（Ａ＋Ｂ）方式）
次に、本実施形態を適用可能なＡ０６（Ａ＋Ｂ）方式について説明する。上記の通り、Ａ０６（Ａ＋Ｂ）方式は、ＡＩ０５方式に比べて効率的な鍵配信を実現可能な方式である。従って、本実施形態を適用するに当り、Ａ０６（Ａ＋Ｂ）方式を適用する方がより効率的である。
【０１５１】
Ａ０６（Ａ＋Ｂ）方式について説明するに先立ち、鍵配信の効率について簡単に説明する。まず、端末装置１２２が所望の鍵生成に要する計算量は、所望の中間鍵を導出するためにＰＲＳＧを実行する回数に依存している。この最悪値は、有向グラフＨを辿りながら、ルートから最も遠い末尾の座標点（有向枝が出ていないリーフ）に到達するまでに存在する有向枝の本数に対応する。図４の有向グラフＨ（１→６４）を参照すると、ルート［１，１］から末尾の座標点［１，６４］に到達するまでに１１本の有向枝を経由しており、中間鍵ｔ（［１，１］）を保持する端末装置１２２が中間鍵ｔ（［１，６４］）を導出するためにＰＲＳＧを１１回も実行しなければならないことを意味している。従って、水平座標軸上の全ての座標点に到達可能な経路を確保しつつ、有向グラフの最長パスを構成する有向枝数を低減させることができれば、端末装置１２２の演算量を低減させることができるのである。この課題に対する一つのアプローチがＡ０６（Ｂ）方式であり、これを更に改良したものがＡ０６（Ａ＋Ｂ）方式である。そこで、本実施形態をＡ０６（Ａ＋Ｂ）方式に適用する場合を例に挙げて詳細に説明する。
【０１５２】
［鍵配信サーバ１０２の構成］
まず、図８を参照しながら、本実施形態に係る鍵配信サーバ１０２の構成について説明する。図８は、本実施形態に係る鍵配信サーバ１０２及び端末装置１２２の構成を示す説明図である。
【０１５３】
図８を参照すると、鍵配信サーバ１０２は、主に、木構造設定部１０４と、座標軸設定部１０６と、仮有向グラフ生成部１０８と、有向グラフ生成部１１０と、初期中間鍵設定部１１２と、鍵生成部１１４と、暗号化部１１６と、通信部１１８と、部分集合決定部１２０とにより構成される。また、木構造設定部１０４と、座標軸設定部１０６と、仮有向グラフ生成部１０８と、有向グラフ生成部１１０とを纏めて、鍵生成ロジック構築ブロックと呼ぶことにする。同様に、初期中間鍵設定部１１２と、鍵生成部１１４とを纏めて、鍵生成ブロックと呼ぶことにする。なお、座標軸設定部１０６、仮有向グラフ生成部１０８、有向グラフ生成部１１０は、上記の集合関係情報生成部又は集合関係情報取得部の一例である。また、通信部１１８は、上記の鍵生成経路情報提供部又は暗号情報提供部の一例である。
【０１５４】
［鍵生成ロジック構築ブロック］
まず、鍵生成ロジック構築ブロックについて詳細に説明する。
【０１５５】
（木構造設定部１０４）
まず、木構造設定部１０４について説明する。木構造設定部１０４は、上記ＡＩ０５方式と同様の二分木構造（図３を参照）を生成することができる。まず、木構造設定部１０４は、番号１〜ｎ（ｎは自然数）のｎ個の葉ノードと、根ノードと、根ノード及び葉ノード以外の複数の中間ノードとにより形成される二分木構造を設定する。次いで、木構造設定部１０４は、ある中間ノードｖ又は根ノードｖの下位に配置された複数の葉ノードのうち、左端に位置する前記葉ノードの番号をｌｖとし、右端に位置する前記葉ノードの番号をｒｖと設定する。次いで、木構造設定部１０４は、根ノードに対して集合（１→ｎ）と集合（２←ｎ）とを割り当てる。次いで、木構造設定部１０４は、上記の二分木を形成する任意の中間ノードｖの対し、中間ノードｖが親ノードの左側に位置する場合には集合（ｌｖ＋１←ｒｖ）を対応付け、逆に、中間ノードｖが親ノードの右側に位置する場合には集合（ｌｖ→ｒｖ−１）を対応付ける。
【０１５６】
（座標軸設定部１０６）
次に、座標軸設定部１０６について説明する。座標軸設定部１０６は、上記ＡＩ０５方式と類似した規則に基づいて水平座標軸を設定する。まず、座標軸設定部１０６は、複数の水平座標軸を設定する。次いで、座標軸設定部１０６は、集合（１→ｎ−１）に含まれる複数の部分集合を左側から順に右方向に向かって包含関係が大きくなるように、一つの水平座標軸上の各座標点に対応付ける。同様に、座標軸設定部１０６は、集合（ｌｖ→ｒｖ−１）に含まれる複数の部分集合を左側から順に右方向に向かって包含関係が大きくなるように、他の一つの水平座標軸上の各座標点に対応付ける。もちろん、座標軸設定部１０６は、上記の二分木を形成する中間ノードに対応付けられた全ての集合（ｌｖ→ｒｖ−１）について同様の処理を繰り返す。
【０１５７】
次いで、座標軸設定部１０６は、集合（２←ｎ）に含まれる複数の部分集合を右側から順に左方向に向かって包含関係が大きくなるように、さらに別の一つの水平座標軸上の各座標点に対応付ける。同様に、座標軸設定部１０６は、集合（ｌｖ＋１←ｒｖ）に含まれる複数の部分集合を右側から順に左方向に向かって包含関係が大きくなるように、さらに別の一つの水平座標軸上の各座標点に対応付ける。もちろん、座標軸設定部１０６は、上記の二分木を形成する中間ノードに対応付けられた全ての集合（ｌｖ＋１←ｒｖ）について同様の処理を繰り返す。
【０１５８】
次いで、座標軸設定部１０６は、集合（１→ｎ−１）に対応する水平座標軸の右端に位置する座標点の右側に２つの仮座標点を生成する。次いで、座標軸設定部１０６は、集合（ｌｖ→ｒｖ−１）に対応する水平座標軸の右端に位置する座標点の右側に２つの仮座標点を生成する。次いで、座標軸設定部１０６は、集合（２←ｎ）に対応する水平座標軸と、集合（ｌｖ＋１←ｒｖ）に対応する水平座標軸の左端に位置する座標点の左側に２つの仮座標点を生成する。
【０１５９】
以上の処理により、座標軸設定部１０６は、二分木を形成する全てのノードに対応付けられた集合に対して有向グラフを形成するための水平座標軸を設定することができる。以下、座標軸設定部１０６により生成された各水平座標軸上に有向グラフを形成する手段について説明する。
【０１６０】
（仮有向グラフ生成部１０８）
次に、仮有向グラフ生成部１０８について説明する。仮有向グラフ生成部１０８は、上記のＡＩ０５方式で有向グラフＨを生成したのと類似した方法により、仮有向グラフＩ’を生成する。まず、仮有向グラフ生成部１０８は、所定の整数ｋをパラメータとして設定する。次いで、仮有向グラフ生成部１０８は、ｎ（ｘ−１）／ｋ＜ｒｖ−ｌｖ＋１≦ｎｘ／ｋを満たす整数ｘを決定する。次いで、仮有向グラフ生成部１０８は、集合（１→ｎ−１）及び集合（ｌｖ→ｒｖ−１）に対応する水平座標軸上に、ｎｉ／ｋ（ｉ＝０〜ｘ−１）の長さを有する右方向を向いた有向枝を形成する。次いで、仮有向グラフ生成部１０８は、集合（２←ｎ）及び集合（ｌｖ＋１←ｒｖ）に対応する水平座標軸上に、ｎｉ／ｋ（ｉ＝０〜ｘ−１）の長さを有する左方向を向いた有向枝を形成する。
【０１６１】
上記の通り、ＡＩ０５方式において、部分集合のうちで最も要素数の少ない部分集合（即ち、一人のユーザからなる部分集合）に対応する座標点の隣に配置された仮座標点から有向枝の生成が開始される。これに対し、Ａ０６（Ａ＋Ｂ）方式では、部分集合のうちで最も要素数の少ない部分集合（即ち、一人のユーザからなる部分集合）に対応する座標点から有向枝の生成が開始される点に注意が必要である。
【０１６２】
次いで、仮有向グラフ生成部１０８は、上記の全ての水平座標軸上の有向枝について、水平座標軸上の仮座標点を始端又は終端とする全ての有向枝を消去する。次いで、仮有向グラフ生成部１０８は、上記の全ての水平座標軸上の全ての座標点について、一つの座標点に到達する有向枝が複数存在する場合、その座標点に到達する複数の有向枝の中から最長の有向枝以外の全ての有向枝を消去する。次いで、仮有向グラフ生成部１０８は、集合（１→ｎ−１）に対応する水平座標軸上に生成された仮座標点のうち、左側に位置する仮座標点を終端とする長さ１の右向き有向枝を追加する。つまり、仮有向グラフ生成部１０８は、下式（３）の処理を実行することにより、根ノードに対応付けられた集合（１→ｎ）に対応する仮有向グラフＩ’（１→ｎ）を生成することができる。
【０１６３】
【数３】
2008236377.tif 000005
【０１６４】
以上の処理により、仮有向グラフ生成部１０８は、ＡＩ０５方式に比べて長い有向枝により構成される仮有向グラフＩ’を形成することができる。このアルゴリズムは、Ａ０６（Ｂ）方式の基本コンセプトに基づくものである。このアルゴリズムを適用することにより、端末装置１２２が鍵生成に要する演算量を低減させる効果が得られる。
【０１６５】
（アルゴリズム）
ここで、図９を参照しながら、座標軸設定部１０６及び仮有向グラフ生成部１０８により実行される処理の流れについて簡単に整理する。なお、図９に示す流れ図は、一例として、集合（ｌｖ→ｒｖ−１）に対応する仮有向グラフＩ’（ｌｖ→ｒｖ−１）の生成方法を示したものである。
【０１６６】
（Ｓ１４０）まず、集合（ｌｖ→ｒｖ−１）の要素を水平直線上に左から右に包含関係が大きくなるように並べる。そして、最左の座標点を始点とする。さらに、最右の座標点の右に２つの仮座標点を配置する。すると、始点から最右の仮座標点までの長さは、Ｌｖ＝ｒｖ−ｌｖ＋１となる。さらに、ｎ（ｘ−１）／ｋ＜Ｌｖ≦ｎｘ／ｋを満たす整数ｘ（１≦ｘ≦ｋ）を算定する。
【０１６７】
（Ｓ１４２）次いで、カウンタｉを０〜ｘ−１まで動かしながら下記の操作を行う。始点から開始し、その座標点からｎｉ／ｋだけ離れた座標点へのジャンプを続け、仮座標点に到達するか、次のジャンプが仮座標点を超えたところで終了する。その後、各ジャンプに対応する有向枝を生成する。
【０１６８】
（Ｓ１４４）次いで、仮座標点に到達する有向枝を全て消去する。
【０１６９】
（Ｓ１４６）ある座標点Ｔに到達する有向枝が複数ある場合には、ジャンプの距離が一番長いもののみを残し、それ以外の有向枝は消去する。
【０１７０】
上記のアルゴリズムを適用することにより、図１０に示した仮有向グラフＩ’を生成することができる。但し、図１０の仮有向グラフＩ’は、葉ノード数ｎ＝６４、パラメータｋ＝６と設定したケースである。以下、この仮有向グラフＩ’を形成する複数の有向枝の一部を所定の規則に基づいて置換し、有向グラフＩを生成するアルゴリズムについて説明する。なお、有向枝の置換処理は、主に、有向グラフ生成部１１０により実行される。
【０１７１】
（有向グラフ生成部１１０）
まず、有向グラフ生成部１１０について説明する。有向グラフ生成部１１０は、仮有向グラフＩ’を構成する複数の有向枝の一部を置換して有向グラフＩを生成する。まず、有向グラフ生成部１１０は、仮有向グラフＩ’に含まれる有向パスのうち、それを構成する有向枝数が最大の有向パスを選択する。その有向パスを最長有向パスＬＰ（Ｌｏｎｇｅｓｔ  Ｐａｔｈ）と呼ぶことにする。そして、有向グラフ生成部１１０は、全ての有向パスの有向枝数が最長有向パスＬＰの有向枝数を超えないという条件の下で、仮有向グラフＩ’に含まれる有向パスを、より短い有向枝の組で構成される有向パスに置換する。
【０１７２】
（アルゴリズム）
ここで、図１１〜図１４を参照しながら、有向グラフＩを生成するアルゴリズムについて詳細に説明する。図１１は、有向グラフＩを生成する処理の全体的な流れを示した説明図である。図１２は、最長有向パスＬＰを抽出する処理の流れを示した説明図である。図１３は、最長有向パスＬＰ以外の有向パスの中から最長の有向パスＰＬＰ（Ｐａｒｔｉａｌｌｙ  Ｌｏｎｇｅｓｔ  Ｐａｔｈ）を抽出する処理の流れを示した説明図である。図１４は、仮有向グラフＩ’の有向パスをより短い有向枝の組で構成される有向パスに置換する処理を示した説明図である。
【０１７３】
図１１に示すように、まず、有向グラフＩ’を形成する有向パスの中から最長有向パスＬＰが抽出される（Ｓ１５０）。次いで、仮有向グラフＩ’の最長有向パスＬＰ以外の有向パスの中から最長の有向パスＰＬＰが抽出される（Ｓ１５２）。なお、各部分集合に対応する仮有向グラフＩ’について最長の有向パスＰＬＰが抽出されてもよい。次いで、仮有向グラフＩ’の有向パスを構成する所定の有向枝が、より短い有向枝に置換される（Ｓ１５４）。このとき、全ての有向パスの有向枝数が最長有向パスＬＰの有向枝数を超えないように有向枝が置換される。つまり、この置換処理を実行したとしても、ＡＩ０５方式又はＡ０６（Ｂ）方式よりも鍵生成に要する計算量の最悪値が増加しないようにする。
【０１７４】
以下、図１１に示した各ステップについて、より詳細に説明する。
【０１７５】
（Ｓ１５０の詳細）
まず、図１２を参照しながら、最長有向パスＬＰが抽出されるステップ（Ｓ１６０）について詳細に説明する。ここで、以下に示す２つの表記を導入する。
【０１７６】
・ＤＤＴ      ：  最長有向パスＬＰの有向枝数を示す。
・Ｊ（ａ，ｂ）：  長さｂの有向枝がａ本連続して存在することを示す。
【０１７７】
まず、ｔ＝ｎ１／ｋ−１とおく。次いで、仮有向グラフＩ’（１→ｎ）の座標点［１，１］から座標点［１，ｎ］までの有向パスＰ（［１，１］，［１，ｎ］）を考える。有向パスＰ（［１，１］，［１，ｎ］）は、Ｊ（ｔ，ｎ（ｋ−１）／ｋ），Ｊ（ｔ，ｎ（ｋ−２）／ｋ），・・・，Ｊ（ｔ，ｎ１／ｋ），Ｊ（ｔ，ｎ０／ｋ）と表現される。この有向パスを最長有向パスＬＰと呼ぶ。このとき、最長有向パスＬＰの有向枝数ＤＤＴは、ＤＤＴ＝ｋ＊（ｎ１／ｋ−１）となる。次いで、最長有向パスＬＰを構成する全ての有向枝に対してａｃｔｉｖｅマークを設定する。
【０１７８】
（Ｓ１５２の詳細）
次に、図１３を参照しながら、最長有向パスＬＰを含む仮有向グラフＩ’以外の全ての部分集合に対応する仮有向グラフＩ’について、最長の有向パスＰＬＰを抽出する処理（Ｓ１６２〜Ｓ１７６）について説明する。ここで、以下に示す２つの表記を導入する。
【０１７９】
・ＣＰ（Ｃｕｒｒｅｎｔ  Ｐａｔｈ）  ：  参照中の有向パス（現在パス）
・＃ＪＰ（ＣＰ）                    ：  現在パスの有向枝数
【０１８０】
まず、有向グラフＩ’の始点から終点への現在パスＣＰを決定する。このとき、現在パスが有向グラフＩ’（ａ→ｂ）に含まれる場合は、有向パスＰ（［ａ，ａ］，［ａ，ｂ］）を現在パスＣＰとし、有向グラフＩ’（ａ←ｂ）に含まれる場合は、有向パスＰ（［ｂ，ｂ］，［ｂ，ａ］）を現在パスＣＰとする（Ｓ１６２）。次いで、現在パスＣＰを構成する有向枝のうち、最長の有向枝を選択して、その長さをＪとする（Ｓ１６４）。次いで、Ｊ≦１か否かを判断する（Ｓ１６６）。
【０１８１】
Ｊ≦１である場合、現在パスＣＰを最長の有向パスＰＬＰと決定して、現在パスＣＰに含まれる全ての有向枝にａｃｔｉｖｅマークを設定する（Ｓ１７６）。Ｊ＞１である場合、＃ＪＰ（ＣＰ）＋ｔ≦ＤＤＴか否かを判断する（Ｓ１６８）。＃ＪＰ（ＣＰ）＋ｔ≦ＤＤＴでない場合、現在パスＣＰを有向パスＰＬＰと決定して、現在パスに含まれる全ての有向枝にａｃｔｉｖｅマークを設定する（Ｓ１７６）。＃ＪＰ（ＣＰ）＋ｔ≦ＤＤＴである場合、Ｊ＝ｎｊ／ｋとなる自然数ｊを算出する（Ｓ１７０）。
【０１８２】
次いで、現在パスＣＰに含まれる長さＪの有向枝の中で現在パスＣＰの始点から最も遠い有向枝を抽出する（Ｓ１７２）。ステップＳ１７２で抽出された有向枝の始点から伸びたｔ個の長さｎ（ｊ−１）／ｋの有向枝の直後にｎ（ｊ−１）／ｋの長さを有する１つの有向枝を追加し、ステップＳ１７２で抽出された有向枝を除去し（Ｓ１７４）、ステップＳ１６２に戻って上記の処理を繰り返す。
【０１８３】
なお、ステップＳ１６２〜ステップＳ１７４の間に生じるループ処理は、有向グラフＩ’の始点から終点への有向パスが全て長さ１の有向枝で構成されるか、又は、それ以上の有向枝の置換を実行することで、その有向パスを構成する有向枝数がＤＤＴを超えてしまう場合にループ処理を終了する。
【０１８４】
（Ｓ１５４の詳細）
次に、図１４を参照しながら、仮有向グラフＩ’に含まれる有向枝を短い有向枝に置換する処理（Ｓ１８０〜Ｓ２０２）について詳細に説明する。
【０１８５】
まず、グラフ中のａｃｔｉｖｅかつ、未実施（ｄｏｎｅマークが付いていない）有向枝のうち、最長の長さＪ’を持つ有向枝を抽出する。もし、最大の有向枝が複数存在する場合は、仮有向グラフＩ’の始点から最も遠い有向枝を選択する（Ｓ１８０）。ここで選択された有向枝をＷＪ（Ｗｏｒｋｉｎｇ  Ｊｕｍｐ）と呼ぶことにする。また、有向枝ＷＪの始点をＷＪＳ、終点をＷＪＥと呼ぶことにする。さらに、仮有向グラフＩ’の始点からＷＪＥまでの有向パスに含まれる有向枝数をＤと表記する。
【０１８６】
次いで、有向枝の長さＪ’がＪ’≦１であるか否かを判断する（Ｓ１８２）。Ｊ’≦１である場合、ａｃｔｉｖｅマークの付いていない有向枝を全て消去し、ａｃｔｉｖｅマークが付いている有向枝を全て集めたものをＥ（Ｉ（ａ→ｂ））又はＥ（Ｉ（ａ←ｂ））と設定する（Ｓ２０２）。逆に、Ｊ’≦１でない場合、ＷＪＳからＷＪＥ−１までの有向パスを現在パスＣＰと設定する（Ｓ１８４）。但し、ＷＪＥ−１は、ＷＪＥの１つ手前の要素を表す。
【０１８７】
次いで、現在パスＣＰに含まれる有向枝の中から最長の有向枝を抽出し、その長さをＪとする（Ｓ１８６）。次いで、有向枝の長さＪがＪ≦１か否かを判断する（Ｓ１８８）。Ｊ≦１である場合、現在パスＣＰに含まれる全ての有向枝にａｃｔｉｖｅマークを付ける（Ｓ１９８）。そして、ＷＪにｄｏｎｅマークを付け（Ｓ２００）、ステップＳ１８０の処理に戻る。逆に、Ｊ≦１でない場合、＃ＪＰ（ＣＰ）＋ｔ≦ＤＤＴ−Ｄであるか否かを判断する（Ｓ１９０）。＃ＪＰ（ＣＰ）＋ｔ≦ＤＤＴ−Ｄでない場合、ステップＳ１９８及びＳ２００の処理を経てステップＳ１８０の処理に戻る。＃ＪＰ（ＣＰ）＋ｔ≦ＤＤＴ−Ｄである場合、Ｊ＝ｎｊ／ｋを満たすｊを算出する（Ｓ１９２）。
【０１８８】
次いで、現在パスＣＰに含まれる長さＪの有向枝が複数存在する場合、現在パスＣＰの始点から最も遠い位置にある有向枝を抽出する（Ｓ１９４）。次いで、ステップＳ１９４で抽出された有向枝の始点から伸びたｎ１／ｋ−１個の長さｎ（ｊ−１）／ｋの有向枝の直後にｎ（ｊ−１）／ｋの長さを有する１つの有向枝を追加し、ステップＳ１９４で抽出された有向枝を消去する（Ｓ１９６）。そして、ステップＳ１８４の処理に戻る。
【０１８９】
但し、ステップＳ１８４〜Ｓ１９６の間に生じるループ処理は、ＷＪＳからＷＪＥ−１への有向パスが全て長さ１の有向枝で構成されるか、又は、それ以上の有向枝を置換することによってＷＪＳからＷＪＥ−１への有向パスに含まれる有向枝数がＤＤＴを超えてしまう場合に終了する。また、上記のステップＳ１８０〜Ｓ２００の間に生じるループ処理は、仮有向グラフＩ’に含まれる有向枝の中から、ｄｏｎｅが設定されておらず、かつ、長さが２以上の有向枝が全てなくなった時点で終了する。
【０１９０】
以上説明したアルゴリズムを仮有向グラフＩ’に適用することにより、図１５に示す有向グラフＩが生成される。この有向グラフＩは、契約者数ｎ＝６４、パラメータｋ＝６の場合について生成されたものである。この有向グラフＩを用いると、ＡＩ０５方式に比べ、各端末装置１２２が鍵生成に要する計算量と、各端末装置１２２が保持すべき鍵数を低減させることが可能になる。
【０１９１】
［鍵生成ブロック］
次に、再び図８を参照しながら、鍵生成ブロックの詳細について説明する。鍵生成ブロックは、主に、初期中間鍵設定部１１２と、鍵生成部１１４と、暗号化部１１６とにより構成される。
【０１９２】
（初期中間鍵設定部１１２）
初期中間鍵設定部１１２は、論理二分木に含まれる全ての中間ノード及び根ノードの有向グラフＩのルートに対応する中間鍵を生成する。例えば、初期中間鍵設定部１１２は、ＰＲＳＧにより擬似乱数を発生させて各ルートに対応する中間鍵を設定してもよいし、又は所定の数値により各ルートの中間鍵を設定してもよい。
【０１９３】
（鍵生成部１１４）
鍵生成部１１４は、ＰＲＳＧを利用して中間鍵又はセット鍵を生成する。このとき、鍵生成部１１４は、ＡＩ０５方式の有向グラフＨ、Ａ０６（Ａ＋Ｂ）方式の有向グラフＩ、Ａ０６（Ａ）方式の有向グラフ、Ａ０６（Ｂ）方式の有向グラフ、又はその他の方式の有向グラフに基づいて擬似乱数生成演算を実行することにより、所望の中間鍵又はセット鍵を生成することができる。上記の通り、ＰＲＳＧは、有向グラフを構成する有向枝の始端に対応する中間鍵を入力すると、その中間鍵に対応するセット鍵と、その有向枝の終端に対応する中間鍵とを出力する。有向グラフの水平座標軸上にある一つの座標点から複数の有向枝が伸びている場合には、その座標点に対応する中間鍵を入力すると、複数の中間鍵を導出することができる。
【０１９４】
なお、ＡＩ０５方式では、上式（２）でＰＲＳＧの入出力が定義されていたが、本実施形態においては、ｔ（Ｓ１）｜｜・・・｜｜ｔ（Ｓｋ）｜｜ｋ（Ｓ０）←ＰＲＳＧ（ｔ（Ｓ０））によりＰＲＳＧの入出力が定義される。即ち、ＡＩ０５方式によるＰＲＳＧの出力は、入力された中間鍵に対応する座標点を始点とする有向枝の数をｄとしたとき、λビットの入力に対して（ｄ＋１）λビットの出力を出すように構成されていた。これに対し、本実施形態に係るＰＲＳＧは、ｄの値に関わらず（ｋ＋１）λビットの出力を出すように構成される。但し、ｋはシステムパラメータである。
【０１９５】
本実施形態において、部分集合Ｓ０に対応する中間鍵ｔ（Ｓ０）がそのＰＲＳＧに入力された場合、その出力をｔ（Ｓ１）｜｜・・・｜｜ｔ（Ｓｋ）｜｜ｋ（Ｓ０）としている。その出力に含まれるｔ（Ｓ１）｜｜・・・｜｜ｔ（Ｓｋ）の部分は、部分集合Ｓ０に対応する座標点を始点とする有向枝の終点である座標点のそれぞれについて、対応する部分集合Ｓ１，・・・，Ｓｋの中間鍵である。また、部分集合Ｓ０に対応する座標点と部分集合Ｓｉに対応する座標点とを結ぶ有向枝の長さがｎ（i−１）／ｋとなる。例えば、部分集合Ｓ０に対応する座標点と部分集合Ｓｉに対応する座標点とを結ぶ有向枝の長さがｎ２／ｋであれば、ＰＲＳＧ（ｔ（Ｓ０））の出力の最初から３番目のλビットの部分がｔ（Ｓｉ）になる。もし、部分集合Ｓ０に対応する座標点から長さｎ（i−１）／ｋの有向枝が出ていない場合、ｔ（Ｓｉ）の部分がＰＲＳＧから出力されるけれども使用されない。
【０１９６】
例えば、鍵生成部１１４は、ＰＲＳＧに対し、有向グラフＩ上の座標点Ｓ０に対応する中間鍵ｔ（Ｓ０）を入力すると、座標点Ｓ０を始端とする複数の有向枝について、その終端の座標点Ｓ１，Ｓ２，・・・，Ｓｍに対応する中間鍵ｔ（Ｓ１），ｔ（Ｓ２），・・・，ｔ（Ｓｍ）と、セット鍵ｋ（Ｓ０）とを導出することができる。なお、ｍは座標点Ｓ０から伸びる有向枝の本数を表している。なお、中間鍵を利用しない場合は、例えば、セット鍵ｋ（Ｓ０）をＰＲＳＧに入力して、複数のセット鍵ｋ（Ｓ１），ｋ（Ｓ２），・・・，ｋ（Ｓｍ）を導出するように構成することも可能である。
【０１９７】
（暗号化部１１６）
暗号化部１１６は、セット鍵を用いてコンテンツ又はコンテンツ鍵を暗号化して暗号文を生成する。暗号化部１１６は、セットシステムＳＳを構成する全ての部分集合のうち、所定の部分集合に対応する１つ以上のセット鍵を用いてコンテンツ又はコンテンツ鍵を暗号化する。従って、一つのコンテンツ又はコンテンツ鍵に対して複数の暗号文が生成される場合もある。
【０１９８】
［情報生成ブロック］
次に、再び図８を参照しながら、情報生成ブロックの詳細について説明する。情報生成ブロックは、主に、部分集合決定部１２０と、経路情報生成部１２１とにより構成される。なお、通信部１１８についても併せて説明する。
【０１９９】
（部分集合決定部１２０）
部分集合決定部１２０は、コンテンツ又はコンテンツ鍵を暗号化するセット鍵を決定する。つまり、部分集合決定部１２０は、所定の許諾契約者の端末装置１２２が含まれる少なくとも１つの部分集合を抽出し、各端末装置１２２に配布されるセット鍵の種類を決定する。例えば、部分集合決定部１２０は、コンテンツ又はコンテンツ鍵の再生を許諾しない排除契約者の集合（Ｒ）、及び全契約者の集合（Ｎ）から排除ユーザの集合（Ｒ）を除外した許諾契約者の集合（Ｎ＼Ｒ）を決定する。つまり、セットシステムＳＳに含まれる部分集合により、許諾契約者の集合（Ｎ＼Ｒ＝Ｓ１∪Ｓ２∪・・・∪Ｓｍ）を構成する部分集合の組（Ｓ１，Ｓ２，・・・，Ｓｍ）を決定する。
【０２００】
（経路情報生成部１２１）
経路情報生成部１２１は、有向グラフに含まれる有向枝の情報を参照し、当該有向グラフの始点から所定の座標点に到達する有向パスの情報を抽出する。所定の座標点とは、部分集合決定部１２０により選択された各部分集合に対応する座標点である。なお、経路情報生成部１２１は、上記の鍵生成経路情報抽出部の一例である。
【０２０１】
既に説明した通り、上記のＡＩ０５方式等の鍵配信方式は、全ての端末装置１２２が有向グラフの情報を保持しているか、又は各端末装置１２２が各鍵配信方式のアルゴリズムに基づいて有向グラフを算出することを前提としている。しかし、この前提は、端末装置１２２のメモリ量を圧迫し、演算負荷を著しく増大させるため、現実的ではないという問題がある。
【０２０２】
例えば、ＡＩ０５方式の有向グラフＨ（図１６を参照）の場合、契約者３の端末装置１２２は、部分集合Ｓ０＝［１，４］に対応する中間鍵ｔ（Ｓ０）を予め保持している。仮に、部分集合決定部１２０が部分集合Ｓ＝［１，８］を選択し、これに対応するセット鍵ｋ（Ｓ）を用いてコンテンツ鍵を暗号化した場合を考えると、契約者３の端末装置１２２は、まず、中間鍵ｔ（Ｓ０）とＰＲＳＧとを利用して中間鍵ｔ（Ｓ）を導出する必要がある。しかし、これを導出するために、契約者３の端末装置１２２は、有向グラフＨ（１→６４）上に座標点Ｓ０＝［１，４］から座標点Ｓ１＝［１，８］に有向枝が存在するという情報（図１６の太線の一部）を保持している必要がある。
【０２０３】
しかし、下式（４）に示す通り、有向グラフＨ（１→ｎ）上には（ｎ−１）本の有向枝が存在するため、ｎが大きくなると全ての有向枝の情報を保持するのが困難になる。例えば、１本の有向枝の情報が８Ｂｙｔｅ程度の情報量で表現できると仮定すると、現実的な契約者数ｎがｎ＝２３２＝４，２９４，９６７，２９６であるから、有向グラフＨ（１→ｎ）の情報だけで約３２ＧＢｙｔｅもの記憶容量を必要とする。
【０２０４】
【数４】
2008236377.tif 000006
【０２０５】
そこで、本件出願人は、選択した部分集合（上記の例では［１，８］）の情報に加え、その有向グラフの始点から、その部分集合に対応する座標点に到達する有向パスの情報も端末装置１２２に配信する方式を考案したのである。例えば、上記の例と同様に、部分集合［１，８］が選択されると、有向グラフＨ（１→６４）の始点［１，１］から座標点［１，８］に到達する有向パス（図１６の太線）の情報が端末装置１２２に配信される。この特徴を実現させる構成が経路情報生成部１２１である。
【０２０６】
以下の説明において、コンテンツ鍵ｍｅｋをセット鍵ｋ（Ｓ０）で暗号化した暗号文をＣ（ｋ（Ｓ０）、ｍｅｋ）と表記する。また、部分集合Ｓｉ＝［ＳＰｉ、ＴＰｉ］のＳＰｉ、ＴＰｉ、Ｓｉは下記の意味を有する。
【０２０７】
（１）座標点Ｓｉが右向きの有向グラフに含まれる場合
ＳＰｉ：  部分集合Ｓｉの要素中で最も小さな番号
ＴＰｉ：  部分集合Ｓｉの要素中で最も大きな番号
⇒  Ｓｉ＝｛ＳＰｉ，ＳＰｉ＋１，・・・，ＴＰｉ｝
（２）座標点Ｓｉが左向きの有向グラフに含まれる場合
ＳＰｉ：  部分集合Ｓｉの要素中で最も大きな番号
ＴＰｉ：  部分集合Ｓｉの要素中で最も小さな番号
⇒  Ｓｉ＝｛ＳＰｉ，ＳＰｉ−１，・・・，ＴＰｉ｝
（３）ＳＰｉ＝ＴＰｉの場合
⇒  Ｓｉ＝｛ＳＰｉ｝
【０２０８】
なお、ＳＰｉとＴＰｉは１以上ｎ以下の値である。また、ＳＰｉは有向グラフの始点と交差する縦線の番号（契約者の番号）を表し、ＴＰｉは選択された部分集合の座標点と交差する縦線の番号（契約者の番号）を表す。
【０２０９】
まず、経路情報生成部１２１は、下式（５）に示すように、上記の部分集合Ｓｉに含まれる契約者の情報に対し、当該部分集合Ｓｉを導出するのに必要な有向パスの情報を生成して付加する。なお、本実施形態に係る経路情報生成部１２１は、有向パスの情報として、当該有向パスに含まれる各有向枝の終端を表す情報（交差する縦軸の番号ＩＰｉｊ；１≦ＩＰｉｊ≦ｎ）を付加する。但し、有向グラフ上の座標点［ＳＰｉ，ＳＰｉ］と座標点［ＳＰｉ，ＴＰｉ］とを結ぶ有向パスにｐ本（ｐ≦ＤＤＴ）の有向枝が存在するものとする。
【０２１０】
【数５】
2008236377.tif 000007
【０２１１】
（例１）
例えば、契約者数ｎ＝６４、パラメータｋ＝６のＡＩ０５方式において、部分集合決定部１２０が部分集合Ｓ＝［１，８］を選択した場合を考える。すると、経路情報生成部１２１は、有向パスの情報を含む部分集合Ｓの情報として、Ｓ＝（１，２，４，８）を生成する（図１６の太線（有向パス）を参照）。
【０２１２】
（例２）
他の例として、契約者数ｎ＝６４、パラメータｋ＝６のＡＩ０５方式において、契約者４５と契約者５５とが排除された場合を考える。このとき、部分集合決定部１２０が部分集合Ｓ１＝［１，４４］，Ｓ２＝［４８，４６］，Ｓ３＝［４９，５４］，Ｓ４＝［６４，５６］を選択したとすると、経路情報生成部１２１は、各部分集合に有向パスの情報を付加した下記の情報を生成する（図１７の太線（有向パス）を参照）。
Ｓ１＝（１，２，４，８，１６，３２，４０，４４）、
Ｓ２＝（４８，４７，４６）、
Ｓ３＝（４９，５０，５２，５４）、
Ｓ４＝（６４，６３，６１，５７，５６）。
【０２１３】
（例３）
他の例として、契約者数ｎ＝６４、パラメータｋ＝６のＡ０６（Ａ＋Ｂ）方式において、契約者４５と契約者５５とが排除された場合を考える。このとき、部分集合決定部１２０が部分集合Ｓ１＝［１，４４］，Ｓ２＝［４８，４６］，Ｓ３＝［４９，５４］，Ｓ４＝［６４，５６］を選択したとすると、経路情報生成部１２１は、各部分集合に有向パスの情報を付加した下記の情報を生成する（図１８の太線（有向パス）を参照）。
Ｓ１＝（１，３３，３７，４１，４２，４３，４４）、
Ｓ２＝（４８，４７，４６）、
Ｓ３＝（４９，５３，５４）、
Ｓ４＝（６４，６０，５６）。
【０２１４】
上記の通り、一つの部分集合について有向パスの情報がｐ＋１個の番号ＩＰｉｊにより表される。また、ｐ≦ＤＤＴであり、各番号ＩＰｉｊを表現するのにｌｏｇ（ｎ）ビットのメモリ領域を要することから、一つの部分集合を表すのに最大（ＤＤＴ＋１）＊ｌｏｇ（ｎ）ビットが必要であることが分かる。但し、ＤＤＴの値は採用する鍵配信方式毎に異なる。例えば、ＡＩ０５方式ではＤＤＴ＝（２ｋ−１）＊（ｎ１／ｋ−１）であり、Ａ０６（Ａ＋Ｂ）方式ではＤＤＴ＝ｋ（ｎ１／ｋ−１）である。
【０２１５】
（通信部１１８）
通信部１１８は、暗号化部１１６により暗号化されたコンテンツ又はコンテンツ鍵を葉ノードに対応する全ての端末装置１２２に対して配信する。また、通信部１１８は、有向グラフＩに基づいて所定の中間鍵を端末装置１２２に対して配信する。このとき、通信部１１８は、各端末装置１２２が、自身が含まれる部分集合に対応する中間鍵を全て導出できるように必要最低限の中間鍵を配信する。また、通信部１１８は、所定の有向グラフの情報を各端末装置１２２に対して配信する。さらに、通信部１１８は、許諾契約者の集合（Ｎ＼Ｒ）、又は許諾契約者の集合（Ｎ＼Ｒ＝Ｓ１∪Ｓ２∪・・・∪Ｓｍ）を構成する部分集合（Ｓ１，Ｓ２，・・・，Ｓｍ）の情報を各端末装置１２２に配信する。このとき、通信部１１８は、経路情報生成部１２１により付加された有向パスの情報も配信する。
【０２１６】
［端末装置１２２の構成］
次に、図１９を参照しながら、本実施形態に係る端末装置１２２の構成について説明する。図１９は、端末装置１２２の構成を示す説明図である。
【０２１７】
図１９を参照すると、端末装置１２２は、主に、通信部１２４と、判断部１２６と、鍵生成部１２８と、復号部１３０とにより構成される。なお、端末装置１２２は、上記のユーザに対応している。また、通信部１２４は、上記の鍵生成経路情報取得部、及び暗号情報取得部の一例である。そして、鍵生成部１２８は、上記の鍵情報生成部の一例である。さらに、復号部１３０は、上記の暗号情報復号部の一例である。
【０２１８】
（通信部１２４）
通信部１２４は、鍵配信サーバ１０２から配信された情報を受信する。例えば、通信部１２４は、鍵配信サーバ１０２から配信されたコンテンツ、コンテンツ鍵、中間鍵、有向グラフに関する情報、又は許諾契約者に関する情報等を受信する。また、通信部１２４は、有線又は無線のネットワークに接続された複数の情報源（例えば、鍵配信サーバ１０２）、又はネットワークを介さずに直接的又は間接的に接続された情報源（例えば、光ディスク装置、磁気ディスク装置、又は携帯型端末装置等の情報メディア）から情報を取得する構成であってもよい。
【０２１９】
（判断部１２６）
判断部１２６は、セット鍵に対応する部分集合のいずれかに自身が要素として含まれるか否かを判断する。判断部１２６は、鍵配信サーバ１０２の部分集合決定部１２０により選択された部分集合のいずれかに自身が含まれるか否かを判断する。このとき、判断部１２６は、鍵配信サーバ１０２から取得した上記部分集合の情報を参照する。
【０２２０】
（鍵生成部１２８）
鍵生成部１２８は、予め配信された中間鍵とＰＲＳＧとを利用して所望の中間鍵又はセット鍵を生成する。このとき、鍵生成部１２８は、鍵配信サーバ１０２から取得した有向パスの情報を参照し、当該情報に基づいて所望の中間鍵又はセット鍵を生成する。なお、判断部１２６により自身が含まれる部分集合が存在しないと判断された場合は、中間鍵又はセット鍵の生成処理を終了する。上記のＰＲＳＧは、鍵配信サーバ１０２が保持するＰＲＳＧと実質的に同一であり、所定の有向グラフに基づき、有向枝の始端に対応する中間鍵を入力すると、当該中間鍵に対応するセット鍵と、当該有向枝の終端に対応する中間鍵が出力される。もちろん、一つの座標点から複数の有向枝が伸びている場合は、当該座標点に対応する中間鍵を入力すると各有向枝の終端に対応する複数の中間鍵が得られる。
【０２２１】
（アルゴリズム）
ここで、図２０を参照しながら、契約者ｕの端末装置１２２による鍵導出アルゴリズムについて説明する。図２０は、契約者ｕの端末装置１２２が鍵を導出する処理を示した説明図である。なお、この処理は、主に、鍵生成部１２８により実行される。
【０２２２】
まず、契約者ｕの端末装置１２２には、鍵配信サーバ１０２の部分集合決定部１２０により選択されたｍ個の部分集合（Ｓ１，・・・，Ｓｍ）を表す情報と、経路情報生成部１２１により部分集合毎に付加された有向パスの情報Ｓｊ＝（ＳＰｊ，ＩＰｊ，１，・・・，ＩＰｊ，（ｐ−１），ＴＰｊ）（但し、ｊ＝１，・・・，ｍ）とが与えられている。また、判断部１２６により、自身が部分集合Ｓｉ＝［ＳＰｉ，ＴＰｉ］に含まれていると判断されたものと仮定する。従って、鍵生成部１２８は、所望の中間鍵又はセット鍵を生成する処理において、有向パスの情報Ｓｉ＝（ＳＰｉ，ＩＰｉ，１，・・・，ＩＰｉ，（ｐ−１），ＴＰｉ）を参照する。以下、図２０に示した流れ図に沿って具体的に説明する。
【０２２３】
図２０を参照すると、まず、変数ＩＰｉ，ｐにＴＰｉの値を設定する（Ｓ４０２）。次いで、カウンタｊを１に初期化する（Ｓ４０４）。次いで、契約者ｕの端末装置１２２が部分集合［ＳＰｉ，ＩＰｉ，ｊ］に含まれるか否かを判断する（Ｓ４０６）。含まれない場合、カウンタｊをインクリメントし（Ｓ４０８）、再びステップＳ４０６に戻る。逆に、含まれる場合、変数ｓｐにＳＰｉを設定し、変数ｅｐにＩＰｉ，ｊを設定する（Ｓ４１０）。このとき、契約者ｕの端末装置１２２は、部分集合［ｓｐ，ｅｐ］に対応する中間鍵ｔ（［ｓｐ，ｅｐ］）を予め保持している。
【０２２４】
次いで、中間鍵ｔ（［ｓｐ，ｅｐ］）を変数ｔｃｕｒｒｅｎｔに設定する（Ｓ４１２）。次いで、ｅｐ＝ＴＰｉか否かを判断する（Ｓ４１４）。ｅｐ＝ＴＰｉである場合、ｔｃｕｒｒｅｎｔをＰＲＳＧに入力し、その出力ＰＲＳＧ（ｔｃｕｒｒｅｎｔ）をλビット毎に区切ったｋ＋１番目の部分（部分集合［ＳＰｉ，ＴＰｉ］のセット鍵ｋ（［ＳＰｉ，ＴＰｉ］）に該当）を取り出し（Ｓ４２４）、セット鍵の生成処理を終了する。
【０２２５】
逆に、ｅｐ＝ＴＰｉでない場合、変数ｌｏｇｄ（下式（６）を参照）を計算する（Ｓ４１６）。即ち、ｌｏｇｄは、ＩＰｉ，ｊからＩＰｉ，ｊ＋１への有向枝の長さがｎ１／ｋの何乗であるかを示す数値である。次いで、カウンタｊをインクリメントし（Ｓ４１８）、ｅｐに対してＩＰｉ，ｊを設定する（Ｓ４２０）。次いで、ｔｃｕｒｒｅｎｔをＰＲＳＧに入力し、その出力ＰＲＳＧ（ｔｃｕｒｒｅｎｔ）をλビット毎に区切ったｌｏｇｄ＋１番目の部分を新たなｔｃｕｒｒｅｎｔに設定する（Ｓ４２２）。その後、ステップＳ４１４に戻る。
【０２２６】
【数６】
2008236377.tif 000008
【０２２７】
（復号部１３０）
復号部１３０は、鍵生成部１２８により生成されたセット鍵を用いてコンテンツ又はコンテンツ鍵を復号する。また、復号部１３０は、コンテンツ鍵を用いてコンテンツを復号する処理も実行可能である。
【０２２８】
以上、本実施形態に係る端末装置１２２の構成について説明した。上記の構成により、端末装置１２２は、鍵配信サーバ１０２から取得した有向パスの情報を利用して所望のセット鍵を生成することが可能になる。その結果、端末装置１２２は、膨大な有向グラフの情報を全て保持又は生成する必要がなくなり、メモリ量及び演算負荷を現実的なレベルまで抑制することが可能になる。
【０２２９】
＜第２実施形態＞
次に、本発明の第２実施形態に係る鍵提供システムの構成、及び鍵配信に係る具体的な方式について詳細に説明する。但し、上記の第１実施形態と実質的に同一の機能構成を有する構成要素については同一の符号を付することにより詳細な説明を省略する。
【０２３０】
上記の第１実施形態における鍵提供システム１００の特徴は、鍵配信サーバ１０２から端末装置１２２に対して提供される有向グラフの情報にあることは既に説明した。特に、有向グラフの情報として、所定の座標点に到達する有向パスに含まれる全ての有向枝の情報を端末装置１２２に提供する手段に特徴を有するものである。第１実施形態では、当該有向枝の情報として各有向枝の終端を表す情報を考えたが、所定の座標点に到達可能な経路を端末装置１２２が認識可能であれば必ずしもこれに限定されるものではない。
【０２３１】
そこで、第２実施形態では、鍵配信サーバ１０２が備える部分集合決定部１２０により選択された所定の部分集合Ｓｉ＝［ＳＰｉ，ＴＰｉ］に対応する座標点Ｓｉに対し、当該座標点Ｓｉに到達する有向パスの情報として、当該有向パスに含まれる各有向枝の長さを表す情報ＬＤｉ，ｊを端末装置１２２に提供する手段（経路情報生成部１２１）について説明する。
【０２３２】
なお、上記の各有向枝の長さＬＤｉｊは、ある有向グラフの座標点［ＳＰｉ，ＳＰｉ］から座標点［ＳＰｉ，ＴＰｉ］に到達する有向パス上のｊ番目に位置する有向枝の長さｌｅｎｉ，ｊに対して、下式（７）により表現される値である。つまり、各有向枝の長さは、ｎ１／ｋのＬＤｉ，ｊ乗として表現される（但し、０≦ＬＤｉ，ｊ＜ｋである）。
【０２３３】
【数７】
2008236377.tif 000009
【０２３４】
そこで、鍵配信サーバ１０２が備える経路情報生成部１２１は、各有向枝の長さを表す情報ＬＤｉ，ｊを用いて、上記の部分集合Ｓｉを下式（８）のように表現する。つまり、経路情報生成部１２１は、部分集合Ｓｉに関し、下式（８）で表現される有向パスの情報を生成する。もちろん、選択された全ての部分集合Ｓｉ（ｉ＝１，・・・，ｍ）について同様に有向パスの情報が生成される。
【０２３５】
【数８】
2008236377.tif 000010
【０２３６】
（例１）
例えば、契約者数ｎ＝６４、パラメータｋ＝６のＡＩ０５方式において、契約者４５と契約者５５とが排除された場合を考える。このとき、部分集合決定部１２０が部分集合Ｓ１＝［１，４４］，Ｓ２＝［４８，４６］，Ｓ３＝［４９，５４］，Ｓ４＝［６４，５６］を選択したとすると、第１実施形態に係る経路情報生成部１２１が生成する情報は下記のように表現される（図１７を参照）。
【０２３７】
（第１実施形態の場合）
Ｓ１＝（１，２，４，８，１６，３２，４０，４４）、
Ｓ２＝（４８，４７，４６）、
Ｓ３＝（４９，５０，５２，５４）、
Ｓ４＝（６４，６３，６１，５７，５６）。
【０２３８】
一方、上記の第１実施形態と同じ条件の下、第２実施形態に係る経路情報生成部１２１が有向枝の長さに基づいて生成する情報は下記のように表現される。
【０２３９】
（第２実施形態の場合）
Ｓ１＝（１，０，１，２，３，４，３，２）、
Ｓ２＝（４８，０，０）、
Ｓ３＝（４９，０，１，１）、
Ｓ４＝（６４，０，１，２，０）。
【０２４０】
（例２）
他の例として、契約者数ｎ＝６４、パラメータｋ＝６のＡ０６（Ａ＋Ｂ）方式において、契約者４５と契約者５５とが排除された場合を考える。このとき、部分集合決定部１２０が部分集合Ｓ１＝［１，４４］，Ｓ２＝［４８，４６］，Ｓ３＝［４９，５４］，Ｓ４＝［６４，５６］を選択したとすると、第１実施形態に係る経路情報生成部１２１が生成する情報は下記のように表現される（図１８を参照）。
【０２４１】
（第１実施形態の場合）
Ｓ１＝（１，３３，３７，４１，４２，４３，４４）、
Ｓ２＝（４８，４７，４６）、
Ｓ３＝（４９，５３，５４）、
Ｓ４＝（６４，６０，５６）。
【０２４２】
一方、上記の第１実施形態と同じ条件の下、第２実施形態に係る経路情報生成部１２１が有向枝の長さに基づいて生成する情報は下記のように表現される。
【０２４３】
（第２実施形態の場合）
Ｓ１＝（１，５，２，２，０，０，０）、
Ｓ２＝（４８，０，０）、
Ｓ３＝（４９，４，０）、
Ｓ４＝（６４，２，２）。
【０２４４】
上記の通り、第２実施形態を適用すると、一つの部分集合に関する有向パスの情報は、１つの始点情報ＳＰｉ（１≦ＳＰｉ≦ｎ）とｐ個の長さ情報ＩＰｉ，ｊ（０≦ＩＰｉ，ｊ≦ｋ−１）とにより表現される。また、ｐ≦ＤＤＴであり、各部分集合はｌｏｇ（ｎ）＋ＤＤＴ＊ｌｏｇ（ｋ）ビットのデータで表される。一方、上記の第１実施形態の場合は、一つの部分集合を表すのに（ＤＤＴ＋１）＊ｌｏｇ（ｎ）ビットが必要であった。また、ｋ｜ｌｏｇ（ｎ）であるから、ｌｏｇ（ｋ）≦ｌｏｇ（ｌｏｇ（ｎ））＜ｌｏｇ（ｎ）となり、ｌｏｇ（ｎ）＋ＤＤＴ＊ｌｏｇ（ｋ）＜（ＤＤＴ＋１）＊ｌｏｇ（ｎ）という関係が得られる。従って、第２実施形態を適用することにより、上記の第１実施形態を適用するよりも各部分集合Ｓｉを表現するための情報を低減させることができる。その結果、鍵配信サーバ１０２から端末装置１２２に対して提供される情報量を低減（通信量の削減又は記録媒体の容量を節約）することが可能になる。
【０２４５】
ところで、部分集合として、Ｓｉ＝［３，３］等の一人のユーザからなる部分集合が選択された場合に、それをどのように表現するかについて考える。この場合、上記の第１実施形態の方式ではＳｉ＝（３，３）と表現される。また、上記の第２実施形態の方式ではいくつかの表現方法が考えられるが、１つの表現方法としては、Ｓｉ＝（３）のようにただひとつの数値で表現する方法が考えられる。他の表現方法としては、特殊記号⊥を用いて、Ｓｉ＝（３，⊥）と表現することもできる。後者の方法を採用すると、ユーザ数が２以上の部分集合において２番目以降が必ず０以上の整数となるため、ユーザ数が１であることを認識することが可能になる。
【０２４６】
（アルゴリズム）
次に、図２１を参照しながら、第２実施形態に係る端末装置１２２により、上記の鍵配信サーバ１０２から取得した各部分集合の情報を利用して鍵が生成されるアルゴリズムについて説明する。図２１は、契約者ｕの端末装置１２２が鍵を導出する処理を示した説明図である。なお、この処理は、主に、端末装置１２２が備える鍵生成部１２８により実行される。
【０２４７】
まず、契約者ｕの端末装置１２２には、鍵配信サーバ１０２の部分集合決定部１２０により選択されたｍ個の部分集合（Ｓ１，・・・，Ｓｍ）を表す情報と、経路情報生成部１２１により部分集合毎に付加された有向パスの情報Ｓｊ＝（ＳＰｊ，ＬＤｊ，１，・・・，ＬＤｊ，ｐ−１，ＬＤｊ，ｐ）（但し、ｊ＝１，・・・，ｍ）とが与えられている。また、判断部１２６により、自身が部分集合Ｓｉ＝［ＳＰｉ，ＴＰｉ］に含まれていると判断されたものと仮定する。従って、鍵生成部１２８は、所望の中間鍵又はセット鍵を生成する処理において、有向パスの情報Ｓｉ＝（ＳＰｉ，ＬＤｉ，１，・・・，ＬＤｉ，ｐ−１，ＬＤｉ，ｐ）を参照する。以下、図２１に示した流れ図に沿って具体的に説明する。
【０２４８】
図２１を参照すると、まず、変数ＩＰｉ，０にＳＰｉの値を設定する（Ｓ４３２）。次いで、ＳＰｉの奇数／偶数を判断して、ＳＰｉが奇数であれば変数ｓｉｇｎに１を設定し、ＳＰｉが偶数であれば−１を設定する（Ｓ４３４）。次いで、カウンタｊを１からｐまで動かしながら、ＩＰｉ，ｊ（下式（９））を計算する（Ｓ４３６）。ここで、ｐは、部分集合Ｓ１の表現において、ＳＰｉに続く０以上の整数値の個数を示す。つまり、Ｓ１＝［３，３］等のようにＳ１＝（３）やＳ１＝（３，⊥）と表現されるユーザ数１の部分集合の場合、ｐ＝０となるためＳ４３６の処理が実行されない。次いで、カウンタｊを０に初期化する（Ｓ４３８）。
【０２４９】
【数９】
2008236377.tif 000011
【０２５０】
次いで、契約者ｕの端末装置１２２が部分集合［ＳＰｉ，ＩＰｉ，ｊ］に含まれるか否かを判断する（Ｓ４４０）。契約者ｕの端末装置１２２が部分集合［ＳＰｉ，ＩＰｉ，ｊ］に含まれない場合、カウンタｊをインクリメントして再びステップＳ４４０に戻る（Ｓ４４２）。逆に、契約者ｕの端末装置１２２が部分集合［ＳＰｉ，ＩＰｉ，ｊ］に含まれる場合、変数ｓｐにＳＰｉの値を設定し、さらに、変数ｅｐにＩＰｉ，ｊの値を設定する（Ｓ４４４）。次いで、契約者ｕの端末装置１２２が予め保持している中間鍵の中から中間鍵ｔ（［ｓｐ，ｅｐ］）を選択してｔｃｕｒｒｅｎｔに設定する（Ｓ４４６）。
【０２５１】
次いで、変数ｅｐがＩＰｉ，ｐか否かを判断する（Ｓ４４８）。ｅｐ＝ＩＰｉ，ｐである場合、ｔｃｕｒｒｅｎｔをＰＲＳＧに入力し、その出力ＰＲＳＧ（ｔｃｕｒｒｅｎｔ）をλビット毎に区切ったｋ＋１番目の部分（セット鍵ｋ（［ＳＰｉ，ＩＰｉ，ｐ］）に該当）を抽出し（Ｓ４５６）、セット鍵の生成処理を終了する。逆に、ｅｐ＝ＩＰｉ，ｐでない場合、カウンタｊをインクリメントする（Ｓ４５０）。次いで、変数ｅｐにＩＰｉ，ｊの値を設定する（Ｓ４５２）。次いで、ｔｃｕｒｒｅｎｔをＰＲＳＧに入力し、その出力ＰＲＳＧ（ｔｃｕｒｒｅｎｔ）をλビット毎に区切ったＬＤｉ，ｊ＋１番目の部分を抽出し、ｔｃｕｒｒｅｎｔに設定する（Ｓ４５４）。そして、ステップＳ４４８に戻る。
【０２５２】
以上説明したアルゴリズムを用いて所望の鍵を生成することができる。もちろん、本実施形態に係る鍵生成部１２８は、これに限定されるものではなく、鍵配信サーバ１０２から取得した有向パスの情報Ｓｉに含まれる各有向枝の長さを表す情報ＬＤｉ，ｊから、各有向枝の終端を表す情報ＩＰｉ，ｊを予め算出し、上記の第１実施形態と同様のアルゴリズムを用いて鍵を算出してもよい。
【０２５３】
［効果］
本発明の各実施形態に係る構成を適用することにより、ＡＩ０５方式等に代表されるブロードキャストエンクリプション方式において、鍵配信サーバ１０２により選択された各部分集合に対応するセット鍵を導出する際に、端末装置１２２が鍵生成に要する有向グラフの情報を予め保持しておく必要がなくなるため、端末装置１２２のメモリ量に対する負担が低減される。
【０２５４】
上記の第１実施形態では、端末装置１２２が鍵生成に要する有向パスの情報として、当該有向パスに含まれる全ての有向枝の終端を示す情報を付加して配信する構成とした。一方、上記の第２実施形態では、端末装置１２２が鍵生成に要する有向パスの情報として、当該有向パスに含まれる全ての有向枝の長さを示す情報を付加して配信する構成とした。上記の第２実施形態を採用すると、第１実施形態に比べて端末装置１２２に配信する情報量を低減することが可能になる。
【０２５５】
［鍵提供システム１００の応用例］
最後に、図２２及び図２３を参照しながら、上記の各実施形態に係る鍵提供システム１００の応用例について簡単に説明する。
【０２５６】
（応用例１）
まず、鍵提供システム１００の一応用例として、放送暗号化システム３００の構成について説明する。図２１は、放送衛星を用いた放送暗号化システム（Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｙｓｔｅｍ）３００の構成を示す説明図である。
【０２５７】
図２２を参照すると、放送暗号化システム３００は、主に、衛星放送局３０２と、管理センタ３０４と、放送衛星３０６と、住居３０８と、受信機３１０とにより構成される。ここで、放送暗号化システム３００は、放送チャンネルを介して暗号化されたデータ（暗号テキスト；Ｃｉｐｈｅｒｔｅｘｔ）を住居３０８に設置された受信機３１０に対して配信するシステムである。但し、放送チャンネルとは、例えば、衛星放送配信チャンネルである。また、暗号テキストとは、例えば、暗号鍵、音声データ、映像データ、又はテキストデータ等を含むコンテンツである。
【０２５８】
まず、衛星放送局３０２には、放送衛星３０６を介して暗号テキスト等のデータを送信する管理センタ（Ｂｒｏａｄｃａｓｔ  Ｔｒｕｓｔｅｄ  Ｃｅｎｔｅｒ）３０４が設置される。管理センタ３０４は、例えば、暗号化用の鍵を選択したり、データの暗号化、及びデータの配信制御を実行する。つまり、管理センタ３０４は、上記の各実施形態に係る鍵配信サーバ１０２の一例である。また、住居３０８に設置された受信機３１０は、上記の各実施形態に係る端末装置１２２の一例である。
【０２５９】
放送衛星３０６は、管理センタ３０４と各住居３０８に設置された受信機３１０との間を媒介し、当該受信機３１０に対して暗号テキスト等のデータを放送する。また、受信機３１０は、例えば、衛星放送受信機等であり、放送衛星３０６を介して放送されたデータを受信する。なお、図２２に示すように、放送暗号化システム３００には複数の受信機３１０が含まれていてもよく、その場合、管理センタ３０４は、複数の受信機３１０から成る受信機グループに対してデータを配信する。このとき、管理センタ３０４は、認証された受信機３１０のみがデータを復号できるように放送データを暗号化して配信する。
【０２６０】
以上、鍵提供システム１００の一応用例である放送暗号化システム３００について説明した。図２２では、衛星放送の例を挙げたが、放送暗号化システム３００は、例えば、ケーブルテレビジョンやコンピュータネットワーク等の他の放送チャンネルを利用した暗号化システムに対しても容易に応用することが可能である。
【０２６１】
（応用例２）
次に、鍵提供システム１００の他の応用例として、放送暗号化システム４００の構成について説明する。図２３は、記録媒体を用いた放送暗号化システム４００の構成を示す説明図である。
【０２６２】
図２３を参照すると、放送暗号化システム４００は、主に、媒体製造業者４０２と、管理センタ４０４と、記録媒体４０６と、配布仲介者４０８と、住居４１２と、受信機４１４とにより構成される。ここで、放送暗号化システム４００における放送チャンネルはデータが記録された記録媒体４０６である。
【０２６３】
まず、媒体製造業者４０２には、記録媒体４０６を利用し、配布仲介者４０８を介して暗号テキスト等のデータを住居４１２に提供する管理センタ４０４が設置されている。但し、管理センタ４０４は、記録媒体４０６に暗号テキスト等のデータを記録するだけであり、記録媒体４０６を用いて間接的に暗号テキスト等のデータを提供する。また、記録媒体４０６は、例えば、読出専用媒体（例えば、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等）、又は書換可能媒体（例えば、ＣＤ−ＲＷ、ＤＶＤ−ＲＷ等）等である。上記の応用例１と同様、管理センタ４０４は、上記の各実施形態に係る鍵配信サーバ１０２に相当する。但し、暗号テキスト等のデータを記録媒体に記録して提供する点で若干相違するが、本発明に係る鍵配信サーバは、この応用例のように、実施形態に応じて暗号テキスト等の情報を配信する手段を適宜変更することが可能である。
【０２６４】
媒体製造業者４０２は、例えば、小売店等の配布仲介者（Ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｏｕｔｌｅｔ）４０８に対して暗号テキスト等のデータが記録された記録媒体４０６を送付する。次いで、配布仲介者４０８は、媒体４０６を各住居４１２に対して提供する。例えば、配布仲介者４０８は、記録媒体４０６を各住居４１２に対応する個人に対して販売する。この個人は、記録媒体４０６を住居４１２に持ち帰り、受信機４１４を利用して記録媒体４０６に記録されたデータを再生する。この受信機４１４は、上記の各実施形態に係る端末装置１２２の一例であるが、暗号テキスト等のデータを記録媒体を介して取得する点で若干相違する。しかし、本発明に係る端末装置は、この応用例のように、実施形態に応じて暗号テキスト等の情報を取得する手段を適宜変更することが可能である。また、受信機４１４は、例えば、ＣＤプレーヤ、ＤＶＤプレーヤ、又はＤＶＤ−ＲＷドライブを備えたコンピュータ等であり、記録媒体４０６に記録されているデータを読み出して再生することが可能な装置により構成されうる。
【０２６５】
以上、鍵提供システム１００の一応用例である放送暗号化システム４００について説明した。図２３では、記録媒体４０６を介して暗号テキスト等のデータを契約者に提供する手段を例に挙げて説明した。このように、本発明に係る鍵配信サーバ及び端末装置は、実施形態に応じて、各種情報の配布手段に関する構成を変更することが可能である。
【０２６６】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【０２６７】
例えば、上記の論理二分木は、上から下に枝が広がる構造を有するものと仮定したが、必ずしもこれに限定されず、下から上、左から右、又は右から左に向けて枝が広がるように構成することも可能である。このような配置に関わる変更は、単純に論理二分木を回転して配置することにより実現されるため、当該変更に係るいずれの構成についても実質的に同一の技術的範囲に属するものと言える。また、仮有向グラフ、及び有向グラフを形成する水平座標軸を左右反転させる変更についても同様である。
【０２６８】
さて、上記の各実施形態に係る鍵配信サーバ１０２は、自身で有向グラフを生成する構成要素を含んでいるが、必ずしもこれに限定されない。例えば、本発明に係る鍵配信サーバ１０２は、所定の有向グラフに関する情報を取得する取得部を備えていてもよく、この場合、木構造設定部１０４、座標軸設定部１０６、仮有向グラフ生成部１０８、及び有向グラフ生成部１１０の一部又は全部を備えている必要はない。
【０２６９】
また、上記の各実施形態に係る鍵配信サーバ１０２は、コンテンツ、コンテンツ鍵、セット鍵、中間鍵、許諾契約者に対応する部分集合の情報、又は有向グラフの情報等を端末装置１２２に配信する通信部１１８を備えているが、上記の応用例２にも示した通り、これらの情報を提供するために常にネットワークを利用するとは限らない。例えば、鍵配信サーバ１０２は、通信部１１８に代えて、記録媒体に情報を記録するための記録部を備えていてもよい。その場合、端末装置１２２は、通信部１２４を備える代わりに、情報が記録された記録媒体を読み込むための読出部を備えていてもよい。
【図面の簡単な説明】
【０２７０】
【図１】本発明の第１及び第２実施形態に係る鍵提供システム１００の構成を示す説明図である。
【図２】同実施形態に係る鍵配信サーバ１０２及び端末装置１２２のハードウェア構成を示す説明図である。
【図３】同実施形態に係る論理二分木の構造を示す説明図である。
【図４】ＡＩ０５方式の有向グラフＨを示す説明図である。
【図５】ＡＩ０５方式に係る鍵配信処理の流れを示す説明図である。
【図６】ＡＩ０５方式に係る鍵配信処理の流れを示す説明図である。
【図７】同実施形態に係る暗号文の復号処理の流れを示す説明図である。
【図８】同実施形態に係る鍵配信サーバ１０２の機能構成を示す説明図である。
【図９】Ａ０６（Ａ＋Ｂ）方式に係る仮有向グラフＩ’を生成する処理の流れを示す説明図である。
【図１０】Ａ０６（Ａ＋Ｂ）方式の仮有向グラフＩ’を示す説明図である。
【図１１】Ａ０６（Ａ＋Ｂ）方式に係る有向グラフＩを生成する処理の流れを示す説明図である。
【図１２】Ａ０６（Ａ＋Ｂ）方式に係る有向グラフＩを生成する処理の流れを示す説明図である。
【図１３】Ａ０６（Ａ＋Ｂ）方式に係る有向グラフＩを生成する処理の流れを示す説明図である。
【図１４】Ａ０６（Ａ＋Ｂ）方式に係る有向グラフＩを生成する処理の流れを示す説明図である。
【図１５】Ａ０６（Ａ＋Ｂ）方式の有向グラフＩを示す説明図である。
【図１６】ＡＩ０５方式の有向グラフＨに同実施形態を適用する際に参照される有向パスの一例を示す説明図である。
【図１７】ＡＩ０５方式の有向グラフＨに同実施形態を適用する際に参照される有向パスの一例を示す説明図である。
【図１８】Ａ０６（Ａ＋Ｂ）方式の有向グラフＩに同実施形態を適用する際に参照される有向パスの一例を示す説明図である。
【図１９】同実施形態に係る端末装置１２２の機能構成を示す説明図である。
【図２０】本発明の第１実施形態に係る鍵生成処理の流れを示す説明図である。
【図２１】本発明の第２実施形態に係る鍵生成処理の流れを示す説明図である。
【図２２】本発明の第１及び第２実施形態の応用例である放送暗号化システム３００の構成を示す説明図である。
【図２３】本発明の第１及び第２実施形態の応用例である放送暗号化システム４００の構成を示す説明図である。
【符号の説明】
【０２７１】
１００    鍵提供システム
１０２    鍵配信サーバ
１０４    木構造設定部
１０６    座標軸設定部
１０８    仮有向グラフ生成部
１１０    有向グラフ生成部
１１２    初期中間鍵設定部
１１４    鍵生成部
１１６    暗号化部
１１８    通信部
１２０    部分集合決定部
１２１    経路情報生成部
１２２    端末装置
１２４    通信部
１２６    判断部
１２８    鍵生成部
１３０    復号部
２０２    コントローラ
２０４    演算ユニット
２０６    入出力インターフェース
２０８    セキュア記憶部
２１０    メイン記憶部
２１２    ネットワークインターフェース
２１６    メディアインターフェース
２１８    情報メディア
【図１】
2008236377.tif 000012
【図２】
2008236377.tif 000013
【図３】
2008236377.tif 000014
【図４】
2008236377.tif 000015
【図５】
2008236377.tif 000016
【図６】
2008236377.tif 000017
【図７】
2008236377.tif 000018
【図８】
2008236377.tif 000019
【図９】
2008236377.tif 000020
【図１０】
2008236377.tif 000021
【図１１】
2008236377.tif 000022
【図１２】
2008236377.tif 000023
【図１３】
2008236377.tif 000024
【図１４】
2008236377.tif 000025
【図１５】
2008236377.tif 000026
【図１６】
2008236377.tif 000027
【図１７】
2008236377.tif 000028
【図１８】
2008236377.tif 000029
【図１９】
2008236377.tif 000030
【図２０】
2008236377.tif 000031
【図２１】
2008236377.tif 000032
【図２２】
2008236377.tif 000033
【図２３】
2008236377.tif 000034