[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP4583069B2 - 鍵管理システム、及び再生装置 - Google Patents

鍵管理システム、及び再生装置 Download PDF

Info

Publication number
JP4583069B2
JP4583069B2 JP2004147985A JP2004147985A JP4583069B2 JP 4583069 B2 JP4583069 B2 JP 4583069B2 JP 2004147985 A JP2004147985 A JP 2004147985A JP 2004147985 A JP2004147985 A JP 2004147985A JP 4583069 B2 JP4583069 B2 JP 4583069B2
Authority
JP
Japan
Prior art keywords
key
node
information
encryption
storing
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
JP2004147985A
Other languages
English (en)
Other versions
JP2005333241A (ja
Inventor
到 竹村
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Pioneer Corp
Original Assignee
Pioneer Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Pioneer Corp filed Critical Pioneer Corp
Priority to JP2004147985A priority Critical patent/JP4583069B2/ja
Priority to US11/131,296 priority patent/US20060002565A1/en
Publication of JP2005333241A publication Critical patent/JP2005333241A/ja
Application granted granted Critical
Publication of JP4583069B2 publication Critical patent/JP4583069B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N5/00—Details of television systems
    • H04N5/76—Television signal recording
    • H04N5/91—Television signal processing therefor
    • H04N5/913—Television signal processing therefor for scrambling ; for copy protection
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H04L9/0819—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s)
    • H04L9/0822—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) using key encryption key
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H04L9/0819—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s)
    • H04L9/083—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]
    • H04L9/0833—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP] involving conference or group key
    • H04L9/0836—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP] involving conference or group key using tree structure or hierarchical structure
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0894—Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/00086—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy
    • G11B20/0021—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/00086—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy
    • G11B20/0021—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier
    • G11B20/00217—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier the cryptographic key used for encryption and/or decryption of contents recorded on or reproduced from the record carrier being read from a specific source
    • G11B20/00224—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier the cryptographic key used for encryption and/or decryption of contents recorded on or reproduced from the record carrier being read from a specific source wherein the key is obtained from a remote server
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/60—Digital content management, e.g. content distribution
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N5/00—Details of television systems
    • H04N5/76—Television signal recording
    • H04N5/91—Television signal processing therefor
    • H04N5/913—Television signal processing therefor for scrambling ; for copy protection
    • H04N2005/91357—Television signal processing therefor for scrambling ; for copy protection by modifying the video signal
    • H04N2005/91364—Television signal processing therefor for scrambling ; for copy protection by modifying the video signal the video signal being scrambled

