"環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、情報処理装置。前記メッセージ生成部は、N回分N≧2のメッセージを生成し、前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、請求項1に記載の情報処理装置。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、情報処理装置。前記メッセージ取得部は、N回分N≧2の前記メッセージを1回の対話で取得し、前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、請求項3に記載の情報処理装置。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、前記検証者に前記第3の情報を提供する中間情報提供部と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、情報処理装置。前記メッセージ生成部は、N回分N≧2のメッセージを生成し、前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、前記中間情報生成部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した前記第1の情報及び前記メッセージを生成する際に得られるN回分の前記第2の情報を用いてN回分の前記第3の情報を生成し、前記中間情報提供部は、N回分の前記第3の情報を1回の対話で検証者に提供し、前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、請求項5に記載の情報処理装置。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供部と、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得部と、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、情報処理装置。前記メッセージ取得部は、N回分N≧2の前記メッセージを1回の対話で取得し、前記情報提供部は、N回分の前記メッセージのそれぞれについて前記第1の情報をランダムに選択し、選択したN回分の前記第1の情報を1回の対話で前記証明者に提供し、前記中間情報取得部は、N回分の前記第1の情報及びN回分の前記メッセージを生成する際に得られるN回分の前記第2の情報を用いて前記証明者が生成したN回分の前記第3の情報を取得し、前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、請求項7に記載の情報処理装置。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、文書M及び前記メッセージを一方向性関数に入力して得られる数値に基づき、k通りk≧3の検証パターンの中から1つの検証パターンを選択するパターン選択部と、選択した前記検証パターンに対応する回答情報を生成する回答生成部と、署名として、前記メッセージ及び前記回答情報を前記検証者に提供する署名提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、署名生成装置。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、情報処理方法。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報処理装置が、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、情報処理方法。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、前記検証者に前記第3の情報を提供するステップと、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、情報処理方法。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報処理装置が、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供するステップと、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得するステップと、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、情報処理方法。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、文書M及び前記メッセージを一方向性関数に入力して得られる数値に基づき、k通りk≧3の検証パターンの中から1つの検証パターンを選択するステップと、選択した前記検証パターンに対応する回答情報を生成するステップと、署名として、前記メッセージ及び前記回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、署名生成方法。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、プログラム。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持機能と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得機能と、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するパターン情報提供機能と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得機能と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、プログラム。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成機能と、前記検証者に前記第3の情報を提供する中間情報提供機能と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、プログラム。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持機能と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得機能と、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供機能と、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得機能と、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供機能と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得機能と、前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、プログラム。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、文書M及び前記メッセージを一方向性関数に入力して得られる数値に基づき、k通りk≧3の検証パターンの中から1つの検証パターンを選択するパターン選択機能と、選択した前記検証パターンに対応する回答情報を生成する回答生成機能と、署名として、前記メッセージ及び前記回答情報を前記検証者に提供する署名提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、プログラム。上記の通り、多変数多項式問題は、量子コンピュータを用いても解くことが困難な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は公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、情報処理装置が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、情報処理装置が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、前記検証者に前記第3の情報を提供する中間情報提供部と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、情報処理装置が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供部と、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得部と、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、情報処理装置が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、文書M及び前記メッセージを一方向性関数に入力して得られる数値に基づき、k通りk≧3の検証パターンの中から1つの検証パターンを選択するパターン選択部と、選択した前記検証パターンに対応する回答情報を生成する回答生成部と、署名として、前記メッセージ及び前記回答情報を前記検証者に提供する署名提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、署名生成装置が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、情報処理方法が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報処理装置が、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、情報処理方法が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、前記検証者に前記第3の情報を提供するステップと、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、情報処理方法が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報処理装置が、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供するステップと、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得するステップと、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、情報処理方法が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、文書M及び前記メッセージを一方向性関数に入力して得られる数値に基づき、k通りk≧3の検証パターンの中から1つの検証パターンを選択するステップと、選択した前記検証パターンに対応する回答情報を生成するステップと、署名として、前記メッセージ及び前記回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、署名生成方法が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、プログラムが提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持機能と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得機能と、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するパターン情報提供機能と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得機能と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、プログラムが提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成機能と、前記検証者に前記第3の情報を提供する中間情報提供機能と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、プログラムが提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持機能と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得機能と、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供機能と、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得機能と、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供機能と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得機能と、前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、プログラムが提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、文書M及び前記メッセージを一方向性関数に入力して得られる数値に基づき、k通りk≧3の検証パターンの中から1つの検証パターンを選択するパターン選択機能と、選択した前記検証パターンに対応する回答情報を生成する回答生成機能と、署名として、前記メッセージ及び前記回答情報を前記検証者に提供する署名提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、プログラムが提供される。また、本技術の別の観点によれば、上記のプログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。以上説明したように本技術によれば、効率的に解く手段トラップドアが知られていない多次多変数連立方程式を用いて、高い安全性を有する効率的な公開鍵認証方式又は電子署名方式を実現することが可能になる。以下に添付図面を参照しながら、本技術の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。[説明の流れについて]ここで、以下に記載する本技術の実施形態に関する説明の流れについて簡単に述べる。まず、図1を参照しながら、公開鍵認証方式のアルゴリズム構成について説明する。次いで、図2を参照しながら、電子署名方式のアルゴリズム構成について説明する。次いで、図3を参照しながら、nパスの公開鍵認証方式について説明する。次いで、図4~図8を参照しながら、3パスの公開鍵認証方式に係るアルゴリズムの構成例について説明する。次いで、図5~図17を参照しながら、5パスの公開鍵認証方式に係るアルゴリズムの構成例について説明する。次いで、図18~図21を参照しながら、3パス及び5パスの公開鍵認証方式に係る効率的なアルゴリズムを電子署名方式のアルゴリズムに変形する方法について説明する。次いで、図22~図27を参照しながら、3パス及び5パスの公開鍵認証方式に係る効率的なアルゴリズムの並直列構成及び直並列構成について説明する。次いで、図28を参照しながら、本技術の第1及び第2実施形態に係る各アルゴリズムを実現することが可能な情報処理装置のハードウェア構成例について説明する。最後に、本実施形態の技術的思想について纏め、当該技術的思想から得られる作用効果について簡単に説明する。説明項目1:はじめに1-1:公開鍵認証方式のアルゴリズム1-2:電子署名方式のアルゴリズム1-3:nパスの公開鍵認証方式2:3パスの公開鍵認証方式に係るアルゴリズムの構成2-1:具体的なアルゴリズムの構成例2-2:2次多変数多項式に基づく効率的なアルゴリズム2-2-1:基本構成2-2-2:並列化アルゴリズム2-3:高次多変数多項式に基づく効率的なアルゴリズム方式12-3-1:基本構成2-3-2:並列化アルゴリズム3:5パスの公開鍵認証方式に係るアルゴリズムの構成3-1:具体的なアルゴリズムの構成例3-2:2次多変数多項式に基づく効率的なアルゴリズム3-2-1:基本構成3-2-2:並列化アルゴリズム3-3:高次多変数多項式に基づく効率的なアルゴリズム実施例13-3-1:基本構成3-3-2:並列化アルゴリズム3-4:高次多変数多項式に基づく効率的なアルゴリズム実施例23-4-1:基本構成3-4-2:並列化アルゴリズム構成例13-4-3:並列化アルゴリズム構成例2:高効率3-4-4:並列化アルゴリズム構成例2:更に高効率4:電子署名方式への変形4-1:3パスの公開鍵認証方式から電子署名方式への変形4-1-1:電子署名アルゴリズム構成例14-1-2:電子署名アルゴリズム構成例2:高効率4-2:5パスの公開鍵認証方式から電子署名方式への変形4-2-1:電子署名アルゴリズム構成例14-2-2:電子署名アルゴリズム構成例2:高効率5:ハイブリッド型アルゴリズム5-1:3パスの公開鍵認証方式に係るハイブリッド型アルゴリズム5-1-1:並直列アルゴリズム5-1-2:直並列アルゴリズム5-2:5パスの公開鍵認証方式に係るハイブリッド型アルゴリズム5-2-1:並直列アルゴリズム構成例15-2-2:並直列アルゴリズム構成例25-2-3:直並列アルゴリズム構成例15-2-4:直並列アルゴリズム構成例26:補遺6-1:システムパラメータの設定方法6-2:イレギュラーな要求に対する応答方法6-2-1:証明者による応答方法について6-2-2:検証者による応答方法について7:ハードウェア構成例8:まとめ<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を実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図28に示した通りである。つまり、鍵生成アルゴリズム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を実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図28に示した通りである。つまり、鍵生成アルゴリズム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について処理工程kの実行及び情報Tkの送信が順次行われ、最後に処理工程n1が実行される。このように、情報がn回送受信される方式のことをnパスの公開鍵認証方式と呼ぶ。以上、nパスの公開鍵認証方式について説明した。<2:3パスの公開鍵認証方式に係るアルゴリズムの構成>以下、3パスの公開鍵認証方式に係るアルゴリズムについて説明する。なお、以下の説明において、3パスの公開鍵認証方式のことを3パス方式と呼ぶ場合がある。[2-1:具体的なアルゴリズムの構成例]まず、図4を参照しながら、3パス方式に係る具体的なアルゴリズムの構成例について紹介する。図4は、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を秘密鍵に設定する。なお、以下では、ベクトルx1,...,xnをxと表記し、多変数多項式の組f1x,...,fmxをFxと表記することにする。証明者アルゴリズムP、検証者アルゴリズムV次に、図4を参照しながら、対話プロトコルの中で証明者アルゴリズムPが実行する処理及び検証者アルゴリズムVが実行する処理について説明する。上記の対話プロトコルの中で、証明者は、秘密鍵sの情報を検証者に一切漏らさずに、自身がy=Fsを満たすsを知っていることを検証者に示す。一方、検証者は、証明者がy=Fsを満たすsを知っているか否かを検証する。なお、公開鍵pkは、検証者に公開されているものとする。また、秘密鍵sは、証明者により秘密に管理されているものとする。以下、図4に示したフローチャートに沿って説明を進める。工程1:まず、証明者アルゴリズムPは、任意に数seed0を選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器PRNGに数seed0を適用してベクトルr0∈Kn及び数seed1を生成する。つまり、証明者アルゴリズムPは、r0,seed1←PRNGseed0を計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器PRNGに数seed1を適用して多変数多項式F1x=f11x,...,f1mxを生成する。つまり、証明者アルゴリズムPは、F1←PRNGseed1を計算する。工程1続き:次いで、証明者アルゴリズムPは、r1←s-r0を計算する。この計算は、秘密鍵sをベクトルr0によりマスクする操作に相当する。さらに、証明者アルゴリズムPは、F2x←Fxr0F1xを計算する。この計算は、xに関して多変数多項式Fxr0を多変数多項式F1xによりマスクする操作に相当する。工程1続き:次いで、証明者アルゴリズムPは、F1r1及びr1のハッシュ値c0を生成する。つまり、証明者アルゴリズムPは、c0←HF1r1,r1を計算する。また、証明者アルゴリズムPは、数seed1のハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←Hseed1を計算する。さらに、証明者アルゴリズムPは、多変数多項式F2のハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←HF2を計算する。このハッシュ値c0,c1,c2は、メッセージとして検証者アルゴリズムVに送られる。このとき、sに関する情報、r0に関する情報、r1に関する情報が検証者に一切漏れない点に注意されたい。工程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=seed0を生成する。Ch=1の場合、証明者アルゴリズムPは、返答Rsp=seed1,r1を生成する。Ch=2の場合、証明者アルゴリズムPは、返答Rsp=F2,r1を生成する。工程3で生成された返答Rspは、検証者アルゴリズムVに送られる。このとき、Ch=0の場合にはr1に関する情報が検証者に一切漏れておらず、Ch=1又は2の場合にはr0に関する情報が検証者に一切漏れない点に注意されたい。工程4:返答Rspを受け取った検証者アルゴリズムVは、受け取った返答Rspを利用して以下の検証処理を実行する。Ch=0の場合、検証者アルゴリズムVは、r0,seed1←PRNGRspを計算する。さらに、検証者アルゴリズムVは、F1←PRNGseed1を計算する。そして、検証者アルゴリズムVは、c1=Hseed1の等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c2=HFxr0F1xの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。Ch=1の場合、検証者アルゴリズムVは、seed1,r1←Rspとする。さらに、検証者アルゴリズムVは、F1←PRNGseed1を計算する。そして、検証者アルゴリズムVは、c0=HF1r1,r1の等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c1=Hseed1の等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。Ch=2の場合、検証者アルゴリズムVは、F2,r1←Rspとする。そして、検証者アルゴリズムVは、c0=HF2r1-y,r1の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c2=HF2の等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。健全性についてここで、3パス方式に係るアルゴリズムの健全性について説明を補足する。3パス方式に係るアルゴリズムの健全性は、検証者アルゴリズムVが選択可能な要求Ch=0,1,2の全てについて、証明者アルゴリズムPが正しい返答Rspを返したならば、下記の式6及び式7を満たすF2、F1、r0、r1が計算可能になるという論理に基づいて保証されている。上記の健全性が保証されることにより、多次多変数連立方程式の求解問題を解かない限りにおいて2/3より高い確率で偽証が成功することは不可能であると保証される。つまり、検証者の要求Ch=0,1,2の全てに正しく回答するためには、偽証者が上記の式6及び式7を満たすF2、F1、r0、r1を計算できる必要がある。言い換えると、偽証者はFs=yを満たすsを計算できる必要がある。但し、検証者の要求Ch=0,1,2の高々2つについて偽証者が正しく回答できてしまう可能性は残る。そのため、偽証の成功確率は2/3となる。なお、上記の対話プロトコルを十分な回数だけ繰り返し実行することで、偽証の成功確率は無視できるほど小さくなる。ハッシュ関数Hについてここで、ハッシュ関数Hについて説明を補足する。上記のアルゴリズムでは、ハッシュ関数Hを用いてc0,c1,c2などを計算しているが、ハッシュ関数Hの代わりにコミットメント関数COMを用いてもよい。コミットメント関数COMは、文字列S及び乱数ρを引数にとる関数である。コミットメント関数の例としては、ShaiHaleviとSilvioMicaliによって国際会議CRYPTO1996で発表された方式などがある。例えば、コミットメント関数COMを用いてc0,c1,c2を計算する場合について考えてみよう。この場合、c0,c1,c2を計算する前に乱数ρ0,ρ1,ρ2を用意し、ハッシュ関数Hを適用する代わりにコミットメント関数COM,ρ0,COM,ρ1,COM,ρ2を適用してc0,c1,c2を生成する。また、検証者がciを生成するために必要なρiは、返答Rspに含めて送られるようにする。以上、3パス方式に係る具体的なアルゴリズムの構成例について紹介した。[2-2:2次多変数多項式に基づく効率的なアルゴリズム]次に、3パス方式に係るアルゴリズムを効率化する方法について述べる。ここでは、多変数多項式Fとして2次多項式の組f1x,...,fmxを利用する場合について説明する。但し、2次多項式fixは、下記の式8のように表現されるものとする。なお、2次多項式の組f1x,...,fmxは、下記の式9のように表現することができる。但し、x=x1,...,xnである。また、A1,...,Amは、n×n行列である。さらに、b1,...,bmはそれぞれn×1ベクトルである。この表現を用いると、多変数多項式Fは、下記の式10及び式11のように表現することができる。この表現が成り立つことは、下記の式12から容易に確認することができる。このようにFxyをxに依存する第1の部分と、yに依存する第2の部分と、x及びyの両方に依存する第3の部分とに分けたとき、第3の部分に対応する項Gx,yは、x及びyについて双線形になる。この性質を利用すると、効率的なアルゴリズムを構築することが可能になる。例えば、ベクトルt0∈Kn、e0∈Kmを用いて、多変数多項式Fxrのマスクに利用する多変数多項式F1xをF1x=Gx,t0e0と表現する。この場合、多変数多項式Fxr0とGxとの和は、下記の式13のように表現される。ここで、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の情報を一切知ることはできない。従って、零知識性が担保される。以下、図5及び図6を参照しながら、3パス方式に係る効率的なアルゴリズムについて説明する。2-2-1:基本構成図5まず、図5を参照しながら、3パス方式に係る効率的なアルゴリズムの基本構成について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。工程1:図5に示すように、証明者アルゴリズム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-2:並列化アルゴリズム図6次に、図6を参照しながら、図5に示した効率的なアルゴリズムを並列化する方法について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。先に述べた通り、上記の対話プロトコルを適用すれば、偽証が成功する確率を2/3以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を2/32以下に抑制することができる。さらに、この対話プロトコルをN回実行すると、偽証が成功する確率は2/3Nとなり、Nを十分に大きい数例えば、N=140にすれば、偽証が成功する確率は無視できる程度に小さくなる。対話プロトコルを複数回実行する方法としては、例えば、メッセージ、要求、返答のやり取りを逐次的に複数回繰り返す直列的な方法と、1回分のやり取りで複数回分のメッセージ、要求、返答のやり取りを行う並列的な方法とが考えられる。ここでは、3パス方式に係る上記の対話プロトコルを並列的に実行するアルゴリズム以下、並列化アルゴリズムについて説明する。工程1:証明者アルゴリズム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,Gr1i,t0ie0iを計算する。さらに、検証者アルゴリズム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パス方式に係る効率的な並列化アルゴリズムの構成例について説明した。なお、図6に示した並列化アルゴリズムには、メッセージをハッシュ値に変換してから送信する工夫を盛り込んだ。この工夫により、通信効率が向上する。同様に、要求Ch1,...,ChNや返答Rsp1,...,RspNをハッシュ値に変換してから送信するように構成を変形してもよい。このように構成を変形することで、更なる通信効率の向上が期待できる。[2-3:高次多変数多項式に基づく効率的なアルゴリズム方式1]上記の効率的なアルゴリズムは、上記の式8で定義される2次多項式fiの組で多変数多項式Fを表現することにより、上記の式10で定義される多項式Gが双線形になるという性質を利用していた。しかし、多項式Gが加法準同型であれば、多項式Gが双線形でなくとも、同様に効率的なアルゴリズムを構築することが可能である。2次多項式fiを利用した効率的なアルゴリズムの構築について多項式Gが加法準同型の場合、変数r0,r1,t0,e0を用いて、下記の式14~式16の関係が成り立つ。なお、下記の式14は、秘密鍵sをs=r0r1と分割し、公開鍵Fsを展開したものである。下記の式14~式16は、r0,t1,e1で再現可能な第1の部分と、r1,t0,e0で再現可能な第2の部分と、r1,t1,e1で再現可能な第3の部分とに分けることができる。例えば、下記の式15に含まれるr0,t1、下記の式16に含まれるFr0,e1は、第1の部分である。また、下記の式14に含まれるe0,Gt0,r1、下記の式15に含まれるt0、下記の式16に含まれるe0は、第2の部分である。さらに、下記の式14に含まれるe1,Fr1,Gt1,r1は、第3の部分である。言い換えると、下記の式14は第2及び第3の部分で構成され、下記の式15は第1及び第2の部分で構成され、下記の式16は第1及び第2の部分で構成されている。上記の通り、下記の式14~式16は、それぞれ2種類の部分で構成されている。また、秘密鍵sの定義及び下記の式14~式16の関係から、r0,t1,e1、r1,t0,e0、r1,t1,e1のいずれか1つを用いても秘密鍵sは得られないことが保証される。これらの性質を利用すると、例えば、図5に示した3パス方式に係る効率的なアルゴリズムを構築することができる。3次多項式flを利用した効率的なアルゴリズムの構築について2次多項式fiを利用する場合に関する上記の考察を発展させ、下記の式17で表現される環R上の3次多項式flを利用した効率的なアルゴリズムの構築方法について検討してみたい。3次多項式flの組で表現される多変数多項式F=f1,...,fmは、下記の式18の関係を満たす。但し、Gxx,yは、xに関して1次となる項を表す。また、Gyx,yは、yに関して1次となる項を表す。Gx=gx1,...,gxm、Gy=gy1,...,gymと表現すると、gxl及びgylは、それぞれ下記の式19及び式20のように展開することができる。但し、gxlの右辺第2項は、x及びyのいずれに関しても1次であるため、gylに含めてもよい。上記の式19及び式20から分かるように、Gxx,y及びGyx,yは、x及びyについて加法準同型になっている。そこで、これらの性質を利用し、2次多項式fiを利用した効率的なアルゴリズムの構築方法と同様に、新たな変数r0,r1,t0,u0,e0を導入して公開鍵Fsを分割する。多項式Gx,Gyが加法準同型であるから、変数r0,r1,t0,u0,e0を用いて、下記の式21~式24の関係が成り立つ。下記の式21~式24は、r0,t0,u0,e0で再現可能な第1の部分と、r0,u1,e1で再現可能な第2の部分と、r1,t0,e0で再現可能な第3の部分と、r1,t1,u1,e1で再現可能な第4の部分と、に分けることができる。例えば、下記の式22に含まれるr0,t0、下記の式23に含まれるu0、下記の式24に含まれるFr0,Gyr0,u0,e0、は、第1の部分である。また、下記の式24に含まれるGyr0,u1,e1は、第2の部分である。さらに、下記の式21に含まれるe0,Gxr0,r1は、第3の部分である。そして、下記の式21に含まれるe1,Fr1,Gxt1,r1、下記の式22に含まれるt1、下記の式23に含まれるu1は、第4の部分である。言い換えると、下記の式21は第3及び第4の部分で構成され、下記の式22及び下記の式23は第1及び第4の部分で構成され、下記の式24は第1及び第2の部分で構成されている。このように、下記の式21~式24は、それぞれ2種類の部分で構成されている。また、秘密鍵sの定義及び下記の式21~式24の関係から、r0,t0,u0,e0、r0,u1,e1、r1,t0,e0、r1,t1,u1,e1のいずれか1つを用いても秘密鍵sは得られないことが保証される。これらの性質を利用すると、例えば、環R上の3次多項式flを利用した3パス方式に係る効率的なアルゴリズム以下、拡張アルゴリズムを構築することができる。以下、具体的な拡張アルゴリズムの構成例について説明する。拡張アルゴリズムの設計に関する基本的なポイントは、下記の式25~式27で表現されるメッセージを検証者に送ること、及び第1~第4の部分のいずれかに関する検証を行うことの2点である。但し、この検証だけでは、第3の部分に含まれるr1と第4の部分に含まれるr1とが等しいかを検証することができない。同様に、第1の部分に含まれるr0と第2の部分に含まれるr0とが等しいか、第1の部分に含まれるt0,e0と第3の部分に含まれるt0,e0とが等しいかも検証することができない。さらに、第2の部分に含まれるu1,e1と第4の部分に含まれるu1,e1とが等しいかも検証することができない。そこで、以下では、これらの検証も可能にした構成例を紹介する。2-3-1:基本構成図7まず、図7を参照しながら、3パス方式に係る拡張アルゴリズムの基本構成について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。工程1:図7に示すように、証明者アルゴリズムPは、ランダムにベクトルr0,t0,u0∈Kn及びe0∈Kmを生成する。次いで、証明者アルゴリズムPは、r1←s-r0を計算する。この計算は、秘密鍵sをベクトルr0によりマスクする操作に相当する。次いで、証明者アルゴリズムPは、t1←r0-t0を計算する。次いで、証明者アルゴリズムPは、u1←r1-u0を計算する。次いで、証明者アルゴリズムPは、e1←Fr0-e0を計算する。工程1続き:次いで、証明者アルゴリズムPは、c0←Hr1,Gxt0,r1e0を計算する。次いで、証明者アルゴリズムPは、c1←Hr0-t0,u0を計算する。次いで、証明者アルゴリズムPは、c2←Hr0,e1-Gyr0,u1を計算する。次いで、証明者アルゴリズムPは、c3←Ht0,e0を計算する。次いで、証明者アルゴリズムPは、c4←Hu1,e1を計算する。工程1で生成されたメッセージc0,c1,c2,c3,c4は、検証者アルゴリズムVに送られる。工程2:メッセージc0,c1,c2,c3,c4を受け取った検証者アルゴリズムVは、4つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す4つの数値{0,1,2,3}の中から1つの数値を選択し、選択した数値を要求Chに設定する。この要求Chは証明者アルゴリズムPに送られる。工程3:要求Chを受け取った証明者アルゴリズムPは、受け取った要求Chに応じて検証者アルゴリズムVに送る返答Rspを生成する。Ch=0の場合、証明者アルゴリズムPは、返答Rsp=r0,t0,u0,e0を生成する。Ch=1の場合、証明者アルゴリズムPは、返答Rsp=r0,u1,e1を生成する。Ch=2の場合、証明者アルゴリズムPは、返答Rsp=r1,t0,e0を生成する。Ch=3の場合、証明者アルゴリズムPは、返答Rsp=r1,t1,u1,e1を生成する。工程3で生成された返答Rspは、検証者アルゴリズムVに送られる。工程4:返答Rspを受け取った検証者アルゴリズムVは、受け取った返答Rspを利用して以下の検証処理を実行する。Ch=0の場合、検証者アルゴリズムVは、c1=Hr0-t0,u0の等号が成り立つか否かを検証する。次いで、検証者アルゴリズムVは、c2=Hr0,Fr0Gyr0,u0-e0の等号が成り立つか否かを検証する。次いで、検証者アルゴリズムVは、c3=Ht0,e0の等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。Ch=1の場合、検証者アルゴリズムVは、c2=Hr0,e1-Gyr0,u1の等号が成り立つか否かを検証する。次いで、検証者アルゴリズムVは、c4=Hu1,e1の等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。Ch=2の場合、検証者アルゴリズムVは、c0=Hr1,e0Gxt0,r1の等号が成り立つか否かを検証する。次いで、検証者アルゴリズムVは、c3=Ht0,e0の等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。Ch=3の場合、検証者アルゴリズムVは、c0=Hr1,y-Fr1-e1-Gxt1,r1の等号が成り立つか否かを検証する。次いで、検証者アルゴリズムVは、c1=Ht1,r1-u1の等号が成り立つか否かを検証する。次いで、検証者アルゴリズムVは、c4=Hu1,e1の等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、3パス方式に係る拡張アルゴリズムの構成例について説明した。このアルゴリズムを利用することにより、通信に必要なデータサイズが大幅に削減される。また、3次多項式を利用していることにより、より高い安全性が実現されている。2-3-2:並列化アルゴリズム図8次に、図8を参照しながら、3パス方式に係る拡張アルゴリズムの並列化について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。工程1:図8に示すように、証明者アルゴリズムPは、i=1~Nについて、以下の処理を実行する。まず、証明者アルゴリズムPは、ランダムにベクトルr0i,t0i,u0i∈Kn及びe0i∈Kmを生成する。次いで、証明者アルゴリズムPは、r1i←s-r0iを計算する。この計算は、秘密鍵sをベクトルr0iによりマスクする操作に相当する。次いで、証明者アルゴリズムPは、t1i←r0i-t0iを計算する。次いで、証明者アルゴリズムPは、u1i←r1i-u0iを計算する。次いで、証明者アルゴリズムPは、e1i←Fr0i-e0iを計算する。工程1続き:次いで、証明者アルゴリズムPは、c0i←Hr1i,Gxt0i,r1ie0iを計算する。次いで、証明者アルゴリズムPは、c1i←Hr0i-t0i,u0iを計算する。次いで、証明者アルゴリズムPは、c2i←Hr0i,e1i-Gyr0i,u1iを計算する。次いで、証明者アルゴリズムPは、c3i←Ht0i,e0iを計算する。次いで、証明者アルゴリズムPは、c4i←Hu1i,e1iを計算する。c01,c11,c21,c31,c41,...,c0N,c1N,c2N,c3N,c4Nを生成した後、証明者アルゴリズムPは、ハッシュ値Cmt←Hc01,c11,c21,c31,c41,...,c0N,c1N,c2N,c3N,c4Nを計算する。工程1で生成されたハッシュ値Cmtは、検証者アルゴリズムVに送られる。工程2:ハッシュ値Cmtを受け取った検証者アルゴリズムVは、i=1~Nのそれぞれについて、4つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、i=1~Nのそれぞれについて、検証パターンの種類を表す4つの数値{0,1,2,3}の中から1つの数値を選択し、選択した数値を要求Chiに設定する。要求Chii=1~Nは証明者アルゴリズムPに送られる。工程3:要求Chii=1~Nを受け取った証明者アルゴリズムPは、i=1~Nについて、受け取った要求Chiに応じて検証者アルゴリズムVに送る返答Rspiを生成する。Chi=0の場合、証明者アルゴリズムPは、返答Rspi=r0i,t0i,u0i,e0i,c0i,c4iを生成する。Chi=1の場合、証明者アルゴリズムPは、返答Rspi=r0i,u1i,e1i,c0i,c1i,c3iを生成する。Chi=2の場合、証明者アルゴリズムPは、返答Rspi=r1i,t0i,e0i,c1i,c2i,c4iを生成する。Chi=3の場合、証明者アルゴリズムPは、返答Rspi=r1i,t1i,u1i,e1i,c2i,c3iを生成する。工程3で生成された返答Rspii=1~Nは、検証者アルゴリズムVに送られる。工程4:返答Rspii=1~Nを受け取った検証者アルゴリズムVは、受け取った返答Rspiを利用し、i=1~Nについて以下の処理を実行する。Chi=0の場合、検証者アルゴリズムVは、c1i=Hr0i-t0i,u0iを計算する。次いで、検証者アルゴリズムVは、c2i=Hr0i,Fr0iGyr0i,u0i-e0iを計算する。次いで、検証者アルゴリズムVは、c3i=Ht0i,e0iを計算する。そして、検証者アルゴリズムVは、c0i,c1i,c2i,c3i,c4iを保持する。Chi=1の場合、検証者アルゴリズムVは、c2i=Hr0i,e1i-Gyr0i,u1iを計算する。次いで、検証者アルゴリズムVは、c4i=Hu1i,e1iを計算する。そして、検証者アルゴリズムVは、c0i,c1i,c2i,c3i,c4iを保持する。Chi=2の場合、検証者アルゴリズムVは、c0i=Hr1i,Gxt0i,r1ie0iを計算する。次いで、検証者アルゴリズムVは、c3i=Ht0i,e0iを計算する。そして、検証者アルゴリズムVは、c0i,c1i,c2i,c3i,c4iを保持する。Chi=3の場合、検証者アルゴリズムVは、c0i=Hr1i,y-Fr1i-e1i-Gxt1i,r1iを計算する。次いで、検証者アルゴリズムVは、c1i=Ht1i,r1i-u1iを計算する。次いで、検証者アルゴリズムVは、c4i=Hu1i,e1iを計算する。そして、検証者アルゴリズムVは、c0i,c1i,c2i,c3i,c4iを保持する。i=1~Nについて上記の処理を実行した後、検証者アルゴリズムVは、Cmt=Hc01,c11,c21,c31,c41,...,c0N,c1N,c2N,c3N,c4Nの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、3パス方式に係る拡張アルゴリズムの並列化について説明した。このアルゴリズムを利用することにより、通信に必要なデータサイズが大幅に削減される。また、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:具体的なアルゴリズムの構成例図9]まず、図9を参照しながら、5パス方式に係る具体的なアルゴリズムの構成例について紹介する。図9は、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次に、図9を参照しながら、対話プロトコルの中で証明者アルゴリズムP及び検証者アルゴリズムVにより実行される処理について説明する。工程1:図9に示すように、証明者アルゴリズムPは、ランダムに数seed0を選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器PRNGに数seed0を適用してベクトルr0∈Kn、及び多変数多項式の組F1x=f11x,...,f1mxを生成する。つまり、証明者アルゴリズムPは、r0,F1←Gseed0を計算する。次いで、証明者アルゴリズムPは、r1←s-r0を計算する。この計算は、秘密鍵sをベクトルr0によりマスクする操作に相当する。工程1続き:次いで、証明者アルゴリズムPは、F1r1及びr1のハッシュ値c0を生成する。つまり、証明者アルゴリズムPは、c0←HF1r1,r1を計算する。また、証明者アルゴリズムPは、数seed0のハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←Hseed0を計算する。工程1で生成されたメッセージc0,c1は、検証者アルゴリズムVに送られる。工程2:メッセージc0,c1を受け取った検証者アルゴリズムVは、q通り存在する環Kの元からランダムに1つの数ChAを選択し、選択した数ChAを証明者アルゴリズムPに送る。工程3:数ChAを受け取った証明者アルゴリズムPは、F2x←ChAFxr0F1xを計算する。この計算は、xに関して多変数多項式Fxr0を多変数多項式F1xによりマスクする操作に相当する。工程3で生成された多変数多項式F2は、検証者アルゴリズムVに送られる。工程4:多変数多項式F2を受け取った検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求ChBに設定する。この要求ChBは証明者アルゴリズムPに送られる。工程5:要求ChBを受け取った証明者アルゴリズムPは、受け取った要求ChBに応じて検証者アルゴリズムVに送り返す返答Rspを生成する。ChB=0の場合、証明者アルゴリズムPは、返答Rsp=seed0を生成する。ChB=1の場合、証明者アルゴリズムPは、返答Rsp=r1を生成する。工程5で生成された返答Rspは、検証者アルゴリズムVに送られる。工程6:返答Rspを受け取った検証者アルゴリズムVは、受け取った返答Rspを利用して以下の検証処理を実行する。ChB=0の場合、検証者アルゴリズムVは、r0,F1←PRNGRspを計算する。そして、検証者アルゴリズムVは、c1=HRspの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、F2x=ChAFxr0F1xの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。ChB=1の場合、検証者アルゴリズムVは、r1←Rspとする。そして、検証者アルゴリズムVは、c0=HF2r1-ChAy,r1の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。健全性について5パス方式の健全性は、証明者アルゴリズムPがc0,c1、及び、検証者アルゴリズムVが選択する2通りのChA,ChA’について、要求ChB=0及び1に正しく回答した場合に、その回答内容から下記の式28~式30を満たすF1、F2、F2’、r0、r1を計算できるということから保証されている。5パス方式の健全性が保証されることにより、多次多変数連立方程式の求解問題を解かない限りにおいて1/21/qより高い確率で偽証することは不可能であることが保証される。つまり、検証者の要求ChA=0及び1の全てに正しく回答するためには、偽証者が上記の式28~式30を満たすF1、F2、F2’、r0、r1を計算できる必要がある。言い換えると、偽証者はFs=yを満たすsを計算できる必要がある。従って、多次多変数連立方程式の求解問題を解かない限り、偽証者は、1/21/qより高い確率で偽証を成功させることができないのである。なお、上記の対話プロトコルを十分に多くの回数実行することにより、偽証の成功確率を無視できるほど小さくすることができる。ハッシュ関数Hについてここで、ハッシュ関数Hについて説明を補足する。上記のアルゴリズムでは、ハッシュ関数Hを用いてc0,c1などを計算しているが、ハッシュ関数Hの代わりにコミットメント関数COMを用いてもよい。コミットメント関数COMは、文字列S及び乱数ρを引数にとる関数である。コミットメント関数の例としては、ShaiHaleviとSilvioMicaliによって国際会議CRYPTO1996で発表された方式などがある。例えば、コミットメント関数COMを用いてc0,c1を計算する場合について考えてみよう。この場合、c0,c1を計算する前に乱数ρ0,ρ1を用意し、ハッシュ関数Hを適用する代わりにコミットメント関数COM,ρ0,COM,ρ1を適用してc0,c1を生成する。また、検証者がciを生成するために必要なρiは、返答Rspに含めて送られるようにする。以上、5パス方式に係る具体的なアルゴリズムの構成例について説明した。[3-2:2次多変数多項式に基づく効率的なアルゴリズム]次に、5パス方式に係るアルゴリズムを効率化する方法について述べる。ここでは、多変数多項式Fとして2次多項式の組f1x,...,fmxを利用する場合について説明する。3パス方式の効率的なアルゴリズムと同様、2つのベクトルt0∈Kn、e0∈Kmを用いて、多変数多項式Fxr0をマスクするために用いた多変数多項式F1xをF1x=Gx、t0e0のように表現する。この表現を用いると、多変数多項式Fxr0について、下記の式31で表現される関係が得られる。そのため、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の情報を一切知ることはできない。従って、零知識性は担保される。以下、図10及び図11を参照しながら、5パス方式に係る効率的なアルゴリズムについて説明する。3-2-1:基本構成図10まず、図10を参照しながら、5パス方式に係る効率的なアルゴリズムの基本構成について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。工程1:図10に示すように、証明者アルゴリズム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-2:並列化アルゴリズム図11次に、図11を参照しながら、図10に示した効率的なアルゴリズムを並列化する方法について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。先に述べた通り、5パス方式に係る対話プロトコルを適用すれば、偽証が成功する確率を1/21/q以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を1/21/q2以下に抑制することができる。さらに、この対話プロトコルをN回実行すると、偽証が成功する確率は1/21/qNとなり、Nを十分に大きい数例えば、N=80にすれば、偽証が成功する確率は無視できる程度に小さくなる。対話プロトコルを複数回実行する方法としては、例えば、メッセージ、要求、返答のやり取りを逐次的に複数回繰り返す直列的な方法と、1回分のやり取りで複数回分のメッセージ、要求、返答のやり取りを行う並列的な方法とが考えられる。ここでは、5パス方式に係る上記の対話プロトコルを並列的に実行するアルゴリズム以下、並列化アルゴリズムについて説明する。工程1:証明者アルゴリズム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パス方式に係る効率的な並列化アルゴリズムの構成例について説明した。なお、図11に示した並列化アルゴリズムには、メッセージをハッシュ値に変換してから送信する工夫を盛り込んだ。この工夫により、通信効率が向上する。同様に、要求ChA1,...,ChAN,ChB1,...,ChBNや返答Rsp1,...,RspNなどをハッシュ値に変換してから送信するように構成を変形してもよい。このように構成を変形することで、更なる通信効率の向上が期待できる。[3-3:高次多変数多項式に基づく効率的なアルゴリズム方式1]上記の効率的なアルゴリズムは、上記の式8で定義される2次多項式fiの組で多変数多項式Fを表現することにより、上記の式10で定義される多項式Gが双線形になるという性質を利用していた。但し、図10に示した効率的なアルゴリズムは、公開鍵FsをChA倍した項がChAに依存する部分と、それ以外の部分とに分割できることを利用している。しかし、5パス方式の場合も多項式Gがxかyの少なくとも片方について線形であれば、多項式Gが双線形でなくとも、同様に効率的なアルゴリズムを構築することが可能である。3次多項式fiを利用した効率的なアルゴリズムの構築について3パス方式の場合と同様、環R上の3次多項式flを利用した効率的なアルゴリズムの構築方法について検討してみたい。3次多項式flを上記の式17のように表現した場合に、Gxx,y及びGyx,yがx及びyについて線形になることについては式19と式20より分かる。そこで、上記の性質を利用し、新たな変数r0,r1,t0,u0,e0を導入して、公開鍵FsをChA倍した項を分割する。多項式Gx,Gyがそれぞれxとyについて線形であるから、変数r0,r1,t0,u0,e0を用いて、下記の式32~式35の関係が成り立つ。また、下記の式32~式35は、ChAに依存する第1の部分と、ChAに依存しない第2の部分とに分けることができる。但し、第1の部分は、r1,t1,u1,e1で再現可能である。また、第2の部分は、r0,t1,u1,e1で再現可能である。例えば、下記の式32に含まれるe0,Gxt0,r1、下記の式33に含まれるt0、下記の式34に含まれるu0、下記の式35に含まれるe0,Gyr0,u0は第1の部分である。一方、下記の式32に含まれるChAFr0r1,e1,ChAFr1,Gxt1,r1、下記の式33に含まれるChAr0,t1、下記の式34に含まれるChAr1,u1、下記の式35に含まれるChAFr0,Gyr0,u1,e1は第2の部分である。また、秘密鍵sの定義及び下記の式32~式35の関係から、r1,t1,u1,e1、r0,t1,u1,e1のいずれか1つを用いても秘密鍵sは得られないことが保証される。これらの性質を利用すると、例えば、環R上の3次多項式flを利用した5パス方式に係る効率的なアルゴリズム以下、拡張アルゴリズムを構築することができる。以下、具体的な拡張アルゴリズムの構成例について説明する。拡張アルゴリズムの設計に関する基本的なポイントは、下記の式36及び式37で表現されるメッセージを検証者に送ること、及び検証者が選択したChAについて、ChAに依存する部分第1の部分に関する検証を行うことの2点である。但し、メッセージを生成する際に利用したr0及びr1を、検証の際に別のr0及びr1にすり替えられることを防ぐために、r0及びr1に関する検証を追加した構成例を以下で紹介する。3-3-1:基本構成図12まず、図12を参照しながら、5パス方式に係る拡張アルゴリズムの基本構成について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。工程1:図12に示すように、証明者アルゴリズムPは、ランダムにベクトルr0,t0,u0∈Kn及びe0∈Kmを生成する。次いで、証明者アルゴリズムPは、r1←s-r0を計算する。この計算は、秘密鍵sをベクトルr0によりマスクする操作に相当する。次いで、証明者アルゴリズムPは、c0←Hr0,t0,e0-Gyr0,u0を計算する。次いで、証明者アルゴリズムPは、c1←Hr1,u0,Gxt0,r1e0を計算する。工程1で生成されたメッセージc0,c1は、検証者アルゴリズムVに送られる。工程2:メッセージc0,c1を受け取った検証者アルゴリズムVは、ランダムに数ChAを選択する。この数ChAは証明者アルゴリズムPに送られる。工程3:数ChAを受け取った証明者アルゴリズムPは、t1←ChAr0-t0を計算する。次いで、証明者アルゴリズムPは、u1←ChAr1-u0を計算する。次いで、証明者アルゴリズムPは、e1←ChAFr0ChAGyr0,r1-e0を計算する。工程3で生成されたt1,u1,e1は、検証者アルゴリズムVに送られる。工程4:t1,u1,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は、c0=Hr0,ChAr0-t1,ChAFr0Gyr0,u1-e1の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。ChB=1の場合、検証者アルゴリズムVは、c1=Hr1,ChAr1-u1,ChAy-Fr1-Gxt1,r1-e1の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、5パス方式に係る拡張アルゴリズムの構成例について説明した。このアルゴリズムを利用することにより、通信に必要なデータサイズが大幅に削減される。また、3次多項式を利用していることにより、より高い安全性が実現されている。3-3-2:並列化アルゴリズム図13次に、図13を参照しながら、5パス方式に係る拡張アルゴリズムの並列化について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。工程1:図13に示すように、証明者アルゴリズムPは、i=1~Nについて、次の処理を実行する。まず、証明者アルゴリズムPは、ランダムにベクトルr0i,t0i,u0i∈Kn及びe0i∈Kmを生成する。次いで、証明者アルゴリズムPは、r1i←s-r0iを計算する。この計算は、秘密鍵sをベクトルr0iによりマスクする操作に相当する。次いで、証明者アルゴリズムPは、c0i←Hr0i,t0i,e0i-Gyr0i,u0iを計算する。次いで、証明者アルゴリズムPは、c1i←Hr1i,u0i,Gxt0i,r1ie0iを計算する。工程1続き:c01,c11,...,c0N,c1Nを計算した後、証明者アルゴリズムPは、ハッシュ値Cmt←Hc01,c11,...,c0N,c1Nを計算する。工程1で生成されたハッシュ値Cmtは、検証者アルゴリズムVに送られる。工程2:ハッシュ値Cmtを受け取った検証者アルゴリズムVは、ランダムに数ChA1,...,ChANを選択する。数ChA1,...,ChANは証明者アルゴリズムPに送られる。工程3:数ChA1,...,ChANを受け取った証明者アルゴリズムPは、i=1~Nについて、次の処理を実行する。まず、証明者アルゴリズムPは、t1i←ChAir0i-t0iを計算する。次いで、証明者アルゴリズムPは、u1i←ChAir1i-u0iを計算する。次いで、証明者アルゴリズムPは、e1i←ChAiFr0iChAiGyr0i,r1i-e0iを計算する。工程3で生成されたt11,u11,e11,...,t1N,u1N,e1Nは、検証者アルゴリズムVに送られる。工程4:t11,u11,e11,...,t1N,u1N,e1Nを受け取った検証者アルゴリズムVは、i=1~Nのそれぞれについて、2つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、i=1~Nのそれぞれについて、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求ChBiに設定する。要求ChB1,...,ChBNは証明者アルゴリズムPに送られる。工程5:要求ChB1,...,ChBNを受け取った証明者アルゴリズムPは、i=1~Nのそれぞれについて、受け取った要求ChBiに応じて検証者アルゴリズムVに送る返答Rspiを生成する。ChBi=0の場合、証明者アルゴリズムPは、返答Rspi=r0i,c1iを生成する。ChBi=1の場合、証明者アルゴリズムPは、返答Rspi=r1i,c0iを生成する。工程5で生成された返答Rspiは、検証者アルゴリズムVに送られる。工程6:返答Rspii=1~Nを受け取った検証者アルゴリズムVは、受け取った返答Rspiを利用し、i=1~Nについて次の処理を実行する。ChBi=0の場合、検証者アルゴリズムVは、c0i=Hr0i,ChAir0i-t1i,ChAiFr0iGyr0i,u1i-e1iを計算する。そして、検証者アルゴリズムVは、c0i,c1iを保持する。ChBi=1の場合、検証者アルゴリズムVは、c1i=Hr1i,ChAir1i-u1i,ChAiy-Fr1i-Gxt1i,r1i-e1iを計算する。そして、検証者アルゴリズムVは、c0i,c1iを保持する。i=1~Nについて上記の処理を実行した後、検証者アルゴリズムVは、Cmt=Hc01,c11,...,c0N,c1Nの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、5パス方式に係る拡張アルゴリズムの並列化について説明した。このアルゴリズムを利用することにより、通信に必要なデータサイズが大幅に削減される。また、3次多項式を利用していることにより、より高い安全性が実現されている。[3-4:高次多変数多項式に基づく効率的なアルゴリズム方式2]これまで、環R上の3次多項式flを利用した効率的なアルゴリズムの構築方法について説明してきた。ここでは標数q及び位数qkの環R上で定義される高次多項式flを利用した拡張アルゴリズムの構築方法について考える。この高次多項式flは、例えば、下記の式38のように表現される。この高次多項式flを用いる場合、Gx,y=Fxy-Fx-Fy=g1,...,gmで定義される多項式Gの成分glは、下記の式39のように表現される。従って、ChA∈Rについて、下記の式40に示す関係が成り立つ。さらに、下記の式41に示す関係も成り立つ。そこで、これらの性質以下、準線形性と呼ぶ。を利用し、新たな変数r0,r1,t0z,e0を導入して、公開鍵FsをChA倍した項を分割する。多項式Gが準線形性を有することから、変数r0,r1,t0z,e0を用いて、下記の式42~式44の関係が成り立つ。また、下記の式42~式44は、ChAに依存する第1の部分と、ChAに依存しない第2の部分とに分けることができる。但し、第1の部分は、r1,t1z,e1で再現可能である。また、第2の部分は、r0,t1z,e1で再現可能である。例えば、下記の式42に含まれるe0,ΣGzt0z,r1、下記の式43に含まれるt0z、下記の式44に含まれるe0は第1の部分である。一方、下記の式42に含まれるChAFr0r1,e1,ChAFr1,ΣGzt1z,r1、下記の式43に含まれるChAq-zr0,t1z但し、qz=qz;以下同様、下記の式44に含まれるChAFr0,e1は第2の部分である。また、秘密鍵sの定義及び下記の式42~式44の関係から、r1,t1z,e1、r0,t1z,e1のいずれか1つを用いても秘密鍵sは得られないことが保証される。これらの性質を利用すると、例えば、環R上の高次多項式flを利用した5パス方式に係る効率的なアルゴリズム以下、高次拡張アルゴリズムを構築することができる。以下、具体的な高次拡張アルゴリズムの構成例について説明する。高次拡張アルゴリズムの設計に関する基本的なポイントは、下記の式45及び式46で表現されるメッセージを検証者に送ること、及び検証者が選択したChAについて、ChAに依存する部分第1の部分に関する検証を行うことの2点である。但し、メッセージを生成する際に利用したr0及びr1を、検証の際に別のr0及びr1にすり替えられることを防ぐために、r0及びr1に関する検証を追加した構成例を以下で紹介する。3-4-1:基本構成図14まず、図14を参照しながら、5パス方式に係る高次拡張アルゴリズムの基本構成について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。工程1:図14に示すように、証明者アルゴリズムPは、ランダムにベクトルr0,t01,...,t0k∈Kn及びe0∈Kmを生成する。次いで、証明者アルゴリズムPは、r1←s-r0を計算する。この計算は、秘密鍵sをベクトルr0によりマスクする操作に相当する。次いで、証明者アルゴリズムPは、c0←Hr0,t01,...,t0k,e0を計算する。次いで、証明者アルゴリズムPは、c1←Hr1,ΣzGzt0z,r1e0但し、Σzはz=1~kについての和を表す。を計算する。工程1で生成されたメッセージc0,c1は、検証者アルゴリズムVに送られる。工程2:メッセージc0,c1を受け取った検証者アルゴリズムVは、ランダムに数ChAを選択する。この数ChAは証明者アルゴリズムPに送られる。工程3:数ChAを受け取った証明者アルゴリズムPは、z=1~kについて、t1z←ChAqz-1r0-t0zを計算する。次いで、証明者アルゴリズムPは、e1←ChAFr0-e0を計算する。工程3で生成されたt11,...,t1k,e1は、検証者アルゴリズムVに送られる。工程4:t11,...,t1k,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は、c0=Hr0,ChAq0r0-t11,...,ChAqk-1r0-t1k,ChAFr0-e1の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。ChB=1の場合、検証者アルゴリズムVは、c1=Hr1,ChAy-Fr1-ΣzGzt1z,r1の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、5パス方式に係る高次拡張アルゴリズムの構成例について説明した。このアルゴリズムを利用することにより、通信に必要なデータサイズが大幅に削減される。また、高次多項式を利用していることにより、より高い安全性が実現されている。3-4-2:並列化アルゴリズム構成例1図15次に、図15を参照しながら、5パス方式に係る高次拡張アルゴリズムの並列化について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。工程1:図15に示すように、証明者アルゴリズムPは、i=1~Nについて、次の処理を実行する。まず、証明者アルゴリズムPは、ランダムにベクトルr0i,t01i,...,t0ki∈Kn及びe0i∈Kmを生成する。次いで、証明者アルゴリズムPは、r1i←s-r0iを計算する。この計算は、秘密鍵sをベクトルr0iによりマスクする操作に相当する。次いで、証明者アルゴリズムPは、c0i←Hr0i,t01i,...,t0ki,e0iを計算する。次いで、証明者アルゴリズムPは、c1i←Hr1i,ΣzGzt0zi,r1ie0i但し、Σzはz=1~kについての和を表す。を計算する。工程1で生成されたメッセージc0i,c1ii=1~Nは、検証者アルゴリズムVに送られる。工程2:メッセージc0i,c1ii=1~Nを受け取った検証者アルゴリズムVは、ランダムに数ChA1,...,ChANを選択する。この数ChA1,...,ChANは証明者アルゴリズムPに送られる。工程3:数ChA1,...,ChANを受け取った証明者アルゴリズムPは、i=1~N及びz=1~kについて、t1zi←ChAiqz-1r0i-t0ziを計算する。次いで、証明者アルゴリズムPは、e1i←ChAiFr0i-e0iを計算する。工程3で生成されたt11i,...,t1ki,e1ii=1~Nは、検証者アルゴリズムVに送られる。工程4:t11i,...,t1ki,e1ii=1~Nを受け取った検証者アルゴリズムVは、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を生成する。ChBi=1の場合、証明者アルゴリズムPは、返答Rspi=r1iを生成する。工程5で生成された返答Rspii=1~Nは、検証者アルゴリズムVに送られる。工程6:返答Rspii=1~Nを受け取った検証者アルゴリズムVは、受け取った返答Rspiを利用し、i=1~Nについて次の認証処理を実行する。ChBi=0の場合、検証者アルゴリズムVは、c0i=Hr0i,ChAiq0r0i-t11i,...,ChAiqk-1r0i-t1ki,ChAiFr0i-e1iの等号が成り立つか否かを検証する。ChBi=1の場合、検証者アルゴリズムVは、c1i=Hr1i,ChAiy-Fr1i-ΣzGzt1zi,r1iの等号が成り立つか否かを検証する。検証者アルゴリズムVは、全ての検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、5パス方式に係る高次拡張アルゴリズムの並列化について説明した。このアルゴリズムを利用することにより、通信に必要なデータサイズが大幅に削減される。また、高次多項式を利用していることにより、より高い安全性が実現されている。3-4-3:並列化アルゴリズム構成例2:高効率図16さて、図15に示した高次拡張アルゴリズムの並列化構成において、1パス目にメッセージc0i,c1ii=1~Nをそのまま送っていた。しかし、通信効率を考えると、メッセージc0i,c1ii=1~Nを1つのハッシュ値に纏めて送る方が好ましい。1パス目でメッセージc0i,c1ii=1~Nを1つのハッシュ値に纏めて送るには、図16に示すようにアルゴリズムの構成を変形すればよい。図16の構成例において、証明者アルゴリズムPは、工程1でハッシュ値Cmt←Hc01,c11,...,c0N,c1Nを計算している。また、証明者アルゴリズムPは、工程5で返答Rspiを生成する際、ChBi=0の場合に返答Rspi=r0i,c1iを生成し、ChBi=1の場合に返答Rspi=r1i,c0iを生成している。一方、検証者アルゴリズムVは、工程6において、ChAi,ChBi,Rspii=1~Nからc01,c11,...,c0N,c1Nを生成し、Cmt=c01,c11,...,c0N,c1Nの等号が成り立つか否かを検証している。これらの変形を行うことにより、通信効率を高めることが可能になる。以上、高次拡張アルゴリズムに基づく効率的な並列化アルゴリズムについて説明した。3-4-4:並列化アルゴリズム構成例2:更に高効率図17さて、図15に示した高次拡張アルゴリズムの並列化構成において、1パス目にメッセージc0i,c1ii=1~Nをそのまま送っていた。さらに、3パス目にt11i,...,t1ki,e1ii=1~Nをそのまま送っていた。しかし、通信効率を考えると、メッセージc0i,c1ii=1~Nを1つのハッシュ値に纏めて送る方が好ましい。さらに、t11i,...,t1ki,e1ii=1~Nを1つのハッシュ値に纏めて送る方が好ましい。1パス目でメッセージc0i,c1ii=1~Nを1つのハッシュ値に纏めて送り、3パス目でt11i,...,t1ki,e1ii=1~Nを1つのハッシュ値に纏めて送るには、図17に示すようにアルゴリズムの構成を変形すればよい。図17の構成例において、証明者アルゴリズムPは、工程1でハッシュ値CmtA←Hc01,c11,...,c0N,c1Nを計算している。証明者アルゴリズムPは、工程3でハッシュ値CmtB←Ht111,...,t1kN,e11,...,e1Nを計算している。また、証明者アルゴリズムPは、工程5で返答Rspiを生成する際、ChBi=0の場合に返答Rspi=r0i,t01i,...,t0ki,e0i,c1iを生成し、ChBi=1の場合に返答Rspi=r1i,t11i,...,t1ki,e1i,c0iを生成している。一方、検証者アルゴリズムVは、工程6において、ChAi,ChBi,Rspii=1~Nからc01,c11,...,c0N,c1N及びt111,...,t1kN,e11,...,e1Nを生成し、CmtA=c01,c11,...,c0N,c1N及びCmtB=t111,...,t1kN,e11,...,e1Nの等号が成り立つか否かを検証している。これらの変形を行うことにより、通信効率を更に高めることが可能になる。以上、高次拡張アルゴリズムに基づく更に効率的な並列化アルゴリズムについて説明した。以上説明した高次拡張アルゴリズムを適用することにより、より安全性が高く効率的な公開鍵認証方式を実現することが可能になる。例えば、5パス方式の拡張アルゴリズムにおいて、q,n,m,N=24,45,30,88とする場合、公開鍵のサイズは120ビット、秘密鍵のサイズは180ビット、通信データのサイズは27512ビットとなる。同程度の安全性を担保しようとすると、5パス方式の高次拡張アルゴリズムの場合、例えば、q,n,m,N=22,42,40,118の条件で済む。この条件において、公開鍵のサイズは80ビット、秘密鍵のサイズは84ビット、通信データのサイズは27814ビットとなる。つまり、高次拡張アルゴリズムを適用することにより、通信データのサイズを同程度に維持しながら、公開鍵のサイズ及び秘密鍵のサイズを大幅に低減することが可能になる。なお、条件をq,n,m,N=23,28,27,97に変更してもよい。この場合、公開鍵のサイズは81ビット、秘密鍵のサイズは84ビット、通信データのサイズは27145ビットとなる。さらに、条件をq,n,m,N=24,21,20,88に変更してもよい。この場合、公開鍵のサイズは80ビット、秘密鍵のサイズは84ビット、通信データのサイズは28392ビットとなる。いずれの条件においても、大幅な効率化が達成されている。<4:電子署名方式への変形>ここで、上記の公開鍵認証方式を電子署名方式へと変形する方法を紹介する。公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させると、証明者のみが検証者を納得させられるという点において、電子署名方式のモデルと近似していることが容易に理解されよう。こうした考えに基づき、上述した公開鍵認証方式を電子署名方式へと変形する方法について説明する。[4-1:3パスの公開鍵認証方式から電子署名方式への変形]まず、3パスの公開鍵認証方式から電子署名方式への変形について説明する。4-1-1:電子署名アルゴリズム構成例1図18図18に示すように、3パス方式に係る効率的なアルゴリズム例えば、図6及び図8を参照は、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で表現される公開鍵認証方式のアルゴリズムは、図18に示すような署名生成アルゴリズム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-1-2:電子署名アルゴリズム構成例2:高効率図19ところで、図18に示した署名生成アルゴリズムSigの構成に注目すると、処理2及び処理3でハッシュ値の計算を行っていることに気づくであろう。また、署名検証アルゴリズムVerの構成に注目すると、処理1において、署名生成アルゴリズムSigの処理3と同じハッシュ値の計算を行っていることに気づくであろう。これらの処理に注目し、図19に示すように署名生成アルゴリズムSig及び署名検証アルゴリズムVerの構成を改良すると、さらに計算効率を向上させることができる。署名生成アルゴリズムSigまず、図19を参照しながら、改良後の署名生成アルゴリズムSigの構成について説明する。署名生成アルゴリズムSigは、以下の処理1~処理4で構成される。処理1:署名生成アルゴリズムSigは、ai=r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1i,c2iを生成する。処理2:署名生成アルゴリズムSigは、Ch1,...,ChN←HM,c01,c11,c21,...,c0N,c1N,c2Nを計算する。このMは、署名を付与する文書である。処理3:署名生成アルゴリズムSigは、Rspi←SelectChi,aiを計算する。処理4:署名生成アルゴリズムSigは、Ch1,...,ChN,Rsp1,...,RspNを署名に設定する。署名検証アルゴリズムVer次に、改良後の署名検証アルゴリズムVerの構成について説明する。署名検証アルゴリズムVerは、以下の処理1及び処理2で構成される。処理1:署名検証アルゴリズムVerは、Ch1,...,ChN及びRsp1,...,RspNを用いてc01,c11,c21,...,c0N,c1N,c2Nを生成する。処理2:署名検証アルゴリズムVerは、再生したc01,c11,c21,...,c0N,c1N,c2Nを用いてCh1,...,ChN=Hc01,c11,c21,...,c0N,c1N,c2Nを検証する。上記のように署名生成アルゴリズムSig及び署名検証アルゴリズムVerの構成を改良することにより、各アルゴリズムにおいてハッシュ値の計算が1回ずつ削減され、計算効率が向上する。[4-2:5パスの公開鍵認証方式から電子署名方式への変形]次に、5パスの公開鍵認証方式から電子署名方式への変形について説明する。4-2-1:電子署名アルゴリズム構成例1図20図20に示すように、5パス方式に係る効率的なアルゴリズム例えば、図11、図13及び図16を参照は、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で表現される公開鍵認証方式のアルゴリズムは、図20に示すような署名生成アルゴリズム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を検証する。以上説明したように、公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させることで、公開鍵認証方式のアルゴリズムを電子署名方式のアルゴリズムへと変形することが可能になる。4-2-2:電子署名アルゴリズム構成例2:高効率図21図21に示すように、5パス方式に係る更に効率的なアルゴリズム例えば、図17を参照は、5回の対話及び6つの工程1~工程6で表現される。工程1は、i=1~Nについて、ai=r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1iを生成する処理1と、CmtA←Hc01,c11,...,c0N,c1Nを計算する処理2とで構成される。工程1で証明者アルゴリズムPにより生成されたCmtAは、検証者アルゴリズムVへと送られる。工程2は、ChA1,...,ChANを選択する処理で構成される。工程2で検証者アルゴリズムVにより選択されたChA1,...,ChANは、証明者アルゴリズムPへと送られる。工程3は、i=1~Nについて、bi=t1i,e1iを生成する処理1と、CmtB←Hb1,...,bNを計算する処理2とで構成される。工程3で証明者アルゴリズムPにより生成されたCmtBは、検証者アルゴリズム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,b1,...,bNを再生する処理1と、再生したc01,c11,...,c0N,c1Nを用いてCmtA=Hc01,c11,...,c0N,c1Nを検証する処理2と、再生したb1,...,bNを用いてCmtB=Hb1,...,bNを検証する処理3とで構成される。上記の工程1~工程6で表現される公開鍵認証方式のアルゴリズムは、図21に示すような署名生成アルゴリズムSig及び署名検証アルゴリズムVerに変形される。署名生成アルゴリズムSigまず、署名生成アルゴリズムSigの構成について述べる。署名生成アルゴリズムSigは、以下の処理1~処理8で構成される。処理1:署名生成アルゴリズムSigは、ai=r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1iを生成する。処理2:署名生成アルゴリズムSigは、CmtA←Hc01,c11,...,c0N,c1Nを計算する。処理3:署名生成アルゴリズムSigは、ChA1,...,ChAN←HM,CmtAを計算する。このMは、署名を付与する文書である。処理4:署名生成アルゴリズムSigは、i=1~Nについて、bi=t1i,e1iを生成する。処理5:署名生成アルゴリズムSigは、CmtB←Hb1,...,bNを計算する。処理6:署名生成アルゴリズムSigは、ChB1,...,ChBN←HM,Cmt,ChA1,...,ChAN,CmtBを計算する。なお、ChB1,...,ChBN←HChA1,...,ChAN,CmtBと変形してもよい。処理7:署名生成アルゴリズムSigは、Rspi←SelectChBi,ai,biを計算する。処理8:署名生成アルゴリズムSigは、CmtA,CmtB,Rsp1,...,RspNを電子署名に設定する。署名検証アルゴリズムVer次に、署名検証アルゴリズムVerの構成について述べる。署名検証アルゴリズムVerは、以下の処理1~処理5で構成される。処理1:署名検証アルゴリズムVerは、ChA1,...,ChAN←HM,CmtAを計算する。処理2:署名検証アルゴリズムVerは、ChB1,...,ChBN←HM,CmtA,ChA1,...,ChAN,CmtBを計算する。なお、署名検証アルゴリズムVerが実行する処理6において、ChB1,...,ChBN←HChA1,...,ChAN,CmtBと変形した場合、署名検証アルゴリズムVerは、ChB1,...,ChBN←HChA1,...,ChAN,CmtBを計算する。処理3:署名検証アルゴリズムVerは、ChA1,...,ChAN,ChB1,...,ChBN,Rsp1,...,RspNを用いてc01,c11,...,c0N,c1N,b1,...,bNを生成する。処理4:署名検証アルゴリズムVerは、再生したc01,c11,...,c0N,c1Nを用いてCmtA=Hc01,c11,...,c0N,c1Nを検証する。処理5:署名検証アルゴリズムVerは、再生したb1,...,bNを用いてCmtB=Hb1,...,bNを検証する。以上説明したように、公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させることで、公開鍵認証方式のアルゴリズムを電子署名方式のアルゴリズムへと変形することが可能になる。<5:ハイブリッド型アルゴリズム>偽証が成功する確率を無視できる程度にまで小さくするために、対話プロトコルを複数回実行する必要性については既に説明した通りである。また、対話プロトコルを複数回実行する方法として、直列的な方法と並列的な方法とを紹介した。特に、並列的な方法については、具体的な並列化アルゴリズムを示して説明した。ここでは、直列的な方法と並列的な方法とを組み合わせたハイブリッド型のアルゴリズムを紹介する。[5-1:3パスの公開鍵認証方式に係るハイブリッド型アルゴリズム]まず、3パスの公開鍵認証方式に係るハイブリッド型アルゴリズムについて説明する。5-1-1:並直列アルゴリズム図22図22を参照しながら、ハイブリッド型の一構成例以下、並直列構成について説明する。図22には、基本構成のアルゴリズム及び並直列構成のアルゴリズムを示した。基本構成の場合、1パス目にメッセージCmtが証明者から検証者へと送られる。2パス目では、検証者から証明者へと要求Chが送られる。3パス目では、証明者から検証者へと返答Rspが送られる。一方、並直列構成の場合、1パス目にN回分のメッセージCmt1,...,CmtNが証明者から検証者へと送られる。2パス目では、検証者から証明者へと1回分の要求Ch1が送られる。3パス目では、証明者から検証者へと1回分の返答Rsp1が送られる。その後、証明者と検証者との間で要求Ch2,...,ChN及び返答Rsp2,...,RspNのやり取りが逐次的に行われる。これまで説明してきた公開鍵認証方式のアルゴリズムに基づく並直列構成の場合、受動的攻撃に対する安全性が保証される。また、対話の回数が2N1回で済む。さらに、1パス目で送信されるN回分のメッセージを1つのハッシュ値に纏めると、通信効率を向上させることができる。5-1-2:直並列アルゴリズム図23図23を参照しながら、ハイブリッド型の他の一構成例以下、直並列構成について説明する。図23には、基本構成のアルゴリズム及び直並列構成のアルゴリズムを示した。基本構成の場合、1パス目にメッセージCmtが証明者から検証者へと送られる。2パス目では、検証者から証明者へと要求Chが送られる。3パス目では、証明者から検証者へと返答Rspが送られる。直並列構成の場合、1パス目に1回分のメッセージCmt1が証明者から検証者へと送られる。2パス目では、検証者から証明者へと1回分の要求Ch1が送られる。その後、証明者と検証者との間でメッセージCmt2,...,CmtN及び要求Ch2,...,ChNのやり取りが逐次的に行われる。要求ChNが検証者から証明者へと送られた後、証明者から検証者へとN回分の返答Rsp2,...,RspNが送られる。これまで説明してきた公開鍵認証方式のアルゴリズムに基づく直並列構成の場合、能動的攻撃に対する安全性が保証される。また、対話の回数が2N1回で済む。[5-2:5パスの公開鍵認証方式に係るハイブリッド型アルゴリズム]次に、5パスの公開鍵認証方式に係るハイブリッド型アルゴリズムについて説明する。5-2-1:並直列アルゴリズム構成例1図24まず、図24を参照しながら、ハイブリッド型の一構成例以下、並直列構成1について説明する。図24には、基本構成のアルゴリズム及び並直列構成1のアルゴリズムを示した。基本構成の場合、1パス目にメッセージCmtAが証明者から検証者へと送られる。2パス目では、検証者から証明者へと数ChAが送られる。3パス目では、証明者から検証者へとベクトルCmtBが送られる。4パス目では、検証者から証明者へと要求ChBが送られる。5パス目では、証明者から検証者へと返答Rspが送られる。並直列構成1の場合、1パス目にN回分のメッセージCmtA1,...,CmtANが証明者から検証者へと送られる。2パス目では、検証者から証明者へと1回分の数ChA1が送られる。3パス目では、証明者から検証者へと1回分のベクトルCmtB1が送られる。4パス目では、検証者から証明者へと1回分の要求ChB1が送られる。5パス目では、証明者から検証者へと1回分の返答Rsp1が送られる。その後、証明者と検証者との間で、ChA2,...,ChAN,CmtB2,...,CmtBN,ChB2,...,ChBN,Rsp2,...,RspNのやり取りが逐次的に行われる。並直列構成1の場合、受動的攻撃に対する安全性が保証される。また、対話の回数が4N1回で済む。さらに、1パス目で送信されるN回分のメッセージを1つのハッシュ値に纏めることにより、通信効率を向上させることができる。5-2-2:並直列アルゴリズム構成例2図25次に、図25を参照しながら、ハイブリッド型の他の一構成例以下、並直列構成2について説明する。図25には、基本構成のアルゴリズム及び並直列構成2のアルゴリズムを示した。並直列構成2の場合、1パス目にN回分のメッセージCmtA1,...,CmtANが証明者から検証者へと送られる。2パス目では、検証者から証明者へとN回分の数ChA1,...,ChANが送られる。3パス目では、証明者から検証者へとN回分のベクトルCmtB1,...,CmtBNが送られる。4パス目では、検証者から証明者へと1回分の要求ChB1が送られる。5パス目では、証明者から検証者へと1回分の返答Rsp1が送られる。その後、証明者と検証者との間で、ChB2,...,ChBN,Rsp2,...,RspNのやり取りが逐次的に行われる。並直列構成2の場合、受動的攻撃に対する安全性が保証される。また、対話の回数が2N3回で済む。さらに、1パス目で送信されるN回分のメッセージや3パス目で送信されるN回分のベクトルなどを1つのハッシュ値に纏めることにより、通信効率を向上させることができる。5-2-3:直並列アルゴリズム構成例1図26次に、図26を参照しながら、ハイブリッド型の他の一構成例以下、直並列構成1について説明する。図26には、基本構成のアルゴリズム及び直並列構成1のアルゴリズムを示した。直並列構成1の場合、1パス目に1回分のメッセージCmtA1が証明者から検証者へと送られる。2パス目では、検証者から証明者へと1回分の数ChA1が送られる。3パス目では、証明者から検証者へと1回分のベクトルCmtB1が送られる。4パス目では、検証者から証明者へと1回分の要求ChB1が送られる。その後、証明者と検証者との間で、CmtA2,...,CmtAN,ChA2,...,ChAN,CmtB2,...,CmtBN,ChB2,...,ChBNのやり取りが逐次的に行われる。最後に、証明者から検証者へとN回分の返答Rsp1...,RspNが送られる。直並列構成1の場合、能動的攻撃に対する安全性が保証される。また、対話の回数が4N1回で済む。5-2-4:直並列アルゴリズム構成例2図27次に、図27を参照しながら、ハイブリッド型の他の一構成例以下、直並列構成2について説明する。図27には、基本構成のアルゴリズム及び直並列構成2のアルゴリズムを示した。直並列構成2の場合、1パス目に1回分のメッセージCmtA1が証明者から検証者へと送られる。2パス目では、検証者から証明者へと1回分の数ChA1が送られる。その後、証明者と検証者との間で、CmtA2,...,CmtAN,ChA2,...,ChANのやり取りが逐次的に行われる。ChANのやり取りを終えた後、証明者から検証者へとN回分のベクトルCmtB1,...,CmtBNが送られる。次いで、検証者から証明者へとN回分の要求ChB1,...,ChB1が送られる。最後に、証明者から検証者へとN回分の返答Rsp1...,RspNが送られる。直並列構成2の場合、能動的攻撃に対する安全性が保証される。また、対話の回数が2N3回で済む。以上、5パスの公開鍵認証方式に係るハイブリッド型アルゴリズムについて説明した。<6:補遺>ここで、上記の公開鍵認証方式に関する説明の補足を行う。[6-1:パラメータの設定方法]ここで、パラメータの設定方法について説明を補足する。多変数多項式の係数についてこれまで、多変数多項式の係数又はその係数の生成に利用する乱数シード以下、多変数多項式の係数などをどのように設定するかについては詳しく言及してこなかった。多変数多項式の係数などは、システムに共通のパラメータとしてもよいし、ユーザ毎に異なるパラメータとしてもよい。しかし、多変数多項式の係数などをシステムに共通のパラメータとすると、その多変数多項式に脆弱性が見つかった場合、システム全体について設定を更新する必要が生じてしまう。また、ランダムに選んだ係数を持つ多変数多項式について、平均的な頑強性解くことの難しさは解析されているが、ある特定の係数を持つ多変数多項式について十分な頑強性を有することを保証することは難しい。そこで、本件発明者は、各ユーザが選択した文字列などを擬似乱数生成器のシードに利用して多変数多項式の係数を生成する仕組みを考案した。例えば、ユーザのe-mailアドレスをシードに利用したり、e-mailアドレスと更新日時などとを結合した文字列をシードに利用したりする方法などが考えられる。このような方法を用いると、万が一、ある文字列から生成された係数を持つ多変数多項式に脆弱性が見つかった場合でも、その係数を持つ多変数多項式を利用しているユーザのみに影響が限定される。また、文字列を変えるだけで多変数多項式が変更されるため、容易に脆弱性を解消することができる。以上、システムパラメータの設定方法について説明した。なお、上記の説明では文字列を例に挙げたが、ユーザ毎に異なる数字の列や記号の列を利用してもよい。多項式の数m及び変数の数nについてところで、これまで説明してきた対話プロトコルは、受動的攻撃に対する安全性が保証されている。しかし、この対話プロトコルを並列的に繰り返し実行する場合、能動的攻撃に対する安全性が確実に保証されることを証明できるようにするには、以下で述べる条件が必要になる。上記の対話プロトコルは、1組の鍵ペア公開鍵y、秘密鍵sを用いて、証明者がyについてy=Fsとなるsを知っていることを検証者に検証させるためのアルゴリズムであった。そのため、検証で受理される対話を行った場合、対話の際に証明者がsを用いたという情報を検証者に知られてしまう可能性が否定できない。また、多変数多項式Fについて衝突困難性が保証されてない。そのため、上記の対話プロトコルを並列的に繰り返し実行する場合、能動的攻撃に対する安全性が確実に保証されていることを無条件で証明することは難しい。そこで、本件発明者は、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにする方法について検討した。そして、本件発明者は、上記の対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性を保証することが可能になる方法を考案した。この方法は、公開鍵として用いる多変数多項式f1,...,fmの数mをその変数の数nよりも十分に小さな値に設定するというものである。例えば、2m-n≪1となるようにm及びnが設定される例えば、n=160、m=80の場合2-80≪1である。。多次多変数方程式の求解問題に対する解答の困難性に安全性の根拠をおく方式において、秘密鍵s1と、それに対応する公開鍵pkとが与えられても、その公開鍵pkに対応する別の秘密鍵s2を生成することは難しい。そのため、公開鍵pkに対する秘密鍵sが2つ以上存在することを保証すれば、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにすることが可能になる。つまり、この保証が成り立てば、対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性を保証することが可能になる。図29を参照しながら、m本のn変数多次多項式で構成される関数F:Kn→Kmについて考えると但し、n>m、2つ目の原像を持たない定義域の要素数は、最大で|K|m-1個しか存在しない。そのため、|K|m-nを十分に小さくすると、2つ目の原像を持たない定義域の要素が選択される確率を無視できる程度にまで小さくすることができる。つまり、n変数多次多項式f1,...,fmの数mがその変数の数nよりも十分に小さな値に設定されていれば、公開鍵pkに対して2つ以上の秘密鍵sが存在することを保証できる。その結果、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにすることが可能になり、対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性が保証される。以上説明したように、n変数多次多項式f1,...,fmの数mがその変数の数nよりも小さな値n>m;好ましくは2m-n≪1に設定する設定条件を課すことで、対話プロトコルを並列的に繰り返し実行する場合の安全性を保証することが可能になる。[6-2:イレギュラーな要求に対する応答方法]ここで、イレギュラーな要求に対する応答方法について考察する。6-2-1:証明者による応答方法について対話プロトコルの中で検証者が偽りの要求を投げかけてくる可能性について考えてみよう。例えば、3パス方式の場合、証明者が検証者へとメッセージc0,c1,c2を送り、検証者が証明者へと要求Ch=0を送った後、証明者から検証者へと要求Ch=0に対応する返答Rspが送られる。ここまでは正常な対話である。その後で、検証者が、証明者に要求Ch=1に対応する返答Rspをさらに要求したものとしよう。もし、この要求に応じ、証明者が要求Ch=1に対応する返答Rspを検証者に送ってしまうと、秘密鍵が検証者に漏洩してしまう。このような秘密鍵の漏洩は現実的に起こりうることである。例えば、検証者は、2パス目で要求Ch=1を送信したのではなく、要求Ch=0を送信したはずだと偽って、要求Ch=1に対応する返答Rspをさらに要求するかもしれない。一方、証明者は、2パス目で送信された要求Chのビットが通信エラーにより別のビットになってしまったと勘違いするかもしれない。そこで、本件発明者は、秘密鍵の漏洩が生じるのを避ける方法として、1回分のメッセージについて証明者が2通り以上の要求Chに対応する返答を求めてきた場合に、対話を終了するか、或いは、新しい乱数を利用して1パス目から対話をやり直す方法を考案した。この方法を適用すれば、検証者が偽って2通り以上の要求Chに対応する返答を求めてきても、秘密鍵が漏洩することはなくなる。6-2-2:検証者による応答方法について次に、証明者が偽って要求Chの再送を要求してくる可能性について考えてみよう。例えば、3パス方式において、証明者が検証者へとメッセージc0,c1,c2を送り、検証者が証明者へと要求Ch=0を送った後、証明者が要求Chの再送を要求してきたとしよう。この要求に応じて、検証者が再びランダムに要求Chを選択すると、先に送った要求Ch=0とは異なる要求Ch=1が選択される可能性がある。この場合、検証者から証明者へと要求Ch=1が送られる。仮に、証明者が要求Ch=1に対応する返答Rspを検証者に送ることができたとしよう。この場合、証明者は、要求Ch=1には回答できるが、要求Ch=0には回答できなかったのかもしれない。つまり、証明者が偽証している可能性が否定できない。例えば、証明者は、要求Chを紛失してしまったので要求Chを再送して欲しいと検証者に求めるかもしれない。一方、検証者は、通信エラーにより先に送信した要求が紛失したと考え、証明者の求めに応じて要求Chを再送してしまうかもしれない。そして、再送した要求Chが先に送信した要求Chと異なるものである場合、偽証が成功してしまう。この例から分かるように、要求Chがランダムに選ばれることで、証明者に偽証の機会を与えてしまう。そこで、本件発明者は、偽証の機会を与えないようにするため、1回分のメッセージについて証明者が要求Chの送信を再度求めてきた場合に、検証者が対話を終了するか、或いは、新たな乱数を生成せずに前回と同じ要求Chを再送するように対話プロトコルを改良する方法を考案した。この方法を適用すると、要求Chの再送要求を利用した偽証の機会をなくすことができる。以上、イレギュラーな要求に対する安全な応答方法について説明した。なお、上記の説明においては3パスの基本構成を例に挙げたが、直列的な繰り返し構成、並列的な繰り返し構成、或いは、ハイブリッド型の繰り返し構成についても同様の工夫を加えることにより、安全性を向上させることができる。もちろん、5パスのアルゴリズムについても同様である。<7:ハードウェア構成例>上記の各アルゴリズムは、例えば、図28に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図28に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、PHS、PDA等の携帯情報端末、ゲーム機、接触式又は非接触式のICチップ、接触式又は非接触式のICカード、又は種々の情報家電がこれに含まれる。但し、上記のPHSは、PersonalHandy-phoneSystemの略である。また、上記のPDAは、PersonalDigitalAssistantの略である。図28に示すように、このハードウェアは、主に、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の略である。<8:まとめ>最後に、本技術の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、PC、携帯電話、ゲーム機、情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置に対して適用することができる。なお、以下で述べる情報処理装置の機能は、1台の情報処理装置を利用して実現することも可能であるし、複数台の情報処理装置を利用して実現することも可能である。また、以下で述べる情報処理装置が処理を実行する際に用いるデータ記憶手段及び演算処理手段は、当該情報処理装置に設けられたものであってもよいし、ネットワークを介して接続された機器に設けられたものであってもよい。上記の情報処理装置の機能構成は以下のように表現される。例えば、下記1に記載の情報処理装置は、多次多変数連立方程式の求解困難性に安全性の根拠を置く効率的な公開鍵認証方式又は電子署名方式のアルゴリズムを実行する機能を有する。1環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、情報処理装置。2前記メッセージ生成部は、N回分N≧2のメッセージを生成し、前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、上記1に記載の情報処理装置。3環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、情報処理装置。4前記メッセージ取得部は、N回分N≧2の前記メッセージを1回の対話で取得し、前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、上記3に記載の情報処理装置。5環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、前記検証者に前記第3の情報を提供する中間情報提供部と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、情報処理装置。6前記メッセージ生成部は、N回分N≧2のメッセージを生成し、前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、前記中間情報生成部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した前記第1の情報及び前記メッセージを生成する際に得られるN回分の前記第2の情報を用いてN回分の前記第3の情報を生成し、前記中間情報提供部は、N回分の前記第3の情報を1回の対話で検証者に提供し、前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、上記5に記載の情報処理装置。7環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供部と、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得部と、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、情報処理装置。8前記メッセージ取得部は、N回分N≧2の前記メッセージを1回の対話で取得し、前記情報提供部は、N回分の前記メッセージのそれぞれについて前記第1の情報をランダムに選択し、選択したN回分の前記第1の情報を1回の対話で前記証明者に提供し、前記中間情報取得部は、N回分の前記第1の情報及びN回分の前記メッセージを生成する際に得られるN回分の前記第2の情報を用いて前記証明者が生成したN回分の前記第3の情報を取得し、前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、上記7に記載の情報処理装置。9環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供部と、文書M及び前記メッセージを一方向性関数に入力して得られる数値に基づき、k通りk≧3の検証パターンの中から1つの検証パターンを選択するパターン選択部と、選択した前記検証パターンに対応する回答情報を生成する回答生成部と、署名として、前記メッセージ及び前記回答情報を前記検証者に提供する署名提供部と、を備え、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、署名生成装置。10環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、情報処理方法。11環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報処理装置が、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、情報処理方法。12環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、前記検証者に前記第3の情報を提供するステップと、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、情報処理方法。13環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報処理装置が、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供するステップと、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得するステップと、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、情報処理方法。14環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するステップと、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するステップと、文書M及び前記メッセージを一方向性関数に入力して得られる数値に基づき、k通りk≧3の検証パターンの中から1つの検証パターンを選択するステップと、選択した前記検証パターンに対応する回答情報を生成するステップと、署名として、前記メッセージ及び前記回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、署名生成方法。15環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、k通りk≧3の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、プログラム。16環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持機能と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得機能と、前記メッセージを提供した証明者に対し、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するパターン情報提供機能と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得機能と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、プログラム。17環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成機能と、前記検証者に前記第3の情報を提供する中間情報提供機能と、k通りk≧2の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、プログラム。18環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持機能と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得機能と、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供機能と、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得機能と、k通りk≧3の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供機能と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得機能と、前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して線形となるように設定される、プログラム。19環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に前記メッセージを提供するメッセージ提供機能と、文書M及び前記メッセージを一方向性関数に入力して得られる数値に基づき、k通りk≧3の検証パターンの中から1つの検証パターンを選択するパターン選択機能と、選択した前記検証パターンに対応する回答情報を生成する回答生成機能と、署名として、前記メッセージ及び前記回答情報を前記検証者に提供する署名提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは秘密鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記多次多変数多項式の組Fは、m本の3次多項式f1,...,fmで構成され、G1x1,x2G2x1,x2=Fx1x2-Fx1-Fx2で定義されるG1x1,x2及びG2x1,x2がそれぞれx1及びx2に関して加法準同型となるように設定される、プログラム。20前記m及びnは、m<nの関係を有する、上記1~9のいずれか1項に記載の装置。21前記m及びnは、2m-n≪1の関係を有する、上記20に記載の装置。22上記15~19のいずれか1項に記載のプログラムが記録された、コンピュータにより読み取り可能な記録媒体。備考上記の証明者アルゴリズムPは、メッセージ生成部、メッセージ提供部、回答提供部、中間情報生成部、中間情報提供部の一例である。また、上記の検証者アルゴリズムVは、情報保持部、メッセージ取得部、パターン情報提供部、回答取得部、検証部、中間情報取得部の一例である。以上、添付図面を参照しながら本技術の好適な実施形態について説明したが、本技術は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本技術の技術的範囲に属するものと了解される。"