(57)【要約】      （修正有）【課題】木構造を用いて鍵管理を行う鍵管理システムにおいて、受信者が保有すべき秘密情報、及び送信される鍵情報の量を増やすことなく、受信者を上限なくシステムに追加可能とする。【解決手段】鍵管理システムで、鍵管理機関は情報送信者が伝送する暗号化情報を復号するための秘密情報と公開情報を各受信者に割り当てる。また、暗号化情報を復号不可能にしたい受信者の集合から、前記集合以外の受信者のみが復号できるような鍵情報を生成する。無効化されていない受信者は、暗号化情報を受信したとき、受信者が持つ秘密情報と公開情報と受信した鍵情報を用いて情報復号化用鍵を計算し受信情報を復号する。情報復号化用鍵は、マスター鍵より定まる復号鍵にて算出される。受信者が割り当てられたリーフからノードに至るパス上に存在するノードに対してマスター鍵が定義され、下位のレイヤのノードに定義されたマスター鍵から順次求めることが可能である。【選択図】図１
2005333241.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理装置であって、
前記木構造を構成する各々のノードに対する複数のリーフの組み合わせにより表現される部分集合において互いに素である自然数を公開情報として前記部分集合と関連付けて記憶する第一記憶手段と、
前記ノードに対するリーフに関連付けてマスター鍵を記憶する第二記憶手段と、
前記部分集合に関連付けて暗号／復号鍵を記憶する第三記憶手段と、
前記木構造の最下位ノードに受信者を割り当てる手段と、
前記木構造の最下位ノードのうち受信者が割り当てられていないノードに新たなリーフを拡張すると共に、前記新たなリーフに暗号／復号鍵を割り当てる第一拡張手段と、を備えていることを特徴とする鍵管理装置。
【請求項２】
少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理装置であって、
前記木構造を構成する各々のノードに対する複数のリーフの組み合わせにより表現される部分集合において互いに素である自然数を公開情報として記憶する第一記憶手段と、
前記ノードに対するリーフに関連付けてマスター鍵を記憶する第二記憶手段と、
前記部分集合に関連付けて暗号／復号鍵を記憶する第三記憶手段と、
前記ルートノードをリーフとする新ノードを生成し、前記新ノードをルートノードとする木構造を追加すると共に、追加された木構造の各ノードに割り当てるマスター鍵を演算する第二拡張手段と、を備えていることを特徴とする鍵管理装置。
【請求項３】
任意の二つ以上の素数の積である合成数を記憶する第四記憶手段と、
前記合成数より小さく前記合成数と互いに素である任意の自然数である秘密情報が前記ルートノードと関連付けて記憶される第五記憶手段と、
前記秘密情報と前記公開情報とに基づき全単射写像関数を介して前記マスター鍵を演算する第一演算手段と、
前記マスター鍵と前記合成数に基づき前記暗号／復号鍵を演算する第二演算手段と、を備えていることを特徴とする請求項１又は２に記載の鍵管理装置。
【請求項４】
少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理方法であって、
前記木構造を構成する各々のノードに対する複数のリーフの組み合わせにより表現される部分集合において互いに素である自然数を公開情報として前記部分集合と関連付けて記憶する第一記憶工程と、
前記ノードに対するリーフに関連付けてマスター鍵を記憶する第二記憶工程と、
前記部分集合に関連付けて暗号／復号鍵を記憶する第三記憶工程と、
前記木構造の最下位ノードに受信者を割り当てる工程と、
前記木構造の最下位ノードのうち受信者が割り当てられていないノードに新たなリーフを拡張すると共に、前記新たなリーフに暗号／復号鍵を割り当てる第一拡張工程と、を備えていることを特徴とする鍵管理方法。
【請求項５】
少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理方法であって、
前記木構造を構成する各々のノードに対する複数のリーフの組み合わせにより表現される部分集合において互いに素である自然数を公開情報として記憶する第一記憶工程と、
前記ノードに対するリーフに関連付けてマスター鍵を記憶する第二記憶工程と、
前記部分集合に関連付けて暗号／復号鍵を記憶する第三記憶工程と、
前記ルートノードをリーフとする新ノードを生成し、前記新ノードをルートノードとする木構造を追加すると共に、追加された木構造の各ノードに割り当てるマスター鍵を演算する第二拡張工程と、を備えていることを特徴とする鍵管理方法。
【請求項６】
少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理コンピュータを、
前記木構造を構成する各々のノードに対する複数のリーフの組み合わせにより表現される部分集合において互いに素である自然数を公開情報として前記部分集合と関連付けて記憶する第一記憶手段と、
前記ノードに対するリーフに関連付けてマスター鍵を記憶する第二記憶手段と、
前記部分集合に関連付けて暗号／復号鍵を記憶する第三記憶手段と、
前記木構造の最下位ノードに受信者を割り当てる手段と、
前記木構造の最下位ノードのうち受信者が割り当てられていないノードに新たなリーフを拡張すると共に、前記新たなリーフに暗号／復号鍵を割り当てる第一拡張手段、として機能させることを特徴とする鍵管理プログラム。
【請求項７】
少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理コンピュータを、
前記木構造を構成する各々のノードに対する複数のリーフの組み合わせにより表現される部分集合において互いに素である自然数を公開情報として記憶する第一記憶手段と、
前記ノードに対するリーフに関連付けてマスター鍵を記憶する第二記憶手段と、
前記部分集合に関連付けて暗号／復号鍵を記憶する第三記憶手段と、
前記ルートノードをリーフとする新ノードを生成し、前記新ノードをルートノードとする木構造を追加すると共に、追加された木構造の各ノードに割り当てるマスター鍵を演算する第二拡張手段、として機能させることを特徴とする鍵管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、木構造を用い、特定の受信者の無効化機能を有する鍵管理システムに関する。
【背景技術】
【０００２】
映画、音楽などの著作物であるコンテンツの著作権を保護するために、コンテンツを暗号化して提供することが行われている。そのようなシステムの一例では、受信装置（以下、「情報送信者」又は「送信者」とも呼ぶ）や再生装置（以下では、「情報受信者」又は「受信者」とも呼ぶ）には複数の復号鍵（即ち、デバイス鍵）又は、復号鍵を生成するための秘密情報を与える。一方、暗号化されたコンテンツと、再生を許可された再生装置のみがコンテンツの復号鍵を生成できるようにした鍵情報とがネットワークを介して伝送され、又は記録媒体に記録されて情報受信者に提供される。再生を許可された受信装置や再生装置は、自身の保有する秘密情報と受信した鍵情報から、コンテンツの復号鍵を生成し、その復号鍵を使用してコンテンツを復号して再生する。一方、再生を許可されていない（無効化された）受信装置や再生装置は、コンテンツの復号鍵を生成できないので、暗号化されているコンテンツを再生することはできない。
【０００３】
ここで、受信装置や再生装置として一般的な機器を考えた場合、それが保有する秘密情報を変更する機能をその装置に持たせることは、その装置の製造コストの増加を招く、秘密情報の保管上の安全性を低下させる可能性があるなどの点であまり好ましくはない。このため、復号鍵を変更する機能を持たない受信装置や再生装置に対応した方式が望まれる。もし受信装置や再生装置が復号鍵を変更する機能を持っている場合には、その装置はある時点で得た復号鍵を、それより後の時点で送信された鍵情報を取得するために利用することができるので、通信量を低減できる可能性がある。しかし、変更機能を持たない装置は初期（例えば装置が製造されたとき）に与えられた復号鍵のみしか保有しない。よって、送信者が鍵生成情報を送信する際には、装置がその復号鍵のみを用いてコンテンツの復号鍵を得るのに必要な情報を毎回送信しなければならない。
【０００４】
このようなシステムで、鍵情報を管理するための手法として木構造を用いた鍵管理方式が提案されており、その例として「The Complete Sub-tree Method」や、「The Subset Difference Method」や、「Tree Pattern Division Method」や、「Master Key Method」（例えば、非特許文献１参照）などが知られている。これらの方式では、コンテンツの復号鍵を生成するための鍵生成情報が不正に暴露されたり漏洩した場合には、その鍵生成情報を無効化するための処理が可能となっている。
【０００５】
しかし、上記の鍵管理方式では、構築された木構造のリーフに対して受信者を割り当てるため、システム全体の受信者数の上限が決まってしまう。よって一旦構築してシステムの運用を開始した後では、前記上限を超えて受信者をシステムに追加できないといった問題点があった。
【０００６】
そこで、例えば特許文献１に記載された鍵管理システムは、上記のTree Pattern Division Methodをベースにした上で、受信者を上限なくシステムに追加する方法を採用することで上記の問題を解決している。具体的には、木構造のリーフの内、受信者の割り当てられていないリーフの数が閾値を超える場合はそのまま受信者を割り当て、閾値以下の場合は受信者の割り当てられていないリーフの下に階層を増やして新たなリーフを生成し、生成したリーフに新たな受信者を割り当てる。
【０００７】
しかしながら、特許文献１に記載された鍵管理システムでは、受信者の割り当てられていないリーフの下に階層を増やして新たにリーフを生成し、生成したリーフに新たな受信者を割り当てるため、受信者の追加を何度も繰り返すと、後に割り当てられた受信者ほど木の階層が深くなる。また、ベースとしているTree Pattern Division Methodは、木の内部ノードに対して複数の復号鍵を仮想的に割り当て、受信者の割り当てられたリーフからルートに至るパス上に存在する全てのノードに割り当てられている復号鍵を受信者は保有しなければならない。つまり、受信者の保有しなければならない復号鍵の数は、受信者の割り当てられているリーフの存在する木の階層の深さに比例するため、後に加入した受信者ほど、多くの復号鍵を保有しなければならないといった問題点がある。
【０００８】
更に、Tree Pattern Division Methodでは、木の深さが深いほど受信者の無効化のために送信する鍵情報の量が増加する。そのため、特許文献１に記載された鍵管理システムは、システム運用開始時に存在した受信者を無効化する場合の送信する鍵情報の量は小さくて済むが、最後に加入した最下層に存在するリーフに割り当てられた受信者を無効化する場合の送信する鍵情報の量は非常に大きくなるといった問題点も存在する。
【０００９】
【非特許文献１】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に分割する。
【００４０】
【数１】
2005333241.tif 000003
ここで、初期設定で上記部分集合に割り当てられた暗号／復号鍵をそれぞれＬi1、Ｌi2、…Ｌimとする。なお、Ｌi1、Ｌi2、…Ｌimは、情報送信者２にとってはセッション鍵を暗号化するための暗号鍵であり、情報受信者３にとってはセッション鍵を復号化するための復号鍵であるため、以下では暗号鍵と復号鍵をまとめて「暗号／復号鍵」とも呼ぶ。
【００４１】
(3)暗号／復号鍵Ｌi1、Ｌi2、…Ｌimを用いてセッション鍵Ｋをｍ回暗号化して式（1-2）を生成、セッション鍵Ｋと一緒に情報送信者２に配送する。
【００４２】
【数２】
2005333241.tif 000004
i1、i2、…imは、各受信者ujが鍵情報式（1-2）の中から自身に割り当てられた復号すべき暗号文Ｅenc（Ｋ,Ｌij）を特定するためのインデックス情報である。
【００４３】
ここで、情報送信者２へのセッション鍵の配送は安全に行われるものと仮定する。また、Ｅencは暗号化アルゴリズムである。本システムで用いられる暗号、復号化アルゴリズムは２種類あり、以下にまとめる（ただし、２つのアルゴリズムに全く同じものを使用しても構わない）。
【００４４】
・伝送情報Ｍの暗号化アルゴリズムＦenc、復号化アルゴリズムＦdec
セッション鍵Ｋを用いて暗号文ＣK＝Ｆenc（Ｍ、Ｋ）を生成する。高速性が要求される。
【００４５】
・セッション鍵暗号化アルゴリズムＥenc、復号化アルゴリズムＥdec
セッション鍵の配送に用いる。Ｆencよりも暗号化アルゴリズムの安全性が要求される。
【００４６】
なお、情報送信者２へのセッション鍵の配送を行わない場合は、初期設定において、送信者にも受信者と同じように秘密情報、公開情報を割り当て、それらと鍵情報からセッション鍵の計算が可能なようにしておく。
【００４７】
（ｂ）情報送信者
セッション鍵Ｋと特定の受信者のみが復号できる鍵情報を鍵管理機関から受け取り、セッション鍵Ｋを鍵として暗号化アルゴリズムＦencを用いて伝送情報Ｍを暗号化して、暗号化情報
【００４８】
【数３】
2005333241.tif 000005
を伝送する。
【００４９】
（ｃ）情報受信者
受信者ｕは、情報送信者により暗号化された次の暗号化情報を受信する。
【００５０】
【数４】
2005333241.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）基礎となる方法
次に、本発明の実施例の基礎となる方法として、Three Pattern Division Method、Master Key Method等にて用いられている鍵管理方式について示し、木構造を用いた鍵管理方式の基本的な概念について説明する。
【００５９】
（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）を満たすものとする。
【００６２】
【数５】
2005333241.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として直接受信者ｕに与える。
【００６６】
【数６】
2005333241.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は、実際の無効化子ノードと一致するパターンを選ぶ必要がある。これにより、上記の無効化ノードに対して一つの部分集合が選択される。以上の処理を全ての無効化ノードについて行い、選択された部分集合がＮ＼Ｒを構成する。このとき、無効化する受信者の数を|Ｒ|＝ｒとすると、選択される部分集合の数の上限はｒ（ｌｏｇａＮ/ｒ＋１）となる。
【００６８】
図６に、ａ＝３、Ｎ＝２７の場合の、無効化したい受信者３２（符号３０は無効化しない受信者を示す。）をｕ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）実施例に係る鍵管理方式
以下では、前述したMaster Key Methodを利用した本発明の実施例に係る鍵管理方式について説明する。なお、部分集合Ｓ1、Ｓ2、…、Ｓwの定義、及び受信者の集合Ｎ＼Ｒの分割方法は、前述した基礎となる方法で示した鍵管理方式と同様であるため、説明は省略する。
【００７０】
（1.3.1）各部分集合Ｓk,b1b2…baに対する暗号／復号鍵Ｌk,b1b2…ba、公開情報ＰＩの割り当て方法
鍵管理機関は、２つの大きな素数（例えば512bit以上）ｑ１、ｑ２を選択し、その積Ｍを公開情報として公開する。各素数ｑ１、ｑ２は鍵管理機関で秘密に保持しておく。
【００７１】
次に式（3-1）を満たす互いに素な２ａ−２個の自然数ｐb1b2…ba（例えば素数）を選択する。ここで、ｂiは上記した式（2-1）を満たすものとする。
【００７２】
【数７】
2005333241.tif 000009
以下では、２ａ−２通り存在するインデックスｂ1ｂ2…ｂaをＢと表記する。ここでλ(Ｍ)は、Carmichael関数と呼ばれ式（3-2）で与えられる。
【００７３】
【数８】
2005333241.tif 000010
鍵管理機関は、部分集合Ｓ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は鍵管理機関が秘密に保持しておく。
【００７４】
【数９】
2005333241.tif 000011
全ての受信者を含む集合Ｓ1,11…1については、割り当てる暗号／復号鍵Ｌ1,11…1を式（3-4）のように定める。
【００７５】
【数１０】
2005333241.tif 000012
ここで、任意の内部ノードｖkについて定義された部分集合の中で、ｖkのａ個の各子ノードｖjについて次のようなインデックス集合を定義する。ｖjの子孫となるリーフに割り当てられた受信者を含むような部分集合Ｓk,BのインデックスＢの集合を、インデックス集合ＡＬjと定義する。次に、各子ノードｖjについて式（3-5）で与えられるマスター鍵を定義する。
【００７６】
【数１１】
2005333241.tif 000013
式（3-5）で定義されるマスター鍵からノードｖkについて定義された部分集合Ｓk,Bの中で、インデックス集合ＡＬjに含まれるインデックスをもつ部分集合Ｓk,i(ｉ∈ＡＬj)に割り当てられた暗号／復号鍵については、式（3-6）に示すように求めることができる。
【００７７】
【数１２】
2005333241.tif 000014
しかし、インデックス集合ＡＬjに含まれないインデックスをもつ部分集合Sk,i(ｉ∈ＡＬj)については、マスター鍵ＭＫk,jのｐi乗根を求めることが困難であるため、暗号／復号鍵Ｌk,i(i∈ＡＬj)を求めることができない。
【００７８】
次に、図４に示したａ＝３、Ｎ＝２７の木構造を有する鍵管理構造があるとき、ｖ1の子ノードｖ4について定義された２ａ−２個の部分集合Ｓ4,Bに割り当てる暗号／復号鍵Ｌ4,Bについて考える。最初に、ｖ1の子ノードｖ4について式（3-7）で定義されるＭＫ1,4を計算する。
【００７９】
【数１３】
2005333241.tif 000015
ノードｖ1と同様にノードｖ4について定義されている２ａ−２個の部分集合Ｓ4,Bに割り当てる暗号／復号鍵Ｌ4,Bを、式（3-8）のように定める。
【００８０】
【数１４】
2005333241.tif 000016
ここで、ｇ4は式（3-9）により定義される。
【００８１】
【数１５】
2005333241.tif 000017
また、Pseudo Random Permutation(ＰＲＰ)は０以上でＭより小さい整数を入出力としてもつような全単射写像関数である。ただし、ここで法をＭとする冪乗剰余関数をＰＲＰとして用いてはならない。このＰＲＰは、全ての受信者に対して公開される。以下では、「ＰＲＰ-１」は、ＰＲＰの逆関数として用いる。
【００８２】
鍵管理機関は、ＭＫ1,4からＰＲＰ-１を用いてｇ4Ｅを計算した後、ｇ4ＥからそのＥ乗根を求めてｇ4を得る。鍵管理機関は法Ｍの素因数ｑ１,ｑ２を保有しているため、式（3-2）のλ(Ｍ)を求めることができる。λ(Ｍ)が与えられれば、Ｅのλ(Ｍ)を法とする乗法の逆元Ｄをユークッリドの互除法などにより求め、式（3-10）を計算すればよい。なお、上記では、ｇからＭＫを求める際にＰＲＰを用い、ＭＫからｇを算出する際にＰＲＰ-１を用いるものについて示したが、ｇからＭＫを求める際にＰＲＰ-１を用い、ＭＫからｇを算出する際にＰＲＰを用いても良い。
【００８３】
【数１６】
2005333241.tif 000018
計算されたｇ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については公開情報としての素数を割り当てていない。これは公開情報の量（素数の数）を減らすためであるが、割り当ててもよい。素数p1,11…1を割り当てたとすると、割り当てられる暗号／復号鍵Ｌ1,11…1は、式（3-11）のようになる。
【００８７】
【数１７】
2005333241.tif 000019
また、この場合、任意の内部ノードｖiについても、ｖi以下に存在する全てのリーフに割り当てられた受信者からなる部分集合Ｓi,11…1に公開情報として素数pi,11…1を割り当てていると考えても問題ない。この場合、部分集合Ｓi,11…1に割り当てられる暗号／復号鍵は式（3-12）のようになる。
【００８８】
【数１８】
2005333241.tif 000020
図８に、ａ＝３、Ｎ＝２７の場合ｖ1とｖ4について定義される部分集合への暗号／復号鍵の割り当て例を示す。上記のような割り当てを行った場合、任意の内部ノードｖi以下に存在する全てのリーフに割り当てられた受信者からなる部分集合Ｓi,11…1は二重に定義されている。これは、各内部ノードに定義される部分集合が、２ａ−２個から２ａ−１個に増えたためである。例えば、図８の部分集合Ｓ1,001と部分集合Ｓ4,111は、ともに受信者ｕ19〜ｕ27からなる集合であり、それぞれの部分集合に割り当てられている暗号／復号鍵Ｌ1,001、Ｌ4,111には式（3-13）に示す関係がある。この場合、どちらの値を用いても構わない。
【００８９】
【数１９】
2005333241.tif 000021
(1.3.2）各受信者ｕへのＳＩu,ＰＩuの割り当て方法と、ＳＩu,ＰＩuから受信者の属する部分集合Ｓk,Bに割り当てられた暗号／復号鍵ＬSk,Bの求め方
鍵管理機関は、公開情報として、２ａ−２個の素数ｐb1b2…baと合成数Ｍを受信者ｕに与える。なお、ｂiは上記した式（2-1）を満たすものとする。
【００９０】
さらに、受信者ｕの親ノードｖklogaNについて、式（3-5）で定義されるマスター鍵を受信者ｕへの秘密情報ＳＩuとして割り当てる。受信者ｕの割り当てられているリーフをｖklogaN+1とすると、受信者ｕの保有する秘密情報は式（3-14）で与えられる。
【００９１】
【数２０】
2005333241.tif 000022
ノードｖ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）により求める。
【００９３】
【数２１】
2005333241.tif 000023
ノードｖklogaNの場合と同様に、ノードｖklogaN-1ついて定義されている部分集合ＳklogaN-1,Bの中で、受信者ｕを含む部分集合ＳklogaN-1,ｌ(ｌ∈ＡＬklogaN,B)に割り当てられた暗号／復号鍵ＬklogaN-1,ｌ(ｌ∈ＡＬklogaN)についても式（3-6）に示す方法により計算できる。
【００９４】
同様の処理をルートノードｖ1まで繰り返すことにより、受信者ｕを含む全ての部分集合に割り当てられた暗号／復号鍵を求めることができる。最後に、全ての受信者を含む集合Ｓ1,11…1に割り当てられた暗号／復号鍵Ｌ1,11…1については、式（3-16）を計算することにより求まる。
【００９５】
【数２２】
2005333241.tif 000024
図９に例として、ａ＝３、Ｎ＝２７の場合の受信者ｕ20の保有する秘密情報ＳＩu20と公開情報、及びそれらからの暗号／復号鍵の計算方法を示す。ｕ20に割り当てられた秘密情報ＭＫ11,20からノードｖ11に割り当てられたマスター鍵ＭＫ4,11を算出し、このマスター鍵ＭＫ4,11からノードｖ4に割り当てられたマスター鍵ＭＫ1,4が算出される。そして、これらのマスター鍵ＭＫ11,20、ＭＫ4,11、ＭＫ1,4から受信者ｕ20が復号化に必要な暗号／復号鍵が求まる。
【００９６】
（1.3.3）効果
本実施例に係る鍵管理方式では、非特許文献１に記載された鍵管理システムと同様に、受信者の保有する秘密情報の量が受信者総数Ｎに依存しないために、受信者総数Ｎが大きい場合も常に一つ（例えば、1024bits）の秘密情報で十分である。しかし、非特許文献１に記載された鍵管理システムでは受信者の保有する公開情報（素数）の数が多くなってしまっていたが、上記の鍵管理方式では、それより少なくてよい（例えば、２ａ−２個）。よって、システム全体で使用する公開情報（素数）の数が少ないため、鍵管理機関も容易にそれを生成、管理することができる。
【００９７】
また、本実施例に係る鍵管理方式では、受信者の割り当てられたリーフからノードに至るパス上に存在するノードに対して定義された全てのマスター鍵を、下のレイヤのノードに定義されたマスター鍵から順次求めることができる方式を取っている。更に、親子の関係にある二つのノードにそれぞれ定義された部分集合に対して割り当てられる暗号／復号鍵の関係を、全単射関数ＰＲＰを用いて相関の無い値にしている。以上により、マスター鍵を用いた暗号／復号鍵の割り当てをノード毎に独立して行うことができ、公開情報の量（素数の数）を大幅に減らすことができる。
【００９８】
（2.1）第１実施例に係るシステム拡張方法
以下では、本発明の第１実施例に係るシステム拡張方法について説明する。ここでは、受信者を鍵管理システムに上限なく追加して、システムを拡張することが可能な鍵管理方式について示す。なお、基本的なアルゴリズムには、前述の（1.3）に示した鍵管理方式を用いる。また、システムの拡張は、主に鍵管理機関が行うことができる。
【００９９】
まず、第１実施例に係る木の拡張方法の具体例について、図１０及び図１１を用いて説明する。
【０１００】
図１０（ａ）に示すように、分木数がａ＝３で、２つのレイヤから構成される木があるとする。ここで，ルートノードの存在するレイヤをレイヤ０と定義し，ルートノードの子ノードの存在するレイヤをレイヤ１，孫ノードの存在するレイヤをレイヤ２というように定義しておく。この木には、まだリーフに受信者が割り当てられていない。また、木を拡張すべきか否かを判定するために、以下では閾値として「３」を用いるものとする。図１０（ａ）で示した木は、受信者が割り当てられていないリーフの数が９個あり、これは閾値よりも大きい数であるので、木は拡張されない。
【０１０１】
図１０（ｂ）に、この木にｕ1〜ｕ6までの受信者を割り当てたものを示す。図示のように、受信者は紙面左から順に、リーフに割り当てられていく。
【０１０２】
受信者の割り当てが完了したとき、受信者が割り当てられていないリーフの数は３個となる。この数は、閾値「３」以下であるので、木は拡張される。拡張された木を、図１１（ａ）に示す。図示のように、新たなレイヤ３が生成されて木が拡張されていることがわかる（符号４０にて示す部分）。図示のようにノードｖ5、ｖ6、ｖ7を親ノードとして、それぞれの下位に９つの子ノードが生成される。そして、新たな受信者ｕ7〜ｕ12を割り当てる場合、生成された上記の子ノードをリーフとして受信者が割り当てられる。
【０１０３】
上記のように受信者ｕ7〜ｕ12が割り当てられたとき、受信者が割り当てられていないリーフの数は３個となる。よって、図１１（ｂ）のように、新たなレイヤ４が生成されて木が拡張される（符号４１にて示す部分）。図示のように、ノードｖ10、ｖ11、ｖ12を親ノードとして、それぞれの下位に９つの子ノードが生成される。そして、新たな受信者ｕ13〜ｕ18を割り当てる場合、生成された上記の子ノードをリーフとして受信者が割り当てられる。
【０１０４】
以上のように、第１実施例に係るシステム拡張方法では、新たな受信者を割り当てる際、受信者が割り当てられていないリーフ数が閾値以下である場合に拡張される。図１２に示すように、新たなレイヤが上記のように順次生成されていくので、このシステムには無限に受信者を追加することができる。そのため、図示のように、受信者によって含まれるレイヤは異なっている。
【０１０５】
次に、前述した具体例において、受信者が保有する公開情報、及び秘密情報、算出される暗号／復号鍵を図１３に示す。図１３には、例として受信者ｕ4、ｕ9、ｕ13の場合を示す。ここでは、前述した本実施例に係る鍵管理方式を採用しているため、保有する公開情報は受信者全てで共通のものとなる。また、受信者は、秘密情報として１つの情報を保有するだけでよい。更に、受信者は、これらの公開情報と秘密情報を用いて、図１３の下段に示すような暗号／復号鍵を算出する。暗号鍵／復号鍵は、受信者が割り当てられているリーフからノードに至るパス上に存在するノードに定義されたマスター鍵を求めていくことで、算出することができる。したがって、受信者が含まれるレイヤの位置によって、受信者が保有すべき情報量に差は生じない。即ち、初期に加入した受信者に比べ後に加入した受信者の方が、保有すべき情報が多いということはない。
【０１０６】
また、第１実施例に係るシステム拡張方法では、新たに追加すべき受信者の数に応じて容易に木を拡張することができる。よって、木を拡張することにより受信者の増加に応じて木に含まれるノードの数を必要最小限にすることができるため、鍵管理機関は、ノードにマスター鍵及び暗号／復号鍵を割り当て際の演算量などを減らすことができる。したがって、この拡張方法は、新たに追加すべき受信者の数が少ない場合に有効となる。
【０１０７】
（2.2）第２実施例に係るシステム拡張方法
次に、本発明の第２実施例に係るシステム拡張方法について説明する。ここでも、受信者を鍵管理システムに上限なく追加して、システムを拡張することが可能な鍵管理方式について示す。なお、基本的なアルゴリズムには、前述の（1.3）に示した鍵管理方式を用いる。また、システムの拡張は、主に鍵管理機関が行う。
【０１０８】
第２実施例に係る木の拡張方法の具体例について図１４を用いて説明する。図１４（ａ）に示すように、分木数がａ＝３で、３つのレイヤから構成される木があるとする。この木には、既に受信ｕ1〜ｕ6が割り当てられている。図１４（ｂ）には、図１４（ａ）で示した木に新たな受信者ｕ7〜ｕ9を追加した図を示している。
【０１０９】
次に、図１４（ｂ）で示した状態の木に新たに受信者を割り当てることを考える。木には受信者が割り当てられていないリーフは存在しないため、新たなリーフを生成するように拡張される。これを図１４（ｃ）に示す。図示のように、ルートノードであったノードｖ1（符号４３で示す）が子ノードとなり、新たなノードｖ5（符号４４で示す）をルートノードとする木が生成される。これによって、木は符号４５で示す部分にて拡張される。ここで，鍵管理に用いる木がａ分木である場合，拡張前のルートノードを子ノードとして設定する際の設定パターンはａ通り存在するが，どのパターンを用いても構わない。図１４（ｃ）の例では３通り(左端，中央，右端)の中から，左端を選択している。ｖ5を親ノードとする子ノードはｖ1、ｖ6、ｖ7であり、ｖ6はｖ8、ｖ9、ｖ10の親ノードとなり、ｖ7も同様にｖ11、ｖ12、ｖ13の親ノードになる。そして、これらｖ8〜ｖ13の下位には新たなリーフが生成される。図１４（ｃ）では、新たな受信者ｕ10〜ｕ18が、新たに生成されたリーフに割り当てられているものを示している。
【０１１０】
以上のように、第２実施例に係るシステム拡張方法では、新たな受信者を割り当てる際、受信者が割り当てられていないリーフが存在しない場合に拡張している。図１５に示すように、鍵管理機関はシステムに無限に受信者を割り当てることができる。なお、第２実施例に係るシステム拡張方法では、全ての受信者は同じレイヤに含まれており、このレイヤは木の最下層となる。
【０１１１】
ここで、受信者が保有する公開情報、及び秘密情報、算出される暗号／復号鍵の具体例を図１６に示す。図１６には、例として受信者ｕ4、ｕ9、ｕ13の場合を示す。ここでは前述した本実施例に係る鍵管理方式を採用しているため、保有する公開情報は受信者全てで共通のものとなる。また、受信者は、秘密情報として１つの情報を保有するだけでよい。第２実施例に係るシステム拡張方法においても、初期に加入した受信者と後に加入した受信者を比較した場合に、保有すべき情報量に差異が生じることはない。
【０１１２】
更に、受信者は、これらの公開情報と秘密情報を用いて、図１６の下段に示すような暗号／復号鍵を算出する。暗号鍵／復号鍵は、受信者が割り当てられているリーフからノードに至るパス上に存在するノードに定義されたマスター鍵を求めていくことで、算出することができる。第１実施例に係るシステム拡張方法では、下位の方向に新たなルーフを生成していったが、第２実施例に係るシステム拡張方法では、新たにルートノードを作成することにより横方向にリーフを生成している。そのため、第１実施例に係るシステム拡張方法では、暗号鍵／復号鍵を算出するための演算量が、後に加入した受信者の方が多くなっている。しかし、第２実施例に係るシステム拡張方法では、全ての受信者が含まれるレイヤの位置は同じであるため、算出すべき暗号／復号鍵の個数は同じになる。よって、暗号／復号鍵を算出するための演算量にも差異は生じない。
【０１１３】
なお、第１実施例に係るシステム拡張方法と第２実施例に係るシステム拡張方法を併用し、特定の新規加入の受信者には加入前の送信情報の復号を許可し、他の加入した受信者には加入前の送信情報の復号許可を与えないという鍵管理システムを行っても良い。
【０１１４】
（2.3）実施例のコンテンツ配信システム
本発明の実施例によるコンテンツ配信システムの概略構成を図１７に示す。このシステムは、情報提供者１２が各種の記憶媒体１５をユーザに提供する。本実施例では、記憶媒体１５は、例えばＤＶＤ−ＲＯＭなどの光ディスクを含む各種の記録媒体とすることが可能である。ユーザは再生装置１３を所持し、当該再生装置１３により記録媒体１５から情報を再生する。再生装置１３は内部に情報復号化用鍵９を有している。
【０１１５】
ここで、図１に示したように、情報提供者１２は鍵管理方式の３要素における情報送信者に対応し、再生装置１３は情報受信者に対応する。即ち、情報提供者１２は、映像／音声などのコンテンツ情報を情報暗号化用鍵５を使用して暗号化し、暗号化情報６ｂとして記録媒体１５に記録する。また、情報提供者１２は、無効化の対象となる再生装置１３によっては復号できないが、無効化の対象とならない再生装置１３によれば復号可能な鍵情報４を記録媒体１５に記録する。そして、情報提供者１２は記録媒体１５を各再生装置１３のユーザに提供する。
【０１１６】
なお、再生装置１３は、前述した第１実施例又は第２実施例に係るシステム拡張方法が用いられて鍵管理機関より、各々が木構造を構成するリーフに割り当てられているものとする。
【０１１７】
無効化の対象とならない再生装置１３は、自己の有する情報復号化用鍵９で鍵情報４を復号して暗号化情報６ｂの復号鍵を取得し、これで暗号化情報６ｂを復号して映像／音声などの情報を再生することができる。一方、無効化の対象となる再生装置１３は、自己の情報復号化用鍵９により記録媒体１５内の鍵情報４を復号することができないので、暗号化情報６ｂを復号する鍵を得ることができず、暗号化情報６ｂを再生することができない。こうして、本システムでは、記録媒体１５上に記録された暗号化情報６ｂを特定の再生装置１３のみにより再生可能とする。
【０１１８】
本発明では、（1.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)システム拡張処理
ここでは、図２５及び図２６を用いて、鍵管理機関が行うシステム拡張処理について説明する。
【０１４８】
（ａ）第１実施例に係るシステム拡張方法を用いた場合
図２５は、第１実施例に係るシステム拡張方法を用いた場合の、鍵管理機関によるシステム拡張処理を示すフローチャートである。なお、以下で示す処理は、新たな受信者を追加するごとに行うものとする。
【０１４９】
まず、ステップＳ１２１では、鍵管理機関は、鍵管理に用いた木において、受信者が割り当てられていないリーフの数をカウントする。そして、処理はステップＳ１２２に進む。
【０１５０】
ステップＳ１２２では、鍵管理機関は、カウントされたリーフ数が、閾値以上であるか否かを判定する。この閾値は、鍵管理機関内のメモリ等に予め記憶させておく。
【０１５１】
リーフ数が閾値よりも大きい場合（ステップＳ１２２；Ｎｏ）は、ステップＳ１２５に進む。ステップＳ１２５では、残っているリーフに当該受信者を割り当てる。前述したように、受信者が割り当てられていないリーフの数が閾値よりも大きければ、木は拡張しない。よって、以上の処理が終了すると、処理は当該フローを抜ける。
【０１５２】
一方、リーフ数が閾値以下である場合（ステップＳ１２２；Ｙｅｓ）は、ステップＳ１２３に進む。ステップＳ１２３では、鍵管理機関は、受信者の割り当てられていないリーフの下に、階層を増やして新たなリーフを生成する。受信者が割り当てられていないリーフの数が閾値以下であるので、木は拡張される。そして、処理はステップＳ１２４に進む。  ステップＳ１２４では、鍵管理機関は、生成したリーフに当該受信者を割り当てる。以上の処理が終了すると、処理は当該フローを抜ける。
【０１５３】
なお、追加すべき受信者がまだ存在する場合には、上記の処理を再度行う。
【０１５４】
（ｂ）第２実施例に係るシステム拡張方法を用いた場合
図２６は、第２実施例に係るシステム拡張方法を用いた場合の、鍵管理機関によるシステム拡張処理を示すフローチャートである。なお、以下で示す処理は、新たな受信者を追加するごとに行うものとする。
【０１５５】
まず、ステップＳ１３１では、鍵管理機関は、鍵管理に用いた木において、受信者が割り当てられていないリーフの数をカウントする。そして、処理はステップＳ１３２に進む。
【０１５６】
ステップＳ１３２では、鍵管理機関は、カウントしたリーフの数より受信者が割り当てられていないリーフが存在するか否かを判定する。第２実施例に係るシステム拡張方法では、木が有するリーフの全てに受信者を割り当てたとき（即ち、受信者が割り当てられていないリーフが存在しなくなるとき）に木を拡張するために、上記の判定を行っている。
【０１５７】
受信者が割り当てられていないリーフが存在する場合（ステップＳ１３２；Ｎｏ）は、ステップＳ１３５に進む。ステップＳ１３５では、残っているリーフに当該受信者を割り当てる。以上の処理が終了すると、処理は当該フローを抜ける。
【０１５８】
一方、受信者が割り当てられていないリーフが存在しない場合（ステップＳ１３２；Ｙｅｓ）は、ステップＳ１３３に進む。ステップＳ１３３では、鍵管理機関は、当該木のルートノードを子ノードとするような新たな親ノードを設定し、新たに設定された親ノードをルートノードとする木を生成する。ここで，鍵管理に用いる木がａ分木である場合，拡張前のルートノードを子ノードとして設定する際の設定パターンはａ通り存在するが，どのパターンを用いても構わない。図１４（ｃ）の例では３通り(左端，中央，右端)の中から，左端を選択している。そして、処理はステップＳ１３４に進む。
【０１５９】
ステップＳ１３４では、鍵管理機関は、当該受信者を新たに生成された木のリーフに割り当てる。以上の処理が終了すると、処理は当該フローを抜ける。
【０１６０】
なお、追加すべき受信者がまだ存在する場合には、上記の処理を再度行う。
【０１６１】
(3.3.3)部分集合への暗号／復号鍵の割り当て処理
次に、鍵管理機関が行うノードに定義される部分集合への暗号／復号鍵の割り当て処理について、図２７及至図２９に示すフローチャートを用いて説明する。
【０１６２】
（ａ）システム拡張前
図２７を用いて、（1.3）にて示した鍵管理方式を採用する鍵管理機関が行う部分集合への暗号鍵の割り当て処理について説明する。ここでは、システムを拡張がされていない（即ち、システム拡張前）木を構成するノードに対して、暗号／復号鍵を割り当てる処理を示す。
【０１６３】
まず、ステップＳ１４１では、鍵管理機関は、２つの大きな素数（例えば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）Ｄを計算する（例えば、式（3-10）に示すように計算する）。そして、処理はステップＳ１４６に進む。
【０１６８】
ステップＳ１４６では、ノードｖjについて定義される部分集合Sj,b1b2…baに上記で求めたｇjを用いて暗号／復号鍵Ｌj,b1b2…baを割り当て、各子ノードには、式（3-5）に示すマスター鍵を割り当てる。そして、処理はステップＳ１４４に戻り、再度処理を行う。ステップＳ１４４からステップＳ１４６までの処理は、すべての部分集合に暗号／復号鍵が割り当てられたとき処理は終了する。
【０１６９】
こうして、部分集合に割り当てられた暗号鍵は、情報送信者が鍵情報を用いることにより計算することができ、部分集合に割り当てられた復号鍵は、再生装置などの情報受信者も情報送信者から鍵情報を取得することにより計算することができる。
【０１７０】
（ｂ）第１実施例に係るシステム拡張処理後
次に、図２８に示すフローチャートを用いて、第１実施例に係る鍵管理処理後に暗号／復号鍵を割り当てる処理について説明する。なお、以下で説明する処理は、システムの拡張がされていない（即ち、システム拡張前）木を構成するノードに仮想的に割り当てられる部分集合に対して、既に暗号／復号鍵が割り当てられていることを想定している。
【０１７１】
まず、ステップＳ１５１では、鍵管理機関は、暗号／復号鍵が割り当てられていない部分集合が存在するかどうかを判定する。存在しない場合（ステップＳ１５１；Ｎｏ）、鍵管理機関はすべての部分集合に対して暗号／復号鍵を割り当てているので、部分集合への暗号／復号鍵の割り当て処理は終了する。
【０１７２】
一方、暗号／復号鍵が割り当てられていない部分集合が存在する場合（ステップＳ１５１；Ｙｅｓ）は、ステップＳ１５２に進み、鍵管理機関は、自身に定義された部分集合に暗号／復号鍵が割り当てられておらず、マスター鍵は割り当てられているノードｖjについて、自身に割り当てられたマスター鍵ＭＫi,jからｇj=ＰＲＰ−１（ＭＫi,j）Ｄを計算する（例えば、式（3-10）に示すように計算する）。例えばシステム拡張前の図１２(レイヤ０〜２までしかノードが存在しない状態)においては，上記に該当するノードはｖ5、ｖ6、ｖ7のいずれかである。ｖ5が選択されたと仮定すると，ｖ5に割り当てられているマスター鍵ＭＫ4,5からｇ5=ＰＲＰ−１（ＭＫ4,5）Ｄを計算する。そして、処理はステップＳ１５３に進む。
ステップＳ１５３では、ノードｖjについて定義される部分集合Sj,b1b2…baに上記で求めたｇjを用いて暗号／復号鍵Ｌj,b1b2…baを割り当て、各子ノードには、式（3-5）に示すマスター鍵を割り当てる。例えば図１２のノードｖ5については，ノードｖ5について定義される部分集合S5,100，S5,010，S5,001，S5,110，S5,101，S5,011に上記で求めたｇjを用いて暗号／復号鍵Ｌ5,100，Ｌ5,010，Ｌ5,001，Ｌ5,110，Ｌ5,101，Ｌ5,011を割り当て、各子ノードには、式（3-5）に示すマスター鍵を割り当てる。そして、処理はステップＳ１５１に戻り、再度処理を行う。ステップＳ１５１からステップＳ１５３までの処理は、すべての部分集合に暗号／復号鍵が割り当てられたとき処理は終了する。
【０１７３】
以上のように、本発明の第１実施例に係るシステム拡張方法を用いることで、鍵管理機関が全ての受信者に共通の公開情報及び１つの秘密情報を割り当てるため、受信者が位置するレイヤによって保有すべき情報量に差異は生じない。
【０１７４】
（ｃ）第２実施例に係るシステム拡張処理後
次に、図２９に示すフローチャートを用いて、第２実施例に係る鍵管理処理後に暗号／復号鍵を割り当てる処理について説明する。なお、以下で説明する処理においては、システムの拡張がされていない（即ち、システム拡張前）木を構成するノードに仮想的に割り当てられる部分集合に対して、既に暗号／復号鍵が割り当てられていることを想定している。また，以下のアルゴリズムにおいて処理対象ノードという言葉を用いるが，最初はルートノードｖ1を表しているものとする。
【０１７５】
まず、ステップＳ１６１では、鍵管理機関は、以下の式（3-17）を用いて処理対象ノードｖiに割り当てられた乱数ｇiと公開情報からＰＲＰを用いて処理対象ノードのマスター鍵ＭＫj,iを求める。そして、処理はステップＳ１６２に進む。
【０１７６】
【数２３】
2005333241.tif 000025
ステップＳ１６２では，処理対象ノードｖiのマスター鍵ＭＫj,iから，ｖiの親ノードｖjに割り当てる乱数ｇjを式（3-18）を用いて求める。そして、処理はステップＳ１６３に進む。
【０１７７】
【数２４】
2005333241.tif 000026
ステップＳ１６３では，ノードｖjが拡張後ルートノードとなるかを判定する。ルートノードでない場合（ステップＳ１６３；Ｎｏ）は，処理対象ノードをｖjに変更し，ステップＳ１６１に戻る。
【０１７８】
一方，ノードｖjが拡張後ルートノードとなる場合（ステップＳ１６３；Ｙｅｓ）は，ステップＳ１６４に進み，ステップＳ１６２で求めた乱数ｇjを用いて，ノードｖjについて定義されている２ａ−２個の部分集合Ｓj,b1b2…baに割り当てる暗号／復号鍵Ｌj,b1b2…baを式（3-19）のように割り当てる。全ての受信者を含む集合Ｓ1,11…1には式（3-21）に示す暗号／復号鍵を割り当てる。また，ｖjの各子ノードｖk,(k＝j+1〜j+1+a)に式（3-20）に示したマスター鍵ＭＫj,kを割り当てる。そして、処理はステップＳ１６５に進む。
【０１７９】
【数２５】
2005333241.tif 000027
【０１８０】
【数２６】
2005333241.tif 000028
【０１８１】
【数２７】
2005333241.tif 000029
ステップＳ１６５では、鍵管理機関はノードｖj以下に存在するノードに定義される部分集合の中で，暗号／復号鍵が割り当てられていない部分集合が存在するかどうかを判定する。存在しない場合（ステップＳ１６５；Ｎｏ）、鍵管理機関はノードｖj以下に定義される全ての部分集合に対して暗号／復号鍵を割り当てているので、部分集合への暗号／復号鍵の割り当て処理は終了する。
【０１８２】
一方、暗号／復号鍵が割り当てられていない部分集合が存在する場合（ステップＳ１６５；Ｙｅｓ）は、ステップＳ１６６に進み、鍵管理機関は、自身に定義された部分集合に暗号鍵が割り当てられておらず、マスター鍵は割り当てられているノードｖdについて、自身に割り当てられたマスター鍵ＭＫc,dからｇd=ＰＲＰ−１（ＭＫc,d）Ｄを計算する（例えば、式（3-10）に示すように計算する）。そして、処理はステップＳ１６７に進む。
【０１８３】
ステップＳ１６７では、ノードｖdについて定義される部分集合Sd,b1b2…baに上記で求めたｇdを用いて暗号／復号鍵Ｌd,b1b2…baを割り当て、各子ノードには、式（3-5）に示すマスター鍵を割り当てる。そして、処理はステップＳ１６５に戻り、再度処理を行う。ステップＳ１６５からステップＳ１６７までの処理は、すべての部分集合に暗号／復号鍵が割り当てられたとき処理は終了する。
【０１８４】
以上のように、本発明の第２実施例に係るシステム拡張方法を用いることで、全ての受信者が含まれるレイヤの位置は同じであるので、受信者が算出すべき暗号／復号鍵の個数が同じになる。したがって、受信者間で、暗号／復号鍵を算出するための演算量に差異は生じない。また、第１実施例に係るシステム拡張方法を用いる場合と同様に、受信者が保有すべき公開情報及び秘密情報の情報量に関しても差異は生じない。
【０１８５】
(3.4)情報送信者が行う処理
以下では、図３０を用いて情報送信者が行うコンテンツの暗号化処理の概要について説明する。この処理は、前述したコンテンツ記録装置５０などが行う。
【０１８６】
まず、ステップＳ２１１では、コンテンツ記録装置５０は、鍵管理機関より鍵情報を取得する。コンテンツ記録装置５０は、通信媒体経由などで鍵情報を取得することもできる。なお、コンテンツ記録装置５０が予め鍵情報を保有している場合は、ステップＳ２１１での処理は行わない。
【０１８７】
次に、ステップＳ２１２での処理は、情報配信システムが前述した図２又は図３にて示したシステムである場合に行われる処理である（したがって、図１の情報配信システムではステップＳ２１２の処理は行わなくてよい）。ここでは、コンテンツ記録装置５０は、鍵情報とともに、秘密情報と公開情報を鍵管理機関より取得し（公開情報の場合は、公開情報掲示板より取得可能）、これらに基づいて暗号鍵を計算する。ここで情報送信者が無効化されている場合、暗号鍵は求まらないが、次のステップＳ２１３でそのような場合はフローを抜けるため問題にならない。暗号鍵は、式（3-6）に保有する秘密情報と公開情報を代入して求めることができる。以上の処理が終了すると、処理はステップＳ２１３に進む。
【０１８８】
ステップＳ２１３では、コンテンツ記録装置５０は、コンテンツを提供すべき情報受信者（コンテンツ再生装置６０）が無効化されていないかどうかを判定する。無効化されている場合は（ステップＳ２１３；Ｎｏ）、処理を終了して当該フローを抜ける。また、ステップ２１３の処理をステップ２１２の処理の前にしても構わない。この場合、無効化されている情報送信者が先に除外されるため、ステップＳ２１２では、必ず暗号鍵が求まる。
【０１８９】
無効化されていなければ（ステップＳ２１３；Ｙｅｓ）、処理はステップＳ２１４に進み、コンテンツ記録装置５０は、ステップＳ２１２にて計算された暗号鍵を用いてセッション鍵（即ち、情報暗号化用鍵）を計算する。そして、処理はステップＳ２１５に進む。
【０１９０】
ステップＳ２１５では、コンテンツ記録装置５０は、ステップＳ２１４で計算したセッション鍵を用いて伝送情報を暗号化して、暗号化情報を作成する。そして、処理はステップＳ２１６に進み、コンテンツ記録装置５０は、情報受信者にこの暗号化情報と鍵情報を送信する。
【０１９１】
(3.5)情報受信者が行う処理
次に、情報受信者が行う処理について図３１及び図３２を参照して説明する。なお、情報受信者は、例えば前述したようなコンテンツ再生装置６０などがある。
【０１９２】
(3.5.1)コンテンツ復号化処理
図３１を用いて、コンテンツ再生装置６０が行うコンテンツ復号処理の概要について説明する。なお、コンテンツ復号処理は、情報送信者が行うコンテンツ暗号化処理の逆の処理であり、実質的には同じ処理を行っている。
【０１９３】
まず、ステップＳ３１１では、コンテンツ再生装置６０は、コンテンツが記録された光ディスク等の記録媒体から暗号化情報及び鍵情報を取得する。また、コンテンツ再生装置６０は、通信媒体経由などでこれらを取得することもできる。
【０１９４】
次に、ステップＳ３１２では、コンテンツ再生装置６０が保有する秘密情報、公開情報、及び取得した鍵情報を用いて復号鍵を計算する。この場合、図３で示した情報配信システムであれば、コンテンツ再生装置６０は、公開情報掲示板から公開情報を取得する。復号鍵は、式（3-6）に秘密情報と公開情報を代入して求めることができる。ここで情報送信者が無効化されている場合、暗号鍵は求まらないが、次のステップＳ３１３でそのような場合はフローを抜けるため問題にならない。なお、ステップS３１２での復号鍵の計算に係る処理は、詳細は後述する。以上の処理が終了すると、処理はステップＳ３１３に進む。
【０１９５】
ステップＳ３１３では、コンテンツ再生装置６０は、自身が無効化の対象とされていないかを判定する。無効化されている場合は（ステップＳ３１３；Ｎｏ）、処理を終了して当該フローを抜ける。また、ステップ３１３の処理をステップ３１２の処理の前にしても構わない。この場合、無効化されている情報送信者が先に除外されるため、ステップＳ３１２では、必ず暗号鍵が求まる。
【０１９６】
無効化されていなければ（ステップＳ３１３；Ｙｅｓ）、処理はステップＳ３１４に進み、コンテンツ再生装置６０は、ステップＳ３１２にて計算された復号鍵を用いてセッション鍵（即ち、情報復号化用鍵）を計算する。そして、処理はステップＳ３１５に進む。
【０１９７】
ステップＳ３１５では、コンテンツ再生装置６０は、ステップＳ３１４で計算したセッション鍵を用いて暗号化情報を復号化して、受信情報を作成する。以上の処理にて、暗号化された情報は、コンテンツ再生装置６０にて復号化される。
【０１９８】
(3.5.2)暗号／復号鍵の計算に係る処理
図３２を用いて、図３１のステップＳ３１２での復号鍵（暗号／復号鍵）の計算に係る処理について具体的に説明する。図３１ではＳ３１２の復号鍵の計算と、Ｓ３１３の情報受信者が無効化されているかのチェックを別の処理として記述しているが、ここでは二つの処理をまとめて記述する。この処理は、コンテンツ再生装置６０が行うものとする。また、この処理は、（1.3）で示した鍵管理方式にて定義された復号鍵を求める処理である。
【０１９９】
まず、ステップＳ３２１では、コンテンツ再生装置６０は、鍵情報[i1,i2,…im,Eenc(K,Li1),Eenc(K,Li2),…,Eenc(K,Lim)]のインデックス部分[i1,i2,…im]（即ち、前述したヘッダー部分である）から自身の含まれる部分集合を決定する。そして、処理はステップＳ３２２に進む。
【０２００】
ステップＳ３２２では、コンテンツ再生装置６０は、上記の鍵情報内に自身が含まれる部分集合が存在するかどうかを判定する。即ち、処理を行っているコンテンツ再生装置６０が、そのコンテンツの再生に関して無効化されていないかどうかを判定する。存在しない場合は（ステップＳ３２２；Ｎｏ）、復号鍵を計算する処理は終了する。
【０２０１】
一方、自身が含まれる部分集合が存在する場合は（ステップＳ３２２；Ｙｅｓ）、処理はステップＳ３２３に進み、コンテンツ再生装置６０は、カウンタｘ＝１と設定する。このカウンタｘは、コンテンツ再生装置６０内のメモリなどに記憶させておく。そして、処理はステップＳ３２４に進む。
【０２０２】
ステップＳ３２４では、コンテンツ再生装置６０は、ステップＳ３２１で決定された自身の含まれる部分集合はレイヤ（Ｗ−ｘ）に存在するノードに定義されているか否かを判定する。ここで，Ｗは受信者の割り当てられているリーフの存在するレイヤとしている。（1.3）にて示した鍵管理方式によれば、下位のレイヤから上位のレイヤへ向かって順にマスター鍵を計算していき、こうして求まったマスター鍵にて暗号／復号鍵が計算される。よって、下位から上位への計算は，ステップＳ３２１で決定された部分集合Ｓijに割り当てられた復号鍵Ｌijを、式（3-6）で求めることのできるマスター鍵が得られたら終了する。即ち、ステップＳ３２４での処理は、鍵情報の復号に用いる復号鍵を式（3-6）で求めることのできるマスター鍵が得られたかどうかを判定している。
【０２０３】
自身の含まれる部分集合はレイヤ（Ｗ−ｘ）に存在するノードに定義されていなければ（ステップＳ３２４；Ｎｏ）、処理はステップＳ３２５に進み、コンテンツ再生装置６０は、式（3-22）を用いて，レイヤ（Ｗ−ｘ）上のノードに割り当てられているマスター鍵から、その親ノードのマスター鍵を求める。このとき、ｘ＝１であれば、マスター鍵としてコンテンツ再生装置６０が保有する秘密情報からレイヤ（Ｗ−１）に存在する親ノードのマスター鍵を求めることになる。こうして求まったマスター鍵は復号鍵を算出するために、コンテンツ再生装置６０内のメモリなどに記憶される。以上の処理が終了すると、処理はステップＳ３２６に進む。
【０２０４】
【数２８】
2005333241.tif 000030
ステップＳ３２６では、コンテンツ再生装置６０は、カウンタｘをｘ＝ｘ＋１へと更新する。そして、処理はステップＳ３２４に戻り鍵情報の復号に用いる復号鍵を式（3-6）で求めることのできるマスター鍵が得られるまで上記の処理を繰り返す。
【０２０５】
一方、自身の含まれる部分集合がレイヤ（Ｗ−ｘ）に存在するノードに定義されている場合（ステップＳ３２４；Ｙｅｓ）、処理はステップＳ３２７に進み、自身を含む部分集合に割り当てられた暗号／復号鍵を計算する。このようにして、コンテンツ再生装置６０は暗号／復号鍵を算出する。
【０２０６】
なお、コンテンツ記録装置５０が暗号／復号鍵を算出する際に行う処理も（即ち、図３０に示したステップＳ２１２での処理）、上記と同様の手順で行うことができる。
【産業上の利用可能性】
【０２０７】
本発明による鍵管理システムは、ＤＶＤプレイヤー、ＤＶＤレコーダー、ＰＤＰ、携帯音楽プレイヤー、ＰＣなど、光ディスクやネットワークなどの何らかの通信媒体を通じて著作権コンテンツを扱う各種の製品において利用することができる。
【図面の簡単な説明】
【０２０８】
【図１】鍵管理方式を適用した情報送信システムの一例を示す図である。
【図２】鍵管理方式を適用した情報送信システムの他の一例を示す図である。
【図３】鍵管理方式を適用した情報送信システムの他の一例を示す図である。
【図４】鍵管理方式に用いられる木構造の例を示す図である。
【図５】基礎となる方式１の鍵管理方式におけるノードに割り当てられる暗号／復号鍵の例を示す。
【図６】鍵管理方式における受信者の集合Ｎ＼Ｒの分割方法について示す図である。
【図７】本発明の実施例に係る鍵管理方式におけるノードに割り当てられる暗号／復号鍵の例を示す。
【図８】本発明の実施例に係る鍵管理方式におけるノードに割り当てられる暗号／復号鍵の他の例を示す。
【図９】本発明の実施例に係る鍵管理方式における受信者の暗号／復号鍵の算出方法を示す図である。
【図１０】本発明の第１実施例に係るシステム拡張方法の例を示す。
【図１１】図１０に示すシステムを更に拡張した図を示す。
【図１２】本発明の第１実施例に係るシステム拡張を繰り返し行った例を示す図である。
【図１３】本発明の第１実施例に係るシステム拡張を行った場合の、受信者が算出すべき暗号／復号鍵などを示す図である。
【図１４】本発明の第２実施例に係るシステム拡張方法の例を示す。
【図１５】本発明の第２実施例に係るシステム拡張を繰り返し行った例を示す図である。
【図１６】本発明の第２実施例に係るシステム拡張を行った場合の、受信者が算出すべき暗号／復号鍵などを示す図である。
【図１７】本発明の実施例に係る鍵管理方式を適用した情報送信システムを示す図である。
【図１８】コンテンツ記録システムの構成の一例を示すブロック図である。
【図１９】図１９に示すコンテンツ記録システムの各部の信号内容を示す図である。
【図２０】図１９に示すコンテンツ記録システムの各部の信号内容を示す図である。
【図２１】コンテンツ再生システムの構成の一例を示すブロック図である。
【図２２】図２１に示すコンテンツ再生システムの各部の信号内容を示す図である。
【図２３】図２１に示すコンテンツ再生システムの各部の信号内容を示す図である。
【図２４】鍵情報生成処理を示すフローチャートである。
【図２５】本発明の第１実施例に係るシステム拡張処理を示すフローチャートである。
【図２６】本発明の第２実施例に係るシステム拡張処理を示すフローチャートである。
【図２７】システムが拡張されてない場合の、部分集合への暗号／復号鍵の割り当てを示すフローチャートである。
【図２８】本発明の第１実施例に係るシステム拡張方法にてシステムが拡張されている場合の、部分集合への暗号／復号鍵の割り当てを示すフローチャートである。
【図２９】本発明の第２実施例に係るシステム拡張方法にてシステムが拡張されている場合の、部分集合への暗号／復号鍵の割り当てを示すフローチャートである。
【図３０】コンテンツの暗号化処理を示すフローチャートである。
【図３１】コンテンツの復号化処理を示すフローチャートである。
【図３２】暗号／復号鍵の算出処理を示すフローチャートである。
【符号の説明】
【０２０９】
１  鍵管理機関
２  情報送信者
３  情報受信者
４  鍵情報
７  秘密情報
８  公開情報
１２  情報提供者
１３  再生装置
１５  記録媒体
５０  コンテンツ記録装置
６０  コンテンツ再生装置
【図１】
2005333241.tif 000031
【図２】
2005333241.tif 000032
【図３】
2005333241.tif 000033
【図４】
2005333241.tif 000034
【図５】
2005333241.tif 000035
【図６】
2005333241.tif 000036
【図７】
2005333241.tif 000037
【図８】
2005333241.tif 000038
【図９】
2005333241.tif 000039
【図１０】
2005333241.tif 000040
【図１１】
2005333241.tif 000041
【図１２】
2005333241.tif 000042
【図１３】
2005333241.tif 000043
【図１４】
2005333241.tif 000044
【図１５】
2005333241.tif 000045
【図１６】
2005333241.tif 000046
【図１７】
2005333241.tif 000047
【図１８】
2005333241.tif 000048
【図１９】
2005333241.tif 000049
【図２０】
2005333241.tif 000050
【図２１】
2005333241.tif 000051
【図２２】
2005333241.tif 000052
【図２３】
2005333241.tif 000053
【図２４】
2005333241.tif 000054
【図２５】
2005333241.tif 000055
【図２６】
2005333241.tif 000056
【図２７】
2005333241.tif 000057
【図２８】
2005333241.tif 000058
【図２９】
2005333241.tif 000059
【図３０】
2005333241.tif 000060
【図３１】
2005333241.tif 000061
【図３２】
2005333241.tif 000062