JP2004320655A - Data processing method, program thereof, apparatus thereof, and receiver - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a data processing method capable of decreasing a communication volume of communication between a key management source and a plurality of receivers attended with revocation of parts of the receivers more than that of prior arts in the case of secure communication between the key management source and the receivers. <P>SOLUTION: When the key management apparatus determines that a communication volume when adopting a key acquisition method SKT-A is a communication volume or over consumed when adopting a key acquisition method SKT-B (ST23), the key management apparatus specifies key encryption key data used for communication with the receivers not revoked according to the key acquisition method SKT-A on the basis of a revocation list (ST24). In other cases, the key management apparatus specifies the key encryption key data according to the key acquisition method SKT-B on the basis of the revocation list (ST25). <P>COPYRIGHT: (C)2005,JPO&NCIPI

Description

【００２８】
Ｋ＝３、Ｈ〔０〕＝２、Ｈ〔１〕＝１、Ｈ〔３〕＝２の場合のツリー２０の構造を図３に示す。
【００２９】
以下、上記ツリーを基に規定された本実施形態の鍵取得方法について説明する。
図４は、本実施形態の鍵取得方法を説明するためのフローチャートである。
以下、図４に示す各ステップについて説明する。
ステップＳＴ１：
処理部１３は、上記ツリーの水平レイヤ０（最下層のレイヤ）に属する全てのセクションの各々に対して、当該セクションが含むサブツリーのリーフに割り当てられた受信装置４＿１〜４＿Ｎのうち、リボークする受信装置を特定する。
また、処理部１３は、ｌに初期値「０」を代入する。
【００３０】
ステップＳＴ２：
処理部１３は、上記ツリーの水平レイヤ０に属する全てのセクションの各々に対して、当該セクションが含むサブツリーに対して採用されたリボケーション方式で、ステップＳＴ１で特定した受信装置をリボークする処理を行う。
すなわち、処理部１３は、上記採用されたリボケーション（ＲＶ）方式を基にリボケーション処理を行い、当該サブツリーに属する受信装置４＿１〜４＿Ｎのうちリボークされない受信装置との通信に使用する鍵暗号鍵データＫＥＫを決定するために用いられるデータ、例えば、リボークするリーフの位置などを示すデータを生成する。
【００３１】
ステップＳＴ３：
処理部１３は、ｌをインクリメントする。すなわち、ｌ＝ｌ＋１を演算する。
【００３２】
ステップＳＴ４：
処理部１３は、上記ツリーの水平レイヤｋに属する全てのセクションの各々に対して、当該セクションが含むサブツリーのリーフ（ノード、水平レイヤｌ−１のルート）のうち、その下層にリボークされる受信装置があるリーフ、すなわちリボークにより影響を受けるリーフを特定する。
【００３３】
ステップＳＴ５：
処理部１３は、上記ツリーの水平レイヤｌに属する全てのセクションの各々に対して、当該セクションが含むサブツリーに対して採用されたリボケーション方式で、ステップＳ４１で特定したリーフをリボークする処理を行う。
すなわち、処理部１３は、上記採用されたリボケーション（ＲＶ）方式を基にリボケーション処理を行い、当該サブツリーに属するリーフのうちリボークの影響を受けないリーフの下層にある受信装置との通信に使用する鍵暗号鍵データＫＥＫを決定するために用いられるデータ、例えば、リボークするノードの位置などを示すデータを生成する。
【００３４】
ステップＳＴ６：
処理部１３は、ｋ＝Ｋであるか否かを判断し、ｌ＝Ｌであると判断した場合に処理を終了し、そうでない場合にステップＳＴ３の処理に戻る。
【００３５】
ステップＳＴ７：
処理部１３は、ステップＳＴ１〜ＳＴ６によって、全ての水平レイヤに属する全てのセクションについて行われたＲＶ処理の結果を基に、リボークしない受信装置４＿１〜４＿Ｎとの間の通信に用いる鍵暗号鍵データＫＥＫｍを生成する。
ここで、ｍは１〜Ｍの整数であり、Ｍは、リボークしない全ての受信装置との通信に用いる鍵暗号鍵データＫＥＫの数を示している。
この場合に、リボークする受信装置の上記ツリー上の位置に応じて、複数のリボークしない受信装置が共通の鍵暗号鍵データＫＥＫｍを使用する場合がある。
【００３６】
次に、本実施形態において採用する鍵取得方法ＳＫＴである鍵取得方法ＳＫＴ−ＡおよびＳＫＴ−Ｂについて説明する。
鍵取得方法ＳＫＴ−Ａ，ＳＫＴ−Ｂは、前述した非特許文献１に開示されているＬＳＤ方式に比べて、受信装置４＿１〜４＿Ｎが記憶するラベルデータＬＡＢＥＬおよび鍵データＫ＿ＯＲＧのデータ量が少なく、非特許文献２に開示されているＣＳＴ方式に比べてリボケーション処理に伴う鍵管理装置３と受信装置４＿１〜４＿Ｎとの間の通信量が小さいという特徴を有している。
【００３７】
先ず、鍵取得方法ＳＫＴ−Ａについて説明する。
図５は、鍵取得方法ＳＫＴ−Ａを説明するための図である。
図５に示すように、鍵取得方法ＳＫＴ−Ａでは、ツリーを２つの水平レイヤＡ０，Ａ１に分割する。
ここで、水平レイヤＡ０が本発明の第１のレイヤに対応し、水平レイヤＡ１が本発明の第２のレイヤに対応している。
最下層の水平レイヤＡ０の高さをＨＡ〔０〕とし、水平レイヤＡ１の高さを（ｌｏｇ_２ Ｎ−ＨＡ〔０〕）とする。ここで、Ｎは受信装置４＿１〜４＿Ｎの総数を示す。
そして、水平レイヤＡ０に属する各セクション３１〔０〕のリボケーション方式として上記非特許文献１に開示されているＬＳＤ方式を採用する。
また、水平レイヤＡ１に属する各セクション３１〔１〕のリボケーション方式として上記非特許文献２に開示されているＣＳＴ方式を採用する。
【００３８】
ここで、鍵取得方法ＳＫＴ−Ａにおいて、Ｒ個の受信装置４＿１〜４＿Ｎのリボークが、上記ツリーを構成するＲ_０Ａ個のセクションに影響を与えるとする。
この場合に、リボークに伴う鍵管理装置３とリボークされない受信装置４＿１〜４＿Ｎとの間の通信量のディメンションは、鍵取得方法ＳＫＴ−Ａの場合には下記式（２）に示すＯ（ＣＯＡ）となる。
【００３９】
【数２】
Ｏ（ＣＯＡ）＝Ｏ（Ｒ＋Ｒ_０Ａ（ｌｏｇ_２ Ｎ−Ｈ_０Ａ）−Ｒ_０Ａｌｏｇ_２ Ｒ_０Ａ）…（２）
【００４０】
次に、鍵取得方法ＳＫＴ−Ｂについて説明する。
図６は、鍵取得方法ＳＫＴ−Ｂを説明するための図である。
図６に示すように、鍵取得方法ＳＫＴ−Ｂでは、ツリーを３つの水平レイヤＢ０，Ｂ１，Ｂ２に分割する。
ここで、水平レイヤＢ０が本発明の第３のレイヤに対応し、水平レイヤＢ１が本発明の第４のレイヤに対応し、水平レイヤＢ２が本発明の第５のレイヤに対応している。
【００４１】
最下層の水平レイヤＢ０の高さをＨＢ〔０〕とし、水平レイヤＢ１の高さをＨＢ〔１〕とし、水平レイヤＢ２の高さを（ｌｏｇ_２ Ｎ−ＨＢ〔０〕−ＨＢ〔１〕）とする。
そして、水平レイヤＢ０に属する各セクション３１〔０〕のリボケーション方式として上記非特許文献１に開示されているＬＳＤ方式を採用する。
また、水平レイヤＢ１に属する各セクション３１〔１〕のリボケーション方式として上記非特許文献１に開示されているＬＳＤ方式を採用する。
さらに、水平レイヤＢ２に属する各セクション３１〔２〕のリボケーション方式として上記非特許文献２に開示されているＣＳＴ方式を採用する。
【００４２】
ここで、上述した鍵取得方法ＳＫＴ−Ｂにおいて、Ｒ個の受信装置４＿１〜４＿Ｎのリボークが、上記ツリーを構成する水平レイヤＢ１のＲ_０Ｂ個のセクションに影響を与え、さらに水平レイヤＢ２のＲ_１Ｂ個のセクションに影響を与えるとする。
この場合に、リボークに伴う鍵管理装置１０３とリボークされない受信装置１０４＿１〜１０４＿Ｎとの間の通信量のディメンションは、鍵取得方法ＳＫＴ−Ｂの場合には下記式（３）に示すＯ（ＣＯＢ）となる。
【００４３】
【数３】

