(57)【特許請求の範囲】
【請求項１】
被検査データに付加された電子透かしの識別データの検出を依頼する利用者端末と、該利用者端末にネットワーク経由で接続され前記利用者端末からの依頼を受けて前記識別データの検出を行うセンタ端末とで構成されたオンライン識別データ検出装置におけるオンライン識別データ検出方法であって、
ａ）前記利用者端末の依頼機構における検出依頼手段が、前記識別データの検出を前記センタ端末に依頼する検出依頼データを生成するステップ、
ｂ）前記利用者端末の依頼機構における検出依頼正当性証明手段が、前記検出依頼データの正当性を証明する検出依頼正当性証明データを生成するステップ、
ｃ）前記センタ端末の検出機構における検出依頼正当性検証手段が、前記利用者端末から受信した検出依頼正当性証明データに基づいて前記検出依頼データの正当性を検証し、前記検出依頼データの正当性が検証された場合に限り検出依頼を受理するステップ、
を含み、
前記検出依頼手段が生成する検出依頼データは、冪乗剰余積の形式を有する確率公開鍵暗号文であってその各指数係数が前記被検査データの各要素の値から導出された値とされるものであり、前記検出依頼正当性証明手段が生成する検証依頼正当性証明データは、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が所定の区間内に属することを証明するデータであり、前記検出依頼正当性検証手段は、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記所定の区間内に属することを検証することを特徴とするオンライン識別データ検出方法。
【請求項２】
ｄ）前記センタ端末の検出機構における検出結果正当性証明手段が、前記受理した検出依頼データに基づく識別データの検出結果とその正当性を証明する検出結果正当性証明データとを生成して前記利用者端末へ送信するステップ、
ｅ）前記利用者端末の依頼機構における検証結果正当性検証手段が、前記センタ端末から受信した前記検出結果正当性証明データに基づいて前記検出結果の正当性を検証するステップ、
をさらに含むことを特徴とする請求項１記載のオンライン識別データ検出方法。
【請求項３】
前記検出結果正当性証明手段は検出結果を確率的に決定することを特徴とする請求項２記載のオンライン識別データ検出方法。
【請求項４】
前記検出結果正当性証明手段は、前記確率公開鍵暗号文を復号して得た平文である統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が確率的に決定した前記区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信するものであり、前記検出結果正当性検証手段は、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証するものである請求項１記載のオンライン識別データ検出方法。
【請求項５】
被検査データに付加された電子透かしの識別データの検出を依頼する利用者端末と、該利用者端末にネットワーク経由で接続され前記利用者端末からの依頼を受けて前記識別データの検出を行うセンタ端末とで構成され、
前記利用者端末は、前記識別データの検出を前記センタ端末に依頼する検出依頼データを生成する検出依頼手段と、前記検出依頼データの正当性を証明する検出依頼正当性証明データを生成する検出依頼正当性証明手段とを含む依頼機構を備え、
前記センタ端末は、前記利用者端末から受信した検出依頼正当性証明データに基づいて前記検出依頼データの正当性を検証し、前記検出依頼データの正当性が検証された場合に限り検出依頼を受理する検出依頼正当性検証手段を含み、
前記検出依頼手段が生成する検出依頼データは、冪乗剰余積の形式を有する確率公開鍵暗号文であってその各指数係数が前記被検査データの各要素の値から導出された値とされるものであり、前記検出依頼正当性証明手段が生成する検証依頼正当性証明データは、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が所定の区間内に属することを証明するデータであり、前記検出依頼正当性検証手段は、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記所定の区間内に属することを検証するものであることを特徴とするオンライン識別データ検出装置。
【請求項６】
前記検出機構は、前記受理した検出依頼データに基づく識別データの検出結果とその正当性を証明する検出結果正当性証明データとを生成して前記利用者端末へ送信する検出結果正当性証明手段を含み、
前記依頼機構は、前記センタ端末から受信した前記検出結果正当性証明データに基づいて前記検出結果の正当性を検証する検証結果正当性検証手段を含む請求項５記載のオンライン識別データ検出装置。
【請求項７】
前記検出結果正当性証明手段は検出結果を確率的に決定するものである請求項６記載のオンライン識別データ検出装置。
【請求項８】
前記検出結果正当性証明手段は、前記確率公開鍵暗号文を復号して得た平文である統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が確率的に決定した前記区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信するものであり、前記検出結果正当性検証手段は、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証するものである請求項５記載のオンライン識別データ検出装置。
【請求項９】
被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合の大きさ、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵を、それぞれ公開情報として記憶する公開情報記憶手段と、
前記公開情報を使って前記被検査データの電子透かしの検出をネットワークを通じてセンタ端末に依頼する依頼機構とを備え、
前記依頼機構は、
前記被検査データと前記抽出公開鍵と前記公開鍵とから、冪乗剰余積の形式を有し各指数係数に前記被検査データの要素の値を置いた確率公開鍵暗号文からなる検出依頼データを生成して前記センタ端末に送信する検出依頼手段と、
前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データを生成して前記センタ端末に送信する検出依頼正当性証明手段と、
前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証した前記センタ端末が前記確率公開鍵暗号文を復号して得た平文である統計量が属する区間を示す検出結果を生成し、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して送信してきたときに、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証する検出結果正当性検証手段と、
前記検出結果正当性検証手段の検証が成功したときに、前記センタ端末から送られてきた前記検出結果を取り出して出力する検出結果取得手段とを備える利用者端末。
【請求項１０】
被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合の大きさ、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵、センタ端末が検出結果を確率的に決定する際の確率を定める変数を、それぞれ公開情報として記憶する公開情報記憶手段と、
前記公開情報を使って前記被検査データの電子透かしの検出をネットワークを通じてセンタ端末に依頼する依頼機構とを備え、
前記依頼機構は、
前記被検査データと前記抽出公開鍵と前記公開鍵とから、冪乗剰余積の形式を有し各指数係数に前記被検査データの要素の値を置いた確率公開鍵暗号文からなる検出依頼データを生成して前記センタ端末に送信する検出依頼手段と、
前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データを生成して前記センタ端末に送信する検出依頼正当性証明手段と、
前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証した前記センタ端末が前記確率公開鍵暗号文を復号して得た平文である統計量が属する区間を確率的に決定した検出結果を生成し、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して送信してきたときに、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証する検出結果正当性検証手段と、
前記検出結果正当性検証手段の検証が成功したときに、前記センタ端末から送られてきた前記検出結果を取り出して出力する検出結果取得手段とを備える利用者端末。
【請求項１１】
被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素の数、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵、前記被検査データに対して電子透かしの有無を反転させるために使う基準値とこの基準値の作成に使用した乱数、センタ端末が検出結果を確率的に決定する際の確率を定める変数を、それぞれ公開情報として記憶する公開情報記憶手段と、
前記公開情報を使って前記被検査データの電子透かしの検出をネットワークを通じて前記センタ端末に依頼する依頼機構とを備え、
前記依頼機構は、
前記被検査データに対して電子透かしの有無を反転させて検出依頼を行うか否かを制御する反転制御情報を生成する反転制御手段と、
前記被検査データと前記基準値とから、前記反転制御情報が反転を示す場合には透かしの有無を反転させた新たな被検査データを生成し、前記反転制御情報が非反転を示す場合には透かしの有無を反転させない新たな被検査データを生成する手段と、前記生成した新たな被検査データと前記抽出公開鍵と前記公開鍵とから、冪乗剰余積の形式を有し各指数係数に前記新たな被検査データを置いた確率公開鍵暗号文からなる検出依頼データを生成して前記センタ端末に送信する検出依頼手段と、
前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データを生成して前記センタ端末に送信する検出依頼正当性証明手段と、
前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証した前記センタ端末が前記確率公開鍵暗号文を復号して得た平文である統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信してきたときに、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証する検出結果正当性検証手段と、
前記検出結果正当性検証手段の検証が成功したときに、前記センタ端末から送られてきた前記検出結果と前記反転制御情報とに基づいて真の検出結果を取り出して出力する検出結果取得手段とを備える利用者端末。
【請求項１２】
被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵と秘密鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵とこの抽出公開鍵に対応する抽出秘密鍵を、それぞれ生成して記憶すると共に、前記列数、前記定数、前記変更量、前記インデックス集合の大きさ、前記公開鍵、前記抽出公開鍵を、それぞれ公開情報として公開する情報設定公開手段と、
ネットワークを通じて接続された利用者端末からの依頼を受けて前記被検査データの電子透かしの検出を行う検出機構とを備え、
前記検出機構は、
前記利用者端末が、前記被検査データと前記抽出公開鍵と前記公開鍵とを使用して冪乗剰余積の形式を有し各指数係数に前記被検査データの要素の値を置いた確率公開鍵暗号文からなる検出依頼データを生成し、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データと共に送信してきたときに、前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証し、正当性を検証した場合に限り前記検出依頼データを受理する検出依頼正当性検証手段と、
受理した前記検出依頼データを復号して得た、前記被検査データのパッチワークによる電子透かしにかかる統計量が属する区間を示す検出結果を生成し、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信する検出結果正当性証明手段とを備えるセンタ端末。
【請求項１３】
被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵と秘密鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵とこの抽出公開鍵に対応する抽出秘密鍵、センタ端末が検出結果を確率的に決定する際の確率を定める変数を、それぞれ生成して記憶すると共に、前記列数、前記定数、前記変更量、前記インデックス集合の大きさ、前記公開鍵、前記抽出公開鍵、前記変数を、それぞれ公開情報として公開する情報設定公開手段と、
ネットワークを通じて接続された利用者端末からの依頼を受けて前記被検査データの電子透かしの検出を行う検出機構とを備え、
前記検出機構は、
前記利用者端末が、前記被検査データと前記抽出公開鍵と前記公開鍵とを使用して冪乗剰余積の形式を有し各指数係数に前記被検査データの要素の値を置いた確率公開鍵暗号文からなる検出依頼データを生成して、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データと共に送信してきたときに、前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証し、正当性を検証した場合に限り前記検出依頼データを受理する検出依頼正当性検証手段と、
受理した前記検出依頼データを復号して得た平文である、前記被検査データのパッチワークによる電子透かしにかかる統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信する検出結果正当性証明手段とを備えるセンタ端末。
【請求項１４】
被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵と秘密鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵とこの抽出公開鍵に対応する抽出秘密鍵、前記被検査データに対して電子透かしの有無を反転させるために使う基準値とこの基準値の作成に使用した乱数、センタ端末が検出結果を確率的に決定する際の確率を定める変数を、それぞれ生成して記憶すると共に、前記列数、前記定数、前記変更量、前記インデックス集合の大きさ、前記公開鍵、前記抽出公開鍵、前記基準値、前記乱数、前記変数を、それぞれ公開情報として公開する情報設定公開手段と、
ネットワークを通じて接続された利用者端末からの依頼を受けて前記被検査データの電子透かしの検出を行う検出機構とを備え、
前記検出機構は、
前記センタ端末が、前記被検査データに対して電子透かしの有無を反転させて検出依頼を行うか否かを制御する反転制御情報と前記被検査データと前記基準値とから、前記反転制御情報が反転を示す場合には透かしの有無を反転させた新たな被検査データを生成し、前記反転制御情報が非反転を示す場合には透かしの有無を反転させない新たな被検査データを生成して、前記生成した新たな被検査データと抽出公開鍵と公開鍵とから、冪乗剰余積の形式を有し各指数係数に前記被検査データを置いた確率公開鍵暗号文からなる検出依頼データを生成し、前記冪乗剰余積の各指数係数が前記定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データと共に送信してきたときに、前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証し、正当性を検証した場合に限り前記検出依頼データを受理する検出依頼正当性検証手段と、
受理した前記検出依頼データを復号して得た平文である、前記被検査データのパッチワークによる電子透かしにかかる統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信する検出結果正当性証明手段とを備えるセンタ端末。
【請求項１５】
被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合の大きさ、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵を、それぞれ公開情報として記憶する公開情報記憶手段を有し、前記公開情報を使って前記被検査データの電子透かしの検出をネットワークを通じてセンタ端末に依頼する利用者端末を構成するコンピュータを、
前記被検査データと前記抽出公開鍵と前記公開鍵とから、冪乗剰余積の形式を有し各指数係数に前記被検査データの要素の値を置いた確率公開鍵暗号文からなる検出依頼データを生成して前記センタ端末に送信する検出依頼手段、
前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データを生成して前記センタ端末に送信する検出依頼正当性証明手段、
前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証した前記センタ端末が前記確率公開鍵暗号文を復号して得た平文である統計量が属する区間を示す検出結果を生成し、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して送信してきたときに、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証する検出結果正当性検証手段、
前記検出結果正当性検証手段の検証が成功したときに、前記センタ端末から送られてきた前記検出結果を取り出して出力する検出結果取得手段、
として機能させるプログラム。
【請求項１６】
被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合の大きさ、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵、センタ端末が検出結果を確率的に決定する際の確率を定める変数を、それぞれ公開情報として記憶する公開情報記憶手段を有し、前記公開情報を使って前記被検査データの電子透かしの検出をネットワークを通じてセンタ端末に依頼する利用者端末を構成するコンピュータを、
前記被検査データと前記抽出公開鍵と前記公開鍵とから、冪乗剰余積の形式を有し各指数係数に前記被検査データの要素の値を置いた確率公開鍵暗号文からなる検出依頼データを生成して前記センタ端末に送信する検出依頼手段、
前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データを生成して前記センタ端末に送信する検出依頼正当性証明手段、
前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証した前記センタ端末が前記確率公開鍵暗号文を復号して得た平文である統計量が属する区間を確率的に決定した検出結果を生成し、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して送信してきたときに、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証する検出結果正当性検証手段、
前記検出結果正当性検証手段の検証が成功したときに、前記センタ端末から送られてきた前記検出結果を取り出して出力する検出結果取得手段、
として機能させるプログラム。
【請求項１７】
被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素の数、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵、前記被検査データに対して電子透かしの有無を反転させるために使う基準値とこの基準値の作成に使用した乱数、センタ端末が検出結果を確率的に決定する際の確率を定める変数を、それぞれ公開情報として記憶する公開情報記憶手段を有し、前記公開情報を使って前記被検査データの電子透かしの検出をネットワークを通じて前記センタ端末に依頼する利用者端末を構成するコンピュータを、
前記被検査データに対して電子透かしの有無を反転させて検出依頼を行うか否かを制御する反転制御情報を生成する反転制御手段、
前記被検査データと前記基準値とから、前記反転制御情報が反転を示す場合には透かしの有無を反転させた新たな被検査データを生成し、前記反転制御情報が非反転を示す場合には透かしの有無を反転させない新たな被検査データを生成する手段と、前記生成した新たな被検査データと前記抽出公開鍵と前記公開鍵とから、冪乗剰余積の形式を有し各指数係数に前記新たな被検査データを置いた確率公開鍵暗号文からなる検出依頼データを生成して前記センタ端末に送信する検出依頼手段、
前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データを生成して前記センタ端末に送信する検出依頼正当性証明手段、
前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証した前記センタ端末が前記確率公開鍵暗号文を復号して得た平文である統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信してきたときに、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証する検出結果正当性検証手段、
前記検出結果正当性検証手段の検証が成功したときに、前記センタ端末から送られてきた前記検出結果と前記反転制御情報とに基づいて真の検出結果を取り出して出力する検出結果取得手段、
として機能させるプログラム。
【請求項１８】
ネットワークを通じて接続された利用者端末からの依頼を受けて被検査データの電子透かしの検出を行うセンタ端末を構成するコンピュータを、
被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵と秘密鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵とこの抽出公開鍵に対応する抽出秘密鍵を、それぞれ生成して記憶すると共に、前記列数、前記定数、前記変更量、前記インデックス集合の大きさ、前記公開鍵、前記抽出公開鍵を、それぞれ公開情報として公開する情報設定公開手段、
前記利用者端末が、前記被検査データと前記抽出公開鍵と前記公開鍵とを使用して冪乗剰余積の形式を有し各指数係数に前記被検査データの要素の値を置いた確率公開鍵暗号文からなる検出依頼データを生成し、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データと共に送信してきたときに、前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証し、正当性を検証した場合に限り前記検出依頼データを受理する検出依頼正当性検証手段、
受理した前記検出依頼データを復号して得た、前記被検査データのパッチワークによる電子透かしにかかる統計量が属する区間を示す検出結果を生成し、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信する検出結果正当性証明手段、
として機能させるプログラム。
【請求項１９】
ネットワークを通じて接続された利用者端末からの依頼を受けて被検査データの電子透かしの検出を行うセンタ端末を構成するコンピュータを、
被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵と秘密鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵とこの抽出公開鍵に対応する抽出秘密鍵、センタ端末が検出結果を確率的に決定する際の確率を定める変数を、それぞれ生成して記憶すると共に、前記列数、前記定数、前記変更量、前記インデックス集合の大きさ、前記公開鍵、前記抽出公開鍵、前記変数を、それぞれ公開情報として公開する情報設定公開手段、
前記利用者端末が、前記被検査データと前記抽出公開鍵と前記公開鍵とを使用して冪乗剰余積の形式を有し各指数係数に前記被検査データの要素の値を置いた確率公開鍵暗号文からなる検出依頼データを生成して、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データと共に送信してきたときに、前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証し、正当性を検証した場合に限り前記検出依頼データを受理する検出依頼正当性検証手段、
受理した前記検出依頼データを復号して得た平文である、前記被検査データのパッチワークによる電子透かしにかかる統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信する検出結果正当性証明手段、
として機能させるプログラム。
【請求項２０】
ネットワークを通じて接続された利用者端末からの依頼を受けて被検査データの電子透かしの検出を行うセンタ端末を構成するコンピュータを、
被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵と秘密鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵とこの抽出公開鍵に対応する抽出秘密鍵、前記被検査データに対して電子透かしの有無を反転させるために使う基準値とこの基準値の作成に使用した乱数、センタ端末が検出結果を確率的に決定する際の確率を定める変数を、それぞれ生成して記憶すると共に、前記列数、前記定数、前記変更量、前記インデックス集合の大きさ、前記公開鍵、前記抽出公開鍵、前記基準値、前記乱数、前記変数を、それぞれ公開情報として公開する情報設定公開手段、
前記センタ端末が、前記被検査データに対して電子透かしの有無を反転させて検出依頼を行うか否かを制御する反転制御情報と前記被検査データと前記基準値とから、前記反転制御情報が反転を示す場合には透かしの有無を反転させた新たな被検査データを生成し、前記反転制御情報が非反転を示す場合には透かしの有無を反転させない新たな被検査データを生成して、前記生成した新たな被検査データと抽出公開鍵と公開鍵とから、冪乗剰余積の形式を有し各指数係数に前記被検査データを置いた確率公開鍵暗号文からなる検出依頼データを生成し、前記冪乗剰余積の各指数係数が前記定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データと共に送信してきたときに、前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証し、正当性を検証した場合に限り前記検出依頼データを受理する検出依頼正当性検証手段、
受理した前記検出依頼データを復号して得た平文である、前記被検査データのパッチワークによる電子透かしにかかる統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信する検出結果正当性証明手段、
として機能させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像や音声のデジタルデータに付加された電子透かし（識別データ）を検出する方法に関し、特に利用者とセンタが相互に通信して電子透かしを検出するオンライン識別データ検出方法に関する。
【０００２】
【従来の技術】
近年、画像や音声のデジタルデータの流通が増加し、不正コピーが問題となっている。この問題の解決方法の一つに、電子透かし技術がある。電子透かし技術は、画像や音声のデータに対して、人が直接的に知覚できない識別データ(電子透かし)を読み書きする方法である。電子透かしには、元のデータの品質を大きく損ねないことに加え、透かしの改竄や消去が困難なことが求められる。なぜなら、この性質があれば不正にコピーされたデータから透かしを検出して不正を証明できるからである。
【０００３】
このような電子透かしを用いたシステムにおいては、電子透かしの付加方法を知らない利用者に対して、画像などに付加された電子透かしを示す必要があることが多い。電子透かしを検出する方法には幾つかの方法が提案されているが、その一つに、電子透かしの検出を希望する利用者がその検出をセンタに依頼するオンライン検出方法がある。
【０００４】
オンライン検出方法の従来技術の一例が峯松一彦(Kazuhiko Minematsu)による文献「オン ア セキュアー デジタル ウォーターマーク ディテクション プロトコル ユージング パッチワーク ウォーターマーキング、2000インターナショナル シンポジウム オン インフォメーション セオリー アンド イッツ アプリケーション(On a Secure Digital Watermark Detection Protocol Using Patchwork Watermarking、2000International Symposiumon Information Theory and Its Applications(ISITA2000))」（以下、文献１と称す）に記載されている。
【０００５】
文献１に記載の従来技術は、パッチワークを用いた電子透かしを、準同型性を持つ確率公開鍵暗号方式を用いて検出する。準同型性を持つ確率公開鍵暗号方式では、確立暗号である公開鍵暗号系に属する暗号方式であって、秘密鍵を用いることにより暗号文から平文のみならず、暗号化のために用いた乱数をも求めることができる。本明細書では、準同型性を持つ確率公開鍵暗号文を単に確率公開鍵暗号文と称する。以下、パッチワークを用いた電子透かしと確率公開鍵暗号について説明した後、文献１に記載の従来技術について説明する。
【０００６】
（１）パッチワークを用いた電子透かし方式
パッチワークを用いた電子透かし方式は、画像（または音声）の統計量を操作して識別データを書き込む。複数の統計量を使ったり、統計量の操作量を変えることにより複数 bit の情報を書き込めるが、ここでは 1 bit の情報の場合のみを説明する（本発明の実施の形態においても同様である）。
【０００７】
画素値の空間を［０，Ｒ］とし、画素数ｍの画像をＺ／ＲＺ上のｍ次元ベクトルで表現する。大きさＫのインデックス集合で、Ｉ1∩Ｉ２＝Φ、Ｉ1，Ｉ２⊆Ｚ／ＮＺとなるような、インデックス集合Ｉ1，Ｉ２を無作為に定める。このとき画像Ａ＝（ａ１…，ａｍ）の統計量Ｔ（Ａ）の期待値は０になる（ＰａをＰの確率分布とするとＥpａ［Ｔ（Ａ）］＝０）。
【数１】
0004092920.tif 000002
【０００８】
パッチワークでは透かし入り画像Ｘ＝（ｘ１…，ｘｍ）を画像Ａから以下のように生成する。ここで、変更量δは小さい正の整数である。
【数２】
0004092920.tif 000003
【０００９】
この結果、透かし入り画像の統計量Ｔ（Ｘ）の期待値は以下のように２δの変更を受ける。
【数３】
Ｅpx［Ｔ（Ｘ）］＝Ｅpａ［Ｔ（Ａ）］＋２δ＝２δ
【００１０】
このように、変更量δを小さくとることで画質の劣化を抑えつつ、統計量Ｔの期待値を０から変更する画像の操作が、パッチワークでの透かしの書き込みになる。そして、画像ＸについてＴ（Ｘ）が有為に０から外れているか否かで透かしの有無を判定する。例えば、Ｔ（Ｘ）＞δなら透かし有り、Ｔ（Ｘ）＜δなら透かし無しと判断する。
【００１１】
（２）確率公開鍵暗号
暗号化関数ｅが準同型であるとは、およそ、平文をｘ，ｙとしたとき、ｅ（ｘ＋ｙ）＝ｅ（ｘ）ｅ（ｙ）が成り立つことである。このような種類の暗号方式としては幾つかの方式があるが、ここではPaillierの方式を説明する。Paillierの方式では、鍵生成、暗号化、復号を以下のように行う。
【００１２】
○鍵生成
素数ｐ，ｑを生成し、ｎ＝ｐｑ，秘密鍵λ＝ｌｃｍ（ｐ−１，ｑ−１）とする。関数Ｌ（ｔ）＝（ｔ−１）／ｎを用いて、ｇｃｄ（Ｌ（ｇλmod n2），ｎ）＝１を満たす任意の数ｇ∈（Ｚ／ｎ２Ｚ）＊を選び、公開鍵を（ｎ，ｇ）とする。
○暗号化
平文ｘ∈Ｚ／ｎＺと乱数ｒ∈Ｚ／ｎＺを選び、暗号文ｅを次のように生成する。
ｅ＝ｅｒ（ｘ）＝ｇＸｒｎmod n2
○復号
平文ｘを暗号文ｅから次のようにして求める。
【数４】
0004092920.tif 000004
○乱数の求め方
暗号化のときに用いた乱数ｒは次のようにして求めることができる。
【数５】
0004092920.tif 000005
【００１３】
（３）文献１に記載のオンライン検出方法
文献１に記載の従来技術は、パッチワークによる透かしと確率公開鍵暗号を用いて、透かし検出を依頼する利用者と検出者（センタ）の相互通信により画像Ｘの透かし検出を以下のように行う。
【００１４】
○鍵配布
センタは、秘密情報であるインデックス集合Ｉ1，Ｉ２及び乱数ｒｉ∈Ｚ／ｎＺ，ｉ＝１，…，Ｎを用いて、抽出公開鍵Ｅ＝（ｅ１，…，ｅＮ）を次のように生成し、利用者に配布する。
【数６】
0004092920.tif 000006
○透かし検出依頼
利用者は画像Ｘと抽出公開鍵Ｅから、下記の冪乗剰余積からなる確率公開鍵暗号文を計算する。
【数７】
0004092920.tif 000007
その他に、およそ０又はおよそ２Ｋδの値ｖｉを無作為に多数（Ｍ個とする）生成し、それらの確率公開鍵暗号文Ｄ＝（ｄ１，…，ｄＭ）を生成する。このうち一つ（ｄｋとする）を数７の確率公開鍵暗号文ｅと置き換え、確率公開鍵暗号文Ｄをセンタに送る。
【００１５】
○透かし検出
センタは受信した確率公開鍵暗号文Ｄを復号して平文Ｄ（ｄｉ）を求める。この平文はパッチワークによる電子透かしの統計量に相当する。そして、平文の値を所定の閾値と比較することにより、以下のような数列Ｕ＝（ｕ１，…，ｕＭ）を生成して、検出結果として利用者に送る。
【数８】
0004092920.tif 000008
○検出結果の取得と検証
利用者はｕＫを透かしの有無の判定結果とする。ｕＫが画像Ｘの透かしの検出結果を与えることは、次式から分る。
【数９】
0004092920.tif 000009
また利用者は、全てのｉ（ｉ≠ｋ）に関して、Ｋδ＜ｖｉ＜ｎ／２ならｕｉ＝１、−ｎ／２＜ｖｉ＜Ｋδならｕｉ＝０が成り立つなら、センタの検出結果は正当であると見なす。
【００１６】
この従来技術において、利用者は全てのｉ（ｉ≠ｋ）の値をｖｉから計算できる。そのためｕＫを同定できないセンタは、不正なＵを生成すれば利用者に発覚する確率が高い。またｕＫを識別できないので、センタには検出結果は分らない。さらに、ＤからＸを知ることはできないため、センタはＸは分らない。一方利用者は、正直に上記方式を実行している限りＥの各要素の平文を解読し得ないので、透かしの書き込み方を知ることができないし、透かしの改竄もできない。
【００１７】
【発明が解決しようとする課題】
しかし、文献１に記載の従来技術では、利用者が不正な暗号文Ｄを生成することで、センタの秘密情報であるインデックス集合Ｉ1，Ｉ２を入手できる問題点がある。具体的には、利用者がｄｉ＝ｅＪ２Ｋδmod n2である暗号文Ｄを送ったときに、ｕｉ＝１ならばｊ∈Ｉ1であることと、ｄｉ＝ｅＪ−２Ｋδmod n2である暗号文Ｄを送ったときに、ｕｉ＝１ならばｊ∈Ｉ２であることとにより、利用者はＩ1，Ｉ２に関する情報を入手できる。この攻撃方法は、各暗号文ごとに行える。そして、多くの暗号文の復号結果をセンタは利用者に教えるため、一回の識別データ検出から、利用者は多くの識別データの付加方法の情報を得ることができることになる。
【００１８】
また、文献１に記載の従来技術では、センタは多くの暗号文の復号を行う必要があるため、効率が悪いという問題点もある。
【００１９】
本発明はこのような事情に鑑みて提案されたものであり、その目的は、センタから識別データ（電子透かし）の付加方法に関する情報の漏れを最小限にすることのできるオンライン識別データ検出方法及び装置を提供することにある。
【００２０】
また本発明の別の目的は、効率良く識別データ（電子透かし）を検出し得るオンライン識別データ検出方法及び装置を提供することにある。
【００２１】
【課題を解決するための手段】
本発明の第１のオンライン識別データ検出方法は、被検査データに付加された電子透かしの識別データの検出を依頼する利用者端末と、該利用者端末にネットワーク経由で接続され前記利用者端末からの依頼を受けて前記識別データの検出を行うセンタ端末とで構成されたオンライン識別データ検出装置におけるオンライン識別データ検出方法であって、ａ）前記利用者端末の依頼機構における検出依頼手段が、前記識別データの検出を前記センタ端末に依頼する検出依頼データを生成するステップ、ｂ）前記利用者端末の依頼機構における検出依頼正当性証明手段が、前記検出依頼データの正当性を証明する検出依頼正当性証明データを生成するステップ、ｃ）前記センタ端末の検出機構における検出依頼正当性検証手段が、前記利用者端末から受信した検出依頼正当性証明データに基づいて前記検出依頼データの正当性を検証し、前記検出依頼データの正当性が検証された場合に限り検出依頼を受理するステップ、を含み、前記検出依頼手段が生成する検出依頼データは、冪乗剰余積の形式を有する確率公開鍵暗号文であってその各指数係数が前記被検査データの各要素の値から導出された値とされるものであり、前記検出依頼正当性証明手段が生成する検証依頼正当性証明データは、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が所定の区間内に属することを証明するデータであり、前記検出依頼正当性検証手段は、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記所定の区間内に属することを検証することを特徴とする。
【００２２】
本発明の第２のオンライン識別データ検出方法は、第１のオンライン識別データ検出方法において、ｄ）前記センタ端末の検出機構における検出結果正当性証明手段が、前記受理した検出依頼データに基づく識別データの検出結果とその正当性を証明する検出結果正当性証明データとを生成して前記利用者端末へ送信するステップ、ｅ）前記利用者端末の依頼機構における検証結果正当性検証手段が、前記センタ端末から受信した前記検出結果正当性証明データに基づいて前記検出結果の正当性を検証するステップ、をさらに含むことを特徴とする。
【００２３】
本発明の第３のオンライン識別データ検出方法は、第２のオンライン識別データ検出方法において、前記検出結果正当性証明手段は検出結果を確率的に決定することを特徴とする。
【００２６】
本発明の第４のオンライン識別データ検出方法は、第１のオンライン識別データ検出方法において、前記検出結果正当性証明手段は、前記確率公開鍵暗号文を復号して得た平文である統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が確率的に決定した前記区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信するものであり、前記検出結果正当性検証手段は、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証する。
【００２７】
また、本発明の第１のオンライン識別データ検出装置は、被検査データに付加された電子透かしの識別データの検出を依頼する利用者端末と、該利用者端末にネットワーク経由で接続され前記利用者端末からの依頼を受けて前記識別データの検出を行うセンタ端末とで構成され、前記利用者端末は、前記識別データの検出を前記センタ端末に依頼する検出依頼データを生成する検出依頼手段と、前記検出依頼データの正当性を証明する検出依頼正当性証明データを生成する検出依頼正当性証明手段とを含む依頼機構を備え、前記センタ端末は、前記利用者端末から受信した検出依頼正当性証明データに基づいて前記検出依頼データの正当性を検証し、前記検出依頼データの正当性が検証された場合に限り検出依頼を受理する検出依頼正当性検証手段を含み、前記検出依頼手段が生成する検出依頼データは、冪乗剰余積の形式を有する確率公開鍵暗号文であってその各指数係数が前記被検査データの各要素の値から導出された値とされるものであり、前記検出依頼正当性証明手段が生成する検証依頼正当性証明データは、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が所定の区間内に属することを証明するデータであり、前記検出依頼正当性検証手段は、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記所定の区間内に属することを検証するものであることを特徴とする。
【００２８】
本発明の第２のオンライン識別データ検出装置は、第１のオンライン識別データ検出装置において、前記検出機構は、前記受理した検出依頼データに基づく識別データの検出結果とその正当性を証明する検出結果正当性証明データとを生成して前記利用者端末へ送信する検出結果正当性証明手段を含み、前記依頼機構は、前記センタ端末から受信した前記検出結果正当性証明データに基づいて前記検出結果の正当性を検証する検証結果正当性検証手段を含んでいる。
【００２９】
本発明の第３のオンライン識別データ検出装置は、第２のオンライン識別データ検出装置において、前記検出結果正当性証明手段は検出結果を確率的に決定するよう構成されている。
【００３２】
本発明の第４のオンライン識別データ検出装置は、第１のオンライン識別データ検出装置において、前記検出結果正当性証明手段は、前記確率公開鍵暗号文を復号して得た平文である統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が確率的に決定した前記区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信するものであり、前記検出結果正当性検証手段は、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証するものとして構成される。
【００３３】
また、本発明の第１の利用者端末は、被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合の大きさ、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵を、それぞれ公開情報として記憶する公開情報記憶手段と、前記公開情報を使って前記被検査データの電子透かしの検出をネットワークを通じてセンタ端末に依頼する依頼機構とを備え、前記依頼機構は、前記被検査データと前記抽出公開鍵と前記公開鍵とから、冪乗剰余積の形式を有し各指数係数に前記被検査データの要素の値を置いた確率公開鍵暗号文からなる検出依頼データを生成して前記センタ端末に送信する検出依頼手段と、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データを生成して前記センタ端末に送信する検出依頼正当性証明手段と、前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証した前記センタ端末が前記確率公開鍵暗号文を復号して得た平文である統計量が属する区間を示す検出結果を生成し、前記確率公開鍵暗号文の当該平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して送信してきたときに、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証する検出結果正当性検証手段と、前記検出結果正当性検証手段の検証が成功したときに、前記センタ端末から送られてきた前記検出結果を取り出して出力する検出結果取得手段とを備えている。
【００３４】
本発明の第２の利用者端末は、被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合の大きさ、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵、センタ端末が検出結果を確率的に決定する際の確率を定める変数を、それぞれ公開情報として記憶する公開情報記憶手段と、前記公開情報を使って前記被検査データの電子透かしの検出をネットワークを通じてセンタ端末に依頼する依頼機構とを備え、前記依頼機構は、前記被検査データと前記抽出公開鍵と前記公開鍵とから、冪乗剰余積の形式を有し各指数係数に前記被検査データの要素の値を置いた確率公開鍵暗号文からなる検出依頼データを生成して前記センタ端末に送信する検出依頼手段と、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データを生成して前記センタ端末に送信する検出依頼正当性証明手段と、前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証した前記センタ端末が前記公開鍵暗号文を復号して得た平文である統計量が属する区間を確率的に決定した検出結果を生成し、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して送信してきたときに、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証する検出結果正当性検証手段と、前記検出結果正当性検証手段の検証が成功したときに、前記センタ端末から送られてきた前記検出結果を取り出して出力する検出結果取得手段とを備えている。
【００３５】
本発明の第３の利用者端末は、被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素の数、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵、前記被検査データに対して電子透かしの有無を反転させるために使う基準値とこの基準値の作成に使用した乱数、センタ端末が検出結果を確率的に決定する際の確率を定める変数を、それぞれ公開情報として記憶する公開情報記憶手段と、前記公開情報を使って前記被検査データの電子透かしの検出をネットワークを通じて前記センタ端末に依頼する依頼機構とを備え、前記依頼機構は、前記被検査データに対して電子透かしの有無を反転させて検出依頼を行うか否かを制御する反転制御情報を生成する反転制御手段と、前記被検査データと前記基準値とから、前記反転制御情報が反転を示す場合には透かしの有無を反転させた新たな被検査データを生成し、前記反転制御情報が非反転を示す場合には透かしの有無を反転させない新たな被検査データを生成する手段と、前記生成した新たな被検査データと前記抽出公開鍵と前記公開鍵とから、冪乗剰余積の形式を有し各指数係数に前記新たな被検査データを置いた確率公開鍵暗号文からなる検出依頼データを生成して前記センタ端末に送信する検出依頼手段と、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データを生成して前記センタ端末に送信する検出依頼正当性証明手段と、前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証した前記センタ端末が前記公開鍵暗号文を復号して得た平文である統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信してきたときに、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを検証する検出結果正当性検証手段と、前記検出結果正当性検証手段の検証が成功したときに、前記センタ端末から送られてきた前記検出結果と前記反転制御情報とに基づいて真の検出結果を取り出して出力する検出結果取得手段とを備えている。
【００３６】
また、本発明の第１のセンタ端末は、被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵と秘密鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵とこの抽出公開鍵に対応する抽出秘密鍵を、それぞれ生成して記憶すると共に、前記列数、前記定数、前記変更量、前記インデックス集合の大きさ、前記公開鍵、前記抽出公開鍵を、それぞれ公開情報として公開する情報設定公開手段と、ネットワークを通じて接続された利用者端末からの依頼を受けて前記被検査データの電子透かしの検出を行う検出機構とを備え、前記検出機構は、前記利用者端末が、前記被検査データと前記抽出公開鍵と前記公開鍵とを使用して冪乗剰余積の形式を有し各指数係数に前記被検査データの要素の値を置いた確率公開鍵暗号文からなる検出依頼データを生成し、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データと共に送信してきたときに、前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証し、正当性を検証した場合に限り前記検出依頼データを受理する検出依頼正当性検証手段と、受理した前記検出依頼データを復号して得た平文である、前記被検査データのパッチワークによる電子透かしにかかる統計量が属する区間を示す検出結果を生成し、前記公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信する検出結果正当性証明手段とを備えている。
【００３７】
本発明の第２のセンタ端末は、被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵と秘密鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵とこの抽出公開鍵に対応する抽出秘密鍵、センタ端末が検出結果を確率的に決定する際の確率を定める変数を、それぞれ生成して記憶すると共に、前記列数、前記定数、前記変更量、前記インデックス集合の大きさ、前記公開鍵、前記抽出公開鍵、前記変数を、それぞれ公開情報として公開する情報設定公開手段と、ネットワークを通じて接続された利用者端末からの依頼を受けて前記被検査データの電子透かしの検出を行う検出機構とを備え、前記検出機構は、前記利用者端末が、前記被検査データと前記抽出公開鍵と前記公開鍵とを使用して冪乗剰余積の形式を有し各指数係数に前記被検査データの要素の値を置いた確率公開鍵暗号文からなる検出依頼データを生成して、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記範囲を定める定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データと共に送信してきたときに、前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証し、正当性を検証した場合に限り前記検出依頼データを受理する検出依頼正当性検証手段と、受理した前記検出依頼データを復号して得た平文である、前記被検査データのパッチワークによる電子透かしにかかる統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信する検出結果正当性証明手段とを備えている。
【００３８】
本発明の第３のセンタ端末は、被検査データの列数、前記被検査データの要素の値が取り得る範囲を定める定数、透かしを入れるために被検査データの要素の値に加算あるいは減算する変更量、前記被検査データの要素のうち透かしを入れるために前記変更量を加算あるいは減算する要素を無作為に定めた同じ大きさの２つのインデックス集合、検出依頼データの暗号化に用いる確率公開鍵暗号方式における公開鍵と秘密鍵、前記被検査データからパッチワークにかかる電子透かしの統計量を抽出するための抽出公開鍵とこの抽出公開鍵に対応する抽出秘密鍵、前記被検査データに対して電子透かしの有無を反転させるために使う基準値とこの基準値の作成に使用した乱数、センタ端末が検出結果を確率的に決定する際の確率を定める変数を、それぞれ生成して記憶すると共に、前記列数、前記定数、前記変更量、前記インデックス集合の大きさ、前記公開鍵、前記抽出公開鍵、前記基準値、前記乱数、前記変数を、それぞれ公開情報として公開する情報設定公開手段と、ネットワークを通じて接続された利用者端末からの依頼を受けて前記被検査データの電子透かしの検出を行う検出機構とを備え、前記検出機構は、前記センタ端末が、前記被検査データに対して電子透かしの有無を反転させて検出依頼を行うか否かを制御する反転制御情報と前記被検査データと前記基準値とから、前記反転制御情報が反転を示す場合には透かしの有無を反転させた新たな被検査データを生成し、前記反転制御情報が非反転を示す場合には透かしの有無を反転させない新たな被検査データを生成して、前記生成した新たな被検査データと抽出公開鍵と公開鍵とから、冪乗剰余積の形式を有し各指数係数に前記被検査データを置いた確率公開鍵暗号文からなる検出依頼データを生成し、前記確率公開鍵暗号文の冪乗剰余積の各指数係数が前記定数で定まる所定の区間内に属することを証明する検出依頼正当性証明データと共に送信してきたときに、前記検出依頼データの正当性を前記検出依頼正当性証明データに基づいて検証し、正当性を検証した場合に限り前記検出依頼データを受理する検出依頼正当性検証手段と、受理した前記検出依頼データを復号して得た平文である、前記被検査データのパッチワークによる電子透かしにかかる統計量が属する区間を確率的に決定した検出結果を生成し、且つ、前記確率公開鍵暗号文の平文が前記検出結果が示す区間内に属することを証明する検出結果正当性証明データを生成して前記利用者端末へ送信する検出結果正当性証明手段とを備えている。
【００３９】
【作用】
本発明にあっては、利用者端末が検出依頼正当性証明データによって検出依頼データの正当性を証明しない限り、センタ端末は電子透かしの検出依頼を受理しないため、実際の被検査データに基づかずに特殊なデータ列に基づく不正な検出依頼を行って電子透かしの付加方法を入手しようとする悪意者からの攻撃が防御できる。また、センタ端末は検出結果の正当性を証明しなければならないために検出結果を偽ることができず、従って、利用者端末は一つの被検査データの電子透かしの検出に際して一つの検出依頼を行えば済み、電子透かしの検出に必要な手続きが効率化する。更に、センタ端末は検出結果を確率的に決定するため、透かし有りと透かし無しの閾値に近い被検査データを用いて電子透かしの付加方法を入手しようとする攻撃からも防御できる。また更に、利用者端末は被検査データに対して電子透かしの有無を反転させて検出依頼を行うか否かを秘密裏に実施するため、電子透かしの真の検出結果がセンタ端末側では分らない。
【００４０】
【発明の実施の形態】
図１を参照すると、本発明の一実施の形態は、センタ端末１０１と利用者端末１０２とで構成され、両者は公衆回線網、専用回線網あるいはインターネット等のネットワーク１０３を通じて相互に通信可能になっている。
【００４１】
利用者端末１０２は、電子透かしの検出を希望する利用者が使用する端末であり、センタ端末１０１は、利用者端末１０２からの依頼を受けて電子透かしの検出を行い、その結果を利用者端末１０１へ通知する端末である。利用者端末１０２としては、パーソナルコンピュータや携帯情報端末等の情報処理装置で実現することができる。また、センタ端末１０１としては、パーソナルコンピュータやワークステーション等の情報処理装置で実現することができる。
【００４２】
利用者端末１０２は、電子透かしの検出を行う画像や音声等のデジタルデータである被検査データを記憶する被検査データ記憶手段１１１と、オンライン検出処理に必要な情報としてセンタ端末１０１から公開された情報を、好ましくは公開情報が正当であることを確認した上で、記憶しておく公開情報記憶手段１１２と、センタ端末１に対して電子透かしの検出を依頼し、その結果を受け取る依頼機構１１３と、利用者からの指示を入力するキーボード等の入力装置および電子透かしの検出結果等の表示や出力を行う出力装置を備える出力装置１１４とを含んで構成される。
【００４３】
センタ端末１０１は、システムの運用に先立ってオンライン検出処理に必要となる各種の情報を生成し、そのうち公開すべき情報は公開情報として利用者端末１０２に公開し、秘密情報は公開情報と共にセンタ端末１０１側に保存する情報設定公開手段１２１と、この情報設定公開手段１２１で生成された秘密情報および公開情報を記憶しておく情報記憶手段１２２と、利用者端末１０２からの依頼を受けて電子透かしの検出を行い、その結果を通知する検出機構１２３とを含んで構成される。
【００４４】
そして、依頼機構１１３は、入出力装置１１４からの指示に従って被検査データの電子透かしの検出を依頼するデータ（検出依頼データ）を生成して検出機構１２３に送信する検出依頼手段１３１と、この検出依頼手段１３１で生成された検出依頼データを入力し、この検出依頼データが正当であることを証明するデータ（検出依頼正当性証明データ）を生成して検出機構１２３に送信する検出依頼正当性証明手段１３２とを備え、検出機構１２３は、依頼機構１１３から送られてきた検出依頼正当性証明データに基づいて、依頼機構１１３から送られてきた検出依頼データの正当性を検証し、その正当性が検証された場合に限って検出依頼データを受理する検出依頼正当性検証手段１４１を備えている。
【００４５】
また、検出機構１２３は、検出依頼正当性検証手段１４１で受理された依頼機構１１３からの検出依頼データを入力し、この検出依頼データに基づき、検出結果とこの検出結果が正当であることを証明するデータ（検出結果証明データ）を生成して依頼機構１１３に送信する検出結果正当性証明手段１４２を備え、依頼機構１１３は、検出機構１２３から送られてきた検出結果証明データと検出依頼手段１３１が生成した検出依頼データに基づいて、検出結果の正当性を検証する検出結果正当性検証手段１３３と、検出結果の正当性が検証された場合に検出結果を取得して入出力装置１１４に出力する検出結果取得手段１３４とを備えている。
【００４６】
更に、好ましくは、依頼機構１１３は、被検査データに対して電子透かしの有無を反転させて検出依頼を行うか否かを制御する反転制御情報を生成して検出依頼手段１３１および検出結果取得手段１３４に出力する反転制御手段１３５を備え、また、検出結果正当性証明手段１４２は、検出結果を確率的に決定する。検出結果を確率的に決定するとは、検出結果に当該検出結果が成立する確率を付与することである。電子透かしが入っていることが極めて明らかな検出依頼データおよび電子透かしが入っていないことが極めて明らかな検出依頼データにたいしては、高い確率を付与し、電子透かしが入っている、入っていないの境目に近い程、確率を小さくする。
【００４７】
記録媒体１５１、記録媒体１５２は、磁気ディスク装置、半導体メモリ、ＣＤ−ＲＯＭ等のコンピュータ可読記録媒体であり、それぞれセンタ端末用プログラム、利用者端末用プログラムが記録されている。記録媒体１５１に記録されたセンタ端末用プログラムは、センタ端末１０１を構成するコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータ上に情報設定公開手段１２１および検出機構１３１を実現する。また、記録媒体１５２に記録された利用者端末用プログラムは、利用者端末１０２を構成するコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータ上に依頼機構１１３を実現する。
【００４８】
次に図２のフローチャートを参照して本実施の形態の動作を説明する。
【００４９】
システムの運用に先立ち、センタ端末１０１の情報設定公開手段１２１は、電子透かしのオンライン検出に必要な所定の公開情報と秘密情報とを生成し、公開情報はネットワーク１０３経由で利用者端末１０２に公開し、秘密情報は公開情報と共に情報記憶手段１２２に保存する（ステップＳ１０１）。利用者端末１０２は、公開情報を受信し、公開情報記憶手段１１２に保存する（ステップＳ２０１）。利用者端末１０２の依頼機構１１３は公開情報記憶手段１１２に記憶された公開情報を使ってオンライン検出にかかる依頼側の処理を実行し、センタ端末１０１の検出機構１２３は情報記憶手段１２２に記憶された公開情報および秘密情報を使ってオンライン検出にかかる検出側の処理を実行する。図２のステップＳ２０２〜Ｓ２０８、Ｓ１０２〜Ｓ１０４は１つの被検査データに関するオンライン検出にかかる処理の流れを示している。検出の依頼は、例えば利用者が入出力装置１１４から被検査データを指定して電子透かし検出を指示したときに開始される。
【００５０】
先ず、依頼機構１１３の反転制御手段１３５は、検出依頼を行うか否かを制御する反転制御情報を無作為に生成して検出依頼手段１３１および検出結果取得手段１３４に出力する（ステップＳ２０２）。次に、検出依頼手段１３１は、被検査データの電子透かしの検出を依頼するデータ（検出依頼データ）を生成し、ネットワーク１０３経由で検出機構１２３に送信する（ステップＳ２０３）。このとき検出依頼手段１３１は、反転制御手段１３５で生成された反転制御情報が反転を示す場合には、被検査データに対して電子透かしの有無を反転させて検出依頼データを生成し、反転制御情報が非反転を示す場合には、被検査データに対して電子透かしの有無を反転させずに検出依頼データを生成する。次に、検出依頼正当性証明手段１３２は、検出依頼手段１３１による検出依頼データが正当な被検査データに基づいて生成されたデータであることを証明する検出依頼正当性証明データを生成し、ネットワーク１０３経由で検出機構１２３に送信する（ステップＳ２０４）。ここでは、検出依頼データと検出依頼正当性証明データとを別々に送信したが、同時に送信するようにしても良い。
【００５１】
センタ端末１０１の検出機構１２３における検出依頼正当性検証手段１４１は、検出依頼データと検出依頼正当性証明データの組が揃った検出依頼に関し、検出依頼正当性証明データに基づいて検出依頼データの正当性を検証する（ステップＳ１０２）。そして、検出依頼データの正当性が検証された場合（ステップＳ１０３でＹＥＳ）、当該検出依頼を受理し、後続の処理を続行する。他方、正当性が検証されなかった場合には当該検出依頼を拒否する（ステップＳ１０５）。
【００５２】
検出依頼を受理した場合、検出機構１２３の検出結果正当性証明手段１４２は、検出依頼データに基づき、検出結果とこの検出結果が正当であることを証明する検出結果証明データを生成し、ネットワーク１０３経由で依頼機構１１３に送信する（ステップＳ１０４）。このとき検出結果正当性証明手段１４２は、検出結果を確率的に決定する。依頼機構１１３の検出結果正当性検証手段１３３は、検出機構１２３から送られてきた検出結果証明データと検出依頼手段１３１が生成しセンタ端末１０１へ送信した検出依頼データに基づいて、検出結果の正当性を検証し（ステップＳ２０５）、正当であると判断した場合（ステップＳ２０６でＹＥＳ）、検出結果取得手段１３４が検出結果を取得して入出力装置１１４に出力する（ステップＳ２０７）。このとき検出結果取得手段１３４は、反転制御手段１３５で生成された反転制御情報が反転を示す場合には、検出機構１２３の検出結果とは反対の検出結果を生成し、反転制御情報が非反転を示す場合には、検出機構１２３の検出結果と同じ検出結果を生成する。他方、検出機構１１３の検出結果が正当でないと判断した場合（ステップＳ２０６でＮＯ）、検出結果取得手段１３４はその旨のエラーメッセージを入出力装置１１４に出力する（ステップＳ２０８）。
【００５３】
このように本実施の形態では、検出依頼正当性証明データによって検出依頼データの正当性を利用者端末１０２側が証明しない限り、センタ端末１０１は電子透かしの検出依頼を受理しない。このため、実際の被検査データに基づかずに特殊なデータ列に基づく不正な検出依頼を行って電子透かしの付加方法を入手しようとする悪意者からの攻撃を防御することができる。
【００５４】
また、センタ端末１０１は検出結果の正当性を証明しなければならないため、検出結果を偽ることができない。このため、利用者は一つの被検査データの電子透かしの検出に際して一つの検出依頼を行えば済み、センタ端末１０１も一つの検出依頼を処理すれば足りる。つまり、文献１の従来技術のように数多くの依頼を出す必要がなくなり、電子透かしの検出に必要な手続きを効率化することができる。
【００５５】
また、検出結果正当性証明手段１４２は、検出結果を確率的に決定するため、透かし有りと透かし無しの閾値に近い被検査データを用いて電子透かしの付加方法を入手しようとする攻撃に対しても防御できる。
【００５６】
また、反転制御手段１３５により生成された反転制御情報が反転を示すか、非反転を示すかはセンタ端末２には分らないため、電子透かしの真の検出結果はセンタ端末１０１側には分らない。
【００５７】
【実施例】
次に、文献１の従来技術と同様に、パッチワークを用いた電子透かしを確率公開鍵暗号方式を用いて検出する場合に本実施の形態を適用した実施例について詳細に説明する。
【００５８】
（１）情報設定公開手段１２１
情報設定公開手段１２１は、以下に列挙するようなデータを生成する。
【００５９】
○被検査データの列数ｍ。被検査データが静止画の場合、画素数に相当する。
【００６０】
○被検査データの要素の値が取り得る正規な範囲［０、Ｒ］を定める定数Ｒ。被検査データが静止画であり、各要素が画素の輝度に対応する場合、輝度の取り得る範囲に相当する。
【００６１】
○透かしを入れるために被検査データの要素の値に加算或いは減算する変更量δ。
【００６２】
○変更量δを加算する要素と減算する要素を定める同じ大きさｋの２つのインデックス集合Ｉ１、Ｉ２。ここで、インデックス集合Ｉ１、Ｉ２は、Ｉ１、Ｉ２⊆Ｚ／ｍＺ、Ｉ１∩Ｉ２＝Φを満たす。また、０＜ｋ＜ｍ／２である。ｋが大きいほど、透かしを入れる過程で変更量δが加算ないし減算される要素数が増えるためデータの質が損なわれ易いが、透かしの改竄は難しくなる。
【００６３】
○検出依頼データの暗号化に使う公開鍵ｎ、ｇと秘密鍵λ。ここで、検出依頼データの暗号化方式には確率公開鍵暗号方式を用いる。例えば、Paillierの方式を用いる場合、２つの大きな素数ｐ，ｑを生成し、公開鍵ｎ＝ｐｑ，秘密鍵λ＝ｌｃｍ（ｐ−１，ｑ−１）とする。また、関数Ｌ（ｔ）＝（ｔ−１）／ｎを用いて、ｇｃｄ（Ｌ（ｇλmod n2），ｎ）＝１を満たす任意の数ｇ∈（Ｚ／ｎ２Ｚ）＊を選び、公開鍵ｇとする。
【００６４】
○被検査データからパッチワークにかかる電子透かしの統計量を依頼側で抽出するための抽出公開鍵ｅｉ、この抽出公開鍵に対応する抽出秘密鍵βｉ。ここで、暗号化方式には確率公開鍵暗号方式を用いる。抽出秘密鍵βｉは、ｉ＝１、…、ｍに関して、一様無作為にβｉ∈Ｚ／λＺとして生成される。また、抽出公開鍵ｅｉは、次式により生成される。
【数１０】
0004092920.tif 000010
【００６５】
○被検査データに対して電子透かしの有無を反転させるために使う基準値ｙｉおよびこの基準値ｙｉの作成に使用した乱数ｒ。基準値ｙｉは、ある乱数ｒに関して、次式を満たすように生成される。ここで、基準値Ｙ（ｙ１、…、ｙｍ）は、その統計量（すなわち透かし）が、透かし有りと判定される統計量と透かし無しと判定される統計量との、ちょうど境界の値を示すデータ列である。
【数１１】
0004092920.tif 000011
【００６６】
○検証結果正当性証明手段１４２が検出結果を確率的に決定する際の確率を定める変数Θ。変数Θは、０＜Θ＜δを満たす。
【００６７】
情報設定公開手段１２１は、上記の情報を情報記憶手段１２２に記憶し、そのうち、δ、Θ、ｍ、Ｒ、ｋ、ｎ、ｇ、ｅｉ、ｙｉ、ｒを公開情報として公開し、ｐ、ｑ、λ、Ｉ１、Ｉ２、βｉは秘密情報として秘密にする（ステップＳ１０１）。利用者端末１０２は、上記の公開情報を受信し、公開情報記憶手段１１２に記憶する（ステップＳ２０１）。
【００６８】
（２）反転制御手段１３５
反転制御手段１３５は、反転制御情報として１ビットの値ｂを、無作為にｂ∈｛０、１｝として生成し、検出依頼手段１３１および検出結果取得手段１３４に出力する（ステップＳ２０２）。ｂが０か１かで、被検査データの透かしの有無を反転させるかどうかが制御される。
【００６９】
（３）検出依頼手段１３１
検出依頼手段１３１は、数１１が成立することを検証した後、被検査データ記憶手段１１１に記憶されている被検査データをＸ（ｘ１、…、ｘｍ）、ｘｉ∈［０、Ｒ］とすると、センタ端末１０１から公開されている基準値ｙｉと反転制御情報ｂの値とから、以下のような計算を行うことにより、新たな被検査データＣ（ｃ１、…、ｃｍ）を生成する。つまり、反転制御情報ｂが０とのきは透かしの有無を反転させない被検査データｃｉを生成し、ｂが１のときは透かしの有無を反転させた被検査データｃｉを生成する。
【数１２】
0004092920.tif 000012
【００７０】
次に検出依頼手段１３１は、被検査データｃｉ、抽出公開鍵ｅｉ、公開鍵ｎを使用して以下のような確率公開鍵暗号文ｅを生成し、センタ端末１０１へ送信する（ステップＳ２０３）。この確率公開鍵暗号文ｅは、冪乗剰余積の形式を有し、各指数部の基数が抽出公開鍵ｅｉ、各指数係数が被検査データｃｉになっている。
【数１３】
0004092920.tif 000013
【００７１】
（４）検出依頼正当性証明手段１３２
検出依頼正当性証明手段１３２は、検出依頼手段１３１による検出依頼データである上記の確率公開暗号文ｅが正当な被検査データから生成されたものであることを証明する検出依頼正当性証明データを生成し、検出機構１２３に送信する（ステップＳ２０４）。具体的には、上記の確率公開暗号文ｅの冪乗剰余積の各指数係数ｃｉが［−Ｒ、Ｒ］の区間内にあることを各指数係数ｃｉの値を隠したまま証明するデータを生成する。各指数係数ｃｉの値を隠したまま証明するのは、各指数係数ｃｉの値が分ると被検査データがセンタの知るところとなり、利用者のプライバシーが侵害されるからである。ここで、ｙｉ∈［０、Ｒ］であるため、ｃｉ∈［−Ｒ、Ｒ］であれば、ｘｉ∈［−Ｒ−ｙｉ、Ｒ＋ｙｉ］⊆［−２Ｒ、２Ｒ］であることが保証される。ｘｉ∈［０、Ｒ］であることが保証されれば好ましいが、ｘｉの値が異常に大きくないことが保証できれば防御可能なので、この条件でも充分である。確率公開鍵暗号文の冪乗剰余積の各指数係数が所定の区間内にあることの証明方法の詳細については後述する。
【００７２】
（５）検出依頼正当性検証手段１４１
検出依頼正当性検証手段１４１は、上記の数１３に示す検出依頼データとその証明データとを利用者端末１０２から受信すると、その証明データに基づき、上記の数１３の確率公開暗号文ｅの冪乗剰余積の各指数係数ｃｉが全て［−Ｒ、Ｒ］の区間内に属することを検証する（ステップＳ１０２）。そして、検証に失敗した場合、利用者端末１０２からの今回の検出依頼を拒否する（ステップＳ１０５）。確率公開暗号文の冪乗剰余積の各指数係数が所定の区間内にあることの検証方法の詳細については後述する。
【００７３】
（６）検証結果正当性証明手段１４２
検証結果正当性証明手段１４２は、検証依頼正当性検証手段１４１で正当であると検証された数１３の確率公開暗号文ｅをλ、ｎ、ｇを用いて復号する。この復号により求められる平文が、被検査データｃｉのパッチワークにより電子透かしにかかる統計量ｗとなる。
【００７４】
次に検証結果正当性証明手段１４２は、この統計量ｗと、ｋ、δ、Θとから、検出結果を以下のように確率的に決定し、この検出結果が依頼を受けた検出依頼データの検出結果として正当であることを証明する検出結果正当性証明データを作成して利用者端末１０２へ送信する（ステップＳ１０４）。
○Θ＜ｗ＜２ｋδならば、確率１でｗ∈［−Θ、２ｋσ］であること。
○−２ｋσ＜ｗ＜−Θならば、確率１でｗ∈［−２ｋσ、Θ］であること。
○−Θ＜ｗ＜Θならば、｛ｗ＋Θ｝／２Θの確率でｗ∈［−Θ、２ｋσ］であり、かつ、｛Θ−ｗ｝／２Θの確率でｗ∈［−２ｋδ、Θ］であること。
【００７５】
上記の検出結果の証明は、統計量ｗを秘密にしたままで行う。統計量ｗが利用者の知るところとなると、透かしの付加方法が漏れるからである。このため、検出依頼データの確率公開鍵暗号文の平文（統計量）が検出結果の示す区間内であることを証明する証明方法を使用する。確率公開鍵暗号文の平文が所定の区間内にあることの証明方法の詳細は後述する。
【００７６】
（７）検証結果正当性検証手段１３３
検証結果正当性検証手段１３３は、検証結果正当性証明手段１４２から受信した検証結果正当性証明データに基づき、検出依頼データの確率公開鍵暗号文の平文（統計量）ｗが、ｗ∈［−Θ、２ｋσ］であること、またはｗ∈［−２ｋσ、Θ］であることを検証する（ステップＳ２０５）。前述したように統計量ｗが秘密にされているため、この検証は、センタから送られてきた検出結果正当性証明データを用いて、統計量ｗを平文とする確率公開鍵暗号文の平文が検出結果が示す区間内にあることを検証することにより行う。確率公開鍵暗号文の平文が所定の区間内にあることの検証方法の詳細は後述する。
【００７７】
（８）検出結果取得手段１３４
検出結果取得手段１３４は、ｗ∈［−Θ、２ｋσ］である場合、反転制御情報ｂ＝０ならば電子透かし有り、ｂ＝１ならば電子透かし無しと判断し、ｗ∈［−２ｋσ、Θ］である場合、ｂ＝０ならば電子透かし有り、ｂ＝１ならば電子透かし無しと判断する。そして、この検出結果を入出力装置１１４へ出力する（ステップＳ２０７）。
【００７８】
次に本実施例の効果を説明する。
【００７９】
前述したように文献１に記載の従来技術では、利用者が不正な暗号文を生成することで、センタの秘密情報であるインデックス集合Ｉ1、Ｉ２を入手できる問題点があった。しかし、本実施例においては、検出依頼データである数１３の確率公開鍵暗号文ｅの冪乗剰余積の各指数係数ｃｉが所定の区間内にあることを利用者側が証明しなければならないため、実際の被検査データＸに基づかずに特殊なデータ列に基づく不正な検出依頼による攻撃は不可能となる。但し、このような証明を利用者に課すと、利用者は任意の暗号文を生成できないためセンタの不正を防ぐ方法として複数の暗号文をセンタに送る文献１に記載の従来技術の方法は使え無くなる。
【００８０】
そこで、本実施例では、検出結果が正当であることをセンタに証明させることでセンタの不正を防止している。ここで、センタが確率公開鍵暗号文ｅの復号および暗号化のための乱数を明示して検出結果を証明することも考えられるが、これは次のような攻撃を許すことになる。利用者が２回の検出依頼で、下記の２つの暗号文をセンタに送れば、それらの復号結果の差からｉの属するインデックス集合を知ることができる。
【数１４】
0004092920.tif 000014
そこで、本実施例では、統計量が閾値を超えているか否かのみを、センタが利用者に統計量を秘密にしたまま証明する方法を採用している。
【００８１】
上記のような対策を施しても、なお統計量が閾値に近い被検査データ（透かしが入っている被検査データから容易につくれる）を用いれば、下記の２つの暗号文の検出結果を比較することにより、ｉの属するインデックス集合を高い確率で知ることができる（ｊ∈Ｉ１の場合、左式の検出結果が０で、右式の検出結果が１となる可能性を無視できない）。
【数１５】
0004092920.tif 000015
【００８２】
そこで本実施例では、検出結果が閾値に近ければ、センタは検出結果を確率的に決定することにより、上記の如き攻撃からインデックス集合を隠している。これにより、左式からと右式からの検出結果の分布が大きく異なるようなＸを存在しなくできる。
【００８３】
また、本実施例では一つの被検査データについて一つの検出依頼データだけをセンタに送るため、センタはその検出依頼データから求めた統計量から検出結果を知ることができ、利用者のプライバシーが侵害される。そこで、本実施例では、センタが統計量を知ったとしても真の検出結果がセンタに分らないようにするために、利用者側でのみ知りうる反転制御情報に応じて被検査対象データの電子透かしの有無を反転させてセンタに依頼するようにしている。
【００８４】
［検出依頼証明の詳細］
次に、検出依頼正当性証明手段１３２で利用可能な、確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを証明する証明方法と、検出依頼正当性検証手段１４１で利用可能な、確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを検証する検証方法の一例について説明する。
【００８５】
図３は確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを証明する証明文を作成する証明文作成装置の一例を示すブロック図であり、図４と図５と図６はこの証明文作成装置による証明文の作成処理を説明するためのフローチャートである。
【００８６】
本実施の形態の確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることの証明方法は、秘密鍵により平文と暗号化に用いられた乱数との両方を求めることのできる確率公開鍵暗号方式による暗号文を用いる。また以下、暗号化する平文は数値データであり、またこれを暗号化した暗号文もまた数値データを成すものとして説明する。
【００８７】
図３を参照すると、本実施の形態の証明文作成装置は、証明文の作成に用いる各種データを人力するための入力部２０１と、入力されたデータに基づき演算を行ない証明文を作成する演算処理部２０２と、作成された証明文２０４を出力する出力部２０３を備えている。本実施の形態における証明文２０４は、証明対象である冪乗剰余積２２１と、平方数の証明文２２３、２２５と、絶対値の大きさの証明文２２２、２２４とから構成されている。
【００８８】
また、演算処理部２０２は、冪乗剰余積生成部２１１と証明文生成部２１２とを備え、証明文生成部２１２は、両端値との差の列の生成部２３１と、拡大部２３２と、分解部２３３と、平方数の証明部２３４と、絶対値の大きさの証明部２３５とを含んでいる。更に、平方数の証明部２３４は、暗号化部２４１と、冪乗剰余積生成部２４２と、乱数の冪乗剰余積生成部２４３と、挑戦値生成部２４４と、応答生成部２４５と、大きさ確認部２４６と、乱数生成部２４７とを有している。また、絶対値の大きさの証明部２３５は、暗号化部２５１と、冪乗剰余積生成部２５２と、挑戦値生成部２５３と、応答生成部２５４と、大きさ確認部２５５と、乱数生成部２５６とを有している。
【００８９】
図４を参照すると、本実施の形態の証明文の作成処理では、まず入力部２０１が証明に必要な各種の情報として、確率公開鍵暗号方式の公開鍵２０５であるｎ、ｇと、指定された区間を定める変数２０６である上限値ａおよび下限値ｂと、確率公開鍵暗号文の列２０７であるｅｉ（ｉ＝１、…、ｍ）と、指数係数の列２０８であるｗｉ（ｉ＝１、…、ｍ）と、正しく検証される確率を規定する安全変数２０９とを入力する（ステップＳ３０１）。
【００９０】
次いで、演算処理部２０２の冪乗剰余積生成部２１１が、確率公開鍵暗号方式の公開鍵２０５と確率公開鍵暗号文の列２０７と指数係数の列２０８とから、確率公開鍵暗号文の列２０７の指数係数の列２０８による冪乗剰余積ｅ＝Πi=1mｅ^{ｗi}mod n2を証明対象の冪乗剰余積２２１として生成する（ステップＳ３０２）。次に、証明文生成部２１２が、証明対象の冪乗剰余積の各指数係数の値が区間を定める変数２０６で指定された区間内にあることを証明するための証明文２２２〜２２５を作成する（ステップＳ３０３）。そして、出力部２０３が、証明対象の冪乗剰余積２２１と証明文２２２〜２２５とを含む証明文２０４を出力する（ステップＳ３０４）。
【００９１】
なお、本実施の形態では、証明対象の冪乗剰余積２２１を証明文作成装置で生成しているが、証明対象の冪乗剰余積が外部から入力される場合には生成する必要はない。また、本実施の形態では、証明文２０４に証明対象の冪乗剰余積２２１を含めたが、必ずしも含める必要はない。
【００９２】
証明文生成部２１２が証明文を生成するステップＳ３０３の詳細は、図４のステップＳ３０３内に示されている。
【００９３】
図４のステップＳ３０３内のフローチャートを参照すると、先ず両端値との差の列の生成部２３１が、指数係数の列２０８と区間を定める変数２０６が示す下限値aとの差の列wi-a;(i=1、…、m)と、指数係数の列２０８と区間の上限値bとの差の列b-wi;(i=1、…、m)とを生成する（ステップＳ３１１）。
【００９４】
次に拡大部２３２が、これらの差の列に安全変数２０９及び区間を定める値a、bにより定められる値Uを乗じて、拡大された下限値との差の列U(wi-a)と、拡大された上限値との差の列U(b-wi)とを生成する（ステップＳ３１２）。
【００９５】
次に分解部２３３が、この拡大された差の列それぞれに対して、それぞれその値より小さい最大の平方数の列w[i1]2、w'[i1]2;(i=1、…、m)をそれぞれ求め、下記のような拡大された差の列それぞれと、それぞれに対応する平方数との差の列をそれぞれ求める（ステップＳ３１３）。
w[i2]=U(wi-a)-w[i1]2、w'[i2]=U(b-wi)-w'[i1]2;(i=1、…、m)
【００９６】
次に平方数の証明部２３４が、確率公開鍵暗号文の列eiの下限値ａに対応する平方数の列w[i1]2による冪乗剰余積e[1]=Πi=1mei^{w[i1]2}modn2と、確率公開鍵暗号文の列eiの上限値ｂに対応する平方数の列w'[i1]2による冪乗剰余積e'[1]=Πi=1mei^{w'[i1]2}modn2を求め、両冪乗剰余積e[1]、e'[1]を生成した係数w[i1]2、w'[i1]2;(i=1、…、m)が平方数であることと、その平方根w[i1]、w'[i1]が安全変数と区間を定める定数で定められる値Vを超えないこととの、平方数の証明文２２３、２２５を生成する（ステップＳ３１４）。上記の冪乗剰余積e[1]は、平方数の証明文２２３の１要素になり、上記の冪乗剰余積e'[1]は、平方数の証明文２２５の１要素となる。
【００９７】
次に絶対値の大きさの証明部２３５が、確率公開鍵暗号文の列eiの下限値ａに対応する平方数との差の列w[i2]による冪乗剰余積e[2]=Πi=1mei^{w[i2]}modn2と、確率公開鍵暗号文の列eiの上限値ｂに対応する平方数との差の列w'[i2]による冪乗剰余積e'[2]=Πi=1mei^{w'[i2]}modn2とを求め、両冪乗剰余積e[2]、e['[2]を生成した係数w[i2]、w'[i2];(i=1、…、m)の絶対値が、安全変数２０９と区間の広さから定められる定数Uより小さいことの、絶対値の大きさの証明文２２２、２２４を生成する（ステップＳ３１５）。上記の冪乗剰余積e[2]は、絶対値の大きさの証明文２２２の１要素になり、上記の冪乗剰余積e'[2]は、絶対値の大きさの証明文２２４の１要素になる。
【００９８】
平方数の証明ステップであるステップＳ３１４の詳細を図５のフローチャートを参照して説明する。
【００９９】
先ず暗号化部２４１が、暗号文でもある前記冪乗剰余積e[1]とe'[1]を生成する（ステップＳ４０１）。
【０１００】
次に乱数生成部２４７が、下限値ａに対応する乱数列v[i1];(i=1、…、m)と上限値ｂに対応する乱数列v'[i1]を生成し、冪乗剰余積生成部２４２が、下限値ａに対応する前記平方数の列の各要素の平方根w[i1]と前記乱数列v[i1]の各要素と2とを乗じた数列2v[i1]w[i1];(i=1、…、m)による、前記暗号文の列eiの冪乗剰余積e[11]=Πi=1mei^{2v[i1]w[i1]}modn2と、上限値ｂに対応する前記平方数の列の各要素の平方根w'[i1]と前記乱数列v'[i1]の各要素と2とを乗じた数列2v'[i1]w'[i1];(i=1、…、m)による、前記暗号文の列eiの冪乗剰余積e'[11]=Πi=1mei^{2v'[i1]w'[i1]}modn2とを生成する（ステップＳ４０２）。ここで生成した冪乗剰余積e[11]は、平方数の証明文２２３の１要素になり、冪乗剰余積e'[12]は、平方数の証明文２２５の１要素になる。
【０１０１】
次に乱数の冪乗剰余積生成部２４３が、下限値ａに対応する前記乱数列v[i1]の各要素の平方の数列v[i1]2;(i=1、…、m)による、前記暗号文の列eiの冪乗剰余積e[12]=Πi=1mei^{v[i1]2}modn2と、上限値ｂに対応する前記乱数列v'[i1]の各要素の平方の数列v'[i1]2;(i=1、…、m)による、前記暗号文の列eiの冪乗剰余積e'[12]=Πi=1mei^{v'[i1]2}modn2とを生成する（ステップＳ４０３）。ここで生成した冪乗剰余積e[12]は、平方数の証明文２２３の１要素になり、冪乗剰余積e'[12]は、平方数の証明文２２５の１要素になる。
【０１０２】
次に挑戦値生成部２４４が、公開鍵n、g、前記暗号文の列ei、前記冪乗剰余積e[1]、前記冪乗剰余積e[11]および前記冪乗剰余積e[12]を入力に含むハッシュ関数の出力である下限値ａに対応する挑戦値c[1]と、公開鍵n、g、前記暗号文の列eI、前記冪乗剰余積e'[1]、前記冪乗剰余積e'[11]および前記冪乗剰余積e'[12]を入力に含むハッシュ関数の出力である上限値ｂに対応する挑戦値c'[1]とを生成する（ステップＳ４０４）。
【０１０３】
次に応答生成部２４５が、下限値ａに対応する前記乱数列の各要素v[i1]と、前記平方数の列の各要素の平方根w[i1]と下限値に対応する挑戦値c[1]の積の列との、和の列である下限値に対応する応答r[i1]=v[i1]+c[1]w[i1];(i=1、…、m)と、上限値に対応する前記乱数列の各要素v'[i1]と、前記平方数の列の各要素の平方根w'[i1]と上限値に対応する挑戦値c'[1]の積の列との、和の列である上限値に対応する応答r'[i1]=v'[i1]+c'[1]w'[i1];(i=1、…、m)とを生成する（ステップＳ４０５）。ここで生成された応答r[i1]は、平方数の証明文２２３の１要素になり、応答r'[i1]は、平方数の証明文２２５の１要素になる。
【０１０４】
次に大きさ確認部２４６が、前記応答r[i1];(i=1、…、m)の要素全てが、安全変数と区間の大きさ|b-a|と挑戦値c[1]より定められる定数により定められる或る区間Rの中にないか、前記応答r'[i1];(i=1、…、m)の要素全てが、安全変数と区間の大きさ|b-a|と挑戦値c'[1]より定められる定数により定められる或る区間R'の中になければ、平方数の証明ステップＳ３１４を最初からやり直すように制御する。そうでなければ、平方数の証明ステップを完了する。
【０１０５】
絶対値の大きさの証明ステップであるステップＳ３１５の詳細を図６のフローチャートを参照して説明する。
【０１０６】
まず暗号化部２５１が、暗号文でもある前記冪乗剰余積e[2]とe'[2]を生成する（ステップＳ５０１）。この生成された冪乗剰余積e[2]は、絶対値の大きさの証明文２２２の１要素になり、冪乗剰余積e'[2]は、絶対値の大きさの証明文２２４の１要素になる。
【０１０７】
次に乱数生成部２５６が、下限値ａに対応する乱数列v[i2];(i=1、…、m)と上限値ｂに対応する乱数列v'[i2]を生成し、下限値ａに対応する前記乱数列v[i2];(i=1、…、m)による、前記暗号文の列eiの冪乗剰余積e[21]=Πi=1mei^{v[i2]}modn2と、上限値ｂに対応する前記乱数列v'[i2];(i=1、…、m)による、前記暗号文の列eiの冪乗剰余積e'[21]=Πi=1mei^{v'[i2]}modn2とを生成する（ステップＳ５０２）。この生成された冪乗剰余積e[21]は、絶対値の大きさの証明文２２２の１要素になり、冪乗剰余積e'[21]は、絶対値の大きさの証明文２２４の１要素になる。
【０１０８】
次に挑戦値生成部２５３が、公開鍵n、g、前記暗号文の列eｉ、前記冪乗剰余積e[2]および前記冪乗剰余積e[21]を入力に含むハッシュ関数の出力である下限値ａに対応する挑戦値c[2]と、公開鍵n、g、前記暗号文の列eI、前記冪乗剰余積e'[2]および前記冪乗剰余積e'[21]を入力に含むハッシュ関数の出力である上限値ｂに対応する挑戦値c'[2]とを生成する（ステップＳ５０３）。
【０１０９】
次に応答生成部２５４が、下限値ａに対応する前記乱数列の各要素v[i2]と、前記平方数との差の列w[i2];(i=1、…、m)と下限値ａに対応する挑戦値c[2]の積の列との、和の列である下限値ａに対応する応答r[i2]=v[i2]+c[2]w[i2];(i=1、…、m)と、上限値ｂに対応する前記乱数列の各要素v'[i2]と、前記平方数との差の列w'[i2];(i=1、…、m)と上限値に対応する挑戦値c'[2]の積の列との、和の列である上限値に対応する応答r'[i2]=v'[i2]+c'[2]w'[i2];(i=1、…、m)とを生成する（ステップＳ５０４）。この生成された応答r[i2]は、絶対値の大きさの証明文２２２の１要素になり、応答r'[i2]は、絶対値の大きさの証明文２２４の１要素になる。
【０１１０】
次に大きさ確認部２５５が、前記応答r[i2];(i=1、…、m)の要素全てが、安全変数と区間の大きさ|b-a|と挑戦値c[2]より定められる定数により定められる区間Sの中にないか、前記応答r'[i2];(i=1、…、m)の要素全てが、安全変数と区間の大きさ|b-a|と挑戦値c'[2]より定められる定数により定められる区間S'の中になければ、絶対値の大きさの証明ステップＳ３１５を最初からのやり直すように制御する。そうでなければ、絶対値の大きさの証明ステップを完了する。
【０１１１】
図７は確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを検証する検証装置の一例を示すブロック図であり、図８と図９と図１０はこの検証装置による検証処理を説明するためのフローチャートである。
【０１１２】
図７を参照すると、本実施の形態の検証装置は、検証に必要な各種データを人力するための入力部３０１と、入力されたデータに基づき演算を行ない証明文を作成する演算処理部３０２と、得られた検証結果３０４を出力する出力部３０３を備えている。
【０１１３】
また、演算処理部３０２は検証部３１１を備え、検証部３１１は、分割検証部３２１と、平方数の検証部３２２と、絶対値の大きさの検証部３２３と、結果まとめ部３２４とを含んで構成される。さらに、平方数の検証部３２２は、挑戦値生成部３３１と、復号部３３２と、乱数生成部３３３と、大きさ確認部３３４と、２次式による検証部３３５とを含み、絶対値の大きさの検証部３２３は、挑戦値生成部３４１と、復号部３４２と、乱数生成部３４３と、大きさ確認部３４４と、１次式による検証部３４５を含んでいる。
【０１１４】
図８を参照すると、本実施の形態の検証処理では、まず入力部３０１が検証に必要な各種の情報として、区間を定める変数２０６である上限値bおよび下限値aと、確率公開鍵暗号方式の公開鍵２０５であるn、gと、確率公開鍵暗号方式の秘密鍵３０５であるλと、安全変数２０９と、m個の確率公開鍵暗号文の列ei=g^{αi}g^{nβi}modn2;(i=1、…、m)の平文の列３０６であるαi;(i=1、…、m)と、前記暗号文の列ei;(i=1、…、m)の暗号化に使われた乱数の列３０７であるβi;(i=1、…、m)と、前記暗号文の列ei=g^{αi}g^{nβi}modn2;(i=1、…、m)の、前記暗号文の列の指数係数の列wi;(i=1、…、m)による冪乗剰余積２２１であるe=Πi=1mei^{wi}modn2およびこの確率公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることを証明する証明文２２２〜２２５を含む証明文２０４とを入力する（ステップＳ６０１）。ここで、証明文２２２〜２２５は以下の要素で構成されている。
○平方数の証明文２２３；
暗号文ｅ［1］、２個の冪乗剰余積ｅ［11］、ｅ［12］、応答ｒ［i1］
○平方数の証明文２２５；
暗号文ｅ'［1］、２個の冪乗剰余積ｅ'［11］、ｅ'［12］、応答ｒ'［i1］
○絶対値の大きさの証明文２２２；
暗号文ｅ［2］、１個の冪乗剰余積ｅ［21］、応答ｒ［i2］
○絶対値の大きさの証明文２２4；
暗号文ｅ'［2］、１個の冪乗剰余積ｅ'［21］、応答ｒ'［i2］
【０１１５】
なお、本実施の形態では、証明文２０４に検証対象となる冪乗剰余積２２１が含まれているが、検証対象となる冪乗剰余積２２１とその証明文２２２〜２２５を分け、証明文２０４に冪乗剰余積２２１を含ませないようにしても良い。
【０１１６】
次いで演算処理部３０２の検証部３１１が、入力された情報に基づいて、検証対象である冪乗剰余積eを生成するのに使った指数係数の列wi;(i=1、…、m)が区間の下限値aと区間の上限値bとの間[a、b]にあるか否かを判定し、当該区間にあれば証明受理の検出結果３０４を生成し、そうでなければ証明不受理の検出結果３０４を生成し（ステップＳ６０２）、出力部３０３がこの検出結果３０４を出力する（ステップＳ６０３）。
【０１１７】
検証部３１１の検証ステップＳ６０２の詳細は、図８のステップＳ６０２内に示されている。
【０１１８】
図８のステップＳ６０２内のフローチャートを参照すると、検証ステップでは、まず分割検証部が以下のような分割の検証を行う（ステップＳ６１１）。まず前記暗号文の列ei;(i=1、…、m)の全ての要素の積に区間の下限値aを乗じた値(Πi=1mei)a=g^{aΣi=1m(αi+nβi)}modn2を求め、この値で、前記冪乗剰余積eを法n2の元で割り、それを安全変数及び区間の大きさより定めらる定数Uを使って拡大した値E=e^U/(Πi=1mei)^{aU}=e^U/g^{UaΣi=1m(αi+nβi)}modn2を求める。そして、この拡大した値Eが、証明文２０４に含まれる下限値ａに対応する平方数の列による冪乗剰余積e[1]と下限値ａに対応する平方数との差の列による冪乗剰余積e[2]との積に等しいか否かを確認する。
【０１１９】
また、前記暗号文の列ei;(i=1、…、m)の全ての要素の積に区間の上限値bを乗じた値(Πi=1mei)b=g^{bΣi=1m(αi+nβi)}modn2を求め、この値を、前記冪乗剰余積eで法n2の元で割り、それを安全変数及び区間の大きさより定めらる定数Uを使って拡大した値E'=(Πi=1mei)^{bU}/e^Ug^{UbΣi=1m(αi+nβi)}/e^Umodn2を求める。そして、この拡大した値E'が、証明文２０４に含まれる上限値ｂに対応する平方数の列による冪乗剰余積e'[1]と上限値ｂに対応する平方数との差の列による冪乗剰余積e'[2]との積に等しいか否かを確認する。
【０１２０】
分割検証部３２１は、前記二つの確認ができれば、分割の検証受理を出力する。
【０１２１】
次に平方数検証部３２２が平方数の検証を以下のように行う（ステップＳ６１２）。まず、下限値ａに対応する平方数の列による冪乗剰余積e[1]を生成した列w[i1]2;(i=1、…、m)の各要素が、平方数であることと、その平方根w[i1];(i=1、…、m)が安全変数と区間を定める定数で定められた前記値Vを超えないことを検証する。また、上限値ｂに対応する平方数の列による冪乗剰余積e'[1]を生成した列w'[i1]2;(i=1、…、m)の各要素が、平方数であることと、その平方根w'[i1];(i=1、…、m)が前記Vを超えないことを検証する。そして、前記二つの検証ができれば平方数の検証受理を出力する。
【０１２２】
次に絶対値の大きさ検証部３２３が、以下のようにして絶対値の大きさを検証する（ステップＳ６１３）。まず下限値ａに対応する前記平方数との差の列による冪乗剰余積e[2]を生成した列w[i2];(i=1、…、m)の各要素が、Uを超えないことを検証する。次に、上限値ｂに対応する平方数との差の列による冪乗剰余積e'[2]を生成した列w'[i2];(i=1、…、m)の各要素が、Uを超えないことを検証する。この二つの検証ができれば、絶対値の大きさの検証受理を出力する。
【０１２３】
平方数の検証ステップであるステップＳ６１２の詳細を図９のフローチャートを参照して説明する。
【０１２４】
まず挑戦値生成部３３１が、公開鍵n、g、暗号文の列eｉ、冪乗剰余積e[1]、冪乗剰余積e[11]および冪乗剰余積e[12]を入力に含むハッシュ関数の出力である下限値ａに対応する挑戦値c[1]と、公開鍵n、g、暗号文の列eｉ、冪乗剰余積e'[1]、冪乗剰余積e'[11]および冪乗剰余積e'[12]を入力に含むハッシュ関数の出力である上限値ｂに対応する挑戦値c'[1]との２つの挑戦値を生成する（ステップＳ７０１）。
【０１２５】
次に復号部３３２が、暗号文でもある冪乗剰余積e[1]とe'[1]と、暗号文でもある冪乗剰余積e[11]とe'[11]と、暗号文でもある冪乗剰余積e[12]とe'[12]との３種の暗号文それぞれの、平文x[11]、x'[11]、x[12]、x'[12]、x[13]、x'[13]を秘密鍵λにより生成する（ステップＳ７０２）。
【０１２６】
次に乱数生成部３３３が、冪乗剰余積e[1]とe'[1]、冪乗剰余積e[11]とe'[11]、冪乗剰余積e[12]とe'[12]の３種の暗号文をそれぞれ生成するのに用いられたそれぞれの乱数s[11]、s'[11]、s[12]、s'[12]、s[13]、s'[13]（３種の乱数）を秘密鍵λにより生成する（ステップＳ７０３）。
【０１２７】
次に大きさ確認部３３４が、証明文に含まれる応答r[i1];(i=1、…、m)の要素全てが、安全変数と区間の大きさ|b-a|と挑戦値c[1]より定められる定数により定められる前記区間Rの中にあることと、応答r'[i1];(i=1、…、m)の要素全てが、安全変数と区間の大きさ|b-a|と挑戦値c'[1]より定められる定数により定められる前記区間R'の中にあることとを確認する（ステップＳ７０４）。
【０１２８】
次に２次式による検証部３３５が、eiの平文αiと暗号文eiの生成に用いられた乱数βiとを用いて、下限値ａに対応する挑戦値c[1]の2次式と応答r[i1]の2次式を用いた検証式、
x[11]c[1]2+x[12]c[1]+x[13]=Σi=1mαir[i1]2(modn)
s[11]^{c[1]2}s[12]^{c[1]}s[13]=g^{Σi=1mβir[i1]2}(modn)
が成り立つことと、
上限値に対応する挑戦値c'[1]の2次式と応答r'[i1]の2次式を用いた検証式
x'[11]c'[1]2+x'[12]c'[1]+x'[13]=Σi=1mαir'[i1]2(modn)
s'[11]^{c'[1]2}s'[12]^{c'[1]}s'[13]=g^{Σi=1mβir'[i1]2}(modn)
が成り立つことを確認する（ステップＳ７０５）。
【０１２９】
絶対値の大きさの検証ステップであるステップＳ６１３の詳細を図１０のフローチャートを参照して説明する。
【０１３０】
まず挑戦値生成部３４１が、公開鍵n、g、前記暗号文の列eｉ、冪乗剰余積e[2]および冪乗剰余積e[21]を入力に含むハッシュ関数の出力である下限値ａに対応する挑戦値c[2]と、公開鍵n、g、暗号文の列eｉ、冪乗剰余積e'[2]および冪乗剰余積e'[21]を入力に含むハッシュ関数の出力である上限値ｂに対応する挑戦値c'[2]との２つの挑戦値を生成する（ステップＳ８０１）。
【０１３１】
次に復号部３４２が、暗号文でもある冪乗剰余積e[2]とe'[2]と、暗号文でもある冪乗剰余積e[21]とe'[21]との２種の暗号文の、それぞれの平文x[21]、x'[21]、x[22]、x'[22]を秘密鍵λにより生成する（ステップＳ８０２）。
【０１３２】
次に乱数生成部３４３が、冪乗剰余積e[2]とe'[2]と、冪乗剰余積e[21]とe'[21]との２種の暗号文を生成するのに用いられたそれぞれの乱数s[21]、s'[21]、s[22]、s'[22]（２種の乱数）を秘密鍵λにより生成する（ステップＳ８０３）。
【０１３３】
次に大きさ確認部３４４が、前記応答r[i2];(i=1、…、m)の要素全てが、安全変数と区間の大きさ|b-a|と挑戦値c[2]より定められる定数により定められる前記区間Sの中にあることと、前記応答r'[i2];(i=1、…、m)の要素全てが、安全変数と区間の大きさ|b-a|と挑戦値c'[2]より定められる定数により定められる前記区間S'の中にあることとをを確認する（ステップＳ８０４）。
【０１３４】
次に１次式による検証部３４５が、下限値ａに対応する挑戦値c[2]の1次式と応答r[i2]の1次式を用いた検証式、
x[21]c[2]+x[22]=Σi=1mαir[i2](modn)
s[21]^{c[2]}s[22]=g^{Σi=1mβir[i2]}(modn)
が成り立つことと、上限値に対応する挑戦値c'[2]の１次式と応答r'[i2]の１次式を用いた検証式、
x'[21]c'[2]+x'[22]=Σi=1mαir'[i2](modn)
s'[21]^{c'[2]}s'[22]=g^{Σi=1mβir'[i2]}(modn)
が成り立つこととを確認する（ステップＳ８０５）。
【０１３５】
次に、確率公開鍵暗号文の冪乗剰余積の各指数係数の値が指定の範囲内にあることを証明する証明方法とその検証方法の一実施例について詳細に説明する。以下の実施例では、Paillierの暗号方式を使った例に即して説明する。
【０１３６】
[準備]
安全変数t、t'、sを準備する。tはt-log2t>t'なる関係を満たす。
本検証方法において、各指数係数の値が定められた区間にないにも関わらず、検証で指数係数の値が定められた区間にあると認められてしまう確率が2-t'以下である。本証明方法において、各指数係数の値が定められた区間にあるにも関わらず、証明に失敗する確率が21-s以下となる。これらの確率を考慮して安全変数t'、sを選ぶ。
また、区間の最小値をa、最大値をb、とする。
T=2(t+s+1)+|b-a|
として、後述の公開鍵n=pqは22T+1<nとなる様に選ぶ。
ここで|b-a|とは、b-aのbit数のことである。
√{2T(b-a)}を超えない最大の整数をDとする。
また、x^aとはxaのことでxのa乗のこととする。
p、qを二つの素数として、秘密鍵λをp-1とq-1の最大公倍数とする。
n=pqとする。
gは{gλmodn2-1}/nとnが互いに素になるよう選ばれているとする。
n=pqとgを公開鍵２０５とする。平文xの乱数rによる暗号文eを、
e=gxrnmod n2
とする。
暗号文列ei(i=1、…、m)を、
αi∈Zn
βi∈RZλ
を用いて、
ei=g^{αi}g^{nβi}mod n2 (i=1、…、m)
とする。ここでβiは定義域内から無作為に選ぶが、αiの分布は偏っていても良い。
列αi、βi(i=1、…、m)を以下では、暗号文列の生成元列と呼ぶ。
【０１３７】
最初に本発明の確率公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることの証明方法を、図面を参照して説明する。図１１と図１２と図１３は、本実施例の証明方法を説明するための図である。
【０１３８】
<入力ステップＳ３０１>
図１１において、区間を定める定数２０６である下限値a、上限値bと、安全変数２０９であるt、sと、指数係数列２０８であるwj∈[a、b](j=1、…、m)と、暗号文列２０７であるei(i=1、…、m)と、公開鍵２０５であるn、gとが入力される。
【０１３９】
<冪乗剰余積を求めるステップＳ３０２>
図１１の４０６において、指数係数列２０８であるwj∈[a、b](j=1、…、m)と、暗号文列２０７であるei(i=1、…、m)と、公開鍵２０５でありnとから、冪乗剰余積e=Πi=1mei^{wi}modn2を計算する。これが検証対象の冪乗剰余積２２１として証明文２０４に出力される。
【０１４０】
<ステップＳ３０３>
<両端値との差の列の生成ステップＳ３１１>
図１１の４０８において、それぞれの指数係数列wjと、区間を定める下限値a、上限値bとのそれぞれ差（４０７）を以下のように生成する。
wi-a(i=1、…、m)
b-wi(i=1、…、m)
【０１４１】
<拡大ステップＳ３１２>
図１１の４２０において、安全変数のｔ、ｓと区間を定める変数ａ、ｂとにより、T=2(t+s+1)+|b-a|を求め、２Ｔを拡大係数として、ステップＳ３０３で求めたそれぞれの差を、以下のように拡大する。
2T(wi-a)(i=1、…、m)
2T(b-wi)(i=1、…、m)
【０１４２】
<分解ステップＳ３１３>
図１１の４０９において、ステップＳ３１２で拡大されたそれぞれの数値（差）を、全てのi=1、…、mについて、
2T(wi-a)を超えない最大の平方数w[i1]2と、w[i2]=2T(wi-a)-w[i1]2とに分割し、また、
2T(b-wi)を超えない最大の平方数w'[i1]2113とw'[i2]=2T(b-wi)-w'[i1]2とに分割する。
【０１４３】
<平方数の証明ステップＳ３１４>
平方数の証明ステップを図１２を参照して説明する。
<暗号化ステップＳ４０１>
図１２の４２１において、暗号文
e[1]=Πi=1mei^{w[i1]2}modn2
e'[1]=Πi=1mei^{w'[i1]2}modn2
を生成する。
平方数の証明ステップでは、暗号文e[1]、e'[1]を生成した係数w[i1]2、w[i1]'2全てが平方数であり、この平文の平方根が2t+sDを超えないことを証明する。但し、Dを2T(b-a)の平方根を超えない最大の整数とする。
e[1]とe'[1]に対する証明方法は同じであるため、以下にはe[1]に対する証明についてのみ記述する。e[1]は最終的に暗号文４２０となる。
【０１４４】
<冪乗剰余積の生成ステップＳ４０２、Ｓ４０３>
図１２の４２２において、乱数列v[i1]∈R[0、2t+sD](i=1、…、m)を生成する。次に、図１２の４３１、４３２において、以下の２つの冪乗剰余積を計算する。
e[11]=Πi=1mei^{2v[i1]w[i1]}modn2
e[12]=Πi=1mei^{v[i1]2}modn2
を計算する。
【０１４５】
<挑戦値の生成ステップＳ４０４>
図１２の４２５において、挑戦値
c[1]=Hash(n、g、ei、e[1]、e[11]、e[12])mod2t
を計算する。
【０１４６】
<応答の生成ステップＳ４０５>
図１２の４２６において、i=1、…、mに関して応答
r[i1]=v[i1]+c[1]w[i1]
を計算する。
【０１４７】
<大きさの確認ステップＳ４０６>
図１２の４２７において、
r[i1]∈[c[1]D、2t+sD](i=1、…、m)
であれば、e[11]、e[12]、r[i1]を平方数の証明文とし、そうでなければ、平方数の証明ステップを最初からやり直す。w[i1]∈[0、D](i=1、…、m)である場合に、やり直す確率は2-s以下である。
【０１４８】
<絶対値の大きさの証明ステップＳ３１５>
絶対値の大きさの証明ステップを図１３を参照して説明する。
<暗号化ステップＳ５０１>
図１３の４５１において、以下の暗号文を生成する。
e[2]=Πi=1mei^{w[i2]}modn2
e'[2]=Πi=1mei^{w'[i2]}modn2
【０１４９】
絶対値の大きさの証明ステップでは、暗号文e[2]、e'[2]を生成した係数w[i2]、w'[i2]全ての絶対値が2Tを超えないことを証明する。
e[2]とe'[2]に対する証明方法は同じであるため、以下にはe[2]に対する証明についてのみ記述する。
【０１５０】
<冪乗剰余積の生成ステップＳ５０２>
図１３の４５２において、乱数列v[i2]∈R[0、2T](i=1、…、m)を生成し、４５５において、下記の冪乗剰余積を計算する。
e[21]=Πi=1mei^{v[i2]}modn2
【０１５１】
<挑戦値の生成ステップＳ５０３>
図１３の４５６において、下記の挑戦値を計算する。
c[2]=Hash(n、g、ei、e[2]、e[21])mod2t
【０１５２】
<応答の生成ステップＳ５０４>
図１３の４５７において、i=1、…、mに関して下記の応答を計算する。
r[i2]=v[i2]+c[2]w[i2]
【０１５３】
<大きさの確認ステップＳ５０５>
図１３の４５８において、
r[i2]∈[c[2]2T/2+1√{b-a}、2T](i=1、…、m)
であれば、e[21]、r[i2]を絶対値の証明文とし、そうでなければ、絶対値の証明ステップを最初からやり直す。w[i2]∈[0、√{b-a}](i=1、…、m)である場合に、やり直す確率は2-s以下である。
【０１５４】
<証明文の出力ステップ３０４>
確率公開鍵暗号文の冪乗剰余積eの各指数係数が区間内にあることの証明文として、暗号文e[1]、e'[1]及びこれらを生成した係数w[i1]2、w'[i1]2全てが平方数であり、且つこの平文の平方根が2t+sDを超えないことの証明文２２３、２２５と、暗号文e[2]、e'[2]及びこれらを生成した係数w[i2]2、w'[i2]2全ての絶対値が2Tを超えないことの証明文２２２、２２４を出力する。
【０１５５】
次に確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることの検証方法の実施例を図面を参照して説明する。図１４と図１５と図１６は本実施例の検証処理を説明するための図である。
【０１５６】
<入力ステップＳ６０１>
図１５において、暗号文列の生成元列５００であるαi、βi(i=1、…、m)と、冪乗剰余積e（２２１）を含む確率公開鍵暗号文の冪乗剰余積eの各指数係数が区間内にあることの証明文２０４等が入力される。そして以下に記される、分割の検証ステップＳ６１１と、平方数の検証ステップＳ６１２と、絶対値の大きさの検証ステップＳ６１３の全てにおいて証明が受理されたら、公開鍵暗号文の冪乗剰余積の各指数係数が指定の区間内にあることを受理する。その他の場合はこれを受理しない。
【０１５７】
<分割の検証ステップＳ６１１>
図１４の５０１において、まず、
E=e^{2T}/g^{2TaΣi=1m(αi+nβi)}modn2
E'=g^{2TbΣi=1m(αi+nβi)}/e^{2T}modn2
を計算する。そして、
e[2]e[1]=E
e'[2]e'[1]=E'
であることを確認したら受理する。
【０１５８】
<平方数の検証ステップＳ６１２>
平方数の検証ステップを図１５を用いて説明する。
平方数の検証ステップでは、暗号文e[1]（４２０）、e'[1]の平文が平方数であり、この平文の平方根が2t+sDを超えないことを検証する（図１４の５０２）。
e[1]とe'[1]に対する検証方法は同じであるため、以下にはe[1]に対する検証についてのみ記述する。
【０１５９】
<挑戦値の生成ステップＳ７０１>
図１５の５２０において、公開鍵２０５であるn、g、暗号文の列であるei、暗号文４２０であるe[1]、２個の冪乗剰余積４２３および４２４であるe[11]、e[12]、安全変数２０９であるtを使い、下記の挑戦値を計算する。
c[1]=Hash(n、g、ei、e[1]、e[11]、e[12])mod2t
【０１６０】
<復号ステップＳ７０２、乱数の生成ステップＳ７０３>
図１５の５１１において、暗号文e[1]（４２０）より、暗号文e[1]の平文x[11]を、
x[11]={(e[1]λmodn2)-1}/{(gλmodn2)-1}
として求め、さらに５１３において、暗号化のための乱数s[11]（５０２）を秘密鍵λを用いて、下記のように求める。
s[11]=(e[1]g-x[11])^(n-1modλ)modn
【０１６１】
また、図１５の５１１において、証明文の要素４２３であるe[11]より、暗号文e[11]の平文x[12]を、
x[12]={(e[11]λmodn2)-1}/{(gλmodn2)-1}
として求め、さらに５１３において、暗号化のための乱数s[12]を秘密鍵λを用いて下記のように求める。
s[12]=(e[11]g-x[12])^(n-1modλ)modn
【０１６２】
更に、図１５の５１１において、証明文の要素４２４であるe[12]より、暗号文e[12]の平文x[13]を、
x[13]={(e[12]λmodn2)-1}/{(gλmodn2)-1}
として求め、さらに５１３において、暗号化のための乱数s[13]を秘密鍵λを用いて下記のように求める。
s[13]=(e[12]g-x[13])^(n-1modλ)modn
【０１６３】
<大きさの確認ステップＳ７０４>
図１５の５１９において、
r[i1]∈[c[1]D、2t+sD](i=1、…、m)
により大きさの確認を行い、生成元列５００であるαi、βiを使い、挑戦値４３０であるc[1]の2乗を使った下記の検証式が成り立つことを確認できれば、平方数の検証を受理する。
x[11]c[1]2+x[12]c[1]+x[13]=Σi=1mαir[i1]2(modn)
s[11]^{c[1]2}s[12]^c[1]s[13]=g^{Σi=1mβir[i1]2}(modn)
e[1]の平文が平方数でない場合や、その平方根がn/2の平方根よりも小さくない場合に、誤って受理してしまう確率は、2-t'以下である。
【０１６４】
<絶対値の大きさの検証ステップＳ６１３>
絶対値の大きさの検証ステップを図１６を参照して説明する。この絶対値の大きさの検証ステップでは、暗号文４５０であるe[2]、e'[2]の平文の絶対値が2Tを超えないことを検証する。
e[2]とe'[2]に対する検証方法は同じであるため、以下にはe[2]に対する検証についてのみ記述する。
【０１６５】
<挑戦値の生成ステップＳ８０１>
図１６の５３０において、公開鍵２０５であるn、g、暗号文の列であるei、暗号文４５０であるe[2]、冪乗剰余積４５４であるe[21]、安全変数２０９であるtを用いて、挑戦値c[2]=Hash(n、g、ei、e[2]、e[21])mod2tを計算する。
【０１６６】
<復号ステップＳ８０２、２種の乱数の生成ステップＳ８０３>
図１６の５３２において、暗号文e[2]より、暗号文e[2]の平文x[21]を
x[21]={(e[2]λmodn2)-1}/{(gλmodn2)-1}
として求め、さらに５３４において、暗号化のための乱数５３３であるs[21]を秘密鍵λを用いて下記のように求める。
s[21]=(e[2]g-x[21])^(n-1modλ)modn
【０１６７】
また、図１６の５３２において、証明文の要素４５４であるe[21]より、暗号文e[21]の平文x[22]（５３５）を
x[22]={(e[21]λmodn2)-1}/{(gλmodn2)-1}
として求め、さらに暗号化のための乱数５３６であるs[22]を秘密鍵λを用いて下記のように求める。
s[22]=(e[21]g-x[22])^(n-1modλ)modn
【０１６８】
<大きさの確認ステップＳ８０４>
図１６の５３７において、
r[i2]∈[c[2]2T/2+1√{b-a}、2T](i=1、…、m)
により、大きさの確認を行い、生成元列５００であるαi、βiを使い、挑戦値c[2]（４６１）の1次である下記の検証式が成り立つことを確認できれば、絶対値の検証を受理する。
x[21]c+x[22]=Σi=1mαir[i2](modn)
s[21]cs[22]=g^{Σi=1mβir[i2]}(modn)
e[2]の平文の絶対値が2Tよりも小さくない場合に、誤って受理してしまう確率は、2-t'以下である。
【０１６９】
[正当性(1)]
本実施例における、平方数の証明ステップ及び平方数の検証ステップの正当性について述べる。
W[i],Z[i],V[i] を、
e[1] =Πi=1m ei[i] mod n^2
e[11]=Πi=1m eiZ[i] mod n^2
e[12]=Πi=1m eiV[i] mod n^2
を満たすもので、e[1],e[11],e[12] を生成した者が知っている値であるとする。
式
r[i1]2 = c[1]2 W[i] + c[1] Z[i] + V[i] mod n
がなり立つ様な r[i1] 以外には、
x[11]c[1]2 +x[12]c[1] +x[13] = Σi=1mαir[i1]2 mod n
s[11]^{c[1]2}s[12]^c[1] s[13] =g^{Σi=1mβir[i1]2} mod n
の両式を満たす r[i1] を生成できる確率はたかだか2-tである。
この時、平方でないW[i] に対して、式
r[i1]2 =c[1]2 W[i] + c[1] Z[i] + V[i] mod n
右辺の平方根 r[i1] が存在する確率はたかだか{1 +t log 2 }/2^t+1 である。これは無視できるほど小さいので, 検証が受理されるにはW[i] は平方でなければならない。
また、
w[i1] ∈ [-2t+sD,2t+sD]
でなければ、式
r[i1] ∈ [c[1] D,2t+sD](i=1,...,m)
が満たされる確率はたかだか2^{-t}である。
これは無視できるほど小さいので, 検証が受理されるにはW[i] の平方は、
[-2t+sD,2t+sD]
の範囲内になければならない。
本ステップから検証者には、
Σi=1m αi w[i1]2 mod n,
Σi=1m αi v[i1]2 mod n,
g^{Σi=1m βi w[i1]2} mod n,
g^{Σi=1m βi v[i1]2} mod n
の値しか漏れない。
【０１７０】
[正当性(2)]
本実施例における、絶対値の大きさの証明ステップ及び絶対値の大きさの検証ステップの正当性について述べる。
式
r[i2] = v[i2] + c[2] w[i2]
で表されるr[i1]以外には、
x[21]c +x[22] = Σi=1mαir[i2] mod n
s[21]cs[22] =g^{Σi=1mβir[i2]} mod n
の両式を満たす r[i1] を生成できる確率はたかだか 2^{-t}である。これは無視できるほど小さいので, 検証が受理されるにはこの条件をが満たされなければならない。
そして、
w[i2] ∈ [-2T,2T](i=1,...,m)
でなければ、
r[i2] ∈ [c[2] 2T/2+1√{b-a},2T](i=1,...,m)
が満たされる確率はたかだか2^{-t}である。
これは無視できるほど小さいので、検証が受理されるにはこの条件が満たされなければならない。
本ステップから検証者には、
Σi=1m αi w[i2] mod n, g^{Σi=1m βi w[i2]} mod nの値しか漏れない。
【０１７１】
[正当性(3)]
本発明の「公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることの証明方法、公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることの検証方法」の正当性について述べる。.
正当性(1)、正当性(2) により示された、w[i1],w[i2],w'[i1],w'[i2] に課せられる条件より、 wi が定められた区間内に存在することが分る。
【０１７２】
［検出結果証明の詳細］
次に、検出結果正当性証明手段１４２で利用可能な、確率公開鍵暗号文の平文が区間内にあることを証明する証明方法と、検出結果正当性検証手段１３３で利用可能な、確率公開鍵暗号文の平文が区間内にあることを検証する検証方法の一例について詳細に説明する。
【０１７３】
図１７は確率公開鍵暗号文の平文が区間内にあることを証明する証明文作成装置の構成を説明するためのブロック図であり、図１８と図１９はこの証明文作成装置による証明文の作成処理を説明するためのフローチャートである。
【０１７４】
本実施の形態の確率公開鍵暗号文の平文の値が区間内にあることの証明方法は、秘密鍵により平文と暗号化に用いられた乱数との両方を求めることのできる確率公開鍵暗号方式による暗号文を用いる。また以下、暗号化する平文は数値データであり、またこれを暗号化した暗号文もまた数値データを成すものとして説明する。
【０１７５】
図１７を参照すると、本実施の形態の証明文作成装置は、証明文の作成に用いる各種データを人力するための入力部６０１と、入力されたデータに基づき演算を行ない証明文を作成する演算処理部６０２と、作成された証明文６０４を出力する出力部６０３を備えている。また、演算処理部６０２は、復号部６２１、両端値との差の算出部６２２、拡大部６２３、分割部６２４、暗号化部６２５、証明文生成部６２６、乱数生成部６２７を備えている。
【０１７６】
図１８を参照すると、本実施の形態の証明文の作成処理において、まず入力部６０１は証明に必要な各種の情報として、証明対象となる確率公開鍵暗号文６１１、秘密鍵６１２、区間を定める変数６１３および予め設定された安全変数６１４を入力する（ステップＳ９０１）。次いで演算処理部６０２の復号部６２１は、秘密鍵６１２を用いて確率公開鍵暗号文６１１を復号することにより、平文の値と暗号化に用いられた乱数の値を取得する（ステップＳ９０２）。
【０１７７】
そして、この取得した平文と乱数の値を用いて、演算処理部６０２は平文の値が定められた区間内にあることを検証者に対し証明するための証明文を作成し、出力部６０３から出力する（ステップＳ９０３）。このステップＳ９０３における証明文の作成処理は、図１９のフローチャートにおいて詳細に示している。
【０１７８】
図１９を参照すると、まず、両端値との差の算出部６２２は、確率公開鍵暗号文６１１の平文の値と、定められた区間の両端値との差を算出する（ステップＳ１００１）。つまり、定められた区間の上限値から平文の値を引いた値と、平文の値から定められた区間の下限値を引いた値とを算出する。
【０１７９】
次に、拡大部６２３は、両端値との差の算出部６２２により算出された2つの値に対して、安全変数６１４から計算された拡大係数をそれぞれ乗じることにより拡大して、拡大値をそれぞれ生成する（ステップＳ１００２）。
【０１８０】
次に、分割部６２４は、拡大部６２３により拡大されたそれぞれの拡大値を分割する（ステップＳ１００３）。つまり、それぞれの拡大値に対して、それぞれの値を超えない最大の平方数をそれぞれに求め、それぞれの拡大値から対応する平方数を引くことにより差の整数をそれぞれ求める。これによりそれぞれの拡大値を、平方数と、差の整数との和に分割する。
【０１８１】
次に、暗号化部６２５は、分割部６２４により分割して得られた数値を暗号化する（ステップＳ１００４)。この暗号化においては、2つの拡大値のそれぞれにおいて、少なくとも１つ以上の分割された値（平方数又は差の整数)を暗号化する。例えば、2つの拡大値のそれぞれにおいて分割して得られた平方数を暗号化する方式や、2つの拡大値のそれぞれにおいて分割して得られた差の値を暗号化する方式により暗号化を行なう。また、この暗号化は、証明対象の確率公開鍵暗号文６１１と同様の方式で行なうものであり、その暗号化に用いる乱数は、乱数生成部６２７により生成された値を用いる。
【０１８２】
次に、証明文生成部６２６は、この分割部６２４により分割して得られた数値の、それぞれに関する証明文を生成する。図１９のフローチャートにおいては、まず各拡大値における差の整数（の絶対値)が、前記拡大係数より小さいことの証明文を生成する（ステップＳ１００５)。この証明文の生成においては、2つの差の整数と、前述の安全変数６１４と、区間を定める変数６１３（上限値と下限値)と、これらの値に基づいて定められる拡大係数と、暗号化部６２５が暗号化に用いるために乱数生成部６２７により生成された乱数と、証明対象の確率公開鍵暗号文６１１の公開鍵等のデータを用いて証明文を生成する。
【０１８３】
そして次に、各拡大値における前記平方数が、平方数を成すことと、且つその平方根が確率公開鍵暗号文６１１の平文に関する周期の半分の平方根より小さい（つまり、各平方数は周期の半分より小さい)ことの証明文を生成する（ステップＳ１００６)。この証明文の生成においては、2つの前記平方数と、前記安全変数６１４と、前記区間を定める変数６１３（上限値と下限値)と、前記拡大係数と、前記暗号化のための乱数と、前記公開鍵等のデータを用いて証明文を生成する。
【０１８４】
ここで、確率暗号文の平文に関する周期mは、平文ｘと暗号化のための乱数rとの組(x,r)と(x+π,r)とが、常に同じ確率公開鍵暗号文を与えるOでない最小のｍである。
【０１８５】
最後に、以上の各ステップにより生成された、2つある平方数の確率公開鍵暗号文（又は、2つある差の整数の確率公開鍵暗号文)と、それぞれの差の整数（の絶対値)が、前記拡大係数より小さいことの証明文と、それぞれの平方数が、平方数を成すことと且つ平方数の平方根が確率公開鍵暗号文の周期の半分の平方根より小さい（つまり、各平方数は周期の半分より小さい)ことの証明文とを、前記確率公開鍵暗号文の平文が定められた区間にあることの証明文として出力する（ステップＳ１００７)。
【０１８６】
図２０は、確率公開鍵暗号文の平文が区間内にあることを検証する検証装置の構成を説明するためのブロック図であり、図２１はこの検証装置の処理を説明するためのフローチャートである。
【０１８７】
図２０を参照すると、本実施の形態の検証装置は、検証処理に用いる各種データを入力するための入力部７０１と、入力されたデータに基づき検証処理を行なう演算処理部７０２と、検証結果を出力する出力部７０３とを備えている。また、演算処理部７０２は、両端値との差の値の暗号文生成部７１１、拡大部７１２、分解部７１３、検証部７１４、判定部７１５を備えている。
【０１８８】
図２１を参照すると、本実施の形態の検証の作成処理において、まず入力部７０１は検証に必要な情報として、検証対象の確率公開鍵暗号文６１１、区間を定める変数６１３、安全変数６１４、証明文６０４を入力する（ステップＳ１１０１）。次に、演算処理部７０２の両端値との差の値の暗号文生成部７１１は、検証対象の確率公開鍵暗号文６１１を、各両端値との差の値の暗号文に変換する（ステップＳ１１０２)。つまり、区間を定める変数６１３の上限値から確率公開鍵暗号文６１１の平文を引いた値の確率公開鍵暗号文と、確率公開鍵暗号文６１１の平文から下限値を引いた値の確率公開鍵暗号文とを生成する。
【０１８９】
次に、拡大部７１２は、両端値との差の値の暗号文生成部７１１により生成された2つの両端値との差の値の暗号文のそれぞれを、その平文の値（端値との差)に安全変数６１４から計算された拡大係数をそれぞれ乗じた拡大値の暗号文（拡大値暗号文)に変換する（ステップＳ１１０３)。つまり、上限値から確率公開鍵暗号文の確率公開鍵暗号文を引いた値に、拡大係数を乗じた値の確率公開鍵暗号文である拡大値暗号文と、確率公開鍵暗号文の平文から下限値を引いた値に、拡大係数を乗じた値の確率公開鍵暗号文である拡大値暗号文とを生成する。
【０１９０】
次に、分解部７１３は、この拡大部７１２により生成された各拡大値暗号文を、それぞれ2つの確率公開鍵暗号文の積に分解する（ステップＳ１１０４)。この積に分解された暗号文（第1と第2の暗号文)においては、その一方（第1の暗号文)に証明文６０４に含まれる（平文と両端値との差の取り方が)対応する側の分割された値の暗号文を用い、分解される他方の暗号文（第2の暗号文)は、先の証明文に含まれる暗号文との積が当該拡大値暗号文を成すものを算出して取る。
【０１９１】
次に、検証部７１４は、分解部７１３により分解されて得られた各暗号文を検証する。図２１のフローチャートにおいては、まず差の値の検証を行なう（ステップＳ１１０５)。分解部７１３により分解された各暗号文の内で、もし説明文６０４から取り出されて用いられた暗号文が、ステップＳ１００３において差の値として分割された値の暗号文である場合には、その暗号文をここでの検証に用い、そうでない場合には分解された他方の暗号文を用いる。ここでの差の値の検証においては、証明文６０４に含まれる、ステップＳ１００５において生成された差の整数（の絶対値)が前記拡大係数より小さいことの証明文を用いて、先の分解された暗号文の平文（の絶対値)が前記拡大係数より小さいことを検証する。ここで、検証結果が正しければ受理を、正しくなければ不受理を出力する。
【０１９２】
そして検証部７１４は、平方数の検証も行なう（ステップＳ１１０６)。ここでの平方数の検証に用いる暗号文は、先の分解部７１３により分解された暗号文の内で、差の検証に用いる側でない側の暗号文である。つまり、分解部７１３により分解された各暗号文の内で、もし説明文６０４から取り出されて用いられた暗号文が、ステップＳ１００３において平方数として分割された値の暗号文である場合には、その暗号文をここでの検証に用い、そうでない場合には分解された他方の暗号文を用いる。ここでの平方数の検証においては、証明文６０４に含まれる、ステップＳ１００６において生成された平方数に関する証明文を用いて、先の分解された暗号文の平文が平方数であり、且つその平方根が確率公開鍵暗号文の周期の半分の平方根より小さい（つまり、その平文の値は周期の半分より小さい)ことを検証する。ここで、検証結果が正しければ受理を、正しくなければ不受理を出力する。
【０１９３】
最後に、判定部７１５が、検証部７１４による差の値と平方数の検証に基づいて、もしその双方の検証においていずれも受理が出力された場合に限り、暗号化された数値が定められた区間内に属する旨の検証結果を出力する（ステップＳ１１０７)。
【０１９４】
次に、確率公開鍵暗号文の平文が区間内にあることを証明する証明方法と確率公開鍵暗号文の平文が区間内にあることを検証する検証方法の一実施例について詳細に説明する。以下の実施例では、Paillierの暗号方式を使った例に即して説明する。
【０１９５】
[準備]
正しく検証される確率を規定する安全変数６１４としてｔ、１を準備する。本検証方法において、平文が定められた区間にないにも関わらず、検証で平文が定められた区間にあると認められてしまう確率が2-t以下である。本証明方法において、平文が定められた区間にあるにも関わらず、証明に失敗する確率が21-1以下となる。これらの確率を考慮して安全変数ｔ、１を選ぶ。
また、区間を定める変数６１３として最小値をa、最大値をbとする。
変数Ｔを、T＝2(t+1+1)＋｜b-a｜と定義する。ここで｜b-a｜とは、b-aのbit数のことである。後述のn=pqは、22T+1＜nとなる様に選ぶ。拡大係数を、2Tと定める。
Dを、√{2Ｔ(b-a)}を超えない最大の整数とする。
【０１９６】
また以下、x^aとは、xのa乗（つまり、xa)を示すものとする。
P、qを2つの素数として、λをp-1とq-1の最小公倍数とする。
gは、gλ mod n2とnが互いに素になるように選ばれているとする。
n=pqと、gを公開鍵とする。
平文xの乱数rによる暗号文eを、e=gxrn mod n2とする。
【０１９７】
先ず最初に、確率公開鍵暗号文の平文が区間内にあることの証明文の作成方法の実施例を、図面を参照して説明する。図２２、図２３は、本実施例の証明文の作成を説明するための図である。
【０１９８】
[平文と暗号化のための乱数を求める]（ステップＳ９０２)
まず、図２２の７０１において、証明対象の確率公開鍵暗号文６１１であるeが入力されたら、その平文７０２であるxを、x={(eλ mod n2)-1}/{(gλ mod n2)-1}により求め、更に、暗号化のために用いられた乱数７０３であるrを、秘密鍵６１２であるλを用いて、e'=cg-x mod n 、n'=n-1 mod λ、r=e'n' mod nとして求め、この平文xと乱数rを出力する。
【０１９９】
[平文が定められた区間にあることの証明文を生成する]（ステップＳ９０３)
[区間の両端値との差を算出]（ステップ１００１)
図２２の７０４において、平文７０２であるxと、区間を定める変数６１３の最小値a、最大値bより、その差(７０５、７０６)であるx-aとb-xを求める。
【０２００】
なお以降は、2つの両端値との差x-aとb-xに対して全く同じ処理を行なうために、片方のみについて記述する。図２２の証明文６０４の（b-xによる)上半分（６０４−１、６０４−２、６０４−３)を生成する過程は、証明文の（x-aによる)下半分（６０４−４、６０４−５、６０４−６)を生成する過程と同様であるため図中では点線で示されている。ここで、両端値との差の一方であるx-aを、Xと表す（これは、点線により示されるb-xの側においても以下同様である)。
【０２０１】
[拡大]（ステップＳ１００２)
図２２の７０７において、このXに、安全変数等から計算された拡大係数2Tを用いて、2ＴXと拡大する。
【０２０２】
[分割]（ステップＳ１００３)
図２２の７０９において、その自乗が2TXを超えない最大の整数vを求め、差の値z（=2TX−ｖ2)を算出する。これにより、拡大値2TXを、平方数７１１であるv2と、差の値７１０であるzに分割する。
【０２０３】
[暗号化]（ステップＳ１００４)
本実施例においては、分解された数値の内で、差の値ｚを平文として暗号化する。
【０２０４】
図２２の７１２において、0≦r[1]＜nなる任意の乱数７１３であるr[l]を無作為に選び、図２２の７１４において、差の値zの暗号文６０４−６であるe[1]を、e[1]=ｇＺr[1]n mod n2 により計算する。ここで、R=r^{2T} mod n、r[2]=R/r[1] mod n、e[2]=g^{v2}r[2]n mod n2と計算すると、e[1]e[2]=ｇＸＲｎ mod n2が得られる。右辺は{e/ga}^{2T} mod n2 又は{gｂ/e}^{2T} mod n2 である。
【０２０５】
[差の値に関する証明文の生成]（ステップＳ１００５)
ここでは、暗号文e[1]の平文ｚの絶対値が、拡大係数2Tを超えないことを証明するための証明文を生成する。
【０２０６】
0≦μ≦2Tなるμ、0≦ρ＜ｎなるρを無作為に選び、w＝gμρn mod n2を計算する。更に、c=Hash（e[1]、w) mod 2tを求める。ここでHashとはハッシュ関数である。更に、d[1]=μ+zc、d[2]=ρr[1]n mod nを求める。
【０２０７】
もし、c2T/2+1√（b-a)≦d[1]≦2Tならば、c、d[1]、d[2]のデータの組を、平文zの絶対値の上限の証明文６０４−５として出力する。そうでない場合には、このステップＳ１００５を最初からやり直す（乱数μ、ρをもう一度無作為に選び直す）。このやり直す確率は21-l以下となる。
【０２０８】
[平方数に関する証明文の生成]（ステップＳ１００６)
本ステップの処理を図２３を参照して説明する。ここでは、先の暗号文e[2]=gXRn  mod n2の平文７１１を成すv2の値が、平方数であることと、その平方根７２２であるvが2t+1Dを超えないことを証明する。
【０２０９】
最初に、図２３の７２４において、0≦τ＜ｎなる任意の乱数７２３であるτを選び、図２３の７２７において、vの暗号文７２５であるｗ[0]を、w[0]＝ｇvτn mod n2により計算する。
【０２１０】
次に、図２３の７２８において、乱数r[l]、r、安全変数６１４から、R＝r^{2T} mod n、r[2]=R/r[1] mod nを求め、ρ'（７２９)を、ρ'=τ-vr[2] ｍod nにより計算する。
【０２１１】
更に、0≦μ'≦2t+1Dなる任意の乱数７３０であるμ'、0≦σ＜nなる在意の乱数７３１であるσ、0≦σ'<nなる任意の乱数７３２であるσ'、を無作為に選び、図２３の７３３と７３４において、生成元７２６であるgと暗号文w[0]をそれぞれ用いて、μ'の暗号文であるw[1]=gμ’σn mod n2、w[2]=w[0]μ’σ'n mod n2を計算する（ステップ412,413)。
【０２１２】
次に、図２３の７３５において、ハッシュ関数Hash()を用いて、ハッシュ値c'=Hash(c[1]、w[1]、w[2]) mod 2tを求める。次に、図２３の７３６、７３７、７３８において、d[3]=μ'+vc'、d[4]=στc' mod n、d[5]=σ'ρ'c' mod n、を計算する。
【０２１３】
そして、図２３の７３９において、証拠の大きさの確認を行ない、もしc'D≦d[3]≦2ｔ+1Dならば、c'、w[0]、d[3]、d[4]、d[5]を証明文６０４−４として出力する。その他の場合はステップＳ１００６を最初からやり直す（乱数τ、μ’、σ、σ’をもう一度無作為に選び直す）。このやり直す確率は21-1以下となる。
【０２１４】
[証明文の出カ](ステップＳ１００７)
証明文生成部６２６は、Xがx-aである場合とb-xである場合についてそれぞれ、分割された値の暗号文(e[1])と、差の値の証明文(c、d[1]、d[2])と、平方数の証明文(c'、w[0]、d[3]、d[4]、d[5])とを、平文が区間内にあることの証明文６０４として出力する。
【０２１５】
次に確率公開鍵暗号文の平文が区間内にあることの検証方法の実施例を以下に図面を参照して説明する。図２４、図２５は、本実施例の検証処理を説明するための図である。
【０２１６】
[両端値との差の値の暗号文を生成](ステップＳ１１０２)
図２４の８０１において、検証対象の確率公開鍵暗号文６１１であるeと、区間を定める変数６１３の最小値a、最大値bより、上限値から確率公開鍵暗号文の平文を引いた値の確率公開鍵暗号文８０３であるgb/e mod n2=gb-xrn mod n2と、確率公開鍵暗号文の平文から下限値を引いた値の確率公開鍵暗号文８０２であるe/ga mod n2=gx-arn mod n2とを生成する。
【０２１７】
以降、2つの両端値との差x-aとb-xによる2つの暗号文に対して、全く同じ処理を行なうために片方のみについて記述する。この暗号文８０２の平文であるx-aをXと表す(また、暗号文８０３の平文であるb-xをXと表す場合も同様である)。Xの暗号文８０６であるE=gXrn mod n2に関して、Xが0以上かつ暗号文の周期の半分以下であることを検証する。
【０２１８】
[拡大値の暗号文に変換](ステップＳ１１０３)
図２４の８０４において、暗号文８０６であるEに対して、Tから計算された拡大係数2Tを用いて、E＾{2T} mod n2=g^{2TX}rn mod n2を計算する。これにより拡大値である2TXの暗号文が算出される。
【０２１９】
[分解](ステップＳ１１０４)
図２４の８０８において、拡大値の暗号文であるE^{2T} mod n2を、証明文６０４に含まれる暗号文６０４−６であるe[1]を用いて、e[1](８１０)とe[2](８１１)、e[2]=E^{2T}/e[1] mod n2の積に分解する。e[1]e[2]=E^{2T}である。
【０２２０】
〔差の値の検証](ステップＳ１１０５)
図２４の８１２において、e[1]の平文(z)の絶対値が2Tより小さいことを検証する。c2T/2+1√(b-a)≦d[1]≦2Tであり、かつ、c=Hash(e[1]、gd[1]d[2]ne[1]-c mod n2) mod 2tであれば、暗号文e[1]の平文の絶対値が2Tより小さいことを受理する。
【０２２１】
[平方数の検証](ステップＳ１１０６)
図２４の８１２において、暗号文e[2]の平文(v2)が平方数であり、その平方根が2t+1Dを超えないことを検証する。
【０２２２】
本ステップの処理を図２５を参照して説明する。
図２５の８２１において、c'D≦d[3]≦2t+1Dであることを確認する。
図２５の８２２において、w[1]を、w[1]=gd[３]d[4]nw[0]-c' mod n2と計算する。
図２５の８２３において、w[2]を、w[2]=w[0]d[３]d[5]ne[1]-c' mod n2と計算する。
図２５の８２４において、ハッシュ値をHash(e[1]、w[1]、w[2])=Hash(e[1]、gd[３]d[4]nw[0]-c' mod n2、w[0]d[３]d[5]ne[1]-c' mod n2、)mod 2tと計算して、図２５の８２５において、これがc'に等しいかどうかを確認し、もし等しい場合には、暗号文e[2]の平文(v2)が平方数でありその平方根が2t+1Dを超えないことを受理する。
【０２２３】
〔検証結果の出力〕(ステップＳ１１０７)
図２４の８１４において、検証結果をまとめて、2つの値x-aとb-xによる2つの暗号文に対する、ステップＳ１１０５の差の値の検証と、ステップＳ１１０６の平方数の検証とによる両方の出力がともに受理であれば受理を、片方でも不受理であれば不受理を、検証結果８１５として出力する。
【０２２４】
次に、上記説明された証明文の作成と検証の方法における、正当性について説明する。
【０２２５】
[正当性(1)]
本実施例の確率公開鍵暗号文の平文が区間内にあることの証明方法における、差の値に関するステップＳ１００５の証明文の作成と、その証明文によるステップＳ１１０５による検証の正当性について述べる。
【０２２６】
式ｇμρn=gd[1]d[2]ne[1]-c mod n2が保証されていない場合には、式c=Hash(e[1]、gd[1]d[2]ne[1]-c mod n2)mod 2tが成立する確率は2-t以下になる。式gμρn=gd[1]d[2]ne[1]-c mod n2が成り立つためには、d[1]=μ+zcが成り立たねばならない。平文xが定められた区間にある場合、zは-2T/2+1√(b-a)≦z≦2T/2+1√(b-a)となる。この時に、c2T/2+1√(b-a)≦d[1]≦2Tが成り立たない可能性は、2-1以下である。また、この時にzが、-2T/2+1√(b-a)≦z≦2T/2+1√(b-a)のいずれの値である可能性もd[1]によらずに同じである。Zが、-2T≦ｚ≦2Tにない場合に、c2T/2+1√(b-a)≦d[1]≦2Tが成り立つ可能性は、2-t以下である。
【０２２７】
[正当性(2)]
本実施例の確率公開鍵暗号文の平文が区間内にあることの証明方法における、平方数に関するステップＳ１００６の証明文の作成と、その証明文によるステップ１１０６による検証の正当性について述べる。
【０２２８】
式gμ'σn=gd[３]d[4]nw[0]-c' mod n2と、式w[0]μ'σ'n=w[0]d[３]d[5]ne[1]-c' mod n2とが保証されていない場合においては、c'=Hash(e[1]、w[1]、w[2])=Hash(e[1]、gd[３]d[4]nw[0]-c' mod n2)、w[0]d[３]d[5]nc[1]-c' mod n2、)mod 2tが成立する確率は2-t以下になる。式gμ'σn=gd[３]d[4]nw[0]-c mod n2と、式ｗ[0]μ'σ'n=w[0]d[３]d[5]ne[1]-c' mod n2とが成り立つためには、d[3]=μ'+vc'が成り立たねばならない。そのため、e[2]の平文はvの平方であることが保証される。平文xが定められた区間にある場合、vは−D≦v≦Dとなる。この時に、cD≦d[3]≦2t+1Dが成り立たない可能性は、2-1以下である。また、この時vの−D≦v≦Dのいずれの値である可能性もd[3]によらずに同じである。すなわち、e[2]の平文が0以上2T(b-a)以下のいずれの値である可能性もd[3]によらずに同じである。
【０２２９】
vが、-2t+1≦V≦2t+lDにあることが保証されていない場合に、cD≦d[3]≦2t+1Dが成り立つ可能性は、2-T以下である。すなわち、e[2]の平文が0以上2２(t+1)2T(b-a)以下でない場合にcD≦d[3]≦2t+1Dが成り立つ可能性は、2-t以下である。2T+1<nであったので、e[2]の平文はn/2より小さいことが保証される。
【０２３０】
[正当性(3)］
正当性(1)、(2)においてv,zの値の大きさが知られないためのv,zの大きさに対する条件が、v,zに対して保証される大きさの区間よりも小さい。しかし、xが定められた区間に属すればv,zは大きさの知られない区間に属する。また、xが定められた区間になければ、v,zはそれらに対して保証される大きさの区間から出てしまう。
【０２３１】
以上好ましい実施の形態および実施例を挙げて本発明を説明したが、本発明は上記の実施の形態および実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形して実施することができる。
【０２３２】
【発明の効果】
以上説明したように本発明によれば以下のような効果が得られる。
【０２３３】
識別データ（電子透かし）の付加方法に関する情報の漏れを最小限にすることができる。その理由は、利用者端末が検出依頼正当性証明データによって検出依頼データの正当性を証明しない限り、センタ端末は電子透かしの検出依頼を受理しないため、実際の被検査データに基づかない特殊なデータ列に基づく不正な検出依頼による悪意者からの攻撃を防御できるからである。特に、センタ端末が検出結果を確率的に決定する構成にあっては、透かし有りと透かし無しの閾値に近い被検査データを用いた攻撃からも防御できるため、より一層効果がある。
【０２３４】
効率良く識別データ（電子透かし）を検出することができる。その理由は、センタ端末は検出結果の正当性を証明しなければならないために検出結果を偽ることができず、このため、利用者端末は一つの被検査データの電子透かしの検出に際して一つの検出依頼を行えば済むからである。また、利用者端末が被検査データに対して電子透かしの有無を反転させて検出依頼を行うか否かを秘密裏に実施することで、一つの検出依頼で済ませながら電子透かしの真の検出結果をセンタ端末側に分からなくすることができる。
【図面の簡単な説明】
【図１】本発明の一実施の形態のブロック図である。
【図２】本発明の一実施の形態の処理を説明するためのフローチャートである。
【図３】確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを証明する証明文を作成する証明文作成装置の一例を示すブロック図である。
【図４】確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを証明する証明文作成装置による証明文の作成処理を説明するためのフローチャートである。
【図５】確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを証明する証明文作成装置による証明文の作成処理を説明するためのフローチャートである。
【図６】確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを証明する証明文作成装置による証明文の作成処理を説明するためのフローチャートである。
【図７】確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを検証する検証装置の一例を示すブロック図である。
【図８】確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを検証する検証装置による検証処理を説明するためのフローチャートである。
【図９】確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを検証する検証装置による検証処理を説明するためのフローチャートである。
【図１０】確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを検証する検証装置による検証処理を説明するためのフローチャートである。
【図１１】確率公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることの証明方法を説明するための図である。
【図１２】確率公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることの証明方法を説明するための図である。
【図１３】確率公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることの証明方法を説明するための図である。
【図１４】確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることの検証方法を説明するための図である。
【図１５】確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることの検証方法を説明するための図である。
【図１６】確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることの検証方法を説明するための図である。
【図１７】確率公開鍵暗号文の平文が区間内にあることを証明する証明文作成装置の構成を説明するためのブロック図である。
【図１８】確率公開鍵暗号文の平文が区間内にあることを証明する証明文作成装置による証明文の作成処理を説明するためのフローチャートである。
【図１９】確率公開鍵暗号文の平文が区間内にあることを証明する証明文作成装置による証明文の作成処理を説明するためのフローチャートである。
【図２０】確率公開鍵暗号文の平文が区間内にあることを検証する検証装置の構成を説明するためのブロック図である。
【図２１】確率公開鍵暗号文の平文が区間内にあることを検証する検証装置処理を説明するためのフローチャートである。
【図２２】確率公開鍵暗号文の平文が区間内にあることの証明文の作成を説明するための図である。
【図２３】確率公開鍵暗号文の平文が区間内にあることの証明文の作成を説明するための図である。
【図２４】確率公開鍵暗号文の平文が区間内にあることの検証方法の処理を説明するための図である。
【図２５】確率公開鍵暗号文の平文が区間内にあることの検証方法の処理を説明するための図である。
【符号の説明】
１０１…センタ端末
１０２…利用者端末
１１１…被検査データ記憶手段
１１２…公開情報記憶手段
１１３…依頼機構
１１４…入出力装置
１２１…情報設定公開手段
１２２…情報記憶手段
１２３…検出機構
【図１】
0004092920.tif 000016
【図２】
0004092920.tif 000017
【図３】
0004092920.tif 000018
【図４】
0004092920.tif 000019
【図５】
0004092920.tif 000020
【図６】
0004092920.tif 000021
【図７】
0004092920.tif 000022
【図８】
0004092920.tif 000023
【図９】
0004092920.tif 000024
【図１０】
0004092920.tif 000025
【図１１】
0004092920.tif 000026
【図１２】
0004092920.tif 000027
【図１３】
0004092920.tif 000028
【図１４】
0004092920.tif 000029
【図１５】
0004092920.tif 000030
【図１６】
0004092920.tif 000031
【図１７】
0004092920.tif 000032
【図１８】
0004092920.tif 000033
【図１９】
0004092920.tif 000034
【図２０】
0004092920.tif 000035
【図２１】
0004092920.tif 000036
【図２２】
0004092920.tif 000037
【図２３】
0004092920.tif 000038
【図２４】
0004092920.tif 000039
【図２５】
0004092920.tif 000040