(57)【特許請求の範囲】
【請求項１】
オブジェクトに埋め込まれた結託耐性符号に対応する識別情報を求める識別情報復号装置において、
対象となるオブジェクトから結託耐性符号として抽出された符号を入力する手段と、
入力された前記符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出する検出手段と、
対象となる各識別情報毎に、当該識別情報に対応する結託耐性符号を構成する複数の成分符号の各々について、ビット列のパターンが変化する境界位置に関する第３の境界位置情報を得る手段と、
対象となる各識別情報毎に、入力された前記符号を構成する前記複数の成分符号の各々について検出された複数組の前記第１及び第２の境界位置情報、並びに当該識別情報に対応する結託耐性符号を構成する複数の成分符号の各々について得られた複数の前記第３の境界位置情報に基づいて、当該識別情報が前記オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるか否か判定する判定手段とを備え、
前記判定手段は、各識別情報に対する前記判定にあたって、各々の前記成分符号に対応する前記第１及び第２の境界位置情報と前記第３の境界位置情報との間の関係が、発生し得ない禁止関係であるか否か判断し、少なくとも１つの成分符号において禁止関係であると判断された場合には、当該識別情報は前記結託攻撃に使用された結託耐性符号に対応するものではないと判定することを特徴とする識別情報復号装置。
【請求項２】
前記判定手段は、同一の前記成分符号について、前記第１の境界位置情報の示す位置と前記第２の境界位置情報の示す位置との間の範囲内に前記第３の境界位置情報の示す位置が存在しない場合に、前記禁止関係であると判断することを特徴とする請求項１に記載の識別情報復号装置。
【請求項３】
前記判定手段は、各識別情報に対する前記判定にあたって、各々の前記成分符号に対応する前記第１及び第２の境界位置情報と前記第３の境界位置情報との間の関係が、前記第１又は第２の境界位置情報の示す位置と前記第３の境界位置情報の示す位置とが一致する合同関係であるか否か判断し、合同関係であると判断された成分符号の総数が予め定められた所定のしきい値を越える場合に、当該識別情報は前記結託攻撃に使用された結託耐性符号に対応するものであると判定することを特徴とする請求項１に記載の識別情報復号装置。
【請求項４】
前記検出手段は、前記第１の境界位置情報を、前記成分符号の上位ビット側からみたときのビット列のパターンの変化に基づいて検出し、前記第２の境界位置情報を、前記成分符号の下位ビット側からみたときのビット列のパターンの変化に基づいて検出することを特徴とする請求項１に記載の識別情報復号装置。
【請求項５】
前記判定手段により前記結託耐性符号に対応するものであると判定された１又は複数の前記識別情報に関する情報、又はいずれの識別情報も前記結託耐性符号に対応するものでないと判定された旨を示す情報を生成して出力する手段を更に備えたことを特徴とする請求項１に記載の識別情報復号装置。
【請求項６】
前記オブジェクトは、該オブジェクトがユーザへ渡されるのに先だってまたは該オブジェクトがユーザの利用に供されるのに先だって、前記ユーザに対応する識別情報に基づいて、該識別情報に対応する前記結託耐性符号を構成する前記成分符号の各々に対応させる第１の整数値を得る処理と、各々の前記成分符号を、それに対応する前記第１の整数値に従って生成する処理と、生成された前記成分符号を連接して前記結託耐性符号を生成する処理と、生成された前記結託耐性符号を埋め込む処理とが施されたものであり、
前記成分符号に対応する前記第３の境界位置情報は、当該成分符号に対応する前記第１の整数値であることを特徴とする請求項１に記載の識別情報復号装置。
【請求項７】
前記成分符号に対応する前記第１の整数値は、前記識別情報が示す第２の整数値を、当該成分符号に対応して予め定められた法を示す第３の整数値で除したときの剰余値であることを特徴とする請求項６に記載の識別情報復号装置。
【請求項８】
前記オブジェクトに埋め込まれる前記結託耐性符号を構成する前記複数の成分符号の各々は、連続する所定のビット数の１又は０のみからなるビット列を単位として、上位ビット側から、まず前記第２の整数値と同じ個数の０のみからなるビット列を連接し、続けて前記第３の整数値より１減じ更に前記第２の整数値を減じた値と同じ個数の１のみからなるビット列を連接してなる符号であることを特徴とする請求項７に記載の識別情報復号装置。
【請求項９】
前記検出手段は、０のみからなる単位ビット列と１を含む単位ビット列とが隣接する位置が存在する場合には、該位置を示す整数値を、前記第１の境界位置情報とし、１のみからなる単位ビット列と０を含む単位ビット列とが隣接する位置が存在する場合には、該位置を示す整数値を、前記第２の境界位置情報として求め、最上位ビットが０と１の混在する単位ビット列である場合には、整数値０を前記第１の境界位置情報とし、最下位ビットが０と１の混在する単位ビット列である場合には、前記第３の整数値より１減じた値を、前記第２の境界位置情報を０とすることを特徴とする請求項８に記載の識別情報復号装置。
【請求項１０】
前記検出手段は、前記成分符号が０のみからなる符号である場合には、前記第３の整数値より１減じた値を前記第１及び第２の境界位置情報とし、前記成分符号が１のみからなる符号である場合には、整数値０を前記第１及び第２の境界位置情報とすることを特徴とする請求項９に記載の識別情報復号装置。
【請求項１１】
前記オブジェクトから前記符号を抽出する手段を更に備えたことを特徴とする請求項１に記載の識別情報復号装置。
【請求項１２】
前記オブジェクトは、デジタルコンテンツの複製物であることを特徴とする請求項１ないし１１のいずれか１項に記載の識別情報復号装置。
【請求項１３】
前記結託耐性符号は、電子透かしによって前記デジタルコンテンツの複製物に埋め込まれたものであることを特徴とする請求項１２に記載の識別情報復号装置。
【請求項１４】
オブジェクトに埋め込まれた結託耐性符号に対応する識別情報を求める識別情報復号方法において、
対象となるオブジェクトから結託耐性符号として抽出された符号を入力するステップと、
入力された前記符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出するステップと、
対象となる各識別情報毎に、当該識別情報に対応する結託耐性符号を構成する複数の成分符号の各々について、ビット列のパターンが変化する境界位置に関する第３の境界位置情報を得るステップと、
対象となる各識別情報毎に、入力された前記符号を構成する前記複数の成分符号の各々について検出された複数組の前記第１及び第２の境界位置情報、並びに当該識別情報に対応する結託耐性符号を構成する複数の成分符号の各々について得られた複数の前記第３の境界位置情報に基づいて、当該識別情報が前記オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるか否か判定する判定ステップとを有し、
前記判定ステップは、各識別情報に対する前記判定にあたって、各々の前記成分符号に対応する前記第１及び第２の境界位置情報と前記第３の境界位置情報との間の関係が、発生し得ない禁止関係であるか否か判断し、少なくとも１つの成分符号において禁止関係であると判断された場合には、当該識別情報は前記結託攻撃に使用された結託耐性符号に対応するものではないと判定することを特徴とする識別情報復号方法。
【請求項１５】
前記判定ステップは、同一の前記成分符号について、前記第１の境界位置情報の示す位置と前記第２の境界位置情報の示す位置との間の範囲内に前記第３の境界位置情報の示す位置が存在しない場合に、前記禁止関係であると判断することを特徴とする請求項１４に記載の識別情報復号方法。
【請求項１６】
オブジェクトに埋め込まれた結託耐性符号に対応する識別情報を求める識別情報復号装置としてコンピュータを機能させるためのプログラムであって、
対象となるオブジェクトから結託耐性符号として抽出された符号を入力する機能と、
入力された前記符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出する機能と、
対象となる各識別情報毎に、当該識別情報に対応する結託耐性符号を構成する複数の成分符号の各々について、ビット列のパターンが変化する境界位置に関する第３の境界位置情報を得る機能と、
対象となる各識別情報毎に、入力された前記符号を構成する前記複数の成分符号の各々について検出された複数組の前記第１及び第２の境界位置情報、並びに当該識別情報に対応する結託耐性符号を構成する複数の成分符号の各々について得られた複数の前記第３の境界位置情報に基づいて、当該識別情報が前記オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるか否か判定するとともに、各識別情報に対する判定にあたって、各々の成分符号に対応する該第１及び第２の境界位置情報と該第３の境界位置情報との間の関係が、発生し得ない禁止関係であるか否か判断し、少なくとも１つの成分符号において禁止関係であると判断された場合には、当該識別情報は前記結託攻撃に使用された結託耐性符号に対応するものではないと判定する機能とをコンピュータに実現させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、識別情報に対応する結託耐性符号の埋め込まれたデジタルコンテンツの複製物に対する結託攻撃に用いられたデジタルコンテンツに埋め込まれていた結託耐性符号に対応する識別情報を求める識別情報復号装置及び識別情報復号方法に関する。
【０００２】
【従来の技術】
デジタルコンテンツ（例えば、静止画、動画、音声、音楽等）は、多数のデジタルデータで構成された構造を持つ。そして、その構造の中には、データを変更しても、当該デジタルコンテンツの作品の同一性あるいは経済的価値を保持できる部分がある。そのような許容された範囲内のデータを変更するによって、デジタルコンテンツに、種々の情報を埋め込むことができる。このような技術は、電子透かしと呼ばれる。
【０００３】
電子透かし技術によって、デジタルコンテンツに、様々な透かし情報（例えば、コンテンツの著作権者やユーザを識別する情報、著作権者の権利情報、コンテンツの利用条件、その利用時に必要な秘密情報、コピー制御情報等、あるいはそれらを組み合わせたものなど)を、様々な目的（例えば、利用制御、コピー制御を含む著作権保護、二次利用の促進等）で埋め込み、検出・利用することができる。
【０００４】
ここでは、例えば同一のデジタルコンテンツを多数のユーザを対象として配給するときに適用される技術として、デジタルコンテンツの複製物に、当該複製物を個々に識別するための情報（例えば、ユーザＩＤに一意に対応する透かし情報）を埋め込む場合を考える。
【０００５】
デジタルコンテンツの複製物に固有の識別情報（に対応する符号）を埋め込む手法は、そのデジタルコンテンツの複製物が更に複製されて海賊版として出回ったときに、該海賊版から識別情報を検出することによって流出元ユーザを特定することができることから、デジタルコンテンツの違法コピーに対する事前の抑制として機能するとともに、著作権侵害が発生したときの事後の救済にも役立つことになる。
【０００６】
また、あるユーザがデジタルコンテンツの複製物に埋め込まれた識別情報を無効するためには、ユーザにはどの部分が識別情報（に対応する符号）を構成するビットであるか分からないので、当該デジタルコンテンツの複製物に相当の改変を加える必要があり、そうすると、当該デジタルコンテンツの経済的価値を損なってしまうので、違法コピーの動機付けを奪うことができる。
【０００７】
このような状況において違法コピーを可能ならしめる方法として出現したのが、「結託攻撃（ｃｏｌｌｕｓｉｏｎ  ａｔｔａｃｋ）」である。
【０００８】
結託攻撃は、異なる複製物には異なる識別情報が埋めこまれていることを利用するものであり、例えば、複数人で複製物を持ちよって、それらをビット単位で比較することによって、デジタルデータの値が異なる部分を見つけ出し、その部分を改ざん（例えば、多数決、少数決、ランダマイズ等）することによって、識別情報を改ざん、消失させるという方法である（なお、具体的な比較操作は行わず、コンテンツ間で画素値を平均化するなどの操作を行って、同様の結果を得る場合もある）。
【０００９】
例えば簡単な例で示すと、Ａ氏、Ｂ氏、Ｃ氏の複製物にそれぞれ、
００…００…
００…１１…
１１…００…
という識別情報（に対応する符号）が埋め込まれていた場合に、例えば、
１０…０１…
という、Ａ氏、Ｂ氏、Ｃ氏のいずれとも異なる識別情報（に対応する符号）が埋め込まれたコンテンツを出現させることができてしまう。
【００１０】
そこで、結託攻撃に対する耐性、すなわち結託攻撃を受けても結託者の全部または一部を特定できるような性質を持つ符号（以下、結託耐性符号と呼ぶ）を電子透かしとして埋め込む方法および該結託耐性符号に基づく追跡アルゴリズム（ｔｒａｃｉｎｇ  ａｌｇｏｒｉｔｈｍ；結託攻撃に用いられたコンテンツに埋め込まれた識別番号を特定し、結託者のユーザＩＤを特定するためのアルゴリズム）が種々提案されている。例えば、その一つにｃ−ｓｅｃｕｒｅ符号がある(D. Boneh and J. Shaw, “Collusion-Secure Fingerprinting for Digital Data,” CRYPTO’95, 180-189, 1995.)。
【００１１】
【発明が解決しようとする課題】
結託攻撃に対する耐性をより強くする、すなわち結託者を特定できなくなる結託数の上限数をより増やすためには、コンテンツに埋め込む符号長をより長くする必要があり、一方、コンテンツに埋め込む符号長にも制限があるので、この種の結託耐性符号およびその結託耐性符号に基づく追跡アルゴリズムでは、符号長を削減するために、結託攻撃に利用された複製物の数に上限を設けている（なお、ｃ−ｓｅｃｕｒｅのｃは、高々ｃ個までの複製物を用いた結託攻撃に対して有効であるという意味である）。もし結託攻撃が許容されている個数を越える数の複製物を用いて行われた場合には、追跡アルゴリズムは、結託攻撃に関与した複製物の識別番号として、誤って、結託攻撃に関与したのではない複製物の識別番号を出力し、結託者でないものが結託者として特定されてしまう、という誤判定が発生することがあり得る。
【００１２】
誤判定の確率を下げるためには、現実的に結託者が準備することができそうな複製物の個数を想像し、その個数以上の許容個数となるように結託耐性符号を設計するより他なく、どうしても、大きな許容個数を設定することになってしまい、その結果、符号長も大きくなってしまうという問題点がある。
【００１３】
本発明は、上記事情を考慮してなされたもので、結託耐性符号による識別情報が埋め込まれたオブジェクト（例えば、デジタルコンテンツの複製物）に対する結託攻撃に用いられたオブジェクトの識別情報を、より短い符号長により推測可能とした識別情報復号装置及び識別情報復号方法を提供することを目的とする。
【００１４】
【課題を解決するための手段】
本発明は、オブジェクトに埋め込まれた結託耐性符号に対応する識別情報を求める識別情報復号装置において、対象となるオブジェクトから結託耐性符号として検出された符号を入力する手段と、入力された前記符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出する検出手段と、対象となる各識別情報毎に、当該識別情報に対応する結託耐性符号を構成する複数の成分符号の各々について、ビット列のパターンが変化する境界位置に関する第３の境界位置情報を得る手段と、対象となる各識別情報毎に、入力された前記符号を構成する前記複数の成分符号の各々について検出された複数組の前記第１及び第２の境界位置情報、並びに当該識別情報に対応する結託耐性符号を構成する複数の成分符号の各々について得られた複数の前記第３の境界位置情報に基づいて、当該識別情報が前記オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるか否か判定する判定手段とを備え、前記判定手段は、各識別情報に対する前記判定にあたって、各々の前記成分符号に対応する前記第１及び第２の境界位置情報と前記第３の境界位置情報との間の関係が、発生し得ない禁止関係であるか否か判断し、少なくとも１つの成分符号において禁止関係であると判断された場合には、当該識別情報は前記結託攻撃に使用された結託耐性符号に対応するものではないと判定することを特徴とする。
【００１５】
好ましくは、前記判定手段は、同一の前記成分符号について、前記第１の境界位置情報の示す位置と前記第２の境界位置情報の示す位置との間の範囲内に前記第３の境界位置情報の示す位置が存在しない場合に、前記禁止関係であると判断するようにしてもよい。
【００１６】
好ましくは、前記判定手段は、各識別情報に対する前記判定にあたって、各々の前記成分符号に対応する前記第１及び第２の境界位置情報と前記第３の境界位置情報との間の関係が、前記第１又は第２の境界位置情報の示す位置と前記第３の境界位置情報の示す位置とが一致する合同関係であるか否か判断し、合同関係であると判断された成分符号の総数が予め定められた所定のしきい値を越える場合に、当該識別情報は前記結託攻撃に使用された結託耐性符号に対応するものであると判定するようにしてもよい。
【００１７】
好ましくは、前記オブジェクトは、該オブジェクトがユーザへ渡されるのに先だってまたは該オブジェクトがユーザの利用に供されるのに先だって、前記ユーザに対応する識別情報に基づいて、該識別情報に対応する前記結託耐性符号を構成する前記成分符号の各々に対応させる第１の整数値を得る処理と、各々の前記成分符号を、それに対応する前記第１の整数値に従って生成する処理と、生成された前記成分符号を連接して前記結託耐性符号を生成する処理と、生成された前記結託耐性符号を埋め込む処理とが施されたものであり、前記成分符号に対応する前記第３の境界位置情報は、当該成分符号に対応する前記第１の整数値であるようにしてもよい。
【００１８】
また、本発明は、オブジェクトに埋め込まれた結託耐性符号に対応する識別情報を求める識別情報復号方法において、対象となるオブジェクトから結託耐性符号として検出された符号を入力するステップと、入力された前記符号を構成する複数の成分符号の各々について、当該成分符号のビット列のパターンに対する改ざん部分の上位ビット側の境界位置に関係する第１の境界位置情報及び下位ビット側の境界位置に関係する第２の境界位置情報を検出するステップと、対象となる各識別情報毎に、当該識別情報に対応する結託耐性符号を構成する複数の成分符号の各々について、ビット列のパターンが変化する境界位置に関する第３の境界位置情報を得るステップと、対象となる各識別情報毎に、入力された前記符号を構成する前記複数の成分符号の各々について検出された複数組の前記第１及び第２の境界位置情報、並びに当該識別情報に対応する結託耐性符号を構成する複数の成分符号の各々について得られた複数の前記第３の境界位置情報に基づいて、当該識別情報が前記オブジェクトに対する結託攻撃に使用された結託耐性符号に対応するものであるか否か判定する判定ステップとを有し、前記判定ステップは、各識別情報に対する前記判定にあたって、各々の前記成分符号に対応する前記第１及び第２の境界位置情報と前記第３の境界位置情報との間の関係が、発生し得ない禁止関係であるか否か判断し、少なくとも１つの成分符号において禁止関係であると判断された場合には、当該識別情報は前記結託攻撃に使用された結託耐性符号に対応するものではないと判定することを特徴とする。
【００１９】
なお、装置に係る本発明は方法に係る発明としても成立し、方法に係る本発明は装置に係る発明としても成立する。
また、装置または方法に係る本発明は、コンピュータに当該発明に相当する手順を実行させるための（あるいはコンピュータを当該発明に相当する手段として機能させるための、あるいはコンピュータに当該発明に相当する機能を実現させるための）プログラムとしても成立し、該プログラムを記録したコンピュータ読取り可能な記録媒体としても成立する。
【００２０】
本発明によれば、識別情報に対応する結託耐性符号の埋め込まれたデジタルコンテンツの複製物に対する結託攻撃に用いられたデジタルコンテンツに埋め込まれていた結託耐性符号に対応する識別情報を、（例えば同じ誤検出率を考えたときに）より短い符号長により推測することができる。
【００２１】
【発明の実施の形態】
以下、図面を参照しながら発明の実施の形態を説明する。
【００２２】
まず、同一のデジタルコンテンツの複製物（例えば、静止画、動画、音声、音楽等）の各々に対して、当該複製物ごとに異なる識別情報を透かし情報として埋め込み、追跡する場合について説明する。以下では、識別情報として、当該複製物に対応するユーザすなわち当該複製物を利用することになるユーザ（例えば、当該複製物を記録媒体若しくは通信媒体を媒介として譲渡し又は貸し渡すユーザ）のユーザ識別子（ユーザＩＤ）を用いる場合を主として説明するが、ユーザＩＤに対して所定の変換を施したものを識別情報としてもよいし、ユーザＩＤ以外の情報又はこれを変換したものを識別情報としてもよい。なお、ユーザＩＤには、利用の日時や利用場所等の情報を含めても良い。
【００２３】
もちろん、デジタルコンテンツの複製物に対して、さらに、その他の様々な透かし情報（例えば、コンテンツの著作権者に関する情報、著作権等の権利に関する情報、コンテンツの利用条件に関する情報、その利用時に必要な秘密情報、コピー制御情報等、あるいはそれらを組み合わせたものなど)を様々な目的（例えば、利用制御、コピー制御を含む著作権保護、二次利用の促進等）が埋め込まれ、検出されてもよいが、その他の透かし情報を利用する場合における当該その他の透かし情報に関係する部分の構成は任意である。
【００２４】
以下で示す構成図は、装置の機能ブロック図としても成立し、また、ソフトウェア（プログラム）の機能モジュール図あるいは手順図としても成立するものである。
【００２５】
図１に、本発明の実施の形態に係る電子透かし埋込装置と電子透かし解析装置が適用されるシステムの概念図を示す。
【００２６】
電子透かし埋込装置１と電子透かし解析装置２は、例えば、コンテンツ提供側に備えられ、管理される。
また、例えば、電子透かし埋込装置１は、ユーザ側に備えられ（例えば、コンテンツを利用するためのユーザ・システム（例えば、計算機システムや専用機器等に接続されあるいは組み込まれるなど）、電子透かし解析装置２は、コンテンツ提供側に備えられるようにしてもよい。
デジタルコンテンツの複製物への透かし情報の埋め込みは、前者の場合、該複製物がユーザへ渡されるのに先だって行われ、後者の場合、該複製物がユーザの利用に供されるのに先だって行われることになる。
【００２７】
電子透かし埋込装置１においてデジタルコンテンツに所望の透かしデータを埋め込む方法や、電子透かし解析装置２においてデジタルコンテンツから該透かしデータ自体を取り出す方法は、どのような方法であってもよい（例えば、“松井甲子雄著、「電子透かしの基礎」、森北出版、１９９８年”等参照）。
電子透かし埋込装置１は、ソフトウェア（プログラム）としてもハードウェアとしても実現可能である。同様に、電子透かし解析装置２は、ソフトウェア（プログラム）としてもハードウェアとしても実現可能である。また、電子透かし埋込装置１および電子透かし解析装置２をコンテンツ提供側で用いる場合には、それらを一体化して実現することも可能である。
【００２８】
図２に、電子透かし埋込装置１の構成例を示す。この電子透かし埋込装置１は、埋め込むべき識別情報（例えば、ユーザＩＤ）に対応する結託耐性符号を生成する符号生成部１１と、生成された結託耐性符号（埋め込み符号）を対象コンテンツに埋め込む符号埋込部１２とから構成される。
【００２９】
電子透かし埋込装置１は、対象コンテンツと、これに埋め込むべき識別情報（例えば、対象ユーザのユーザＩＤ）とが与えられると、該識別情報に対応する結託耐性符号を生成し、該結託耐性符号が埋め込まれたコンテンツを、該識別情報に対応する複製物（例えば、該ユーザＩＤのユーザ向けの複製物）として出力する。他の透かし情報を利用する場合には、その際に、必要に応じて他の透かし情報が埋め込まれる。
【００３０】
なお、例えば、識別情報≠ユーザＩＤであって、かつ、ユーザＩＤが与えられるような場合には、与えられたユーザＩＤを識別情報に変換する、などの前処理を行う。
【００３１】
電子透かし埋込装置１により得られた当該識別情報に対応するコンテンツの複製物は、記憶媒体や通信媒体などを媒介とした流通経路３を経てそれぞれ流通する。複数の複製物を用いた結託攻撃は、この流通経路３にて行われる。
【００３２】
図３に、電子透かし解析装置２の構成例を示す。
【００３３】
図３に示されるように、電子透かし解析装置２は、符号抽出部２１と、復号部２２とを備えている。
【００３４】
符号抽出部２１は、検出対象となるコンテンツの複製物から埋め込み符号を抽出する（結託攻撃の有無にかかわらず、結託攻撃が無かった場合の結託耐性符号が埋め込まれているものとして符号を抽出する）。実際には、埋め込まれた結託耐性符号が抽出される場合だけでなく、結託攻撃が施されて改ざんされたものが抽出される場合もある。
【００３５】
復号部２２は、抽出された符号に対して、後述する追跡アルゴリズムを実行することによって、結託攻撃がなかったこと、または結託攻撃に用いられたであろう複製物に埋め込まれていた結託耐性符号に対応する識別情報（例えば、ユーザＩＤ）を特定（あるいは推測）する。
【００３６】
なお、例えば、識別情報≠ユーザＩＤであって、ユーザＩＤを求める必要があるような場合には、特定された識別情報を、さらに、ユーザＩＤに変換する、などの後処理を行う。
【００３７】
以下では、電子透かし埋込装置１についてより詳細に説明する。
【００３８】
ここでは、識別情報＝ユーザＩＤの場合を例にとって説明する。
【００３９】
図４に、概略的な手順の一例を示す。
【００４０】
符号生成部１１は、まず、対象複製物に、埋め込むべきユーザＩＤに対応する、Ｍ（Ｍは複数）個の整数Ａ（１）、Ａ（２）、…、Ａ（Ｍ）を求める（ステップＳ１）。該Ｍ個の整数は、予め求めて記憶しておく方法と、必要時に求める方法とがある。
【００４１】
整数Ａ（１）、Ａ（２）、…、Ａ（Ｍ）の設定の仕方は、様々な方法がある。
【００４２】
例えば、各ｉ（ｉ＝１〜Ｍ）におけるそれぞれの整数Ａ（ｉ）が、０〜Ｎ（ｉ）−１のいずれかの値を取るようにしてもよい。ここで、Ｎ（１）、Ｎ（２）、…、Ｎ（Ｍ）は、例えば、予め定められた相互に異なる正整数（より好ましくは、互いに素の関係にある正数）である。
【００４３】
その際、ユーザＩＤに対応するＭ個の整数Ａ（ｉ）の各々には、０〜Ｎ（ｉ）−１の範囲でランダムに値を割り当てる方法と、０〜Ｎ（ｉ）−１の範囲で一定の規則に従って値を割り当てる方法とがある。また、いずれの場合についても、各ユーザＩＤには、互いにＡ（１）、Ａ（２）、…、Ａ（Ｍ）のうちの少なくとも一つが相違するように、Ｍ個の正数の組を排他的に割り当てる方法と、Ａ（１）、Ａ（２）、…、Ａ（Ｍ）のすべてを同一とするＭ個の整数の組を複数のユーザＩＤに重複に割当てることを許す方法とがある。
【００４４】
排他的に値を割り当てる方法には、例えば、ユーザＩＤの値として、０〜Ｎ（１）×Ｎ（２）×・・・×Ｎ（Ｍ）−１の範囲の整数の全部または一部を使用するものとし、Ｍ個の整数Ａ（ｉ）の各々について、対象ユーザＩＤをＮ（ｉ）で割ったときの余りを、該ユーザＩＤに対応するＡ（ｉ）の値とする方法がある。
【００４５】
なお、上記の代わりに、例えば、識別情報≠ユーザＩＤのようにする場合に、ユーザＩＤに所定の変換を施すことによって、その変換値＝識別情報が０〜Ｎ（１）×Ｎ（２）×・・・×Ｎ（Ｍ）−１のうちの使用すべき範囲内の整数になるような所定の変換を用意し、対象ユーザＩＤに対して該所定の変換を施して得た識別情報をＮ（ｉ）で割ったときの余りを、該ユーザＩＤに対応する識別情報に対応するＡ（ｉ）の値とする方法もある（この場合、復号部２２では、まず、ユーザＩＤに対応する識別情報が得られるので、ユーザＩＤを求める必要があるならば、復号部２２等において、得られた当該識別情報に上記の所定の変換に対する逆変換を施して、対応するユーザＩＤを求めることになる）。
【００４６】
また、ここでは、コンテンツの複製物に、ユーザＩＤに対応する符号を埋め込む場合を例にとって説明しているが、その代わりに、例えば、コンテンツの複製物の複製物ＩＤとそのユーザを特定するための情報（例えば、ユーザ名、あるいはユーザＩＤ等）との対応を示す情報を所定の記憶装置に記録しておき、識別情報＝複製物ＩＤとして、コンテンツの複製物に、そのユーザのユーザＩＤに対応する複製物ＩＤに対応する符号を埋め込むようにしてもよい（この場合、復号部２２では、まず、ユーザＩＤに対応する複製物ＩＤが得られるので、ユーザＩＤを求める必要があるならば、復号部２２等において、得られた当該複製物ＩＤから、対応するユーザＩＤを求めることになる）。
また、例えば、上記のようにユーザＩＤに対応する複製物ＩＤに対応する符号を埋め込むようにする場合であって、かつ、識別情報≠複製物ＩＤのようにする場合に、ユーザＩＤに対応する複製物ＩＤに所定の変換を施して得た識別情報をＮ（ｉ）で割ったときの余りを、該ユーザＩＤに対応する複製物ＩＤに対応する識別情報に対応するＡ（ｉ）の値とする方法もある（この場合、復号部２２では、まず、識別情報が得られるので、ユーザＩＤを求める必要があるならば、復号部２２等において、得られた当該識別情報に上記の所定の変換に対する逆変換を施して、対応する複製物ＩＤを求め、該複製物ＩＤからユーザＩＤを求めることになる）。
【００４７】
さて、次に、符号生成部１１は、対象複製物に埋め込むべきユーザＩＤ（識別情報）に対応する、Ｍ個の整数Ａ（１）、Ａ（２）、…、Ａ（Ｍ）から、該ユーザＩＤに対応する結託耐性符号を生成する（ステップＳ２）。各ユーザＩＤに対応する結託耐性符号は、予め生成して記憶しておく方法と、必要時に生成する方法とがある。
【００４８】
各ユーザＩＤに対応する結託耐性符号は、該ユーザＩＤに対応するＭ個の整数Ａ（１）、Ａ（２）、…、Ａ（Ｍ）の各々について、対応する成分符号Ｗ（１）、Ｗ（２）、…、Ｗ（Ｍ）を求め、それらを連結することによって生成する。
【００４９】
整数Ａ（ｉ）に対応する成分符号Ｗ（ｉ）としては、例えば、Γ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＝４となる。
【００７７】
なお、第ｉ番目の成分符号Ｗ（ｉ）が０のみからなる場合には、ｒ(-)i＝ｒ(+)i＝Ｎ（ｉ）−１となる。
また、第ｉ番目の成分符号Ｗ（ｉ）が１のみからなる場合には、ｒ(-)i＝ｒ(+)i＝０となる。
【００７８】
また、０のみからなる要素Ｂ（s1−１）と１を含む要素Ｂ（s1）との境界がない場合には、ｒ(-)i＝０となる。
また、１のみからなる要素Ｂ（s2）と０を含む要素Ｂ（s2−１）との境界がない場合には、ｒ(+)i＝Ｎ（ｉ）−１となる。
【００７９】
このように１つの成分符号Ｗ（ｉ）から、１対の位置情報ｒ(-)i，ｒ(+)iが得られる。これらｒ(-)iとｒ(+)iとの対を、剰余対と呼ぶ。
【００８０】
さて、追跡アルゴリズムでは、検出された符号の各々の成分符号を調べ、予め定められたｄ（上記の例の場合、３）ビット未満の数の１や０が孤立して存在する成分符号が検出された場合に、結託攻撃がなされたものと判断することができる。また、この場合に、（結託数が予め規定された許容数以下であったものと仮定して）全成分符号Ｗ（ｉ）から得られた剰余対ｒ(-)i，ｒ(+)iの組（ｉ＝１〜Ｍ）に基づいて、結託攻撃に使用された複製物に埋め込まれていたであろう結託耐性符号に対応するユーザＩＤを求め、これを結託攻撃を行った結託者のユーザＩＤとして特定することができる。
【００８１】
各々のＡ（ｉ）に対応する成分符号Ｍ（ｉ）は、例えば、先に例示したもの、すなわち、
Ａ（３）＝０：  Ｗ３＝１１１  １１１  １１１  １１１  １１１  １１１
Ａ（３）＝１：  Ｗ３＝０００  １１１  １１１  １１１  １１１  １１１
Ａ（３）＝２：  Ｗ３＝０００  ０００  １１１  １１１  １１１  １１１
Ａ（３）＝３：  Ｗ３＝０００  ０００  ０００  １１１  １１１  １１１
Ａ（３）＝４：  Ｗ３＝０００  ０００  ０００  ０００  １１１  １１１
Ａ（３）＝５：  Ｗ３＝０００  ０００  ０００  ０００  ０００  １１１
Ａ（３）＝６：  Ｗ３＝０００  ０００  ０００  ０００  ０００  ０００
を比較して分かるように、その性質上、複数の複製物から得られる相違部分は、必ず連続した要素Ｂとして得られることがわかる（したがって、結託攻撃による改ざんによって、この連続した部分に０と１が混在してくることになる）。
【００８２】
そして、ある成分符号（ｉ）において、そのｄビット未満の数の１や０が孤立して存在する連続した部分の左端の位置と右端の位置、すなわちｒ(-)iとｒ(+)iは、必ず、結託攻撃に用いられた複数の複製物のいずれかに埋め込まれた結託耐性符号の対応する成分符号の０と１の区切り目の位置（成分符号がすべて１の場合は、該成分符号の左端の位置、すべて０の場合は、該成分符号の右端の位置）すなわちｒ(-)i＝ｒ(+)iに一致することがわかる。このような情報が、各成分符号Ｗ（ｉ）毎に得られる。それら情報ｒ(-)1、ｒ(+)1、ｒ(-)2、ｒ(+)2、…、ｒi(-)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の全ては得られないことがある。しかし、一方で、ある複製物に埋め込まれた結託耐性符号について、多数の成分符号について本来の境界位置ｒ(-)i＝ｒ(+)iが得られることが期待される。よって、対象コンテンツから検出された符号から得られたｒ(-)1、ｒ(-)2、…、ｒ(-)M、ｒ(+)1、ｒ(+)2、…、ｒ(+)Mを適宜組み合わせて検証することによって、かりにすべての結託者のユーザＩＤが特定できなかったとしても、一部の結託者のユーザＩＤを特定することができる。
【００８６】
これが追跡アルゴリズムの基本的な考え方である。
【００８７】
ところで、従来の追跡アルゴリズムは、ｒ(-)1、ｒ(-)2、…、ｒ(-)M、ｒ(+)1、ｒ(+)2、…、ｒ(+)Mのうちから選択された幾つかのものが、あるユーザＩＤを示していれば、それを結託者のユーザＩＤとして出力するものである。しかしながら、該選択された幾つかのものが実際には一人のユーザにのみ属するものではなく、複数のユーザに分属するものである場合には、結託者でないユーザのユーザＩＤが偶然に出力されてしまう。そこで、そのような誤検出の確率を一定以下に抑えるために、成分符号の個数（Ｍ）をより多く使う必要があり、符号長が長くなってしまうという問題があった。
【００８８】
本実施形態は、電子透かし解析装置２の復号部２２による追跡アルゴリズムを工夫することによって、従来よりも符号長をより短く（成分符号の個数（Ｍ）をより少なく）することを可能にするものである。
【００８９】
以下、本実施形態の電子透かし解析装置２の復号部２２について詳しく説明する。
【００９０】
前述したように、ここでは、識別情報＝ユーザＩＤである場合を例にとって説明している。
【００９１】
なお、成分符号を内符号とも呼ぶ。
【００９２】
図１１に、本実施形態の電子透かし解析装置２の復号部２２の構成例を示す。
【００９３】
図１１に示されるように、復号部２２は、検出対象のコンテンツから読み出された符号（埋め込まれた結託耐性符号、あるいは結託攻撃が施されて改ざんされたもの）を入力し、各成分符号Ｗ（ｉ）から得られる剰余対ｒ(-)ｉ，ｒ(+)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）を入力し、対応する第ｖ識別情報について追跡し（結託攻撃に使用されたものか否かを調べ）、第ｖ識別情報に対する追跡結果を出力する。第ｖ識別情報に対する追跡結果は、第ｖ識別情報が追跡されたか否か（結託攻撃に使用されたと推測されたか、結託攻撃に使用されなかったと推測されたか）を示す情報である。
【０１１３】
なお、例えば、図８、図９の例では、第１識別情報＝０、第２識別情報＝１、…、第１５識別情報＝１４である。
【０１１４】
追跡識別情報出力部２２２２は、各識別情報追跡部２２２１−１〜２２２１−Ｌによりそれぞれ得られた第１識別情報に対する追跡結果〜第Ｌ識別情報に対する追跡結果を統合し、最終的な追跡結果を生成して、出力する。最終的な追跡結果は、例えば、追跡された（結託攻撃に使用されたと推測された）識別情報がある場合には、追跡された識別情報の全部又は一部を含むリスト情報、追跡された識別情報がない場合には、その旨を示す情報である。
【０１１５】
次に、外符号復号部２２２の識別情報追跡部２２２１−１〜２２２１−Ｌについて説明する。
【０１１６】
第ｖ識別情報追跡部２２２１−ｖは、検出された符号の各成分符号Ｗ（１）〜Ｗ（Ｍ）から得られた剰余対の組、すなわち、
ｒ(-)1，ｒ(+)1，ｒ(-)2，ｒ(+)2，…，ｒ(-)M，ｒ(+)M
を入力し、それらと、第ｖ識別情報（＝Ｖ）に対応する結託耐性符号の各成分符号Ｗ（１）〜Ｗ（Ｍ）における本来の０からなるブロックと１からなるブロックの境界位置（ただし、成分符号が０のみからなる場合には左の端の位置、成分符号が０のみからなる場合には右の端の位置）を示す値、
ｒ(0)1〜ｒ(0)M
とを比較することによって、第ｖ識別情報が追跡されたか否かを判定する。
【０１１７】
なお、先の例では、ｐ1＝Ｎ（１）、ｐ2＝Ｎ（２）、…、ｐM＝Ｎ（Ｍ）とし、Ｖ％ｐiはＶをｐiで割ったときの剰余を示すとして、
ｒ(0)1＝Ｖ％ｐ1 
ｒ(0)2＝Ｖ％ｐ2 
：
ｒ(0)M＝Ｖ％ｐM
である。
【０１１８】
本実施形態では、上記の比較・判定において、従来よりも結託耐性符号の符号長をより短く（成分符号の個数（Ｍ）をより少なく）できるように、後述するような処理を行う。
【０１１９】
図１６に、外符号復号部２２２の第ｖ識別情報追跡部２２２１−ｖの構成例を示す。なお、第ｖ識別情報追跡部２２２１−ｖを代表させて記述しているが、識別情報追跡部２２２１−１〜２２２１−Ｌのいずれも基本的には同様の構成である。
【０１２０】
図１６に示されるように、外符号復号部２２２の第ｖ識別情報追跡部２２２１−ｖは、検出された符号の各成分符号Ｗ（１）〜Ｗ（Ｍ）からそれぞれ得られた第１剰余対〜第Ｍ剰余対にそれぞれ対応して設けられる複数（Ｍ個）の合同性判定部２２２１１−１〜２２２１１−Ｍと、全合同性判定に基づいて総合判定を行う総合判定部２２２１２とを含む。
【０１２１】
第ｙ合同性判定部２２２１１−ｙは、第ｖ識別情報と、第ｙ剰余対（ｒ(-)y，ｒ(+)y）との間が、合同関係にあるか否か、禁止関係にあるか、それ以外の関係にあるかを判定し、その判定結果を示す情報を出力する。
【０１２２】
図１７に、外符号復号部２２２の第ｖ識別情報追跡部２２２１−ｖにおける第ｙ合同性判定部２２２１１−ｙの構成例を示す。なお、第ｙ合同性判定部２２２１１−ｙを代表させて記述しているが、合同性判定部２２２１１−１〜２２２１１−Ｍのいずれも基本的には同様の構成である。
【０１２３】
図１７に示されるように、第ｙ合同性判定部２２２１１−ｙは、第ｖ識別情報（＝Ｖ）に対応する結託耐性符号の第ｙ成分符号Ｗ（ｙ）における本来の境界位置情報すなわち基準となる剰余ｒ(0)yを生成する基準剰余生成部２２２１１１と、ｒ(0)yとｒ(-)yとの大小関係を比較する第１の大小関係比較部２２２１１２と、ｒ(0)yとｒ(+)yとの大小関係を比較する第２の大小関係比較部２２２１１３と、それら大小関係の比較結果に基づいて、合同性・禁止性について判定する合同性・禁止性判定部２２２１１４とを含む。
【０１２４】
基準剰余生成部２２２１１１は、第ｖ識別情報（＝Ｖ）に対応する剰余ｒ(0)yを生成する。基準剰余生成部２２２１１１の生成方法は、識別情報から結託耐性符号を生成する方法に応じたものになる。
【０１２５】
先の例では、第ｖ識別情報追跡部２２２１−ｖには、第ｖ識別情報（この例では、第ｖ識別情報＝Ｖ＝ユーザＩＤ＝ｖ−１である）が割り当てられ、かつ、その第ｙ合同性判定部２２２１１−ｙには、正整数ｐy（この例では、ｐy＝Ｎ（ｙ））が割り当てられ、第ｖ識別情報追跡部２２２１−ｖの第ｙ合同性判定部２２２１１−ｙの基準剰余生成部２２２１１１では、基準剰余ｒ(0)yとして、
ｒ(0)y＝Ｖ％ｐy 
が生成される。
【０１２６】
例えば、先の図８、図９の例で、ユーザＩＤ＝２に対する追跡については（なお、ユーザＩＤ＝２に対応する結託耐性符号＝、
000000  000000111111  000000111111111111  ）、
第３識別情報追跡部２２２１−３の第１合同性判定部２２２１１−１の基準剰余生成部２２２１１１では（Ｖ＝ユーザＩＤ＝２、ｐ1＝Ｎ（１）＝３から）、
ｒ(0)1＝２％３＝２
が生成され、
第２合同性判定部２２２１１−２の基準剰余生成部２２２１１１では（Ｖ＝ユーザＩＤ＝２、ｐ2＝Ｎ（２）＝５から）、
ｒ(0)2＝２％５＝２
が生成され、
第３合同性判定部２２２１１−３の基準剰余生成部２２２１１１では（Ｖ＝ユーザＩＤ＝２、ｐ3＝Ｎ（３）＝７から）、
ｒ(0)3＝２％７＝２
が生成される。
【０１２７】
同様に、先の図８、図９の例で、ユーザＩＤ＝３に対する追跡については（なお、ユーザＩＤ＝３に対応する結託耐性符号＝、
111111  000000000111  000000000111111111  ）、
第４識別情報追跡部２２２１−４の第１〜第３合同性判定部２２２１１−１〜３の各基準剰余生成部２２２１１１で、
ｒ(0)1＝３％３＝０
ｒ(0)2＝３％５＝３
ｒ(0)3＝３％７＝３
がそれぞれ生成される。
【０１２８】
このようにして第ｖ識別情報追跡部２２２１−ｖの第ｙ合同性判定部２２２１１−ｙの基準剰余生成部２２２１１１で生成された基準剰余ｒ(0)yは、第１の大小関係比較部２２２１１２及び第２の大小関係比較部２２２１１３に与えられる。
【０１２９】
なお、上記では、基準剰余生成部２２２１１１は、計算によって基準剰余ｒ(0)yを生成する例を示したが、あらかじめ用意しておいた対応テーブルを参照して求めるようにしてもよい。また、与えられるＶの値とｐyの値が固定されているなどによって、出力すべきｒ(0)yの値が予め決まっている場合には、そのｒ(0)yを記憶しておいて、必要時にこれを出力するようにしてもよい。
【０１３０】
次に、第１の大小関係比較部２２２１１２及び第２の大小関係比較部２２２１１３によって、ｒ(0)yとｒ(-)yとの大小関係の比較及びｒ(0)yとｒ(+)yとの大小関係の比較が行われる。なお、両比較は、いずれを先に行ってもよいし、同時にあるいは並列的に行ってもよい。
【０１３１】
第１の大小関係比較部２２２１１２は、与えられたｒ(0)yとｒ(-)yとを比較して、ｒ(-)y＞ｒ(0)yであるか、ｒ(-)y＝ｒ(0)yであるか、ｒ(-)y＜ｒ(0)yであるかを調べ、その比較結果（以下、ｒ(-)y＞ｒ(0)yである場合を“＞”、ｒ(-)y＝ｒ(0)yである場合を“＝”、ｒ(-)y＜ｒ(0)yである場合を“＜”でそれぞれ表すものとする）を出力する。
【０１３２】
同様に、第２の大小関係比較部２２２１１３は、与えられたｒ(0)yとｒ(+)yとを比較して、ｒ(+)y＞ｒ(0)yであるか、ｒ(+)y＝ｒ(0)yであるか、ｒ(+)y＜ｒ(0)yであるかを調べ、その比較結果（以下、ｒ(+)y＞ｒ(0)yである場合を“＞”、ｒ(+)y＝ｒ(0)yである場合を“＝”、ｒ(+)y＜ｒ(0)yである場合を“＜”でそれぞれ表すものとする）を出力する。
【０１３３】
第１の大小関係比較部２２２１１２による判定結果（第１の大小関係（−））及び大小関係比較部２２２１１３による判定結果（第２の大小関係（＋）は、合同性・禁止性判定部２２２１１４に与えられる。
【０１３４】
ここで、第１の大小関係と第２の大小関係との組合せ（第１の大小関係，第２の大小関係）は、次の通りとなる。
（＞，＞）
（＜，＜）
（＝，＞）
（＜，＝）
（＜，＞）
（＝，＝）
次に、合同性・禁止性判定部２２２１１４は、第１判定結果と第２判定結果との組合せに基づいて、合同性・禁止性判定を行い、合同性・禁止性判定結果を出力する。
【０１３５】
図１８に、合同性・禁止性判定部２２２１１４による合同性・禁止性判定の処理手順の一例を示す。
【０１３６】
まず、第１の大小関係及び第２の大小関係を入力する（ステップＳ１１）。
【０１３７】
（第１の大小関係，第２の大小関係）が、（＜，＜）または（＞，＞）である場合には（ステップＳ１２）、合同性・禁止性判定結果として、禁止関係にある旨を出力する（ステップＳ１３）。
【０１３８】
（第１の大小関係，第２の大小関係）が、（＝，＜）または（＞，＝）である場合には（ステップＳ１４，Ｓ１５）、合同性・禁止性判定結果として、合同関係にある旨を出力する（ステップＳ１６）。
【０１３９】
それ以外の場合には（ステップＳ１５）、合同性・禁止性判定結果として、その他である旨を出力する（ステップＳ１７）。
【０１４０】
なお、（第１の大小関係，第２の大小関係）が、（＝，＝）である場合にも、合同関係にある旨を出力するようにする構成を採用してもよい。
【０１４１】
ここで、ｒ(-)yまたはｒ(+)yと、ｒ(0)yとの間が合同関係にあると判定されたということは、当該追跡対象の識別情報に対応する結託耐性符号が結託攻撃に使用されたものである可能性を示唆している（なお、全剰余対についてみたときに、合同関係にあると判定された剰余対の個数が多いほど、当該追跡対象の識別情報に対応する結託耐性符号が結託攻撃に使用されたものである可能性が高くなる）。
【０１４２】
一方、本実施形態では、禁止関係という考え方を導入している。すなわち、結託攻撃を行った場合に、結託攻撃に使用された結託耐性符号のある成分符号における本来の境界位置（基準剰余ｒ(0)i）は、その性質上、結託攻撃後のある成分符号Ｗ（ｉ）における剰余対ｒ(-)i，ｒ(+)iに対して、かならず、ｒ(0)i＝ｒ(-)i、または、ｒ(0)i＝ｒ(+)i、または、ｒ(-)i＜ｒ(0)i＜ｒ(+)iとなる（かりに、ｒ(0)i＜ｒ(-)iまたはｒ(0)i＞ｒ(+)iであるとすると、そのｒ(0)iが、ｒ(-)iまたはｒ(+)iでなければならないので、矛盾する）。したがって、（第１の大小関係，第２の大小関係）が、（＜，＜）または（＞，＞）である場合には、当該追跡対象の識別情報に対応する結託耐性符号が結託攻撃に使用されていないことになるので、当該追跡対象の識別情報を追跡結果として出力することを禁止するために（当該追跡対象の識別情報を追跡結果として出力すると誤検出になる）、これを禁止関係にあるものとした。
【０１４３】
さて、第ｖ識別情報追跡部２２２１−ｖにおいて合同性・禁止性判定結果が得られると、総合判定部２２２１２は、それら全合同性・禁止性判定結果に基づいて、当該第ｖ識別情報が追跡されたか否かについての総合判定を行う。
【０１４４】
図１９に、第ｖ識別情報追跡部２２２１−ｖの総合判定部２２２１２による総合判定の処理手順の一例を示す。なお、第ｖ識別情報追跡部２２２１−ｖの総合判定部２２２１２を代表させて記述しているが、第ｖ識別情報追跡部２２２１−１の総合判定部２２２１２〜第ｖ識別情報追跡部２２２１−Ｌの総合判定部２２２１２のいずれも基本的には同様の構成である。
【０１４５】
まず、各合同性判定部２２２１１−１〜２２２１１−Ｍが出力した合同性・禁止性判定結果（「合同」、「禁止」又は「その他」）を入力する（ステップＳ２１）。
【０１４６】
次に、全合同性・禁止性判定結果のうちに、「禁止」が存在するか否かを判定する（ステップＳ２２）。
【０１４７】
禁止が存在する場合には、追跡結果として、第ｖ識別情報は追跡されなかった旨を示す情報を出力する（ステップＳ２３）。
【０１４８】
禁止が存在しなかった場合には、「合同」の総数を求める（ステップＳ２４）。
【０１４９】
そして、「合同」の総数が所定のしきい値を越えるか否か判定する（ステップＳ２５）。
【０１５０】
「合同」の総数が所定のしきい値を越える場合には、追跡結果として、第ｖ識別情報は追跡された旨を示す情報を出力する（ステップＳ２６）。
【０１５１】
「合同」の総数が所定のしきい値を越えない場合には、追跡結果として、第ｖ識別情報は追跡されなかった旨を示す情報を出力する（ステップＳ２７）。
【０１５２】
なお、しきい値は、大きくすると、結託攻撃に使用された識別情報の検出漏れが少なくなる代わりに、結託攻撃に使用されなかった識別情報の誤検出が多くなるとともに、逆に、小さくすると、結託攻撃に使用された識別情報の検出漏れが多くなる代わりに、結託攻撃に使用されなかった識別情報の誤検出が少なくなる、という関係にある。しきい値は、例えば、誤検出が許容範囲内に収まるように、適宜、設定される。しきい値は、経験的に、あるいはシミュレーションにより、あるいは試行錯誤的に、などの方法で、決定してもよいが、例えば、後述するように計算により求めた値を使用することができる。
【０１５３】
一例として、上記している例において、検出された符号から、
ｒ(-)1＝０、ｒ(+)1＝２
ｒ(-)2＝２、ｒ(+)2＝３
ｒ(-)3＝２、ｒ(+)3＝３
の剰余対の組が得られ、
追跡対象の第２識別情報（ユーザＩＤ＝２）について、
ｒ(0)1＝１
ｒ(0)2＝１
ｒ(0)3＝１
の各基準剰余が得られ、
追跡対象の第２識別情報（ユーザＩＤ＝２）について、
ｒ(0)1＝２
ｒ(0)2＝２
ｒ(0)3＝２
の各基準剰余が得られ、
追跡対象の第３識別情報（ユーザＩＤ＝１２）について、
ｒ(0)1＝０
ｒ(0)2＝２
ｒ(0)3＝５
の各基準剰余が得られた場合を考える（図８、図９参照）。
【０１５４】
ユーザＩＤ＝１については、各剰余対について、（第１の大小関係，第２の大小関係）として、
（＞，＜）、（＜，＜）、（＜，＜）
が得られ、合同性・禁止性判定結果として、
「その他」、「禁止」、「禁止」
が得られる。
【０１５５】
この結果、総合判定結果としては、「禁止」があるので、「追跡されなかった（結託攻撃に使用されていない）旨」が出力される。
【０１５６】
ユーザＩＤ＝２については、各剰余対について、（第１の大小関係，第２の大小関係）として、
（＜，＝）、（＝，＜）、（＝，＜）
が得られ、合同性・禁止性判定結果として、
「合同」、「合同」、「合同」
が得られる。
【０１５７】
この結果、総合判定結果としては、すべて「合同」であるので、追跡された（結託攻撃に使用された）と判断され、当該識別情報（ユーザＩＤ＝２）が出力される。
【０１５８】
ユーザＩＤ＝１２については、各剰余対について、（第１の大小関係，第２の大小関係）として、
（＝，＜）、（＝，＜）、（＞，＞）
が得られ、合同性・禁止性判定結果として、
「合同」、「合同」、「禁止」
が得られる。
【０１５９】
この結果、総合判定結果としては、「禁止」があるので、「追跡されなかった（結託攻撃に使用されていない）旨」が出力される。なお、このように「合同」の判定結果が多数あっても、１つの「禁止」の判定結果によって、追跡結果から排除し、誤検出を回避するようにしたので、従来よりも結託耐性符号の符号長をより短く（成分符号の個数（Ｍ）をより少なく）できるようになる。
【０１６０】
ここで、上記の所定のしきい値および符号長について説明する。
【０１６１】
なお、ｃは、想定する最大の結託者数、
k’Ｃ(k+z)×２k+zは、ｋ′個の剰余対から剰余の(ｋ＋ｚ)組を選択する組合せ、
ｋは、ｐ0，…，ｐk’-1のうちの最初のｋ個の積を、識別情報の総数以上とするような値（ここで、ｐ0，…，ｐk’-1とする）、
ｔは、各内符号（成分符号）のブロックのビット数とする。
【０１６２】
従来のように禁止関係を考慮しない場合には、合同判定部におけるしきい値は、以下の定理１における式（２）によって決まるｚを用いて、（ｋ＋ｚ）で与えられる。ちなみに、式（１）は、内符号において誤った剰余対を出力する確率を抑える式である。一方、式（２）は、外符号において誤った識別情報を追跡する確率である。なお、ｋ’＝［ｃ（ｋ＋ｚ）／２］における［ｃ（ｋ＋ｚ）／２］は、（ｃ（ｋ＋ｚ）／２）以上の整数のうちで最小の整数を示す。
【０１６３】
＜定理１＞  内符号の個数をｋ’＝［ｃ（ｋ＋ｚ）／２］（＝Ｍ）、ｐ0，…，ｐk’-1を互いに素な正数、各内符号のブロックのビット数をｔとする。ｐ0，…，ｐk’-1とし、そのうちの最初のｋの積は、識別情報の総数（＝Ｌ）以上であるとする。次式（１），（２）が満たされると、誤追跡確率は、ε以下となる。
【０１６４】
【数１】
0003748402.tif 000002
【０１６５】
【数２】
0003748402.tif 000003
【０１６６】
ここで、ε1とε2は正数で、０＜ε1＜１、０＜ε2＜１、（１−ε1）（１−ε2）＞１−εを満たすとする。
【０１６７】
これに対して、本実施形態のように禁止関係を考慮した判定の場合、「禁止」の判定結果を持つ（禁止領域に属する剰余を持つ）識別情報を追跡結果から排除するので、その確率を考慮に入れると、式（２）は、次のように修正される。
【０１６８】
【数３】
0003748402.tif 000004
【０１６９】
ここで、δiは第ｉ番目の内符号における剰余対の幅で、δi＝ｒ(+)i−ｒ(-)i＋１で与えられる。
【０１７０】
式（２）から式（３）への修正は、ε2をそのままにｚを小さくする寄与をする。ｚが小さくなれば、内符号の個数ｋ’も小さくなり、符号長は短くて済む。
【０１７１】
さて、本実施形態の電子透かし解析装置２の復号部２２の外符号復号部２２２の追跡識別情報出力部２２２２は、各識別情報追跡部２２２１−１〜２２２１−Ｌによりそれぞれ得られた第１識別情報に対する追跡結果〜第Ｌ識別情報に対する追跡結果を統合し、最終的な追跡結果として出力する。例えば、上記の例では、追跡された（結託攻撃に使用されたと推測された）識別情報のリスト情報として、ユーザＩＤ＝２およびユーザＩＤ＝３を出力する。
【０１７２】
なお、これまでは、識別情報＝ユーザＩＤとし、追跡結果としてユーザＩＤを出力する場合を主に説明しているが、識別情報≠ユーザＩＤの場合に、復号部２２の外符号復号部２２２の追跡識別情報出力部２２２２の形態について、以下のように種々のバリエーションが可能である。
・識別情報からユーザＩＤを求めて、ユーザＩＤを出力する。
・識別情報を出力する（必要に応じて外部で識別情報からユーザＩＤを求める）。
・識別情報から複製物ＩＤを求め、複製物ＩＤからユーザＩＤを求め、ユーザＩＤを出力する。
・識別情報から複製物ＩＤを求め、複製物ＩＤを出力する（必要に応じて外部で複製物ＩＤからユーザＩＤを求める）。
・識別情報を出力する（必要に応じて外部で識別情報から複製物ＩＤを求め、複製物ＩＤからユーザＩＤを求める）。
【０１７３】
また、使用可能な全ての識別情報あるいは実際に使用している全ての識別情報について、追跡対象とする代わりに、ある特定の１又は複数の識別情報についてのみ、追跡対象とする方法も可能である。
【０１７４】
また、電子透かし解析装置２は、符号抽出部２１と、復号部２２との他に、結託攻撃がなかった場合に、符号抽出部２１により検出された符号をもとに、対応する識別情報を検出する機能を有する識別情報検出部（識別情報検出装置）を更に備えてもよい。
【０１７５】
以下では、本実施形態のハードウェア構成、ソフトウェア構成について説明する。
【０１７６】
本実施形態の電子透かし解析装置は、ハードウェアとしても、ソフトウェア（（コンピュータに所定の手段を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるための）プログラム）としても、実現可能である。また、電子透かし解析装置をソフトウェアで実現する場合には、記録媒体によってプログラムを受け渡しすることも、通信媒体によってプログラムを受け渡しすることもできる。もちろん、それらは、電子透かし埋込装置についても同様である。
また、電子透かし埋込装置や電子透かし解析装置をハードウェアとして構成する場合、半導体装置として形成することができる。
また、本発明を適用した電子透かし解析装置を構成する場合、あるいは電子透かし解析プログラムを作成する場合に、同一構成（あるいは、共有もしくは使い回し可能な構成）を有するブロックもしくはモジュールがあっても、それらをすべて個別に作成することも可能であるが、同一構成（あるいは、共有もしくは使い回し可能な構成）を有するブロックもしくはモジュールについては１または適当数のみ用意しておいて、それをアルゴリズムの各部分で共有する（使い回す）ことも可能である。電子透かし埋込装置を構成する場合、あるいは電子透かし埋め込みプログラムを作成する場合も、同様である。また、電子透かし埋込装置および電子透かし解析装置を含むシステムを構成する場合、あるいは電子透かし埋め込みプログラムおよび電子透かし検出プログラムを含むシステムを作成する場合には、電子透かし埋込装置（あるいはプログラム）と電子透かし解析装置（あるいはプログラム）に渡って、同一構成（あるいは、共有もしくは使い回し可能な構成）を有するブロックもしくはモジュールについては１または適当数のみ用意しておいて、それをアルゴリズムの各部分で共有する（使い回す）ことも可能である。
【０１７７】
また、電子透かし埋込装置や電子透かし解析装置をソフトウェアで構成する場合には、マルチプロセッサを利用し、並列処理を行って、処理を高速化することも可能である。
【０１７８】
また、これまで説明してきた構成は、装置の一部としてだけでなく、それ自体が一つの装置として成立可能である。例えば、電子透かし解析装置の復号部２２は、電子透かし解析装置を構成する一体不可分の構成部分としても、電子透かし解析装置を構成する部品あるいはモジュール等としも、独立した復号装置としても成立する。
【０１７９】
ところで、デジタル透かしに対する透かし技術は、デジタルデータの他に、ある情報あるいは物質の一部の内容を変更しても、その情報あるいは物質の同一性、同質性あるいは経済的価値等を変じないようなものにも適用可能であり、本発明は、デジタルデータの他に、そのような情報あるいは物質にも適用可能である。
【０１８０】
例えば、本発明において、結託攻撃への耐性を持つ電子透かし埋込装置／電子透かし解析装置において用いられる、埋め込まれる符号の生成手段、検出手段は、化学的に合成される、あるいは、工業的に管理された環境下で生物的に生成される化合物あるいは化学物質の出所の追跡にも応用できる。化合物としては、ＤＮＡ、ＲＮＡ、タンパク質、その他の高分子の化合物が、符号を埋め込むことができる冗長性を多く持つ。
【０１８１】
以下では、本発明を、化合物の複製物に対して個別の識別情報（ユーザＩＤ、製造者ＩＤ、販売者ＩＤ、取引ＩＤ、それらを組み合わせた情報など）を埋め込み、その出所を特定する手段を与える透かし技術として適用する場合について説明する。
【０１８２】
化合物は、複数の原子、分子、基といった物質から構成されている。例えば、ＤＮＡやＲＮＡは、所定のアミノ酸の配列構造を持っており、別のアミノ酸で置きかえるか如何かによって情報が表現されているとみなせる。その構造の中には、（デジタルコンテンツの場合には、データを変更しても、作品の同一性あるいは経済的価値を変えない場合があるのと同様に、）化合物の場合には、組成を変更しても、当該目的において、その作用・副作用・効用等の性質・機能等（別の観点でみれば、経済的価値）を変えない場合がある。
【０１８３】
そのような許容された範囲内の変更によって、その複製物を個々に識別する情報を埋め込むことができる。
【０１８４】
本発明の電子透かしを化合物に適用する場合、化合物に対する透かし埋込装置は、デジタルコンテンツに対する透かし埋込装置におけるデジタルコンテンツの所定の部分のビットを変更する構成を、化合物の所定の部分の組成を変更する装置に置き換えたものである（符号生成部は同様の構成のもので構わない）。また、化合物に対する透かし解析装置は、デジタルコンテンツに対する透かし解析装置において透かし情報を検出するためにデジタルコンテンツの所定の部分のビットの値を読み取る情報を検出する構成を、透かし情報を検出するために化合物の所定の部分の組成を解析する装置に置き換えたものである（復号部は同様の構成のもので構わない）。すなわち、化合物とのインタフェースとなる装置が相違するだけで、原理的には、デジタルコンテンツに対する透かし技術と同じである。
【０１８５】
図２０に、化合物に対する透かし埋込装置の構成例を示す。
【０１８６】
符号生成部３００１は、その化合物に埋め込むべき識別情報を入力とし、結託耐性符号を生成する（図２の符号生成部１１と同様の構成のもので構わない）。
【０１８７】
特定部位の構造変換部３００２〜３００４は、それぞれ、結託耐性符号の各ビット、あるいは、ビットの各集合に対して、その値に応じて化合物の構造を変換するものである。特定部位の構造変換部３００２は、原化合物の特定部位１を処理し、特定部位の構造変換部３００３は、特定部位１を処理済みの化合物の特定部位２を処理し、特定部位の構造変換部３００４は、特定部位１，２を処理済みの化合物の特定部位３を処理して、所望する埋込済み化合物を生成する。もちろん、図２０では、３つの構造変換部が示されているが、その数は３に限定されるものではない。
【０１８８】
ここで、化合物の構造の変換とは、その化合物の利用の目的に適した性質あるいは機能等を損なわず且つ新たな弊害あるいは副作用等をもたらさないままで、異なる構造を持つ化合物に変換する手段のことである。あるいは、その化合物が純粋な化合物ではなく、混合物である場合には、その組成を変更する手段であってもよい。
【０１８９】
図２１に、化合物に対する透かし埋込装置の他の構成例を示す。
【０１９０】
図２０の構成例は、すでに合成された化合物の構造を後から変換するものであったが、図２１の構成例は、化合物の合成時に符号を埋め込むものである。
【０１９１】
符号生成部３０１１は、その化合物に埋め込むべき識別情報を入力とし、結託耐性符号を生成する（図２の符号生成部１１と同様の構成のもので構わない）。
【０１９２】
この場合、各合成材料毎に、結託耐性符号の各ビット、あるいは、ビットの各集合に対して、その値に応じた合成材料が容易されており、合成材料部３０１２〜３０１４は、それぞれ、結託耐性符号の各ビット、あるいは、ビットの各集合に対して、その値に応じた化合物の合成材料を選択するものである。もちろん、図２１では、３つの合成材料選択部が示されているが、その数は３に限定されるものではない。
【０１９３】
合成部３０１５は、各合成材料部３０１２〜３０１４により選択された合成材料を合成して、所望する埋込済み化合物を生成する。
【０１９４】
さて、化合物に対する結託攻撃では、基本的にはデジタルコンテンツに対する結託攻撃と同様で、例えば、複数の異なる識別情報（例えば、ユーザＩＤ、製造者ＩＤ、ユーザＩＤ及び製造者ＩＤ等）が埋め込まれた化合物の構造を比較することで、差異のある部分の構造を改変することで作られる。
【０１９５】
図２２に、化合物に対する透かし解析装置の構成例を示す。
【０１９６】
特定部位の構造読み取り部３２０１〜３２０１は、図２０の特定部位の構造変換部３００２〜３００４あるいは図２１の合成材料部３０１２〜３０１４に対応するもので、その化合物中の特定部位の構造を読み取り、それをビットあるいはビットの集合である情報として出力する。
【０１９７】
復号部３２０４は、それらのビットをもとに、追跡アルゴリズムを実行して、結託攻撃がなかったこと、または結託攻撃に用いられたであろう複製物に埋め込まれていた結託耐性符号に対応するユーザＩＤを特定するものである（図３の復号部２２と同様の構成のもので構わない）。
【０１９８】
ここで、本発明に用いられる化合物の構造の変換手段や構造の読み取り手段について、利用可能な技術を例示する。以下では、ＤＮＡの場合を例にとって説明する。
【０１９９】
ＤＮＡにおいて、その塩基配列を求めることを、シークエンシングという。シークエンシングの方法としては、ショットガン法、プライマーウォーク法、ネスティッドデレーション法などが知られている。これらは、いずれも遺伝子のクローニングによる方法である。シークエンシングで用いる試薬・機器・装置の例については、各種の方法が提案されている。例えば、渡辺格監修、杉浦昌弘編集「クローニングとシークエンス」、農村文化社（１９８９年）や、榊佳之等編「ゲノムサイエンス」、共立出版（１９９９年）などに開示されている。
【０２００】
同様に、ＤＮＡの例では、新しい遺伝子を導入する際に用いられている遺伝子導入法により構造変換が可能である。遺伝子導入法には、燐酸カルシウム沈殿法、デキストラン法、リボフェクション法などの化学的な方法や、電気穿孔法、マイクロインジェクション法などが知られている。例えば、波賀信幸著「分子細胞工学」、コロナ社（２０００年）に開示されている。
【０２０１】
さて、上記では、デジタルコンテンツの複製物に対する追跡の他にも適用可能な一例として、化合物あるいは化学物質に対する追跡の例を示した。
【０２０２】
このような追跡対象を「オブジェクト」と呼ぶとすると、本発明は、デジタルコンテンツや、化合物あるいは化学物質以外のオブジェクトの追跡にも、適用可能である。本実施形態では、オブジェクトが、物理的実体を持たない（あるいは物理的実体を媒介としてやり取りされる）電子的なデータの一例として、デジタルコンテンツについて説明した。本実施形態では、デジタルコンテンツへの識別情報に対応する結託耐性符号の埋め込み技術として、電子透かし技術を用いたが、その他の技術を用いた場合にも適用可能である。また、本実施形態では、オブジェクトが物質の一例として、遺伝子情報を含むＤＮＡ、ＲＮＡ、タンパク質などについて示した。本実施形態では、ＤＮＡ、ＲＮＡ、タンパク質などへの識別情報に対応する結託耐性符号の書き込み技術として、遺伝子組換えやタンパク質のアミノ酸配列の置換によって行う例を示した。しかしながら、前述したように、オブジェクトとのインタフェースとなる技術が相違するだけで、識別情報や結託耐性符号に関しては、電子情報処理システムにおいて処理可能であり、その処理については、原理的には、どのようなオブジェクトであっても全て同じである。したがって、当該オブジェクトへの識別情報に対応する結託耐性符号の埋め込み技術を、当該オブジェクトに応じて選択しさえすれば、これまでに説明してきた構成を提供することが可能である。
【０２０３】
なお、この発明の実施の形態で例示した構成は一例であって、それ以外の構成を排除する趣旨のものではなく、例示した構成の一部を他のもので置き換えたり、例示した構成の一部を省いたり、例示した構成に別の機能あるいは要素を付加したり、それらを組み合わせたりすることなどによって得られる別の構成も可能である。また、例示した構成と論理的に等価な別の構成、例示した構成と論理的に等価な部分を含む別の構成、例示した構成の要部と論理的に等価な別の構成なども可能である。また、例示した構成と同一もしくは類似の目的を達成する別の構成、例示した構成と同一もしくは類似の効果を奏する別の構成なども可能である。
また、この発明の実施の形態で例示した各種構成部分についての各種バリエーションは、適宜組み合わせて実施することが可能である。
また、この発明の実施の形態は、個別装置としての発明、関連を持つ２以上の装置についての発明、システム全体としての発明、個別装置内部の構成部分についての発明、またはそれらに対応する方法の発明等、種々の観点、段階、概念またはカテゴリに係る発明を包含・内在するものである。
従って、この発明の実施の形態に開示した内容からは、例示した構成に限定されることなく発明を抽出することができるものである。
【０２０４】
本発明は、上述した実施の形態に限定されるものではなく、その技術的範囲において種々変形して実施することができる。
【０２０５】
【発明の効果】
本発明によれば、結託耐性符号による識別情報が埋め込まれたオブジェクトに対する結託攻撃に用いられたオブジェクトの識別情報を、より短い符号長により推測することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る電子透かし埋込装置及び電子透かし解析装置を含むコンテンツ流通システムの概略構成を示す図
【図２】同実施形態に係る電子透かし埋込装置の構成例を示す図
【図３】同実施形態に係る電子透かし解析装置の構成例を示す図
【図４】同実施形態に係る電子透かし埋込装置の概略的な手順の一例を示すフローチャート
【図５】同実施形態に係る電子透かし埋込装置の符号生成部の構成例を示す図
【図６】同実施形態に係る符号生成部の成分符号生成部の構成例を示す図
【図７】同実施形態に係る電子透かし埋込装置により生成される成分符号の例について説明するための図
【図８】同実施形態における各ユーザＩＤに対応する複数の整数の組の例について説明するための図
【図９】同実施形態における各ユーザＩＤに対応する結託耐性符号の例について説明するための図
【図１０】同実施形態における各成分符号でのビットパターンに関する境界の位置について説明するための図
【図１１】同実施形態に係る電子透かし解析装置の復号部の構成例を示す図
【図１２】同実施形態に係る復号部の内符号復号部の構成例を示す図
【図１３】同実施形態に係る内符号復号部の符号分割部の処理について説明するための図
【図１４】同実施形態に係る内符号復号部の剰余対検出部の構成例を示す図
【図１５】同実施形態に係る復号部の外符号復号部の構成例を示す図
【図１６】同実施形態に係る外符号復号部の識別情報追跡部の構成例を示す図
【図１７】同実施形態に係る識別情報追跡部の合同性判定部の構成例を示す図
【図１８】同実施形態に係る合同性・禁止性判定の処理手順の一例を示すフローチャート
【図１９】同実施形態に係る総合判定の処理手順の一例を示すフローチャート
【図２０】同実施形態に係る化合物に対する透かし埋込装置の構成例を示す図
【図２１】同実施形態に係る化合物に対する透かし埋込装置の他の構成例を示す図
【図２２】同実施形態に係る化合物に対する透かし解析装置の他の構成例を示す図
【符号の説明】
１…電子透かし埋込装置
２…電子透かし解析装置
３…流通経路
１１…符号生成部
１２…符号埋込部
２１…符号抽出部
２２…復号部
２２１…内符号復号部
２２１１…符号分割部
２２１２−１〜２２１２−Ｍ…剰余対検出部
２２１２１−１〜２２１２１−Ｋ…判定部
２２１２２，２２１２３…境界位置検出部
２２２…外符号復号部
２２２１−１〜２２２１−Ｌ…識別情報追跡部
２２２１１−１〜２２２１１−Ｍ…合同性判定部
２２２１１１…基準剰余生成部
２２２１１２，２２２１１３…大小関係比較部
２２２１１４…合同性・禁止性判定部
２２２１２…総合判定部
２２２２…追跡情報出力部
１２１−１〜１２１−ｋ′…法記憶部
１２２−１〜１２２−ｋ′…剰余計算部
１２３…符号パラメータ記憶部
１２４−１〜１２４−ｋ′…成分符号生成部
１２５…符号連接部
１３１…減算部
１３２…“０”列生成部
１３３…“１”列生成部
１３４…連接部
３００１，３０１１…符号生成部
３００２〜３００４…特定部位の構造変換部
３０１２〜３０１４…合成材料部
３０１５…合成部
３２０１〜３２０１…特定部位の構造読み取り部
３２０４…復号部
【図１】
0003748402.tif 000005
【図２】
0003748402.tif 000006
【図３】
0003748402.tif 000007
【図４】
0003748402.tif 000008
【図５】
0003748402.tif 000009
【図６】
0003748402.tif 000010
【図７】
0003748402.tif 000011
【図８】
0003748402.tif 000012
【図９】
0003748402.tif 000013
【図１０】
0003748402.tif 000014
【図１１】
0003748402.tif 000015
【図１２】
0003748402.tif 000016
【図１３】
0003748402.tif 000017
【図１４】
0003748402.tif 000018
【図１５】
0003748402.tif 000019
【図１６】
0003748402.tif 000020
【図１７】
0003748402.tif 000021
【図１８】
0003748402.tif 000022
【図１９】
0003748402.tif 000023
【図２０】
0003748402.tif 000024
【図２１】
0003748402.tif 000025
【図２２】
0003748402.tif 000026