【００４４】
以下、ＣＳＴ方式について説明する。
図７〜図９は、ＣＳＴ方式を説明するための図である。
以下の説明では、図７に示すように、１６個の受信装置ｕ１〜ｕ１６に対してＣＳＴ方式でリボケーション処理を行う場合を例示する。
ＣＳＴ方式では、２分ツリーの各ノードを用いて、「そのノードを頂点とする２分ツリーのリーフに割り当てられた受信装置からなる集合」を規定する。
図７に示す例では、ノードｉは、受信装置ｕ５とｕ６を要素とする集合を示す。そして、各ノードにノードキー（ＳＫＴ−Ａでは鍵データＫ＿ＯＲＧに対応）が定義される。
【００４５】
各受信装置には、それが割り当てられているリーフから、鍵管理装置が割り当てられているツリーのルートに至るパス上のノードに割り当てられたノードキーが与えられ、受信装置はこれらのノードキーを安全なメモリに保持する。
図８に示すように、受信装置ｕ４には、ノード１，２，４，９，１９に割り当てられた５個のノードキーが与えられる。
すなわち、全受信装置数をＮとした場合には、各受信装置はｌｏｇＮ＋１個のノードキーを保持する。
【００４６】
図９は、秘密情報（たとえば、暗号化されたコンテンツを復号するためのコンテンツキー）をどのようにリボークされない受信装置に送信するかを説明するための図である。
ここで、受信装置ｕ２，ｕ１１，ｕ１２がリボークする受信装置とする。
この場合に、リボークする受信装置ｕ２，ｕ１１，ｕ１２が割り当てられているリーフからツリーのルートに至るパス上のノードに割り当てられたノードキーは使用することができない。これは、これらのノードキーを使用するとリボークする受信装置が秘密情報を入手できてしまうためである。
そして、これらのノードおよびパスをツリーから除外すると、１つ以上のサブツリー（部分ツリー）が残る。
それぞれのサブツリーの頂点に最も近いノード（図９ではノード５，７，９，１２，１６）に割り当てられたノードキーを用いて秘密情報を暗号化して送信することで、効率的で安全な秘密情報の送信を行う。
受信装置は、伝送された暗号文のうち、自分が復号できるもの、すなわち、自身が割り当てられたリーフからルートに至るまでのパス上のノードに対応するノードキーを用いて暗号化されたものを復号して秘密情報を得る。
上記の例では、例えば、受信装置ｕ４はノード９のノードキーを保持しているので、これを用いて暗号化された暗号文を復号する。
ＣＳＴ方式では、リボークしない受信装置が復号できる暗号文は必ずひとつ存在する。
【００４７】
次に、ＬＳＤ方式の前提となったＳＤ（Ｓｕｂｓｅｔ Ｄｉｆｆｅｒｅｎｃｅ） 方式について説明する。
図１０〜図１３は、ＳＤ方式を説明するための図である。
上述したように、ＣＳＴ方式においては、ツリーの各ノードを用いて、「そのノードを頂点とするサブツリーのリーフに割り当てられた受信装置からなる集合」を表している。
これに対し、ＳＤ方式では、ツリーの２つのノードｉ，ｊ（ただしｉはｊの先祖であるノード）を用いて、「（ノードｉを頂点とするサブツリーのリーフからなる集合）から（ノードｉを頂点とするサブツリーのリーフからなる集合）を引いた集合」を定義する。
例えば、図１０に示すノードｉ，ｊで定義される集合Ｓ（ｉ，ｊ）は、受信装置ｕ１〜ｕ８の集合から受信装置ｕ５，ｕ６を除いたものであり、すなわち、Ｓ（ｉ，ｊ）＝｛ｕ１，ｕ２，ｕ３，ｕ４，ｕ５，ｕ６，ｕ７，ｕ８，ｕ９｝−｛ｕ５，ｕ６｝である。
ノードｉがノードｊの先祖である（すなわち、ノードｊはノードｉと同一ではなく、ノードｊからルートへのパス上にノードｉが存在する）全てのノードの組についてこのような集合を定義する。
そして、各集合に、ラベルデータＬＡＢＥＬを割り当てる。また、ラベルデータＬＡＢＥＬを基に所定の演算（例えば、当該ラベルデータＬＡＢＥＬをキーとして疑似乱数を生成して）を行ってサブセットキーを得る。
当該サブセットキーは、当該集合の要素である受信装置と鍵管理装置との間の通信において、鍵暗号鍵データＫＥＫとして用いられる。
ＳＤ方式では、一つの受信装置が所属する集合の個数はＯ（Ｎ）となるため、それぞれの集合（サブセット）に鍵データＳＫ（サブセットキー）を独立に割り当てたのでは、各受信装置がＯ（Ｎ）個のサブセットキーに対応するラベルデータＬＡＢＥＬを安全に保持する必要があるが、これはＮが大きいときには現実的に困難である。
【００４８】
そのため、ＳＤ方式では以下に述べる手法により、各受信装置が保持するラベルデータＬＡＢＥＬの数を削減している。
例えば、図１１（Ａ）に示すように、内部ノード（すなわち、リーフでないノード）ｉに注目し、そのノードのラベルデータＬＡＢＥＬ（ｉ）としてＣビットの値Ｓをランダムに選択する。
次に、図１２に示すように、Ｃビット入力、３Ｃビット出力の擬似乱数生成器Ｇに、ＬＡＢＥＬ（ｉ）の値Ｓを入力する。
そして、擬似乱数生成器Ｇからの３Ｃビットの出力を左から（最上位ビット側から）Ｃビットずつに区切り、それぞれＧ_Ｌ （Ｓ），Ｇ_Ｍ （Ｓ），Ｇ_Ｒ （Ｓ）とする。
【００４９】
そして、Ｇ_Ｌ （Ｓ）を、ノードｉの左側（一方）の子ノードのラベルデータＬＡＢＥＬとし、Ｇ_Ｒ （Ｓ）をノードｉの右側（他方）の子ノードのラベルデータＬＡＢＥＬとする。
この処理により、図１１においてノードｉの左側の子であるノードｋについて、ノードｉを始点にした場合のノードｋのラベルデータＬＡＢＥＬ（ｉ，ｋ）は、ＬＡＢＥＬ（ｉ，ｋ）＝Ｇ_Ｌ （Ｓ）となる。そして、これをＴとする。
次に、Ｔを上記の擬似乱数生成器Ｇに入力し、その出力を左からＣビットずつに区切って、Ｇ_Ｌ （Ｔ），Ｇ_Ｍ （Ｔ），Ｇ_Ｒ （Ｔ）を得る。
そして、Ｇ_Ｌ （Ｔ），Ｇ_Ｍ （Ｔ），Ｇ_Ｒ （Ｔ）を、それぞれノードｉを始点にした場合のノードｋの左側の子ノードＬのラベルデータＬＡＢＥＬ（ｉ，ｋＬ）、ノードｉを始点にした場合のノードｋのラベルデータＬＡＢＥＬ（ｉ，ｋ）、ノードｉを始点にした場合のノードｋの右側の子ノードｋＲのラベルデータＬＡＢＥＬ（ｉ，ｋＲ）とする。
この処理を繰り返すことにより、ノードｉを始点とした場合の、その子孫となるすべてのノードに対応するラベルを作り出す。
【００５０】
なお、上記の定義によれば集合Ｓ（ｉ，ｉ）は空集合であり、ノードｉを始点とした場合に、ノードｉの鍵というものは不要であるため、ＬＡＢＥＬ（ｉ）を擬似乱数生成器Ｇに入力した出力の中央部分であるＧ_Ｍ （Ｓ）は使われない。
図１１（Ａ）に示すように、始点であるノードｉのラベルデータＬＡＢＥＬ（ｉ）の値Ｓが定められ、Ｇ_Ｒ （Ｓ）がノードｉを始点とした場合のノードｉの右の子ノードのラベルデータＬＡＢＥＬとなり、さらにそれを擬似乱数生成器Ｇに入力して得られたＧ_Ｌ （Ｓ）が、ノードｉを始点とした場合のノードｊのラベルデータＬＡＢＥＬとなる。
この処理を、すべての内部ノードｉに対して行う。
【００５１】
これらの処理はシステムのセットアップ時に鍵管理装置によって行われるが、擬似乱数生成器（あるいは擬似乱数生成関数）Ｇは鍵管理装置によって定められ公開されており、これを用いることによって、ＬＡＢＥＬ（ｉ，ｊ）を与えられた受信装置は、ノードｉを始点とした場合の、ノードｊの子孫となるすべてのノードｎのラベルＬＡＢＥＬ（ｉ，ｎ）を計算でき、ノードｉを始点とした場合の、ノードｊおよびその子孫ノードｎのサブセットキーＳＫ（ｉ，ｎ）を計算できる。
このようにしておけば、図１１（Ｂ）に示すように、ある受信装置ｕは、それが割り当てられたリーフからツリーの頂点へのパス上のそれぞれの内部ノードｉについて、ノードｉを始点として、このリーフからｉへのパスから直接枝分かれしているノードのラベルデータＬＡＢＥＬのみを保持しておけば、そのノードおよびそれ以降の（その子孫となる）ノードの、ノードｉを始点としたサブセットキーを作り出すことが可能となる。図１１（Ｂ）では、ノードｉに注目したときに、ｕからｉへのパスから直接枝分かれしているノードは３つであり、受信装置ｕは、これら３つのラベルデータＬＡＢＥＬをシステムのセットアップ時に鍵管理装置から受け取る。
【００５２】
以下、図１３に示す例において、受信装置ｕ４について考える。
受信装置ｕ４については、それが割り当てられたリーフであるノード１９から、ルート１へのパス上の内部ノード１，２，４，９が始点（ノードｉ）となる。ノード１を始点とすると、ノード１９からノード１へのパスから直接枝分かれしているノードはノード３，５，８，１８の４つであるため、ＬＡＢＥＬ（１，３），（１，５），（１，８），（１，１８）を受信装置ｕ４は保持する。
同様に、ノード２を始点とした場合にＬＡＢＥＬ（２，５），（２，８），（２，１８）３つのラベルデータＬＡＢＥＬを、ノード４を始点とした場合にはＬＡＢＥＬ（４，８），（４，１８）の２つのラベルデータＬＡＢＥＬを、ノード９を始点とした場合にはＬＡＢＥＬ（９，１８）を保持する。
また、リボークする受信装置がないという特別な場合に使用する、全受信装置を含む集合（これをＳ１，φと表すことにする）に対応するラベルデータＬＡＢＥＬ（１）をひとつ保持する。
ただし、Ｓ（１），φに対応するラベルデータＬＡＢＥＬとしているが、ラベルデータＬＡＢＥＬではなくＳ１、Φに対応するサブセットキーを直接保持してもよい。
上記のように、各受信装置は、リーフからルートへのパス上の各内部ノードについて、その内部ノードの高さ分だけのラベルデータＬＡＢＥＬを保持する必要がある。
これらのラベルデータＬＡＢＥＬは、公開されているＧを用いることによりサブセットキーを作り出せるものであるため、受信装置はこれらを安全に保持する。
【００５３】
以下、上述したＳＤ方式を基礎としたＬＳＤ（ Ｂａｓｉｃ Ｌａｙｅｒｅｄ Ｓｕｂｓｅｔ Ｄｉｆｆｅｒｅｎｃｅ）方式を説明する。
ＬＳＤ方式には、Ｂａｓｉｃ（基本）方式と、その拡張であるＧｅｎｅｒａｌ（一般化）方式がある。ここではＢａｓｉｃ方式について説明する。
ＬＳＤ方式はＳＤ方式の拡張であり、レイヤという新たな概念を取り入れたものである。ＳＤ方式における木構造の中で、特定の高さを特別レベル（Ｓｐｅｃｉａｌ Ｌｅｖｅｌ）として定義する。
Ｂａｓｉｃ＿ＬＳＤ方式においては特別ラベルは１種類だけであるが、Ｇｅｎｅｒａｌ＿ＬＳＤ方式においては重要度の異なる複数の特別レベルを用いる。
ここで、簡単のため、ｌｏｇ^１／２ Ｎを整数であるとする。
Ｂａｓｉｃ＿ＬＳＤ方式では、図１４に示すように、ツリーのルートからリーフに至るまでのそれぞれのレベル（階）のうち、ルートとリーフのレベルを含む、ｌｏｇ^１／２ Ｎごとのレベルを特別レイヤとする。
そして、隣り合う２つの特別レイヤに挟まれた階層（両方の特別レベルを含む）を、レイヤと呼ぶ。
図１４の例では、ルートのレベル、ノードｋを含むレベル、リーフのレベルが特別レベルであり、ルートのレベルとノードｉを含むレベルとノードｋを含むレベルが１つのレイヤを構成する。またノードｋを含むレベルとノードｊを含むレベルとリーフを含むレベルが別のレイヤを構成する。
【００５４】
Ｂａｓｉｃ＿ＬＳＤ方式においては、ＳＤ方式において定義されたサブセットＳ（ｉ，ｊ）のうち、ノードｉとノードｊが同一レイヤにあるか、もしくはノードｉが特別レベルにあるものだけを定義する。
このようにすると、ＳＤ方式において用いられたサブセットのうちのいくつかはＢａｓｉｃ＿ＬＳＤ方式では定義されなくなるが、このサブセットはＢａｓｉｃ＿ＬＳＤ方式で定義されたサブセットの高々２つの和集合で表すことができる。
例えば、図１４の例では、サブセットＳ（ｉ，ｊ）はＢａｓｉｃ＿ＬＳＤ方式では定義されないが、ノードｉからノードｊへのパス上の、ノードｉに最も近い特別レベル上のノード（ノードｋ）を用いて、Ｓ（ｉ，ｊ）＝Ｓ（ｉ，ｋ）∪Ｓ（ｋ，ｊ）と表すことができる。
つまり、ＳＤ方式においてはサブセットＳ（ｉ，ｊ）に対応するサブセットキーＳｋ（ｉ，ｊ）を用いて暗号化した１つの暗号文の代わりに、Ｂａｓｉｃ＿ＬＳＤ方式においてはサブセットＳ（ｉ，ｋ）とＳ（ｋ，ｊ）に対応するサブセットキーＳｋ（ｉ，ｋ），ＳＫ（ｋ，ｊ）を用いて暗号化した２つの暗号文を送信する。
これにより、送信される暗号文の数はＳＤ方式の高々２倍に増加するが、各受信機が保持するラベルの数を減らすことができる。
【００５５】
図１５に、図１３のＳＤ方式で想定したのと同じ場合においてＢａｓｉｃ＿ＬＳＤ方式を適用した場合を説明する。
図１５に示す受信装置ｕ４は、ｉ，ｊが同一レイヤにあるか、ｉが特別レベルにあるラベルデータＬＡＢＥＬ（ｉ，ｊ）のみ保持すればよい。
すなわち、受信装置ｕ４が保持するラベルデータＬＡＢＥＬは、ラベルデータＬＡＢＥＬ（１，３），（１，５），（１，８），（１，１８），（２，５），（４，８），（４，１８），（９，１８）となる。
さらに、ＳＤ方式と同様に、リボークする受信機がない場合に用いる特別なラベルも保持する必要がある。
【００５６】
以下、図２に示す鍵管理装置３の動作例を説明する。
鍵管理装置３の動作は、上述したように、プログラムＰＲＧ１を基にした処理部１３の処理により実現される。
〔前処理の動作例〕
図１６は、鍵管理装置３が上述した前処理を行う場合の動作例を説明するためのフローチャートである。
前述したように、鍵管理装置３の処理部１３は、リボケーション処理に先立って、例えば、受信装置４＿１〜４＿Ｎの登録時などに、以下に示す前処理を行う。
【００５７】
ステップＳＴ１１：
鍵管理装置３は、上述した鍵取得方法ＳＫＴのうち、鍵取得方法ＳＫＴ−ＡおよびＳＫＴ−Ｂを、受信装置のリボケーション処理に使用する鍵取得方法として規定する。
ステップＳＴ１２：
鍵管理装置３は、鍵取得方法ＳＫＴ−ＡおよびＳＫＴ−ＡＴ、並びに鍵取得方法ＳＫＴ−ＡおよびＳＫＴ−Ｂで使用する鍵データＫ＿ＯＲＧおよびラベルデータＬＡＢＥＬを受信装置４＿１〜４＿Ｎに設定する。
具体的には、鍵管理装置３は、受信装置４＿１〜４＿Ｎの各々に、図５に示す鍵取得方法ＳＫＴ−Ａにおける水平レイヤＡ０内の当該受信装置が属するサブツリー内の他の何れの受信装置が無効にされる場合でも、当該サブツリー内の無効にされない受信装置のみを要素とする集合が存在するように規定された複数の集合にそれぞれ割り当てられた複数のラベルデータＬＡＢＥＬを取得するためのラベルデータＬＡＢＥＬを設定する。
また、鍵管理装置３は、受信装置４＿１〜４＿Ｎの各々に、図５に示す水平レイヤＡ１内の当該受信装置に対応する最終端のノードと前記ルートとの間のパス上に位置する全てのノードにそれぞれ割り当てられた複数の鍵データＫ＿ＯＲＧを設定する。
【００５８】
また、鍵管理装置３は、受信装置４＿１〜４＿Ｎの各々に、図６に示す鍵取得方法ＳＫＴ−Ｂにおける水平レイヤＢ０内の当該受信装置が属するサブツリー内の他の何れの受信装置が無効にされる場合でも、当該サブツリー内の無効にされない受信装置のみを要素とする集合が存在するように規定された複数の集合にそれぞれ割り当てられた複数のラベルデータＬＡＢＥＬを取得するためのラベルデータＬＡＢＥＬを設定する。
また、鍵管理装置３は、受信装置４＿１〜４＿Ｎの各々に、図６に示す水平レイヤＢ１内の何れのサブツリー内がその分岐先に無効にされる受信装置を含む場合でも、当該サブツリー内の無効にされない受信装置のみを分岐先に含む最終端のノードのみを要素とする集合が存在するように規定された複数の集合にそれぞれ割り当てられた複数のラベルデータＬＡＢＥＬを取得するためのラベルデータＬＡＢＥＬを設定する。
また、鍵管理装置３は、受信装置４＿１〜４＿Ｎの各々に、図６に示す水平レイヤＢ２内の当該受信装置に対応する最終端のノードと前記ルートとの間のパス上に位置する全てのノードにそれぞれ割り当てられた複数の鍵データＫ＿ＯＲＧを設定する。
鍵管理装置３は、例えば、受信装置４＿１〜４＿Ｎの発行あるいは登録時に、受信装置４＿１〜４＿Ｎに対して個別に上記設定をセキュアな状態で行う。
【００５９】
〔リボケーション処理の動作例〕
図１７および図１８は、鍵管理装置３が上述したリボケーション処理を行う場合の動作例を説明するためのフローチャートである。
図１７に示すステップＳＴ２２，ＳＴ２３が第１の発明の第１の工程に対応し、図１７に示すステップＳＴ２４，ＳＴ２５が第１の発明の第２の工程に対応している。
また、第３の発明の第１の手段は処理部１３がステップＳＴ２２，ＳＴ２３を実行することで実現され、第３の発明の第２の手段は処理部１３がステップＳＴ２４，ＳＴ２５を実行することで実現される。
鍵管理装置３の処理部１３は、受信装置４＿１〜４＿Ｎのうち何れかをリボークする場合に、当該リボケーション処理を行う。
【００６０】
ステップＳＴ２１：
鍵管理装置３は、受信装置４＿１〜４＿Ｎのうちリボークする受信装置を示すリボケーションリストＲＬを生成する。
ステップＳＴ２２：
鍵管理装置３は、リボケーションリストＲＬを基に、上述した鍵取得方法ＳＫＴ−ＡおよびＳＫＴ−Ｂの各々について、当該鍵取得方法を採用した場合に、鍵管理装置３とリボークしない受信装置４＿１〜４＿Ｎとの間に生じる通信量を特定する。
ステップＳＴ２３：
鍵管理装置３は、ステップＳＴ２２で特定した鍵取得方法ＳＫＴ−Ａを採用した場合の通信量が、鍵取得方法ＳＫＴ−Ｂを採用した場合の通信量以上であるか否かを判断する。
鍵管理装置３は、ステップＳＴ２２で特定した鍵取得方法ＳＫＴ−Ａを採用した場合の通信量が鍵取得方法ＳＫＴ−Ｂを採用した場合の通信量以上であると判断すると鍵取得方法ＳＫＴ−Ａを選択してステップＳＴ２４に進み、そうでない場合には鍵取得方法ＳＫＴ−Ｂを選択してステップＳＴ２５に進む。
【００６１】
ステップＳＴ２４：
鍵管理装置３は、ステップＳＴ２１で生成したリボケーションリストＲＬを基に、リボークしない受信装置４＿１〜４＿Ｎとの間の通信に用いる鍵暗号鍵データＫＥＫｍを、鍵取得方法ＳＫＴ−Ａに従って特定する。
当該処理については、後に詳細に説明する。
ステップＳＴ２５：
鍵管理装置３は、ステップＳＴ２１で生成したリボケーションリストＲＬを基に、リボークしない受信装置４＿１〜４＿Ｎとの間の通信に用いる鍵暗号鍵データＫＥＫｍを、鍵取得方法ＳＫＴ−Ｂに従って特定する。
当該処理については、後に詳細に説明する。
【００６２】
ステップＳＴ２６：
鍵管理装置３は、図１９に示すように、ステップＳＴ２４あるいはＳＴ２５で特定した鍵暗号鍵データＫＥＫｍの生成に用いる鍵データＫ＿ＯＲＧおよびラベルデータＬＡＢＥＬを指定した鍵指定データＫＩＤｍと、ステップＳＴ２３で選択した鍵取得方法を指定する鍵取得方法指定データＫＯＩＤｍとを含む指定データＩｍ（本発明の指定データ）を生成する。
なお、鍵指定データＫＩＤｍにおける鍵データＫ＿ＯＲＧおよびラベルデータＬＡＢＥＬの指定は、鍵データＫ＿ＯＲＧおよびラベルデータＬＡＢＥＬに割り当てられたインデックスなどの識別データを基に行い、鍵データＫ＿ＯＲＧおよびラベルデータＬＡＢＥＬ自体は含めない。
【００６３】
ステップＳＴ２７：
鍵管理装置３は、新たな（更新後の）セッション鍵データＮＥＷ＿ＳＥＫを、ステップＳＴ２４あるいはＳＴ２５で生成した鍵暗号鍵データＫＥＫｍで暗号化してデータＥ_ＫＥＫｍ（ＮＥＷ＿ＳＥＫ）を生成する。
ステップＳＴ２８：
鍵管理装置３は、受信装置４＿１〜４＿Ｎに提供する秘密情報であるペイロードデータＰＡＹＬを、新たなセッション鍵データＮＥＷ＿ＳＥＫを用いて暗号化してデータＥ_ＮＥＷ ＿_ＳＥＫ （ＰＡＹＬ）を生成する。
ステップＳＴ２９：
鍵管理装置３は、ステップＳＴ２６で生成した指定データＩｍ（Ｉ_１ 〜Ｉ_Ｍ ）と、ステップＳＴ２７で生成したデータＥ_ＫＥＫｍ（ＮＥＷ＿ＳＥＫ）と、ステップＳＴ２８で生成したＥ_ＮＥＷ ＿_ＳＥＫ （ＰＡＹＬ）とを格納したデータである図２０に示すカプセルデータＣＡＰを生成する。
ステップＳＴ３０：
鍵管理装置３は、ステップＳＴ２９で生成したカプセルデータＣＡＰを、図２に示す通信部１１を介して、例えば、無線方式で放送（送信）する。
当該放送は、いわゆるＰＵＳＨ配信である。
なお、本実施形態における通信量は、ステップＳＴ３０における送信による通信に応じて決まり、前述したように、鍵取得方法ＳＫＴ−ＡとＳＫＴ−Ｂのうちより通信量が少ない方が採用される。
【００６４】
以下、図１７に示すステップＳＴ２４、すなわち、鍵取得方法ＳＫＴ−Ａを採用した場合の鍵暗号鍵データＫＥＫｍの生成方法について詳細に説明する。
図２１は、図１７に示すステップＳＴ２４、すなわち鍵取得方法ＳＫＴ−Ａを基にした鍵暗号鍵データＫＥＫの生成方法を説明するための図である。
【００６５】
ステップＳＴ３１：
鍵管理装置３は、図５に示す水平レイヤＡ０に属するサブツリー（ＳＵＢＴ）のうちリボークする受信装置を含む全てのサブツリーの各々に対して、当該サブツリーに属する受信装置を各々が要素とする予め規定された複数の集合のなかから、当該サブツリー内の無効にされない受信装置のみを要素とする集合を特定する。
【００６６】
ステップＳＴ３２：
鍵管理装置３は、図５に示す水平レイヤＡ１内の最終端のノードのうち、当該ノードの分岐先に無効にする受信装置が存在しないノードを特定する。
【００６７】
ステップＳＴ３３：
鍵管理装置３は、ステップＳＴ３２で特定した全てのノードに対して、当該ノードとルートとの間のパス上に位置するノードのなかで、当該ノードから分岐した前記リーフに無効にする前記受信装置が無く、かつルートに最も近いノードを特定する。
【００６８】
ステップＳＴ３４：
鍵管理装置３は、ステップＳＴ３１で特定した集合（あるいはそのラベルデータＬＡＢＥＬ）に対応付けられた鍵暗号鍵データＫＥＫｍを、当該集合の要素である受信装置４＿１〜４＿Ｎとの間の通信に使用することを決定する。
鍵管理装置３は、例えば、図５に示す水平レイヤＡ０内の全てのサブセットの上記集合と鍵暗号鍵データＫＥＫｍとを対応付けて保持し、ステップＳＴ３１で特定した集合に対応する鍵暗号鍵データＫＥＫを特定する。
また、鍵管理装置３は、例えば、図５に示す水平レイヤＡ０内の上述した集合であるサブセットＳ（ｉ，ｊ）のうち、ノードｉとノードｊが同一レイヤにあるか、もしくはノードｉが特別レベルにあるものに対応するラベルデータＬＡＢＥＬ（ｉ，ｊ）を保持し、これを基に、図１０〜図１４を用いて説明した方法でラベルデータＬＡＢＥＬを生成し、このラベルデータＬＡＢＥＬを基にそのサブセットキーである鍵暗号鍵データＫＥＫｍを生成してもよい。
そして、鍵管理装置３は、上記特定（生成）した鍵暗号鍵データＫＥＫｍを、上記特定した集合の要素である受信装置４＿１〜４＿Ｎが生成するために用いるラベルデータＬＡＢＥＬを指定する鍵・ラベル指定データＫＩＤｍを含む指定データＩｍを生成する。
【００６９】
ステップＳＴ３５：
鍵管理装置３は、ステップＳＴ３３で特定したノードに対応する鍵データＫ＿ＯＲＧ（ノードキー）を鍵暗号鍵データＫＥＫｍとして、当該ノードの分岐先の受信装置４＿１〜４＿Ｎとの通信に使うことを決定する。
そして、鍵管理装置３は、上記決定した鍵暗号鍵データＫＥＫｍである鍵データＫ＿ＯＲＧを指定する鍵指定データＫＩＤｍを含む指定データＩｍを生成する。
【００７０】
以下、図１７に示すステップＳＴ２５、すなわち、鍵取得方法ＳＫＴ−Ｂを採用した場合の鍵暗号鍵データＫＥＫｍの生成方法について詳細に説明する。
図２２は、図１７に示すステップＳＴ２５、すなわち鍵取得方法ＳＫＴ−Ｂを基にした鍵暗号鍵データＫＥＫの生成方法を説明するための図である。
【００７１】
ステップＳＴ４１：
鍵管理装置３は、図６に示す水平レイヤＢ０に属するサブツリー（ＳＵＢＴ）のうちリボークする受信装置を含む全てのサブツリーの各々に対して、当該サブツリーに属する受信装置を各々が要素とする予め規定された複数の集合のなかから、当該サブツリー内の無効にされない受信装置のみを要素とする集合を特定する。
【００７２】
ステップＳＴ４２：
鍵管理装置３は、図６に示す水平レイヤＢ１に属するサブツリー（ＳＵＢＴ）に対して、当該サブツリー内の最終端のノードのうち分岐先に無効にしない受信装置のみを含むノードのみを要素とする集合を特定する。
ステップＳＴ４３：
鍵管理装置３は、図６に示す水平レイヤＢ２内の最終端のノードのうち、当該ノードの分岐先に無効にする受信装置が存在しないノードを特定する。
【００７３】
ステップＳＴ４４：
鍵管理装置３は、ステップＳＴ４３で特定した全てのノードに対して、当該ノードとルートとの間のパス上に位置するノードのなかで、当該ノードから分岐した前記リーフに無効にする前記受信装置が無く、かつルートに最も近いノードを特定する。
【００７４】
ステップＳＴ４５：
鍵管理装置３は、ステップＳＴ４１で特定した集合（あるいはそのラベルデータＬＡＢＥＬ）に対応付けられた鍵暗号鍵データＫＥＫｍを、当該集合の要素である受信装置との間の通信に使用することを決定する。
鍵管理装置３は、例えば、図６に示す水平レイヤＢ０内の全てのサブセットの上記集合と鍵暗号鍵データＫＥＫｍとを対応付けて保持し、ステップＳＴ４１で特定した集合に対応する鍵暗号鍵データＫＥＫを特定する。
また、鍵管理装置３は、例えば、図６に示す水平レイヤＢ０内の上述した集合であるサブセットＳ（ｉ，ｊ）のうち、ノードｉとノードｊが同一レイヤにあるか、もしくはノードｉが特別レベルにあるものに対応するラベルデータＬＡＢＥＬ（ｉ，ｊ）を保持し、これを基に、図１０〜図１５を用いて説明した方法でラベルデータＬＡＢＥＬを生成し、このラベルデータＬＡＢＥＬを基にそのサブセットキーである鍵暗号鍵データＫＥＫｍを生成してもよい。
そして、鍵管理装置３は、上記特定（生成）した鍵暗号鍵データＫＥＫｍを、上記特定した集合の要素である受信装置４＿１〜４＿Ｎが生成するために用いるラベルデータＬＡＢＥＬを指定する鍵・ラベル指定データＫＩＤｍを含む指定データＩｍを生成する。
【００７５】
ステップＳＴ４６：
鍵管理装置３は、ステップＳＴ４２で特定した集合（あるいはそのラベルデータＬＡＢＥＬ）に対応付けられた鍵暗号鍵データＫＥＫｍを、当該集合の要素である受信装置との間の通信に使用することを決定する。
当該鍵暗号鍵データＫＥＫの決定（生成）方法は、ステップＳＴ４５と同様である。
そして、鍵管理装置３は、上記特定（生成）した鍵暗号鍵データＫＥＫｍを、上記特定した集合の要素である受信装置４＿１〜４＿Ｎが生成するために用いるラベルデータＬＡＢＥＬを指定する鍵・ラベル指定データＫＩＤｍを含む指定データＩｍを生成する。
ステップＳＴ４７：
鍵管理装置３は、ステップＳＴ４４で特定したノードに対応する鍵データＫ＿ＯＲＧ（ノードキー）を鍵暗号鍵データＫＥＫｍとして、当該ノードの分岐先の受信装置１０４＿１〜１０４＿Ｎとの通信に使うことを決定する。
そして、鍵管理装置３は、上記決定した鍵暗号鍵データＫＥＫｍである鍵データＫ＿ＯＲＧを指定する鍵・ラベル指定データＫＩＤｍを含む指定データＩｍを生成する。
【００７６】
〔受信装置４＿１〜４＿Ｎ〕
受信装置４＿１〜４＿Ｎは、例えば、ＰＤＡ（Ｐｅｒｓｏｎａｌ Ｄｉｇｉｔａｌ Ａｓｓｉｓｔａｎｔ）や携帯電話などのユビキタスな端末装置である。
図２３は、図１に示す受信装置４＿１〜４＿Ｎのハードウェア構成図である。
受信装置４＿１〜４＿Ｎは、メモリ４２に記憶する鍵データＫ＿ＯＲＧおよびラベルデータＬＡＢＥＬを除いて同じ構成を有している。
図２３に示すように、受信装置４＿１〜４＿Ｎは、例えば、通信部４１、メモリ４２および処理部４３を有する。
ここで、通信部４１が第６の発明の第１の手段に対応し、処理部４３が第６の発明の第２の手段に対応している。
【００７７】
通信部４１は、鍵管理装置３がＰＵＳＨ方式で送信した前述したカプセルデータＣＡＰを無線方式で受信する。
メモリ４２は、処理部４３によって実行されるプログラムＰＲＧ２（第５の発明のプログラム）と、プログラムＰＲＧ２の実行に用いられる種々データを記憶する。
プログラムＰＲＧ２は、前述した鍵取得方法ＳＫＴ−ＡおよびＳＫＴ−Ｂの処理手順を含んでいる。
メモリ４２は、鍵管理装置３による前述した前処理によって、受信装置４＿１〜４＿Ｎの各々に割り当てられた鍵データＫ＿ＯＲＧおよびラベルデータＬＡＢＥＬを記憶する。
具体的には、メモリ４２は、図５に示す鍵取得方法ＳＫＴ−Ａの水平レイヤＡ０内の当該受信装置が属するサブツリー内の他の何れの受信装置が無効にされる場合でも、当該サブツリー内の無効にされない前記受信装置のみを要素とする集合が存在するように規定された複数の集合にそれぞれ割り当てられた複数のラベルデータＬＡＢＥＬを取得するためのラベルデータＬＡＢＥＬを記憶する。
また、メモリ４２は、図５に示す鍵取得方法ＳＫＴ−Ａの水平レイヤＡ１内の当該受信装置に対応する最終端のノードと前記ルートとの間のパス上に位置する全てのノードにそれぞれ割り当てられた複数の鍵データＫ＿ＯＲＧを記憶する。
【００７８】
また、メモリ４２は、図６に示す鍵取得方法ＳＫＴ−Ｂの水平レイヤＢ０内の当該受信装置が属するサブツリー内の他の何れの受信装置が無効にされる場合でも、当該サブツリー内の無効にされない受信装置のみを要素とする集合が存在するように規定された複数の集合にそれぞれ割り当てられた複数のラベルデータＬＡＢＥＬを取得するためのラベルデータＬＡＢＥＬを記憶する。
また、メモリ４２は、図６に示す水平レイヤＢ１内の何れのサブツリー内がその分岐先に無効にされる受信装置を含む場合でも、当該サブツリー内の無効にされない受信装置のみを分岐先に含む最終端のノードのみを要素とする集合が存在するように規定された複数の集合にそれぞれ割り当てられた複数のラベルデータＬＡＢＥＬを取得するためのラベルデータＬＡＢＥＬを記憶する。
また、メモリ４２は、図６に示す水平レイヤＢ２内の当該受信装置に対応する最終端のノードと前記ルートとの間のパス上に位置する全てのノードにそれぞれ割り当てられた複数の鍵データＫ＿ＯＲＧを記憶する。
【００７９】
ここで、メモリ４２が記憶する鍵データＫ＿ＯＲＧおよびラベルデータＬＡＢＥＬのデータ量はオーダＯ（ＳＴ）は、下記式（４）で示される。

