"環K上で定義される多次多変数多項式の組F=f1,...,fm、署名鍵s∈Kn、及び文書Mに基づいて生成された第1の情報と、前記文書M、前記多次多変数多項式の組F、及びベクトルy=f1s,...,fmsに基づいて前記第1の情報が前記署名鍵sを用いて生成されたことを検証するために必要な複数の第2の情報と、を含む電子署名を取得する署名取得部と、前記電子署名に含まれる複数の第2の情報を用いて前記第1の情報を復元可能か否かを確認することで前記文書Mの正当性を検証する署名検証部と、を備え、前記多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記署名取得部は、前記第2の情報を所定数ずつ取得し、前記署名検証部は、所定数ずつ取得される前記第2の情報を用いて逐次的に前記第1の情報を復元し、復元処理に不要な前記第2の情報を不要になった段階で消去する、署名検証装置。前記第1の情報は、入力される情報をブロック単位に区切って処理する一方向性関数を用いて生成されており、前記署名検証部は、前記所定数ずつ取得される前記第2の情報を用いて前記ブロック単位の処理で前記一方向性関数が出力する中間値を生成する処理、当該中間値及び次に取得される所定数の前記第2の情報を用いて次の中間値を生成する処理を繰り返し実行して前記第1の情報を復元する、請求項1に記載の署名検証装置。所定数の前記第2の情報は、前記中間値の生成が完了した段階で消去される、請求項2に記載の署名検証装置。前記所定数は1であり、前記第2の情報に含まれ、かつ、前記一方向性関数から前記中間値を生成する際に用いる情報のサイズは、前記ブロック単位のデータサイズ以上である、請求項2に記載の署名検証装置。環K上で定義される多次多変数多項式の組F=f1,...,fm、署名鍵s∈Kn、及び文書Mに基づいて生成された第1の情報と、前記文書M、前記多次多変数多項式の組F、及びベクトルy=f1s,...,fmsに基づいて前記第1の情報が前記署名鍵sを用いて生成されたことを検証するために必要な複数の第2の情報と、を含む電子署名を取得するステップと、前記電子署名に含まれる複数の第2の情報を用いて前記第1の情報を復元可能か否かを確認することで前記文書Mの正当性を検証するステップと、を含み、前記多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記取得するステップでは、前記第2の情報を所定数ずつ取得し、前記検証するステップでは、所定数ずつ取得される前記第2の情報を用いて逐次的に前記第1の情報を復元し、復元処理に不要な前記第2の情報を不要になった段階で消去する、署名検証方法。環K上で定義される多次多変数多項式の組F=f1,...,fm、署名鍵s∈Kn、及び文書Mに基づいて生成された第1の情報と、前記文書M、前記多次多変数多項式の組F、及びベクトルy=f1s,...,fmsに基づいて前記第1の情報が前記署名鍵sを用いて生成されたことを検証するために必要な複数の第2の情報と、を含む電子署名を取得する署名取得機能と、前記電子署名に含まれる複数の第2の情報を用いて前記第1の情報を復元可能か否かを確認することで前記文書Mの正当性を検証する署名検証機能と、をコンピュータに実現させるためのプログラムであり、前記多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記署名取得機能は、前記第2の情報を所定数ずつ取得し、前記署名検証機能は、所定数ずつ取得される前記第2の情報を用いて逐次的に前記第1の情報を復元し、復元処理に不要な前記第2の情報を不要になった段階で消去する、プログラム。環K上で定義される多次多変数多項式の組F=f1,...,fm、署名鍵s∈Kn、及び文書Mに基づいて生成された第1の情報と、前記文書M、前記多次多変数多項式の組F、及びベクトルy=f1s,...,fmsに基づいて前記第1の情報が前記署名鍵sを用いて生成されたことを検証するために必要な複数の第2の情報と、を含む電子署名を取得する署名取得機能と、前記電子署名に含まれる複数の第2の情報を用いて前記第1の情報を復元可能か否かを確認することで前記文書Mの正当性を検証する署名検証機能と、をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、前記多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記署名取得機能は、前記第2の情報を所定数ずつ取得し、前記署名検証機能は、所定数ずつ取得される前記第2の情報を用いて逐次的に前記第1の情報を復元し、復元処理に不要な前記第2の情報を不要になった段階で消去する、記録媒体。上記の通り、多変数多項式問題は、量子コンピュータを用いても解くことが困難な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、及び文書Mに基づいて生成された第1の情報と、前記文書M、前記多次多変数多項式の組F、及びベクトルy=f1s,...,fmsに基づいて前記第1の情報が前記署名鍵sを用いて生成されたことを検証するために必要な複数の第2の情報と、を含む電子署名を取得する署名取得部と、前記電子署名に含まれる複数の第2の情報を用いて前記第1の情報を復元可能か否かを確認することで前記文書Mの正当性を検証する署名検証部と、を備え、前記多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記署名取得部は、前記第2の情報を所定数ずつ取得し、前記署名検証部は、所定数ずつ取得される前記第2の情報を用いて逐次的に前記第1の情報を復元し、復元処理に不要な前記第2の情報を不要になった段階で消去する、署名検証装置が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm、署名鍵s∈Kn、及び文書Mに基づいて生成された第1の情報と、前記文書M、前記多次多変数多項式の組F、及びベクトルy=f1s,...,fmsに基づいて前記第1の情報が前記署名鍵sを用いて生成されたことを検証するために必要な複数の第2の情報と、を含む電子署名を取得するステップと、前記電子署名に含まれる複数の第2の情報を用いて前記第1の情報を復元可能か否かを確認することで前記文書Mの正当性を検証するステップと、を含み、前記多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記取得するステップでは、前記第2の情報を所定数ずつ取得し、前記検証するステップでは、所定数ずつ取得される前記第2の情報を用いて逐次的に前記第1の情報を復元し、復元処理に不要な前記第2の情報を不要になった段階で消去する、署名検証方法が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm、署名鍵s∈Kn、及び文書Mに基づいて生成された第1の情報と、前記文書M、前記多次多変数多項式の組F、及びベクトルy=f1s,...,fmsに基づいて前記第1の情報が前記署名鍵sを用いて生成されたことを検証するために必要な複数の第2の情報と、を含む電子署名を取得する署名取得機能と、前記電子署名に含まれる複数の第2の情報を用いて前記第1の情報を復元可能か否かを確認することで前記文書Mの正当性を検証する署名検証機能と、をコンピュータに実現させるためのプログラムであり、前記多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記署名取得機能は、前記第2の情報を所定数ずつ取得し、前記署名検証機能は、所定数ずつ取得される前記第2の情報を用いて逐次的に前記第1の情報を復元し、復元処理に不要な前記第2の情報を不要になった段階で消去する、プログラムが提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm、署名鍵s∈Kn、及び文書Mに基づいて生成された第1の情報と、前記文書M、前記多次多変数多項式の組F、及びベクトルy=f1s,...,fmsに基づいて前記第1の情報が前記署名鍵sを用いて生成されたことを検証するために必要な複数の第2の情報と、を含む電子署名を取得する署名取得機能と、前記電子署名に含まれる複数の第2の情報を用いて前記第1の情報を復元可能か否かを確認することで前記文書Mの正当性を検証する署名検証機能と、をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、前記多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記署名取得機能は、前記第2の情報を所定数ずつ取得し、前記署名検証機能は、所定数ずつ取得される前記第2の情報を用いて逐次的に前記第1の情報を復元し、復元処理に不要な前記第2の情報を不要になった段階で消去する、記録媒体が提供される。以上説明したように本技術によれば、効率的に解く手段トラップドアが知られていない多次多変数連立方程式を用いて高い安全性を有する効率的な電子署名方式の署名検証を少ないメモリで実現することが可能になる。以下に添付図面を参照しながら、本技術の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。[説明の流れについて]ここで、以下に記載する本技術の実施形態に関する説明の流れについて簡単に述べる。まず、図1を参照しながら、公開鍵認証方式のアルゴリズム構成について説明する。次いで、図2を参照しながら、電子署名方式のアルゴリズム構成について説明する。次いで、図3を参照しながら、nパスの公開鍵認証方式について説明する。次いで、図4及び図5を参照しながら、3パスの公開鍵認証方式に係るアルゴリズムの構成例について説明する。次いで、図6及び図7を参照しながら、5パスの公開鍵認証方式に係るアルゴリズムの構成例について説明する。次いで、図8及び図9を参照しながら、3パス及び5パスの公開鍵認証方式に係る効率的なアルゴリズムを電子署名方式のアルゴリズムに変形する方法について説明する。次いで、図10~図14を参照しながら、本実施形態に係る電子署名方式のアルゴリズムを実行する際に署名検証に要するメモリ量を削減する方法について説明する。次いで、図15~図19を参照しながら、2進乱数から3進乱数を効率的に抽出する方法について説明する。次いで、図20及び図21を参照しながら、多変数多項式の係数を効率的に代入する方法について説明する。次いで、図22を参照しながら、本技術の実施形態に係る各アルゴリズムを実現することが可能な情報処理装置のハードウェア構成例について説明する。最後に、本実施形態の技術的思想について纏め、当該技術的思想から得られる作用効果について簡単に説明する。説明項目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:3パス方式に基づく電子署名方式への適用例5-3:5パス方式に基づく電子署名方式への適用例6:2進数の乱数列から3進数の乱数列を抽出する方法について6-1:抽出方法12ビット区切り6-2:抽出方法2区切りなし6-3:抽出方法3kビット区切り6-3-1:基本構成6-3-2:追加抽出方法7:多変数多項式の係数を効率的に代入する方法について7-1:基本的な取り決め7-2:データの構造化7-2-1:構造化手法17-2-2:構造化手法27-2-3:構造化手法38:ハードウェア構成例9:まとめ<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は、ハッシュ値d←Ht11,e11,...,t1N,e1Nを計算する。そして、証明者アルゴリズムPは、ハッシュ値dを検証者アルゴリズムVに送る。工程4:ハッシュ値dを受け取った検証者アルゴリズム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,t0i,e0i,c1iを生成する。ChBi=1の場合、証明者アルゴリズムPは、返答Rspi=r1i,t1i,e1i,c0iを生成する。工程5で生成された返答Rspii=1~Nは、検証者アルゴリズムVに送られる。工程6:返答Rspii=1~Nを受け取った検証者アルゴリズムVは、受け取った返答Rspii=1~Nを利用して以下の処理1及び処理2を実行する。処理1:ChBi=0の場合、検証者アルゴリズムVは、r0i,t0i,e0i,c1i←Rspiを実行する。そして、検証者アルゴリズムVは、c0i=Hr0i,t0i,e0iを計算する。さらに、検証者アルゴリズムVは、t1i←ChAir0it0i、及びe1i←ChAiFr0i-e0iを計算する。そして、検証者アルゴリズムVは、c0i,c1i,t1i,e1iを保持する。処理2:ChBi=1の場合、検証者アルゴリズムVは、r1i,t1i,e1i,c0i←Rspiを実行する。そして、検証者アルゴリズムVは、c1i=Hr1i,ChAiy-Fr1i-Gt1i,r1i-e1iを計算する。そして、検証者アルゴリズムVは、c0i,c1i,t1i,e1iを保持する。i=1~Nについて処理1及び処理2を実行した後、検証者アルゴリズムVは、Cmt=Hc01,c11,...,c0N,c1Nの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、d=Ht11,e11,...,t1N,e1Nの等号が成り立つか否かを検証する。そして、検証者アルゴリズム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を生成する処理、及びd=Ht11,e11,...,t1N,e1Nを生成する処理で構成される。工程3で証明者アルゴリズムPにより生成されたdは、検証者アルゴリズム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,t11,e11,...,t1N,e1Nを再生する処理と、再生したc01,c11,...,c0N,c1Nを用いてCmt=Hc01,c11,...,c0N,c1Nを検証する処理と、d=Ht11,e11,...,t1N,e1Nを検証する処理とで構成される。上記の工程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を生成する。さらに、署名生成アルゴリズムSigは、d=Ht11,e11,...,t1N,e1Nを算出する。処理5:署名生成アルゴリズムSigは、ChB1,...,ChBN←HM,Cmt,ChA1,...,ChAN,dを計算する。なお、ChB1,...,ChBN←HChA1,...,ChAN,dと変形してもよい。処理6:署名生成アルゴリズムSigは、Rspi←SelectChBi,ai,biを計算する。処理7:署名生成アルゴリズムSigは、Cmt,d,Rsp1,...,RspNを電子署名に設定する。署名検証アルゴリズムVer次に、署名検証アルゴリズムVerの構成について述べる。署名検証アルゴリズムVerは、以下の処理1~処理4で構成される。処理1:署名検証アルゴリズムVerは、ChA1,...,ChAN←HM,Cmtを計算する。処理2:署名検証アルゴリズムVerは、ChB1,...,ChBN←HM,Cmt,ChA1,...,ChAN,dを計算する。なお、署名検証アルゴリズムVerが実行する処理5において、ChB1,...,ChBN←HChA1,...,ChAN,dと変形した場合、署名検証アルゴリズムVerは、ChB1,...,ChBN←HChA1,...,ChAN,dを計算する。処理3:署名検証アルゴリズムVerは、ChA1,...,ChAN,ChB1,...,ChBN,Rsp1,...,RspNを用いてt11,e11,...,t1N,e1N,c01,c11,...,c0N,c1Nを生成する。処理4:署名検証アルゴリズムVerは、再生したc01,c11,...,c0N,c1Nを用いてCmt=Hc01,c11,...,c0N,c1N及びd=Ht11,e11,...,t1N,e1N,を検証する。以上説明したように、公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させることで、公開鍵認証方式のアルゴリズムを電子署名方式のアルゴリズムへと変形することが可能になる。<5:署名検証に要するメモリ量の削減方法について>ところで、上述した電子署名方式のアルゴリズムにおいては、署名検証アルゴリズムVerが電子署名全体を受信した後で署名検証の処理を実行していた。しかし、上述した電子署名方式の場合、電子署名のデータサイズが比較的大きい。そのため、RFIDRadioFrequencyIDentificationなど、少ないメモリ容量しか持たないデバイスを用いて認証を行う場合には、メモリの空き容量や認証処理中のメモリ使用率などに気を配る必要があった。また、十分なメモリ容量を持たないデバイスを利用する場合、認証を行うことができない場合も想定される。そこで、本件発明者は、署名検証に要するメモリ量の削減方法を考案した。[5-1:ハッシュ関数の構造について図10]まず、本件発明者は、ハッシュ関数の構造に注目した。多くの場合、ハッシュ関数は、入力をブロック単位に区切り、ブロック単位で順次処理を進める構造を有している。例えば、SHA-1の場合、ハッシュ関数は、図10に示すような構造を有している。図10に示すハッシュ関数は、パディング済みの入力MをZ個のブロックm1,...,mZに区切り、インデックスjをインクリメントしながら、逐次的に、ブロックmjを初期値IV又は中間値CVjと共に所定の関数CFに作用させてハッシュ値を生成する。従って、中間値CVjが得られた時点で、それ以前に利用したブロックは不要になる。そこで、この特性を利用し、アルゴリズムの実行に必要なメモリ量を効果的に削減する仕組み以下、メモリ削減方法を考案した。以下、この仕組みを上述した電子署名方式に適用する方法について説明する。[5-2:3パス方式に基づく電子署名方式への適用例図12]まず、図8に示した3パス方式に基づく電子署名方式のアルゴリズムに上記のメモリ削減方法を適用する方法について説明する。通常の実装方法:図11通常、上述した電子署名方式に係る署名検証アルゴリズムVerは、図11に示すように、電子署名を構成するCmt,Rsp1,...,RspNを1度に受信するS101。次いで、署名検証アルゴリズムVerは、Ch1,...,ChN←HM,Cmtを実行するS102。次いで、署名検証アルゴリズムVerは、c01,c11,c21,...,c0N,c1N,c2N←ReproduceCh1,...,ChN;Rsp1,...,RspNを実行するS103。次いで、署名検証アルゴリズムVerは、Cmt=Hc01,c11,c21,...,c0N,c1N,c2Nを検証しS104、署名検証に係る一連の処理を終了する。メモリ削減方法:図12通常の実装方法の場合、図11のステップS101のように、一度に電子署名を受信すると、ステップS103の処理が完了するまでRsp1,...,RspNを保持しておくためのメモリが必要になる。しかし、図5のアルゴリズム構成から分かるように、ステップS103で実行するc0i,c1i,c2iの再生にはChi;Rspi以外の情報を利用しない。また、図10に示したハッシュ関数の構造を考慮すると、ステップS104において実行されるハッシュ関数の計算はブロック単位で分割して実行できることが分かる。そこで、署名検証に係る処理の構成を図12に示すような構成に改良する。図12に示す構成の場合、署名検証アルゴリズムVerは、まず、電子署名に含まれるCmtだけを受信するS111。次いで、署名検証アルゴリズムVerは、Ch1,...,ChN←HM,Cmtを実行するS112。次いで、署名検証アルゴリズムVerは、i=1~Nについて、iをインクリメントさせながら逐次的にステップS113~S115の処理を実行する。ステップS113において、署名検証アルゴリズムVerは、Rspiを受信するS113。次いで、署名検証アルゴリズムVerは、受信したRspiを用いて、c0i,c1i,c2i←ReproduceChi;Rspiを実行するS114。ステップS114の処理を実行した後、Chi及びRspiは不要になる。そこで、署名検証アルゴリズムVerは、ステップS114の処理を実行後にChi及びRspiをメモリから消去する。次いで、署名検証アルゴリズムVerは、tmpi←Hitmpi-1;c0i,c1i,c2iを実行するS115。なお、関数Hiは、ハッシュ関数Hの内部でc0i,c1i,c2iまで計算した際に生成される中間値を出力する関数である。実際には選択したハッシュ関数に応じて関数Hiの入力サイズは異なるため必要に応じて、ビットを付加するなどの適切な入力長の補正が行われる。関数Hiを用いると、ハッシュ関数Hは、以下に示す処理1~処理3で構成されたアルゴリズムにより表現される。そして、tmpNがハッシュ関数Hの最終的な出力ハッシュ値となる。実際にはハッシュ関数の仕様に応じて、最終処理においてパディングの追加処理を行う。処理1:tmp0←空文字列処理2:fori=1toNtmpi←Hitmpi-1;c0i,c1i,c2iendfor処理3:outputtmpNi=1~Nについて、ステップS113~S115の処理を実行した後、署名検証アルゴリズムVerは、Cmt=tmpNが成り立つか否かを検証しS116、署名検証に係る一連の処理を終了する。上記のように、署名検証アルゴリズムVerは、ステップS113~S115の処理を繰り返し実行する過程で不要になった情報をメモリかた消去する。そのため、署名検証に要するメモリ量は最小限に抑えられる。その結果、少ないメモリ容量しか持たないデバイスでも、上記の署名検証が可能になる。[5-3:5パス方式に基づく電子署名方式への適用例図14]次に、図9に示した5パス方式に基づく電子署名方式のアルゴリズムに上記のメモリ削減方法を適用する方法について説明する。通常の実装方法:図13通常、上述した電子署名方式に係る署名検証アルゴリズムVerは、図13に示すように、電子署名を構成するCmt,d,Rsp1,...,RspNを1度に受信するS121。次いで、署名検証アルゴリズムVerは、ChA1,...,ChAN←HM,Cmtを実行するS122。次いで、署名検証アルゴリズムVerは、ChB1,...,ChBN←HM,Cmt,ChA1,...,ChAN,dを実行するS123。次いで、署名検証アルゴリズムVerは、c01,c11,...,c0N,c1N,d11,e11,...,d1N,e1N←ReproduceChA1,...,ChAN,ChB1,...,ChBN;Rsp1,...,RspNを実行するS124。次いで、署名検証アルゴリズムVerは、Cmt=Hc01,c11,...,c0N,c1Nとd=Hを検証しS125、署名検証に係る一連の処理を終了する。メモリ削減方法:図14図13のステップS121のように、一度に電子署名を受信すると、ステップS124の処理が完了するまでRsp1,...,RspNを保持しておくためのメモリが必要になる。しかしながら、図7のアルゴリズム構成から分かるように、ステップS124で実行するc0i,c1i,d1i,e1iの再生にはChAi,ChBi;Rspi以外の情報を利用しない。また、図10に示したハッシュ関数の構造を考慮すると、ステップS125において実行されるハッシュ関数の計算はブロック単位で分割して実行できることが分かる。そこで、署名検証に係る処理の構成を図14に示すような構成に改良する。図14に示す構成の場合、署名検証アルゴリズムVerは、まず、電子署名に含まれるCmtだけを受信するS131。次いで、署名検証アルゴリズムVerは、ChA1,...,ChAN←HM,Cmtを実行するS132。次いで、署名検証アルゴリズムVerは、dを受信するS133。次いで、署名検証アルゴリズムVerは、受信したdを用いて、ChB1,...,ChBN←HM,Cmt,ChA1,...,ChAN,dを実行するS134。ステップS134の処理を実行した後、dは不要になる。そこで、署名検証アルゴリズムVerは、ステップS134の処理を実行後にdをメモリから消去する。次いで、署名検証アルゴリズムVerは、i=1~Nについて、iをインクリメントさせながら逐次的にステップS135~S137の処理を実行する。ステップS135において、署名検証アルゴリズムVerは、Rspiを受信するS135。次いで、署名検証アルゴリズムVerは、受信したRspiを用いて、c0i,c1i,t1i,e1i←ReproduceChAi,ChBi,Rspiを実行するS136。ステップS136の処理を実行した後、ChAi、ChBi及びRspiは不要になる。そこで、署名検証アルゴリズムVerは、ステップS136の処理を実行後にChAi、ChBi及びRspiをメモリから消去する。次いで、署名検証アルゴリズムVerは、tmpi←Hitmpi-1;c0i,c1iとtmpi’←Hitmpi-1’;t1i,e1iを実行するS137。i=1~Nについて、ステップS135~S137の処理を実行した後、署名検証アルゴリズムVerは、Cmt=tmpNとd=tmpN’が成り立つか否かを検証しS138、署名検証に係る一連の処理を終了する。上記のように、署名検証アルゴリズムVerは、ステップS135~S137の処理を繰り返し実行する過程で不要になった情報をメモリから消去する。そのため、署名検証に要するメモリ量は最小限に抑えられる。その結果、少ないメモリ容量しか持たないデバイスでも、上記の署名検証が可能になる。以上、署名検証に要するメモリ量の削減方法について説明した。<6:2進数の乱数列から3進数の乱数列を抽出する方法について>ところで、3パス方式に基づく公開鍵認証方式のアルゴリズムにおいて、3進数の一様乱数をN個以上生成する場面が存在する。しかし、3進数の一様乱数を生成する優れた乱数生成器は一般的ではない。そのため、2進数の一様乱数を生成する優れた乱数生成器を用いて3進数の一様乱数を生成する方法を考える必要がある。そこで、本件発明者は、2進数の一様乱数から3進数の一様乱数を効率的に生成する方法を考案した。以下、この方法について詳細に説明する。なお、以下の説明において、l進表現lは2又は3で表された1つの数を1シンボルと数えることにする。[6-1:抽出方法12ビット区切り図15]まず、図15を参照しながら、Mビットの2進数を2ビットずつ区切って3進数を抽出する方法以下、抽出方法1を紹介する。図15に示すように、2進表現の乱数列を2ビットずつ区切ると、M/2個の2ビットの乱数が得られる。例えば、00を3進数の0、01を3進数の1、10を3進数の2に対応付けると、2ビット単位の2進表現の乱数列から3進数の乱数列を得ることができる。但し、2ビットの値11は除外する。つまり、抽出方法1は、2進数2シンボルで表現される22通りの数の中から、3進数1シンボルで表現される31通りの数を抽出する方法である。従って、N個以上の3進数が抽出できない確率P1は、下記の式13のようになる。[6-2:抽出方法2区切りなし図16]次に、図16を参照しながら、2進数Mシンボルの乱数を区切らずに利用して3進数Lシンボルの乱数を抽出する方法以下、抽出方法2を紹介する。但し、Lは、3L≦2Mとなる最大の整数である。2進数Mシンボルで表現可能な数は、2M通り存在する。一方、3進数Lシンボルで表現可能な数は、3L通りしか存在しない。そのため、2進数Mシンボルで表現される2M通りの数のうち、2M-3L通りの数は、3進表現の乱数として利用されない。従って、N個以上の3進数が抽出できない確率P2は、下記の式14のようになる。[6-3:抽出方法3kビット区切り図17]上記の抽出方法1は、最小の区切り単位で2進表現の乱数列を区切る方法である。一方、上記の抽出方法2は、Mビット区切りと考えられるため最大の区切り単位で2進表現の乱数列を区切る方法である。上記の式13及び式14から分かるように、区切る長さに応じて、N個以上の3進数が抽出できない確率は異なる。因みに、図17に示すように、kビット単位で2進Mシンボルの乱数列を区切った場合、N個以上の3進数が抽出できない確率P3は、下記の式15のようになる。N個以上の3進数が抽出できない確率P3を最小化することができれば、最も効率よく3進表現の乱数列を抽出できることになる。例えば、M=512、N=140の場合、k=8のときに確率P3が最小となる。6-3-1:基本構成図18ここで、図18を参照しながら、2進Mシンボルの乱数列から3進Lシンボルの乱数列を抽出する処理の流れについて説明する。図18に示すように、まず、2進Mシンボルの乱数列が生成されるS201。次いで、2進Mシンボルの乱数列が、kビット単位に区切られるS202。次いで、kビット単位で区切られたビット列X2kのうち、X2k≦3Lとなるビット列が抽出されるS203。次いで、抽出されたビット列が、3進数表現で出力されS204、一連の処理が終了する。6-3-2:追加抽出方法図19上記の式15で表現される確率P3が最小となる区切りの長さkを算出し、図18に示したアルゴリズムを実行することにより、2進表現の乱数列から3進表現の乱数列を効率的に抽出することが可能になる。しかし、本件発明者は、図18のステップS204においてX2k>3Lとなるビット列が利用されない点に注目し、3進表現の乱数列をより効率的に抽出する方法を考案した。以下、この方法について、図19を参照しながら説明する。この方法は、図18のステップS204で抽出されなかったビット列を利用して、3進表現のシンボル列を抽出する方法である。図19に示すように、まず、図18のステップS204で抽出されなかった、X2k>3Lとなるビット列の組例えば、ビット列の組をy1y2...yN’と表現すると、個々のビット列yiは3L≦yi<2kが抽出されるS211。次いで、抽出したビット列yiからそれぞれ3Lが減算され、新たなビット列の組例えば、新たなビット列の組をz1z2...zN’と表現すると、個々のビット列zi=yi-3Lは0≦zi<2k-3Lが算出されるS212。次いで、新たなビット列の組から、ビット列XがX<3L’となるものが抽出されるS213。但し、L’は、3L’≦2k-3Lとなる最大の整数である。次いで、ステップS213で抽出されたビット列が3進表現で出力されS214、一連の処理が終了する。このアルゴリズムを適用することにより、確率3L’/2k-3Lで新たにL’個の3進数を抽出することが可能になる。なお、この方法を再帰的に用いることで、さらに多くの3進数を抽出することができる。つまり、ステップS213でビット列XがX≧3L’となったビット列から同様にして3進数を抽出することができる。以上、2進数の一様乱数から3進数の一様乱数を効率的に生成する方法について説明した。<7:多変数多項式の係数を効率的に代入する方法について>さて、これまでは多変数多項式を証明者又は署名者と検証者との間で共有する方法について具体的に明示してこなかった。多変数多項式を共有する方法としては、多変数多項式の係数乱数を生成する際に用いるシードを両者で共有する方法が考えられる。しかしながら、共有しているシードを利用して生成した乱数を係数に当てはめる順序を両者で共有しない限り、多変数多項式を共有したことにはならない。[7-1:基本的な取り決め]そこで、証明者又は署名者と検証者との間で、共有しているシードを用いて生成した乱数列を、どの順序で多変数多項式に当てはめるかについて基本的な取り決めを行う。そして、多変数多項式を利用する際に、この基本的な取り決めに従って乱数列を多変数多項式に当てはめる。このような方法を用いれば、証明者又は署名者と検証者との間で多変数多項式を共有したことになる。[7-2:データの構造化]但し、多変数多項式を構成する係数の数は膨大である。1つの係数が1ビット単位で表現されている場合、多変数多項式を表現するのに最低でも数万ビット以上のデータが必要になる。そのため、数を多変数多項式の係数に代入する処理の負荷は非常に高い。そこで、本件発明者は、多変数多項式の係数を所定の単位で構造化し、係数への代入処理を効率化する手法構造化手法1及び2を考案した。さらに、本件発明者は、同じ多変数多項式の係数に対して複数回の代入処理を実行する場合に、その処理効率を向上させる手法構造化手法3を考案した。以下、これらの手法について詳細に説明する。7-2-1:構造化手法1図20まず、構造化手法1について説明する。構造化手法1は、図20に示すように、多変数多項式を構成する同じ種類の項の係数を1つのデータ構造として纏める手法である。図20の例では、係数a1IJ~amIJがデータ構造Aとして纏められ、係数b1I~bmIがデータ構造Bとして纏められている。構造化手法1を適用しない場合、m本のn変数多項式に対する係数の代入は、次のようなアルゴリズム例1により行われる。例1の場合、1ビットのAND演算を2×N×N-1×M/2回実行する必要がある。さらに、1ビットのXOR演算^をN×N-1×M/2回実行する必要がある。例1forL=1toMforI=1toNforJ=ItoN[fのLビット目]^=[aIJL][xのIビット目][xのJビット目];endforendforendforoutputf;一方、図20に示すように係数を構造化し、生成した乱数を多変数多項式の係数として一部ずつ逐次適用していく場合、係数の代入アルゴリズムは例2のようになる。例2の場合、LビットのAND演算を2×N×N-1/2回、MビットのXOR演算^をN×N-1/2回実行するだけで済む。なお、aIJ1~Mは、それぞれループのタイミングで生成される。また、係数を使い回してもよい。例えば、NN-1/2回のループを実行する際、[aIJ1~M]を毎回生成せず、L回に1回だけ生成するようにしてもよい。また、M回のループ中、[aIJ1~M]を1ビットずつローテーションしながら利用してもよい。例2forI=1toNforJ=ItoN[fの1~Mビット目]^=[aIJ1~M][xのIビット目][xのJビット目];endforendforoutputf;また、図20に示すように係数を構造化し、多変数多項式の係数を適用した中間の結果をテーブルに保持するようにしてもよい。この場合、係数の代入アルゴリズムは例3のようになる。なお、配列aIJ[0][0]~aIJ[2k-1][2k-1]には、それぞれ、aIJ[x1,...,xk][z1,...,zk]=akI-11kJ-11x1z1^...^akI-11kJ-1kx1zk^...^akI-1kkJ-11xkz1^...^akI-1kkJ-1kxkzkが格納されている。例3の場合、LビットのXOR演算^をN/kN/k-1/2回実行するだけで済む。但し、例2のアルゴリズムに比べると、必要なメモリ量は、22k/k2倍となる。例えば、k=1のとき、LビットXOR演算が120119/2=7140回、必要なメモリ量が例2の22=4倍、ループ回数は変化なしとなる。また、k=2のとき、LビットXOR演算が6059/2=1770回、必要なメモリ量が24/4=4倍、ループ回数が1/4となる。k=4のとき、LビットXOR演算が3029/2=435回、必要なメモリ量が28/42=16倍、ループ回数が1/16.4となる。k=6のとき、LビットXOR演算が2019/2=190回、必要なメモリ量が212/62=114倍、ループ回数が1/37.6となる。k=8のとき、LビットXOR演算が1514/2=135回、必要なメモリが216/82=1024倍、ループ回数が1/52.9となる。例3forI=1toN/kforJ=ItoN/k[fの1~Mビット目]^=aIJ1~M[xのkI-11~kビット目][xのkJ-11~kビット目];endforendforoutputf;以上、構造化手法1に係る具体的な係数の代入アルゴリズムについて説明した。かかる構成により、アルゴリズムを実行する際に処理の高速化が期待できる。7-2-2:構造化手法2図21次に、構造化手法2について説明する。構造化手法2は、図21に示すように、多変数多項式を2次形式で表現し、2次形式の行又は列を1つのデータ構造として纏める手法である。図21の例では、行方向にデータ構造が纏められている。図21に示すように係数を構造化し、生成した乱数を多変数多項式の係数として一部ずつ逐次適用していく場合、係数の代入アルゴリズムは例4のようになる。例4の場合、NビットのAND演算をN1×M回、NビットのXOR演算^をN×M回、関数Qの演算をM回実行するだけで済む。例4forI=1toNT^=AI[xのIビット目];endforT=x;outputQT;Qz{z=z^z>>1;z=z^z>>2;z=z^z>>4;z=z^z>>8;z=z^z>>2LogN;returnz1;}また、図21に示すように係数を構造化し、多変数多項式の係数を適用した中間の結果をテーブルに保持するようにしてもよい。この場合、係数の代入アルゴリズムは例5のようになる。なお、配列AI[0]~AI[2k-1]には、それぞれ、AI[x1,...,xk]=AkI-11x1^...^AkI-1kxkが格納されている。例5の場合、NビットのXOR演算^をN/k×M、Nビットの関数Qの演算をM回実行するだけで済む。但し、例4のアルゴリズムに比べると、必要なメモリ量は、2k/k倍となる。例えば、k=1のとき、NビットXOR演算が120回、必要なメモリ量が例4の2倍、ループ回数は変化なしとなる。また、k=4のとき、NビットXOR演算が30回、必要なメモリ量が24/4=4倍、ループ回数が1/4となる。k=8のとき、NビットXOR演算が15回、必要なメモリが28/8=32倍、ループ回数が1/8となる。k=16のとき、NビットXOR演算が8回、必要なメモリが216/16=4096倍、ループ回数が1/15となる。例5forI=1toN/kT^=AI[xのkI-11~kI-1kビット目];endforT=x;outputQT;以上、構造化手法2に係る具体的な係数の代入アルゴリズムについて説明した。かかる構成により、アルゴリズムを実行する際に処理の高速化が期待できる。7-2-3:構造化手法3次に、構造化手法3について説明する。構造化手法3は、同じ多変数多項式にN回N≧2代入処理を行なう場合に、乱数から多項式をN回生成して代入処理を行うのではなく、係数を一部生成し、その部分に関するN回分の処理を行なう部分を単位とする逐次的な処理をN回分並列して行なうという手法である。この手法を適用すると、乱数生成のコストが無視できない場合にN回分の処理全体でのスループットが改善される。例えば、図5に示したアルゴリズムでは、工程1において引数を更新しながら多変数多項式F及びGの計算をN回繰り返し実行している。そこで、このような計算部分について、同じ係数を利用して繰り返し演算を行うように構成する。上記例2のアルゴリズムを用いて多変数多項式Fr0ii=1~Nを計算する場合、一度生成した[aIJL]について、N個のr0iを全て適用した後で、次の[aIJL]に関する処理を実行するように構成する。このように構成すると、同じ係数[aIJL]をN回生成せずに済むようになる。以上、構造化手法3に係る具体的な係数の代入アルゴリズムについて説明した。かかる構成により、N回分の処理におけるトータルでのスループットが改善される。<8:ハードウェア構成例図22>上記の各アルゴリズムは、例えば、図22に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図22に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、PHS、PDA等の携帯情報端末、ゲーム機、接触式又は非接触式のICチップ、接触式又は非接触式のICカード、又は種々の情報家電がこれに含まれる。但し、上記のPHSは、PersonalHandy-phoneSystemの略である。また、上記のPDAは、PersonalDigitalAssistantの略である。図22に示すように、このハードウェアは、主に、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の略である。<9:まとめ>最後に、本技術の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、PC、携帯電話、ゲーム機、情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置に対して適用することができる。なお、以下で述べる情報処理装置の機能は、1台の情報処理装置を利用して実現することも可能であるし、複数台の情報処理装置を利用して実現することも可能である。また、以下で述べる情報処理装置が処理を実行する際に用いるデータ記憶手段及び演算処理手段は、当該情報処理装置に設けられたものであってもよいし、ネットワークを介して接続された機器に設けられたものであってもよい。上記の情報処理装置の機能構成は以下のように表現される。例えば、下記1に記載の情報処理装置は、多次多変数連立方程式の求解困難性に安全性の根拠を置く効率的な公開鍵認証方式又は電子署名方式のアルゴリズムを実行する機能を有する。1環K上で定義される多次多変数多項式の組F=f1,...,fm、署名鍵s∈Kn、及び文書Mに基づいて生成された第1の情報と、前記文書M、前記多次多変数多項式の組F、及びベクトルy=f1s,...,fmsに基づいて前記第1の情報が前記署名鍵sを用いて生成されたことを検証するために必要な複数の第2の情報と、を含む電子署名を取得する署名取得部と、前記電子署名に含まれる複数の第2の情報を用いて前記第1の情報を復元可能か否かを確認することで前記文書Mの正当性を検証する署名検証部と、を備え、前記多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記署名取得部は、前記第2の情報を所定数ずつ取得し、前記署名検証部は、所定数ずつ取得される前記第2の情報を用いて逐次的に前記第1の情報を復元し、復元処理に不要な前記第2の情報を不要になった段階で消去する、署名検証装置。2前記第1の情報は、入力される情報をブロック単位に区切って処理する一方向性関数を用いて生成されており、前記署名検証部は、前記所定数ずつ取得される前記第2の情報を用いて前記ブロック単位の処理で前記一方向性関数が出力する中間値を生成する処理、当該中間値及び次に取得される所定数の前記第2の情報を用いて次の中間値を生成する処理を繰り返し実行して前記第1の情報を復元する、上記1に記載の署名検証装置。3所定数の前記第2の情報は、前記中間値の生成が完了した段階で消去される、上記2に記載の署名検証装置。4前記所定数は1であり、前記第2の情報に含まれ、かつ、前記一方向性関数から前記中間値を生成する際に用いる情報のサイズは、前記ブロック単位のデータサイズ以上である、上記2又は3に記載の署名検証装置。5環K上で定義される多次多変数多項式の組F=f1,...,fm、署名鍵s∈Kn、及び文書Mに基づいて生成された第1の情報と、前記文書M、前記多次多変数多項式の組F、及びベクトルy=f1s,...,fmsに基づいて前記第1の情報が前記署名鍵sを用いて生成されたことを検証するために必要な複数の第2の情報と、を含む電子署名を取得するステップと、前記電子署名に含まれる複数の第2の情報を用いて前記第1の情報を復元可能か否かを確認することで前記文書Mの正当性を検証するステップと、を含み、前記多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記取得するステップでは、前記第2の情報を所定数ずつ取得し、前記検証するステップでは、所定数ずつ取得される前記第2の情報を用いて逐次的に前記第1の情報を復元し、復元処理に不要な前記第2の情報を不要になった段階で消去する、署名検証方法。6環K上で定義される多次多変数多項式の組F=f1,...,fm、署名鍵s∈Kn、及び文書Mに基づいて生成された第1の情報と、前記文書M、前記多次多変数多項式の組F、及びベクトルy=f1s,...,fmsに基づいて前記第1の情報が前記署名鍵sを用いて生成されたことを検証するために必要な複数の第2の情報と、を含む電子署名を取得する署名取得機能と、前記電子署名に含まれる複数の第2の情報を用いて前記第1の情報を復元可能か否かを確認することで前記文書Mの正当性を検証する署名検証機能と、をコンピュータに実現させるためのプログラムであり、前記多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記署名取得機能は、前記第2の情報を所定数ずつ取得し、前記署名検証機能は、所定数ずつ取得される前記第2の情報を用いて逐次的に前記第1の情報を復元し、復元処理に不要な前記第2の情報を不要になった段階で消去する、プログラム。7環K上で定義される多次多変数多項式の組F=f1,...,fm、署名鍵s∈Kn、及び文書Mに基づいて生成された第1の情報と、前記文書M、前記多次多変数多項式の組F、及びベクトルy=f1s,...,fmsに基づいて前記第1の情報が前記署名鍵sを用いて生成されたことを検証するために必要な複数の第2の情報と、を含む電子署名を取得する署名取得機能と、前記電子署名に含まれる複数の第2の情報を用いて前記第1の情報を復元可能か否かを確認することで前記文書Mの正当性を検証する署名検証機能と、をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、前記多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記署名取得機能は、前記第2の情報を所定数ずつ取得し、前記署名検証機能は、所定数ずつ取得される前記第2の情報を用いて逐次的に前記第1の情報を復元し、復元処理に不要な前記第2の情報を不要になった段階で消去する、記録媒体。備考上記の署名検証アルゴリズムVerは、署名取得部、署名検証部の一例である。以上、添付図面を参照しながら本技術の好適な実施形態について説明したが、本技術は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本技術の技術的範囲に属するものと了解される。上記の説明において、ハッシュ関数Hを用いるアルゴリズムを紹介したが、ハッシュ関数Hの代わりにコミットメント関数COMを用いてもよい。コミットメント関数COMは、文字列S及び乱数ρを引数にとる関数である。コミットメント関数の例としては、ShaiHaleviとSilvioMicaliによって国際会議CRYPTO1996で発表された方式などがある。"