Landscapes

  • Engineering & Computer Science (AREA)
  • Signal Processing (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Multimedia (AREA)
  • Storage Device Security (AREA)

Description

本発明は、木構造を用い、特定の受信者の無効化機能を有する鍵管理システムに関する。
映画、音楽などの著作物であるコンテンツの著作権を保護するために、コンテンツを暗号化して提供することが行われている。そのようなシステムの一例では、受信装置（以下、「情報送信者」又は「送信者」とも呼ぶ）や再生装置（以下では、「情報受信者」又は「受信者」とも呼ぶ）には複数の復号鍵（即ち、デバイス鍵）又は、復号鍵を生成するための秘密情報を与える。一方、暗号化されたコンテンツと、再生を許可された再生装置のみがコンテンツの復号鍵を生成できるようにした鍵情報とがネットワークを介して伝送され、又は記録媒体に記録されて情報受信者に提供される。再生を許可された受信装置や再生装置は、自身の保有する秘密情報と受信した鍵情報から、コンテンツの復号鍵を生成し、その復号鍵を使用してコンテンツを復号して再生する。一方、再生を許可されていない（無効化された）受信装置や再生装置は、コンテンツの復号鍵を生成できないので、暗号化されているコンテンツを再生することはできない。
ここで、受信装置や再生装置として一般的な機器を考えた場合、それが保有する秘密情報を変更する機能をその装置に持たせることは、その装置の製造コストの増加を招く、秘密情報の保管上の安全性を低下させる可能性があるなどの点であまり好ましくはない。このため、復号鍵を変更する機能を持たない受信装置や再生装置に対応した方式が望まれる。もし受信装置や再生装置が復号鍵を変更する機能を持っている場合には、その装置はある時点で得た復号鍵を、それより後の時点で送信された鍵情報を取得するために利用することができるので、通信量を低減できる可能性がある。しかし、変更機能を持たない装置は初期（例えば装置が製造されたとき）に与えられた復号鍵のみしか保有しない。よって、送信者が鍵生成情報を送信する際には、装置がその復号鍵のみを用いてコンテンツの復号鍵を得るのに必要な情報を毎回送信しなければならない。
このようなシステムで、鍵情報を管理するための手法として木構造を用いた鍵管理方式が提案されており、その例として「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に分割する。
Figure 0004583069
 ここで、初期設定で上記部分集合に割り当てられた暗号／復号鍵をそれぞれＬi1、Ｌi2、…Ｌimとする。なお、Ｌi1、Ｌi2、…Ｌimは、情報送信者２にとってはセッション鍵を暗号化するための暗号鍵であり、情報受信者３にとってはセッション鍵を復号化するための復号鍵であるため、以下では暗号鍵と復号鍵をまとめて「暗号／復号鍵」とも呼ぶ。
(3)暗号／復号鍵Ｌi1、Ｌi2、…Ｌimを用いてセッション鍵Ｋをｍ回暗号化して式（1-2）を生成、セッション鍵Ｋと一緒に情報送信者２に配送する。
Figure 0004583069
 i1、i2、…imは、各受信者ujが鍵情報式（1-2）の中から自身に割り当てられた復号すべき暗号文Ｅenc（Ｋ,Ｌij）を特定するためのインデックス情報である。
ここで、情報送信者２へのセッション鍵の配送は安全に行われるものと仮定する。また、Ｅencは暗号化アルゴリズムである。本システムで用いられる暗号、復号化アルゴリズムは２種類あり、以下にまとめる（ただし、２つのアルゴリズムに全く同じものを使用しても構わない）。
・伝送情報Ｍの暗号化アルゴリズムＦenc、復号化アルゴリズムＦdec
セッション鍵Ｋを用いて暗号文ＣK＝Ｆenc（Ｍ、Ｋ）を生成する。高速性が要求される。
・セッション鍵暗号化アルゴリズムＥenc、復号化アルゴリズムＥdec
セッション鍵の配送に用いる。Ｆencよりも暗号化アルゴリズムの安全性が要求される。
なお、情報送信者２へのセッション鍵の配送を行わない場合は、初期設定において、送信者にも受信者と同じように秘密情報、公開情報を割り当て、それらと鍵情報からセッション鍵の計算が可能なようにしておく。
（ｂ）情報送信者
セッション鍵Ｋと特定の受信者のみが復号できる鍵情報を鍵管理機関から受け取り、セッション鍵Ｋを鍵として暗号化アルゴリズムＦencを用いて伝送情報Ｍを暗号化して、暗号化情報
Figure 0004583069
 を伝送する。
（ｃ）情報受信者
受信者ｕは、情報送信者により暗号化された次の暗号化情報を受信する。
Figure 0004583069
 (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）を満たすものとする。
Figure 0004583069
 部分集合Ｓ 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として直接受信者ｕに与える。
Figure 0004583069
 例えば、ａ＝３、Ｎ＝２７の場合の受信者ｕ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）を満たすものとする。
Figure 0004583069
 以下では、２ａ−２通り存在するインデックスｂ1ｂ2…ｂaをＢと表記する。ここでλ(Ｍ)は、Carmichael関数と呼ばれ式（3-2）で与えられる。
Figure 0004583069
 鍵管理機関は、部分集合Ｓ 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は鍵管理機関が秘密に保持しておく。
Figure 0004583069
 全ての受信者を含む集合Ｓ 1,11…1については、割り当てる暗号／復号鍵Ｌ1,11…1を式（3-4）のように定める。
Figure 0004583069
 ここで、任意の内部ノードｖkについて定義された部分集合の中で、ｖkのａ個の各子ノードｖjについて次のようなインデックス集合を定義する。ｖjの子孫となるリーフに割り当てられた受信者を含むような部分集合Ｓ k,BのインデックスＢの集合を、インデックス集合ＡＬjと定義する。次に、各子ノードｖjについて式（3-5）で与えられるマスター鍵を定義する。
Figure 0004583069
 式（3-5）で定義されるマスター鍵からノードｖkについて定義された部分集合Ｓ k,Bの中で、インデックス集合ＡＬjに含まれるインデックスをもつ部分集合Ｓ k,i(ｉ∈ＡＬj)に割り当てられた暗号／復号鍵については、式（3-6）に示すように求めることができる。
Figure 0004583069
 しかし、インデックス集合ＡＬjに含まれないインデックスをもつ部分集合Sk,i(ｉ∈ＡＬj)については、マスター鍵ＭＫk,jのｐi乗根を求めることが困難であるため、暗号／復号鍵Ｌk,i(i∈ＡＬj)を求めることができない。
次に、図４に示したａ＝３、Ｎ＝２７の木構造を有する鍵管理構造があるとき、ｖ1の子ノードｖ4について定義された２ａ−２個の部分集合Ｓ4,Bに割り当てる暗号／復号鍵Ｌ4,Bについて考える。最初に、ｖ1の子ノードｖ4について式（3-7）で定義されるＭＫ1,4を計算する。
Figure 0004583069
 ノードｖ1と同様にノードｖ4について定義されている２ａ−２個の部分集合Ｓ 4,Bに割り当てる暗号／復号鍵Ｌ4,Bを、式（3-8）のように定める。
Figure 0004583069
 ここで、ｇ4は式（3-9）により定義される。
Figure 0004583069
 また、Pseudo Random Permutation(ＰＲＰ)は０以上でＭより小さい整数を入出力としてもつような全単射写像関数である。ただし、ここで法をＭとする冪乗剰余関数をＰＲＰとして用いてはならない。このＰＲＰは、全ての受信者に対して公開される。以下では、「ＰＲＰ-１」は、ＰＲＰの逆関数として用いる。
鍵管理機関は、ＭＫ1,4からＰＲＰ-１を用いてｇ4 Ｅを計算した後、ｇ4 ＥからそのＥ乗根を求めてｇ4を得る。鍵管理機関は法Ｍの素因数ｑ１,ｑ２を保有しているため、式（3-2）のλ(Ｍ)を求めることができる。λ(Ｍ)が与えられれば、Ｅのλ(Ｍ)を法とする乗法の逆元Ｄをユークッリドの互除法などにより求め、式（3-10）を計算すればよい。なお、上記では、ｇからＭＫを求める際にＰＲＰを用い、ＭＫからｇを算出する際にＰＲＰ-１を用いるものについて示したが、ｇからＭＫを求める際にＰＲＰ-１を用い、ＭＫからｇを算出する際にＰＲＰを用いても良い。
Figure 0004583069
 計算されたｇ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）のようになる。
Figure 0004583069
 また、この場合、任意の内部ノードｖiについても、ｖi以下に存在する全てのリーフに割り当てられた受信者からなる部分集合Ｓ i,11…1に公開情報として素数pi,11…1を割り当てていると考えても問題ない。この場合、部分集合Ｓ i,11…1に割り当てられる暗号／復号鍵は式（3-12）のようになる。
Figure 0004583069
 図８に、ａ＝３、Ｎ＝２７の場合ｖ1とｖ4について定義される部分集合への暗号／復号鍵の割り当て例を示す。上記のような割り当てを行った場合、任意の内部ノードｖi以下に存在する全てのリーフに割り当てられた受信者からなる部分集合Ｓ i,11…1は二重に定義されている。これは、各内部ノードに定義される部分集合が、２ａ−２個から２ａ−１個に増えたためである。例えば、図８の部分集合Ｓ 1,001と部分集合Ｓ 4,111は、ともに受信者ｕ19〜ｕ27からなる集合であり、それぞれの部分集合に割り当てられている暗号／復号鍵Ｌ1,001、Ｌ4,111には式（3-13）に示す関係がある。この場合、どちらの値を用いても構わない。
Figure 0004583069
 (1.3.2）各受信者ｕへのＳＩu,ＰＩuの割り当て方法と、ＳＩu,ＰＩuから受信者の属する部分集合Ｓ k,Bに割り当てられた暗号／復号鍵Ｌ Sk,Bの求め方
鍵管理機関は、公開情報として、２ａ−２個の素数ｐb1b2…baと合成数Ｍを受信者ｕに与える。なお、ｂiは上記した式（2-1）を満たすものとする。
さらに、受信者ｕの親ノードｖklogaNについて、式（3-5）で定義されるマスター鍵を受信者ｕへの秘密情報ＳＩuとして割り当てる。受信者ｕの割り当てられているリーフをｖklogaN+1とすると、受信者ｕの保有する秘密情報は式（3-14）で与えられる。
Figure 0004583069
 ノードｖ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）により求める。
Figure 0004583069
 ノードｖklogaNの場合と同様に、ノードｖklogaN-1ついて定義されている部分集合ＳklogaN-1,Bの中で、受信者ｕを含む部分集合ＳklogaN-1,ｌ(ｌ∈ＡＬklogaN,B)に割り当てられた暗号／復号鍵ＬklogaN-1,ｌ(ｌ∈ＡＬklogaN)についても式（3-6）に示す方法により計算できる。
同様の処理をルートノードｖ1まで繰り返すことにより、受信者ｕを含む全ての部分集合に割り当てられた暗号／復号鍵を求めることができる。最後に、全ての受信者を含む集合Ｓ 1,11…1に割り当てられた暗号／復号鍵Ｌ1,11…1については、式（3-16）を計算することにより求まる。
Figure 0004583069
 図９に例として、ａ＝３、Ｎ＝２７の場合の受信者ｕ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について定義される部分集合S j,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について定義される部分集合S j,b1b2…baに上記で求めたｇjを用いて暗号／復号鍵Ｌj,b1b2…baを割り当て、各子ノードには、式（3-5）に示すマスター鍵を割り当てる。例えば図１２のノードｖ5については，ノードｖ5について定義される部分集合S 5,100，S 5,010，S 5,001，S 5,110，S 5,101，S 5,011に上記で求めたｇjを用いて暗号／復号鍵Ｌ5,100，Ｌ5,010，Ｌ5,001，Ｌ5,110，Ｌ5,101，Ｌ5,011を割り当て、各子ノードには、式（3-5）に示すマスター鍵を割り当てる。そして、処理はステップＳ１５１に戻り、再度処理を行う。ステップＳ１５１からステップＳ１５３までの処理は、すべての部分集合に暗号／復号鍵が割り当てられたとき処理は終了する。
以上のように、本発明の第１実施例に係るシステム拡張方法を用いることで、鍵管理機関が全ての受信者に共通の公開情報及び１つの秘密情報を割り当てるため、受信者が位置するレイヤによって保有すべき情報量に差異は生じない。
（ｃ）第２実施例に係るシステム拡張処理後
次に、図２９に示すフローチャートを用いて、第２実施例に係る鍵管理処理後に暗号／復号鍵を割り当てる処理について説明する。なお、以下で説明する処理においては、システムの拡張がされていない（即ち、システム拡張前）木を構成するノードに仮想的に割り当てられる部分集合に対して、既に暗号／復号鍵が割り当てられていることを想定している。また，以下のアルゴリズムにおいて処理対象ノードという言葉を用いるが，最初はルートノードｖ1を表しているものとする。
まず、ステップＳ１６１では、鍵管理機関は、以下の式（3-17）を用いて処理対象ノードｖiに割り当てられた乱数ｇiと公開情報からＰＲＰを用いて処理対象ノードのマスター鍵ＭＫj,iを求める。そして、処理はステップＳ１６２に進む。
Figure 0004583069
 ステップＳ１６２では，処理対象ノードｖiのマスター鍵ＭＫj,iから，ｖiの親ノードｖjに割り当てる乱数ｇjを式（3-18）を用いて求める。そして、処理はステップＳ１６３に進む。
Figure 0004583069
 ステップＳ１６３では，ノードｖ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を割り当てる。そして、処理はステップＳ１６５に進む。
Figure 0004583069
Figure 0004583069
Figure 0004583069
 ステップＳ１６５では、鍵管理機関はノードｖj以下に存在するノードに定義される部分集合の中で，暗号／復号鍵が割り当てられていない部分集合が存在するかどうかを判定する。存在しない場合（ステップＳ１６５；Ｎｏ）、鍵管理機関はノードｖj以下に定義される全ての部分集合に対して暗号／復号鍵を割り当てているので、部分集合への暗号／復号鍵の割り当て処理は終了する。
一方、暗号／復号鍵が割り当てられていない部分集合が存在する場合（ステップＳ１６５；Ｙｅｓ）は、ステップＳ１６６に進み、鍵管理機関は、自身に定義された部分集合に暗号鍵が割り当てられておらず、マスター鍵は割り当てられているノードｖdについて、自身に割り当てられたマスター鍵ＭＫc,dからｇd=ＰＲＰ−１（ＭＫc,d）Ｄを計算する（例えば、式（3-10）に示すように計算する）。そして、処理はステップＳ１６７に進む。
ステップＳ１６７では、ノードｖdについて定義される部分集合S d,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）を用いて，レイヤ（Ｗ−ｘ）上のノードに割り当てられているマスター鍵から、その親ノードのマスター鍵を求める。このとき、ｘ＝１であれば、マスター鍵としてコンテンツ再生装置６０が保有する秘密情報からレイヤ（Ｗ−１）に存在する親ノードのマスター鍵を求めることになる。こうして求まったマスター鍵は復号鍵を算出するために、コンテンツ再生装置６０内のメモリなどに記憶される。以上の処理が終了すると、処理はステップＳ３２６に進む。
Figure 0004583069
 ステップＳ３２６では、コンテンツ再生装置６０は、カウンタｘをｘ＝ｘ＋１へと更新する。そして、処理はステップＳ３２４に戻り鍵情報の復号に用いる復号鍵を式（3-6）で求めることのできるマスター鍵が得られるまで上記の処理を繰り返す。
一方、自身の含まれる部分集合がレイヤ（Ｗ−ｘ）に存在するノードに定義されている場合（ステップＳ３２４；Ｙｅｓ）、処理はステップＳ３２７に進み、自身を含む部分集合に割り当てられた暗号／復号鍵を計算する。このようにして、コンテンツ再生装置６０は暗号／復号鍵を算出する。
なお、コンテンツ記録装置５０が暗号／復号鍵を算出する際に行う処理も（即ち、図３０に示したステップＳ２１２での処理）、上記と同様の手順で行うことができる。
本発明による鍵管理システムは、ＤＶＤプレイヤー、ＤＶＤレコーダー、ＰＤＰ、携帯音楽プレイヤー、ＰＣなど、光ディスクやネットワークなどの何らかの通信媒体を通じて著作権コンテンツを扱う各種の製品において利用することができる。
鍵管理方式を適用した情報送信システムの一例を示す図である。 鍵管理方式を適用した情報送信システムの他の一例を示す図である。 鍵管理方式を適用した情報送信システムの他の一例を示す図である。 鍵管理方式に用いられる木構造の例を示す図である。 基礎となる方式１の鍵管理方式におけるノードに割り当てられる暗号／復号鍵の例を示す。 鍵管理方式における受信者の集合Ｎ＼Ｒの分割方法について示す図である。 本発明の実施例に係る鍵管理方式におけるノードに割り当てられる暗号／復号鍵の例を示す。 本発明の実施例に係る鍵管理方式におけるノードに割り当てられる暗号／復号鍵の他の例を示す。 本発明の実施例に係る鍵管理方式における受信者の暗号／復号鍵の算出方法を示す図である。 本発明の第１実施例に係るシステム拡張方法の例を示す。 図１０に示すシステムを更に拡張した図を示す。 本発明の第１実施例に係るシステム拡張を繰り返し行った例を示す図である。 本発明の第１実施例に係るシステム拡張を行った場合の、受信者が算出すべき暗号／復号鍵などを示す図である。 本発明の第２実施例に係るシステム拡張方法の例を示す。 本発明の第２実施例に係るシステム拡張を繰り返し行った例を示す図である。 本発明の第２実施例に係るシステム拡張を行った場合の、受信者が算出すべき暗号／復号鍵などを示す図である。 本発明の実施例に係る鍵管理方式を適用した情報送信システムを示す図である。 コンテンツ記録システムの構成の一例を示すブロック図である。 図１９に示すコンテンツ記録システムの各部の信号内容を示す図である。 図１９に示すコンテンツ記録システムの各部の信号内容を示す図である。 コンテンツ再生システムの構成の一例を示すブロック図である。 図２１に示すコンテンツ再生システムの各部の信号内容を示す図である。 図２１に示すコンテンツ再生システムの各部の信号内容を示す図である。 鍵情報生成処理を示すフローチャートである。 本発明の第１実施例に係るシステム拡張処理を示すフローチャートである。 本発明の第２実施例に係るシステム拡張処理を示すフローチャートである。 システムが拡張されてない場合の、部分集合への暗号／復号鍵の割り当てを示すフローチャートである。 本発明の第１実施例に係るシステム拡張方法にてシステムが拡張されている場合の、部分集合への暗号／復号鍵の割り当てを示すフローチャートである。 本発明の第２実施例に係るシステム拡張方法にてシステムが拡張されている場合の、部分集合への暗号／復号鍵の割り当てを示すフローチャートである。 コンテンツの暗号化処理を示すフローチャートである。 コンテンツの復号化処理を示すフローチャートである。 暗号／復号鍵の算出処理を示すフローチャートである。
符号の説明
１ 鍵管理機関
２ 情報送信者
３ 情報受信者
４ 鍵情報
７ 秘密情報
８ 公開情報
１２ 情報提供者
１３ 再生装置
１５ 記録媒体
５０ コンテンツ記録装置
６０ コンテンツ再生装置

Claims (6)

  1. 少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理装置であって、
    前記木構造を構成する各々のノードに対する複数のリーフの組み合わせにより表現される部分集合において互いに素である自然数を公開情報として前記部分集合と関連付けて記憶する第一記憶手段と、
    前記ノードに対するリーフに関連付けてマスター鍵を記憶する第二記憶手段と、
    前記部分集合に関連付けて暗号／復号鍵を記憶する第三記憶手段と、
    前記木構造の最下位ノードに受信者を割り当てる手段と、
    前記木構造の最下位ノードのうち受信者が割り当てられていないノードに新たなリーフを拡張すると共に、前記新たなリーフに暗号／復号鍵を割り当てる第一拡張手段と、
    任意の二つ以上の素数の積である合成数を記憶する第四記憶手段と、
    前記合成数より小さく前記合成数と互いに素である任意の自然数である秘密情報が前記ルートノードと関連付けて記憶される第五記憶手段と、
    前記秘密情報と前記公開情報とに基づき全単射写像関数を介して前記マスター鍵を演算する第一演算手段と、
    前記マスター鍵と前記合成数に基づき前記暗号／復号鍵を演算する第二演算手段と、を備えていることを特徴とする鍵管理装置。
  2. 少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理装置であって、
    前記木構造を構成する各々のノードに対する複数のリーフの組み合わせにより表現される部分集合において互いに素である自然数を公開情報として記憶する第一記憶手段と、
    前記ノードに対するリーフに関連付けてマスター鍵を記憶する第二記憶手段と、
    前記部分集合に関連付けて暗号／復号鍵を記憶する第三記憶手段と、
    前記ルートノードをリーフとする新ノードを生成し、前記新ノードをルートノードとする木構造を追加すると共に、追加された木構造の各ノードに割り当てるマスター鍵を演算する第二拡張手段と、
    任意の二つ以上の素数の積である合成数を記憶する第四記憶手段と、
    前記合成数より小さく前記合成数と互いに素である任意の自然数である秘密情報が前記ルートノードと関連付けて記憶される第五記憶手段と、
    前記秘密情報と前記公開情報とに基づき全単射写像関数を介して前記マスター鍵を演算する第一演算手段と、
    前記マスター鍵と前記合成数に基づき前記暗号／復号鍵を演算する第二演算手段と、を備えていることを特徴とする鍵管理装置。
  3. 少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理方法であって、
    前記木構造を構成する各々のノードに対する複数のリーフの組み合わせにより表現される部分集合において互いに素である自然数を公開情報として前記部分集合と関連付けて記憶する第一記憶工程と、
    前記ノードに対するリーフに関連付けてマスター鍵を記憶する第二記憶工程と、
    前記部分集合に関連付けて暗号／復号鍵を記憶する第三記憶工程と、
    前記木構造の最下位ノードに受信者を割り当てる工程と、
    前記木構造の最下位ノードのうち受信者が割り当てられていないノードに新たなリーフを拡張すると共に、前記新たなリーフに暗号／復号鍵を割り当てる第一拡張工程と、
    任意の二つ以上の素数の積である合成数を記憶する第四記憶工程と、
    前記合成数より小さく前記合成数と互いに素である任意の自然数である秘密情報が前記ルートノードと関連付けて記憶される第五記憶工程と、
    前記秘密情報と前記公開情報とに基づき全単射写像関数を介して前記マスター鍵を演算する第一演算工程と、
    前記マスター鍵と前記合成数に基づき前記暗号／復号鍵を演算する第二演算工程と、を備えていることを特徴とする鍵管理方法。
  4. 少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理方法であって、
    前記木構造を構成する各々のノードに対する複数のリーフの組み合わせにより表現される部分集合において互いに素である自然数を公開情報として記憶する第一記憶工程と、
    前記ノードに対するリーフに関連付けてマスター鍵を記憶する第二記憶工程と、
    前記部分集合に関連付けて暗号／復号鍵を記憶する第三記憶工程と、
    前記ルートノードをリーフとする新ノードを生成し、前記新ノードをルートノードとする木構造を追加すると共に、追加された木構造の各ノードに割り当てるマスター鍵を演算する第二拡張工程と、
    任意の二つ以上の素数の積である合成数を記憶する第四記憶工程と、
    前記合成数より小さく前記合成数と互いに素である任意の自然数である秘密情報が前記ルートノードと関連付けて記憶される第五記憶工程と、
    前記秘密情報と前記公開情報とに基づき全単射写像関数を介して前記マスター鍵を演算する第一演算工程と、
    前記マスター鍵と前記合成数に基づき前記暗号／復号鍵を演算する第二演算工程と、を備えていることを特徴とする鍵管理方法。
  5. 少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理コンピュータを、
    前記木構造を構成する各々のノードに対する複数のリーフの組み合わせにより表現される部分集合において互いに素である自然数を公開情報として前記部分集合と関連付けて記憶する第一記憶手段、
    前記ノードに対するリーフに関連付けてマスター鍵を記憶する第二記憶手段、
    前記部分集合に関連付けて暗号／復号鍵を記憶する第三記憶手段、
    前記木構造の最下位ノードに受信者を割り当てる手段、
    前記木構造の最下位ノードのうち受信者が割り当てられていないノードに新たなリーフを拡張すると共に、前記新たなリーフに暗号／復号鍵を割り当てる第一拡張手段、
    任意の二つ以上の素数の積である合成数を記憶する第四記憶手段、
    前記合成数より小さく前記合成数と互いに素である任意の自然数である秘密情報が前記ルートノードと関連付けて記憶される第五記憶手段、
    前記秘密情報と前記公開情報とに基づき全単射写像関数を介して前記マスター鍵を演算する第一演算手段、
    前記マスター鍵と前記合成数に基づき前記暗号／復号鍵を演算する第二演算手段、として機能させることを特徴とする鍵管理プログラム。
  6. 少なくとも一つのルートノードを有し、ノードの下位に複数のノードをリーフとして割り当てた木構造に関連付けて鍵情報を生成する鍵管理コンピュータを、
    前記木構造を構成する各々のノードに対する複数のリーフの組み合わせにより表現される部分集合において互いに素である自然数を公開情報として記憶する第一記憶手段、
    前記ノードに対するリーフに関連付けてマスター鍵を記憶する第二記憶手段、
    前記部分集合に関連付けて暗号／復号鍵を記憶する第三記憶手段、
    前記ルートノードをリーフとする新ノードを生成し、前記新ノードをルートノードとする木構造を追加すると共に、追加された木構造の各ノードに割り当てるマスター鍵を演算する第二拡張手段、
    任意の二つ以上の素数の積である合成数を記憶する第四記憶手段、
    前記合成数より小さく前記合成数と互いに素である任意の自然数である秘密情報が前記ルートノードと関連付けて記憶される第五記憶手段、
    前記秘密情報と前記公開情報とに基づき全単射写像関数を介して前記マスター鍵を演算する第一演算手段、
    前記マスター鍵と前記合成数に基づき前記暗号／復号鍵を演算する第二演算手段、として機能させることを特徴とする鍵管理プログラム。
JP2004147985A 2004-05-18 2004-05-18 鍵管理システム、及び再生装置 Expired - Fee Related JP4583069B2 (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP2004147985A JP4583069B2 (ja) 2004-05-18 2004-05-18 鍵管理システム、及び再生装置
US11/131,296 US20060002565A1 (en) 2004-05-18 2005-05-18 Key management system and playback apparatus

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2004147985A JP4583069B2 (ja) 2004-05-18 2004-05-18 鍵管理システム、及び再生装置

Publications (2)

Publication Number Publication Date
JP2005333241A JP2005333241A (ja) 2005-12-02
JP4583069B2 true JP4583069B2 (ja) 2010-11-17

Family

ID=35487619

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2004147985A Expired - Fee Related JP4583069B2 (ja) 2004-05-18 2004-05-18 鍵管理システム、及び再生装置

Country Status (2)

Country Link
US (1) US20060002565A1 (ja)
JP (1) JP4583069B2 (ja)

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100803596B1 (ko) * 2005-11-25 2008-02-19 삼성전자주식회사 폐기 메커니즘 상에서 외부 디바이스 또는 서비스를이용하는 복호화 방법 및 장치, 이를 위한 복호화 지원방법 및 장치
US8290157B2 (en) * 2007-02-20 2012-10-16 Sony Corporation Identification of a compromised content player
US8989388B2 (en) * 2008-04-02 2015-03-24 Cisco Technology, Inc. Distribution of storage area network encryption keys across data centers
WO2009157050A1 (ja) * 2008-06-23 2009-12-30 三菱電機株式会社 情報処理装置及びプログラム
US9757071B1 (en) 2016-04-29 2017-09-12 Bayer Healthcare Llc System and method for suppressing noise from electrocardiographic (ECG) signals

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2002077131A (ja) * 2000-04-06 2002-03-15 Sony Corp 情報処理システム、情報処理方法、および情報記録媒体、並びにプログラム提供媒体
JP2003204321A (ja) * 2001-10-26 2003-07-18 Matsushita Electric Ind Co Ltd 著作物保護システム及び鍵管理装置
JP2003273862A (ja) * 2002-01-30 2003-09-26 Sony Corp 放送暗号化方法、放送復号方法及び受信装置

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4934923B2 (ja) * 2001-08-09 2012-05-23 ソニー株式会社 情報記録装置、情報再生装置、および情報記録方法、情報再生方法、並びにコンピュータ・プログラム
US7308583B2 (en) * 2002-01-25 2007-12-11 Matsushita Electric Industrial Co., Ltd. Data distribution system
AU2003260951A1 (en) * 2002-09-03 2004-03-29 Matsushita Electric Industrial Co., Ltd. Region restrictive playback system

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2002077131A (ja) * 2000-04-06 2002-03-15 Sony Corp 情報処理システム、情報処理方法、および情報記録媒体、並びにプログラム提供媒体
JP2003204321A (ja) * 2001-10-26 2003-07-18 Matsushita Electric Ind Co Ltd 著作物保護システム及び鍵管理装置
JP2003273862A (ja) * 2002-01-30 2003-09-26 Sony Corp 放送暗号化方法、放送復号方法及び受信装置

Also Published As

Publication number Publication date
JP2005333241A (ja) 2005-12-02
US20060002565A1 (en) 2006-01-05

Similar Documents

Publication Publication Date Title
US7757082B2 (en) Efficient revocation of receivers
JP2001358707A (ja) 暗号鍵ブロックを用いた情報処理システムおよび情報処理方法、並びにプログラム提供媒体
EP1249962A1 (en) Information processing system and method
KR100777906B1 (ko) 정보 처리 시스템 및 방법
JP2002198948A (ja) 情報処理システム、情報処理方法、情報処理装置、および情報記録媒体、並びにプログラム記録媒体
JP2002198952A (ja) 情報処理システム、および情報処理方法、並びにプログラム記録媒体
JP2001352321A (ja) 情報処理システム、情報処理方法、および情報記録媒体、並びにプログラム提供媒体
RU2369024C2 (ru) Система защиты информационного содержания, устройство генерации данных ключей и устройство воспроизведения
JP2005286959A (ja) 情報処理方法、復号処理方法、および情報処理装置、並びにコンピュータ・プログラム
JP2006086568A (ja) 情報処理方法、復号処理方法、および情報処理装置、並びにコンピュータ・プログラム
JP2005333242A (ja) 鍵管理システム、及び再生装置
JP4583069B2 (ja) 鍵管理システム、及び再生装置
JP2004120008A (ja) 鍵管理システム
JP4120135B2 (ja) 暗号鍵ブロックを用いた情報処理システムおよび情報処理方法、並びにプログラム提供媒体
JP4561074B2 (ja) 情報処理装置、および情報処理方法、並びにコンピュータ・プログラム
JP4161859B2 (ja) 情報処理装置、情報記録媒体、および情報処理方法、並びにコンピュータ・プログラム
US20050169481A1 (en) Method of assigning user keys for broadcast encryption
JP2003204321A (ja) 著作物保護システム及び鍵管理装置
JP2004229128A (ja) 暗号データ配信システム、および情報処理装置、情報処理方法、並びにコンピュータ・プログラム
JP4635459B2 (ja) 情報処理方法、復号処理方法、および情報処理装置、並びにコンピュータ・プログラム
US20070147603A1 (en) Copyright protection system, modular exponentiation operation apparatus, and modular exponentiation operation method
JP2004248272A (ja) コンテンツ再生のための鍵を管理する方法
JP4638176B2 (ja) 著作権保護システム、べき乗剰余演算装置、演算装置、鍵管理装置、再生装置、記録装置、記録媒体、べき乗剰余演算方法、演算方法、及びプログラム
JP2005191805A (ja) 暗号文配信方法、情報処理装置、および情報処理方法、並びにコンピュータ・プログラム
JP2005252916A (ja) 情報処理方法、復号処理方法、および情報処理装置、並びにコンピュータ・プログラム

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20070412

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20100629

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20100729

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20100824

A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20100831

R150 Certificate of patent or registration of utility model

Free format text: JAPANESE INTERMEDIATE CODE: R150

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130910

Year of fee payment: 3

LAPS Cancellation because of no payment of annual fees