不正ユーザ検出装置、結託耐性符号生成装置及びプログラム
【課題】デジタルコンテンツに埋め込まれた結託耐性符号のうち全ての符号を抽出できなくても、デジタルコンテンツを不正に生成した不正ユーザの判定を行うことを可能にする不正ユーザ検出技術を提供する。
【解決手段】閾値設定部１０１は、符号抽出部が抽出した結託耐性符号の符号長に基づいて、ユーザが不正ユーザである否かの判定に用いる閾値を設定する。スコア計算部１０２は、符号抽出部が抽出した結託耐性符号の全部又は一部の符号と、各ユーザに対して割り当てられた符号と用いてスコアをユーザ毎に計算する。不正ユーザ判定部１０３は、スコア計算部１０２が計算した各ユーザのスコアと、閾値設定部１０１が設定した閾値とを用いて、各ユーザが不正ユーザであるか否かを判定する。
【解決手段】閾値設定部１０１は、符号抽出部が抽出した結託耐性符号の符号長に基づいて、ユーザが不正ユーザである否かの判定に用いる閾値を設定する。スコア計算部１０２は、符号抽出部が抽出した結託耐性符号の全部又は一部の符号と、各ユーザに対して割り当てられた符号と用いてスコアをユーザ毎に計算する。不正ユーザ判定部１０３は、スコア計算部１０２が計算した各ユーザのスコアと、閾値設定部１０１が設定した閾値とを用いて、各ユーザが不正ユーザであるか否かを判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツに埋め込まれた電子透かしの偽造に対抗するための結託耐性符号に基づいて不正ユーザを検出する不正ユーザ検出装置、結託耐性符号を生成する結託耐性符号生成装置及びプログラムに関わる。
【背景技術】
【０００２】
近年、コンピュータやネットワークの発達により、デジタルコンテンツを扱う場面が増えてきている。デジタルコンテンツには、非常に低いコストでオリジナルのコンテンツと全く同じコンテンツが作成できるという特徴がある。このため、デジタルコンテンツの著作権を保護するという観点から、デジタルコンテンツの違法コピーに対する対策は不可欠なものとなってきている。違法コピーを抑止するための対策として、例えば、電子透かし技術とフィンガープリンティングという技術とが用いられる。電子透かし技術とは、デジタルコンテンツに情報を埋め込む技術である。フィンガープリンティングとは、電子透かし技術を用いてデジタルコンテンツに利用者ＩＤを埋め込んでおき、違法にコンテンツのコピーが流通した際に、埋めこまれたＩＤを用いてデジタルコンテンツを違法にコピーしたユーザ（以下、不正ユーザという）を追跡する技術である。
【０００３】
しかしながらフィンガープリンティングにおいては、異なるＩＤの埋め込まれたデジタルコンテンツを複数持ち寄り、これらのＩＤにおける相違点を書き換えることにより、このＩＤによるユーザを識別不可能にする結託攻撃が行われる場合がある。これにより、不正ユーザを追跡不能になるため、結託攻撃に対する対策が不可欠である。この結託攻撃に対する対策として、例えば、ＩＤの代わりに結託耐性符号をデジタルコンテンツに埋め込めば良い。
【０００４】
結託耐性符号の例としてc-secure（with ε error）符号がある。これは、結託攻撃を行った結託者がｃ人までであるなら、その結託者（不正ユーザ）を１人も追跡（告発）できない確率、あるいは、結託攻撃を行っていないユーザを誤って追跡してしまう確率（誤り確率）をε以下にすることができる符号である。この具体的な符号の構成例としてＴａｒｄｏｓ符号（非特許文献１参照）とＮＨＷＩ符号（非特許文献２参照）がある。これらの非特許文献１〜２の技術においては、符号シンボルのうち「１」を取る生起確率の分布をある規則に則ってビット毎に各々取ることにより、符号を構成する（例えば、非特許文献１〜２参照）。
【０００５】
これらの非特許文献１〜２に示される技術においては、各ユーザが不正ユーザであるか否かは、結託攻撃後の符号とユーザの符号との相関を基に計算されたスコアを用いて判定され、そのスコアが閾値Ｚを超えていると判定される場合に不正ユーザとして告発されるアルゴリズムとなっている。すなわち、あるユーザｊのスコアをＳｊとすると、「Ｓｊ≧Ｚ」を満たすときに、ユーザｊは告発される。
【０００６】
Ｔａｒｄｏｓ符号（非特許文献１参照）では符号長を「１００ｃ２ｋ」と定め、不正ユーザか否かの判定を行うための閾値を「２０ｃｋ」と定めていた。ここで、「ｃ」は結託者数、「ｎ」はユーザ数、「ε」は誤り確率である。「ｋ」は以下の式１で表される。
【０００７】
【数１】
【０００８】
ＮＨＷＩ符号（非特許文献２参照）においても、設定された結託者数、ユーザ数等の条件により符号長と閾値が定まっている。上記、いずれの方式においても予め設定された条件で符号を生成し、生成した符号をコンテンツに埋め込み、結託攻撃を行われたコンテンツから符号を抽出し、結託攻撃が行われた符号全体から各ユーザのスコアＳｊを計算し、設定された閾値を用いて不正ユーザを特定することを想定している。
【０００９】
【非特許文献１】“Optimal probabilistic fingerprint codes”, STOC，pp116-125, 2003
【非特許文献２】“Optimal probabilistic fingerprint codes using optimal finite random variables related to numerical quadrature”, CR/0610036, arxiv.org
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、不正ユーザを追跡する際、全てのビットを対象としてスコア計算を行う必要があるため、不正ユーザであるか否かの判定には膨大な計算量が必要であった。また、コンテンツから全てのビットが抽出できないと、設定された安全性条件で不正ユーザであるか否かが判定させられない場合があるという問題もあった。
【００１１】
本発明は、上記に鑑みてなされたものであって、デジタルコンテンツに埋め込まれた結託耐性符号のうち全ての符号を抽出できなくても、デジタルコンテンツを不正に生成した不正ユーザの判定を行うことを可能にする不正ユーザ検出装置、結託耐性符号生成装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するために、本発明は、不正ユーザ検出装置であって、ユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号の一部又は全部をデジタルコンテンツから抽出する抽出手段と、前記結託耐性符号のうち抽出された符号と、各ユーザに対して各々割り当てられた符号とを用いて、ビット毎の相関値を計算し、当該相関値の合計点をユーザ毎に計算する計算手段と、抽出された前記符号の符号長に基づいて、不正ユーザの判定に用いる閾値を設定する第１設定手段と、設定された前記閾値と、計算されたユーザ毎の前記合計点とを用いて、各ユーザが不正ユーザか否かを判定する判定手段とを備えることを特徴とする。
【００１３】
また、本発明は、結託耐性符号生成装置であって、デジタルコンテンツに対してユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号を生成する結託耐性符号生成装置であって、想定される不正ユーザ数と、ユーザ数と、ユーザを不正ユーザであると誤って判定する誤り確率とに基づいて、符号長を設定する設定手段と、設定された符号長の結託耐性符号を生成する生成手段とを備え、前記設定手段は、前記結託耐性符号を用いて不正ユーザを検出する不正ユーザ検出装置において不正ユーザであるか否かを判定する処理が一ユーザにつき複数回行われ得る場合、当該処理が行われ得る最大の回数ｔ（ｔ：２以上の整数）に応じて、前記符号長を設定することを特徴とする。
【００１４】
また、本発明は、プログラムであって、コンピュータを、ユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号の一部又は全部をデジタルコンテンツから抽出する抽出手段と、前記結託耐性符号のうち抽出された符号と、各ユーザに対して各々割り当てられた符号とを用いて、ビット毎の相関値を計算し、当該相関値の合計点をユーザ毎に計算する計算手段と、抽出された前記符号の符号長に基づいて、不正ユーザの判定に用いる閾値を設定する第１設定手段と、設定された前記閾値と、計算されたユーザ毎の前記合計点とを用いて、各ユーザが不正ユーザか否かを判定する判定手段として機能させることを特徴とする。
【００１５】
また、本発明は、プログラムであって、コンピュータを、デジタルコンテンツに対してユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号を生成する結託耐性符号生成装置であって、想定される不正ユーザ数と、ユーザ数と、ユーザを不正ユーザであると誤って判定する誤り確率とに基づいて、符号長を設定する設定手段と、設定された符号長の結託耐性符号を生成する生成手段として機能させ、前記設定手段は、前記結託耐性符号を用いて不正ユーザを検出する不正ユーザ検出装置において不正ユーザであるか否かを判定する処理が一ユーザにつき複数回行われ得る場合、当該処理が行われ得る最大の回数ｔ（ｔ：２以上の整数）に応じて、前記符号長を設定することを特徴とする。
【発明の効果】
【００１６】
本発明によれば、デジタルコンテンツに埋め込まれた結託耐性符号のうち全ての符号を抽出できなくても、抽出された符号を基に、デジタルコンテンツを不正に生成した不正ユーザを適切に判定することができ、不正ユーザを追跡することができる。
【００１７】
また、本発明によれば、ユーザを不正ユーザであると誤って判定する誤り確率を想定内に収めつつ、判定回数に応じて想定された結託者数の摘発を可能な符号長を設定することにより、設定された安全性条件を満たす結託耐性符号を生成することができる。
【発明を実施するための最良の形態】
【００１８】
以下に添付図面を参照して、この発明にかかる不正ユーザ検出装置、結託耐性符号生成装置及びプログラムの最良な実施の形態を詳細に説明する。
【００１９】
[第１の実施の形態]
（１）構成
本実施の形態にかかる不正ユーザ検出装置は、装置全体の制御を行うＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００２０】
次に、このようなハードウェア構成において、不正ユーザ検出装置が、記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について説明する。図１は本実施の形態にかかる不正ユーザ検出装置の機能的構成を示す図である。同図に示される不正ユーザ検出装置１００は、符号抽出部（図示せず）と、閾値設定部１０１と、スコア計算部１０２と、不正ユーザ判定部１０３とを有する。
【００２１】
符号抽出部は、抽出対象のデジタルコンテンツから、結託耐性符号の全部又は一部を抽出する。閾値設定部１０１は、符号抽出部が抽出した結託耐性符号の符号長に基づいて、ユーザが不正ユーザである否かの判定に用いる閾値を設定する。スコア計算部１０２は、符号抽出部が抽出した結託耐性符号の全部又は一部の符号と、各ユーザに対して割り当てられた符号とについて、ビット毎に相関値を計算し、各ビットの相関値の合計をスコアとしてユーザ毎に計算する。このようなスコアの計算方法は、例えばＴａｒｄｏｓ符号について非特許文献１に記載されている方法を用いれば良い。不正ユーザ判定部１０３は、スコア計算部１０２が計算した各ユーザのスコアと、閾値設定部１０１が設定した閾値とを用いて、各ユーザが不正ユーザであるか否かを判定する。
【００２２】
（２）動作
次に、本実施の形態にかかる不正ユーザ検出装置１００の行う処理の手順について図２を参照しながら説明する。尚、本実施の形態においては、抽出対象のデジタルコンテンツに埋め込まれたに結託耐性符号のうち、一部の符号しか抽出できなかった場合について説明する。まず、不正ユーザ検出装置１００の符号抽出部が、抽出対象のデジタルコンテンツから符号の一部を抽出する。その際、抽出できた符号の符号長をｍＬとする。次いで、閾値設定部１０１は、ステップＳ１０１で抽出された符号の符号長ｍＬによって、ユーザが不正ユーザである否かの判定に用いる閾値ＴＨＬを設定する。閾値の設定は、Ｔａｒｄｏｓ符号では例えば以下のように行えば良い。閾値設定部１０１は、「ｍＬ＝１００ｃＬ２ｋ」となる結託者数ｃＬを計算し（ステップＳ１０１）、「ＴＨＬ＝２０ｃＬｋ」となるように閾値ＴＨＬを設定する（ステップＳ１０２）。即ち、「ＴＨＬ＝２√(ｍＬｋ）)」となる。ただしｋは上述の式１で表される。尚、これらの各種定数は、記憶装置や外部記憶装置に予め記憶されているものとする。
【００２３】
その後、スコア計算部１０２は、符号抽出部が抽出した符号と、各ユーザに対して割り当てられた符号とについて、ビット毎に相関値を計算し、各ビットの相関値の合計点をスコアとしてユーザ毎に計算する（ステップ１０３）。次いで、不正ユーザ判定部１０３は、スコア計算部１０２が計算した各ユーザｊのスコアＳｊと、閾値設定部１０１が設定した閾値ＴＨＬとを用いて、各ユーザｊが不正ユーザであるか否かを判定する。具体的には、不正ユーザ判定部１０３は、ユーザのスコアが閾値ＴＨＬより大きい場合、当該ユーザは不正ユーザであると判定し、ユーザのスコアが閾値ＴＨＬ以下である場合、当該ユーザは無罪である（無罪ユーザ）と判定する。
【００２４】
しかしながら、不正ユーザのスコアを直接評価することは難しい。攻撃アルゴリズムが未知であるため、攻撃アルゴリズムによってはスコアの分布に偏りが生ずる。このため、Tardosらは、不正ユーザの平均スコアが閾値ＴＨを超えているか否かで不正ユーザを告発できる確率を評価している。平均スコアであれば攻撃アルゴリズムによらず評価が可能であり、不正ユーザの平均スコアがＴＨを超えていれば、少なくとも1人の不正ユーザのスコアはＴＨを超え、告発が可能となるためである。
【００２５】
ここで、閾値ＴＨＬを用いた判定について説明する。図３は、Ｔａｒｄｏｓ符号におけるスコアによる無罪ユーザと不正ユーザとの頻度分布（確率分布であってもよい）を簡略化して示した図である。同図に示されるように、無罪ユーザのスコアの平均点は「０」点であり、無罪ユーザは、「０」点の近傍に集中し、この点から遠ざかるほど少なくなる分布となっている。一方、不正ユーザの平均スコアの平均ＡＶは「０」点より大きく、不正ユーザの平均スコアは、平均点ＡＶの近傍に集中し、この点から遠ざかるほど少なくなる分布となっている。このような分布において、スコアが適当に定めた閾値ＴＨ以下であれば、無罪ユーザであると判定し、スコアが閾値ＴＨより大きければ、不正ユーザであると判定することができる。
【００２６】
ところで、無罪ユーザと不正ユーザとの頻度分布は、符号長に応じて異なる。符号長が短くなるほど、その分布の分散は小さくなる。図４は、図３における符号長よりも短い符号長を用いた場合の無罪ユーザと不正ユーザとの頻度分布を簡略化して示した図である。同図に示されるように、この場合、図３に示した分布における閾値ＴＨより小さい値となる閾値（ＴＨＬ）を設定しなければならないことになる。従って、上述のステップＳ１０２では、閾値設定部１０１は、この符号長ｍＬの長さに応じて、ユーザが不正ユーザである否かの判定に用いる閾値ＴＨＬを設定することになる。このように、不正ユーザ判定部１０３は、符号長ｍＬに応じて設定された閾値ＴＨＬを用いて不正ユーザであるか否かの判定を行うことにより、その判定を適切に行うことができる。
【００２７】
図２に戻り、ステップＳ１０４の後、不正ユーザ判定部１０３は、不正ユーザであると判定したユーザを結託者であるとして告発する（ステップＳ１０５）。尚、不正ユーザ判定部１０３が不正ユーザであると判定したユーザが１人もいない場合、即ち、全てのユーザのスコアが閾値ＴＨＬ以下である場合（ステップＳ１０４：ＮＯ）、抽出された符号長ｍＬでは不正ユーザの追跡ができないものとして処理は終了する。
【００２８】
ここで、本実施の形態において用いる符号長について説明する。図５は、ある結託者数について、当該結託者数が比較的多い場合に、各符号長に対する不正ユーザ及び無罪ユーザのスコアの分布を示した図である。同図では、曲線Ｃｒ１〜Ｃｒ２は各々、不正ユーザであるか否かを判定するための閾値を示すものである。スコアの値が曲線Ｃｒ１より上にある場合、無罪ユーザがそのようなスコアとなることは極めて稀（想定している誤り確率以下）であることから不正ユーザであると判定され、スコアの値が曲線Ｃｒ１以下にある場合無罪ユーザであると判定される。また、スコアの値が曲線Ｃｒ２以下にある場合、不正ユーザ全員がそのようなスコアをとることも極めて稀（想定している誤り確率以下）であることから無罪ユーザであると判断され、スコアの値が曲線Ｃｒ２より上にある場合不正ユーザであると判定される。このような分布において、曲線Ｃｒ１及びＣｒ２が交わる点が、不正ユーザと無罪ユーザとを適切に判定することができる符号長（必要符号長）及びそれに対応する閾値であることを示している。
【００２９】
図６は、図５における結託者数より少ない結託者数について、各符号長に対する不正ユーザ及び無罪ユーザのスコアの分布を示した図である。この場合、不正ユーザであるか否かを判定するための閾値を示す曲線Ｃｒ３の傾きは、曲線Ｃｒ２の傾きより急なものとなる。従って、曲線Ｃｒ１及びＣｒ３の交点は、曲線Ｃｒ１及びＣｒ２の交点より、原点に近いものとなる。従って、結託者がより少ない場合の必要符号長Ｍは、結託者数がより多い場合の必要符号長より短くなる。即ち、結託者がより少ない場合には、結託者数がより多い場合に比べてより短い符号長（必要符号長）で、不正ユーザであるか否かを適切に判定することができる。
【００３０】
以上のような構成によれば、デジタルコンテンツから全ての符号を抽出できない場合であっても、抽出された符号の符号長に応じて想定される結託者数を基に閾値を設定することにより、不正ユーザを適切に判定することができる。従って、このような場合であっても、不正ユーザを効率的に追跡することができる。
【００３１】
[第２の実施の形態]
次に、不正ユーザ検出装置の第２の実施の形態について説明する。なお、上述の第１の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００３２】
（１）構成
本実施の形態においては、不正ユーザ検出装置は、元来想定していた符号長よりも短い符号長で不正ユーザの追跡を行う。図７は、本実施の形態にかかる不正ユーザ検出装置の機能的構成を示す図である。上述の第１の実施の形態と異なる部分について説明する。機能的構成において、本実施の形態にかかる不正ユーザ検出装置２００は、符号抽出部（図示せず）と、符号長設定部２０１と、閾値設定部２０２と、スコア計算部２０３と、不正ユーザ判定部２０４とを有する。符号長設定部２０１は、符号抽出部が抽出した符号のうち、その全部の符号又は一部の符号を用いるべく、不正ユーザであるか否かの判定に用いる符号長を判定回数に応じて設定する。閾値設定部２０２は、符号長設定部２０１が設定した符号長に基づいて、ユーザが不正ユーザであるか否かの判定に用いる閾値を設定する。スコア計算部２０３は、符号抽出部が抽出した符号のうち、符号長設定部２０１が設定した符号長の符号と、各ユーザの符号とについて、ビット毎に相関値を計算し、各ビットの相関値の合計をスコアとしてユーザ毎に計算する。不正ユーザ判定部２０４は、スコア計算部２０３が計算した各ユーザのスコアと、閾値設定部２０１が設定した閾値とを用いて、各ユーザが不正ユーザであるか否かを判定する。
【００３３】
以上のような構成において、不正ユーザ検出装置２００は、一ユーザにつき不正ユーザであるか否かを判定する判定処理を最大「ｔ」（ｔ：１以上の正整数）回行うものとする。この「ｔ」回を最大回数という。この最大回数「ｔ」の値は、予め設定され、例えば記憶装置や外部記憶装置に記憶されているものとする。そして、不正ユーザ検出装置２００は、１回目の判定処理において、１回目に対応した符号長を設定し、当該符号長に基づいて閾値を設定し、当該閾値を用いて、不正ユーザであるか否かの判定処理を行う。不正ユーザであると判定したユーザが１人もいない場合、判定回数が「ｔ」回に達していなければ、次回の判定処理において、不正ユーザ検出装置２００は、当該回数に対応した符号長を設定し、当該符号長に基づいて閾値を設定し、当該閾値を用いて、不正ユーザであるか否かの判定処理を行う。この回においても、不正ユーザであると判定したユーザが１人もいない場合には、「ｔ」回に達するまで、次回の判定処理において、上述と同様の判定処理を繰り返す。
【００３４】
また、ここでは、想定される結託者数が、判定回数に対応しており、その判定回数に対応する結託者数の不正ユーザを追跡可能な閾値を設定するための符号長を設定する。例えば、判定回数「１」に対して、結託者数「２」が想定されており、判定回数「２」に対して、結託者数「４」が想定されており、判定回数「３」に対して、結託者数「８」が想定されており、判定回数「４」に対して、結託者数「１０」が想定されている場合、最大回数「ｔ＝４」と設定され、判定回数ｕに対応する結託者数ｃｕとして、「ｃ１＝２」、「ｃ２＝４」、「ｃ３＝８」、「ｃ４＝１０」と設定される。最大回数ｔに対応する結託者数（最大結託者数）ｃｍａｘとする。即ち、ここでは、判定回数が増えるほど、想定される結託者数が多くなるよう設定される。
【００３５】
不正ユーザ検出装置２００は、不正ユーザであると判定したユーザが１人もいない場合には、このように、判定回数に応じた結託者数を用いて符号長を伸張し、伸張された符号長に基づいて次回の判定処理に用いる閾値を設定する。
【００３６】
尚、以上のように、判定回数に応じて符号長を設定するのは、以下の理由からである。上述のように、一ユーザにつき複数回の判定処理を行う場合、無罪であるユーザが、処理回によっては、不正ユーザであると判定される可能性がある。図８は、ユーザに対して計算されるスコアが、符号長の長さによって、即ち、処理回によって異なることを例示する図である。例えば、必要符号長Ｍ１を用いる処理回において計算されたスコアがＳｃ１であるユーザに対し、必要符号長Ｍ２を用いる処理回において計算されるスコアが、例えばＳｃ１"となる場合がある。この場合、前者の処理回では、スコアＳｃ１は必要符号長Ｍ１に対応する閾値ＴＨＭ１以下であるため、無罪であると判定され、後者の処理回では、スコアＳｃ１"は必要符号長Ｍ２に対応する閾値ＴＨＭ２を上回るため、不正ユーザであると判定される。また、必要符号長Ｍ１を用いる処理回において計算されたスコアがＳｃ２であるユーザに対し、必要符号長Ｍ２を用いる処理回において計算されるスコアが、例えばＳｃ２´となる場合もある。この場合、前者の処理回では、スコアＳｃ２は必要符号長Ｍ１に対応する閾値ＴＨＭ１を上回るため、不正ユーザであると判定され、後者の処理回では、スコアＳｃ２´は必要符号長Ｍ２に対応する閾値ＴＨＭ２以下であるため、無罪であると判定されるはずである。尚、必要符号長Ｍ１を用いる処理回において計算されたスコアがＳｃ１であるユーザに対し、必要符号長Ｍ２を用いる処理回において計算されるスコアが、例えばＳｃ１´となる場合、又は、前者の処理回でスコアＳｃ２であるユーザに対し、後者の処理回において計算されるスコアが、例えばＳｃ２"となる場合は、前者の処理回と後者の処理回とで判定結果は変わらないため、問題とはならない。
【００３７】
このように、複数回の判定処理を行うことにより、一ユーザに対する判定を誤ることがあると、判定を誤った回数分だけ確率事象が増えることになるため、判定を誤る確率が上がることになる。従って、複数回の判定処理を行う場合、判定を誤る確率を上述した誤り確率「ε」、即ち、判定処理が行われ得る回数が一ユーザにつき１回の場合に設定される誤り確率「ε」に収められない可能性があるため、判定回数に応じて符号長を設定する。
【００３８】
一方、判定を誤る確率を誤り確率「ε」以内に収めるためには、従来技術において、「ｃ」人の結託者の摘発に必要な符号長がｍｃだとすると、最悪、以下の式２で表される長さの符号長があれば十分である。
【００３９】
【数２】
【００４０】
このため、Ｔａｒｄｏｓ符号の例では、最大の結託者数として最大結託者数「ｃｍａｘ」を想定し、最大判定回数「ｔ」に対応して、符号長が以下の式３で表される長さ（最大符号長）の符号が必要となる。
【００４１】
【数３】
【００４２】
このため、対象のデジタルコンテンツには、最大結託者数「ｃｍａｘ」に対応して必要な最大符号長の結託耐性符号を予め埋めておく必要がある。ここでは、このような結託耐性符号が対象のデジタルコンテンツに予め埋め込まれているものとして説明する。尚、このような結託耐性符号を生成する結託耐性符号生成装置については後述する。
【００４３】
（２）動作
次に、本実施の形態にかかる不正ユーザ検出装置２００の行う処理の手順について図９を参照しながら説明する。まず、判定回数ｕを「１」とし（ステップＳ２０１）、符号長設定部２０１は、符号抽出部が抽出した符号から、不正ユーザの検出に用いる符号長ｍｕを判定回数ｕに応じて設定する（ステップＳ２０２）。ここで、符号長ｍｕを判定回数ｕに応じて設定するのは、判定回数ｕに対応して想定される結託者数ｃｕに応じて符号長を設定するということである。Ｔａｒｄｏｓ符号を用いる場合は、例えば、１回目（判定回数ｕが「１」のとき）で追跡したい結託者数を「ｃ１」とすると、符号長ｍｕを以下の式４で表される長さに設定する。判定回数ｕが「２」以上の場合については後述する。
【００４４】
【数４】
【００４５】
次に、閾値設定部２０２は、ステップＳ２０２で設定された符号長ｍｕを用いて、ユーザが不正ユーザである否かの判定に用いる閾値ＴＨｕを設定する（ステップＳ２０３）。スコア計算部２０３は、符号抽出部が抽出した符号のうち、符号長設定部２０１が設定した符号長ｍｕの符号と、各ユーザの符号長ｍｕ分の符号とについて、ビット毎に相関値を計算し、各ビットの相関値の合計をスコアとしてユーザ毎に計算する。不正ユーザ判定部２０４は、スコア計算部２０３が計算した各ユーザｊのスコアＳｊについて、閾値設定部１０１が設定した閾値ＴＨｕを用いて、各ユーザが不正ユーザであるか否かを判定する。そして、不正ユーザ判定部２０４は、不正ユーザであると判定したユーザを告発する（ステップＳ２０６）。不正ユーザであると判定したユーザが１人もいない場合、即ち、全てのユーザｊのスコアＳｊが閾値ＴＨｕ以下である場合（ステップＳ２０５：ＮＯ）、判定回数ｕに「１」を加え（ステップＳ２１６）、判定回数ｕが「ｔ」以下である場合（ステップＳ２１７：ＹＥＳ）、ステップＳ２０２に戻る。
【００４６】
尚、判定回数ｕが「２」の場合のステップＳ２０２では、符号長設定部２０１は、結託者数ｃを判定回数ｕに対応した結託者数「ｃ２」として、符号長ｍ２を以下の式５で表される長さに設定する。
【００４７】
【数５】
【００４８】
そして、ステップＳ２０３では、直前のステップＳ２０２で設定された符号長ｍｕを用いて、ユーザが不正ユーザである否かの判定に用いる閾値ＴＨｕを設定する。以降同様の処理を繰り返す。判定回数ｕが「ｒ」（２＜ｒ＜ｔ）の場合のステップＳ２０２では、符号長設定部２０１は、結託者数ｃを判定回数ｕに対応した結託者数「ｃｒ」として、符号長を以下の式６で表される長さに設定する。
【００４９】
【数６】
【００５０】
そして、判定回数ｕが「ｔ」に達した場合、ステップＳ２０２では、符号長設定部２０１は、結託者数ｃを最大判定回数「ｔ」に対応した最大結託者数「ｃｍａｘ」として、符号長を以下の式７で表される長さに設定する。
【００５１】
【数７】
【００５２】
このようにして、符号長設定部２０１は、判定回数ｕの値と、判定回数ｕに対応して想定される結託者数とを用いて、符号長ｍｕを設定する。そして、閾値設定部２０２が、設定された符号長ｍｕにより閾値ＴＨｕを設定し、不正ユーザ判定部２０４が、設定された閾値ＴＨｕを用いて、各ユーザが不正ユーザであるか否かを判定する。そして、ステップＳ２１７で、判定回数ｕが「ｔ」よりも大きくなった場合（ステップＳ２１７：ＮＯ）、抽出された符号では不正ユーザを追跡できないので、処理を終了する。
【００５３】
以上のようにして、本実施の形態においては、１回目の処理では、最大結託者数より少ない結託者数を想定して、最大符号長を用いるのではなくより短い符号長を用いて、不正ユーザか否かの判定処理を行う。この判定において、不正ユーザであると判定したユーザが１人もいない場合には、符号長を再設定して、不正ユーザか否かの判定処理を再度行う。このとき、判定回数が増えるほど、想定される結託者数が多くなるように設定するため、結果として、判定回数が増えるほど長く設定される符号長を用いて、不正ユーザか否かの判定処理を再度行うことになる。このように、結託者数が、符号生成時において想定される最大結託者数よりも少ないと想定される場合に、結託耐性符号のうち全部の符号を用いるのではなく一部を用いることにより、上述のスコアの計算や不正ユーザの判定のための計算量を減らすことができる。従って、不正ユーザの追跡をより効率的に行うことができる。
【００５４】
また、上述のように、判定を誤る確率を想定内に収めつつ、判定回数に応じて想定された結託者数の摘発を可能な符号長を設定することにより、設定された安全性条件を満たすことができる。
【００５５】
＜結託耐性符号生成装置＞
（１）構成
ここで、不正ユーザ検出装置２００において不正ユーザであるか否かを判定する判定処理が一ユーザにつき最大「ｔ」回(上述の最大回数)行われ得る場合の結託耐性符号を生成する結託耐性符号生成装置について説明する。結託耐性符号生成装置は、装置全体の制御を行うＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００５６】
次に、このようなハードウェア構成において、結託耐性符号生成装置が、記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について説明する。図１０は、結託耐性符号生成装置５００の機能的構成を例示する図である。同図に示される結託耐性符号生成装置５００は、誤り確率設定部５０１と、符号長設定部５０２と、結託耐性符号生成部５０３とを有する。誤り確率設定部５０１は、符号長の設定に用いる誤り確率として、処理が行われ得る最大の回数が１回の場合と比較して「１／ｔ」以下となるように、誤り確率の値を設定する。符号長設定部５０２は、誤り確率設定部５０１が設定した誤り確率と、想定される結託者数（不正ユーザ数）と、ユーザ数とに基づいて、符号長を設定する。結託耐性符号生成部５０３は、符号長設定部５０２が設定した符号長の結託耐性符号を生成する。
【００５７】
尚、最大回数「ｔ」の値は、特に限定されず、予め設定されて記憶装置や外部記憶装置に記憶されているものとする。また、結託耐性符号の生成に用いるユーザ数、想定される結託者数、誤り確率「ε」についても各々記憶装置や外部記憶装置に予め記憶されているものとする。
【００５８】
（２）動作
次に、結託耐性符号生成装置５００が行う結託耐性符号生成処理の手順について図１１を用いて説明する。結託耐性符号生成装置５００の誤り確率設定部５０１は、記憶装置や外部記憶装置に記憶されている誤り確率「ε」と最大回数「ｔ」とを読み出し、その値が「１／ｔ」以下となるように誤り確率を再設定する（ステップＳ３００）。次いで、符号長設定部５０２は、記憶装置や外部記憶装置に記憶された結託者数と、ユーザ数とを読み出し、これらと、ステップＳ３００で設定された誤り確率とに基づいて、符号長を設定する（ステップＳ３０１）。結託耐性符号生成部５０３は、ステップＳ３０１で設定された符号長の結託耐性符号を生成する（ステップＳ３０２）。
【００５９】
尚、Ｔａｒｄｏｓ符号の構成法においては誤り確率を「ε」とした場合、「不正ユーザを一人も告発できない」確率を「ε／ｎ」、「無罪ユーザを不正ユーザとして告発する」確率を「（ｎ−１）ε／ｎ」としており、このうちある「無罪ユーザを不正ユーザとして告発する」確率は「ε／ｎ」以下となる。上記のことを考えれば、ある「無罪ユーザを不正ユーザとして告発する」確率のみ「１／ｔ」倍すれば十分である。しかし、ステップＳ３００では、「不正ユーザを一人も告発できない」確率も「１／ｔ」倍して符号長を導出することを試みている。もちろん、ある「無罪ユーザを不正ユーザとして告発する」確率のみを「１／ｔ」倍して、符号長の設定をやり直せば符号長を短くできるのは自明であるが、ここではその説明を割愛する。
【００６０】
また、Ｔａｒｄｏｓ符号の構成法では、ユーザ数を「ｎ」、結託者数を「ｃ」、誤り確率を「ε」、符号長を「ｍ」とすると、符号長ｍは以下の式８で表される。
【００６１】
【数８】
【００６２】
ステップＳ３０１では、符号長設定部５０２は、この符号長ｍ’を以下の式９で表される長さに設定すれば良い。
【００６３】
【数９】
【００６４】
尚、不正ユーザ検出装置２００において不正ユーザであるか否かを判定する判定処理で用いる閾値は、以下の式１０で表される。
【００６５】
【数１０】
【００６６】
この代わりに以下の式１１で表される閾値が不正ユーザ検出装置２００では用いられるものとして、ステップＳ３０２では、結託耐性符号生成部５０３は結託耐性符号を生成すれば良い。
【００６７】
【数１１】
【００６８】
以上のような構成によって生成された結託耐性符号をデジタルコンテンツに埋め込むことにより、当該結託耐性符号を用いて不正ユーザ検出装置２００において不正ユーザであるか否かを判定する判定処理を一ユーザにつき最大「ｔ」回が行われたとしても、判定を誤る確率を想定内（「ε」以内）に収めることができ、設定された安全性条件を満たすことができる。
【００６９】
このようなことができるのは以下の理由からである。ユーザ数を「ｎ」とし、ある無罪ユーザを１回の判定処理で不正ユーザとして誤って告発する確率を「εｔ」とすると、無罪ユーザは最大「ｎ-１」人おり、不正ユーザ検出装置２００において１回の判定処理で無罪ユーザ全員が正しく判定される確率は、「（１−εｔ）ｎ−１」である。
【００７０】
毎回の判定処理が独立なものであると仮定すると、２回目の判定処理でもある無罪ユーザを不正ユーザとして誤って告発する確率は「εｔ」で変わらないため、２回目の判定処理で無罪ユーザ全員が正しく判定される確率は、「（１−εｔ）ｎ−１」である。
【００７１】
尚、実際は、毎回の判定処理が独立なものでないため、本来、誤り確率はこの確率よりもずっと低くなると考えられるが、ここでの評価は少なくともこの評価よりも高い誤り確率になることはない、というケースで誤り確率を見積もったものとなっている。
【００７２】
１人でも不正ユーザを告発した時点で判定処理は終了となるため、無罪ユーザを不正ユーザとして誤って告発した場合も判定処理は終了となる。このため、２回目以降は１回目の判定処理で無罪ユーザとして正しく判定されたものに対して判定処理が行われる。このことを考慮すると、２回目の判定処理終了時点で、無罪ユーザ全員が告発されない確率は、「（１−εｔ）２（ｎ−１）」となる。これを「ｔ」回繰り返すことを考え、「ｔ」回目の判定処理終了時点で無罪ユーザ全員が告発されない確率は、「（１−εｔ）ｔ（ｎ−１）」となる。
【００７３】
ここで「ｔ（ｎ−１）εｔ≪１」を想定すると、「（１−εｔ）ｔ（ｎ−１）＞１−ｔ（ｎ−１）εｔ」が成立する。従って、無罪のユーザを不正ユーザとして誤って告発する誤り確率は、「ｔ（ｎ−１）εｔ」以下となることがわかる。
【００７４】
尚、「ｔ（ｎ−１）εｔ≪１」という想定は、以下の理由からである。「ｔ（ｎ−１）εｔ」が「１」に近い場合は誤り確率自体が「１」に近いか、「ｔ」が非常に大きいということを示唆するものである。このため、安全性要件と、想定される「ｔ」はせいぜい結託者数「ｃ」以下であることとを鑑みて、上記の想定は妥当な想定であると考えられるからである。
【００７５】
例えば、Ｔａｒｄｏｓ符号の構成法では、１回の判定処理で無罪ユーザを誤って告発する確率を「（ｎ−１）ε／ｎ」となるようにしている。この確率と、一ユーザにつき最大「ｔ」回の判定処理を行って無罪ユーザを誤って告発する確率とを比較すると、「１−ｔ（ｎ−１）εｔ≦（ｎ−１）ε／ｎ」が成立する。これを整理すると「εｔ≦ε／（ｎ・ｔ）」となる。元々、Ｔａｒｄｏｓの構成法ではある無罪ユーザを誤って告発する確率を「ε／ｎ」としていたので、ある無罪のユーザを誤って告発する確率を当初の「１／ｔ」以下にすれば全体としての誤り確率を「ε」以下にすることができる。「ε」とは、上述において説明したように、元々想定される誤り確率の値であり、判定処理が行われ得る回数が一ユーザにつき１回の場合に設定される誤り確率の値である。
【００７６】
尚、誤りとは、上述したように、「不正ユーザを１人も告発できない」場合と「無罪ユーザを不正ユーザとして告発する」場合との２通りの場合があり得る。このうち「不正ユーザを一人も告発できない」という確率は、１回の判定処理でこの確率を「ε」以下に抑えているのであれば、「ｔ」回の判定を行った場合も「ε」以下になっているはずである。一方、「無罪のユーザを不正ユーザとして告発する」確率は上記で説明したように「ｔ」回の判定処理を行うと最悪で「ｔ」倍になる。「ｔ」回の判定処理後、全体として誤り確率を「ε」以下に抑えるためには、少なくとも１回のみの判定処理で「無罪ユーザを不正ユーザとして告発する」という誤り確率として「１／ｔ」倍以下のものを用いればよいということが分かる。
【００７７】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【００７８】
＜変形例１＞
上述の各実施の形態においては、不正ユーザ検出装置は、符号抽出部を有する構成であるとしたが、これを有するのではなく、ネットワークを介して外部のコンピュータと通信を行う通信制御装置を有し、当該通信制御装置を介して、コンテンツから抽出された符号を受信することにより、処理対象の符号を取得するように構成しても良い。
【００７９】
＜変形例２＞
上述した実施の形態において、不正ユーザ検出装置で実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、当該プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成しても良い。
【００８０】
＜変形例３＞
上述の第１の実施の形態の構成の一部又は全部及び第２の実施の形態の構成の一部又は全部を組み合わせても良い。このような構成によれば、例えば、全ての符号を抽出することができなくても、十分な長さの符号長の符号を得られた場合や、一部の符号しか抽出できていなくとも効率性を重視して極めて短い符号で予め不正ユーザの追跡を行いたい場合などに好適である。
【図面の簡単な説明】
【００８１】
【図１】第１の実施の形態にかかる不正ユーザ検出装置の機能的構成を示す図である。
【図２】同実施の形態にかかる不正ユーザ検出装置１００の行う処理の手順を示すフローチャートである。
【図３】同実施の形態にかかるＴａｒｄｏｓ符号におけるスコアによる無罪ユーザと不正ユーザとの人数分布を簡略化して示した図である。
【図４】図３における符号長よりも短い符号長を用いた場合の無罪ユーザと不正ユーザとの人数分布を簡略化して示した図である。
【図５】ある結託者数について、当該結託者数が比較的多い場合に、各符号長に対する不正ユーザ及び無罪ユーザのスコアの分布を示した図である。
【図６】図５における結託者数より少ない結託者数について、各符号長に対する不正ユーザ及び無罪ユーザのスコアの分布を示した図である。
【図７】第２の実施の形態にかかる不正ユーザ検出装置の機能的構成を示す図である。
【図８】ユーザに対して計算されるスコアが、符号長の長さによって、即ち、処理回によって異なることを例示する図である。
【図９】同実施の形態にかかる不正ユーザ検出装置２００の行う処理の手順を示すフローチャートである。
【図１０】同実施の形態にかかる結託耐性符号生成装置５００の機能的構成を例示する図である。
【図１１】同実施の形態にかかる結託耐性符号生成装置５００が行う結託耐性符号生成処理の手順を示すフローチャートである。
【符号の説明】
【００８２】
１００ 不正ユーザ検出装置
１０１ 閾値設定部
１０２ スコア計算部
１０３ 不正ユーザ判定部
２０１ 符号長設定部
２０２ 閾値設定部
２０３ スコア計算部
２０４ 不正ユーザ判定部
５００ 結託耐性符号生成装置
５０１ 誤り確率設定部
５０２ 符号長設定部
５０３ 結託耐性符号生成部
【技術分野】
【０００１】
本発明は、コンテンツに埋め込まれた電子透かしの偽造に対抗するための結託耐性符号に基づいて不正ユーザを検出する不正ユーザ検出装置、結託耐性符号を生成する結託耐性符号生成装置及びプログラムに関わる。
【背景技術】
【０００２】
近年、コンピュータやネットワークの発達により、デジタルコンテンツを扱う場面が増えてきている。デジタルコンテンツには、非常に低いコストでオリジナルのコンテンツと全く同じコンテンツが作成できるという特徴がある。このため、デジタルコンテンツの著作権を保護するという観点から、デジタルコンテンツの違法コピーに対する対策は不可欠なものとなってきている。違法コピーを抑止するための対策として、例えば、電子透かし技術とフィンガープリンティングという技術とが用いられる。電子透かし技術とは、デジタルコンテンツに情報を埋め込む技術である。フィンガープリンティングとは、電子透かし技術を用いてデジタルコンテンツに利用者ＩＤを埋め込んでおき、違法にコンテンツのコピーが流通した際に、埋めこまれたＩＤを用いてデジタルコンテンツを違法にコピーしたユーザ（以下、不正ユーザという）を追跡する技術である。
【０００３】
しかしながらフィンガープリンティングにおいては、異なるＩＤの埋め込まれたデジタルコンテンツを複数持ち寄り、これらのＩＤにおける相違点を書き換えることにより、このＩＤによるユーザを識別不可能にする結託攻撃が行われる場合がある。これにより、不正ユーザを追跡不能になるため、結託攻撃に対する対策が不可欠である。この結託攻撃に対する対策として、例えば、ＩＤの代わりに結託耐性符号をデジタルコンテンツに埋め込めば良い。
【０００４】
結託耐性符号の例としてc-secure（with ε error）符号がある。これは、結託攻撃を行った結託者がｃ人までであるなら、その結託者（不正ユーザ）を１人も追跡（告発）できない確率、あるいは、結託攻撃を行っていないユーザを誤って追跡してしまう確率（誤り確率）をε以下にすることができる符号である。この具体的な符号の構成例としてＴａｒｄｏｓ符号（非特許文献１参照）とＮＨＷＩ符号（非特許文献２参照）がある。これらの非特許文献１〜２の技術においては、符号シンボルのうち「１」を取る生起確率の分布をある規則に則ってビット毎に各々取ることにより、符号を構成する（例えば、非特許文献１〜２参照）。
【０００５】
これらの非特許文献１〜２に示される技術においては、各ユーザが不正ユーザであるか否かは、結託攻撃後の符号とユーザの符号との相関を基に計算されたスコアを用いて判定され、そのスコアが閾値Ｚを超えていると判定される場合に不正ユーザとして告発されるアルゴリズムとなっている。すなわち、あるユーザｊのスコアをＳｊとすると、「Ｓｊ≧Ｚ」を満たすときに、ユーザｊは告発される。
【０００６】
Ｔａｒｄｏｓ符号（非特許文献１参照）では符号長を「１００ｃ２ｋ」と定め、不正ユーザか否かの判定を行うための閾値を「２０ｃｋ」と定めていた。ここで、「ｃ」は結託者数、「ｎ」はユーザ数、「ε」は誤り確率である。「ｋ」は以下の式１で表される。
【０００７】
【数１】
【０００８】
ＮＨＷＩ符号（非特許文献２参照）においても、設定された結託者数、ユーザ数等の条件により符号長と閾値が定まっている。上記、いずれの方式においても予め設定された条件で符号を生成し、生成した符号をコンテンツに埋め込み、結託攻撃を行われたコンテンツから符号を抽出し、結託攻撃が行われた符号全体から各ユーザのスコアＳｊを計算し、設定された閾値を用いて不正ユーザを特定することを想定している。
【０００９】
【非特許文献１】“Optimal probabilistic fingerprint codes”, STOC，pp116-125, 2003
【非特許文献２】“Optimal probabilistic fingerprint codes using optimal finite random variables related to numerical quadrature”, CR/0610036, arxiv.org
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、不正ユーザを追跡する際、全てのビットを対象としてスコア計算を行う必要があるため、不正ユーザであるか否かの判定には膨大な計算量が必要であった。また、コンテンツから全てのビットが抽出できないと、設定された安全性条件で不正ユーザであるか否かが判定させられない場合があるという問題もあった。
【００１１】
本発明は、上記に鑑みてなされたものであって、デジタルコンテンツに埋め込まれた結託耐性符号のうち全ての符号を抽出できなくても、デジタルコンテンツを不正に生成した不正ユーザの判定を行うことを可能にする不正ユーザ検出装置、結託耐性符号生成装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するために、本発明は、不正ユーザ検出装置であって、ユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号の一部又は全部をデジタルコンテンツから抽出する抽出手段と、前記結託耐性符号のうち抽出された符号と、各ユーザに対して各々割り当てられた符号とを用いて、ビット毎の相関値を計算し、当該相関値の合計点をユーザ毎に計算する計算手段と、抽出された前記符号の符号長に基づいて、不正ユーザの判定に用いる閾値を設定する第１設定手段と、設定された前記閾値と、計算されたユーザ毎の前記合計点とを用いて、各ユーザが不正ユーザか否かを判定する判定手段とを備えることを特徴とする。
【００１３】
また、本発明は、結託耐性符号生成装置であって、デジタルコンテンツに対してユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号を生成する結託耐性符号生成装置であって、想定される不正ユーザ数と、ユーザ数と、ユーザを不正ユーザであると誤って判定する誤り確率とに基づいて、符号長を設定する設定手段と、設定された符号長の結託耐性符号を生成する生成手段とを備え、前記設定手段は、前記結託耐性符号を用いて不正ユーザを検出する不正ユーザ検出装置において不正ユーザであるか否かを判定する処理が一ユーザにつき複数回行われ得る場合、当該処理が行われ得る最大の回数ｔ（ｔ：２以上の整数）に応じて、前記符号長を設定することを特徴とする。
【００１４】
また、本発明は、プログラムであって、コンピュータを、ユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号の一部又は全部をデジタルコンテンツから抽出する抽出手段と、前記結託耐性符号のうち抽出された符号と、各ユーザに対して各々割り当てられた符号とを用いて、ビット毎の相関値を計算し、当該相関値の合計点をユーザ毎に計算する計算手段と、抽出された前記符号の符号長に基づいて、不正ユーザの判定に用いる閾値を設定する第１設定手段と、設定された前記閾値と、計算されたユーザ毎の前記合計点とを用いて、各ユーザが不正ユーザか否かを判定する判定手段として機能させることを特徴とする。
【００１５】
また、本発明は、プログラムであって、コンピュータを、デジタルコンテンツに対してユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号を生成する結託耐性符号生成装置であって、想定される不正ユーザ数と、ユーザ数と、ユーザを不正ユーザであると誤って判定する誤り確率とに基づいて、符号長を設定する設定手段と、設定された符号長の結託耐性符号を生成する生成手段として機能させ、前記設定手段は、前記結託耐性符号を用いて不正ユーザを検出する不正ユーザ検出装置において不正ユーザであるか否かを判定する処理が一ユーザにつき複数回行われ得る場合、当該処理が行われ得る最大の回数ｔ（ｔ：２以上の整数）に応じて、前記符号長を設定することを特徴とする。
【発明の効果】
【００１６】
本発明によれば、デジタルコンテンツに埋め込まれた結託耐性符号のうち全ての符号を抽出できなくても、抽出された符号を基に、デジタルコンテンツを不正に生成した不正ユーザを適切に判定することができ、不正ユーザを追跡することができる。
【００１７】
また、本発明によれば、ユーザを不正ユーザであると誤って判定する誤り確率を想定内に収めつつ、判定回数に応じて想定された結託者数の摘発を可能な符号長を設定することにより、設定された安全性条件を満たす結託耐性符号を生成することができる。
【発明を実施するための最良の形態】
【００１８】
以下に添付図面を参照して、この発明にかかる不正ユーザ検出装置、結託耐性符号生成装置及びプログラムの最良な実施の形態を詳細に説明する。
【００１９】
[第１の実施の形態]
（１）構成
本実施の形態にかかる不正ユーザ検出装置は、装置全体の制御を行うＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００２０】
次に、このようなハードウェア構成において、不正ユーザ検出装置が、記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について説明する。図１は本実施の形態にかかる不正ユーザ検出装置の機能的構成を示す図である。同図に示される不正ユーザ検出装置１００は、符号抽出部（図示せず）と、閾値設定部１０１と、スコア計算部１０２と、不正ユーザ判定部１０３とを有する。
【００２１】
符号抽出部は、抽出対象のデジタルコンテンツから、結託耐性符号の全部又は一部を抽出する。閾値設定部１０１は、符号抽出部が抽出した結託耐性符号の符号長に基づいて、ユーザが不正ユーザである否かの判定に用いる閾値を設定する。スコア計算部１０２は、符号抽出部が抽出した結託耐性符号の全部又は一部の符号と、各ユーザに対して割り当てられた符号とについて、ビット毎に相関値を計算し、各ビットの相関値の合計をスコアとしてユーザ毎に計算する。このようなスコアの計算方法は、例えばＴａｒｄｏｓ符号について非特許文献１に記載されている方法を用いれば良い。不正ユーザ判定部１０３は、スコア計算部１０２が計算した各ユーザのスコアと、閾値設定部１０１が設定した閾値とを用いて、各ユーザが不正ユーザであるか否かを判定する。
【００２２】
（２）動作
次に、本実施の形態にかかる不正ユーザ検出装置１００の行う処理の手順について図２を参照しながら説明する。尚、本実施の形態においては、抽出対象のデジタルコンテンツに埋め込まれたに結託耐性符号のうち、一部の符号しか抽出できなかった場合について説明する。まず、不正ユーザ検出装置１００の符号抽出部が、抽出対象のデジタルコンテンツから符号の一部を抽出する。その際、抽出できた符号の符号長をｍＬとする。次いで、閾値設定部１０１は、ステップＳ１０１で抽出された符号の符号長ｍＬによって、ユーザが不正ユーザである否かの判定に用いる閾値ＴＨＬを設定する。閾値の設定は、Ｔａｒｄｏｓ符号では例えば以下のように行えば良い。閾値設定部１０１は、「ｍＬ＝１００ｃＬ２ｋ」となる結託者数ｃＬを計算し（ステップＳ１０１）、「ＴＨＬ＝２０ｃＬｋ」となるように閾値ＴＨＬを設定する（ステップＳ１０２）。即ち、「ＴＨＬ＝２√(ｍＬｋ）)」となる。ただしｋは上述の式１で表される。尚、これらの各種定数は、記憶装置や外部記憶装置に予め記憶されているものとする。
【００２３】
その後、スコア計算部１０２は、符号抽出部が抽出した符号と、各ユーザに対して割り当てられた符号とについて、ビット毎に相関値を計算し、各ビットの相関値の合計点をスコアとしてユーザ毎に計算する（ステップ１０３）。次いで、不正ユーザ判定部１０３は、スコア計算部１０２が計算した各ユーザｊのスコアＳｊと、閾値設定部１０１が設定した閾値ＴＨＬとを用いて、各ユーザｊが不正ユーザであるか否かを判定する。具体的には、不正ユーザ判定部１０３は、ユーザのスコアが閾値ＴＨＬより大きい場合、当該ユーザは不正ユーザであると判定し、ユーザのスコアが閾値ＴＨＬ以下である場合、当該ユーザは無罪である（無罪ユーザ）と判定する。
【００２４】
しかしながら、不正ユーザのスコアを直接評価することは難しい。攻撃アルゴリズムが未知であるため、攻撃アルゴリズムによってはスコアの分布に偏りが生ずる。このため、Tardosらは、不正ユーザの平均スコアが閾値ＴＨを超えているか否かで不正ユーザを告発できる確率を評価している。平均スコアであれば攻撃アルゴリズムによらず評価が可能であり、不正ユーザの平均スコアがＴＨを超えていれば、少なくとも1人の不正ユーザのスコアはＴＨを超え、告発が可能となるためである。
【００２５】
ここで、閾値ＴＨＬを用いた判定について説明する。図３は、Ｔａｒｄｏｓ符号におけるスコアによる無罪ユーザと不正ユーザとの頻度分布（確率分布であってもよい）を簡略化して示した図である。同図に示されるように、無罪ユーザのスコアの平均点は「０」点であり、無罪ユーザは、「０」点の近傍に集中し、この点から遠ざかるほど少なくなる分布となっている。一方、不正ユーザの平均スコアの平均ＡＶは「０」点より大きく、不正ユーザの平均スコアは、平均点ＡＶの近傍に集中し、この点から遠ざかるほど少なくなる分布となっている。このような分布において、スコアが適当に定めた閾値ＴＨ以下であれば、無罪ユーザであると判定し、スコアが閾値ＴＨより大きければ、不正ユーザであると判定することができる。
【００２６】
ところで、無罪ユーザと不正ユーザとの頻度分布は、符号長に応じて異なる。符号長が短くなるほど、その分布の分散は小さくなる。図４は、図３における符号長よりも短い符号長を用いた場合の無罪ユーザと不正ユーザとの頻度分布を簡略化して示した図である。同図に示されるように、この場合、図３に示した分布における閾値ＴＨより小さい値となる閾値（ＴＨＬ）を設定しなければならないことになる。従って、上述のステップＳ１０２では、閾値設定部１０１は、この符号長ｍＬの長さに応じて、ユーザが不正ユーザである否かの判定に用いる閾値ＴＨＬを設定することになる。このように、不正ユーザ判定部１０３は、符号長ｍＬに応じて設定された閾値ＴＨＬを用いて不正ユーザであるか否かの判定を行うことにより、その判定を適切に行うことができる。
【００２７】
図２に戻り、ステップＳ１０４の後、不正ユーザ判定部１０３は、不正ユーザであると判定したユーザを結託者であるとして告発する（ステップＳ１０５）。尚、不正ユーザ判定部１０３が不正ユーザであると判定したユーザが１人もいない場合、即ち、全てのユーザのスコアが閾値ＴＨＬ以下である場合（ステップＳ１０４：ＮＯ）、抽出された符号長ｍＬでは不正ユーザの追跡ができないものとして処理は終了する。
【００２８】
ここで、本実施の形態において用いる符号長について説明する。図５は、ある結託者数について、当該結託者数が比較的多い場合に、各符号長に対する不正ユーザ及び無罪ユーザのスコアの分布を示した図である。同図では、曲線Ｃｒ１〜Ｃｒ２は各々、不正ユーザであるか否かを判定するための閾値を示すものである。スコアの値が曲線Ｃｒ１より上にある場合、無罪ユーザがそのようなスコアとなることは極めて稀（想定している誤り確率以下）であることから不正ユーザであると判定され、スコアの値が曲線Ｃｒ１以下にある場合無罪ユーザであると判定される。また、スコアの値が曲線Ｃｒ２以下にある場合、不正ユーザ全員がそのようなスコアをとることも極めて稀（想定している誤り確率以下）であることから無罪ユーザであると判断され、スコアの値が曲線Ｃｒ２より上にある場合不正ユーザであると判定される。このような分布において、曲線Ｃｒ１及びＣｒ２が交わる点が、不正ユーザと無罪ユーザとを適切に判定することができる符号長（必要符号長）及びそれに対応する閾値であることを示している。
【００２９】
図６は、図５における結託者数より少ない結託者数について、各符号長に対する不正ユーザ及び無罪ユーザのスコアの分布を示した図である。この場合、不正ユーザであるか否かを判定するための閾値を示す曲線Ｃｒ３の傾きは、曲線Ｃｒ２の傾きより急なものとなる。従って、曲線Ｃｒ１及びＣｒ３の交点は、曲線Ｃｒ１及びＣｒ２の交点より、原点に近いものとなる。従って、結託者がより少ない場合の必要符号長Ｍは、結託者数がより多い場合の必要符号長より短くなる。即ち、結託者がより少ない場合には、結託者数がより多い場合に比べてより短い符号長（必要符号長）で、不正ユーザであるか否かを適切に判定することができる。
【００３０】
以上のような構成によれば、デジタルコンテンツから全ての符号を抽出できない場合であっても、抽出された符号の符号長に応じて想定される結託者数を基に閾値を設定することにより、不正ユーザを適切に判定することができる。従って、このような場合であっても、不正ユーザを効率的に追跡することができる。
【００３１】
[第２の実施の形態]
次に、不正ユーザ検出装置の第２の実施の形態について説明する。なお、上述の第１の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００３２】
（１）構成
本実施の形態においては、不正ユーザ検出装置は、元来想定していた符号長よりも短い符号長で不正ユーザの追跡を行う。図７は、本実施の形態にかかる不正ユーザ検出装置の機能的構成を示す図である。上述の第１の実施の形態と異なる部分について説明する。機能的構成において、本実施の形態にかかる不正ユーザ検出装置２００は、符号抽出部（図示せず）と、符号長設定部２０１と、閾値設定部２０２と、スコア計算部２０３と、不正ユーザ判定部２０４とを有する。符号長設定部２０１は、符号抽出部が抽出した符号のうち、その全部の符号又は一部の符号を用いるべく、不正ユーザであるか否かの判定に用いる符号長を判定回数に応じて設定する。閾値設定部２０２は、符号長設定部２０１が設定した符号長に基づいて、ユーザが不正ユーザであるか否かの判定に用いる閾値を設定する。スコア計算部２０３は、符号抽出部が抽出した符号のうち、符号長設定部２０１が設定した符号長の符号と、各ユーザの符号とについて、ビット毎に相関値を計算し、各ビットの相関値の合計をスコアとしてユーザ毎に計算する。不正ユーザ判定部２０４は、スコア計算部２０３が計算した各ユーザのスコアと、閾値設定部２０１が設定した閾値とを用いて、各ユーザが不正ユーザであるか否かを判定する。
【００３３】
以上のような構成において、不正ユーザ検出装置２００は、一ユーザにつき不正ユーザであるか否かを判定する判定処理を最大「ｔ」（ｔ：１以上の正整数）回行うものとする。この「ｔ」回を最大回数という。この最大回数「ｔ」の値は、予め設定され、例えば記憶装置や外部記憶装置に記憶されているものとする。そして、不正ユーザ検出装置２００は、１回目の判定処理において、１回目に対応した符号長を設定し、当該符号長に基づいて閾値を設定し、当該閾値を用いて、不正ユーザであるか否かの判定処理を行う。不正ユーザであると判定したユーザが１人もいない場合、判定回数が「ｔ」回に達していなければ、次回の判定処理において、不正ユーザ検出装置２００は、当該回数に対応した符号長を設定し、当該符号長に基づいて閾値を設定し、当該閾値を用いて、不正ユーザであるか否かの判定処理を行う。この回においても、不正ユーザであると判定したユーザが１人もいない場合には、「ｔ」回に達するまで、次回の判定処理において、上述と同様の判定処理を繰り返す。
【００３４】
また、ここでは、想定される結託者数が、判定回数に対応しており、その判定回数に対応する結託者数の不正ユーザを追跡可能な閾値を設定するための符号長を設定する。例えば、判定回数「１」に対して、結託者数「２」が想定されており、判定回数「２」に対して、結託者数「４」が想定されており、判定回数「３」に対して、結託者数「８」が想定されており、判定回数「４」に対して、結託者数「１０」が想定されている場合、最大回数「ｔ＝４」と設定され、判定回数ｕに対応する結託者数ｃｕとして、「ｃ１＝２」、「ｃ２＝４」、「ｃ３＝８」、「ｃ４＝１０」と設定される。最大回数ｔに対応する結託者数（最大結託者数）ｃｍａｘとする。即ち、ここでは、判定回数が増えるほど、想定される結託者数が多くなるよう設定される。
【００３５】
不正ユーザ検出装置２００は、不正ユーザであると判定したユーザが１人もいない場合には、このように、判定回数に応じた結託者数を用いて符号長を伸張し、伸張された符号長に基づいて次回の判定処理に用いる閾値を設定する。
【００３６】
尚、以上のように、判定回数に応じて符号長を設定するのは、以下の理由からである。上述のように、一ユーザにつき複数回の判定処理を行う場合、無罪であるユーザが、処理回によっては、不正ユーザであると判定される可能性がある。図８は、ユーザに対して計算されるスコアが、符号長の長さによって、即ち、処理回によって異なることを例示する図である。例えば、必要符号長Ｍ１を用いる処理回において計算されたスコアがＳｃ１であるユーザに対し、必要符号長Ｍ２を用いる処理回において計算されるスコアが、例えばＳｃ１"となる場合がある。この場合、前者の処理回では、スコアＳｃ１は必要符号長Ｍ１に対応する閾値ＴＨＭ１以下であるため、無罪であると判定され、後者の処理回では、スコアＳｃ１"は必要符号長Ｍ２に対応する閾値ＴＨＭ２を上回るため、不正ユーザであると判定される。また、必要符号長Ｍ１を用いる処理回において計算されたスコアがＳｃ２であるユーザに対し、必要符号長Ｍ２を用いる処理回において計算されるスコアが、例えばＳｃ２´となる場合もある。この場合、前者の処理回では、スコアＳｃ２は必要符号長Ｍ１に対応する閾値ＴＨＭ１を上回るため、不正ユーザであると判定され、後者の処理回では、スコアＳｃ２´は必要符号長Ｍ２に対応する閾値ＴＨＭ２以下であるため、無罪であると判定されるはずである。尚、必要符号長Ｍ１を用いる処理回において計算されたスコアがＳｃ１であるユーザに対し、必要符号長Ｍ２を用いる処理回において計算されるスコアが、例えばＳｃ１´となる場合、又は、前者の処理回でスコアＳｃ２であるユーザに対し、後者の処理回において計算されるスコアが、例えばＳｃ２"となる場合は、前者の処理回と後者の処理回とで判定結果は変わらないため、問題とはならない。
【００３７】
このように、複数回の判定処理を行うことにより、一ユーザに対する判定を誤ることがあると、判定を誤った回数分だけ確率事象が増えることになるため、判定を誤る確率が上がることになる。従って、複数回の判定処理を行う場合、判定を誤る確率を上述した誤り確率「ε」、即ち、判定処理が行われ得る回数が一ユーザにつき１回の場合に設定される誤り確率「ε」に収められない可能性があるため、判定回数に応じて符号長を設定する。
【００３８】
一方、判定を誤る確率を誤り確率「ε」以内に収めるためには、従来技術において、「ｃ」人の結託者の摘発に必要な符号長がｍｃだとすると、最悪、以下の式２で表される長さの符号長があれば十分である。
【００３９】
【数２】
【００４０】
このため、Ｔａｒｄｏｓ符号の例では、最大の結託者数として最大結託者数「ｃｍａｘ」を想定し、最大判定回数「ｔ」に対応して、符号長が以下の式３で表される長さ（最大符号長）の符号が必要となる。
【００４１】
【数３】
【００４２】
このため、対象のデジタルコンテンツには、最大結託者数「ｃｍａｘ」に対応して必要な最大符号長の結託耐性符号を予め埋めておく必要がある。ここでは、このような結託耐性符号が対象のデジタルコンテンツに予め埋め込まれているものとして説明する。尚、このような結託耐性符号を生成する結託耐性符号生成装置については後述する。
【００４３】
（２）動作
次に、本実施の形態にかかる不正ユーザ検出装置２００の行う処理の手順について図９を参照しながら説明する。まず、判定回数ｕを「１」とし（ステップＳ２０１）、符号長設定部２０１は、符号抽出部が抽出した符号から、不正ユーザの検出に用いる符号長ｍｕを判定回数ｕに応じて設定する（ステップＳ２０２）。ここで、符号長ｍｕを判定回数ｕに応じて設定するのは、判定回数ｕに対応して想定される結託者数ｃｕに応じて符号長を設定するということである。Ｔａｒｄｏｓ符号を用いる場合は、例えば、１回目（判定回数ｕが「１」のとき）で追跡したい結託者数を「ｃ１」とすると、符号長ｍｕを以下の式４で表される長さに設定する。判定回数ｕが「２」以上の場合については後述する。
【００４４】
【数４】
【００４５】
次に、閾値設定部２０２は、ステップＳ２０２で設定された符号長ｍｕを用いて、ユーザが不正ユーザである否かの判定に用いる閾値ＴＨｕを設定する（ステップＳ２０３）。スコア計算部２０３は、符号抽出部が抽出した符号のうち、符号長設定部２０１が設定した符号長ｍｕの符号と、各ユーザの符号長ｍｕ分の符号とについて、ビット毎に相関値を計算し、各ビットの相関値の合計をスコアとしてユーザ毎に計算する。不正ユーザ判定部２０４は、スコア計算部２０３が計算した各ユーザｊのスコアＳｊについて、閾値設定部１０１が設定した閾値ＴＨｕを用いて、各ユーザが不正ユーザであるか否かを判定する。そして、不正ユーザ判定部２０４は、不正ユーザであると判定したユーザを告発する（ステップＳ２０６）。不正ユーザであると判定したユーザが１人もいない場合、即ち、全てのユーザｊのスコアＳｊが閾値ＴＨｕ以下である場合（ステップＳ２０５：ＮＯ）、判定回数ｕに「１」を加え（ステップＳ２１６）、判定回数ｕが「ｔ」以下である場合（ステップＳ２１７：ＹＥＳ）、ステップＳ２０２に戻る。
【００４６】
尚、判定回数ｕが「２」の場合のステップＳ２０２では、符号長設定部２０１は、結託者数ｃを判定回数ｕに対応した結託者数「ｃ２」として、符号長ｍ２を以下の式５で表される長さに設定する。
【００４７】
【数５】
【００４８】
そして、ステップＳ２０３では、直前のステップＳ２０２で設定された符号長ｍｕを用いて、ユーザが不正ユーザである否かの判定に用いる閾値ＴＨｕを設定する。以降同様の処理を繰り返す。判定回数ｕが「ｒ」（２＜ｒ＜ｔ）の場合のステップＳ２０２では、符号長設定部２０１は、結託者数ｃを判定回数ｕに対応した結託者数「ｃｒ」として、符号長を以下の式６で表される長さに設定する。
【００４９】
【数６】
【００５０】
そして、判定回数ｕが「ｔ」に達した場合、ステップＳ２０２では、符号長設定部２０１は、結託者数ｃを最大判定回数「ｔ」に対応した最大結託者数「ｃｍａｘ」として、符号長を以下の式７で表される長さに設定する。
【００５１】
【数７】
【００５２】
このようにして、符号長設定部２０１は、判定回数ｕの値と、判定回数ｕに対応して想定される結託者数とを用いて、符号長ｍｕを設定する。そして、閾値設定部２０２が、設定された符号長ｍｕにより閾値ＴＨｕを設定し、不正ユーザ判定部２０４が、設定された閾値ＴＨｕを用いて、各ユーザが不正ユーザであるか否かを判定する。そして、ステップＳ２１７で、判定回数ｕが「ｔ」よりも大きくなった場合（ステップＳ２１７：ＮＯ）、抽出された符号では不正ユーザを追跡できないので、処理を終了する。
【００５３】
以上のようにして、本実施の形態においては、１回目の処理では、最大結託者数より少ない結託者数を想定して、最大符号長を用いるのではなくより短い符号長を用いて、不正ユーザか否かの判定処理を行う。この判定において、不正ユーザであると判定したユーザが１人もいない場合には、符号長を再設定して、不正ユーザか否かの判定処理を再度行う。このとき、判定回数が増えるほど、想定される結託者数が多くなるように設定するため、結果として、判定回数が増えるほど長く設定される符号長を用いて、不正ユーザか否かの判定処理を再度行うことになる。このように、結託者数が、符号生成時において想定される最大結託者数よりも少ないと想定される場合に、結託耐性符号のうち全部の符号を用いるのではなく一部を用いることにより、上述のスコアの計算や不正ユーザの判定のための計算量を減らすことができる。従って、不正ユーザの追跡をより効率的に行うことができる。
【００５４】
また、上述のように、判定を誤る確率を想定内に収めつつ、判定回数に応じて想定された結託者数の摘発を可能な符号長を設定することにより、設定された安全性条件を満たすことができる。
【００５５】
＜結託耐性符号生成装置＞
（１）構成
ここで、不正ユーザ検出装置２００において不正ユーザであるか否かを判定する判定処理が一ユーザにつき最大「ｔ」回(上述の最大回数)行われ得る場合の結託耐性符号を生成する結託耐性符号生成装置について説明する。結託耐性符号生成装置は、装置全体の制御を行うＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００５６】
次に、このようなハードウェア構成において、結託耐性符号生成装置が、記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について説明する。図１０は、結託耐性符号生成装置５００の機能的構成を例示する図である。同図に示される結託耐性符号生成装置５００は、誤り確率設定部５０１と、符号長設定部５０２と、結託耐性符号生成部５０３とを有する。誤り確率設定部５０１は、符号長の設定に用いる誤り確率として、処理が行われ得る最大の回数が１回の場合と比較して「１／ｔ」以下となるように、誤り確率の値を設定する。符号長設定部５０２は、誤り確率設定部５０１が設定した誤り確率と、想定される結託者数（不正ユーザ数）と、ユーザ数とに基づいて、符号長を設定する。結託耐性符号生成部５０３は、符号長設定部５０２が設定した符号長の結託耐性符号を生成する。
【００５７】
尚、最大回数「ｔ」の値は、特に限定されず、予め設定されて記憶装置や外部記憶装置に記憶されているものとする。また、結託耐性符号の生成に用いるユーザ数、想定される結託者数、誤り確率「ε」についても各々記憶装置や外部記憶装置に予め記憶されているものとする。
【００５８】
（２）動作
次に、結託耐性符号生成装置５００が行う結託耐性符号生成処理の手順について図１１を用いて説明する。結託耐性符号生成装置５００の誤り確率設定部５０１は、記憶装置や外部記憶装置に記憶されている誤り確率「ε」と最大回数「ｔ」とを読み出し、その値が「１／ｔ」以下となるように誤り確率を再設定する（ステップＳ３００）。次いで、符号長設定部５０２は、記憶装置や外部記憶装置に記憶された結託者数と、ユーザ数とを読み出し、これらと、ステップＳ３００で設定された誤り確率とに基づいて、符号長を設定する（ステップＳ３０１）。結託耐性符号生成部５０３は、ステップＳ３０１で設定された符号長の結託耐性符号を生成する（ステップＳ３０２）。
【００５９】
尚、Ｔａｒｄｏｓ符号の構成法においては誤り確率を「ε」とした場合、「不正ユーザを一人も告発できない」確率を「ε／ｎ」、「無罪ユーザを不正ユーザとして告発する」確率を「（ｎ−１）ε／ｎ」としており、このうちある「無罪ユーザを不正ユーザとして告発する」確率は「ε／ｎ」以下となる。上記のことを考えれば、ある「無罪ユーザを不正ユーザとして告発する」確率のみ「１／ｔ」倍すれば十分である。しかし、ステップＳ３００では、「不正ユーザを一人も告発できない」確率も「１／ｔ」倍して符号長を導出することを試みている。もちろん、ある「無罪ユーザを不正ユーザとして告発する」確率のみを「１／ｔ」倍して、符号長の設定をやり直せば符号長を短くできるのは自明であるが、ここではその説明を割愛する。
【００６０】
また、Ｔａｒｄｏｓ符号の構成法では、ユーザ数を「ｎ」、結託者数を「ｃ」、誤り確率を「ε」、符号長を「ｍ」とすると、符号長ｍは以下の式８で表される。
【００６１】
【数８】
【００６２】
ステップＳ３０１では、符号長設定部５０２は、この符号長ｍ’を以下の式９で表される長さに設定すれば良い。
【００６３】
【数９】
【００６４】
尚、不正ユーザ検出装置２００において不正ユーザであるか否かを判定する判定処理で用いる閾値は、以下の式１０で表される。
【００６５】
【数１０】
【００６６】
この代わりに以下の式１１で表される閾値が不正ユーザ検出装置２００では用いられるものとして、ステップＳ３０２では、結託耐性符号生成部５０３は結託耐性符号を生成すれば良い。
【００６７】
【数１１】
【００６８】
以上のような構成によって生成された結託耐性符号をデジタルコンテンツに埋め込むことにより、当該結託耐性符号を用いて不正ユーザ検出装置２００において不正ユーザであるか否かを判定する判定処理を一ユーザにつき最大「ｔ」回が行われたとしても、判定を誤る確率を想定内（「ε」以内）に収めることができ、設定された安全性条件を満たすことができる。
【００６９】
このようなことができるのは以下の理由からである。ユーザ数を「ｎ」とし、ある無罪ユーザを１回の判定処理で不正ユーザとして誤って告発する確率を「εｔ」とすると、無罪ユーザは最大「ｎ-１」人おり、不正ユーザ検出装置２００において１回の判定処理で無罪ユーザ全員が正しく判定される確率は、「（１−εｔ）ｎ−１」である。
【００７０】
毎回の判定処理が独立なものであると仮定すると、２回目の判定処理でもある無罪ユーザを不正ユーザとして誤って告発する確率は「εｔ」で変わらないため、２回目の判定処理で無罪ユーザ全員が正しく判定される確率は、「（１−εｔ）ｎ−１」である。
【００７１】
尚、実際は、毎回の判定処理が独立なものでないため、本来、誤り確率はこの確率よりもずっと低くなると考えられるが、ここでの評価は少なくともこの評価よりも高い誤り確率になることはない、というケースで誤り確率を見積もったものとなっている。
【００７２】
１人でも不正ユーザを告発した時点で判定処理は終了となるため、無罪ユーザを不正ユーザとして誤って告発した場合も判定処理は終了となる。このため、２回目以降は１回目の判定処理で無罪ユーザとして正しく判定されたものに対して判定処理が行われる。このことを考慮すると、２回目の判定処理終了時点で、無罪ユーザ全員が告発されない確率は、「（１−εｔ）２（ｎ−１）」となる。これを「ｔ」回繰り返すことを考え、「ｔ」回目の判定処理終了時点で無罪ユーザ全員が告発されない確率は、「（１−εｔ）ｔ（ｎ−１）」となる。
【００７３】
ここで「ｔ（ｎ−１）εｔ≪１」を想定すると、「（１−εｔ）ｔ（ｎ−１）＞１−ｔ（ｎ−１）εｔ」が成立する。従って、無罪のユーザを不正ユーザとして誤って告発する誤り確率は、「ｔ（ｎ−１）εｔ」以下となることがわかる。
【００７４】
尚、「ｔ（ｎ−１）εｔ≪１」という想定は、以下の理由からである。「ｔ（ｎ−１）εｔ」が「１」に近い場合は誤り確率自体が「１」に近いか、「ｔ」が非常に大きいということを示唆するものである。このため、安全性要件と、想定される「ｔ」はせいぜい結託者数「ｃ」以下であることとを鑑みて、上記の想定は妥当な想定であると考えられるからである。
【００７５】
例えば、Ｔａｒｄｏｓ符号の構成法では、１回の判定処理で無罪ユーザを誤って告発する確率を「（ｎ−１）ε／ｎ」となるようにしている。この確率と、一ユーザにつき最大「ｔ」回の判定処理を行って無罪ユーザを誤って告発する確率とを比較すると、「１−ｔ（ｎ−１）εｔ≦（ｎ−１）ε／ｎ」が成立する。これを整理すると「εｔ≦ε／（ｎ・ｔ）」となる。元々、Ｔａｒｄｏｓの構成法ではある無罪ユーザを誤って告発する確率を「ε／ｎ」としていたので、ある無罪のユーザを誤って告発する確率を当初の「１／ｔ」以下にすれば全体としての誤り確率を「ε」以下にすることができる。「ε」とは、上述において説明したように、元々想定される誤り確率の値であり、判定処理が行われ得る回数が一ユーザにつき１回の場合に設定される誤り確率の値である。
【００７６】
尚、誤りとは、上述したように、「不正ユーザを１人も告発できない」場合と「無罪ユーザを不正ユーザとして告発する」場合との２通りの場合があり得る。このうち「不正ユーザを一人も告発できない」という確率は、１回の判定処理でこの確率を「ε」以下に抑えているのであれば、「ｔ」回の判定を行った場合も「ε」以下になっているはずである。一方、「無罪のユーザを不正ユーザとして告発する」確率は上記で説明したように「ｔ」回の判定処理を行うと最悪で「ｔ」倍になる。「ｔ」回の判定処理後、全体として誤り確率を「ε」以下に抑えるためには、少なくとも１回のみの判定処理で「無罪ユーザを不正ユーザとして告発する」という誤り確率として「１／ｔ」倍以下のものを用いればよいということが分かる。
【００７７】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【００７８】
＜変形例１＞
上述の各実施の形態においては、不正ユーザ検出装置は、符号抽出部を有する構成であるとしたが、これを有するのではなく、ネットワークを介して外部のコンピュータと通信を行う通信制御装置を有し、当該通信制御装置を介して、コンテンツから抽出された符号を受信することにより、処理対象の符号を取得するように構成しても良い。
【００７９】
＜変形例２＞
上述した実施の形態において、不正ユーザ検出装置で実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、当該プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成しても良い。
【００８０】
＜変形例３＞
上述の第１の実施の形態の構成の一部又は全部及び第２の実施の形態の構成の一部又は全部を組み合わせても良い。このような構成によれば、例えば、全ての符号を抽出することができなくても、十分な長さの符号長の符号を得られた場合や、一部の符号しか抽出できていなくとも効率性を重視して極めて短い符号で予め不正ユーザの追跡を行いたい場合などに好適である。
【図面の簡単な説明】
【００８１】
【図１】第１の実施の形態にかかる不正ユーザ検出装置の機能的構成を示す図である。
【図２】同実施の形態にかかる不正ユーザ検出装置１００の行う処理の手順を示すフローチャートである。
【図３】同実施の形態にかかるＴａｒｄｏｓ符号におけるスコアによる無罪ユーザと不正ユーザとの人数分布を簡略化して示した図である。
【図４】図３における符号長よりも短い符号長を用いた場合の無罪ユーザと不正ユーザとの人数分布を簡略化して示した図である。
【図５】ある結託者数について、当該結託者数が比較的多い場合に、各符号長に対する不正ユーザ及び無罪ユーザのスコアの分布を示した図である。
【図６】図５における結託者数より少ない結託者数について、各符号長に対する不正ユーザ及び無罪ユーザのスコアの分布を示した図である。
【図７】第２の実施の形態にかかる不正ユーザ検出装置の機能的構成を示す図である。
【図８】ユーザに対して計算されるスコアが、符号長の長さによって、即ち、処理回によって異なることを例示する図である。
【図９】同実施の形態にかかる不正ユーザ検出装置２００の行う処理の手順を示すフローチャートである。
【図１０】同実施の形態にかかる結託耐性符号生成装置５００の機能的構成を例示する図である。
【図１１】同実施の形態にかかる結託耐性符号生成装置５００が行う結託耐性符号生成処理の手順を示すフローチャートである。
【符号の説明】
【００８２】
１００ 不正ユーザ検出装置
１０１ 閾値設定部
１０２ スコア計算部
１０３ 不正ユーザ判定部
２０１ 符号長設定部
２０２ 閾値設定部
２０３ スコア計算部
２０４ 不正ユーザ判定部
５００ 結託耐性符号生成装置
５０１ 誤り確率設定部
５０２ 符号長設定部
５０３ 結託耐性符号生成部
【特許請求の範囲】
【請求項１】
ユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号の一部又は全部をデジタルコンテンツから抽出する抽出手段と、
前記結託耐性符号のうち抽出された符号と、各ユーザに対して各々割り当てられた符号とを用いて、ビット毎の相関値を計算し、当該相関値の合計点をユーザ毎に計算する計算手段と、
抽出された前記符号の符号長に基づいて、不正ユーザの判定に用いる閾値を設定する第１設定手段と、
設定された前記閾値と、計算されたユーザ毎の前記合計点とを用いて、各ユーザが不正ユーザか否かを判定する判定手段とを備える
ことを特徴とする不正ユーザ検出装置。
【請求項２】
前記第１設定手段は、前記符号長に対して予め想定されている不正ユーザ数を計算し、当該不正ユーザ数を用いて前記閾値を計算して、前記閾値を設定する
ことを特徴とする請求項１に記載の不正ユーザ検出装置。
【請求項３】
不正ユーザであると前記判定手段が判定したユーザが１人もいない場合に、前記符号長を伸張する伸張手段と、
伸張された前記符号長に基づいて、前記閾値を再設定する第２設定手段とを更に備え、
前記判定手段は、再設定された前記閾値と、計算されたユーザ毎の前記合計点とを用いて、各ユーザが不正ユーザか否かを判定する
ことを特徴とする請求項１に記載の不正ユーザ検出装置。
【請求項４】
前記判定手段が１人のユーザに対して不正ユーザであるか否かを判定可能な最大の回数が予め設定されており、
前記伸張手段は、各ユーザに対する前記判定手段による判定回数が最大の回数を超えていない場合且つ不正ユーザであると前記判定手段が判定したユーザが１人もいない場合に、前記符号長を伸張する
ことを特徴とする請求項３に記載の不正ユーザ検出装置。
【請求項５】
判定回数が増えるほど想定される不正ユーザ数が増えるように、前記判定回数に対応して前記不正ユーザ数が予め設定されており、
前記伸張手段は、前記判定回数に対応して予め設定された不正ユーザ数を用いて、前記符号長を再計算することにより、前記符号長を伸張し、
前記計算手段は、抽出された前記符号のうち、伸張された前記符号長の符号と、各ユーザに対して各々割り当てられた符号とを用いて、前記合計点をユーザ毎に計算する
ことを特徴とする請求項４に記載の不正ユーザ検出装置。
【請求項６】
デジタルコンテンツに対してユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号を生成する結託耐性符号生成装置であって、
想定される不正ユーザ数と、ユーザ数と、ユーザを不正ユーザであると誤って判定する誤り確率とに基づいて、符号長を設定する設定手段と、
設定された符号長の結託耐性符号を生成する生成手段とを備え、
前記設定手段は、前記結託耐性符号を用いて不正ユーザを検出する不正ユーザ検出装置において不正ユーザであるか否かを判定する処理が一ユーザにつき複数回行われ得る場合、当該処理が行われ得る最大の回数ｔ（ｔ：２以上の整数）に応じて、前記符号長を設定する
ことを特徴とする結託耐性符号生成装置。
【請求項７】
前記設定手段は、
前記結託耐性符号を用いて不正ユーザを検出する不正ユーザ検出装置において不正ユーザであるか否かを判定する処理が一ユーザにつき最大ｔ回行われ得る場合、前記処理が行われ得る最大の回数が１回の場合と比較して１／ｔ以下となるように、前記誤り確率を再設定する確率設定手段と、
再設定された前記誤り確率と、前記不正ユーザ数と、前記ユーザ数とに基づいて、符号長を設定する符号長設定手段とを有する
ことを特徴とする
請求項６に記載の結託耐性符号生成装置。
【請求項８】
コンピュータを、
ユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号の一部又は全部をデジタルコンテンツから抽出する抽出手段と、
前記結託耐性符号のうち抽出された符号と、各ユーザに対して各々割り当てられた符号とを用いて、ビット毎の相関値を計算し、当該相関値の合計点をユーザ毎に計算する計算手段と、
抽出された前記符号の符号長に基づいて、不正ユーザの判定に用いる閾値を設定する第１設定手段と、
設定された前記閾値と、計算されたユーザ毎の前記合計点とを用いて、各ユーザが不正ユーザか否かを判定する判定手段として機能させることを特徴とするプログラム。
【請求項９】
コンピュータを、
デジタルコンテンツに対してユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号を生成する結託耐性符号生成装置であって、
想定される不正ユーザ数と、ユーザ数と、ユーザを不正ユーザであると誤って判定する誤り確率とに基づいて、符号長を設定する設定手段と、
設定された符号長の結託耐性符号を生成する生成手段として機能させ、
前記設定手段は、前記結託耐性符号を用いて不正ユーザを検出する不正ユーザ検出装置において不正ユーザであるか否かを判定する処理が一ユーザにつき複数回行われ得る場合、当該処理が行われ得る最大の回数ｔ（ｔ：２以上の整数）に応じて、前記符号長を設定する
ことを特徴とするプログラム。
【請求項１】
ユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号の一部又は全部をデジタルコンテンツから抽出する抽出手段と、
前記結託耐性符号のうち抽出された符号と、各ユーザに対して各々割り当てられた符号とを用いて、ビット毎の相関値を計算し、当該相関値の合計点をユーザ毎に計算する計算手段と、
抽出された前記符号の符号長に基づいて、不正ユーザの判定に用いる閾値を設定する第１設定手段と、
設定された前記閾値と、計算されたユーザ毎の前記合計点とを用いて、各ユーザが不正ユーザか否かを判定する判定手段とを備える
ことを特徴とする不正ユーザ検出装置。
【請求項２】
前記第１設定手段は、前記符号長に対して予め想定されている不正ユーザ数を計算し、当該不正ユーザ数を用いて前記閾値を計算して、前記閾値を設定する
ことを特徴とする請求項１に記載の不正ユーザ検出装置。
【請求項３】
不正ユーザであると前記判定手段が判定したユーザが１人もいない場合に、前記符号長を伸張する伸張手段と、
伸張された前記符号長に基づいて、前記閾値を再設定する第２設定手段とを更に備え、
前記判定手段は、再設定された前記閾値と、計算されたユーザ毎の前記合計点とを用いて、各ユーザが不正ユーザか否かを判定する
ことを特徴とする請求項１に記載の不正ユーザ検出装置。
【請求項４】
前記判定手段が１人のユーザに対して不正ユーザであるか否かを判定可能な最大の回数が予め設定されており、
前記伸張手段は、各ユーザに対する前記判定手段による判定回数が最大の回数を超えていない場合且つ不正ユーザであると前記判定手段が判定したユーザが１人もいない場合に、前記符号長を伸張する
ことを特徴とする請求項３に記載の不正ユーザ検出装置。
【請求項５】
判定回数が増えるほど想定される不正ユーザ数が増えるように、前記判定回数に対応して前記不正ユーザ数が予め設定されており、
前記伸張手段は、前記判定回数に対応して予め設定された不正ユーザ数を用いて、前記符号長を再計算することにより、前記符号長を伸張し、
前記計算手段は、抽出された前記符号のうち、伸張された前記符号長の符号と、各ユーザに対して各々割り当てられた符号とを用いて、前記合計点をユーザ毎に計算する
ことを特徴とする請求項４に記載の不正ユーザ検出装置。
【請求項６】
デジタルコンテンツに対してユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号を生成する結託耐性符号生成装置であって、
想定される不正ユーザ数と、ユーザ数と、ユーザを不正ユーザであると誤って判定する誤り確率とに基づいて、符号長を設定する設定手段と、
設定された符号長の結託耐性符号を生成する生成手段とを備え、
前記設定手段は、前記結託耐性符号を用いて不正ユーザを検出する不正ユーザ検出装置において不正ユーザであるか否かを判定する処理が一ユーザにつき複数回行われ得る場合、当該処理が行われ得る最大の回数ｔ（ｔ：２以上の整数）に応じて、前記符号長を設定する
ことを特徴とする結託耐性符号生成装置。
【請求項７】
前記設定手段は、
前記結託耐性符号を用いて不正ユーザを検出する不正ユーザ検出装置において不正ユーザであるか否かを判定する処理が一ユーザにつき最大ｔ回行われ得る場合、前記処理が行われ得る最大の回数が１回の場合と比較して１／ｔ以下となるように、前記誤り確率を再設定する確率設定手段と、
再設定された前記誤り確率と、前記不正ユーザ数と、前記ユーザ数とに基づいて、符号長を設定する符号長設定手段とを有する
ことを特徴とする
請求項６に記載の結託耐性符号生成装置。
【請求項８】
コンピュータを、
ユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号の一部又は全部をデジタルコンテンツから抽出する抽出手段と、
前記結託耐性符号のうち抽出された符号と、各ユーザに対して各々割り当てられた符号とを用いて、ビット毎の相関値を計算し、当該相関値の合計点をユーザ毎に計算する計算手段と、
抽出された前記符号の符号長に基づいて、不正ユーザの判定に用いる閾値を設定する第１設定手段と、
設定された前記閾値と、計算されたユーザ毎の前記合計点とを用いて、各ユーザが不正ユーザか否かを判定する判定手段として機能させることを特徴とするプログラム。
【請求項９】
コンピュータを、
デジタルコンテンツに対してユーザ毎に異なって埋め込まれる符号であって結託攻撃を行った不正ユーザを追跡可能な結託耐性符号を生成する結託耐性符号生成装置であって、
想定される不正ユーザ数と、ユーザ数と、ユーザを不正ユーザであると誤って判定する誤り確率とに基づいて、符号長を設定する設定手段と、
設定された符号長の結託耐性符号を生成する生成手段として機能させ、
前記設定手段は、前記結託耐性符号を用いて不正ユーザを検出する不正ユーザ検出装置において不正ユーザであるか否かを判定する処理が一ユーザにつき複数回行われ得る場合、当該処理が行われ得る最大の回数ｔ（ｔ：２以上の整数）に応じて、前記符号長を設定する
ことを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００９−１６３６０４（Ｐ２００９−１６３６０４Ａ）
【公開日】平成２１年７月２３日（２００９．７．２３）
【国際特許分類】
【出願番号】特願２００８−２０５２（Ｐ２００８−２０５２）
【出願日】平成２０年１月９日（２００８．１．９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２１年７月２３日（２００９．７．２３）
【国際特許分類】
【出願日】平成２０年１月９日（２００８．１．９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]