(57)【要約】【課題】数論変換による脆弱型電子透かしを用いた改ざん位置検出手法及び改ざん訂正手法を提供する。【解決手段】処理部は、数論変換のための主鍵情報Ｐと、Ｐに基づき位数Ｎ及びＰを法とする位数Ｎの根αを求める（Ｓ１０１）。処理部は、原画像ブロックｏｘｙの各画素値ｏｉｊ入力する（Ｓ１０３）。処理部は、Ｐに基づき各画素値ｏｘｙに埋め込む署名情報ｓｘｙを作成する（Ｓ１０５）。処理部は、ｏｘｙとｓｘｙの差分を取ることで署名情報を埋め込んだ埋め込み画像ブロックｅｘｙを得る（Ｓ１０７）。処理部は、ｅｘｙの数論変換係数Ｅｘｙとｏｘｙの数論変換係数Ｏｘｙを求める（Ｓ１０９、Ｓ１１１）。処理部は、各ブロックに対応する副鍵情報のブロックＫｘｙを生成する（Ｓ１１３）。処理部は、各ステップの処理を原画素ブロックｏｘｙに対して行い、ｅｘｙとＫｘｙを得て、記憶部に記憶し（Ｓ１１５）、ｅｘｙ、Ｐ、Ｎ、Ｋｘｙを送信する（Ｓ１１７）。【選択図】　図４
2004048285.tif 000002
【特許請求の範囲】
【請求項１】
処理部は、数論変換のための主鍵情報Ｐを、入力部からの入力又は記憶部から読み出すことで設定し、Ｐに基づき位数Ｎ及びＰを法とする位数Ｎの根αを求めるステップと、
処理部は、ｗＮ×ｈＮ画素の原画像ｏを表した複数の原画像ブロックｏｘｙ（ｘ＝０、…、ｗ−１、　ｙ＝０、…、ｈ−１）の各画素値ｏｉｊ（ｉ、ｊ＝０、…、Ｎ−１）を記憶部から読み取る又は入力部から入力するステップと、
処理部は、Ｐに基づき各画素値ｏｘｙに埋め込む署名情報ｓｘｙを作成するステップと、
処理部は、ｏｘｙとｓｘｙの差分を取ることで署名情報を埋め込んだ埋め込み画像ブロックｅｘｙを得るステップと、
処理部は、ｅｘｙの数論変換係数Ｅｘｙとｏｘｙの数論変換係数Ｏｘｙを求めるステップと、
処理部は、次式により、各ブロックに対応する副鍵情報のブロックＫｘｙを生成するステップと、
Ｋｉｊ＝ＥｉｊＯ−１ｉｊ（ｍｏｄＰ）
（ここに、Ｏｉｊ、Ｅｉｊ、Ｋｉｊは、Ｏｘｙ、Ｅｘｙ、Ｋｘｙの各要素値をそれぞれ示す。また、Ｏ−１ｉｊはＯｉｊの逆元である。）
処理部は、各前記ステップの処理をｗ×ｈ個の原画素ブロックｏｘｙに対して行い、埋め込み画像ブロックｅｘｙと、副鍵情報ブロックＫｘｙを得て、記憶部に記憶するステップと、
処理部は、ｅｘｙ、Ｐ、Ｎ、Ｋｘｙを送信するステップと、
を含む改ざん位置検出方法。
【請求項２】
処理部は、署名情報を埋め込んだ受信画像を受信画像ブロックｅ’ｘｙ（ｘ＝０、…、ｗ−１、　ｙ＝０、…、ｈ−１）に分割し、この各画素値ｅ’ｉｊ（ｉ、ｊ＝０、…、Ｎ−１）を設定し、その受信画像ブロックｅ’ｘｙを記憶部に記憶するステップと、
処理部は、主鍵情報Ｐ、位数Ｎ、副鍵情報Ｋｘｙ、を記憶部から読み取る又は受信することで設定するステップと、
処理部は、Ｐを法とする位数Ｎの根αを計算するステップと、
処理部は、各受信画像ブロックｅ’ｘｙを、予め取得したＰと位数ＮとＰを法とする位数Ｎの根αに基づき数論変換係数Ｅ’ｘｙに数論変換するステップと、処理部は、次式により、受信画像ブロックｅ’ｘｙに基づく受信原画像ｏ’ｘｙの数論変換係数Ｏ’ｘｙを計算するステップと、
Ｅ’ｉｊＫ−１ｉｊ＝Ｏ’ｉｊ（ｍｏｄＰ）
（ここに、Ｏ’ｉｊ、Ｅ’ｉｊ、Ｋｉｊは、Ｏ’ｘｙ、Ｅ’　ｘｙ、Ｋｘｙの各要素値をそれぞれ示す。）
処理部は、得られたＯ’ｘｙを逆数論変換したｏ’ｘｙを計算するステップと、
処理部は、ｏ’ｘｙとｅ’ｘｙとの差をとることにより、署名情報ｓ’ｘｙを抽出するステップと、
処理部は、各前記ステップの処理をｗ×ｈ個の受信画像ブロックに対して行い、ｓ’ｘｙとｏ’ｘｙを得て、記憶部に記憶するステップと、
を含む改ざん位置検出方法。
【請求項３】
処理部は、数論変換のための主鍵情報Ｐを、入力部からの入力又は記憶部から読み出すことで設定し、Ｐに基づき位数Ｎ及びＰを法とする位数Ｎの根αを求めるステップと、
処理部は、ｗＮ×ｈＮ画素の原画像ｏを表した複数の原画像ブロックｏｘｙ（ｘ＝０、…、ｗ−１、　ｙ＝０、…、ｈ−１）の各画素値ｏｉｊ（ｉ、ｊ＝０、…、Ｎ−１）を記憶部から読み取る又は入力部から入力するステップと、
処理部は、Ｐに基づき各画素値ｏｘｙに埋め込む署名情報ｓｘｙを作成するステップと、
処理部は、ｏｘｙとｓｘｙの差分を取ることで署名情報を埋め込んだ埋め込み画像ブロックｅｘｙを得るステップと、
処理部は、ｅｘｙの数論変換係数Ｅｘｙとｏｘｙの数論変換係数Ｏｘｙを求めるステップと、
処理部は、次式により、各ブロックに対応する副鍵情報のブロックＫｘｙを生成するステップと、
Ｋｉｊ＝ＥｉｊＯ−１ｉｊ（ｍｏｄＰ）
（ここに、Ｏｉｊ、Ｅｉｊ、Ｋｉｊは、Ｏｘｙ、Ｅｘｙ、Ｋｘｙの各要素値をそれぞれ示す。また、Ｏ−１ｉｊはＯｉｊの逆元である。）
処理部は、各前記ステップの処理をｗ×ｈ個の原画素ブロックｏｘｙに対して行い、埋め込み画像ブロックｅｘｙと、副鍵情報ブロックＫｘｙを得て、記憶部に記憶するステップと、
処理部は、ｅｘｙ、Ｐ、Ｎ、Ｋｘｙを送信するステップと、
処理部は、署名情報を埋め込んだ受信画像を受信画像ブロックｅ’ｘｙ（ｘ＝０、…、ｗ−１、　ｙ＝０、…、ｈ−１）に分割し、この各画素値ｅ’ｉｊ（ｉ、ｊ＝０、…、Ｎ−１）を設定し、その受信画像ブロックｅ’ｘｙを記憶部に記憶するステップと、
処理部は、主鍵情報Ｐ、位数Ｎ、副鍵情報Ｋｘｙ、を記憶部から読み取る又は受信することで設定するステップと、
処理部は、Ｐを法とする位数Ｎの根αを計算するステップと、
処理部は、各受信画像ブロックｅ’ｘｙを、予め取得したＰと位数ＮとＰを法とする位数Ｎの根αに基づき数論変換係数Ｅ’ｘｙに数論変換するステップと、処理部は、次式により、受信画像ブロックｅ’ｘｙに基づく受信原画像ｏ’ｘｙの数論変換係数Ｏ’ｘｙを計算するステップと、
Ｅ’ｉｊＫ−１ｉｊ＝Ｏ’ｉｊ（ｍｏｄＰ）
（ここに、Ｏ’ｉｊ、Ｅ’ｉｊ、Ｋｉｊは、Ｏ’ｘｙ、Ｅ’　ｘｙ、Ｋｘｙの各要素値をそれぞれ示す。また、Ｋ−１ｉｊはＫｉｊの逆元である。）
処理部は、得られたＯ’ｘｙを逆数論変換したｏ’ｘｙを計算するステップと、
処理部は、ｏ’ｘｙとｅ’ｘｙとの差をとることにより、署名情報ｓ’ｘｙを抽出するステップと、
処理部は、各前記ステップの処理をｗ×ｈ個の受信画像ブロックに対して行い、ｓ’ｘｙとｏ’ｘｙを得て、記憶部に記憶するステップと、
を含む改ざん位置検出方法。
【請求項４】
処理部は、記憶部から受信画像に基づく受信原画像ブロックｏ’ｘｙの検出対象ブロックを読み込むステップと、
処理部は、ｏ’ｉｊが予め定められた最大値より大でないという第１の条件、又は、Ｐに基づき生成された署名情報ｓｉｊがｓ’ｘｙと一致しないという第２の条件のいずれかを満たす場合、改ざんされていると判断するステップと、
を含むことを特徴とする請求項１乃至３のいずれかに記載の改ざん位置検出方法。
【請求項５】
処理部は、記憶部から受信画像に基づく受信原画像ブロックｏ’ｘｙの検出対象ブロックを読み込むステップと、
処理部は、記憶部から読み出したｏ’ｘｙ、ｓ’ｘｙに基づき、副鍵情報Ｋ’ｘｙを生成し、受信したＫｘｙと一致しないという第３の条件を満たす場合、改ざんされていると判断するステップと、
を含むことを特徴とする請求項１乃至３のいずれかに記載の改ざん位置検出方法。
【請求項６】
処理部は、記憶部から受信画像に基づく受信原画像ブロックｏ’ｘｙの検出対象ブロックを読み込むステップと、
処理部は、検出対象ブロックが改ざんされているかを判断するステップと、
処理部は、　探索パターンのための初期値を周囲のブロックに基づき設定するステップと、
処理部は、改ざんされたと判断された対象ブロックの各画素に、初期値又は初期値から派生する複数値の任意の組合わせを当てはめた探索パターンを作成するステップと、
処理部は、作成された探索パターンに基づき前記判断するステップで改ざんされていないと判断されるまで、前記探索パターンを作成するステップ及び前記判断するステップを繰り返し、該当する探索パターンを求めるステップと、
処理部は、求めた探索パターンを記憶部に記憶するステップと、
を含むことを特徴とする請求項１乃至３のいずれかに記載の改ざん位置検出方法。
【請求項７】
処理部は、ｐｉを素数、ｒｉを正の整数としてＰ＝ｐ１ｒ１ｐ２ｒ２…ｐｉｒｉで表されるとしたＰを設定し、
処理部は、位数ＮをＮ｜ＧＣＤ［（ｐ１−１）、（ｐ２−１）、…、（ｐｉ−１）］を満たす正の整数から選択し又は記憶部から読み取り、
処理部は、ｐｉを法とする位数Ｎの根ｇ１、ｉを計算し、
処理部は、ｐｉｒｉを法とする位数Ｎの根ｇ２、ｉを、ｇ１、ｉより求め、
処理部は、中国剰余定理により、Ｐを法とする位数Ｎの根αを、ｇ２、ｉより求める
ことを特徴とする請求項１乃至３のいずれかに記載の改ざん位置検出方法。
【請求項８】
処理部は、Ｐ、Ｎ及びαを用いて、次式によりｘ（ｎ）とＸ（ｋ）との間の数論変換を実行することを特徴とする請求項１乃至３のいずれかに記載の改ざん位置検出方法。
【数１】
2004048285.tif 000010
（ここに、Ｐ（素数のべき乗となる任意の合成数）、α、（を正の整数、ＮをαＮ＝１（ｍｏｄＰ）となる最小の正の整数）
Ｘ＝［Ｔ］ｘ
ｘ＝［Ｔ］−１Ｘ
（［Ｔ］：変換行列、［Ｔ］−１：逆変換行列）
【請求項９】
処理部は、Ｐ、ｘ、ｙ、ｉ、ｊが、あらかじめ送信者用コンピュータと受信者用コンピュータの間で決定しており、εを埋め込み強度を決定する正の整数とすると、ｓｘｙを、
ｓｉｊ＝Ｐ（ｘ＋ｙ＋ｉ＋ｊ）（ｍｏｄε）
又は、
ｓｉｊ＝Ｐ（ｘ・ｙ・ｉ・ｊ）（ｍｏｄε）
により求めることを特徴とする請求項１乃至３のいずれかに記載の改ざん位置検出方法。
【請求項１０】
処理部は、数論変換のための主鍵情報Ｐを、入力部からの入力又は記憶部から読み出すことで設定し、Ｐに基づき位数Ｎ及びＰを法とする位数Ｎの根αを求めるステップと、
処理部は、ｗＮ×ｈＮ画素の原画像ｏを表した複数の原画像ブロックｏｘｙ（ｘ＝０、…、ｗ−１、　ｙ＝０、…、ｈ−１）の各画素値ｏｉｊ（ｉ、ｊ＝０、…、Ｎ−１）を記憶部から読み取る又は入力部から入力するステップと、
処理部は、Ｐに基づき各画素値ｏｘｙに埋め込む署名情報ｓｘｙを作成するステップと、
処理部は、ｏｘｙとｓｘｙの差分を取ることで署名情報を埋め込んだ埋め込み画像ブロックｅｘｙを得るステップと、
処理部は、ｅｘｙの数論変換係数Ｅｘｙとｏｘｙの数論変換係数Ｏｘｙを求めるステップと、
処理部は、次式により、各ブロックに対応する副鍵情報のブロックＫｘｙを生成するステップと、
Ｋｉｊ＝ＥｉｊＯ−１ｉｊ（ｍｏｄＰ）
（ここに、Ｏｉｊ、Ｅｉｊ、Ｋｉｊは、Ｏｘｙ、Ｅｘｙ、Ｋｘｙの各要素値をそれぞれ示す。また、Ｏ−１ｉｊはＯｉｊの逆元である。）
処理部は、各前記ステップの処理をｗ×ｈ個の原画素ブロックｏｘｙに対して行い、埋め込み画像ブロックｅｘｙと、副鍵情報ブロックＫｘｙを得て、記憶部に記憶するステップと、
処理部は、ｅｘｙ、Ｐ、Ｎ、Ｋｘｙを送信するステップと、
をコンピュータに実行させるための改ざん位置検出プログラム。
【請求項１１】
処理部は、署名情報を埋め込んだ受信画像を受信画像ブロックｅ’ｘｙ（ｘ＝０、…、ｗ−１、　ｙ＝０、…、ｈ−１）に分割し、この各画素値ｅ’ｉｊ（ｉ、ｊ＝０、…、Ｎ−１）を設定し、その受信画像ブロックｅ’ｘｙを記憶部に記憶するステップと、
処理部は、主鍵情報Ｐ、位数Ｎ、副鍵情報Ｋｘｙ、を記憶部から読み取る又は受信することで設定するステップと、
処理部は、Ｐを法とする位数Ｎの根αを計算するステップと、
処理部は、各受信画像ブロックｅ’ｘｙを、予め取得したＰと位数ＮとＰを法とする位数Ｎの根αに基づき数論変換係数Ｅ’ｘｙに数論変換するステップと、処理部は、次式により、受信画像ブロックｅ’ｘｙに基づく受信原画像ｏ’ｘｙの数論変換係数Ｏ’ｘｙを計算するステップと、
Ｅ’ｉｊＫ−１ｉｊ＝Ｏ’ｉｊ（ｍｏｄＰ）
（ここに、Ｏ’ｉｊ、Ｅ’ｉｊ、Ｋｉｊは、Ｏ’ｘｙ、Ｅ’　ｘｙ、Ｋｘｙの各要素値をそれぞれ示す。また、Ｋ−１ｉｊはＫｉｊの逆元である。）
処理部は、得られたＯ’ｘｙを逆数論変換したｏ’ｘｙを計算するステップと、
処理部は、ｏ’ｘｙとｅ’ｘｙとの差をとることにより、署名情報ｓ’ｘｙを抽出するステップと、
処理部は、各前記ステップの処理をｗ×ｈ個の受信画像ブロックに対して行い、ｓ’ｘｙとｏ’ｘｙを得て、記憶部に記憶するステップと、
をコンピュータに実行させるための改ざん位置検出プログラム。
【請求項１２】
処理部は、数論変換のための主鍵情報Ｐを、入力部からの入力又は記憶部から読み出すことで設定し、Ｐに基づき位数Ｎ及びＰを法とする位数Ｎの根αを求めるステップと、
処理部は、ｗＮ×ｈＮ画素の原画像ｏを表した複数の原画像ブロックｏｘｙ（ｘ＝０、…、ｗ−１、　ｙ＝０、…、ｈ−１）の各画素値ｏｉｊ（ｉ、ｊ＝０、…、Ｎ−１）を記憶部から読み取る又は入力部から入力するステップと、
処理部は、Ｐに基づき各画素値ｏｘｙに埋め込む署名情報ｓｘｙを作成するステップと、
処理部は、ｏｘｙとｓｘｙの差分を取ることで署名情報を埋め込んだ埋め込み画像ブロックｅｘｙを得るステップと、
処理部は、ｅｘｙの数論変換係数Ｅｘｙとｏｘｙの数論変換係数Ｏｘｙを求めるステップと、
処理部は、次式により、各ブロックに対応する副鍵情報のブロックＫｘｙを生成するステップと、
Ｋｉｊ＝ＥｉｊＯ−１ｉｊ（ｍｏｄＰ）
（ここに、Ｏｉｊ、Ｅｉｊ、Ｋｉｊは、Ｏｘｙ、Ｅｘｙ、Ｋｘｙの各要素値をそれぞれ示す。また、Ｏ−１ｉｊはＯｉｊの逆元である。）
処理部は、各前記ステップの処理をｗ×ｈ個の原画素ブロックｏｘｙに対して行い、埋め込み画像ブロックｅｘｙと、副鍵情報ブロックＫｘｙを得て、記憶部に記憶するステップと、
処理部は、ｅｘｙ、Ｐ、Ｎ、Ｋｘｙを送信するステップと
をコンピュータに実行させるための改ざん位置検出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１３】
処理部は、署名情報を埋め込んだ受信画像を受信画像ブロックｅ’ｘｙ（ｘ＝０、…、ｗ−１、　ｙ＝０、…、ｈ−１）に分割し、この各画素値ｅ’ｉｊ（ｉ、ｊ＝０、…、Ｎ−１）を設定し、その受信画像ブロックｅ’ｘｙを記憶部に記憶するステップと、
処理部は、主鍵情報Ｐ、位数Ｎ、副鍵情報Ｋｘｙ、を記憶部から読み取る又は受信することで設定するステップと、
処理部は、Ｐを法とする位数Ｎの根αを計算するステップと、
処理部は、各受信画像ブロックｅ’ｘｙを、予め取得したＰと位数ＮとＰを法とする位数Ｎの根αに基づき数論変換係数Ｅ’ｘｙに数論変換するステップと、処理部は、次式により、受信画像ブロックｅ’ｘｙに基づく受信原画像ｏ’ｘｙの数論変換係数Ｏ’ｘｙを計算するステップと、
Ｅ’ｉｊＫ−１ｉｊ＝Ｏ’ｉｊ（ｍｏｄＰ）
（ここに、Ｏ’ｉｊ、Ｅ’ｉｊ、Ｋｉｊは、Ｏ’ｘｙ、Ｅ’　ｘｙ、Ｋｘｙの各要素値をそれぞれ示す。また、Ｋ−１ｉｊはＫｉｊの逆元である。）
処理部は、得られたＯ’ｘｙを逆数論変換したｏ’ｘｙを計算するステップと、
処理部は、ｏ’ｘｙとｅ’ｘｙとの差をとることにより、署名情報ｓ’ｘｙを抽出するステップと、
処理部は、各前記ステップの処理をｗ×ｈ個の受信画像ブロックに対して行い、ｓ’ｘｙとｏ’ｘｙを得て、記憶部に記憶するステップと、
をコンピュータに実行させるための改ざん位置検出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、改ざん位置検出方法、改ざん位置検出プログラム及びそのプログラムを記録した記録媒体に係り、特に、数論変換による脆弱型電子透かしを用いた静止画像の改ざん位置検出技術及び改ざん訂正技術に関する。
【０００２】
【従来の技術】
一般に、証拠写真などの、公文書で用いられる画像には原本性が十分に保証されたものが要求されるが、ディジタル画像は不自然さを排除した改ざんを容易に行えるため、原本性保証や改ざん検出の技術が求められている。従来、これらの目的を実現する方法としてハッシュ関数を用いた電子署名が検討されてきた［１］。（以下［　］内は後述の文献を示す。）ただ、このような電子署名は、現代の多種多様な要件の一つである、改ざんの位置検出をすることを意図していない。
【０００３】
これを可能とする一つの方法として、電子透かしを応用したものが検討されている［２］［３］。対象とするディジタルコンテンツには、特定の攻撃に意図的に壊れやすくした脆弱型の電子透かしを、小さなブロック単位でコンテンツ全体に繰り返し埋めておく。そして改ざん検出の処理段階では、破壊された電子透かしを同定し、改ざんの位置を特定するというものである。
【０００４】
また、従来、電子透かしによる改ざん位置検出の従来手法としては、ディジタルコンテンツから得られたハッシュ値やパリティ値をビットプレーンのＬＳＢ（Ｌｅａｓｔ　Ｓｉｇｎｉｆｉｃａｎｔ　Ｂｉｔ）に埋めるといったものが主であった［４］−［７］。
【０００５】
【発明が解決しようとする課題】
著作権保護技術としての電子透かしは、改ざん位置検出の観点からも注目を集めている。特定な処理に対して脆弱な性質を持たせた電子透かしは、改ざん位置検出に利用できるからである。しかしながら、静止画像の改ざん位置検出においては、原画像を必要とせず、あらゆる改ざんも検出できる手法が理想である。また、アルゴリズム公開を視野に入れると、鍵情報の利用を考慮することが望ましい。さらに、上述のような従来の電子透かしによる改ざん位置提出の手法は、改ざん箇所の訂正までは考慮していない。
【０００６】
本発明は、以上の点に鑑み、数論変換（ＮＴＴ：Ｎｕｍｂｅｒ　Ｔｈｅｏｒｅｔｉｃ　Ｔｒａｎｓｆｏｒｍ）による脆弱型電子透かしを用いた改ざん位置検出手法を提供することを目的とする。さらに、本発明は、数論変換に基づく新たな手法により［８］、改ざんの位置検出だけでなく、数論変換の性質から、改ざん訂正手法を提供することを目的とする。
【０００７】
本発明は、受信者は透かし情報が埋め込まれた画像を受け取った後、認証機関から取得した鍵情報を用いて原本性を確認するという過程により、送信者は、原本そのものを受信者あるいは認証機関に伝送する必要がなく、原本を第三者に見せることなく保護することができる改ざん位置検出・訂正手法を提供することを目的とする。
【０００８】
また、本発明は、インターネット回線を利用した画像を含む公文書の伝送、ディジタルカメラやスキャナ等によって取得された画像の原本性保証、画像に施された各種修正や特殊効果の同定と除去等に利用することができる改ざん位置検出手法を提供することを目的とする。
【０００９】
【課題を解決するための手段】
本発明の第１の解決手段によると、
処理部は、数論変換のための主鍵情報Ｐを、入力部からの入力又は記憶部から読み出すことで設定し、Ｐに基づき位数Ｎ及びＰを法とする位数Ｎの根αを求めるステップと、
処理部は、ｗＮ×ｈＮ画素の原画像ｏを表した複数の原画像ブロックｏｘｙ（ｘ＝０、…、ｗ−１、　ｙ＝０、…、ｈ−１）の各画素値ｏｉｊ（ｉ、ｊ＝０、…、Ｎ−１）を記憶部から読み取る又は入力部から入力するステップと、
処理部は、Ｐに基づき各画素値ｏｘｙに埋め込む署名情報ｓｘｙを作成するステップと、
処理部は、ｏｘｙとｓｘｙの差分を取ることで署名情報を埋め込んだ埋め込み画像ブロックｅｘｙを得るステップと、
処理部は、ｅｘｙの数論変換係数Ｅｘｙとｏｘｙの数論変換係数Ｏｘｙを求めるステップと、
処理部は、次式により、各ブロックに対応する副鍵情報のブロックＫｘｙを生成するステップと、
Ｋｉｊ＝ＥｉｊＯ−１ｉｊ（ｍｏｄＰ）
（ここに、Ｏｉｊ、Ｅｉｊ、Ｋｉｊは、Ｏｘｙ、Ｅｘｙ、Ｋｘｙの各要素値をそれぞれ示す。また、Ｏ−１ｉｊはＯｉｊの逆元である。）
処理部は、各前記ステップの処理をｗ×ｈ個の原画素ブロックｏｘｙに対して行い、埋め込み画像ブロックｅｘｙと、副鍵情報ブロックＫｘｙを得て、記憶部に記憶するステップと、
処理部は、ｅｘｙ、Ｐ、Ｎ、Ｋｘｙを送信するステップと、
を含む改ざん位置検出方法、各ステップをコンピュータに実行させるための改ざん位置検出プログラムを記録したコンピュータ読み取り可能な記録媒体が提供される。
【００１０】
本発明の第２の解決手段によると、
処理部は、署名情報を埋め込んだ受信画像を受信画像ブロックｅ’ｘｙ（ｘ＝０、…、ｗ−１、　ｙ＝０、…、ｈ−１）に分割し、この各画素値ｅ’ｉｊ（ｉ、ｊ＝０、…、Ｎ−１）を設定し、その受信画像ブロックｅ’ｘｙを記憶部に記憶するステップと、
処理部は、主鍵情報Ｐ、位数Ｎ、副鍵情報Ｋｘｙ、を記憶部から読み取る又は受信することで設定するステップと、
処理部は、Ｐを法とする位数Ｎの根αを計算するステップと、
処理部は、各受信画像ブロックｅ’ｘｙを、予め取得したＰと位数ＮとＰを法とする位数Ｎの根αに基づき数論変換係数Ｅ’ｘｙに数論変換するステップと、処理部は、次式により、受信画像ブロックｅ’ｘｙに基づく受信原画像ｏ’ｘｙの数論変換係数Ｏ’ｘｙを計算するステップと、
Ｅ’ｉｊＫ−１ｉｊ＝Ｏ’ｉｊ（ｍｏｄＰ）
（ここに、Ｏ’ｉｊ、Ｅ’ｉｊ、Ｋｉｊは、Ｏ’ｘｙ、Ｅ’　ｘｙ、Ｋｘｙの各要素値をそれぞれ示す。また、Ｋ−１ｉｊはＫｉｊの逆元である。）
処理部は、得られたＯ’ｘｙを逆数論変換したｏ’ｘｙを計算するステップと、
処理部は、ｏ’ｘｙとｅ’ｘｙとの差をとることにより、署名情報ｓ’ｘｙを抽出するステップと、
処理部は、各前記ステップの処理をｗ×ｈ個の受信画像ブロックに対して行い、ｓ’ｘｙとｏ’ｘｙを得て、記憶部に記憶するステップと、
を含む改ざん位置検出方法、各ステップをコンピュータに実行させるための改ざん位置検出プログラムを記録したコンピュータ読み取り可能な記録媒体が提供される。
【００１１】
【発明の実施の形態】
本実施の形態では、数論変換の概要および、数論変換を用いた脆弱型電子透かしによる改ざん位置検出手法及び改ざん訂正手法について述べる。また、本実施の形態についてのシミュレーション実験を通じて有効性について述べる。
【００１２】
１．数論変換
１−１．概要
はじめに、数論変換について説明する［８］−［１３］。パラメータＰ、α、ｕを正の整数、ＮをαＮ＝１（ｍｏｄＰ）となる最小の正の整数とする。ここで、φ（Ｐ）はＥｕｌｅｒ関数で、Ｐより小さく、かつＰに対し互いに素となる整数の数とすると、Ｎ＝φ（Ｐ）となるαを位数Ｎの原始根と呼び、Ｎ＜φ（Ｐ）のαを、単に位数Ｎの根と呼ぶ。また、ｕｕ−１＝１（ｍｏｄＰ）となるｕ−１を、Ｐを法とするＮの逆元と呼ぶ。
ここで、αを用いた次のような変換対を考える。
【００１３】
【数２】
2004048285.tif 000003
【００１４】
上式の計算は、Ｐを法とする剰余数系ですべての演算が可能なため、丸め誤差を一切生じない。よって、電子透かしへの応用を考えたとき、Ｐを秘匿しておけば、数論変換の性質から、第三者は期待する変換結果を得ることができないため、Ｐは変換における鍵情報として利用できる。
【００１５】
数論変換を用いた電子透かしの従来手法には、我々が提案した文献［１４］の手法があるが、Ｐにはフェルマー数を用いたものであった。フェルマー数とは、ｔを正の整数とすると、
Ｐ＝２ｂ＋１、ｂ＝２ｔ　　　　（３）
で表されるため、Ｐの選択には厳しい制限があり、鍵情報として用いるのには必ずしも不適当でない場合があった。そこでＰが素数のべき乗による任意の合成数でも可能である手法を紹介する［１２］。
【００１６】
ｐｉを素数としてＰ＝ｐ１ｒ１ｐ２ｒ２…ｐｉｒｉで表されるとする。まず、位数をＮ｜ＧＣＤ［（ｐ１−１）、（ｐ２−１）、…、（ｐｉ−１）］を満たす正の整数から選択し、ｐｉを法とする位数Ｎの根ｇ１、ｉを計算する。次に、ｐｉｒｉを法とする位数Ｎの根ｇ２、ｉを次のように求める。
【００１７】
【数３】
2004048285.tif 000004
【００１８】
続いて、中国剰余定理により、Ｐを法とする位数Ｎの根αをｇ２、ｉより求める。数論変換は以上より算出したパラメータにより実行する。
【００１９】
一般に、剰余系で演算を行う場合取扱える数の範囲を広げるため、異なる法の剰余系の組を用い、演算結果は法ごとの結果の組となる場合がある。中国剰余定理（Ｃｈｉｎｅｓｅ　ｒｅｍａｉｎｄｅｒ　ｔｈｅｏｒｅｍ）は、この組からある進数で唯一に定まる数を求めるもので次のように表わせる。（青木由直「波動信号処理」、森北出版株式会社、１９８６年４月３日、参照）
【００２０】
［定理］　法ｍｉ（ｉ＝１、２、・・・、ｌ）を互いに素な正整数に選びＭ＝ｍ１ｍ２・・・ｍｌとすると
＜ａ＞ｍｉ＝ｒｉ　（ｉ＝１、２、・・・、ｌ）
（ここに、ｒｉは法ｍｉに関するａの剰余である。）
を満足する正整数ａ（０＜ａ≦Ｍ−１）は次式で唯一に与えられる。
ａ＝Σｄｉｄｉ−１ｒｉ　（ｍｏｄ　Ｍ）
ここで、
Σは、ｉ＝１〜ｌの和
ｄｉ＝Ｍ／ｍｉ　、
ｄｉ−１＝（＜ｄｉ＞ｍｉ）−１　（ｍｏｄ　ｍｉ）
（なお、（＜ｄｉ＞ｍｉ）−１は法ｍｉでの乗法逆元。）
【００２１】
１−２．例
例えば、Ｐ＝６１００９＝１３２×１９２による数論変換を考える。まず、ＧＣＤ［１２、１８］＝６より、ＮをＮ｜６＝［１、２、３、６］から選択する。ここではＮ＝３を採用する。次に１３と１９を法とする位数３の根を計算する。それぞれをｇ１、１、ｇ１、２とすると、ｇ１、１＝３、ｇ１、２＝７である。よって、１３２と１９２を法とする位数３の根をｇ２、１、ｇ２、２とすると、次のようになる。
【００２２】
【数４】
2004048285.tif 000005
【００２３】
続いて、よく知られた中国剰余定理により、６１００９を法とする位数３の根はα＝６５３と求まる。
【００２４】
図１に、素数１３のｙｘ（ｍｏｄ　１３）の説明図を示す。
例えば、１３を法とする位数３の根の見つけ方を考える。ｙが縦、ｘが横である。１が出る周期がＮである時、ｙを１３を法とした位数Ｎ（ここだと３）である。ｙ＝３、９の時、３つおきに“３”が出ているため、３、９が根である。ここでは、例えば、複数の根のうち最小のものを選択することとすると、根＝３となる。なお、数論の全般的なことについては、ｈｔｔｐ：／／ｆｏｘ．ｚｅｒｏ．ａｄ．ｊｐ／￣ｚａｔ２５９６０／ｍａｔｈ／ｎｕｍｂｅｒ／ｉｎｄｅｘ．ｈｔｍ等参照。
【００２５】
ここで、一例として、以上に基づき、Ｎ＝３の系列ｘ＝［１０、２０、３０］Ｔの数論変換を考える。式（１）、（２）は行列表示すると次のようになる。
Ｘ＝［Ｔ］ｘ　　　　（４）
ｘ＝［Ｔ］−１Ｘ　　　（５）
ただし、
Ｘ＝［Ｘ（０）、Ｘ（１）、Ｘ（２）］Ｔ
　ｘ＝［ｘ（０）、ｘ（１）、ｘ（２）］Ｔ
である。変換行列［Ｔ］は、
【００２６】
【数５】
2004048285.tif 000006
【００２７】
となり、逆変換行列［Ｔ］−１は
【００２８】
【数６】
2004048285.tif 000007
【００２９】
となる。ｘを数論変換すると、
【００３０】
【数７】
2004048285.tif 000008
【００３１】
となり、［Ｔ］−１を用いて逆変換すると、
ｘ＝［Ｔ］−１Ｘ＝［１０、２０、３０］Ｔ（ｍｏｄ　６１００９）
が得られる。
【００３２】
ここで、例えば、変換後の系列Ｘ＝［６０、５４４５９、６５２０］ＴがＸ’＝［６１、５４４５９、６５２１］Ｔに改ざんされたとする。逆変換後の出力ｘ’は、
ｘ’＝［Ｔ］−１Ｘ’＝［１１、２３８、４０４８５］Ｔ（ｍｏｄ　６１００９）
となり、ｘとは全く異なる。この結果は、丸め誤差の生じない数論変換の性質から得られるもので、改ざん検出に有効であるといえる。
【００３３】
２．ハードウェア
図２に、システム構成の概略図を示す。このシステムでは、送信者用コンピュータ１０、受信者用コンピュータ２０、認証機関用コンピュータ３０を備える。
送信者コンピュータ１０から受信者用コンピュータ２０へは署名情報が電子透かしで埋め込まれた画像情報ｅが伝達される。なお、署名データＳは送信者用コンピュータ１０から受信者用コンピュータ２０との間で予め決定されている。送信者用コンピュータ１０から認証機関用コンピュータ３０は主鍵情報Ｐ、位数Ｎ及び副鍵情報Ｋが送られる。受信者用コンピュータ２０は認証機関用コンピュータ３０からこれら鍵情報Ｐ及びＫを取得する。
【００３４】
送信者から受信者へのｅ、Ｐ、Ｋの伝送手段は、例えば、次のような手段がある。ここで、ｅは公開してもかまわないため、受信者用コンピュータ２０は送信者用コンピュータ１０からｅ−ｍａｉｌで直接送信しても特に問題ないが、鍵情報Ｐ、Ｋは秘密鍵のため、送信者用コンピュータ１０から認証機関コンピュータ３０に送信する場合にはセキュリティの観点から、ＲＳＡなどの暗号化を施した後に送信するべきである。例えば、ディジタルカメラでの運用を考えた場合、カメラから直接認証機関に送信されることが一案である。この場合はｅ−ｍａｉｌではなく、暗号化ファイルを直接パケット交換や回線交換で送信することもできる。これら鍵情報を認証機関コンピュータ３０から送信者用コンピュータ１０が受信する場合も同様である。
【００３５】
図３は、送信者・受信者用コンピュータのハードウェアの構成図である。
このハードウェアは、中央処理装置（ＣＰＵ）である処理部１、入力部２、出力部３、表示部４、記憶部５、インターフェース６を有する。また、処理部１、入力部２、出力部３、表示部４及び記憶部５は、スター又はバス等の適宜の接続手段で接続されている。記憶部５は、パラメータファイル５１、画像ファイル５２を含む。インターフェース６は、インターネット、移動体通信網等の各種ネットワークと接続され、他のコンピュータと情報の送受を無線、又は有線で行う。
【００３６】
３．改ざん位置検出
３−１．埋め込み処理
図４に、埋め込み処理のフローチャートを示す。また、図５は、Ｎ＝２の場合の、一つのブロックに対する埋め込み処理の概念図である。
【００３７】
埋め込み処理を行う送信者用コンピュータ１０は、まず数論変換のパラメータとなる主鍵情報Ｐを決定し、処理部１は、数論変換のための主鍵情報Ｐを、入力部２からの入力又は記憶部５のパラメータファイル５１から読み出すことで設定し、Ｐに基づき位数Ｎ及びＰを法とする位数Ｎの根α等の各種パラメータを設定する（Ｓ１０１）。例えば、Ｐは、記憶部５のパラメータファイル５１に予め素数のべき乗の積による形式で記憶されていてもよいし、入力部２により素数ｐｉ乗数ｒｉを所望の数に組合せて入力して作成するようにしてもよい。ここでＰは任意の合成数でよいが、１または偶数である場合には数論の性質により、Ｎは１に限定される［１３］。ゆえに、Ｐは３以上の奇数とする。また、画像の画素値の最大値をｏｍａｘとすると、後述の「３−３」で述べる改ざん位置検出処理を考慮して、Ｐ＞＞ｏｍａｘであることが望ましい。
【００３８】
また、処理部１は前述したＮ｜ＧＣＤ［（ｐ１−１）、（ｐ２−１）、…、（ｐｉ−１）］から位数Ｎを求める。Ｐを決定すると、一般に、Ｎの候補が複数出てくる。Ｎがユーザで指定又は処理部１が自動設定すると、αは自動的に計算により決定される（計算については前述の具体的例を参照）。複数のＮの候補が求められた場合、Ｎをユーザが入力部により適宜指定・採用することができる。また、処理部１が予め定めた範囲で選択するようにしてもよい。Ｎはブロックサイズと等価であることから、Ｎは小さければ小さいほど検出の精度は高くなるが、Ｎ＝１では数論変換の意味が無くなってしまうため、２以上を選択する。Ｎが大きいほど、一つのブロックに対する鍵情報Ｋｘｙのビット数が大きくなるためよりセキュアになるものの、検出の精度は低くなる。検出の精度とセキュリティの高さはトレードオフの関係にあるといえる。
【００３９】
さらに、処理部１はＰとＮから前述のようにαを求める。処理部１は得られた数論変換のパラメータＰ、Ｎ、αをパラメータファイルに記憶してもよい。
【００４０】
つぎに、処理部１は、ｗＮ×ｈＮ画素の原画像ｏを表した原画像データを記憶部５の画像ファイル５２から読み取る又は入力部２から入力する。（Ｓ１０３）ｏはｗＮ×ｈＮ画素とする。さらに、ｏをＮ×Ｎ画素の原画像のブロックに分割し、この一つの原画像ブロックをｏｘｙ（ｘ＝０、…、ｗ−１、ｙ＝０、…、ｈ−１）とする。また、ｏｘｙの各画素値をｏｉｊ（ｉ、ｊ＝０、…、Ｎ−１）で表す。次に、処理部１は、Ｐに基づきｏｘｙに埋め込む署名情報をｓｘｙとして作成する（Ｓ１０５）。処理部１は、ｏｘｙとｓｘｙの差分を取ることで署名情報を埋め込んだ埋め込み画像ブロックｅｘｙを得る（Ｓ１０７）。つまり、ｅｘｙの各画素値をｅｉｊ、ｓｘｙの各要素値をｓｉｊとすると、
ｅｉｊ＝ｏｉｊ−ｓｉｊ　　　　　（８）
となる。なお、ここではｓｘｙは、Ｐ、ｘ、ｙ、ｉ、ｊのいずれか又は所定の複数を用いて、適宜の演算により決定することができる。たとえば、εを埋め込み強度を決定する正の整数とすると、
ｓｉｊ＝Ｐ（ｘ＋ｙ＋ｉ＋ｊ）（ｍｏｄε）　　　　（９）
又は、
ｓｉｊ＝Ｐ（ｘ・ｙ・ｉ・ｊ）（ｍｏｄε）
等で決定することができる。この関数はあらかじめ送信者と受信者の間で決定しておく。さらに、処理部１は、「１．数論変換」で述べたように、ｅｘｙの数論変換係数Ｅｘｙとｏｘｙ数論変換係数Ｏｘｙを求める（Ｓ１０９、Ｓ１１１）。
つぎに、処理部１は、ｏｘｙとｅｘｙから、このブロックに対応する副鍵情報のブロックＫｘｙを生成する（Ｓ１１３）。Ｋｘｙはｅｘｙの数論変換係数とｏｘｙの数論変換係数の逆元の積で得られる。つまり、ｏｘｙとｅｘｙの数論変換係数をそれぞれＯｘｙ、Ｅｘｙとし、Ｏｘｙ、Ｅｘｙ、Ｋｘｙの各要素値をそれぞれＯｉｊ、Ｅｉｊ、Ｋｉｊとすると、
Ｋｉｊ＝ＥｉｊＯ−１ｉｊ（ｍｏｄＰ）　　　　（１０）
となる。
【００４１】
処理部１は、以上の処理をｗ×ｈ個の全ブロックに対して行い、各埋め込み画像ブロックｅｘｙを含む埋め込み画像ｅと、各副鍵情報ブロックＫｘｙを含む副鍵情報Ｋを得て、処理部１は得られたｅ、Ｋを記憶部５の画像ファイル及びパラメータファイルに記憶する（Ｓ１１５）。
【００４２】
送信者用コンピュータ１０の処理部１は、ｅ、Ｐ、Ｎ、Ｋを記憶部５から吸収し、受信者用コンピュータ２０に対してｅ、認証機関用コンピュータ３０にＰ、Ｎ、Ｋを送信する（Ｓ１１７）。ここでは、正規の受信者のみが認証機関から鍵情報を取得することができるものとする。
【００４３】
３−２．抽出処理
図６に、抽出処理のフローチャートを示す。また、図７は、Ｎ＝２の場合の、一つのブロックに対する抽出処理の概念図である。
【００４４】
処理部１は、署名情報を埋め込んだ受信画像のブロックｅ’ｘｙ（ｘ＝０、…、ｗ−１、　ｙ＝０、…、ｈ−１）に分割し、この各画素値ｅ’ｉｊ（ｉ、ｊ＝０、…、Ｎ−１）を設定し、その受信画像ｅ’を記憶部５の画像ファイル５２に記憶する（Ｓ２０１）。処理部１は、認証機関用コンピュータ３０から予め取得した主鍵情報Ｐ、位数Ｎ、副鍵情報Ｋ、を記憶部５のパラメータファイル５１から読み取る又は認証機関用コンピュータ３０から受信することで設定する（Ｓ２０２）。処理部１は、Ｐを法とする位数Ｎの根α等のパラメータを計算する（Ｓ２０３）。
【００４５】
処理部１は、各受信画像ブロックｅ’ｘｙを、読み込み（Ｓ２０４）、予め取得したＰに基づき上述のように数論変換係数Ｅ’ｘｙに数論変換する（Ｓ２０５）。処理部１は、Ｅ’ｘｙとＫｘｙの逆元との積をとり受信画像ｅ’に基づく受信原画像ｏ’ｘｙの数論変換係数Ｏ’ｘｙを計算する（Ｓ２０７）。
【００４６】
Ｅ’ｉｊＫ−１ｉｊ＝Ｏ’ｉｊ（ｍｏｄＰ）　　（１１）
（ここに、Ｏ’ｉｊ、Ｅ’ｉｊ、Ｋｉｊは、Ｏ’ｘｙ、Ｅ’　ｘｙ、Ｋｘｙの各要素値をそれぞれ示す。）
【００４７】
処理部１は、得られたＯ’ｘｙを逆数論変換したものをｏ’ｘｙとして求める（Ｓ２０９）。処理部１は、署名情報を抽出するため、式（８）に基づき、ｏ’ｘｙとｅ’ｘｙとの差をとる（Ｓ２１１）。つまり、差をｓ’ｘｙとし、ｏ’ｘｙ、ｓ’ｘｙの各要素値をｏ’ｉｊ、ｓ’ｉｊとすると、
ｏ’ｉｊ−ｅ’ｉｊ＝ｓ’ｉｊ　　　　（１２）
となる。処理部は、各前記ステップの処理をｗ×ｈ個の受信画像ブロックに対して行い、Ｓ’ｘｙとＯ’ｘｙを得て、記憶部に記憶する（Ｓ２１３）。
【００４８】
３−３．改ざん検出処理
図８に改ざん検出処理のフローチャートを示す。図は一つのブロックに対する検出処理の過程を表したものである。なお本手法では、改ざんがなければ受信側で原画像を復元できる利点がある。処理部１は、記憶部５の画像ファイル５２から受信画像に基づく受信原画像ｏ’ｘｙの検出対象ブロックを読み込む（Ｓ３０１）。
【００４９】
ここで、ｅ’ｘｙに改ざんがなければｅ’ｘｙ＝ｅｘｙである。この場合は、式（８）、式（１０）および数論変換の性質から、ｏ’ｘｙ＝ｏｘｙ、ｓ’ｘｙ＝ｓｘｙとなる。一方で、これらの式が成立しない場合は改ざんがあったと見なす。本手法では、例えば、ｏ’ｘｙおよびｓ’ｘｙが以下に示す条件を一つでも満たせば（Ｓ３０３、Ｓ３０５、Ｓ３０７）、ｅ’ｘｙは改ざんされているとする（Ｓ３１１）。一方、処理部１は、全ての条件をクリアすれば改ざんされていないとする。（Ｓ３１３）
条件１（Ｓ３０３）　ｏ’ｉｊ＞ｏｍａｘである。
条件２（Ｓ３０５）　式（９）から署名情報を生成し、ｓ’ｘｙと一致しない。条件３（Ｓ３０７）　ｏ’ｘｙ、ｓ’ｘｙ、式（８）および式（１０）より副鍵情報を生成し、受信したＫｘｙと一致しない。
【００５０】
条件１は、ｏ’ｘｙが画像としての要件を満たしていない場合は改ざんと見なすものである。Ｐ＞＞ｏｍａｘである場合に、この条件は有効である。条件２と条件３については、ｏ’ｘｙ＝ｏｘｙ、ｓ’ｘｙ＝ｓｘｙであれば、ｏ’ｘｙやｓ’ｘｙから署名情報や副鍵情報を生成したものと、受信した署名情報や副鍵情報は一致するはずである。もし一致しない場合は、改ざんされていると見なせる。なお、これら条件１〜３のうち例えば条件３のみでも判定可能である。また、条件３の処理をすべてに行うと処理に時間を要するため、比較的処理が複雑ではない条件１及び２を用いることで検出処理時間を短縮することもできる。その他、適宜の条件及びその組み合わせを用いることができる。
【００５１】
４．改ざん訂正
図９は、改ざん訂正についてのフローチャートである。ステップＳ３０１〜Ｓ３１３は改ざん検出処理の各ステップの処理と同様であり、改ざんを検出する処理である。
【００５２】
３−３で述べたすべての条件を満たさないブロックは、改ざんされていない正規ブロックの場合のみである（Ｓ３１３）。ゆえにそのようなブロックを全数探索すればよい。ただ、全数探索では多大な計算時間を必要とするため、工夫が必要である。
【００５３】
改ざんがされている場合（Ｓ３１１）、処理部１は、初めての改ざん検出処理か判断する（Ｓ４０１）。処理部１は、初めての改ざん検出の場合は、探索パターンのための初期値を周囲のブロックに基づき設定する（Ｓ４０３）。
【０００５４】
処理部１は、改ざんされたと判断された対象ブロックの各画素に、初期値又は初期値から派生する複数値の任意の組合わせを当てはめた探索パターンを作成する（Ｓ４０５）。処理部１は、作成された探索パターンに基づき判断するステップＳ３０３〜Ｓ３０７で改ざんされていないと判断されるまで、探索パターンを作成するステップＳ４０５及び判断するステップＳ３０３〜Ｓ３１１を繰り返し、該当する探索パターンを求める。処理部１は、求めた探索パターンを記憶部５の画像ファイル５２に記憶する（Ｓ４０７）。
【００５５】
図１０に、改ざん訂正のスキャンについての説明図を示す。また、図１１に、改ざん訂正における検索を開始する初期値の算出と検索についての説明図を示す。
【００５６】
今、ｅ’ｘｙに改ざんが検出されたとする。図に示す方向にスキャンして改ざん訂正を行うとすると、隣接する二つのブロックであるｅ’ｘ（ｙ−１）とｅ’（ｘ−１）ｙは正規のブロックである。自然画像は画素値の変化が小さいという特徴があるため、ｅ’ｘ（ｙ−１）とｅ’（ｘ−１）ｙの各画素値の平均は、ｅ’ｘｙの真値に近いと予測できる。よって、この予測値を初期値として探索を開始することで、探索にかかる時間を短縮できる。
【００５７】
図１２に、改ざん訂正における探索パターン作成についての説明図を示す。
図の具体例で説明すると、例えば、一段目の探索ではすべて１０７のパターンを作ってテストする。二段目では１０６、１０７、１０８の三つの数字を使ったすべてのＮ×Ｎのパターンについてテストする。（この例では３４＝８１通り）さらに、三段目では５４＝６２５通りとなる。このように、テストするパターンを生成する　ための数字の数をだんだん増やしていき、真値が見つかるまで幅を広げながら探索する。
【００５８】
５．シミュレーション実験
図１３に、実験に用いたパラメータの説明図を示す。図１４、図１５に、シミュレーション実験の結果についての説明図（１）、（２）を示す。
本手法を図１４（ａ）に示す標準画像ＬＥＮＡに適用し、有効性を検証した。
ＬＥＮＡは２５６×２５６画素、８ｂｉｔ階調の白黒画像である。
【００５９】
５−１．改ざん位置検出実験
埋め込み処理を行った結果が図１４（ｂ）である。ＳＮＲは４３．１ｄＢとなり、署名情報の埋め込み強度が小さいことから、埋め込みによる劣化はほとんど目立たなかった。ただし、ＳＮＲは以下の式で算出した。
【００６０】
【数８】
2004048285.tif 000009
【００６１】
ここで、ｏｒｇｉｊは原画像の画素値、ｅｍｂｉｊは埋め込み画像の画素値である。
【００６２】
次に、図１４（ｂ）を図１４（ｃ）のように改ざんを行った。これは図１４（ｂ）において２０×２０画素の矩形領域内を輝度値２００で塗りつぶしたものである。図１４（ｄ）が本手法による改ざん検出結果である。変色した箇所が、改ざんと判定された箇所である。変色箇所と実際の改ざん箇所は一致していることから、提案手法が有効であることがわかった。
【００６３】
５−２．改ざん訂正実験
様々な箇所に前節と同様の改ざんを行い、提案手法による改ざん訂正を行った。図１５（ａ）は、図１４（ｃ）のような画素値の変化が小さい箇所に改ざんを行った場合の改ざん訂正結果である。一方、図１５（ｃ）は、図１５（ｂ）のような画素値の変化が大きな箇所に改ざんを行った場合の改ざん訂正結果である。いずれの場合も改ざん前の画像と全く同じものが得られ、提案手法が有効であることがわかった。
【００６４】
なお図１６は、改ざん箇所における隣接画素の差分値の標準偏差を横軸に、改ざん訂正処理に要した時間を縦軸にしたグラフである。標準偏差が大きいほど時間がかかることがわかった。
【００６５】
６．考察
シミュレーション実験の結果、提案手法ではブロック単位での位置検出が可能であることがわかった。ゆえに、ブロックサイズＮは小さいほど正確な位置検出が可能であるが、一方でＫｘｙのビット数が小さくなるため、全数探索に対する安全性は低下する。この問題を改善するために、法Ｐをできるだけ大きな整数の中から選ぶことを考える。例えば、Ｎ＝２、Ｐは３２ｂｉｔで表すことのできる整数の中から選ぶとすると、一つのブロックは３２×２×２＝１２８ｂｉｔのＫｘｙを持つことになり、全数探索によってＫｘｙを同定することが非常に困難となるので、安全性を高めることができる。また、標準偏差が大きいほど改ざん訂正処理に時間が増大している。これは、本発明による改ざん訂正は付近の画素からの予測値を初期値として真値の探索を始めるが、エッジ部分のような標準偏差が大きな箇所に改ざんが行われた場合、その予測値と真値の誤差が大きくなるからだと考えられる。
【００６６】
７．むすび
本発明では、数論変換による脆弱型電子透かしを用いた改ざん位置の検出と訂正について検討した。シミュレーション実験を通じて提案手法の有効性について検討し、良好な結果を得た。
【００６７】
本発明の改ざん位置検出方法・改ざん訂正方法又は改ざん位置検出・改ざん訂正の装置・システムは、その各手順をコンピュータに実行させるための改ざん位置検出プログラム・改ざん訂正プログラム、改ざん位置検出プログラム・改ざん訂正プログラムを記録したコンピュータ読み取り可能な記録媒体、改ざん位置検出プログラム・改ざん訂正プログラムを含みコンピュータの内部メモリにロード可能なプログラム製品、そのプログラムを含むサーバ等のコンピュータ、等により提供されることができる。
【００６８】
８．文献
［１］ＮＴＴデータ経営研究所（編著）、電子文書署名、ＮＴＴ出版株式会社、東京、２００１．
［２］遠藤直樹、小出昭夫、“コンテンツ配信と不正コピー防止、”信学会誌、Ｖｏｌ．８３，Ｎｏ．２、ｐｐ．１１７−１２１，Ｆｅｂ．２０００．
［３］小野束（著）、電子透かしとコンテンツ保護、オーム社、東京、２００１．
［４］Ｐ．　Ｓ．　Ｌ．　Ｍ．　Ｂａｒｒｅｔｏ，　Ｈ．Ｙ．Ｋｉｍ，ａｎｄ　Ｖ．Ｒｉｊｍｅｎ，　“Ｔｏｗａｒｄ　Ａ　Ｓｅｃｕｒｅ　Ｐｕｂｌｉｃ−Ｋｅｙ　Ｂｌｏｃｋｗｉｓｅ　Ｆｒａｇｉｌｅ　Ａｕｔｈｅｎｔｉｃａｔｉｏｎ　Ｗａｔｅｒｍａｒｋｉｎｇ，”　Ｐｒｏｃ．　ＩＥＥＥ　Ｉｎｔ．　Ｃｏｎｆ．　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，　ｖｏｌ．２，　ｐｐ．４９４−４９７，　２００１．
［５］Ｐ．　Ｗ．　Ｗｏｎｇ，　“Ａ　Ｐｕｂｌｉｃ　Ｋｅｙ　Ｗａｔｅｒｍａｒｋｉｎｇ　ｏｆ　Ｉｍａｇｅ　Ｖｅｒｉｆｉｃａｔｉｏｎ　ａｎｄ　Ａｕｔｈｅｎｔｉｃａｔｉｏｎ、”　Ｐｒｏｃ．　ＩＥＥＥ　Ｉｎｔ．　Ｃｏｎｆ．　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，　ｖｏｌ．１，　ＭＡ１１．０７，　１９９８．
［６］岩村恵市、林純一、桜井幸一、今井秀樹、“安全な改ざん位置検出用電子透かしに関する考察と提案、”コンピュータセキュリティシンポジウム、ｐｐ．２８３−２８８，　Ｏｃｔ．　２００１．
［７］小野束、“電子文書改竄検出方法およびその装置、”公開特許広報、特開２００２−４４４２９、日本国特許庁、Ｆｅｂ．２００２．
［８］Ｈ．　Ｔａｍｏｒｉ，　Ｎ．　Ａｏｋｉ，　ａｎｄ　Ｔ．　Ｙａｍａｍｏｔｏ，　“Ａ　Ｆｒａｇｉｌｅ　Ｄｉｇｉｔａｌ　Ｗａｔｅｒｍａｒｋｉｎｇ　Ｔｅｃｈｎｉｑｕｅ　ｂｙ　Ｎｕｍｂｅｒ　Ｔｈｅｏｒｅｔｉｃ　Ｔｒａｎｓｆｏｒｍ，”　ＩＥＩＣＥ　Ｔｒａｎｓ．　Ｆｕｎｄａｍｅｎｔａｌｓ，　Ａｕｇ．２００２．　（ｔｏ　ｂｅ　ｐｕｂｌｉｓｈｅｄ）
［９］Ｊ．　Ｈ．　ＭｃＣｌｅｌｌａｎ，　ａｎｄ　Ｃ．　Ｍ．　Ｒａｄｅｒ，　“Ｎｕｍｂｅｒ　Ｔｈｅｏｒｙ　ｉｎ　Ｄｉｇｉｔａｌ　Ｓｉｇｎａｌ　Ｐｒｏｃｅｓｓｉｎｇ，”　Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，　Ｎｅｗ　Ｊｅｒｓｅｙ，　１９７９．
［１０］電子情報通信学会（編）、ディジタル信号処理ハンドブック、オーム社、東京、１９９３．
［１１］Ｓ．Ｃ．Ｃｏｕｔｉｎｈｏ（著）、林彬（訳）、暗号の数学的基礎、シュプリンガー・フェアラーク東京株式会社、東京、２００１．
［１２］Ｈ．Ｊ．Ｎｕｓｓｂａｕｍｅｒ（著）、佐川雅彦、本間仁志（訳）、高速フーリエ変換のアルゴリズム、科学技術出版社、東京、１９８９．
［１３］谷荻隆嗣（著）、ディジタル信号処理ライブラリー４　アルゴリズムと並列処理、コロナ社、東京、２０００．
［１４］田森秀明、青木直史、山本強、“数論変換を用いた改ざん検出可能な電子透かし方式、”信学技報ＩＥ２００１−３３，ｐｐ．１０５−１１０，　Ｊｕｌ．　２００１．
［１５］Ｊ．　Ｆｒｉｄｒｉｃｈ　ａｎｄ　Ｍ．　Ｇｏｌｊａｎ，　“Ｐｒｏｔｅｃｔｉｏｎ　ｏｆ　Ｄｉｇｉｔａｌ　Ｉｍａｇｅｓ　Ｕｓｉｎｇ　Ｓｅｌｆ−Ｅｍｂｅｄｄｉｎｇ，”　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｃｏｎｔｅｎｔ　Ｓｅｃｕｒｉｔｙ　ａｎｄ　Ｄａｔａ　Ｈｉｄｉｎｇ　ｉｎ　Ｄｉｇｉｔａｌ　Ｍｅｄｉａ，　Ｎｅｗ　Ｊｅｒｓｅｙ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，　Ｍａｙ　１９９９．
［１６］Ｊ．　Ｆｒｉｄｒｉｃｈ　ａｎｄ　Ｍ．　Ｇｏｌｊａｎ，　“Ｉｍａｇｅｓ　ｗｉｔｈ　Ｓｅｌｆ−Ｃｏｒｒｅｃｔｉｎｇ　Ｃａｐａｂｉｌｉｔｉｅｓ，”　ＩＣＩＰ’９９，　Ｋｏｂｅ，　Ｊａｐａｎ，　Ｏｃｔ．　１９９９．
【００６９】
【発明の効果】
本発明によると、以上のように、数論変換（ＮＴＴ：Ｎｕｍｂｅｒ　Ｔｈｅｏｒｅｔｉｃ　Ｔｒａｎｓｆｏｒｍ）による脆弱型電子透かしを用いた改ざん位置検出手法を提供することができる。さらに、本発明によると、数論変換に基づく新たな手法により、改ざんの位置検出だけでなく、数論変換の性質から、改ざん訂正手法を提供することができる。
【００７０】
本発明によると、受信者は透かし情報が埋め込まれた画像を受け取った後、認証機関から取得した鍵情報を用いて原本性を確認する。この過程で送信者は、原本そのものを受信者あるいは認証機関に伝送する必要がなく、原本を第三者に見せることなく保護することができる。
【００７１】
また、本発明は、インターネット回線を利用した画像を含む公文書の伝送、ディジタルカメラやスキャナ等によって取得された画像の原本性保証、画像に施された各種修正や特殊効果の同定と除去等に利用できると考えられる。
【図面の簡単な説明】
【図１】素数１３のｙｘ（ｍｏｄ　１３）の説明図。
【図２】システム構成の概略図。
【図３】送信者・受信者用コンピュータのハードウェアの構成図。
【図４】埋め込み処理のフローチャート。
【図５】Ｎ＝２の場合の、一つのブロックに対する埋め込み処理の概念図。
【図６】抽出処理のフローチャート。
【図７】Ｎ＝２の場合の、一つのブロックに対する抽出処理の概念図。
【図８】改ざん検出処理のフローチャート。
【図９】改ざん訂正についてのフローチャート。
【図１０】改ざん訂正のスキャンについての説明図
【図１１】改ざん訂正における検索を開始する初期値の算出と検索についての説明図。
【図１２】改ざん訂正における探索パターン作成についての説明図。
【図１３】実験に用いたパラメータの説明図。
【図１４】シミュレーション実験の結果についての説明図（１）。
【図１５】シミュレーション実験の結果についての説明図（２）。
【図１６】改ざん箇所における隣接画素の差分値の標準偏差を横軸に、改ざん訂正処理に要した時間を縦軸にしたグラフ。
【符号の説明】
１０　送信者用コンピュータ
２０　受信者用コンピュータ
３０　認証機関用コンピュータ
【図１】
2004048285.tif 000011
【図２】
2004048285.tif 000012
【図３】
2004048285.tif 000013
【図４】
2004048285.tif 000014
【図５】
2004048285.tif 000015
【図６】
2004048285.tif 000016
【図７】
2004048285.tif 000017
【図８】
2004048285.tif 000018
【図９】
2004048285.tif 000019
【図１０】
2004048285.tif 000020
【図１１】
2004048285.tif 000021
【図１２】
2004048285.tif 000022
【図１３】
2004048285.tif 000023
【図１４】
2004048285.tif 000024
【図１５】
2004048285.tif 000025
【図１６】
2004048285.tif 000026