(57)【特許請求の範囲】
【請求項１】
確率公開鍵暗号方式によって暗号化された確率公開鍵暗号文の列の指数係数の列による冪乗剰余積の前記各指数係数の値が、指定された区間内にあることを証明するための証明文を作成し、かつ前記証明文に基づいて前記各指数係数の値が前記指定された区間内にあることを検証する証明システムにおいて、
前記確率公開鍵暗号方式の公開鍵と、前記指定された区間を定める上限値および下限値と、前記確率公開鍵暗号文の列と、前記指数係数の列と、正しく検証される確率を規定する安全変数の値とに基づいて、前記各指数係数の値の解読困難性を失うことなく前記各指数係数の値が前記指定された区間内にあるか否かを判定するための前記証明文を作成する証明文作成装置と、
検証対象の前記冪乗剰余積と、指定された範囲を定める前記上限値および下限値と、前記確率公開鍵暗号方式の公開鍵および秘密鍵と、前記安全変数と、前記確率公開鍵暗号文の列と、前記確率公開鍵暗号文の列の暗号化に使われた乱数の列と、前記証明文とに基づいて、前記冪乗剰余積の各指数係数の値が前記指定された区間内にあるか否かを、前記安全変数で規定される以上の確率で検証する検証装置とを備えた証明システム。
【請求項２】
前記証明文作成装置は、
前記指数係数の列の各指数係数の値から前記下限値を減算した列である下限値との差の列と、前記上限値から前記指数係数の列の各指数係数の値を減算した列である上限値との差の列とを生成する両端値との差の列の生成部と、
前記下限値との差の列および前記上限値との差の列の各要素の値に安全変数及び区間を定める値により定められる第１の値を乗じて、拡大された下限値との差の列と拡大された上限値との差の列とを生成する拡大部と、
前記拡大された下限値との差の列および前記拡大された上限値との差の列の各要素に対して、それぞれその値より小さい最大の平方数と、各要素の値から対応する前記平方数を減算した差の値とを算出することにより、前記拡大された下限値との差の列および前記拡大された上限値との差の列を、前記平方数の列と前記差の値の列とに分割する分割部と、
前記確率公開鍵暗号文の列の前記下限値に対応する前記平方数の列による第１の冪乗剰余積と、前記確率公開鍵暗号文の列の前記上限値に対応する前記平方数の列による第２の冪乗剰余積とを求め、前記第１および第２の冪乗剰余積の指数係数の列が平方数であることと、その平方根が前記安全変数と区間を定める定数で定められる第２の値を超えないこととの証明文を生成する平方数の証明部と、
前記確率公開鍵暗号文の列の前記下限値に対応する前記差の値の列による第３の冪乗剰余積と、前記確率公開鍵暗号文の列の前記上限値に対応する前記差の値の列による第４の冪乗剰余積とを求め、前記第３および第４の冪乗剰余積の各指数係数の値の絶対値が前記第１の値より小さいことの証明文を生成する絶対値の大きさの証明部とを含む請求項１記載の証明システム。
【請求項３】
前記検証装置は、
前記確率公開鍵暗号文の列の全ての要素の積に前記下限値を乗じた値を求め、この値で、検証対象の前記冪乗剰余積を、公開鍵である元の２乗を法として割り、それを前記第１の値を使って拡大した値を求め、この値が、前記第１の冪乗剰余積と前記第３の冪乗剰余積との積に等しいことを確認し、且つ、前記確率公開鍵暗号文の列の全ての要素の積に前記上限値を乗じた値を求め、この値で、検証対象の前記冪乗剰余積を、公開鍵である元の２乗を法として割り、それを前記第１の値を使って拡大した値を求め、この値が、前記第２の冪乗剰余積と前記第４の冪乗剰余積との積に等しいことを確認し、前記二つの確認ができれば分割の検証受理を出力する分割検証部と、
前記第１の冪乗剰余積の各指数係数の値が平方数であることと、その平方根が前記第２の値を超えないことを検証し、且つ、前記第２の冪乗剰余積の各指数係数の値が平方数であることと、その平方根が前記第２の値を超えないことを検証し、前記二つの検証ができれば平方数の検証受理を出力する平方数の検証部と、
前記第３の冪乗剰余積の各指数係数の値が前記第１の値を超えないことを検証し、且つ、前記第４の冪乗剰余積の各指数係数の値が前記第１の値を超えないことを検証し、前記二つの検証ができれば絶対値の大きさの検証受理を出力する絶対値の大きさの検証部とを含む請求項２記載の証明システム。
【請求項４】
前記平方数の証明部は、
前記第１および第２の冪乗剰余積を生成する暗号化部と、
前記下限値に対応する第１の乱数列と前記上限値に対応する第２の乱数列とを生成する乱数生成部と、
前記下限値に対応する前記平方数の列の各要素の平方根と前記下限値に対応する第１の乱数列の各要素と2とを乗じた数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第５の冪乗剰余積と、前記上限値に対応する前記平方数の列の各要素の平方根と前記第２の乱数列の各要素と2とを乗じた数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第６の冪乗剰余積とを生成する冪乗剰余積生成部と、
前記下限値に対応する前記第１の乱数列の各要素の平方の数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第７の冪乗剰余積と、前記上限値に対応する前記第２の乱数列の各要素の平方の数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第８の冪乗剰余積とを生成する乱数の冪乗剰余積生成部と、
前記公開鍵、前記確率公開鍵暗号文の列、前記第１、第５および第７の冪乗剰余積を入力に含むハッシュ関数の出力である下限値に対応する第１の挑戦値と、前記公開鍵、前記確率公開鍵暗号文の列、前記第２、第６および第８の冪乗剰余積を入力に含むハッシュ関数の出力である上限値に対応する第２の挑戦値とを生成する挑戦値生成部と、
前記下限値に対応する前記第１の乱数列の各要素と下限値に対応する前記平方数の列の各要素の平方根と第１の挑戦値の積の列との、和の列である下限値に対応する第１の応答と、前記上限値に対応する前記第２の乱数列の各要素と上限値に対応する前記平方数の列の各要素の平方根と前記第１の挑戦値の積の列との、和の列である上限値に対応する第２の応答とを生成する応答生成部と、
前記第１の応答の要素全てが、安全変数と区間の大きさと前記第１の挑戦値より定められる定数により定められる第１の区間の中にないか、前記第２の応答の要素全てが、安全変数と区間の大きさと第２の挑戦値より定められる定数により定められる第２の区間の中になければ、平方数の証明を最初からやり直す大きさ確認部とを含む請求項２記載の証明システム。
【請求項５】
前記平方数の検証部は、
前記第１の挑戦値と前記第２の挑戦値とを生成する挑戦値生成部と、
前記第１、第２、第５、第６、第７、第８の冪乗剰余積それぞれの平文である第１、第２、第５、第６、第７、第８の平文を前記秘密鍵により生成する復号部と、
前記第１、第２、第５、第６、第７、第８の冪乗剰余積それぞれを生成するのに用いた乱数である第１、第２、第５、第６、第７、第８の乱数を秘密鍵により生成する乱数生成部と、
前記第１の応答の要素全てが前記第１の区間の中にあるかと、前記第２の応答の要素全てが前記第２の区間の中にあるかとを確認する大きさ確認部と、
前記確率公開鍵暗号文の列の平文と前記確率公開鍵暗号文の生成に用いられた乱数とを用いて、前記下限値に対応する前記第１の挑戦値の2次式と前記第１の応答の2次式を用いた第１の検証式が成り立つことと、前記上限値に対応する第２の挑戦値の2次式と前記第２の応答の2次式を用いた第２の検証式が成り立つことを確認する2次式による検証部とを含む請求項４記載の証明システム。
【請求項６】
前記絶対値の大きさの証明部は、
第３および第４の冪乗剰余積を生成する暗号化部と、
前記下限値に対応する第３の乱数列と上限値に対応する第４の乱数列を生成する乱数生成部と、
前記下限値に対応する前記第３の乱数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第９の冪乗剰余積と、前記上限値に対応する前記第４の乱数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第１０の冪乗剰余積とを生成する冪乗剰余積生成部と、
前記公開鍵、前記確率公開鍵暗号文の列、前記第３および第９の冪乗剰余積とを入力に含むハッシュ関数の出力である下限値に対応する第３の挑戦値と、前記公開鍵、前記確率公開鍵暗号文の列、前記第４および第１０の冪乗剰余積とを入力に含むハッシュ関数の出力である上限値に対応する第４の挑戦値とを生成する挑戦値生成部と、
下限値に対応する前記第３の乱数列の各要素と下限値に対応する前記平方数との差の列と下限値に対応する前記第３の挑戦値の積の列との、和の列である下限値に対応する第３の応答と、上限値に対応する前記第４の乱数列の各要素と前記上限値に対応する前記平方数との差の列と上限値に対応する前記第４の挑戦値の積の列との、和の列である上限値に対応する第４の応答とを生成する応答生成部と、
前記第３の応答の要素全てが、安全変数と区間の大きさと前記第３の挑戦値より定められる定数により定められる第３の区間の中にないか、前記第４の応答の要素全てが、安全変数と区間の大きさと前記第４の挑戦値より定められる定数により定められる第４の区間の中になければ、絶対値の大きさの証明処理を最初からやり直す大きさ確認部とを備えた請求項４記載の証明システム。
【請求項７】
前記絶対値の大きさの検証部は、
前記第３の挑戦値と前記第４の挑戦値とを生成する挑戦値生成部と、
前記第３、第４、第９および第１０の冪乗剰余積のそれぞれの平文である第３、第４、第９および第１０の平文を秘密鍵により生成する復号部と、
前記第３、第４、第９、第１０の冪乗剰余積を生成するのに用いられた第３、第４、第９および第１０の乱数を秘密鍵により生成する乱数生成部と、
前記第３の応答の要素全てが前記第３の区間の中にあるかと、前記第４の応答の要素全てが前記第４の区間の中にあるかとを確認する大きさ確認部と、
下限値に対応する前記第３の挑戦値の1次式と前記第３の応答の1次式を用いた第３の検証式が成り立つことと、上限値に対応する前記第４の挑戦値の１次式と前記第４の応答の１次式を用いた第４の検証式が成り立つことを確認する1次式による検証部とを含む請求項６記載の証明システム。
【請求項８】
確率公開鍵暗号方式によって暗号化された確率公開鍵暗号文の列の指数係数の列による冪乗剰余積の前記各指数係数の値が、指定された区間内にあることを証明するための証明文を作成し、かつ前記証明文に基づいて前記各指数係数の値が前記指定された区間内にあることを検証する証明方法において、
証明文作成装置が、前記確率公開鍵暗号方式の公開鍵と、前記指定された区間を定める上限値および下限値と、前記確率公開鍵暗号文の列と、前記指数係数の列と、正しく検証される確率を規定する安全変数の値とに基づいて、前記各指数係数の値の解読困難性を失うことなく前記各指数係数の値が前記指定された区間内にあるか否かを判定するための前記証明文を作成する証明文作成ステップと、
検証装置が、検証対象の前記冪乗剰余積と、指定された範囲を定める前記上限値および下限値と、前記確率公開鍵暗号方式の公開鍵および秘密鍵と、前記安全変数と、前記確率公開鍵暗号文の列と、前記確率公開鍵暗号文の列の暗号化に使われた乱数の列と、前記証明文とに基づいて、前記冪乗剰余積の各指数係数の値が前記指定された区間内にあるか否かを、前記安全変数で規定される以上の確率で検証する検証ステップとを含む証明方法。
【請求項９】
前記証明文作成ステップは、
前記証明文作成装置の両端値との差の列の生成部が、前記指数係数の列の各指数係数の値から前記下限値を減算した列である下限値との差の列と、前記上限値から前記指数係数の列の各指数係数の値を減算した列である上限値との差の列とを生成する両端値との差の列の生成ステップと、
前記証明文作成装置の拡大部が、前記下限値との差の列および前記上限値との差の列の各要素の値に安全変数及び区間を定める値により定められる第１の値を乗じて、拡大された下限値との差の列と拡大された上限値との差の列とを生成する拡大ステップと、
前記証明文作成装置の分割部が、前記拡大された下限値との差の列および前記拡大された上限値との差の列の各要素に対して、それぞれその値より小さい最大の平方数と、各要素の値から対応する前記平方数を減算した差の値とを算出することにより、前記拡大された下限値との差の列および前記拡大された上限値との差の列を、前記平方数の列と前記差の値の列とに分割する分割ステップと、
前記証明文作成装置の平方数の証明部が、前記確率公開鍵暗号文の列の前記下限値に対応する前記平方数の列による第１の冪乗剰余積と、前記確率公開鍵暗号文の列の前記上限値に対応する前記平方数の列による第２の冪乗剰余積とを求め、前記第１および第２の冪乗剰余積の指数係数の列が平方数であることと、その平方根が前記安全変数と区間を定める定数で定められる第２の値を超えないこととの証明文を生成する平方数の証明ステップと、
前記証明文作成装置の絶対値の大きさの証明部が、前記確率公開鍵暗号文の列の前記下限値に対応する前記差の値の列による第３の冪乗剰余積と、前記確率公開鍵暗号文の列の前記上限値に対応する前記差の値の列による第４の冪乗剰余積とを求め、前記第３および第４の冪乗剰余積の各指数係数の値の絶対値が前記第１の値より小さいことの証明文を生成する絶対値の大きさの証明ステップとを含む請求項８記載の証明方法。
【請求項１０】
前記検証ステップは、
前記検証装置の分割検証部が、前記確率公開鍵暗号文の列の全ての要素の積に前記下限値を乗じた値を求め、この値で、検証対象の前記冪乗剰余積を、公開鍵である元の２乗を法として割り、それを前記第１の値を使って拡大した値を求め、この値が、前記第１の冪乗剰余積と前記第３の冪乗剰余積との積に等しいことを確認し、且つ、前記確率公開鍵暗号文の列の全ての要素の積に前記上限値を乗じた値を求め、この値で、検証対象の前記冪乗剰余積を、公開鍵である元の２乗を法として割り、それを前記第１の値を使って拡大した値を求め、この値が、前記第２の冪乗剰余積と前記第４の冪乗剰余積との積に等しいことを確認し、前記二つの確認ができれば分割の検証受理を出力する分割検証ステップと、
前記検証装置の平方数の検証部が、前記第１の冪乗剰余積の各指数係数の値が平方数であることと、その平方根が前記第２の値を超えないことを検証し、且つ、前記第２の冪乗剰余積の各指数係数の値が平方数であることと、その平方根が前記第２の値を超えないことを検証し、前記二つの検証ができれば平方数の検証受理を出力する平方数の検証ステップと、
前記検証装置の絶対値の大きさの検証部が、前記第３の冪乗剰余積の各指数係数の値が前記第１の値を超えないことを検証し、且つ、前記第４の冪乗剰余積の各指数係数の値が前記第１の値を超えないことを検証し、前記二つの検証ができれば絶対値の大きさの検証受理を出力する絶対値の大きさの検証ステップとを含む請求項９記載の証明方法。
【請求項１１】
前記平方数の証明ステップは、
前記平方数の証明部の暗号化部が、前記第１および第２の冪乗剰余積を生成する暗号化ステップと、
前記平方数の証明部の乱数生成部が、前記下限値に対応する第１の乱数列と前記上限値に対応する第２の乱数列とを生成する乱数生成ステップと、
前記平方数の証明部の冪乗剰余積生成部が、前記下限値に対応する前記平方数の列の各要素の平方根と前記下限値に対応する第１の乱数列の各要素と2とを乗じた数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第５の冪乗剰余積と、前記上限値に対応する前記平方数の列の各要素の平方根と前記第２の乱数列の各要素と2とを乗じた数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第６の冪乗剰余積とを生成する冪乗剰余積生成ステップと、
前記平方数の証明部の乱数の冪乗剰余積生成部が、前記下限値に対応する前記第１の乱数列の各要素の平方の数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第７の冪乗剰余積と、前記上限値に対応する前記第２の乱数列の各要素の平方の数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第８の冪乗剰余積とを生成する乱数の冪乗剰余積生成ステップと、
前記平方数の証明部の挑戦値生成部が、前記公開鍵、前記確率公開鍵暗号文の列、前記第１、第５および第７の冪乗剰余積を入力に含むハッシュ関数の出力である下限値に対応する第１の挑戦値と、前記公開鍵、前記確率公開鍵暗号文の列、前記第２、第６および第８の冪乗剰余積を入力に含むハッシュ関数の出力である上限値に対応する第２の挑戦値とを生成する挑戦値生成ステップと、
前記平方数の証明部の応答生成部が、前記下限値に対応する前記第１の乱数列の各要素と下限値に対応する前記平方数の列の各要素の平方根と第１の挑戦値の積の列との、和の列である下限値に対応する第１の応答と、前記上限値に対応する前記第２の乱数列の各要素と上限値に対応する前記平方数の列の各要素の平方根と前記第１の挑戦値の積の列との、和の列である上限値に対応する第２の応答とを生成する応答生成ステップと、
前記平方数の証明部の大きさ確認部が、前記第１の応答の要素全てが、安全変数と区間の大きさと前記第１の挑戦値より定められる定数により定められる第１の区間の中にないか、前記第２の応答の要素全てが、安全変数と区間の大きさと第２の挑戦値より定められる定数により定められる第２の区間の中になければ、平方数の証明を最初からやり直す大きさ確認ステップとを含む請求項９記載の証明方法。
【請求項１２】
前記平方数の検証ステップは、
前記平方数の検証部の挑戦値生成部が、前記第１の挑戦値と前記第２の挑戦値とを生成する挑戦値生成ステップと、
前記平方数の検証部の復号部が、前記第１、第２、第５、第６、第７、第８の冪乗剰余積それぞれの平文である第１、第２、第５、第６、第７、第８の平文を前記秘密鍵により生成する復号ステップと、
前記平方数の検証部の乱数生成部が、前記第１、第２、第５、第６、第７、第８の冪乗剰余積それぞれを生成するのに用いた乱数である第１、第２、第５、第６、第７、第８の乱数を秘密鍵により生成する乱数生成ステップと、
前記平方数の検証部の大きさ確認部が、前記第１の応答の要素全てが前記第１の区間の中にあるかと、前記第２の応答の要素全てが前記第２の区間の中にあるかとを確認する大きさ確認ステップと、
前記平方数の検証部の2次式による検証部が、前記確率公開鍵暗号文の列の平文と前記確率公開鍵暗号文の生成に用いられた乱数とを用いて、前記下限値に対応する前記第１の挑戦値の2次式と前記第１の応答の2次式を用いた第１の検証式が成り立つことと、前記上限値に対応する第２の挑戦値の2次式と前記第２の応答の2次式を用いた第２の検証式が成り立つことを確認する2次式による検証ステップとを含む請求項１１記載の証明方法。
【請求項１３】
前記絶対値の大きさの証明ステップは、
前記絶対値の大きさの証明部の暗号化部が、第３および第４の冪乗剰余積を生成する暗号化ステップと、
前記絶対値の大きさの証明部の乱数生成部が、前記下限値に対応する第３の乱数列と上限値に対応する第４の乱数列を生成する乱数生成ステップと、
前記絶対値の大きさの証明部の冪乗剰余積生成部が、前記下限値に対応する前記第３の乱数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第９の冪乗剰余積と、前記上限値に対応する前記第４の乱数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第１０の冪乗剰余積とを生成する冪乗剰余積生成ステップと、
前記絶対値の大きさの証明部の挑戦値生成部が、前記公開鍵、前記確率公開鍵暗号文の列、前記第３および第９の冪乗剰余積とを入力に含むハッシュ関数の出力である下限値に対応する第３の挑戦値と、前記公開鍵、前記確率公開鍵暗号文の列、前記第４および第１０の冪乗剰余積とを入力に含むハッシュ関数の出力である上限値に対応する第４の挑戦値とを生成する挑戦値生成ステップと、
前記絶対値の大きさの証明部の応答生成部が、下限値に対応する前記第３の乱数列の各要素と下限値に対応する前記平方数との差の列と下限値に対応する前記第３の挑戦値の積の列との、和の列である下限値に対応する第３の応答と、上限値に対応する前記第４の乱数列の各要素と前記上限値に対応する前記平方数との差の列と上限値に対応する前記第４の挑戦値の積の列との、和の列である上限値に対応する第４の応答とを生成する応答生成ステップと、
前記絶対値の大きさの証明部の大きさ確認部が、前記第３の応答の要素全てが、安全変数と区間の大きさと前記第３の挑戦値より定められる定数により定められる第３の区間の中にないか、前記第４の応答の要素全てが、安全変数と区間の大きさと前記第４の挑戦値より定められる定数により定められる第４の区間の中になければ、絶対値の大きさの証明処理を最初からやり直す大きさ確認ステップとを含む請求項１１記載の証明方法。
【請求項１４】
前記絶対値の大きさの検証ステップは、
前記絶対値の大きさの検証部の挑戦値生成部が、前記第３の挑戦値と前記第４の挑戦値とを生成する挑戦値生成ステップと、
前記絶対値の大きさの検証部の復号部が、前記第３、第４、第９および第１０の冪乗剰余積のそれぞれの平文である第３、第４、第９および第１０の平文を秘密鍵により生成する復号ステップと、
前記絶対値の大きさの検証部の乱数生成部が、前記第３、第４、第９、第１０の冪乗剰余積を生成するのに用いられた第３、第４、第９および第１０の乱数を秘密鍵により生成する乱数生成ステップと、
前記絶対値の大きさの検証部の大きさ確認部が、前記第３の応答の要素全てが前記第３の区間の中にあるかと、前記第４の応答の要素全てが前記第４の区間の中にあるかとを確認する大きさ確認ステップと、
前記絶対値の大きさの検証部の1次式による検証部が、下限値に対応する前記第３の挑戦値の1次式と前記第３の応答の1次式を用いた第３の検証式が成り立つことと、上限値に対応する前記第４の挑戦値の１次式と前記第４の応答の１次式を用いた第４の検証式が成り立つことを確認する1次式による検証ステップとを含む請求項１３記載の証明方法。
【請求項１５】
確率公開鍵暗号方式によって暗号化された確率公開鍵暗号文の列の指数係数の列による冪乗剰余積の前記各指数係数の値が、指定された区間内にあることを証明するための証明文を作成し、かつ前記証明文に基づいて前記各指数係数の値が前記指定された区間内にあることを検証する証明システムを構成するコンピュータを、
前記確率公開鍵暗号方式の公開鍵と、前記指定された区間を定める上限値および下限値と、前記確率公開鍵暗号文の列と、前記指数係数の列と、正しく検証される確率を規定する安全変数の値とに基づいて、前記各指数係数の値の解読困難性を失うことなく前記各指数係数の値が前記指定された区間内にあるか否かを判定するための前記証明文を作成する証明文作成装置、
検証対象の前記冪乗剰余積と、指定された範囲を定める前記上限値および下限値と、前記確率公開鍵暗号方式の公開鍵および秘密鍵と、前記安全変数と、前記確率公開鍵暗号文の列と、前記確率公開鍵暗号文の列の暗号化に使われた乱数の列と、前記証明文とに基づいて、前記冪乗剰余積の各指数係数の値が前記指定された区間内にあるか否かを、前記安全変数で規定される以上の確率で検証する検証装置、
として機能させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、確率公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることを各指数係数の値を隠したまま証明する技術とその検証技術に関し、特に証明する主体に対しては秘密鍵が秘密にされていて、検証する主体が秘密鍵を所持している場合の技術に関する。
【０００２】
【従来の技術】
従来、特定の値が定められた区間にあることを、その値を隠したまま証明する技術について、例えばファブリーチェブード(Fabrice Boudot)による方式がある。これは文献「エフィシエント プルーフス ザット ア コミッテッド ナンバー ライズ イン アン インターバル、アドバンス イン クリプトロジー、プロシーヂング オブ ユーロクリプト２０００、エルエヌシーエス１８０７、シュプリンガーフェアラーグ、４３１ページから４４４ページまで、２０００年(Efficient Proofs that a Committed Number Lies in an Interval、Advance in Cryptology、Proceeding of Eurocrypt'2000、LNCS1807、Springer-Verlag、pp．431-444、2000)」に開示されている。この方式を以下、単に従来技術と称す。この従来技術では、与えられた値を、乱数を用いてコミットし、その値が定められた区間内にあることを、その値を隠したまま証明する。
【０００３】
以下に、図面を参照してこの従来の技術の概略を説明する。図１７は、この従来技術における、特定の数値が定められた区間にあることを、その特定の数値を隠したまま証明するための証明文を作成する証明文作成装置の構成を説明するためのブロック図である。
【０００４】
図１７においては、証明文の上半分（６３１−１、６３１−２)を導く過程が点線により省略されているが、これは以下に説明する下半分（６３１−４、６３１−５)を導く過程と全く同様にして導くことができる。
【０００５】
ここでの「xをコミットする」とは、一方向性関数にｘがと場合により乱数とが入力された結果を公開することであり、この結果をコミットメントと呼ぶ。一方向性関数の性質より、ｘのコミットメントよりｘを求めることはできず、また、同じコミットメントを与えるｘ以外の入力を求めることも困難となる。
【０００６】
合成数nを、証明者、検証者のいずれも知らない（十分に大きな)2つの素数p、ｑの積であるとする。g、hを、乗法群Z*nの要素で、互いを底とする離散対数のどちらも証明者と検証者は知らないとする。
【０００７】
証明者は、まず図１７の６１１に示されるように、コメットされる数６０１（被コミット数)である“x”と、そのコミットメントに用いる乱数６０２である“ｒ”を用いて、計算した値“ｇｘｈｒ mod n"をxのコミットメント６３１−５として算出する。このxの値が、指定された区間である[a,b]の区間内にあることを、xを秘密にしたまま証明するための証明文を作成する。
【０００８】
そして図１７の６１２において、被コミット数のx、指定された区間を定める定数６０４である下限値a、上限値bのコミットメントから区間の両端値との差x-a(６１３)、b-x(６１４)のコミットメントを計算する。そして図１７の６１５、６１６において、安全変数６０３と定められた区間の大きさから求められる変数Tを用いて、この2つのコミットメントを2T乗し、2T(x-1)、2T(b-x)のコミットメントを計算する。
【０００９】
そして、コミットされた各値2T(x-1)、2T(b-x)を隠したまま（解読困難性を保ったまま)、これらの値が−2Tより大きいことをそれぞれ証明する。x,a,bが整数なので、この証明は、x-a,b-xが正であること、すなわちxが[a,b]の区間内にあることの証明となる。以下ではコミットされた数が−2Tより大きいことを、その数を秘密にしたまま（解読困難性を保ったまま)、検証者に対して証明する方法について述べる。
【００１０】
以下、この秘密の数（つまり、2T(x-1)、２T(b-x)の一方の値)をXとする。vをXの平方根より小さい最大の整数とし、整数ｚをX-v２として取る。
【００１１】
ここで、v２,u,Xをコミットする。検証者は、これらのコミットメントから、コミットされた各数がv２+u＝Xなる関係を満たすことが分かる。
【００１２】
そして、図１７の６２１において、uのコミットメントが、絶対値が2Tより小さい値のコミットメントであることを、uを隠したままで証明するための証明文６３１−４を生成する。更に、図１７の６２２において、v２のコミットメントが、平方数のコミットメントであることを、vを隠したままで証明するための証明文６３１−３を生成する。
【００１３】
正である平方数と、絶対値が2Tより小さい値の和であるXは−2Tより大きくなる。uの絶対値が2Tより小さいことの証明をuの値を隠して行なうためには、uの絶対値は2Tよりずっと小さい必要がある。そのような絶対値の小さなuと平方数との和で[a,b]の区間内にある整数全てが表せるように十分に大きなTを選ぶことによりXの値を隠す。また、これらの証明にはコミットメントを生成するために使った乱数が必要になる。
【００１４】
【発明が解決しようとする課題】
しかしながら、上記した従来技術では、定められた区間内にあることを証明できる数は、一度の証明で一個だけに限定されるという問題がある。この問題点の解決が重要となる例を次に挙げる。
【００１５】
[例]
例として、アンケート式の個人の性格の傾向診断サービスを考える。
主催者は利用者にアンケートを配り、利用者はそれに回答して主催者に返送し、主催者は傾向の有無を利用者に返答する。
ここで利用者のプライバシー保護のため、利用者がどの項目に印をつけたか主催者に分からないようにしたい。
その一方で、主催者は有効な資料を収集するためにも、各項目に対して利用者が選択肢以外の答えを選ぶことを避けたい。また、主催者のノウハウを隠すためや、利用者が結果を意識してアンケートに答えることがないようにするため、アンケートの各項目が診断される傾向に正に働くのか或は負に働くのか利用者に分からないようにしたい。
主催者はアンケートの各質問項目に対応して、1または0をコミットしたもの(g1hrmod nまたはg0hrmod n)のどちらかである要素からなる列を利用者に配る。各コミットメントが1のコミットメントであるか0のコミットメントであるかが対応する質問項目が診断される傾向に正に働くのか或は負に働くのかを決める。乱数rは各コミットメント毎に異なるものを使い、利用者にコミットメントされている数を分からなくする。
利用者は自分の当てはまると思われる質問に対応するコミットメントと任意の乱数r"を選び、それらコミットメントとhr"との積を求め主催者に返送する。
この積はg0+，…，+1hr'+…+r+r"mod nといった形をしており、判断に正に働く項目の質問を利用者が選んだ数がコミットされている。
ここで、各項目に対する答えを送る代わりに全ての積を送ることにより、利用者がどの項目に印をつけたか主催者に分からないようにしている。
【００１６】
[例における問題点]
上記アンケートでは、利用者は特定の項目の答えを重複して答えることができる。例えば、最初の質問に対して主催者がコミットした値g1hrをs個返答の中にいれれば(g1hr)s=gshsrとなるので、最初の質問の答えが最終的な判断に大きく寄与してしまう。
このような返答を許すならば、集めたデータの信頼性は低くなり、主催者にとって価値のないものとなる場合がある。
そこで主催者は、利用者に、全ての質問に対して一回だけ答えたことを証明させたい。しかも、各項目ごとに証明するのでは各項目毎の返事が分るので、一度に全ての項目に関しての証明を求めたい。
このような要求には従来技術では、上記問題が存在する故に、答えることができなかった。
【００１７】
本発明は、上記問題点に鑑みてなされたものであって、その目的は、従来の技術における前記問題を解決することにより、証明者が与えられた暗号文の列から、それぞれの要素を規定の範囲内の個数とりだし、それら全ての積を検証者に送り、証明者はその積の生成にあったってどの暗号文の個数も、規定の範囲内であることを証明する方法、すなわち、確率公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることの証明方法と、検証がこの証明が正しいかを検証する方法と、すなわち、確率公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることの検証方法とを、提供することである。
【００１８】
【課題を解決するための手段】
本発明の第１の証明システムは、確率公開鍵暗号方式によって暗号化された確率公開鍵暗号文の列の指数係数の列による冪乗剰余積の前記各指数係数の値が、指定された区間内にあることを証明するための証明文を作成し、かつ前記証明文に基づいて前記各指数係数の値が前記指定された区間内にあることを検証する証明システムにおいて、
前記確率公開鍵暗号方式の公開鍵と、前記指定された区間を定める上限値および下限値と、前記確率公開鍵暗号文の列と、前記指数係数の列と、正しく検証される確率を規定する安全変数の値とに基づいて、前記各指数係数の値の解読困難性を失うことなく前記各指数係数の値が前記指定された区間内にあるか否かを判定するための前記証明文を作成する証明文作成装置と、
検証対象の前記冪乗剰余積と、指定された範囲を定める前記上限値および下限値と、前記確率公開鍵暗号方式の公開鍵および秘密鍵と、前記安全変数と、前記確率公開鍵暗号文の列と、前記確率公開鍵暗号文の列の暗号化に使われた乱数の列と、前記証明文とに基づいて、前記冪乗剰余積の各指数係数の値が前記指定された区間内にあるか否かを、前記安全変数で規定される以上の確率で検証する検証装置とを備えている。
【００１９】
本発明の第２の証明システムにおいては、前記証明文作成装置は、
前記指数係数の列の各指数係数の値から前記下限値を減算した列である下限値との差の列と、前記上限値から前記指数係数の列の各指数係数の値を減算した列である上限値との差の列とを生成する両端値との差の列の生成部と、
前記下限値との差の列および前記上限値との差の列の各要素の値に安全変数及び区間を定める値により定められる第１の値を乗じて、拡大された下限値との差の列と拡大された上限値との差の列とを生成する拡大部と、
前記拡大された下限値との差の列および前記拡大された上限値との差の列の各要素に対して、それぞれその値より小さい最大の平方数と、各要素の値から対応する前記平方数を減算した差の値とを算出することにより、前記拡大された下限値との差の列および前記拡大された上限値との差の列を、前記平方数の列と前記差の値の列とに分割する分割部と、
前記確率公開鍵暗号文の列の前記下限値に対応する前記平方数の列による第１の冪乗剰余積と、前記確率公開鍵暗号文の列の前記上限値に対応する前記平方数の列による第２の冪乗剰余積とを求め、前記第１および第２の冪乗剰余積の指数係数の列が平方数であることと、その平方根が前記安全変数と区間を定める定数で定められる第２の値を超えないこととの証明文を生成する平方数の証明部と、
前記確率公開鍵暗号文の列の前記下限値に対応する前記差の値の列による第３の冪乗剰余積と、前記確率公開鍵暗号文の列の前記上限値に対応する前記差の値の列による第４の冪乗剰余積とを求め、前記第３および第４の冪乗剰余積の各指数係数の値の絶対値が前記第１の値より小さいことの証明文を生成する絶対値の大きさの証明部とを含んでいる。
【００２０】
本発明の第３の証明システムでは、前記検証装置は、
前記確率公開鍵暗号文の列の全ての要素の積に前記下限値を乗じた値を求め、この値で、検証対象の前記冪乗剰余積を、公開鍵である元の２乗を法として割り、それを前記第１の値を使って拡大した値を求め、この値が、前記第１の冪乗剰余積と前記第３の冪乗剰余積との積に等しいことを確認し、且つ、前記確率公開鍵暗号文の列の全ての要素の積に前記上限値を乗じた値を求め、この値で、検証対象の前記冪乗剰余積を、公開鍵である元の２乗を法として割り、それを前記第１の値を使って拡大した値を求め、この値が、前記第２の冪乗剰余積と前記第４の冪乗剰余積との積に等しいことを確認し、前記二つの確認ができれば分割の検証受理を出力する分割検証部と、
前記第１の冪乗剰余積の各指数係数の値が平方数であることと、その平方根が前記第２の値を超えないことを検証し、且つ、前記第２の冪乗剰余積の各指数係数の値が平方数であることと、その平方根が前記第２の値を超えないことを検証し、前記二つの検証ができれば平方数の検証受理を出力する平方数の検証部と、
前記第３の冪乗剰余積の各指数係数の値が前記第１の値を超えないことを検証し、且つ、前記第４の冪乗剰余積の各指数係数の値が前記第１の値を超えないことを検証し、前記二つの検証ができれば絶対値の大きさの検証受理を出力する絶対値の大きさの検証部とを含んでいる。
【００２１】
本発明の第４の証明システムでは、前記平方数の証明部は、
前記第１および第２の冪乗剰余積を生成する暗号化部と、
前記下限値に対応する第１の乱数列と前記上限値に対応する第２の乱数列とを生成する乱数生成部と、
前記下限値に対応する前記平方数の列の各要素の平方根と前記下限値に対応する第１の乱数列の各要素と2とを乗じた数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第５の冪乗剰余積と、前記上限値に対応する前記平方数の列の各要素の平方根と前記第２の乱数列の各要素と2とを乗じた数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第６の冪乗剰余積とを生成する冪乗剰余積生成部と、
前記下限値に対応する前記第１の乱数列の各要素の平方の数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第７の冪乗剰余積と、前記上限値に対応する前記第２の乱数列の各要素の平方の数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第８の冪乗剰余積とを生成する乱数の冪乗剰余積生成部と、
前記公開鍵、前記確率公開鍵暗号文の列、前記第１、第５および第７の冪乗剰余積を入力に含むハッシュ関数の出力である下限値に対応する第１の挑戦値と、前記公開鍵、前記確率公開鍵暗号文の列、前記第２、第６および第８の冪乗剰余積を入力に含むハッシュ関数の出力である上限値に対応する第２の挑戦値とを生成する挑戦値生成部と、
前記下限値に対応する前記第１の乱数列の各要素と下限値に対応する前記平方数の列の各要素の平方根と第１の挑戦値の積の列との、和の列である下限値に対応する第１の応答と、前記上限値に対応する前記第２の乱数列の各要素と上限値に対応する前記平方数の列の各要素の平方根と前記第１の挑戦値の積の列との、和の列である上限値に対応する第２の応答とを生成する応答生成部と、
前記第１の応答の要素全てが、安全変数と区間の大きさと前記第１の挑戦値より定められる定数により定められる第１の区間の中にないか、前記第２の応答の要素全てが、安全変数と区間の大きさと第２の挑戦値より定められる定数により定められる第２の区間の中になければ、平方数の証明を最初からやり直す大きさ確認部とを含んでいる。
【００２２】
本発明の第５の証明システムでは、前記平方数の検証部は、
前記第１の挑戦値と前記第２の挑戦値とを生成する挑戦値生成部と、
前記第１、第２、第５、第６、第７、第８の冪乗剰余積それぞれの平文である第１、第２、第５、第６、第７、第８の平文を前記秘密鍵により生成する復号部と、
前記第１、第２、第５、第６、第７、第８の冪乗剰余積それぞれを生成するのに用いた乱数である第１、第２、第５、第６、第７、第８の乱数を秘密鍵により生成する乱数生成部と、
前記第１の応答の要素全てが前記第１の区間の中にあるかと、前記第２の応答の要素全てが前記第２の区間の中にあるかとを確認する大きさ確認部と、
前記確率公開鍵暗号文の列の平文と前記確率公開鍵暗号文の生成に用いられた乱数とを用いて、前記下限値に対応する前記第１の挑戦値の2次式と前記第１の応答の2次式を用いた第１の検証式が成り立つことと、前記上限値に対応する第２の挑戦値の2次式と前記第２の応答の2次式を用いた第２の検証式が成り立つことを確認する2次式による検証部とを含んでいる。
【００２３】
本発明の第６の証明システムでは、前記絶対値の大きさの証明部は、
第３および第４の冪乗剰余積を生成する暗号化部と、
前記下限値に対応する第３の乱数列と上限値に対応する第４の乱数列を生成する乱数生成部と、
前記下限値に対応する前記第３の乱数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第９の冪乗剰余積と、前記上限値に対応する前記第４の乱数列による、前記確率公開鍵暗号文の列の冪乗剰余積である第１０の冪乗剰余積とを生成する冪乗剰余積生成部と、
前記公開鍵、前記確率公開鍵暗号文の列、前記第３および第９の冪乗剰余積とを入力に含むハッシュ関数の出力である下限値に対応する第３の挑戦値と、前記公開鍵、前記確率公開鍵暗号文の列、前記第４および第１０の冪乗剰余積とを入力に含むハッシュ関数の出力である上限値に対応する第４の挑戦値とを生成する挑戦値生成部と、
下限値に対応する前記第３の乱数列の各要素と下限値に対応する前記平方数との差の列と下限値に対応する前記第３の挑戦値の積の列との、和の列である下限値に対応する第３の応答と、上限値に対応する前記第４の乱数列の各要素と前記上限値に対応する前記平方数との差の列と上限値に対応する前記第４の挑戦値の積の列との、和の列である上限値に対応する第４の応答とを生成する応答生成部と、
前記第３の応答の要素全てが、安全変数と区間の大きさと前記第３の挑戦値より定められる定数により定められる第３の区間の中にないか、前記第４の応答の要素全てが、安全変数と区間の大きさと前記第４の挑戦値より定められる定数により定められる第４の区間の中になければ、絶対値の大きさの証明処理を最初からやり直す大きさ確認部とを備えている。
【００２４】
本発明の第７の証明システムでは、前記絶対値の大きさの検証部は、
前記第３の挑戦値と前記第４の挑戦値とを生成する挑戦値生成部と、
前記第３、第４、第９および第１０の冪乗剰余積のそれぞれの平文である第３、第４、第９および第１０の平文を秘密鍵により生成する復号部と、
前記第３、第４、第９、第１０の冪乗剰余積を生成するのに用いられた第３、第４、第９および第１０の乱数を秘密鍵により生成する乱数生成部と、
前記第３の応答の要素全てが前記第３の区間の中にあるかと、前記第４の応答の要素全てが前記第４の区間の中にあるかとを確認する大きさ確認部と、
下限値に対応する前記第３の挑戦値の1次式と前記第３の応答の1次式を用いた第３の検証式が成り立つことと、上限値に対応する前記第４の挑戦値の１次式と前記第４の応答の１次式を用いた第４の検証式が成り立つことを確認する1次式による検証部とを含んでいる。
【００２５】
【発明の実施の形態】
図１を参照すると、本発明の確率公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることの証明システムの一実施の形態は、検証者端末１０１と証明者端末１０２とで構成され、両者は公衆回線網、専用回線網あるいはインターネット等のネットワーク１０３を通じて相互に通信可能になっている。
【００２６】
証明者端末１０２は、確率公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることを証明する証明者が使用する端末であり、検証者端末１０１は、確率公開鍵暗号文の冪乗剰余積の各指数係数が区間内にあることを検証する検証者が使用する端末である。証明者端末１０２としては、パーソナルコンピュータや携帯情報端末等の情報処理装置で実現することができる。また、検証者端末１０１としては、パーソナルコンピュータやワークステーション等の情報処理装置で実現することができる。
【００２７】
証明者端末１０２は、確率公開鍵暗号文の冪乗剰余積の指数係数の列として使用するデータ列を記憶するデータ記憶手段１１１と、証明処理に必要な情報として検証者端末１０１から公開された情報を記憶しておく公開情報記憶手段１１２と、この公開情報記憶手段１１２に記憶された公開情報とデータ記憶手段１１１に記憶されたデータとから、冪乗剰余積の形式を有する確率公開鍵暗号文であってその指数係数の列としてデータ記憶手段１１１に記憶されたデータ列を用いた確率公開鍵暗号文と、この確率公開鍵暗号文の冪乗剰余積の各指数係数の値が指定された区間にあることの証明文とを生成して、ネットワーク１０３経由で検証者端末１０１へ送信する証明文作成装置１１３と、ネットワーク１０３経由で検証者端末１０１から送られてくる処理結果を受信する処理結果受信装置１１４と、利用者からの指示やデータを入力するキーボード等の入力装置および検証者端末１０１からの応答内容などの表示や出力を行う出力装置を備える出力装置１１５とを含んで構成される。
【００２８】
検証者端末１０１は、システムの運用に先立って証明および検証に必要となる各種の情報を生成し、そのうち公開すべき情報は公開情報として証明者端末１０２に公開し、秘密情報は公開情報と共に検証者端末１０１側に保存する情報設定公開手段１２１と、この情報設定公開手段１２１で生成された秘密情報および公開情報を記憶しておく情報記憶手段１２２と、冪乗剰余積の形式を有する確率公開鍵暗号文とこの確率公開鍵暗号文の冪乗剰余積の各指数係数の値が指定された区間にあることの証明文とを証明者端末１０２から受信し、その証明文と情報記憶手段１２２に記憶されている情報とに基づいて、受信した確率公開鍵暗号文の冪乗剰余積の各指数係数の値が指定された区間にあることを検証する検証装置１２３と、この検証装置１２３で検証された確率公開鍵暗号文を復号して得た平文の内容に基づいて所定の処理を実行し、その結果をネットワーク１０３経由で証明者端末１０２へ通知する処理装置１２４とを含んで構成される。
【００２９】
記録媒体１５１、記録媒体１５２は、磁気ディスク装置、半導体メモリ、ＣＤ−ＲＯＭ等のコンピュータ可読記録媒体であり、それぞれ検証者端末用プログラム、証明者端末用プログラムが記録されている。記録媒体１５１に記録された検証者端末用プログラムは、検証者端末１０１を構成するコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータ上に検証装置１２３および処理装置１２４を実現する。また、記録媒体１５２に記録された証明者端末用プログラムは、証明者端末１０２を構成するコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータ上に証明文作成装置１１３および処理結果受信装置１１４を実現する。
【００３０】
次に図２のフローチャートを参照して本実施の形態の動作を説明する。
【００３１】
システムの運用に先立ち、検証者端末１０１の情報設定公開手段１２１は、証明と検証に必要な所定の公開情報と秘密情報とを生成し、公開情報はネットワーク１０３経由で証明者端末１０２に公開し、秘密情報は公開情報と共に情報記憶手段１２２に保存する（ステップＳ１０１）。証明者端末１０２は、公開情報を受信し、公開情報記憶手段１１２に保存する（ステップＳ２０１）。証明者端末１０２の証明文作成装置１１３は公開情報記憶手段１１２に記憶された公開情報を使って証明文の作成処理を実行し、検証者端末１０１の検証装置１２３は情報記憶手段１２２に記憶された公開情報および秘密情報を使って検証処理を実行する。図２のステップＳ２０２〜Ｓ２０４、Ｓ１０２〜Ｓ１０６は、１つの証明文を証明者端末１０２から検証者端末１０１へ送出した際の処理の流れを示している。証明者端末１０２における証明文の作成は、例えば利用者が入出力装置１１５からデータ記憶手段１１１中のデータ列を指定して作成を指示したときに開始される。
【００３２】
先ず、証明者端末１０２の証明文作成装置１１３は、冪乗剰余積の形式を有し指数係数の列としてデータ記憶手段１１１に記憶されたデータ列を用いた確率公開鍵暗号文を生成する（ステップＳ２０２）。次に、この生成した確率公開鍵暗号文の冪乗剰余積の各指数係数の値が指定された区間にあることの証明文を生成する（ステップＳ２０３）。具体的には、確率公開鍵暗号方式の公開鍵と、指定された区間を定める上限値および下限値と、確率公開鍵暗号文の列と、指数係数の列と、正しく検証される確率を規定する安全変数の値などに基づいて、各指数係数の値の解読困難性を失うことなく各指数係数の値が指定された区間内にあるか否かを判定するための証明文を作成する。そして、生成した確率公開鍵暗号文と証明文とをネットワーク１０３経由で検証者端末１０１へ送信する（ステップＳ２０４）。
【００３３】
証明者端末１０１の検証装置１２３は、証明者端末１０２から確率公開鍵暗号文と証明文とを受信すると（ステップＳ１０２）、受信した証明文と情報記憶手段１２２に記憶されている公開情報および秘密情報とに基づいて、受信した確率公開鍵暗号文の冪乗剰余積の各指数係数の値が指定された区間にあることを前記安全変数で規定される以上の確率で検証する（ステップＳ１０３）。そして、正当性が検証された場合（ステップＳ１０４でＹＥＳ）、処理装置１２４は、確率公開鍵暗号文を復号して得た平文の内容に基づいて所定の処理を実行し、その結果をネットワーク１０３経由で証明者端末１０２へ通知する（ステップＳ１０５）。他方、検証装置１２３において正当性が検証されなかった場合、処理装置１２４は、証明者端末１０２が今回送信してきた確率公開鍵暗号文に基づく処理の依頼を拒否するメッセージをネットワーク１０３経由で証明者端末１０２へ通知する（ステップＳ１０６）。
【００３４】
証明者端末１０２の処理結果受信装置１１４は、検証者端末１０１から送信されてきた処理結果または拒否メッセージを受信し、入出力装置１１５に出力する（ステップＳ２０５）。
【００３５】
このように本実施の形態における証明文作成装置１１３は、冪乗剰余積の形式を有する確率公開鍵暗号文であってその指数係数の列としてデータ記憶手段１１１に記憶されたデータ列を用いた確率公開鍵暗号文を生成し、この確率公開鍵暗号文の冪乗剰余積の各指数係数の値が指定された区間にあることを指数係数の値を隠したまま証明する証明文を添えて検証者端末１０１へ送信する。従って、一度に複数のデータ（データ列を構成する複数の要素）に対する証明を行うことが可能となる。
【００３６】
本実施の形態の証明システムの具体的な利用例としては各種考えられる。例えば「発明が解決しようとする課題」の欄で説明したアンケート式の個人の性格の傾向診断サービスもその一利用例である。この場合、データ記憶手段１１１に記憶されるデータ列は、アンケートの質問に対する利用者の回答に対応し、処理装置１２４の処理は個人の性格の傾向を診断する処理となる。
【００３７】
次に、本実施の形態の証明システムで使われる証明文作成装置と検証装置の実施の形態について詳細に説明する。
【００３８】
（１）証明文作成装置の実施の形態
まず、確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを証明する証明文作成装置の実施の形態について説明する。
【００３９】
図３は確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることを証明する証明文を作成する証明文作成装置の一例を示すブロック図であり、図４と図５と図６はこの証明文作成装置による証明文の作成処理を説明するためのフローチャートである。
【００４０】
本実施の形態の確率公開鍵暗号文の冪乗剰余積の各指数係数が指定された区間内にあることの証明方法は、秘密鍵により平文と暗号化に用いられた乱数との両方を求めることのできる確率公開鍵暗号方式による暗号文を用いる。また以下、暗号化する平文は数値データであり、またこれを暗号化した暗号文もまた数値データを成すものとして説明する。
【００４１】
図３を参照すると、本実施の形態の証明文作成装置は、証明文の作成に用いる各種データを人力するための入力部２０１と、入力されたデータに基づき演算を行ない証明文を作成する演算処理部２０２と、作成された証明文２０４を出力する出力部２０３を備えている。本実施の形態における証明文２０４は、証明対象である冪乗剰余積２２１と、平方数の証明文２２３、２２５と、絶対値の大きさの証明文２２２、２２４とから構成されている。
【００４２】
また、演算処理部２０２は、冪乗剰余積生成部２１１と証明文生成部２１２とを備え、証明文生成部２１２は、両端値との差の列の生成部２３１と、拡大部２３２と、分解部２３３と、平方数の証明部２３４と、絶対値の大きさの証明部２３５とを含んでいる。更に、平方数の証明部２３４は、暗号化部２４１と、冪乗剰余積生成部２４２と、乱数の冪乗剰余積生成部２４３と、挑戦値生成部２４４と、応答生成部２４５と、大きさ確認部２４６と、乱数生成部２４７とを有している。また、絶対値の大きさの証明部２３５は、暗号化部２５１と、冪乗剰余積生成部２５２と、挑戦値生成部２５３と、応答生成部２５４と、大きさ確認部２５５と、乱数生成部２５６とを有している。
【００４３】
図４を参照すると、本実施の形態の証明文の作成処理では、まず入力部２０１が証明に必要な各種の情報として、確率公開鍵暗号方式の公開鍵２０５であるｎ、ｇと、指定された区間を定める変数２０６である上限値ａおよび下限値ｂと、確率公開鍵暗号文の列２０７であるｅｉ（ｉ＝１、…、ｍ）と、指数係数の列２０８であるｗｉ（ｉ＝１、…、ｍ）と、正しく検証される確率を規定する安全変数２０９とを入力する（ステップＳ３０１）。
【００４４】
次いで、演算処理部２０２の冪乗剰余積生成部２１１が、確率公開鍵暗号方式の公開鍵２０５と確率公開鍵暗号文の列２０７と指数係数の列２０８とから、確率公開鍵暗号文の列２０７の指数係数の列２０８による冪乗剰余積ｅ＝Π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 が定められた区間内に存在することが分る。
【０１２７】
以上好ましい実施の形態および実施例を挙げて本発明を説明したが、本発明は上記の実施の形態および実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形して実施することができる。
【０１２８】
【発明の効果】
以上説明したように本発明によれば、冪乗剰余積の形式を有する確率公開鍵暗号文であってその指数係数の列として、その値が指定された範囲にあるデータ列を用いた確率公開鍵暗号文に対して、前記各指数係数の値が指定された区間にあることを指数係数の値を隠したまま一度に証明することのできる証明文を作成でき、またその証明文に基づいて前記各指定係数の値が指定された範囲にあることを検証することができる効果がある。
【図面の簡単な説明】
【図１】本発明の一実施の形態のブロック図である。
【図２】本発明の一実施の形態の処理を説明するためのフローチャートである。
【図３】本発明の証明文作成装置の一例を示すブロック図である。
【図４】本発明の証明文作成装置による証明文の作成処理を説明するためのフローチャートである。
【図５】本発明の証明文作成装置による証明文の作成処理を説明するためのフローチャートである。
【図６】本発明の証明文作成装置による証明文の作成処理を説明するためのフローチャートである。
【図７】本発明の検証装置の一例を示すブロック図である。
【図８】本発明の検証装置による検証処理を説明するためのフローチャートである。
【図９】本発明の検証装置による検証処理を説明するためのフローチャートである。
【図１０】本発明の検証装置による検証処理を説明するためのフローチャートである。
【図１１】本発明の証明文作成装置の処理を説明するための図である。
【図１２】本発明の証明文作成装置の処理を説明するための図である。
【図１３】本発明の証明文作成装置の処理を説明するための図である。
【図１４】本発明の検証装置の処理を説明するための図である。
【図１５】本発明の検証装置の処理を説明するための図である。
【図１６】本発明の検証装置の処理を説明するための図である。
【図１７】従来技術を説明するための図である。
【符号の説明】
１０１…検証者端末
１０２…証明者端末
１１１…データ記憶手段
１１２…公開情報記憶手段
１１３…証明文作成装置
１１４…処理結果受信装置
１１５…入出力装置
１２１…情報設定公開手段
１２２…情報記憶手段
１２３…検証装置
１２４…処理装置
【図１】
0004103401.tif 000002
【図２】
0004103401.tif 000003
【図３】
0004103401.tif 000004
【図４】
0004103401.tif 000005
【図５】
0004103401.tif 000006
【図６】
0004103401.tif 000007
【図７】
0004103401.tif 000008
【図８】
0004103401.tif 000009
【図９】
0004103401.tif 000010
【図１０】
0004103401.tif 000011
【図１１】
0004103401.tif 000012
【図１２】
0004103401.tif 000013
【図１３】
0004103401.tif 000014
【図１４】
0004103401.tif 000015
【図１５】
0004103401.tif 000016
【図１６】
0004103401.tif 000017
【図１７】
0004103401.tif 000018