【００８０】
処理部４３は、メモリ４２に記憶されたプログラムＰＲＧ２を実行し、その実行に応じて受信装置４＿１〜４＿Ｎの処理を統括して制御する。本実施形態において、受信装置４＿１〜４＿Ｎの処理は、処理部４３が実行するプログラムＰＲＧ２によって規定される。
プログラムＰＲＧ２によって規定される処理部４３の機能は、受信装置４＿１〜４＿Ｎもユーザからは制御できないように構成されている。また、受信装置４＿１〜４＿Ｎのユーザは、これらの機能を全く意識せずに受信装置４＿１〜４＿Ｎを使用する。
【００８１】
以下、受信装置４＿１〜４＿Ｎの動作例を説明する。
図２４は、受信装置４＿１〜４＿Ｎの動作例を説明するためのフローチャートである。
なお、受信装置４＿１〜４＿Ｎの動作は、処理部４３がプログラムＰＲＧ２を実行することで規定される。
図２４において、ステップＳＴ５１が第４の発明の第１の工程に対応し、ステップＳＴ５５，ＳＴ５６が第４の発明の第２の工程に対応している。
【００８２】
ステップＳＴ５１：
受信装置４＿１〜４＿Ｎの通信部４１が、図１８に示すステップＳＴ３０において鍵管理装置３が放送したカプセルデーダＣＡＰを受信する。
ステップＳＴ５２：
受信装置４＿１〜４＿Ｎの処理部４３が、ステップＳＴ５１で受信したカプセルデータＣＡＰ内に、自らに対応する鍵指定データＩｍが含まれているか否かを判断し、含まれていると判断するとステップＳＴ５３の処理に進み、そうでない場合には処理を終了する。
【００８３】
ステップＳＴ５３：
処理部４３は、カプセルデータＣＡＰ内に、自らに対応する指定データＩｍを取得する。
ステップＳＴ５４：
処理部４３は、メモリ４２が記憶する鍵データＫ＿ＯＲＧおよびラベルデータＬＡＢＥＬのなかから、ステップＳＴ５２で取得した指定データＩｍ内の鍵・ラベル指定データＫＩＤｍが指定する鍵データＫ＿ＯＲＧｍあるいはラベルデータＬＡＢＥＬｍを特定する。
【００８４】
ステップＳＴ５５：
処理部４３は、ステップＳＴ５３で取得した指定データＩｍ内の鍵取得方法指定データＫＯＩＤｍが鍵取得方法ＳＫＴ−ＡとＳＫＴ−Ｂのうち何れを指定しているかを特定する。
ステップＳＴ５６：
処理部４３は、ステップＳＴ５４で特定した鍵データＫ＿ＯＲＧｍあるいはラベルデータＬＡＢＥＬｍを基に、ステップＳＴ５５で特定した鍵取得方法ＳＫＴ−ＡあるいはＳＫＴ−Ｂを基に鍵暗号鍵データＫＥＫｍを取得（生成）する。
当該ステップＳＴ５６の処理については、後に詳細に説明する。
【００８５】
ステップＳＴ５７：
処理部４３は、ステップＳＴ５７で取得（生成）した鍵暗号鍵データＫＥＫｍを用いて、カプセルデータＣＡＰ内のデータＥ_ＫＥＫｍ（ＮＥＷ＿ＳＥＫ）を復号して新たなセッション鍵データＮＥＷ＿ＳＥＫを取得する。
ステップＳＴ５８：
処理部４３は、カプセルデータＣＡＰ内のデータＥ_ＮＥＷ ＿_ＳＥＫ （ＰＡＹＬ）を、ステップＳＴ５７で取得した新たなセッション鍵データＮＥＷ＿ＳＥＫを用いて復号してパイロードデータＰＡＹＬを取得する。
【００８６】
受信装置４＿１〜４＿Ｎは、以後、次にリボケーション処理を行うまで、管理装置３から受信したデータを復号するために、ステップＳＴ５７で取得したセッション鍵データＮＥＷ＿ＳＥＫを使用する。
【００８７】
以下、図２４に示すステップＳＴ５６の処理を説明する。
図２５は、図２４に示すステップＳＴ５６の処理を説明するためのフローチャートである。
ステップＳＴ６１：
処理部４３は、図２４に示す前述したステップＳＴ５４でラベルデータＬＡＢＥＬｍを特定したか否かを判断し、ラベルデータＬＡＢＥＬｍを特定したと判断するとステップＳＴ６２に進み、鍵データＫ＿ＯＲＧｍを特定したと判断するとステップＳＴ６６に進む。
【００８８】
ステップＳＴ６２：
処理部４３は、ステップＳＴ５４で特定したラベルデータＬＡＢＥＬｍの生成に必要なラベルデータＬＡＢＥＬを、メモリ４２が記憶（保持）しているか否かを判断し、メモリ４２が記憶していると判断するとステップＳＴ６５に進み、そうでない場合にはステップＳＴ６３に進む。
ステップＳＴ６３：
処理部４３は、鍵指定データＩｍが指定するラベルデータＬＡＢＥＬｍに対応する集合を和集合とする２つの集合に対応するラベルデータＬＡＢＥＬを特定する。
ステップＳＴ６４：
処理部４３は、ステップＳＴ６３で特定した２つのラベルデータＬＡＢＥＬを、必要に応じてメモリ４２に記憶されたラベルデータＬＡＢＥＬを基にそれぞれ生成する。
そして、処理部４３は、当該２つのラベルデータＬＡＢＥＬを、それぞれキーとして疑似乱数発生器Ｇを基に疑似乱数を発生させて、２つのサブセットキーＳＫを生成する。
そして、処理部４３は、当該２つのサブセットキーＳＫを基に鍵暗号鍵データＫＥＫｍを生成する。
【００８９】
ステップＳＴ６５：
処理部４３は、ステップＳＴ５４で特定したラベルデータＬＡＢＥｍを、必要に応じてメモリ４２に記憶されたラベルデータＬＡＢＥＬを基に生成する。
そして、処理部４３は、当該ラベルデータＬＡＢＥＬｍを、キーとして疑似乱数発生器Ｇを基に疑似乱数を発生させて、サブセットキーＳＫを生成する。
そして、処理部４３は、当該サブセットキーＳＫを鍵暗号鍵データＫＥＫｍとする。
【００９０】
ステップＳＴ６６：
処理部４３は、ステップＳＴ５４で特定した鍵データＫ＿ＯＲＧｍを、鍵暗号鍵データＫＥＫｍとする。
【００９１】
以下、通信システム１の全体動作例を説明する。
先ず、鍵管理装置３が、図１６を用いて前述した前処理により、所定の鍵データＫ＿ＯＲＧおよびラベルデータＬＡＢＥＬを受信装置４＿１〜４＿Ｎに配信する。
そして、鍵管理装置３が、所定の受信装置４＿１〜４＿Ｎをリボークする場合に、図１７、図１８、図２１および図２２を用いて前述した手法で、カプセルデータＣＡＰをリボークしない受信装置４＿１〜４＿Ｎに配信する。
そして、受信装置４＿１〜４＿Ｎが、図２４および図２５を用いて説明した処理を行い、リボークしない受信装置４＿１〜４＿Ｎが、新たなセッション鍵データＮＥＷ＿ＳＥＫを基に復号したペイロードデータＰＡＹＬを得る。
【００９２】
以上説明したように、通信システム１では、鍵管理装置３が、予め決められた複数の鍵取得方法（例えば、後述する鍵取得方法ＳＫＴ−Ａ，ＳＫＴ−Ｂなど）のうち、所定の受信装置４＿１〜４＿Ｎをリボーク（無効に）するために生じる、リボークにしない受信装置との間の通信量が最少となる鍵取得方法を選択する。そして、鍵管理装置３が当該選択した鍵取得方法を基に新たな鍵暗号鍵データＫＥＫを取得する。
そのため、通信システム１によれば、リボケーション処理に伴う鍵管理装置３とリボークしない受信装置４＿１〜４＿Ｎとの間の通信量を、前述したＣＳＴ方式に比べて少なくできる。
具体的には、当該通信量は、通信システム１の場合には、前述した式（２）に示すＯ（ＣＯＡ）と式（３）に示すＯ（ＣＯＢ）とのうち少ない方になり、ＬＳＤ方式およびＳＤ方式の場合（Ｏ（Ｒ））よりは多いが、ＣＳＴ方式の場合（Ｏ（Ｒｌｏｇ_２ Ｎ／Ｒ））より少なくできる。
【００９３】
また、通信システム１によれば、受信装置４＿１〜４＿Ｎに記憶される鍵データおよびラベルデータＬＡＢＥＬのデータ量（上記式（４）に示すＯ（ＳＴ））は、ＣＳＴ方式の場合（Ｏ（ｌｏｇ_２ Ｒ））よりは大きいが、ＳＤ方式およびＬＳＤ方式の場合（Ｏ（（ｌｏｇ_２ Ｎ）^２ ），Ｏ（（ｌｏｇ_２ Ｎ）^１＋ａ ），ａ＞１）より少なくできる。
これにより、通信システム１によれば、リボケーション処理に伴う鍵管理装置３と受信装置４＿１〜４＿Ｎとの間の通信量と、受信装置４＿１〜４＿Ｎが保持する鍵データのデータ量とを適切なトレードオフにより規定できる。
【００９４】
また、通信システム１では、受信装置４＿１〜４＿Ｎは、そのユーザが前述した鍵管理などのセキュリティ機能を制御できないように構成されているため、セキュリティ機能を高めることがでる。
また、受信装置４＿１〜４＿Ｎは、鍵管理装置３からの受信（ダウンロード）に、ＳＤＲを採用しているため、権限のある正当な受信装置４＿１〜４＿Ｎのみが、当該受信装置に対して送信されたデータを自動的に受信でき、ダウンロードに伴うセキュリティを高めることができる。
また、ユーザは、これらのセキュリティ機能を全く意識せずに受信装置４＿１〜４＿Ｎを使用できる。
【００９５】
本発明は上述した実施形態には限定されない。
上述した実施形態では、鍵管理装置３と受信装置４＿１〜４＿Ｎとの間の通信を無線方式で行う場合を例示したが、当該通信を有線で行ってもよい。
【００９６】
また、上述した実施形態では、本発明の複数の鍵取得方法として、２つの鍵取得方法ＳＫＴ−Ａ，ＳＫＴ−Ｂを例示したが、鍵取得方法の種類に特に限定されず、また、鍵取得方法の数も複数であれば特に限定されない。
例えば、本発明は、複数の受信装置が割り当てられたリーフを含む第１の水平レイヤに対してＬＳＤあるいはＳＤ方式を適用し、鍵管理装置が割り当てられたルートを含む第２の水平レイヤに対してＣＳＴ方式を採用していれば、上記第１の水平レイヤと上記第２の水平レイヤとの間に、水平レイヤがなくても、単数または複数のレイヤがあってもよく、これらの水平レイヤに適用される鍵取得方法は任意である。
【００９７】
【発明の効果】
以上説明したように、本発明によれば、リボケーション処理に伴う鍵管理元と受信装置との間の通信量と、受信装置が保持する鍵データのデータ量とを適切なトレードオフにより規定したデータ処理方法、そのプログラム、その装置と受信装置を提供することができる。
【図面の簡単な説明】
【図１】図１は、本発明の実施形態に係わる通信システムの全体構成図である。
【図２】図２は、図１に示す鍵管理装置のハードウェア構成図である。
【図３】図３は、本発明の実施形態で採用される鍵取得方法の基礎となるツリー構造を説明するための図である。
【図４】図４は、本発明の実施形態で採用される鍵取得方法の処理を説明するためのフローチャートである。
【図５】図５は、本発明の実施形態で採用される鍵取得方法ＳＫＴ−Ａを説明するための図である。
【図６】図６は、本発明の実施形態で採用される鍵取得方法ＳＫＴ−Ｂを説明するための図である。
【図７】図７は、ＣＳＴ方式を説明するための図である。
【図８】図８は、ＣＳＴ方式を説明するための図である。
【図９】図９は、ＣＳＴ方式を説明するための図である。
【図１０】図１０は、ＳＤ方式を説明するための図である。
【図１１】図１１は、ＳＤ方式を説明するための図である。
【図１２】図１２は、ＳＤ方式を説明するための図である。
【図１３】図１３は、ＳＤ方式を説明するための図である。
【図１４】図１４は、ＬＳＤ方式を説明するための図である。
【図１５】図１５は、ＬＳＤ方式を説明するための図である。
【図１６】図１６は、図１に示す鍵管理装置が行う前処理を説明するためのフローチャートである。
【図１７】図１７は、図１に示す鍵管理装置が行うリボケーション処理を説明するためのフローチャートである。
【図１８】図１８は、図１に示す鍵管理装置が行うリボケーション処理を説明するための図１７の続きのフローチャートである。
【図１９】図１９は、本発明の実施形態の指定データを説明するための図である。
【図２０】図２０は、図１に示す鍵管理装置がリボークしない受信装置に送信するカプセルデータＣＡＰを説明するための図である。
【図２１】図２１は、図１７に示すステップＳＴ２４を説明するためのフローチャートである。
【図２２】図２２は、図１７に示すステップＳＴ２５を説明するためのフローチャートである。
【図２３】図２３は、図１に示す受信装置のハードウェア構成図である。
【図２４】図２４は、図１に示す受信装置の動作例を説明するためのフローチャートである。
【図２５】図２５は、図２４に示すステップＳＴ５６を説明するためのフローチャートである。
【符号の説明】
１…通信システム、３…鍵管理装置、４＿１〜４＿Ｎ…受信装置、１０…バス、１１…通信部、１２…メモリ、１３…処理部、４０…バス、４１…通信部、４２…メモリ、４３…処理部[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a data processing method for performing secure communication, a program therefor, a device therefor, and a receiving device.
[0002]
[Prior art]
In secure communication, usually, a key management device and a receiving device (terminal device) hold or generate the same session key data, and the key management device encrypts the data based on the session key data (hereinafter also referred to as SEK data). To the receiving device.
In such secure communication, for example, secure communication is performed with a plurality of predetermined receiving devices based on common session key data.
In this case, if at least one of the plurality of receiving devices loses the right, the key management device updates the session key data used so far and revokes (invalidates) the receiving device. There is a need to.
[0003]
As such a method of updating session key data (key acquisition method), for example, the methods described in Non-Patent Documents 1 and 2 below are known.
In the key acquisition methods described in Non-Patent Documents 1 and 2 below, a plurality of key data is held in a receiving device in advance, and at the time of updating, the key management device uses any of the plurality of key data to perform secure communication. Is instructed to generate a key encryption key data to be used for non-revoking.
The receiving device that is not revoked selects the instructed key data from the plurality of key data stored in advance, and uses the selected key data to generate a key in a predetermined fixed key generation method. Generate encryption key data.
[0004]
The key management device encrypts the new session key data with the key encryption key data, and transmits the data to the receiving device that does not revoke.
The non-revoked receiving device decrypts the encrypted session key data received from the key management device using the generated key encryption key data to obtain new session key data.
In the above-described key acquisition method, an algorithm is defined so that as many receiving devices as possible can share the same new session key data, that is, to reduce the number of newly used key encryption key data KEK. The amount of communication between the key management device and the receiving device involved in the processing is reduced.
[0005]
[Non-patent document 1]
D. Halevy and A Shamir, "The LCD broadcastcasting scheme", CRYPTO 2002, Lecture Notes in Computer Science, vol. 2442. pp. 47-60, 2002
[Non-patent document 2]
D. Naor, M .; Naor and J.M. Lotspiech, "Revolution and tracing schemes for stateless receivers", CRYPTO 2001. Lecture Notes in Computer Science. vol 2139. pp. 41-62, 2001.
[0006]
[Problems to be solved by the invention]
By the way, of the plurality of key acquisition methods described above, the key acquisition method that minimizes the communication amount involved in the revocation processing differs depending on the number of receiving devices to be revoked, key data assigned to the receiving devices, and the like.
However, conventionally, since the revocation processing method is fixed, there is a problem that the communication amount cannot be sufficiently reduced in some cases.
[0007]
The present invention has been made in view of the above circumstances, and when performing secure communication with a plurality of receiving devices, the communication between a key management source and a receiving device caused by disabling some of the receiving devices. It is an object of the present invention to provide a data processing method, a program thereof, a device thereof, and a receiving device capable of reducing the communication traffic of the communication compared with the conventional one.
[0008]
[Means for Solving the Problems]
In order to achieve the object described above, a data processing method according to a first aspect of the present invention performs encrypted communication with a plurality of receiving devices based on predetermined key data, and performs any one of the plurality of receiving devices. A data processing method for a key management source to obtain new key data used for the encrypted communication with the receiving device that is not invalidated when the invalidation is performed. A first step of selecting, from among the acquisition methods, the key acquisition method that minimizes the amount of communication between the key management source that is generated to invalidate a predetermined reception device and the reception device that is not invalidated; And a second step of acquiring the new key data used for the encrypted communication with the receiving device that is not invalidated based on the key acquisition method selected in the first step.
[0009]
The operation of the data processing method of the first invention is as follows.
First, in a first step, of a plurality of predetermined key acquisition methods, a communication amount between the key management source and a non-invalidating receiving device generated for invalidating a predetermined receiving device. The key acquisition method that minimizes the key is selected.
Next, in a second step, new key data used for the encrypted communication with the receiving device that is not invalidated is obtained based on the key obtaining method selected in the first step.
[0010]
According to a second aspect of the present invention, there is provided a program for performing encrypted communication with a plurality of receiving devices based on predetermined key data, and when disabling any one of the plurality of receiving devices, A program for causing a computer to execute a process for a key management source to acquire the new key data used for the encrypted communication with the device, and a predetermined key acquisition method among a plurality of predetermined key acquisition methods. A first procedure for selecting the key acquisition method that minimizes a communication amount between the key management source generated to invalidate the reception apparatus and the reception apparatus that does not invalidate, and the first procedure A second procedure of acquiring the new key data used for the encrypted communication with the receiving apparatus that is not invalidated based on the selected key acquisition method.
[0011]
The data processing device of the third invention performs encrypted communication with a plurality of receiving devices based on predetermined key data, and does not invalidate any of the plurality of receiving devices. A data processing device for performing a process for a key management source to obtain the new key data used for the encrypted communication with the receiving device, wherein a predetermined key acquisition method is selected from a plurality of predetermined key acquisition methods. First means for selecting the key acquisition method that minimizes the amount of communication between the key management source generated to invalidate the receiving device and the non-invalidating receiving device, and the first means And second means for acquiring the new key data used for the encrypted communication with the receiving device which is not invalidated, based on the key acquisition method selected in the above.
[0012]
The operation of the data processing device of the third invention is as follows.
First, the first means is configured to determine, among a plurality of predetermined key acquisition methods, a communication amount between the key management source and a non-invalidating receiving device, which is generated to invalidate a predetermined receiving device. The key acquisition method that minimizes the key is selected.
Next, the second means acquires the new key data used for the encrypted communication with the receiving apparatus which is not invalidated, based on the key acquisition method selected by the first means.
[0013]
A data processing method according to a fourth aspect of the present invention is a data processing method for performing encrypted communication with a key management source based on predetermined key data, and specifies a key acquisition method and data used in the key acquisition method. A first step of receiving the specified data from the key management source, and using the data specified by the specified data received in the first step, based on the key acquisition method specified by the specified data. And a second step of acquiring new key data.
[0014]
The operation of the data processing method according to the fourth invention is as follows.
First, in a first step, designated data specifying a key acquisition method and data used in the key acquisition method is received from the key management source.
Next, in the second step, using the data specified by the specified data received in the first step, the new key data is obtained based on the key obtaining method specified by the specified data. I do.
[0015]
A program according to a fifth aspect of the present invention is a program executed by a computer that performs encrypted communication with a key management source based on predetermined key data, and specifies a key acquisition method and data used in the key acquisition method. A first procedure of receiving the specified data from the key management source, and using the data specified by the specified data received in the first procedure, based on the key acquisition method specified by the specified data. , And obtain the new key data.
[0016]
A receiving device according to a sixth aspect of the present invention is a receiving device that performs encrypted communication with a key management source based on predetermined key data, and specifies a key acquisition method and data used in the key acquisition method. A first means for receiving data from the key management source, and a data acquisition method designated by the designated data using the data designated by the designated data received by the first means. And second means for generating the key data.
[0017]
The operation of the receiving device according to the sixth invention is as follows.
First, the first means receives, from the key management source, designated data specifying a key acquisition method and data used for the key acquisition method.
Next, the second means generates new key data based on the key acquisition method specified by the specified data, using the data specified by the specified data received by the first means. I do.
[0018]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, a communication system according to an embodiment of the present invention will be described.
FIG. 1 is an overall configuration diagram of a communication system 1 according to an embodiment of the present invention.
As illustrated in FIG. 1, the communication system 1 includes, for example, a key management device 3 and a plurality (N) of reception devices 4_1 to 4_N.
Here, the key management device 3 corresponds to the key management source of the present invention and the data processing device of the third invention, and the receiving devices 4_1 to 4_N correspond to the receiving devices of the present invention.
For example, encrypted communication is performed between the key management device 3 and the receiving devices 4_1 to 4_N by a wireless method.
The receiving devices 4_1 to 4_N are registered in the key management device 3 in advance, and hold key data K_ORG and label data LABEL used for encrypted communication with the key management device 3.
[0019]
In the communication system 1, the key management device 3 revokes predetermined reception devices 4_1 to 4_N among a plurality of predetermined key acquisition methods (for example, key acquisition methods SKT-A and SKT-B described below). The key acquisition method that minimizes the amount of communication with the receiving device that does not revoke, which occurs due to invalidation), is selected.
Then, the key management device 3 assigns the key acquisition method designation data designating the selected key acquisition method to each of the non-revoked reception devices among the reception devices 4_1 to 4_N, and the key used for the selected key acquisition method. The designated data (the designated data of the present invention) including the data K_ORG or the key / label designation data designating the label data LABEL is transmitted by, for example, the PUSH method.
The transmission from the key management device 3 to the receiving devices 4_1 to 4_N is realized by, for example, software defined radio (SDR) secure download by SDR.
Then, the non-revoked receiving devices 4_1 to 4_N use the key data K_ORG or the label data LABEL designated by the designated data received from the key management device 3 among the plurality of key data K_ORG and the label data LABEL held by the receiving device. The key encryption key data KEK (new key data of the present invention) is acquired (generated) based on the key acquisition method designated by the key acquisition method designation data.
The key management device 3 encrypts the new session key data NEW_SEK based on the key encryption key data KEK and transmits the encrypted new session key data to the receiving devices 4_1 to 4_N.
The non-revoked receiving devices 4_1 to 4_N decrypt the session key data NEW_SEK based on the obtained key encryption key data KEK.
Thereafter, secure communication between the key management device 3 and the non-revoked receiving devices 4_1 to 4_N is performed based on the session key data NEW_SEK.
[0020]
Hereinafter, the key management device 3 and the receiving devices 4_1 to 4_N shown in FIG. 1 will be described.
[Key management device 3]
FIG. 2 is a hardware configuration diagram of the key management device 3 shown in FIG.
As illustrated in FIG. 2, the key management device 3 includes, for example, a communication unit 11, a memory 12, and a processing unit 13.
The communication unit 11 transmits the data generated by the processing unit 13 by a wireless method. The transmission is performed by software-defined radio (SDR) SDR secure download using, for example, a push (PUSH) method such as broadcasting.
The memory 12 stores a program PRG1 executed by the processing unit 13 and various data used for executing the program PRG1.
Here, the program PRG1 corresponds to the program of the second invention.
For example, the memory 12 stores, for example, all key data K_ORG and label data LABEL held by the receiving devices 4_1 to 4_N.
Further, the memory 12 may store the key encryption key data KEK finally obtained by storing some or all of the key data K_ORG and the label data LABEL.
[0021]
The processing unit 13 executes the program PRG1 stored in the memory 12, and controls the processing of the key management device 3 according to the execution. In the present embodiment, the processing of the key management device 3 is defined by a program PRG1 executed by the processing unit 13.
[0022]
The processing unit 13 performs security such as preprocessing such as distribution of key data K_ORG and label data LABEL to the receiving devices 4_1 to 4_N and revocation processing such as updating of session key data in response to the execution of the program PRG1. Perform processing.
[0023]
The processing unit 13 performs the preprocessing before the revocation processing, for example, at the time of registration of the receiving devices 4_1 to 4_N.
The processing unit 13 uses the key obtaining methods SKT-A and SKT-B (underlying structure) and the key obtaining methods SKT-A and SKT-B used in performing the revocation processing in the preprocessing. The key data K_ORG and the label data LABEL are set in the receiving devices 4_1 to 4_N.
[0024]
The processing unit 13 performs the revocation processing when any of the receiving devices 4_1 to 4_N is revoked (invalidated).
In the revocation process, the processing unit 13 sends the key encryption key data KEK for transmitting the session key data SEK to the non-revoked receiving devices 4_1 to 4_N in accordance with which of the receiving devices 4_1 to 4_N is revoked. select.
Then, the processing unit 13 transmits the designated data for the non-revoked receiving devices 4_1 to 4_N to generate the key encryption key data KEK to the non-revoked receiving devices 4_1 to 4_N.
[0025]
In the present embodiment, the key acquisition methods SKT-A and SKT-B are, for example, the LSD method disclosed in Non-Patent Document 1 and the CST method disclosed in Non-Patent Document 2 as described below. For example, an SKT (Sectioned Key) is defined based on the revocation method for each section, which is a subtree constituting a tree in which a plurality of binary trees are symmetrically combined.
Trees).
The information on the key acquisition methods SKT-A and SKT-B adopted by the processing unit 13 and the key data K_ORG and the label data LABEL used in the key acquisition method are provided to the receiving devices 4_1 to 4_N by the preprocessing.
[0026]
Hereinafter, the key acquisition method SKT of the present embodiment will be described.
In the tree, a plurality of horizontal layers are defined, and each horizontal layer is divided into a plurality of sections.
Each section has a subtree whose root (node) is a leaf (node) of a higher horizontal layer.
Also, for example, sections belonging to the same horizontal layer have the same number of nodes. That is, sections belonging to the same layer have the same subtree.
As a general example, if the tree is divided into K horizontal layers, and the height of each horizontal layer l (1 is an integer from 0 to L-1) is H [l], then 2 ^{H [l-1]} It has leaves. The horizontal layer 1 has the number of sections represented by the following equation (1), and its subtree is 2 ^{H [l-1]} It has leaves.
[0027]
(Equation 1)

