符号化装置、追跡装置、符号化方法、追跡方法、および、プログラム
【課題】Ｔａｒｄｏｓ符号を改良し、符号長を短縮しより実用的な符号法を与えるための符号化装置を提供する。
【解決手段】符号化装置１は、結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置４で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成する。
符号化装置１は、前記追跡装置４で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成する最適Z計算部１１と、生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択する最適符号長計算部１２と、選択された値の符号長で、利用者ごとに異なる符号語を生成する符号語生成部とを備える。
【解決手段】符号化装置１は、結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置４で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成する。
符号化装置１は、前記追跡装置４で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成する最適Z計算部１１と、生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択する最適符号長計算部１２と、選択された値の符号長で、利用者ごとに異なる符号語を生成する符号語生成部とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルコンテンツの流通に際し、デジタルフィンガープリンティングで埋め込まれる符号語への符号化、または、結託により改ざんされたデジタルコンテンツからの結託者の符号語の追跡に係る符号化装置、追跡装置、符号化方法、追跡方法、および、プログラムに関する。
【背景技術】
【０００２】
デジタルコンテンツの著作権保護を目的として、コンテンツのコピー毎に異なる識別情報を埋め込み、不正コピーが現れた際に、埋め込まれている識別情報からその出所追跡するスキームをデジタルフィンガープリンティング（ｄｉｇｉｔａｌ ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ）と呼ぶ。
【０００３】
デジタルコンテンツに識別情報を埋め込む方法として、コンテンツの品質を落さずに別の情報を埋め込む電子透かし（ｄｉｇｉｔａｌ ｗａｔｅｒｍａｒｋｉｎｇ）がある。電子透かしには、コンテンツがＭＰＥＧ圧縮やデジタル・アナログ・デジタル変換などのさまざまな操作を受けても埋め込まれた情報が失われないロバスト電子透かし（ｒｏｂｕｓｔ ｄｉｇｉｔａｌ ｗａｔｅｒｍａｒｋｉｎｇ）と呼ばれるものがある。しかし、例えロバスト電子透かしとしても、利用者毎に異なる識別情報が埋め込まれたコンテンツの配布を受けた利用者が結託して、各自のコンテンツを持ち寄り、コピーを比較するとコンテンツ中のコピー毎に異なる部分が分かり、その情報をもとにコンテンツに改ざんを加えることで、埋め込まれた識別情報を改ざん・消去する結託攻撃（ｃｏｌｌｕｓｉｏｎ ａｔｔａｃｋ）が可能である。
【０００４】
結託攻撃に対する対策として、識別情報に対して結託攻撃に強い符号化を施してからコンテンツに埋め込む方法がある。そのような符号を結託耐性符号（ｃｏｌｌｕｓｉｏｎ−ｒｅｓｉｌｉｅｎｔ ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ ｃｏｄｅ）と呼ぶ。誤りεを持つｃ−ｓｅｃｕｒｅ符号（ｃ−ｓｅｃｕｒｅ ｃｏｄｅ ｗｉｔｈ ε−ｅｒｒｏｒ）は、結託者数ｃまでの結託攻撃に対して高々εの追跡誤り確率で少なくとも1人の結託者を特定することが可能な結託耐性符号である。
【０００５】
誤りεを持つｃ−ｓｅｃｕｒｅ符号の構成法の一種として、Ｔａｒｄｏｓ符号（Ｔａｒｄｏｓ ｃｏｄｅ）が、知られている。（例えば、非特許文献１参照）。
【非特許文献１】Ｔａｒｏｄｏｓ，Ｇ．：Ｏｐｔｉｍａｌ Ｐｒｏｂａｂｉｌｉｓｔｉｃ ＦｉｎｇｅｒｐｒｉｎｔｉｎｇＣｏｄｅｓ． Ｉｎ：ＳＴＯＣ’０３，ＡＣＭ（２００３）１１６−１２５
【発明の開示】
【発明が解決しようとする課題】
【０００６】
Ｔａｒｄｏｓ符号は、論理上誤りεを持つｃ−ｓｅｃｕｒｅ符号として有力な方式であるが、現実的には、符号長ｍが長すぎるため、あまり実用的ではなかった。
【０００７】
そこで、本発明は、Ｔａｒｄｏｓ符号を改良し、符号長を短縮しより実用的な符号法を与えるための符号化装置、追跡装置、符号化方法、追跡方法、および、プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成する符号化装置であって、前記追跡装置で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成する閾値計算手段と、前記閾値計算手段で生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択する最適符号長計算手段と、前記最適符号長計算手段で選択された値の符号長で、利用者ごとに異なる符号語を生成する符号語生成手段とを備えたことを特徴とする。
【０００９】
また、本発明は、利用者ごとに異なる符号語を埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡装置であって、不正利用されたデジタルデータの利用者であるか否かの判定のために用いる閾値の候補を計算により複数生成する閾値計算手段と、前記閾値計算手段で生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択する最適符号長計算手段と、前記最適符号長計算手段で選択された値の符号長で、利用者ごとに異なる符号語を生成する符号語生成手段と、前記改ざんデータと、前記符号化生成手段で生成された符号語との相関値をそれぞれ計算する相関計算手段と、前記最適符号長計算手段で選択された符号長に対応する閾値を複数の閾値の候補から選定し、前記相関計算手段で計算された各相関値が該選定された閾値を超えるか否かを判定する判定手段とを備えたことを特徴とする。
【００１０】
また、本発明は、利用者ごとに異なる符号語を符号化装置で生成し、生成された各符号語をそれぞれ埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡装置であって、前記符号化装置で符号語の生成時に生成された閾値と、各符号語とを記憶する記憶手段と、前記改ざんデータと、前記記憶手段で記憶する各符号語との相関値をそれぞれ計算する相関計算手段と、前記相関計算手段で計算された各相関値が前記記憶手段に記憶する閾値を超えるか否かを判定する判定手段とを備えたことを特徴とする。
【００１１】
また、本発明は、結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成する符号化方法であって、前記追跡装置で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成し、該生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択し、該選択された値の符号長で、利用者ごとに異なる符号語を生成するようにした。
【００１２】
また、本発明は、利用者ごとに異なる符号語を埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡方法であって、不正利用されたデジタルデータの利用者であるか否かの判定のために用いる閾値の候補を計算により複数生成し、該生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択し、該選択された値の符号長で、利用者ごとに異なる符号語を生成し、前記改ざんデータと、該生成された符号語との相関値をそれぞれ計算し、該選択された符号長に対応する閾値を複数の閾値の候補から選定し、該計算された各相関値が該選定された閾値を超えるか否かを判定するようにした。
【００１３】
また、本発明は、利用者ごとに異なる符号語を符号化装置で生成し、生成された各符号語をそれぞれ埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡方法であって、前記符号化装置で符号語の生成時に生成された閾値と、各符号語とを記憶手段に記憶し、前記改ざんデータと、前記記憶手段で記憶する各符号語との相関値をそれぞれ計算し、該計算された各相関値が前記記憶手段に記憶する閾値を超えるか否かを判定するようにした。
【００１４】
また、本発明は、結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成させるためにコンピュータで実行されるプログラムであって、前記追跡装置で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成させる第１プログラムコードと、前記第1プログラムコードで生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めさせ、該複数の符号長の値から最も小さい値を選択させる第２プログラムコードと、 前記第２プログラムコードで選択された値の符号長で、利用者ごとに異なる符号語を生成させる第３プログラムコードとを備えた。
【００１５】
また、本発明は、利用者ごとに異なる符号語を埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡させるために、コンピュータで実行されるプログラムであって、不正利用されたデジタルデータの利用者であるか否かの判定のために用いる閾値の候補を計算により複数生成させる第1プログラムコードと、前記第1プログラムコードで生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めさせ、該複数の符号長の値から最も小さい値を選択させる第２プログラムコードと、前記第２プログラムコードで選択された値の符号長で、利用者ごとに異なる符号語を生成させる第３プログラムコードと、前記改ざんデータと、前記第３プログラムコードで生成された符号語との相関値をそれぞれ計算する第４プログラムコードと、前記第２プログラムコードで選択された符号長に対応する閾値を複数の閾値の候補から選定し、前記第４プログラムコードで計算された各相関値が該選定された閾値を超えるか否かを判定する第５プログラムコードとを備えた。
【００１６】
また、本発明は、利用者ごとに異なる符号語を符号化装置で生成し、生成された各符号語をそれぞれ埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡させるために、コンピュータで実行されるプログラムであって、前記符号化装置で符号語の生成時に生成された閾値と、各符号語とを記憶手段に記憶させる第１プログラムコードと、前記改ざんデータと、前記記憶手段で記憶する各符号語との相関値をそれぞれ計算させる第２プログラムコードと、前記第２プログラムコードで計算された各相関値が前記記憶手段に記憶する閾値を超えるか否かを判定する第３プログラムコードとを備えた。
【発明の効果】
【００１７】
本発明によれば、誤りεを持つｃ−ｓｅｃｕｒｅ符号であることを維持しつつ、より短い符号長ｍを実現できる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を用いて本実施の形態を説明する。
【００１９】
図１は、本実施の形態の符号化装置／追跡装置が利用されるシステムの一例を示している。このシステムは、同じデジタルコンテンツを利用したい複数の人に配布する際に利用者ごとにそれぞれ異なる固有の識別情報ｕを決定し、符号化装置１で各識別情報ｕからそれぞれ異なる各符号語ｗｕを生成し、埋込み装置２でデジタルコンテンツに生成された各符号語ｗｕを知覚できないように埋め込み、各符号語ｗｕを埋め込み済みのデジタルコンテンツを各利用者へ配布する。その後、不正な利用者によって、結託攻撃が行われたとする。結託攻撃とは、配布された異なる符号語が埋め込まれたデジタルコンテンツまたはそのコピーを複数入手し、それらの間の違いを見出して得られた知識を用い、埋め込み済みのデジタルコンテンツに埋め込まれる符号語を改ざん・消去しようとする攻撃である。不正な利用者は、結託攻撃によって攻撃された後の結託攻撃済みのデジタルコンテンツを不正に流通させる。不正に流通された結託攻撃済みのデジタルコンテンツを取得し、埋め込み装置２での埋め込み方式に対応する検出方式を備えた検出装置３にて、結託攻撃済みのデジタルコンテンツに埋め込まれている符号語（追跡対象符号語）ｙを検出する。検出された追跡対象符号語ｙを、追跡装置４で検査することによって、この結託攻撃に利用された複数のデジタルコンテンツの利用者のうち少なくとも一人の識別情報がわかる。これにより、結託に携わった少なくとも一人を特定できることになり、デジタルコンテンツの著作権保護につながる。なお、符号化装置１、埋め込み装置２、検出装置３、追跡装置４は、専用装置で構成しても良いが、プロセッサ、主メモリ、ＨＤＤ等を備えた通常のコンピュータ装置に、ソフトウェアプログラムを実行させることにより実現しても良いことは勿論である。また、符号化装置１、埋め込み装置２、検出装置３、追跡装置４は、それぞれ独立した装置構成でも良いし、これらの幾つかを同時に備えた装置構成としても良い。
【００２０】
上記のシステムにおいて、デジタルコンテンツに埋め込む符号語は、結託攻撃に強い符号であることが重要である。そのような符号を結託耐性符号（ｃｏｌｌｕｓｉｏｎ−ｒｅｓｉｌｉｅｎｔ ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ ｃｏｄｅ）と呼ぶ。誤りεを持つｃ−ｓｅｃｕｒｅ符号（ｃ−ｓｅｃｕｒｅ ｃｏｄｅ ｗｉｔｈ ε−ｅｒｒｏｒ）は、結託者数ｃまでの結託攻撃に対して高々εの追跡誤り確率で少なくとも1人の結託者を特定することが可能な結託耐性符号である。Ｔａｒｄｏｓ符号（Ｔａｒｄｏｓ ｃｏｄｅ）は、誤りεを持つｃ−ｓｅｃｕｒｅ符号の構成法の一種であるが、本実施の形態ではこれを一部改良した。これについて、以下に詳細な説明を行う前に、用いる表記方法について定義しておく。
【００２１】
［ｎ］と記すと、１からｎまでの整数の集合を示すとする。また、［ａ，ｂ］は、ａ以上ｂ以下の全ての実数の集合を示すとする。また、ａ∈Ｃは、ａが集合Ｃの元であることを示すとする。また、Ｃ＼Ｄは、集合Ｃと集合Ｄとの差集合を示し、集合Ｃから集合Ｄに属する元を取り除いたものである。例えば、［ｎ］＼［ｃ］は、１からｎまでの整数の集合と１からｃまでの整数の集合の差集合であるので、ｃ＋１からｎまでの整数の集合となる。また、ａ∈ＵＣは、確率変数ａが集合Ｃから一様に値をとることを示す。また、Ｐｒ［Ｅ］は、事象Ｅが生起する確率を示す。また、≡は、記号の定義を示す式に用い、左辺を右辺と定義するか右辺を左辺と定義する場合に用いる。また、対数関数をｌｎ≡ｌｏｇｅとし、ｅは自然対数の底を示し、ｅ＝２．７１８２８・・・である。また、∀ｘＡ（ｘ）は、全てのｘに対して式Ａ（ｘ）が成り立つという意味である。同様に、∀ｘ∈ＣＡ（ｘ）は、Ｃの全ての元に対して式Ａ（ｘ）が成り立つという意味である。また、Ｅｘ［Ｂ（ｘ）］は、Ｂ（ｘ）の期待値を表す記号で、確率変数ｘが集合Ａから値をとるとき、Ｅｘ［Ｂ（ｘ）］≡Σａ∈ＡＰｒ［ｘ＝ａ］Ｂ（ａ）と定義される。また、（ｗｉ）ｉ＝１，,…，８＝（ｗ１，ｗ２，・・・，ｗ８）＝（１，０，１，１，０，１，１，０）である。
【００２２】
まず、符号化法の概略動作を図２を用いて説明する。
【００２３】
以下、利用者数をｎ、想定する最大結託者数をｃ、追跡誤り確率をε、符号長をｍとする。また、利用者の識別情報をｕ∈［ｎ］≡｛１，２，・・・，ｎ｝とする。識別情報ｕ∈［ｎ］の利用者に割り当てられる符号語ｗｕの第ｉビットをｗｕ，ｉ（ｉ＝１・・・ｍ）と示すと、符号生成においてｗｕ，ｉが値1を取る確率をＰｒ［ｗｕ，ｉ＝１］と示す。
【００２４】
まず、各ｉに対してｐｉを生成する（ステップＳ１１）。より詳細には、ｔ＝１／（３００ｃ）、ｔ’＝ａｒｃｓｉｎ ｔ１／２とし、ｒｉ∈［ｔ’，π・２−ｔ’］を一様分布に従う確率変数とし、ｒｉの値をランダムに生成し、ｐｉ＝ｓｉｎ２ｒｉを生成する。
【００２５】
次に、各ｕ、各ｉに対して、Ｐｒ［ｗｕ，ｉ＝１］＝ｐｉ、Ｐｒ［ｗｕ，ｉ＝０］＝１−ｐｉとし、ｗｕ，ｉ∈｛０，１｝をランダムに生成する（ステップＳ１２）。
【００２６】
生成した符号語ｗｕ（＝ｗｕ，１，ｗｕ，２，・・・，ｗｕ，ｍ）を出力する（ステップＳ１３）。
【００２７】
以上のようにして符号語ｗｕ生成される。
【００２８】
一方、符号語ｙの追跡法の概略動作を図３を用いて説明する。
【００２９】
まず、結託攻撃を受けたと想定されるデジタルコンテンツから、検出された追跡対象符号語ｙ（＝ｙ１，ｙ２，・・・，ｙｍ）と、調査対象のある一利用者の識別情報に対応する符号語ｗｕ（＝ｗｕ，１，ｗｕ，２，・・・，ｗｕ，ｍ）とを入力する（ステップＳ２１）。
【００３０】
次に、追跡対象符号語ｙと符号語ｗｕとの相関値Ｓ（ｙ，ｗｕ）を計算する（ステップＳ２２）。この相関値Ｓ（ｙ，ｗｕ）が、閾値Ｚを越えているか否かを判断する（ステップＳ２３）。超えていると判断された場合にはその符号語ｗｕに対応する識別情報の利用者が結託者であると決定し（ステップＳ２４）、超えていなければこの利用者は結託者でないと決定し（ステップＳ２５）、決定結果を出力する（ステップＳ２６）。
【００３１】
以上のことを調査対象の利用者を代えて、順次調べることにより、少なくとも結託者の一人を特定する。
【００３２】
次に、Ｔａｒｄｏｓ符号語ｗｕがｃ−ｓｅｃｕｒｅ符号であるための十分条件を以下に説明する。
【００３３】
ステップＳの相関値の計算を式として示すと以下のようになる
【数１】
【００３４】
符号がｃ−ｓｅｃｕｒｅ符号であるには、いかなるｃ人以下の結託に対しても、確率（１−ε）以上で少なくとも一人の結託者を追跡できなければならない。つまり、結託者数は、１人からｃ人までの任意の数であるとする。そこで、ｃ’人の結託者による攻撃が行われたとする。但し、ｃ’∈［ｃ］とする。
【００３５】
Ｔａｒｄｏｓ特定の符号語を特別扱いするものではないので、一般性を失うことなく、結託者の集合を［ｃ’］とすることができる。このとき、無実の利用者の符号語の集合は、符号語全体の集合と結託者の符号語の集合の差集合［ｎ］＼［ｃ’］である。
【００３６】
ｃ−ｓｅｃｕｒｅ符号は、その定義により追跡誤り確率がε以下でなければならない。追跡誤りが起こる場合として、１）結託者でない人を誤って追跡してしまう、２）結託者を誰一人として追跡できない。これらの追跡誤りが怒る確率の和がε以下ならば、Ｔａｒｄｏｓ符号はｃ−ｓｅｃｕｒｅ符号となる。
【００３７】
判定条件を表す式［数１］より、あるｕ∈［ｎ］＼［ｃ’］は、Ｓ（ｙ，ｗｕ）＞Ｚのとき不正者として誤って追跡される。その確率はＰｒ［Ｓ（ｙ，ｗｕ）＞Ｚ］で表される。
【００３８】
一方、判定条件を表す式［数１］より、結託者ｕ∈［ｃ’］は、Ｓ（ｙ，ｗｕ）＞Ｚのとき追跡されるので、Σｕ∈［ｃ’］Ｓ（ｙ，ｗｕ）＞ｃ’Ｚならば、少なくとも一人の結託者ｕに対しては、Ｓ（ｙ，ｗｕ）＞Ｚとなることが保証されるので、少なくとも一人の不正者が追跡される（図４）。反対に、Σｕ∈［ｃ’］Ｓ（ｙ，ｗｕ）≦ｃ’Ｚのときは、少なくとも一人を追跡されるという保証はなくなる。
【００３９】
以上のことから、次式を満たすときに、Ｔａｒｄｏｓ符号は誤りεを持つｃ−ｓｅｃｕｒｅ符号となる。
【数２】
【数３】
【００４０】
実際、［数２］、［数３］の２つの不等式より、追跡誤り確率が、次式の通りεで抑えられるからである。
【数４】
【００４１】
なお、式［数４］の右辺の第１因子（ｎ−ｃ’）は、不正者でないユーザについての確率を足し上げるためである。
【００４２】
式［数２］と式［数３］の式のそれぞれに、よく知られるＭａｒｋｏｖ不等式（後述）を適用し、次式を得る。
【数５】
【数６】
【００４３】
ここで、Ｍａｒｋｏｖ不等式について説明する。Ｍａｒｋｏｖ不等式は、ある非負の確率変数Ｘと、非負の実数ｖが与えられていたとき、次式のことをいう。
【数７】
【００４４】
Ｍａｒｋｏｖ不等式を使うと、任意の整数αに対して、
【数８】
【００４５】
が成り立つ。
【００４６】
式［数５］、式［数６］のαとα’は、式［数２］、式［数３］のそれぞれに、Ｍａｒｋｏｖ不等式を適用する際に現れる正定数で、Ｔａｒｄｏｓ符号の構成上のパラメータとなる。
【００４７】
また、Ａは、α’とｃに依存する関数で、次式で定義される。
【数９】
【００４８】
Ｅは、期待値を示し、ｐ＝（ｐｉ）ｉ＝１、・・・ｍとｗｕ＝（ｗｕ，ｉ）ｉ＝１、・・・ｍの確率分布に従って計算される。
【００４９】
さらに、Ｔａｒｄｏｓ符号において符号語の各ビットが独立であることを用いると、
【数１０】
【００５０】
となる。ここで、ｘｉは結託者のうち符号語の第ｉビットが１である者の数である。
【００５１】
以上の説明により、Ｔａｒｄｏｓ符号は、符号長ｍが［数５］、［数６］の不等式を満たすとき、誤りεを持つｃ−ｓｅｃｕｒｅ符号となることがわかる。
【００５２】
ところで、従来から知られているＴａｒｄｏｓ符号は、閾値Ｚおよび符号長ｍは、次式によって定められていた。
【数１１】
【数１２】
【００５３】
これらも、式［数５］、式［数６］の不等式を満たすため、誤りεを持つｃ−ｓｅｃｕｒｅ符号となるが、符号長ｍの長さについて考慮されておらず、実際、この符号長ｍでは、長すぎて実用上利用できなかった。
【００５４】
そこで、以下では、符号長ｍを誤りεを持つｃ−ｓｅｃｕｒｅ符号であることを保ちつつ、最小の符号長ｍを求めることについて考察を進める。
【００５５】
図５は、［数５］と［数６］によって、符号長が決まる様子を表している。式［数５］と式［数６］は、それぞれ符号長ｍの上限と下限を与えている。従って、このあいだの黒塗りの領域内にｍが取り得る値がある。なお、符号長ｍは、図５からもわかるように、２つの直線の交点のｍが、ｍの最小値となる。この交点は、次式で表される。
【数１３】
【数１４】
【００５６】
式［数１３］より、ｍが最小になるαを決定する。これはｄｍ／ｄα＝０を満たす極限値を求めることによって行われる（図６）。その結果、
【数１５】
のとき、符号長が最小になり、そのときの閾値Ｚと符号長ｍは、
【数１６】
【数１７】
【００５７】
となる。
【００５８】
式［数１６］、式［数１７］からわかるように、閾値Ｚと符号長ｍとは、α’によって求まる。α’は、小数第２位程度の値を取り得ることがわかっているので、α’をその近辺の値として所定間隔（例えば、０．００１間隔）で変更しつつ、式［数１６］が最小になるα’を探索することにより最小となる符号長ｍと、そのときのα’から式［数１７］を計算することにより得られる閾値Ｚとを決定することができる。
【００５９】
次に、上記で説明してきた本実施の形態の符号長ｍを最小にする誤りεを持つｃ−ｓｅｃｕｒｅ符号を実現する符号化装置および復号装置について、以下に説明する。
【００６０】
図７は、符号化装置１の全体を示した図である。符号化装置１は、パラメータ入力部１６、最適Ｚ計算部１１、最適符号長計算部１２、符号語生成部１３、および、符号語出力部１７とを備える。
【００６１】
パラメータ入力部１６は、図示しない表示装置やキーボードなどのマンマシン・インタフェースを介し、本装置を利用する人から、配布するデジタルコンテンツを利用する利用者数（配布数）ｎ、想定する最大結託者数ｃ、および、追跡誤り確率εの入力を受け、一時的に保持する。また、パラメータ入力部１６は、利用者数ｎに基づき、ユーザ識別情報ｕ１・・・ｎを自動生成する。なお、この自動生成に代え、ユーザが識別情報を１つずつ入力するようにしても良い。
【００６２】
最適Ｚ計算部１１は、パラメータｎ、ｃ、εの入力を受け、復号時に利用される最適な閾値Ｚ（＋）を求めるための閾値候補群Ｚ１（＋），Ｚ２（＋），・・・，ＺＭ（＋）を不定なパラメータα’を残したまま、式［数１８］を計算するものである。
【数１８】
【００６３】
最適Ｚ計算部１１内の機能ブロックを図８に示す。最適Ｚ計算部１１は、ε／ｎ計算部１１０、α’系列生成部１２０、Ａ計算部１３０、Ｚ（＋）計算部１４０を備える。
【００６４】
ε／ｎ計算部１１０は、パラメータ入力部１６からεとｎとを入力し、ε／ｎを計算し、計算結果をＺ（＋）計算部１４０へ出力するものである。
【００６５】
α’系列生成部１２０は、閾値Ｚの最適値がその中に存在すると想定するα’領域内から、α’の値の候補をＭ個生成する。または、α’系列生成部１２０は、上記でも説明したように、小数第２位程度の値を取り得ることがわかっているので、そのようなα’の値の候補をＭ個を予め用意しておいても良い。なお、Ｍは、予め定めた値でも良いし、適宜変更される値であっても良い。α’系列生成部１２０は、α’の値の候補を系列α’１，α’２，・・・，α’ＭとしてＡ計算部１３０およびＺ（＋）計算部１４０へ出力する。
【００６６】
Ａ計算部１３０は、パラメータ入力部１６からｃを入力し、α’系列生成部１２０から入力された系列α’１，α’２，・・・，α’Ｍの各値に対して、Ａを計算する。Ａの計算は、具体的には［数１０］の式の右辺を計算するが、ｙｉに依存しない値を出すために、不等式の最後の右辺を計算する。α’ｉに対するＡの計算結果をＡｉとすると、Ａ計算部１３０は、系列（α’１，Ａ１），（α’２，Ａ２），・・・，（α’Ｍ，ＡＭ）をＺ（＋）計算部１４０へ出力する。
【００６７】
Ｚ（＋）計算部１４０は、入力されたε／ｎと系列（α’１，Ａ１），（α’２，Ａ２），・・・，（α’Ｍ，ＡＭ）とから、各α’ｉに対して、それぞれ式［数１８］に対応した式［数１９］の計算を行うものである。
【数１９】
【００６８】
計算結果は、系列（α’１，Ａ１，Ｚ１（＋）），（α’２，Ａ２，Ｚ２（＋）），・・・，（α’Ｍ，ＡＭ，ＺＭ（＋））として出力する。
【００６９】
次に、最適符号長計算部１２は、符号時に利用される最も小さい符号長ｍＭＩＮを求めるためのものである。最適符号長計算部１２内の機能ブロックを図９に示す。最適符号長計算部１２は、ε／ｎ計算部２１０とｍｍｉｎ計算部２２０とｍＭＩＮ決定部２３０とを備える。
【００７０】
ε／ｎ計算部２１０は、パラメータ入力部１６からεとｎとを入力し、ε／ｎを計算し、計算結果をｍｍｉｎ計算部２２０へ出力する。なお、ε／ｎ計算部２１０は、最適Ｚ計算部１１内のε／ｎ計算部１１０と同一の機能を有しているから、ε／ｎ計算部２１０を省略し、最適Ｚ計算部１１内のε／ｎ計算部１１０から直接入力するようにしても良い。
【００７１】
ｍｍｉｎ計算部２２０は、各α’ｉに対して、次式を計算する。
【数２０】
【００７２】
ｍＭＩＮ決定部２３０は、ｍｍｉｎ１，ｍｍｉｎ２，・・・，ｍｍｉｎＭの中から最小値を求め、その値ｍＭＩＮを出力する。
【００７３】
次に、符号語生成部１３は、識別情報ｕとｍＭＩＮとから符号長ｍＭＩＮビットの符号を生成するものである。符号語生成部１３内の機能ブロックを図１０に示す。符号語生成部１３は、ｐｉ生成部３１０とｗｕ，ｉ生成部３２０とを備える。
【００７４】
ｐｉ生成部３１０は、パラメータ入力部１６からｃを、最適符号長計算部１２からｍＭＩＮを入力し、乱数の系列ｐ１，ｐ２，・・・，ｐｍＭＩＮを生成する。各ｐｉは、ｒｉを［ａｒｃｓｉｎ（１／３００ｃ）１／２，π／２−ａｒｃｓｉｎ（１／３００ｃ）１／２］から一様に選択し、ｐｉ＝ｓｉｎ２ｒｉとする。生成されたｐ１，ｐ２，・・・，ｐｍＭＩＮをｗｕ，ｉ生成部３２０へ出力する。
【００７５】
ｗｕ，ｉ生成部３２０は、ｉ＝１，２，・・・，ｍＭＩＮに対して、入力されたｐｉの値に基づいて、Ｐｒ［ｗｕ，ｉ＝１］＝ｐｉとＰｒ［ｗｕ，ｉ＝０］＝１−ｐｉの確率に従って、ｗｕ，ｉの値をランダムに生成する。こうして得られた符号語ｗｕ＝（ｗｕ，ｉ）ｉ＝１、・・・ｍＭＩＮを出力する。この出力された符号語ｗｕ＝（ｗｕ，ｉ）ｉ＝１、・・・ｍＭＩＮは、符号化装置１の出力となる。
【００７６】
以上のようにして、符号化装置１は、構成される。なお、図７の最適Ｚ計算部１１、最適符号長計算部１２、及び、符号語生成部１３で求められた値を図示しない記憶部へ出力し（図の点線矢印）、記憶させるようにしても良い。
【００７７】
次に、このような符号語生成装置１の動作について図１１を用いて説明する。
【００７８】
パラメータ入力部１６は、利用者数（配布数）ｎ、想定する最大結託者数ｃ、および、追跡誤り確率εの入力を受ける（ステップＳ３１）。最適Ｚ計算部１１は、閾値Ｚ候補を複数生成する（ステップＳ３２）。最適符号長計算部１２は、生成された閾値Ｚ候補群を入力し、複数の符号長を求め、その中から最小となる符号長を決定する（ステップＳ３３）。
【００７９】
パラメータ入力部１６は、符号語生成部１３へ符号化したい識別情報を入力する（ステップＳ３４）。符号語生成部１３は、ステップＳ３３で決定した符号長と、入力された識別情報とに基づき、符号語を生成する（ステップＳ３５）。符号語生成部１３は、生成された符号語を出力する（ステップＳ３６）。なお、生成された符号語は一旦図示しない記憶部に保持し、後で全符号語を纏めて出力するようにしても良い。
【００８０】
まだ、符号化を行う識別情報があるか確認し（ステップＳ３７）、なければ、符号化の処理を終了する。一方、符号化を行う識別情報がまだある場合には、符号語生成対象とする識別情報を更新し（ステップＳ３８）、ステップＳ３４の処理に戻る。
【００８１】
以上のようにして、符号化装置１は、各識別情報ｕに対し各ユーザの符号語ｗｕを生成・出力し、例えば、埋込み装置２は、デジタルコンテンツのコピーごとに、符号語ｗｕを変えて透かし情報として埋め込む。
【００８２】
次に、追跡装置について説明する。図１２は、追跡装置４の全体を示した図である。
【００８３】
追跡装置４は、符号化部２１、相関計算部２２、および、不正者判定部２３を備える。
【００８４】
符号化部２１は、上記した符号化装置１と、同等の機能を有している。これは、相関計算部２２で、検出対象語との相関を求めるための各利用者の識別情報ｕに基づく符号語ｗｕが必要になるため、更に、閾値Ｚを得るために備えているものである。従って、符号化部２１の代わりに、符号化装置１での生成した符号語ｗｕ、閾値Ｚを記憶しておき、記憶した内容を利用するような構成でも良い。
【００８５】
デジタルコンテンツから検出装置３で検出された検出対象符号語ｙを検出装置３から受け取り一時的に保持しておく。
【００８６】
相関計算部２２は、デジタルコンテンツから検出装置３で検出された検出対象符号語ｙと、符号化部２１からのｗｕとを入力し、それらの符号の間の相関値σ（ｗｕ，ｙ）を計算し、計算結果を出力する。相関値σ（ｗｕ，ｙ）の計算は、各ビットの値が１のときに、個数を求める計算を行う。
【００８７】
不正者判定部２３は、相関計算部２２が出力した相関値が、ｍＭＩＮを与えた場合のα’の値に対する閾値Ｚ（＋）を超えるか否かを判定する。超える場合には、識別情報ｕの利用者が不正者であるという旨の出力を行う。超えない場合には、不正者とはいえない旨の出力を行う。
【００８８】
次に、このような符号語生成装置１の動作について図１３を用いて説明する。
【００８９】
まず、相関計算部２２は、検出装置１で検出された検出対象符号語ｙを入力する（ステップＳ４１）。また、符号化部２１（または符号語を記憶した記憶部）から、調べる符号語ｗｕをひとつ入力する（ステップＳ４２）。相関計算部２２は、入力された検出対象符号語ｙと符号語ｗｕの各ビット間を比較し、相関値を計算する（ステップＳ４３）。
【００９０】
不正者判定部２３は、符号化部２１（または、閾値Ｚを記憶した記憶部）から得られた閾値Ｚより、該計算された相関値が小さいかを確認する（Ｓステップ４４）。もし、相関値のほうが大きければ、調べた符号語ｗｕに対応する識別情報を出力する（ステップＳ４５）。これはこの識別情報に対応する利用者が、結託者であることを示す。一方、相関値のほうが小さければ、結託者であるとは断定できないとして、次に、調べる符号語ｗｕがあるか否かを確認し（ステップＳ４６）、あればステップＳ４２の処理に戻る。なお、ステップＳ４５で識別情報を出力した後、更に結託者を探す処理（ステップＳ４６へ）に進んでも良いし、結託者を探す処理を終了しても良い。
【００９１】
以上のように、本実施の形態によれば、本発明によれば、誤りεを持つｃ−ｓｅｃｕｒｅ符号であることを維持しつつ、より短い符号長ｍを実現できるようになった。その結果、実用性に優れた結託耐性符号を提供できる。
【００９２】
次に、他の実施形態を説明する。
【００９３】
式［数５］に変えて、より厳密な以下の不等式を用いても、Ｔａｒｄｏｓ符号は、誤りεを持つｃ−ｓｅｃｕｒｅ符号となる。
【数２１】
【００９４】
ここで、Ｂはαとｃに依存する関数で、以下のように定義される。
【数２２】
【００９５】
Ｅは期待値を表し、ｐ＝（ｐｉ）ｉ＝１，。。。，ｍとｗｕ＝（ｗｕ，ｉ）ｉ＝１、・・・ｍに関してとられる。
【００９６】
式［数６］と式［数２１］とを用いて符号長を決定する場合、式［数２１］の左辺が大きいほうがより短い符号長を与える。
【００９７】
上の考え方に従って、先の実施形態の最適Z計算部１１と最適符号長計算部１２とを合わせた機能として、代わりに、別の最適符号長計算部３１による実施形態を、図１４を用いて説明する。
【００９８】
最適符号長計算部３１は、ε／ｎ計算部４１、α’系列生成部４２、α系列生成部４３、Z系列生成部４４、Ａ計算部４５、Ｂ計算部４６、下限計算部４７、上限計算部４８、および、最小下限計算部４９を備える。
【００９９】
本実施形態では、Ａの他に式［数２２］で定義されたＢという量の計算が必要となる。Ｂはパラメータαとｃに依存する量である。そのため、Ａの場合と同様に、α系列生成部４３が生成したαの値の系列α１，α２，・・・，αＭの各値に対して、Ｂ計算部４６は、ｃとαｉから、それぞれのＢの値、Ｂ１，Ｂ２，・・・，ＢＭを計算する。Ｂ計算部４６は、（α１，Ｂ１），（α２，Ｂ２），・・・，（αＭ，ＢＭ）を出力する。
【０１００】
Ｚ系列生成部４４は、想定するＺの値の範囲内から所定の間隔でＺの値の系列Ｚ１，Ｚ２，・・・，ＺＭを生成する。
【０１０１】
下限計算部４７は、ε／ｎ計算部４１が出力したε／ｎとｃとそれぞれＡ計算部４５が出力した系列とを入力として、式［数６］の左辺に相当する、
【数２３】
【０１０２】
を各ｉ＝１，２，・・・，Ｍと各ｊ＝１，２，・・・，Ｍに対して計算し、系列（α’１，Ｚ１，ｍｍｉｎ，１，１），・・・，（α’１，ＺＭ，ｍｍｉｎ，１，Ｍ），・・・，（α’Ｍ，Ｚ１，ｍｍｉｎ，Ｍ，１），・・・，（α’Ｍ，ＺＭ，ｍｍｉｎ，Ｍ，Ｍ）を出力する。
【０１０３】
上限計算部４８は、ε／ｎ計算部が出力したε／ｎとｃとそれぞれＢ計算部が出力した系列を入力として、式［数２２］の左辺に相当する、
【数２４】
を各ｉ＝１，２，・・・，Ｍと各ｊ＝１，２，・・・，Ｍに対して計算し、系列（α１，Ｚ１，ｍｍａｘ，１，１），・・・，（α１，ＺＭ，ｍｍａｘ，１，Ｍ），・・・，（αＭ，Ｚ１，ｍｍａｘ，Ｍ，１），・・・，（αＭ，ＺＭ，ｍｍａｘ，Ｍ，Ｍ）を出力する。
【０１０４】
最小下限計算部４９は、上限計算部の出力と下限計算部の出力から、各（ｉ，ｊ，ｋ）∈｛１，・・・，Ｍ｝３に対して、条件ｍｍｉｎ，ｉ，ｊ≦ｍｍａｘ，ｋ，ｊを満たすもののうち、最小のｍｍｉｎ，ｉ，ｊ≡ｍＭＩＮを与える（ｉ，ｊ，ｋ）≡（ｉＭＩＮ，ｊＭＩＮ，ｋＭＩＮ）を選択する。ＺＭＩＮ≡ＺｊＭＩＮとして、ＺＭＩＮ，ｍＭＩＮを出力する。
【０１０５】
以上のような本実施の形態によれば、先の実施の形態よりも、より厳密な［数２２］の不等式を用いるから、誤りεを持つｃ−ｓｅｃｕｒｅ符号であることを維持しつつ、より短い符号長で実現できる可能性を秘めている。その結果、実用性に優れた結託耐性符号を提供できる。
【図面の簡単な説明】
【０１０６】
【図１】本実施の形態の符号化装置／追跡装置が利用されるシステムの一例を示す図。
【図２】符号化法の概略動作を示す図。
【図３】符号語ｙの追跡法の概略動作を示す図。
【図４】少なくとも一人の不正者が追跡されることを示すグラフ。
【図５】［数７］と［数８］の式をグラフ化した図。
【図６】［数１５］の式のｄｍ／ｄαを示したグラフ。
【図７】符号化装置１の全体を示した図。
【図８】最適Ｚ計算部１１内の機能ブロックを示す図。
【図９】最適符号長計算部１２内の機能ブロックを示す図。
【図１０】符号語生成部１３内の機能ブロックを示す図。
【図１１】符号語生成装置１の動作について示した図。
【図１２】追跡装置４の全体を示した図。
【図１３】符号語生成装置１の動作について示した図。
【図１４】別の最適符号長計算部３１による実施形態を示した図。
【符号の説明】
【０１０７】
１・・・符号化装置
２・・・埋込み装置
３・・・検出装置
４・・・追跡装置
１１・・・最適Ｚ計算部
１２、３１・・・最適符号長計算部
１３・・・符号語生成部
１６・・・パラメータ入力部
１７・・・符号語出力部
２１・・・符号化部
２２・・・相関計算部
２３・・・不正者判定部
４１、１１０、２１０・・・ε／ｎ計算部
４２、１２０・・・α’系列生成部
４３・・・α系列生成部
４４・・・Z系列生成部
４５、１３０・・・Ａ計算部
４６・・・Ｂ計算部
４７・・・下限計算部
４８・・・上限計算部
４９・・・最小下限計算部
１４０・・・Ｚ（＋）計算部
２２０・・・ｍｍｉｎ計算部
２３０・・・ｍＭＩＮ決定部
３１０・・・ｐｉ生成部
３２０・・・ｗｕ，ｉ生成部
【技術分野】
【０００１】
本発明は、デジタルコンテンツの流通に際し、デジタルフィンガープリンティングで埋め込まれる符号語への符号化、または、結託により改ざんされたデジタルコンテンツからの結託者の符号語の追跡に係る符号化装置、追跡装置、符号化方法、追跡方法、および、プログラムに関する。
【背景技術】
【０００２】
デジタルコンテンツの著作権保護を目的として、コンテンツのコピー毎に異なる識別情報を埋め込み、不正コピーが現れた際に、埋め込まれている識別情報からその出所追跡するスキームをデジタルフィンガープリンティング（ｄｉｇｉｔａｌ ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ）と呼ぶ。
【０００３】
デジタルコンテンツに識別情報を埋め込む方法として、コンテンツの品質を落さずに別の情報を埋め込む電子透かし（ｄｉｇｉｔａｌ ｗａｔｅｒｍａｒｋｉｎｇ）がある。電子透かしには、コンテンツがＭＰＥＧ圧縮やデジタル・アナログ・デジタル変換などのさまざまな操作を受けても埋め込まれた情報が失われないロバスト電子透かし（ｒｏｂｕｓｔ ｄｉｇｉｔａｌ ｗａｔｅｒｍａｒｋｉｎｇ）と呼ばれるものがある。しかし、例えロバスト電子透かしとしても、利用者毎に異なる識別情報が埋め込まれたコンテンツの配布を受けた利用者が結託して、各自のコンテンツを持ち寄り、コピーを比較するとコンテンツ中のコピー毎に異なる部分が分かり、その情報をもとにコンテンツに改ざんを加えることで、埋め込まれた識別情報を改ざん・消去する結託攻撃（ｃｏｌｌｕｓｉｏｎ ａｔｔａｃｋ）が可能である。
【０００４】
結託攻撃に対する対策として、識別情報に対して結託攻撃に強い符号化を施してからコンテンツに埋め込む方法がある。そのような符号を結託耐性符号（ｃｏｌｌｕｓｉｏｎ−ｒｅｓｉｌｉｅｎｔ ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ ｃｏｄｅ）と呼ぶ。誤りεを持つｃ−ｓｅｃｕｒｅ符号（ｃ−ｓｅｃｕｒｅ ｃｏｄｅ ｗｉｔｈ ε−ｅｒｒｏｒ）は、結託者数ｃまでの結託攻撃に対して高々εの追跡誤り確率で少なくとも1人の結託者を特定することが可能な結託耐性符号である。
【０００５】
誤りεを持つｃ−ｓｅｃｕｒｅ符号の構成法の一種として、Ｔａｒｄｏｓ符号（Ｔａｒｄｏｓ ｃｏｄｅ）が、知られている。（例えば、非特許文献１参照）。
【非特許文献１】Ｔａｒｏｄｏｓ，Ｇ．：Ｏｐｔｉｍａｌ Ｐｒｏｂａｂｉｌｉｓｔｉｃ ＦｉｎｇｅｒｐｒｉｎｔｉｎｇＣｏｄｅｓ． Ｉｎ：ＳＴＯＣ’０３，ＡＣＭ（２００３）１１６−１２５
【発明の開示】
【発明が解決しようとする課題】
【０００６】
Ｔａｒｄｏｓ符号は、論理上誤りεを持つｃ−ｓｅｃｕｒｅ符号として有力な方式であるが、現実的には、符号長ｍが長すぎるため、あまり実用的ではなかった。
【０００７】
そこで、本発明は、Ｔａｒｄｏｓ符号を改良し、符号長を短縮しより実用的な符号法を与えるための符号化装置、追跡装置、符号化方法、追跡方法、および、プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成する符号化装置であって、前記追跡装置で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成する閾値計算手段と、前記閾値計算手段で生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択する最適符号長計算手段と、前記最適符号長計算手段で選択された値の符号長で、利用者ごとに異なる符号語を生成する符号語生成手段とを備えたことを特徴とする。
【０００９】
また、本発明は、利用者ごとに異なる符号語を埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡装置であって、不正利用されたデジタルデータの利用者であるか否かの判定のために用いる閾値の候補を計算により複数生成する閾値計算手段と、前記閾値計算手段で生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択する最適符号長計算手段と、前記最適符号長計算手段で選択された値の符号長で、利用者ごとに異なる符号語を生成する符号語生成手段と、前記改ざんデータと、前記符号化生成手段で生成された符号語との相関値をそれぞれ計算する相関計算手段と、前記最適符号長計算手段で選択された符号長に対応する閾値を複数の閾値の候補から選定し、前記相関計算手段で計算された各相関値が該選定された閾値を超えるか否かを判定する判定手段とを備えたことを特徴とする。
【００１０】
また、本発明は、利用者ごとに異なる符号語を符号化装置で生成し、生成された各符号語をそれぞれ埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡装置であって、前記符号化装置で符号語の生成時に生成された閾値と、各符号語とを記憶する記憶手段と、前記改ざんデータと、前記記憶手段で記憶する各符号語との相関値をそれぞれ計算する相関計算手段と、前記相関計算手段で計算された各相関値が前記記憶手段に記憶する閾値を超えるか否かを判定する判定手段とを備えたことを特徴とする。
【００１１】
また、本発明は、結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成する符号化方法であって、前記追跡装置で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成し、該生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択し、該選択された値の符号長で、利用者ごとに異なる符号語を生成するようにした。
【００１２】
また、本発明は、利用者ごとに異なる符号語を埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡方法であって、不正利用されたデジタルデータの利用者であるか否かの判定のために用いる閾値の候補を計算により複数生成し、該生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択し、該選択された値の符号長で、利用者ごとに異なる符号語を生成し、前記改ざんデータと、該生成された符号語との相関値をそれぞれ計算し、該選択された符号長に対応する閾値を複数の閾値の候補から選定し、該計算された各相関値が該選定された閾値を超えるか否かを判定するようにした。
【００１３】
また、本発明は、利用者ごとに異なる符号語を符号化装置で生成し、生成された各符号語をそれぞれ埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡方法であって、前記符号化装置で符号語の生成時に生成された閾値と、各符号語とを記憶手段に記憶し、前記改ざんデータと、前記記憶手段で記憶する各符号語との相関値をそれぞれ計算し、該計算された各相関値が前記記憶手段に記憶する閾値を超えるか否かを判定するようにした。
【００１４】
また、本発明は、結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成させるためにコンピュータで実行されるプログラムであって、前記追跡装置で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成させる第１プログラムコードと、前記第1プログラムコードで生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めさせ、該複数の符号長の値から最も小さい値を選択させる第２プログラムコードと、 前記第２プログラムコードで選択された値の符号長で、利用者ごとに異なる符号語を生成させる第３プログラムコードとを備えた。
【００１５】
また、本発明は、利用者ごとに異なる符号語を埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡させるために、コンピュータで実行されるプログラムであって、不正利用されたデジタルデータの利用者であるか否かの判定のために用いる閾値の候補を計算により複数生成させる第1プログラムコードと、前記第1プログラムコードで生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めさせ、該複数の符号長の値から最も小さい値を選択させる第２プログラムコードと、前記第２プログラムコードで選択された値の符号長で、利用者ごとに異なる符号語を生成させる第３プログラムコードと、前記改ざんデータと、前記第３プログラムコードで生成された符号語との相関値をそれぞれ計算する第４プログラムコードと、前記第２プログラムコードで選択された符号長に対応する閾値を複数の閾値の候補から選定し、前記第４プログラムコードで計算された各相関値が該選定された閾値を超えるか否かを判定する第５プログラムコードとを備えた。
【００１６】
また、本発明は、利用者ごとに異なる符号語を符号化装置で生成し、生成された各符号語をそれぞれ埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡させるために、コンピュータで実行されるプログラムであって、前記符号化装置で符号語の生成時に生成された閾値と、各符号語とを記憶手段に記憶させる第１プログラムコードと、前記改ざんデータと、前記記憶手段で記憶する各符号語との相関値をそれぞれ計算させる第２プログラムコードと、前記第２プログラムコードで計算された各相関値が前記記憶手段に記憶する閾値を超えるか否かを判定する第３プログラムコードとを備えた。
【発明の効果】
【００１７】
本発明によれば、誤りεを持つｃ−ｓｅｃｕｒｅ符号であることを維持しつつ、より短い符号長ｍを実現できる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を用いて本実施の形態を説明する。
【００１９】
図１は、本実施の形態の符号化装置／追跡装置が利用されるシステムの一例を示している。このシステムは、同じデジタルコンテンツを利用したい複数の人に配布する際に利用者ごとにそれぞれ異なる固有の識別情報ｕを決定し、符号化装置１で各識別情報ｕからそれぞれ異なる各符号語ｗｕを生成し、埋込み装置２でデジタルコンテンツに生成された各符号語ｗｕを知覚できないように埋め込み、各符号語ｗｕを埋め込み済みのデジタルコンテンツを各利用者へ配布する。その後、不正な利用者によって、結託攻撃が行われたとする。結託攻撃とは、配布された異なる符号語が埋め込まれたデジタルコンテンツまたはそのコピーを複数入手し、それらの間の違いを見出して得られた知識を用い、埋め込み済みのデジタルコンテンツに埋め込まれる符号語を改ざん・消去しようとする攻撃である。不正な利用者は、結託攻撃によって攻撃された後の結託攻撃済みのデジタルコンテンツを不正に流通させる。不正に流通された結託攻撃済みのデジタルコンテンツを取得し、埋め込み装置２での埋め込み方式に対応する検出方式を備えた検出装置３にて、結託攻撃済みのデジタルコンテンツに埋め込まれている符号語（追跡対象符号語）ｙを検出する。検出された追跡対象符号語ｙを、追跡装置４で検査することによって、この結託攻撃に利用された複数のデジタルコンテンツの利用者のうち少なくとも一人の識別情報がわかる。これにより、結託に携わった少なくとも一人を特定できることになり、デジタルコンテンツの著作権保護につながる。なお、符号化装置１、埋め込み装置２、検出装置３、追跡装置４は、専用装置で構成しても良いが、プロセッサ、主メモリ、ＨＤＤ等を備えた通常のコンピュータ装置に、ソフトウェアプログラムを実行させることにより実現しても良いことは勿論である。また、符号化装置１、埋め込み装置２、検出装置３、追跡装置４は、それぞれ独立した装置構成でも良いし、これらの幾つかを同時に備えた装置構成としても良い。
【００２０】
上記のシステムにおいて、デジタルコンテンツに埋め込む符号語は、結託攻撃に強い符号であることが重要である。そのような符号を結託耐性符号（ｃｏｌｌｕｓｉｏｎ−ｒｅｓｉｌｉｅｎｔ ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ ｃｏｄｅ）と呼ぶ。誤りεを持つｃ−ｓｅｃｕｒｅ符号（ｃ−ｓｅｃｕｒｅ ｃｏｄｅ ｗｉｔｈ ε−ｅｒｒｏｒ）は、結託者数ｃまでの結託攻撃に対して高々εの追跡誤り確率で少なくとも1人の結託者を特定することが可能な結託耐性符号である。Ｔａｒｄｏｓ符号（Ｔａｒｄｏｓ ｃｏｄｅ）は、誤りεを持つｃ−ｓｅｃｕｒｅ符号の構成法の一種であるが、本実施の形態ではこれを一部改良した。これについて、以下に詳細な説明を行う前に、用いる表記方法について定義しておく。
【００２１】
［ｎ］と記すと、１からｎまでの整数の集合を示すとする。また、［ａ，ｂ］は、ａ以上ｂ以下の全ての実数の集合を示すとする。また、ａ∈Ｃは、ａが集合Ｃの元であることを示すとする。また、Ｃ＼Ｄは、集合Ｃと集合Ｄとの差集合を示し、集合Ｃから集合Ｄに属する元を取り除いたものである。例えば、［ｎ］＼［ｃ］は、１からｎまでの整数の集合と１からｃまでの整数の集合の差集合であるので、ｃ＋１からｎまでの整数の集合となる。また、ａ∈ＵＣは、確率変数ａが集合Ｃから一様に値をとることを示す。また、Ｐｒ［Ｅ］は、事象Ｅが生起する確率を示す。また、≡は、記号の定義を示す式に用い、左辺を右辺と定義するか右辺を左辺と定義する場合に用いる。また、対数関数をｌｎ≡ｌｏｇｅとし、ｅは自然対数の底を示し、ｅ＝２．７１８２８・・・である。また、∀ｘＡ（ｘ）は、全てのｘに対して式Ａ（ｘ）が成り立つという意味である。同様に、∀ｘ∈ＣＡ（ｘ）は、Ｃの全ての元に対して式Ａ（ｘ）が成り立つという意味である。また、Ｅｘ［Ｂ（ｘ）］は、Ｂ（ｘ）の期待値を表す記号で、確率変数ｘが集合Ａから値をとるとき、Ｅｘ［Ｂ（ｘ）］≡Σａ∈ＡＰｒ［ｘ＝ａ］Ｂ（ａ）と定義される。また、（ｗｉ）ｉ＝１，,…，８＝（ｗ１，ｗ２，・・・，ｗ８）＝（１，０，１，１，０，１，１，０）である。
【００２２】
まず、符号化法の概略動作を図２を用いて説明する。
【００２３】
以下、利用者数をｎ、想定する最大結託者数をｃ、追跡誤り確率をε、符号長をｍとする。また、利用者の識別情報をｕ∈［ｎ］≡｛１，２，・・・，ｎ｝とする。識別情報ｕ∈［ｎ］の利用者に割り当てられる符号語ｗｕの第ｉビットをｗｕ，ｉ（ｉ＝１・・・ｍ）と示すと、符号生成においてｗｕ，ｉが値1を取る確率をＰｒ［ｗｕ，ｉ＝１］と示す。
【００２４】
まず、各ｉに対してｐｉを生成する（ステップＳ１１）。より詳細には、ｔ＝１／（３００ｃ）、ｔ’＝ａｒｃｓｉｎ ｔ１／２とし、ｒｉ∈［ｔ’，π・２−ｔ’］を一様分布に従う確率変数とし、ｒｉの値をランダムに生成し、ｐｉ＝ｓｉｎ２ｒｉを生成する。
【００２５】
次に、各ｕ、各ｉに対して、Ｐｒ［ｗｕ，ｉ＝１］＝ｐｉ、Ｐｒ［ｗｕ，ｉ＝０］＝１−ｐｉとし、ｗｕ，ｉ∈｛０，１｝をランダムに生成する（ステップＳ１２）。
【００２６】
生成した符号語ｗｕ（＝ｗｕ，１，ｗｕ，２，・・・，ｗｕ，ｍ）を出力する（ステップＳ１３）。
【００２７】
以上のようにして符号語ｗｕ生成される。
【００２８】
一方、符号語ｙの追跡法の概略動作を図３を用いて説明する。
【００２９】
まず、結託攻撃を受けたと想定されるデジタルコンテンツから、検出された追跡対象符号語ｙ（＝ｙ１，ｙ２，・・・，ｙｍ）と、調査対象のある一利用者の識別情報に対応する符号語ｗｕ（＝ｗｕ，１，ｗｕ，２，・・・，ｗｕ，ｍ）とを入力する（ステップＳ２１）。
【００３０】
次に、追跡対象符号語ｙと符号語ｗｕとの相関値Ｓ（ｙ，ｗｕ）を計算する（ステップＳ２２）。この相関値Ｓ（ｙ，ｗｕ）が、閾値Ｚを越えているか否かを判断する（ステップＳ２３）。超えていると判断された場合にはその符号語ｗｕに対応する識別情報の利用者が結託者であると決定し（ステップＳ２４）、超えていなければこの利用者は結託者でないと決定し（ステップＳ２５）、決定結果を出力する（ステップＳ２６）。
【００３１】
以上のことを調査対象の利用者を代えて、順次調べることにより、少なくとも結託者の一人を特定する。
【００３２】
次に、Ｔａｒｄｏｓ符号語ｗｕがｃ−ｓｅｃｕｒｅ符号であるための十分条件を以下に説明する。
【００３３】
ステップＳの相関値の計算を式として示すと以下のようになる
【数１】
【００３４】
符号がｃ−ｓｅｃｕｒｅ符号であるには、いかなるｃ人以下の結託に対しても、確率（１−ε）以上で少なくとも一人の結託者を追跡できなければならない。つまり、結託者数は、１人からｃ人までの任意の数であるとする。そこで、ｃ’人の結託者による攻撃が行われたとする。但し、ｃ’∈［ｃ］とする。
【００３５】
Ｔａｒｄｏｓ特定の符号語を特別扱いするものではないので、一般性を失うことなく、結託者の集合を［ｃ’］とすることができる。このとき、無実の利用者の符号語の集合は、符号語全体の集合と結託者の符号語の集合の差集合［ｎ］＼［ｃ’］である。
【００３６】
ｃ−ｓｅｃｕｒｅ符号は、その定義により追跡誤り確率がε以下でなければならない。追跡誤りが起こる場合として、１）結託者でない人を誤って追跡してしまう、２）結託者を誰一人として追跡できない。これらの追跡誤りが怒る確率の和がε以下ならば、Ｔａｒｄｏｓ符号はｃ−ｓｅｃｕｒｅ符号となる。
【００３７】
判定条件を表す式［数１］より、あるｕ∈［ｎ］＼［ｃ’］は、Ｓ（ｙ，ｗｕ）＞Ｚのとき不正者として誤って追跡される。その確率はＰｒ［Ｓ（ｙ，ｗｕ）＞Ｚ］で表される。
【００３８】
一方、判定条件を表す式［数１］より、結託者ｕ∈［ｃ’］は、Ｓ（ｙ，ｗｕ）＞Ｚのとき追跡されるので、Σｕ∈［ｃ’］Ｓ（ｙ，ｗｕ）＞ｃ’Ｚならば、少なくとも一人の結託者ｕに対しては、Ｓ（ｙ，ｗｕ）＞Ｚとなることが保証されるので、少なくとも一人の不正者が追跡される（図４）。反対に、Σｕ∈［ｃ’］Ｓ（ｙ，ｗｕ）≦ｃ’Ｚのときは、少なくとも一人を追跡されるという保証はなくなる。
【００３９】
以上のことから、次式を満たすときに、Ｔａｒｄｏｓ符号は誤りεを持つｃ−ｓｅｃｕｒｅ符号となる。
【数２】
【数３】
【００４０】
実際、［数２］、［数３］の２つの不等式より、追跡誤り確率が、次式の通りεで抑えられるからである。
【数４】
【００４１】
なお、式［数４］の右辺の第１因子（ｎ−ｃ’）は、不正者でないユーザについての確率を足し上げるためである。
【００４２】
式［数２］と式［数３］の式のそれぞれに、よく知られるＭａｒｋｏｖ不等式（後述）を適用し、次式を得る。
【数５】
【数６】
【００４３】
ここで、Ｍａｒｋｏｖ不等式について説明する。Ｍａｒｋｏｖ不等式は、ある非負の確率変数Ｘと、非負の実数ｖが与えられていたとき、次式のことをいう。
【数７】
【００４４】
Ｍａｒｋｏｖ不等式を使うと、任意の整数αに対して、
【数８】
【００４５】
が成り立つ。
【００４６】
式［数５］、式［数６］のαとα’は、式［数２］、式［数３］のそれぞれに、Ｍａｒｋｏｖ不等式を適用する際に現れる正定数で、Ｔａｒｄｏｓ符号の構成上のパラメータとなる。
【００４７】
また、Ａは、α’とｃに依存する関数で、次式で定義される。
【数９】
【００４８】
Ｅは、期待値を示し、ｐ＝（ｐｉ）ｉ＝１、・・・ｍとｗｕ＝（ｗｕ，ｉ）ｉ＝１、・・・ｍの確率分布に従って計算される。
【００４９】
さらに、Ｔａｒｄｏｓ符号において符号語の各ビットが独立であることを用いると、
【数１０】
【００５０】
となる。ここで、ｘｉは結託者のうち符号語の第ｉビットが１である者の数である。
【００５１】
以上の説明により、Ｔａｒｄｏｓ符号は、符号長ｍが［数５］、［数６］の不等式を満たすとき、誤りεを持つｃ−ｓｅｃｕｒｅ符号となることがわかる。
【００５２】
ところで、従来から知られているＴａｒｄｏｓ符号は、閾値Ｚおよび符号長ｍは、次式によって定められていた。
【数１１】
【数１２】
【００５３】
これらも、式［数５］、式［数６］の不等式を満たすため、誤りεを持つｃ−ｓｅｃｕｒｅ符号となるが、符号長ｍの長さについて考慮されておらず、実際、この符号長ｍでは、長すぎて実用上利用できなかった。
【００５４】
そこで、以下では、符号長ｍを誤りεを持つｃ−ｓｅｃｕｒｅ符号であることを保ちつつ、最小の符号長ｍを求めることについて考察を進める。
【００５５】
図５は、［数５］と［数６］によって、符号長が決まる様子を表している。式［数５］と式［数６］は、それぞれ符号長ｍの上限と下限を与えている。従って、このあいだの黒塗りの領域内にｍが取り得る値がある。なお、符号長ｍは、図５からもわかるように、２つの直線の交点のｍが、ｍの最小値となる。この交点は、次式で表される。
【数１３】
【数１４】
【００５６】
式［数１３］より、ｍが最小になるαを決定する。これはｄｍ／ｄα＝０を満たす極限値を求めることによって行われる（図６）。その結果、
【数１５】
のとき、符号長が最小になり、そのときの閾値Ｚと符号長ｍは、
【数１６】
【数１７】
【００５７】
となる。
【００５８】
式［数１６］、式［数１７］からわかるように、閾値Ｚと符号長ｍとは、α’によって求まる。α’は、小数第２位程度の値を取り得ることがわかっているので、α’をその近辺の値として所定間隔（例えば、０．００１間隔）で変更しつつ、式［数１６］が最小になるα’を探索することにより最小となる符号長ｍと、そのときのα’から式［数１７］を計算することにより得られる閾値Ｚとを決定することができる。
【００５９】
次に、上記で説明してきた本実施の形態の符号長ｍを最小にする誤りεを持つｃ−ｓｅｃｕｒｅ符号を実現する符号化装置および復号装置について、以下に説明する。
【００６０】
図７は、符号化装置１の全体を示した図である。符号化装置１は、パラメータ入力部１６、最適Ｚ計算部１１、最適符号長計算部１２、符号語生成部１３、および、符号語出力部１７とを備える。
【００６１】
パラメータ入力部１６は、図示しない表示装置やキーボードなどのマンマシン・インタフェースを介し、本装置を利用する人から、配布するデジタルコンテンツを利用する利用者数（配布数）ｎ、想定する最大結託者数ｃ、および、追跡誤り確率εの入力を受け、一時的に保持する。また、パラメータ入力部１６は、利用者数ｎに基づき、ユーザ識別情報ｕ１・・・ｎを自動生成する。なお、この自動生成に代え、ユーザが識別情報を１つずつ入力するようにしても良い。
【００６２】
最適Ｚ計算部１１は、パラメータｎ、ｃ、εの入力を受け、復号時に利用される最適な閾値Ｚ（＋）を求めるための閾値候補群Ｚ１（＋），Ｚ２（＋），・・・，ＺＭ（＋）を不定なパラメータα’を残したまま、式［数１８］を計算するものである。
【数１８】
【００６３】
最適Ｚ計算部１１内の機能ブロックを図８に示す。最適Ｚ計算部１１は、ε／ｎ計算部１１０、α’系列生成部１２０、Ａ計算部１３０、Ｚ（＋）計算部１４０を備える。
【００６４】
ε／ｎ計算部１１０は、パラメータ入力部１６からεとｎとを入力し、ε／ｎを計算し、計算結果をＺ（＋）計算部１４０へ出力するものである。
【００６５】
α’系列生成部１２０は、閾値Ｚの最適値がその中に存在すると想定するα’領域内から、α’の値の候補をＭ個生成する。または、α’系列生成部１２０は、上記でも説明したように、小数第２位程度の値を取り得ることがわかっているので、そのようなα’の値の候補をＭ個を予め用意しておいても良い。なお、Ｍは、予め定めた値でも良いし、適宜変更される値であっても良い。α’系列生成部１２０は、α’の値の候補を系列α’１，α’２，・・・，α’ＭとしてＡ計算部１３０およびＺ（＋）計算部１４０へ出力する。
【００６６】
Ａ計算部１３０は、パラメータ入力部１６からｃを入力し、α’系列生成部１２０から入力された系列α’１，α’２，・・・，α’Ｍの各値に対して、Ａを計算する。Ａの計算は、具体的には［数１０］の式の右辺を計算するが、ｙｉに依存しない値を出すために、不等式の最後の右辺を計算する。α’ｉに対するＡの計算結果をＡｉとすると、Ａ計算部１３０は、系列（α’１，Ａ１），（α’２，Ａ２），・・・，（α’Ｍ，ＡＭ）をＺ（＋）計算部１４０へ出力する。
【００６７】
Ｚ（＋）計算部１４０は、入力されたε／ｎと系列（α’１，Ａ１），（α’２，Ａ２），・・・，（α’Ｍ，ＡＭ）とから、各α’ｉに対して、それぞれ式［数１８］に対応した式［数１９］の計算を行うものである。
【数１９】
【００６８】
計算結果は、系列（α’１，Ａ１，Ｚ１（＋）），（α’２，Ａ２，Ｚ２（＋）），・・・，（α’Ｍ，ＡＭ，ＺＭ（＋））として出力する。
【００６９】
次に、最適符号長計算部１２は、符号時に利用される最も小さい符号長ｍＭＩＮを求めるためのものである。最適符号長計算部１２内の機能ブロックを図９に示す。最適符号長計算部１２は、ε／ｎ計算部２１０とｍｍｉｎ計算部２２０とｍＭＩＮ決定部２３０とを備える。
【００７０】
ε／ｎ計算部２１０は、パラメータ入力部１６からεとｎとを入力し、ε／ｎを計算し、計算結果をｍｍｉｎ計算部２２０へ出力する。なお、ε／ｎ計算部２１０は、最適Ｚ計算部１１内のε／ｎ計算部１１０と同一の機能を有しているから、ε／ｎ計算部２１０を省略し、最適Ｚ計算部１１内のε／ｎ計算部１１０から直接入力するようにしても良い。
【００７１】
ｍｍｉｎ計算部２２０は、各α’ｉに対して、次式を計算する。
【数２０】
【００７２】
ｍＭＩＮ決定部２３０は、ｍｍｉｎ１，ｍｍｉｎ２，・・・，ｍｍｉｎＭの中から最小値を求め、その値ｍＭＩＮを出力する。
【００７３】
次に、符号語生成部１３は、識別情報ｕとｍＭＩＮとから符号長ｍＭＩＮビットの符号を生成するものである。符号語生成部１３内の機能ブロックを図１０に示す。符号語生成部１３は、ｐｉ生成部３１０とｗｕ，ｉ生成部３２０とを備える。
【００７４】
ｐｉ生成部３１０は、パラメータ入力部１６からｃを、最適符号長計算部１２からｍＭＩＮを入力し、乱数の系列ｐ１，ｐ２，・・・，ｐｍＭＩＮを生成する。各ｐｉは、ｒｉを［ａｒｃｓｉｎ（１／３００ｃ）１／２，π／２−ａｒｃｓｉｎ（１／３００ｃ）１／２］から一様に選択し、ｐｉ＝ｓｉｎ２ｒｉとする。生成されたｐ１，ｐ２，・・・，ｐｍＭＩＮをｗｕ，ｉ生成部３２０へ出力する。
【００７５】
ｗｕ，ｉ生成部３２０は、ｉ＝１，２，・・・，ｍＭＩＮに対して、入力されたｐｉの値に基づいて、Ｐｒ［ｗｕ，ｉ＝１］＝ｐｉとＰｒ［ｗｕ，ｉ＝０］＝１−ｐｉの確率に従って、ｗｕ，ｉの値をランダムに生成する。こうして得られた符号語ｗｕ＝（ｗｕ，ｉ）ｉ＝１、・・・ｍＭＩＮを出力する。この出力された符号語ｗｕ＝（ｗｕ，ｉ）ｉ＝１、・・・ｍＭＩＮは、符号化装置１の出力となる。
【００７６】
以上のようにして、符号化装置１は、構成される。なお、図７の最適Ｚ計算部１１、最適符号長計算部１２、及び、符号語生成部１３で求められた値を図示しない記憶部へ出力し（図の点線矢印）、記憶させるようにしても良い。
【００７７】
次に、このような符号語生成装置１の動作について図１１を用いて説明する。
【００７８】
パラメータ入力部１６は、利用者数（配布数）ｎ、想定する最大結託者数ｃ、および、追跡誤り確率εの入力を受ける（ステップＳ３１）。最適Ｚ計算部１１は、閾値Ｚ候補を複数生成する（ステップＳ３２）。最適符号長計算部１２は、生成された閾値Ｚ候補群を入力し、複数の符号長を求め、その中から最小となる符号長を決定する（ステップＳ３３）。
【００７９】
パラメータ入力部１６は、符号語生成部１３へ符号化したい識別情報を入力する（ステップＳ３４）。符号語生成部１３は、ステップＳ３３で決定した符号長と、入力された識別情報とに基づき、符号語を生成する（ステップＳ３５）。符号語生成部１３は、生成された符号語を出力する（ステップＳ３６）。なお、生成された符号語は一旦図示しない記憶部に保持し、後で全符号語を纏めて出力するようにしても良い。
【００８０】
まだ、符号化を行う識別情報があるか確認し（ステップＳ３７）、なければ、符号化の処理を終了する。一方、符号化を行う識別情報がまだある場合には、符号語生成対象とする識別情報を更新し（ステップＳ３８）、ステップＳ３４の処理に戻る。
【００８１】
以上のようにして、符号化装置１は、各識別情報ｕに対し各ユーザの符号語ｗｕを生成・出力し、例えば、埋込み装置２は、デジタルコンテンツのコピーごとに、符号語ｗｕを変えて透かし情報として埋め込む。
【００８２】
次に、追跡装置について説明する。図１２は、追跡装置４の全体を示した図である。
【００８３】
追跡装置４は、符号化部２１、相関計算部２２、および、不正者判定部２３を備える。
【００８４】
符号化部２１は、上記した符号化装置１と、同等の機能を有している。これは、相関計算部２２で、検出対象語との相関を求めるための各利用者の識別情報ｕに基づく符号語ｗｕが必要になるため、更に、閾値Ｚを得るために備えているものである。従って、符号化部２１の代わりに、符号化装置１での生成した符号語ｗｕ、閾値Ｚを記憶しておき、記憶した内容を利用するような構成でも良い。
【００８５】
デジタルコンテンツから検出装置３で検出された検出対象符号語ｙを検出装置３から受け取り一時的に保持しておく。
【００８６】
相関計算部２２は、デジタルコンテンツから検出装置３で検出された検出対象符号語ｙと、符号化部２１からのｗｕとを入力し、それらの符号の間の相関値σ（ｗｕ，ｙ）を計算し、計算結果を出力する。相関値σ（ｗｕ，ｙ）の計算は、各ビットの値が１のときに、個数を求める計算を行う。
【００８７】
不正者判定部２３は、相関計算部２２が出力した相関値が、ｍＭＩＮを与えた場合のα’の値に対する閾値Ｚ（＋）を超えるか否かを判定する。超える場合には、識別情報ｕの利用者が不正者であるという旨の出力を行う。超えない場合には、不正者とはいえない旨の出力を行う。
【００８８】
次に、このような符号語生成装置１の動作について図１３を用いて説明する。
【００８９】
まず、相関計算部２２は、検出装置１で検出された検出対象符号語ｙを入力する（ステップＳ４１）。また、符号化部２１（または符号語を記憶した記憶部）から、調べる符号語ｗｕをひとつ入力する（ステップＳ４２）。相関計算部２２は、入力された検出対象符号語ｙと符号語ｗｕの各ビット間を比較し、相関値を計算する（ステップＳ４３）。
【００９０】
不正者判定部２３は、符号化部２１（または、閾値Ｚを記憶した記憶部）から得られた閾値Ｚより、該計算された相関値が小さいかを確認する（Ｓステップ４４）。もし、相関値のほうが大きければ、調べた符号語ｗｕに対応する識別情報を出力する（ステップＳ４５）。これはこの識別情報に対応する利用者が、結託者であることを示す。一方、相関値のほうが小さければ、結託者であるとは断定できないとして、次に、調べる符号語ｗｕがあるか否かを確認し（ステップＳ４６）、あればステップＳ４２の処理に戻る。なお、ステップＳ４５で識別情報を出力した後、更に結託者を探す処理（ステップＳ４６へ）に進んでも良いし、結託者を探す処理を終了しても良い。
【００９１】
以上のように、本実施の形態によれば、本発明によれば、誤りεを持つｃ−ｓｅｃｕｒｅ符号であることを維持しつつ、より短い符号長ｍを実現できるようになった。その結果、実用性に優れた結託耐性符号を提供できる。
【００９２】
次に、他の実施形態を説明する。
【００９３】
式［数５］に変えて、より厳密な以下の不等式を用いても、Ｔａｒｄｏｓ符号は、誤りεを持つｃ−ｓｅｃｕｒｅ符号となる。
【数２１】
【００９４】
ここで、Ｂはαとｃに依存する関数で、以下のように定義される。
【数２２】
【００９５】
Ｅは期待値を表し、ｐ＝（ｐｉ）ｉ＝１，。。。，ｍとｗｕ＝（ｗｕ，ｉ）ｉ＝１、・・・ｍに関してとられる。
【００９６】
式［数６］と式［数２１］とを用いて符号長を決定する場合、式［数２１］の左辺が大きいほうがより短い符号長を与える。
【００９７】
上の考え方に従って、先の実施形態の最適Z計算部１１と最適符号長計算部１２とを合わせた機能として、代わりに、別の最適符号長計算部３１による実施形態を、図１４を用いて説明する。
【００９８】
最適符号長計算部３１は、ε／ｎ計算部４１、α’系列生成部４２、α系列生成部４３、Z系列生成部４４、Ａ計算部４５、Ｂ計算部４６、下限計算部４７、上限計算部４８、および、最小下限計算部４９を備える。
【００９９】
本実施形態では、Ａの他に式［数２２］で定義されたＢという量の計算が必要となる。Ｂはパラメータαとｃに依存する量である。そのため、Ａの場合と同様に、α系列生成部４３が生成したαの値の系列α１，α２，・・・，αＭの各値に対して、Ｂ計算部４６は、ｃとαｉから、それぞれのＢの値、Ｂ１，Ｂ２，・・・，ＢＭを計算する。Ｂ計算部４６は、（α１，Ｂ１），（α２，Ｂ２），・・・，（αＭ，ＢＭ）を出力する。
【０１００】
Ｚ系列生成部４４は、想定するＺの値の範囲内から所定の間隔でＺの値の系列Ｚ１，Ｚ２，・・・，ＺＭを生成する。
【０１０１】
下限計算部４７は、ε／ｎ計算部４１が出力したε／ｎとｃとそれぞれＡ計算部４５が出力した系列とを入力として、式［数６］の左辺に相当する、
【数２３】
【０１０２】
を各ｉ＝１，２，・・・，Ｍと各ｊ＝１，２，・・・，Ｍに対して計算し、系列（α’１，Ｚ１，ｍｍｉｎ，１，１），・・・，（α’１，ＺＭ，ｍｍｉｎ，１，Ｍ），・・・，（α’Ｍ，Ｚ１，ｍｍｉｎ，Ｍ，１），・・・，（α’Ｍ，ＺＭ，ｍｍｉｎ，Ｍ，Ｍ）を出力する。
【０１０３】
上限計算部４８は、ε／ｎ計算部が出力したε／ｎとｃとそれぞれＢ計算部が出力した系列を入力として、式［数２２］の左辺に相当する、
【数２４】
を各ｉ＝１，２，・・・，Ｍと各ｊ＝１，２，・・・，Ｍに対して計算し、系列（α１，Ｚ１，ｍｍａｘ，１，１），・・・，（α１，ＺＭ，ｍｍａｘ，１，Ｍ），・・・，（αＭ，Ｚ１，ｍｍａｘ，Ｍ，１），・・・，（αＭ，ＺＭ，ｍｍａｘ，Ｍ，Ｍ）を出力する。
【０１０４】
最小下限計算部４９は、上限計算部の出力と下限計算部の出力から、各（ｉ，ｊ，ｋ）∈｛１，・・・，Ｍ｝３に対して、条件ｍｍｉｎ，ｉ，ｊ≦ｍｍａｘ，ｋ，ｊを満たすもののうち、最小のｍｍｉｎ，ｉ，ｊ≡ｍＭＩＮを与える（ｉ，ｊ，ｋ）≡（ｉＭＩＮ，ｊＭＩＮ，ｋＭＩＮ）を選択する。ＺＭＩＮ≡ＺｊＭＩＮとして、ＺＭＩＮ，ｍＭＩＮを出力する。
【０１０５】
以上のような本実施の形態によれば、先の実施の形態よりも、より厳密な［数２２］の不等式を用いるから、誤りεを持つｃ−ｓｅｃｕｒｅ符号であることを維持しつつ、より短い符号長で実現できる可能性を秘めている。その結果、実用性に優れた結託耐性符号を提供できる。
【図面の簡単な説明】
【０１０６】
【図１】本実施の形態の符号化装置／追跡装置が利用されるシステムの一例を示す図。
【図２】符号化法の概略動作を示す図。
【図３】符号語ｙの追跡法の概略動作を示す図。
【図４】少なくとも一人の不正者が追跡されることを示すグラフ。
【図５】［数７］と［数８］の式をグラフ化した図。
【図６】［数１５］の式のｄｍ／ｄαを示したグラフ。
【図７】符号化装置１の全体を示した図。
【図８】最適Ｚ計算部１１内の機能ブロックを示す図。
【図９】最適符号長計算部１２内の機能ブロックを示す図。
【図１０】符号語生成部１３内の機能ブロックを示す図。
【図１１】符号語生成装置１の動作について示した図。
【図１２】追跡装置４の全体を示した図。
【図１３】符号語生成装置１の動作について示した図。
【図１４】別の最適符号長計算部３１による実施形態を示した図。
【符号の説明】
【０１０７】
１・・・符号化装置
２・・・埋込み装置
３・・・検出装置
４・・・追跡装置
１１・・・最適Ｚ計算部
１２、３１・・・最適符号長計算部
１３・・・符号語生成部
１６・・・パラメータ入力部
１７・・・符号語出力部
２１・・・符号化部
２２・・・相関計算部
２３・・・不正者判定部
４１、１１０、２１０・・・ε／ｎ計算部
４２、１２０・・・α’系列生成部
４３・・・α系列生成部
４４・・・Z系列生成部
４５、１３０・・・Ａ計算部
４６・・・Ｂ計算部
４７・・・下限計算部
４８・・・上限計算部
４９・・・最小下限計算部
１４０・・・Ｚ（＋）計算部
２２０・・・ｍｍｉｎ計算部
２３０・・・ｍＭＩＮ決定部
３１０・・・ｐｉ生成部
３２０・・・ｗｕ，ｉ生成部
【特許請求の範囲】
【請求項１】
結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成する符号化装置であって、
前記追跡装置で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成する閾値計算手段と、
前記閾値計算手段で生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択する最適符号長計算手段と、
前記最適符号長計算手段で選択された値の符号長で、利用者ごとに異なる符号語を生成する符号語生成手段とを備えたことを特徴とする符号化装置。
【請求項２】
前記閾値計算手段は、許容される閾値の範囲を示す、閾値と符号長の値とを変数とする２次不等式で与えられた解の領域から、閾値の候補を計算により複数生成するようにしたことを特徴とする請求項１に記載の符号化装置。
【請求項３】
利用者ごとに異なる符号語を埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡装置であって、
不正利用されたデジタルデータの利用者であるか否かの判定のために用いる閾値の候補を計算により複数生成する閾値計算手段と、
前記閾値計算手段で生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択する最適符号長計算手段と、
前記最適符号長計算手段で選択された値の符号長で、利用者ごとに異なる符号語を生成する符号語生成手段と、
前記改ざんデータと、前記符号化生成手段で生成された符号語との相関値をそれぞれ計算する相関計算手段と、
前記最適符号長計算手段で選択された符号長に対応する閾値を複数の閾値の候補から選定し、前記相関計算手段で計算された各相関値が該選定された閾値を超えるか否かを判定する判定手段とを備えたことを特徴とする追跡装置。
【請求項４】
前記閾値計算手段は、
許容される閾値の範囲を示す、閾値と符号長の値とを変数とする２次不等式で与えられた解の領域から、閾値の候補を計算により複数生成するようにしたことを特徴とする請求項３に記載の追跡装置。
【請求項５】
利用者ごとに異なる符号語を符号化装置で生成し、生成された各符号語をそれぞれ埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡装置であって、
前記符号化装置で符号語の生成時に生成された閾値と、各符号語とを記憶する記憶手段と、
前記改ざんデータと、前記記憶手段で記憶する各符号語との相関値をそれぞれ計算する相関計算手段と、
前記相関計算手段で計算された各相関値が前記記憶手段に記憶する閾値を超えるか否かを判定する判定手段とを備えたことを特徴とする追跡装置。
【請求項６】
結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成する符号化方法であって、
前記追跡装置で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成し、
該生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択し、
該選択された値の符号長で、利用者ごとに異なる符号語を生成するようにしたことを特徴とする符号化方法。
【請求項７】
利用者ごとに異なる符号語を埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡方法であって、
不正利用されたデジタルデータの利用者であるか否かの判定のために用いる閾値の候補を計算により複数生成し、
該生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択し、
該選択された値の符号長で、利用者ごとに異なる符号語を生成し、
前記改ざんデータと、該生成された符号語との相関値をそれぞれ計算し、
該選択された符号長に対応する閾値を複数の閾値の候補から選定し、該計算された各相関値が該選定された閾値を超えるか否かを判定するようにしたことを特徴とする追跡方法。
【請求項８】
利用者ごとに異なる符号語を符号化装置で生成し、生成された各符号語をそれぞれ埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡方法であって、
前記符号化装置で符号語の生成時に生成された閾値と、各符号語とを記憶手段に記憶し、
前記改ざんデータと、前記記憶手段で記憶する各符号語との相関値をそれぞれ計算し、
該計算された各相関値が前記記憶手段に記憶する閾値を超えるか否かを判定するようにしたことを特徴とする追跡方法。
【請求項９】
結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成させるためにコンピュータで実行されるプログラムであって、
前記追跡装置で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成させる第１プログラムコードと、
前記第1プログラムコードで生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めさせ、該複数の符号長の値から最も小さい値を選択させる第 ２プログラムコードと、
前記第２プログラムコードで選択された値の符号長で、利用者ごとに異なる符号語を生成させる第３プログラムコードとを備え、コンピュータで実行されるプログラム。
【請求項１０】
利用者ごとに異なる符号語を埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡させるために、コンピュータで実行されるプログラムであって、
不正利用されたデジタルデータの利用者であるか否かの判定のために用いる閾値の候補を計算により複数生成させる第1プログラムコードと、
前記第1プログラムコードで生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めさせ、該複数の符号長の値から最も小さい値を選択させる第２プログラムコードと、
前記第２プログラムコードで選択された値の符号長で、利用者ごとに異なる符号語を生成させる第３プログラムコードと、
前記改ざんデータと、前記第３プログラムコードで生成された符号語との相関値をそれぞれ計算する第４プログラムコードと、
前記第２プログラムコードで選択された符号長に対応する閾値を複数の閾値の候補から選定し、前記第４プログラムコードで計算された各相関値が該選定された閾値を超えるか否かを判定する第５プログラムコードとを備え、コンピュータで実行されるプログラム。
【請求項１１】
利用者ごとに異なる符号語を符号化装置で生成し、生成された各符号語をそれぞれ埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡させるために、コンピュータで実行されるプログラムであって、
前記符号化装置で符号語の生成時に生成された閾値と、各符号語とを記憶手段に記憶させる第１プログラムコードと、
前記改ざんデータと、前記記憶手段で記憶する各符号語との相関値をそれぞれ計算させる第２プログラムコードと、
前記第２プログラムコードで計算された各相関値が前記記憶手段に記憶する閾値を超えるか否かを判定する第３プログラムコードとを備え、コンピュータで実行されるプログラム。
【請求項１】
結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成する符号化装置であって、
前記追跡装置で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成する閾値計算手段と、
前記閾値計算手段で生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択する最適符号長計算手段と、
前記最適符号長計算手段で選択された値の符号長で、利用者ごとに異なる符号語を生成する符号語生成手段とを備えたことを特徴とする符号化装置。
【請求項２】
前記閾値計算手段は、許容される閾値の範囲を示す、閾値と符号長の値とを変数とする２次不等式で与えられた解の領域から、閾値の候補を計算により複数生成するようにしたことを特徴とする請求項１に記載の符号化装置。
【請求項３】
利用者ごとに異なる符号語を埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡装置であって、
不正利用されたデジタルデータの利用者であるか否かの判定のために用いる閾値の候補を計算により複数生成する閾値計算手段と、
前記閾値計算手段で生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択する最適符号長計算手段と、
前記最適符号長計算手段で選択された値の符号長で、利用者ごとに異なる符号語を生成する符号語生成手段と、
前記改ざんデータと、前記符号化生成手段で生成された符号語との相関値をそれぞれ計算する相関計算手段と、
前記最適符号長計算手段で選択された符号長に対応する閾値を複数の閾値の候補から選定し、前記相関計算手段で計算された各相関値が該選定された閾値を超えるか否かを判定する判定手段とを備えたことを特徴とする追跡装置。
【請求項４】
前記閾値計算手段は、
許容される閾値の範囲を示す、閾値と符号長の値とを変数とする２次不等式で与えられた解の領域から、閾値の候補を計算により複数生成するようにしたことを特徴とする請求項３に記載の追跡装置。
【請求項５】
利用者ごとに異なる符号語を符号化装置で生成し、生成された各符号語をそれぞれ埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡装置であって、
前記符号化装置で符号語の生成時に生成された閾値と、各符号語とを記憶する記憶手段と、
前記改ざんデータと、前記記憶手段で記憶する各符号語との相関値をそれぞれ計算する相関計算手段と、
前記相関計算手段で計算された各相関値が前記記憶手段に記憶する閾値を超えるか否かを判定する判定手段とを備えたことを特徴とする追跡装置。
【請求項６】
結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成する符号化方法であって、
前記追跡装置で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成し、
該生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択し、
該選択された値の符号長で、利用者ごとに異なる符号語を生成するようにしたことを特徴とする符号化方法。
【請求項７】
利用者ごとに異なる符号語を埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡方法であって、
不正利用されたデジタルデータの利用者であるか否かの判定のために用いる閾値の候補を計算により複数生成し、
該生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めて、該複数の符号長の値から最も小さい値を選択し、
該選択された値の符号長で、利用者ごとに異なる符号語を生成し、
前記改ざんデータと、該生成された符号語との相関値をそれぞれ計算し、
該選択された符号長に対応する閾値を複数の閾値の候補から選定し、該計算された各相関値が該選定された閾値を超えるか否かを判定するようにしたことを特徴とする追跡方法。
【請求項８】
利用者ごとに異なる符号語を符号化装置で生成し、生成された各符号語をそれぞれ埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡するための追跡方法であって、
前記符号化装置で符号語の生成時に生成された閾値と、各符号語とを記憶手段に記憶し、
前記改ざんデータと、前記記憶手段で記憶する各符号語との相関値をそれぞれ計算し、
該計算された各相関値が前記記憶手段に記憶する閾値を超えるか否かを判定するようにしたことを特徴とする追跡方法。
【請求項９】
結託して作られた不正デジタルデータに残る改ざんデータから不正利用されたデジタルデータの利用者を追跡装置で追跡するために、デジタルデータへ埋め込まれる、利用者ごとに異なる符号語を生成させるためにコンピュータで実行されるプログラムであって、
前記追跡装置で不正者追跡のための判定のために用いる閾値の候補を計算により複数生成させる第１プログラムコードと、
前記第1プログラムコードで生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めさせ、該複数の符号長の値から最も小さい値を選択させる第 ２プログラムコードと、
前記第２プログラムコードで選択された値の符号長で、利用者ごとに異なる符号語を生成させる第３プログラムコードとを備え、コンピュータで実行されるプログラム。
【請求項１０】
利用者ごとに異なる符号語を埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡させるために、コンピュータで実行されるプログラムであって、
不正利用されたデジタルデータの利用者であるか否かの判定のために用いる閾値の候補を計算により複数生成させる第1プログラムコードと、
前記第1プログラムコードで生成された複数の閾値の候補のそれぞれに対応する複数の符号長の値を計算により求めさせ、該複数の符号長の値から最も小さい値を選択させる第２プログラムコードと、
前記第２プログラムコードで選択された値の符号長で、利用者ごとに異なる符号語を生成させる第３プログラムコードと、
前記改ざんデータと、前記第３プログラムコードで生成された符号語との相関値をそれぞれ計算する第４プログラムコードと、
前記第２プログラムコードで選択された符号長に対応する閾値を複数の閾値の候補から選定し、前記第４プログラムコードで計算された各相関値が該選定された閾値を超えるか否かを判定する第５プログラムコードとを備え、コンピュータで実行されるプログラム。
【請求項１１】
利用者ごとに異なる符号語を符号化装置で生成し、生成された各符号語をそれぞれ埋め込んだデジタルデータの幾つかに基づいて作られた不正デジタルデータから検出された改ざんデータから不正利用されたデジタルデータの利用者を追跡させるために、コンピュータで実行されるプログラムであって、
前記符号化装置で符号語の生成時に生成された閾値と、各符号語とを記憶手段に記憶させる第１プログラムコードと、
前記改ざんデータと、前記記憶手段で記憶する各符号語との相関値をそれぞれ計算させる第２プログラムコードと、
前記第２プログラムコードで計算された各相関値が前記記憶手段に記憶する閾値を超えるか否かを判定する第３プログラムコードとを備え、コンピュータで実行されるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２００７−１７８８５７（Ｐ２００７−１７８８５７Ａ）
【公開日】平成１９年７月１２日（２００７．７．１２）
【国際特許分類】
【出願番号】特願２００５−３７９１７５（Ｐ２００５−３７９１７５）
【出願日】平成１７年１２月２８日（２００５．１２．２８）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成１９年７月１２日（２００７．７．１２）
【国際特許分類】
【出願日】平成１７年１２月２８日（２００５．１２．２８）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]