(57)【要約】【課題】  ブラックボックス追跡の際に、入力の意図を不正復号器に知られることが無く、巧妙な不正復号器に対しても、確実に追跡を実行する。【解決手段】  コンテンツ提供システム１は、提供すべきコンテンツをセッション鍵で復号可能に暗号化し、暗号化コンテンツを得るコンテンツ暗号化部１４と、セッション鍵を各ユーザ側システム固有の復号鍵で復号可能に暗号化し、得られた暗号化セッション鍵を含み且つ暗号化セッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ生成部１５とを備え、暗号化コンテンツ及びヘッダ情報を各ユーザ側システムに送信する。ここで、ヘッダ情報がユーザ側システムのユーザ識別情報を含まないので、ブラックボックス追跡の際に、誰の復号鍵が無効化されているかという情報が漏れない。【選択図】  図１
2005236963.tif 000002
【特許請求の範囲】
【請求項１】
複数のユーザ側システムに割り当てられた復号鍵に対応する暗号化鍵を第三者装置から受信し、前記各ユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムであって、
提供すべきコンテンツをセッション鍵で復号可能に暗号化し、前記暗号化コンテンツを得るコンテンツ暗号化手段と、
前記セッション鍵を前記暗号化鍵で暗号化し、得られた暗号化セッション鍵を含み且つ前記暗号化セッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成手段と、
前記暗号化コンテンツ及び前記ヘッダ情報を各ユーザ側システムに送信する送信手段とを備え、
前記復号鍵は、
複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とするコンテンツ提供側システム。
【請求項２】
請求項１に記載のコンテンツ提供側システムにおいて、
前記鍵生成多項式は、複数個の多項式係数を有し、前記各多項式係数のいずれかがサブグループ毎に固有の値であることを特徴とするコンテンツ提供側システム。
【請求項３】
請求項１に記載のコンテンツ提供側システムにおいて、
前記鍵生成多項式を割り当てる手段は、
多項式の次数がｋであり、前記ユーザ識別情報がｘであるとき、第ｖ・ｋ＋ｉ（０≦ｖ、１≦ｉ≦ｋ）のサブグループに、下記鍵生成多項式ｆv・k＋i（ｘ）を割り当てることを特徴とするコンテンツ提供側システム。
ｆv・k＋i（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋…＋ａi-1・ｘi-1＋ｂv,i・ｘi＋ａi＋1・ｘi＋1＋…＋ａk-2・ｘk-2＋ａk-1・ｘk-1＋ａk・ｘk
但し、ａ0〜ａi-1，ａi＋1〜ａkは多項式係数、ｂv,iは第ｖ・ｋ＋ｉのサブグループ固有の多項式係数。
【請求項４】
請求項１に記載のコンテンツ提供側システムにおいて、
前記鍵生成多項式を割り当てる手段は、
多項式の次数がｋであり、前記ユーザ識別情報がｘであるとき、第ｖ・（ｋ＋１）＋ｉ＋１（０≦ｖ、０≦ｉ≦ｋ）のサブグループに、下記鍵生成多項式ｆv・(k＋1)+i+1（ｘ）を割り当てることを特徴とするコンテンツ提供側システム。
ｆv・(k＋1)+i+1（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋…＋ａi-1・ｘi-1＋ｂv,i・ｘi＋ａi＋1・ｘi＋1＋…＋ａk-2・ｘk-2＋ａk-1・ｘk-1＋ａk・ｘk 
但し、ａ0〜ａi-1，ａi＋1〜ａkは多項式係数、ｂv,iは第ｖ・（ｋ＋１）＋ｉ＋１のサブグループ固有の多項式係数。
【請求項５】
請求項３又は請求項４に記載のコンテンツ提供側システムにおいて、
前記ｋに代えて、２ｋ−１を用いることを特徴とするコンテンツ提供側システム。
【請求項６】
請求項１乃至請求項５のいずれか１項に記載のコンテンツ提供側システムにおいて、
前記ヘッダ情報は前記サブグループ毎に固有の値を含み、
前記ヘッダ情報生成手段は、特定のサブグループに属する全てのユーザ側システムの復号鍵を無効にするとき、前記ヘッダ情報における特定のサブグループに固有の値を正しい値とは異なる値に設定することを特徴とするコンテンツ提供側システム。
【請求項７】
請求項６に記載のコンテンツ提供側システムにおいて、
前記固有の値を正しい値とは異なる値に設定することに代えて、
前記固有の値を削除することを特徴とするコンテンツ提供側システム。
【請求項８】
請求項１乃至請求項５のいずれか１項に記載のコンテンツ提供側システムにおいて、
前記ヘッダ情報は、前記サブグループ毎に固有の値と、当該サブグループに属する複数のユーザ識別情報の部分集合に基づく値とを含み、
前記ヘッダ情報生成手段は、特定のサブグループに属する全てのユーザ側システムのうち、１以上のユーザ側システムの復号鍵を無効にするとき、当該無効にするユーザ側システムのユーザ識別情報を前記部分集合に含めないことを特徴とするコンテンツ提供側システム。
【請求項９】
請求項８に記載のコンテンツ提供側システムにおいて、
前記ヘッダ情報生成手段は、前記特定のサブグループとは異なる他の特定のサブグループに属する全てのユーザ側システムの復号鍵を無効にするとき、前記ヘッダ情報における当該他の特定のサブグループに固有の値を正しい値とは異なる値に設定することを特徴とするコンテンツ提供側システム。
【請求項１０】
請求項９に記載のコンテンツ提供側システムにおいて、
前記固有の値を正しい値とは異なる値に設定することに代えて、
前記固有の値を削除することを特徴とするコンテンツ提供側システム。
【請求項１１】
請求項１乃至請求項１０のいずれか１項に記載のコンテンツ提供側システムにおいて、
前記送信手段は、前記サブグループ毎のヘッダ情報における各要素のうち、同一の要素を共有化して送信することを特徴とするコンテンツ提供側システム。
【請求項１２】
複数のユーザ側システムに割り当てられた復号鍵に対応する暗号化鍵を第三者装置から受信し、前記各ユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムであって、
提供すべきコンテンツをセッション鍵で復号可能に暗号化し、前記暗号化コンテンツを得るコンテンツ暗号化手段と、
前記セッション鍵を前記暗号化鍵で暗号化し、得られた暗号化セッション鍵を含み且つ前記暗号化セッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成手段と、
前記暗号化コンテンツ及び前記ヘッダ情報を各ユーザ側システムに送信する送信手段とを備え、
前記復号鍵は、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、複数のユーザ識別情報が属するサブグループが各リーフに割り当てられ、前記ルートと，前記ノードと，前記リーフとの一部又は全てに対し、互いに異なる鍵生成多項式が割り当てられ、１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式が割り当てられたとき、
前記１個以上のサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とするコンテンツ提供側システム。
【請求項１３】
請求項１２に記載のコンテンツ提供側システムにおいて、
前記鍵生成多項式は、複数個の多項式係数を有し、前記各多項式係数のいずれかが前記ルート，前記ノード，又は前記リーフ毎に固有の値であり、システム立ち上げ時に生成される秘密定数が少なくとも１つの多項式係数に乗じられている又は除されていることを特徴とするコンテンツ提供側システム。
【請求項１４】
コンテンツ提供側システムから提供された暗号化コンテンツを復号するユーザ側システムであって、
前記コンテンツ提供側システムから、セッション鍵で復号可能な暗号化コンテンツと、ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ前記暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報とを受信する手段と、
前記復号鍵に基づいて、前記ヘッダ情報からセッション鍵を復号するセッション鍵復号手段と、
前記復号されたセッション鍵に基づいて、前記暗号化コンテンツを復号するコンテンツ復号手段とを備え、
前記セッション鍵復号手段は、
複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ識別情報を代入することによって得られた値を前記復号鍵とすることを特徴とするユーザ側システム。
【請求項１５】
請求項１４に記載のユーザ側システムにおいて、
前記鍵生成多項式は、複数個の多項式係数を有し、前記各多項式係数のいずれかがサブグループ毎に固有の値であることを特徴とするユーザ側システム。
【請求項１６】
請求項１４に記載のユーザ側システムにおいて、
前記セッション鍵復号手段は、
多項式の次数がｋであり、前記ユーザ識別情報がｘであり、第ｖ・ｋ＋ｉ（０≦ｖ、１≦ｉ≦ｋ）のサブグループに属するとき、当該サブグループに割り当てられた下記鍵生成多項式ｆv・k＋i（ｘ）に前記ユーザ識別情報を代入することによって得られた値を前記復号鍵とすることを特徴とするユーザ側システム。
ｆv・k＋i（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋…＋ａi-1・ｘi-1＋ｂv,i・ｘi＋ａi＋1・ｘi＋1＋…＋ａk-2・ｘk-2＋ａk-1・ｘk-1＋ａk・ｘk
但し、ａ0〜ａi-1，ａi＋1〜ａkは多項式係数、ｂv,iは第ｖ・ｋ＋ｉのサブグループ固有の多項式係数。
【請求項１７】
請求項１４に記載のユーザ側システムにおいて、
前記セッション鍵復号手段は、
多項式の次数がｋであり、前記ユーザ識別情報がｘであり、第ｖ・（ｋ＋１）＋ｉ＋１（０≦ｖ、０≦ｉ≦ｋ）のサブグループに属するとき、当該サブグループに割当てられた下記鍵生成多項式ｆv・(k+1)+i+1（ｘ）に前記ユーザ識別情報を代入することによって得られた値を前記復号鍵とすることを特徴とするユーザ側システム。
ｆv・(k+1)+i+1（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋…＋ａi-1・ｘi-1＋ｂv,i・ｘi＋ａi＋1・ｘi＋1＋…＋ａk-2・ｘk-2＋ａk-1・ｘk-1＋ａk・ｘk 
但し、ａ0〜ａi-1，ａi＋1〜ａkは多項式係数、ｂv,iは第ｖ・（ｋ＋１）＋ｉ＋１のサブグループ固有の多項式係数。
【請求項１８】
請求項１６又は請求項１７に記載のユーザ側システムにおいて、
前記ｋに代えて、２ｋ−１を用いることを特徴とするユーザ側システム。
【請求項１９】
請求項１４乃至請求項１８のいずれか１項に記載のユーザ側システムにおいて、
前記ヘッダ情報は、前記サブグループ毎に固有の値を含み、
前記固有の値は、特定のサブグループに属する全てのユーザ側システムの復号鍵を無効にするとき、正しい値とは異なる値に設定されており、
前記セッション鍵復号手段は、前記ヘッダ情報に含まれるサブグループ毎に固有の値のうち、対応するユーザ識別情報が属するサブグループに固有の値を用いて前記セッション鍵を復号することを特徴とするユーザ側システム。
【請求項２０】
請求項１９に記載のユーザ側システムにおいて、
前記固有の値は、正しい値とは異なる値に設定されることに代えて、削除されることを特徴とするユーザ側システム。
【請求項２１】
請求項１４乃至請求項１８のいずれか１項に記載のユーザ側システムにおいて、
前記ヘッダ情報は、前記サブグループ毎に固有の値と、当該サブグループに属する複数のユーザ識別情報の部分集合に基づく値とを含み、
前記部分集合は、特定のサブグループに属する全てのユーザ側システムのうち、１以上のユーザ側システムの復号鍵を無効にするとき、当該無効にするユーザ側システムのユーザ識別情報を含まないように設定されており、
前記セッション鍵復号手段は、前記ヘッダ情報に含まれるサブグループ毎に固有の値のうち、対応するユーザ識別情報が属するサブグループに固有の値と、当該サブグループに属する複数のユーザ識別情報の部分集合に基づく値とを用いて前記セッション鍵を復号することを特徴とするユーザ側システム。
【請求項２２】
請求項２１に記載のユーザ側システムにおいて、
前記ヘッダ情報は、前記特定のサブグループとは異なる他の特定のサブグループに属する全てのユーザ側システムの復号鍵を無効にするとき、当該他の特定のサブグループに固有の値が正しい値とは異なる値に設定されることを特徴とするユーザ側システム。
【請求項２３】
請求項２２に記載のユーザ側システムにおいて、
前記固有の値が正しい値とは異なる値に設定されることに代えて、
前記固有の値が削除されることを特徴とするユーザ側システム。
【請求項２４】
コンテンツ提供側システムから提供された暗号化コンテンツを復号するユーザ側システムであって、
前記コンテンツ提供側システムから、セッション鍵で復号可能な暗号化コンテンツと、ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ前記暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報とを受信する手段と、
前記復号鍵に基づいて、前記ヘッダ情報からセッション鍵を復号するセッション鍵復号手段と、
前記復号されたセッション鍵に基づいて、前記暗号化コンテンツを復号するコンテンツ復号手段とを備え、
前記セッション鍵復号手段は、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、複数のユーザ識別情報が属するサブグループが各リーフに割り当てられ、前記ルートと，前記ノードと，前記リーフとの一部又は全てに対し、互いに異なる鍵生成多項式が割り当てられ、１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式が割り当てられたとき、
１個以上のサブグループ毎に割り当てられた鍵生成多項式に、ユーザ識別情報を代入することによって得られた値を前記復号鍵とすることを特徴とするユーザ側システム。
【請求項２５】
請求項２４に記載のユーザ側システムにおいて、
前記鍵生成多項式は、複数個の多項式係数を有し、前記各多項式係数のいずれかが前記ルート，前記ノード，又は前記リーフ毎に固有の値であり、システム立ち上げ時に生成される秘密定数が少なくとも１つの多項式係数に乗じられている又は除されていることを特徴とするユーザ側システム。
【請求項２６】
検査対象のユーザ側システムを検査し、不正ユーザを特定して追跡するための追跡システムであって、
ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ当該暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成手段と、
コンテンツをセッション鍵で復号可能に暗号化し、暗号化コンテンツを得るコンテンツ暗号化手段と、
前記ヘッダ情報及び前記暗号化コンテンツを前記検査対象のユーザ側システムに入力し、このユーザ側システムによる暗号化コンテンツの復号結果を取得する手段と、
前記ヘッダ情報生成手段の制御により、復号不能なユーザ側システムの数を変えて生成されたヘッダ情報と、当該ヘッダ情報を入力したときに取得した復号結果との関係に基づいて、前記検査対象のユーザ側システムの作出のもととなった１以上のユーザ側システムの不正ユーザを特定する特定手段とを備え、
前記復号鍵は、
複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とする追跡システム。
【請求項２７】
請求項２６に記載の追跡システムにおいて、
前記鍵生成多項式は、複数個の多項式係数を有し、前記各多項式係数のいずれかがサブグループ毎に固有の値であることを特徴とする追跡システム。
【請求項２８】
請求項２６に記載の追跡システムにおいて、
前記復号鍵は、
多項式の次数がｋであり、前記ユーザ識別情報がｘであり、第ｖ・ｋ＋ｉ（０≦ｖ、１≦ｉ≦ｋ）のサブグループに属するとき、当該サブグループに割り当てられた下記鍵生成多項式ｆv・k＋i（ｘ）に代入されて得られた値であることを特徴とする追跡システム。
ｆv・k＋i（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋…＋ａi-1・ｘi-1＋ｂv,i・ｘi＋ａi＋1・ｘi＋1＋…＋ａk-2・ｘk-2＋ａk-1・ｘk-1＋ａk・ｘk
但し、ａ0〜ａi-1，ａi＋1〜ａkは多項式係数、ｂv,iは第ｖ・ｋ＋ｉのサブグループ固有の多項式係数。
【請求項２９】
請求項２６に記載の追跡システムにおいて、
前記復号鍵は、
多項式の次数がｋであり、前記ユーザ識別情報がｘであり、第ｖ・（ｋ＋１）＋ｉ＋１（０≦ｖ、０≦ｉ≦ｋ）のサブグループに属するとき、当該サブグループに割り当てられた下記鍵生成多項式ｆv・(k+1)+i+1（ｘ）に代入されて得られた値であることを特徴とする追跡システム。
ｆv・(k+1)+i+1（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋…＋ａi-1・ｘi-1＋ｂv,i・ｘi＋ａi＋1・ｘi＋1＋…＋ａk-2・ｘk-2＋ａk-1・ｘk-1＋ａk・ｘk 
但し、ａ0〜ａi-1，ａi＋1〜ａkは多項式係数、ｂv,iは第ｖ・（ｋ＋１）＋ｉ＋１のサブグループ固有の多項式係数。
【請求項３０】
請求項２８又は請求項２９に記載の追跡システムにおいて、
前記ｋに代えて、２ｋ−１を用いることを特徴とする追跡システム。
【請求項３１】
請求項２６乃至請求項３０のいずれか１項に記載の追跡システムにおいて、
前記特定手段は、
前記復号不能なユーザ側システムの数がｊ−１のときに復号可能と判定され、当該ｊ−１のユーザ側システムとは異なる他の１つのユーザ側システムをさらに前記復号不能なユーザ側システムに加え，前記復号不能なユーザ側システムの数がｊのときに復号不能と判定されたとき、当該他のユーザ側システムのユーザを不正ユーザであると特定することを特徴とする追跡システム。
【請求項３２】
検査対象のユーザ側システムを検査し、不正ユーザを特定して追跡するための追跡システムであって、
ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ当該暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成手段と、
コンテンツをセッション鍵で復号可能に暗号化し、暗号化コンテンツを得るコンテンツ暗号化手段と、
前記ヘッダ情報及び前記暗号化コンテンツを前記検査対象のユーザ側システムに入力し、このユーザ側システムによる暗号化コンテンツの復号結果を取得する手段と、
前記ヘッダ情報生成手段の制御により、復号不能なユーザ側システムの数を変えて生成されたヘッダ情報と、当該ヘッダ情報を入力したときに取得した復号結果との関係に基づいて、前記検査対象のユーザ側システムの作出のもととなった１以上のユーザ側システムの不正ユーザを特定する特定手段とを備え、
前記復号鍵は、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、複数のユーザ識別情報が属するサブグループが各リーフに割り当てられ、前記ルートと，前記ノードと，前記リーフとの一部又は全てに対し、互いに異なる鍵生成多項式が割り当てられ、１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式が割り当てられたとき、
前記１個以上のサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とする追跡システム。
【請求項３３】
請求項３２に記載の追跡システムにおいて、
前記鍵生成多項式は、複数個の多項式係数を有し、前記各多項式係数のいずれかが前記ルート，前記ノード，又は前記リーフ毎に固有の値であり、システム立ち上げ時に生成される秘密定数が少なくとも１つの多項式係数に乗じられている又は除されていることを特徴とする追跡システム。
【請求項３４】
複数のユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムに用いられるコンテンツ提供方法であって、
提供すべきコンテンツをセッション鍵で復号可能に暗号化し、前記暗号化コンテンツを得るコンテンツ暗号化工程と、
前記各ユーザ側システムに割り当てられた復号鍵に対応する暗号化鍵を第三者装置から受信する工程と、
前記セッション鍵を前記暗号化鍵で暗号化し、得られた暗号化セッション鍵を含み且つ前記暗号化セッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成工程と、
前記暗号化コンテンツ及び前記ヘッダ情報を各ユーザ側システムに送信する送信工程とを備え、
前記復号鍵は、
複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とするコンテンツ提供方法。
【請求項３５】
複数のユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムに用いられるコンテンツ提供方法であって、
提供すべきコンテンツをセッション鍵で復号可能に暗号化し、前記暗号化コンテンツを得るコンテンツ暗号化工程と、
前記各ユーザ側システムに割り当てられた復号鍵に対応する暗号化鍵を第三者装置から受信する工程と、
前記セッション鍵を前記暗号化鍵で暗号化し、得られた暗号化セッション鍵を含み且つ前記暗号化セッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成工程と、
前記暗号化コンテンツ及び前記ヘッダ情報を各ユーザ側システムに送信する送信工程とを備え、
前記復号鍵は、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、複数のユーザ識別情報が属するサブグループが各リーフに割り当てられ、前記ルートと，前記ノードと，前記リーフとの一部又は全てに対し、互いに異なる鍵生成多項式が割り当てられ、１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式が割り当てられたとき、
前記１個以上のサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とするコンテンツ提供方法。
【請求項３６】
コンテンツ提供側システムから提供された暗号化コンテンツを復号するユーザ側システムに用いられる暗号化コンテンツ復号方法であって、
前記コンテンツ提供側システムから、セッション鍵で復号可能な暗号化コンテンツと、ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ前記暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報とを受信する工程と、
前記復号鍵に基づいて、前記ヘッダ情報からセッション鍵を復号するセッション鍵復号工程と、
前記復号されたセッション鍵に基づいて、前記暗号化コンテンツを復号するコンテンツ復号工程とを備え、
前記セッション鍵復号工程は、
複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ識別情報を代入することによって得られた値を前記復号鍵とする
ことを特徴とする暗号化コンテンツ復号方法。
【請求項３７】
コンテンツ提供側システムから提供された暗号化コンテンツを復号するユーザ側システムに用いられる暗号化コンテンツ復号方法であって、
前記コンテンツ提供側システムから、セッション鍵で復号可能な暗号化コンテンツと、ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ前記暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報とを受信する工程と、
前記復号鍵に基づいて、前記ヘッダ情報からセッション鍵を復号するセッション鍵復号工程と、
前記復号されたセッション鍵に基づいて、前記暗号化コンテンツを復号するコンテンツ復号工程とを備え、
前記セッション鍵復号工程は、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、複数のユーザ識別情報が属するサブグループが各リーフに割り当てられ、前記ルートと，前記ノードと，前記リーフとの一部又は全てに対し、互いに異なる鍵生成多項式が割り当てられ、１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式が割り当てられたとき、
１個以上のサブグループ毎に割り当てられた鍵生成多項式に、ユーザ識別情報を代入することによって得られた値を前記復号鍵とする
ことを特徴とする暗号化コンテンツ復号方法。
【請求項３８】
検査対象のユーザ側システムを検査し、不正ユーザを特定して追跡するための追跡システムに用いられる不正ユーザ特定方法であって、
ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ当該暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成工程と、
コンテンツをセッション鍵で復号可能に暗号化し、暗号化コンテンツを得るコンテンツ暗号化工程と、
前記ヘッダ情報及び前記暗号化コンテンツを前記検査対象のユーザ側システムに入力し、このユーザ側システムによる暗号化コンテンツの復号結果を取得する工程と、
前記ヘッダ情報生成工程の制御により、復号不能なユーザ側システムの数を変えて生成されたヘッダ情報及び暗号化コンテンツと、当該ヘッダ情報及び当該暗号化コンテンツを入力したときに取得した復号結果との関係に基づいて、前記検査対象のユーザ側システムの作出のもととなった１以上のユーザ側システムの不正ユーザを特定する特定工程とを備え、
前記復号鍵は、
複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とする不正ユーザ特定方法。
【請求項３９】
検査対象のユーザ側システムを検査し、不正ユーザを特定して追跡するための追跡システムに用いられる不正ユーザ特定方法であって、
ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ当該暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成工程と、
コンテンツをセッション鍵で復号可能に暗号化し、暗号化コンテンツを得るコンテンツ暗号化工程と、
前記ヘッダ情報及び前記暗号化コンテンツを前記検査対象のユーザ側システムに入力し、このユーザ側システムによる暗号化コンテンツの復号結果を取得する工程と、
前記ヘッダ情報生成工程の制御により、復号不能なユーザ側システムの数を変えて生成されたヘッダ情報及び暗号化コンテンツと、当該ヘッダ情報及び当該暗号化コンテンツを入力したときに取得した復号結果との関係に基づいて、前記検査対象のユーザ側システムの作出のもととなった１以上のユーザ側システムの不正ユーザを特定する特定工程とを備え、
前記復号鍵は、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、複数のユーザ識別情報が属するサブグループが各リーフに割り当てられ、前記ルートと，前記ノードと，前記リーフとの一部又は全てに対し、互いに異なる鍵生成多項式が割り当てられ、１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式が割り当てられたとき、
１個以上のサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とする不正ユーザ特定方法。
【請求項４０】
複数のユーザ側システムに割り当てられた復号鍵に対応する暗号化鍵を第三者装置から受信し、前記各ユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムのコンピュータに用いられるプログラムであって、
前記コンピュータを、
提供すべきコンテンツをセッション鍵で復号可能に暗号化し、前記暗号化コンテンツを得るコンテンツ暗号化手段、
前記セッション鍵を前記復号鍵で復号可能に暗号化し、得られた暗号化セッション鍵を含み且つ前記暗号化セッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成手段、
前記暗号化コンテンツ及び前記ヘッダ情報を各ユーザ側システムに送信する送信手段、として機能させ、
前記復号鍵は、
複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とするプログラム。
【請求項４１】
複数のユーザ側システムに割り当てられた復号鍵に対応する暗号化鍵を第三者装置から受信し、前記各ユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムのコンピュータに用いられるプログラムであって、
前記コンピュータを、
提供すべきコンテンツをセッション鍵で復号可能に暗号化し、前記暗号化コンテンツを得るコンテンツ暗号化手段、
前記セッション鍵を前記暗号化鍵で暗号化し、得られた暗号化セッション鍵を含み且つ前記暗号化セッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成手段、
前記暗号化コンテンツ及び前記ヘッダ情報を各ユーザ側システムに送信する送信手段、として機能させ、
前記復号鍵は、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、複数のユーザ識別情報が属するサブグループが各リーフに割り当てられ、前記ルートと，前記ノードと，前記リーフとの一部又は全てに対し、互いに異なる鍵生成多項式が割り当てられ、１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式が割り当てられたとき、
前記１個以上のサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とするプログラム。
【請求項４２】
コンテンツ提供側システムから提供された暗号化コンテンツを復号するユーザ側システムのコンピュータに用いられるプログラムであって、
前記コンピュータを、
前記コンテンツ提供側システムから、セッション鍵で復号可能な暗号化コンテンツと、ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ前記暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報とを受信する手段、
前記復号鍵に基づいて、前記ヘッダ情報からセッション鍵を復号するセッション鍵復号手段、
前記復号されたセッション鍵に基づいて、前記暗号化コンテンツを復号するコンテンツ復号手段、として機能させ、
前記セッション鍵復号手段は、
複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ識別情報を代入することによって得られた値を前記復号鍵とする
ことを特徴とするプログラム。
【請求項４３】
コンテンツ提供側システムから提供された暗号化コンテンツを復号するユーザ側システムのコンピュータに用いられるプログラムであって、
前記コンピュータを、
前記コンテンツ提供側システムから、セッション鍵で復号可能な暗号化コンテンツと、ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ前記暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報とを受信する手段、
前記復号鍵に基づいて、前記ヘッダ情報からセッション鍵を復号するセッション鍵復号手段、
前記復号されたセッション鍵に基づいて、前記暗号化コンテンツを復号するコンテンツ復号手段、として機能させ、
前記セッション鍵復号手段は、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、複数のユーザ識別情報が属するサブグループが各リーフに割り当てられ、前記ルートと，前記ノードと，前記リーフとの一部又は全てに対し、互いに異なる鍵生成多項式が割り当てられ、１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式が割り当てられたとき、
１個以上のサブグループ毎に割り当てられた鍵生成多項式に、ユーザ識別情報を代入することによって得られた値を前記復号鍵とする
ことを特徴とするプログラム。
【請求項４４】
検査対象のユーザ側システムを検査し、不正ユーザを特定して追跡するための追跡システムのコンピュータに用いられるプログラムであって、
前記コンピュータを、
ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ当該暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成手段、
コンテンツをセッション鍵で復号可能に暗号化し、暗号化コンテンツを得るコンテンツ暗号化手段、
前記ヘッダ情報及び前記暗号化コンテンツを前記検査対象のユーザ側システムに入力し、このユーザ側システムによる暗号化コンテンツの復号結果を取得する手段、
前記ヘッダ情報生成手段の制御により、復号不能なユーザ側システムの数を変えて生成されたヘッダ情報及び暗号化コンテンツと、当該ヘッダ情報及び当該暗号化コンテンツを入力したときに取得した復号結果との関係に基づいて、前記検査対象のユーザ側システムの作出のもととなった１以上のユーザ側システムの不正ユーザを特定する特定手段、として機能させ、
前記復号鍵は、
複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とするプログラム。
【請求項４５】
検査対象のユーザ側システムを検査し、不正ユーザを特定して追跡するための追跡システムのコンピュータに用いられるプログラムであって、
前記コンピュータを、
ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ当該暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成手段、
コンテンツをセッション鍵で復号可能に暗号化し、暗号化コンテンツを得るコンテンツ暗号化手段、
前記ヘッダ情報及び前記暗号化コンテンツを前記検査対象のユーザ側システムに入力し、このユーザ側システムによる暗号化コンテンツの復号結果を取得する手段、
前記ヘッダ情報生成手段の制御により、復号不能なユーザ側システムの数を変えて生成されたヘッダ情報及び暗号化コンテンツと、当該ヘッダ情報及び当該暗号化コンテンツを入力したときに取得した復号結果との関係に基づいて、前記検査対象のユーザ側システムの作出のもととなった１以上のユーザ側システムの不正ユーザを特定する特定手段、として機能させ、
前記復号鍵は、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、複数のユーザ識別情報が属するサブグループが各リーフに割り当てられ、前記ルートと，前記ノードと，前記リーフとの一部又は全てに対し、互いに異なる鍵生成多項式が割り当てられ、１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式が割り当てられたとき、
１個以上のサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とするプログラム。
【請求項４６】
複数のユーザ側システムに割り当てられた復号鍵に対応する暗号化鍵を第三者装置から受信し、前記各ユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムに用いられる暗号化装置であって、
提供すべきコンテンツをセッション鍵で復号可能に暗号化し、前記暗号化コンテンツを得るコンテンツ暗号化手段と、
前記セッション鍵を前記暗号化鍵で復号可能に暗号化し、得られた暗号化セッション鍵を含み且つ前記暗号化セッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成手段とを備え、
前記復号鍵は、
複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とする暗号化装置。
【請求項４７】
複数のユーザ側システムに割り当てられた復号鍵に対応する暗号化鍵を第三者装置から受信し、前記各ユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムに用いられる暗号化装置であって、
提供すべきコンテンツをセッション鍵で復号可能に暗号化し、前記暗号化コンテンツを得るコンテンツ暗号化手段と、
前記セッション鍵を前記暗号化鍵で暗号化し、得られた暗号化セッション鍵を含み且つ前記暗号化セッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成手段とを備え、
前記復号鍵は、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、複数のユーザ識別情報が属するサブグループが各リーフに割り当てられ、前記ルートと，前記ノードと，前記リーフとの一部又は全てに対し、互いに異なる鍵生成多項式が割り当てられ、１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式が割り当てられたとき、
前記１個以上のサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であることを特徴とする暗号化装置。
【請求項４８】
コンテンツ提供側システムから提供された暗号化コンテンツを復号するユーザ側システムに用いられる復号装置であって、
前記コンテンツ提供側システムから、セッション鍵で復号可能な暗号化コンテンツと、ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ前記暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報とが受信されたとき、前記復号鍵に基づいて、前記ヘッダ情報からセッション鍵を復号するセッション鍵復号手段と、
前記復号されたセッション鍵に基づいて、前記暗号化コンテンツを復号するコンテンツ復号手段とを備え、
前記セッション鍵復号手段は、
複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ識別情報を代入することによって得られた値を前記復号鍵とする
ことを特徴とする復号装置。
【請求項４９】
コンテンツ提供側システムから提供された暗号化コンテンツを復号するユーザ側システムに用いられる復号装置であって、
前記コンテンツ提供側システムから、セッション鍵で復号可能な暗号化コンテンツと、ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ前記暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報とが受信されたとき、前記復号鍵に基づいて、前記ヘッダ情報からセッション鍵を復号するセッション鍵復号手段と、
前記復号されたセッション鍵に基づいて、前記暗号化コンテンツを復号するコンテンツ復号手段とを備え、
前記セッション鍵復号手段は、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、複数のユーザ識別情報が属するサブグループが各リーフに割り当てられ、前記ルートと，前記ノードと，前記リーフとの一部又は全てに対し、互いに異なる鍵生成多項式が割り当てられ、１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式が割り当てられたとき、
１個以上のサブグループ毎に割り当てられた鍵生成多項式に、ユーザ識別情報を代入することによって得られた値を前記復号鍵とする
ことを特徴とする復号装置。
【請求項５０】
複数のユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムに対し、前記各ユーザ側システムに割り当てられた復号鍵に対応する暗号化鍵を送信する第三者装置に用いられる鍵生成方法であって、
複数個の多項式係数に基づいて、前記各ユーザ側システム共通の暗号化鍵を生成する暗号化鍵生成工程と、
前記各多項式係数に基づいて、前記各ユーザ側システム固有の復号鍵を生成する復号鍵生成工程とを備え、
前記復号鍵生成工程は、
複数のユーザ側システムを個別に識別するための複数のユーザ識別情報が属するグループを、複数のサブグループに分割する工程と、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、前記サブグループ毎に前記各リーフを割り当てる工程と、
前記木構造におけるルートと，前記ノードと，前記リーフとの一部又は全てに対し、前記各多項式係数を有して互いに異なる鍵生成多項式を割り当てる工程と、
１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式を割り当てる工程と、
前記ユーザ側システム毎のユーザ識別情報を、このユーザ識別情報が属するサブグループに割り当てられた鍵生成多項式に代入し、得られた値を当該ユーザ側システム固有の復号鍵とする工程と、
を備えたことを特徴とする鍵生成方法。
【請求項５１】
複数のユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムに用いられる鍵生成方法であって、
複数個の多項式係数に基づいて、前記各ユーザ側システム共通の暗号化鍵を生成する暗号化鍵生成工程と、
前記各多項式係数に基づいて、前記各ユーザ側システム固有の復号鍵を生成する復号鍵生成工程とを備え、
前記復号鍵生成工程は、
複数のユーザ側システムを個別に識別するための複数のユーザ識別情報が属するグループを、複数のサブグループに分割する工程と、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、前記サブグループ毎に前記各リーフを割り当てる工程と、
前記木構造におけるルートと，前記ノードと，前記リーフとの一部又は全てに対し、前記各多項式係数を有して互いに異なる鍵生成多項式を割り当てる工程と、
１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式を割り当てる工程と、
前記ユーザ側システム毎のユーザ識別情報を、このユーザ識別情報が属するサブグループに割り当てられた鍵生成多項式に代入し、得られた値を当該ユーザ側システム固有の復号鍵とする工程と、
を備えたことを特徴とする鍵生成方法。
【請求項５２】
複数のユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムに用いられる鍵生成装置であって、
複数個の多項式係数に基づいて、前記各ユーザ側システム共通の暗号化鍵を生成する暗号化鍵生成手段と、
前記各多項式係数に基づいて、前記各ユーザ側システム固有の復号鍵を生成する復号鍵生成手段とを備え、
前記復号鍵生成手段は、
複数のユーザ側システムを個別に識別するための複数のユーザ識別情報が属するグループを、複数のサブグループに分割する分割手段と、
ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、前記サブグループ毎に前記各リーフを割り当てる第１の割り当て手段と、
前記木構造におけるルートと，前記ノードと，前記リーフとの一部又は全てに対し、前記各多項式係数を有して互いに異なる鍵生成多項式を割り当てる第２の割り当て手段と、
１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式を割り当てる第３の割り当て手段と、
前記ユーザ側システム毎のユーザ識別情報を、このユーザ識別情報が属するサブグループに割り当てられた鍵生成多項式に代入し、得られた値を当該ユーザ側システム固有の復号鍵とする手段と、
を備えたことを特徴とする鍵生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツ提供側システム、ユーザ側システム、追跡システム、装置、方法及びプログラムに関する。
【背景技術】
【０００２】
従来、放送型コンテンツ配信事業では、放送番組のコンテンツを暗号化し、得られた暗号化コンテンツをユーザに配信する。ユーザは、例えば配信者から貸与された正当な復号器により暗号化コンテンツを復号し、得られたコンテンツにより放送番組を視聴している。しかしながら、放送型コンテンツ配信事業に対しては、自己の正当な復号器の内部情報（復号鍵等）をコピーした海賊版復号器を作成し、暗号化コンテンツを不正に復号可能とする不正ユーザが存在している。
【０００３】
一方、このような不正ユーザを特定し得る各種の不正ユーザ特定方法が知られている。係る不正ユーザ特定方法は、ユーザの復号鍵生成方法により二つのタイプに分類される。第１のタイプは、組み合わせ論的な構成に基づく方法であり、第２のタイプは、代数的な構成に基づく方法である。
【０００４】
第１の不正ユーザ特定方法では、海賊版復号器の作成に関与しない正当なユーザを不正ユーザと誤って検出する確率を十分小さくするために送信オーバヘッドを非常に大きくしなければならない問題がある。
【０００５】
第２の不正ユーザ特定方法では、この問題を解決し、効率的な送信オーバヘッドを達成している。また、第２の不正ユーザ特定方法に関しては、鍵配送方法に秘密分散法を応用し、特定のユーザの復号鍵を無効化する機能が提案されている（例えば、非特許文献１参照）。
【０００６】
しかしながら、海賊版復号器は、複数の不正ユーザの結託により、複数の復号鍵または復号鍵と等価な機能をもつデータが格納されることがある。この海賊版復号器に対して、海賊版復号器をこじ開けずにその入出力のみを観測し、不正ユーザを特定するブラックボックス追跡が行なわれる場合がある。
【０００７】
この場合、第２の不正ユーザ特定方法では、ブラックボックス追跡に要する処理ステップ数が指数関数的であり、ブラックボックス追跡が実用上不可能となる問題がある。具体的には、ブラックボックス追跡を行う追跡者は、不正ユーザの候補（以下、容疑者という）を想定し、容疑者の復号鍵が海賊版復号器に保持されているか否かを検査する。この検査は、あり得る全ての容疑者集合を対象とし、１つの容疑者集合毎に行なう。これは、鍵生成多項式ｆ（ｘ）が次式のように単一であるので、一度に復号鍵を無効化できる数（容疑者の数）に上限があるからである。
【０００８】
ｆ（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋…＋ａk・ｘk 
かかるブラックボックス追跡は、全ユーザ数をｎ、最大結託人数をｋとしたとき、ｎＣｋ＝ｎ！／｛ｋ！（ｎ−ｋ）！｝通りの容疑者集合を検査する必要があるため、前述した通り、実用上不可能となる問題がある。
【０００９】
一方、この問題を解決する観点から、複数の鍵生成多項式を用い、復号鍵の無効化を柔軟に行う技術が提案されている（例えば非特許文献２参照）。なお、ここでいう柔軟とは、無効化できる復号鍵の数に上限がない旨を意味する。
【００１０】
しかしながら、非特許文献２においても、鍵配送方法には秘密分散法が応用されるため、ブラックボックス追跡の際に、各入力の意図（想定した容疑者）が不正復号器に知られてしまう。ここで、巧妙な不正復号器であれば、入力の意図を読み取って不正ユーザの特定を妨げるように動作し、ブラックボックス追跡を失敗させる。この失敗は、不正ユーザを特定できないか、または無実のユーザに濡れ衣を着せてしまう問題につながる。
【非特許文献１】Ｍ．ナオア、Ｂ．ピンカス（M. Naor and B. Pinkas）、“エフィシェント・トレース・アンド・リボーク・スキームズ（Efficient Trace and Revoke Schemes）”、 イン・プロシーディングス・オブ・ファイナンシャル・クリプトグラフィ・’００（In Proc. of Financial Cryptography ’00）、エルエヌシーエス１９６２（LNCS 1962）、シュプリンガー・フェアラーク（Springer-Verlag）、２０００年２月、pp.1-20
【非特許文献２】松下達之（T. Matsushita）、“ア・フレキシブリー・リボケーブル・キーディストリビューション・スキーム・フォー・エフィシェント・ブラックボックス・トレーシング（A Flexibly Revocable Key-Distribution Scheme for Efficient Black-Box Tracing）”、イン・プロシーディングス・オブ・インターナショナル・コンファレンス・オン・インフォメーション・アンド・コミニュケーションズ・セキュリティ・’０２（In Proc. of International Conference on Information and Communications Security '02）、エルエヌシーエス２５１３（LNCS 2513）、シュプリンガー・フェアラーク（Springer-Verlag）、２００２年１２月、 pp. 197-208
【発明の開示】
【発明が解決しようとする課題】
【００１１】
以上説明したように従来の不正ユーザ特定方法では、ブラックボックス追跡の際に、各入力の意図が不正復号器に知られてしまうため、巧妙な不正復号器に対しては、ブラックボックス追跡が失敗するという問題がある。
【００１２】
本発明は上記実情を考慮してなされたもので、ブラックボックス追跡の際に、入力の意図を不正復号器に知られることが無く、巧妙な不正復号器に対しても、確実に追跡を実行し得るコンテンツ提供側システム、ユーザ側システム、追跡システム、装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
第１の発明は、複数のユーザ側システムに割り当てられた復号鍵に対応する暗号化鍵を第三者装置から受信し、前記各ユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムであって、提供すべきコンテンツをセッション鍵で復号可能に暗号化し、前記暗号化コンテンツを得るコンテンツ暗号化手段と、前記セッション鍵を前記暗号化鍵で復号可能に暗号化し、得られた暗号化セッション鍵を含み且つ前記暗号化セッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成手段と、前記暗号化コンテンツ及び前記ヘッダ情報を各ユーザ側システムに送信する送信手段とを備え、前記復号鍵としては、複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値であるコンテンツ提供側システムである。
【００１４】
第２の発明は、コンテンツ提供側システムから提供された暗号化コンテンツを復号するユーザ側システムであって、前記コンテンツ提供側システムから、セッション鍵で復号可能な暗号化コンテンツと、ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ前記暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報とを受信する手段と、前記復号鍵に基づいて、前記ヘッダ情報からセッション鍵を復号するセッション鍵復号手段と、前記復号されたセッション鍵に基づいて、前記暗号化コンテンツを復号するコンテンツ復号手段とを備え、前記セッション鍵復号手段としては、複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ識別情報を代入することによって得られた値を前記復号鍵とするユーザ側システムである。
【００１５】
第３の発明は、検査対象のユーザ側システムを検査し、不正ユーザを特定して追跡するための追跡システムであって、ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ当該暗号化されたセッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含むヘッダ情報を生成するヘッダ情報生成手段と、コンテンツをセッション鍵で復号可能に暗号化し、暗号化コンテンツを得るコンテンツ暗号化手段と、前記ヘッダ情報及び前記暗号化コンテンツを前記検査対象のユーザ側システムに入力し、このユーザ側システムによる暗号化コンテンツの復号結果を取得する手段と、前記ヘッダ情報生成手段の制御により、復号不能なユーザ側システムの数を変えて生成されたヘッダ情報と、当該ヘッダ情報を入力したときに取得した復号結果との関係に基づいて、前記検査対象のユーザ側システムの作出のもととなった１以上のユーザ側システムの不正ユーザを特定する特定手段とを備え、前記復号鍵としては、複数のユーザ識別情報が属するサブグループ毎に割り当てられた鍵生成多項式に、ユーザ側システム固有のユーザ識別情報が代入されることにより、得られた値である追跡システムである。
【００１６】
第４の発明は、複数のユーザ側システムへ暗号化コンテンツとこの暗号化コンテンツを復号するためのヘッダ情報とを提供するコンテンツ提供側システムに用いられる鍵生成方法であって、複数個の多項式係数に基づいて、前記各ユーザ側システム共通の暗号化鍵を生成する暗号化鍵生成工程と、前記各多項式係数に基づいて、前記各ユーザ側システム固有の復号鍵を生成する復号鍵生成工程とを備え、前記復号鍵生成工程としては、複数のユーザ側システムを個別に識別するための複数のユーザ識別情報が属するグループを、複数のサブグループに分割する工程と、ルートから一つ又は複数のノードを介して複数のリーフに至る木構造に関し、前記サブグループ毎に前記各リーフを割り当てる工程と、前記ルートと，前記木構造におけるノードと，前記リーフとの一部又は全てに対し、前記各多項式係数を有して互いに異なる鍵生成多項式を割り当てる工程と、１個以上のサブグループ毎について、前記木構造に割り当てられた全ての鍵生成多項式のうち少なくとも一つの鍵生成多項式を割り当てる工程と、前記ユーザ側システム毎のユーザ識別情報を、このユーザ識別情報が属するサブグループに割り当てられた鍵生成多項式に代入し、得られた値を当該ユーザ側システム固有の復号鍵とする工程と、を備えた鍵生成方法である。
【００１７】
（作用）
第１〜第４の各発明は、ヘッダ情報が暗号化セッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含み、ユーザ側システムのユーザ識別情報を含まないので、ブラックボックス追跡の際に、入力の意図を不正復号器に知られることが無く、入力の意図を読み取って不正ユーザの特定を阻止しようと動作する巧妙な不正復号器に対しても、確実に追跡を実行することができる。
【００１８】
なお、以上の各発明は、主に「システム」のカテゴリーで表現したが、これに限らず、「装置」、「方法」、「コンピュータ読取り可能な記憶媒体」又は「プログラム」等といった任意のカテゴリーで表現してもよいことは言うまでもない。また、システム全体のカテゴリーを変える場合に限らず、システムの一部を抽出して他のカテゴリーで表現してもよいことも言うまでもない。
【発明の効果】
【００１９】
以上説明したように本発明によれば、ブラックボックス追跡の際に、入力の意図を不正復号器に知られることが無く、巧妙な不正復号器に対しても、確実に追跡を実行できる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の各実施形態について図面を参照しながら説明する。  
（第１の実施形態）
図１は本発明の第１の実施形態に係るコンテンツ提供側システム及びユーザ側システム等が適用されたデータ通信システムの構成を示す模式図であり、図２及び図３は同実施形態におけるユーザ集合のサブグループを説明するための模式図であり、図４は同実施形態における追跡システムの構成を示す模式図である。
【００２１】
このデータ通信システムは、図１に示すように、暗号化装置１０を有するコンテンツ提供側システム１と、復号装置２０を有するｎ個のユーザ側システム２とがネットワーク３を介して接続されている。また、ネットワーク３には例えば追跡装置３０が接続されている。
【００２２】
ここで、コンテンツ提供側システム１は、コンテンツを暗号化してネットワーク３を介してブロードキャストあるいはマルチキャストするものである。
【００２３】
ｎ個のユーザ側システム２は、コンテンツ提供側システム１によりブロードキャストあるいはマルチキャストされた暗号化コンテンツをネットワーク３を介して受信し復号するものである。
【００２４】
なお、図１では、１つのコンテンツ提供側システム１のみ示しているが、コンテンツ提供側システム１が複数存在しても構わない。
【００２５】
また、１つのノードが、コンテンツ提供側システム１の機能とユーザ側システム２の機能とを兼ね備えてもよい。また、全てのノードがコンテンツ提供側システム１の機能とユーザ側システム２の機能とを兼ね備えることによって、相互に暗号通信可能としてもよい。
【００２６】
ネットワーク３は、有線ネットワークでも、無線ネットワークでもよい。また、有線ネットワークと無線ネットワークを両方使用したものであってもよい。また、双方向ネットワークでも、単方向ネットワークでもよい。また、ネットワーク３は、オフラインであってもよい。つまりＤＶＤ等の媒体を用いて実現されていても構わない。
【００２７】
次に、コンテンツ提供側システム１に搭載される暗号化装置１０を説明する。  
暗号化装置１０は、公開鍵格納部１１、無効化対象ユーザ情報格納部１２、セッション鍵生成部１３、コンテンツ暗号化部１４及びヘッダ生成部１５を備えている。
【００２８】
公開鍵格納部１１は、公開鍵を格納するメモリであり、セッション鍵生成部１３及びヘッダ生成部１５から読出可能となっている。
【００２９】
無効化対象ユーザ情報格納部１２は、無効化の対象とするユーザに関する情報（ユーザＩＤ等）を格納するメモリであり、ヘッダ生成部１５から読出可能となっている。
【００３０】
セッション鍵生成部１３は、公開鍵格納部１１内の公開鍵をもとにセッション鍵を生成する機能をもっている。
【００３１】
コンテンツ暗号化部１４は、提供すべきコンテンツを、セッション鍵生成部１３により生成されたセッション鍵に基づいて暗号化し、暗号化コンテンツを得る機能をもっている。なお、暗号化コンテンツはセッション鍵に基づいて復号可能である。
【００３２】
ヘッダ生成部１５は、公開鍵、セッション鍵（のもととなる情報）、（無効化対象ユーザがある場合の）情報無効化対象ユーザ情報や、その他の必要なパラメータ（後述する例では、パラメータｐ、ｑ、ｋ、Ｕ(=Ｕ1+・・・+Ｕt)）等に基づいてヘッダ情報を生成する機能をもっている。なお、ユーザ集合ＵはサブグループＵ１〜Ｕｔの和集合である。
【００３３】
具体的には、ヘッダ生成部１５は、暗号化セッション鍵及び３種類のヘッダ情報を生成する機能を有する。暗号化セッション鍵は、セッション鍵を公開鍵で暗号化することにより、生成される。
【００３４】
第１のヘッダ情報は、無効化対象ユーザに関するものであり、暗号化セッション鍵を含まないものである。
【００３５】
第２のヘッダ情報は、無効化対象ユーザ及び有効化対象ユーザに関する。第２のヘッダ情報は、セッション鍵を公開鍵で暗号化し、得られた暗号化セッション鍵を含み且つ暗号化セッション鍵の復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含んでいる。なお、暗号化セッション鍵は復号鍵に基づいて復号可能である。
【００３６】
第３のヘッダ情報は、有効化対象ユーザに関するものであり、暗号化セッション鍵を含んでいる。なお、第３のヘッダ情報は、有効化対象ユーザのユーザ識別情報に基づく値を含まない。但し、第３のヘッダ情報は、有効化対象ユーザのユーザ識別情報に基づく値を含んでもよい。
【００３７】
なお、コンテンツ提供側システム１は、ヘッダ情報及び暗号化コンテンツの通信インタフェース、コンテンツを蓄積する装置、コンテンツを入力する装置あるいは復号鍵生成装置（図示せず）など、種々の装置を必要に応じて備えるものとする。また、コンテンツ提供側システム１は、複数のサブグループに各ヘッダ情報を送信するとき、データ量を低減させる観点から、各ヘッダ情報の共通部分を共有化して送信することが好ましい。但し、これに限らず、共通部分を共有化しなくてもよい。
【００３８】
ここで、復号鍵生成装置は、各ユーザ側システム固有の復号鍵を生成するものであり、複数のユーザ側システムを個別に識別するための複数のユーザ識別情報が属するグループを複数のサブグループに分割する機能と、サブグループ毎に互いに異なる鍵生成多項式を割り当てる機能と、ユーザ側システム毎のユーザ識別情報をこのユーザ識別情報が属するサブグループの鍵生成多項式に代入し、得られた値を当該ユーザ側システム固有の復号鍵とする機能とをもっている。
【００３９】
詳しくは、ユーザの復号鍵は鍵生成多項式にユーザＩＤ（一定の範囲内から選択された正整数（例えば、１からｎまでの連番）とする）を代入して生成する。その際、図２及び図３に例示するように、ユーザ集合を複数のサブグループに分割し、各サブグループへの鍵生成多項式の割り当て方を以下のようにする。  
例えばサブグループＵ1に対しては、  
ｆ1（ｘ）＝ａ0＋ｂ1・ｘ＋ａ2・ｘ2＋ａ3・ｘ3＋…＋ａk・ｘkを割り当てる。  
サブグループＵ2に対しては、  
ｆ2（ｘ）＝ａ0＋ａ1・ｘ＋ｂ2・ｘ2＋ａ3・ｘ3＋…＋ａk・ｘkを割り当てる。  
サブグループＵ3に対しては、  
ｆ3（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋ｂ3・ｘ3＋…＋ａk・ｘkを割り当てる。
【００４０】
以下同様にして、サブグループＵｉに対しては、次式のｆi（ｘ）を割り当てる。
【００４１】
ｆi（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋…＋ａi-1・ｘi-1＋ｂi・ｘi＋ａi＋1・ｘi＋1＋…＋ａk-2・ｘk-2＋ａk-1・ｘk-1＋ａk・ｘk 
但し、ａ0〜ａi-1，ａi＋1〜ａkは多項式係数、ｂiは第ｉのサブグループ固有の多項式係数。なお、上記割り当て方は一例であり、例えば、鍵生成多項式ｆi（ｘ）をサブグループ番号ｉに対応させずランダムかつユニークに割り当てる割り当て方も可能であるし、どのサブグループにも割り当てられない鍵生成多項式ｆj（ｘ）が存在してもよい。
【００４２】
このように、それぞれのサブグループに対し異なる鍵生成多項式（上記は、多項式係数の一部（ｂｉ）を異にする鍵生成多項式の例）を割り当てる割り当て方とし、当該ユーザＩＤの属するサブグループに割り当てられた鍵生成多項式を用いて当該ユーザＩＤの復号鍵を生成するようにする。
【００４３】
これにより、任意の人数のユーザの復号鍵を無効化することが可能となり、また、ブラックボックス追跡に要する処理ステップ数の削減が可能となる。
【００４４】
なお、ユーザ側システム２に割り当てられたユーザＩＤを、当該ユーザＩＤの属するサブグループに割り当てられた鍵生成多項式に代入して得られる復号鍵は、予めコンテンツ提供側システム１または信頼できる第三者からユーザ側システム２へ与えられて保持しておくものとする。
【００４５】
なお、図２及び図３に例示したグルーピングの方法は一例であり、この他にも種々のグルーピングの仕方が可能である。
【００４６】
また、上記では、ユーザＩＤを一定の範囲内から選択された正整数（例えば、１からｎまでの連番）としているが、その代わりに、ユーザＩＤは特に正整数とはせずに（例えば、英数字等でもよい）、英数字等のユーザＩＤに対して固有に一定の範囲内から選択された正整数を割り当て、ユーザＩＤに固有に割り当てられた正整数及び該当する鍵生成多項式をもとに復号鍵を計算する構成も可能である。
【００４７】
次に、ユーザ側システム２に搭載される復号装置２０を説明する。  
復号装置２０は、図１に示すように、ユーザ情報格納部２１、セッション鍵復号部２２及びコンテンツ復号部２３を備えている。
【００４８】
ユーザ情報格納部２１は、復号に必要なパラメータ（後述する例では、パラメータｐ、ｑ、ｋ）と、自システム２が属するサブグループＩＤと、自システム２に割り当てられたユーザＩＤと、該ユーザＩＤに対応する復号鍵を格納するメモリであり、セッション鍵復号部２２から読出可能となっている。なお、復号鍵は、該ユーザＩＤが属するサブグループに割り当てられた鍵生成多項式に該ユーザＩＤを代入することによって得られる値である。
【００４９】
セッション鍵復号部２２は、コンテンツ提供側システム１から暗号化コンテンツとヘッダ情報とを受信したとき、ユーザ情報格納部２１内の復号鍵に基づいて、ヘッダ情報からセッション鍵を取得（復号）する機能をもっている。
【００５０】
コンテンツ復号部２３は、セッション鍵復号部２２により取得（復号）したセッション鍵に基づいて、コンテンツ提供側システム１から受信した暗号化コンテンツを復号する機能をもっている。
【００５１】
なお、ユーザ側システム２は、コンテンツ提供側システム１から暗号化コンテンツとヘッダ情報とを受信する通信インタフェース、コンテンツを蓄積する装置あるいはコンテンツを表示等する装置など、種々の装置を必要に応じて備えるものとする。
【００５２】
次に、図４を用いて追跡装置３０を説明する。  
追跡装置３０は、公開鍵格納部３１、ヘッダ生成部３２及び制御部３３を備えている。
【００５３】
ここで、公開鍵格納部３１は、公開鍵を格納するメモリであり、ヘッダ生成部３２から読出可能となっている。
【００５４】
ヘッダ生成部３２は、制御部３３から指示された無効化対象ユーザ集合に従い、公開鍵やその他の必要なパラメータ（後述する例では、パラメータｐ、ｑ、ｋ、Ｕ(=Ｕ1+・・・+Ｕt)）等をもとにしてヘッダ情報を生成する機能と、ヘッダ情報を検査対象に入力する機能とをもっている。なお、セッション鍵（のもととなる情報）は、制御部３３が生成してヘッダ生成部３２に指示してもよいし、ヘッダ生成部３２が生成して制御部３３に通知してもよい。また、ヘッダ情報は、前述同様に、ユーザ側システム固有の復号鍵で復号可能に暗号化されたセッション鍵を含み且つ当該暗号化されたセッション鍵の復号を許可する各ユーザ側システムの各ユーザ識別情報に基づく値を含むように生成される。
【００５５】
制御部（特定手段）３３は、追跡装置３０全体の制御を司るものであり、ヘッダ生成部３２の制御により、復号不能なユーザ側システムの数を変えて生成されたヘッダ情報と、当該ヘッダ情報を入力したときに取得した復号結果との関係に基づいて、前記検査対象のユーザ側システムの作出のもととなった１以上のユーザ側システムの不正ユーザを特定する機能をもっている。
【００５６】
詳しくは制御部３３は、無効化すべき（１又は複数の）ユーザＩＤ（すなわち無効化対象ユーザ集合χ）をヘッダ生成部３２に指示する機能と、検査対象復号装置２０χにより復号されたセッション鍵を入力し、正しいセッション鍵が得られたか否かを調べる機能と、無効化対象ユーザ集合を変えながら、同様の処理を繰り返し行い、それらの判定結果を総合して、不正ユーザのユーザＩＤを特定する機能とをもっている。
【００５７】
なお、制御部３３は、検査対象復号装置２０χによるセッション鍵の復号結果を判断しているが、これに限らず、ヘッダ情報に加え、セッション鍵で暗号化されたコンテンツを検査対象復号装置２０χに入力し、検査対象復号装置２０χによるコンテンツの復号結果を判断してもよい。
【００５８】
また、追跡装置３０は、例えば、コンテンツ提供側システム１に搭載されてもよいし、コンテンツ提供側システム１とは独立した装置であってもよい。また、ネットワーク３に接続する機能を備えてもよいし、備えなくても構わない。
【００５９】
次に、以上のように構成されたネットワーク通信システムの動作を説明する。図５は同システムの全体動作を説明するためのフローチャートである。
【００６０】
各ユーザ側システム２には、それぞれ固有のユーザＩＤが割り当てられているとする。
【００６１】
コンテンツ提供側システム１は、所定のセッション鍵（単一の鍵）を生成し（ＳＴ１）、無効化対象のユーザ集合に応じてセッション鍵を暗号化し、ヘッダ情報Ｈ（χ）を生成する（ＳＴ２）。
【００６２】
次に、コンテンツ提供側システム１は、該セッション鍵でコンテンツを暗号化し（ＳＴ３）、得られた暗号化コンテンツにヘッダ情報を付加してブロードキャストあるいはマルチキャストする（ＳＴ４）。
【００６３】
なお、ステップＳＴ２，ＳＴ３は、上記とは逆の順序で行ってもよいし、同時に行ってもよい。また、セッション鍵をその都度変更しない場合は、ＳＴ１が省かれることもある（従前のセッション鍵を使用する）。
【００６４】
各々のユーザ側システム２は、ヘッダ情報／暗号化コンテンツを受信すると、自己のユーザＩＤ及びサブグループＩＤに基づき、無効化対象のユーザ集合χとの関係に応じて、ヘッダ情報を復号処理する（ＳＴ５）。
【００６５】
ここで、各々のユーザ側システム２は、無効化対象のユーザ集合χに属していれば（ＳＴ６）、セッション鍵を取得できない（ＳＴ７）。逆に、無効化対象のユーザ集合χに属していなければ（ＳＴ６）、セッション鍵を取得し（ＳＴ８）、セッション鍵で暗号化コンテンツを復号する（ＳＴ９）。
【００６６】
また、詳しくは後述するように、コンテンツ提供側システム１は、無効化対象のユーザ集合χに応じてヘッダ情報を生成するので、復号鍵を柔軟に無効化できる。復号鍵の無効化は、無効化対象ユーザの復号鍵を用いてもセッション鍵が得られず、かつそれ以外のユーザの復号鍵で復号できる形式に、セッション鍵を暗号化することにより達成される。
【００６７】
なお、放送型コンテンツ配信では、送信データは単一のセッション鍵で暗号化されるのが一般的であり、鍵配送方法とは、セッション鍵を各ユーザの復号鍵で復号できる形式に暗号化するセッション鍵の暗号化・復号方法を意味する。
【００６８】
さて、以下では、予め実行される鍵生成フェーズ、ステップＳＴ２の暗号化フェーズ、ステップＳＴ５〜ＳＴ８の復号フェーズについて、詳細に説明する。
【００６９】
始めにパラメータを定義する。  
全ユーザ数をｎとし、最大結託人数をｋとする。  
ｐ、ｑを素数とし、ｑはｐ−１を割り切り、かつ、ｑはｎ＋ｋ＋１以上であるとする。
Ｚｑ＝｛０、１、…、ｑ−１｝とする。  
Ｚｐ*＝｛１、…、ｐ−１｝とする。  
Ｇｑを、Ｚｐ*の部分群であり、かつ、位数がｑである乗法群とし，ｇをＧｑの生成元とする。  
ユーザＩＤ（ユーザ番号）の集合（以下、ユーザ集合という）を、Ｕ（Ｕ⊆Ｚｑ−｛０｝）とする。なお、Ｚｑ−｛０｝は、Ｚｑから｛０｝を取り除いたものを意味する。  
無効化対象ユーザ集合（復号鍵を無効化されるユーザの集合）をχとする。  
ｐ、ｑ、ｇの値は公開されている。  
以下、特に断りの無い限り、計算はＺｐ*上で行われるとする。
【００７０】
（鍵生成フェーズ）
コンテンツ提供側システム１は、ユーザ集合Ｕを、共通要素を持たないｔ個の部分集合（サブグループ）に分割する。これらｔ個の部分集合をＵ1、…、Ｕtとする。Ｕ1、…、Ｕtは公開されている。公開鍵のもととなるパラメータａ0、…、ａk、ｂ1、…、ｂtをＺｑからランダムに選択する。
【００７１】
次に、コンテンツ提供側システム１は、公開鍵ｅを計算する。公開鍵ｅは、式（１）のようになる。
【数１】
2005236963.tif 000003
【００７２】
最後にコンテンツ提供側システム１は、部分集合Ｕiに属するユーザＩＤ＝ｕの復号鍵ｆi（ｕ）を、鍵生成多項式ｆi（ｘ）にｘ＝ｕを代入して算出する。ここで、鍵生成多項式ｆi（ｘ）は、ユーザｕの属する部分集合Ｕiに割り当てられ、式（２）のように表される。
【数２】
2005236963.tif 000004
【００７３】
なお、上記鍵生成フェーズにおける処理は、図１３に示すように、コンテンツ提供側システム１以外の信頼できる第三者装置１０ｂが行ってもよい。これは以下の各実施形態でも同様である。
【００７４】
（暗号化フェーズ）
コンテンツ提供側システム１のセッション鍵生成部１３は、セッション鍵ｓをＧｑからランダムに選択する。次に、ヘッダ生成部１５は、乱数ｒを選択し、式（３）を計算する。
【数３】
2005236963.tif 000005
【００７５】
次に、ヘッダ生成部１５は、図６に示すように、１≦ｉ≦ｔについて、以下の処理を繰り返し、Ｈ1、…、Ｈtを計算する（ＳＴ２−１〜ＳＴ２−８）。
【００７６】
ヘッダ生成部１５は、無効化対象ユーザ集合χとＵiとの積集合が空集合であるか否かを判定する（ＳＴ２−２）。
【００７７】
ここで、χとＵiとの積集合が空集合である場合を述べる。これは、Ｕiに属するユーザ全員が無効化対象ユーザではない場合であり、例えば、図２のＵ３が対応する。ヘッダ生成部１５は、次式（４）に従いＨiを計算する（ＳＴ２−３）。
【数４】
2005236963.tif 000006
【００７８】
ステップＳＴ２−２の結果、無効化対象ユーザ集合χとＵiとの積集合が空集合でない場合、ヘッダ生成部１５は、χとＵiの積集合がＵiであるか否かを判定する（ＳＴ２−４）。
【００７９】
ここで、χとＵiの積集合がＵiである場合を述べる。これは、Ｕiに属するユーザ全員が無効化対象ユーザである場合、例えば、図２のＵ1が対応する。ヘッダ生成部１５は、乱数ｚiを選択し、式（５）に従いＨiを計算する（ＳＴ２−５）。
【数５】
2005236963.tif 000007
【００８０】
なお、式（５）の例は、特定のサブグループＵｉに属する全てのユーザ側システム２の復号鍵を無効にするとき、ヘッダ情報Ｈｉにおける特定のサブグループＵｉに固有の値ｂｉを正しい値とは異なる値ｚｉに設定する例である。これに限らず、例えば、無効化するサブグループについては、ヘッダ情報Ｈｉの固有の値ｂｉを削除（記述を禁止）してもよい。
【００８１】
このようにしても、無効化するサブグループについては、ヘッダ情報に、セッション鍵を計算するもととなる情報自体が含まれていないので、結局、正しいセッション鍵を求めることができず、他方、それ以外のサブグループについては、正しいセッション鍵を求めることができることになる。
【００８２】
一方、ステップＳＴ２−４の結果がそれ以外となる場合を述べる（ＳＴ２−４；ＮＯ）。これは、Ｕiに属するユーザの少なくとも１人は無効化対象ユーザではなく、かつ少なくとも１人は無効化対象ユーザである場合、例えば、図２のＵ2に対応する。
【００８３】
ヘッダ生成部１５は、図７に示すように、Ｕiから、無効化対象ユーザ集合χを取り除いた部分集合を｛ｘ1、…、ｘw｝とする。例えば、図２のＵ2の場合に｛ｘ1、…、ｘ１０｝＝｛３１、…、４０｝（ｗ＝１０）などとなる。
【００８４】
次に、ヘッダ生成部１５は、ｄ（ｋ＋１）≦ｗ≦ｄ（ｋ＋１）＋ｋを満たす整数ｄを求め、ｍ＝ｄ（ｋ＋１）＋ｋとする。
【００８５】
次に、ｗ＜ｍならば、ｘw+1、…、ｘmをＺｑ−（Ｕ＋｛０｝）からランダムに選択する。なお、Ｚｑ−（Ｕ＋｛０｝）は、ＺｑからＵと｛０｝の和集合を取り除いたものを意味する。また、上記処理において、Ｕiから、無効化対象ユーザ集合χを取り除いた部分集合｛ｘ1、…、ｘw｝に対し、（ユーザ集合以外且つ｛０｝以外で）Ｚｑから適宜選択したｍ’−ｗ個の異なる要素ｘw+1、…、ｘm’を任意に付け加えてもよい。この場合、｛ｘ1、…、ｘw、ｘw+1、…、ｘm’｝を、これまでの｛ｘ1、…、ｘw｝と考え、（これまでの各数式においてｗ＝ｍ’として）計算を行えばよい。
【００８６】
ヘッダ生成部１５は、１≦α≦ｍについて、ｃ0＝１として式（６）を満たすＺｑの要素ｃ1、…、ｃmを求める。
【数６】
2005236963.tif 000008
【００８７】
この場合、ヘッダ情報Ｈｉは、サブグループ毎に固有の値ｂｉと、当該サブグループに属する複数のユーザＩＤの部分集合｛ｘ１〜ｘｗ｝に基づく値｛ｃ０，…，ｃｍ｝とを含む。ヘッダ生成部１５は、特定のサブグループに属する全てのユーザ側システムのうち、１以上のユーザ側システム２の復号鍵を無効にするとき、当該無効にするユーザ側システム２のユーザＩＤを部分集合｛ｘ１〜ｘｗ｝に含めないようにすればよい。
【００８８】
なお、前述した部分集合に基づく値｛ｃ０，…，ｃｍ｝は、当該部分集合に属する各ユーザＩＤ｛ｕ１，…，ｕｗ｝をｍ次多項式の変数として第２ベクトルとする場合の当該第２ベクトルとの内積を０とする下記式の関係を満たす第１ベクトルである。
【００８９】
（ｃ０，ｃ１，ｃ２，…，ｃｍ）・（１，ｕｗ，ｕｗ２，…，ｕｗｍ）＝０ ｍｏｄ ｑ
但し、ｕｗ＝ｕ１〜ｕｗのいずれか。
【００９０】
以上の繰り返し処理により得られたＨ1、…、ＨtをヘッダＨ（χ）とする（ＳＴ２−９）。ここで、ヘッダは公開鍵ｅを用いて計算できるので、誰でもコンテンツ提供側システム１を運営することができる。また、以上の繰り返し処理により得られたＨ1、…、Ｈtを構成する各要素の中での同一要素を１つにまとめ、ヘッダＨ（χ）内にて共有化することにより、送信オーバヘッドをより削減することができる。これは以下の各実施形態でも同様である。
【００９１】
コンテンツ提供側システム１は、ヘッダＨ（χ）とセッション鍵ｓで暗号化したコンテンツとをユーザ側システム２へ送信する（ＳＴ３〜ＳＴ４）。
【００９２】
（復号フェーズ）
部分集合Ｕiに属するユーザｕを考える。ユーザＩＤ＝ｕのユーザ側システム２は、図８に示すように、ヘッダＨ（χ）を受信した場合（ＳＴ５−１）、Ｈiを用いて式（８）を計算する。
【数７】
2005236963.tif 000009
【００９３】
なお、ｄ＝（ｍ−ｋ）／（ｋ＋１）である。
【００９４】
ここで、ヘッダ情報からセッション鍵を復号した結果について簡単に説明する。  
ユーザ側システム２のセッション鍵復号部２２における復号結果は、無効化対象ユーザ集合χとＵiの積集合が空集合であるか（ＳＴ５−２）、無効化対象ユーザ集合χとＵiの積集合がＵiであるか（ＳＴ５−４）、またはそれ以外（ＳＴ６）の場合によって場合分けされる。なお、ユーザ側システム２のセッション鍵復号部２２がこれを判定することはなく、どの場合においても復号手順は共通であり、Ｈiを用いて式（８）を計算する。
【００９５】
ここで、χとＵiの積集合が空集合である場合（ｍ＝ｋ、ｄ＝０）（ＳＴ５−２；ＹＥＳ）を述べる。これは、Ｕiに属するユーザ全員が無効化対象ユーザではない場合であり、例えば、図２のＵ３が対応する。セッション鍵復号部２２は、式（９）のようにＤi（ｕ）を計算し（ＳＴ５−３）、セッション鍵ｓを得る（ＳＴ８）。
【数８】
2005236963.tif 000010
【００９６】
ここで、無効化対象ユーザ集合χとＵiの積集合がＵiである場合（ｍ＝ｋ、ｄ＝０）（ＳＴ５−４；ＹＥＳ）を述べる。これは、Ｕiに属するユーザ全員が無効化対象ユーザである場合であり、例えば、図２のＵ1が対応する。
【数９】
2005236963.tif 000011
【００９７】
従って、Ｄi（ｕ）≠ｓとなり（ＳＴ５−５）、セッション鍵ｓを得られない（ＳＴ７）。このとき、サブグループＵiに属するユーザＩＤについては、セッション鍵を計算するもととなる情報ｈi、g(i)が間違った値になっているので、正しいセッション鍵を取得することができない。
【００９８】
ここで、それ以外の場合を述べる（ＳＴ５−４；ＮＯ）。これは、Ｕiに属するユーザの少なくとも１人は無効化対象ユーザではなく、かつ少なくとも１人は無効化対象ユーザである場合であり、例えば、図２のＵ2が対応する。
【００９９】
Ｄi（ｕ）はさらに式（１０）のように表される。
【数１０】
2005236963.tif 000012
【０１００】
ユーザｕが無効化対象ユーザである場合（ＳＴ６；ＹＥＳ）、式（１１）が不成立であるので、セッション鍵ｓを得られない（ＳＴ７）。
【０１０１】
（追跡フェーズ）
次に、追跡アルゴリズムの手順例を示すが、その前に追跡装置３０とその追跡対象となる不正ユーザについて概略を述べる。追跡装置３０は、海賊版復号器（不正復号器）が押収された場合に、ブラックボックス追跡により、該海賊版復号器の不正作出のもととなった不正ユーザ（のユーザＩＤ）を特定するためのものである。
【０１０２】
正当な復号装置をもとにして海賊版復号器が作出される場合、１台の復号装置のみをもとにして作出される場合と、複数台の復号装置をもとにして作出される場合とがある。後者の場合の復号装置の不正ユーザを結託者と呼ぶ。
【０１０３】
１台の復号装置のみをもとにして作出された海賊版復号器は、当該復号装置と同じ復号鍵が使用可能になる。複数台の復号装置をもとにして作出された海賊版復号器は、当該複数の復号装置と同じ復号鍵がいずれも使用可能になる。後者の場合、結託者に対する全ての復号鍵が無効化されない限り、セッション鍵を得ることが可能になる。
【０１０４】
この追跡装置３０は、複数の不正ユーザが結託した場合に対しても、従来のｎＣｋ通りの検査と比べ、迅速に検査を実行でき、１以上の不正ユーザを特定するものである。
【０１０５】
（手順例）
具体的な追跡アルゴリズムの手順については様々なバリエーションが可能であり、以下に示すものに限定されるものではない。図９は追跡装置による追跡フェーズの動作を説明するためのフローチャートである。
【０１０６】
海賊版復号器Ｄが押収されたとき、以下の処理により不正ユーザを特定する。
【０１０７】
なお、部分集合Ｕ1、…、Ｕtの要素は、式（１２）のようにラベル付けされているとする。
【数１１】
2005236963.tif 000013
【０１０８】
追跡装置３０は、ｊ＝１、…、ｎについて以下の処理を実行する（ＳＴ１１〜ＳＴ２１）。制御部３３は、正常な復号回数Ｃj＝０、同一の無効化対象ユーザ集合χの検査回数ｚ＝１と代入し、以下の処理をｍ回繰り返す（ＳＴ１２）。
【０１０９】
制御部３３は、無効化対象ユーザ集合χ＝｛ｕ1、…、ｕj｝とし（ＳＴ１３）、ヘッダ生成部３２を制御し、ヘッダＨ（χ）を生成させる（ＳＴ１４）。なお、ヘッダ生成法は暗号化フェーズに示した方法と同様であり、乱数は毎回ランダムに選択される。
【０１１０】
ヘッダ生成部３２がヘッダＨ（χ）を不正復号器Ｄに入力すると（ＳＴ１５）、制御部３３は、不正復号器Ｄの出力を観察する。
【０１１１】
このとき、制御部３３は、不正復号器Ｄが正しいセッション鍵ｓを出力したか否かを判定し（ＳＴ１６）、正しいセッション鍵ｓを出力した場合（ＳＴ１６；ＹＥＳ）、Ｃjを1だけインクリメントする（ＳＴ１７）。そうでない場合（ＳＴ１６；ＮＯ）、Ｃj の値を変化させない。
【０１１２】
なお、海賊版復号器Ｄが復号後のコンテンツのみを出力する場合、コンテンツが正しく復号されているか否かを観測し、コンテンツが正しく復号されていればＣjを1だけインクリメントし、そうでなければＣj の値は変化しないようにすればよい。
【０１１３】
いずれにしても、制御部３３は、Ｃｊの更新が終わると、検査回数ｚがｍ回未満か否かを判定し（ＳＴ１８）、ｍ回未満であればｚを１だけインクリメントし（ＳＴ１９）、ステップＳＴ１４に戻って検査を繰り返す。
【０１１４】
また、制御部３３は、ステップＳＴ１８の判定の結果、検査回数ｚがｍ回未満でないとき、無効化対象のユーザ番号ｊがユーザ総数ｎ未満か否かを判定し（ＳＴ２０）、ｎ未満であればｊを１だけインクリメントし（ＳＴ２１）、ステップＳＴ１２に戻って検査を繰り返す。
【０１１５】
ステップＳＴ２０の判定の結果、無効化対象のユーザ番号ｊがユーザ総数ｎ未満でなければ検査が終了する。次に、制御部３３は、ｊ＝１、…、ｎについて、得られたＣj-1−Ｃjを計算し、Ｃj-1−Ｃjが最大値となる整数ｊを検出すると（ＳＴ２２）、ｕjを不正ユーザと特定してそのユーザＩＤを出力する（ＳＴ２３）。  
この追跡方法では、図１０及び図１１に示すように、無効化対象ユーザ集合に属する不正ユーザの候補を一人ずつ増やし、不正ユーザの候補を無効化したときに復号不能となるかを検査しており、この検査を合計ｍｎ回行うことにより、１人以上の不正ユーザを特定することができる。
【０１１６】
例えば、ユーザＩＤの集合を｛ｕ1、…、ｕn｝とし、検査対象復号装置２０χの結託者のユーザＩＤ＝ｕ2、ｕ4であるとする。
【０１１７】
この場合、ユーザＩＤ＝ｕ1、ｕ2、ｕ3を無効化対象として生成したヘッダ情報を与えると、該検査対象復号装置２０χはユーザＩＤ＝ｕ4に対応しているので、正しいセッション鍵が得られるので、ｍ回の繰り返し処理後Ｃ3＝ｍとなる。
【０１１８】
また、ユーザＩＤ＝ｕ1、ｕ2、ｕ3、ｕ4を無効化対象として生成したヘッダ情報を与えると、該検査対象復号装置からは、正しいセッション鍵が得られないので、ｍ回の繰り返し処理後Ｃ4＝０となる。
【０１１９】
したがって、Ｃ3−Ｃ4が最大値ｍを与えるため、該検査対象復号装置２０χの結託者の内の１人のユーザＩＤは、ｕ4であることがわかる。さらに、ユーザのラベル付けの順序を変えることにより、結託者全員のユーザＩＤを特定することも可能である。
【０１２０】
より一般的には、Ｃj-1−Ｃj≧ｍ／ｎとなる整数ｊが少なくとも１つは存在し、ユーザＩＤ＝ｕiのユーザが不正ユーザでないときＣi-1−Ｃi≪ｍ／ｎであることから、Ｃj-1−Ｃjが最大値となる整数jを検出することにより不正ユーザＩＤを特定できる。なお、検査対象復号装置がより巧妙な不正復号器であるとき、検査対象復号装置がブラックボックス追跡を検知して、ある時点以降、ヘッダ生成部３２からの入力を全く受け付けなくなる場合が考えられる。この場合、その時点のｊの値を用いて不正ユーザＩＤをｕjと特定できる。これは以下の各実施形態でも同様である。
【０１２１】
ここで、ヘッダは公開鍵ｅを用いて計算できるので、誰でも追跡装置３０を用いて不正ユーザを追跡することができる。
【０１２２】
上述したように本実施形態によれば、ヘッダ情報が、暗号化されたセッション鍵ｓの復号を許す各ユーザ側システムのうち少なくとも一つのユーザ側システムのユーザ識別情報に基づく値を含み、ユーザ側システムのユーザ識別情報を含まないので、ブラックボックス追跡の際に、誰の復号鍵が無効化されているかという情報が漏れない。これにより、ブラックボックス追跡の際に、各入力の意図が不正復号器に知られることがないため、入力の意図を読み取って不正ユーザの特定を阻止しようと動作する巧妙な不正復号器に対しても、確実に追跡を実行することができる。
【０１２３】
また、一度に検査できる容疑者数の制限が無いので、効率的なブラックボックス追跡を実現できる。
【０１２４】
（第２の実施形態）
次に、本発明の第２の実施形態について説明する。本実施形態は、第１の実施形態の変形例であり、サブグループの分割方法を変えたものである。
【０１２５】
例えば、Ｖ・ｋ＋Δｋ個（１≦Ｖ、０＜Δｋ≦ｋ）のサブグループに分割する場合に、第ｖ・ｋ＋ｉ（０≦ｖ≦Ｖ、０≦ｖ＜Ｖのときに１≦ｉ≦ｋ、ｖ＝Ｖのときに１≦ｉ≦Δｋ）で表されるサブグループに対して、次式（１３）で表されるような鍵生成多項式を割り当てる方法が可能である。  
ｆv・k＋i（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋…＋ａi-1・ｘi-1＋ｂv,i・ｘi＋ａi＋1・ｘi＋1＋…＋ａk-2・ｘk-2＋ａk-1・ｘk-1＋ａk・ｘk       …（１３）
但し、ａ0〜ａi-1，ａi＋1〜ａkは多項式係数、ｂv,iは第ｖ・ｋ＋ｉのサブグループ固有の多項式係数。
【０１２６】
この第ｖ・ｋ＋ｉのサブグループに対し、式（１３）を割り当てる例は、固有の多項式係数ｂv,iをａ0には設定しない場合を示している。なお、この例に代えて、第ｖ・（ｋ＋１）＋ｉ＋１のサブグループに対し、式（１３ｃ）を割り当てることにより、固有の多項式係数ｂv,iをａ0にも設定することもできる。
【０１２７】
ｆv・(k+1)+i+1（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋…＋ａi-1・ｘi-1＋ｂv,i・ｘi＋ａi＋1・ｘi＋1＋…＋ａk-2・ｘk-2＋ａk-1・ｘk-1＋ａk・ｘk     …（１３ｃ）
但し、ａ0〜ａi-1，ａi＋1〜ａkは多項式係数、ｂv,iは第ｖ・（ｋ＋１）＋ｉ＋１のサブグループ固有の多項式係数。なお、上記両割り当て方は一例であり、例えば、鍵生成多項式ｆv・k＋i（ｘ）をサブグループ番号ｉに対応させずランダムかつユニークに割り当てる割り当て方も可能であるし、どのサブグループにも割り当てられない鍵生成多項式ｆw・k＋j（ｘ）が存在してもよい。これは鍵生成多項式ｆv・(k+1)+i+1（ｘ）についても同様であり、さらに以下の各実施形態でも同様である。
【０１２８】
ここで、上記ｆv・k＋i（ｘ）の係数ｂv,iでｖ＝０の場合の各係数すなわちｂ0,1，…，ｂ0,kは、それぞれ、これまでの説明におけるｂ1，…，ｂkに対応している。また、以下の説明では、ｂ0,1，…，ｂ0,kをそれぞれｂ1，…，ｂkで略記し、ｂ1,1，…，ｂ1,kをそれぞれｄ1，…，ｄkで略記することもある。
【０１２９】
例えば、上記でＶ＝１とすると、ｋの値は増加させずに、鍵生成フェーズにおいてｄ1，…，ｄΔk（上記式（１３）では、ｂ1,1，…，ｂ1,Δkとなる）を追加し、鍵生成多項式の種類(サブグループ数)を次式（１４）のように増加させることもできる。  
ｆ1（ｘ）＝ａ0＋ｂ1・ｘ＋ａ2・ｘ2＋ａ3・ｘ3＋…＋ａk・ｘk 
ｆ2（ｘ）＝ａ0＋ａ1・ｘ＋ｂ2・ｘ2＋ａ3・ｘ3＋…＋ａk・ｘk 
：  
ｆk（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋ａ3・ｘ3＋…＋ｂk・ｘk 
ｆk+1（ｘ）＝ａ0＋ｄ1・ｘ＋ａ2・ｘ2＋ａ3・ｘ3＋…＋ａk・ｘk 
ｆk+2（ｘ）＝ａ0＋ａ1・ｘ＋ｄ2・ｘ2＋ａ3・ｘ3＋…＋ａk・ｘk 
：  
ｆk+Δk（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋…＋ｄΔk・ｘΔk＋…＋ａk・ｘk 
…（１４）
なお、Ｖ＝１、Δｋ＝ｋの場合には、次式（１５）のようになる。  
ｆ1（ｘ）＝ａ0＋ｂ1・ｘ＋ａ2・ｘ2＋ａ3・ｘ3＋…＋ａk・ｘk 
ｆ2（ｘ）＝ａ0＋ａ1・ｘ＋ｂ2・ｘ2＋ａ3・ｘ3＋…＋ａk・ｘk 
：  
ｆk（ｘ）＝ａ0＋ａ1・ｘ＋ａ2・ｘ2＋ａ3・ｘ3＋…＋ｂk・ｘk 
ｆk+1（ｘ）＝ａ0＋ｄ1・ｘ＋ａ2・ｘ2＋ａ3・ｘ3＋…＋ａk・ｘk 
ｆk+2（ｘ）＝ａ0＋ａ1・ｘ＋ｄ2・ｘ2＋ａ3・ｘ3＋…＋ａk・ｘk 
：  
ｆ2k（ｘ）＝ａ0＋ａ1・ｘ＋ｄ2・ｘ2＋ａ3・ｘ3＋…＋ｄk・ｘk 
…（１５）
Ｖ＞２の場合には、同様にして適宜パラメータを追加して、鍵生成多項式の種類(サブグループ数)を増加させればよい。例えば上記式（１３）において、パラメータｂv,iを次のようにすればよい。
【数１２】
2005236963.tif 000014
【０１３０】
また、ｋの値を増加させるとともに、パラメータの追加も行うようにして、鍵生成多項式の種類(サブグループ数)を増加させることも可能である。なお、ｋの値を２ｋ−１に増加させた例については後述する各実施形態で詳細に述べる。
【０１３１】
上述したように本実施形態によれば、第１の実施形態の作用効果に加え、サブグループの分割方法を変えることができる。
【０１３２】
（第３の実施形態）
次に、本発明の第３の実施形態について説明する。本実施形態は、第１の実施形態の変形例であり、セッション鍵ｓの埋め込み位置が異なり、安全性を高めるために鍵生成多項式の次数を２ｋ−１に増加させている。以下、鍵生成フェーズ、暗号化フェーズ、復号フェーズ、追跡フェーズの順に説明する。なお、パラメータなどの定義は、特に断りの無い限り、第１の実施形態と同じものを用いる。
【０１３３】
ｑを素数とし、ｑはｐ−１を割り切り、かつ、ｑはｎ＋２ｋ以上であるとする。  
（鍵生成フェーズ）
コンテンツ提供側システム１は、ユーザ集合Ｕを、共通要素を持たないｔ個の部分集合（サブグループ）に分割する。これらｔ個の部分集合をＵ0、…、Ｕt-1とする。Ｕ0、…、Ｕt-1は公開されている。公開鍵のもととなるパラメータａ0、…、ａ2k-1、ｂ0、…、ｂt-1をＺｑからランダムに選択する。
【０１３４】
次に、コンテンツ提供側システム１は、公開鍵ｅを計算する。公開鍵ｅは、式（１ａ）のようになる。
【数１３】
2005236963.tif 000015
【０１３５】
最後にコンテンツ提供側システム１は、部分集合Ｕiに属するユーザＩＤ＝ｕの復号鍵ｆi（ｕ）を、鍵生成多項式ｆi（ｘ）にｘ＝ｕを代入して算出する。ここで、鍵生成多項式ｆi（ｘ）は、ユーザｕの属する部分集合Ｕiに割り当てられ、式（２ａ）のように表される。
【数１４】
2005236963.tif 000016
【０１３６】
（暗号化フェーズ）
コンテンツ提供側システム１のセッション鍵生成部１３は、セッション鍵ｓをＧｑからランダムに選択する。次に、ヘッダ生成部１５は、乱数ｒを選択し、図６に示すように、0≦ｉ≦ｔ-1について、以下の処理を繰り返し、Ｈ0、…、Ｈt-1を計算する（ＳＴ２−１〜ＳＴ２−８）。なお、図６では、1≦ｉ≦ｔとして繰り返し処理が行われるが、本実施形態では、0≦ｉ≦ｔ-1と読み替える。
【０１３７】
ヘッダ生成部１５は、無効化対象ユーザ集合χとＵiとの積集合が空集合であるか否かを判定する（ＳＴ２−２）。
【０１３８】
ここで、χとＵiとの積集合が空集合である場合を述べる。これは、Ｕiに属するユーザ全員が無効化対象ユーザではない場合であり、例えば、図２のＵ３が対応する。ヘッダ生成部１５は、次式（４ａ）に従いＨiを計算する（ＳＴ２−３）。
【数１５】
2005236963.tif 000017
【０１３９】
ステップＳＴ２−２の結果、無効化対象ユーザ集合χとＵiとの積集合が空集合でない場合、ヘッダ生成部１５は、χとＵiの積集合がＵiであるか否かを判定する（ＳＴ２−４）。
【０１４０】
ここで、χとＵiの積集合がＵiである場合を述べる。これは、Ｕiに属するユーザ全員が無効化対象ユーザである場合であり、例えば図２のＵ1が対応する。ヘッダ生成部１５は、乱数ｚiを選択し、式（５ａ）に従いＨiを計算する（ＳＴ２−５）。
【数１６】
2005236963.tif 000018
【０１４１】
なお、式（５ａ）の例は、前述同様に、無効化のときにはサブグループＵｉに固有の値ｂｉを正しい値とは異なる値ｚｉに設定する例である。これに限らず、無効化のときには、固有の値ｂｉを削除等してもよいことも前述した通りである。
【０１４２】
一方、ステップＳＴ２−４の結果がそれ以外となる場合を述べる（ＳＴ２−４；ＮＯ）。これは、例えば図２のＵ2に対応する。
【０１４３】
ヘッダ生成部１５は、図７に示したように、Ｕiから、無効化対象ユーザ集合χを取り除いた部分集合を｛ｘ1、…、ｘw｝とする。次に、ヘッダ生成部１５は、ｗ≦ 2ｋ（ｄ＋１）−１を満たす整数ｄを求め、ｍ＝2ｋ（ｄ＋１）−１とする。
【０１４４】
以下、前述同様に、ｗ＜ｍならば、ｘw+1、…、ｘmをＺｑ−（Ｕ＋｛０｝）からランダムに選択する。なお、上記処理において、部分集合｛ｘ1、…、ｘw｝に対し、ｍ’−ｗ個の異なる要素ｘw+1、…、ｘm’を付け加えてもよいことも前述同様である。
【０１４５】
ヘッダ生成部１５は、１≦α≦ｍについて、前述した式（６）を満たすＺｑの要素ｃ0、…、ｃmを求める。最後に、ヘッダ生成部１５は乱数ｒiを選択し、式（７ａ）に従いＨiを計算する（ＳＴ２−６）。
【数１７】
2005236963.tif 000019
【０１４６】
以上の繰り返し処理により得られたＨ0、…、Ｈt-1をヘッダＨ（χ）とする（ＳＴ２−９）。コンテンツ提供側システム１は、ヘッダＨ（χ）とセッション鍵ｓで暗号化したコンテンツとをユーザ側システム２へ送信する（ＳＴ３〜ＳＴ４）。
【０１４７】
（復号フェーズ）
部分集合Ｕiに属するユーザｕを考える。ユーザＩＤ＝ｕのユーザ側システム２は、図８に示したように、ヘッダＨ（χ）を受信した場合（ＳＴ５−１）、Ｈiを用いて式（８ａ）を計算する。
【数１８】
2005236963.tif 000020
【０１４８】
なお、ｄ＝（ｍ＋１）／２ｋ−１である。
【０１４９】
第１の実施形態と同様に、ユーザ側システム２のセッション鍵復号部２２における復号結果は、無効化対象ユーザ集合χとＵiの積集合が空集合であるか（ＳＴ５−２）、無効化対象ユーザ集合χとＵiの積集合がＵiであるか（ＳＴ５−４）、またはそれ以外（ＳＴ６）の場合によって場合分けされる。
【０１５０】
（追跡フェーズ）
追跡アルゴリズムの手順例は、第１の実施形態と同様である。ここで、ヘッダは公開鍵ｅを用いて計算できるので、誰でも追跡装置３０を用いて不正ユーザを追跡することができる。
【０１５１】
上述したように本実施形態によれば、鍵生成多項式の次数を２ｋ−１に増加させた構成により、第１の実施形態の効果に加え、次数の増分に応じて安全性を向上させることができる。また、セッション鍵ｓの埋め込み位置を変えた構成としても、第１の実施形態と同様の効果を得ることができる。
【０１５２】
（第４の実施形態）
次に、本発明の第４の実施形態について図１２を参照しながら説明する。本実施形態は、第１の実施形態の変形例であり、暗号化フェーズにおいて復号鍵の無効化が行われない場合（受信者全員が有効化対象ユーザの場合）の例であり、第３の実施形態と同様に、鍵生成多項式の次数を２ｋ−１に増加させている。以下、鍵生成フェーズ、暗号化フェーズ、復号フェーズ、追跡フェーズの順に説明する。なお、パラメータなどの定義は、特に断りの無い限り、第１の実施形態と同じものを用いる。
【０１５３】
ｑを素数とし、ｑはｐ−１を割り切り、かつ、ｑはｎ＋２ｋ−１以上であるとする。  
（鍵生成フェーズ）
鍵生成フェーズでの処理手順は、第３の実施形態と同じである。
【０１５４】
（暗号化フェーズ）
コンテンツ提供側システム１のセッション鍵生成部１３は、セッション鍵ｓをＧｑからランダムに選択する。次に、ヘッダ生成部１５は、乱数Ｒ0、Ｒ1を選択し、図１２に示すように、0≦ｉ≦ｔ-1について、以下の処理を繰り返し、Ｈ0、…、Ｈt-1を計算する（ＳＴ２−１〜ＳＴ２−８）。
【０１５５】
Ｒ0、Ｒ1のどちらか一方の値をｒｉに代入し、式（４ｂ）によりＨiを計算する（ＳＴ２−３’）。
【数１９】
2005236963.tif 000021
【０１５６】
以上の繰り返し処理により得られたＨ0、…、Ｈt-1をヘッダＨ（χ）とする（ＳＴ２−９’）。以下、前述同様に、コンテンツ提供側システム１は、ヘッダＨ（χ）とセッション鍵ｓで暗号化したコンテンツとをユーザ側システム２へ送信する（ＳＴ３〜ＳＴ４）。
【０１５７】
（復号フェーズ）
部分集合Ｕiに属するユーザｕを考える。ユーザＩＤ＝ｕのユーザ側システム２は、図８に示すように、ヘッダＨ（χ）を受信した場合、Ｈiを用いて式（８ｂ）によりセッション鍵ｓを得る。
【数２０】
2005236963.tif 000022
【０１５８】
（追跡フェーズ）
追跡アルゴリズムの手順例は、第１の実施形態と同様であり、追跡装置による追跡フェーズの動作は、図９に示されているものと同様である。但し、本実施形態は、第１の実施形態とは異なり、追跡フェーズと暗号化フェーズとの間でヘッダの生成手順が異なる。
【０１５９】
詳しくは、本実施形態は、前述した通り、暗号化フェーズにおいて全ユーザを有効化対象ユーザとするようにヘッダを生成する。一方、追跡フェーズは、有効化対象ユーザを順次無効化するようにヘッダを生成する。このように本実施形態は、追跡フェーズと暗号化フェーズとの間で有効化対象ユーザが異なることから、両フェーズ間でヘッダの生成手順が異なっている。
【０１６０】
以下、追跡フェーズにおけるヘッダの生成手順のみを説明する。なお、説明を簡単にするため、各部分集合Ｕiの要素数を全て２ｋとし、部分集合Ｕ0、…、Ｕt-1の要素は、式（１２ｂ）のようにラベル付けされているとする。
【０１６１】
Ｕ０＝｛ｕ１，…，ｕ2k｝
Ｕ１＝｛ｕ2k+1，…，ｕ4k｝
：
Ｕt-1＝｛ｕn-2k+1，…，ｕｎ｝．      …（１２ｂ）
無効化対象ユーザ集合χ＝｛ｕ1、…、ｕj｝であるとき、以下の手順によりヘッダＨ（χ）を生成させる。
【０１６２】
0≦ｉ≦ｔ-1について、以下の処理を繰り返し、Ｈ0、…、Ｈt-1を計算する。なお、記号は暗号化フェーズにおいて用いたものと同じである。
【０１６３】
ヘッダ生成部３２は、無効化対象ユーザ集合χとＵiとの積集合が空集合であるか否かを判定する。
【０１６４】
ここで、χとＵiとの積集合が空集合である場合を述べる。これは、Ｕiに属するユーザ全員が無効化対象ユーザではない場合であり、例えば、図２のＵ３が対応する。ヘッダ生成部３２は、次式（１６）に従いＨiを計算する。
【数２１】
2005236963.tif 000023
【０１６５】
無効化対象ユーザ集合χとＵiとの積集合が空集合でない場合、ヘッダ生成部３２は、χとＵiの積集合がＵiであるか否かを判定する。
【０１６６】
ここで、χとＵiの積集合がＵiでない場合を述べる。これは、Ｕiに属するユーザの少なくとも１人は無効化対象ユーザではなく、かつ少なくとも１人は無効化対象ユーザである場合、例えば、図２のＵ2に対応する。
【０１６７】
ヘッダ生成部３２は、図７に示したように、Ｕiから、無効化対象ユーザ集合χを取り除いた部分集合を｛ｘ1、…、ｘw｝とする。例えば、図２のＵ2の場合に｛ｘ1、…、ｘ１０｝＝｛３１、…、４０｝（ｗ＝１０）などとなる。
【０１６８】
次に、ヘッダ生成部３２は、ｗ＜２ｋ−１ならば、ｘw+1、…、ｘ2k-1をＺｑ−（Ｕ＋｛０｝）からランダムに選択する。なお、Ｚｑ−（Ｕ＋｛０｝）は、ＺｑからＵと｛０｝の和集合を取り除いたものを意味する。
【０１６９】
ヘッダ生成部３２は、１≦α≦２ｋ−１について、式（１７）を満たすＺｑの要素ｃ0、…、ｃ2k-1を求める。
【数２２】
2005236963.tif 000024
【０１７０】
ここで、χとＵiの積集合がＵiである場合を述べる。これは、Ｕiに属するユーザ全員が無効化対象ユーザである場合、例えば、図２のＵ1が対応する。ヘッダ生成部３２は、乱数ｚiを選択し、式（１９）に従いＨiを計算する。
【数２３】
2005236963.tif 000025
【０１７１】
以上の繰り返し処理により得られたＨ0、…、Ｈt-1をヘッダＨ（χ）とする。
【０１７２】
ここで、ヘッダは公開鍵ｅを用いて計算できるので、誰でも追跡装置３０を用いて不正ユーザを追跡することができる。
【０１７３】
上述したように本実施形態によれば、鍵生成多項式の次数を２ｋ−１に増加させた構成により、第１の実施形態の効果に加え、次数の増分に応じて安全性を向上させることができる。また、暗号化フェーズにおいて復号鍵の無効化が行われない構成としても、第１の実施形態と同様の効果を得ることができる。
【０１７４】
（第５の実施形態）
次に、本発明の第５の実施形態について説明する。本実施形態は、第３又は第４の実施例の変形例であり、分割したサブグループをリーフ（leaf；葉）に割り当てた二分木構造を用いている。具体的には、二分木構造のルート（root；根）から複数のノード（node；節）を介して複数のリーフに至るまでの各ノードにそれぞれ鍵生成多項式を割り当てる。これにより、鍵生成多項式をマルチレベルに階層化した例である。なお、以下の例では、二分木構造を用いた例を説明しているが、これに限らず、分岐数はいくつでもよいし、一つの木構造の中で分岐数が異なるノードが存在してもよいし、また、ルートからリーフへ至るノード数（レベル数）が全てのリーフについて同じである必要はなく、異なるレベルに位置するリーフが存在してもよい。第３又は第４の実施形態と同様に、鍵生成多項式の次数を２ｋ−１に増加させている。以下、鍵生成フェーズ、暗号化フェーズ、復号フェーズ、追跡フェーズの順に説明する。なお、パラメータなどの定義は、特に断りの無い限り、第１の実施形態と同じものを用いる。
【０１７５】
ｑを素数とし、ｑはｐ−１を割り切り、かつ、ｑはｎ＋２ｋ−１以上であるとする。
【０１７６】
（鍵生成フェーズ）
コンテンツ提供側システム１は、ユーザ集合Ｕを、共通要素を持たないｔ個の部分集合（サブグループ）に分割する。以下、説明を簡単にするため、ｔ＝４、４個の部分集合をＵ0、…、Ｕ3とし、｜Ｕ0｜＝｜Ｕ1｜＝｜Ｕ2｜＝｜Ｕ3｜＝２ｋとする。Ｕ0、…、Ｕ3は公開されている。公開鍵のもととなるパラメータａ0、…、ａ2k-1、ｂ0、…、ｂ2k-1、ｃ0、…、ｃ6、ｄ0、…、ｄ6、λをＺｑからランダムに選択する。パラメータｃ0、…、ｃ6及びｄ0、…、ｄ6は、それぞれ７（＝２ｔ−１）個ある。
【０１７７】
次に、コンテンツ提供側システム１は、図１４に示すように、各ノードに鍵生成多項式Ａi(x)、Ｂi(x)を割り当てる。ここで、各ノードは０から２ｔ−２までそれぞれラベル付けされている。鍵生成多項式Ａi(x)、Ｂi(x)は式（２２）のように生成する。
【数２４】
2005236963.tif 000026
【０１７８】
ｃi、ｄiは各ノードに割り当てられた鍵生成多項式に固有な係数であり、(i mod 2k)次の係数へ埋め込まれる。式（２２）は、i mod 2k = 1，j mod 2k = 2，m mod 2k = 3の場合の一例である。λはその埋め込み位置と埋め込む個数を任意に設定できる秘密定数である。但し、同一ノードにおける鍵生成多項式Ａi(x)、Ｂi(x)において、λの埋め込み位置と埋め込む個数は同一である。
【０１７９】
次に、コンテンツ提供側システム１は、公開鍵ｅを計算する。公開鍵ｅは、式（２３）のようになる。
【数２５】
2005236963.tif 000027
【０１８０】
最後にコンテンツ提供側システム１は、部分集合Ｕiに属するユーザＩＤ＝ｕの復号鍵を生成する。例えば、ユーザｕがＵ0に属している場合、Ｕ0に割り当てられたリーフｉからルートｍへの経路上の各ノードに割り当てられた鍵生成多項式Ａi(x)、Ｂi(x)、Ａj(x)、Ｂj(x)、Ａm(x)、Ｂm(x)にｘ＝ｕを代入して算出する。ここで、鍵生成多項式Ａi(x)、Ｂi(x)、Ａj(x)、Ｂj(x)、Ａm(x)、Ｂm(x)は、ユーザｕの属する部分集合Ｕ0に割り当てられ、式（２２）のように表される。
【０１８１】
（暗号化フェーズ）
コンテンツ提供側システム１のセッション鍵生成部１３は、セッション鍵ｓをＧｑからランダムに選択する。次に、ヘッダ生成部１５は、乱数Ｒ0、Ｒ1を選択する。以下、図１５を用いて説明する。始めに、ノードＮとしてルートｍを設定する（ＳＴ３１）。ノードＮを祖先に持つ全ユーザについて、次の場合（１）〜（３）のいずれかに該当するか否かを判定する（ＳＴ３２）。（１）全員無効化対象である場合。（２）全員有効化対象である場合。（３）有効化対象ユーザ数が１以上２ｋ−１以下である場合。
【０１８２】
なお、祖先の語は、ルートに限らず、親ノード，又は親の親ノード，又は親の親の親ノード．．．を意味する。
【０１８３】
ヘッダ生成部１５は、判定結果に基づいて、ヘッダＨNを計算する（ＳＴ３３）。
【０１８４】
（１）全員無効化対象である場合
ヘッダ生成部１５は、ＨNを式（２４）により計算する。なお、乱数Ｒ0、Ｒ1のいずれかの値がｒに（ＨNを計算する度にランダムに）代入される。
【数２６】
2005236963.tif 000028
【０１８５】
なお、式（２４）の例は、前述同様に、無効化のときにはノードＮを祖先に持つユーザ集合に固有の値ｃN、ｄNを正しい値とは異なる値ｚNに設定する例である。これに限らず、無効化のときには、固有の値ｃN、ｄNを削除等してもよいことも前述した通りである。
【０１８６】
（２）全員有効化対象である場合
ヘッダ生成部１５は、ＨNを式（２５）により計算する。なお、乱数Ｒ0がｒに代入される。但し、下記（３）の場合が存在しない場合、乱数Ｒ0、Ｒ1のいずれかの値がｒに（ＨNを計算する度にランダムに）代入される。
【数２７】
2005236963.tif 000029
【０１８７】
（３）有効化対象ユーザ数が１以上２ｋ−１以下である場合
ヘッダ生成部１５は、第４の実施形態の追跡フェーズにて説明した式（１７）を満たすＺｑの要素ｃ0、…、ｃ2k-1と同じ方法でＺｑの要素Ｌ0、…、Ｌ2k-1を求め、式（２６）に従いＨNを計算する。なお、乱数Ｒ1がｒに代入される。
【数２８】
2005236963.tif 000030
【０１８８】
上記（１）〜（３）のいずれにも該当しない場合（ＳＴ３２；Ｎｏ）、当該ノードＮの子ノードで、未検査の子ノードをノードＮとして設定し（ＳＴ３４）、上記処理を繰り返す。なお、ノードＮとしてリーフを設定しても構わない。
【０１８９】
全ての有効化対象ユーザ集合についてＨNを生成したか否かを判定し（ＳＴ３５）、全ての有効化対象ユーザ集合についてＨNを生成した場合、生成された（複数の）ＨNをヘッダＨ(x)とする（ＳＴ３６）。そうでない場合（ＳＴ３５；Ｎｏ）、未検査のノードで、ルートｍに最も近い、つまり最上位のノードをノードＮとして設定し（ＳＴ３７）、上記処理を繰り返す。なお、ノードＮとしてリーフを設定しても構わない。
【０１９０】
上記の例では、ヘッダサイズをより削減するために、なるべく上位のノードを選択する方法を説明したが、ノードの選択方法はこれに限らず、例えば、以下のような選択方法も可能である。図１４において、Ｕ0に属するユーザ全員が無効化対象であり、Ｕ1に属するユーザの内ｋ人が有効化対象であり、Ｕ2に属するユーザ全員が有効化対象であり、Ｕ3に属するユーザ全員が有効化対象である場合、図１５のフローチャートに従うと，ノードｊとノードｖが選択され，Ｈ(x)=(Ｈj, Ｈv)となる。ここで、ノードｊはリーフi（Ｕ0に対応）及びリーフw（Ｕ1に対応）の親ノードである。ノードｖはＵ2に対応するリーフ及びＵ3に対応するリーフの親ノードである。但し，これに限らず，ステップＳＴ３２の条件が満たされていれば、ノードをどう選択しても良い。例えば，リーフｉとリーフｗとノードｖを選択しても良い。このときＨ(x)=（Ｈi, Ｈw, Ｈv）となる。
【０１９１】
（復号フェーズ）
部分集合Ｕ0に属するユーザｕを考える。ユーザＩＤ＝ｕのユーザ側システム２は、ヘッダＨ（χ）を受信した場合、Ｈi、Ｈj、Ｈmの中でヘッダＨ（χ）に含まれているものを用いて式（２７）によりセッション鍵ｓを得る。なお、次式はＨjがヘッダＨ（χ）に含まれており、ユーザｕがＨjを用いてセッション鍵ｓを得る場合の計算式である。
【数２９】
2005236963.tif 000031
【０１９２】
（追跡フェーズ）
追跡アルゴリズムの手順例は、第１の実施形態と同様であり、追跡装置による追跡フェーズの動作は、図９に示されているものと同様である。ここで、ヘッダは公開鍵ｅを用いて計算できるので、誰でも追跡装置３０を用いて不正ユーザを追跡することができる。
【０１９３】
上述したように本実施形態によれば、鍵生成多項式をマルチレベル化させた構成により、第３又は第４の実施形態の効果に加え、鍵生成多項式のレベルに応じてヘッダサイズを削減させることができる。また、鍵生成多項式をマルチレベル化させた構成としても、第１の実施形態と同様の効果を得ることができる。
【０１９４】
上記全ての実施形態の暗号化装置、復号装置、追跡装置は、いずれも、半導体集積装置などのハードウェアとしても、ソフトウェア（（コンピュータに所定の手段を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるための）プログラム）としても、実現可能である。もちろん、ハードウェアとソフトウェアとを併用して実現することも可能である。
【０１９５】
また、プログラムとして実現する場合、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１９６】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であってもよい。
【０１９７】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行してもよい。
【０１９８】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１９９】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であってもよい。
【０２００】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。
【０２０１】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０２０２】
なお、この発明の実施の形態で例示した構成は一例であって、それ以外の構成を排除する趣旨のものではなく、例示した構成の一部を他のもので置き換えたり、例示した構成の一部を省いたり、例示した構成に別の機能あるいは要素を付加したり、それらを組み合わせたりすることなどによって得られる別の構成も可能である。また、例示した構成と論理的に等価な別の構成、例示した構成と論理的に等価な部分を含む別の構成、例示した構成の要部と論理的に等価な別の構成なども可能である。また、例示した構成と同一もしくは類似の目的を達成する別の構成、例示した構成と同一もしくは類似の効果を奏する別の構成なども可能である。  
また、この発明の実施の形態で例示した各種構成部分についての各種バリエーションは、適宜組み合わせて実施することが可能である。  
また、この発明の実施の形態は、個別装置としての発明、関連を持つ２以上の装置についての発明、システム全体としての発明、個別装置内部の構成部分についての発明、またはそれらに対応する方法の発明等、種々の観点、段階、概念またはカテゴリに係る発明を包含・内在するものである。  
従って、この発明の実施の形態に開示した内容からは、例示した構成に限定されることなく発明を抽出することができるものである。
【０２０３】
本発明は、上述した実施の形態に限定されるものではなく、その技術的範囲において種々変形して実施することができる。例えば本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０２０４】
【図１】本発明の第１の実施形態に係るコンテンツ提供側システム及びユーザ側システム等が適用されたデータ通信システムの構成を示す模式図である。
【図２】同実施形態におけるユーザ集合のサブグループを説明するための模式図である。
【図３】同実施形態におけるユーザ集合のサブグループを説明するための模式図である。
【図４】同実施形態における追跡システムの構成を示す模式図である。
【図５】同実施形態における全体動作を説明するためのフローチャートである。
【図６】同実施形態における暗号化フェーズの動作を説明するためのフローチャートである。
【図７】同実施形態に係るヘッダ生成部の処理を説明するための模式図である。
【図８】同実施形態における復号フェーズの動作を説明するためのフローチャートである。
【図９】同実施形態における追跡フェーズの動作を説明するためのフローチャートである。
【図１０】同実施形態における検査の概要を説明するための模式図である。
【図１１】同実施形態における検査の結果を説明するための模式図である。
【図１２】本発明の第４の実施形態に係るコンテンツ提供側システムにおける暗号化フェーズの動作を説明するためのフローチャートである。
【図１３】本発明の第１の実施形態に係るコンテンツ提供側システム及びユーザ側システム等が適用されたデータ通信システムの変形例を示す模式図である。
【図１４】本発明の第５の実施形態における鍵生成多項式の割当てを説明するための模式図である。
【図１５】同実施形態における暗号化フェーズの動作を説明するためのフローチャートである。
【符号の説明】
【０２０５】
１…コンテンツ提供側システム、２…ユーザ側システム、３…ネットワーク、１０…暗号化装置、１１，３１…公開鍵格納部、１２…無効化対象ユーザ情報格納部、１３…セッション鍵生成部、１４…コンテンツ暗号化部、１５，３２…ヘッダ生成部、２０…復号装置、２１…ユーザ情報格納部、２２…セッション鍵復号部、２３…コンテンツ復号部、３０…追跡装置、３３…制御部。
【図１】
2005236963.tif 000032
【図２】
2005236963.tif 000033
【図３】
2005236963.tif 000034
【図４】
2005236963.tif 000035
【図５】
2005236963.tif 000036
【図６】
2005236963.tif 000037
【図７】
2005236963.tif 000038
【図８】
2005236963.tif 000039
【図９】
2005236963.tif 000040
【図１０】
2005236963.tif 000041
【図１１】
2005236963.tif 000042
【図１２】
2005236963.tif 000043
【図１３】
2005236963.tif 000044
【図１４】
2005236963.tif 000045
【図１５】
2005236963.tif 000046