[0028]
FIG. 3 shows the structure of the tree 20 when K = 3, H [0] = 2, H [1] = 1, and H [3] = 2.
[0029]
Hereinafter, the key acquisition method of the present embodiment defined based on the tree will be described.
FIG. 4 is a flowchart for explaining the key acquisition method of the present embodiment.
Hereinafter, each step shown in FIG. 4 will be described.
Step ST1:
The processing unit 13 performs, for each of all the sections belonging to the horizontal layer 0 (the lowest layer) of the tree, reception among the receiving apparatuses 4_1 to 4_N assigned to the leaves of the subtree included in the section, the reception to be revoked. Identify the device.
Further, the processing unit 13 substitutes the initial value “0” for l.
[0030]
Step ST2:
The processing unit 13 performs, for each of the sections belonging to the horizontal layer 0 of the tree, a process of revoking the receiving device specified in step ST1 by a revocation method adopted for a subtree included in the section. Do.
That is, the processing unit 13 performs revocation processing based on the adopted revocation (RV) method, and uses the key encryption key used for communication with the non-revoked receiving device among the receiving devices 4_1 to 4_N belonging to the subtree. Data used to determine the data KEK, for example, data indicating the position of a leaf to be revoked is generated.
[0031]
Step ST3:
The processing unit 13 increments l. That is, 1 = l + 1 is calculated.
[0032]
Step ST4:
The processing unit 13 receives, for each of all the sections belonging to the horizontal layer k of the tree, the reception revoked to the lower layer among the leaves (nodes, the root of the horizontal layer 1-1) of the subtree included in the section. The device identifies the leaf where it is, ie the leaf affected by the revoke.
[0033]
Step ST5:
The processing unit 13 performs a process for revoking the leaf specified in step S41 for each of all the sections belonging to the horizontal layer 1 of the tree by the revocation method adopted for the subtree included in the section. .
That is, the processing unit 13 performs revocation processing based on the revocation (RV) method adopted above, and performs communication with a receiving device that is below the leaf that is not affected by the revocation among the leaves belonging to the subtree. It generates data used to determine the key encryption key data KEK to be used, for example, data indicating the position of a node to be revoked.
[0034]
Step ST6:
The processing unit 13 determines whether or not k = K. If it is determined that 1 = L, the processing ends. If not, the processing returns to step ST3.
[0035]
Step ST7:
The processing unit 13 performs key encryption key data used for communication with the non-revoked receiving devices 4_1 to 4_N based on the results of the RV processing performed on all sections belonging to all horizontal layers in steps ST1 to ST6. Generate KEKm.
Here, m is an integer of 1 to M, and M indicates the number of key encryption key data KEK used for communication with all non-revoked receiving devices.
In this case, a plurality of non-revoking receiving devices may use the common key encryption key data KEKm according to the position of the receiving device to be revoked on the tree.
[0036]
Next, key acquisition methods SKT-A and SKT-B, which are key acquisition methods SKT employed in the present embodiment, will be described.
In the key acquisition methods SKT-A and SKT-B, the data amounts of the label data LABEL and the key data K_ORG stored in the receiving devices 4_1 to 4_N are smaller than those of the LSD method disclosed in Non-Patent Document 1 described above. Compared to the CST method disclosed in Non-Patent Document 2, the communication apparatus has a feature that the communication amount between the key management device 3 and the receiving devices 4_1 to 4_N involved in the revocation process is small.
[0037]
First, the key acquisition method SKT-A will be described.
FIG. 5 is a diagram for explaining the key acquisition method SKT-A.
As shown in FIG. 5, in the key acquisition method SKT-A, the tree is divided into two horizontal layers A0 and A1.
Here, the horizontal layer A0 corresponds to the first layer of the present invention, and the horizontal layer A1 corresponds to the second layer of the present invention.
The height of the lowermost horizontal layer A0 is HA [0], and the height of the horizontal layer A1 is (log ₂ N-HA [0]). Here, N indicates the total number of receiving devices 4_1 to 4_N.
Then, the LSD method disclosed in Non-Patent Document 1 is adopted as the revocation method for each section 31 [0] belonging to the horizontal layer A0.
The CST method disclosed in Non-Patent Document 2 is adopted as a revocation method for each section 31 [1] belonging to the horizontal layer A1.
[0038]
Here, in the key acquisition method SKT-A, the revokes of the R receiving devices 4_1 to 4_N determine whether the R _0A Section.
In this case, the dimension of the communication amount between the key management device 3 involved in the revocation and the non-revoked receiving devices 4_1 to 4_N is O (COA) shown in the following equation (2) in the case of the key acquisition method SKT-A. It becomes.
[0039]
(Equation 2)
O (COA) = O (R + R _0A (Log ₂ N-H _0A ) -R _0A log ₂ R _0A )… (2)
[0040]
Next, the key acquisition method SKT-B will be described.
FIG. 6 is a diagram for explaining the key acquisition method SKT-B.
As shown in FIG. 6, in the key acquisition method SKT-B, the tree is divided into three horizontal layers B0, B1, and B2.
Here, the horizontal layer B0 corresponds to the third layer of the present invention, the horizontal layer B1 corresponds to the fourth layer of the present invention, and the horizontal layer B2 corresponds to the fifth layer of the present invention.
[0041]
The height of the lowermost horizontal layer B0 is HB [0], the height of the horizontal layer B1 is HB [1], and the height of the horizontal layer B2 is (log ₂ N-HB [0] -HB [1]).
Then, the LSD method disclosed in Non-Patent Document 1 is adopted as the revocation method for each section 31 [0] belonging to the horizontal layer B0.
Further, the LSD method disclosed in Non-Patent Document 1 is adopted as a revocation method for each section 31 [1] belonging to the horizontal layer B1.
Further, the CST method disclosed in Non-Patent Document 2 is adopted as a revocation method for each section 31 [2] belonging to the horizontal layer B2.
[0042]
Here, in the above-described key acquisition method SKT-B, the revokes of the R receiving devices 4_1 to 4_N determine whether the R of the horizontal layer B1 constituting the tree is revoked. _0B Of the horizontal layer B2 _1B Section.
In this case, the dimension of the communication volume between the key management device 103 involved in the revocation and the non-revoked receiving devices 104_1 to 104_N is O (COB) shown in the following equation (3) in the case of the key acquisition method SKT-B. It becomes.
[0043]
[Equation 3]

