(57)【特許請求の範囲】
【請求項１】
複数のシンボルを使用して複数のユーザの各々のための固有の符号を生成するステップと、
前記複数のシンボルを表す複数の符号を生成するステップであって、第２のシンボルが後に続く第１のシンボルの文字列を生成するステップをさらに含み、前記第１のシンボルは全て１であり、前記第２のシンボルは全て−１であり、前記第１のシンボルの数は前記第２のシンボルの数と同じであり、前記第２のシンボルが後に続く前記第１のシンボルの長さが前記符号の長さよりも小さい場合には、前記第２のシンボルが後に続く前記第１のシンボルは前記符号長が満たされるまで繰り返される、当該複数の符号を生成するステップと、
前記複数の符号を前記複数のユーザの各々のための前記固有の符号に置換するステップと、
前記複数のユーザの各々のための符号語を生成するために、前記置換の結果として得られた前記符号を並べ替えるステップと、
前記符号語をディジタル・コンテンツに埋め込むステップと、
を含む方法。
【請求項２】
対応する符号語を有するユーザを識別する前記各符号語を出力するステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記複数のシンボルを表す前記複数の符号は指数直交符号である、請求項１に記載の方法。
【請求項４】
前記シンボルはアルファベットである、請求項１に記載の方法。
【請求項５】
前記固有の符号はリードソロモン符号である、請求項１に記載の方法。
【請求項６】
ユーザの数、シンボルのサイズ、および固有符号長を含む入力パラメータを受信するステップをさらに含む、請求項１に記載の方法。
【請求項７】
前記複数の符号のうちの第３の符号を生成するために前記複数の符号のうちの第１の符号を前記複数の符号のうちの第２の符号で乗算するステップをさらに含む、請求項１に記載の方法。
【請求項８】
前記複数の符号のうちの第２の符号を生成するために前記複数の符号のうちの第１の符号を直交行列で乗算するステップをさらに含む、請求項１に記載の方法。
【請求項９】
複数のシンボルを使用して複数のユーザの各々のための固有の符号を生成する手段と、
前記複数のシンボルを表す複数の符号を生成する手段であって、第２のシンボルが後に続く第１のシンボルの文字列を生成する手段をさらに含み、前記第１のシンボルは全て１であり、前記第２のシンボルは全て−１であり、前記第１のシンボルの数は前記第２のシンボルの数と同じであり、前記第２のシンボルが後に続く前記第１のシンボルの長さが前記符号の長さよりも小さい場合には、前記第２のシンボルが後に続く前記第１のシンボルは前記符号長が満たされるまで繰り返される、当該複数の符号を生成する手段と、
前記複数の符号を前記複数のユーザの各々のための前記固有の符号に置換する手段と、
前記複数のユーザの各々のための符号語を生成するために、前記置換の結果として得られた前記符号を並べ替える手段と、
前記符号語をディジタル・コンテンツに埋め込む手段と、
を含む装置。
【請求項１０】
対応する符号語を有するユーザを識別する前記各符号語を出力する手段をさらに含む、請求項９に記載の装置。
【請求項１１】
前記複数のシンボルを表す前記複数の符号は指数直交符号である、請求項９に記載の装置。
【請求項１２】
前記シンボルはアルファベットである、請求項９に記載の装置。
【請求項１３】
前記固有の符号はリードソロモン符号である、請求項９に記載の装置。
【請求項１４】
ユーザの数、シンボルのサイズ、および固有符号長を含む入力パラメータを受信する手段をさらに含む、請求項９に記載の装置。
【請求項１５】
前記装置はストレージを内蔵するプロセッサであり、前記ストレージは前記符号語を生成するために前記プロセッサ上で実行される命令を含む、請求項９に記載の装置。
【請求項１６】
前記複数の符号のうちの第３の符号を生成するために前記複数の符号のうちの第１の符号を前記複数の符号のうちの第２の符号で乗算する手段を含む、請求項９に記載の装置。
【請求項１７】
前記複数の符号のうちの第２の符号を生成するために前記複数の符号のうちの第１の符号を直交行列で乗算する手段を含む、請求項９に記載の装置。
【発明の詳細な説明】
【背景技術】
【０００１】
本発明は、ディジタル・コンテンツの電子透かしに関し、特に、ディジタル・コンテンツに埋め込まれた電子透かしに対して仕掛けられた共謀攻撃（ｃｏｌｌｕｓｉｏｎ  ａｔｔａｃｋｓ）に対抗できる電子透かしを生成するために使用される内部符号の構成に関する。
【０００２】
本明細書において使用される用語、コンテンツまたはディジタル・コンテンツは、限定するものではないが、オーディオ、ビデオ、または、マルチメディア・コンテンツを含み得る。コンテンツまたはディジタル・コンテンツは、ディジタル信号として考えることができる。電子透かしの埋め込みは、情報をコンテンツに埋め込むためにコンテンツを変更する処理、さらに、変更されたコンテンツからこの情報を復元する、対応する処理である。このような電子透かし情報の一例は、プロダクション（制作）の後、配布の前または、配布の間にコンテンツ内に付加される、または、埋め込まれるディジタル・フォレンシック符号である。この場合、電子透かしまたはディジタル・フォレンシック符号は、独自の識別子をマルチメディア作品の多数のコピーの各々に適用するように意図されている。これらのマルチメディア作品のコピーは、他の点では同一のものである。一適用例においては、不正にコピーされたコンテンツのソース（出所源）を特定するためにこれを使用することができる。ディジタル・シネマなどのディジタル・コンテンツに電子透かしを埋め込むことは、不正取得者がコンテンツを不正にコピーして不正に再配布しようとするのを抑止する一技術である。さらに、電子透かしは、不正なコピーの元となる特定の正規ディーラを識別できるため、この技術は、ディジタル・コンテンツの正規配布者に対し、高セキュリティ基準を維持するように促すものである。例えば、ディジタル・コピーの不正コピーが没収された場合には、ディジタル・コンテンツ内の電子透かし情報を使用して、正規配布者の身元、さらに、おそらくは、フォレンシック符号内のシリアル番号の使用を通じて正規配布者によるディジタル・コンテンツの上映や販売の場所や時間を判定することができる。この情報を用いて、識別された正規配布者から調査を開始して、不正利用が発生した状況を特定することができる。
【０００３】
多くの適用例においては、電子透かしを埋め込まれたコンテンツのユニットには、この電子透かしが埋め込まれた時点と埋め込まれた電子透かしが検出された時点との間で幾らかの変更がなされることがある。これらの変更は、一般的に、電子透かしの品質を低下させ、検出をより困難にするものであるため、「アタック」と呼ばれる。アタックが正規の配布または不正な（無許可の）配布処理の間に自然に発生すると予期される場合には、アタックは、「非意図的」と考えられる。非意図的なアタックの例としては、（１）クロッピング、スケーリング、ＪＰＥＧ圧縮、フィルタリングなどが行われる電子透かしが埋め込まれたコンテンツ、（２）テレビジョン・ディスプレイでの視聴のためにＮＴＳＣ／ＰＡＬ  ＳＥＣＡＭ形式に変換されたり、ＭＰＥＧ圧縮またはＤＩＶＸ圧縮、リサンプリングなどが行われたりする電子透かしが埋め込まれたコンテンツが挙げられる。その一方で、アタックが電子透かしの目的を妨げるために故意に行われる場合には、アタックは、「意図的」であり、アタックを行っている者は、不正取得者、または、海賊行為者である。意図的なアタックの３つの種別は、不正な埋め込み、不正な検出、さらに、不正な除去である。本発明は、不正な除去、即ち、電子透かしを除去したり、その検出に支障を及ぼしたりする（即ち、電子透かしがコンテンツ内に依然として存在するが、検出器によって容易に取得されなくなる）ことに関する。不正な除去のアタックは、一般的に、電子透かしを読めなくする一方で、コンテンツの知覚的なダメージを最小限にする目的で行われる。アタックの例としては、検出器との同期をとることが困難にするためにコンテンツに対して与えられる、ライン除去／追加および／またはローカル回転／スケーリングを小さく、知覚できないように組み合わせたものが挙げられる（多くの電子透かし検出器は、脱同期に対して敏感である）。
【０００４】
アタックの１つのタイプは、各々に含まれる異なる電子透かし情報に対し、偽装を行うため、または、スクランブルをかけることを意図して複数の異なるコピーが組み合わせられる共謀アタックである。さらに、アタッカは、共謀行為が行われたコピーに対して追加的な処理を行い、その後、この共謀行為が行われたコピーを再配布することがある。追加的な処理は、フォレンシック符号の検出されたビット中にエラーを生じさせることがある。慎重な設計がなされてない場合には、フォレンシック電子透かし埋め込みシステムは、２、３人の共謀者（ｃｏｌｌｕｄｅｒ）によるアタックにより、容易に破られてしまう。
【０００５】
従来技術は、Ｂｏｎｅｈ‐Ｓｈａｗによるフォレンシック・マーキング符号に取り組んでおり、Ｔａｒｄｏｓは、共謀攻撃に対する耐性を有するように設計されている。しかしながら、Ｂｏｎｅｈ‐Ｓｈａｗのアプローチは、非常に長い符号を必要とし、マルチメディア信号に適用された場合には、共謀行為に対する耐性が低いという欠点がある。即ち、少数の共謀者のみでシステムを破ることができる。Ｔａｒｄｏｓのアプローチは、共謀行為に対する耐性が良好であり、必要な符号長がより短い。しかしながら、符号生成および検出の間のその演算量ストレージの消費は、比較の対象となるエラー訂正符号（ＥＣＣ：Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅ）に基づくフォレンシック符号の１万倍にもなる。ＨｅおよびＷｕの提案するＥＣＣに基づくフォレンシック・マーキングは、バイナリ内部符号を使用するのではなく、ガウス・スペクトラム拡散埋め込みを使用して符号シンボルを担持する。このスキームは、特に、スペクトラム拡散埋め込みを使用するため、他の埋め込みスキームには適用できないことがある。共謀行為に対して耐性を有する電子透かしを生成するためのバイナリ内部符号であって、演算が効率的に行われ、妥当な長さを有するバイナリ内部符号を構成する技術を開発することが有用であろう。
【発明の概要】
【０００６】
本発明は、既存のスキームにより上記のように生ずる問題点や問題事項に対処し、ＥＣＣ外部符号と共に使用するように設計された内部バイナリ直交符号に関する。
【０００７】
複数のシンボルを使用して複数のユーザの各々のための固有の符号を生成し、複数のシンボルを表す複数の符号を生成し、複数の符号を複数のユーザの各々のための固有の符号に置換し、複数のユーザの各々のための符号語を生成するために、置換の結果として得られた符号を並べ替え、符号語をディジタル・コンテンツに埋め込むことを含む、方法および装置が開示される。２番目の生成動作は、第２のシンボルが後に続く第１のシンボルの文字列を生成することをさらに含み、第１のシンボルは全て１であり、第２のシンボルは全て−１であり、第１のシンボルの数は第２のシンボルの数と同じであり、第２のシンボルが後に続く第１のシンボルの長さが符号の長さよりも小さい場合には、第２のシンボルが後に続く第１のシンボルは符号長が満たされるまで繰り返される。
【０００８】
本発明は、添付図面と併せて以下の詳細な説明を読むことによって最良に理解できるであろう。図面は、以下に概略的に説明する図を含む。各図において、同様の参照符号は、同様の要素を表す。
【図面の簡単な説明】
【０００９】
【図１】電子透かし埋め込み処理を示す図である。
【図２】電子透かし検出処理を示す図である。
【図３Ａ】ＥＣＣに基づく符号化器のための例示的な外部符号を描いた図である。
【図３Ｂ】ＥＣＣに基づく符号化器のための直交内部符号を描いた図である。
【図３Ｃ】内部符号と外部符号の組み合わせを描いた図である。
【図３Ｄ】ＥＣＣに基づく符号化器メカニズムのランダム化を描いた図である。
【図４】本発明の原理に従ったＥＣＣに基づく符号の生成を描いた図である。
【図５】本発明の原理に従って動作するＥＣＣに基づく符号生成のための装置のブロック図である。
【図６】本発明の原理に従って生成されたＥＣＣに基づく符号を使用した指数符号の構成を描いたフローチャートである。
【図７】相異なる符号相関および相異なる内部符号を有する本発明のＥＣＣに基づく各符号の検出確率の下限およびシミュレーション結果を示す図である。
【図８】５人の共謀者によるマジョリティ・アタック（ｍａｊｏｒｉｔｙ  ａｔｔａｃｋ）を]受けた際のＴａｒｄｏｓ符号、改良された本発明のＥＣＣに基づく符号、さらに、ＢＳ符号の検出確率を示す図である。
【図９】５人の共謀者によるインターリービング・アタック（ｉｎｔｅｒｌｅａｖｉｎｇ  ａｔｔａｃｋ）を受けた際のＴａｒｄｏｓ符号、改良された本発明のＥＣＣに基づく符号、さらに、ＢＳ符号の検出確率を示す図である。
【発明を実施するための形態】
【００１０】
ここで使用する「／」は、同一または同様の要素または構造に対する代替的な名称を表す。即ち、「／」は、本明細書において、「または」と同様の意味で使用されることがある。ディジタル・フォレンシック符号／電子透かしは、不正な配布または再配布のためにマルチメディア・コンテンツを不正利用するユーザを識別する技術において使用することができる。このフォレンシック符号／電子透かしは、通常、様々なアタックに対して堅牢に設計された電子透かし技術を用いてコンテンツに埋め込まれる。このようなディジタル・フォレンシック符号に対するアタックの一種は、共謀行為であり、これは、同一のコンテンツの幾つかの異なるマーキングを行ったコピーを組み合わせて、ディジタル・メディア・コンテンツの正規ソースを識別するための、埋め込まれたフォレンシック電子透かし情報を壊そうとするものである。マルチメディア・フォレンシック符号設計における特別な課題は、保護されたデータがマルチメディアであるときに、通常、誤ったチャネルを形成する共謀行為の後に共謀者が後処理を適用する点にある。例えば、共謀者は、マルチメディアを圧縮して、共謀行為が行われたコピーを再配布する前にデータ・サイズを小さくする。従って、チャネル・エラーに対して堅牢な共謀行為に対して耐性を有するフォレンシック符号を設計することが重要である。
【００１１】
一般的に、広く検討されているものとして、２種類の共謀アタックが存在する。これらは、インターリービング・アタックおよびマジョリティ・アタックである。インターリービング・アタックにおいては、共謀者は、有効なフォレンシック符号／電子透かしの検出を避けようとして、大体同じ分担で、自己のフォレンシック・データのコピーをビット単位で提供する。この種類のアタックは、２人以上の共謀ユーザが存在する際に開始することができる。この方法は、フォレンシック符号検出において、善良な正規分配者を、保護されたディジタル・コンテンツを不正利用したソースであるとする、誤ったポジティブな検出結果を生じさせるおそれがある。マジョリティ・アタックにおいては、各共謀者間のビット状態の大部分が選択され、保護されたディジタル・コンテンツの最終的な共謀行為が行われたコピーに置かれるように、共謀者は、ビット単位で各々のフォレンシック・データを組み合わせる。この種類のアタックは、３人以上の共謀行為を行うユーザが存在する際に開始することができる。この方法もまた、フォレンシック符号語検出において誤ったポジティブな結果を生じさせることがある。
【００１２】
本発明は、ディジタル・マルチメディア信号に埋め込まれる電子透かしに対するマジョリティ・アタックおよびインターリービング・アタックなどの様々な共謀アタックに対して耐性を有するＥＣＣに基づくフォレンシック符号用の内部符号を構成する方法および装置に関する。ＥＣＣに基づくフォレンシック符号のための内部符号を構成するために、２つの直交バイナリ符号の置換（コンカチネーション（連結）と呼ばれることもある）が使用される。
【００１３】
図１および図２は、フォレンシック符号の一般的な埋め込みおよび検出処理を示している。埋め込み処理の間、各ユーザのための符号語が生成される。全ての符号語のセット（集合）は、集合的に、符号ブックと呼ばれる。ユーザ入力インデックスに基づいて、このユーザのための符号語は、符号ブックから取得され、ユーザの自己の符号語がオリジナルの信号にディジタル電子透かし技術を通じて埋め込まれる。この処理の出力は、対応するユーザのための電子透かしが埋め込まれた信号である。
【００１４】
検出処理の間、電子透かし検出器にテスト信号が入力され、テスト・フォレンシック符号語を抽出する。符号ブックが作成または取得され、各ユーザのフォレンシック符号語が共謀者検出器においてテスト・フォレンシック符号語との比較のために使用される。出力は、責任を問われるべき共謀者である。
【００１５】
図１は、コンピューティング・システムを使用して実施されるフォレンシック符号語／電子透かしを埋め込むシステム１００のブロック図を描いている。まず、各ユーザのための符号語が生成され、符号ブックに保存される。一実施の形態においては、符号ブックは、ディジタル・ビデオのプロダクトの正規ユーザのための符号語の幾らかまたは全てを表すディジタル情報である。入力ユーザ・インデックス／識別子（ＩＤ：ｉｄｅｎｔｉｆｉｅｒ）に基づき、識別されたユーザのための符号語が生成される（１０５）。このような符号語の生成は、メモリ内に格納されたデータを取得することによって実行されるか、電子透かし埋め込み処理が開始した際に生成することができる。ユーザの符号語は、次に、符号化器１１０において、オリジナルのコンテンツと組み合わされる。符号化の結果として、符号語がオリジナルのコンテンツに埋め込まれた電子透かしが埋め込まれた信号が得られる。符号化器１１０の出力は、対応する正規ユーザによる配布のために電子透かしが埋め込まれた信号を有するコンテンツである。
【００１６】
図２は、電子透かし／フォレンシック符号の一般的な符号検出器２００を示している。一般的な符号検出器２００は、結果の生成および表示のためにコンピュータ・システム上で実施することができる。まず、疑いのある信号（ｓｕｓｐｅｃｔ  ｓｉｇｎａｌ）がフォレンシック符号／電子透かし抽出器２０５に入力される。疑いのあるビデオから電子透かし情報が抽出される。ユーザの符号語の全ては、符号語発生器２１０によって生成される。この符号語生成器は、図１の参照符号１０５に示されているものと同様の装置とすることができる。次に、アタッカ検出器２１０は、アタッカの符号語を検出し、アタッカの身元を判定するために、各符号語が全ての符号語のリストと比較される。疑いのある共謀者の身元が表示される（２２０）。このような表示は、限定するものではないが、端末／モニタまたは印刷機上に表示することを含む。この例においては、ユーザは、符号化されたコンテンツの正規ユーザである。例えば、ユーザは、映画などのディジタル・コンテンツの正規配布者であることが考えられる。海賊行為が行われたコンテンツが発見された場合、疑いのあるコンテンツにおける符号語に対応する符号語を有する１人以上の正規ユーザが共謀者であろう。ここで、共謀者という用語は、コンテンツの海賊行為者／不正取得者にコンテンツのコピーを入手させる正規ユーザを指す。
【００１７】
図３Ａ〜図３Ｄは、基本的なＥＣＣに基づくフォレンシック符号を生成する一般的な方法を描いている。図３Ａの第１のステップは、Ｌ個のシンボルおよびｑ個のアルファベット｛ｆ０，ｆ１，・・・ｆｑ−１｝を有するＮ人のユーザのためのＥＣＣ外部符号を生成することである。一実施の形態においては、図３Ａの外部符号は、その大きな最小距離のため、リードソロモン（ＲＳ：Ｒｅｅｄ‐Ｓｏｌｏｍｏｎ）符号として構成される。図３Ｂは、基本的なＥＣＣのためのアルファベットとして使用されるべき例示的なバイナリ内部符号を描いている。ここで、各ゼロ（０）は−１の値として描かれている。図３Ｃは、図３Ｂの各内部符号を各ユーザのための図３Ａの外部符号に置換した結果を示している。これは、ユーザのための基本的なＥＣＣに基づく符号語を生成する１つの方法である。一実施の形態においては、基本的なＥＣＣに基づく符号語は、各ユーザのためのビットをランダムに並べ替えることによってさらに操作することができる。図３Ｄは、ユーザ１のための図３Ｃの符号ビットのランダムな並べ替えを描いている。この「ランダムな」並べ替えは、ランダマイザによって実施することができ、一般的に、符号語構造がアタッカによって破られることを阻止するために実行される。図３Ｄの処理の後の結果は、各ユーザのランダム化された基本的なＥＣＣに基づく符号語である。
【００１８】
再び図３Ｂおよび内部符号を参照すると、値＋１／−１を有するｑ個の直交バイナリ符号および長さｌを使用することにより、ｑ個のアルファベットが変更され、内部符号が外部符号に置換されている。符号の全長はＬｌビットであり、ユーザの合計人数は、Ｎ＝ｑｔである。ここで、ｔは、外部リードソロモン符号の次数である。指数直交符号と呼ばれるｑ個の内部符号語は、共謀者の情報を可能な限り保持するように設計されている。この指数直交内部符号の各列は、１と−１の全ての２ｑ個の想定される組み合わせからなり、１つの列は、１つのビット位置でのｑ個の符号語からのビットに対応する。従って、符号の符号長は、ｌ＝２ｑである。基本的なＥＣＣのための図３Ｂに示されている直交内部符号は、以下のように構成される。ｉ番目の符号語ｆｉ−１については、最初の２ｑ−１ビットは１であり、次の２ｑ−１ビットは−１である。次に、同じ符号が２ｉ―１回繰り返され、最終的に、２ｑビットとなる。ｑ＝３の内部符号行列を図３Ｂに示す。最初の符号語ｆ０の最初の４つのビットは１であり、残りのビットは−１である。２番目の符号語ｆ１の最初の２ビットは１であり、次の２つは−１である。次に、符号パターンは１度繰り返される。３番目／最後の符号語ｆ３は、１から始まって、１と−１とが繰り返される。これにより、基本的なＥＣＣ符号語のための内部符号が生成される。
【００１９】
相関に基づく検出器がＥＣＣフォレンシック符号スキームにおいて使用され、ユーザの符号語を検出して共謀者を識別する。ｙを共謀行為が行われたコピーから抽出されたフォレンシック符号であるとし、ｘｉをユーザｉのフォレンシック符号であるとし、Ｕを全てのユーザの集合であるとする。ユーザｉの検出統計は、以下のように表される。
【数１】
0005182975.tif 000002
ここで、
【数２】
0005182975.tif 000003
および
【数３】
0005182975.tif 000004
は、ｘｉおよびｙのｊ番目のシンボルにそれぞれ対応する符号語である。最大値検出器において、ユーザｉは、最高の検出統計値、即ち、Ｔｉ≧Ｔｋ  ∀ｋ∈Ｕであると、共謀者であるとして責任を問われる。閾値検出器においては、ユーザｉの統計値が閾値ｈよりも大きい場合、即ち、Ｔｉ≧ｈである場合、ユーザｉが共謀者であると責任を問われる。等式（１）を使用した検出は、ソフト検出と呼ぶことができる。
【００２０】
ＥＣＣに基づくバイナリ・フォレンシック符号について、内部符号が指数直交符号であれば、相対距離、即ち、最小距離を外部ＥＣＣ符号の符号長で割ったものが大きくなるほど、システムのパフォーマンスが良好となる。リードソロモン符号については、アルファベットのサイズｑを大きくすることによって、相対距離を増加させることができる。しかしながら、指数バイナリ直交符号の符号長は２ｑであり、アルファベットのサイズを大きくすると符号長が大きくなりすぎる。従って、２つの直交バイナリ符号を置換／コンカチネートすることによって生成されるバイナリ直交内部符号が提案される。
【００２１】
例としてマジョリティ共謀を使用すると、ＥＣＣに基づく符号の検出確率の理論的な分析は以下の通りである。他のアタックの下でのパフォーマンス分析も同様に行われる。
【００２２】
共謀行為が行われたコピーのマルチメディア処理は、二元対称通信路（ＢＳＣ：ｂｉｎａｒｙ  ｓｙｍｍｅｔｒｉｃ  ｃｈａｎｎｅｌ）としてモデル化される。即ち、０が１として認識される確率（そして、１が０として認識される確率）はδであり、０が０として認識される確率（そして、１が１として認識される確率）は１−δである。ｌを内部符号の長さであるとし、δを二元対称通信路のビット・エラー率（ＢＥＲ：ｂｉｔ  ｅｒｒｏｒ  ｒａｔｅ）であるとし、ｘを内部符号であるとし、ｙ（ｊ）をｊ番目のシンボルのマジョリティ共謀行為が行われた内部符号であるとする。ｙ’（ｊ）は、ＢＥＲ＝δでｙ（ｊ）がＢＳＣを通った後に結果として得られる内部符号である。ユーザｉの検出統計値、Ｔｉは、等式（２）の場合のように、
【数４】
0005182975.tif 000005
として得ることができる。ここで、
【数５】
0005182975.tif 000006
である。
【００２３】
ＢＳＣは、確率δでビットをフリッピングすることによってモデル化することができる。ｙ’（ｊ）およびｘ（ｊ）が＋１／−１であるとき、フリッピング処理および乗算の順番は、切り替える／逆にすることもできる。従って、＜ｙ’（ｊ），ｘ（ｊ）＞  ＝
【数６】
0005182975.tif 000007
となる。ここで、ｙ’（ｊ）（ｉ）、ｙ（ｊ）（ｉ）、ｘ（ｊ）（ｉ）は、それぞれ、ｙ’（ｊ）、ｙ（ｊ）、およびｘ（ｊ）のｉ番目のビットである。＜ｙ’（ｊ），ｘ（ｊ）＞は、ＢＳＣを介してｌビット単位の積ｙ（ｊ）（ｉ）×ｘ（ｊ）（ｉ），１≦ｉ≦ｌを送信し、これらを合計するというように処理を取り扱うことによって算出することができる。ａｉを確率変数とし、ｙ（ｊ）（ｉ）＝ｘ（ｊ）（ｉ）であるときに、ｙ（ｊ）（ｉ）×ｘ（ｊ）（ｉ）は、ＢＥＲ＝δでＢＳＣを通過する。さらに、ｂｉを確率変数とし、ｙ（ｊ）（ｉ）＝−ｘ（ｊ）（ｉ）であるときに、ｙ（ｊ）（ｉ）×ｘ（ｊ）（ｉ）は、ＢＥＲ＝δでＢＳＣを通過する。従って、＜ｙ’（ｊ），ｘ（ｊ）＞は、ａｉとｂｉの合計としてモデル化することができる。ここで、ａｉとｂｉは、以下のようになる。
【数７】
0005182975.tif 000008
ここで、“ｗ．ｐ．”は、「〜の確率（ｗｉｔｈ  ｐｒｏｂａｂｉｌｉｔｙ）」を表す。
【００２４】
従って、ａｉの期待値は、ｌ−２δであり、分散は、４δ（１−δ）である。ｂｉの期待値は、２δ−１であり、分散は、４δ（１−δ）である。例えば、ｙ（ｊ）およびｘ（ｊ）が直交するならば、ｙ（ｊ）およびｘ（ｊ）は、同一のビットをｌ／２の各位置で共有し、他のｌ／２の各位置で異なるビットを有する。従って、＜ｙ’（ｊ），ｘ（ｊ）＞は、ｌ／２の独立同一分布（ｉ．ｉ．ｄ．（ｉｎｄｅｐｅｎｄｅｎｔ  ｉｄｅｎｔｉｃａｌ  ｄｉｓｔｒｉｂｕｔｉｏｎ））ａｉおよびｌ／２の独立同一分布ｂｊの合計としてモデル化することができる。内部符号の符号長は、２１６の次数であるため、中心極限定理を適用するのに十分に長く、ガウス確率変数として、モデルＴｉ（ｊ）＝
【数８】
0005182975.tif 000009
となる。
【００２５】
ＲＳ外部符号が最小距離Ｄで等しく離れており、従って、任意の２人のユーザの外部符号間で正確にＬ−Ｄの共有されたシンボルが存在する最悪の場合のシナリオを考える。所与の１つの符号語ｚおよびランダムに選択された別の符号語ｚ’、Ｐ［ｚ（ｉ）＝ｚ’（ｉ）］が全ての１≦ｉ≦Ｌについて同じであるという意味において、各ＲＳ符号が対照的であると仮定する。ここで、ｚｉおよびｚ’ｉは、それぞれ、ｚおよびｚ’のｉ番目のシンボルである。このような仮定の下で、外部符号の全ての場合の確率を算出することができ、各ユーザｉのためのＴｉの分布を得ることができる。例えば、２人の共謀者が存在する場合には、Ｐ［共謀者は、外部符号におけるＬ−Ｄのシンボルを共有する］＝１である。結果として、
【数９】
0005182975.tif 000010
となり、これもまた、ガウス確率変数としてモデル化することができる。従って、各ユーザの検出統計値は、ガウス確率変数としてモデル化することができ、検出確率は、最高の検出統計値が共謀者に属する確率を算出することによって得ることができる。
【００２６】
以下の説明において、例を挙げて本発明の符号分析処理を示す。２２０のユーザが存在し、３人の共謀者がマジョリティ・アタックを仕掛けると仮定すると、リードソロモン（ＲＳ）符号は、アルファベットのサイズが２４であり、符号長が１５であるように構成される。従って、ＲＳ外部符号の最小距離は１１であり、外部符号相関は４／１５である。ｘ１（ｊ）、ｘ２（ｊ）、ｘ３（ｊ）が３人の共謀者のためのｊ番目のシンボルの内部符号とし、Ｘ＝｛ｘ｜ｘは内部符号であり、ｘ≠ｘ１（ｊ）、ｘ２（ｊ）、ｘ３（ｊ）｝であるとする。各シンボル位置につき、３人の共謀者は、（第１の場合）３つの相異なる内部符号を有し、（第２の場合）これらの２つが同一の内部符号を共有し（ｘ３（ｊ）＝ｘ２（ｊ））、または、（第３の場合）これらの全てが同じ符号を有する（ｘ１（ｊ）＝ｘ２（ｊ）＝ｘ３（ｊ））。
マジョリティ・アタックの下では、第１の場合には、ｘ１（ｊ）≠ｘ２（ｊ）、ｘ２（ｊ）≠ｘ３（ｊ）、およびｘ１（ｊ）≠ｘ３（ｊ）であるとき、
＜ｙ，ｘ＞＝０  ∀ｘ∈Ｘであり、
＜ｙ（ｊ），ｘ１（ｊ）＞＝＜ｙ（ｊ），ｘ２（ｊ）＞＝＜ｙ（ｊ），ｘ３（ｊ）＞＝ｌ／２である。（４）
後者の２つの場合、ｙは、Ｘにおける任意の内部符号と直交するｘ３と等しくなり、第２の場合にはさらにｘ１（ｊ）と等しくなり、＜ｙ（ｊ），ｘ３（ｊ）＞＝ｌである。
【００２７】
共謀行為に関わりのない符号語ｘ（ｊ）についての検出統計Ｔｉ（ｊ）の分布を見ると、ｘ（ｊ）は、善良なユーザの符号語Ｘからの符号語、あるいは第２の場合のｘ１（ｊ）であり、即ち、ｘ１（ｊ）≠ｘ２（ｊ）＝ｘ３（ｊ）のとき、ｘ（ｊ）＝ｘ１（ｊ）である。従って、第２の場合におけるｘ（ｊ）∈Ｘや第３の場合におけるｘ（ｊ）∈Ｘについて、
【数１０】
0005182975.tif 000011
である。ｌが十分に長い場合には、中心極限定理によって、
【数１１】
0005182975.tif 000012
は、Ｎ（１−２δ，４δ（１−δ）／（ｌ／２））によって与えられる正規分布／ガウシアン分布に従い、さらに、
【数１２】
0005182975.tif 000013
は、Ｎ（２δ―１，４δ（１−δ）／（ｌ／２））によって与えられる正規分布／ガウス分布に従う。ここにおいて使用される表記Ｎ（ｍ，ｖ）において、ｍは、平均／期待値であり、ｖは分散である。よって、
【数１３】
0005182975.tif 000014
は、Ｎ（０，４δ（１−δ）／（ｌ／４）によって与えられる正規分布／ガウス分布に従う。従って、
【数１４】
0005182975.tif 000015
は、上記第２の場合において、ユーザｉのｊ番目のシンボルがｘｉ（ｊ）∈ＸまたはＸｉ（ｊ）∈Ｘ∪｛Ｘ１（ｊ）｝であれば、Ｎ（０，４δ（１−δ））によって与えられる正規分布／ガウス分布に従う。
【００２８】
共謀行為が行われたコピーに寄与する符号語ｘ（ｊ）の検出統計値
【数１５】
0005182975.tif 000016
は、以下のように導出される。３人の共謀者の符号語が別個である第１の場合、即ちｘ１（ｊ）≠ｘ２（ｊ）、ｘ２（ｊ）≠ｘ３（ｊ）、およびｘ１（ｊ）≠ｘ３（ｊ）である場合、＜ｙ’（ｊ），ｘ１（ｊ）＞／）（ｌ／４）は、Ｎ（２（１−２δ），１６δ（１−δ）／（ｌ／４））によって与えられる正規分布／ガウス分布に従う。
従って、
【数１６】
0005182975.tif 000017
は、
【数１７】
0005182975.tif 000018
によって与えられる正規分布／ガウス分布に従い、
【数１８】
0005182975.tif 000019
および
【数１９】
0005182975.tif 000020
もまた、対称に、同じ分布を有する。即ち、共謀行為が行われたシンボルが導出され、３つの全てのシンボルが異なる場合には、検出統計値の平均は、
【数２０】
0005182975.tif 000021
となる。第２の場合および第３の場合においては、Ｘ１（ｊ）≠Ｘ２（ｊ）＝Ｘ３（ｊ）、または、ｘ１（ｊ）＝ｘ２（ｊ）＝３（ｊ）、ｙ＝ｘ３（ｊ）である。共謀者３については、＜ｙ’（ｊ），ｘ３（ｊ）＞／ｌは、Ｎ（１−２δ，４δ（１−δ）／ｌ）によって与えられる正規分布／ガウス分布に従う。
【数２１】
0005182975.tif 000022
は、
【数２２】
0005182975.tif 000023
によって与えられる正規分布／ガウス分布に従う。つまり、共謀行為が行われたシンボルが完全に共謀者のうちの１人から来る場合、即ち、共謀者のシンボルの全てが同じ場合、または、そのうちの２つが同じである場合には、検出統計値の平均は、
【数２３】
0005182975.tif 000024
となる。双方の場合の分散は同じである。
【００２９】
表記（ｃ１，ｃ２，ｃ３）は、１つのシンボル位置での３人の共謀者の間でのシンボル分布を表す。（１，１，１）は、全ての３人の共謀者が異なる内部符号を有することを意味し、（２，１，０）は、２人の共謀者が同じ内部符号を共有し、３番目の共謀者が異なる符号を有することを意味する。さらに、（３，０，０）は、全ての３人の共謀者が同じ内部符号を共有することを意味する。単純に説明するために、ＲＳ符号が等距離を有し、これが符号１１の最小距離であると仮定する。従って、符号語の各対の間で４つのシンボルが共有される。一般概念から外れることなく、最初の４つのシンボルが最初の２人の共謀者、共謀者１および共謀者２の間で共有され、共有されたシンボルの集合をｓｙｍ１２で表す。同様に、共謀者２と共謀者３との間で共有されたシンボルの集合をｓｙｍ１３で表し、共謀者２と共謀者３との間で共有されたシンボルの集合をｓｙｍ２３で表す。第３の共謀者、即ち、共謀者３が参加する際、幾つかの場合が存在する。
【数２４】
0005182975.tif 000025
である。そのとき、３人の共謀者の全てが同一のシンボルを共有するシンボル位置は存在しない、即ち、１５個のシンボル位置において、（３，０，０）の数である♯（３，０，０）は０である。ペア単位の共有されたシンボル数を４に維持するために、
【数２５】
0005182975.tif 000026
となる。結果として、１５個のシンボル位置の中で、｛ｓｙｍ１２∪ｓｙｍ１３∪ｓｙｍ２３｝における１２個の位置が（２，１，０）を有し、残りの３個の位置は、（１，１，１）である。従って、イベント｛＃（３，０，０）＝０｝の確率は、以下のように算出することができる。
【数２６】
0005182975.tif 000027
となり、
同様に、
【数２７】
0005182975.tif 000028
となり、
【数２８】
0005182975.tif 000029
となり、
【数２９】
0005182975.tif 000030
となり、
【数３０】
0005182975.tif 000031
となる。
Ｋ≠０、１、２、３、４である全てにつき、Ｐ[＃（３，０，０）＝ｋ]＝０
となる。                                                        （５）
【００３０】
イベント＃（１，１，１）＝１１、＃（２，１，０）＝０、＃（３，０，０）＝４を例にとる。この場合、３人の共謀者は、最初の４つのシンボル位置のために同じシンボルを有する。内部符号分析に基づき、３人の共謀者Ｔｃｏｌｌｕｄｅｒ１、Ｔｃｏｌｌｕｄｅｒ２、およびＴｃｏｌｌｕｄｅｒ３の検出統計値は、同じ分布
【数３１】
0005182975.tif 000032
を有する。善良なユーザとして、幾つかの場合／可能性がある。
【００３１】
１．善良なユーザもまた、以下の図に示すように、最初の４つのシンボル位置については、共謀者と同じシンボルを有する。内部符号分析に基づいて、この善良なユーザのためのＴｉの平均は
【数３２】
0005182975.tif 000033
となるであろう。これは、以下の確率で正規／ガウス分布
【数３３】
0005182975.tif 000034
に従ったＴｉ分布に対応する。
【数３４】
0005182975.tif 000035
【表１】
0005182975.tif 000036
【００３２】
２．善良なユーザは、以下の図に示すように、最初の４つのシンボル位置のうちの最初の３つについては、共謀者と同じシンボルを有する。任意の符号語対の間で合計４つのシンボルの一致を維持するために、善良なユーザは、３人の共謀者の各々と一致する残りの１１個の位置において１つのシンボルを有していなければならない。これらの一致したシンボル位置は、重複することはできない。そこで、この善良なユーザのためのＴｉの平均は、
【数３５】
0005182975.tif 000037
となるであろう。これは、以下の確率で正規／ガウス分布
【数３６】
0005182975.tif 000038
に従ったＴｉ分布に対応する。
【数３７】
0005182975.tif 000039
【表２】
0005182975.tif 000040
【００３３】
３．善良なユーザは、以下の図に示すように、最初の４つのシンボル位置のうちの最初の２つについては、共謀者と同じシンボルを有する。任意の符号語対の間で合計４つのシンボルの一致を維持するために、善良なユーザは、３人の共謀者の各々と一致する残りの１１個の位置において２つのシンボルを有していなければならない。これらの一致したシンボル位置は、重複することはできない。そこで、この善良なユーザのためのＴｉの平均は、
【数３８】
0005182975.tif 000041
となるであろう。これは、以下の確率で正規／ガウス分布
【数３９】
0005182975.tif 000042
に従ったＴｉ分布に対応する。
【数４０】
0005182975.tif 000043
【表３】
0005182975.tif 000044
【００３４】
４．善良なユーザは、以下の図に示すように、最初の４つのシンボル位置のうちの最初の２つについては、共謀者と同じシンボルを有する。任意の符号語対の間で合計４つのシンボルの一致を維持するために、善良なユーザは、３人の共謀者の各々と一致する残りの１１個の位置において３つのシンボルを有していなければならない。これらの一致したシンボル位置は、重複することはできない。そこで、この善良なユーザのためのＴｉの平均は、
【数４１】
0005182975.tif 000045
となるであろう。これは、以下の確率で正規／ガウス分布
【数４２】
0005182975.tif 000046
に従ったＴｉ分布に対応する。
【数４３】
0005182975.tif 000047
【表４】
0005182975.tif 000048
【００３５】
同様に、イベント＃（３，０，０）＝ｋ（ここで、ｋ＝０、１、２、３）についての、３人の共謀者と、各善良なユーザの検出統計値を得ることができる。上記の全ての場合で、全てのユーザの検出統計値を考慮すると、等距離の仮定の下でのＥＣＣに基づく符号の検出確率を得ることができる。なお、実際のＥＣＣ符号のペア単位の距離は、常に最小距離と同じになるものではない。これらの多くは、仮定された距離よりも大きくなる。また、符号語の組み合わせの合計の数は、
【数４４】
0005182975.tif 000049
となる。これは、ユーザの合計人数の１．０５×１０６よりも大きい。従って、全ての場合が符号ブックに表れているわけではない。結果として、得られる確率分析は、図７に示されているような実際のパフォーマンスの下限である。ここで、分析の数値的な評価を円が付けられた破線で示しており、２００回の繰り返しに基づくシミュレーション結果を円が付けられた実線で示している。
【００３６】
３人の共謀者によって仕掛けられるマジョリティ・アタックについては、以下のように要約される。
【００３７】
Ｄを外部符号の最小距離であるとし、Ｌを外部符号の長さであるとし、ｌを指数直交内部符号の長さであるとする。共謀者の検出統計値Ｔｃｏｌｌｕｄｅｒは、
【数４５】
0005182975.tif 000050
によって与えられる正規分布／ガウス分布に従い、善良なユーザの検出統計値は、幾つかの可能性を有し、最も高い平均を有するもの
【数４６】
0005182975.tif 000051
は、Ｄ＜Ｌ‐３の場合は、
【数４７】
0005182975.tif 000052
によって与えられる正規分布／ガウス分布に従い、
【数４８】
0005182975.tif 000053
は、Ｄ≧Ｌ‐３の場合は、
【数４９】
0005182975.tif 000054
によって与えられる正規分布／ガウス分布に従う。従って、Ｔｃｏｌｌｕｄｅｒの平均と
【数５０】
0005182975.tif 000055
との間の差は、Ｄの非減少関数（ｎｏｎ‐ｄｅｃｒｅａｓｉｎｇ  ｆｕｎｃｔｉｏｎ）である。フォレンシック検出器は、最大の検出統計値を有するユーザを選択するため、Ｔｃｏｌｌｕｄｅｒの平均と
【数５１】
0005182975.tif 000056
との差が大きいほど、共謀者追跡パフォーマンスが良好となる。
【００３８】
上述した分析から、外部符号の最小距離が重要な役割を果たすことが分かる。例えば、最小距離が符号長と等しい場合、即ち、全体の符号相関が０である場合、任意の善良なユーザｉのためのＴｉの平均が０に減らされ、共謀者のＴｃｏｌｌｕｄｅｒの平均は、
【数５２】
0005182975.tif 000057
となる。従って、全体的な検出確率は増加する。次に、アルファベットのサイズ３２、次数４、および外部符号長３１を有するＲＳ符号を用いることによって符号相関を減少させることについて検討する。この状況においては、直交内部符号が依然として使用される場合には、全体の相関は、３／３１になる。ＲＳ符号がアルファベットのサイズ１６、次数５、および符号長１５を有する同じ発明者による従来の作業において使用される符号と比較して、相関は、０．１７（４／１５−３／３１）だけ減らされる。従って、この新しい符号設定を用いて、より良好なパフォーマンスが期待される。しかしながら、本明細書において説明されるバイナリ内部符号が依然として使用される場合には、符号の全長は、３１×２３２＝１．３×１０１１に増加する。これは、ストレージおよび演算量の点では、許容できるものを超えている。従って、同じ符号長を維持するために、より短い符号長を有する直交内部符号のファミリーが提案される。
【００３９】
値±１をとるバイナリ直交符号のセットを考えると、値「１」をとるビットがビットシーケンスＶによって置き換えられ、「−１」のビットが−Ｖで置き換えられる場合には、各符号は、依然として互いに直交している。さらに、直交符号の２つのセットがコンカチネートされている場合には、コンカチネートされた符号もまた、直交している。ここで、ＸおよびＹのコンカチネーション／行列乗算を
【数５３】
0005182975.tif 000058
で示し、以下のように定義する。
【数５４】
0005182975.tif 000059
【００４０】
従って、ｑ／ｑｃ指数直交内部符号を他のｑｃ直交シーケンス（例えば、限定するものではないが、アダマール（Ｈａｄａｍａｒｄ）行列のような直交行列）でコンカチネート／乗算すると、ｑ個の直交内部符号が得られる。以下に、指数直交内部符号によってコンカチネート／乗算されるべき２つの直交符号を列挙する。
【００４１】
アダマール行列：アダマール行列は、ｑｃ＝２ｍ、ｍ∈Ｎのときに存在するｑｃ×ｑｃの直交行列である。ｑｃの次数を有するアダマール行列Ｈｑｃを、
【数５５】
0005182975.tif 000060
によって、再帰的に生成することができる。
ここで、
【数５６】
0005182975.tif 000061
である。Ｈｑｃがｑ／ｑｃの次数を有するオリジナルの内部符号によってコンカチネート／乗算される場合には、最終的な内部符号長は、２ｑ／ｑｃ×ｑｃになるであろう。この例においては、内部符号の必要な符号長は、２１５となり、アルファベットのサイズを３２に増加することによって外部符号相関が減らされるため、ｑｃ＝４が選択され、ｑ／ｑｃ＝８であり、コンカチネート／乗算された符号が２５回繰り返される。
【００４２】
指数直交内部符号：ｑ／ｑｃおよびｑｃの次数を有する２つの指数直交内部符号がコンカチネート／乗算される場合、結果として得られる符号は、符号長２ｑ／ｑｃ＋ｑｃで、次数ｑを有するであろう。この例においては、ｑｃ＝４が選択され、ｑ／ｑｃ＝８であり、コンカチネート／乗算された符号は２３回繰り返される。
【００４３】
これらの２つのコンカチネートされたバイナリ符号のいずれにおいても、符号長は、２ｑからｑｃ２ｑ／ｑｃまたは２ｑ／ｑｃ＋ｑｃに大幅に減らされる。
【００４４】
ｑ＝３２、ｑｃ＝４である２つの指数直交内部符号を例にとる。外部符号の各対につき、共有されたシンボルの数は３であり、外部符号相関は、３／３１である。全ての可能性が網羅的にサーチされ、マジョリティ・アタックを仕掛ける３人の共謀者が存在すると判定されると、共謀行為が行われた内部符号ｙ（ｊ）は、３人の共謀者の符号の関係にかかわらず、各ｘ∈Ｘに対して直交する。さらに、ｘ１（ｊ）≠ｘ２（ｊ）、ｘ２（ｊ）≠ｘ３（ｊ）、およびｘ１（ｊ）≠ｘ３（ｊ）である場合、＜ｙ（ｊ），ｘ１（ｊ）＞＝＜ｙ（ｊ），ｘ２（ｊ）＞＝＜ｙ（ｊ），ｘ３（ｊ）＞＝ｌ’／２である。ｌ’は、ｑ＝３２の内部符号長である。外部符号長は、３１にまで拡大されているため、内部符号長ｌ’は、１５ｌ／３１≒ｌ／２にまで短くならなければならない。従って、上述したものと同じ分析を適用して以下を導くことができる。
【数５７】
0005182975.tif 000062
となり、
【数５８】
0005182975.tif 000063
となり、
【数５９】
0005182975.tif 000064
となり、
【数６０】
0005182975.tif 000065
となる。
Ｋ≠０、１、２、３である全てにつき、Ｐ[＃（３，０，０）＝ｋ]＝０
となる。                                                        （６）
【００４５】
イベント＃（１，１，１）＝２８，＃（２，１，０）＝０、＃（３，０，０）＝３を例にとる。この場合、内部符号分析に基づくと、３人の共謀者Ｔｃｏｌｌｕｄｅｒ１、Ｔｃｏｌｌｕｄｅｒ２、およびＴｃｏｌｌｕｄｅｒ３の検出統計値は、同じ分布、
【数６１】
0005182975.tif 000066
を有する。善良なユーザｉの検出統計値は、以下のようになる。
Ｔｉは、確率
【数６２】
0005182975.tif 000067
で正規分布／ガウス分布
【数６３】
0005182975.tif 000068
に従い、
Ｔｉは、確率
【数６４】
0005182975.tif 000069
で正規分布／ガウス分布
【数６５】
0005182975.tif 000070
に従い、
Ｔｉは、確率
【数６６】
0005182975.tif 000071
で正規分布／ガウス分布
【数６７】
0005182975.tif 000072
に従い、
Ｔｉは、確率
【数６８】
0005182975.tif 000073
で正規分布／ガウス分布
【数６９】
0005182975.tif 000074
に従う。ここで、
【数７０】
0005182975.tif 000075
である。同様に、さらに、全てのイベント＃（３，０，０）（ここで、ｋ＝０、１、２）について、３人の共謀者と、各善良なユーザの検出統計値を得ることができる。
【００４６】
（６）における全ての場合で、全てのユーザの検出統計値が与えられると、ＥＣＣ符号の検出確率の下限が数値的に調べられる。この下限は、三角が付けられた破線により図７に示されている。同一の設定のシミュレーション結果が三角が付けられた実線による図７に示されている。なお、２つの曲線の間には差異が存在するが、その差異は、主に、分析におけるＲＳ符号の等距離の仮定から生じるものである。図７より、ＢＥＲ＝０．４であるとき、符号相関＝３／３１を有する符号の検出確率は、依然として１であり、その一方で、符号相関＝４／１５を有する符号が共謀者を完全には識別できないことが分かる。従って、符号相関を減少させることにより、ＥＣＣフォレンシック・マーキング符号のためのＢＳＣの下で共謀行為に対する耐性を有効に高めることができる。
【００４７】
図８および図９は、５人の共謀者により、それぞれマジョリティ・アタックおよびインターリービング・アタックを受けた際のＴａｒｄｏｓ符号、本発明の改良されたＥＣＣ符号、さらに、ＢＳ符号の共謀者追跡パフォーマンスを示している。ユーザの合計人数は２２０であり、Ｔａｒｄｏｓ符号とＢＳ符号の誤り警告の確率が１０−３に設定されている。本発明の改良されたＥＣＣ符号は、外部符号長３１を有する３２個のアルファベットと、内部符号として８次の指数直交符号の修正されたアダマール行列のコンカチネーション／乗算を使用する。ＢＥＲが０〜０．３２の範囲にあるテスト環境の下では、図８および図９から、本発明のＥＣＣ符号は、Ｔａｒｄｏｓ符号と同様に完全な検出を達成することが明らかである。従って、符号相関を減らす（外部符号の最小距離を増やす）ことにより、ＥＣＣ符号の共謀行為に対する耐性が大幅に改善する。これは、より多くのアルファベットを使用することによって達成することができる。相関は、（Ｌ−最小距離＋１）／Ｌに減らされる。外部符号最小距離Ｄ＝Ｌ−ｔ＋１は、概ねｑ−ｔ＝ｌｏｇｑＮｕに等しい。ここで、ｑ＝３２である。ｑ＝３２の指数内部符号長は、２ｑである。すなわち、２３２は、概ね４×１０９に等しい。符号の全長は、６×１０９未満とすべきであり、内部符号長は、２×１０５未満とすべきである。Ｔａｒｄｏｓ符号は、本発明の改良されたＥＣＣに基づく符号よりも１００００倍もの演算量およびストレージを使用することが分かった。
【００４８】
図４は、ＥＣＣに基づく処理を使用して、ユーザのフォレンシック符号ブックを生成する処理４００を描いている。この処理４００は、基本的なＥＣＣおよび本発明の態様に係る改良されたＥＣＣの双方のために有用である。処理４００は、図３Ａ〜図３Ｄにおいて描かれた処理に従う。ステップ４０５において、リードソロモン符号のような外部符号がｑ個のアルファベットを有するＮ人のユーザのために生成される。一般的には、外部符号の生成のための入力パラメータは、ユーザの数、アルファベットのサイズｑ、および所望の外部符号長を含む。ステップ４１０において、内部符号が生成される。ここで、外部符号のｑ個のアルファベットを表すためにｑ個のバイナリ内部符号語が生成される。ゼロ（０）の状態のために値−１が使用され、使用されるアルゴリズムに対応する。一般的には、内部符号の生成のための入力パラメータは、アルファベットのサイズｑおよび所望の内部符号の全長を含む。ステップ４１５において、内部符号が外部符号と組み合わされる。一実施の形態においては、内部符号は、外部符号に置換される。ステップ４２０において、結果として得られる内部符号および外部符号は、各ユーザのための既知のランダム化アルゴリズムに従ってランダムに並び替えられる。従って、各ユーザのために、ビットレベルでのランダム化が適用される。各正規ユーザのための結果として得られる符号語は、ユーザのフォレンシック符号の符号語におけるそのユーザのための各エントリのうちの１つとして本質的に使用される。そこで、この符号語は、不正なコンテンツ配布スキームにおけるアタッカ／共謀者を明らかにするための検出処理において有用である。ステップ４２５は、正規ユーザに対応するように使用できる単一の符号語または完全な符号語を出力する。生成された符号語は、ディジタル・コンテンツに埋め込まれる。
【００４９】
図５は、本発明の原理を使用して符号語を生成するシステム５５０を描いている。符号語生成装置５６０は、システム５５０のユーザからの入力５５５を受信する。これらの入力は、外部符号と内部符号の両方を生成するのに必要な入力を含む。リードソロモン符号などの外部符号の定義のため、システム５００のユーザによって入力される入力パラメータは、意図されたコンテンツのユーザ（配布者／ユーザなど）の数、アルファベットのサイズ（ｑ）、およびリードソロモン符号長（Ｌ）を含む。本発明の態様に係る内部符号のための入力パラメータは、アルファベットのサイズ（ｑ）および内部符号語の全長を含む。符号語生成装置５６０は、本発明に従った外部符号および内部符号を生成するコンピュータ命令を含むコンピュータ符号５６２に対するアクセスを有するプロセッサ５６４を備える。コンピュータ符号は、磁気的なメモリ、光学的なメモリ、または、ソリッドステート・メモリなどの、固定または着脱可能のコンピュータによって読み取り可能なメディアの形態をとることができる。一実施の形態においては、プロセッサによってアクセス可能なメモリ５６６に存在する符号は、コンピュータ命令のためだけでなく、コンピュータ符号の必要に応じた符号語の処理に関連するストレージのためにコンピュータによって使用することもできる。さらに、プロセッサは、バッファリングを行って生成された符号語を装置５６０から引き出すために有用な出力バッファ５６８と、プリンタやディスプレイなどの有形物に対するアクセスを有し、図１または図２などのシステムの場合には、符号化処理または検出処理のいずれかにおいて符号語を使用する後段に対するアクセスを有する。当業者であれば良好に理解できるであろうが、図５の実施の形態は、限定されるものではない。なぜならば、本発明の範囲および精神の中で、ハードウエアおよびソフトウエアの多数の変更、ファームウエアの実施態様が想定可能だからである。
【００５０】
図６は、本発明の原理に従って生成されるＥＣＣに基づく符号を使用した指数符号の構成を描いたフローチャートである。具体的には、ステップ６０５において、カウンタが初期化される。ステップ６１０、６１５、および６２０において、上述したように、複数の１と複数の−１からなるビット列を生成することによって、符号語が生成される。ステップ６２５において、カウンタの値が増やされる。ここにおいて、カウンタの値が増やされると記載しているが、カウンタは、一般性を失うことなく、最大値に初期化され、値が減らされることもある。ステップ６３０において、カウンタの値がｑ未満であるかどうかを判定するテストが実行され、内部符号が生成されているかどうがが判定される。
【００５１】
本発明は、ハードウエア（例えば、ＡＳＩＣチップ）、ソフトウエア、ファームウエア、特定用途向けのプロセッサ、または、これらを組み合わせたものの形態で、例えば、サーバ、中間装置（無線アクセス・ポイントまたは無線ルータなど）、または、モバイル装置内で実施することができることが理解できよう。好ましくは、本発明は、ハードウエアおよびソフトウエアを組み合わせて実施することができる。さらに、好ましくは、ソフトウエアは、プログラム・ストレージ装置に実行可能に格納されるアプリケーション・プログラムとして具体的な形態で実施される。アプリケーション・プログラムは、適切なアーキテクチャからなるマシンにアップロードされ、このマシンによって実行されるようにすることができる。好ましくは、このマシンは、１つ以上の中央処理装置（ＣＰＵ）、ランダム・アクセス・メモリ（ＲＡＭ）、入出力（Ｉ／Ｏ）インタフェースを有するコンピュータ・プラットフォーム上で実施される。また、コンピュータ・プラットフォームは、オペレーティング・システムおよびマイクロインストラクション・コードを含む。本明細書中で開示される様々な処理および機能は、マイクロインストラクション・コードの一部を構成するものでもよいし、アプリケーション・プログラムの一部を構成するものであってもよいし、これらを組み合わせたものであってもよく、オペレーティングによって実行される。さらに、追加的なデータ・ストレージ・デバイスや印刷機等、コンピュータ・プラットフォームに様々な他の周辺機器を結合するようにしてもよい。
【００５２】
添付図面に示すシステムの構成要素および方法のステップの幾つかをソフトウエアの形態によって実施してもよいため、システムの構成要素（または処理ステップ）間の実際の結合は、本発明のプログラムの仕方によって異なる場合があることが理解できよう。本明細書の開示する内容に基づいて、関連する技術に関して通常の技術を有するものであれば、本明細書中に開示された実施の形態または構成を理解し、これらの、さらに、類似した実施態様または構成を企図できるであろう。
【図１】
0005182975.tif 000076
【図２】
0005182975.tif 000077
【図３Ａ】
0005182975.tif 000078
【図３Ｂ】
0005182975.tif 000079
【図３Ｃ】
0005182975.tif 000080
【図３Ｄ】
0005182975.tif 000081
【図４】
0005182975.tif 000082
【図５】
0005182975.tif 000083
【図６】
0005182975.tif 000084
【図７】
0005182975.tif 000085
【図８】
0005182975.tif 000086
【図９】
0005182975.tif 000087