(57)【要約】【課題】  フィンガープリンティングスキームにおいて埋め込まれる識別情報を第三者から読出不可とし、利用者のプライバシを保護する。【解決手段】  利用者の識別番号ｕを剰余符号＜ｑ１，・・・，ｑＮ＞に変換して電子透かし埋込処理によりコンテンツ情報に埋め込む際に、予め秘密鍵ｓに基づいて識別番号ｕ又は剰余符号＜ｕ１，・・・，ｕＮ＞に暗号化処理を施す。これにより、秘密鍵ｓを知らない第三者が電子透かしを不正に検出し、暗号化された識別番号ｖを得たとしても、暗号化前の正当な識別番号ｕを得ることができないので、利用者のプライバシを保護できる。【選択図】      図１
2005165231.tif 000002
【特許請求の範囲】
【請求項１】
利用者の識別番号を符号化してコンテンツ情報に埋め込むための符号埋込方法において、
秘密鍵を準備する工程と、
前記識別番号を剰余系で表現するための複数個の剰余からなる剰余符号に変換する符号化工程と、
前記符号化工程中、前記識別番号又は剰余符号を前記秘密鍵に基づいて暗号化処理する工程と、
前記符号化工程により得られた剰余符号を電子透かし埋込処理によりコンテンツ情報に埋め込む工程と、
を備えたことを特徴とする符号埋込方法。
【請求項２】
請求項１に記載の符号埋込方法において、
前記暗号化処理は、疑似乱数に基づく置換処理であることを特徴とする符号埋込方法。
【請求項３】
利用者の識別番号を符号化してコンテンツ情報に埋め込むための符号埋込方法において、
前記識別番号を剰余系で表現するための複数個の剰余からなる剰余符号に変換する工程と、
前記剰余符号から各剰余を表す連続した１の列及び０の列からなる複数個の成分符号を生成する工程と、
前記各成分符号を連接して埋込符号を生成する工程と、
秘密鍵を準備する工程と、
前記秘密鍵に基づいて、複数個の疑似乱数を生成する工程と、
前記埋込符号の１又は０に基づいて、前記各疑似乱数をコンテンツ情報に加算又は減算することにより、当該埋込符号を各成分符号内で他の情報が混合しないようにコンテンツ情報に埋込む工程と、
を備えたことを特徴とする符号埋込方法。
【請求項４】
利用者の識別番号を剰余系で表現するための複数個の剰余からなる剰余符号に変換する際に前記識別番号又は剰余符号に暗号化処理が施され、この暗号化処理後の剰余符号が各成分符号が連接されてなる埋込符号として埋め込まれたコンテンツ情報に対し、前記コンテンツ情報から識別番号を復元するための識別情報復元方法において、
前記暗号化処理に対応する復号処理を施すための秘密鍵を準備する工程と、
前記コンテンツ情報から埋込符号を抽出する工程と、
前記抽出された埋込符号を各成分符号に分割する工程と、
前記分割された各成分符号が表す剰余の上下限値を表す剰余対を、各成分符号毎に生成する工程と、
前記生成された各剰余対に基づいて、中国剰余定理により識別番号を復元する復元工程と、
前記復元工程中、前記各剰余対又は識別番号を前記秘密鍵に基づいて復号処理する工程と、
を備えたことを特徴とする識別情報復元方法。
【請求項５】
請求項４に記載の識別情報復元方法において、
前記復号処理は、予め保持する疑似乱数に基づく置換処理であることを特徴とする識別情報復元方法。
【請求項６】
請求項４又は請求項５に記載の識別情報復元方法において、
前記コンテンツ情報から埋込符号を抽出する際に、
前記秘密鍵に基づいて、複数個の疑似乱数を生成する工程と、
前記埋込符号が埋め込まれたコンテンツ情報と前記各疑似乱数との相互相関を計算する工程と、
前記相互相関の計算結果に基づいて、前記コンテンツ情報に埋め込まれた埋込符号が１又は０である旨を決定する工程と、
を備えたことを特徴とする識別情報復元方法。
【請求項７】
互いに素である複数個の整数をそれぞれ法とした剰余の算出により、コンテンツ情報の利用者の識別番号を複数個の剰余からなる剰余符号で表現するための符号化装置であって、
秘密鍵が格納される秘密鍵格納手段と、
前記秘密鍵格納手段内の秘密鍵に基づいて、前記識別番号又は剰余符号に暗号化処理を施す暗号化手段と、
を備えたことを特徴とする符号化装置。
【請求項８】
請求項７に記載の符号化装置において、
前記暗号化手段は、前記暗号化処理の対象が剰余符号のとき、前記剰余符号の各剰余を損なわないように当該剰余符号を暗号化することを特徴とする符号化装置。
【請求項９】
請求項７又は請求項８に記載の符号化装置を備えた符号埋込装置において、
前記符号化装置により得られた剰余符号を電子透かし埋込処理により前記コンテンツ情報に埋め込む埋込手段を備えたことを特徴とする符号埋込装置。
【請求項１０】
請求項９に記載の符号埋込装置において、
前記埋込手段は、
前記剰余符号の各剰余を表す複数個の成分符号を生成する成分符号生成手段と、
前記成分符号生成手段により生成された各成分符号を連接して埋込符号を生成する連接手段と、
前記連接手段により生成された埋込符号を電子透かし埋込処理により前記コンテンツ情報に埋め込む電子透かし処理手段と、
を備えたことを特徴とする符号埋込装置。
【請求項１１】
請求項１０に記載の符号埋込装置において、
前記成分符号生成手段は、一定のビット数を一単位として連続した１の列及び０の列で構成される符号を前記各成分符号として生成することを特徴とする符号埋込装置。
【請求項１２】
請求項１１に記載の符号埋込装置において、
前記法の個数をＮとし、Ｎ未満の正整数をＮ’とし、２以上の正整数をｃとし、１以上の正整数をｚとし、前記埋込符号の検出時に各成分符号から検出可能な識別番号の個数をｑとして、前記法の個数Ｎ≧ｃ（Ｎ’＋ｚ）／２という関係を満たしており、
前記各成分符号は、前記埋込符号の検出時にコンテンツ情報から利用者の識別番号以外のｃ個の識別番号を検出可能とするｃ−セキュアＣＲＴ符号であることを特徴とする符号埋込装置。
【請求項１３】
利用者の識別番号を剰余系で表現するための複数個の剰余からなる剰余符号を、前記各剰余を表す連続した１の列及び０の列からなる各成分符号が連接されてなる埋込符号としてコンテンツ情報に埋め込む符号埋込装置であって、
秘密鍵が格納される秘密鍵格納手段と、
前記秘密鍵格納手段内の秘密鍵に基づいて、複数個の疑似乱数を生成する疑似乱数生成手段と、
前記埋込符号の１又は０に基づいて、前記各疑似乱数をコンテンツ情報に加算又は減算することにより、当該埋込符号をコンテンツ情報に埋込む埋込手段と、
を備えたことを特徴とする符号埋込装置。
【請求項１４】
利用者の識別番号を剰余系で表現するための複数個の剰余からなる剰余符号に変換する際に前記識別番号又は剰余符号に暗号化処理が施され、この暗号化処理後の剰余符号が電子透かし埋込処理により各成分符号が連接されてなる埋込符号として埋め込まれたコンテンツ情報に対し、前記埋め込まれた剰余符号を検出するための符号検出装置であって、
前記コンテンツ情報から埋込符号を抽出する符号抽出手段と、
前記抽出された埋込符号を各成分符号に分割する符号分割手段と、
前記分割された各成分符号が表す剰余の上下限値を表す剰余対を、各成分符号毎に生成する剰余対生成手段と、
前記各成分符号の剰余対からなる剰余対符号を出力する剰余対符号出力手段と、
を備えたことを特徴とする符号検出装置。
【請求項１５】
請求項１４に記載の符号検出装置を備えた識別情報復元装置において、
前記暗号化処理に対応する復号処理を施すための秘密鍵が格納される秘密鍵格納手段と、
前記符号検出装置から出力された剰余対符号の各剰余対に基づいて、中国剰余定理により識別番号を復元する復元手段とを備え、
前記復元手段は、
前記中国剰余定理による復元前の各剰余対、又は前記中国剰余定理による復元後の識別番号に対し、前記秘密鍵格納手段内の秘密鍵に基づいて復号処理を施す復号手段、
を備えたことを特徴とする識別情報復元装置。
【請求項１６】
請求項１５に記載の識別情報復元装置において、
前記暗号化処理を施す暗号化装置との間で公開鍵基盤を用いた鍵交換プロトコルを実行し、当該暗号化処理に対応する復号処理を施すための秘密鍵を前記暗号化装置から受ける鍵交換手段と、
前記鍵交換手段により受けた秘密鍵を前記秘密鍵格納手段に書込む鍵書込手段と、
を備えたことを特徴とする識別情報復元装置。
【請求項１７】
請求項１５に記載の識別情報復元装置において、
前記暗号化処理を施す暗号化装置を備え、
前記秘密鍵格納手段は、前記暗号化装置と前記復元手段の両者から読出可能であることを特徴とする識別情報復元装置。
【請求項１８】
利用者の識別番号を剰余系で表現するための複数個の剰余からなる剰余符号が、前記各剰余を表す連続した１の列及び０の列からなる各成分符号が連接されてなる埋込符号に変換され、予め秘密鍵から生成した疑似乱数が前記埋込符号の１又は０に基づいてコンテンツ情報に加算又は減算されることにより前記埋込符号が埋め込まれたコンテンツ情報に対し、前記コンテンツ情報から埋込符号を検出するための符号検出装置であって、
前記秘密鍵が格納される秘密鍵格納手段と、
前記秘密鍵格納手段内の秘密鍵に基づいて、複数個の疑似乱数を生成する疑似乱数生成手段と、
前記埋込符号が埋め込まれたコンテンツ情報と前記各疑似乱数との相互相関を計算する相互相関計算手段と、
前記相互相関の計算結果に基づいて、前記コンテンツ情報に埋め込まれた埋込符号が１又は０である旨を決定する埋込符号決定手段と、
を備えたことを特徴とする符号検出装置。
【請求項１９】
請求項１８に記載の符号検出装置において、
前記埋込符号決定手段により決定された埋込符号を各成分符号に分割する符号分割手段と、
前記分割された各成分符号が表す剰余の上下限値を表す剰余対を、各成分符号毎に生成する剰余対生成手段と、
前記各成分符号の剰余対からなる剰余対符号を出力する剰余対符号出力手段と、
を備えたことを特徴とする符号検出装置。
【請求項２０】
請求項１９に記載の符号検出装置を備えた識別情報復元装置において、
前記符号検出装置から出力された剰余対符号の各剰余対に基づいて、中国剰余定理により識別番号を復元する復元手段を備えたことを特徴とする識別情報復元装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号埋込方法、識別情報復元方法及び装置に関する。
【背景技術】
【０００２】
一般に、デジタルデータ又は物理的実体からなるオブジェクトに対し、当該オブジェクトの構造や構成を変更して識別情報を書込み、後日、識別情報を読出してオブジェクトを追跡するスキームをフィンガープリンティングスキームと呼ぶ。
【０００３】
ここで、オブジェクトは、デジタルデータ又は物理的実体のいずれでもよい。デジタルデータとしては、例えば映画、音楽、静止画、プログラム、論理構造記述などがある。一方、物理的実体としては、例えば化合物や混合物、遺伝子情報を含むＤＮＡ（デオキシリボ核酸）やＲＮＡ（リボ核酸）あるいはタンパク質などがある。
【０００４】
識別情報の書込方法は任意であり、オブジェクトがデジタルコンテンツの場合、電子透かしによって識別情報を埋込可能である（例えば非特許文献１参照。）。一方、オブジェクトが物理的実体の場合、その組成を物理的又は化学的に識別可能に変更して識別情報を埋込可能である。特に、遺伝子情報を含む物理的実体の場合、遺伝子組換えや塩基配列の置換、タンパク質のアミノ酸配列の置換などにより、識別情報を埋込可能である。
【０００５】
しかしながら、以上のようなフィンガープリンティングスキームは、悪意を持つ複数の者による結託攻撃を受ける場合がある。結託攻撃とは、互いに異なる識別情報が埋め込まれた各オブジェクトを比較し、比較結果の差異に関する情報を用いて識別情報を改ざんし、追跡を妨害する操作である。例えば悪意あるパーティがデジタルコンテンツの海賊版を配布する際に、結託攻撃を行う場合がある。
【０００６】
一方、このような結託攻撃を防止する観点から、識別情報の埋込みの際に、一旦、識別情報を符号化し、得られた符号を埋込む符号化方法が考えられている。かかる符号化方法の一つとして、ｃ−ｓｅｃｕｒｅ ＣＲＴ符号（以下、ｃ−セキュアＣＲＴ符号という）が知られている（例えば、非特許文献２及び特許文献１参照。）。ｃ−セキュアＣＲＴ符号とは、最大ｃ人の結託者による結託攻撃を受けても結託者を指摘可能なセキュアな性質を有し、中国剰余定理（CRT; Chinese Remainder Theorem）を用いて構成された符号化方法である。
【０００７】
なお、ｃ−セキュアＣＲＴ符号及びそれと同様の符号では、識別情報の集合Ｕの元ｕが、複数の集合Ｑ１，…，ＱＮの元の組ｕ１，…，ｕＮで表現される。なお、ｕｉは集合Ｑｉの元である。集合ＵやＱｉは、例えばＵ＝ＺＮ やＱｉ=Ｚｐｉと定められることがある。ここで、ＺＮはＮ未満の非負整数の集合である。Ｎは利用者の識別に十分な大きさの非負整数である。ｐｉはＮよりも小さい非負整数である。
【非特許文献１】「インフォメーション・ハイディングテクニック・フォー・ステガノグラフィ・アンド・デジタル・ウォーターマーキング（Information Hiding - technique for steganography and digital watermarking）」，S. Katzenbeisser and Faibien A. P. Petitcolas, 2000.
【非特許文献２】村谷博文（H. Muratani），「ア・コルージョン・セキュア・フィンガープリンティング・コード・リジュースト・バイ・チャイニーズ・リマインダリング・アンド・イッツ・ランダム・エラー・レジリエンス（A collusion-secure fingerprinting code reduced by Chinese remaindering and itｓrandom-error resilience）」，ピーアールオーシー・フォース・インフォメーション・ハイディング・ワークショップ（Proc. Fourth Information Hiding Workshop），IHW 2001，LNCS 2137，シュプリンガー・フェアラーク（Springer-Verlag），２００１年、ｐ．３０３−３１５．
【特許文献１】特開２００１ −２８５６２３号公報。
【非特許文献３】「ザ・フェデラル・インフォメーション・プロシーディング・スタンダード・（エフアイピーエス）・フォー・ジ・アドバンスト・エンクリプション・スタンダード（the Federal Information Processing Standard （FIPS） for the Advanced Encryption Standard）」、ＦＩＰＳ−１９７．
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、以上のような符号化埋込方法では、通常は問題ないと考えられるが、本発明者の検討によれば、悪意の第三者が結託し、コンテンツの電子透かしを検出してコンテンツから識別情報を読み出す可能性を完全には否定できない。また、仮に識別情報が読み出された場合、その識別情報が利用者ＩＤであると、利用者ＩＤに対応する利用者のプライバシが侵害される可能性がある。
【０００９】
本発明は上記実情を考慮してなされたもので、フィンガープリンティングスキームにおいて埋め込まれる識別情報を第三者から読出不可とし、利用者のプライバシを保護し得る符号化埋込方法、識別番号復元方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
第１の発明は、利用者の識別番号を符号化してコンテンツ情報に埋め込むための符号埋込方法において、秘密鍵を準備する工程と、前記識別番号を剰余系で表現するための複数個の剰余からなる剰余符号に変換する符号化工程と、前記符号化工程中、前記識別番号又は剰余符号を前記秘密鍵に基づいて暗号化処理する工程と、前記符号化工程により得られた剰余符号を電子透かし埋込処理によりコンテンツ情報に埋め込む工程と、を備えた符号埋込方法である。
【００１１】
第２の発明は、利用者の識別番号を剰余系で表現するための複数個の剰余からなる剰余符号に変換する際に前記識別番号又は剰余符号に暗号化処理が施され、この暗号化処理後の剰余符号が各成分符号が連接されてなる埋込符号として埋め込まれたコンテンツ情報に対し、前記コンテンツ情報から識別番号を復元するための識別情報復元方法において、前記暗号化処理に対応する復号処理を施すための秘密鍵を準備する工程と、前記コンテンツ情報から埋込符号を抽出する工程と、前記抽出された埋込符号を各成分符号に分割する工程と、前記分割された各成分符号が表す剰余の上下限値を表す剰余対を、各成分符号毎に生成する工程と、前記生成された各剰余対に基づいて、中国剰余定理により識別番号を復元する復元工程と、前記復元工程中、前記各剰余対又は識別番号を前記秘密鍵に基づいて復号処理する工程と、を備えた識別情報復元方法である。
【００１２】
第３の発明は、互いに素である複数個の整数をそれぞれ法とした剰余の算出により、コンテンツ情報の利用者の識別番号を複数個の剰余からなる剰余符号で表現するための符号化装置であって、秘密鍵が格納される秘密鍵格納手段と、前記秘密鍵格納手段内の秘密鍵に基づいて、前記識別番号又は剰余符号に暗号化処理を施す暗号化手段と、を備えた符号化装置である。
【００１３】
第４の発明は、第３の発明の符号化装置を備えた符号埋込装置において、前記符号化装置により得られた剰余符号を電子透かし埋込処理により前記コンテンツ情報に埋め込む埋込手段を備えた符号埋込装置である。
【００１４】
第５の発明は、利用者の識別番号を剰余系で表現するための複数個の剰余からなる剰余符号を、前記各剰余を表す連続した１の列及び０の列からなる各成分符号が連接されてなる埋込符号としてコンテンツ情報に埋め込む符号埋込装置であって、秘密鍵が格納される秘密鍵格納手段と、前記秘密鍵格納手段内の秘密鍵に基づいて、複数個の疑似乱数を生成する疑似乱数生成手段と、前記埋込符号の１又は０に基づいて、前記各疑似乱数をコンテンツ情報に加算又は減算することにより、当該埋込符号をコンテンツ情報に埋込む埋込手段と、を備えた符号埋込装置である。
【００１５】
第６の発明は、利用者の識別番号を剰余系で表現するための複数個の剰余からなる剰余符号に変換する際に前記識別番号又は剰余符号に暗号化処理が施され、この暗号化処理後の剰余符号が電子透かし埋込処理により各成分符号が連接されてなる埋込符号として埋め込まれたコンテンツ情報に対し、前記埋め込まれた剰余符号を検出するための符号検出装置であって、前記コンテンツ情報から埋込符号を抽出する符号抽出手段と、前記抽出された埋込符号を各成分符号に分割する符号分割手段と、前記分割された各成分符号が表す剰余の上下限値を表す剰余対を、各成分符号毎に生成する剰余対生成手段と、前記各成分符号の剰余対からなる剰余対符号を出力する剰余対符号出力手段と、を備えた符号検出装置である。
【００１６】
第７の発明は、第６の発明の符号検出装置を備えた識別情報復元装置において、前記暗号化処理に対応する復号処理を施すための秘密鍵が格納される秘密鍵格納手段と、前記符号検出装置から出力された剰余対符号の各剰余対に基づいて、中国剰余定理により識別番号を復元する復元手段とを備え、前記復元手段は、前記中国剰余定理による復元前の各剰余対、又は前記中国剰余定理による復元後の識別番号に対し、前記秘密鍵格納手段内の秘密鍵に基づいて復号処理を施す復号手段、を備えた識別情報復元装置である。
【００１７】
第８の発明は、利用者の識別番号を剰余系で表現するための複数個の剰余からなる剰余符号が、前記各剰余を表す連続した１の列及び０の列からなる各成分符号が連接されてなる埋込符号に変換され、予め秘密鍵から生成した疑似乱数が前記埋込符号の１又は０に基づいてコンテンツ情報に加算又は減算されることにより前記埋込符号が埋め込まれたコンテンツ情報に対し、前記コンテンツ情報から埋込符号を検出するための符号検出装置であって、前記秘密鍵が格納される秘密鍵格納手段と、前記秘密鍵格納手段内の秘密鍵に基づいて、複数個の疑似乱数を生成する疑似乱数生成手段と、前記埋込符号が埋め込まれたコンテンツ情報と前記各疑似乱数との相互相関を計算する相互相関計算手段と、前記相互相関の計算結果に基づいて、前記コンテンツ情報に埋め込まれた埋込符号が１又は０である旨を決定する埋込符号決定手段と、を備えた符号検出装置である。
【００１８】
ここで、第８の発明は、前記埋込符号決定手段により決定された埋込符号を各成分符号に分割する符号分割手段と、前記分割された各成分符号が表す剰余の上下限値を表す剰余対を、各成分符号毎に生成する剰余対生成手段と、前記各成分符号の剰余対からなる剰余対符号を出力する剰余対符号出力手段と、を備えてもよい。
【００１９】
第９の発明は、第８の発明の符号検出装置を備えた識別情報復元装置において、前記符号検出装置から出力された剰余対符号の各剰余対に基づいて、中国剰余定理により識別番号を復元する復元手段を備えた識別情報復元装置である。
【００２０】
（作用）
従って、第１、第３及び第４の発明は以上のような手段を講じたことにより、利用者の識別番号を剰余符号に変換し、得られた剰余符号を電子透かし埋込処理によりコンテンツ情報に埋め込む際に、識別番号又は剰余符号を秘密鍵に基づいて暗号化処理するので、フィンガープリンティングスキームにおいて埋め込まれる識別情報を第三者から読出不可とし、利用者のプライバシを保護できる。
【００２１】
また、第２、第６及び第７の発明は、前述した第１、第３及び第４の発明による暗号化処理に対応する復号処理を施すための秘密鍵に基づいて、識別番号又は各剰余対を復号処理するので、第１、第３及び第４の発明に対応する作用に加え、識別情報復元装置からは識別情報を読み出すことができる。
【００２２】
また、第５の発明は、利用者の識別番号を剰余系で表現する剰余符号を、１の列及び０の列を含む埋込符号としてコンテンツ情報に埋め込む際に、秘密鍵に基づいて生成した疑似乱数を埋込符号の１，０に応じてコンテンツ情報に加算又は減算することにより、埋込符号をコンテンツ情報に埋め込むので、フィンガープリンティングスキームにおいて埋め込まれる識別情報を第三者から読出不可とし、利用者のプライバシを保護できる。
【００２３】
また、第８の発明は、前述した第５の発明による疑似乱数を生成するための秘密鍵に基づいて、コンテンツ情報に埋め込まれた埋込符号の１，０を決定するので、第８の発明に対応する作用に加え、第５の発明により埋め込まれた埋込符号をコンテンツ情報から読み出すことができる。
【００２４】
また、第９の発明は、前述した第８の発明により決定された埋込符号から得られる剰余対符号の各剰余対に基づいて識別番号を復元できるので、識別情報復元装置からは識別情報を読み出すことができる。
【発明の効果】
【００２５】
以上説明したように本発明によれば、フィンガープリンティングスキームにおいて埋め込まれる識別情報を第三者から読出不可とし、利用者のプライバシを保護できる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明の各実施形態について説明する。なお、以下の各実施形態は、プライバシ侵害を防ぐために、識別情報がオブジェクトに埋め込まれるまでの間に暗号化を施し、第三者に識別情報を知られないようにしている。具体的には、どの段階で暗号化を施すかにより、図１及び以下に示すように、大きく３つの方式（ａ）〜（ｃ）に分類される。
【００２７】
（ａ）識別情報に暗号化を施し、得られた結果をｃ−セキュアＣＲＴ符号により符号化し、得られた符号を電子透かしによりコンテンツに埋め込む（第１，第４の実施形態）。
【００２８】
（ｂ）識別情報をｃ−セキュアＣＲＴ符号により符号化し、得られた符号を暗号化し、得られた結果を電子透かしによりコンテンツに埋め込む（第２，第５の実施形態）。
【００２９】
（ｃ）識別情報をｃ−セキュアＣＲＴ符号により符号化し、得られた符号を検出には鍵が必要となる方式の電子透かしによりコンテンツに埋め込む（第３，第６の実施形態）。
【００３０】
なお、図示しないが、いずれの方式（ａ）〜（ｃ）においても、電子透かしの埋め込みの前にシンボルの組をもう一度別の符号化を施してもよい。例えばシンボルを２進の符号の系列に符号化し、系列中の各値を電子透かしで埋め込んでもよい。
【００３１】
次に、以上のように分類される各実施形態について順次、具体的に説明する。  
（第１の実施形態）
図２は本発明の第１の実施形態に係る埋込装置及び追跡装置を備えたオブジェクト追跡システムの構成を示す模式図であり、図３はこの埋込装置の構成を示す模式図であり、図４はこの追跡装置の構成を示す模式図である。図２に示すオブジェクト追跡システムは、埋込装置（符号埋込装置）１０Ａ及び追跡装置（識別情報復元装置）２０Ａを備えている。図中、鍵情報ｓ，ｓ’は、共通鍵暗号の場合には、ｓ’=ｓ、非対称鍵暗号の場合には、ｓ’は公開鍵ｓに対する秘密鍵である。埋込装置１０Ａと追跡装置２０Ａの間の鍵共有は、例えば、信頼できるパーティによる鍵配布や公開鍵基盤（インフラストラクチャ）を用いた鍵交換プロトコル、秘密のチャンネル（専用線通信）、信頼できる者の間での手渡し、量子暗号、守秘を保証する郵便等を用いることで実現可能である。なお、埋込装置１０Ａと追跡装置２０Ａが同一装置で実現される場合、鍵情報ｓ，ｓ’を外部に出さずに装置内で共有可能である。
【００３２】
ここで、埋込装置１０Ａは、鍵格納部１１、暗号化部１２、符号化部１３及び埋込部１４を備えている。
【００３３】
鍵格納部（秘密鍵格納手段）１１は、暗号化部１２から読出可能となっており、秘密鍵ｓが格納されるメモリである。なお、秘密鍵ｓは、埋込装置１０Ａ内で生成されたものでもよく、外部から入力又は受信されたものでもよい。
【００３４】
暗号化部（暗号化手段）１２は、利用者の識別番号ｕが入力されると、鍵格納部１１内の秘密鍵ｓに基づいてこの識別番号ｕに暗号化処理を施し、この暗号化された識別番号ｖを符号化部１３に送出する機能をもっている。
【００３５】
符号化部１３は、暗号化部１２から識別番号ｖを受けると、互いに素であるＮ個の整数｛ｐ１，ｐ２，…，ｐＮ｝をそれぞれ法とした剰余ｑｉ＝ｖ ｍｏｄ ｐｉの算出（ｉ＝１，２，…，Ｎ）により、識別番号ｖをＮ個の剰余｛ｑ１，ｑ２，…，ｑＮ｝からなる剰余符号＜ｑ１，ｑ２，…，ｑＮ＞で表現する機能と、この剰余符号を埋込部１４に送出する機能とをもっている。
【００３６】
埋込部（埋込手段）１４は、符号化部１３から受けた剰余符号＜ｑ１，ｑ２，…，ｑＮ＞を電子透かし埋込処理によりコンテンツ情報に埋め込むものであり、具体的には、剰余符号の各剰余を表すＮ個の成分符号ｗ１，ｗ２，…，ｗＮを生成する機能と、生成した各成分符号を連接して埋込符号ｗ＝ｗ１‖ｗ２‖…‖ｗＮを生成する機能と、生成した埋込符号ｗを電子透かし埋込処理によりコンテンツ情報に埋め込む機能とをもっている。
【００３７】
ここで図５に示すように、成分符号ｗｉは、一定のビット数ｔを一単位として連続した１の列及び０の列で構成される符号であり、ｃ−セキュアＣＲＴ符号では、各ｑｉがｑｉ×ｔ個の０と、それに続く（ｐｉ−ｑｉ−１）×ｔ個の１のビット系列ｗｉに変換される。ｔは所定のパラメータである。なお、成分符号ｗｉや埋込符号ｗを生成する機能は、符号化部１３に持たせてもよい。
【００３８】
ｃ−セキュアＣＲＴ符号化の場合、法の個数をＮとし、Ｎ未満の正整数をＮ’とし、２以上の正整数をｃとし、１以上の正整数をｚとし、埋込符号の検出時に各成分符号から検出可能な識別番号の個数をｑとしたとき、法の個数Ｎ≧ｃ（Ｎ’＋ｚ）／２という関係を満たしており、各成分符号ｗｉは、埋込符号の検出時にコンテンツ情報から利用者の識別番号以外のｃ個の識別番号を検出可能とするｃ−セキュアＣＲＴ符号である。
【００３９】
一方、追跡装置２０Ａは、鍵格納部２１、検出部２２、追跡部２３及び復号部２４を備えている。
【００４０】
鍵格納部（秘密鍵格納手段）２１は、復号部２４から読出可能となっており、埋込装置１０Ａにおける暗号化処理に対応した復号処理を施すための秘密鍵ｓ’が格納されるメモリである。なお、秘密鍵ｓ’は、公開鍵基盤を用いた鍵交換プロトコルにより埋込装置１０Ａから配送されたものでもよく、操作者の操作により入力されたものでもよい。
【００４１】
検出部（符号検出装置）２２は、コンテンツ情報から埋込符号ｗを抽出する機能と、抽出された埋込符号ｗを各成分符号ｗ１，…，ｗＮに分割する機能と、分割された各成分符号ｗｉが表す剰余ｑｉの上下限値を表す剰余対＜ｑｉ(−)，ｑｉ(＋)＞を、各成分符号毎に生成する機能と、各成分符号の剰余対からなる剰余対符号＜＜ｑ１(−)，ｑ１(＋)＞，…，＜ｑＮ(−)，ｑＮ(＋)＞＞を追跡部２３に送出する機能とを持っている。
【００４２】
追跡部（復元手段）２３は、検出部２２から受けた剰余対符号の各剰余対＜ｑｉ(−)，ｑｉ(＋)＞に基づいて、中国剰余定理により識別番号ｖを算出する機能と、算出した識別番号ｖに対し、各剰余対＜ｑｉ(−)，ｑｉ(＋)＞の少なくとも一方の剰余との間で合同式（法ｐｉ）が成立するｉの個数を計算する機能と、得られたｉの個数がしきい値Ｄｔｈ以上のとき、その識別番号ｖを復号部２４に出力する機能とをもっている。
【００４３】
例えば、追跡部２３は、各剰余対ｑ１(−)，ｑ１(＋)，・・・，ｑＮ(−)，ｑＮ(＋)に対して、追跡候補となっている各識別番号ｖ毎にｖ≡ｑｉ(−)（ｍｏｄ ｐｉ）またはｖ≡ｑｉ(＋)（ｍｏｄ ｐｉ）が成立するｉの個数を計算し、得られたｉの個数がしきい値Ｄｔｈ以上のとき、その識別番号ｖを復号部２４に出力する。
【００４４】
しきい値Ｄｔｈは、特許文献１の請求項１０及び（１）式などに開示された次の不等式を満たす場合の「ｋ＋ｚ」である。
【数１】
2005165231.tif 000003
【００４５】
但し、特許文献１中のｋ’は本明細書中のＮ（＝法の個数）であり、特許文献１中のｋは本明細書中のＮ’（＝Ｎ未満の正整数）である。このため、Ｄｔｈ＝Ｎ’＋ｚである。
【００４６】
復号部（復号手段）２４は、追跡部２３から受けた識別番号ｖに対し、鍵格納部２１内の秘密鍵ｓ’に基づいて復号処理を施し、識別番号ｕを復元する機能をもっている。
【００４７】
次に、以上のように構成されたオブジェクト追跡システムの動作を説明する。  
（埋込装置１０Ａ側の処理）
埋込装置１０Ａでは、識別番号ｕが埋め込まれるオブジェクトとしてのコンテンツ情報と、識別番号の集合Ｕに属する元ｕとしての識別番号ｕとが入力されたとする。
【００４８】
暗号化部１２は、識別番号ｕが入力されると、鍵格納部１１内の秘密鍵ｓに基づいて識別番号ｕに暗号化処理を施し、得られた識別情報ｖを符号化部１３に送出する。
【００４９】
暗号化処理の方法は任意であり、例えば非特許文献３に記載の米国標準暗号ＡＥＳであれば、識別番号の集合Ｕ＝Ｚ2128 とする。秘密鍵ｓは鍵空間Ｋ＝Ｚ128 から選ばれる。暗号化処理の詳細は、非特許文献３に詳細に記載されている。この暗号化処理は、ＵからＶへの全単射な写像Ｐ［ｓ］を与える。
【００５０】
符号化部１３は、暗号化された識別情報ｖを受けると、識別番号ｖを符号化して剰余符号を埋込部１４に出力する。符号化としては、例えばｃ−セキュアＣＲＴ符号が適用される。符号化の処理の詳細は、非特許文献２及び特許文献１に開示されている。剰余の集合Ｑｉ＝Ｚpi とされ、法ｐｉはｐ１＜ｐ２＜・・・＜ｐＮ を満たす互いに素な正整数として選択されている。この符号化部１３では、識別番号ｖに対して法ｐｉとした剰余ｑｉ＝ｕ ｍｏｄ ｐｉ が計算され、Ｎ個の剰余ｑ１，ｑ２，・・・，ｑＮからなる剰余符号＜ｑ１，ｑ２，・・・，ｑＮ＞が得られて埋込部１４に送出される。
【００５１】
埋込部１４では、剰余符号をｃ−セキュアＣＲＴ符号に変換する。具体的には、剰余符号の各剰余ｑｉがｑｉ×ｔ個の０とそれに続く（ｐｉ−ｑｉ−１）×ｔ個の１のビット系列である成分符号ｗｉに変換される。次に、埋込部１４は、各成分符号ｗｉを連接して埋込符号ｗ＝ｗ１‖ｗ２‖・・・‖ｗＮ を得る。
【００５２】
埋込部１４は、埋込符号ｗの個々のビットを電子透かしとしてコンテンツ情報に埋込んでいく。具体的な電子透かしの方式には様々のものがあり（非特許文献１参照）、本発明は任意の電子透かし方式を適用可能となっている。
【００５３】
但し、ここでは簡単な例で説明する。コンテンツ情報が濃淡画像データの場合とする。埋込部１４は、埋込符号ｗのビット毎に、画像データから、所定の複数個（Ｍとする）の画素を選択し、その画素値Ｙｊ（ｊ＝１，２，…，Ｍ）をＹｊ’に変更するとする。その際、０を埋め込む場合には、Ｙｊ’＝Ｙｊ＋ｒｊとし、１を埋め込む場合には、Ｙｊ’＝Ｙｊ−ｒｊとする。ｒｊは乱数とする。
【００５４】
埋込符号ｗの埋め込みが完了すると、埋込部１４は、埋込符号ｗの埋め込まれたコンテンツ情報を出力する。
【００５５】
（追跡装置２０Ａ側の処理）
追跡装置２０Ａでは、追跡対象オブジェクトとしてのコンテンツ情報が入力されたとする。検出部２２は、このコンテンツ情報に埋め込まれた埋込符号ｗを検出する。前述した例に合わせてオブジェクトが濃淡画像データの場合を説明する。
【００５６】
検出部２２は、埋込符号ｗのビット毎に、画像データから、所定の複数個（Ｍとする）の画素を選択し、その画素値Ｙｊ（ｊ＝１，２，…，Ｍ）と、埋込みの際に用いた乱数ｒｊとの相互相関を計算する。なお、乱数ｒｊは予め追跡装置２０Ａに与えられている。
【００５７】
検出部２２は、相互相関の計算結果が所定の上限値より大きいとき、０が埋め込まれており、所定の下限値より小さいとき、１が埋め込まれていると決定する。
【００５８】
検出部２２は、さらに、こうして得られた埋込符号ｗを埋込の時と同じ成分のサイズに分割して、Ｎ個の成分符号ｗ１，ｗ２，…，ｗＮを得る。
【００５９】
検出部２２は、図６に示すように、各成分符号ｗｉ毎に、ｗｉのビット列の左側からｔビットずつのブロックを順次検査し、０でない値を含むブロックが初めて現れると、それより左側のブロックの個数をｑｉ(−)とする。同様に、ｗｉのビット列の右側からｔビットずつのブロックを順次検査し、１でない値を含むブロックが初めて現れると、それより右側のブロックの個数をｐｉ−ｑｉ(＋) −１ とする。これにより、各成分符号ｗｉ毎に剰余対ｑｉ(−) ，ｑｉ(＋) を決定する。
【００６０】
しかる後、全ての生成符号ｗ１〜ｗＮに対して剰余対＜ｑ１(−)，ｑ１(＋)＞，・・・，＜ｑＮ(−)，ｑＮ(＋)＞が得られると、検出部２２は、これらの剰余対からなる剰余対符号＜＜ｑ１(−)，ｑ１(＋)＞，・・・，＜ｑＮ(−)，ｑＮ(＋)＞＞を追跡部２３に送出する。
【００６１】
追跡部２３は、剰余対符号の各剰余対＜ｑ１(−)，ｑ１(＋)＞，・・・，＜ｑＮ(−)，ｑＮ(＋)＞に基づいて、（削除）追跡候補となっている各識別番号ｖ毎にｖ≡ｒ(−)ｉ（ｍｏｄ ｐｉ）またはｖ≡ｒ(＋)ｉ（ｍｏｄ ｐｉ）となっているｉの個数を計算し、ｉの個数がしきい値Ｄｔｈ以上のとき、その識別番号ｖを復号部２４に送出する。ここでは、図７に示すように、しきい値Ｄｔｈを大きくとることにより、結託者の識別番号（ＩＤ）を検出し、且つ無関係な人の識別番号（ＩＤ）を除外するようにする。
【００６２】
復号部２４は、追跡部２３から受けた識別番号ｖに対し、鍵格納部２１内の秘密鍵ｓ’に基づいて復号処理を施し、識別番号ｕを復元すると、これを追跡された識別情報ｕとして出力する。なお、復号処理ＩＰ［ｓ’］は、暗号化時の全単射Ｐ［ｓ］の逆写像になっている。
【００６３】
上述したように本実施形態によれば、利用者の識別番号ｕを剰余符号＜ｑ１，・・・，ｑＮ＞に変換し、得られた剰余符号を電子透かし埋込処理によりコンテンツ情報に埋め込む際に、予め秘密鍵ｓに基づいて識別番号ｕに暗号化処理を施すので、フィンガープリンティングスキームにおいて埋め込まれる識別情報ｕを第三者から読出不可とし、利用者のプライバシを保護できる。
【００６４】
例えば秘密鍵ｓを知らない第三者が電子透かしを不正に検出し、暗号化された識別番号ｖを得たとしても、暗号化前の正当な識別番号ｕを得ることができないので、利用者のプライバシを保護することができる。
【００６５】
また、結託攻撃に強い符号化を行って得た符号をオブジェクトに埋込む際に、結託攻撃に強いこの符号の追跡能力を損なうことのない暗号化を行うことで埋め込まれている識別番号を守秘し、その識別番号に対応する利用者のプライバシを保護することができる。
【００６６】
また、本実施形態は、暗号化処理に対応する復号処理を施すための秘密鍵ｓ’に基づいて、識別番号に復号処理を施すので、追跡装置２０Ａからは識別番号をコンテンツ情報から読み出すことができる。
【００６７】
（第２の実施形態）
図８は本発明の第２の実施形態に係る埋込装置の構成を示す模式図であり、図９は同実施形態における追跡装置の構成を示す模式図であり、前述した図面と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。なお、以下の各実施形態も同様にして重複した説明を省略する。また、埋込装置１０Ｂ及び追跡装置２０Ｂは、図２に示したように、オブジェクト追跡システムを構成している。
【００６８】
すなわち、本実施形態は、第１の実施形態の変形例であり、識別番号ｕの暗号化に代えて、剰余符号を暗号化する構成となっている。
【００６９】
これに伴い、埋込装置１０Ｂは、前述した暗号化部１２に代えて、符号化部１３と埋込部１４との間に挿入された暗号化部１２Ｂを備えている。なお、符号化部１３及び埋込部１４は、暗号化部１２Ｂとの配置関係が異なるだけで、前述した機能をもつものである。
【００７０】
ここで、暗号化部（暗号化手段）１２Ｂは、符号化部１３から受けた（暗号化してない識別番号ｕを剰余系で表す）剰余符号＜ｕ１，…，ｕＮ＞が入力されると、鍵格納部１１内の秘密鍵ｓに基づいてこの剰余符号に暗号化処理を施し、この暗号化された剰余符号＜ｑ１，…，ｑＮ＞を埋込部１４に送出する機能をもっている。
【００７１】
なお、この暗号化処理Ｐ［ｓ］は、符号の追跡能力を損なわないように行われる必要がある。例えば暗号化処理は、剰余符号の各剰余を損なわないように剰余符号を暗号化するものとして、剰余の集合Ｑｉ毎の暗号化として表される方式を採用すればよい。つまり、暗号化処理Ｐ［ｓ］は、Ｑｉ毎の全単射な写像Ｐｉ［ｓ］によって表される。各Ｐｉ［ｓ］の実現は、ブロック暗号を採用するか、必要に応じてビット長を変える変形を行うことで可能である。ここでは、暗号化処理として、図１０に示す如き、疑似乱数ｒ０，ｒ１，…に基づいて、剰余ｑ１，…，ｑＮをランダムに置換するランダム置換処理を用いている。このランダム置換では、剰余ｑ１に対応する符号を剰余ｑ１＋ｒ０に対応する符号に置換する。以下、剰余ｑｉ−１に対応する符号が剰余ｑｊに置換されていたとすると、剰余ｑｉに対応する符号は、ｑｊから数えてｒｉ番目の符号に置換される。ただし、すでに置換先になっている符号は飛ばして数えるものとする。これをｉを１ずつ増加させて、ｉ＝Ｎまで繰り返す。
【００７２】
一方、追跡装置２０Ｂは、前述した復号部２４に代えて、検出部２２と追跡部２３との間に挿入された復号部２４Ｂを備えている。なお、検出部２２及び追跡部２３は、復号部２４Ｂとの配置関係が異なるだけで、前述した機能をもつものである。
【００７３】
復号部（復号手段）２４Ｂは、検出部２２から受けた剰余対符号＜＜ｑ１(−)，ｑ１(＋)＞，…，＜ｑＮ(−)，ｑＮ(＋)＞＞に対し、鍵格納部２１内の秘密鍵ｓ’に基づいて復号処理を施し、得られた剰余対符号＜＜ｕ１(−)，ｕ１(＋)＞，…，＜ｕＮ(−)，ｕＮ(＋)＞＞を追跡部２３に送出する機能をもっている。なお、復号処理ＩＰｉ［ｓ’］は、埋込装置１０Ｂによる暗号化処理Ｐｉ［ｓ］の逆置換となっている。
【００７４】
次に、以上のように構成されたオブジェクト追跡システムの動作を説明する。  
（埋込装置１０Ｂ側の処理）
埋込装置１０Ｂでは、識別番号ｕが埋め込まれるオブジェクトとしてのコンテンツ情報と、識別番号の集合Ｕに属する元ｕとしての識別番号ｕとが入力されたとする。
【００７５】
符号化部１３は、識別番号ｕが入力されると、識別番号ｕを符号化して剰余符号＜ｕ１，ｕ２，・・・，ｕＮ＞を暗号化部１２Ｂに送出する。
【００７６】
暗号化部１２Ｂは、剰余符号＜ｕ１，…，ｕＮ＞が入力されると、鍵格納部１１内の秘密鍵ｓに基づいてこの剰余符号に暗号化処理を施し、この暗号化された剰余符号＜ｑ１，…，ｑＮ＞を埋込部１４に送出する。
【００７７】
以下、前述同様に、埋込部１４では、この剰余符号を電子透かし埋め込み処理により各成分符号ｗｉが連接されてなる埋込符号ｗとしてコンテンツ情報に埋め込む。埋込符号ｗの埋込完了後、埋込部１４は、埋込符号ｗの埋め込まれたコンテンツ情報を出力する。
【００７８】
（追跡装置２０Ｂ側の処理）
追跡装置２０Ｂでは、追跡対象オブジェクトとしてのコンテンツ情報が入力されたとする。検出部２２は、前述同様に、このコンテンツ情報に埋め込まれた埋込符号ｗを検出し、埋込符号ｗの全ての生成符号ｗ１〜ｗＮに対して剰余対＜ｑ１(−)，ｑ１(＋)＞，・・・，＜ｑＮ(−)，ｑＮ(＋)＞からなる剰余対符号＜＜ｑ１(−)，ｑ１(＋)＞，・・・，＜ｑＮ(−)，ｑＮ(＋)＞＞を得る。
【００７９】
しかる後、検出部２２は、この剰余対符号＜＜ｑ１(−)，ｑ１(＋)＞，・・・，＜ｑＮ(−)，ｑＮ(＋)＞＞を復号部２４Ｂに送出する。
【００８０】
復号部２４Ｂは、この剰余対符号＜＜ｑ１(−)，ｑ１(＋)＞，…，＜ｑＮ(−)，ｑＮ(＋)＞＞に対し、鍵格納部２１内の秘密鍵ｓ’に基づいて復号処理を施し、得られた剰余対符号＜＜ｕ１(−)，ｕ１(＋)＞，…，＜ｕＮ(−)，ｕＮ(＋)＞＞を追跡部２３に送出する。
【００８１】
以下、前述同様に、追跡部２３は、剰余対符号の各剰余対＜ｕ１(−)，ｕ１(＋)＞，・・・，＜ｕＮ(−)，ｕＮ(＋)＞に基づいて、中国剰余定理により、追跡候補の識別番号ｕを算出する。
【００８２】
続いて、追跡部２３は、追跡候補となっている各識別番号ｕ毎にｕ≡ｒ(−)ｉ（ｍｏｄ ｐｉ）またはｕ≡ｒ(＋)ｉ（ｍｏｄ ｐｉ）となっているｉの個数を計算し、ｉの個数がしきい値Ｄｔｈ以上のとき、その識別番号ｕを出力する。
【００８３】
上述したように本実施形態によれば、利用者の識別番号ｕを剰余符号＜ｑ１，・・・，ｑＮ＞に変換し、得られた剰余符号を電子透かし埋込処理によりコンテンツ情報に埋め込む際に、秘密鍵ｓに基づいて剰余符号＜ｕ１，…，ｕＮ＞に暗号化処理を施すので、フィンガープリンティングスキームにおいて埋め込まれる識別情報ｕを第三者から読出不可とし、利用者のプライバシを保護できる。
【００８４】
例えば秘密鍵ｓを知らない第三者が電子透かしを不正に検出し、暗号化された識別番号ｖを得たとしても、暗号化前の正当な剰余符号＜ｕ１，…，ｕＮ＞を得ることができないので、正当な識別情報を得ることができず、利用者のプライバシを保護することができる。
【００８５】
また、結託攻撃に強い符号化を行って得た符号をオブジェクトに埋込む際に、結託攻撃に強いこの符号の追跡能力を損なうことのない暗号化を行うことで埋め込まれている識別番号を守秘し、その識別番号に対応する利用者のプライバシを保護することができる。
【００８６】
また、本実施形態は、暗号化処理に対応する復号処理を施すための秘密鍵ｓ’に基づいて、剰余符号に復号処理を施すので、追跡装置２０Ｂからは識別番号をコンテンツ情報から読み出すことができる。
【００８７】
以上は第１の実施形態と類似した効果であるが、次に、本実施形態に特有の効果について述べる。本実施形態によれば、特に、ランダム誤り耐性を高めることができる。これは、暗号化によるＱｉのランダム置換の結果、弱ＩＤ（弱識別番号）が存在しにくくなるため、符号に対するランダム誤り耐性を高めることができるからである。ここで、弱ＩＤとは、ｃ−セキュアＣＲＴ符号において、符号にランダム誤りが加わった場合に、誤って追跡される確率が高い識別番号のことである。
【００８８】
ｃ−セキュアＣＲＴ符号では、小さな値の識別番号が弱ＩＤとなる傾向にある。小さな値の識別番号は、小さな値の整数の組で表現されるが、ランダム誤りが加わったとき、小さな整数の組を多く含む符号が検出される可能性が高いためである。ランダム置換を導入することで、小さな値の識別番号は、小さな値の整数の組で表現される確率が小さくなり、その結果、符号にランダム誤りが加わっても誤追跡の確率が小さくなる。
【００８９】
（第３の実施形態）
図１１は本発明の第３の実施形態に係る埋込装置の構成を示す模式図であり、図１２は同実施形態における追跡装置の構成を示す模式図である。また、埋込装置１０Ｃ及び追跡装置２０Ｃは、図２に示したように、オブジェクト追跡システムを構成している。
【００９０】
すなわち、本実施形態は、第１の実施形態の変形例であり、識別番号ｕの暗号化に代えて、電子透かしの処理に秘密鍵ｓを用いる構成となっている。
【００９１】
これに伴い、埋込装置１０Ｃは、暗号化部１２を省略し、鍵格納部１１を読出可能な埋込部１４Ｃを備えている。なお、符号化部１３は、前述した機能をもつものである。
【００９２】
ここで、埋込部１４Ｃは、前述した埋込部１４の機能において、乱数列ｒｊを生成する際に、秘密鍵ｓに依存した生成を行う。この生成は、異なる鍵ｓから生成された乱数列ｒｊの間の相互相関が小さいものが良い。例えば、線形フィードバックレジスタを用いた乱数生成を行い、秘密鍵ｓをその初期値とすればよい。また、埋込部１４Ｃは、埋込符号ｗの埋め込みの際に、各成分符号ｗ１，…，ｗＮ内で１と０とが混合しないように埋込符号ｗをコンテンツ情報に埋め込む。
【００９３】
一方、追跡装置２０Ｃは、暗号化部２３を省略し、鍵格納部２１を読出可能な検出部２２Ｃを備えている。なお、追跡部２４は、前述した機能をもつものである。
【００９４】
ここで、検出部２２Ｃは、前述した検出部２２の機能において、乱数列ｒｊを生成する際に、秘密鍵ｓ’に依存した生成を行う。この生成は、埋込部１４Ｃにおける生成と同様の構成である。
【００９５】
以上のような構成によれば、利用者の識別番号ｕを剰余系で表現する剰余符号＜ｕ１，…ｕＮ＞を、１の列及び０の列を含む埋込符号ｗとしてコンテンツ情報に埋め込む際に、秘密鍵ｓに基づいて生成した疑似乱数ｒｊを埋込符号ｗの１，０に応じてコンテンツ情報に加算又は減算することにより、埋込符号ｗをコンテンツ情報に埋め込むので、フィンガープリンティングスキームにおいて埋め込まれる識別情報ｕを第三者から読出不可とし、利用者のプライバシを保護できる。
【００９６】
また、追跡装置２０Ｃは、秘密鍵に基づいて疑似乱数ｒｊを生成し、前述した相互相関により、コンテンツ情報に埋め込まれた埋込符号の１，０を決定するので、問題なく、埋込符号をコンテンツ情報から読み出すことができる。また、決定された埋込符号ｗから得られる剰余対符号＜＜ｕ１(−)，ｕ１(＋)＞，…，＜ｕＮ(−)，ｕＮ(＋)＞＞の各剰余対に基づいて識別番号ｕを復元できるので、第三者からは読出不可でも、追跡装置２０Ｃからは識別情報ｕを読み出すことができる。
【００９７】
なお、本実施形態は、第１又は第２の実施形態と組合せるように変形してもよい。このような変形例とすることにより、組合せた各実施形態の作用効果を同時に得ることができる。また、この変形例は、以下の各実施形態にも適用することができる。
【００９８】
（第４の実施形態）
図１３は本発明の第４の実施形態に係る埋込・追跡装置の構成を示す模式図である。  
本実施形態は、第１の実施形態の変形例であり、別々の埋込装置１０Ａと追跡装置２０Ａに代えて、両者を同一装置で実現した埋込・追跡装置３０Ａを備えている。これに伴い、前述した鍵格納部１１，２１に代えて、鍵格納部３１が設けられている。
【００９９】
ここで、鍵格納部３１は、暗号化部１２及び復号部２４から読出可能となっており、秘密鍵ｓ，ｓ’が格納されるメモリである。なお、秘密鍵ｓ，ｓ’は、埋込装置１０Ａ内で生成されたものでもよく、外部から入力又は受信されたものでもよい。
【０１００】
以上のような構成によれば、第１の実施形態の効果に加え、秘密鍵ｓ，ｓ’を他者の手に渡すことなく装置３０Ａ内で共有することができる。
【０１０１】
なお、本実施形態の鍵格納部３１は、次のように変形しても良い。すなわち、鍵格納部３１は、秘密鍵ｓ，ｓ’が暗号化された状態で格納されており、暗号化部１２又は復号部２４から読出要求を受けると、当該秘密鍵ｓ，ｓ’を復号して読出要求元に出力する構成に変形してもよい。この変形例の場合、秘密鍵の安全性を向上させることができる。なお、この変形例は、以下の各実施形態にも適用可能である。
【０１０２】
（第５の実施形態）
図１４は本発明の第５の実施形態に係る埋込・追跡装置の構成を示す模式図である。  
本実施形態は、第２の実施形態の変形例であり、別々の埋込装置１０Ｂと追跡装置２０Ｂに代えて、両者を同一装置で実現した埋込・追跡装置３０Ｂを備えている。これに伴い、前述した鍵格納部１１，２１に代えて、前述した鍵格納部３１が設けられている。
【０１０３】
以上のような構成としても、第２の実施形態の効果に加え、第４の実施形態の効果を得ることができる。
【０１０４】
（第６の実施形態）
図１５は本発明の第６の実施形態に係る埋込・追跡装置の構成を示す模式図である。  
本実施形態は、第３の実施形態の変形例であり、別々の埋込装置１０Ｃと追跡装置２０Ｃに代えて、両者を同一装置で実現した埋込・追跡装置３０Ｃを備えている。これに伴い、前述した鍵格納部１１，２１に代えて、前述した鍵格納部３１が設けられている。
【０１０５】
以上のような構成としても、第３の実施形態の効果に加え、第４の実施形態の効果を得ることができる。
【０１０６】
なお、上記各実施形態に記載した手法は、ｃ−セキュアＣＲＴ符号として、有理整数環上で構成された例を示したが、多項式環上で構成された例や、一般には、デデキント環上で構成された例においても、同様の効果を得ることができる。
【０１０７】
また、上記各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１０８】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１０９】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【０１１０】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１１１】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１１２】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１１３】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１１４】
なお、本願発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１１５】
【図１】本発明の各実施形態を分類して説明するための模式図である。
【図２】本発明の第１の実施形態に係る埋込装置及び追跡装置を備えたオブジェクト追跡システムの構成を示す模式図である。
【図３】同実施形態における埋込装置の構成を示す模式図である。
【図４】同実施形態における追跡装置の構成を示す模式図である。
【図５】同実施形態における埋込部の構成を説明するための模式図である。
【図６】同実施形態における検出部の動作を説明するための模式図である。
【図７】同実施形態における追跡部の動作を説明するための模式図である。
【図８】本発明の第２の実施形態に係る埋込装置の構成を示す模式図である。
【図９】同実施形態における追跡装置の構成を示す模式図である。
【図１０】同実施形態における暗号化部の構成を説明するための模式図である。
【図１１】本発明の第３の実施形態に係る埋込装置の構成を示す模式図である。
【図１２】同実施形態における追跡装置の構成を示す模式図である。
【図１３】本発明の第４の実施形態に係る埋込・追跡装置の構成を示す模式図である。
【図１４】本発明の第４の実施形態に係る埋込・追跡装置の構成を示す模式図である。
【図１５】本発明の第４の実施形態に係る埋込・追跡装置の構成を示す模式図である。
【符号の説明】
【０１１６】
１０Ａ〜１０Ｃ…埋込装置、１１，２１，３１…鍵格納部、１２，１２Ｂ…暗号化部、１３…符号化部、１４，１４ｃ…埋込部、２０Ａ〜２０Ｃ…追跡装置、２２，２２ｃ…検出部、２３…追跡部、２４，２４Ｂ…復号部、ｓ，ｓ’…秘密鍵（鍵情報）、ｕ，ｖ…識別番号、ｐｉ…法、ｑｉ，ｕｉ…剰余、ｗｉ…生成符号、ｗ…埋込符号、ｑｉ(−)，ｑｉ(＋)…剰余対。
【図１】
2005165231.tif 000004
【図２】
2005165231.tif 000005
【図３】
2005165231.tif 000006
【図４】
2005165231.tif 000007
【図５】
2005165231.tif 000008
【図６】
2005165231.tif 000009
【図７】
2005165231.tif 000010
【図８】
2005165231.tif 000011
【図９】
2005165231.tif 000012
【図１０】
2005165231.tif 000013
【図１１】
2005165231.tif 000014
【図１２】
2005165231.tif 000015
【図１３】
2005165231.tif 000016
【図１４】
2005165231.tif 000017
【図１５】
2005165231.tif 000018