[0044]
Hereinafter, the CST method will be described.
7 to 9 are diagrams for explaining the CST method.
In the following description, as shown in FIG. 7, a case where revocation processing is performed on the 16 receiving devices u1 to u16 by the CST method will be exemplified.
In the CST method, "a set of receiving devices assigned to the leaves of the binary tree having the node as the vertex" is defined using each node of the binary tree.
In the example illustrated in FIG. 7, the node i indicates a set including the receiving devices u5 and u6 as elements. Then, a node key (corresponding to the key data K_ORG in SKT-A) is defined for each node.
[0045]
Each receiving device is given a node key assigned to a node on a path from the leaf to which it is assigned to the root of the tree to which the key management device is assigned, and the receiving device secures these node keys to a secure node key. Keep in memory.
As shown in FIG. 8, the receiving device u4 is provided with five node keys assigned to the nodes 1, 2, 4, 9, and 19.
That is, when the total number of receiving devices is N, each receiving device holds logN + 1 node keys.
[0046]
FIG. 9 is a diagram for explaining how secret information (for example, a content key for decrypting encrypted content) is transmitted to a non-revoked receiving device.
Here, it is assumed that the receiving devices u2, u11, and u12 are revoked.
In this case, the node keys assigned to the nodes on the path from the leaf to which the receiving devices u2, u11, and u12 to be revoked are assigned to the root of the tree cannot be used. This is because the use of these node keys allows a receiving device to be revoked to obtain confidential information.
Then, when these nodes and paths are excluded from the tree, one or more subtrees (subtrees) remain.
Efficient and secure secret information is transmitted by encrypting and transmitting the secret information using the node keys assigned to the nodes (nodes 5, 7, 9, 12, and 16 in FIG. 9) closest to the apex of each subtree. Is sent.
The receiving device decrypts the transmitted ciphertext that can be decrypted by itself, that is, the encrypted text that has been encrypted using the node key corresponding to the node on the path from the assigned leaf to the root. To get confidential information.
In the above example, for example, the receiving device u4 holds the node key of the node 9, and uses this to decrypt the encrypted ciphertext.
In the CST method, there is always one ciphertext that can be decrypted by a receiving device that does not revoke.
[0047]
Next, a description will be given of an SD (Subset Difference) method on which the LSD method is based.
10 to 13 are diagrams for explaining the SD method.
As described above, in the CST system, each node of the tree is used to represent "a set of receiving devices assigned to leaves of a subtree having that node as a vertex".
On the other hand, in the SD method, two nodes i and j of the tree (where i is an ancestor of j) are used to calculate from (a set of leaves of a subtree having node i as a vertex) and (node i A set obtained by subtracting a set of leaves of a subtree whose is a vertex).
For example, a set S (i, j) defined by nodes i and j shown in FIG. 10 is obtained by removing the receiving devices u5 and u6 from the set of receiving devices u1 to u8, that is, S (i, j). ) = {U1, u2, u3, u4, u5, u6, u7, u8, u9} − {u5, u6}.
Define such a set for all node sets where node i is an ancestor of node j (ie node j is not the same as node i and node i is on the path from node j to the root). .
Then, label data LABEL is assigned to each set. Also, a predetermined operation is performed based on the label data LABEL (for example, a pseudo-random number is generated using the label data LABEL as a key) to obtain a subset key.
The subset key is used as key encryption key data KEK in communication between the receiving device and the key management device that are members of the set.
In the SD system, the number of sets to which one receiving device belongs is O (N). Therefore, if the key data SK (subset key) is independently assigned to each set (subset), each receiving device becomes O (N). It is necessary to securely hold the label data LABEL corresponding to the (N) subset keys, but this is practically difficult when N is large.
[0048]
Therefore, in the SD system, the number of label data LABEL held by each receiving device is reduced by the method described below.
For example, as shown in FIG. 11A, an internal node (that is, a node that is not a leaf) i is focused on, and a C-bit value S is randomly selected as label data LABEL (i) of the node.
Next, as shown in FIG. 12, a value S of LABEL (i) is input to a pseudo-random number generator G having a C-bit input and a 3C-bit output.
Then, the 3C-bit output from the pseudo-random number generator G is divided into C bits from the left (from the most significant bit side), and _L (S), G _M (S), G _R (S).
[0049]
And G _L (S) is the label data LABEL of the child node on the left side (one side) of the node i, and G _R Let (S) be the label data LABEL of the child node on the right (other) side of node i.
By this processing, for node k which is a child on the left side of node i in FIG. 11, label data LABEL (i, k) of node k when node i is the starting point is LABEL (i, k) = G _L (S). This is T.
Next, T is input to the pseudo-random number generator G, and its output is divided into C bits from the left, and G _L (T), G _M (T), G _R (T) is obtained.
And G _L (T), G _M (T), G _R (T) is the label data LABEL (i, kL) of the child node L on the left side of the node k when the node i is the starting point, and the label data LABEL (i, k) of the node k when the node i is the starting point. ), Label data LABEL (i, kR) of a child node kR on the right side of node k when node i is the starting point.
By repeating this process, labels corresponding to all descendant nodes when the node i is the starting point are created.
[0050]
According to the above definition, the set S (i, i) is an empty set. When the node i is the starting point, the key of the node i is unnecessary, so that LABEL (i) is generated by pseudo-random number generation. G, which is the central part of the output input to the _M (S) is not used.
As shown in FIG. 11A, the value S of the label data LABEL (i) of the node i which is the starting point is determined, and _R (S) becomes the label data LABEL of the child node on the right side of the node i when the node i is the starting point, and the label data LABEL obtained by inputting it to the pseudorandom number generator G _L (S) becomes the label data LABEL of the node j when the node i is the starting point.
This process is performed for all internal nodes i.
[0051]
These processes are performed by the key management device when setting up the system. The pseudo random number generator (or pseudo random number generation function) G is determined and released by the key management device, and by using this, LABEL (i, j) can calculate the labels LABEL (i, n) of all the nodes n that are descendants of the node j when the node i is the starting point, and when the node i is the starting point, The subset key SK (i, n) of the node j and its descendant node n can be calculated.
By doing so, as shown in FIG. 11 (B), a certain receiving apparatus u sets, for each internal node i on the path from the leaf to which it is assigned to the vertex of the tree, starting from the node i. If only the label data LABEL of the node directly branching from the path from the leaf to i is held, the subset key of the node and the subsequent (descendant) nodes starting from the node i Can be created. In FIG. 11B, when attention is paid to the node i, the number of nodes directly branching from the path from u to i is three, and the receiving apparatus u outputs these three label data LABEL at the time of setting up the system. Received from key management device.
[0052]
Hereinafter, in the example shown in FIG. 13, the receiving device u4 will be considered.
With respect to the receiving device u4, the internal nodes 1, 2, 4, 9 on the path from the node 19, which is the leaf to which the receiving device u4 is assigned, to the route 1 are the starting points (node i). Assuming that the node 1 is the starting point, the nodes directly branching from the path from the node 19 to the node 1 are the nodes 3, 5, 8, and 18, and therefore, LABEL (1, 3), (1, 5) , (1, 8) and (1, 18) are held by the receiving device u4.
Similarly, LABEL (2, 5), (2, 8), and (2, 18) three label data LABEL when node 2 is the starting point, and LABEL (4, 8) when node 4 is the starting point. ), (4, 18), and LABEL (9, 18) when the node 9 is the starting point.
Further, one label data LABEL (1) corresponding to a set including all the receiving devices (this is represented as S1 and φ), which is used in a special case where there is no receiving device to be revoked, is held.
However, the label data LABEL corresponding to S (1), φ is used, but the subset key corresponding to S1, Φ may be directly stored instead of the label data LABEL.
As described above, each receiving device needs to hold, for each internal node on the path from the leaf to the root, the label data LABEL corresponding to the height of the internal node.
Since these label data LABEL can generate a subset key by using a publicly available G, the receiving device safely holds them.
[0053]
Hereinafter, an LSD (Basic Layered Subset Difference) method based on the above-described SD method will be described.
The LSD system includes a Basic (basic) system and an extension of the General (generalized) system. Here, the Basic method will be described.
The LSD scheme is an extension of the SD scheme and incorporates a new concept of a layer. In the tree structure in the SD system, a specific height is defined as a special level.
In the Basic_LSD system, there is only one special label, but in the General_LSD system, a plurality of special levels having different degrees of importance are used.
Here, for simplicity, log ^1/2 Let N be an integer.
In the Basic_LSD method, as shown in FIG. 14, of each level (floor) from the root of the tree to the leaf, a log including the level of the root and the leaf is included. ^1/2 The level for each N is a special layer.
Then, a layer sandwiched between two adjacent special layers (including both special levels) is called a layer.
In the example of FIG. 14, the root level, the level including the node k, and the leaf level are the special levels, and the root level, the level including the node i, and the level including the node k constitute one layer. The level including the node k, the level including the node j, and the level including the leaves constitute different layers.
[0054]
In the Basic_LSD method, of the subsets S (i, j) defined in the SD method, only those in which the node i and the node j are on the same layer or the node i is on a special level are defined.
In this way, some of the subsets used in the SD scheme are no longer defined in the Basic_LSD scheme, but this subset can be represented by at most two unions of the subsets defined in the Basic_LSD scheme.
For example, in the example of FIG. 14, although the subset S (i, j) is not defined in the Basic_LSD method, a node (node k) on a special level closest to the node i on the path from the node i to the node j is used. Thus, S (i, j) = S (i, k) ∪S (k, j).
That is, in the SD method, instead of one ciphertext encrypted using the subset key Sk (i, j) corresponding to the subset S (i, j), the subset S (i, k) is used in the Basic_LSD method. Two ciphertexts encrypted using the subset keys Sk (i, k) and SK (k, j) corresponding to S (k, j) are transmitted.
Thereby, the number of ciphertexts to be transmitted increases at most twice that of the SD system, but the number of labels held by each receiver can be reduced.
[0055]
FIG. 15 illustrates a case where the Basic_LSD method is applied in the same case as assumed in the SD method of FIG.
The receiving device u4 shown in FIG. 15 may hold only the label data LABEL (i, j) in which i and j are in the same layer or i is at a special level.
That is, the label data LABEL held by the receiving device u4 is the label data LABEL (1, 3), (1, 5), (1, 8), (1, 18), (2, 5), (4, 8). ), (4, 18), (9, 18).
Further, similarly to the SD system, it is necessary to hold a special label used when there is no receiver to be revoked.
[0056]
Hereinafter, an operation example of the key management device 3 shown in FIG. 2 will be described.
The operation of the key management device 3 is realized by the processing of the processing unit 13 based on the program PRG1, as described above.
[Operation example of preprocessing]
FIG. 16 is a flowchart for explaining an operation example when the key management device 3 performs the above-described preprocessing.
As described above, the processing unit 13 of the key management device 3 performs the following preprocessing before registering the receiving devices 4_1 to 4_N, for example, before the revocation processing.
[0057]
Step ST11:
The key management device 3 defines the key acquisition methods SKT-A and SKT-B among the above-described key acquisition methods SKT as key acquisition methods used for revocation processing of the receiving device.
Step ST12:
The key management device 3 sets the key acquisition methods SKT-A and SKT-AT and the key data K_ORG and label data LABEL used in the key acquisition methods SKT-A and SKT-B in the receiving devices 4_1 to 4_N.
Specifically, the key management device 3 assigns, to each of the receiving devices 4_1 to 4_N, any other receiving device in the subtree to which the receiving device belongs in the horizontal layer A0 in the key acquisition method SKT-A illustrated in FIG. Even if is invalidated, a label for acquiring a plurality of label data LABELs respectively assigned to a plurality of sets defined so that there is a set having only receiving devices in the subtree that are not invalidated. Set the data LABEL.
In addition, the key management device 3 assigns, to each of the receiving devices 4_1 to 4_N, all of the nodes located on the path between the last node corresponding to the receiving device in the horizontal layer A1 shown in FIG. A plurality of key data K_ORG respectively assigned to the nodes are set.
[0058]
In addition, the key management device 3 makes each of the receiving devices 4_1 to 4_N invalidate any other receiving device in the subtree to which the receiving device belongs in the horizontal layer B0 in the key acquisition method SKT-B shown in FIG. Even if the label data LABEL for acquiring a plurality of label data LABELs respectively assigned to a plurality of sets defined so that there is a set including only a receiving device that is not invalidated in the subtree, is set. Set.
Further, the key management device 3 is configured such that, even when each of the receiving devices 4_1 to 4_N includes a receiving device in which the subtree in the horizontal layer B1 shown in FIG. Label data LABEL for acquiring a plurality of label data LABELs respectively assigned to a plurality of sets defined so that there is a set having only the terminal node at the branch end that includes only the receiving device that is not invalidated. Set.
Further, the key management device 3 assigns, to each of the receiving devices 4_1 to 4_N, all of the positions located on the path between the last node and the route in the horizontal layer B2 shown in FIG. A plurality of key data K_ORG respectively assigned to the nodes are set.
The key management device 3 individually performs the above-described setting for the receiving devices 4_1 to 4_N in a secure state when the receiving devices 4_1 to 4_N are issued or registered, for example.
[0059]
[Operation example of revocation processing]
17 and 18 are flowcharts for explaining an operation example when the key management device 3 performs the above-described revocation processing.
Steps ST22 and ST23 shown in FIG. 17 correspond to the first step of the first invention, and steps ST24 and ST25 shown in FIG. 17 correspond to the second step of the first invention.
The first means of the third invention is realized by the processing unit 13 executing steps ST22 and ST23, and the second means of the third invention is that the processing unit 13 executes steps ST24 and ST25. Is realized.
The processing unit 13 of the key management device 3 performs the revocation processing when revoking any of the receiving devices 4_1 to 4_N.
[0060]
Step ST21:
The key management device 3 generates a revocation list RL indicating a revoked receiving device among the receiving devices 4_1 to 4_N.
Step ST22:
The key management device 3, based on the revocation list RL, for each of the above-described key acquisition methods SKT-A and SKT-B, when the key acquisition method is adopted, the reception device 4 </ b> _ <b> 1 that does not revoke the key management device 3 To 4_N.
Step ST23:
The key management device 3 determines whether or not the traffic when the key acquisition method SKT-A specified in step ST22 is adopted is equal to or greater than the traffic when the key acquisition method SKT-B is adopted.
If the key management device 3 determines that the communication amount when the key acquisition method SKT-A specified in step ST22 is adopted is equal to or larger than the communication amount when the key acquisition method SKT-B is adopted, the key acquisition method SKT-A Is selected and the process proceeds to step ST24. Otherwise, the key acquisition method SKT-B is selected and the process proceeds to step ST25.
[0061]
Step ST24:
The key management device 3 specifies key encryption key data KEKm used for communication with the non-revoked receiving devices 4_1 to 4_N based on the revocation list RL generated in step ST21 according to the key acquisition method SKT-A.
This processing will be described later in detail.
Step ST25:
The key management device 3 specifies the key encryption key data KEKm used for communication with the non-revoked receiving devices 4_1 to 4_N based on the revocation list RL generated in step ST21 according to the key acquisition method SKT-B.
This processing will be described later in detail.
[0062]
Step ST26:
As shown in FIG. 19, the key management device 3 selects the key data K_ORG and the label data LABEL used to generate the key encryption key data KEKm specified in step ST24 or ST25, and selects the key specification data KIDm in step ST23. The designated data Im (the designated data of the present invention) including the key acquisition method designation data KOIDm that designates the key acquisition method is generated.
The key data K_ORG and the label data LABEL in the key specification data KIDm are specified based on identification data such as indexes assigned to the key data K_ORG and the label data LABEL, and do not include the key data K_ORG and the label data LABEL itself. .
[0063]
Step ST27:
The key management device 3 encrypts the new (updated) session key data NEW_SEK with the key encryption key data KEKm generated in step ST24 or ST25, and generates data E _KEKm (NEW_SEK) is generated.
Step ST28:
The key management device 3 encrypts the payload data PAYL, which is the secret information provided to the receiving devices 4_1 to 4_N, using the new session key data NEW_SEK, _NEW _ _SEK (PAYL) is generated.
Step ST29:
The key management device 3 specifies the designated data Im (I ₁ ~ I _M ) And the data E generated in step ST27. _KEKm (NEW_SEK) and E generated in step ST28. _NEW _ _SEK (PAYL) is generated as capsule data CAP shown in FIG.
Step ST30:
The key management device 3 broadcasts (transmits) the capsule data CAP generated in step ST29, for example, by a wireless method via the communication unit 11 shown in FIG.
The broadcast is so-called PUSH distribution.
Note that the communication amount in the present embodiment is determined according to the communication by the transmission in step ST30, and as described above, the smaller one of the key acquisition methods SKT-A and SKT-B is adopted.
[0064]
Hereinafter, step ST24 shown in FIG. 17, that is, a method of generating the key encryption key data KEKm when the key acquisition method SKT-A is adopted will be described in detail.
FIG. 21 is a diagram for explaining step ST24 shown in FIG. 17, that is, a method of generating key encryption key data KEK based on the key acquisition method SKT-A.
[0065]
Step ST31:
The key management device 3 determines, for each of the sub-trees (SUBT) belonging to the horizontal layer A0 shown in FIG. 5 including the revoked receiving device, each receiving device belonging to the sub-tree as an element. From among the plurality of sets, a set including only non-invalidated receiving devices in the subtree is specified.
[0066]
Step ST32:
The key management device 3 specifies a node having no receiving device to be invalidated at a branch destination of the node, from among the nodes at the end in the horizontal layer A1 illustrated in FIG.
[0067]
Step ST33:
The key management device 3 makes the receiving device invalidate all the nodes identified in step ST32 among the nodes located on the path between the node and the root, to the leaf branched from the node. And the node closest to the root is specified.
[0068]
Step ST34:
The key management device 3 uses the key encryption key data KEKm associated with the set specified in step ST31 (or the label data LABEL) for communication with the receiving devices 4_1 to 4_N that are elements of the set. To decide.
The key management device 3 holds, for example, the set of all the subsets in the horizontal layer A0 shown in FIG. 5 and the key encryption key data KEKm in association with each other, and stores the key encryption key data corresponding to the set specified in step ST31. Specify KEK.
In addition, for example, in the subset S (i, j), which is the above-described set in the horizontal layer A0 illustrated in FIG. 5, the key management device 3 determines whether the node i and the node j are in the same layer or the node i is The label data LABEL (i, j) corresponding to the data at the special level is held, and based on this, the label data LABEL is generated by the method described with reference to FIGS. 10 to 14, and based on this label data LABEL. Alternatively, key encryption key data KEKm, which is a subset key thereof, may be generated.
Then, the key management device 3 specifies the label (LABEL) used to generate the specified (generated) key encryption key data KEKm by the receiving devices 4_1 to 4_N which are elements of the specified set. The designated data Im including the data KIDm is generated.
[0069]
Step ST35:
The key management device 3 determines that the key data K_ORG (node key) corresponding to the node specified in step ST33 is used as the key encryption key data KEKm for communication with the receiving devices 4_1 to 4_N at the branch destination of the node.
Then, the key management device 3 generates designation data Im including key designation data KIDm that designates the key data K_ORG that is the determined key encryption key data KEKm.
[0070]
Hereinafter, step ST25 shown in FIG. 17, that is, a method of generating key encryption key data KEKm in the case of employing the key acquisition method SKT-B will be described in detail.
FIG. 22 is a diagram for explaining step ST25 shown in FIG. 17, that is, a method for generating key encryption key data KEK based on the key acquisition method SKT-B.
[0071]
Step ST41:
The key management device 3 determines, for each of the subtrees (SUBTs) belonging to the horizontal layer B0 shown in FIG. 6 including the revoking receiving device, the receiving device belonging to the subtree as an element. From among the plurality of sets that have been set, a set that includes only non-invalidated receiving devices in the subtree is specified.
[0072]
Step ST42:
The key management device 3 has, for the subtree (SUBT) belonging to the horizontal layer B1 shown in FIG. 6, only the node that includes only the receiving device that is not invalidated at the branch destination among the nodes at the end of the subtree as elements. Identify the set.
Step ST43:
The key management device 3 specifies a node having no receiving device to be invalidated at the branch destination of the node, from among the nodes at the end in the horizontal layer B2 illustrated in FIG.
[0073]
Step ST44:
The key management device 3 invalidates, for all the nodes specified in step ST43, among the nodes located on the path between the node and the root, the reception device that invalidates the leaf branched from the node. And the node closest to the root is specified.
[0074]
Step ST45:
The key management device 3 decides to use the key encryption key data KEKm associated with the set specified in step ST41 (or the label data LABEL) for communication with the receiving device that is an element of the set. I do.
The key management device 3 holds, for example, the set of all the subsets in the horizontal layer B0 shown in FIG. 6 and the key encryption key data KEKm in association with each other, and stores the key encryption key data corresponding to the set specified in step ST41. Specify KEK.
In addition, for example, in the subset S (i, j), which is the above set in the horizontal layer B0 illustrated in FIG. 6, the key management device 3 determines whether the node i and the node j are in the same layer or the node i is The label data LABEL (i, j) corresponding to the data at the special level is held, and based on this, the label data LABEL is generated by the method described with reference to FIGS. Alternatively, key encryption key data KEKm, which is a subset key thereof, may be generated.
Then, the key management device 3 specifies the label (LABEL) used to generate the specified (generated) key encryption key data KEKm by the receiving devices 4_1 to 4_N which are elements of the specified set. The designated data Im including the data KIDm is generated.
[0075]
Step ST46:
The key management device 3 determines that the key encryption key data KEKm associated with the set specified in step ST42 (or the label data LABEL) is used for communication with the receiving device that is an element of the set. I do.
The method of determining (generating) the key encryption key data KEK is the same as in step ST45.
Then, the key management device 3 specifies the label (LABEL) used to generate the specified (generated) key encryption key data KEKm by the receiving devices 4_1 to 4_N which are elements of the specified set. The designated data Im including the data KIDm is generated.
Step ST47:
The key management device 3 determines that the key data K_ORG (node key) corresponding to the node specified in step ST44 is used as the key encryption key data KEKm for communication with the receiving devices 104_1 to 104_N at the branch destination of the node.
Then, the key management device 3 generates designation data Im including key / label designation data KIDm that designates the key data K_ORG that is the determined key encryption key data KEKm.
[0076]
[Receiving devices 4_1 to 4_N]
The receiving devices 4_1 to 4_N are, for example, ubiquitous terminal devices such as a PDA (Personal Digital Assistant) and a mobile phone.
FIG. 23 is a hardware configuration diagram of the receiving devices 4_1 to 4_N shown in FIG.
The receiving devices 4_1 to 4_N have the same configuration except for the key data K_ORG and the label data LABEL stored in the memory 42.
As illustrated in FIG. 23, the receiving devices 4_1 to 4_N include, for example, a communication unit 41, a memory 42, and a processing unit 43.
Here, the communication unit 41 corresponds to the first means of the sixth invention, and the processing unit 43 corresponds to the second means of the sixth invention.
[0077]
The communication unit 41 receives the above-described capsule data CAP transmitted by the key management device 3 by the PUSH method by a wireless method.
The memory 42 stores a program PRG2 (the program of the fifth invention) executed by the processing unit 43 and various data used for executing the program PRG2.
The program PRG2 includes the processing procedure of the key acquisition methods SKT-A and SKT-B described above.
The memory 42 stores the key data K_ORG and the label data LABEL assigned to each of the receiving devices 4_1 to 4_N by the above-described preprocessing by the key management device 3.
Specifically, even if any other receiving device in the subtree to which the receiving device belongs in the horizontal layer A0 of the key acquisition method SKT-A shown in FIG. The label data LABEL for acquiring a plurality of label data LABELs respectively assigned to a plurality of sets defined so that there is a set including only the receiving device that is not invalidated is stored.
In addition, the memory 42 is assigned to all nodes located on the path between the last node corresponding to the receiving apparatus and the root in the horizontal layer A1 of the key obtaining method SKT-A illustrated in FIG. The stored plurality of key data K_ORG is stored.
[0078]
In addition, even when any other receiving device in the subtree to which the receiving device belongs in the horizontal layer B0 of the key acquisition method SKT-B illustrated in FIG. 6 is invalidated, the memory 42 disables the invalidation in the subtree. Label data LABEL for acquiring a plurality of label data LABELs respectively assigned to a plurality of sets defined such that a set including only receiving devices as elements exists.
Further, even when any of the subtrees in the horizontal layer B1 shown in FIG. 6 includes a receiving device that is invalidated at the branch destination, the memory 42 includes only the receiving device that is not invalidated within the subtree at the branching destination. Label data LABEL for acquiring a plurality of label data LABELs respectively assigned to a plurality of sets defined so that a set having only the last node as an element is stored.
In addition, the memory 42 stores a plurality of key data K_ORGs respectively assigned to all nodes located on a path between the last node and the route in the horizontal layer B2 shown in FIG. Is stored.
[0079]
Here, the data amount of the key data K_ORG and the label data LABEL stored in the memory 42 is of the order O (ST) as shown in the following equation (4).

