"電子透かし情報のビット列を含む第一符号語を生成する符号語生成部と、前記電子透かし情報に基づいて巡回シフト系列を生成するシフト系列生成部と、生成された前記巡回シフト系列に基づいて前記第一符号語を巡回シフトして第二符号語を生成するシフト部と、生成された前記第二符号語をコンテンツに埋め込む埋め込み部と、を備える電子透かし埋め込み装置。前記シフト系列生成部は、複数の乱数の系列に対して、前記電子透かし情報のビット列が示す数字を開始位置に決定し、前記開始位置からの乱数の系列を前記巡回シフト系列とする請求項1記載の電子透かし埋め込み装置。前記シフト部は、前記巡回シフト系列の乱数をシフト量にして前記第一符号語を巡回シフトして第二符号語を生成する処理を、乱数の系列順に繰り返し、前記埋め込み部は、前記コンテンツの最後に到達するまで、前記乱数の系列順に生成された第二符号語を、前記コンテンツに順番に埋め込む請求項2記載の電子透かし埋め込み装置。前記第一符号語は、前記電子透かし情報に、前記第一符号語の開始位置を表す位置検出符号及び前記シフト部のシフト量の特定に用いるシフト量検出符号を付加した符号である請求項1乃至3いずれか一項に記載の電子透かし埋め込み装置。電子透かし情報のビット列を含む第一符号語を生成し、前記電子透かし情報に基づいて巡回シフト系列を生成し、生成された前記巡回シフト系列に基づいて前記第一符号語を巡回シフトして第二符号語を生成し、生成された前記第二符号語をコンテンツに埋め込む処理をコンピュータが実行する電子透かし埋め込み方法。透かし検出対象のコンテンツから、電子透かし情報を含む第一符号語が、前記電子透かし情報に基づいて生成された巡回シフト系列を用いて巡回シフトされた複数の第二符号語を含む第一検出符号を検出する符号語検出部と、一の第二符号語に対し、他の第二符号語を巡回シフトしながら相互相関値を求めることでシフト量を検出し、前記シフト量で逆シフトした他の第二符号語と前記一の第二符号語とを累積して一の第二符号語を更新する処理を、全ての他の第二符号語に対して行うシフト系列検出部と、検出された前記シフト量を並べたシフト系列から、前記電子透かし情報の各候補を生成する候補生成部と、前記電子透かし情報の各候補と、累積された一の第二符号語との類似度に基づき、前記コンテンツに埋め込まれた電子透かし情報を検出する照合部と、を備える電子透かし検出装置。前記巡回シフト系列が、複数の乱数の系列に対して、前記電子透かし情報のビット列が示す開始位置からの乱数の系列である場合、前記候補生成部は、前記シフト系列と、前記乱数の系列との類似度が所定値以上である位置の数字を表すビット列を前記候補とする請求項6記載の電子透かし検出装置。透かし検出対象のコンテンツから、電子透かし情報を含む第一符号語が、前記電子透かし情報に基づいて生成された巡回シフト系列を用いて巡回シフトされた複数の第二符号語を含む第一検出符号を検出し、一の第二符号語に対し、他の第二符号語を巡回シフトしながら相互相関値を求めることでシフト量を検出し、前記シフト量で逆シフトした他の第二符号語と前記一の第二符号語とを累積して一の第二符号語を更新する処理を、全ての他の第二符号語に対して行い、検出された前記シフト量を並べたシフト系列から、前記電子透かし情報の各候補を生成し、前記電子透かし情報の各候補と、累積された一の第二符号語との類似度に基づき、前記コンテンツに埋め込まれた電子透かし情報を検出する処理をコンピュータが実行する電子透かし検出方法。しかしながら、上述した従来技術は、各々に課題がある。一つ目の技術は、結託攻撃を受けた場合の電子透かし情報の検出精度を理論的に保証する符号化方式であるが、動画データや音声データに透かしとして埋め込むには符号長が非常に長い。そのため、この技術は実用的でないという課題がある。また、透かし検出対象のコンテンツが結託攻撃されていない場合、より短い符号長で透かしを検出できるにも関わらず、不必要に長い符号を付加しなければならない。二つ目の技術は、ユーザ毎に異なる鍵で符号化しているため、検出時にユーザが未知の場合に全ての鍵で検出を試みなければならず、処理効率の観点で実用的ではないという課題がある。そこで、開示の技術は、上記問題に鑑みてなされたものであり、結託攻撃に対する耐性を持ち、実用性を向上させることができる電子透かし埋め込み装置、電子透かし埋め込み方法、電子透かし検出装置及び電子透かし検出方法を提供することを目的とする。開示の一態様における電子透かし埋め込み装置は、電子透かし情報のビット列を含む第一符号語を生成する符号語生成部と、前記電子透かし情報に基づいて巡回シフト系列を生成するシフト系列生成部と、生成された前記巡回シフト系列に基づいて前記第一符号語を巡回シフトして第二符号語を生成するシフト部と、生成された前記第二符号語をコンテンツに埋め込む埋め込み部と、を備える。また、開示の他の態様における電子透かし検出装置は、透かし検出対象のコンテンツから、電子透かし情報を含む第一符号語が、前記電子透かし情報に基づいて生成された巡回シフト系列を用いて巡回シフトされた複数の第二符号語を含む第一検出符号を検出する符号語検出部と、一の第二符号語に対し、他の第二符号語を巡回シフトしながら相互相関値を求めることでシフト量を検出し、前記シフト量で逆シフトした他の第二符号語と前記一の第二符号語とを累積して一の第二符号語を更新する処理を、全ての他の第二符号語に対して行うシフト系列検出部と、検出された前記シフト量を並べたシフト系列から、前記電子透かし情報の各候補を生成する候補生成部と、前記電子透かし情報の各候補と、累積された一の第二符号語との類似度に基づき、前記コンテンツに埋め込まれた電子透かし情報を検出する照合部と、を備える。開示の技術によれば、結託攻撃に対する耐性を持ち、実用性を向上させることができる。以下、各実施例について、添付図面を参照しながら説明する。[実施例1]<構成>図1は、情報処理装置1の構成の一例を示す図である。図1に示す情報処理装置1は、電子透かし情報を埋め込む電子透かし埋め込み装置として機能する。図1に示す情報処理装置1は、制御部10、主記憶部20、補助記憶部30、通信部40、記録媒体I/F装置50を有する。各部は、バスを介して相互にデータ送受信可能に接続されている。制御部10は、コンピュータの中で、各装置の制御やデータの演算、加工を行うCPUCentralProcessingUnitである。また、制御部10は、主記憶部20や補助記憶部30に記憶されたプログラムを実行する演算装置であり、通信部40や各記憶部からデータを受け取り、演算、加工した上で、出力部や各記憶部に出力する。また、制御部10は、例えば補助記憶部30に記憶される電子透かし情報を埋め込むためのプログラムを実行することで、電子透かし埋め込み機能の役割を果たす。主記憶部20は、ROMReadOnlyMemoryやRAMRandomAccessMemoryなどであり、制御部20が実行する基本ソフトウェアであるOSやアプリケーションソフトウェアなどのプログラムやデータを記憶又は一時保存する記憶装置である。補助記憶部30は、HDDHardDiskDriveなどであり、アプリケーションソフトウェアなどに関連するデータを記憶する記憶装置である。補助記憶部30には、通信部40から取得された映像や音楽などの電子化されたコンテンツや電子透かし情報を記憶する。また、補助記憶部30は、記録媒体60などから取得されたコンテンツや電子透かし情報を記憶しておいてもよい。通信部40は、有線又は無線で通信を行う。通信部40は、例えば、サーバなどから映像や音楽などのコンテンツや電子透かし情報を取得し、例えば補助記憶部30に記憶させる。記録媒体I/F部50は、USBUniversalSerialBusなどのデータ伝送路を介して接続された記録媒体60例えば、フラッシュメモリなどと情報処理装置1とのインターフェースである。また、記録媒体60に、所定のプログラムを格納し、この記録媒体60に格納されたプログラムは記録媒体I/Fインターフェース部50を介して情報処理装置1にインストールされる。インストールされた所定のプログラムは、情報処理装置1により実行可能となる。なお、記録媒体60を例えばSDカードとした場合は、記録媒体I/F部50は、SDカードスロットである。<電子透かし情報の埋め込み機能>次に、電子透かし情報を埋め込む機能を有する制御部10について詳しく説明する。図2は、制御部10における電子透かし埋め込み機能の一例を示すブロック図である。図2に示す制御部10は、符号語生成部101、シフト系列生成部102、シフト部103及び埋め込み部104を有する。符号語生成部101は、電子透かし情報のビット列を含む基準符号語を生成する。基準符号語は第一符号語とも呼ぶ。符号語生成部101は、電子透かし情報を通信部40又は補助記憶部30などから取得する。基準符号語は、位置検出符号と、シフト量検出符号と、電子透かし情報を修正した修正透かし情報とを含む。位置検出符号は、基準符号語の位置を特定するための符号である。シフト量検出符号は、後述するシフト量を特定するために用いる符号である。修正透かし情報は、電子透かし情報に対し、誤り検出符号及び/又は誤り訂正符号を付加した情報である。シフト系列生成部102は、シフト部103で巡回シフトするシフト量の系列を、電子透かし情報に基づいて生成する。シフト系列生成部102の処理については、図4を用いて後述する。シフト部103は、取得した基準符号語のうち、位置検出符号を除いた部分、例えば、シフト量検出符号及び修正透かし情報を、取得したシフト系列が示すシフト量で巡回シフトすることで、修正符号語を生成する。修正符号語は、第二符号語とも呼ばれる。また、シフト部103は、一つのコンテンツに対して、一つの基準符号語から複数の修正符号語を生成する。その際、シフト部103は、各修正符号語に対するシフト量として、シフト系列生成部102から取得した巡回シフト系列のシフト量を順番に用いる。埋め込み部104は、シフト部103で生成された修正符号語を、画像や音声等の埋め込み対象のコンテンツに電子透かしとして埋め込む。コンテンツは、補助記憶部30や通信部40から取得される。埋め込み部104は、電子透かし情報を埋め込むために、コンテンツに応じた様々な電子透かし情報の埋め込み方法の何れかを利用することができる。例えば、コンテンツが音声データである場合、埋め込み部104は、人の非可聴域に修正符号語を埋め込む。その際、埋め込み部104は、修正符号語に含まれるビット毎に、そのビットの値に応じた信号を生成する。そして、埋め込み部104は、修正符号語の先頭のビットから順に、各ビットの値に応じた信号を時系列に沿って音声データの非可聴域に重畳する。また、コンテンツが動画像データである場合、埋め込み部104は、動画像データに含まれる時系列順に並んだ複数の画像に対して、修正符号語の先頭のビットから順に、一つずつビットを埋め込む。例えば、埋め込み部104は、各画像のそれぞれの所定位置の画素の輝度値を、修正符号語の先頭のビットから順に、そのビットの値に応じた輝度値にする。なお、所定位置は、例えば、画像の4隅のいずれかの画素とすることができる。よって、実施例では、コンテンツに透かしを埋め込む方法については特に限定せず、種々の方法を適用することが可能である。<各部の詳細処理>次に、電子透かし埋め込み処理の各処理について詳しく説明する。《基準符号語の生成》図3は、基準符号語の生成を説明するための図である。図3に示す例では、符号語生成部101に入力された電子透かし情報には、埋め込み対象のコンテンツの著作権情報や、販売店情報、購入者情報などが含まれる。図3に示す例では、電子透かし情報は、ビット列b11に符号化されている。符号語生成部101は、この符号化された電子透かし情報を、誤り訂正および誤り検出可能な修正透かし情報b12に変換する。すなわち、符号語生成部101は、取得した電子透かし情報に対する誤り訂正符号及び誤り検出符号を算出し、修正透かし情報b12を生成する。誤り検出符号と誤り訂正符号は、埋め込んだ電子透かし情報が圧縮や結託攻撃等を受けて発生する符号の誤りを検出、訂正するのに使用する。誤り検出符号には、CRCCyclicRedundancyChecking符号など、また誤り訂正符号にはリードソロモン符号やLDPCLowDensityParityCheck符号などを使用可能とする。なお、基準符号語は、誤り検出符号及び/又は誤り訂正符号を含まなくてもよい。さらに、符号語生成部101は、修正透かし情報b12の先頭に位置検出符号b13及びシフト量検出符号b14を付加することで基準符号語を生成する。位置検出符号b13は、電子透かし情報が埋め込まれたコンテンツにおいて、後述する修正符号語の位置を示すための符号である。シフト量検出符号b14は、修正符号語におけるシフト量を、電子透かし検出装置が検出するために用いられる符号である。位置検出符号b13及びシフト量検出符号b14は、電子透かし検出装置が正確に位置検出符号及びシフト量検出符号を検出することができるように、互いに直交する所定量のビット列として設定されることが望ましい。例えば、位置検出符号b13は、1111111100000000、シフト量検出符号b14は0000111100001111の16ビットの符号として設定する。なお、位置検出符号b13及びシフト量検出符号b14は、16ビット以外にも、互いに直交する8ビットや32ビットなどでもよい。上記の例の位置検出符号b13及びシフト量検出符号b14は、ビット0を-1とみなして16次元ベクトルの内積を取ると0になるため、直交する例である。基準符号語のうち、修正透かし情報b12とシフト量検出符号b14は、後述のシフト部103で巡回シフトの対象となる。なお、符号語生成部101は、符号語を生成する前に、電子透かし情報の暗号化、電子透かし情報に含まれるビット列を所定のブロック単位で入れ替えるスクランブル処理の実行、又はスペクトル拡散などの前処理を行ってもよい。この場合、符号語生成部101は、前処理が行われた電子透かし情報を基準符号語に含める。また、符号語生成部101は、電子透かし情報が所定のビット長よりも長いビット列で表される場合、そのビット列をその所定のビット長単位で分割し、分割されたビット列ごとに基準符号語を生成してもよい。符号語生成部101は、生成した基準符号語をシフト部103に出力する。《巡回シフト系列の生成》図4は、巡回シフト系列の生成を説明するための図である。図4に示す例では、電子透かし情報のビット列b11が表す数字wから得られるシフト系列は、wの関数として表現できる。巡回シフト系列Swの各要素Siwが、巡回シフトのシフト量を表す。シフト部103は、このシフト量を用いて巡回シフトの対象領域を巡回シフトする。以後、シフト量Siwを簡便化のためSiと表記する。巡回シフト系列Swの生成方法の一例として、擬似乱数を用いる方法が考えられる。使用する擬似乱数は、線形合同法やメルセンヌツイスタ、AES暗号を用いた乱数生成法等、様々な方式が適用可能である。電子透かし情報wの全ての場合の数をnw、擬似乱数のt番目の値をR[t]とする。図4に示す乱数系列R[t]t012wは、擬似乱数により生成された乱数の系列である。この乱数系列に対して、電子透かし情報wを開始位置とすると、シフト量Siは、透かし情報wを乱数の種として、次の式2で表される。ここでは簡便化のため、電子透かし情報wは、0からnw-1までの値を取り得るものとする。また、乱数系列R[t]は、巡回シフトの対象となる符号長よりも小さな値を取るものとする。シフト系列生成部102は、生成した巡回シフト系列Siをシフト部103に出力する。《巡回シフト》図5は、巡回シフトを説明するための図である。図5に示す例では、巡回シフトは、基準符号語の先頭の位置検出符号b13を除く符号領域に適用する。巡回シフトのシフト量Siは、シフト系列生成部102から得られた巡回シフト系列より設定する。シフト量Siは、巡回シフト系列のi番目の値である。図5に示すように、シフト部103は、巡回シフトにより巡回シフト対象領域の左端のビットabcを、Siだけ右にシフトし、右端のビットXYZのように右シフト後にシフト対象領域の外側にはみ出るものは、シフト対象領域の左側に移動して配置する。なお、一つのコンテンツに対して生成される修正符号語の数は、そのコンテンツのデータ量が多いほど多くなるように設定されてもよい。例えば、生成される修正符号語の数は、コンテンツのデータ量を、一つの修正符号語を埋め込むために必要なデータ量で除した値とすることができる。ただし、その値が所定の上限値を超える場合、シフト部103は、生成される修正符号語の数をその上限値としてもよい。この上限値は、例えば10とする。シフト部103は、生成した1又は複数の修正符号語を埋め込み部104に出力する。《埋め込み処理》図6は、コンテンツへの修正符号語の埋め込みを説明するための図である。図6に示す例では、シフト部103は、埋め込み対象のコンテンツのサイズに応じて、シフト量を用いて修正符号語を複数生成する。基準符号語に対する巡回シフト量は、図6に示すように、シフト系列生成部102で生成された巡回シフト系列からS0,S1,S2,...の順に設定される。埋め込み部104は、生成された複数の修正符号語を、コンテンツに対して所定の埋め込み方法で埋め込んでいく。これにより、結託攻撃への耐性があり、実用性が向上した修正符号語を、埋め込み対象コンテンツに埋め込むことができる。<動作>次に、電子透かし埋め込み装置の動作について説明する。図7は、実施例1における電子透かし埋め込み処理の一例を示すフローチャートである。図7に示すステップS101で、符号語生成部101は、電子透かし情報から基準符号語を生成する。基準符号語は、例えば、位置検出符号、シフト量検出符号、修正透かし情報を含む。ステップS102で、シフト系列生成部102は、電子透かし情報から巡回シフト系列S0,S1,S2,...を生成する。シフト系列生成部102は、例えば、乱数の系列に対して、電子透かし情報のビット列が示す数字を開始位置とし、この開始位置からの乱数系列を巡回シフト系列とする。ステップS103で、シフト部103は、透かし埋め込みの繰り返し回数を表すインデックスiを0に設定する。ステップS104で、シフト部103は、埋め込み対象のコンテンツに透かしが挿入されていない領域があるかどうかを判定する。未挿入の領域があればステップS104-YESステップS105に進み、未挿入の領域がなければステップS104-NO処理を終了する。なお、未挿入の領域は、いまだに修正符号語が埋め込まれておらず、かつ、修正符号語を埋め込むことが可能な領域である。例えば、コンテンツが音声データであれば、修正符号語が埋め込まれておらず、かつ、修正符号語のデータ量を重畳可能な非可聴域が、未挿入の領域である。また、コンテンツが動画像データであれば、例えば、修正符号語が埋め込まれておらず、かつ、修正符号語に含まれるビットの総数に対応する複数の画像が、未挿入の領域である。ステップS105で、シフト部103は、基準符号語厳密には、基準符号語から位置検出符号を除いた符号をSiだけ巡回シフトして修正符号語を生成する。ステップS106で、埋め込み部104は、シフト部103で生成された修正符号語を、透かし未挿入の領域に挿入する。ステップS107で、シフト部103は、ステップS106の処理後、iに1を加算し、S104の判定処理に戻る。以上、実施例1によれば、結託攻撃に対する耐性を持ち、実用性を向上させることができる電子透かし情報を含む符号語をコンテンツに埋め込むことができる。[実施例2]次に、実施例2における情報処理装置について説明する。実施例2における情報処理装置は、電子透かし検出装置として機能し、実施例1における電子透かし埋め込み装置で埋め込まれた電子透かし情報を検出する装置である。<構成>実施例2における情報処理装置は、実施例1における情報処理装置1と同様であるため、その説明を省略する。なお、実施例2における情報処理装置の構成を説明する際、図1に示す符号と同じ符号を用いて説明する。<電子透かし情報の検出機能>次に、電子透かし情報を検出する機能を有する制御部10について詳しく説明する。図8は、制御部10における電子透かし検出機能の一例を示すブロック図である。図8に示す制御部10は、符号語検出部201、シフト系列検出部202、候補生成部203、透かし情報検出部204及び透かし情報照合部205を有する。符号語検出部201は、コンテンツに埋め込まれた複数の修正符号語を検出する。例えば、符号語検出部201は、コンテンツに埋め込まれた複数の修正符号語の各ビットを、実施例1における電子透かし埋め込み方法に応じた検出方法を用いて検出する。例えば、コンテンツが音声データであり、その音声データの非可聴域に修正符号語に含まれる各ビットの値に応じた信号が付加されているとする。この場合、符号語検出部201は、その信号に対応するテンプレートと非可聴域の信号とのテンプレートマッチングにより非可聴域内でテンプレートと一致する信号を検出する。符号語検出部201は、一致したテンプレートに対応するビット値を修正符号語に含まれるビットとして検出する。また、コンテンツが動画像データであり、各画像の所定の画素が修正符号語に含まれるビット値に応じた値を持っている場合、符号語検出部201は、その所定の画素の値に応じたビット値を検出する。符号語検出部201は、検出した符号語を第一検出符号としてシフト系列検出部202に出力する。シフト系列検出部202は、図9を用いて説明する。図9は、シフト系列検出部202の構成の一例を示すブロック図である。図9に示すシフト系列検出部202は、シフト量算出部301、逆シフト部302、符号更新部303及び第二検出符号生成部304を有する。シフト量算出部301は、符号語検出部201から取得した第一検出符号に基づき、電子透かし埋め込み時に基準符号語を巡回シフトしたシフト量の系列シフト系列とも呼ぶを算出する。シフト量算出部301は、例えば、第一検出符号内の任意の一の符号を基準とし、他の符号との間で相互相関値を用いて、シフト量を算出する。なお、シフト量算出部301は、二回目以降のシフト量算出において基準とする一の符号を、符号更新部303により更新された符号とする。逆シフト部302は、シフト量算出部301で算出されたシフト量を用いて、相互相関値を算出した他の符号を逆シフトする。逆シフトした他の符号を、符号更新部303に出力する。符号更新部303は、逆シフトされた他の符号と、基準となる一の符号とを加算し、一の符号を更新して新たな符号を生成する。シフト量算出部301、逆シフト部302、符号更新部303は、この処理を、一の符号以外の他の符号全てに対して行う。他の符号がなくなった場合、シフト量算出部301は、求めた各シフト量を並べてシフト系列を生成し、生成したシフト系列を第二検出符号生成部304に出力する。また、符号更新部303は、最終的に更新された符号を第二検出符号生成部304に出力する。第二検出符号生成部304は、符号更新部303から取得した符号に基づき、透かし検出用の符号である第二検出符号を生成する。第二検出符号生成部304は、符号からシフト量検出符号の位置を特定し、このシフト量検出符号が先頭にくるように逆シフトする。第二検出符号生成部304は、逆シフトした符号からシフト量検出符号を除いた符号を第二検出符号として生成する。第二検出符号は、修正透かし情報に対応する符号である。第二検出符号生成部304は、生成した第二検出符号を透かし情報検出部204及び透かし情報照合部205に出力する。また、第二検出符号生成部304は、シフト量算出部301から取得したシフト系列を、逆シフトした量分だけ逆シフトし、シフト系列を更新する。第二検出符号生成部304は、更新したシフト系列を候補生成部203に出力する。図8に戻り、候補生成部203は、シフト系列検出部202で得られたシフト系列から、検出対象の電子透かし情報の候補を1又は複数生成する。候補生成部203は、生成した1又は複数の候補を透かし情報照合部205に出力する。透かし情報検出部204では、シフト系列検出部202で生成された第二検出符号から電子透かし情報として埋め込んだ透かし情報を検出し、出力する。透かし情報検出部204で透かしを検出できなかった場合は、透かし情報照合部205で最適な電子透かし情報を求めさせる。透かし情報照合部205は、候補生成部203で生成された電子透かし情報の各候補と、第二検出符号との類似度を求め、電子透かし情報の候補から最適なものを電子透かし情報として出力する。<各部の詳細処理>次に、電子透かし検出処理の各処理について詳しく説明する。《第一検出符号の検出処理》電子透かし情報が埋め込まれたコンテンツから、透かしに対応する第一検出符号が検出される。第一検出符号を検出する処理は、実施例1の埋め込み部104での埋め込み方法に対応した検出方法である。この検出方法は、埋め込み部104の埋め込み方法に対応するため、特定の処理に限定されるものではない。第一検出符号は、透かし埋め込み時に生成した修正符号語が異なるシフト量で繰り返し並べられた符号に対応する。透かしが埋め込まれているコンテンツは、データ圧縮やフィルタ処理、ビデオ撮影、結託攻撃などを経て劣化している可能性がある。よって、劣化したコンテンツから検出される第一検出符号は、埋め込み時に生成された符号とは必ずしも一致せず、誤りを含む場合もある。《巡回シフト系列と第二検出符号の検出処理》シフト系列検出部202は、第一検出符号から、透かし埋め込み時に繰り返し生成された修正符号語の各々のシフト量を求め、第一検出符号から、透かし検出用の第二検出符号を生成する。求められた各々のシフト量を並べたシフト系列は、巡回シフト系列に相当する。図10は、コンテンツからの符号検出を説明するための図である。図10に示す例では、符号語検出部201が、コンテンツから第一検出符号を検出する。次に、シフト系列検出部202は、第一検出符号から、巡回シフト系列と第二検出符号を検出するための符号を検出する。この符号をC[i]と表記する。なお、第二検出符号を検出するための符号は、後述する符号C[i]、C[i]も含む。符号C[i]は、シフト量算出部301により、位置検出符号を検出することで求められる。ここで、位置検出符号は、各々の修正符号語の先頭位置を表す。よって、シフト量算出部301は、各位置検出符号に続く符号が修正符号語の巡回シフトされた箇所であることがわかる。以下、各C[i]を用いて巡回シフト系列と第二検出符号とを生成する処理を説明する。各C[i]は、基準符号語を異なるシフト量で巡回シフトしたものである。よって、シフト量算出部301は、C[i]のうちの二つの符号の相互相関値を求めると、両者の巡回シフト量の差に相当する部分の相互相関値が最大となる。したがって、シフト量算出部301は、C[0]とそれ以外の符号C[i]との相互相関値が最大となる巡回シフト量を求めることで、C[0]を基準とした相対的なシフト系列S[0],S[1],S[2]を求めることができる。ここで、S[0]は、符号C[0]とC[0]の相互相関値、つまりC[0]の自己相関値が最大の巡回シフト値を表しており、必ず0となる。次に、相互相関値の算出方法を説明する。Nを修正符号語の数、MをC[i]の符号長全てのiで同じ、c[i][k]をC[i]のk番目0≦k≦M-1のビット情報とし、ビット0をc[i][k]=-1、ビット1をc[i][k]=1に対応させる。また、C[i]は、逆シフト部302によりC[i]をS[i]で逆巡回シフトした符号系列とし、c[i][k]は、C[i]のk番目のビット情報である。また、C[i]は、符号更新部303により、相互相関値が最大の位置でC[0]からC[i]までを加算した符号系列であり、c[i][k]は、C[i]のk番目のビット情報とする。この時、C[i]をjだけ巡回シフトした場合のC[i-1]とC[i]の相互相関値をr[i][j]として、次式の繰り返し計算を行う。<1>初期化<2>式5~8はi=1~N-1の範囲で繰り返すここで、式5,7中のは剰余演算子を表し、ABはAをBで割った余りを意味する。また、式6のargmaxはjを0からM-1まで変化させた場合に、r[i][j]が最大となるインデックスをS[i]に返す関数である。さらに、式3と式8の計算はC[i],C[i],C[i]の各要素で行われるものとする。これらの繰り返し計算により、C[0]を基準とした相対的な巡回シフト系列S[i]、および各C[i]を相互相関値が最大の位置に合わせて累積した符号系列C[N-1]を得る。図11は、シフト系列の検出を説明するための図である。図11に示す例で、C[i]、C[i]及びC[i]の右隣にある横長の長方形は、各符号のビット列を表す。ビット列は、符号系列とも呼ばれる。図11に示す例では、まず、シフト量算出部301は、相互相関値として、式6を用いてC[0]とC[1]の巡回シフト量の差に相当するS[1]を求める。図11に示すように、シフト量と相互相関値とのグラフを見ると、シフト量S[1]のところに相互相関値のピークが現れる。逆シフト部302は、式7を用いてC[1]をS[1]で逆巡回シフトし、C[1]を生成する。次に、符号更新部303は、式8を用いてC[1]=C[0]C[1]によりC[1]を求める。図11に示すように、シフト系列検出部202は、式5~8の処理を繰り返すことで、相互相関値のピークの位置に合わせてC[i]を累積した符号系列C[N-1]を生成することができる。このC[N-1]は、第二検出符号を検出するための符号である。なお、C[N-1]の各要素c[N-1][k]は、巡回シフトを行う前の基準符号語の同位置のビット情報が加算されたものとなっている。図12は、三人の結託者で結託攻撃を受けたコンテンツにおけるシフト系列の検出を説明するための図である。図12に示すように、まず、シフト量算出部301は、相互相関値として、式6を用いてC[0]とC[1]の巡回シフト量の差に相当するS[1]を求める。このとき、図12に示すように、C[1]において、3人の結託者の巡回シフトの量はそれぞれ異なるため、C[0]とC[1]で相互相関値を計算すると、各結託者に対応する3つのピークが現れる。図12に示す例では、結託者3に対応する巡回シフト量の相互相関値が最大となり、結託者3の巡回シフト位置に合わせてC[1]が生成される。この時、C[1]は、C[1]の逆巡回シフトにより結託者3に対応する符号位置で揃えられてC[0]と加算された符号系列となっている。よって、結託者3の符号系列が強調される。一方で、結託者1,2に対応する符号系列は全くランダムな位置関係で加算されているため、ランダムノイズ化されて相互相関値の大きさが弱まる。したがって、C[1]とC[2]の相互相関値をさらに計算すると、結託者3の巡回シフト量に対応する相互相関値のピークがより顕著に現れる。図12に示す例で、シフト系列検出部202により、式5~8の処理を繰り返されることで、加算により得られる符号系列C[N-1]は、結託者3の符号系列がより強調され、結託者1,2の符号系列がよりランダムノイズ化され弱まる。一つの符号系列のみでは結託攻撃により各々の透かし情報は破壊されているため、透かし情報を検出することは極めて困難である。しかしながら、上記の方法で相互相関値を用いて複数の符号系列を加算すると、結託者のうちの特定の一人の透かし情報が強調される。よって、破壊された透かし情報を復元し、結託攻撃を受けた符号からも透かしを検出できる可能性が高まる。これにより、シフト系列検出部202は、式6によりシフト系列S[i]を求めることができ、式8により第二検出符号を検出するための符号C[N-1]を求めることができる。次に、第二検出符号を生成する処理について説明する。図13は、第二検出符号の生成を説明するための図である。第二検出符号生成部304は、まず、符号系列C[N-1]から基準符号語のシフト量を表すシフト量検出符号を検出し、シフト量検出符号が先頭に来るようにC[N-1]を左に逆巡回シフトする。図13に示す例では、C[N-1]におけるシフト量検出符号の先頭位置からのずれをSとする。第二検出符号生成部304は、C[N-1]を逆巡回シフトして得られる符号系列から、シフト量検出符号を除いたものを第二検出符号とする。以後、図13にも示すように、第二検出符号を示す記号をC^とする。第二検出符号C^の生成手順を数式で示す。Lをシフト量検出符号の符号長、c^[i]を第二検出符号のi番目の要素とすると、c^[i]を次式9~10により求めることができる。また、第二検出符号を生成する際の逆巡回シフトに合わせて、各S[i]も次式によりSだけ左に逆巡回シフトして値を更新する。以上の手順により、第二検出符号生成部304は、第二検出符号とシフト系列S[i]とを求めることができる。《透かし情報候補の生成》次に、透かし情報候補の生成について説明する。図14は、透かし情報候補の生成を説明するための図である。候補生成部203は、シフト系列検出部202で得られたシフト系列S[i]に基づいて、検出対象の電子透かし情報の候補を生成する。図14に示す例では、まず、候補生成部203は、実施例1のシフト系列生成部102と同様の乱数系列を用意する。次に、候補生成部203は、乱数系列の中でシフト系列と一致する箇所を探索する。なお、候補生成部203は、シフト系列と、所定箇所の乱数系列との類似度が所定値以上であれば、これらの系列は一致すると判断してもよい。シフト系列と一致する部分が見つかった場合、その位置に対応する透かし情報を透かし候補として生成する。図14に示す例では、透かし候補をw[0]~w[NW-1]と表記する。なお、図14に示す例では、透かし候補がNW個生成された場合を示す。候補生成部203は、透かし候補w[i]を、後述の透かし情報照合部205で第二検出符号C^と照合可能にするため、実施例1の符号語生成部101と同様の手順で修正透かし符号W[i]に変換する。候補生成部203は、修正透かし候補W[i]を透かし情報照合部205に出力する。《透かし情報の検出》透かし情報検出部204は、シフト系列検出部202で検出された第二検出符号に基づき、電子透かし情報を検出する。第二検出符号は、透かし埋め込み処理の符号語生成部101で生成した修正透かし情報b12に対応し、元の電子透かし情報を誤り訂正および誤り検出可能な形式に変換したものである。そこで、透かし情報検出部204は、第二検出符号に誤り訂正と誤り検出を適用して逆変換し、誤り検出処理において誤りがないと判定されたら逆変換した符号系列を透かし情報として検出し、透かし検出処理を終了する。一方、誤りが検出された場合は、透かし情報検出部204は、誤りが検出された旨を透かし情報照合部205に通知する。《透かし情報の照合》透かし情報照合部205は、候補生成部203で生成された電子透かし情報の各候補W[i]と第二検出符号C^との類似度を求め、電子透かし情報の候補から最適なものを透かし情報として出力する。透かし情報照合部205は、w[i][j]をW[i]のj番目の要素のビット情報とすると、W[i]とC^の類似度sim[i]は、例えば、次式12の相関値計算により求められる。透かし情報照合部205は、式12を用いて類似度sim[i]を全ての電子透かし情報候補で求める。透かし情報照合部205は、類似度が最大となる電子透かし情報候補を選択し、最大の類似度が閾値より大きい等の一定の条件を満たす場合に、電子透かし情報を検出する。なお、第二検出符号C^は、類似度計算のため0の値を-1にしていたため、検出した電子透かし情報では、-1を0に戻しておく。これにより、第二検出符号に誤りがあり、訂正できない場合にも、シフト系列から電子透かし情報の候補を生成することで、電子透かし情報の検出精度を高めることができる。よって、結託攻撃に耐性をもち、実用性が向上した電子透かし技術を提供することができる。<動作>次に、実施例2における情報処理装置の動作について説明する。図15は、実施例2における電子透かし検出処理の一例を示すフローチャートである。図15に示すステップS201で、符号語検出部201は、透かしが埋め込まれたコンテンツから透かしに対応する第一検出符号を検出する。ステップS202で、シフト系列検出部202は、検出された第一検出符号から透かし検出用の第二検出符号と各修正符号語に対するシフト量を示すシフト系列を生成する。ステップS202の詳細な処理は、図16を用いて後述する。ステップS203で、候補生成部203は、シフト系列検出部202で生成されたシフト系列を用いて電子透かし情報の候補を生成する。ステップS204で、透かし情報検出部204は、シフト系列検出部202で生成された第二検出符号に対し、誤り訂正と誤り検出を適用して逆変換し、電子透かし情報の検出を試みる。ステップS205で、透かし情報検出部204は、電子透かし情報を検出できたか否かを判定する。電子透かし情報が検出できればステップS205-YESステップS208に進み、電子透かし情報が検出できなければステップS205-NOステップS206に進む。ステップS206で、透かし情報照合部205は、第二検出符号と電子透かし情報の各候補との類似度を求め、電子透かし情報の候補から最適なものを電子透かし情報として検出する。ステップS207で、透かし情報照合部205は、電子透かし情報を検出できたか否かの判定を行う。電子透かし情報が検出できればステップS207-YESステップS208に進み、電子透かし情報が検出できなければステップS207-NOステップS209に進む。ステップS208で、透かし情報検出部204、又は透かし情報照合部205は、検出した電子透かし情報を出力する。ステップS209で、透かし情報照合部205は、電子透かし情報の検出に失敗したとみなす。なお、S206~S209の詳細な処理は、図17を用いて後述する。これにより、実施例1の電子透かし埋め込み処理で埋め込まれた電子透かし情報を、適切に検出することができる。図16は、シフト系列検出部202の処理の一例を示すフローチャートである。なお、図16に示すフローチャート内で説明なしで使われている変数は、上記で既出の変数と同じものとする。ステップS301で、シフト量算出部301は、第一検出符号から位置検出符号を検出して各修正符号語の先頭位置を特定し、C[i]を生成する。ステップS302で、シフト量算出部301は、C[0]の相互相関値が最大の巡回シフト値S[0]は必ず0なので、予めS[0]=0に設定し、C[0]をC[0]とする。ステップS303で、シフト量算出部301は、C[i]に対応するループ変数iを1に設定する。ステップS304で、シフト量算出部301は、iがNより小さいか否かの判定を行う。iがNより小さければステップS304-YESS305に進み、iがN以上であればステップS304-NOS316に進む。ステップS305で、シフト量算出部301は、シフト量に対応するループ変数jを0とする。ステップS306で、シフト量算出部301は、相互相関値の現時点の最大値を表す変数max_tmpを、相互相関値が取り得る値よりも小さい値SMALLに予め設定する。ステップS307で、シフト量算出部301は、jがC[i]の符号長Mより小さいか否か判定を行う。jがMよりも小さければステップS307-YESS308に進み、jがM以上であればステップS307-NOS313に進む。ステップS308で、シフト量算出部301は、C[i]をjだけ巡回シフトした場合のC[i-1]とC[i]の相互相関値r[i][j]を式5により算出する。ステップS309で、シフト量算出部301は、算出したr[i][j]がmax_tmpより大きいか否かを判定する。r[i][j]がmax_tmpより大きければステップS309-YESS310に進み、r[i][j]がmax_tmp以下であればステップS309-NOS312に進む。ステップS310で、シフト量算出部301は、S[i]をjとする。ステップS311で、シフト量算出部301は、max_tmpにr[i][j]を代入する。ステップS312で、シフト量算出部301は、jに1を足して、S307の処理に戻る。ステップS313で、逆シフト部302は、式7によりC[i]をS[i]だけ逆巡回シフトした符号系列をC[i]に代入する。ステップS314で、符号更新部303は、C[i]を相互相関値が最大となる位置に合わせて累積した符号系列C[i]を式8により更新する。ステップS315で、符号更新部303は、iに1を足して、S304の処理に戻る。ステップS316で、第二検出符号生成部304は、C[N-1]からシフト量検出符号を検出する。ステップS317で、第二検出符号生成部304は、C[N-1]をシフト量Sだけ逆巡回シフトして、シフト量検出符号の後ろに位置する第二検出符号を生成する。ステップS318で、第二検出符号生成部304は、各S[i]をSだけ逆巡回シフトして、シフト量検出符号を基準としたシフト系列S[i]を生成する。これにより、第二検出符号と、シフト系列とを生成し、以降の電子透かし検出処理に用いることができる。図17は、透かし情報照合部205の処理の一例を示すフローチャートである。図17に示すステップS401で、透かし情報照合部205は、類似度計算のインデックスiを0に設定する。ステップS402で、透かし情報照合部205は、類似度の最大値max_tmpを0に設定する。ステップS403で、透かし情報照合部205は、電子透かし情報候補W[i]の候補数をNWとし、iがNWより小さいか否かを判定する。iがNWより小さければステップS403-YESステップS404に進み、iがNW以上であればステップS403-NOステップS409に進む。ステップS404で、透かし情報照合部205は、W[i]とC^の類似度sim[i]を式12により計算する。ステップS405で、透かし情報照合部205は、sim[i]がmax_tmpよりも大きいか否かを判定する。sim[i]がmax_tmpよりも大きればS405-YESステップS406に進み、sim[i]がmax_tmp以下であればS405-NOステップS408に進むステップS406で、透かし情報照合部205は、sim[i]が最大となるインデックスとi_maxとして、i_maxにiを代入する。ステップS407で、透かし情報照合部205は、max_tmpにsim[i]を代入する。ステップS408で、透かし情報照合部205は、iの値に1を足して、ステップS403に戻る。ステップS409で、透かし情報照合部205は、電子透かし情報を検出するかどうかを判定する閾値をsim_threとして、最大の類似度sim[i_max]がsim_thre以上か否かを判定する。この処理は、図15に示すステップS207に対応する。sim[i_max]がsim_thre以上であればステップS409-YESステップS410に進み、sim[i_max]がsim_thre未満であればステップS409-NOステップS411に進む。ステップS410で、透かし情報照合部205は、W[i_max]を電子透かし情報として出力する。この処理は、図15に示すステップS208に対応する。ステップS411で、透かし情報照合部205は、透かし検出失敗とみなす。この処理は、図15に示すステップS209に対応する。なお、透かし情報を検出する処理で、閾値sim_threを定めるのは、類似度計算による透かし情報の誤検出を防ぐためである。例えば、シフト系列検出部202でシフト系列S[i]を正しく求められなかった場合、第二検出符号C^も全く関係ない系列を生成してしまい、透かし情報照合部205から正しい電子透かし情報を求めるのは不可能である。このような場合、どの電子透かし情報候補の類似度も値が小さくなるが、類似度が最大の透かし情報候補は求められてしまう。よって、類似度の最大値のみで電子透かし情報を選択すると誤検出してしまう。そこで、閾値sim_threを設定し、誤検出を防ぐ。誤検出を防ぐためのsim_threの値は、例えば0.75から0.80の間であることが望ましい。以上、実施例2によれば、実施例1における電子透かし埋め込み処理で埋め込まれた電子透かし情報を検出することができる。[変形例]なお、前述した各実施例で説明した電子透かし埋め込み処理及び電子透かし検出処理を実現するためのプログラムを記録媒体に記録することで、各実施例での電子透かし埋め込み処理及び電子透かし検出処理をコンピュータに実施させることができる。例えば、このプログラムを記録媒体に記録し、このプログラムが記録された記録媒体をコンピュータや携帯装置に読み取らせて、前述した電子透かし埋め込み処理及び電子透かし検出処理を実現させることも可能である。なお、記録媒体は、CD-ROM、フレキシブルディスク、光磁気ディスク等の様に情報を光学的,電気的或いは磁気的に記録する記録媒体、ROM、フラッシュメモリ等の様に情報を電気的に記録する半導体メモリ等、様々なタイプの記録媒体を用いることができる。情報処理装置で実行されるプログラムは、各実施例で説明した各部を含むモジュール構成となっている。実際のハードウェアとしては、制御部10が補助記憶部30からプログラムを読み出して実行することにより上記各部のうち1又は複数の各部が主記憶部20上にロードされ、1又は複数の各部が主記憶部20上に生成されるようになっている。以上、実施例について詳述したが、特定の実施例に限定されるものではなく、特許請求の範囲に記載された範囲内において、種々の変形及び変更が可能である。また、前述した各実施例の構成要素を全部又は複数を組み合わせることも可能である。なお、以上の各実施例に関し、さらに以下の付記を開示する。付記1電子透かし情報のビット列を含む第一符号語を生成する符号語生成部と、前記電子透かし情報に基づいて巡回シフト系列を生成するシフト系列生成部と、生成された前記巡回シフト系列に基づいて前記第一符号語を巡回シフトして第二符号語を生成するシフト部と、生成された前記第二符号語をコンテンツに埋め込む埋め込み部と、を備える電子透かし埋め込み装置。付記2前記シフト系列生成部は、複数の乱数の系列に対して、前記電子透かし情報のビット列が示す開始位置を決定し、前記開始位置からの乱数の系列を前記巡回シフト系列とする付記1記載の電子透かし埋め込み装置。付記3前記巡回シフト部は、前記巡回シフト系列の乱数をシフト量にして前記第一符号語を巡回シフトして第二符号語を生成する処理を、乱数の系列順に繰り返し、前記埋め込み部は、前記コンテンツの最後に到達するまで、前記乱数の系列順に生成された第二符号語を、前記コンテンツに順番に埋め込む付記2記載の電子透かし埋め込み装置。付記4前記第一符号語は、前記電子透かし情報に、前記第一符号語の開始位置を表す位置検出符号及び前記巡回シフト部のシフト量の特定に用いるシフト量検出符号を付加した符号である付記1乃至3いずれか一項に記載の電子透かし埋め込み装置。付記5電子透かし情報のビット列を含む第一符号語を生成し、前記電子透かし情報に基づいて巡回シフト系列を生成し、生成された前記巡回シフト系列に基づいて前記第一符号語を巡回シフトして第二符号語を生成し、生成された前記第二符号語をコンテンツに埋め込む処理をコンピュータが実行する電子透かし埋め込み方法。付記6透かし検出対象のコンテンツから、電子透かし情報を含む第一符号語が、前記電子透かし情報に基づいて生成された巡回シフト系列を用いて巡回シフトされた複数の第二符号語を含む第一検出符号を検出する符号語検出部と、一の第二符号語に対し、他の第二符号語を巡回シフトしながら相互相関値を求めることでシフト量を検出し、前記シフト量で逆シフトした他の第二符号語と前記一の第二符号語とを累積して一の第二符号語を更新する処理を、全ての他の第二符号語に対して行うシフト系列検出部と、検出された前記シフト量を並べたシフト系列から、前記電子透かし情報の各候補を生成する候補生成部と、前記電子透かし情報の各候補と、累積された一の第二符号語との類似度に基づき、前記コンテンツに埋め込まれた電子透かし情報を検出する照合部と、を備える電子透かし検出装置。付記7前記巡回シフト系列が、複数の乱数の系列に対して、前記電子透かし情報のビット列が示す開始位置からの乱数の系列である場合、前記候補生成部は、前記シフト系列と、前記乱数の系列との類似度が所定値以上である位置の数字を表すビット列を前記候補とする付記6記載の電子透かし検出装置。付記8前記シフト系列検出部は、前記一の第二符号語に対し、他の第二符号語を巡回シフトしながら求める相互相関値に基づき、シフト量を算出するシフト量算出部と、算出されたシフト量で、前記他の第二符号語を逆シフトする逆シフト部と、逆シフトされた符号語と、前記一の第二符号語とを累積する符号更新部と、累積された前記一の第二符号語に基づき、前記第一符号語に対応する第二検出符号と、シフト量を並べたシフト系列とを生成する第二検出符号生成部と、を備える付記6又は7記載の電子透かし検出装置。付記9透かし検出対象のコンテンツから、電子透かし情報を含む第一符号語が、前記電子透かし情報に基づいて生成された巡回シフト系列を用いて巡回シフトされた複数の第二符号語を含む第一検出符号を検出し、一の第二符号語に対し、他の第二符号語を巡回シフトしながら相互相関値を求めることでシフト量を検出し、前記シフト量で逆シフトした他の第二符号語と前記一の第二符号語とを累積して一の第二符号語を更新する処理を、全ての他の第二符号語に対して行い、検出された前記シフト量を並べたシフト系列から、前記電子透かし情報の各候補を生成し、前記電子透かし情報の各候補と、累積された一の第二符号語との類似度に基づき、前記コンテンツに埋め込まれた電子透かし情報を検出する処理をコンピュータが実行する電子透かし検出方法。"