(57)【特許請求の範囲】
【請求項１】
オブジェクトから抽出された識別情報を表現する情報をもとに、対応する識別情報を求める識別情報復号装置において、
対象となるオブジェクトから抽出された、識別情報を表現する情報を入力する入力手段と、
入力された前記識別情報を表現する情報が、前記オブジェクトに対する結託攻撃によって得られたものである場合に、２から最大結託数（最大結託数は予め定められた３以上の数）までの間の任意の結託数による任意の識別情報の組合せからなる結託グループのうち、その一つの結託グループを構成する全ての識別情報を使用して前記オブジェクトに対する結託攻撃を行うことによって、入力された前記識別情報を表現する情報と同じものを生成することの可能な結託グループを求めるとともに、そのような結託グループが複数存在する場合には、それら複数の結託者グループに共通に存在する識別情報を求め、それら複数の結託者グループに共通に存在する識別情報があるときは、該識別情報を前記オブジェクトに対する結託攻撃に使用されたものであるとして出力する処理手段とを備えたことを特徴とする識別情報復号装置。
【請求項２】
オブジェクトに埋め込まれた結託耐性符号に対応する識別情報を求める識別情報復号装置において、
対象となるオブジェクトから結託耐性符号として抽出された符号を入力する入力手段と、
入力された前記符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出する検出手段と、
２から最大結託数（最大結託数は予め定められた３以上の数）までの間の任意の結託数による任意の識別情報の組合せからなる結託グループのうち、前記検出手段により検出された前記第１及び第２の境界位置情報の組に適合する結託グループを求めるとともに、適合する結託グループが複数存在する場合には、それら複数の結託者グループに共通に存在する識別情報を求め、それら複数の結託者グループに共通に存在する識別情報があるときは、該識別情報を前記オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるとして出力する処理手段とを備えたことを特徴とする識別情報復号装置。
【請求項３】
前記処理手段は、前記検出手段により検出された前記第１及び第２の境界位置情報の組に適合する結託グループが複数存在する場合に、それら複数の結託者グループに共通に存在する識別情報がないときは、その旨を示す情報を出力することを特徴とする請求項２に記載の識別情報復号装置。
【請求項４】
前記処理手段は、前記検出手段により検出された前記第１及び第２の境界位置情報の組に適合する結託グループが１つのみ存在する場合には、その結託グループを構成する全ての識別情報を、前記オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるとして出力することを特徴とする請求項２に記載の識別情報復号装置。
【請求項５】
前記処理手段は、予め作成された、前記第１及び第２の境界位置情報の組と、当該第１及び第２の境界位置情報の組に適合する１又は複数の結託グループとの対応関係を示す情報に基づいて、前記検出手段により検出された前記第１及び第２の境界位置情報の組に適合する結託グループを求めることを特徴とする請求項２に記載の識別情報復号装置。
【請求項６】
前記処理手段は、予め作成された、前記第１及び第２の境界位置情報の組と、当該第１及び第２の境界位置情報の組に適合する１つの結託グループを構成する全識別情報又は当該第１及び第２の境界位置情報の組に適合する複数の結託グループに共通に存在する全識別情報若しくはそれが存在しないことを示す情報との対応関係を示す情報に基づいて、前記検出手段により検出された前記第１及び第２の境界位置情報の組に適合する唯一の結託グループを構成する全識別情報又は該第１及び第２の境界位置情報の組に適合する複数の結託グループに共通に存在する全識別情報若しくはそれが存在しないことを示す情報を求めることを特徴とする請求項２に記載の識別情報復号装置。
【請求項７】
前記処理手段は、前記検出手段により検出された前記第１及び第２の境界位置情報の組と、各識別情報毎に定まる当該識別情報に対応する結託耐性符号を構成する複数の成分符号の各々におけるビット列のパターンが変化する境界位置に関する第３の境界位置情報の組とに基づいて、前記検出手段により検出された前記第１及び第２の境界位置情報の組に適合する結託グループを求めることを特徴とする請求項２に記載の識別情報復号装置。
【請求項８】
前記処理手段は、前記検出手段により検出された前記第１及び第２の境界位置情報の組に適合する結託グループを全て求め、該第１及び第２の境界位置情報の組に適合する結託グループが複数求められた場合に、それら複数の結託者グループに共通に存在する識別情報を求めることを特徴とする請求項２に記載の識別情報復号装置。
【請求項９】
前記処理手段は、前記検出手段により検出された前記第１及び第２の境界位置情報の組に適合する結託グループを１つ求め、該結託グループと共通する識別情報を含む結託グループのうち前記検出手段により検出された前記第１及び第２の境界位置情報の組に適合する結託グループを全て求め、それら結託者グループに共通に存在する識別情報を求め、求められた識別情報を、前記オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるとすることを特徴とする請求項２に記載の識別情報復号装置。
【請求項１０】
前記処理手段は、前記検出手段により検出された前記第１及び第２の境界位置情報の組に適合する結託グループを１つ求め、求められた結託グループに含まれる特定の識別情報を含まない結託グループであって前記検出手段により検出された前記第１及び第２の境界位置情報の組に適合するものが存在するか否かを調べ、存在しない場合に、該特定の識別情報を、前記オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるとすることを特徴とする請求項２に記載の識別情報復号装置。
【請求項１１】
前記検出手段は、前記第１の境界位置情報を、前記成分符号の上位ビット側からみたときのビット列のパターンの変化に基づいて検出し、前記第２の境界位置情報を、前記成分符号の下位ビット側からみたときのビット列のパターンの変化に基づいて検出することを特徴とする請求項２に記載の識別情報復号装置。
【請求項１２】
前記オブジェクトに埋め込まれる前記結託耐性符号を構成する前記複数の成分符号の各々は、連続する所定のビット数の１又は０のみからなるビット列を単位として、各成分符号毎に定められた数の単位ビット列を持ち、かつ、上位ビット側から、０のみからなる単位ビット列を所定の個数連接し続けて１のみからなる単位ビット列を所定の個数連接してなる符号又は０のみからなる単位ビット列を所定の個数連接してなる符号若しくは１のみからなる単位ビット列を所定の個数連接してなる符号であり、かつ、前記結託耐性符号に対応する識別情報に応じて該符号における０のみからなる単位ビット列と１のみからなる単位ビット列とが隣接する位置又は該符号が１のみからなる単位ビット列のみからなること若しくは該符号が０のみからなる単位ビット列のみからなることが定まるものであり、
前記検出手段は、０のみからなる単位ビット列と１を含む単位ビット列とが隣接する位置が存在する場合には、該位置を示す整数値を、前記第１の境界位置情報とし、１のみからなる単位ビット列と０を含む単位ビット列とが隣接する位置が存在する場合には、該位置を示す整数値を、前記第２の境界位置情報として求め、最上位ビット側の単位ビット列が０と１の混在する単位ビット列である場合には、整数値０を前記第１の境界位置情報とし、最下位ビット側の単位ビット列が０と１の混在する単位ビット列である場合には、当該成分符号の持つ単位ビット列の数より１減じた値を、前記第２の境界位置情報とすることを特徴とする請求項１１に記載の識別情報復号装置。
【請求項１３】
前記検出手段は、前記成分符号が０のみからなる符号である場合には、前記成分符号の持つ単位ビット列の数より１減じた値を前記第１及び第２の境界位置情報とし、前記成分符号が１のみからなる符号である場合には、整数値０を前記第１及び第２の境界位置情報とすることを特徴とする請求項１２に記載の識別情報復号装置。
【請求項１４】
最大結託数と、結託耐性符号を構成する成分符号の個数と、識別情報の範囲との間に、一定の制約を設けたことを特徴とする請求項２に記載の識別情報復号装置。
【請求項１５】
最大結託数をｃとし、結託耐性符号を構成する成分符号の個数をｄとし、ｐ0，ｐ1，…，ｐd-1を互いに素の整数（ただし、０＜ｐ0＜ｐ1＜…＜ｐd-1とする）とし、識別情報Ｖに対する第ｉ番目の成分符号におけるビット列のパターンが変化する境界位置を決定する整数値を、Ｖ  ｍｏｄ  ｐi-1とし、識別情報の範囲を０からｐ0×ｐ1×…×ｐk-1−１までの範囲の整数とした場合に、ｄとｃとｋとの関係を、ｄ＞（ｃ2／２）・（ｋ−１）としたことを特徴とする請求項２に記載の識別情報復号装置。
【請求項１６】
前記オブジェクトから前記符号を抽出する手段を更に備えたことを特徴とする請求項１または２に記載の識別情報復号装置。
【請求項１７】
前記オブジェクトは、デジタルコンテンツの複製物であることを特徴とする請求項１ないし１６のいずれか１項に記載の識別情報復号装置。
【請求項１８】
前記オブジェクトは、デジタルコンテンツの複製物であり、前記結託耐性符号は、電子透かしによって前記デジタルコンテンツの複製物に埋め込まれたものであることを特徴とする請求項２ないし１６のいずれか１項に記載の識別情報復号装置。
【請求項１９】
前記オブジェクトは、デジタルコンテンツの複製物であり、前記結託攻撃は、複数の前記デジタルコンテンツの複製物をビット単位で比較したときに得られる相違部分に対して、所定の方法で改変を加えるものであることを特徴とする請求項２ないし１６のいずれか１項に記載の識別情報復号装置。
【請求項２０】
前記オブジェクトは、化学物質製品であることを特徴とする請求項１ないし１６のいずれか１項に記載の識別情報復号装置。
【請求項２１】
前記オブジェクトは、化学物質製品であり、前記結託耐性符号は、前記化学物質製品の特定部位の構造を変化させることによって該化学物質製品に埋め込まれたものであることを特徴とする請求項２ないし１６のいずれか１項に記載の識別情報復号装置。
【請求項２２】
対象となるオブジェクトに識別情報に対応する結託耐性符号を埋め込む識別情報埋込装置において、
前記オブジェクトに対応するユーザを特定する識別情報に対応する、複数の成分符号を連結してなる結託耐性符号を生成する生成手段と、
生成された前記結託耐性符号を前記複製物に埋め込む埋込手段とを備え、
前記生成手段により前記結託耐性符号を生成するにあたって、追跡アルゴリズムにて想定する最大結託数をｃとし、前記結託耐性符号を構成する成分符号の個数をｄとし、ｐ0，ｐ1，…，ｐd-1を互いに素の整数（ただし、０＜ｐ0＜ｐ1＜…＜ｐd-1とする）とし、識別情報Ｖに対する第ｉ番目の成分符号におけるビット列のパターンが変化する境界位置を決定する整数値を、Ｖ  ｍｏｄ  ｐi-1とし、識別情報の範囲を０からｐ0×ｐ1×…×ｐk-1−１までの範囲の整数とした場合に、ｄとｃとｋとの関係を、ｄ＞（ｃ2／２）・（ｋ−１）とし、
前記追跡アルゴリズムは、対象となるオブジェクトから結託耐性符号として抽出された符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出し、２から最大結託数（最大結託数は予め定められた３以上の数）までの間の任意の結託数による任意の識別情報の組合せからなる結託グループのうち、該検出された第１及び第２の境界位置情報の組に適合する結託グループを求めるとともに、適合する結託グループが複数存在する場合には、それら複数の結託者グループに共通に存在する識別情報を求め、それら複数の結託者グループに共通に存在する識別情報があるときは、該識別情報を該オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるとするものであることを特徴とする識別情報埋込装置。
【請求項２３】
前記結託耐性符号を構成する第ｉ番目の前記成分符号は、連続する所定のビット数の１又は０のみからなるビット列を単位として、上位ビット側から、まず前記整数値Ｖ  ｍｏｄ  ｐi-1と同じ個数の０のみからなる単位ビット列を連接し、続けて前記整数値ｐi-1より１減じ更に前記整数値Ｖ  ｍｏｄ  ｐi-1を減じた値と同じ個数の１のみからなるビット列を連接してなる符号であることを特徴とする請求項２２に記載の識別情報埋込装置。
【請求項２４】
前記オブジェクトは、デジタルコンテンツの複製物であることを特徴とする請求項２２または２３のいずれか１項に記載の識別情報埋込装置。
【請求項２５】
前記オブジェクトは、化学物質製品であることを特徴とする請求項２２または２３のいずれか１項に記載の識別情報埋込装置。
【請求項２６】
オブジェクトから抽出された識別情報を表現する情報をもとに、対応する識別情報を求める識別情報復号方法において、
対象となるオブジェクトから抽出された、識別情報を表現する情報を入力する入力ステップと、
入力された前記識別情報を表現する情報が、前記オブジェクトに対する結託攻撃によって得られたものである場合に、２から最大結託数（最大結託数は予め定められた３以上の数）までの間の任意の結託数による任意の識別情報の組合せからなる結託グループのうち、その一つの結託グループを構成する全ての識別情報を使用して前記オブジェクトに対する結託攻撃を行うことによって、入力された前記識別情報を表現する情報と同じものを生成することの可能な結託グループを求めるとともに、そのような結託グループが複数存在する場合には、それら複数の結託者グループに共通に存在する識別情報を求め、それら複数の結託者グループに共通に存在する識別情報があるときは、該識別情報を前記オブジェクトに対する結託攻撃に使用されたものであるとして出力する処理ステップとを有することを特徴とする識別情報復号方法。
【請求項２７】
オブジェクトに埋め込まれた結託耐性符号に対応する識別情報を求める識別情報復号方法において、
対象となるオブジェクトから結託耐性符号として抽出された符号を入力する入力ステップと、
入力された前記符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出する検出ステップと、
２から最大結託数（最大結託数は予め定められた３以上の数）までの間の任意の結託数による任意の識別情報の組合せからなる結託グループのうち、前記検出ステップにて検出された前記第１及び第２の境界位置情報の組に適合する結託グループを求めるとともに、適合する結託グループが複数存在する場合には、それら複数の結託者グループに共通に存在する識別情報を求める処理ステップとを有することを特徴とする識別情報復号方法。
【請求項２８】
対象となるオブジェクトに識別情報に対応する結託耐性符号を埋め込む識別情報埋込方法において、
前記オブジェクトに対応するユーザを特定する識別情報に対応する、複数の成分符号を連結してなる結託耐性符号を生成する生成ステップと、
生成された前記結託耐性符号を前記複製物に埋め込む埋込ステップとを有し、
前記生成ステップにて前記結託耐性符号を生成するにあたって、追跡アルゴリズムにて想定する最大結託数をｃとし、前記結託耐性符号を構成する成分符号の個数をｄとし、ｐ0，ｐ1，…，ｐd-1を互いに素の整数（ただし、０＜ｐ0＜ｐ1＜…＜ｐd-1とする）とし、識別情報Ｖに対する第ｉ番目の成分符号におけるビット列のパターンが変化する境界位置を決定する整数値を、Ｖ ｍｏｄ ｐi-1とし、識別情報の範囲を０からｐ0×ｐ1×…×ｐk-1−１までの範囲の整数とした場合に、ｄとｃとｋとの関係を、ｄ＞（ｃ2／２）・（ｋ−１）とし、
前記追跡アルゴリズムは、対象となるオブジェクトから結託耐性符号として抽出された符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出し、２から最大結託数（最大結託数は予め定められた３以上の数）までの間の任意の結託数による任意の識別情報の組合せからなる結託グループのうち、該検出された第１及び第２の境界位置情報の組に適合する結託グループを求めるとともに、適合する結託グループが複数存在する場合には、それら複数の結託者グループに共通に存在する識別情報を求め、それら複数の結託者グループに共通に存在する識別情報があるときは、該識別情報を該オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるとするものであることを特徴とする識別情報埋込方法。
【請求項２９】
オブジェクトから抽出された識別情報を表現する情報をもとに、対応する識別情報を求める識別情報復号装置としてコンピュータを機能させるためのプログラムであって、
対象となるオブジェクトから抽出された、識別情報を表現する情報を入力する入力機能と、
入力された前記識別情報を表現する情報が、前記オブジェクトに対する結託攻撃によって得られたものである場合に、２から最大結託数（最大結託数は予め定められた３以上の数）までの間の任意の結託数による任意の識別情報の組合せからなる結託グループのうち、その一つの結託グループを構成する全ての識別情報を使用して前記オブジェクトに対する結託攻撃を行うことによって、入力された前記識別情報を表現する情報と同じものを生成することの可能な結託グループを求めるとともに、そのような結託グループが複数存在する場合には、それら複数の結託者グループに共通に存在する識別情報を求め、それら複数の結託者グループに共通に存在する識別情報があるときは、該識別情報を前記オブジェクトに対する結託攻撃に使用されたものであるとして出力する処理機能とをコンピュータに実現させるためのプログラム。
【請求項３０】
オブジェクトに埋め込まれた結託耐性符号に対応する識別情報を求める識別情報復号装置としてコンピュータを機能させるためのプログラムであって、
対象となるオブジェクトから結託耐性符号として抽出された符号を入力する入力機能と、
入力された前記符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出する検出機能と、
２から最大結託数（最大結託数は予め定められた３以上の数）までの間の任意の結託数による任意の識別情報の組合せからなる結託グループのうち、前記検出機能により検出された前記第１及び第２の境界位置情報の組に適合する結託グループを求めるとともに、適合する結託グループが複数存在する場合には、それら複数の結託者グループに共通に存在する識別情報を求める処理機能とをコンピュータに実現させるためのプログラム。
【請求項３１】
対象となるオブジェクトに識別情報に対応する結託耐性符号を埋め込む識別情報埋込装置としてコンピュータを機能させるためのプログラムであって、
前記オブジェクトに対応するユーザを特定する識別情報に対応する、複数の成分符号を連結してなる結託耐性符号を生成する生成機能と、
生成された前記結託耐性符号を前記複製物に埋め込む埋込機能とをコンピュータに実現させるためのものであるとともに、
前記生成機能にて前記結託耐性符号を生成するにあたって、追跡アルゴリズムにて想定する最大結託数をｃとし、前記結託耐性符号を構成する成分符号の個数をｄとし、ｐ0，ｐ1，…，ｐd-1を互いに素の整数（ただし、０＜ｐ0＜ｐ1＜…＜ｐd-1とする）とし、識別情報Ｖに対する第ｉ番目の成分符号におけるビット列のパターンが変化する境界位置を決定する整数値を、Ｖ ｍｏｄ ｐi-1とし、識別情報の範囲を０からｐ0×ｐ1×…×ｐk-1−１までの範囲の整数とした場合に、ｄとｃとｋとの関係を、ｄ＞（ｃ2／２）・（ｋ−１）とし、
前記追跡アルゴリズムは、対象となるオブジェクトから結託耐性符号として抽出された符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出し、２から最大結託数（最大結託数は予め定められた３以上の数）までの間の任意の結託数による任意の識別情報の組合せからなる結託グループのうち、該検出された第１及び第２の境界位置情報の組に適合する結託グループを求めるとともに、適合する結託グループが複数存在する場合には、それら複数の結託者グループに共通に存在する識別情報を求め、それら複数の結託者グループに共通に存在する識別情報があるときは、該識別情報を該オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるとするものであることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、識別情報に対応する結託耐性符号を生成しデジタルコンテンツの複製物などのオブジェクトに埋め込む識別情報埋込装置、識別情報埋込方法及びプログラム、並びに識別情報に対応する結託耐性符号の埋め込まれたデジタルコンテンツの複製物などのオブジェクトに対する結託攻撃に用いられたオブジェクトに埋め込まれていた結託耐性符号に対応する識別情報を求める識別情報復号装置、識別情報復号方法及びプログラムに関する。
【０００２】
【従来の技術】
デジタルコンテンツ（例えば、静止画、動画、音声、音楽等）は、多数のデジタルデータで構成された構造を持つ。そして、その構造の中には、データを変更しても、当該デジタルコンテンツの作品の同一性あるいは経済的価値を保持できる部分がある。そのような許容された範囲内のデータを変更するによって、デジタルコンテンツに、種々の情報を埋め込むことができる。このような技術は、電子透かしと呼ばれる。
【０００３】
電子透かし技術によって、デジタルコンテンツに、様々な透かし情報（例えば、コンテンツの著作権者やユーザを識別する情報、著作権者の権利情報、コンテンツの利用条件、その利用時に必要な秘密情報、コピー制御情報等、あるいはそれらを組み合わせたものなど）を、様々な目的（例えば、利用制御、コピー制御を含む著作権保護、二次利用の促進等）で埋め込み、検出・利用することができる。
【０００４】
ここでは、例えば同一のデジタルコンテンツを多数のユーザを対象として配給するときに適用される技術として、デジタルコンテンツの複製物に、当該複製物を個々に識別するための情報（例えば、ユーザＩＤに一意に対応する透かし情報）を埋め込む場合を考える。
【０００５】
デジタルコンテンツの複製物に固有の識別情報（に対応する符号）を埋め込む手法は、そのデジタルコンテンツの複製物が更に複製されて海賊版として出回ったときに、該海賊版から識別情報を検出することによって流出元ユーザを特定することができることから、デジタルコンテンツの違法コピーに対する事前の抑制として機能するとともに、著作権侵害が発生したときの事後の救済にも役立つことになる。
【０００６】
また、あるユーザがデジタルコンテンツの複製物に埋め込まれた識別情報を無効にするためには、ユーザにはどの部分が識別情報（に対応する符号）を構成するビットであるか分からないので、当該デジタルコンテンツの複製物に相当の改変を加える必要があり、そうすると、当該デジタルコンテンツの経済的価値を損なってしまうので、違法コピーの動機付けを奪うことができる。
【０００７】
このような状況において違法コピーを可能ならしめる方法として出現したのが、「結託攻撃（ｃｏｌｌｕｓｉｏｎ  ａｔｔａｃｋ）」である。
【０００８】
結託攻撃は、異なる複製物には異なる識別情報が埋めこまれていることを利用するものであり、例えば、複数人で複製物を持ち寄って、それらをビット単位で比較することによって、デジタルデータの値が異なる部分を見つけ出し、その部分を改ざん（例えば、多数決、少数決、ランダマイズ等）することによって、識別情報を改ざん、消失させるという方法である（なお、具体的な比較操作は行わず、コンテンツ間で画素値を平均化するなどの操作を行って、同様の結果を得る場合もある）。
【０００９】
例えば簡単な例で示すと、Ａ氏、Ｂ氏、Ｃ氏の複製物にそれぞれ、
Ａ  ：  ００…００…
Ｂ  ：  ００…１１…
Ｃ  ：  １１…００…
という識別情報（に対応する符号）が埋め込まれていた場合に、例えば、
１０…０１…
という、Ａ氏、Ｂ氏、Ｃ氏のいずれとも異なる識別情報（に対応する符号）が埋め込まれたコンテンツを出現させることができてしまう。
【００１０】
そこで、結託攻撃に対する耐性、すなわち結託攻撃を受けても結託者の全部または一部を特定できるような性質を持つ符号（以下、結託耐性符号と呼ぶ）を電子透かしとして埋め込む方法および該結託耐性符号に基づく追跡アルゴリズム（ｔｒａｃｉｎｇ  ａｌｇｏｒｉｔｈｍ；結託攻撃に用いられたコンテンツに埋め込まれた識別番号を特定し、結託者のユーザＩＤを特定するためのアルゴリズム）が種々提案されている。例えば、ｃ−ｓｅｃｕｒｅ  符号(D. Boneh and J. Shaw,“Collusion-Secure Fingerprinting for Digital Data,” CRYPTO’95, 180-189, 1995.)やｃ−ｓｅｃｕｒｅ  ＣＲＴ  符号(Hirofumi Muratani,“A Collusion-Secure Fingerprinting Code Reduced by Chinese Remaindering and its Random-Error Resilience”,Information Hiding Workshop 2001, 301-315, 2001.)がその例である。
【００１１】
【発明が解決しようとする課題】
結託攻撃に対する耐性をより強くする、すなわち結託者を特定できなくなる結託数の上限数をより増やすためには、コンテンツに埋め込む符号長をより長くする必要があり、一方、コンテンツに埋め込む符号長にも制限があるので、この種の結託耐性符号およびその結託耐性符号に基づく追跡アルゴリズムでは、符号長を削減するために、結託攻撃に利用された複製物の数に上限を設けている（なお、ｃ−ｓｅｃｕｒｅのｃは、高々ｃ個までの複製物を用いた結託攻撃に対して有効であるという意味である）。もし結託攻撃が許容されている個数を越える数の複製物を用いて行われた場合には、追跡アルゴリズムは、結託攻撃に関与した複製物の識別番号として、誤って、結託攻撃に関与したのではない複製物の識別番号を出力し、結託者でないものが結託者として特定されてしまう、という誤判定が発生することがあり得る。
【００１２】
誤判定の確率を下げるためには、現実的に結託者が準備することができそうな複製物の個数を想像し、その個数以上の許容個数となるように結託耐性符号を設計するより他なく、どうしても、大きな許容個数を設定することになってしまい、その結果、符号長も大きくなってしまうという問題点がある。
【００１３】
本発明は、上記事情を考慮してなされたもので、結託耐性符号による識別情報が埋め込まれたオブジェクト（例えば、デジタルコンテンツの複製物）に対する結託攻撃に用いられたオブジェクトの識別情報を、より短い符号長により推測可能とした識別情報復号装置及び識別情報復号方法、識別情報埋込装置及び識別情報埋込方法、並びにプログラムを提供することを目的とする。
【００１４】
【課題を解決するための手段】
本発明は、オブジェクトから抽出された識別情報を表現する情報をもとに、対応する識別情報を求める識別情報復号装置において、対象となるオブジェクトから抽出された、識別情報を表現する情報を入力する入力手段と、入力された前記識別情報を表現する情報が、前記オブジェクトに対する結託攻撃によって得られたものである場合に、２から最大結託数（最大結託数は予め定められた３以上の数）までの間の任意の結託数による任意の識別情報の組合せからなる結託グループのうち、その一つの結託グループを構成する全ての識別情報を使用して前記オブジェクトに対する結託攻撃を行うことによって、入力された前記識別情報を表現する情報と同じものを生成することの可能な結託グループを求めるとともに、そのような結託グループが複数存在する場合には、それら複数の結託者グループに共通に存在する識別情報を求め、それら複数の結託者グループに共通に存在する識別情報があるときは、該識別情報を前記オブジェクトに対する結託攻撃に使用されたものであるとして出力する処理手段とを備えたことを特徴とする。
また、本発明は、オブジェクトに埋め込まれた結託耐性符号に対応する識別情報を求める識別情報復号装置において、対象となるオブジェクトから結託耐性符号として抽出された符号を入力する入力手段と、入力された前記符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出する検出手段と、２から最大結託数（最大結託数は予め定められた３以上の数）までの間の任意の結託数による任意の識別情報の組合せからなる結託グループのうち、前記検出手段により検出された前記第１及び第２の境界位置情報の組に適合する結託グループを求めるとともに、適合する結託グループが複数存在する場合には、それら複数の結託者グループに共通に存在する識別情報を求め、それら複数の結託者グループに共通に存在する識別情報があるときは、該識別情報を前記オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるとして出力する処理手段とを備えたことを特徴とする。
また、本発明は、対象となるオブジェクトに識別情報に対応する結託耐性符号を埋め込む識別情報埋込装置において、前記オブジェクトに対応するユーザを特定する識別情報に対応する、複数の成分符号を連結してなる結託耐性符号を生成する生成手段と、生成された前記結託耐性符号を前記複製物に埋め込む埋込手段とを備え、前記生成手段により前記結託耐性符号を生成するにあたって、追跡アルゴリズムにて想定する最大結託数をｃとし、前記結託耐性符号を構成する成分符号の個数をｄとし、ｐ0，ｐ1，…，ｐd-1を互いに素の整数（ただし、０＜ｐ0＜ｐ1＜…＜ｐd-1とする）とし、識別情報Ｖに対する第ｉ番目の成分符号におけるビット列のパターンが変化する境界位置を決定する整数値を、Ｖ  ｍｏｄ  ｐi-1とし、識別情報の範囲を０からｐ0×ｐ1×…×ｐk-1−１までの範囲の整数とした場合に、ｄとｃとｋとの関係を、ｄ＞（ｃ2／２）・（ｋ−１）とし、前記追跡アルゴリズムは、対象となるオブジェクトから結託耐性符号として抽出された符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出し、２から最大結託数（最大結託数は予め定められた３以上の数）までの間の任意の結託数による任意の識別情報の組合せからなる結託グループのうち、該検出された第１及び第２の境界位置情報の組に適合する結託グループを求めるとともに、適合する結託グループが複数存在する場合には、それら複数の結託者グループに共通に存在する識別情報を求め、それら複数の結託者グループに共通に存在する識別情報があるときは、該識別情報を該オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるとするものであることを特徴とする。
【００２２】
なお、装置に係る本発明は方法に係る発明としても成立し、方法に係る本発明は装置に係る発明としても成立する。
また、装置または方法に係る本発明は、コンピュータに当該発明に相当する手順を実行させるための（あるいはコンピュータを当該発明に相当する手段として機能させるための、あるいはコンピュータに当該発明に相当する機能を実現させるための）プログラムとしても成立し、該プログラムを記録したコンピュータ読取り可能な記録媒体としても成立する。
【００２３】
本発明によれば、識別情報に対応する結託耐性符号の埋め込まれたデジタルコンテンツの複製物に対する結託攻撃に用いられたデジタルコンテンツに埋め込まれていた結託耐性符号に対応する識別情報を、（例えば同じ誤検出率を考えたときに）より短い符号長により推測することができる。
【００２４】
また、従来はある確率でもって正しい追跡を行うという確率論的な追跡を行ったいたのに対して、確率論的ではなく、確実な追跡を行うことを可能にし、かつ、従来よりも符号長をより短く（成分符号の個数（Ｍ）をより少なく）することを可能にすることができる。
【００２５】
【発明の実施の形態】
以下、図面を参照しながら発明の実施の形態を説明する。
【００２６】
まず、同一のデジタルコンテンツの複製物（例えば、静止画、動画、音声、音楽等）の各々に対して、当該複製物ごとに異なる識別情報を透かし情報として埋め込み、追跡する場合について説明する。以下では、識別情報として、当該複製物に対応するユーザすなわち当該複製物を利用することになるユーザ（例えば、当該複製物を記録媒体若しくは通信媒体を媒介として譲渡し又は貸し渡すユーザ）のユーザ識別子（ユーザＩＤ）を用いる場合を主として説明するが、ユーザＩＤに対して所定の変換を施したものを識別情報としてもよいし、ユーザＩＤ以外の情報又はこれを変換したものを識別情報としてもよい。なお、ユーザＩＤには、利用の日時や利用場所等の情報を含めても良い。
【００２７】
もちろん、デジタルコンテンツの複製物に対して、さらに、その他の様々な透かし情報（例えば、コンテンツの著作権者に関する情報、著作権等の権利に関する情報、コンテンツの利用条件に関する情報、その利用時に必要な秘密情報、コピー制御情報等、あるいはそれらを組み合わせたものなど）が様々な目的（例えば、利用制御、コピー制御を含む著作権保護、二次利用の促進等）で埋め込まれ、検出されてもよいが、その他の透かし情報を利用する場合における当該その他の透かし情報に関係する部分の構成は任意である。
【００２８】
以下で示す構成図は、装置の機能ブロック図としても成立し、また、ソフトウェア（プログラム）の機能モジュール図あるいは手順図としても成立するものである。
【００２９】
図１に、本発明の実施の形態に係る電子透かし埋込装置と電子透かし解析装置が適用されるシステムの概念図を示す。
【００３０】
電子透かし埋込装置１と電子透かし解析装置２は、例えば、コンテンツ提供側に備えられ、管理される。
また、例えば、電子透かし埋込装置１は、ユーザ側に備えられ（例えば、コンテンツを利用するためのユーザ・システム（例えば、計算機システムや専用機器等に接続されあるいは組み込まれるなど）、電子透かし解析装置２は、コンテンツ提供側に備えられるようにしてもよい。
デジタルコンテンツの複製物への透かし情報の埋め込みは、前者の場合、該複製物がユーザへ渡されるのに先だって行われ、後者の場合、該複製物がユーザの利用に供されるのに先だって行われることになる。
【００３１】
電子透かし埋込装置１においてデジタルコンテンツに所望の透かしデータを埋め込む方法や、電子透かし解析装置２においてデジタルコンテンツから該透かしデータ自体を取り出す方法は、どのような方法であってもよい（例えば、“松井甲子雄著、「電子透かしの基礎」、森北出版、１９９８年”等参照）。
電子透かし埋込装置１は、ソフトウェア（プログラム）としてもハードウェアとしても実現可能である。同様に、電子透かし解析装置２は、ソフトウェア（プログラム）としてもハードウェアとしても実現可能である。また、電子透かし埋込装置１および電子透かし解析装置２をコンテンツ提供側で用いる場合には、それらを一体化して実現することも可能である。
【００３２】
図２に、電子透かし埋込装置１の構成例を示す。この電子透かし埋込装置１は、埋め込むべき識別情報（例えば、ユーザＩＤ）に対応する結託耐性符号を生成する符号生成部１１と、生成された結託耐性符号（埋め込み符号）を対象コンテンツに埋め込む符号埋込部１２とから構成される。
【００３３】
電子透かし埋込装置１は、対象コンテンツと、これに埋め込むべき識別情報（例えば、対象ユーザのユーザＩＤ）とが与えられると、該識別情報に対応する結託耐性符号を生成し、該結託耐性符号が埋め込まれたコンテンツを、該識別情報に対応する複製物（例えば、該ユーザＩＤのユーザ向けの複製物）として出力する。他の透かし情報を利用する場合には、その際に、必要に応じて他の透かし情報が埋め込まれる。
【００３４】
なお、例えば、識別情報≠ユーザＩＤであって、かつ、ユーザＩＤが与えられるような場合には、与えられたユーザＩＤを識別情報に変換する、などの前処理を行う。
【００３５】
電子透かし埋込装置１により得られた当該識別情報に対応するコンテンツの複製物は、記憶媒体や通信媒体などを媒介とした流通経路３を経てそれぞれ流通する。複数の複製物を用いた結託攻撃は、この流通経路３にて行われる。
【００３６】
図３に、電子透かし解析装置２の構成例を示す。
【００３７】
図３に示されるように、電子透かし解析装置２は、符号抽出部２１と、復号部２２とを備えている。
【００３８】
符号抽出部２１は、検出対象となるコンテンツの複製物から埋め込み符号を抽出する（結託攻撃の有無にかかわらず、結託攻撃が無かった場合の結託耐性符号が埋め込まれているものとして符号を抽出する）。実際には、埋め込まれた結託耐性符号が抽出される場合だけでなく、結託攻撃が施されて改ざんされたものが抽出される場合もある。
【００３９】
復号部２２は、抽出された符号に対して、後述する追跡アルゴリズムを実行することによって、結託攻撃がなかったこと、または結託攻撃に用いられたであろう複製物に埋め込まれていた結託耐性符号に対応する１又は複数の識別情報（例えば、ユーザＩＤ）を特定（あるいは推測）する。
【００４０】
なお、例えば、識別情報≠ユーザＩＤであって、ユーザＩＤを求める必要があるような場合には、特定された識別情報を、さらに、ユーザＩＤに変換する、などの後処理を行う。
【００４１】
以下では、電子透かし埋込装置１についてより詳細に説明する。
【００４２】
ここでは、識別情報＝ユーザＩＤの場合を例にとって説明する（したがって、以下において、識別情報＝ユーザＩＤとして説明している場合には、ユーザＩＤは一般的には識別情報のことを意味している）。
【００４３】
図４に、概略的な手順の一例を示す。
【００４４】
符号生成部１１は、まず、対象複製物に、埋め込むべき識別情報（すなわち、ここでは、ユーザＩＤ）に対応する、Ｍ（Ｍは複数）個の整数Ａ（１）、Ａ（２）、…、Ａ（Ｍ）を求める（ステップＳ１０１）。該Ｍ個の整数は、予め求めて記憶しておく方法と、必要時に求める方法とがある。
【００４５】
整数Ａ（１）、Ａ（２）、…、Ａ（Ｍ）の設定の仕方は、様々な方法がある。
【００４６】
例えば、各ｉ（ｉ＝１〜Ｍ）におけるそれぞれの整数Ａ（ｉ）が、０〜Ｎ（ｉ）−１のいずれかの値を取るようにしてもよい。ここで、Ｎ（１）、Ｎ（２）、…、Ｎ（Ｍ）は、例えば、予め定められた相互に異なる正整数である（本実施形態では、互いに素の関係にある整数とするのが望ましい）。なお、Ｎ（１）＜Ｎ（２）＜…＜Ｎ（Ｍ）としてもよい。
【００４７】
その際、ユーザＩＤに対応するＭ個の整数Ａ（ｉ）の各々には、０〜Ｎ（ｉ）−１の範囲でランダムに値を割り当てる方法と、０〜Ｎ（ｉ）−１の範囲で一定の規則に従って値を割り当てる方法とがある。また、いずれの場合についても、各ユーザＩＤには、互いにＡ（１）、Ａ（２）、…、Ａ（Ｍ）のうちの少なくとも一つが相違するように、Ｍ個の整数の組を排他的に割り当てる方法と、Ａ（１）、Ａ（２）、…、Ａ（Ｍ）のすべてを同一とするＭ個の整数の組を複数のユーザＩＤに重複に割当てることを許す方法とがある（本実施形態では、前者を採用して、Ｍ個の整数の組から唯一の識別情報が特定できるようにするのが望ましい）。
【００４８】
排他的に値を割り当てる方法には、例えば、ユーザＩＤの値として、０〜Ｎ（１）×Ｎ（２）×…×Ｎ（Ｍ）−１の範囲の整数の一部を使用するものとし、Ｍ個の整数Ａ（ｉ）の各々について、対象ユーザＩＤをＮ（ｉ）で割ったときの余りを、該ユーザＩＤに対応するＡ（ｉ）の値とする方法がある。本実施形態では、これらＭ個の数Ｎ（１）、Ｎ（２）、…、Ｎ（Ｍ）は、互いに素の関係にある整数とするのが望ましい（なお、Ｎ（１）＜Ｎ（２）＜…＜Ｎ（Ｍ）とする）。なお、この場合の識別情報（＝Ｖとする）に対応するＭ個の整数の組｛Ａ（１）＝Ｖ  ｍｏｄ  Ｎ（１）、Ａ（２）＝Ｖ  ｍｏｄ  Ｎ（２）、…、Ａ（Ｍ）＝Ｖｍｏｄ  Ｎ（Ｍ）｝が、詳しくは後述する基準剰余の組｛ｒ(0)1、ｒ(0)2、…、ｒ(0)M｝に相当する。また、この場合に、詳しくは後述するように、想定する最大の結託者数ｃと、整数の個数Ｍ（＝成分符号の個数）と、使用する識別情報の範囲（例えば、０から始まる連番）との間に、一定の制約を与えると好ましい。
【００４９】
なお、上記の代わりに、例えば、識別情報≠ユーザＩＤのようにする場合に、ユーザＩＤに所定の変換を施すことによって、その変換値＝識別情報が０〜Ｎ（１）×Ｎ（２）×…×Ｎ（Ｍ）−１のうちの使用すべき範囲内の整数になるような所定の変換を用意し、対象ユーザＩＤに対して該所定の変換を施して得た識別情報をＮ（ｉ）で割ったときの余りを、該ユーザＩＤに対応する識別情報に対応するＡ（ｉ）の値とする方法もある（この場合、復号部２２では、まず、ユーザＩＤに対応する識別情報が得られるので、ユーザＩＤを求める必要があるならば、復号部２２等において、得られた当該識別情報に上記の所定の変換に対する逆変換を施して、対応するユーザＩＤを求めることになる）。
【００５０】
また、ここでは、コンテンツの複製物に、ユーザＩＤに対応する符号を埋め込む場合を例にとって説明しているが、その代わりに、例えば、コンテンツの複製物の複製物ＩＤとそのユーザを特定するための情報（例えば、ユーザ名、あるいはユーザＩＤ等）との対応を示す情報を所定の記憶装置に記録しておき、識別情報＝複製物ＩＤとして、コンテンツの複製物に、そのユーザのユーザＩＤに対応する複製物ＩＤに対応する符号を埋め込むようにしてもよい（この場合、復号部２２では、まず、ユーザＩＤに対応する複製物ＩＤが得られるので、ユーザＩＤを求める必要があるならば、復号部２２等において、得られた当該複製物ＩＤから、対応するユーザＩＤを求めることになる）。
また、例えば、上記のようにユーザＩＤに対応する複製物ＩＤに対応する符号を埋め込むようにする場合であって、かつ、識別情報≠複製物ＩＤのようにする場合に、ユーザＩＤに対応する複製物ＩＤに所定の変換を施して得た識別情報をＮ（ｉ）で割ったときの余りを、該ユーザＩＤに対応する複製物ＩＤに対応する識別情報に対応するＡ（ｉ）の値とする方法もある（この場合、復号部２２では、まず、識別情報が得られるので、ユーザＩＤを求める必要があるならば、復号部２２等において、得られた当該識別情報に上記の所定の変換に対する逆変換を施して、対応する複製物ＩＤを求め、該複製物ＩＤからユーザＩＤを求めることになる）。
【００５１】
さて、次に、符号生成部１１は、対象複製物に埋め込むべきユーザＩＤ（識別情報）に対応する、Ｍ個の整数Ａ（１），Ａ（２），…，Ａ（Ｍ）から、該ユーザＩＤに対応する結託耐性符号を生成する（ステップＳ１０２）。各ユーザＩＤに対応する結託耐性符号は、予め生成して記憶しておく方法と、必要時に生成する方法とがある。
【００５２】
各ユーザＩＤに対応する結託耐性符号は、該ユーザＩＤに対応するＭ個の整数Ａ（１），Ａ（２），…，Ａ（Ｍ）の各々について、対応する成分符号Ｗ（１），Ｗ（２），…，Ｗ（Ｍ）を求め、それらを連結（連接）することによって生成する。
【００５３】
整数Ａ（ｉ）に対応する成分符号Ｗ（ｉ）としては、例えば、Γ0(ｎ，ｄ)符号（１または０のみからなる連続したｄビットを一つの単位Ｂ（ｊ）とし、Ｂ（０）〜Ｂ（ｎ−２）を連結したもの；ただし、Ｂ（０）〜Ｂ（ｎ−２）は、すべてが０のみからなるか、すべてが１のみからなるか、またはＢ（０）〜Ｂ（ｍ−１）までは０のみからなり且つＢ（ｍ）〜Ｂ（ｎ−２）までは１のみからなるものである）を用いることができる。
【００５４】
例えば、ユーザＩＤが、０〜Ｎ（１）×Ｎ（２）×…×Ｎ（Ｍ）−１のうちの予め定められた範囲内の整数から選択される場合に、対象ユーザＩＤをＮ（ｉ）で割った余りを該ユーザＩＤに対応する整数Ａ（ｉ）の値とする方法の場合の簡単な例を示すと、Ｎ（１）＝５の場合、ｎ＝５となり、ｄ＝３とすると、Γ0（５，３）符号は、以下のようになる。
Ａ（１）＝０のとき  ：  Ｗ（１）＝１１１  １１１  １１１  １１１
Ａ（１）＝１のとき  ：  Ｗ（１）＝０００  １１１  １１１  １１１
Ａ（１）＝２のとき  ：  Ｗ（１）＝０００  ０００  １１１  １１１
Ａ（１）＝３のとき  ：  Ｗ（１）＝０００  ０００  ０００  １１１
Ａ（１）＝４のとき  ：  Ｗ（１）＝０００  ０００  ０００  ０００
このようにして求めた各Ａ（ｉ）に対応する成分符号Ｗ（ｉ）を連結することによって、結託耐性符号を生成することができる。
【００５５】
この符号では１と０はそれぞれｄビットを単位として連続するように配置され、ｄビット未満の数の１や０が孤立して存在することはない（上記の例では、３ビット未満の数の１や０が孤立して存在することはないことがわかる）。したがって、ｄビット未満の数の１や０が孤立して存在する場合には、結託攻撃がなされたことが推測される（ｄビット未満の数の１や０が孤立して存在しない場合には、結託攻撃がなされなかったことが推測される）。
【００５６】
このようにして生成された結託耐性符号は、電子透かし埋込装置１の符号埋め込み部１２によって、対象コンテンツに埋め込まれる（ステップＳ１０３）。前述したように、生成された結託耐性符号を対象コンテンツに埋め込む方法には、特に限定はなく、どのような方法でも本発明は適用可能である。
【００５７】
図５に、符号生成部１１の一構成例を示す。
【００５８】
この符号生成部１１は、それぞれｋ’（＝Ｍ）個の法記憶部１２１−１，１２１−２，…，１２１−ｋ’、剰余計算部１２２−１，１２２−２，…，１２２−ｋ’、成分符号生成部１２４−１，１２４−２，…，１２４−ｋ’と、符号パラメータ記憶部１２３及び符号連接部１２５からなる。
【００５９】
法記憶部１２１−１，１２１−２，…，１２１−ｋ’には、例えば互いに素の関係にある整数ｐi（＝Ｎ（ｉ））(ｉ＝１，２，…，ｋ’)が記憶されており、これらの整数ｐiが剰余計算部１２２−１，１２２−２，…，１２２−ｋ’に法として供給される。剰余計算部１２２−１，１２２−２，…，１２２−ｋ’は、入力されるユーザＩＤ＝ｕに対して、整数ｐiを法とする剰余ｕi＝ｕ mod ｐi(ｉ＝１，２，…，ｋ’)をそれぞれ求める。すなわち、入力されたユーザＩＤに対応した複数の整数要素の組（＝｛Ａ（１），Ａ（２），…，Ａ（Ｍ）｝）として、剰余計算部１２２−１，１２２−２，…，１２２−ｋ’により剰余ｕi＝ｕ mod ｐi(ｉ＝１，２，…，ｋ’)が計算される。
【００６０】
成分符号生成部１２４−１，１２４−２，…，１２４−ｋ’は、ｋ’個の整数ｐi(ｉ＝１，２，…，ｋ’)に対して、符号パラメータ記憶部１２３に記憶された符号パラメータｔに従って剰余計算部１２２−１，１２２−２，…，１２２−ｋ’により求められた剰余ｕi(ｉ＝１，２，…，ｋ’)を表す前述したΓ0(ｎ，ｄ)符号からなる成分符号Γ0(ｐi，ｔ)をそれぞれ生成する。
【００６１】
符号連接部１２５は、成分符号生成部１２４−１，１２４−２，…，１２４−ｋ’により生成された各成分符号Γ0(ｐi，ｔ)を連接することによって、透かし情報である結託耐性符号を生成する。
【００６２】
図６に、成分符号生成部１２４−１，１２４−２，…，１２４−ｋ’の一つ(１２４−ｉ)の構成を示す。符号パラメータをｔ、剰余をｕi、法をｐiとすると、減算部１３１ではｐi−ｕi−１が求められる。“０”列生成部１３２では、符号パラメータｔと剰余ｕiに基づきｔ×ｕiビットの連続した“０”列が生成され、“１”列生成部１３３では、符号パラメータｔと減算部１３１からの出力ｐi−ｕi−１に基づきｔ×(ｐi−ｕi−１)ビットの連続した“１”列が生成される。そして、これらの“０”列と“１”列が連接部１３４で連接され、ｔ×(ｐi−１)ビットのビット列がΓ0(ｎ，ｄ)符号からなる成分符号Γ0(ｐi，ｔ)として生成される。
【００６３】
図７は、このようにして生成される結託耐性符号の成分符号(結託攻撃を受ける前の成分符号)の一例を示している。０からｎ−１までのｎ個のユーザＩＤ（識別情報）に対応して、Ｂ(０)，…，Ｂ(ｎ−２)のブロック“０”列からなる成分符号が割り当てられている。
【００６４】
ここで、上記の符号生成方法について数値を小さくとって簡単にした例を用いて説明する。
【００６５】
まず、整数の個数Ｍを３とし、Ｎ（１）＝３，Ｎ（２）＝５，Ｎ（３）＝７とする。この場合、Ａ（１）は０〜２のいずれか、Ａ（２）は０〜４のいずれか、Ａ（３）は０〜６のいずれかとなる。
【００６６】
次に、Ｎ（１）×Ｎ（２）×Ｎ（３）−１＝１０４であるので、０〜１０４の範囲の全部または一部をユーザＩＤ（識別情報）として用いる。ここでは、そのうち０〜１４をユーザＩＤとして用いるものとする。
【００６７】
例えば、ユーザＩＤ＝７の場合、
Ａ（１）＝７  ｍｏｄ  Ｎ（１）＝７  ｍｏｄ  ３＝１、
Ａ（２）＝７  ｍｏｄ  Ｎ（２）＝７  ｍｏｄ  ５＝２、
Ａ（３）＝７  ｍｏｄ  Ｎ（３）＝７  ｍｏｄ  ７＝０、
となる。
【００６８】
図８に、この例において各識別情報（ユーザＩＤ＝０〜１４）について求められたＡ（１），Ａ（２），Ａ（３）を示す。
【００６９】
次に、Γ0(ｎ，ｄ)符号においてｄ＝３とした場合におけるＡ（１）＝０，Ａ（１）＝１，Ａ（１）＝２のそれぞれに対応する成分符号Ｗ１は、次のようになる（なお、分かりやすくするために、０または１を、３ビット単位に分けて記述している）。
Ａ（１）＝０  ：  Ｗ１＝１１１  １１１
Ａ（１）＝１  ：  Ｗ１＝０００  １１１
Ａ（１）＝２  ：  Ｗ１＝０００  ０００
また、同様に、Ａ（２）＝０、Ａ（１）＝１、Ａ（２）＝２、Ａ（２）＝３、Ａ（２）＝４のそれぞれに対応する成分符号Ｗ２は、次のようになる。
Ａ（２）＝０：  Ｗ２＝１１１  １１１  １１１  １１１
Ａ（２）＝１：  Ｗ２＝０００  １１１  １１１  １１１
Ａ（２）＝２：  Ｗ２＝０００  ０００  １１１  １１１
Ａ（２）＝３：  Ｗ２＝０００  ０００  ０００  １１１
Ａ（２）＝４：  Ｗ２＝０００  ０００  ０００  ０００
また、同様に、Ａ（３）＝０、Ａ（３）＝１、Ａ（３）＝２、Ａ（３）＝３、Ａ（３）＝４、Ａ（３）＝５、Ａ（３）＝６のそれぞれに対応する成分符号Ｗ２は、次のようになる。
Ａ（３）＝０：  Ｗ３＝１１１  １１１  １１１  １１１  １１１  １１１
Ａ（３）＝１：  Ｗ３＝０００  １１１  １１１  １１１  １１１  １１１
Ａ（３）＝２：  Ｗ３＝０００  ０００  １１１  １１１  １１１  １１１
Ａ（３）＝３：  Ｗ３＝０００  ０００  ０００  １１１  １１１  １１１
Ａ（３）＝４：  Ｗ３＝０００  ０００  ０００  ０００  １１１  １１１
Ａ（３）＝５：  Ｗ３＝０００  ０００  ０００  ０００  ０００  １１１
Ａ（３）＝６：  Ｗ３＝０００  ０００  ０００  ０００  ０００  ０００
したがって、例えば、ユーザＩＤ＝７の場合、Ａ（１）＝１、Ａ（２）＝２、Ａ（３）＝０であるから、
Ｗ１＝０００  １１１
Ｗ２＝０００  ０００  １１１  １１１
Ｗ３＝１１１  １１１  １１１  １１１  １１１  １１１
となり、ユーザＩＤ＝７に対応する結託耐性符号は、それらを連結して、
000111  000000111111  111111111111111111
となる（なお、分かりやすくするために、Ｗ１〜Ｗ３に対応する部分の境界で分けて記述している）。
【００７０】
図９に、この例において各識別情報（ユーザＩＤ＝０〜１４）について求められた結託耐性符号を示す。
【００７１】
以下では、本実施形態に係る電子透かし解析装置２についてより詳細に説明する。
【００７２】
ここで、上記の例を利用して、結託攻撃について説明する。
【００７３】
例えば、上記のユーザＩＤ＝２のユーザが入手したコンテンツには、結託耐性符号として、
000000  000000111111  000000111111111111
が埋め込まれている（図８、図９参照）。また、例えば、上記のユーザＩＤ＝３のユーザが入手したコンテンツには、結託耐性符号として、
111111  000000000111  000000000111111111
が埋め込まれている（図８、図９参照）。
【００７４】
この場合に、ユーザＩＤ＝２のユーザとユーザＩＤ＝３の２人のユーザが持ちよったコンテンツを比較すると、上記３６ビットのうち、左から１〜６番目、１３〜１５番目、２５〜２７番目が相違していることがわかる。そこで、それらが識別情報（に対応する結託耐性符号）の一部と分かるため、１〜６番目、１３〜１５番目、２５〜２７番目のうちの一部に改ざんが施され、例えば、次のような改変が施される。
010101  000000010111  000000101111111111
同様に、ユーザＩＤ＝７のユーザとユーザＩＤ＝８との２人のユーザで、例えば、次のような改ざんが施される。
000010  000000101111  010111111111111111
また、同様に、ユーザＩＤ＝３、４、５、６の４人のユーザによって、例えば、次のような改ざんが施される。
010101  010101010101  000000000010101010
さて、前述したように、本実施形態の電子透かし解析装置２において、まず、符号抽出部２１は、検出対象となるコンテンツの複製物から埋め込み符号（埋め込まれた結託耐性符号、あるいは結託攻撃が施されて改ざんされたもの）を抽出する。
【００７５】
次いで、復号部２２は、抽出された符号に対して、追跡アルゴリズムを実行する。
【００７６】
ここで、追跡アルゴリズムの概要について説明する。
【００７７】
まず、剰余対および基準剰余について説明する。
【００７８】
図１０（ａ）に示すように、抽出された符号（生成された結託耐性符号、あるいは結託攻撃を受けた結託耐性符号）の成分符号（上記の例では３つの成分符号）の各々ごとについて、当該成分符号の両端の位置と、隣接する要素Ｂ（ｅ−１）とＢ（ｅ）との境界の位置を、数値化して表すものとする。すなわち、第ｉ番目の成分符号Ｗ（ｉ）の要素Ｂ（ｊ）の数をＮ（ｉ）−１個とし、図１０（ａ）でＮ（ｉ）をＮで表すものとすると、要素Ｂ（０）の左端の位置が０、要素Ｂ（ｅ−１）とＢ（ｅ）との境界の位置がｅ、要素Ｂ（Ｎ−２）の右端の位置がＮ−１で表される。
【００７９】
そして、コンテンツから検出された符号の第ｉ番目の成分符号Ｗ（ｉ）を、左端のビットからみていったときにはじめて出現する、０のみからなる要素Ｂ（s1−１）と１を含む要素Ｂ（s1）との境界を求め、該境界に対応する上記の位置を示す値s1を、ｒ(-)iで表すものとする。一方、右端のビットからみていったときにはじめて出現する、１のみからなる要素Ｂ（s2）と０を含む要素Ｂ（s2−１）との境界を求め、該境界に対応する上記の位置を示す値s2を、ｒ(+)iで表すものとする。
【００８０】
例えば、図１０（ｂ）の符号の例では、ｒ(-)i＝２，ｒ(+)i＝４となる。
なお、第ｉ番目の成分符号Ｗ（ｉ）が０のみからなる場合には、ｒ(-)i＝ｒ(+)i＝Ｎ（ｉ）−１となる。
また、第ｉ番目の成分符号Ｗ（ｉ）が１のみからなる場合には、ｒ(-)i＝ｒ(+)i＝０となる。
【００８１】
また、０のみからなる要素Ｂ（s1−１）と１を含む要素Ｂ（s1）との境界がない場合には、ｒ(-)i＝０となる。
また、１のみからなる要素Ｂ（s2）と０を含む要素Ｂ（s2−１）との境界がない場合には、ｒ(+)i＝Ｎ（ｉ）−１となる。
【００８２】
このように１つの成分符号Ｗ（ｉ）から、１対の位置情報ｒ(-)i，ｒ(+)iが得られる。これらｒ(-)iとｒ(+)iとの対を、剰余対と呼ぶものとする（なお、全成分符号Ｗ（ｉ）から得られた全剰余対の組（ｒ(-)1，ｒ(+)1，ｒ(-)2，ｒ(+)2，…ｒ(-)M，ｒ(+)M）を、以下、剰余対表現とも呼ぶ）。
【００８３】
なお、識別情報（＝Ｖとする）から生成される結託耐性符号そのものにおいては、０と１が混在する成分符号の要素は存在しないので、上記の剰余対に相当するものを考えると、常に、ｒ(-)i＝ｒ(+)i＝Ｖ  ｍｏｄ  Ｎ（ｉ）となる。例えば、図１０（ｃ）の符号の例では、ｒ(-)i＝２，ｒ(+)i＝２となる。また、例えば、図１０（ｄ）の符号の例では、ｒ(-)i＝４，ｒ(+)i＝４となる。
【００８４】
以下、識別情報から生成される結託耐性符号そのものにおける各成分符号（Ｗ（ｉ））における本来の境界位置情報（０からなるブロックと１からなるブロックの境界位置（ただし、成分符号が１のみからなる場合には左の端の位置、成分符号が０のみからなる場合には右の端の位置）を示す値）すなわち基準となる剰余（ｒ(-)i＝ｒ(+)i＝Ｖ  ｍｏｄ  Ｎ（ｉ））を、基準剰余と呼び、ｒ(0)iで表すものとする（なお、全成分符号Ｗ（ｉ）から得られる全基準剰余の組（ｒ(0)1，ｒ(0)2…ｒ(0)M）を、以下、基準剰余表現とも呼ぶ）。
【００８５】
さて、追跡アルゴリズムでは、検出された符号の各々の成分符号を調べ、予め定められたｄ（上記の例の場合、３）ビット未満の数の１や０が孤立して存在するブロックが存在する成分符号が検出された場合に、結託攻撃がなされたものと判断することができる。また、この場合に、（結託数が予め規定された許容数ｃ以下であったものと仮定して）全成分符号Ｗ（ｉ）から得られた全剰余対の組すなわち剰余対表現（ｒ(-)i，ｒ(+)i（ｉ＝１〜Ｍ））に基づいて、結託攻撃に使用された複製物に埋め込まれていたであろう結託耐性符号に対応する１又は複数のユーザＩＤ（識別情報）を求め、これを結託攻撃を行った結託者のユーザＩＤとして特定することができる。
【００８６】
各々のＡ（ｉ）に対応する成分符号Ｍ（ｉ）は、例えば、先に例示したもの、すなわち、
Ａ（３）＝０：  Ｗ３＝１１１  １１１  １１１  １１１  １１１  １１１
Ａ（３）＝１：  Ｗ３＝０００  １１１  １１１  １１１  １１１  １１１
Ａ（３）＝２：  Ｗ３＝０００  ０００  １１１  １１１  １１１  １１１
Ａ（３）＝３：  Ｗ３＝０００  ０００  ０００  １１１  １１１  １１１
Ａ（３）＝４：  Ｗ３＝０００  ０００  ０００  ０００  １１１  １１１
Ａ（３）＝５：  Ｗ３＝０００  ０００  ０００  ０００  ０００  １１１
Ａ（３）＝６：  Ｗ３＝０００  ０００  ０００  ０００  ０００  ０００
を比較して分かるように、その性質上、複数の複製物から得られる相違部分は、必ず連続した要素Ｂとして得られることがわかる（したがって、結託攻撃による改ざんによって、この連続した部分に０と１が混在してくることになる）。
【００８７】
そして、ある成分符号（ｉ）において、そのｄビット未満の数の１や０が孤立して存在する連続した部分（ブロック）の左端の位置と右端の位置、すなわちｒ(-)iとｒ(+)iは、必ず、結託攻撃に用いられた複数の複製物のいずれかに埋め込まれた結託耐性符号の対応する成分符号の０と１の区切り目の位置（成分符号がすべて１の場合は、該成分符号の左端の位置、すべて０の場合は、該成分符号の右端の位置）すなわちｒ(-)i＝ｒ(+)iに一致することがわかる。このような情報が、各成分符号Ｗ（ｉ）毎に得られる。それら情報ｒ(-)1、ｒ(+)1、ｒ(-)2、ｒ(+)2、…、ｒ(-)M、ｒ(+)Mを解析することによって、結託攻撃に使用された複製物に埋め込まれていたであろう結託耐性符号に対応するユーザＩＤを、結託攻撃を行った結託者のユーザＩＤとして特定することができる。
【００８８】
簡単な例としては、２人のユーザによる結託攻撃では、各成分符号ごとにおいて、ｒ(-)iは、２人のユーザの一方の持つ複製物に埋め込まれた符号のｒ(-)i＝ｒ(+)iに一致し、ｒ(+)iは、他方のユーザの持つ複製物に埋め込まれた符号のｒ(-)i＝ｒ(+)iに一致する（各成分符号ごとに一方と他方の対応は異なりうる）。ｒ(-)1とｒ(+)1からいずれか１つ、ｒ(-)2とｒ(+)2からいずれか１つ、…、ｒ(-)Mとｒ(+)Mからいずれか１つを選択したものを、それぞれ、各成分符号の０と１の区切り目の位置として持つような結託耐性符号が存在すれば、それが求める解であり、該結託耐性符号に対応するユーザＩＤが結託者を示すことになる。
【００８９】
例えば、先の図８、図９の例で示したように、
ユーザＩＤ＝２のユーザが入手したコンテンツに、結託耐性符号として、
000000  000000111111  000000111111111111
が埋め込まれており、ユーザＩＤ＝３のユーザが入手したコンテンツに、結託耐性符号として、
111111  000000000111  000000000111111111
が埋め込まれており、当該２人のユーザによって結託攻撃がなされ、次のような結託耐性符号、
010101  000000010111  000000101111111111
に改ざんされた場合に、
この改ざん符号では、
ｒ(-)1＝０，ｒ(+)1＝２
ｒ(-)2＝２，ｒ(+)2＝３
ｒ(-)3＝２，ｒ(+)3＝３
であり、
図８あるいは図９を参照すると、
ｒ(+)1＝２、ｒ(-)2＝２、ｒ(-)3＝２を、ユーザＩＤ＝２が満たし、かつ、
ｒ(-)1＝０、ｒ(+)2＝３、ｒ(+)3＝３を、ユーザＩＤ＝３が満たすので、
この結託攻撃は、ユーザＩＤ＝２とユーザＩＤ＝３によって行われ、
結託攻撃に用いられた符号は、
000000  000000111111  000000111111111111
と、
111111  000000000111  000000000111111111
であることを突き止めることができる。
【００９０】
ところで、結託攻撃後のある成分符号Ｗ（ｉ）における剰余対ｒ(-)i，ｒ(+)i（ｒ(-)i≠ｒ(+)iである場合）は、３人以上のユーザで結託攻撃を行ったとしても、そのうちの２人のユーザのユーザＩＤに対応する当該成分符号Ｗ（ｉ）における境界位置により決定されるので、当該ｒ(-)i，ｒ(+)i以外の位置に境界を持つユーザＩＤの当該成分符号Ｗ（ｉ）における当該境界位置は、対象コンテンツから検出された符号から得られた剰余対ｒ(-)i，ｒ(+)iには、現れてこないことになる。したがって、３人以上のユーザによる結託攻撃では、これに用いられたある複製物に埋め込まれた結託耐性符号について、その全成分符号が本来持つ境界位置ｒ(-)i＝ｒ(+)i（すなわち、基準剰余ｒ(0)i）の全ては得られないことがある。しかし、一方で、ある複製物に埋め込まれた結託耐性符号について、多数の成分符号について本来の境界位置ｒ(-)i＝ｒ(+)iが得られることが期待される。よって、対象コンテンツから検出された符号から得られたｒ(-)1、ｒ(-)2、…、ｒ(-)M、ｒ(+)1、ｒ(+)2、…、ｒ(+)Mを適宜組み合わせて検証することによって、かりにすべての結託者のユーザＩＤが特定できなかったとしても、一部の結託者のユーザＩＤを特定することができる。
【００９１】
これが従来の確率論的な追跡アルゴリズムの基本的な考え方である。
【００９２】
ところで、従来の追跡アルゴリズムは、ｒ(-)1、ｒ(-)2、…、ｒ(-)M、ｒ(+)1、ｒ(+)2、…、ｒ(+)Mのうちから選択された幾つかの剰余が、あるユーザＩＤを示していれば（選択された幾つかの剰余が、あるユーザＩＤに対応する識別情報に対する基準剰余表現の一部を示していれば）、それを結託者のユーザＩＤとして出力するものである。しかしながら、該選択された幾つかのものが実際には一人のユーザにのみ属するものではなく、複数のユーザに分属するものである場合には、結託者でないユーザのユーザＩＤが偶然に出力されてしまう。そこで、そのような誤検出の確率を一定以下に抑えるために、成分符号の個数（Ｍ）をより多く使う必要があり、符号長が長くなってしまうという問題があった。
【００９３】
本実施形態は、電子透かし解析装置２の復号部２２による追跡アルゴリズムにおいて、外符号の復号処理を工夫することによって、従来はある確率でもって正しい追跡を行うという確率論的な追跡を行ったいたのに対して、少なくとも外符号の復号は、確率論的ではなく、確実な追跡を行うことを可能にし、かつ、従来よりも符号長をより短く（成分符号の個数（Ｍ）をより少なく）することを可能にするものである。
【００９４】
以下、本実施形態の電子透かし解析装置２の復号部２２について詳しく説明する。
【００９５】
なお、前述したように、ここでは、識別情報＝ユーザＩＤである場合を例にとって説明している。
【００９６】
なお、成分符号は、内符号とも呼ばれ、各剰余対を符号化している。また、剰余対表現は、外符号とも呼ばれ、識別情報や、完全にとは言えないが、結託者のグループに含まれる１つ以上の識別情報に関する情報を、符号化している。
【００９７】
図１１に、本実施形態の電子透かし解析装置２の復号部２２の構成例を示す。
【００９８】
図１１に示されるように、復号部２２は、検出対象のコンテンツから読み出された符号（埋め込まれた結託耐性符号、あるいは結託攻撃が施されて改ざんされたもの）を入力し、各成分符号Ｗ（ｉ）から得られる剰余対の組すなわち剰余対表現ｒ(-)i，ｒ(+)i（ｉ＝１〜Ｍ）を出力する内符号復号部（剰余対表現部）２２１と、この剰余対表現ｒ(-)i，ｒ(+)i（ｉ＝１〜Ｍ）を入力し、追跡情報を出力する外符号復号部２２２とを含む。
【００９９】
まず、内符号復号部２２１について説明する。
【０１００】
図１２に、内符号復号部２２１の構成例を示す。
【０１０１】
図１２に示されるように、内符号復号部２２１は、符号分割部２２１１、各成分符号Ｗ（１）〜Ｗ（Ｍ）に対応して設けられる複数（Ｍ個）の剰余対検出部２２１２−１〜２２１２−Ｍからなる。
【０１０２】
図１３に、内符号復号部２２１の符号分割部２２１１の処理例を示す。
【０１０３】
符号分割部２２１１は、図１３に例示するように、検出された符号を入力し、予め定められている各成分符号の符号長に従って、それを各成分符号（内符号の符号語）に分割する。
【０１０４】
各成分符号Ｗ（ｉ）の符号長は、Γ0(ｎ，ｄ)符号では、ｎ＝Ｎ（ｉ）として、（Ｎ（ｉ）−１）×ｄビットとなる。
【０１０５】
例えば、先の結託攻撃例（図８、図９のユーザＩＤ＝２のユーザとユーザＩＤ＝３のユーザが結託攻撃した例；Γ0(ｎ，ｄ)符号で、Ｍ＝３，Ｎ（１）＝３，Ｎ（２）＝５，Ｎ（３）＝７，ｄ＝３の例）のように、
010101  000000010111  000000101111111111
という符号が検出された場合に、（予め、第１成分符号の符号長＝（３−１）×３＝６、第２成分符号の符号長＝（５−１）×３＝１２、第３成分符号の符号長＝（７−１）×３＝１８が分かっているものとして）この検出された符号を、
成分符号Ｗ（１）＝010101
成分符号Ｗ（２）＝000000010111
成分符号Ｗ（３）＝000000101111111111
のように分割する。
【０１０６】
分割された各成分符号Ｗ（１）〜Ｗ（Ｍ）は、それぞれ、対応する剰余対検出部２２１２−１〜２２１２−Ｍに与えられる。
【０１０７】
図１４に、内符号復号部２２１の第ｙ成分符号Ｗ（ｙ）に対応する第ｙ剰余対検出部２２１２−ｙの構成例を示す。なお、第ｙ剰余対検出部２２１２−ｙを代表させて記述しているが、剰余対検出部２２１２−１〜２２１２−Ｍのいずれも基本的には同様の構成である。
【０１０８】
図１４に示されるように、剰余対検出部２２１２−ｙは、第ｙ成分符号Ｗ（ｙ）のｄビット単位の各ブロックＢ(０)，…，Ｂ(Ｎ（ｙ）−２)に対応する複数（Ｋ＝Ｎ（ｙ）−１個）の判定部２２１２１−１〜２２１２１−Ｋと、境界位置ｒ(-)yを求める第１の境界位置検出部２２１２２と、境界位置ｒ(+)yを求める第２の境界位置検出部２２１２３とを含む。
【０１０９】
判定部２２１２１−１〜２２１２１−Ｋは、それぞれ、与えられた成分符号Ｗ（ｙ）のうちの該当するｄビットのブロックについて、ｄビット全てが０であるか、ｄビット全てが１であるか、それ以外（０と１が混在する）かを判定する。
【０１１０】
第１の境界位置検出部２２１２２は、判定部２２１２１−１〜２２１２１−Ｋの出力を判定部２２１２１−１から参照していくことによって、先に説明した境界位置ｒ(-)yを求める。
【０１１１】
同様に、第２の境界位置検出部２２１２３は、判定部２２１２１−１〜２２１２１−Ｋの出力を判定部２２１２１−Ｋから参照していくことによって、先に説明した境界位置ｒ(+)yを求める。
【０１１２】
検出された１対のｒ(-)y，ｒ(+)yが、第ｙ剰余対となる。
【０１１３】
例えば、上記の符号例（Ｍ＝３）では、第１剰余対検出部２２１２−１、第２剰余対検出部２２１２−２、第３剰余対検出部２２１２−３に、それぞれ、上記のＷ（１），Ｗ（２），Ｗ（３）が与えられ、
第１剰余対｛ｒ(-)1，ｒ(+)1｝＝｛０，２｝
第２剰余対｛ｒ(-)2，ｒ(+)2｝＝｛２，３｝
第３剰余対｛ｒ(-)3，ｒ(+)3｝＝｛２，３｝
がそれぞれ得られる。
【０１１４】
以上のようにして内符号復号部２２１により得られた第１剰余対ｒ(-)1，ｒ(+)1〜第Ｍ剰余対ｒ(-)M，ｒ(+)Mの組すなわち剰余対表現は、外符号復号部２２２へ与えられる。
【０１１５】
続いて、本実施形態の電子透かし解析装置２の復号部２２の外符号復号部２２２について説明する。
【０１１６】
図１５に、外符号復号部２２２の構成例を示す。
【０１１７】
図１５に示されるように、外符号復号部２２２は、結託者グループ抽出部２２２１と、結託者識別情報抽出部２２２２と、追跡情報出力部２２２３とを含む。
【０１１８】
ここで、追跡アルゴリズムでは、結託攻撃が行われる際の最大結託数をｃと想定している。すなわち、２≦ａ≦ｃを満たす任意のａ人の結託者すなわちａ個の相互に異なる識別情報の埋め込まれたコンテンツの複製物により結託攻撃が行われる場合を考える（なお、ここでは、ユーザと識別情報とが１対１に対応するものとして考えているが、例えば、ユーザと識別情報とが１対多対応となり得る場合であって、実際に同一の結託者が自身に対応する２つの識別情報をそれぞれ埋め込まれた同一のコンテンツについての２つの複製物を当該結託攻撃に供する際には、結託者の数とは、異なる識別情報を埋め込まれたコンテンツの複数物ごとに考えることになる）。
【０１１９】
以下では、ａ（２≦ａ≦ｃ）個の相互に異なる識別情報の埋め込まれたコンテンツの複製物により結託攻撃を行う際に供される当該複数のコンテンツの複製物にそれぞれ埋め込まれた識別情報により構成される識別情報群を、結託者グループと呼ぶものとする。例えば、図８、図９の例では、識別情報＝ユーザＩＤ＝０〜１４であるので、最大結託数ｃ＝３とすると（なお、実際には識別情報の範囲や最大結託数はもっと大きく取られる）、結託者グループには、｛０，１｝、｛０，２｝、…、｛０，１４｝、｛１，１｝、｛１，２｝、…、｛１，１４｝、｛２，３｝、…｛２，１４｝、｛３，４｝、…、｛１１，１４｝、｛１２，１３｝、｛１２，１４｝、｛１３，１４｝（以上、ａ＝２による結託）、｛０，１，２｝、｛０，１，３｝、…、｛０，１，１４｝、｛０，２，３｝、｛０，２，４｝、…、｛０，２，１４｝、｛０，３，４｝、…、｛１０，１１，１４｝、｛１１，１２，１３｝、｛１１，１２，１４｝、｛１２，１３，１４｝（以上、ａ＝３による結託）がある。最大結託数ｃ＝３以下での結託攻撃は、必ず、上記の結託者グループのいずれかによって行われる。
【０１２０】
次に、結託者グループ抽出部２２２１は、検出された符号の各成分符号Ｗ（１）〜Ｗ（Ｍ）から得られた剰余対の組すなわち剰余対表現、
ｒ(-)1，ｒ(+)1，ｒ(-)2，ｒ(+)2，…，ｒ(-)M，ｒ(+)M
を入力し、これに適合する結託者グループを出力する。
【０１２１】
ここで、ある結託者グループが（対象となった）剰余対表現に適合するとは、次の場合である。すなわち、その結託者グループを構成する複数の識別情報にそれぞれ対応する基準剰余表現（ｒ(0)1，ｒ(0)2，…，ｒ(0)M）を、同じ成分符号Ｗ（ｉ）に対応するものごとに比較して（例えば、Ｗ（１）について、各識別情報に対するｒ(0)1を比較して）、成分符号Ｗ（ｉ）における基準剰余の最大値をｍａｘ（ｒ(0)i）で表し、最小値をｍｉｎ（ｒ(0)i）で表したときに、（対象となった）剰余対表現ｒ(-)1，ｒ(+)1，ｒ(-)2，ｒ(+)2，…，ｒ(-)M，ｒ(+)Mの全てについて、ｒ(-)1＝ｍｉｎ（ｒ(0)1）、ｒ(+)1＝ｍａｘ（ｒ(0)1）、ｒ(-)2＝ｍｉｎ（ｒ(0)2）、ｒ(+)2＝ｍａｘ（ｒ(0)2）、…ｒ(-)M＝ｍｉｎ（ｒ(0)M）、ｒ(+)M＝ｍａｘ（ｒ(0)M）が成立する場合に、当該ある結託者グループが（対象となった）剰余対表現に適合すると判断する。
【０１２２】
結託者グループ抽出部２２２１により得られる結託者グループの数は、剰余対表現の内容によって、１つになる場合と、複数になる場合とがあり得る。
【０１２３】
なお、上記の適合性の判断は、上記の処理により行ってもよいが、あらかじめ剰余対表現と該剰余対表現に適合する（１又は複数の）結託者グループとの対応関係を示すテーブルを容易しておいて、該テーブルを参照することによって行ってもよい。また、剰余対表現と、該剰余対表現に適合する１つの結託者グループを構成する複数の識別情報又は該剰余対表現に適合する複数の結託者グループに共通に存在する１又は複数の識別情報あるいはそれが存在しないことを示す情報との対応関係を示すテーブルを用意しておいて、該テーブルを参照して、識別情報を求めてもよい。この場合には、次の結託者識別情報抽出部２２２２は、不要になる。
【０１２４】
ところで、与えられた剰余対表現のすべての剰余について、ｒ(-)1＝ｒ(+)1，ｒ(-)2＝ｒ(+)2，…，ｒ(-)M＝ｒ(+)Mが成り立つ場合には、結託攻撃はなかったことになる。この場合、全ての基準剰余についてｒ(-)1＝ｒ(+)1＝ｒ(0)1，ｒ(-)2＝ｒ(+)2＝ｒ(0)2，…，ｒ(-)M＝ｒ(+)M＝ｒ(0)Mが成立するような基準剰余表現ｒ(0)1，ｒ(0)2，…，ｒ(0)Mにより特定される識別情報が、当該コンテンツに埋め込まれていたことになる。この場合には、結託攻撃はなかった旨（または結託攻撃はなかった旨及び検出された識別情報）を、追跡情報出力部２２２３に渡せばよい。
【０１２５】
なお、例えば、最初に、与えられた剰余対表現のすべての剰余について、ｒ(-)1＝ｒ(+)1，ｒ(-)2＝ｒ(+)2，…，ｒ(-)M＝ｒ(+)Mが成り立つかどうか判断し、成り立たない場合にはじめて前述の適合性の判断を行うようにしてもよい。あるいは、例えば、前述したようにテーブルを参照する方法をとる場合において、該テーブルにｒ(-)1＝ｒ(+)1，ｒ(-)2＝ｒ(+)2，…，ｒ(-)M＝ｒ(+)Mが成り立つ剰余対表現とそのときの識別情報との対応関係をも併せて登録しておき、与えられた剰余対表現のすべての剰余についてｒ(-)1＝ｒ(+)1，ｒ(-)2＝ｒ(+)2，…，ｒ(-)M＝ｒ(+)Mが成り立つか否かにかかわらず、該テーブルを用いて処理ができるようにしてもよい。
【０１２６】
また、何らかの理由により、ｒ(-)1＝ｒ(+)1，ｒ(-)2＝ｒ(+)2，…，ｒ(-)M＝ｒ(+)Mが成り立たたず、かつ、与えられた剰余対表現に適合する結託者グループが得られない場合や、ｒ(-)1＝ｒ(+)1，ｒ(-)2＝ｒ(+)2，…，ｒ(-)M＝ｒ(+)Mが成り立ち、かつ、当該コンテンツに埋め込まれていたことになる識別情報が得られない場合には、エラーとなる。この場合には、エラーとなった旨を、追跡情報出力部２２２３に渡せばよい。
【０１２７】
なお、使用する識別情報の範囲、最大結託数ｃ、各識別情報に対応する基準剰余表現（または、これを求めるための情報（例えば、Ｎ（ｉ）など））などの追跡アルゴリズムに必要な情報は、追跡を実施する際に外部から入力するようにしてもよいし、予め格納しておいてもよい（なお、各識別情報に対応する基準剰余表現を求めるための情報を予め格納しておいた場合に、追跡を実施するごとに基準剰余表現を求めてもよいし、一度計算した値については格納しておいてもよい）。
【０１２８】
次に、結託者識別情報抽出部２２２２は、結託者グループ抽出部２２２１により得られた結託者グループをもとに、実際に結託攻撃に参加したであろう結託者の識別情報を抽出する。
【０１２９】
結託者グループ抽出部２２２１により１つの結託者グループのみが得られた場合には、該結託者グループを構成する識別情報を全て、結託者の識別情報として、追跡情報出力部２２２３に渡す。なお、求められた識別情報に加えて、結託者グループを特定する情報または剰余対表現をも出力するようにしてもよい。
【０１３０】
結託者グループ抽出部２２２１により２以上の結託者グループが得られた場合には、得られた全ての結託者グループに共通に存在する（１又は複数の）識別情報のみを、結託者の識別情報として、追跡情報出力部２２２３に渡す。なお、この共通に存在する識別情報を、共通識別情報と呼ぶものとする。
【０１３１】
なお、結託者グループ抽出部２２２１により２以上の結託者グループが得られ、かつ、共通識別情報が存在する場合に、求められた共通識別情報に加えて、結託者グループを特定する情報または剰余対表現をも出力するようにしてもよい。
【０１３２】
ただし、結託者グループ抽出部２２２１により２以上の結託者グループが得られた場合であっても、共通識別情報が１つもないときは、共通識別情報が存在しない旨（または共通識別情報が存在しない旨及び得られた結託者グループを特定する情報、または共通識別情報が存在しない旨及び得られた剰余対表現）を、追跡情報出力部２２２３に渡せばよい。なお、後述するように、得られた複数の結託者グループに共通識別情報が存在しないケースが理論的には発生しないようにした場合には、得られた複数の結託者グループに共通識別情報が存在しないケースは何らかのエラーによってのみ発生することになる。
【０１３３】
追跡情報出力部２２２３は、結託者グループ抽出部２２２１又は結託者識別情報抽出部２２２２から渡された情報を含む追跡情報を出力する。
【０１３４】
追跡情報は、例えば、結託攻撃が検出された場合にその結託攻撃に参加したであろう１又は複数の結託者の識別情報、もしくは結託攻撃が検出されたものの共通識別情報が得られなかった旨（またはその旨及び結託者グループを特定する情報、またはその旨及び剰余対表現）、もしくは結託攻撃はなかった旨（または結託攻撃はなかった旨及び検出された識別情報）、もしくはエラーとなった旨を含むものである。
【０１３５】
次に、本実施形態の外符号復号部２２２による追跡アルゴリズムについて、数値を小さくとって簡単にした簡単にした具体例を用いて説明する。
【０１３６】
まず、整数の個数Ｍを４とし、Ｎ（１）＝２，Ｎ（２）＝３，Ｎ（３）＝５，Ｎ（４）＝７とする。また、Ｎ（１）×Ｎ（２）×Ｎ（３）×Ｎ（４）−１＝２１０であるが、そのうち０〜５を識別情報（すなわち、その一例としてのユーザＩＤ）として用いるものとする。
【０１３７】
図１６に、この例において各識別情報（ユーザＩＤ＝０〜５）について求められた基準剰余表現ｒ(0)1（＝Ａ（１）），ｒ(0)2（＝Ａ（２）），ｒ(0)3（＝Ａ（３）），ｒ(0)4（＝Ａ（４））を示す。
【０１３８】
ユーザＩＤ＝０〜５に対応するユーザに提供されるコンテンツの複製物には、それぞれ、図１６の該当する基準剰余表現に対応する結託耐性符号が埋め込まれることになる。
【０１３９】
ここで、識別情報としてユーザＩＤ＝０が埋め込まれたコンテンツの複製物、ユーザＩＤ＝１が埋め込まれたコンテンツの複製物、ユーザＩＤ＝２が埋め込まれたコンテンツの複製物、ユーザＩＤ＝３が埋め込まれたコンテンツの複製物、ユーザＩＤ＝４が埋め込まれたコンテンツの複製物、ユーザＩＤ＝５が埋め込まれたコンテンツの複製物のうちの、いずれか２つまたはいずれか３つにより結託攻撃がなされた結果、その結託攻撃によって生成されたコンテンツの複製物から、図１７（ａ）に示すような剰余対表現が得られたものとする。
【０１４０】
この場合には、図１７（ｂ）に示すようなユーザＩＤ＝２とユーザＩＤ＝３により構成される結託者グループのみが、図１７（ａ）の剰余対表現に適合する（該結託者グループのみが得られる）。
【０１４１】
なお、図１７（ｂ）において、○は当該成分符号ｉで剰余ｒ(-)iを与えることになった各ユーザＩＤの基準剰余での最小値を示し、□は当該成分符号ｉで剰余ｒ(+)iを与えることになった各ユーザＩＤの基準剰余での最大値を示す。
【０１４２】
このように、唯一の結託者グループのみが得られた場合には、該結託者グループを構成する全ユーザＩＤが、実際に結託攻撃に参加したであろう結託者のユーザＩＤ（識別情報）になる。
【０１４３】
また、他の例として、図１８（ａ）に示すような剰余対表現が得られたものとする。
【０１４４】
この場合には、図１８（ｂ）に示すようなユーザＩＤ＝２とユーザＩＤ＝３とユーザＩＤ＝４により構成される結託者グループのみが、図１８（ａ）の剰余対表現に適合する（該結託者グループのみが得られる）。
【０１４５】
なお、図１８（ｂ）において、○および□は図１７（ｂ）と同様の意味を示している。ただし、図１８（ｂ）では、ｒ(+)1を与えたのはＩＤ＝３の基準剰余として示しているが、ＩＤ＝５の基準剰余としても同じである。この点は、ｒ(+)2についても同様のことが言える。
【０１４６】
この場合も、唯一の結託者グループのみが得られた場合であるので、該結託者グループを構成する全ユーザＩＤが、実際に結託攻撃に参加したであろう結託者のユーザＩＤ（識別情報）になる。
【０１４７】
一方、図１９（ａ）に示すような剰余対表現が得られたものとする。
【０１４８】
この場合には、図１９（ｂ）に示すようなユーザＩＤ＝０とユーザＩＤ＝１とユーザＩＤ＝４により構成される結託者グループ▲１▼と、図１９（ｃ）に示すようなユーザＩＤ＝０とユーザＩＤ＝３とユーザＩＤ＝４により構成される結託者グループ▲２▼の両方が、図１９（ａ）の剰余対表現に適合する（該２つの結託者グループが得られる）。
【０１４９】
なお、図１９（ｂ），（ｃ）において、○および□は図１７（ｂ）と同様の意味を示している。ただし、図１９（ｂ）では、ｒ(-)1を与えたのはＩＤ＝０の基準剰余として示しているが、ＩＤ＝４の基準剰余としても同じである。この点は、図１９（ｂ）でのｒ(+)2、図１９（ｃ）でのｒ(-)1、ｒ(-)2についても同様のことが言える。
【０１５０】
このように、同一の剰余対表現から複数の結託者グループが得られた場合には、いずれの結託者グループが、実際に結託攻撃に参加したであろう結託者のユーザＩＤ（識別情報）に対応するものかは、（剰余対表現のみからは）わからない。
【０１５１】
しかしながら、（結託攻撃が最大結託者数以下の結託者数で行われたとすれば）、それらのうちのいずれか１つの結託者グループが、求めるべき結託者グループである。
【０１５２】
したがって、得られた複数の結託者グループの全てに共通に存在する識別情報があれば、少なくともその識別情報（すなわち共通識別情報）は、実際に結託攻撃に参加したであろう結託者の識別情報である。
【０１５３】
よって、この例の場合には、図１９（ｂ）に示す結託者グループ▲１▼と図１９（ｃ）に示す結託者グループ▲２▼に共通に存在するユーザＩＤ＝０とユーザＩＤ＝４が、実際に結託攻撃に参加したであろう結託者のユーザＩＤ（識別情報）になる。
【０１５４】
このように、実際に結託攻撃に参加したであろう結託者が、たとえ全ては分からなくても、確実に一人でも分かるということは、デジタルコンテンツの違法コピーに対する事前の抑制や著作権侵害が発生したときの事後の救済のために、非常に大きな意味がある。
【０１５５】
ところで、複数の結託者グループが得られたものの共通識別情報が存在しないケースが（理論的に）発生し得ることを許容する場合において、そのようなケースが発生したことは、実際に結託攻撃に参加したであろう結託者の識別情報が１つも得られないことを意味する。しかしながら、（結託攻撃が最大結託者数以下の結託者数で行われたとすれば）、それらのうちのいずれか１つの結託者グループが、求めるべき結託者グループである。したがって、このような場合にも、得られた複数の結託者グループの情報を蓄積することによって、何らかの参考になることが考えられる。
【０１５６】
しかし、複数の結託者グループが得られたものの共通識別情報が存在しないケースは、できるだけ少なく抑えらるのが望ましい。そして、このようなケースは、何らかの手段によって、少なくすることができる。
【０１５７】
例えば、複数の結託者グループが得られたものの、共通識別情報が存在しないようなケースを探索し、そのような結託者グループを構成する識別情報の全部又は一部を使用しないようにすることも、一つの方法である。
【０１５８】
また、例えば、想定する最大の結託者数ｃを一定とすれば、定性的には、整数の個数Ｍ（＝成分符号の個数）を増加させるほど、あるいは使用する識別情報の範囲を減少させるほど、上記のケースを少なくすることができる。なお、図１６の例は、上記のケースを皆無にした例に該当している。
【０１５９】
また、本発明者は、最大結託者数ｃと、整数の個数Ｍ（＝成分符号の個数）と、使用する識別情報の範囲（０から始まる連番とする）との間に、一定の条件を規定することによって、複数の結託者グループが得られた場合に１又は複数の共通識別情報が（理論的に）必ず存在するようにする（すなわち、上記のケースを理論的に皆無にする）方法を見出した。この点については、後で詳しく説明する。
【０１６０】
さて、以下では、本実施形態の追跡アルゴリズムの手順例を幾つか示す。なお、具体的な追跡アルゴリズムの手順については様々なバリエーションが可能であり、以下に示すものに限定されるものではない。
【０１６１】
（手順例１）
図２０に、本実施形態に係る復号部の外符号復号部の処理手順の一例を示す。
【０１６２】
なお、ここでは、与えられた剰余対表現において、ｒ(-)1＝ｒ(+)1，ｒ(-)2＝ｒ(+)2，…，ｒ(-)M＝ｒ(+)Mの少なくとも一つが成立しない場合を考える。
【０１６３】
まず、与えられた剰余対表現に適合する結託者グループを全て求める（ステップＳ１）。
【０１６４】
求められた結託者グループの数が１である場合（ステップＳ２）、求められた結託者グループを構成する全てのユーザＩＤを結託者のユーザＩＤ（結託者ＩＤ）とし（ステップＳ３）、求められた結託者ＩＤを出力する（ステップＳ６）。
【０１６５】
求められた結託者グループの数が２以上である場合（ステップＳ２）、求められた全ての結託者グループに共通に存在するユーザＩＤがあれば（ステップＳ４）、求められた全ての結託者グループに共通に存在する（１又は複数の）ユーザＩＤのみを結託者ＩＤとし（ステップＳ５）、求められた結託者ＩＤを出力する（ステップＳ６）。一方、求められた全ての結託者グループに共通に存在するユーザＩＤがなければ（ステップＳ４）、結託者ＩＤが得られなかった旨（またはその旨及び結託者グループを特定する情報、またはその旨及び剰余対表現）を出力する（ステップＳ７）。
【０１６６】
なお、ステップＳ２で結託者グループが１つも得られない場合には、エラーとなる。
【０１６７】
図２１に、ステップＳ１の処理手順の一例を示す。
【０１６８】
なお、ここでは、対象となる全ての結託者グループに、結託者グループＩＤとして０からの連続番号を付すものとする。
【０１６９】
まず、ｉ＝０とする（ステップＳ１１）。
【０１７０】
結託者グループ０が、与えられた剰余対表現に適合するかどうか調べる（ステップＳ１２）。そして、結託者グループ０が与えられた剰余対表現に適合するならば、該結託者グループ０のＩＤ＝０を保持する（ステップＳ１３）。
【０１７１】
次に、ｉを１増加させ（ステップＳ１５）、結託者グループ１が、与えられた剰余対表現に適合するかどうか調べ（ステップＳ１２）、結託者グループ１が与えられた剰余対表現に適合するならば、該結託者グループ０のＩＤ＝０を保持する（ステップＳ１３）。
【０１７２】
以下、同様の処理を全ての結託者グループに対して行う（ステップＳ１４，Ｓ１５）。
【０１７３】
なお、ユーザＩＤの総数が大きい場合には、全ての結託者グループに対して、この処理を行うことは、コストが大きいので、例えば、結託者グループのサイズに関する条件や、現実の結託攻撃がそれを破る確率は十分に小さいと考えられる条件などによって、限定された結託者グループに対してのみ、この処理を行うようにしてもよい。
【０１７４】
（手順例２）
図２２に、本実施形態に係る復号部の外符号復号部の処理手順の一例を示す。
【０１７５】
なお、ここでは、与えられた剰余対表現において、ｒ(-)1＝ｒ(+)1，ｒ(-)2＝ｒ(+)2，…，ｒ(-)M＝ｒ(+)Mの少なくとも一つが成立しない場合を考える。
【０１７６】
まず、与えられた剰余対表現に適合する結託者グループＸを１つ求める（ステップＳ２１）。
【０１７７】
次に、求められた結託者グループＸを構成するユーザＩＤと同一のユーザＩＤを少なくとも一つ含む結託者グループであって、与えられた剰余対表現に適合する結託者グループＹ（Ｙ1，Ｙ2，Ｙ3，…）を全て求める（ステップＳ２２）。
【０１７８】
結託者グループＹが１つも得られなければ（ステップＳ２３）、求められた結託者グループを構成する全てのユーザＩＤを結託者ＩＤとし（ステップＳ２４）、求められた結託者ＩＤを出力する（ステップＳ２７）。
【０１７９】
結託者グループＹが１又は複数得られた場合（ステップＳ２３）、得られた全ての結託者グループ（Ｘ，Ｙ1，Ｙ2，Ｙ3，…）に共通に存在するユーザＩＤがあれば（ステップＳ２５）、求められた全ての結託者グループに共通に存在する（１又は複数の）ユーザＩＤのみを結託者ＩＤとし（ステップＳ２６）、求められた結託者ＩＤを出力する（ステップＳ２７）。一方、求められた全ての結託者グループ（Ｘ，Ｙ1，Ｙ2，Ｙ3，…）に共通に存在するユーザＩＤがなければ（ステップＳ２５）、結託者ＩＤが得られなかった旨（またはその旨及び結託者グループを特定する情報、またはその旨及び剰余対表現）を出力する（ステップＳ２８）。
【０１８０】
なお、ステップＳ２１で結託者グループが１つも得られない場合には、エラーとなる。あるいは、このエラー時に、結託者ＩＤが得られなかった旨等を出力し、終了するように変形してもよい。
【０１８１】
図２３に、ステップＳ２１の処理手順の一例を示し、図２４に、ステップＳ２２の処理手順の一例を示す。
【０１８２】
なお、ここでは、対象となる全ての結託者グループに、結託者グループＩＤとして０からの連続番号を付すものとする。
【０１８３】
ｉ＝０から順にｉを１ずつ増加し（ステップＳ３１，Ｓ３４）、結託者グループｉが与えられた剰余対表現に適合するかどうか調べ（ステップＳ３２）、最初に見つかった該剰余対表現に適合する結託者グループｉを（ステップＳ３３）、結託者グループＸとする（ステップＳ３５）。
【０１８４】
次に、図２３の手順で得られた結託者グループＸの次の結託者グループｉ＝Ｘ＋１から順にｉを１ずつ増加し（ステップＳ４１，Ｓ４５）、各結託者グループｉについて（ステップＳ４４）、次の処理を行う。なお、ｊ＝０とする（ステップＳ４１）。Ｓ３４において、次のｉに相当する結託者グループが無くなった場合には、エラーを出力し終了する。
【０１８５】
結託者グループｉが、結託者グループＸを構成するユーザＩＤと同一のユーザＩＤを一つも含まない場合は、次の結託者グループに移る（ステップＳ４２，Ｓ４５）。
【０１８６】
結託者グループｉが、結託者グループＸを構成するユーザＩＤと同一のユーザＩＤを少なくとも一つ含む場合は（ステップＳ４２）、結託者グループｉが、与えられた剰余対に適合するか調べ、適合するならば、該結託者グループｉを、結託者グループＹjとし、ｊを１増加する（ステップＳ４３）。
【０１８７】
（手順例３）
図２５及び図２６に、本実施形態に係る復号部の外符号復号部の処理手順の一例を示す。
【０１８８】
なお、図２５及び図２６は、最大結託数ｃ＝３の場合の例である。
【０１８９】
剰余対表現の剰余対の個数をｄ（これまでのＭ）とする（ステップＳ５１）。
【０１９０】
すべての識別情報ｕに対して、剰余対表現との間で、ｕが最大剰余あるいは最小剰余と合同であるような剰余対の数を、Ｖ（ｕ）とする（ステップＳ５２）。ただし、ｕの剰余が最大剰余より大きいか、最小剰余より小さいような対がひとつでも存在する場合には、Ｖ（ｕ）＝０とする。また、Ｖ（ｕ）が零でない識別情報全体の集合をＵ’とする（ステップＳ５２）。
【０１９１】
なお、ｇは、剰余対の組において、最大剰余と最小剰余が一致している対の個数を表す。
【０１９２】
結託に加わった最大３個の識別情報で、剰余対の組に含まれる２（ｄ−ｇ）個の剰余のすべてを作り出す必要があるので、まず、Ｕ’の中から｜Ｖ（ｕ１）｜が２（ｄ−ｇ）／３以上の識別情報ｕ１を選ぶ（ステップＳ５３）。
【０１９３】
結託に加わった残り最大２個の識別情報で、識別情報の組に含まれる２（ｄ−ｇ）個の剰余からｕ１が作り出した｜Ｖ（ｕ１）｜個の剰余を引いた残りの２（ｄ−ｇ）−｜Ｖ（ｕ１）｜個の剰余のすべてを作り出す必要があるので、次に、Ｕ’−｛ｕ１｝の中から、｜Ｖ（ｕ２）−Ｖ（ｕ１）｜が（２（ｄ−ｇ）−｜Ｖ（ｕ１）｜）／２以上の識別情報ｕ２を選ぶ（ステップＳ５４）。
【０１９４】
適当なｕ２が存在しないときは（ステップＳ５５）、ステップＳ５３に戻り、新たなｕ１を選ぶ。
【０１９５】
結託に加わった残り最大１個の識別情報で、識別情報の組に含まれる２（ｄ−ｇ）個の剰余からｕ１とｕ２が作り出した｜Ｖ（ｕ１）＋Ｖ（ｕ２）｜個の剰余を引いた残りの２（ｄ−ｇ）−｜Ｖ（ｕ１）＋Ｖ（ｕ２）｜個の剰余のすべてを作り出す必要があるので、次に、Ｕ’−｛ｕ１，ｕ２｝の中から、｜Ｖ（ｕ３）−Ｖ（ｕ１）−Ｖ（ｕ２）｜が（２（ｄ−ｇ）−｜Ｖ（ｕ１）＋Ｖ（ｕ２）｜）以上の識別情報ｕ３を選ぶ（ステップＳ５６）。
【０１９６】
適当なｕ３が存在しないときは（ステップＳ５７）、ステップＳ５４に戻り、新たなｕ２を選ぶ。
【０１９７】
ステップＳ５７までのステップで得られた｛ｕ１，ｕ２，ｕ３｝は、与えられた剰余対表現を与える結託である。そこで、各要素ｕ１，ｕ２，ｕ３が共通逆像（共通識別情報）に含まれるか否かを調べるため、Ｕのかわりに、Ｕ−｛ｕ１｝、Ｕ−｛ｕ２｝、Ｕ−｛ｕ３｝の各々に対して、ステップＳ５１からステップＳ５７を行い、与えられた剰余対表現を与える結託が存在するか調べる。
【０１９８】
ステップＳ５８においてＵ−｛ｕｉ｝について与えられた剰余対表現を与えるような結託が存在しない場合には（ステップＳ５９）、ｕ１とｕ２とｕ３のすべてを結託者ＩＤとして｛ｕ１，ｕ２，ｕ３｝を共通逆像として出力する（ステップＳ６１）。
【０１９９】
ステップＳ５８においてＵ−｛ｕｉ｝について与えられた剰余対表現を与えるような結託が存在した場合には（ステップＳ５９）、そのようなｕｉは、共通逆像（共通識別情報）に含まれないとして｛ｕ１，ｕ２，ｕ３｝から排除し、残された集合である共通逆像（共通識別情報）を結託として出力する（ステップＳ６０）。
【０２００】
なお、図２５及び図２６は、最大結託数ｃ＝３の場合の例であったが、もちろん、最大結託数ｃが４以上の場合の手順も同様に実施可能である。
【０２０１】
なお、これまでは、識別情報＝ユーザＩＤとし、追跡結果としてユーザＩＤを出力する場合を主に説明しているが、識別情報≠ユーザＩＤの場合に、復号部２２の外符号復号部２２２の追跡情報出力部２２２３の形態について、以下のように種々のバリエーションが可能である。
・追跡結果として識別情報を求め、求められた識別情報からユーザＩＤを求めて、ユーザＩＤを出力する。
・追跡結果として識別情報を求め、求められた識別情報を出力する（必要に応じて外部で識別情報からユーザＩＤを求める）。
・追跡結果として識別情報を求め、求められた識別情報から複製物ＩＤを求め、複製物ＩＤからユーザＩＤを求め、ユーザＩＤを出力する。
・追跡結果として識別情報を求め、求められた識別情報から複製物ＩＤを求め、複製物ＩＤを出力する（必要に応じて外部で複製物ＩＤからユーザＩＤを求める）。
・追跡結果として識別情報を求め、求められた識別情報を出力する（必要に応じて外部で識別情報から複製物ＩＤを求め、複製物ＩＤからユーザＩＤを求める）。
【０２０２】
また、使用可能な全ての識別情報あるいは実際に使用している全ての識別情報について、追跡対象とする代わりに、ある特定の１又は複数の識別情報についてのみ、追跡対象とする方法も可能である。例えば、何らかの手段によってある特定の結託者が判明しているときに、残りの結託者を特定するような場合にこの方法を適用できる。
【０２０３】
さて、先に言及したように、最大結託者数ｃと、整数の個数Ｍ（＝成分符号の個数）と、使用する識別情報の範囲（０から始まる連番とする）との間に、一定の条件を規定することによって、同一の剰余対表現に適合する結託者グループが複数存在する場合には、少なくとも１つの共通識別情報（それら複数の結託者グループの全てに共通に含まれる識別情報）が存在するようにすることができる。この場合には、同一の剰余対表現に適合する結託者グループが複数存在しても、必ず、少なくとも１つの結託者の識別情報（例えば、ユーザＩＤ）を得ることができる。以下では、この条件の一つを示す。
【０２０４】
（１）この条件の一つとは、最大結託数ｃと、内符号の成分符号の個数ｄ（これまでのＭ）と、後述する識別情報数規定パラメータｋとを用いて、次のように表される。
ｄ＞（ｃ2／２）（ｋ−１）
以下では、ｄ＞（ｃ2／２）（ｋ−１）が成立する場合には、同一の剰余対表現に適合する結託者グループが複数存在しても、少なくとも１つの共通識別情報が必ず存在することを示す。
【０２０５】
（２）組合せ論的な外符号
組合せ論的な外符号が持つべき性質を“追跡可能性表現”として定式化する。
【０２０６】
（２．１）追跡可能表現
以下、Ｕを識別情報（例えば、ユーザＩＤ）の集合、Ｐをある集合とし、
写像φ：POW（Ｕ）→Ｐ
が与えられているとする。
【０２０７】
＜定義１（追跡可能表現）＞  CC⊂POW（Ｕ）とする。次の条件が満たされるとき、（φ，Ｐ，CC）をＵの追跡可能表現（ｔｒａｃｅａｂｌｅ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ｏｆ  Ｕ）と定義する。ここで、POW（Ｕ）はＵのべき集合とする。
【０２０８】
【数１】
0003822501.tif 000002
【０２０９】
＜定義２（共通逆像）＞  Ｕの追跡可能表現（φ，Ｐ，CC）において、ｐ∈Ｐの共通逆像（ｃｏｍｍｏｎ  ｉｎｖｅｒｓｅ）を次のように定義する。
【０２１０】
【数２】
0003822501.tif 000003
【０２１１】
なお、Ｃは、ある結託者グループに相当し、ｐは、剰余対表現に相当し、共通逆像Ｔ（ｐ）は、「同一の剰余対表現ｐに適合する結託者グループＣが複数存在する場合に、それら複数の結託者グループの全てに共通に存在する識別情報（共通識別情報）」に相当する。
【０２１２】
＜定理１＞  次の条件を満たすＵの追跡可能表現（φ，Ｐ，CC）は、ｃ−ｓｅｃｕｒｅ符号の外符号（識別情報）として利用できる。
【０２１３】
【数３】
0003822501.tif 000004
なお、ｃは、最大結託数である。
【０２１４】
＜＜定理１の証明＞＞  内符号（成分符号）は、与えられた符号語ｕを復号してｐ＝φ（Ｃ）なるｐ∈Ｐを出力すると仮定する。外符号における復号を、ｐを入力して、Ｔ（ｐ）を出力するものとする。
式（３）より、｜Ｃ｜≦ｃならば、Ｃ∈CCである。このとき、Ｔ（ｐ）⊂Ｃが保証され、ｃ−ｓｅｃｕｒｅ符号を構成できる。  ＜＜定理１の証明おわり＞＞
追跡可能表現の組合せ論的な構成により、外符号における誤りは生じない。
【０２１５】
（３）具体的構成
追跡可能表現の具体的構成として、ｃ−ｓｅｃｕｒｅ  ＣＲＴ  符号への適用を想定して、剰余対の組である剰余対表現による構成を与える。剰余対表現が追跡可能表現となるための十分条件を示す。
【０２１６】
【数４】
0003822501.tif 000005
【０２１７】
なお、Ｚは、整数全体の集合を表すものとする。また、ｎＺは、整数全体の集合の各要素の絶対値をｎ倍したものを表すものとする。したがって、Ｕ＝Ｚ／ｎＺ＝｛０，１，２，３，…，ｎ−１｝となる。
【０２１８】
このとき、（φ，Ｐ）をＵの剰余対表現（ｒｅｓｉｄｕｅ−ｐａｉｒ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）と呼び、ｐ0，…，ｐd-1をそのモジュライと呼び、（ｐ0，…，ｐk-1；ｐk，…，ｐd-1）と記すことにする。
【０２１９】
なお、ｐ0，…，ｐd-1は、これまでのＮ（１），…，Ｎ（Ｍ）に相当する（ｄはＭに相当する）。また、φ（Ｃ）は、これまでのｒ(-)1、ｒ(-)2、…、ｒ(-)M、ｒ(+)1、ｒ(+)2、…、ｒ(+)Mに相当する。また、ｋは、０〜ｐ0×ｐ1×…×ｐd-1−１（これまでの０〜Ｎ（１）×Ｎ（２）×…×Ｎ（Ｍ）−１）の範囲の整数のうちから、使用する識別情報の範囲を、０〜ｐ0×ｐ1×…×ｐk-1−１（これまでの０〜Ｎ（１）×Ｎ（２）×…×Ｎ（ｋ）−１）に規定するものである。なお、ｋを、識別情報数規定パラメータと呼ぶものとする。
【０２２０】
（３．１）ｃ＝２と一般のｋ≧２の場合
＜定理２＞  条件１を仮定する。
CC＝｛Ｃ∈POW（Ｕ）  ｜  ｜C｜≦２｝，
ｄ≧２ｋ−１，
ならば、Ｕの剰余対表現（φ，Ｐ）は、Ｕの追跡可能表現（φ，Ｐ，CC）を与える。
【０２２１】
【数５】
0003822501.tif 000006
【０２２２】
＜＜補題１の証明＞＞  各剰余に対して、それを生じさせているＣの元が少なくとも１つ存在することにより自明である。  ＜＜補題１の証明おわり＞＞
【数６】
0003822501.tif 000007
【０２２３】
＜補題２＞  条件１を仮定する。ｕ，ｕ′∈Ｃに対して、
ｕ＝ｕ′  ⇔  δ（ｕ，ｕ′）＝０，
ｕ≠ｕ′  ⇔  δ（ｕ，ｕ′）≧ｄ−ｋ−１．
＜＜補題２の証明＞＞  ｕ，ｕ′の間において、ｋ個の剰余が一致するとき、中国人剰余定理により、ｕ＝ｕ′となる。そのとき、それ以外の剰余も全て一致する。  ＜＜補題２の証明おわり＞＞
＜＜定理２の証明＞＞  POW（Ｕ）の元Ｃ＝｛ｕ1，ｕ2｝，Ｃ′＝｛ｕ1′，ｕ2′｝が、
φ（Ｃ）＝φ（ｃ′），                                    （４）
Ｃ∩Ｃ′＝｛｝，                                          （５）
を満たすと仮定する。なお、｛｝は空集合を表す。ｄ′≡δ（ｕ1，ｕ2）＝δ（ｕ1′，ｕ2′）≦ｄとおく。式（４）は、ｕ1，ｕ2の間で、いくつか（ｍ個とする）のモジュライに対応して、値の異なる剰余を交換すると、ｕ1′，ｕ2′が得られることを意味している（図２７参照）。この交換によって、ｕ1とｕ1′とを入れ替え、ｕ2とｕ2′とを入れ替えるとすると、
δ（ｕ1，ｕ1′）＝δ（ｕ2，ｕ2′）＝ｍ，
δ（ｕ1，ｕ2′）＝δ（ｕ1′，ｕ2）＝ｄ′−ｍ．
となる。
【０２２４】
式（５）より、ｕ1′≠ｕ1，ｕ1′≠ｕ2である。これに、補題２を適用し、
ｄ−ｋ＋１≦ｍ≦ｄ′−ｄ＋ｋ−１，
が、式（４）と式（５）が成立する十分条件である。これより、ｄ≧２ｋ−１のとき、式（４）と式（５）は、両立し得ず、
φ（Ｃ）＝φ（Ｃ′）  ⇒  Ｃ∩Ｃ′≠｛｝，
となる。しかも、Ｃ，Ｃ′の間に共通の元が１つ存在するならば、補題１より、それぞれの残りの元も一致して、Ｃ＝Ｃ′となる。よって、式（１）が満足され、（φ，Ｐ，CC）は、Ｕの追跡可能表現となる。  ＜＜定理２の証明おわり＞＞上の追跡可能表現を外符号とするｃ−ｓｅｃｕｒｅ  ＣＲＴ符号は、ｃ＝２のままであるが、“J. Yoshida,K. Iwamura and H. Imai,“A coding method for collusionsecure watermark and less decline”,SCIS’98-10.2A, 1998.”の２−ｓｅｃｕｒｅ符号をｋ＝２からｋ≧２に一般化したものと見なせる。
【０２２５】
（３．２）一般のｃ≧２と一般のｋ≧２の場合
一般のｃ≧２とｋ≧２に対して、剰余対表現が追跡可能表現となるための十分条件を示す。
【０２２６】
＜定理３＞  条件１を仮定する。
CC＝｛Ｃ∈POW（Ｕ）  ｜  ｜Ｃ｜≦ｃ｝，                  （６）
ｄ＞ｃ2（ｋ−１）／２，                                  （７）
ならば、Ｕの剰余対表現（φ，Ｐ）は、Ｕの追跡可能表現（φ，Ｐ，CC）を与える。
【０２２７】
＜＜定理３の証明＞＞  命題PP（ｒ）を次のように定義する。
【０２２８】
∀Ｃ1，…，Ｃr∈CC
［φ（Ｃ1）＝…＝φ（Ｃr）  ⇒  Ｃ1∩…∩Ｃr≠｛｝］．
基底命題をPP（２）とし、帰納法のステップを
∀ｒ≧２［PP（ｒ）  ⇒  PP（ｒ＋１）］
とする数学的帰納法により証明する。
【０２２９】
命題PP（２）の証明：  ２つの結託Ｃ1｛ｕ1，…，ｕc｝，Ｃ2｛ｕ1′，…，ｕc′｝が、以下を満たしているものと仮定する。
φ（Ｃ1）＝φ（Ｃ2），                                    （８）
Ｃ1∩Ｃ2＝｛｝．                                          （９）
【数７】
0003822501.tif 000008
上式において、両辺の位数をとる。
【０２３０】
【数８】
0003822501.tif 000009
【０２３１】
したがって、式（１０）に式（１１）を代入し、次式を得る。
ｄ≦ｃ2（ｋ−１）／２−（ｃ2／２−１）ｇ
よって、定理が仮定している条件ｄ＞ｃ2（ｋ−１）／２が満たされるとき、命題PP（２）が成立する。
【０２３２】
命題PP（ｒ）⇒命題PP（ｒ＋１）の証明：  （ｒ＋１）個の結託Ｃi（ｉ＝１，…，ｒ＋１）が次の条件を満たしているとする。
∀ｉ∈｛１，…，ｒ＋１｝［｜Ｃi｜≦ｃ］，
φ（Ｃ1）＝…＝φ（Ｃr+1）．
次式を仮定すると矛盾が生ずるという背理法を展開する。
【０２３３】
【数９】
0003822501.tif 000010
【０２３４】
上式より、次式が成り立つ（図２８参照）。
【０２３５】
【数１０】
0003822501.tif 000011
【０２３６】
よって、ｒ≦｜Ｃi｜≦ｃである。
【０２３７】
ｒ＞ｃの場合には、式（１２）は、明らかに矛盾である。
【０２３８】
【数１１】
0003822501.tif 000012
【０２３９】
よって、定理が仮定している条件ｄ＞ｃ2（ｋ−１）／２が満たされるとき、式（１２）は、矛盾である。
【０２４０】
【数１２】
0003822501.tif 000013
【０２４１】
例外２に言う２個以上の元は、各々、式（１３）を満たす。したがって、例外１や例外２が存在しても、ｒ＝ｃの場合と同様の議論が展開でき、定理が仮定している条件ｄ＞ｃ2（ｋ−１）／２が満たされるとき、式（１２）は、矛盾である。以上より、命題PP（ｒ）⇒命題PP（ｒ＋１）が証明された。  ＜＜定理３の証明おわり＞＞
以上によって、ｄ＞（ｃ2／２）（ｋ−１）が成立する場合には、同一の剰余対表現に適合する結託者グループが複数存在しても、少なくとも１つの共通識別情報が必ず存在することが示された。
【０２４２】
なお、上記の条件ｄ＞（ｃ2／２）（ｋ−１）を緩和した条件で、システムを構成することも可能である。上記の条件は、必要十分条件ではないので、上記の条件を満たすｄより小さい値、あるいはｋより大きい値によって、同一の剰余対表現に適合する結託者グループが複数存在しても、少なくとも１つの結託者の識別情報（ユーザＩＤ）を必ず得ることができる、という構成があり得る（例えば、なお、図１６の例は、上記の条件を緩和したものになっている）。また、上記の条件を緩和した値を使用することによって、同一の剰余対表現に適合する結託者グループが複数存在し、その複数の結託者グループの全てに共通に存在するユーザＩＤがないために、１つも結託者の識別情報（ユーザＩＤ）を特定できないケースが幾つか発生したとしても、そのようなケースを許容することができれば、より短い符号でシステムを構成することができる。
【０２４３】
以下では、本発明がＤｅｄｅｋｉｎｄ環上のｃ−ｓｅｃｕｒｅ  ＣＲＴ符号に適用可能であることについて説明する。
【０２４４】
本発明では、ｃ−ｓｅｃｕｒｅ  ＣＲＴ符号は、中国人剰余定理という数学上の定理を応用したもので、整数の法ｐ0，ｐ1，…，ｐd-1を用いて、整数によって識別情報を表現していたが、中国人剰余定理が成立するのは整数のなす環に限定されない。Ｄｅｄｅｋｉｎｄ環とよばれる環では、中国人剰余定理が成立することが知られている。よって、本発明は、Ｄｅｄｅｋｉｎｄ環上で構成されたｃ−ｓｅｃｕｒｅ  ＣＲＴ符号に対しても適用できる。整数のなす環以外のＤｅｄｅｋｉｎｄ環として有限体上の多項式環が知られている。そのような有限体上の多項式環上のｃ−ｓｅｃｕｒｅ  ＣＲＴ符号の構成は、文献“M. Kim, J. Shikata, H. Muratani, and H. Imai,“Constructing c-secure codes using polynomials over finite fields”, SITA2001, W-B-1-3, 2001.”において詳述されている。
【０２４５】
整数のなす環の場合との対比で説明すると、法ｐ0，ｐ1，…，ｐd-1は、整数のなす環の場合には、互いに素な整数の組であったが、多項式環の場合には、共通の因子を持たない既約多項式の組
ｐ0（ｘ），ｐ1（ｘ），…，ｐd-1（ｘ）
となる。条件ｐ0＜ｐ1＜…＜ｐd-1については、これに代わって、
ｄｅｇ（０）≦ｄｅｇ（１）≦…≦ｄｅｇ（ｄ−１）
とする。ここで、ｄｅｇ（ｉ）は多項式ｐi（ｘ）の次数とする。ここで、多項式の係数は有限体Ｆ（ｑ）上で定義されているとする。条件｜Ｕ｜≦ｐ0×ｐ1×…×ｐk-1については、これに代わって、
｜Ｕ｜≦ｑdeg(0)×ｑdeg(1)×…×ｑdeg(k-1)
とする。ここでのＵは、（ｄｅｇ（０）＋ｄｅｇ（１）＋…＋ｄｅｇ（ｋ−１））次以下のモニック多項式全体の集合とする。
【０２４６】
２つの多項式の間に大小関係を定義し、また、剰余は、多項式の意味での剰余とすれば（例えば、法となる多項式ｐi（ｘ）ごとに、考えられる全ての剰余を０から始まる正整数に対応させ、該正整数をこれまで説明してきた当該法における基準剰余として扱えば）、これまで説明してきた整数の環の場合と全く同様にして、多項式環上でｃ−ｓｅｃｕｒｅ  ＣＲＴ符号が構成され、本発明の組合せ論的な外符号の構成も可能である。
【０２４７】
以下では、本実施形態のハードウェア構成、ソフトウェア構成について説明する。
【０２４８】
本実施形態の電子透かし解析装置は、ハードウェアとしても、ソフトウェア（（コンピュータに所定の手段を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるための）プログラム）としても、実現可能である。また、電子透かし解析装置をソフトウェアで実現する場合には、記録媒体によってプログラムを受け渡しすることも、通信媒体によってプログラムを受け渡しすることもできる。もちろん、それらは、電子透かし埋込装置についても同様である。
また、電子透かし埋込装置や電子透かし解析装置をハードウェアとして構成する場合、半導体装置として形成することができる。
また、本発明を適用した電子透かし解析装置を構成する場合、あるいは電子透かし解析プログラムを作成する場合に、同一構成（あるいは、共有もしくは使い回し可能な構成）を有するブロックもしくはモジュールがあっても、それらをすべて個別に作成することも可能であるが、同一構成（あるいは、共有もしくは使い回し可能な構成）を有するブロックもしくはモジュールについては１または適当数のみ用意しておいて、それをアルゴリズムの各部分で共有する（使い回す）ことも可能である。電子透かし埋込装置を構成する場合、あるいは電子透かし埋め込みプログラムを作成する場合も、同様である。また、電子透かし埋込装置および電子透かし解析装置を含むシステムを構成する場合、あるいは電子透かし埋め込みプログラムおよび電子透かし検出プログラムを含むシステムを作成する場合には、電子透かし埋込装置（あるいはプログラム）と電子透かし解析装置（あるいはプログラム）に渡って、同一構成（あるいは、共有もしくは使い回し可能な構成）を有するブロックもしくはモジュールについては１または適当数のみ用意しておいて、それをアルゴリズムの各部分で共有する（使い回す）ことも可能である。
【０２４９】
また、電子透かし埋込装置や電子透かし解析装置をソフトウェアで構成する場合には、マルチプロセッサを利用し、並列処理を行って、処理を高速化することも可能である。
【０２５０】
また、これまで説明してきた構成は、装置の一部としてだけでなく、それ自体が一つの装置として成立可能である。例えば、電子透かし解析装置の復号部２２は、電子透かし解析装置を構成する一体不可分の構成部分としても、電子透かし解析装置を構成する部品あるいはモジュール等としも、独立した復号装置としても成立する。
【０２５１】
ところで、デジタル透かしに対する透かし技術は、デジタルデータの他に、ある情報あるいは物質の一部の内容を変更しても、その情報あるいは物質の同一性、同質性あるいは経済的価値等を変じないようなものにも適用可能であり、本発明は、デジタルデータの他に、そのような情報あるいは物質にも適用可能である。
【０２５２】
例えば、本発明において、結託攻撃への耐性を持つ電子透かし埋込装置／電子透かし解析装置において用いられる、埋め込まれる符号の生成手段、検出手段は、化学的に合成される、あるいは、工業的に管理された環境下で生物的に生成される化合物あるいは化学物質の出所の追跡にも応用できる。化合物としては、ＤＮＡ、ＲＮＡ、タンパク質、その他の高分子の化合物が、符号を埋め込むことができる冗長性を多く持つ。
【０２５３】
以下では、本発明を、化合物の複製物に対して個別の識別情報（ユーザＩＤ、製造者ＩＤ、販売者ＩＤ、取引ＩＤ、それらを組み合わせた情報など）を埋め込み、その出所を特定する手段を与える透かし技術として適用する場合について説明する。
【０２５４】
化合物は、複数の原子、分子、基といった物質から構成されている。例えば、ＤＮＡやＲＮＡは、所定のアミノ酸の配列構造を持っており、別のアミノ酸で置きかえるか如何かによって情報が表現されているとみなせる。その構造の中には、（デジタルコンテンツの場合には、データを変更しても、作品の同一性あるいは経済的価値を変えない場合があるのと同様に、）化合物の場合には、組成を変更しても、当該目的において、その作用・副作用・効用等の性質・機能等（別の観点でみれば、経済的価値）を変えない場合がある。そのような許容された範囲内の変更によって、その複製物を個々に識別する情報を埋め込むことができる。
【０２５５】
本発明の電子透かしを化合物に適用する場合、化合物に対する透かし埋込装置は、デジタルコンテンツに対する透かし埋込装置におけるデジタルコンテンツの所定の部分のビットを変更する構成を、化合物の所定の部分の組成を変更する装置に置き換えたものである（符号生成部は同様の構成のもので構わない）。また、化合物に対する透かし解析装置は、デジタルコンテンツに対する透かし解析装置において透かし情報を検出するためにデジタルコンテンツの所定の部分のビットの値を読み取る情報を検出する構成を、透かし情報を検出するために化合物の所定の部分の組成を解析する装置に置き換えたものである（復号部は同様の構成のもので構わない）。すなわち、化合物とのインタフェースとなる装置が相違するだけで、原理的には、デジタルコンテンツに対する透かし技術と同じである。
【０２５６】
図２９に、化合物に対する透かし埋込装置の構成例を示す。
【０２５７】
符号生成部３００１は、その化合物に埋め込むべき識別情報を入力とし、結託耐性符号を生成する（図２の符号生成部１１と同様の構成のもので構わない）。
【０２５８】
特定部位の構造変換部３００２〜３００４は、それぞれ、結託耐性符号の各ビット、あるいは、ビットの各集合に対して、その値に応じて化合物の構造を変換するものである。特定部位の構造変換部３００２は、原化合物の特定部位１を処理し、特定部位の構造変換部３００３は、特定部位１を処理済みの化合物の特定部位２を処理し、特定部位の構造変換部３００４は、特定部位１，２を処理済みの化合物の特定部位３を処理して、所望する埋込済み化合物を生成する。もちろん、図２９では、３つの構造変換部が示されているが、その数は３に限定されるものではない。
【０２５９】
ここで、化合物の構造の変換とは、その化合物の利用の目的に適した性質あるいは機能等を損なわず且つ新たな弊害あるいは副作用等をもたらさないままで、異なる構造を持つ化合物に変換する手段のことである。あるいは、その化合物が純粋な化合物ではなく、混合物である場合には、その組成を変更する手段であってもよい。
【０２６０】
図３０に、化合物に対する透かし埋込装置の他の構成例を示す。
【０２６１】
図２９の構成例は、すでに合成された化合物の構造を後から変換するものであったが、図３０の構成例は、化合物の合成時に符号を埋め込むものである。
【０２６２】
符号生成部３０１１は、その化合物に埋め込むべき識別情報を入力とし、結託耐性符号を生成する（図２の符号生成部１１と同様の構成のもので構わない）。
【０２６３】
この場合、各合成材料毎に、結託耐性符号の各ビット、あるいは、ビットの各集合に対して、その値に応じた合成材料が容易されており、合成材料部３０１２〜３０１４は、それぞれ、結託耐性符号の各ビット、あるいは、ビットの各集合に対して、その値に応じた化合物の合成材料を選択するものである。もちろん、図３０では、３つの合成材料選択部が示されているが、その数は３に限定されるものではない。
【０２６４】
合成部３０１５は、各合成材料部３０１２〜３０１４により選択された合成材料を合成して、所望する埋込済み化合物を生成する。
【０２６５】
さて、化合物に対する結託攻撃では、基本的にはデジタルコンテンツに対する結託攻撃と同様で、例えば、複数の異なる識別情報（例えば、ユーザＩＤ、製造者ＩＤ、ユーザＩＤ及び製造者ＩＤ等）が埋め込まれた化合物の構造を比較することで、差異のある部分の構造を改変することで作られる。
【０２６６】
図３１に、化合物に対する透かし解析装置の構成例を示す。
【０２６７】
特定部位の構造読み取り部３２０１〜３２０１は、図２９の特定部位の構造変換部３００２〜３００４あるいは図３０の合成材料部３０１２〜３０１４に対応するもので、その化合物中の特定部位の構造を読み取り、それをビットあるいはビットの集合である情報として出力する。
【０２６８】
復号部３２０４は、それらのビットをもとに、追跡アルゴリズムを実行して、結託攻撃がなかったこと、または結託攻撃に用いられたであろう複製物に埋め込まれていた結託耐性符号に対応するユーザＩＤを特定するものである（図３の復号部２２と同様の構成のもので構わない）。
【０２６９】
ここで、本発明に用いられる化合物の構造の変換手段や構造の読み取り手段について、利用可能な技術を例示する。以下では、ＤＮＡの場合を例にとって説明する。
【０２７０】
ＤＮＡにおいて、その塩基配列を求めることを、シークエンシングという。シークエンシングの方法としては、ショットガン法、プライマーウォーク法、ネスティッドデレーション法などが知られている。これらは、いずれも遺伝子のクローニングによる方法である。シークエンシングで用いる試薬・機器・装置の例については、各種の方法が提案されている。例えば、渡辺格監修、杉浦昌弘編集「クローニングとシークエンス」、農村文化社（１９８９年）や、榊佳之等編「ゲノムサイエンス」、共立出版（１９９９年）などに開示されている。
【０２７１】
同様に、ＤＮＡの例では、新しい遺伝子を導入する際に用いられている遺伝子導入法により構造変換が可能である。遺伝子導入法には、燐酸カルシウム沈殿法、デキストラン法、リボフェクション法などの化学的な方法や、電気穿孔法、マイクロインジェクション法などが知られている。例えば、波賀信幸著「分子細胞工学」、コロナ社（２０００年）に開示されている。
【０２７２】
さて、上記では、デジタルコンテンツの複製物に対する追跡の他にも適用可能な一例として、化合物あるいは化学物質に対する追跡の例を示した。
【０２７３】
このような追跡対象を「オブジェクト」と呼ぶとすると、本発明は、デジタルコンテンツや、化合物あるいは化学物質以外のオブジェクトの追跡にも、適用可能である。本実施形態では、オブジェクトが、物理的実体を持たない（あるいは物理的実体を媒介としてやり取りされる）電子的なデータの一例として、デジタルコンテンツについて説明した。本実施形態では、デジタルコンテンツへの識別情報に対応する結託耐性符号の埋め込み技術として、電子透かし技術を用いたが、その他の技術を用いた場合にも適用可能である。また、本実施形態では、オブジェクトが物質の一例として、遺伝子情報を含むＤＮＡ、ＲＮＡ、タンパク質などについて示した。本実施形態では、ＤＮＡ、ＲＮＡ、タンパク質などへの識別情報に対応する結託耐性符号の書き込み技術として、遺伝子組換えやタンパク質のアミノ酸配列の置換によって行う例を示した。しかしながら、前述したように、オブジェクトとのインタフェースとなる技術が相違するだけで、識別情報や結託耐性符号に関しては、電子情報処理システムにおいて処理可能であり、その処理については、原理的には、どのようなオブジェクトであっても全て同じである。したがって、当該オブジェクトへの識別情報に対応する結託耐性符号の埋め込み技術を、当該オブジェクトに応じて選択しさえすれば、これまでに説明してきた構成を提供することが可能である。
【０２７４】
本発明は、これまで説明してきた結託耐性符号とは異なる構成を持つ「識別情報を表現する情報」を用いる場合にも、適用可能である。この場合には、例えば、オブジェクトから抽出された識別情報を表現する情報をもとに、対応する識別情報を求めるにあたって、対象となるオブジェクトから抽出された、識別情報を表現する情報を入力し、予め定められた最大結託数以下の結託数による任意の識別情報の組合せからなる結託グループのうち、入力された前記識別情報を表現する情報と一定の関係にある結託グループ（例えば、入力された前記識別情報を表現する情報を、結託攻撃によって生成し得る、あるいは、生成する確率が高いような、結託者グループ）を求めるとともに、複数の結託グループが求められた場合には、それら複数の結託者グループに共通に存在する識別情報を求めるようにしてもよい。
【０２７５】
なお、この発明の実施の形態で例示した構成は一例であって、それ以外の構成を排除する趣旨のものではなく、例示した構成の一部を他のもので置き換えたり、例示した構成の一部を省いたり、例示した構成に別の機能あるいは要素を付加したり、それらを組み合わせたりすることなどによって得られる別の構成も可能である。また、例示した構成と論理的に等価な別の構成、例示した構成と論理的に等価な部分を含む別の構成、例示した構成の要部と論理的に等価な別の構成なども可能である。また、例示した構成と同一もしくは類似の目的を達成する別の構成、例示した構成と同一もしくは類似の効果を奏する別の構成なども可能である。
また、この発明の実施の形態で例示した各種構成部分についての各種バリエーションは、適宜組み合わせて実施することが可能である。
また、この発明の実施の形態は、個別装置としての発明、関連を持つ２以上の装置についての発明、システム全体としての発明、個別装置内部の構成部分についての発明、またはそれらに対応する方法の発明等、種々の観点、段階、概念またはカテゴリに係る発明を包含・内在するものである。
従って、この発明の実施の形態に開示した内容からは、例示した構成に限定されることなく発明を抽出することができるものである。
【０２７６】
本発明は、上述した実施の形態に限定されるものではなく、その技術的範囲において種々変形して実施することができる。
【０２７７】
【発明の効果】
本発明によれば、結託耐性符号による識別情報が埋め込まれたオブジェクトに対する結託攻撃に用いられたオブジェクトの識別情報を、より短い符号長により推測することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る電子透かし埋込装置及び電子透かし解析装置を含むコンテンツ流通システムの概略構成を示す図
【図２】同実施形態に係る電子透かし埋込装置の構成例を示す図
【図３】同実施形態に係る電子透かし解析装置の構成例を示す図
【図４】同実施形態に係る電子透かし埋込装置の概略的な手順の一例を示すフローチャート
【図５】同実施形態に係る電子透かし埋込装置の符号生成部の構成例を示す図
【図６】同実施形態に係る符号生成部の成分符号生成部の構成例を示す図
【図７】同実施形態に係る電子透かし埋込装置により生成される成分符号の例について説明するための図
【図８】同実施形態における各ユーザＩＤに対応する複数の整数の組の例について説明するための図
【図９】同実施形態における各ユーザＩＤに対応する結託耐性符号の例について説明するための図
【図１０】同実施形態における各成分符号でのビットパターンに関する境界の位置について説明するための図
【図１１】同実施形態に係る電子透かし解析装置の復号部の構成例を示す図
【図１２】同実施形態に係る復号部の内符号復号部の構成例を示す図
【図１３】同実施形態に係る内符号復号部の符号分割部の処理について説明するための図
【図１４】同実施形態に係る内符号復号部の剰余対検出部の構成例を示す図
【図１５】同実施形態に係る復号部の外符号復号部の構成例を示す図
【図１６】同実施形態に係る追跡アルゴリズムについて説明するための図
【図１７】同実施形態に係る追跡アルゴリズムについて説明するための図
【図１８】同実施形態に係る追跡アルゴリズムについて説明するための図
【図１９】同実施形態に係る追跡アルゴリズムについて説明するための図
【図２０】同実施形態に係る復号部の外符号復号部の処理手順の一例を示すフローチャート
【図２１】同実施形態に係る復号部の外符号復号部の処理手順の一例を示すフローチャート
【図２２】同実施形態に係る復号部の外符号復号部の処理手順の他の例を示すフローチャート
【図２３】同実施形態に係る復号部の外符号復号部の処理手順の他の例を示すフローチャート
【図２４】同実施形態に係る復号部の外符号復号部の処理手順の他の例を示すフローチャート
【図２５】同実施形態に係る復号部の外符号復号部の処理手順のさらに他の例を示すフローチャート
【図２６】同実施形態に係る復号部の外符号復号部の処理手順のさらに他の例を示すフローチャート
【図２７】剰余の交換について説明するための図
【図２８】ｒ＝ｃ＝３の場合について説明するための図
【図２９】同実施形態に係る化合物に対する透かし埋込装置の構成例を示す図
【図３０】同実施形態に係る化合物に対する透かし埋込装置の他の構成例を示す図
【図３１】同実施形態に係る化合物に対する透かし解析装置の他の構成例を示す図
【符号の説明】
１…電子透かし埋込装置
２…電子透かし解析装置
３…流通経路
１１…符号生成部
１２…符号埋込部
２１…符号抽出部
２２…復号部
２２１…内符号復号部
２２１１…符号分割部
２２１２−１〜２２１２−Ｍ…剰余対検出部
２２１２１−１〜２２１２１−Ｋ…判定部
２２１２２，２２１２３…境界位置検出部
２２２…外符号復号部
２２２１…結託者グループ抽出部
２２２２…結託者識別情報抽出部
２２２３…追跡情報出力部
１２１−１〜１２１−ｋ′…法記憶部
１２２−１〜１２２−ｋ′…剰余計算部
１２３…符号パラメータ記憶部
１２４−１〜１２４−ｋ′…成分符号生成部
１２５…符号連接部
１３１…減算部
１３２…“０”列生成部
１３３…“１”列生成部
１３４…連接部
３００１，３０１１…符号生成部
３００２〜３００４…特定部位の構造変換部
３０１２〜３０１４…合成材料部
３０１５…合成部
３２０１〜３２０１…特定部位の構造読み取り部
３２０４…復号部
【図１】
0003822501.tif 000014
【図２】
0003822501.tif 000015
【図３】
0003822501.tif 000016
【図４】
0003822501.tif 000017
【図５】
0003822501.tif 000018
【図６】
0003822501.tif 000019
【図７】
0003822501.tif 000020
【図８】
0003822501.tif 000021
【図９】
0003822501.tif 000022
【図１０】
0003822501.tif 000023
【図１１】
0003822501.tif 000024
【図１２】
0003822501.tif 000025
【図１３】
0003822501.tif 000026
【図１４】
0003822501.tif 000027
【図１５】
0003822501.tif 000028
【図１６】
0003822501.tif 000029
【図１７】
0003822501.tif 000030
【図１８】
0003822501.tif 000031
【図１９】
0003822501.tif 000032
【図２０】
0003822501.tif 000033
【図２１】
0003822501.tif 000034
【図２２】
0003822501.tif 000035
【図２３】
0003822501.tif 000036
【図２４】
0003822501.tif 000037
【図２５】
0003822501.tif 000038
【図２６】
0003822501.tif 000039
【図２７】
0003822501.tif 000040
【図２８】
0003822501.tif 000041
【図２９】
0003822501.tif 000042
【図３０】
0003822501.tif 000043
【図３１】
0003822501.tif 000044