"環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記2次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、前記メッセージを生成する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、情報処理装置。前記メッセージ生成部は、N回分N≧2のメッセージを生成し、前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、請求項1に記載の情報処理装置。環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記2次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記2次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証部は、前記検証に用いるメッセージを再生する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、情報処理装置。前記メッセージ取得部は、N回分N≧2の前記メッセージを1回の対話で取得し、前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、請求項3に記載の情報処理装置。環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記2次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、前記検証者に前記第3の情報を提供する中間情報提供部と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、前記メッセージを生成する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、情報処理装置。前記メッセージ生成部は、N回分N≧2のメッセージを生成し、前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、前記中間情報生成部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した前記第1の情報及び前記メッセージを生成する際に得られるN回分の前記第2の情報を用いてN回分の前記第3の情報を生成し、前記中間情報提供部は、N回分の前記第3の情報を1回の対話で検証者に提供し、前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、請求項5に記載の情報処理装置。環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記2次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供部と、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得部と、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記第1の情報、前記第3の情報、前記2次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証部は、前記検証に用いるメッセージを再生する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、情報処理装置。前記メッセージ取得部は、N回分N≧2の前記メッセージを1回の対話で取得し、前記情報提供部は、N回分の前記メッセージのそれぞれについて前記第1の情報をランダムに選択し、選択したN回分の前記第1の情報を1回の対話で前記証明者に提供し、前記中間情報取得部は、N回分の前記第1の情報及びN回分の前記メッセージを生成する際に得られるN回分の前記第2の情報を用いて前記証明者が生成したN回分の前記第3の情報を取得し、前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、請求項7に記載の情報処理装置。環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成する署名生成部と、前記2次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供する署名提供部と、を備え、前記署名生成部は、前記電子署名を生成する過程で実行する、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、署名生成装置。環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=f1s,...,fmsを保持する情報保持部と、文書Mについて、前記2次多変数多項式の組F及び署名鍵s∈Knを用いて生成された電子署名に基づいて前記文書Mの正当性を検証する署名検証部と、を備え、前記署名検証部は、前記電子署名を検証する過程で実行する、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、署名検証装置。環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記2次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記生成するステップでは、前記メッセージを生成する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、情報処理方法。環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報処理装置が、前記2次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記2次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証するステップでは、前記検証に用いるメッセージを再生する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、情報処理方法。環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記2次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、前記検証者に前記第3の情報を提供するステップと、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージを生成するステップでは、前記メッセージを生成する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、情報処理方法。環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報処理装置が、前記2次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供するステップと、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得するステップと、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記第1の情報、前記第3の情報、前記2次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証するステップでは、前記検証に用いるメッセージを再生する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、情報処理方法。環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成するステップと、前記2次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供するステップと、を含み、前記生成するステップでは、前記電子署名を生成する過程で実行される、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、署名生成方法。環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=f1s,...,fmsを保持する情報処理装置が、文書Mについて、前記2次多変数多項式の組F及び署名鍵s∈Knを用いて生成された電子署名に基づいて前記文書Mの正当性を検証するステップを含み、前記検証するステップでは、前記電子署名を検証する過程で実行される、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、署名検証方法。上記の通り、多変数多項式問題は、量子コンピュータを用いても解くことが困難な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しか用いることができず、十分な安全性を確保することが難しかった。本技術は、上記の事情に鑑みて、効率的に解く手段トラップドアが知られていない多次多変数連立方程式を用いて高い安全性を有する効率的な公開鍵認証方式又は電子署名方式を実現することが可能な、新規かつ改良された情報処理装置、署名生成装置、署名検証装置、情報処理方法、署名生成方法、及び署名検証方法の提供を意図して考案されたものである。本技術のある観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記2次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、前記メッセージを生成する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、情報処理装置が提供される。また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記2次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記2次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証部は、前記検証に用いるメッセージを再生する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、情報処理装置が提供される。また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記2次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、前記検証者に前記第3の情報を提供する中間情報提供部と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、前記メッセージを生成する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、情報処理装置が提供される。また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記2次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供部と、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得部と、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記第1の情報、前記第3の情報、前記2次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証部は、前記検証に用いるメッセージを再生する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、情報処理装置が提供される。また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成する署名生成部と、前記2次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供する署名提供部と、を備え、前記署名生成部は、前記電子署名を生成する過程で実行する、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、署名生成装置が提供される。また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=f1s,...,fmsを保持する情報保持部と、文書Mについて、前記2次多変数多項式の組F及び署名鍵s∈Knを用いて生成された電子署名に基づいて前記文書Mの正当性を検証する署名検証部と、を備え、前記署名検証部は、前記電子署名を検証する過程で実行する、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、署名検証装置が提供される。また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記2次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記生成するステップでは、前記メッセージを生成する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、情報処理方法が提供される。また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報処理装置が、前記2次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記2次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証するステップでは、前記検証に用いるメッセージを再生する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、情報処理方法が提供される。また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記2次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、前記検証者に前記第3の情報を提供するステップと、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージを生成するステップでは、前記メッセージを生成する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、情報処理方法が提供される。また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報処理装置が、前記2次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供するステップと、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得するステップと、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記第1の情報、前記第3の情報、前記2次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証するステップでは、前記検証に用いるメッセージを再生する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、情報処理方法が提供される。また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成するステップと、前記2次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供するステップと、を含み、前記生成するステップでは、前記電子署名を生成する過程で実行される、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、署名生成方法が提供される。また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=f1s,...,fmsを保持する情報処理装置が、文書Mについて、前記2次多変数多項式の組F及び署名鍵s∈Knを用いて生成された電子署名に基づいて前記文書Mの正当性を検証するステップを含み、前記検証するステップでは、前記電子署名を検証する過程で実行される、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、署名検証方法が提供される。また、本技術の別の観点によれば、上記の情報処理装置、署名生成装置、署名検証装置が有する各部の機能をコンピュータに実現させるためのプログラムが提供される。また、本技術の別の観点によれば、当該プログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。また、本技術の別の観点によれば、上記のプログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。以上説明したように本技術によれば、効率的に解く手段トラップドアが知られていない多次多変数連立方程式を用いて、高い安全性を有する効率的な公開鍵認証方式又は電子署名方式を実現することが可能になる。以下に添付図面を参照しながら、本技術の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。[説明の流れについて]ここで、以下に記載する本技術の実施形態に関する説明の流れについて簡単に述べる。まず、図1を参照しながら、公開鍵認証方式のアルゴリズム構成について説明する。次いで、図2を参照しながら、電子署名方式のアルゴリズム構成について説明する。次いで、図3を参照しながら、nパスの公開鍵認証方式について説明する。次いで、図4及び図5を参照しながら、3パスの公開鍵認証方式に係るアルゴリズムの構成例について説明する。次いで、図6及び図7を参照しながら、5パスの公開鍵認証方式に係るアルゴリズムの構成例について説明する。次いで、図8及び図9を参照しながら、3パス及び5パスの公開鍵認証方式に係る効率的なアルゴリズムを電子署名方式のアルゴリズムに変形する方法について説明する。次いで、図10を参照しながら、本技術の第1及び第2実施形態に係る各アルゴリズムを実現することが可能な情報処理装置のハードウェア構成例について説明する。最後に、本実施形態の技術的思想について纏め、当該技術的思想から得られる作用効果について簡単に説明する。説明項目1:はじめに1-1:公開鍵認証方式のアルゴリズム1-2:電子署名方式のアルゴリズム1-3:nパスの公開鍵認証方式2:3パスの公開鍵認証方式に係るアルゴリズムの構成2-1:具体的なアルゴリズムの構成例2-2:並列化アルゴリズムの構成例3:5パスの公開鍵認証方式に係るアルゴリズムの構成3-1:具体的なアルゴリズムの構成例3-2:並列化アルゴリズムの構成例4:電子署名方式への変形4-1:3パスの公開鍵認証方式から電子署名方式への変形4-2:5パスの公開鍵認証方式から電子署名方式への変形5:双線形項Gの効率的な計算方法5-1:原理説明5-2:適用例13パス方式への適用5-3:適用例25パス方式への適用5-4:適用例3電子署名方式への適用6:ハードウェア構成例7:まとめ<1:はじめに>本実施形態は、多次多変数連立方程式に対する求解問題の困難性に安全性の根拠をおく公開鍵認証方式及び電子署名方式に関する。但し、本実施形態は、HFE電子署名方式などの従来手法とは異なり、効率的に解く手段トラップドアを持たない多次多変数連立方程式を利用する公開鍵認証方式及び電子署名方式に関する。まず、公開鍵認証方式のアルゴリズム、電子署名方式のアルゴリズム、及びnパスの公開鍵認証方式について、その概要を簡単に説明する。[1-1:公開鍵認証方式のアルゴリズム]まず、図1を参照しながら、公開鍵認証方式のアルゴリズムについて概要を説明する。図1は、公開鍵認証方式のアルゴリズムについて概要を説明するための説明図である。公開鍵認証は、ある人証明者が、公開鍵pk及び秘密鍵skを利用して、他の人検証者に本人であることを納得させるために利用される。例えば、証明者Aの公開鍵pkAは、検証者Bに公開される。一方、証明者Aの秘密鍵skAは、証明者Aにより秘密に管理される。公開鍵認証の仕組みにおいては、公開鍵pkAに対応する秘密鍵skAを知る者が証明者A本人であるとみなされる。公開鍵認証の仕組みを利用して証明者Aが証明者A本人であることを検証者Bに証明するには、対話プロトコルを介して、証明者Aが公開鍵pkAに対応する秘密鍵skAを知っているという証拠を検証者Bに提示すればよい。そして、証明者Aが秘密鍵skAを知っているという証拠が検証者Bに提示され、その証拠を検証者Bが確認し終えた場合、証明者Aの正当性本人であることが証明されたことになる。但し、公開鍵認証の仕組みには、安全性を担保するために以下の条件が求められる。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を実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図10に示した通りである。つまり、鍵生成アルゴリズム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を出力するアルゴリズムである。なお、検証者は、検証者アルゴリズムVが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を実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図10に示した通りである。つまり、鍵生成アルゴリズムGen、署名生成アルゴリズムSig、署名検証アルゴリズムVerは、ROM904、RAM906、記憶部920、リムーバブル記録媒体928などに記録されたプログラムに基づいてCPU902などにより実行される。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、署名者により利用される。鍵生成アルゴリズムGenは、署名者固有の署名鍵skと検証鍵pkとの組を生成するアルゴリズムである。鍵生成アルゴリズムGenにより生成された検証鍵pkは公開される。一方、鍵生成アルゴリズムGenにより生成された署名鍵skは、署名者により秘密に管理される。そして、署名鍵skは、文書Mに付与される電子署名σの生成に利用される。例えば、鍵生成アルゴリズムGenは、セキュリティパラメータ1λλは0以上の整数を入力とし、署名鍵sk及び公開鍵pkを出力する。この場合、鍵生成アルゴリズムGenは、形式的に、下記の式3のように表現することができる。署名生成アルゴリズムSig署名生成アルゴリズムSigは、署名者により利用される。署名生成アルゴリズムSigは、文書Mに付与される電子署名σを生成するアルゴリズムである。署名生成アルゴリズムSigは、署名鍵skと文書Mとを入力とし、電子署名σを出力するアルゴリズムである。この署名生成アルゴリズムSigは、形式的に、下記の式4のように表現することができる。署名検証アルゴリズムVer署名検証アルゴリズムVerは、検証者により利用される。署名検証アルゴリズムVerは、電子署名σが文書Mに対する正当な電子署名であるか否かを検証するアルゴリズムである。署名検証アルゴリズムVerは、署名者の検証鍵pk、文書M、電子署名σを入力とし、0又は11bitを出力するアルゴリズムである。この署名検証アルゴリズムVerは、形式的に、下記の式5のように表現することができる。なお、検証者は、署名検証アルゴリズムVerが0を出力した場合公開鍵pkが文書Mと電子署名σを拒否する場合に電子署名σが不当であると判断し、1を出力した場合公開鍵pkが文書Mと電子署名σを受理する場合に電子署名σが正当であると判断する。以上、電子署名方式のアルゴリズムについて、その概要を説明した。[1-3:nパスの公開鍵認証方式]次に、図3を参照しながら、nパスの公開鍵認証方式について説明する。図3は、nパスの公開鍵認証方式について説明するための説明図である。上記の通り、公開鍵認証方式は、対話プロトコルの中で、証明者が公開鍵pkに対応する秘密鍵skを保有していることを検証者に証明する認証方式である。また、対話プロトコルは、健全性及び零知識性という2つの条件を満たす必要がある。そのため、対話プロトコルの中では、図3に示すように、証明者及び検証者の双方がそれぞれ処理を実行しながらn回の情報交換を行う。nパスの公開鍵認証方式の場合、証明者アルゴリズムPを用いて証明者により処理工程1が実行され、情報T1が検証者に送信される。次いで、検証者アルゴリズムVを用いて検証者により処理工程2が実行され、情報T2が証明者に送信される。さらに、k=3~nについて処理の実行及び情報Tkの送信が順次行われ、最後に処理工程n1が実行される。このように、情報がn回送受信される方式のことをnパスの公開鍵認証方式と呼ぶ。以上、nパスの公開鍵認証方式について説明した。<2:3パスの公開鍵認証方式に係るアルゴリズムの構成>以下、3パスの公開鍵認証方式に係るアルゴリズムについて説明する。なお、以下の説明において、3パスの公開鍵認証方式のことを3パス方式と呼ぶ場合がある。[2-1:具体的なアルゴリズムの構成例図4]まず、図4を参照しながら、3パス方式に係る具体的なアルゴリズムの構成例について紹介する。図4は、3パス方式に係る具体的なアルゴリズムの構成について説明するための説明図である。ここでは、公開鍵pkの一部として2次多項式の組f1x,...,fmxを利用する場合について考える。但し、2次多項式fixは、下記の式6のように表現されるものとする。また、ベクトルx1,...,xnをxと表記し、2次多項式の組f1x,...,fmxを多変数多項式Fxと表記することにする。また、2次多項式の組f1x,...,fmxは、下記の式7のように表現することができる。また、A1,...,Amは、n×n行列である。さらに、b1,...,bmはそれぞれn×1ベクトルである。この表現を用いると、多変数多項式Fは、下記の式8及び式9のように表現することができる。この表現が成り立つことは、下記の式10から容易に確認することができる。このようにFxyをxに依存する第1の部分と、yに依存する第2の部分と、x及びyの両方に依存する第3の部分とに分けたとき、第3の部分に対応する項Gx,yは、x及びyについて双線形になる。以下、項Gx,yを双線形項と呼ぶ場合がある。この性質を利用すると、効率的なアルゴリズムを構築することが可能になる。例えば、ベクトルt0∈Kn、e0∈Kmを用いて、多変数多項式Fxrのマスクに利用する多変数多項式F1xをF1x=Gx,t0e0と表現する。この場合、多変数多項式Fxr0とGxとの和は、下記の式11のように表現される。ここで、t1=r0t0、e1=Fr0e0とおけば、多変数多項式F2x=Fxr0F1xは、ベクトルt1∈Kn、e1∈Kmにより表現することができる。そのため、F1x=Gx,t0e0に設定すれば、Kn上のベクトル及びKm上のベクトルを用いてF1及びF2を表現できるようになり、通信に必要なデータサイズの少ない効率的なアルゴリズムを実現することが可能になる。なお、F2或いはF1からr0に関する情報が一切漏れることはない。例えば、e1及びt1或いはe0及びt0を与えられても、e0及びt0或いはe1及びt1を知らない限り、r0の情報を一切知ることはできない。従って、零知識性が担保される。以下、上記の論理に基づいて構築された3パス方式のアルゴリズムについて説明する。ここで説明する3パス方式のアルゴリズムは、以下のような鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本の多変数多項式f1x1,...,xn,...,fmx1,...,xn、及びベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1x1,...,xn,...,fmx1,...,xn,yを公開鍵pkに設定し、sを秘密鍵に設定する。証明者アルゴリズムP、検証者アルゴリズムV以下、図4を参照しながら、対話プロトコルの中で証明者アルゴリズムPが実行する処理及び検証者アルゴリズムVが実行する処理について説明する。この対話プロトコルの中で、証明者は、秘密鍵sの情報を検証者に一切漏らさずに、自身がy=Fsを満たすsを知っていることを検証者に示す。一方、検証者は、証明者がy=Fsを満たすsを知っているか否かを検証する。なお、公開鍵pkは、検証者に公開されているものとする。また、秘密鍵sは、証明者により秘密に管理されているものとする。以下、図4に示したフローチャートに沿って説明を進める。工程1:図4に示すように、まず、証明者アルゴリズムPは、ランダムにベクトルr0,t0∈Kn及びe0∈Kmを生成する。次いで、証明者アルゴリズムPは、r1←s-r0を計算する。この計算は、秘密鍵sをベクトルr0によりマスクする操作に相当する。さらに、証明者アルゴリズムPは、t1←r0-t0を計算する。次いで、証明者アルゴリズムPは、e1←Fr0-e0を計算する。工程1続き:次いで、証明者アルゴリズムPは、c0←Hr1,Gt0,r1e0を計算する。次いで、証明者アルゴリズムPは、c1←Ht0,e0を計算する。次いで、証明者アルゴリズムPは、c2←Ht1,e1を計算する。工程1で生成されたメッセージc0,c1,c2は、検証者アルゴリズムVに送られる。工程2:メッセージc0,c1,c2を受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す3つの数値{0,1,2}の中から1つの数値を選択し、選択した数値を要求Chに設定する。この要求Chは証明者アルゴリズムPに送られる。工程3:要求Chを受け取った証明者アルゴリズムPは、受け取った要求Chに応じて検証者アルゴリズムVに送る返答Rspを生成する。Ch=0の場合、証明者アルゴリズムPは、返答Rsp=r0,t1,e1を生成する。Ch=1の場合、証明者アルゴリズムPは、返答Rsp=r1,t0,e0を生成する。Ch=2の場合、証明者アルゴリズムPは、返答Rsp=r1,t1,e1を生成する。工程3で生成された返答Rspは、検証者アルゴリズムVに送られる。工程4:返答Rspを受け取った検証者アルゴリズムVは、受け取った返答Rspを利用して以下の検証処理を実行する。Ch=0の場合、検証者アルゴリズムVは、c1=Hr0-t1,Fr0-e1の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c2=Ht1,e1の等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。Ch=1の場合、検証者アルゴリズムVは、c0=Hr1,Gt0,r1e0の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c1=Ht0,e0の等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。Ch=2の場合、検証者アルゴリズムVは、c0=Hr1,y-Fr1-Gt1,r1-e1の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c2=Ht1,e1の等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、3パス方式に係る効率的なアルゴリズムの構成例について説明した。[2-2:並列化アルゴリズムの構成例図5]次に、図5を参照しながら、図4に示した3パス方式のアルゴリズムを並列化する方法について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。さて、上記の対話プロトコルを適用すれば、偽証が成功する確率を2/3以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を2/32以下に抑制することができる。さらに、この対話プロトコルをN回実行すると、偽証が成功する確率は2/3Nとなり、Nを十分に大きい数例えば、N=140にすれば、偽証が成功する確率は無視できる程度に小さくなる。対話プロトコルを複数回実行する方法としては、例えば、メッセージ、要求、返答のやり取りを逐次的に複数回繰り返す直列的な方法と、1回分のやり取りで複数回分のメッセージ、要求、返答のやり取りを行う並列的な方法とが考えられる。さらに、直列的な方法と並列的な方法とを組み合わせたハイブリッド型の方法も考えられる。ここでは、図5を参照しながら、3パス方式に係る上記の対話プロトコルを並列的に実行するアルゴリズム以下、並列化アルゴリズムについて説明する。工程1:図5に示すように、まず、証明者アルゴリズムPは、i=1~Nについて以下の処理1~処理6を実行する。処理1:証明者アルゴリズムPは、ランダムにベクトルr0i,t0i∈Kn及びe0i∈Kmを生成する。処理2:証明者アルゴリズムPは、r1i←s-r0iを計算する。この計算は、秘密鍵sをベクトルr0iによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、t1i←r0it0iを計算する。処理3:証明者アルゴリズムPは、e1i←Fr0i-e0iを計算する。処理4:証明者アルゴリズムPは、c0i←Hr1i,Gr1i,t0ie0iを計算する。処理5:証明者アルゴリズムPは、c1i←Ht0i,e0iを計算する。処理6:証明者アルゴリズムPは、c2i←Ht1i,e1iを計算する。工程1続きi=1~Nについて上記の処理1~処理6を実行した後、証明者アルゴリズムPは、Cmt←Hc01,c11,c21,...,c0N,c1N,c2Nを計算する。工程1で生成されたハッシュ値Cmtは、検証者アルゴリズムVに送られる。このように、メッセージc01,c11,c21,...,c0N,c1N,c2Nをハッシュ値に変換してから検証者アルゴリズムVに送ることで、通信量を削減することが可能になる。工程2:ハッシュ値Cmtを受け取った検証者アルゴリズムVは、i=1~Nのそれぞれについて、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、i=1~Nのそれぞれについて、検証パターンの種類を表す3つの数値{0,1,2}の中から1つの数値を選択し、選択した数値を要求Chiに設定する。要求Ch1,...,ChNは、証明者アルゴリズムPに送られる。工程3:要求Ch1,...,ChNを受け取った証明者アルゴリズムPは、受け取った要求Ch1,...,ChNのそれぞれ応じて検証者アルゴリズムVに送る返答Rsp1,...,RspNを生成する。Chi=0の場合、証明者アルゴリズムPは、Rspi=r0i,t1i,e1i,c0iを生成する。Chi=1の場合、証明者アルゴリズムPは、Rspi=r1i,t0i,e0i,c2iを生成する。Chi=2の場合、証明者アルゴリズムPは、Rspi=r1i,t1i,e1i,c1iを生成する。工程3で生成された返答Rsp1,...,RspNは、検証者アルゴリズムVに送られる。工程4:返答Rsp1,...,RspNを受け取った検証者アルゴリズムVは、受け取った返答Rsp1,...,RspNを利用して以下の処理1~処理3をi=1~Nについて実行する。但し、検証者アルゴリズムVは、Chi=0の場合に処理1を実行し、Chi=1の場合に処理2を実行し、Chi=2の場合に処理3を実行する。処理1:Chi=0の場合、検証者アルゴリズムVは、Rspiからr0i,t1i,e1i,c0iを取り出す。次いで、検証者アルゴリズムVは、c1i=Hr0i-t1i,Fr0i-e1iを計算する。さらに、検証者アルゴリズムVは、c2i=Ht1i,e1iを計算する。そして、検証者アルゴリズムVは、c0i,c1i,c2iを保持する。処理2:Chi=1の場合、検証者アルゴリズムVは、Rspiからr1i,t0i,e0i,c2iを取り出す。次いで、検証者アルゴリズムVは、c0i=Hr1i,Gt0i,r1ie0iを計算する。さらに、検証者アルゴリズムVは、c1i=Ht0i,e0iを計算する。そして、検証者アルゴリズムVは、c0i,c1i,c2iを保持する。処理3:Chi=2の場合、検証者アルゴリズムVは、Rspiからr1i,t1i,e1i,c1iを取り出す。次いで、検証者アルゴリズムVは、c0i=Hr1i,y-Fr1i-Gt1i,r1i-e1iを計算する。さらに、検証者アルゴリズムVは、c2i=Ht1i,e1iを計算する。そして、検証者アルゴリズムVは、c0i,c1i,c2iを保持する。処理1~処理3をi=1~Nについて実行した後、検証者アルゴリズムVは、Cmt=Hc01,c11,c21,...,c0N,c1N,c2Nの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗した場合に認証失敗を示す値0を出力する。以上、3パス方式に係る効率的な並列化アルゴリズムの構成例について説明した。<3:5パスの公開鍵認証方式に係るアルゴリズムの構成>次に、5パスの公開鍵認証方式に係るアルゴリズムについて説明する。なお、以下の説明において、5パスの公開鍵認証方式のことを5パス方式と呼ぶ場合がある。3パス方式の場合には対話プロトコル1回当たりの偽証確率が2/3であったが、5パス方式の場合には対話プロトコル1回当たりの偽証確率が1/21/qとなる。但し、qは、利用する環の位数である。従って、環の位数が十分に大きい場合、5パス方式の方が1回当たりの偽証確率を低減することが可能になり、少ない対話プロトコルの実行回数で、偽証確率を十分に小さくすることができる。例えば、偽証確率を1/2n以下にしたい場合、3パス方式においては、n/log3-1=1.701n回以上、対話プロトコルを実行する必要がある。一方、偽証確率を1/2n以下にしたい場合、5パス方式においては、n/1-log11/q回以上、対話プロトコルを実行する必要がある。従って、q=24にすれば、同じセキュリティレベルを実現するのに必要な通信量は、3パス方式に比べ、5パス方式の方が少なくなるのである。[3-1:具体的なアルゴリズムの構成例図6]まず、図6を参照しながら、5パス方式に係る具体的なアルゴリズムの構成例について紹介する。図6は、5パス方式に係る具体的なアルゴリズムの構成について説明するための説明図である。ここでは、公開鍵pkの一部として2次多項式の組f1x,...,fmxを利用する場合について考える。但し、2次多項式fixは、上記の式6のように表現されるものとする。また、ベクトルx1,...,xnをxと表記し、2次多項式の組f1x,...,fmxを多変数多項式Fxと表記することにする。3パス方式に係るアルゴリズムと同様、2つのベクトルt0∈Kn、e0∈Kmを用いて、多変数多項式Fxr0をマスクするために用いた多変数多項式F1xをF1x=Gx、t0e0のように表現する。この表現を用いると、多変数多項式Fxr0について、下記の式12で表現される関係が得られる。そのため、t1=ChAr0t0、e1=ChAFr0e0とすれば、マスク後の多変数多項式F2x=ChAFxr0F1xも、2つのベクトルt1∈Kn、e1∈Kmにより表現することができる。これらの理由から、F1x=Gx,t0e0と設定すれば、Kn上のベクトル及びKm上のベクトルを用いてF1及びF2を表現できるようになり、通信に必要なデータサイズが少ない効率的なアルゴリズムを実現することが可能になる。なお、F2或いはF1からr0に関する情報が一切漏れることはない。例えば、e1及びt1或いはe0及びt0を与えられても、e0及びt0或いはe1及びt1を知らない限り、r0の情報を一切知ることはできない。従って、零知識性は担保される。以下、上記の論理に基づいて構築された5パス方式のアルゴリズムについて説明する。ここで説明する5パス方式のアルゴリズムは、以下のような鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義される多変数多項式f1x1,...,xn,...,fmx1,...,xn、及びベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、ベクトルx1,...,xnをxと表記し、多変数多項式の組f1x,...,fmxをFxと表記する。証明者アルゴリズムP、検証者アルゴリズムV以下、図6を参照しながら、対話プロトコルの中で証明者アルゴリズムP及び検証者アルゴリズムVにより実行される処理について説明する。この対話プロトコルの中で、証明者は、秘密鍵sの情報を検証者に一切漏らさずに、自身がy=Fsを満たすsを知っていることを検証者に示す。一方、検証者は、証明者がy=Fsを満たすsを知っているか否かを検証する。なお、公開鍵pkは、検証者に公開されているものとする。また、秘密鍵sは、証明者により秘密に管理されているものとする。以下、図6に示したフローチャートに沿って説明を進める。工程1:図6に示すように、まず、証明者アルゴリズムPは、ランダムにベクトルr0∈Kn、t0∈Kn、e0∈Kmを生成する。次いで、証明者アルゴリズムPは、r1←s-r0を計算する。この計算は、秘密鍵sをベクトルr0によりマスクする操作に相当する。次いで、証明者アルゴリズムPは、ベクトルr0,t0,e0のハッシュ値c0を生成する。つまり、証明者アルゴリズムPは、c0←Hr0,t0,e0を計算する。次いで、証明者アルゴリズムPは、Gt0,r1e0及びr1のハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c0←Hr1,Gt0,r1e0を計算する。工程1で生成されたメッセージc0,c1は、検証者アルゴリズムVに送られる。工程2:メッセージc0,c1を受け取った検証者アルゴリズムVは、q通り存在する環Kの元からランダムに1つの数ChAを選択し、選択した数ChAを証明者アルゴリズムPに送る。工程3:数ChAを受け取った証明者アルゴリズムPは、t1←ChAr0-t0を計算する。さらに、証明者アルゴリズムPは、e1←ChAFr0-e0を計算する。そして、証明者アルゴリズムPは、t1及びe1を検証者アルゴリズムVに送る。工程4:t1及びe1を受け取った検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求ChBに設定する。この要求ChBは証明者アルゴリズムPに送られる。工程5:要求ChBを受け取った証明者アルゴリズムPは、受け取った要求ChBに応じて検証者アルゴリズムVに送り返す返答Rspを生成する。ChB=0の場合、証明者アルゴリズムPは、返答Rsp=r0を生成する。ChB=1の場合、証明者アルゴリズムPは、返答Rsp=r1を生成する。工程5で生成された返答Rspは、検証者アルゴリズムVに送られる。工程6:返答Rspを受け取った検証者アルゴリズムVは、受け取った返答Rspを利用して以下の検証処理を実行する。ChB=0の場合、検証者アルゴリズムVは、r0←Rspを実行する。そして、検証者アルゴリズムVは、c0=Hr0,ChAr0-t1,ChAFr0-e1の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。ChB=1の場合、検証者アルゴリズムVは、r1←Rspを実行する。そして、検証者アルゴリズムVは、c1=H1r1,ChAy-Fr1-Gt1,r1-e1の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、5パス方式に係る効率的なアルゴリズムの構成例について説明した。[3-2:並列化アルゴリズムの構成例図7]次に、図7を参照しながら、図6に示した5パス方式のアルゴリズムを並列化する方法について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。先に述べた通り、5パス方式に係る対話プロトコルを適用すれば、偽証が成功する確率を1/21/q以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を1/21/q2以下に抑制することができる。さらに、この対話プロトコルをN回実行すると、偽証が成功する確率は1/21/qNとなり、Nを十分に大きい数例えば、N=80にすれば、偽証が成功する確率は無視できる程度に小さくなる。対話プロトコルを複数回実行する方法としては、例えば、メッセージ、要求、返答のやり取りを逐次的に複数回繰り返す直列的な方法と、1回分のやり取りで複数回分のメッセージ、要求、返答のやり取りを行う並列的な方法とが考えられる。さらに、直列的な方法と並列的な方法とを組み合わせたハイブリッド型の方法も考えられる。ここでは、5パス方式に係る上記の対話プロトコルを並列的に実行するアルゴリズム以下、並列化アルゴリズムについて説明する。工程1:図7に示すように、まず、証明者アルゴリズムPは、i=1~Nについて処理1~処理4を実行する。処理1:証明者アルゴリズムPは、ランダムにベクトルr0i,t0i∈Kn及びe0i∈Kmを生成する。処理2:証明者アルゴリズムPは、r1i←s-r0iを計算する。この計算は、秘密鍵sをベクトルr0iによりマスクする操作に相当する。処理3:証明者アルゴリズムPは、c0i←Hr0i,t0i,e0iを計算する。処理4:証明者アルゴリズムPは、c1i←Hr1i,Gt0i,r1ie0iを計算する。i=1~Nについて処理1~処理4を実行した後、証明者アルゴリズムPは、ハッシュ値Cmt←Hc01,c11,...,c0N,c1Nを実行する。そして、工程1で生成されたハッシュ値Cmtは、検証者アルゴリズムVに送られる。工程2:ハッシュ値Cmtを受け取った検証者アルゴリズムVは、i=1~Nのそれぞれについて、q通り存在する環Kの元からランダムに1つの数ChAiを選択し、選択した数ChAii=1~Nを証明者アルゴリズムPに送る。工程3:数ChAii=1~Nを受け取った証明者アルゴリズムPは、i=1~Nのそれぞれについて、t1i←ChAir0i-t0iを計算する。さらに、証明者アルゴリズムPは、i=1~Nのそれぞれについて、e1i←ChAiFr0i-e0iを計算する。そして、証明者アルゴリズムPは、t11,...,t1N及びe11,...,e1Nを検証者アルゴリズムVに送る。工程4:t11,...,t1N及びe11,...,e1Nを受け取った検証者アルゴリズムVは、i=1~Nのそれぞれについて、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求ChBiに設定する。要求ChBii=1~Nは証明者アルゴリズムPに送られる。工程5:要求ChBii=1~Nを受け取った証明者アルゴリズムPは、i=1~Nについて、受け取った要求ChBiに応じて検証者アルゴリズムVに送り返す返答Rspiを生成する。ChBi=0の場合、証明者アルゴリズムPは、返答Rspi=r0i,c1iを生成する。ChBi=1の場合、証明者アルゴリズムPは、返答Rspi=r1i,c0iを生成する。工程5で生成された返答Rspii=1~Nは、検証者アルゴリズムVに送られる。工程6:返答Rspii=1~Nを受け取った検証者アルゴリズムVは、受け取った返答Rspii=1~Nを利用して以下の処理1及び処理2を実行する。処理1:ChBi=0の場合、検証者アルゴリズムVは、r0i,c1i←Rspiを実行する。そして、検証者アルゴリズムVは、c0i=Hr0i,ChAir0i-t1i,ChAiFr0i-e1iを計算する。そして、検証者アルゴリズムVは、c0i,c1iを保持する。処理2:ChBi=1の場合、検証者アルゴリズムVは、r1i,c0i←Rspiを実行する。そして、検証者アルゴリズムVは、c1i=Hr1i,ChAiy-Fr1i-Gt1i,r1i-e1iを計算する。そして、検証者アルゴリズムVは、c0i,c1iを保持する。i=1~Nについて処理1及び処理2を実行した後、検証者アルゴリズムVは、Cmt=Hc01,c11,...,c0N,c1Nの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、5パス方式に係る効率的な並列化アルゴリズムの構成例について説明した。<4:電子署名方式への変形>次に、上記の公開鍵認証方式を電子署名方式へと変形する方法を紹介する。公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させると、証明者のみが検証者を納得させられるという点において、電子署名方式のモデルと近似していることが容易に理解されよう。こうした考えに基づき、上述した公開鍵認証方式を電子署名方式へと変形する方法について説明する。[4-1:3パスの公開鍵認証方式から電子署名方式への変形図8]まず、3パスの公開鍵認証方式から電子署名方式への変形について説明する。図8に示すように、3パス方式に係る効率的なアルゴリズム例えば、図5を参照は、3回の対話及び4つの工程1~工程4で表現される。工程1は、i=1~Nについて、ai=r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1i,c2iを生成する処理1と、Cmt←Hc01,c11,c21,...,c0N,c1N,c2Nを計算する処理2とで構成される。工程1で証明者アルゴリズムPにより生成されたCmtは、検証者アルゴリズムVへと送られる。工程2は、Ch1,...,ChNを選択する処理で構成される。工程2で検証者アルゴリズムVにより選択されたCh1,...,ChNは、証明者アルゴリズムPへと送られる。工程3は、Ch1,...,ChN及びa1,...,aNを用いてRsp1,...,RspNを生成する処理で構成される。この処理をRspi←SelectChi,aiと表現する。工程3で証明者アルゴリズムPにより生成されたRsp1,...,RspNは、検証者アルゴリズムVへと送られる。工程4は、Ch1,...,ChN及びRsp1,...,RspNを用いてc01,c11,c21,...,c0N,c1N,c2Nを再生する処理1と、再生したc01,c11,c21,...,c0N,c1N,c2Nを用いてCmt=Hc01,c11,c21,...,c0N,c1N,c2Nを検証する処理2とで構成される。上記の工程1~工程4で表現される公開鍵認証方式のアルゴリズムは、図8に示すような署名生成アルゴリズムSig及び署名検証アルゴリズムVerに変形される。署名生成アルゴリズムSigまず、署名生成アルゴリズムSigの構成について述べる。署名生成アルゴリズムSigは、以下の処理1~処理5で構成される。処理1:署名生成アルゴリズムSigは、ai=r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1i,c2iを生成する。処理2:署名生成アルゴリズムSigは、Cmt←Hc01,c11,c21,...,c0N,c1N,c2Nを計算する。処理3:署名生成アルゴリズムSigは、Ch1,...,ChN←HM,Cmtを計算する。このMは、署名を付与する文書である。処理4:署名生成アルゴリズムSigは、Rspi←SelectChi,aiを計算する。処理5:署名生成アルゴリズムSigは、Cmt,Rsp1,...,RspNを署名に設定する。署名検証アルゴリズムVer次に、署名検証アルゴリズムVerの構成について述べる。署名検証アルゴリズムVerは、以下の処理1~処理3で構成される。処理1:署名検証アルゴリズムVerは、Ch1,...,ChN←HM,Cmtを計算する。処理2:署名検証アルゴリズムVerは、Ch1,...,ChN及びRsp1,...,RspNを用いてc01,c11,c21,...,c0N,c1N,c2Nを生成する。処理3:署名検証アルゴリズムVerは、再生したc01,c11,c21,...,c0N,c1N,c2Nを用いてCmt=Hc01,c11,c21,...,c0N,c1N,c2Nを検証する。以上説明したように、公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させることで、公開鍵認証方式のアルゴリズムを電子署名方式のアルゴリズムへと変形することが可能になる。[4-2:5パスの公開鍵認証方式から電子署名方式への変形図9]次に、5パスの公開鍵認証方式から電子署名方式への変形について説明する。図9に示すように、5パス方式に係る効率的なアルゴリズム例えば、図7を参照は、5回の対話及び6つの工程1~工程6で表現される。工程1は、i=1~Nについて、ai=r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1iを生成する処理1と、Cmt←Hc01,c11,...,c0N,c1Nを計算する処理2とで構成される。工程1で証明者アルゴリズムPにより生成されたCmtは、検証者アルゴリズムVへと送られる。工程2は、ChA1,...,ChANを選択する処理で構成される。工程2で検証者アルゴリズムVにより選択されたChA1,...,ChANは、証明者アルゴリズムPへと送られる。工程3は、i=1~Nについて、bi=t1i,e1iを生成する処理で構成される。工程3で証明者アルゴリズムPにより生成されたb1,...,bNは、検証者アルゴリズムVへと送られる。工程4は、ChB1,...,ChBNを選択する処理で構成される。工程4で検証者アルゴリズムVにより選択されたChB1,...,ChBNは、証明者アルゴリズムPへと送られる。工程5は、ChB1,...,ChBN,a1,...,aN,b1,...,bNを用いてRsp1,...,RspNを生成する処理で構成される。この処理をRspi←SelectChBi,ai,biと表現する。工程5で証明者アルゴリズムPにより生成されたRsp1,...,RspNは、検証者アルゴリズムVへと送られる。工程6は、ChA1,...,ChAN,ChB1,...,ChBN,Rsp1,...,RspNを用いてc01,c11,...,c0N,c1Nを再生する処理1と、再生したc01,c11,...,c0N,c1Nを用いてCmt=Hc01,c11,...,c0N,c1Nを検証する処理2とで構成される。上記の工程1~工程6で表現される公開鍵認証方式のアルゴリズムは、図9に示すような署名生成アルゴリズムSig及び署名検証アルゴリズムVerに変形される。署名生成アルゴリズムSigまず、署名生成アルゴリズムSigの構成について述べる。署名生成アルゴリズムSigは、以下の処理1~処理7で構成される。処理1:署名生成アルゴリズムSigは、ai=r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1iを生成する。処理2:署名生成アルゴリズムSigは、Cmt←Hc01,c11,...,c0N,c1Nを計算する。処理3:署名生成アルゴリズムSigは、ChA1,...,ChAN←HM,Cmtを計算する。このMは、署名を付与する文書である。処理4:署名生成アルゴリズムSigは、i=1~Nについて、bi=t1i,e1iを生成する。処理5:署名生成アルゴリズムSigは、ChB1,...,ChBN←HM,Cmt,ChA1,...,ChAN,b1,...,bNを計算する。なお、ChB1,...,ChBN←HChA1,...,ChAN,b1,...,bNと変形してもよい。処理6:署名生成アルゴリズムSigは、Rspi←SelectChBi,ai,biを計算する。処理7:署名生成アルゴリズムSigは、Cmt,b1,...,bN,Rsp1,...,RspNを電子署名に設定する。署名検証アルゴリズムVer次に、署名検証アルゴリズムVerの構成について述べる。署名検証アルゴリズムVerは、以下の処理1~処理4で構成される。処理1:署名検証アルゴリズムVerは、ChA1,...,ChAN←HM,Cmtを計算する。処理2:署名検証アルゴリズムVerは、ChB1,...,ChBN←HM,Cmt,ChA1,...,ChAN,b1,...,bNを計算する。なお、署名検証アルゴリズムVerが実行する処理5において、ChB1,...,ChBN←HChA1,...,ChAN,b1,...,bNと変形した場合、署名検証アルゴリズムVerは、ChB1,...,ChBN←HChA1,...,ChAN,b1,...,bNを計算する。処理3:署名検証アルゴリズムVerは、ChA1,...,ChAN,ChB1,...,ChBN,Rsp1,...,RspNを用いてc01,c11,...,c0N,c1Nを生成する。処理4:署名検証アルゴリズムVerは、再生したc01,c11,...,c0N,c1Nを用いてCmt=Hc01,c11,...,c0N,c1Nを検証する。以上説明したように、公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させることで、公開鍵認証方式のアルゴリズムを電子署名方式のアルゴリズムへと変形することが可能になる。<5:双線形項Gの効率的な計算方法>ところで、上記の公開鍵認証方式及び電子署名方式に係るアルゴリズムには、下記の式13で定義される双線形項Gの演算が含まれる。例えば、3パス方式のアルゴリズム図4及び図5を参照においては、工程1及び工程4の中に双線形項Gの演算が含まれる。また、5パス方式のアルゴリズム図6及び図7を参照においては、工程1及び工程6の中に双線形項Gの演算が含まれる。さらに、これらの公開鍵認証方式のアルゴリズムを変形して得られる電子署名方式のアルゴリズムにも、同様に双線形項Gの演算が含まれる。上記の式13から分かるように、双線形項Gの値を得るには、多変数多項式Fの演算を3回実行することが必要になる。また、多変数多項式Fはm本の2次多項式fll=1,...,mで構成されているため、多変数多項式Fの値を得るには、2次多項式flを実行するのに要する演算量のm倍の演算量以下、演算量Zが必要になる。つまり、双線形項Gの値を得るのに要する演算量は3×Z以上となる。ここでは、双線形項Gの値を得るのに要する演算量を3×Zよりも少なくする方法について説明する。[5-1:原理説明]2次多項式flxyは、下記の式14に示すように展開することができる。従って、双線形項G=g1,...,gmの要素glx,yは、下記の式15のようになる。下記の式15から分かるように、要素glx,yは、2つの2次多項式で構成されている。そのため、下記の式15に示した展開式に基づいて双線形項Gを演算することにより、双線形項Gの演算量を2×Z程度に抑制することが可能になる。また、上記の式6の右辺第2項xjに関する1次の項を省略した形下記の式16を参照で2次多項式flを定義すると、fl及びglは、下記の式17の表現を用いて、下記の式18及び式19のように表現することができる。この表現を用いると、関数wlx,yを計算する演算モジュールを用意し、その演算モジュールを繰り返し利用して双線形項Gや多変数多項式Fを計算することが可能になる。例えば、この演算モジュールをハードウェア又はソフトウェアで実装し、実装した演算モジュールを利用してアルゴリズムを実行することが可能になる。以上、双線形項Gの効率的な計算方法の原理を説明した。なお、ここでは2次多項式flを上記の式16のように定義する方法について説明したが、本実施形態に係る技術の適用範囲はこれに限定されず、上記の式6に示した定義をそのまま用いてもよい。この場合、上記の式19にxjに関する1次の項が現れる。但し、以下の説明においては、2次多項式flを上記の式16のように定義することを前提に説明を進める。[5-2:適用例13パス方式への適用]まず、3パス方式のアルゴリズムに対する具体的な適用方法について説明する。単純な適用例図4を参照すると、工程1において、メッセージc0を算出する際に、双線形項Gt0,r1の演算が登場する。そこで、証明者アルゴリズムPは、glt0,r1=wlt0,r1wlr1,t0を用いて双線形項Gt0,r1を計算する。また、工程4において、Ch=1の場合に双線形項Gt0,r1の演算が登場し、Ch=2の場合に双線形項Gt1,r1の演算が登場する。そこで、検証者アルゴリズムVは、Ch=1の場合にglt0,r1=wlt0,r1wlr1,t0を用いて双線形項Gt0,r1を計算し、Ch=2の場合にglt1,r1=wlt1,r1wlr1,t1を用いて双線形項Gt1,r1を計算する。この方法を適用すると、双線形項Gの計算に要する演算量は2×Z程度に抑制される。効率的な適用例上記の方法を用いることにより、双線形項Gの演算を効率的に実行することが可能になる。但し、工程4において、Ch=2の場合に計算すべき項y-Fr1-Gt1,r1-e1に注目すると、より効率的に演算を実行する方法に気づくであろう。上記の式13の定義に従うと、Fr1Gt1,r1=Ft1r1-Ft1となる。従って、左辺を単純に計算すると、1×Z3×Z=4×Z程度の演算量となるが、右辺を参照すると分かるように、この変形により2×Z程度の演算量に削減される。なお、演算モジュールwlx,yの具体的な適用方法については、下記の式20に示すように何通りかの方法が考えられる。いずれの方法を用いても、Fr1Gt1,r1の計算に要する演算量は2×Z程度となる。以上、3パス方式のアルゴリズムに対する具体的な適用方法について説明した。なお、ここでは、図4に示したアルゴリズムを参考に説明を行ったが、図5に示した並列化アルゴリズム又はこれらのアルゴリズムを変形したアルゴリズムに対しても同様に適用することが可能である。[5-3:適用例25パス方式への適用]次に、5パス方式のアルゴリズムに対する具体的な適用方法について説明する。図6を参照すると、工程1において、メッセージc1を算出する際に、双線形項Gt0,r1の演算が登場する。そこで、証明者アルゴリズムPは、glt0,r1=wlt0,r1wlr1,t0を用いて双線形項Gt0,r1を計算する。また、工程6において、ChB=1の場合に双線形項Gt1,r1の演算が登場する。そこで、検証者アルゴリズムVは、ChB=1の場合にglt1,r1=wlt1,r1wlr1,t1を用いて双線形項Gt1,r1を計算する。この方法を適用すると、双線形項Gの計算に要する演算量は2×Z程度に抑制される。以上、5パス方式のアルゴリズムに対する具体的な適用方法について説明した。なお、ここでは、図6に示したアルゴリズムを参考に説明を行ったが、図7に示した並列化アルゴリズム又はこれらのアルゴリズムを変形したアルゴリズムに対しても同様に適用することが可能である。[5-4:適用例3電子署名方式への適用]次に、電子署名方式のアルゴリズムに対する具体的な適用方法について説明する。3パス方式に基づく電子署名方式への適用図8に示した電子署名方式のアルゴリズムは、図5に示した3パス方式の並列化アルゴリズムに基づくアルゴリズムである。従って、署名生成アルゴリズムSigがメッセージc0iを算出する際に、双線形項Gt0i,r1iの演算が登場する。そこで、署名生成アルゴリズムSigは、glt0i,r1i=wlt0i,r1iwlr1i,t0iを用いて双線形項Gt0i,r1iを計算する。また、署名検証アルゴリズムVerがメッセージc0iを算出する際に、双線形項Gt0i,r1iや双線形項Gt1i,r1iの演算が登場する。そこで、署名検証アルゴリズムVerは、glt0i,r1i=wlt0i,r1iwlr1i,t0iを用いて双線形項Gt0i,r1iを計算し、glt1i,r1i=wlt1i,r1iwlr1i,t1iを用いて双線形項Gt1i,r1iを計算する。この方法を適用すると、双線形項Gの計算に要する演算量は2×Z程度に抑制される。また、署名検証アルゴリズムVerがメッセージc0iを算出する際に実行するFr1iGt1i,r1iの演算に注目し、上記の式20に基づいて演算を実行することにより、演算量をさらに削減することが可能になる。5パス方式に基づく電子署名方式への適用図9に示した電子署名方式のアルゴリズムは、図7に示した5パス方式の並列化アルゴリズムに基づくアルゴリズムである。従って、署名生成アルゴリズムSigがメッセージc1iを算出する際に、双線形項Gt0i,r1iの演算が登場する。そこで、署名生成アルゴリズムSigは、glt0i,r1i=wlt0i,r1iwlr1i,t0iを用いて双線形項Gt0i,r1iを計算する。また、署名検証アルゴリズムVerがメッセージc1iを再生する際に、双線形項Gt1i,r1iの演算が登場する。そこで、署名検証アルゴリズムVerは、glt1,r1=wlt1,r1wlr1,t1を用いて双線形項Gt1,r1を計算する。この方法を適用すると、双線形項Gの計算に要する演算量は2×Z程度に抑制される。以上、電子署名方式のアルゴリズムに対する具体的な適用方法について説明した。なお、ここでは、図8及び図9に示したアルゴリズムを参考に説明を行ったが、これらのアルゴリズムを変形したアルゴリズムに対しても同様に適用することが可能である。以上、双線形項Gの効率的な計算方法について説明した。<6:ハードウェア構成例>上記の各アルゴリズムは、例えば、図10に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図10に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、PHS、PDA等の携帯情報端末、ゲーム機、接触式又は非接触式のICチップ、接触式又は非接触式のICカード、又は種々の情報家電がこれに含まれる。但し、上記のPHSは、PersonalHandy-phoneSystemの略である。また、上記のPDAは、PersonalDigitalAssistantの略である。図10に示すように、このハードウェアは、主に、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の略である。<7:まとめ>最後に、本技術の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、PC、携帯電話、ゲーム機、情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置に対して適用することができる。なお、以下で述べる情報処理装置の機能は、1台の情報処理装置を利用して実現することも可能であるし、複数台の情報処理装置を利用して実現することも可能である。また、以下で述べる情報処理装置が処理を実行する際に用いるデータ記憶手段及び演算処理手段は、当該情報処理装置に設けられたものであってもよいし、ネットワークを介して接続された機器に設けられたものであってもよい。上記の情報処理装置の機能構成は以下のように表現される。例えば、下記1に記載の情報処理装置は、多次多変数連立方程式の求解困難性に安全性の根拠を置く効率的な公開鍵認証方式又は電子署名方式のアルゴリズムを実行する機能を有する。1環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記2次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、前記メッセージを生成する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、情報処理装置。2前記メッセージ生成部は、N回分N≧2のメッセージを生成し、前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、上記1に記載の情報処理装置。3環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記2次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記2次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証部は、前記検証に用いるメッセージを再生する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、情報処理装置。4前記メッセージ取得部は、N回分N≧2の前記メッセージを1回の対話で取得し、前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、上記3に記載の情報処理装置。5環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記2次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、前記検証者に前記第3の情報を提供する中間情報提供部と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、前記メッセージを生成する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、情報処理装置。6前記メッセージ生成部は、N回分N≧2のメッセージを生成し、前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、前記中間情報生成部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した前記第1の情報及び前記メッセージを生成する際に得られるN回分の前記第2の情報を用いてN回分の前記第3の情報を生成し、前記中間情報提供部は、N回分の前記第3の情報を1回の対話で検証者に提供し、前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、上記5に記載の情報処理装置。7環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記2次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供部と、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得部と、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記第1の情報、前記第3の情報、前記2次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証部は、前記検証に用いるメッセージを再生する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、情報処理装置。8前記メッセージ取得部は、N回分N≧2の前記メッセージを1回の対話で取得し、前記情報提供部は、N回分の前記メッセージのそれぞれについて前記第1の情報をランダムに選択し、選択したN回分の前記第1の情報を1回の対話で前記証明者に提供し、前記中間情報取得部は、N回分の前記第1の情報及びN回分の前記メッセージを生成する際に得られるN回分の前記第2の情報を用いて前記証明者が生成したN回分の前記第3の情報を取得し、前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、上記7に記載の情報処理装置。9環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成する署名生成部と、前記2次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供する署名提供部と、を備え、前記署名生成部は、前記電子署名を生成する過程で実行する、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、署名生成装置。10環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=f1s,...,fmsを保持する情報保持部と、文書Mについて、前記2次多変数多項式の組F及び署名鍵s∈Knを用いて生成された電子署名に基づいて前記文書Mの正当性を検証する署名検証部と、を備え、前記署名検証部は、前記電子署名を検証する過程で実行する、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算を式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行する、署名検証装置。11環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記2次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記生成するステップでは、前記メッセージを生成する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、情報処理方法。12環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報処理装置が、前記2次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記2次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証するステップでは、前記検証に用いるメッセージを再生する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、情報処理方法。13環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記2次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、前記検証者に前記第3の情報を提供するステップと、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージを生成するステップでは、前記メッセージを生成する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、情報処理方法。14環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報処理装置が、前記2次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供するステップと、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得するステップと、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記第1の情報、前記第3の情報、前記2次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証するステップでは、前記検証に用いるメッセージを再生する際、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、情報処理方法。15環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成するステップと、前記2次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供するステップと、を含み、前記生成するステップでは、前記電子署名を生成する過程で実行される、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、署名生成方法。16環K上で定義され、2次形式で表現される2次多変数多項式の組F=f1,...,fm及びベクトルy=f1s,...,fmsを保持する情報処理装置が、文書Mについて、前記2次多変数多項式の組F及び署名鍵s∈Knを用いて生成された電子署名に基づいて前記文書Mの正当性を検証するステップを含み、前記検証するステップでは、前記電子署名を検証する過程で実行される、Gx1,x2=Fx1x2-Fx1-Fx2で定義される関数G=g1,...,gmの計算が式glx1,x2=x1TAlx2x2TAlx1l=1~m;Alは、n×nの係数行列に基づいて実行される、署名検証方法。17上記の1~8のいずれか1項に記載の情報処理装置が備える各部の機能をコンピュータに実現させるためのプログラム。18上記の9に記載の署名生成装置が備える各部の機能をコンピュータに実現させるためのプログラム。19上記の10に記載の署名検証装置が備える各部の機能をコンピュータに実現させるためのプログラム。20上記の17~19のいずれか1項に記載のプログラムが記録された、コンピュータにより読み取り可能な記録媒体。備考上記の証明者アルゴリズムPは、メッセージ生成部、メッセージ提供部、回答提供部、中間情報生成部、中間情報提供部の一例である。また、上記の検証者アルゴリズムVは、情報保持部、メッセージ取得部、パターン情報提供部、回答取得部、検証部、中間情報取得部の一例である。また、上記の署名生成アルゴリズムSigは、署名生成部、署名提供部の一例である。また、上記の署名検証アルゴリズムVerは、情報保持部、署名検証部の一例である。以上、添付図面を参照しながら本技術の好適な実施形態について説明したが、本技術は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本技術の技術的範囲に属するものと了解される。上記の説明において、ハッシュ関数Hを用いるアルゴリズムを紹介したが、ハッシュ関数Hの代わりにコミットメント関数COMを用いてもよい。コミットメント関数COMは、文字列S及び乱数ρを引数にとる関数である。コミットメント関数の例としては、ShaiHaleviとSilvioMicaliによって国際会議CRYPTO1996で発表された方式などがある。"