(57)【要約】【課題】放送暗号化システムにおいて、効率的に受信機を無効にする。【解決手段】複数の受信機のそれぞれに対し、２つ以上のサブキーを導出するために用いることができるマスタキーを割り当て、１つ以上の受信機を無効にし、無効にされていない受信機のマスタキーについて、このマスタキーから導出できるとともに、無効にされた全ての受信機のマスタキーからは導出できないサブキーを選択し、選択された各サブキーについて、サブキーを用いてデータを暗号化して暗号テキストを生成し、暗号化された暗号テキストを複数の受信機に送信する。【選択図】図７
2010081656.tif 000002
【特許請求の範囲】
【請求項１】
複数の受信機のそれぞれに対し、２つ以上のサブキーを導出するために用いることができるマスタキーを割り当てるステップと、
１つ以上の受信機を無効にし、１つ以上の受信機を有効なまま残すステップと、
無効にされていない受信機のマスタキーについて、該マスタキー及び他の大部分のマスタキーから導出できるとともに、上記無効にされた全ての受信機のマスタキーからは導出できないサブキーを選択するステップと、
上記選択された各サブキーについて、該サブキーを用いてデータを暗号化して暗号テキストを生成するステップと、
上記暗号化された暗号テキストを複数の受信機に送信するステップとを有する放送暗号化方法。
【請求項２】
対応する受信機に各マスタキーを送信するステップを有する請求項１記載の放送暗号化方法。
【請求項３】
上記各暗号テキストは、暗号化されたコンテンツファイルを復号するためのコンテンツキーを暗号化したものであることを特徴とする請求項１記載の放送暗号化方法。
【請求項４】
コンテンツキーを用いてコンテンツファイルを暗号化するステップを有する請求項１記載の放送暗号化方法。
【請求項５】
上記コンテンツキーを用いてコンテンツファイルを暗号化するステップは、コンテンツキーからサブコンテンツキーを導出し、導出されたサブコンテンツキーを用いてコンテンツファイルを暗号化するステップを有することを特徴とする請求項４記載の放送暗号化方法。
【請求項６】
各受信機に暗号化されたコンテンツファイルを送信するステップを有する請求項４記載の放送暗号化方法。
【請求項７】
上記暗号化されたコンテンツファイルは、記録媒体に格納されたデータとして各受信機に送付されることを特徴とする請求項６記載の放送暗号化方法。
【請求項８】
各受信機について、個別の記録媒体に暗号化されたコンテンツファイルを格納するステップを有する請求項６記載の放送暗号化方法。
【請求項９】
上記各受信機は、媒体再生装置であり、上記暗号化された暗号テキストは、該媒体製造装置の製造業者によって該媒体製造装置に格納されることを特徴とする請求項１記載の放送暗号化方法。
【請求項１０】
上記無効にされた受信機に割り当てられているマスタキーから導出できる各サブキーを無効にするステップを有する請求項１記載の放送暗号化方法。
【請求項１１】
上記各受信機に対し、上記マスタキーとともに用いてサブキーを導出することができる１つ以上の暗号化パラメータを送信するステップを有する請求項１記載の放送暗号化方法。
【請求項１２】
上記少なくとも１つの暗号化パラメータは素数であることを特徴とする請求項１１記載の放送暗号化方法。
【請求項１３】
上記選択されたサブキーを用いて暗号テキストを暗号化するステップは、該選択されたサブキーにハッシュ関数を適用し、ハッシュキーを生成し、該ハッシュキーを用いて暗号テキストを暗号化するステップを有することを特徴とする請求項１記載の放送暗号化方法。
【請求項１４】
根と、複数の内部ノードと、複数の葉とを有する階層的キー木を定義するステップであって、上記各サブキーは、該階層的キー木の各ノードに対応するノードキーであるステップと、
上記各受信機を上記階層的キー木の葉に割り当てるステップと、
上記階層的キー木において、無効にされている受信機の葉から根までのパス上のノードに割り当てられている各ノードキーを無効にし、無効にされていないノードキーを残すステップとを有し、
上記各マスタキーを用いて、上記階層的キー木において、該マスタキーに対応する受信機の葉から根までのパス上のノードのノードキーを導出でき、
上記マスタキーについてサブキーを選択するステップは、無効にされていないノードキーに対応する階層的キー木内の１つ以上のノードをそれぞれ含む１つ以上のサブ木を定義するステップを含み、各サブ木の根は、無効にされているノードキーに対応する子ノードを有さず、
上記暗号テキストを暗号化するステップは、上記１つ以上のサブ木の根の１つに対応するノードキーを用いて暗号テキストを暗号化するステップを含むことを特徴とする請求項１記載の放送暗号化方法。
【請求項１５】
上記階層的キー木に基づいて表現木を生成するステップを有し、
上記表現木は、選択されたノードキーに対応する全てのノードと、該選択されたノードキー及び根に対応するノード間の全てのノードとを含み、該選択されたノードキーは、該表現木の葉に対応することを特徴とする請求項１４記載の放送暗号化方法。
【請求項１６】
上記表現木の各ノードには、該ノードの子が表現木に含まれているか否かを反映する値が割り当てられており、
上記表現木のノードに割り当てられている値を表現する表現コードを生成するステップと、
上記表現コードを各受信機に送信するステップとを有することを特徴とする請求項１５記載の放送暗号化方法。
【請求項１７】
上記階層的キー木の１つ以上のノードを表現する表現値であって、対応するノードに表現値を有する子が存在する場合、該対応するノードのどの子が表現値を有しているかを示し、及び該対応するノードのノードキーが選択されている場合、どのノードキーが選択されているかを示す表現値を含む表現コードを生成するステップと、
上記表現コードを各受信機に送信するステップとを有する請求項１４記載の放送暗号化方法。
【請求項１８】
上記複数の受信機は、ｊ＝１，・・・，ＮとするＮ個の受信機ｕｊであり、
２つの素数ｑ１及びｑ２を選択するステップと、
ｑ１及びｑ２を乗算してＭを算出するステップと、
ｉ＝１，・・・，２Ｎ−１として２Ｎ−１個の素数ｐｉを選択するステップと、
上記階層的キー木の各ノードに各選択された素数ｐｉを割り当てるステップと、
以下の式に基づいてＴを算出するステップと、
【数１】
2010081656.tif 000080
Ｋ０∈Ｚ＊Ｍを満たすＫ０を選択するステップと、
以下の式に基づいてｉ個のノードキーＮＫｉを生成するステップと、
【数２】
2010081656.tif 000081
ｗｊを受信機ｕｊのノードから根までのパス上のノードに割り当てられている各素数ｐｉの積として、以下の式に基づいてマスタキーＭＫｊを生成するステップとを有する請求項１４記載の放送暗号化方法。
【数３】
2010081656.tif 000082
【請求項１９】
全ての受信機に、上記Ｍの値と、上記選択された素数ｐｉと、各素数ｐｉがどのノードに割り当てられているかを示す情報とを放送するステップを有する請求項１８記載の放送暗号化方法。
【請求項２０】
各サブキーは、各サブセットに対応するサブセットキーであり、該各サブセットは、階層的キー木のノードに対応することを特徴とする請求項１記載の放送暗号化方法。
【請求項２１】
根と、内部ノードと、複数の葉とを有し、該根も内部ノードである階層的キー木を定義するステップと、
上記階層的キー木の各内部ノードについて、複数のサブセットを定義するステップであって、各サブセットは、該サブセットに対応する１つ以上の子ノードを示し、各サブキーは、各サブセットに対応し、及び該サブセットによって示される子ノードに対応するステップと、
上記階層的キー木の葉に各受信機を割り当てるステップと、
上記階層的キー木において、無効にされた受信機の葉から根までのパス上のノードに対応する各サブセットキーを無効にし、有効な１つ以上のサブセットを残すステップとを有し、
上記各マスタキーを用いて、上記階層的キー木において、該マスタキーに対応する受信機の葉から根までのパス上のノードのノードキーを導出でき、
上記マスタキーについてサブキーを選択するステップは、無効にされていないノードキーに対応する階層的キー木内の１つ以上のノードをそれぞれ含む１つ以上のサブ木を定義するステップを含み、各サブ木の根は、無効にされているノードキーに対応する子ノードを有さず、
上記暗号テキストを暗号化するステップは、上記１つ以上のサブ木の根の１つに対応するサブセットキーを用いて暗号テキストを暗号化するステップを含むことを特徴とする請求項１記載の放送暗号化方法。
【請求項２２】
上記階層的キー木に基づいて表現木を生成するステップを有し、
上記表現木は、選択されたサブセットキーに対応する全てのノードと、該選択されたサブセットキー及び根に対応するノード間の全てのノードとを含むことを特徴とする請求項２１記載の放送暗号化方法。
【請求項２３】
上記表現木の各ノードには、該ノードの子が表現木に含まれているか否かを反映する子値と、ノードに対応するサブセットキーが選択されている場合、どのサブセットキーが選択されているかを示すサブセット値とが割り当てられており、
上記表現木のノードに割り当てられている値を表現する表現コードを生成するステップと、
上記表現コードを各受信機に送信するステップとを有することを特徴とする請求項２２記載の放送暗号化方法。
【請求項２４】
上記階層的キー木の１つ以上のノードを表現する表現値であって、対応するノードに表現値を有する子が存在する場合、該対応するノードのどの子が表現値を有しているかを示し、及び該対応するノードのサブセットキーが選択されている場合、どのサブセットキーが選択されているかを示す表現値を含む表現コードを生成するステップと、
上記表現コードを各受信機に送信するステップとを有する請求項２１記載の放送暗号化方法。
【請求項２５】
上記複数の受信機は、ｊ＝１，・・・，ＮとするＮ個の受信機ｕｊであり、
上記階層的キー木は、ｋ＝１，・・・，（Ｎ−１）／（ａ−１）とし、ルートを内部ノードｖ１として、Ｎ個の葉と内部ノードｖｋを有する根の付いた完全ａ進木であり、
２つの素数ｑ１及びｑ２を選択するステップと、
ｑ１及びｑ２を乗算してＭを算出するステップと、
各ノードｖｋについて、以下の条件
【数４】
2010081656.tif 000083
を満たす２ａ−２個のサブセット
【数５】
2010081656.tif 000084
を定義するステップと、
根についてＳ１，１１・・・１を定義するステップと、
以下の条件
【数６】
2010081656.tif 000085
を満たす（２ａ−２）＊（Ｎ−１）／（ａ−１）＋１個の素数
【数７】
2010081656.tif 000086
を選択するステップと、
上記選択された素数
【数８】
2010081656.tif 000087
を各サブセット
【数９】
2010081656.tif 000088
に割り当てるステップと、
以下の式に基づいてＴを生成するステップと、
【数１０】
2010081656.tif 000089
Ｋ＝∈Ｚ＊Ｍとして、値Ｋをランダムに選択するステップと、
以下の式に基づき、
【数１１】
2010081656.tif 000090
２ａ−２個のサブセットキー
【数１２】
2010081656.tif 000091
を生成するステップと、
ｗｊを内部ノードｖｋに割り当てられ、受信機ｕｊのノードから根までのパス上の子ノードに割り当てられているサブセットキー
【数１３】
2010081656.tif 000092
に対応するサブセット
【数１４】
2010081656.tif 000093
に割り当てられている全ての素数
【数１５】
2010081656.tif 000094
の積として、以下の式に基づいて、各受信機ｕｊに対するマスタキーＭＫｊを生成するステップとを有する請求項２１記載の放送暗号化方法。
【数１６】
2010081656.tif 000095
【請求項２６】
全ての受信機に、上記Ｍの値と、上記選択された素数
【数１７】
2010081656.tif 000096
と、各素数
【数１８】
2010081656.tif 000097
がどのサブセット
【数１９】
2010081656.tif 000098
に割り当てられているかを示す情報とを放送するステップを有する請求項２５記載の放送暗号化方法。
【請求項２７】
根と、内部ノードと、複数の葉とを有し、該根も内部ノードである階層的キー木を定義するステップと、
上記階層的キー木の各内部ノードについて、複数のサブセットを定義するステップであって、各サブセットは、該サブセットに対応する１つ以上の子ノードを示し、各サブキーは、各サブセットに対応し、及び該サブセットによって示される子ノードに対応するステップと、
上記階層的キー木の葉に各受信機を割り当てるステップと、
上記階層的キー木において、無効にされた受信機の葉から根までのパス上のノードに対応する各サブセットキーを無効にし、有効な１つ以上のサブセットを残すステップとを有し、
各マスタキーを複数の受信機に割り当てるステップは、１つ以上のマスタキーを各受信機に割り当てるステップを有し、受信機には、上記階層的キー木における受信機の葉から根までのパス上の、根を含む各内部ノードについて１つのマスタキーが割り当てられ、
上記各マスタキーを用いて、上記階層的キー木において、該マスタキーに対応する受信機の葉から根までのパス上の各ノードのノードキーを導出でき、
上記マスタキーについてサブキーを選択するステップは、無効にされていないノードキーに対応する階層的キー木内の１つ以上のノードをそれぞれ含む１つ以上のサブ木を定義するステップを含み、各サブ木の根は、無効にされているノードキーに対応する子ノードを有さず、
上記暗号テキストを暗号化するステップは、上記１つ以上のサブ木の根の１つに対応するサブセットキーを用いて暗号テキストを暗号化するステップを含むことを特徴とする請求項１記載の放送暗号化方法。
【請求項２８】
上記階層的キー木に基づいて表現木を生成するステップを有し、
上記表現木は、選択されたサブセットキーに対応する全てのノードと、該選択されたサブセットキー及び根に対応するノード間の全てのノードとを含むことを特徴とする請求項２７記載の放送暗号化方法。
【請求項２９】
上記表現木の各ノードには、該ノードの子が表現木に含まれているか否かを反映する子値と、ノードに対応するサブセットキーが選択されている場合、どのサブセットキーが選択されているかを示すサブセット値とが割り当てられており、
上記表現木のノードに割り当てられている値を表現する表現コードを生成するステップと、
上記表現コードを各受信機に送信するステップとを有することを特徴とする請求項２８記載の放送暗号化方法。
【請求項３０】
上記階層的キー木の１つ以上のノードを表現する表現値であって、対応するノードに表現値を有する子が存在する場合、該対応するノードのどの子が表現値を有しているかを示し、及び該対応するノードのサブセットキーが選択されている場合、どのサブセットキーが選択されているかを示す表現値を含む表現コードを生成するステップと、
上記表現コードを各受信機に送信するステップとを有する請求項２７記載の放送暗号化方法。
【請求項３１】
上記複数の受信機は、ｊ＝１，・・・，ＮとするＮ個の受信機ｕｊであり、
上記階層的キー木は、ｋ＝１，・・・，（Ｎ−１）／（ａ−１）とし、ルートを内部ノードｖ１として、Ｎ個の葉と内部ノードｖｋを有する根の付いた完全ａ進木であり、
２つの素数ｑ１及びｑ２を選択するステップと、
ｑ１及びｑ２を乗算してＭを算出するステップと、
各ノードｖｋについて、以下の条件
【数２０】
2010081656.tif 000099
を満たす２ａ−２個のサブセット
【数２１】
2010081656.tif 000100
を定義するステップと、
根についてＳ１，１１・・・１を定義するステップと、
各内部ノードｖｋについて、以下の条件
【数２２】
2010081656.tif 000101
を満たす２ａ−１個の素数
【数２３】
2010081656.tif 000102
を選択するステップと、
選択された各素数
【数２４】
2010081656.tif 000103
の積としてＴを算出するステップと、
各内部ノードｖｋについて、Ｋｋ∈ＺＭ＊を満たすＫｋを選択するステップと、
以下の式に基づき、
【数２５】
2010081656.tif 000104
各サブセット
【数２６】
2010081656.tif 000105
についてサブセットキー
【数２７】
2010081656.tif 000106
を生成するステップと、
ｗｊ，ｋを内部ノードｖｋに割り当てられ、受信機ｕｊのノードから根までのパス上の子ノードに割り当てられているサブセットに割り当てられている選択された素数
【数２８】
2010081656.tif 000107
の積として、以下の式に基づいて、各受信機ｕｊにｌｏｇａＮ個のマスタキーを生成するステップとを有する請求項２７記載の放送暗号化方法。
【数２９】
2010081656.tif 000108
【請求項３２】
全ての受信機に、上記Ｍの値と、上記選択された素数
【数３０】
2010081656.tif 000109
と、各素数
【数３１】
2010081656.tif 000110
がどのサブセット
【数３２】
2010081656.tif 000111
に割り当てられているかを示す情報とを放送するステップを有する請求項２５記載の放送暗号化方法。
【請求項３３】
受信機において暗号テキストを受信するステップと、
受信機において表現コードを受信するステップと、
上記表現コードに基づいて、受信機に保存されているマスタキーから導出できる複数のサブキーからターゲットサブキーを選択するステップと、
上記マスタキーから上記選択されたターゲットサブキーを導出するステップと、
上記導出したサブキーを用いて暗号テキストを復号するステップとを有する放送復号方法。
【請求項３４】
マスタキーを受信し、該マスタキーを受信機に保存するステップを有する請求項３３記載の放送復号方法。
【請求項３５】
上記受信機に保存されているマスタキーから導出できるサブキーによっては復号できない１つ以上の暗号テキストを削除するステップを有する請求項３３記載の放送復号方法。
【請求項３６】
上記マスタキーとともに用いて、上記サブキーを導出するために用いることができる１つ以上の暗号化パラメータを受信するステップを有する請求項３３記載の放送復号方法。
【請求項３７】
上記表現コードに含まれる値を用いて、１つ以上のノードを含み、各ノードが上記表現コードからの少なくとも１つの対応する値を有する表現木を定義するステップを有し、
上記ターゲットサブキーを選択するステップは、上記表現木のノードに対応する値によって示されるターゲットサブキーを選択するステップを含むことを特徴とする請求項３３記載の放送復号方法。
【請求項３８】
上記暗号テキストは、上記選択されたサブキーを用いて暗号化されたコンテンツキーであり、上記受信した暗号テキストを復号することにより、該コンテンツキーが復号されることを特徴とする請求項３３記載の放送復号方法。
【請求項３９】
上記コンテンツキーを用いて暗号化されたコンテンツファイルを受信するステップを有する請求項３８記載の放送復号方法。
【請求項４０】
上記復号されたコンテンツキーを用いて上記暗号化されたコンテンツファイルを復号するステップを有する請求項３９記載の放送復号方法。
【請求項４１】
上記復号されたコンテンツキーを用いて上記暗号化されたコンテンツファイルを復号するステップは、上記復号されたコンテンツキーからサブコンテンツキーを導出し、該導出したサブコンテンツキーを用いて上記暗号化されたコンテンツファイルを復号するステップを有することを特徴とする請求項４０記載の放送復号方法。
【請求項４２】
上記復号されたコンテンツファイルを上記受信機において再生するステップを有する請求項４０記載の放送復号方法。
【請求項４３】
上記暗号化されたコンテンツファイルは、記録媒体に記録されたデータとして受け取られることを特徴とする請求項３９記載の放送復号方法。
【請求項４４】
上記表現コードは、記録媒体に記録されたデータとして受け取られることを特徴とする請求項３９記載の放送復号方法。
【請求項４５】
上記復号されたコンテンツキーを用いて、コンテンツファイルを暗号化するステップを有する請求項３３記載の放送復号方法。
【請求項４６】
上記暗号テキスト及び表現コードは、記録媒体を介して受け取られ、該記録媒体に暗号化されたコンテンツファイルを記録するステップを有することを特徴とする請求項４５記載の放送復号方法。
【請求項４７】
上記受信機は、媒体再生装置であり、上記暗号テキストは、該媒体再生装置の製造業者によって該媒体再生装置に組み込まれることを特徴とする請求項３３記載の放送復号方法。
【請求項４８】
上記導出したサブキーを用いて暗号テキストを復号するステップは、該導出したサブキーにハッシュ関数を適用し、ハッシュキーを生成し、該ハッシュキーを用いて上記暗号テキストを復号するステップを有することを特徴とする請求項３３記載の放送復号方法。
【請求項４９】
上記受信機は、根と、複数の内部ノードと、複数の葉とを含む階層的キー木の葉に割り当てられ、
上記各サブキーは、上記階層的キー木の各ノードに対応するノードキーであり、
上記表現コードは、上記階層的キー木の各ノードの表現値であって、該ノードの子のノードキーが無効にされているか否かを示す表現値を含むことを特徴とする請求項３３記載の放送復号方法。
【請求項５０】
上記受信機は、階層的キー木の葉に割り当てられた、ｊ＝１，・・・，ＮとするＮ個の受信機ｕｊであり、該階層的キー木は、Ｎ個の葉を有する根の付いた完全２進木であって、ｉ＝２Ｎ−１として、根及び葉を含むｉ個のノードを有する完全２進木であり、
２つの素数ｑ１及びｑ２の積である値Ｍと、
複数の素数ｐｉと、
各素数ｐｉがどのノードに割り当てられているかを示す情報とを含む暗号化パラメータを受信するステップを有し、
ｉを選択されたノードキーに対応するノードとし、ｗｊを受信機ｕｊのノードから根までのパス上のノードに割り当てられている全ての素数ｐｉの積として、以下の式に基づいてノードキーＮＫｉを導出することを特徴とする請求項４９記載の放送復号方法。
【数３３】
2010081656.tif 000112
【請求項５１】
上記ｗｊを暗号化パラメータとして受信するステップを有する請求項５０記載の放送復号方法。
【請求項５２】
上記暗号化テキストを受信する前に、上記ｗｊを算出するステップを有する請求項５０記載の放送復号方法。
【請求項５３】
上記受信機は、根と、内部ノードと、複数の葉とを有し、該根も内部ノードである階層的キー木の葉に割り当てられ、
上記階層的キー木の各内部ノードは、１つ以上の対応するサブセットを有し、各サブセットは、対応するノードの１つ以上の子ノードを示し、
各サブキーは、各サブセットに対応し、及び該サブセットにより示される子ノードに対応するサブセットキーであり、
上記表現コードは、上記表現木の各ノードに対する表現値を含み、該表現値は、ノードの子のサブセットキーが無効にされているか否かを示すことを特徴とする請求項３３記載の放送復号方法。
【請求項５４】
複数の素数と、各素数がどのサブセットに割り当てられているかを示す情報とを含む暗号化パラメータを受信するステップを有し、
上記サブセットキーは、選択されたサブセットキーに対応するサブセットに割り当てられている素数と、上記階層的キー木における受信機のノードから根までのパス上のノードのサブセットに割り当てられている素数とを用いて導出されることを特徴とする請求項５３記載の放送復号方法。
【請求項５５】
上記複数の素数は、各サブセットに割り当てられていることを特徴とする請求項５４記載の放送復号方法。
【請求項５６】
それぞれが上記サブセットに対応し、値Ｌより大きく、値Ｌに近い順の複数の素数を生成するステップを有する請求項５３記載の放送復号方法。
【請求項５７】
それぞれが上記サブセットに対応し、０より大きく、０に近い順の複数の素数を生成するステップを有する請求項５３記載の放送復号方法。
【請求項５８】
それぞれが奇数に対応し、該奇数が素数であるか否かを示すビット値のテーブルを用いて素数を生成するステップを有する請求項５７記載の放送復号方法。
【請求項５９】
上記複数の受信機は、上記階層的キー木の葉に割り当てられた、ｊ＝１，・・・，ＮとするＮ個の受信機ｕｊであり、該階層的キー木は、ｋ＝１，・・・，（Ｎ−１）／（ａ−１）とし、ルートを内部ノードｖ１として、Ｎ個の葉と内部ノードｖｋを有する根の付いた完全ａ進木であり、
２つの素数ｑ１及びｑ２の積である値Ｍと、
以下の条件
【数３４】
2010081656.tif 000113
を満たす複数の素数
【数３５】
2010081656.tif 000114
と、
各素数
【数３６】
2010081656.tif 000115
がどのサブセットに割り当てられているかを示す情報とを含む暗号化パラメータを受信するステップとを有し、
ｋを選択されたサブキーに対応する内部ノードｖｋとし、ｂ１ｂ２．．．ｂｉ．．ｂａを選択されたサブキーに対応するサブセットとし、ｗｊを内部ノードｖｋに割り当てられ、受信機ｕｊのノードから根までのパス上の子ノードに割り当てられているサブセットキー
【数３７】
2010081656.tif 000116
に対応するサブセット
【数３８】
2010081656.tif 000117
に割り当てられている全ての素数
【数３９】
2010081656.tif 000118
の積として、サブセットキー
【数４０】
2010081656.tif 000119
は、以下の式に基づいて導出されることを特徴とする請求項５３記載の放送復号方法。
【数４１】
2010081656.tif 000120
【請求項６０】
上記ｗｊを暗号化パラメータとして受信するステップを有する請求項５９記載の放送復号方法。
【請求項６１】
上記暗号化テキストを受信する前に、上記ｗｊを算出するステップを有する請求項５９記載の放送復号方法。
【請求項６２】
上記受信機は、２つ以上のマスタキーを保存することを特徴とする請求項５３記載の放送復号方法。
【請求項６３】
上記複数の受信機は、上記階層的キー木の葉に割り当てられた、ｊ＝１，・・・，ＮとするＮ個の受信機ｕｊであり、上記階層的キー木は、ｋ＝１，・・・，（Ｎ−１）／（ａ−１）とし、ルートを内部ノードｖ１として、Ｎ個の葉と内部ノードｖｋを有する根の付いた完全ａ進木であり、
２つの素数ｑ１及びｑ２の積である値Ｍと、
以下の条件
【数４２】
2010081656.tif 000121
を満たす複数の素数
【数４３】
2010081656.tif 000122
と、各素数
【数４４】
2010081656.tif 000123
がどのサブセット
【数４５】
2010081656.tif 000124
に割り当てられているかを示す情報とを含む暗号化パラメータを受信するステップを有し、
ｋを選択されたサブキーに対応する内部ノードｖｋを指すものとし、ｂ１ｂ２．．．ｂｉ．．ｂａを選択されたサブキーに対応するサブセットを指すものとし、ｗｊ，ｋを内部ノードｖｋに割り当てられ、受信機ｕｊのノードから根までのパス上の子ノードに割り当てられているサブセットに割り当てられている選択された素数
【数４６】
2010081656.tif 000125
の積として、サブセットキー
【数４７】
2010081656.tif 000126
は、以下の式に基づいて導出されることを特徴とする請求項６２記載の放送復号方法。
【数４８】
2010081656.tif 000127
【請求項６４】
上記ｗｊ，ｋを暗号化パラメータとして受信するステップを有する請求項６３記載の放送復号方法。
【請求項６５】
上記暗号化テキストを受信する前に、上記ｗｊ，ｋを算出するステップを有する請求項６３記載の放送復号方法。
【請求項６６】
Ａ個の列とＢ個の行とを有するテーブルを定義するステップと、
上記テーブル内の各要素が対応するサブキーを有するように、該各要素についてそれぞれのサブキーを選択するステップと、
上記各サブキーを用いて媒体キーを暗号化するステップと、
上記暗号化された媒体キーを、上記テーブルにおいて、該媒体キーを暗号化するために使用されたサブキーに対応する要素に格納するステップと、
上記テーブルを複数の受信機のそれぞれに供給するステップと、
上記複数の受信機のそれぞれに、上記テーブルの各行の要素に対応するサブキーを含む２つ以上のサブキーを導出するために用いることができる各マスタキーを供給するステップとを有する暗号化方法。
【請求項６７】
上記テーブルは、記録媒体に記録され、該記録媒体が各受信機に供給されることを特徴とする請求項６６記載の暗号化方法。
【請求項６８】
上記記録媒体は、デジタルバーサタイルディスク（ＤＶＤ）であることを特徴とする請求項６６記載の暗号化方法。
【請求項６９】
上記各受信機にＢ個の要素を有するベクトルであって、各要素が上記テーブルの各行の要素を示すとともにサブキーを示すベクトルを供給するステップを有する請求項６６記載の暗号化方法。
【請求項７０】
受信機を無効にするステップと、
上記無効にされた受信機に提供されたマスタキーによって導出できる各サブキーを無効にするステップと、
上記無効にされたサブキーに対応する各要素を削除することによって上記テーブルを更新するステップと、
上記更新されたテーブルを上記各受信機に供給するステップとを有する請求項６６記載の暗号化方法。
【請求項７１】
媒体キーを用いてコンテンツファイルを暗号化するステップを有する請求項６６記載の暗号化方法。
【請求項７２】
上記各受信機に、上記暗号化したコンテンツファイルを送信するステップを有する請求項７１記載の暗号化方法。
【請求項７３】
上記各受信機に対し、上記マスタキーとともに用いてサブキーを導出することができる１つ以上の暗号化パラメータを送信するステップを有する請求項６６記載の暗号化方法。
【請求項７４】
上記少なくとも１つの暗号化パラメータは素数であることを特徴とする請求項７３記載の暗号化方法。
【請求項７５】
ｊ個の受信機ｕｊが存在し、テーブル内の各要素（ａ，ｂ）は、対応するキーＫａ，ｂを有し、上記ベクトルの各要素がサブキー
【数４９】
2010081656.tif 000128
をも指示するように、上記テーブルの各行内の要素を指示するＢ個の要素ｖｂ，ｖｂ∈｛１，・・・，Ａ｝を有するベクトルＶｊを各受信機ｕｊに供給するステップと、
２つの素数ｑ１及びｑ２を選択するステップと、
ｑ１及びｑ２を乗算してＭを算出するステップと、
複数の個別の素数ｐａ，ｂを選択するステップと、
上記選択された各素数ｐａ，ｂを上記テーブルの要素に割り当てるステップと、
Ｋ＝∈Ｚ＊Ｍとして、値Ｋをランダムに選択するステップと、
選択された全ての素数ｐａ，ｂの積としてＴを算出するステップと、
ベクトルＶｊのｂ番目の要素によって示されるテーブル内の要素に対応する素数を
【数５０】
2010081656.tif 000129
とし、ｗｊを
【数５１】
2010081656.tif 000130
として、マスタキーＭＫｊ以下の式に基づいて生成するステップとを有する請求項６６記載の暗号化方法。
【数５２】
2010081656.tif 000131
【請求項７６】
ストレージ装置と、
複数のサブキーを導出できるマスタキーを格納する安全ストレージ装置と、
暗号テキスト及び表現コードを受信する入出力インタフェースと、
コントローラとを備え、
上記コントローラは、
上記受信した表現コードに基づいて、マスタキーから導出できる複数のサブキーからターゲットサブキーを選択し、
上記マスタキーから上記選択したターゲットサブキーを導出し、
上記導出したサブキーを用いて上記受信した暗号テキストを復号する放送暗号化システム用の受信装置。
【請求項７７】
読出専用媒体からデータを読み出す媒体インタフェースを備える請求項７６記載の受信装置。
【請求項７８】
書込可能媒体からデータを読み出し、及び該書込可能媒体にデータを書き込む媒体インタフェースを備える請求項７６記載の受信装置。
【請求項７９】
複数の受信機のそれぞれに対し、２つ以上のサブキーを導出するために用いることができるマスタキーを割り当てる割当手段と、
１つ以上の受信機を無効にし、１つ以上の受信機を有効なまま残す取消手段と、
無効にされていない受信機のマスタキーについて、該マスタキー及び他の大部分のマスタキーから導出できるとともに、上記無効にされた全ての受信機のマスタキーからは導出できないサブキーを選択する選択手段と、
上記選択された各サブキーについて、該サブキーを用いてデータを暗号化して暗号テキストを生成する暗号化手段と、
上記暗号化された暗号テキストを複数の受信機に送信する送信手段とを備える放送暗号化装置。
【請求項８０】
受信機において暗号テキストを受信する暗号テキスト受信手段と、
受信機において表現コードを受信する表現コード受信手段と、
上記表現コードに基づいて、受信機に保存されているマスタキーから導出できる複数のサブキーからターゲットサブキーを選択する選択手段と、
上記マスタキーから上記選択されたターゲットサブキーを導出する導出手段と、
上記導出したサブキーを用いて暗号テキストを復号する復号手段とを備える放送復号装置。
【請求項８１】
データ媒体の個体を受け取るステップと、
上記データ媒体の個体に復号のために複数のサブキーのうち、どのサブキーを使用すべきかを指示する表現コードを格納するステップと、
上記表現コードによって指示された各サブキーについて、該サブキーを用いてコンテンツキーを暗号化し、該各指示されたサブキーに対する暗号化された各コンテンツキーを生成するステップと、
上記データ媒体の個体に上記暗号化された各コンテンツキーを格納するステップとを有するデータ媒体の製造方法。
【請求項８２】
上記データ媒体の個体を受け取るステップは、該データ媒体の個体を製造するステップを有することを特徴とする請求項８１記載のデータ媒体の製造方法。
【請求項８３】
上記データ媒体は、書込可能データ媒体であることを特徴とする請求項８１記載のデータ媒体の製造方法。
【請求項８４】
上記データ媒体は、読出専用データ媒体であることを特徴とする請求項８１記載のデータ媒体の製造方法。
【請求項８５】
コンテンツキーを用いてコンテンツファイルを暗号化するステップと、
上記暗号化されたコンテンツファイルを上記データ媒体の個体に格納するステップとを有する請求項８１記載のデータ媒体の製造方法。
【請求項８６】
ストレージ装置と、
入出力インタフェースと、
コントローラとを備え、
上記コントローラは、上記データ媒体の個体に復号のために複数のサブキーのうち、どのサブキーを使用すべきかを指示する表現コードを格納し、上記表現コードによって指示された各サブキーについて、該サブキーを用いてコンテンツキーを暗号化し、該各指示されたサブキーに対する暗号化された各コンテンツキーを生成し、上記データ媒体の個体に上記暗号化された各コンテンツキーを格納するデータ媒体の製造装置。
【請求項８７】
複数の受信機のそれぞれに対し、２つ以上のサブキーを導出するために用いることができるマスタキーを割り当てるステップと、
０つ以上の受信機を無効にし、１つ以上の受信機を有効なまま残すステップと、
無効にされていない受信機のマスタキーについて、該マスタキー及び他の大部分のマスタキーから導出できるとともに、上記無効にされた０つ以上の全ての受信機のマスタキーからは導出できないサブキーを選択するステップと、
上記選択された各サブキーについて、該サブキーを用いてデータを暗号化して暗号テキストを生成するステップと、
上記暗号化された暗号テキストを複数の受信機に送信するステップとを有する放送暗号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、放送暗号化方法、放送復号方法、受信装置、放送暗号化装置及び放送復号装置に関する。なお、本発明は、２００２年１月３０日に出願された米国特許仮出願番号第６０／３５３６４０号及び２００２年５月１５日に出願された米国特許仮出願番号第６０／３８１２９９号に基づく優先権を主張し、これらの出願における開示内容を参照することにより本願に援用する。
【背景技術】
【０００２】
デジタルデータ処理技術の進歩により、データの品質を損なうことなく、データを用いることができるようになっている。例えばデジタルピクチャ、デジタルミュージック等の多くの種類のコンテンツがデジタルデータとして利用できるようになり、またこれらのデジタルデータに対して、例えば生成、保存、コピー、編集、交換等の様々な処理を行うことができるようになっている。同時に、コンテンツの権利の所有者にとっては、不正なコピーやその他の使用からデータを保護することが益々困難になっている。
【０００３】
デジタルデータの配信を制御する一手法として、リボケーション方式（revocation Scheme）又は放送暗号化方式が用いられている。ここでは、送信機は、放送チャンネルを介して、受信機のグループに暗号化された情報又はコンテンツを送信する。１つ以上の受信機は、この情報を復号するための認証を得ていない。このような認証を受けていない受信機は、無効な受信機（revoked receiver）とも呼ばれる。無効な受信機は、暗号化されて放送された情報を復号するための復号キーを有していない。すなわち、全ての受信機は、情報を受信するが、この情報を復号することができる有効な受信機と、この情報を復号できない無効な受信機とが存在する。このリボケーション方式は、例えば有料テレビジョン放送及びコピー保護された媒体等に利用されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−３５２３２１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
そこで、本発明は上述の課題に鑑みてなされたものであり、本発明の目的は、効率的に受信機を無効にすることができる放送暗号化方法、放送復号方法、受信装置、放送暗号化装置及び放送復号装置を提供することである。
【課題を解決するための手段】
【０００６】
上述の課題を解決するために、本発明に係る放送暗号化方法は、管理センタによって、複数のサブキーのうちの２つ以上のサブキーを導出するために用いることができるそれぞれのマスタキーを複数の受信機のそれぞれに割り当てるステップと、管理センタによって、複数の受信機のうちの１つ以上の受信機を無効にし、無効にされていない１つ以上の受信機を残すステップと、管理センタによって、無効にされていない受信機の各マスタキー毎に、該マスタキーから導出できるとともに、無効にされた１つ以上受信機の全てのマスタキーからは導出できないサブキーを管理センタが選択するステップと、管理センタによって、選択された各サブキー毎に、該選択されたサブキーを用いて、１つの暗号文を暗号化するステップと、管理センタによって、暗号化された暗号文を複数の受信機に送信するステップとを有し、複数の受信機は、無効にされた受信機を示す受信機情報と、それぞれのサブキーとそれぞれの受信機間の関係を示す関係情報とを取得する。
【０００７】
また、上述の課題を解決するために、本発明に係る放送復号方法は、暗号文を受信機で受信するステップと、無効にされた受信機を示す受信機情報を受信機で取得するステップと、受信機情報、関係情報及びマスタキーに基づいて、サブキーを受信機で導出するステップと、導出されたサブキーを用いて、受信された暗号文を復号するステップとを有する。
【０００８】
また、上述の課題を解決するために、本発明に係る受信装置は、記憶装置と、複数のサブキーを導出できるマスタキーを格納する安全記憶装置と、暗号文、無効にされた受信装置を示す受信装置情報、及びそれぞれのサブキーとそれぞれの受信装置間の関係を示す関係情報を受信する入出力インタフェースと、コントローラとを備え、コントローラは、当該受信装置において、受信装置情報、関係情報及びマスタキーに基づき、サブキーを導出し、受信された暗号文を、導出されたサブキーを用いて復号する。
【０００９】
また、上述の課題を解決するために、本発明に係る放送暗号化装置は、複数のサブキーのうちの２つ以上のサブキーを導出するために用いることができるそれぞれのマスタキーを、複数の受信機のそれぞれに割り当てる割当手段と、複数の受信機のうちの１つ以上の受信機を無効にし、無効にされていない１つ以上の受信機を残す取消手段と、上記無効にされていない受信機の各マスタキー毎に、該マスタキーから導出できるとともに、上記無効にされた１つ以上の受信機の全てのマスタキーから導出できないサブキーを選択する選択手段と、上記選択された各サブキー毎に、該選択されたサブキーを用いて、１つの暗号文を暗号化する暗号化手段と、上記暗号化された暗号文を、上記複数の受信機に送信する送信手段とを備え、上記複数の受信機は、上記無効にされた受信機を示す受信機情報と、それぞれのサブキーとそれぞれの受信機間の関係を示す関係情報とを取得する。
【００１０】
また、上述の課題を解決するために、本発明に係る放送復号装置は、暗号文を受信する暗号文受信手段と、それぞれのサブキーとそれぞれの受信機間の関係を示す関係情報を取得する関係情報取得手段と、上記関係情報及びマスタキーに基づいて、サブキーを導出する導出手段と、上記関係情報及びマスタキーに基づいて、サブキーを導出する導出手段と、上記受信された暗号文を、上記導出されたサブキーを用いて復号する復号手段とを備える。
【発明の効果】
【００１１】
本発明は、複数の受信機のそれぞれに対し、２つ以上のサブキーを導出するために用いることができるマスタキーを割り当て、１つ以上の受信機を無効にし、無効にされていない受信機のマスタキー毎に、このマスタキーから導出できるとともに、無効にされた全ての受信機のマスタキーからは導出できないサブキーを選択し、選択された各サブキー毎に、サブキーを用いてデータを暗号化して暗号文を生成し、暗号化された暗号文を複数の受信機に送信することで、放送暗号化システムにおいて、効率的に受信機を無効にする。
【図面の簡単な説明】
【００１２】
【図１】衛星放送を用いた放送暗号化システムのアーキテクチャを示す図である。
【図２】管理センタの構成を示すブロック図である。
【図３】受信機の構成を示すブロック図である。
【図４】データ媒体を用いた放送暗号化システムのアーキテクチャを示す図である。
【図５】管理センタの具体例を示すブロック図である。
【図６】受信装置の具体例を示すブロック図である。
【図７】データを暗号化して暗号文を生成し、１つ以上の受信機に暗号文を送信する放送暗号化処理の手順を示すフローチャートである。
【図８】コンテンツキー及びコンテンツファイルを暗号化する処理を含む放送暗号化処理の手順を示すフローチャート。
【図９】受信機によって放送復号処理を行う手順を示すフローチャートである。
【図１０】ノードキーを有するＨＫＴを用いて、放送暗号化システムを設定し、受信機にマスタキーを割り当てる手順を示すフローチャートである。
【図１１】ノードに対するノードキーの割当を説明するＨＫＴを示す図である。
【図１２】ＨＫＴを用いて、受信機を無効にし、ノードキーを選択し、表現コードを生成する手順を示すフローチャートである。
【図１３】図１１のＨＫＴにおける無効にされた受信機と、選択されたノードキーとを示す図である。
【図１４】図１１及び図１３に示すＨＫＴに基づく表現木を示す図である。
【図１５】ＨＫＴ及びノードキーを用いて、受信機により放送復号処理を行う手順を示すフローチャートである。
【図１６】コンテンツキー及びコンテンツファイルの復号を含む放送復号処理の手順を示すフローチャートである。
【図１７】サブセット及びサブセットキーを有するＨＫＴを用いて、放送暗号化システムを設定し、受信機にマスタキーを割り当てる手順を示すフローチャートである。
【図１８】ノードに対するサブセットの割当を示すＨＫＴを示す図である。
【図１９】図１８のＨＫＴにおけるノードキーに対するサブセットキーの割当を示す図である。
【図２０】ＨＫＴを用いて受信機を無効にし、サブセットキーを選択し、表現コードを生成する手順を示すフローチャートである。
【図２１】図１８に示すＨＫＴにおいて、無効にされた受信機と、選択されたサブセットキーに対応するサブセットのノードとを示す図である。
【図２２】図１８に示すＨＫＴの枝を除去した状態を示す図である。
【図２３】図１８及び図２１に示すＨＫＴに基づく表現木を示す図である。
【図２４】ＨＫＴ及びサブセットキーを用いて、受信機によって放送復号処理を行う手順を示すフローチャートである。
【図２５】コンテンツキー及びコンテンツファイルの復号を含む放送復号処理の手順を示すフローチャートである。
【図２６】サブセット及びサブセットキーを有するＨＫＴを用いて、放送暗号化システムを設定し、マスタキーを受信機に割り当てる手順を示すフローチャートである。
【図２７】ＨＫＴにおけるノードに対するサブセットキーの割当を示す図である。
【図２８】ＭＫＢを用いて、放送暗号化システムを設定し、マスタキーを受信機に割り当てる手順を示すフローチャートである。
【図２９】ブロックキーテーブルを示す図である。
【図３０】媒体キーブロックを示す図である。
【図３１】受信機を無効にし、ＭＫＢを更新する手順を示すフローチャートである。
【図３２】ＭＫＢを用いて、受信機によって放送復号処理を行う手順を示すフローチャートである。
【図３３】データ媒体製造装置の一具体例を示すブロック図である。
【図３４】媒体製造装置によって、再生専用データ媒体を製造する手順を示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、本発明に係る放送暗号化方法、放送復号方法、受信装置、放送暗号化装置及び放送復号装置について、図面を参照して詳細に説明する。
【００１４】
本発明は、例えば放送の暗号化又は媒体の保護の分野において、一部の受信機を効率的に無効にする方法及び装置を提供する。一具体例においては、マスタキーとサブキーとを組み合わせて用いることにより、認証された受信機に対し、暗号化されて放送されたコンテンツへのアクセスを許可するとともに、無効な受信機（すなわち、認証されていない受信機）が暗号化されたコンテンツにアクセスすることを防止する。すなわち、暗号化されたコンテンツは、全ての受信機に対して送信されるが、無効な受信機は、このコンテンツのファイルを復号するためのコンテンツキーにアクセスすることができない。
【００１５】
図１は、放送衛星を用いた放送暗号化システム（broadcast encryption system）の構成を示すブロック図である。図１に示す放送暗号化システム１００は、放送チャンネルを介して暗号化されたデータ（暗号文（ciphertext）とも呼ばれる。）を受信機１２０１〜１２０Ｎに送信する。図１に示す放送暗号化システム１００では、放送チャンネルは、衛星放送配信チャンネルである。暗号文として送信されるデータは、例えば暗号キー、オーディオ及び／又はビデオコンテンツ、テキストメッセージ等を含んでいる。衛星放送局１１０における放送管理センタ（broadcast trusted center）１０５は、放送衛星１１５にデータを送信する。放送管理センタ１０５は、例えば暗号化用のキーを選択すること等により、データの暗号化及び配信を制御する。放送衛星１１５は、データを放送する。住居１２５１に設置された受信機１２０１は、例えば衛星放送受信機を備え、放送されてくるデータを受信する。他の複数の受信機１２０２〜１２０Ｎも放送されてくるデータを受信することができる。このようにして、放送管理センタ１０５は、受信機１２０１〜１２０Ｎからなる受信機グループ内の各受信機にデータを送信することができる。後述するように、放送管理センタ１０５は、認証されている受信機１２０１〜１２０Ｎのみが放送されたデータを復号することができるように、放送データを暗号化する。なお、図１には、放送衛星１１５を用いた放送システムを示しているが、ケーブルテレビジョンやコンピュータネットワーク等、この他の放送チャンネルを用いてもよい。
【００１６】
図２は、例えば図１に示す放送管理センタ１０５等の管理センタの具体的な構成を示すブロック図である。図２に示す管理センタ２００は、コントローラ２０５と、演算ユニット２１０と、入出力インタフェース２１５と、安全記憶装置（secure storage）２２０と、主記憶装置２２５とを備える。コントローラ２０５は、管理センタ２００の動作を制御する。一具体例においては、コントローラ２０５は、中央演算処理装置（central processing unit：以下、ＣＰＵという。）であってもよい。演算ユニット２１０は、暗号キーの生成及び暗号化等のための専用の演算機能を提供する。また、管理センタ２００は、入出力インタフェース２１５を介してデータを送受する。一具体例においては、入出力インタフェース２１５は、送信機を含む。また、他の具体例においては、入出力インタフェース２１５は、例えば図１に示す衛星放送局１１０が備える送信機等の送信機に接続されていてもよい。安全記憶装置２２０は、例えば暗号キー等、安全又は秘密に保持すべきデータを保存する。主記憶装置２２５は、管理センタ２００の動作をサポートするためのデータ、及び例えばビデオ及び／又はオーディオデータを含むコンテンツファイル等、受信機１２０に送信するデータを保存している。一具体例においては、安全記憶装置２２０及び主記憶装置２２５は、例えばランダムアクセスメモリ（random access memory：以下、ＲＡＭという。）等のメモリ装置であってもよい。
【００１７】
図３は、例えば図１に示す受信機１２０１〜１２０Ｎ等の受信機の具体的な構成を示すブロック図である。図３に示す受信機３００は、コントローラ３０５と、演算ユニット３１０と、入出力インタフェース３１５と、安全記憶装置３２０と、主記憶装置３２５と、ディスプレイ装置３３０とを備える。コントローラ３０５は、受信機３００の動作を制御する。一具体例においては、コントローラ３０５は、ＣＰＵであってもよい。演算ユニット３１０は、例えば復号等の専用の演算機能を提供する。受信機３００は、入出力インタフェース３１５を介して、データを送受する。一具体例においては、入出力インタフェース３１５は、放送受信機を含む。また、他の具体例においては、入出力インタフェース３１５は、図１に示す住居１２５１〜１２５Ｎに設置されている対応した衛星放送受信機等の放送受信機に接続されている。安全記憶装置３２０は、例えば復号キー等、安全又は秘密に保持すべきデータを保存する。受信機３００用の１又は複数の復号キーは、製造業者によって、安全記憶装置３２０に保存される。これに代えて、放送管理センタ１０５が受信機３００に復号キーを送信し、受信機３００がその安全記憶装置３２０にこの復号キーを保存するようにしてもよい。主記憶装置３２５は、受信機３００の動作をサポートするためのデータを保存する。一具体例においては、安全記憶装置３２０及び主記憶装置３２５は、ＲＡＭ等のメモリ装置であってもよい。ディスプレイ装置３３０は、例えばモニタ又はテレビジョン受像機を介して、受信機３００のユーザに、データに基づく情報を表示する。変形例においては、受信機３００は、ディスプレイ装置自体を備えるのではなく、外部のディスプレイ装置に接続されるディスプレイインタフェースを備えていてもよい。
【００１８】
図４は、データ媒体を用いた放送暗号化システムの構成を示すブロック図である。図４に示す放送暗号化システム４００では、放送チャンネルは、データ媒体の配布である。媒体製造業者４１０内の媒体管理センタ４０５は、例えば再生専用媒体（ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等）又は記録可能な媒体（ＣＤ−ＲＷやＤＶＤ−ＲＷ等）等のデータ媒体４１５の各個体（article of data media）にデータを記録する。後述するように、再生専用媒体については、媒体管理センタ４０５は、暗号化されたコンテンツキー及び暗号化されたコンテンツを記録し、認証された再生装置のみが、暗号化されているコンテンツ（例えば、ビデオ及び／又はオーディオ）を復号して、アクセスできるようにしている。一方、記録可能な媒体については、媒体管理センタ４０５は、暗号化されたコンテンツキーを、記録可能な媒体に記録し、認証された記録装置のみが対応するデータを、記録可能な媒体に記録できるようにしている。媒体製造業者４１０は、例えば小売店等の販売店（distrbution outlet）４２０にデータ媒体４１５を送付する。販売店４２０は、データ媒体４１５を住居４３０の受信機４２５に提供する。例えば、販売店４２０は、データ媒体４１５を個人に販売し、この個人がデータ媒体４１５を住居４３０に持ち帰り、データ媒体４１５を受信機４２５に挿入する。一具体例においては、受信機４２５は、例えばＤＶＤプレイヤ等、データ媒体４１５に記録されているデータを読み出して再生する装置であってもよい。他の具体例においては、受信機４２５は、例えばＤＶＤ−ＲＷドライブ等、データ媒体４１５にデータを記録し、及びデータ媒体４１５からデータを読み出す記録装置であってもよい。このようにして、媒体管理センタ４０５は、受信機４２５にデータを供給することができる。後述するように、媒体管理センタ４０５は、認証されている受信機４２５のみが、暗号化されているデータを復号することができるように、データを暗号化する。
【００１９】
図５は、図４に示す媒体管理センタ４０５等の管理センタの具体的な構成を示すブロック図である。図５に示す媒体管理センタ５００は、コントローラ５０５と、演算ユニット５１０と、入出力インタフェース５１５と、安全記憶装置５２０と、主記憶装置５２５と、媒体インタフェース５３０とを備える。コントローラ５０５は、媒体管理センタ５００の動作を制御する。一具体例においては、コントローラ５０５は、ＣＰＵであってもよい。演算ユニット５１０は、例えば暗号キーの生成及び暗号化等のための専用の演算機能を提供する。また、媒体管理センタ５００は、入出力インタフェース５１５を介してデータを送受する。安全記憶装置５２０は、例えば暗号キー等、安全又は秘密に保持すべきデータを保存する。主記憶装置５２５は、媒体管理センタ５００の動作をサポートするためのデータ、及び例えばビデオ及び／又はオーディオデータを含むコンテンツファイル等、受信機４２２に配布すべきデータを保存している。一具体例においては、安全記憶装置５２０及び主記憶装置５２５は、例えばＲＡＭ等のメモリ装置であってもよい。媒体インタフェース５３０は、媒体管理センタ５００に読出／書込機能を提供し、これにより、媒体管理センタ５００は、例えば図４に示す放送暗号化システム４００によって配布されるデータ媒体４１５等の媒体の個体にデータを書き込み、及びこの媒体の個体からデータを読み出すことができる。
【００２０】
図６は、例えば図４に示す受信機４２５等の受信機の具体的な構成を示すブロック図である。図６に示す受信機６００は、再生装置であってもよく、記録装置であってもよい。受信機６００は、コントローラ６０５と、演算ユニット６１０と、入出力インタフェース６１５と、安全記憶装置６２０と、主記憶装置６２５と、ディスプレイ装置６３０と、媒体インタフェース６３５とを備える。コントローラ６０５は、受信機６００の動作を制御する。一具体例においては、コントローラ６０５は、ＣＰＵであってもよい。演算ユニット６１０は、例えば復号又は暗号化（記録装置の場合）等の専用の演算機能を提供する。受信機６００は、入出力インタフェース６１５を介して、データを送受する。安全記憶装置６２０は、例えば復号キー等、安全又は秘密に保持すべきデータを保存する。受信機６００用の１又は複数の復号キーは、製造業者によって、安全記憶装置６２０に保存される。主記憶装置６２５は、受信機６００の動作をサポートするためのデータを保存する。一具体例においては、安全記憶装置６２０及び主記憶装置６２５は、ＲＡＭ等のメモリ装置であってもよい。ディスプレイ装置６３０は、例えばモニタ又はテレビジョン受像機を介して、受信機６００のユーザに、データに基づく情報を表示する。変形例においては、受信機６００は、ディスプレイ装置自体を備えるのではなく、外部のディスプレイ装置に接続されるディスプレイインタフェースを備えていてもよい。媒体インタフェース６３５は、受信機６００に読出機能を提供し、及び受信機６００が記録装置である場合、受信機６００に書込機能を提供し、これにより、受信機６００は、例えば図４に示す放送暗号化システム４００によって配布されるデータ媒体４１５等の媒体の個体からデータを読み出し、また受信機６００が記録装置の場合、この媒体の個体にデータを書き込むことができる。
【００２１】
図７は、データを暗号化して暗号文を生成し、及び暗号文を１つ以上の受信機のグループに送信する処理を含む放送暗号化処理の手順を示すフローチャートである。一具体例においては、例えば図１に示す放送暗号化システム１００のように、放送管理センタ１０５は、１つ以上の受信機１２０に暗号文を放送する。他の具体例においては、例えば図４に示す放送暗号化システム４００のように、媒体管理センタ４０５は、１つ以上の受信機４２５に配布するためのデータ媒体を準備する。管理センタは、ステップＳ７０５において、放送暗号化システムを設定する。管理センタは、設定の一部として、サブキー及びマスタキーを生成する。各マスタキーは、２つ以上のサブキーを生成するために用いることができる。管理センタ及び受信機は、サブキーを用いて暗号文を暗号化及び復号する。一具体例においては、管理センタは、各マスタキーを対応する受信機に送信する。他の具体例においては、各受信機は、受信機の製造業者から対応するマスタキーが供給される。管理センタは、ステップＳ７１０において、２つ以上の受信機からなるグループの各受信機に、それぞれマスタキーを割り当てる。これに応じて、各受信機はマスタキーを保存する。なお、受信機は、サブキーのそれぞれを保存する必要はない。後述するように、受信機は、サブキー又はサブキーの一部を予め算出していてもよい。これにより、予め算出されたサブキー又はサブキーの一部を記憶するための記憶容量が必要となるが、処理速度を速めることができる。
【００２２】
管理センタは、ステップＳ７１５において、１つ以上の受信機を無効にする。管理センタが受信機を無効にすると、受信機の認証が取り消される。この無効処理の後は、元の受信機のグループのうちの１つ以上の受信機が有効のまま残る。また、全ての受信機がデータを復号するための認証を管理センタから受けている場合等、管理センタが受信機を１つも無効にしない場合もある。管理センタは、ステップＳ７２０において、暗号化に使用するためのサブキーを選択する。後述するように、管理センタは、無効にされた受信機に割り当てられているマスタキーからは生成することができないサブキーを選択する。管理センタは、各マスタキーについて、そのマスタキー及び他の多くのマスタキーから生成でき、且つ無効にされた受信機のマスタキーからは生成できないサブキーを選択する。後述するように、一具体例においては、管理センタは、階層的キー木（hierarchical key tree）を用いて、サブキーの割当及び選択を行う。選択されたサブキーのグループは、利用可能なサブキーの全てを含んではいない。管理センタは、ステップＳ７２５において、どのサブキーが選択されたかを示す表現コード（representation code）を生成する。管理センタは、この表現コードを受信機に送信する。
【００２３】
管理センタは、ステップＳ７３０において、選択された各サブキーを用いて、データを暗号化して暗号文を生成する。管理センタは、ＡＥＳやＤＥＳ等の暗号アルゴリズムを使用する。管理センタは、ステップＳ７３５において、暗号文を全ての受信機に送信する。ここでは、無効にされた受信機は、暗号文を復号することができないので、管理センタは、無効にされた受信機を含む全ての受信機に暗号文を送信することができる。管理センタは、各放送暗号化システムにおいて適切なチャンネルを介して、受信機に暗号文を送信する。例えば図１に示す放送暗号化システム１００では、放送チャンネルは、上述のように放送衛星１１５である。一具体例においては、管理センタは、ステップＳ７０５及びステップＳ７１０を１回（又は、受信機の数が変わる等、放送暗号化システムに変化が生じるまで）実行し、この後は、暗号文の配信毎に、ステップＳ７１５〜ステップＳ７３５を繰り返す。
【００２４】
一具体例においては、管理センタは、選択された各サブキーを用いて、コンテンツキーを暗号化する。受信機は、コンテンツキーを用いて、例えばビデオ及び／又はオーディオデータを含むファイル等である暗号化されたコンテンツファイルを復号することができる。ここで、コンテンツキーには、暗号化されたコンテンツファイルを直接復号するために用いることができるものと、暗号化されたコンテンツファイルを復号するための１つ以上のサブコンテンツキーを生成するために使用されるものとがある。また、コンテンツは、データストリーム又はライブコンテンツのように静的ファイルとして保存されないものもある。図８は、コンテンツキー及びコンテンツファイルの暗号化を含む放送暗号化処理の手順を示すフローチャートである。図８に示す具体例において、図７を用いて説明したステップと同様のステップは、図７に示す具体例と同様に実行されるので、変更があったステップについて、以下に説明する。まず、ステップＳ８０５において、管理センタは、放送暗号化システムを設定する。管理センタは、ステップＳ８１０において、２つ以上の受信機からなるグループの各受信機に、それぞれマスタキーを割り当てる。管理センタは、ステップＳ８１５において、１つ以上の受信機を無効にする。管理センタは、ステップＳ８２０において、暗号化に使用するためのサブキーを選択する。管理センタは、ステップＳ８２５において、どのサブキーが選択されたかを示す表現コードを生成し、この表現コードを全ての受信機に送信する。管理センタは、ステップＳ８３０において、選択された各サブキーを用いて、コンテンツキーをそれぞれのキー暗号文として暗号化する。管理センタは、選択された各サブキーを用いて、同じコンテンツキーを暗号化し、選択された各サブキーに対するキー暗号文を生成する。管理センタは、ステップＳ８３５において、受信機にキー暗号文を送信する。管理センタは、ステップＳ８４０において、コンテンツキーを用いて、コンテンツファイルを暗号化する。ここでは、無効にされた受信機は、暗号化されたコンテンツファイル又はキー暗号文を復号できないので、管理センタは、無効にされた受信機を含む全ての受信機に、暗号化されたコンテンツファイル及びキー暗号文（それぞれがコンテンツキーを含んでいる）を送信することができる。更に、管理センタは、選択された各サブキーを用いて、コンテンツキーを独立したキー暗号文として複数回暗号化及び放送し、及びコンテンツキーを用いて、コンテンツファイルを１回暗号化及び放送する。一具体例においては、管理センタは、ステップＳ８０５及びステップＳ８１０を１回（又は、受信機の数が変わる等、放送暗号化システムに変化が生じるまで）実行し、この後は、暗号文の配信毎に、ステップＳ８１５〜ステップＳ８４５を繰り返す。
【００２５】
受信機によって実行される放送データ復号処理を説明するフローチャートを図９に示す。一具体例においては、例えば図１に示す放送暗号化システム１００のように、受信機１２０１〜１２０Ｎは、放送管理センタ１０５から放送されてくるデータ及び暗号文を受信する。他の具体例においては、例えば図４に示す放送暗号化システム４００のように、受信機４２５は、媒体管理センタ４０５が配布のために準備したデータ媒体を介して、データ及び暗号文が供給される。受信機は、ステップＳ９０５において、管理センタからマスタキーが供給される。受信機は、マスタキーを安全記憶装置に保存する。上述した図７のステップＳ７１０と同様に、一具体例においては、受信機は、管理センタから直接ではなく、受信機の製造業者からマスタキーが供給される。受信機は、ステップＳ９１０において、管理センタから表現コードを受信する。表現コードは、管理センタがどのサブキーを用いて暗号文を暗号化しているかを示している。受信機は、ステップＳ９１５において、管理センタから放送暗号化システムの放送チャンネルを介して、１つ以上の暗号文を受信する。一具体例においては、受信機は、表現コードを確認し、どの暗号文を復号することができるかを判定し、受信機が復号できない暗号文を削除又は無視する。受信機は、ステップＳ９２０において、表現コードを用いて、復号に用いるターゲットサブキー（targetsub key）を選択する。ターゲットサブキーは、受信機のマスタキーに基づいて生成されるサブキーである。サブキーを選択した後、受信機は、ステップＳ９２５において、受信機のマスタキーに基づいて、選択されたサブキーを生成する。受信機は、ステップＳ９３０において、上述のようにして生成したサブキーを用いて、受信した暗号文を復号する。この復号の後、受信機は、暗号文に含まれているデータにアクセスすることができるようになる。一具体例においては、受信機は、ステップＳ９０５を１回（又は、受信機の数が変わる等、放送暗号化システムに変化が生じるまで）実行し、この後は、暗号文の配信毎に、ステップＳ９１０〜ステップＳ９３０を繰り返す。
【００２６】
管理センタは、様々な手法を用いて、放送暗号化システムを設定する（図７に示すステップＳ７０５参照）。放送暗号化システムの設定は、管理センタと受信機との間のインタラクションに影響を与える。管理センタは、受信機を葉（leaf）とする階層的キー木を生成する。一具体例においては、管理センタは、木のノードにノードキーを割り当てた階層的キー木を用いる。他の具体例においては、管理センタは、ノード及びサブセットキーの子を指示するサブセットを階層的キー木のノードに割り当てる。更に他の具体例においては、管理センタは、サブセットキーを用いて、複数のマスタキーを各受信機に割り当てる。更に他の具体例においては、管理センタは、キー木に代えて、キーテーブルと、キーテーブルから要素を選択するためのベクトルとを使用する。以下、これらの具体例及び変形例について説明する。
【００２７】
ノードキーを有する階層的キー木
例えば図１に示す放送暗号化システム１００又は図４に示す放送暗号化システム４００等、管理センタと、Ｎ個の受信機とを備える放送暗号化システムの一具体例においては、管理センタは、階層的キー木（hierarchical key tree：以下、ＨＫＴとも呼ぶ。）及びノードキーを用いる。この具体例においては、ノードキーは、上述したサブキーである。以下、図７及び図９に示す処理をこの構造に適用した具体例について説明する。
【００２８】
図１０は、ノードキーを有するＨＫＴを用いて、マスタキーを受信機に割り当てる放送暗号化システムの設定の手順を示すフローチャートである（図７のステップＳ７０５及びＳ７１０参照）。図１１は、１６個の受信機からなる受信機のグループを含むＨＫＴ１１００におけるノード１１１０に対するノードキー１１０５の割当を示す図である。管理センタは、ステップＳ１００５において、ＨＫＴを定義する。このＨＫＴは、葉、根及び内部ノードとを含む、２Ｎ−１個のノード及びＮ個の葉を有する根の付いた完全２分木（full binary tree）である。図１１に示すように、ノードは、Ｖｉ（ｉ＝１，・・・，２Ｎ−１）として表される。ここで、Ｎが２の累乗ではない場合、管理センタは、Ｎより大きく且つＮに最も近い２の累乗個の葉を有するＨＫＴを定義する。変形例においては、管理センタは、２分木ではなく、ａ分木を定義する。
【００２９】
管理センタは、ステップＳ１０１０において、各受信機をそれぞれの葉に割り当てる。受信機は、図１１に示すように、ｕｊ（ｊ＝１，・・・，Ｎ）として表される。ここで、Ｎが２の累乗ではない場合、余りの葉には「仮想の」受信機が割り当てられる。なお、仮想の受信機は、仮想のエンティティであり、後に無効にする必要はない。管理センタは、ステップＳ１０１５において、暗号化パラメータを選択する。管理センタは、暗号化パラメータを用いて、例えばキー等の暗号化のための値を生成する。暗号化パラメータの一部は、公開暗号化パラメータであり、管理センタは、ステップＳ１０２０において、公開暗号化パラメータを公開する。ここで、管理センタは、例えば公開暗号化パラメータを各受信機に送信することにより、公開暗号化パラメータを公開する。なお、管理センタは、残りの秘密暗号化パラメータを受信機に対して秘密にする。管理センタは、２つの大きな素数ｑ１、ｑ２を選択し、Ｍ＝ｑ１×ｑ２である値Ｍを算出する。管理センタは、この値Ｍを公開暗号化パラメータとして公開する。更に、管理センタは、Ｋ０∈Ｚ＊Ｍとして、値Ｋ０を秘密暗号化パラメータとして選択する。更に、管理センタは、２Ｎ−１個の素数ｐｉ（ｉ＝１，・・・，２Ｎ−１）を公開暗号化パラメータとして選択する。管理センタは、根及び葉を含む対応したノードＶｉに、各素数ｐｉを割り当てる（例えば、素数ｐ１はノードｖ１に割り当てられる）。管理センタは、ノードに対する素数の割当を公開する。管理センタは、以下の式に基づいて、値Ｔを生成する。
【００３０】
【数１】
2010081656.tif 000003
【００３１】
なお、管理センタは、値Ｔを公開しない。また、管理センタは、各受信機ｕｊに対して値ｗｊを生成する。値ｗｊは、受信機ｕｊに対応する葉から根までのパスに含まれる各ノードＶｉに割り当てられた全ての素数ｐｉの積である。例えば、図１１に示すＨＫＴ１１００において、値ｗ１は、受信機ｕ１に対応し、ノードｖ１６、ｖ８、ｖ４、ｖ２、ｖ１に割り当てられた素数ｐ１６、ｐ８、ｐ４、ｐ２、ｐ１の積であり、したがって、ｗ１＝ｐ１６×ｐ８×ｐ４×ｐ２×ｐ１である。
【００３２】
管理センタは、ステップＳ１０２５において、暗号化パラメータを用いて、ノードキーを生成する。ノードキーは、図１１に示すように、ＮＫｉとして表される。管理センタは、以下の式に基づいて、各ノードＶｉに対応するノードキーＮＫｉを算出する。
【００３３】
【数２】
2010081656.tif 000004
【００３４】
管理センタは、各ノードキーＮＫｉを対応するノードＶｉに割り当てる。
【００３５】
管理センタは、ステップＳ１０３０において、暗号化パラメータを用いて、マスタキーを生成する。マスタキーは、図１１に示すように、ＭＫｊとして表される。ここで、管理センタは、以下の式に基づいて、各受信機ｕｊに対応するマスタキーＭＫｊを算出する。
【００３６】
【数３】
2010081656.tif 000005
【００３７】
管理センタは、各マスタキーＭＫｊを対応する受信機ｕｊに割り当てる。これらのマスタキーＭＫｊを用いて、受信機ｕｊに対応する葉から根までのパスに含まれるノードＶｉに対応する全てのノードキーＮＫｉを導出することができる。例えば、図１１に示すＨＫＴ１１００において、受信機ｕ１には、マスタキーＭＫ１が割り当てられており、このマスタキーＭＫ１を用いて、ノードキーＮＫ１６、ＮＫ８、ＮＫ４、ＮＫ２、ＮＫ１を導出することができる。受信機ｕｊのいずれも無効にされていない場合は、根のノードキーＮＫｉは、全てのマスタキーＭＫｊから導出することができる。管理センタは、ステップＳ１０３５において、各マスタキーＭＫｊを対応する受信機ｕｊに送信する。
【００３８】
管理センタは、ステップＳ１０４０において、ＨＫＴに関する情報を各受信機に送信する。ここで、管理センタは、ＨＫＴのノード数及び受信機に関連する割当を示す情報を受信機に送信する。上述のように、管理センタは、公開暗号化パラメータ、例えば、素数ｐｉ及びどのノードＶｉに素数ｐｉが対応しているかに関する情報を公開する。更に、管理センタは、どのノードＶｉに受信機ｕｊが割り当てられているか、どのノードＶｉにどの受信機のマスタキーＭＫｊが割り当てられているか、及びどのノードＶｉに受信機のマスタキーＭＫｊから導出可能なノードキーＮＫｉが割り当てられているかを示す情報を送信する。
【００３９】
図７のステップＳ７１０について上述したように、他の具体例においては、管理センタは、受信機の製造業者にマスタキーを供給し、受信機の製造業者が受信機にマスタキーを組み込む。この場合、管理センタは、製造業者を介して、公開暗号化パラメータ及びＨＫＴ情報を受信機に供給する。
【００４０】
図１２は、ＨＫＴを用いて、受信機を無効にし、ノードキーを選択し、表現コードを生成する処理を示すフローチャートである（図７のステップＳ７１５、Ｓ７２０、Ｓ７２５参照）。図１３は、図１１のＨＫＴ１１００において、無効にされた受信機１３０５及び選択されたノードキー１３１０を示す図である。管理センタは、ステップＳ１２０５において、１つ以上の受信機を無効にする。管理センタは、受信機が管理センタから送信されてくる暗号文を復号する権限を有さなくなった場合に、その受信機を無効又は有効ではなくする。例えば、管理センタは、必要な料金を支払っていない受信機又はライセンスが有効ではなくなった受信機を無効にする。図１３では、無効にされた受信機１３０５には、ＨＫＴ１１００の対応するノードに「×」印を付している。管理センタは、受信機ｕ１、ｕ５、ｕ９、ｕ１３を無効にしている。他の受信機ｕ２、ｕ３、ｕ４、ｕ６、ｕ７、ｕ８、ｕ１０、ｕ１１、ｕ１２、ｕ１４、ｕ１５、ｕ１６は、無効にされていない、すなわち有効な受信機である。
【００４１】
管理センタは、ステップＳ１２１０において、無効にされた受信機に割り当てられているマスタキーに基づいて生成することができるノードキーを無効にする。例えば、図１３に示す具体例では、管理センタは、受信機ｕ１を無効にし、この受信機ｕ１には、マスタキーＭＫ１が割り当てられている。受信機ｕ１は、マスタキーＭＫ１に基づいて、ノードキーＮＫ１６、ＮＫ８、ＮＫ４、ＮＫ２、ＮＫ１を生成することができる。したがって、管理センタは、ノードキーＮＫ１６、ＮＫ８、ＮＫ４、ＮＫ２、ＮＫ１を無効にする。
【００４２】
無効にされていない受信機の各マスタキーについては、管理センタは、ステップＳ１２１５において、これらのマスタキーに基づいて生成でき、及び他の大部分のマスタキーに基づいて生成でき、且つ無効にされた受信機に対応するマスタキーからは生成できないノードキーを選択する。ＨＫＴ１１００において、管理センタは、無効にされたノードキーに対応する親ノードを有する無効にされていないノードキーを選択する。他の手法では、管理センタは、無効にされたノードキーに対応するノードを取り除く。ノードを取り除くことにより、１つ以上の部分木が残る（１つ以上の部分木は、単一のノードのみから構成される場合もある）。管理センタは、これらの部分木の根となるノードに対応したノードキーを選択する。図１３では、ノードを囲む正方形の枠によって選択されたノードキー１３１０を示している。すなわち、管理センタは、ノードキーＮＫ１７、ＮＫ９、ＮＫ２１、ＮＫ１１、ＮＫ２５、ＮＫ１３、ＮＫ２９、ＮＫ１５を選択する。
【００４３】
管理センタは、ステップＳ１２２０において、ＨＫＴ及び無効にされた受信機に基づいて、表現木（representation tree）を定義する。図１４は、図１１及び図１３に示すＨＫＴ１１００に基づく表現木１４００を示している。図１４の濃い又は太い枝（edge）は、表現木１４００の一部である枝を示している。図１４の薄い又は細い枝は、表現木１４００に含まれない。無効にされた受信機１４０５及び選択されたノードキー１４１０が、図１３と同様に示されている。表現木１４００の根は、対応するＨＫＴ１１００の根である。表現木１４００の葉は、選択されたノードキーに対応するノードである。表現木１４００の内部ノードは、葉と根の間の内部ノードである。
【００４４】
管理センタは、ステップＳ１２２５において、表現木１４００に基づいて、表現コードを生成する。管理センタは、ＨＫＴの対応するノードに子が存在する場合、ＨＫＴの対応するノードのどの子が表現木に含まれているかを示す値を、表現木の各ノードに割り当てる。この具体例では、２分木を用いているので、表現木の各ノードは、２つの子を有する可能性がある。したがって、２つの１ビット値を用いて、ノードが有する可能性がある各子について、表現木に子ノードが含まれているか否かを示すことができる。図１４では、表現木１４００の各ノードの隣に示す括弧で括られた２つの数によって、この値を示している。例えば、根の隣には、（１，１）が示されており、これは、根の左側の子と右側の子が表現木１４００に含まれていることを表している。また、内部ノードｖ８については、左側の子（無効にされた受信機ｕ１に対応するノードｖ１６）は表現木１４００に含まれておらず、右側の子（ノードｖ１７）は表現木１４００に含まれているので、内部ノードｖ８の隣には、（０，１）が示されている。葉は、子となるノードを有していないので、表現木１４００の葉は、子が含まれていないことを示す値を有している。例えば、図１４に示すノードｖ１７は、（０，０）の値を有している。表現木の葉に対応するノードキーは、選択されたノードキーであり、したがって、管理センタは、葉に対応するノードキーを用いて暗号化を行い、暗号文を生成する。
【００４５】
管理センタは、表現木のノードに割り当てられた値を一続きにすることにより、表現コードを生成する。管理センタは、各ノードに割り当てられた値を幅優先順（breadth-first order）に連結する。例えば、図１４に示す具体例では、管理センタは、ノードｖ１、ｖ２、ｖ３、ｖ４、ｖ５、ｖ６、ｖ７、ｖ８、ｖ９、ｖ１０、ｖ１１、ｖ１２、ｖ１３、ｖ１４、ｖ１５、ｖ１７、ｖ２１、ｖ２５、ｖ２９（この他のノードは、表現木に含まれていない。）の値を用いる。すなわち、管理センタは、値（１，１）、（１，１）、（１，１）、（１，１）、（１，１）、（１，１）、（１，１）、（０，１）、（０，０）、（０，１）、（０，０）、（０，１）、（０，０）、（０，１）、（０，０）、（０，０）、（０，０）、（０，０）、（０，０）を用いる。これにより生成される表現コードは、１１１１１１１１１１１１１１０１０００１０００１０００１００００００００００である。
【００４６】
管理センタは、ステップＳ１２３０において、各受信機に表現コードを送信する。受信機は、表現コードを用いて、表現木を再構築することができる。後述するように、受信機は、探索アルゴリズム（例えば幅優先順探索法（breadth-first search））を用いて、受信機の葉ノードからＨＫＴの根までのパス上のノードに対応する表現木の葉を検出する。受信機は、受信機のマスタキーに基づいて、そのノードのノードキーを導出し、このノードキーを用いて復号を行う。
【００４７】
管理センタは、表現コードを生成した後、選択された各ノードキーを用いて、データを暗号文として暗号化する（図７のステップＳ７３０参照）。変形例においては、管理センタは、ノードキーを選択した後であって、表現コードを生成する前に、データを暗号化して暗号文を生成する。上述のように、受信機が１つも無効にされていない場合、管理センタは、全ての暗号文に対して、同じノードキー（図１１におけるＮＫ１）を用いて、暗号化を行う。管理センタは、全ての受信機に暗号文を送信する（図７に示すステップＳ７３５参照）。一具体例においては、管理センタは、選択された各ノードキーを用いて、コンテンツキーをキー暗号文として暗号化し、このキー暗号文を受信機に送信する（図８参照）。そして、管理センタは、コンテンツキーを用いて、コンテンツファイルを暗号化し、暗号化されたコンテンツファイルを受信機に送信する。
【００４８】
図１５は、ＨＫＴ及びノードキーを用いた、受信機による放送復号の処理を示すフローチャートである（図９参照）。一具体例においては、例えば図１に示す放送暗号化システム１００のように、受信機１２０１〜１２０Ｎは、放送管理センタ１０５から放送されたデータ及び暗号文を受信する。他の具体例においては、例えば図４に示す放送暗号化システム４００のように、受信機４２５は、媒体管理センタ４０５が配布のために準備したデータ媒体を介して、データ及び暗号文が供給される。受信機は、ステップＳ１５０５において、管理センタから暗号化パラメータを受信する。図１０のステップＳ１０２０に関連して上述したように、管理センタは、受信機が管理センタから受信した暗号文を復号するために使用する、例えば選択された素数ｐｉ等の公開暗号化パラメータを、受信機に公開する。一具体例においては、受信機は、公開暗号化パラメータを非安全記憶装置（例えば、図２に示す主記憶装置２２５）に保存する。受信機は、ステップＳ１５１０において、管理センタからマスタキーを受信する。図１０のステップＳ１０３０及びステップＳ１０３５に関連して上述したように、管理センタは、受信機用のマスタキーを生成し、このマスタキーを受信機に送信する。受信機は、このマスタキーに基づいて、復号のためのノードキーを導出する。更に、受信機は、ステップＳ１５１５において、管理センタから、管理センタによって定義されたＨＫＴに関する情報を受信する。図１０のステップＳ１０４０に関連して上述したように、管理センタは、ＨＫＴのノードの数と、受信機に関連するノードに対するキー割当とを示す情報を受信機に送信する。変形例においては、管理センタは、暗号化パラメータの一部又は全部と、マスタキーと、ＨＫＴ情報とを受信機に送信する。更に、図７のステップＳ７１０に関連して上述したように、一具体例においては、受信機は、暗号化パラメータと、マスタキーと、ＨＫＴ情報とが、管理センタから直接ではなく、受信機の製造業者を介して供給される。
【００４９】
受信機は、ステップＳ１５２０において、管理センタから表現コードを受信する。図１２のステップＳ１２２０及びステップＳ１２２５に関連して上述したように、管理センタは、表現木（図１４参照）を定義し、この表現木から表現コードを生成する。
【００５０】
受信機は、ステップＳ１５２５において、表現コードを用いて、復号に使用するノードキーを選択する。受信機は、表現コードから表現木を再構築する。上述のように、図１４に示す表現木１４００用の表現コードは、１１１１１１１１１１１１１１０１０００１０００１０００１００００００００００である。受信機は、ＨＫＴ情報を用いて、表現コードを表現木のノードに対応する値、すなわち（１，１）、（１，１）、（１，１）、（１，１）、（１，１）、（１，１）、（１，１）、（０，１）、（０，０）、（０，１）、（０，０）、（０，１）、（０，０）、（０，１）、（０，０）、（０，０）、（０，０）、（０，０）、（０，０）に分離する。受信機は、これらの値に基づき、幅優先順探索法（breadth-first approach）を用いて、表現木内における子ノードの有無を判定する。例えば、最初の値（１，１）は、根（ノードｖ１）に対応し、根が左側の子（内部ノードｖ２）と右側の子（内部ノードｖ３）とを有していることを示している。第２の値（１，１）は、内部ノードｖ２に対応し、内部ノードｖ２が左側の子（内部ノードｖ４）と右側の子（内部ノードｖ５）とを有していることを示している。受信機は、このようなパターンに基づく判定を繰り返して、表現木を完成させる。
【００５１】
受信機は、受信機の葉ノードからＨＫＴの根までのパス上のノードに対応する葉ノードを検出するまで、（例えば幅優先順探索法を用いて、）再構築された表現木を検索する（ここで、表現木のノードｖ１は、ＨＫＴのノードｖ１に対応する）。例えば、図１１及び図１３に示すＨＫＴ１１００及び図１４に示す表現木１４００において、受信機ｕ２は、ノードｖ１７を葉であると認識し、受信機ｕ３及び受信機ｕ４は、共に内部ノードｖ９を葉であると認識する。受信機は、受信機の葉ノードからＨＫＴの根までのパス上のノードに対応する葉ノードを検出しない場合、受信機は、それ自体が無効にされ、有効なノードキーを導出することができないと判定する。例えば、受信機ｕ１は、無効にされており、したがって、受信機ｕ１のノードから根までのパス上に葉を検出することができない。すなわち、受信機ｕ１は、ノードｖ１６に対応し、ノードｖ１６から根（ノードｖ１）までのパスには、ノードｖ１６、ｖ８、ｖ４、ｖ２、ｖ１が含まれ、これらのノードｖ１６、ｖ８、ｖ４、ｖ２、ｖ１は、いずれも表現木の葉に対応していない。一具体例においては、受信機は、（例えば、ネットワーク接続を介して）管理センタと通信することにより、受信機が無効にされたことを確認する。
【００５２】
ノードキーを選択した後、受信機は、ステップＳ１５３０において、受信機のマスタキーに基づいて、選択されたノードキーを導出する。図１１を参照して上述したように、ノードＶｉ用のノードキーは、ＮＫｉと表され、受信機ｕｊのマスタキーは、ＭＫｊと表される。受信機ｕｊが受信する暗号化パラメータは、素数ｐｉと、受信機ｕｊに対応する葉から根までのパス上のノードＶｉに割り当てられた全ての素数ｐｉの積である値ｗｊとである。受信機は、以下の式に基づいて、ノードキーＮＫｉを算出する。
【００５３】
【数４】
2010081656.tif 000006
【００５４】
一具体例においては、受信機は、ｗｊ／ｐｉを予め算出しておく。
【００５５】
受信機は、ステップＳ１５３５において、放送暗号化システムの放送チャンネルを介して、管理センタから１つ以上の暗号文を受信する。なお、変形例として、受信機は、ノードキーを導出する前に、例えばステップＳ１５２０で受信する表現コード等とともに、暗号文を受信してもよい。
【００５６】
ステップＳ１５４０において、受信機は、上述のようにして導出したノードキーを用いて、受信した暗号文を復号する。一具体例においては、受信機は、導出したノードキーを用いて、受信した各暗号文を復号するように試みる。受信機は、例えばチェックサム値を用いて、復号結果が、受信した暗号文に対して正しいものであるか否かを判定する。他の具体例においては、受信機は、導出したノードキーが暗号文の復号に有効であるか否かを判定した後、導出したノードキーに対応する暗号文を復号する。一具体例においては、受信機は、ステップＳ１５０５〜ステップＳ１５１５を１回（又は、受信機の数が変わる等、放送暗号化システムに変化が生じるまで）実行し、そして、暗号文の配信毎に、ステップＳ１５２０〜ステップＳ１５４０を繰り返す。
【００５７】
一具体例においては、受信機は、コンテンツキーを暗号文として受信し、更に、コンテンツキーに対応する暗号化されたコンテンツファイルを受信する（図８参照）。コンテンツキー及びコンテンツファイルの復号を含む放送復号処理のフローチャートを図１６に示す。図１６に示す具体例において、図１５を用いて説明したステップと同様のステップは、図１５に示す具体例と同様に実行されるので、変更があったステップについて、以下に説明する。受信機は、ステップＳ１６０５において、管理センタから暗号化パラメータを受信する。受信機は、ステップＳ１６１０において、管理センタからマスタキーを受信する。受信機は、ステップＳ１６１５において、管理センタから、管理センタによって定義されたＨＫＴに関する情報を受信する。受信機は、ステップＳ１６２０において、管理センタから表現コードを受信する。受信機は、ステップＳ１６２５において、表現コードを用いて、復号に使用するノードキーを選択する。ノードキーを選択した後、受信機は、ステップＳ１６３０において、受信機のマスタキーに基づいて、選択されたノードキーを導出する。
【００５８】
受信機は、ステップＳ１６３５において、放送暗号化システムの放送チャンネルを介して、管理センタから１つ以上のキー暗号文を受信する。受信機が受信する各キー暗号文は、同じコンテンツキーを含んでいるが、異なるノードキーを用いて暗号化されている。受信機は、ステップＳ１６４０において、導出したノードキーを用いて、受信したキー暗号文を復号する。導出されたノードキーは、複数のキー暗号文のうちの１つのキー暗号文のみの復号に有効である。復号されたキー暗号文により、受信機は、コンテンツキーを（例えば、平文（cleartext）として）得ることができる。
【００５９】
受信機は、ステップＳ１６４５において、管理センタから、暗号化されたコンテンツファイルを受信する。コンテンツファイルは、コンテンツキーを用いて暗号化されている。受信機は、例えばヘッダ情報又はファイルサイズに基づいて、キー暗号文と、暗号化されているコンテンツファイルとを区別する。受信機は、ステップＳ１６５０において、コンテンツキーを用いて、暗号化されているコンテンツファイルを復号する。これにより、受信機は、平文のコンテンツファイルにアクセスすることができる。例えば、コンテンツファイルがビデオファイルである場合、受信機は、コンテンツを再生することができる（図３に示す受信機３００及び図６に示す受信機６００参照）。一具体例においては、受信機は、ステップＳ１６０５〜ステップＳ１６１５を１回（又は、受信機の数が変わる等、放送暗号化システムに変化が生じるまで）実行し、そして、暗号文の配信毎に、ステップＳ１６２０〜ステップＳ１６５０を繰り返す。
【００６０】
他の具体例においては、受信機は、記録装置であり、記録可能なデータ媒体の個体に記録されている表現コード及び１つ以上のキー暗号文を再生する。受信機は、データ媒体からの表現コードを用いて、上述のように、ノードキーを導出する。受信機は、導出したノードキーを用いて、データ媒体に記録されているキー暗号文からコンテンツキーを復号する。受信機は、復号されたコンテンツキーを用いて、データ媒体にデータを記録する。受信機が有効なノードキーを導出できず、したがって、データ媒体に記録されているキー暗号文からコンテンツキーを復号できない場合、この受信機は、データ媒体にデータを記録することはできない。管理センタ及び受信機は、後述するように、この記録技術を、サブセットキーを用いる具体例にも適用することができる。
【００６１】
上述のように、管理センタは、ノードキーを生成し、これらのノードキーを用いて暗号化を行う。同様に、受信機は、管理センタからノードキーを受信し、これらのノードキーを用いて復号を行う。他の具体例においては、管理センタは、ノードキーにハッシュ関数を適用して、ハッシュキーを算出し、このハッシュキーを用いて暗号化を行う。ハッシュ関数は、ノードキーの空間上にランダムに分布された要素を、ハッシュキーの長さであるランダムに分布された文字列にマッピングする。これにより、管理センタは、ハッシュ関数を用いて、ノードキーのサイズを暗号化アルゴリズム用のキーのサイズに調整することができる。例えば、一具体例において、ノードキーは１０２４ビットからなり、暗号化アルゴリズムは１２８ビットキーを用いる。ハッシュ関数は、この変換を行う。ハッシュ関数の具体例として、ＭＤ５がある（１９９７年、ＣＲＣプレス社、エー・ジェイ・メネゼス（A.J.Menezes）、ピー・シー・バン・オースコット（P.C.vanOorschot）、エス・エー・バンストーン（S.A.Vanstone）著「応用暗号技術のハンドブック（Handbook of Applied Cryptography）」の第３４７頁、２００１年、スプリンガ（Springer）、コンピュータ科学講義ノート２１３９（Lecture Notses in Computer Science 2139）、暗号化技術の進歩−クリプト２００１（Advances in Cryptology - Crypto 2001）、ディー・ナオール（D.Naor）、エム・ナオール（M.Naor）、ジェイ・ロッツピーチ（J.Lotspiech）著「ステートレス受信機の取消及び追跡方式（Revocation and Tracing Schemes for Stateless Receivers）」、及び１９９７年、コンピュータ科学の基礎に関する第３８回ＩＥＥＥシンポジウム議事録（Proceedings of 38th IEEE Symposium on Foundations of Computer Science）第４５８〜４６７頁、エム・ナオール（M.Naor）、オー・レインゴールド（O.Reingold）著「効率的擬似ランダム関数の数論的構築（Number-Theoretic Constructions of Efficient Pseudo-Random Functions）」参照。これらの文献は参照により本願に援用される）。
【００６２】
サブセットキーを有する階層的キー木
一具体例において、放送暗号化システムは、例えば図１及び図４に示す放送暗号化システム１００、４００のように、管理センタと、Ｎ個の受信機とを備え、管理センタは、階層的キー木（ＨＫＴ）及びサブセットキーを用いる。この具体例においては、サブセットキーは、上述したサブキーとして機能する。図７及び図９に示す処理をこの具体例に適用する手法について以下に述べる。
【００６３】
図１７は、サブセット及びサブセットキーを有するＨＫＴを用いて、放送暗号化システムを設定し、受信機にマスタキーを割り当てる手順を示すフローチャートである（図７のステップＳ７０５及びステップＳ７１０参照）。図１８は、ＨＫＴ１８００において、ノード１８１０に対するサブセット１８０５の割当を示す図である。ここで、ＨＫＴ１８００は、２７個の受信機のグループに対応する３次の木である。図１９は、図１８に示すＨＫＴ１８００において、ノード１８１０に対するサブセットキー１９０５の割当を示す図である。サブセット及びサブセットキーについては、後に説明する。
【００６４】
管理センタは、ステップＳ１７０５において、ＨＫＴを定義する。ＨＫＴは、Ｎ個の葉を有する根の付いた完全ａ分木（rooted full a-ary tree）であり、葉と、根と、内部ノードとを含む（Ｎ−１）／（ａ−１）＋Ｎ個のノードを有する。内部ノードは、図１８に示すように、ｖｋ（ｋ＝１，・・・，（Ｎ−１）／（ａ−１））として表される。ここで、Ｎがａの累乗ではない場合、管理センタは、Ｎより大きく且つＮに最も近いａの累乗個の葉を有するＨＫＴを定義する。管理センタは、ステップＳ１７１０において、各受信機をそれぞれの葉に割り当てる。受信機は、図１８に示すように、ｕｊ（ｊ＝１，・・・，Ｎ）として表される。ここで、Ｎがａの累乗ではない場合、余りの葉には「仮想の」受信機が割り当てられる。なお、仮想の受信機は、仮想のエンティティであり、後に無効にする必要はない。
【００６５】
管理センタは、ステップＳ１７１５において、各内部ノードにサブセットを定義する。管理センタは、各内部ノードｖｋに対して、２ａ−２個のサブセットを定義する。サブセットは、次のように示される。
【００６６】
【数５】
2010081656.tif 000007
【００６７】
ここで、ｋは、サブセットがどの内部ノードｖｋに対応しているかを示し、ｂ１ｂ２・・・ｂｉ・・・ｂａは、サブセットに含まれるａ値（サブセットの値）を示している。サブセットの値は、サブセットに対応する内部ノードの子ノードを示し、及び、後述するように、暗号化に使用するためにどのサブセットキーが選択されたかを示す。更に、管理センタは、根（ノードｖ１）に対して、サブセットＳ１，１１・・・１を定義する。図１８は、内部ノードに対するサブセットの割当を示している。例えば、管理センタは、内部ノードｖ２に、サブセットＳ２，１００、Ｓ２，０１０、Ｓ２，００１、Ｓ２，１１０、Ｓ２，１０１、Ｓ２，０１１を割り当てる。
【００６８】
管理センタは、ステップＳ１７２０において、暗号化パラメータを選択する。管理センタは、暗号化パラメータを用いて、例えばキー等の暗号化のための値を生成する。暗号化パラメータの一部は、公開暗号化パラメータであり、管理センタは、ステップＳ１７２５において、公開暗号化パラメータを公開する。なお、管理センタは、残りの秘密暗号化パラメータを受信機に対して秘密にする。管理センタは、２つの大きな素数ｑ１、ｑ２を選択し、Ｍ＝ｑ１×ｑ２である値Ｍを算出する。管理センタは、この値Ｍを、公開暗号化パラメータとして公開する。更に、管理センタは、Ｋ∈Ｚ＊Ｍとして、値Ｋを秘密暗号化パラメータとしてランダムに選択する。更に、管理センタは、以下に示すような、（２ａ−２）×（Ｎ−１）／（ａ−１）＋１個の素数を選択する。
【００６９】
【数６】
2010081656.tif 000008
【００７０】
管理センタは、各素数
【００７１】
【数７】
2010081656.tif 000009
【００７２】
を、対応するサブセット
【００７３】
【数８】
2010081656.tif 000010
【００７４】
に割り当てる（例えば、素数ｐ１，１００は、サブセットＳ１，１００に割り当てられる）。そして、管理センタは、素数
【００７５】
【数９】
2010081656.tif 000011
【００７６】
及びその割当を公開する。更に、管理センタは、以下に示すような値Ｔを算出する。
【００７７】
【数１０】
2010081656.tif 000012
【００７８】
管理センタは、値Ｔを公開しない。
【００７９】
管理センタは、ステップＳ１７３０において、暗号化パラメータを用いて、サブセットキーを生成する。サブセットキーは、図１９に示すように、以下のように表される。
【００８０】
【数１１】
2010081656.tif 000013
【００８１】
管理センタは、各サブセット
【００８２】
【数１２】
2010081656.tif 000014
【００８３】
に対するサブセットキー
【００８４】
【数１３】
2010081656.tif 000015
【００８５】
を、以下のようにして求める。
【００８６】
【数１４】
2010081656.tif 000016
【００８７】
管理センタは、各サブセットキー
【００８８】
【数１５】
2010081656.tif 000017
【００８９】
を、対応するサブセット
【００９０】
【数１６】
2010081656.tif 000018
【００９１】
に割り当てる。
【００９２】
更に、管理センタは、ステップＳ１７３５において、各サブセットキーを内部ノードの子ノードに割り当てる。サブセットの値は、サブセットに対応する内部ノードの子ノードを示している。管理センタは、サブセットの値が１であるサブセットの内部ノードの各子ノードに、サブセットキーを割り当てる。図１９は、子ノードに対するサブセットキーの割当を示している。例えば、図１８及び図１９に示すように、サブセットＳ１，１１１は、根（ノードｖ１）に対応し、サブセットキーＳＫ１，１１１は、根の各子ノード（内部ノードｖ２、ｖ３、ｖ４）に割り当てられる。サブセットキーＳＫ１，００１は、根の右側の子ノード（内部ノードｖ４）のみに割り当てられる。このようにして、管理センタは、２ａ−１−１個のサブセットキーを各子ノードに割り当てる（及びサブセットキーＳＫ１，１１・・・１を根の各子ノードに割り当てる）。
【００９３】
管理センタは、各受信機ｕｊに対し、追加的なパラメータである値ｗｊを生成する。値ｗｊは、内部ノードｖｋに割り当てられたサブセットであって、受信機ｕｊの葉ノードから根のノードまでのパス上の子ノード（後述する）に割り当てられたサブセットキー
【００９４】
【数１７】
2010081656.tif 000019
【００９５】
に対応するサブセット
【００９６】
【数１８】
2010081656.tif 000020
【００９７】
に割り当てられた全ての素数
【００９８】
【数１９】
2010081656.tif 000021
【００９９】
の積である。例えば、図１８に示すＨＫＴ１８００では、値ｗ１は、受信機ｕ１に対応し、各ノードｖ５、ｖ２、ｖ１に割り当てられた、ｂ１＝１の値を有するサブセットに割り当てられている素数の積である。したがって、ｗ１＝ｐ５，１００×ｐ５，１１０×ｐ５，１０１×ｐ２，１００×ｐ２，１１０×ｐ２，１０１×ｐ１，１００×ｐ１，１１０×ｐ１，１０１×ｐ１，１１１である。これに代えて、管理センタが値ｗｊを提供するのではなく、受信機が素数
【０１００】
【数２０】
2010081656.tif 000022
【０１０１】
から値ｗｊを導出するようにしてもよい。
【０１０２】
管理センタは、ステップＳ１７４０において、暗号化パラメータを用いて、マスタキーを生成する。マスタキーは、図１９に示すように、ＭＫｊとして表される。ここで、管理センタは、以下の式に基づいて、各受信機ｕｊに対応するマスタキーＭＫｊを算出する。
【０１０３】
【数２１】
2010081656.tif 000023
【０１０４】
管理センタは、各マスタキーＭＫｊを対応する受信機ｕｊに割り当てる。マスタキーＭＫｊを用いて、受信機ｕｊに対応する葉、又は受信機ｕｊに対応する葉から根までのパスに含まれる内部ノードｖｋに対応する全てのサブセットキー
【０１０５】
【数２２】
2010081656.tif 000024
【０１０６】
を導出することができる。例えば、図１９に示すＨＫＴ１８００において、受信機ｕ１には、マスタキーＭＫ１が割り当てられており、このマスタキーＭＫ１を用いて、サブセットキーＳＫ５，１００、ＳＫ５，１１０、ＳＫ５，１０１、ＳＫ２，１００、ＳＫ２，１１０、ＳＫ２，１０１、ＳＫ１，１００、ＳＫ１，１１０、ＳＫ１，１０１、ＳＫ１，１１１を導出することができる。受信機ｕｊのいずれも無効にされていない場合は、サブセットキーＳＫ１，１１・・・１は、全てのマスタキーＭＫｊから導出することができる。管理センタは、ステップＳ１７４５において、各マスタキーＭＫｊを対応する受信機ｕｊに送信する。
【０１０７】
管理センタは、ステップＳ１７５０において、ＨＫＴに関する情報を各受信機に送信する。管理センタは、ＨＫＴの構造（例えば、ＨＫＴのノード数）及び受信機に関連する割当（例えば、ノードに対するサブセットキー及びサブセットの割当）を示す情報を、受信機に送信する。上述のように、管理センタは、素数
【０１０８】
【数２３】
2010081656.tif 000025
【０１０９】
等の公開暗号化パラメータ及びどの内部ノードがこの素数
【０１１０】
【数２４】
2010081656.tif 000026
【０１１１】
に対応しているかを示す情報を公開する。更に、管理センタは、各サブセット
【０１１２】
【数２５】
2010081656.tif 000027
【０１１３】
がどの内部ノードｖｋに割り当てられており、及び受信機のマスタキーＭＫｊから導出することができるサブセットキー
【０１１４】
【数２６】
2010081656.tif 000028
【０１１５】
がどの内部ノードｖｋ又は葉に割り当てられているかを示す情報を送信する。
【０１１６】
図７のステップＳ７１０について上述したように、他の具体例においては、管理センタは、受信機の製造業者にマスタキーを供給し、受信機の製造業者が受信機にマスタキーを組み込む。この場合、管理センタは、製造業者を介して、公開暗号化パラメータ及びＨＫＴ情報を受信機に供給する。
【０１１７】
図２０は、ＨＫＴを用いて受信機を無効にし、ノードキーを選択し、表現コードを生成する処理を示すフローチャートである（図７のステップＳ７１５、Ｓ７２０、Ｓ７２５参照）。図２１は、図１８のＨＫＴ１８００において、無効にされた受信機２１０５及び選択されたサブセットキー２１１０に対応するサブセットのノードを示す図である。管理センタは、ステップＳ２００５において、１つ以上の受信機を無効にする。管理センタは、受信機が管理センタから送信されてくる暗号文を復号する権限を有さなくなった場合に、その受信機を無効又は有効ではなくする。例えば、管理センタは、必要な料金を支払っていない受信機又はライセンスが有効ではなくなった受信機を無効にする。図２１では、無効にされた受信機２１０５には、ＨＫＴ１８００の対応するノードに「×」印を付している。管理センタは、受信機ｕ２、ｕ１３、ｕ２７を無効にしている。残りの受信機ｕ１、ｕ３〜ｕ１２、ｕ１４〜ｕ２６は、無効にされていない、すなわち有効な受信機である。
【０１１８】
管理センタは、ステップＳ２０１０において、無効にされた受信機に割り当てられているマスタキーに基づいて生成できるサブセットキーを無効にする。例えば、図１２に示す具体例では、管理センタは、受信機ｕ２を無効にし、この受信機ｕ２にはマスタキーＭＫ２が割り当てられている。受信機ｕ２は、マスタキーＭＫを用いて、サブセットキーＳＫ５，０１０、ＳＫ５，１１０、ＳＫ５，０１１、ＳＫ２，１００、ＳＫ２，１１０、ＳＫ２，１０１、ＳＫ１，１００、ＳＫ１，１１０、ＳＫ１，１０１、ＳＫ１，１１１を生成することができる。したがって、管理センタは、サブセットキーＳＫ５，０１０、ＳＫ５，１１０、ＳＫ５，０１１、ＳＫ２，１００、ＳＫ２，１１０、ＳＫ２，１０１、ＳＫ１，１００、ＳＫ１，１１０、ＳＫ１，１０１、ＳＫ１，１１１を無効にする。
【０１１９】
無効にされていない受信機の各マスタキーについては、管理センタは、ステップＳ２０１５において、これらのマスタキーに基づいて生成でき、及び他の大部分のマスタキーに基づいて生成でき、且つ無効にされた受信機に対応するマスタキーからは生成できないサブセットキーを選択する。ＨＫＴ１８００において、管理センタは、対応する無効にされていないサブセットキーを有する大部分の子ノードを示すサブセットに対応する無効にされていないサブセットを選択する（図１８を用いて説明したように、サブセットは内部ノードに割り当てられており、また図１９を用いて説明したように、サブセットキーは、子ノードに割り当てられている）。
【０１２０】
他の手法においては、管理センタは、無効にされた受信機に対応する葉から根までのパス上の枝を取り除く。枝を取り除くことにより、１つ以上の独立した部分木が残る（１つ以上の部分木は、単一の枝しか有していない場合もある）。図２２は、図１８に示すＨＫＴ１８００から枝を取り除いた木２２００を示している。取り除かれた枝２２０５は、破線により示されている。一方、残っている枝２２１０は、実線により示されている。管理センタは、これらの部分木の根となるノードに対応し、これらの部分木に含まれる子ノードを示すサブセットに対応するサブセットキーを選択する。例えば、図２２に示す具体例では、内部ノードｖ５は、部分木の根である。内部ノードｖ５は、３個の子ノードを有する。右側の子ノード及び左側の子ノードのサブセットキーは、無効にされておらず、一方、中央の子ノードのサブセットキーは、無効にされている。サブセットＳ５，１０１は、内部ノードｖ５の左側及び右側の子ノードを示しており、したがって、管理センタは、対応するサブセットキーＳＫ５，１０１を選択する。図２１及び図２２では、選択されたサブセットキー２１１０に対応するノードを囲む正方形の枠によって、選択されたサブセットキー２１１０を示している。すなわち、管理センタは、サブセットキーＳＫ２，０１１、ＳＫ３，１０１、ＳＫ４，１１０、ＳＫ５，１０１、ＳＫ９，０１１、ＳＫ１３，１１０を選択している。
【０１２１】
管理センタは、ステップＳ２０２０において、ＨＫＴ及び無効にされた受信機に基づいて、表現木を定義する。図２３は、図１８及び図２１に示すＨＫＴ１８００に基づく表現木２３００を示している。図２３の濃い又は太い枝は、表現木２３００の一部である枝を示している。図１４の薄い又は細い枝は、表現木２３００に含まれない。無効にされた受信機２１０５及び選択されたサブセットキー２１１０は、図２１と同様に示されている。表現木２３００の根は、対応するＨＫＴの根である。表現木２３００の葉は、選択されたサブセットキーに対応するサブセットである。表現木２３００の内部ノードは、葉と根の間のノードである。
【０１２２】
管理センタは、ステップＳ２０２５において、表現木２３００に基づいて、表現コードを生成する。管理センタは、表現木の各ノードに、２つの値を割り当てる。管理センタは、ＨＫＴの対応するノードに子が存在する場合、ＨＫＴの対応するノードのどの子が表現木に含まれているかを示す子値（child value）を割り当てる。管理センタは、ノードに対応するサブセットが存在する場合、ノードに対応するどのサブセットが、選択された対応するサブセットキーを有するかを示すサブセット値を、割り当てる。この具体例では、ａ分木を用いているので、表現木の各ノードは、ａ個の子を有する可能性がある。したがって、管理センタは、ａ個の１ビット値を用いて、サブセット値を示すことができる。図２３では、表現木２３００の各ノードの隣に示す括弧で括られた（「子値」、「サブセット値」）のパターンを有する２つの数によって、子値及びサブセット値を示している。例えば、根の隣には、（１１１，０００）が示されている。「１１１」は子値であり、根の左側、中央、右側の子が表現木２３００に含まれていることを表している。「０００」はサブセット値であり、根のサブセットに対応するサブセットキーが１つも選択されていないことを表している。また、内部ノードｖ２の隣には、（１００，０１１）が示されている。子値「１００」は、左側の子（内部ノードｖ５）が表現木２３００に含まれており、中央及び右側の子（内部ノードｖ６、ｖ７）が表現木２３００に含まれていないことを表している。サブセット値「０１１」は、値０１１を有するサブセットに対応するサブセットキー（すなわち、サブセットキーＳＫ２，０１１）が選択されていることを表している。表現木の葉は、子を有していないことを示す値を有している。例えば、図２３に示す具体例では、内部ノードｖ５、ｖ９は、それぞれ値（０００，１０１）、（０００，０１１）を有する。このように、表現木２３００は、ノードｖ１、ｖ２、ｖ３、ｖ４、ｖ５、ｖ９、ｖ１３を含み、管理センタは、サブセットキーＳＫ２，０１１、ＳＫ３，１０１、ＳＫ４，１１０、ＳＫ５，１０１、ＳＫ９，０１１、ＳＫ１３，１１０を選択している。
【０１２３】
管理センタは、表現木のノードに割り当てられた値を一続きにすることにより、表現コードを生成する。管理センタは、各ノードに割り当てられた値を幅優先順に連結する。例えば、図２３に示す具体例では、管理センタは、ノードｖ１、ｖ２、ｖ３、ｖ４、ｖ５、ｖ９、ｖ１３（ＨＫＴの他のノードは、表現木に含まれていない。）の値を用いる。すなわち、管理センタは、値（１１１，０００）、（１００，０１１）、（０１０，１０１）、（００１，１１０）、（０００，１０１）、（０００，０１１）、（０００，１１０）を用いる。これにより生成される表現コードは、１１１０００１０００１１０１０１０１００１１１００００１０１００００１１０００１１０である。
【０１２４】
管理センタは、ステップＳ２０３０において、各受信機に表現コードを送信する。受信機は、表現コードを用いて、表現木を再構築することができる。後述するように、受信機は、表現木内のサブセット値に基づく探索アルゴリズムを用いて、受信機の葉ノードからＨＫＴの根までのパス上のノードであって、受信機のマスタキーによって導出できる対応するサブセットを有するノードに対応する表現木のノードを検出する。受信機は、受信機のマスタキーに基づいて、そのサブセットキーを導出し、このサブセットキーを用いて復号を行う。
【０１２５】
管理センタは、表現コードを生成した後、選択された各サブセットキーを用いて、データを暗号文として暗号化する（図７のステップＳ７３０参照）。変形例においては、管理センタは、サブセットキーを選択した後であって、表現コードを生成する前に、データを暗号化して暗号文を生成する。上述のように、受信機が１つも無効にされていない場合、管理センタは、全ての暗号文を、同じサブセットキー（図１９におけるＳＫ１，１１・・・１）を用いて暗号化する。そして、管理センタは、全ての受信機に暗号文を送信する（図７に示すステップＳ７３５参照）。一具体例においては、管理センタは、選択されたサブセットキーを用いて、コンテンツキーをキー暗号文として暗号化し、このキー暗号文を受信機に送信する（図８参照）。そして、管理センタは、コンテンツキーを用いて、コンテンツファイルを暗号化し、暗号化されたコンテンツファイルを受信機に送信する。
【０１２６】
図２４は、ＨＫＴ及びサブセットキーを用いた、受信機による放送復号の処理を示すフローチャートである（図９参照）。一具体例においては、例えば図１に示す放送暗号化システム１００のように、受信機は、管理センタから放送されたデータ及び暗号文を受信する。他の具体例においては、例えば図４に示す放送暗号化システム４００のように、受信機は、管理センタが配布のために準備したデータ媒体を介して、データ及び暗号文が供給される。受信機は、ステップＳ２４０５において、管理センタから暗号化パラメータを受信する。図１７のステップＳ１７２０に関連して上述したように、管理センタは、受信機が管理センタから受信した暗号文を復号するために使用する、例えばサブセット
【０１２７】
【数２７】
2010081656.tif 000029
【０１２８】
に対する素数
【０１２９】
【数２８】
2010081656.tif 000030
【０１３０】
の割当等の公開暗号化パラメータを受信機に公開する。一具体例においては、受信機は、公開暗号化パラメータを非安全記憶装置（例えば、図２に示す主記憶装置２２５）に保存する。受信機は、ステップＳ２４１０において、管理センタからマスタキーを受信する。受信機は、マスタキーを安全記憶装置に保存する。図１７のステップＳ１７４０及びステップＳ１７４５に関連して上述したように、管理センタは、受信機用のマスタキーを生成し、このマスタキーを受信機に送信する。受信機は、このマスタキーに基づいて、復号のためのノードキーを導出する。更に、受信機は、ステップＳ２４１５において、管理センタから、管理センタによって定義されたＨＫＴに関する情報を受信する。図１７のステップＳ１７５０に関連して上述したように、管理センタは、ＨＫＴの構造及び受信機に関連する割当を表す情報を受信機に送信する。変形例においては、管理センタは、暗号化パラメータの一部又は全部と、マスタキーと、ＨＫＴ情報とを受信機に送信する。更に、図７のステップＳ７１０に関連して上述したように、一具体例においては、受信機は、暗号化パラメータと、マスタキーと、ＨＫＴ情報とが、管理センタから直接ではなく、受信機の製造業者を介して供給される。
【０１３１】
受信機は、ステップＳ２４２０において、管理センタから表現コードを受信する。図２０のステップＳ２０２０及びステップＳ２０２５に関連して上述したように、管理センタは、表現木（図２３参照）を定義し、この表現木から表現コードを生成する。
【０１３２】
受信機は、ステップＳ２４２５において、表現コードを用いて、復号に使用するサブセットキーを選択する。受信機は、表現コードから表現木を再構築する。上述のように、図２３に示す表現木２３００用の表現コードは、１１１０００１０００１１０１０１０１００１１１００００１０１００００１１０００１１０である。受信機は、ＨＫＴ情報を用いて、表現コードを表現木のノードに対応する値、すなわち（１１１，０００）、（１００，０１１）、（０１０，１０１）、（００１，１１０）、（０００，１０１）、（０００，０１１）、（０００，１１０）に分離する。受信機は、これらの値に基づき、幅優先順探索法（breadth-first approach）を用いて、表現木内における子ノードの有無を判定する。例えば、最初の値（１１１，０００）は、根（ノードｖ１）に対応し、子値「１１１」は、根が左側の子（内部ノードｖ２）と、中央の子（内部ノードｖ３）と、右側の子（内部ノードｖ４）とを有していることを示している。第２の値（１００，０１１）は、内部ノードｖ２に対応し、内部ノードｖ２が左側の子（内部ノードｖ５）を有しているが、中央及び右側の子を有していないことを示している。受信機は、このようなパターンに基づく判定を繰り返して、表現木を完成させる。サブセット値は、サブセットキーが選択されている場合、各ノードに対してどのサブセットキーが選択されているかを表している。
【０１３３】
受信機は、内部ノードｖｋに対応するとともに、受信機の葉ノードからＨＫＴの根までのパス上の子ノードに割り当てられたサブセットキーに対応するサブセットを検出するまで、（例えば幅優先順探索法を用いて、）再構築された表現木を検索する（ここで、表現木のノードｖ１は、ＨＫＴのノードｖ１に対応している）。上述のように、管理センタは、ＨＫＴのノードに各サブセットを割り当てる（図１８参照）。各サブセットは、対応するサブセットキーを有している。管理センタは、サブセットの値を用いて、サブセットに対応するノードの１つ以上の子ノードに、対応するサブセットキーを割り当てる（図１９参照）。受信機は、子ノードに対するサブセットキーの割当に関する情報に基づいて、表現木により示されているどのサブセットキーを用いて復号を行うかを判定する。受信機は、表現木を検索し、受信機に対応する葉からＨＫＴの根までのパス上のノードに対応するサブセットキーを検出する。例えば、図１８、図１９及び図２１のＨＫＴ１８００及び図２３の表現木２３００に示すように、受信機ｕ１は、ＨＫＴ１８００における受信機ｕ１に対応する葉から根までのパス上のノードに対応する選択されたサブセットキーとして、サブセットキーＳＫ５，１０１を検出する。受信機ｕ１のパスには、受信機ｕ１に対応する葉と、ノードｖ５、ｖ２、ｖ１が含まれている。受信機ｕ１に対応する葉には、サブセットキーＳＫ５，１０１が対応し、したがって、受信機ｕ１のパス上のノードには、サブセットキーが対応している。また、サブセットキーＳＫ５，１０１は、受信機ｕ３に対応するノードにも対応しているので、同様に、受信機ｕ３は、サブセットキーＳＫ５，１０１を、選択されたサブセットキーとして検出する。受信機ｕ４〜ｕ９は、サブセットキーＳＫ２，０１１を検出する。受信機が、受信機の葉ノードからＨＫＴの根までのパス上のノードに対応するサブセットキーを表現木内で検出できない場合、受信機は、それ自体が無効にされ、有効なサブセットキーを導出することができないと判定する。例えば、受信機ｕ２は、無効にされており、したがって、受信機ｕ２は、受信機ｕ２に対応する葉から根までのパス上のノードに対応するサブセットキーを検出することができない。受信機ｕ２のパス上には、受信機ｕ２に対応する葉と、ノードｖ５、ｖ２、ｖ１が存在する。これらのうち、いずれのノードも表現木におけるサブセットキーに対応していない。一具体例においては、受信機は、（例えば、ネットワーク接続を介して）管理センタと通信することにより、受信機が無効にされたことを確認する。
【０１３４】
ノードキーを選択した後、受信機は、ステップＳ２４３０において、受信機のマスタキーに基づいて、選択されたサブセットキーを導出する。上述のように、サブセットキーは、
【０１３５】
【数２９】
2010081656.tif 000031
【０１３６】
と表され、マスタキーは、図１１に示すように、ＭＫｊと表される。受信機ｕｊが受信する暗号化パラメータは、素数
【０１３７】
【数３０】
2010081656.tif 000032
【０１３８】
と、値ｗｊとである。値ｗｊは、内部ノードｖｋに割り当てられたサブセットであって、受信機ｕｊに対応する葉ノードから根までのパス上に存在する子ノードに割り当てられたサブセットキー
【０１３９】
【数３１】
2010081656.tif 000033
【０１４０】
に対応するサブセット
【０１４１】
【数３２】
2010081656.tif 000034
【０１４２】
に割り当てられた全ての素数
【０１４３】
【数３３】
2010081656.tif 000035
【０１４４】
の積である。これに代えて、受信機は、値ｗｊを受信するのではなく、素数
【０１４５】
【数３４】
2010081656.tif 000036
【０１４６】
から値ｗｊを算出してもよい。受信機は、以下の式に基づいて、サブセットキー
【０１４７】
【数３５】
2010081656.tif 000037
【０１４８】
を算出する。
【０１４９】
【数３６】
2010081656.tif 000038
【０１５０】
一具体例においては、受信機は、
【０１５１】
【数３７】
2010081656.tif 000039
【０１５２】
を予め算出しておく。
【０１５３】
受信機は、ステップＳ２４３５において、放送暗号化システムの放送チャンネルを介して、管理センタから１つ以上の暗号文を受信する。なお、変形例として、受信機は、サブセットキーを導出する前に、例えばステップＳ２４２０で受信する表現コード等とともに、暗号文を受信してもよい。
【０１５４】
ステップＳ２４４０において、受信機は、上述のようにして導出したサブセットキーを用いて、受信した暗号文を復号する。一具体例においては、受信機は、導出したサブセットキーを用いて、受信した各暗号文を復号するように試みる。受信機は、例えばチェックサム値を用いて、復号結果が、受信した暗号文に対して正しいものであるか否かを判定する。他の具体例においては、受信機は、導出したサブセットキーが暗号文の復号に有効であるか否かを判定した後、導出したサブセットキーに対応する暗号文を復号する。一具体例においては、受信機は、ステップＳ２４０５〜ステップＳ２４１５を１回（又は、受信機の数が変わる等、放送暗号化システムに変化が生じるまで）実行し、そして、暗号文の配信毎に、ステップＳ２４２０〜ステップＳ２４４０を繰り返す。
【０１５５】
一具体例においては、受信機は、コンテンツキーを暗号文として受信し、更に、コンテンツキーに対応する暗号化されたコンテンツファイルを受信する（図８参照）。コンテンツキー及びコンテンツファイルの復号を含む放送復号処理のフローチャートを図２５に示す。図２５に示す具体例において、図２４を用いて説明したステップと同様のステップは、図２４に示す具体例と同様に実行されるので、変更があったステップについて、以下に説明する。受信機は、ステップＳ２５０５において、管理センタから暗号化パラメータを受信する。受信機は、ステップＳ２５１０において、管理センタからマスタキーを受信する。受信機は、ステップＳ２５１５において、管理センタから、管理センタにより定義されたＨＫＴに関する情報を受信する。受信機は、ステップＳ２５２０において、管理センタから表現コードを受信する。受信機は、ステップＳ２５２５において、表現コードを用いて、復号に使用するノードキーを選択する。サブセットキーを選択した後、受信機は、ステップＳ２５３０において、受信機のマスタキーに基づいて、選択されたサブセットキーを導出する。
【０１５６】
受信機は、ステップＳ２５３５において、放送暗号化システムの放送チャンネルを介して、管理センタから１つ以上のキー暗号文を受信する。受信機が受信する各キー暗号文は、同じコンテンツキーを含んでいるが、異なるサブセットキーを用いて暗号化されている。受信機は、ステップＳ２５４０において、導出したサブセットキーを用いて、受信したキー暗号文を復号する。導出されたサブセットキーは、複数のキー暗号文のうちの１つのキー暗号文のみの復号に有効である。復号されたキー暗号文により、受信機は、コンテンツキーを（例えば、平文として）得ることができる。
【０１５７】
受信機は、ステップＳ２５４５において、管理センタから、暗号化されたコンテンツファイルを受信する。コンテンツファイルは、コンテンツキーを用いて暗号化されている。受信機は、例えばヘッダ情報又はファイルサイズに基づいて、キー暗号文と、暗号化されているコンテンツファイルとを区別する。受信機は、ステップＳ２５５０において、コンテンツキーを用いて、暗号化されているコンテンツファイルを復号する。これにより、受信機は、平文のコンテンツファイルにアクセスすることができる。例えば、コンテンツファイルがビデオファイルである場合、受信機は、コンテンツを再生することができる（図３に示す受信機３００及び図６に示す受信機６００参照）。一具体例においては、受信機は、ステップＳ２５０５〜ステップＳ２５１５を１回（又は、受信機の数が変わる等、放送暗号化システムに変化が生じるまで）実行し、そして、暗号文の配信毎に、ステップＳ２５２０〜ステップＳ２５５０を繰り返す。
【０１５８】
一具体例においては、受信機は、管理センタから、暗号化パラメータとして受信した素数
【０１５９】
【数３８】
2010081656.tif 000040
【０１６０】
を保存する。他の具体例においては、受信機は、この素数
【０１６１】
【数３９】
2010081656.tif 000041
【０１６２】
を保存せず、必要に応じて生成する。この場合、受信機は、値Ｌを保存する。ここで、値Ｌは、間隔（interval）（（ｋ−１）Ｌ，ｋＬ）が少なくとも２ａ−１個の素数を含むように選択される。更に、一具体例においては、値Ｌは、Ｌ＞（２ａ−１）ｌｎ（２ａＮｌｏｇ２ａＮ）を満たすように選択される。受信機は、例えばミラー・ラビンアルゴリズム（Miller-Rabin algorithm）等の素数判定アルゴリズムを用いて、（ｋ−１）Ｌより大きいｘ番目に小さい素数を検索する。ここで、ｘは、素数
【０１６３】
【数４０】
2010081656.tif 000042
【０１６４】
に対するサブセット
【０１６５】
【数４１】
2010081656.tif 000043
【０１６６】
の値によって示される２進表現の１０進数の値である。例えば、受信機は、素数ｐ１，１１１に対して７番目に小さい奇素数（odd prime）を使用する（「１１１」は、１０進数の値７の２進表現である）。
【０１６７】
サブセットキー及び各受信機用の複数のマスタキーを有する階層的キー木
一具体例において、放送暗号化システム１００、４００のように、放送暗号化システムは、管理センタと、Ｎ個の受信機とを備え、管理センタは、階層的キー木（ＨＫＴ）及びサブセットキーを用い、各受信機に複数のマスタキーを供給する。この具体例は、図１７〜図２５を用いて説明した具体例に類似しており、その変化については以下に説明する。管理センタは、図１７〜図１９を用いて上述した処理と同様の手法により、放送暗号化システムを設定する。なお、この具体例においては、管理センタは、各受信機に対して、複数のマスタキーを生成する。後述するように、受信機は、上述の具体例のように、１つのマスタキーを用いて、受信機の葉から根までのパス上のノードに割り当てられたサブセットキーを導出するのではなく、受信した各マスタキーを用いて、各ノードに割り当てられたサブセットキーを導出する。この具体例では、管理センタは、受信機の葉から根までのパス上の各ノード毎に、１つのマスタキーを受信機に供給する（なお、根にはサブセットキーが割り当てられないので、根自体は除く）。
【０１６８】
図２６は、サブセット及びサブセットキーを有するＨＫＴを用いて、放送暗号化システムを設定し、受信機に複数のマスタキーを割り当てる手順を示すフローチャートである（図７のステップＳ７０５及びステップＳ７１０参照）。図２７は、ＨＫＴ２７００において、ノード２７１０に対するサブセットキー２７０５の割当を示す図である。ここで、ＨＫＴ２７００は、２７個の受信機のグループに対応する３次の木である。図２７において、サブセットは、図１８におけるＨＫＴ１８００と同様に、ＨＫＴ２７００に割り当てられている。
【０１６９】
管理センタは、ステップＳ２６０５において、ＨＫＴを定義する。ＨＫＴは、Ｎ個の葉を有する根の付いた完全ａ分木（rooted full a-ary tree）であり、葉と、根と、内部ノードとを含む（Ｎ−１）／（ａ−１）＋Ｎ個のノードを有する。内部ノードは、図２７に示すように、ｖｋ（ｋ＝１，・・・，（Ｎ−１）／（ａ−１））として表される。ここで、Ｎがａの累乗ではない場合、管理センタは、Ｎより大きく且つＮに最も近いａの累乗個の葉を有するＨＫＴを定義する。管理センタは、ステップＳ２６１０において、各受信機をそれぞれの葉に割り当てる。受信機は、図２７に示すように、ｕｊ（ｊ＝１，・・・，Ｎ）として表される。Ｎがａの累乗ではない場合、余りの葉には「仮想の」受信機が割り当てられる。なお、仮想の受信機は、仮想のエンティティであり、後に無効にする必要はない。
【０１７０】
管理センタは、ステップＳ２６１５において、各内部ノードにサブセットを定義する。管理センタは、各内部ノードｖｋに対して、２ａ−２個のサブセットを定義する。サブセットは、ａ個の値を有し、次のように示される。
【０１７１】
【数４２】
2010081656.tif 000044
【０１７２】
ここで、ｋは、サブセットがどの内部ノードｖｋに対応しているかを示し、ｂ１ｂ２・・・ｂｉ・・・ｂａは、サブセットに含まれるａ値（サブセットの値）を示している。サブセットの値は、サブセットに対応する内部ノードの子ノードを示し、及び、後述するように、暗号化に使用するためにどのサブセットキーが選択されたかを示す。更に、管理センタは、根（ノードｖ１）に対して、サブセットＳ１，１１・・・１を定義する。サブセットは、図１８に示すＨＫＴ１８００と同様に、図２７に示すＨＫＴ２７００に割り当てられる。例えば、管理センタは、内部ノードｖ２に、サブセットＳ２，１００、Ｓ２，０１０、Ｓ２，００１、Ｓ２，１１０、Ｓ２，１０１、Ｓ２，０１１を割り当てる。
【０１７３】
管理センタは、ステップＳ２６２０において、暗号化パラメータを選択する。管理センタは、暗号化パラメータを用いて、例えばキー等の暗号化のための値を生成する。暗号化パラメータの一部は、公開暗号化パラメータであり、管理センタは、ステップＳ２６２５において、公開暗号化パラメータを公開する。なお、管理センタは、残りの秘密暗号化パラメータを受信機に対して秘密にする。管理センタは、２つの大きな素数ｑ１、ｑ２を選択し、Ｍ＝ｑ１×ｑ２である値Ｍを算出する。管理センタは、この値Ｍを公開暗号化パラメータとして公開する。更に、管理センタは、Ｋｋ∈Ｚ＊Ｍとして、値Ｋｋを秘密暗号化パラメータとしてランダムに選択する。更に、管理センタは、以下に示すような、（２ａ−１）個の素数を選択する。
【０１７４】
【数４３】
2010081656.tif 000045
【０１７５】
管理センタは、各素数
【０１７６】
【数４４】
2010081656.tif 000046
【０１７７】
を、各内部ノードｖｋ用の対応するサブセット
【０１７８】
【数４５】
2010081656.tif 000047
【０１７９】
に割り当てる（例えば、素数ｐ１００は、サブセットＳ１，１００、Ｓ２，１００、Ｓ３，１００、・・・に割り当てられる）。そして、管理センタは、素数
【０１８０】
【数４６】
2010081656.tif 000048
【０１８１】
及びその割当を公開する。更に、管理センタは、全ての素数
【０１８２】
【数４７】
2010081656.tif 000049
【０１８３】
の積として値Ｔを算出する。管理センタは、各受信機ｕｊ及び各内部ノードｖｋに対して、値ｗｊ，ｋを生成する。値ｗｊ，ｋは、内部ノードｖｋに割り当てられたサブセットであって、受信機ｕｊの葉ノードから根までのパス上の子ノードに割り当てられたサブセットキー
【０１８４】
【数４８】
2010081656.tif 000050
【０１８５】
に対応するサブセット
【０１８６】
【数４９】
2010081656.tif 000051
【０１８７】
に割り当てられた全ての素数
【０１８８】
【数５０】
2010081656.tif 000052
【０１８９】
の積である。例えば、図２７のＨＫＴ２７００において、値ｗ１，５は、受信機ｕ１及び内部ノードｖ５に対応する。値ｗ１，５は、内部ノードｖ５に割り当てられたサブセットであって、受信機ｕ１に対応する葉ノード（受信機ｕ１に対応する葉から根までのパス上の内部ノードｖ５の子ノード）に割り当てられたサブセットキー
【０１９０】
【数５１】
2010081656.tif 000053
【０１９１】
に対応するサブセット
【０１９２】
【数５２】
2010081656.tif 000054
【０１９３】
に割り当てられた素数
【０１９４】
【数５３】
2010081656.tif 000055
【０１９５】
の積である。すなわち、ｗ１，５＝ｐ１００×ｐ１１０×ｐ１０１である。
【０１９６】
管理センタは、ステップＳ２６３０において、暗号化パラメータを用いてサブセットキーを生成する。サブセットキーは、図２７に示すように、以下のように表される。
【０１９７】
【数５４】
2010081656.tif 000056
【０１９８】
管理センタは、各サブセット
【０１９９】
【数５５】
2010081656.tif 000057
【０２００】
に対するサブセットキー
【０２０１】
【数５６】
2010081656.tif 000058
【０２０２】
を、以下のようにして求める。
【０２０３】
【数５７】
2010081656.tif 000059
【０２０４】
管理センタは、各サブセットキー
【０２０５】
【数５８】
2010081656.tif 000060
【０２０６】
を、対応するサブセット
【０２０７】
【数５９】
2010081656.tif 000061
【０２０８】
に割り当てる。
【０２０９】
更に、管理センタは、ステップＳ２６３５において、各サブセットキーを内部ノードの子ノードに割り当てる。サブセットの値は、サブセットに対応する内部ノードの子ノードを示している。管理センタは、サブセットの値が１であるサブセットの内部ノードの各子ノードに、サブセットキーを割り当てる。図２７は、子ノードに対するサブセットキーの割当を示している。例えば、図１８及び図１９に示すように、サブセットＳ１，１１１は、根（ノードｖ１）に対応し、サブセットキーＳＫ１，１１１は、根の各子ノード（内部ノードｖ２、ｖ３、ｖ４）に割り当てられる。サブセットキーＳＫ１，００１は、根の右側の子ノード（内部ノードｖ４）のみに割り当てられる。このようにして、管理センタは、２ａ−１−１個のサブセットキーを各子ノードに割り当てる（及びサブセットキーＳＫ１，１１・・・１を根の各子ノードに割り当てる）。
【０２１０】
管理センタは、ステップＳ２６４０において、暗号化パラメータを用いて、複数のマスタキーを生成する。マスタキーは、図２７に示すように、ＭＫｊ，ｋと表される。管理センタは、各受信機ｕｊに対して、その受信機ｕｊの葉ノードから根までのパス上に存在する各内部ノードｖｋ毎に１つのマスタキーＭＫｊ，ｋを生成することにより、各受信機ｕｊに対して複数のマスタキーＭＫｊ，ｋを生成する。したがって、マスタキーＭＫｊ，ｋは、受信機ｕｊ及び内部ノードｖｋに対応する。管理センタは、マスタキーＭＫｊ，ｋを、以下の式に基づいて、算出する。
【０２１１】
【数６０】
2010081656.tif 000062
【０２１２】
管理センタは、複数のマスタキーＭＫｊ，ｋのそれぞれを、対応する受信機ｕｊに割り当てる。これらのマスタキーＭＫｊ，ｋに基づいて、内部ノードｖｋに割り当てられたサブセットであって、受信機の葉ノードからＨＫＴの根までのパス上のノードに対応するサブセット
【０２１３】
【数６１】
2010081656.tif 000063
【０２１４】
に対応する全てのサブセットキー
【０２１５】
【数６２】
2010081656.tif 000064
【０２１６】
を導出することができる。例えば、図２７に示すＨＫＴ２７００において、受信機ｕ１には、マスタキーＭＫ１，１、ＭＫ１，２、ＭＫ１，５が割り当てられている。受信機ｕ１は、マスタキーＭＫ１，１を用いて、サブセットキーＳＫ１，１００、ＳＫ１，１１０、ＳＫ１，１０１、ＳＫ１，１１１を導出することができ、マスタキーＭＫ１，２を用いて、サブセットキーＳＫ２，１００、ＳＫ２，１１０、ＳＫ２，１０１を導出することができ、マスタキーＭＫ５，１００を用いて、サブセットキーＳＫ５，１００、ＳＫ５，１１０、ＳＫ５，１０１を導出することができる。受信機ｕｊのいずれも無効にされていない場合、各受信機ｕｊは、マスタキーＭＫｊ，１を有し、これを用いて、サブセットキーＳＫ１，１１・・・１を導出することができる。管理センタは、ステップＳ２６４５において、対応する受信機ｕｊに複数のマスタキーＭＫｊ，ｋを送信する。更に、管理センタは、ステップＳ２６５０において、各受信機にＨＫＴに関する情報を送信する。
【０２１７】
管理センタは、図２０〜図２３を用いて説明したように、受信機を無効にし、表現コードを生成する。受信機は、図２４及び図２５を用いて説明したように、管理センタから送信されてきた暗号文を復号する。なお、ここでは、受信機ｕｊは、選択されたサブセットキー
【０２１８】
【数６３】
2010081656.tif 000065
【０２１９】
に対応するマスタキーＭＫｊ，ｋを選択し、以下の式に基づいて、選択されたサブセットキー
【０２２０】
【数６４】
2010081656.tif 000066
【０２２１】
を導出する。
【０２２２】
【数６５】
2010081656.tif 000067
【０２２３】
一具体例においては、受信機は、管理センタから、暗号化パラメータとして受信した素数
【０２２４】
【数６６】
2010081656.tif 000068
【０２２５】
を保存する。他の具体例においては、受信機は、この素数
【０２２６】
【数６７】
2010081656.tif 000069
【０２２７】
を保存せず、最も小さい２ａ−１個の素数として生成する。他の具体例においては、受信機は、素数
【０２２８】
【数６８】
2010081656.tif 000070
【０２２９】
に対してｄ番目に小さい奇素数（odd prime）を使用する。ここで、ｄは、サブセット
【０２３０】
【数６９】
2010081656.tif 000071
【０２３１】
の値によって示される２進表現の１０進数の値である。例えば、受信機は、素数ｐ１，１１１に対して７番目に小さい奇素数（odd prime）を使用する（「１１１」は、１０進数の値７の２進表現である）。この場合、各受信機は、Ａ／２個のエントリを有する１ビット値のテーブルを保存する。ここで、Ａは、２ａ−１個の素数を含むのに十分大きな値とする。ｘ番目のエントリは、０からｘ番目の奇数に対応し、エントリのビット値は、エントリに対応している奇数が素数であるか否かを表している。
【０２３２】
媒体キーブロック及びデータ媒体
一具体例においては、放送暗号化システムは、例えば図４に示す放送暗号化システム４００のように、管理センタと、Ｎ個の受信機とを備え、管理センタは、媒体キーブロック（media key block：以下、ＭＫＢという。）及びマスタキーを使用する。この具体例では、ブロックキーは、上述のサブキーであり、表現コードは、ＭＫＢであり、放送チャンネルは、データ媒体の配布（distrbution）である。図７及び図９に示す処理をこの具体例に適用する手法について以下に述べる。なお、この具体例は、後述するように、マスタキーを利用できるように変更された着脱自在の／記録可能な／再生専用媒体のためのコンテンツ保護法（Content Protection for Removable/Recordable/Prec-recorded Media：以下、ＣＰＲＭ／ＣＰＰＭという。）に基づいている（なお、ＣＰＲＭ／ＣＰＰＭは、上述したディー・ナオール（D.Naor）他著「ステートレス受信機の取消及び追跡方式（Revocation and Tracing Schemes for Stateless Receivers）」に開示されている）。
【０２３３】
図２８は、ＭＫＢを用いて、放送暗号化システムを設定し、受信機にマスタキーを割り当てる手順を示すフローチャートである（図７のステップＳ７０５及びステップＳ７１０参照）。図２９は、ブロックキーテーブル（block key table：以下、ＢＫＴ）２９００を示している。図３０は、ＭＫＢ３０００を示している。ＢＫＴ２９００及びＭＫＢ３０００については、後に説明する。
【０２３４】
管理センタは、ステップＳ２８０５において、ＢＫＴを定義する。ＢＫＴは、Ａ個の列及びＢ個の行を有する、エントリ２９０５の２次元テーブルである。各エントリ（ａ，ｂ）は、図２９のＢＫＴ２９００に示すように、Ｋａ，ｂ（ａ＝１，・・・，Ａ、ｂ＝１，・・・，Ｂ）と表されるブロックキーを格納する。ブロックキーＫａ，ｂの生成については、後述する。
【０２３５】
管理センタは、ステップＳ２８１０において、暗号化パラメータを選択する。管理センタは、暗号化パラメータを用いて、例えばキー等の暗号化のための値を生成する。暗号化パラメータの一部は、公開暗号化パラメータであり、管理センタは、ステップＳ２８１５において、公開暗号化パラメータを公開する。管理センタは、例えば、公開暗号化パラメータを受信機の製造業者に供給し、受信機の製造業者が（製造工程において）受信機にこの公開暗号化パラメータを組み込むことにより、公開暗号化パラメータを公開する。なお、管理センタは、残りの秘密暗号化パラメータを受信機に対して秘密にする。管理センタは、２つの大きな素数ｑ１、ｑ２を選択し、Ｍ＝ｑ１×ｑ２である値Ｍを算出する。管理センタは、この値Ｍを公開暗号化パラメータとして公開する。更に、管理センタは、Ｋ∈Ｚ＊Ｍとして、値Ｋを秘密暗号化パラメータとしてランダムに選択する。更に、管理センタは、ＡＢ素数ｐａ，ｂを公開暗号化パラメータとして選択する。管理センタは、各素数ｐａ，ｂをＢＫＴ内のエントリ（ａ，ｂ）に割り当てる（例えば、素数ｐ１，１はエントリ（１，１）に割り当てられる）。管理センタは、エントリに対する素数の割当を公開する。更に、管理センタは、以下に示すような値Ｔを算出する。
【０２３６】
【数７０】
2010081656.tif 000072
【０２３７】
管理センタは、値Ｔを公開しない。
【０２３８】
管理センタは、ステップＳ２８２０において、ＢＫＴ内の各エントリに対するブロックキーを生成する。ブロックキーは、図２９のＢＫＴ２９００に示すように、Ｋａ，ｂと表される。管理センタは、以下のようにしてブロックキーを算出する。
【０２３９】
【数７１】
2010081656.tif 000073
【０２４０】
管理センタは、図２９のＢＫＴ２９００に示すように、ブロックキーＫａ，ｂをＢＫＴの対応するエントリ（ａ，ｂ）に格納する。例えば、ブロックキーＫ１，１は、エントリ（１，１）に格納される。
【０２４１】
管理センタは、ステップＳ２８２５において、ＭＫＢを定義する。ＭＫＢは、ＢＫＴに基づく２次元テーブルであり、ＢＫＴの各エントリ２９０５に対応するエントリ３００３を含むＡ個の列とＢ個の行を有する。図３０は、図２９に示すＢＫＴ２９００に基づくＭＫＢ３０００を示している。初期的には、ＭＫＢは、空である。ＭＫＢの各エントリ（ａ，ｂ）は、後述するように、ＢＫＴ内の対応するエントリ（ａ，ｂ）に格納されているブロックキーＫａ，ｂを用いて、暗号化された媒体キー（media key）を格納する。×印が付されているエントリ３００３は、図３１を用いて後述するように、無効にされた受信機に対応するエントリである。
【０２４２】
管理センタは、ステップＳ２８３０において、各受信機ｕｊに対して、ベクトルを定義する。ベクトルは、Ｖｊと表され、Ｂ個の要素ｖｂを含む。すなわち、Ｖｊ＝（ｖ１，・・・，ｖｂ，・・・，ｖＢ）であり、ここで、ｖｂ∈｛１，・・・，Ａ｝である。ベクトルＶｊの各要素ｖｂは、ＭＫＢのエントリ（ａ，ｂ）を表している。ベクトルにおける要素の順序の位置は、行（すなわち、ｂ）を表し、要素の値は、列（すなわち、ａ）を表している。例えば、第１の要素ｖ１が２である場合、第１の要素ｖ１は、ＭＫＢにおける第２行第１列の媒体キー暗号文（すなわち、エントリ（２，１））を表している。このように、受信機ｕｊのベクトルＶｊは、受信機ｕｊのためのＢ個の媒体キー暗号文を表している。管理センタは、ステップＳ２８３５において、各受信機ｕｊにベクトルＶｊを供給する。
【０２４３】
更に、管理センタは、各受信機ｕｊに対して、値ｗｊを生成する。値ｗｊは、受信機ｕｊのベクトルＶｊによって示されるエントリに対応する素数ｐａ，ｂの積である。管理センタは、以下の式に基づいて、値ｗｊを算出する。
【０２４４】
【数７２】
2010081656.tif 000074
【０２４５】
ここで、ｖｂは、ベクトルＶｊのｂ番目の要素の値を表す。管理センタは、ベクトルＶｊとともに、あるいは受信機が復号を開始する前、例えば公開暗号化パラメータとともに（上述のステップＳ２８１５）又はマスタキーとともに（後述のステップＳ２８４５）、各値ｗｊを、対応する受信機ｕｊに供給する。これに代えて、受信機が、素数ｐａ，ｂから値ｗｊを導出するようにしてもよい。
【０２４６】
管理センタは、ステップＳ２８４０において、暗号化パラメータを用いて、マスタキーを生成する。マスタキーは、ＭＫｊと表される。ここで、管理センタは、以下の式に基づいて、各受信機ｕｊに対応するマスタキーＭＫｊを算出する。
【０２４７】
【数７３】
2010081656.tif 000075
【０２４８】
管理センタは、各マスタキーＭＫｊを対応する受信機ｕｊに割り当てる。管理センタは、マスタキーＭＫｊを用いて、受信機ｕｊのベクトルＶｊによって示される媒体キー暗号文に対応する全てのブロックキーＫａ，ｂを導出することができる。例えば、図２９に示すＢＫＴ２９００及び図３０に示すＭＫＢ３０００において、受信機ｕ１には、マスタキーＭＫ１が割り当てられており、ベクトルＶｊは、要素｛１，１，・・・１｝を含み、マスタキーＭＫｊを用いて、ブロックキーＫ１，１、Ｋ１，２、・・・、Ｋ１，Ｂを導出することができる。管理センタは、ステップＳ２８４５において、対応する受信機ｕｊに各マスタキーＭＫｊを送信する。
【０２４９】
管理センタは、ステップＳ２８５０において、ＢＫＴに格納されている各ブロックキーを用いて、媒体キーを暗号化する。媒体キーは、データ媒体の個体に記録されるコンテンツファイル（例えば、ＤＶＤディスクに記録されるビデオデータ）を暗号化及び復号するためのキーである。各媒体キーを暗号化することにより、それぞれの媒体キー暗号文が生成される。管理センタは、ステップＳ２８５５において、各媒体キーを暗号化するために使用されたブロックキーに対応するＭＫＢのエントリに、媒体キー暗号文を格納する。例えば、管理センタは、ブロックキーＫ１，１を用いて、媒体キーを暗号化し、これにより得られる媒体キー暗号文をＭＫＢのエントリ（１，１）に格納する。図３０のＭＫＢ３０００には、各エントリに格納された媒体キー暗号文３００５が、Ｅ（Ｋａ，ｂ，ＭＫ）として示されており、このＥ（Ｋａ，ｂ，ＭＫ）は、ブロックキーＫａ，ｂを用いた媒体キー（ＭＫ）の暗号化（Ｅ）を表している。他の具体例においては、管理センタは、ブロックキーを用いて、媒体キー以外の他のデータを暗号化する。管理センタは、ステップＳ２８６０において、データ媒体の各個体にＭＫＢを記録する。
【０２５０】
管理センタは、ステップＳ２８６５において、データ媒体を受信機に送付する。上述のように、データ媒体は、ＭＫＢを記録している。各受信機は、例えば受信機の製造業者を介して、公開暗号化パラメータと、ベクトルと、ブロックキーを導出するための値（ｗｊ）と、マスタキーとが供給される。一具体例においては、管理センタは、媒体キーを用いてコンテンツファイル（例えば、ビデオ及び／又はオーディオコンテンツ）を暗号化し、暗号化したコンテンツファイルをデータ媒体に記録する。一具体例においては、管理センタは、ステップＳ２８０５〜ステップＳ２８４５を１回（又は、受信機の数が変わる等、放送暗号化システムに変化が生じるまで）実行し、そして、暗号文の配信毎に、ステップＳ２８５０〜ステップＳ２８６５を繰り返す。
【０２５１】
図３１は、受信機を無効にし、ＭＫＢを更新する処理を示すフローチャートである（図７のステップＳ７１５〜Ｓ７３５参照）。管理センタは、ステップＳ３１０５において、１つ以上の受信機を無効にする。管理センタは、受信機が管理センタから送信されてくる暗号文を復号する権限を有さなくなった場合に、その受信機を無効又は有効ではなくする。上述のように、管理センタがいずれの受信機も無効にしない場合もある。この場合、全てのブロックキーが有効なまま残る。
【０２５２】
管理センタは、ステップＳ３１１０において、無効にされた受信機に割り当てられているマスタキーから導出することができるブロックキーを無効にする。上述のように、受信機に割り当てられ、マスタキーに対応するベクトルは、どのブロックキーがマスタキーから導出することができるかを示している。したがって、管理センタが受信機を無効にする場合、管理センタは、受信機のベクトルによって示されるブロックキーを無効にする。
【０２５３】
管理センタは、ステップＳ３１１５において、無効にされたブロックキーに対応する媒体キー暗号文を無効にすることによって、ＭＫＢを更新する。一具体例においては、管理センタは、媒体キー暗号文を所定の値に置換することにより、媒体キー暗号文を無効にする。すなわち、この所定の値は、媒体キー暗号文が暗号化された暗号化アルゴリズムを用いて媒体キーを復号することができない値である。他の具体例においては、管理センタは、ＭＫＢのエントリに格納されている媒体キー暗号文を削除し、このエントリにブランクデータ又はランダムデータを格納する。図３０のＭＫＢ３０００においては、無効な媒体キー暗号文に対応するエントリに×印を付している。
【０２５４】
管理センタは、ステップＳ３１２０において、データ媒体の新しい各個体に、更新されたＭＫＢを記録する。管理センタは、新たなデータ媒体に記録するＭＫＢを制御することによって、どの受信機が新たなデータ媒体に記録された媒体キーを復号できるかを制御する。管理センタは、ステップＳ３１２５において、受信機に新たなデータ媒体を送付する。
【０２５５】
図３２は、ＭＫＢを用いた、受信機による放送復号の処理を示すフローチャートである（図９参照）。一具体例においては、例えば図４に示す放送暗号化システム４００のように、受信機は、管理センタが配布のために準備したデータ媒体を介して、データ及び暗号文が供給される。受信機は、ステップＳ３２０５において、管理センタから暗号化パラメータが供給される。上述のように、管理センタは、例えば選択された素数ｐａ，ｂ等、受信機が管理センタからの暗号文を復号するために使用する公開暗号化パラメータを受信機に公開する。一具体例においては、受信機は、公開暗号化パラメータを非安全記憶装置（例えば、図２に示す主記憶装置２２５）に保存する。更に、受信機は、ステップＳ３２１０において、受信機ｕｊ用のベクトルＶｊとして表されるベクトルが供給され、ステップＳ３２１５において、受信機ｕｊ用のマスタキーＭＫｊとして表されるマスタキーが供給される。上述のように、管理センタは、受信機用のベクトル及びマスタキーを生成し、これらのベクトル及びマスタキーを受信機に送る。受信機は、マスタキーを用いて復号のためのブロックキーを導出する。他の具体例においては、管理センタは、受信機の製造業者を介して、暗号化パラメータの一部又は全部と、ベクトルと、マスタキーとを共に受信機に供給する。
【０２５６】
受信機は、ステップＳ３２２０において、管理センタからＭＫＢが供給される。図２８を参照して上述したように、管理センタは、ＭＫＢを定義し（図３０参照）、ＭＫＢをデータ媒体に記録して、受信機にデータ媒体を配布する。
【０２５７】
受信機は、ステップＳ３２２５において、ベクトル及びＭＫＢを用いて、復号のためのブロックキーを選択する。上述のように、ベクトルは、多数の媒体キー暗号文を表し、したがって、対応するブロックキーを表している。受信機は、ベクトルの要素によって表さるブロックキーの１つを選択する。したがって、受信機は、ベクトルのエントリ（ｖｂ，ｂ）に対応するブロックキーを導出する。ここで、要素ｖｂは、ベクトルＶｊのｂ番目の要素である。ブロックキーは、Ｋｖｂ，ｂと表される。例えば、図２９及び図３０に示す具体例では、ベクトルの第１の要素ｖ１の値は２であり、この要素は、エントリ（２，１）における媒体キー暗号文を表している。ブロックキーＫ２，１は、エントリ（２，１）に対応しており、したがって、受信機は、ブロックキーＫ２，１を選択する。
【０２５８】
受信機は、ステップＳ３２３０において、受信機のマスタキーから、選択されたブロックキーを導出する。上述のように、受信機ｕｊ用のマスタキーは、ＭＫｊと表され、受信機ｕｊは、Ｋｖｂ，ｂと表され、エントリ（ｖｂ，ｂ）に対応するブロックキーを選択する。受信機ｕｊは、素数ｐａ，ｂ及び値ｗｊを含む暗号化パラメータが既に供給されている。そして、受信機ｕｊは、以下の式に基づいて、ブロックキーＫａ，ｂを導出する。
【０２５９】
【数７４】
2010081656.tif 000076
【０２６０】
一具体例においては、受信機は、受信機のベクトルの各要素について、
【０２６１】
【数７５】
2010081656.tif 000077
【０２６２】
を予め算出しておく。また、一具体例においては、受信機は、ｃ≠ｂとして、Ｂ−１個の素数
【０２６３】
【数７６】
2010081656.tif 000078
【０２６４】
を乗算することにより、
【０２６５】
【数７７】
2010081656.tif 000079
【０２６６】
を算出する。
【０２６７】
受信機は、ステップＳ３２３５において、導出したブロックキーに対応するＭＫＢの媒体キー暗号文を復号する。一具体例においては、受信機は、例えばチェックサム値を用いて、復号結果が受信した暗号文に対して正しいものであるか否かを判定する。復号結果が正しくない場合、受信機は、受信機のベクトルの他の要素を用いて、別のブロックキーを選択する。受信機のベクトルによって表されるブロックキーのいずれによっても正しい復号結果が得られない場合、受信機は、それ自体が無効にされ、有効なノードキーを導出することができないと判定する。一具体例においては、受信機は、（例えば、ネットワーク接続を介して）管理センタと通信することにより、受信機が無効にされたことを確認する。
【０２６８】
一具体例においては、受信機に供給されるデータ媒体は、復号される媒体キーに対応する暗号化されたコンテンツファイルを含んでいる。この場合、受信機は、復号された媒体キーを用いて、暗号化されているコンテンツファイルを復号し、コンテンツにアクセスする。
【０２６９】
他の具体例においては、データ媒体は、データを記録するために使用され、受信機は、復号された媒体キーを用いて、データ媒体にデータを記録する。受信機が有効なブロックキーを有さず、したがって、ＭＫＢから媒体キーを復号できない場合、受信機は、データをデータ媒体に記録することができない。
【０２７０】
データ媒体の製造
図４〜図６を用いて上述したように、放送チャンネルがデータ媒体の配布である場合、管理センタは、データ（例えば、暗号文）をデータ媒体に記録して受信機に供給する。管理センタは、まず、データを媒体製造装置（例えば、図４に示す媒体製造業者４１０の工場に設けられている）にデータを供給し、データをデータ媒体に記録する。再生専用媒体（例えば、ＣＤ−ＲＯＭ又はＤＶＤ−ＲＯＭ）については、管理センタは、媒体製造装置に、キー暗号文及び暗号化されたコンテンツを供給する。記録可能な媒体（例えば、ＣＤ−ＲＷ又はＤＶＤ−ＲＷ）については、管理センタは、キー暗号文を供給し、受信機が暗号化されたコンテンツを、記録可能な媒体に書き込む。
【０２７１】
図３３は、媒体製造装置３３００の具体的構成例を示すブロック図である。一具体例においては、媒体製造装置３３００は、再生専用媒体を製造し、他の具体例においては、媒体製造装置３３００は、記録可能な媒体を製造する。また、媒体製造装置３３００は、データ媒体そのものを製造するのではなく、データ媒体にデータを書き込むことにより、データ媒体を準備する装置である。また、他の具体例においては、媒体製造装置３３００は、データ媒体そのものを製造する装置であってもよい。媒体製造装置３３００は、コントローラ３３０５と、入出力インタフェース３３１０と、記憶装置３３１５と、媒体インタフェース３３２０とを備える。他の具体例においては、媒体製造装置３３００は、秘密にするデータを保存する安全記憶装置を備えていてもよい。コントローラ３３０５は、媒体製造装置３３００の動作を制御する。一具体例においては、コントローラ３３０５は、ＣＰＵであってもよい。媒体製造装置３３００は、（例えば、管理センタに対し、）入出力インタフェース３３１０を介してデータを送受する。記憶装置３３１５は、媒体製造装置３３００の動作をサポートするためのデータを保存する。一具体例においては、記憶装置３３１５は、例えばＲＡＭ等のメモリ装置であってもよい。媒体インタフェース３３２０は、媒体製造装置３３００にデータ読出／書込機能を提供し、これにより、媒体製造装置３３００は、媒体の個体からデータを読み出し、また、媒体が記録可能な媒体の場合、媒体の個体にデータを書き込むことができる。
【０２７２】
図３４は、例えば図３３に示す媒体製造装置３３００等の媒体製造装置によって、再生専用媒体を製造する工程を示すフローチャートである。媒体製造装置は、ステップＳ３４０５において、データ媒体の空の個体が供給される。他の具体例においては、媒体製造装置は、既にデータの一部が記録されているデータ媒体が供給されてもよく、また、データ媒体の個体の一部又は全部を原材料から製造してもよい。媒体製造装置は、ステップＳ３４１０において、データ媒体に表現コードを記録する。上述のように、表現コードは、例えば表現木及びコード又はベクトル及び媒体キーブロック等に基づき、どの受信機が無効にされたかを示すコードである。媒体製造装置は、ステップＳ３４１５において、データ媒体に１つ以上の暗号文を記録する。暗号文は、暗号化されたコンテンツキーである。各暗号文は、同じコンテンツを含んでいるが、上述したノードキー、サブセットキー又はブロックキー等のそれぞれのサブキーを用いて暗号化されている。媒体製造装置は、ステップＳ３４２０において、コンテンツキーを用いて、コンテンツファイルを暗号化する。変形例においては、媒体製造装置は、例えば管理センタ等の外部ソースから、暗号化されたコンテンツファイルが供給される。媒体製造装置は、ステップＳ３４２５において、データ媒体に、暗号化されたコンテンツファイルを記録する。上述のように、受信機は、表現コードを用いて、サブキーを選択し、受信機に保存されているマスタキーから、選択されたサブキーを導出する。受信機は、暗号文を復号して、コンテンツキーを生成し、このコンテンツキーを用いて、暗号化されているコンテンツファイルを復号する。
【０２７３】
媒体製造装置が記録可能なデータ媒体を製造する場合、媒体製造装置は、常に、コンテンツファイルを暗号化して、データ媒体に記録する必要はない。
【０２７４】
本発明は、電子ハードウェア、コンピュータソフトウェア、又はこれらの技術の組み合わせにより、様々な形態で実現することができる。多くの実現例は、プログラミング可能なコンピュータにより実行される１つ以上のコンピュータプログラムを含んでいる。例えば、図１に示すように、一具体例においては、放送管理センタ１０５及び各受信機１２０１〜１２０Ｎは、上述した装置のそれぞれの機能を実現する１つ以上のプログラミング可能なコンピュータを備える。通常、各コンピュータは、１つ以上のプロセッサと、１つ以上のデータ記憶装置（例えば、揮発性又は不揮発性メモリモジュールと、例えばハードディスクドライブ、フロッピディスクドライブ、ＣＤ−ＲＯＭドライブ、磁気テープドライブ等の永続的な光及び磁気記録装置）と、１つ以上の入力装置（例えば、マウス及びキーボード）と、１つ以上の出力装置（例えば、ディスプレイ及びプリンタ）とを備える。
【０２７５】
コンピュータプログラムは、通常、永続的な記録媒体（persistent storage medium）に記録されており、実行時にメモリにコピーされる実行コードを含んでいる。プロセッサは、所定の順序でメモリから命令を読み出すことにより、このコードを実行する。プログラムコードを実行する際、コンピュータは、入力装置及び／又は記憶装置からデータが供給され、データを処理し、処理されたデータを出力装置及び／又は記憶装置に供給する。
【０２７６】
本発明の様々な実施の形態について説明したが、当業者は、本発明の範囲を逸脱することなく、上述した以外の実施の形態を想到することができる。例えば、上述の説明では、衛星放送の放送チャンネル又はデータ媒体配布の具体例を示しているが、放送チャンネルは、ケーブルテレビ、インターネット又はこの他の無線又は有線ネットワークであってもよい。このように、本発明は、上述の具体例によって限定されるものではない。
【０２７７】
本発明は、複数の受信機のそれぞれに対し、２つ以上のサブキーを導出するために用いることができるマスタキーを割り当て、１つ以上の受信機を無効にし、無効にされていない受信機のマスタキー毎に、このマスタキーから導出できるとともに、無効にされた全ての受信機のマスタキーからは導出できないサブキーを選択し、選択された各サブキー毎に、サブキーを用いてデータを暗号化して暗号文を生成し、暗号化された暗号文を複数の受信機に送信することで、放送暗号化システムにおいて、効率的に受信機を無効にする。
【符号の説明】
【０２７８】
１００  放送暗号化システム、１０５  放送管理センタ、１１０  衛星放送局、１１５  
放送衛星、１２０  受信機、２００  管理センタ
【図１】
2010081656.tif 000132
【図２】
2010081656.tif 000133
【図３】
2010081656.tif 000134
【図４】
2010081656.tif 000135
【図５】
2010081656.tif 000136
【図６】
2010081656.tif 000137
【図７】
2010081656.tif 000138
【図８】
2010081656.tif 000139
【図９】
2010081656.tif 000140
【図１０】
2010081656.tif 000141
【図１１】
2010081656.tif 000142
【図１２】
2010081656.tif 000143
【図１３】
2010081656.tif 000144
【図１４】
2010081656.tif 000145
【図１５】
2010081656.tif 000146
【図１６】
2010081656.tif 000147
【図１７】
2010081656.tif 000148
【図１８】
2010081656.tif 000149
【図１９】
2010081656.tif 000150
【図２０】
2010081656.tif 000151
【図２１】
2010081656.tif 000152
【図２２】
2010081656.tif 000153
【図２３】
2010081656.tif 000154
【図２４】
2010081656.tif 000155
【図２５】
2010081656.tif 000156
【図２６】
2010081656.tif 000157
【図２７】
2010081656.tif 000158
【図２８】
2010081656.tif 000159
【図２９】
2010081656.tif 000160
【図３０】
2010081656.tif 000161
【図３１】
2010081656.tif 000162
【図３２】
2010081656.tif 000163
【図３３】
2010081656.tif 000164
【図３４】
2010081656.tif 000165