(57)【要約】【課題】所定の安全性条件を満たす符号長の結託耐性符号を生成する結託耐性符号生成装置を提供する。【解決手段】第１パラメータ設定器１１０は、正規ユーザを誤って追跡してしまう確率を一定値以下に抑える算式を満たす第１パラメータを設定する。第２パラメータ設定器１２０は、不正ユーザを一人も追跡できない確率を一定値以下に抑える算式を満たす第２パラメータを設定する。符号生成確率分布変換器１３０は、入力された符号生成確率分布を１／ユーザ数（ｎ）刻みの確率分布に変更する。符号長計算器１４０は、第１パラメータと第２パラメータと符号生成確率分布とに基づいて、結託耐性符号として必要な符号長ｍを計算する。符号生成器１５０は、符号長計算器１４０が計算した符号長ｍと符号生成確率分布変換器１３０が出力した符号生成確率分布とを基にユーザ数ｎ分の結託耐性符号を生成する。【選択図】        図１
2009017442.tif 000002
【特許請求の範囲】
【請求項１】
デジタルコンテンツに対してユーザ毎に異なって埋め込まれる符号であって結託攻撃を行ったユーザを追跡可能な結託耐性符号を、ビット毎に独立に定められた符号生成確率を用いて生成する結託耐性符号生成装置であって、
結託攻撃を行っていない正規ユーザを誤って追跡する確率を第１の一定値以下に抑える算式を満たす第１パラメータを設定する第１パラメータ設定器と、
結託攻撃を行った不正ユーザを１人も追跡できない確率を第２の一定値以下に抑える算式を満たす第２パラメータを設定する第２パラメータ設定器と、
前記符号生成確率の確率分布の入力を受け付け、当該確率分布を、確率変数が１／ユーザ数毎となる確率分布に変更する確率分布変換器と、
前記第１パラメータ設定器が設定した前記第１パラメータと、前記第２パラメータ設定器が設定した前記第２パラメータと、前記確率分布変換器が変更した前記確率分布とに基づいて、符号長を計算する符号長計算器と、
前記符号長計算器が計算した前記符号長と前記確率分布変換器が変更した前記確率分布とを用いて、前記結託耐性符号を生成する符号生成器と、を備える
ことを特徴とする結託耐性符号生成装置。
【請求項２】
前記第２パラメータ設定器が前記第２パラメータを設定する処理、前記確率分布変換器が前記確率分布を変更する処理及び前記第１パラメータ設定器が前記第１パラメータを設定する処理の順に処理を行う
ことを特徴とする請求項１に記載の結託耐性符号生成装置。
【請求項３】
前記第１パラメータ設定器は、結託攻撃を行ったと想定される結託者数の逆数に比例する値を前記第１パラメータとして設定し、
前記第２パラメータ設定器は、前記結託者数の１．５乗の逆数に比例する値を前記第２パラメータとして設定する
ことを特徴とする請求項１又は請求項２に記載の結託耐性符号生成装置。
【請求項４】
前記第２パラメータ設定器が前記第２パラメータを設定する処理、前記確率分布変換器が前記確率分布を変更する処理及び前記第１パラメータ設定器が前記第１パラメータを設定する処理のうち少なくとも１つを複数回行う
ことを特徴とする請求項１乃至請求項３のいずれか一項に記載の結託耐性符号生成装置。
【請求項５】
前記処理を複数回行うことに伴い、前記符号長計算器が前記符号長を計算する処理を複数回行う
ことを特徴とする請求項４の結託耐性符号生成装置。
【請求項６】
前記符号長計算器が計算した前記符号長が適切であるか否かを判定する符号長判定器を備える
ことを特徴とする請求項１乃至請求項５のいずれか一項に記載の結託耐性符号生成装置。
【請求項７】
前記符号長判定器は、前記符号長計算器が計算した前記符号長が、前記確率分布変換器が入力を受け付けた前記確率分布によって計算された符号長よりも長い場合に、前記符号長が適切でないと判定する
ことを特徴とする請求項６の結託耐性符号生成装置。
【請求項８】
前記符号長計算器が計算した前記符号長が適切でないと前記符号長判定器が判定した場合、前記第１パラメータ設定器は、前記第１パラメータを再設定する
ことを特徴とする請求項６又は請求項７に記載の結託耐性符号生成装置。
【請求項９】
前記符号長計算器が計算した前記符号長が適切でないと前記符号長判定器が判定した場合、前記第２パラメータ設定器は、前記第２パラメータを再設定する
ことを特徴とする請求項６乃至請求項８のいずれか一項に記載の結託耐性符号生成装置。
【請求項１０】
前記符号長計算器が計算した前記符号長が適切でないと前記符号長判定器が判定した場合、前記確率分布変換器は、１／ユーザ数毎の前記確率変数のうち少なくとも１つに対する前記符号生成確率を変更して、前記確率分布を変更する
ことを特徴とする請求項６乃至請求項９のいずれか一項に記載の結託耐性符号生成装置。
【請求項１１】
前記符号長計算器は、前記ユーザ数及び結託攻撃を行ったと想定される結託者数の入力を受け付け、当該ユーザ数、当該結託者数、前記第１パラメータ、前記第２パラメータ及び前記確率分布に基づいて、前記符号長を計算する
ことを特徴とする請求項１乃至請求項１０のいずれか一項に記載の結託耐性符号生成装置。
【請求項１２】
デジタルコンテンツに対してユーザ毎に異なって埋め込まれる符号であって結託攻撃を行ったユーザを追跡可能な結託耐性符号を、ビット毎に独立に定められた符号生成確率を用いて生成する結託耐性符号生成方法であって、
結託攻撃を行っていない正規ユーザを誤って追跡する確率を第１の一定値以下に抑える算式を満たす第１パラメータを設定する第１パラメータ設定ステップと、
結託攻撃を行った不正ユーザを１人も追跡できない確率を第２の一定値以下に抑える算式を満たす第２パラメータを設定する第２パラメータ設定ステップと、
前記符号生成確率の確率分布の入力を受け付け、当該確率分布を、確率変数が１／ユーザ数毎となる確率分布に変更する確率分布変換ステップと、
前記第１パラメータ設定ステップで設定した前記第１パラメータと、前記第２パラメータ設定ステップで設定した前記第２パラメータと、前記確率分布変換器が変更した前記確率分布とに基づいて、符号長を計算する符号長計算ステップと、
前記符号長計算ステップで計算した前記符号長と前記確率分布変換器が変更した前記確率分布とを用いて、前記結託耐性符号を生成する符号生成ステップと、を含む
ことを特徴とする結託耐性符号生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツに埋め込まれた電子透かしの偽造に対抗するための結託耐性符号を生成する結託耐性符号生成装置及び方法に関わる。
【背景技術】
【０００２】
近年、コンピュータやネットワークの発達により、デジタルコンテンツを扱う場面が増えてきている。デジタルコンテンツには、非常に低いコストでオリジナルのコンテンツと全く同じコンテンツが作成できるという特徴がある。このため、デジタルコンテンツの著作権を保護するという観点から、デジタルコンテンツの違法コピーに対する対策は不可欠なものとなってきている。違法コピーを抑止するための対策として、例えば、電子透かし技術とフィンガープリンティングという技術とが用いられる。電子透かし技術とは、デジタルコンテンツにＩＤを埋め込む技術である。フィンガープリンティングとは、電子透かし技術によりデジタルコンテンツに埋め込まれたＩＤを用いてデジタルコンテンツを違法にコピーしたユーザ（以下、不正ユーザという）を追跡する技術である。
【０００３】
しかしながらフィンガープリンティングにおいては、異なるＩＤの埋め込まれたデジタルコンテンツを複数持ち寄り、これらのＩＤにおける相違点を書き換えることにより新たなＩＤを生成し、このＩＤによるユーザを識別不可能にする結託攻撃が行われる場合がある。これにより、不正ユーザを追跡不能になるため、結託攻撃に対する対策が不可欠である。この結託攻撃に対する対策として、例えば、ＩＤの代わりに結託耐性符号がデジタルコンテンツに埋め込まれるものとして用いられる。
【０００４】
結託耐性符号の例としてc-secure（with ε error）符号がある。これは、結託攻撃を行った結託者がｃ人までであるなら、その結託者（以下、不正ユーザという）を１人も追跡（告発）できない確率、あるいは、結託攻撃を行っていないユーザ（以下、正規ユーザという）を誤って追跡してしまう確率をε以下にすることができる符号である。この具体的な符号の構成例としてＴａｒｄｏｓ符号（非特許文献１参照）とＮＨＷＩ符号（非特許文献２参照）がある。これらの非特許文献１〜２の技術においては、符号シンボルのうち「１」を取る生起確率の分布をある規則に則ってビット毎に各々取ることにより、符号を構成する。
【０００５】
具体的には、非特許文献１においては、結託者の追跡を誤る確率（誤り確率）を上述した不正ユーザを１人も追跡できない確率及び正規ユーザを誤って追跡してしまう確率の２種類に分類し、これらの確率の和が一定値ε以下となるように符号を構成する。そして、このように構成された各ユーザの符号と、結託攻撃により生成された符号との相関をビット毎に求め、これを基にスコアを計算し、そのスコアが閾値Zを超えているユーザを不正ユーザであるとして告発する。あるユーザｊのスコアをSjとすると、式（１）を満たすときに、ユーザｊは告発される。
【０００６】
【数１】
2009017442.tif 000003
【０００７】
正規のユーザを誤って追跡してしまう確率をε1以下に抑えるためには、式（２）を満たす必要がある。
【０００８】
【数２】
2009017442.tif 000004
【０００９】
ここで、確率の上界を押さえる方法として、Markovの不等式を用いる。Markovの不等式では、非負の確率分布Xに対してある閾値aを定めると、式（３）が成り立つ。
【００１０】
【数３】
2009017442.tif 000005
【００１１】
尚、Pr[Y]は事象Yの起こる確率を表し、E[W]はWの期待値を表す。このときに確率の上界をより厳密に押さえるために、Sj,Zをα倍した上で指数関数とすると、以下の式（４）が成り立つ。
【００１２】
【数４】
2009017442.tif 000006
【００１３】
また、不正ユーザを一人も追跡できない確率をε２以下に抑えるためには、少なくとも以下の式５を満たせばよい。
【００１４】
【数５】
2009017442.tif 000007
【００１５】
尚、Cとは結託者の集合を表し、cは結託者数を表す。このときΣj∈CSj/cは結託者の平均スコアを表しており、平均スコアがZ以上であれば少なくとも1人のスコアはZを超えているはずであるので、上記式５を満たす場合には、不正ユーザを少なくとも１人は追跡して摘発することができる。
【００１６】
ここでも確率の上界を押さえるために、Markovの不等式を用いる。ただし、ここでは確率分布と閾値Ｚを−α´倍した後、指数関数化する。このとき、以下の式（６）が成り立つ。
【００１７】
【数６】
2009017442.tif 000008
【００１８】
このような符号の符号長を決定付ける要素としては、誤り確率、結託者数、ユーザ数、上記パラメータα、α´及び符号生成確率分布がある。誤り確率、結託者数とユーザ数は予め定まっているものとすると、パラメータα、α´及び符号生成確率分布に応じて符号長が定まることになる。例えば、符号生成確率分布を変更すると、その変更に応じて、同じ安全性条件（誤り確率、結託者数、ユーザ数）での符号長は増減する。
【００１９】
【非特許文献１】“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
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかしながら、実際に符号を構成する際、取り得る符号の生成確率（符号生成確率）は１／ユーザ数の刻みでしか取れない、即ち、符号生成確率の確率変数は、１／ユーザ数毎でなければならない。このため、想定していた確率分布をそのまま当てはめることができない場合があるという問題がある。非特許文献１の技術においては、符号生成確率をp=sin2(t)とし、ｔを一様に分布させることによって符号を構成している。このため、ｐは連続値となり、符号生成確率を１／ユーザ数の刻みに修正する必要がある。また、非特許文献２の技術においては、符号生成確率は離散値であるものの、やはり１／ユーザ数の刻みにはなっていない。このため、符号の生成確率を（１／ユーザ数）の刻みに修正する必要がある。しかし、非特許文献１〜２に記載されている結託耐性符号のように、各ビットの符号生成確率を独立に定める結託耐性符号においては、上述したように、パラメータα、α´と符号生成確率分布とが変わると、必要な符号長が変化する。このため、この符号生成確率分布を１／ユーザ数刻みに変更する、即ち、符号生成確率分布を、確率変数が１／ユーザ数毎となる確率分布に変更すると、元々想定していた符号長では要求される安全性条件を満たせない場合があったり、元々想定していた符号長が必要以上の長さである場合があったりする。
【００２１】
また、電子透かしとして結託耐性符号をデジタルコンテンツに埋め込む場合、想定した符号長でコンテンツへの符号の埋め込みを行うというアルゴリズムを予め決定すると、想定していたものよりも長い符号長の符号の埋め込みは困難となる場合がある。
【００２２】
本発明は、上記に鑑みてなされたものであって、所定の安全性条件を満たす符号長の結託耐性符号を生成する結託耐性符号生成装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００２３】
上述した課題を解決し、目的を達成するために、本発明は、デジタルコンテンツに対してユーザ毎に異なって埋め込まれる符号であって結託攻撃を行ったユーザを追跡可能な結託耐性符号を、ビット毎に独立に定められた符号生成確率を用いて生成する結託耐性符号生成装置であって、結託攻撃を行っていない正規ユーザを誤って追跡する確率を第１の一定値以下に抑える算式を満たす第１パラメータを設定する第１パラメータ設定器と、結託攻撃を行った不正ユーザを１人も追跡できない確率を第２の一定値以下に抑える算式を満たす第２パラメータを設定する第２パラメータ設定器と、前記符号生成確率の確率分布の入力を受け付け、当該確率分布を、確率変数が１／ユーザ数毎となる確率分布に変更する確率分布変換器と、前記第１パラメータ設定器が設定した前記第１パラメータと、前記第２パラメータ設定器が設定した前記第２パラメータと、前記確率分布変換器が変更した前記確率分布とに基づいて、符号長を計算する符号長計算器と、前記符号長計算器が計算した前記符号長と前記確率分布変換器が変更した前記確率分布とを用いて、前記結託耐性符号を生成する符号生成器と、を備えることを特徴とする。
【００２４】
また、本発明は、デジタルコンテンツに対してユーザ毎に異なって埋め込まれる符号であって結託攻撃を行ったユーザを追跡可能な結託耐性符号を、ビット毎に独立に定められた符号生成確率を用いて生成する結託耐性符号生成方法であって、結託攻撃を行っていない正規ユーザを誤って追跡する確率を第１の一定値以下に抑える算式を満たす第１パラメータを設定する第１パラメータ設定ステップと、結託攻撃を行った不正ユーザを１人も追跡できない確率を第２の一定値以下に抑える算式を満たす第２パラメータを設定する第２パラメータ設定ステップと、前記符号生成確率の確率分布の入力を受け付け、当該確率分布を、確率変数が１／ユーザ数毎となる確率分布に変更する確率分布変換ステップと、前記第１パラメータ設定ステップで設定した前記第１パラメータと、前記第２パラメータ設定ステップで設定した前記第２パラメータと、前記確率分布変換器が変更した前記確率分布とに基づいて、符号長を計算する符号長計算ステップと、前記符号長計算ステップで計算した前記符号長と前記確率分布変換器が変更した前記確率分布とを用いて、前記結託耐性符号を生成する符号生成ステップと、を含むことを特徴とする。
【発明の効果】
【００２５】
本発明によれば、不正ユーザの追跡を誤る確率が一定値以下に抑えられ、所定の安全性条件を満たす適切な符号長の結託耐性符号を生成することができる。
【発明を実施するための最良の形態】
【００２６】
以下に添付図面を参照して、この発明にかかる結託耐性符号生成装置及び方法の最良な実施の形態を詳細に説明する。
[第１の実施の形態]
（１）構成
図１は本実施の形態にかかる結託耐性符号生成装置１００の構成を示すブロック図である。同図に示される結託耐性符号生成装置１００は、第１パラメータ設定器１１０と、第２パラメータ設定器１２０と、符号生成確率分布変換器１３０と、符号長計算器１４０と、符号生成器１５０とを備えている。第１パラメータ設定器１１０は、正規ユーザを誤って追跡してしまう確率（誤り確率ε１）を第１の一定値以下に抑える算式を満たすパラメータであり、当該確率の上界を押さえるために用いられるパラメータα（第１パラメータ）を設定する。第２パラメータ設定器１２０は、不正ユーザを一人も追跡できない確率（誤り確率ε２）を第２の一定値以下に抑える算式を満たすパラメータであり、当該確率の上界を押さえるために用いられるパラメータα´（第２パラメータ）を設定する。符号生成確率分布変換器１３０は、ビット毎に独立に定められた符号生成確率の確率分布（符号生成確率分布）を入力として受け取り、当該確率分布の確率変数を１／ユーザ数（ｎ）毎にする、即ち、当該確率分布を１／ユーザ数（ｎ）刻みの確率分布に変更する。尚、結託耐性符号生成装置１００は、各種設定値や計算値を保存するための記憶装置やユーザの操作が入力される操作装置(いずれも図示せず)を有している。符号生成確率分布は、例えば、この記憶装置に記憶されており、操作装置などを介して符号生成確率分布変換器１３０に入力される。
【００２７】
符号長計算器１４０は、第１パラメータ設定器１１０が設定したパラメータαと、第２パラメータ設定器１２０が設定したパラメータα´と、符号生成確率分布変換器１３０から出力された符号生成確率分布と、不正ユーザの追跡を誤る誤り確率εと、デジタルコンテンツを利用するユーザ数ｎと、想定される結託者数ｃとを入力として、結託耐性符号として必要な符号長ｍを計算する。誤り確率εとユーザ数ｎと結託者数ｃとは、図示しない操作装置などを介して結託耐性符号生成装置１００に入力される。誤り確率ε１及び誤り確率ε２は誤り確率εに基づいて定まる。符号生成器１５０は、符号長計算器１４０が計算した符号長ｍと符号生成確率分布変換器１３０が出力した符号生成確率分布とを基にユーザ数ｎ分の結託耐性符号を生成する。
【００２８】
（２）動作
次に、本実施の形態にかかる結託耐性符号生成装置１００の動作について説明する。図２は本実施の形態にかかる結託耐性符号生成装置１００の動作を示すフローチャートである。本実施の形態は、結託耐性符号の構成として上述したＴａｒｄｏｓ符号の構成を基に設計する。
【００２９】
まず、結託耐性符号生成装置１００の第１パラメータ設定器１１０がαの値を設定すると共に、第２パラメータ設定器１２０がα´の値を設定する（ステップＳ１０１）。ここでは、Ｔａｒｄｏｓ符号の構成に倣い、α＝１／（１０ｃ）、α´＝１／（２０ｃ）とする。但し、これらのパラメータα，α´の値はこの例に限るものではない。
【００３０】
次に、符号生成確率分布変換器１３０が、初期値を設定する（ステップＳ１０２）。ここでは、符号生成確率分布変換器１３０は、初期値として、結託耐性符号におけるビット順を表すｉを「１」に設定し、符号生成確率分布ｒ´における１≦ｊ≦ｎ−１となるすべてのｊにつきｒ´ｊを「０」に設定する。尚、この符号生成確率分布ｒ´はｐ＝ｓｉｎ２（ｔ）でｔを一様分布させることにより得られる。ここで、符号生成確率分布変換器１３０は、一様分布であるｔをｕ個の点に分割することを考え、ｔ＝πｉ／２ｕとし、ｐｉ＝ｓｉｎ２（ｔ）を計算する（ステップＳ１０３）。ｐｉとは、ｉビット目の「１」の生成確率である。次に、符号生成確率分布変換器１３０は、ｐｉが最もｊ／ｎに近づくｊの値を探し、「ｒ´ｊ＝ｒ´ｊ＋１」とする（ステップＳ１０４）。次に、符号生成確率分布変換器１３０は、ｉが「ｕ−１」以下であるかどうかを調べ（ステップＳ１０５）、ｉが「ｕ−１」以下である場合（ステップＳ１０５:ＹＥＳ）、ｔの値を変えた値での符号生成確率分布ｒ´を計算するために「i＝i＋１」とし（ステップＳ１１５）、ステップＳ１０３に戻る。ｉが「ｕ−１」より大きい場合（ステップＳ１０５:ＮＯ）、符号生成確率分布変換器１３０は、一様分布となっているｔの値はすべて調べたものとして、ステップＳ１０６に進む。ステップＳ１０６では、符号生成確率分布変換器１３０は、１≦ｊ≦ｎ−１にあるすべてのｊに関して、「ｒ´ｊ＝ｒ´ｊ／（ｕ−１）」を計算し、「Σｒ´ｊ＝１」となるようにして、符号生成確率分布ｒ´を求める（ステップＳ１０６）。ここで求められる符号生成確率分布ｒ´は、１／ユーザ数（ｎ）刻みの確率分布に変更されている。
【００３１】
その後、符号長計算器１４０が、ステップＳ１０６で求められた符号生成確率分布ｒ´と、予め定められた誤り確率ε、ユーザ数ｎ及び結託者数ｃとを基に符号長ｍを計算する（ステップＳ１０７）。そして、符号生成器１５０が、ステップＳ１０７で計算された符号長ｍを基に結託耐性符号を生成し、終了する（ステップＳ１０８）。
【００３２】
以上のようにして符号長ｍを求め、この符号長ｍの結託耐性符号を生成することにより、不正ユーザの追跡を誤る確率を所定の確率以下に抑え、所定の安全性条件を満たす適切な符号長の結託耐性符号を生成することができる。
【００３３】
[第２の実施の形態]
次に、結託耐性符号生成装置の第２の実施の形態について説明する。なお、上述の第１の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００３４】
上述の第１の実施の形態においては、与えられた確率ｐの値を、この値に最も近い（１／ユーザ数）刻みの値を取るように近似して、符号生成確率分布ｒ´を求めた。しかし、所定の安全条件を満たしつつ、符号長ｍを更に短くできる符号生成確率分布が存在する可能性がある。なぜなら、上述したように、符号生成確率を変更すると符号長に影響が及ぼされるが、この影響は必ずしも符号長を長くする方向に及ぼされるわけではないからである。例えば、結託者数ｃが「２」の場合、「１」となる符号生成確率が全てのビットにおいて１／２とすると、最も短い結託耐性符号が生成可能なことが理論的にわかっている。しかしながら、Ｔａｒｄｏｓ符号においては、ｐ＝ｓｉｎ２（ｔ）とし、tをある範囲で一様分布させることにより確率分布を構成しているため、Ｔａｒｄｏｓ符号よりも符号長を短くできる符号生成確率分布（すべて1／２に設定）が存在することは明らかであるからである。そこで、本実施の形態においては、所定の安全条件を満たす最短の符号長ｍの結託耐性符号を構成すべく、符号長に影響を与えるパラメータであるα、α´と符号生成確率分布ｒｊの設定を複数回行う。これにより、結託耐性符号を電子透かしとしてデジタルコンテンツに埋め込む場合、符号長が長くなってしまうと符号の埋め込みが困難になってしまうという問題を解決可能にする。
【００３５】
（１）構成
図３は、本実施の形態にかかる結託耐性符号生成装置２００の構成を示すブロック図である。本実施の形態にかかる結託耐性符号生成装置２００の構成は、上述の第１の実施の形態にかかる結託耐性符号生成装置２００の構成とは以下の点で異なる。結託耐性符号生成装置２００は、第1パラメータ設定器２１０と、第２パラメータ設定器２３０と、符号生成確率分布変換器２２０と、符号長計算器２４０と、符号生成器２６０とに加え、符号長判定器２５０を備えている。第1パラメータ設定器２１０と、第２パラメータ設定器２３０と、符号生成確率分布変換器２２０と、符号長計算器２４０と、符号生成器２６０との構成は、上述の第１の実施の形態で説明した第1パラメータ設定器１１０と、第２パラメータ設定器１２０と、符号生成確率分布変換器１３０と、符号長計算器１４０と、符号生成器１５０との構成と各々略同じであるため、その説明を省略する。符号長判定器２５０は、符号長計算器２４０で計算された符号長ｍが所定の範囲内にあるか否かを判定し、当該判定結果が肯定的である場合、符号長計算器２４０で計算された符号長ｍを基に符号生成器２６０が結託耐性符号を生成する。また、符号長判定器２５０の判定結果が否定的である場合、第1パラメータ設定器２１０がαの値を再設定すると共に、第２パラメータ設定器２３０がα´の値を再設定して、符号生成確率分布変換器２２０が符号生成確率分布を変更し、符号長計算器２４０が符号長ｍを再計算する。
【００３６】
（２）動作
次に、本実施の形態にかかる結託耐性符号生成装置２００の動作について説明する。図４は、本実施の形態にかかる結託耐性符号生成装置２００の動作を示すフローチャートである。尚、上述の第１の実施の形態と共通する部分についてはその説明を省略する場合がある。
【００３７】
なお、本実施の形態においては、上述の従来技術において説明したスコアを式（７）により求めるものとする。
【００３８】
【数７】
2009017442.tif 000009
【００３９】
また、符号長ｍを式（８）により計算するものとする。
【００４０】
【数８】
2009017442.tif 000010
【００４１】
また、評価式Ａ(α)、Ｂ(α´)は各々式（９）、（１０）となっている。
【００４２】
【数９】
2009017442.tif 000011
【００４３】
【数１０】
2009017442.tif 000012
【００４４】
なお、ｋ１、ｋ２については、以下の式（１１）、（１２）と各々表現すべきである。
【００４５】
【数１１】
2009017442.tif 000013
【００４６】
【数１２】
2009017442.tif 000014
【００４７】
しかし、1人以上の不正ユーザがいる状況では多くとも（ｎ−１）人が正規ユーザであるので、（ｎ−１）×（正規のユーザを誤って追跡してしまう確率：ε１）＋（不正ユーザを一人も追跡できない確率：ε２）を設定した誤り確率（ε）以下とすれば誤り確率はεを上回ることはない。すなわち、以下の式（１３）が成立する。
【００４８】
【数１３】
2009017442.tif 000015
【００４９】
このことから、ｍを最小化するε１，ε２を求めると、ε１，ε２は、それぞれ、式（１４）、（１５）により求められる。
【００５０】
【数１４】
2009017442.tif 000016
【００５１】
【数１５】
2009017442.tif 000017
【００５２】
まず、第２パラメータ設定器２３０は、初期値として「ｉ＝０」に設定し、「α´＝１/(０．０１ｃ3/2)」に設定し、「a´＝０．０」に設定し、「ｄｉ＝１．０」に設定する(ステップＳ２０１)。なお、ｄｉはa´のプロット間隔を決定する値である。
【００５３】
次に、符号生成確率分布を仮決定するため、符号生成確率分布変換器２２０は、符号生成確率分布出力処理を行う（ステップＳ２０２）。図５は、符号生成確率分布変換器２２０が行う符号生成確率分布出力処理の詳細な手順を示すフローチャートである。
【００５４】
ここでの手順は、符号生成確率分布変換器２２０が、符号生成確率分布の取り得る値をある刻みごとに減らしていき、最終的にＢ(α´)が閾値ＢＴＨ以下となる又はＢ(α´)が最小となる符号生成確率分布を得られるようになっている。
【００５５】
ここで与えられる符号生成確率分布は、上述の第１の実施の形態で説明した図２におけるＳ１０２とＳ１０３〜Ｓ１０５，Ｓ１１５を繰り返し行った後に得られるｒ´と同様のものを扱うとする。連続値として符号生成確率分布が与えられた場合は、実施例１と同様の手法により離散的な確率分布であるｒ´を求めれば良い。なお、ここでは、以下の式（１６）〜（１７）を用いる。
【００５６】
【数１６】
2009017442.tif 000018
【００５７】
【数１７】
2009017442.tif 000019
【００５８】
符号生成確率分布変換器２２０は、図５のステップＳ３０１において、与えられた符号生成確率分布ｒとパラメータα´を基にＢ（α´）を計算し、Ｂminとして符号生成確率分布ｒとともに保存する。次に、符号生成確率分布変換器２２０は、初期値として「ｕ＝Σｒ´ｊ（１≦ｊ≦ｎ−１）」を設定し（ステップＳ３０２）、さらに「ｉ＝１」に設定し、ｕを「１」減らす（ステップＳ３０３）。次に、符号生成確率分布変換器２２０は、ｒ´ｉが「０」でないかどうかを判定する（ステップＳ３０４）。このとき、ｒ´ｉが「０」であれば、符号生成確率分布変換器２２０は、ｉを「１」増やし（ステップＳ３１０）、このｉが「ｎ」未満か否かを判定し（ステップＳ３１１）、当該判定結果が肯定的であれば、ステップＳ３０４の処理を再度行う。また、ステップＳ３０４で、ｒ´ｉが「０」でない場合、符号生成確率分布変換器２２０は、符号生成確率分布ｒｊを「ｒｊ＝ｒ´ｊ／ｕ」に設定する。また、符号生成確率分布変換器２２０は、添え字ｉのところではｒ´ｉを「１」減らした値でｒｉを計算する、すなわち、「ｒｉ＝(ｒ´ｉ−１)／ｕ」を計算する（ステップＳ３０５）。次に、符号生成確率分布変換器２２０は、ステップＳ３０５で得られた符号生成確率分布ｒを基にＢ（α´）を計算する（ステップＳ３０６）。そして、符号生成確率分布変換器２２０は、ステップＳ３０６で計算したＢ（α´）の値が予め設定しておいたＢＴＨより小さいか否かを判定し（ステップＳ３０７）、当該判定結果が肯定的であれば、計算したＢ（α´）と符号生成確率分布ｒとを出力して（ステップＳ３１５）、符号生成確率分布出力処理を終了する。ステップＳ３０７の判定結果が否定的である場合には、符号生成確率分布変換器２２０は、ステップＳ３０８に進む。
【００５９】
なお、ＢＴＨは予め設定されるようにしたが、例えば、入力として与えられた符号生成確率分布ｒを基に計算されたＢの値をＢＴＨとして設定するようにしても良い。また、最終的に最も短い符号長ｍを求めたい場合は、ステップＳ３０７は省略しても良い。
【００６０】
ステップＳ３０８では、符号生成確率分布変換器２２０は、ステップＳ３０６で計算されたＢ（α´）が今まで計算されたＢの中で最小であるかどうかを判定する。即ち、符号生成確率分布変換器２２０は、ステップＳ３０６で計算されたＢ（α´）が、今まで計算されたＢの中の最小値Ｂminより大きいか否かを判定する。当該判定結果が肯定的である場合、符号生成確率分布変換器２２０は、「ｉ´＝ｉ」に設定し、「Ｂmin＝Ｂ」に設定し、符号生成確率分布ｒを保存し（ステップＳ３０９）、その後、上述したステップＳ３１０に進む。ステップＳ３０８の判定結果が否定的である場合には、符号生成確率分布変換器２２０は、ステップＳ３１０へ進む。
【００６１】
そして、符号生成確率分布変換器２２０は、ｉがｎ未満であるうちは、ステップＳ３０４からの処理を繰り返し、ｉがｎになると、ステップＳ３１２へと進む。即ち、ここでは、ステップＳ３０４からステップＳ３１１までの処理は、ステップＳ３０７を除いて考えると、１／ｎ刻みで設定された符号生成確率の１点の生起確率を下げてみて、その中で最もＢの値を小さくできる点を探し出すという処理となっている。
【００６２】
次に、ステップＳ３１２では、符号生成確率分布変換器２２０は、ｒ´ｉの生起確率を下げるため、「ｒ´ｉ＝ｒ´ｉ−１」とする。次いで、符号生成確率分布変換器２２０は、ｕが２以上かどうかを判定することにより、生起確率をまだ下げられる点が存在するか否かを判定する（ステップＳ３１３）。当該判定結果が肯定的である場合、符号生成確率分布変換器２２０は、Ｓ３０３からの処理を繰り返す。ステップＳ３１３の判定結果が否定的である場合、符号生成確率分布変換器２２０は、保存してあるＢminと符号生成確率分布ｒとを出力して（ステップＳ３１４）、符号生成確率分布出力処理を終了する（ステップＳ２０２）。
【００６３】
以上のようにして、符号生成確率分布変換器２２０が符号生成確率分布ｒを書き換えたら、図４に戻り、第１パラメータ設定器２１０は、初期値として「ｊ＝０」を設定し、「α０＝１／（０．０１ｃ）」を設定し、「ａ＝０．０」を設定し、「ｄｊ＝１．０」を設定する（ステップ２０３）。なお、ｄｊはａのプロット間隔を決定する値である。次いで、符号長計算器２４０は、ステップＳ２０３で設定された各パラメータの値と、符号生成確率分布ｒとを用いて、符号長ｍｉｊを計算する（ステップＳ２０４）。次に、符号長判定器２５０が、ステップＳ２０４で計算された符号長ｍｉｊが、予め設定された閾値ｍＴＨ以下であるか否かを判定する（ステップＳ２０５）。当該判定結果が肯定的である場合、符号生成器２６０が、ステップＳ２０４で計算された符号長ｍｉｊと符号生成確率分布ｒとを基に符号を生成する（ステップＳ２０６）。ステップＳ２０５の判定結果が否定的である場合、符号長判定器２５０は、ｄｊが、予め設定された閾値ｄｊＴＨよりも小さいか否かを判定する（ステップＳ２１５）。なお、ｄｊＴＨはこの処理における精度を決定する値であり、精度の高い結果を求める場合はｄｊＴＨを小さくする必要がある。
【００６４】
ステップＳ２１５の判定結果が否定的である場合には、αの値を変えて符号長を再計算するため、以下のようにして、αを再設定する処理を行う。まず、ｊが「０」であるか、又は、符号長ｍｉｊが符号長ｍｉｊ−１よりも小さい、即ち、符号長ｍｉｊがそれまでに計算された符号長の中で最短であるか否かを符号長判定器２５０は判定する(ステップＳ２６６)。当該判定結果が否定的である場合、精度を高めるため、第１パラメータ設定器２１０は、ｄｊの値を半分にすべく、「ｄｊ＝ｄｊ／２」を設定する。また、第１パラメータ設定器２１０は、「ａ＝ａ−ｄｊ」を設定し（ステップＳ２６７）、ステップＳ２６８に進む。尚、ステップＳ２６６の判定結果が肯定的である場合には、第１パラメータ設定器２１０は、「ａ＝ａ+ｄｊ」を設定し（Ｓ２７７）、ステップＳ２６８に進む。ステップＳ２６８では、第１パラメータ設定器２１０は、「ｊ＝ｊ＋１」を設定し、「αｊ＝１／（ａｃ）」を設定する。その後、ステップＳ２０４に進み、符号長計算器２４０が符号長ｍｉｊを再計算する。
【００６５】
尚、ステップＳ２１５の判定結果が肯定的である場合には、αに関しては十分な精度で計算処理が終わったものと判定し、α´の値をα同様に変えて、符号長を再計算するため、以下のようにして、α´を再設定する処理を行う。まず、ｉが「０」であるか、又は、符号長ｍｉ-1xが符号長ｍiyよりも大きいか否かを符号長判定器２５０は判定する(ステップＳ２１６)。当該判定結果が否定的である場合、精度を高めるため、第２パラメータ設定器２３０は、ｄｉの値を半分にすべく、「ｄｉ＝ｄｉ／２」を設定する。また、第２パラメータ設定器２３０は、「ａ´＝ａ´−ｄｊ」を設定し（Ｓ２２７）、ステップＳ２１８に進む。尚、ステップＳ２１６の判定結果が肯定的である場合には、第２パラメータ設定器２３０は、「ａ´＝ａ´+ｄｊ」を設定し（Ｓ２１７）、ステップＳ２１８に進む。ステップＳ２１８では、第２パラメータ設定器２３０は、「ｉ＝ｉ＋１」を設定し、「α´ｉ＝１／（ａｃ3/2）」を設定する。その後、ステップＳ２１９に進む。ステップＳ２１９では、符号長判定器２５０は、ｄｉがｄｉＴＨよりも小さいか否かを判定し、当該判定結果が肯定的である場合は、設定された精度と条件とでは所定の安全性条件を満たす結託耐性符号は生成できないものとして処理を終了する。ステップＳ２１９の判定結果が否定的である場合には、ステップＳ２０２に進み、符号生成確率分布変換器２２０が符号生成確率分布出力処理を行う。
【００６６】
以上のようにして、ステップＳ２０１でα´を仮決定し、ステップＳ２０２で符号生成確率分布ｒを仮決定してＢ(α´)を計算し、ステップＳ２０３でαを仮決定し、ステップＳ２０４で符号長ｍijを計算する。この符号長ｍijが予め設定された閾値ｍTH以下にならない場合には、Ｓ２６６〜２６８，Ｓ２７７の処理を繰り返してαの値を変えて、符号長ｍijの再計算を繰り返す。そして、ステップＳ２１５の判定結果が肯定的となった場合には、ステップＳ２１６，Ｓ２１７，Ｓ２２７，Ｓ２１８の処理によってα´の値を変えて、Ｓ２０２の処理によって符号生成確率分布ｒを仮決定してＢ(α´)を計算し、符号長ｍijを再計算する。即ち、α´の仮決定、Ｂ(α´)の計算及びαの仮決定をこの順に繰り返し行うことにより、符号長ｍがｍTH以下となる場合の各パラメータの値を探索する。これは、符号長ｍを計算するための上述の式（８）の分母におけるＢ(α´)の値を「０」より小さく且つできるだけ小さい値にするために行う。α´の仮決定の後Ｂ(α´)の計算を行うのは、Ｂ(α´)の値はα´に依存するからであり、Ｂ(α´)の計算の後にαの仮決定を行うのは、Ｂ(α´)の計算は処理負担が大きいからである。このため、必要な設定を行いつつＢ(α´)の計算回数を極力減らすべく、このような順に処理を繰り返し行ってパラメータの値を探索することにより、所定の安全条件を満たす適切な符号長ｍを効率良く計算することができる。
【００６７】
また、αには、１／ｃに比例する値を設定し、α´には、１／ｃ3/2に比例する値を設定することにより、符号長の算出をより効率的に行うことができる。なぜなら、符号長を短くできるα、α´の値では、ｃαとｃ３/２α´が各々ほぼ一定の値を取るということが実験的に分かっているからである（表１参照）。即ち、ｃ、ｃ３/２とこのような関係にあるα、α’の各初期値をこの近傍に定めることにより、符号長の算出をより効率的に行うことができる。
【００６８】
【表１】
2009017442.tif 000020
【００６９】
[変形例]
また、上述した各実施の形態に限定されるものではなく、以下に例示するような種々の変形が可能である。
【００７０】
＜変形例１＞
上述した各実施の形態においては、パラメータの設定や結託耐性符号の構成は、Ｔａｒｄｏｓ符号の構成に倣ったが、本実施の形態においては、これに限らない。
【００７１】
また、パラメータαには、１／ｃに比例する値を設定し、パラメータα´には、１／ｃ3/2に比例する値を設定するようにしたが、α´も、１／ｃ2に比例する値を設定するようにしても良い。
【００７２】
また、確率の上界を押さえる方法として、Markovの不等式を用いたが、本実施の形態においては、これに限らない。
【００７３】
＜変形例２＞
上述した第２の実施の形態においては、ステップＳ２０５で符号長ｍijがｍTH以下となった時点でステップＳ２０６に進み、結託耐性符号の生成を行うようにした。しかし、符号長ｍijがｍTH以下になっても、設定された精度の範囲内で処理を継続し、最も短い符号長を取るパラメータ及び符号生成確率分布を用いて結託耐性符号を生成するようにしても良い。その場合は、ステップＳ２１９の後に、符号長を最短とするパラメータで結託耐性符号を生成するステップを追加すれば良い。
【図面の簡単な説明】
【００７４】
【図１】第１の実施の形態にかかる結託耐性符号生成装置１００の構成を示すブロック図である。
【図２】同実施の形態にかかる結託耐性符号生成装置１００の動作を示すフローチャートである。
【図３】第２の実施の形態にかかる結託耐性符号生成装置２００の構成を示すブロック図である。
【図４】同実施の形態にかかる結託耐性符号生成装置２００の動作を示すフローチャートである。
【図５】同実施の形態にかかる符号生成確率分布変換器２２０が行う符号生成確率分布出力処理の詳細な手順を示すフローチャートである。
【符号の説明】
【００７５】
１００  結託耐性符号生成装置
１１０  第１パラメータ設定器
１２０  第２パラメータ設定器
１３０  符号生成確率分布変換器
１４０  符号長計算器
１５０  符号生成器
２００  結託耐性符号生成装置
２１０  第１パラメータ設定器
２２０  符号生成確率分布変換器
２３０  第２パラメータ設定器
２４０  符号長計算器
２５０  符号長判定器
２６０  符号生成器
【図１】
2009017442.tif 000021
【図２】
2009017442.tif 000022
【図３】
2009017442.tif 000023
【図４】
2009017442.tif 000024
【図５】
2009017442.tif 000025