ブロードキャスト暗号化システムにおける除かれたノードリストの生成方法
【課題】タグサイズが小さく、除かれた葉ノードのノードＩＤが効率よく配置された、ブロードキャスト暗号化システムにおける除かれたノードリストの生成方法を提供する。
【解決手段】除かれたノードリストの生成方法は、除かれた葉ノードの親ノードのＩＤを把握するステップと、前記親ノードのＩＤ及び除かれた葉ノードのＩＤを順次並べて、除かれたノードのリストを生成するステップとを含む。又は、除かれた第１の葉ノードの親ノードである第１の親ノードのＩＤを把握するステップと、前記第１の親ノードのＩＤ及び前記第１の葉ノードのＩＤを並べて生成されるＩＤが、除かれたノードＩＤで収録されるリストを生成するステップとを含む。
【解決手段】除かれたノードリストの生成方法は、除かれた葉ノードの親ノードのＩＤを把握するステップと、前記親ノードのＩＤ及び除かれた葉ノードのＩＤを順次並べて、除かれたノードのリストを生成するステップとを含む。又は、除かれた第１の葉ノードの親ノードである第１の親ノードのＩＤを把握するステップと、前記第１の親ノードのＩＤ及び前記第１の葉ノードのＩＤを並べて生成されるＩＤが、除かれたノードＩＤで収録されるリストを生成するステップとを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ブロードキャスト暗号化システムにおける除かれたノードリストの生成方法に係り、より詳しくは、タグサイズの減少のための効率よいブロードキャスト暗号化システムにおける除かれたノードリストの生成方法に関する。
【背景技術】
【０００２】
ブロードキャスト暗号化（Ｂｒｏａｄｃａｓｔ Ｅｎｃｒｙｐｔｉｏｎ、以下、「ＢＥ」と称する。）は、全体のユーザーのうち送信者、すなわち、放送センター（Ｂｒｏａｄｃａｓｔ Ｃｅｎｔｅｒ）が情報の受信を希望するユーザーにのみ情報を効果的に伝える方法であり、情報を受信するユーザーの集まりが任意的で且つ動的に変わる場合に効果的に使用可能でなければならない。ＢＥにおける最も重要な性質は、情報を送信したくないデバイスまたはユーザー（例えば、不法ユーザーまたは期間満了のユーザー）の排除または除外である。
【０００３】
このために、それぞれのデバイスは異なるキー集合（ｋｅｙ ｓｅｔ）を割り当てられて保存しており、サービスプロバイダーは全てのデバイスの全体のキー集合を保存している。
ＢＥシステムには種々の技法が提案されており、通常、階層化されたノード構造を取る場合が多く、また、ＨＢＥＳにおいて実現される場合もある。
ここで、ＨＢＥＳ（Ｈｉｅｒａｒｃｈｉｃａｌ Ｈａｓｈ−Ｃｈａｉｎ Ｂｒｏａｄｃａｓｔ Ｅｎｃｒｙｐｔｉｏｎ Ｓｃｈｅｍｅ）とは、階層的なハッシュチェインブロードキャスト暗号化の体系を意味する。
【０００４】
図１は、ＢＥシステムにおける、各ノードにキーを割り当てる原理を説明するための図である。
図１を参照すると、ノード０、ノード１、ノード２及びノード３が円形に配列されており、ここで、各ノードはＢＥシステム内におけるそれぞれのユーザーに対応する。なお、それぞれのノード（Ｎｏｄｅ ｉ）には独自のノードキーＫｉを割り当てられる。すなわち、ノード０にはＫ０が、ノード１にはＫ１が、ノード２にはＫ２が、ノード３にはＫ３が独自のノードキーとして割り当てられる。
【０００５】
また、円形構造の各ノードは認証されたユーザーのみの通信のためには、認証されたユーザーだけが共有する所定のキーが想定されなければならない。このために、一方向ハッシュ関数に上記各ノードに割り当てられた独自のキー値を連続して適用して、生成されたキー値（つまり、キー集合）を下記の表１に示す方法によりそれぞれのノードに割り当てる。
【０００６】
【表１】
【０００７】
上記表１において、「Ｈ」は一方向ハッシュ関数を意味し、ＨＨ（Ｋ０）＝Ｈ（Ｈ（Ｋ０））を意味する。なお、ここで、一方向ハッシュ関数とは、任意の長さの入力値を固定された長さの出力値に圧縮する関数であり、次のような性質を有している。
一方向ハッシュ関数上においては、与えられた出力値を用いて入力値を求めることが計算上不可能であり、与えられた入力値に対して同じ出力値を示す他の入力値を見出すことが計算上不可能である。加えて、一方向ハッシュ関数上においては、同じ出力値を示す任意の異なる２つの入力値を見出すことも計算上不可能である。
上述の如き性質を満足するハッシュ関数は、データの完全性（ｉｎｔｅｇｒｉｔｙ）、認証、不認防止（ｒｅｐｕｄｉａｔｉｏｎ ｐｒｅｖｅｎｔｉｏｎ）などにおいて応用される重要な関数の一つであり、一方向ハッシュ関数は「ＨＢＥＳ ＳＨＡ−１」でありうる。
【０００８】
図１にもどり、もし、ノード０、ノード１及びノード２だけが安全な通信チャンネルを確保することを希望する場合、ノード０、ノード１及びノード２は暗号化キーとして「ＨＨ（Ｋ０）」を用いるであろう。この場合、ノード０、ノード１及びノード２は暗号化キーに相当する「ＨＨ（Ｋ０）」を保存しているか、あるいは、保存された値からこれを容易に計算することができる。しかしながら、ノード３は上述の一方向関数の特性のために、自分が保存している「ＨＨＨ（Ｋ０）」から暗号化キーに相当する「ＨＨ（Ｋ０）」を計算することができなくなる。
【０００９】
ここで、ノード３のように暗号化通信チャンネルから排除されたノードを除かれたノード（ｒｅｖｏｋｅｄ ｎｏｄｅ）といい、暗号化通信チャンネルを構成しているノードを認証されたノード（ｐｒｉｖｉｌｅｇｅｄ ｎｏｄｅ）という。また、円形に構成されたノードの集まりをノード群という。
【００１０】
一方、多数のノードを処理するためには、図１における構造を階層化する必要がある。
図２は、図１に示す円形ノード群を階層化した構造に示した図である。
図２に示すように、第０の層と第１の層の２つの層からなり、各層を構成するそれぞれのノード群は４個のノードからなり、これらのノードには上記表１における方法により、ハッシュ関数により生成されたキー値（キー集合）が割り当てられる。また、図２における最後の層である第１の層を構成するノードは葉ノード（ｌｅａｆ ｎｏｄｅ）という。
【００１１】
但し、図２に示す層構造において留意すべき点は、下位の層を構成するノードは自分の上位の層を構成する親ノードに割り当てられたキーを保存しているということである。また、層構造において一つのノードが通信チャンネルから除かれた状態であれば、除かれたノードの親ノードも除かれたノードとみなされる。
すなわち、ノード群１のノード３は自分に割り当てられたキー集合とノード群０のノード０に割り当てられたキー集合を両方とも保存している。また、ノード群３のノード１が除かれた場合に、ノード群０のノード２もまた除かれたノードと見なされる。
【００１２】
この時、ノード群０のノード３の暗号化キーである「Ｋ０３（ここで、０はノード群の番号を意味し、３はノードの通し番号を意味する）」から生成された「ＨＨ（Ｋ０３）」を暗号化キーとして用いると、ノード群０のノード３、ノード０、ノード１は暗号化通信チャンネルを確保することができる。
さらに、ノード群３の認証されたノードのためには、「Ｋ３２」から生成された「ＨＨ（Ｋ３２）」を暗号化キーとして用いて、ノード群３の認証されたノードも暗号化通信チャンネルを確保可能にする。
このため、サーバーは、「ＨＨ（Ｋ０３）」と「ＨＨ（Ｋ３２）」を暗号化キーとして用いて、ノード群３のノード１を除く全てのノードに暗号化された情報を伝送することが可能になる。
【００１３】
すなわち、サーバーは上述の方法により選択された暗号化キーを用いて暗号化した臨時キー及び臨時キーにより暗号化したコンテンツを葉ノードに伝送することになる。
この場合、葉ノードは、サーバーからの暗号化されたデータパケットを伝送された場合に、自分が保存しているキーの内のいかなるキーを用いて暗号化キーを生成し、コンテンツを復号化できるかに関する情報が必要となる。
【００１４】
この理由から、サーバーは、暗号化キーを伝送するに際し、葉ノードに暗号化キーに関する情報を得させるために、伝送したいデータパケットにタグを付けて伝送し、このようなタグは除かれたノードに関する情報を含んでいることになる。
このため、葉ノードは、除かれたノードに関する情報から、伝送されたデータパケットを暗号化した暗号化キーを認知することができ、これにより、暗号化キーを生成することになる。
【発明の概要】
【発明が解決しようとする課題】
【００１５】
ＢＥにおいては、伝送量（ｔｒａｎｓｍｉｓｓｉｏｎ ｏｖｅｒｈｅａｄ）、保存量（ｓｔｏｒａｇｅ ｏｖｅｒｈｅａｄ）、計算量（ｃｏｍｐｕｔａｔｉｏｎ ｏｖｅｒｈｅａｄ）を重要視するが、伝送量は伝送側から伝送すべきヘッダーの量、保存量はユーザーが保存すべき秘密キーの量、計算量はユーザーがセッションキーを得るために必要となる計算の量を意味する。中でも、伝送量を減らすことが大きな課題であると言える。このため、タグの伝送による伝送量を減らすことは重要な課題である。
【００１６】
そこで、本発明の目的は、タグサイズの減少のために除かれた葉ノードのノードＩＤの効率よい配置を用いるブロードキャスト暗号化システムにおける、除かれたノードリストの生成方法を提供するところにある。
【課題を解決するための手段】
【００１７】
上記目的を達成するための、本発明によるブロードキャスト暗号化システムにおける、除かれたノードリストの生成方法は、 除かれた葉ノードの親ノードのＩＤを把握するステップと、前記親ノードのＩＤ及び除かれた葉ノードのＩＤを順次に並べて、除かれたノードのリストを生成するステップと、を含むことを特徴とする。
好ましくは、 前記生成ステップは、 （０） 除かれた葉ノードに対する第０の層の親ノードのＩＤ、 （１） 前記除かれた葉ノードに対する第１の層の親ノードのＩＤ、 乃至、 ｎ−２） 前記除かれた葉ノードに対する第ｎ−２の層の親ノードのＩＤ、及び （ｎ−１） 第ｎ−１の層に従属された前記除かれた葉ノードのＩＤ、を結合して、前記除かれたノードのリストを生成する。
好ましくは、 前記ノードはグループ化され、 前記ＩＤは、「ノードが従属するグループにおける前記ノードの順番に従って決定されるノードパスＩＤ（Ｎｏｄｅ Ｐａｔｈ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」及び「前記ノードが従属するグループを示すグループＩＤ（Ｇｒｏｕｐ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」が結合される。
好ましくは、 前記グループＩＤは、 各層における最初のノードに対しては第１の値で割当てられ、 各層における２番目からのノードに対しては、以前のノードと同じグループに従属すると前記第１の値で割当てられ、以前のノードと異なるグループに従属すると第２の値で割当てられる。
好ましくは、 前記第２の値は、 前記第１の値に「１」を加えた後に「２」で割った余り値である。
好ましくは、 前記各層における最初のノードが、子ノードが全て除かれたノードであり、親ノードの子ノードが全て除かれたノードではないノードの子ノードであると、前記グループＩＤは第３の値で割当てられる。
好ましくは、 前記各層における２番目からのノードが、子ノードが全て除かれたノードであり、親ノードの子ノードが全て除かれたノードではないノードの子ノードであると、前記グループＩＤは前記第３の値で割当てられる。
【００１８】
上記目的を達成するための、本発明によるブロードキャスト暗号化システムにおける、除かれたノードリストの生成方法は、 除かれた第１の葉ノードの親ノードである第１の親ノードのＩＤを把握するステップと、 前記第１の親ノードのＩＤ及び前記第１の葉ノードのＩＤを並べて生成されるＩＤが、除かれたノードＩＤで収録されるリストを生成するステップと、 を含むことを特徴とする。
好ましくは、 前記ノードは、第０の層ないし第ｎ−１の層に階層化され、 前記第１の葉ノードは、前記第ｎ−１の層に従属され、 前記第１の親ノードのＩＤは、 「第０の層に従属する第１の親ノードのＩＤ」、「第１の層に従属する第１の親ノードのＩＤ」、乃至、「第ｎ−２の層に従属する第１の親ノードのＩＤ」を含む。
好ましくは、 前記ノードはグループ化され、 前記ＩＤは、「ノードが従属するグループにおける前記ノードの順番に従って決定されるノードパスＩＤ（Ｎｏｄｅ Ｐａｔｈ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」を含む。
好ましくは、 除かれた第２の葉ノードの親ノードである第２の親ノードのＩＤを把握するステップを更に含み、 前記生成ステップは、 前記第１の親ノードのＩＤ及び前記第１の葉ノードのＩＤを並べて生成されるＩＤが、除かれた第１の葉ノードのＩＤで収録され、前記第２の親ノードのＩＤ及び前記第２の葉ノードのＩＤを並べて生成されるＩＤが、除かれた第２の葉ノードのＩＤで収録されるリストを生成する。
好ましくは、 前記ノードは、第０の層ないし第ｎ−１の層に階層化され、 前記第１の葉ノード及び前記第２の葉ノードは、前記第ｎ−１の層に従属され、 前記生成ステップは、 「第０の層に従属する第１の親ノードのＩＤ」、「第０の層に従属する第２の親ノードのＩＤ」、「第１の層に従属する第１の親ノードのＩＤ」、「第１の層に従属する第２の親ノードのＩＤ」、乃至、「第ｎ−２の層に従属する第１の親ノードのＩＤ」、「第ｎ−２の層に従属する第２の親ノードのＩＤ」、前記第１の葉ノードのＩＤ及び前記第２の葉ノードのＩＤを並べて、前記除かれたノードのリストを生成する。
【発明の効果】
【００１９】
本発明による除かれたノードリストの生成方法によれば、タグサイズの減少に伴い、ＢＥシステムにおけるサーバーの伝送量が顕著に減るという効果がある。
【図面の簡単な説明】
【００２０】
【図１】ＢＥシステムにおいて各ノードにキーを割り当てる原理を説明するための図である。
【図２】図１に示す円形ノード群を階層化した構造を示す図である。
【図３】本発明の一実施形態によるタグの形成方法が適用される層構造を示す図である。
【図４】本発明の一実施形態による、特定の層内のノードに属する全ての葉ノードが除かれた場合を示す図である。
【図５】本発明によるタグの形成方法に従ったタグサイズの説明するためのグラフである。
【発明を実施するための形態】
【００２１】
以下、添付図面に基づき、本発明の好適な実施の形態について詳細に説明する。
【００２２】
図３は、本発明の一実施形態によるタグの形成方法が適用される層構造を示す図である。
図３は、層構造が３個の層（第０の層、第１の層、第２の層）からなる場合を例に取っている。図３に示す各ノード群は、図２に示す円形ノード群であってもよいが、説明の便宜のために、図中には円形の構造を示していない。
【００２３】
図３を参照すると、第０の層は、１６個のノードからなる一つのノード群を含んでおり、第１の層は第０の層における１６個の各ノード毎に１６個のノードからなるノード群が子ノードの群を形成する。すなわち、第１の層には１６個のノードからなるノード群が１６個存在し、その結果、１６２個のノードが存在する。
第２の層は、第１の層における１６２個の各ノード毎に１６個のノードからなるノード群が子ノードの群を形成する。すなわち、第２の層には１６個のノードからなるノード群が１６２個存在し、その結果、１６３個のノードが存在する。ここで、最後の層である第２の層を構成する１６３個のノードを葉ノード（ｌｅａｆ ｎｏｄｅ）という。
【００２４】
本実施形態において、層構造は、１６個の層（第０の層、第１の層、．．．、第１５の層）からなってもよく、この場合、第１５の層には第１４の層における１６１５個の各ノード別に１６個のノードからなるノード群が子ノードの群を形成する。すなわち、第１５の層には１６個のノードからなるノード群が１６１５個存在し、その結果、１６１６個のノード（すなわち、葉ノード）が存在すると言える。
【００２５】
以下、葉ノードのノードＩＤの決定方法について述べる。
本実施形態において、図３に示す各ノード群を構成するノードは、順番に０からＦまでの１６進数を通し番号として与えられる。すなわち、それぞれのノード群を構成するノードの数をＮとしたとき、それぞれのノード群を構成するノードに０からＮ−１までの通し番号を与える。
【００２６】
図３を参照すると、本発明によるタグの形成方法における葉ノードのノードＩＤは、最上位の層である第０の層から最下位の層である第１５の層において、葉ノードが属するノードに与えられた通し番号を連続したものである。以下、各層における通し番号は相当する葉ノードに関連する各層におけるノードパスＩＤ（Ｎｏｄｅ Ｐａｔｈ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ、ＮＰＩＤ）という。
【００２７】
すなわち、相当する葉ノードに関連する各層におけるノードパスＩＤを連結したものが葉ノードのノードＩＤとなる。
下記に示す表２は、本発明によるタグの形成方法における葉ノードのノードＩＤの決定方法を示すものである。
【００２８】
【表２】
【００２９】
図３において、第２の層に斜線が入った「○」で表示された葉ノードは現状態において除かれた葉ノードを意味する。合計で９個のノード（ｉ〜ｉｘ）が除かれているとしたとき、それぞれの除かれた葉ノードに対するノードＩＤは次のような方法により構成される。
【００３０】
優先順位１、上位層から下位層への順位により構成される。
優先順位２、同じ層においては、親ノードに与えられたノードパスＩＤが小さなものから構成する。
優先順位３、同じノード群内にある場合には、該当ノード群内におけるノードパスＩＤが小さなものから構成する。
【００３１】
上述の優先順位に応じて、除かれた葉ノード「ｉ」におけるノードＩＤを決定してみると、最上位層である第０の層におけるノードのうちノード「ｉ」の親ノードはノードパスＩＤを「１」として与えられている。ここで、「１」が、除かれた葉ノード「ｉ」の第０の層におけるノードパスＩＤとなる。その後、第１の層におけるノードのうちノード「ｉ」の親ノードはノードパスＩＤを「Ｂ」として与えられている。ここで、「Ｂ」が、除かれた葉ノード「ｉ」の第１の層におけるノードパスＩＤとなる。最後に、除かれた葉ノード「ｉ」は自分が含まれている第２の層においてノードパスＩＤを「１」として与えられている。ここで、「１」が、除かれた葉ノード「ｉ」の第２の層におけるノードパスＩＤとなる。上記のような過程を通じて、除かれた葉ノード「ｉ」のノードＩＤは［１、Ｂ、１］と決定される。
【００３２】
一方、除かれた葉ノード「ｖｉ」におけるノードＩＤを決定してみると、最上位層である第０の層におけるノードのうちノード「ｖｉ」の親ノードはノードパスＩＤを「８」として与えられている。ここで、「８」が、除かれた葉ノード「ｖｉ」の第０の層におけるノードパスＩＤとなる。その後、第１の層におけるノードのうちノード「ｖｉ」の親ノードは、ノードパスＩＤを「０」として与えられている。ここで、「０」が、除かれた葉ノード「ｖｉ」の第１の層におけるノードパスＩＤとなる。最後に、除かれた葉ノード「ｖｉ」は、自分が含まれている第２の層においてノードパスＩＤを「２」として与えられている。ここで、「２」は、除かれた葉ノード「ｖｉ」の第２の層におけるノードパスＩＤとなる。上記のような過程を通じて、除かれた葉ノード「ｖｉ」のノードＩＤは［８、０、２］と決定される。
【００３３】
ここで、表２に示す除かれた葉ノードに対して決定されたノードＩＤを下記の表３に示すように行方向に並べ替える。
【００３４】
【表３】
【００３５】
しかしながら、実際に葉ノードにタグ情報を伝送する場合には、ノードパスＩＤに群ＩＤ（ＧＩＤ）（Ｇｒｏｕｐ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）を付けて伝送することになる。下記に示す表４は、本発明の一実施形態による群ＩＤ（ＧＩＤ）の結合方法を示している。
【００３６】
【表４】
【００３７】
上記表４を参照すると、各層におけるノードパスＩＤに結合された群ＩＤ（ＧＩＤ）は各除かれた葉ノードに対応する各層におけるノードが従属する親ノードのノードパスＩＤとなる。但し、第０の層における除かれた葉ノードに対応するノードの親ノードは存在しないため、第０の層における群ＩＤ（ＧＩＤ）は「０」となる。
換言すると、各ノードパスＩＤには各ノードパスＩＤに相当するノードの親ノードのノードパスＩＤである群ＩＤ（ＧＩＤ）が結合されるのである。
【００３８】
下記の表５は、上記表４による群ＩＤ（ＧＩＤ）の結合方法による場合に各葉ノードに伝送されるタグテーブルを示す。
【００３９】
【表５】
【００４０】
下記の表６は、本発明の他の実施形態による群ＩＤ（ＧＩＤ）の結合方法を示している。
【００４１】
【表６】
【００４２】
上記表６を参照すると、まず、各層における最初のノードパスＩＤには群ＩＤ（ＧＩＤ）として「０」を結合する。また、各層における２番目からのノードパスＩＤは直前のノードパスＩＤと同じノード群内にある場合には以前のノードパスＩＤに結合された群ＩＤ（ＧＩＤ）と同じ群ＩＤ（ＧＩＤ）が結合される。
【００４３】
これに対し、各層における２番目からのノードパスＩＤが直前のノードパスＩＤとは異なるノード群内にある場合には、直前のノードパスＩＤに「１」を加えた後に２で割った余りの値の群ＩＤ（ＧＩＤ）が結合される。すなわち、各層における２番目からのノードパスＩＤが直前のノードパスＩＤとは異なるノード群内にある場合には、直前の群ＩＤ（ＧＩＤ）が「１」である場合には「０」となり、直前の群ＩＤ（ＧＩＤ）が「０」である場合には「１」となる。
【００４４】
下記の表７は、上記表６による群ＩＤ（ＧＩＤ）の結合方法による場合に各葉ノードに伝送されるタグテーブルを示している。
【００４５】
【表７】
【００４６】
一方、本実施形態において、特定の層内のノードに属する全ての葉ノードが除かれた場合を想定する。
図４は、本発明の一実施形態による、特定の層内のノードに属する全ての葉ノードが除かれた場合を示す図である。
【００４７】
図４において、層構造が３個の層（第０の層、第１の層、第２の層）からなる場合を例に取っている。図４に示すように、第０の層は４個のノードからなる一つのノード群を含んでおり、第１の層は第０の層における４個の各ノード毎に４個のノードからなるノード群が子ノードの群を形成する。すなわち、第１の層には４個のノードからなるノード群が４個存在し、その結果、４２個のノードが存在する。
【００４８】
第２の層は、第１の層における４２個の各ノード毎に４個のノードからなるノード群が子ノードの群を形成する。すなわち、第２の層には４個のノードからなるノード群が４２個存在し、その結果、４３個のノードが存在する。ここで、層構造における最後の層である第２の層を構成する４３個のノードを葉ノードという。
【００４９】
本実施形態において、層構造は、１６個の層（第０の層、第１の層、．．．、第１５の層）からなってもよく、また、各ノード群を構成するノードの数もまた１６個になってもよい。この場合、第１５の層には第１４の層における１６１５個の各ノード毎に１６個のノードからなるノード群が子ノードの群を形成する。すなわち、第１５の層には１６個のノードからなるノード群が１６１５個存在し、その結果、１６１６個のノード（すなわち、葉ノード）が存在する。
【００５０】
再び図４を参照すると、第０の層のノード群内の２番目のノードに属する全ての葉ノードが除かれていること、第０の層のノード群内の４番目のノードに属する一つの葉ノードが除かれていることを確認することができる。
除かれた葉ノードのノードＩＤを表２における方法により表現すれば、下記の表８に示す通りである。
【００５１】
【表８】
【００５２】
図４と表８を参照すると、除かれた葉ノード（ａ〜ｐ）まではいずれも第１の層において同じ群をなしているノードを親ノードとしており、第１の層におけるこれらのノードは第０の層における同じノードを親ノードとしている。
この場合、本実施形態において、除かれた葉ノード（ａ）から（ｐ）までのノードＩＤを除かれた葉ノード（ａ）のノードＩＤに置き換える。これを表現すれば、下記の表９に示す通りである。
【００５３】
【表９】
【００５４】
すなわち、本実施形態において、層構造内の特定のノードからの下位の枝（ｂｒａｎｃｈｅｓ）に従属する全ての葉ノードが除かれた場合に、除かれた全ての葉ノードに対する各ノードパスＩＤは、除かれた各葉ノードの各層における全てのノードパスＩＤのうち最も小さなノードパスＩＤに置き換えられる。
【００５５】
図４の場合、群ＩＤ（ＧＩＤ）の結合方法については、下記の表１０において説明する。
【００５６】
【表１０】
【００５７】
表８、表９及び表１０を参照すると、除かれた葉ノード（ａ）〜（ｐ）のノードＩＤに置き換えたＩＤ（以下、代表ノードＩＤと言う。）である［１、０、０］はそれぞれのノードパスＩＤ（［１］、［０］、［０］）により構成される。第０の層におけるノードパスＩＤ［１］は除かれた葉ノード（ａ）から（ｐ）において重複するノードパスＩＤであったが、第１の層及び第２の層におけるノードパスＩＤ（［０］、［０］）は第１の層及び第２の層における葉ノード（ａ）から（ｐ）におけるノードパスＩＤ（［０］、［１］、［２］、［３］）にそれぞれ置き換えている。
【００５８】
代表ノードＩＤを構成するノードパスＩＤのうち、第０の層におけるノードパスＩＤ［１］は、実質的に置き換えたノードパスＩＤがないため、重複による表示をせず、その代わりに、表６において説明した方式により、第０の層における最初のノードパスＩＤとして群ＩＤ（ＧＩＤ）「０」を結合することになる。
【００５９】
一方、代表ノードＩＤを構成するノードパスＩＤのうち第１の層及び第２の層におけるノードパスＩＤ（［０］、［０］）はそれぞれ葉ノード（ａ）から（ｐ）におけるノードパスＩＤ（［０］、［１］、［２］、［３］）に置き換えられているため、これを示すために、群ノードとして所定数の「１」が連続する２進数の群ＩＤ（ＧＩＤ）（例えば、１１、．．．、１１（２））を結合する。
【００６０】
本実施形態において、置き換えたノードパスＩＤの種類の数に応じて、群ＩＤ（ＧＩＤ）の桁数を定めることができ、図４に示すように、４種類のノードパスＩＤの置き換えを行ったならば、群ＩＤ（ＧＩＤ）は「１１（２）」となる。なお、図４中、各群ノードが１６個のノードからなるとしたとき、群ＩＤ（ＧＩＤ）は「１１１１（２）」となる。
ここで、群ＩＤ（ＧＩＤ）の桁数は代表ノードＩＤを構成するノードパスＩＤに相当するノードが構成するノード群内のノードの数（ｔ）に対する底が２の対数値（ｌｏｇ２ｔ）であるともいえる。
【００６１】
一方、表１０における、代表ノードＩＤを構成するノードパスＩＤを除くノードパスＩＤに対する群ＩＤ（ＧＩＤ）の決定方法は、上記表６において説明した方法と同様である。
【００６２】
すなわち、各層におけるノードパスＩＤは直前のノードパスＩＤと同じノード群内にある場合には、以前のノードパスＩＤに結合された群ＩＤ（ＧＩＤ）と同じ群ＩＤ（ＧＩＤ）と結合される。
これに対し、各層における２番目からのノードパスＩＤが直前のノードパスＩＤとは異なるノード群内にある場合には、直前のノードパスＩＤに「１」を加えた後に２で割った余りの値の群ＩＤ（ＧＩＤ）が結合される。
【００６３】
下記の表１１は、上記表１０による群ＩＤ（ＧＩＤ）の結合方法による場合に各葉ノードに伝送されるタグテーブルを示している。
【００６４】
【表１１】
【００６５】
図５は、本発明の実施形態によるタグの形成方法によるタグサイズと、米国特許出願公開第２００２／０１４７９０６号明細書において開示された従来技術によるタグの形成方法によるタグサイズとを比較したグラフである。
【００６６】
図５を参照すると、本発明によるタグサイズ１００の方が上記文献の従来技術によるタグサイズ２００と比べて顕著に小さいことが分かる。除かれた葉ノードが１個の場合には、従来技術に比べて６５倍のタグサイズの減少効果が得られ、除かれた葉ノードが１６個の場合には従来技術に比べて６１倍のタグサイズの減少効果が得られている。
【００６７】
さらに、除かれた葉ノードが２５６個の場合には、従来技術に比べて５７倍のタグサイズの減少効果があり、除かれた葉ノードが６５５３６個の場合には、従来の技術に比べて４９倍のタグサイズの減少効果があり、除かれた葉ノードが４２億個の場合に関しては、従来技術に比べて約３２倍のタグサイズの減少効果が得られている。
【００６８】
なお、以上、本発明の好適な実施形態について図示及び説明したが、本発明は上述の特定の実施形態に限定されるものではなく、特許請求の範囲において請求する本発明の要旨から逸脱しない限り、当該発明が属する技術分野において通常の知識を持った者にとって種々の変形実施が可能であることは言うまでもなく、これらの変形の実施形態は本発明の技術的な思想や展望から個別的に理解されてはならないものである。
【産業上の利用可能性】
【００６９】
本発明は、様々なキャスト暗号化システム、特に、ブロードキャスト暗号化システムに適用可能である。
【技術分野】
【０００１】
本発明は、ブロードキャスト暗号化システムにおける除かれたノードリストの生成方法に係り、より詳しくは、タグサイズの減少のための効率よいブロードキャスト暗号化システムにおける除かれたノードリストの生成方法に関する。
【背景技術】
【０００２】
ブロードキャスト暗号化（Ｂｒｏａｄｃａｓｔ Ｅｎｃｒｙｐｔｉｏｎ、以下、「ＢＥ」と称する。）は、全体のユーザーのうち送信者、すなわち、放送センター（Ｂｒｏａｄｃａｓｔ Ｃｅｎｔｅｒ）が情報の受信を希望するユーザーにのみ情報を効果的に伝える方法であり、情報を受信するユーザーの集まりが任意的で且つ動的に変わる場合に効果的に使用可能でなければならない。ＢＥにおける最も重要な性質は、情報を送信したくないデバイスまたはユーザー（例えば、不法ユーザーまたは期間満了のユーザー）の排除または除外である。
【０００３】
このために、それぞれのデバイスは異なるキー集合（ｋｅｙ ｓｅｔ）を割り当てられて保存しており、サービスプロバイダーは全てのデバイスの全体のキー集合を保存している。
ＢＥシステムには種々の技法が提案されており、通常、階層化されたノード構造を取る場合が多く、また、ＨＢＥＳにおいて実現される場合もある。
ここで、ＨＢＥＳ（Ｈｉｅｒａｒｃｈｉｃａｌ Ｈａｓｈ−Ｃｈａｉｎ Ｂｒｏａｄｃａｓｔ Ｅｎｃｒｙｐｔｉｏｎ Ｓｃｈｅｍｅ）とは、階層的なハッシュチェインブロードキャスト暗号化の体系を意味する。
【０００４】
図１は、ＢＥシステムにおける、各ノードにキーを割り当てる原理を説明するための図である。
図１を参照すると、ノード０、ノード１、ノード２及びノード３が円形に配列されており、ここで、各ノードはＢＥシステム内におけるそれぞれのユーザーに対応する。なお、それぞれのノード（Ｎｏｄｅ ｉ）には独自のノードキーＫｉを割り当てられる。すなわち、ノード０にはＫ０が、ノード１にはＫ１が、ノード２にはＫ２が、ノード３にはＫ３が独自のノードキーとして割り当てられる。
【０００５】
また、円形構造の各ノードは認証されたユーザーのみの通信のためには、認証されたユーザーだけが共有する所定のキーが想定されなければならない。このために、一方向ハッシュ関数に上記各ノードに割り当てられた独自のキー値を連続して適用して、生成されたキー値（つまり、キー集合）を下記の表１に示す方法によりそれぞれのノードに割り当てる。
【０００６】
【表１】
【０００７】
上記表１において、「Ｈ」は一方向ハッシュ関数を意味し、ＨＨ（Ｋ０）＝Ｈ（Ｈ（Ｋ０））を意味する。なお、ここで、一方向ハッシュ関数とは、任意の長さの入力値を固定された長さの出力値に圧縮する関数であり、次のような性質を有している。
一方向ハッシュ関数上においては、与えられた出力値を用いて入力値を求めることが計算上不可能であり、与えられた入力値に対して同じ出力値を示す他の入力値を見出すことが計算上不可能である。加えて、一方向ハッシュ関数上においては、同じ出力値を示す任意の異なる２つの入力値を見出すことも計算上不可能である。
上述の如き性質を満足するハッシュ関数は、データの完全性（ｉｎｔｅｇｒｉｔｙ）、認証、不認防止（ｒｅｐｕｄｉａｔｉｏｎ ｐｒｅｖｅｎｔｉｏｎ）などにおいて応用される重要な関数の一つであり、一方向ハッシュ関数は「ＨＢＥＳ ＳＨＡ−１」でありうる。
【０００８】
図１にもどり、もし、ノード０、ノード１及びノード２だけが安全な通信チャンネルを確保することを希望する場合、ノード０、ノード１及びノード２は暗号化キーとして「ＨＨ（Ｋ０）」を用いるであろう。この場合、ノード０、ノード１及びノード２は暗号化キーに相当する「ＨＨ（Ｋ０）」を保存しているか、あるいは、保存された値からこれを容易に計算することができる。しかしながら、ノード３は上述の一方向関数の特性のために、自分が保存している「ＨＨＨ（Ｋ０）」から暗号化キーに相当する「ＨＨ（Ｋ０）」を計算することができなくなる。
【０００９】
ここで、ノード３のように暗号化通信チャンネルから排除されたノードを除かれたノード（ｒｅｖｏｋｅｄ ｎｏｄｅ）といい、暗号化通信チャンネルを構成しているノードを認証されたノード（ｐｒｉｖｉｌｅｇｅｄ ｎｏｄｅ）という。また、円形に構成されたノードの集まりをノード群という。
【００１０】
一方、多数のノードを処理するためには、図１における構造を階層化する必要がある。
図２は、図１に示す円形ノード群を階層化した構造に示した図である。
図２に示すように、第０の層と第１の層の２つの層からなり、各層を構成するそれぞれのノード群は４個のノードからなり、これらのノードには上記表１における方法により、ハッシュ関数により生成されたキー値（キー集合）が割り当てられる。また、図２における最後の層である第１の層を構成するノードは葉ノード（ｌｅａｆ ｎｏｄｅ）という。
【００１１】
但し、図２に示す層構造において留意すべき点は、下位の層を構成するノードは自分の上位の層を構成する親ノードに割り当てられたキーを保存しているということである。また、層構造において一つのノードが通信チャンネルから除かれた状態であれば、除かれたノードの親ノードも除かれたノードとみなされる。
すなわち、ノード群１のノード３は自分に割り当てられたキー集合とノード群０のノード０に割り当てられたキー集合を両方とも保存している。また、ノード群３のノード１が除かれた場合に、ノード群０のノード２もまた除かれたノードと見なされる。
【００１２】
この時、ノード群０のノード３の暗号化キーである「Ｋ０３（ここで、０はノード群の番号を意味し、３はノードの通し番号を意味する）」から生成された「ＨＨ（Ｋ０３）」を暗号化キーとして用いると、ノード群０のノード３、ノード０、ノード１は暗号化通信チャンネルを確保することができる。
さらに、ノード群３の認証されたノードのためには、「Ｋ３２」から生成された「ＨＨ（Ｋ３２）」を暗号化キーとして用いて、ノード群３の認証されたノードも暗号化通信チャンネルを確保可能にする。
このため、サーバーは、「ＨＨ（Ｋ０３）」と「ＨＨ（Ｋ３２）」を暗号化キーとして用いて、ノード群３のノード１を除く全てのノードに暗号化された情報を伝送することが可能になる。
【００１３】
すなわち、サーバーは上述の方法により選択された暗号化キーを用いて暗号化した臨時キー及び臨時キーにより暗号化したコンテンツを葉ノードに伝送することになる。
この場合、葉ノードは、サーバーからの暗号化されたデータパケットを伝送された場合に、自分が保存しているキーの内のいかなるキーを用いて暗号化キーを生成し、コンテンツを復号化できるかに関する情報が必要となる。
【００１４】
この理由から、サーバーは、暗号化キーを伝送するに際し、葉ノードに暗号化キーに関する情報を得させるために、伝送したいデータパケットにタグを付けて伝送し、このようなタグは除かれたノードに関する情報を含んでいることになる。
このため、葉ノードは、除かれたノードに関する情報から、伝送されたデータパケットを暗号化した暗号化キーを認知することができ、これにより、暗号化キーを生成することになる。
【発明の概要】
【発明が解決しようとする課題】
【００１５】
ＢＥにおいては、伝送量（ｔｒａｎｓｍｉｓｓｉｏｎ ｏｖｅｒｈｅａｄ）、保存量（ｓｔｏｒａｇｅ ｏｖｅｒｈｅａｄ）、計算量（ｃｏｍｐｕｔａｔｉｏｎ ｏｖｅｒｈｅａｄ）を重要視するが、伝送量は伝送側から伝送すべきヘッダーの量、保存量はユーザーが保存すべき秘密キーの量、計算量はユーザーがセッションキーを得るために必要となる計算の量を意味する。中でも、伝送量を減らすことが大きな課題であると言える。このため、タグの伝送による伝送量を減らすことは重要な課題である。
【００１６】
そこで、本発明の目的は、タグサイズの減少のために除かれた葉ノードのノードＩＤの効率よい配置を用いるブロードキャスト暗号化システムにおける、除かれたノードリストの生成方法を提供するところにある。
【課題を解決するための手段】
【００１７】
上記目的を達成するための、本発明によるブロードキャスト暗号化システムにおける、除かれたノードリストの生成方法は、 除かれた葉ノードの親ノードのＩＤを把握するステップと、前記親ノードのＩＤ及び除かれた葉ノードのＩＤを順次に並べて、除かれたノードのリストを生成するステップと、を含むことを特徴とする。
好ましくは、 前記生成ステップは、 （０） 除かれた葉ノードに対する第０の層の親ノードのＩＤ、 （１） 前記除かれた葉ノードに対する第１の層の親ノードのＩＤ、 乃至、 ｎ−２） 前記除かれた葉ノードに対する第ｎ−２の層の親ノードのＩＤ、及び （ｎ−１） 第ｎ−１の層に従属された前記除かれた葉ノードのＩＤ、を結合して、前記除かれたノードのリストを生成する。
好ましくは、 前記ノードはグループ化され、 前記ＩＤは、「ノードが従属するグループにおける前記ノードの順番に従って決定されるノードパスＩＤ（Ｎｏｄｅ Ｐａｔｈ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」及び「前記ノードが従属するグループを示すグループＩＤ（Ｇｒｏｕｐ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」が結合される。
好ましくは、 前記グループＩＤは、 各層における最初のノードに対しては第１の値で割当てられ、 各層における２番目からのノードに対しては、以前のノードと同じグループに従属すると前記第１の値で割当てられ、以前のノードと異なるグループに従属すると第２の値で割当てられる。
好ましくは、 前記第２の値は、 前記第１の値に「１」を加えた後に「２」で割った余り値である。
好ましくは、 前記各層における最初のノードが、子ノードが全て除かれたノードであり、親ノードの子ノードが全て除かれたノードではないノードの子ノードであると、前記グループＩＤは第３の値で割当てられる。
好ましくは、 前記各層における２番目からのノードが、子ノードが全て除かれたノードであり、親ノードの子ノードが全て除かれたノードではないノードの子ノードであると、前記グループＩＤは前記第３の値で割当てられる。
【００１８】
上記目的を達成するための、本発明によるブロードキャスト暗号化システムにおける、除かれたノードリストの生成方法は、 除かれた第１の葉ノードの親ノードである第１の親ノードのＩＤを把握するステップと、 前記第１の親ノードのＩＤ及び前記第１の葉ノードのＩＤを並べて生成されるＩＤが、除かれたノードＩＤで収録されるリストを生成するステップと、 を含むことを特徴とする。
好ましくは、 前記ノードは、第０の層ないし第ｎ−１の層に階層化され、 前記第１の葉ノードは、前記第ｎ−１の層に従属され、 前記第１の親ノードのＩＤは、 「第０の層に従属する第１の親ノードのＩＤ」、「第１の層に従属する第１の親ノードのＩＤ」、乃至、「第ｎ−２の層に従属する第１の親ノードのＩＤ」を含む。
好ましくは、 前記ノードはグループ化され、 前記ＩＤは、「ノードが従属するグループにおける前記ノードの順番に従って決定されるノードパスＩＤ（Ｎｏｄｅ Ｐａｔｈ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」を含む。
好ましくは、 除かれた第２の葉ノードの親ノードである第２の親ノードのＩＤを把握するステップを更に含み、 前記生成ステップは、 前記第１の親ノードのＩＤ及び前記第１の葉ノードのＩＤを並べて生成されるＩＤが、除かれた第１の葉ノードのＩＤで収録され、前記第２の親ノードのＩＤ及び前記第２の葉ノードのＩＤを並べて生成されるＩＤが、除かれた第２の葉ノードのＩＤで収録されるリストを生成する。
好ましくは、 前記ノードは、第０の層ないし第ｎ−１の層に階層化され、 前記第１の葉ノード及び前記第２の葉ノードは、前記第ｎ−１の層に従属され、 前記生成ステップは、 「第０の層に従属する第１の親ノードのＩＤ」、「第０の層に従属する第２の親ノードのＩＤ」、「第１の層に従属する第１の親ノードのＩＤ」、「第１の層に従属する第２の親ノードのＩＤ」、乃至、「第ｎ−２の層に従属する第１の親ノードのＩＤ」、「第ｎ−２の層に従属する第２の親ノードのＩＤ」、前記第１の葉ノードのＩＤ及び前記第２の葉ノードのＩＤを並べて、前記除かれたノードのリストを生成する。
【発明の効果】
【００１９】
本発明による除かれたノードリストの生成方法によれば、タグサイズの減少に伴い、ＢＥシステムにおけるサーバーの伝送量が顕著に減るという効果がある。
【図面の簡単な説明】
【００２０】
【図１】ＢＥシステムにおいて各ノードにキーを割り当てる原理を説明するための図である。
【図２】図１に示す円形ノード群を階層化した構造を示す図である。
【図３】本発明の一実施形態によるタグの形成方法が適用される層構造を示す図である。
【図４】本発明の一実施形態による、特定の層内のノードに属する全ての葉ノードが除かれた場合を示す図である。
【図５】本発明によるタグの形成方法に従ったタグサイズの説明するためのグラフである。
【発明を実施するための形態】
【００２１】
以下、添付図面に基づき、本発明の好適な実施の形態について詳細に説明する。
【００２２】
図３は、本発明の一実施形態によるタグの形成方法が適用される層構造を示す図である。
図３は、層構造が３個の層（第０の層、第１の層、第２の層）からなる場合を例に取っている。図３に示す各ノード群は、図２に示す円形ノード群であってもよいが、説明の便宜のために、図中には円形の構造を示していない。
【００２３】
図３を参照すると、第０の層は、１６個のノードからなる一つのノード群を含んでおり、第１の層は第０の層における１６個の各ノード毎に１６個のノードからなるノード群が子ノードの群を形成する。すなわち、第１の層には１６個のノードからなるノード群が１６個存在し、その結果、１６２個のノードが存在する。
第２の層は、第１の層における１６２個の各ノード毎に１６個のノードからなるノード群が子ノードの群を形成する。すなわち、第２の層には１６個のノードからなるノード群が１６２個存在し、その結果、１６３個のノードが存在する。ここで、最後の層である第２の層を構成する１６３個のノードを葉ノード（ｌｅａｆ ｎｏｄｅ）という。
【００２４】
本実施形態において、層構造は、１６個の層（第０の層、第１の層、．．．、第１５の層）からなってもよく、この場合、第１５の層には第１４の層における１６１５個の各ノード別に１６個のノードからなるノード群が子ノードの群を形成する。すなわち、第１５の層には１６個のノードからなるノード群が１６１５個存在し、その結果、１６１６個のノード（すなわち、葉ノード）が存在すると言える。
【００２５】
以下、葉ノードのノードＩＤの決定方法について述べる。
本実施形態において、図３に示す各ノード群を構成するノードは、順番に０からＦまでの１６進数を通し番号として与えられる。すなわち、それぞれのノード群を構成するノードの数をＮとしたとき、それぞれのノード群を構成するノードに０からＮ−１までの通し番号を与える。
【００２６】
図３を参照すると、本発明によるタグの形成方法における葉ノードのノードＩＤは、最上位の層である第０の層から最下位の層である第１５の層において、葉ノードが属するノードに与えられた通し番号を連続したものである。以下、各層における通し番号は相当する葉ノードに関連する各層におけるノードパスＩＤ（Ｎｏｄｅ Ｐａｔｈ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ、ＮＰＩＤ）という。
【００２７】
すなわち、相当する葉ノードに関連する各層におけるノードパスＩＤを連結したものが葉ノードのノードＩＤとなる。
下記に示す表２は、本発明によるタグの形成方法における葉ノードのノードＩＤの決定方法を示すものである。
【００２８】
【表２】
【００２９】
図３において、第２の層に斜線が入った「○」で表示された葉ノードは現状態において除かれた葉ノードを意味する。合計で９個のノード（ｉ〜ｉｘ）が除かれているとしたとき、それぞれの除かれた葉ノードに対するノードＩＤは次のような方法により構成される。
【００３０】
優先順位１、上位層から下位層への順位により構成される。
優先順位２、同じ層においては、親ノードに与えられたノードパスＩＤが小さなものから構成する。
優先順位３、同じノード群内にある場合には、該当ノード群内におけるノードパスＩＤが小さなものから構成する。
【００３１】
上述の優先順位に応じて、除かれた葉ノード「ｉ」におけるノードＩＤを決定してみると、最上位層である第０の層におけるノードのうちノード「ｉ」の親ノードはノードパスＩＤを「１」として与えられている。ここで、「１」が、除かれた葉ノード「ｉ」の第０の層におけるノードパスＩＤとなる。その後、第１の層におけるノードのうちノード「ｉ」の親ノードはノードパスＩＤを「Ｂ」として与えられている。ここで、「Ｂ」が、除かれた葉ノード「ｉ」の第１の層におけるノードパスＩＤとなる。最後に、除かれた葉ノード「ｉ」は自分が含まれている第２の層においてノードパスＩＤを「１」として与えられている。ここで、「１」が、除かれた葉ノード「ｉ」の第２の層におけるノードパスＩＤとなる。上記のような過程を通じて、除かれた葉ノード「ｉ」のノードＩＤは［１、Ｂ、１］と決定される。
【００３２】
一方、除かれた葉ノード「ｖｉ」におけるノードＩＤを決定してみると、最上位層である第０の層におけるノードのうちノード「ｖｉ」の親ノードはノードパスＩＤを「８」として与えられている。ここで、「８」が、除かれた葉ノード「ｖｉ」の第０の層におけるノードパスＩＤとなる。その後、第１の層におけるノードのうちノード「ｖｉ」の親ノードは、ノードパスＩＤを「０」として与えられている。ここで、「０」が、除かれた葉ノード「ｖｉ」の第１の層におけるノードパスＩＤとなる。最後に、除かれた葉ノード「ｖｉ」は、自分が含まれている第２の層においてノードパスＩＤを「２」として与えられている。ここで、「２」は、除かれた葉ノード「ｖｉ」の第２の層におけるノードパスＩＤとなる。上記のような過程を通じて、除かれた葉ノード「ｖｉ」のノードＩＤは［８、０、２］と決定される。
【００３３】
ここで、表２に示す除かれた葉ノードに対して決定されたノードＩＤを下記の表３に示すように行方向に並べ替える。
【００３４】
【表３】
【００３５】
しかしながら、実際に葉ノードにタグ情報を伝送する場合には、ノードパスＩＤに群ＩＤ（ＧＩＤ）（Ｇｒｏｕｐ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）を付けて伝送することになる。下記に示す表４は、本発明の一実施形態による群ＩＤ（ＧＩＤ）の結合方法を示している。
【００３６】
【表４】
【００３７】
上記表４を参照すると、各層におけるノードパスＩＤに結合された群ＩＤ（ＧＩＤ）は各除かれた葉ノードに対応する各層におけるノードが従属する親ノードのノードパスＩＤとなる。但し、第０の層における除かれた葉ノードに対応するノードの親ノードは存在しないため、第０の層における群ＩＤ（ＧＩＤ）は「０」となる。
換言すると、各ノードパスＩＤには各ノードパスＩＤに相当するノードの親ノードのノードパスＩＤである群ＩＤ（ＧＩＤ）が結合されるのである。
【００３８】
下記の表５は、上記表４による群ＩＤ（ＧＩＤ）の結合方法による場合に各葉ノードに伝送されるタグテーブルを示す。
【００３９】
【表５】
【００４０】
下記の表６は、本発明の他の実施形態による群ＩＤ（ＧＩＤ）の結合方法を示している。
【００４１】
【表６】
【００４２】
上記表６を参照すると、まず、各層における最初のノードパスＩＤには群ＩＤ（ＧＩＤ）として「０」を結合する。また、各層における２番目からのノードパスＩＤは直前のノードパスＩＤと同じノード群内にある場合には以前のノードパスＩＤに結合された群ＩＤ（ＧＩＤ）と同じ群ＩＤ（ＧＩＤ）が結合される。
【００４３】
これに対し、各層における２番目からのノードパスＩＤが直前のノードパスＩＤとは異なるノード群内にある場合には、直前のノードパスＩＤに「１」を加えた後に２で割った余りの値の群ＩＤ（ＧＩＤ）が結合される。すなわち、各層における２番目からのノードパスＩＤが直前のノードパスＩＤとは異なるノード群内にある場合には、直前の群ＩＤ（ＧＩＤ）が「１」である場合には「０」となり、直前の群ＩＤ（ＧＩＤ）が「０」である場合には「１」となる。
【００４４】
下記の表７は、上記表６による群ＩＤ（ＧＩＤ）の結合方法による場合に各葉ノードに伝送されるタグテーブルを示している。
【００４５】
【表７】
【００４６】
一方、本実施形態において、特定の層内のノードに属する全ての葉ノードが除かれた場合を想定する。
図４は、本発明の一実施形態による、特定の層内のノードに属する全ての葉ノードが除かれた場合を示す図である。
【００４７】
図４において、層構造が３個の層（第０の層、第１の層、第２の層）からなる場合を例に取っている。図４に示すように、第０の層は４個のノードからなる一つのノード群を含んでおり、第１の層は第０の層における４個の各ノード毎に４個のノードからなるノード群が子ノードの群を形成する。すなわち、第１の層には４個のノードからなるノード群が４個存在し、その結果、４２個のノードが存在する。
【００４８】
第２の層は、第１の層における４２個の各ノード毎に４個のノードからなるノード群が子ノードの群を形成する。すなわち、第２の層には４個のノードからなるノード群が４２個存在し、その結果、４３個のノードが存在する。ここで、層構造における最後の層である第２の層を構成する４３個のノードを葉ノードという。
【００４９】
本実施形態において、層構造は、１６個の層（第０の層、第１の層、．．．、第１５の層）からなってもよく、また、各ノード群を構成するノードの数もまた１６個になってもよい。この場合、第１５の層には第１４の層における１６１５個の各ノード毎に１６個のノードからなるノード群が子ノードの群を形成する。すなわち、第１５の層には１６個のノードからなるノード群が１６１５個存在し、その結果、１６１６個のノード（すなわち、葉ノード）が存在する。
【００５０】
再び図４を参照すると、第０の層のノード群内の２番目のノードに属する全ての葉ノードが除かれていること、第０の層のノード群内の４番目のノードに属する一つの葉ノードが除かれていることを確認することができる。
除かれた葉ノードのノードＩＤを表２における方法により表現すれば、下記の表８に示す通りである。
【００５１】
【表８】
【００５２】
図４と表８を参照すると、除かれた葉ノード（ａ〜ｐ）まではいずれも第１の層において同じ群をなしているノードを親ノードとしており、第１の層におけるこれらのノードは第０の層における同じノードを親ノードとしている。
この場合、本実施形態において、除かれた葉ノード（ａ）から（ｐ）までのノードＩＤを除かれた葉ノード（ａ）のノードＩＤに置き換える。これを表現すれば、下記の表９に示す通りである。
【００５３】
【表９】
【００５４】
すなわち、本実施形態において、層構造内の特定のノードからの下位の枝（ｂｒａｎｃｈｅｓ）に従属する全ての葉ノードが除かれた場合に、除かれた全ての葉ノードに対する各ノードパスＩＤは、除かれた各葉ノードの各層における全てのノードパスＩＤのうち最も小さなノードパスＩＤに置き換えられる。
【００５５】
図４の場合、群ＩＤ（ＧＩＤ）の結合方法については、下記の表１０において説明する。
【００５６】
【表１０】
【００５７】
表８、表９及び表１０を参照すると、除かれた葉ノード（ａ）〜（ｐ）のノードＩＤに置き換えたＩＤ（以下、代表ノードＩＤと言う。）である［１、０、０］はそれぞれのノードパスＩＤ（［１］、［０］、［０］）により構成される。第０の層におけるノードパスＩＤ［１］は除かれた葉ノード（ａ）から（ｐ）において重複するノードパスＩＤであったが、第１の層及び第２の層におけるノードパスＩＤ（［０］、［０］）は第１の層及び第２の層における葉ノード（ａ）から（ｐ）におけるノードパスＩＤ（［０］、［１］、［２］、［３］）にそれぞれ置き換えている。
【００５８】
代表ノードＩＤを構成するノードパスＩＤのうち、第０の層におけるノードパスＩＤ［１］は、実質的に置き換えたノードパスＩＤがないため、重複による表示をせず、その代わりに、表６において説明した方式により、第０の層における最初のノードパスＩＤとして群ＩＤ（ＧＩＤ）「０」を結合することになる。
【００５９】
一方、代表ノードＩＤを構成するノードパスＩＤのうち第１の層及び第２の層におけるノードパスＩＤ（［０］、［０］）はそれぞれ葉ノード（ａ）から（ｐ）におけるノードパスＩＤ（［０］、［１］、［２］、［３］）に置き換えられているため、これを示すために、群ノードとして所定数の「１」が連続する２進数の群ＩＤ（ＧＩＤ）（例えば、１１、．．．、１１（２））を結合する。
【００６０】
本実施形態において、置き換えたノードパスＩＤの種類の数に応じて、群ＩＤ（ＧＩＤ）の桁数を定めることができ、図４に示すように、４種類のノードパスＩＤの置き換えを行ったならば、群ＩＤ（ＧＩＤ）は「１１（２）」となる。なお、図４中、各群ノードが１６個のノードからなるとしたとき、群ＩＤ（ＧＩＤ）は「１１１１（２）」となる。
ここで、群ＩＤ（ＧＩＤ）の桁数は代表ノードＩＤを構成するノードパスＩＤに相当するノードが構成するノード群内のノードの数（ｔ）に対する底が２の対数値（ｌｏｇ２ｔ）であるともいえる。
【００６１】
一方、表１０における、代表ノードＩＤを構成するノードパスＩＤを除くノードパスＩＤに対する群ＩＤ（ＧＩＤ）の決定方法は、上記表６において説明した方法と同様である。
【００６２】
すなわち、各層におけるノードパスＩＤは直前のノードパスＩＤと同じノード群内にある場合には、以前のノードパスＩＤに結合された群ＩＤ（ＧＩＤ）と同じ群ＩＤ（ＧＩＤ）と結合される。
これに対し、各層における２番目からのノードパスＩＤが直前のノードパスＩＤとは異なるノード群内にある場合には、直前のノードパスＩＤに「１」を加えた後に２で割った余りの値の群ＩＤ（ＧＩＤ）が結合される。
【００６３】
下記の表１１は、上記表１０による群ＩＤ（ＧＩＤ）の結合方法による場合に各葉ノードに伝送されるタグテーブルを示している。
【００６４】
【表１１】
【００６５】
図５は、本発明の実施形態によるタグの形成方法によるタグサイズと、米国特許出願公開第２００２／０１４７９０６号明細書において開示された従来技術によるタグの形成方法によるタグサイズとを比較したグラフである。
【００６６】
図５を参照すると、本発明によるタグサイズ１００の方が上記文献の従来技術によるタグサイズ２００と比べて顕著に小さいことが分かる。除かれた葉ノードが１個の場合には、従来技術に比べて６５倍のタグサイズの減少効果が得られ、除かれた葉ノードが１６個の場合には従来技術に比べて６１倍のタグサイズの減少効果が得られている。
【００６７】
さらに、除かれた葉ノードが２５６個の場合には、従来技術に比べて５７倍のタグサイズの減少効果があり、除かれた葉ノードが６５５３６個の場合には、従来の技術に比べて４９倍のタグサイズの減少効果があり、除かれた葉ノードが４２億個の場合に関しては、従来技術に比べて約３２倍のタグサイズの減少効果が得られている。
【００６８】
なお、以上、本発明の好適な実施形態について図示及び説明したが、本発明は上述の特定の実施形態に限定されるものではなく、特許請求の範囲において請求する本発明の要旨から逸脱しない限り、当該発明が属する技術分野において通常の知識を持った者にとって種々の変形実施が可能であることは言うまでもなく、これらの変形の実施形態は本発明の技術的な思想や展望から個別的に理解されてはならないものである。
【産業上の利用可能性】
【００６９】
本発明は、様々なキャスト暗号化システム、特に、ブロードキャスト暗号化システムに適用可能である。
【特許請求の範囲】
【請求項１】
除かれた葉ノードの親ノードのＩＤを把握するステップと、
前記親ノードのＩＤ及び除かれた葉ノードのＩＤを順次に並べて、除かれたノードのリストを生成するステップと、
を含むことを特徴とする除かれたノードリストの生成方法。
【請求項２】
前記生成ステップは、
（０） 除かれた葉ノードに対する第０の層の親ノードのＩＤ、
（１） 前記除かれた葉ノードに対する第１の層の親ノードのＩＤ、
乃至、
（ｎ−２） 前記除かれた葉ノードに対する第ｎ−２の層の親ノードのＩＤ、及び
（ｎ−１） 第ｎ−１の層に従属された前記除かれた葉ノードのＩＤ、
を結合して、前記除かれたノードのリストを生成することを特徴とする請求項１に記載の除かれたノードリストの生成方法。
【請求項３】
前記ノードはグループ化され、
前記ＩＤは、「ノードが従属するグループにおける前記ノードの順番に従って決定されるノードパスＩＤ（Ｎｏｄｅ Ｐａｔｈ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」及び「前記ノードが従属するグループを示すグループＩＤ（Ｇｒｏｕｐ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」が結合されたことを特徴とする請求項２に記載の除かれたノードリストの生成方法。
【請求項４】
前記グループＩＤは、
各層における最初のノードに対しては第１の値で割当てられ、
各層における２番目からのノードに対しては、以前のノードと同じグループに従属すると前記第１の値で割当てられ、以前のノードと異なるグループに従属すると第２の値で割当てられることを特徴とする請求項３に記載の除かれたノードリストの生成方法。
【請求項５】
前記第２の値は、
前記第１の値に「１」を加えた後に「２」で割った余り値であることを特徴とする請求項４に記載の除かれたノードリストの生成方法。
【請求項６】
前記各層における最初のノードが、子ノードが全て除かれたノードであり、親ノードの子ノードが全て除かれたノードではないノードの子ノードであると、前記グループＩＤは第３の値で割当てられることを特徴とする請求項４に記載の除かれたノードリストの生成方法。
【請求項７】
前記各層における２番目からのノードが、子ノードが全て除かれたノードであり、親ノードの子ノードが全て除かれたノードではないノードの子ノードであると、前記グループＩＤは前記第３の値で割当てられることを特徴とする請求項４に記載の除かれたノードリストの生成方法。
【請求項８】
除かれた第１の葉ノードの親ノードである第１の親ノードのＩＤを把握するステップと、
前記第１の親ノードのＩＤ及び前記第１の葉ノードのＩＤを並べて生成されるＩＤが、除かれたノードＩＤで収録されるリストを生成するステップと、
を含むことを特徴とする除かれたノードリストの生成方法。
【請求項９】
前記ノードは、第０の層ないし第ｎ−１の層に階層化され、
前記第１の葉ノードは、前記第ｎ−１の層に従属され、
前記第１の親ノードのＩＤは、
「第０の層に従属する第１の親ノードのＩＤ」、「第１の層に従属する第１の親ノードのＩＤ」、乃至、「第ｎ−２の層に従属する第１の親ノードのＩＤ」を含むことを特徴とする請求項８に記載の除かれたノードリストの生成方法。
【請求項１０】
前記ノードはグループ化され、
前記ＩＤは、「ノードが従属するグループにおける前記ノードの順番に従って決定されるノードパスＩＤ（Ｎｏｄｅ Ｐａｔｈ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」を含むことを特徴とする請求項８に記載の除かれたノードリストの生成方法。
【請求項１１】
除かれた第２の葉ノードの親ノードである第２の親ノードのＩＤを把握するステップを更に含み、
前記生成ステップは、
前記第１の親ノードのＩＤ及び前記第１の葉ノードのＩＤを並べて生成されるＩＤが、除かれた第１の葉ノードのＩＤで収録され、前記第２の親ノードのＩＤ及び前記第２の葉ノードのＩＤを並べて生成されるＩＤが、除かれた第２の葉ノードのＩＤで収録されるリストを生成することを特徴とする請求項８に記載の除かれたノードリストの生成方法。
【請求項１２】
前記ノードは、第０の層ないし第ｎ−１の層に階層化され、
前記第１の葉ノード及び前記第２の葉ノードは、前記第ｎ−１の層に従属され、
前記生成ステップは、
「第０の層に従属する第１の親ノードのＩＤ」、「第０の層に従属する第２の親ノードのＩＤ」、「第１の層に従属する第１の親ノードのＩＤ」、「第１の層に従属する第２の親ノードのＩＤ」、乃至、「第ｎ−２の層に従属する第１の親ノードのＩＤ」、「第ｎ−２の層に従属する第２の親ノードのＩＤ」、前記第１の葉ノードのＩＤ及び前記第２の葉ノードのＩＤを並べて、前記除かれたノードのリストを生成することを特徴とする請求項１１に記載の除かれたノードリストの生成方法。
【請求項１３】
前記ノードはグループ化され、
前記ＩＤは、「ノードが従属するグループにおける前記ノードの順番に従って決定されるノードパスＩＤ（Ｎｏｄｅ Ｐａｔｈ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」及び「前記ノードが従属するグループを示すグループＩＤ（Ｇｒｏｕｐ ＩＤｅｎｔｉｆｉｎａｔｉｏｎ）」が結合されたことを特徴とする請求項１２に記載の除かれたノードリストの生成方法。
【請求項１】
除かれた葉ノードの親ノードのＩＤを把握するステップと、
前記親ノードのＩＤ及び除かれた葉ノードのＩＤを順次に並べて、除かれたノードのリストを生成するステップと、
を含むことを特徴とする除かれたノードリストの生成方法。
【請求項２】
前記生成ステップは、
（０） 除かれた葉ノードに対する第０の層の親ノードのＩＤ、
（１） 前記除かれた葉ノードに対する第１の層の親ノードのＩＤ、
乃至、
（ｎ−２） 前記除かれた葉ノードに対する第ｎ−２の層の親ノードのＩＤ、及び
（ｎ−１） 第ｎ−１の層に従属された前記除かれた葉ノードのＩＤ、
を結合して、前記除かれたノードのリストを生成することを特徴とする請求項１に記載の除かれたノードリストの生成方法。
【請求項３】
前記ノードはグループ化され、
前記ＩＤは、「ノードが従属するグループにおける前記ノードの順番に従って決定されるノードパスＩＤ（Ｎｏｄｅ Ｐａｔｈ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」及び「前記ノードが従属するグループを示すグループＩＤ（Ｇｒｏｕｐ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」が結合されたことを特徴とする請求項２に記載の除かれたノードリストの生成方法。
【請求項４】
前記グループＩＤは、
各層における最初のノードに対しては第１の値で割当てられ、
各層における２番目からのノードに対しては、以前のノードと同じグループに従属すると前記第１の値で割当てられ、以前のノードと異なるグループに従属すると第２の値で割当てられることを特徴とする請求項３に記載の除かれたノードリストの生成方法。
【請求項５】
前記第２の値は、
前記第１の値に「１」を加えた後に「２」で割った余り値であることを特徴とする請求項４に記載の除かれたノードリストの生成方法。
【請求項６】
前記各層における最初のノードが、子ノードが全て除かれたノードであり、親ノードの子ノードが全て除かれたノードではないノードの子ノードであると、前記グループＩＤは第３の値で割当てられることを特徴とする請求項４に記載の除かれたノードリストの生成方法。
【請求項７】
前記各層における２番目からのノードが、子ノードが全て除かれたノードであり、親ノードの子ノードが全て除かれたノードではないノードの子ノードであると、前記グループＩＤは前記第３の値で割当てられることを特徴とする請求項４に記載の除かれたノードリストの生成方法。
【請求項８】
除かれた第１の葉ノードの親ノードである第１の親ノードのＩＤを把握するステップと、
前記第１の親ノードのＩＤ及び前記第１の葉ノードのＩＤを並べて生成されるＩＤが、除かれたノードＩＤで収録されるリストを生成するステップと、
を含むことを特徴とする除かれたノードリストの生成方法。
【請求項９】
前記ノードは、第０の層ないし第ｎ−１の層に階層化され、
前記第１の葉ノードは、前記第ｎ−１の層に従属され、
前記第１の親ノードのＩＤは、
「第０の層に従属する第１の親ノードのＩＤ」、「第１の層に従属する第１の親ノードのＩＤ」、乃至、「第ｎ−２の層に従属する第１の親ノードのＩＤ」を含むことを特徴とする請求項８に記載の除かれたノードリストの生成方法。
【請求項１０】
前記ノードはグループ化され、
前記ＩＤは、「ノードが従属するグループにおける前記ノードの順番に従って決定されるノードパスＩＤ（Ｎｏｄｅ Ｐａｔｈ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」を含むことを特徴とする請求項８に記載の除かれたノードリストの生成方法。
【請求項１１】
除かれた第２の葉ノードの親ノードである第２の親ノードのＩＤを把握するステップを更に含み、
前記生成ステップは、
前記第１の親ノードのＩＤ及び前記第１の葉ノードのＩＤを並べて生成されるＩＤが、除かれた第１の葉ノードのＩＤで収録され、前記第２の親ノードのＩＤ及び前記第２の葉ノードのＩＤを並べて生成されるＩＤが、除かれた第２の葉ノードのＩＤで収録されるリストを生成することを特徴とする請求項８に記載の除かれたノードリストの生成方法。
【請求項１２】
前記ノードは、第０の層ないし第ｎ−１の層に階層化され、
前記第１の葉ノード及び前記第２の葉ノードは、前記第ｎ−１の層に従属され、
前記生成ステップは、
「第０の層に従属する第１の親ノードのＩＤ」、「第０の層に従属する第２の親ノードのＩＤ」、「第１の層に従属する第１の親ノードのＩＤ」、「第１の層に従属する第２の親ノードのＩＤ」、乃至、「第ｎ−２の層に従属する第１の親ノードのＩＤ」、「第ｎ−２の層に従属する第２の親ノードのＩＤ」、前記第１の葉ノードのＩＤ及び前記第２の葉ノードのＩＤを並べて、前記除かれたノードのリストを生成することを特徴とする請求項１１に記載の除かれたノードリストの生成方法。
【請求項１３】
前記ノードはグループ化され、
前記ＩＤは、「ノードが従属するグループにおける前記ノードの順番に従って決定されるノードパスＩＤ（Ｎｏｄｅ Ｐａｔｈ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）」及び「前記ノードが従属するグループを示すグループＩＤ（Ｇｒｏｕｐ ＩＤｅｎｔｉｆｉｎａｔｉｏｎ）」が結合されたことを特徴とする請求項１２に記載の除かれたノードリストの生成方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１２−９０３２４（Ｐ２０１２−９０３２４Ａ）
【公開日】平成２４年５月１０日（２０１２．５．１０）
【国際特許分類】
【出願番号】特願２０１１−２７６３９２（Ｐ２０１１−２７６３９２）
【出願日】平成２３年１２月１６日（２０１１．１２．１６）
【分割の表示】特願２００８−５０７５４３（Ｐ２００８−５０７５４３）の分割
【原出願日】平成１８年４月１４日（２００６．４．１４）
【出願人】（５０３４４７０３６）サムスン エレクトロニクス カンパニー リミテッド (2,221)
【Ｆターム（参考）】
【公開日】平成２４年５月１０日（２０１２．５．１０）
【国際特許分類】
【出願日】平成２３年１２月１６日（２０１１．１２．１６）
【分割の表示】特願２００８−５０７５４３（Ｐ２００８−５０７５４３）の分割
【原出願日】平成１８年４月１４日（２００６．４．１４）
【出願人】（５０３４４７０３６）サムスン エレクトロニクス カンパニー リミテッド (2,221)
【Ｆターム（参考）】
[ Back to top ]