"s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定する鍵設定部と、検証者に対してメッセージcを送信するメッセージ送信部と、1つの前記メッセージcに対するk通りk≧3の検証パターンの中から前記検証者により選択された1つの検証パターンの情報を受信する検証パターン受信部と、k通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、を備え、前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、認証装置。前記メッセージ送信部により単数又は複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第2ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第3ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、請求項1に記載の認証装置。前記メッセージ送信部により単数又は複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第2ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第3ステップを実行する処理を繰り返し、前記第1~第3ステップを所定回数実行した結果、前記検証者により毎回全ての回答情報で検証が成功した場合に認証が成功する、請求項2に記載の認証装置。前記メッセージcがc=c1,...,cmである場合、前記メッセージ送信部は、一方向性関数Hを用いて新たなメッセージc’=Hcを算出して、前記検証者に対してメッセージc’を送信し、前記回答送信部は、前記回答情報と共に、当該回答情報を利用しても前記検証者が復元することができないメッセージcの要素を送信する、請求項2又は3に記載の認証装置。s∈Knが秘密鍵に設定され、環K上の多次多項式fix1,...,xni=1~m及びyi=fisが公開鍵に設定されており、証明者からメッセージcを受信するメッセージ受信部と、1つの前記メッセージcに対するk通りk≧3の検証パターンの中から1つの検証パターンを選択する検証パターン選択部と、前記検証パターン選択部により選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信部と、k通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信部と、前記メッセージ受信部により受信されたメッセージc、及び前記回答受信部により受信された回答情報を用いて前記証明者の正当性を検証する検証部と、を備え、前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、認証装置。s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定する鍵設定部と、検証者に対してメッセージcを送信するメッセージ送信部と、前記検証者から応答αを受信する応答受信部と、前記応答受信部により受信された応答αを用いて、前記メッセージcに対する検証に利用される多項式fを生成する多項式生成部と、前記多項式生成部により生成された多項式fを前記検証者に送信する多項式送信部と、1つの前記メッセージcに対するk通りk≧2の検証パターンの中から前記検証者により選択された1つの検証パターンの情報を受信する検証パターン受信部と、k通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、を備え、前記回答情報は、2通りの前記応答α、前記多項式f及び前記k通りの回答情報を用いて実施した前記メッセージcに対する計2k通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵sが計算可能となる情報である、認証装置。前記メッセージ送信部により単数又は複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記応答受信部から応答αを受信する第2ステップ、当該第2ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式fを生成し、前記多項式送信部により当該多項式fを送信する第3ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第4ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第5ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、請求項6に記載の認証装置。前記メッセージ送信部により単数又は複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記応答受信部から応答αを受信する第2ステップ、当該第2ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式fを生成し、前記多項式送信部により当該多項式fを送信する第3ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第4ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第5ステップを実行する処理を繰り返し、前記第1~第5ステップを所定回数実行した結果、前記検証者により毎回全ての回答情報で検証が成功した場合に認証が成功する、請求項7に記載の認証装置。s∈Knが秘密鍵に設定され、環K上の多次多項式fix1,...,xni=1~m及びyi=fisが公開鍵に設定されており、証明者からメッセージcを受信するメッセージ受信部と、前記証明者に対して応答αを送信する応答送信部と、前記応答送信部により送信された応答αを用いて前記証明者により生成された、前記メッセージcに対する検証に利用される多項式fを受信する多項式受信部と、1つの前記メッセージcに対するk通りk≧2の検証パターンの中から1つの検証パターンを選択する検証パターン選択部と、前記検証パターン選択部により選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信部と、k通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信部と、前記メッセージ受信部により受信されたメッセージc、前記多項式受信部により受信された多項式f、及び前記回答受信部により受信された回答情報を用いて前記証明者の正当性を検証する検証部と、を備え、前記回答情報は、2通りの前記応答α、前記多項式f及び前記k通りの回答情報を用いて実施した前記メッセージcに対する計2k通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵sが計算可能となる情報である、認証装置。前記m及びnは、m<nの関係を有する、請求項1、5、6、9のいずれか1項に記載の認証装置。前記m及びnは、2m-n≪1の関係を有する、請求項10に記載の認証装置。s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定する鍵設定ステップと、検証者に対してメッセージcを送信するメッセージ送信ステップと、1つの前記メッセージcに対するk通りk≧3の検証パターンの中から前記検証者により選択された1つの検証パターンの情報を受信する検証パターン受信ステップと、k通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信ステップと、を含み、前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、認証方法。s∈Knが秘密鍵に設定され、環K上の多次多項式fix1,...,xni=1~m及びyi=fisが公開鍵に設定されており、証明者からメッセージcを受信するメッセージ受信ステップと、1つの前記メッセージcに対するk通りk≧3の検証パターンの中から1つの検証パターンを選択する検証パターン選択ステップと、前記検証パターン選択ステップで選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信ステップと、k通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信ステップと、前記メッセージ受信ステップで受信されたメッセージc、及び前記回答受信ステップで受信された回答情報を用いて前記証明者の正当性を検証する検証ステップと、を含み、前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、認証方法。s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定する鍵設定ステップと、検証者に対してメッセージcを送信するメッセージ送信ステップと、前記検証者から応答αを受信する応答受信ステップと、前記応答受信ステップで受信された応答αを用いて、前記メッセージcに対する検証に利用される多項式fを生成する多項式生成ステップと、前記多項式生成ステップで生成された多項式fを前記検証者に送信する多項式送信ステップと、1つの前記メッセージcに対するk通りk≧2の検証パターンの中から前記検証者により選択された1つの検証パターンの情報を受信する検証パターン受信ステップと、k通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信ステップと、を含み、前記回答情報は、2通りの前記応答α、前記多項式f及び前記k通りの回答情報を用いて実施した前記メッセージcに対する計2k通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵sが計算可能となる情報である、認証方法。s∈Knが秘密鍵に設定され、環K上の多次多項式fix1,...,xni=1~m及びyi=fisが公開鍵に設定されており、証明者からメッセージcを受信するメッセージ受信ステップと、前記証明者に対して応答αを送信する応答送信ステップと、前記応答送信ステップで送信された応答αを用いて前記証明者により生成された、前記メッセージcに対する検証に利用される多項式fを受信する多項式受信ステップと、1つの前記メッセージcに対するk通りk≧2の検証パターンの中から1つの検証パターンを選択する検証パターン選択ステップと、前記検証パターン選択ステップで選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信ステップと、k通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信ステップと、前記メッセージ受信ステップで受信されたメッセージc、前記多項式受信ステップで受信された多項式f、及び前記回答受信ステップで受信された回答情報を用いて前記証明者の正当性を検証する検証ステップと、を含み、前記回答情報は、2通りの前記応答α、前記多項式f及び前記k通りの回答情報を用いて実施した前記メッセージcに対する計2k通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵sが計算可能となる情報である、認証方法。s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定する鍵設定機能と、検証者に対してメッセージcを送信するメッセージ送信機能と、1つの前記メッセージcに対するk通りk≧3の検証パターンの中から前記検証者により選択された1つの検証パターンの情報を受信する検証パターン受信機能と、k通りの回答情報の中から、前記検証パターン受信機能により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信機能と、をコンピュータに実現させるためのプログラムであり、前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、プログラム。s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定する鍵設定部と、前記多次多項式fix1,...,xn及び前記秘密鍵sに基づいてN個のメッセージcを生成するメッセージ生成部と、文書M及び前記メッセージcを一方向性関数に適用して得られた情報に基づいて、kN通りk≧3の検証パターンの中から検証パターンを選択する検証パターン選択部と、前記検証パターン選択部により選択された検証パターンに応じて、前記メッセージc及び前記文書Mを用いた検証を通過するような電子署名σを生成する署名生成部と、を備え、前記電子署名σは、前記k-1N1通りの検証パターンに対応する電子署名σを用いて実施した検証が全て成功した場合に秘密鍵sが計算可能となる情報である、署名生成装置。上記の通り、多変数多項式問題は、量子コンピュータを用いても解くことが困難なNP困難問題と呼ばれる問題の一例である。通常、HFEなどに代表される多変数多項式問題を利用した公開鍵認証方式は、特殊なトラップドアが仕込まれた多次多変数連立方程式を利用している。例えば、x1,...,xnに関する多次多変数連立方程式Fx1,...,xn=yと線形変換A,Bが用意され、線形変換A,Bが秘密に管理される。この場合、多次多変数連立方程式F、線形変換A,Bがトラップドアとなる。トラップドアF,A,Bを知っているエンティティは、x1,...,xnに関する方程式BFAx1,...,xn=y’を解くことができる。一方、トラップドアF,A,Bを知らないエンティティは、x1,...,xnに関する方程式BFAx1,...,xn=y’を解くことができない。この仕組みを利用することにより、多次多変数連立方程式の解答困難性を安全性の根拠とする公開鍵認証方式や電子署名方式を実現することができる。上記の通り、こうした公開鍵認証方式や電子署名方式を実現するには、BFAx1,...,xn=yを満たすような特殊な多次多変数連立方程式を利用する必要がある。しかし、従来方式では署名生成時に多次多変数連立方程式Fを解く必要があるため,Fには比較的容易に解けるものしか用いることができない。すなわち、こうした従来方式では比較的容易に解ける3つの関数トラップドアB、F、Aを合成した型式の多次多変数連立方程式BFAx1,...,xn=yしか用いることができないため、十分な安全性を確保することが難しい。その結果、このような効率的に解く手段トラップドアを持つ多次多変数連立方程式を用いた公開鍵認証方式や電子署名方式に対して数々の攻撃法が提案されており、効率的に解く手段トラップドアを持たない多次多変数連立方程式を公開鍵認証方式や電子署名方式に用いることができるようにする工夫が求められている。そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、効率的に解く手段トラップドアを持たない多次多変数連立方程式を用いて安全性を高めた公開鍵認証方式又は電子署名方式を実現することが可能な、新規かつ改良された認証装置、認証方法、プログラム、及び署名生成装置を提供することにある。上記課題を解決するために、本発明のある観点によれば、s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定する鍵設定部と、検証者に対してメッセージcを送信するメッセージ送信部と、1つの前記メッセージcに対するk通りk≧3の検証パターンの中から前記検証者により選択された1つの検証パターンの情報を受信する検証パターン受信部と、k通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、を備え、前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、認証装置が提供される。また、上記の認証装置は、前記メッセージ送信部により複数のメッセージcをk回送信する第1ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第2ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第3ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、ように構成されていてもよい。また、上記の認証装置は、前記メッセージ送信部により複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第2ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第3ステップを実行する処理を繰り返し、前記第1~第3ステップを所定回数実行した結果、前記検証者により毎回全ての回答情報で検証が成功した場合に認証が成功する、ように構成されていてもよい。また、前記メッセージcがc=c1,...,cmである場合、前記メッセージ送信部は、一方向性関数Hを用いて新たなメッセージc’=Hcを算出して、前記検証者に対してメッセージc’を送信し、前記回答送信部は、前記回答情報と共に、当該回答情報を利用しても前記検証者が復元することができないメッセージcの要素を送信する、ように構成されていてもよい。また、上記課題を解決するために、本発明の別の観点によれば、s∈Knが秘密鍵に設定され、環K上の多次多項式fix1,...,xni=1~m及びyi=fisが公開鍵に設定されており、証明者からメッセージcを受信するメッセージ受信部と、1つの前記メッセージcに対するk通りk≧3の検証パターンの中から1つの検証パターンを選択する検証パターン選択部と、前記検証パターン選択部により選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信部と、k通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信部と、前記メッセージ受信部により受信されたメッセージc、及び前記回答受信部により受信された回答情報を用いて前記証明者の正当性を検証する検証部と、を備え、前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、認証装置が提供される。また、上記課題を解決するために、本発明の別の観点によれば、s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定する鍵設定部と、検証者に対してメッセージcを送信するメッセージ送信部と、前記検証者から応答αを受信する応答受信部と、前記応答受信部により受信された応答αを用いて、前記メッセージcに対する検証に利用される多項式の組Fを生成する多項式生成部と、前記多項式生成部により生成された多項式の組Fを前記検証者に送信する多項式送信部と、1つの前記メッセージcに対するk通りk≧2の検証パターンの中から前記検証者により選択された1つの検証パターンの情報を受信する検証パターン受信部と、k通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、を備え、前記回答情報は、2通りの前記応答α、前記多項式f及び前記k通りの回答情報を用いて実施した前記メッセージcに対する計2k通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵sが計算可能となる情報である、認証装置が提供される。また、上記の認証装置は、前記メッセージ送信部により複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記応答受信部から応答αを受信する第2ステップ、当該第2ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式fを生成し、前記多項式送信部により当該多項式fを送信する第3ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第4ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第5ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、ように構成されていてもよい。また、上記の認証装置は、前記メッセージ送信部により複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記応答受信部から応答αを受信する第2ステップ、当該第2ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式fを生成し、前記多項式送信部により当該多項式fを送信する第3ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第4ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第5ステップを実行する処理を繰り返し、前記第1~第5ステップを所定回数実行した結果、前記検証者により毎回全ての回答情報で検証が成功した場合に認証が成功する、ように構成されていてもよい。また、上記課題を解決するために、本発明の別の観点によれば、s∈Knが秘密鍵に設定され、環K上の多次多項式fix1,...,xni=1~m及びyi=fisが公開鍵に設定されており、証明者からメッセージcを受信するメッセージ受信部と、前記証明者に対して応答αを送信する応答送信部と、前記応答送信部により送信された応答αを用いて前記証明者により生成された、前記メッセージcに対する検証に利用される多項式fを受信する多項式受信部と、1つの前記メッセージcに対するk通りk≧2の検証パターンの中から1つの検証パターンを選択する検証パターン選択部と、前記検証パターン選択部により選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信部と、k通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信部と、前記メッセージ受信部により受信されたメッセージc、前記多項式受信部により受信された多項式f、及び前記回答受信部により受信された回答情報を用いて前記証明者の正当性を検証する検証部と、を備え、前記回答情報は、2通りの前記応答α、前記多項式f及び前記k通りの回答情報を用いて実施した前記メッセージcに対する計2k通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵sが計算可能となる情報である、認証装置が提供される。また、上記課題を解決するために、本発明の別の観点によれば、s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定する鍵設定ステップと、検証者に対してメッセージcを送信するメッセージ送信ステップと、1つの前記メッセージcに対するk通りk≧3の検証パターンの中から前記検証者により選択された1つの検証パターンの情報を受信する検証パターン受信ステップと、k通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信ステップと、を含み、前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、認証方法が提供される。また、上記課題を解決するために、本発明の別の観点によれば、s∈Knが秘密鍵に設定され、環K上の多次多項式fix1,...,xni=1~m及びyi=fisが公開鍵に設定されており、証明者からメッセージcを受信するメッセージ受信ステップと、1つの前記メッセージcに対するk通りk≧3の検証パターンの中から1つの検証パターンを選択する検証パターン選択ステップと、前記検証パターン選択ステップで選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信ステップと、k通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信ステップと、前記メッセージ受信ステップで受信されたメッセージc、及び前記回答受信ステップで受信された回答情報を用いて前記証明者の正当性を検証する検証ステップと、を含み、前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、認証方法が提供される。また、上記課題を解決するために、本発明の別の観点によれば、s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定する鍵設定ステップと、検証者に対してメッセージcを送信するメッセージ送信ステップと、前記検証者から応答αを受信する応答受信ステップと、前記応答受信ステップで受信された応答αを用いて、前記メッセージcに対する検証に利用される多項式fを生成する多項式生成ステップと、前記多項式生成ステップで生成された多項式fを前記検証者に送信する多項式送信ステップと、1つの前記メッセージcに対するk通りk≧2の検証パターンの中から前記検証者により選択された1つの検証パターンの情報を受信する検証パターン受信ステップと、k通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信ステップと、を含み、前記回答情報は、2通りの前記応答α、前記多項式f及び前記k通りの回答情報を用いて実施した前記メッセージcに対する計2k通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵sが計算可能となる情報である、認証装置が提供される。また、上記課題を解決するために、本発明の別の観点によれば、s∈Knが秘密鍵に設定され、環K上の多次多項式fix1,...,xni=1~m及びyi=fisが公開鍵に設定されており、証明者からメッセージcを受信するメッセージ受信ステップと、前記証明者に対して応答αを送信する応答送信ステップと、前記応答送信ステップで送信された応答αを用いて前記証明者により生成された、前記メッセージcに対する検証に利用される多項式fを受信する多項式受信ステップと、1つの前記メッセージcに対するk通りk≧2の検証パターンの中から1つの検証パターンを選択する検証パターン選択ステップと、前記検証パターン選択ステップで選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信ステップと、k通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信ステップと、前記メッセージ受信ステップで受信されたメッセージc、前記多項式受信ステップで受信された多項式f、及び前記回答受信ステップで受信された回答情報を用いて前記証明者の正当性を検証する検証ステップと、を含み、前記回答情報は、2通りの前記応答α、前記多項式f及び前記k通りの回答情報を用いて実施した前記メッセージcに対する計2k通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵sが計算可能となる情報である、認証装置が提供される。また、上記課題を解決するために、本発明の別の観点によれば、s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定する鍵設定機能と、検証者に対してメッセージcを送信するメッセージ送信機能と、1つの前記メッセージcに対するk通りk≧3の検証パターンの中から前記検証者により選択された1つの検証パターンの情報を受信する検証パターン受信機能と、k通りの回答情報の中から、前記検証パターン受信機能により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信機能と、をコンピュータに実現させるためのプログラムであり、前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、プログラムが提供される。さらに、上記課題を解決するために、本発明の別の観点によれば、上記のプログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。また、上記課題を解決するために、本発明の別の観点によれば、s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定する鍵設定部と、前記多次多項式fix1,...,xn及び前記秘密鍵sに基づいてN個のメッセージcを生成するメッセージ生成部と、文書M及び前記メッセージcを一方向性関数に適用して得られた情報に基づいて、kN通りk≧3の検証パターンの中から検証パターンを選択する検証パターン選択部と、前記検証パターン選択部により選択された検証パターンに応じて、前記メッセージc及び前記文書Mを用いた検証を通過するような電子署名σを生成する署名生成部と、を備え、前記電子署名σは、前記k-1N1通りの検証パターンに対応する電子署名σを用いて実施した検証が全て成功した場合に秘密鍵sが計算可能となる情報である、署名生成装置が提供される。上記のm、nは、m<nであってもよい。さらに、上記のm、nは、2m-n≪1であってもよい。以上説明したように本発明によれば、効率的に解く手段トラップドアを持たない多次多変数連立方程式を用いて安全性を高めた公開鍵認証方式又は電子署名方式を実現することが可能になる。以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。[説明の流れについて]ここで、以下に記載する本発明の実施形態に関する説明の流れについて簡単に述べる。まず、図1を参照しながら、公開鍵認証方式のアルゴリズム構成について説明する。次いで、図2を参照しながら、電子署名方式のアルゴリズム構成について説明する。次いで、図3を参照しながら、nパスの公開鍵認証方式について説明する。なお、本実施形態に係る説明に先立ち、一般的なHFE署名方式についても簡単に説明する。次いで、図4を参照しながら、本発明の第1実施形態3パスに係る公開鍵認証方式のアルゴリズムについて説明する。次いで、図5を参照しながら、同実施形態に係る公開鍵認証方式の拡張アルゴリズムについて説明する。次いで、図6を参照しながら、同実施形態に係る公開鍵認証方式の並列化アルゴリズムについて説明する。次いで、図7を参照しながら、同実施形態に係る公開鍵認証方式の非対話型アルゴリズムについて説明する。次いで、図8を参照しながら、同実施形態に係る公開鍵認証方式の具体的なアルゴリズムについて説明する。次いで、図9~図11を参照しながら、同実施形態に係る公開鍵認証方式の効率的なアルゴリズムについて説明する。次いで、図12を参照しながら、本発明の第2実施形態5パスに係る公開鍵認証方式のアルゴリズムについて説明する。次いで、図13を参照しながら、同実施形態に係る公開鍵認証方式の拡張アルゴリズムについて説明する。次いで、図14、図15を参照しながら、同実施形態に係る公開鍵認証方式の並列化アルゴリズムについて説明する。次いで、図16を参照しながら、同実施形態に係る公開鍵認証方式の非対話型アルゴリズムについて説明する。次いで、図17を参照しながら、同実施形態に係る公開鍵認証方式の具体的なアルゴリズムについて説明する。次いで、図18~図25を参照しながら、同実施形態に係る公開鍵認証方式の効率的なアルゴリズムについて説明する。次いで、本発明の第1及び第2実施形態に係る効率的なアルゴリズムを2次以上の多変数多項式に適用するための拡張手法について説明する。次いで、図26を参照しながら、本発明の第1及び第2実施形態に係る各アルゴリズムを実現することが可能な情報処理装置のハードウェア構成例について説明する。最後に、本実施形態の技術的思想について纏め、当該技術的思想から得られる作用効果について簡単に説明する。説明項目1:はじめに1-1:公開鍵認証方式のアルゴリズム構成1-2:電子署名方式のアルゴリズム構成1-3:nパスの公開鍵認証方式1-4:HFE電子署名方式1-4-1:HFE関数の性質1-4-2:HFE電子署名方式のアルゴリズム2:第1実施形態2-1:公開鍵認証方式のアルゴリズム2-2:拡張アルゴリズム2-3:並列化アルゴリズム2-4:非対話型アルゴリズム2-5:電子署名方式への変形2-6:具体例2-7:効率的なアルゴリズム2-8:多次多変数連立方程式の形式2-8-1:共通鍵ブロック暗号に関する形式2-8-2:ハッシュ関数に関する形式2-8-3:ストリーム暗号に関する形式3:第2実施形態3-1:公開鍵認証方式のアルゴリズム3-2:拡張アルゴリズム3-3:並列化アルゴリズム3-4:非対話型アルゴリズム3-5:電子署名方式への変形3-6:具体例3-7:効率的なアルゴリズム4:効率的なアルゴリズムの一般化5:ハードウェア構成例6:まとめ<1:はじめに>はじめに、本発明に係る実施形態について詳細に説明するに先立ち、一般的な公開鍵認証方式のアルゴリズム構成、一般的な電子署名方式のアルゴリズム構成、及びnパスの公開鍵認証方式について簡単に説明する。[1-1:公開鍵認証方式のアルゴリズム構成]まず、図1を参照しながら、一般的な公開鍵認証方式のアルゴリズム構成について説明する。図1は、一般的な公開鍵認証方式のアルゴリズム構成について説明するための説明図である。概要公開鍵認証方式とは、ある人証明者が、公開鍵pk及び秘密鍵skを利用して、他の人検証者に本人であることを納得させるための認証方式である。例えば、証明者Aの公開鍵pkAは、検証者に公開される。一方、証明者Aの秘密鍵skAは、証明者により秘密に管理される。公開鍵認証方式では、公開鍵pkAに対応する秘密鍵skAを知る者が証明者A本人であるとみなされる。証明者Aが検証者Bに対して本人であることを証明しようとする場合、証明者Aは、検証者Bと対話プロトコルを実行して、自身が公開鍵pkAに対応する秘密鍵skAを知っていることを証明すればよい。そして、対話プロトコルにより証明者Aが秘密鍵skAを知っていることが検証者Bにより証明された場合、証明者Aの正当性本人であることが証明される。なお、公開鍵認証方式の安全性を確保するには、次に示す2つの条件が求められる。1つ目の条件は、対話プロトコルを実行した際に秘密鍵skを持たない偽証者により偽証が成立してしまう確率を限りなく小さくすることである。この1つ目の条件が成り立つことを健全性と呼ぶ。つまり、健全性を有する対話プロトコルにおいては、秘密鍵skを持たない偽証者により、無視できない確率で偽証が成立することはないと言い換えられる。2つ目の条件は、対話プロトコルを実行したとしても、証明者Aが有する秘密鍵skAの情報が検証者Bに一切漏れることがないようにすることである。この2つ目の条件が成り立つことを零知識性と呼ぶ。上記の健全性と零知識性を有する対話プロトコルを利用することにより、公開鍵認証方式の安全性が確保される。モデル公開鍵認証方式のモデルには、図1に示すように、証明者と検証者という2つのエンティティが存在する。証明者は、鍵生成アルゴリズムGenを用いて、証明者固有の秘密鍵skと公開鍵pkの組を生成する。次いで、証明者は、鍵生成アルゴリズムGenを用いて生成した秘密鍵skと公開鍵pkの組を利用して検証者と対話プロトコルを実行する。このとき、証明者は、証明者アルゴリズムPを利用して対話プロトコルを実行する。上記の通り、対話プロトコルにおいて、証明者は、証明者アルゴリズムPを利用して、秘密鍵skを保有していることを検証者に証明する。一方、検証者は、検証者アルゴリズムVを利用して対話プロトコルを実行し、証明者が公開している公開鍵に対応する秘密鍵を、その証明者が保有しているか否かを検証する。つまり、検証者は、証明者が公開鍵に対応する秘密鍵を保有しているか否かを検証するエンティティである。このように、公開鍵認証方式のモデルは、証明者と検証者という2つのエンティティ、及び、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVという3つのアルゴリズムにより構成される。なお、以下の説明において、証明者検証者という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムGen、証明者アルゴリズムPを実行する主体は、証明者のエンティティに対応する情報処理装置である。同様に、検証者アルゴリズムVを実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図26に示した通りである。つまり、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVは、ROM904、RAM906、記憶部920、リムーバブル記録媒体928などに記録されたプログラムに基づいてCPU902により実行される。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、証明者により利用される。そして、鍵生成アルゴリズムGenは、証明者に固有の秘密鍵skと公開鍵pkの組を生成するアルゴリズムである。鍵生成アルゴリズムGenにより生成された公開鍵pkは公開される。そして、公開された公開鍵pkは、検証者により利用される。一方、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者が秘密に管理する。そして、秘密に管理される秘密鍵skは、検証者に対して公開鍵pkに対応する秘密鍵skを保有していることを証明するために利用される。形式的に、鍵生成アルゴリズムGenは、セキュリティパラメータ1λλは0以上の整数を入力とし、秘密鍵skと公開鍵pkを出力するアルゴリズムとして、下記の式1のように表現される。証明者アルゴリズムP証明者アルゴリズムPは、証明者により利用される。そして、証明者アルゴリズムPは、公開鍵pkに対応する秘密鍵skを保有していることを証明するアルゴリズムである。証明者アルゴリズムPは、証明者の秘密鍵skと公開鍵pkを入力とし、検証者との対話プロトコルを実行するアルゴリズムとして定義される。検証者アルゴリズムV検証者アルゴリズムVは、検証者により利用される。そして、検証者アルゴリズムVは、対話プロトコルの中で、公開鍵pkに対応する秘密鍵skを証明者が保有しているか否かを検証するアルゴリズムである。検証者アルゴリズムVは、証明者の公開鍵pkを入力とし、証明者との間で対話プロトコルを実行した後、0又は11bitを出力するアルゴリズムとして定義される。なお、出力0の場合には証明者が不正なものであり、出力1の場合には証明者が正当なものであるとする。形式的に、検証者アルゴリズムVは、下記の式2のように表現される。補足上記の通り、公開鍵認証方式は、安全性を確保するため、健全性と零知識性という2つの条件を満たすことが求められる。しかし、証明者が秘密鍵skを保有していることを証明者に証明させるためには、証明者が秘密鍵skに依存した手続きを実行し、その結果を検証者に通知して、その通知内容に基づく検証を検証者に実行させる必要がある。秘密鍵skに依存した手続きを実行するのは、健全性を担保するために必要である。一方で、この手続きの結果を検証者に通知しても、秘密鍵skの情報が一切検証者に漏れないようにする必要がある。そのため、これらの要件を満たすように、上記の鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVが設計されることが必要になる。以上、一般的な公開鍵認証方式のアルゴリズム構成について説明した。[1-2:電子署名方式のアルゴリズム構成]次に、図2を参照しながら、一般的な電子署名方式のアルゴリズム構成について説明する。図2は、一般的な電子署名方式のアルゴリズム構成について説明するための説明図である。概要紙文書とは異なり、ある電子化されたデータに対して押印したり署名を記載したりすることはできない。そのため、電子化されたデータの作成者を証明するためには、紙文書に押印したり署名を記載したりするのと同等の効果を奏する電子的な仕組みが必要とされる。このような仕組みが電子署名である。例えば、データの作成者しか知らない署名データをデータに関連付けて受領者に提供し、その署名データを受領者側で検証する仕組みのことを電子署名方式と呼ぶ。モデル電子署名方式のモデルには、図2に示すように、署名者と検証者という2つのエンティティが存在する。そして、電子署名方式のモデルは、鍵生成アルゴリズムGen、署名生成アルゴリズムSig、署名検証アルゴリズムVerという3つのアルゴリズムにより構成される。署名者は、鍵生成アルゴリズムGenを利用して署名者固有の署名鍵skと検証鍵pkとの組を生成する。また、署名者は、署名生成アルゴリズムSigを利用して文書Mに対して付与する電子署名σを生成する。つまり、署名者は、文書Mに電子署名を付与するエンティティである。一方、検証者は、署名検証アルゴリズムVerを利用して文書Mに付与された電子署名σを検証する。つまり、検証者は、文書Mの作成者が署名者であるか否かを確認するために、電子署名σを検証するエンティティである。なお、以下の説明において、署名者検証者という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムGen、署名生成アルゴリズムSigを実行する主体は、署名者のエンティティに対応する情報処理装置である。同様に、署名検証アルゴリズムVerを実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図26に示した通りである。つまり、鍵生成アルゴリズムGen、署名生成アルゴリズムSig、署名検証アルゴリズムVerは、ROM904、RAM906、記憶部920、リムーバブル記録媒体928などに記録されたプログラムに基づいてCPU902により実行される。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、署名者により利用される。そして、鍵生成アルゴリズムGenは、署名者固有の署名鍵skと検証鍵pkの組を生成するアルゴリズムである。鍵生成アルゴリズムGenにより生成された検証鍵pkは公開される。一方、鍵生成アルゴリズムGenにより生成された署名鍵skは、署名者により秘密に管理される。そして、署名者により秘密に管理されている署名鍵skは、文書Mに付与される電子署名σの生成に利用される。形式的に、鍵生成アルゴリズムGenは、セキュリティパラメータ1λλは0以上の整数を入力とし、秘密鍵skと公開鍵pkを出力するアルゴリズムとして、下記の式3のように表現される。署名生成アルゴリズムSig署名生成アルゴリズムSigは、署名者により利用される。そして、署名生成アルゴリズムSigは、文書Mに対して付与される電子署名σを生成するアルゴリズムである。形式的に、署名生成アルゴリズムSigは、署名者の署名鍵skと文書Mを入力とし、下記の式4に示すように、電子署名σを出力するアルゴリズムとして表現される。署名検証アルゴリズムVer署名検証アルゴリズムVerは、検証者により利用される。そして、署名検証アルゴリズムVerは、電子署名σが文書Mに対する正当な電子署名であるか否かを検証するアルゴリズムである。形式的に、署名検証アルゴリズムVerは、下記の式5に示すように、署名者の検証鍵pk、文書M、電子署名σを入力とし、0又は11bitを出力するアルゴリズムとして表現される。なお、0を出力する場合公開鍵pkが文書Mと電子署名σを拒否する場合、文書Mに対する電子署名σは不当である。1を出力する場合公開鍵pkが文書Mと電子署名σを受理する場合、文書Mに対する電子署名σは正当である。以上、一般的な電子署名方式のアルゴリズム構成について説明した。[1-3:nパスの公開鍵認証方式]次に、図3を参照しながら、nパスの公開鍵認証方式について説明する。図3は、nパスの公開鍵認証方式について説明するための説明図である。上記の通り、公開鍵認証方式は、対話プロトコルの中で、証明者が公開鍵pkに対応する秘密鍵skを保有していることを検証者に証明する認証方式である。また、公開鍵認証方式の安全性を担保するため、健全性と零知識性という2つの条件を満たす必要がある。そのため、対話プロトコルの中では、図3に示すように、証明者と検証者の双方がそれぞれ処理を実行しながら、証明者と検証者との間でn回の情報交換が行われる。nパスの公開鍵認証方式の場合、証明者アルゴリズムPを用いて証明者により処理Step.1が実行され、情報T1が検証者に送信される。次いで、検証者アルゴリズムVを用いて検証者により処理Step.2が実行され、情報T2が証明者に送信される。同様にして処理Step.3,...,Step.nが実行され、情報T3,...,Tnが送信され、処理Step.n1が実行される。このように、情報がn回送受信される対話プロトコルに基づく公開鍵認証方式のことをnパスの公開鍵認証方式と呼ぶ。以上、nパスの公開鍵認証方式について説明した。[1-4:HFE電子署名方式]ここで、多次多変数連立方程式を用いた電子署名方式の一例として、HFE電子署名方式について簡単に説明する。1-4-1:HFE関数の性質まず、HFE関数Ftの定義、及びHFE関数Ftの性質について簡単に説明する。≪記号の定義≫K:q個の数を含む元で構成される有限環KnKのn個の直積Ft:Kn→KnA:有限環Kのn次拡大要素数qnB:有限環Kのm次拡大要素数qmφ:線形写像A→Kn下記の式6を参照S:Kn上での可逆的アフィン変換T:Kn上での可逆的アフィン変換f:中央写像下記の式7を参照トラップドア:S、T、aij、bi、c但し、dをそれほど大きくない整数として、aij,bi,c∈A、qiqj>dならばaij=0かつqi>dならばbj=0である。≪HFE関数Ftの構造≫HFE関数Ftは、変換Sによる写像、中央写像FF=φ-1fφ、及び変換Tによる写像の合成写像Ft=TFSにより表現されるこのは写像の合成。そして、y=Ftxを計算するアルゴリズムは、次のようになる。Step.1変換Sにより、与えられたx=x0,...,xn-1∈Knをx’=x0’,...,xn-1’∈Knに変換する。Step.2φ-1により、x’∈KnをX’∈Aに変換する。Step.3中央写像fにより、X’∈AをY’=fX’∈Aに変換する。Step.4φにより、Y’∈Aをy’=y0’,...,yn-1’∈Knに変換する。Step.5変換Tにより、y’∈Knをy=y0,...,yn-1∈Knに変換する。Step.6y∈Knを出力する。上記の式7に示すように、HFE関数Ftは、非線形の一変数多項式に基づく中央写像fを含んでいる。そのため、ある終域Aの元Y’に対し、一変数多項式の根の集合に相当する原像{Z∈A|fZ=Y’}の要素数が複数存在する可能性がある。この場合、値域の元yに対し、HFE関数Ftに関する原像の要素数が複数となる。また、ある終域Aの元Y’に対し、原像{Z∈A|fZ=Y’}の要素が全く存在しない可能性もある。この場合、原像{Z∈A|fZ=Y’}の要素が全く存在しない終域の元は値域に含まれないため、終域と値域とは異なる。以下、HFE関数Ftの計算アルゴリズムについて、より詳細に説明する。≪順方向の計算アルゴリズム≫HFE関数Ftに対する順方向の計算アルゴリズムは、与えられたx∈KnをHFE関数Ftxに代入してy=Ftx∈Knを得るステップにより構成される。この順方向の計算アルゴリズムに定義域の元xが1つ入力されると値域の元yが1つ出力される。≪逆方向の計算アルゴリズム≫HFE関数Ftに関する逆方向の計算アルゴリズムは、次のStep.1~Step.7により構成される。Step.1与えられたy=y0,...,yn-1∈Knを変換Tの逆変換T-1に適用してy’=y0’,...,yn-1’∈Knを得る。Step.2φ-1により、y’=y0’,...,yn-1’∈KnをY’∈Aに変換する。Step.3Y’を用いて、X’∈{Z∈A|fZ=Y’}の集合を計算する。但し、{Z∈A|fZ=Y’}が空集合の場合、例外値errを出力する。なお、X’∈{Z∈A|fZ=Y’}は、例えば、多項式fX-Y’を因数分解することにより求められる。また、終域の要素Y’をランダムに選択したとき、その要素Y’に対する原像{Z∈A|fZ=Y’}がm個の元を持つ確率は、近似的に1/meとなる但し、このeはネイピア数。Step.4X’∈{Z∈A|fZ=Y’}の集合から1つの要素X’を選択する。Step.5φにより、Step.4で選択された1つの要素X’∈Aをx’=x0’,...,xn-1’∈Knに変換する。Step.6変換Sの逆変換S-1により、x’∈Knをx=x0,...,xn-1∈Knに変換する。Step.7x∈Knを出力する。上記のStep.3において、X’∈{Z∈A|fZ=Y’}の要素数α=|{Z∈A|fZ=Y’}|がα=0又はα≧2となる可能性がある点に注意されたい。1-4-2:HFE電子署名方式のアルゴリズムここまでHFE関数Ftについて説明してきた。次に、HFE関数Ftを用いた電子署名方式以下、HFE署名方式の具体的なアルゴリズムについて説明する。但し、ここでは、HFE署名方式の一例として、HFE関数を用いたPFDH署名方式以下、HFEPFDH署名方式について説明する。≪PFDH署名方式≫まず、PFDH署名方式における鍵生成アルゴリズムGen、署名生成アルゴリズムSig、署名検証アルゴリズムVerについて説明する。これらPFDH署名方式のアルゴリズムは、トラップドア付き一方向性関数Ft:A→B、ハッシュ関数H:{0,1}→Bを利用する。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、セキュリティパラメータを1λとし、署名鍵skをFtのトラップドアtとし、検証鍵pkをFtとしてsk,pkを計算するsk,pk←Gen1λ。署名生成アルゴリズムSig署名生成アルゴリズムSigは、メッセージM、署名鍵skを入力とし、次のStep.1~Step.4により電子署名σを計算するσ←Sigsk,M。Step.1乱数rを生成する。Step.2y=HM,r∈Bを計算する。Step.3トラップドアtを用いてFtの逆方向の計算アルゴリズムを実行し、y=Ftxとなるxを算出する。但し、y=Ftxとなるxが存在しない場合にはStep.1に戻る。Step.4電子署名σ=x,rを出力する。署名検証アルゴリズムVer署名検証アルゴリズムVerは、検証鍵pk=Ft、メッセージM、電子署名σ=x,rを入力とし、次のStep.1及びStep.2によりメッセージMに対する電子署名σの正当性を検証する0/1←Verpk,M,σ。Step.1Ftx=HM,rか否かを判断する。Step.2Ftx=HM,rの場合に1を出力し、Ftx≠HM,rの場合に0を出力する。≪HFEPFDH署名方式≫次に、HFEPFDH署名方式における署名生成アルゴリズムSig、署名検証アルゴリズムVerについて説明する。HFEPFDH署名方式は、HFE関数Ftを用いたPFDH署名方式である。なお、HFEPFDH署名方式では、署名鍵sk、HFE関数FtのトラップドアS,T,aij、bi、c、検証鍵pkがFtに設定される。署名生成アルゴリズムSig署名生成アルゴリズムSigは、メッセージM、署名鍵skを入力とし、次のStep.1~Step.9により電子署名σを計算するσ←Sigsk,M。Step.1乱数rを生成する。Step.2乱数r、メッセージMを用いて、ハッシュ値y∈Kn←HM,rを計算する。Step.3y=y0,...,yn-1∈Knを変換Tの逆変換T-1に適用してy’=y0’,...,yn-1’∈Knを得る。Step.4φ-1により、y’=y0’,...,yn-1’∈KnをY’∈Aに変換する。Step.5X’∈{Z∈A|fZ=Y’}の集合を計算する。Step.6集合{Z∈A|fZ=Y’}から1つの要素X’を選択する。但し、集合{Z∈A|fZ=Y’}が空集合の場合、Step.1の処理へ戻る。Step.7φにより、X’∈Aをx’=x0’,...,xn-1’∈Knに変換する。Step.8変換Sにより、x’∈Knをx=x0,...,xn-1∈Knに変換する。Step.9電子署名σ=x,rを出力する。署名検証アルゴリズムVer署名検証アルゴリズムVerは、検証鍵pk=Ft、メッセージM、電子署名σ=x,rを入力とし、次のStep.1~Step.3によりメッセージMに対する電子署名σの正当性を検証する0/1←Verpk,M,σ。Step.1電子署名σに含まれるr、及びメッセージMを用いて、ハッシュ値y←HM,rを計算する。Step.2電子署名σに含まれるx∈KnをHFE関数Ftxに代入して、y=Ftx∈Knを計算する。Step.3y=yならば1を出力し、y≠yならば0を出力する。以上、HFE電子署名方式ここではHFEPFDH署名方式を例示した。における各アルゴリズムの構成について説明した。上記のアルゴリズム構成から推察される通り、HFE電子署名方式においては、HM,rに関するFt=TFSの原像が計算されると電子署名σが偽造されてしまう。つまり、HFE電子署名方式は、HM,r=Ftxで表現される特殊な多次多変数連立方程式の解答困難性に依存した方式である。そして、このような特殊な多次多変数連立方程式については、その求解問題の困難性に対する評価が難しい。実際には、HFE電子署名方式で用いられる多次多変数連立方程式は、準指数時間quasi-polynominaltime以下で解くことができると言われている。<2:第1実施形態>ここで、本発明の第1実施形態について説明する。本実施形態は、HFE電子署名方式と同様、多次多変数連立方程式に対する求解問題の困難性に安全性の根拠をおく公開鍵認証方式及び電子署名方式に関する。但し、本実施形態は、HFE電子署名方式などとは異なり、十分な安全性を確保するために、効率的に解く手段トラップドアを持たない多次多変数連立方程式を利用できるようにした公開鍵認証方式及び電子署名方式を提供するものである。[2-1:公開鍵認証方式のアルゴリズム]まず、図4を参照しながら、本実施形態に係る公開鍵認証方式以下、本手法のアルゴリズムについて説明する。図4は、本手法のアルゴリズムについて説明するための説明図である。なお、本手法は、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。以下、各アルゴリズムの内容について説明する。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1x1,...,xn,...,fmx1,...,xnと、ベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトルx1,...,xnをxと表記し、m本のn変数多次多項式f1x,...,fmxをFxと表記する。証明者アルゴリズムP、検証者アルゴリズムV次に、図4を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、証明者がy=Fsを満たすsを知っていることをsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。Step.1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器G1に数wを適用してベクトルr∈Knと数w’を生成する。つまり、証明者アルゴリズムPは、r,w’←G1wを計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器G2に数w’を適用してn変数多項式F’x=f’1x,...,f’mxを生成する。つまり、証明者アルゴリズムPは、F’←G2w’を計算する。Step.1続き:次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、Fx←FxrF’xを計算する。この計算は、xについての多項式の組Fxrを多項式の組F’xによりマスクする操作に相当する。Step.1続き:次いで、証明者アルゴリズムPは、F’zとzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1F’z,zを計算する。また、証明者アルゴリズムPは、数w’のハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2w’を計算する。さらに、証明者アルゴリズムPは、多項式の組Fのハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3Fを計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。また、ハッシュ値c1,c2,c3はメッセージである。Step.1で生成されたメッセージc1,c2,c3は、検証者に送られる。Step.2:検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1,2}を証明者に送る。Step.3:証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=w’,zを生成する。そして、d=2の場合、証明者アルゴリズムPは、情報σ=Fx,zを生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。Step.4:検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、r’,w←G1σを計算する。さらに、検証者アルゴリズムVは、F←G2wを計算する。そして、検証者アルゴリズムVは、c2=H2wの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3=H3Fxr’Fxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、w,z’←σとする。さらに、検証者アルゴリズムVは、F←G2wを計算する。そして、検証者アルゴリズムVは、c1=H1Fz’,z’の等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c2=H2wの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=2の場合、検証者アルゴリズムVは、F,z’←σとする。そして、検証者アルゴリズムVは、c1=H1Fz’-y,z’の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3=H3Fの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。補足さて、上記Step.1において生成されたメッセージc1,c2,c3を検証者に送った際、秘密鍵skに関する情報、rに関する情報、zに関する情報が検証者に一切漏れていないことに注意されたい。また、上記Step.3において生成された情報σを検証者に送った際、d=0のときにはzに関する情報が検証者に一切漏れておらず、d=1,2のときにはrに関する情報が検証者に一切漏れていないことに注意されたい。本手法における健全性について本手法の健全性は、検証者の全ての要求d=0,1,2に対して、証明者がメッセージc1,c2,c3に対する正しい情報σを回答したならば、その回答内容から、下記の式8及び式9を満たすF、F、r’、z’が計算できるということから保証されている。このようなロジックが保証されることにより、多次多変数連立方程式の求解問題を解かない限りにおいて2/3より高い確率で偽証することは不可能であることが保証される。つまり、検証者の要求d=0,1,2の全てに正しく回答するためには、偽証者が上記の式8及び式9を満たすF、F、r’、z’を計算できる必要がある。言い換えると、偽証者はFs=yを満たすsを計算できる必要がある。なお、検証者の要求d=0,1,2の高々2つまでに偽証者が正しく回答する可能性はある。そのため、偽証の成功確率は2/3となる。上記の対話プロトコルは十分な回数実行される。そのため、偽証の成功確率は無視できるほど小さくすることができる。変形例上記の鍵生成アルゴリズムGenは、y←Fsを計算し、公開鍵をF,yに設定している。しかし、鍵生成アルゴリズムGenは、y1,...,ym←Fsとして、f1x,...,fmx←f1x-y1,...,fmx-ymを計算し、公開鍵をf1,...,fmに設定するように構成されていてもよい。このように変形すると、証明者と検証者との間でy=0として対話プロトコルを実行することが可能になる。また、上記の証明者アルゴリズムPは、Fzとzからメッセージc1を生成しているが、Fz=F’zの関係があることにより、F’zとzからメッセージc1を生成しても、同様の対話プロトコルを構成することができる。また、証明者アルゴリズムPは、Fzのハッシュ値と、zのハッシュ値とを別々に計算し、それぞれをメッセージとして検証者に送るようにしてもよい。また、上記の証明者アルゴリズムPは、数wに擬似乱数生成器G1を適用してベクトルrと数w’を生成している。そして、上記の証明者アルゴリズムPは、数w’を擬似乱数生成器G2に適用してn変数多項式F’xを生成している。しかし、証明者アルゴリズムPは、最初からw=r,F’を算出し、G1を恒等写像としてもよい。また、この場合には、数wをG1に適用する必要はない。なお、G2についても同様である。また、上記の対話プロトコルにおいては公開鍵をF,yとしている。このFは秘密鍵skに依らないパラメータである。そのため、このパラメータFを証明者毎に設けるのではなく、このパラメータFをシステム全体に共通するパラメータにしてもよい。この場合、証明者毎に設定される公開鍵はyだけで済むことになり、公開鍵のサイズを小さくすることが可能になる。また、上記の対話プロトコルにおいては公開鍵をf1,...,fm,yとしているが、F=f1,...,fmは適当に選択してもよいパラメータである。そのため、証明者と検証者は、f1,...,fmをそのまま保持するのではなく、例えば、乱数のシードwpkを用意し、擬似乱数生成器Gを利用してF←Gwpkを計算するようにしてもよい。この場合、公開鍵はwpk,yとなり、F,yを公開鍵として公開する場合よりも、公開鍵のサイズを小さくすることが可能になる。上記の方式では、ハッシュ関数H1,H2,H3を用いてc1,c2,c3を計算しているが、ハッシュ関数の代わりにコミットメント方式COMを用いてもよい。コミットメント関数COMは、文字列Sと乱数ρの2つを引数にとる関数である。コミットメント関数の例としては、ShaiHaleviとSilvioMicaliによって国際会議CRYPTO1996で発表された方式などがある。このコミットメント関数を用いる場合、c1,c2,c3を計算する前に、乱数ρ1,ρ2,ρ3を用意し、ハッシュ関数H1,H2,H3を適用する代わりにコミットメント関数COM,ρ1,COM,ρ2,COM,ρ2を適用することによりc1,c2,c3を生成する。また、この変形例では、検証部で計算するCiを生成するために必要なρiを回答情報に含めることになる。なお、この変形手法は、後述の全ての方式について適用可能である。以上、本手法に係る基本的なアルゴリズム構成について説明した。[2-2:拡張アルゴリズム]次に、図5を参照しながら、本手法を拡張した公開鍵認証方式以下、拡張手法のアルゴリズムについて説明する。図5は、拡張手法に基づく対話プロトコルの流れを説明するための説明図である。この拡張手法は、1パス目に送信するメッセージc1,c2,c3を1つのハッシュ値cに変換して検証者に送る方式である。また、この拡張手法では、1パス目にハッシュ値cを送るように対話プロトコルを構成するため、3パス目で送る情報σから復元できないメッセージを情報σと共に検証者に送る。このように拡張することで、対話プロトコルの中で検証者に送るハッシュ値の数を減らすことが可能になり、通信するデータサイズを削減することができる。以下、拡張方式における各アルゴリズムの内容について詳細に説明する。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1x1,...,xn,...,fmx1,...,xnと、ベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトルx1,...,xnをxと表記し、m本のn変数多次多項式f1x,...,fmxをFxと表記する。証明者アルゴリズムP、検証者アルゴリズムV次に、図5を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、証明者がy=Fsを満たすsを知っていることをsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。Step.1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器G1に数wを適用してベクトルr∈Knと数w’を生成する。つまり、証明者アルゴリズムPは、r,w’←G1wを計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器G2に数w’を適用してn変数多項式F’x=f’1x,...,f’mxを生成する。つまり、証明者アルゴリズムPは、F’←G2w’を計算する。Step.1続き:次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、Fx←FxrF’xを計算する。この計算は、xについての多項式の組Fxrを多項式の組F’xによりマスクする操作に相当する。Step.1続き:次いで、証明者アルゴリズムPは、Fzとzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1Fz,zを計算する。また、証明者アルゴリズムPは、数w’のハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2w’を計算する。さらに、証明者アルゴリズムPは、多項式の組Fのハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3Fを計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。また、ハッシュ値c1,c2,c3はメッセージである。Step.1続き:拡張方式の場合、証明者アルゴリズムPは、メッセージc1,c2,c3をハッシュ関数Hに適用してハッシュ値cを生成する。そして、証明者アルゴリズムPは、生成したハッシュ値cを検証者に送る。Step.2:検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1,2}を証明者に送る。Step.3:証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ,c=w,c1を生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ,c=w’,z,c3を生成する。そして、d=2の場合、証明者アルゴリズムPは、情報σ,c=F,z,c2を生成する。このようにして生成された情報σ,cは、証明者アルゴリズムPにより検証者に送られる。Step.4:検証者アルゴリズムVは、証明者から受け取った情報σ,cを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、r’,w←G1σを計算する。次いで、検証者アルゴリズムVは、F←G2wを計算する。次いで、検証者アルゴリズムVは、c2’=H2wを計算する。次いで、検証者アルゴリズムVは、c3’=H3Fxr’Fxを計算する。その後、検証者アルゴリズムVは、c=Hc,c2’,c3’の等号が成り立つか否かを検証する。そして、検証者アルゴリズムVは、検証が成功した場合に認証成功を示す値1を出力し、検証が失敗した場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、w,z’←σとする。次いで、検証者アルゴリズムVは、F←G2wを計算する。次いで、検証者アルゴリズムVは、c1’=H1Fz’,z’を計算する。次いで、検証者アルゴリズムVは、c2’=H2wを計算する。その後、検証者アルゴリズムVは、c=Hc1’,c2’,cの等号が成り立つか否かを検証する。そして、検証者アルゴリズムVは、検証が成功した場合に認証成功を示す値1を出力し、検証が失敗した場合に認証失敗を示す値0を出力する。d=2の場合、検証者アルゴリズムVは、F,z’←σとする。次いで、検証者アルゴリズムVは、c1’=H1Fz’-y,z’を計算する。次いで、検証者アルゴリズムVは、c3’=H3Fを計算する。その後、検証者アルゴリズムVは、c=Hc1’,c,c3’の等号が成り立つか否かを検証する。そして、検証者アルゴリズムVは、検証が成功した場合に認証成功を示す値1を出力し、検証が失敗した場合に認証失敗を示す値0を出力する。以上、拡張方式の対話プロトコルにおける各アルゴリズムの処理について説明した。このように拡張することで、対話プロトコルの中で検証者に送るハッシュ値の数を減らすことが可能になり、通信するデータサイズを削減することができる。[2-3:並列化アルゴリズム]さて、先に述べた通り、本手法又は拡張手法に係る対話プロトコルを適用すれば、偽証が成功する確率を2/3以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を2/32以下に抑制することができる。同様に、この対話プロトコルをN回実行すると、偽証が成功する確率は2/3Nとなり、Nを十分に大きい数例えば、N=140にすれば、偽証が成功する確率は無視できる程度に小さくなる。例えば、本手法に係る対話プロトコルを並列的にN回実行するアルゴリズムは図6のようになる。以下、図6を参照しながら、並列的に対話プロトコルをN回実行する各アルゴリズムの内容について説明する。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1x1,...,xn,...,fmx1,...,xnと、ベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトルx1,...,xnをxと表記し、m本のn変数多次多項式f1x,...,fmxをFxと表記する。証明者アルゴリズムP、検証者アルゴリズムV次に、図6を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、証明者がy=Fsを満たすsを知っていることをsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。Step.1:まず、証明者アルゴリズムPは、i=1~Nについて、以下の処理1~処理8を実行する。処理1証明者アルゴリズムPは、任意に数wiを選択する。処理2証明者アルゴリズムPは、擬似乱数生成器G1に数wiを適用してベクトルri∈Knと数w’iを生成する。つまり、証明者アルゴリズムPは、ri,w’i←G1wiを計算する。処理3証明者アルゴリズムPは、擬似乱数生成器G2に数w’iを適用してn変数多項式の組F’ixを生成する。つまり、証明者アルゴリズムPは、F’i←G2w’iを計算する。Step.1続き:処理4証明者アルゴリズムPは、zi←si-riを計算する。この計算は、秘密鍵siをベクトルriによりマスクする操作に相当する。処理5証明者アルゴリズムPは、Fix←FxriF’ixを計算する。この計算は、xについての多項式の組Fxriを多項式の組F’ixによりマスクする操作に相当する。Step.1続き:処理6証明者アルゴリズムPは、Fiziとziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1Fizi,ziを計算する。処理7証明者アルゴリズムPは、数w’iのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2w’iを計算する。処理8証明者アルゴリズムPは、多項式の組Fiのハッシュ値c3,iを生成する。つまり、証明者アルゴリズムPは、c3,i←H3Fiを計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。また、ハッシュ値c1,i、c2,i、c3,iはメッセージである。i=1~Nについて、上記の処理1~処理8が実行された後、Step.1で生成されたメッセージc1,i,c2,i,c3,ii=1~Nは、検証者に送られる。Step.2:検証者アルゴリズムVは、i=1~Nのそれぞれについて、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求di∈{0,1,2}i=1~Nを証明者に送る。Step.3:証明者アルゴリズムPは、検証者から受けた要求diに応じて検証者に送り返す情報σiを生成する。ここで、証明者アルゴリズムPは、i=1~Nについて、以下の処理1~処理3を実行する。処理1di=0の場合、証明者アルゴリズムPは、情報σi=wiを生成する。処理2di=1の場合、証明者アルゴリズムPは、情報σi=w’i,ziを生成する。処理3di=2の場合、証明者アルゴリズムPは、情報σi=Fi,ziを生成する。上記の処理1~3の判定及び処理が実行された後、情報σii=1~Nは、証明者アルゴリズムPにより検証者に送られる。Step.4:検証者アルゴリズムVは、証明者から受け取った情報σii=1~Nを利用して以下の検証処理を実行する。なお、以下の処理は、i=1~Nについて実行される。di=0の場合、検証者アルゴリズムVは、r’i,wi←G1σiを計算する。さらに、検証者アルゴリズムVは、Fi←G2wiを計算する。そして、検証者アルゴリズムVは、c2,i=H2wiの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3,i=H3Fxr’iFixの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。di=1の場合、検証者アルゴリズムVは、wi,z’i←σiとする。さらに、検証者アルゴリズムVは、Fi←G2wiを計算する。そして、検証者アルゴリズムVは、c1,i=H1Fiz’i,z’iの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c2=H2wiの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。di=2の場合、検証者アルゴリズムVは、Fi,z’i←σiとする。そして、検証者アルゴリズムVは、c1,i=H1Fiz’i-y,z’iの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3,i=H3Fixの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、本手法の対話プロトコルを並列的に実行する方法について説明した。上記のように、本手法の対話プロトコルを繰り返し実行することにより、偽証が成功する確率を無視できる程度まで低減させることが可能になる。なお、上記のStep.1の後、c1,1,c1,2,c1,3,...,cN,1,cN,2,cN,3を検証者に送信する代わりに,これらをハッシュ値Hc1,1,c1,2,c1,3,...,cN,1,cN,2,cN,3にまとめて送信してもよい。この構成を適用すると、1パス目で送るメッセージが1つのハッシュ値だけとなり、大幅に通信量を削減することが可能になる。但し、このハッシュ値、及び証明者から送られるチャレンジに対する回答から復元できないハッシュ値については、回答と併せて証明者から送ってもらうようにする。この構成によると、N回の並列的繰り返し構成の場合、送るべき情報の数を2N-1個削減することが可能になる。好適なパラメータの設定方法についてさて、本実施形態に係る対話プロトコルは、受動的攻撃に対する安全性レベルを保証している。しかし、この対話プロトコルを並列的に繰り返し実行する上記の方法を適用した場合、能動的攻撃に対する安全性レベルが確実に保証されているということを保証するには、以下で説明するような条件が必要になる。上記の対話プロトコルは、1組の鍵ペア公開鍵y、秘密鍵sを用いてyについてy=Fsとなるsを知っていることを証明者が検証者に対して証明する方式であった。そのため、検証で受理される対話を行った場合、対話の際に証明者がsを用いたという情報を検証者に知られてしまう可能性が否定できない。また、上記のFには衝突困難性が保証されてない。そのため、上記の対話プロトコルを並列的に繰り返し実行する場合について、能動的攻撃に対する安全性レベルが確実に保証されているということを無条件で証明することは難しいのである。そこで、本件発明者は、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにする方法について検討した。そして、本件発明者は、上記の対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性を保証することが可能になる方法を考案した。この方法は、公開鍵として用いるn変数多次多項式f1,...,fmの数mをその変数の数nよりも十分に小さな値に設定するというものである。例えば、2m-n≪1となるようにm及びnが設定される例えば、n=160、m=80の場合2-80≪1である。。上記のような多次多変数方程式の求解問題に対する解答の困難性に安全性の根拠をおく方式において、秘密鍵s1と、それに対応する公開鍵pkとが与えられても、その公開鍵pkに対応する別の秘密鍵s2を生成することは難しい。そのため、公開鍵pkに対する秘密鍵sが2つ以上存在することを保証すれば、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにすることが可能になる。つまり、この保証が成り立てば、対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性を保証することが可能になる。図28を参照しながら、m本のn次多変数多項式で構成される関数F:Kn→Kmについて考えると但し、n>m、2つ目の原像を持たない定義域の要素数は、最大で|K|m-1個しか存在しない。そのため、|K|m-nを十分に小さくすると、2つ目の原像を持たない定義域の要素が選択される確率を無視できる程度まで小さくすることができる。つまり、n変数多次多項式f1,...,fmの数mがその変数の数nよりも十分に小さな値に設定されていれば、公開鍵pkに対して2つ以上の秘密鍵sが存在することを保証できる。その結果、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにすることが可能になり、対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性が保証される。以上説明したように、n変数多次多項式f1,...,fmの数mがその変数の数nよりも小さな値n>m;好ましくは2m-n≪1に設定する方法を適用することで、対話プロトコルを並列的に繰り返し実行する場合の安全性を向上させることが可能になる。[2-4:非対話型アルゴリズム]これまで3パスの公開鍵認証方式について説明してきた。しかし、本手法においては、2パス目で検証者から証明者に送られる情報が検証パターンを示す要求d実際には単なる乱数を用いることが多い。だけであるため、1パスの公開鍵認証方式以下、非対話型方式に変形することができる。なお、非対話型方式に係る各アルゴリズムの内容を図7に示した。以下、図7を参照しながら、非対話型方式に係る各アルゴリズムの内容について説明する。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1x1,...,xn,...,fmx1,...,xnと、ベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトルx1,...,xnをxと表記し、m本のn変数多次多項式f1x,...,fmxをFxと表記する。証明者アルゴリズムP、検証者アルゴリズムV次に、図7を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、証明者がy=Fsを満たすsを知っていることをsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。Step.1:まず、証明者アルゴリズムPは、i=1~Nについて、以下の処理1~処理8を実行する。処理1証明者アルゴリズムPは、任意に数wiを選択する。処理2証明者アルゴリズムPは、擬似乱数生成器G1に数wiを適用してベクトルri∈Knと数w’iを生成する。つまり、証明者アルゴリズムPは、ri,w’i←G1wiを計算する。処理3証明者アルゴリズムPは、擬似乱数生成器G2に数w’iを適用してn変数多項式の組F’ixを生成する。つまり、証明者アルゴリズムPは、F’i←G2w’iを計算する。Step.1続き:処理4証明者アルゴリズムPは、zi←s-riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。処理5証明者アルゴリズムPは、Fix←FxriF’ixを計算する。この計算は、xについての多項式の組Fxriを多項式の組F’ixによりマスクする操作に相当する。Step.1続き:処理6証明者アルゴリズムPは、Fiziとziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1Fizi,ziを計算する。処理7証明者アルゴリズムPは、数w’iのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2w’iを計算する。処理8証明者アルゴリズムPは、多項式の組Fiのハッシュ値c3,iを生成する。つまり、証明者アルゴリズムPは、c3,i←H3Fiを計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。また、ハッシュ値c1,i、c2,i、c3,iはメッセージである。Step.2:次に、証明者アルゴリズムPは、乱数Rを選択する。次いで、証明者アルゴリズムPは、i=1~Nについて、乱数RとStep.1で生成したメッセージc1,i、c2,i、c3,iをハッシュ関数Hに適用してd=d1,...,dNを生成する。Step.3:次に、証明者アルゴリズムPは、生成したdiに応じて検証者に送り返す情報σiを生成する。ここで、証明者アルゴリズムPは、i=1~Nについて、以下の処理1~3を実行する。処理1di=0の場合、証明者アルゴリズムPは、情報σi=wiを生成する。処理2di=1の場合、証明者アルゴリズムPは、情報σi=w’i,ziを生成する。処理3di=2の場合、証明者アルゴリズムPは、情報σi=Fi,ziを生成する。上記の処理1~3の判定及び処理が実行された後、乱数R、メッセージc1,i,c2,i,c3,i及び情報σii=1~Nは、証明者アルゴリズムPにより検証者に送られる。Step.4:検証者アルゴリズムVは、まず、証明者から受け取った乱数R、メッセージc1,i,c2,i,c3,i及び情報σii=1~Nをハッシュ関数Hに適用してd=d1,...,dNを生成する。次いで、検証者アルゴリズムVは、情報σii=1~Nを利用して以下の検証処理を実行する。なお、以下の処理は、i=1~Nについて実行される。di=0の場合、検証者アルゴリズムVは、r’i,wi←G1σiを計算する。さらに、検証者アルゴリズムVは、Fi←G2wiを計算する。そして、検証者アルゴリズムVは、c2,i=H2wiの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3,i=H3Fxr’iFixの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。di=1の場合、検証者アルゴリズムVは、wi,z’i←σiとする。さらに、検証者アルゴリズムVは、Fi←G2wiを計算する。そして、検証者アルゴリズムVは、c1,i=H1Fiz’i,z’iの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c2=H2wiの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。di=2の場合、検証者アルゴリズムVは、Fi,z’i←σiとする。そして、検証者アルゴリズムVは、c1,i=H1Fiz’i-y,z’iの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3,i=H3Fiの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、非対話型方式に係る各アルゴリズムの内容について説明した。上記の通り、非対話型方式は、検証者が検証パターンを選択するために乱数dを証明者に送る代わりに、証明者アルゴリズムPがメッセージc1,i、c2,i、c3,iを利用してdを生成するというものである。理想的なハッシュ関数Hを仮定すれば、ハッシュ値dがランダムに振る舞うため、証明者に都合の良いハッシュ値dが出ることはない。そのため、上記のような変形を行っても、十分な安全性が確保される。なお、このような変形は、拡張方式などに対しても同様に適用することが可能である。[2-5:電子署名方式への変形]ここで、本手法を電子署名方式へと変形する方法について説明する。なお、ここでは簡単のために、上記の非対話型方式を電子署名方式に変形する方法について述べる。上記の非対話型方式における証明者と検証者を電子署名方式における署名者と検証者に対応させると、証明者のみが検証者を納得させられるという点において、電子署名方式のモデルと類似していることが分かるであろう。こうした考えをもとに、非対話型方式に基づく電子署名方式のアルゴリズム構成について詳細に説明する。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1x1,...,xn,...,fmx1,...,xnと、ベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトルx1,...,xnをxと表記し、m本のn変数多次多項式f1x,...,fmxをFxと表記する。署名生成アルゴリズムSig署名生成アルゴリズムSigは、i=1~Nについて、以下の処理1~処理15を実行する。なお、署名生成アルゴリズムSigには、署名鍵sk=s1,...,sNと文書Mが入力されているものとする。処理1署名生成アルゴリズムSigは、任意に数wiを選択する。処理2署名生成アルゴリズムSigは、擬似乱数生成器G1に数wiを適用してベクトルri∈Knと数w’iを生成する。つまり、署名生成アルゴリズムSigは、ri,w’i←G1wiを計算する。処理3署名生成アルゴリズムSigは、擬似乱数生成器G2に数w’iを適用してm本のn変数多項式F’ix=f’1,ix,...,f’m,ixを生成する。つまり、署名生成アルゴリズムSigは、F’i←G2w’iを計算する。処理4署名生成アルゴリズムSigは、zi←si-riを計算する。この計算は、秘密鍵siをベクトルriによりマスクする操作に相当する。処理5署名生成アルゴリズムSigは、Fix←FxriF’ixを計算する。この計算は、xについての多項式の組Fxriを多項式の組F’ixによりマスクする操作に相当する。処理6署名生成アルゴリズムSigは、Fiziとziのハッシュ値c1,iを生成する。つまり、署名生成アルゴリズムSigは、c1,i←H1Fizi,ziを計算する。処理7署名生成アルゴリズムSigは、数w’iのハッシュ値c2,iを生成する。つまり、署名生成アルゴリズムSigは、c2,i←H2w’iを計算する。処理8署名生成アルゴリズムSigは、多項式の組Fiのハッシュ値c3,iを生成する。つまり、署名生成アルゴリズムSigは、c3,i←H3Fiを計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。処理9署名生成アルゴリズムSigは、乱数Rを選択する。処理10署名生成アルゴリズムSigは、i=1~Nについて、文書M、乱数R、及びハッシュ値c1,i,c2,i,c3,iをハッシュ関数Hに適用してd=d1,...,dNを生成する。つまり、署名生成アルゴリズムSigは、d=d1,...,dN←HR,M,c1,1,...,c3,Nを計算する。処理11署名生成アルゴリズムSigは、生成したdiに応じて情報σiを生成する。ここで、署名生成アルゴリズムSigは、i=1~Nについて、以下の処理12~処理14を実行する。処理12di=0の場合、署名生成アルゴリズムSigは、情報σi=wiを生成する。処理13di=1の場合、署名生成アルゴリズムSigは、情報σi=w’i,ziを生成する。処理14di=2の場合、署名生成アルゴリズムSigは、情報σi=Fi,ziを生成する。処理15i=1~Nについて、上記処理12~処理14の判定及び処理が実行された後、署名生成アルゴリズムSigは、乱数R、メッセージc1,i、c2,i、c3,i及び情報σii=1~Nを含む電子署名σ=R,c1,i、c2,i、c3,i,σ1,...,σNを出力する。署名検証アルゴリズムVer署名検証アルゴリズムVerは、i=1~Nについて、以下の全ての検証を通過すれば、電子署名σを受理し、1つでも検証を通過しなかった場合には電子署名σを拒否する。なお、署名検証アルゴリズムVerには、電子署名σと文書Mが入力されているものとする。まず、署名検証アルゴリズムVerは、d=d1,...,dN←HR,M,c1,1,...,c3,Nを計算する。次いで、署名検証アルゴリズムVerは、i=1~Nについて、以下の検証1~検証3を実行する。検証1di=0の場合、署名検証アルゴリズムVerは、r’i,wi←G1σiを計算する。次いで、署名検証アルゴリズムVerは、Fi←G2wiを計算する。そして、署名検証アルゴリズムVerは、c2,i=H2wiの等号が成り立つか否かを検証する。また、署名検証アルゴリズムVerは、c3,i=H3Fxr’iFixの等号が成り立つか否かを検証する。署名検証アルゴリズムVerは、これらの検証が全て成功した場合に電子署名σの受理を示す値1を出力し、検証に失敗があった場合に電子署名σの拒否を示す値0を出力する。検証2di=1の場合、署名検証アルゴリズムVerは、wi,z’i←σiを計算する。次いで、署名検証アルゴリズムVerは、Fi←G2wiを計算する。そして、署名検証アルゴリズムVerは、c1,i=H1Fiz’i,z’iの等号が成り立つか否かを検証する。また、署名検証アルゴリズムVerは、c2=H2wiの等号が成り立つか否かを検証する。署名検証アルゴリズムVerは、これらの検証が全て成功した場合に電子署名σの受理を示す値1を出力し、検証に失敗があった場合に電子署名σの拒否を示す値0を出力する。検証3di=2の場合、署名検証アルゴリズムVerは、Fi,z’i←σiを計算する。次いで、署名検証アルゴリズムVerは、c1,i=H1Fiz’i-y,z’iの等号が成り立つか否かを検証する。さらに、署名検証アルゴリズムVerは、c3,i=H3Fiの等号が成り立つか否かを検証する。署名検証アルゴリズムVerは、これらの検証が全て成功した場合に電子署名σの受理を示す値1を出力し、検証に失敗があった場合に電子署名σの拒否を示す値0を出力する。以上、本手法に基づく電子署名方式の各アルゴリズム構成について説明した。同様にして、上記の拡張方式に基づく電子署名方式を構築することも可能である。[2-6:具体例]次に、図8を参照しながら、本手法を実施する際に想定される具体的なアルゴリズム構成について説明する。図8は、本手法の具体例を説明するための説明図である。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f1x1,...,xn,...,fmx1,...,xnと、ベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトルx1,...,xnをxと表記し、m本のn変数2次多項式f1x,...,fmxをFxと表記する。但し、n変数2次多項式fix1,...,xnは、下記の式10のように表現される。証明者アルゴリズムP、検証者アルゴリズムV次に、図8を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、証明者がy=Fsを満たすsを知っていることをsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。Step.1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器G1に数wを適用してベクトルr∈Knと数w’を生成する。つまり、証明者アルゴリズムPは、r,w’←G1wを計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器G2に数w’を適用してm本の1次多項式の組f’1x1,...,xn,...,f’mx1,...,xnを生成する。つまり、証明者アルゴリズムPは、f’1,...,f’m←G2w’を計算する。但し、1次多項式f’ix1,...,xnは、下記の式11のように表現される。また、m本の1次多項式の組f’1x,...,f’mxをF’xと表記する。Step.1続き:次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、Fx←FxrF’xを計算する。この計算は、xについての多項式Fxrを多項式F’xによりマスクする操作に相当する。ここで、Fxrの中にはrに関する情報がxの1次の項にしか現れないため、rに関する情報は全てF’xによりマスクされている点に注意されたい。Step.1続き:次いで、証明者アルゴリズムPは、F’zとzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1F’z,zを計算する。また、証明者アルゴリズムPは、数w’のハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2w’を計算する。さらに、証明者アルゴリズムPは、多項式Fのハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3Fを計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。また、ハッシュ値c1、c2、c3はメッセージである。Step.1で生成されたメッセージc1、c2、c3は、検証者に送られる。Step.2:検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1,2}を証明者に送る。Step.3:証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=w’,zを生成する。そして、d=2の場合、証明者アルゴリズムPは、情報σ=F,zを生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。Step.4:検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、r’,w←G1σを計算する。さらに、検証者アルゴリズムVは、f←G2wを計算する。そして、検証者アルゴリズムVは、c2=H2wの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3=H3Fxr’Fxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、w,z’←σとする。さらに、検証者アルゴリズムVは、F←G2wを計算する。そして、検証者アルゴリズムVは、c1=H1Fz’,z’の等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c2=H2wの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=2の場合、検証者アルゴリズムVは、F,z’←σを計算する。そして、検証者アルゴリズムVは、c1=H1Fz’-y,z’の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3=H3Fの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、本手法を実施する際に想定される具体的なアルゴリズム構成について説明した。[2-7:効率的なアルゴリズム]m本のn変数2次多項式の組f1x,...,fmxは、下記の式12のように表現することができる。但し、x=x1,...,xnは、n個の変数を表すベクトルである。また、A1,...,Amは、n×n行列である。さらに、b1,...,bmはn×1ベクトルである。そして、cは、m×1ベクトルである。この表現を用いると、多項式の組Fは、下記の式13及び式14のように表現することができる。この表現が成り立つことは、下記の式15から容易に確認することができる。このようにFx1x2をx1に依存する部分と、x2に依存する部分と、x1,x2の両方に依存する部分の3つに分けたとき、x1とx2の両方に依存する部分Fbx1,x2は、x1,x2について双線形写像になる。この性質を利用すると、効率的な方式を実現することが可能になる。例えば、本手法において、xに関する多項式の組Fxrをマスクするために利用する多項式の組F’xを、ベクトルt∈Kn、e∈Kmを用いてF’x=Fbx,teとする変形について考えてみたい。この変形を行うと、xに関する多項式の組Fxr、F’xの和は、下記の式16のように表現することができる。ここで、t’=rt、e’=Fr-ceとおけば、xに関する多項式Fxは、ベクトルt’∈Kn、e’∈Kmにより表現することができる。これらの理由から、F’x=Fbx,teに設定すれば、F’とFの表現がKn上のベクトルとKm上のベクトルにより表現することが可能になり、通信に必要なデータサイズを大幅に減らすことができる。また、上記の変形により、F又はF’からrに関する情報が一切漏れることはない。例えば、e’,t’又はe,tを与えられても、e,t又はe’,t’を知らない限り、rの情報を一切知ることはできない。従って、上記の変形を施した本手法は、零知識性が担保された公開鍵認証方式である。以下、図9~図11を参照しながら、上記の変形を施した本手法に係る効率的なアルゴリズムについて、より詳細に説明する。なお、鍵生成アルゴリズムGenの構成については先に説明した本手法と実質的に同じであるため、詳細な説明を省略する。Step.1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器G1に数wを適用してベクトルr∈Knと数w’を生成する。つまり、証明者アルゴリズムPは、r,w’←G1wを計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器G2に数w’を適用して2つのベクトルt∈Kn、e∈Kmを生成する。つまり、証明者アルゴリズムPは、t,e←G2w’を計算する。次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、t’←rtを計算する。次いで、証明者アルゴリズムPは、e’←Fr-ceを計算する。Step.1続き:次いで、証明者アルゴリズムPは、上記の式16に基づいてFbz,tを算出し、Fbz,teとzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1Fbz,te,zを計算する。また、証明者アルゴリズムPは、数w’のハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2w’を計算する。さらに、証明者アルゴリズムPは、2つのベクトルt’とe’のハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3t’,e’を計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。また、ハッシュ値c1,c2,c3はメッセージである。Step.1で生成されたメッセージc1,c2,c3は、検証者に送られる。Step.2:検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1,2}を証明者に送る。Step.3:証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=w’,zを生成する。そして、d=2の場合、証明者アルゴリズムPは、情報σ=t’,e’,zを生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。Step.4:検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、r’,w←G1σを計算する。さらに、検証者アルゴリズムVは、t,e←G2wを計算する。そして、検証者アルゴリズムVは、c2=H2wの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3=H3r’t,Fr’-ceの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、w,z’←σとする。さらに、検証者アルゴリズムVは、t,e←G2wを計算する。そして、検証者アルゴリズムVは、c1=H1Fbz’,te,z’の等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c2=H2wの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=2の場合、検証者アルゴリズムVは、t,e,z’←σとする。そして、検証者アルゴリズムVは、c1=H1Fz’Fbz’,te-y,z’の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3=H3t,eの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、本手法の効率的なアルゴリズムについて説明した。この効率的なアルゴリズムを利用することにより、通信に必要なデータサイズを大幅に削減することができる。また、対話プロトコルの中で、xrを多項式Fに代入し、xについて整理しなおす計算Fxrの計算が必要なくなるため、計算効率も向上する。効率的なアルゴリズムの変形例についてさて、図9に示した本手法の効率的なアルゴリズムは、その計算効率を維持しながら、図10、図11に示すようなアルゴリズムに変形することが可能である。変形例A:図10に示すアルゴリズム例えば、図9に示した効率的なアルゴリズムのStep.1において、e’←Fr-ceという計算を行っているが、この計算を図10に示すようにe’←Freという計算に変形してもよい。但し、この変形を行う場合には、Step.4において検証者が行う検証内容の一部を変形する必要がある。具体的には、Step.4においてd=0の場合に検証者が行う検証内容のうち、c3=H3r’t,Fr’-ceの検証をc3=H3r’t,Fr’eの検証に置き換える必要がある。また、Step.4においてd=2の場合に検証者が行う検証内容のうち、c1=H1Fz’Fbz’,t’’’e’’’-y,z’の検証をc1=H1Fz’Fbz’,t’’’-ce’’’-y,z’の検証に置き換える必要がある。変形例B:図11に示すアルゴリズムまた、図10に示したアルゴリズムのStep.3において、d=0の場合にσをwに設定しているが、d=0の場合に設定されるσは、r,t,eが復元できる情報であればどのような情報でもよい。例えば、図11に示すように、Step.3においてd=0の場合に設定されるσの内容をw’,t’にしてもよい。但し、この変形を行う場合には、Step.4において検証者が行う検証内容の一部を変形する必要がある。具体的には、Step.4においてd=0の場合に検証者が行う検証内容のうち、c3=H3r’t,Fr’eの検証をc3=H3t’,Ft’-teの検証に置き換える必要がある。上記のように、Step.1において証明者により行われるe’←Fr-ceという計算をe’←Freという計算に変更することができる変形例A。また、Step.3においてd=0の場合に証明者により設定されるσの内容をw’,t’などに変更することができる変形例B。図11には、変形例Aに係る変形と変形例Bに係る変形を共に図9の効率的なアルゴリズムに対して適用したアルゴリズムを示したが、変形例Bに係る変形だけを図9の効率的なアルゴリズムに対して適用することも可能である。つまり、変形例Aの変形内容及び変形例Bの変形内容は、それぞれ単独で図9のアルゴリズムに適用してもよいし、両者を組み合わせて図9のアルゴリズムに適用してもよい。[2-8:多次多変数連立方程式の形式]これまで説明してきたように、本手法は、多次多変数連立方程式の求解問題に対する解答の困難性に安全性の根拠をおく方式である。また、本手法は、複雑な多次多変数連立方程式を利用可能な点に特徴がある。ここまでの説明においては多次多変数連立方程式の形式に特別な限定を行ってこなかったが、例えば、十分に困難性が補償されている暗号要素技術を表現した多次多変数連立方程式を利用することが好ましい。以下、本手法に適用可能な多次多変数連立方程式の具体例を紹介する。2-8-1:共通鍵ブロック暗号に関する形式AES、DES、KATANなどの共通鍵ブロック暗号技術は、よく解析され、安全性及び信頼性が高い要素技術である。これらの共通鍵ブロック暗号は、共通鍵ブロック暗号の鍵、平文、暗号文を変数とする多次多変数連立方程式により表現することができる。この多次多変数連立方程式において平文と暗号文を表現する変数に値を与えると、この多次多変数連立方程式は、鍵を表現する変数だけを変数に持つ方程式になる。このような共通鍵ブロック暗号を表現した多次多変数連立方程式の解を求めることは、平文と暗号文から共通鍵ブロック暗号の鍵を復元することに相当する。つまり、その共通鍵ブロック暗号の安全性が維持されている限りにおいて、その共通鍵ブロック暗号を表現した多次多変数連立方程式の求解困難性は担保される。そのため、ある共通鍵ブロック暗号方式を表現する多次多変数連立方程式を本手法に適用するならば、共通鍵ブロック暗号方式の安全性と同等の安全性を具備した公開鍵認証方式が実現される。但し、共通鍵ブロック暗号を、鍵、平文、暗号文を変数とする多次多変数連立方程式で表現した場合、多項式の次数が大きくなるため、連立方程式を表現するためのデータサイズが増大してしまう。そこで、鍵、平文、暗号文に加え、それぞれのラウンドにおける内部状態を表現するための変数を導入する。この変数を導入すれば、共通鍵ブロック暗号を表現する多次多変数連立方程式の次数を小さくすることができる。例えば、平文と暗号文を表現する変数に適当な値を代入し、鍵と内部状態を表現するための変数に関する連立方程式を導入する。このような方法を採用することにより、変数の数は増加するが、次数が下がるため、連立方程式の表現はコンパクトになる。2-8-2:ハッシュ関数に関する形式同様に、SHA-1、SHA-256などのハッシュ関数に関する多次多変数連立方程式を本手法に適用することも可能である。これらのハッシュ関数は、ハッシュ関数の入力となるメッセージと出力となるハッシュ値を変数とする多次多変数連立方程式で表現することができる。この多次多変数連立方程式において、ハッシュ値を表現する変数に適当な値を与えると、対応する入力を表現した変数に関する多次多変数連立方程式が得られる。このような多次多変数連立方程式の解を求めることは、ハッシュ値から、元になるメッセージの値を復元することに相当する。つまり、そのハッシュ関数の安全性一方向性が維持されている限りにおいて、そのハッシュ関数を表現した多次多変数連立方程式の求解問題に対する解答の困難性は担保される。そのため、あるハッシュ関数を表現した多次多変数連立方程式を本手法に適用すれば、ハッシュ関数の安全性に基づく公開鍵認証方式が実現される。但し、ハッシュ関数を、入力メッセージとハッシュ値を変数とする多次多変数連立方程式で表現した場合、多項式の次数が大きくなるため、連立方程式を表現するためのデータサイズが増大してしまう。そこで、入力メッセージ、ハッシュ値に加え、内部状態を表現するための変数を導入する。この変数を導入すれば、ハッシュ関数を表現する多次多変数連立方程式の次数を小さくすることができる。例えば、ハッシュ値を表現する変数に適用な値を代入し、入力メッセージと内部状態を表現するための変数に関する連立方程式を導入する。このような方法を採用することにより、変数の数は増加するが、次数が下がるため、連立方程式の表現はコンパクトになる。2-8-3:ストリーム暗号に関する形式同様に、Triviumなどのストリーム暗号に関する多次多変数連立方程式を本手法に適用することも可能である。これらのストリーム暗号は、ストリーム暗号の初期の内部状態を表現する変数と、出力されるストリームを表現する変数に関する多次多変数連立方程式で表現することが可能である。この場合、出力ストリームを表現する変数に適当な値を与えると、対応する初期の内部状態を表現するための変数に関する多次多変数連立方程式が得られる。このような多次多変数連立方程式の解を求めることは、出力されたストリームの値から、元になった初期の内部状態を表現する変数を復元することに相当する。つまり、そのストリーム暗号の安全性が確保されている限りにおいて、そのストリーム暗号を表現した多次多変数連立方程式の求解問題に対する解答の困難性は担保されている。そのため、あるストリーム暗号を表現した多次多変数連立方程式を本手法に適用すれば、ストリーム暗号の安全性に基づく公開鍵認証方式が実現される。但し、ストリーム暗号を、初期の内部状態と出力ストリームを変数とする多次多変数連立方程式で表現した場合、多項式の次数が大きくなり、連立方程式を表現するサイズが増大してしまう。そこで、初期の内部状態と出力ストリームに加え、それぞれのラウンドにおける内部状態を表現するための変数を導入する。この変数を導入すれば、ストリーム暗号を表現するための多次多変数連立方程式の次数を小さくすることが可能になる。例えば、出力ストリームを表現する変数に適当な値を代入し、初期の内部状態とラウンドにおける内部状態を表現するための変数に関する連立方程式を導入する。このような方法を採用することにより、変数の数は増加するが、次数が下がるため、連立方程式の表現はコンパクトになる。以上、本発明の第1実施形態について説明した。<3:第2実施形態>次に、本発明の第2実施形態について説明する。これまで3パスの公開鍵認証方式について説明してきた。本実施形態では、5パスの公開鍵認証方式以下、本手法について説明する。本手法は、検証者の検証パターンを2q通りにすることにより、公開鍵認証方式の健全性を確保する方式である。なお、上記の第1実施形態に係る3パスの公開鍵認証方式は、対話プロトコル1回当たりの偽証確率が2/3であったが、本手法では、後述するように対話プロトコル1回当たりの偽証確率は1/21/qとなる。但し、qは、利用する環の位数である。従って、環の位数が十分に大きい場合、図27に示すように、本手法の方が1回当たりの偽証確率を低減することが可能になり、少ない対話プロトコルの実行回数で、偽証確率を十分に小さくすることができる。5パスの公開鍵認証方式に係る対話プロトコルは、3パスの公開鍵認証方式に係る対話プロトコルよりも効率が低いように思われるかもしれない。しかし、5パスの公開鍵認証方式においては、環の位数を十分に大きくとった場合、対話プロトコル1回当たりの偽証確率が1/2に近くなるため、同じセキュリティレベルを達成するために必要な対話プロトコルの実行回数が少なくて済む。例えば、偽証確率を1/2n以下にしたい場合、3パスの公開鍵認証方式においては、n/log3-1=1.701n回以上、対話プロトコルを実行する必要がある。一方、5パスの公開鍵認証方式においては、n/1-log11/q回以上、対話プロトコルを実行する必要がある。図27に示すように、例えば、q=24にすれば、同じセキュリティレベルを実現するのに必要な通信量は、3パスの公開鍵認証方式に比べ、5パスの公開鍵認証方式の方が少なくなる。[3-1:公開鍵認証方式のアルゴリズム]以下、図12を参照しながら、5パスの公開鍵認証方式本手法に係るアルゴリズム構成について説明する。図12は、本手法に係るアルゴリズムの内容について説明するための説明図である。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1x1,...,xn,...,fmx1,...,xnと、ベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトルx1,...,xnをxと表記し、m本のn変数多次多項式f1x,...,fmxをFxと表記する。証明者アルゴリズムP、検証者アルゴリズムV次に、図12を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、証明者がy=Fsを満たすsを知っていることをsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。Step.1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Knと、n変数多項式の組F’x=f’1x,...,f’mxを生成する。つまり、証明者アルゴリズムPは、r,F’←Gwを計算する。次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。Step.1続き:次いで、証明者アルゴリズムPは、F’zとzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1F’z,zを計算する。また、証明者アルゴリズムPは、数wのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2wを計算する。なお、上記のH1...、H2...は、ハッシュ関数である。また、ハッシュ値c1,c2はメッセージである。Step.1で生成されたメッセージc1,c2は、検証者に送られる。Step.2:検証者アルゴリズムVは、q通り存在する環Kの元から1つの乱数αを選択する。そして、検証者アルゴリズムVは、選択した乱数αを証明者に送る。Step.3:証明者アルゴリズムPは、Fx←αFxrF’xを計算する。この計算は、xについての多項式の組Fxrを多項式の組F’xによりマスクする操作に相当する。Step.3で生成された多項式Fは、検証者に送られる。Step.4:検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1}を証明者に送る。Step.5:証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=zを生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。Step.6:検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、r’,F←Gσを計算する。そして、検証者アルゴリズムVは、c2=H2σの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、Fx=αFxr’Fxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、z’←σを計算する。そして、検証者アルゴリズムVは、c1=H1Fz’-αy,z’の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。補足さて、上記Step.1及びStep.3において生成されたメッセージc1,c2及び多項式の組Fを検証者に送った際、秘密鍵skに関する情報、rに関する情報、zに関する情報が検証者に一切漏れていないことに注意されたい。また、上記Step.5において生成された情報σを検証者に送った際、d=0のときにはzに関する情報が検証者に一切漏れておらず、d=1のときにはrに関する情報が検証者に一切漏れていないことに注意されたい。本手法における健全性について本手法の健全性は、証明者アルゴリズムPが1組のc1,c2、及び、検証者アルゴリズムVが選択する2通りのα1,α2について、要求d=0,1に正しく回答した場合に、その回答内容から下記の式17~式19を満たすF1、F2、F、r’、z’を計算できるということから保証されている。このようなロジックが保証されることにより、多変数連立方程式の求解問題を解かない限りにおいて1/21/qより高い確率で偽証することは不可能であることが保証される。つまり、検証者の要求d=0,1の全てに正しく回答するためには、偽証者が上記の式17~式19を満たすF1、F2、F、r’、z’を計算できる必要がある。言い換えると、偽証者はFs=yを満たすsを計算できる必要がある。従って、多変数連立方程式の求解問題を解かない限り、偽証者は、1/21/qより高い確率で偽証を成功させることができないのである。なお、上記の対話プロトコルを十分に多くの回数実行することにより、偽証の成功確率を無視できるほど小さくすることができる。変形例上記の鍵生成アルゴリズムGenは、y←Fsを計算し、公開鍵をF,yに設定している。しかし、鍵生成アルゴリズムGenは、y1,...,ym←Fsとして、f1x,...,fmx←f1x-y1,...,fmx-ymを計算し、公開鍵をf1,...,fmに設定するように構成されていてもよい。このように変形すると、証明者と検証者との間でy=0として対話プロトコルを実行することが可能になる。また、証明者アルゴリズムPは、Fzのハッシュ値と、zのハッシュ値とを別々に計算し、それぞれをメッセージとして検証者に送るようにしてもよい。また、上記の証明者アルゴリズムPは、数wに擬似乱数生成器G1を適用してベクトルrと数w’を生成している。そして、上記の証明者アルゴリズムPは、数w’を擬似乱数生成器G2に適用してn変数多項式F’xを生成している。しかし、証明者アルゴリズムPは、最初からw=r,F’を算出し、G1を恒等写像としてもよい。また、この場合には、数wをG1に適用する必要はない。なお、G2についても同様である。以上、本手法に係る基本的なアルゴリズム構成について説明した。[3-2:拡張アルゴリズム]次に、図13を参照しながら、本手法を拡張した公開鍵認証方式以下、拡張手法のアルゴリズムについて説明する。図13は、拡張手法に基づく対話プロトコルの流れを説明するための説明図である。この拡張手法は、3パス目に送信する多項式の組Fを1つのハッシュ値c3に変換して検証者に送る方式である。このように拡張することで、対話プロトコルの中で表現サイズの大きい多項式の組Fを検証者に送る確率を半減することが可能になり、通信する平均的なデータサイズを削減することができる。以下、拡張方式における各アルゴリズムの内容について詳細に説明する。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1x1,...,xn,...,fmx1,...,xnと、ベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトルx1,...,xnをxと表記し、m本のn変数多次多項式f1x,...,fmxをFxと表記する。証明者アルゴリズムP、検証者アルゴリズムV次に、図13を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、証明者がy=Fsを満たすsを知っていることをsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。Step.1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Knと、n変数多項式の組F’xを生成する。つまり、証明者アルゴリズムPは、r,F’←Gwを計算する。次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。Step.1続き:次いで、証明者アルゴリズムPは、F’zとzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1F’z,zを計算する。また、証明者アルゴリズムPは、数wのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2wを計算する。なお、上記のH1...、H2...は、ハッシュ関数である。また、ハッシュ値c1,c2はメッセージである。Step.1で生成されたメッセージc1,c2は、検証者に送られる。Step.2:検証者アルゴリズムVは、q通り存在する環Kの元から1つの乱数αを選択する。そして、検証者アルゴリズムVは、選択した乱数αを証明者に送る。Step.3:証明者アルゴリズムPは、Fx←αFxrF’xを計算する。この計算は、xについての多項式の組Fxrを多項式の組F’xによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、多項式の組Fのハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3Fxを計算する。なお、上記のH3...は、ハッシュ関数である。また、ハッシュ値c3はメッセージである。Step.3で生成されたメッセージc3は、検証者に送られる。Step.4:検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1}を証明者に送る。Step.5:証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=z,Fを生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。Step.6:検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、r’,F←Gσを計算する。そして、検証者アルゴリズムVは、c2=H2σの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3=H3αFxr’Fxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、z’,F←σを計算する。そして、検証者アルゴリズムVは、c1=H1Fz’-αy,z’の等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c2=H2Fxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、拡張方式の対話プロトコルにおける各アルゴリズムの処理について説明した。このように拡張することで、対話プロトコルの中で表現サイズの大きい多項式の組Fを検証者に送る確率を半減することが可能になり、通信する平均的なデータサイズを削減することができる。[3-3:並列化アルゴリズム]さて、先に述べた通り、本手法又は拡張手法に係る対話プロトコルを適用すれば、偽証が成功する確率を1/21/q以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を1/21/q2以下に抑制することができる。同様に、この対話プロトコルをN回実行すると、偽証が成功する確率は1/21/qNとなり、Nを十分に大きい数例えば、N=80にすれば、偽証が成功する確率は無視できる程度に小さくなる。例えば、本手法に係る対話プロトコルを並列的にN回実行するアルゴリズムは図14のようになる。以下、図14を参照しながら、並列的に対話プロトコルをN回実行する各アルゴリズムの内容について説明する。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1x1,...,xn,...,fmx1,...,xnと、ベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトルx1,...,xnをxと表記し、m本のn変数多次多項式f1x,...,fmxをFxと表記する。証明者アルゴリズムP、検証者アルゴリズムV次に、図14を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、証明者がy=Fsを満たすsを知っていることをsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。Step.1:まず、証明者アルゴリズムPは、i=1~Nについて、以下の処理1~処理5を実行する。処理1証明者アルゴリズムPは、任意に数wiを選択する。処理2証明者アルゴリズムPは、擬似乱数生成器Gに数wiを適用してベクトルri∈Knと多項式の組F’ixを生成する。つまり、証明者アルゴリズムPは、ri,F’i←Gwiを計算する。処理3証明者アルゴリズムPは、zi←s-riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。Step.1続き:処理4証明者アルゴリズムPは、F’iziとziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1F’izi,ziを計算する。処理5証明者アルゴリズムPは、数w’iのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2w’iを計算する。i=1~Nについて、上記の処理1~5が実行された後、Step.1で生成されたメッセージc1,i,c2,ii=1~Nは、検証者に送られる。Step.2:検証者アルゴリズムVは、q通り存在する環Kの元からN個の乱数α1,...,αNを選択する。そして、検証者アルゴリズムVは、選択した乱数α1,...,αNを証明者に送る。Step.3:検証者アルゴリズムVは、i=1~Nについて、Fix←αiFxriF’ixを計算する。この計算は、xについての多項式の組Fxriを多項式の組F’ixによりマスクする操作に相当する。そして、検証者アルゴリズムVは、多項式の組F1,...,FNを検証者に送る。Step.4:検証者アルゴリズムVは、i=1~Nのそれぞれについて、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求di∈{0,1}i=1~Nを証明者に送る。Step.5:証明者アルゴリズムPは、検証者から受けた要求diに応じて検証者に送り返す情報σiを生成する。ここで、証明者アルゴリズムPは、i=1~Nについて、以下の処理1又は処理2を実行する。処理1di=0の場合、証明者アルゴリズムPは、情報σi=wiを生成する。処理2di=1の場合、証明者アルゴリズムPは、情報σi=ziを生成する。上記処理1又は処理2の判定及び処理が実行された後、情報σii=1~Nは、証明者アルゴリズムPにより検証者に送られる。Step.6:検証者アルゴリズムVは、証明者から受け取った情報σii=1~Nを利用して以下の検証処理を実行する。なお、以下の処理は、i=1~Nについて実行される。di=0の場合、検証者アルゴリズムVは、r’i,Fi←Gσiを計算する。そして、検証者アルゴリズムVは、c2,i=H2σiの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、Fix=αiFxr’iFixの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。di=1の場合、検証者アルゴリズムVは、z’i←σiを計算する。そして、検証者アルゴリズムVは、c1,i=H1Fiz’i-αiy,ziの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、本手法の対話プロトコルを並列的に実行する方法について説明した。上記のように、本手法の対話プロトコルを繰り返し実行することにより、偽証が成功する確率を無視できる程度まで低減させることが可能になる。なお、拡張方式についても同様にして並列化することが可能である。拡張方式について並列化した対話プロトコルのアルゴリズム構成を図15に示した。なお、上記のStep.1の後、c1,1,c1,2,...,cN,1,cN,2を検証者に送信する代わりに,そのハッシュ値Hc1,1,c1,2,...,cN,1,cN,2にまとめて送信してもよい.この構成を適用すると、1パス目で送るメッセージが1つのハッシュ値だけとなり、大幅に通信量を削減することが可能になる。但し、このハッシュ値、及び証明者から送られるチャレンジに対する回答から復元できないハッシュ値については、回答と併せて証明者から送ってもらうようにする。この構成によると、N回の並列的繰り返し構成の場合、送るべき情報の数をN-1個削減することが可能になる。拡張方式に係る並列化アルゴリズムについて以下、図15を参照しながら、拡張方式に係る並列化アルゴリズムの内容について説明する。なお、鍵生成アルゴリズムGenの構成については本手法に係る並列化アルゴリズムと同じであるため、詳細な説明を省略する。Step.1:まず、証明者アルゴリズムPは、i=1~Nについて、以下の処理1~処理5を実行する。処理1証明者アルゴリズムPは、任意に数wiを選択する。処理2証明者アルゴリズムPは、擬似乱数生成器Gに数wiを適用してベクトルri∈Knと多項式の組F’ixを生成する。つまり、証明者アルゴリズムPは、ri,F’i←Gwiを計算する。処理3証明者アルゴリズムPは、zi←s-riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。Step.1続き:処理4証明者アルゴリズムPは、F’iziとziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1F’izi,ziを計算する。処理5証明者アルゴリズムPは、数wiのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2wiを計算する。i=1~Nについて、上記の処理1~5が実行された後、Step.1で生成されたメッセージc1,i,c2,ii=1~Nは、検証者に送られる。Step.2:検証者アルゴリズムVは、q通り存在する環Kの元からN個の乱数α1,...,αNを選択する。そして、検証者アルゴリズムVは、選択した乱数α1,...,αNを証明者に送る。Step.3:検証者アルゴリズムVは、i-1~Nについて、Fix←αiFxriF’ixを計算する。この計算は、xについての多項式の組Fxriを多項式の組F’ixによりマスクする操作に相当する。次いで、検証者アルゴリズムVは、多項式の組F1,...,FNのハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3F1,...,FNを計算する。なお、上記のH3...は、ハッシュ関数である。また、ハッシュ値c3はメッセージである。Step.3で生成されたメッセージc3は、検証者に送られる。Step.4:検証者アルゴリズムVは、i=1~Nのそれぞれについて、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求di∈{0,1}i=1~Nを証明者に送る。Step.5:証明者アルゴリズムPは、検証者から受けた要求diに応じて検証者に送り返す情報σiを生成する。ここで、証明者アルゴリズムPは、i=1~Nについて、以下の処理1又は処理2を実行する。処理1di=0の場合、証明者アルゴリズムPは、情報σi=wiを生成する。処理2di=1の場合、証明者アルゴリズムPは、情報σi=zi,Fiを生成する。上記処理1又は処理2の判定及び処理が実行された後、情報σii=1~Nは、証明者アルゴリズムPにより検証者に送られる。Step.6:検証者アルゴリズムVは、証明者から受け取った情報σii=1~Nを利用して以下の検証処理を実行する。なお、以下の処理は、i=1~Nについて実行される。di=0の場合、検証者アルゴリズムVは、r’i,Fi←Gσiを計算する。さらに、検証者アルゴリズムVは、Fi←αiFxr’iFixを計算する。そして、検証者アルゴリズムVは、c2,i=H2σiの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3=H3F1,...,FNの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。di=1の場合、検証者アルゴリズムVは、z’i,Fi←σiとする。そして、検証者アルゴリズムVは、c1,i=H1Fiz’i-αiy,z’iの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3=H3F1,...,FNの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、拡張方式に係る並列化アルゴリズムの内容について説明した。好適なパラメータの設定方法についてさて、上記の第1実施形態に係る対話プロトコルと同様、本実施形態に係る対話プロトコルは、受動的攻撃に対する安全性レベルを保証している。しかし、この対話プロトコルを並列的に繰り返し実行する上記の方法を適用した場合、能動的攻撃に対する安全性レベルが確実に保証されているということを保証するには、以下で説明するような条件が必要になる。上記の対話プロトコルは、1組の鍵ペア公開鍵y、秘密鍵sを用いてyについてy=Fsとなるsを知っていることを証明者が検証者に対して証明する方式であった。そのため、検証で受理される対話を行った場合、対話の際に証明者がsを用いたという情報を検証者に知られてしまう可能性が否定できない。また、上記のFには衝突困難性が保証されてない。そのため、上記の対話プロトコルを並列的に繰り返し実行する場合について、能動的攻撃に対する安全性レベルが確実に保証されているということを無条件で証明することは難しいのである。そこで、本件発明者は、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにする方法について検討した。そして、本件発明者は、上記の対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性を保証することが可能になる方法を考案した。この方法は、公開鍵として用いるn変数多次多項式f1,...,fmの数mをその変数の数nよりも十分に小さな値に設定するというものである。例えば、2m-n≪1となるようにm及びnが設定される例えば、n=160、m=80の場合2-80≪1である。。上記のような多次多変数方程式の求解問題に対する解答の困難性に安全性の根拠をおく方式において、秘密鍵s1と、それに対応する公開鍵pkとが与えられても、その公開鍵pkに対応する別の秘密鍵s2を生成することは難しい。そのため、公開鍵pkに対する秘密鍵sが2つ以上存在することを保証すれば、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにすることが可能になる。つまり、この保証が成り立てば、対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性を保証することが可能になる。図28を参照しながら、m本のn次多変数多項式で構成される関数F:Kn→Kmについて考えると但し、n>m、2つ目の原像を持たない定義域の要素数は、最大で|K|m-1個しか存在しない。そのため、|K|m-nを十分に小さくすると、2つ目の原像を持たない定義域の要素が選択される確率を無視できる程度まで小さくすることができる。つまり、n変数多次多項式f1,...,fmの数mがその変数の数nよりも十分に小さな値に設定されていれば、公開鍵pkに対して2つ以上の秘密鍵sが存在することを保証できる。その結果、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにすることが可能になり、対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性が保証される。以上説明したように、n変数多次多項式f1,...,fmの数mがその変数の数nよりも小さな値n>m;好ましくは2m-n≪1に設定する方法を適用することで、対話プロトコルを並列的に繰り返し実行する場合の安全性を向上させることが可能になる。[3-4:非対話型アルゴリズム]これまで5パスの公開鍵認証方式について説明してきた。しかし、本手法においては、検証者から証明者に送られる情報が実際には単なる乱数だけであるため、1パスの公開鍵認証方式以下、非対話型方式に変形することができる。なお、非対話型方式に係る各アルゴリズムの内容を図16に示した。以下、図16を参照しながら、非対話型方式に係る各アルゴリズムの内容について説明する。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1x1,...,xn,...,fmx1,...,xnと、ベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトルx1,...,xnをxと表記し、m本のn変数多次多項式f1x,...,fmxをFxと表記する。証明者アルゴリズムP、検証者アルゴリズムV次に、図16を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、証明者がy=Fsを満たすsを知っていることをsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。Step.1:まず、証明者アルゴリズムPは、i=1~Nについて、以下の処理1~処理5を実行する。処理1証明者アルゴリズムPは、任意に数wiを選択する。処理2証明者アルゴリズムPは、擬似乱数生成器Gに数wiを適用してベクトルri∈Knと多項式の組F’ixを生成する。つまり、証明者アルゴリズムPは、ri,F’i←Gwiを計算する。処理3証明者アルゴリズムPは、zi←s-riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。Step.1続き:処理4証明者アルゴリズムPは、Fiziとziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1Fizi,ziを計算する。処理5証明者アルゴリズムPは、数wiのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2wiを計算する。Step.1続き:次に、検証者アルゴリズムVは、乱数RA,RBを選択する。そして、検証者アルゴリズムVは、乱数RAと上記の処理4及び5で計算されたハッシュ値c1,i,c2,iをハッシュ関数HAに適用してハッシュ値α1,...,αNを生成する。つまり、検証者アルゴリズムVは、α1,...,αN←HARA,c1,1,...,c2,Nを計算する。Step.1続き:次に、検証者アルゴリズムVは、i=1~Nについて、以下の処理1及び2を実行する。処理1証明者アルゴリズムPは、Fix←αiFxriF’ixを計算する。この計算は、xについての多項式の組Fxriを多項式の組F’ixによりマスクする操作に相当する。処理2証明者アルゴリズムPは、i=1~Nについて、乱数RA,RB、ハッシュ値c1,i、c2,i、αi,Fiをハッシュ関数HBに適用してd=d1,...,dNを生成する。つまり、証明者アルゴリズムPは、d1,...,dN←HBRA,RB,c1,1,...,c2,N,α1,...,αN,F1,...,FNを計算する。Step.1続き:次に、証明者アルゴリズムPは、生成したdiに応じて検証者に送り返す情報σiを生成する。ここで、証明者アルゴリズムPは、i=1~Nについて、以下の処理1又は処理2を実行する。処理1di=0の場合、証明者アルゴリズムPは、情報σi=wiを生成する。処理2di=1の場合、証明者アルゴリズムPは、情報σi=ziを生成する。上記処理1又は処理2の判定及び処理が実行された後、RA、RB、c1,i、c2,i、σii=1~Nは、証明者アルゴリズムPにより検証者に送られる。Step.2:検証者アルゴリズムVは、まず、証明者から受け取ったRA、c1,i、c2,iをハッシュ関数HAに適用してαiを生成する。つまり、検証者アルゴリズムVは、α1,...,αN←HARA,c1,1,...,c2,Nを計算する。次いで、検証者アルゴリズムVは、d=d1,...,dN←HBRA,RB,c1,1,...,c2,N,α1,...,αN,F1,...,FNを計算する。次いで、検証者アルゴリズムVは、情報σii=1~Nを利用して以下の検証処理を実行する。なお、以下の処理は、i=1~Nについて実行される。di=0の場合、検証者アルゴリズムVは、r’i,Fi←Gσiを計算する。そして、検証者アルゴリズムVは、c2,i=H2σiの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、Fix=αiFxr’iFixの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。di=1の場合、検証者アルゴリズムVは、z’i←σiを計算する。そして、検証者アルゴリズムVは、c1,i=H1Fiz’i-αiy,z’iの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、非対話型方式に係る各アルゴリズムの内容について説明した。なお、理想的なハッシュ関数HA、HBを仮定すれば、ハッシュ値αi,diがランダムに振る舞うため、証明者に都合の良いハッシュ値αi,diが出ることはない。そのため、上記のような変形を行っても、十分な安全性が確保される。なお、このような変形は、拡張方式などに対しても同様に適用することが可能である。[3-5:電子署名方式への変形]ここで、本手法を電子署名方式へと変形する方法について説明する。なお、ここでは簡単のために、上記の非対話型方式を電子署名方式に変形する方法について述べる。上記の非対話型方式における証明者と検証者を電子署名方式における署名者と検証者に対応させると、証明者のみが検証者を納得させられるという点において、電子署名方式のモデルと近似していることが分かるであろう。こうした考えをもとに、非対話型方式に基づく電子署名方式のアルゴリズム構成について詳細に説明する。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1x1,...,xn,...,fmx1,...,xnと、ベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトルx1,...,xnをxと表記し、m本のn変数多次多項式f1x,...,fmxをFxと表記する。署名生成アルゴリズムSig署名生成アルゴリズムSigは、i=1~Nについて、以下の処理1~処理11を実行する。なお、署名生成アルゴリズムSigには、署名鍵sk=sと文書Mが入力されているものとする。処理1署名生成アルゴリズムSigは、任意に数wiを選択する。処理2署名生成アルゴリズムSigは、擬似乱数生成器Gに数wiを適用してベクトルri∈Knとn変数多項式の組F’ix=f1,1’x,...,fm,i’xを生成する。つまり、署名生成アルゴリズムSigは、ri,F’i←Gwiを計算する。処理2署名生成アルゴリズムSigは、zi←s-riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。処理3署名生成アルゴリズムSigは、Fiziとziのハッシュ値c1,iを生成する。つまり、署名生成アルゴリズムSigは、c1,i←H1Fizi,ziを計算する。処理4署名生成アルゴリズムSigは、数w’iのハッシュ値c2,iを生成する。つまり、署名生成アルゴリズムSigは、c2,i←H2w’iを計算する。なお、上記のH1...、H2...は、ハッシュ関数である。処理4署名生成アルゴリズムSigは、乱数RAを任意に選択する。処理5署名生成アルゴリズムSigは、α=α1,...,αN←HARA,M,c1,1,...,c2,Nを計算する。処理6署名生成アルゴリズムSigは、i=1~Nについて、Fix=αiFxr’iF’ixを計算する。処理7署名生成アルゴリズムSigは、乱数RBを任意に選択する。処理8署名生成アルゴリズムSigは、d=d1,...,dN←HBRB,M,c1,1,...,c2,N,α,F1,...,FNを計算する。次に、署名生成アルゴリズムSigは、i=1~Nについて、diに応じた次の処理9又は処理10を実行する。処理9di=0の場合、署名生成アルゴリズムSigは、σi←wiを計算する。処理10di=1の場合、署名生成アルゴリズムSigは、σi←ziを計算する。処理11i=1~Nについて、上記処理9又は処理10の判定及び処理が実行された後、署名生成アルゴリズムSigは、電子署名σ=RA,RB,c1,1,...,c2,N,α1,...,αN,F1,...,FN,σ1,...,σNを出力する。署名検証アルゴリズムVer署名検証アルゴリズムVerは、i=1~Nについて、以下の全ての検証を通過すれば、電子署名σを受理し、1つでも検証を通過しなかった場合には電子署名σを拒否する。なお、署名検証アルゴリズムVerには、電子署名σと文書Mが入力されているものとする。まず、署名検証アルゴリズムVerは、α=α1,...,αN←HARA,M,c1,1,...,c3,Nを計算する。次いで、署名検証アルゴリズムVerは、d=d1,...,dN←HR,M,c1,1,...,c3,N,α,F1,...,FNを計算する。次いで、署名検証アルゴリズムVerは、i=1~Nについて、以下の検証1~検証3を実行する。検証1di=0の場合、署名検証アルゴリズムVerは、r’i,Fi←Gσiを計算する。そして、署名検証アルゴリズムVerは、c2,i=H2σiの等号が成り立つか否かを検証する。また、署名検証アルゴリズムVerは、Fix=αiFxr’iF’ix1,...,xnの等号が成り立つか否かを検証する。署名検証アルゴリズムVerは、これらの検証が全て成功した場合に電子署名σの受理を示す値1を出力し、検証に失敗があった場合に電子署名σの拒否を示す値0を出力する。検証2di=1の場合、署名検証アルゴリズムVerは、z’i,Fi←σiを計算する。そして、署名検証アルゴリズムVerは、c1,i=H1Fiz’i,z’iの等号が成り立つか否かを検証する。署名検証アルゴリズムVerは、この検証が成功した場合に電子署名σの受理を示す値1を出力し、検証に失敗があった場合に電子署名σの拒否を示す値0を出力する。以上、本手法に基づく電子署名方式の各アルゴリズム構成について説明した。なお、同様にして、上記の拡張方式に基づく電子署名方式を構築することも可能である。[3-6:具体例]次に、図17を参照しながら、本手法を実施する際に想定される具体的なアルゴリズム構成について説明する。図17は、本手法の具体例を説明するための説明図である。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f1x1,...,xn,...,fmx1,...,xnと、ベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトルx1,...,xnをxと表記し、m本のn変数多次多項式f1x,...,fmxをFxと表記する。証明者アルゴリズムP、検証者アルゴリズムV次に、図17を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、証明者がy=Fsを満たすsを知っていることをsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。Step.1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Knと、n変数多項式の組F’x=f’1x,...,f’mxを生成する。つまり、証明者アルゴリズムPは、r,F’←Gwを計算する。次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。但し、多項式f’ixは、下記の式20のように表現される。Step.1続き:次いで、証明者アルゴリズムPは、F’zとzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1F’z,zを計算する。また、証明者アルゴリズムPは、数wのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2wを計算する。なお、上記のH1...、H2...は、ハッシュ関数である。また、ハッシュ値c1,c2はメッセージである。Step.1で生成されたメッセージc1,c2は、検証者に送られる。Step.2:検証者アルゴリズムVは、q通り存在する環Kの元から1つの乱数αを選択する。そして、検証者アルゴリズムVは、選択した乱数αを証明者に送る。Step.3:証明者アルゴリズムPは、Fx←αFxrF’xを計算する。この計算は、xについての多項式の組Fxrを多項式の組F’xによりマスクする操作に相当する。Step.3で生成された多項式Fは、検証者に送られる。Step.4:検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1}を証明者に送る。Step.5:証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=zを生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。Step.6:検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、r’,F←Gσを計算する。そして、検証者アルゴリズムVは、c2=H2σの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、Fx=αFxr’Fxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、z’←σとする。そして、検証者アルゴリズムVは、c1=H1Fz’-αy,z’の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、本手法を実施する際に想定される具体的なアルゴリズム構成について説明した。[3-7:効率的なアルゴリズム]ここで、上記の第1実施形態と同様、効率の良いアルゴリズムについて考える。例えば、xについての多項式の組Fxrをマスクするために用いた多項式の組F’xを、2つのベクトルt∈Kn、e∈Kmを用いてF’x=Fbx、teのように表現する方法について考える。この方法を用いると、xについての多項式の組Fxrは、下記の式21のように表現される。そのため、t’=αrt,e’=αFr-ceとすれば、マスク後のxに関する多項式の組Fxも、2つのベクトルt’∈Kn、e∈Kmにより表現することができる。これらの理由から、F’をF’x=Fbx,teと設定すれば、F’とFの表現がKn上のベクトルとKm上のベクトルによる表現されることになり、通信に必要なデータサイズを大幅に削減することが可能になる。また、上記の変形により、F又はF’からrに関する情報が一切漏れることはない。例えば、e’,t’又はe,tを与えられても、e,t又はe’,t’を知らない限り、rの情報を一切知ることはできない。従って、上記の変形を施した本手法は、零知識性が担保された公開鍵認証方式である。以下、図18~図25を参照しながら、上記の変形を施した本手法に係る効率的なアルゴリズムについて、より詳細に説明する。なお、鍵生成アルゴリズムGenの構成については先に説明した本手法と実質的に同じであるため、詳細な説明を省略する。Step.1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Kn、t∈Kn、e∈Kmを生成する。つまり、証明者アルゴリズムPは、r,t,e←Gwを計算する。次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。Step.1続き:次いで、証明者アルゴリズムPは、Fbz,teとzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1Fbz,te,zを計算する。また、証明者アルゴリズムPは、数wのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2wを計算する。なお、上記のH1...、H2...は、ハッシュ関数である。また、ハッシュ値c1,c2はメッセージである。Step.1で生成されたメッセージc1,c2は、検証者に送られる。Step.2:検証者アルゴリズムVは、q通り存在する環Kの元から1つの乱数αを選択する。そして、検証者アルゴリズムVは、選択した乱数αを証明者に送る。Step.3:証明者アルゴリズムPは、t’←αrtを計算する。さらに、証明者アルゴリズムPは、e’←αFr-ceを計算する。そして、証明者アルゴリズムPは、t’,e’を検証者に送る。Step.4:検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1}を証明者に送る。Step.5:証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=zを生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。Step.6:検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、r’,t,e←Gσを計算する。そして、検証者アルゴリズムVは、c2=H2σの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、t’=αr’tの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、e’=αFr’-ceの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、z’←σとする。そして、検証者アルゴリズムVは、c1=H1αFz’-yFbz’,t’e’,z’の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、本手法に係る効率的なアルゴリズム構成について説明した。この効率的なアルゴリズムを利用することにより、通信に必要なデータサイズを大幅に削減することができる。また、対話プロトコルの中で、xrを多項式Fに代入し、xについて整理しなおす計算Fxrの計算が必要なくなるため、計算効率も向上する。効率的なアルゴリズムの変形例についてさて、図18に示した本手法の効率的なアルゴリズムは、その計算効率を維持しながら、図19~図25に示すようなアルゴリズムに変形することが可能である。変形例A:図19に示すアルゴリズム例えば、図18に示した効率的なアルゴリズムのStep.3において、e’←αFr-ceという計算を行っているが、この計算を図19に示すようにe’←αFreという計算に変形してもよい。但し、この変形を行う場合には、Step.6において検証者が行う検証内容の一部を変形する必要がある。具体的には、Step.6においてd=0の場合に検証者が行う検証内容のうち、e’=αFr’-ceの検証をe’=αFr’eの検証に置き換える必要がある。また、Step.6においてd=1の場合に検証者が行う検証内容のうち、c1=H1αFz’-yFbz’,t’’’e’’’,z’の検証をc1=H1αFz’-c-yFbz’,t’’’e’’’,z’の検証に置き換える必要がある。変形例B:図20に示すアルゴリズムまた、図19に示したアルゴリズムのStep.5において、d=0の場合にσをwに設定しているが、d=0の場合に設定されるσは、t’,e’’に併せて用いることでr,t,eが復元できるような情報であればどのような情報でもよい。例えば、図20に示すように、Step.5においてd=0の場合に設定されるσの内容をrにしてもよい。但し、この変形を行う場合には、図19に示したアルゴリズムのStep.1における計算c2←H2wをc2←H2r,t,eに変形する必要がある。また、Step.6においてd=0の場合に検証者が行う検証内容をc2=H2r,t’-αr,e’-αFrの検証に置き換える必要がある。変形例C:図21に示すアルゴリズムまた、図20に示したアルゴリズムのStep.3において、t’←αrtという計算を行っているが、この計算を図21に示すようにt’←αrtという計算に変形してもよい。但し、この変形を行う場合には、図20に示したアルゴリズムのStep.6においてd=0の場合に検証者が行う検証内容をc2=H2r,α-1t’-r,e’-αFrの検証に置き換える必要がある。変形例D:図22に示すアルゴリズムまた、図20に示したアルゴリズムのStep.3において、e’←αFreという計算を行っているが、この計算を図22に示すようにe’←αFreという計算に変形してもよい。但し、この変形を行う場合には、図20に示したアルゴリズムのStep.6においてd=0の場合に検証者が行う検証内容をc2=H2r,t’-αr,e’-α-1e’-Frの検証に置き換える必要がある。変形例E:図23に示すアルゴリズムまた、図20に示したアルゴリズムのStep.5において、d=0の場合にσをrに設定しているが、d=0の場合に設定されるσは、t’,e’’に併せて用いることでr,t,eが復元できるような情報であればどのような情報でもよい。例えば、図23に示すように、Step.5においてd=0の場合に設定されるσの内容をtにしてもよい。但し、この変形を行う場合には、Step.2においてαがα∈RK\{0}から選ばれるようにすると共に、Step.6においてd=0の場合に検証者が行う検証内容をc2=H2α-1t’-t,t,e’-αFα-1t’-tの検証に置き換える必要がある。変形例F:図24に示すアルゴリズムまた、図23に示したアルゴリズムのStep.3において、t’←αrtという計算を行っているが、この計算を図24に示すようにt’←αrtという計算に変形してもよい。但し、この変形を行う場合には、図23に示したアルゴリズムのStep.6においてd=0の場合に検証者が行う検証内容をc2=H2α-1t’-t,t,e’-αFα-1t’-tの検証に置き換える必要がある。変形例G:図25に示すアルゴリズムまた、図23に示したアルゴリズムのStep.3において、e’←αFreという計算を行っているが、この計算を図25に示すようにe’←αFreという計算に変形してもよい。但し、この変形を行う場合には、図23に示したアルゴリズムのStep.6においてd=0の場合に検証者が行う検証内容をc2=H2α-1t’-t,t,α-1e’-αFα-1t’-tの検証に置き換える必要がある。上記のように、Step.3において証明者が行うe’←αFr-ceという計算をe’←αFreという計算に変更することができる変形例A。また、Step.5においてd=0の場合に証明者が設定するσの内容をrやtなどに変更することができる変形例B、E。さらに、Step.3において証明者が行うt’←αrtという計算をt’←αrtという計算に変更することができる変形例C、F。また、Step.3において証明者が行うe’←αFreという計算をe’←αFreという計算に変更することができる変形例D、G。変形例Aに係る変形、変形例B、Eに係る変形、変形例C、Fに係る変形、及び変形例D、Gに係る変形は、それぞれ単独で図18に示した効率的なアルゴリズムに適用することもできるし、複数の変形を組み合わせて図18に示した効率的なアルゴリズムに適用することもできる。以上、本発明の第2実施形態について説明した。なお、多変数連立方程式の形式については、上記の第1実施形態と同様である。<4:効率的なアルゴリズムの一般化>ところで、上記の第1及び第2実施形態に係る効率的なアルゴリズムは、下記の式22で表現される2次の多変数多項式を公開鍵又はシステムパラメータとして利用する構成であった。しかし、上記の効率的なアルゴリズムは、位数q=pkの体上で定義される3次以上の多次多変数多項式下記の式23を参照を公開鍵又はシステムパラメータとして利用する構成に拡張することができる。上記の第1及び第2実施形態に係る効率的なアルゴリズムにおける公開鍵として多変数多項式flが利用可能となる条件は、下記の式24がx1,...,xn及びy1,...,ynに対して双線形になることである。上記の式22で表現される多変数多項式の場合、下記の式25に示すように容易に双線形性を確認することができる下線部がxi、yiのそれぞれについて線形となっている。また、上記の式23で表現される多変数多項式の場合についても同様にして、下記の式26に示すように双線形性を確認することができる。但し、下記の式26の下線部は、位数pの体GFp上における双線形性を示している。そのため、上記の第2実施形態に係る効率的なアルゴリズムの公開鍵として上記の式23で表現される多変数多項式を利用する場合、当該アルゴリズムのStep.2の後に検証者が送信するチャレンジαは、GFpの要素に限定する必要がある。このような理由から、上記の第1及び第2実施形態に係る効率的なアルゴリズムを拡張し、上記の式23で表現されるような3次以上の多変数多項式を公開鍵として利用するアルゴリズムを構築することが可能であると言える。ここで、上記の式22で表現される多変数多項式以下、2次多項式と、上記の式23で表現される多変数多項式以下、多次多項式との関係について考察しておきたい。いま、位数q=pの体上で定義されるnk変数の2次多項式、及び位数q=pkの体上で定義されるn変数の多次多項式について考える。この場合、mk本の2次多項式で構成される連立方程式の解答困難性は、m本の多次多項式で構成される連立方程式の解答困難性と等価である。例えば、位数2の体上で定義される80本の80変数2次多項式により構成される連立方程式と、位数28の体上で定義される10本の10変数多次多項式とは、その解答困難性が等価である。つまり、GFpkの要素と、GFpkの要素とを同型写像により同一視した場合、位数q=pの体上で定義されるmk本のnk変数2次多項式の組で表現される関数と等価な、位数q=pkの体上で定義されるm本のn変数多次多項式の組で表現される関数が存在する。例えば、GF28の要素と、GF28の要素とを同型写像により同一視した場合、位数2の体上で定義される80本の80変数2次多項式の組で表現される関数と等価な、位数28の体上で定義される10本の10変数多次多項式の組で表現される関数が存在する。このような理由から、上記の2次多項式を利用するか、上記の多次多項式を利用するかは、任意に選択することが可能である。ここで、上記の2次多項式を利用する場合の計算効率と上記の多次多項式を利用する場合の計算効率について考察しておきたい。位数2の体上で定義されるnk変数2次多項式を利用する場合、アルゴリズムに含まれる演算は、nk個の1ビット変数を対象に実行されることになる。つまり、演算の単位が1ビットとなる。一方、位数2kの体上で定義されるn変数多次多項式を利用する場合、アルゴリズムに含まれる演算は、n個のkビット変数を対象に実行されることになる。つまり、演算の単位がkビットとなる。このkk=2,3,4,...は任意に設定することができる。そのため、実装上、都合の良い値にkを設定することにより、計算効率を向上させることが可能になる。例えば、32ビットのアーキティクチャ上にアルゴリズムを実装する場合、1ビット単位で演算を実行する構成にするよりも、32ビット単位で演算を実行する構成にする方が高い計算効率を得られる。このように、上記の第1及び第2実施形態に係る効率的なアルゴリズムを、多次多項式を公開鍵として利用できるように拡張することで、演算の単位を実装するアーキティクチャに合わせることが可能になる。その結果、計算効率を向上させることが可能になる。<5:ハードウェア構成例>上記の各アルゴリズムは、例えば、図26に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図26に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、PHS、PDA等の携帯情報端末、ゲーム機、接触式又は非接触式のICチップ、接触式又は非接触式のICカード、又は種々の情報家電がこれに含まれる。但し、上記のPHSは、PersonalHandy-phoneSystemの略である。また、上記のPDAは、PersonalDigitalAssistantの略である。図26に示すように、このハードウェアは、主に、CPU902と、ROM904と、RAM906と、ホストバス908と、ブリッジ910と、を有する。さらに、このハードウェアは、外部バス912と、インターフェース914と、入力部916と、出力部918と、記憶部920と、ドライブ922と、接続ポート924と、通信部926と、を有する。但し、上記のCPUは、CentralProcessingUnitの略である。また、上記のROMは、ReadOnlyMemoryの略である。そして、上記のRAMは、RandomAccessMemoryの略である。CPU902は、例えば、演算処理装置又は制御装置として機能し、ROM904、RAM906、記憶部920、又はリムーバブル記録媒体928に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ROM904は、CPU902に読み込まれるプログラムや演算に用いるデータ等を格納する手段である。RAM906には、例えば、CPU902に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等が一時的又は永続的に格納される。これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス908を介して相互に接続される。一方、ホストバス908は、例えば、ブリッジ910を介して比較的データ伝送速度が低速な外部バス912に接続される。また、入力部916としては、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等が用いられる。さらに、入力部916としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラ以下、リモコンが用いられることもある。出力部918としては、例えば、CRT、LCD、PDP、又はELD等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等、取得した情報を利用者に対して視覚的又は聴覚的に通知することが可能な装置である。但し、上記のCRTは、CathodeRayTubeの略である。また、上記のLCDは、LiquidCrystalDisplayの略である。そして、上記のPDPは、PlasmaDisplayPanelの略である。さらに、上記のELDは、Electro-LuminescenceDisplayの略である。記憶部920は、各種のデータを格納するための装置である。記憶部920としては、例えば、ハードディスクドライブHDD等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等が用いられる。但し、上記のHDDは、HardDiskDriveの略である。ドライブ922は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体928に記録された情報を読み出し、又はリムーバブル記録媒体928に情報を書き込む装置である。リムーバブル記録媒体928は、例えば、DVDメディア、Blu-rayメディア、HDDVDメディア、各種の半導体記憶メディア等である。もちろん、リムーバブル記録媒体928は、例えば、非接触型ICチップを搭載したICカード、又は電子機器等であってもよい。但し、上記のICは、IntegratedCircuitの略である。接続ポート924は、例えば、USBポート、IEEE1394ポート、SCSI、RS-232Cポート、又は光オーディオ端子等のような外部接続機器930を接続するためのポートである。外部接続機器930は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はICレコーダ等である。但し、上記のUSBは、UniversalSerialBusの略である。また、上記のSCSIは、SmallComputerSystemInterfaceの略である。通信部926は、ネットワーク932に接続するための通信デバイスであり、例えば、有線又は無線LAN、Bluetooth登録商標、又はWUSB用の通信カード、光通信用のルータ、ADSL用のルータ、又は接触又は非接触通信用のデバイス等である。また、通信部926に接続されるネットワーク932は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内LAN、赤外線通信、可視光通信、放送、又は衛星通信等である。但し、上記のLANは、LocalAreaNetworkの略である。また、上記のWUSBは、WirelessUSBの略である。そして、上記のADSLは、AsymmetricDigitalSubscriberLineの略である。<6:まとめ>最後に、本発明の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、PC、携帯電話、携帯ゲーム機、携帯情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置に対して適用することができる。上記の情報処理装置の機能構成は次のように表現することができる。当該情報処理装置は、次のような鍵設定部と、メッセージ送信部と、検証パターン受信部と、回答送信部とを有する。上記の鍵設定部は、s∈Knを秘密鍵に設定し、環K上の多次多項式fix1,...,xni=1~m及びyi=fisを公開鍵に設定するものである。i=1~mについてyi=fisを求める問題は、多次多変数連立方程式の求解問題に他ならない。つまり、上記の情報処理装置は、多次多変数連立方程式の求解問題に安全性の根拠をおく認証の仕組みを提供するものである。また、上記のメッセージ送信部は、検証者に対してメッセージcを送信するものである。さらに、上記の検証パターン受信部は、1つの前記メッセージcに対するk通りk≧3の検証パターンの中から前記検証者により選択された1つの検証パターンの情報を受信するものである。そして、上記の回答送信部は、k通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信するものである。但し、前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である。上記のメッセージcには、例えば、3つのメッセージc1、c2、c3が含まれている。そして、各検証パターンでは、c1、c2、c3のいずれか2つに対する検証が行われる。また、上記の回答情報は、各検証パターンに応じて、上記いずれか2つのメッセージに対する検証を行うために必要な情報である。但し、上記のメッセージcを検証者に渡しても、秘密鍵の情報が一切漏れないことが1つの条件である。もう1つの条件は、メッセージcと回答情報が揃っても秘密鍵の情報が一切漏れないことである。これらの条件を満たすメッセージcの構成、及び回答情報の構成については、図4などを参照しながら、既に具体的に説明した通りである。備考上記の鍵生成アルゴリズムGenは、鍵設定部の一例である。上記の証明者アルゴリズムPは、メッセージ送信部、検証パターン受信部、回答送信部、応答受信部、多項式生成部、多項式送信部の一例である。上記の情報σは、回答情報の一例である。上記の検証者アルゴリズムVは、メッセージ受信部、検証パターン選択部、検証パターン送信部、回答受信部、検証部、応答送信部、多項式受信部の一例である。上記の署名生成アルゴリズムSigは、メッセージ生成部、検証パターン選択部、署名生成部の一例である。以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。"