【手続補正書】
【提出日】平成21年10月23日(2009.10.23)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の有向枝により構成される有向グラフで、当該有向グラフを構成する最大長の有向枝のひとつの始点が、当該有向グラフの始点と一致する有向グラフを取得する有向グラフ取得部と；
前記有向グラフ取得部により取得された前記有向グラフに基づいてコンテンツ又はコンテンツ鍵を暗号化又は復号するためのセット鍵を生成する鍵生成部と；
を備える、情報処理装置。
【請求項２】
前記鍵生成部は、
前記有向グラフにおけるある座標点に対応する部分集合Ｓの中間鍵ｔ（Ｓ）の入力に応じて、当該座標点に対応する部分集合Ｓに対応する前記セット鍵ｋ（Ｓ）と、当該座標点Ｓを始点とする前記有向枝の終点の座標点Ｓ１，Ｓ２，・・・，Ｓｋの中間鍵ｔ（Ｓ１），ｔ（Ｓ２），・・・，ｔ（Ｓｋ）と、を出力する、請求項１に記載の情報処理装置。
【請求項３】
前記鍵生成部は、
前記有向グラフにおけるある座標点に対応する部分集合Ｓのセット鍵ｋ（Ｓ）の入力に応じて、当該座標点Ｓを始点とする前記有向枝の終点の座標点Ｓ１，Ｓ２，・・・，Ｓｋのセット鍵ｋ（Ｓ１），ｋ（Ｓ２），・・・，ｋ（Ｓｋ）を出力する、請求項１に記載の情報処理装置。
【請求項４】
さらに、前記セット鍵を用いてコンテンツ又はコンテンツ鍵を暗号化する暗号化部を備える、請求項２又は３に記載の情報処理装置。
【請求項５】
所定の２分木構造を構成する葉ノード１〜ｎ（ｎは自然数）の一部又は全部にそれぞれ対応付けられた端末装置に対し、前記暗号化部により暗号化された前記コンテンツ又は前記コンテンツ鍵を送信する送信部をさらに備える、請求項４に記載の情報処理装置。
【請求項６】
前記葉ノード１〜ｎの部分集合をＳｉと定義して、前記セット鍵又は前記コンテンツ鍵で暗号化された前記コンテンツの復号を許可する前記端末装置の集合（Ｎ＼Ｒ）を決定し、前記集合（Ｎ＼Ｒ）＝Ｓ１∪Ｓ２∪・・・∪Ｓｍを満たすｍ個の部分集合Ｓ１〜Ｓｍを決定する部分集合決定部をさらに備える、請求項５に記載の情報処理装置。
【請求項７】
前記部分集合決定部は、
前記ｍが最小となるように、前記部分集合Ｓ１〜Ｓｍを決定する、請求項６に記載の情報処理装置。
【請求項８】
前記送信部は、
前記集合（Ｎ＼Ｒ）を表す情報、又は、前記集合（Ｎ＼Ｒ）を構成する前記部分集合Ｓ１〜Ｓｍを表す情報を、前記端末装置に送信する、請求項７に記載の情報処理装置。
【請求項９】
さらに、前記セット鍵を用いてコンテンツ又はコンテンツ鍵を復号する復号部を備える、請求項１に記載の情報処理装置。
【請求項１０】
所定の２分木構造を構成する葉ノード１〜ｎ（ｎは自然数）の１つ以上に対応付けられ，前記セット鍵を用いて暗号化されたコンテンツ又はコンテンツ鍵を受信する受信部をさらに備える、請求項９に記載の情報処理装置。
【請求項１１】
前記受信部が受信する前記暗号化されたコンテンツ又はコンテンツ鍵は，前記葉ノード１〜ｎの部分集合として定義された集合Ｓｉの中で，自身に対応付けられた前記葉ノードを含む集合Ｓの要素である前記葉ノードに対応付けられた１つ以上の情報処理装置が復号可能である、請求項１０に記載の情報処理装置。
【請求項１２】
複数の有向枝により構成される仮有向グラフに対し、当該仮有向グラフを構成する前記複数の有向枝の中から、より長い前記有向枝を残すことにより生成された有向グラフを取得する有向グラフ取得部と；
前記有向グラフ取得部により取得された前記有向グラフに基づいてコンテンツ又はコンテンツ鍵を暗号化又は復号するためのセット鍵を生成する鍵生成部と；
を備える、情報処理装置。
【請求項１３】
番号１〜ｎ（ｎは自然数）が対応付けられたｎ個の葉ノードと、根ノードと、前記根ノード及び前記葉ノード以外の複数の中間ノードと、から構成される２分木構造に対し、ある中間ノードｖ又は根ノードｖの下位に配置された複数の前記葉ノードの中で左端に位置する前記葉ノードの番号がｌｖ、そして右端に位置する前記葉ノードの番号がｒｖと定義されており，
さらに，自然数ｉ及びｊ（ｉ≦ｊ）に対して，集合（ｉ→ｊ）が｛｛ｉ｝，｛ｉ，ｉ＋１｝，．．．，｛ｉ，ｉ＋１，．．．，ｊ−１，ｊ｝｝と表記され、集合（ｉ←ｊ）が｛｛ｊ｝，｛ｊ，ｊ−１｝，．．．，｛ｊ，ｊ−１，．．．，ｉ＋１，ｉ｝｝と表記されるものと仮定されており，
集合（１→ｎ）に含まれる各部分集合に対応付けられた座標点が水平座標軸上に左から右に向かって包含関係が大きくなるように配列され、前記根ノードに対応付けられた第１水平座標軸が設定され，
また，集合（２←ｎ）に含まれる各部分集合に対応付けられた座標点が水平座標軸上に右から左に向かって包含関係が大きくなるように配列され、前記根ノードに対応付けられた第２水平座標軸が設定されており，
さらに，前記中間ノードの各々について、
集合（ｌｖ→ｒｖ−１）に含まれる各部分集合に対応付けられた座標点が水平座標軸上に左から右に向かって包含関係が大きくなるように配列され、ある中間ノードｖに対応づけられた第３水平座標軸が設定され、
また，集合（ｌｖ＋１←ｒｖ）に含まれる各部分集合に対応付けられた座標点が水平座標軸上に右から左に向かって包含関係が大きくなるように配列され、ある中間ノードｖに対応付けられた第４水平座標軸が設定された上で、
所定の整数ｋに対し，ｎ（ｘ−１）／ｋ＜（ｒｖ−ｌｖ＋１）≦ｎｘ／ｋを満たす自然数ｘに応じて長さｎｉ／ｋ（ｉ＝０，１，．．．ｘ−１）を有する複数の有向枝を前記第１〜４水平座標軸上に配置して形成された仮有向グラフを処理する情報処理装置であって、
前記仮有向グラフを取得する仮有向グラフ取得部と；
前記仮有向グラフ取得部により取得された前記仮有向グラフを構成する複数の有向枝の中から、より長い前記有向枝を残して有向グラフを生成する有向グラフ生成部と；
前記有向グラフに基づいてコンテンツ又はコンテンツ鍵を暗号化するためのセット鍵を生成する鍵生成部と；
を備える、情報処理装置。
【請求項１４】
番号１〜ｎ（ｎは自然数）が対応付けられたｎ個の葉ノードと、根ノードと、前記根ノード及び前記葉ノード以外の複数の中間ノードと、から構成される２分木構造を設定し、自然数ｉ及びｊ（ｉ≦ｊ）に関して、集合（ｉ→ｊ）を｛｛ｉ｝，｛ｉ，ｉ＋１｝，．．．，｛ｉ，ｉ＋１，．．．，ｊ−１，ｊ｝｝、集合（ｉ←ｊ）を｛｛ｊ｝，｛ｊ，ｊ−１｝，．．．，｛ｊ，ｊ−１，．．．，ｉ＋１，ｉ｝｝と定義して、ある中間ノードｖ又は根ノードｖの下位に配置された複数の前記葉ノードのうち、左端に位置する前記葉ノードの番号をｌｖ、右端に位置する前記葉ノードの番号をｒｖと設定する木構造設定部と；
集合（１→ｎ）に含まれる各部分集合に対応付けられた座標点が、水平座標軸上に左から右に向かって包含関係が大きくなるように配列された、前記根ノードに対応する第１水平座標軸と、
集合（２←ｎ）に含まれる各部分集合に対応付けられた座標点が、水平座標軸上に右から左に向かって包含関係が大きくなるように配列された、前記根ノードに対応する第２水平座標軸と、
前記中間ノードの各々について、
集合（ｌｖ→ｒｖ−１）に含まれる各部分集合に対応付けられた座標点が、水平座標軸上に左から右に向かって包含関係が大きくなるように配列された、ある中間ノードｖに対応する第３水平座標軸と、
集合（ｌｖ＋１←ｒｖ）に含まれる各部分集合に対応付けられた座標点が、水平座標軸上に右から左に向かって包含関係が大きくなるように配列された、ある中間ノードｖに対応する第４水平座標軸と、を設定し、
前記第３水平座標軸上の右端に位置する座標点の右側と、前記第２及び第４水平座標軸上の左端に位置する座標点の左側と、にそれぞれ２個の仮座標点を配置し、
前記第１水平座標軸上の右端に位置する座標点を第１の仮座標点として設定し、当該第１の仮座標点の右側に第２の仮座標点を配置する座標軸設定部と；
所定の整数ｋを設定し、
ｎ（ｘ−１）／ｋ＜（ｒｖ−ｌｖ＋１）≦ｎｘ／ｋを満たす整数ｘを算定した上で、
整数ｉ＝０〜ｘ−１の各々について、
ｎｉ／ｋの長さを有する右方向を向いた一又は複数の有向枝を連結して前記第１及び第３水平座標軸上の最左にある座標点を始点とする有向パスを形成し、
ｎｉ／ｋの長さを有する左方向を向いた一又は複数の有向枝を連結して前記第２及び第４水平座標軸上の最右にある座標点を始点とする有向パスを形成し、
前記第１〜４水平座標軸の各々について、前記各仮座標点を始点又は終点とする全ての前記有向枝を除外し、
前記第１〜４水平座標軸上の各座標点に到達する前記有向枝のうち、最長の有向枝以外の有向枝を除外することにより、
集合（１→ｎ−１）、集合（２←ｎ）、集合（ｌｖ＋１←ｒｖ）、集合（ｌｖ→ｒｖ−１）に関する有向グラフをそれぞれ生成し、
前記集合（１→ｎ−１）に関する有向グラフに対し、前記第１水平座標軸上にある前記第１の仮座標点を終点とする長さ１の有向枝を追加して、集合（１→ｎ）に関する有向グラフを生成する有向グラフ生成部と；
を備える、情報処理装置。
【請求項１５】
前記有向グラフに基づいて、コンテンツ又はコンテンツ鍵を暗号化するためのセット鍵を生成する鍵生成部を備え、
前記鍵生成部は、
前記有向グラフにおけるある座標点に対応する部分集合Ｓの中間鍵ｔ（Ｓ）の入力に応じて、当該座標点に対応する部分集合Ｓに対応する前記セット鍵ｋ（Ｓ）と、当該座標点Ｓを始点とする前記有向枝の終点の座標点Ｓ１，Ｓ２，・・・，Ｓｋの中間鍵ｔ（Ｓ１），ｔ（Ｓ２），・・・，ｔ（Ｓｋ）と、を出力する、請求項１４に記載の情報処理装置。
【請求項１６】
前記有向グラフに基づいて、コンテンツ又はコンテンツ鍵を暗号化するためのセット鍵を生成する鍵生成部を備え、
前記鍵生成部は、
前記有向グラフにおけるある座標点に対応する部分集合Ｓのセット鍵ｋ（Ｓ）の入力に応じて、当該座標点Ｓを始点とする前記有向枝の終点の座標点Ｓ１，Ｓ２，・・・，Ｓｋのセット鍵ｋ（Ｓ１），ｋ（Ｓ２），・・・，ｋ（Ｓｋ）を出力する、請求項１４に記載の情報処理装置。
【請求項１７】
有向グラフに基づいて、コンテンツ又はコンテンツ鍵を復号するためのセット鍵を生成する鍵生成部を備え、
前記有向グラフは、
番号１〜ｎ（ｎは自然数）が対応付けられたｎ個の葉ノードと、根ノードと、前記根ノード及び前記葉ノード以外の複数の中間ノードと、から構成される２分木構造を設定し、自然数ｉ及びｊ（ｉ≦ｊ）に関して、集合（ｉ→ｊ）を｛｛ｉ｝，｛ｉ，ｉ＋１｝，．．．，｛ｉ，ｉ＋１，．．．，ｊ−１，ｊ｝｝、集合（ｉ←ｊ）を｛｛ｊ｝，｛ｊ，ｊ−１｝，．．．，｛ｊ，ｊ−１，．．．，ｉ＋１，ｉ｝｝と定義して、ある中間ノードｖ又は根ノードｖの下位に配置された複数の前記葉ノードのうち、左端に位置する前記葉ノードの番号をｌｖ、右端に位置する前記葉ノードの番号をｒｖと設定し、
集合（１→ｎ）に含まれる各部分集合に対応付けられた座標点が、水平座標軸上に左から右に向かって包含関係が大きくなるように配列された、前記根ノードに対応する第１水平座標軸と、
集合（２←ｎ）に含まれる各部分集合に対応付けられた座標点が、水平座標軸上に右から左に向かって包含関係が大きくなるように配列された、前記根ノードに対応する第２水平座標軸と、
前記中間ノードの各々について、
集合（ｌｖ→ｒｖ−１）に含まれる各部分集合に対応付けられた座標点が、水平座標軸上に左から右に向かって包含関係が大きくなるように配列された、ある中間ノードｖに対応する第３水平座標軸と、
集合（ｌｖ＋１←ｒｖ）に含まれる各部分集合に対応付けられた座標点が、水平座標軸上に右から左に向かって包含関係が大きくなるように配列された、ある中間ノードｖに対応する第４水平座標軸と、を設定し、
前記第３水平座標軸上の右端に位置する座標点の右側と、前記第２及び第４水平座標軸上の左端に位置する座標点の左側と、にそれぞれ２個の仮座標点を配置し、
前記第１水平座標軸上の右端に位置する座標点を第１の仮座標点として設定し、当該第１の仮座標点の右側に第２の仮座標点を配置し、
所定の整数ｋを設定し、
ｎ（ｘ−１）／ｋ＜（ｒｖ−ｌｖ＋１）≦ｎｘ／ｋを満たす整数ｘを算定した上で、
整数ｉ＝０〜ｘ−１の各々について、
ｎｉ／ｋの長さを有する右方向を向いた一又は複数の有向枝を連結して前記第１及び第３水平座標軸上の最左にある座標点を始点とする有向パスを形成し、
ｎｉ／ｋの長さを有する左方向を向いた一又は複数の有向枝を連結して前記第２及び第４水平座標軸上の最右にある座標点を始点とする有向パスを形成し、
前記第１〜４水平座標軸の各々について、前記各仮座標点を始点又は終点とする全ての前記有向枝を除外し、
前記第１〜４水平座標軸上の各座標点に到達する前記有向枝のうち、最長の有向枝以外の有向枝を除外することにより、
集合（１→ｎ−１）、集合（２←ｎ）、集合（ｌｖ＋１←ｒｖ）、集合（ｌｖ→ｒｖ−１）に関する有向グラフをそれぞれ生成し、
前記集合（１→ｎ−１）に関する有向グラフに対し、前記第１水平座標軸上にある前記第１の仮座標点を終点とする長さ１の有向枝を追加して、集合（１→ｎ）に関する有向グラフを生成することにより得られる、端末装置。
【請求項１８】
複数の有向枝により構成される仮有向グラフに対し、当該仮有向グラフを構成する前記複数の有向枝の中から、より長い前記有向枝を残すことにより生成された有向グラフを取得する有向グラフ取得ステップと；
前記有向グラフ取得部により取得された前記有向グラフに基づいてコンテンツ又はコンテンツ鍵を暗号化又は復号するためのセット鍵を生成する鍵生成ステップと；
を含む、情報処理方法。
【請求項１９】
番号１〜ｎ（ｎは自然数）が対応付けられたｎ個の葉ノードと、根ノードと、前記根ノード及び前記葉ノード以外の複数の中間ノードと、から構成される２分木構造に対し、ある中間ノードｖ又は根ノードｖの下位に配置された複数の前記葉ノードの中で左端に位置する前記葉ノードの番号がｌｖ、そして右端に位置する前記葉ノードの番号がｒｖと定義されており，
さらに，自然数ｉ及びｊ（ｉ≦ｊ）に対して，集合（ｉ→ｊ）が｛｛ｉ｝，｛ｉ，ｉ＋１｝，．．．，｛ｉ，ｉ＋１，．．．，ｊ−１，ｊ｝｝と表記され、集合（ｉ←ｊ）が｛｛ｊ｝，｛ｊ，ｊ−１｝，．．．，｛ｊ，ｊ−１，．．．，ｉ＋１，ｉ｝｝と表記されるものと仮定されており，
集合（１→ｎ）に含まれる各部分集合に対応付けられた座標点が水平座標軸上に左から右に向かって包含関係が大きくなるように配列され、前記根ノードに対応付けられた第１水平座標軸が設定され，
また，集合（２←ｎ）に含まれる各部分集合に対応付けられた座標点が水平座標軸上に右から左に向かって包含関係が大きくなるように配列され、前記根ノードに対応付けられた第２水平座標軸が設定されており，
さらに，前記中間ノードの各々について、
集合（ｌｖ→ｒｖ−１）に含まれる各部分集合に対応付けられた座標点が水平座標軸上に左から右に向かって包含関係が大きくなるように配列され、ある中間ノードｖに対応づけられた第３水平座標軸が設定され、
また，集合（ｌｖ＋１←ｒｖ）に含まれる各部分集合に対応付けられた座標点が水平座標軸上に右から左に向かって包含関係が大きくなるように配列され、ある中間ノードｖに対応付けられた第４水平座標軸が設定された上で、
所定の整数ｋに対し，ｎ（ｘ−１）／ｋ＜（ｒｖ−ｌｖ＋１）≦ｎｘ／ｋを満たす自然数ｘに応じて長さｎｉ／ｋ（ｉ＝０，１，．．．ｘ−１）を有する複数の有向枝を前記第１〜４水平座標軸上に配置して形成された仮有向グラフを処理する情報処理方法であって、
前記仮有向グラフを取得する仮有向グラフ取得ステップと；
前記仮有向グラフ取得部により取得された前記仮有向グラフを構成する複数の有向枝の中から、より長い前記有向枝を残して有向グラフを生成する有向グラフ生成ステップと；
前記有向グラフに基づいてコンテンツ又はコンテンツ鍵を暗号化するためのセット鍵を生成する鍵生成ステップと；
を含む、情報処理方法。
【請求項２０】
番号１〜ｎ（ｎは自然数）が対応付けられたｎ個の葉ノードと、根ノードと、前記根ノード及び前記葉ノード以外の複数の中間ノードと、から構成される２分木構造を設定し、自然数ｉ及びｊ（ｉ≦ｊ）に関して、集合（ｉ→ｊ）を｛｛ｉ｝，｛ｉ，ｉ＋１｝，．．．，｛ｉ，ｉ＋１，．．．，ｊ−１，ｊ｝｝、集合（ｉ←ｊ）を｛｛ｊ｝，｛ｊ，ｊ−１｝，．．．，｛ｊ，ｊ−１，．．．，ｉ＋１，ｉ｝｝と定義して、ある中間ノードｖ又は根ノードｖの下位に配置された複数の前記葉ノードのうち、左端に位置する前記葉ノードの番号をｌｖ、右端に位置する前記葉ノードの番号をｒｖと設定する木構造設定ステップと；
集合（１→ｎ）に含まれる各部分集合に対応付けられた座標点が、水平座標軸上に左から右に向かって包含関係が大きくなるように配列された、前記根ノードに対応する第１水平座標軸と、
集合（２←ｎ）に含まれる各部分集合に対応付けられた座標点が、水平座標軸上に右から左に向かって包含関係が大きくなるように配列された、前記根ノードに対応する第２水平座標軸と、
前記中間ノードの各々について、
集合（ｌｖ→ｒｖ−１）に含まれる各部分集合に対応付けられた座標点が、水平座標軸上に左から右に向かって包含関係が大きくなるように配列された、ある中間ノードｖに対応する第３水平座標軸と、
集合（ｌｖ＋１←ｒｖ）に含まれる各部分集合に対応付けられた座標点が、水平座標軸上に右から左に向かって包含関係が大きくなるように配列された、ある中間ノードｖに対応する第４水平座標軸と、を設定し、
前記第３水平座標軸上の右端に位置する座標点の右側と、前記第２及び第４水平座標軸上の左端に位置する座標点の左側と、にそれぞれ２個の仮座標点を配置し、
前記第１水平座標軸上の右端に位置する座標点を第１の仮座標点として設定し、当該第１の仮座標点の右側に第２の仮座標点を配置する座標軸設定ステップと；
所定の整数ｋを設定し、
ｎ（ｘ−１）／ｋ＜（ｒｖ−ｌｖ＋１）≦ｎｘ／ｋを満たす整数ｘを算定した上で、
整数ｉ＝０〜ｘ−１の各々について、
ｎｉ／ｋの長さを有する右方向を向いた一又は複数の有向枝を連結して前記第１及び第３水平座標軸上の最左にある座標点を始点とする有向パスを形成し、
ｎｉ／ｋの長さを有する左方向を向いた一又は複数の有向枝を連結して前記第２及び第４水平座標軸上の最右にある座標点を始点とする有向パスを形成し、
前記第１〜４水平座標軸の各々について、前記各仮座標点を始点又は終点とする全ての前記有向枝を除外し、
前記第１〜４水平座標軸上の各座標点に到達する前記有向枝のうち、最長の有向枝以外の有向枝を除外することにより、
集合（１→ｎ−１）、集合（２←ｎ）、集合（ｌｖ＋１←ｒｖ）、集合（ｌｖ→ｒｖ−１）に関する有向グラフをそれぞれ生成し、
前記集合（１→ｎ−１）に関する有向グラフに対し、前記第１水平座標軸上にある前記第１の仮座標点を終点とする長さ１の有向枝を追加して、集合（１→ｎ）に関する有向グラフを生成する有向グラフ生成ステップと；
を含む、情報処理方法。