(57)【特許請求の範囲】
【請求項１】
コンピュータ・システムによって実行される方法であって：
行が互いに直交する正方行列を生成する段階と；
前記正方行列の行を入れ替えて複数の置換正方行列を生成する段階と；
前記複数の置換正方行列を集めて集合された行を生成する段階と；
前記集合された行の一つを、デジタル透かし中の符号語として、デジタル・プロダクトに適用する段階とを含む、
方法。
【請求項２】
請求項１記載の方法であって：
前記符号語を、前記デジタル透かしの外側符号中に代入する段階をさらに含む、
方法。
【請求項３】
前記外側符号がリード・ソロモン符号である、請求項２記載の方法。
【請求項４】
請求項２記載の方法であって：
前記デジタル透かしをデジタル・プロダクトに適用する段階をさらに含む、
方法。
【請求項５】
請求項４記載の方法であって：
前記代入する段階後だが前記デジタル透かしをデジタル・プロダクトに適用する段階の前に、前記符号語のビットをランダムに入れ替える段階をさらに含む、
方法。
【請求項６】
前記正方行列がアダマール行列である、請求項１記載の方法。
【請求項７】
前記入れ替える段階が、固定マッピング、網羅的マッピング、ランダムなマッピングのうちの一つを使って達成される、請求項１記載の方法。
【請求項８】
符号帳からの透かし入れ符号語を検出する方法であって：
デジタル・プロダクトから透かし情報を抽出する段階であって、前記透かしは、行が互いに直交する正方行列を生成し；前記正方行列の行を入れ替えて複数の置換正方行列を生成し；前記複数の置換正方行列を集めて集合された行を生成し；前記集合された行の一つを、前記デジタル透かし中の符号語として、前記デジタル・プロダクトに適用することによって前記デジタル・プロダクトに適用されている、段階と；
前記抽出された透かし情報を、硬検出器と軟検出器の間で切り替わる適応検出器中に入力する段階と；
前記適応検出器の出力から、検出された透かし入れ符号語を生成する段階とを含む、
方法。
【請求項９】
請求項８記載の方法であって、前記適応検出器が、前記入力透かし情報に基づいて曖昧シンボル・カウントを計算し、前記曖昧シンボル・カウントが所定の閾値より高ければ前記軟検出器に切り替わり、前記曖昧シンボル・カウントが所定の閾値以下であれば前記硬検出器に切り替わる、方法。
【請求項１０】
前記軟検出器は、前記透かし情報から相関を通じて符号語を抽出する、請求項８記載の方法。
【請求項１１】
前記硬検出器を使って、前記符号語の各シンボル位置について、前記透かし情報から疑わしいシンボルを抽出する段階をさらに含む、請求項８記載の方法。
【請求項１２】
請求項１１記載の方法であって、さらに：
前記符号帳中の各符号語について、疑わしいシンボルの数を計算する段階と；
最大数の疑わしいシンボルをもつ一つまたは複数の符号語を同定する段階と；
前記同定された一つまたは複数の符号語を、前記の検出された透かし符号語として出力する段階とを含む、
方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデジタル・コンテンツの透かし入れに、より詳細には少数派結託攻撃に対するデジタル・コンテンツ透かしの保護に関する。
【背景技術】
【０００２】
マルチメディア・コンテンツ（静止画、動画またはオーディオ）の透かし入れは、デジタル・コンテンツ中に情報を埋め込むために該デジタル・コンテンツを修正するプロセスおよび修正されたコンテンツからその情報を復元する対応するプロセスである。そのような透かし情報の一つの例は、デジタル・オーディオまたはデジタル・ビデオのようなデジタル・マルチメディア・コンテンツに、制作後かつ頒布前または頒布中に追加されるまたは埋め込まれるデジタル法的コード（digital  forensic  code）である。この場合、透かしまたはデジタル法的コードは、それ以外の点では同一であるマルチメディア作品の多数のコピーのそれぞれに一意的な識別子を加えることを意図されている。ある応用では、これは、不正にコピーされたデジタル・マルチメディア・アイテムの出所を特定するために使うことができる。デジタル・ビデオおよびデジタル・オーディオのようなマルチメディア・アプリケーションのデジタル・コンテンツの透かし入れは、盗人が作品のコピーを不正使用し、それを不正に再頒布することを抑止する一つの技法である。この技法はまた、権限を与えられたデジタル・コンテンツの頒布者が高いセキュリティ基準を維持することを奨励することにもなる。透かし入れによって、不正使用されたコピーのもとになった特定の正規ディーラーを特定することができるからである。たとえば、デジタル・コンテンツの不正コピーが没収された場合、デジタル・コンテンツ内の透かし情報を使って権限を与えられた頒布者の素性（identity）、権限を与えられた頒布者によるデジタル・コンテンツの公衆呈示の時間と場所を、法的コード内のシリアル番号の使用により決定できる。この情報により、不正使用が行われた状況を判別すべく、特定された権限のある頒布者から捜査を始めることができる。
【０００３】
多くの応用では、デジタル的に透かし入れされたコンテンツの単位は、透かしが埋め込まれた時点と透かしが検出される時点との間に何らかの修正を受けることがある。これらの修正は、一般に透かしを劣化させてその検出をより難しくするので、「攻撃」と名付けられる。該攻撃が、正規のまたは非正規の頒布のプロセスの過程で自然に発生すると期待される場合、その攻撃は「意図的でない」と考えられる。意図的でない攻撃の例は次のようなものである：（１）クロッピング、スケーリング、JPEG圧縮、フィルタ処理などされた透かし入れ画像、（２）テレビジョン・ディスプレイ上での閲覧のためにNTSC／PAL  SECAMへの変換、MPEGまたはDIVX圧縮、再サンプリングなどがされた透かし入れされたデジタル・プロダクト。他方、攻撃が、透かしの目的をくじく意図をもって意図的になされる場合、攻撃は「意図的」であり、その攻撃を実行する者は盗人または海賊である。意図的な攻撃の三つのクラスは権限のない埋め込み、権限のない検出および権限のない除去である。本発明は、権限のない除去、つまり透かしを除去したりその検出を妨害したり（つまり、透かしはまだコンテンツ中にあるが検出器によって簡単に取得することはできない）することに関する。不正除去攻撃は一般に、コンテンツへの知覚上の害を最小限にしつつ透かしを読めなくすることを目標にする。攻撃の例は、小規模な知覚できないライン除去／付加および／またはローカル回転／スケーリングの組み合わせをコンテンツに加えてその検出器との同期を難しくすることでありうる（多くの透かし検出器は同期外れに敏感である）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】D.  Boneh  and  J.  Shaw,  "Collusion-secure  fingerprinting  for  digital  data",  IEEE  Transactions  on  Information  Theory,  vol.44,  no.5,  pp.1897-1905,  1998年9月
【非特許文献２】G.  Tardos,  "Optimal  probabilistic  fingerprint  codes",  Proceedings  of  the  35th  Annual  ACM  Symposium  on  Theory  of  Computing,  2003,  pp.116-140
【非特許文献３】S.  He  and  M.  Wu,  "Joint  coding  and  embedding  techniques  for  multimedia  fingerprinting",  IEEE  Transactions  on  Information  Forensics  and  Security,  vol.1,  no.2,  pp.231-247,  2006年6月
【発明の概要】
【発明が解決しようとする課題】
【０００５】
一つの型の攻撃は、同じコンテンツの複数の異なるコピーを組み合わせてそれぞれに含まれる異なる透かし情報を偽装またはスクランブルしようとする結託攻撃である。結託によって透かし情報を破壊することが試みられた場合に海賊行為の対象とされたデジタル・コンテンツからデジタル透かし情報を正確に取得するための技法を開発することが有用であろう。
【課題を解決するための手段】
【０００６】
透かし符号語を生成する方法であって、少数派型結託攻撃を示す結託されたデジタル・プロダクトを生成する一または複数の結託者の正確な検出を可能にする方法が呈示される。本符号語生成プロセスは、各行が互いに直交する正方行列を生成することを含む。そのような互いに直交する正方行列はアダマール行列（Hadamard  matrix）である。その正方行列の行の入れ替え〔置換（permutation）〕が生成される。そのような入れ替えが多数生成される。それらの入れ替えされた正方行列の総合的な連結（aggregate  concatenation）の諸行が内側符号として使われる。改善された誤り訂正符号ベースの方式の構築において外側符号も使われる。内側符号と外側符号の組み合わせがデジタル透かし入れのための符号語である。
【０００７】
三以上の結託者の少数派結託攻撃における該三以上の結託者のうちの一を、あるいは多数派結託攻撃における該三以上の結託者のうちの一を、およびインターリーブ式結託攻撃における二以上の結託者の一を検出するために、適応検出器装置が有用である。少数派攻撃、多数派攻撃およびインターリーブ式攻撃のもとでの本適応検出器の全体的な機能は、上記の行入れ替えされたアダマール・ベースの内側符号で透かし入れされた、デジタル・マルチメディア・プロダクトのようなデジタル・プロダクト／コンテンツに対する結託攻撃を呈する二以上の結託者のうちの一の検出である。本適応検出器は、結託攻撃にさらされたデジタル・プロダクト／コンテンツから抽出された透かし情報を受け入れる入力バッファを含む。本装置は、結託されたデジタル・プロダクト／コンテンツから符号語を抽出するコンピュータ命令を実行する。本装置は、抽出された符号語の統計的な特徴を使って、試験対象の結託されたデジタル・プロダクト／コンテンツを制作した結託者の最も確からしい集合を決定する。処理された符号語は、結託攻撃にさらされたデジタル・プロダクト／コンテンツからの透かし情報を生成するために符号語が使われた二以上の既知のユーザーに対応する二以上の符号語の少なくとも一つを同定する。
【０００８】
本発明の追加的な特徴および利点は、付属の図面を参照しつつ進められる例示的な実施形態の以下の詳細な説明から明白となるであろう。
【図面の簡単な説明】
【０００９】
【図１】透かし埋め込みプロセスを示す図である。
【図２】透かし検出プロセスを示す図である。
【図３】ａはECCベースのエンコーダのための例示的な外側符号を表し、ｂはECCベースのエンコーダのための直交する内側符号を表し、ｃは内側符号と外側符号の組み合わせを表し、ｄはECCベースのエンコーダ機構のためのランダム化を表す図である。
【図４】本発明の諸側面に基づくECCベースの符号の生成を示す図である。
【図５】本発明の諸側面に基づく行入れ替えされた直交内側符号の生成を示す図である。
【図５ａ】本発明の諸側面に基づくアダマール行列の例示的な行入れ替えを示す図である。
【図５ｂ】本発明の諸側面に基づく符号帳生成器を示す図である。
【図６】本発明の諸側面に基づく行列Ti(i)の例示的な計算を示す図である。
【図７】本発明の諸側面に基づく適応検出器の流れ図である。
【図８】本発明の諸側面に基づく適応検出器システムのブロック図である。
【図９】本発明の諸側面に基づく少数派攻撃のもとでの確率検出を示す図である。
【発明を実施するための形態】
【００１０】
本稿での用法では、「／」は同じまたは同様の構成要素または構造についての代替的な名前を表す。すなわち、「／」は本稿での用法では「あるいは」を意味するものと解釈できる。デジタル法的符号／透かしは、不正頒布のためにマルチメディア・コンテンツを不正使用したユーザーを特定するための技法において用いることができる。これらの法的符号／透かしは典型的には、多様な攻撃に対して堅牢であるよう設計された透かし入れ技法を使ってコンテンツ中に埋め込まれる。そのようなデジタル法的符号に対する攻撃の一つの型が結託である。結託においては、デジタル・マルチメディア・コンテンツの正規のソースを特定する、基底にある法的透かしを破壊するために、同じコンテンツのいくつかの異なるマーク付けされたコピーが組み合わされる。マルチメディア法的符号の設計における特別な困難は、保護されるデータがマルチメディアである場合、結託者は通例、誤ったチャネルを形成する、結託後の後処理を適用するということである。たとえば、結託者は、結託されたコピーを再頒布する前に、データ・サイズを削減するためにマルチメディアを圧縮することができる。したがって、チャネル誤りに対して堅牢な、結託耐性のある法的符号を設計することが重要である。
【００１１】
結託対策の法的マーク付け方式としては三つの一般的なものがある。第一の結託対策符号は、ボネー・ショー（BS:  Boneh  and  Shaw）符号として知られ、非特許文献１に記載されている。第二の結託対策符号はタルドス（Tardos）符号として知られ、非特許文献２に記載されている。第三の結託対策マーク付け方式は誤り訂正符号（ECC:  error  correcting  code）ベースのマーク付けとして知られ、非特許文献３に記載されている。ECCアルファベットを変調するために直交内側符号を使うことによりこの枠組みを拡張して、基本的なECCベースの法的符号が得られる。
【００１２】
BS符号は、長い符号長および少数結託者しかいない結託に対する低い結託耐性という欠点がある。タルドス符号は二元対称通信路（BSC:  binary  symmetric  channel）のもとで最良の結託耐性を与えるものの、基本的ECCやBS符号設計に比べ四桁高い計算量と四桁高い記憶消費をももつ。基本ECC設計は最悪ケースのシナリオのもとでより高い検出確率を与えるので、BS符号よりも好ましいように思われる。全体的には、基本ECC符号は計算および記憶資源が限られている実際的な応用のために有望な方式である。基本ECC符号の欠点は、タルドス符号と比べたときの、BSCのもとでの低い結託耐性である。本発明のある側面では、BSCのもとでの基本ECC符号の結託耐性パフォーマンスの改善（改善されたECCの生成）が提示される。
【００１３】
一般に、結託攻撃には三つの型がある：インターリーブ式、多数派および少数派である。インターリーブ式攻撃（interleaving  attack）では、有効な法的符号／透かし検出を回避しようとして、結託者たちはほぼ均等なシェアでビットごとに法的データのコピーを寄与する。この型の攻撃は、二以上の結託するユーザーがいるときに開始できる。この方法は、罪のない正規の頒布者が保護されたデジタル・コンテンツの不正使用されたコピーの一つのソースとして偽陽性検出されることにつながるおそれがある。多数派攻撃（majority  attack）では、結託者たちは、結託者の間でのビット状態の多数派が選択されて保護されたデジタル・コンテンツの最終的な結託コピーに入れられるよう、ビットごとに法的データを組み合わせる。この型の攻撃は、三以上の結託するユーザーがいるときに開始できる。この方法も法的符号語検出における偽陽性結果を生じうる。少数派攻撃（minority  attack）は、最も少ない結託者の符号語ビットを表す法的符号語のビットを選ぶことによって、相関ベースの検出器による有効な検出の可能性を減らすことを目標としている。こうして、検出誤差の確率が増す。この型の攻撃は、三以上の結託するユーザーがいるときに開始できる。本発明は、少数派攻撃検出解決策に取り組むものであるが、インターリーブ式および多数派型の結託攻撃についても機能する。
【００１４】
図１は、コンピューティング・システムを使って実装された、法的符号語／透かし埋め込みシステム１００のブロック図を描いている。最初に、各ユーザーについての符号語が生成され、符号帳〔コードブック〕に記憶される。ある実施形態では、符号帳は、デジタル・コンテンツ／プロダクトの正規ユーザーのための符号語の一部またはすべてを表すデジタル情報である。入力ユーザー・インデックス／ID（識別子）に基づいて、同定されたユーザーについての符号語が生成される（１０５）。そのような符号語生成は、メモリに記憶されたデータを取得することによって実行されることができ、あるいは透かし入れプロセスが開始されたときに生成されることができる。ユーザー符号語は次いでエンコーダ１１０においてもとのデジタル・コンテンツ信号と組み合わされる。エンコードの結果は、もとのデジタル・コンテンツ信号中に符号語が埋め込まれた、透かし入れされたデジタル・コンテンツ信号である。エンコーダ１１０の出力は、対応する正規ユーザーによる頒布のための透かし入れされたデジタル・コンテンツ信号である。
【００１５】
図２は、透かし／法的符号の一般符号検出器２００を示している。一般符号検出器２００は、結果の生成および表示のためのコンピュータ・システム上で実装されてもよい。最初、疑わしいデジタル・コンテンツ信号が法的符号／透かし抽出器２０５中に入力される。疑わしいデジタル・コンテンツからの透かし情報が抽出される。ユーザー符号語のすべては符号語生成器２１０によって生成される。この符号語生成器は、図１の項目１０５に示したものと同様のデバイスであることができる。攻撃者検出器２１０は次いで攻撃者の符号語を検出し、攻撃者の素性を判別するために該符号語が全符号語のリストと比較される。疑われる結託者の素性が表示されることができる（２２０）。そのような表示は、これに限られないが、端末／モニタまたは印刷デバイス上での表示を含む。この事例において、ユーザーはエンコードされたデジタル・コンテンツの正規ユーザーである。たとえば、ユーザーは映画のようなデジタル・コンテンツ・プロダクトの正規の頒布者であることができる。海賊行為の対象とされたデジタル・プロダクトが暴露されると、疑わしいデジタル・プロダクト中の符号語に対応する符号語をもつ正規ユーザーの一または複数が結託者でありうる。ここで、結託者という用語は、デジタル・プロダクトのコピーがデジタル・プロダクト海賊版制作者／盗人の手に落ちるのを許した正規ユーザーをいう。
【００１６】
図３のａ〜ｄは、基本的なECCベースの法的符号を生成する一般的方法を描いている。図３のａの第一のステップは、L個のシンボルおよびq個のアルファベット{f0,f1,…,fq-1}をもつNのユーザーについてECC外側符号を生成するものである。ある実施形態では、図３のａの外側符号はその大きな最小距離に起因するリード・ソロモン符号として構築される。図３のｂは、基本ECCのためにアルファベットとして使われる例示的な二元内側符号を描いている。ここで、零は−1の値として描かれている。図３のｃは、各ユーザーについて、図３のｂの内側符号を図３のａの外側符号に代入した結果を示す。これが、ユーザーについての基本ECC符号を生成する一つの方法である。ある実施形態では、基本ECC符号語はさらに、各ユーザーについてのビットをランダムに入れ替えることによって操作されることができる。図３のｄはユーザー１についての図３のｃの符号語ビットのランダム置換を描いている。この「ランダム」置換は、ランダム化器によって実施されてもよく、一般に符号語構造が攻撃者によって破られる（broken  down）ことを防止するために実行される。図３のｄの動作後の結果は、各ユーザーについてのランダム化された基本ECC符号語である。
【００１７】
図３のｂおよび内側符号に戻って参照すると、q個のアルファベットを変調し、内側符号を外側符号に代入するために、値＋1／−1および長さlをもつq個の直交二元内側符号が使われる。全体的な符号長はLlビットであり、ユーザーの総数はN＝qtである。ここで、tは外側リード・ソロモン符号の次元である。直交内側符号は結託者の情報をできるだけ多くリザーブするよう設計される。q個の直交ベクトルについて、q個の内側符号は1と−1のすべての2q通りの可能な組み合わせをリストし、よって符号長l＝2qをもつ。基本ECCについて図３のｂに示される直交内側符号は次のようにして構築される。i番目の符号語fi-1について、最初の2q-i個のビットは1であり、次の2q-i個のビットは−1である。次いで、同じ符号が2i-1回繰り返され、2qビットとなる。q＝3の内側符号行列が図３のｂに示されている。第一の符号語f0の最初の4ビットは1であり、残りのビットは−1である；第二の符号語f1の最初の2ビットは1であり、残りの2ビットは−1であり、次いでこの符号パターンが一回繰り返される。これは基本ECC符号語についての内側符号を生成する。
【００１８】
図４は、ECCベースのプロセスを使ってユーザーの法的符号帳を生成するプロセス４００を描いている。このプロセス４００は、基本ECCおよび本発明の一側面である改善されたECCの両方について有用である。プロセス４００は、図３のａ〜ｄに描かれたプロセスに続く。ステップ４０５では、リード・ソロモン符号のような外側符号がq個のアルファベットをもってNユーザーのために生成される。一般に、外側符号の生成のための入力パラメータはユーザー数、アルファベット・サイズqおよび所望される外側符号長である。ステップ４１０では、内側符号が生成される。ここで、外側符号のq個のアルファベットを表すためにq個の二元内側符号語が生成される。使用されるアルゴリズムに対応するために零状態については−1の値が使われる。一般に、内側符号の生成のための入力パラメータは、アルファベット・サイズqおよび所望される内側符号の全体的な長さを含む。ステップ４１５において、内側符号が外側符号と組み合わされる。ある実施形態では、内側符号は外側符号に代入される。ステップ４２０では、各ユーザーについて、結果として得られる内側および外側符号が既知のランダム化アルゴリズムに従ってランダムに置換される。こうして、ビット・レベルのランダム化が各ユーザーについて適用される。各正規ユーザーについて結果として得られる符号語は、本質的には、ユーザー法的符号の符号帳において、そのユーザーについてのエントリーの一つとして使用される。こうすると、この符号帳は、不正なデジタル・コンテンツ頒布の計略における攻撃者／結託者を見出すための検出プロセスにおいて有用である。ステップ４２５は、正規ユーザーに対応するために使用されることのできる単一の符号語または符号帳全体を出力する。
【００１９】
ある実施形態では、結託者を特定するためにユーザーの符号語を検出するためにECC法的符号方式において相関ベースの検出器が用いられる。yが結託されたコピーから抽出された法的符号であり、xiがユーザーiの法的符号であり、Uが全ユーザーの集合であるとすると、ユーザーiの検出統計量は次のようになる。
【００２０】
【数１】
0005331889.tif 000002
ここで、xi(j)およびy(j)はそれぞれxiおよびyのj番目のシンボルに対応する符号語である。最大値検出器においては、ユーザーiが最高の検出統計量をもつ、すなわちTi≧Tk  ∀k∈Uである場合に、ユーザーiは結託者であるとして有罪と見なされうる。閾値検出器においては、ユーザーiの検出統計量が閾値hより大きい、すなわちTi≧hである場合に、ユーザーiは結託者として有罪と見なされうる。上記の公式(1)を使った検出は、軟検出器（soft  detector）と称することができる。
【００２１】
ある実施形態では、少数派型結託攻撃が透かし入れされたデジタル・コンテンツに対して行われる場合に、ECC法的符号において相関ベースの検出器が用いられる。±1二元法的符号についてのcの結託者による少数派攻撃は次のように定式化される。
【００２２】
【数２】
0005331889.tif 000003
【００２３】
少数派攻撃の背後にある一つの動機は、結託者を検出および特定しようとして相関ベースの検出器が使われるということを結託者が知っているということである。少数派攻撃検出では、相関ベースの検出器はデジタル・コンテンツの結託されたコピーのあらゆる符号ビットから各攻撃者の痕跡を集める。これを知っているので、結託者たちは、結託者の符号語中の各位置において、現れる回数が最も少ないビットを選ぶのである。これは、相関ベースの検出器によって決定される相関を効果的に低下させ、よって検出誤りの確率を高める効果がありうる。
【００２４】
基本ECC法的符号設計の一つの特徴は、ビット誤り率（BER:  bit  error  rate）が0であるときでさえ、三人の結託者による少数派攻撃に弱いということである。これは次の定理によって説明される。±1の値を取る任意の三つの二元直交符号x1,x2,x3が与えられたとき、少数派結託された符号yはx1,x2,x3に直交する。あるいは等価なことだが、〈y,x1〉＝〈y,x2〉＝〈y,x3〉＝0である。これは、lを符号長とし、x1(i)、x2(i)、x3(i)およびy(i)をそれぞれx1、x2、x3およびyのi番目のビットとして証明できる。x1(i)はx1(i)、x2(i)およびx3(i)のうちの少数派または多数派のいずれかであることができる。x1(i)が少数派である場合、y(i)＝x1(i)であり、よってy(i)*x1(i)＝1である。さらに、ディリクレの引き出し論法によりx1(i)は少数派なので、x2(i)はx3(i)に等しくなければならない。したがって、x2(i)*x3(i)＝y(i)*x1(i)＝1である。
【００２５】
同様に、x1(i)が多数派の場合、y(i)＝−x1(i)およびx2(i)＝−x3(i)である。よって、x2(i)*x3(i)＝y(i)*x1(i)＝-1である。x1(i)＝x2(i)＝x3(i)であれば、明らかにy(i)＝x1(i)＝x2(i)＝x3(i)であり、x2(i)*x3(i)＝y(i)*x1(i)＝1である。よって、1≦i≦lのすべてのiについてx2(i)*x3(i)＝y(i)*x1(i)＝1である。
【００２６】
【数３】
0005331889.tif 000004
なので、〈y,x1〉＝〈x2,x3〉＝0である。同じ証明は〈y,x2〉＝〈y,x3〉＝0にも適用できる。
【００２７】
上記の定理に基づいて、結託者の数が3であるとき、基本ECC相関ベース検出器を用いた任意の二元直交法的符号の少数派結託された法的マーク付け符号は常に結託者の法的符号に直交する。したがって、上で論じた基本ECC設計を使うと、結託者が三つの異なる内側符号をもつ場合にシンボル位置において結託者についての情報は失われるので、結託者の検出統計量は非常に小さくなる。こうして、結託者が少数派攻撃戦略を適用するときには基本ECC法的符号の結託耐性は劣化する。基本ECC設計は一般に、少数派攻撃における三人の結託者を正確に検出することはできないのである。本発明は、基本ECC符号語設計のこの検出欠点に対処する。
【００２８】
基本ECC設計において使用される内側符号を生成するためにアダマール行列を使うことができる。アダマール行列は、要素が＋1または−1であり、行が互いに直交している正方行列である。一般に、アダマール行列のどの二つの異なる行も二つの直交なベクトルを表す。アダマール行列は、qc＝2mかつmが整数の場合に存在するqc×qcの直交行列である。次数qcのアダマール行列Hqcは再帰的に次式によって生成できる
【数４】
0005331889.tif 000005
【００２９】
4≦n≦32として次数nのアダマール行列Hnにおける任意の三つの行{r1,r2,r3}が与えられたとき、それら三つの行のビットごとの少数派をとったものをyとすると、y＝xとなるような行
【数５】
0005331889.tif 000006
が一つ、しかも一つだけ存在する。このように、標準的なアダマール行列が内側直交符号生成に使われれば、結果として得られる少数派結託された法的符号は常に偽陽性結果を生じる（すなわち、罪のないユーザーを誤って特定する）。結果として、結託者の三つの符号語が異なっている場合、一人の罪のないユーザーが結託の罪を着せられることになりうる。しかしながら、本発明のある側面として、基本ECC内側符号設計において標準的なアダマール行列を使うときに経験される偽陽性結果を回避するために、アダマール行列を使った内側符号の生成に修正をすることが可能である。本発明の内側符号設計の修正および改善は、アダマール行列のランダム置換によって、少数派結託攻撃において結託者を罪のないユーザーから区別するために有用な直交内側符号を得ることに関わる。
【００３０】
図５は、一組の行置換されたアダマール行列の連結を使う、本発明の諸側面に基づく、n個の行とnK個の列をもつ直交内側符号を生成する例示的なプロセス５００を示している。ステップ５０５で次数nのアダマール行列H(1)が生成される。ステップ５１０で逐次反復数を制御するためにインデックス／カウンタが設定される。次いで、ステップ５１５で、アダマール行列H(1)の行のランダム置換が実行されて行レベル置換されたアダマール行列H(i)が生成される。これは、8×8のアダマール行列を示す図５ａにさらに描かれている。図５ａでは、本発明のある側面に従って、行レベル置換がアダマール行列H8に適用され、行置換されたH8を生じる。図５ａは行列H8の最初の置換しか描いていないが、通常、本発明の側面に従って、そのような多数の置換が達成される。置換行列の数は、内側符号語の所望される長さに基づいて決定できる。より多数のアダマール行列を置換することは、より長い長さの内側符号語を生じる。内側符号のアダマール行列置換の数は、固定した、網羅的なまたはランダムなマッピングを使って達成できる。固定マッピングは既知の一組の置換であってもよい。網羅的なマッピングはアダマール行列の行のあらゆる可能な置換である。ランダム置換は、ランダムな手段または擬似ランダムな手段によって生成されるいくつかの置換を含む。
【００３１】
図５に戻ると、アダマール行列H(1)が行置換されてH(1)の次の置換であるH(2)が得られたのち、ステップ５２０でインデックス／カウンタがインクリメントされる。判断ステップ５２５はプロセス５００がステップ５１５のランダム置換をK回実行し、アダマール行列H(1)のK−1個の置換されたバージョンを得ることを許容する。置換されたアダマール行列は、H(2)  H(3)…H(K)のようなアダマール行列の系列をなす。K−1個の置換されたアダマール行列が形成されたとき、ステップ５２５が完了し、プロセス５００はステップ５３０に進む。ステップ５３０では、最終内側符号Gはすべての行列H(i)の総合（aggregation）、すなわちG＝[H(1)  H(2)  H(3)…H(K)]であり、H(i)≠H(j)  ∀1≦i,j≦K  i≠jである。この総合は、アダマール行列の連結と見なしてもよく、この連結がECC符号の内側符号をなす。一般に、内側符号の長さが長いほど、結託されたデジタル・コンテンツにおける検出属性はよくなる。ステップ５３０の結果は、一または複数の正規ユーザーについての生成された内側符号を見たい操作者による目視のために、コンピュータ・システムを使って表示または印刷されてもよい。さらに、上記のような改善されたECC内側符号の生成は、改善された内側符号をデジタル・プロダクトに透かしとして挿入することを許容する。上記の改善された内側符号はまた、デジタル・プロダクトについてのデジタル透かし入れプロセスにおける使用のために、図４におけるように外側符号中に挿入されることもできる。
【００３２】
上に提示した改善された内側符号の使用の一例において、三結託者が少数派攻撃をかけているとする。一般性を失うことなく、一つのシンボル位置に注目する。yを、そのシンボル位置での結託された法的符号とする。内側符号を考えると、Kが十分大きければ、1≦i≦Kとして、すべてのH(i)のうちK/(n−3)個の行列において、あらゆる罪のないユーザーが検出される。よって、試験信号yと罪のないユーザーxについての法的符号との間の相関の期待値は、〈y,x〉＝Kn/(n−3)である。一方、yと任意の結託者の法的符号との間の相関は0のままである。したがって、結託者は、結託者については0であり罪のないユーザーについてはKn/((n−3)√l)である検出統計量の差によって検出されることができる。ここで、lは内側符号の符号長であり、K＝l/nである。Kが大きくなると結託者と罪のないユーザーの検出統計量の期待値の差が大きくなるため、内側符号が長いほど、ECCベースの法的符号の、少数派攻撃に対する結託耐性はよくなる。
【００３３】
当業者は、図５の内側符号生成方法が図１に示した型のシステムとの関連で、内側符号、（必要なら）外側符号を生成し、デジタル・コンテンツ・プロダクトのようなデジタル・プロダクトに対して透かしをエンコードするために使用されうることを認識するであろう。これが達成されるのは、図５の方法が、符号語を、あるいはユーザーをデジタル・プロダクトのコピーと同定するためのユーザーの符号語の符号帳を生成するために使用されうるからである。図５ｂは、本発明の原理を使って符号帳を生成するシステム５５０を描いている。符号帳生成デバイス５６０はシステム５５０ユーザーから入力５５５を受け取る。それらの入力は、外側符号と内側符号の両方を生成するために必要とされる入力を含む。リード・ソロモン符号のような外側符号定義のために、システム５５０ユーザーによって入力される入力パラメータは、意図されるデジタル・コンテンツ／プロダクト・ユーザー（頒布者／ユーザーなど）の数、アルファベット・サイズ（q）およびリード・ソロモン符号長（L）を含む。本発明の諸側面に基づく内側符号のための入力パラメータは、アルファベット・サイズ（q）および内側符号語の合計長さを含む。符号語生成デバイス５６０は、本発明に従って外側および内側符号を生成するためのコンピュータ命令を含むコンピュータ・コード５６２へのアクセスをもつプロセッサ５６４を含む。コンピュータ・コードは、磁気、光学式または半導体メモリのような固定または着脱可能なコンピュータ可読媒体の形であってもよい。ある実施形態では、コードはメモリ５６６内に存在する。メモリ５６６はコンピュータ命令のためにプロセッサにとってアクセス可能であるだけでなく、コンピュータ・コードの必要性に応じて符号語の処理に関係した記憶のためにもコンピュータによって使用されうる。プロセッサはまた、出力バッファ５６８へのアクセスをももつ。出力バッファ５６８は、生成された符号語をバッファリングしてデバイス５６０の外に出し、プリンタ、ディスプレイまたは図１もしくは図２のようなシステムの場合にはエンコードもしくは検出プロセスにおいて符号語を使う下流の段といった有形的な具現に送り込むために有用である。当業者はよく理解するように、本発明の範囲および精神内でハードウェアおよびソフトウェアまたはファームウェア実装の多くの変形が可能であるので、図５ｂの実施形態は限定するものではない。
【００３４】
検出目的について図５の改善された内側符号設計の恩恵を実感するために、検出統計量がユーザーiについてのj番目のシンボルTi(j)に関して再定義される。別の言い方をすると、基本ECC設計の内側符号設計の公式(1)の検出統計量は、本発明の内側符号設計を使って改善されることができる。発想は、ユーザーiの検出統計量と罪のないユーザーの検出統計量との間の差を検出統計量として使うということである。T(j)medianをGy(j)Tのメジアン値とする。これは、G中の各内側符号語と結託された符号y(j)との間の相関を含むベクトルである。実際的な応用ではたいていそうであるようにアルファベット・サイズが結託者シンボルの数の２倍より大きければ、Gy(j)Tのメジアン値は罪のない符号語に属する可能性が非常に高い。よって、本発明の一側面として、シンボルjにおけるユーザーiについての検出統計量Ti(j)は次のように再定義される。
【００３５】
【数６】
0005331889.tif 000007
【００３６】
上記の公式(3)の行列の例示的な計算は図６に与えられている。ここで、G＝[H(1)  H(2)  H(3)  …  H(5)]であり、H(k)は行置換された次数8のアダマール行列である。図６の行列は[H(1)  H(2)  H(3)  …  H(5)]×y(j)Tを示している。図６から、G×y(j)Tのメジアンは8であり、これは罪のない符号語から来る。よって、G×y(j)TからT(j)medianを引いて√lにより規格化することにより、罪のないユーザーについては値Ti(j)＝0が得られ、一方、結託者については値Ti(j)＝(√40)/5が得られる。この例は、本発明の改善されたECC設計が、無実のユーザーではなく結託者を明確に特定するために少数派攻撃解析においていかに有用かを示している。こうして、基本ECC設計は、三結託者での少数派攻撃におけるいかなる符号語をも完全に検出することに失敗するが、本発明の改善されたECC設計は三結託者の少数派攻撃における少なくとも一の、最大では三の結託者の符号語を検出でき、よって基本ECC設計に対する著しい改善である。
【００３７】
本発明のもう一つの側面を考えると、適応検出器は、公式(3)の改善されたECC設計統計量の向上された検出能力と公式(1)の基本ECC設計統計量の基本的な検出能力の両方を利用するよう実装されることができる。罪のない（結託していない）ユーザー検出統計量が、結託者の統計量より高ければ、検出誤差は受け入れられないと考えられる。たとえば、少数派攻撃のもとにおけるように、上記の公式(1)の軟検出器だけを使うと罪のないユーザーが実際の結託者のグループに含められる結果になりうることが可能である。この問題を解決するために、本発明の一側面に従って、公式(1)の軟検出器と関連して硬検出器（hard  detector）を使ってもよい。図７は、本発明の側面に基づく適応検出のための例示的なプロセスの一つの実施形態を描いている。
【００３８】
図７のプロセス７００は、本発明の側面に従って硬検出器および軟検出器の両方を含んでいるという点で適応検出器である。軟検出器の属性は公式(1)に関連して上で論じた。硬検出器は、外側符号の各シンボル位置上での疑わしいシンボルを検出するために用いられる。次いで、各ユーザーについて、疑わしいとマークされたシンボル数が計算される。疑わしいシンボルの数が最大であるユーザーが結託者として選ばれる。図７を参照するに、ユーザー符号語の符号帳〔コードブック〕および試験対象の結託されたデジタル・プロダクト／コンテンツのサンプルから導出された試験符号語（y）がステップ７０５でプロセス７００に入力される。ステップ７０５では、j番目のシンボルにおける各ユーザーについての公式(3)のTi(j)も計算される。外側符号構造のため、ユーザーたちはあらゆるシンボル位置上でシンボルを共有することを注意しておく。Ti(j)はq個のアルファベットにおける各シンボルについて計算される。ステップ７１０では、集合{T1(j)  T2(j)  …  TN(j)}が各位置jについて降順にソートされ、ベクトルZを得る。ステップ７１５では、∀1≦k≦q−1に対して値D＝Z(k)−Z(k＋1)が計算される。ここで、Z(k)はソートされたZのk番目の要素である。Z(k)−Z(k＋1)の最大を与えるインデックスkをkmaxとする。ステップ７２０では、計算されたDの値に基づいて、シンボルが疑わしいか否かまたは公式(3)の統計量が曖昧であるかどうかについての判断がなされる。Dの値が閾値（a）より大きい場合、シンボルは疑わしく、プロセス７００はステップ７２０からステップ７２５に移る。Dの値が閾値（a）より大きくない場合、シンボルの統計量は曖昧であり、プロセス７００はステップ７２０からステップ７３５に移る。一事例では、Z(kmax)−Z(kmax＋1)としての値Dが≦閾値（a）と評価される場合、統計量が曖昧なので、どのシンボルも位置jにおいて疑わしいシンボルとして主張されない。この事例では、プロセス７００はステップ７２０からステップ７３５に移る。しかしながら、D＝Z(kmax)−Z(kmax＋1)の値が閾値（a）より大きいと評価される場合、Z(1),…,Z(kmax)に対応するシンボルは疑わしいシンボルであると宣言され、プロセス７００はステップ７２０からステップ７２５に移る。
【００３９】
ステップ７３５では、j番目のシンボルが曖昧だとマークされるまたは考えられ、曖昧シンボル・カウントCvがインクリメントされてからステップ７４０に移る。Dの評価された値が閾値（a）より大きい場合、ステップ７２５にはいって、シンボルが疑わしいシンボルとして記憶され、その後プロセス７００はステップ７４０に進む。ステップ７４０では、結託された符号語のシンボル位置すべてが調査されたか否かについての判定がなされる。さらなるシンボルが残っている場合、プロセス７００はステップ７４０からステップ７４５に移る。ステップ７４５では、次のシンボル位置が調査される。次いでプロセスはステップ７１５に移る。何らかの反復工程において、結託された符号語のシンボルすべてが調査され終わり、ステップ７４０の判定はステップ７５０に移る。
【００４０】
ステップ７５０では、軟検出器を使うか硬検出器を使うかについての決定がなされる。曖昧なシンボルの数が閾値（b）を超える場合、硬判定は信頼性をもってできない。結果として、ステップ７５０の判定により曖昧なシンボルの数（Cv）が閾値（b）を超える場合、ステップ７５５の軟検出器が使用される。ステップ７５５では、ユーザーiについての全体的な検出統計量の計算が公式(1)を使って決定され、結託者の統計量が決定される。閾値（b）は検出プロセス７００ユーザーによって定義されるパラメータであり、異なるシンボル位置について異なることができる。ある実施形態では、閾値（b）は、結託者の数および外側符号相関パラメータに依存して閾値のリストから検出システム７００によって選択されてもよい。たとえば、外側符号相関が3/31であり、L＝31であり、結託者数が5の場合、我々の実験によれば、罪のないユーザーは最大15の疑わしいシンボルをもつことができる一方、結託者は少なくとも27の疑わしいシンボルをもつはずである。したがって、閾値（b）は、硬検出器精度を保証するために12より小さく設定されることができる。
【００４１】
ステップ７５０に戻ると、曖昧なシンボルの数が閾値（b）を超えない場合、硬検出を使うことができ、プロセス７００はステップ７５０からステップ７３０に移る。ステップ７３０では、各ユーザーについての疑わしいシンボルの総数が計算され、硬検出において結託者が同定される。ステップ７５５および７３０は両方とも、結果を累積し、発見された結託者のリストを表示するステップ７６０にはいる。ステップ７６０は結託者統計を収集し、符号帳のエントリーを結託符号語結果に対して比較する。したがって、結託符号語に対応する結託者のリストが生成される。ステップ７６０は次いで、表示、プリントアウトまたは他の形の具体的な出力を生成し、試験対象のデジタル・コンテンツに含まれる結託者情報の検出に関するプロセス７００から帰結する出力情報を与える。ステップ７６０の出力はステップ７３０（硬検出器）、ステップ７５５（軟検出器）および符号帳入力を使ったそれらの符号語の比較から集められた符号語の表示を許容する。符号帳符号語は既知の正規ユーザーの符号語である。プロセス７００において、ステップ７３０、７５５および７６０の結果は、プロセス７００が結託されたデジタル・プロダクトの結託者として同定する正規ユーザーの符号語に対応する処理された符号語を提供する。
【００４２】
硬検出器は、少数の結託者（三以上）の少数派攻撃の条件下ではよく機能するものの、結託者の数が増えたときは、多数派攻撃およびインターリーブ式攻撃のような他の結託攻撃のもとでは軟検出器ほど堅牢ではない。したがって、法的検出器は適応的に機能し、検出器システムに入力された結託されたデジタル・コンテンツからのサンプルの結託された透かしにおいて検出された情報に基づいて硬検出器と軟検出器の間で切り換えるよう設計される。
【００４３】
硬検出器のパフォーマンスが各シンボルの疑わしい内側符号の検出が成功するか否かに依存していることを注意しておく。曖昧なシンボルの数が多すぎると硬検出器はうまく機能しないことがありうる一方、軟検出器はより多くの情報を含むのでよりよく機能できることは合理的に予見できる。図７に機能的に表されている適応検出器はこの柔軟性を達成する。全体としては、適応検出器は、三以上の結託者の少数派型結託攻撃における三以上の結託者のうち少なくとも一の、最大では三の結託者、多数派型結託攻撃における三以上の結託者の一、あるいはインターリーブ型結託攻撃における二以上の結託者の一を検出できる。
【００４４】
図８は、適応検出器システム８００の実施形態を描いている。適応検出器装置８３０は、本発明に従って、符号帳〔コードブック〕８１０または改善されたECC符号語を割り当てられたユーザーの符号帳エントリーを入力する。符号帳生成器は、図５ｂの符号帳生成器または図５ｂと同様の生成器の出力である符号語の事前記憶されたリストであってもよい。海賊版マルチメディア・プロダクトのような疑われるデジタル・プロダクトの抽出された透かし符号語８２０も適応検出器装置８３０に入力される。ある実施形態では、海賊行為の対象にされたデジタル・コンテンツ符号語８２０からの法的符号語が抽出され、適応検出器８３０に与えられる。
【００４５】
入力バッファ８３２は入力を受け入れ、該入力をプロセッサ８３４によって使用可能にするために使われる。疑われるデジタル・コンテンツ符号語８２０の処理は、本発明の側面に従って、プロセッサ８３４の指令のもとで開始される。ある実施形態では、適応検出器フローを実装するプロセス７００が着脱可能または固定のコンピュータ可読媒体として前記プロセッサに利用可能にされてもよい。媒体は、磁気、光学式または半導体メモリのような有形媒体において、記憶されたコンピュータ実行可能な命令をもつ。ある実施形態では、プロセッサはプロセス７００のステップを実行するファームウェア・ブロックを制御する。こうして、プロセス７００はソフトウェア８３６として記憶されてもよいし、あるいはプロセッサ８３４に利用可能なデバイス中のファームウェア８３６中にコードされていてもよい。メモリ８３５はプロセス７００を実行する際にプロセッサによって使用されうる、あるいはプロセス７００のための命令を記憶するために使用されうる。当業者には理解されるように、いかなる構成のプロセッサ、メモリおよびソフトウェアおよび／またはハードウェアが使用されてもよい。プロセス７００のコンピュータ命令の処理の結果は、システム８００のユーザーが見るためのディスプレイ８４０への出力バッファ８３８に与えられる。ディスプレイは、コンピュータ・モニタ、プリントアウトまたは結果情報をシステム８００ユーザーに伝える他の手段といったいかなる形の具体的な表示であってもよい。
【００４６】
上記の適応検出器の試験結果はコンピュータ・シミュレーションを介して達成された。シミュレーション設定では、220ユーザーがいる。結託者数cは最大5であり；RS符号は32のアルファベットをもち、符号長は31である。よって、最小距離は28である。内側符号は、上に提示したような置換‐修正された／改善されたアダマール符号であり、検出器は上記のような適応検出器である。一般に、５分の疑われるデジタル・コンテンツ・クリップにおける埋め込み可能なビットの数は108のオーダーであり、シミュレーション結果によれば、圧縮のような一般的な処理の等価BERは0.4ないし0.44の範囲である。全体的な符号長が約6×106であり、これは、各符号ビットの少なくとも20回の反復を許容することを注意しておく。検出器では、これら20の繰り返されたビットでの多数決を使って符号ビットに対する判断をする。二元対称通信路（BSC）は、各ビットを独立してある確率BERで反転させると想定される。すると、符号ビットを20回繰り返すのと多数決検出を組み合わせた結果は、符号ビットについて0.3の等価BER（生のビットについての0.44BERに対応）である。このように、シミュレーション結果では、反復および多数決処理は簡単のために省略される。0.32までのBERのもとでの6×106ビットをもつ符号のパフォーマンスはリーズナブルだからである。硬検出器についての閾値（a）（THa）は1.5に設定され、適応検出器についての閾値（b）THbは9である。内側符号の符号長は全ビットをフルに利用し、アダマール行列をできるだけ多数回置換するため2×105である。結果は200回のシミュレーション・ランに基づく。
【００４７】
図９は、結託者数c＝3,  4,  5で、BERが0ないし0.4であるときの、適応検出器、軟検出器および硬検出器についての少数派攻撃のもとでの結託耐性を描いている。ここで、0.4でのBERは、単一の硬検出器または軟検出器に対する、適応検出器の利点を示すために調べられている。結託者数が3であるときは、改善されたECCを使う本発明の適応検出器が基本ECCより完全に高い性能であることを注意しておく。c＝3では、基本ECCは完全に結託者を検出することに失敗する。修正された内側符号をもつ本発明の改善されたECCは、BERが0.32未満であるときに三以上の結託者を正確に検出するために有効である。しかしながら、BERが大きくなりすぎると、硬検出器は各シンボルについての疑わしい内側符号を同定できず、したがって、結託者ユーザー同定（裏切り者追跡（traitor-tracing））パフォーマンスはBERが増すにつれて急速に劣化する。適応検出器が軟検出器と硬検出器との間で正確な検出／判断をすることができることは明らかである。シミュレーションでは、硬検出器についての閾値（a）は1.5に設定され、軟検出器についての閾値（b）は9に設定される。上で論じたように、三結託者が少数派攻撃を実施するとき軟検出器は失敗するが、本発明の硬検出器は三人の少数派結託者をうまく検出する。他のシナリオでは、軟検出器は、0.4以下のBERについては完璧に機能できる。このように、軟検出器のパフォーマンスはBERによって変わらない。
【図１】
0005331889.tif 000008
【図２】
0005331889.tif 000009
【図３】
0005331889.tif 000010
【図４】
0005331889.tif 000011
【図５】
0005331889.tif 000012
【図５ａ】
0005331889.tif 000013
【図５ｂ】
0005331889.tif 000014
【図６】
0005331889.tif 000015
【図７】
0005331889.tif 000016
【図８】
0005331889.tif 000017
【図９】
0005331889.tif 000018