[0080]
The processing unit 43 executes the program PRG2 stored in the memory 42, and controls the processing of the receiving devices 4_1 to 4_N according to the execution. In the present embodiment, the processing of the receiving devices 4_1 to 4_N is defined by a program PRG2 executed by the processing unit 43.
The function of the processing unit 43 defined by the program PRG2 is configured such that the receiving devices 4_1 to 4_N cannot be controlled by the user. The users of the receiving devices 4_1 to 4_N use the receiving devices 4_1 to 4_N without being conscious of these functions.
[0081]
Hereinafter, an operation example of the receiving devices 4_1 to 4_N will be described.
FIG. 24 is a flowchart for describing an operation example of the receiving devices 4_1 to 4_N.
Note that the operations of the receiving devices 4_1 to 4_N are defined by the processing unit 43 executing the program PRG2.
In FIG. 24, step ST51 corresponds to the first step of the fourth invention, and steps ST55 and ST56 correspond to the second step of the fourth invention.
[0082]
Step ST51:
The communication units 41 of the receiving devices 4_1 to 4_N receive the capsule data CAP broadcasted by the key management device 3 in step ST30 shown in FIG.
Step ST52:
The processing units 43 of the receiving apparatuses 4_1 to 4_N determine whether or not the capsule data CAP received in step ST51 includes the key designation data Im corresponding to the capsule data CAP. Proceeds to the processing of, otherwise ends the processing.
[0083]
Step ST53:
The processing unit 43 acquires the designated data Im corresponding to itself in the capsule data CAP.
Step ST54:
The processing unit 43 specifies the key data K_ORGm or the label data LABELm designated by the key / label designation data KIDm in the designation data Im obtained in step ST52 from the key data K_ORG and the label data LABEL stored in the memory 42. .
[0084]
Step ST55:
The processing unit 43 specifies which of the key acquisition methods SKT-A and SKT-B is specified by the key acquisition method designation data KOIDm in the designation data Im acquired in step ST53.
Step ST56:
The processing unit 43 acquires (generates) the key encryption key data KEKm based on the key acquisition method SKT-A or SKT-B identified in step ST55 based on the key data K_ORGm or the label data LABELm identified in step ST54. .
The process of step ST56 will be described later in detail.
[0085]
Step ST57:
The processing unit 43 uses the key encryption key data KEKm obtained (generated) in step ST57 to store the data E in the capsule data CAP. _KEKm (NEW_SEK) to obtain new session key data NEW_SEK.
Step ST58:
The processing unit 43 stores the data E in the capsule data CAP. _NEW _ _SEK (PAYL) is decrypted using the new session key data NEW_SEK obtained in step ST57 to obtain the payload data PAYL.
[0086]
The receiving devices 4_1 to 4_N thereafter use the session key data NEW_SEK obtained in step ST57 to decrypt the data received from the management device 3 until the next revocation process is performed.
[0087]
Hereinafter, the process of step ST56 shown in FIG. 24 will be described.
FIG. 25 is a flowchart for explaining the process of step ST56 shown in FIG.
Step ST61:
The processing unit 43 determines whether or not the label data LABELm has been specified in the above-described step ST54 shown in FIG. 24, and proceeds to step ST62 when determining that the label data LABELm has been specified. It proceeds to step ST66.
[0088]
Step ST62:
The processing unit 43 determines whether or not the memory 42 stores (holds) the label data LABEL necessary for generating the label data LABELm specified in step ST54, and determines that the memory 42 stores the label data LABEL. The process proceeds to ST65, otherwise proceeds to step ST63.
Step ST63:
The processing unit 43 specifies the label data LABEL corresponding to the two sets whose union is the set corresponding to the label data LABELm specified by the key specification data Im.
Step ST64:
The processing unit 43 generates the two label data LABELs specified in step ST63 based on the label data LABEL stored in the memory 42 as needed.
Then, the processing unit 43 generates a pseudo-random number based on the pseudo-random number generator G using the two label data LABEL as keys, and generates two subset keys SK.
Then, the processing unit 43 generates key encryption key data KEKm based on the two subset keys SK.
[0089]
Step ST65:
The processing unit 43 generates the label data LABem specified in step ST54 based on the label data LABEL stored in the memory 42 as needed.
Then, the processing unit 43 generates a pseudo random number based on the pseudo random number generator G using the label data LABELm as a key, and generates a subset key SK.
Then, the processing unit 43 sets the subset key SK as key encryption key data KEKm.
[0090]
Step ST66:
The processing unit 43 sets the key data K_ORGm specified in step ST54 as key encryption key data KEKm.
[0091]
Hereinafter, an overall operation example of the communication system 1 will be described.
First, the key management device 3 distributes predetermined key data K_ORG and label data LABEL to the receiving devices 4_1 to 4_N by the preprocessing described above with reference to FIG.
Then, when the key management device 3 revokes the predetermined reception devices 4_1 to 4_N, the reception devices 4_1 to 4_1 to revoke the capsule data CAP by the method described above with reference to FIGS. 17, 18, 21 and 22. 4_N.
Then, receiving apparatuses 4_1 to 4_N perform the processing described with reference to FIGS. 24 and 25, and non-revoking receiving apparatuses 4_1 to 4_N obtain payload data PAYL decrypted based on new session key data NEW_SEK.
[0092]
As described above, in the communication system 1, the key management device 3 is configured such that a predetermined receiving device is selected from a plurality of predetermined key obtaining methods (for example, key obtaining methods SKT-A and SKT-B described later). A key acquisition method that minimizes the amount of communication with a non-revoked receiving device, which is generated to revoke (invalidate) 4_1 to 4_N, is selected. Then, the key management device 3 acquires new key encryption key data KEK based on the selected key acquisition method.
Therefore, according to the communication system 1, the communication traffic between the key management device 3 and the non-revoked receiving devices 4_1 to 4_N involved in the revocation process can be reduced as compared with the CST method described above.
Specifically, in the case of the communication system 1, the communication amount is the smaller one of O (COA) shown in the above equation (2) and O (COB) shown in the above equation (3). System and the SD system (O (R)), but the CST system (O (Rlog ₂ N / R)).
[0093]
Further, according to the communication system 1, the data amounts of the key data and the label data LABEL (O (ST) shown in the above equation (4)) stored in the receiving devices 4_1 to 4_N are equal to those of the CST method (O (log)). ₂ R)), but in the case of the SD method and the LSD method (O ((log ₂ N) ² ), O ((log ₂ N) ^{1 + a} ), A> 1).
Thereby, according to the communication system 1, the communication amount between the key management device 3 and the receiving devices 4_1 to 4_N involved in the revocation process and the data amount of the key data held by the receiving devices 4_1 to 4_N are appropriately adjusted. It can be specified by a trade-off.
[0094]
Further, in the communication system 1, the receiving devices 4_1 to 4_N are configured so that the user cannot control the security functions such as the key management described above, so that the security functions can be enhanced.
In addition, since the receiving devices 4_1 to 4_N adopt SDR for receiving (downloading) from the key management device 3, only authorized authorized receiving devices 4_1 to 4_N are transmitted to the receiving devices. Data can be automatically received, and security associated with downloading can be enhanced.
Also, the user can use the receiving devices 4_1 to 4_N without being conscious of these security functions at all.
[0095]
The present invention is not limited to the embodiments described above.
In the above-described embodiment, the case where the communication between the key management device 3 and the receiving devices 4_1 to 4_N is performed by a wireless method is illustrated. However, the communication may be performed by a wire.
[0096]
Further, in the above-described embodiment, two key acquisition methods SKT-A and SKT-B have been exemplified as the plurality of key acquisition methods of the present invention. However, the type of key acquisition method is not particularly limited. There is no particular limitation as long as the number of methods is plural.
For example, the present invention applies the LSD or SD method to a first horizontal layer including a leaf to which a plurality of receiving devices are assigned, and applies a LSD or SD method to a second horizontal layer including a route to which a key management device is assigned. If the CST method is adopted, there may be no horizontal layer or one or more layers between the first horizontal layer and the second horizontal layer. The key acquisition method applied to is arbitrary.
[0097]
【The invention's effect】
As described above, according to the present invention, the communication amount between the key management source and the receiving device involved in the revocation process and the data amount of the key data held by the receiving device are defined by an appropriate trade-off. A data processing method, a program thereof, a device thereof, and a receiving device can be provided.
[Brief description of the drawings]
FIG. 1 is an overall configuration diagram of a communication system according to an embodiment of the present invention.
FIG. 2 is a hardware configuration diagram of the key management device shown in FIG. 1;
FIG. 3 is a diagram for explaining a tree structure serving as a basis of a key acquisition method employed in an embodiment of the present invention.
FIG. 4 is a flowchart for explaining processing of a key acquisition method employed in an embodiment of the present invention.
FIG. 5 is a diagram for explaining a key acquisition method SKT-A employed in the embodiment of the present invention.
FIG. 6 is a diagram for explaining a key acquisition method SKT-B employed in the embodiment of the present invention.
FIG. 7 is a diagram for explaining a CST method.
FIG. 8 is a diagram for explaining a CST method.
FIG. 9 is a diagram for explaining a CST method.
FIG. 10 is a diagram for explaining the SD method.
FIG. 11 is a diagram for explaining the SD method.
FIG. 12 is a diagram for explaining the SD method.
FIG. 13 is a diagram for explaining the SD method.
FIG. 14 is a diagram for explaining the LSD method.
FIG. 15 is a diagram for explaining the LSD method.
FIG. 16 is a flowchart illustrating a pre-process performed by the key management device illustrated in FIG. 1;
FIG. 17 is a flowchart illustrating a revocation process performed by the key management device illustrated in FIG. 1;
FIG. 18 is a flowchart continued from FIG. 17 for explaining revocation processing performed by the key management device shown in FIG. 1;
FIG. 19 is a diagram for describing designated data according to the embodiment of the present invention.
FIG. 20 is a diagram for explaining capsule data CAP transmitted by the key management device shown in FIG. 1 to a non-revoking receiving device.
FIG. 21 is a flowchart illustrating step ST24 shown in FIG. 17;
FIG. 22 is a flowchart illustrating step ST25 shown in FIG. 17;
FIG. 23 is a hardware configuration diagram of the receiving device shown in FIG. 1;
FIG. 24 is a flowchart for explaining an operation example of the receiving apparatus shown in FIG. 1;
FIG. 25 is a flowchart illustrating step ST56 shown in FIG. 24;
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 1 ... Communication system, 3 ... Key management device, 4_1-4_N ... Receiving device, 10 ... Bus, 11 ... Communication part, 12 ... Memory, 13 ... Processing part, 40 ... Bus, 41 ... Communication part, 42 ... Memory, 43 … Processor

