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