(57)【特許請求の範囲】
【請求項１】
デジタルデータの非同期化フィンガープリンティングを行うコンピュータによって実施される方法であって、
フィンガープリントを埋め込む、前記デジタルデータ内の埋め込み領域を選択するステップと、
前記デジタルデータの複数のコピーを互いに非同期化させる、前記デジタルデータ内の非同期化領域を選択するステップと、
前記非同期化領域の各々についてランダム非同期化を実行し、前記非同期化領域の幅がコピーと前記デジタルデータとの間で変化するように、前記非同期化領域の各々の幅をランダムにばらつかせるステップと、
前記埋め込み領域の各々にフィンガープリントを埋め込んで、非同期化フィンガープリンティングされたデジタルデータを生成するステップと
を備えたことを特徴とする方法。
【請求項２】
前記埋め込み領域と非同期化領域とをランダムに選択するステップをさらに備えたことを特徴とする請求項１に記載のコンピュータによって実施される方法。
【請求項３】
マスター鍵とハッシュ関数とを使用して前記埋め込み領域をランダムに選択するステップをさらに備えたことを特徴とする請求項１に記載のコンピュータによって実施される方法。
【請求項４】
前記埋め込み領域の各々についてハッシュ値を求め、および記憶するステップをさらに備えたことを特徴とする請求項３に記載のコンピュータによって実施される方法。
【請求項５】
マスター鍵を使用して前記非同期化領域をランダムに選択するステップをさらに備えたことを特徴とする請求項１に記載のコンピュータによって実施される方法。
【請求項６】
前記非同期化領域の各々についてランダム非同期化を実行するステップは、マスター鍵を使用して、前記非同期化領域の各々の幅をランダムに計算するステップをさらに備えたことを特徴とする請求項１に記載のコンピュータによって実施される方法。
【請求項７】
前記デジタルデータの複数のコピーを生成し、および各コピーをフィンガープリンティングするステップをさらに備えたことを特徴とする請求項１に記載のコンピュータによって実施される方法。
【請求項８】
前記埋め込み領域の各々に一意の秘密鍵を埋め込むステップをさらに備えたことを特徴とする請求項１に記載のコンピュータによって実施される方法。
【請求項９】
請求項１に記載のコンピュータによって実施される方法を実行するための、コンピュータで実行可能な命令を有することを特徴とするコンピュータ読取り可能な媒体。
【請求項１０】
デジタルマルチメディアデータの非同期化フィンガープリンティングを行う、コンピュータで実行可能な命令を有するコンピュータ読取り可能な媒体であって、前記命令は、
前記デジタルマルチメディアの各コピー内で１又は複数の埋め込み領域をランダムに選択するステップと、
前記デジタルマルチメディアの各コピー内で１又は複数の非同期化領域をランダムに選択するステップと、
前記選択された非同期化領域の各々についてランダムな幅を計算することによって、前記選択された非同期化領域各々の幅が前記複数のコピー間でばらつくようにするステップと、
前記選択された埋め込み領域の各々に情報を埋め込んで、前記デジタルマルチメディアデータの非同期化フィンガープリンティングされたコピーを生成するステップと
を備えたことを特徴とするコンピュータ読取り可能な記録媒体。
【請求項１１】
埋め込み領域をランダムに選択するステップは、擬似ランダム演算子とマスター鍵とを使用するステップをさらに含むことを特徴とする請求項１０に記載のコンピュータ読取り可能な記録媒体。
【請求項１２】
前記擬似ランダム演算子はハッシュ関数であることを特徴とする請求項１１に記載のコンピュータ読取り可能な記録媒体。
【請求項１３】
非同期化領域をランダムに選択するステップは、マスター鍵を使用するステップを含むことを特徴とする請求項１０に記載のコンピュータ読取り可能な記録媒体。
【請求項１４】
前記非同期化領域の各々についてランダムな幅を計算するステップは、マスター鍵を使用してランダムな幅を計算し、これに従って前記幅を変更するステップを含むことを特徴とする請求項１０に記載のコンピュータ読取り可能な記録媒体。
【請求項１５】
前記埋め込み領域の各々に情報を埋め込むステップは、一意のコピー情報と一意の秘密鍵を埋め込むステップを含むことを特徴とする請求項１０に記載のコンピュータ読取り可能な記録媒体。
【請求項１６】
前記命令は、前記複数のコピーの各々を特定のエンティティに関連付けるように前記一意のコピー情報および対応する前記エンティティのリストを生成するステップをさらに備えたことを特徴とする請求項１５に記載のコンピュータ読取り可能な記録媒体。
【請求項１７】
前記命令は、前記一意のコピー情報を前記一意の秘密鍵に関連付けるステップをさらに備えたことを特徴とする請求項１５に記載のコンピュータ読取り可能な記録媒体。
【請求項１８】
前記一意の情報は、前記複数のコピーのうちの特定の１つの番号であることを特徴とする請求項１７に記載のコンピュータ読取り可能な記録媒体。
【請求項１９】
前記命令は、前記デジタルマルチメディアデータの違法コピーから前記一意のコピー情報を抽出するステップと、
前記一意のコピー情報から、前記違法コピーの製造に関与したエンティティの身元を割り出すステップと
をさらに備えたことを特徴とする請求項１６に記載のコンピュータ読取り可能な記録媒体。
【請求項２０】
オリジナルのデジタルマルチメディア製品のコピーの非同期化フィンガープリンティングを行う非同期化フィンガープリンティングシステムであって、
前記非同期化領域の幅が前記オリジナルのデジタルマルチメディア製品のコピー間で異なるように前記非同期化領域の幅をランダムに選択して適用するランダム非同期化プロセスと複数の秘密鍵とを用いて、前記製品の各コピーにフィンガープリントを埋め込む埋め込みモジュールと、
前記複数の秘密鍵を用いて前記埋め込まれたフィンガープリントを検出し、前記フィンガープリントから協力者情報を抽出して、前記デジタルマルチメディア製品の違法コピーの製造に協力した人物を識別する検出および抽出モジュールと
を備えたことを特徴とする非同期化フィンガープリンティングシステム。
【請求項２１】
前記埋め込みモジュールは、マスター鍵を使用して前記製品の各コピーにおいて、フィンガープリントを埋め込む埋め込み領域をランダムに選択する埋め込み領域セレクタを含み、前記検出および抽出モジュールが前記マスター鍵とハッシュ関数を使用して埋め込み領域を検出することを特徴とする請求項２０に記載の非同期化フィンガープリンティングシステム。
【請求項２２】
前記埋め込みモジュールは、マスター鍵を使用して前記オリジナルマルチメディア製品のコピーから前記非同期化領域を選択し、前記オリジナルマルチメディア製品のコピーの非同期化領域に幅を適用する非同期化領域セレクタを含むことを特徴とする請求項２０に記載の非同期化フィンガープリンティングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、マルチメディアフィンガープリンティングに関し、より詳細には、デジタルマルチメディア製品の違法コピー作成の協力者を識別するための安全なフィンガープリンティングのシステムおよび方法に関する。
【背景技術】
【０００２】
デジタルマルチメディアデータ製品（映画や録音など）の違法コピーの問題が広まっている。この問題は、コピープロテクトの技術的進歩や、知的財産権の強化に向けての努力にもかかわらず、拡大する一方のようである。こうした知的財産権の侵害は、権利所有者に多大な経済的損害を与え得る。
【０００３】
この違法コピーの拡大傾向は、デジタルマルチメディアデータを記憶および配布するために、デジタル媒体およびデジタル機器の利用が広まっていることと強く関係していると見られる。インターネット技術とデジタル記憶データが大きく発展したことにより、オリジナルと変わりない高品質コピーを簡単かつ安価に製造することが可能になっているのである。さらに、そのコピーをインターネットコミュニティの全体で利用することが可能である。このプロセスは、ピアツーピア（Ｐ２Ｐ）ネットワークを利用することでさらに簡便になっている。利用できるコピー装置が増え、デジタルデータ用の情報量が増える（ｉｎｃｒｅａｓｅｄ  ｂａｎｄｗｉｄｔｈ）につれて、デジタルマルチメディアデータ（イメージ、ビデオ、音楽など）の違法な再配布を抑止することが必要であり、重要な懸案となってきた。
【０００４】
違法コピーを抑止する１つの方法は、著作権侵害行為によって逮捕されるリスクを高めることである。そのリスクを高める方法の１つが、各コピーに一意かつ不可視のマークを記憶させる（言い換えると、デジタル媒体信号の知覚内容の中に安全かつ確実にマークを埋め込む）ことである。このようにすると、違法コピーがどこかで見つかったとき、オリジナルの所有者を割り出し、法的措置をとることができる。この種の実施手法をフィンガープリンティングと呼ぶ（あるコミュニティでは、捜査のための「マーク埋め込み」としても知られる）。
【０００５】
フィンガープリンティングの考え方は、各コピーに一意のマーキングを施すというものである。これにより、各コピーは、他のすべてのコピーとビット単位で異なり、それにも拘らず知覚的にはほぼ同一とすることができる。このようにすれば、すべての合法コピーを区別することが可能である。このマーキングにより、コピーを識別することができ、それにより何らかの方法でそのフィンガープリント（マーク）とユーザの識別情報がリンクしていれば、そのユーザも識別することができる。たとえば、フィンガープリンティングされたコピーが、身元を明らかにした人にのみ配布される場合、違法コピーが見つかったときに、そのコピー元になった合法コピーの所有者を識別できる場合がある。
【０００６】
一例として、映画を収録したＤＶＤ（デジタルビデオディスク）の所有者が販売目的でその映画のコピーを作成すると仮定する。コピー各々にはフィンガープリンティングを施す。所有者は、各ユーザのコピーに、フィンガープリントを個別に、かつ一意にマーキングし、各フィンガープリントを購入者に一意に関連付けた後で、コピーをユーザに販売するだけである。後日、何人かの購入者（海賊業者）が共謀して、違法コピーを作成し、再配布したとする（この場合、海賊業者らを共謀攻撃者とも呼ぶ）。映画の所有者は、その違法コピーを解析して、どの購入者が違法コピー作成に関与したかを突き止めるようすることができる。
【０００７】
フィンガープリンティング技法には、ウォーターマーキング（「マーク埋め込み」とも呼ぶ）の手法を用いてデジタル製品の各コピーにフィンガープリントを挿入するステップが含まれる。ウォーターマーキング方式は、安全鍵（ｓｅｃｕｒｅ  ｋｅｙ）でのみ復元可能な方法で、知覚内容に知覚できないフィンガープリントを埋め込む方式である。この種の方式は、コンテンツの保護に関する従来のＤＲＭ（デジタル著作権管理）技法とまったく異なることに留意されたい。（違法コピーまたは違法記録を防ぐ保護目的の場合の）電子透かしと、（漏洩を追跡する捜査目的の場合の）フィンガープリントとでは、重要な違いが２つある。第１に、ウォーターマーキングでは、隠しメッセージ（マーク）がすべての購入者に対して同一であり（また、多くの場合、このマークはコンテンツ所有者の身元を表すものであり）、フィンガープリンティングでは、購入者の身元によってマークが異なる。第２に、購入者の共謀は、ウォーターマーキングにおける課題ではない（１つのコンテンツについてマーキングされたコピーがすべての購入者に対して同一）。しかし、フィンガープリンティングでは、マークがすべての購入者ごとに異なるため、共謀する購入者が各自のコピーを比較し、いくつかのマーキングビットを探し当てて削除しようとする行為が意味を持つ。したがって、フィンガープリンティングされたデジタル製品に対する共謀攻撃では、不誠実なユーザのグループが、各自のコピーの異なる部分を寄せ集めて身元を隠した違法コピーを作成するという共謀行為を行う。この攻撃は、隠して埋め込まれたフィンガープリントを除去しようとする行為である。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
現在のフィンガープリンティング技法における１つの問題は、識別できる協力者の数が限られていることである。たとえば、現在ある従来型のフィンガープリンティング技法には、４〜８人の協力者しか識別できないものがある。より新しい、フィンガープリンティング技法には、フィンガープリンティング符号を用いて、従来型のフィンガープリンティング技法より１桁良好な検出が可能なものがある。しかし、多くの場合、違法コピーの製造には大勢の協力者が関与しているのである。つまり、現在あるフィンガープリンティング技法では、１００人を超える協力者を正確に検出し、および識別することはできない。これは、フィンガープリンティングの抑止効果に対する厳しい制限である。協力者らは、大勢のコピー所有者と手を組みさえすれば検出を逃れられることを知っているからである。
【０００９】
現在のフィンガープリンティング技法における別の問題は、予測攻撃（ｅｓｔｉｍａｔｉｏｎ  ａｔｔａｃｋ）を受けやすいことである。攻撃者がシーンのすべてのフレームを取得して、すべてのフレームの平均を算出し、それによりマーキングされていないオリジナルコンテンツの予測を形成した場合、予測攻撃が行われる。また、別の技法でも、媒体信号に存在する固有の冗長性から各クライアントのフィンガープリントを予測できる。これにより、すべてのフィンガープリントが大幅に機能が低下させられ、または除去される傾向にある。
【００１０】
したがって、現在あるフィンガープリンティング技法におけるより少なくとも１桁多い人数の協力者を正確に識別できるフィンガープリンティングのシステムおよび方法が求められている。同時に、（暗号技法として）安全で、予測攻撃に対する耐性を有するフィンガープリンティングのシステムおよび方法が求められている。
【課題を解決するための手段】
【００１１】
本願明細書において開示する発明には、攻撃に対する耐性があり、フィンガープリンティング符号を用いずに多数の協力者を識別できる非同期化フィンガープリンティングの方法およびシステムが含まれる。特に、本願明細書において開示する非同期化フィンガープリンティングの方法およびシステムは、現在あるフィンガープリンティング技法で識別できる人数より１桁を超える人数の協力者を識別できる。
【００１２】
非同期フィンガープリンティングのシステムおよび方法は、どのようなタイプのマルチメディアアプリケーションにでも使用でき、特にオーディオおよびビデオのアプリケーションに使用できる。一般に、各ユーザには異なる鍵を割り当てられる。埋め込み機能には、選択した領域に擬似ランダム変換を適用することが含まれる。擬似ランダム変換の鍵は、ユーザごとに異なる。これらの領域の選択は、安全なマルチメディアハッシュ関数によって行う。検出および抽出機能には、ユーザの鍵空間の総当たり検索が含まれる。それらの鍵の１つに十分な「確実性」があれば、そのユーザが違法コピーの製造に関与していることが明らかになる。
【００１３】
非同期化フィンガープリンティング方法には、非同期化埋め込みプロセスと検出および抽出プロセスが含まれる。非同期化埋め込みプロセスには、オリジナルのマルチメディア製品のコピーを作成するステップと（各コピーはオリジナルを擬似ランダム非同期化したもの）、非同期化領域およびフィンガープリントを埋め込む埋め込み領域の両方をランダムに選択するステップとが含まれる。マークを実際に埋め込む前に擬似ランダムな「意図的」非同期化を行うと、共謀攻撃者らが、マーキングされていないオリジナル信号の良好な予測を（たとえば、平均算出型の攻撃などによって）求めることが困難になる。なぜなら、共謀攻撃者らが、共謀するために各自のコピーを互いに「位置合せ」しなければならず、協力者の数が増えるほど（総計算能力に限りがあると仮定して）予測が困難になるためである。ランダム非同期化プロセスには、各非同期化領域の幅を、異なるクライアントのコピーの間でばらつくように、擬似ランダムに決定された量にマッピングすることが含まれる。ランダム非同期化プロセスにはマスター鍵を使用する。同様に、埋め込み領域のランダム選択にはマスター鍵とハッシュ関数を使用する。次にその埋め込み領域に、一意のコピー情報と秘密鍵を埋め込む。一般に、埋め込み領域と非同期化領域とは同じでなくても、一部が重なっていてもよい。
【００１４】
検出および抽出プロセスには、オリジナルのデジタルマルチメディア製品の違法コピーを取得するステップが含まれる。その違法コピーについてハッシュ値を計算し、それらのハッシュ値とオリジナルコンテンツの埋め込み領域のハッシュ値とを比較して、違法コピーの埋め込み領域を決定する。本質的には、強固な知覚の（ｒｏｂｕｓｔ  ｐｅｒｃｅｐｔｕａｌ）ハッシュ関数を使用して、受け手側の埋め込み場所に「照準を合わせる」。次に、埋め込み領域の各々に対し、各１つの秘密鍵を使用して、電子透かしの検出を行う。識別情報を検出し、協力者情報を抽出して、協力者のリストを作成する。これらの協力者が、違法コピーの製造に協力した人物である。
【００１５】
以下の説明と、本発明の態様を表す添付の図面とを参照することにより、本発明を深く理解することができる。以下の本発明の詳細な説明と、本発明の原理を例示的に表した添付の図面とを併せて参照することにより、他の特徴や利点も明らかになる。
【００１６】
各図面間で類似している参照符号は、全体を通して、対応している部分を表す。
【発明を実施するための最良の形態】
【００１７】
以下の本発明の説明では、添付の図面を参照する。添付の図面は説明の一部であり、本発明の具体的な実施例を図示している。本発明の範囲を逸脱することなく、他の実施形態を利用することや、構造の変更を行うことが可能であることを理解されたい。
【００１８】
Ｉ．はじめに
デジタルマルチメディアデータの違法コピーの作成および配布が広く問題になっており、知的財産の所有者の利益を損なう結果になっている。捕捉されるリスクを高める方法の１つは、デジタルマルチメディアデータを含んだ製品のコピーと購入者とを一意に特定するフィンガープリンティング技法を利用することである。但し、現存するフィンガープリンティング技法は、識別可能な協力者の数に厳しい制限がある。また、それらの技法は、通常、フィンガープリンティングの符号を用いるが、フィンガープリンティング符号は実装しにくい場合がある。さらに、現在のフィンガープリンティング技法は予測攻撃を受けやすい。この攻撃を受けると、フィンガープリントは、ほぼ除去される。
【００１９】
本願明細書で説明する非同期化フィンガープリンティングの方法およびシステムは、現存する技法より少なくとも１桁多い人数の協力者を識別できる。さらに、この方法およびシステムは、フィンガープリンティングの符号を用いることなく、それを実行できる。非同期化フィンガープリンティングの方法およびシステムでも符号を用いることができるが、必須ではない。さらに、非同期化フィンガープリンティングの方法およびシステムは、ランダムに選択した非同期化領域の幅をランダムにばらつかせる新規なランダム非同期化プロセスを用いることにより、予測攻撃に対する耐性を備えている。そして、デジタルマルチメディアデータの各コピーの埋め込み領域にフィンガープリントを埋め込む。埋め込み領域は、非同期化領域と同じであっても、異なっていてもよい。識別可能な協力者数を増やしたことと、この技法に予測攻撃に対する耐性を持たせたことにより、非同期化フィンガープリンティングの方法およびシステムは、違法コピー作成に対する強力な抑止力として機能する。
【００２０】
ＩＩ．全体の概要
図１は、本願明細書で開示した非同期化フィンガープリンティングのシステムおよび方法の例示的な実施形態を示すブロック図である。図１は、非同期化フィンガープリンティングのシステムおよび方法を実装および使用するいくつかのやり方の１つを示しているに過ぎないことに留意されたい。
【００２１】
非同期化フィンガープリンティングのシステムおよび方法は、（イメージ、ビデオ、またはオーディオなどの）デジタルマルチメディアデータに対して動作する。非同期化フィンガープリンティングのシステムおよび方法は、概ね２つの部分に分かれる。第１の部分は、非同期化フィンガープリンティングのシステムおよび方法を用いて、（映画または録音などの）デジタルマルチメディア製品の各コピーの中に一意情報を埋め込むステップである。この一意情報を一覧表にして、各コピーと特定人物（コピーの購入者など）とを関連付ける。第２の部分は、製品の違法コピーを解析して（たとえば、科学捜査など）、どの人物が違法コピーの製造に協力したかを突き止めるステップを含む。
【００２２】
図１に示す例示的な実施形態では、デジタルマルチメディア製品は映画である。より具体的には、図１に示すように、非同期化フィンガープリンティングのシステムおよび方法１００を用いて、映画１０５のマスターコピーを処理する。以下に詳述するように、非同期化フィンガープリンティングのシステムおよび方法１００では、マスター鍵１１０と複数の秘密鍵１１５を使用する。この例示的な実施形態では、秘密鍵の数をＮとする。非同期化フィンガープリンティングのシステムおよび方法１００の処理後の出力は、映画１０５のＮ個のコピーである。具体的には、非同期化フィンガープリンティングのシステムおよび方法１００は、映画のフィンガープリンティングされたコピー（１）１２０、映画のフィンガープリンティングされたコピー（２）１２５、映画のフィンガープリンティングされたコピー（３）１３０、同様に、映画のフィンガープリンティングされたコピー（Ｎ）１３５を生成する。映画のフィンガープリンティングされたコピーの各々は、対応する、秘密鍵１１５のいずれかを有する。映画のフィンガープリンティングされたコピーに関連付けられた秘密鍵の保有者は、その鍵を使用して、映画コピーの中に格納された一意情報にアクセスできる。
【００２３】
次に、映画のフィンガープリンティングされたコピーの各々を何らかの方法で配布する。通常、配布には、販売が含まれる。しかし、販売以外の配布もありうる。確認、評価、その他、販売以外の目的でのクライアントへの配布などである。図１に示した例示的な実施形態では、映画のフィンガープリンティングされたコピーを誰かが購入するというかたちで配布が行われる。具体的には、第１の購入者（Ｂ（１））１４０が、映画のフィンガープリンティングされたコピー（１）１２０を購入し、第２の購入者（Ｂ（２））１４５が、映画のフィンガープリンティングされたコピー（２）１２５を購入し、第３の購入者（Ｂ（３））１５０が、映画のフィンガープリンティングされたコピー（３）１３０を購入し、同様に続いて、第Ｎの購入者（Ｂ（Ｎ））１５５が、映画のフィンガープリンティングされたコピー（Ｎ）１３５を購入する。各購入者および各購入者が購入した映画のコピーの番号の記録を保管する。
【００２４】
映画の違法コピー１６０は、通常、図１に示すように、複数の購入者が協力して作成する。しかし、協力した購入者の身元は、この時点では不明である。非同期化フィンガープリンティングのシステムおよび方法１００を用いて、映画の違法コピー１６０を処理し、協力者を識別する。
【００２５】
秘密鍵１１５各々を試すことによって、非同期化フィンガープリンティングのシステムおよび方法１００により、映画の違法コピー１６０を処理する。ある秘密鍵１１５によって、映画の違法コピー１６０に埋め込まれている情報の一部が開いたら、次にその鍵に関連付けられている購入者が、映画の違法コピー１６０の作成に関与した協力者だということになる。図１に示す例示的な実施形態では、購入者Ｂ（６）１６５、Ｂ（７）１７０、およびＢ（９）１７５が、映画の違法コピー１６０の作成に関与したとして識別されている。次に他の人物が違法コピーの作成に関与するのを抑止するために、しかるべき法的措置をとる（たとえば、犯罪者らを拘束する１８０）ことができる。
【００２６】
非同期化フィンガープリンティングのシステムおよび方法１００は、例示した３人をはるかに上回る数の協力者を識別できることに留意されたい。そもそも、非常に多くの協力者を識別できることが、非同期化フィンガープリンティングのシステムおよび方法１００の強みの１つである。しかしこの例示的な実施形態では、説明を簡潔にするために、３人だけを示したのである。
【００２７】
ＩＩＩ．動作の概要
図１に示した非同期化フィンガープリンティングのシステムおよび方法１００の動作について説明する。図２は、図１に示した非同期化フィンガープリンティングシステムの全般的な動作を示す概略フロー図である。非同期化フィンガープリンティングの方法では、まず、オリジナルのデジタルマルチメディア製品を取得し（ステップ２００）、コピーを作成する（ステップ２１０）。各コピーに、異なる一意の秘密鍵を割り当てると共に、その鍵に一意の情報を関連付ける（ステップ２２０）。この一意の情報とは、たとえば、各コピーの番号である。
【００２８】
次に秘密鍵と関連付けられた一意情報とを、非同期化埋め込みプロセスを用いて埋め込むことによって、各コピーにフィンガープリンティングを行う（ステップ２３０）。次に非同期化フィンガープリンティングされたコピーを配布する（ステップ２４０）。たとえば、コピーを一般の人々に販売したり、またはレンタルできるようにしたりする。
【００２９】
一部のコピー保有者が、入手後に、違法コピーの製造に協力する場合がある。たとえば、複数の協力者のコピーを少しずつ使用して、単一の違法コピーを製造する場合がある。このような場合は、多数の協力者が関与するのが普通である。つまり、協力者の数が多いほど、個々の協力者を識別しにくくなるという考え方である。
【００３０】
違法コピーを取得し（ステップ２５０）、非同期化フィンガープリンティング方法で処理する。この方法で、違法コピーに埋め込まれたフィンガープリントを検出および抽出する（ステップ２６０）。埋め込まれたフィンガープリントを、非同期化フィンガープリンティングの検出および抽出プロセスと秘密鍵を使用して、検出および抽出する。非同期化フィンガープリンティングの検出および抽出プロセスで、違法コピーの作成に関係した協力者を特定および識別する。
【００３１】
ＩＶ．動作の詳細
図３は、図２に示した非同期化フィンガープリンティング方法の非同期化埋め込みプロセスの動作を示す概略フロー図である。一般に、非同期化埋め込みプロセスでは、２つの機能を実行する。第１に、マルチメディア製品のコピーのランダムな埋め込み位置に一意情報を埋め込む。第２に、（マスター鍵を使用して）異なるコピーを、それぞれ異なる非同期化位置で、互いにランダムに非同期化する。一実施形態では、埋め込み領域と非同期化領域が同じ位置にある。あるいは、埋め込み領域を、非同期化領域と同じ位置にすることができる。
【００３２】
図３を参照すると、非同期化埋め込みプロセスでは、まず、マルチメディア製品のコピーを取得する（ステップ３００）。次に、マルチメディア製品のコピーの埋め込み領域と非同期化領域をランダムに選択する（ステップ３１０）。埋め込み領域は、マルチメディア製品のコピーの、フィンガープリントを埋め込む位置である。非同期化領域は、ランダムな幅変更を適用する位置である。このランダムな幅変更は、高い確率でユーザごとに異なる。マルチメディア製品が映画の場合、埋め込み領域は、単一のフレームまたはシーンではないことが好ましい。あるいは、いくつかのフレームを含む単一シーンを埋め込み領域にすることもできる。マルチメディア製品が録音の場合は、録音の一部を含むオーディオクリップまたはオーディオフラグメントを埋め込み領域にすることができる。同様の考え方が非同期化領域にも当てはまる。通常、フィンガープリントが埋め込まれるオーディオクリップは、録音全体よりもかなり短い。
【００３３】
埋め込み領域と非同期化領域の数は、ランダムに選択されるようにし、またはユーザが選択することができる。さらに、媒体内容の知覚特性も、この選択に影響する。通常は、知覚と安全上の理由から、低アクティビティの領域（つまり、エントロピーが低い領域）にマークを埋め込むのは好ましくない。このことも、必然的に、選択される領域の数の選択に影響する。（安全性とロバスト性に関してはマークの埋め込みに適する）高アクティビティの領域が多数ある場合でも、埋め込み領域の数の選択は、信頼性と費用のトレードオフになる。埋め込み領域の数を多くするほど、フィンガープリントの数が多くなり、信頼性が高くなるが、費用も増える。一方、埋め込み領域の数を少なくするほど、フィンガープリントの数が少なくなり、信頼性が低くなり、逃してしまう協力者の数が増える。但し、フィンガープリントの検出および抽出にかかる費用が少なくなる面もある。
【００３４】
各非同期化領域に対してランダム非同期化を実行する（ステップ３２０）。ランダム非同期化は、非同期化フィンガープリンティング方法を予測攻撃から保護するために用いる、非同期化フィンガープリンティング方法の新規な機能である。フィンガープリンティングにおける１つの課題は、製品のコピーの数が非常に多い場合や、同じシーンが多数の鍵でフィンガープリンティングされている場合に発生する部類の共謀攻撃である。一例として、攻撃者は、シーンのすべてのフレームを取得し、すべてのフレームの平均を計算することができる（攻撃者が、マーキングされていない元のコンテンツの予測を形成するので、予測攻撃と呼ばれる）。あるいは、攻撃者は、別のコピーからシーンの異なる一部分を選択して貼り合わせ、これにより新しいコピーを形成することができる（コピー・アンド・ペースト攻撃と呼ばれる）。この種の攻撃は（正常に実行されると）大抵は、すべてのフィンガープリントが無効になる。
【００３５】
これらのタイプの攻撃（予測攻撃、コピー・アンド・ペースト攻撃、その他）に対抗するために、非同期化フィンガープリンティング方法では、ランダム非同期化を用いて、シーンに含まれるフレームの数をランダムにばらつかせる。共謀攻撃の適用を可能にするための重要な前提条件の１つとして、すべてのクライアントコピーは「整列」していなければならないことに留意されたい。擬似ランダム非同期化を適用すると、シーンに含まれるフレームの数は、映画のコピー間でばらつく。これらの数は、ユーザごとに擬似ランダムに選択されるので、高い確率でユーザごとに異なる。この技法を、非同期化領域と呼ばれるランダムに選択された領域に適用する。非同期化フィンガープリンティング方法個有の非同期化の技法により、攻撃者がフィンガープリントを消去する確率は低減される。たとえば、映画の１つ目のシーンのコピー１には２８個のフレームが含まれ、コピー２には３２個のフレームが含まれる、とすることが可能である。これにより、潜在的攻撃者が共謀攻撃を適用する可能性が厳しく制限される。すべてのコピーを同期化して平均をとるのが困難になるからである。さらに、コピーの数が多いほど、それらを同期化してつなぎ合わせ、予測攻撃を仕掛けることが困難になる。
【００３６】
次に、各埋め込み領域に情報を埋め込む（ステップ３３０）。一般に、非同期化領域と埋め込み領域とは同じでなくてもよいが、一部が重なっていてもよい。埋め込む情報として、たとえば、マルチメディア製品のコピーの番号を用いることができる。最後に、マルチメディア製品の非同期化フィンガープリンティングされたコピーを出力する（ステップ３４０）。
【００３７】
図４は、図３に示した非同期化埋め込みプロセスの動作をさらに詳細に示す詳細フロー図である。マルチメディア製品のコピーを作成する（ステップ４００）。次に、マスター鍵を使用して、マルチメディア製品のコピー内で非同期化領域をランダムに選択する（ステップ４１０）。同様に、マスター鍵とハッシュ関数を使用して、埋め込み領域をランダムに選択する（ステップ４２０）。次に、各埋め込み領域について、ハッシュ値を検出し、記憶する（ステップ４３０）。
【００３８】
ランダム非同期化プロセスには、製品のコピーを非同期化するために、非同期化領域の幅をランダムにばらつかせるステップが含まれる。このランダム非同期化プロセスでは、まず、マスター鍵を使用して、各非同期化領域の新しい幅をランダムに計算し、それに従って幅を変更する（ステップ４４０）。各埋め込み領域に一意のコピー情報を埋め込む（ステップ４５０）。さらに、各埋め込み領域に一意の秘密鍵を埋め込む（ステップ４６０）。最後に、製品の非同期化フィンガープリンティングされた製品のコピーを出力する（ステップ４７０）。
【００３９】
図５は、図２に示した非同期化フィンガープリンティング方法の検出および抽出プロセスの動作を示す概略フロー図である。このプロセスでは、まず、オリジナルのマルチメディア製品の違法コピーを取得する（ステップ５００）。次に、違法コピーのハッシュ値を計算する（ステップ５１０）。次に、算出したハッシュ値から埋め込み領域を特定する（ステップ５２０）。
【００４０】
次に、秘密鍵の各々について、埋め込み領域の各々で電子透かし検出プロセスを実行する（ステップ５３０）。したがって、埋め込み領域各々で、秘密鍵の各々が試される。これにより、フィンガープリンティングの符号または他の種類の符号の必要性が低くなる。計算の費用を度外視すれば、このプロセスを用いることにより、現在可能な規模よりずっと大規模な共謀を追跡できる。あるいは、違法コピーに対して、ランダムな数の鍵を選択して試すことができる。この場合は、計算の費用が減るが、ある程度の数の協力者を逃すリスクを伴う。
【００４１】
次に、特定の秘密鍵に関連付けられた識別情報を検出する（ステップ５４０）。この識別情報として、たとえば、製品のコピーの購入者の名前と住所を用いることができる。次に、検出した識別情報を抽出し、協力者に関連付けて、協力者情報を取得する（ステップ５５０）。これにより、協力者のリストを作成することができる（ステップ５６０）。
【００４２】
Ｖ．例示的な動作環境
非同期化フィンガープリンティングのシステムおよび方法１００は、コンピューティング環境において、コンピューティング装置上で動作することを想定している。ここでは、非同期化フィンガープリンティングのシステムおよび方法１００が動作するコンピューティング環境について説明する。以下の説明は、非同期化フィンガープリンティングのシステムおよび方法１００の実装に適するコンピューティング環境についての簡単かつ一般的な説明を意図したものである。
【００４３】
図６は、図１に示した非同期化フィンガープリンティングのシステムおよび方法１００を実装するのにふさわしいコンピューティングシステム環境の一例を示す図である。コンピューティングシステム環境６００は、適するコンピューティング環境の一例に過ぎず、本発明の用途または機能性の範囲に関する何らかの限定を意図するものではない。コンピューティング環境６００は、例示的な動作環境６００に示す、いずれかのコンポーネントまたはコンポーネントの組み合わせに関連する何らかの依存性または要件を有すると見なされるべきではない。
【００４４】
非同期化フィンガープリンティングのシステムおよび方法１００は、他のさまざまな汎用または特殊用途のコンピューティングシステム環境または構成で動作可能である。非同期化フィンガープリンティングのシステムおよび方法での使用に適すると考えられるよく知られたコンピューティングシステム、環境、および／または構成の例として、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルド、ラップトップ、またはモバイルコンピュータあるいは、携帯電話およびＰＤＡなどの通信装置、マルチプロセッサシステム、マイクロプロセッサベースシステム、セットトップボックス、プログラマブル民生用電子機器、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、これらのシステムまたは装置を任意に含む分散コンピューティング環境などがあり、これらに限定されない。
【００４５】
非同期化フィンガープリンティングのシステムおよび方法１００は、コンピュータで実行されるプログラムモジュールなどの、コンピュータで実行可能な命令の一般的なコンテキストで説明できる。一般に、プログラムモジュールとして、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などがあり、これらは、特定のタスクを実行したり、または特定の抽象データ型を実装したりする。非同期化フィンガープリンティングのシステムおよび方法１００は、通信ネットワークでリンクされたリモート処理装置でタスクを実行する分散コンピューティング環境でも実施することができる。分散コンピューティング環境では、プログラムモジュールを、ローカルコンピュータとリモートコンピュータの両方の記憶媒体（メモリ記憶装置を含む）に配置することができる。図６を参照すると、非同期化フィンガープリンティングのシステムおよび方法１００を実装する例示的なシステムは、コンピュータ６１０という形態で汎用コンピューティング装置を備える。
【００４６】
コンピュータ６１０のコンポーネントとして、処理ユニット６２０、システムメモリ６３０、システムメモリを含む種々のシステムコンポーネントを処理ユニット６２０に接続するシステムバス６２１などを含めることができるが、これらに限定されない。システムバス６２１として、メモリバスまたはメモリコントローラ、周辺機器バス、および種々のバス構造を任意に使用するローカルバスなど、任意のさまざまなタイプのバス構造を使用できる。そのようなアーキテクチャの例として、ＩＳＡ（Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＭＣＡ（Ｍｉｃｒｏ  Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ  ＩＳＡ）バス、ＶＥＳＡ（Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ）ローカルバス、およびメザニンバスとも呼ばれるＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ）バスなどがあるが、これらに限定されない。
【００４７】
コンピュータ６１０は、通常、種々のコンピュータ読取り可能な媒体を含む。コンピュータ読取り可能な媒体として、コンピュータ６１０からアクセスできる任意の市販媒体を使用でき、揮発性媒体と不揮発性媒体、取外し可能な媒体と固定の媒体の両方がある。一例として、コンピュータ読取り可能な媒体には、コンピュータ記憶媒体や通信媒体があり、これらに限定されない。コンピュータ記憶媒体には、揮発性、不揮発性、取外し可能な、および固定の媒体があり、これらは、コンピュータ読取り可能な命令、データ構造、プログラムモジュール、その他のデータなどの情報の記憶のためのあらゆる方法または技術に実装されている。
【００４８】
コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリもしくは他のメモリ技術、ＣＤ−ＲＯＭ、ＤＶＤ（デジタル多用途ディスク）もしくは他の光ディスク記憶媒体、磁気カセット、磁気テープ、磁気ディスクもしくは他の磁気記憶媒体または他の磁気記憶装置、または他の、必要な情報を記憶し、コンピュータ６１０からアクセスできる任意の媒体があるが、これらに限定されない。通信媒体は、通常、コンピュータ読取り可能な命令、データ構造、プログラムモジュールなどのデータを、搬送波などの変調データ信号または他の伝送メカニズムのかたちで具現化し、任意の情報配信媒体を含む。
【００４９】
「変調データ信号」という用語は、信号に情報を符号化するようにその１つまたは複数の特性が設定または変更された信号を意味することに留意されたい。一例として、通信媒体には、有線ネットワークまたは直接有線接続などの有線媒体や、音響、ＲＦ、赤外線などの無線媒体があるが、これらに限定されない。以上の媒体の任意の組み合わせも、コンピュータ読取り可能な媒体の範囲に含まれる。
【００５０】
システムメモリ６３０は、ＲＯＭ（読み出し専用メモリ）６３１やＲＡＭ（ランダムアクセスメモリ）６３２などの揮発性および／または不揮発性メモリの形態でコンピュータ記憶媒体を含む。ＢＩＯＳ（基本入出力システム）６３３は、起動時などにコンピュータ６１０内で要素間の情報転送を支援する基本ルーチンを含み、通常はＲＯＭ６３１に記憶される。ＲＡＭ６３２は、通常、ただちに処理ユニット６２０からアクセスできるデータおよび／またはプログラムモジュールや、間もなく処理ユニット６２０によって処理が行われるデータおよび／またはプログラムモジュールを格納する。一例として、図６では、オペレーティングシステム６３４、アプリケーションプログラム６３５、他のプログラムモジュール６３６、およびプログラムデータ６３７を示しているが、これらに限定されない。
【００５１】
コンピュータ６１０は、他の取外し可能なまたは固定の、揮発性または不揮発性のコンピュータ記憶媒体も含むことができる。図６では、例としてのみ、固定で不揮発性の磁気媒体の読み取りまたは書き込みを行うハードディスクドライブ６４１、取外し可能な不揮発性の磁気ディスク６５２の読み取りまたは書き込みを行う磁気ディスクドライブ６５１、および取外し可能な不揮発性の光ディスク６５６（ＣＤ−ＲＯＭまたは他の光媒体）の読み取りまたは書き込みを行う光ディスクドライブ６５５を示している。
【００５２】
例示的な動作環境で使用できる他の取外し可能なまたは固定で、揮発性または不揮発性のコンピュータ記憶媒体として、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭ、その他があるが、これらに限定されない。ハードディスクドライブ６４１は、通常、インターフェース６４０などの固定メモリインターフェースを介してシステムバス６２１に接続され、磁気ディスクドライブ６５１と光ディスクドライブ６５５は、通常、インターフェース６５０などの取外し可能なメモリインターフェースによってシステムバス６２１に接続される。
【００５３】
上記で説明し、図６に示したドライブとそれに対応するコンピュータ記憶媒体は、コンピュータ６１０で使用するコンピュータ読取り可能な命令、データ構造、プログラムモジュール、およびその他のデータを記憶する。図６では、たとえば、ハードディスクドライブ６４１がオペレーティングシステム６４４、アプリケーションプログラム６４５、他のプログラムモジュール６４６、およびプログラムデータ６４７を格納している。これらのコンポーネントは、オペレーティングシステム６３４、アプリケーションプログラム６３５、他のプログラムモジュール６３６、およびプログラムデータ６３７と同じであっても、異なっていてもよいことに留意されたい。オペレーティングシステム６４４、アプリケーションプログラム６４５、他のプログラムモジュール６４６、およびプログラムデータ６４７は、ここでは、少なくとも、これらが別のコピーであることを示すために、異なる番号になっている。ユーザは、キーボード６６２やポインティングデバイス６６１（一般にマウス、トラックボール、タッチパッドなどを指す）などの入力装置からコンピュータ６１０にコマンドや情報を入力することができる。
【００５４】
他の入力装置（図示せず）として、マイクロホン、ジョイスティック、ゲームパッド、パラボラアンテナ、スキャナ、ラジオ受信機、または、テレビ受像器もしくは放送ビデオ受信機なども使用できる。これらの入力装置や他の入力装置は、たいていの場合、システムバス６２１に接続されているユーザ入力インターフェース６６０を介して処理ユニット６２０に接続されるが、他のインターフェースやバス構造（たとえば、パラレルポート、ゲームポート、またはＵＳＢ（ユニバーサルシリアルバス）など）で接続することもできる。モニタ６９１または他のタイプの表示装置も、ビデオインターフェース６９０などのインターフェースを介してシステムバス６２１に接続される。コンピュータは、モニタの他に、スピーカ６９７やプリンタ６９６などの他の周辺出力装置も含めることもでき、これらは、出力周辺機器インターフェース６９５を介して接続できる。
【００５５】
コンピュータ６１０は、リモートコンピュータ６８０など、１つまたは複数のリモートコンピュータへの論理接続を使用して、ネットワーク環境で動作できる。リモートコンピュータ６８０として、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピア装置または他の通常のネットワークノードなどを使用でき、通常は、コンピュータ６１０を中心として上記で説明してきた要素の多くまたはすべてを使用できるが、図６では、メモリ記憶装置６８１だけを示している。図６に示した論理接続は、ＬＡＮ（ローカルエリアネットワーク）６７１およびＷＡＮ（ワイドエリアネットワーク）６７３を含むが、他のネットワークも含むことができる。そのようなネットワーキング環境は、オフィス、企業規模コンピュータネットワーク、イントラネット、およびインターネットではごく一般的である。
【００５６】
コンピュータ６１０は、ＬＡＮネットワーキング環境で使用される場合、ネットワークインターフェースまたはアダプタ６７０を介してＬＡＮ６７１に接続される。また、ＷＡＮネットワーキング環境で使用される場合、コンピュータ６１０は、通常、ＷＡＮ６７３（インターネットなど）経由の通信を確立するためにモデム６７２などの手段を含む。モデム６７２は、内蔵でも外付けでも、ユーザ入力インターフェース６６０または他の適切なメカニズムにより、システムバス６２１に接続できる。ネットワーク環境では、コンピュータ６１０を中心として示した各種プログラムモジュールまたはその一部を、リモートメモリ記憶装置に記憶できる。一例として、図６では、メモリ装置６８１の常駐プログラムとしてリモートアプリケーションプログラム６８５を示したが、これに限定されない。説明したネットワーク接続は例示的なものであり、コンピュータ間の通信リンクを確立する他の手法も使用できることを理解されたい。
【００５７】
ＶＩ．システムコンポーネント
図１に示す非同期化フィンガープリンティングシステム１００では、システム１００が、これに含まれるいくつかのプログラムモジュールを使用して、マルチメディア製品のコピーに一意のマーキングを施した後に、その製品の違法コピーの製造に関与した協力者を識別することができる。システム１００は、大まかに言えば、埋め込み機能と、検出および抽出機能とを含む。ここでは、これらの機能のそれぞれに対応するプログラムモジュールについて説明する。
【００５８】
図７は、図１に示した非同期化フィンガープリンティングシステム１００の詳細を示すブロック図である。システム１００は、基本的に、破線で示した２つの機能（（ａ）フィンガープリントの非同期化埋め込み、および（ｂ）フィンガープリントの検出および抽出）を有する。詳細には、埋め込み機能において、オリジナルのデジタルマルチメディア製品７００（映画または録音など）を非同期化フィンガープリンティングシステム１００に入力する。次に、非同期化フィンガープリンティングシステム１００内にある埋め込みモジュール７１０を使用して製品７００を処理し、製品７００の非同期化フィンガープリンティングを施されたコピー７２０を作成する。
【００５９】
検出および抽出機能においては、製品７００の違法コピー７３０を取得し、非同期化フィンガープリンティングシステム１００で解析する。非同期化フィンガープリンティングシステム１００内にある検出および抽出モジュール７４０を使用して、埋め込まれているフィンガープリントを検出し、フィンガープリント内の情報を抽出する。この情報によって、違法コピー７３０の製造に関与した協力者を一意に識別できる。この結果から、非同期化フィンガープリンティングシステム１００は、協力者のリスト７５０を作成することができる。
【００６０】
図８は、図７に示した埋め込みモジュール７１０の詳細を示すブロック図である。詳細には、埋め込みモジュール７１０は、コピーモジュール８００、埋め込み領域セレクタ８１０、非同期化領域セレクタ８２０、ランダム非同期化モジュール８３０、および埋め込みモジュール８４０を備える。まず、コピーモジュール８００を使用して、オリジナルのデジタルマルチメディア製品７００のコピーを複数個製造する。これらのコピーの各々を、埋め込みモジュール８４０で処理する。埋め込み領域セレクタ８１０が、各コピーにおいて、フィンガープリントを埋め込む領域をランダムに選択する。同様に、非同期化領域セレクタ８２０が、各コピーにおいて、幅変更によるランダム非同期化を適用する領域をランダムに選択する。実施形態によっては、埋め込み領域セレクタ８１０と非同期化領域セレクタ８２０は、埋め込み領域と非同期化領域の数も選択する。
【００６１】
ランダム非同期化モジュール８３０は、非同期化領域の各々の幅をランダムに選択する。これは、非同期化領域の幅が、製品７００の複数のコピー間で少しずつ異なることを意味する。幅は、製品７００が映画であればフレーム数を意味し、あるいは、製品７００が録音であればオーディオセグメントの時間長を意味する。埋め込みモジュール８４０は、埋め込み領域の各々の内にフィンガープリントを埋め込んで、製品７００の非同期化フィンガープリンティングされたコピー７２０を製造する。
【００６２】
図９は、図７に示した検出および抽出モジュール７４０の詳細を示すブロック図である。検出および抽出モジュール７４０は、ハッシュ値抽出器（ｅｘｔｒａｃｔｏｒ）９００、埋め込み領域割り出しモジュール９１０、フィンガープリント検出器（ｄｅｔｅｃｔｏｒ）９２０、および協力者抽出モジュール９３０を備える。ハッシュ値抽出器９００は、違法コピー７３０を解析し、ハッシュ値を抽出する。埋め込み領域割り出しモジュール９１０は、抽出されたハッシュ値を、オリジナル信号の埋め込み領域のハッシュ値と比較して、違法コピー７３０内の埋め込み領域の位置を割り出す。フィンガープリント検出器９２０は、埋め込み領域の各々でフィンガープリントを探す。フィンガープリントの検出には、各々の秘密鍵を使用する。協力者抽出モジュール９３０は、フィンガープリントの検出に使用した秘密鍵に基づいて協力者に関する情報を抽出する。特定の秘密鍵によってフィンガープリントが検出された場合は、その鍵に関連付けられた一意情報を使用して、違法コピー７３０の製造に関与した協力者を識別する。通常は、協力者が多数いるので、違法コピー７３０の製造に関与した協力者のリストを生成する。
【００６３】
ＶＩＩ．実施例
本願明細書で開示した非同期化フィンガープリンティングのシステムおよび方法がよりよく理解されるように、代表的な実施例の動作を詳細に説明する。この実施例は、非同期化フィンガープリンティングのシステムおよび方法を実装する一方法に過ぎないことに留意されたい。この実施例では、非同期化フィンガープリンティングのシステムおよび方法をストリーミングマルチメディアオブジェクトに適用している。
【００６４】
非同期化フィンガープリンティングのシステムおよび方法は、オーディオとビデオの両方の用途に用いることができる。一般に、各ユーザには異なる鍵を割り当てる。埋め込み機能には、選択した領域に擬似ランダム変換を適用する機能が含まれる。擬似ランダム変換用の鍵は、ユーザ固有である。これらの領域は、安全なマルチメディアハッシュ関数を介して選択される。検出および抽出機能には、ユーザの鍵空間の総当たり（ｂｒｕｔｅ−ｆｏｒｃｅ）検索が含まれる。それらの鍵の１つに十分な「確実性」があれば、そのユーザが違法コピーの製造に関与していることが明らかになる。
【００６５】
表記
所与のマルチメディア信号が、別個の「オブジェクト」、ｓ１、ｓ２、．．．、ｓＭからなるとする。但し、Ｍはオブジェクトの総数。たとえば、ビデオ用途では、１つのフレームを１つのオブジェクトとして扱い、ビデオのフレームの総数をＭで表すことができる。また、オーディオ用途では、固定長の時間ブロックの１つを１つのオブジェクトとして扱い、そのような時間ブロックの総数をＭで表すことができる。顧客（または購入者）の総数をＮとする。したがって、マルチメディア信号の、Ｎ個の異なるコピーを製造することが必要になる。ユーザｉ（１≦ｉ≦Ｎ）の秘密鍵をＫｉとする。秘密マスター鍵をＫとする。これは
【００６６】
【数１】
0004810096.tif 000002
【００６７】
と異なる。
【００６８】
ハッシュ関数
ハッシュ関数  ｈＫ（・）
があると仮定する。これは、オブジェクト
｛ｓｉ｝
に対して動作し、その範囲は、
｛０，１｝Ｌ
である。このハッシュ関数は擬似ランダムな演算子であり、秘密鍵Ｋによってランダム化される。
（出力ハッシュ値の長さＬで正規化された）正規化ハミング距離を
【００６９】
【数２】
0004810096.tif 000003
【００７０】
で表し、次のように仮定する。
１．ｈＫ（ｓｉ）は、所与の各ｉについて、｛０，１｝Ｌにほぼ均一に分布する。
２．
【００７１】
【数３】
0004810096.tif 000004
【００７２】
但し、ｓｉとｓｊは知覚的に異なるオブジェクトである。
３．
【００７３】
【数４】
0004810096.tif 000005
【００７４】
但し、ｓｉとｓ'ｉは知覚的にほぼ同じオブジェクトである。
上記条件では、異なる複数の鍵に対して確率空間が定義されることに留意されたい。実際の用途のほとんどでは、０＜Ｔ０＜Ｔ１＜０．５であり、Ｔ０とＴ１は十分離れている。
【００７５】
オブジェクトのグループのウォーターマーキング
この実施例では、擬似ランダム電子透かし埋め込み関数
ＷＫｉ（・）
を使用しており、これはほとんどのＲオブジェクトに対して動作する。ここで、Ｋｉは、ウォーターマーキングで使用する擬似ランダム数ジェネレータの鍵である。所与のｒ個（１≦ｒ≦Ｒ）のオブジェクト（たとえば、ｓ１，．．．，ｓｒ−１，ｓｒ）に対し、この電子透かし埋め込み関数は、ｒ個のオブジェクト
【００７６】
【数５】
0004810096.tif 000006
【００７７】
を、鍵Ｋｉの関数として生成する。オブジェクト
【００７８】
【数６】
0004810096.tif 000007
【００７９】
は、知覚的には、
【００８０】
【数７】
0004810096.tif 000008
【００８１】
と同等である。このコンテキストにおいて、電子透かし埋め込み関数は、秘密鍵をインデックスとする擬似ランダム変換ととらえることができる。さらに、この実施例では、対応する電子透かし検出関数
ＤＫｉ（・）
を仮定している。この関数は、埋め込み関数の場合と同数のオブジェクトに対して動作する。この検出関数の定義域は｛０，１｝である。１は、鍵Ｋｉによって電子透かしの存在が決定することを示し、０は、決定しないことを示す。検出関数の動作は信頼できるものと仮定する。すなわち、以下を仮定する。
１．
【００８２】
【数８】
0004810096.tif 000009
【００８３】
但し
【００８４】
【数９】
0004810096.tif 000010
【００８５】
は
【００８６】
【数１０】
0004810096.tif 000011
【００８７】
の攻撃された結果である。攻撃は、両者は知覚的には同等であるようになされたものとする。
２．
【００８８】
【数１１】
0004810096.tif 000012
【００８９】
および
【００９０】
【数１２】
0004810096.tif 000013
【００９１】
ストリーミングマルチメディアのマーク埋め込み
ユーザｉ（１≦ｉ≦Ｎ）に対するマーク埋め込みのアルゴリズムは以下のとおりである。
１．Ｐ個の異なる位置を選択し、マスター鍵Ｋでランダム化する。これらの各位置をｔ１，ｔ２，．．．，ｔｐとする。但し、
ｔｊ∈｛１，２．．．Ｎ｝，１≦ｊ≦Ｐ
２．次のハッシュ値を求め、記憶する。
【００９２】
【数１３】
0004810096.tif 000014
【００９３】
３．各位置ｔｊに対し、幅
２Δｊ＋１
をその近傍とする。これにより、以下の領域を求める。
ｊ，ｔｊ−Δｊ，ｔｊ−Δｊ＋１，．．．，ｔｊ＋Δｊ−１，ｔｊ＋Δｊ，１≦ｊ≦Ｐ
ここで、マスター鍵Ｋを使用して、
【００９４】
【数１４】
0004810096.tif 000015
【００９５】
を擬似ランダムに選択する。この場合、すべてのｊについて、
２Δｊ＋１≦Ｒ
であるとし、
ｊ≠ｋ
であるすべてのｊとｋについて、領域ｊと領域ｋが重ならないようにする。
４．各ｊ（１≦ｊ≦Ｐ）について、
【００９６】
【数１５】
0004810096.tif 000016
【００９７】
を
【００９８】
【数１６】
0004810096.tif 000017
【００９９】
で置き換える。但し、Ｋｉはユーザｉの秘密鍵である。
【０１００】
ストリーミングマルチメディアの復号
オブジェクトｘ１，ｘ２，．．．，ｘＭ’からなるマルチメディア信号を、デコーダへの入力とする。一般には
Ｍ’≠Ｍ
とすることが可能であることに留意されたい。実施例で使用する検出および抽出（または復号）プロセスには、以下の操作が含まれる。
１．すべてのｊ（１≦ｊ≦Ｍ’）について、受信信号ｈＫ（ｘｊ）のハッシュ値を計算する。
２．各ｊ（１≦ｊ≦Ｍ’）について、以下を実行する。
（ａ）
【０１０１】
【数１７】
0004810096.tif 000018
【０１０２】
が成り立つｔｋ（１≦ｋ≦Ｐ）が存在する場合は、次のステップに進む。
（ｂ）すべてのＫｉ（１≦ｉ≦Ｎ）について、ｔｋの周囲の幅２Δｋ＋１の領域に対し、電子透かし検出アルゴリズムを実行する。すなわち、以下を計算する。
【０１０３】
【数１８】
0004810096.tif 000019
【０１０４】
（ｃ）各ｉ（１≦ｉ≦Ｎ）に対し、ｄｉ＝１であれば、ユーザｉのマークが受信入力内で見つかったことを宣言する。
【０１０５】
ＶＩＩＩ．デジタルビデオ向けに改良したイメージハッシュに基づく時間同期化アルゴリズム
前のセクションの実施例では、非同期化フィンガープリンティングのシステムおよび方法の概略アルゴリズムを説明した。この実施例のマーク埋め込みアルゴリズムのステップ２と、復号アルゴリズムのステップ２（ａ）では、マーク埋め込み位置を照合するために単一のハッシュ値を用いた。但し、実用上は、これで十分とは限らない。特にデジタルビデオにおいては、埋め込み位置を十分な精度で検出するのに、単一のイメージフレームのハッシュ値では不十分な場合がしばしばある。そこで、このセクションでは、改良版のハッシュベース領域照合技法について説明する。この技法では、単一のハッシュ値の代わりに複数のハッシュ値を用いる。
【０１０６】
このセクションでは、説明をデジタルビデオの場合に限定し、単一のビデオフレーム（単一イメージ）に適用される強固なイメージハッシュ関数を使用する。但し、この方法論はフレームの集合またはデジタルオーディオ信号にも明らかに拡張可能であることに留意されたい。このセクションで説明する、改良したハッシュに基づく領域照合技法は、図９の埋め込み領域割り出しモジュール９１０に適用できる。
【０１０７】
ここで、マークを埋め込まれたビデオが、検出または復号時に時間同期化の問題を起こす変更を受ける可能性があるということが懸念される。多くの場合、一時的な攻撃はこのクラスである。特に、時間軸に対してビデオの内容の順序を変更する等の悪意ある攻撃（シーンの挿入、変更および入れ替え、時間の大量間引き（ｄｅｃｉｍａｔｉｏｎ）および内挿（ｉｎｔｅｒｐｏｌａｔｉｏｎ）、ならびにシフトなど）がデコーダにとって問題となる可能性がある。さらに、悪意がない場合でも、エンタテインメントビジネスにおける種々の用途により、ビデオを切り貼りし、またはビデオにコマーシャルを挿入する可能性がある。そうした結果、オリジナルビデオのマーク埋め込み領域が、受信したビデオの同じ時間上の位置にない可能性がある。そのような場合、受信側でマーク埋め込み位置を見つけるのは難しい。この問題を克服するために、このセクションで説明する改良版のハッシュベース領域照合技法は、強固なイメージハッシュ関数を用いてマーク埋め込み位置を割り出すことにより、デジタルビデオの時間同期化を達成する。
【０１０８】
この技法は、電子透かし埋め込みを行っても、許容可能な攻撃（言い換えると、知覚品質が維持される程度の攻撃）を受けても、強固なイメージハッシュ関数の出力が不変であることを前提としている。まず、万全を期すために、このセクションでの表記を定義する。このセクションでの表記は、セクションＶＩＩでの表記と異なることを留意されたい。
【０１０９】
0004810096.tif 000020
【０１１０】
0004810096.tif 000021
【０１１１】
0004810096.tif 000022
【０１１２】
注記
この直接的なプロセスを用いることにより、ステップ３および４において
【０１１３】
【数１９】
0004810096.tif 000023
【０１１４】
演算を行うことに注目されたい。理由は、可能なＫタプルの総数が
【０１１５】
【数２０】
0004810096.tif 000024
【０１１６】
（つまり、Ｋの指数関数）であること、およびこのアプローチは、各Ｋタプルに対し、Ｏ（Ｋ）演算を実行して、知覚的同等性の意味においての最適一致（言い換えると、オリジナルのハッシュ値までのハミング距離）を見つける必要があることである。但し、ハッシュ値間のハミング距離を再計算する必要のない共通要素を含むＫタプルが存在するため、それらの演算には冗長性がある。したがって、動的プログラミングを用いることにより、ステップ３および４を一緒に解くという、計算の面でより効率的なアプローチを適用できる。
【０１１７】
0004810096.tif 000025
【０１１８】
上述の本発明の説明は、例示および解説を目的としたものであり、網羅的なものとし、または開示した精細な形態に本発明を限定することを意図したものではない。上記の教示に照らして、多くの変更形態や変形形態が可能である。本発明の範囲は、本発明のこの詳細な説明によっては限定されず、特許請求の範囲によって限定されるものである。
【図面の簡単な説明】
【０１１９】
【図１】本願明細書で開示した非同期化フィンガープリンティングのシステムおよび方法の例示的な実施態様を示すブロック図である。
【図２】図１に示した非同期化フィンガープリンティングシステムの全般的な動作を示す概略フロー図である。
【図３】図２に示した非同期化フィンガープリンティング方法の非同期化埋め込みプロセスの動作を示す概略フロー図である。
【図４】図３に示した非同期化埋め込みプロセスの動作をさらに詳細に示す詳細フロー図である。
【図５】図２に示した非同期化フィンガープリンティング方法の検出および抽出プロセスの動作を示す概略フロー図である。
【図６】図１に示した非同期化フィンガープリンティングのシステムおよび方法を実装するのにふさわしいコンピューティングシステム環境の一例を示す図である。
【図７】図１に示した非同期化フィンガープリンティングシステムの詳細を示すブロック図である。
【図８】図７に示した埋め込みモジュールの詳細を示すブロック図である。
【図９】図７に示した検出および抽出モジュールの詳細を示すブロック図である。
【符号の説明】
【０１２０】
１４０〜１５５  購入者
１６５〜１７５  購入者
６１０  コンピュータ
６４１  ハードディスクドライブ
６５１  磁気ディスクドライブ
６５２  磁気ディスク
６５５  光ディスクドライブ
６５６  光ディスク
６８１  メモリ記憶装置
【図１】
0004810096.tif 000026
【図２】
0004810096.tif 000027
【図３】
0004810096.tif 000028
【図４】
0004810096.tif 000029
【図５】
0004810096.tif 000030
【図６】
0004810096.tif 000031
【図７】
0004810096.tif 000032
【図８】
0004810096.tif 000033
【図９】
0004810096.tif 000034