"シードから乱数の組を発生させる乱数生成部と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、情報処理装置。前記回答提供部は、前記記憶装置に格納されたシードを利用し、前記回答情報として用いる前記乱数又は前記中間変数を再生成する、請求項1に記載の情報処理装置。前記メッセージ生成部は、N回分N≧2のメッセージを生成し、前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、請求項1に記載の情報処理装置。前記メッセージ生成部は、前記N回分のメッセージから1つのハッシュ値を生成し、前記メッセージ提供部は、前記N回分のメッセージに代えて前記ハッシュ値を前記検証者に提供する、請求項3に記載の情報処理装置。前記メッセージ生成部は、生成した前記メッセージを記憶装置に格納し、前記記憶装置に格納したメッセージの合計サイズがハッシュ関数のブロック単位より大きい場合に、当該記憶装置に格納したメッセージを利用して、当該ハッシュ関数が前記ハッシュ値の計算途中で算出する中間値を算出し、前記記憶装置に格納したメッセージを消去する処理を逐次実行して前記ハッシュ値を算出する、請求項4に記載の情報処理装置。シードから乱数の組を発生させる乱数生成部と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、前記検証者に前記第3の情報を提供する中間情報提供部と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、情報処理装置。前記中間情報生成部は、前記記憶装置に格納されたシードを利用して、前記第3の情報を生成する際に用いる前記乱数又は前記中間変数を再生成する、請求項6に記載の情報処理装置。前記中間情報生成部は、前記第3の情報の生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、請求項7に記載の情報処理装置。前記回答提供部は、前記記憶装置に格納されたシードを利用し、前記回答情報として用いる前記乱数又は前記中間変数を再生成する、請求項6に記載の情報処理装置。前記メッセージ生成部は、N回分N≧2のメッセージを生成し、前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、前記中間情報生成部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した前記第1の情報及び前記メッセージを生成する際に得られるN回分の前記第2の情報を用いてN回分の前記第3の情報を生成し、前記中間情報提供部は、N回分の前記第3の情報を1回の対話で検証者に提供し、前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、請求項6に記載の情報処理装置。前記メッセージ生成部は、前記N回分のメッセージから1つのハッシュ値を生成し、前記メッセージ提供部は、前記N回分のメッセージに代えて前記ハッシュ値を前記検証者に提供する、請求項10に記載の情報処理装置。前記メッセージ生成部は、生成した前記メッセージを記憶装置に格納し、前記記憶装置に格納したメッセージの合計サイズがハッシュ関数のブロック単位より大きい場合に、当該記憶装置に格納したメッセージを利用して、当該ハッシュ関数が前記ハッシュ値の計算途中で算出する中間値を算出し、前記記憶装置に格納したメッセージを消去する処理を逐次実行して前記ハッシュ値を算出する、請求項11に記載の情報処理装置。シードから乱数の組を発生させる乱数生成部と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成する署名生成部と、前記多次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供する署名提供部と、を備え、前記署名生成部は、記憶装置に前記シードを格納し、前記電子署名の生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、署名生成装置。シードから乱数の組を発生させるステップと、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記生成するステップでは、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する処理が実行される、情報処理方法。シードから乱数の組を発生させるステップと、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、前記検証者に前記第3の情報を提供するステップと、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージを生成するステップでは、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する処理が実行される、情報処理方法。シードから乱数の組を発生させるステップと、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成するステップと、前記多次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供するステップと、を含み、前記生成するステップでは、記憶装置に前記シードを格納し、前記電子署名の生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する処理が実行される、署名生成方法。シードから乱数の組を発生させる乱数生成機能と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成機能は、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、プログラム。シードから乱数の組を発生させる乱数生成機能と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成機能と、前記検証者に前記第3の情報を提供する中間情報提供機能と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成機能は、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、プログラム。シードから乱数の組を発生させる乱数生成機能と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成する署名生成機能と、前記多次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供する署名提供機能と、をコンピュータに実現させるためのプログラムであり、前記署名生成機能は、記憶装置に前記シードを格納し、前記電子署名の生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、プログラム。上記の通り、多変数多項式問題は、量子コンピュータを用いても解くことが困難な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上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、情報処理装置が提供される。また、本技術の別の観点によれば、シードから乱数の組を発生させる乱数生成部と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、前記検証者に前記第3の情報を提供する中間情報提供部と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、情報処理装置が提供される。また、本技術の別の観点によれば、シードから乱数の組を発生させる乱数生成部と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成する署名生成部と、前記多次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供する署名提供部と、を備え、前記署名生成部は、記憶装置に前記シードを格納し、前記電子署名の生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、署名生成装置が提供される。また、本技術の別の観点によれば、シードから乱数の組を発生させるステップと、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記生成するステップでは、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する処理が実行される、情報処理方法が提供される。また、本技術の別の観点によれば、シードから乱数の組を発生させるステップと、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、前記検証者に前記第3の情報を提供するステップと、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージを生成するステップでは、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する処理が実行される、情報処理方法が提供される。また、本技術の別の観点によれば、シードから乱数の組を発生させるステップと、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成するステップと、前記多次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供するステップと、を含み、前記生成するステップでは、記憶装置に前記シードを格納し、前記電子署名の生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する処理が実行される、署名生成方法が提供される。また、本技術の別の観点によれば、シードから乱数の組を発生させる乱数生成機能と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成機能は、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、プログラムが提供される。また、本技術の別の観点によれば、シードから乱数の組を発生させる乱数生成機能と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成機能と、前記検証者に前記第3の情報を提供する中間情報提供機能と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成機能は、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、プログラムが提供される。また、本技術の別の観点によれば、シードから乱数の組を発生させる乱数生成機能と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成する署名生成機能と、前記多次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供する署名提供機能と、をコンピュータに実現させるためのプログラムであり、前記署名生成機能は、記憶装置に前記シードを格納し、前記電子署名の生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、プログラムが提供される。また、本技術の別の観点によれば、上記のプログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。また、本技術の別の観点によれば、上記のプログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。以上説明したように本技術によれば、効率的に解く手段トラップドアが知られていない多次多変数連立方程式を用いて、高い安全性を有する効率的な公開鍵認証方式又は電子署名方式を実現することが可能になる。以下に添付図面を参照しながら、本技術の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。[説明の流れについて]ここで、以下に記載する本技術の実施形態に関する説明の流れについて簡単に述べる。まず、図1を参照しながら、公開鍵認証方式のアルゴリズム構成について説明する。次いで、図2を参照しながら、電子署名方式のアルゴリズム構成について説明する。次いで、図3を参照しながら、nパスの公開鍵認証方式について説明する。次いで、図4及び図5を参照しながら、3パスの公開鍵認証方式に係るアルゴリズムの構成例について説明する。次いで、図6及び図7を参照しながら、5パスの公開鍵認証方式に係るアルゴリズムの構成例について説明する。次いで、図8及び図9を参照しながら、3パス及び5パスの公開鍵認証方式に係る効率的なアルゴリズムを電子署名方式のアルゴリズムに変形する方法について説明する。次いで、図10~図28を参照しながら、本実施形態に係る中間変数の管理方法について説明する。次いで、図29を参照しながら、本技術の第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:中間変数の効率的な管理方法5-1:概要5-2:適用例13パス方式の基本構成への適用5-3:適用例23パス方式の並列化構成への適用5-4:適用例35パス方式の基本構成への適用5-5:適用例45パス方式v並列化構成への適用5-6:適用例5電子署名方式への適用5-7:変形例Aハッシュ関数の構造を考慮した構成5-7-1:3パス方式への適用5-7-2:5パス方式への適用5-8:変形例Bシードの決め方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:中間変数の効率的な管理方法>ところで、上記の公開鍵認証方式及び電子署名方式のアルゴリズムを実行する際、多くの中間変数を証明者アルゴリズムPが保持していることに気づくであろう。例えば、図4に示した3パス方式のアルゴリズムにおいて、工程1で生成した中間変数r0,t0,e0,r1,t1,e1は、証明者アルゴリズムPにより保持され、工程3で再び利用される。また、図5に示した並列化アルゴリズムのように、工程1でメッセージをハッシュ値Cmtに纏めて送信する構成の場合、証明者アルゴリズムPは、工程3で再び利用する中間変数r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1i,c2ii=1~Nを中間変数として保持しておく必要がある。そのため、上記の公開鍵認証方式及び電子署名方式のアルゴリズムを実行するには、十分な記憶領域が必要になる。そこで、本件発明者は、証明者アルゴリズムPが保持すべき中間変数の量を削減し、少ない記憶領域で上記の公開鍵認証方式及び電子署名方式のアルゴリズムを実行できるようにする仕組みを考案した。以下、この仕組み以下、メモリ削減方法について説明する。[5-1:概要図10、図11]まず、図10及び図11を参照しながら、本実施形態に係るメモリ削減方法の概要について説明する。図10は、3パス方式のアルゴリズムを簡略的に表現したものである。一方、図11は、5パス方式のアルゴリズムを簡略的に表現したものである。図10に示すように、3パス方式の場合、1まず、証明者アルゴリズムPによりCmtが生成され、検証者アルゴリズムVへと送られる。2次いで、検証者アルゴリズムVによりChが選択され、証明者アルゴリズムPへと送られる。3次いで、証明者アルゴリズムPによりRspが生成され、検証者アルゴリズムVへと送られる。4次いで、検証者アルゴリズムVによりCmt及びRspに基づく検証が行われる。図10において、a1,...,auは、擬似乱数生成器により生成される中間変数である。一方、b1,...,bvは、乱数成分a1,...,auに基づいて生成される中間変数である。また、T1は、b1,...,bvを生成するための関数である。そして、T2は、Cmtを生成するための関数である。さらに、T3は、Rspを生成するための関数である。このように、Cmtを生成する過程で生成された中間変数は、Rspを生成する過程で利用される。そのため、証明者アルゴリズムPは、Cmtを検証者アルゴリズムVへと送った後も中間変数を保持している必要がある。5パス方式の場合、図11に示すように、1まず、検証者アルゴリズムVによりCmtAが生成され、検証者アルゴリズムVへと送られる。2次いで、検証者アルゴリズムVによりChAが選択され、証明者アルゴリズムPへと送られる。3次いで、検証者アルゴリズムVによりCmtBが生成され、検証者アルゴリズムVへと送られる。4次いで、検証者アルゴリズムVによりChBが選択され、証明者アルゴリズムPへと送られる。5次いで、証明者アルゴリズムPによりRspが生成され、検証者アルゴリズムVへと送られる。6次いで、検証者アルゴリズムVによりCmt及びRspに基づく検証が行われる。図11において、a1,...,auは、擬似乱数生成器により生成される中間変数である。一方、b1,...,bvは、乱数成分a1,...,auに基づいて生成される中間変数である。また、T1は、b1,...,bvを生成するための関数である。そして、T2は、CmtAを生成するための関数である。また、T3は、CmtBを生成するための関数である。さらに、T4は、Rspを生成するための関数である。このように、CmtAを生成する過程で生成された中間変数は、CmtB及びRspを生成する過程で利用される。そのため、証明者アルゴリズムPは、CmtAを検証者アルゴリズムVへと送った後も中間変数を保持している必要がある。しかしながら、図10及び図11に示したアルゴリズムの構成を注意深く分析した結果、擬似乱数生成器に入力するシードの値を保持することにより、中間変数を一時的に破棄できるようにアルゴリズムを変形可能なことが分かった。但し、中間変数を一時的に破棄できるようにするには、ハッシュ値Cmtの生成手順に工夫を施す必要がある。以下、具体例を参照しながら、一度に多くの中間変数を保持せずに済む工夫について詳細に説明する。なお、この工夫は、3パス方式、5パス方式、電子署名方式のいずれにも適用可能である。[5-2:適用例13パス方式の基本構成への適用図12~図14]まず、図12~図14を参照しながら、本実施形態に係るメモリ削減方法を3パス方式の基本構成図4を参照に適用する場合のアルゴリズム構成について説明する。全体構成3パス方式の基本構成は、例えば、図12のように表現することができる。図12に示すように、1まず、証明者アルゴリズムPは、メッセージc0,c1,c2に基づくハッシュ値Cmtを生成する。ハッシュ値Cmtの生成に際し、証明者アルゴリズムPは、擬似乱数生成器PRNGを用いて、r0,t0,e0=PRNGseedを生成する。次いで、証明者アルゴリズムPは、r1,t1,e1=s-r0,r0-t0,Fr0-e0を算出する。次いで、証明者アルゴリズムPは、c0=Hr1,Gt0,r1e0、c1=Ht0,e0、c2=Ht1,e1を算出する。次いで、証明者アルゴリズムPは、Cmt=Hc0,c1,c2を算出する。証明者アルゴリズムPにより生成されたハッシュ値Cmtは、検証者アルゴリズムVへと送られる。2ハッシュ値Cmtを受け取った検証者アルゴリズムVは、チャレンジChを選択する。そして、検証者アルゴリズムVにより選択されたチャレンジChは、証明者アルゴリズムPへと送られる。3チャレンジChを受け取った証明者アルゴリズムPは、返答Rspを生成する。Rspの生成に際し、証明者アルゴリズムPは、チャレンジChに応じてr0,t0,e0,r1,t1,e1,c0,c1,c2の中から必要な組み合わせを選択し、返答Rspに設定する。そして、証明者アルゴリズムPにより生成された返答Rspは、検証者アルゴリズムVへと送られる。4返答Rspを受け取った検証者アルゴリズムVは、ハッシュ値Cmt、チャレンジCh、及び返答Rspに基づいて検証を実行する。ここで、以上説明した3パス方式の基本構成において、ハッシュ値Cmtの生成後に中間変数r0,t0,e0,r1,t1,e1,c0,c1,c2を一時的に破棄できるようにしたハッシュ値Cmtの生成方法について説明する。また、ここで説明するハッシュ値Cmtの生成方法を適用した場合における返答Rspの生成方法についても説明する。ハッシュ値Cmtの生成方法まず、図13を参照する。図13に示すように、証明者アルゴリズムPは、ハッシュ値Cmtの生成を開始すると、まず、r0,seedt0=PRNGseedr0を算出し、その後でr0及びseedr0を記憶するS101。次いで、証明者アルゴリズムPは、t0,seede0=PRNGseedt0を算出し、その後でt0を記憶するS102。次いで、証明者アルゴリズムPは、e0,seed’=PRNGseede0を算出し、その後でe0を記憶するS103。次いで、証明者アルゴリズムPは、r1=s-r0を算出し、その後でr1を記憶するS104。次いで、証明者アルゴリズムPは、t1=r0-t0を算出し、その後でt1を記憶するS105。次いで、証明者アルゴリズムPは、e1=Fr0-e0を算出し、その後でe1を記憶し、r0を消去するS106。次いで、証明者アルゴリズムPは、c2=Ht1,e1を算出し、その後でc2を記憶し、t1及びe1を消去するS107。次いで、証明者アルゴリズムPは、c0=Hr1,Gt0,r1e0を算出し、その後でc0を記憶し、r1を消去するS108。次いで、証明者アルゴリズムPは、c1=Ht0,e0を算出し、その後でc1を記憶し、t0及びe0を消去するS109。次いで、証明者アルゴリズムPは、ハッシュ値Cmt=Hc0,c1,c2を算出し、その後でc0,c1,c2を消去するS110。ステップS110の処理を完了した後、証明者アルゴリズムPは、ハッシュ値Cmtの生成に係る一連の処理を終了する。なお、この時点で証明者アルゴリズムPは、中間変数r0,t0,e0,r1,t1,e1,c0,c1,c2を保持していない。返答Rspの生成方法次に、図14を参照する。図14に示すように、証明者アルゴリズムPは、チャレンジChの値を判別するS121。Ch=0の場合、証明者アルゴリズムPは、処理をステップS122に進める。Ch=1の場合、証明者アルゴリズムPは、処理をステップS124に進める。Ch=2の場合、証明者アルゴリズムPは、処理をステップS126に進める。処理をステップS122に進めた場合、証明者アルゴリズムPは、r0,t1,e1,c0を生成するS122。このとき、証明者アルゴリズムPは、図13に示したアルゴリズムのうち、必要なステップを実行してr0,t1,e1,c0を生成する。次いで、証明者アルゴリズムPは、返答Rsp=r0,t1,e1,c0を設定しS123、返答Rspの生成に係る一連の処理を終了する。また、処理をステップS124に進めた場合、証明者アルゴリズムPは、r1,t0,e0,c2を生成するS124。このとき、証明者アルゴリズムPは、図13に示したアルゴリズムのうち、必要なステップを実行してr1,t0,e0,c2を生成する。次いで、証明者アルゴリズムPは、返答Rsp=r1,t0,e0,c2を設定しS125、返答Rspの生成に係る一連の処理を終了する。また、処理をステップS126に進めた場合、証明者アルゴリズムPは、r1,t1,e1,c1を生成するS126。このとき、証明者アルゴリズムPは、図13に示したアルゴリズムのうち、必要なステップを実行してr1,t1,e1,c1を生成する。次いで、証明者アルゴリズムPは、返答Rsp=r1,t1,e1,c1を設定しS127、返答Rspの生成に係る一連の処理を終了する。以上、本実施形態に係るメモリ削減方法を3パス方式の基本構成に適用する場合のアルゴリズム構成について説明した。上記のメモリ削減方法を適用することにより、少ない記憶領域で3パス方式の公開鍵認証方式を実現することが可能になる。[5-3:適用例23パス方式の並列化構成への適用図15、図16]次に、図15及び図16を参照しながら、本実施形態に係るメモリ削減方法を3パスの並列化構成図5を参照に適用する場合のアルゴリズム構成について説明する。ここでは、図5に示した3パス方式の並列化アルゴリズムに本実施形態に係るメモリ削減方法を適用する場合のアルゴリズム構成について考える。ハッシュ値Cmtの生成方法まず、図15を参照する。図15に示すように、証明者アルゴリズムPは、ハッシュ値Cmtの生成を開始し、i=1~Nについて、ステップS131~S139の処理を繰り返し実行する。ステップS131において、証明者アルゴリズムPは、r0i,seedt0i=PRNGseedr0iを算出し、その後でr0iを記憶するS131。但し、証明者アルゴリズムPは、i=1の場合にseedr01を記憶する。次いで、証明者アルゴリズムPは、t0i,seede0i=PRNGseedt0iを算出し、その後でt0iを記憶するS132。次いで、証明者アルゴリズムPは、e0i,seedr0i1=PRNGseede0iを算出し、その後でe0iを記憶するS133。次いで、証明者アルゴリズムPは、r1i=s-r0iを算出し、その後でr1iを記憶するS134。次いで、証明者アルゴリズムPは、t1i=r0i-t0iを算出し、その後でt1iを記憶するS135。次いで、証明者アルゴリズムPは、e1i=Fr0i-e0iを算出し、その後でe1iを記憶し、r0iを消去するS136。次いで、証明者アルゴリズムPは、c2i=Ht1i,e1iを算出し、その後でc2iを記憶し、t1i及びe1iを消去するS137。次いで、証明者アルゴリズムPは、c0i=Hr1i,Gt0i,r1ie0iを算出し、その後でc0iを記憶し、r1iを消去するS138。次いで、証明者アルゴリズムPは、c1i=Ht0i,e0iを算出し、その後でc1iを記憶し、t0i及びe0iを消去するS139。i=1~Nについて、ステップS131~S139の処理を実行した後、証明者アルゴリズムPは、ハッシュ値Cmt=Hc01,c11,c21,...,c0N,c1N,c2Nを算出し、その後でc01,c11,c21,...,c0N,c1N,c2Nを消去するS140。ステップS140の処理を完了した後、証明者アルゴリズムPは、ハッシュ値Cmtの生成に係る一連の処理を終了する。なお、この時点で証明者アルゴリズムPは、中間変数r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1i,c2ii=1~Nを保持していない。返答Rspiの生成方法次に、図16を参照する。なお、i=1~Nについて、同様に返答Rspiの生成処理が実行される。図16に示すように、証明者アルゴリズムPは、チャレンジChiの値を判別するS151。Chi=0の場合、証明者アルゴリズムPは、処理をステップS152に進める。Chi=1の場合、証明者アルゴリズムPは、処理をステップS154に進める。Chi=2の場合、証明者アルゴリズムPは、処理をステップS156に進める。処理をステップS152に進めた場合、証明者アルゴリズムPは、r0i,t1i,e1i,c0iを生成するS152。このとき、証明者アルゴリズムPは、図15に示したアルゴリズムのうち、必要なステップを実行してr0i,t1i,e1i,c0iを生成する。次いで、証明者アルゴリズムPは、返答Rspi=r0i,t1i,e1i,c0iを設定しS153、返答Rspiの生成に係る一連の処理を終了する。また、処理をステップS154に進めた場合、証明者アルゴリズムPは、r1i,t0i,e0i,c2iを生成するS154。このとき、証明者アルゴリズムPは、図15に示したアルゴリズムのうち、必要なステップを実行してr1i,t0i,e0i,c2iを生成する。次いで、証明者アルゴリズムPは、返答Rspi=r1i,t0i,e0i,c2iを設定しS155、返答Rspiの生成に係る一連の処理を終了する。また、処理をステップS156に進めた場合、証明者アルゴリズムPは、r1i,t1i,e1i,c1iを生成するS156。このとき、証明者アルゴリズムPは、図15に示したアルゴリズムのうち、必要なステップを実行してr1i,t1i,e1i,c1iを生成する。次いで、証明者アルゴリズムPは、返答Rspi=r1i,t1i,e1i,c1iを設定しS157、返答Rspiの生成に係る一連の処理を終了する。以上、本実施形態に係るメモリ削減方法を3パス方式の並列化構成に適用する場合のアルゴリズム構成について説明した。上記のメモリ削減方法を適用することにより、少ない記憶領域で3パス方式の並列化された公開鍵認証方式を実現することが可能になる。メモリ削減効果について仮に、q,n,m,N=2,80,80,140とし、ciが160ビットで表せるとする場合、上記のメモリ削減方法を適用しないと、134400ビット分の記憶領域が必要になる。しかし、上記のメモリ削減方法を適用した場合、ci及びseedが160ビットで表せるならば、アルゴリズムの実行に要する記憶領域は、68000ビットまで削減される。つまり、上記のメモリ削減方法を適用することにより、必要な記憶領域のサイズが半分以下で済むようになる。[5-4:適用例35パス方式の基本構成への適用図17~図20]次に、図17~図20を参照しながら、本実施形態に係るメモリ削減方法を5パスの基本構成図6を参照に適用する場合のアルゴリズム構成について説明する。全体構成5パス方式の基本構成は、例えば、図17のように表現することができる。図17に示すように、1まず、証明者アルゴリズムPは、メッセージc0,c1に基づくハッシュ値CmtAを生成する。ハッシュ値CmtAの生成に際し、証明者アルゴリズムPは、擬似乱数生成器PRNGを用いて、r0,t0,e0=PRNGseedを生成する。次いで、証明者アルゴリズムPは、r1=s-r0を算出する。次いで、証明者アルゴリズムPは、c0=Hr0,t0,e0、c1=Hr1,Gt0,r1e0を算出する。次いで、証明者アルゴリズムPは、CmtA=Hc0,c1を算出する。証明者アルゴリズムPにより生成されたハッシュ値CmtAは、検証者アルゴリズムVへと送られる。2ハッシュ値CmtAを受け取った検証者アルゴリズムVは、チャレンジChAを選択する。そして、検証者アルゴリズムVにより選択されたチャレンジChAは、証明者アルゴリズムPへと送られる。3チャレンジChAを受け取った証明者アルゴリズムPは、チャレンジChA、中間変数t1,e1を含むコミットメント値CmtBを生成する。コミットメント値CmtBの生成に際し、証明者アルゴリズムPは、t1=ChAr0-t0、e1=ChAFr0-e0を算出する。次いで、証明者アルゴリズムPは、CmtB=t1,e1を設定する。証明者アルゴリズムPにより生成されたコミットメント値CmtBは、検証者アルゴリズムVへと送られる。4コミットメント値CmtBを受け取った検証者アルゴリズムVは、チャレンジChBを選択する。そして、検証者アルゴリズムVにより選択されたチャレンジChBは、証明者アルゴリズムPへと送られる。5チャレンジChBを受け取った証明者アルゴリズムPは、返答Rspを生成する。Rspの生成に際し、証明者アルゴリズムPは、チャレンジChBに応じてr0,r1,c0,c1の中から必要な組み合わせを選択し、返答Rspに設定する。そして、証明者アルゴリズムPにより生成された返答Rspは、検証者アルゴリズムVへと送られる。6返答Rspを受け取った検証者アルゴリズムVは、ハッシュ値CmtA、チャレンジChA、コミットメント値CmtB、チャレンジChB、及び返答Rspに基づいて検証を実行する。ここで、以上説明した5パス方式の基本構成において、ハッシュ値CmtAの生成後に中間変数r0,t0,e0,r1,c0,c1を一時的に破棄できるようにしたハッシュ値CmtAの生成方法について説明する。また、コミットメント値CmtBの生成後に中間変数r0,t0,e0を一時的に破棄できるようにしたコミットメント値CmtBの生成方法について説明する。さらに、ここで説明するハッシュ値CmtA及びコミットメント値CmtBの生成方法を適用した場合における返答Rspの生成方法についても説明する。ハッシュ値CmtAの生成方法まず、図18を参照する。図18に示すように、証明者アルゴリズムPは、ハッシュ値CmtAの生成を開始すると、まず、r0,seedt0=PRNGseedr0を算出し、その後でr0及びseedr0を記憶するS201。次いで、証明者アルゴリズムPは、t0,seede0=PRNGseedt0を算出し、その後でt0を記憶するS202。次いで、証明者アルゴリズムPは、e0,seed’=PRNGseede0を算出し、その後でe0を記憶するS203。次いで、証明者アルゴリズムPは、r1=s-r0を算出し、その後でr1を記憶するS204。次いで、証明者アルゴリズムPは、c0=Hr0,t0,e0を算出し、その後でc0を記憶し、r0を消去するS205。次いで、証明者アルゴリズムPは、c1=Hr1,Gt0,r1e0を算出し、その後でc1を記憶し、r1,t0,e0を消去するS206。次いで、証明者アルゴリズムPは、ハッシュ値CmtA=Hc0,c1を算出し、その後でc0,c1を消去するS207。ステップS207の処理を完了した後、証明者アルゴリズムPは、ハッシュ値CmtAの生成に係る一連の処理を終了する。なお、この時点で証明者アルゴリズムPは、中間変数r0,t0,e0,r1,c0,c1を保持していない。ハッシュ値CmtBの生成方法次に、図19を参照する。図19に示すように、証明者アルゴリズムPは、コミットメント値CmtBの生成を開始すると、まず、r0,seedt0=PRNGseedr0を算出し、その後でr0及びseedr0を記憶するS211。次いで、証明者アルゴリズムPは、t0,seede0=PRNGseedt0を算出し、その後でt0を記憶するS212。次いで、証明者アルゴリズムPは、t1=ChAr0-t0を算出し、その後でt1を記憶し、t0を消去するS213。次いで、証明者アルゴリズムPは、e0,seed’=PRNGseede0を算出し、その後でe0を記憶するS214。次いで、証明者アルゴリズムPは、e1=Fr0-e0を算出し、その後でe1を記憶し、r0,e0を消去するS215。次いで、証明者アルゴリズムPは、コミットメント値CmtB=t1,e1を設定するS216。ステップS216の処理を完了した後、証明者アルゴリズムPは、コミットメント値CmtBの生成に係る一連の処理を終了する。なお、この時点で証明者アルゴリズムPは、中間変数r0,t0,e0を保持していない。返答Rspの生成方法次に、図20を参照する。図20に示すように、証明者アルゴリズムPは、チャレンジChBの値を判別するS221。ChB=0の場合、証明者アルゴリズムPは、処理をステップS222に進める。ChB=1の場合、証明者アルゴリズムPは、処理をステップS224に進める。処理をステップS222に進めた場合、証明者アルゴリズムPは、r0,c1を生成するS222。このとき、証明者アルゴリズムPは、図18に示したアルゴリズムのうち、必要なステップを実行してr0,c1を生成する。次いで、証明者アルゴリズムPは、返答Rsp=r0,c1を設定しS223、返答Rspの生成に係る一連の処理を終了する。また、処理をステップS224に進めた場合、証明者アルゴリズムPは、r1,c0を生成するS224。このとき、証明者アルゴリズムPは、図18に示したアルゴリズムのうち、必要なステップを実行してr1,c0を生成する。次いで、証明者アルゴリズムPは、返答Rsp=r1,c0を設定しS225、返答Rspの生成に係る一連の処理を終了する。以上、本実施形態に係るメモリ削減方法を5パス方式の基本構成に適用する場合のアルゴリズム構成について説明した。上記のメモリ削減方法を適用することにより、少ない記憶領域で5パス方式の公開鍵認証方式を実現することが可能になる。[5-5:適用例45パス方式の並列化構成への適用図20、図21]次に、図21及び図22を参照しながら、本実施形態に係るメモリ削減方法を5パスの並列化構成図7を参照に適用する場合のアルゴリズム構成について説明する。ここでは、図7に示した5パス方式の並列化アルゴリズムに本実施形態に係るメモリ削減方法を適用する場合のアルゴリズム構成について考える。ハッシュ値CmtAの生成方法まず、図21を参照する。図21に示すように、証明者アルゴリズムPは、ハッシュ値CmtAの生成を開始し、i=1~Nについて、ステップS231~S236の処理を繰り返し実行する。ステップS231において、証明者アルゴリズムPは、r0i,seedt0i=PRNGseedr0iを算出し、その後でr0iを記憶するS231。但し、証明者アルゴリズムPはi=1の場合にseedr01を記憶する。次いで、証明者アルゴリズムPは、t0i,seede0i=PRNGseedt0iを算出し、その後でt0iを記憶するS232。次いで、証明者アルゴリズムPは、e0i,seedr0i1=PRNGseede0iを算出し、その後でe0iを記憶するS233。次いで、証明者アルゴリズムPは、r1i=s-r0iを算出し、その後でr1iを記憶するS234。次いで、証明者アルゴリズムPは、c0i=Hr0i,t0i,e0iを算出し、その後でc0iを記憶し、r0iを消去するS235。次いで、証明者アルゴリズムPは、c1i=Hr1i,Gt0i,r1ie0iを算出し、その後でc1iを記憶し、r1i,t0i,e0iを消去するS236。i=1~Nについて、ステップS231~S236の処理を実行した後、証明者アルゴリズムPは、ハッシュ値CmtA=Hc01,c11,...,c0N,c1Nを算出し、その後でc01,c11,...,c0N,c1Nを消去するS237。ステップS237の処理を完了した後、証明者アルゴリズムPは、ハッシュ値CmtAの生成に係る一連の処理を終了する。なお、この時点で証明者アルゴリズムPは、中間変数r0i,t0i,e0i,r1i,c0i,c1ii=1~Nを保持していない。ハッシュ値CmtBの生成方法次に、図22を参照する。図22に示すように、証明者アルゴリズムPは、コミットメント値CmtBの生成を開始し、i=1~Nについて、ステップS241~S246の処理を繰り返し実行する。ステップS241において、証明者アルゴリズムPは、r0i,seedt0i=PRNGseedr0iを算出し、その後でr0iを記憶するS241。但し、証明者アルゴリズムPはi=1の場合にseedr01を記憶する。次いで、証明者アルゴリズムPは、t0i,seede0i=PRNGseedt0iを算出し、その後でt0iを記憶するS242。次いで、証明者アルゴリズムPは、t1i=ChAir0i-t0iを算出し、その後でt1iを記憶し、t0iを消去するS243。次いで、証明者アルゴリズムPは、e0i,seedr0i1=PRNGseede0iを算出し、その後でe0iを記憶するS244。次いで、証明者アルゴリズムPは、e1i=Fr0i-e0iを算出し、その後でe1iを記憶し、r0i,e0iを消去するS245。次いで、証明者アルゴリズムPは、コミットメント値CmtB=t1i,e1iを設定し、検証者アルゴリズムVへと送り、その後でt1i,e1iを消去するS246。i=1~Nについて、ステップS241~S246の処理を実行した後、証明者アルゴリズムPは、コミットメント値CmtBの生成に係る一連の処理を終了する。なお、この時点で証明者アルゴリズムPは、中間変数r0i,t0i,e0i,t1i,e1ii=1~Nを保持していない。返答Rspiの生成方法次に、図23を参照する。なお、i=1~Nについて、同様に返答Rspiの生成処理が実行される。図23に示すように、証明者アルゴリズムPは、チャレンジChBiの値を判別するS251。ChBi=0の場合、証明者アルゴリズムPは、処理をステップS252に進める。ChBi=1の場合、証明者アルゴリズムPは、処理をステップS254に進める。処理をステップS252に進めた場合、証明者アルゴリズムPは、r0i,c1iを生成するS252。このとき、証明者アルゴリズムPは、図21に示したアルゴリズムのうち、必要なステップを実行してr0i,c1iを生成する。次いで、証明者アルゴリズムPは、返答Rspi=r0i,c1iを設定しS253、返答Rspiの生成に係る一連の処理を終了する。また、処理をステップS254に進めた場合、証明者アルゴリズムPは、r1i,c0iを生成するS254。このとき、証明者アルゴリズムPは、図21に示したアルゴリズムのうち、必要なステップを実行してr1i,c0iを生成する。次いで、証明者アルゴリズムPは、返答Rspi=r1i,c0iを設定しS255、返答Rspiの生成に係る一連の処理を終了する。以上、本実施形態に係るメモリ削減方法を5パス方式の並列化構成に適用する場合のアルゴリズム構成について説明した。上記のメモリ削減方法を適用することにより、少ない記憶領域で5パス方式の並列化された公開鍵認証方式を実現することが可能になる。メモリ削減効果について仮に、q,n,m,N=2,80,80,90とし、ciが160ビットで表せるとする場合、上記のメモリ削減方法を適用しないと、72000ビット分以上の記憶領域が必要になる。しかし、上記のメモリ削減方法を適用した場合、ci及びseedが160ビットで表せるならば、アルゴリズムの実行に要する記憶領域は、29600ビット以下にまで削減される。つまり、上記のメモリ削減方法を適用することにより、必要な記憶領域のサイズが半分以下で済むようになる。[5-6:適用例5電子署名方式への適用]次に、本実施形態に係るメモリ削減方法を電子署名方式図8及び図9を参照に適用する場合のアルゴリズム構成について述べる。図8及び図9に示した通り、上記の電子署名方式は、3パス方式や5パス方式の並列化アルゴリズムから得られる。そのため、署名生成アルゴリズムSigが実行する処理には、CmtやRspiの生成処理が含まれる。そこで、これらの処理に上記のメモリ削減方法を適用することで、一度に保持すべき中間変数の最大量が低減するため、少ない記憶領域で上記の電子署名方式に係るアルゴリズムを実行することが可能になる。[5-7:変形例Aハッシュ関数の構造を考慮した構成図24]ところで、上記の各アルゴリズムにおいては、ハッシュ値Cmt又はCmtAを算出するために記憶領域にメッセージの値を保持していた。例えば、図15の例ではメッセージc0i,c1i,c2ii=1~Nが記憶領域に保持されている。同様に、図21の例ではメッセージc0i,c1ii=1~Nが記憶領域に保持されている。しかしながら、メッセージの値を全て記憶領域に格納しておくことは、記憶領域のサイズを節約するという観点からは好ましくない。そこで、本件発明者は、ハッシュ関数の構造に注目し、メッセージの値を全て記憶領域に格納しておくことなく、ハッシュ値Cmt又はCmtAを算出する方法を考案した。多くの場合、ハッシュ関数は、入力をブロック単位に区切り、ブロック単位で順次処理を進める構造を有している。例えば、SHA-1の場合、ハッシュ関数は、図24に示すような構造を有している。図24に示すハッシュ関数は、入力MをZ個のブロックm1,...,mZに区切り、インデックスjをインクリメントしながら、ブロックmjを初期値IV又は中間値CVjと共に所定の関数CFに作用させてハッシュ値を生成する。従って、中間値CVjが得られた時点で、それ以前に利用したブロックは不要になる。そこで、この特性を利用し、アルゴリズムの実行に必要な記憶領域のサイズを更に削減する仕組みを考案した。以下、この仕組みについて具体的に説明する。5-7-1:変形例A13パス方式への適用図25、図26まず、図25及び図26を参照する。図25及び図26は、図15に示したアルゴリズムを改良した構成ハッシュ関数の構造を考慮したアルゴリズムを示したものである。図25に示すように、証明者アルゴリズムPは、ハッシュ値Cmtの生成を開始し、i=1~Nについて、ステップS301~S310の処理を繰り返し実行する。ステップS301において、証明者アルゴリズムPは、r0i,seedt0i=PRNGseedr0iを算出し、その後でr0iを記憶するS301。但し、証明者アルゴリズムPは、i=1の場合にseedr01を記憶する。次いで、証明者アルゴリズムPは、t0i,seede0i=PRNGseedt0iを算出し、その後でt0iを記憶するS302。次いで、証明者アルゴリズムPは、e0i,seedr0i1=PRNGseede0iを算出し、その後でe0iを記憶するS303。次いで、証明者アルゴリズムPは、r1i=s-r0iを算出し、その後でr1iを記憶するS304。次いで、証明者アルゴリズムPは、t1i=r0i-t0iを算出し、その後でt1iを記憶するS305。次いで、証明者アルゴリズムPは、e1i=Fr0i-e0iを算出し、その後でe1iを記憶し、r0iを消去するS306。次いで、証明者アルゴリズムPは、c2i=Ht1i,e1iを算出し、その後でc2iを記憶し、t1i及びe1iを消去するS307。次いで、証明者アルゴリズムPは、c0i=Hr1i,Gt0i,r1ie0iを算出し、その後でc0iを記憶し、r1iを消去するS308。次いで、証明者アルゴリズムPは、c1i=Ht0i,e0iを算出し、その後でc1iを記憶し、t0i及びe0iを消去するS309。次いで、証明者アルゴリズムPは、ハッシュ値Cmt=Hc01,c11,c21,...,c0N,c1N,c2Nの算出に係る計算を実行するS310:詳細は後述。i=1~Nについて、ステップS301~S310の処理を実行した後、証明者アルゴリズムPは、ハッシュ値Cmtの生成に係る一連の処理を終了する。なお、この時点で証明者アルゴリズムPは、中間変数r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1i,c2ii=1~Nを保持していない。ステップS310の処理についてここで、図26を参照しながら、ステップS310の処理について詳細に説明する。図26に示すように、ステップS310において、証明者アルゴリズムPは、既に記憶領域に保持しているメッセージ...,c0i,c1i,c2iの合計サイズがハッシュ関数のブロック単位以上であるか否かを判定するS311。保持しているメッセージの合計サイズがブロック単位以上の場合、証明者アルゴリズムPは、処理をステップS312に進める。一方、保持しているメッセージの合計サイズがブロック単位より小さい場合、証明者アルゴリズムPは、処理をステップS313に進める。処理をステップS312に進めた場合、証明者アルゴリズムPは、記憶領域に保持しているメッセージ...,c0i,c1i,c2iと、IV又は中間値CVjを利用して次の中間値CVj1を生成して記憶領域に格納し、その後でメッセージ...,c0i,c1i,c2i及び中間値CVjを消去するS312。一方、処理をステップS313に進めた場合、証明者アルゴリズムPは、メッセージc0i,c1i,c2iを記憶領域に格納するS313。ステップS312又はS313の処理を実行した後、証明者アルゴリズムPは、ステップS310の処理を終了する。以上、ハッシュ関数の構造を考慮した3パス方式のアルゴリズムについて説明した。この構成を適用すると、q,n,m,N=2,80,80,140とし、ci及びseedが160ビットで表せ、かつ、ハッシュ関数のブロック単位が512ビットの場合、アルゴリズムの実行に要する記憶領域は、1952ビット以下まで削減される。5-7-2:変形例A25パス方式への適用図27、図28次に、図27及び図28を参照する。図27及び図28は、図21に示したアルゴリズムを改良した構成ハッシュ関数の構造を考慮したアルゴリズムを示したものである。図27に示すように、証明者アルゴリズムPは、ハッシュ値CmtAの生成を開始し、i=1~Nについて、ステップS401~S407の処理を繰り返し実行する。ステップS401において、証明者アルゴリズムPは、r0i,seedt0i=PRNGseedr0iを算出し、その後でr0iを記憶するS401。但し、証明者アルゴリズムPはi=1の場合にseedr01を記憶する。次いで、証明者アルゴリズムPは、t0i,seede0i=PRNGseedt0iを算出し、その後でt0iを記憶するS402。次いで、証明者アルゴリズムPは、e0i,seedr0i1=PRNGseede0iを算出し、その後でe0iを記憶するS403。次いで、証明者アルゴリズムPは、r1i=s-r0iを算出し、その後でr1iを記憶するS404。次いで、証明者アルゴリズムPは、c0i=Hr0i,t0i,e0iを算出し、その後でc0iを記憶し、r0iを消去するS405。次いで、証明者アルゴリズムPは、c1i=Hr1i,Gt0i,r1ie0iを算出し、その後でc1iを記憶し、r1i,t0i,e0iを消去するS406。次いで、証明者アルゴリズムPは、ハッシュ値CmtA=Hc01,c11,...,c0N,c1Nの算出に係る計算を実行するS407:詳細は後述。i=1~Nについて、ステップS401~S407の処理を実行した後、証明者アルゴリズムPは、ハッシュ値CmtAの生成に係る一連の処理を終了する。なお、この時点で証明者アルゴリズムPは、中間変数r0i,t0i,e0i,r1i,c0i,c1ii=1~Nを保持していない。ステップS407の処理についてここで、図28を参照しながら、ステップS407の処理について詳細に説明する。図28に示すように、ステップS407において、証明者アルゴリズムPは、既に記憶領域に保持しているメッセージ...,c0i,c1iの合計サイズがハッシュ関数のブロック単位以上であるか否かを判定するS411。保持しているメッセージの合計サイズがブロック単位以上の場合、証明者アルゴリズムPは、処理をステップS412に進める。一方、保持しているメッセージの合計サイズがブロック単位より小さい場合、証明者アルゴリズムPは、処理をステップS413に進める。処理をステップS412に進めた場合、証明者アルゴリズムPは、記憶領域に保持しているメッセージ...,c0i,c1iと、IV又は中間値CVjを利用して次の中間値CVj1を生成して記憶領域に格納し、その後でメッセージ...,c0i,c1i及び中間値CVjを消去するS412。一方、処理をステップS413に進めた場合、証明者アルゴリズムPは、メッセージc0i,c1iを記憶領域に格納するS413。ステップS412又はS413の処理を実行した後、証明者アルゴリズムPは、ステップS407の処理を終了する。以上、ハッシュ関数の構造を考慮した5パス方式のアルゴリズムについて説明した。この構成を適用すると、q,n,m,N=2,80,80,90とし、ci及びseedが160ビットで表せ、かつ、ハッシュ関数のブロック単位が512ビットの場合、アルゴリズムの実行に要する記憶領域は、1712ビット以下まで削減される。[5-8:変形例Bシードの決め方]これまで、一つのシードから全ての乱数が生成される構成を念頭に置いて説明を進めてきたが、上記の各アルゴリズムは、このような構成に限定されるものではない。つまり、複数のシードから乱数が生成されるように構成することも可能である。例えば、下記の式13~式15に示すように、1つのシードに対し、事前に取り決めた値を作用させ、任意の変数にランダムアクセスすることができるように構成してもよい。この例では、シードseed、テキストr,t,e、インデックスiを組み合わせている。この例のように、一つのシードseedから任意の変数へとランダムアクセスできるようにすることで、必要な中間変数を直ちに取得することが可能になり、演算速度の向上が期待できる。以上、中間変数の効率的な管理方法について説明した。上記の方法を適用することで、アルゴリズムの実行に要する記憶領域のサイズを削減することが可能になる。<6:ハードウェア構成例図29>上記の各アルゴリズムは、例えば、図29に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図29に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、PHS、PDA等の携帯情報端末、ゲーム機、接触式又は非接触式のICチップ、接触式又は非接触式のICカード、又は種々の情報家電がこれに含まれる。但し、上記のPHSは、PersonalHandy-phoneSystemの略である。また、上記のPDAは、PersonalDigitalAssistantの略である。図29に示すように、このハードウェアは、主に、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上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、情報処理装置。2前記回答提供部は、前記記憶装置に格納されたシードを利用し、前記回答情報として用いる前記乱数又は前記中間変数を再生成する、上記1に記載の情報処理装置。3前記メッセージ生成部は、N回分N≧2のメッセージを生成し、前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、上記1又は2に記載の情報処理装置。4前記メッセージ生成部は、前記N回分のメッセージから1つのハッシュ値を生成し、前記メッセージ提供部は、前記N回分のメッセージに代えて前記ハッシュ値を前記検証者に提供する、上記3に記載の情報処理装置。5前記メッセージ生成部は、生成した前記メッセージを記憶装置に格納し、前記記憶装置に格納したメッセージの合計サイズがハッシュ関数のブロック単位より大きい場合に、当該記憶装置に格納したメッセージを利用して、当該ハッシュ関数が前記ハッシュ値の計算途中で算出する中間値を算出し、前記記憶装置に格納したメッセージを消去する処理を逐次実行して前記ハッシュ値を算出する、上記4に記載の情報処理装置。6シードから乱数の組を発生させる乱数生成部と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、前記検証者に前記第3の情報を提供する中間情報提供部と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、情報処理装置。7前記中間情報生成部は、前記記憶装置に格納されたシードを利用して、前記第3の情報を生成する際に用いる前記乱数又は前記中間変数を再生成する、上記6に記載の情報処理装置。8前記中間情報生成部は、前記第3の情報の生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、上記7に記載の情報処理装置。9前記回答提供部は、前記記憶装置に格納されたシードを利用し、前記回答情報として用いる前記乱数又は前記中間変数を再生成する、上記6~8のいずれか1項に記載の情報処理装置。10前記メッセージ生成部は、N回分N≧2のメッセージを生成し、前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、前記中間情報生成部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した前記第1の情報及び前記メッセージを生成する際に得られるN回分の前記第2の情報を用いてN回分の前記第3の情報を生成し、前記中間情報提供部は、N回分の前記第3の情報を1回の対話で検証者に提供し、前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、上記6~9のいずれか1項に記載の情報処理装置。11前記メッセージ生成部は、前記N回分のメッセージから1つのハッシュ値を生成し、前記メッセージ提供部は、前記N回分のメッセージに代えて前記ハッシュ値を前記検証者に提供する、上記10に記載の情報処理装置。12前記メッセージ生成部は、生成した前記メッセージを記憶装置に格納し、前記記憶装置に格納したメッセージの合計サイズがハッシュ関数のブロック単位より大きい場合に、当該記憶装置に格納したメッセージを利用して、当該ハッシュ関数が前記ハッシュ値の計算途中で算出する中間値を算出し、前記記憶装置に格納したメッセージを消去する処理を逐次実行して前記ハッシュ値を算出する、上記11に記載の情報処理装置。13シードから乱数の組を発生させる乱数生成部と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成する署名生成部と、前記多次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供する署名提供部と、を備え、前記署名生成部は、記憶装置に前記シードを格納し、前記電子署名の生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、署名生成装置。14シードから乱数の組を発生させるステップと、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記生成するステップでは、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する処理が実行される、情報処理方法。15シードから乱数の組を発生させるステップと、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、前記検証者に前記第3の情報を提供するステップと、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージを生成するステップでは、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する処理が実行される、情報処理方法。16シードから乱数の組を発生させるステップと、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成するステップと、前記多次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供するステップと、を含み、前記生成するステップでは、記憶装置に前記シードを格納し、前記電子署名の生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する処理が実行される、署名生成方法。17シードから乱数の組を発生させる乱数生成機能と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成機能は、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、プログラム。18シードから乱数の組を発生させる乱数生成機能と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成機能と、前記検証者に前記第3の情報を提供する中間情報提供機能と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記回答情報は、前記乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成機能は、記憶装置に前記シードを格納し、前記メッセージの生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、プログラム。19シードから乱数の組を発生させる乱数生成機能と、環K上で定義される多次多変数多項式の組F=f1,...,fm、前記乱数の組、及び署名鍵s∈Knを用いて文書Mに対する電子署名を生成する署名生成機能と、前記多次多変数多項式の組F及びベクトルy=f1s,...,fmsを保持する検証者へと前記電子署名を提供する署名提供機能と、をコンピュータに実現させるためのプログラムであり、前記署名生成機能は、記憶装置に前記シードを格納し、前記電子署名の生成過程で不要になった前記乱数及び当該乱数から生成された中間変数を順次消去する、プログラム。20上記の17~19のいずれか1項に記載のプログラムが記録された、コンピュータにより読み取り可能な記録媒体。備考上記の証明者アルゴリズムPは、乱数生成部、メッセージ生成部、メッセージ提供部、回答提供部、中間情報生成部、中間情報提供部の一例である。また、上記の署名生成アルゴリズムSigは、乱数生成部、署名生成部、署名提供部の一例である。以上、添付図面を参照しながら本技術の好適な実施形態について説明したが、本技術は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本技術の技術的範囲に属するものと了解される。上記の説明において、ハッシュ関数Hを用いるアルゴリズムを紹介したが、ハッシュ関数Hの代わりにコミットメント関数COMを用いてもよい。コミットメント関数COMは、文字列S及び乱数ρを引数にとる関数である。コミットメント関数の例としては、ShaiHaleviとSilvioMicaliによって国際会議CRYPTO1996で発表された方式などがある。"