【手続補正書】
【提出日】平成21年10月15日(2009.10.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ｎ個の葉ノードと、根ノードと、前記根ノード及び前記葉ノード以外の複数の中間ノードとから構成される２分木の全体木構造を設定し、前記全体木構造を、ｎ１／ｙ個の葉ノードを有する複数の基本部分木に分割してｙ階層（ｙはｌｏｇ（ｎ）の約数）に階層化し、下位階層の前記基本部分木の根ノードが上位階層の前記基本部分木の葉ノードとなるように構成し、
前記全体木構造のノードｗの下位に位置する葉ノードの集合をＡｗと定義し、
前記基本部分木の葉ノードのうち、ある葉ノードｖよりもｉ個左に位置する葉ノードをｖ（−ｉ）、ｉ個右に位置する葉ノードをｖ（＋ｉ）と定義し、
前記基本部分木の２つの葉ノードｕ，ｖ（ｖはｕの右にある）に関し、集合（ｕ→ｖ）を｛Ａｕ，Ａｕ∪Ａｕ（＋１），・・・，Ａｕ∪・・・∪Ａｖ｝、集合（ｕ←ｖ）を｛Ａｖ，Ａｖ∪Ａｖ（−１），・・・，Ａｖ∪・・・∪Ａｕ｝と定義し、
前記基本部分木のノードｖの下位に位置する複数の葉ノードのうち、左端に位置する葉ノードをｌｖ’、右端に位置する葉ノードをｒｖ’と定義したときに、
最上位階層の前記基本部分木の根ノードｒｏｏｔに対して、集合（ｌroot’→ｒroot’）及び集合（ｌroot’（＋１）←ｒroot’）を対応付け、
前記最上位階層以外の階層の前記基本部分木の根ノードｖに対して、集合（ｌｖ’→ｒｖ’（−１））及び集合（ｌｖ’（＋１）←ｒｖ’）を対応付け、
前記各基本部分木の中間ノードｖが、その親ノードの左側に位置する場合には、当該中間ノードｖに対して集合（ｌｖ’（＋１）←ｒｖ’）を対応付け、
前記各基本部分木の中間ノードｖが、その親ノードの右側に位置する場合には、当該中間ノードｖに対して集合（ｌｖ’→ｒｖ’（−１））を対応付ける木構造設定部と；
前記各基本部分木の根ノード及び中間ノードｖの各々について、前記集合（ｌroot’→ｒroot’）又は前記集合（ｌｖ’→ｒｖ’（−１））に含まれる各部分集合に対応する座標点が、水平座標軸上に左から右に向かって包含関係が大きくなるように配列され、当該座標点を相互に結ぶ有向枝が設定された有向グラフ、及び／又は、前記集合（ｌroot’（＋１）←ｒroot’）又は前記集合（ｌｖ’（＋１）←ｒｖ’）に含まれる各部分集合に対応する座標点が、水平座標軸上に右から左に向かって包含関係が大きくなるように配列され、当該座標点を相互に結ぶ有向枝が設定された有向グラフを生成する有向グラフ生成部と；
を備える、情報処理装置。
【請求項２】
前記有向グラフ生成部は、
前記下位階層の基本部分木に対応する前記有向グラフから、前記上位階層の基本部分木に対応する前記有向グラフへの有向枝を設定する部分木間有向枝設定部をさらに備える、請求項１に記載の情報処理装置。
【請求項３】
前記部分木間有向枝設定部は、
前記下位階層の基本部分木に対応する前記有向グラフにおける第１座標点から、前記上位階層の基本部分木に対応する前記有向グラフにおける第２座標点への有向枝を設定し、
前記第２座標点に対応する部分集合は、前記第１座標点に対応する部分集合を包含する、請求項２に記載の情報処理装置。
【請求項４】
前記有向グラフ作成部は、座標軸設定部と、有向枝設定部とを含み、
前記座標軸設定部は、
前記各基本部分木の根ノード及び中間ノードｖの各々について、前記集合（ｌroot’→ｒroot’）又は前記集合（ｌｖ’→ｒｖ’（−１））に含まれる各部分集合に対応する座標点を左から右に向かって包含関係が大きくなるように配列した第１水平座標軸、及び／又は、前記集合（ｌroot’（＋１）←ｒroot’）又は前記集合（ｌｖ’（＋１）←ｒｖ’）に含まれる各部分集合に対応する座標点を左から右に向かって包含関係が大きくなるように配列した第２水平座標軸をそれぞれ設定し、前記第１及び第２水平座標軸の各々の左端及び／又は右端に、少なくとも合計２つの仮座標点を追加設定し、
前記有向枝設定部は、
所定の整数ｋ（ｋはｌｏｇ（ｎ１／ｙ）の約数）を設定し、
ｎ（ｘ−１）／ｋ・ｙ＜（ｒｖ’−ｌｖ’＋１）≦ｎｘ／ｋ・ｙを満たす整数ｘを算定した上で、
前記各第１水平座標軸上の左端にある座標点から開始して、ｎｉ／（ｋ・ｙ）（ｉ＝０〜ｘ−１）だけ離れた座標点へ延びる右向きの有向枝の設定を繰り返し行い、
前記各第２水平座標軸上の右端にある座標点から開始して、ｎｉ／（ｋ・ｙ）（ｉ＝０〜ｘ−１）だけ離れた座標点へ延びる左向きの有向枝の設定を繰り返し行い、
前記各第１及び第２水平座標軸について、前記仮座標点を始点又は終点とする全ての前記有向枝を除外し、
前記各第１及び第２座標軸上の各座標点に到達する前記有向枝のうち、最長の有向枝以外の有向枝を除外する、請求項１に記載の情報処理装置。
【請求項５】
前記有向グラフに基づいて、コンテンツ又はコンテンツ鍵を暗号化するためのセット鍵を生成する鍵生成部をさらに備える、請求項１に記載の情報処理装置。
【請求項６】
前記鍵生成部は、
前記有向グラフにおけるある座標点に対応する部分集合Ｓの中間鍵ｔ（Ｓｉ）の入力に応じて、当該座標点に対応する部分集合Ｓｉに対応する前記セット鍵ｋ（Ｓｉ）と、当該座標点Ｓを始点とする前記有向枝の終点の座標点Ｓ１，Ｓ２，・・・，Ｓｋの中間鍵ｔ（Ｓ１），ｔ（Ｓ２），・・・，ｔ（Ｓｋ）と、を出力する、、請求項５に記載の情報処理装置。
【請求項７】
前記鍵生成部は、
前記有向グラフにおけるある座標点に対応する部分集合Ｓのセット鍵ｋ（Ｓ）の入力に応じて、当該座標点Ｓを始点とする前記有向枝の終点の座標点Ｓ１，Ｓ２，・・・，Ｓｋのセット鍵ｋ（Ｓ１），ｋ（Ｓ２），・・・，ｋ（Ｓｋ）を出力する、請求項５に記載の情報処理装置。
【請求項８】
前記セット鍵を用いて、前記コンテンツ又は前記コンテンツ鍵を暗号化する暗号化部をさらに備える、請求項５に記載の情報処理装置。
【請求項９】
前記全体木構造の葉ノード１〜ｎの一部又は全部にそれぞれ対応付けられた端末装置に、前記暗号化部により暗号化された前記コンテンツ又は前記コンテンツ鍵を送信する送信部をさらに備える、請求項８に記載の情報処理装置。
【請求項１０】
前記全体木構造の葉ノード１〜ｎの部分集合をＳｉと定義したときに、
前記セット鍵または前記コンテンツ鍵で暗号化された前記コンテンツの復号を許可する前記端末装置の集合（Ｎ＼Ｒ）を決定し、前記集合（Ｎ＼Ｒ）＝｛Ｓ１∪Ｓ２∪・・・∪Ｓｍ｝を満たすｍ個の部分集合Ｓ１〜Ｓｍを決定する部分集合決定部をさらに備える、請求項１に記載の情報処理装置。
【請求項１１】
前記部分集合決定部は、前記ｍが最小となるように、前期部分集合Ｓ１〜Ｓｍを決定する、請求項１０に記載の情報処理装置。
【請求項１２】
前記送信部は、
前記集合（Ｎ＼Ｒ）を表す情報、又は、前記集合（Ｎ＼Ｒ）を構成する前記部分集合Ｓ１〜Ｓｍを表す情報を、前記端末装置に送信する、請求項１０に記載の情報処理装置。
【請求項１３】
前記送信部は、
前記暗号化部により前記各部分集合Ｓ１〜Ｓｍに対応する前記セット鍵でそれぞれ暗号化された前記コンテンツ又は前記コンテンツ鍵を、前記端末装置に送信する、請求項９に記載の情報処理装置。
【請求項１４】
有向グラフに基づいて、暗号化されたコンテンツ又はコンテンツ鍵を復号するためのセット鍵を生成する鍵生成部を備え、
前記有向グラフは、
ｎ個の葉ノードと、根ノードと、前記根ノード及び前記葉ノード以外の複数の中間ノードとから構成される２分木の全体木構造を設定し、前記全体木構造を、ｎ１／ｙ個の葉ノードを有する複数の基本部分木に分割してｙ階層（ｙはｌｏｇ（ｎ）の約数）に階層化し、下位階層の前記基本部分木の根ノードが上位階層の前記基本部分木の葉ノードとなるように構成し、
前記全体木構造のノードｗの下位に位置する葉ノードの集合をＡｗと定義し、
前記基本部分木の葉ノードのうち、ある葉ノードｖよりもｉ個左に位置する葉ノードをｖ（−ｉ）、ｉ個右に位置する葉ノードをｖ（＋ｉ）と定義し、
前記基本部分木の２つの葉ノードｕ，ｖ（ｖはｕの右にある）に関し、集合（ｕ→ｖ）を｛Ａｕ，Ａｕ∪Ａｕ（＋１），・・・，Ａｕ∪・・・∪Ａｖ｝、集合（ｕ←ｖ）を｛Ａｖ，Ａｖ∪Ａｖ（−１），・・・，Ａｖ∪・・・∪Ａｕ｝と定義し、
前記基本部分木のノードｖの下位に位置する複数の葉ノードのうち、左端に位置する葉ノードをｌｖ’、右端に位置する葉ノードをｒｖ’と定義したときに、
最上位階層の前記基本部分木の根ノードｒｏｏｔに対して、集合（ｌroot’→ｒroot’）及び集合（ｌroot’（＋１）←ｒroot’）を対応付け、
前記最上位階層以外の階層の前記基本部分木の根ノードｖに対して、集合（ｌｖ’→ｒｖ’（−１））及び集合（ｌｖ’（＋１）←ｒｖ’）を対応付け、
前記各基本部分木の中間ノードｖが、その親ノードの左側に位置する場合には、当該中間ノードｖに対して集合（ｌｖ’（＋１）←ｒｖ’）を対応付け、
前記各基本部分木の中間ノードｖが、その親ノードの右側に位置する場合には、当該中間ノードｖに対して集合（ｌｖ’→ｒｖ’（−１））を対応付け、
前記各基本部分木の根ノード及び中間ノードｖの各々について、前記集合（ｌroot’→ｒroot’）又は前記集合（ｌｖ’→ｒｖ’（−１））に含まれる各部分集合に対応する座標点が、水平座標軸上に左から右に向かって包含関係が大きくなるように配列され、当該座標点を相互に結ぶ有向枝が設定された有向グラフ、及び／又は、前記集合（ｌroot’（＋１）←ｒroot’）又は前記集合（ｌｖ’（＋１）←ｒｖ’）に含まれる各部分集合に対応する座標点が、水平座標軸上に右から左に向かって包含関係が大きくなるように配列され、当該座標点を相互に結ぶ有向枝が設定された有向グラフを生成する、
ことによって得られる、端末装置。
【請求項１５】
前記下位階層の基本部分木に対応する前記有向グラフから、前記上位階層の基本部分木に対応する前記有向グラフへの有向枝が設定されている、請求項１４に記載の端末装置。
【請求項１６】
前記下位階層の基本部分木に対応する前記有向グラフにおける第１座標点から、前記上位階層の基本部分木に対応する前記有向グラフにおける第２座標点への有向枝が設定され、
前記第２座標点に対応する部分集合は、前記第１座標点に対応する部分集合を包含する、請求項１５に記載の端末装置。
【請求項１７】
ｎ個の葉ノードと、根ノードと、前記根ノード及び前記葉ノード以外の複数の中間ノードとから構成される２分木の全体木構造を設定し、前記全体木構造を、ｎ１／ｙ個の葉ノードを有する複数の基本部分木に分割してｙ階層（ｙはｌｏｇ（ｎ）の約数）に階層化し、下位階層の前記基本部分木の根ノードが上位階層の前記基本部分木の葉ノードとなるように構成するステップと；
前記全体木構造のノードｗの下位に位置する葉ノードの集合をＡｗと定義し、
前記基本部分木の葉ノードのうち、ある葉ノードｖよりもｉ個左に位置する葉ノードをｖ（−ｉ）、ｉ個右に位置する葉ノードをｖ（＋ｉ）と定義し、
前記基本部分木の２つの葉ノードｕ，ｖ（ｖはｕの右にある）に関し、集合（ｕ→ｖ）を｛Ａｕ，Ａｕ∪Ａｕ（＋１），・・・，Ａｕ∪・・・∪Ａｖ｝、集合（ｕ←ｖ）を｛Ａｖ，Ａｖ∪Ａｖ（−１），・・・，Ａｖ∪・・・∪Ａｕ｝と定義し、
前記基本部分木のノードｖの下位に位置する複数の葉ノードのうち、左端に位置する葉ノードをｌｖ’、右端に位置する葉ノードをｒｖ’と定義したときに、
最上位階層の前記基本部分木の根ノードｒｏｏｔに対して、集合（ｌroot’→ｒroot’）及び集合（ｌroot’（＋１）←ｒroot’）を対応付け、
前記最上位階層以外の階層の前記基本部分木の根ノードｖに対して、集合（ｌｖ’→ｒｖ’（−１））及び集合（ｌｖ’（＋１）←ｒｖ’）を対応付け、
前記各基本部分木の中間ノードｖが、その親ノードの左側に位置する場合には、当該中間ノードｖに対して集合（ｌｖ’（＋１）←ｒｖ’）を対応付け、
前記各基本部分木の中間ノードｖが、その親ノードの右側に位置する場合には、当該中間ノードｖに対して集合（ｌｖ’→ｒｖ’（−１））を対応付けるステップと；
前記各基本部分木の根ノード及び中間ノードｖの各々について、前記集合（ｌroot’→ｒroot’）又は前記集合（ｌｖ’→ｒｖ’（−１））に含まれる各部分集合に対応する座標点が、水平座標軸上に左から右に向かって包含関係が大きくなるように配列され、当該座標点を相互に結ぶ有向枝が設定された有向グラフ、及び／又は、前記集合（ｌroot’（＋１）←ｒroot’）又は前記集合（ｌｖ’（＋１）←ｒｖ’）に含まれる各部分集合に対応する座標点が、水平座標軸上に右から左に向かって包含関係が大きくなるように配列され、当該座標点を相互に結ぶ有向枝が設定された有向グラフを生成するステップと；
を含む、情報処理方法。
【請求項１８】
ｎ個の葉ノードと、根ノードと、前記根ノード及び前記葉ノード以外の複数の中間ノードとから構成される２分木の全体木構造を設定し、前記全体木構造を、ｎ１／ｙ個の葉ノードを有する複数の基本部分木に分割してｙ階層（ｙはｌｏｇ（ｎ）の約数）に階層化し、下位階層の前記基本部分木の根ノードが上位階層の前記基本部分木の葉ノードとなるように構成し、
前記全体木構造のノードｗの下位に位置する葉ノードの集合をＡｗと定義し、
前記基本部分木の葉ノードのうち、ある葉ノードｖよりもｉ個左に位置する葉ノードをｖ（−ｉ）、ｉ個右に位置する葉ノードをｖ（＋ｉ）と定義し、
前記基本部分木の２つの葉ノードｕ，ｖ（ｖはｕの右にある）に関し、集合（ｕ→ｖ）を｛Ａｕ，Ａｕ∪Ａｕ（＋１），・・・，Ａｕ∪・・・∪Ａｖ｝、集合（ｕ←ｖ）を｛Ａｖ，Ａｖ∪Ａｖ（−１），・・・，Ａｖ∪・・・∪Ａｕ｝と定義し、
前記基本部分木のノードｖの下位に位置する複数の葉ノードのうち、左端に位置する葉ノードをｌｖ’、右端に位置する葉ノードをｒｖ’と定義したときに、
最上位階層の前記基本部分木の根ノードｒｏｏｔに対して、集合（ｌroot’→ｒroot’）及び集合（ｌroot’（＋１）←ｒroot’）を対応付け、
前記最上位階層以外の階層の前記基本部分木の根ノードｖに対して、集合（ｌｖ’→ｒｖ’（−１））及び集合（ｌｖ’（＋１）←ｒｖ’）を対応付け、
前記各基本部分木の中間ノードｖが、その親ノードの左側に位置する場合には、当該中間ノードｖに対して集合（ｌｖ’（＋１）←ｒｖ’）を対応付け、
前記各基本部分木の中間ノードｖが、その親ノードの右側に位置する場合には、当該中間ノードｖに対して集合（ｌｖ’→ｒｖ’（−１））を対応付け、
前記各基本部分木の根ノード及び中間ノードｖの各々について、前記集合（ｌroot’→ｒroot’）又は前記集合（ｌｖ’→ｒｖ’（−１））に含まれる各部分集合に対応する座標点が、水平座標軸上に左から右に向かって包含関係が大きくなるように配列され、当該座標点を相互に結ぶ有向枝が設定された有向グラフ、及び／又は、前記集合（ｌroot’（＋１）←ｒroot’）又は前記集合（ｌｖ’（＋１）←ｒｖ’）に含まれる各部分集合に対応する座標点が、水平座標軸上に右から左に向かって包含関係が大きくなるように配列され、当該座標点を相互に結ぶ有向枝が設定された有向グラフを生成する、
ことによって得られた有向グラフに基づいて、暗号化されたコンテンツ又はコンテンツ鍵を復号するためのセット鍵を生成する、鍵生成方法。
【請求項１９】
ｎ個の葉ノードと、根ノードと、前記根ノード及び前記葉ノード以外の複数の中間ノードとから構成される２分木の全体木構造を設定し、前記全体木構造を、ｎ１／ｙ個の葉ノードを有する複数の基本部分木に分割してｙ階層（ｙはｌｏｇ（ｎ）の約数）に階層化し、下位階層の前記基本部分木の根ノードが上位階層の前記基本部分木の葉ノードとなるように構成するステップと；
前記全体木構造のノードｗの下位に位置する葉ノードの集合をＡｗと定義し、
前記基本部分木の葉ノードのうち、ある葉ノードｖよりもｉ個左に位置する葉ノードをｖ（−ｉ）、ｉ個右に位置する葉ノードをｖ（＋ｉ）と定義し、
前記基本部分木の２つの葉ノードｕ，ｖ（ｖはｕの右にある）に関し、集合（ｕ→ｖ）を｛Ａｕ，Ａｕ∪Ａｕ（＋１），・・・，Ａｕ∪・・・∪Ａｖ｝、集合（ｕ←ｖ）を｛Ａｖ，Ａｖ∪Ａｖ（−１），・・・，Ａｖ∪・・・∪Ａｕ｝と定義し、
前記基本部分木のノードｖの下位に位置する複数の葉ノードのうち、左端に位置する葉ノードをｌｖ’、右端に位置する葉ノードをｒｖ’と定義したときに、
最上位階層の前記基本部分木の根ノードｒｏｏｔに対して、集合（ｌroot’→ｒroot’）及び集合（ｌroot’（＋１）←ｒroot’）を対応付け、
前記最上位階層以外の階層の前記基本部分木の根ノードｖに対して、集合（ｌｖ’→ｒｖ’（−１））及び集合（ｌｖ’（＋１）←ｒｖ’）を対応付け、
前記各基本部分木の中間ノードｖが、その親ノードの左側に位置する場合には、当該中間ノードｖに対して集合（ｌｖ’（＋１）←ｒｖ’）を対応付け、
前記各基本部分木の中間ノードｖが、その親ノードの右側に位置する場合には、当該中間ノードｖに対して集合（ｌｖ’→ｒｖ’（−１））を対応付けるステップと；
前記各基本部分木の根ノード及び中間ノードｖの各々について、前記集合（ｌroot’→ｒroot’）又は前記集合（ｌｖ’→ｒｖ’（−１））に含まれる各部分集合に対応する座標点が、水平座標軸上に左から右に向かって包含関係が大きくなるように配列され、当該座標点を相互に結ぶ有向枝が設定された有向グラフ、及び／又は、前記集合（ｌroot’（＋１）←ｒroot’）又は前記集合（ｌｖ’（＋１）←ｒｖ’）に含まれる各部分集合に対応する座標点が、水平座標軸上に右から左に向かって包含関係が大きくなるように配列され、当該座標点を相互に結ぶ有向枝が設定された有向グラフを生成するステップと；
をコンピュータに実行させるためのプログラム。
【請求項２０】
ｎ個の葉ノードと、根ノードと、前記根ノード及び前記葉ノード以外の複数の中間ノードとから構成される２分木の全体木構造を設定し、前記全体木構造を、ｎ１／ｙ個の葉ノードを有する複数の基本部分木に分割してｙ階層（ｙはｌｏｇ（ｎ）の約数）に階層化し、下位階層の前記基本部分木の根ノードが上位階層の前記基本部分木の葉ノードとなるように構成し、
前記全体木構造のノードｗの下位に位置する葉ノードの集合をＡｗと定義し、
前記基本部分木の葉ノードのうち、ある葉ノードｖよりもｉ個左に位置する葉ノードをｖ（−ｉ）、ｉ個右に位置する葉ノードをｖ（＋ｉ）と定義し、
前記基本部分木の２つの葉ノードｕ，ｖ（ｖはｕの右にある）に関し、集合（ｕ→ｖ）を｛Ａｕ，Ａｕ∪Ａｕ（＋１），・・・，Ａｕ∪・・・∪Ａｖ｝、集合（ｕ←ｖ）を｛Ａｖ，Ａｖ∪Ａｖ（−１），・・・，Ａｖ∪・・・∪Ａｕ｝と定義し、
前記基本部分木のノードｖの下位に位置する複数の葉ノードのうち、左端に位置する葉ノードをｌｖ’、右端に位置する葉ノードをｒｖ’と定義したときに、
最上位階層の前記基本部分木の根ノードｒｏｏｔに対して、集合（ｌroot’→ｒroot’）及び集合（ｌroot’（＋１）←ｒroot’）を対応付け、
前記最上位階層以外の階層の前記基本部分木の根ノードｖに対して、集合（ｌｖ’→ｒｖ’（−１））及び集合（ｌｖ’（＋１）←ｒｖ’）を対応付け、
前記各基本部分木の中間ノードｖが、その親ノードの左側に位置する場合には、当該中間ノードｖに対して集合（ｌｖ’（＋１）←ｒｖ’）を対応付け、
前記各基本部分木の中間ノードｖが、その親ノードの右側に位置する場合には、当該中間ノードｖに対して集合（ｌｖ’→ｒｖ’（−１））を対応付け、
前記各基本部分木の根ノード及び中間ノードｖの各々について、前記集合（ｌroot’→ｒroot’）又は前記集合（ｌｖ’→ｒｖ’（−１））に含まれる各部分集合に対応する座標点が、水平座標軸上に左から右に向かって包含関係が大きくなるように配列され、当該座標点を相互に結ぶ有向枝が設定された有向グラフ、及び／又は、前記集合（ｌroot’（＋１）←ｒroot’）又は前記集合（ｌｖ’（＋１）←ｒｖ’）に含まれる各部分集合に対応する座標点が、水平座標軸上に右から左に向かって包含関係が大きくなるように配列され、当該座標点を相互に結ぶ有向枝が設定された有向グラフを生成する、
ことによって得られた有向グラフに基づいて、暗号化されたコンテンツ又はコンテンツ鍵を復号するためのセット鍵を生成するステップ
をコンピュータに実行させるためのプログラム。