(57)【要約】      （修正有）【課題】木構造を用いた鍵管理システムにおいて、受信者へ送信する暗号文数及び受信者が保有すべき秘密情報の量を減らし、且つ受信者の保有すべき公開情報の量も減らすことを可能とする。【解決手段】情報配信システムで、鍵管理機関は情報送信者が伝送する暗号化情報を復号するための秘密情報と公開情報を各受信者に割り当てる。また、暗号化情報を復号不可能にしたい受信者の集合を決め、上記の集合以外の受信者のみが復号できるような鍵情報を生成する。無効化されていない受信者は、暗号化情報を受信したとき、受信者が持つ秘密情報と公開情報と受信した鍵情報を用いて情報復号化用鍵を計算し受信情報を復号する。ここで、情報復号化用鍵はマスター鍵より定まる復号鍵にて算出される。受信者が割り当てられたリーフからノードに至るパス上に存在するノードに対してマスター鍵が定義され、下位のレイヤのノードに定義されたマスター鍵から順次求められる。【選択図】図１
2005333242.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理装置であって、
任意の二つ以上の素数の積である合成数を演算する合成数演算手段と、
前記合成数より小さく前記合成数と互いに素である任意のランダムな自然数を第一秘密情報として前記ルートノードに関連付けて記憶する第一秘密情報記憶手段と、
前記木構造の任意のノードに対する複数のリーフの組み合わせによって表現される部分集合において互いに素である自然数を公開情報として前記部分集合に関連付けて記憶する公開情報記憶手段と、
前記ルートノードに設定された前記第一秘密情報と前記公開情報に基づいて前記ルートノードのリーフに対するマスター鍵を演算する第一マスター鍵演算手段と、
前記マスター鍵を対応する前記リーフに関連付けて記憶する第一マスター鍵記憶手段と、
各前記ノードに対して、該ノードをリーフとする親ノードに設定されたマスター鍵と前記合成数に基づき，全単射写像関数を介して秘密情報である第二秘密情報を演算する第二秘密情報演算手段と、
前記第二秘密情報を対応する前記任意のノードに関連付けて記憶する第二秘密情報記憶手段と、
各前記ノードに設定された前記第二秘密情報と前記公開情報に基づいて各前記ノードのリーフに対する前記マスター鍵を演算する第二マスター鍵演算手段と、
前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶手段と、
前記部分集合に対して、前記ノードに設定された第一秘密情報又は第二秘密情報と前記公開情報に基づいて暗号／復号鍵を演算する暗号／復号鍵演算手段と、
前記暗号／復号鍵を対応する前記ノードに関連付けて記憶する暗号／復号鍵記憶手段と、を有することを特徴とする鍵管理装置。
【請求項２】
鍵管理装置が生成した合成数と、公開情報と、再生装置に対応するリーフに割り当てられた秘密情報とを取得する手段と、
前記鍵管理装置が生成した鍵情報を取得する手段と、
前記鍵管理装置が生成した暗号鍵にて暗号化された暗号化コンテンツを取得する手段と、
前記鍵情報から自身が含まれる部分集合が存在するかを判定する手段と、
前記再生装置に対応するリーフに割り当てられた秘密情報と前記合成数と前記公開情報に基づき、全単射写像関数を介して前記リーフからルートノードに至るパス上に存在する各々のノードに対するマスター鍵を演算する第三マスター鍵演算手段と、
前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶手段と、
前記自身を含む部分集合に対して、前記マスター鍵と前記合成数と前記公開情報に基づいて復号鍵を演算する復号鍵演算手段と、
前記復号鍵により、前記暗号化コンテンツを復号する手段と、
前記復号されたコンテンツを再生する手段と、を備えることを特徴とする再生装置。
【請求項３】
少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理手段は、
任意の二つ以上の素数の積である合成数を演算する合成数演算手段と、
前記合成数より小さく前記合成数と互いに素である任意のランダムな自然数を第一秘密情報として前記ルートノードに関連付けて記憶する第一秘密情報記憶手段と、
前記木構造の任意のノードに対する複数のリーフの組み合わせによって表現される部分集合において互いに素である自然数を公開情報として前記部分集合に関連付けて記憶する公開情報記憶手段と、
前記ルートノードに設定された前記第一秘密情報と前記公開情報に基づいて前記ルートノードのリーフに対するマスター鍵を演算する第一マスター鍵演算手段と、
前記マスター鍵を対応する前記リーフに関連付けて記憶する第一マスター鍵記憶手段と、
各前記ノードに対して、該ノードをリーフとする親ノードに設定されたマスター鍵と前記合成数に基づき，全単射写像関数を介して秘密情報である第二秘密情報を演算する第二秘密情報演算手段と、
前記第二秘密情報を対応する前記任意のノードに関連付けて記憶する第二秘密情報記憶手段と、
各前記ノードに設定された前記第二秘密情報と前記公開情報に基づいて各前記ノードのリーフに対する前記マスター鍵を演算する第二マスター鍵演算手段と、
前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶手段と、
前記部分集合に対して、前記ノードに設定された第一秘密情報又は第二秘密情報と前記公開情報に基づいて暗号／復号鍵を演算する暗号／復号鍵演算手段と、
前記暗号／復号鍵を対応する前記ノードに関連付けて記憶する暗号／復号鍵記憶手段と、
を有し、
前記鍵管理手段によって生成された暗号鍵により暗号化された鍵情報と、
前記鍵情報により暗号化された暗号化コンテンツと、が記録されていることを特徴とする記録媒体。
【請求項４】
鍵管理装置と、記録装置と、再生装置とを備える鍵管理システムであって、
前記鍵管理装置は、少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成し、
任意の二つ以上の素数の積である合成数を演算する合成数演算手段と、
前記合成数より小さく前記合成数と互いに素である任意のランダムな自然数を第一秘密情報として前記ルートノードに関連付けて記憶する第一秘密情報記憶手段と、
前記木構造の任意のノードに対する複数のリーフの組み合わせによって表現される部分集合において互いに素である自然数を公開情報として前記部分集合に関連付けて記憶する公開情報記憶手段と、
前記ルートノードに設定された前記第一秘密情報と前記公開情報に基づいて前記ルートノードのリーフに対するマスター鍵を演算する第一マスター鍵演算手段と、
前記マスター鍵を対応する前記リーフに関連付けて記憶する第一マスター鍵記憶手段と、
各前記ノードに対して、該ノードをリーフとする親ノードに設定されたマスター鍵と前記合成数に基づき，全単射写像関数を介して秘密情報である第二秘密情報を演算する第二秘密情報演算手段と、
前記第二秘密情報を対応する前記任意のノードに関連付けて記憶する第二秘密情報記憶手段と、
各前記ノードに設定された前記第二秘密情報と前記公開情報に基づいて各前記ノードのリーフに対する前記マスター鍵を演算する第二マスター鍵演算手段と、
前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶手段と、
前記部分集合に対して、前記ノードに設定された第一秘密情報又は第二秘密情報と前記公開情報に基づいて暗号／復号鍵を演算する暗号／復号鍵演算手段と、
前記暗号／復号鍵を対応する前記ノードに関連付けて記憶する暗号／復号鍵記憶手段と、
前記鍵情報と、前記暗号鍵とを記録装置に供給する手段と、
前記公開情報と、前記秘密情報と、を供給手段と、を有し、
前記記録装置は、前記鍵管理装置によって生成された暗号鍵を取得する手段と、
前記暗号鍵によりコンテンツを暗号化して暗号化コンテンツを生成する手段と、
前記暗号化コンテンツを記録媒体に記録する手段と、を有し、
前記再生装置は、鍵管理装置から合成数と、公開情報と、当該再生装置に対応するリーフに割り当てられた秘密情報と、を取得する手段と、
前記記録媒体より、前記鍵管理装置が生成した鍵情報と、前記暗号化コンテンツを取得する手段と、
前記鍵情報から自身が含まれる部分集合が存在するかを判定する手段と、
前記再生装置に対応するリーフに割り当てられた秘密情報と前記合成数と前記公開情報に基づき、全単射写像関数を介して前記リーフからルートノードに至るパス上に存在する各々のノードに対するマスター鍵を演算する第三マスター鍵演算手段と、
前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶手段と、
前記自身を含む部分集合に対して、前記マスター鍵と前記合成数と前記公開情報に基づいて復号鍵を演算する復号鍵演算手段と、
前記復号鍵により、前記暗号化コンテンツを復号する手段と、
前記復号されたコンテンツを再生する手段と、を備えることを特徴とする鍵管理システム。
【請求項５】
少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理方法であって、
任意の二つ以上の素数の積である合成数を演算する合成数演算工程と、
前記合成数より小さく前記合成数と互いに素である任意のランダムな自然数を第一秘密情報として前記ルートノードに関連付けて記憶する第一秘密情報記憶工程と、
前記木構造の任意のノードに対する複数のリーフの組み合わせによって表現される部分集合において互いに素である自然数を公開情報として前記部分集合に関連付けて記憶する公開情報記憶工程と、
前記ルートノードに設定された前記第一秘密情報と前記公開情報に基づいて前記ルートノードのリーフに対するマスター鍵を演算する第一マスター鍵演算工程と、
前記マスター鍵を対応する前記リーフに関連付けて記憶する第一マスター鍵記憶工程と、
各前記ノードに対して、該ノードをリーフとする親ノードに設定されたマスター鍵と前記合成数に基づき，全単射写像関数を介して秘密情報である第二秘密情報を演算する第二秘密情報演算工程と、
前記第二秘密情報を対応する前記任意のノードに関連付けて記憶する第二秘密情報記憶工程と、
各前記ノードに設定された前記第二秘密情報と前記公開情報に基づいて各前記ノードのリーフに対する前記マスター鍵を演算する第二マスター鍵演算工程と、
前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶工程と、
前記部分集合に対して、前記ノードに設定された第一秘密情報又は第二秘密情報と前記公開情報に基づいて暗号／復号鍵を演算する暗号／復号鍵演算工程と、
前記暗号／復号鍵を対応する前記ノードに関連付けて記憶する暗号／復号鍵記憶工程と、を有することを特徴とする鍵管理方法。
【請求項６】
少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理コンピュータを、
請求項１に記載の鍵管理装置として機能させることを特徴とする鍵管理プログラム。
【請求項７】
鍵管理装置が生成した合成数と、公開情報と、再生装置に対応するリーフに割り当てられた秘密情報とを取得する工程と、
前記鍵管理装置が生成した鍵情報を取得する工程と、
前記鍵管理装置が生成した暗号鍵にて暗号化された暗号化コンテンツを取得する工程と、
前記鍵情報から自身が含まれる部分集合が存在するかを判定する工程と、
前記再生装置に対応するリーフに割り当てられた秘密情報と前記合成数と前記公開情報に基づき、全単射写像関数を介して前記リーフからルートノードに至るパス上に存在する各々のノードに対するマスター鍵を演算する第三マスター鍵演算工程と、
前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶工程と、
前記自身を含む部分集合に対して、前記マスター鍵と前記合成数と前記公開情報に基づいて復号鍵を演算する復号鍵演算工程と、
前記復号鍵により、前記暗号化コンテンツを復号する工程と、
前記復号されたコンテンツを再生する工程と、を備えることを特徴とする再生方法。
【請求項８】
コンピュータを請求項２に記載の再生装置として機能させることを特徴とする再生プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、木構造を用い、特定の受信者の無効化機能を有する鍵管理システムに関する。
【背景技術】
【０００２】
映画、音楽などの著作物であるコンテンツの著作権を保護するために、コンテンツを暗号化して提供することが行われている。そのようなシステムの一例では、受信装置や再生装置（以下、「情報受信者」又は「受信者」とも呼ぶ）には複数の復号鍵（即ち、デバイス鍵）又は、復号鍵を生成するための秘密情報を与える。一方、暗号化されたコンテンツと、再生を許可された再生装置のみがコンテンツの復号鍵を生成できるようにした鍵情報とがネットワークを介して伝送され、又は記録媒体に記録されて情報受信者に提供される。再生を許可された受信装置や再生装置は、自身の保有する秘密情報と受信した鍵情報から、コンテンツの復号鍵を生成し、その復号鍵を使用してコンテンツを復号して再生する。一方、再生を許可されていない（無効化された）受信装置や再生装置は、コンテンツの復号鍵を生成できないので、暗号化されているコンテンツを再生することはできない。
【０００３】
ここで、受信装置や再生装置として一般的な機器を考えた場合、それが保有する秘密情報を変更する機能をその装置に持たせることは、その装置の製造コストの増加を招く、秘密情報の保管上の安全性を低下させる可能性があるなどの点であまり好ましくはない。このため、復号鍵を変更する機能を持たない受信装置や再生装置に対応した方式が望まれる。もし受信装置や再生装置が復号鍵を変更する機能を持っている場合には、その装置はある時点で得た復号鍵を、それより後の時点で送信された鍵情報を取得するために利用することができるので、通信量を低減できる可能性がある。しかし、変更機能を持たない装置は初期（例えば装置が製造されたとき）に与えられた復号鍵のみしか保有しない。よって、送信者が鍵生成情報を送信する際には、装置がその復号鍵のみを用いてコンテンツの復号鍵を得るのに必要な情報を毎回送信しなければならない。
【０００４】
このようなシステムで、鍵情報を管理するための手法として木構造を用いた鍵管理方式が提案されており、その例として「The Complete Sub-tree Method」、「The Subset Difference Method」（例えば非特許文献１参照。）、「Three Pattern Division Method」などが知られている。これらの方式では、コンテンツの復号鍵を生成するための鍵生成情報が不正に暴露されたり漏洩した場合には、その鍵生成情報を無効化するための処理が可能となっている。
【０００５】
木構造を用いた鍵管理方式の性能として以下の４点が挙げられる。
（１）送信する鍵情報の量
（２）受信者が保有しておく秘密情報の量
（３）受信者の保有しておく公開情報の量
（４）秘密情報と公開情報から復号鍵を計算するための受信者の計算量
上述のThe Complete Sub-tree Methodにおいては、（２）受信者が保有すべき秘密情報の量は少ないものの、（１）送信する鍵情報の量は多い。また、The Subset Difference Methodにおいては、（１）送信する鍵情報の量は少ないが、（２）受信者が保有すべき秘密情報の量は多い。一方、Three Pattern Division Methodは、これら２つの方式の中間の特性を持っている。
【０００６】
ところで、受信者に公開情報として素数を割り当て、受信者は与えられた秘密情報と公開情報から複数の復号鍵を生成するという鍵管理方式（「Master Key Method」）が知られている（例えば、非特許文献２参照）。この方式を用いた場合、受信者には１つだけの秘密情報が与えられ、公開情報と与えられた秘密情報から復号鍵を求めることができるため、上記の（１）送信する鍵情報の量及び（２）受信者が保有すべき秘密情報の量がThe Complete Sub-tree Methodよりも少なくてよい。しかし、公開情報として多くの素数を必要とするため、（３）受信者の保有しておく公開情報の量と、（４）秘密情報と公開情報から復号鍵を計算するための受信者の計算量とが増えてしまう。
【０００７】
【非特許文献１】Dalit Naor, Noni Naor, and Heff Lotspiech,"Revocation and Tracing Schemes for Stateless Receivers", Lecture Notes in Computer Science, Vol.2139, pp.41-62, 2001
【非特許文献２】Tomoyuki Asano, "A revocation scheme with minimal storage at receivers", Lecture Notes in Computer Science, Vol.2501, pp433-450, 2002
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明が解決しようとする課題には、上記のようなものが例として挙げられる。本発明は、木構造を用いて鍵管理を行う鍵管理システムにおいて、受信者へ送信する鍵情報の量、受信者が保有すべき秘密情報、及び受信者の保有すべき公開情報の量を減らすことが可能な鍵管理システムと、上記の鍵管理システムにて暗号化された鍵を復号することが可能な再生装置と、を提供する。
【課題を解決するための手段】
【０００９】
請求項１に記載の発明は、少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理装置は、任意の二つ以上の素数の積である合成数を演算する合成数演算手段と、前記合成数より小さく前記合成数と互いに素である任意のランダムな自然数を第一秘密情報として前記ルートノードに関連付けて記憶する第一秘密情報記憶手段と、前記木構造の任意のノードに対する複数のリーフの組み合わせによって表現される部分集合において互いに素である自然数を公開情報として前記部分集合に関連付けて記憶する公開情報記憶手段と、前記ルートノードに設定された前記第一秘密情報と前記公開情報に基づいて前記ルートノードのリーフに対するマスター鍵を演算する第一マスター鍵演算手段と、前記マスター鍵を対応する前記リーフに関連付けて記憶する第一マスター鍵記憶手段と、各前記ノードに対して、該ノードをリーフとする親ノードに設定されたマスター鍵と前記合成数に基づき，全単射写像関数を介して秘密情報である第二秘密情報を演算する第二秘密情報演算手段と、前記第二秘密情報を対応する前記任意のノードに関連付けて記憶する第二秘密情報記憶手段と、各前記ノードに設定された前記第二秘密情報と前記公開情報に基づいて各前記ノードのリーフに対する前記マスター鍵を演算する第二マスター鍵演算手段と、前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶手段と、前記部分集合に対して、前記ノードに設定された第一秘密情報又は第二秘密情報と前記公開情報に基づいて暗号／復号鍵を演算する暗号／復号鍵演算手段と、前記暗号／復号鍵を対応する前記ノードに関連付けて記憶する暗号／復号鍵記憶手段と、を有することを特徴とする。
【００１０】
請求項２に記載の発明は、再生装置は、鍵管理装置が生成した合成数と、公開情報と、再生装置に対応するリーフに割り当てられた秘密情報とを取得する手段と、前記鍵管理装置が生成した鍵情報を取得する手段と、前記鍵管理装置が生成した暗号鍵にて暗号化された暗号化コンテンツを取得する手段と、前記鍵情報から自身が含まれる部分集合が存在するかを判定する手段と、前記再生装置に対応するリーフに割り当てられた秘密情報と前記合成数と前記公開情報に基づき、全単射写像関数を介して前記リーフからルートノードに至るパス上に存在する各々のノードに対するマスター鍵を演算する第三マスター鍵演算手段と、前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶手段と、前記自身を含む部分集合に対して、前記マスター鍵と前記合成数と前記公開情報に基づいて復号鍵を演算する復号鍵演算手段と、前記復号鍵により、前記暗号化コンテンツを復号する手段と、前記復号されたコンテンツを再生する手段と、を備えることを特徴とする。
【００１１】
請求項３に記載の発明は、記録媒体は、少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理手段は、任意の二つ以上の素数の積である合成数を演算する合成数演算手段と、前記合成数より小さく前記合成数と互いに素である任意のランダムな自然数を第一秘密情報として前記ルートノードに関連付けて記憶する第一秘密情報記憶手段と、前記木構造の任意のノードに対する複数のリーフの組み合わせによって表現される部分集合において互いに素である自然数を公開情報として前記部分集合に関連付けて記憶する公開情報記憶手段と、前記ルートノードに設定された前記第一秘密情報と前記公開情報に基づいて前記ルートノードのリーフに対するマスター鍵を演算する第一マスター鍵演算手段と、前記マスター鍵を対応する前記リーフに関連付けて記憶する第一マスター鍵記憶手段と、各前記ノードに対して、該ノードをリーフとする親ノードに設定されたマスター鍵と前記合成数に基づき，全単射写像関数を介して秘密情報である第二秘密情報を演算する第二秘密情報演算手段と、前記第二秘密情報を対応する前記任意のノードに関連付けて記憶する第二秘密情報記憶手段と、各前記ノードに設定された前記第二秘密情報と前記公開情報に基づいて各前記ノードのリーフに対する前記マスター鍵を演算する第二マスター鍵演算手段と、前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶手段と、前記部分集合に対して、前記ノードに設定された第一秘密情報又は第二秘密情報と前記公開情報に基づいて暗号／復号鍵を演算する暗号／復号鍵演算手段と、前記暗号／復号鍵を対応する前記ノードに関連付けて記憶する暗号／復号鍵記憶手段と、を有し、前記鍵管理手段によって生成された暗号鍵により暗号化された鍵情報と、前記鍵情報により暗号化された暗号化コンテンツと、が記録されている。
【００１２】
請求項４に記載の発明は、鍵管理装置と、記録装置と、再生装置とを備える鍵管理システムは、前記鍵管理装置は、少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成し、任意の二つ以上の素数の積である合成数を演算する合成数演算手段と、前記合成数より小さく前記合成数と互いに素である任意のランダムな自然数を第一秘密情報として前記ルートノードに関連付けて記憶する第一秘密情報記憶手段と、前記木構造の任意のノードに対する複数のリーフの組み合わせによって表現される部分集合において互いに素である自然数を公開情報として前記部分集合に関連付けて記憶する公開情報記憶手段と、前記ルートノードに設定された前記第一秘密情報と前記公開情報に基づいて前記ルートノードのリーフに対するマスター鍵を演算する第一マスター鍵演算手段と、前記マスター鍵を対応する前記リーフに関連付けて記憶する第一マスター鍵記憶手段と、各前記ノードに対して、該ノードをリーフとする親ノードに設定されたマスター鍵と前記合成数に基づき，全単射写像関数を介して秘密情報である第二秘密情報を演算する第二秘密情報演算手段と、前記第二秘密情報を対応する前記任意のノードに関連付けて記憶する第二秘密情報記憶手段と、各前記ノードに設定された前記第二秘密情報と前記公開情報に基づいて各前記ノードのリーフに対する前記マスター鍵を演算する第二マスター鍵演算手段と、前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶手段と、前記部分集合に対して、前記ノードに設定された第一秘密情報又は第二秘密情報と前記公開情報に基づいて暗号／復号鍵を演算する暗号／復号鍵演算手段と、前記暗号／復号鍵を対応する前記ノードに関連付けて記憶する暗号／復号鍵記憶手段と、前記鍵情報と、前記暗号鍵とを記録装置に供給する手段と、前記公開情報と、前記秘密情報と、を供給手段と、を有し、前記記録装置は、前記鍵管理装置によって生成された暗号鍵を取得する手段と、前記暗号鍵によりコンテンツを暗号化して暗号化コンテンツを生成する手段と、前記暗号化コンテンツを記録媒体に記録する手段と、を有し、前記再生装置は、鍵管理装置から合成数と、公開情報と、当該再生装置に対応するリーフに割り当てられた秘密情報と、を取得する手段と、前記記録媒体より、前記鍵管理装置が生成した鍵情報と、前記暗号化コンテンツを取得する手段と、前記鍵情報から自身が含まれる部分集合が存在するかを判定する手段と、前記再生装置に対応するリーフに割り当てられた秘密情報と前記合成数と前記公開情報に基づき、全単射写像関数を介して前記リーフからルートノードに至るパス上に存在する各々のノードに対するマスター鍵を演算する第三マスター鍵演算手段と、前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶手段と、前記自身を含む部分集合に対して、前記マスター鍵と前記合成数と前記公開情報に基づいて復号鍵を演算する復号鍵演算手段と、前記復号鍵により、前記暗号化コンテンツを復号する手段と、前記復号されたコンテンツを再生する手段と、を備えることを特徴とする。
【００１３】
請求項５に記載の発明は、少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理方法は、任意の二つ以上の素数の積である合成数を演算する合成数演算工程と、前記合成数より小さく前記合成数と互いに素である任意のランダムな自然数を第一秘密情報として前記ルートノードに関連付けて記憶する第一秘密情報記憶工程と、前記木構造の任意のノードに対する複数のリーフの組み合わせによって表現される部分集合において互いに素である自然数を公開情報として前記部分集合に関連付けて記憶する公開情報記憶工程と、前記ルートノードに設定された前記第一秘密情報と前記公開情報に基づいて前記ルートノードのリーフに対するマスター鍵を演算する第一マスター鍵演算工程と、前記マスター鍵を対応する前記リーフに関連付けて記憶する第一マスター鍵記憶工程と、各前記ノードに対して、該ノードをリーフとする親ノードに設定されたマスター鍵と前記合成数に基づき，全単射写像関数を介して秘密情報である第二秘密情報を演算する第二秘密情報演算工程と、前記第二秘密情報を対応する前記任意のノードに関連付けて記憶する第二秘密情報記憶工程と、各前記ノードに設定された前記第二秘密情報と前記公開情報に基づいて各前記ノードのリーフに対する前記マスター鍵を演算する第二マスター鍵演算工程と、前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶工程と、前記部分集合に対して、前記ノードに設定された第一秘密情報又は第二秘密情報と前記公開情報に基づいて暗号／復号鍵を演算する暗号／復号鍵演算工程と、前記暗号／復号鍵を対応する前記ノードに関連付けて記憶する暗号／復号鍵記憶工程と、を有することを特徴とする。
【００１４】
請求項７は、再生方法は、鍵管理装置が生成した合成数と、公開情報と、再生装置に対応するリーフに割り当てられた秘密情報とを取得する工程と、前記鍵管理装置が生成した鍵情報を取得する工程と、前記鍵管理装置が生成した暗号鍵にて暗号化された暗号化コンテンツを取得する手段と、前記鍵情報から自身が含まれる部分集合が存在するかを判定する工程と、前記再生装置に対応するリーフに割り当てられた秘密情報と前記合成数と前記公開情報に基づき、全単射写像関数を介して前記リーフからルートノードに至るパス上に存在する各々のノードに対するマスター鍵を演算する第三マスター鍵演算工程と、前記マスター鍵を対応する前記リーフに関連付けて記憶する第二マスター鍵記憶工程と、前記自身を含む部分集合に対して、前記マスター鍵と前記合成数と前記公開情報に基づいて復号鍵を演算する復号鍵演算工程と、前記復号鍵により、前記暗号化コンテンツを復号する工程と、前記復号されたコンテンツを再生する工程と、を備えることを特徴とする。
【発明を実施するための最良の形態】
【００１５】
以下、発明を実施するための最良の形態としての本発明の実施形態に係る鍵管理装置、再生装置、記録媒体、鍵管理システム、鍵管理方法及び鍵管理プログラム、再生方法及び再生プログラムについて説明する。
【００１６】
上記の鍵管理システムは、コンテンツ等の著作権の保護を目的として、鍵情報を管理するための手法として木構造を用いた鍵管理方式を採用している。この鍵管理システムを採用した情報配信システムは、例えば鍵管理装置などの鍵管理機関、情報送信者、情報受信者から構成される。鍵管理機関は、情報送信者（例えば、「記録媒体」にコンテンツを記録する「記録装置」など）が伝送する暗号化情報を復号するための秘密情報と公開情報を各情報受信者（例えば、「記録媒体」に記録されたコンテンツを再生する「再生装置」など）に割り当てる。また、鍵管理機関は、暗号化情報を復号不可能にしたい受信者の集合を決め、前記集合以外の受信者のみが復号できるような鍵情報を生成し、伝送情報を暗号化するための情報暗号化用鍵とあわせて情報送信者への配送も行う。
【００１７】
情報送信者は、鍵管理機関から配送された、伝送情報の情報暗号化用鍵を用いて伝送情報を暗号化して暗号化情報を作成し、鍵情報と一緒に暗号化情報を受信者に伝送する。無効化されていない受信者については、暗号化情報を受信したとき、受信者が持つ秘密情報と公開情報と受信した鍵情報を用いて情報復号化用鍵を計算し、この情報復号化用鍵を用いて暗号化情報から受信情報を復号する。ここで、情報暗号化用鍵及び情報復号化用鍵（以下、これらを「セッション鍵」と呼ぶ）は、マスター鍵より定まる暗号／復号鍵にて算出されるようになっている。
【００１８】
上記の鍵管理システムにおいては、暗号／復号鍵は、木構造を構成するノードに定義される部分集合に割り当てられる。このとき、暗号／復号鍵は、各ノードに割り当てられたマスター鍵を用いて求められるようになっている。このマスター鍵は、上位のレイヤのノードに割り当てたマスター鍵に基づいて、下位のレイヤのノードに割り当てるべきマスター鍵を生成する。これにより、情報受信者は、秘密情報として１つのマスター鍵を保有し、公開情報も共通の情報を保有すればよいので、暗号／復号鍵を作成するために保持する情報を少なくすることができる。
【００１９】
また、第二秘密情報演算手段は、全単射写像関数に従って、親に当たるノードに割り当てたマスター鍵から子に当たるノードに割り当てるべきマスター鍵を生成する。好適には、全単射写像関数としてPseudo Random Permutation(ＰＲＰ)を用いることができる。この場合、親子の関係にあるノードに定義される部分集合に割り当てられる暗号／復号鍵の関係は無相関となる。よって、コンテンツ等の著作権を安全に保護することができる。
【００２０】
本発明の鍵管理方法及び鍵管理プログラムに係る実施形態によれば、上述した本発明の鍵管理装置に係る実施形態と同様の各種利益を享受することができる。同様に、本発明の再生方法及び再生プログラムに係る実施形態によっても、上述した本発明の再生装置に係る実施形態と同様の各種利益を享受することができる。
【実施例】
【００２１】
以下、図面を参照して本発明の好適な実施例について説明する。まず、鍵管理方式について基礎的な説明を行い、続いて本発明の実施例に係る鍵管理方式を説明する。
【００２２】
（1.1）受信者の無効化機能を有する鍵管理方式
送信者が多数の受信者に対して同一の情報を伝送するシステムにおいて、信頼できる鍵管理機関が、あらかじめ全ての受信者に伝送情報を復号するための秘密情報を配布しておき、その秘密情報を持たない受信者が送信者からの情報を復号できないように、送信者側で情報を暗号化して伝送する方法がある。この場合に問題となるのは、全ての受信者が同一の秘密情報を保有している場合、悪意ある受信者が自分の保有する秘密情報を１回公開してしまえば、その後に伝送される情報は誰にでも復号が可能になってしまうことである。
【００２３】
この問題の対策として、鍵管理機関が受信者毎に異なる秘密情報を配布し、特定の受信者の秘密情報が漏洩した場合、その受信者の保有していた秘密情報を用いても伝送された情報を復号できないようにする手法、即ち、受信者の無効化機能を有する鍵管理方式がある。本発明はそのような鍵管理方式を扱う。
【００２４】
ここでは、受信者に最初に秘密情報（復号鍵等）を割り当てる以外は、受信者の保有する秘密情報を一切変更できないようなアプリケーションを想定している。
【００２５】
受信者の無効化機能を有する鍵管理方式を適用した情報配信システムの１つのモデルを図１及至３に示す。図１及び図２においては、情報配信システムは、鍵管理機関１、情報送信者２及び情報受信者３の３つの要素から構成される。一方、図３に示す情報配信システムは、鍵管理機関１、情報送信者２、情報受信者３、公開情報掲示板１０の４つの要素から構成される。以下、図１から順に具体的に説明する。
【００２６】
図１においては、鍵管理機関１は、情報送信者２が伝送する暗号化情報６ｂを復号するための秘密情報７と公開情報８を各受信者に割り当てる。公開情報８については、鍵管理方式によっては存在しない場合もあるが、秘密情報７は必ず存在する。また、鍵管理機関１は、暗号化情報６ｂを復号不可能にしたい受信者（今後、ある特定の受信者に対して、伝送される情報を復号できないようにすることを「受信者の無効化」と呼ぶ）の集合を決め、前記集合以外の受信者のみが復号できるような鍵情報４を生成し、伝送情報６ａを暗号化するための鍵（情報暗号化用鍵５）とあわせて情報送信者２への配送も行う。ここで各受信者に割り当てる秘密情報７と、伝送情報６ａの暗号化に用いられる鍵（情報暗号化用鍵５）の生成・保管・配送は安全に行われるものと仮定する。
【００２７】
情報送信者２は、鍵管理機関１から配送された、伝送情報６ａの情報暗号化用鍵５を用いて伝送情報６ａを暗号化して暗号化情報６ｂを作成し、無効化されていない受信者のみが復号できる鍵情報４と一緒に暗号化情報６ｂを受信者に伝送する。
【００２８】
無効化されていない受信者については、暗号化情報６ｂを受信したとき、受信者が持つ秘密情報７と公開情報８と受信した鍵情報４を用いて情報復号化用鍵９を計算し、この情報復号化用鍵９を用いて暗号化情報６ｂから受信情報６ｃを復号する。逆に無効化されている受信者については、そのような受信者が複数結託しても、暗号化情報６ｂに関して何の情報も得られない。また、ここでは多数の受信者の存在を想定している。
【００２９】
次に、図２に示す情報配信システムは、鍵管理機関１は、鍵情報４のみを情報送信者２に配送し、情報暗号化用鍵５は配送しないシステムである。この場合、情報送信者２は情報受信者３と同様に、鍵管理機関１から得た秘密情報７と公開情報８とから情報暗号化用鍵５を計算する。そのため、情報受信者２には、秘密情報７と公開情報８を、鍵管理機関１が割り当てておく必要がある。
【００３０】
次に、図３に示す情報配信システムは、公開情報８を鍵管理機関１が保有するのではなく、例えばネットワーク上の公開掲示板１０のような公開の場に保存し、情報を暗号化・復号化する毎に情報送信者２又は情報受信者３が公開掲示板１０にアクセスしてダウンロードするというようなシステムである。
【００３１】
以下、上記構成要素について詳しく説明する。
【００３２】
Ｎを全ての受信者の集合とし、その要素数を｜Ｎ｜＝Ｎとする。Ｎの部分集合Ｒを無効化したい受信者の集合とし、その要素数を｜Ｒ｜＝ｒとする。受信者の無効化機能を有する鍵管理方式の目的は、鍵管理機関（又は情報送信者）が受信を許可した受信者、つまり集合Ｒに含まれない全ての受信者ｕ∈Ｎ＼Ｒが伝送される情報を復号でき、逆に受信を許可されていない集合Ｒに含まれる受信者全てが結託しても全く暗号化情報を得られないようにすることである。
【００３３】
(a)鍵管理機関
（i）初期設定
受信者全体の集合Ｎの部分集合Ｓ1、Ｓ2、…、Ｓw（∀ｊ、Ｓj⊆Ｎ）を定義する。各Ｓjには暗号（復号）鍵Ｌjが割り当てられる。ここで、各Ｌjは一様に分布しており、互いに独立な値を割り当てるのが望ましい。各受信者（受信装置）uには、秘密情報ＳＩuと公開情報ＰＩuを割り当てる。ここでＳjに含まれる全ての受信者ｕ∈Ｓjが、自分に割り当てられた秘密情報ＳＩuと公開情報ＰＩuから、自分の属する部分集合Ｓjに割り当てられた復号鍵Ｌjを求められるように秘密情報ＳＩuと公開情報ＰＩuを割り当てなければならない。また、Ｓjに含まれない全ての受信者ｕ∈Ｎ＼Ｓjが結託しても復号鍵Ｌjを求めることができないように秘密情報ＳＩuと公開情報ＰＩuを割り当てなければならない。
【００３４】
（ii）鍵情報生成
(1)伝送情報Ｍの暗号化、復号化に用いる鍵（即ち、上述した情報暗号化用鍵５又は情報復号化用鍵９であり、以下では、これらを「セッション鍵」とも呼ぶ）Ｋを選ぶ。
【００３５】
(2)無効化する受信者の集合Ｒの補集合Ｎ＼Ｒに属する受信者ｕ∈Ｎ＼Ｒをいくつかの部分集合Ｓi1、Ｓi2、…、Ｓimに分割する。
【００３６】
【数１】
2005333242.tif 000003
ここで、初期設定で上記部分集合に割り当てられてた暗号／復号鍵をそれぞれＬi1、Ｌi2、…Ｌimとする。なお、Ｌi1、Ｌi2、…Ｌimは、情報送信者２にとってはセッション鍵を暗号化するための暗号鍵であり、情報受信者３にとってはセッション鍵を復号化するための復号鍵であるため、以下では暗号鍵と復号鍵の両方の意味を含む場合には、これを「暗号／復号鍵」と表記する。
【００３７】
(3)暗号／復号鍵Ｌi1、Ｌi2、…Ｌimを用いてセッション鍵Ｋをｍ回暗号化して式（1-2）を生成、セッション鍵Ｋと一緒に情報送信者２に配送する。
【００３８】
【数２】
2005333242.tif 000004
i1、i2、…imは、各受信者ujが鍵情報式（1-2）の中から自身に割り当てられた復号すべき暗号文Ｅenc（Ｋ,Ｌij）を特定するためのインデックス情報である。
【００３９】
ここで、情報送信者２へのセッション鍵の配送は安全に行われるものと仮定する。また、Ｅencは暗号化アルゴリズムである。本システムで用いられる暗号、復号化アルゴリズムは２種類あり、以下にまとめる（ただし、２つのアルゴリズムに全く同じものを使用しても構わない）。
【００４０】
・伝送情報Ｍの暗号化アルゴリズムＦenc、復号化アルゴリズムＦdec
セッション鍵Ｋを用いて暗号文ＣK＝Ｆenc（Ｍ、Ｋ）を生成する。高速性が要求される。
【００４１】
・セッション鍵暗号化アルゴリズムＥenc、復号化アルゴリズムＥdec
セッション鍵の配送に用いる。Ｆencよりも暗号化アルゴリズムの安全性が要求される。
【００４２】
なお、情報送信者２へのセッション鍵の配送を行わない場合は、初期設定において、送信者にも受信者と同じように秘密情報、公開情報を割り当て、それらと鍵情報からセッション鍵の計算が可能なようにしておく。
【００４３】
（ｂ）情報送信者
セッション鍵Ｋと特定の受信者のみが復号できる鍵情報を鍵管理機関から受け取り、セッション鍵Ｋを鍵として暗号化アルゴリズムＦencを用いて伝送情報Ｍを暗号化して、暗号化情報
【００４４】
【数３】
2005333242.tif 000005
を伝送する。
【００４５】
（ｃ）情報受信者
受信者ｕは、情報送信者により暗号化された次の暗号化情報を受信する。
【００４６】
【数４】
2005333242.tif 000006
(1)ｕ∈Ｓijであるようなｉjを探索する。（ｕ∈Ｒの場合、存在しない。）
(2)自身の保有する秘密情報ＳＩuと公開情報ＰＩuからＬijを求める。
【００４７】
(3)Ｋ＝Ｅdec（Ｃij、Ｌij）を求める。
【００４８】
(4)Ｍ＝Ｆdec（ＣK、Ｋ）を求める。
【００４９】
上記鍵管理方式を実現するアルゴリズムとして、例えば以下のような鍵管理方式がある。
・The Complete Subtree Method
・The Subset Difference Method 
・Tree Pattern Division Method 
上記方式の違いとしては、(1)受信者の部分集合Ｓ１、…、Ｓwの定義、(2)各部分集合に対する暗号（復号）鍵ＬSj、公開情報ＰＩの割り当て方法、(3)受信を許可する（無効化しない）受信者の集合Ｎ＼Ｒの分割方法、(4)各受信者ｕへのＳＩu、ＰＩuの割り当て方法と、ＳＩu、ＰＩuから受信者の属する部分集合Ｓjに割り当てられた鍵ＬSjの求め方等が挙げられる。
【００５０】
各方式は以下の４つの観点から評価される。
【００５１】
・伝送する鍵情報の量
式(1−2)，式(1−3)の[ ]の部分であり，暗号文Ｆenc(M、K) 以外にコンテンツ復号のために必要な伝送情報。一般にＮ＼Ｒを分割した部分集合の数ｍに比例する。
【００５２】
・受信者が保有しておく秘密情報ＳＩuの量
復号用の鍵等の秘密情報を受信者がどれだけ保持しておかなければならないか。
【００５３】
・受信者が復号鍵を得るために必要とする公開情報ＰＩuの量
復号鍵を求めるための公開情報を受信者がどれだけ保持しておかなければならないか。
【００５４】
・受信者が伝送された情報を復号するのに要する演算量
（1.2）基礎となる方法１
次に、本発明の実施例の基礎となる方法１として、上述したThe Complete Sub-tree Method、Three Pattern Division等にて用いられている鍵管理方式について説明する。
【００５５】
（1.2.1）部分集合Ｓ1、Ｓ2、…、Ｓwの定義
最初に受信者全体の集合Ｎの部分集合Ｓ1、Ｓ2、…、Ｓwを定義する。この部分集合に対して暗号／復号鍵Ｌi1、Ｌi2、…Ｌimを割り当てることになる。Ｎ枚のリーフを持つａ分木のリーフに各受信者ｕj(ｊ＝１、２、…Ｎ)を割り当てる（ここでａはａ＞１を満たす整数、Ｎはａの冪であるとしている）。図４に、ａ＝３、Ｎ＝２７の場合の例を示す。
【００５６】
ａ分木の各内部ノードｖkについてｖk(k＝１、２、…、(Ｎ−１)/(ａ−１))と番号づけをする。ただしルートをｖ1とし、図４に示すように左側のノードから右側のノードへ、上位ノードから下位ノードの順番で行う。また各リーフに割り当てられている受信者ｕj(ｊ＝１、２、…Ｎ)も左から順番に番号づけする。
【００５７】
次に全ての内部ノードｖk(k＝１、２、…、(Ｎ−１)/(ａ−１))について２ａ−２個の部分集合Ｓk,b1b2…bi…baを定義する。ここで、ｂiは式（2-1）を満たすものとする。
【００５８】
【数５】
2005333242.tif 000007
部分集合Ｓk,b1b2…bi …baは、ノードｖkのａ個の子ノードを左から順番にｂ1、ｂ2、…、ｂi、…、ｂaとしたときｂi＝１であるような子ノードの子孫であるリーフに割り当てられた受信者の集合として定義される。つまり、ノードｖkのａ個の子ノードの子孫に無効化されるべき受信者の割り当てられたリーフが存在する場合、その子ノードに対応するｂi＝０である。このときｂi＝０の子ノードを、「無効化ノード」と呼ぶ。ノードｖkのａ個の子ノードが無効化ノードであるか否かはｂi∈｛０、１｝の値で示される。それらの値を左から順番にｂ1、ｂ2、…、ｂi、…、ｂaとしたものを「ノード無効化パターン」と呼ぶ。
【００５９】
例えば、図４に示したａ＝３、Ｎ＝２７の場合、ルートノードｖ1に定義される部分集合は、Ｓ1,100、Ｓ1,010、Ｓ1,001、Ｓ1,110、Ｓ1,101、Ｓ1,011、Ｓ1,111であり、ノードｖ2…ｖ(N-1)(a-1)に定義される部分集合は、Ｓk,100、Ｓk,010、Ｓk,001、Ｓk,110、Ｓk,101、Ｓk,011である。このとき、全ての受信者を含む集合としてａ分木のルートノードｖ1について集合Ｓ1,11…1を定義する。また、部分集合Ｓ2,101は、ノードｖ2の子ノードｖ5、ｖ6、ｖ7の中でｂ1とｂ3に対応するｖ5、ｖ7の子孫であるリーフに割り当てられた受信者ｕ1、ｕ2、ｕ3、ｕ7、ｕ8、ｕ9からなる部分集合である。
【００６０】
（1.2.2）各部分集合Ｓk,b1b2…baに対する暗号／復号鍵Ｌk,b1b2…baの割り当て方法
鍵管理機関は部分集合Ｓk,b1b2…baに対して、互いに独立な値を持つ暗号／復号鍵Ｌk,b1b2…baを割り当てる。図５に例として、ａ＝３、Ｎ＝２７の場合のいくつかのノードとリーフについて仮想的に割り当てられている部分集合、暗号／復号鍵、また部分集合に含まれる受信者を示す。
【００６１】
（1.2.3）各受信者ｕへのＳＩuの割り当て方法と、ＳＩuから受信者の属する部分集合Ｓk,b1b2…baに割り当てられた暗号／復号鍵ＬSk,b1b2…baの求め方
鍵管理機関は、受信者ｕの割り当てられたリーフからルートに至るパス上に存在する内部ノードｖkについて定義されている部分集合Ｓk,b1b2…baの中で、受信者ｕを要素として含むような部分集合に割り当てられた式（2-2）に示す個数の暗号／復号鍵Ｌk,b1b2…baを、秘密情報ＰＩuとして直接受信者ｕに与える。
【００６２】
【数６】
2005333242.tif 000008
例えば、ａ＝３、Ｎ＝２７の場合の受信者ｕ20の保有する秘密情報ＳＩu20を説明する。受信者ｕ20が含まれる部分集合は、Ｓ1,111、Ｓ1,001、Ｓ1,101、Ｓ1,011、Ｓ4,100、Ｓ4,110、Ｓ4,101、Ｓ11,010、Ｓ11,110、Ｓ11,011である。また、受信者ｕ20が保有する秘密情報ＳＩu20は、これらの部分集合と対応し、Ｌ1,111、Ｌ1,001、Ｌ1,101、Ｌ1,011、Ｌ4,100、Ｌ4,110、Ｌ4,101、Ｌ11,010、Ｌ11,110、Ｌ11,011となる。
【００６３】
（1.2.4）受信者の集合Ｎ＼Ｒの分割方法
受信を許可する（無効化しない）受信者の集合Ｎ＼Ｒを、上記で定義された部分集合に分割する方法を説明する。最初に、鍵管理機関は無効化したい受信者に対応するリーフからルートに至るパス上に存在する全ての内部ノードを無効化ノードとする。無効化したい受信者が存在しない場合は、集合Ｓ1,11…1をＮ＼Ｒとする。無効化ノードをｖkとしたとき、ｖkのａ個の子ノード全てが無効化ノードである場合を除き、ｖkに対して定義されている部分集合Ｓk,b1b2…bi …ba、（ｂiは、式（2-1）を満たすものとする）を受信者の集合Ｎ＼Ｒを構成する部分集合として選択する。ここで、ノード無効化パターンｂ1ｂ2…ｂi…ｂaは、実際の無効化子ノードと一致するパターンを選ぶ必要がある。これにより、上記の無効化ノードに対して一つの部分集合が選択される。以上の処理を全ての無効化ノードについて行い、選択された部分集合がＮ＼Ｒを構成する。このとき、選択される部分集合の数の上限は、無効化する受信者の数を|Ｒ|＝ｒとするとｒ(logａＮ/ｒ+１)で与えられる。
【００６４】
図６に、ａ＝３、Ｎ＝２７の場合の、無効化したい受信者３２（符号３０は無効化しない受信者を示す。）をｕ3、ｕ7、ｕ8、ｕ10、ｕ11、ｕ12、ｕ16としたときの例を示している。この場合、無効化ノードはｖ1、ｖ2、ｖ3、ｖ5、ｖ7、ｖ8、ｖ10であり、子ノード全てが無効化ノードでない無効化ノードはｖ1、ｖ2、ｖ3、ｖ5、ｖ7、ｖ10となる。よって、Ｎ／Ｒを構成する部分集合は、Ｓ1,001、Ｓ2,010、Ｓ3,010、Ｓ5,110、Ｓ7,001、Ｓ10,011である。
【００６５】
（1.3）基礎となる方法２
次に、本発明の実施例の基礎となる方法２として、上述した非特許文献２に記載されたMater Key Methodの鍵管理方式について説明する。
【００６６】
なお、部分集合Ｓ1、Ｓ2、…、Ｓwの定義、及び受信者の集合Ｎ＼Ｒの分割方法は、前述した基礎となる方法１と同様であるため、説明は省略する。
【００６７】
（1.3.1）各部分集合Ｓk,b1b2…baに対する暗号／復号鍵Ｌk,b1b2…ba、公開情報ｐk,b1b2…baの割り当て方法
鍵管理機関は２つの大きな素数（例えば512bit以上）ｑ１,ｑ２を選択し、その積Ｍを公開情報として公開する。各素数ｑ１,ｑ２は鍵管理機関で秘密に保持しておく。次に式（2-3）に示す個数の素数ｐk,b1b2…baを選択する。
【００６８】
【数７】
2005333242.tif 000009
ここで、ｋ＝１、２、…、(Ｎ−１)/(ａ−１)、ｂi∈｛０、１｝であり、ｂiは全てのｋに対し式（2-4）を満たす。
【００６９】
【数８】
2005333242.tif 000010
また、ｂiはｋ≠１に対して、式（2-5）を満たすものとする。
【００７０】
【数９】
2005333242.tif 000011
なお、以下では、インデックスｂ1ｂ2…ｂaをＢと表記する。
【００７１】
鍵管理機関は部分集合Ｓk,Bに素数ｐk,Bを割り当て、各ｐk,Bとこの割り当てを公開情報ＰＩとして公開する。またＥを全ての部分集合Ｓk,Bに割り当てられた全ての素数ｐk,Bの積とする。鍵管理機関はランダムにｇ∈Ｚ*Mを選び、部分集合Ｓk,Bに割り当てる暗号／復号鍵Ｌk,Bを式（2-6）のように定める。ここでＺ*Mは正整数Ｍを法とした剰余環ＺM＝｛０、１、…、Ｍ−１｝でＭと互いに素となるものの集合である。これは法Ｍに関する既約剰余類と呼ばれ、乗法に関して群となる。またｇは鍵管理機関が秘密に保持しておく。
【００７２】
【数１０】
2005333242.tif 000012
鍵管理機関は暗号／復号鍵Ｌk,Bのうちｂi＝１であるものを、ノードｖkの子ノードの中で左からｉ番目の子ノードに仮想的に割り当てる。同様に、部分集合Ｓk,B、素数ｐk,Bについてもｖkの子ノードに割り当てる。
【００７３】
図７に例として、ａ＝３、Ｎ＝２７の場合のいくつかのノードとリーフについて仮想的に割り当てられている部分集合、素数、暗号／復号鍵を示す。
【００７４】
（1.3.2）各受信者ｕへのＳＩu,ＰＩuの割り当て方法と、ＳＩu,ＰＩuから受信者の属する部分集合Ｓk,Bに割り当てられた暗号／復号鍵Ｌk,Bの求め方
鍵管理機関は、受信者ｕの割り当てられたリーフからルートに至るパス上に存在する内部ノードに仮想的に割り当てられた式（2-2）で示した個数の素数を公開情報ＰＩuとして受信者ｕに与える。
【００７５】
また、鍵管理機関は受信者ｕの割り当てられたリーフからルートに至るパス上に存在する内部ノードに仮想的に割り当てられている式（2-2）で求まる個数の暗号／復号鍵に対応するマスター鍵ＭＫuを秘密情報ＳＩuとして受信者ｕに与える。マスター鍵は式（2-7）のように計算できる。
【００７６】
【数１１】
2005333242.tif 000013
ここで、Ｐuは、受信者ｕの割り当てられたリーフからルートに至るパス上に存在する内部ノードに仮想的に割り当てられた全ての素数ｐk,Bの積である。
【００７７】
式（2-7）で定義されるマスター鍵から、受信者ｕの割り当てられたリーフからルートに至るパス上に存在する内部ノードに仮想的に割り当てられた暗号／復号鍵については、式（2-8）に示すように自身の保有する公開情報（素数）を用いて求めることができる。
【００７８】
【数１２】
2005333242.tif 000014
図８に例として、ａ＝３、Ｎ＝２７の場合の受信者ｕ20の保有する秘密情報ＳＩu20と公開情報、及びそれらからの暗号／復号鍵の計算方法を示す。
【００７９】
(2.1)第１実施例による方法
以下では、上述した基礎となる方法２（Master Key Method）を改良した本発明の第１実施例に係る鍵管理方式について説明する。
【００８０】
なお、部分集合Ｓ1、Ｓ2、…、Ｓwの定義、及び受信者の集合Ｎ＼Ｒの分割方法は、前述した基礎となる方法１及び基礎となる方法２と同様であるため、説明は省略する。
【００８１】
（2.1.1）各部分集合Ｓk,b1b2…baに対する暗号／復号鍵Ｌk,b1b2…ba、公開情報ＰＩの割り当て方法
鍵管理機関は、２つの大きな素数（例えば512bit以上）ｑ１、ｑ２を選択し、その積Ｍを公開情報として公開する。各素数ｑ１、ｑ２は鍵管理機関で秘密に保持しておく。
【００８２】
次に式（3-1）を満たす互いに素な２ａ−２個の自然数ｐb1b2…ba（例えば素数）を選択する。ここで、ｂiは上記した式（2-1）を満たすものとする。
【００８３】
【数１３】
2005333242.tif 000015
以下では、２ａ−２通り存在するインデックスｂ1ｂ2…ｂaをＢと表記する。ここでλ(Ｍ)は、Carmichael関数と呼ばれ式（3-2）で与えられる。
【００８４】
【数１４】
2005333242.tif 000016
鍵管理機関は、部分集合Ｓk,Bに素数ｐBを割り当て、各ｐBとこの割り当てを公開情報ＰＩとして公開する。またＥをノードｖkについて定義された全ての部分集合Ｓk,Bに割り当てられた素数ｐBの積とする。すなわちＥ＝ｐ00…001ｐ00…010ｐ00…011…ｐ11…100…ｐ11…001ｐ11…110である。鍵管理機関は、ランダムにｇ1∈Ｚ*Mを選び、ノードｖ1について定義されている２ａ−２個の部分集合Ｓ1,Bに割り当てる暗号／復号鍵Ｌ1,Bを式（3-3）のように定める。ここでＺ*Mは、正整数Ｍを法とした剰余環ＺM＝｛０、１、…、Ｍ−１｝でＭと互いに素となるものの集合である。これは法Ｍに関する既約剰余類と呼ばれ、乗法に関して群となる。また、ｇ1は鍵管理機関が秘密に保持しておく。
【００８５】
【数１５】
2005333242.tif 000017
全ての受信者を含む集合Ｓ1,11…1については、割り当てる暗号／復号鍵Ｌ1,11…1を式（3-4）のように定める。
【００８６】
【数１６】
2005333242.tif 000018
ここで、任意の内部ノードｖkについて定義された部分集合の中で、ｖkのａ個の各子ノードｖjについて次のようなインデックス集合を定義する。ｖjの子孫となるリーフに割り当てられた受信者を含むような部分集合Ｓk,BのインデックスＢの集合を、インデックス集合ＡＬjと定義する。次に、各子ノードｖjについて式（3-5）で与えられるマスター鍵を定義する。
【００８７】
【数１７】
2005333242.tif 000019
式（3-5）で定義されるマスター鍵からノードｖkについて定義された部分集合Ｓk,Bの中で、インデックス集合ＡＬjに含まれるインデックスをもつ部分集合Ｓk,i(ｉ∈ＡＬj)に割り当てられた暗号／復号鍵については、式（3-6）に示すように求めることができる。
【００８８】
【数１８】
2005333242.tif 000020
しかし、インデックス集合ＡＬjに含まれないインデックスをもつ部分集合Ｓk,i(ｉ∈ＡＬj)については、マスター鍵ＭＫk,jのｐi乗根を求めることが困難であるため、暗号／復号鍵Ｌk,i(i∈ＡＬj)を求めることができない。
【００８９】
次に、図２に示したａ＝３、Ｎ＝２７の木構造を有する鍵管理構造があるとき、ｖ1の子ノードｖ4について定義された２ａ−２個の部分集合Ｓ4,Bに割り当てる暗号／復号鍵Ｌ4,Bについて考える。最初に、ｖ1の子ノードｖ4について式（3-7）で定義されるＭＫ1,4を計算する。
【００９０】
【数１９】
2005333242.tif 000021
ノードｖ1と同様にノードｖ4について定義されている２ａ−２個の部分集合Ｓ4,Bに割り当てる暗号／復号鍵Ｌ4,Bを、式（3-8）のように定める。
【００９１】
【数２０】
2005333242.tif 000022
ここで、ｇ4は式（3-9）により定義される。
【００９２】
【数２１】
2005333242.tif 000023
また、Pseudo Random Permutation(ＰＲＰ)は０以上でＭより小さい整数を入出力としてもつような全単射写像関数である。ただし、ここで法をＭとする冪乗剰余関数をＰＲＰとして用いてはならない。このＰＲＰは、全ての受信者に対して公開される。以下では、「ＰＲＰ-１」は、ＰＲＰの逆関数として用いる。
【００９３】
鍵管理機関は、ＭＫ1,4からＰＲＰ-１を用いてｇ4Ｅを計算した後、ｇ4ＥからそのＥ乗根を求めてｇ4を得る。鍵管理機関は法Ｍの素因数ｑ１,ｑ２を保有しているため、式（3-2）のλ(Ｍ)を求めることができる。λ(Ｍ)が与えられれば、Ｅのλ(Ｍ)を法とする乗法の逆元Ｄをユークッリドの互除法などにより求め、式（3-10）を計算すればよい。なお、上記では、ｇからＭＫを求める際にＰＲＰを用い、ＭＫからｇを算出する際にＰＲＰ-１を用いるものについて示したが、ｇからＭＫを求める際にＰＲＰ-１を用い、ＭＫからｇを算出する際にＰＲＰを用いても良い。
【００９４】
【数２２】
2005333242.tif 000024
計算されたｇ4に対して、ノードｖ1について行った方法と同様の方法で、式（3-8）に示すようにノードｖ4に定義されている部分集合Ｓ4,Bへの暗号／復号鍵Ｌ4,Bの割り当てを行えばよい。
【００９５】
以下同様に、全ての内部ノードｖk(k＝１、２、…、(Ｎ−１)/(ａ−１))について、ノードｖkに定義されている部分集合Ｓk,Bへの暗号／復号鍵Ｌk,Bの割り当てを行う。
【００９６】
図９に例として、ａ＝３、Ｎ＝２７の場合のノードｖ1,ｖ4に定義されている部分集合Ｓ1,B、Ｓ4,Bへの暗号／復号鍵Ｌ1,B、Ｌ4,Bの割り当てを示す。
【００９７】
なお、上記の方法では、全ての受信者を含む集合Ｓ1,11…1については公開情報としての素数を割り当てていない。これは公開情報の量（素数の数）を減らすためであるが、割り当ててもよい。素数ｐ1,11…1を割り当てたとすると、割り当てられる暗号／復号鍵Ｌ1,11…1は、式（3-11）のようになる。
【００９８】
【数２３】
2005333242.tif 000025
また、この場合、任意の内部ノードｖiについても、ｖi以下に存在する全てのリーフに割り当てられた受信者からなる部分集合Ｓi,11…1に公開情報として素数ｐi,11…1を割り当てていると考えても問題ない。この場合、部分集合Ｓi,11…1に割り当てられる暗号／復号鍵は式（3-12）のようになる。
【００９９】
【数２４】
2005333242.tif 000026
図１０に、ａ＝３、Ｎ＝２７の場合ｖ1とｖ4について定義される部分集合への暗号／復号鍵の割り当て例を示す。上記のような割り当てを行った場合、任意の内部ノードｖi以下に存在する全てのリーフに割り当てられた受信者からなる部分集合Ｓi,11…1は二重に定義されている。これは、各内部ノードに定義される部分集合が、２ａ−２個から２ａ−１個に増えたためである。例えば、図１０の部分集合Ｓ1,001と部分集合Ｓ4,111は、ともに受信者ｕ19〜ｕ27からなる集合であり、それぞれの部分集合に割り当てられている暗号／復号鍵Ｌ1,001、Ｌ4,111には式（3-13）に示す関係がある。この場合、どちらの値を用いても構わない。
【０１００】
【数２５】
2005333242.tif 000027
(2.1.2）各受信者ｕへのＳＩu,ＰＩuの割り当て方法と、ＳＩu,ＰＩuから受信者の属する部分集合Ｓk,Bに割り当てられた暗号／復号鍵Ｌk,Bの求め方
鍵管理機関は、公開情報として、２ａ−２個の素数ｐb1b2…baを受信者ｕに与える。なお、ｂiは上記した式（2-1）を満たすものとする。
【０１０１】
さらに、受信者ｕの親ノードｖklogaNについて、式（3-5）で定義されるマスター鍵を受信者ｕへの秘密情報ＳＩuとして割り当てる。受信者ｕの割り当てられているリーフをｖklogaN+1とすると、受信者ｕの保有する秘密情報は式（3-14）で与えられる。
【０１０２】
【数２６】
2005333242.tif 000028
ノードｖklogaNについて定義されている部分集合ＳklogaN,Bの中で、受信者ｕを含む部分集合は、インデックス集合ＡＬklogaN+1に含まれるインデックスをもつ部分集合ＳklogaN,l(ｌ∈ＡＬklogaN+1)である。部分集合ＳklogaN,l(ｌ∈ＡＬklogaN+1)に割り当てられた暗号／復号鍵ＬklogaN,l(ｌ∈ＡＬklogaN+1)については、式（3-6）に示す方法により計算できる。
【０１０３】
次にノードｖklogaNの親ノードｖklogaN-1について定義されているマスター鍵ＭＫklogaN-1,klogaNを式（3-15）により求める。
【０１０４】
【数２７】
2005333242.tif 000029
ノードｖklogaNの場合と同様に、ノードｖklogaN-1ついて定義されている部分集合ＳklogaN-1,Bの中で、受信者ｕを含む部分集合ＳklogaN-1,ｌ(ｌ∈ＡＬklogaN,B)に割り当てられた暗号／復号鍵ＬklogaN-1,ｌ(ｌ∈ＡＬklogaN)についても式（3-6）に示す方法により計算できる。
【０１０５】
同様の処理をルートノードｖ1まで繰り返すことにより、受信者ｕを含む全ての部分集合に割り当てられた暗号／復号鍵を求めることができる。最後に、全ての受信者を含む集合Ｓ1,11…1に割り当てられた暗号／復号鍵Ｌ1,11…1については、式（3-16）を計算することにより求まる。
【０１０６】
【数２８】
2005333242.tif 000030
図１１に例として、ａ＝３、Ｎ＝２７の場合の受信者ｕ20の保有する秘密情報ＳＩu20と公開情報、及びそれらからの暗号／復号鍵の計算方法を示す。ｕ20に割り当てられた秘密情報ＭＫ11,20からノードｖ11に割り当てられたマスター鍵ＭＫ4,11を算出し、このマスター鍵ＭＫ4,11からノードｖ4に割り当てられたマスター鍵ＭＫ1,4が算出される。そして、これらのマスター鍵ＭＫ11,20、ＭＫ4,11、ＭＫ1,4から暗号／復号鍵が求まる。
【０１０７】
（2.1.3）各方式の性能比較
以下では、第１実施例に係る鍵管理方式と従来の鍵管理方式について性能を比較する。従来の方法と第１実施例に係る鍵管理方式の性能比較したものを図１２に示す。図１２では、送信する鍵情報の量と、受信者が保有しておく秘密情報の量と、受信者の保有しておく公開情報の量と、秘密情報と公開情報から復号鍵を計算するための受信者の計算量と、を各鍵管理方式で比較している。なお、図１２中のｒは無効化する受信者の数、Ｎは受信者の総数（即ち、リーフの数）、ａは木の分岐数、を表している。
【０１０８】
Complete Sub-tree Methodは、秘密情報として直接復号鍵を保有するため、受信者の保有する復号鍵の量は少ないものの、鍵情報の量は多い。逆に、Subset Difference Methodは受信者の保有する秘密情報の量は多いものの、鍵情報の量は少ない。これら２つの鍵管理方式においては、送信する鍵情報の量と受信者の保有する秘密情報の量はトレードオフの関係にあり、片方を減らせば、もう片方は増加してしまうという関係がある。一方、Tree Pattern Division Methodにおいては、上記の鍵管理方式の中間の特性をもっていることがわかる。
【０１０９】
ここで、基礎となる方法２（即ち、非特許文献２に記載のMaster Key Method）では、一つの秘密情報から公開情報を用いて複数の暗号／復号鍵を計算するため、受信者の保有する秘密情報は一つであるにもかかわらず、送信する鍵情報の量が増えることはない。ここで、上記のComplete Sub-tree Method、Subset-Difference Method、Tree Pattern Division Methodの３方式においては、受信者の保有する秘密情報の量はパラメータとしてＮを含むため、受信者総数が多い場合、秘密情報の量が増えてしまう。しかし、基礎となる方法２においては、受信者総数Ｎが大きい場合でも、受信者は1024bitsのみの秘密情報を保有していればよい。
【０１１０】
基礎となる方法２では、上記のようなメリットがある反面、秘密情報から暗号／復号鍵を計算するために、多くの公開情報（素数）を必要とするといったデメリットがある。公開情報であるため、あらかじめ受信者に保有させずに、暗号化情報の送信時に鍵情報として送信してもよいが、この場合には送信する情報量の増加を招く。他にも図１０には示していないが、システム全体で用いる素数の数は(２ａ−２)(Ｎ−１)/(ａ−１)+１と膨大な数であるため、鍵管理機関はこれら全ての素数を生成、管理しなければならない。
【０１１１】
本発明の第１実施例に係る鍵管理方式では、上記の基礎となる方法２と同様に、受信者の保有する秘密情報の量が受信者総数Ｎをパラメータとしていないため、受信者総数Ｎが大きい場合も常に一つ（1024bits）の秘密情報で十分である。しかし、基礎となる方法２では受信者の保有する公開情報（素数）の数が多くなってしまっていたが、第１実施例に係る鍵管理方式では、それより少ない２ａ−２個でよいことがわかる。よって、システム全体で使用する公開情報（素数）の数が少ないため、鍵管理機関も容易にそれを生成、管理することができる。
【０１１２】
第１実施例に係る鍵管理方式では、受信者の割り当てられたリーフからノードに至るパス上に存在するノードに対して定義された全てのマスター鍵を、下のレイヤのノードに定義されたマスター鍵から順次求めることができる方式を取っている。また、親子の関係にある二つのノードにそれぞれ定義された部分集合に対して割り当てられる暗号／復号鍵の関係を、全単射関数ＰＲＰを用いて相関の無い値にしている。以上により、マスター鍵を用いた暗号／復号鍵の割り当てをノード毎に独立して行うことができ、公開情報の量（素数の数）を大幅に減らすことができる。
【０１１３】
（2.2）第２実施例による方法
第２実施例による鍵管理方式では、部分集合に対する暗号／復号鍵の割り当てにマスター鍵を用いる方式と、部分集合に対して互いに独立な値を持つ暗号／復号鍵を直接割り当てる方式の二つのタイプの方式の中で，全ての部分集合の定義、及び受信者の集合Ｎ＼Ｒの分割方法が同じである方式についてのみ組み合わせて用いる。具体的には、マスター鍵を用いる方式として上記の第１実施例による鍵管理方式を用い、部分集合に対して互いに独立な値を持つ暗号／復号鍵を直接割り当てる方式として基礎となる方法１で示したTree Pattern Division Methodを用いる。
【０１１４】
（2.2.1）各部分集合Ｓk,b1b2…baに対する暗号／復号鍵Ｔk,b1b2…ba、公開情報ＰＩの割り当て方法
各部分集合Ｓk,b1b2…baに対する暗号／復号鍵Ｔk,b1b2…baと公開情報ＰＩの割り当ては、最初に第１実施例にて示したマスター鍵技術を用いる方式を用いる。その後、割り当てられた暗号／復号鍵Ｌk,b1b2…baを、非特許文献１に紹介されているようなＺ*M上にランダムに分布する要素を任意の長さｔの乱数列への写像関数ｈ（式（3-17）に示す）を用いて変換し、これを各部分集合に割り当てる暗号／復号鍵とする。
【０１１５】
【数２９】
2005333242.tif 000031
例えば、セッション鍵の暗号（復号）アルゴリズムＥenc、Ｅdecに用いる暗号／復号鍵の鍵長を128bitとする場合、第１実施例に係る鍵管理方式による鍵の割り当で部分集合Ｓk,Bに割り当てられた暗号／復号鍵Ｌk,bは、128bitの乱数列Ｔk,b＝ｈ（Ｌk,b）に写像される。これを部分集合Ｓk,Bに割り当て、暗号／復号鍵とする。
【０１１６】
（2.2.2）各受信者ｕへのＳＩu、ＰＩuの割り当て方法と、ＳＩu、ＰＩuから受信者の属する部分集合Ｓk,Bに割り当てられた暗号／復号鍵Ｔk,Bの求め方
各受信者は、自分の環境、実装形態に応じて、二つの鍵管理方式から一つを選択することが可能である。
【０１１７】
第１実施例に係る鍵管理方式を用いる方式で実装する場合、前述の(2.1.2）にて示した方法を用いる。異なる点は、秘密情報ＳＩuから自身の含まれる部分集合Ｓk,Bに割り当てられた暗号／復号鍵Ｌk,Bを求めた後、写像関数Ｔk,b＝ｈ（Ｌk,b）を用いて計算された値を暗号／復号鍵とする点である。
【０１１８】
一方、基礎となる方法１で示した部分集合に互いに独立な値を持つ暗号／復号鍵を直接割り当てる鍵管理方式で実装する場合、前述の(1.2.3）にて示した方法を用いる。ただし、受信者に割り当てる暗号／復号鍵は、Ｔk,b＝ｈ（Ｌk,b）である。
【０１１９】
図１３に例として、ａ＝２、Ｎ＝１６における第２実施例に係る鍵管理方式を示す。この例では、受信者ｕ3は第１実施例に係る鍵管理方式を用いる方式を選択し、受信者ｕ9は基礎となる方法１の鍵管理方式を用いる方式を選択している。この場合、受信者ｕ3は、公開情報としてp10、p01を保有し、秘密情報としてＭＫ9,18=ｇ9E/p10=gp01=T9,10が割り当てられる。この秘密情報を用いて、受信者ｕ3は暗号／復号鍵Ｔ1,11、Ｔ1,10、Ｔ2,10、Ｔ4,01、Ｔ9,10を求める。一方、受信者ｕ9には、秘密情報として暗号／復号鍵そのものであるＴ1,11、Ｔ1,01、Ｔ3,10、Ｔ6,10、Ｔ12,10のみが割り当てられる。
【０１２０】
なお、上記では、部分集合に対する暗号／復号鍵の割り当てにマスター鍵を用いる方式として第１実施例に係る鍵管理方式を用いるものを示したが、これを基礎となる方法２で示した鍵管理方式に置き換えてもよい。
【０１２１】
（2.2.3）第２実施例に係る鍵管理方式を用いた場合の効果
前述したように、Complete Sub-tree Method、Subset-Difference Method、Tree Pattern Division Methodの３方式においては、受信者の保有する秘密情報の量はパラメータとしてＮをもつため、受信者総数Ｎが大きい場合は、各受信者の保有する秘密情報の量が増えてしまう。しかし、秘密情報から復号鍵を得るための計算は要しない。
【０１２２】
これに対し、基礎となる方法２（Master Key Method）や第１実施例に係る鍵管理方式では、受信者総数Ｎが大きい場合も、受信者は常に1024bitsのみの秘密情報を保有していればよい。しかしながら、秘密情報から暗号／復号鍵を計算するために多くの公開情報（素数）を必要とする。公開情報を予め受信者が保持せず、暗号化データ送信時に鍵情報として送信した場合には、情報送信量が増加してしまう。また、公開掲示板の役割をもつサーバに、システムで用いられる全ての公開情報（素数）を保存しておき、データ受信時に各受信者がサーバにアクセスし、暗号／復号鍵の計算に用いる公開情報（素数）のみダウンロードして使用することで、大量の公開情報を受信者が直接保有することは避けられるが、ネットワークにつながっていないオフラインアプリケーションには適用が難しい。さらに、秘密情報から復号鍵の計算に多量の冪乗剰余演算を必要とする。
【０１２３】
以上のように、受信者の環境(例えば、オンラインかオフラインか）、又は実装形態（例えば、ＰＣ機器かＣＥ機器）により、適した鍵管理方式が異なることがわかる。
【０１２４】
したがって、受信者の形態がＰＣ等のある程度演算能力があり、ソフトウェア実装可能な環境においては、基礎となる方法２や第１実施例に係る方式が適している。ＰＣでは、オンライン環境であることが多いため、公開情報をオンラインで配送したり、公開掲示板からダウンロードするといった実装も容易である。さらに、ＰＣでのソフトウェア実装においては、秘密情報は直接、プログラムに埋め込むことになるが、その場合、プログラムを不正な解析から保護するためにプログラムの難読化が必要になる。プログラムの難読化においては、保護対象となるデータのサイズが大きければ、難読化後のプログラムサイズもそれに依存して大きくなるため、秘密情報はできる限り少ないことが望ましいことを考慮すると、基礎となる方法２や第１実施例に係る方式が実装に適していると考えられる。
【０１２５】
一方、ＣＥ機器等のハードウェア環境において低コストで受信装置を実装したい場合、回路規模を著しく増加させる冪乗剰余演算回路の実装は避けたい。また、オフライン環境も想定されるため、公開情報の量はそのまま製品に搭載するメモリー量に影響することを考慮すると、公開情報がなく、秘密情報の量も比較的少ないComplete Sub-tree MethodやTree Pattern Division Method等の方式が適している。
【０１２６】
以上のような理由から本発明の第２実施例に係る鍵管理方式は、２つの鍵管理方式を受信者の環境、実装形態に応じて選択可能にしている。また、この場合、鍵管理機関は受信者の実装形態に関与することなく、あたかも一つの鍵管理方式で全ての受信者を管理しているように扱うことができる。このように、第２実施例に係る鍵管理方式では、鍵管理機関で管理しなければならない情報の少ない方式を選びつつ、各受信者は、自分の環境や実装形態に適した鍵管理方式を選択することができる。
【０１２７】
（2.3）実施例のコンテンツ配信システム
本発明の実施例によるコンテンツ配信システムの概略構成を図１４に示す。このシステムは、情報提供者１２が各種の記憶媒体１５をユーザに提供する。本実施例では、記憶媒体１５は、例えばＤＶＤ−ＲＯＭなどの光ディスクを含む各種の記録媒体とすることが可能である。ユーザは再生装置１３を所持し、当該再生装置１３により記録媒体１５から情報を再生する。再生装置１５は内部に情報復号化用鍵９を有している。
【０１２８】
ここで、図１に示したように、情報提供者１２は鍵管理方式の３要素における情報送信者に対応し、再生装置１３は情報受信者に対応する。即ち、情報提供者１２は、映像／音声などのコンテンツ情報を情報暗号化用鍵５を使用して暗号化し、暗号化情報６ｂとして記録媒体１５に記録する。また、情報提供者１２は、無効化の対象となる再生装置１３によっては復号できないが、無効化の対象とならない再生装置１３によれば復号可能な鍵情報４を記録媒体１５に記録する。そして、情報提供者１２は記録媒体１５を各再生装置１３のユーザに提供する。
【０１２９】
無効化の対象とならない再生装置１３は、自己の有する情報復号化用鍵９で鍵情報４を復号して暗号化情報６ｂの復号鍵を取得し、これで暗号化情報６ｂを復号して映像／音声などの情報を再生することができる。一方、無効化の対象となる再生装置１３は、自己の情報復号化用鍵９により記録媒体１５内の鍵情報４を復号することができないので、暗号化情報６ｂを復号する鍵を得ることができず、暗号化情報６ｂを再生することができない。こうして、本システムでは、記録媒体１５上に記録された暗号化情報６ｂを特定の再生装置１３のみにより再生可能とする。
【０１３０】
本発明では、上述の第１実施例又は第２実施例にて示したいずれかの鍵管理方式に従って、再生装置１３側の情報復号化用鍵９及び記録媒体１５に記録される鍵情報４を生成する。具体的には、再生装置１３は、記憶媒体１５から取得する鍵情報４と、鍵管理機関より予め与えられる秘密情報（その再生装置に対応するものである）及び公開情報と、から情報復号化用鍵９を生成する。第１実施例に係る鍵管理方式の場合、秘密情報及び公開鍵の情報量が少ないので、再生装置１５が記憶しておく情報量を少なくすることができる。一方、第２実施例に係る鍵管理方式であれば、再生装置１３がＣＥ機器などである場合には、再生装置１５は復号鍵の計算量が少ない鍵管理方式を選択し、秘密情報と鍵情報４から情報復号化用鍵９を生成する。第２実施例に係る鍵管理方式を用いることにより、再生装置１３は実装形態に適した鍵管理方式を選択することができ、効率的に暗号化情報６ｂを復号化することができる。
【０１３１】
（3）コンテンツ配信システムの具体例
次に、本発明の実施例に係るコンテンツ配信システムの具体例について説明する。なお、このコンテンツ配信システムは、ＤＶＤなどの光ディスクを記録媒体として使用するものであり、ここでは特にＤＶＤ−ＲＯＭを例にとって説明する。このコンテンツ配信システムでは、情報送信者はコンテンツの著作権者、光ディスク製造工場などに相当する。一方、情報受信者はコンテンツの再生機能を有する装置（再生装置）であり、ハードウェア又はソフトウェアにより構成されている。
【０１３２】
なお、以下の実施例の説明において、Encryption（  ）は暗号化アルゴリズム、Decryption（  ）は復号化アルゴリズムを表すものとする。また、Encryption（引数１、引数２）は引数２を暗号鍵として引数１を暗号化した暗号文を表し、Decryption（引数１、引数２）は引数２を復号鍵として引数１を復号したデータを表す。また、記号“｜”は２つのデータの結合を表し、（データＡ）｜（データＢ）のように用いる。
【０１３３】
（3.1）コンテンツ記録装置
まず、コンテンツ記録装置について説明する。図１５はコンテンツをディスクに記録するコンテンツ記録装置５０の構成を示すブロック図であり、情報送信者としての前述のディスク製造工場などに設けられるものである。また、コンテンツ記録装置５０の各部の信号Ｓ１〜Ｓ７の内容を図１６及び図１７に示している。なお、ここでのコンテンツは、情報送信者から情報受信者へ送信される前述の暗号化情報に対応するものである。
【０１３４】
図１５において、コンテンツ入力装置５１はコンテンツを入力する装置であり、図１６（ａ）に示すように、コンテンツに対応する信号Ｓ１を出力する。コンテンツとしては、通常、音楽、映像などのマルチメディアデータが代表的であるが、ここでのコンテンツはそれらに限定されるものではなく、文書などのデータも含まれる。また、コンテンツ入力装置５１としては、コンテンツのマスターデータが記録された磁気テープや、ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭなどの記録媒体を読み込んで信号Ｓ１を出力する回路や、ＬＡＮ、インターネットなどの通信回線を経由してアクセスし、そのデータをダウンロードして信号Ｓ１を出力する回路などが挙げられる。
【０１３５】
復号鍵入力装置５２はコンテンツ復号用の鍵Ｋを入力する装置であり、図１６（ｂ）に示すように、コンテンツ復号鍵Ｋである信号Ｓ２を出力する。コンテンツ復号鍵Ｋは、情報送信者である著作権者、ディスク製造工場又は鍵管理機関により決定される。
【０１３６】
暗号鍵入力装置５３は、コンテンツ暗号鍵Ｋを入力する装置であり、図１６（ｃ）に示すように、コンテンツ暗号鍵Ｋである信号Ｓ３を出力する。コンテンツ暗号鍵Ｋとコンテンツ復号鍵Ｋには、次の関係が成立することが要求される。
【０１３７】
Ｐ＝Decryption（Encryption（任意のデータＰ、コンテンツ暗号鍵Ｋ）、コンテンツ復号鍵Ｋ）
コンテンツ暗号化装置５４は、コンテンツ暗号鍵Ｋ（信号Ｓ３）を用いてコンテンツ（信号Ｓ１）を暗号化し、暗号化コンテンツである信号Ｓ４を出力する。信号Ｓ４を図１６（ｄ）に示す。
【０１３８】
なお、この例ではコンテンツ暗号鍵Ｋを用いてコンテンツを直接暗号化しているが、コンテンツ自体を暗号化する必要は必ずしもない。例えば、コンテンツ自体は他の暗号鍵Ｃで暗号化し、暗号鍵Ｃに対応する復号鍵Ｃを上記のコンテンツ暗号鍵Ｋで暗号化して信号Ｓ４として出力してもよい。つまり、ここでいう「コンテンツ暗号鍵を用いてコンテンツを暗号化する」とは、コンテンツの復号化に少なくともコンテンツ復号鍵Ｋを必要とするような方法でコンテンツを変換することを意味する。
【０１３９】
暗号鍵入力装置５５は、コンテンツ復号鍵Ｋを暗号化するための複数の暗号鍵Ｌiを入力する装置であり、ｍ個の暗号鍵ＬI1、ＬI2、…ＬIm-1、ＬImを、前述の鍵管理方式のアルゴリズムに従って選択し、信号Ｓ５を出力する。信号Ｓ５を図１６（ｅ）に示す。これら複数の暗号鍵ＬI1、ＬI2、…、ＬIi…、ＬIm-1、ＬImの組み合わせにより、コンテンツを再生することができる再生装置（上述した「無効化の対象とならない受信者」）が一意に決まる。よって、暗号鍵ＬIiは再生を許可する権限を持つ機関（鍵管理機関又は情報送信者）により決定される。また、Header（暗号鍵ＬI1）、Header（暗号鍵ＬI2）…、Header（暗号鍵ＬIm-1）、Header（暗号鍵ＬIm）は，暗号鍵ＬI1、ＬI2、…ＬIm-1、ＬImそれぞれの識別情報を示しており、式(1−2)、式(1−3)のインデックス部分[i1,i2,…im]と同じものを表している。ここでは、Header（暗号鍵Ｌ）を暗号鍵Ｌのヘッダーと呼ぶ。
【０１４０】
鍵暗号化装置５６は、信号Ｓ５として得られる暗号鍵ＬIiを用いて、信号Ｓ２として得られるコンテンツ復号鍵Ｋを暗号化し、信号Ｓ６を出力する。図１７（ａ）に信号Ｓ６を示す。なお、以下の説明では簡単のため、
信号Ｓ６＝Header（暗号鍵Ｌ）｜Encryption（コンテンツ復号鍵Ｋ、暗号鍵Ｌ）と表す。
【０１４１】
記録信号生成装置５７は、暗号化されたコンテンツと、複数の暗号鍵ＬIiで暗号化されたコンテンツ復号鍵Ｋとを合成して記録信号を生成する。より具体的には、記録信号生成装置５７は、信号Ｓ４＝Encryption（コンテンツ、コンテンツ暗号鍵Ｋ）と、信号Ｓ６＝Header（暗号鍵Ｌ）｜Encryption（コンテンツ復号鍵Ｋ、暗号鍵Ｌ）を結合し、それにエラー訂正符号を付加したものを信号Ｓ７として出力する。よって、図１７（ｂ）に示すように、信号Ｓ７は、コンテンツ暗号鍵Ｋで暗号化したコンテンツ、ｍ個の暗号鍵ＬIiで暗号化されたコンテンツ復号鍵Ｋ、及びそれらにエラー訂正符号を追加した信号である。なお、ＥＣＣはエラー訂正符号である。
【０１４２】
記録装置５８は、生成された記録信号Ｓ７を光ディスクＤに記録し、又は、光ディスクを製造するためのマスターディスクなどに記録信号Ｓ７をカッティングする）に記録する装置であり、通常レーザ光源やレーザ発信器などを備える。
【０１４３】
（3.2）コンテンツ再生装置
次に、上述のようにしてコンテンツが記録された光ディスクＤからコンテンツを再生するためのコンテンツ再生装置６０について説明する。図１８はコンテンツ再生装置６０の構成を示すブロック図である。また、コンテンツ再生装置６０の各部の信号の内容を図１９及び図２０に示している。
【０１４４】
図１２において、情報読取装置６１は光ピックアップなどの装置であり、光ディスクＤに記録されている情報を読み取って信号Ｓ１１を出力する。信号Ｓ１１を、図１９（ａ）に示す。
【０１４５】
エラー訂正装置６２は、入力された信号Ｓ１１のエラー訂正を行う装置であり、信号Ｓ１１中のＥＣＣに基づいてエラー訂正処理を実行する。そして、エラー訂正後の信号を信号Ｓ１２と信号Ｓ１３に分けてそれぞれ鍵復号装置６４及びコンテンツ復号装置６５へ供給する。信号Ｓ１２は暗号鍵Ｌiで暗号化されたコンテンツ復号鍵Ｋのデータであり、Ｓ１２＝Header（暗号鍵Ｂ）｜Encryption（コンテンツ復号鍵Ｋ、暗号鍵Ｌ）で示される。一方、信号Ｓ１３はコンテンツ暗号鍵Ｋで暗号化されたコンテンツのデータであり、Ｓ１３＝Encryption（コンテンツ、コンテンツ暗号鍵Ｋ）で示される。
【０１４６】
記憶装置６３は、再生装置が保有する複数の復号鍵ＬJ1、ＬJ2、…ＬJj…ＬJn-1、ＬJnとそのヘッダHeader（ＬJ1）、Header（ＬJ2）、…、Header（ＬJj）、…、Header（ＬJn-1）、Header（ＬJn）を保存しておく装置である。なお、ここでは記憶装置６３はｎ個の復号鍵を保有していると仮定する。また、鍵管理機関は、コンテンツ復号鍵Ｋの暗号化用の暗号鍵ＬIiと再生を許可されている再生装置の保有する復号鍵ＬJjのうちの少なくとも１つは次の関係が整理するように、予め再生装置に復号鍵ＬJjを配布している：
Ｐ  ＝  Decryption（Encryption（任意のデータＰ、暗号鍵ＬIi）、復号鍵ＬJj）
さらに、ヘッダーについては、上記の関係の暗号鍵ＬIiと復号鍵ＬJjに付加されたヘッダーについて次の関係が成立するようにヘッダーの値が決定されている：
Header（暗号鍵ＬIi）＝Header（暗号鍵ＬJj）
上記の関係が成立するように復号鍵ＬJjとそのヘッダーを各再生装置に（再生装置製造時に）配布するのは、上述の鍵管理機関であり、その際にどの再生装置にどの復号鍵ＬJjを配布するかの決定は、上述の鍵管理方式のアルゴリズムに従って行われる。
【０１４７】
記憶装置６３は、図２０（ｂ）に示すように、復号鍵ＬJ1｜復号鍵ＬJ2｜…｜復号鍵ＬJn-1｜復号鍵ＬJnと、そのヘッダーHeader（復号鍵ＬJ1）｜Header（復号鍵ＬJ2）｜…｜Header（復号鍵ＬJn-1）｜Header（復号鍵ＬJn）を出力する。
【０１４８】
鍵復号装置６４は、信号Ｓ１２＝Header（復号鍵Ｌ｜Encryption（コンテンツ復号鍵Ｋ、暗号鍵Ｌ）と、信号Ｓ１４＝（復号鍵ＬJ1｜復号鍵ＬJ2｜…｜復号鍵ＬJn-1｜復号鍵ＬJn）とそのヘッダーHeader（復号鍵ＬJ1）｜Header（復号鍵ＬJ2）｜…｜Header（復号鍵ＬJj）｜…｜Header（復号鍵ＬJn-1）｜Header（復号鍵ＬJn）を入力とし、光ディスクＤから読み取ったHeader（暗号鍵ＬIi）と再生装置が保有するHeader（復号鍵ＬJj）が一致するかを調べ、一致する時には復号鍵ＬJjを用いてEncryption（コンテンツ復号鍵Ｋ、暗号鍵ＬIi）を復号する。つまり、コンテンツ復号鍵Ｋ＝Decryption（Encryption（コンテンツ復号鍵Ｋ、暗号鍵ＬIi）,復号鍵ＬJj）となる。この処理を一致するヘッダーの組み合わせが見つかるようにIｉ及びJｊの組み合わせを変えて実行し、図２０（ｃ）に示すように信号Ｓ１５＝コンテンツ復号鍵Ｋを出力する。こうして、復号されたコンテンツ復号鍵Ａが信号Ｓ１５としてコンテンツ復号装置６５へ供給される。一方、一致するヘッダーの組み合わせがない場合は、再生不可能として全ての処理を終了する。
【０１４９】
コンテンツ復号装置６５は、図２０（ａ）に示す信号Ｓ１３＝Encryption（コンテンツ、コンテンツ暗号鍵Ｋ）と、図２０（ｃ）に示す信号Ｓ１５＝Decryption（Encryption（コンテンツ復号鍵Ｋ、暗号鍵ＬIi）、復号鍵ＬJj）＝コンテンツ復号鍵Ｋを入力とし、信号Ｓ１５を用いて信号Ｓ１３を復号し、その結果、Decryption（Encryption（コンテンツ、コンテンツ暗号鍵Ｋ）、コンテンツ復号鍵Ｋ）＝コンテンツを信号Ｓ１６として出力する。再生装置６６はコンテンツ復号装置６５により復号されたコンテンツを再生する。こうして、再生を許可された再生装置のみによりコンテンツの再生が行われる。
【０１５０】
(3.3)鍵管理機関での処理
次に、鍵管理機関での処理について図２１及至２３を参照して説明する。鍵管理機関は、演算手段としてＣＰＵ、記録手段としてＲＡＭ等のメモリを備える。即ち、鍵管理機関は、前述したように、合成数を演算する合成数演算手段と、第一秘密情報をルートノードに関連付けて記憶する第一秘密情報記憶手段と、公開情報を部分集合に関連付けて記憶する公開情報記憶手段と、第一秘密情報と公開情報に基づいてルートノードのリーフに対するマスター鍵を演算する第一マスター鍵演算手段と、マスター鍵を対応するリーフに関連付けて記憶する第一マスター鍵記憶手段と、ノードに対して、該ノードをリーフとする親ノードに設定されたマスター鍵と合成数に基づき，全単射写像関数を介して秘密情報である第二秘密情報を演算する第二秘密情報演算手段と、第二秘密情報を対応する任意のノードに関連付けて記憶する第二秘密情報記憶手段と、各ノードに設定された第二秘密情報と公開情報に基づいて各ノードのリーフに対するマスター鍵を演算する第二マスター鍵演算手段と、マスター鍵を対応するリーフに関連付けて記憶する第二マスター鍵記憶手段と、部分集合に対して、ノードに設定された第一秘密情報又は第二秘密情報と公開情報に基づいて暗号／復号鍵を演算する暗号／復号鍵演算手段と、暗号／復号鍵を対応するノードに関連付けて記憶する暗号／復号鍵記憶手段として機能する。以下で、鍵管理機関が行う具体的な処理について説明する。なお、以下で説明する処理は著作権者やディスク製造工場などの情報送信者が行う場合もある。
【０１５１】
(3.3.1)鍵情報生成処理
図２１を用いて、鍵管理機関が行う鍵情報生成処理について説明する。
【０１５２】
まず、ステップＳ１１１では、鍵管理機関は無効化する（即ち、コンテンツの受信を許可しない）受信者を決定する。
【０１５３】
次に、ステップＳ１１１で選ばれた受信者の割り当てられたリーフからルートに至るパス上に存在するノードを全て無効化ノードとする（ステップＳ１１２）。そして、処理はステップＳ１１３に進む。
【０１５４】
次に、ステップＳ１１３では、子ノード全てが無効化ノードである場合を除く全てのノードの無効化パターンに対応する暗号／復号鍵を、セッション鍵を暗号化するために選択する。
【０１５５】
次に、セッション鍵をステップＳ１１３で選択した全ての暗号鍵でそれぞれ独立に暗号化し、複数の暗号化セッション鍵からなる鍵情報を生成する（ステップｓ１１４）。こうして、生成された鍵情報は、鍵管理機関が情報送信者に配送する。
【０１５６】
(3.3.2)部分集合への暗号鍵の割り当て処理１
図２２を用いて、第１実施例にて示した鍵管理機関が行う部分集合への暗号鍵の割り当て処理について説明する。
【０１５７】
まず、ステップＳ１２１では、鍵管理機関は、２つの大きな素数（例えば512bit以上）ｑ１,ｑ２を選択し、その積Ｍを公開情報として公開する。そして、処理はステップＳ１２２に進む。
【０１５８】
次に、ステップ１２２では、鍵管理機関は、式（3-1）を満たす互いに素な２ａ−２個の自然数ｐb1b2…ba（例えば素数）を選択し、各ｐb1b2…baをノード無効化パターンｂ1ｂ2…ｂaに割り当て、ｐb1b2…baとこの割り当てを公開情報として公開する。さらに、鍵管理機関は、ランダムにｇ1∈Ｚ*Mを選ぶ。ここで、Ｚ*Mは、正整数Ｍを法とした剰余環ＺM＝｛０、１、…、Ｍ−１｝でＭと互いに素となるものの集合である。これは，法Ｍに関する既約剰余類と呼ばれ、乗法に関して群となる。また、ｇ1は鍵管理機関が秘密に保持しておく。そして、処理はステップＳ１２３に進む。
【０１５９】
ステップＳ１２３では、鍵管理機関は、ルートノードｖ1について定義されている２ａ−２個の部分集合Ｓ1,b1b2…baに割り当てる暗号／復号鍵Ｌ1,b1b2…baを式（3-3）のように割り当てる。全ての受信者を含む集合Ｓ1,11…1には式（3-4）に示す暗号／復号鍵を割り当てる。また、ｖ1の各子ノードｖj,(j＝2〜a+1)に式（3-5）に示したマスター鍵ＭＫ1,jを割り当てる。そして、処理はステップＳ１２４に進む。
【０１６０】
ステップＳ１２４では、鍵管理機関は暗号／復号鍵が割り当てられていない部分集合が存在するかどうかを判定する。存在しない場合（ステップＳ１２４；Ｎｏ）、鍵管理機関はすべての部分集合に対して暗号鍵を割り当てているので、部分集合への暗号／復号鍵の割り当て処理は終了する。
【０１６１】
一方、暗号／復号鍵が割り当てられていない部分集合が存在する場合（ステップＳ１２４；Ｙｅｓ）は、ステップＳ１２５に進み、鍵管理機関は、自身に定義された部分集合に暗号鍵が割り当てられておらず、マスター鍵は割り当てられているノードｖjについて、自身に割り当てられたマスター鍵ＭＫi,jからｇj=ＰＲＰ−１(ＭＫi,j)Dを計算する（例えば、式（3-10）に示すように計算する）。そして、処理はステップＳ１２６に進む。
【０１６２】
ステップＳ１２６では、ノードｖjについて定義される部分集合Sj,b1b2…baに上記で求めたｇjを用いて暗号／復号鍵Ｌj,b1b2…baを割り当て、各子ノードには、式（3-5）に示すマスター鍵を割り当てる。そして、処理はステップＳ１２４に戻り、再度処理を行う。ステップＳ１２４からステップＳ１２６までの処理は、すべての部分集合に暗号／復号鍵が割り当てられたとき処理は終了する。
【０１６３】
こうして、部分集合に割り当てられた暗号鍵は、情報送信者が鍵情報を用いることにより計算することができ、部分集合に割り当てられた復号鍵は、再生装置などの情報受信者も情報送信者かた鍵情報を取得することにより計算することができる。
【０１６４】
(3.3.2)部分集合への暗号鍵の割り当て処理２
ここでは、図２３を用いて、第２実施例にて示した鍵管理機関が行う部分集合への暗号鍵の割り当て処理について説明する。基本的な処理の流れは、上記の図２２を用いて説明した処理を同じである。
【０１６５】
ステップＳ１３１及びステップＳ１３２での処理は、それぞれ図２２のステップＳ１２１とステップＳ１２２での処理と同様であるので説明は省略する。
【０１６６】
ステップＳ１３３では、鍵管理機関は、ルートノードｖ1について定義されている２ａ−２個の部分集合Ｓ1,b1b2…baに割り当てる暗号／復号鍵Ｌ1,b1b2…baを式（3-3）にてＬ1,b1b2…baを求めた後、関数ｈにて暗号／復号鍵Ｔ1,b1b2…ba=ｈ（Ｌ1,b1b2…ba）を割り当てる。具体的には、Ｚ*M上にランダムに分布する要素を任意の長さｔの乱数列へ変換する写像関数ｈ（式（3-17）に示す）を用いる。全ての受信者を含む集合Ｓ1,11…1には式（3-4）に示す暗号／復号鍵を求めた後、暗号／復号鍵Ｔ1,11…1=ｈ（Ｌ1,11…1）を割り当てる。この際も写像関数ｈを用いて変換する。また、ｖ1の各子ノードｖj,(j＝2〜a+1)に式（3-5）に示したマスター鍵ＭＫ1,jを割り当てる。そして、処理はステップＳ１３４に進む。
【０１６７】
ステップＳ１３４からステップＳ１３６までの処理は、図２２に示したステップＳ１２５とステップＳ１２６までの処理の流れと同様である。即ち、鍵管理機関はすべての部分集合に暗号／復号鍵を割り当てるまで、暗号／復号鍵を割り当てる処理を続ける。ただし、ステップＳ１３６では、暗号／復号鍵Ｔj,b1b2…baの計算の際に写像関数ｈにて変換を行っている。そして、鍵管理機関は、各子ノードに、式（3-5）に示すマスター鍵を割り当てる。
【０１６８】
(3.4)情報送信者が行う処理
以下では、図２４を用いて情報送信者が行うコンテンツの暗号化処理の概要について説明する。この処理は、前述したコンテンツ記録装置５０などが行う。
【０１６９】
まず、ステップＳ２１１では、コンテンツ記録装置５０は、鍵管理機関より鍵情報を取得する。コンテンツ記録装置５０は、通信媒体経由などで鍵情報を取得することもできる。なお、コンテンツ記録装置５０が予め鍵情報を保有している場合は、ステップＳ２１１での処理は行わない。
【０１７０】
次に、ステップＳ２１２での処理は、情報配信システムが前述した図２又は図３にて示したシステムである場合に行われる処理である（したがって、図１の情報配信システムではステップＳ２１２の処理は行わなくてよい）。ここでは、コンテンツ記録装置５０は、鍵情報とともに、秘密情報と公開情報を鍵管理機関より取得し（公開情報の場合は、公開情報掲示板より取得可能）、これらに基づいて暗号鍵を計算する。ここで情報送信者が無効化されている場合、暗号鍵は求まらないが、次のステップＳ２１３でそのような場合はフローを抜けるため問題にならない。暗号鍵は、式（3-6）に保有する秘密情報と公開情報を代入して求めることができる。また、第２実施例で示した鍵管理方式を採用している場合は、式（3-6）で計算された値を前述した写像関数ｈにて変換する。以上の処理が終了すると、処理はステップＳ２１３に進む。
【０１７１】
ステップＳ２１３では、コンテンツ記録装置５０は、コンテンツを提供すべき情報受信者（コンテンツ再生装置６０）が無効化されていないかどうかを判定する。無効化されている場合は（ステップＳ２１３；Ｎｏ）、処理を終了して当該フローを抜ける。また、ステップ２１３の処理をステップ２１２の処理の前にしても構わない。この場合、無効化されている情報送信者が先に除外されるため、ステップＳ２１２では、必ず暗号鍵が求まる。
【０１７２】
無効化されていなければ（ステップＳ２１３；Ｙｅｓ）、処理はステップＳ２１４に進み、コンテンツ記録装置５０は、ステップＳ２１２にて計算された暗号鍵を用いてセッション鍵（即ち、情報暗号化用鍵）を計算する。そして、処理はステップＳ２１５に進む。
【０１７３】
ステップＳ２１５では、コンテンツ記録装置５０は、ステップＳ２１４で計算したセッション鍵を用いて伝送情報を暗号化して、暗号化情報を作成する。そして、処理はステップＳ２１６に進み、コンテンツ記録装置５０は、情報受信者にこの暗号化情報と鍵情報を送信する。
【０１７４】
(3.5)情報受信者が行う処理
次に、情報受信者が行う処理について図２５及至２８を参照して説明する。なお、情報受信者は、例えば前述したようなコンテンツ再生装置６０などがある。
【０１７５】
(3.5.1)コンテンツ復号化処理
図２５を用いて、コンテンツ再生装置６０が行うコンテンツ復号処理の概要について説明する。なお、コンテンツ復号処理は、情報送信者が行うコンテンツ暗号化処理の逆の処理であり、実質的には同じ処理を行っている。
【０１７６】
まず、ステップＳ３１１では、コンテンツ再生装置６０は、コンテンツが記録された光ディスク等の記録媒体から暗号化情報及び鍵情報を取得する。また、コンテンツ再生装置６０は、通信媒体経由などでこれらを取得することもできる。
【０１７７】
次に、ステップＳ３１２では、コンテンツ再生装置６０が保有する秘密情報、公開情報、及び取得した鍵情報を用いて復号鍵を計算する。ここで情報送信者が無効化されている場合、暗号鍵は求まらないが、次のステップＳ３１３でそのような場合はフローを抜けるため問題にならない。この場合、図３で示した情報配信システムであれば、コンテンツ再生装置６０は、公開情報掲示板から公開情報を取得する。復号鍵は、式（3-6）に秘密情報と公開情報を代入して求めることができる。また、第２実施例で示した鍵管理方式を採用している場合は、式（3-6）で計算された値を前述した写像関数ｈにて変換する。なお、ステップS３１２での復号鍵の計算に係る処理は、詳細は後述する。以上の処理が終了すると、処理はステップＳ３１３に進む。
【０１７８】
ステップＳ３１３では、コンテンツ再生装置６０は、自身が無効化の対象とされていないかを判定する。無効化されている場合は（ステップＳ３１３；Ｎｏ）、処理を終了して当該フローを抜ける。また、ステップ３１３の処理をステップ３１２の処理の前にしても構わない。この場合、無効化されている情報送信者が先に除外されるため、ステップＳ３１２では、必ず暗号鍵が求まる。
【０１７９】
無効化されていなければ（ステップＳ３１３；Ｙｅｓ）、処理はステップＳ３１４に進み、コンテンツ再生装置６０は、ステップＳ３１２にて計算された復号鍵を用いてセッション鍵（即ち、情報復号化用鍵）を計算する。そして、処理はステップＳ３１５に進む。
【０１８０】
ステップＳ３１５では、コンテンツ再生装置６０は、ステップＳ３１４で計算したセッション鍵を用いて暗号化情報を復号化して、受信情報を作成する。以上の処理にて、暗号化された情報は、コンテンツ再生装置６０にて復号化される。
【０１８１】
(3.5.2)復号鍵の計算に係る処理１
図２６を用いて、図２５のステップＳ３１２での復号鍵の計算に係る処理について具体的に説明する。図２５ではＳ３１２の復号鍵の計算と、Ｓ３１３の情報受信者が無効化されているかのチェックを別の処理として記述しているが、ここでは二つの処理をまとめて記述する。この処理は、コンテンツ再生装置６０が行うものとする。また、この処理は、第１実施例にて示した鍵管理方式にて定義された復号鍵を求める処理である。
【０１８２】
まず、ステップＳ３２１では、コンテンツ再生装置６０は、鍵情報[i1,i2,…im,Eenc(K,Li1),Eenc(K,Li2),…,Eenc(K,Lim)]のインデックス部分[i1,i2,…im]（即ち、前述したヘッダー部分である）から自身の含まれる部分集合Ｓijを決定する。そして、処理はステップＳ３２２に進む。
【０１８３】
ステップＳ３２２では、コンテンツ再生装置６０は、上記の鍵情報内に自身が含まれる部分集合が存在するかどうかを判定する。即ち、処理を行っているコンテンツ再生装置６０が、そのコンテンツの再生に関して無効化されていないかどうかを判定する。存在しない場合は（ステップＳ３２２；Ｎｏ）、復号鍵を計算する処理は終了する。
【０１８４】
一方、自身が含まれる部分集合が存在する場合は（ステップＳ３２２；Ｙｅｓ）、処理はステップＳ３２３に進み、コンテンツ再生装置６０は、カウンタをｘ＝０と設定する。このカウンタｘは、コンテンツ再生装置６０内のメモリなどに記憶させておく。そして、処理はステップＳ３２４に進む。
【０１８５】
ステップＳ３２４では、コンテンツ再生装置６０は、ステップＳ３２１で決定された自身の含まれる部分集合はレイヤlogaＮ-(ｘ+1)に存在するノードに定義されているかどうかを判定する。第１実施例にて示した鍵管理方式によれば、下位のレイヤから上位のレイヤへ向かって順にマスター鍵を計算していき、こうして求まったマスター鍵にて復号鍵が計算される。よって、下位から上位への計算は、ステップＳ３２１で決定された部分集合Ｓijに割り当てられた復号鍵Ｌijを、式（3-6）で求めることのできるマスター鍵が得られたら終了する。即ち、ステップＳ３２４での処理は、鍵情報の復号に用いる復号鍵を式（3-6）で求めることのできるマスター鍵が得られたかどうかを判定している。
【０１８６】
自身の含まれる部分集合はレイヤlogaＮ-(ｘ+1)に存在するノードに定義されていなければ（ステップＳ３２４；Ｎｏ）、処理はステップＳ３２５に進み、コンテンツ再生装置６０は、式（3-15）に従ってレイヤlogaＮ-ｘ上のノードに割り当てられているマスター鍵から、その親ノードのマスター鍵を求める。このとき、ｘ＝０であればマスター鍵にコンテンツ再生装置６０が保有する秘密情報を用いる。こうして求まったマスター鍵は、復号鍵を起算するために、コンテンツ再生装置６０内のメモリなどに記憶される。以上の処理が終了すると、処理はステップＳ３２６に進む。
【０１８７】
ステップＳ３２６では、コンテンツ再生装置６０は、カウンタｘをｘ＝ｘ＋１へと更新する。そして、処理はステップＳ３２４に戻り鍵情報の復号に用いる復号鍵を式（3-6）で求めることのできるマスター鍵が得られるまで上記の処理を繰り返す。
【０１８８】
自身の含まれる部分集合はレイヤlogaＮ-(ｘ+1)に存在するノードに定義されている場合（ステップＳ３２３；Ｙｅｓ）、処理はステップＳ３２７に進み、式（3-6）に従って、自身を含む部分集合に割り当てられた復号鍵を計算する。このようにして、コンテンツ再生装置６０は復号鍵を算出する。
【０１８９】
なお、コンテンツ記録装置５０が暗号鍵の計算を行う際も（即ち、図２４に示したステップＳ２１２での処理）、コンテンツ記録装置５０は図２６で示した処理と同様の手順で行うことができる。
【０１９０】
(3.5.3)復号鍵の計算に係る処理２
ここでは、第２実施例に係る鍵管理方式にて定義された復号鍵の計算方法について、コンテンツ再生装置の実装形態によって分けて説明する。
【０１９１】
(ａ)コンテンツ再生装置がＰＣ機器等である場合
図２７には、コンテンツ再生装置６０がＰＣ機器などであり、第１実施例に係る鍵管理方式を選択した場合の、コンテンツ再生装置６０による復号鍵の計算のための処理を示す。
【０１９２】
コンテンツ再生装置６０は、第１実施例に係る鍵管理方式にて定義された復号鍵を計算するので基本的には処理は、前述の図２６に示したものと同様である。即ち、図２７に示すステップＳ３３１からステップＳ３３６までの処理は、図２６のＳ３２１からステップＳ３２６までの処理と同様である。但し、ステップＳ３３７において、コンテンツ再生装置６０は、式（3-6）より求めた値を写像関数ｈにて変換し、こうして計算された値を復号鍵とする。
【０１９３】
(ｂ)コンテンツ再生装置がＣＥ機器等である場合
図２８には、コンテンツ再生装置６０がＣＥ機器などであり、基礎となる方法１にて示した鍵管理方式（即ち、Complete Sub-tree Methodなど）を選択した場合の、コンテンツ再生装置６０による復号鍵の計算のための処理を示す。
【０１９４】
まず、ステップＳ３４１では、コンテンツ再生装置６０は、鍵情報[i1,i2,…im,Eenc(K,Li1),Eenc(K,Li2),…,Eenc(K,Lim)]のインデックス部分[i1,i2,…im]（即ち、前述したヘッダー部分である）から自身の含まれる部分集合を決定する。そして、処理はステップＳ３４２に進む。
【０１９５】
ステップＳ３４２では、コンテンツ再生装置６０は、上記の鍵情報内に自身が含まれる部分集合が存在するかどうかを判定する。即ち、処理を行っているコンテンツ再生装置６０が、そのコンテンツの再生に関して無効化されていないかどうかを判定する。存在しない場合は（ステップＳ３４２；Ｎｏ）、復号鍵を計算する処理は終了する。
【０１９６】
自身が含まれる部分集合が存在する場合は（ステップＳ３４２；Ｙｅｓ）、処理はステップＳ３２３に進み、自身の含まれる部分集合に対応する復号鍵を選択する。基礎となる方法１で示した鍵管理方式の場合、復号鍵が直接，再生装置に保存されているので、計算する必要はない。以上の処理にて、コンテンツ再生装置６０は、復号鍵を取得することができる。
【産業上の利用可能性】
【０１９７】
本発明による鍵管理システムは、ＤＶＤプレイヤー、ＤＶＤレコーダー、ＰＤＰ、携帯音楽プレイヤー、ＰＣなど、光ディスクやネットワークなどの何らかの通信媒体を通じて著作権コンテンツを扱う各種の製品において利用することができる。
【図面の簡単な説明】
【０１９８】
【図１】鍵管理方式を適用した情報送信システムの一例を示す図である。
【図２】鍵管理方式を適用した情報送信システムの他の一例を示す図である。
【図３】鍵管理方式を適用した情報送信システムの他の一例を示す図である。
【図４】鍵管理方式に用いられる木構造の例を示す図である。
【図５】基礎となる方法１の鍵管理方式におけるノードに割り当てられる暗号／復号鍵の例を示す。
【図６】鍵管理方式における受信者の集合Ｎ＼Ｒの分割方法について示す図である。
【図７】基礎となる方法２の鍵管理方式におけるノードに割り当てられる暗号／復号鍵の例を示す。
【図８】基礎となる方法２の鍵管理方式における受信者の暗号／復号鍵の算出方法を示す図である。
【図９】本発明の第１実施例に係る鍵管理方式におけるノードに割り当てられる暗号／復号鍵の例を示す。
【図１０】本発明の第１実施例に係る鍵管理方式におけるノードに割り当てられる暗号／復号鍵の他の例を示す。
【図１１】本発明の第１実施例に係る鍵管理方式における受信者の暗号／復号鍵の算出方法を示す図である。
【図１２】各鍵管理方式の性能比較を示す図である。
【図１３】本発明の第２実施例に係る鍵管理方式の概要を説明するための図である。
【図１４】本発明の実施例に係る鍵管理方式を適用した情報送信システムを示す図である。
【図１５】本発明の実施例に係るコンテンツ記録システムの構成を示すブロック図である。
【図１６】図１６に示すコンテンツ記録システムの各部の信号内容を示す図である。
【図１７】図１６に示すコンテンツ記録システムの各部の信号内容を示す図である。
【図１８】本発明の実施例に係るコンテンツ再生システムの構成を示すブロック図である。
【図１９】図１８に示すコンテンツ再生システムの各部の信号内容を示す図である。
【図２０】図１８に示すコンテンツ再生システムの各部の信号内容を示す図である。
【図２１】鍵情報生成処理を示すフローチャートである。
【図２２】部分集合への暗号鍵の割り当て処理を示すフローチャートである。
【図２３】部分集合への暗号鍵の割り当て処理を示すフローチャートである。
【図２４】コンテンツの暗号化処理を示すフローチャートである。
【図２５】コンテンツの復号化処理を示すフローチャートである。
【図２６】第１実施例に係る鍵管理方式を用いた場合の、復号鍵の計算に係る処理を示すフローチャートである。
【図２７】第２実施例に係る鍵管理方式を用いた場合の、復号鍵の計算に係る処理を示すフローチャートである。
【図２８】第２実施例に係る鍵管理方式を用いた場合の、復号鍵の計算に係る処理を示すフローチャートである。
【符号の説明】
【０１９９】
１  鍵管理機関
２  情報送信者
３  情報受信者
４  鍵情報
７  秘密情報
８  公開情報
１２  情報提供者
１３  再生装置
１５  記録媒体
５０  コンテンツ記録装置
６０  コンテンツ再生装置
【図１】
2005333242.tif 000032
【図２】
2005333242.tif 000033
【図３】
2005333242.tif 000034
【図４】
2005333242.tif 000035
【図５】
2005333242.tif 000036
【図６】
2005333242.tif 000037
【図７】
2005333242.tif 000038
【図８】
2005333242.tif 000039
【図９】
2005333242.tif 000040
【図１０】
2005333242.tif 000041
【図１１】
2005333242.tif 000042
【図１２】
2005333242.tif 000043
【図１３】
2005333242.tif 000044
【図１４】
2005333242.tif 000045
【図１５】
2005333242.tif 000046
【図１６】
2005333242.tif 000047
【図１７】
2005333242.tif 000048
【図１８】
2005333242.tif 000049
【図１９】
2005333242.tif 000050
【図２０】
2005333242.tif 000051
【図２１】
2005333242.tif 000052
【図２２】
2005333242.tif 000053
【図２３】
2005333242.tif 000054
【図２４】
2005333242.tif 000055
【図２５】
2005333242.tif 000056
【図２６】
2005333242.tif 000057
【図２７】
2005333242.tif 000058
【図２８】
2005333242.tif 000059