結託戦略の選択を含む確率論的結託防止符号のための復号方法
【課題】デジタル・コンテンツの不正コピーの作成および頒布に対する保護で、不正コピーのソースの特定を可能とする符号化方法を提供する。
【解決手段】確率論的結託防止符号の復号方法であって、マルチメディア・コンテンツの不正コピーの作成に使われた前記マルチメディア・コンテンツ中に存在する前記符号の少なくとも一つのシーケンスを識別することをねらいとし、結託戦略モデルの集合のうちから前記不正コピーを構築するために使われた結託戦略を選択するステップを含む。
【解決手段】確率論的結託防止符号の復号方法であって、マルチメディア・コンテンツの不正コピーの作成に使われた前記マルチメディア・コンテンツ中に存在する前記符号の少なくとも一つのシーケンスを識別することをねらいとし、結託戦略モデルの集合のうちから前記不正コピーを構築するために使われた結託戦略を選択するステップを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、不正コピーに対するデジタル・コンテンツの保護および不正コピーの出所におけるソースの特定という概括的な領域に関する。より詳細には、本発明は、デジタル・コンテンツの不正コピーの起源における（at the origin）一つまたは複数のソースを特定することをねらいとする確率論的結託防止符号（probabilistic anti-collusion code）のための高速復号方法に関する。
【背景技術】
【０００２】
たとえば音楽、映画、写真およびビデオ・ゲームのようなデジタル・コンテンツの、不正コピーの作成および頒布に対する保護は、メディアおよびエンターテインメント産業にとって、特にマルチメディア・コンテンツの提供者および著作権保有者にとって重要な問題である。
【０００３】
この目的のため、不正なコンテンツの作成および頒布を克服するためにさまざまな解決策が知られている。データの暗号化に基づく解決策は不正コピーの実際の作成および頒布を防止する。正当なコピーのトレーサビリティ〔追跡可能性〕に基づく抑止的な解決策は、不正コピーのソースを特定することを可能にする。本発明の領域は、この後者の抑止的な解決策の範疇に属する。
【０００４】
不正コピーの起源におけるソースの特定には、数多くの応用がある。たとえば、ビデオ・オン・デマンド・サーバーは、異なる顧客に対して同じコンテンツの個人的なコピーを配信する。海賊と呼ばれる一部の不心得な顧客がこのコンテンツのコピーを、たとえばP2P（ピアツーピア［Peer-To-Peer］ネットワーク上で）不正に再頒布する。著作権保有者は海賊版制作者を特定したい。そのために、ビデオ・オン・デマンド・サーバーは、ビデオ透かし入れ技術を使って各コピーに一意的な識別子を挿入し、これにより一見同一に見えるが異なるコピーを多数生産する。こうして、不正コピー中のコンテンツ識別子により、この不正コピーのソース、よって海賊が特定できる。しかしながら、認識されないために、複数の海賊のグループが、自分たちの異なるコピーを混合することによって不正コピーを構築することによって、識別子を変更することができる。これがコピーの結託（collusion of copies）である。最後に、この同じ海賊のグループは、特に不正コピーを損失のある圧縮にかけることによって、不正頒布されるコピーの識別子に誤りを導入し、無実の人々に罪が着せられたり海賊の素性を隠蔽したりしようと試みることができる。
【０００５】
この目的のため、透かし入れによってコピーに挿入される識別子を、結託防止符号（anti-collusion code）のシンボルのシーケンスとすることが知られている。D・ボネーおよびJ・ショーのような暗号学者は、非特許文献１において、有限個の符号シーケンスの混合の復号によって、そのコピーを作成するために使われた結託戦略が何であっても、結託のために使われたもとのシーケンスの部分集合を特定することを可能にする最短長の最適符号の存在を示している。
【０００６】
既知の広く使われているそのような最適符号は、タルドスによって2003年に非特許文献２において提案された。この確率論的符号は、用いられている結託戦略が何であっても一様に効率的な復号システムのパフォーマンス基準に応答する。それは、ユーザー数（符号におけるシーケンス数に対応）、不心得なユーザーの最大数（符号における、識別が試みられるシーケンスの数に対応）、アルファベット中のシンボル数、偽警報確率（結託の一員でなかったユーザーに罪を着せる事実）およびミス確率（結託の一員であったユーザーを特定しない事実）に依存するその長さによって特徴付けられる。
【０００７】
フィリップスは、非特許文献３において、偽警報の確率をある閾値ε未満に維持したければ、タルドスのもののような二元符号について、符号長は2π2c2log(nε-1)より大きくなければならないことを示した。ここで、cは不心得な顧客の数を表し、nは全顧客数を表す。フィリップスはまた、（非特許文献４において）符号長を最短にする発想に従って、タルドス符号を任意の大きさのアルファベット上で設計された符号に一般化することにも取り組んだ。
【０００８】
これらの解決策の技術的課題は、符号の長さである。他方、透かし入れ技術を使ってマルチメディア・コンテンツ中に隠すことのできるシンボル数は限られており、符号の長さは、識別されるべきコンテンツのサイズと適合する範囲内に留まる必要がある。他方、復号の計算量は符号の長さに直接関係し、復号装置の計算パワーおよびメモリ・サイズ手段の制限は最小限に留まる必要がある。さらに、結託防止符号の長さは、特にビデオ・オン・デマンド・サービスのサービス・ユーザーおよび潜在的に不心得なユーザーの増え続ける数を扱うために増加する。
【０００９】
本願と同じ出願人によって同日に出願される第一の特許出願では、そのような符号を復号する逐次反復的な方法であって、結託中に存在する諸シーケンスの識別ステップに関連付けられた結託戦略の推定ステップを含む方法が提案された。この方法は、符号復号パフォーマンスを改善することおよび伝送におけるノイズによってまたはコンテンツの変換（transformation）によって導入される誤りに対して耐性があることという利点を呈する。その復号パフォーマンスは、結託における諸シーケンスを識別するために使われる符号の長さを制限することを可能にし、よって前記の技術的課題に対する解決策を提供する。しかしながら、この復号方法は、その逐次反復的な方法のため、かなりの計算パワーおよびメモリ・サイズ手段を要求する。したがって、第二の技術的課題は、多数のシーケンスをサポートする符号のための使用を不可能にすることがありうる逐次反復的な復号の複雑さである。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】D. Boneh and J. Shaw, "Collusion-secure fingerprinting for digital data", "IEEE Transactions on Information Theory", vol. 44, pp. 1897-1905, 1998年9月
【非特許文献２】Tardos, "Optimal probabilistic fingerprint codes", "Proc. of the 35th annual ACM symposium on theory of computing", pp.116-125, San Diego, CA, USA, 2003年, ACM
【非特許文献３】B. Skoric, T. Vladimirova, M. Celik, and J. Talstra, "Tardos fingerprinting is better than we thought", "IEEE Transactions on Information Theory", vol. 54, pp. 3363-3676, 2008年8月
【非特許文献４】B. Skoric, S. Katzenbeisser and M. Celik, "Symmetric Tardos fingerprinting codes for arbitrary alphabet sizes", "Designs, Codes and Cryptography", vol. 46(2):137-166, 2008年2月
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、タルドス符号のような確率論的結託防止符号のパフォーマンスを、該符号の生成ではなく復号において改善しつつ、復号演算の計算量を制限することによって、従来技術の欠点の少なくとも一つを克服することである。従来技術では、復号パフォーマンスは、不心得なユーザーたちの結託戦略が何であっても保証される。本発明の発想は、可能な結託戦略について仮設を立てて、それらの仮設のうちから符号のパフォーマンスを改善するよう最も確からしい戦略を選択するというものである。さらに、確率計算は不正コピー中のシーケンスおよび符号シンボルのみに依存するので、この選択は、実装するのが比較的簡単である。
【００１２】
さらに、本発明は、諸符号シーケンスのうちから、復号方法が結託中でのその存在を識別しようとする符号シーケンスをフィルタリングする方法を提案する。有利なことに、このフィルタリング方法は、復号の計算量を低下させる。
【課題を解決するための手段】
【００１３】
この目的のため、本発明は、マルチメディア・コンテンツの不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する符号の少なくとも一つのシーケンスを識別することをねらいとする確率論的結託防止符号のための復号方法であって、結託戦略モデルの集合のうちから前記コピーを構築するために使われた結託戦略を選択するステップを有する方法に関する。実際、海賊のグループは、不正コピーを作成するために、彼らのコピーをブロックごとに混合することによって、種々の結託戦略を使用できる。例として、一様な抽出、多数決、少数決、ランダム投票を挙げることができる。本発明に基づく復号方法は、戦略がランダムであるときおよび戦略が、諸コピーの所与の結託について変わらないときに特に好適である。結託戦略について何の仮設も立てない一様戦略として知られる訴追戦略について従来技術が教示することとは逆に、本発明に基づく復号方法は、不正コピーを作成するために海賊のグループによって使用された戦略を決定する。この知識は、有利なことに、所与の長さの符号について、復号方法をより効率的にする。それにより、無実の人に罪を着せる所与の確率について、符号シンボルの数を減らすことが可能になる。さらに、不正コピーのシーケンスおよび結託に含まれる諸シーケンスの両方を解析することによって結託戦略が推定される逐次反復的な復号方法を提案する本出願人によって本日出願された前記特許出願によって教示されることとは逆に、本発明に基づく結託戦略の推定は、不正コピー中のシーケンスの解析のみに基づく。精確さは下がるものの、この推定は逐次反復的方法に頼らず、よって本発明に基づく復号方法の複雑さを低減するという利点がある。逐次反復的方法とは逆に、本発明に基づく復号方法は、コンテンツ提供者サービスのますます増加する数のユーザーまたはますます増加する数の海賊版制作者のために必要とされるますます増加する数の符号シーケンスに効率的に対処することを可能にする。
【００１４】
本発明のある個別的な特徴によれば、結託戦略は、結託中に存在するいくつかのシーケンスについて、結託中に存在する諸シーケンスのシンボルのリストを知っての不正コピー中にそのシンボルを観察する条件的確率の、結託中に存在する諸シーケンスのシンボルの各リストについて構築される結託戦略の諸確率のベクトルによって表現される。この表現は、結託戦略が不正コピーのシーケンスおよび結託中の諸シーケンスの両方を解析することによって推定される本出願人によって本日出願された前記特許出願において提示される方法の結託戦略の推定に対する仮設を使う。実は、結託戦略は、統計的領域において、確率ベクトル：結託に荷担している海賊たちの全シンボルを知っているときにある海賊が不正コピー中に所与のシンボルを入れる条件付き確率、によってモデル化できる。結託戦略はまた、結託中の海賊の数の知識をも含む。
【００１５】
本発明のもう一つの個別的な特徴によれば、結託戦略のモデルの集合は、結託中に存在するシーケンスの数の各推定について、最も確からしい結託戦略を含む。実際、この集合の生成およびその確率に基づく結託戦略の選択は、可能なあらゆる結託事例を、不正コピー中のシーケンスのみから推定することによって、逐次反復的方法を克服することを可能にする。可能なあらゆる結託事例は、結託中のシーケンスの数および結託中に存在する諸シーケンスのシンボルのリストによって設定されるパラメータをもつ。
【００１６】
本発明のもう一つの個別的な特徴によれば、本発明は：
ａ）結託戦略のモデルの集合を生成する段階、つまり、
ｉ．結託中のシーケンスの数の各推定について、結託中に存在する諸シーケンスのシンボルの各リストについて、不正コピー中に含まれるシーケンスを知っての結託戦略の確率の推定量の計算、
ｉｉ．結託中のシーケンスの数の各推定について、結託戦略の確率の推定量を最大にする結託戦略の事後的な選択；
ｂ）結託戦略のモデルの集合のうちから結託戦略を選択する段階、つまり、
ｉ．最も確からしい結託戦略に関連付けられた結託中のシーケンスの数の各推定について、結託中にあるシーケンスが存在する確率のベクトルであって、符号の各シーケンスについての、不正コピー中に含まれるシーケンス、所与のシーケンスおよび最も確からしい結託戦略を知っているときに結託中に前記所与のシーケンスが存在する条件付き確率から構築されるベクトルの計算、
ｉｉ．最も確からしい結託戦略に関連付けられた結託中のシーケンスの数の各推定について、結託中にあるシーケンスが存在する諸確率と、不正コピー中に含まれるシーケンスを知っているときの結託戦略の確率との前記ベクトルから、結託戦略のモデルの確率の計算、
ｉｉｉ．結託戦略のモデルの前記集合のうちからの、結託戦略の前記モデルの確率を最大にする、前記最も確からしい結託戦略に関連付けられた結託中のシーケンスの数の選択；
ｃ）不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する前記符号の少なくとも一つのシーケンスを、ステップｂ）で推定された結託戦略の前記モデルを知っているときの前記シーケンスの存在の条件付き確率から、識別するステップを含む。
【００１７】
実際、結託戦略の確率のベクトルの形のモデル化から、結託戦略の確率の推定量が定義される：それは、不正コピーに含まれるシーケンスを知っているときの、ある結託戦略の事後確率である。したがって、海賊版制作者の所与の数について最も確からしい結託戦略は、結託戦略のこの事後確率を最大にする結託戦略である。有利には、この第一の基準は、所与の結託に関与する海賊版制作者の数についてのある推定値について、この数のシーケンスについて最も確からしい戦略を選択し、よって実施形態の一つに基づいて結託戦略のモデルの集合を生成することを可能にする。
【００１８】
さらに、第二のステップは、最も確からしいモデルが選択されることを可能にする。つまり、最も確からしい結託戦略に関連付けられた結託中のシーケンスの数である。このステップは、モデルの確率の計算のために、結託戦略の確率に加えて、結託プロセスに加わったユーザーの有罪判定、すなわち識別を使う。有罪判定は、確率ベクトルによってモデル化される：あるユーザーが結託に参加している確率である。有利なことに、これら二つの確率の使用により、結託戦略のモデルのシーケンスの数と有罪判定を相関させることができる。こうして生成されたモデルの集合のうちから結託戦略を選択することにより、本復号方法は、逐次的方法ほど計算パワーにおいて貪欲でない。
【００１９】
最後に、最終ステップにおいて、ステップｂ）で選択された結託戦略を使って有罪判定が実行される。結託に関与している確率は、不正ユーザーと正当なユーザーとの間で明確に異なる。この分離により、本発明に基づく復号方法は、そのパフォーマンス対計算量比のため、特に別の特許出願で教示される逐次的方法と比べて、非常に興味深いものとなる。一様有罪判定方法（つまり、結託戦略についての仮設を立てることなく動作する方法）に対して効率的である復号方法を提案することにより、本発明は、海賊版制作者の識別のために必要とされる符号の長さを短縮することも可能にする。
【００２０】
本発明の別の個別的な特徴によれば、最も確からしい結託戦略の選択後、符号のあるシーケンスが不正コピーの作成に使われたマルチメディア・コンテンツ中に存在するとして識別されるのは、不正コピーに含まれるシーケンス、前記シーケンスおよびステップｂ）で選択された結託戦略のモデルを知っているときに結託中に前記シーケンスが存在する条件付き確率の値が最大であるときである。この特徴により、有罪である確率が最も高いユーザーを訴追することが可能になる。
【００２１】
本発明の別の個別的な特徴によれば、最も確からしい結託戦略の選択後、符号シーケンスのグループが不正コピーの作成に使われたマルチメディア・コンテンツ中に存在するとして識別されるのは、不正コピーに含まれるシーケンス、前記グループの前記シーケンスおよびステップｂ）で選択された結託戦略のモデルを知っているときに前記グループの諸シーケンスのそれぞれについて前記条件付き確率の値がある閾値Sより大きいときである。この特徴は、たとえば、閾値が１／２に固定される場合、有罪である確率が無罪である確率より大きいユーザーを訴追することを可能にする。さらに、無実の個人の確率と有罪の個人の確率との間に明確な分離が観察されることを強調しておくことが有益である。この特徴は、結託防止符号の復号方法のパフォーマンス基準である。有利には、この閾値はまた、無実の個人に罪を着せる確率を減らすように、あるいは海賊版制作者を見逃す確率を減らすように決定されることができる。よって、不正コピーの起源のソースを識別しようとする著作権保有者またはコンテンツ提供者は、単一のユーザーを高い確度をもって追跡することを選ぶか、あるいは結託の発生に関与していた可能性が高いユーザーのグループを追跡することを選ぶことができる。有利には、これら最後の二つの特徴は、コンテンツ提供者またはデータベース管理者のようなかかる解決策の顧客の、「裏切り者追跡（traitor tracing）」のようなさまざまな期待に応えることを可能にする。
【００２２】
本発明の別の個別的な特徴によれば、本復号方法は、符号シーケンスをフィルタリングするステップを含む。フィルタリングするステップは、不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する少なくとも一つのシーケンスを含む可能な最も小さい符号シーケンスのサブグループを選択することを含み、前記選択は、各符号シーケンスについて、選択された所与のシンボル・インデックスについて、前記符号シーケンスのシンボルを不正コピーに含まれているシーケンスのシンボルと比較することによる。海賊版制作者を捜す範囲となるシーケンスの数を制限することによって、実装が非常に簡単なこのフィルタリングは、復号の計算量を制限し、よって本復号方法を、多数のユーザーをサポートする符号について格別に有利にする。実際、海賊版制作者によって使用される結託戦略に依存して、フィルタリングは、ユーザーのうち、つまり符号シーケンスのうちのほんの0.1%ないし20%だけを保持することを可能にする。したがって、このフィルタリングは、特に計算パワーに貪欲なステップａ）およびｂ）における計算から、少なくともユーザーの５分の４を解放することができる。しかしながら、このフィルタリングの負の側面は、有罪判定を単一の海賊版制作者に限定するということ、および不正コピー中のシーケンスに誤りがあってはならないということである。実際、本フィルタリング方法は、不正コピーのシーケンス中に誤ったシンボルがなければ、サブグループが、不正コピーのシーケンス中で選択されたインデックス・シンボルを提供した少なくとも一つの海賊シーケンスを含むことを保証するが、２つ以上あることを保証するものは何もない。有利に、高速復号のこの実施形態は、最初の解析として使用されることができ、その後、追加的な解析において従来技術によって教示される最適復号によって検証されることができる。
【００２３】
本発明の別の個別的な特徴によれば、符号シーケンスをフィルタリングする前記ステップは、前記コピーに含まれるシーケンスが、符号シーケンスの結託の誤りのない結果であることを検証する。実際、前記コピーのシーケンス中に所与のシンボルが存在することに基づくフィルタリング方法は、このシンボルにおけるいかなる誤りも許容しない。よって、この検証は、前記コピーのシーケンスが、誤りのない、符号シーケンスの結託の結果である場合に本フィルタリング方法が適用されることを可能にし、よって無実の個人に罪を着せる確率を限定することを可能にする。しかしながら、この限定のため、本方法は、ノイズおよびコンテンツ歪みに起因する誤りに対して、別の特許出願において提示される逐次反復的復号方法ほど堅牢でなくなる。不正コピーのシーケンス中に誤りが検出される場合には、本日出願される別の出願において本出願人によって提示される方法が有利に使用されるであろう。
【００２４】
ある個別的な実施形態によれば、不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する少なくとも一つのシーケンスの識別後、結託中の少なくとも一つの新たなシーケンスを識別するために本方法が繰り返される。よって、たとえば以前の高速復号方法から帰結するユーザーの有罪性について事前情報が存在するときは、本復号方法のパラメータが適応され、同じ有罪判定方法が使われる。この実施形態は、シーケンスのフィルタリングの場合において、二人以上の不正ユーザーの訴追を提起するという利点をもたらす。シーケンスのフィルタリングのステップに関連するこの実施形態は、より迅速に不正コピーの発生におけるソースの識別に収束する解決策をも提起することができる。
【００２５】
本発明のある個別的な特徴によれば、結託戦略がθc＝{Prob[y|t], y∈χ, t∈Tqc}と記され、ここでcは結託中に存在するシーケンスの数であり、{Prob[y|t], y∈χ, t∈Tqc}はシンボルの各リストtについて構成される、結託戦略の確率の前記ベクトルであって、χ＝{0,1,...,q−1}と記されるq元アルファベットのc個のシンボルから作られる可能なリストのTqcと記される集合のうちからの結託中に存在する諸シーケンスのシンボルの前記リストtを知っているときの、不正コピーのシーケンスy中にそのシンボルを観察する条件付き確率Prob[y|t]からなる。実際、結託戦略は、統計的領域において、確率ベクトル：結託に関与している海賊版制作者たちの全シンボルを知っているときの、ある海賊版制作者が不正コピー中に所与のシンボルを入れる条件付き確率、によってモデル化されることができる。結託戦略のモデル化は、結託に加わっている海賊版制作者の数cの知識をも含む。
【００２６】
本発明の別の個別的な特徴によれば、結託戦略のモデルの集合を生成するステップａ）において、結託戦略θcの確率の前記推定量がLblind(θc)＝Log(Prob[y|θc])と記され、ここで、Prob[y|θc]は、結託中に存在するc個のシーケンスについて結託戦略θcを知っているときの、前記不正コピー中にシーケンスyを観察する条件付き確率である。この推定量は、不正コピー中のシーケンスの解析と、q個のシンボルのアルファベットから生成されることのできるc個のシンボルのリストの集合の知識のみに依存するという利点がある。その推定は有罪判定に依存しないので、逐次反復的な計算を必要としない。さらに、ある個別的な実施形態によれば、この推定量の計算は、不正コピーのシーケンスの可能な各シンボルについて、推定量の種々の部分項を事前計算しておくことによって有利に加速され、こうして復号のパフォーマンスが改善される。
【００２７】
本発明の別の個別的な特徴によれば、結託戦略を選択するステップｂ）において、結託中にあるシーケンスxjが存在する確率のベクトルが{Prob[sjc＝1|xj, y, θc*], j∈[1,n]}と記される。ここで、sjは、シーケンスxjが結託中に存在する場合に1に等しい変数であり、Prob[sjc＝1|xj, y, θc*]は、前記不正コピーに含まれるシーケンスy、前記シーケンスxjおよび前記最も確からしい結託戦略θc*を知っているときの、前記符号のn個のシーケンスのうちc個のシーケンスの結託中における前記所与のシーケンスxjの存在の条件付き確率であり、該存在はsjc＝1によって表される。実際、有罪判定は確率ベクトル：あるユーザーが結託に参加している確率によってモデル化できる。変数sjcがこの参加を表し、ユーザーjが結託に参加していれば1に等しく、ユーザーjが無実であれば0に等しい。有罪判定は、sjc＝1となる確率の評価に基づく。この確率は、有罪の個人（最大スコア）または有罪の個人たちのグループ（ある閾値より大きいスコア）を識別することを有利に可能にする有罪性スコアを提起する。
【００２８】
さらに、本発明は、確率論的結託防止符号のシーケンスを、マルチメディア・コンテンツの不正コピーの作成に使われた前記マルチメディア・コンテンツ中に存在する前記符号の少なくとも一つのシーケンスを識別することをねらいとする前記符号の復号のためにフィルタリングする方法に関する。本方法は、前記不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する少なくとも一つのシーケンスを含む、可能な最も小さい符号シーケンスのサブグループを選択するステップを含み、前記選択は、前記符号の各シーケンスについて、選択された所与のシンボル・インデックスについて、前記符号のシーケンスのシンボルを前記不正コピーに含まれているシーケンスのシンボルと比較することによる。海賊版制作者を捜すシーケンスの数を制限することによって、実装が非常に簡単なこのフィルタリングは、復号の計算量を制限する。この本復号方法は、多数のユーザーをサポートするいかなる符号復号方法についても格別に有利である。実際、海賊版制作者によって使用される結託戦略に依存して、フィルタリングは、ユーザーのうち、つまり符号シーケンスのうちのほんの0.1%ないし20%だけを保持することを可能にする。
【００２９】
本発明のある個別的な特徴によれば、符号シーケンスをフィルタリングする前記方法は、前記コピーに含まれるシーケンスが、符号シーケンスの結託の誤りのない結果であることを検証する。実際、前記コピーのシーケンス中に所与のシンボルが存在することに基づくフィルタリング方法は、このシンボルにおけるいかなる誤りも許容しない。よって、この検証は、前記コピーのシーケンスが、誤りのない、符号シーケンスの結託の結果である場合にのみ本フィルタリング方法が適用されることを可能にする。
【００３０】
ある個別的な実施形態によれば、前記結託防止符号はタルドス符号である、
本発明は、付属の図面を参照しつつ決して限定するものではない実施形態および有利な実装によってよりよく理解され、例解されるであろう。
【図面の簡単な説明】
【００３１】
【図１】コンテンツの結託による不正コピーの作成および頒布の原理を示す図である。
【図２】タルドス符号の原理を示す図である。
【図３】コピーの結託におけるシンボルの選択の戦略を示す図である。
【図４】本発明のある実施形態に基づく、結託防止符号を復号する方法を示す図である。
【図５】本発明に基づくフィルタリング方法を示す図である。
【図６】本発明に基づく復号方法を示す図である。
【発明を実施するための形態】
【００３２】
図１は、コンテンツの結託による不正コピーの作成および頒布の原理を図的に示している。コンテンツ提供者は、たとえばインターネットを通じて、特に映画もしくはビデオ、音楽もしくはオーディオ、ビデオ・ゲーム、デジタル書籍または他の任意のデジタル文書を含むマルチメディア・コンテンツ１０１を提案する。アクティブ・フィンガープリンティングとして知られる原理によれば、コンテンツ提供者は合法的に頒布される各コピー１０２に、そのコピーのソースおよびそのユーザーを特定できるようにする一意的な通し番号１０３を挿入する。この通し番号１０３は、タルドス符号のような結託防止符号のシーケンスである。この通し番号は、一意的なユーザーへの各コピーを見かけ上同一にする透かし入れ方法を使ってコピー中に挿入される。コンテンツはブロックに切り分けられ、通し番号の諸シンボルはコンテンツ中でブロックごとに隠される。自分たちの素性を保護しながらこのコンテンツのコピーを不正に提案するため、PおよびMのような海賊ユーザーのグループが自分たちの個人的なコピーをブロックごとに組み合わせることによってコピー１０４を作成し、こうして符号シーケンスに対応しない通し番号Y １０５を作り出す。これがコピーの結託（collusion of copies）である。さらに、この通し番号Y １０５は、低域通過フィルタリングによって、透かし入れ層の復号方法に干渉するノイズを加えることによって、その不正コピーの損失のある圧縮によって、変更されることもできる。コピーの結託は、ブロックのマージによっても実現できる。この場合、ユーザーたちは自分たちのコピーを、画像またはビデオの場合はピクセルごとに、オーディオ文書の場合はサンプルごとに混合する。たとえば、前記コピーのピクセルは、各コピーのピクセルの平均、中央値（三つ以上のコピーが混合される場合）、最小値または最大値である。この場合、コンテンツ通し番号を検出するために課題を突きつけられるのは、透かしを復号する方法の堅牢さである。通し番号の、すなわち結託防止符号のこれらの修正は、ノイズ１０６によってモデル化される。ソースが求められる不正コピー１０７において検出される通し番号は、Z １０８と記される。
【００３３】
タルドス符号のような確率論的結託防止符号は、結託によって得られるコピーの起源における種々のソースを特定できるようにするために設計された。図２は、そのような符号X ２０１の構築原理を示す。この符号は、n個のシーケンス２０２{xj}j=1,nから構成される。ここで、シーケンスのインデックスjは1からnまで変わる。各シーケンス２０３ xjはユーザーjに関連付けられる。シーケンスは、m個のシンボル２０４のリストxj＝{xj,1,xj,2,...,xj,m}である。これらのシンボル２０４はq元アルファベットχ＝{0,1,...,q}に属する。図２に表されるタルドス符号の場合、このアルファベットは二元χ＝{0,1}であり、たとえばxj＝{0,1,...,0}である。
【００３４】
確率論的符号の生成は擬似ランダムである。鍵２０５{P1,P2,...,Pm}から、任意のシーケンスj∈{0,...,n}について、そのシーケンス中の任意のシンボルi∈{0,...,m}について
Prob[xj,i＝x]＝p(x,i)
となるような統計則（statistical law）pがある。
【００３５】
値p(x,i)はその符号の補助変数行列と呼ばれる行列P ２００に記憶される。この行列の行インデックスは符号のn個のシーケンスであり、列インデックスはシーケンスのm個のシンボルである。この行列は、さらに符号X ２０１のすべてのシーケンス２０２をリストするための秘密鍵としてはたらくデータベースに対応する。
【００３６】
結託防止符号は次の性質をもつ：有限個の符号シーケンスのシンボルの混合から、こうして得られた新しいシーケンスの復号によって、その混合によって使われたもとの諸シーケンスの部分集合を再び見出すことを可能にする。符号は、シーケンスの（よってユーザーの）ある最大数nおよび再び見出すことのできる混合中のもとのシーケンスの（よって不心得なユーザーの）ある最大数cについて設計される。従来技術によれば、結託戦略が何であっても、復号パフォーマンスは一様である。本発明に基づく復号方法は、復号パフォーマンスを改善するような仕方で結託戦略に対する仮設を選択することを含む。種々の結託戦略は、図３を使ってより簡単に説明されるであろう。保護されるべく試みられているマルチメディア・コンテンツはm個のブロック３０１に切り分けられる。各ブロックiは、透かし入れ技術を使って、結託防止符号のシンボルxi ３０２を隠しており、こうして、隠されたシンボルに固有のブロックiのバージョンを提案している。透かし入れの原理が十分安全でないので、ユーザーは、透かし入れ層のブロックをみつけることはできるが、挿入されたデータ項目を抽出することはできない。換言すれば、海賊版制作者は、自分たちがもっていないシンボルをマスクするブロックを作成することはできない。不正なユーザーたちはこうして、もとのコンテンツP ３０３またはM ３０４の各ブロックについて、自分たちが知っているブロックの諸バージョンの集合３０７のうちからあるバージョンを集めてくることによって、コピー３０６を構成する。海賊たちはたとえば、もとのコンテンツの諸ブロックのバージョンJ ３０５は知らない。よって、結託によってc人の不心得なユーザー３０８をまとめてグループ化し、彼らのコピーがインデックスがC＝{j1,...,jc}であるシーケンスによって同定されるとすると、所与のインデックスiのブロックyiについて、彼らはyi∈{xj1,i,...,xjc,i}のうちからの選択に制限される。よって、これは海賊たちが構成できる可能なシーケンス数に対して制限を課すことになる。
【００３７】
種々の結託戦略が考えられる：
・一様な引き抜き（uniform pulling）：結託に加わっているユーザーたちのブロックのうちから、それぞれについて等しい確率で、たとえば二つの場合には確率１／２で、あるブロッが引き出される。
・多数決（majority vote）：結託に加わっているユーザーたちのブロックのうちで他よりも多い存在によってブロックが選択される。
・少数決（minority vote）：結託に加わっているユーザーたちのブロックのうちで他よりも少ない存在によってブロックが選択される。
・ランダム投票（random vote）：結託に加わっているユーザーたちのブロックのうちでランダムにブロックが選択される。
【００３８】
すべての場合において、海賊たちに利用可能なシンボルの分布の知識が重要である。それは型の概念である。結託中に存在するc個のシーケンスのシンボルは型（type）tで分布する。型tは、q個の値のベクトルであり、結託中に潜在的に存在するc個のシーケンスjについて、シンボル・インデックスiについてのk番目の成分t(k,i)は、シンボルkに等しい可能性のあるシンボルのリスト{xj1,i,...,xjc,i}内のシンボル数を示す。q元アルファベットのシンボルのc個のシーケンスから作成される可能な型tの集合は、Tqcと記される。
【００３９】
本発明のある個別的な特徴によれば、結託戦略（collusion strategy）は、海賊たちがもっている全シンボルの型を知っているときの、海賊たちがシンボルyを不正なコピー内に入れる条件付き確率として定義される。y∈χとしてProb[y|t]と記されるこのモデル化は、特に、決定論的であれランダムであれ先述した種々の戦略の、確率論的領域における一つの可能な表現である。たとえば、多数決の場合（結託中のユーザーたちのブロックのうち他より多く存在している場合にあるブロックが選ばれる）、Prob[y|t]は、結託中の諸シーケンスのうちで同一のシンボルの最大数を有する型について最大になるであろう。本発明に基づく復号方法は、戦略がランダムであるときに特に好適であるが、所与のコピーの結託について変わるものではない。
【００４０】
本発明のもう一つの個別的な特徴によれば、結託中のあるユーザーの存在も確率論的領域においてモデル化される。変数sjを、シーケンスjが結託で使われたマルチメディア・コンテンツ内に存在していると同定される場合に値1をとり、そうでない場合に値0をとるものと定義する。結託におけるあるユーザーの存在は、確率Prob[sj＝1]によってモデル化される。
【００４１】
本発明に基づく復号方法は、結託に対する耐性の問題のこの二重モデル化に基づく。実際、結託戦略について何の仮設も立てない一様戦略として知られる有罪判定戦略について従来技術が教示することとは逆に、本発明に基づく復号方法は、不正コピーを作成するために海賊のグループによって使用された戦略を決定する。さらに、別の特許出願によって教示される逐次反復的方法とは逆に、本発明に基づく復号方法は、可能なモデルの集合のうちからの結託モデルの確率に基づく二重選択によって、使われた結託戦略を決定する。図６は、本発明に基づく復号方法を示している。不正コピー（６０１）に含まれるシーケンスおよび諸符号シーケンス（６０２）から、結託防止符号の復号方法は、不正コピーの起源における諸ソースを決定する（６０５）。本方法は、一様方法と呼ばれる有罪判定方法によって教示されるソースの特定ステップ（６０４）に加えて、結託戦略の選択ステップ（６０３）をもつ。この結託戦略は、不正コピーを作成するために海賊たちによって実行された選択、たとえば一様な引き抜き、多数決、少数決またはランダム投票を表す。
【００４２】
図４は、n個のシーケンス{xj}j=1,nから構成される確率論的結託防止符号Xについての高速復号方法であって、マルチメディア・コンテンツの不正コピーの作成に使われたマルチメディア・コンテンツ内に存在する少なくとも一つの符号シーケンスXの識別を、結託戦略のモデルの集合のうちからそのコピーを構成するために使われた結託戦略を選択することから行うことをねらいとする方法の実施形態の一つを示している。作成されるモデルの集合は二つのパラメータに依存する：結託における海賊の数と、結託に存在する諸シーケンスのシンボルのリストである。結託中の海賊の数cはcminからcmaxまでの間で変わる。結託中のシーケンス数に対する仮設が可能でない場合には、cminは1に固定され、cmaxは符号の構築の間に考慮された裏切り者の最大数を超えてはならない。最初のステップ４０１の間に、不正コピーに含まれるシーケンスyを知っている場合の結託戦略の確率の推定量が計算される。この推定量は、θc＝{Prob[y|t], y∈χ, t∈Tqc}と記される結託戦略のモデル化を使う。ここでcは結託中に存在するシーケンス数、{Prob[y|t], y∈χ, t∈Tqc}は、シンボルの各リストtについて構成される、結託戦略の確率のベクトルであって、χ＝{0,1,...,q−1}と記されるq元アルファベットのc個のシンボルから作られる可能なリストのTqcと記される集合のうちからの結託中に存在する諸シーケンスのシンボルのリストtを知っているときの、不正コピーのシーケンスy中にそのシンボルを観察する条件付き確率Prob[y|t]からなる。このモデルを考慮に入れると、所与の結託戦略について不正コピー中にシーケンスyを観察する事後確率は、
Prob[y|θc]＝Πi∈[1,m]Prob[y(i)|θc]＝Πi∈[1,m](Σti∈TcqProb[y(i)|ti]Prob[ti])
である。ここで、iは1からmまで変わるシンボル・インデックスであり、結託中のc個のシーケンスについて、シンボル・インデックスiについてのtiは、符号の各シンボルについて、q個のシンボルからなるアルファベット上のc個のシンボルのリストから構築されるベクトルである。最も確からしい結託戦略は、シーケンスyを観察するためのその結託戦略の事後確率を最大にするものである。結託戦略θcの確率の推定量はLblind(θc)＝Log(Prob[y|θc])と記される。ここで、Prob[y|θc]は、結託中に存在するc個のシーケンスについて結託戦略θcを知っているときの、不正コピー中にシーケンスyを観察する条件付き確率である。この推定量は、シーケンスy ４０８、符号のシンボルχ＝{0,1,...,q−1} ４０９および秘密鍵{P1,P2,...,Pm} ２０５のみに依存する。
【００４３】
ある変形実施形態によれば、不正コピー中にシーケンスyを観察するための所与の結託戦略の事後確率の種々の項Prob[y(i)|ti].Prob[ti]は、可能な各シンボルy(i)およびq個のシンボルのアルファベット中のc個のシンボルの各リストtiについて事前計算される。事前計算は、結託戦略θcの確率の推定量の計算ステップを加速し、よって復号のパフォーマンスを改善する。
【００４４】
ステップ４０３では、結託におけるシーケンスの数cの各推定について、結託中の諸シーケンスのシンボルのリスト上で、第一の選択が、結託戦略の、つまりこのリストの最大確率に基づいて行われる。結託中のc個のシーケンスの確率の推定量を最大にする結託戦略は、θc*と記される。こうして、このステップ４０３ののち、結託中のシーケンスの数がcであるとすると、結託戦略はθc* ４１１である。
【００４５】
ステップ４０４は、結託戦略θc*の仮設を形成する間に、各ユーザーについての有罪性スコアの計算を含む。よって、{Prob[sjc＝1|xj, y, θc*], j∈[1,n]}と記される、結託におけるシーケンスxjの存在の確率４１２のベクトルが計算される。sjは、シーケンスxjが結託中に存在する場合に1に等しい変数であり、Prob[sjc＝1|xj, y, θc*]４１２は、不正コピーに含まれるシーケンスy、シーケンスxjおよび最も確からしい結託戦略θc*を知っているときの、符号のn個のシーケンスのうちc個のシーケンスの結託中における所与のシーケンスxjの存在の条件付き確率である。その存在はsjc＝1と記される。この確率ベクトルは、結託戦略θc* ４１１が与えられたときのユーザーたちの有罪性スコアを表す。この確率ベクトルは、不正コピー中にシーケンスyを観察するための所与の結託戦略の事後確率Prob[y|θc]４０９で構成される。結託戦略のモデルの確率計算の二つのパラメータの一つである。これら二つのパラメータは、結託に荷担している海賊の数を、混合によってそのコピーのシーケンスを作成する海賊の数と相関させることを可能にする。Q(θc*) ４１３と記される結託戦略のモデルの確率の計算がステップ４０５において実行される。ステップ４０６の間に、モデルの集合のうちからの第二の選択が、結託中のシーケンスの数ならびにQ(θc*) ４１３と記されるモデルの確率を最大化する関連付けられた結託戦略、つまりθc** ４１４の決定を可能にする。つまり、θc**＝argmaxθQ(θc*)である。
【００４６】
最後に、ステップ４０７において、ユーザーたちの有罪性スコアすなわちシーケンスxjが結託中に存在する確率４１２のベクトルの計算が、ステップａ）４０１、４０３およびｂ）４０４、４０５、４０６の確率基準に従った選択によって得られた結託戦略θc**に従って更新される。その際、この同じステップ４０７は、不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する符号の少なくとも一つのシーケンスを決定する。本発明の諸実施形態によれば、少なくとも二つの基準によって結託中に存在するシーケンスを決定できる。第一の基準は、結託におけるシーケンスの存在の確率のベクトルの値のうちからの、所与のシーケンスについての確率の最大値Prob[sjc＝1|xj, y, θc**]である。有利なことに、この基準は、比較的低い偽警報確率の誤りで、海賊を特定することを可能にする。第二の基準は、結託におけるシーケンスの存在の確率のベクトルの値のうちからの、あるグループの諸シーケンスjのそれぞれについてある閾値Sより大きな確率の値Prob[sjc＝1|xj, y, θc**]である。たとえば、この基準は、有利なことに、この閾値が１／２に固定される場合、有罪である確率が無罪である確率より大きいユーザーを訴追することを可能にする。有利には、この閾値は、偽警報または見逃し条件を満たすよう決定されることもできる。本発明に基づく復号に従って、無実の個人と有罪の個人のスコアが広く分離されることを強調することが特に有益である。これは、有罪である個人がより確信をもって（すなわち、偽警報またはミスの高められた確率について）訴追されることを可能にし、あるいはコピーの結託の諸ソースの特定のために必要とされる符号の長さを短縮することを可能にする。
【００４７】
ある実施形態によれば、復号方法は、諸シーケンスをフィルタリングするステップ４０２を含むことができる。このステップは、符号のシーケンスの数nが、よって結託仮設が構築されるシンボル数が制限されることを可能にする。このフィルタリング・ステップは、ステップ４０１および４０４のデータ４０９に対して介入する。さらに、フィルタリングのある復号方法のパラメータも適応されるが、同じ有罪判定方法が使われる。フィルタリング方法において選択されたシンボルのインデックスi*が記されるとすると、有罪判定方法は、このシンボルを無視しなければならない。こうして、符号の諸シーケンスはm−1シンボルの長さであり、考慮されるべきコピーのシーケンスはy′と記され、シンボルy(i*)が除去されたyに等しい。このフィルタリング・ステップに関連する方法は、図５においてより広く例解される。
【００４８】
本発明に基づく復号方法は、たとえば以前の高速復号方法から帰結する、ユーザーの有罪性についての事前の知識を考慮に入れることができるという利点をも呈する。復号方法のパラメータは適応され、同じ有罪判定方法が使われる。不正コピーの作成に使われたマルチメディア・コンテンツ中に存在するシーケンスがxlと記されるとすると、シーケンスxlを条件とする、結託中でのシーケンスの存在の確率のベクトルはProb[sjc|xj, xl, y, θ c**]と書かれる。
【００４９】
図５は、シーケンス・フィルタリング方法の実施形態の一つを示す。このフィルタリング方法は、海賊たちが、彼らのコピーをブロックごとに混合することによって不正コピーを作成する間に、シンボルを生成することはできないという仮設に基づく。符号のシーケンスのm個のシンボルのうちから巧妙に選択されたシンボル・インデックスiについて、不正コピーのシンボルy(i)は、諸シーケンスのうち、同じインデックスにおいてこの同じシンボルをもつシーケンスからである。問題は、その中から海賊を捜すことができるできるだけ小さいユーザーのグループであって、よってフィルタリングに従う復号アルゴリズムの計算量を低下させるグループを構築できるようにするインデックスiを選択することである。図２に示されるように、確率論的結託防止符号は、鍵２０５と、任意のシーケンスj∈{0,...,n}についてシーケンス中の任意のシンボルi∈{0,...,m}についてProb[xj(i)＝x]＝p(x,i)のような統計則pとから構築される。この統計則は、不正コピーのシーケンス５０１の所与のインデックス・シンボルiについて、このシンボルを観察する確率５０２を計算することを可能にする。タルドス符号のような、また図５に表されるような二元符号の場合、シンボルは値(0,1)をとり、p1がインデックス・シンボルiについて「1」にあるシンボルを観察する確率であるとすると、1−piは「0」におけるシンボルを観察する確率である。というのも、Prob[x(i)＝0]＋Prob[x(i)＝1]＝1だからである。復号されるシーケンスy ５０１について最大数のユーザーがフィルタリングされることを可能にするシンボル・インデックスi* ５０４の選択は、復号されるシーケンス５０１においてこのインデックスについてのこのシンボルを観察する確率p(y(i),i)が最低になるようにするものである。i∈[1,m]として、i*＝argmin p(y(i),i) ５０３である。よって、フィルタリングに続くステップは、i*インデックス・シンボルが不正コピーのシーケンスのi*インデックス・シンボルに等しくなるxM(i*)＝xJ(i*)＝y(i*)のような符号のシーケンスM ５０６およびJ ５０７の選択を含む。なお、図２に示した例において、結託に荷担したシーケンスはシーケンスP ５０５およびM ５０６であり、フィルタリングによって保持されるシーケンスはシーケンスM ５０６およびJ ５０７である。このように、フィルタリングは、サブグループが結託中の少なくとも一つのシーケンス、シーケンスM ５０６を含むが結託中の全部のシーケンスは含まない、たとえばシーケンスP ５０７は含まないときにサブグループを選択することを可能にする。このフィルタリング方法は、こうして、復号方法が結託内のシーケンスを特定することを許可するが、シーケンスのグループをではない。事前選択によって保持されるシーケンス５０７のサブグループ内に、結託に荷担した二つ以上のシーケンスがあった保証はないからである。
【００５０】
さらに、このフィルタリング方法は、シーケンスyが結託における諸シーケンスのシンボルの混合の誤りのない結果である場合にのみ機能する。ある個別的な実施形態によれば、フィルタリングの混合は、マーキング仮設（marking hypothesis）、つまりシーケンスyがシンボルに対する誤りを含むという仮設の検証ステップを含む。
【００５１】
結託戦略に応じて、フィルタリング方法は、多数決または少数決の場合には符号の諸シーケンスのうちの0.1%ないし一様な引き抜きの場合には符号のシーケンスの20%しか保持しない。実装が非常に簡単なこのフィルタリング方法は、結託防止符号復号方法の、特に本発明に基づく復号方法の計算量対パフォーマンス比の改善を可能にする。
【００５２】
ある有利な実施形態によれば、結託防止符号は、二元タルドス符号である。当該符号が構成によって復元することを可能にするシーケンスの最大数は、cと記される。こうして、q＝2であり、c＋1個の型が可能である。型は対(σ,c−σ)と記すことができる。ここで、σは、海賊が所有する「1」であるシンボルの数である。σと記される海賊が所有する「1」であるシンボルの数は0からcまでの間で変わる。すると、確率ベクトルθは、推定されるc′人の海賊版制作者について、{Prob[y＝1|σ＝0], Prob[y＝1|σ＝1],...,Prob[y＝1|σ＝c′]}∈[0,1]c′+1と書かれる。このベクトルは、それぞれ、結託の諸シーケンスの0個のシンボルが「1」であること、結託の諸シーケンスの一つのシンボルが「1」であることないし結託の諸シーケンスのc′個のシンボルが「1」であることを知っているときの、不正コピーのシーケンス中に「1」を観察する確率から構築される。透かし入れ層に対する誤り検出なしでは、海賊たちは新しいシンボルを作成できないので、不正コピー中のシンボルは海賊たちの「1」である諸シンボルまたは海賊たちの「0」である諸シンボルからであるので、Prob[y＝1|σ]＋Prob[y＝1|c′−σ]＝1であることも等しく考慮に入れるべきである。透かし入れ層に対する誤り検出なしでは、海賊たちは新しいシンボルを作成できないので、不正コピーのシーケンスは、海賊のシンボルのどれも「1」でない場合には「1」であるシンボルを含むことができず（つまりProb[y＝1|0]＝0）、逆に海賊のシンボルの全部が「1」である場合には「1」であるシンボルを含む（Prob[y＝1|c′]＝1）ことも等しく考慮に入れるべきである。
【００５３】
当然ながら、本発明は上記で述べた実施形態に限定されるものではない。
【００５４】
特に、本発明は、タルドス符号とは異なる結託防止符号にも適合する。
【符号の説明】
【００５５】
１０１ マルチメディア・コンテンツ
１０２ マルチメディア・コンテンツ
１０３ シーケンス
１０４ マルチメディア・コンテンツ
１０５ 不正コピーのシーケンス（PとMの結託）
１０６ ノイズ
１０７ マルチメディア・コンテンツ
１０８ 不正コピーの検出されるシーケンス
２００ 補助変数行列
２０１ 符号X
２０２ シーケンス
２０３ シーケンスJ
２０４ シンボル
２０５ 符号の鍵
３０１ マルチメディア・コンテンツをなすM個のブロック
３０２ シンボル
３０３ シーケンスP
３０４ シーケンスM
３０５ シーケンスJ
３０６ 不正コピーのシーケンスY
３０７ あるブロックの諸バージョンの集合
３０８ 結託に関与しているc個のシーケンス
４０２ シーケンスのフィルタリング
４０３ θc*の選択 θc*＝argmaxθc Lblind(θc)
４０４ θc*に基づいて有罪性スコアを計算 Prob[sjc＝1|xj,y,θc*]
４０５ Q(θc*)の計算
４０６ 結託戦略θc**の選択 θc**＝argmaxθ Q(θc*)
４０７ 結託に加わっている少なくとも一つのシーケンスを同定
４０８ シーケンスy
４０９ 符号のシンボルχ＝{0,1,...,q−1}
４１０ 確率Prob[y|θc]
４１１ 結託戦略θc*
４１２ 結託にシーケンスxjが加わっている確率
４１３ 結託戦略のモデルの確率Q(θc*)
４１４ モデルの確率を最大化する結託戦略θc**
４１５ sj＝1（シーケンスxjが結託に関与している）
５０１ 不正コピーのシーケンス
５０２ シンボルを観測する確率
５０３ シンボルを観察する確率p(y(i),i)が最低になるシンボル・インデックスi*
５０４ 最大数のユーザーがフィルタリングされることを可能にするシンボル・インデックスi*
５０５ シーケンスP
５０６ シーケンスM
５０７ シーケンスJ
６０１ 不正コピー
６０２ コード
６０３ 結託戦略の選択
６０４ 結託に加わっているソースの同定
６０５ 不正コピーの出所のソース
【技術分野】
【０００１】
本発明は、不正コピーに対するデジタル・コンテンツの保護および不正コピーの出所におけるソースの特定という概括的な領域に関する。より詳細には、本発明は、デジタル・コンテンツの不正コピーの起源における（at the origin）一つまたは複数のソースを特定することをねらいとする確率論的結託防止符号（probabilistic anti-collusion code）のための高速復号方法に関する。
【背景技術】
【０００２】
たとえば音楽、映画、写真およびビデオ・ゲームのようなデジタル・コンテンツの、不正コピーの作成および頒布に対する保護は、メディアおよびエンターテインメント産業にとって、特にマルチメディア・コンテンツの提供者および著作権保有者にとって重要な問題である。
【０００３】
この目的のため、不正なコンテンツの作成および頒布を克服するためにさまざまな解決策が知られている。データの暗号化に基づく解決策は不正コピーの実際の作成および頒布を防止する。正当なコピーのトレーサビリティ〔追跡可能性〕に基づく抑止的な解決策は、不正コピーのソースを特定することを可能にする。本発明の領域は、この後者の抑止的な解決策の範疇に属する。
【０００４】
不正コピーの起源におけるソースの特定には、数多くの応用がある。たとえば、ビデオ・オン・デマンド・サーバーは、異なる顧客に対して同じコンテンツの個人的なコピーを配信する。海賊と呼ばれる一部の不心得な顧客がこのコンテンツのコピーを、たとえばP2P（ピアツーピア［Peer-To-Peer］ネットワーク上で）不正に再頒布する。著作権保有者は海賊版制作者を特定したい。そのために、ビデオ・オン・デマンド・サーバーは、ビデオ透かし入れ技術を使って各コピーに一意的な識別子を挿入し、これにより一見同一に見えるが異なるコピーを多数生産する。こうして、不正コピー中のコンテンツ識別子により、この不正コピーのソース、よって海賊が特定できる。しかしながら、認識されないために、複数の海賊のグループが、自分たちの異なるコピーを混合することによって不正コピーを構築することによって、識別子を変更することができる。これがコピーの結託（collusion of copies）である。最後に、この同じ海賊のグループは、特に不正コピーを損失のある圧縮にかけることによって、不正頒布されるコピーの識別子に誤りを導入し、無実の人々に罪が着せられたり海賊の素性を隠蔽したりしようと試みることができる。
【０００５】
この目的のため、透かし入れによってコピーに挿入される識別子を、結託防止符号（anti-collusion code）のシンボルのシーケンスとすることが知られている。D・ボネーおよびJ・ショーのような暗号学者は、非特許文献１において、有限個の符号シーケンスの混合の復号によって、そのコピーを作成するために使われた結託戦略が何であっても、結託のために使われたもとのシーケンスの部分集合を特定することを可能にする最短長の最適符号の存在を示している。
【０００６】
既知の広く使われているそのような最適符号は、タルドスによって2003年に非特許文献２において提案された。この確率論的符号は、用いられている結託戦略が何であっても一様に効率的な復号システムのパフォーマンス基準に応答する。それは、ユーザー数（符号におけるシーケンス数に対応）、不心得なユーザーの最大数（符号における、識別が試みられるシーケンスの数に対応）、アルファベット中のシンボル数、偽警報確率（結託の一員でなかったユーザーに罪を着せる事実）およびミス確率（結託の一員であったユーザーを特定しない事実）に依存するその長さによって特徴付けられる。
【０００７】
フィリップスは、非特許文献３において、偽警報の確率をある閾値ε未満に維持したければ、タルドスのもののような二元符号について、符号長は2π2c2log(nε-1)より大きくなければならないことを示した。ここで、cは不心得な顧客の数を表し、nは全顧客数を表す。フィリップスはまた、（非特許文献４において）符号長を最短にする発想に従って、タルドス符号を任意の大きさのアルファベット上で設計された符号に一般化することにも取り組んだ。
【０００８】
これらの解決策の技術的課題は、符号の長さである。他方、透かし入れ技術を使ってマルチメディア・コンテンツ中に隠すことのできるシンボル数は限られており、符号の長さは、識別されるべきコンテンツのサイズと適合する範囲内に留まる必要がある。他方、復号の計算量は符号の長さに直接関係し、復号装置の計算パワーおよびメモリ・サイズ手段の制限は最小限に留まる必要がある。さらに、結託防止符号の長さは、特にビデオ・オン・デマンド・サービスのサービス・ユーザーおよび潜在的に不心得なユーザーの増え続ける数を扱うために増加する。
【０００９】
本願と同じ出願人によって同日に出願される第一の特許出願では、そのような符号を復号する逐次反復的な方法であって、結託中に存在する諸シーケンスの識別ステップに関連付けられた結託戦略の推定ステップを含む方法が提案された。この方法は、符号復号パフォーマンスを改善することおよび伝送におけるノイズによってまたはコンテンツの変換（transformation）によって導入される誤りに対して耐性があることという利点を呈する。その復号パフォーマンスは、結託における諸シーケンスを識別するために使われる符号の長さを制限することを可能にし、よって前記の技術的課題に対する解決策を提供する。しかしながら、この復号方法は、その逐次反復的な方法のため、かなりの計算パワーおよびメモリ・サイズ手段を要求する。したがって、第二の技術的課題は、多数のシーケンスをサポートする符号のための使用を不可能にすることがありうる逐次反復的な復号の複雑さである。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】D. Boneh and J. Shaw, "Collusion-secure fingerprinting for digital data", "IEEE Transactions on Information Theory", vol. 44, pp. 1897-1905, 1998年9月
【非特許文献２】Tardos, "Optimal probabilistic fingerprint codes", "Proc. of the 35th annual ACM symposium on theory of computing", pp.116-125, San Diego, CA, USA, 2003年, ACM
【非特許文献３】B. Skoric, T. Vladimirova, M. Celik, and J. Talstra, "Tardos fingerprinting is better than we thought", "IEEE Transactions on Information Theory", vol. 54, pp. 3363-3676, 2008年8月
【非特許文献４】B. Skoric, S. Katzenbeisser and M. Celik, "Symmetric Tardos fingerprinting codes for arbitrary alphabet sizes", "Designs, Codes and Cryptography", vol. 46(2):137-166, 2008年2月
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、タルドス符号のような確率論的結託防止符号のパフォーマンスを、該符号の生成ではなく復号において改善しつつ、復号演算の計算量を制限することによって、従来技術の欠点の少なくとも一つを克服することである。従来技術では、復号パフォーマンスは、不心得なユーザーたちの結託戦略が何であっても保証される。本発明の発想は、可能な結託戦略について仮設を立てて、それらの仮設のうちから符号のパフォーマンスを改善するよう最も確からしい戦略を選択するというものである。さらに、確率計算は不正コピー中のシーケンスおよび符号シンボルのみに依存するので、この選択は、実装するのが比較的簡単である。
【００１２】
さらに、本発明は、諸符号シーケンスのうちから、復号方法が結託中でのその存在を識別しようとする符号シーケンスをフィルタリングする方法を提案する。有利なことに、このフィルタリング方法は、復号の計算量を低下させる。
【課題を解決するための手段】
【００１３】
この目的のため、本発明は、マルチメディア・コンテンツの不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する符号の少なくとも一つのシーケンスを識別することをねらいとする確率論的結託防止符号のための復号方法であって、結託戦略モデルの集合のうちから前記コピーを構築するために使われた結託戦略を選択するステップを有する方法に関する。実際、海賊のグループは、不正コピーを作成するために、彼らのコピーをブロックごとに混合することによって、種々の結託戦略を使用できる。例として、一様な抽出、多数決、少数決、ランダム投票を挙げることができる。本発明に基づく復号方法は、戦略がランダムであるときおよび戦略が、諸コピーの所与の結託について変わらないときに特に好適である。結託戦略について何の仮設も立てない一様戦略として知られる訴追戦略について従来技術が教示することとは逆に、本発明に基づく復号方法は、不正コピーを作成するために海賊のグループによって使用された戦略を決定する。この知識は、有利なことに、所与の長さの符号について、復号方法をより効率的にする。それにより、無実の人に罪を着せる所与の確率について、符号シンボルの数を減らすことが可能になる。さらに、不正コピーのシーケンスおよび結託に含まれる諸シーケンスの両方を解析することによって結託戦略が推定される逐次反復的な復号方法を提案する本出願人によって本日出願された前記特許出願によって教示されることとは逆に、本発明に基づく結託戦略の推定は、不正コピー中のシーケンスの解析のみに基づく。精確さは下がるものの、この推定は逐次反復的方法に頼らず、よって本発明に基づく復号方法の複雑さを低減するという利点がある。逐次反復的方法とは逆に、本発明に基づく復号方法は、コンテンツ提供者サービスのますます増加する数のユーザーまたはますます増加する数の海賊版制作者のために必要とされるますます増加する数の符号シーケンスに効率的に対処することを可能にする。
【００１４】
本発明のある個別的な特徴によれば、結託戦略は、結託中に存在するいくつかのシーケンスについて、結託中に存在する諸シーケンスのシンボルのリストを知っての不正コピー中にそのシンボルを観察する条件的確率の、結託中に存在する諸シーケンスのシンボルの各リストについて構築される結託戦略の諸確率のベクトルによって表現される。この表現は、結託戦略が不正コピーのシーケンスおよび結託中の諸シーケンスの両方を解析することによって推定される本出願人によって本日出願された前記特許出願において提示される方法の結託戦略の推定に対する仮設を使う。実は、結託戦略は、統計的領域において、確率ベクトル：結託に荷担している海賊たちの全シンボルを知っているときにある海賊が不正コピー中に所与のシンボルを入れる条件付き確率、によってモデル化できる。結託戦略はまた、結託中の海賊の数の知識をも含む。
【００１５】
本発明のもう一つの個別的な特徴によれば、結託戦略のモデルの集合は、結託中に存在するシーケンスの数の各推定について、最も確からしい結託戦略を含む。実際、この集合の生成およびその確率に基づく結託戦略の選択は、可能なあらゆる結託事例を、不正コピー中のシーケンスのみから推定することによって、逐次反復的方法を克服することを可能にする。可能なあらゆる結託事例は、結託中のシーケンスの数および結託中に存在する諸シーケンスのシンボルのリストによって設定されるパラメータをもつ。
【００１６】
本発明のもう一つの個別的な特徴によれば、本発明は：
ａ）結託戦略のモデルの集合を生成する段階、つまり、
ｉ．結託中のシーケンスの数の各推定について、結託中に存在する諸シーケンスのシンボルの各リストについて、不正コピー中に含まれるシーケンスを知っての結託戦略の確率の推定量の計算、
ｉｉ．結託中のシーケンスの数の各推定について、結託戦略の確率の推定量を最大にする結託戦略の事後的な選択；
ｂ）結託戦略のモデルの集合のうちから結託戦略を選択する段階、つまり、
ｉ．最も確からしい結託戦略に関連付けられた結託中のシーケンスの数の各推定について、結託中にあるシーケンスが存在する確率のベクトルであって、符号の各シーケンスについての、不正コピー中に含まれるシーケンス、所与のシーケンスおよび最も確からしい結託戦略を知っているときに結託中に前記所与のシーケンスが存在する条件付き確率から構築されるベクトルの計算、
ｉｉ．最も確からしい結託戦略に関連付けられた結託中のシーケンスの数の各推定について、結託中にあるシーケンスが存在する諸確率と、不正コピー中に含まれるシーケンスを知っているときの結託戦略の確率との前記ベクトルから、結託戦略のモデルの確率の計算、
ｉｉｉ．結託戦略のモデルの前記集合のうちからの、結託戦略の前記モデルの確率を最大にする、前記最も確からしい結託戦略に関連付けられた結託中のシーケンスの数の選択；
ｃ）不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する前記符号の少なくとも一つのシーケンスを、ステップｂ）で推定された結託戦略の前記モデルを知っているときの前記シーケンスの存在の条件付き確率から、識別するステップを含む。
【００１７】
実際、結託戦略の確率のベクトルの形のモデル化から、結託戦略の確率の推定量が定義される：それは、不正コピーに含まれるシーケンスを知っているときの、ある結託戦略の事後確率である。したがって、海賊版制作者の所与の数について最も確からしい結託戦略は、結託戦略のこの事後確率を最大にする結託戦略である。有利には、この第一の基準は、所与の結託に関与する海賊版制作者の数についてのある推定値について、この数のシーケンスについて最も確からしい戦略を選択し、よって実施形態の一つに基づいて結託戦略のモデルの集合を生成することを可能にする。
【００１８】
さらに、第二のステップは、最も確からしいモデルが選択されることを可能にする。つまり、最も確からしい結託戦略に関連付けられた結託中のシーケンスの数である。このステップは、モデルの確率の計算のために、結託戦略の確率に加えて、結託プロセスに加わったユーザーの有罪判定、すなわち識別を使う。有罪判定は、確率ベクトルによってモデル化される：あるユーザーが結託に参加している確率である。有利なことに、これら二つの確率の使用により、結託戦略のモデルのシーケンスの数と有罪判定を相関させることができる。こうして生成されたモデルの集合のうちから結託戦略を選択することにより、本復号方法は、逐次的方法ほど計算パワーにおいて貪欲でない。
【００１９】
最後に、最終ステップにおいて、ステップｂ）で選択された結託戦略を使って有罪判定が実行される。結託に関与している確率は、不正ユーザーと正当なユーザーとの間で明確に異なる。この分離により、本発明に基づく復号方法は、そのパフォーマンス対計算量比のため、特に別の特許出願で教示される逐次的方法と比べて、非常に興味深いものとなる。一様有罪判定方法（つまり、結託戦略についての仮設を立てることなく動作する方法）に対して効率的である復号方法を提案することにより、本発明は、海賊版制作者の識別のために必要とされる符号の長さを短縮することも可能にする。
【００２０】
本発明の別の個別的な特徴によれば、最も確からしい結託戦略の選択後、符号のあるシーケンスが不正コピーの作成に使われたマルチメディア・コンテンツ中に存在するとして識別されるのは、不正コピーに含まれるシーケンス、前記シーケンスおよびステップｂ）で選択された結託戦略のモデルを知っているときに結託中に前記シーケンスが存在する条件付き確率の値が最大であるときである。この特徴により、有罪である確率が最も高いユーザーを訴追することが可能になる。
【００２１】
本発明の別の個別的な特徴によれば、最も確からしい結託戦略の選択後、符号シーケンスのグループが不正コピーの作成に使われたマルチメディア・コンテンツ中に存在するとして識別されるのは、不正コピーに含まれるシーケンス、前記グループの前記シーケンスおよびステップｂ）で選択された結託戦略のモデルを知っているときに前記グループの諸シーケンスのそれぞれについて前記条件付き確率の値がある閾値Sより大きいときである。この特徴は、たとえば、閾値が１／２に固定される場合、有罪である確率が無罪である確率より大きいユーザーを訴追することを可能にする。さらに、無実の個人の確率と有罪の個人の確率との間に明確な分離が観察されることを強調しておくことが有益である。この特徴は、結託防止符号の復号方法のパフォーマンス基準である。有利には、この閾値はまた、無実の個人に罪を着せる確率を減らすように、あるいは海賊版制作者を見逃す確率を減らすように決定されることができる。よって、不正コピーの起源のソースを識別しようとする著作権保有者またはコンテンツ提供者は、単一のユーザーを高い確度をもって追跡することを選ぶか、あるいは結託の発生に関与していた可能性が高いユーザーのグループを追跡することを選ぶことができる。有利には、これら最後の二つの特徴は、コンテンツ提供者またはデータベース管理者のようなかかる解決策の顧客の、「裏切り者追跡（traitor tracing）」のようなさまざまな期待に応えることを可能にする。
【００２２】
本発明の別の個別的な特徴によれば、本復号方法は、符号シーケンスをフィルタリングするステップを含む。フィルタリングするステップは、不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する少なくとも一つのシーケンスを含む可能な最も小さい符号シーケンスのサブグループを選択することを含み、前記選択は、各符号シーケンスについて、選択された所与のシンボル・インデックスについて、前記符号シーケンスのシンボルを不正コピーに含まれているシーケンスのシンボルと比較することによる。海賊版制作者を捜す範囲となるシーケンスの数を制限することによって、実装が非常に簡単なこのフィルタリングは、復号の計算量を制限し、よって本復号方法を、多数のユーザーをサポートする符号について格別に有利にする。実際、海賊版制作者によって使用される結託戦略に依存して、フィルタリングは、ユーザーのうち、つまり符号シーケンスのうちのほんの0.1%ないし20%だけを保持することを可能にする。したがって、このフィルタリングは、特に計算パワーに貪欲なステップａ）およびｂ）における計算から、少なくともユーザーの５分の４を解放することができる。しかしながら、このフィルタリングの負の側面は、有罪判定を単一の海賊版制作者に限定するということ、および不正コピー中のシーケンスに誤りがあってはならないということである。実際、本フィルタリング方法は、不正コピーのシーケンス中に誤ったシンボルがなければ、サブグループが、不正コピーのシーケンス中で選択されたインデックス・シンボルを提供した少なくとも一つの海賊シーケンスを含むことを保証するが、２つ以上あることを保証するものは何もない。有利に、高速復号のこの実施形態は、最初の解析として使用されることができ、その後、追加的な解析において従来技術によって教示される最適復号によって検証されることができる。
【００２３】
本発明の別の個別的な特徴によれば、符号シーケンスをフィルタリングする前記ステップは、前記コピーに含まれるシーケンスが、符号シーケンスの結託の誤りのない結果であることを検証する。実際、前記コピーのシーケンス中に所与のシンボルが存在することに基づくフィルタリング方法は、このシンボルにおけるいかなる誤りも許容しない。よって、この検証は、前記コピーのシーケンスが、誤りのない、符号シーケンスの結託の結果である場合に本フィルタリング方法が適用されることを可能にし、よって無実の個人に罪を着せる確率を限定することを可能にする。しかしながら、この限定のため、本方法は、ノイズおよびコンテンツ歪みに起因する誤りに対して、別の特許出願において提示される逐次反復的復号方法ほど堅牢でなくなる。不正コピーのシーケンス中に誤りが検出される場合には、本日出願される別の出願において本出願人によって提示される方法が有利に使用されるであろう。
【００２４】
ある個別的な実施形態によれば、不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する少なくとも一つのシーケンスの識別後、結託中の少なくとも一つの新たなシーケンスを識別するために本方法が繰り返される。よって、たとえば以前の高速復号方法から帰結するユーザーの有罪性について事前情報が存在するときは、本復号方法のパラメータが適応され、同じ有罪判定方法が使われる。この実施形態は、シーケンスのフィルタリングの場合において、二人以上の不正ユーザーの訴追を提起するという利点をもたらす。シーケンスのフィルタリングのステップに関連するこの実施形態は、より迅速に不正コピーの発生におけるソースの識別に収束する解決策をも提起することができる。
【００２５】
本発明のある個別的な特徴によれば、結託戦略がθc＝{Prob[y|t], y∈χ, t∈Tqc}と記され、ここでcは結託中に存在するシーケンスの数であり、{Prob[y|t], y∈χ, t∈Tqc}はシンボルの各リストtについて構成される、結託戦略の確率の前記ベクトルであって、χ＝{0,1,...,q−1}と記されるq元アルファベットのc個のシンボルから作られる可能なリストのTqcと記される集合のうちからの結託中に存在する諸シーケンスのシンボルの前記リストtを知っているときの、不正コピーのシーケンスy中にそのシンボルを観察する条件付き確率Prob[y|t]からなる。実際、結託戦略は、統計的領域において、確率ベクトル：結託に関与している海賊版制作者たちの全シンボルを知っているときの、ある海賊版制作者が不正コピー中に所与のシンボルを入れる条件付き確率、によってモデル化されることができる。結託戦略のモデル化は、結託に加わっている海賊版制作者の数cの知識をも含む。
【００２６】
本発明の別の個別的な特徴によれば、結託戦略のモデルの集合を生成するステップａ）において、結託戦略θcの確率の前記推定量がLblind(θc)＝Log(Prob[y|θc])と記され、ここで、Prob[y|θc]は、結託中に存在するc個のシーケンスについて結託戦略θcを知っているときの、前記不正コピー中にシーケンスyを観察する条件付き確率である。この推定量は、不正コピー中のシーケンスの解析と、q個のシンボルのアルファベットから生成されることのできるc個のシンボルのリストの集合の知識のみに依存するという利点がある。その推定は有罪判定に依存しないので、逐次反復的な計算を必要としない。さらに、ある個別的な実施形態によれば、この推定量の計算は、不正コピーのシーケンスの可能な各シンボルについて、推定量の種々の部分項を事前計算しておくことによって有利に加速され、こうして復号のパフォーマンスが改善される。
【００２７】
本発明の別の個別的な特徴によれば、結託戦略を選択するステップｂ）において、結託中にあるシーケンスxjが存在する確率のベクトルが{Prob[sjc＝1|xj, y, θc*], j∈[1,n]}と記される。ここで、sjは、シーケンスxjが結託中に存在する場合に1に等しい変数であり、Prob[sjc＝1|xj, y, θc*]は、前記不正コピーに含まれるシーケンスy、前記シーケンスxjおよび前記最も確からしい結託戦略θc*を知っているときの、前記符号のn個のシーケンスのうちc個のシーケンスの結託中における前記所与のシーケンスxjの存在の条件付き確率であり、該存在はsjc＝1によって表される。実際、有罪判定は確率ベクトル：あるユーザーが結託に参加している確率によってモデル化できる。変数sjcがこの参加を表し、ユーザーjが結託に参加していれば1に等しく、ユーザーjが無実であれば0に等しい。有罪判定は、sjc＝1となる確率の評価に基づく。この確率は、有罪の個人（最大スコア）または有罪の個人たちのグループ（ある閾値より大きいスコア）を識別することを有利に可能にする有罪性スコアを提起する。
【００２８】
さらに、本発明は、確率論的結託防止符号のシーケンスを、マルチメディア・コンテンツの不正コピーの作成に使われた前記マルチメディア・コンテンツ中に存在する前記符号の少なくとも一つのシーケンスを識別することをねらいとする前記符号の復号のためにフィルタリングする方法に関する。本方法は、前記不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する少なくとも一つのシーケンスを含む、可能な最も小さい符号シーケンスのサブグループを選択するステップを含み、前記選択は、前記符号の各シーケンスについて、選択された所与のシンボル・インデックスについて、前記符号のシーケンスのシンボルを前記不正コピーに含まれているシーケンスのシンボルと比較することによる。海賊版制作者を捜すシーケンスの数を制限することによって、実装が非常に簡単なこのフィルタリングは、復号の計算量を制限する。この本復号方法は、多数のユーザーをサポートするいかなる符号復号方法についても格別に有利である。実際、海賊版制作者によって使用される結託戦略に依存して、フィルタリングは、ユーザーのうち、つまり符号シーケンスのうちのほんの0.1%ないし20%だけを保持することを可能にする。
【００２９】
本発明のある個別的な特徴によれば、符号シーケンスをフィルタリングする前記方法は、前記コピーに含まれるシーケンスが、符号シーケンスの結託の誤りのない結果であることを検証する。実際、前記コピーのシーケンス中に所与のシンボルが存在することに基づくフィルタリング方法は、このシンボルにおけるいかなる誤りも許容しない。よって、この検証は、前記コピーのシーケンスが、誤りのない、符号シーケンスの結託の結果である場合にのみ本フィルタリング方法が適用されることを可能にする。
【００３０】
ある個別的な実施形態によれば、前記結託防止符号はタルドス符号である、
本発明は、付属の図面を参照しつつ決して限定するものではない実施形態および有利な実装によってよりよく理解され、例解されるであろう。
【図面の簡単な説明】
【００３１】
【図１】コンテンツの結託による不正コピーの作成および頒布の原理を示す図である。
【図２】タルドス符号の原理を示す図である。
【図３】コピーの結託におけるシンボルの選択の戦略を示す図である。
【図４】本発明のある実施形態に基づく、結託防止符号を復号する方法を示す図である。
【図５】本発明に基づくフィルタリング方法を示す図である。
【図６】本発明に基づく復号方法を示す図である。
【発明を実施するための形態】
【００３２】
図１は、コンテンツの結託による不正コピーの作成および頒布の原理を図的に示している。コンテンツ提供者は、たとえばインターネットを通じて、特に映画もしくはビデオ、音楽もしくはオーディオ、ビデオ・ゲーム、デジタル書籍または他の任意のデジタル文書を含むマルチメディア・コンテンツ１０１を提案する。アクティブ・フィンガープリンティングとして知られる原理によれば、コンテンツ提供者は合法的に頒布される各コピー１０２に、そのコピーのソースおよびそのユーザーを特定できるようにする一意的な通し番号１０３を挿入する。この通し番号１０３は、タルドス符号のような結託防止符号のシーケンスである。この通し番号は、一意的なユーザーへの各コピーを見かけ上同一にする透かし入れ方法を使ってコピー中に挿入される。コンテンツはブロックに切り分けられ、通し番号の諸シンボルはコンテンツ中でブロックごとに隠される。自分たちの素性を保護しながらこのコンテンツのコピーを不正に提案するため、PおよびMのような海賊ユーザーのグループが自分たちの個人的なコピーをブロックごとに組み合わせることによってコピー１０４を作成し、こうして符号シーケンスに対応しない通し番号Y １０５を作り出す。これがコピーの結託（collusion of copies）である。さらに、この通し番号Y １０５は、低域通過フィルタリングによって、透かし入れ層の復号方法に干渉するノイズを加えることによって、その不正コピーの損失のある圧縮によって、変更されることもできる。コピーの結託は、ブロックのマージによっても実現できる。この場合、ユーザーたちは自分たちのコピーを、画像またはビデオの場合はピクセルごとに、オーディオ文書の場合はサンプルごとに混合する。たとえば、前記コピーのピクセルは、各コピーのピクセルの平均、中央値（三つ以上のコピーが混合される場合）、最小値または最大値である。この場合、コンテンツ通し番号を検出するために課題を突きつけられるのは、透かしを復号する方法の堅牢さである。通し番号の、すなわち結託防止符号のこれらの修正は、ノイズ１０６によってモデル化される。ソースが求められる不正コピー１０７において検出される通し番号は、Z １０８と記される。
【００３３】
タルドス符号のような確率論的結託防止符号は、結託によって得られるコピーの起源における種々のソースを特定できるようにするために設計された。図２は、そのような符号X ２０１の構築原理を示す。この符号は、n個のシーケンス２０２{xj}j=1,nから構成される。ここで、シーケンスのインデックスjは1からnまで変わる。各シーケンス２０３ xjはユーザーjに関連付けられる。シーケンスは、m個のシンボル２０４のリストxj＝{xj,1,xj,2,...,xj,m}である。これらのシンボル２０４はq元アルファベットχ＝{0,1,...,q}に属する。図２に表されるタルドス符号の場合、このアルファベットは二元χ＝{0,1}であり、たとえばxj＝{0,1,...,0}である。
【００３４】
確率論的符号の生成は擬似ランダムである。鍵２０５{P1,P2,...,Pm}から、任意のシーケンスj∈{0,...,n}について、そのシーケンス中の任意のシンボルi∈{0,...,m}について
Prob[xj,i＝x]＝p(x,i)
となるような統計則（statistical law）pがある。
【００３５】
値p(x,i)はその符号の補助変数行列と呼ばれる行列P ２００に記憶される。この行列の行インデックスは符号のn個のシーケンスであり、列インデックスはシーケンスのm個のシンボルである。この行列は、さらに符号X ２０１のすべてのシーケンス２０２をリストするための秘密鍵としてはたらくデータベースに対応する。
【００３６】
結託防止符号は次の性質をもつ：有限個の符号シーケンスのシンボルの混合から、こうして得られた新しいシーケンスの復号によって、その混合によって使われたもとの諸シーケンスの部分集合を再び見出すことを可能にする。符号は、シーケンスの（よってユーザーの）ある最大数nおよび再び見出すことのできる混合中のもとのシーケンスの（よって不心得なユーザーの）ある最大数cについて設計される。従来技術によれば、結託戦略が何であっても、復号パフォーマンスは一様である。本発明に基づく復号方法は、復号パフォーマンスを改善するような仕方で結託戦略に対する仮設を選択することを含む。種々の結託戦略は、図３を使ってより簡単に説明されるであろう。保護されるべく試みられているマルチメディア・コンテンツはm個のブロック３０１に切り分けられる。各ブロックiは、透かし入れ技術を使って、結託防止符号のシンボルxi ３０２を隠しており、こうして、隠されたシンボルに固有のブロックiのバージョンを提案している。透かし入れの原理が十分安全でないので、ユーザーは、透かし入れ層のブロックをみつけることはできるが、挿入されたデータ項目を抽出することはできない。換言すれば、海賊版制作者は、自分たちがもっていないシンボルをマスクするブロックを作成することはできない。不正なユーザーたちはこうして、もとのコンテンツP ３０３またはM ３０４の各ブロックについて、自分たちが知っているブロックの諸バージョンの集合３０７のうちからあるバージョンを集めてくることによって、コピー３０６を構成する。海賊たちはたとえば、もとのコンテンツの諸ブロックのバージョンJ ３０５は知らない。よって、結託によってc人の不心得なユーザー３０８をまとめてグループ化し、彼らのコピーがインデックスがC＝{j1,...,jc}であるシーケンスによって同定されるとすると、所与のインデックスiのブロックyiについて、彼らはyi∈{xj1,i,...,xjc,i}のうちからの選択に制限される。よって、これは海賊たちが構成できる可能なシーケンス数に対して制限を課すことになる。
【００３７】
種々の結託戦略が考えられる：
・一様な引き抜き（uniform pulling）：結託に加わっているユーザーたちのブロックのうちから、それぞれについて等しい確率で、たとえば二つの場合には確率１／２で、あるブロッが引き出される。
・多数決（majority vote）：結託に加わっているユーザーたちのブロックのうちで他よりも多い存在によってブロックが選択される。
・少数決（minority vote）：結託に加わっているユーザーたちのブロックのうちで他よりも少ない存在によってブロックが選択される。
・ランダム投票（random vote）：結託に加わっているユーザーたちのブロックのうちでランダムにブロックが選択される。
【００３８】
すべての場合において、海賊たちに利用可能なシンボルの分布の知識が重要である。それは型の概念である。結託中に存在するc個のシーケンスのシンボルは型（type）tで分布する。型tは、q個の値のベクトルであり、結託中に潜在的に存在するc個のシーケンスjについて、シンボル・インデックスiについてのk番目の成分t(k,i)は、シンボルkに等しい可能性のあるシンボルのリスト{xj1,i,...,xjc,i}内のシンボル数を示す。q元アルファベットのシンボルのc個のシーケンスから作成される可能な型tの集合は、Tqcと記される。
【００３９】
本発明のある個別的な特徴によれば、結託戦略（collusion strategy）は、海賊たちがもっている全シンボルの型を知っているときの、海賊たちがシンボルyを不正なコピー内に入れる条件付き確率として定義される。y∈χとしてProb[y|t]と記されるこのモデル化は、特に、決定論的であれランダムであれ先述した種々の戦略の、確率論的領域における一つの可能な表現である。たとえば、多数決の場合（結託中のユーザーたちのブロックのうち他より多く存在している場合にあるブロックが選ばれる）、Prob[y|t]は、結託中の諸シーケンスのうちで同一のシンボルの最大数を有する型について最大になるであろう。本発明に基づく復号方法は、戦略がランダムであるときに特に好適であるが、所与のコピーの結託について変わるものではない。
【００４０】
本発明のもう一つの個別的な特徴によれば、結託中のあるユーザーの存在も確率論的領域においてモデル化される。変数sjを、シーケンスjが結託で使われたマルチメディア・コンテンツ内に存在していると同定される場合に値1をとり、そうでない場合に値0をとるものと定義する。結託におけるあるユーザーの存在は、確率Prob[sj＝1]によってモデル化される。
【００４１】
本発明に基づく復号方法は、結託に対する耐性の問題のこの二重モデル化に基づく。実際、結託戦略について何の仮設も立てない一様戦略として知られる有罪判定戦略について従来技術が教示することとは逆に、本発明に基づく復号方法は、不正コピーを作成するために海賊のグループによって使用された戦略を決定する。さらに、別の特許出願によって教示される逐次反復的方法とは逆に、本発明に基づく復号方法は、可能なモデルの集合のうちからの結託モデルの確率に基づく二重選択によって、使われた結託戦略を決定する。図６は、本発明に基づく復号方法を示している。不正コピー（６０１）に含まれるシーケンスおよび諸符号シーケンス（６０２）から、結託防止符号の復号方法は、不正コピーの起源における諸ソースを決定する（６０５）。本方法は、一様方法と呼ばれる有罪判定方法によって教示されるソースの特定ステップ（６０４）に加えて、結託戦略の選択ステップ（６０３）をもつ。この結託戦略は、不正コピーを作成するために海賊たちによって実行された選択、たとえば一様な引き抜き、多数決、少数決またはランダム投票を表す。
【００４２】
図４は、n個のシーケンス{xj}j=1,nから構成される確率論的結託防止符号Xについての高速復号方法であって、マルチメディア・コンテンツの不正コピーの作成に使われたマルチメディア・コンテンツ内に存在する少なくとも一つの符号シーケンスXの識別を、結託戦略のモデルの集合のうちからそのコピーを構成するために使われた結託戦略を選択することから行うことをねらいとする方法の実施形態の一つを示している。作成されるモデルの集合は二つのパラメータに依存する：結託における海賊の数と、結託に存在する諸シーケンスのシンボルのリストである。結託中の海賊の数cはcminからcmaxまでの間で変わる。結託中のシーケンス数に対する仮設が可能でない場合には、cminは1に固定され、cmaxは符号の構築の間に考慮された裏切り者の最大数を超えてはならない。最初のステップ４０１の間に、不正コピーに含まれるシーケンスyを知っている場合の結託戦略の確率の推定量が計算される。この推定量は、θc＝{Prob[y|t], y∈χ, t∈Tqc}と記される結託戦略のモデル化を使う。ここでcは結託中に存在するシーケンス数、{Prob[y|t], y∈χ, t∈Tqc}は、シンボルの各リストtについて構成される、結託戦略の確率のベクトルであって、χ＝{0,1,...,q−1}と記されるq元アルファベットのc個のシンボルから作られる可能なリストのTqcと記される集合のうちからの結託中に存在する諸シーケンスのシンボルのリストtを知っているときの、不正コピーのシーケンスy中にそのシンボルを観察する条件付き確率Prob[y|t]からなる。このモデルを考慮に入れると、所与の結託戦略について不正コピー中にシーケンスyを観察する事後確率は、
Prob[y|θc]＝Πi∈[1,m]Prob[y(i)|θc]＝Πi∈[1,m](Σti∈TcqProb[y(i)|ti]Prob[ti])
である。ここで、iは1からmまで変わるシンボル・インデックスであり、結託中のc個のシーケンスについて、シンボル・インデックスiについてのtiは、符号の各シンボルについて、q個のシンボルからなるアルファベット上のc個のシンボルのリストから構築されるベクトルである。最も確からしい結託戦略は、シーケンスyを観察するためのその結託戦略の事後確率を最大にするものである。結託戦略θcの確率の推定量はLblind(θc)＝Log(Prob[y|θc])と記される。ここで、Prob[y|θc]は、結託中に存在するc個のシーケンスについて結託戦略θcを知っているときの、不正コピー中にシーケンスyを観察する条件付き確率である。この推定量は、シーケンスy ４０８、符号のシンボルχ＝{0,1,...,q−1} ４０９および秘密鍵{P1,P2,...,Pm} ２０５のみに依存する。
【００４３】
ある変形実施形態によれば、不正コピー中にシーケンスyを観察するための所与の結託戦略の事後確率の種々の項Prob[y(i)|ti].Prob[ti]は、可能な各シンボルy(i)およびq個のシンボルのアルファベット中のc個のシンボルの各リストtiについて事前計算される。事前計算は、結託戦略θcの確率の推定量の計算ステップを加速し、よって復号のパフォーマンスを改善する。
【００４４】
ステップ４０３では、結託におけるシーケンスの数cの各推定について、結託中の諸シーケンスのシンボルのリスト上で、第一の選択が、結託戦略の、つまりこのリストの最大確率に基づいて行われる。結託中のc個のシーケンスの確率の推定量を最大にする結託戦略は、θc*と記される。こうして、このステップ４０３ののち、結託中のシーケンスの数がcであるとすると、結託戦略はθc* ４１１である。
【００４５】
ステップ４０４は、結託戦略θc*の仮設を形成する間に、各ユーザーについての有罪性スコアの計算を含む。よって、{Prob[sjc＝1|xj, y, θc*], j∈[1,n]}と記される、結託におけるシーケンスxjの存在の確率４１２のベクトルが計算される。sjは、シーケンスxjが結託中に存在する場合に1に等しい変数であり、Prob[sjc＝1|xj, y, θc*]４１２は、不正コピーに含まれるシーケンスy、シーケンスxjおよび最も確からしい結託戦略θc*を知っているときの、符号のn個のシーケンスのうちc個のシーケンスの結託中における所与のシーケンスxjの存在の条件付き確率である。その存在はsjc＝1と記される。この確率ベクトルは、結託戦略θc* ４１１が与えられたときのユーザーたちの有罪性スコアを表す。この確率ベクトルは、不正コピー中にシーケンスyを観察するための所与の結託戦略の事後確率Prob[y|θc]４０９で構成される。結託戦略のモデルの確率計算の二つのパラメータの一つである。これら二つのパラメータは、結託に荷担している海賊の数を、混合によってそのコピーのシーケンスを作成する海賊の数と相関させることを可能にする。Q(θc*) ４１３と記される結託戦略のモデルの確率の計算がステップ４０５において実行される。ステップ４０６の間に、モデルの集合のうちからの第二の選択が、結託中のシーケンスの数ならびにQ(θc*) ４１３と記されるモデルの確率を最大化する関連付けられた結託戦略、つまりθc** ４１４の決定を可能にする。つまり、θc**＝argmaxθQ(θc*)である。
【００４６】
最後に、ステップ４０７において、ユーザーたちの有罪性スコアすなわちシーケンスxjが結託中に存在する確率４１２のベクトルの計算が、ステップａ）４０１、４０３およびｂ）４０４、４０５、４０６の確率基準に従った選択によって得られた結託戦略θc**に従って更新される。その際、この同じステップ４０７は、不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する符号の少なくとも一つのシーケンスを決定する。本発明の諸実施形態によれば、少なくとも二つの基準によって結託中に存在するシーケンスを決定できる。第一の基準は、結託におけるシーケンスの存在の確率のベクトルの値のうちからの、所与のシーケンスについての確率の最大値Prob[sjc＝1|xj, y, θc**]である。有利なことに、この基準は、比較的低い偽警報確率の誤りで、海賊を特定することを可能にする。第二の基準は、結託におけるシーケンスの存在の確率のベクトルの値のうちからの、あるグループの諸シーケンスjのそれぞれについてある閾値Sより大きな確率の値Prob[sjc＝1|xj, y, θc**]である。たとえば、この基準は、有利なことに、この閾値が１／２に固定される場合、有罪である確率が無罪である確率より大きいユーザーを訴追することを可能にする。有利には、この閾値は、偽警報または見逃し条件を満たすよう決定されることもできる。本発明に基づく復号に従って、無実の個人と有罪の個人のスコアが広く分離されることを強調することが特に有益である。これは、有罪である個人がより確信をもって（すなわち、偽警報またはミスの高められた確率について）訴追されることを可能にし、あるいはコピーの結託の諸ソースの特定のために必要とされる符号の長さを短縮することを可能にする。
【００４７】
ある実施形態によれば、復号方法は、諸シーケンスをフィルタリングするステップ４０２を含むことができる。このステップは、符号のシーケンスの数nが、よって結託仮設が構築されるシンボル数が制限されることを可能にする。このフィルタリング・ステップは、ステップ４０１および４０４のデータ４０９に対して介入する。さらに、フィルタリングのある復号方法のパラメータも適応されるが、同じ有罪判定方法が使われる。フィルタリング方法において選択されたシンボルのインデックスi*が記されるとすると、有罪判定方法は、このシンボルを無視しなければならない。こうして、符号の諸シーケンスはm−1シンボルの長さであり、考慮されるべきコピーのシーケンスはy′と記され、シンボルy(i*)が除去されたyに等しい。このフィルタリング・ステップに関連する方法は、図５においてより広く例解される。
【００４８】
本発明に基づく復号方法は、たとえば以前の高速復号方法から帰結する、ユーザーの有罪性についての事前の知識を考慮に入れることができるという利点をも呈する。復号方法のパラメータは適応され、同じ有罪判定方法が使われる。不正コピーの作成に使われたマルチメディア・コンテンツ中に存在するシーケンスがxlと記されるとすると、シーケンスxlを条件とする、結託中でのシーケンスの存在の確率のベクトルはProb[sjc|xj, xl, y, θ c**]と書かれる。
【００４９】
図５は、シーケンス・フィルタリング方法の実施形態の一つを示す。このフィルタリング方法は、海賊たちが、彼らのコピーをブロックごとに混合することによって不正コピーを作成する間に、シンボルを生成することはできないという仮設に基づく。符号のシーケンスのm個のシンボルのうちから巧妙に選択されたシンボル・インデックスiについて、不正コピーのシンボルy(i)は、諸シーケンスのうち、同じインデックスにおいてこの同じシンボルをもつシーケンスからである。問題は、その中から海賊を捜すことができるできるだけ小さいユーザーのグループであって、よってフィルタリングに従う復号アルゴリズムの計算量を低下させるグループを構築できるようにするインデックスiを選択することである。図２に示されるように、確率論的結託防止符号は、鍵２０５と、任意のシーケンスj∈{0,...,n}についてシーケンス中の任意のシンボルi∈{0,...,m}についてProb[xj(i)＝x]＝p(x,i)のような統計則pとから構築される。この統計則は、不正コピーのシーケンス５０１の所与のインデックス・シンボルiについて、このシンボルを観察する確率５０２を計算することを可能にする。タルドス符号のような、また図５に表されるような二元符号の場合、シンボルは値(0,1)をとり、p1がインデックス・シンボルiについて「1」にあるシンボルを観察する確率であるとすると、1−piは「0」におけるシンボルを観察する確率である。というのも、Prob[x(i)＝0]＋Prob[x(i)＝1]＝1だからである。復号されるシーケンスy ５０１について最大数のユーザーがフィルタリングされることを可能にするシンボル・インデックスi* ５０４の選択は、復号されるシーケンス５０１においてこのインデックスについてのこのシンボルを観察する確率p(y(i),i)が最低になるようにするものである。i∈[1,m]として、i*＝argmin p(y(i),i) ５０３である。よって、フィルタリングに続くステップは、i*インデックス・シンボルが不正コピーのシーケンスのi*インデックス・シンボルに等しくなるxM(i*)＝xJ(i*)＝y(i*)のような符号のシーケンスM ５０６およびJ ５０７の選択を含む。なお、図２に示した例において、結託に荷担したシーケンスはシーケンスP ５０５およびM ５０６であり、フィルタリングによって保持されるシーケンスはシーケンスM ５０６およびJ ５０７である。このように、フィルタリングは、サブグループが結託中の少なくとも一つのシーケンス、シーケンスM ５０６を含むが結託中の全部のシーケンスは含まない、たとえばシーケンスP ５０７は含まないときにサブグループを選択することを可能にする。このフィルタリング方法は、こうして、復号方法が結託内のシーケンスを特定することを許可するが、シーケンスのグループをではない。事前選択によって保持されるシーケンス５０７のサブグループ内に、結託に荷担した二つ以上のシーケンスがあった保証はないからである。
【００５０】
さらに、このフィルタリング方法は、シーケンスyが結託における諸シーケンスのシンボルの混合の誤りのない結果である場合にのみ機能する。ある個別的な実施形態によれば、フィルタリングの混合は、マーキング仮設（marking hypothesis）、つまりシーケンスyがシンボルに対する誤りを含むという仮設の検証ステップを含む。
【００５１】
結託戦略に応じて、フィルタリング方法は、多数決または少数決の場合には符号の諸シーケンスのうちの0.1%ないし一様な引き抜きの場合には符号のシーケンスの20%しか保持しない。実装が非常に簡単なこのフィルタリング方法は、結託防止符号復号方法の、特に本発明に基づく復号方法の計算量対パフォーマンス比の改善を可能にする。
【００５２】
ある有利な実施形態によれば、結託防止符号は、二元タルドス符号である。当該符号が構成によって復元することを可能にするシーケンスの最大数は、cと記される。こうして、q＝2であり、c＋1個の型が可能である。型は対(σ,c−σ)と記すことができる。ここで、σは、海賊が所有する「1」であるシンボルの数である。σと記される海賊が所有する「1」であるシンボルの数は0からcまでの間で変わる。すると、確率ベクトルθは、推定されるc′人の海賊版制作者について、{Prob[y＝1|σ＝0], Prob[y＝1|σ＝1],...,Prob[y＝1|σ＝c′]}∈[0,1]c′+1と書かれる。このベクトルは、それぞれ、結託の諸シーケンスの0個のシンボルが「1」であること、結託の諸シーケンスの一つのシンボルが「1」であることないし結託の諸シーケンスのc′個のシンボルが「1」であることを知っているときの、不正コピーのシーケンス中に「1」を観察する確率から構築される。透かし入れ層に対する誤り検出なしでは、海賊たちは新しいシンボルを作成できないので、不正コピー中のシンボルは海賊たちの「1」である諸シンボルまたは海賊たちの「0」である諸シンボルからであるので、Prob[y＝1|σ]＋Prob[y＝1|c′−σ]＝1であることも等しく考慮に入れるべきである。透かし入れ層に対する誤り検出なしでは、海賊たちは新しいシンボルを作成できないので、不正コピーのシーケンスは、海賊のシンボルのどれも「1」でない場合には「1」であるシンボルを含むことができず（つまりProb[y＝1|0]＝0）、逆に海賊のシンボルの全部が「1」である場合には「1」であるシンボルを含む（Prob[y＝1|c′]＝1）ことも等しく考慮に入れるべきである。
【００５３】
当然ながら、本発明は上記で述べた実施形態に限定されるものではない。
【００５４】
特に、本発明は、タルドス符号とは異なる結託防止符号にも適合する。
【符号の説明】
【００５５】
１０１ マルチメディア・コンテンツ
１０２ マルチメディア・コンテンツ
１０３ シーケンス
１０４ マルチメディア・コンテンツ
１０５ 不正コピーのシーケンス（PとMの結託）
１０６ ノイズ
１０７ マルチメディア・コンテンツ
１０８ 不正コピーの検出されるシーケンス
２００ 補助変数行列
２０１ 符号X
２０２ シーケンス
２０３ シーケンスJ
２０４ シンボル
２０５ 符号の鍵
３０１ マルチメディア・コンテンツをなすM個のブロック
３０２ シンボル
３０３ シーケンスP
３０４ シーケンスM
３０５ シーケンスJ
３０６ 不正コピーのシーケンスY
３０７ あるブロックの諸バージョンの集合
３０８ 結託に関与しているc個のシーケンス
４０２ シーケンスのフィルタリング
４０３ θc*の選択 θc*＝argmaxθc Lblind(θc)
４０４ θc*に基づいて有罪性スコアを計算 Prob[sjc＝1|xj,y,θc*]
４０５ Q(θc*)の計算
４０６ 結託戦略θc**の選択 θc**＝argmaxθ Q(θc*)
４０７ 結託に加わっている少なくとも一つのシーケンスを同定
４０８ シーケンスy
４０９ 符号のシンボルχ＝{0,1,...,q−1}
４１０ 確率Prob[y|θc]
４１１ 結託戦略θc*
４１２ 結託にシーケンスxjが加わっている確率
４１３ 結託戦略のモデルの確率Q(θc*)
４１４ モデルの確率を最大化する結託戦略θc**
４１５ sj＝1（シーケンスxjが結託に関与している）
５０１ 不正コピーのシーケンス
５０２ シンボルを観測する確率
５０３ シンボルを観察する確率p(y(i),i)が最低になるシンボル・インデックスi*
５０４ 最大数のユーザーがフィルタリングされることを可能にするシンボル・インデックスi*
５０５ シーケンスP
５０６ シーケンスM
５０７ シーケンスJ
６０１ 不正コピー
６０２ コード
６０３ 結託戦略の選択
６０４ 結託に加わっているソースの同定
６０５ 不正コピーの出所のソース
【特許請求の範囲】
【請求項１】
確率論的結託防止符号の復号方法であって、マルチメディア・コンテンツの不正コピーの作成に使われた前記マルチメディア・コンテンツ中に存在する前記符号の少なくとも一つのシーケンスを識別することをねらいとし、結託戦略モデルの集合のうちから前記コピーを構築するために使われた結託戦略を選択するステップを有することを特徴とする方法。
【請求項２】
前記結託戦略は、結託中に存在するいくつかのシーケンスについて、結託中に存在する諸シーケンスのシンボルの各リストについての、結託中に存在する諸シーケンスのシンボルのリストを知っているときの前記不正コピー中に前記シンボルを観察する条件的確率からなる結託戦略の諸確率のベクトルを含む、請求項１記載の方法。
【請求項３】
結託戦略のモデルの前記集合は、結託中に存在するシーケンスの数の各推定について、最も確からしい結託戦略を含む、請求項２記載の方法。
【請求項４】
請求項３記載の方法であって：
ａ）結託戦略のモデルの集合を生成するステップ、つまり、
ｉ．結託中のシーケンスの数の各推定について、結託中に存在する諸シーケンスのシンボルの各リストについて、前記不正コピー中に含まれるシーケンスを知っているときの結託戦略の確率の推定量の計算、
ｉｉ．結託中のシーケンスの数の各推定について、結託戦略の確率の前記推定量を最大にする結託戦略の事後的な選択；
ｂ）結託戦略のモデルの前記集合のうちから結託戦略を選択するステップ、つまり、
ｉ．前記最も確からしい結託戦略に関連付けられた結託中のシーケンスの数の各推定について、結託中にあるシーケンスが存在する諸確率のベクトルであって、前記符号の各シーケンスについての、前記不正コピー中に含まれるシーケンス、所与のシーケンスおよび前記最も確からしい結託戦略を知っているときに結託中に前記所与のシーケンスが存在する条件付き確率、から構築されるベクトルの計算、
ｉｉ．前記最も確からしい結託戦略に関連付けられた結託中のシーケンスの数の各推定について、結託中にあるシーケンスが存在する諸確率の前記ベクトルと、前記不正コピー中に含まれるシーケンスを知っているときの結託戦略の確率とからの、結託戦略の前記モデルの確率の計算、
ｉｉｉ．結託戦略のモデルの前記集合のうちからの、結託戦略の前記モデルの確率を最大にする、前記最も確からしい結託戦略に関連付けられた結託中のシーケンスの数の選択；
ｃ）前記不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する前記符号の少なくとも一つのシーケンスを、ステップｂ）で推定された結託戦略の前記モデルを知っているときの前記少なくとも一つのシーケンスの存在の条件付き確率から、識別するステップを含むことを特徴とする、
方法。
【請求項５】
請求項４記載の方法であって、ステップｃ）において、前記符号のあるシーケンスが前記不正コピーの作成に使われたマルチメディア・コンテンツ中に存在するとして識別することを、前記不正コピーに含まれるシーケンス、前記シーケンスおよびステップｂ）で選択された結託戦略の前記モデルを知っているときに結託中に前記シーケンスが存在する条件付き確率の値が最大であるときに行うことを特徴とする、方法。
【請求項６】
請求項４記載の方法であって、ステップｃ）において、前記符号のシーケンスのグループが前記不正コピーの作成に使われたマルチメディア・コンテンツ中に存在するとして識別することを、前記不正コピーに含まれるシーケンス、前記グループの前記シーケンスおよびステップｂ）で選択された結託戦略の前記モデルを知っているときに前記グループの各シーケンスについて前記条件付き確率の値がある閾値Sより大きいときに行うことを特徴とする、方法。
【請求項７】
前記符号のシーケンスをフィルタリングするステップを含むことを特徴とする請求項５記載の方法であって、前記フィルタリングするステップは、前記不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する少なくとも一つのシーケンスを含む前記符号のシーケンスの可能な最小のサブグループを選択することを含み、前記選択は、前記符号の各シーケンスについて、選択された所与のシンボル・インデックスについて、前記符号のシーケンスのシンボルを前記不正コピーに含まれているシーケンスのシンボルと比較することによる、方法。
【請求項８】
前記符号のシーケンスをフィルタリングする前記ステップは、前記コピーに含まれるシーケンスが前記符号のシーケンスの結託の、誤りのない結果であることを検証することを特徴とする、請求項７記載の方法。
【請求項９】
請求項５ないし７のうちいずれか一項記載の方法であって、前記不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する少なくとも一つのシーケンスの識別後、結託中の少なくとも一つの新たなシーケンスを識別するために当該方法が繰り返されることを特徴とする方法。
【請求項１０】
請求項２記載のであって、前記結託戦略がθc＝{Prob[y|t], y∈χ, t∈Tqc}と書かれ、ここでcは結託中に存在するシーケンスの数であり、{Prob[y|t], y∈χ, t∈Tqc}はシンボルの各リストtについて構成される、結託戦略の確率の前記ベクトルであって、χ＝{0,1,...,q−1}と記されるq元アルファベットのシンボルのc個のシーケンスから作られる可能なリストのTqcと記される集合のうちからの結託中に存在する諸シーケンスのシンボルの前記リストtを知っているときの、前記不正コピーのシーケンスy中にそのシンボルを観察する条件付き確率Prob[y|t]からなる、方法。
【請求項１１】
請求項４記載の方法であって、結託戦略のモデルの集合を生成するステップａ）において、結託戦略θcの確率の前記推定量がLblind(θc)＝Log(Prob[y|θc])と書かれ、ここで、Prob[y|θc]は、結託中に存在するc個のシーケンスについて結託戦略θcを知っているときの、前記不正コピー中にシーケンスyを観察する条件付き確率である、ことを特徴とする方法。
【請求項１２】
請求項４記載の方法であって、結託戦略を選択するステップｂ）において、結託中にあるシーケンスxjが存在する確率のベクトルが{Prob[sjc＝1|xj, y, θc*], j∈[1,n]}と書かれ、ここで、sjは、シーケンスxjが結託中に存在する場合に1に等しい変数であり、Prob[sjc＝1|xj, y, θc*]は、前記不正コピーに含まれるシーケンスy、前記シーケンスxjおよび前記最も確からしい結託戦略θc*を知っているときの、前記符号のn個のシーケンスのうちc個のシーケンスの結託中における前記所与のシーケンスxjの存在の条件付き確率であり、該存在はsjc＝1によって表される、ことを特徴とする、方法。
【請求項１３】
前記結託防止符号がタルドス符号である、請求項１ないし１２のうちいずれか一項記載の方法。
【請求項１】
確率論的結託防止符号の復号方法であって、マルチメディア・コンテンツの不正コピーの作成に使われた前記マルチメディア・コンテンツ中に存在する前記符号の少なくとも一つのシーケンスを識別することをねらいとし、結託戦略モデルの集合のうちから前記コピーを構築するために使われた結託戦略を選択するステップを有することを特徴とする方法。
【請求項２】
前記結託戦略は、結託中に存在するいくつかのシーケンスについて、結託中に存在する諸シーケンスのシンボルの各リストについての、結託中に存在する諸シーケンスのシンボルのリストを知っているときの前記不正コピー中に前記シンボルを観察する条件的確率からなる結託戦略の諸確率のベクトルを含む、請求項１記載の方法。
【請求項３】
結託戦略のモデルの前記集合は、結託中に存在するシーケンスの数の各推定について、最も確からしい結託戦略を含む、請求項２記載の方法。
【請求項４】
請求項３記載の方法であって：
ａ）結託戦略のモデルの集合を生成するステップ、つまり、
ｉ．結託中のシーケンスの数の各推定について、結託中に存在する諸シーケンスのシンボルの各リストについて、前記不正コピー中に含まれるシーケンスを知っているときの結託戦略の確率の推定量の計算、
ｉｉ．結託中のシーケンスの数の各推定について、結託戦略の確率の前記推定量を最大にする結託戦略の事後的な選択；
ｂ）結託戦略のモデルの前記集合のうちから結託戦略を選択するステップ、つまり、
ｉ．前記最も確からしい結託戦略に関連付けられた結託中のシーケンスの数の各推定について、結託中にあるシーケンスが存在する諸確率のベクトルであって、前記符号の各シーケンスについての、前記不正コピー中に含まれるシーケンス、所与のシーケンスおよび前記最も確からしい結託戦略を知っているときに結託中に前記所与のシーケンスが存在する条件付き確率、から構築されるベクトルの計算、
ｉｉ．前記最も確からしい結託戦略に関連付けられた結託中のシーケンスの数の各推定について、結託中にあるシーケンスが存在する諸確率の前記ベクトルと、前記不正コピー中に含まれるシーケンスを知っているときの結託戦略の確率とからの、結託戦略の前記モデルの確率の計算、
ｉｉｉ．結託戦略のモデルの前記集合のうちからの、結託戦略の前記モデルの確率を最大にする、前記最も確からしい結託戦略に関連付けられた結託中のシーケンスの数の選択；
ｃ）前記不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する前記符号の少なくとも一つのシーケンスを、ステップｂ）で推定された結託戦略の前記モデルを知っているときの前記少なくとも一つのシーケンスの存在の条件付き確率から、識別するステップを含むことを特徴とする、
方法。
【請求項５】
請求項４記載の方法であって、ステップｃ）において、前記符号のあるシーケンスが前記不正コピーの作成に使われたマルチメディア・コンテンツ中に存在するとして識別することを、前記不正コピーに含まれるシーケンス、前記シーケンスおよびステップｂ）で選択された結託戦略の前記モデルを知っているときに結託中に前記シーケンスが存在する条件付き確率の値が最大であるときに行うことを特徴とする、方法。
【請求項６】
請求項４記載の方法であって、ステップｃ）において、前記符号のシーケンスのグループが前記不正コピーの作成に使われたマルチメディア・コンテンツ中に存在するとして識別することを、前記不正コピーに含まれるシーケンス、前記グループの前記シーケンスおよびステップｂ）で選択された結託戦略の前記モデルを知っているときに前記グループの各シーケンスについて前記条件付き確率の値がある閾値Sより大きいときに行うことを特徴とする、方法。
【請求項７】
前記符号のシーケンスをフィルタリングするステップを含むことを特徴とする請求項５記載の方法であって、前記フィルタリングするステップは、前記不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する少なくとも一つのシーケンスを含む前記符号のシーケンスの可能な最小のサブグループを選択することを含み、前記選択は、前記符号の各シーケンスについて、選択された所与のシンボル・インデックスについて、前記符号のシーケンスのシンボルを前記不正コピーに含まれているシーケンスのシンボルと比較することによる、方法。
【請求項８】
前記符号のシーケンスをフィルタリングする前記ステップは、前記コピーに含まれるシーケンスが前記符号のシーケンスの結託の、誤りのない結果であることを検証することを特徴とする、請求項７記載の方法。
【請求項９】
請求項５ないし７のうちいずれか一項記載の方法であって、前記不正コピーの作成に使われたマルチメディア・コンテンツ中に存在する少なくとも一つのシーケンスの識別後、結託中の少なくとも一つの新たなシーケンスを識別するために当該方法が繰り返されることを特徴とする方法。
【請求項１０】
請求項２記載のであって、前記結託戦略がθc＝{Prob[y|t], y∈χ, t∈Tqc}と書かれ、ここでcは結託中に存在するシーケンスの数であり、{Prob[y|t], y∈χ, t∈Tqc}はシンボルの各リストtについて構成される、結託戦略の確率の前記ベクトルであって、χ＝{0,1,...,q−1}と記されるq元アルファベットのシンボルのc個のシーケンスから作られる可能なリストのTqcと記される集合のうちからの結託中に存在する諸シーケンスのシンボルの前記リストtを知っているときの、前記不正コピーのシーケンスy中にそのシンボルを観察する条件付き確率Prob[y|t]からなる、方法。
【請求項１１】
請求項４記載の方法であって、結託戦略のモデルの集合を生成するステップａ）において、結託戦略θcの確率の前記推定量がLblind(θc)＝Log(Prob[y|θc])と書かれ、ここで、Prob[y|θc]は、結託中に存在するc個のシーケンスについて結託戦略θcを知っているときの、前記不正コピー中にシーケンスyを観察する条件付き確率である、ことを特徴とする方法。
【請求項１２】
請求項４記載の方法であって、結託戦略を選択するステップｂ）において、結託中にあるシーケンスxjが存在する確率のベクトルが{Prob[sjc＝1|xj, y, θc*], j∈[1,n]}と書かれ、ここで、sjは、シーケンスxjが結託中に存在する場合に1に等しい変数であり、Prob[sjc＝1|xj, y, θc*]は、前記不正コピーに含まれるシーケンスy、前記シーケンスxjおよび前記最も確からしい結託戦略θc*を知っているときの、前記符号のn個のシーケンスのうちc個のシーケンスの結託中における前記所与のシーケンスxjの存在の条件付き確率であり、該存在はsjc＝1によって表される、ことを特徴とする、方法。
【請求項１３】
前記結託防止符号がタルドス符号である、請求項１ないし１２のうちいずれか一項記載の方法。
【図２】
【図３】
【図４】
【図５】
【図６】
【図１】
【図３】
【図４】
【図５】
【図６】
【図１】
【公開番号】特開２０１０−２６８４５３（Ｐ２０１０−２６８４５３Ａ）
【公開日】平成２２年１１月２５日（２０１０．１１．２５）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１０−１０２１５０（Ｐ２０１０−１０２１５０）
【出願日】平成２２年４月２７日（２０１０．４．２７）
【出願人】（５０１２６３８１０）トムソン ライセンシング (2,848)
【氏名又は名称原語表記】Ｔｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ
【住所又は居所原語表記】１−５， ｒｕｅ Ｊｅａｎｎｅ ｄ’Ａｒｃ， ９２１３０ ＩＳＳＹ ＬＥＳ ＭＯＵＬＩＮＥＡＵＸ， Ｆｒａｎｃｅ
【Ｆターム（参考）】
【公開日】平成２２年１１月２５日（２０１０．１１．２５）
【国際特許分類】
【出願番号】特願２０１０−１０２１５０（Ｐ２０１０−１０２１５０）
【出願日】平成２２年４月２７日（２０１０．４．２７）
【出願人】（５０１２６３８１０）トムソン ライセンシング (2,848)
【氏名又は名称原語表記】Ｔｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ
【住所又は居所原語表記】１−５， ｒｕｅ Ｊｅａｎｎｅ ｄ’Ａｒｃ， ９２１３０ ＩＳＳＹ ＬＥＳ ＭＯＵＬＩＮＥＡＵＸ， Ｆｒａｎｃｅ
【Ｆターム（参考）】
[ Back to top ]