Claims (10)

Encrypted communication is performed with a plurality of receiving devices based on predetermined key data, and when any of the plurality of receiving devices is invalidated, the encryption with the receiving device that is not invalidated is performed. A data processing method for a key management source to obtain new key data used for communication,
Among a plurality of predetermined key acquisition methods, the key acquisition method in which the communication amount between the key management source generated to invalidate the predetermined reception device and the reception device that does not invalidate is minimized. A first step of selecting;
A second step of acquiring the new key data used for the encrypted communication with the receiving device that is not invalidated based on the key acquisition method selected in the first step. . In the second step, each of the plurality of receiving devices is associated with a leaf that is a terminal node at the last end branched from the route with which the key management source is associated, and a plurality of receiving devices are provided between the root and the leaf. The receiving device to be invalidated is associated based on a tree in which a layer is defined and the key acquisition method that applies a mutually different algorithm to at least two of the plurality of layers. 2. The data processing method according to claim 1, wherein data used for acquiring the new key data among data allocated to the nodes in the tree is specified according to the leaf. As the different algorithm,
Of the subtrees in the layer to be processed, of the subtree associated with the receiving device to be invalidated in the subtree or its branch destination, among the nodes at the final end in the subtree, the node at the final end or A first method of acquiring the new key data based on first data assigned to a set including only nodes to which the receiving device to be invalidated at the branch destination is not associated,
Among the nodes of the layer to be processed, the second data assigned to the node having no leaf associated with the receiving device to be invalidated at the branch destination and assigned to the node closest to the root is the new data. 3. The data processing method according to claim 2, wherein the second method is used as key data. The plurality of key acquisition methods include:
A first key acquisition that employs the first method for a first layer that includes the last node of the tree and the second method for a second layer that includes the root; Method and
The first method is adopted for a third layer including the last node of the tree, and the fourth method is defined for a fourth layer defined on the root side for the third layer. 4. The data processing method according to claim 3, further comprising a second key acquisition method that employs the first method and employs the second method for a fifth layer including the route. A third step of transmitting, to the receiving device that does not invalidate, specified data that specifies the key acquisition method specified in the first step and the data to be used for the selected key acquisition method. Item 2. The data processing method according to Item 1. Encrypted communication is performed with a plurality of receiving devices based on predetermined key data, and when any of the plurality of receiving devices is invalidated, the encryption with the receiving device that is not invalidated is performed. A program for causing a computer to execute a process for a key management source to obtain new key data used for communication,
Among a plurality of predetermined key acquisition methods, the key acquisition method in which the communication amount between the key management source generated to invalidate the predetermined reception device and the reception device that does not invalidate is minimized. A first step to choose;
A second procedure of acquiring the new key data used for the encrypted communication with the receiving apparatus that is not invalidated based on the key acquisition method selected in the first procedure. Encrypted communication is performed with a plurality of receiving devices based on predetermined key data, and when any of the plurality of receiving devices is invalidated, the encryption with the receiving device that is not invalidated is performed. A data processing device that performs a process for obtaining a new key data used for communication by a key management source,
Among a plurality of predetermined key acquisition methods, the key acquisition method in which the communication amount between the key management source generated to invalidate the predetermined reception device and the reception device that does not invalidate is minimized. A first means for selecting;
A second processing means for obtaining new key data used for the encrypted communication with the receiving apparatus which is not invalidated based on the key obtaining method selected by the first means. . A data processing method for performing encrypted communication with a key management source based on predetermined key data,
A first step of receiving, from the key management source, designated data specifying a key acquisition method and data used for the key acquisition method;
A second step of acquiring new key data based on the key acquisition method designated by the designated data using the data designated by the designated data received in the first step. Processing method. A program executed by a computer that performs encrypted communication with a key management source based on predetermined key data,
A first procedure of receiving, from the key management source, designated data specifying a key acquisition method and data used for the key acquisition method;
A second procedure for acquiring new key data based on the key acquisition method designated by the designated data using data designated by the designated data received in the first procedure. . A receiving device that performs encrypted communication with a key management source based on predetermined key data,
First means for receiving, from the key management source, designated data specifying a key acquisition method and data used for the key acquisition method;
Second means for acquiring new key data based on the key acquisition method designated by the designated data, using data designated by the designated data received by the first means. apparatus.

Images